支持向量机（Support Vector Machine，SVM）

支持向量机（Support Vector Machine，简称SVM）是一种监督学习模型，主要用于分类和回归分析。

SVM的基本思想是寻找一个决策边界或超平面，使得两类样本之间的间隔最大化。

这个间隔被定义为支持向量到超平面的最短距离，而支持向量就是那些恰好位于间隔边缘上的训练样本点。

线性可分情况下的SVM

假设我们有一组训练数据 ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x n , y n ) (x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n) (x1​,y1​),(x2​,y2​),…,(xn​,yn​) ，其中 x i x_i xi​ 是输入特征向量， y i y_i yi​ 是对应的输出标签（ + 1 +1 +1 或 − 1 -1 −1 ）。

SVM试图找到一个最优超平面 w T x + b = 0 \mathbf{w}^T \mathbf{x} + b = 0 wTx+b=0 来区分这两类数据，其中 w \mathbf{w} w 是权重向量， b b b 是偏置项。

最大间隔超平面公式

为了找到最大间隔超平面，我们需要满足以下条件：
y i ( w T x i + b ) ≥ 1 y_i (\mathbf{w}^T \mathbf{x}_i + b) \geq 1 yi​(wTxi​+b)≥1

这表示对于所有的训练样本，它们都必须正确分类并且与决策边界保持至少单位距离。

这个距离由 1 ∣ ∣ w ∣ ∣ \frac{1}{||\mathbf{w}||} ∣∣w∣∣1​ 给出，因此我们的目标是最小化 1 2 ∣ ∣ w ∣ ∣ 2 \frac{1}{2}||\mathbf{w}||^2 21​∣∣w∣∣2 同时满足上述不等式约束。

公式解释

• w \mathbf{w} w ：权重向量，决定了超平面的方向。
• b b b ：偏置项，决定了超平面的位置。
• x i \mathbf{x}_i xi​ ：第 i i i 个训练样本的特征向量。
• y i y_i yi​ ：第 i i i 个训练样本的标签，取值为 + 1 +1 +1 或 − 1 -1 −1 。
• ∣ ∣ w ∣ ∣ ||\mathbf{w}|| ∣∣w∣∣ ：权重向量的范数，用于度量向量的长度。

软间隔SVM

在实际问题中，数据可能不是完全线性可分的，此时可以允许一些样本点跨越决策边界，这就是所谓的软间隔SVM。

为此，我们引入松弛变量 ξ i \xi_i ξi​ 和惩罚参数 C C C ，并最小化以下目标函数：
1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 n ξ i \frac{1}{2}||\mathbf{w}||^2 + C\sum_{i=1}^{n}\xi_i 21​∣∣w∣∣2+Ci=1∑n​ξi​
同时满足：
y i ( w T x i + b ) ≥ 1 − ξ i y_i (\mathbf{w}^T \mathbf{x}_i + b) \geq 1 - \xi_i yi​(wTxi​+b)≥1−ξi​
ξ i ≥ 0 \xi_i \geq 0 ξi​≥0

核技巧

当数据不是线性可分时，SVM通过核函数（Kernel Function）将原始低维特征空间映射到高维特征空间，在高维空间中找到一个线性超平面来实现分类。

常用的核函数包括多项式核、高斯核（RBF核）、Sigmoid核等。

核函数公式

K ( x , x ′ ) = ϕ ( x ) T ϕ ( x ′ ) K(\mathbf{x}, \mathbf{x}') = \phi(\mathbf{x})^T\phi(\mathbf{x}') K(x,x′)=ϕ(x)Tϕ(x′)

其中， ϕ \phi ϕ 表示从原始特征空间到高维特征空间的映射函数， K K K 是核函数，它直接计算两个向量在高维空间中的内积。

拉格朗日乘子法

SVM的优化问题通常通过拉格朗日乘子法转化为对偶问题来解决，对偶问题的形式为：
max ⁡ α W ( α ) = ∑ i = 1 n α i − 1 2 ∑ i , j = 1 n y i y j α i α j K ( x i , x j ) \max_{\alpha} W(\alpha) = \sum_{i=1}^{n}\alpha_i - \frac{1}{2}\sum_{i,j=1}^{n}y_iy_j\alpha_i\alpha_jK(\mathbf{x}_i,\mathbf{x}_j) αmax​W(α)=i=1∑n​αi​−21​i,j=1∑n​yi​yj​αi​αj​K(xi​,xj​)

其中， α i \alpha_i αi​ 是Lagrange乘子，且需满足KKT条件。

这些公式和概念构成了SVM的基础，通过调整参数和选择合适的核函数，SVM可以非常有效地处理复杂的数据分类问题。