方法之間呢,其實如果你很熟悉整個Machine Learning的原則的話,不同的方法之間,它們其實是非常像的,所以其實就算你沒有辦法把所有方法都學過,其實也是一法通萬法通,就Machine Learning的方法其實非常非常多的,我覺得你其實並不需要很積極盈盈的把所有的方法都覺得你應該要學過一遍,掌握幾個大原則,其實你就可以了解大部分的方法。

Support Vector Machine是什麼呢?Support Vector Machine呢,它有兩個特色,第一個呢,是它用了Hinged Loss,等一下我們會講Hinged Loss是什麼,另外一個呢,是我覺得它最厲害的地方,它有一個Kernel Tree,把Hinged Loss加上Kernel Tree,就是Support Vector Machine,就是SVM。

我們現在講一下Hinged Loss是什麼,回到我們在開學的時候講過的Binary Classification的問題,我們講過說在理想上Binary Classification應該要怎麼做呢?在理想上我們期待說,我們知道說一個Machine Learning的Solution,它往往就有三個Step,在Binary的Classification裡面,第一個Step是,我們想要第一個Function,G of S。

這個G of S呢,它裡面有另外一個Function,F of S,當F of S大於0的時候,它的Output就是正1,代表某一個Class,當F of S小於0的時候,它的Output就是負1,代表另外一個Class。

那我們現在的Training Data呢,我們是Supervisor Buffer,所以每一筆Data都有一個Label,White Hat,我們現在假設White Hat就用正1和負1來表示,分別代表兩個不同的Class,而之前在講Logistic Regression的時候,我知道說我們在講White Hat的時候,我們是用1跟0表示,那這邊要用正1和負1來表示比較順。

那你知道說用正1和負1來表示,用1跟0來表示是講一件事情,講的是同一件事情,就只是朝三暮四的差別而已。

但是這邊如果用正1和負1的話,等一下在寫式子的時候是會比較順,所以這邊用正1和負1,只要記得它的差別就好。

那Loss Function呢,理想上,一個最理想的Loss Function,就是寫成像下面這個樣子。

當今天呢,這個G of X的Output跟White Hat不一樣的時候,Machine就得到一個Loss1,如果一樣的時候就沒有Loss。

所以一個很理想的Loss Function是Summation over我們今天所有的Training Data,然後呢,對每一筆Training Data都代進G of X裡面看它的Output是多少,它可能Output正1也可能Output負1。

接下來看它的Output跟White Hat是一樣的還是不一樣,如果是不一樣的,你就得到一個Loss1,反之呢就是0。

我這邊用Delta加一個括號的意思就是,裡面這件事情如果為真的話,Delta這個Function的Output就是1。

所以如果G不等於Y,那Delta的Output就是1。

所以我們現在的Loss就變成,G在Training Set上總共犯了幾次錯誤,那我們當然希望它犯的錯誤是越小越好。

但是在今天這個Task裡面,你要做Optimization,你要用第三步找一個好的Function,這件事情變得有點困難,因為你的Loss是不可為分的。

這個東西是沒有辦法為分的,所以你根本沒有辦法用Gradient Descent來解它。

怎麼辦呢?我們把這個Delta用另外一個Approximate的Loss來表示,直接Minimize這個Delta做不到。

所以我們不直接Minimize這個Delta,我們Minimize另外一個Loss Function,我這邊寫成小寫的L。

那至於這個Loss Function可以長什麼樣子,你就可以自己隨便定了。

這是我們的G,它裡面有一個F of X,這個橫軸啊,這個圖上的橫軸啊,是Ym hat乘上F of X。

那我們會希望說,因為這個Ym hat可以是正一,也可能是負一。

那麼希望如果Ym hat是正一的時候,F of X要越positive越好。

Ym hat如果是正一的話,F of X要越大越好。Ym hat如果是負一的時候,F of X應該要是越負越好。

所以整體說來,你會希望Ym hat乘上F of X兩者相乘以後,它的值越大越好。

它們要是同項,它們要是同號的,它們兩個乘起來要越大越好。

所以今天原則就是,如果我們把縱軸當作是Loss的話,原則就是越往右,Ym hat乘F of X越大,Loss就應該要越小。

那我們剛才講的理想的狀況是什麼樣子呢?我們剛才講的理想的狀況是,假設今天Ym hat跟F of X它們是反向的。

它們相乘以後,你得到的值是負數的話,那你得到的Loss就是1。

反之如果它們是同項的,你的Loss就是0。這個是理想的狀況,但這件事情是沒辦法為分的。

那我們現在做一個proximation,我們把delta用L來取代,我們把delta用L來取代。

這個縱軸就是L的值,你可以選各種各式各樣不同的function來當作L這個function。

舉例來說,你可以說我現在Loss的定法是,我希望當Ym hat等於1的時候,F of X跟1越接近越好。

Ym hat等於負1的時候,F of X跟負1越接近越好。這個是square loss。

那square loss它其實可以寫成這個樣子,square loss的這個Loss可以寫成Ym hat乘上F of X減1的平方。

為什麼呢?如果我們今天Ym hat代1的話,這個function就變成F of X減1的平方。

如果Ym hat代負1的話,這個function就變成負F of X減1的平方。

那負F of X減1的平方可以寫成,因為它在平方裡面,所以可以把負號拿掉,F of X加1的平方,也就是F of X減負1的平方。

所以當你寫這個式子的時候,你就意味著如果Ym hat等於1的時候,F of X要跟1越接近越好。

Ym hat等於負1的時候,F of X要跟負1越接近越好。

square loss的function,你把這個function畫出來,它對Ym hat乘以F of N的變化是寫成這樣子。

但是這個東西是不合理的,我們一開始在講binary classification的時候,我們就講過,你用square loss是不合理的。

從這個圖上你又可以更明確的看出它的不合理性,因為我們不希望說Ym hat跟F of N乘起來很大的時候,居然有一個很大的Loss。

另外一個是sigmoid加square loss,這邊我們sigmoid function就用一個sigma來表示。

我們希望Ym hat等於1的時候,F of Xn趨近於1等於負1的時候,F of Xn趨近於0。

這個式子可以寫成這個樣子。

為什麼呢?如果你把Y hat N代1的話,那沒有問題,很直覺的就是希望這個output跟1越接近越好。

代負1的話,變成sigma of F of sigma of負F of X減1的平方。

