机器学习基础：最优化方法
本文先總結(jié)了凸函數(shù)、hessian矩陣、泰勒展開(kāi)、拉格朗日乘子、對(duì)偶函數(shù)，隨后介紹了最優(yōu)化中常用的梯度下降法、牛頓法、共軛梯度法、線性搜索法、置信域方法，最后介紹了其他的一些流行的最優(yōu)化方法，模擬退火法和爬山法、遺傳算法、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)。
? ? ?一、最優(yōu)化基礎(chǔ)：
? ? 1. ?凸函數(shù)：
? ? ? ? ? ? ? 凸函數(shù)有很多優(yōu)良的特性，而且在求解極大值極小值時(shí)，十分有用。先看一下凸函數(shù)的定義：凸函數(shù)：在函數(shù)的區(qū)間I上，若對(duì)任意x1和x2，任意0<t<1，都有
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? ? ? ? ?或者對(duì)任意x1,x2都有：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? ? ? ? ?凸函數(shù)有很多優(yōu)良的：
? ? ? ? ? ? ? ? ? ? ? ? 1. 凸函數(shù)任何極小值也是最小值。
? ? ? ? ? ? ? ? ? ? ? ? 2. 一元二階的函數(shù)在區(qū)間上市凸的，當(dāng)且僅當(dāng)它的二階倒數(shù)是非負(fù)的；如果一個(gè)函數(shù)的二階導(dǎo)數(shù)是正數(shù)，那么函數(shù)也就是嚴(yán)格凸的。反過(guò)來(lái)不成立。多遠(yuǎn)二次可微的連續(xù)函數(shù)在凸集上是可微的，當(dāng)且僅當(dāng)它的hessian矩陣在凸集內(nèi)部是半正定的。
? ? ? ? ? ? ? ? ? ? ? ? 3. ? 對(duì)于凸函數(shù)f，水平子集{x| f(x) <=a}和{x|f(x)<=a}是凸集。然而，水平子集是凸集的函數(shù)不一定是凸函數(shù)；這樣的函數(shù)被稱(chēng)為擬凸函數(shù)。
? ? ? ? ? ? ? ? ? ? ? ? 4. ?凸函數(shù)的求和、最大也是凸函數(shù)；如果g(x)是遞增的，那么g(f(x))仍然是凸函數(shù)。
? ? 2. ?hessian矩陣：
? ? ? ? ? ? ? hessian(海瑟矩陣)就是所謂的二階偏倒矩陣。對(duì)于一個(gè)臨界點(diǎn)有一階偏導(dǎo)等于零，然而憑借一階偏導(dǎo)數(shù)無(wú)法確定這個(gè)點(diǎn)是鞍點(diǎn)、局部極大點(diǎn)還是局部極小點(diǎn)。而hessian矩陣可以回答這個(gè)問(wèn)題。
? ? ? ? ? ? ? ? ? ? ??? ? ? ?
? ? ? ? ? ? ?若x0是f(x)的極值點(diǎn)，如果存在，則進(jìn)一步設(shè)在一個(gè)鄰域內(nèi)所有二階導(dǎo)數(shù)連續(xù)，H為在點(diǎn)x0的海瑟矩陣。而且x0是f(x)的極小值點(diǎn)時(shí)H>=0，即H的特征根均為非負(fù)。x0是f(x)的極大值點(diǎn)，H<=0, 即H的特征根均為非負(fù)。H>0，即H為正定矩陣，x0是f(x)的極小值點(diǎn)；H<0，即H為負(fù)定矩陣，x0是f(x)的極大值點(diǎn)；H的特征值有正有負(fù)，x0不是f(x)的極值點(diǎn)。
? ? 3. ?正定矩陣：
? ? ? ? ? ? ?設(shè)M是n階方陣，如果對(duì)任何非零變量z，都有z'Mz>0,其中z'表示z的轉(zhuǎn)置，就稱(chēng)M正定矩陣。
? ? ? ? ? ? ?判定定理1：矩陣A的特征值全為正。
? ? ? ? ? ? ?判定定理2：A的各階主子式為正。
? ? ? ? ? ? ?判定定理3：A合同于單位陣。
? ? 4. ?泰勒展開(kāi)：
? ? ? ? ? ? ?泰勒公式可以用若干項(xiàng)加一起來(lái)表示一個(gè)函數(shù)。對(duì)于正整數(shù)n，若函數(shù)f(x)在閉區(qū)間[a,b]上n階可導(dǎo)，切在(a,b)上面n+1階可導(dǎo)數(shù)。任取a<=x<=b，則有：
? ? ? ? ? ? ?
? ? ? ? ? ? 拉格朗日余數(shù)：
? ? ? ? ? ??
? ? ? ? ? ? 請(qǐng)注意：泰勒展開(kāi)在很多地方都有重要的應(yīng)用，例如開(kāi)方的計(jì)算。這里添加上牛頓迭代和泰勒級(jí)數(shù)展開(kāi)求解根號(hào)的計(jì)算過(guò)程。另外我一直以為泰勒級(jí)數(shù)和牛頓迭代有一定關(guān)系，后來(lái)發(fā)現(xiàn)好像沒(méi)有，不過(guò)可以把牛頓迭代看做僅取泰勒級(jí)數(shù)的一階展開(kāi)。
? ? ? ? ? ? 1). 使用泰勒級(jí)數(shù)求解根號(hào)2。此時(shí)我們可以得到f(x)=x^2-2;
? ? ? ? ? ? ? ? ? ? ? ? 取泰勒級(jí)數(shù)前兩項(xiàng)，我們可以得到： f(x)=f(a) + f'(a)(x-a)，令f(x)=0我們可以得到：
? ? ? ? ? ? ? ? ? ? ? ? ?x=a-f(a)/f'(a); 其實(shí)我們可以把x看做是f(x)=0的解，使用這個(gè)式子多次迭代就可以得到根號(hào)的值。使用x(n+1)替換x，x(n)替換a，我們就可以得到：x(n+1)=x(n)-f(x(n))/f'(x(n))=x(n)-(x(n)^2-2)/2*x(n).
? ? ? ? ? ? 2). 牛頓迭代法：
? ? ? ? ? ? ? ? ? ? ? ? 如下圖，已知(x0,y0) ,我們通過(guò)對(duì)f(x0)做切線，得到切線與x軸的交點(diǎn)(x1,0)，然后根據(jù)(x1,f(x1))繼續(xù)遞推得到(x2,f(x2))：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? ? ? ? ? ? ? ? ? ? 那么對(duì)已知的(x0,y0)，我們可以得到斜率：f'(x0)和點(diǎn)(x0,y0)，那么我們可以得到直線：y-f(x0)=f'(x0)(x-x0)。再令y=0，我們可以得到：f(x)=x0-f(x0)/f'(x0)。其實(shí)我們已經(jīng)得到了與泰勒級(jí)數(shù)展開(kāi)相同的迭代公式。
? ? ?5. ?拉格朗日乘子：
? ? ? ? ? ? ?拉格朗日乘子，就是求函數(shù)f(x1,x2,....)在g(x1,x2,....)=0的約束條件下的極值的方法。主要思想是通過(guò)引入一個(gè)新的參數(shù)λ，將約束條件和原函數(shù)聯(lián)系到一起，從而求出原函數(shù)極值的各個(gè)變量的解。假設(shè)需要求極值的目標(biāo)函數(shù)f(x,y)，約束條件為φ(x,y)=M，然后我們得到新的函數(shù)：?F(x,y,λ)=f(x,y)+λg(x,y)，將新函數(shù)分別對(duì)x,y,?λ求解即可得到原函數(shù)的極值。
? ? ?6. ?對(duì)偶函數(shù)：
? ? ?一、最優(yōu)化常見(jiàn)方法：
? ? ?1. ?牛頓法：
? ? ? ? ? ? ?看了一些文章我的理解是牛頓法在最優(yōu)化求解和前面的函數(shù)求解略有不同，此時(shí)是通過(guò)泰勒級(jí)數(shù)的二階展開(kāi)來(lái)進(jìn)行計(jì)算的。展開(kāi)泰勒級(jí)數(shù)的二階形式：
? ? ? ? ? ? ? ? ? ? ??
?? ? ? ? ? ? ?當(dāng)Δx 無(wú)限趨近于零時(shí)f(x+Δx )=f(x)，然后可以得到(注意f''(x)Δx+1/2f''(x))Δx^2=0)，然后將f'(x)和f''(x)看作常數(shù)，對(duì)Δx 再次求導(dǎo)即可得到如下公式：
? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? 繼續(xù)迭代可以得到：
? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ?得出迭代公式：
? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ?對(duì)于高緯的情況，我們可以得到如下迭代公式（其中H是海瑟矩陣）：
? ? ? ? ? ? ? ? ? ??
? ? ? ? ? ? 牛頓法引入了高階導(dǎo)數(shù)，利用了曲線的額外信息，迭代次數(shù)更很少，更容易收斂，可是也引入了hessian矩陣的復(fù)雜性。下圖為牛頓法和梯度下降法求解的一個(gè)例子，牛頓法為紅色，梯度下降法沿梯度方向?yàn)榫G色。其實(shí)牛頓法每次迭代都需要計(jì)算hessian矩陣，這極大增加了求解的復(fù)雜性，因而也有擬牛頓法和各種近似優(yōu)化方法，避免了每次都需要進(jìn)行迭代的方法。
? ? ?2. ?梯度下降法：
? ? ? ? ? ? ?梯度下降法，若實(shí)值函數(shù)F(x)在點(diǎn)a處可微且有意義，那么函數(shù)F(x)在a點(diǎn)沿著梯度相反的方向下降最快。因而并且足夠小時(shí)，我們從預(yù)估的F函數(shù)的局部極小值x0出發(fā)可以得到遞推公式：
如果順利的話，我們可以得到如下式子，并且xn會(huì)收斂到極值（注意可變）：
如果滿足條件，并且迭代收斂的話，我們就會(huì)沿著梯度下降的方向找到最小值。
? ? ?3. ?共軛梯度法：
? ? ? ? ? ? ?共軛梯度法是結(jié)余最快下降法和牛頓法的一個(gè)方法，它僅需利用一階導(dǎo)數(shù)信息，但克服了最快下降法收斂慢的缺點(diǎn)，又避免了牛頓法需要存儲(chǔ)和計(jì)算hessian矩陣并求逆的缺點(diǎn)（這么牛逼的介紹，簡(jiǎn)直是集眾多優(yōu)點(diǎn)于一身呀。。。存儲(chǔ)小、收斂快、穩(wěn)定性高、不需要額外參數(shù)。。?？磥?lái)還是需要深入研究）。
參考文獻(xiàn)：
1. 泰勒級(jí)數(shù)、牛頓展開(kāi)、求解根號(hào)：?http://www.linuxidc.com/Linux/2012-09/71467.htm
2. 拉格朗日乘子：http://baike.baidu.com/view/2415642.htm?fr=aladdin
3. 深入理解拉格朗日乘子和KKT法：http://blog.csdn.net/xianlingmao/article/details/7919597
4. 拉格朗日對(duì)偶：?http://www.cnblogs.com/liqizhou/archive/2012/05/11/2495689.html
5. 牛頓法和梯度下降法：http://blog.csdn.net/luoleicn/article/details/6527049
6. 共軛梯度法：?http://baike.baidu.com/view/2565822.htm?fr=aladdin
總結(jié)
以上是生活随笔為你收集整理的机器学习基础：最优化方法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 机器学习中的范数规则化之（二）核范数与规
- 下一篇： 矩阵的奇异值分解