SVM支持向量机：分类、回归和核函数

本文内容，参考了机器学习实战：基于Scikit-Learn和Tensorflow一书。

SVM可以执行线性和非线性分类、回归或者异常值检测任务，适用于中小型复杂数据。

线性SVM分类

如下图的大间隔分类所示：右图的实线（决策边界）尽可能的远离训练实例。
SVM对特征缩放敏感：
1. 软间隔/硬间隔分类
硬间隔：在数据是线性可分离时才有效；对异常值敏感。
左图，由于有异常值，硬间隔无法分类；右图的边界则无法很好泛化。
软间隔：在Scikit-Learn的SVM分类中，可以通过超参数C值来控制平衡：C值越小，则街道越宽。

import numpy as np
from sklearn import datasets
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import LinearSVC

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

svm_clf = Pipeline(
    [
        ('scaler', StandardScaler()),
        ('line_svc', LinearSVC(C=1, loss='hinge')),
    ]
)

svm_clf.fit(X, y)
print(svm_clf.predict([[5.5, 1.7]]))     # [[1.0]]

要训练SVM，还可以选择SVC(kernel='liner',C=1)，但这个很慢，不适合与大型训练集。也可以选择SGDClassifier(loss='hinge',alpha=1/(m*C))，它不能像LinerSVC那样快速收敛，但对于内存处理不力的大型数据集（核外训练）或在线分类任务，则非常有效。
LinearSVC类会对偏置项进行正则化，所以你需要先减去平均值，使训练集集中。可以使用StandardScaler，loss参数设置为’hinge’,还也可以将dual设置为False来获得更好性能。

非线性SVM分类

处理非线性数据集的方法之一是添加更多特征，比如多项式特征，在某些情况下，可以使数据集线性可分离。如下图：左图只有一个特征x1，右图添加一个特征x2=(x1)^2。

from sklearn.datasets import make_moons
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import PolynomialFeatures

polynomial_svm_clf = Pipeline([
    ('poly_features', PolynomialFeatures(degree=3)),
    ('scaler', StandardScaler()),
    ('svm_clf', LinearSVC(C=0.2, loss='hinge', max_iter=100000)),      # 次数过小会不收敛
])

X, y = make_moons(n_samples=1000, noise=None, random_state=42, shuffle=True)
polynomial_svm_clf.fit(X, y)

多项式核

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

超参数coef0控制的是模型受高阶多项式的还是地接多项式的影响程度。

添加相似特征
特征经相似函数计算得出，相似函数可以测量每个实例与特定地标之间的相似度。
- 高斯RBF(高斯径向基函数):
  $ϕ γ X, ℓ) = e x p (- ℓ ∣ ∣ X - ℓ ∣ ∣^{2})$ 在上图可以看到，x=-1与其中一个地标距离为1，另一个距离为2。这里γ=0.3，计算得x2=eps（-0.3×12）≈0.74，x3=eps（-0.3×22）≈0.30。转换后的数据特征如右图。此时，已经可以线性分离了。
  那么如何选择地标呢？一个简单的方法是在数据集中每个实例位置创建一个地标。但这会创造出许多维度，因而增加了转换后的训练集的线性可分离的机会。缺点是m个实例n个特征的训练***被转换为一个m个实例m个特征的训练集。如果训练集很大，则会得到同样大数量的特征。
- 高斯RBF核函数
  增加gamma值会使钟形曲线变得更窄，因此每个实例的影响范围随之变小：决策边界变得更不规则，开始围着单个实例绕弯。反过来，减小gamma值使钟形曲线变得更宽，因而每个实例的影响范围增大，决策边界变得更平坦。所以就像是一个正则化的超参数：模型过度拟合，就降低它的值，如果拟合不足则提升它的值（类似超参数C）。

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

计算复杂度

