主成分分析

線性判別分析

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

隱馬爾科夫模型

5.凸優(yōu)化

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

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

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

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

線性回歸

嶺回歸

LASSO回歸

Logistic回歸

支持向量機(jī)

Softamx回歸

6.拉格朗日對偶

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

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

必須滿足

的約束。原問題為：

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

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

7.KKT條件

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

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

和

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

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

等式約束

和不等式約束

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

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

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

8.特征值與特征向量

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

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

則稱

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

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

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

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

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

9.奇異值分解

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

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

為m x n的對角矩陣，除了主對角線

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

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