机器学习之支持向量机

线性分类器中主要任务是在样本空间中寻找一个超平面将不同类别的样本分开。
这些超平面有很多，一般来说，”正中间“的泛化性能最强，鲁棒性最好。

间隔与支持向量
划分超平面可描述为：$\omega^Tx+b=0$ωTx+b=0
$\omega=(\omega_1;\omega_2;\cdots;\omega_d)$ω=(ω1​;ω2​;⋯;ωd​)为法向量，决定方向；
$b$b为位移量，决定超平面到原点的距离。
任意点x到超平面$(\omega,b)$(ω,b)的距离为$r=\frac{|\omega^Tx+b|}{||\omega||}$r=∣∣ω∣∣∣ωTx+b∣​
假设超平面分类正确，那么
若$(x_i,y_i)\in D$(xi​,yi​)∈D,$y_i=+1$yi​=+1则$\omega^Tx_i+b>0$ωTxi​+b>0,$y_i=-1$yi​=−1则$\omega^Tx_i+b<0$ωTxi​+b<0；令$\omega^Tx_i+b>=1$ωTxi​+b>=1,$y_i=+1$yi​=+1;$\omega^Tx_i+b<=-1$ωTxi​+b<=−1,$y_i=-1$yi​=−1
距离超平面最近的几个训练样本点使得上式成立，称为支持向量。
两个异类支持向量到超平面的距离之和为$\gamma=\frac{2}{||\omega||}$γ=∣∣ω∣∣2​，称为间隔。

SVM的基本型
找到$\omega$ω和$b$b满足$y_i(\omega^Tx_i+b)>=1$yi​(ωTxi​+b)>=1,$i=1,2,\cdots,m$i=1,2,⋯,m使得间隔$\gamma=\frac{2}{||\omega||}$γ=∣∣ω∣∣2​最大。
这等价于：找到$\omega$ω和$b$b满足$y_i(\omega^Tx_i+b)>=1$yi​(ωTxi​+b)>=1,$i=1,2,\cdots,m$i=1,2,⋯,m使得$\frac{1}{2}{||\omega||}^2$21​∣∣ω∣∣2最小(式1)。

对偶问题
对式1使用拉格朗日乘子法，得到其对偶问题。
#1.$L(\omega,b,\alpha)=\frac{1}{2}||\omega||^2+\sum\limits_{i=1}^{m}\alpha_i(1-y_i(\omega^Tx_i+b))$L(ω,b,α)=21​∣∣ω∣∣2+i=1∑m​αi​(1−yi​(ωTxi​+b))
#2.令$L(\omega,b,\alpha)$L(ω,b,α)对$\omega$ω和b的偏导等于零，即得：$\omega=\sum\limits_{i=1}^{m}\alpha_iy_ix_i$ω=i=1∑m​αi​yi​xi​ $\sum\limits^{m}_{i=1}\alpha_iy_i=0(*)$i=1∑m​αi​yi​=0(∗) #3.代回即得：$L(\omega,b,\alpha)=\sum\limits_{i=1}^{m}\alpha_i-\frac{1}{2}\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j$L(ω,b,α)=i=1∑m​αi​−21​i=1∑m​j=1∑m​αi​αj​yi​yj​xiT​xj​ #4.考虑(*)处约束，即得式1的对偶问题：$\max\limits_{\alpha}\,\,\,\,\,\,\,\sum\limits_{i=1}^{m}\alpha_i-\frac{1}{2}\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j$αmax​i=1∑m​αi​−21​i=1∑m​j=1∑m​αi​αj​yi​yj​xiT​xj​s.t.$\sum\limits^{m}_{i=1}\alpha_iy_i=0(*)$i=1∑m​αi​yi​=0(∗)$\alpha_i>=0$αi​>=0.

