机器学习：支持向量机

超平面

任一平面都可以用它上面的一点及它的法线向量来确定。易于理解的形式：

$$x\cos \alpha +y\cos \beta +z\cos \gamma =p$$

其中 $p$ 为平面到原点的距离，3 个角度分别为平面法向量在 x y z 轴方向的方向余弦

超平面 $(\omega ,b)$ 表示超平面方程为：

$${\omega }^{T}x+b=0$$

• $\omega$ 为超平面的法向量，决定了超平面的方向
• $b$ 为位移项，决定了超平面与原点的距离

任意点 $x_0$ 到超平面 $(\omega ,b)$ 的距离 $r$ 可写为：

$$r=\frac{|{\omega }^T{x}_0+b|}{||\omega ||}$$

式子的分子为法向量和以点 $x_0$ 为终点的向量的数量积，分母为法向量的模，得出的结果即为平面上的任意一点与点 $x_0$ 的连线的模乘以其与法向量的夹角的余弦值，显然为点到平面的距离。

超平面用于分类

设有样本 $x_i$ ，其类别为 $y_i(y_i\in \{1,-1\})$，若超平面 $(\omega ,b)$ 能将其正确分类，则 $(\omega ,b)$ 应满足：

$$\{\begin{array}{rclll}\omega x_i+b& \ge & 1& & y=1\\ \omega x_i+b& \le & -1& & y=-1\end{array}$$

支持向量机的基本型

距离超平面最近的几个样本点称为支持向量，支持向量点 $x_j$ 满足

$$\begin{array}{rlrl}\omega x_i+b& =1& & y=1\\ \omega x_i+b& =-1& & y=-1\end{array}$$

因此，两个异类支持向量到平面的距离之和为

$$\gamma =\frac{2}{||\omega ||}$$

显然，超平面与支持向量之间的距离越远越好，此时分类结果是最鲁棒的，泛化能力最强，故分类的目标是：

$$\begin{array}{rl}& \underset{\omega ,b}{max}\frac{2}{||\omega ||}\\ \text{ s.t. }& y_i({\omega }^T{x}_i+b)\ge 1& i=1,2,3,...,m.\end{array}$$

最大化间隔等效于最大化 $\omega$ 的倒数，等效于最小化 $\frac{1}{2}{\omega }^2$，此即为支持向量机（Support Vector Machine，SVM）的基本型

求解

利用拉格朗日乘数法来求解上述基本型

考研数学中，拉格朗日乘数法用于多元函数的求条件极值问题，若求 $f(x,y)$ 在条件 $\phi (x,y)=0$ 下的极值，只需构造拉格朗日函数 $F(x,y,\lambda )=f(x,y)+\lambda \phi (x,y)$ ，然后求解使其偏导均为 0 的方程组即可。

此时的条件极值的条件为：$y_i({\omega }^T{x}_i+b)\ge 1$ （其意义为对每一个样本 $x_i$，都能正确计算其类别）

写出拉格朗日函数：

$$L(\omega ,b,\alpha )=\frac{1}{2}||\omega |{|}^2+\sum _{i=1}^m{\alpha }_i(1-y_i({\omega }^T{x}_i+b))$$

学习中…

核函数

原始样本空间内不存在可以划分样本的超平面时，可选择将样本空间映射到一个更高维的特征空间，使样本在这个特征空间内线性可分。

如果原始空间是有限维，那么一定存在一个高维特征空间使样本可分。

令 $\varphi (x)$ 表示 $x$ 映射到高维空间后的向量，则对应的超平面可表示为：

$$f(x)={\omega }^T\varphi (x)+b$$

其对偶问题为：

$$\begin{array}{rl}& \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\varphi (x_i{)}^T\varphi (x_j)\\ & \text{s.t.}\sum _{i=1}^m{\alpha }_i{y}_i=0\\ & {\alpha }_i\ge 0,i=1,2,...,m.\end{array}$$

其中涉及到 $\varphi (x_i{)}^T\varphi (x_j)$ 的计算，计算比较困难，用函数 $\kappa (x_i,x_j)$ 来代替，即函数

$$\kappa (x_i,x_j)=\varphi (x_i{)}^T\varphi (x_j)$$

此即为核函数，关于核函数是否存在的问题，有一个核函数定理如下：

令 $\chi$ 为输入空间，$\kappa (·,·)$ 是定义在 $\chi \times \chi$ 上的对称函数，设 $\kappa$ 是核函数当且仅当对于任意数据 $D=\{x_1,x_2,...,x_m\}$ ，“核矩阵” $K$ 总是半正定的。

$$K=\left(\begin{array}{cccc}\kappa (x_1,x_1)& \kappa (x_1,x_2)& \cdots & \kappa (x_1,x_n)\\ \kappa (x_2,x_1)& \kappa (x_2,x_2)& \cdots & \kappa (x_2,x_n)\\ ⋮& ⋮& \ddots & ⋮\\ \kappa (x_n,x_1)& \kappa (x_n,x_2)& \cdots & \kappa (x_n,x_n)\end{array}\right)$$

也就是只要对称函数对应的核矩阵是半正定的，它就可以作为核函数，对于一个半正定核矩阵，总能找到一个相对应的映射空间，也就是任意一个核函数都隐式地定义了一个特征空间（称为“再生核希尔伯特空间”， RKHS）

特征空间的好坏对支持向量机至关重要，故选择核函数十分控妖，必须将样本映射到合适的特征空间，使其尽可能地线性可分，常用核函数有：

svm常用核函数_svm核函数_wolfrevoda的博客-CSDN博客

核函数的组合也是核函数

• 对于 ${\gamma }_1$ 和 ${\gamma }_2$ 均为正数的情况， ${\gamma }_1{\kappa }_1+{\gamma }_2{\kappa }_2$ 也是核函数
• 核函数的直积也是核函数
• 对于任意的函数 $g(x)$ ，$g(x){\kappa }_1(x,z)g(z)$ 也是核函数

软间隔

软间隔允许支持向量机在一些样本上出错，即允许部分样本不满足 $y_i({\omega }^T{x}_i+b)\ge 1$

此时优化目标变成了：

$$\underset{\omega ,b}{min}\frac{1}{2}||\omega |{|}^2+C\sum _{i=1}^{m}l(y_i({\omega }^T{x}_i+b)-1)$$

其中 $C$ 为常数，$l$ 为损失函数，常见的损失函数有：

• hinge 损失：$max(0,1,-z)$
• 指数损失：$\exp (-z)$
• 对率损失：$\log (1+\exp (-z))$

支持向量回归

传统回归模通常直接基于模型输出 $f(x)$ 与真实输出 $y$ 计算损失，而支持向量机则允许计算值和真实值之间有一定的误差 $ϵ$ ，也就是仅当预测值和真实值之间的绝对差大于 $ϵ$ 时才计算损失，这相当于以 $f(x)$ 为中心，构建一条宽度为 $2ϵ$ 的间隔带，只要预测值落入其中，即为预测正确。