sigma of負F of X是什麼呢?

如果你了解這個sigmoid function的特性的話,你把裡面的值取一個負號,其實就是1減sigma of F of X。

我想這個不會想一下的話應該可以體會,減1的平方。

然後這個1可以消掉,所以就變成sigma of F of X的平方。

總之你寫這個式子的意思,就是希望F of X通過sigma function以後,如果它的答案是1,它就要接近1,如果答案是負1,它就要接近於0。

這個式子寫出來是藍色的這一條線。

我們之前有講過說,其實你在做logistic regression的時候,你不會用square loss當作你的loss,因為它的performance不好。

我們之前應該也有實地操作過,你不會用square loss,其實你會用cross entropy。

如果用cross entropy的話,在logistic regression的時候,我們其實真正用的是cross entropy。

cross entropy的意思我們其實之前講過,就是你的sigma of F of X代表了一個distribution,代表一個distribution。

你的ground truth是另外一個distribution,兩個distribution之間的cross entropy,就是你要去minimize的loss。

如果你回頭過去把square loss的function寫出來的話,你會發現,其實這個function可以寫成log一加exponential負y n hat F of X。

這邊我們就不做多餘的推導,這比較麻煩,自己回去推一下就知道了。

這個式子是不是合理的呢?它其實是合理的。你想想看,當你今天的y n hat乘上F of Xn,趨近於無窮大的時候,

當它趨近於無窮大的時候,exponential負的無窮大是0,那就變成log一加0,得到的結果是0。

所以當這一項趨近於無窮大的時候,這個sigma一加cross entropy這樣的loss function,它是綠色的這一條,它會趨近於0。

如果你今天y n hat F of X它的負很大的時候,exponential裡面會是正的很大,再加上1,它的值會很大,再取log以後,它還是無窮大。

log只能跟exponential消掉,如果exponential這裡面是無窮大的話,得到的結果還是無窮大,所以你得到的值是無窮大。

所以今天這一項是這一條線。

我在這邊我特別偷偷把它除了一個log2,你對loss function除一個constant,不會影響你最後找出來的解。

我們這邊偷偷除了一個log2,為什麼呢?因為我們要偷偷除log2以後,你可以讓它變成剛才ideal的loss的upper bound。

也就是說,我就可以claim說,我們雖然沒有辦法minimize ideal的loss,就黑色這一條線,但是我們可以去minimize它的upper bound,希望minimize upper bound就可以順便minimize這個ideal的loss function。

那我們可以比較一下這兩條曲線,你可以比較這兩條曲線,你就可以比較了解說,為什麼我們之前會選擇用cross entropy,而不是用square error來當作我們的loss function,在我們做logistic regression的時候。

可以想想看,我們今天如果我們把ylhat,所以f of x,從-2移到-1的時候,如果是square error,它的變化很小,如果是sigmoid加cross entropy,它的變化就非常大。

那所以對sigmoid的這個function來說,它在這種極端的case,在你的值非常的negative的時候,在值非常negative的時候,照理說應該要有很大的規定,你應該趕快調整你的值。

但是實際上不是如此,因為在值很大的時候,當你在這一項,ylhat乘上f of x非常negative的時候,你調整你的值,對你最後的total loss影響不大。

所以就會變成說,對這個sigmoid加square loss的case來說,就算是它調整了它negative的值,它也沒有辦法得到太多的回報,所以它就會不想要調整那些非常negative的值。

那對這個cross entropy來說,它的努力是可以得到回報的,所以它就會很樂意把原來很negative的值,把它往正的地方推。

所以我們用cross entropy的時候,在實作上,你會比square error還更容易training,所以我們在做logistic regression的時候,都是用cross entropy。

那hinged loss呢?hinged loss它是寫成一個很特別的式子,它寫成這樣,它說我們的loss function是maximum,其實我們剛才在講zero-sharp learning的時候,其實是有看到類似的function。

我們這邊寫成maximum括號0跟1減y-hat f of x,0跟1減y-hat f of x。今天如果y-hat代1,那loss function就是max0跟1減f of x。

那什麼樣的狀況下,今天我們會有一個zero的loss呢?因為這邊是max0跟1減f of x,所以這個function最小值是0。

什麼時候會是達到這個function最小值,會達到loss是0最完美的狀況呢?只要1減f of x小於0就行了。

1減f of x小於0的時候,這個loss的值就會是0,也就是說只要f of x大於1的時候,這個loss就會是0。

那如果今天y-hat等於負1的時候,這個loss function會寫成0跟1加f of x的max。

那要讓loss等於0,我們就是要讓1加f of x小於0,也就是要讓f of x小於負1。

所以今天你用pinch loss做training的時候,你想要讓Machine做到的事情,什麼時候Machine會覺得它的loss是0,它已經做到完美的case了呢?

它如果今天對一個positive的example來說,f of x大於1的時候,就是完美的case。

對一個negative example來說,它的f of x小於負1的時候,它就是一個完美的case。

它的值不用太大,你把f of x變成2,loss也不會比較小,你把f of x變成負2,loss也不會比較小。

它只要大過1跟小於負1就可以了。

如果你把hinged loss畫出來的話,它長得像是這個樣子,它是紫色的這一條線。

那你會發現說呢,在紫色的這一條線上,在這一段,只要y-hat乘上f of x大於1的時候,就已經夠好,你的loss就已經是0,再更大都沒有幫助。

但是今天如果y-hat f of xn是positive的example,是positive的,是positive還不夠好。

就是如果今天y-hat跟f of xn是同項,那machine在做classification的時候,它已經可以得到正確的答案。

根據我們剛才定出來的step1定出來的function,它已經可以得到正確的答案。

但是對hinged loss來說,這樣還不夠好。

它會說你只得到正確的答案還不夠,你要比正確的答案還要好過一段距離,這個距離就是margin。

也就是說,當你今天y-hat乘上f of x,當y-hat乘上f of x還沒有大於1的時候,你其實還是會有penalty的,促使這個machine讓y-hat乘上f of x大於1。

那你可能會問說,為什麼這邊是1呢?

你可以想想看,如果這邊是1的話,hinged loss才會是ideal loss的一個type的upper bound。

如果你用其他值的話,它可能就不是一個那麼tight的upper bound。

所以hinged loss跟我們剛才看到的cross entropy一樣,它也是一個我們ideal loss function的upper bound。

