---

6.0 学习导图

---

6.1 基本流程

  给定训练样本集 $D=\left\{\left(\boldsymbol{x}_{1}, y_{1}\right),\left(\boldsymbol{x}_{2}, y_{2}\right), \ldots,\left(\boldsymbol{x}_{m}, y_{m}\right)\right\}，y_{i} \in\{-1,+1\}$D={(x1​,y1​),(x2​,y2​),…,(xm​,ym​)}，yi​∈{−1,+1} ，在样本空间中找到一个超平面，将不同类别的样本分开。

  在样本空间中，划分超平面可通过如下线性方程描述：

$\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b=0\tag{6.1}$wTx+b=0(6.1)

其中 $\boldsymbol{w}=\left( \begin{array}{c}{w_{1}} \\ {w_{2}} \\ {\vdots} \\ {w_{d}}\end{array}\right)$w=⎝⎜⎜⎜⎛​w1​w2​⋮wd​​⎠⎟⎟⎟⎞​ 为法向量，决定超平面的方向， $b$b 为位移项，决定超平面与原点之间的距离。将超平面简写为 $(\boldsymbol{w}, b)$(w,b) 。样本空间中任意点 $\boldsymbol{x}$x 到超平面 $(\boldsymbol{w}, b)$(w,b) 的距离为

$r=\frac{\left|\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b\right|}{\|\boldsymbol{w}\|}\tag{6.2}$r=∥w∥∣∣​wTx+b∣∣​​(6.2)

证：从点 $\boldsymbol{x}$x 向超平面 $(\boldsymbol{w}, b)$(w,b) 做垂线，垂足为 $\boldsymbol{x_0}$x0​ ，令 $\boldsymbol{r}=\boldsymbol{x}-\boldsymbol{x_0}$r=x−x0​ ，则 $r=\|\boldsymbol{x}-\boldsymbol{x_0}\|$r=∥x−x0​∥ ，显然， $\boldsymbol{w}$w 平行于 $\boldsymbol{r}$r ，故有

$|\boldsymbol{w}^\mathrm{T}(\boldsymbol{x}-\boldsymbol{x_0})|=|\boldsymbol{w}^\mathrm{T}\boldsymbol{r}|=|\boldsymbol{w}\cdot\boldsymbol{r}|=\|\boldsymbol{w}\|\|\boldsymbol{r}\|=\|\boldsymbol{w}\|r$∣wT(x−x0​)∣=∣wTr∣=∣w⋅r∣=∥w∥∥r∥=∥w∥r

又 $\boldsymbol{x_0}$x0​ 在超平面上，故有

$\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x_0}+b=0$wTx0​+b=0

所以

$|\boldsymbol{w}^\mathrm{T}(\boldsymbol{x}-\boldsymbol{x_0})|=|\boldsymbol{w}^\mathrm{T}\boldsymbol{x}-\boldsymbol{w}^\mathrm{T}\boldsymbol{x_0}|=|\boldsymbol{w}^\mathrm{T}\boldsymbol{x}+b|$∣wT(x−x0​)∣=∣wTx−wTx0​∣=∣wTx+b∣

联立，可得式(6.2)

  假设超平面 $(\boldsymbol{w},b)$(w,b) 能将训练样本正确分类，即有

