Large Margin Classification

Optimization Objective

此小節(jié)主要講了SVM的cost function是怎么來(lái)的报亩。SVM(Support Vector Machine)是一種類(lèi)似于Logistic Regression的分類(lèi)算法。Andrew通過(guò)Logistic Regression的cost function來(lái)引申出了SVM的cost function，如下圖：

1.1-cost function

1.2-SVM cost function

• 首先用cost₀(θ^Tx)和cost₁(θ^Tx)替換原先的cost function
• 其次全庸，去掉1/m纷宇，因?yàn)檫@個(gè)乘數(shù)不影響最終θ的值
• 用C來(lái)代替λ甫煞，相當(dāng)于各項(xiàng)都乘以1/λ
  另外，在優(yōu)化這個(gè)cost function的時(shí)候腿宰，我們會(huì)使得中括號(hào)中的項(xiàng)為0(根據(jù)我們的cost function的圖形可以看出雁刷，優(yōu)化成功的結(jié)果就是使得cost(z)為0)覆劈，所以我們優(yōu)化的目標(biāo)就轉(zhuǎn)化為如下公式
  
  1.3-optimize objective
  
  圖中紅框圈出的就是我們的優(yōu)化目標(biāo)，其中紅色箭頭指向的是限定條件

Large Margin Intuition

這節(jié)主要講了直覺(jué)上large margin是怎么回事沛励，主要是decision bounary兩邊會(huì)有margin责语，如下圖：

2.1-large margin

Mathematics behind large margin classification

此小節(jié)主要講了SVM背后的數(shù)學(xué)原理。
首先目派，講了向量?jī)?nèi)積(vector inner product)的知識(shí)坤候，假設(shè)我們有兩個(gè)向量u和v, 那么它們的inner product就是u^Tv，從這里也可以看出向量?jī)?nèi)積是一個(gè)實(shí)數(shù)址貌，我們可以通過(guò)如下方式計(jì)算向量?jī)?nèi)積：

3.1-vector inner product

u^Tv = P · ||u|| = u1v1 + u2v2
其中P是向量v在向量u上投影的長(zhǎng)度铐拐， ||u||是向量u的長(zhǎng)度徘键，這里需要注意P是一個(gè)有符號(hào)數(shù)练对，當(dāng)其夾角>90° 且<270°時(shí)，P為負(fù)吹害。

然后螟凭，結(jié)合圖1.3我們的優(yōu)化目標(biāo)，可以看出要想滿足我們的優(yōu)化條件就會(huì)使得decision boundary有較大的margin它呀，如下圖推導(dǎo)過(guò)程：

3.2-SVM Decision Boundary

上圖中有些錯(cuò)誤：首先第二個(gè)限定條件應(yīng)該是y(i)=0; 另外螺男，右下角圖應(yīng)該是滿足條件P(i)||θ|| >= 1

從圖中可以看出為了滿足我們的優(yōu)化目標(biāo)，即θ的長(zhǎng)度越小越好纵穿，還要符合限定條件下隧，那么結(jié)論就是p越大越好，即當(dāng)y=1時(shí)谓媒，p長(zhǎng)度越大淆院，||θ||就可以使用相對(duì)較小的值來(lái)滿足p⁽ⁱ⁾·||θ|| >= 1, 這樣就會(huì)使得1/2 ||θ||²越小句惯；同樣道理y=0也是希望p的長(zhǎng)度越大越好土辩。

這里有個(gè)問(wèn)題支救，就是為啥θ向量一定是垂直于decision boundary的？另外拷淘，如果不是線性可分的各墨，那么如何使得其限定條件能滿足呢？比如在y(i)=1的情況下启涯，如果p(i)<0贬堵，這種情況就無(wú)法滿足p(i)·||θ|| >=1

第二個(gè)問(wèn)題在接下來(lái)的Kernels章節(jié)得到了回答，即如果是非線性可分的情況下结洼，我們需要引入polynomial function來(lái)使得decision bounary變?yōu)榍€的扁瓢，而在接下來(lái)的章節(jié)，我們會(huì)發(fā)現(xiàn)补君，最終使用的是新引入的feature引几，而非直接將原有的feature相乘。具體參考后面的章節(jié)挽铁。

Kernels

Kernels I

首先伟桅，Andrew引入了一個(gè)非線性問(wèn)題的示例，使用之前Linear Regression的知識(shí)叽掘，我們可以想象出需要引入polynomial function來(lái)解決此類(lèi)問(wèn)題楣铁。實(shí)際上我們可以理解為引入了新的Feature（比如將x1*x2作為一個(gè)新的feature f1），但是更扁，實(shí)際上我們是否有更好的引入新的feature的方法呢盖腕？原因之一就是使用polynomial方法的計(jì)算量會(huì)非常大，而且這個(gè)變量本身的含義也不是很清楚浓镜，因此這就是我們接下來(lái)要引入kernel的原因溃列。下圖展示了如何引入新的feature：

4.1-kernel

• 圖中我們選取了三個(gè)點(diǎn)，分別記做l⁽¹⁾,l⁽²⁾,l⁽³⁾,這三個(gè)點(diǎn)我們稱之為landmarks

• 新的feature記做f₁,f₂,f₃, 實(shí)際上是與x的相似度膛薛，所以我們使用similarity(x, l)來(lái)表示听隐，空間中兩個(gè)點(diǎn)的相似度我們改如何表示和計(jì)算呢？這里我們使用了所謂的高斯核(Gaussian Kernels)哄啄，這個(gè)函數(shù)中其中一部分就是使用歐幾里得距離來(lái)表示兩點(diǎn)之間的距離（某種程度上就是近似度）雅任，如下圖所示：
  

  4.2-歐幾里得距離

