SVM（一）：问题定义

支持向量机（Support Vector Machine）由Cortes 和Vapnik于1995年正式发表（“Support vector networks”, Machine Learning, 20(3):273-297)，由于在二维表分类任务中显示出卓越性能，很快成为机器学习的主流技术，并在2000年掀起了统计学习的高潮。

1 线性支持向量机

图(a)中红色和蓝色分别代表两个不同类别的数据，显然是线性可分的，但将两类数据点分开的直线不止一条。

• 图的(b)和©分别给出B、C两种不同的划分方案，其中黑色实线为分界线称为划分超平面（又称决策面）。
• 两侧虚线所穿过的样本点，就是SVM中的支持样本点，称为支持向量。
• 支持向量到超平面的距离称为间隔，显然，分类器B的分离超平面优于分类器C的，在SVM中认为分类器B的分类间隔比分类器C的分类间隔大。
• 每一个可能把数据集正确分开的方向都有一个最优分离超平面，而不同方向的最优决策面的分类间隔通常是不同的，具有最大间隔的决策面就是SVM的最优解，称为最优超平面。

1.1 问题定义

（1） 划分超平面

二维样本空间中，划分平面可以表示为：$w_1x_1+w_2x_2+b=0$w1​x1​+w2​x2​+b=0

在高维样本空间中，划分超平面定义如下：$\boldsymbol w^T \boldsymbol x + b = 0$wTx+b=0
其中，$\boldsymbol w = (w_1,w_2,...,w_d)$w=(w1​,w2​,...,wd​)为法向量，决定了超平面的方向；$b$b为位移，决定了超平面与原点之间的距离。

设空间中任一点$\boldsymbol x$x在超平面的投影为$\boldsymbol x'$x′，则$\boldsymbol x= \boldsymbol x′+ \lambda \boldsymbol w$x=x′+λw

$\boldsymbol w^T \boldsymbol x +b = \boldsymbol w^T (\boldsymbol x'+\lambda w) + b = \boldsymbol w^T \boldsymbol x' +b + \lambda \boldsymbol w \boldsymbol w^T = \lambda \boldsymbol w^T \boldsymbol w$wTx+b=wT(x′+λw)+b=wTx′+b+λwwT=λwTw

（2） 点到超平面的距离

样本空间中任意点$\boldsymbol x$x到超平面的距离为
$\begin{aligned} \gamma & = ||\boldsymbol x - \boldsymbol x'|| \\ & = ||\lambda \boldsymbol w|| \\ & = \frac {\lambda {||\boldsymbol w||}^2}{||\boldsymbol w||} \\ & = \frac{|\boldsymbol w^{T} \boldsymbol x+b|}{|| \boldsymbol w||} \end{aligned}$γ​=∣∣x−x′∣∣=∣∣λw∣∣=∣∣w∣∣λ∣∣w∣∣2​=∣∣w∣∣∣wTx+b∣​​

其中，$\left| \left| \boldsymbol w \right| \right|=\sqrt{\sum_{i=1}^{n}{w_{i}^{2}}}$∣∣w∣∣=∑i=1n​wi2​​为$w$w的L2范数。

（3）支持向量、间隔

假设超平面能将训练样本正确分类，即对于$(\boldsymbol x_i,y_i) \in D$(xi​,yi​)∈D，
$\begin{cases} \boldsymbol w^T \boldsymbol x_i + b > 0, y_i=+1 & \\ \boldsymbol w^T \boldsymbol x_i + b < 0, y_i=-1 & \end{cases}${wTxi​+b>0,yi​=+1wTxi​+b<0,yi​=−1​​

$\begin{aligned} & \Leftrightarrow y_i(\boldsymbol w^T \boldsymbol x_i + b)>0 \;\; \\ & \Leftrightarrow \exists r>0, s.t. \min y_i(\boldsymbol w^T \boldsymbol x_i + b)=r \end{aligned}$​⇔yi​(wTxi​+b)>0⇔∃r>0,s.t.minyi​(wTxi​+b)=r​

由于$\boldsymbol w 与 b$w与b可任意缩放，令$r=1$r=1
$\begin{aligned} & \Leftrightarrow y_i(\boldsymbol w^T \boldsymbol x_i + b) \geq 1 \\ & \\ & \Leftrightarrow \begin{cases} \boldsymbol w^T \boldsymbol x_i + b \geq +1, y_i=+1 & \\ \boldsymbol w^T \boldsymbol x_i + b \leq -1, y_i=-1 & \end{cases} \end{aligned}$​⇔yi​(wTxi​+b)≥1⇔{wTxi​+b≥+1,yi​=+1wTxi​+b≤−1,yi​=−1​​​

如下图所示，距离超平面最近的训练样本点是得上式等号成立，称为支持向量（Support vector）。

支持向量到超平面的距离之和为$\gamma = \frac{2}{|| \boldsymbol w||}$γ=∣∣w∣∣2​，称为间隔（margin）。

（4）最优超平面

能将两类样本划分的超平面有无数多个，具有最大分类间隔的超平面，称为最优超平面。
为找到具有最大间隔的划分超平面，需要$\max_{\boldsymbol w,b} \;\; \frac{1}{||\boldsymbol w||} \;\; s.t. \;\; y_i(\boldsymbol w^T \boldsymbol x_i + b) \geq 1 (i =1,2,...m)$w,bmax​∣∣w∣∣1​s.t.yi​(wTxi​+b)≥1(i=1,2,...m)

即$\min_{\boldsymbol w,b} \;\; \frac{1}{2}||\boldsymbol w||^2 \;\; s.t. \;\; y_i(\boldsymbol w^T \boldsymbol x_i + b) \geq 1 (i =1,2,...m)$w,bmin​21​∣∣w∣∣2s.t.yi​(wTxi​+b)≥1(i=1,2,...m)