支持向量机(svm)
1.背景：
1.1最早是由Vladimir N. Vapnik 和 Alexey Ya. Chervonenkis 在1963年提出
1.2目前的版本(soft margin)是由Corinna Cortes 和 Vapnik在1993年提出，并在1995年发表
1.3深度学习（2012）出现之前，svm被认为机器学习中近十几年来最成功，表现最好的算法
2.机器学习的一般框架：
训练集=>提取特殊向量=>结合一定的算法（分类器：比如决策树，KNN）=>得到结果
3.介绍
3.1例子：
将以上的点分为两类，哪条线划分最好？
3.2 SVM目的是寻找区分两类的超平面(hyper plane),使边际（margin）最大
总共可以有多少个可能的超平面？无数条如何选取使边际（margin）最大的超平面（Max Margin Hyperplane）超平面到一侧最近点的距离等于到另一侧最近点的距离，两侧的两个超平面平行
4.线性可区分(linear separable) 和 线性不可分 （linear inseparable）
以下两图例为线性不可区分，无法找到一条线进行类别区分
5.定义与公式建立
超平面可以定义为：
W*X + b =0
W:weight vectot(向量),
W = {w1,w2,...,wn}
n是特征值的个数
X：训练实例
b : bias
5.1假设2维特征向量：X = (x1,x2)
把b想象为额外的 wight -> w0
超平面方程变为：w0 + w1*x1 + w2*x2 = 0
所有超平面右上方的点满足： w0 + w1*x1 + w2*x2 > 0
所有超平面左下方的点满足： w0 + w1*x1 + w2*x2 < 0
调整weight (w0),使超平面定义边际的两边：
定义yi 为分类值，代表分类结果值
H1 : w0 + w1x1 + w2x2 >= 1 for yi = +1
H2 : w0 + w1x1 + w2x2 <= -1 for yi = -1
综合以上两式，得到：
所有坐落在边际的两边的超平面上的点被称作"支持向量(support vectors)"
分界的超平面和H1或H2上任意一点的距离为
（i.e : 其中||w||是向量的范围"norm")
所以最大边际距离为：
6.求解(线性可区分 linear separable )
6.1 SVM如何找出最大边际的超平面呢（MMH）？
利用一些数学推倒，以上公式
可变为有限制的凸优化问题(convex quadraticoptimization)
利用Karush-Kuhn-Tucker(KKT)条件和拉格朗日公式，推出MMH可以被表示为以下“决定边界(decision boundary)”
其中，yi是支持向量点; Xi为支持向量的类别标记(class label);
6.2 对于任何测试实例，带入以上公式，得出的符号是正还是负，根据结果值对实例分类处理
7.SVM算法图示(线性可区分 linear separable )：
8.SVM算法特性
8.1训练好的模型算法复杂度是由支持向量的个数决定的，而不是由数据的维度决定的。所以SVM不太容易产生overfitting
8.2SVM训练出来的模型完全依赖于支持向量（support vectors）,即使训练集里面所有非支持向量的点都被去除，重复训练过程，结果仍然会得到完全一样的模型。
8.3一个SVM如果训练得出的支持向量个数比较小，SVM训练出的模型比较容易被泛化。
９.线性不可分的情况（linearly inseparable case）
９.１数据集在空间中对应的向量不可被一个超平面区分开
９.２两个步骤来解决：
９.２.１利用一个非线性的映射把原数据集中的向量点转化到一个更高维度的空间中
９.２.２在这个高维度的空间中找一个线性的超平面来根据线性可分的情况处理
图示１：
图示２：
９.３ 如何利用非线性映射把原始数据转化到高维中？
9.3.1 例子：
3维输入向量：
X = (x1,x2,x3)
转化到6维空间Z中去：
新的决策超平面：
d(Z) = WZ + b.
其中W和Z是向量，这个超平面是线性的
解出W和b之后，并且带入回原方程:
d(Z)=w1x1+w2x2+w3x3+w4(x1*x1)+w5x1x2+w6x1x3+b
=w1z1+w2z2+w3z3+w4z4+w5z5+w6z6+b
9.3.2思考问题：
9.3.2.1：如何选择合理的非线性转化把数据转化到高纬度中？
9.3.2.2：如何解决计算内积时算法复杂度非常高的问题？
为了降低内积计算复杂度需要使用核函数(kernel trick)
10.核方法（kernel trick）
10.1动机
在线性SVM中转化为最优化问题时求解的公式计算都是以内积（dot product）的形式出现的
其中
是把训练集中的向量点转化到高维的非线性映射函数，因为内积的算法复杂度非常大，所以我们利用核函数来取代计算非线性映射函数的内积。
10.2以下核函数和非线性映射函数的内积等同
10.3常用的核函数（kernel functions）
h度多项式核函数(polynomial kernel of degree h):
高斯径向基核函数(Gaussian radial basis function kernel):
S型核函数(Sigmoid function kernel):
如何选择使用哪个kernel?
根据先验知识，比如图像分类，通常使用RBF，文字不使用RBF尝试不同的kernel,根据结果准确而定
10.4核函数与常规算法对比：
假设定义两个向量：x=(x1,x2,x3);y=(y1,y2,y3)
定义方程：f(x)=(x1x1,x1x2,x1x3,x2x1,x2x2,x2x3,x3x1,x3x2,x3x3)
假设x=(1,2,3);y=(4,5,6).
使用传统算法计算如下：
f(x)=(1,2,3,2,4,6,3,6,9)
f(y)=(16,20,24,20,25,30,24,30,36)
<f(x),f(y)> = 16+40+72+40+100+180+72+180+324=1024
使用核函数算法如下：
K(x,y)=(4,10,18)^2 = 32^2 = 1024
同样的结果，使用kernel方法将计算复杂度大大降低了
10.5 SVM扩展可解决多个类别分类问题
通过某种方式构造一系列的两类分类器并将它们组合在一起来实现多类分类；
将多个分类面的参数求解合并到一个最优化问题中，通过求解该最优化问题“一次性”的实现多类分类器结构方法