$\left\{\begin{array}{ll}{\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b &gt; 0,} &amp; {y_{i}=+1} \\ {\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b &lt; 0,} &amp; {y_{i}=-1}\end{array}\right.${wTxi​+b>0,wTxi​+b<0,​yi​=+1yi​=−1​

则对 $\boldsymbol{w}$w 和 $b$b 进行等比例缩放，一定能有

$\left\{\begin{array}{ll}{\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b \geqslant+1,} &amp; {y_{i}=+1} \\ {\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b \leqslant-1,} &amp; {y_{i}=-1}\end{array}\right.\tag{6.3}${wTxi​+b⩾+1,wTxi​+b⩽−1,​yi​=+1yi​=−1​(6.3)

  如图 6.2 所示，距离超平面最近的几个训练样本使式(6.3)的等号成立，它们被称为“支持向量”，两个异类支持向量到超平面的距离之和为

$\gamma=\frac{2}{\|\boldsymbol{w}\|}\tag{6.4}$γ=∥w∥2​(6.4)

它被称为“间隔”。

  要找到具有“最大化间隔”的划分超平面，也就是要找到能满足式(6.3)中约束的参数 $\boldsymbol{w}$w 和 $b$b ，使得 $\gamma$γ 最大，即

$\begin{array}{l}{\max _{w, b} \frac{2}{\|\boldsymbol{w}\|}} \\\\ {\text { s.t. } y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1, \quad i=1,2, \ldots, m}\end{array}\tag{6.5}$maxw,b​∥w∥2​ s.t. yi​(wTxi​+b)⩾1,i=1,2,…,m​(6.5)

  显然，上式(6.5)与下式(6.6)等价

$\begin{array}{l}{\min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2}} \\\\ {\text { s.t. } y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1, \quad i=1,2, \ldots, m}\end{array}\tag{6.6}$minw,b​21​∥w∥2 s.t. yi​(wTxi​+b)⩾1,i=1,2,…,m​(6.6)

这就是支持向量机（简称SVM）的基本型。

---

6.2 对偶问题

  求解式(6.6)可得到最大间隔划分超平面所对应的模型

$f(\boldsymbol{x})=\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b\tag{6.7}$f(x)=wTx+b(6.7)

其中 $\boldsymbol{w}$w 和 $b$b 是模型参数。
  式(6.6)是一个凸二次规划，可以使用拉格朗日乘子法得到其“对偶问题”：

• 将式(6.6)写成如下形式

$\begin{array}{l}{\min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2}} \\\\ {\text { s.t. } 1-y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \leqslant 0, \quad i=1,2, \ldots, m}\end{array}\tag{6.6}$minw,b​21​∥w∥2 s.t. 1−yi​(wTxi​+b)⩽0,i=1,2,…,m​(6.6)

• 加入拉格朗日乘子 $\alpha_i\geqslant0$αi​⩾0

$L(\boldsymbol{w}, b, \boldsymbol{\alpha})=\frac{1}{2}\|\boldsymbol{w}\|^{2}+\sum_{i=1}^{m} \alpha_{i}\left(1-y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)\right)，其中，\boldsymbol{\alpha}=\left( \begin{array}{c}{\alpha_{1}} \\ {\alpha_{2}} \\ {\vdots} \\ {\alpha_{m}}\end{array}\right)\tag{6.8}$L(w,b,α)=21​∥w∥2+i=1∑m​αi​(1−yi​(wTxi​+b))，其中，α=⎝⎜⎜⎜⎛​α1​α2​⋮αm​​⎠⎟⎟⎟⎞​(6.8)

• 原问题转化为

$\min _{\boldsymbol{w}, b} \max _{\boldsymbol{\alpha}} L(\boldsymbol{w}, b, \boldsymbol{\alpha})$w,bmin​αmax​L(w,b,α)

• 其对偶问题为

$\max _{\boldsymbol{\alpha}} \min _{\boldsymbol{w}, b} L(\boldsymbol{w}, b, \boldsymbol{\alpha})$αmax​w,bmin​L(w,b,α)

• 对 $\boldsymbol{w}$w 和 $b$b 求偏导令其为 $0$0，得到内层取最小值时的解

$\boldsymbol{w}=\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{x}_{i}\tag{6.9}$w=i=1∑m​αi​yi​xi​(6.9)

$0=\sum_{i=1}^{m} \alpha_{i} y_{i}\tag{6.10}$0=i=1∑m​αi​yi​(6.10)

• 代回式(6.8)

$\begin{aligned} L(\boldsymbol{w}, b, \boldsymbol{\alpha})&amp;=\frac{1}{2}\|\boldsymbol{w}\|^{2}+\sum_{i=1}^{m} \alpha_{i}\left(1-y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)\right) \\ &amp;=\frac{1}{2}\boldsymbol{w}^\mathrm{T}\boldsymbol{w}+\sum_{i=1}^{m} \alpha_{i}-\sum_{i=1}^{m} \alpha_{i}y_{i}\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}-b\sum_{i=1}^{m} \alpha_{i}y_{i} \\ &amp;=\frac{1}{2}\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{x}_{i}^\mathrm{T}\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{x}_{i}+\sum_{i=1}^{m} \alpha_{i}-\sum_{i=1}^{m} \alpha_{i}y_{i}(\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{x}_{i}^\mathrm{T})\boldsymbol{x}_{i}-0 \\ &amp;=\sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j} \end{aligned}$L(w,b,α)​=21​∥w∥2+i=1∑m​αi​(1−yi​(wTxi​+b))=21​wTw+i=1∑m​αi​−i=1∑m​αi​yi​wTxi​−bi=1∑m​αi​yi​=21​i=1∑m​αi​yi​xiT​i=1∑m​αi​yi​xi​+i=1∑m​αi​−i=1∑m​αi​yi​(i=1∑m​αi​yi​xiT​)xi​−0=i=1∑m​αi​−21​i=1∑m​j=1∑m​αi​αj​yi​yj​xiT​xj​​

• 加上约束条件，得到原问题的对偶问题

$\begin{aligned}&amp;{\max _{\alpha} (\sum_{i=1}^{m} \alpha_{i}- \frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}}) \\\\ &amp;\text { s.t. } {\sum_{i=1}^{m} \alpha_{i} y_{i}=0} \\\\ &amp;\ \ \ \ \ \ \ {\alpha_{i} \geqslant 0, \quad i=1,2, \ldots, m}\end{aligned}\tag{6.11}$​α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​(6.11)

令 $\boldsymbol\alpha^*$α∗ 是式(6.11)的解，则可得到 $\boldsymbol{w}$w 和 $b$b 进而得到模型

$\begin{aligned} f(\boldsymbol{x}) &amp;=\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b \\ &amp;=\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}+b \end{aligned}\tag{6.12}$f(x)​=wTx+b=i=1∑m​αi​yi​xiT​x+b​(6.12)

解 $\boldsymbol\alpha^*$α∗ 常用 SMO 方法

---

6.3 核函数

  将式(6.7)中的 $\boldsymbol{x}$x 用 $\phi(\boldsymbol{x})$ϕ(x) 代替，常用于将原始输入空间映射到新的高维特征空间，使原本线性不可分的样本在核空间可分。

---

6.4 软间隔与正则化

  所有样本都必须划分正确“硬间隔”，允许一些错误“软间隔”。引入损失函数和松弛变量。

  软间隔增强泛化能力，可防止过拟合，但容易产生欠拟合。

---

6.5 支持向量回归

  将分类模型转化成回归模型：SVR 支持向量回归

---

6.6 核方法

  基于核函数的一系列学习方法：“核方法”