所以我們也會期待說,我們可以minimize hinged loss,然後就可能可以得到minimize ideal loss function的效果。

那如果我們比較hinged loss跟cross entropy的話,你會發現說,它們最大的不同來自於它們對待已經做得好的example的態度。

今天如果我們把y-hat乘上f of x從1挪到2,對cross entropy來說,你可以得到loss的下降。

所以cross entropy它會想要好還要更好。如果你今天已經可以把y-hat乘上f of x的值做得夠大,

cross entropy它有動機要讓它的值更大,因為這樣還可以減少loss。

但是對hinged loss來說,如果你採用的是hinged loss function,它是一個及格就好的loss function。

所以今天只要你的值大過你的margin的時候,就結束了。

OK,就這樣子了,它就不會想要再做得更好。

Nathan問說,在實作上到底hinged loss跟cross entropy它們的performance有什麼樣的差別呢?

在實作上的差別可能沒有你想像的那麼顯著。

有一些時候我們會看到hinged loss可以略勝cross entropy,但其實也沒有贏那麼多。

那你採用hinged loss的時候有一個好處是它比較不害怕outlier,

比較不害怕outlier,那你認出來的結果會是比較robust的。

那這個等一下我們在講kernel的時候會比較明顯的看到這個結果。

那如果你看這個hinged loss跟cross entropy的差別的話,這個cross entropy就好像是說,

你現在期末可能有很多科目要讀,但是你就只想要拼死讀一科而已,

你想要把某一科考到100分,其他如果你唸不起來了,你就會放棄,

因為你最後可能就被惡意了。

那hinged loss它會顧全所有的科目,它所有的科目都考到及格就好了,

所以它其實是會有歐趴的。

所以如果今天你有outlier的時候,hinged loss會給你比較好的結果,

cross entropy會給你比較差的結果。

等一下我們在別的角度來看這個問題的時候可能是會更清楚的。

好,那現在什麼是linear的SVM?

linear的SVM是說我們現在的function就是linear,

我們現在的f of x就是feature x裡面的每一個feature xi乘上它的對應的位wi,

summation起來再加上b。

那我們可以把這件事情看作是兩個vector的inner product,

其中一個vector是model的parameter w跟bconcatenate起來的一個vector,

另外一個vector是feature的vector,x這個x的feature的vector跟econcatenate起來的結果。

如果你把這兩個vector做inner product的話,那你就會得到左邊這個式子。

所以在等一下以下的說明裡面,我們把w跟b串起來的那個vector,

直接就用w來表示,

這個東西是你的model的參數,是要透過training data把它找出來的。

下面的x跟econcatenate起來的結果,我們就當作是一個新的feature,

你就想像每一個feature下面都有concatenate的e,

這樣你就可以把bias這一項省略掉。

所以一個function,你就寫成w的transpose乘上x,

或w跟x的inner product。

那在SVM裡面,你的這個f長這個樣子,

然後你就說f大於0的時候是屬於某一個class,

f小於0的時候是另外一個class。

那如果是loss function呢?如果是loss function的話,

在SVM裡面,它的特色就是它採用了hinge loss這個loss function。

那通常呢,你還會加上一個這個regularization的term。

那這個loss function呢,它是一個convex的function。

為什麼呢?因為我們知道hinge loss的loss function,

它長得是這個樣子,就像IOU的那個activation function的形狀。

所以它是一個convex的function。

而這項L2的regularization,它也是一個convex的function。

所以你所有的loss都是convex的function,

regularization也是convex的function。

當你把這些convex的function疊加起來以後會發生什麼事情呢?

其實你可以很輕易的證明說,

把convex function疊加起來仍然是convex function。

所以你今天的loss function其實就是一個convex的function。

好,如果是convex的function的話呢,

你做歸根descend就很簡單了,

你不管從哪個地方做initialization,

你最後找出來的結果呢,都會是一樣。

那你可能會問說,這個東西它在某些點不可為啊,對不對?

它有這種稜稜角角的東西,

它有這種稜稜角角的東西,

你這個hinged loss,它在某些點是不可為的,

那你把很多這些不可為的convex的function疊起來,

它就長這樣,它還有很多稜稜角角的地方,

感覺不是每個位置都不可為,

都都是可為的。

但是這個不是什麼大問題,

這個其實可以做的,

你想想看,我們之前在講deep learning的時候,

你有IOU的exclamation function,你有mixed out network,

它們表面上看起來也是不可為的,

但是其實呢,你都是可以用歸根descend去做optimization,

所以今天這個case也一樣,

我們可以用歸根descend去做optimization,

那等一下我們會看看呢,

怎麼做這件事情。

好,其實呢,如果我們比較logistic regression跟linear SVM的差別,

它唯一的差別是什麼?

它唯一的差別就只是我們怎麼定loss function,

你用Hinged loss就是linear SVM,

你用Cross entropy loss就是logistic regression,

而這個function,它沒有必要一定要是linear,

只是它如果是linear的話,有很多好的特質,

但是如果它不是linear的,也ok,

你也可以用歸根descend來check,

所以SVM是可以有deep的版本的,

我這邊列一個reference給大家參考,

當你今天在做deep learning的時候,

你不是用Cross entropy當作你的minimization的對象,

當作你的loss function,而是改用Hinged loss的話,

你其實就是有一個deep版本的SVM,

所以你其實沒有必要說什麼,

我做的是deep learning,我做的是SVM,

它們其實就是可以是一樣的東西,

背後的精神其實都是可以相通的,

再來的問題就是,

怎麼用歸根descend來learn SVM呢?

我知道你傳統上聽到的方法都不是用歸根descend來learnSVM,

但SVM確實是可以用歸根descend來做training的,

有一個用歸根descend來train SVM的方法叫做Picasso,

我這邊忘了附reference,我之後再附上去,

總之SVM是可以用歸根descend train,

怎麼train呢?

我們現在的loss function長這個樣子,

然後它是一個Hinged loss,

然後歸根descend就很簡單,

你只要能夠對它做微分就好了,

我們只要能夠對我們的model裡面的某一個位Wi,

對這個summation裡面的某一個loss可以做偏微分,

我們就可以做歸根descend,

這個偏微分的值是什麼呢?

Wi只跟f of x有關,

所以我們可以把這一下拆成partial f分之partial loss function,

