支持向量机

机器学习

---

1. 任务

给定训练集：

$$T={(x_1,y_1),(x_2,y_2),...,(x_n,y_n)}$$

其中$x_i$为特征向量（实例）；$y_i$为类标记：$y_i=\pm1$。
目标是寻找一个分离超平面将实例分到不同类。

---

2. 线性可分支持向量机

模型：分离超平面：

$$w\cdot x+b=0$$

分类决策函数：

$$\begin{aligned} f(x)&=sign(w\cdot x+b)\\ &= \begin{cases} +1, & \text{if $w\cdot x+b\geq0$} \\ -1, & \text{if $w\cdot x+b<0$} \end{cases} \end{aligned}$$

策略：寻找能将两类数据正确划分且间隔最大的分离超平面。
算法：凸二次规划。

---

3. 间隔
在超平面$w\cdot x+b=0$ 确定的情况下，$|w\cdot x+b|$ 能够表示点$x$到超平面的距离，而通过观察$w\cdot x+b$ 的符号与类标记$y$的符号是否一致可判断分类是否正确。所以，可以用$y(w\cdot x+b)$的正负性来表示分类的正确性。

超平面$(w,b)$关于样本点$(x_i,y_i)$的函数间隔：

$$\hat{\gamma_i}=y_i(w\cdot x_i+b)$$

所有样本点函数间隔的最小值，为超平面$(w, b)$关于训练数据集$T$的函数间隔：

$$\hat{\gamma}=\min_{i=1,...,N}{\hat{\gamma_i}}$$

函数间隔可以表示分类预测的正确性及确信度。需要对超平面的法向量加些约束，如规范化，$||w||=1$，使得间隔是确定的，这时函数间隔变为几何间隔。

超平面$(w,b)$关于样本点$(x_i,y_i)$的几何间隔：

$$\begin{aligned} \gamma_i&=\frac{\hat{\gamma_i}}{||w||}\\ &=y_i(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||}) \end{aligned}$$

所有样本点几何间隔的最小值，为超平面$(w, b)$关于训练数据集$T$的几何间隔：

$$\gamma=\min_{i=1,...,N}{\gamma_i}$$

如果$||w||=1$，那么函数间隔和几何间隔相等，如果超平面参数$w$和$b$成比例变化（超平面没有改变），函数间隔也按此比例变化，而几何间隔不变。

---

4. 最大间隔分离超平面

定理：线性可分训练数据集的最大间隔分离超平面是存在且唯一的。
将问题表示为约束优化：

$$\begin{aligned} &\max_{w,b} \quad \gamma\\ &s.t. \quad y_i(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||})\geq{\gamma}, \quad i=1,2,\cdots,N \end{aligned}$$

或

$$\begin{aligned} &\max_{w,b} \quad \frac{\hat{\gamma}}{||w||}\\ &s.t. \quad y_i(w \cdot x_i+b)\geq{\hat \gamma}, \quad i=1,2,\cdots,N \end{aligned}$$

函数间隔对求解无影响，取$\hat \gamma=1$，上式等价于：

$$\begin{aligned} &\min_{w,b} \quad \frac{1}{2}||w||^2\\ &s.t. \quad y_i(w \cdot x_i+b)-1 \geq 0, \quad i=1,2,\cdots,N \end{aligned}$$

求得最优解$w^*,b^*$ 得到分离超平面 $w^*\cdot x+b^*=0$
分类决策函数 $f(x)=sign(w^*\cdot x+b^*)$

---

5. 支持向量和间隔边界

支持向量是使$y_i(w \cdot x_i+b)-1=0$成立的点。

对$y_i=+1$的正例点，支持向量在超平面$H_1:w\cdot x+b=+1$上；
对$y_i=-1$的负例点，支持向量在超平面$H_2:w\cdot x+b=-1$上。
$H_1$和$H_2$称为间隔边界，$H_1$和$H_2$之间距离称为间隔，等于$\frac{2}{||w||}$。

在决定分离超平面时只有支持向量起作用，所以支持向量机是由很少的“重要的”训练样本确定。

---

6. 对偶算法

为了求解线性可分支持向量机的最优化问题，应用拉格朗日对偶性，通过求解对偶问题，得到原始问题的最优解。这样做的优点在于：
1. 对偶问题往往更容易求解；
2. 自然引入核函数，进而推广到非线性分类问题。

构建拉格朗日函数：

$$L(w,b,\alpha)=\frac{1}{2}||w||^2-\sum_{i=1}^{N}{\alpha_iy_i(w\cdot x_i+b)}+\sum_{i=1}^{N}{\alpha_i}$$

原始问题：

$$\min_{w,b}\max_{\alpha_i\geq0}L(w,b,\alpha)$$

$\max_{\alpha_i\geq0}$保证了约束条件成立。

对偶问题：

$$\max_{\alpha_i\geq0}\min_{w,b}L(w,b,\alpha)$$

(1)求$\min_{w,b}L(w,b,\alpha)$

$$\begin{aligned} &\nabla_wL(w,b,\alpha)=w-\sum_{i=1}^{N}{\alpha_iy_ix_i}=0\\ &\nabla_bL(w,b,\alpha)=\sum_{i=1}^{N}{\alpha_iy_i}=0 \end{aligned}$$

得:

$$\begin{aligned} &w=\sum_{i=1}^{N}{\alpha_iy_ix_i}\\ &\sum_{i=1}^{N}{\alpha_iy_i}=0 \end{aligned}$$

代入拉格朗日函数：

