支持向量机

因为用 k k k 对 ( ω , b ) (\omega, b) (ω,b) 进行缩放后，即 ( ω , b ) (\omega, b) (ω,b) 变为 ( k ω , k ω ) (k\omega, k\omega) (kω,kω)，样本 x ( n ) x^{(n)} x(n) 到超平面距离不发生变化，也就是系数的改变对直线并无任何实质影响，所以不管 k k k 是多少，距离 γ ( n ) \gamma^{(n)} γ(n) 都是不会改变的。那么现在对最特殊的，也是最近距离的支持向量 x 0 x_0 x0​，我们要求出其最大距离，因为对于 ∣ ω T x 0 + b ∣ |\omega^Tx_0+b| ∣ωTx0​+b∣ 的缩放也好都不会改变直线的距离，因此我们通过 k k k 的缩放使得恰好满足 ∣ ω T x 0 + b ∣ = 1 |\omega^Tx_0+b| = 1 ∣ωTx0​+b∣=1，这里我们需要注意的是，此时的 ω \omega ω 和 b b b 为缩放调整后的 ω \omega ω 和 b b b，当然你也可以令 ∣ ω T x 0 + b ∣ |\omega^Tx_0+b| ∣ωTx0​+b∣ 这个值为 2 , 3 , 4... 2, 3, 4... 2,3,4... 等等，这都无妨，我们另其为 1 1 1，主要也是为了方便，最终的目的是固定距离计算中的分子，来单独讨论分母对距离的影响。既然要固定变量，就把分子固定住，让分母去最小，就可以得到最大间距了。当我们固定了距离公式中的分子，此时支持向量与平面的距离为：
d = 1 ∥ ω ∥ d=\frac{1}{\|\omega\|} d=∥ω∥1​

支持向量机为了最小化： ∥ ω ∥ \|\omega\| ∥ω∥，目的就是为了最大化支持向量到平面的距离 d d d。

SVM处理线性问题

• 最小化

• min ⁡ ω , b (   1 2 ∥ ω ∥ 2 ) \min\limits_{\omega,b}\left( \ \frac{1}{2}\|\omega\|^2\right) ω,bmin​( 21​∥ω∥2)

• 限制条件s.t.

• y i [ ω T x i + b ] ⩾ 1 y_i\left[\omega^Tx_i+b\right] \geqslant 1 yi​[ωTxi​+b]⩾1（ i = 1 , 2 , . . . , N i=1, 2, ..., N i=1,2,...,N）

SVM处理非线性问题

• 最小化

• min ⁡ ω , b [   1 2 ∥ ω ∥ 2 + C ∑ i = 1 N ξ i ] \min\limits_{\omega,b}\left[ \ \frac{1}{2}\|\omega\|^2+C\sum\limits_{i=1}^N\xi_i\right] ω,bmin​[ 21​∥ω∥2+Ci=1∑N​ξi​]（其中 ξ i \xi_i ξi​ 为松弛变量 s l a c k v a r i a b l e slack variable slackvariable， i = 1 , 2 , . . . , N i=1, 2, ..., N i=1,2,...,N）

• 限制条件s.t.

• y i [ ω T x i + b ] ⩾ 1 − ξ i y_i\left[\omega^Tx_i+b\right] \geqslant 1-\xi_i yi​[ωTxi​+b]⩾1−ξi​（ i = 1 , 2 , . . . , N i=1, 2, ..., N i=1,2,...,N）
• ξ i ⩾ 0 \xi_i \geqslant 0 ξi​⩾0（ i = 1 , 2 , . . . , N i=1, 2, ..., N i=1,2,...,N）

对于非线性优化问题，我们已知的是 X i , y i X_i,y_i Xi​,yi​，要求的是 w , b , ξ i w,b,\xi_i w,b,ξi​

---

对于 x 1 = [ 0 0 ] ∈ C 1 x_1 = \left[\begin{matrix}0\\0 \end{matrix}\right]\in C_1 x1​=[00​]∈C1​， x 1 = [ 1 1 ] ∈ C 1 ， x 1 = [ 1 0 ] ∈ C 2 x_1 = \left[\begin{matrix}1\\1 \end{matrix}\right]\in C_1，x_1 = \left[\begin{matrix}1\\0 \end{matrix}\right]\in C_2 x1​=[11​]∈C1​，x1​=[10​]∈C2​， x 1 = [ 0 1 ] ∈ C 2 x_1 = \left[\begin{matrix}0\\1 \end{matrix}\right]\in C_2 x1​=[01​]∈C2​，我该如何将这四个向量分为两类呢？

首先我们定义这样的函数 φ ( x ) ： x = [ a b ] ⟶ φ ( x ) = [ a 2 b 2 a b a b ] \varphi(x)：x=\left[\begin{matrix}a\\b\end{matrix}\right]\longrightarrow\varphi(x)=\left[\begin{matrix} a^2\\b^2\\a\\b\\ab \end{matrix}\right] φ(x)：x=[ab​]⟶φ(x)=⎣⎢⎢⎢⎢⎡​a2b2abab​⎦⎥⎥⎥⎥⎤​，我们可以看到 φ ( x ) \varphi(x) φ(x) 实际上就是原向量所有元素相互乘积得到的更高维度的向量。

