支持向量机 (Support Vector Machines, SVM)
支持向量机 (Support Vector Machines, SVM)
通俗易懂算法
支持向量机（SVM）是一种用于分类和回归任务的机器学习算法。在最简单的情况下，SVM是一种线性分类器，适用于二分类问题。它的基本思想是找到一个超平面（在二维空间中是直线，在高维空间中是平面）来将数据点分开。
核心思想
-
分类超平面：
- 在二维空间中，我们希望找到一条直线将两类数据点分开。对于三维空间，就是一个面；对于更高维空间，就是一个超平面。
- 这个分隔面的方程可以表示为： w x + b = 0 wx + b = 0 wx+b=0，其中 w w w是权重向量， b b b是偏置。
-
最大化间隔：
- SVM的关键是不仅仅将数据点分开，而是要找到能最大化两类之间“间隔”（或“边界”）的超平面。这个间隔被称为“margin”。
- 理想情况下，SVM选择的超平面会距离最近的数据点（支持向量）最远。
-
支持向量：
- 那些离超平面最近的点被称为“支持向量”。它们是计算最大间隔的关键，因为它们决定了超平面的最终位置。
数学表达
我们希望找到能够最大化函数间隔的超平面。假设数据集线性可分，这可以通过以下优化问题实现：
min w , b 1 2 ∥ w ∥ 2 s.t. y i ( w x i + b ) ≥ 1 ∀ i \begin{align*} \min_{w, b} & \quad \frac{1}{2} \|w\|^2 \\ \text{s.t.} & \quad y_i(wx_i + b) \geq 1 \quad \forall i \end{align*} w,bmins.t.21∥w∥2yi(wxi+b)≥1∀i
其中：
- w w w 是权重向量。
- b b b 是偏置。
- y i y_i yi 是数据点 x i x_i xi 的标签，通常 y i ∈ { − 1 , 1 } y_i \in \{-1, 1\} yi∈{−1,1}。
此优化问题的目标是最小化向量 w w w的范数，同时保证所有数据点都在间隔之外。
核技巧
当数据集不是线性可分时，SVM可以通过“核技巧”来处理非线性分类问题。核技巧的核心是在较高维度空间中寻找线性分割面，而不需要显式地转换数据。
常用的核函数包括：
- 线性核： K ( x i , x j ) = x i ⋅ x j K(x_i, x_j) = x_i \cdot x_j K(xi,xj)=xi⋅xj
- 多项式核： K ( x i , x j ) = ( x i ⋅ x j + c ) d K(x_i, x_j) = (x_i \cdot x_j + c)^d K(xi,xj)=(xi⋅xj+c)d
- 高斯核（RBF核）： K ( x i , x j ) = exp ( − γ ∥ x i − x j ∥ 2 ) K(x_i, x_j) = \exp(-\gamma \|x_i - x_j\|^2) K(xi,xj)=exp(−γ∥xi−xj∥2)
总结
支持向量机是一种功能强大的分类算法，尤其在维度较高的数据集上表现良好。其关键优势在于：
- 能够处理高维空间。
- 通过核技巧，能够处理非线性分类任务。
- 对少量样本和稀疏数据较为有效。
理解SVM的核心，在于理解它是如何通过最大化间隔来实现分类以及如何利用支持向量来影响模型的最终决策。
底层原理
支持向量机（SVM）是一种用于分类和回归的监督学习模型。其核心思想是寻找一个最优的超平面，把不同类别的数据分开，同时最大化类别之间的间隔。以下是SVM的数学原理：
1. 问题定义
对于给定的训练数据集：
{
(
x
i
,
y
i
)
∣
x
i
∈
R
n
,
y
i
∈
{
−
1
,
1
}
,
i
=
1
,
2
,
…
,
m
}
\{(\mathbf{x}_i, y_i) \mid \mathbf{x}_i \in \mathbb{R}^n, y_i \in \{-1, 1\}, i = 1, 2, \ldots, m\}
{(xi,yi)∣xi∈Rn,yi∈{−1,1},i=1,2,…,m}
我们要找到一个超平面把数据分开。这个超平面可以表示为：
w
⋅
x
+
b
=
0
\mathbf{w} \cdot \mathbf{x} + b = 0
w⋅x+b=0
2. 几何间隔和函数间隔
-
函数间隔：
函数间隔是超平面对点 ( x i , y i ) (\mathbf{x}_i, y_i) (xi,yi) 的这一形式的产品：
γ i = y i ( w ⋅ x i + b ) \gamma_i = y_i (\mathbf{w} \cdot \mathbf{x}_i + b) γi=yi(w⋅xi+b) -
几何间隔：
几何间隔通过归一化权重向量 w \mathbf{w} w 来计算，定义为：
γ ^ i = γ i ∣ ∣ w ∣ ∣ = y i ( w ⋅ x i + b ) ∣ ∣ w ∣ ∣ \hat{\gamma}_i = \frac{\gamma_i}{||\mathbf{w}||} = \frac{y_i (\mathbf{w} \cdot \mathbf{x}_i + b)}{||\mathbf{w}||} γ^i=∣∣w∣∣γi=∣∣w∣∣yi(w⋅xi+b)
对于SVM，我们希望最大化几何间隔。
3. 最优化问题
为了最大化间隔，SVM把最大化问题转化为以下约束的二次优化问题：
min
w
,
b
1
2
∣
∣
w
∣
∣
2
subject to
y
i
(
w
⋅
x
i
+
b
)
≥
1
,
∀
i
\begin{align*} \min_{\mathbf{w}, b} \quad & \frac{1}{2} ||\mathbf{w}||^2 \\ \text{subject to} \quad & y_i (\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1, \quad \forall i \end{align*}
w,bminsubject to21∣∣w∣∣2yi(w⋅xi+b)≥1,∀i
4. 拉格朗日对偶问题
通过引入拉格朗日乘子
α
i
≥
0
\alpha_i \geq 0
αi≥0，可以构建拉格朗日函数：
L
(
w
,
b
,
α
)
=
1
2
∣
∣
w
∣
∣
2
−
∑
i
=
1
m
α
i
[
y
i
(
w
⋅
x
i
+
b
)
−
1
]
L(\mathbf{w}, b, \alpha) = \frac{1}{2} ||\mathbf{w}||^2 - \sum_{i=1}^{m} \alpha_i [y_i(\mathbf{w} \cdot \mathbf{x}_i + b) - 1]
L(w,b,α)=21∣∣w∣∣2−i=1∑mαi[yi(w⋅xi+b)−1]
通过对
w
\mathbf{w}
w 和
b
b
b 求导并设为零，可以得到对偶问题：
max
α
∑
i
=
1
m
α
i
−
1
2
∑
i
=
1
m
∑
j
=
1
m
α
i
α
j
y
i
y
j
(
x
i
⋅
x
j
)
subject to
∑
i
=
1
m
α
i
y
i
=
0
,
α
i
≥
0
,
∀
i
\begin{align*} \max_{\alpha} \quad & \sum_{i=1}^{m} \alpha_i - \frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_i \alpha_j y_i y_j (\mathbf{x}_i \cdot \mathbf{x}_j) \\ \text{subject to} \quad & \sum_{i=1}^{m} \alpha_i y_i = 0, \\ & \alpha_i \geq 0, \quad \forall i \end{align*}
αmaxsubject toi=1∑mαi−21i=1∑mj=1∑mαiαjyiyj(xi⋅xj)i=1∑mαiyi=0,αi≥0,∀i
5. 核函数方法
在高维空间中，数据很难线性分开；我们通过核函数引入非线性映射 ϕ ( x ) \phi(\mathbf{x}) ϕ(x)，使问题在特征空间中线性可分。常用的核函数包括：
- 多项式核： K ( x i , x j ) = ( x i ⋅ x j + c ) d K(\mathbf{x}_i, \mathbf{x}_j) = (\mathbf{x}_i \cdot \mathbf{x}_j + c)^d K(xi,xj)=(xi⋅xj+c)d
- 高斯核（RBF核）： K ( x i , x j ) = exp ( − ∣ ∣ x i − x j ∣ ∣ 2 2 σ 2 ) K(\mathbf{x}_i, \mathbf{x}_j) = \exp\left(-\frac{||\mathbf{x}_i - \mathbf{x}_j||^2}{2\sigma^2}\right) K(xi,xj)=exp(−2σ2∣∣xi−xj∣∣2)
通过这些核函数，SVM可以在高维空间中找到超平面对原数据进行分类。
6. 软间隔SVM
对于不可完全分的情况，引入松弛变量
ξ
i
\xi_i
ξi 允许部分数据点越过分隔边界，最优化问题变成：
min
w
,
b
,
ξ
1
2
∣
∣
w
∣
∣
2
+
C
∑
i
=
1
m
ξ
i
subject to
y
i
(
w
⋅
x
i
+
b
)
≥
1
−
ξ
i
,
ξ
i
≥
0
,
∀
i
\begin{align*} \min_{\mathbf{w}, b, \xi} \quad & \frac{1}{2} ||\mathbf{w}||^2 + C \sum_{i=1}^{m} \xi_i \\ \text{subject to} \quad & y_i (\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1 - \xi_i, \\ & \xi_i \geq 0, \quad \forall i \end{align*}
w,b,ξminsubject to21∣∣w∣∣2+Ci=1∑mξiyi(w⋅xi+b)≥1−ξi,ξi≥0,∀i
这里的 C C C 是一个超参数，用于控制间隔的宽度和违反间隔的惩罚之间的权衡。
以上是支持向量机的底层数学原理概述，通过这些方法，SVM能够有效地进行分类和回归。
常用面试考点
支持向量机（Support Vector Machines, SVM）是一种常用于分类任务的监督学习模型。SVM的主要目标是找到一个最佳超平面，将数据的不同类别分开。以下是SVM算法的主要概念和公式，从常用面试考点的角度进行讲解：
1. 基本概念
- 超平面: 在 n n n维空间中，一个超平面是一个 ( n − 1 ) (n-1) (n−1)维的子空间，它可以用来分离数据。如在二维空间中，超平面是直线；在三维空间中，超平面是平面。
- 支持向量: 距离超平面最近的那些数据点，这些点决定了超平面的位置和方向。
- 间隔（Margin）: 支持向量到超平面的最小距离。SVM的目标是最大化这个间隔。
2. 数学公式
SVM算法的目标是找到一个超平面，其方程可表示为：
w ⋅ x + b = 0 w \cdot x + b = 0 w⋅x+b=0
其中， w w w是法向量， b b b是偏置项。
对于每个数据点 ( x i , y i ) (x_i, y_i) (xi,yi)，分类要求满足：
y i ( w ⋅ x i + b ) ≥ 1 y_i(w \cdot x_i + b) \geq 1 yi(w⋅xi+b)≥1
在硬间隔（Hard Margin）情况下，SVM的目标是最大化间隔，可以转化为最小化以下目标函数：
min 1 2 ∣ ∣ w ∣ ∣ 2 \min \frac{1}{2} ||w||^2 min21∣∣w∣∣2
主体约束为上述分类条件。
在软间隔（Soft Margin）情况下，为了允许一些数据点在错误侧，目标变为：
min 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 n ξ i \min \frac{1}{2} ||w||^2 + C \sum_{i=1}^{n} \xi_i min21∣∣w∣∣2+Ci=1∑nξi
约束为：
y i ( w ⋅ x i + b ) ≥ 1 − ξ i , ξ i ≥ 0 y_i(w \cdot x_i + b) \geq 1 - \xi_i, \, \xi_i \geq 0 yi(w⋅xi+b)≥1−ξi,ξi≥0
其中， ξ i \xi_i ξi是松弛变量， C C C是惩罚参数，控制对错误分类的惩罚程度。
3. 核函数（Kernel Trick）
为了处理非线性分类问题，SVM采用核技巧，通过一种映射将原始数据从输入空间映射到高维特征空间。在高维特征空间中，数据变得线性可分。常用的核函数包括：
- 线性核: K ( x i , x j ) = x i ⋅ x j K(x_i, x_j) = x_i \cdot x_j K(xi,xj)=xi⋅xj
- 多项式核: K ( x i , x j ) = ( x i ⋅ x j + c ) d K(x_i, x_j) = (x_i \cdot x_j + c)^d K(xi,xj)=(xi⋅xj+c)d
- 高斯核（RBF）: K ( x i , x j ) = exp ( − γ ∣ ∣ x i − x j ∣ ∣ 2 ) K(x_i, x_j) = \exp(-\gamma ||x_i - x_j||^2) K(xi,xj)=exp(−γ∣∣xi−xj∣∣2)
- sigmoid核: K ( x i , x j ) = tanh ( α x i ⋅ x j + c ) K(x_i, x_j) = \tanh(\alpha x_i \cdot x_j + c) K(xi,xj)=tanh(αxi⋅xj+c)
4. 优点与局限
-
优点:
- 有效处理高维数据。
- 在特征数大于样本数的情况下依然表现良好。
- 可通过核函数处理非线性问题。
-
局限:
- 对大规模数据集效率不高。
- 在参数选择和核函数选择上较复杂。
面试中的常见问题包括解释间隔的概念、核函数的作用、如何选择参数C和核函数的参数等，以及如何将SVM应用于具体的分类任务。