• exp表示e的多少次方，其中A為(0,1)點(diǎn)咨跌，其圖形如下：

  
  
  4.3-以e為底的指數(shù)函數(shù)

由上圖我們可得出如下的結(jié)論：

4.4-kernels and similarity

即如果兩點(diǎn)距離很大沪么，那么這個(gè)新的feature f就會(huì)接近于0，如果距離很小锌半，f就會(huì)接近于1禽车，而 ?? 可以調(diào)節(jié)這種相似度的影響大小，如果??越大，即分母越大哭当，那么分子（即距離）的變化影響就減小了猪腕，相反，如果??很小钦勘，那么分子的微小變化也會(huì)很明顯甚至?xí)环糯舐希簿褪菍?duì)距離變化越敏感，可以通過(guò)下圖從直覺(jué)上理解：

4.5-??影響

1. landmark是如何選出來(lái)的蔫磨，是隨機(jī)的么淘讥？
2. 除了Gaussian Kernel還有其它什么核函數(shù)？
   下面的章節(jié)就是解決這些問(wèn)題的堤如。

Kernels II

首先要解決的就是如何選擇landmark的問(wèn)題蒲列，如前所述，本質(zhì)上就是根據(jù)相似的點(diǎn)來(lái)進(jìn)行預(yù)測(cè)搀罢，那么我們完全可以將所有的樣本點(diǎn)作為landmark蝗岖，想象在空間中布滿了樣本點(diǎn)，然后我們看要預(yù)測(cè)的點(diǎn)離哪個(gè)樣本點(diǎn)近魄揉，我們就預(yù)測(cè)跟那個(gè)樣本的y值相同剪侮。如下圖所示：

5.1-choose landmarks

如上圖所示拭宁，假設(shè)我們有m個(gè)樣本洛退，那么就意味著我們會(huì)有m個(gè)landmark，這也意味著我們會(huì)新增m個(gè)feature（實(shí)際上如果算上f0=1的話應(yīng)該是m+1個(gè)new features)杰标，如下圖所示：

5.2-get new features

需要注意的是由于歐幾里得距離是一個(gè)標(biāo)量兵怯，因此最終組成新的f是一個(gè)m+1維的vector。另外腔剂，我們將不再直接使用x進(jìn)行預(yù)測(cè)媒区，而是使用新生成的f進(jìn)行計(jì)算并預(yù)測(cè)。

然后，我們?cè)倩剡^(guò)頭來(lái)看下之前的訓(xùn)練目標(biāo)袜漩，即min(cost function)绪爸， 如下圖所示：

5.3-new cost function

需要注意的是:

• 原先的x被替換成了f， 即θ^Tx⁽ⁱ⁾被替換成了θ^Tf⁽ⁱ⁾
• 原先的正則式sum(θ²_j)被替換成了θ^Tθ宙攻，然后可以進(jìn)一步變換為θ^TMθ(主要是為計(jì)算方便)

SVM In Practice

這一節(jié)主要講了如何在實(shí)踐中使用SVM奠货。通常，我們都會(huì)使用現(xiàn)成的軟件包來(lái)幫助我們實(shí)現(xiàn)座掘，但在這個(gè)過(guò)程中我們?nèi)匀恍枰鰞杉拢?/p>

1. 選擇C parameter

2. 選擇Kernel函數(shù)
   具體如下：

   
   
   6.1-use SVM SW package

• 一般的递惋，對(duì)于feature數(shù)量較大(n比較大），樣本數(shù)量較小時(shí)(m較小)我們采用Linear Kernels實(shí)際上等于不用任何Kernels溢陪，即不會(huì)做任何映射萍虽，你也可以認(rèn)為是x->x的映射
• 或者當(dāng)n較小，m較大時(shí)形真，我們就可以采用Gaussian kernel杉编，本質(zhì)上是增加了feature形成了更高維的函數(shù)空間。在使用Gaussian kernel的時(shí)候咆霜，我們需要選擇??

當(dāng)使用Gaussian Kernel的時(shí)候王财，我們一般也需要實(shí)現(xiàn)x->f的kernel映射函數(shù)，如下圖所示：

6.2-kernel function

• 一般的裕便，當(dāng)我們實(shí)現(xiàn)了這個(gè)Kernel函數(shù)后绒净，軟件包會(huì)自動(dòng)幫我們將x映射到多個(gè)f
• 我們需要做feature scaling，以便讓所有的feature的影響在一個(gè)量級(jí)內(nèi)偿衰。

另外挂疆，除了上述的linear kernel 和Gaussian kernel之外還有一些kernel可能會(huì)被用到，但是一般的下翎，它們都需要符合Mercer' Theorem

6.3-other kernels

對(duì)于多分類(lèi)問(wèn)題缤言，一般情況下，軟件包都已經(jīng)內(nèi)置了多分類(lèi)方法视事，可以直接調(diào)用胆萧。另一方面，如果沒(méi)有提供俐东，我們可以使用之前在Logistic regression中使用的one-vs-other方法

6.4-multi-class classification

最終跌穗，我們可以看到在解決分類(lèi)的問(wèn)題時(shí)，我們會(huì)有多種選擇虏辫，那么如何選擇這些不同的算法呢蚌吸？

6.5-choose algorithm

• 通常會(huì)根據(jù)feature的數(shù)量以及樣本的數(shù)量來(lái)做出選擇
• 神經(jīng)網(wǎng)絡(luò)適用于幾乎所有的情況，唯一的問(wèn)題是訓(xùn)練的時(shí)候會(huì)比較慢