此时我们对 x 1 ， x 2 ， x 3 ， x 4 x_1，x_2，x_3，x_4 x1​，x2​，x3​，x4​拓展维度：
φ ( x 1 ) = [ 0 0 0 0 0 ] ， φ ( x 2 ) = [ 1 1 1 1 1 ] ， φ ( x 3 ) = [ 1 0 1 0 0 ] ， φ ( x 4 ) = [ 0 1 0 1 0 ] \varphi(x_1)=\left[\begin{matrix} 0\\0\\0\\0\\0 \end{matrix}\right]，\varphi(x_2)=\left[\begin{matrix} 1\\1\\1\\1\\1 \end{matrix}\right]，\varphi(x_3)=\left[\begin{matrix} 1\\0\\1\\0\\0 \end{matrix}\right]，\varphi(x_4)=\left[\begin{matrix} 0\\1\\0\\1\\0 \end{matrix}\right] φ(x1​)=⎣⎢⎢⎢⎢⎡​00000​⎦⎥⎥⎥⎥⎤​，φ(x2​)=⎣⎢⎢⎢⎢⎡​11111​⎦⎥⎥⎥⎥⎤​，φ(x3​)=⎣⎢⎢⎢⎢⎡​10100​⎦⎥⎥⎥⎥⎤​，φ(x4​)=⎣⎢⎢⎢⎢⎡​01010​⎦⎥⎥⎥⎥⎤​