我們先用f對loss function做偏微分,

再乘上用w對f做偏微分,

用w對f做偏微分的結果是很簡單的,

因為我們知道f of xn就是一個linear的function,

它是兩個vector的inner product,

所以如果你用Wi對f做偏微分的話,

那你得到的其實就是xn的第一個dimension的value,

那前面這個用f對loss function做偏微分,

它的解釋是怎樣呢?

這個f它就是這個Hinged loss的loss function,

這個Hinged loss的loss function,

它長的是ilu這個樣子,

它有兩個operation的region,

它可以是operate在0是max的case,

它可以是operate在1減y乘上f of x是max的case,

如果它operate在0是max的case,

就是這個region,

它operate在1減y f of x是max的case,

它就是這個region,

那什麼時候會operate在哪一個case呢?

這個是depend on你現在的model w是多少,

也就是說假如你現在的1減y f of x,

1減y hat f of x大於0,

這個f of x的值取決於你現在的model w,

取決於你現在w的值是多少,

假設這個東西大於0,

那就是y hat乘上f of x小於1這樣,

當y hat乘上f of x小於1的時候,

你的model作用在這個region,

作用在這個region,

把它對f做為分,

你得到的值就是-y hat,

那在另外一個case,

因為就是值就是0,

所以做為分以後還是0這樣,

所以今天的為分值就有兩個可能,

如果今天是作用在這個region,

就得到這個為分值,

作用在這個region就得到這個為分值,

所以為分的值,

你把這一整項大L對w偏為分以後,

你得到的值就是這個樣子,

summation over all the training data,

再看每一筆training data的y hat乘上f of x是不是小於1,

如果是的話,

這一項delta值就是1,

那它這個1就會乘上y hat,

就是乘上負的y hat,

而這前面還會乘上一項這個,

我寫錯了,

這邊應該有一個上標n,

這邊這一項應該就是x上標n下標i,

x上標n下標i,

前面這一項,

dependent現在的參數是什麼,

所以我們就把它寫成cn of w,

所以你要update參數的時候,

你就把wi減掉learning rate,

乘上cn of w,

乘上你的第二個feature裡面的di為,

你就可以update你的參數wi,

所以就這樣,

所以SVM是可以用歸電descent來解的,

所以如果你只是要寫linear的SVM的話,

其實你用keras就可以秒做,

你可能會說,

這跟我平常看到的SVM不一樣,

我知道平常看到SVM是什麼樣子,

那我們現在把我講的hinge loss的function,

變成你平常看到的SVM,

你平常看到的SVM是怎麼樣呢,

你平常看到的SVM是,

我們現在把這個hinge loss,

換成用一個notation,

εn來取代它,

然後我說εn就等於,

0,1減yn hat乘上f of xn,

上標n,

1減yn hat乘上f of xn,

跟0的max,

我現在什麼都沒有做,

我只是換了一下notation而已,

我們現在的目標就是要minimize total loss,

這一項,

我其實可以有另外一個寫法,

另外一個寫法是什麼呢,

我寫成,

你說我們要0跟1減yn hat f of x裡面,

取大的那一個當作εn,

所以εn它會大於0,

也大於1減yn hat乘上f of x,

那我可不可以寫成,

這件事情其實就等於εn大於等於0,

εn大於等於1減yn hat乘上f of x,

假設我們不考慮這個loss,

我們先無視上面這塊,

你先無視上面這塊,

無視上面這件事,

這個紅框框,上面紅框框裡面的式子,

等於下面紅框框裡面的式子嗎,

給大家三秒鐘的時間想一下,

你覺得它相等的同學舉手,

好,手放下,

你覺得它不相等的同學舉手,

好,手放下,

好像差距沒有很大,

我們來想想看,

這個εn它是0跟1減yn hat的max,

然後我今天說εn可以大於0也可以大於它,

但是它不見得是正好等於它們的max,

它可以是它們的max加1加2加100萬,

所以如果我這樣講的話,

我們再問一下,

你覺得上面跟下面這兩個式子,

它們是一樣的嗎,

你覺得它是不一樣的同學舉手,

好,謝謝,

手放下,

其實人沒有變多這樣,

其實它們是不一樣的,

如果我們無視上面這個式子的話,

這兩個式子是不一樣的,

這兩個εn,

一個符合上面這個式子的εn,

跟符合下面這兩個框圈的εn,

是不同的εn,

它們是不同的值,

所以上面跟下面這兩個式子好像是不一樣,

但是這個只是表象上,

就假設我們不考慮這個loss function的話,

上下這兩個疑似是不一樣,

我們這邊整理一下式子,

把yn f of x移到左邊,

x0移到右邊,

所以變成yn hat乘上f of x,

大於等於1減x0n,

所以上面這兩個,

上面跟下面是不一樣,

但是今天重點就是,

你今天加了minimize loss function l這件事情以後,

上面這個式子跟下面這個式子,

就會變得是一模一樣,

為什麼呢?

因為我們現在要去minimize l of f,

所以你要選擇一個最小的εn,

讓你的l能夠最小,

雖然我們下面只有下constraint說,

εn要大於等於0,

εn要大於等於1減yn hat f of x,

理論上它不需要正好等於0,

它不需要正好等於1減yn hat f of x,

它可以是任何值這樣,

或者說舉個最簡單的例子,

εn我大概帶一兆,

帶一個無窮大,

它就符合這個constraint了,

εn隨便帶一個很大的值,

它大於0,

也大於它就符合這個constraint,

它不需要等於它們兩個之間比較大的那一個,

所以理論上這兩個東西是不相等的,

εn你是帶任何一個很大的值,

就符合下面這個constraint,

但問題是我們現在要做的事情,

是要去minimize l,

當我們要做的事情是要minimize l的時候,

我們就要選一個,

我們就要想辦法讓εn越小越好,

那當εn它的constraint是要大於等於0,

跟大於等於1減yn hat f of x,

那它最小的辦法,

就是讓εn等於它們裡面最大的這個,

所以加上我們的目標,

要minimize total loss的時候,

上面這個紅框框裡面的式子,

會跟下面這個紅框框裡面的式子是一樣的,

所以當我們把上面這個紅框框裡面的式子,

轉成下面這個紅框框裡面的式子的時候,

這個就是你所熟悉的SVM了,對不對?

你所熟悉的SVM就是告訴我們說,

