从数学角度理解SVM分类算法

从数学角度理解SVM分类算法

1. 背景

支持向量机(Support Vector Machine，SVM)是一种分类算法，以最大化分类器的边际(margin)为目标，并且分类效果在训练数据集上表现非常好。

2. SVM算法原理

SVM算法通过将特征空间映射到高维空间，寻找一个超平面(hyperplane)，将不同类别的数据点进行分离。SVM算法的核心思想就是找到数据集的最优超平面。

2.1 SVM的简单公式

$$ f(x) = w^T x + b $$

其中，$w$是超平面的法向量，$b$是超平面的截距，$x$是样本点。

$f(x)$的符号决定了$x$所属的类别。

当$f(x) > 0$时，$x$属于正例类别;

当$f(x) < 0$时，$x$属于负例类别;

当$f(x) = 0$时，$x$在超平面上。

2.2 SVM的目标函数

求解SVM的过程就是在所有可能的超平面中找到最优的超平面。用数学语言描述，就是找到使边际最大的超平面。

定义决策边距(decision margin)：

$$margin = \frac{2}{\left|\boldsymbol{w}\right|}$$

其中$\boldsymbol{w}$是向量$(w_1, w_2, ..., w_n)$，所有的$\boldsymbol{w}$都满足边距的条件。

SVM分类问题的目标就是最大化边距，可以转化为以下的优化问题：

$$\max_{\boldsymbol{w},b} \frac{2}{\left|\boldsymbol{w}\right|}$$

同时满足以下约束条件：

$$y^{(i)}(\boldsymbol{w}^Tx^{(i)} + b) \geq 1, i=1, 2, ..., m$$

其中，$y^{(i)}$是类别标签，$x^{(i)}$是样本点，$m$是样本数目。

这个约束条件实际上是告诉我们：所有的样本都必须正确分类。

2.3 最大化边距

根据拉格朗日乘子法，将所有约束条件转化为目标函数的一部分。得到下面的拉格朗日函数：

$$L(\boldsymbol{w}, b, \alpha) = \frac{1}{2}\left|\boldsymbol{w}\right|^2 - \sum_{i=1}^m\alpha_i(y^{(i)}(\boldsymbol{w}^Tx^{(i)} + b) - 1)$$

其中，$\alpha$是拉格朗日乘子向量，可以用于求解最优化问题的惩罚因子。

最优化的问题被转换成了极大极小化的问题：

$$\min_{\boldsymbol{w},b} \max_{\alpha} L(\boldsymbol{w}, b, \alpha)$$

化简后得到：

$$\max_{\alpha} \sum_{i=1}^m\alpha_i - \frac{1}{2}\sum_{i,j=1}^m y^{(i)}y^{(j)}\alpha_i\alpha_jx^{(i)}\cdot x^{(j)}$$

约束条件为：

$$\sum_{i=1}^m y^{(i)}\alpha_i=0 \;\;\;\;\;\;\;\;\;\;\;\;\ 0 \leq \alpha_i \leq C,$$

其中，$C$是一个惩罚因子，用于控制过拟合的情况。

求解这个优化问题，得到$\alpha$向量，然后就可以用$f(x)$进行分类了。

2.4 对偶问题

这个最优化问题是一个凸二次规划问题，可以用凸优化的方法进行求解。不过，可以将这个原问题转换成对偶问题。

对偶问题的目标函数：

$$\min_{\alpha} \frac{1}{2} \sum_{i=1}^m\sum_{j=1}^m y^{(i)}y^{(j)}\alpha_i\alpha_j \cdot \left(x^{(i)}\cdot x^{(j)}\right) - \sum_{i=1}^m \alpha_i$$

约束条件为：

$$\sum_{i=1}^m y^{(i)}\alpha_i=0 \;\;\;\;\;\;\;\;\;\;\;\;\ 0 \leq \alpha_i \leq C$$