解的稀疏性
求出$\alpha$α后即得最终模型：
$f(x)=\omega^Tx+b=\sum\limits^{m}_{i=1}\alpha_iy_ix_i^Tx+b$f(x)=ωTx+b=i=1∑m​αi​yi​xiT​x+b
KKT条件：$\left\{\begin{matrix} \alpha_i>=0\\ y_if(x_i)>=1\\\alpha_i(1-y_if(x_i))=0 \end{matrix}\right.$⎩⎨⎧​αi​>=0yi​f(xi​)>=1αi​(1−yi​f(xi​))=0​
即必有：$\alpha_i=0$αi​=0或者$y_if(x_i)=1$yi​f(xi​)=1
由此体现解的稀疏性：训练完成后，最终模型只与支持向量有关。

特征空间映射
不存在一个超平面能将两类样本正确划分时，可将样本从原始空间映射到更高维度的特征空间，使得样本在这个特征空间内线性可分。
设样本$x$x映射后的向量为$\phi(x)$ϕ(x)，划分超平面为：
$f(x)=\omega^T\phi(x)+b$f(x)=ωTϕ(x)+b
原始问题：找到$\omega$ω和$b$b满足$y_i(\omega^T\phi(x_i)+b)>=1$yi​(ωTϕ(xi​)+b)>=1,$i=1,2,\cdots,m$i=1,2,⋯,m使得$\frac{1}{2}{||\omega||}^2$21​∣∣ω∣∣2最小
对偶问题：$\max\limits_{\alpha}\,\,\,\,\,\,\,\sum\limits_{i=1}^{m}\alpha_i-\frac{1}{2}\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{m}\alpha_i\alpha_jy_iy_j\phi(x_i)^T\phi(x_j)$αmax​i=1∑m​αi​−21​i=1∑m​j=1∑m​αi​αj​yi​yj​ϕ(xi​)Tϕ(xj​)s.t.$\sum\limits^{m}_{i=1}\alpha_iy_i=0(*)$i=1∑m​αi​yi​=0(∗)$\alpha_i>=0$αi​>=0.
预测模型： $f(x)=\omega^T\phi(x)+b=\sum\limits^{m}_{i=1}\alpha_iy_i\phi(x_i)^T\phi(x)+b$f(x)=ωTϕ(x)+b=i=1∑m​αi​yi​ϕ(xi​)Tϕ(x)+b

核函数
设计核函数$k(x_i,x_j)=\phi(x_i)^T\phi(x_j)$k(xi​,xj​)=ϕ(xi​)Tϕ(xj​)解决内积$\phi(x_i)^T\phi(x_j)$ϕ(xi​)Tϕ(xj​)因维度过高计算困难的问题。
只要一个对称函数对应的矩阵半正定，这个函数就能作为核函数使用。
常用核函数：文本数据常用线性核，情况不明时先尝试高斯核。
若$k_1(x_i,x_j)$k1​(xi​,xj​),$k_1(x_i,x_j)$k1​(xi​,xj​)均为核函数，那么对任意正数$\gamma_1$γ1​、$\gamma_1$γ1​和任意函数$g(x)$g(x)：$\gamma_1k_1(x_i,x_j)+\gamma_2k_2(x_i,x_j)$γ1​k1​(xi​,xj​)+γ2​k2​(xi​,xj​)、$k_1(x_i,x_j)k_1(x_i,x_j)$k1​(xi​,xj​)k1​(xi​,xj​)、$k(x_i,x_j)=g(x_i)k_1(x_i,x_j)g(x_j))$k(xi​,xj​)=g(xi​)k1​(xi​,xj​)g(xj​))均为核函数。

