SVM 的推导

本是古典何须时尚 2022-09-04 12:45 159阅读 0赞

> SVM（Support Vector Machine，支持向量机）是一个线性分类器，是最经典的分类算法，其核心目标就是找到最大间隔超平面。本文记录SVM的推导过程。

### 概述 ###

> SVM就是一个分类器，只是相对于传统的线性分类器，它添加了一个支持向量的概念。

*  考虑一个分类任务

![61c1a101e57489c858c136768e9763c7.gif][]

> 从图片上解释，对于一组数据，SVM在使用直线的同时要求数据点距离这条直线的最小距离最大，也就是说分类器和数据之间要有足够大的“间隔”。这样做的好处是很明显的，越大的“间隔”代表了更大的转圜空间，在得到新的数据之后更容易将其正确分类。
> 
> 而SVM的工作就是求解这个最大间隔，也就是最优化问题。对于线性可分的数据，可以直接套用线性规划的知识进行推导，但如果数据线性不可分，就需要核函数进行数据升维，进行超平面分类。

### 目标函数 ###

> SVM是一个线性分类器，SVM的目标就是找到最大间隔超平面。

*  定义任意的超平面函数为：

w T x + b = 0 \\bf\{w\}^\{T\} \\bf\{x\}+b=0 wTx\+b=0

*  二维空间点 ( x , y ) (x,y) (x,y)到直线 A x + B y + C = 0 Ax+By+C=0 Ax\+By\+C=0的距离为：

∣ A x + B y + C ∣ A 2 + B 2 \\frac\{|A x+B y+C|\}\{\\sqrt\{A^\{2\}+B^\{2\}\}\} A2\+B2∣Ax\+By\+C∣

*  扩展到 k k k维空间后，点 X = ( x 1 , x 2 , … , x k ) X=(x\_1,x\_2,\\dots,x\_k) X=(x1,x2,…,xk)到超平面 w T x + b = 0 w^\{T\} x+b=0 wTx\+b=0距离为：

∣ w T x + b ∣ ∥ w ∥ \\frac\{\\left|\\bf\{w\}^\{T\} \\bf\{x\}+b\\right|\}\{\\|\\bf\{w\}\\|\} ∥w∥∣∣wTx\+b∣∣

*  其中：

∥ w ∥ = w 1 2 + … w n 2 \\|\\bf\{w\}\\|=\\sqrt\{w\_\{1\}^\{2\}+\\ldots w\_\{n\}^\{2\}\} ∥w∥=w12\+…wn2

*  我们希望这个超平面可以区分不同两类数据特征，这个分类决策函数就是：

f ( x ) = sign ⁡ ( w T x + b ) f(x)=\\operatorname\{sign\}\\left(\\bf\{w\}^T\\bf\{x\}+b\\right) f(x)=sign(wTx\+b)

*  我们的数据为$ (\{ \{\\bf\{x\}\}\_i\},\{y\_i\}), i \\in \{ 1,2, \\ldots ,n\},y\_i \\in \{1,-1\} $ ，定义点$(\{ \{\\bf\{x\}\}\_i\},\{y\_i\}) $ 到超平面的函数距离 γ ^ i \\hat\{\\gamma\}\_\{i\} γ^i：

γ ^ i = y i ( w ⋅ x i + b ) \\hat\{\\gamma\}\_\{i\}=y\_\{i\}\\left(\\bf\{w\} \\cdot \\bf\{x\}\_\{i\}+b\\right) γ^i=yi(w⋅xi\+b)

*  而我们的目标是找到可以最大化数据到点几何距离的超平面，将几何距离用 γ i \{\\gamma\}\_\{i\} γi表示，为：

γ i = ∣ w ∥ w ∥ ⋅ x i + b ∥ w ∥ ∣ = ∣ w T x i + b ∣ ∥ w ∥ = y i ( w ⋅ x i + b ) ∥ w ∥ = γ ^ i ∥ w ∥ \\gamma\_\{i\}=|\\frac\{\\bf\{w\}\}\{\\|\\bf\{w\}\\|\} \\cdot \\bf\{x\}\_\{i\}+\\frac\{b\}\{\\|\\bf\{w\}\\|\}|=\\frac\{|\\bf\{w\}^T\\bf\{x\}\_i+b|\}\{\\|\\bf\{w\}\\|\}=\\frac\{y\_\{i\}\\left(\\bf\{w\} \\cdot \\bf\{x\}\_\{i\}+b\\right)\}\{\\|\\bf\{w\}\\|\}=\\frac\{\\hat\{\\gamma\}\_\{i\}\}\{\\|\\bf\{w\}\\|\} γi=∣∥w∥w⋅xi\+∥w∥b∣=∥w∥∣wTxi\+b∣=∥w∥yi(w⋅xi\+b)=∥w∥γ^i

