1 SVM介绍
SVM是一个二类分类器，它的全称是Support Vector Machine，即支持向量机。
SVM的目标是找到一个超平面，使用两类数据离这个超平面越远越好，从而对新的数据分类更准确，即使分类器更加健壮。比如上面的图中，两种分界线都成功划分了所有数据，但是浅颜色的线距离样本很近，距离分界线比较近的样本很容易被误判，相比之下黑色的线就好得多。
它有两个核心思想，一个是对于线性可分数据，SVM通过寻找最大化类别间距离的超平面进行分类；另一个是对于线性不可分数据，SVM就利用核函数将数据映射到高维空间，再找到线性可分的超平面。这个后面再详细说。
2 公式推导
2.1 距离求解
下面需要求解样本点与分界平面之间的距离。这里用到两个概念：投影、向量点乘。
可设分界超平面为 w X + b = 0 wX+b=0 wX+b=0， b b b是偏移量， w ⃗ \vec{w} w 就是平面法向量。
如图， x x x是任意样本点，平面是需要求解的分界面。 x ′ x' x′ 是平面上任意一点， w ⃗ \vec{w} w 是平面法向量。其中 x ′ x ⃗ \vec {x'x} x′x 为 x − x ′ x-x' x−x′。需要求解 x x x 到平面的距离 d d d，也就是 x ′ x ⃗ \vec {x'x} x′x 在 w ⃗ \vec{w} w 方向上的投影。
为了符合线性代数的习惯，向量符号就不使用箭头标识了。
根据向量点乘公式知：
w T ( x − x ′ ) = ∣ ∣ w ∣ ∣ × ∣ ∣ x − x ′ ∣ ∣ × cos < w T , x − x ′ > w^{T}(x-x')=||w||×||x-x'||×\cos<w^T,x-x'> wT(x−x′)=∣∣w∣∣×∣∣x−x′∣∣×cos<wT,x−x′>
则投影为：
∣ ∣ x − x ′ ∣ ∣ cos < w T , x − x ′ > = W T ( x − x ′ ) ∣ ∣ w ∣ ∣ = 1 ∣ ∣ w ∣ ∣ ( w T x + b ) ||x-x'||\cos<w^T,x-x'>=\frac{W^T(x-x')}{||w||}=\frac{1}{||w||}(w^Tx+b) ∣∣x−x′∣∣cos<wT,x−x′>=∣∣w∣∣WT(x−x′)=∣∣w∣∣1(wTx+b)
所以距离公式为：
d = 1 ∣ ∣ w ∣ ∣ ∣ w T x + b ∣ d = \frac{1}{||w||}|w^Tx+b| d=∣∣w∣∣1∣wTx+b∣
为了方便求解，约定 w w w方向朝向正例样本所在方向，正例样本标签 y y y记为1，负例样本标签 y y y记为-1，那么距离公式可记为：
d = 1 ∣ ∣ w ∣ ∣ y ( w T x + b ) d = \frac{1}{||w||}y(w^Tx+b) d=∣∣w∣∣1y(wTx+b)
2.2 目标表示
距离平面的最小间隔，公式表示为：
min x i 1 ∣ ∣ w ∣ ∣ y i ( w T x i + b ) \min_{x_i}{\frac{1}{||w||}y_i(w^Tx_i+b)} minxi∣∣w∣∣1yi(wTxi+b)
目标是最大化所有样本点中距离平面的最小间隔，公式表示为：
max w , b min x i 1 ∣ ∣ w ∣ ∣ y i ( w T x i + b ) = max w , b 1 ∣ ∣ w ∣ ∣ min x i y i ( w T x i + b ) \max_{w,b}{\min_{x_i}{\frac{1}{||w||}y_i(w^Tx_i+b)}}=\max_{w,b}{\frac{1}{||w||}\min_{x_i}{y_i(w^Tx_i+b)}} maxw,bminxi∣∣w∣∣1yi(wTxi+b)=maxw,b∣∣w∣∣1minxiyi(wTxi+b)
随着 w w w和 b b b的任意变化， y i ( w T x i + b ) y_i(w^Tx_i+b) yi(wTxi+b)大小可以随之变化。在同一个最优解情况下，会有多个 w w w和 b b b。于是为了便于求解，约定以下公式作为约束条件：
min x i y i ( w T x i + b ) = 1 ⇒ y i ( w T x i + b ) ≥ 1 ⇒ 1 − y i ( w T x i + b ) ≤ 0 \min_{x_i}{y_i(w^Tx_i+b)}=1 \Rightarrow y_i(w^Tx_i+b)\geq1 \Rightarrow 1-y_i(w^Tx_i+b)\leq0 minxiyi(wTxi+b)=1⇒yi(wTxi+b)≥1⇒1−yi(wTxi+b)≤0
注意这里每个样本点都构成一个约束。因此求解目标转变为在该限制下的 max w , b 1 ∣ ∣ w ∣ ∣ \max_{w,b}{\frac{1}{||w||}} maxw,b∣∣w∣∣1。为了符合习惯，将其转换为求解最小值，则：
max w , b 1 ∣ ∣ w ∣ ∣ \max_{w,b}{\frac{1}{||w||}} maxw,b∣∣w∣∣1= min w , b ∣ ∣ w ∣ ∣ = min x , b 1 2 w T w \min_{w,b}{||w||}=\min_{x,b}{\frac{1}{2}w^Tw} minw,b∣∣w∣∣=minx,b21wTw
这里增加 1 2 \frac{1}{2} 21是为了便于求导，不会影响结果。
此时优化目标使用公式表示为：
{ min x , b 1 2 w T w s . t . 1 − y i ( w T x i + b ) ≤ 0 , i = 1 , 2 , . . . N \left\{ \begin{array}{l} \min_{x,b}{\frac{1}{2}w^Tw} \\ s.t. \ \ 1-y_i(w^Tx_i+b)\leq0,\ \ i=1,2,...N \end{array} \right. {minx,b21wTws.t. 1−yi(wTxi+b)≤0, i=1,2,...N
2.3 求解 w w w
下面就是使用数学原理拉格朗日乘数法、Karush-Kuhn-Tucker (KKT)条件、对偶问题求解上述公式。可以不过于纠结数学原理，如果另有需要，再深入研究。
上述求解目标是有不等式约束下的凸二次优化问题。于是根据拉格朗日乘数法，问题可以转换为：
{ min w , b max α L ( w , b , α ) s . t . α i ≥ 0 \left\{ \begin{array}{l} \min_{w,b}{\max_{\alpha}{L(w,b,\alpha)}} \\ s.t. \ \alpha_{i}\geq0 \end{array} \right. {minw,bmaxαL(w,b,α)s.t. αi≥0
其中拉格朗日函数 L ( w , b , α ) = 1 2 w T w + ∑ i = 1 N α i ( 1 − y i ( w T x i + b ) ) L(w,b,\alpha)=\frac{1}{2}w^{T}w+\sum_{i=1}^{N}{\alpha_{i}(1-y_{i}(w^{T}x_{i}+b))} L(w,b,α)=21wTw+∑i=1Nαi(1−yi(wTxi+b))。
该公式需要满足KKT条件：
{ 1 − y i ( w T x i + b ) ≤ 0 α i ( 1 − y i ( w T x i + b ) ) = 0 α i ≥ 0 \left\{ \begin{array}{l} 1-y_i(w^Tx_i+b)\leq0 \\ \alpha_{i}(1-y_i(w^Tx_i+b))=0 \\ \alpha_{i}\geq0 \end{array} \right. ⎩
⎨
⎧1−yi(wTxi+b)≤0αi(1−yi(wTxi+b))=0αi≥0
L ( w , b , α ) L(w,b,\alpha) L(w,b,α)一定是强对偶问题，上述问题可以转换为：
{ max α min w , b L ( w , b , α ) s . t . α i ≥ 0 \left\{ \begin{array}{l} \max_{\alpha}{\min_{w,b}{L(w,b,\alpha)}} \\ s.t. \ \alpha_{i}\geq0 \end{array} \right. {maxαminw,bL(w,b,α)s.t. αi≥0
那么当前首要任务是求解有约束下的 min x , b L ( w , b , α ) \min_{x,b}{L(w,b,\alpha)} minx,bL(w,b,α)。求解思路是： L ( w , b , α ) L(w,b,\alpha) L(w,b,α)对 w w w和 b b b求偏导，最小值就在偏导为0的点上，那么比较这些点的 L L L值大小，最小的点就是最优解。
则求解下面式子：
{ ∂ L ∂ w = w − ∑ i = 1 N α i y i x i = 0 ∂ L ∂ b = ∑ i = 1 N α i y i = 0 α i ≥ 0 \left\{ \begin{array}{l} \frac{\partial L}{\partial w}=w-\sum_{i=1}^{N}{\alpha_{i}y_{i}x_{i}}=0 \\ \frac{\partial L}{\partial b}=\sum_{i=1}^{N}{\alpha_{i}y_{i}}=0 \\ \alpha_{i}\geq0 \end{array} \right. ⎩
⎨
⎧∂w∂L=w−∑i=1Nαiyixi=0∂b∂L=∑i=1Nαiyi=0αi≥0
可知：
w = ∑ i = 1 N α i y i x i w=\sum_{i=1}^{N}{\alpha_{i}y_{i}x_{i}} w=∑i=1Nαiyixi
将 w w w 带回原式子，则：
L ( w , b , α ) = 1 2 w T w + ∑ i = 1 N α i ( 1 − y i ( w T x i + b ) ) = 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i x j + ∑ i = 1 N α i − ∑ i = 1 N α i y i ( ∑ j = 1 N α j y j x j x i + b ) = 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i x j + ∑ i = 1 N α i − ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i x j − b ∑ i = 1 N α i y i = ∑ i = 1 N α i − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i x j \begin{array}{l} L(w,b,\alpha) \\ =\frac{1}{2}w^{T}w+\sum_{i=1}^{N}{\alpha_{i}(1-y_{i}(w^{T}x_{i}+b))} \\ = \frac{1}{2}{\sum_{i=1}^{N}\sum_{j=1}^{N}{\alpha_{i}\alpha_{j}y_{i}y_{j}x_{i}x_{j}}}+\sum_{i=1}^{N}{\alpha_{i}}-\sum_{i=1}^{N}{\alpha_{i}y_{i}(\sum_{j=1}^{N}{\alpha_{j}y_{j}x_{j}}x_{i}+b)} \\ = \frac{1}{2}{\sum_{i=1}^{N}\sum_{j=1}^{N}{\alpha_{i}\alpha_{j}y_{i}y_{j}x_{i}x_{j}}}+\sum_{i=1}^{N}{\alpha_{i}}-\sum_{i=1}^{N}\sum_{j=1}^{N}{\alpha_{i}\alpha_{j}y_{i}y_{j}x_{i}x_{j}}-b\sum_{i=1}^{N}{\alpha_{i}y_{i}} \\ = \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}x_{j}} \end{array} L(w,b,α)=21wTw+∑i=1Nαi(1−yi(wTxi+b))=21∑i=1N∑j=1Nαiαjyiyjxixj+∑i=1Nαi−∑i=1Nαiyi(∑j=1Nαjyjxjxi+b)=21∑i=1N∑j=1Nαiαjyiyjxixj+∑i=1Nαi−∑i=1N∑j=1Nαiαjyiyjxixj−b∑i=1Nαiyi=∑i=1Nαi−21∑i=1N∑j=1Nαiαjyiyjxixj
下一步又需要求解：
{ max α [ ∑ i = 1 N α i − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i x j ] s . t . ∑ i = 1 N α i y i = 0 , α i ≥ 0 \left\{ \begin{array}{l} \max_{\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}x_{j}}]} \\ s.t. \ \sum_{i=1}^{N}{\alpha_{i}y_{i}}=0,\alpha_{i}\geq0 \end{array} \right. {maxα[∑i=1Nαi−21∑i=1N∑j=1Nαiαjyiyjxixj]s.t. ∑i=1Nαiyi=0,αi≥0
即：
{ 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 = 1 N α i y i = 0 , α i ≥ 0 \left\{ \begin{array}{l} \min_{\alpha}{[\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}{\alpha_{i}\alpha_{j}y_{i}y_{j}x_{i}x_{j}}-\sum_{i=1}^{N}{\alpha_{i}}]} \\ s.t. \ \sum_{i=1}^{N}{\alpha_{i}y_{i}}=0,\alpha_{i}\geq0 \end{array} \right. {minα[21∑i=1N∑j=1Nαiαjyiyjxixj−∑i=1Nαi]s.t. ∑i=1Nαiyi=0,αi≥0
2.4 求解 b b b
支持向量是位于间隔边界上样本点，即 1 − y i ( w T x i + b ) ) = 0 1-y_i(w^Tx_i+b))=0 1−yi(wTxi+b))=0。
对于任意一个支持向量，求可以通过 1 − y i ( w T x i + b ) ) = 0 1-y_i(w^Tx_i+b))=0 1−yi(wTxi+b))=0计算得到 b b b。
如果有多个支持向量，记 S S S为支持向量集合，那么可以求解：
b = 1 ∣ S ∣ ∑ S y i − w T x i b=\frac{1}{|S|}\sum_{S}{y_i-w^Tx_i} b=∣S∣1∑Syi−wTxi。
2.5 求解支持向量（SOM算法）
下面需要基于上面的公式求解每个样本点的 α i \alpha_{i} αi。所有满足 α i ≤ 0 \alpha_{i}\leq0 αi≤0 的样本均为支持向量。
如果使用传统二次规划算法求解，样本量较大时效率较为低下。可以使用序列最小优化算法(Sequential Minimal Optimization, SMO)求解：
初始化
设置所有拉格朗日乘子α的初始值，通常设为零。选择两个变量 α i \alpha_i αi 和 α j \alpha_j αj
- 外层循环：
遍历训练集中的每个样本，检查其是否违反KKT条件。如果发现某个样本不满足KKT条件，则将其作为第一个要优化的变量 α i \alpha_i αi。 - 内层循环：
选择第二个变量 α j \alpha_j αj，目标是最大化 ∣ E 1 − E 2 ∣ |E1 - E2| ∣E1−E2∣，即两者的误差差异。这有助于确保每次迭代都能带来显著的变化。（ E i = w ⊤ x i + b − y i E_i = \mathbf{w}^\top \mathbf{x}_i + b - y_i Ei=w⊤xi+b−yi，是样本预测值与真实值的误差。）
- 外层循环：
优化子问题
固定其他 α \alpha α，仅优化 α i \alpha_i αi 和 α j \alpha_j αj。由于约束 α i y i + α j y j = − ∑ k ≠ i , j α k y k = ζ ( 常数 ) \alpha_i y_i + \alpha_j y_j = -\sum_{k\neq i,j} \alpha_k y_k = \zeta \quad (\text{常数}) αiyi+αjyj=−∑k=i,jαkyk=ζ(常数)，可用 α 1 \alpha_1 α1表示 α 2 \alpha_2 α2，将问题转换为单变量二次函数优化。然后求导找极值点可得：
α j new = α j old + y j ( E i − E j ) η , η = K ( x i , x i ) + K ( x j , x j ) − 2 K ( x i , x j ) \alpha_j^{\text{new}} = \alpha_j^{\text{old}} + \frac{y_j (E_i - E_j)}{\eta}, \quad \eta = K(x_i, x_i) + K(x_j, x_j) - 2K(x_i, x_j) αjnew=αjold+ηyj(Ei−Ej),η=K(xi,xi)+K(xj,xj)−2K(xi,xj)
其中 K ( x i , x j ) = x i ∗ x j K(x_i, x_j)=x_i*x_j K(xi,xj)=xi∗xj，称为线性核。 η = ∥ x i − x j ∥ 2 \eta =\|\mathbf{x}_i - \mathbf{x}_j\|^2 η=∥xi−xj∥2（几何意义：两个样本的欧氏距离平方）。
然后对 α j new \alpha_j^{\text{new}} αjnew 进行剪裁，也就是约束其在可行域内：
α 2 new,clipped = { H if α 2 new > H L if α 2 new < L α 2 new otherwise \alpha_2^{\text{new,clipped}} = \begin{cases} H & \text{if } \alpha_2^{\text{new}} > H \\ L & \text{if } \alpha_2^{\text{new}} < L \\ \alpha_2^{\text{new}} & \text{otherwise} \end{cases} α2new,clipped=⎩ ⎨ ⎧HLα2newif α2new>Hif α2new<Lotherwise其中：
- 若 y i ≠ y j y_i \neq y_j yi=yj，则： L = max ( 0 , α j old − α i old ) , H = + ∞ L = \max(0, \alpha_j^{\text{old}} - \alpha_i^{\text{old}}), \quad H = +\infty L=max(0,αjold−αiold),H=+∞
- 若 y i = y j y_i = y_j yi=yj，则： L = max ( 0 , α i old + α j old − ζ ) , H = + ∞ L = \max(0, \alpha_i^{\text{old}} + \alpha_j^{\text{old}} - \zeta), \quad H = +\infty L=max(0,αiold+αjold−ζ),H=+∞
然后更新 α i \alpha_i αi：
α 1 new = α 1 old + y 1 y 2 ( α 2 old − α 2 new,clipped ) \alpha_1^{\text{new}} = \alpha_1^{\text{old}} + y_1 y_2 (\alpha_2^{\text{old}} - \alpha_2^{\text{new,clipped}}) α1new=α1old+y1y2(α2old−α2new,clipped)。更新阈值 b b b 和误差缓存
- 根据新 α i \alpha_i αi 和 α j \alpha_j αj 计算阈值 b b b。
- 更新所有样本的误差缓存 E i E_i Ei，用于后续变量选择。
收敛判断
重复上述步骤，直到所有 α i \alpha_i αi 满足KKT条件，或达到最大迭代次数。
3 优化
3.1 软间隔
允许部分样本不满足约束，引入松弛变量 ξ i ≥ 0 \xi_i \geq 0 ξi≥0，优化目标变为：
{ min x , b 1 2 w T w + C ∑ i = 1 n ξ i s . t . 1 − y i ( w T x i + b ) ≤ ξ i , ξ i ≥ 0 , i = 1 , 2 , . . . N \left\{ \begin{array}{l} \min_{x,b}{\frac{1}{2}w^Tw}+C\sum_{i=1}^{n}{\xi_i} \\ s.t. \ \ 1-y_i(w^Tx_i+b)\leq\xi_i ,\ \xi_i \geq 0, \ i=1,2,...N \end{array} \right. {minx,b21wTw+C∑i=1nξis.t. 1−yi(wTxi+b)≤ξi, ξi≥0, i=1,2,...N
其中 C C C 是惩罚参数，控制分类错误与间隔的权衡。
3.2 核技巧（Kernel Trick）
当数据线性不可分时，可以通过映射 $\phi(x)$ 将数据投影到高维空间，使其线性可分。
为了避免显式计算高维内积 ϕ ( x i ) ⋅ ϕ ( x j ) \phi(x_i) \cdot \phi(x_j) ϕ(xi)⋅ϕ(xj)，可以直接使用核函数 ( K(x_i, x_j) ) 代替。
常用核函数：
- 线性核： 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 2 σ 2 ) K(x_i, x_j) = \exp\left( -\frac{\|x_i - x_j\|^2}{2\sigma^2} \right) K(xi,xj)=exp(−2σ2∥xi−xj∥2)
2.5的优化目标变为：
{ min α [ 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j K ( x i , x j ) − ∑ i = 1 N α i ] s . t . ∑ i = 1 N α i y i = 0 , α i ≥ 0 \left\{ \begin{array}{l} \min_{\alpha}{[\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}{\alpha_{i}\alpha_{j}y_{i}y_{j}K(x_i, x_j)}-\sum_{i=1}^{N}{\alpha_{i}}]} \\ s.t. \ \sum_{i=1}^{N}{\alpha_{i}y_{i}}=0,\alpha_{i}\geq0 \end{array} \right. {minα[21∑i=1N∑j=1NαiαjyiyjK(xi,xj)−∑i=1Nαi]s.t. ∑i=1Nαiyi=0,αi≥0