這個yn hat乘上f of x,

就yn hat跟f of x要是同號的,

那它們相乘以後呢,

要大於等於一個margin1,

但是呢,這個margin是soft的,

因為soft是軟的,

有時候你沒有辦法滿足這個margin,

沒有辦法讓yn hat乘上f of x大於等於1,

那怎麼辦呢?

你把你的margin稍微做一下放寬,

把它減掉一個εn,

這個εn會放寬你的margin,

所以這個εn叫做slack variable,

slack大概是鬆弛的意思,

它可以讓你的margin變得比較鬆,

但是這個鬆弛的ε,

它絕對不能夠是負的,

因為這個負的不符合它的目的,

如果εn是負的的話,

那你就是把margin變大,

而不是把margin變小,

所以這個εn呢,

它必須要,它有一個constraint,

它必須要大於等於零,

那把這些事情合起來以後,

你會有一個你要minimize的對象,

再加上一些constraint,

那這個formulation,

它是一個quadratic programming的problem,

那你就可以帶一個quadratic programming的solver,

然後把它解出來,

那其實你不見得要帶quadratic programming的solver來解,

我們剛才看到說,

SVM其實可以用gradient descent來解。

好,我們講到這邊,

我們先休息十分鐘,

等一下再繼續講,謝謝。

字幕由Amara.org社區提供

好,我把滑鼠叫出來。

好,這個是這樣子的,

kernel map,你隨便google就有一大堆的東西,

那在這一整套東西裡面,

我認為最重要的一個,

大家容易卡住的地方就是,

要先說服你一下這件事情,

要說服你說,

實際上啊,我們找出來的weight,

我們實際上找出來,

可以minimize loss function的那個weight,

我們寫作W hat,

它其實呢,

是我們的data的linear combination,

這個W star,

其實是summation over,

所有的training data的vector point xn,

然後呢,

對所有的xn都乘以上一個weight,

alpha上標star,下標n,

也就是說,

你找出來的model,

其實就是你的data point的linear combination,

一般說服你,

這件事情的方法呢,

都是做這個,

用Lagrange multiplier,

解一下剛才的那個式子,

然後說服你這件事情,

我這邊試著從另外一個角度來說服你,

我們剛才說,

我們可以用gradient descent,

來minimize SVM,

所以當我們算出來說,

gradient descent的式子呢,

就是長這個樣子,

那這個是對Wi update的時候的式子,

那對W1到Wk,

假設現在W有k位update的式子呢,

都是一樣的,

唯一不一樣的地方,

只是你會換這個,

最後乘上去的這個value,

在update第一位的時候,

你乘上去的value,

就是xn的第一位,

在update第二位的時候,

你乘上去的value,

就是xn的第二位,

在update第三位的時候,

你乘上去的value,

就是xn的第四位,

那把他們全部合起來,

把這邊W1到Wk串成一個vector,

這邊x1上標n,

到xk上標n也串成一個vector,

那你得到的結果就是,

每次你updateW的時候,

你都是把W減掉eta,

乘上summation over xn,

乘上一個weight,

這意味著什麼,

這意味著假設,

我們initialize的時候,

你的W是一個zero vector,

那你每次在updateW的時候,

你都是加上一個data point,

linear combination,

所以最後得到的solution,

你解出來的W,

your gradient descent解出來的W,

得到的結果呢,

就是W的linear combination,

那這個cn of W是什麼呢,

這個cn of W是F對loss function的偏微分,

那我們剛才講說,

如果我們今天用的是hinged loss,

如果我們是用的是hinged loss的話,

hinged loss像ilu,

它有兩個operation的region,

如果它作用在max等於零的那個region的話,

那它的這一項就會是零,

所以當你在用hinged loss的時候,

你用hinged loss的時候呢,

你的這一項呢,

往往都是零,

也就是不是所有的xn都會被拿來加到W裡面去,

所以你最後解出來的W star,

它的這個linear combination的weight可能會是sparse,

所謂linear combination的weight是sparse的意思是說,

可能有很多的data point,

它對應的alpha star值等於零,

而那些值不等於零,

它的alpha star不等於零的那些xn呢,

它就是support vector,

如果你alpha等於零,

那你就一點作用都沒有,

你對這個model呢,

完全沒有影響力,

你要alpha呢,

是non-zero的,

那你才會決定說你最後的model呢,

你最後的parameter呢,

長什麼樣子,

而這些可以決定這個parameter長什麼樣子的data point,

它們就叫做support vector,

所以叫做support vector machine,

那今天在data point裡面,

不是所有的點都會被選作support vector,

其實只有少數的點,

少數的data point會被選作support vector,

所以SVM相較於其他方法,

它可能是比較robust的,

你今天呢,

你今天如果你的loss function,

選的是cross entropy,

你在做logistic regression選的是cross entropy,

它就沒有sparse的這個特性,

因為如果你看cross entropy的那個loss function,

它在每一個地方為分都是不等於零的,

它沒有為分等於零的地方,

為分都是不等於零的,

所以你今天你解出來的這個alpha呢,

它就不會是sparse,

如果你用hinged loss,

你解出來的alpha就會是sparse,

解出來alpha,

sparse的意思就是說,

今天那些不是support vector的data point,

你把它從data base裡面remove掉,

它對你的最後的結果是一點影響都沒有的,

如果今天有一個奇怪的outlier,

你只要不要把它選做support vector,

它對你最後串出來的model,

就不會有任何影響,

而不像是其他的方法,

如果你是用logistic regression,

每一個data都count,

每一個data,

每一筆data對你最後的結果都會造成影響。

好,那今天我們把w寫成是data point的linear combination,

最大的好處就是我們可以使用等一下說的kernel的trick,

這個想法是這樣,

我們已經知道說w就是data point的linear combination,

那我們可以把,

本來我們w可以寫成這樣,

這個w我們可以把它寫成說,

我們把所有的data point S1到S大n排起來,

排成一個matrix S,

然後α就是一個vector,

它裡面的值是α1,α2到αN,

我們把這個matrix乘上這個vector,

你就會得到Xn,

X的這個column的linear combination,

也就是matrix S乘上vector α,

所以w可以寫成matrix S乘上vector α。

當我們知道這件事情以後,

當我們知道w可以這麼寫以後,

我們可以做什麼事情呢?

我們可以改一下我們的function的樣子,

