Support Vector Machine

支持向量機反肋，一個有監(jiān)督的機器學習算法。通俗來講匾七，它是一種二類分類模型絮短，其基本模型定義為特征空間上的間隔最大的線性分類器，其學習策略便是間隔最大化昨忆，最終可轉化為一個凸二次規(guī)劃問題的求解丁频。

除了進行線性分類，支持向量機可以使用所謂的核技巧邑贴，它們的輸入隱含映射成高維特征空間中有效地進行非線性分類席里。

給定一些數(shù)據(jù)點，它們分別屬于兩個不同的類拢驾，現(xiàn)在要找到一個線性分類器把這些數(shù)據(jù)分成兩類奖磁。如果用 $x$ 表示數(shù)據(jù)點，用 $y$ 表示類別（ $y$ 可以取 1 或者 -1繁疤，分別代表兩個不同的類）咖为，一個線性分類器的學習目標便是要在 $n$ 維的數(shù)據(jù)空間中找到一個超平面(hyper plane)，這個超平面的方程可以表示為
$\omega^{T}x+b=0$
下面即簡單刻畫了這些數(shù)據(jù)：

%matplotlib inline
from sklearn.datasets import make_blobs
import mglearn
import matplotlib.pyplot as plt

#生成聚類數(shù)據(jù)
X,y = make_blobs(centers=2, random_state=1)
mglearn.discrete_scatter(X[:,0], X[:,1],y)
plt.xlabel("Feature 0")
plt.ylabel("Feature 1")

image.png

根據(jù)上圖我們可以很容易的作出一條線區(qū)分兩類數(shù)據(jù)點.那么要如何確定這個超平面呢?這個超平面應該是最適合分開兩類數(shù)據(jù)的直線稠腊。而判定“最適合”的標準就是這條直線離直線兩邊的數(shù)據(jù)的間隔最大躁染。所以，得尋找有最大間隔的超平面

import numpy as np
from mglearn.plot_helpers import cm2

def plot_2d_separator1(classifier, X, fill=False, ax=None, eps=None, alpha=1,
                      cm=cm2, linewidth=None, threshold=None,
                      linestyle="dashed",a=0):
    # binary?
    if eps is None:
        eps = X.std() / 2.

    if ax is None:
        ax = plt.gca()

    x_min, x_max = X[:, 0].min() - eps, X[:, 0].max() + eps
    y_min, y_max = X[:, 1].min() - eps, X[:, 1].max() + eps
    xx = np.linspace(x_min, x_max, 1000)
    yy = np.linspace(y_min, y_max, 1000)


    X1, X2 = np.meshgrid(xx, yy)

    X_grid = np.c_[X1.ravel(), X2.ravel()-a]

    try:
        decision_values = classifier.decision_function(X_grid)
        levels = [0] if threshold is None else [threshold]
        fill_levels = [decision_values.min()] + levels + [
            decision_values.max()]
    except AttributeError:
        # no decision_function
        decision_values = classifier.predict_proba(X_grid)[:, 1]
        levels = [.5] if threshold is None else [threshold]
        fill_levels = [0] + levels + [1]
    if fill:
        ax.contourf(X1, X2, decision_values.reshape(X1.shape),
                    levels=fill_levels, alpha=alpha, cmap=cm)
    else:
        ax.contour(X1, X2, decision_values.reshape(X1.shape), levels=levels,
                   colors="black", alpha=alpha, linewidths=linewidth,
                   linestyles=linestyle, zorder=5)

from sklearn.svm import LinearSVC
linear_svm = LinearSVC().fit(X,y)
plot_2d_separator1(linear_svm, X,a=2)
plot_2d_separator1(linear_svm, X,a=-2)
mglearn.plots.plot_2d_separator(linear_svm, X)
mglearn.discrete_scatter(X[:,0],X[:,1],y)
plt.xlabel("Feature 0")
plt.ylabel("Feature 1")

image.png

我們注意到 $|\omega^{T}x+b|$ 能夠表示點 $x$ 到距離超平面的遠近（相對遠近）,又類標記 $y$ 的符號 $(-1, +1)$ 表示不同類別架忌，故我們可以用
$\hat{\gamma}=y(\omega^{T}x+b)=yf(x)$
表示間隔吞彤，稱為函數(shù)間隔(functional margin)

