-
线性可分支持向量机(硬间隔最大化)：求解能够正确划分训练数据集并且几何间隔最大的分离超平面。可以表示为凸二次规划问题，其原始最优化问题为： $$ \begin{align} & \min_{w,b}\quad \frac{1}{2} \Vert w\Vert ^2 \ & s.t.\quad y_i (w\cdot x_i + b)-1\ge 0,\quad i=1,2,\dots,N \end{align} $$ 二次规划的对偶问题为： $$ \begin{align} \min_\alpha\quad & \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_j y_i y_j(x_i\cdot x_j) - \sum_{i=1}^N \alpha_i \ s.t.\quad & \sum_{i=1}^N \alpha_i y_i = 0 \ & \alpha_i \ge 0,\quad i=1,2,\dots, N \end{align} $$
-
线性不可分意味着某些样本点
$(x_i, y_i)$ 不能满足函数间隔大于等于1的约束条件。为了解决这个问题，可以对每个样本点$(x_i, y_i)$ 引入一个松弛变量$\xi_i \ge 0$ ，使函数间隔加上松弛变量大于等于1。同时，对每个松弛变量$\xi_i$ ，支付一个代价$\xi_i$ 。线性不可分的线性支持向量机的学习问题变成如下凸二次规划问题（原始问题）： $$ \begin{align} \min_{w,b,\xi}\quad & \frac{1}{2} \Vert w\Vert ^2 + C\sum_{i=1}^N \xi_i \ s.t.\quad & y_i (w\cdot x_i + b) + \xi_i \ge 1,\quad i=1,2,\dots,N \ & \xi_i \ge 0,\quad i=1,2,\dots,N \end{align} $$ 其对偶形式为： $$ \begin{align} \min_\alpha\quad & \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_j y_i y_j(x_i\cdot x_j) - \sum_{i=1}^N \alpha_i \ s.t.\quad & \sum_{i=1}^N \alpha_i y_i = 0 \ & 0 \le \alpha_i \le C,\quad i=1,2,\dots, N \end{align} $$ -
核技巧可以用线性分类方法求解非线性分类问题，分为两步：首先使用一个变换将原空间的数据映射到新空间；然后在新空间里用线性分类学习方法从训练数据中学习分类模型。
-
（核函数）设
$\mathcal{X}$ 是输入空间（欧氏空间$\mathbf{R}^n$ 的子集或离散集合），又设$\mathcal{H}$ 为特征空间（希尔伯特空间），如果存在一个从$\mathcal{X}$ 到$\mathcal{H}$ 的映射$$\phi(x):\mathcal{X} \to \mathcal{H}$$ 使得对所有的$x,z \in \mathcal{X}$ ，函数$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$ 。对于给定的核$K(x,z)$ ，特征空间$\mathcal{H}$ 和映射函数$\phi$ 的取法并不唯一，可以取不同的特征空间，即便在同一特征空间里也可以取不同的映射。 -
常用核函数 $$ \begin{align} 线性核\quad & k(x_i, x_j) = x_i^T x_j \ 多项式核\quad & k(x_i, x_j) = (x_i^T x_j)^d \ 高斯核（RBF核）\quad & k(x_i^T x_j) = exp(-\frac{\Vert x_i - x_j\Vert^2}{2\sigma^2}) \ 拉普拉斯核\quad & k(x_i^T x_j) = exp(-\frac{\Vert x_i - x_j\Vert}{\sigma}) \ Sigmoid核\quad & k(x_i^T x_j) = tanh(\beta x_i^T x_j + \theta) \ 字符串核函数\quad & 定义在字符串集合上的核函数 \end{align} $$
-
SMO算法是支持向量机学习的一种快速算法，其特点是不断地将原二次规划问题分解为只有两个变量的二次规划问题，并对子问题进行解析求解，直到所有变量满足KKT条件为止。这样通过启发式的方式得到原二次规划问题的最优解。