梯度下降法分析

梯度下降法的基本思想是函數沿著其梯度方向增加最快，反之，沿著其梯度反方向減小最快。在前面的線性回歸和邏輯回歸中，都采用了梯度下降法來求解。梯度下降的迭代公式為：
\(\begin{aligned} \theta_j=\theta_j-\alpha\frac{\partial\;J(\theta)}{\partial\theta_j} \end{aligned} \)

在回歸算法的實驗中，梯度下降的步長\(\alpha\)為0.01，當時也指出了該步長是通過多次時間找到的，且換一組數據后，算法可能不收斂。為什么會出現這樣的問題呢？從梯度下降法的出發(fā)點可以看到，算法指出了行進的方向，但沒有明確要行進多遠，那么問題就來了，步子太小，走個一千一萬年都到不了終點，而步子太大，扯到蛋不說，還可能越跑越遠。

　　如上圖，藍色為一個碗形函數，其最小值在\(x=2\)那點，假如從\(x=0\)開始迭代，即是圖中點1，此時知道應該向右走，但步子太大，直接到點2 了，同樣點2處知道該往左走，結果又跑太遠到點3了，…，這樣越走越偏離我們的終點了。此情況的驗證可以直接把前面回歸算法的步長改大，比如把線性回歸迭代步長改為10，要不了幾次迭代結果就是Nan了。

這樣有一點需要說明下，同樣的步長\(\alpha\)，為何從1到2和2到3的長度不一致？因為1-6點的梯度是逐步增大的，故雖然步長相同，但移動的距離卻越來越遠，從而進入了一個惡性循環(huán)了。

解決方法　　對于上面提出的問題，解決方法有多種，下面就大致來說說，若有新的方法此處未提及，歡迎補充。

　　1.手動測試法
　　顧名思義，此方法需要手動進行多次實驗，不停調整參數，觀測實驗效果，最終來確定出一個最優(yōu)的步長。那么如何判斷實驗效果的好壞呢？一種常用的方法是觀察代價函數（對線性回歸而言）的變化趨勢，如果迭代結束后，代價函數還在不停減少，則說明步長過??；若代價函數呈現出振蕩現象，則說明步長過大。如此多次調整可得到較合理的步長值。
顯然，該方法給出的步長對于這組訓練樣本而言是相對較優(yōu)的，但換一組樣本，則需要重新實驗來調整參數了；另外，該方法可能會比較累人~~
　　2.固定步進
　　這是一個非常保險的方法，但需要舍棄較多的時間資源。既然梯度下降法只給出方向，那么我們就沿著這個方向走固定路程，即將梯度下降迭代公式修改為：
\(\begin{aligned} \theta_j=\theta_j-\alpha\;sign({\frac{\partial\;J(\theta)}{\partial\theta_j}}) \end{aligned} \)
　　其中的\(sign\)是符號函數。
　　那么\(\alpha\)取多大呢？就取可容許的最小誤差，這樣的迭代方式可以保證必然不會跨過最終點，但需要耗費更多次迭代。
　　3.步長衰減
　　步長衰減主要考慮到越接近終點，每一步越需要謹慎，故把步長減小，寧肯多走幾步也絕不踏錯一步。在吳恩達公開課中，他也提到了可在迭代中逐步減少步長。那如何減少步長？通?？梢杂羞@么幾種做法：
　　A．固定衰減。比如每次迭代后，步長衰減為前一次的某個比例（如95%）。
　　B．選擇性衰減。根據迭代狀態(tài)來確定本次是否衰減，可以根據梯度或代價函數的情況來確定。比如，若此次迭代后代價函數增加了，則說明上次迭代步長過大，需要減小步長，否則保持不變，這么做的一個缺點是需要不停計算代價函數，訓練樣本過多可能會大大增加耗時；也可以根據梯度變化情況來判斷，我們知道我們的終點是梯度為0的地方，若本次迭代后的梯度與前一次的梯度方向相反，則說明跨過了終點，需要減小步長。
　　顯然，采用步長衰減的方式，同樣也依賴于初始步長，否則可能不收斂。當然其相對于固定步長，則會更具穩(wěn)定性。
　　4.自適應步長
　　此方法思想來源與步長衰減。在每次迭代，按照下面步驟來計算步長：
　　A．設置一個較大的初始步長值
　　B．計算若以此步長移動后的梯度
　　C．判斷移動前后梯度方向是否會改變，若有改變，將步長減半，再進行A步；否則，以此步長為本次迭代的步長。

還是以上面那個圖像來說明下。首先，初始點1在\(x=0\)處，按照初始步長則應該移動到點2\(x=5\)處，可點1和2處梯度方向改變了，那邊步長減半則應該到點A\(x=2.5\)處，點1與A的梯度還是不同，那再將步長減半，則移動到點B\(x=1.25\)處，由于點1與B的梯度方向相同，則此次迭代將從1移動到B。

 　　顯然，該方法不會收到初始步長的影響，每次自動計算使得不會跨過終點的最大步長值。另一方面，從計算量上講，有可能會比原來的方式更大，畢竟有得有失，你不用自己去一次次修改參數->運行程序->觀察結果->…->修改參數。具體代碼只需對原回歸算法的代碼略做修改即可。
　　將原回歸算法迭代中的2行代碼
1         Grad = CalcGrad(TX, TY, Theta, fun);  
2         Theta = Theta + Alpha .* Grad;
　　修改為

 1         Alpha = 16 * ones(n, 1);
 2         Theta0 = Theta;
 3         Grad0 = CalcGrad(TX, TY, Theta0, fun);
 4         while(min(Alpha) > eps)  
 5             Theta1 = Theta0 + Alpha .* Grad0;
 6             Grad1 = CalcGrad(TX, TY, Theta1, fun);
 7             s = sign(Grad1 .* Grad0);
 8             if (min(s)>=0)
 9                 break;
10             end          
11            
12             s(s==-1) = 0.5;
13             s(s==0) = 1;
14             Alpha = Alpha .* s;  
15         end
16         Grad = Grad0;
17         Theta=Theta1;
View Code
　　即可實現。
補充說明
　　上面的說明是針對每一維的，對于步長需要每一維計算。若需要所有維度使用同一個步長，請先將訓練樣本歸一化，否則很可能收斂不到你想要的結果。數據分析師培訓