但是這樣定義間隔，如果成比例的改變 $\omega$ 和 $b$ （如將它們改成 $2\omega$ 和 $2b$ ）叹放，則函數(shù)間隔的值 $f(x)$ 卻變成了原來的 2 倍（雖然此時超平面沒有改變）饰恕，所以我們要引入幾何間隔(geometrical margin)（經計算得）
$\gamma=\frac{\omega^{T}x+b}{||\omega||}=\frac{f(x)}{||\omega||}$
為了得到 $\gamma$ 的絕對值，令 $\gamma$ 乘上對應的類別 $y$ 井仰，即可得出幾何間隔
$\tilde{\gamma}=y\gamma=\frac{\hat{\gamma}}{||\omega||}$

對一個數(shù)據(jù)點進行分類埋嵌，當超平面離數(shù)據(jù)點的“間隔”越大，分類的確信度也越大俱恶，為了使分類的確信度盡量高莉恼，需要讓所選擇的超平面能夠最大化這個“間隔”值。而在這個間隔值上的數(shù)據(jù)點被稱為是支持向量(support vector)的,這就是支持向量機的由來速那。于是最大間隔分類器(maximum margin classifier) 的目標函數(shù)定義為：
$max\tilde{\gamma}$
同時要滿足一些條件俐银，根據(jù)間隔的定義，有：
$y_{i}(\omega^{T}x_{i}+b)=\hat{\gamma_{i}}\geq \hat{\gamma},\quad i=1,..,n$

如果令函數(shù)間隔 $\hat{\gamma}$ 等于 1端仰，則有 $\tilde{\gamma}=\frac{1}{||\omega||}$ 且 $y_{i}(\omega^{T}x_{i}+b)\geq 1,i=1,...,n$ 捶惜，從而上述目標函數(shù)轉換為
$max\frac{1}{||\omega||},\qquad s.t.\ y_{i}(\omega^{T}x_{i}+b)\geq 1,i=1,...,n$

由于求 $\frac{1}{||\omega||}的最大值相當于求\frac{1}{2}||\omega||^2$ 的最小值，所以上述目標函數(shù)等價于
$min\frac{1}{2}||\omega||^2,\qquad s.t.\ y_{i}(\omega^{T}x_{i}+b)\geq 1,i=1,...,n$

因為現(xiàn)在的目標函數(shù)是二次的荔烧，約束條件是線性的吱七，所以它是一個凸二次規(guī)劃問題汽久。此外，由于這個問題的特殊結構踊餐，還可以通過拉格朗日對偶性(Lagrange Duality)變換到對偶變量的優(yōu)化問題景醇，即通過求解與原問題等價的對偶問題得到原始問題的最優(yōu)解，這就是線性可分條件下支持向量機的對偶算法吝岭，這樣做的有點在于：一者對偶問題往往更容易求解三痰；二者可以自然的引入核函數(shù)。進而推廣到非線性分類問題

我們通過給每一個約束條件加上一個拉格朗日乘子(Lagrange multiplier) $\alpha$ 窜管，定義拉格朗日函數(shù)（通過拉格朗日函數(shù)將約束條件融合到目標函數(shù)里散劫，從而只用一個函數(shù)表達式能夠清楚表達問題）：
$\mathcal{L}(\omega,b,\alpha)=\frac{1}{2}||\omega||^2-\sum_{i=1}^{n}\alpha_{i}(y_{i}(\omega^{T}x_{i}+b)-1)$
然后令：
$\theta(\omega)=\max_{\alpha_{i}\geq 0}\mathcal{L}(\omega,b,\alpha)$
如果沒有對 $\alpha_{i}$ 的限制， $\theta(\omega)$ 會等于無窮大

容易驗證幕帆，當所有約束條件都得到滿足時获搏，則有 $\theta(\omega)=\frac{1}{2}||\omega||^2$ ，亦即最初要最小化的量失乾，所以等價于直接最小化 $\theta(\omega)$

