边际（margin）是什么？
：边际就是某一条线距离它两侧最近的点的距离之和。
比如下图中两条虚线构成的带状区域就是 margin，虚线是由距离中央实线最近的两个点所确定出来的。但此时 margin 比较小，如果用第二种方式画，margin 明显变大也更接近我们的目标。
【机器学习算法】SVM
为什么要让 margin 尽量大？
：因为大 margin 犯错的几率比较小

如何选取使边际最大的超平面（Max Margin Hyperplane，简称 MMH）？
：超平面到一侧最近点的距离等于到另一侧最近点的距离，两侧的两个超平面平行

SVM 算法特性

训练好的模型的算法复杂度是由支持向量的个数决定的，而不是由数据的维度决定的。所以 SVM 不太容易产生 overfitting。
SVM 训练出来的模型完全依赖于支持向量，即使训练集里面所有非支持向量的点都被去除，重复训练过程，结果仍然会得到完全一样的模型。
一个 SVM 如果训练得出的支持向量个数比较少，那么SVM 训练出的模型比较容易被泛化。

SVM 定义与公式建立

超平面可以定义为： $w^TX+b=0$

W：权重向量， $w = \{w_1,w_2, ..., w_n\}$ ，n 是特征值的个数
X：训练实例
b：bias 偏向

假设2维特征向量： $X = (x1, x2)$
【机器学习算法】SVM
把 b 看作额外的 wight，记作 $w_0$
则超平面方程为： $w_0+w_1x_1+w_2x_2=0$

所有超平面右上方的点满足： $w_0+w_1x_1+w_2x_2>0$
所有超平面左下方的点满足： $w_0+w_1x_1+w_2x_2<0$

调整 weight，使超平面定义如下：
$H1:w_0+w_1x_1+w_2x_2\geq1\ \ \ \ \ for\ y_i=+1$
$H2:w_0+w_1x_1+w_2x_2\leq-1\ \ \ \ \ for\ y_i=-1$

综合以上两式，得到： $y_i*(w_0+w_1x_1+w_2x_2)\geq1,\ \forall i$

所有坐落在边际超平面上的点被称作支持向量(support vectors)

含义： 支持向量（support vector）就是刚好贴在边际所在的平面上的点，它们是用来定义边际的，是距离划分超平面最近的点。

作用： 支持向量因为支撑了边际区域，并且用于建立划分超平面。

注意： 支持向量可能不止一侧一个，有可能一侧有多个点都贴在边际平面上。

划分超平面和它两侧的边际超平面上任意一点的距离为 $\frac{1}{||w||}$ (i.e.: 其中 $||w||$ 是向量的范数(norm))

所以，最大边际距离为： $\frac{2}{||w||}$

推导过程待补充。

SVM 求解过程

SVM 如何找出有最大边际的超平面呢（MMH）？
利用一些数学推导，公式 $y_i*(w_0+w_1x_1+w_2x_2)\geq1,\ \forall i$ 可变为有限制的凸优化问题(convex quadratic optimization)

利用 Karush-Kuhn-Tucker (KKT)条件和拉格朗日公式，可以推出 MMH 可以被表示为以下“决定边界 (decision boundary)”
$d(X^T)=\sum_{i=1}^ly_i\alpha_iX_iX^T+b_0$
此方程就代表了边际最大化的划分超平面。

$l$ 是支持向量点的个数，因为大部分的点并不是支持向量点，只有个别在边际超平面上的点才是支持向量点。那么我们就只对属于支持向量点的进行求和；
$X_i$ 为支持向量点的特征值；
$y_i$ 是支持向量点 $X_i$ 的类别标记（class label)，比如+1还是-1；
$X^T$ 是要测试的实例，想知道它应该属于哪一类，把它带入该方程
$\alpha _i$ 和 $b_0$ 都是单一数值型参数，由以上提到的最优算法得出， $\alpha _i$ 是拉格朗日乘数。

每当有新的测试样本 $X$ ，将它带入该方程，看看该方程的值是正还是负，根据符号进行归类。

SVM 求解案例

看一下 SVM 如何求出一个划分超平面。

我们已经知道了两个支持向量点（1,1）和（2,3），设置权重为 $w = (a,2a)$ ，那么将这两个支持向量点坐标分别带入公式 $w^Tx+b=\pm1$ 中，可以得到：
$a+2a+w_0=-1,\ \ \ using\ point\ (1,1)$
$2a+6a+w_0=1,\ \ \ using \ point\ (2,3)$
那么未知数就是 $a$ 和 $w_0$ ，解方程组可得： $a=\frac{2}{5}$ ， $w_0=-\frac{11}{5}$
带回到权重向量 $w$ 中有： $w=(a,2a)=(\frac{2}{5},\frac{4}{5})$
那么划分超平面为 $x_1+2x_2-5.5=0$
最后可以用点（2,0）验证一下这个划分超平面的分类效果。
【机器学习算法】SVM

SVM 应用实例

由于 SVM 算法本身的实现非常复杂，所以这里不研究自己如何实现 SVM，而仍采用 sklearn 库来帮助我们学习 SVM 的应用问题。

sklearn 简单例子

# sklearn 库中导入 svm 模块
from sklearn import svm

# 定义三个点和标签
X = [[2, 0], [1, 1], [2,3]]
y = [0, 0, 1]
# clf 意为 classifier，定义一个分类器的传统命名
clf = svm.SVC(kernel = 'linear')  # .SVC（）就是 SVM 的方程，参数 kernel 为线性核函数
clf.fit(X, y)  # 调用分类器的 fit 函数建立模型（即计算出划分超平面，且所有相关属性都保存在了分类器 cls 里）