$$\begin{aligned} L(w,b,\alpha)&=\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}{\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)}-\sum_{i=1}^{N}{\alpha_iy_i}\left((\sum_{j=1}^{N}{\alpha_jy_jx_j})\cdot x_i+b\right)+\sum_{i=1}^{N}{\alpha_i}\\ &=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}{\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)}+\sum_{i=1}^{N}{\alpha_i} \end{aligned}$$

即：

$$\min_{w,b}L(w,b,\alpha)=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}{\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)}+\sum_{i=1}^{N}{\alpha_i}$$

(2)求$\min_{w,b}L(w,b,\alpha)$对$\alpha$的极大

$$\begin{aligned} \max_\alpha \quad &{-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}{\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)}+\sum_{i=1}^{N}{\alpha_i}}\\ s.t. \quad &\sum_{i=1}^{N}{\alpha_iy_i}=0\\ &\alpha_i\geq0, \quad i=1,2,\cdots,N \end{aligned}$$

等价于：

$$\begin{aligned} \min_\alpha \quad &{\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}{\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)}-\sum_{i=1}^{N}{\alpha_i}}\\ s.t. \quad &\sum_{i=1}^{N}{\alpha_iy_i}=0\\ &\alpha_i\geq0, \quad i=1,2,\cdots,N \end{aligned}$$

这便是第4节中原始问题的对偶问题。可以通过SMO算法求解$\alpha^*$，再根据KKT条件求解$w^*,b^*$。

$$\begin{aligned} & w^*=\sum_{i=1}^{N}{\alpha_i^*y_ix_i}\\ & b^*=y_j-\sum_{i=1}^{N}{\alpha_i^*y_i(x_i\cdot x_j)} \end{aligned}$$

其中$j$为使得$\alpha_j^*>0$的下标。

SMO算法是SVM学习的一种快速算法，其特点是不断将原二次规划问题分解为只有两个变量的二次规划问题，并对子问题进行解析求解，直到所有变量满足KKT条件。

---

7. 软间隔最大化

线性不可分意味着某些样本点$(x_i,y_i)$不能满足函数间隔大于等于1，的约束条件，可以对每个样本点$(x_i,y_i)$引进一个松弛变量$\xi_i\geq0$，使函数间隔加上松弛变量大于等于1。
线性不可分的线性支持向量机的学习问题变成下凸二次规划问题（原始问题）：

$$\begin{aligned} \min_{w,b} \quad &\frac{1}{2}||w||^2+C\sum_{i=1}^{N}{\xi_i}\\ s.t. \quad &y_i(w \cdot x_i+b) \geq 1-\xi_i, \quad i=1,2,\cdots,N\\ &\xi_i\geq0, \quad i=1,2,\cdots,N \end{aligned}$$

对偶问题：

$$\begin{aligned} \min_\alpha \quad &{\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}{\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)}-\sum_{i=1}^{N}{\alpha_i}}\\ s.t. \quad &\sum_{i=1}^{N}{\alpha_iy_i}=0\\ &0 \le \alpha_i \le C, \quad i=1,2,\cdots,N \end{aligned}$$

解为：

$$\begin{aligned} & w^*=\sum_{i=1}^{N}{\alpha_i^*y_ix_i}\\ & b^*=y_j-\sum_{i=1}^{N}{\alpha_i^*y_i(x_i\cdot x_j)} \end{aligned}$$

其中$j$为使得$0<\alpha_j^*<C$的下标。$b$的解不唯一，可以取所有符合条件的样本点平均值。

---

8. 合页损失函数

第7节中的原始问题等价于：

$$\min_{w,b} \quad \sum_{i=1}^{N}{\left[1-y_i(w \cdot x_i+b)\right]_{+}+\lambda||w||^2}$$

第一项为经验损失，第二项为正则化项（带松弛变量的SVM自带$L_2$正则化）。
$L(y(w \cdot x+b))=\left[1-y_i(w \cdot x_i+b)\right]_{+}$称为合页损失函数。

$$[z]_+= \begin{cases} z, & \text{$z>0$} \\ 0, & \text{$z \le 0$} \end{cases}$$

即，当样本点被正确分类且函数间隔$y_i(w \cdot x_i+b)$大于1时，损失为0，否则损失是$1-y_i(w \cdot x_i+b)$。

---

9. 核技巧

核函数定义：设$\chi$是输入空间，又设$H$为特征空间，如果存在一个从$\chi$到的映射

$$\phi(x): \chi \to H$$

使得对所有$x,z \in \chi$，函数$K(x,z)$满足

$$K(x,z)=\phi(x) \cdot \phi(z)$$

则称$K(x,z)$为核函数，$\phi(x)$为映射函数，式中$\phi(x) \cdot \phi(z)$为$\phi(x)$和$\phi(z)$的內积。

核技巧的想法是，在学习与预测中只定义核函数$K(x,z)$而不显式地定义映射函数$\phi$。

---

10. 核技巧应用在支持向量机

在处理线性不可分问题时，需要将原空间非线性可分问题变成特征空间的线性可分问题。即：将$x$映射为$\phi (x)$。

$$\begin{aligned} \min_\alpha \quad &{\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}{\alpha_i\alpha_jy_iy_j K(x_i,x_j)}-\sum_{i=1}^{N}{\alpha_i}}\\ s.t. \quad &\sum_{i=1}^{N}{\alpha_iy_i}=0\\ &0 \le \alpha_i \le C, \quad i=1,2,\cdots,N \end{aligned}$$

只需要定义核函数$K(x_i,x_j)$而不用显式地定义映射函数$\phi(x)$。核函数的价值在于它虽然将特征进行从低维到高维的转换，但在低维上进行计算，而将实质上的分类效果(利用了内积)表现在了高维上，这样避免了直接在高维空间中的复杂计算，真正解决了SVM线性不可分的问题。