美人迈兮音尘阙，隔千里兮共明月

临风叹兮将焉歇，川路长兮不可越

概述

支持向量机（SVM）是一个功能强大并且全面的机器学习模型，它能够执行线性分类、非线性分类、回归甚至是异常检测任务。SVM特别适合中小型复杂数据集的分类。

线性SVM分类

基本理论

左图是几个线性分类模型，其中虚线模型效果很差，橙、紫两个模型表现还凑合，但是太多实例在决策边界附近，泛化效果不理想。右图是SVM模型，可知这条线不仅分离了两个类别，还尽可能远离了最近的训练实例。SVM即可理解为在类别之间拟合最宽的街道（平行虚线所示）的模型，所以也叫大间隔分类。

SVM对特征缩放很敏感，如上图所示，缩放后，街道距离明显加宽，决策边界看起来好了很多。

软间隔分类

如果严格要求所有实例都不在街道上，且位于正确的一边，就叫做硬间隔分类。但是硬间隔分类对异常值很敏感，且要求训练实例是线性可分离的，如左图所示，这种情况就无法拟合硬间隔模型。如右图所示，有时候，硬间隔情况下，决策边界很窄，可能无法很好的泛化。因此，要解决这个问题，需要在保持街道宽阔和限制间隔违例（位于街道上，甚至在错误一边的实例）之间找到良好的平衡，这就是软间隔分类。
PS：在Sckilt-Learn的SVM类中，可以通过超参数C来控制这个平衡。C越小，街道越宽，违例越多；C越大，街道越窄，违例越少。

iris = datasets.load_iris()
X = iris['data'][:,(2,3)]#petal length, petal width
y = (iris['target'] == 2).astype(np.float64)

svm_clf = Pipeline([
	('scaler', StandardScaler()),
	('linear_svc', LinearSVC(C=1, loss='hinge'))
	])
svm_clf.fit(X, y)
svm_clf.predict([[5.5, 1.7]])

也可以使用SVC类，使用SVC(kernel=’linear’,C=1)，但这样会慢很多，对于大型数据集，不推荐。另一个选择是SGDClassifier(loss=’hinge’,alpha=1/(m*C))，这适用于常规随机梯度下降来训练SVM分类器，它不会像LinearSVC那样快速收敛，但对于内存处理不了的大型数据集（核外训练）或是在线分类任务，非常有效。

非线性SVM分类

基本理论

有时候，数据集并非线性可分的，则可以添加多项式特征，有可能使其变得线性可分，如上图所示。

X, y = datasets.make_moons()
polynomial_svm_clf = Pipeline([
	('poly_features', PolynomialFeatures(degree=3)),
	('scaler', StandardScaler()),
	('svm_clf', LinearSVC(C=10, loss='hinge'))
	])
polynomial_svm_clf.fit(X, y)

多项式核

添加多项式特征实现很简单，但可能会造成特征数量爆炸。而使用SVM时，可以使用核技巧来避免这个问题。

poly_kernel_scm_clf = Pipeline([
	('scaler', StandardScaler()),
	('svm_clf', SVC(kernel='poly', degree=3, coef0=1, C=5))
	])
poly_kernel_scm_clf.fit(X, y)

PS：如果过拟合，降低多项式参数；如果欠拟合，提高多项式参数。超参数coef0用与控制模型接受多项式影响的程度

添加相似特征

添加的相似特征经过相似函数算出，相似函数可以计算每一个实例与地标实例之间的相似度，以上图为例，在\(x_1=-2\)和\(x_1=1\)处设置坐标，以高斯径向基函数（RBF）作为相似函数，\(\gamma\)设置为0.3，则新特征分别是\(x_2=exp(-0.3\times1^2)\approx0.74\),\(x_3=exp(-0.3\times2^2)\approx0.3\)

高斯RBF：
\(\Phi\gamma(x,l)=exp(-\gamma||x-l||^2)\)

图中可知，转换过特征之后，训练集线性可分了。如何选择地标呢？最简单的方法是每一个实例都作为一个地标，但这会创造大量维度。

高斯RBF核函数

rbf_kernel_svm_clf = Pipeline([
	('scaler', StandardScaler()),
	('svm_clf', SVC(kernel='rbf', gamma=5, C=0.001))
	])
rbf_kernel_svm_clf.fit(X, y)

减小\(\gamma\)会使钟形曲线变窄，导致每个实例的影响范围变小，决策边界变的不规则，开始围绕单个实例绕弯；反过来，会使每个实例影响范围变大，决策边界变的平坦。因此，模型过拟合，降低其值；模型欠拟合，增大其值

计算复杂度

SVC适合复杂但中小型的数据集，不过面对特征数量增加尤其是稀疏特征时，其表现也很不错。

SVM回归

基本概念