libliner库为线性SVM实现了一个优化算法，LinearSVC正是基于此库。该算法不知此核技巧，但它与训练实例数量和特征数量几乎线性相关：训练时间复杂度大致为O(mXn)。
SVC则是基于libsvm库的，这个库的算法支持核技巧。训练时间复杂度通常在O（m^2^×n）和O（m^3^×n）之间。这个算法完美适用于复杂但是中小型的训练集。它还是可以良好适应地特征数量的增加，特别是应对稀疏特征。在这种情况下，算法复杂度大致与实例的平均非零特征数成比例。

SVM回归

尽可能的让实例位于街道上，同时限制间隔违例。街道宽度有超参数ξ控制（ξ越大，街道越宽）。在间隔内添加更多的实例，不会影响到模型的预测，这个模型称为ξ不敏感。

from skleran.svm import LinearSVR

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

也可以使用核化SVM模型：
左图几乎没有正则化，右图则过度正则化（C值很小，C为正则化参数）。

from sklearn.svm import SVR

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

工作原理

决策函数和预测
$W^{T} \cdot X + b = w_{1} x_{1} + \dots + w_{n} x_{n} + b$
如果结果为正，则预测类别是正例（1），否则为负类（0）。
以花瓣宽度和长度为例，构成二维平面。决策边界是决策函数等于0的点集合：是两个平面的交集。图中实线：
虚线表示决策函数1或-1，他们与决策边界平行且距离相等，从而形成一个间隔。训练线性SVM分类器需要寻找w和b，使这个间隔竟可能宽的同时，避免或是限制间隔违例。
当有n个特征时，决策函数是一个n维的超平面，决策边界是一个（n-1）维的超平面。

训练目标

我们需要最小化||w||来得到尽可能大的间隔。如果想要避免任何间隔违例（硬间隔），就要使所有正例训练集决策函数大于1，负例训练集决策函数小于-1。实例为
负类（如果y^（i）=0）时，t^（i）=-1；实例为正类（如果y^（i）=1）时，
t^（i）=1。那么我们就可以将这个约束条件表示为：对所有实例来说，t^（i）（w^T·x^（i）+b）≥1。

硬间隔线性SVM分类器的目标
最小化w^T·w*0.5，使得t^（i）（w^T·x^（i）+b）≥1。
之所以不最小化||w||，是因为||w||在w=0时，是不可微的。
软间隔线性SVM分类器目标
$最小化 \frac{1}{2} w^{T} w + C <munderover> \sum i = 1 m </munderover> ζ^{(i)} 使得 t^{(i)} (w^{T} x^{(i)} + b) \geq 1 - ζ^{(i)}$
引入松弛变量，衡量第i个实例多大程度允许间隔违例。松弛变量月小越好，同时w^T·w/2最小化以增大间隔。参数C则是衡量这两个目标的权衡。

二次规划

硬间隔和软间隔问题都属于线性约束的凸二次优化问题。这类问题被称为二次规划（QP）问题。
表达式A·p≤b实际上定义了nc个约束：对于i=1，2，…，nc，p^T·a^（i）≤b^（i），其中^a（i）是包含A的第i行元素的向量，而b^（i）是b的第i
个元素。

对偶问题

通常来说，对偶问题的解只能算是原始问题的解的下限，但是在某些情况下，它也可能跟原始问题的解完全相同。
线性SVM目标的对偶形式：
对偶问题到原始问题：
当实例数量小于特征数量时，解决对偶问题比原始问题更快速。而且可以实现核技巧。

核化SVM

假如将一个二阶多项式转换为一个二维训练集，然后在转换训练集上训练SVM分类器。

二阶多项式映射
二阶多项式核技巧
由推导过程可知，能够有效提高计算效率，甚至不知道φ转换函数。
常用核函数
使用核化SVM做出预测
使用核技巧计算偏置项
线性SVM分类器成本函数
成本函数中第一项会推动模型向小w移动，从而使间隔增大。第二项，能够保证模型间隔违例尽可能小。
Hinge损失函数
t=1处函数不可导。在t=0处则可以使用任意次导数。