通过求解对偶问题，可以得到最优化问题的解，包括$\boldsymbol{w}$和$b$。

2.5 图形化表示

在2维空间中，SVM就是寻找一条直线尽可能远离下面的负点并尽可能接近上面的正点。

上图中，红色和蓝色的点代表两个不同的分类，绿色的线就是SVM分类器找到的超平面。

2.6 核函数

如果数据集无法线性分割，可以使用核函数来将非线性数据转换为线性数据。

在2维空间中，可以使用圆形的核函数将非线性数据转换为线性数据。

$$K(x, y) = exp(-\gamma||x-y||^2)$$

其中，$\gamma$是一个调节参数，$||x-y||$是点$x$和点$y$之间的欧几里得距离。

在高维空间中，多项式核函数和高斯核函数非常流行。

3. 两个SVM的例子

3.1 线性SVM的例子

在这个例子中，我们使用sklearn库中的make_blobs方法生成1000个随机点，其中包含2个不同的分类。

from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
import numpy as np

X, y = make_blobs(n_samples=1000, centers=2, n_features=2,
                  random_state=0, cluster_std=0.5)

plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='viridis')
plt.show()

可以看到这些点是可分的，我们可以使用线性SVM将这些点分开。

from sklearn.svm import SVC

model = SVC(kernel='linear', C=1E10)
model.fit(X, y)

plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='viridis')

xlim = plt.xlim()
ylim = plt.ylim()
xx = np.linspace(xlim[0], xlim[1], 30)
yy = np.linspace(ylim[0], ylim[1], 30)
XX, YY = np.meshgrid(xx, yy)
xy = np.vstack([XX.ravel(), YY.ravel()]).T
Z = model.decision_function(xy).reshape(XX.shape)

plt.contour(XX, YY, Z, colors='k', levels=[-1, 0, 1],
           alpha=0.5, linestyles=['--', '-', '--'])

plt.scatter(model.support_vectors_[:, 0], model.support_vectors_[:, 1],
            s=100, linewidth=1, facecolors='none', edgecolors='k')
plt.show()

在上面的图片中，黑色实线是超平面，黑色虚线是超平面与两类数据点的边界。在这个例子中线性SVM可以正确地将数据分为两类。

3.2 非线性SVM的例子

在这个例子中，我们使用sklearn库中的make_moons方法生成1000个随机点，其中包含2个不同的分类。

from sklearn.datasets import make_moons

X, y = make_moons(n_samples=1000, noise=0.30, random_state=0)

plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='viridis')
plt.show()

可以看到这些点是非线性可分的，我们需要使用非线性SVM将这些点分开。

from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC

clf = Pipeline([
    ("scaler", StandardScaler()),
    ("svm", SVC(kernel="rbf", gamma=0.1, C=1E10))
])
clf.fit(X, y)

plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='viridis')

xlim = plt.xlim()
ylim = plt.ylim()
xx = np.linspace(xlim[0], xlim[1], 30)
yy = np.linspace(ylim[0], ylim[1], 30)
XX, YY = np.meshgrid(xx, yy)
xy = np.vstack([XX.ravel(), YY.ravel()]).T
Z = clf.decision_function(xy).reshape(XX.shape)

plt.contour(XX, YY, Z, colors='k', levels=[-1, 0, 1],
           alpha=0.5, linestyles=['--', '-', '--'])

plt.scatter(clf["svm"].support_vectors_[:, 0], clf["svm"].support_vectors_[:, 1],
            s=100, linewidth=1, facecolors='none', edgecolors='k')
plt.show()

在上面的图片中，黑色实线是SVM函数，黑色虚线是SVM函数与两类数据点的边界。在这个例子中非线性SVM可以正确地将数据分为两类。由于这个例子中数据并不是线性可分的，所以我们需要使用核函数将非线性数据转换为线性数据。在这个例子中我们使用的是高斯核函数。