Task05 详读西瓜书 + 南瓜书第 6 章

1 间隔与支持向量

• 支持向量的概念： 假设超平面 $(w,b)$ 能将训练样本正确分类，即对于 $(x_i,y_i)\in D$，若 $y_i=+1$，则有 $w^T{x}_i+b>0$，若 $y_i=-1$，则有 $w^T{x}_i+b<0$，令：

$$\{\begin{array}{c}{w}^T{x}_i+b⩾+1,y_i=+1\\ w^T{x}_i+b⩽-1,y_i=-1\end{array}$$

距离超平面最近的这几个训练样本点使得上式成立，则这些样本点被称为支持向量。

• 间隔：两个异类支持向量超平面的距离之和 $\gamma =\frac{2}{\parallel w\parallel }$
• 支持向量机（SVM）基本型：

找到最大间隔的划分超平面，需要求解参数 $w$ 和 $b$ 使得 $\gamma$ 最大，目标函数如下：

$$\begin{array}{ll}\underset{w,b}{min}& \frac{1}{2}\parallel w{\parallel }^2\\ \text{ s.t. }& y_i(w^T{x}_i+b)⩾1,i=1,2,\dots ,m\end{array}$$

2 对偶问题

• 拉格朗日函数：$L(w,b,\alpha )=\frac{1}{2}\parallel w{\parallel }^2+\sum _{i=1}^m{\alpha }_i(1y_i(w^T{x}_i+b))$
• 对偶问题：

$$\begin{array}{ll}\underset{\alpha }{max}& \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{x}_i^T{x}_j\\ \text{ s.t. }& \sum _{i=1}^m{\alpha }_i{y}_i=0\\ & {\alpha }_i⩾0,i=1,\dots ,m\end{array}$$

• KKT 条件：

$$\{\begin{array}{l}{\alpha }_i⩾0\\ y_{i}f(x_i)-1⩾0\\ {\alpha }_i(y_{i}f(x_i)-1)=0\end{array}$$

• 支持向量机特点：训练完成后，大部分的训练样本都不需保留，最终模型仅与支持向量有关
• SMO 算法思路：
  1. 选取一对需要更新的变量 ${\alpha }_i$ 和 ${\alpha }_j$
  2. 固定 ${\alpha }_i$ 和 ${\alpha }_j$ 以外的参数，求解对偶问题，获得更新后的 ${\alpha }_i$ 和 ${\alpha }_j$
  3. 重复上述 2 个步骤，直至收敛
• SMO 采用一个启发式：使选取的两变量所对应样本之间的间隔最大

3 软间隔与正则化

• 软间隔：允许某项样本不满足约束 $y_i(w^T{x}_i+b)⩾1$，在最大化间隔的同时，不满足约束的样本应该尽可能少
• 目标函数：

$$\begin{array}{ll}{\displaystyle \underset{w,b}{min}}& {\displaystyle \frac{1}{2}\parallel w{\parallel }^2+C\sum _{i=1}^m{\ell }_{0/1}(y_i(w^T{x}_i+b)-1)}\\ & {\ell }_{0/1}(z)=\{\begin{array}{ll}1,& \text{ if }z<0;\\ 0,& \text{ otherwise }\end{array}\end{array}$$

• 损失函数：
  1. hinge 损失：${\ell }_{hinge}(z)=max(0,1-z)$
  2. 指数损失（exponential loss）: ${\ell }_{exp}(z)=\exp (-z)$
  3. 对率损失（logistic loss）：${\ell }_{log}(z)=log(1+\exp (-z))$
• 常用的软间隔支持向量机：

$$\begin{array}{ll}{\displaystyle \underset{w,b,\xi }{min}}& {\displaystyle \frac{1}{2}\parallel w{\parallel }^2+C\sum _{i=1}^m{\xi }_i}\\ \text{s.t.}& y_i(w^T{x}_i+b)⩾1-{\xi }_i\\ & {\xi }_i⩾0,i=1,\dots ,m\end{array}$$

• 软间隔支持向量机的对偶问题：

$$\begin{array}{cl}{\displaystyle \underset{\alpha }{max}}& {\displaystyle \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{x}_i^T{x}_j}\\ \text{s.t.}& {\displaystyle \sum _{i=1}^m{\alpha }_i{y}_i=0}\\ & 0⩽{\alpha }_i⩽C,i=1,2,\dots ,m\end{array}$$

• 软间隔支持向量机的 KKT 条件：

$$\{\begin{array}{l}{\alpha }_i⩾0,{\mu }_i⩾0\\ y_{i}f(x_i)-1+{\xi }_i⩾0\\ {\alpha }_i(y_{i}f(x_i)-1+{\xi }_i)=0\\ {\xi }_i⩾0,{\mu }_i{\xi }_i=0\end{array}$$

• 软间隔支持向量机的最终模型仅与支持向量有关，即通过采用 hinge 损失函数仍保持了稀疏性
• 正则化问题：

$$\underset{f}{min}\mathrm{\Omega }(f)+C\sum _{i=1}^m\ell (f(x_i),y_i)$$

在该式中，$\mathrm{\Omega }(f)$ 称为正则化项，$C$ 称为正则化参数

1. $L_p$ 范数使常用的正则化项
2. $L_2$ 范数 $\|w\|_2$ 倾向于 $w$ 的分量取值尽量均衡，即非零分量个数尽量稠密
3. $L_0$ 范数 $\|w\|_0$ 和 $L_1$ 范数 $\|w\|_1$ 倾向于 $w$ 的分量尽量系数，即非零分量个数尽量少

4 支持向量回归

• 损失计算规则：以 $f(x)$ 为中心，构建一个宽度为 $2ϵ$ 的间隔带，若训练样本落入此间隔带，则不计算损失，认为是被预测正确
• SVR 目标函数：

$$\begin{array}{ll}{\displaystyle \underset{w,b,{\xi }_i,\hat{\xi }\ast i}{min}}& {\displaystyle \frac{1}{2}\parallel w{\parallel }^2+C\sum \ast {i=1}^m({\xi }_i+\hat{\xi }\ast i)}\\ \text{s.t.}& f(x_i)-y_i⩽ϵ+{\xi }_i\\ & y_i-f(x_i)⩽ϵ+\hat{\xi }\ast i\\ & {\xi }_i⩾0,\hat{\xi }\ast i⩾0,i=1,2,\dots ,m\end{array}$$

• SVR 对偶问题：

$$\begin{array}{ll}max\ast \alpha ,\hat{\alpha }& {\displaystyle \sum \ast {i=1}^{m}y\ast i(\hat{\alpha }\ast i-\alpha \ast i)-ϵ(\hat{\alpha }\ast i+\alpha \ast i)-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m(\hat{\alpha }\ast i-\alpha \ast i)(\hat{\alpha }\ast j-\alpha \ast j)x_i^T{x}_j}\\ \text{ s.t. }& {\displaystyle \sum _{i=1}^m(\hat{\alpha }\ast i-\alpha \ast i)=0}\\ & 0⩽{\alpha }_i,{\hat{\alpha }}_i⩽C\end{array}$$

• SVR 的 KKT 条件：

$$\{\begin{array}{l}{\alpha }_i(f(x_i)-y_i-ϵ-{\xi }_i)=0\\ {\hat{\alpha }}_i(y_i-f(x_i)-ϵ-{\hat{\xi }}_i)=0\\ {\alpha }_i{\hat{\alpha }}_i=0,{\xi }_i{\hat{\xi }}_i=0\\ (C-{\alpha }_i){\xi }_i=0,(C-{\hat{\alpha }}_i)\hat{\xi }\ast i=0\end{array}$$

• SVR 的解：

$$f(x)=\sum \ast {i=1}^m(\hat{\alpha }\ast i-{\alpha }_i)x_i^{T}x+b$$

其中：

$$\begin{gathered} b=y_i+ϵ-\sum \ast {i=1}^m(\hat{\alpha }\ast i-{\alpha }_i)x_i^{T}x \\ w=\sum \ast {i=1}^m({\hat{\alpha }}_i-{\alpha }_i)\varphi (x_i) \end{gathered}$$