学习笔记——支持向量机

支持向量机（SVM），基本模型是定义在特征空间上的间隔最大的线性分类器，使用核技巧可以使它成为实质上的非线性分类器。“使间隔最大”形成一个凸二次规划问题。由简至繁可分为：线性可分（硬间隔）支持向量机，（软间隔）线性支持向量机，非线性支持向量机。

线性可分支持向量机

数据线性可分的时候，感知机可以求得分离超平面，但有无数多个解，而支持向量机通过间隔最大化求得的最优分离超平面，解是唯一的。

线性可分支持向量机
给定线性可分训练数据集，通过间隔最大化或等价地求解相应的凸二次规划问题学习得到的分离超平面为$$w^* cdot x + b^* = 0$$以及相应的分类决策函数$$f(x) = sign(w^* dot x + b)$$称为线性可分支持向量机。

超平面((w, b))关于样本点((x_i, y_i))的几何间隔：$$gamma = y_i (frac{w}{||w||} cdot x_i + frac{b}{||w||} ),$$求最大间隔分离超平面可以表示成下面的约束最优化问题：

[max_{w, b} : gamma$$$$s.t. : y_i (frac{w}{||w||} cdot x_i + frac{b}{||w||} ) geq gamma ]

进行简单的推导，得到下面的线性可分支持向量机学习算法——最大间隔法，

线性可分支持向量机学习算法——最大间隔法

输入：线性可分数据集(T={(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)})，其中(x_i in mathcal{X}=R^n)，(y_i in mathcal{Y} = {-1, +1})，(i = 1,2,...,N)

输出：最大间隔分离超平面和分类决策函数.

构造并求解约束最优化问题：$$min_{w, b} : frac{1}{2}||w||^2$$$$s.t. : y_i (w cdot x_i + b) - 1 geq 0, i = 1, 2, ..., N$$

由此得到分离超平面：$$w^* cdot x + b^* = 0$$分类决策函数$$f(x) = sign(w^* cdot x + b^*)$$

距离分离超平面最近的实例称为支持向量，在决定分离超平面时只有支持向量起作用，其他实例点不起作用。

可以应用拉格朗日对偶性，通过求解对偶问题得到原始问题的解，简单来说，就是把最优化问题中的约束条件作为目标函数的一部分，形成新的最优化问题，这个新的最优化问题如果想要和原问题一致的话，需要满足KKT条件。经过推导，可以得到线性可分支持向量机原始问题的对偶问题，相应的对偶学习算法为，

线性可分支持向量机学习算法（对偶）

构造并求解约束最优化问题$$min_{alpha} :: 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.:: sum_{i=1}^{N} alpha_i y_i = 0$$ $$alpha_i geq 0, i = 1, 2, ..., N $$求得最优解$$ alpha^* = ( alpha_1^, alpha_2^,..., alpha_N^*)^T$$

计算 $$w^* = sum_{i=1}^{N} alpha_i^* y_i x_i$$并选择(alpha)的一个正分量，计算$$b^* = y_j - sum_{i=1}^N alpha_i^*y_i(x_i cdot x_j)$$

求得分离超平面：$$w^* cdot x + b^* = 0$$分类决策函数$$f(x) = sign(w^* cdot x + b^*)$$

数据集中对应于(alpha_i > 0)的实例为支持向量，在间隔边界上。

线性支持向量机与软间隔最大化

对于线性不可分的数据，可以引入一个松弛变量(xi_i geq 0)，对约束条件放宽一点，同时在目标函数中给予相应的惩罚，这样，就得到了线性不可分的线性支持向量机的原始问题：

线性不可分支持向量机原始问题

[min_{w, b, xi} : : frac{1}{2} ||w||^2 + Csum_{i=1}^N xi_i$$$$s.t. : : y_i(w cdot + b) geq 1 - xi_i, i=1,2, ..., N$$$$xi_i geq 0, i = 1,2,...,N ]

与线性可分支持向量机一样，可以得到线性支持向量机相应的对偶问题，

线性支持向量机学习算法（对偶）

选择惩罚参数(C > 0)，构造并求解凸二次规划问题$$min_{alpha} :: 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.:: sum_{i=1}^{N} alpha_i y_i = 0$$ $$0 leq alpha_i leq C, i = 1, 2, ..., N $$求得最优解$$ alpha^* = ( alpha_1^, alpha_2^,..., alpha_N^*)^T$$

