支持向量機反肋,一個有監(jiān)督的機器學習算法。通俗來講匾七,它是一種二類分類模型絮短,其基本模型定義為特征空間上的間隔最大的線性分類器,其學習策略便是間隔最大化昨忆,最終可轉化為一個凸二次規(guī)劃問題的求解丁频。
除了進行線性分類,支持向量機可以使用所謂的核技巧邑贴,它們的輸入隱含映射成高維特征空間中有效地進行非線性分類席里。
給定一些數(shù)據(jù)點,它們分別屬于兩個不同的類拢驾,現(xiàn)在要找到一個線性分類器把這些數(shù)據(jù)分成兩類奖磁。如果用
表示數(shù)據(jù)點,用
表示類別(
可以取 1 或者 -1繁疤,分別代表兩個不同的類)咖为,一個線性分類器的學習目標便是要在
維的數(shù)據(jù)空間中找到一個超平面(hyper plane),這個超平面的方程可以表示為
下面即簡單刻畫了這些數(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")
根據(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")
我們注意到
能夠表示點
到距離超平面的遠近(相對遠近),又類標記
的符號
表示不同類別架忌,故我們可以用
表示間隔吞彤,稱為函數(shù)間隔(functional margin)
但是這樣定義間隔,如果成比例的改變
和
(如將它們改成
和
)叹放,則函數(shù)間隔的值
卻變成了原來的 2 倍(雖然此時超平面沒有改變)饰恕,所以我們要引入幾何間隔(geometrical margin)(經計算得)
為了得到的絕對值,令
乘上對應的類別
井仰,即可得出幾何間隔
對一個數(shù)據(jù)點進行分類埋嵌,當超平面離數(shù)據(jù)點的“間隔”越大,分類的確信度也越大俱恶,為了使分類的確信度盡量高莉恼,需要讓所選擇的超平面能夠最大化這個“間隔”值。而在這個間隔值上的數(shù)據(jù)點被稱為是支持向量(support vector)的,這就是支持向量機的由來速那。于是最大間隔分類器(maximum margin classifier) 的目標函數(shù)定義為:
同時要滿足一些條件俐银,根據(jù)間隔的定義,有:
如果令函數(shù)間隔
等于 1端仰,則有
且
捶惜,從而上述目標函數(shù)轉換為
由于求
的最小值,所以上述目標函數(shù)等價于
因為現(xiàn)在的目標函數(shù)是二次的荔烧,約束條件是線性的吱七,所以它是一個凸二次規(guī)劃問題汽久。此外,由于這個問題的特殊結構踊餐,還可以通過拉格朗日對偶性(Lagrange Duality)變換到對偶變量的優(yōu)化問題景醇,即通過求解與原問題等價的對偶問題得到原始問題的最優(yōu)解,這就是線性可分條件下支持向量機的對偶算法吝岭,這樣做的有點在于:一者對偶問題往往更容易求解三痰;二者可以自然的引入核函數(shù)。進而推廣到非線性分類問題
我們通過給每一個約束條件加上一個拉格朗日乘子(Lagrange multiplier)
窜管,定義拉格朗日函數(shù)(通過拉格朗日函數(shù)將約束條件融合到目標函數(shù)里散劫,從而只用一個函數(shù)表達式能夠清楚表達問題):
然后令:
如果沒有對的限制,
會等于無窮大
容易驗證幕帆,當所有約束條件都得到滿足時获搏,則有
,亦即最初要最小化的量失乾,所以等價于直接最小化
![]()
故目標函數(shù)變成:
這里用表示這個問題的最優(yōu)值常熙,且和最初的問題是等價的。如果直接求解碱茁,那么一上來便得應對
和
兩個參數(shù)裸卫,而
又是不等式約束,這個求解過程不好做早芭”顺牵可以把最小的最大的位置變換一下诅蝶,變成:
交換以后的新問題是原始問題的對偶問題退个,這個問題的最優(yōu)值用來表示。而且有
调炬。在滿足某些條件的情況下语盈,兩者等價,這個時候就可以用求解對偶問題來間接地求解原始問題缰泡。
上面提到 “
在滿足某些條件的情況下刀荒,兩者等價”,這所謂的“滿足某些條件”就是要滿足
條件棘钞。經過證明(省略)缠借,這里的問題是滿足
條件的,因此現(xiàn)在轉化為求解第二個問題宜猜。而求解這個對偶問題泼返,分為3個步驟:1.首先要讓
關于
和
最小化,2.然后求對
的極大姨拥,3.最后利用
算法求解對偶問題中的拉格朗日乘子绅喉。
1.首先固定
渠鸽,要讓
關于
和
最小化,我們分別對
柴罐,
求偏導數(shù)徽缚,即令
和
等于零:
將其帶入之前的,得到:
2.對
求極大革屠,即是關于對偶問題的最優(yōu)化問題凿试。根據(jù)上式有:
如果求出了根據(jù):
即可求出,最終得出分類超平面和分類決策函數(shù)
3.求解上式
等價于求解(這個等價引入了后面的松弛變量屠阻,及對偶原則红省,不加證明):
下面要解決的問題就是:在上求上述目標函數(shù)的最小值。為了求解這些乘子国觉,每次從中任意抽取兩個乘子
和
吧恃,然后固定
和
以外的其它乘子
,使得目標函數(shù)只是關于
和
的函數(shù)麻诀。這樣痕寓,不斷的從一堆乘子中任意抽取兩個求解,不斷的迭代求解子問題蝇闭,最終達到求解原問題的目的呻率。
(具體如何求解,略)
根據(jù)前面推導的:
帶入分類函數(shù)有:
通過這種形式我們觀察到呻引,對于新點x的預測礼仗,只需要計算它與訓練數(shù)據(jù)點的內積即可,這一點至關重要逻悠,是之后使用Kernel進行非線性推廣的基本前提元践。此外,所謂Supporting Vector 也在這里顯示出來——事實上童谒,所有非Supporting Vector 所對應的系數(shù)都是等于零的单旁,因此對于新點的內積計算實際上只要針對少量的“支持向量”而不是所有的訓練數(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')
對于上面的數(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")
現(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)
如果將線性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")
從上面的例子中城须,我們簡單的理解了一下處理非線性的方法
支持向量機首先在低維空間中完成計算蚤认,然后通過核函數(shù)將輸入空間映射到高維特征空間,最終在高維特征空間中構造出最優(yōu)分離超平面糕伐,從而把平面上本身不好分的非線性數(shù)據(jù)分開砰琢。
而在我們遇到核函數(shù)之前,如果用原始的方法良瞧,那么在用線性學習器學習一個非線性關系陪汽,需要選擇一個非線性特征集,并且將數(shù)據(jù)寫成新的表達形式褥蚯,這等價于應用一個固定的非線性映射挚冤,將數(shù)據(jù)映射到特征空間,在特征空間中使用線性學習器赞庶,因此训挡,考慮的假設集是這種類型的函數(shù):
這里的:
是從輸入空間到某個特征空間的映射,這意味著建立非線性學習器分為兩步:
1.首先使用一個非線性映射將數(shù)據(jù)變換到一個特征空間;
2.然后在特征空間使用線性學習器分類歧强。
根據(jù)之前導出的內積形式:
及上面所述澜薄,我們可以在原始特征空間中直接計算內積,就有可能將兩個步驟融合到一起建立一個非線性的學習器誊锭,這樣直接計算法的方法稱為核函數(shù)方法
核(Kernel)是一個函數(shù)K表悬,對所有的
弥锄,滿足
丧靡,這里
是從
到內積特征空間
的映射
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,'.')
對于上面的數(shù)據(jù),(用兩個橢圓加了點噪聲生成)籽暇,理想的分界應該是一個“圓圈”温治,我們知道任意一條二次曲線都可以寫成下面的形式:
注意上面的形式,如果我們構造另外一個五維的空間戒悠,其中五個坐標的值分別為
熬荆,那么上面的方程在新的坐標系下可以寫成:
此時的坐標,是一個超平面方程绸狐,也就是卤恳,我們做的一個映射
:
累盗,將
按照上面的規(guī)則映射為
,那么在新的空間中原來的數(shù)據(jù)將變成線性可分的(可以參照上面的特征平方的例子)突琳。這正是Kernel方法處理非線性問題的基本思想若债。
核函數(shù)相當于把原來的分類函數(shù):
映射成:
這樣看似我們的問題得到了解決,其實不然拆融,因為我們發(fā)現(xiàn)對一個二維空間做映射蠢琳,得到一個五維空間。如果原始空間是三維的話镜豹,那么就會得到一個19維空間傲须,這會給計算帶來非常大的困難。如果遇到無窮維的情況趟脂,就變得無從計算泰讽。
我們從剛才的例子出發(fā)。設兩個向量
和
映射后的內積為:
另外我們注意到:
兩者有很多相似的地方昔期,實際上菇绵,上面這個式子的計算結果實際上和映射:
之后的內積的結果是相等的,它們的區(qū)別在于:
1.一個是映射到高維空間中镇眷,然后再根據(jù)內積的公式進行計算咬最;
2.而另一個則直接在原來的低維空間中進行計算,而不需要顯式地寫出映射后的結果欠动。
我們把計算兩個向量在隱式映射過后的空間中的內積的函數(shù)叫做核函數(shù)永乌。
常用的核函數(shù)有:
1.多項式核
2.高斯核(通過調控
,高斯核實際上具有相當高的靈活性)
3.線性核
到此為止具伍,還有些問題沒有解決翅雏。例如可能并不是因為數(shù)據(jù)本身是非線性結構的,而只是因為數(shù)據(jù)有噪聲人芽。對于這種偏離正常位置很遠的數(shù)據(jù)點望几,我們稱之為outlier,outlier的存在有可能造成很大的影響,因為超平面本身就是只有少數(shù)幾個support vector組成的萤厅,這樣就會造成很大的影響橄抹。
為此我們引入松弛變量,那么約束條件變成:
它為對應數(shù)據(jù)點允許偏移的量惕味,但是
又不能隨意擴大楼誓,所以我們在目標函數(shù)后加一項,使得
總和最忻印:
其中C是一個參數(shù)疟羹,用于控制目標函數(shù)中兩項(“尋找margin最大的超平面”和“保證數(shù)據(jù)點偏移量最小”)之間的權重。用之前的方法將限制約束條件加入到目標函數(shù)中,得到新的拉格朗日函數(shù)榄融,如下所示:
經過計算参淫,現(xiàn)在問題寫作:
這樣一個稍微完整的,可以處理線性核非線性并能容忍噪聲和outliers的支持向量機差不多簡單介紹完了愧杯。