2014年11月4日 星期二

[Algorithm] Stochastic gradient descent(梯度下降法)作為Online Learning Model(即時訓練模型)(二)


        昨天最後我們停在Cost Function,再複習一下他的樣子:
θ為迴歸係數,要求得θ的最小值,也就是求上述Cost Function的最小值,統計上的做法就是直接將上述式子對每個係數做偏微分=0就可以計算出θ.這個方法完全沒錯,但是今天我要介紹的SGD是另外一種概念.


        如果說直接讓Cost Function微分=0來求得最小值是一種站在宏觀的做法,SGD(其實嚴格來說目前還只是Gradient Descent),是站在微觀的觀點,讓θ值根據當下的狀況(也就是對迴歸方程式最小平方和的影響),動態的調整θ的大小,來求得最小值.

        讓我們以圖形化的方式來了解這個過程.
           線性回歸方程式                                         Cost Function
                 



迴歸方程式是一次方程式,所以是一條線(如果是多元迴歸請自行想像成某個變項的切面謝謝orz)

Cost Function是計算最小平方和,是自變項的二次方程式,所以是個曲線(如果是多元迴歸就是一個高維度的山谷,我無法想像,不過就每個切面來說還是長得像山谷.)那我們今天的做法就是將問題從線性方程式轉換成求最小平方和的最佳解.要求最佳解我們用的做法就是,先隨便站在山谷上的任何一點,發現哪邊比較低,就往哪邊走(如右圖).透過多次的迭代來找到最低點,化成公式就長得像下面這樣:
       直到收斂  while{
                      }

這個公式中的:=不是一般數學上的=(equal),而是一般程式語言“ = ”的用法或是R中的<-(assign),將右邊的值指派給左邊的意思.整個公式比起數學,更像程式語言,使用一個while loop來控制程式流程,反覆迭代運算θ值來得到最佳解:
公式中左邊的θ代表了n+1次時的值,右邊的θ是第n次的值.那每次θ要加減多少就是以一個α(又稱learning rate)以及J(θ)在θ點的微分來控制.先不管α,先來看微分這件事情.一個二次方程式在不同自變項的偏微分在圖形上就代表了這一點的斜率.(見下圖,圖片來源:http://stackoverflow.com/questions/21064030/gradient-descent-in-linear-regression


θ落在最小值的右邊,斜率是正的,帶到公式中,就會減少θ值;反之,如果θ比最小值還小,那斜率是負的,帶到迭代公式中就會增加θ值.由於曲線越接近谷底越為平緩,所以當θ靠近最低點時,每次移動的距離也會越來越小,最終將收斂在最低點.

講完微分的部分,接下來是α值(learning rate).α值的用途主要在控制每次θ移動的距離,下圖顯示移動距離太大或太小的狀況:

如果一次移動太短的距離(左圖),那收斂速度會相當的慢.但是如果移動的距離太大(右圖),反而可能造成無法收斂的情形.所以會需要根據不同的狀況來調整這個α的大小,這部分也有相當多的討論和證明,就請另外參考其他相關討論.概念是這樣,接著我們將微分後的結果展開:
如果有是多元迴歸,就是根據個別的係數做偏微分,最後結果如下(如果是常數項就把最右邊那個x丟掉就好):
所以整理起來,為了要得到迴歸方程式的最佳解,我們會透過下述方式:
這邊的x和y就是一次帶入所有資料進去做運算,這邊到目前為止,我們已經將整個 Gradient Descent的推倒介紹完,但是這樣的方法在運算上會有個缺點:就是每次的迭代都必須將所有變項丟進去(又稱之為Batch Mode的演算法),會大幅增加運算的時間,所以下一篇我們將介紹一次丟一筆資料進去計算的方法,並且都過這樣的方法,讓我們的演算法從Batch Mode轉換成Online Mode,也才有可能對Streaming資料做機器學習.