【AI】机器学习——支持向量机(线性模型)_ai计算支持向量机

支持向量机是一种二分类算法，通过在高维空间中构建超平面实现对样本的分类

5. 支持向量机(非线性SVM)

---

线性可分SVM通过硬间隔最大化求出划分超平面，解决线性分类问题

线性SVM通过软间隔最大化求出划分超平面，解决线性分类问题

5.1 SVM概述

解决的问题：二分类问题

目标：通过间隔最大化策略，找一个超平面 ${\omega }^{\ast }\cdot x+b^{\ast }=0$ ，将特征空间划分为两部分 { + 1 , − 1 } \{+1,-1\} {+1,−1}

模型：定义在特征空间上的 间隔最大 的线性分类器

• 间隔最大是与感知机有区别的地方
• 通过核技巧，使SVM成为非线性分类器/回归器

策略：间隔最大化 $\to$ 凸二次化（加约束项）

• 正则化的合页损失函数最小化

算法：求解凸二次规划的最优化算法

5.1.1 分类

支持向量机 { S V C ( 支持向量分类机 ) { 线性支持向量机 { 线性可分：硬间隔最大化 近似线性可分：软间隔最大化 非线性支持向量机：核技巧 + 软间隔最大化 S V R ( 支持向量回归机 ) 支持向量机

$$\begin{cases} SVC(支持向量分类机)\begin{cases} 线性支持向量机\begin{cases} 线性可分：硬间隔最大化\\ 近似线性可分：软间隔最大化 \end{cases}$$ \\ 非线性支持向量机：核技巧+软间隔最大化 \end{cases}\\ SVR(支持向量回归机) \end{cases} 支持向量机⎩ ⎨ ⎧​SVC(支持向量分类机)⎩ ⎨ ⎧​线性支持向量机{线性可分：硬间隔最大化近似线性可分：软间隔最大化​非线性支持向量机：核技巧+软间隔最大化​SVR(支持向量回归机)​

数据集
D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } , x i ∈ X ⊆ R n , y ∈ { + 1 , − 1 } , i = 1 , 2 , ⋯   , N D=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\},x_i\in\mathcal{X}\subseteq R^n,y\in \{+1,-1\},i=1,2,\cdots,N D={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)},xi​∈X⊆Rn,y∈{+1,−1},i=1,2,⋯,N

5.2 线性可分SVM

eg：SVM解决二分类问题的思路

线性可分的数据集可以简化为二维平面上的点集。

在直角坐标系中，如果有若干个点位于 $x$ 轴下方，另外若干个点位于 $x$ 轴上方，这两个点集共同构成了一个线性可分的训练数据集，而 $x$ 轴就是将它们区别开的一维超平面，也就是直线。

假设 $x$ 轴上方的点全部位于直线 $y=1$ 上及其上方，$x$ 轴下方的点全部位于直线 $y=-2$ 上及其下方。则任何平行于 $x$ 轴且在 $(-2,1)$ 之间的直线都可以将这个训练集分开。但此时面临选择哪一条直线分类效果最好的问题。

直观上看 $y=-0.5$ 最好，这条分界线正好位于两个边界中间，与两个类别的间隔 可以同时达到最大。当训练集中的数据因为噪音干扰而移动时，这个最优划分超平面的划分精确度受到的影响最小，具有很强的泛化能力

5.2.1 线性可分SVM基本思想

在高维的特征空间上，划分超平面可以用简单的线性方程描述
$$\omega \cdot x+b=0$$

• $n$ 维向量 $\omega$ 为法向量，决定了超平面的方向
• $b$ 为截距，决定了超平面与高维空间中原点的距离

划分超平面将特征空间分为两部分

• 法向量所指一侧——正例，$y=+1$
• 法向量反方向恻——负例，$y=-1$

决策函数：
$$f(x)=sign(\omega \cdot x+b)$$

5.2.2 策略

硬间隔最大化策略 ——使距离超平面最近的两个点之间的间距最大

函数间隔

超平面 $(\omega ,b)$ 关于 $(x_i,y_i)$ 的函数间隔
$${\gamma }_i=y_i(\omega \cdot x_i+b)$$

• 符号：是否分类正确
• 大小：确信程度—— $|\omega \cdot x_i+b|$ 表示点到超平面的远近程度

超平面关于数据集 $D$ 的函数间隔
$$\hat{\gamma }=\underset{x_i\in \mathcal{X}}{\min }\widehat{{\gamma }_i}=\underset{x_i\in \mathcal{X}}{\min }{y}_i(\omega \cdot +b)$$
可用函数间隔表示分类的正确性和确信程度

几何间隔

给定超平面后，特征空间中的样本点 $x_i$ 到超平面的距离可以表示为
$$\begin{gathered} +1类到超平面的距离：{\gamma }_i=\frac{\omega \cdot x_i+b}{\Vert \omega {\Vert }_2} \\ -1类到超平面的距离：{\gamma }_i=-\frac{\omega \cdot x_i+b}{\Vert \omega {\Vert }_2} \end{gathered}$$
即点被正确分类时，到超平面几何距离
$${\gamma }_i=y_i\left(\frac{\omega \cdot x_i+b}{\Vert \omega {\Vert }_2}\right)$$

• 这个距离是一个归一化距离——几何间隔

数据集 $D$ 到超平面 $(\omega ,b)$ 的几何距离
γ = min ⁡ x i ∈ X ω T ⋅ x i + b ∥ ω ∥ 2 = min ⁡ x i ∈ X γ ^ i ∥ ω ∥ 2

$$\begin{aligned} \gamma&=\min\limits_{x_i\in \mathcal{X}}\frac{\omega^T\cdot x_i+b}{\Vert \omega\Vert_2}\\ &=\min\limits_{x_i\in \mathcal{X}}\frac{\hat{\gamma}_i}{\Vert \omega\Vert_2} \end{aligned}$$ γ​=xi​∈Xmin​∥ω∥2​ωT⋅xi​+b​=xi​∈Xmin​∥ω∥2​γ^​i​​​

硬间隔最大化

定理 ：最大分离超平面存在且唯一
{ max ⁡ ω , b γ = max ⁡ ω , b min ⁡ x i ∈ X ω ⋅ x i + b ∥ ω ∥ 2 = max ⁡ ω , b min ⁡ x i ∈ X γ ^ i ∥ ω ∥ 2 s . t . y i ( ω ⋅ x i + b ∥ ω ∥ ) ≥ γ

$$\begin{cases} \max\limits_{\omega,b}\gamma=\max\limits_{\omega,b}\min\limits_{x_i\in \mathcal{X}}\frac{\omega\cdot x_i+b}{\Vert \omega\Vert_2}=\max\limits_{\omega,b}\min\limits_{x_i\in \mathcal{X}}\frac{\hat{\gamma}_i}{\Vert \omega\Vert_2}\\ s.t.\quad y_i\left(\frac{\omega\cdot x_i+b}{\Vert \omega\Vert}\right)\ge \gamma \end{cases}$$ ⎩ ⎨ ⎧​ω,bmax​γ=ω,bmax​xi​∈Xmin​∥ω∥2​ω⋅xi​+b​=ω,bmax​xi​∈Xmin​∥ω∥2​γ^​i​​s.t.yi​(∥ω∥ω⋅xi​+b​)≥γ​

可通过等比例调整参数 $\omega$ 和 $b$ ，可以使每个样本到达最优划分超平面的函数距离都不小于 $1$
$$\begin{gathered} {\lambda }_i(\omega \cdot x_i+b)\ge 1,y_i=+1 \\ {\lambda }_i(\omega \cdot x_i+b)\le -1,y_i=-1 \end{gathered}$$
设 ${\lambda }_i=\frac{1}{\omega x_i+b}$ ，有
$$|{\hat{\gamma }}^{\prime }|=|\lambda \hat{\gamma }|\ge 1$$
问题变为
{ max ⁡ ω , b γ ′ = max ⁡ ω , b min ⁡ x i ∈ X λ y i ( ω ⋅ x i + b ) ∥ λ ω ∥ 2 ≥ max ⁡ ω , b 1 ∥ ω ′ ∥ 2 s . t . λ y i ( ω ⋅ x i + b ) ∥ λ ω ∥ 2 = y i ( ω ′ ⋅ x i + b ) ∥ ω ′ ∥ 2 ≥ γ ′ ⇒ { max ⁡ ω , b γ = max ⁡ ω , b 1 ∥ ω ∥ 2 s . t . y i ( ω ⋅ x i + b ) ≥ 1 , i = 1 , 2 , ⋯   , N    ⟺    便于凸二次规划 { min ⁡ ω , b 1 γ = min ⁡ ω , b ∥ ω ∥ 2 2 2 s . t . y i ( ω ⋅ x i + b ) − 1 ≥ 0 , i = 1 , 2 , ⋯   , N    ⟺    { min ⁡ ω , b ∥ ω ∥ 2 2 2 s . t . 1 − y i ( ω ⋅ x i + b ) ≤ 0 , i = 1 , 2 , ⋯   , N

$$\begin{aligned} &\begin{cases} \max\limits_{\omega,b}\gamma'=\max\limits_{\omega,b}\min\limits_{x_i\in \mathcal{X}}\frac{\lambda y_i(\omega\cdot x_i+b)}{\Vert \lambda\omega\Vert_2}\ge \max\limits_{\omega,b}\frac{1}{\Vert \omega'\Vert_2}\\ s.t.\quad \frac{\lambda y_i(\omega\cdot x_i+b)}{\Vert \lambda\omega\Vert_2}=\frac{y_i(\omega'\cdot x_i+b)}{\Vert \omega'\Vert_2}\ge \gamma' \end{cases}\\ \Rightarrow &\begin{cases} \max\limits_{\omega,b}\gamma=\max\limits_{\omega,b}\frac{1}{\Vert \omega\Vert_2}\\ s.t.\quad y_i(\omega\cdot x_i+b)\ge 1,i=1,2,\cdots,N \end{cases}\\ \overset{便于凸二次规划}{\iff} &\begin{cases} \min\limits_{\omega,b}\frac{1}{\gamma}=\min\limits_{\omega,b}\frac{\Vert \omega\Vert_2^2}{2}\\ s.t.\quad y_i(\omega\cdot x_i+b)-1\ge 0,i=1,2,\cdots,N \end{cases}\\ \iff&\begin{cases} \min\limits_{\omega,b}\frac{\Vert \omega\Vert_2^2}{2}\\ s.t.\quad 1-y_i(\omega\cdot x_i+b)\le 0,i=1,2,\cdots,N \end{cases} \end{aligned}$$ ⇒⟺便于凸二次规划​⟺​⎩ ⎨ ⎧​ω,bmax​γ′=ω,bmax​xi​∈Xmin​∥λω∥2​λyi​(ω⋅xi​+b)​≥ω,bmax​∥ω′∥2​1​s.t.∥λω∥2​λyi​(ω⋅xi​+b)​=∥ω′∥2​yi​(ω′⋅xi​+b)​≥γ′​⎩ ⎨ ⎧​ω,bmax​γ=ω,bmax​∥ω∥2​1​s.t.yi​(ω⋅xi​+b)≥1,i=1,2,⋯,N​⎩ ⎨ ⎧​ω,bmin​γ1​=ω,bmin​2∥ω∥22​​s.t.yi​(ω⋅xi​+b)−1≥0,i=1,2,⋯,N​⎩ ⎨ ⎧​ω,bmin​2∥ω∥22​​s.t.1−yi​(ω⋅xi​+b)≤0,i=1,2,⋯,N​​

5.2.3 原始算法

输入 ：线性可分的数据集
D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } , x i ∈ X ⊆ R n , y i ∈ Y = { + 1 , − 1 } , i = 1 , 2 , ⋯   , N

$$\begin{aligned} D=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\},x_i\in \mathcal{X}\subseteq R^n,y_i\in \mathcal{Y}=\{+1,-1\},i=1,2,\cdots,N \end{aligned}$$ D={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)},xi​∈X⊆Rn,yi​∈Y={+1,−1},i=1,2,⋯,N​
输出 ：最大分离超平面和决策函数

步骤

1. 构造并求解最优化问题
   { min ⁡ ω , b ∥ ω ∥ 2 2 2 s . t . 1 − y i ( ω ⋅ x i + b ) ≤ 0 , i = 1 , 2 , ⋯   , N

   $$\begin{cases} \min\limits_{\omega,b}\frac{\Vert \omega\Vert_2^2}{2}\\ s.t.\quad 1-y_i(\omega\cdot x_i+b)\le 0,i=1,2,\cdots,N \end{cases}$$ ⎩ ⎨ ⎧​ω,bmin​2∥ω∥22​​s.t.1−yi​(ω⋅xi​+b)≤0,i=1,2,⋯,N​
   凸二次规划可得最优解 ${\omega }^{\ast },b^{\ast }$

2. 可得分类超平面
   $${\omega }^{\ast }\cdot x+b^{\ast }=0$$
   决策函数 $f(x)=sign({\omega }^{\ast }\cdot x+b^{\ast })$

支持向量

在特征空间中，距离划分超平面最近的样本点能让函数间隔取等号，这些样本点称为 支持向量 ，即有点 $x_{k^{+}},x_{k^{-}}$
$$\begin{gathered} \omega \cdot x_{k^{+}}+b=1,y_{k^{+}}=+1 \\ \omega \cdot x_{k^{-}}+b=-1,y_{k^{-}}=-1 \end{gathered}$$

• $H_1,H_2$ 为分类间隔边界；$S$ 为分离超平面

两个异类支持向量到超平面的距离之和为 $\frac{2}{\Vert \omega \Vert }$ 。

因而对于线性可分的SVM任务就是：在满足上述不等式的条件下，寻找 $\frac{2}{\Vert \omega \Vert }$ 的最大值，最大化 $\frac{2}{\Vert \omega \Vert }$ 等效于最小化 $\frac{1}{2}\Vert \omega {\Vert }^2$

5.2.4 对偶形式

输入：
D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } ∈ X ∈ R n , y i ∈ Y ∈ { + 1 , − 1 } , i = 1 , ⋯   , N D=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}\in \mathcal{X}\in R^n,y_i\in \mathcal{Y}\in \{+1,-1\},i=1,\cdots,N D={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}∈X∈Rn,yi​∈Y∈{+1,−1},i=1,⋯,N
输出：分离超平面和决策函数

算法

1. 构造并求解对偶问题

由原始算法，可得 Lagrange 函数
$$L(\omega ,b,\alpha )=\frac{1}{2}\Vert \omega {\Vert }_2^2+\sum _{i=1}^N{\alpha }_i[1-y_i({\omega }_i\cdot x_i+b)],{\alpha }_i\ge 0$$
$\frac{1}{2}\Vert \omega {\Vert }_2^2$ 为凸函数，约束范围为凸集，则有 $局部最优解=全局最优解$
最优解 ∈ 约束域 , 即 1 − y i ( ω i ⋅ x i + b ) < 0 最优解 ∉ 约束域 , 即最优解在约束边界上，有 1 − y i ( ω i ⋅ x i + b ) = 0 } ⇒ max ⁡ α i α i [ 1 − y i ( ω i ⋅ x i + b ) ] = 0 \left.

$$\begin{aligned} 最优解\in 约束域,即1-y_i(\omega_i\cdot x_i+b)<0\\ 最优解\notin 约束域,即最优解在约束边界上，有1-y_i(\omega_i\cdot x_i+b)=0 \end{aligned}$$ \right\}\Rightarrow \max\limits_{\alpha_i}\alpha_i[1-y_i(\omega_i\cdot x_i+b)]=0 最优解∈约束域,即1−yi​(ωi​⋅xi​+b)<0最优解∈/约束域,即最优解在约束边界上，有1−yi​(ωi​⋅xi​+b)=0​}⇒αi​max​αi​[1−yi​(ωi​⋅xi​+b)]=0
可知 $\underset{\alpha }{\max }L(\omega ,b,\alpha )=\frac{1}{2}\Vert \omega {\Vert }_2^2$ ，即
$$\underset{\omega }{\min }\frac{1}{2}\Vert \omega {\Vert }_2^2=\underset{\omega }{\min }\underset{\alpha }{\max }L(\omega ,\alpha )$$
又由于 $\underset{\omega }{\min }\underset{\alpha }{\max }L(\omega ,b,\alpha )$ 与 $\underset{\alpha }{\max }\underset{\omega }{\min }L(\omega ,b,\alpha )$ 是对偶问题，有相同的最优解

