好,那我們來看看我們之前講過了PLA跟Logistic regression,我們用的Gradient descent
Logistic regression 都可以看成是Interative Optimization的方法,也就是說我們是一步一步的讓那個w越變越好
那在PLA裏面我們做什麼事情呢,用這個圖希望大家還記得說,我們選一個點出來然後看
看這個點有沒有錯,如果它有錯的話,我們就用這個點來當作一個錯誤修正的方向
所以每一輪我只需要選一個點出來就好了,大家可以想像說每一輪這有點像是一個
constant,也就是說我只要所有那麼多個點,比如說我有一千個點也好,一萬個點也- 好,我只要看其中一個點就好
那但是Logistic Regression看起來不是做這樣的事情
什麼意思呢?例如說看Logistic Regression演算法的話,它做的事情是什麼,每一輪我要看完所有的點
把所有的點的這個對gradient貢獻統統算出來,加起來平均一下
把整個gradient算出來,算出來以後再對那個梯度的方向往下面去做
所以如果你只看每一輪花的力氣的話
Logistic Regression看起來會花顯著的比較多的力氣,會比較慢一些
那我們接下來要跟大家探討的課題就是我們 能不能讓Logistic Regression跟PLA一樣快
不然的話,Logistic Regression目前差不多跟誰一樣快,跟Pocket一樣快,因為在Pocket-
裏面我們也是 每一輪要看過n個點,看看什麼,看它Ein是多少,看看我們要不要把w
hat換掉 好,所以我們來看看,我們來看一下Logistic
Regression的演算法長什麼樣子 我們說我們要更新的式子是長這樣,就是說我們要把w加上它的反的梯度
方向,然後這個反的梯度方向是一個summation,然後有個1/N在裏面有一堆的- 值在裏面
好,那我們希望是這樣,我們的更新方向跟這個gradient要很接近
因為我們之前的推導告訴我們,至少如果η夠小的時候我的梯度是一個好的方向
但是我不希望花那個n的力氣去把梯度算出來 花n倍的力氣去把梯度算出來,所以這是我們的挑戰
好,那我要怎麼樣做到這件事情? 我們看到1/N,看到summation,一個可能的想法是把這個
東西想成一個隨機過程的平均,隨機什麼,隨機抽一個點
然後平均,所以隨機抽一個點,平均,我們就避開了這個把它加起來然後再除以N的動作,而是
我隨便抽一個,然後在期望值上來說,會跟我真正去把100個東西加起來然後做平均,很接近
好,所以這樣的道理是什麼,就像你現在有一萬個數字,然後你要加起來,你不知,不想認真的
算一萬個數字,不然你從裏面隨機的抽幾個數字來,然後把它加起來,把它做平均
這對於你的一萬個數字是好的衡量,我們今天只是做一個很extream的動作,說我只抽- 一個數字
抽一個數字以後,然後看看,它的上面 的那個值是多少,然後我們可以用這個數字來代替整個的平均
這個數字我們把它叫做 stochastic gradient
隨機的這個梯度,不是我們原來的真正的梯度 而是我把在單一個點上的error
做一個偏微分,做一個梯度,取梯度的動作 然後那這樣子的話,它,我們就可以把
整體的真正的那個梯度看成是這個隨機過程的一個期望值
好,這樣的話有什麼好處?反正來看 我們也可以把隨機的梯度當成什麼,真正的那個梯度
加上某些隨便亂走的,好像喝醉酒一樣隨便亂走的,所以我真正想要走的是
藍色的那個方向,然後但是因為我這個隨機過程,所以呢我可能稍微偏了一下,左邊偏一下,- 右邊偏一下
不過期望值來說我跟我原來要走的方向可能沒有差太多
好,所以從這個角度出發的話,我們就可以寫下另外一個演算法,叫做Stochastic
Gradient Descent,我用隨機的梯度來做下降,而不是用真實的梯度來做下降
那要怎麼做呢?我們今天就是把正式的梯度換成隨機的梯度,而就這麼簡單
那這麼簡單的justification是什麼?實際上是說如果我今天跑的夠多步
時候,真實的梯度跟隨機的梯度平均起來應該會差不多吧,這跟我們平常在做抽樣
做的事情是類似的。那如果是這樣呢,我們就賺到什麼好處?
簡單,我只要抽一個點出來算它的東西就好,不用說我有一萬個點,我要把一萬個點做平均
然後再來,既然我只要算一個點,這是比較便宜的,比較容易算出來的
那在如果你今天的資料量很大,我剛才講,一萬個點,兩萬個點,或現在大家聽到很紅的big data很多的資料的時候
這樣方式就很有用。或者什麼,或者你今天資料本來就 是一筆一筆來,我們之前說這是什麼設定,這叫on line
learning 綫上的學習,你的資料本來就是一筆一筆來的時候,這樣的方法就會可以在那樣的狀況下使用-
,也就是說你今天 的資料不再是一批一批來,而是一筆一筆來的時候,那Stochastic
Gradient Descent這樣的想法就 可能可以套到那個裏面去。好,那但是缺點是什麼?
缺點就是你如果把它跟原來的梯度下降做比較的話
你會發現,你本來要走這個方向,結果你喝醉酒了,左邊拐一步,喝醉酒了右邊拐一步
那所以你走的方向跟原來的可能不是太一樣
然後所以你的演算法在性質上會比較不穩定,特別是如果你的η太大的時候它會更不穩定
對不對,因為你今天就真的不知道踏空了一步,踏到哪裡去 到底是踏到一個比較高的地方,還是真的踏到一個比較低的地方,你就不知道
不過呢,你如果不太在乎這些負面東西,想像它的好處就是
簡單,然後計算快的話,你就可以把Logistic Regression用在SGD上面的步驟寫下來
它就長這個樣子,純粹是基於我們之前對於這個梯度的推導
它說什麼呢?我今天就把原來那些1/N summation拔掉了,所以我就有兩個項目,一個項目是
我的θ,okay對上我現在到底y乘上x的值是多少,然後再來
這個方向,y乘上x,okay,這就是我們要的更新的方向是什麼
好,我們這邊畫了一個笑臉,大家想想看你什麼地方看過這個式子
看過這個式子說,我要更新,我更新的方向好像跟
這個我的這個y乘上x有關,你說,啊我知道,老師你很早就教過了,PLA嘛
對不對,PLA我們說我們選一個點出來,看這個點有沒有錯,有錯的話,我就更新,我就往-
它的方向就更新 沒有錯的話,我就不更新,寫下式子來是怎麼樣,有錯的話
這個是1的話,我就更新,沒有錯的話,我就不更新
所以它就是用一個Boolean的evaluation再決定要不要更新
跟上面的式子對照,θ,θ是什麼,是那個S形的平滑的長相,所以我們就可以把 用SGD來做的Logistic
Regression看成是Perceptron Learning Algorithm
不過呢,做的軟一點,我不是看它有錯還是沒有錯,而是看它錯多少
錯的多一點,我就多更新一點,錯的少一點,我就少更新一點 再來呢,反著來看,我們可以把Perceptron
Learning Algorithm看成什麼呢? 如果我今天的w很大,或者w乘上x我這個score分數很大
分數很大的時候,我的θ是什麼,我的θ就不是很接近0,就是很接近1
所以當我的w乘上x,我的分數已經很大的時候,我的
Logistic Regression如果跑在SGD的話,就跟在跑PLA沒有什麼兩樣
所以PLA這樣的演算法跟SGD的Logistic Regression是非常有關係的
你會說,那實務上,好,看起來SGD 是這麼好,跟我們熟悉的PLA好像很接近,那我真的要怎麼用它呢?
我這邊要提醒大家,還有兩件你真正把這個演算法用上去的小事
一件事情是你怎麼決定你的演算法做好 回想一下,Gradient
descent我們怎麼決定演算法做好了,一個可能性是 我要看我到不到谷底了,到谷底我就要看我的梯度,我的真實的梯度是不是0
SGD能不能做這件事,不適合吧,因為就是說你要省那個
計算,你如果要省那個計算,還去check真正的gradient是不是0的話,那麼你- 剛才省就白省了
所以通常在SGD裏面要決定什麼時候停很困難
很多時候大部分人使用的都是 我就跑夠久,我就相信我應該已經到谷底了
好,這是一個相信,並不是說我跑夠久我就一定能夠到谷底 但是這是一個相信,實務上很多人都這樣做。另外一個呢則是
今天我的η,我每一步要跨多大到底要怎麼決定?
好,這是一個困難的問題,後面的章節裏面我們會講到怎麼樣把η當作一個參數來做選擇
但是現在如果你沒有頭緒說你要怎麼樣做η的話,告訴你一個 小秘密,小秘密就是你就用η等於0.1吧
如果你的x的範圍不算是太糟糕的話,經驗上0.1是一個還蠻好的範圍
不要問我這怎麼算出來的,這只是經驗上我的小秘密,當然每個人的習慣的數字不一樣,- 實際上我
自己通常的習慣不是用0.1,而是0.1126,不過0.1附近大概都還做的很好
好,那我們這邊再來給大家一個練習,說 如果我今天想要把SGD用在linear
regression上,可不可以? 當然可以啊,你今天式子已經寫出來了,然後梯度已經寫出來了,如果說
今天我有大量的資料,我沒有辦法像我本來做這個linear regression 說,我用pseudo-inverse就可以算得出來,那我想要用SGD的方式,可以-
,那請你 推導一下到底你用SGD方式的時候,你要用什麼樣的
方向來做更新。大家推導一下之後,我希望大家能夠得到正確的答案是4
這只是把我們之前寫過的跟linear regression有關的 梯度的式子寫下來,對單一的點寫下來而已
那值得注意的是這樣子,我們也是往xn的方向更新 也是往我們資料的方向更新,那更新的強度是多少呢?
今天如果錯的越多,什麼叫錯的越多,y減掉我現在的分數的這個值越大的話
我就會更新越多,這是這個方法背後還蠻有趣的一個物理意義,給大家做參考