SVM回归不再尝试拟合两个类别之间可能的最宽的街道的同时限制间隔违例，SVM回归要做的是要让尽可能多的实例位于街道上，同时限制间隔违例（不在街道上的实例）。街道宽度由\(\epsilon\)控制，其值越大，街道越宽。

PS：在间隔内添加更多的实例不会影响模型的预测，因此这个模型也被称作\(\epsilon\)不敏感

svm_reg = LinearSVR(epsilon=1.5)
svm_reg.fit(X, y)

解决非线性回归任务，可以使用核化的SVM模型。

svm_poly_reg = SVR(kernel='poly', degree=2, C=100, epsilon=0.1)
svm_poly_reg.fit(X, y)

工作原理

处理SVM时，约定偏置项表示为b，特征权重向量表示为w，同时输入特征中不添加偏置特征。

决策函数和预测

线性SVM分类器通过简单地计算决策函数\(w^t\cdot x + b = w_1 x_1 +…+w_n x_n + b\)来预测新实例x的分类，如果结果为正，则预测类为正类（1），不然预测其为负类（0）。


如上图所示，数据集包含两个特征，所以是一个二维平面，决策边界是决策函数等于0的点的集合：两个平面的交集，是一条直线。虚线是决策函数等于1与-1的点的集合，训练SVM分类器就是找到w和b的值，使虚线间间隔尽可能宽的同时，避免（硬间隔）或是限制（软间隔）间隔违例。

训练目标

决策函数的斜率等于权重向量的范数，即||w||，权重向量越小，间隔越大，如上图所示。
因此我们要最小化||w||来得到尽可能大的间隔。如果我们要避免间隔违例，就要使所有正类训练集的决策函数大于1，负类训练集决策函数小于-1。所以我们定义实例为负类时（\(y^i=0\)),\(t^i=-1\);实例为正类时（\(y^i=1\)),\(t^i=1\)。那么对所有实例来说，则有\(t^i \times (w^T \cdot x^i + b) \geq 1\)

所以硬间隔SVM分类问题其实是一个约束优化问题，其目标是：

要达到软间隔的目标，对每个实例引入一个松弛变量\(\zeta^i \geq 0\)，其表示第i个实例多大程度上允许间隔违例，同时还要使\(\frac{1}{2} w^T \cdot w\) 最小化以增大间隔。这正是超参数C的意义。软间隔约束优化目标是：

二次规划

硬间隔和软间隔问题都是属于线性约束的凸二次优化问题，即二次规划（QP）问题。此问题一般形式如下：

对偶问题

针对一个给定的约束优化问题，称之为原始问题，我们也可以使用一个不同的但与之密切相关的问题来表达，叫做对偶问题。通常对偶问题的解只能算原始问题的解的下限，但是，某些条件下，其解跟原始问题完全相同，SVM恰好满足这个条件。线性SVM目标的对偶形式如下：

一旦利用二次规划求解器得到使该等式最小化的向量\(\hat{a}\)，便可以利用以下公式来求得原始问题的最小化的\(\hat{w}\)和\(\hat{b}\)。

PS:当训练实例数量小于特征数量时，解决对偶问题比原始问题更快

核化SVM

如果我们想将一个二姐多项式转换成一个二维训练集，然后在转换训练集上训练线性SVM分类器，假设转换函数\(\phi\)如下：

转换后的向量是三维的，而不是二维的，如果两个二维向量进行映射会如何？

转换后向量的点积等于原始向量的点积的平方：\(\phi (a)^T \cdot \phi (b) = (a^T \cdot b)^2\)
如果将映射\(\phi\)应用于所有训练实例，那么对偶问题将包含点积\(\phi (x^i)^T \cdot \phi (x^j)\)的计算，如果\(\phi\)是上面的转换映射，就可以使用\(((x^i)^T \cdot (x^j))^2\)来替代，就不用转换训练实例了。这个过程大大提高了计算效率，这就是核技巧的本质。

\(K(a,b)=(a^T \cdot b)^2\) 是二阶多项式核，核就是能仅基于原始向量来计算点积\(\phi (a)^T \cdot \phi (b)\)的函数。

如下是一些常用的核：

使用核化SVM作出预测：

使用核化SVM计算偏置项：

在线SVM

对于线性SVM来说，增量训练可以使用梯度下降进行成本函数最小化，但速度比二次规划慢很多。成本函数如下：

成本函数的第一项会推动模型得到一个较小的权重向量w，从而使间隔增大；第二项则用于计算全部的间隔违例，此项最小化，能保证间隔违例尽可能少。

总结

• 支持向量机是尽可能使决策边界宽阔的同时，使间隔违例比较少的模型
• 支持向量是位于决策边界上的实例
• 输入值的缩放直接影响支持向量机的决策边界宽度

• Previous
  机器学习（四）
• Next
  机器学习（六）