故目標函數(shù)變成：
$\min_{\omega,b}\theta(\omega)=\min_{\omega,b}\max_{\alpha_{i}\geq 0}\mathcal{L}(\omega,b,\alpha)=p^*$
這里用 $p^*$ 表示這個問題的最優(yōu)值常熙，且和最初的問題是等價的。如果直接求解碱茁，那么一上來便得應對 $\omega$ 和 $b$ 兩個參數(shù)裸卫，而 $\alpha_{i}$ 又是不等式約束，這個求解過程不好做早芭”顺牵可以把最小的最大的位置變換一下诅蝶，變成：
$\max_{\alpha_{i}\geq 0}\min_{\omega,b}\mathcal{L}(\omega,b,\alpha)=d^*$
交換以后的新問題是原始問題的對偶問題退个，這個問題的最優(yōu)值用 $d^*$ 來表示。而且有 $d^* \leq p^*$ 调炬。在滿足某些條件的情況下语盈，兩者等價，這個時候就可以用求解對偶問題來間接地求解原始問題缰泡。

上面提到 “ $d^* \leq p^*$ 在滿足某些條件的情況下刀荒，兩者等價”，這所謂的“滿足某些條件”就是要滿足 $KKT$ 條件棘钞。經過證明（省略）缠借，這里的問題是滿足 $KKT$ 條件的，因此現(xiàn)在轉化為求解第二個問題宜猜。而求解這個對偶問題泼返，分為3個步驟：1.首先要讓 $\mathcal{L}(\omega,b,\alpha)$ 關于 $\omega$ 和 $b$ 最小化，2.然后求對 $\alpha$ 的極大姨拥，3.最后利用 $SMO$ 算法求解對偶問題中的拉格朗日乘子绅喉。

1.首先固定 $\alpha$ 渠鸽，要讓 $\mathcal{L}$ 關于 $\omega$ 和 $b$ 最小化，我們分別對 $\omega$ 柴罐， $b$ 求偏導數(shù)徽缚，即令 $\partial \mathcal{L}/ \partial \omega$ 和 $\partial \mathcal{L}/ \partial b$ 等于零：
$\frac{\partial \mathcal{L}}{\partial \omega}=0 \Rightarrow \omega=\sum_{i=1}^{n}\alpha_{i}y_{i}x_{i}$
$\frac{\partial \mathcal{L}}{\partial b}=0 \Rightarrow \sum_{i=1}^{n}\alpha_{i}y_{i}=0$
將其帶入之前的 $\mathcal{L}$ ，得到：
$\mathcal{L}(\omega,b,\alpha)=\sum_{i=1}^{n}\alpha_{i}-\frac{1}{2}\sum_{i,j=1}^{n}\alpha_{i}\alpha_{j}y_{i}y_{j}x_{i}^T x_{j}$

2.對 $\alpha$ 求極大革屠，即是關于對偶問題的最優(yōu)化問題凿试。根據(jù)上式有：
$\max_{\alpha}\sum_{i=1}^{n}\alpha_{i}-\frac{1}{2}\sum_{i,j=1}^{n}\alpha_{i}\alpha_{j}y_{i}y_{j}x_{i}^T x_{j}$
$s.t. \quad \alpha_{i}\geq 0,i=1,...,n$
$\sum_{i=1}^{n}\alpha_{i}y_{i}=0$
如果求出了 $\alpha_{i}$ 根據(jù)：
$\omega^*=\sum_{i=1}^{n}\alpha_{i}y_{i}x_{i}$
$b^*=-\frac{max_{i:y_{i}=-1}\omega^{*T} x_{i}+min_{i:y_{i}-1}\omega^{*T} x_{i}}{2}$
即可求出 $\omega,b$ ，最終得出分類超平面和分類決策函數(shù)

3.求解上式
$\max_{\alpha}\sum_{i=1}^{n}\alpha_{i}-\frac{1}{2}\sum_{i,j=1}^{n}\alpha_{i}\alpha_{j}y_{i}y_{j}x_{i}^T x_{j}$
$s.t. \quad \alpha_{i}\geq 0,i=1,...,n$
$\sum_{i=1}^{n}\alpha_{i}y_{i}=0$
等價于求解（這個等價引入了后面的松弛變量屠阻，及對偶原則红省，不加證明）：
$\min_{\alpha}\Psi(\vec \alpha)=\min_{\alpha}\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}y_{i}y_{j}K(x_{i},x_{j})\alpha_{i}\alpha_{j}-\sum_{i=1}^{n}\alpha_{i}$
$s.t. \quad 0\leq \alpha_{i}\leq C,i=1,...,n$
$\sum_{i=1}^{n}\alpha_{i}y_{i}=0$
下面要解決的問題就是：在 $\alpha_{i}={\alpha_{1},\alpha_{2},...,\alpha_{n}}$ 上求上述目標函數(shù)的最小值。為了求解這些乘子国觉，每次從中任意抽取兩個乘子 $\alpha_{1}$ 和 $\alpha_{2}$ 吧恃，然后固定 $\alpha_{1}$ 和 $\alpha_{2}$ 以外的其它乘子 ${\alpha_{3},...,\alpha_{n}}$ ，使得目標函數(shù)只是關于 $\alpha_{1}$ 和 $\alpha_{2}$ 的函數(shù)麻诀。這樣痕寓，不斷的從一堆乘子中任意抽取兩個求解，不斷的迭代求解子問題蝇闭，最終達到求解原問題的目的呻率。

