SVM原理（1）

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例子：

220px-Svm_separating_hyperplanes_(SVG).svg.png

图中哪条线对于区分两类小球好呢？
3.2 SVM寻找区分两类的超平面（hyper plane), 使边际(margin)最大

Image [4].png

总共可以有多少个可能的超平面？无数条

如何选取使边际(margin)最大的超平面 (Max Margin Hyperplane)？

超平面到一侧最近点的距离等于到另一侧最近点的距离，两侧的两个超平面平行

3.3. 线性可区分(linear separable) 和 线性不可区分 （linear inseparable)

images [1].jpg
images.jpg

有两类，分别是线性可区分和线性不可区分，我们先讲线性可区分

Image [1].png

4. 定义与公式建立

超平面可定义为：

Image [2].png

w: weight vector

Image [3].png
n是特征值的个数。

X是训练实例
b：bias

4.1 假设2维特征向量：X = (x1, X2)

把 b 想象为额外的 wight

超平面方程变为：

Image [5].png

所有超平面右上方的点满足：

Image [6].png

所有超平面左下方的点满足：

Image [7].png

调整weight，使超平面定义边际的两边：

Image [8].png

综合以上两个式子得到：

Image [9].png

决定决策边界的数据叫做支持向量，它决定了margin到底是多少
分界的超平面和H1或H2上任意一点的距离为 ：

屏幕快照 2018-09-03 下午2.42.58.png

(i.e.: 其中||W||是向量的范数(norm))

Image [11].png

所以，最大边际距离为：

屏幕快照 2018-09-03 下午2.44.49.png

5. 求解

5.1 SVM如何找出最大边际的超平面呢(MMH)？
利用一些数学推倒，以上公式 （1）可变为有限制的凸优化问题(convex quadratic optimization)
利用 Karush-Kuhn-Tucker (KKT)条件和拉格朗日公式，可以推出MMH可以被表示为以下“决定边界 (decision boundary)”

Image [13].png

其中，
yi是支持向量点xi的类别标记
X^T是要测试的实例

具体的公式推导，可以自己在纸上推到试试。

6 ，例子

Image [14].png
Image [15].png