最近由於趕論文的deadline專欄一直沒有更新，也沒怎麼看書，所以還是只能吃老底，上次寫了數學估計方法，這次就來寫一下數學優化方法吧

還有一點就是下面馬上就該講線性回歸，感知機，決策樹什麼的了，我一直沒有什麼好點子該怎麼把這部分寫出來，我的想法是不推導和寫公式，直接擼代碼，如果看到這篇文的人能夠給出建議就好了。

封面：電影《幽靈公主》

1.最小二乘

最小二乘法也是我最近看一個論文的實現才注意的方法，之前很多人說線性最小二乘怎麼怎麼不好，但在我自己測試了隨機梯度下降和線性最小二乘的效果之後，發現線性最小二乘的效果竟然比梯度下降好。現在numpy等科學計算庫這麼多，求個逆求個點積分分鐘的事，在線性優化問題上，最小二乘法還是一個值得有限考慮的選擇。

考慮線性優化問題如下：

obj(eta^{T}) = frac{1}{n}sum_{i=1}^{n}{(eta^{T}x_{i}-y_{i})^{2}}

然後我們把問題矩陣化，可以寫成這樣的形式：

obj(eta^{T})=||eta^{T}X-Y||^{2}

這裡X是所有列向量x組成的矩陣，我們需要求得線性函數obj的最值，而我們知道當函數對參數beta的導數為0時，函數取得最值，因此只要求obj(eta)=0 時beta的值即可。

即求：

2（eta^TX-Y）X^{T}=0

至於這個式子怎麼求導來的，下次我想寫一寫矩陣求導的法則來好好整理一下。

當XX^T是一個可逆矩陣時，就可以解出來啦：

eta^{T}=YX^{T}(XX^{T})^{-1}

當然如果XXT是不可逆的怎麼辦？那麼可以通過增加正則項的方法，讓XX_t變成滿秩矩陣的方法來解決。

2. 梯度下降

梯度下降法可以說是最常用的優化方法了，它可以解決線性或非線性優化問題，亦可以解決凸優化或非凸優化問題，梯度下降法還有很多變種包括隨機梯度下降，牛頓法，擬牛頓法，共軛梯度下降。

2.1 梯度下降

相同的優化問題：

obj(eta^{T}) = frac{1}{n}sum_{i=1}^{n}{(eta^{T}x_{i}-y_{i})^{2}}

對於該目標函數，我們採用一種迭代的思路一步一步走，最終到達一個極值點，然後求得使其最小或者最大的參數，像這樣

額

那麼我們去過要走到那個想要去的地方，就得知道往哪裡走和走多少，這時想起我們在高數中學到的梯度的概念：

梯度的本意是一個向量（矢量），表示某一函數在該點處的方嚮導數沿著該方向取得最大值，即函數在該點處沿著該方向（此梯度的方向）變化最快，變化率最大（為該梯度的模）。

那麼我們只要每一步都沿著梯度方向走，就可以走到我們想要去的那個點。

梯度的計算方法說白了就是求偏導：

grad(obj(eta^T))=2(eta^TX-Y)X^T

然後我們設置一個步長alpha，也就是在這個梯度方向上每一步我們走多少，然後我們就有了迭代公式：

eta^Tleftarroweta^T+alpha*grad(obj(eta^T))

在幾何上導數就是斜率嘛，這樣一直迭代到低谷的時候，斜率就靠近0了，所以最後參數是可以收斂到一個值的。

2.2 隨機梯度下降

和梯度下降不同的地方是，梯度下降每次迭代要計算所有樣本的平均梯度，而隨機梯度下降，每次只算一個樣本的梯度，這樣就會變得很快，因為我們假設樣本是獨立同分布的，所以這樣還可以避免冗餘的梯度計算。

grad(obj(eta^T))=2(eta^Tx_{i}-y_i)x_{i}^T

其中x_i是每次隨機選一個樣本，這樣實際上可能所有的樣本就用不完就迭代完了。

2.3 共軛梯度下降

共軛梯度法的思想就是找到n個兩兩共軛的共軛方向，每次沿著一個方向優化得到該方向上的極小值，後面再沿其它方向求極小值的時候，不會影響前面已經得到的沿哪些方向上的極小值，所以理論上對n個方向都求出極小值就得到了n維問題的極小值。

它要求新的搜索方向與前面所有的搜索方向是共軛的……共軛是啥

兩向量間的一種特殊關係.設A為n×n對稱正定矩陣，向量p1，p2∈R.若滿足條件p1Ap2=0，則稱p1和p2關於A是共軛方向，或稱p1和p2關於A共軛.

我們的obj(beta_T)可以把二範數展開變成，最後兩項是常數：

eta^TXX^Teta-2YX^T-YY^T

然後對於參數beta，y可以由XXT的n個共軛向量表示，其中di是XX_T的基，ai是係數：

eta=sum_{i=1}^na_id_i

然後目標函數可以展開為:

min_{a_1,...,a_nin R^n}frac{1}{2}sum_{i=1}^n(a_i^2d_i^TXX^Td_i)

然後我們分別優化a_i，最後再通過上面的表達式把beta加出來。

3. 牛頓法

3.1 原始牛頓法

牛頓法據說是牛頓提出的優化方法，和梯度下降一樣也是一種迭代優化方法，但是比梯度下降要快很多，因為它是一種使用二階導數的方法，以前一直搞不懂二階在哪裡，現在才剛剛看懂。

牛頓法迭代思路在於使用泰勒展開，假設我們要求 f(x)=0 ，我們可以通過一階泰勒展開在附近選擇一個點x_0使得：

f(x)=f(x_0)+(x-x_0)f(x_0)=0

這裡一階導數就是：

2(eta^TX-Y)X^T

雖然一階泰勒展開只是一個粗略的擬合，但是求得的x一定比x_0所在的點更接近於0，然後下一步我們繼續這樣做，最終就能迭代收斂。

讓我困惑的是這個方法哪裡用到二階導數了，然後才反應過來是這樣的道理。

我們要求的是函數的最值，最值就是導數等於零的點，求讓導數等於零的點就要對導數進行一階泰勒展開，也就有了二階導數。

f(x)=f(x_0)+(x-x_0)f(x_0)=0

這樣就可以迭代求出參數了。

3.2 擬牛頓法

很麻煩的一個東西是二階導數是對偏導的偏導，在特徵特徵維度很高的時候這個方法根本沒法用，這個二階導數會是個m*m的矩陣，因為最後化簡形式是一階導除以二階導，所以我們要求這個大矩陣的逆，非常麻煩。這個大矩陣其中的某個元素是：

H_{i,j}=frac{partial^2 (obj(eta^T))}{partialeta^T_1 partialeta^T_2}

其實這個求出來就是XX_T (小聲逼逼

然後擬牛頓法就是用一個正定矩陣去代替這個海森矩陣H的逆，具體這個正定矩陣怎麼求，有兩個方法DFP演算法和BFGS演算法，有興趣可以去查一查。


推薦閱讀：
查看原文 >>
相关文章