软间隔
允许在一些样本上不满足约束
优化目标：在最大化间隔的同时，让不满足约束$y_i(\omega^Tx_i+b)>=1$yi​(ωTxi​+b)>=1的样本数尽可能少。
$\min\limits_{\omega,b}\,\,\,\,\,\frac{1}{2}||\omega||^2+C\sum\limits_{i=1}^{m}l_{0/1}(y_i(\omega^Tx_i+b)-1)$ω,bmin​21​∣∣ω∣∣2+Ci=1∑m​l0/1​(yi​(ωTxi​+b)−1)
其中，$l_{0/1}(z)=\left\{\begin{matrix} 1\,\,\,if\,z<0\\ 0\,\,\,else \end{matrix}\right.$l0/1​(z)={1ifz<00else​
非凸、不连续、不易优化
替代损失函数：$l_{hinge}(z)=max(0,1-z)$lhinge​(z)=max(0,1−z)、$l_{exp}(z)=exp(-z)$lexp​(z)=exp(−z)、$l_{log}(z)=log(1+exp(-z))$llog​(z)=log(1+exp(−z))
替代损失的一致性问题讨论：
原始问题：$\min\limits_{\omega,b}\,\,\,\,\,\frac{1}{2}||\omega||^2+C\sum\limits_{i=1}^{m}max(0,1-y_i(\omega^Tx_i+b))$ω,bmin​21​∣∣ω∣∣2+Ci=1∑m​max(0,1−yi​(ωTxi​+b))
引入松弛变量$\xi_i$ξi​:$\min\limits_{\omega,b}\,\,\,\,\,\frac{1}{2}||\omega||^2+C\sum\limits_{i=1}^{m}\xi_i$ω,bmin​21​∣∣ω∣∣2+Ci=1∑m​ξi​,
s.t.$y_i(\omega^Tx_i+b)>=1-\xi_i$yi​(ωTxi​+b)>=1−ξi​$\xi_i>=0$ξi​>=0
对偶问题：$\max\limits_{\alpha}\,\,\,\,\,\,\,\sum\limits_{i=1}^{m}\alpha_i-\frac{1}{2}\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j$αmax​i=1∑m​αi​−21​i=1∑m​j=1∑m​αi​αj​yi​yj​xiT​xj​s.t.$\sum\limits^{m}_{i=1}\alpha_iy_i=0$i=1∑m​αi​yi​=0$0\leq\alpha_i<=C$0≤αi​<=C.
最终模型仍只与支持向量有关。

支持向量回归(SVR)
基本思路：允许模型输出与实际输出存在$2\epsilon$2ϵ的差别。
使用 $\epsilon$ϵ不敏感损失函数： $l_\epsilon(z)=\left\{\begin{matrix} 0\,\,\,if\,z\leq|\epsilon|\\ |z|-\epsilon\,\,\,else \end{matrix}\right.$lϵ​(z)={0ifz≤∣ϵ∣∣z∣−ϵelse​，表示落入$2\epsilon$2ϵ间隔段内的数据不计算损失。
原始问题：$\min\limits_{\omega,b,\xi_i,\hat{\xi_i}}\,\,\frac{1}{2}||\omega||^2+C\sum\limits_{i=1}^{m}(\xi_i+\hat{\xi_i})$ω,b,ξi​,ξi​^​min​21​∣∣ω∣∣2+Ci=1∑m​(ξi​+ξi​^​),s.t.$f(x_i)-y_i\leq\xi_i+\epsilon$f(xi​)−yi​≤ξi​+ϵ$y_i-f(x_i)\leq\hat{\xi_i}+\epsilon$yi​−f(xi​)≤ξi​^​+ϵ$\xi_i>=0$ξi​>=0$\hat{\xi_i}>=0$ξi​^​>=0
对偶问题：

KKT条件：

最终模型：
$f(x)=\sum\limits_{i=1}^{m}(\hat{\alpha_i}-\alpha_i)x_i^Tx+b$f(x)=i=1∑m​(αi​^​−αi​)xiT​x+b
在求得$\alpha_i$αi​后，根据KKT条件，当$C-\alpha_i\neq 0$C−αi​​=0时，利用$\alpha_i(f(x_i)-y_i-\epsilon)=0$αi​(f(xi​)−yi​−ϵ)=0求出$b$b。更鲁棒的方法是找到所以$0=<\alpha_i\leq C$0=<αi​≤C的$\alpha_i$αi​求出b后取平均值。

核方法
表示定理：
最常见的核方法是通过引入核函数（核化）将线性学习器拓展为非线性学习器。