支持向量机（support vector machine，SVM）是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别与感知机，此外SVM还包含和技巧，这使它成为实质上的非线性分类器。如果摘要你暂时无法理解也不要担心，最后学完再回头看能明白就好。
一. 概念引入
- 支持向量
刚开始学习SVM的时候经常一头雾水，因为不知道到底什么是support vector，什么是支持向量。所以在开篇先说明什么是支持向量。
支持向量就是距离超平面最近的点，我们要最大化支持向量与超平面之间的间隔来达到尽可能地将两类样本分离。 - 函数间隔和几何间隔
本节将形式化函数间隔及几何间隔。对于给定的训练样本 ( x ( i ) , y ( i ) ) \left(x^{(i)},y^{(i)}\right) (x(i),y(i))，我们定义关于超平面(w,b)此训练样本的函数间隔为：
γ ^ ( i ) = y ( i ) ( w T x ( i ) + b ) \hat{\gamma}^{(i)}=y^{(i)}\left(w^Tx^{(i)}+b\right) γ^(i)=y(i)(wTx(i)+b)
上式可以解释为，当 y ( i ) = 1 y^{(i)}=1 y(i)=1（正类）时，为了得到一个较大的函数间隔（即为了使预测有较高的的可信度及准确性），我们需要 w T x + b w^Tx+b wTx+b取一个较大的正数（ w T x + b ≫ 0 w^Tx+b\gg 0 wTx+b≫0）；反之，当 y ( i ) = − 1 y^{(i)}=-1 y(i)=−1（负类）时，我们需要 w T x + b w^Tx+b wTx+b取一个较大的负数（ w T x + b ≪ 0 w^Tx+b\ll 0 wTx+b≪0）。此外，如果 y ( i ) ( w T x + b ) > 0 y^{(i)}\left(w^Tx+b\right)\gt 0 y(i)(wTx+b)>0，则说明关于此样本的预测是正确的。因此，较大的函数间隔意味着较高的可信度和准确性。
对于给定的训练集 S = { ( x ( i ) , y ( i ) ) ; i = 1 , ⋯ , m } S=\left\{\left(x^{(i)},y^{(i)}\right);i=1,\cdots,m\right\} S={(x(i),y(i));i=1,⋯,m}，关于S以(w,b)为参数的函数间隔 γ ^ \hat\gamma γ^定义为取所以独立的训练样本中最小的那个函数间隔（即取最坏的一个样本的情况）：
γ ^ = min i = 1 , ⋯ , m γ ^ ( i ) \hat\gamma=\min_{i=1,\cdots,m}\hat\gamma^{(i)} γ^=i=1,⋯,mminγ^(i) 这里的函数间隔（functional margin）是定义的，用于后续的模型计算和处理。
函数间隔可以表示分类预测的正确性和确信度，但是选择分离超平面（hyper plane）时，只有函数间隔还不够，因为只要成比例地改变w和b，超平面 w T x ( i ) + b w^Tx^{(i)}+b wTx(i)+b = 0 没有发生改变，依旧是原来那条直线，但是函数间隔的大小却会发生改变。
因此我们考虑对超平面法向量进行约束，即规范化，||w||=1，使得间隔是确定的，同时(w,b)变成了 ( w ∥ w ∥ , b ∥ w ∥ ) \left(\frac{w}{\lVert w\rVert},\frac{b}{\lVert w\rVert}\right) (∥w∥w,∥w∥b)，这时函数间隔成为了几何间隔（geometric margin），考虑下图：
γ ( i ) \gamma^{(i)} γ(i)为训练样本点A到分离超平面 w T x + b = 0 w^Tx+b=0 wTx+b=0的距离，即几何间隔。如何计算 γ ( i ) \gamma^{(i)} γ(i)呢？注意到 w ∥ w ∥ \frac{w}{\lVert w\rVert} ∥w∥w是标准化后的w向量，点A为 x ( i ) x^{(i)} x(i)，则点B为 x ( i ) − γ ( i ) ⋅ w ∥ w ∥ x^{(i)}-\gamma^{(i)}\cdot\frac{w}{\lVert w\rVert} x(i)−γ(i)⋅∥w∥w。点B在判定边界上，而判定边界上的所有点都满足方程 w T x + b = 0 w^Tx+b=0 wTx+b=0，则将B代入超平面方程：
w T ( x ( i ) − γ ( i ) w ∥ w ∥ ) + b = 0 w^T\left(x^{(i)}-\gamma^{(i)}\frac{w}{\lVert w\rVert}\right)+b=0 wT(x(i)−γ(i)∥w∥w)+b=0解得 γ ( i ) = w T x ( i ) + b ∥ w ∥ = ( w ∥ w ∥ ) T x ( i ) + b ∥ w ∥ \gamma^{(i)}=\frac{w^Tx^{(i)}+b}{\lVert w\rVert}=\left(\frac{w}{\lVert w\rVert}\right)^Tx^{(i)}+\frac{b}{\lVert w\rVert} γ(i)=∥w∥wTx(i)+b=(∥w∥w)Tx(i)+∥w∥b
这就是正训练样本A被正确的分在判别边界y=1一侧的情形，加上在y=-1一侧的情形，我们可以将解一般化为 γ ( i ) = y ( i ) ( ( w ∥ w ∥ ) T x ( i ) + b ∥ w ∥ ) \gamma^{(i)}=y^{(i)}\left(\left(\frac{w}{\lVert w\rVert}\right)^Tx^{(i)}+\frac{b}{\lVert w\rVert}\right) γ(i)=y(i)((∥w∥w)Tx(i)+∥w∥b) 同样对于给定的训练集 S = { ( x ( i ) , y ( i ) ) ; i = 1 , ⋯ , m } S=\left\{\left(x^{(i)},y^{(i)}\right);i=1,\cdots,m\right\} S={(x(i),y(i));i=1,⋯,m}，关于S以(w,b)为参数的几何间隔 γ γ γ定义为取所以独立的训练样本中最小的那个几何间隔（即取最坏的一个样本的情况）：
γ = min i = 1 , ⋯ , m γ ( i ) \gamma=\min_{i=1,\cdots,m}\gamma^{(i)} γ=i=1,⋯,mminγ(i) - 最大间隔分类器（maximum margin classifier）
最大间隔分类器是早期的SVM，实际上就是选择特定的w和b使得几何间隔最大化。 - 拉格朗日对偶（Lagrange duality）
这里暂时不需要看，先看 二.模型分类概述，等到需要理解拉格朗日对偶了再回过头看。看这里之前可以先去回顾一下高数曾经学过的拉格朗日乘子法。
传统的QP软件已经可以求解我们所提出的原始优化问题，那为什么还要使用拉格朗日对偶呢？一是对偶问题更容易求解，二是自然引入核函数，从而推广到我们的第三个模型——非线性分类模型。
我们先放下SVM，考虑一下带有约束的原始优化问题（primal optimization problem）如下：
min w f ( w ) s . t . g i ( w ) ≤ 0 , i = 1 , ⋯ , k h i ( w ) = 0 , i = 1 , ⋯ , l \begin{aligned}&\min_{w}\quad f(w)\\&\mathrm{s.t.}\quad g_i(w)\leq 0,\quad i=1,\cdots ,k\\&\quad\quad h_i(w)=0,\quad i=1,\cdots,l\end{aligned} wminf(w)s.t.gi(w)≤0,i=1,⋯,khi(w)=0,i=1,⋯,l定义广义拉格朗日算子（generalized Lagrangian）：
L ( w , α , β ) = f ( w ) + ∑ i = 1 k α i g i ( w ) + ∑ i = 1 l β i h i ( w ) \mathcal{L}(w,\alpha,\beta)=f(w)+\sum_{i=1}^k\alpha_ig_i(w)+\sum_{i=1}^l\beta_ih_i(w) L(w,α,β)=f(w)+i=1∑kαigi(w)+i=1∑lβihi(w)这里的α,β是拉格朗日乘数，考虑下面的量：
θ P ( w ) = max α , β : α i ≥ 0 L ( w , α , β ) \theta_{\mathcal{P}}(w)=\max_{\alpha,\beta:\alpha_i\geq 0}\mathcal{L}(w,\alpha,\beta) θP(w)=α,β:αi≥0maxL(w,α,β)如果w违反了限制条件（如 g i ( w ) > 0 g_i(w)\gt 0 gi(w)>0或 h i ( w ) ≠ 0 h_i(w)\neq 0 hi(w)=0），则易得 θ P ( w ) = ∞ \theta_{\mathcal{P}}(w)=\infty θP(w)=∞。（如果某个 g i ( w ) > 0 g_i(w)\gt 0 gi(w)>0，则拉格朗日算子中该项相应的拉格朗日乘数 α i \alpha_i αi只需取无穷大就可以使整个式子最大化；类似的，如果某个 h i ( w ) ≠ 0 h_i(w)\neq 0 hi(w)=0，则拉格朗日算子中该项相应的拉格朗日乘数 β i \beta_i βi只需取无穷大也可以使整个式子最大化。），即：
θ P = { f ( w ) if w satisfies primal constraints ∞ otherwise \theta_{\mathcal{P}}=\begin{cases}f(w)&\textrm{if }w\textrm{ satisfies primal constraints}\\\infty&\textrm{otherwise}\end{cases} θP={f(w)∞if w satisfies primal constraintsotherwise因此当w满足原始条件限制时， min w θ P ( w ) = min w max α , β : α i ≥ 0 L ( w , α , β ) \min_{w}\theta_{\mathcal{P}}(w)=\min_{w}\max_{\alpha,\beta:\alpha_i\geq 0}\mathcal{L}(w,\alpha,\beta) wminθP(w)=wminα,β:αi≥0maxL(w,α,β)就等价于原始优化问题。 为了后面使用方便，我们定义优化目标的最优值为 p ∗ = min w θ P ( w ) p^*=\min_{w}\theta_{\mathcal{P}}(w) p∗=minwθP(w)，称为原始问题的最优值（optimal value）。
现在，我们来看一个略微不同的问题，定义关于拉格朗日乘数的函数： θ D ( α , β ) = min w L ( w , α , β ) \theta_{\mathcal{D}}(\alpha,\beta)=\min_{w}\mathcal{L}(w,\alpha,\beta) θD(α,β)=wminL(w,α,β) 引入对偶优化问题（dual optimization problem）：
max α , β : α i ≥ 0 θ D ( α , β ) = max α , β : α i ≥ 0 min w L ( w , α , β ) \max_{\alpha,\beta:\alpha_i\geq 0}\theta_{\mathcal{D}}(\alpha,\beta)=\max_{\alpha,\beta:\alpha_i\geq 0}\min_{w}\mathcal{L}(w,\alpha,\beta) α,β:αi≥0maxθD(α,β)=α,β:αi≥0maxwminL(w,α,β)
这个式子除了“max”和“min”的顺序发生改变以外，其余的同前面的原始问题一样。同样的，定义对偶优化问题的最优值为 d ∗ = max α , β : α i ≥ 0 θ D ( α , β ) d^*=\max_{\alpha,\beta:\alpha_i\geq 0}\theta_{\mathcal{D}}(\alpha,\beta) d∗=α,β:αi≥0maxθD(α,β) 原始问题与对偶问题的关系可以用下面的式子简单表示： d ∗ = max α , β : α i ≥ 0 min w L ( w , α , β ) ≤ p ∗ = min w max α , β : α i ≥ 0 L ( w , α , β ) d^*=\max_{\alpha,\beta:\alpha_i\geq 0}\min_{w}\mathcal{L}(w,\alpha,\beta)\leq p^*=\min_{w}\max_{\alpha,\beta:\alpha_i\geq 0}\mathcal{L}(w,\alpha,\beta) d∗=α,β:αi≥0maxwminL(w,α,β)≤p∗=wminα,β:αi≥0maxL(w,α,β) 在某些特定情况下，能够得到 d ∗ = p ∗ d^*=p^* d∗=p∗，也就是说，我们可以通过解对偶优化问题来得到原始优化问题的最优值（这么做的原因是，对偶问题通常更加简单，而且与原始问题相比，对偶问题具有更多有用的性质，稍后我们会在最优间隔分类器即支持向量机问题中见到），接下来看在什么情况下等式成立，下面将以定理的形式叙述有关的重要结论而不予以证明。
考虑原始优化问题和对偶优化问题，如果满足以下条件（这里记作条件C1）： f f f和 g i g_i gi是凸函数（对于 f f f的Hessian矩阵，当且仅当其为半正定时， f f f是凸函数）， h i h_i hi是仿射函数，并且 g i g_i gi是严格执行的（对于所有 i i i存在 w w w能够使得 g i ( w ) < 0 g_i(w)\lt 0 gi(w)<0），则能够得到以下结论： w ∗ , α ∗ , β ∗ w^*,\alpha^*,\beta^* w∗,α∗,β∗一定存在（ w ∗ w^* w∗是原始优化问题的解， α ∗ , β ∗ \alpha^*,\beta^* α∗,β∗是对偶优化问题的解），且 p ∗ = d ∗ = L ( w ∗ , α ∗ , β ∗ ) p^*=d^*=\mathcal{L}(w^*,\alpha^*,\beta^*) p∗=d∗=L(w∗,α∗,β∗)，且 w ∗ , α ∗ , β ∗ w^*,\alpha^*,\beta^* w∗,α∗,β∗满足KKT条件（Karush-Kuhn-Tucker conditions）：
∂ ∂ w i L ( w ∗ , α ∗ , β ∗ ) = 0 , i = 1 , ⋯ , n ∂ ∂ β i L ( w ∗ , α ∗ , β ∗ ) = 0 , i = 1 , ⋯ , l α i ∗ g i ( w ∗ ) = 0 , i = 1 , ⋯ , k g i ( w ∗ ) ≤ 0 , i = 1 , ⋯ , k α i ∗ ≥ 0 , i = 1 , ⋯ , k \begin{aligned}\frac{\partial}{\partial w_i}\mathcal{L}(w^*,\alpha^*,\beta^*)&=0,\quad i=1,\cdots,n\\\frac{\partial}{\partial \beta_i}\mathcal{L}(w^*,\alpha^*,\beta^*)&=0,\quad i=1,\cdots,l\\\alpha_i^*g_i(w^*)&=0,\quad i=1,\cdots,k\\g_i(w^*)&\leq0,\quad i=1,\cdots,k\\\alpha_i^*&\geq0,\quad i=1,\cdots,k\end{aligned} ∂wi∂L(w∗,α∗,β∗)∂βi∂L(w∗,α∗,β∗)αi∗gi(w∗)gi(w∗)αi∗=0,i=1,⋯,n=0,i=1,⋯,l=0,i=1,⋯,k≤0,i=1,⋯,k≥0,i=1,⋯,k如果存在满足KKT条件的w∗,α∗,β∗，则原始问题与对偶问题一定有解。 α i ∗ g i ( w ∗ ) = 0 \alpha_i^*g_i(w^*)=0 αi∗gi(w∗)=0又被称为KKT对偶互补条件（KKT dual complementarity condition），这个条件表明如果 a i > 0 a_i>0 ai>0则 g i ( w ∗ ) = 0 g_i(w^∗)=0 gi(w∗)=0，满足 a i > 0 a_i>0 ai>0的点即为支持向量，二.1中将证明。 - 核方法和核函数
（先看到二.3再回头看这里）对于一个二分类问题，有一个理想的数据集，假设它是线性可分的，这时直接应用SVM算法即可进行分类，但如果现在的数据集不是线性可分的，如下图：
该数据集在二维空间中，每个数据点都可用一个二维向量 （ x 1 , x 2 ） （x_1,x_2） （x1,x2）表示，我们可以用一个椭圆形状的超平面在该2维空间中对数据集进行分类，我们写出椭圆的一般方程：
如果我们令：
其中：
你会发现，2维向量x被映射成另一个5维向量z后，分类超平面是一个线性超平面，数据点变得线性可分，也就是下面的变换：
也就是说如果我们想完成非线性分类，就需要把数据集映射到高维空间中实现数据集的线性可分。好像问题就这样解决了，但实际上并非如此。只是想实现该问题中二维数据的线性可分就映射到了五维空间，如果数据本身的维度就很高，那映射后的空间维度会更高，甚至是无限维。所以，我们应该找一个合适的二元函数，它的输入是原空间的两个向量，它的输出是映射到高维空间的两个向量的内积，也就是核函数。为什么输出是映射到高维空间的两个向量的内积呢？考虑SVM的原始优化问题：
min w , b 1 2 ∥ w ∥ 2 s . t . y ( i ) ( w T x ( i ) + b ) ≥ 1 , i = 1 , ⋯ , m \begin{aligned}&\min_{w,b}\quad\frac{1}{2}\lVert w\rVert^2\\&\mathrm{s.t.}\quad y^{(i)}\left(w^Tx^{(i)}+b\right)\geq 1,\quad i=1,\cdots,m\end{aligned} w,bmin21∥w∥2s.t.y(i)(wTx(i)+b)≥1,i=1,⋯,m
经过映射后变成： min w , b 1 2 ∥ w ∥ 2 s . t . y ( i ) ( w T ϕ ( x ( i ) ) + b ) ≥ 1 , i = 1 , ⋯ , m \begin{aligned}&\min_{w,b}\quad\frac{1}{2}\lVert w\rVert^2\\&\mathrm{s.t.}\quad y^{(i)}\left(w^T\phi(x^{(i)})+b\right)\geq 1,\quad i=1,\cdots,m\end{aligned} w,bmin21∥w∥2s.t.y(i)(wTϕ(x(i))+b)≥1,i=1,⋯,m原空间内的判定值为 w T x + b = ∑ i = 1 m α i y ( i ) ⟨ x ( i ) , x ⟩ + b \begin{aligned}w^Tx+b=\sum_{i=1}^m\alpha_iy^{(i)}\left\langle x^{(i)},x\right\rangle+b\end{aligned} wTx+b=i=1∑mαiy(i)⟨x(i),x⟩+b映射后的判定值为 w T x + b = ∑ i = 1 m α i y ( i ) ⟨ ϕ ( x ( i ) ) , ϕ ( x ) ⟩ + b \begin{aligned}w^Tx+b=\sum_{i=1}^m\alpha_iy^{(i)}\left\langle \phi(x^{(i)}),\phi(x)\right\rangle+b\end{aligned} wTx+b=i=1∑mαiy(i)⟨ϕ(x(i)),ϕ(x)⟩+b
因此我们需要的是映射到高维空间的两个向量的内积。这样，我们就避免了求映射函数，只通过一个核函数就可以在低维空间完成高维空间中才能完成的事。我当时学到这里的时候有一个疑问，为什么核函数的值就会是映射后向量内积的值呢？这里我们研究一下。
先考虑一个简单的例子，现在有两个二维空间的数据点 x = ( x 1 , x 2 ) , y = ( y 1 , y 2 ) x=(x_1,x_2),y=(y_1,y_2) x=(x1,x2),y=(y1,y2)，考虑二次函数 f ( x , y ) = ( x ⋅ y ) 2 f(x,y)=(x·y)^2 f(x,y)=(x⋅y)2，将 x , y x,y x,y代入该二次函数：
我们可以发现最后的函数值竟然等于两个向量p和q的内积，而且两个向量分别是二维空间数据点 x x x和 y y y在三维空间中的映射，想到刚才定义的核函数，我们很容易想到， f ( x , y ) f(x,y) f(x,y)就是一个核函数。它给出了一个二维的表达式，使得 x , y x,y x,y代入即可求值，而不再需要先把 x , y x,y x,y映射成3维空间中的向量p,q，再求内积。
这也正是我们定义核函数的目的，即虽然没有显式地给出原空间中向量的映射函数，但却达到了可以在原空间中计算映射后的向量内积的目的。
那么我们应该怎么构造一个这样的核函数呢？有几个经典的核函数可供选用，如：多项式核函数，高斯核函数等。当然你也可以自己构造核函数，但也不是任意一个函数就可以当做核函数的，需要满足Mercer条件。
那么我们怎么知道我们构造的核函数一定能使数据在高维空间中线性可分呢？事实上，如果我们选择上面提到的常用的核函数，选择合适的参数，就能使得原空间中的数据点在高维空间中变得线性可分。常用的核函数把原空间的数据映射到了高维空间中，使得数据变得“更容易”线性可分，考虑下图所示的例子：
二维空间中的点只能用非线性的超平面才能分开，但把数据映射到高维空间中，就可以用一个线性的平面给分开了。空间的维度越高，数据越容易线性可分。
核函数不只应用在SVM中，只要有类似需求的地方都可以考虑使用核技巧。
\quad
二. 模型分类概述
在学习SVM的过程中，我将由简至繁逐步带你理解SVM。总的来说，SVM经历了线性可分支持向量机、线性支持向量机和非线性支持向量机。
- 线性可分支持向量机与硬间隔最大化
考虑如下二分类问题：
该分类问题是线性可分的，SVM的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面，这样的超平面是唯一的。这里线性可分模型的的间隔最大化又称为硬间隔最大化。
下面考虑如何求得一个几何间隔最大的分离超平面，这个问题可以表示为下面的约束优化问题： max w , b γ s . t . y ( i ) ( w T x ( i ) + b ) ≥ γ , i = 1 , ⋯ , m ∥ w ∥ = 1 \begin{aligned}&\max_{w,b}\quad\gamma\\&\mathrm{s.t.}\quad y^{(i)}\left(w^Tx^{(i)}+b\right)\geq\gamma,\quad i=1,\cdots,m\\&\quad\quad\lVert w\rVert=1\end{aligned} w,bmaxγs.t.y(i)(wTx(i)+b)≥γ,i=1,⋯,m∥w∥=1 即我们希望最大化整个训练样本中最小的几何间隔。上面的优化问题有个棘手的限制条件||w||=1（这是一个非凸性约束，即参数w可能位于一个单位圆环/球面上），这显然不是可以提交给标准的凸优化软件（如梯度下降法、牛顿法等）去解决的问题。所以，我们将上面的问题变形为用函数函数间隔表示另一种的形式： max w , b γ ^ ∥ w ∥ s . t . y ( i ) ( w T x ( i ) + b ) ≥ γ ^ , i = 1 , ⋯ , m \begin{aligned}&\max_{w,b}\quad\frac{\hat\gamma}{\lVert w\rVert}\\&\mathrm{s.t.}\quad y^{(i)}\left(w^Tx^{(i)}+b\right)\geq\hat\gamma,\quad i=1,\cdots,m\end{aligned} w,bmax∥w∥γ^s.t.y(i)(wTx(i)+b)≥γ^,i=1,⋯,m 我们改变了几何间隔的表示方式，舍弃了非凸的限制条件||w||=1，但是这时我们的优化对象 γ ^ ∥ w ∥ \frac{\hat\gamma}{\lVert w\rVert} ∥w∥γ^仍然是非凸的，依旧无法通过现有的凸优化软件来解决此类问题。
于是，我们发现在第一个优化问题中，存在非凸性的限制条件，而在第二个优化问题中，存在非凸性的优化目标，所以我们并不能保证软件可以找到全局最小值，要带上限制条||w||=1是因为我们的优化想要度量的是几何间隔，那我们应该如何解决这个问题呢？在我自己的学习过程中，我在理解下面的转化时花费了许多时间。
回想前一讲，我们知道，按比例缩放参数(w,b)会改变函数间隔但不会改变超平面本身，因此我们可以通过函数间隔标准化w和b，即令 γ ^ = 1 \hat\gamma=1 γ^=1，则优化问题可以转化为如下的原始优化问题：
min w , b 1 2 ∥ w ∥ 2 s . t . y ( i ) ( w T x ( i ) + b ) ≥ 1 , i = 1 , ⋯ , m \begin{aligned}&\min_{w,b}\quad\frac{1}{2}\lVert w\rVert^2\\&\mathrm{s.t.}\quad y^{(i)}\left(w^Tx^{(i)}+b\right)\geq 1,\quad i=1,\cdots,m\end{aligned} w,bmin21∥w∥2s.t.y(i)(wTx(i)+b)≥1,i=1,⋯,m 这样，我们就把原来棘手的最大间隔优化问题转化为了可以通过软件（如QP: quadratic programming）求解的带有线性约束的凸二次型问题。到这里问题基本结束，但值得一提的是，我们可以通过拉格朗日对偶引出该优化问题的对偶模式，通过使用核方法，将保证我们将SVM推广到高维空间时算法的高效求解，其求解速度远高于QP。拉格朗日对偶见概念引入的第4点。接下去看前请确认自己理解了 一. 概念引入 中的拉格朗日对偶。
首先为原始优化问题构建拉格朗日函数: L ( w , b , α ) = 1 2 ∥ w ∥ 2 − ∑ i = 1 m α i [ y ( i ) ( w T x ( i ) + b ) − 1 ] \mathcal{L}(w,b,\alpha)=\frac{1}{2}\lVert w\rVert^2-\sum_{i=1}^m\alpha_i\left[y^{(i)}\left(w^Tx^{(i)}+b\right)-1\right] L(w,b,α)=21∥w∥2−i=1∑mαi[y(i)(wTx(i)+b)−1]根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题： max a min w , b L ( w , b , α ) \max_{a}\min_{w,b}\mathcal{L}(w,b,\alpha) amaxw,bminL(w,b,α)先求 min w , b L ( w , b , α ) \min_{w,b}\mathcal{L}(w,b,\alpha) minw,bL(w,b,α)
对 L \mathcal{L} L分别求关于 w , b w,b w,b的偏导，并将偏导数置为零：
∇ w L ( w , b , α ) = w − ∑ i = 1 m α i y ( i ) x ( i ) = 0 \nabla_w\mathcal{L}(w,b,\alpha)=w-\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)}=0 ∇wL(w,b,α)=w−i=1∑mαiy(i)x(i)=0 ∂ ∂ b L ( w , b , α ) = ∑ i = 1 m α i y ( i ) = 0 \frac{\partial}{\partial b}\mathcal{L}(w,b,\alpha)=\sum_{i=1}^m\alpha_iy^{(i)}=0 ∂b∂L(w,b,α)=i=1∑mαiy(i)=0解得 w = ∑ i = 1 m α i y ( i ) x ( i ) ， ∑ i = 1 m α i y ( i ) = 0 \quad w=\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)} ，\quad \sum_{i=1}^m\alpha_iy^{(i)}=0 w=∑i=1mαiy(i)x(i)，∑i=1mαiy(i)=0
代入拉格朗日函数，得到 min w , b L ( w , b , α ) = W ( w , b , α ) = ∑ i = 1 m α i − 1 2 ∑ i , j = 1 m α i α j y ( i ) y ( j ) ( x ( i ) ) T x ( j ) \begin{aligned}\min_{w,b}\mathcal{L}(w,b,\alpha)&=W(w,b,\alpha)\\&=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i,j=1}^m\alpha_i\alpha_jy^{(i)}y^{(j)}\left(x^{(i)}\right)^Tx^{(j)}\end{aligned} w,bminL(w,b,α)=W(w,b,α)=i=1∑mαi−21i,j=1∑mαiαjy(i)y(j)(x(i))Tx(j)最终得到下面的对偶优化问题:
max α W ( α ) = ∑ i = 1 m α i − 1 2 ∑ i , j = 1 m α i α j y ( i ) y ( j ) ⟨ x ( i ) , x ( j ) ⟩ s . t . α i ≥ 0 , i = 1 , ⋯ , m ∑ i = 1 m α i y ( i ) = 0 \begin{aligned}\max_{\alpha}&\quad W(\alpha)=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i,j=1}^m\alpha_i\alpha_jy^{(i)}y^{(j)}\left\langle x^{(i)},x^{(j)}\right\rangle\\\mathrm{s.t.}&\quad \alpha_i\geq 0,\quad i=1,\cdots,m\\&\quad\sum_{i=1}^m\alpha_iy^{(i)}=0\end{aligned} αmaxs.t.W(α)=i=1∑mαi−21i,j=1∑mαiαjy(i)y(j)⟨x(i),x(j)⟩αi≥0,i=1,⋯,mi=1∑mαiy(i)=0原始问题满足条件C1，因此 w ∗ , α ∗ , β ∗ w^*,\alpha^*,\beta^* w∗,α∗,β∗一定存在（ w ∗ w^* w∗是原始优化问题的解， α ∗ , β ∗ \alpha^*,\beta^* α∗,β∗是对偶优化问题的解），且 p ∗ = d ∗ = L ( w ∗ , α ∗ , β ∗ ) p^*=d^*=\mathcal{L}(w^*,\alpha^*,\beta^*) p∗=d∗=L(w∗,α∗,β∗)，且 w ∗ , α ∗ , β ∗ w^*,\alpha^*,\beta^* w∗,α∗,β∗满足KKT条件，那么我们就可以通过计算对偶问题的解 α i ∗ \alpha_i^* αi∗来得到原始问题的解 w ∗ , b ∗ w^*,b^* w∗,b∗。 w ∗ w^* w∗可以通过将 a i ∗ a_i^* ai∗代入上面偏导置0得到的等式中求得，对于 b ∗ b^* b∗，因为此时超平面的法向量已经确定，我们只需要在满足该法向量的超平面中“固定”适当的截距，使得超平面到正负样本的距离相等即可，由该几何意义我们可以写出：
b ∗ = max i : y ( i ) = − 1 w ∗ T x ( i ) + min i : y ( i ) = 1 w ∗ T x ( i ) 2 b^*=\frac{\max_{i:y^{(i)}=-1}w^{*T}x^{(i)}+\min_{i:y^{(i)}=1}w^{*T}x^{(i)}}{2} b∗=2maxi:y(i)=−1w∗Tx(i)+mini:y(i)=1w∗Tx(i) 如此，我们便得到了分离超平面 ( w , b ) (w,b) (w,b)，现在想要预测一个新的输入点x，那么我们会计算 w T x + b w^Tx+b wTx+b，当且仅当这个值大于1时，模型才会给出结论y=1。结合 w = ∑ i = 1 m α i y ( i ) x ( i ) w=\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)} w=∑i=1mαiy(i)x(i)，这个判定值也可以表示为： w T x + b = ( ∑ i = 1 m α i y ( i ) x ( i ) ) T x + b = ∑ i = 1 m α i y ( i ) ⟨ x ( i ) , x ⟩ + b \begin{aligned}w^Tx+b&=\left(\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)}\right)^Tx+b\\&=\sum_{i=1}^m\alpha_iy^{(i)}\left\langle x^{(i)},x\right\rangle+b\end{aligned} wTx+b=(i=1∑mαiy(i)x(i))Tx+b=i=1∑mαiy(i)⟨x(i),x⟩+b如果我们已经求出 α i \alpha_i αi，为了做出预测，则只需要按照上式求出x与训练集中样本的内积。而除了支持向量以外，其余训练样本对应的 α i \alpha_i αi都是零，因此上面的求和中很多项都是零，只有支持向量的 α i > 0 \alpha_i>0 αi>0。所以我们只需要求出x与支持向量的内积，然后再根据上式计算做出预测即可。
证明支持向量的 α i > 0 \alpha_i>0 αi>0：
根据KKT互补条件 α i ∗ g i ( w ∗ ) = 0 \alpha_i^*g_i(w^*)=0 αi∗gi(w∗)=0可得 α i [ y ( i ) ( w T x ( i ) + b ) − 1 ] = 0 \alpha_i\left[y^{(i)}\left(w^Tx^{(i)}+b\right)-1\right]=0 αi[y(i)(wTx(i)+b)−1]=0对于 α i > 0 \alpha_i>0 αi>0的实例 x i x_i xi来说，有 y ( i ) ( w T x ( i ) + b ) − 1 = 0 y^{(i)}\left(w^Tx^{(i)}+b\right)-1=0 y(i)(wTx(i)+b)−1=0即 y ( i ) ( w T x ( i ) + b ) = ± 1 y^{(i)}\left(w^Tx^{(i)}+b\right)=±1 y(i)(wTx(i)+b)=±1即满足 α i > 0 \alpha_i>0 αi>0的实例一定在分离超平面上，根据定义这样的实例就是支持向量。
对于线性可分问题，上述线性可分支持向量机（硬间隔最大化）算法是完美的。但是，训练数据集线性可分是理想情形。在现实问题中，训练数据集往往是线性不可分的，即在样本中出现噪声或特异点。此时，有更一般的学习方法。
\quad - 线性支持向量机与软间隔最大化
线性可分问题的SVM对于线性不可分的数据是不适用的，因为这时上述方法中的不等式约束并不能都成立，那么怎么才能将它扩展到线性不可分问题呢？这就需要修改硬间隔最大化使其成为软间隔最大化。
通常情况下，训练数据中有一些特异点（噪声），将这些特异点去除后，剩下的大部分的样本点组成的集合是线性可分的。线性不可分意味着某些样本点 ( x i , y i ) (x_i,y_i) (xi,yi)不能满足函数间隔大于等于1的约束条件，为了解决这个问题，可以对每个样本点引进一个松弛变量 ξ i ≥ 0 \xi_i\ge0 ξi≥0，使得函数间隔加上松弛变量大于等于1，这样就不必所有点的函数间隔都大于等于1，约束条件变为 y i ( w x i + b ) ≥ 1 − ξ i y_i(wx_i+b)\ge1-\xi_i yi(wxi+b)≥1−ξi，但是我们仍然需要保持大多数点满足函数间隔大于等于1的条件，因此对于每个松弛变量 ξ i \xi_i ξi支付一个代价，目标函数变成： 1 2 ∥ w ∥ 2 + C ∑ i = 1 N ξ i \frac{1}{2}\lVert w\rVert^2+C\sum_{i=1}^N\xi_i 21∥w∥2+Ci=1∑Nξi这里 C > 0 C>0 C>0称为惩罚参数，最小化该目标函数不仅能使 1 2 ∥ w ∥ 2 \frac{1}{2}\lVert w\rVert^2 21∥w∥2尽量小即间隔尽量大，还能使误差分类点的个数尽量少， C C C是调和二者的参数。
由此我们可以得到原始优化问题： min w , b , ξ 1 2 ∥ w ∥ 2 + C ∑ i = 1 N ξ i s . t . y ( i ) ( w T x ( i ) + b ) ≥ 1 − ξ i , i = 1 , ⋯ , N ξ i ≥ 0 , i = 1 , ⋯ , N \begin{aligned}\min_{w,b,\xi}&\quad\frac{1}{2}\lVert w\rVert^2+C\sum_{i=1}^N\xi_i\\\mathrm{s.t.}&\quad y^{(i)}\left(w^Tx^{(i)}+b\right)\geq 1-\xi_i,\quad i=1,\cdots,N\\&\quad \xi_i\geq0,\quad i=1,\cdots,N\end{aligned} w,b,ξmins.t.21∥w∥2+Ci=1∑Nξiy(i)(wTx(i)+b)≥1−ξi,i=1,⋯,Nξi≥0,i=1,⋯,N该问题是一个凸二次规划问题，可以证明 w w w的解是唯一的的，但 b b b的解可能不是唯一的，而是存在于一个区间。
得到对偶优化问题： min α W ( α ) = 1 2 ∑ i , j = 1 N α i α j y ( i ) y ( j ) ⟨ x ( i ) , x ( j ) ⟩ − ∑ i = 1 N α i s . t . 0 ≤ α i ≤ C , i = 1 , ⋯ , N ∑ i = 1 N α i y ( i ) = 0 \begin{aligned}\min_{\alpha}&\quad W(\alpha)=\frac{1}{2}\sum_{i,j=1}^N\alpha_i\alpha_jy^{(i)}y^{(j)}\left\langle x^{(i)},x^{(j)}\right\rangle-\sum_{i=1}^N\alpha_i\\\mathrm{s.t.}&\quad 0\leq\alpha_i\leq C,\quad i=1,\cdots,N\\&\quad\sum_{i=1}^N\alpha_iy^{(i)}=0\end{aligned} αmins.t.W(α)=21i,j=1∑Nαiαjy(i)y(j)⟨x(i),x(j)⟩−i=1∑Nαi0≤αi≤C,i=1,⋯,Ni=1∑Nαiy(i)=0线性SVM的对偶学习方法首先求解求偶问题得到最优解 α ∗ \alpha^* α∗，然后求原始问题最优解 w ∗ , b ∗ w^*,b^* w∗,b∗，得出分离超平面。
在线性不可分的情况下，仍然将 α i ∗ > 0 \alpha_i^*>0 αi∗>0的点称为支持向量（软间隔的支持向量），但这时候的支持向量比线性可分时的情况更复杂一些，考虑下图：
图中实线是分离超平面，虚线是间隔边界，软间隔的支持向量 x i x_i xi或者在间隔边界上，或者在间隔边界与分离超平面之间，或者在分离超平面误分一侧。《统计学习方法》中提到 ξ i ∥ w ∥ \frac{\xi_i}{\lVert w\rVert} ∥w∥ξi是实例 x i x_i xi到间隔边界的距离，但没有作出说明，这里笔者作出说明：
到平面的几何间隔 γ = γ ^ ∥ w ∥ \gamma=\frac{\hat\gamma}{\lVert w\rVert} γ=∥w∥γ^，而实例 x i x_i xi到分离超平面的函数间隔为 1 − ξ i 1-\xi_i 1−ξi，几何间隔为 1 − ξ i ∥ w ∥ \frac{1-\xi_i}{\lVert w\rVert} ∥w∥1−ξi，因为间隔边界到分离超平面的函数间隔已经被规范化为1个单位，故其几何间隔为 1 ∥ w ∥ \frac{1}{\lVert w\rVert} ∥w∥1，则两者相减可以得到 ξ i ∥ w ∥ \frac{\xi_i}{\lVert w\rVert} ∥w∥ξi是实例 x i x_i xi到间隔边界的距离。由这个重要结论可以推出以下结论：
· 若 α i ∗ < C \alpha_i^*<C αi∗<C，则 ξ i = 0 \xi_i=0 ξi=0，支持向量 x i x_i xi恰好落在间隔边界上；
· 若 α i ∗ = C ， 0 < ξ i < 1 \alpha_i^*=C，0<\xi_i<1 αi∗=C，0<ξi<1，则分类正确，支持向量 x i x_i xi在分离超平面和间隔边界之间；
· 若 α i ∗ = C ， ξ i = 1 \alpha_i^*=C，\xi_i=1 αi∗=C，ξi=1，则支持向量 x i x_i xi落在分离超平面上；
· 若 α i ∗ = C ， ξ i > 1 \alpha_i^*=C，\xi_i>1 αi∗=C，ξi>1，则支持向量 x i x_i xi落在分离超平面误分一侧。
除此之外，线性SVM还有另一种解释，就是最小化以下目标函数
目标函数的第一项是经验损失或经验函数，函数
称为合页损失函数（hinge loss function），下标"+"表示以下取正值的函数
这就是说，当样本点 ( x i , y i ) (x_i,y_i) (xi,yi)被正确分类且函数间隔 y i ( w x i + b ) y_i(wx_i+b) yi(wxi+b)大于1时，损失是0，否则损失是 1 − y i ( w x i + b ) 1-y_i(wx_i+b) 1−yi(wxi+b)，这里注意到并不是被正确分类了就没有损失，而是要在间隔边界以外才可以。目标函数的第二项是系数为 λ \lambda λ的 w w w的 L 2 L_2 L2范数，是正则化项。
合页损失函数不仅要分类正确，而且确信度要足够高时损失才为0，也就是说，合页损失函数相比起感知机模型来说对学习有更高的要求（所以希望大家都成为合页损失函数，尽量不做感知机哦）。
\quad - 非线性支持向量机与核函数
对解线性分类问题，线性分类支持向量机是一种非常有效的方法。但是，有时分类问题是非线性的，这时可以使用非线性支持向量机。看到这里请确保已经理解核函数，详情可见（一.5）。
利用核方法，我们可以将线性分类的学习方法应用到非线性分类问题中。将线性SVM扩展到非线性SVM中，只需要将线性SVM对偶形式中的内积换成核函数即可。 具体方法不再赘述，与线性SVM一致。
三. 序列最小最优化算法（SMO: sequential minimal optimization）
- 概述
序列最小优化算法来源于John Platt，他找到了一种高效解决“由支持向量机引出的对偶问题”的算法。在继续介绍该算法之前，我们先来看一下坐标下降/上升算法。
\quad - 坐标下降/上升算法
考虑如何解决一个不加约束条件的优化问题： max α W ( α 1 , α 2 , ⋯ , α m ) \max_\alpha W\left(\alpha_1,\alpha_2,\cdots,\alpha_m\right) αmaxW(α1,α2,⋯,αm)现在，我们只将 W W W看做关于 α i α_i αi的函数，与支持向量机无关。到目前为止我们已经了解了两种优化算法：梯度下降/上升法，牛顿法，这里我们再来介绍一种新的优化算法——坐标下降/上升法（coordinate descent/ascent algorithm）：
在算法里面一层循环中，我们会固定除 α i α_i αi以外的参数，然后重新优化这个关于 α i α_i αi的函数 W W W。对上面的这个例子，里面的循环会按照 α 1 , α 2 , ⋯ , α m , α 1 , α 2 , ⋯ \alpha_1,\alpha_2,\cdots,\alpha_m,\alpha_1,\alpha_2,\cdots α1,α2,⋯,αm,α1,α2,⋯的顺序进行优化。（对一些复杂的问题可能会使用别的顺序，比如，我们可以看哪个参数会带来 W ( α ) W(α) W(α)最大幅度的增长，就选择哪个参数作为下一个优化的对象。）而当函数 W W W恰好符合里面一层循环可以高效运行的状态时（事实上有很多优化问题很容易固定其他参数只对一个参数求最优值，在这种情况下本算法的内层循环将会执行的非常快。而支持向量机通常也属于这种情况），坐标下降/上升法确实是一个效率很高的算法，如图所示：
这是一个需要优化的二次函数的等高线图，坐标上升算法初始值取在(2,−2)，图中的线就是坐标上升算法从初始值到全局最大值的优化路径。注意到算法的每一步都是沿着坐标轴方向优化，因为算法每次只优化一个参数。
\quad - SMO
考虑我们的对偶优化问题： min α W ( α ) = 1 2 ∑ i , j = 1 N α i α j y ( i ) y ( j ) ⟨ x ( i ) , x ( j ) ⟩ − ∑ i = 1 N α i s . t . 0 ≤ α i ≤ C , i = 1 , ⋯ , N ∑ i = 1 N α i y ( i ) = 0 \begin{aligned}\min_{\alpha}&\quad W(\alpha)=\frac{1}{2}\sum_{i,j=1}^N\alpha_i\alpha_jy^{(i)}y^{(j)}\left\langle x^{(i)},x^{(j)}\right\rangle-\sum_{i=1}^N\alpha_i\\\mathrm{s.t.}&\quad 0\leq\alpha_i\leq C,\quad i=1,\cdots,N\\&\quad\sum_{i=1}^N\alpha_iy^{(i)}=0\end{aligned} αmins.t.W(α)=21i,j=1∑Nαiαjy(i)y(j)⟨x(i),x(j)⟩−i=1∑Nαi0≤αi≤C,i=1,⋯,Ni=1∑Nαiy(i)=0假设我们已经有一组满足约束条件的 α i α_i αi，现在，我们固定 α 2 , ⋯ , α m \alpha_2,\cdots,\alpha_m α2,⋯,αm，然后进行坐标上升优化步骤，重新优化关于 α 1 \alpha_1 α1的目标函数，那么我们能够得到更加优化的目标函数吗？答案是否定的，因为 α 1 y ( 1 ) = − ∑ i = 2 m α i y ( i ) \alpha_1y^{(1)}=-\sum_{i=2}^m\alpha_iy^{(i)} α1y(1)=−i=2∑mαiy(i)上式两边同时乘以 y ( 1 ) y^{(1)} y(1)，因为 y ( 1 ) y^{(1)} y(1)∈{−1,1}，所以 ( y ( 1 ) ) 2 = 1 (y^{(1)})^2=1 (y(1))2=1，则有 α 1 = − y ( 1 ) ∑ i = 2 m α i y ( i ) \alpha_1=-y^{(1)}\sum_{i=2}^m\alpha_iy^{(i)} α1=−y(1)i=2∑mαiy(i)我们发现， α 1 \alpha_1 α1直接可以由其余的 α i α_i αi确定，所以如果我们固定 α 2 , ⋯ , α m \alpha_2,\cdots,\alpha_m α2,⋯,αm，在不违反约束条件的前提下，我们根本不能改变 α 1 \alpha_1 α1。
如果我们想要更新某个 α i α_i αi，我们就至少得同时更新两个参数以保证算法仍在约束条件内。这就是序列最小优化算法（最小就是指一次改变最少个 α i α_i αi，在这里即两个）的思路：
Repeat till convergence {
1. 选择一对参数 α i , α j \alpha_i,\alpha_j αi,αj作为将要优化的对象，通过启发式（也就是经验法则）找到两个可以使优化目标朝全局最大值最快收敛的参数。
2. 在满足条件的情况下优化关于 α i , α j \alpha_i,\alpha_j αi,αj的函数 W ( α ) W(\alpha) W(α)。
}
序列最小优化是一个高效算法的关键在于对 α i , α j \alpha_i,\alpha_j αi,αj的计算效率非常高（它可能比牛顿法迭代的步骤更多，但是它每次迭代的代价非常小）。我们来简要推导一下这种高效的参数更新。
那么如何应用SMO算法在满足条件的情况下优化关于 α i , α j \alpha_i,\alpha_j αi,αj的函数 W ( α ) W(\alpha) W(α)呢？
假设我们有一组满足约束条件的 α 1 , α 2 \alpha_1,\alpha_2 α1,α2，这里其实可以是任意 α i , α j \alpha_i,\alpha_j αi,αj，只不过为了方便后面写推导公式才假设 α 1 , α 2 \alpha_1,\alpha_2 α1,α2。然后将参数 α 3 , ⋯ , α m \alpha_3,\cdots,\alpha_m α3,⋯,αm固定，然后优化关于 α 1 , α 2 \alpha_1,\alpha_2 α1,α2的函数 W ( α 1 , α 2 , ⋯ , α m ) W(\alpha_1,\alpha_2,\cdots,\alpha_m) W(α1,α2,⋯,αm)。根据 ∑ i = 1 N α i y ( i ) = 0 \sum_{i=1}^N\alpha_iy^{(i)}=0 ∑i=1Nαiy(i)=0可得 α 1 y ( 1 ) + α 2 y ( 2 ) = − ∑ i = 3 m α i y ( i ) \alpha_1y^{(1)}+\alpha_2y^{(2)}=-\sum_{i=3}^m\alpha_iy^{(i)} α1y(1)+α2y(2)=−i=3∑mαiy(i)等式右边是固定的（因为我们固定了参数 α 3 , ⋯ , α m \alpha_3,\cdots,\alpha_m α3,⋯,αm），我们把右边记作常量 ζ \zeta ζ： α 1 y ( 1 ) + α 2 y ( 2 ) = ζ \alpha_1y^{(1)}+\alpha_2y^{(2)}=\zeta α1y(1)+α2y(2)=ζ我们可以用下图表示 α 1 , α 2 \alpha_1,\alpha_2 α1,α2上的约束条件：
从 0 ≤ α i ≤ C 0\leq\alpha_i\leq C 0≤αi≤C得知 α 1 , α 2 \alpha_1,\alpha_2 α1,α2必须落在图中 [ 0 , C ] × [ 0 , C ] [0,C]\times[0,C] [0,C]×[0,C]的区域内，从约束条件我们还能得到 L ≤ α 2 ≤ H L\leq\alpha_2\leq H L≤α2≤H。在本例中 L = 0 L=0 L=0，但并不总是如此，这需要参考直线 α 1 y ( 1 ) + α 2 y ( 2 ) = ζ \alpha_1y^{(1)}+\alpha_2y^{(2)}=\zeta α1y(1)+α2y(2)=ζ。
根据 ( y ( i ) ) 2 = 1 \left(y^{(i)}\right)^2=1 (y(i))2=1 和 α 1 y ( 1 ) + α 2 y ( 2 ) = ζ \alpha_1y^{(1)}+\alpha_2y^{(2)}=\zeta α1y(1)+α2y(2)=ζ，可以得到 α 1 = ( ζ − α 2 y ( 2 ) ) y ( 1 ) \alpha_1=\left(\zeta-\alpha_2y^{(2)}\right)y^{(1)} α1=(ζ−α2y(2))y(1)因此 W ( α ) W(\alpha) W(α)可以表示为 W ( α 1 , α 2 , ⋯ , α m ) = W ( ( ζ − α ( 2 ) y ( 2 ) ) y ( 1 ) , α 2 , ⋯ , α m ) W(\alpha_1,\alpha_2,\cdots,\alpha_m)=W\left(\left(\zeta-\alpha^{(2)}y^{(2)}\right)y^{(1)},\alpha_2,\cdots,\alpha_m\right) W(α1,α2,⋯,αm)=W((ζ−α(2)y(2))y(1),α2,⋯,αm)将 α 3 , ⋯ , α m \alpha_3,\cdots,\alpha_m α3,⋯,αm当做常数，易知这就是一个关于 α 2 \alpha_2 α2的二次函数。也就是说可以将 W W W看做 a α 2 2 + b α 2 + c a\alpha_2^2+b\alpha_2+c aα22+bα2+c。如果忽略 L ≤ α 2 ≤ H L\leq\alpha_2\leq H L≤α2≤H，则我们可以通过将这个二次函数的导数置为零的方法，求出最大值。我们使用 α 2 n e w , u n c l i p p e d \alpha_2^{new,unclipped} α2new,unclipped标记解出的 α 2 \alpha_2 α2。如果我们服从 0 ≤ α i ≤ C 0\leq\alpha_i\leq C 0≤αi≤C的约束条件，想要最大化 W W W，只需要简单的将 α 2 n e w , u n c l i p p e d \alpha_2^{new,unclipped} α2new,unclipped“剪入” [ L , H ] [L,H] [L,H]的区间即可： α 2 n e w = { H i f α 2 n e w , u n c l i p p e d > H α 2 n e w , u n c l i p p e d i f L ≤ α 2 n e w , u n c l i p p e d ≤ H L i f α 2 n e w , u n c l i p p e d < L \alpha_2^{new}=\begin{cases}H&if\ \alpha_2^{new,unclipped}\gt H\\\alpha_2^{new,unclipped}&if\ L\leq\alpha_2^{new,unclipped}\leq H\\L&if\ \alpha_2^{new,unclipped}\lt L\end{cases} α2new=⎩⎪⎨⎪⎧Hα2new,unclippedLif α2new,unclipped>Hif L≤α2new,unclipped≤Hif α2new,unclipped<L当我们求出 α 2 n e w \alpha_2^{new} α2new之后，代入 α 1 = ( ζ − α 2 y ( 2 ) ) y ( 1 ) \alpha_1=\left(\zeta-\alpha_2y^{(2)}\right)y^{(1)} α1=(ζ−α2y(2))y(1)即可得到 α 1 n e w \alpha_1^{new} α1new的优化值。
至此，SVM的全部知识就已经系统地梳理了一遍，如果你认真地阅读和推导这篇文章，相信你对于SVM的理论知识已经能完全掌握了。对于SVM的深度剖析并不只是为了能够学会这个模型本身，更进一步是为了学习前辈们敏捷缜密的思维和数学逻辑，再进一步是为了提高自己的学习能力和坚持探索的精神！共勉！