主成分分析

線(xiàn)性判別分析

流形學(xué)習(xí)中的拉普拉斯特征映射

隱馬爾科夫模型

5.凸優(yōu)化

數(shù)值優(yōu)化算法面臨兩個(gè)方面的問(wèn)題：局部極值，鞍點(diǎn)。前者是梯度為0的點(diǎn)，也是極值點(diǎn)，但不是全局極小值；后者連局部極值都不是，在鞍點(diǎn)處Hessian矩陣不定，即既非正定，也非負(fù)定。
凸優(yōu)化通過(guò)對(duì)目標(biāo)函數(shù)，優(yōu)化變量的可行域進(jìn)行限定，可以保證不會(huì)遇到上面兩個(gè)問(wèn)題。凸優(yōu)化是一類(lèi)特殊的優(yōu)化問(wèn)題，它要求：

優(yōu)化變量的可行域是一個(gè)凸集

目標(biāo)函數(shù)是一個(gè)凸函數(shù)

凸優(yōu)化最好的一個(gè)性質(zhì)是：所有局部最優(yōu)解一定是全局最優(yōu)解。機(jī)器學(xué)習(xí)中典型的凸優(yōu)化問(wèn)題有：

線(xiàn)性回歸

嶺回歸

LASSO回歸

Logistic回歸

支持向量機(jī)

Softamx回歸

6.拉格朗日對(duì)偶

對(duì)偶是最優(yōu)化方法里的一種方法，它將一個(gè)最優(yōu)化問(wèn)題轉(zhuǎn)換成另外一個(gè)問(wèn)題，二者是等價(jià)的。拉格朗日對(duì)偶是其中的典型例子。對(duì)于如下帶等式約束和不等式約束的優(yōu)化問(wèn)題：

與拉格朗日乘數(shù)法類(lèi)似，構(gòu)造廣義拉格朗日函數(shù)：

必須滿(mǎn)足

的約束。原問(wèn)題為：

即先固定住x，調(diào)整拉格朗日乘子變量，讓函數(shù)L取極大值；然后控制變量x，讓目標(biāo)函數(shù)取極小值。原問(wèn)題與我們要優(yōu)化的原始問(wèn)題是等價(jià)的。
對(duì)偶問(wèn)題為：

和原問(wèn)題相反，這里是先控制變量x，讓函數(shù)L取極小值；然后控制拉格朗日乘子變量，讓函數(shù)取極大值。
一般情況下，原問(wèn)題的最優(yōu)解大于等于對(duì)偶問(wèn)題的最優(yōu)解，這稱(chēng)為弱對(duì)偶。在某些情況下，原問(wèn)題的最優(yōu)解和對(duì)偶問(wèn)題的最優(yōu)解相等，這稱(chēng)為強(qiáng)對(duì)偶。
強(qiáng)對(duì)偶成立的一種條件是Slater條件：一個(gè)凸優(yōu)化問(wèn)題如果存在一個(gè)候選x使得所有不等式約束都是嚴(yán)格滿(mǎn)足的，即對(duì)于所有的i都有g(shù)i (x)<0，不等式不取等號(hào)，則強(qiáng)對(duì)偶成立，原問(wèn)題與對(duì)偶問(wèn)題等價(jià)。注意，Slater條件是強(qiáng)對(duì)偶成立的充分條件而非必要條件。
拉格朗日對(duì)偶在機(jī)器學(xué)習(xí)中的典型應(yīng)用是支持向量機(jī)。

7.KKT條件

KKT條件是拉格朗日乘數(shù)法的推廣，用于求解既帶有等式約束，又帶有不等式約束的函數(shù)極值。對(duì)于如下優(yōu)化問(wèn)題：

和拉格朗日對(duì)偶的做法類(lèi)似，KKT條件構(gòu)如下乘子函數(shù)：

和

稱(chēng)為KKT乘子。在最優(yōu)解處

應(yīng)該滿(mǎn)足如下條件：

等式約束

和不等式約束

是本身應(yīng)該滿(mǎn)足的約束，

和之前的拉格朗日乘數(shù)法一樣。唯一多了關(guān)于gi (x)的條件：

KKT條件只是取得極值的必要條件而不是充分條件。
 

8.特征值與特征向量

對(duì)于一個(gè)n階矩陣A，如果存在一個(gè)數(shù)

和一個(gè)非0向量X，滿(mǎn)足：

則稱(chēng)

為矩陣A的特征值，X為該特征值對(duì)應(yīng)的特征向量。根據(jù)上面的定義有下面線(xiàn)性方程組成立：

上式左邊的多項(xiàng)式稱(chēng)為矩陣的特征多項(xiàng)式。矩陣的跡定義為主對(duì)角線(xiàn)元素之和：

根據(jù)韋達(dá)定理，矩陣所有特征值的和為矩陣的跡：

同樣可以證明，矩陣所有特征值的積為矩陣的行列式：

利用特征值和特征向量，可以將矩陣對(duì)角化，即用正交變換將矩陣化為對(duì)角陣。實(shí)對(duì)稱(chēng)矩陣一定可以對(duì)角化，半正定矩陣的特征值都大于等于0，在機(jī)器學(xué)習(xí)中，很多矩陣都滿(mǎn)足這些條件。特征值和特征向量在機(jī)器學(xué)習(xí)中的應(yīng)用包括：正態(tài)貝葉斯分類(lèi)器、主成分分析，流形學(xué)習(xí)，線(xiàn)性判別分析，譜聚類(lèi)等。 

9.奇異值分解

矩陣對(duì)角化只適用于方陣，如果不是方陣也可以進(jìn)行類(lèi)似的分解，這就是奇異值分解，簡(jiǎn)稱(chēng)SVD。假設(shè)A是一個(gè)m x n的矩陣，則存在如下分解：

其中U為m x m的正交矩陣，其列稱(chēng)為矩陣A的左奇異向量；

為m x n的對(duì)角矩陣，除了主對(duì)角線(xiàn)

以外，其他元素都是0；V為n x n的正交矩陣，其行稱(chēng)為矩陣A的右奇異向量。U的列為AAT的特征向量，V的列為AT A的特征向量。 

10.最大似然估計(jì)