SVM

Profile

FullName: Support Vector Machine

vs Logistic Regression

Logistic Regression

聲明損失函數(shù): L(\theta)=\sum_{i=1}^N(y_i(1-\ln{(\sigma(\theta·X_b^{(i)}})) + (1-y_i)(\ln{(\sigma{(\theta·X_b^{(i)})})}))
其中:\hat{y} = \sigma(t) = \frac{1}{1+exp(-t)}
求解:argmin_{\theta}L({\theta})
Logistic回歸的決策邊界可以使得向量(ln(\hat{y})-ln(y))的范數(shù)盡可能小,即盡可能保證陽性事件的預(yù)測概率盡可能大,陰性事件的預(yù)測概率盡可能小

Support Vector Machine

hard-margin:找到一個超平面f(θ),使這個超平面兩邊的最近的兩個點(Support Vector)與這個超平面的距離(margin/2)最遠(yuǎn),f(θ)作為分類邊界,并且不允許有點落在margin區(qū)域內(nèi)

soft-margin:允許部分向量落在margin區(qū)域或者margin對岸,并將這些點距離margin的距離作為損失函數(shù)的一部分.

svm的數(shù)學(xué)表達(dá)

hard-margin-SVM

二維空間中(x_0,y_0)到直線l(Ax+By+C=0)的距離 d = \frac{(Ax_0+By_0+C)}{\sqrt{A^2+B^2}}
拓展到N維空間,向量x_b到超平面\theta^T·x=0的距離d_b = \frac{| w_0^Tx+b_0|}{\|w_0\|}
設(shè) margin = 2d
\begin{equation} \begin{cases} \frac{w_0^Tx^{(i)}+b_0}{\|w_0\|}>=d & \forall y^{(i)} =1\\ \frac{w_0^Tx^{(i)}+b_0}{\|w_0\|}<=-d & \forall y^{(i)}=-1 \end{cases} \end{equation}=>\begin{cases} \frac{w_0^Tx^{(i)}+b_0}{\|w_0\|d} >= 1 & \forall y^{(i)} = 1 \\ \frac{w_0^Tx^{(i)}+b_0}{\|w_0\|d}<=-1 & \forall y^{(i)}=-1 \end{cases}=>\frac{y^{(i)}(w_0^Tx^{(i)}+b_0)}{\|w_0\|d} >= 1
令w = \frac{w_0^T}{\|w_0\|d},b=\frac{b_0}{\|w_0\|d},約束條件可表示為y^{(i)}(w·x^{(i)}+b) >= 1
對于任意支撐向量x_s,x_s到l的距離d = \frac{|w·x_s+b|}{\|w\|}=\frac{1}{\|w\|}
d=d_{max} 時w= \|w\|_{min},所以svm問題可轉(zhuǎn)化為有條件的最優(yōu)值問題
min\frac{1}{2}\|w\|^2 \\ s.t. \quad\forall(x^{(i)},y^{(i)}) \in trainDataSet \quad y^{(i)}(w·x^{(i)}+b)>=1

soft-margin-SVM

允許部分點越過支撐向量,越過的部分會作為損失函數(shù)的一部分,最優(yōu)值問題轉(zhuǎn)化為
min(\frac{1}{2}\|w\|^2+C\sum_{i=1}^m\eta_i) \\ s.t.\qquad y^{(i)}(w·x^{(i)}+b) >= 1-\eta_i\qquad (\eta_{i} >=0)\\ 特別的,當(dāng)C\to+∞時,soft-margin-SVM會轉(zhuǎn)化為hard-margin-SVM
以上模型成為L1正則,L2正則目標(biāo)表達(dá)式為
min(\frac{1}{2}\|w\|^2+C\sum_{i=1}^{m}\eta_i^2)

Kernel Function(核函數(shù),Kernel Check)

SVM可以視為求解
min(\frac{1}{2}\|w\|^2+C\sum_{i=1}^{m}\eta_i) \\ s.t. \qquad y^{{i}}(w^Tx^{(i)}+b) \ge 1-\eta_i\quad (\eta_i\ge0)
的最優(yōu)化問題,這個問題可以等價于它的對偶問題
max\sum_{i=1}^{m}\alpha_i - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_ix_j \qquad(1)\\ s.t. \qquad 0\le \alpha_i\le C \ and\ \sum_{i=1}^{m}\alpha_iy_j=0
有時分類邊界是非線性的,需要對x,y進(jìn)行某種變形
def\ function\ K:(x,y)\rightarrow (x'y') ,其中x',y'是x,y進(jìn)行某種變形后的結(jié)果
目標(biāo)問題可轉(zhuǎn)化為
max\sum_{i=1}^{m}\alpha_i - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jK(x_i,x_j) \qquad(2)\\ s.t. \qquad 0\le \alpha_i\le C \ and\ \sum_{i=1}^{m}\alpha_iy_j=0

多項式核函數(shù)

最高系數(shù)為2的多項式核函數(shù)為例,
K(x,y)=(x·y+1)^2=(\sum_{i=1}^{n}x_iy_i+1)^2\\=\sum_{i=1}^{n}(x_i^2)(y_i^2)+\sum_{i=2}^{n}\sum_{j=1}^{i-1}(\sqrt2x_ix_j)(\sqrt2y_iy_j)+\sum_{i=1}^{n}(\sqrt2x_i)(\sqrt2y_i)+1=x'·y'\qquad(3)\\ 其中x'=(x_n^2,...,x_1^2,\sqrt2x_nx_{n-1},...,\sqrt2x_n,...,\sqrt2x_1,1),\\y'=(y_n^2,...,y_1^2,\sqrt2y_ny_{n-1},...,\sqrt2y_n,...,\sqrt2y_1,1)
(3)帶入(2)可得
max\sum_{i=1}^{m}\alpha_i - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_j(x_iy_i+1)^2 \qquad(4)\\ s.t. \qquad 0\le \alpha_i\le C \ and\ \sum_{i=1}^{m}\alpha_iy_j=0
將二次核函數(shù)推廣到一般情況,
K_{c,d}(x,y)=(x·y+c)^d
特別地,當(dāng)c=0,d=1時候,多項式核函數(shù)可稱為線性核函數(shù)
K_{0,1}(x,y)=x·y
多項式核函數(shù)可以認(rèn)為是向量點乘推廣到更一般的形式
x·y=K_{0,1}(x,y)=\sum_{i=1}^{m}x_iy_i \\ K_{c,d}(x,y)=(x·y+c)^d

高斯核函數(shù)

高斯分布(正態(tài)分布)\qquad g(x)=\frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{1}{2}(\frac{x-\mu}{\sigma})^2}=\frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{1}{2}(\frac{1}{\sigma})^2({x-\mu})^2}
又稱RBF核(Radial Basis Function Kernel),形態(tài)如下
K_{\gamma}(x,y)=e^{-\gamma\|x-y\|^2}
其中y是每一個數(shù)據(jù)點,即每一個數(shù)據(jù)點都作為landmark
由于和高斯分布的形態(tài)一致,所以得名高斯核函數(shù)
高斯核函數(shù)可以將一個m*n的樣本映射為一個m*m的樣本,是一種維度拓展的方法
\gamma越大,高斯分布越窄,越容易過擬合
\gamma越小,高斯分布越寬,越容易欠擬合
可以認(rèn)為\gamma和模型復(fù)雜度正相關(guān)

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 1. 回顧拉格朗日乘數(shù)法 為了找到曲線上的最低點，就從最低的等高線（0那條）開始網(wǎng)上數(shù)。數(shù)到第三條，等高線終于和曲...
    jiandanjinxin閱讀 2,780評論 0贊 5
  • 本文是scikit-learn 支持向量機的翻譯，原文地址：http://scikit-learn.org/sta...
    學(xué)以致用123閱讀 3,453評論 0贊 4
  • 1、SVM簡介 給定訓(xùn)練樣本集D，分類學(xué)習(xí)最基本的想法就是基于D在樣本空間中找到一個超平面，將不同種類的樣本分開。...
    單調(diào)不減閱讀 2,516評論 0贊 6
  • 本文參考整理了Coursera上由NTU的林軒田講授的《機器學(xué)習(xí)技法》課程的第三章的內(nèi)容，主要介紹了Kernel ...
    sonack閱讀 18,656評論 2贊 10
  • 哈哈
    愛情是故事閱讀 129評論 0贊 0

友情鏈接更多精彩內(nèi)容