（具體如何求解，略）

根據(jù)前面推導的：
$\omega^*=\sum_{i=1}^{n}\alpha_{i}y_{i}x_{i}$
帶入分類函數(shù)有：
$f(x)=(\sum_{i=1}^{n}\alpha_{i}y_{i}x_{i})^T x+b=\sum_{i=1}^{n}\alpha_{i}y_{i}<x_{i},x>+b$
通過這種形式我們觀察到呻引，對于新點x的預測礼仗，只需要計算它與訓練數(shù)據(jù)點的內積即可，這一點至關重要逻悠，是之后使用Kernel進行非線性推廣的基本前提元践。此外，所謂Supporting Vector 也在這里顯示出來——事實上童谒，所有非Supporting Vector 所對應的系數(shù) $\alpha$ 都是等于零的单旁，因此對于新點的內積計算實際上只要針對少量的“支持向量”而不是所有的訓練數(shù)據(jù)即可。

到目前為止饥伊，我們的SVM還比較弱象浑，只能處理線性的情況，不過琅豆，在得到對偶形式之后愉豺，通過Kernel推廣到非線性的情況就變成一件比較容易的事情。

我們觀察一下下面的數(shù)據(jù)：

X,y = make_blobs(centers=4, random_state=8)
y = y%2

mglearn.discrete_scatter(X[:,0],X[:,1],y)
plt.xlabel('Feature 0')
plt.ylabel('Feature 1')

image.png

對于上面的數(shù)據(jù)茫因，我們可以知道他們是線性不可分的蚪拦，對于非線性的情況，SVM的處理方法是選擇一個核函數(shù)K(.,.)，通過將數(shù)據(jù)映射到高維空間外盯，來解決在原始空間中先行不可分的問題摘盆。

為了理解這個過程（映射到高維空間)，我們簡單的假設添加第二個特征的平方作為一個新特征饱苟，生成一個三維圖孩擂。

X_new = np.hstack([X, X[:,1:]** 2])
from mpl_toolkits.mplot3d import Axes3D,axes3d
figure = plt.figure()

ax=Axes3D(figure, elev=-152, azim=-26)
mask = y == 0
ax.scatter(X_new[mask,0],X_new[mask,1],X_new[mask,2],c='b',
          cmap=mglearn.cm2, s=60)
ax.scatter(X_new[~mask,0],X_new[~mask,1],X_new[~mask,2],c='r',marker='^',cmap=mglearn.cm2, s=60)
ax.set_xlabel("feature0")
ax.set_ylabel("feature1")
ax.set_zlabel("feature1**2")

image.png

現(xiàn)在我們可以用線性模型將這兩個類別分開。

linear_svm_3d = LinearSVC().fit(X_new, y)
coef, intercept = linear_svm_3d.coef_.ravel(),linear_svm_3d.intercept_
figure = plt.figure()
ax = Axes3D(figure, elev=-152, azim=-26)
xx = np.linspace(X_new[:,0].min()-2,X_new[:,0].max()+2,50)
yy = np.linspace(X_new[:,1].min()-2,X_new[:,1].max()+2,50)

XX,YY = np.meshgrid(xx,yy)
ZZ = (coef[0] * XX + coef[1] * YY + intercept) / -coef[2]
ax.plot_surface(XX,YY,ZZ,rstride=8,cstride=8,alpha=0.6)
ax.scatter(X_new[mask,0], X_new[mask,1], X_new[mask,2],c='b',
          cmap=mglearn.cm2,s=60)
ax.scatter(X_new[~mask,0], X_new[~mask,1], X_new[~mask,2],c='r',marker='^',
          cmap=mglearn.cm2,s=60)

image.png

