九九九九吊,蜜臀99在线,久久电影亚洲

之前介紹了幾種不同的監(jiān)督學習算法以及測試集和驗證集的概念：

這篇文章介紹監(jiān)督學習中一個很強大，在學術界和工業(yè)界都很流行的算法——支持向量機（Support Vector Machine，SVM），首先大致了解一下支持向量機的思想

支持向量機簡介

支持向量機是用于分類問題的算法，支持向量機的基本思想是對于N維的數(shù)據(jù)，找到一個N-1維的超平面（hyperplane），作為數(shù)據(jù)分類的決策邊界，確定這個超平面的規(guī)則是找到離分隔超平面最近的那些點，使它們離分隔超平面的距離盡可能遠，因為這樣可以使得訓練出來的分類器更加健壯。離超平面最近的那些點就被稱為支持向量（support vector），舉個例子，對于二維的數(shù)據(jù)，支持向量機就要找到一個一維的向量來作為邊界，如圖所示：

二維數(shù)據(jù)點中的支持向量

線性支持向量機（Linear SVM）

在 Logistic 回歸中，我們根據(jù) $\theta^Tx$ 是否大于0來進行分類，并且將兩個類別分別記作1和0，這里我們則將兩個類別分別記為+1和-1，即 $y^n=1$ 或 $y^n=-1$ 。當 $f(x)=\theta^Tx$ 大于0的時候，預測為+1，并且 $f(x)$ 越大越好；當小于0的時候，預測為-1，并且 $f(x)$ 越小越好
所以其實線性支持向量機的假設函數(shù)和 Logistic回歸的假設函數(shù)是相同的，不同的只是損失函數(shù)。下面我們來看一下怎么確定線性支持向量機的損失函數(shù)。
首先我們畫出用不同函數(shù)作為損失函數(shù)時候的圖像，將橫軸記為 $y^nf(x)$ ，這樣的話，如果 $y^n=1$ ，這時候我們希望 $f(x)$ 越正越好，所以 $y^nf(x)$ 越大，損失函數(shù)越小， $f(x)$ 越小，損失函數(shù)越大；而如果 $y^n=-1$ ，這時候希望 $f(x)$ 越負越好，所以 $y^nf(x)$ 越大，說明 $f(x)$ 越負，即損失函數(shù)就越小。所以，將橫軸記為 $y^nf(x)$ 更加方便，無論是 $y^n=1$ 還是 $y^n=-1$ 的情況，損失函數(shù)都是隨著橫軸遞減的
之前我們曾經(jīng)使用過 Square Error Cost 作為損失函數(shù)，這是一個二次函數(shù)，當 $y^n=1$ 的時候，是 $(f(x)-1)^2$ ，當 $y^n=-1$ 的時候，是 $(f(x-(-1)))^2$ ，因此總的可以寫成 $(y^nf(x)-1)^2$
在 Logistic 回歸中使用的損失函數(shù)則是交叉熵（Cross-Entropy），統(tǒng)一了 $y^n=1$ 和 $y^n=-1$ 的情況后，可以寫成 $\ln(1+e^{-y^nf(x)})/\ln2$ ，其中除以了一個常數(shù)是不影響的。從下圖看一下：

Loss functions

紅色的曲線就是 Square Error Cost，顯然違背了隨著橫軸遞減的規(guī)律，因此不能采用；藍線是 Sigmoid 函數(shù)加上 Square Error Cost，雖然滿足遞減的規(guī)律，但是變化趨勢太小，損失函數(shù)的下降并不明顯，而我們知道隨著橫軸增大，損失函數(shù)應該會下降很多；而綠色的曲線就是 Logistic 回歸中使用的交叉熵，和藍線對比起來，損失函數(shù)的下降趨勢就很明顯
那么在支持向量機中，使用的是叫做 Hinge Loss 的損失函數(shù)，它的圖像就是下面的紫色的線：

Hinge Loss

具體的損失函數(shù)是：
$l(f(x^n),y^n)=max(0,1-y^nf(x^n))$
當 $y^n=1$ 時，只要 $1-f(x)<0$ 即 $f(x)>1$ ，損失函數(shù)就為0了；
當 $y^n=-1$ 時，只要 $1+f(x)<0$ 即 $f(x)<-1$ ，損失函數(shù)為0
也就是說，當 $y^nf(x)>1$ 時，損失函數(shù)就是0，就算繼續(xù)讓 $y^nf(x)$ 增大，也不會得到損失的下降；而當 $y^nf(x)$ 在0到1之間時，雖然已經(jīng)可以預測出正確的結果，但是對于 Hinge Loss 來說還不夠好，還是有一定的損失，要比正確的結果好過一段距離之后，損失函數(shù)才會降為0。相比于交叉熵，Hinge Loss 更加健壯
所以概括一下，線性支持向量機使用的假設函數(shù)就是一個線性函數(shù)（ $f(x)=\theta^Tx$ ），損失函數(shù)是 Hinge Loss 再加上一個正則化的部分，這是一個凸函數(shù)，因此我們可以使用梯度下降法來進行優(yōu)化

松弛變量（Slack Variable）

