线性SVM分类器的工作原理

线性支持向量机的分类方法，是在这组分布中找出一个超平面作为决策边界，使得模型在数据上的分类误差尽量接近于小，尤其是在未知数据集上的分类误差（泛化误差）尽量小。

超平面
在几何中，超平面是一个空间的子空间，它是维度比所在空间小一维的空间，如果数据空间本身是三维的，则其超平面是二维平面，而如果数据空间本身是二维的，则其超平面是一维的直线。 在二分类问题中，如果一个超平面能够将数据划分为两个集合，其中每个集合中包含单独的一个类别，我们就说这个超平面是数据的“决策边界”。

在决策边界一侧的所有点属于一个类，而另一侧的所有点分类属于另一个类。如果把上图中的数据集作为训练集，只要直线的一边只有一种类型的数据，就没有分类错误，我们的训练误差就为0。但是，对于一个数据集来说，训练误差为0的决策边界可以由无数条。

但在此基础上，我们无法保证这条决策边界在未知数据集（测试集）上的表现也会优秀。对于现有的数据集来说，我们有B₁和B₂两条可能的决策边界。我们可以把决策边界B₁向两边平移，直到碰到离这条决策边界最近的方块和圆圈后停下，形成两个新的超平面，分别是b₁₁和b₁₂，并且我们将原始的决策边界移动到b₁₁和b₁₂的中间，确保B₁到b₁₁和b₁₂的距离相等。在b₁₁和b₁₂中间的距离，叫做B₁这条决策边界的边际(margin)，通常记作d。

为了简便，我们称b₁₁和b₁₂为“虚线超平面”。

对B₂也执行同样的操作，然后我们对比两个决策边界，发现两个决策边界在训练集上的误差都为0。

现在我们引入和原本数据集相同分布的测试样本（红色），我们可以发现，对于B₁而言，依然没有样本分类错误，B₁这条决策边界上的泛化误差也是0。但是对于B₂而言，有三个方块被误认为了是圆，这条决策边界上的误差就远大于B₁。

从中可以看出，拥有更大边际的决策边界在分类中的泛化误差更小。如果边际很小，则任何轻微的扰动都会对决策边界产生很大的影响。边际很小的情况，是一种模型在训练集上表现很好，却在测试集上表现不佳的情况，即“过拟合”现象。所以在寻找决策边界的时候，我们希望边际越大越好。

支持向量机，就是通过找出边际最大的决策边界，对数据进行分类的分类器。

线性SVM损失函数的理解

间隔与支持向量

先来定义决策边界，假设给定的数据集有$N$N个样本，每个训练样本$i$i可以表示为$（\boldsymbol {x_i},y_i）$（xi​,yi​）,其中$\boldsymbol {x_i} = (x_{1i},x_{2i},...,x_{ni})^T$xi​=(x1i​,x2i​,...,xni​)T，每个样本含有$n$n个特征。二分类标签$y_i\in \{-1,1\}$yi​∈{−1,1}。

如果$n$n等于2，则有$i = (x_{1i},x_{2i},y_i)^T$i=(x1i​,x2i​,yi​)T，分别由特征向量和标签组成，此时在二维平面上，以$x_2$x2​为横坐标，$x_1$x1​为纵坐标，$y$y为颜色，可以可视化我们的$N$N个样本：

我们规定紫色点的标签为1，红色点的标签为-1。我们要在该数据集上寻找一个决策边界（二维平面上为一条直线）。

二维平面上的任意一条直线可以表示为：
$x_1= ax_2+b$x1​=ax2​+b
将上式进行等价变换：
$\begin{aligned} &0=a x_{2}-x_{1}+b\\ &0=[a,-1] *\left[\begin{array}{l} x_{2} \\ x_{1} \end{array}\right]+b\\ &0=\boldsymbol{w}^{T} \boldsymbol{x}+b \end{aligned}$​0=ax2​−x1​+b0=[a,−1]∗[x2​x1​​]+b0=wTx+b​
其中$[a,-1]$[a,−1]就是参数向量$\boldsymbol {w}$w，$\boldsymbol {x}$x就是特征向量，$ {b}$就是截距。

