模型

在线性空间划分超平面可通过如下方程描述：
$w^Tx+b=0\tag{1}$wTx+b=0(1)
其中$w=(w_1,w_2,\cdots,w_d)$w=(w1​,w2​,⋯,wd​)为法向量，决定了超平面的方向；$b$b为位移项，决定了超平面与原点之间的距离。显然，划分超平面可被$w,b$w,b确定，记为$(w,b)$(w,b)，样本空间中任意点$x$x到超平面$(w,b)$(w,b)的距离可写为
$r=\frac{|w^T+b|}{||w||}\tag{2}$r=∣∣w∣∣∣wT+b∣​(2)
假设超平面$(w,b)$(w,b)能将训练样本正确分类，即对于$(x_i,y_i)\in D$(xi​,yi​)∈D（其中$D=\{(x_1,y_1),(x_2,y_2),\cdots,(x_m,y_m)\},y_i \in\{-1,+1\}$D={(x1​,y1​),(x2​,y2​),⋯,(xm​,ym​)},yi​∈{−1,+1}），若$y_i=+1$yi​=+1，则有$w^Tx_i+b>0$wTxi​+b>0；若$y_i=-1$yi​=−1，则有$w^Tx_i+b<0$wTxi​+b<0。此时可令（如果超平面能将样本正确分类，总存在缩放变量使得(3)式成立）
$\begin{cases} w^Tx_i+b\geq+1, & y_i=+1\\ w^Tx_i+b\leq-1, & y_i=-1\\ \end{cases}\tag{3}${wTxi​+b≥+1,wTxi​+b≤−1,​yi​=+1yi​=−1​(3)
如下图所示，距离超平面最近的这几个训练样本点使得（3）式的等号成立，它们被称为“支持向量”，两个异类支持向量到超平面的距离之和为
$\gamma=\frac{2}{||w||}\tag{4}$γ=∣∣w∣∣2​(4)
它被称为“间隔”

欲找到具有“最大间隔”的划分超平面，也就是要找到能满足（3）式约束的参数$w,b$w,b使得$\gamma$γ最大，即
$\underset{w,b}{max}\quad \frac{2}{||w||}\\ \quad \\ s.t.\quad y_i(w^Tx_i+b)\geq1,i=1,2,\cdots,m. \tag{5}$w,bmax​∣∣w∣∣2​s.t.yi​(wTxi​+b)≥1,i=1,2,⋯,m.(5)
为了最大化间隔，仅需最大化$||w||^{-1}$∣∣w∣∣−1，这等价于最小化$||w||^2$∣∣w∣∣2，于是（5）式可重写为
$\underset{w,b}{max}\quad \frac{1}{2}||w||^2\\ \quad \\ s.t.\quad y_i(w^Tx_i+b)\geq1,i=1,2,\cdots,m. \tag{6}$w,bmax​21​∣∣w∣∣2s.t.yi​(wTxi​+b)≥1,i=1,2,⋯,m.(6)
这就是SVM的基本型。

求解

• 对偶问题
  对（6）式的每条约束添加拉格朗日乘子$\alpha_i\geq0$αi​≥0，则该问题的拉格朗日函数可写为
  $L(w,b,\alpha)=\frac{1}{2}||w||^2+\sum^{m}_{i=1}\alpha_i(1-y_i(w^Tx_i+b))\tag{7}$L(w,b,α)=21​∣∣w∣∣2+i=1∑m​αi​(1−yi​(wTxi​+b))(7)
  即我们的目标函数可表示为
  $\underset{w,b}{min}\underset{\alpha}{max}\quad L(w,b,\alpha)\tag{8}$w,bmin​αmax​L(w,b,α)(8)
  满足一定条件下，等价于（注意，这个满足一定条件，是指满足KKT条件）
  $\underset{\alpha}{max}\underset{w,b}{min}\quad L(w,b,\alpha)\tag{9}$αmax​w,bmin​L(w,b,α)(9)
  于是我们的整个问题转化为
  1.$L(w,b,\alpha)$L(w,b,α)对$w,b$w,b求最小
  2.再对$\alpha$α 求最大。
  至于第一步，令$L(w,b,\alpha)$L(w,b,α)对$w,b$w,b求偏导为0可得
  $w=\sum^{m}_{i=1}\alpha_iy_ix_i\tag{10}$w=i=1∑m​αi​yi​xi​(10)
  $0=\sum^{m}_{i=1}\alpha_iy_i\tag{11}$0=i=1∑m​αi​yi​(11)
  将（10）（11）式带入（7）式，即可将$w,b$w,b消去，便可得到（6）式的对偶式
  $\underset{\alpha}{max}\quad \sum^{m}_{i=1}\alpha_i-\frac{1}{2}\sum^{m}_{i=1}\sum^{m}_{j=1}\alpha_i\alpha_jy_iy_jx_i^Tx_j\\ s.t.\quad \sum^{m}_{i=1}\alpha_iy_i=0,\\ \alpha_i\geq0,\quad i=1,2,\cdots,m.\tag{12}$αmax​i=1∑m​αi​−21​i=1∑m​j=1∑m​αi​αj​yi​yj​xiT​xj​s.t.i=1∑m​αi​yi​=0,αi​≥0,i=1,2,⋯,m.(12)
• KKT条件
  以上转换过程中的KKT条件为
  $\begin{cases} \alpha_i\geq0\\ y_if(x_i)-1\geq0\\ \alpha_i(y_if(x_i)-1)=0\\ \end{cases}\tag{13}$⎩⎪⎨⎪⎧​αi​≥0yi​f(xi​)−1≥0αi​(yi​f(xi​)−1)=0​(13)
  于是，对任意训练样本$(x_i,y_i)$(xi​,yi​)，总有$\alpha_i=0$αi​=0或$y_if(x_i)=1$yi​f(xi​)=1。若$\alpha_i=0$αi​=0，则该样本将不会对$f(x)$f(x)有任何影响；若$\alpha_i>0$αi​>0，则必有$y_if(x_i)=1$yi​f(xi​)=1，则所对应的样本点位于最大间隔边界上，是一个支持向量。
  以上显示了SVM的一个重要性质：训练完成后，大部分的训练样本都不需要保留，最终模型仅与支持向量有关。
• SMO

核函数

与LR对比

参考：
机器学习（西瓜书）
https://blog.csdn.net/b285795298/article/details/81977271