我們本來的function是寫成w的transpose乘上X,

現在我們已經知道w就是X乘上α,

所以f of X就是α的transpose乘上X的transpose乘上X。

那這一項看起來像什麼樣子呢?

X是一個vector,

X的transpose是一堆row疊在一起,

α是一個倒下來的vector,

αtranspose是一個倒下來的vector,

你把這個vector乘上這個matrix,

再乘上這個vector,

你得到的是一個scalar。

我們把這個vector X,

把這個vector X乘上這個X的transpose以後,

你得到的是一個vector,

得到的結果是什麼呢?

你得到的結果是第一個dimension,

就是X1跟X的inner product,

第二個dimension就是X2跟X的inner product,

最後一個dimension就是Xn跟X的inner product。

接下來你把這個vector跟這個vector,

再做inner product以後,

你得到的結果就是,

你的f of X等於呢?

Summation over αn乘上Xn跟X的inner product,

就是f of X怎麼算?

把X代進來,

它跟每一個Xn database裡面的每一個Xn,

都乘上inner product以後,

再把inner product的結果,

用αn做weighted sum,

就是你的f of X。

那你可能會擔心說,

哇,那個database裡面每一個Xn,

算那個,

算一遍inner product,

會不會很費事呢?

其實還好,

因為假如你是用hinged loss,

這個α是sparse的,

所以你只需要考慮那些α不等於0的vector就好了。

好,那再等一下呢,

我們會把Xn跟X做inner product這件事情,

寫成一個function,

我們寫一個function,

K of Xn跟X,

K of Xn跟X,

就是Xn跟X的inner product,

這個function呢,

叫做kernel function。

好,那我們今天已經知道step 1,

就是寫成,

把Xn跟X代進kernel function,

再乘上αn再summation以後的結果。

那在step 2跟step 3呢,

我們今天要maximize的對象變成什麼呢?

我們的model是寫成這個樣子,

不知道的東西,

其實變成是αn,

inner product裡面沒有參數,

你本來就知道了,

ok,inner product你本來就知道了,

你不知道的東西呢,

是αn。

那我們在step 2跟step 3的時候,

我們的問題就變成,

你要找一組最好的αn,

你要找一組最好的αn,

它可以讓我們的total loss最小。

這個最好的αn,

它可以長什麼樣子呢?

這個東西長什麼樣子呢?

我們叫我們loss function,

就寫成summation over所有的每筆data的,

這個小l的loss function。

而小l的loss function,

它吃兩個input,

一個是f of Xn,

一個是y hat of n。

f of Xn,

就是step 1的這個function。

你可以把這個function帶進來,

它寫起來就是這個樣子,ok?

所以f of Xn,

就是下面這一項。

summation over n前面已經用過了,

所以我們這邊呢,

summation over n',

但是都是summation over所有的training data。

那觀察這個投影片上所有的式子,

你會發現說現在,

我們不再需要真的知道說,

一個,

我們不需要知道x的vector是多少,

對不對?

我們真正需要知道的,

其實只有x跟另外一個vector z,

它們之間的inner product的值。

或者是我們只需要知道這個kernel function,

我們就可以做所有的optimization。

我們今天只需要知道,

k of xn'跟xn的value是什麼,

我只需要知道k of xn跟x的value是什麼,

我並不需要真的去知道,

xn跟xn的vector長什麼樣子,

我只要能夠算得出這一項,

我只要能夠算得出這一項,

其實就結束了,

其實就結束了。

這個呢,等一下看到這一招可以給我們帶來一些好處,

這一招呢就叫做kernel trick。

那其實這個kernel trick不是只能用在SVM裡面,

如果你回過頭去看說,

這個w等於β的linear combination這件事情,

其實不是只有SVM適用,

像logistic regression,

你也可以用同樣的方法,

所以你也可以有kernel-based logistic regression。

linear regression,

你也可以用同樣的方法,

所以你也可以有kernel-based regression。

這些都是可以的,

只是這些都不限在SVM上面。

好,那這個kernel trick怎麼用呢?

這個kernel trick是這樣,

假設我們現在,

我們把,

我們之前有說過說,

如果是linear model,

它有很多的限制,

你可能要對你input的feature,

做一個feature transform,

它才能用linear model來處理。

如果在neural network裡面,

我們就用好幾個hidden layer,

來做feature transform。

那現在呢,

假設我們有一筆data,

它是二維的x1,x2,

那我們想要對它做,

先做feature transform,

在feature transform上面,

再去apply linear SVM,

在feature transform以後,

再去apply linear model。

那我們假設feature transform以後的結果是,

我們把final x變成x1的平方,

跟後面的x1,x2,

跟x2的平方,

也是我們想要考慮,

feature和feature之間,

x1和x2之間的這個,

他們之間的關係。

那如果我要算kernel xz的時候,

我想要算,

x跟z的kernel function,

也就是x跟z,

他們的做完transition form以後,

做inner product的值的話,

我可以怎麼做呢?

我現在的方法當然就是,

我把x跟z,

都帶到這個feature transform的function裡面,

把它們變成新的feature,

變成新的feature以後,

我們就可以直接做inner product,

那算出來的結果呢,就是這樣。

這個是國中生都會算的東西。

那我們可以把這一項呢,

做一下轉化,

所以這一項,

它是x1平方,

z1平方,

加兩倍x1,x2,z1,z2,

它可以被簡化成,

x1,z1加x2,z2的平方。

x1,z1加x2,z2的平方是什麼?

x1,z1,x2,z2,

正好就是x1,x2

跟z1,z2,

這兩個vector的inner product。

所以說,

我們把x跟z,

投影到另外,

做feature transform,

再做inner product,

等同於他們在原來feature transform之前,

的space上面,

先做inner product以後,

再平方。

那,這招有時候

可以給予我們帶來好處,

因為有時候,直接

計算這個結果,

直接計算x跟z,

代進kernel function以後的output,

會比先做feature transform,

再做inner product,還要更快速。

舉例來說,

假設我們現在要做的事情,

是我的x跟z

都不是兩維,而是高維,

我們想要把它

投影到一個更高維的平面,

這更高維的平面裡面,

我們會考慮所有feature,

兩兩之間的關係。

假設你現在原來有黑維,

在更高維的平面,

至少是ch2維,

我們要考慮所有feature之間,

