关于SVM的补充

本文参考周志华《机器学习》（西瓜书）进行整理。整理的内容包括支持向量机(Support Vector Machine)以及相关的回归方法，补充介绍核方法。

本文并不具体介绍SVM的求解算法。

SVM基本原理

问题描述

给定样本集：$D={{\textbf{X},\textbf y}}$。其中，$\textbf{X}={\textbf{x}i}{i=1}^m\in\real^{m\times d}$，$\textbf y\in{-1,+1}^{m\times 1}$，把样本用决策面 ($\textbf{w}^{\rm T}\textbf{x}+b=0$) 分成两类，问题的目的是找到最合适的$\textbf{w}$，使得两类样本能够明显地分开。

SVM要求$y=-1$和$y=+1$两类样本能够以一定间隔分开，即当$y=-1$时，$\textbf{w}^{\rm T}\textbf{x}_i+b\leq-1$；当$y=+1$时，$\textbf{w}^{\rm T}\textbf{x}_i+b\geq+1$。两种情况合并为：$y_i(\textbf{w}^{\rm T}\textbf{x}_i+b)\geq1,i=1,2,…,m$。间隔$\gamma$由平行线间的距离公式计算得到$\gamma=\frac{2}{\Vert \textbf{w} \Vert}$，$\gamma$要尽量大。问题可以重写为：

\[\min\limits_{\textbf{w},b}\frac{1}{2}{\Vert \textbf{w} \Vert}^2,s.t.\space y_i(\textbf{w}^{\rm T}\textbf{x}_i+b)\geq1,i=1,2,...,m\]

对偶问题与核函数

对上面这个优化问题，用拉格朗日乘子法求解可以得到该问题的对偶问题：

\[\max_{\alpha}{\sum_{i=1}^m\alpha_i-\frac{1}{2}{}\sum_{i=1}^m\sum_{j=1}^m{\alpha_i\alpha_jy_iy_j\textbf{x}_i^{\rm{T}}\textbf{x}_j}}\] \[s.t.\space\left\{ \begin{array}{ll} \sum\limits_{i=1}^m\alpha_iy_i=0\\ \alpha\geq0,i=1,2,...,m \end{array} \right.\]

对线性不可分问题，可以采用核函数的方法，将$\textbf x$映射到高维特征向量$\phi(\textbf x)$，我们希望这些映射后的特征向量线性可分。

而在它们的对偶问题中，总是要计算$\phi(\textbf{x}_i)^{\rm{T}}\phi(\textbf{x}_j)$的值，这个值不容易计算，可以将其作为核函数$K$的计算结果，即

\[\phi(\textbf{x}_i)^{\rm{T}}\phi(\textbf{x}_j)=K(\textbf{x}_i,\textbf{x}_j)\]

核函数最好能够包含$\textbf{x}_i^{\rm{T}}\textbf{x}_j$项，并加以多种形式的变换，即可实现不同的高维映射，还能降低计算复杂度。

支持向量回归(SVR)

回归的目的是让数据离决策面尽可能近，对于模型$f(\textbf{x})=\textbf{w}^{\rm T}\textbf{x}+b$，容忍一定范围内的误差，在f(\textbf{x})两侧设立了一个宽度为$2\epsilon$的间隔带，样本在间隔带内，则被认为预测正确。

SVR问题的形式化为：

\[\min\limits_{\textbf{w},b}\frac{1}{2}{\Vert \textbf{w} \Vert}^2+C\sum\limits_{i=1}^{m}{l_\epsilon(\textbf{w}^{\rm T}\textbf{x}_i+b-y_i)}\]

其中

\[l_\epsilon=\left\{ \begin{array}{ll} 0,\rm{if}\space\vert z\vert\leq\epsilon\\ \vert z\vert-\epsilon,\rm{otherwise} \end{array} \right.\]

类似地，可以得到SVR的对偶问题，形式与SVM的对偶问题类似。