先直觀地理解一下松弛變量。支持向量機的目標是找到一個邊界以最大化邊界與支持向量的距離，但是有時有些樣本點可能不滿足間隔條件，這時引入一個松弛變量 $\epsilon^n\ge0$ ，使間隔加上松弛變量滿足間隔條件
我們來看一下 Hinge Loss 的部分，記：
$\epsilon^n=max(0,1-y^nf(x))$
由于我們的目標是最小化 Hinge Loss，因此上式等價于：
$\begin{align} \epsilon\ge1-y^nf(x) \newline\ \epsilon^n\ge0\end{align}$
變化之后： $y^nf(x)\ge1-\epsilon^n$ ，就是說間隔（margin）要大于等于1，但是這個間隔是軟間隔（soft margin），其中有一個松弛變量，就是 $\epsilon^n$
這是一個二次規(guī)劃（Quadratic Programming，QP）問題，因此可以用QP問題的算法來解。當然，不用QP算法的話用梯度下降法也是可以的

對 Hinge Loss 使用梯度下降法

忽略掉正則化的部分，線性支持向量機的損失函數(shù)就是：
$L(f)=\sum_nl(f(x^n,y^n))$
$l(f(x^n),y^n)=max(0,1-y^nf(x^n))$
如果我們的參數(shù)是 $\theta$ ，我們首先需要求出損失函數(shù)對 $\theta$ 的偏導數(shù)：
$\frac{\partial l(f(x^n,y^n))}{\partial \theta_i}=\frac{\partial l(f(x^n,y^n))}{\partial f(x^n)}\frac{\partial f(x^n)}{\partial \theta_i}$
由于 $f(x^n)=\theta^Tx^n$ ，因此 $\frac{\partial f(x^n)}{\partial \theta_i}=x_i^n$
接下來計算 $\frac{\partial l(f(x^n,y^n))}{\partial f(x^n)}$ ：
$\frac{\partial max(0,1-y^nf(x^n))}{\partial f(x^n)}= \begin{cases} -y^n, & if \ \ \ y^nf(x^n)<1 \\ 0, & otherwise \end{cases}$
因此，偏導數(shù)為：
$\frac{\partial L(f)}{\partial \theta_i}=\sum_n-\delta(y^nf(x^n)<1)y^nx_i^n$
我們把 $-\delta(y^nf(x^n)<1)y^n$ 記作 $c^n(\theta)$ ，其中 $\delta(x)$ 表示當滿足 $x$ 時， $\delta(x)$ 為1，否則為0
于是，我們就得到了在 Hinge Loss 中，梯度下降法的更新公式：
$\theta_i=\theta_i-\alpha\sum_n c^n(\theta)x_i^n$

核函數(shù)（Kernel Function）

將我們最終使用梯度下降法得到的那組最優(yōu)化的參數(shù)記作向量 $\theta^*$ ，實際上， $\theta^*$ 就是 $x^n$ 的線性組合：
$\theta^*=\sum_n a_n^*x^n$
將梯度下降法的更新公式寫成向量的形式：
$\theta=\theta-\alpha\sum_n c^n(\theta)x^n$
而前面說過 $c^n(\theta)$ 很多時候都會是等于0的，因此對應最后的參數(shù) $\theta^*=\sum_n a_n^*x^n$ ，就會有很多數(shù)據(jù)點 $x^n$ 前面對應的 $a_n^*$ 是等于0的，也叫做 $a_n^*$ 是稀疏的（sparse），而那些 $a_n^*$ 不等于0的 $x^n$ 就叫做支持向量（Support Vectors）
意思就是如果一個數(shù)據(jù)點對應的 $a_n^*$ 等于0，那么這個數(shù)據(jù)點對模型一點作用都沒有，只有當它對應的 $a_n^*$ 不等于0，它才會對決定最后的模型有用。只有少數(shù)的點會被選作支持向量，如果出現(xiàn)了異常值（outlier），那么只需要保證不把它選作支持向量就行了。比如如果是用的交叉熵作為損失函數(shù)，那么損失函數(shù)在每個地方的微分都是不等于0的，所以最終的 $a_n^*$ 也不會是稀疏的，那么每一個數(shù)據(jù)點對最后的模型都會有影響，所以相比于其他模型，支持向量機是比較穩(wěn)健的（robust）。
將式子 $\theta^*=\sum_n a_n^*x^n$ 矩陣化得到： $\theta=Xa$ ，則：
$f(x)=\theta^Tx=a^TX^Tx=\sum_n a_n(x^n*x)$
具體的矩陣變換如圖（圖中的 $w$ 就是指 $\theta$ ）：

Dual Representation

接下來，我們將假設函數(shù)寫成帶核函數(shù)的形式：

其中的就是核函數(shù)（Kernel Function），如果不作任何映射直接作內(nèi)積，就稱為線性核，得到的就是之前的線性支持向量機。
之前構造的線性支持向量機沒有作數(shù)據(jù)的映射，因此只能用來分隔線性的數(shù)據(jù)。如果數(shù)據(jù)線性不可分，就需要將映射到，映射到高維空間之后得到線性可分的數(shù)據(jù)：

映射

這樣帶來的問題是如果維度較高會導致計算量爆炸，因此使用核技巧（Kernel trick）可以幫助我們在高維映射下計算SVM，舉個高維映射的例子：

Kernel trick

這樣，計算就可以通過計算核函數(shù)來計算，避免了顯式地寫出映射后的結果，直接使計算量小了很多
在實際應用中，不需要去考慮如何映射，而是可以直接選擇核函數(shù)，通常我們會從一些核函數(shù)中選擇，例如：

線性核函數(shù)： $K(x,z)=<x,z>$ （向量內(nèi)積）
多項式核函數(shù)： $K(x,z)=(<x,z>+R)^d$
高斯核函數(shù)，高斯核函數(shù)是最常用的，可以將數(shù)據(jù)映射到無窮維，也叫做徑向基函數(shù)（Radial Basis Function，RBF）：
$K(x,z)=exp(-\frac{||x-z||^2}{2\sigma^2})$