*  因此优化函数为：

KaTeX parse error: Unknown column alignment: \* at position 16: \\begin\{array\}\{\*̲\{20\}\{l\}\} \{\\math…

*  根据已有结论可以将优化函数转化为：

\{% raw %\}  
KaTeX parse error: Unknown column alignment: \* at position 16: \\begin\{array\}\{\*̲\{20\}\{l\}\} \{\\math…  
\{% endraw %\}

*  事实上函数间隔 γ ^ \{\\hat \\gamma \} γ^并不影响最优化问题的解，假设将 w \\bf\{w\} w和 b b b成倍的改变为 a w ， a b a\\bf\{w\}，ab aw，ab，那么函数间隔也会相应变成 a γ ^ a\{\\hat \\gamma \} aγ^，因此为简便，我们取  γ ^ = 1 \{\\hat \\gamma \}=1 γ^=1，因此优化函数为最大化 1 / ∣ ∣ w ∣ ∣ 1/||\\bf\{w\}|| 1/∣∣w∣∣，这等价于最小化 ∣ ∣ w ∣ ∣ ||\\bf\{w\}|| ∣∣w∣∣，考虑到求导方便，我们最小化 1 / 2 ∣ ∣ w ∣ ∣ 2 1/2||\\bf\{w\}||^2 1/2∣∣w∣∣2
 *  优化函数最终为：

\{% raw %\}  
KaTeX parse error: Unknown column alignment: \* at position 16: \\begin\{array\}\{\*̲\{20\}\{l\}\} \{\\math…  
\{% endraw %\}

### 拉格朗日对偶求极值 ###

*  写成拉格朗日优化的格式：

\{% raw %\}  
KaTeX parse error: Unknown column alignment: \* at position 16: \\begin\{array\}\{\*̲\{20\}\{l\}\} \{\\math…  
\{% endraw %\}

*  拉格朗日方程：

\{% raw %\}  
 L ( w , b , α ) = 1 2 ∣ ∣ w ∣ ∣ 2 + ∑ i = 1 n α i ( 1 − y i ( w ⋅ x i + b ) ) L(\{\\bf\{w\}\},b,\{\\bf\{\\alpha \}\}) = \\frac\{1\}\{2\}||\{\\bf\{w\}\}|\{|^2\} + \\sum\\limits\_\{i = 1\}^n \{ \{\\alpha \_i\}(1 - \{y\_i\}\\left( \{ \{\\bf\{w\}\} \\cdot \{ \{\\bf\{x\}\}\_i\} + b\} \\right)\} ) L(w,b,α)=21∣∣w∣∣2\+i=1∑nαi(1−yi(w⋅xi\+b))  
\{% endraw %\}

*  原始问题为凸优化问题，我们按照KKT条件求解该问题的对偶问题，即可根据强对偶条件获得原始问题的解
 *  对偶问题为：

\{% raw %\}  
 m a x α D ( α ) = m a x α min ⁡ w , b L ( w , b , α ) \\mathop \{max\}\\limits\_\{\\bf\{\\alpha \}\} D(\{\\bf\{\\alpha \}\}) = \\mathop \{max\}\\limits\_\{\\bf\{\\alpha \}\} \\mathop \{\\min \}\\limits\_\{ \{\\bf\{w\}\},b\} L(\{\\bf\{w\}\},b,\{\\bf\{\\alpha \}\}) αmaxD(α)=αmaxw,bminL(w,b,α)  
\{% endraw %\}

*  先求最小化极值问题\{% raw %\}  min ⁡ w , b L ( w , b , α ) \\mathop \{\\min \}\\limits\_\{ \{\\bf\{w\}\},b\} L(\{\\bf\{w\}\},b,\{\\bf\{\\alpha \}\}) w,bminL(w,b,α)\{% endraw %\}：

\{% raw %\}  
KaTeX parse error: Unknown column alignment: \* at position 25: …\{\\begin\{array\}\{\*̲\{20\}\{c\}\} \{\\frac…  
\{% endraw %\}

*  解得：

\{% raw %\}  
KaTeX parse error: Unknown column alignment: \* at position 25: …\{\\begin\{array\}\{\*̲\{20\}\{c\}\} \{ \{\\bf\{…  
\{% endraw %\}

*  带入 L ( w , b , α ) L(\{\\bf\{w\}\},b,\{\\bf\{\\alpha \}\}) L(w,b,α)得：

\{% raw %\}  
 L ( w , b , α ) = 1 2 ∥ w ∥ 2 + ∑ i = 1 n α i \[ 1 − y i ( w T x i + b ) \] = 1 2 w T w − w T ∑ i = 1 n α i y i x i − b ∑ i = 1 n α i y i + ∑ i = 1 n α i = 1 2 w T ∑ i = 1 n α i y i x i − w T ′ ∑ i = 1 n α i x i y i − b ∗ 0 + ∑ i = 1 n α i = ∑ i = 1 n α i − 1 2 ( ∑ i = 1 n α i y i x i ) T ∑ i = 1 n α i y i x i = ∑ i = 1 n α i − 1 2 ∑ i , j = 1 n α i α j y i y j x i T x j \\begin\{aligned\} L(\\bf\{w\}, b, \\bf\{\\alpha\}) &=\\frac\{1\}\{2\}\\|\\bf\{w\}\\|^\{2\}+\\sum\_\{i=1\}^\{n\} \\alpha\_\{i\}\\left\[1-y\_\{i\}\\left(\\bf\{w\}^\{T\} x\_\{i\}+b\\right)\\right\] \\\\ &=\\frac\{1\}\{2\} \\bf\{w\}^\{T\} \\bf\{w\}-\\bf\{w\}^\{T\} \\sum\_\{i=1\}^\{n\} \\alpha\_\{i\} y\_\{i\} x\_\{i\}-b \\sum\_\{i=1\}^\{n\} \\alpha\_\{i\} y\_\{i\}+\\sum\_\{i=1\}^\{n\} \\alpha\_\{i\} \\\\ &=\\frac\{1\}\{2\} \\bf\{w\}^\{T\} \\sum\_\{i=1\}^\{n\} \\alpha\_\{i\} y\_\{i\} x\_\{i\}-\\bf\{w\}^\{T^\{\\prime\}\} \\sum\_\{i=1\}^\{n\} \\alpha\_\{i\} x\_\{i\} y\_\{i\}-b \* 0+\\sum\_\{i=1\}^\{n\} \\alpha\_\{i\} \\\\ &=\\sum\_\{i=1\}^\{n\} \\alpha\_\{i\}-\\frac\{1\}\{2\}\\left(\\sum\_\{i=1\}^\{n\} \\alpha\_\{i\} y\_\{i\} x\_\{i\}\\right)^\{T\} \\sum\_\{i=1\}^\{n\} \\alpha\_\{i\} y\_\{i\} x\_\{i\} \\\\ &=\\sum\_\{i=1\}^\{n\} \\alpha\_\{i\}-\\frac\{1\}\{2\} \\sum\_\{i, j=1\}^\{n\} \\alpha\_\{i\} \\alpha\_\{j\} y\_\{i\} y\_\{j\} x\_\{i\}^\{T\} x\_\{j\} \\end\{aligned\} L(w,b,α)=21∥w∥2\+i=1∑nαi\[1−yi(wTxi\+b)\]=21wTw−wTi=1∑nαiyixi−bi=1∑nαiyi\+i=1∑nαi=21wTi=1∑nαiyixi−wT′i=1∑nαixiyi−b∗0\+i=1∑nαi=i=1∑nαi−21(i=1∑nαiyixi)Ti=1∑nαiyixi=i=1∑nαi−21i,j=1∑nαiαjyiyjxiTxj  
\{% endraw %\}

*  此时我们需要解决的优化问题是：

\{% raw %\}  
KaTeX parse error: Unknown column alignment: \* at position 16: \\begin\{array\}\{\*̲\{20\}\{c\}\} \{\\math…  
\{% endraw %\}

*  可以看到通过拉格朗日对偶，我们将原始拉格朗日方程 k + 1 + n k+1+n k\+1\+n个未知数、 n n n个复杂不等式约束条件的优化问题转换为了 n n n个未知数，1个等式约束的问题，当然满足KKT条件是前提
 *  对于这个问题，我们有更高效的优化算法，即序列最小优化（SMO）算法。我们通过这个优化算法能得到 α \\bf\{α\} α，再根据 α \\bf\{α\} α，我们就可以求解出 w \\bf\{w\} w和 b b b，进而求得我们最初的目的：找到超平面，即"决策平面"。

### 参考资料 ###

*  https://www.jianshu.com/p/0f8f9d52abcf
 *  https://www.pianshen.com/article/15821257925/
 *  https://blog.csdn.net/qq\_40778406/article/details/79879434

[61c1a101e57489c858c136768e9763c7.gif]: /images/20220829/0e9ce8a75c764e57998dabf2bbd755dc.png