在一组数据下，给定固定的$\boldsymbol {w}$w和$b$b，这个式子就是一条固定的直线；当$\boldsymbol {w}$w和$b$b不确定的情况下，可表示平面上的任意直线；给定$\boldsymbol {w}$w、$b$b和$x$x，表达式可表示固定的点。在SVM中，就使用这个表达式来表示决策边界，我们的目标式求解边际最大化的决策边界，因此需要求解参数向量$\boldsymbol {w}$w$和$和$b$b。

参数向量$\boldsymbol {w}$w的方向

在决策边界上任取两点$x_a$xa​,$x_b$xb​，带入决策边界的表达式：
$0=\boldsymbol{w}^{T} \boldsymbol{x_a}+b\\ 0=\boldsymbol{w}^{T} \boldsymbol{x_b}+b$0=wTxa​+b0=wTxb​+b
将上面两式相减可得：
$\boldsymbol{w}^{T}* (\boldsymbol{x_b}-\boldsymbol{x_a})=0$wT∗(xb​−xa​)=0
一个列向量的转置乘以另一个列向量，可以得到两个向量的点积（dot product）。两个向量点积为0表示两个向量的方向式互相垂直的。$x_a$xa​,$x_b$xb​是决策边界上的两点，相减后的向量方向由$x_b$xb​指向$x_a$xa​,并且平行于决策边界。因此，参数向量$\boldsymbol w$w的方向必然垂直于决策边界。