计算 $$w^* = sum_{i=1}^{N} alpha_i^* y_i x_i$$并选择(alpha)的一个大于0小于(C)的分量，计算$$b^* = y_j - sum_{i=1}^N alpha_i^*y_i(x_i cdot x_j)$$

求得分离超平面：$$w^* cdot x + b^* = 0$$分类决策函数$$f(x) = sign(w^* cdot x + b^*)$$

这时的线性支持向量机原始最优化问题等价于合页损失函数最小化问题$$min_{w,b} :: sum_{i=1}^N [1 - y_i(w cdot x_i + b)]_+ + lambda ||w||^2$$，合页损失函数长得像合页，是0-1损失函数的上界。

非线性支持向量机与核函数

在处理非线性问题的时候，可以把原空间映射到新的空间，这是的数据可能就线性可分了，这是就能在新空间中学习分类模型。

核函数的定义

设(mathcal{X})是输入空间（欧氏空间的子集或离散集合），(mathcal{H})为特征空间（希尔伯特空间），如果存在一个从(mathcal{X})到(mathcal{H})的映射$$phi(x): mathcal{X} ightarrow mathcal{H}$$使得对所有的(x, z in mathcal{X})，函数(K(x, z) = phi(x) cdot phi(z))

核技巧的想法是，在学习与预测中只定义核函数(K(x,z))，而不显式地定义映射函数(phi)，用一些合适的(K(x,z))，计算起来容易。在支持向量机的对偶问题中，目标函数与决策函数都只涉及实例与实例之间的内积，可以用核函数(K(x_i, x_j) = phi(x_i) cdot phi(x_j))来代替。

常用的核函数
- 多项式核函数
  [K(x, z) = (x cdot z + 1)^p$$对应的支持向量机是一个p次多项式分类器，分类决策函数为$$f(x) = sign(sum_{i=1}^{N_s} a_i^* y_i (x_i cdot x + 1)^p + b^*) ]
- 高斯核函数
  [K(x, z) = exp(-frac{||x-z||^2}{2sigma^2})$$对应的支持向量机是高斯径向基函数分类器，分类决策函数为$$f(x) = sign((sum_{i=1}^{N_s} a_i^* y_i exp(-frac{||x-z||^2}{2sigma^2}) + b^*) ]
- 字符串核函数
  离散的字符串集合中的核函数，在文本分类、信息检索中可以应用。

非线性支持向量机学习算法

选择适当的核函数(K(x, z))和适当的参数(C)，构造并求解最优化问题$$min_{alpha} :: frac{1}{2} sum_{i=1}^{N}sum_{j=1}^{N} alpha_i alpha_j y_i y_j K(x_i, x_j) - sum_{i = 1}^{N}alpha_i$$$$s,t.:: sum_{i=1}^{N} alpha_i y_i = 0$$ $$0 leq alpha_i leq C, i = 1, 2, ..., N $$求得最优解$$ alpha^* = ( alpha_1^, alpha_2^,..., alpha_N^*)^T$$

选择(alpha)的一个大于0小于(C)的分量，计算$$b^* = y_j - sum_{i=1}^N alpha_i^*y_iK(x_i cdot x_j)$$

构造决策函数：$$f(x) = sign(sum_{i=1}^N alpha_i^* y_i K(x cdot x_i) + b^*)$$

序列最小最优化算法（SMO）
求解支持向量机中的凸二次规划问题，数据量很大时，需要这些快速实现算法。SMO算法不断地将原二次规划问题分解为只有两个变量的二次规划子问题，并对子问题进行解析求解，直到所有变量满足KKT条件为止。这种通过启发式的方法得到最优解，因为子问题有解析，所以很有效。

(注：本文为读书笔记与总结，侧重算法原理，来源为[《统计学习方法》](http://book.douban.com/subject/10590856/)一书第七章)
作者：[rubbninja](http://www.cnblogs.com/rubbninja/) 出处：[http://www.cnblogs.com/rubbninja/](http://www.cnblogs.com/rubbninja/) 关于作者：目前主要研究领域为机器学习与无线定位技术，欢迎讨论与指正！