brief introduction
information
支持向量机（Support Vector Machine，以下简称SVM），是一个二元分类（ dualistic classification）的广义线性分类器（generalized linear classifier），通过寻找分离超平面作为决策边界（decision boundary），分离少量的支持向量（support vector），从而达到分类目的([1][2][3])。
可采用一对一（One Versus One）、一对多（One Versus Rest）等策略转变为多分类问题([6])。
原问题（primal problem）仅支持硬间隔最大化（hard margin maximum），添加松弛变量（slack variable）后支持软间隔最大化（soft margin maximum）。
details
属性：稀疏性和稳健性（Robust）([1])、非参数模型（nonparametric models）、监督学习（supervised learning）、判别模型（discriminant model）、【KKT条件（Karush-Kuhn-Tucker condition）约束，对偶形式（dual form）转换，序列最小优化（Sequential Minimal Optimization，以下简称为SMO）算法求解([1][4][5])】、支持核方法（kernel method）。
求解：使用门页损失函数（hinge loss function）计算经验风险（empirical risk）并在求解时加入了正则化项以优化结构风险（structural risk），1.直接进行二次规划（Quadratic Programming）求解；2.利用拉格朗日算子（ Lagrange multipliers），将其转为，符合KKT条件（Karush-Kuhn-Tucker condition）的对偶形式（dual form），再进行二次规划（Quadratic Programming）求解([1])。
扩展：利用正则化、概率学、结构化、核方法改进算法，包括偏斜数据、概率SVM、最小二乘SVM（Least Square SVM, LS-SVM）、结构化SVM（structured SVM）、多核SVM（multiple kernel SVM）；也可扩充到回归（Support Vector Regression）、聚类、半监督学习（Semi-Supervised SVM, S3VM）。
problems
- generalized formula:
- 间隔距离（support vector distance）：最优解时，值等于(frac{2}{| w |});
- 分割线-原点垂直距离： 最优解时，值等于(frac{b}{| w |});
- 简单推导：
-
[color{black}{s\,v\,distance\,:} egin{aligned} &egin{cases} W^{ m{T}}x_i^++b=1\ W^{ m{T}}x_i+b=0\ W^{ m{T}}x_i^-+b=-1\ end{cases} \ &downarrow \ &egin{cases} W^{ m{T}}(x_i-x_j)= 0 & ightarrow Wot (x_i-x_j)\ W| (x^+-x^-) & ightarrow x^+=x^-+lambda W\ W^{ m{T}}x^++b=1 & ightarrow lambda W^{ m{T}}W=2, \,|lambda| =frac{2}{|W^{ m{T}}W|}\ end{cases} \ &downarrow \ &maximize;|x^+-x^-| \ & ightarrow |x^+-x^-| = |lambda W|=frac{2}{|W|} end{aligned}]
-
primal problem
当样本数据集线性可分（linear separable）时，寻找正负样本中各自距离对方最近的样本数据（称为支持向量，即SVM的名字由来）（一般为三个），利用相对位置（排除坐标缩放影响，也是采用几何间隔的原因），构建最大间隔（几何间隔）进行分类[3]。
[from:greedyai.com ]
如图，当硬间隔最大化时，正类支持向量（positive support vector）（图中(x_1)）与负类支持向量（negative support vector）（图中(x_2, x_3)）使
- 约束条件：(y_i(W^{ op}x_i+b)geq 1)
- 经验风险函数（Hinge loss）：([1-y_i(W^{ op}x_i+b)]_+)
- 目标函数：(min_{(w,b)}\,frac{1}{2}|W|^2)
- 预测：(h(x)=sign(W^{ op}x+b))
(sign)表示符号函数，即计算括号内的值，值为正数则取正类别，反之亦然。
（求解推导请查看下方dual problem内容）
multi-class
- 多元分类（类似于LR多标签分类的策略）（(C_k^2>k,;when;k>3)）
- OVR（one versus rest）：k元分类问题，训练(k)个模型，每个模型二分类为某个类和非该类，预测时选择(max_i\,w_i^{ m{T}}x;)为(x)的类别
- OVO（one versus one）：k元分类问题，训练(C_k^2)个模型，每个模型二分类为k元中二元组合，预测时选择计票次数最多的(i)为(x)的类别
slack problem
硬间隔最大化无法满足实际条件中，异常值间隔、线性不可分等情况，因此引入软间隔（soft margin）方式： 在原问题基础上，添加松弛变量（slack variable），增加容错率。
[from:greedyai.com ]
- 约束条件：(egin{aligned} &y_i(W^{ m{T}}x_i+b)geq 1color{red}{-xi_i} end{aligned})
- 经验风险函数（Hinge loss）：[egin{aligned} y_i(W^{ m{T}}x+b)geq 1-{color{red}{xi_i}} ightarrow &egin{cases} {color{red}{xi_i}}geq 1-y_i(W^{ m{T}}x+b) \ {color{red}{xi_i}}geq 0 end{cases}\ &downarrow \ {color{red}{xi_i}}=&[1-y_i(W^{ m{T}}x+b)]_+ end{aligned}]
- 目标函数：(min_{(w,b,color{red}{xigeq 0})}\,frac{1}{2}|W|^2+color{red}{Csum_{i}xi_i} \)
- 预测：(h(x)=sign(W^{ op}X+b))
（求解推导请查看下方dual problem内容）
Duality
- 原问题转为对偶形式再求解的好处：([9])
- 把约束条件和待优化目标融合在一个表达式，便于求解；
- 对偶问题一般是凹函数，便于求全局最优解（global optimal）；
- 对偶形式，便于引入核技巧；
KKT condition
-
成立条件：
- (f(W)=W^{ m{T}}W) is convex,
- (egin{cases}g_i(W)\h_i(W)=alpha_i^{ m{T}}W+bend{cases}) is affine,
- (exists W,\,forall_i g_i(W)<0),
-
内容（具体问题中有不同表现形式）：
[egin{cases} frac{partial }{partial w_i}L(w^star,alpha^star,eta^star)=0 & i=1,dots,d \ frac{partial }{partial eta_i}L(w^star,alpha^star,eta^star)=0 & i=1,dots,l \ {color{red}{alpha^star g_i(w^star)=0}}& i=1,dots,k\ g_i(w^star)leq 0 & i=1,dots,k \ alpha^star geq 0 & i=1,dots,k \ end{cases} ightarrow alpha^star>0, g_i(w^star)=0 ]
留意(alpha^star>0, g_i(w^star)=0)，即非支持向量的样本令(g_i(w^star) eq 0)，可得(alpha^star=0)；
dual form normal processing
-
原优化问题：
[egin{align} &min_w;f(w) \ s.t. &g_i(w)leq 0 \ &h_i(w)=0 end{align} ] -
拉格朗日函数（添加(alpha,eta)算子）：
[egin{align} &{cal{L}(w,alpha,eta)}= f(w)+ sum_{i=1}^kalpha_ig_i(w)+ sum_{i=1}^leta_ih_i(w) end{align} ]- 约束情况：[egin{align} heta_{cal{p}}(w) &= max_{alpha,eta:alpha_igeq0} {cal{L}}(w,alpha,eta) \ &= egin{cases} f(w)&约束被满足\ infty&约束未满足 end{cases} end{align} ]
- 约束情况：
dual form transformation
primal to dual
(from greedyai.com)
- 已知： 原问题数学模型
-
改造：符合对偶形式一般流程（dual form normal processing）
[egin{align} g_i(w)= -y_i(W^{ op}x_i+b)+1 leq 0 end{align} ] -
转换：拉格朗日函数
[egin{align} {cal{L}(w,alpha,eta)} &= f(w) + sum_{i=1}^kalpha_ig_i(w)+ sum_{i=1}^leta_ih_i(w) \ &=frac{1}{2}|W|^2- sum_{i=1}^nalpha_i[y_i(W^{ op}x_i+b)-1] end{align} ] -
去除：未知值(w,b)求解
[egin{align} ]
&=
abla_wlarge[frac{1}{2}|W|^2-
sum_{i=1}^nalpha_i[y_i(W^{ op}x_i+b)-1]large]
&=w-sum_{i=1}^nalpha_iy_ix_i
{color{red}{
ightarrow0}}
ightarrow w
&=sum_{i=1}^nalpha_iy_ix_i
ag{3.1}
abla_b{cal{L}(w,b,alpha,eta)}
&=
abla_blarge[frac{1}{2}|W|^2-
sum_{i=1}^nalpha_i[y_i(W^{ op}x_i+b)-1]large]
&=sum_{i=1}^nalpha_iy_i
{color{red}{
ightarrow0}}
ag{3.2}
end{align}
egin{align}
{cal{L}(w,b,alpha,eta)}
&=
frac{1}{2}[sum_{i=1}^nalpha_iy_ix_i]^2-
sum_{i=1}^nalpha_i[y_i(sum_{i=1}^nalpha_jy_jx_ix_j+b)-1]
&=
frac{1}{2}sum_{i=1}^nalpha_ialpha_jy_iy_jx_ix_j-
sum_{i,j=1}^nalpha_ialpha_jy_iy_jx_ix_j-bsum_{i=1}^nalpha_iy_i+
sum_{i=1}^nalpha_i
&=
-frac{1}{2}sum_{i=1}^nalpha_ialpha_jy_iy_jx_ix_j-
0+
sum_{i=1}^nalpha_i
&=
sum_{i=1}^nalpha_i-frac{1}{2}sum_{i=1}^nalpha_ialpha_jy_iy_jx_ix_j
ag{3.3}
end{align}
egin{align}
max_alpha;W(alpha)
&=
sum_{i=1}^nalpha_i-frac{1}{2}sum_{i=1}^nalpha_ialpha_jy_iy_jx_ix_j
s.t.;
&alpha_igeq 0
&sum_{i=1}^nalpha_iy_i=0
end{align}
egin{align}
b=-frac{1}{2}
(max_{i:y_i=-1}W^ op x_i+min_{i:y=1}W^ op x_i)
end{align}
egin{align}
f(w)
&=
W^ op x+b
&=(sum_{i=1}^nalpha_iy_ix_i)x-
frac{1}{2}
(max_{i:y_i=-1}W^ op x_i+min_{i:y=1}W^ op x_i)
end{align}
egin{cases}
&alpha_i&=&0 &Rightarrow
&y_i(W^{
m{T}}x+b) &geq 1
&alpha_i&>&0 &Rightarrow
&y_i(W^{
m{T}}x+b)&= 1
end{cases}
egin{align}
&min_{(w,b,color{red}{xigeq 0})},frac{1}{2}|W|^2+color{red}{Csum_{i}xi_i}
s.t.
&y_i(W^{
m{T}}x_i+b)geq 1color{red}{-xi_i}
end{align}
egin{align}
g_i(w)=
-y_i(W^{ op}x_i+b)+1{color{red}{-xi_i}}
leq 0
end{align}
egin{align}
{cal{L}(w,alpha,eta)}
&=
f(w) +
sum_{i=1}^kalpha_ig_i(w)+
sum_{i=1}^leta_ih_i(w)
&=frac{1}{2}|W|^2+{color{red}{Csum_{i}xi_i}}-
sum_{i=1}^nalpha_i[y_i(W^{ op}x_i+b)-1{color{red}{+xi_i}}]
end{align}
egin{align}
abla_w{cal{L}(w,b,xi,alpha,eta)}
&=w-sum_{i=1}^nalpha_iy_ix_i
{color{red}{
ightarrow0}}
ightarrow w
&=sum_{i=1}^nalpha_iy_ix_i
ag{3.4}
abla_b{cal{L}(w,b,xi,alpha,eta)}
&=sum_{i=1}^nalpha_iy_i
{color{red}{
ightarrow0}}
ag{3.5}
abla_xi{cal{L}(w,b,xi,alpha,eta)}
&=
abla_xilarge[frac{1}{2}|W|^2+color{red}{Csum_{i}xi_i}
&qquad -sum_{i=1}^nalpha_i[y_i(W^{ op}x_i+b)-1+{color{red}{xi_i}}]
&qquad -sum_i lambda_i{color{red}{xi_i}}large]
&=0+sum_iC-sum_{i=1}^nalpha_i-sum_ilambda_i
{color{red}{
ightarrow0}}
ightarrow C&=alpha_i+lambda_i
ag{3.6}
end{align}
egin{align}
{cal{L}(w,b,xi,alpha,eta)}
&=
large[frac{1}{2}|W|^2+color{red}{Csum_{i}xi_i}
&qquad -sum_{i=1}^nalpha_i[y_i(W^{ op}x_i+b)-1+{color{red}{xi_i}}]
&qquad -sum_i lambda_i{color{red}{xi_i}}large]
&=
frac{1}{2}sum_{i=1}^nalpha_ialpha_jy_iy_jx_ix_j+(alpha_i+lambda_i)sum_i{color{red}{xi_i}}
&qquad -sum_{i,j=1}^nalpha_ialpha_jy_iy_jx_ix_j-bsum_{i=1}^nalpha_iy_i+
sum_{i=1}^nalpha_i (1-{color{red}{xi_i}})
&qquad -sum_ilambda_icolor{red}{xi_i}
&=
-frac{1}{2}sum_{i=1}^nalpha_ialpha_jy_iy_jx_ix_j-
0+
sum_{i=1}^nalpha_i +
0sum_icolor{red}{xi_i}
&=
sum_{i=1}^nalpha_i-frac{1}{2}sum_{i=1}^nalpha_ialpha_jy_iy_jx_ix_j
ag{3.7}
end{align}
egin{align}
max_{alpha};W(alpha)
&=
sum_{i=1}^nalpha_i-frac{1}{2}sum_{i=1}^nalpha_ialpha_jy_iy_jx_ix_j
s.t.;
&alpha_igeq 0
&sum_{i=1}^nalpha_iy_i=0
&{color{red}{alpha_ileq C}}
end{align}
egin{cases}&alpha_i&=&0 &Rightarrow &y_i(W^{ m{T}}x+b) &geq 1 &alpha_i&=&C &Rightarrow &y_i(W^{ m{T}}x+b)&leq 1 &<&alpha_i&<C&Rightarrow &y_i(W^{ m{T}}x+b)&= 1 \end{cases}
egin{align}
max_{alpha};W(alpha)
&=
sum_{i=1}^nalpha_i-frac{1}{2}sum_{i=1}^nalpha_ialpha_j
{color{blue}{y_iy_j}}{color{green}{x_ix_j}}
s.t.;
&alpha_igeq 0
&sum_{i=1}^n{color{orange}{alpha_iy_i}}=0
&Cgeq alpha_i
end{align}
egin{align}
max &egin{cases}
-{color{blue}{y_iy_j}}:;
两样本标签同类，值减少 & 阻碍max
-{color{green}{x_ix_j}}:;
两样本数据相似，值减少 & 阻碍max
-{color{blue}{y_iy_j}}{color{green}{x_ix_j}}:;
两样本内在逻辑类似，值减少 & 阻碍max
end{cases}
sum_{i=1}^n &egin{cases}
{color{orange}{alpha_iy_i}}:;
不同类标签各自加和，绝对值相等
end{cases}
end{align}
|x_n^k-x_0^k|leq varepsilon
egin{align}
&k={cal{K}}(i,i)+{cal{K}}(j,j)-2{cal{K}}(i,j) ;
,s.t.,k>0
end{align}
egin{align}
&alpha_j^{new}=
egin{cases}
U & min
alpha_j^{old}+frac{y(E_j-E_i)}{k} & alpha
V & max
end{cases}
&alpha_i^{new}=alpha_i^{old}+y_iy_j(alpha_j^{old}-alpha_j^{new})
s.t.&;Uleq alpha_jleq V
&
define&;egin{cases}
E_m=sum_{l=1}^n[alpha_jy_lK(l,m)]+b-y_m
U=
egin{cases}
max(0,alpha_j^{old}-alpha_i^{old}) &y_i
eq y_j
max(0,alpha_j^{old}+alpha_i^{old}-C) &y_i= y_j
end{cases}
V=
egin{cases}
min(0,alpha_j^{old}-alpha_i^{old})+C &y_i
eq y_j
min(C,alpha_j^{old}+alpha_i^{old}) &y_i= y_j
end{cases}
end{cases}
end{align}
egin{align}
b=&(b_x+b_y)/2,;;init;0
b_x&=b-E_{color{blue}{i}}
&qquad-y_i(alpha_i^{new}-alpha_i^{old}){cal{K}}(i,{color{blue}{i}})
&qquad-y_i(alpha_j^{new}-alpha_j^{old}){cal{K}}({color{blue}{i}},j),;;0<alpha_{color{blue}{i}}^{new}<C
b_y&=b-E_{color{green}{j}}
&qquad-y_i(alpha_i^{new}-alpha_i^{old}){cal{K}}(i,{color{green}{j}})
&qquad-y_i(alpha_j^{new}-alpha_j^{old}){cal{K}}({color{green}{j}},j),;;0<alpha_{color{green}{j}}^{new}<C\
end{align}
egin{align}
&{cal{K}}(x_i,x_j)=
({large<}x_i,x_j{large>}+c)^d \
end{align}
$$
-
Gaussian Kernel(need:feature standardization)
[egin{align} &{cal{K}}(x_i,x_j)= exp(-frac{|x_i-x_j|_2^2}{2sigma^2}) \ &qquadegin{cases} lower;bias&low;sigma^2\ lower;variance&high;sigma^2\ end{cases} end{align} ] -
Sigmoid Kernel(equal:NN without hidden layer)
[egin{align} &{cal{K}}(x_i,x_j)= anh(alpha{large<}x_i,x_j{large>}+c) \ end{align} ] -
Cosine Similarity Kernel(used:text similarity)
[egin{align} &{cal{K}}(x_i,x_j)= frac{{large<}x_i,x_j{large>}} {|x_i||x_j|} \ end{align} ] -
Chi-squared Kernel
[egin{align} SVM:;&{cal{K}}(x_i,x_j)= 1-sum_{i=1}^n{frac{(x_i-y_i)^2}{0.5(x_i+y_i)}}\ rest:;&{cal{K}}(x_i,x_j)= sum_{i=1}^n{frac{2x_iy_i}{x_i+y_i}} \ end{align} ] -
Kerel condition
[egin{align} gram;&G_{i,j} egin{cases} symmetric \ pos-difi\ end{cases}\ define: &G_{i,j}={cal{K}}(x_i. x_j)\ end{align} ]
kernel svm
-
直观模型
[egin{align} &{color{gray}{max_{alpha};W(alpha)= sum_{i=1}^nalpha_i-frac{1}{2}sum_{i=1}^nalpha_ialpha_jy_iy_j}}{color{red}{x_ix_j}} \ &{color{black}{max_{alpha};W(alpha)= sum_{i=1}^nalpha_i-frac{1}{2}sum_{i=1}^nalpha_ialpha_jy_iy_j}}{color{blue}{cal{K}(x_i,x_j)}} \ &s.t.; 0leq alpha_ileq C,;sum_{i=1}^nalpha_iy_i=0 \ &define:; {cal{K}(x_i,x_j)}= large<varPhi(x_i),varPhi(x_j)large>\ end{align} ] -
kernel trick
-
关于正定核({cal{K}_i})的函数可以转为关于另一个正定核({cal{K}_j})的函数
-
预测：
[egin{align} {color{gray}{h(x)}} &{color{gray}{=sign(W^{ op}X+b)}} \ h(x) &=sign(W^ opvarPhi(X)+b) \ &=sign(sum_ialpha_iy_i{cal{K}}(x_i,x)+b) end{align} ] -
高维映射（核空间定义可参看B站-3Blue1Brown-微积分的本质）
[egin{align} polynomial;kernel&(c=0,d=2):\ &{cal{K}}(x_i,x_j)= ({large<}x_i,x_j{large>}+0)^2\ &qquadqquad={large<}varPhi(x_i),varPhi(x_j){large>}\ &egin{cases} varPhi(x_i)=[x_{i1}^2,x_{i2}^2,sqrt{2}x_{i1}x_{i2}] \ varPhi(x_j)= [x_{j1}^2,x_{j2}^2,sqrt{2}x_{j1}x_{j2}] \ end{cases}\ end{align} ]
-
-
kernel & basis expansion(compared)
-
Oxford-Basis Expansion, Regularization, Validation, SNU-Basis expansions and Kernel methods,
-
类似：使用创建多项式方法创建新特征，都可用于线性分类（线性核），都能升维
-
不同：feature map不同（(varPhi(x))），存在非线性核
-
模型：
[egin{align} linear;model: &y=w{cdot}varPhi(x)+epsilon\ basis: &egin{cases} varPhi(x)=[1,x_1,x_2,x_1x_2,x_1^2,x_2^2], D^dfeatures \ define:;D\,dimension,;d\,polynomials\ end{cases}\ kernel: &egin{cases} varPhi(x)={cal{K}}(x_1,x_2) ={large<}x_1,x_2{large>},;2;features\ varPhi(x)=[1,{cal{K}}(mu_i,x)],mu\,is\,centre, ;i\,features\ end{cases}\ end{align} ]
-
#.reference links
重点推荐([5][6][10])：
- [1].百度百科，支持向量机；
- [2].简书，作者：刘敬，支持向量机(SVM) 浅析；
- [3].CSDN，作者：于建民，浅析支持向量机SVM；
- [4].百度文库，未知作者，SVM算法学习（PPT）；
- [5].CSDN，作者：zouxy09，机器学习算法与Python实践之（四）支持向量机（SVM）实现；
- [6].CSDN，作者：zouxy09，机器学习算法与Python实践之（三）支持向量机（SVM）进阶；
- [7].CSDN，作者：勿在浮砂筑高台，【机器学习详解】SMO算法剖析；
- [8].CSDN，作者：qll125596718，SVM学习（五）：松弛变量与惩罚因子;
- [9].CSDN，作者：Dominic_S，手撕SVM公式——硬间隔、软间隔、核技巧；
- [10].私人网站，作者：pluskid，支持向量机: Support Vector 2；