兩兩的關係。

所以,final max,

就是x1平方到xk平方,

跟號2,x1,x2,跟號2,

x1,x3,跟號2,x2,x3,

這樣子那一堆。

那如果你用kernel trick的話,

你可以輕易地把

final x跟final z的inner product

的結果呢,輕易地算出來。

輕易地算出來。

怎麼算呢?其實final x

跟final z的inner product

就是x跟z的inner product

的平方。你直接

把x跟z做inner product

在平方,你只需要算

k個element的相乘,

再做一次平方就好。

但是,你如果先把它project到

high dimension,再做inner product的話,

在high dimension,這個dimension

很大,這個dimension

是ch2維,如果今天的feature

dimension越大,k值越大的話,

這個feature就越長。

所以,你先做完feature transform

再做inner product,是會比你先

做inner product再取平方,還要

運算量要大,所以這個是比較快的。

而這個平方,可以

拆成x1 z1

加x2 z2,加到xk zk的

平方。那,這個平方你把它

展開的話,裡面有24項

x1 z1的平方,x2 z2的平方

等等,那會有兩兩相乘的

兩倍的x1 x2 z1 z2

兩倍的x1 x3 z1 z3

兩倍的x2 x3

兩倍的x2 x4等等。

那,你把x呢

集中到一邊,就可以得到

這個vector。你把z集中到

另外一邊,就得到

z做完feature transform後的結果。

所以,這一項呢

就會等價於

先做feature transform,再做inner product。

那還有一些更驚人的結果,比如說

你可以說,我做

kernel basis的,我把那個

這個

我做RBF kernel

做RBF kernel的意思是說

我們現在啊,我們說

k log x z

就等於呢

x跟z的

距離乘上

負二分之一,再取

exponential。

那,你知道這個東西呢,就是在衡量

x跟z之間的相似度。

如果x跟z越像

這個kernel的值呢

就越大。

如果x等於z的話呢,值就是1。

如果跟x跟z完全不一樣的話

他們的值呢

就是0。

那這個式子啊

這個式子啊,exponential x-z

的距離再乘以

負二分之一,其實也可以化成

兩個high dimensional vector

做inner product

以後的結果。

而這兩個vector啊

他們其實他們的dimension

是有無窮多維的。

所以,本來如果你要把一個

x呢,project到

無窮多維再做inner product,你做不到。

因為無窮多維是什麼樣子,你根本不知道。

但是,如果你直接算

x跟z的距離,然後再乘

二分之一再取exponential

就等同於是在一個無窮多維的

空間裡面,去做inner product。

這個無窮多維的空間

長什麼樣子呢?

你看,我們可以把這個exponential

負二分之一x-z的

tunone展開,變成

exponential負二分之一

x-z的none,

加上x跟z的

inner product。

好,接下來呢,把x的none跟z的none

這兩項呢,提出來,剩下exponential

x跟z的inner product。

那我們把

x的none這一項,用cx

來表示它,它跟x有關。

這一項呢,用cz來表示

它跟z有關,剩下exponential的x

乘以z。exponential的x乘以z

你可以用tiler展開

你不用對它做tiler extension,就變成

說,它等於cx乘上cz。

summation over i

等於0到無窮大,i階分之

x跟z的inner product

的i次方。

這個呢,有無窮多項,

從0次方一直summation到

無窮多次方。

如果把它展開的話,看起來就像是這樣

cxcz加上

cxczx跟z的inner product

加上cxcz二分之

x跟z的inner product的平方。

好,那如果我們今天

把這每一項都拆開的話,

你會得到什麼呢?

cx跟cz,你可以看成是

兩個vector,它們都

只有一個dimension,一個是cx,

一個是cz的inner product。

這一項,你可以看成是

把原來的x的vector

乘上cx,把z的vector

乘上cz

在做inner product

以後的結果。

這一項,x跟z

的平方,x跟z先做

inner product在平方,我們已經看過

在前面的例子已經看過,x跟z

先做inner product在平方,其實

可以拆成是兩個high dimension

的vector在

inner product的結果。

所以,x跟z的平方

等於兩個high dimension

的vector做inner product的結果。

這個high dimension的vector

它會考慮兩個

dimension之間的關係。

如果你是三次方,它就會考慮

三個dimension之間的關係。

好,那我們現在

把屬於x這邊的vector

都串起來,把它串成一個很長的vector。

串起來,串成一個很長的vector。

屬於z這邊的,也都串起來。

也都串起來。

這邊有無窮多項,所以串起來以後

x跟z,它們都有各自的

無窮長的vector,然後它們做inner product。

然後最後,你得到的

結果,就是這個

kernel所給你的結果。

kernel所給你的結果。

所以,當你使用RBF

kernel的時候,你就是在

無窮多維的平面上

去做事情。

去做事情。

不過,如果你在

無窮多維的平面上去做事情,

你可以想像說,它其實是

有可能蠻容易overfitting的。

所以,如果你用RBFkernel的時候,有時候要小心

你可能會在training data上

得到很好的performance,

但是在testing data上,得到很糟的performance。

而你也可以做

Symoy的kernel。Symoy的kernel

是說,k的

x跟z,等於

x跟z的inner product

做hyperbolic tangent。

那至於,x跟z的inner product做hyperbolic tangent

是哪兩個vector做inner product

的結果,哪兩個highlight major vector

做inner product的結果,你就自己回去用

這個tele-extension展開來看看,你就知道了。

好,

那我們之前已經說過說,

當我們的function,

我們的function,

當我要把一個x呢,

拿來做testing的時候,帶到f裡面的時候,

我其實是聚散x跟我training data

裡面所有xn的kernel

的function output,

然後再乘上αn。

如果當我們用的是Symoy的kernel的時候呢,

你就是把

所有data裡面的xn跟xn inner product

再去hyperbolic tangent,

再乘αn,再全部合起來

以後的結果。

呃,

如果我們今天用的是

Symoy的kernel,

這個f of x

你就可以想成它其實是一個

只有一個hidden layer

的neural network,

ok,你可以把它想成是只有一個hidden layer

的neural network,為什麼?

你把x拿進來,

它會跟

所有的x都做inner product

再通過hyperbolic tangent,

對每一個x

做inner product這件事情,其實就

好像是你有一個neural,

它的weight就是

某一筆data,ok?

你把x1那一筆data拿出來

