支持向量机

分类学习可看成基于训练集在样本空间中找到划分超平面，将不同类别样本分开

间隔与支持向量

alt text

超平面通过线性方程描述：\(w^Tx + b=0\)

样本空间中点x到超平面 \((w,b)\) 的距离：

\(r=\frac{w^Tx+b}{\|w\|}\)

若超平面(w,b)可将训练样本正确分类，即对于 \((x_i,y_i)\in D\)，若\(y_i =+1\)，则有 \(w^Tx_i+b>0\)，若\(y_i=-1\),则 \(w^Tx_i+b<0\)令

\[ \begin{cases} w^Tx_i+b\geq +1, y_i=+1 \\ w^Tx_i+b\leq -1, y_i=-1 \end{cases} \tag{1} \]

alt text

如图，距离超平面最近的样本点可使上述不等式等号成立，其称为“支持向量”，两个异类支持向量到超平面距离之和为

\[ \gamma = \frac{2}{\|w\|} \]

称为“间隔”（margin）。要找到最大间隔的划分超平面，也就是要找到能满足上（1）式约束的w,b，使\gamma最大，即

\[ \max_{w,b}\frac{2}{\|w\|} \]

\[ \text{s.t.} y_i(w^Tx_i+b)\geq 1, i=1,\dots,m \tag{2} \]

等价于最小化 \(\frac{1}{2}\|w\|^2\)

上面（2）式使用拉格朗日乘子法得到：

\[ L(w,b,\alpha) = \frac{1}{2}||{w}||^2+\sum_{i=1}^{m}\alpha_i(1-y_i(w^Tx_i+b)) \]

其中 \(\bf{\alpha}=(\alpha_1,\dots,\alpha_m)\). 令L对w, b的偏导为零代入上式得对偶问题：

\[ \text{max}_\alpha \sum_{i=1}^{m}-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j \]

\[ s.t.\sum_{i=1}^m \alpha_iy_i=0, \alpha_i\geq 0, i=1,2,...,m \tag{3} \]

解出 \(\alpha\) 后，求出 w与b即可得到模型

\[ f(x)=w^Tx+b=\sum_{i=1}^{m}\alpha_i y_i x_i^Tx +b \]

\[ \kappa(x_i, x_j)=\phi(x_i)^T\phi(x_j) \]

现实中, 很难确定合适的核函数使得训练样本在特征空间中线性可分; 同时一个线性可分的结果也难断定是否是有过拟合造成的
以上方法假设数据线性可分，即存在一个超平面能将不同类的样本完全划分开（硬间隔）。软间隔允许某些样本不满足约束 \(y_i(w^Tx+b)\geq 1\)，在最大化间隔的同时，不满足约束对的样本应尽可能少，于是优化目标中引入0/1损失函数。但是其性质不好，用替代损失来代替0/1损失
常见替代损失函数：hinge损失，指数损失，对率损失

alt text