支持向量机

【引入】

在 单层感知机 中介绍了单层感知机，其能够处理线性可分问题，同时，根据 Novikoff 定理可知，感知机学习算法的原始形式是迭代收敛的

但单层感知机的学习算法是以误分类样本点到超平面 $S$ 的总几何间隔作为损失函数，其存在诸多解，这些解既依赖于参数 $\boldsymbol{\omega}$ 和阈值 $\theta$ 初值的选择，也依赖于迭代过程中误分类点的选择顺序

如下图所示，对于线性可分的样本集而言，能够将样本集划分开的分离超平面可能有无穷多个

直观上来看，应该去找位于两类训练样本的正中间的分离超平面，这个超平面对未见样本的泛化能力是最强的

【支持向量机模型】

支持向量机（Support Vector Machines，SVM）是感知机的进阶算法，也是一种二分类的线性分类模型，其本质上是寻找特征空间 $\mathbb{R}^n$ 中的一个超平面 $S:\boldsymbol{\omega}\cdot \mathbf{x}+\theta=0$，将特征空间划分为两个部分，使得位于两部分的点被分为正负两类

设输入空间 $\mathcal{X}\in \mathbb{R}^{n}$，输出空间 $\mathcal{Y}=\{-1,+1\}$，输入 $\mathbf{x}=(x^{(1)},x^{(2)},…,x^{(n)})\in\mathcal{X}$ 为实例的特征向量，对应于输入空间的点，输出 $y\in\mathcal{Y}$ 为实例的类别

支持向量机的分类决策函数为：

$$f(\mathbf{x}) = \text{sign}(\boldsymbol{\omega}\cdot\mathbf{x}+\theta)$$

其中，$\boldsymbol{\omega}\in \mathbb{R}^{n}$ 为权值（Weight），$\theta\in \mathbb{R}$ 为阈值（Threshold），$\boldsymbol{\omega}\cdot \mathbf{x}$ 表示 $\boldsymbol{\omega}$ 与 $\mathbf{x}$ 的内积

可以发现，支持向量机的分类决策函数与感知机的分类决策函数一致，但不同的是，感知机的学习算法是以误分类样本点到超平面 $S$ 的总几何间隔作为损失函数，支持向量机的学习算法是寻找能够正确划分训练集且使几何间隔最大的分离超平面，即两者的损失函数不同

【支持向量机的类型】

支持向量机的学习策略是间隔最大化，根据训练数据的实际情况，可分为以下三类：

1）硬间隔支持向量机（Hard Margin Support Vector Machines）

当训练数据线性可分时，通过硬间隔最大化来求解唯一的最优分离超平面：

$$S: \boldsymbol{\omega}^*\cdot \mathbf{x}+\theta^* = 0$$

以及相应的分类决策函数：

$$f(\mathbf{x}) = \text{sign}(\boldsymbol{\omega}^*+\theta^*)$$

关于硬间隔支持向量机，详见：硬间隔支持向量机

2）软间隔支持向量机

当训练数据近似可分时，通过软间隔最大化来求解唯一的最优分离超平面：

$$S: \boldsymbol{\omega}^*\cdot \mathbf{x}+\theta^* = 0$$

以及相应的分类决策函数：

$$f(\mathbf{x}) = \text{sign}(\boldsymbol{\omega}^*+\theta^*)$$

关于硬间隔支持向量机，详见：软间隔支持向量机

3）非线性支持向量机

当训练数据线性不可分时，通过核方法在软间隔支持向量机的基础上来求解分类决策函数：

$$f(\mathbf{x}) = \text{sign} (\sum_{i=1}^n \lambda_i^*y_iK(\mathbf{x}_i,\mathbf{x})+\theta^*)$$

关于非线性支持向量机，详见：非线性支持向量机

【支持向量机的学习策略】

支持向量机的学习策略可以形式化为一个求解凸二次规划（Convex Quadratic Programming）的问题，也等价于正则化的铰链损失函数的最小化问题，其学习算法就是求解凸二次规划的最优算法

凸二次规划问题具有全局最优解且有许多最优化算法可用于这一问题的求解，但当训练样本容量 $n$ 很大时，这些算法往往会变得十分低效，以致无法使用

目前，针对这一问题，已经提出了许多快速求解凸二次规划问题的算法，如：椭球法、内点法、增广拉格朗日法、梯度投影法等，在支持向量机中，最常用的是 SMO 算法

关于 SMO 算法，详见：序列最小最优化算法 SMO