此时，有了决策边界。图中任意一个紫色点$x_p$xp​可以被表示为：
$\boldsymbol{w}^{T}·\boldsymbol x_p+b=1$wT⋅xp​+b=1
任意一个红色点$x_r$xr​可以被表示为：
$\boldsymbol{w}^{T}·\boldsymbol x_r+b=1$wT⋅xr​+b=1
此时，如果有新的测试数据$\boldsymbol x_t$xt​输入，则$\boldsymbol x_t$xt​的标签可以根据下式来判定：
$y=\left\{\begin{aligned} 1, & \text { if } \boldsymbol{w} \cdot \boldsymbol{x}_{t}+b>0 \\ -1, & \text { if } \boldsymbol{w} \cdot \boldsymbol{x}_{t}+b<0 \end{aligned}\right.$y={1,−1,​ if w⋅xt​+b>0 if w⋅xt​+b<0​

虚线超平面与支持向量

决策边界的两边要有两个超平面，这两个超平面在二维空间中就是两条平行线（就是我们的虚线超平面），而他们之间的距离就是我们的边际$d$d。而决策边界位于这两条线的中间，所以这两条平行线必然是对称的。我们令这两条平行线被表示为：
$\boldsymbol{w}·\boldsymbol x+b=1\\ \boldsymbol{w}·\boldsymbol x+b=-1$w⋅x+b=1w⋅x+b=−1
这就是我们平行于决策边界的两条线的表达式，表达式两边的1和-1分别表示了两条平行于决策边界的虚线到决策边界的相对距离。此时，我们可以让这两条线分别过两类数据中距离我们的决策边界最近的点，这些点就被称为“支持向量”，而决策边界永远在这两条线的中间，所以可以被调整。我们令紫色类的点为$x_p$xp​，红色类的点为$x_r$xr​，则我们可以得到：
$\boldsymbol{w}·\boldsymbol x_p+b=1\\ \boldsymbol{w}·\boldsymbol x_r+b=-1$w⋅xp​+b=1w⋅xr​+b=−1
两式相减，则有：
$\boldsymbol{w}* (\boldsymbol{x_p}-\boldsymbol{x_r})=2$w∗(xp​−xr​)=2
如下图所示，$(\boldsymbol {x_p-x_r})$(xp​−xr​)可表示为两点之间的连线，而我们的实际边际$d$d是平行于$\boldsymbol w$w的，所以现在相当于是得到了三角形的斜边，并且知道一条直角边的方向。

线性代数中的模长
向量$\boldsymbol b$b除以自身的模长可以得到$b$b方向上的单位向量。 向量$\boldsymbol a$a乘以向量$\boldsymbol b$b方向上的单位向量，可以得到向量$\boldsymbol a$a在向量$\boldsymbol b$b方向上的投影长度。

所以，将上述式子两边同除以$||w||$∣∣w∣∣，可得：
$\begin{aligned} &\frac{\boldsymbol {w \cdot\left(x_{p}-x_{r}\right)}}{\|w\|}=\frac{2}{\|w\|}\\ &\therefore d=\frac{2}{\|w\|} \end{aligned}$​∥w∥w⋅(xp​−xr​)​=∥w∥2​∴d=∥w∥2​​

我们的目的，是要最大化边际求决策边界，要最大化$d$d，则求解$\boldsymbol w$w的最小值。极值问题可以相互转化，我们可以把求解$\boldsymbol w$w的最小值转化为求解以下函数的最小值：
$f(w)=\frac{\|w\|^{2}}{2}$f(w)=2∥w∥2​
之所以要在模长上加上平方，是因为模长的本质是一个距离，是一个带根号的存在，取平方是为了消除根号。

我们的两条虚线表示的超平面，是数据边缘所在的点。所以对于任意样本，我们可以把决策函数写作：
$\begin{aligned} &\boldsymbol{w} \cdot \boldsymbol{x}_{i}+b \geq 1 \text { if } y_{i}=1\\ &\boldsymbol{w} \cdot \boldsymbol{x}_{i}+b \leq-1 \text { if } y_{i}=-1 \end{aligned}$​w⋅xi​+b≥1 if yi​=1w⋅xi​+b≤−1 if yi​=−1​
整理一下，把两个式子进行整合：
$y_{i}\left(\boldsymbol{w} \cdot \boldsymbol{x}_{i}+b\right) \geq 1, i=1,2 \ldots . . N$yi​(w⋅xi​+b)≥1,i=1,2…..N
这个式子被称为“函数间隔”。将函数间隔作为条件附加到我们的上，我们就得到了SVM的损失函数最初形态：
$\min _{w, b} \frac{\|\boldsymbol{w}\|^{2}}{2}\\ subject\quad to \quad y_i(\boldsymbol {w\cdot x_i}+b)\geq1,i=1,2,...N.$w,bmin​2∥w∥2​subjecttoyi​(w⋅xi​+b)≥1,i=1,2,...N.

线性SVM的拉格朗日对偶函数和决策函数

将损失函数从最初形态转换为拉格朗日乘数形态

我们的目标是最小化$\boldsymbol w$w，但其实很容易得出，如果$||w||$∣∣w∣∣为0，$f(w)$f(w)必然最小。但是$||w||$∣∣w∣∣为0是一个无效值。

首先，我们的决策边界是$\boldsymbol{w}·\boldsymbol x+b=0$w⋅x+b=0，如果$\boldsymbol w$w为0，则这个向量里包含的所有元素都为0，那就有$b = 0$b=0这个唯一值。然而，如果$b$b和$\boldsymbol w$w都为0，决策边界就不再是一条直线了，函数间隔$y_i(\boldsymbol {w\cdot x_i}+b)$yi​(w⋅xi​+b)就会为0，条件中的$y_i(\boldsymbol {w\cdot x_i}+b)\geq1$yi​(w⋅xi​+b)≥1就不可能实现，所以$\boldsymbol w$w不可以是一个0向量。可见，单纯让$f(w)=\frac{\|w\|^{2}}{2}$f(w)=2∥w∥2​为0，是不能求解出合理的$\boldsymbol w$w的，我们希望能够找出一种方式，能够让我们的条件$y_i(\boldsymbol {w\cdot x_i}+b)\geq1$yi​(w⋅xi​+b)≥1在计算中也被纳入考虑，一种业界认可的方法是使用拉格朗日乘数法(standard Lagrange multiplier method)。

我们的损失函数是二次的(quadratic)，并且我们损失函数中的约束条件在参数$w$w和$b$b下是线性的，求解这样的损失函数被称为“凸优化问题”(convex optimization problem)。拉格朗日乘数法正好可以用来解决凸优化问题，这种方法也是业界常用的，用来解决带约束条件，尤其是带有不等式的约束条件的函数的数学方法。首先第一步，我们需要使用拉格朗日乘数来将损失函数改写为考虑了约束条件的形式：
$L(w, b, \alpha)=\frac{1}{2}\|w\|^{2}-\sum_{i=1}^{N} \alpha_{i}\left(y_{i}\left(\boldsymbol{w} \cdot \boldsymbol{x}_{i}+b\right)-1\right)\left(\alpha_{i} \geq 0\right)$L(w,b,α)=21​∥w∥2−i=1∑N​αi​(yi​(w⋅xi​+b)−1)(αi​≥0)
上式被称为拉格朗日函数，其中$\alpha_i$αi​就叫做拉格朗日乘数。此时此刻，我们要求解的就不只有参数向量$\boldsymbol w$w和截距$b$b了，我们也要求解拉格朗日乘数$\alpha$α，而$x_i$xi​和$y_i$yi​都是我们已知的特征矩阵和标签。

拉格朗日函数也分为两部分。第一部分和我们原始的损失函数一样，第二部分呈现了我们带有不等式的约束条件。我们希望，$L(w, b, \alpha)$L(w,b,α) 不仅能够代表我们原有的损失函数$f(w)$f(w)和约束条件，还能够表示我们想要最小化损失函数来求解$\boldsymbol w$w和$b$b的意图，**所以我们要先以$\alpha$α为参数，求解$L(w, b, \alpha)$L(w,b,α) 的最大值，再以$\boldsymbol w$w和$b$b为参数，求解$L(w, b, \alpha)$L(w,b,α)的最小值。**因此，我们的目标可以写作：
$\min_{w,b}\max_{\alpha_i\geq0}L(w,b,\alpha)(\alpha_i\geq0)$w,bmin​αi​≥0max​L(w,b,α)(αi​≥0)
怎么理解这个式子呢？首先，我们第一步先执行max，即最大化$L(w, b, \alpha)$L(w,b,α)，那就有两种情况：

1. 当$y_i(\boldsymbol {w\cdot x_i}+b)>1$yi​(w⋅xi​+b)>1，函数的第二部分$\sum_{i=1}^{N}\alpha_i(y_i(\boldsymbol {w\cdot x_i}+b)-1)$∑i=1N​αi​(yi​(w⋅xi​+b)−1)就一定为正，式子$\frac{1}{2}\|w\|^{2}$21​∥w∥2就要减去一个正数，此时若要最大化$L(w, b, \alpha)$L(w,b,α)，则$\alpha$α必须取到0。
2. 当$y_i(\boldsymbol {w\cdot x_i}+b)<1$yi​(w⋅xi​+b)<1，函数的第二部分$\sum_{i=1}^{N}\alpha_i(y_i(\boldsymbol {w\cdot x_i}+b)-1)$∑i=1N​αi​(yi​(w⋅xi​+b)−1)就一定为负，式子$\frac{1}{2}\|w\|^{2}$21​∥w∥2就要减去一个负数，相当于加上一个正数，此时若要最大化$L(w, b, \alpha)$L(w,b,α)，则$\alpha$α必须取到正无穷。

若把函数第二部分当作一个惩罚项来看待，则$y_i(\boldsymbol {w\cdot x_i}+b)$yi​(w⋅xi​+b)大于1时函数没有受到惩罚，而$y_i(\boldsymbol {w\cdot x_i}+b)$yi​(w⋅xi​+b)小于1时函数受到了极致的惩罚，即加上了一个正无穷项，函数整体永远不可能取到最小值。所以第二步，我们执行min的命令，求解函数整体的最小值，我们就永远不能让必须取到正无穷的状况出现，即是说永远不让$y_i(\boldsymbol {w\cdot x_i}+b)<1$yi​(w⋅xi​+b)<1的状况出现，从而实现了求解最小值的同时让约束条件被满足。

现在， $L(w, b, \alpha)$L(w,b,α)就是我们新的损失函数了，我们的目标是要通过先最大化，在最小化它来求解参数向量$\boldsymbol w$w和截距$b$b的值。

将拉格朗日函数转换为拉格朗日对偶函数

要求极值，最简单的方法还是对参数求导后让一阶导数等于0。先来试试看对拉格朗日函数求极值，在这里我对参数向量$\boldsymbol w$w和截距$b$b分别求偏导并且让他们等于0：
$\begin{aligned} L(w, b, \alpha) &=\frac{1}{2}\|w\|^{2}-\sum_{i=1}^{N} \alpha_{i}\left(y_{i}\left(\boldsymbol{w} \cdot \boldsymbol{x}_{i}+b\right)-1\right) \\ &=\frac{1}{2}\|w\|^{2}-\sum_{i=1}^{N}\left(\alpha_{i} y_{i} \boldsymbol{w} \cdot \boldsymbol{x}_{i}+\alpha_{i} y_{i} b-\alpha_{i}\right) \\ &=\frac{1}{2}\|w\|^{2}-\sum_{i=1}^{N}\left(\alpha_{i} y_{i} \boldsymbol{w} \cdot \boldsymbol{x}_{i}\right)-\sum_{i=1}^{N} \alpha_{i} y_{i} b+\sum_{i=1}^{N} \alpha_{i} \\ &=\frac{1}{2}\left(\boldsymbol{w}^{T} \boldsymbol{w}\right)^{\frac{1}{2} \cdot 2}-\sum_{i=1}^{N}\left(\alpha_{i} y_{i} \boldsymbol{w} \cdot \boldsymbol{x}_{i}\right)-\sum_{i=1}^{N} \alpha_{i} y_{i} b+\sum_{i=1}^{N} \alpha_{i} \\ &=\frac{1}{2} \boldsymbol{w}^{T} \boldsymbol{w}-\sum_{i=1}^{N}\left(\alpha_{i} y_{i} \boldsymbol{w} \cdot \boldsymbol{x}_{i}\right)-\sum_{i=1}^{N} \alpha_{i} y_{i} b+\sum_{i=1}^{N} \alpha_{i} \end{aligned} \\ \begin{aligned} \frac{\partial L(\boldsymbol{w}, b, \alpha)}{\partial \boldsymbol{w}} &=\frac{1}{2} * 2 \boldsymbol{w}-\sum_{i=1}^{N} \alpha_{i} y_{i} \boldsymbol{x}_{i} \\ &=\boldsymbol{w}-\sum_{j=1}^{N} \alpha_{i} y_{i} \boldsymbol{x}_{i}=0 \rightarrow \boldsymbol{w}=\sum_{i=1}^{N} \alpha_{i} y_{i} \boldsymbol{x}_{i}\quad(1) \end{aligned} \\ \frac{\partial L(\boldsymbol{w}, b, \alpha)}{\partial b}=\sum_{i=1}^{N} \alpha_{i} y_{i}=0 \rightarrow \sum_{i=1}^{N} \alpha_{i} y_{i}=0\quad(2)$L(w,b,α)​=21​∥w∥2−i=1∑N​αi​(yi​(w⋅xi​+b)−1)=21​∥w∥2−i=1∑N​(αi​yi​w⋅xi​+αi​yi​b−αi​)=21​∥w∥2−i=1∑N​(αi​yi​w⋅xi​)−i=1∑N​αi​yi​b+i=1∑N​αi​=21​(wTw)21​⋅2−i=1∑N​(αi​yi​w⋅xi​)−i=1∑N​αi​yi​b+i=1∑N​αi​=21​wTw−i=1∑N​(αi​yi​w⋅xi​)−i=1∑N​αi​yi​b+i=1∑N​αi​​∂w∂L(w,b,α)​​=21​∗2w−i=1∑N​αi​yi​xi​=w−j=1∑N​αi​yi​xi​=0→w=i=1∑N​αi​yi​xi​(1)​∂b∂L(w,b,α)​=i=1∑N​αi​yi​=0→i=1∑N​αi​yi​=0(2)
由于两个求偏导结果中都带有未知的拉格朗日乘数$\alpha_i$αi​，因此还是无法求解出$\boldsymbol w$w和$b$b，我们必须想出一种方法来求解拉格朗日乘数$\alpha_i$αi​。幸运地是，拉格朗日函数可以被转换成一种只带有$\alpha_i$αi​，而不带有$\boldsymbol w$w和$b$b的形式，这种形式被称为拉格朗日对偶函数。在对偶函数下，我们就可以求解出拉格朗日乘数$\alpha_i$αi​，然后带入到上面推导出的(1)和(2)式中来求解$\boldsymbol w$w和$b$b。

当拉格朗日函数满足KKT(Karush-Kuhn-Tucker)条件时：
$\begin{aligned} \frac{\partial L}{\partial x_{i}} &=0, \forall_{i}=1,2, \ldots, d \\ h_{i}(x) & \leq 0, \forall_{i}=1,2, \ldots, q \\ \alpha_{i} & \geq 0, \forall_{i}=1,2, \ldots, q \\ \alpha_{i} h_{i}(x) &=0, \forall_{i}=1,2, \ldots, q \end{aligned}$∂xi​∂L​hi​(x)αi​αi​hi​(x)​=0,∀i​=1,2,…,d≤0,∀i​=1,2,…,q≥0,∀i​=1,2,…,q=0,∀i​=1,2,…,q​
存在一个拉格朗日对偶函数$g(\alpha)$g(α)，使得：
$\min_{x}L(x,\alpha) = \max_{\alpha}g(\alpha)$xmin​L(x,α)=αmax​g(α)
这里的条件其实都比较好理解。首先是所有参数的一阶导数必须为0，然后约束条件中的函数本身需要小于等于0，拉格朗日乘数需要大于等于0，以及约束条件乘以拉格朗日乘数必须等于0，即不同的取值下，两者之中至少有一个为0。当所有限制都被满足，则拉格朗日函数$L(x,\alpha)$L(x,α)的最优解与其对偶函数的最优解相等，我们就可以将原始的最优化问题转换成为对偶函数的最优化问题。而不难注意到，对于我们的损失函数$L(w, b, \alpha)$L(w,b,α)而言，KKT条件都是可以操作的。如果我们能够人为让KKT条件全部成立，我们就可以求解出$L(w, b, \alpha)$L(w,b,α)的对偶函数来解出$\alpha$α。

之前我们已经让拉格朗日函数上对参数w和b的求导为0，得到了式子：
$\begin{aligned} &\sum_{i=1}^{N} \alpha_{i j} x_{i}=w\\ &\sum_{i=1}^{N} \alpha_{i} y_{i}=0 \end{aligned}$​i=1∑N​αij​xi​=wi=1∑N​αi​yi​=0​
并且在我们的函数中，我们通过先求解最大值再求解最小值的方法使得函数天然满足：
$-\left(y_{i}\left(\boldsymbol{w} \cdot \boldsymbol{x}_{i}+b\right)-1\right) \leq 0\quad(3) \\ \alpha_{i} \geq 0\quad(4)$−(yi​(w⋅xi​+b)−1)≤0(3)αi​≥0(4)
所以接下来，我们只需要再满足一个条件：
$\alpha_{i}\left(y_{i}\left(\boldsymbol{w} \cdot \boldsymbol{x}_{i}+b\right)-1\right)=0\quad(5)$αi​(yi​(w⋅xi​+b)−1)=0(5)
这个条件其实很容易满足，能够让$y_i(\boldsymbol {w \cdot x_i}+b)-1=0$yi​(w⋅xi​+b)−1=0的就是落在虚线的超平面上的样本点，即我们的支持向量。所有不是支持向量的样本点则必须满足$\alpha_i=0$αi​=0。**满足这个式子说明了，我们求解的参数$\boldsymbol w$w和$b$b以及求解的超平面的存在，只与支持向量相关，与其他样本点都无关。**现在KKT的五个条件都得到了满足，我们就可以使用$L(w, b, \alpha)$L(w,b,α)的对偶函数来求解了。

首先让拉格朗日函数对参数$\boldsymbol w$w和$b$b求导后的结果为0，本质是在探索拉格朗日函数的最小值。然后：
$\begin{aligned} L(w, b, \alpha) &=\frac{1}{2}\|w\|^{2}-\sum_{i=1}^{N} \alpha_{i}\left(y_{i}\left(\boldsymbol{w} \cdot \boldsymbol{x}_{i}+b\right)-1\right) \\ &=\frac{1}{2}\|w\|^{2}-\sum_{i=1}^{N}\left(\alpha_{i} y_{i} \boldsymbol{w} \cdot \boldsymbol{x}_{i}\right)-\sum_{i=1}^{N} \alpha_{i} y_{i} b+\sum_{i=1}^{N} \alpha_{i} \\ &=\frac{1}{2}\|w\|^{2}-\boldsymbol{w} \sum_{i=1}^{N}\left(\alpha_{i} y_{i} \cdot \boldsymbol{x}_{i}\right)-b \sum_{i=1}^{N} \alpha_{i} y_{i}+\sum_{i=1}^{N} \alpha_{i} \end{aligned}$L(w,b,α)​=21​∥w∥2−i=1∑N​αi​(yi​(w⋅xi​+b)−1)=21​∥w∥2−i=1∑N​(αi​yi​w⋅xi​)−i=1∑N​αi​yi​b+i=1∑N​αi​=21​∥w∥2−wi=1∑N​(αi​yi​⋅xi​)−bi=1∑N​αi​yi​+i=1∑N​αi​​
代入式（1）和（2）：
$\begin{aligned} &=\frac{1}{2} \boldsymbol{w}^{T} \boldsymbol{w}-\boldsymbol{w}^{T} \boldsymbol{w}+\sum_{i=1}^{N} \alpha_{i}\\ &=-\frac{1}{2} \boldsymbol{w}^{T} \boldsymbol{w}+\sum_{i=1}^{N} \alpha_{i} \end{aligned}$​=21​wTw−wTw+i=1∑N​αi​=−21​wTw+i=1∑N​αi​​
再次代入（1）：
$=-\frac{1}{2} \sum_{i=1}^{N} \alpha_{i} y_{i} \boldsymbol{x}_{i}^{T} * \sum_{i=1}^{N} \alpha_{i} y_{i} \boldsymbol{x}_{i}+\sum_{i=1}^{N} \alpha_{i} \\ \begin{aligned} &=-\frac{1}{2} \sum_{i, j=1}^{N} \alpha_{i} y_{i} \boldsymbol{x}_{i}^{T} \alpha_{j} y_{j} \boldsymbol{x}_{j}+\sum_{i=1}^{N} \alpha_{i}\\ &=\sum_{i=1}^{N} \alpha_{i}-\frac{1}{2} \sum_{i, j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j} \boldsymbol{x}_{i}^{T} \boldsymbol{x}_{j} \end{aligned}$=−21​i=1∑N​αi​yi​xiT​∗i=1∑N​αi​yi​xi​+i=1∑N​αi​​=−21​i,j=1∑N​αi​yi​xiT​αj​yj​xj​+i=1∑N​αi​=i=1∑N​αi​−21​i,j=1∑N​αi​αj​yi​yj​xiT​xj​​
将矩阵相乘转换为内积形式：
$L_{d}=\sum_{i=1}^{N} \alpha_{i}-\frac{1}{2} \sum_{i, j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j} x_{i} \cdot x_{j}$Ld​=i=1∑N​αi​−21​i,j=1∑N​αi​αj​yi​yj​xi​⋅xj​
函数$L_d$Ld​就是我们的对偶函数。对所有存在对偶函数的拉格朗日函数我们有对偶差异如下表示：
$\Delta=\min _{x} L(x, \alpha)-\max _{\alpha} g(\alpha)$Δ=xmin​L(x,α)−αmax​g(α)
则对于我们的$L(w, b, \alpha)$L(w,b,α)和$L_d$Ld​，我们则有：
$\Delta=\min _{w, b} \max _{\alpha_{i} \geq 0} L(w, b, \alpha)-\max _{\alpha_{i} \geq 0} L_{d}$Δ=w,bmin​αi​≥0max​L(w,b,α)−αi​≥0max​Ld​
我们推导的第一步是对$L(w, b, \alpha)$L(w,b,α)求偏导并让偏导数都为0，所以我们求解对偶函数的过程其实是在求解$L(w, b, \alpha)$L(w,b,α)的最小值，所以我们又可以把公式写成：
$\begin{array}{l} \Delta= \min _{w, b} \max _{\alpha_{i} \geq 0} L(w, b, \alpha)-\max _{\alpha_{i} \geq 0} \min _{w, b} L(w, b, \alpha) \\ \quad \because \text {所有KKT条件被满足 } \\ \therefore \min _{w, b} \max _{\alpha_{i} \geq 0} L(w, b, \alpha)=\max _{\alpha_{i} \geq 0} \min _{w, b} L(w, b, \alpha) \end{array}$Δ=minw,b​maxαi​≥0​L(w,b,α)−maxαi​≥0​minw,b​L(w,b,α)∵所有KKT条件被满足 ∴minw,b​maxαi​≥0​L(w,b,α)=maxαi​≥0​minw,b​L(w,b,α)​
最终，我们的目标函数变化为：
$\max _{\alpha_{i} \geq 0}\left(\sum_{i=1}^{N} \alpha_{i}-\frac{1}{2} \sum_{i, j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j} x_{i} \cdot x_{j}\right)$αi​≥0max​(i=1∑N​αi​−21​i,j=1∑N​αi​αj​yi​yj​xi​⋅xj​)

求解拉格朗日对偶函数极其后续过程

到了这一步，我们就需要使用梯度下降，SMO或者二次规划(QP，quadratic programming)来求解我们的，数学的难度又进一步上升。这一过程对数学的要求已经远远超出了我们需要的程度。

一旦我们求得了$\alpha$α值，我们就可以使用求导后得到的(1)式求解$\boldsymbol w$w，并可以使用(1)式和决策边界的表达式结合，得到下面的式子来求解$b$b：
$\sum_{i=1}^{N} \alpha_{i} y_{i} \boldsymbol{x}_{i} * x+b=0$i=1∑N​αi​yi​xi​∗x+b=0
当求得特征向量$\boldsymbol w$w和$b$b，我们就得到了我们的决策边界的表达式，也就可以利用决策边界和其有关的超平面来进行分类了，我们的决策函数就可以被写作：
$f\left(x_{t e s t}\right)=\operatorname{sign}\left(\boldsymbol{w} \cdot \boldsymbol{x}_{t e s t}+b\right)=\operatorname{sign}\left(\sum_{i=1}^{N} \alpha_{i} y_{i} \boldsymbol{x}_{i} \cdot \boldsymbol{x}_{t e s t}+b\right)$f(xtest​)=sign(w⋅xtest​+b)=sign(i=1∑N​αi​yi​xi​⋅xtest​+b)
其中$x_{test}$xtest​是任意测试样本，$sign(h)$sign(h) 是$h>0$h>0时返回1，$h<0$h<0时返回-1的符号函数。