# 打印分类器 clf 的一系列参数
print (clf)

# 支持向量
print (clf.support_vectors_)

# 属于支持向量的点的 index 
print (clf.support_)

# 在每一个类中有多少个点属于支持向量
print (clf.n_support_) 

# 预测一个新的点
print (clf.predict([[2,0]]))

输出结果：

SVC(C=1.0, cache_size=200, class_weight=None, coef0=0.0,
  decision_function_shape='ovr', degree=3, gamma='auto_deprecated',
  kernel='linear', max_iter=-1, probability=False, random_state=None,
  shrinking=True, tol=0.001, verbose=False)
[[1. 1.]
 [2. 3.]]
[1 2]
[1 1]
[0]

可以看到 SVM 找到的支持向量是（1,1）和（2,3）两个点，和我们上面的例子是符合的
输出的属于支持向量的点的 index 就是 1 和 2
由于找到了两个支持向量分别属于正类和负类，所以输出的每个类中属于支持向量的点的个数就是 1 和 1

sklearn画出决定界限

print(__doc__)

import numpy as np
import pylab as pl  # 画图功能
from sklearn import svm

# 创建 40 个点
np.random.seed(0) # 让随机值不变
# 生成训练实例并保证是线性可分的
X = np.r_[np.random.randn(20, 2) - [2, 2], np.random.randn(20, 2) + [2, 2]]
# 两个类别 每类有 20 个点
Y = [0] * 20 + [1] * 20

# 建立 svm 模型
clf = svm.SVC(kernel='linear')
clf.fit(X, Y)

# 获得划分超平面
w = clf.coef_[0]  # w 是一个二维数据
a = -w[0] / w[1]  # 斜率
xx = np.linspace(-5, 5)  # 产生一些连续的值
yy = a * xx - (clf.intercept_[0]) / w[1]  # 获得直线方程

# 画出和划分超平面平行且经过支持向量的两条线
b = clf.support_vectors_[0]
yy_down = a * xx + (b[1] - a * b[0])
b = clf.support_vectors_[-1]
yy_up = a * xx + (b[1] - a * b[0])


print("w: ", w)
print("a: ", a)
# print " xx: ", xx
# print " yy: ", yy
print("support_vectors_: ", clf.support_vectors_)
print("clf.coef_: ", clf.coef_)

# In scikit-learn coef_ attribute holds the vectors of the separating hyperplanes for linear models. It has shape (n_classes, n_features) if n_classes > 1 (multi-class one-vs-all) and (1, n_features) for binary classification.
# 
# In this toy binary classification example, n_features == 2, hence w = coef_[0] is the vector orthogonal to the hyperplane (the hyperplane is fully defined by it + the intercept).
# 
# To plot this hyperplane in the 2D case (any hyperplane of a 2D plane is a 1D line), we want to find a f as in y = f(x) = a.x + b. In this case a is the slope of the line and can be computed by a = -w[0] / w[1].


# plot the line, the points, and the nearest vectors to the plane
pl.plot(xx, yy, 'k-')
pl.plot(xx, yy_down, 'k--')
pl.plot(xx, yy_up, 'k--')

pl.scatter(clf.support_vectors_[:, 0], clf.support_vectors_[:, 1],
           s=80, facecolors='none')
pl.scatter(X[:, 0], X[:, 1], c=Y, cmap=pl.cm.Paired)

pl.axis('tight')
pl.show()

输出结果：

Automatically created module for IPython interactive environment
w:  [0.90230696 0.64821811]
a:  -1.391980476255765
support_vectors_:  [[-1.02126202  0.2408932 ]
 [-0.46722079 -0.53064123]
 [ 0.95144703  0.57998206]]
clf.coef_:  [[0.90230696 0.64821811]]

【机器学习算法】SVM

核方法（kernel trick)

使用核方法的动机

在线性 SVM 中转化为最优化问题时求解的公式计算都是以内积(dot product)形式出现的，其中 $\phi(X)$ 是把训练集中的向量点转化到高维的非线性映射函数，因为内积的算法复杂度非常大，所以我们利用核函数来取代计算非线性映射函数的内积。

以下核函数和非线性映射函数的内积等同，但核函数 K 的运算量要远少于求内积。
$K(X_i,X_j)=\phi(X_i)·\phi(X_j)$

常用的核函数（kernel functions）

h 度多项式核函数(polynomial kernel of degree h)：
$K(X_i,X_j)=(X_i,X_j+1)^h$

高斯径向基核函数(Gaussian radial basis function kernel)：
$K(X_i,X_j)=e^{-||X_i-X_j||^2/2\sigma^2}$

S 型核函数(Sigmoid function kernel)：
$K(X_i,X_j)=tanh(kX_i·X_j-\delta)$

如何选择使用哪个 kernel ？

根据先验知识，比如图像分类，通常使用 RBF（高斯径向基核函数），文字不使用 RBF。
尝试不同的 kernel，根据结果准确度而定尝试不同的 kernel，根据结果准确度而定。

核函数举例

假设定义两个向量： $x = (x_1, x_2, x_3)$ ， $y = (y_1, y_2, y_3)$

定义方程：
$f(x) = (x_1x_1, x_1x_2, x_1x_3, x_2x_1, x_2x_2, x_2x_3, x_3x_1, x_3x_2, x_3x_3)$

核函数： $K(x,y ) = (<x,y>)^2$

假设： $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, 36, 24, 30, 36)$
$<f(x), f(y)> = 16 + 40 + 72 + 40 + 100+ 180 + 72 + 180 + 324 = 1024$