• 对偶问题(极小中求极大)，相当于求原问题(极大中求极小)的下界

最优解满足KKT条件
{ ∂ L ∂ ω = 0 ∂ L ∂ b = 0 ∂ L ∂ α i = 0 α i ≥ 0 α i [ 1 − y i ( ω i ⋅ x i + b ) ] ≤ 0 ⇒ { ω − ∑ i = 1 N α i y i x i = 0 − ∑ i = 1 N α i y i = 0 1 − y i ( ω i ⋅ x i + b ) = 0 α i ≥ 0 α i [ 1 − y i ( ω i ⋅ x i + b ) ] ≤ 0

$$\begin{cases} \frac{\partial L}{\partial \omega}=0\\ \frac{\partial L}{\partial b}=0\\ \frac{\partial L}{\partial \alpha_i}=0\\ \alpha_i\ge 0\\ \alpha_i[1-y_i(\omega_i\cdot x_i+b)]\le 0 \end{cases}$$ \Rightarrow $$\begin{cases} \omega-\sum\limits_{i=1}^N\alpha_iy_ix_i=0\\ -\sum\limits_{i=1}^N\alpha_iy_i=0\\ 1-y_i(\omega_i\cdot x_i+b)=0\\ \alpha_i\ge 0\\ \alpha_i[1-y_i(\omega_i\cdot x_i+b)]\le 0 \end{cases}$$ ⎩ ⎨ ⎧​∂ω∂L​=0∂b∂L​=0∂αi​∂L​=0αi​≥0αi​[1−yi​(ωi​⋅xi​+b)]≤0​⇒⎩ ⎨ ⎧​ω−i=1∑N​αi​yi​xi​=0−i=1∑N​αi​yi​=01−yi​(ωi​⋅xi​+b)=0αi​≥0αi​[1−yi​(ωi​⋅xi​+b)]≤0​
即有 ${\omega }^{\ast }=\sum _{i=1}^N{\alpha }_i{y}_i{x}_i$ ，代入 $L(\omega ,b,\alpha )$

min ⁡ ω , b L ( α ) = 1 2 ( ω ∗ ) T ω ∗ + ∑ i = 1 N α i − ∑ i = 1 N α i y i ω ∗ ⋅ x i − ∑ i = 1 N α i y i b = 1 2 ∑ j = 1 N α j y j x j ∑ i = 1 N α i y i x i + ∑ i = 1 N α i − ∑ i = 1 N α i y i ∑ j = 1 N α j y j x j = x j ⋅ , x i 为向量点积，其余部分为标量 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i ⋅ x j − ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i ⋅ x j + ∑ i = 1 N α i = ∑ i = 1 N α i − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i ⋅ x j

$$\begin{aligned} \min\limits_{\omega,b}L(\alpha)&=\frac{1}{2}(\omega^*)^T\omega^*+\sum\limits_{i=1}^N\alpha_i-\sum\limits_{i=1}^N\alpha_iy_i\omega^*\cdot x_i-\sum\limits_{i=1}^N\alpha_iy_i b\\ &=\frac{1}{2}\sum\limits_{j=1}^N\alpha_jy_jx_j\sum\limits_{i=1}^N\alpha_iy_ix_i+\sum\limits_{i=1}^N\alpha_i-\sum\limits_{i=1}^N\alpha_iy_i\sum\limits_{j=1}^N\alpha_jy_jx_j\\ &\xlongequal{x_j\cdot,x_i为向量点积，其余部分为标量}\frac{1}{2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N\alpha_i\alpha_jy_iy_jx_i\cdot x_j-\sum\limits_{i=1}^N\sum\limits_{j=1}^N\alpha_i\alpha_jy_iy_jx_i\cdot x_j+\sum\limits_{i=1}^N\alpha_i\\ &=\sum\limits_{i=1}^N\alpha_i-\frac{1}{2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N\alpha_i\alpha_jy_iy_jx_i\cdot x_j \end{aligned}$$ ω,bmin​L(α)​=21​(ω∗)Tω∗+i=1∑N​αi​−i=1∑N​αi​yi​ω∗⋅xi​−i=1∑N​αi​yi​b=21​j=1∑N​αj​yj​xj​i=1∑N​αi​yi​xi​+i=1∑N​αi​−i=1∑N​αi​yi​j=1∑N​αj​yj​xj​xj​⋅,xi​为向量点积，其余部分为标量 21​i=1∑N​j=1∑N​αi​αj​yi​yj​xi​⋅xj​−i=1∑N​j=1∑N​αi​αj​yi​yj​xi​⋅xj​+i=1∑N​αi​=i=1∑N​αi​−21​i=1∑N​j=1∑N​αi​αj​yi​yj​xi​⋅xj​​
对偶问题
$$\{\begin{array}{l}\underset{\alpha }{\max }L(\alpha )=\sum _{i=1}^N{\alpha }_i-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i\cdot x_j\\ s.t.{\alpha }_i\ge 0\\ \sum _{i=1}^N{\alpha }_i{y}_i=0\end{array}$$
求解对偶问题，可得 ${\alpha }^{\ast }=\left(\begin{array}{r}{\alpha }_1^{\ast }\\ {\alpha }_2^{\ast }\\ ⋮\\ {\alpha }_N^{\ast }\end{array}\right)$

2. 计算参数

由 ${\alpha }^{\ast }$ 可得 ${\omega }^{\ast }=\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i{x}_i$

• 结论：对于支持向量，有 ${\alpha }_j^{\ast }>0$ ，其余点 ${\alpha }^{\ast }=0$

间隔边界上的点，满足
y ( ω ⋅ x + b ) = 1 y 2 ( ω ⋅ x + b ) = y ⇒ ω ⋅ x + b = y

$$\begin{aligned} &y(\omega\cdot x+b)=1\\ &y^2(\omega\cdot x+b)=y\\ \Rightarrow &\omega\cdot x+b=y \end{aligned}$$ ⇒​y(ω⋅x+b)=1y2(ω⋅x+b)=yω⋅x+b=y​
将 ${\omega }^{\ast }$ 代入支持向量
$$\begin{array}{rl}& {\omega }^{\ast }{x}_j+b^{\ast }=y_j\\ \Rightarrow & b^{\ast }=y_j-{\omega }^{\ast }{x}_j=y_j-\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x_i\cdot x_j)\end{array}$$

3. 求得分离超平面

{ ω ∗ x + b ∗ = 0 分类决策函数 f ( x ) = s i g n ( ω ∗ x + b ) ⇒ { ∑ i = 1 N α i y i x i ⋅ x + ( y j − ∑ i = 1 N α i ∗ y i ( x i ⋅ x j ) ) = 0 f ( x ) = s i g n ( ∑ i = 1 N α i y i x i ⋅ x + y j − ∑ i = 1 N α i ∗ y i ( x i ⋅ x j ) )

$$\begin{cases} \omega^* x+b^*=0\\ 分类决策函数 f(x)=sign(\omega^* x+b) \end{cases}$$ \Rightarrow $$\begin{cases} \sum\limits_{i=1}^N\alpha_iy_ix_i\cdot x+\left(y_j-\sum\limits_{i=1}^N\alpha_i^*y_i(x_i\cdot x_j)\right)=0\\ f(x)=sign\left(\sum\limits_{i=1}^N\alpha_iy_ix_i\cdot x+y_j-\sum\limits_{i=1}^N\alpha_i^*y_i(x_i\cdot x_j)\right) \end{cases}$$ {ω∗x+b∗=0分类决策函数f(x)=sign(ω∗x+b)​⇒⎩ ⎨ ⎧​i=1∑N​αi​yi​xi​⋅x+(yj​−i=1∑N​αi∗​yi​(xi​⋅xj​))=0f(x)=sign(i=1∑N​αi​yi​xi​⋅x+yj​−i=1∑N​αi∗​yi​(xi​⋅xj​))​

优点

• 对偶问题易于求解
• 引入核函数，推广到非线性分类问题

例题

有样本 $+1:x_1=(3,3),x_2=(4,3)$ ，$-1:x_3=(1,1)$

由对偶算法
{ min ⁡ α ( 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i ⋅ x j − ∑ i = 1 N α i ) s . t . α i ≥ 0 ∑ i = 1 N α i y i = 0 , i = 1 , 2 , ⋯   , N

$$\begin{cases} \min\limits_{\alpha}\left(\frac{1}{2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N\alpha_i\alpha_jy_iy_jx_i\cdot x_j-\sum\limits_{i=1}^N\alpha_i\right)\\ s.t.\quad \alpha_i\ge 0\\ \qquad \sum\limits_{i=1}^N\alpha_iy_i=0,i=1,2,\cdots,N \end{cases}$$ ⎩ ⎨ ⎧​αmin​(21​i=1∑N​j=1∑N​αi​αj​yi​yj​xi​⋅xj​−i=1∑N​αi​)s.t.αi​≥0i=1∑N​αi​yi​=0,i=1,2,⋯,N​
代入后有
$$\{\begin{array}{l}\begin{array}{c}\underset{\alpha }{\min }L(\alpha )=\frac{1}{2}(18{\alpha }_1^2+25{\alpha }_2^2+2{\alpha }_3^2+42{\alpha }_1{\alpha }_2-12{\alpha }_1{\alpha }_3-14{\alpha }_2{\alpha }_3)-({\alpha }_1+{\alpha }_2+{\alpha }_3)\end{array}\text{\hspace{1em}(1)}\\ s.t.{\alpha }_1+{\alpha }_2-{\alpha }_3=0\\ {\alpha }_i\ge 0\end{array}$$
将 ${\alpha }_3={\alpha }_1+{\alpha }_2$ 代入 $(1)$
$$S({\alpha }_1,{\alpha }_2)=4{\alpha }_1^2+\frac{13}{2}{\alpha }_2^2+10{\alpha }_1{\alpha }_2-2{\alpha }_1-2{\alpha }_2$$
令 $\frac{\partial S}{\partial {\alpha }_1}=0$ ，$\frac{\partial S}{\partial {\alpha }_2}=0$ 可得 $({\alpha }_1,{\alpha }_2{)}^T=(\frac{3}{2},-1{)}^T$ ，但不满足约束条件

可知最优解在约束边界上
$$\begin{gathered} 若{\alpha }_1=0，令\frac{\partial S}{\partial {\alpha }_2}=0\Rightarrow {\alpha }_2=\frac{2}{13}\Rightarrow S(0,\frac{2}{13})=-\frac{2}{13} \\ {\alpha }_2=0，令\frac{\partial S}{\partial {\alpha }_1}=0\Rightarrow {\alpha }_1=\frac{1}{4}\Rightarrow S(\frac{1}{4},0)=-\frac{1}{4} \end{gathered}$$
$\therefore$ $S({\alpha }_1,{\alpha }_2)$ 在 $(\frac{1}{4},0{)}^T$ 上取最小，${\alpha }_3={\alpha }_1+{\alpha }_2=\frac{1}{4}$

由于 ${\alpha }_1={\alpha }_3=\frac{1}{4}\ne 0$ ，故 $x_1,x_3$ 为支持向量
ω ∗ = α 1 y 1 x 1 + α 3 y 3 x 3 = 1 4 ( 3 3 ) + 1 4 ( − 1 ) ( 1 1 ) = ( 1 2 1 2 ) b ∗ = y 3 − ∑ i = 1 3 α i y i ( x i ⋅ x 3 ) = − 2

$$\begin{aligned} \omega^*&=\alpha_1y_1x_1+\alpha_3y_3x_3\\ &=\frac{1}{4}\left(\begin{aligned} 3\\3 \end{aligned}$$ \right)+\frac{1}{4}(-1)\left( $$\begin{aligned} 1\\1 \end{aligned}$$ \right)=\left( $$\begin{aligned} \frac{1}{2}\\\frac{1}{2} \end{aligned}$$ \right)\\ b^*&=y_3-\sum\limits_{i=1}^3\alpha_iy_i(x_i\cdot x_3)=-2 \end{aligned} ω∗b∗​=α1​y1​x1​+α3​y3​x3​=41​(33​)+41​(−1)(11​)= ​21​21​​ ​=y3​−i=1∑3​αi​yi​(xi​⋅x3​)=−2​
所以有分离超平面 $\frac{1}{2}{x}^{(1)}+\frac{1}{2}{x}^{(2)}-2=0$ ，决策函数 $f(x)=sign(\frac{1}{2}{x}^{(1)}+\frac{1}{2}{x}^{(2)}-2)$