如果將線性SVM模型看作原始特征的函數(shù)箱熬，那么它實際上已經不是線性的了类垦。他不是一條直線，而是一個橢圓

ZZ = YY**2
dec = linear_svm_3d.decision_function(np.c_[XX.ravel(),YY.ravel(),ZZ.ravel()])
plt.contourf(XX, YY, dec.reshape(XX.shape), levels=[dec.min(),0,dec.max()],cmap=mglearn.cm2, alpha=0.5)
mglearn.discrete_scatter(X[:,0],X[:,1],y)
plt.xlabel("Feature 0")
plt.ylabel("Feature 1")

image.png

從上面的例子中城须，我們簡單的理解了一下處理非線性的方法

支持向量機首先在低維空間中完成計算蚤认，然后通過核函數(shù)將輸入空間映射到高維特征空間，最終在高維特征空間中構造出最優(yōu)分離超平面糕伐，從而把平面上本身不好分的非線性數(shù)據(jù)分開砰琢。

而在我們遇到核函數(shù)之前，如果用原始的方法良瞧，那么在用線性學習器學習一個非線性關系陪汽，需要選擇一個非線性特征集，并且將數(shù)據(jù)寫成新的表達形式褥蚯，這等價于應用一個固定的非線性映射挚冤，將數(shù)據(jù)映射到特征空間，在特征空間中使用線性學習器赞庶，因此训挡，考慮的假設集是這種類型的函數(shù)：
$f(x)=\sum_{i=1}^{N}\omega_{i}\phi_{i}(x)+b$
這里的 $\phi$ : $\mathcal{X}\to \mathcal{F}$ 是從輸入空間到某個特征空間的映射，這意味著建立非線性學習器分為兩步:

1.首先使用一個非線性映射將數(shù)據(jù)變換到一個特征空間 $\mathcal{F}$ ;

2.然后在特征空間使用線性學習器分類歧强。

根據(jù)之前導出的內積形式：
$f(x)=\sum_{i=1}^{n}\alpha_{i}y_{i}<x_{i},x>+b$
及上面所述澜薄，我們可以在原始特征空間中直接計算內積 $<\phi(x_{i}),\phi(x)>$ ，就有可能將兩個步驟融合到一起建立一個非線性的學習器誊锭，這樣直接計算法的方法稱為核函數(shù)方法

核(Kernel)是一個函數(shù)K表悬，對所有的 $x,z\in \mathcal{X}$ 弥锄，滿足 $K(x,z)=<\phi(x_{i}),\phi(x)>$ 丧靡，這里 $\phi$ 是從 $\mathcal{X}$ 到內積特征空間 $\mathcal{F}$ 的映射

an1 = np.linspace(0, 2*np.pi, 100) 
an2 = np.linspace(0, 2*np.pi, 100)
fig,ax = plt.subplots()
ax.plot(3*np.cos(an1)+np.random.rand(100)*0.3, 3*np.sin(an1)+np.random.rand(100)*0.3,'.')
ax.plot(2*np.cos(an2)+np.random.rand(100)*0.3, 2*np.sin(an2)+np.random.rand(100)*0.3,'.')

image.png

對于上面的數(shù)據(jù)，（用兩個橢圓加了點噪聲生成）籽暇，理想的分界應該是一個“圓圈”温治，我們知道任意一條二次曲線都可以寫成下面的形式：
$a_{1}X_{1}+a_{2}X_{1}^{2}+a_{3}X_{2}+a_{4}X_{2}^{2}+a_{5}X_{1}X_{2}+a_{6}=0$

注意上面的形式，如果我們構造另外一個五維的空間戒悠，其中五個坐標的值分別為 $Z_{1}=X_{1}, Z_{2}=X_{1}^{2}, Z_{3}=X_{2}, Z_{4}=X_{2}^{2}, Z_{5}=X_{1}X_{2}$ 熬荆，那么上面的方程在新的坐標系下可以寫成：
$\sum_{i=1}^{5}a_{i}Z_{i}+a_{6}=0$
此時的坐標 $Z$ ，是一個超平面方程绸狐，也就是卤恳，我們做的一個映射 $\phi$ ： $\mathfrak{R}^2 \to \mathfrak{R}^5$ 累盗，將 $X$ 按照上面的規(guī)則映射為 $Z$ ，那么在新的空間中原來的數(shù)據(jù)將變成線性可分的（可以參照上面的特征平方的例子）突琳。這正是Kernel方法處理非線性問題的基本思想若债。