當作這個neural的weight,

你把x2

那筆data拿出來當作第二個neural的weight,

一直到把第n筆data拿出來

當作這個neural的weight,

然後把它們都通過hyperbolic tangent

得到output,

ok,然後呢

你再把它全部乘上

alpha,然後呢

把它全部呢,加起來

結果我突然發現我犯了一個錯誤,

這個alpha呢,我就應該要下標

呃,上標下標都可以啦,

那前面是下標,所以後面應該

也要下標,這樣比較一致

好,

好,不好意思

好,那沒關係

那這樣子,好,我們找出這個

我們找出這些

我們找出這些alpha,把它

weight上起來

那就得到最後的f of x

所以這就是一個

neural network,只是它只有一個

hidden layer,那在這個

neural network裡面,它的每一個

neural的weight,就是某一筆data

那neural的

數目呢,neural的數目

就是看你有幾個support vector

你就有幾個neural

那,呃,既然

有了這個kernel trick以後

我們其實可以去直接

設計這個kernel function

我們根本就可以

完全不用理會

x跟z的feature長什麼樣

你只要有一個kernel function

可以把x跟z

這兩個東西帶進去

它可以給你一個value

這個value代表了x跟z

在某一個高維平面

上的vector inner product的話

你根本就不需要在意說x跟z

它們的vector長什麼樣子

什麼時候

這招會有用呢,假設你的

x是

有structure的data,比如說

它是一個sequence

如果是一個sequence的話

你其實不容易把sequence

表示成一個vector,假設

你的每一個sequence長度都還不一樣

假設你的每一個sequence長度

都還不一樣,那你就不容易

把這些不同長度的sequence

都用一個vector來

描述它,所以你根本不知道

它的x跟z長什麼樣子

你根本就不知道它的final x

應該要長什麼樣子

但是,如果我們可以

直接定它的kernel function

我們知道kernel function其實

就是

投影到高維以後的inner product

所以kernel function往往就是一個類似

similarity的東西

所以今天如果你可以定一個function

它是evaluate x跟z的similarity

就算x跟z它是

有structure的object

比如說它是tree structure

它是sequence也沒有關係

只要知道什麼算兩個sequence之間的

similarity

你知道知道什麼算兩個tree structure

similarity,你就可以

有機會把這個similarity

當作一個kernel來使用

當然你可能會很懷疑說

我胡亂定一個

similarity,它背後

有那個feature vector

可以support它嗎?

這個kernel其實是兩個vector

做inner product以後的結果

那你胡亂定一個function

它可以拆成兩個vector

inner product以後的結果嗎?

不是所有的function都可以

但是有一個叫做Merser's theory

可以告訴你說

哪些function

是可以的

所以你有辦法check

說你定出來的

kernel function

它背後有沒有兩個vector

做inner product

這件事情你是可以check的

所以在語音上

假設你現在要做分類的

對象其實是

audio的segment

audio segment

每一段聲音訊號

我們就是會用一個vector sequence

來描述它

它們的長度都不一樣

所以它vector sequence的長度可能都不一樣

比如說假設你現在做test

可能是給你一段聲音訊號

它要看說這段聲音訊號

它是個分類的問題

它要看說這段聲音訊號裡面

語者的情緒

它可能分成高興、生氣

等等的,有十類之類的

你要把它做分類

那你想要SVM

但是一段聲音訊號你沒有辦法直接用一個vector

來描述它

你可以直接定它的kernel

你就不要管它

你就不要管一段聲音訊號它變成一個fixed length

vector的時候長什麼樣

你直接定它的kernel

你直接定說定一個function

kl xz

然後說我把x是一段聲音訊號帶進去

z是另外一段新聲音訊號

帶進去的時候

這個function的output應該是什麼

你定好這個,你就可以直接

用kernel trick apply SVM

就算你不知道說

你要描述成一個vector的時候

應該是什麼樣

那這個方法

怎麼定這個kernel呢

怎麼定兩個sequence之間的kernel呢

這個我就把reference留在這邊

給大家參考

給大家參考

其實SVM還有很多

比如說SVM可以做

regression

SVM做regression就是

support vector regression

那它的精神是這樣

我可以用幾句話講一下它的精神

它的精神是說

我們原來在做regression的時候

我們會希望model的output跟target越近越好

那如果做support vector regression

它說我進到某一個距離裡面

進到它的某一個

我本來想像是某一個

漸微的距離,但我想說漸微大家不知道是什麼

所以就算了

就張聊的漸微

算了,我覺得這個太沒有關係了

就是它進入某一個距離

進入target的某一個距離裡面

它的loss就是0

那就是support vector regression

那ranking SVM呢

ranking SVM它常常被用在

當你要考慮的東西是

一個排序是一個list的時候

比如說在final quadrant裡面

不是有一個recommendation的題目嗎

它要你的output

是一個list

你可以說我把它當作是一個

regression的題目

我給每一個element

一個分數

然後按照分數由高到低做收集

但是

這樣你並沒有直接optimize你的問題

你其實可以直接考慮

這個list的ranking

如果直接考慮ranking的

SVM呢,叫做ranking SVM

或許你在你的final quadrant裡面

用得到這個東西

它另外一個東西叫

one class SVM

它是說它會希望

屬於positive的example都聚成一類

negative example呢

然後就散佈在其他地方

這個都留一些reference給大家參考就好

我們可以比較一下

deep learning跟SVM的差別

那我們說deep learning的前幾個

那個layer

你就可以看作是一個feature transform

最後一個layer

可以看作是一個linear classifier

那其實SVM做的事情

也是很類似的事情

你會它前面它先做一個

我們先apply一個kernel function

把你的feature轉到一個

high dimensional上面

然後在high dimensional上面

我們就可以applylinear classifier

只是在SVM裡面一般linear classifier

你都會用這個hinge loss

那事實上呢

SVM的kernel是

learnable

我列了一個reference給大家參考

事實上它是learnable

但是它沒有辦法

認得像這個

deep learning那麼多

你可以做的事情是

你把好幾個不同的kernel

然後你把不同的kernelcombine起來

它們中間的位置是可以認的

當你只有一個kernel的時候

好像是只有

SVM就好像是只有一個hidden layer

的learnable

當你把kernel再做linear combination的時候

它就好像是一個有

兩個layer的learnable

ok

好

這邊呢SVM的部分