SVM 支持向量机

svm,support vector machine，可用于模式分类和非线性回归。

支持向量机的主要思想是建立一个分类超平面作为决策曲面,使得正例和反例之间的隔离边缘被最大化。支持向量机的理论基础是统计学习理论,更精确的说,支持向量机是结构风险最小化的近似实现。这个原理基于这样的事实:学习机器在测试数据上的误差率(即泛化误差率)以训练误差率和一个依赖于vc维数(vapnik-chervonenkis dimension)的项的和为界,在可分模式情况下,支持向量机对于前一项的值为零,并且使第二项最小化。因此,尽管它不利用问题的领域内部问题,但在模式分类问题上支持向量机能提供好的泛化性能,这个属性是支持向量机特有的。

二分类问题中，n个数据点的数据集共有2n种排列可能，若对于其中的任意一个排列，假设空间h总能够将两类数据点分开，那么就说vc(h)=n。比如二维空间中，假设空间h是直线，它的vc维就是3。

vc维是对假设h(hypothesis)的解决问题的能力的度量。

这个与问题真实解之间的误差，就叫做风险（更严格的说，误差的累积叫做风险）。真实风险应该由两部分内容刻画，一是经验风险，代表了分类器在给定样本上的误差；二是置信风险，代表了我们在多大程度上可以信任分类器在未知文本上分类的结果。很显然，第二部分是没有办法精确计算的，因此只能给出一个估计的区间，也使得整个误差只能计算上界，而无法计算准确的值（所以叫做泛化误差界，而不叫泛化误差）。

一般地，如果一个线性函数能够将样本完全正确的分开，就称这些数据是线性可分的，否则称为非线性可分的。

什么叫线性函数呢？在一维空间里就是一个点，在二维空间里就是一条直线，三维空间里就是一个平面，可以如此想象下去，如果不关注空间的维数，这种线性函数还有一个统一的名称——超平面（hyper plane）！

c-svc模型是比较常见的二分类支持向量机模型，其具体形式如下：

1)设已知训练集:

t={x⃗ ,d}

其中x⃗ i∈x=rn,y⃗ i∈y={1,−1},(i=1,...,n);x⃗ i为特征向量

2)构造并求解问题：

找到权重矩阵（列向量）w⃗ 和偏置b，使得w⃗ tx⃗ +b=0，也即di(w⃗ tx⃗ i)≥0。那么数据点离超平面的距离为distance=di(w⃗ tx⃗ i+b)||w⃗ ||。为了提高泛化性能，令分类平面的边缘至少大于某个ρ。我们希望最大化ρ，同时缩放w，我们可以得到无限多个解。为了得到唯一解，我们固定ρ||w⃗ ||=1，至此，要求解的任务可以定义为

min12||w⃗ ||2，受限于di(w⃗ tx⃗ i+b)≥1,∀i ( 13.3)

这是一个标准的二次优化问题。对于不等式约束的条件极值问题，可以用拉格朗日方法求解。而拉格朗日方程的构造规则是：用约束方程乘以非负的拉格朗日系数，然后再从目标函数中减去。于是得到拉格朗日方程如下：

lp=12||w⃗ ||2−∑nt=1αt[di(w⃗ tx⃗ i+b)−1] (13.4)

这里应当关于w,b最小化，并关于αt≥0最大化。鞍点给出解。

这是一个凸二次优化问题，直接解有困难，可以通过拉格朗日对偶问题来解决，为此我们把（13.4）式做一个等价变换：

结束。(latex写的好累 啊)