我们知道对于SVM处理非线性问题的限制条件为： y i ( ω T x i + b ) ⩾ 1 − ξ i y_i(\omega^Tx_i+b) \geqslant 1-\xi_i yi​(ωTxi​+b)⩾1−ξi​（ i = 1 , 2 , . . . , N i=1, 2, ..., N i=1,2,...,N），此时当 x i x_i xi​ 拓展维度以后即变为： y i [ ω T φ ( x i ) + b ] ⩾ 1 − ξ i y_i\left[\omega^T\varphi(x_i)+b\right] \geqslant 1-\xi_i yi​[ωTφ(xi​)+b]⩾1−ξi​（ i = 1 , 2 , . . . , N i=1, 2, ..., N i=1,2,...,N），需要注意的是 w w w的维度也会拓展，与 φ ( x i ) \varphi(x_i) φ(xi​) 相同。那么为了将 x 1 ， x 2 ， x 3 ， x 4 x_1，x_2，x_3，x_4 x1​，x2​，x3​，x4​ 进行二分类，我们目前的问题是如何寻找一个适合的 w w w 和 b b b 来使得满足SVM的限制条件。这样的 w w w 和 b b b 有很多，我们给出其中一个：
ω = [ − 1 − 1 − 1 − 1 6 ] \omega = \left[\begin{matrix}-1 \\ -1\\ -1\\ -1\\ 6\end{matrix}\right] ω=⎣⎢⎢⎢⎢⎡​−1−1−1−16​⎦⎥⎥⎥⎥⎤​， b = 1 b = 1 b=1，带入到限制条件得到： { ω T φ ( x 1 ) + b = 1 > 0 ω T φ ( x 2 ) + b = 3 > 0 ω T φ ( x 3 ) + b = − 1 < 0 ω T φ ( x 4 ) + b = − 1 < 0 \left\{\begin{array}{lr} \omega^T\varphi(x_1)+b=1>0\\\omega^T\varphi(x_2)+b=3>0 \\ \omega^T\varphi(x_3)+b = -1<0 \\ \omega^T\varphi(x_4) +b=-1<0 \end{array}\right. ⎩⎪⎪⎨⎪⎪⎧​ωTφ(x1​)+b=1>0ωTφ(x2​)+b=3>0ωTφ(x3​)+b=−1<0ωTφ(x4​)+b=−1<0​，我们可以看出 x 1 ， x 2 x1，x2 x1，x2被分到 C 1 C_1 C1​类， x 3 ， x 4 x3，x4 x3，x4被分到 C 2 C_2 C2​类。

「QUESTION」：那么我们如何选取 φ ( x ) \varphi(x) φ(x) 呢？
我们可以不知道无限维映射 φ ( x ) \varphi(x) φ(x) 的显式表达，我们只要知道一个核函数（Kernel Function）
K ( x 1 , x 2 ) = φ ( x 1 ) T φ ( x 2 ) K(x_1, x_2) = \varphi(x_1)^T\varphi(x_2) K(x1​,x2​)=φ(x1​)Tφ(x2​)则 y i [ ω T φ ( x i ) + b ] ⩾ 1 − ξ i y_i\left[\omega^T\varphi(x_i)+b\right] \geqslant 1-\xi_i yi​[ωTφ(xi​)+b]⩾1−ξi​（ i = 1 , 2 , . . . , N i=1, 2, ..., N i=1,2,...,N）这个优化式仍然可解，其中 φ ( x 1 ) \varphi(x_1) φ(x1​) 和 φ ( x 2 ) \varphi(x_2) φ(x2​) 均为无限维向量。这同样给我们带来了一个新的问题，我们该如何将 φ ( x i ) \varphi(x_i) φ(xi​) 替换成核函数 K ( x 1 , x 2 ) K(x_1, x_2) K(x1​,x2​) 呢？我们先来看看常见的几种核函数，再了解满足核函数拆分的充要条件（Mercer’s Theorem）。

常见的几种核函数

• 线性核： K ( x 1 , x 2 ) = x 1 T x 2 K(x_1,x_2)=x_1^Tx_2 K(x1​,x2​)=x1T​x2​。
• 高斯核： K ( x 1 , x 2 ) = e − ∣ ∣ x 1 − x 2 ∣ ∣ 2 2 σ 2 = φ ( x 1 ) T φ ( x 2 ) K(x_1, x_2) = e^{-\frac{||x_1-x_2||^2}{2\sigma^2}} = \varphi(x_1)^T\varphi(x_2) K(x1​,x2​)=e−2σ2∣∣x1​−x2​∣∣2​=φ(x1​)Tφ(x2​)，可拆成两个无限维度的 φ ( x ) \varphi(x) φ(x)，但必须满足某种条件，可自己尝试（泰勒展开）。
• 多项式核： K ( x 1 , x 2 ) = ( x 1 T x 2 + 1 ) d = φ ( x 1 ) T φ ( x 2 ) K(x_1, x_2) = (x_1^Tx_2+1)^d = \varphi(x_1)^T\varphi(x_2) K(x1​,x2​)=(x1T​x2​+1)d=φ(x1​)Tφ(x2​)，其中 d d d 为多项式的阶数，可拆成两个有限维度的 φ ( x ) \varphi(x) φ(x)，同样需满足某种条件，可自己尝试看 φ ( x i ) \varphi(x_i) φ(xi​) 的维度和 d d d 维度的关系。
• Sigmoid核： K ( x 1 , x 2 ) = t a n h ( β 1 x 1 T x 2 + β 2 ) K(x_1, x_2) = tanh(\beta_1x_1^Tx_2 + \beta_2) K(x1​,x2​)=tanh(β1​x1T​x2​+β2​)。

Mercer’s Theorem

上面提到 K ( x 1 , x 2 ) K(x_1, x_2) K(x1​,x2​) 拆成 φ ( x 1 ) T φ ( x 2 ) \varphi(x_1)^T\varphi(x_2) φ(x1​)Tφ(x2​) 需满足某种条件（泛函分析），那 K ( x 1 , x 2 ) = φ ( x 1 ) T φ ( x 2 ) K(x_1, x_2) = \varphi(x_1)^T\varphi(x_2) K(x1​,x2​)=φ(x1​)Tφ(x2​) 的充要条件为：

1. K ( x 1 , x 2 ) = K ( x 2 , x 1 ) K(x_1, x_2) = K(x_2, x_1) K(x1​,x2​)=K(x2​,x1​)（交换性）
2. ∀ c i , x i ( i = 1 , 2 , 3 , . . . , N ) \forall c_i, x_i (i=1, 2, 3, ..., N) ∀ci​,xi​(i=1,2,3,...,N)，有： ∑ i = 1 N ∑ j = 1 N c i c j K ( x i , x j ) ⩾ 0 \sum\limits_{i=1}^N\sum\limits_{j=1}^Nc_ic_jK(x_i, x_j) \geqslant 0 i=1∑N​j=1∑N​ci​cj​K(xi​,xj​)⩾0，其中 c i c_i ci​ 为常数， x i x_i xi​ 为向量（半正定性）

---

补充知识：优化理论

原问题（Prime Problem）（非常普适）

• 最小化：

• min ⁡ f ( ω ) \min f(\omega) minf(ω)

• 限制条件s.t.：

• g i ( ω ) ⩽ 0 ( i = 1 , 2 , 3 , . . . , K ) g_i(\omega) \leqslant 0 (i=1,2,3,...,K) gi​(ω)⩽0(i=1,2,3,...,K)
• h i ( ω ) = 0 （ i = 1 , 2 , 3 , . . . , M ） h_i(\omega) = 0（i=1,2,3,...,M） hi​(ω)=0（i=1,2,3,...,M）

对偶问题（Dual Problem）

• 定义： L ( ω , α , β ) = f ( ω ) + ∑ i = 1 K α i g i ( ω ) + ∑ i = 1 M β i h i ( ω ) = f ( ω ) + α T g ( ω ) + β T h ( ω ) L(\omega, \alpha, \beta) = f(\omega)+\sum\limits_{i=1}^K\alpha_ig_i(\omega)+\sum\limits_{i=1}^M\beta_ih_i(\omega)=f(\omega)+\alpha^Tg(\omega)+\beta^Th(\omega) L(ω,α,β)=f(ω)+i=1∑K​αi​gi​(ω)+i=1∑M​βi​hi​(ω)=f(ω)+αTg(ω)+βTh(ω)
  其中 α \alpha α 是一个 K K K 维向量，与 g i ( ω ) ⩽ 0 g_i(\omega) \leqslant 0 gi​(ω)⩽0 的多项式个数相同； β \beta β 是一个 M M M 维向量，与 h i ( ω ) = 0 h_i(\omega) = 0 hi​(ω)=0 的多项式个数相同。式子最右侧 g ( ω ) = [ g 1 ( ω ) g 2 ( ω ) . . . g K ( ω ) ] g(\omega) = \left[\begin{matrix}g_1(\omega) \\ g_2(\omega) \\...\\g_K(\omega)\end{matrix}\right] g(ω)=⎣⎢⎢⎡​g1​(ω)g2​(ω)...gK​(ω)​⎦⎥⎥⎤​，然后 h ( ω ) = [ h 1 ( ω ) h 2 ( ω ) . . . h M ( ω ) ] h(\omega) = \left[\begin{matrix}h_1(\omega) \\ h_2(\omega) \\...\\h_M(\omega)\end{matrix}\right] h(ω)=⎣⎢⎢⎡​h1​(ω)h2​(ω)...hM​(ω)​⎦⎥⎥⎤​。

对偶问题的定义

• 最大化：

• max ⁡ [ Θ ( α , β ) = inf ⁡ a l l ( ω ) [ L ( ω , α , β ) ] ] \max\left[\Theta(\alpha, \beta) = \inf\limits_{all(\omega)}\left[L(\omega, \alpha, \beta)\right]\right] max[Θ(α,β)=all(ω)inf​[L(ω,α,β)]]，其中 inf ⁡ \inf inf 表示求最小值，在什么情况下求最小值呢？在限定 α \alpha α 和 β \beta β 的前提下，遍历所有 ω \omega ω 后，求得最小的 L ( ω , α , β ) L(\omega, \alpha, \beta) L(ω,α,β)，因此每确认一个 α \alpha α 和 β \beta β 我都能求出一个最小值，在众多最小值中选取最大的 Θ ( α , β ) \Theta(\alpha, \beta) Θ(α,β)。

• 限制条件s.t.： α i ⩾ 0 （ i = 1 , 2 , 3 , . . . , K ） \alpha_i \geqslant 0（i=1,2,3,...,K） αi​⩾0（i=1,2,3,...,K） ，或按照向量的写法 α ⩾ 0 \alpha \geqslant 0 α⩾0，其中 α = [ α 1 α 2 . . α i . . α K ] \alpha = \left[\begin{matrix}\alpha_1 \\ \alpha_2\\ ..\\\alpha_i\\..\\\alpha_K\end{matrix}\right] α=⎣⎢⎢⎢⎢⎢⎢⎡​α1​α2​..αi​..αK​​⎦⎥⎥⎥⎥⎥⎥⎤​

接下来我们需要解决原问题和对偶问题的关系，但了解他们关系之前我们还需要知道一个定理，定理如下。

定理：如果 ω ∗ \omega^* ω∗ 是原问题的解，而 α ∗ ， β ∗ \alpha^*，\beta^* α∗，β∗ 是对偶问题的解，则有：
f ( ω ∗ ) ⩾ Θ ( α ∗ , β ∗ ) f(\omega^*) \geqslant \Theta(\alpha^*, \beta^*) f(ω∗)⩾Θ(α∗,β∗)

证明：
Θ ( α ∗ , β ∗ ) = inf ⁡ a l l ( ω ) [ L ( ω , α ∗ , β ∗ ) ] ⩽ L ( ω ∗ , α ∗ , β ∗ ) = f ( ω ∗ ) + ∑ i = 1 K α i ∗ g i ( ω ∗ ) + ∑ i = 1 M β i ∗ h i ( ω ∗ ) \Theta(\alpha^*, \beta^*) = \inf\limits_{all(\omega)}\left[L(\omega, \alpha^*, \beta^*)\right]\leqslant L(\omega^*, \alpha^*, \beta^*) = f(\omega^*)+\sum\limits_{i=1}^K\alpha_i^*g_i(\omega^*)+\sum\limits_{i=1}^M\beta_i^*h_i(\omega^*) Θ(α∗,β∗)=all(ω)inf​[L(ω,α∗,β∗)]⩽L(ω∗,α∗,β∗)=f(ω∗)+i=1∑K​αi∗​gi​(ω∗)+i=1∑M​βi∗​hi​(ω∗)，其中限制条件为： { g i ( ω ∗ ) ⩽ 0 ( i = 1 , 2 , 3 , . . . , K ) h i ( ω ∗ ) = 0 ( i = 1 , 2 , 3 , . . . , M ) α i ∗ ⩾ 0 \left\{\begin{array}{lr}g_i(\omega^*) \leqslant 0 (i=1,2,3,...,K) \\ h_i(\omega^*) = 0(i=1,2,3,...,M) \\ \alpha_i^* \geqslant 0\end{array}\right. ⎩⎨⎧​gi​(ω∗)⩽0(i=1,2,3,...,K)hi​(ω∗)=0(i=1,2,3,...,M)αi∗​⩾0​，为什么限制条件是这个呢？因为定理说了 ω ∗ \omega^* ω∗ 为原问题的解，因此由原问题的限制条件得到前两个结果，又因为 α i ∗ \alpha_i^* αi∗​ 满足对偶问题的解，因此第三个式子成立，第三个式子为对偶问题的限制条件。因此 ∑ i = 1 K α i ∗ g i ( ω ∗ ) ⩽ 0 \sum\limits_{i=1}^K\alpha_i^*g_i(\omega^*) \leqslant 0 i=1∑K​αi∗​gi​(ω∗)⩽0 并且 ∑ i = 1 M β i ∗ h i ( ω ∗ ) = 0 \sum\limits_{i=1}^M\beta_i^*h_i(\omega^*)=0 i=1∑M​βi∗​hi​(ω∗)=0，我们得出结论： Θ ( α ∗ , β ∗ ) ⩽ f ( ω ∗ ) \Theta(\alpha^*,\beta^*) \leqslant f(\omega^*) Θ(α∗,β∗)⩽f(ω∗)，即证定理。

已知上面的定理和证明后我们有如下这样一个定义。

定义： G = f ( ω ∗ ) − Θ ( a ∗ , b ∗ ) ⩾ 0 G = f(\omega^*) - \Theta(a^*, b^*) \geqslant 0 G=f(ω∗)−Θ(a∗,b∗)⩾0， G G G 叫做原问题与对偶问题的间距 （ D u a l i t y G a p ） （Duality Gap） （DualityGap）。
重要结论：对于某些特定优化问题，可以证明 G = 0 G=0 G=0。具体有哪些特定优化问题呢？我们直接写结论。

强对偶定理

若 f ( ω ) f(\omega) f(ω) 为凸函数，且 g ( ω ) = A ω + b ， h ( ω ) = C ω + d g(\omega) = A\omega + b，h(\omega) = C\omega + d g(ω)=Aω+b，h(ω)=Cω+d，则此优化问题的原问题和对偶问题间距为0，即 f ( ω ∗ ) = Θ ( α ∗ , β ∗ ) f(\omega^*) = \Theta(\alpha^*, \beta^*) f(ω∗)=Θ(α∗,β∗)

若强对偶定理成立，即若 f ( ω ∗ ) = Θ ( α ∗ , β ∗ ) f(\omega^*) = \Theta(\alpha^*, \beta^*) f(ω∗)=Θ(α∗,β∗) 成立，意味着什么呢？有以下两点。
第一点，我们由上面的定理证明得： Θ ( α ∗ , β ∗ ) = inf ⁡ a l l ( ω ) [ L ( ω , α ∗ , β ∗ ) ] ⩽ L ( ω ∗ , α ∗ , β ∗ ) = f ( ω ∗ ) + ∑ i = 1 K α i ∗ g i ( ω ∗ ) + ∑ i = 1 M β i ∗ h i ( ω ∗ ) \Theta(\alpha^*, \beta^*) = \inf\limits_{all(\omega)}\left[L(\omega, \alpha^*, \beta^*)\right]\leqslant L(\omega^*, \alpha^*, \beta^*) = f(\omega^*)+\sum\limits_{i=1}^K\alpha_i^*g_i(\omega^*)+\sum\limits_{i=1}^M\beta_i^*h_i(\omega^*) Θ(α∗,β∗)=all(ω)inf​[L(ω,α∗,β∗)]⩽L(ω∗,α∗,β∗)=f(ω∗)+i=1∑K​αi∗​gi​(ω∗)+i=1∑M​βi∗​hi​(ω∗)
根据强对偶定理和上述证明得到的结论，可以得出 Θ ( α ∗ , β ∗ ) = L ( ω ∗ , α ∗ , β ∗ ) \Theta(\alpha^*, \beta^*) = L(\omega^*, \alpha^*, \beta^*) Θ(α∗,β∗)=L(ω∗,α∗,β∗)，这就意味着确定 α ∗ , β ∗ \alpha^*, \beta^* α∗,β∗ 的情况下，此时让 L L L 取到最小值那个点所对应的是 ω ∗ \omega^* ω∗。
第二点，由上述证明过程和强对偶定理，我们得出： ∑ i = 1 K α i ∗ g i ( ω ∗ ) + ∑ i = 1 M β i ∗ h i ( ω ∗ ) = 0 \sum\limits_{i=1}^K\alpha_i^*g_i(\omega^*)+\sum\limits_{i=1}^M\beta_i^*h_i(\omega^*) = 0 i=1∑K​αi∗​gi​(ω∗)+i=1∑M​βi∗​hi​(ω∗)=0，那么对于 ∀ i = 1 , 2 , . . . , K \forall i = 1,2,...,K ∀i=1,2,...,K，或者 α i ∗ = 0 \alpha_i^* = 0 αi∗​=0，或者 g i ∗ ( ω ∗ ) = 0 g_i^*(\omega^*) = 0 gi∗​(ω∗)=0，那么这个这个条件成为KKT条件。

经上述补充，目的是将拓展维度后的限制条件： y i [ ω T φ ( x i ) + b ] ⩾ 1 − ξ i （ i = 1 , 2 , 3 , . . . , N ） y_i\left[\omega^T\varphi(x_i)+b\right] \geqslant 1-\xi_i（i=1,2,3,...,N） yi​[ωTφ(xi​)+b]⩾1−ξi​（i=1,2,3,...,N）这样的原问题转化为对偶问题，用求解对偶问题的方式来求解原问题的解。接下来我们用原问题、对偶问题来求解SVM，在解决对偶问题时会消除 φ ( x i ) \varphi(x_i) φ(xi​)，只使用 K ( x 1 , x 2 ) K(x_1, x_2) K(x1​,x2​)。

---

什么是凸函数？

现在我们回到SVM处理非线性问题这上面来，因为 1 2 ∣ ∣ ω ∣ ∣ 2 + C ∑ i = 1 N ξ i \frac{1}{2}||\omega||^2+C\sum\limits_{i=1}^N\xi_i 21​∣∣ω∣∣2+Ci=1∑N​ξi​ 是凸函数，此时我们就可以使用强对偶定理，SVM所对应的非线性问题：

• 最小化

• min ⁡ ω , b [   1 2 ∥ ω ∥ 2 + C ∑ i = 1 N ξ i ] \min\limits_{\omega,b}\left[ \ \frac{1}{2}\|\omega\|^2+C\sum\limits_{i=1}^N\xi_i\right] ω,bmin​[ 21​∥ω∥2+Ci=1∑N​ξi​]（其中 ξ i \xi_i ξi​ 为松弛变量 s l a c k v a r i a b l e slack variable slackvariable， i = 1 , 2 , . . . , N i=1, 2, ..., N i=1,2,...,N）

• 限制条件s.t.

• y i [ ω T x i + b ] ⩾ 1 − ξ i y_i\left[\omega^Tx_i+b\right] \geqslant 1-\xi_i yi​[ωTxi​+b]⩾1−ξi​（ i = 1 , 2 , . . . , N i=1, 2, ..., N i=1,2,...,N）
• ξ i ⩾ 0 \xi_i \geqslant 0 ξi​⩾0（ i = 1 , 2 , . . . , N i=1, 2, ..., N i=1,2,...,N）

原问题：

• 最小化： min ⁡ f ( ω ) \min f(\omega) minf(ω)
• 限制条件s.t.：

• g i ( ω ) ⩽ 0 ( i = 1 , 2 , 3 , . . . , K ) g_i(\omega) \leqslant 0 (i=1,2,3,...,K) gi​(ω)⩽0(i=1,2,3,...,K)
• h i ( ω ) = 0 （ i = 1 , 2 , 3 , . . . , M ） h_i(\omega) = 0（i=1,2,3,...,M） hi​(ω)=0（i=1,2,3,...,M）

我们将SVM非线性问题改造为原问题的形式：

• 最小化

• min ⁡ ω , b [   1 2 ∥ ω ∥ 2 − C ∑ i = 1 N ξ i ] \min\limits_{\omega,b}\left[\ \frac{1}{2}\|\omega\|^2-C\sum\limits_{i=1}^N\xi_i\right] ω,bmin​[ 21​∥ω∥2−Ci=1∑N​ξi​]（因为我们要使得限制条件 ξ i ⩽ 0 \xi_i \leqslant 0 ξi​⩽0，因此需将 C C C 前的系数由正变为负）

• 限制条件s.t.

• 1 + ξ i − y i [ ω T x i + b ] ⩽ 0 1+\xi_i-y_i\left[\omega^Tx_i+b\right] \leqslant 0 1+ξi​−yi​[ωTxi​+b]⩽0（ i = 1 , 2 , . . . , K i=1, 2, ..., K i=1,2,...,K）
• ξ i ⩽ 0 \xi_i \leqslant 0 ξi​⩽0（ i = 1 , 2 , . . . , K i=1, 2, ..., K i=1,2,...,K）

转化为对偶问题（我们知道最初原问题为 f ( ω ) f(\omega) f(ω)，当时的待求变量为 ω \omega ω，SVM非线性问题的原问题转换为对偶问题以后，我们的待求变量为 ω , ξ i , b \omega, \xi_i, b ω,ξi​,b）：

• 最大化：

• Θ ( α , β ) = inf ⁡ a l l ( ω , ξ i , β ) [ 1 2 ∥ ω ∥ 2 − C ∑ i = 1 N ξ i + ∑ i = 1 N β i ξ i + ∑ i = 1 N α i [ 1 + ξ i − y i ω T φ ( x i ) − y i b ] ] \Theta(\alpha, \beta) = \inf\limits_{all(\omega,\xi_i,\beta)}\left[\frac{1}{2}\|\omega\|^2-C\sum\limits_{i=1}^N\xi_i+\sum\limits_{i=1}^N\beta_i\xi_i+\sum\limits_{i=1}^N\alpha_i\left[1+\xi_i-y_i\omega^T\varphi(x_i)-y_ib\right]\right] Θ(α,β)=all(ω,ξi​,β)inf​[21​∥ω∥2−Ci=1∑N​ξi​+i=1∑N​βi​ξi​+i=1∑N​αi​[1+ξi​−yi​ωTφ(xi​)−yi​b]]

• 限制条件s.t.：

• { α i ⩾ 0 β i ⩾ 0 i = 1 , 2 , . . , N \left\{\begin{array}{lr} \alpha_i \geqslant 0 \\ \beta_i \geqslant 0 \\ i=1,2,..,N \end{array}\right. ⎩⎨⎧​αi​⩾0βi​⩾0i=1,2,..,N​

注意：需注意的是我们将对偶问题 f ( ω ) + ∑ i = 1 K α i g i ( ω ) + ∑ i = 1 M β i h i ( ω ) f(\omega)+\sum\limits_{i=1}^K\alpha_ig_i(\omega)+\sum\limits_{i=1}^M\beta_ih_i(\omega) f(ω)+i=1∑K​αi​gi​(ω)+i=1∑M​βi​hi​(ω)，转为适用于SVM非线性问题的对偶问题 1 2 ∥ ω ∥ 2 − C ∑ i = 1 N ξ i + ∑ i = 1 N β i ξ i + ∑ i = 1 N α i [ 1 + ξ i − y i ω T φ ( x i ) − y i b ] \frac{1}{2}\|\omega\|^2-C\sum\limits_{i=1}^N\xi_i+\sum\limits_{i=1}^N\beta_i\xi_i+\sum\limits_{i=1}^N\alpha_i\left[1+\xi_i-y_i\omega^T\varphi(x_i)-y_ib\right] 21​∥ω∥2−Ci=1∑N​ξi​+i=1∑N​βi​ξi​+i=1∑N​αi​[1+ξi​−yi​ωTφ(xi​)−yi​b] 后，因对于对偶问题，限制条件 g i ( ω ) ⩽ 0 g_i(\omega) \leqslant 0 gi​(ω)⩽0 这一个条件在SVM非线性下对偶问题中有两个限制条件 { 1 + ξ i − y i [ ω T x i + b ] ⩽ 0 ξ i ⩽ 0 \left\{\begin{array}{lr}1+\xi_i-y_i\left[\omega^Tx_i+b\right] \leqslant 0\\ \xi_i \leqslant 0\end{array}\right. {1+ξi​−yi​[ωTxi​+b]⩽0ξi​⩽0​与之对应（都是小于等于），因此对偶问题 f ( ω ) + ∑ i = 1 K α i g i ( ω ) + ∑ i = 1 M β i h i ( ω ) f(\omega)+\sum\limits_{i=1}^K\alpha_ig_i(\omega)+\sum\limits_{i=1}^M\beta_ih_i(\omega) f(ω)+i=1∑K​αi​gi​(ω)+i=1∑M​βi​hi​(ω) 中 ∑ i = 1 K α i g i ( ω ) \sum\limits_{i=1}^K\alpha_ig_i(\omega) i=1∑K​αi​gi​(ω) 这一部分转换为了 ∑ i = 1 N β i ξ i + ∑ i = 1 N α i [ 1 + ξ i − y i ω T φ ( x i ) − y i b ] \sum\limits_{i=1}^N\beta_i\xi_i+\sum\limits_{i=1}^N\alpha_i\left[1+\xi_i-y_i\omega^T\varphi(x_i)-y_ib\right] i=1∑N​βi​ξi​+i=1∑N​αi​[1+ξi​−yi​ωTφ(xi​)−yi​b]，后者的 β i \beta_i βi​ 与前者的 β i \beta_i βi​ 不同，这里容易混淆，后者的 α i , β i \alpha_i, \beta_i αi​,βi​ 均由前者的 α i \alpha_i αi​ 转换而成，这一点一定要注意，很容易混淆，前者所对应的 h i ( ω ) = 0 h_i(\omega)=0 hi​(ω)=0 这个限制条件在SVM非线性的对偶问题中并未出现，并且尽管出现也为0，因此在SVM非线性对偶问题中不会出现前者的那个 β i \beta_i βi​。

OK！到目前为止，我们已经将SVM非线性问题的原问题转化为对偶问题，我们再写一遍：

• 最大化：

• Θ ( α , β ) = inf ⁡ a l l ( ω , ξ i , β ) [ 1 2 ∥ ω ∥ 2 − C ∑ i = 1 N ξ i + ∑ i = 1 N β i ξ i + ∑ i = 1 N α i [ 1 + ξ i − y i ω T φ ( x i ) − y i b ] ] \Theta(\alpha, \beta) = \inf\limits_{all(\omega,\xi_i,\beta)}\left[\frac{1}{2}\|\omega\|^2-C\sum\limits_{i=1}^N\xi_i+\sum\limits_{i=1}^N\beta_i\xi_i+\sum\limits_{i=1}^N\alpha_i\left[1+\xi_i-y_i\omega^T\varphi(x_i)-y_ib\right]\right] Θ(α,β)=all(ω,ξi​,β)inf​[21​∥ω∥2−Ci=1∑N​ξi​+i=1∑N​βi​ξi​+i=1∑N​αi​[1+ξi​−yi​ωTφ(xi​)−yi​b]]

• 限制条件s.t.：

• { α i ⩾ 0 β i ⩾ 0 i = 1 , 2 , . . , N \left\{\begin{array}{lr} \alpha_i \geqslant 0 \\ \beta_i \geqslant 0 \\i=1,2,..,N\end{array}\right. ⎩⎨⎧​αi​⩾0βi​⩾0i=1,2,..,N​

此时 L ( ω , ξ i , b ) = 1 2 ∥ ω ∥ 2 − C ∑ i = 1 N ξ i + ∑ i = 1 N β i ξ i + ∑ i = 1 N α i [ 1 + ξ i − y i ω T φ ( x i ) − y i b ] L(\omega,\xi_i,b) = \frac{1}{2}\|\omega\|^2-C\sum\limits_{i=1}^N\xi_i+\sum\limits_{i=1}^N\beta_i\xi_i+\sum\limits_{i=1}^N\alpha_i\left[1+\xi_i-y_i\omega^T\varphi(x_i)-y_ib\right] L(ω,ξi​,b)=21​∥ω∥2−Ci=1∑N​ξi​+i=1∑N​βi​ξi​+i=1∑N​αi​[1+ξi​−yi​ωTφ(xi​)−yi​b]，我们要找一个 ω , ξ i , b \omega,\xi_i,b ω,ξi​,b，使得 L ( ω , ξ i , b ) L(\omega,\xi_i,b) L(ω,ξi​,b) 最小，接下来我们分别对 L L L 关于 ω , ξ i , b \omega,\xi_i,b ω,ξi​,b 求偏导数，这里涉及到对向量的偏导数，那么实际上对向量求偏导数就是对向量的每个元素求偏导数，即就是： ∂ f ∂ ω = [ ∂ f ∂ ω 1 ∂ f ∂ ω 2 . . ∂ f ∂ ω n ] \frac{\partial f}{\partial\omega} = \left[\begin{matrix}\frac{\partial f}{\partial\omega_1} \\ \frac{\partial f}{\partial\omega_2} \\ .. \\ \frac{\partial f}{\partial\omega_n}\end{matrix}\right] ∂ω∂f​=⎣⎢⎢⎢⎡​∂ω1​∂f​∂ω2​∂f​..∂ωn​∂f​​⎦⎥⎥⎥⎤​，接下来我们对 L ( ω , ξ i , b ) = 1 2 ∥ ω ∥ 2 − C ∑ i = 1 N ξ i + ∑ i = 1 N β i ξ i + ∑ i = 1 N α i [ 1 + ξ i − y i ω T φ ( x i ) − y i b ] L(\omega,\xi_i,b) = \frac{1}{2}\|\omega\|^2-C\sum\limits_{i=1}^N\xi_i+\sum\limits_{i=1}^N\beta_i\xi_i+\sum\limits_{i=1}^N\alpha_i\left[1+\xi_i-y_i\omega^T\varphi(x_i)-y_ib\right] L(ω,ξi​,b)=21​∥ω∥2−Ci=1∑N​ξi​+i=1∑N​βi​ξi​+i=1∑N​αi​[1+ξi​−yi​ωTφ(xi​)−yi​b] 分别关于 ω , ξ i , b \omega,\xi_i,b ω,ξi​,b 求偏导。

我们给出如下两个结论（这两个结论可自行推导）
（1）若 f ( ω ) = 1 2 ∥ ω ∥ 2 f(\omega) = \frac{1}{2}\|\omega\|^2 f(ω)=21​∥ω∥2，则 ∂ f ∂ ω = ω \frac{\partial f}{\partial \omega} = \omega ∂ω∂f​=ω
（2）若 f ( ω ) = ω T x f(\omega) = \omega^Tx f(ω)=ωTx，则 ∂ f ∂ ω = x \frac{\partial f}{\partial \omega} = x ∂ω∂f​=x

∂ L ∂ ω = 0 ⇒ ω − ∑ i = 1 N α i y i φ ( x i ) = 0 ⇒ ω = ∑ i = 1 N α i y i φ ( x i ) \frac{\partial L}{\partial \omega} = 0 \Rightarrow \omega - \sum\limits_{i=1}^N \alpha_iy_i\varphi(x_i) = 0 \Rightarrow \omega = \sum\limits_{i=1}^N \alpha_iy_i\varphi(x_i) ∂ω∂L​=0⇒ω−i=1∑N​αi​yi​φ(xi​)=0⇒ω=i=1∑N​αi​yi​φ(xi​)

∂ L ∂ ξ i = 0 ⇒ − C + β i + α i = 0 ⇒ β i + α i = C \frac{\partial L}{\partial \xi_i} = 0 \Rightarrow -C + \beta_i + \alpha_i = 0 \Rightarrow \beta_i + \alpha_i = C ∂ξi​∂L​=0⇒−C+βi​+αi​=0⇒βi​+αi​=C

∂ L ∂ b = 0 ⇒ ∑ i = 1 N α i y i = 0 \frac{\partial L}{\partial b} = 0 \Rightarrow \sum\limits_{i=1}^N\alpha_iy_i=0 ∂b∂L​=0⇒i=1∑N​αi​yi​=0

我们将上述三个式子带入到SVM非线性的对偶问题中可求最小值，首先将 β i + α i = C \beta_i + \alpha_i = C βi​+αi​=C 带入消项，然后由 ∑ i = 1 N α i y i = 0 \sum\limits_{i=1}^N\alpha_iy_i=0 i=1∑N​αi​yi​=0 消项，最终得到下面的等式：
Θ ( α , β ) = inf ⁡ a l l ( ω , ξ i , b ) [ 1 2 ∥ ω ∥ 2 + ∑ i = 1 N α i [ 1 − y i ω T φ ( x i ) ] ] \Theta(\alpha, \beta) = \inf\limits_{all(\omega,\xi_i,b)}\left[\frac{1}{2}\|\omega\|^2+\sum\limits_{i=1}^N\alpha_i \left[ 1-y_i\omega^T\varphi(x_i)\right]\right] Θ(α,β)=all(ω,ξi​,b)inf​[21​∥ω∥2+i=1∑N​αi​[1−yi​ωTφ(xi​)]]

其中 1 2 ∥ ω ∥ 2 = 1 2 ω T ω = 1 2 [ ∑ i = 1 N α i y i φ ( x i ) ] T [ ∑ j = 1 N α j y j φ ( x j ) ] = 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j φ ( x i ) T φ ( x j ) \frac{1}{2}\|\omega\|^2 = \frac{1}{2}\omega^T\omega = \frac{1}{2}\left[\sum\limits_{i=1}^N \alpha_iy_i\varphi(x_i)\right]^T \left[\sum\limits_{j=1}^N \alpha_jy_j\varphi(x_j)\right] = \frac{1}{2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N\alpha_i\alpha_jy_iy_j\varphi(x_i)^T\varphi(x_j) 21​∥ω∥2=21​ωTω=21​[i=1∑N​αi​yi​φ(xi​)]T[j=1∑N​αj​yj​φ(xj​)]=21​i=1∑N​j=1∑N​αi​αj​yi​yj​φ(xi​)Tφ(xj​)，此时两部分单独运算，因此我们将两部分用 i , j i,j i,j 区分开，由前面的知识我们知道， y i , y j y_i,y_j yi​,yj​ 只能取 ± 1 \pm1 ±1。此时我们可将 φ ( x i ) T φ ( x j ) \varphi(x_i)^T\varphi(x_j) φ(xi​)Tφ(xj​) 转为核函数 K ( x i , x j ) K(x_i, x_j) K(xi​,xj​)。

其中 − ∑ i = 1 N α i y i ω T φ ( x i ) = − ∑ i = 1 N α i y i [ ∑ j = 1 N α j y j φ ( x j ) ] T φ ( x i ) = − ∑ i = 1 N ∑ j = 1 N α i α j y i y j φ ( x j ) T φ ( x i ) -\sum\limits_{i=1}^N\alpha_iy_i\omega^T\varphi(x_i) = -\sum\limits_{i=1}^N\alpha_iy_i\left[\sum\limits_{j=1}^N\alpha_jy_j\varphi(x_j)\right]^T\varphi(x_i)=-\sum\limits_{i=1}^N\sum\limits_{j=1}^N\alpha_i\alpha_jy_iy_j\varphi(x_j)^T\varphi(x_i) −i=1∑N​αi​yi​ωTφ(xi​)=−i=1∑N​αi​yi​[j=1∑N​αj​yj​φ(xj​)]Tφ(xi​)=−i=1∑N​j=1∑N​αi​αj​yi​yj​φ(xj​)Tφ(xi​)，该式也可将 φ ( x j ) T φ ( x i ) \varphi(x_j)^T\varphi(x_i) φ(xj​)Tφ(xi​) 转为核函数 K ( x i , x j ) K(x_i, x_j) K(xi​,xj​)。

最后我们得到以下结果：
Θ ( α , β ) = ∑ i = 1 N α i − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j K ( x i , x j ) \Theta(\alpha,\beta)=\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_jK(x_i, x_j) Θ(α,β)=i=1∑N​αi​−21​i=1∑N​j=1∑N​αi​αj​yi​yj​K(xi​,xj​)

支持向量机结论

• 最大化：

• Θ ( α ) = ∑ i = 1 N α i − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j K ( x i , x j ) \Theta(\alpha)=\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_jK(x_i, x_j) Θ(α)=i=1∑N​αi​−21​i=1∑N​j=1∑N​αi​αj​yi​yj​K(xi​,xj​)

• 限制条件s.t.：

• { 0 ⩽ α i ⩽ C ∑ i = 1 N α i y i = 0 \left\{\begin{array}{lr} 0 \leqslant \alpha_i \leqslant C \\ \sum\limits_{i=1}^N\alpha_iy_i = 0\end{array}\right. ⎩⎨⎧​0⩽αi​⩽Ci=1∑N​αi​yi​=0​

限制条件第一个由 α i + β i = C , α i ⩾ 0 , β i ⩾ 0 \alpha_i+\beta_i = C, \alpha_i \geqslant 0,\beta_i \geqslant 0 αi​+βi​=C,αi​⩾0,βi​⩾0 这三个条件一起得出，之所以这样合并，是因为在整个优化过程中 β \beta β 是不出现的。限制条件第二个是由令 L L L 关于 b b b 求偏导数为零得到的。此时的问题也是凸优化问题。我们已知的是 y i , y j , K ( x i , x j ) y_i,y_j,K(x_i,x_j) yi​,yj​,K(xi​,xj​)，未知的是所有的 α \alpha α。解决此处的凸优化问题所使用的标准算法为：SMO算法。