中小企业网站建设如何,网站建设经费管理,wordpress 前端展示,烟台网站建设找三硕科技文章目录 引言间隔与支持向量机对偶问题#xff08;拉格朗日乘子法#xff09;SMO算法核函数软间隔与正则化软间隔正则化#xff08;罚函数法#xff09; 模型的稀疏性结论实验分析 引言
在机器学习领域#xff0c;支持向量机#xff08;Support Vector Machine#xf… 文章目录 引言间隔与支持向量机对偶问题拉格朗日乘子法SMO算法核函数软间隔与正则化软间隔正则化罚函数法 模型的稀疏性结论实验分析 引言
在机器学习领域支持向量机Support Vector Machine简称SVM是一种强大而广泛应用的监督学习算法。其独特的优势在于在高维空间中进行准确分类并在处理复杂数据集时表现出色。支持向量机的核心思想是在数据点间找到一个最优的超平面以最大化不同类别之间的间隔同时最小化分类误差。
SVM的独特之处在于其对非线性关系的处理能力这得益于其引入了核函数的概念使得在高维空间中进行非线性映射成为可能。除了在分类问题中的成功应用支持向量机还被广泛用于回归、异常检测和数据压缩等多个领域。
本博客将深入探讨支持向量机的原理从数学层面推导其基本公式并通过实际例子展示其在现实问题中的应用。通过阅读本文您将更好地理解支持向量机的工作原理以及如何在实际场景中应用这一强大的机器学习算法。
间隔与支持向量机
给定训练样本集 D { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x m , y m ) } D\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m) \} D{(x1,y1),(x2,y2),...,(xm,ym)} y i ∈ { − 1 , 1 } y_i \in \{-1,1\} yi∈{−1,1}分类学习最基本想法是基于训练集 D D D在样本空间中找到一个可以划分的超平面将不同类别的样本分开。但能将训练样本划分开的超平面由很多如下图所示 在之前的线性判别分析LDA中我们可知所得到的超平面应该使得同类样例的投影点尽可能的接近、异类的样本点尽可能的原理。 线性判别分析LDA 在样本空间中划分超平面可通过如下线性方程来描述 w T x b 0 (1) w^Txb0 \tag{1} wTxb0(1)
其中 w ( w 1 , w 2 , . . . , w d ) T w(w_1,w_2,...,w_d)^T w(w1,w2,...,wd)T为法向量决定了超平面的方向 b b b是位移项决定了超平面与原点之间的距离。显然划分超平面可被法向量 w w w和位移 b b b确定。样本空间中任意点 x x x到超平面 ( w , b ) (w,b) (w,b)的 距离可写为 r ∣ w T x b ∣ ∣ ∣ w ∣ ∣ (2) r\frac{|w^Txb|}{||w||} \tag{2} r∣∣w∣∣∣wTxb∣(2)
假设超平面 ( w , b ) (w,b) (w,b)能将训练样本正确分类即对于 ( x i , y i ) ∈ D (x_i,y_i)\in D (xi,yi)∈D若 y i 1 y_i1 yi1则有 w T x i b 0 w^Tx_ib0 wTxib0若 y i − 1 y_i-1 yi−1则有 w T x i b 0 w^Tx_ib0 wTxib0。令 { w T x i b ≥ 1 , y i 1 w T x i b ≤ − 1 , y i − 1 (3) \begin{cases} w^Tx_ib\geq1,\quad y_i1\\ w^Tx_ib\leq-1,\quad y_i-1 \end{cases} \tag{3} {wTxib≥1,yi1wTxib≤−1,yi−1(3) 由式2和3可得出对于类别1和类别2距离超平面最近的两个点使得3式的等号成立被称为支持向量即 { w T x i b 1 , y i 1 w T x i b − 1 , y i − 1 \begin{cases} w^Tx_ib1,\quad y_i1\\ w^Tx_ib-1,\quad y_i-1 \end{cases} {wTxib1,yi1wTxib−1,yi−1 将其带入2中得到两个异类支持向量到超平面的距离之和为 γ 2 ∣ ∣ w ∣ ∣ (4) \gamma\frac{2}{||w||} \tag{4} γ∣∣w∣∣2(4) Mark支持向量距离超平面最近的这几个训练样本点使得式3的等号成立。 欲寻找到具有最大间隔的划分超平面也就是要找到能满足式3中约束的参数 w w w和 b b b使得 γ \gamma γ最大即 max ( w , b ) 2 ∥ w ∥ s.t. y i ( w T x i b ) ≥ 1 , i 1 , 2 , … , m (5) \begin{aligned} \underset{(w, b)}{\text{max}} \quad \frac{2}{\|w\|} \\ \text{s.t.} \quad y_i(w^Tx_i b) \geq 1, \quad i 1, 2, \ldots, m \end{aligned} \tag{5} (w,b)max∥w∥2s.t.yi(wTxib)≥1,i1,2,…,m(5)
显然若使得 γ \gamma γ最大化仅需要最大化 ∣ ∣ w ∣ ∣ − 1 ||w||^{-1} ∣∣w∣∣−1这就等价于 最小化 ∣ ∣ w ∣ ∣ 2 ||w||^2 ∣∣w∣∣2。于是式5可改写为 max ( w , b ) 1 2 ∣ ∣ w ∣ ∣ 2 s.t. y i ( w T x i b ) ≥ 1 , i 1 , 2 , … , m (6) \begin{aligned} \underset{(w, b)}{\text{max}} \quad \frac{1}{2}||w||^2 \\ \text{s.t.} \quad y_i(w^Tx_i b) \geq 1, \quad i 1, 2, \ldots, m \end{aligned} \tag{6} (w,b)max21∣∣w∣∣2s.t.yi(wTxib)≥1,i1,2,…,m(6) 这就是支持向量机(SVM)的基本型。
对偶问题拉格朗日乘子法
我们直接对式6使用拉格朗日乘子法可得到一个对偶问题则拉格朗日函数可写为 L ( w , b , λ ) 1 2 ∣ ∣ w ∣ ∣ 2 ∑ i 1 m λ i ( 1 − y i ( w T x i b ) ) (7) L(w,b,\lambda)\frac{1}{2}||w||^2\sum_{i1}^m \lambda_i(1-y_i(w^Tx_i b)) \tag{7} L(w,b,λ)21∣∣w∣∣2i1∑mλi(1−yi(wTxib))(7) 其中 λ i ≥ 0 \lambda_i\geq0 λi≥0令 L ( w , b , λ ) L(w,b,\lambda) L(w,b,λ)对 w w w、 b b b和 λ \lambda λ的偏导为0可得 { ∂ L ∂ w w − ∑ i 1 m λ i y i x i 0 ∂ L ∂ b − ∑ i 1 m λ i y i 0 ∂ L ∂ λ 1 − y i ( w T x i b ) 0 \begin{cases} \frac{\partial L}{\partial w}w-\sum_{i1}^m\lambda_iy_ix_i0 \\ \frac{\partial L}{\partial b}-\sum_{i1}^m\lambda_iy_i0 \\ \frac{\partial L}{\partial \lambda}1-y_i(w^Tx_i b)0 \end{cases} ⎩ ⎨ ⎧∂w∂Lw−∑i1mλiyixi0∂b∂L−∑i1mλiyi0∂λ∂L1−yi(wTxib)0
整理可得 w ∑ i 1 m λ i y i x i (8) w\sum_{i1}^m\lambda_iy_ix_i \tag{8} wi1∑mλiyixi(8) ∑ i 1 m λ i y i 0 (9) \sum_{i1}^m\lambda_iy_i0 \tag{9} i1∑mλiyi0(9) y i ( w T x i b ) 1 (10) y_i(w^Tx_i b)1 \tag{10} yi(wTxib)1(10)
将式8和9带入式子7中可得到式6的对偶问题 max λ ∑ i 1 m λ i − 1 2 ∑ i 1 m ∑ j 1 m λ i λ j y i y j x i T x j s.t. ∑ i 1 m λ i y i 0 λ i ≥ 0 , i 1 , 2 , … , m (11) \begin{aligned} \underset{\lambda}{\text{max}} \quad \sum_{i1}^m\lambda_i-\frac{1}{2}\sum_{i1}^m\sum_{j1}^m\lambda_i\lambda_jy_iy_jx_i^Tx_j \\ \text{s.t.} \quad \sum_{i1}^m\lambda_iy_i0 \\ \ \ \ \ \ \ \ \ \ \ \lambda_i\geq0, \quad i 1, 2, \ldots, m \end{aligned} \tag{11} λmaxi1∑mλi−21i1∑mj1∑mλiλjyiyjxiTxjs.t.i1∑mλiyi0 λi≥0,i1,2,…,m(11)
解出 λ \lambda λ后求出 w w w和 b b b即可得到模型 f ( x ) w T x b ∑ i 1 m λ i y i x i T x b (12) \begin{aligned} f(x) w^Txb \\ \sum_{i1}^m\lambda_iy_ix_i^Txb \end{aligned} \tag{12} f(x)wTxbi1∑mλiyixiTxb(12)
从对偶问题11所解出的 λ i \lambda_i λi是式7中的拉格朗日乘子它对应着样本 ( x i , y i ) (x_i,y_i) (xi,yi)。注意到式6中有不等式约束条件故上述式子的推导过程应满足KKT条件即 { λ i ≥ 0 y i f ( x i ) − 1 ≥ 0 λ i ( y i f ( x i ) − 1 ) 0 (13) \begin{cases} \lambda_i\geq0 \\ y_if(x_i)-1\geq0 \\ \lambda_i(y_if(x_i)-1)0 \end{cases}\tag{13} ⎩ ⎨ ⎧λi≥0yif(xi)−1≥0λi(yif(xi)−1)0(13)
所以对于训练样本 ( x i , y i ) (x_i,y_i) (xi,yi)总有 λ i 1 \lambda_i1 λi1或 y i f ( x i ) 1 y_if(x_i)1 yif(xi)1。
若 λ i 0 \lambda_i0 λi0则有式12 f ( x ) ∑ i 1 m λ i y i x i T x b b f(x)\sum_{i1}^m\lambda_iy_ix_i^Txbb f(x)∑i1mλiyixiTxbb即 λ i \lambda_i λi不会对 f ( x ) f(x) f(x)产生任何影响那么对应的样本不是支持向量因为它对目标函数没有贡献。若 λ i 0 \lambda_i0 λi0则必有 y i f ( x i ) 1 y_if(x_i)1 yif(xi)1所对应的样本点位于最大间隔边界上是一个支持向量。
SMO算法
SMOSequential Minimal Optimization是一种用于求解支持向量机的优化算法。它通过将大优化问题分解为多个小优化子问题的方式每次只优化两个变量从而简化了问题的求解。 SMO算法步骤
选取一对需要更新的变量 λ i \lambda_i λi和 λ j \lambda_j λj固定 λ i \lambda_i λi和 λ j \lambda_j λj以外的参数求解式11获取更新后的 λ i \lambda_i λi和 λ j \lambda_j λj 注意到只选取 λ i \lambda_i λi和 λ j \lambda_j λj中有一个不满足KKT条件目标函数就会在迭代后增大。直观来看KKT条件违背的程度越大则变量更新后可能会导致目标函数值增大。故SMO算法采用如下策略来缓解该情况。 先选取违背KKT条件程度最大的变量。第二个变量选择一个使目标函数值增长最快的变量。 因此SMO算法采取了一个启发式使选取的两变量所对应样本之间的间隔最大。每次的更新使得目标函数的优化达到最大值 直到收敛
SMO算法之所以高效是由于固定其他参数后仅优化两个参数的过程能做到非常高效。具体来说仅考虑 λ i \lambda_i λi和 λ j \lambda_j λj时式11的约束条件可重写为 λ i y i λ j y j c , λ i ≥ 0 λ j ≥ 0 (14) \lambda_iy_i\lambda_jy_jc,\quad \lambda_i\geq0\quad \lambda_j\geq0 \tag{14} λiyiλjyjc,λi≥0λj≥0(14) 其中 c − ∑ k ≠ i , j λ k y k (15) c-\sum_{k\neq i,j} \lambda_ky_k \tag{15} c−ki,j∑λkyk(15) 是使 ∑ i 1 m λ i y i 0 \sum_{i1}^m\lambda_iy_i0 ∑i1mλiyi0成立的常数。用式14 λ j c − λ i y i y j \lambda_j\frac{c-\lambda_iy_i}{y_j} λjyjc−λiyi消去式11中的变量 λ j \lambda_j λj最终得到一个关于 λ i \lambda_i λi的单变量二次规划问题式11可变为 max λ ∑ i 1 m λ i − 1 2 ∑ i 1 m ∑ j 1 m λ i y i ( c − λ i y i ) x i T x j λ i ≥ 0 , i 1 , 2 , … , m (16) \begin{aligned} \underset{\lambda}{\text{max}} \quad \sum_{i1}^m\lambda_i-\frac{1}{2}\sum_{i1}^m\sum_{j1}^m\lambda_iy_i(c-\lambda_iy_i)x_i^Tx_j \\ \ \ \ \ \ \ \ \ \ \ \lambda_i\geq0, \quad i 1, 2, \ldots, m \end{aligned} \tag{16} λmaxi1∑mλi−21i1∑mj1∑mλiyi(c−λiyi)xiTxj λi≥0,i1,2,…,m(16) 确定偏移项 b b b 注意到对任意支持向量 ( x s , y s ) (x_s,y_s) (xs,ys)都有 y s f ( x s ) 1 y_sf(x_s)1 ysf(xs)1即 y s ( ∑ i ∈ S λ i y i x i T x s b ) 1 (17) y_s(\sum_{i \in S}\lambda_iy_ix_i^Tx_sb)1 \tag{17} ys(i∈S∑λiyixiTxsb)1(17) 其中由式12可知 f ( x s ) ∑ i 1 m λ i y i x i T x s b f(x_s)\sum_{i1}^m\lambda_iy_ix_i^Tx_sb f(xs)∑i1mλiyixiTxsb S { i ∣ λ i 0 , i 1 , 2 , . . . , m } S\{i|\lambda_i0,i1,2,...,m\} S{i∣λi0,i1,2,...,m}是所有支持向量的下标集。理论上我们可选择任意的支持向量并通过式17经行求解从而获得 b b b但现实任务中常常采用一种更鲁棒性的做法使用所有支持向量求解的平均值 b 1 ∣ S ∣ ∑ s ∈ S ( 1 / y s − ∑ i ∈ S λ i y i x i T x s ) (18) b\frac{1}{|S|}\sum_{s \in S}(1/y_s-\sum_{i \in S}\lambda_iy_ix_i^Tx_s) \tag{18} b∣S∣1s∈S∑(1/ys−i∈S∑λiyixiTxs)(18)
核函数
核函数是一个能够计算两个输入数据点之间相似度的函数。在 SVM 中核函数的主要目的是将数据映射到高维空间而无需显式地计算新空间的坐标。 例如在上图中若将原始的二维空间映射到一个合适的三维空间就能映射到一个合适的三维空间从而找到一个合适的划分超平面。
令 ϕ ( x ) \phi(x) ϕ(x)表示将 x x x映射后的特征向量于是在特征空间中划分超平面所对应的模型可表示为 f ( x ) w T ϕ ( x ) b (19) f(x)w^T\phi(x)b \tag{19} f(x)wTϕ(x)b(19) 其中 w w w和 b b b是模型参数类似于式6有 max ( w , b ) 1 2 ∣ ∣ w ∣ ∣ 2 s.t. y i ( w T ϕ ( x i ) b ) ≥ 1 , i 1 , 2 , … , m (20) \begin{aligned} \underset{(w, b)}{\text{max}} \quad \frac{1}{2}||w||^2 \\ \text{s.t.} \quad y_i(w^T\phi(x_i) b) \geq 1, \quad i 1, 2, \ldots, m \end{aligned} \tag{20} (w,b)max21∣∣w∣∣2s.t.yi(wTϕ(xi)b)≥1,i1,2,…,m(20) 其对偶问题是 max λ ∑ i 1 m λ i − 1 2 ∑ i 1 m ∑ j 1 m λ i λ j y i y j ϕ ( x i ) T ϕ ( x j ) s.t. ∑ i 1 m λ i y i 0 λ i ≥ 0 , i 1 , 2 , … , m (21) \begin{aligned} \underset{\lambda}{\text{max}} \quad \sum_{i1}^m\lambda_i-\frac{1}{2}\sum_{i1}^m\sum_{j1}^m\lambda_i\lambda_jy_iy_j\phi(x_i)^T\phi(x_j) \\ \text{s.t.} \quad \sum_{i1}^m\lambda_iy_i0 \\ \ \ \ \ \ \ \ \ \ \ \lambda_i\geq0, \quad i 1, 2, \ldots, m \end{aligned} \tag{21} λmaxi1∑mλi−21i1∑mj1∑mλiλjyiyjϕ(xi)Tϕ(xj)s.t.i1∑mλiyi0 λi≥0,i1,2,…,m(21)
求解式21中涉及计算 ϕ ( x i ) T ϕ ( x j ) \phi(x_i)^T\phi(x_j) ϕ(xi)Tϕ(xj)这就是样本 x i x_i xi和 x j x_j xj映射到特征空间之后的内积。由于特征空间的维数高因此直接计算 ϕ ( x i ) T ϕ ( x j ) \phi(x_i)^T\phi(x_j) ϕ(xi)Tϕ(xj)很困难为了避开这个障碍可以设想这样一个函数 κ ( x i , x j ) ⟨ ϕ ( x i ) ϕ ( x j ) ⟩ ϕ ( x i ) T ϕ ( x j ) (22) \kappa(x_i,x_j)\lang\phi(x_i)\phi(x_j)\rang\phi(x_i)^T\phi(x_j) \tag{22} κ(xi,xj)⟨ϕ(xi)ϕ(xj)⟩ϕ(xi)Tϕ(xj)(22)
于是式21可以重写为 max λ ∑ i 1 m λ i − 1 2 ∑ i 1 m ∑ j 1 m λ i λ j y i y j κ ( x i , x j ) s.t. ∑ i 1 m λ i y i 0 λ i ≥ 0 , i 1 , 2 , … , m (23) \begin{aligned} \underset{\lambda}{\text{max}} \quad \sum_{i1}^m\lambda_i-\frac{1}{2}\sum_{i1}^m\sum_{j1}^m\lambda_i\lambda_jy_iy_j\kappa(x_i,x_j) \\ \text{s.t.} \quad \sum_{i1}^m\lambda_iy_i0 \\ \ \ \ \ \ \ \ \ \ \ \lambda_i\geq0, \quad i 1, 2, \ldots, m \end{aligned} \tag{23} λmaxi1∑mλi−21i1∑mj1∑mλiλjyiyjκ(xi,xj)s.t.i1∑mλiyi0 λi≥0,i1,2,…,m(23)
求解后即可得到 f ( x ) w T ϕ ( x ) b ∑ i 1 m λ i y i ϕ ( x i ) T ϕ ( x ) b ∑ i 1 m λ i y i κ ( x , x i ) b (24) \begin{aligned} f(x) w^T\phi(x)b \\ \sum_{i1}^m\lambda_iy_i\phi(x_i)^T\phi(x)b \\ \sum_{i1}^m\lambda_iy_i\kappa(x,x_i) b \end{aligned} \tag{24} f(x)wTϕ(x)bi1∑mλiyiϕ(xi)Tϕ(x)bi1∑mλiyiκ(x,xi)b(24)
这里的 κ ( ⋅ , ⋅ ) \kappa(\cdot,\cdot) κ(⋅,⋅)就是核函数。
定理 6.1核函数 令 χ \chi χ为输入空间 κ ( ⋅ , ⋅ ) \kappa(\cdot,\cdot) κ(⋅,⋅)是定义在 χ × χ \chi \times \chi χ×χ上的对称函数则 κ \kappa κ是核函数当且仅当对于任意数据 D { x 1 , x 2 , . . . , x m } D\{x_1,x_2,...,x_m\} D{x1,x2,...,xm}核矩阵 K \Kappa K总是半正定的即主对角线上全为0且 K ≥ 0 \Kappa \geq0 K≥0 K [ κ ( x 1 , x 1 ) κ ( x 1 , x 2 ) … κ ( x 1 , x m ) κ ( x 2 , x 1 ) κ ( x 2 , x 2 ) … κ ( x 2 , x m ) ⋮ ⋮ ⋱ ⋮ κ ( x m , x 1 ) κ ( x m , x 2 ) … κ ( x m , x m ) ] \Kappa \begin{bmatrix} \kappa(x_1, x_1) \kappa(x_1, x_2) \ldots \kappa(x_1, x_m) \\ \kappa(x_2, x_1) \kappa(x_2, x_2) \ldots \kappa(x_2, x_m) \\ \vdots \vdots \ddots \vdots \\ \kappa(x_m, x_1) \kappa(x_m, x_2) \ldots \kappa(x_m, x_m) \end{bmatrix} K κ(x1,x1)κ(x2,x1)⋮κ(xm,x1)κ(x1,x2)κ(x2,x2)⋮κ(xm,x2)……⋱…κ(x1,xm)κ(x2,xm)⋮κ(xm,xm)
该定理说明只要一个对称函数所对应的核矩阵半正定它就能作为核函数使用。事实上对于一个半正定核矩阵总能找到一个与之对应的映射 ϕ \phi ϕ。换言之任何一个核函数都隐式地定义了一个称为再生核希尔伯特空间的特征空间。 故核函数选择称为支持向量机的最大变数。若核函数选择不合适则意味着将样本映射到一个不合适的特征空间很可能导致性能不佳。 下表是几种常见的核函数 除此之外我们还可以通过函数组合得到
若 κ 1 \kappa_1 κ1和 κ 2 \kappa_2 κ2为核函数则对于任意正数 γ 1 \gamma_1 γ1、 γ 2 \gamma_2 γ2其线性组合 γ 1 κ 1 γ 2 κ 2 (25) \gamma_1\kappa_1\gamma_2\kappa_2\tag{25} γ1κ1γ2κ2(25)
也是核函数。
若 κ 1 \kappa_1 κ1和 κ 2 \kappa_2 κ2为核函数则该核函数的直积 κ 1 ⊗ κ 2 ( x , z ) κ 1 ( x , z ) κ ( x , z ) (26) \kappa_1\otimes\kappa_2(x,z)\kappa_1(x,z)\kappa(x,z)\tag{26} κ1⊗κ2(x,z)κ1(x,z)κ(x,z)(26) 也是核函数。若若 κ 1 \kappa_1 κ1为核函数则对于任意函数 g ( x ) g(x) g(x) κ ( x , z ) g ( x ) κ 1 ( x , z ) g ( z ) (27) \kappa(x,z)g(x)\kappa_1(x,z)g(z) \tag{27} κ(x,z)g(x)κ1(x,z)g(z)(27) 也是核函数。
软间隔与正则化
软间隔
在标准的硬间隔支持向量机中假设训练数据是线性可分的即存在一个超平面能够完美地分开两个类别。然而在实际问题中数据往往是噪音存在或者非线性可分的这时候强调完全分类可能导致过拟合。
为了处理非线性可分的情况和噪音引入了软间隔允许一些样本点出现在分隔超平面的错误一侧。软间隔 SVM 的目标是找到一个最优的超平面最小化误分类的同时允许一些样本点落在间隔内。 软间隔允许某些样本不满足约束 y i ( w T x i b ) ≥ 1 (28) y_i(w^Tx_ib)\geq1 \tag{28} yi(wTxib)≥1(28) 当然在最大化间隔的同时不满足约束的样本应尽可能的少。于是优化目标可写为 max ( w , b ) 1 2 ∣ ∣ w ∣ ∣ 2 C ∑ i 1 m ℓ 0 / 1 ( y i ( w T x i b ) − 1 ) (29) \begin{aligned} \underset{(w, b)}{\text{max}} \quad \frac{1}{2}||w||^2C\sum_{i1}^m \ell_{0/1}(y_i(w^Tx_i b)-1) \\ \end{aligned} \tag{29} (w,b)max21∣∣w∣∣2Ci1∑mℓ0/1(yi(wTxib)−1)(29) 其中 C 0 C0 C0是一个常数容忍范围 ℓ 0 / 1 \ell_{0/1} ℓ0/1是 0/1损失函数(惩罚函数)。 ℓ 0 / 1 ( z ) { 1 , i f z 0 0 , o t h e r w i s e (30) \ell_{0/1}(z) \begin{cases} 1,\quad if \ z 0\\ 0, \quad otherwise \end{cases} \tag{30} ℓ0/1(z){1,if z00,otherwise(30) 显然当 C C C为无穷大时式29迫使所有样本均满足约束式28当 C C C取有极限值时式29允许一些样本不满足约束。
然而现存的问题是 ℓ 0 / 1 \ell_{0/1} ℓ0/1函数的数学性质不好非凸、非连续使得式29不易直接求解。于是人们常用其他一些函数来替代 ℓ 0 / 1 \ell_{0/1} ℓ0/1称为替代函数。替代函数具有较好的数学性质。通常用以下三种常用的替代损失函数 ℓ h i n g e ( z ) m a x ( 0 , 1 − z ) (31) \ell_{hinge}(z)max(0,1-z \tag{31}) ℓhinge(z)max(0,1−z)(31) ℓ e x p ( z ) e − z (32) \ell_{exp}(z)e^{-z} \tag{32} ℓexp(z)e−z(32) ℓ l o g l o g ( 1 e − z ) (33) \ell_{log}log(1e^{-z})\tag{33} ℓloglog(1e−z)(33) 若采用hinge损失则式29变成 max ( w , b ) 1 2 ∣ ∣ w ∣ ∣ 2 C ∑ i 1 m m a x ( 0 , 1 − y i ( w T x i b ) ) (34) \begin{aligned} \underset{(w, b)}{\text{max}} \quad \frac{1}{2}||w||^2C\sum_{i1}^m max(0,1-y_i(w^Tx_i b)) \\ \end{aligned} \tag{34} (w,b)max21∣∣w∣∣2Ci1∑mmax(0,1−yi(wTxib))(34) 引入松弛变量 ξ i ≥ 0 \xi_i\geq0 ξi≥0可将式34重写为 min ( w , b , ξ i ) 1 2 ∣ ∣ w ∣ ∣ 2 C ∑ i 1 m ξ i s.t. y i ( w T x i b ) ≥ 1 − ξ i ξ i ≥ 0 , i 1 , 2 , … , m (35) \begin{aligned} \underset{(w, b,\xi_i)}{\text{min}} \quad \frac{1}{2}||w||^2C\sum_{i1}^m \xi_i \\ \text{s.t.} \quad y_i(w^Tx_ib)\geq1-\xi_i \\ \ \ \ \ \ \ \ \ \ \ \xi_i\geq0, \quad i 1, 2, \ldots, m \end{aligned} \tag{35} (w,b,ξi)min21∣∣w∣∣2Ci1∑mξis.t.yi(wTxib)≥1−ξi ξi≥0,i1,2,…,m(35) 这就是常用的软间隔支持向量机。
显然通过拉格朗日乘子法可得到式35的拉格朗日函数 L ( w , b , λ , ξ , μ ) 1 2 ∣ ∣ w ∣ ∣ 2 C ∑ i 1 m ξ i ∑ i 1 m λ i ( 1 − ξ i − y i ( w T x i b ) ) − ∑ i 1 m μ i ξ i (36) L(w,b,\lambda,\xi,\mu)\frac{1}{2}||w||^2C\sum_{i1}^m \xi_i\sum_{i1}^m \lambda_i(1-\xi_i-y_i(w^Tx_i b))-\sum_{i1}^m\mu_i\xi_i \tag{36} L(w,b,λ,ξ,μ)21∣∣w∣∣2Ci1∑mξii1∑mλi(1−ξi−yi(wTxib))−i1∑mμiξi(36) 其中 λ i ≥ 0 \lambda_i\geq0 λi≥0 μ i ≥ 0 \mu_i\geq0 μi≥0是拉格朗日乘子。 令 L ( w , b , λ , ξ , μ ) L(w,b,\lambda,\xi,\mu) L(w,b,λ,ξ,μ)对 w w w、 b b b、 λ \lambda λ、 ξ \xi ξ和 μ \mu μ的偏导为0可得 { ∂ L ∂ w w − ∑ i 1 m λ i y i x i 0 ∂ L ∂ b − ∑ i 1 m λ i y i 0 ∂ L ∂ λ 1 − ξ i − y i ( w T x i b ) 0 ∂ L ∂ ξ C − ∑ i 1 m λ i − ∑ i 1 m μ i 0 ∂ L ∂ μ − ∑ i 1 m ξ i 0 \begin{cases} \frac{\partial L}{\partial w}w-\sum_{i1}^m\lambda_iy_ix_i0 \\ \frac{\partial L}{\partial b}-\sum_{i1}^m\lambda_iy_i0 \\ \frac{\partial L}{\partial \lambda}1-\xi_i-y_i(w^Tx_i b)0\\ \frac{\partial L}{\partial \xi}C-\sum_{i1}^m\lambda_i-\sum_{i1}^m\mu_i0\\ \frac{\partial L}{\partial \mu}-\sum_{i1}^m\xi_i0 \end{cases} ⎩ ⎨ ⎧∂w∂Lw−∑i1mλiyixi0∂b∂L−∑i1mλiyi0∂λ∂L1−ξi−yi(wTxib)0∂ξ∂LC−∑i1mλi−∑i1mμi0∂μ∂L−∑i1mξi0 整理可得 w ∑ i 1 m λ i y i x i (37) w\sum_{i1}^m\lambda_iy_ix_i \tag{37} wi1∑mλiyixi(37) ∑ i 1 m λ i y i 0 (38) \sum_{i1}^m\lambda_iy_i0 \tag{38} i1∑mλiyi0(38) C ∑ i 1 m λ i ∑ i 1 m μ i (39) C \sum_{i1}^m\lambda_i\sum_{i1}^m\mu_i\tag{39} Ci1∑mλii1∑mμi(39) 将式37-39带入式子35中可得到式40的对偶问题 min ( w , b , ξ i ) ∑ i 1 m λ i 1 2 ∑ i 1 m ∑ j 1 m λ i λ j y i y j x i T x j s.t. ∑ i 1 m λ i y i 0 0 ≤ λ i ≤ C , i 1 , 2 , … , m (40) \begin{aligned} \underset{(w, b,\xi_i)}{\text{min}} \quad \sum_{i1}^m\lambda_i\frac{1}{2}\sum_{i1}^m\sum_{j1}^m \lambda_i\lambda_jy_iy_jx_i^Tx_j \\ \text{s.t.} \quad \sum_{i1}^m\lambda_iy_i0 \\ \ \ \ \ \ \ \ \ \ \ 0\leq\lambda_i\leq C, \quad i 1, 2, \ldots, m \end{aligned} \tag{40} (w,b,ξi)mini1∑mλi21i1∑mj1∑mλiλjyiyjxiTxjs.t.i1∑mλiyi0 0≤λi≤C,i1,2,…,m(40) 软间隔相较于硬间隔两个唯一的差别就在于对偶变量的约束不同前者是 0 ≤ λ i ≤ C 0\leq \lambda_i\leq C 0≤λi≤C后者是 0 ≤ λ i 0\leq \lambda_i 0≤λi。于是可采用与硬间隔同样的方法去解决软间隔。类似的对于软间隔支持向量机KKT条件要求 { λ i ≥ 0 , μ i ≥ 0 y i f ( x i ) − 1 ξ i ≥ 0 λ i ( y i f ( x i ) − 1 ξ i ) 0 ξ i ≥ 0 , μ i ξ i 0 (41) \begin{cases} \lambda_i\geq0,\quad \mu_i\geq0 \\ y_if(x_i)-1\xi_i\geq0 \\ \lambda_i(y_if(x_i)-1\xi_i)0 \\ \xi_i\geq0,\quad \mu_i\xi_i0 \end{cases}\tag{41} ⎩ ⎨ ⎧λi≥0,μi≥0yif(xi)−1ξi≥0λi(yif(xi)−1ξi)0ξi≥0,μiξi0(41)
所以对于训练样本 ( x i , y i ) (x_i,y_i) (xi,yi)总有 λ i 1 \lambda_i1 λi1或 y i f ( x i ) 1 − ξ i y_if(x_i)1-\xi_i yif(xi)1−ξi。
若 λ i 0 \lambda_i0 λi0则有式12 f ( x ) ∑ i 1 m λ i y i x i T x b b f(x)\sum_{i1}^m\lambda_iy_ix_i^Txbb f(x)∑i1mλiyixiTxbb即 λ i \lambda_i λi不会对 f ( x ) f(x) f(x)产生任何影响那么对应的样本不是支持向量因为它对目标函数没有贡献。若 λ i 0 \lambda_i0 λi0则必有 y i f ( x i ) 1 − ξ i y_if(x_i)1-\xi_i yif(xi)1−ξi是一个支持向量。
由式39可知
若 λ i C \lambda_iC λiC则 μ i 0 \mu_i0 μi0又因为 μ i ξ i 0 \mu_i\xi_i0 μiξi0进而有 ξ i 0 \xi_i0 ξi0即样本呢恰好在最大间隔边界上。 ≤ \leq ≤若 λ i C \lambda_iC λiC则 μ i 0 \mu_i0 μi0 此时若 ξ i ≤ 1 \xi_i\leq1 ξi≤1则样本落在最大间隔内部。若 ξ i 1 \xi_i1 ξi1则该样本被分类错误。 由此可知软间隔支持向量机的最终模型仅与支持向量有关通过使用了 hinge 损失函数。这个损失函数在一定程度上惩罚了误分类的数据点并且对于正确分类的数据点和那些在间隔内但仍允许一定误差的数据点是不敏感的。因此对于在间隔内的数据点只有当它们的误差超过一定阈值时才会对模型参数的更新产生影响否则它们的存在对模型的稀疏性保持了贡献。
正则化罚函数法
我们可以把式29中的 0 / 1 0/1 0/1损失函数替换成别的替代损失函数从而得到其他的学习模型这些模型的性质与所用的替代函数直接相关他们都具有相同的共性
第一项描述划分超平面的间隔大小。另一项 ∑ i 1 m ℓ ( f ( x i ) , y i ) \sum_{i1}^m\ell(f(x_i),y_i) ∑i1mℓ(f(xi),yi)用来表述训练集上的误差。
故我们可以写成更一般的形式 min f Ω ( f ) C ∑ i 1 m ℓ ( f ( x i ) , y i ) (42) \begin{aligned} \underset{f}{\text{min}} \quad \Omega(f)C\sum_{i1}^m \ell(f(x_i),y_i) \\ \end{aligned} \tag{42} fminΩ(f)Ci1∑mℓ(f(xi),yi)(42)
其中 Ω ( f ) \Omega(f) Ω(f)称为结构风险用于描述模型 f f f的性质。第二项 ∑ i 1 m ℓ ( f ( x i ) , y i ) \sum_{i1}^m \ell(f(x_i),y_i) ∑i1mℓ(f(xi),yi)称为经验风险用于描述模型与训练数据的契合程度。 C C C用于对二者进行折中。
以正则化的角度来说 Ω ( f ) \Omega(f) Ω(f)被称作正则化项 C C C称为正则化常数。 L p L_p Lp范数是常用的正则化项其中 L 2 L_2 L2范数 ∣ ∣ w ∣ ∣ 2 ||w||_2 ∣∣w∣∣2倾向于 w w w的分量取值尽量均衡即非零分量个数尽量稠密而 L 0 L_0 L0范数 ∣ ∣ w ∣ ∣ 0 ||w||_0 ∣∣w∣∣0和 L 1 L_1 L1范数 ∣ ∣ w ∣ ∣ 1 ||w||_1 ∣∣w∣∣1则倾向于 w w w的分量尽量稀疏即非零分量个数尽量少。 范数 下面我们来详细说明一下非零分量个数尽量少和非零分量个数尽量稠密 非零分量个数尽量少 这意味着在模型的参数中很多权重被设为零而只有少数权重是非零的。这通常是通过使用 L 1 L_1 L1 范数正则化来实现的因为 L 1 L_1 L1 范数鼓励参数向量中的某些元素取零值使得模型更加稀疏。目的是为了让模型更加简单降低模型的复杂度以防止过拟合。在某些场景下只有少数几个特征对预测结果有显著的贡献而其他特征的权重可以被设置为零。 非零分量个数尽量稠密 这意味着模型的参数中非零元素的分布相对均匀而非零权重的数量相对较多。这通常是通过使用 L 2 L_2 L2 范数正则化来实现的因为 L 2 L_2 L2 范数鼓励参数向量中的所有元素都较小但非零元素的数量不一定很少。目的是为了平衡模型各个参数的影响防止某些特征对预测结果过于显著以免引入不必要的偏差。
模型的稀疏性
模型的稀疏性是指在模型中只有少数非零参数或特征的性质。在统计学和机器学习中一个稀疏的模型意味着模型的大部分参数或特征都是零只有一小部分参数或特征对最终的预测起到关键作用。
对于线性模型稀疏性通常表现为只有一小部分权重对最终的预测有贡献其他权重为零。对于特征选择和解释性而言稀疏性是一个重要的性质因为它可以帮助识别对输出变量有显著影响的关键特征。
支持向量机SVM是一种能够产生稀疏模型的算法。在软间隔支持向量机中只有一小部分数据点被称为支持向量它们对于定义决策边界和间隔的计算起到关键作用而其他数据点对于模型的参数调整影响较小。
稀疏模型有一些优点包括 更好的泛化能力 稀疏模型通常对未见过的数据更具泛化能力因为它们更倾向于捕捉数据中真正重要的模式而不受不相关的特征的干扰。 更容易解释 当模型的大部分参数为零时模型的解释变得更加简单和直观。只有非零参数或特征需要考虑这有助于理解模型在决策时的关键因素。 减少存储和计算成本 稀疏模型需要存储和计算的资源较少因为只有少数参数或特征需要被处理。
结论
在本篇文章中我们深入探讨了支持向量机SVM的基本原理、核函数的作用以及正则化的概念。通过详细介绍硬间隔和软间隔支持向量机的推导过程我们理解了在处理非线性可分数据和噪音时软间隔的重要性。
核函数作为 SVM 中的关键组成部分通过将数据映射到高维空间使得在原始特征空间中线性不可分的问题在新的特征空间中变得线性可分。我们还介绍了常见的核函数及其组合形式以及核函数与再生核希尔伯特空间的关系。
正则化在软间隔支持向量机中发挥了关键作用通过引入正则化项我们可以在最大化间隔的同时控制模型的复杂度使其更好地泛化到新的数据。不同范数的使用对模型的稀疏性产生不同影响这在解释性和计算效率上都具有重要意义。
最后我们强调了稀疏模型的优势包括更好的泛化能力、更容易解释和减少资源消耗。这篇文章为读者提供了深入理解支持向量机及其相关概念的基础有助于读者更好地应用和理解这一强大的机器学习算法。
实验分析
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score# 读取数据集
df pd.read_csv(data/nonlinear_svm_ring_dataset.csv)该数据集所对应的散点图
# 绘制散点图
plt.scatter(df[df[Label] 1][Feature1], df[df[Label] 1][Feature2], labelClass 1)
plt.scatter(df[df[Label] -1][Feature1], df[df[Label] -1][Feature2], labelClass -1)plt.xlabel(Feature 1)
plt.ylabel(Feature 2)
plt.legend()
plt.title(Nonlinear SVM Ring Dataset)
plt.show()数据升维后的散点图
# 创建3D图形
fig plt.figure()
ax fig.add_subplot(111, projection3d)# 绘制3D散点图
ax.scatter(X_test[y_test 1][Feature1], X_test[y_test 1][Feature2], y_test[y_test 1], labelClass 1)
ax.scatter(X_test[y_test -1][Feature1], X_test[y_test -1][Feature2], y_test[y_test -1], labelClass -1)# 设置坐标轴标签
ax.set_xlabel(Feature 1)
ax.set_ylabel(Feature 2)
ax.set_zlabel(Label)# 添加图例
ax.legend()
plt.title(SVM Decision Boundary on Nonlinear Separable Dataset (3D))# 显示图形
plt.show()划分数据集
# 准备数据
X df[[Feature1, Feature2]]
y df[Label]# 划分训练集和测试集
X_train, X_test, y_train, y_test train_test_split(X, y, test_size0.2, random_state42)明显线性可分了
先采用LDA线性判别分析看看其模型的表现如何 LDA # 初始化LDA模型
lda_model LinearDiscriminantAnalysis()# 拟合模型
lda_model.fit(X_train, y_train)# 在测试集上进行预测
y_pred lda_model.predict(X_test)# 计算准确度
accuracy accuracy_score(y_test, y_pred)
print(fAccuracy: {accuracy * 100:.2f}%)# 绘制决策边界
plt.scatter(df[df[Label] 1][Feature1], df[df[Label] 1][Feature2], labelClass 1)
plt.scatter(df[df[Label] -1][Feature1], df[df[Label] -1][Feature2], labelClass -1)# 绘制决策边界
xx, yy np.meshgrid(np.linspace(np.min(X[Feature1]), np.max(X[Feature1]), 100),np.linspace(np.min(X[Feature2]), np.max(X[Feature2]), 100))
Z lda_model.decision_function(np.c_[xx.ravel(), yy.ravel()])
Z Z.reshape(xx.shape)plt.contour(xx, yy, Z, colorsk, levels[0], linestylesdashed)plt.xlabel(Feature 1)
plt.ylabel(Feature 2)
plt.legend()
plt.title(LDA Decision Boundary on Nonlinear Separable Dataset)
plt.show()Accuracy: 45.00%显然模型在非线性数据下表现不佳
然后采用SVM支持向量机看看模型的表现如何
# 初始化SVM模型
svm_model SVC(kernelrbf, C1.0, gammascale)# 拟合模型
svm_model.fit(X_train, y_train)# 在测试集上进行预测
y_pred svm_model.predict(X_test)# 计算准确度
accuracy accuracy_score(y_test, y_pred)
print(fAccuracy: {accuracy * 100:.2f}%)# 绘制散点图
plt.scatter(df[df[Label] 1][Feature1], df[df[Label] 1][Feature2], labelClass 1)
plt.scatter(df[df[Label] -1][Feature1], df[df[Label] -1][Feature2], labelClass -1)# 绘制决策边界
xx, yy np.meshgrid(np.linspace(np.min(X[Feature1]), np.max(X[Feature1]), 100),np.linspace(np.min(X[Feature2]), np.max(X[Feature2]), 100))
Z svm_model.decision_function(np.c_[xx.ravel(), yy.ravel()])
Z Z.reshape(xx.shape)plt.contour(xx, yy, Z, colorsk, levels[0], linestylesdashed)plt.xlabel(Feature 1)
plt.ylabel(Feature 2)
plt.legend()
plt.title(SVM Decision Boundary on Nonlinear Separable Dataset)
plt.show()Accuracy: 100.00%显然SVM在该数据集下表现良好
在非线性可分数据集上通过使用线性判别分析LDA和支持向量机SVM两种不同的分类器进行比较 LDA模型 准确度45.00%决策边界LDA在非线性可分数据集上表现不佳因为它是线性分类器无法很好地捕捉数据中的非线性关系。 SVM模型 准确度100.00%决策边界SVM在非线性可分数据集上表现良好通过使用径向基函数RBF kernelSVM能够将数据映射到高维空间并在该空间中找到有效的决策边界实现了高准确度的分类。
总结在处理非线性可分数据集时SVM相对于LDA表现更好。SVM通过引入核函数实现了将数据映射到更高维度的特征空间从而能够更好地处理非线性关系。