核函數(shù)相當于把原來的分類函數(shù)：
$f(x)=\sum_{i=1}^{n}\alpha_{i}y_{i}<x_{i},x>+b$
映射成：
$f(x)=\sum_{i=1}^{n}\alpha_{i}y_{i}<\phi(x_{i}),\phi(x)>+b$
這樣看似我們的問題得到了解決，其實不然拆融，因為我們發(fā)現(xiàn)對一個二維空間做映射蠢琳，得到一個五維空間。如果原始空間是三維的話镜豹，那么就會得到一個19維空間傲须，這會給計算帶來非常大的困難。如果遇到無窮維的情況趟脂，就變得無從計算泰讽。

我們從剛才的例子出發(fā)。設兩個向量 $x_{1}=(\eta_{1},\eta_{2})^T$ 和 $x_{2}=(\xi_{1},\xi_{2})^T$ 映射后的內積為：
$<\phi(x_{i}),\phi(x)>=\eta_{1}\xi_{1}+\eta_{1}^{2}\xi_{1}^{2}+\eta_{2}\xi_{2}+\eta_{2}^{2}\xi_{2}^{2}+\eta_{1}\eta_{2}\xi_{1}\xi_{2}$
另外我們注意到：
$(<x_{1},x_{2}>+1)^2=2\eta_{1}\xi_{1}+\eta_{1}^{2}\xi_{1}^{2}+2\eta_{2}\xi_{2}+\eta_{2}^{2}\xi_{2}^{2}+2\eta_{1}\eta_{2}\xi_{1}\xi_{2}+1$
兩者有很多相似的地方昔期，實際上菇绵，上面這個式子的計算結果實際上和映射：
$\phi(x_{1},x_{2}) =(\sqrt{2}x_{1},x_{1}^{2},\sqrt{2}x_{2},x_{2}^{2},\sqrt{2}x_{1}x_{2},1)^T$
之后的內積 $<\phi(x_{1}),\phi(x_{2})>$ 的結果是相等的，它們的區(qū)別在于：

1.一個是映射到高維空間中镇眷，然后再根據(jù)內積的公式進行計算咬最；

2.而另一個則直接在原來的低維空間中進行計算，而不需要顯式地寫出映射后的結果欠动。

我們把計算兩個向量在隱式映射過后的空間中的內積的函數(shù)叫做核函數(shù)永乌。

常用的核函數(shù)有：

1.多項式核 $K(x_{1},x_{2})=(<x_{1},x_{2}>+R)^d$

2.高斯核 $K(x_{1},x_{2})=exp(-||x_{1}-x_{2}||^2 / 2 \sigma^2)$ （通過調控 $\sigma$ ，高斯核實際上具有相當高的靈活性）

3.線性核 $K(x_{1},x_{2})=<x_{1},x_{2}>$

到此為止具伍，還有些問題沒有解決翅雏。例如可能并不是因為數(shù)據(jù)本身是非線性結構的，而只是因為數(shù)據(jù)有噪聲人芽。對于這種偏離正常位置很遠的數(shù)據(jù)點望几，我們稱之為outlier,outlier的存在有可能造成很大的影響，因為超平面本身就是只有少數(shù)幾個support vector組成的萤厅，這樣就會造成很大的影響橄抹。

為此我們引入松弛變量 $\xi_{i}$ ，那么約束條件變成：
$y_{i}(\omega^T x_{i}+b)\geq 1-\xi_{i},\quad i=1,...,n$
它為對應數(shù)據(jù)點 $x_{i}$ 允許偏移的量惕味，但是 $\xi_{i}$ 又不能隨意擴大楼誓，所以我們在目標函數(shù)后加一項，使得 $\xi_{i}$ 總和最忻印：
$min \frac{1}{2}||\omega||^2 + C\sum_{i=1}^{n}\xi_{i}$

