决策边界是一个假想的边界,用来区分不同类别的数据点。在特征空间中,决策边界定义了一个分界线或分界面,用于决定新的输入数据点应该被分类为哪一类。
在二维特征空间中,决策边界通常是一条线。
在三维特征空间中,决策边界可能是一个平面。
在更高维度的特征空间中,决策边界可以是一个超平面。
需要计算数据点到决策边界(超平面)的距离。对于一个超平面,可以用公式 w x + b = 0 wx + b = 0 wx+b=0 来表示,其中 w w w 是权重向量, x x x 是数据点, b b b 是偏置项。
点到超平面的距离:
数据点 x x x 到超平面的距离 d d d 可以通过以下公式计算:
d = ∣ w x + b ∣ ∣ ∣ w ∣ ∣ d = \frac{|wx + b|}{||w||} d=∣∣w∣∣∣wx+b∣?
其中, ∣ ∣ w ∣ ∣ ||w|| ∣∣w∣∣ 是权重向量的范数(即长度)。这个公式衡量了点 x x x 到超平面的“垂直”距离。
数据集:(X1,Y1)(X2,Y2)…(Xn,Yn)
二分类问题:
在二分类问题中,Y为样本的类别通常定义为 + 1 +1 +1 和 ? 1 -1 ?1。 + 1 +1 +1 表示一个类别, ? 1 -1 ?1 表示另一个类别。SVM 的目标是找到一个超平面,使得两个类别的数据点被正确地分开。
多分类问题:
对于多分类问题,可以使用一对一(One-vs-One)或一对多(One-vs-All)的策略,将多分类问题转化为多个二分类问题。
决策方程
在 SVM 中,决策方程基于支持向量和分离超平面定义。给定一个训练数据集
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
.
.
.
,
(
x
n
,
y
n
)
}
\{(\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), ..., (\mathbf{x}_n, y_n)\}
{(x1?,y1?),(x2?,y2?),...,(xn?,yn?)},其中
x
i
\mathbf{x}_i
xi? 是特征向量,
y
i
y_i
yi? 是类别标签(通常为 +1 或 -1),决策方程为:
f ( x ) = sign ( w ? x + b ) f(\mathbf{x}) = \text{sign}(\mathbf{w} \cdot \mathbf{x} + b) f(x)=sign(w?x+b)
其中,
min
?
w
,
b
1
2
∥
w
∥
2
\min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2
w,bmin?21?∥w∥2
subject?to?
y
i
(
w
?
x
i
+
b
)
≥
1
,
?for?all?
i
\text{subject to } y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1, \text{ for all } i
subject?to?yi?(w?xi?+b)≥1,?for?all?i
这个优化问题通常通过拉格朗日乘子法转换为对偶问题来求解。
通过引入拉格朗日乘子 α i \alpha_i αi?,优化问题变为:
max ? α [ ∑ i = 1 n α i ? 1 2 ∑ i , j = 1 n y i y j α i α j ( x i ? x j ) ] \max_{\alpha} \left[ \sum_{i=1}^{n} \alpha_i - \frac{1}{2} \sum_{i,j=1}^{n} y_i y_j \alpha_i \alpha_j (\mathbf{x}_i \cdot \mathbf{x}_j) \right] αmax?[i=1∑n?αi??21?i,j=1∑n?yi?yj?αi?αj?(xi??xj?)]
受制于:
∑ i = 1 n α i y i = 0 \sum_{i=1}^{n} \alpha_i y_i = 0 i=1∑n?αi?yi?=0
和
α i ≥ 0 , ? i \alpha_i \geq 0, \quad \forall i αi?≥0,?i
在这个对偶问题中,我们寻求最大化拉格朗日乘子的和,同时考虑到数据点之间的内积。这种方法能够处理线性不可分的情况,通过引入核函数,SVM 可以被扩展到非线性分类问题。
我们需要求解支持向量机(SVM)的拉格朗日乘子时,首先对拉格朗日函数分别对 w w w 和 b b b 求偏导数,然后令其等于零,从而找到最优解。
对拉格朗日函数:
L ( w , b , α ) = 1 2 ∥ w ∥ 2 ? ∑ i = 1 n α i [ y i ( w ? x i + b ) ? 1 ] L(w, b, \boldsymbol{\alpha}) = \frac{1}{2} \|w\|^2 - \sum_{i=1}^{n} \alpha_i \left[ y_i (w \cdot x_i + b) - 1 \right] L(w,b,α)=21?∥w∥2?i=1∑n?αi?[yi?(w?xi?+b)?1]
其中, w w w 是超平面的法向量, α \boldsymbol{\alpha} α 是拉格朗日乘子向量。
我们对 w w w 求偏导数:
? L ? w = w ? ∑ i = 1 n α i y i x i = 0 \frac{\partial L}{\partial w} = w - \sum_{i=1}^{n} \alpha_i y_i x_i = 0 ?w?L?=w?i=1∑n?αi?yi?xi?=0
将这个结果令为零,得到了 w w w 的表达式。
同样,我们对拉格朗日函数求关于 b b b 的偏导数:
? L ? b = ? ∑ i = 1 n α i y i = 0 \frac{\partial L}{\partial b} = -\sum_{i=1}^{n} \alpha_i y_i = 0 ?b?L?=?i=1∑n?αi?yi?=0
将上述方程组的解代入拉格朗日函数 L L L 中,得到最小化问题只关于拉格朗日乘子 α \boldsymbol{\alpha} α 的表达式:
min ? α [ ∑ i = 1 n α i ? 1 2 ∑ i , j = 1 n α i α j y i y j ( x i ? x j ) ] \min_{\boldsymbol{\alpha}} \left[ \sum_{i=1}^{n} \alpha_i - \frac{1}{2} \sum_{i,j=1}^{n} \alpha_i \alpha_j y_i y_j (\mathbf{x}_i \cdot \mathbf{x}_j) \right] αmin?[i=1∑n?αi??21?i,j=1∑n?αi?αj?yi?yj?(xi??xj?)]
一旦找到最优的拉格朗日乘子 α \boldsymbol{\alpha} α,我们可以使用以下公式计算最终的超平面参数 w \mathbf{w} w 和 b b b:
超平面法向量 w \mathbf{w} w:
w = ∑ i = 1 n α i y i x i \mathbf{w} = \sum_{i=1}^{n} \alpha_i y_i \mathbf{x}_i w=i=1∑n?αi?yi?xi?
偏置项 b b b:
选择任意一个支持向量点 x j \mathbf{x}_j xj?,然后使用以下公式计算 b b b:
b = y j ? ∑ i = 1 n α i y i ( x i ? x j ) b = y_j - \sum_{i=1}^{n} \alpha_i y_i (\mathbf{x}_i \cdot \mathbf{x}_j) b=yj??i=1∑n?αi?yi?(xi??xj?)
然而,在实际问题中,数据通常不是线性可分的,或者数据中可能存在噪声。硬间隔 SVM 对于这些情况可能过于严格,容易导致过拟合。这时就引入了 soft-margin SVM。
Soft-margin SVM 的目标是找到一个超平面,最大化间隔,同时允许一些训练样本分类错误。为了实现这一目标,引入了松弛变量(slack variables) ξ i \xi_i ξi?,用来度量每个样本允许的分类错误程度。
Soft-margin SVM 的目标函数可以表示为:
min ? w , b , ξ 1 2 ∥ w ∥ 2 + C ∑ i = 1 N ξ i \min_{w, b, \xi} \frac{1}{2} \|w\|^2 + C \sum_{i=1}^{N} \xi_i w,b,ξmin?21?∥w∥2+Ci=1∑N?ξi?
其中, w w w 是超平面的法向量, b b b 是偏置项, C C C 是一个正则化参数, N N N 是训练样本的数量。
Soft-margin SVM 的工作原理是最小化目标函数,找到合适的超平面,以最大化间隔并容忍一定程度的分类错误。通过调整正则化参数 C C C 的值,可以控制容忍错误的程度。当 C C C 较小时,模型更容忍分类错误,可能导致更大的间隔但分类错误更多;当 C C C 较大时,模型更严格,容忍分类错误较少,但可能导致较小的间隔。
在支持向量机中,核函数的主要作用是将原始的输入数据映射到一个更高维的特征空间,从而改变数据在特征空间中的表现形式。这个转换的目的是使得原本在低维空间中线性不可分的数据在高维特征空间中变得线性可分。
核函数通常表示为 K ( x , x ′ ) K(x, x') K(x,x′),其中 x x x 和 x ′ x' x′ 是输入数据的向量。不同的核函数有不同的形式,常见的核函数包括:
线性核函数:
K ( x , x ′ ) = x T x ′ K(x, x') = x^T x' K(x,x′)=xTx′
线性核函数不进行特征变换,直接在原始特征空间中进行内积操作。
多项式核函数:
K ( x , x ′ ) = ( x T x ′ + c ) d K(x, x') = (x^T x' + c)^d K(x,x′)=(xTx′+c)d
多项式核函数将数据映射到高维空间,并进行多项式特征的组合。
高斯径向基函数(RBF)核函数:
K ( x , x ′ ) = exp ? ( ? ∣ ∣ x ? x ′ ∣ ∣ 2 2 σ 2 ) K(x, x') = \exp\left(-\frac{||x - x'||^2}{2\sigma^2}\right) K(x,x′)=exp(?2σ2∣∣x?x′∣∣2?)
高斯核函数通过计算数据点之间的相似度来进行非线性映射,其中 σ \sigma σ 是高斯核的宽度参数。