本文纯理论，来源于 Andrew Ng 公开课和李航的《统计学习方法》。Support Vector Machine 简称SVM，是一种二元(binary)线性分类，核心就是求出一个线性超平面完美的将测试数据分成两类，正例和负例，如图中直线就是一个超平面，X 代表正例，O 代表负例。如果测试数据落在A点，那么就有很大程度确信 A 属于正例，对于落 在C点的数据就没那么确信，B点介于A, C 之间。SVM的核心：以充分大的确信度对训练数据进行划分
有两个概念比较烦:
- 支持向量: 支持或支撑平面上，把测试数据划分两类的点。也就是离超平面最近的正负例点，又因为这些点是 N 维的向量，所以这几个有限点叫支持向量
- 超平面: 如果二维的，那么将测试数据分类的就是一条直线，如果是三维的就是一个平面，更高维的虽然无法直观对应物理模型，但道理一样的。统一称为超平面(hyperplane)
回顾 Logistic Regression
Logistic 回归无论二分，还是多元分类，都是使用 Sigmoid 函数将h(θ) 从负无穷到正无穷压缩到(0,1)
hθ(x) =g(θTx)
其中g(z) 就是我们熟知的 Sigmoid 函数 g(z)=1/(1+e^(-z))
可以看到 g(z) 将 θTx 从 (-∞, +∞) 映到到 (0,1), 从而将回归问题转换到概率问题，对于标记 y=1的概率
p{y=1|x,θ} = hθ(x)
对于标记 y=0的概率
p{y=0|x,θ} = 1-hθ(x)
当验证数据大于0.5时，就划分为y=1的类，否则标记为 y=0. 实际上抛开 Sigmoid 函数，θTx >0 那么 y=1, θTx < 0 判定 y=0
新的约定
SVM 会有些改变，将结果y标记由(0, 1) 替换为 {1, -1}, 同时将 θ 替换为 w 和b ,其中 θ, w 是向量，b是截距常数。
θTx= θ0 + θ1x1 + θ2x2 + ....
替换为
θTx= b + w1x1 + w2x2 + ....
将 intercept 从 θ 中剥离出来变成 b, 新的函数变成
hw,b(x) = g(w·x + b)
很好理解，实质是一样的，但是为什么要做新的约定呢？后面会看到 y 值替换为 {1,-1} 可以创建一个拉格朗日约束，而 w, b 又是构造超平面的两要素，w 是超平面的法向量，用于确定平面方向，而b是截距，用来确定满足这个方向的唯一平面。
线性分类形象化表示
笔记开篇就是一个线性分类，下图的也是，一个二维平面(超平面，二维空间中就是一条直线)，坐标内有两类点，红颜色和蓝颜色，完全被红颜色直线分隔。
我们定义这个红颜色直线(超平面)为 w·x + b = 0, 也就是说分隔函数为 f(x) = w·x + b, 对于超平面上方的点有 f(x) >0,并且 y ＝1(人为标记成1)，对于下方的点 f(x) < 0, 并且 y = -1, 对于超平面上的点的 有 f(x) = 0.
函数间隔与几何间隔
如何确定这样的超平面呢？答案是让支持向量到超平面的距离尽可能最大，这样有更好的泛化能力。
函数间隔 functional margins
对于给定训练数据 (xi, yi), 我们定如下公式为函数间隔，其中 xi 是特征向量，yi 是我们标记的数据 {1, -1}, 如果 xi 在超平面上方，那么 w·x + b > 0, yi =1 所以函数间隔大于0，同样如果样本 xi 位于下方，那么 w·x + b <0 , yi = -1, 函数间隔仍然大于0. 后面会用到这个约束。
对于给定训练集，到超平面 w·x + b ＝0 的函数距离为所有点到超平面最小的距离
我们的目标就是寻找，使这个最小距离尽可能取最大值时的 w 和 b. 稍微有些绕 ... 但是函数间隔有个最大问题，会随着 w, b 等比缩放。比如对于超平面 2w·x + 2b ＝0, 同样满足需求，但此时函数间隔也会放大 2 倍。所以我们要使用几何间隔
几何间隔 geometric margins
回想一下高中知识，求点 (x0,y0)到直线 ax + by + c = 0的距离公式，就是几何间隔在二维的特殊形式
推广到 N 维空间，点(x,y) 到超平面w·x + b ＝0的距离公式
由此可以看到几何间隔就是函数间隔除以||w||, 即 w 向量的L2范数，也就是向量 w 每个元素的平方和的开方。那么此时我们的几何间隔不会随着 w和b 而等比缩放，始终固定。其实也很好理解，函数间隔就是 |f(x)| ，是我们人为定义的，而几何间隔才是真正广义空间的距离。
此时 SVM 的目标，就是寻找使测试样本中几何间隔最小的值，尽可能最大的 w 和 b
如上图所示，用我们高中的知识就知道，两类测试数据 1，2，3最接近，使样本中几何间隔最小的距离尽可能最大的，就是中间的红色直线(好绕口... ) 此时几何间隔就是
由于 w, b 的等比收缩对几何间隔没有影响，那么我们将w, b收缩成一个值，使 w·x + b ＝ 1，也就是说三个支持向量点 1，2，3距离超平面(中间红线)的距离相等且为1。那么此时几何间隔就变成了 1/||w||, 即最终寻找 w, b 使满足
max min 1/||w||
约束为
w·x + b ＝ 1
由于求 1/||W|| 最大值，但该式数学处理上不方便，那么转换成求 ||w||^2/2 的最小值，且满足对于所有点有 yi(w·xi + b ) - 1 >= 0, 原理很简单，表达方式有些绕口
由此求出了 SVM 的目标函数。
举个小例子
内容来自李航的书。如图所示三个训练数据，正例 x1=(3,3), x2=(4,3), 负例 x3=(1,1), 试求最大间隔分离超平面
根据所学的理论，x1, x3 是所谓的支持向量，x2 对解w, b 没有贡献，得到目标函数如下
min (w1^2 + w2^2)/2
约束如下
w1 + w2 + b = -1
3w1 + 3w2 + b = 1
由以上约束得到 b = -2, w1 + w2 =1
代入目标函数有
min 2w1^2 - 2w1 + 1
上面就是普通的一元二次函数，求导后得到当 w1 = 1/2 时值最小，那么 w2 = 1/2 ，得到超平面为 (1/2,1/2)·x -2 =0
注：由于书写格式问题 w1, w2 是矢量，w 是向量，x 是特征向量。