其中C是一個參數(shù)疟羹，用于控制目標函數(shù)中兩項（“尋找margin最大的超平面”和“保證數(shù)據(jù)點偏移量最小”）之間的權重。用之前的方法將限制約束條件加入到目標函數(shù)中，得到新的拉格朗日函數(shù)榄融，如下所示：
$\mathcal{L}(\omega,b,\xi,\alpha,r)=\frac{1}{2}||\omega||^2+C\sum_{i=1}{n}\xi_{i}-\sum_{}^{}\alpha_{i}(y_{i}(\omega^T x_{i}+b)-1+\xi_{i})-\sum_{i=1}^{n}r_{i}\xi_{i}$
經過計算参淫，現(xiàn)在問題寫作：
$\max_{\alpha}\sum_{i=1}^{n}\alpha_{i}-\frac{1}{2}\sum_{i,j=1}^{n}\alpha_{i}\alpha_{j}y_{i}y_{j}x_{i}^T x_{j}$
$s.t. \quad 0 \leq \alpha_{i} \leq C,i=1,...,n$
$\sum_{i=1}^{n}\alpha_{i}y_{i}=0$

這樣一個稍微完整的，可以處理線性核非線性并能容忍噪聲和outliers的支持向量機差不多簡單介紹完了愧杯。

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者

人面猴
序言：七十年代末黄刚，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子民效，更是在濱河造成了極大的恐慌憔维，老刑警劉巖，帶你破解...
沈念sama閱讀 222,681評論 6贊 517
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件畏邢，死亡現(xiàn)場離奇詭異业扒，居然都是意外死亡，警方通過查閱死者的電腦和手機舒萎，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 95,205評論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門程储，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人臂寝，你說我怎么就攤上這事章鲤。” “怎么了咆贬？”我有些...
開封第一講書人閱讀 169,421評論 0贊 362
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵败徊，是天一觀的道長。經常有香客問我掏缎，道長皱蹦，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 60,114評論 1贊 300
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮，結果婚禮上牙瓢，老公的妹妹穿的比我還像新娘。我一直安慰自己辜妓，他們只是感情好，可當我...
茶點故事閱讀 69,116評論 6贊 398
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布忌怎。她就那樣靜靜地躺著籍滴，像睡著了一般。火紅的嫁衣襯著肌膚如雪呆躲。梳的紋絲不亂的頭發(fā)上异逐，一...
開封第一講書人閱讀 52,713評論 1贊 312
城市分裂傳說
那天捶索，我揣著相機與錄音插掂，去河邊找鬼。笑死，一個胖子當著我的面吹牛辅甥，可吹牛的內容都是我干的酝润。我是一名探鬼主播，決...
沈念sama閱讀 41,170評論 3贊 422
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼璃弄，長吁一口氣：“原來是場噩夢啊……” “哼要销！你這毒婦竟也來了？” 一聲冷哼從身側響起夏块，我...
開封第一講書人閱讀 40,116評論 0贊 277
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤疏咐，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后脐供，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體浑塞，經...
沈念sama閱讀 46,651評論 1贊 320
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內容為張勛視角年9月15日...
茶點故事閱讀 38,714評論 3贊 342
?白月光啟示錄
正文我和宋清朗相戀三年政己，在試婚紗的時候發(fā)現(xiàn)自己被綠了酌壕。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點故事閱讀 40,865評論 1贊 353
活死人
序言：一個原本活蹦亂跳的男人離奇死亡歇由，死狀恐怖卵牍，靈堂內的尸體忽然破棺而出，到底是詐尸還是另有隱情沦泌，我是刑警寧澤糊昙，帶...
沈念sama閱讀 36,527評論 5贊 351
?日本核電站爆炸內幕
正文年R本政府宣布，位于F島的核電站谢谦，受9級特大地震影響溅蛉，放射性物質發(fā)生泄漏。R本人自食惡果不足惜他宛，卻給世界環(huán)境...
茶點故事閱讀 42,211評論 3贊 336
男人毒藥：我在死后第九天來索命
文/蒙蒙一船侧、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧厅各，春花似錦镜撩、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,699評論 0贊 25
一樁弒父案袁梗，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至憔古，卻和暖如春遮怜，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背鸿市。一陣腳步聲響...
開封第一講書人閱讀 33,814評論 1贊 274
情欲美人皮
我被黑心中介騙來泰國打工锯梁，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留即碗，地道東北人。一個月前我還...
沈念sama閱讀 49,299評論 3贊 379
代替公主和親
正文我出身青樓陌凳，卻偏偏與公主長得像剥懒，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子合敦，可洞房花燭夜當晚...
茶點故事閱讀 45,870評論 2贊 361

Support Vector Machine

推薦閱讀更多精彩內容