回忆逻辑回归，概率 $p(y=1|x; \theta)$ 由 $h_\theta(x) = g(\theta^Tx)$ 计算而得。如果 $h_\theta(x) \geq 0.5$，则我们预测输入 $x$ 为正类，换言之，当且仅当 $\theta^Tx \geq 0$ 时，模型预测 $x$ 为正类。并且，根据我们的概率假设，$\theta^Tx$ 越大，$x$ 取正类的概率就越大，或者说，我们对于预测 $x$ 为正类的信心就越大。
也就是说，如果 $\theta^Tx \gg 0$，那么我们可以非常自信地预测 $y=1$。类似的，如果 $\theta^Tx \ll 0$，则我们可以非常自信地预测 $y=0$。直觉上看，如果我们的成本函数考虑这一点，那么我们可以得到一个不错的分类器。对此，稍后我们将会引入函数间隔的概念。
换一种思路来看，$\theta^Tx=0$ 代表决策边界（也称为分割超平面 separating hyperplane），离决策边界越远的点，我们对准确预测其分类的信心越大。直觉上看，在数据集线性可分的前提下，在所有决策边界集合中，使得样本点尽可能远离的决策边界，通常代表着更好的模型。对此，稍后我们会引入几何间隔的概念。
对于支持向量机，我们将引入和广义线性模型所不同的符号来阐述二元分类问题。给定标签 $y$ 和特征 $x$，令 $y \in \{-1, 1\}$（而不是 $\{0, 1\}$），同时我们不再使用 $\theta$ 作为参数向量，而是使用 $w, b$ 来描述分类器 $$ h_{w, b}(x) = g(w^Tx + b) $$
这里，当 $z \geq 0$ 时，$g(z)=1$，否则 $g(z) = -1$。$w, b$ 的记号，使我们将截距项 $b$ 从其它参数独立出来，从而我们也不需要再假定 $x_0=1$，因而这里 $x$ 是 $n$ 维向量，而不是 $n+1$ 维向量。也就是说，$b$ 就是之前的 $\theta_0$，而 $w$ 是之前的 $[\theta_1...\theta_n]^T$
注意到，根据我们对 $g$ 的上述定义，我们的分类器将直接预测 $1$ 或 $-1$（类比感知器），而不再需要和逻辑回归一样，必须包含预测 $y=1$ 的概率这个中间步骤。
给定一个训练样本 $(x^{(i)}, y^{(i)})$，定义该训练样本 $(w, b)$ 的函数间隔 functional margin为 $$ \hat{\gamma}^{(i)} = y^{(i)}(w^Tx+b) $$
注意到，如果 $y^{(i)}=1$，要使函数间隔更大（也即使我们的预测更有信心更准确），则需要 $w^Tx+b$ 是一个非常大的正数。相反，如果 $y^{(i)}=-1$，要使函数间隔更大，则需要 $w^Tx+b$ 是一个（绝对值）非常大的负数。另外，当 $y^{(i)}(w^Tx+b) > 0$ 时，我们对这个训练样本的预测是准确的。因此，一个非常大的函数间隔，同时代表着高置信度以及正确的分类。
对于上述给定的线性分类器 $g$ （取值范围为 $\{-1, 1\}$），函数间隔的一个特性使其并不能成为置信度的很好测量指标。考虑如下情况：将 $w$ 替换为 $2w$，$b$ 替换为 $2b$，由于 $g(w^Tx+b)=g(2w^Tx+2b)$，分类结果 $h_{w,b}(x)$ 将保持不变。然而，这个时候函数间隔扩大了两倍。换言之，我们可以同比例地扩大参数 $w, b$，从而以任意倍数扩大函数间隔，但这个操作对分类器本身的效果而言，不带来任何变化。从直觉上看，我们应该对参数做归一化操作，使得 $||w||_2=1$，替换 $(w,b)$ 为 $(\frac{w}{||w||_2}, \frac{b}{||w||_2})$，在此基础上，再计算函数间隔。之后我们将会回到这个问题。
给定一个训练集，我们定义训练集 $S$ 的函数间隔为所有单个训练样本的函数间隔的最小值，即 $$ \hat{\gamma} = \min_{i=1,...,m}\hat{\gamma}^{(i)} $$
接下来，考虑几何间隔 geometric margin
注意到，向量 $w$ 和分割超平面总是正交的，考虑处于正类的点 $A$，其特征为 $x^{(i)}$，标签为 $y^{(i)}=1$，假设点 $A$ 到决策边界的距离为 $\gamma^{(i)}$，相交点为 $B$。
这里 $\frac{w}{||w||}$ 是 $w$ 方向的单位向量，点 $A$ 可以用向量 $x^{(i)}$ 表示。因此点 $B$ 就是 $x^{(i)} - \gamma^{(i)} \cdot \frac{w}{||w||}$，由于点 $B$ 处于决策边界上，满足 $w^Tx+b=0$，因此 $$ w^T(x^{(i)}-\gamma^{(i)}\frac{w}{||w||})+b=0 $$ 解方程得 $$ \gamma^{(i)} = \frac{w^Tx^{(i)}+b}{||w||} = (\frac{w}{||w||})^Tx^{(i)} + \frac{b}{||w||} $$
这是正类的情况，对于正类和反类的情况 $$ \gamma^{(i)} = y^{(i)}((\frac{w}{||w||})^Tx^{(i)} + \frac{b}{||w||}) $$
注意到，$\frac{\hat{\gamma}}{||w||}=\gamma$，当 $||w||=1$ 时，函数间隔等于几何间隔。并且，几何间隔不会受到参数扩大缩小的影响。也即是说，我们可以按任意约束对 $w, b$ 进行缩放，而不改变几何间隔。
最后，给定一个训练集，我们同样定义训练集 $S$ 的几何间隔为所有单个训练样本的几何间隔的最小值，即 $$ \gamma = \min_{i=1,...,m}\gamma^{(i)} $$
根据上述对间隔的讨论，我们希望找到一条最大化（几何）间隔的决策边界，这样的决策边界同时保证了分类的正确性和置信度，它会尽可能地远离正类和反类。
这里，我们暂且假定数据集线性可分，为了最大化几何间隔，我们引入以下优化问题： $$ \begin{split} & \max_{\gamma, w, b} \gamma \\ & s.t. y^{(i)}\frac{w^Tx^{(i)}+b}{||w||} = y^{(i)}(w^Tx^{(i)}+b) \geq \gamma, i=1,...,m \\ & ||w||=1 \end{split} $$
也就是说，给定约束条件 $||w||=1$ （从而函数间隔等于几何间隔），且所有训练样本的函数间隔大于等于 $\gamma$，也即几何间隔大于等于 $\gamma$，我们要想找到最大的 $\gamma$。解这个优化问题求得的 $(w, b)$ 就保证了针对训练集的最大几何间隔。
如果上述优化问题可解，则我们已经获得了最大间隔分类器。但由于 $||w||=1$ 是一个非凸约束，标准的优化软件无法对其求解。因此，我们试着对优化问题做一定的转换： $$ \begin{split} & \max_{\gamma, w, b} \frac{\hat{\gamma}}{||w||} \\ & s.t. y^{(i)}(w^Tx^{(i)}+b) \geq \hat{\gamma}, i=1,...,m \\ \end{split} $$
这里，我们的优化目前是函数间隔除以权重的模，根据之前的定义，等于几何间隔，也即优化目标不变。而约束条件为所有训练样本的函数间隔大于等于 $\hat{\gamma}$。这样，我们去除了 $||w||=1$ 的非凸约束，但是得到了非凸优化目标。目前依然没有求解的现成方法。
我们需要对这个优化问题做进一步转换。注意上一节提到过，我们可以按任意约束对 $w, b$ 进行缩放，而不改变几何间隔（也就不改变模型，但是会改变函数间隔）。引入约束函数间隔等于 $1$ $$ \hat{\gamma}=1 $$ 从而，上面的优化目标 $\frac{\hat{\gamma}}{||w||}=\frac{1}{||w||}$，而最大化 $\frac{1}{||w||}$ 等价于最小化 $||w||^2$，于是我们得到下列优化问题： $$ \begin{split} & \min_{\gamma,w,b}\frac{1}{2}||w||^2 \\ & s.t. y^{(i)}(w^Tx^{(i)}+b) \geq 1, i=1,...,m \\ \end{split} $$
这个问题是线性约束下凸二次函数的优化，利用一些二次规划（Quadratric Programming）的软件，可以有效求解。求解得到的结果，就是最大间隔分类器。（由于有约束条件的存在，通常不会用梯度下降类似的方法来解条件极值的问题）
为了从凸优化的角度来理解最大间隔分类器，我们先介绍条件极值的问题。考虑以下问题： $$ \begin{split} & \min_{w}f(w) \\ & s.t. \, h_i(w)=0, i=1,...,l \\ \end{split} $$ 这个问题在多元函数微分学中，通常使用拉格朗日乘数法求解，上面这个问题对应的拉格朗日函数 Lagrangian为 $$ L(w,b) = f(w) + \sum_{i=1}^l \beta_i h_i(w) $$ $\beta_i$ 被称为拉格朗日乘子，使拉格朗日函数的偏导为0： $$ \frac{\partial L}{\partial w_i} = 0; \, \frac{\partial L}{\partial \beta_i}=0 $$ 求解 $w$ 和 $\beta$ 即可。
本节，我们将推广条件极值求解问题到约束条件允许包含不等式的情况。考虑以下优化问题，我们称之为原问题 primal problem： $$ \begin{split} & \min_{w}f(w) \\ & s.t. \, g_i(w) \leq 0, i=1,...,k \\ & h_i(w)=0, i=1,...,l \\ \end{split} $$ 我们定义广义拉格朗日函数 Generalized Lagrangian $$ L(w,\alpha,\beta) = f(w) + \sum_{i=1}^k \alpha_i g_i(w) + \sum_{i=1}^l \beta_i h_i(w) $$ 这里，$\alpha_i$ 和 $\beta_i$ 为拉格朗日乘子。考虑下面这个值 $$ \theta_p(w) = \max_{\alpha, \beta: \alpha_i \geq 0}L(w,\alpha,\beta)$$ 当给定 $w$ 时，如果 $w$ 没能满足原问题的约束（比如对某个 $i$， $g_i(w)>0$ 或 $h_i(w) \neq 0$），那么 $$ \begin{split} \theta_p(w) &= \max_{\alpha, \beta: \alpha_i \geq 0}f(w) + \sum_i^k \alpha_i g_i(w) + \sum_i^l \beta_i h_i(w) \\ &= \infty \end{split} $$ 相反，当约束条件均满足时，$\theta_p(w) = f(w)$，所以 $$ \theta_p(w) = \left\{ \begin{aligned} & f(w) &如果w满足约束 \\ & \infty & w不满足约束 \end{aligned} \right. $$ 也就是说，对于所有满足约束的 $w$ 来说，$\theta_p$ 的值和我们目标函数的值一致，否则就取正无穷。从而，考虑下面这个最优化问题 $$ \min_w \theta_p(w) = \min_w {\max_{\alpha,\beta:\alpha \geq 0}L(w,\alpha,\beta)} $$ 易知这个问题和原问题是相同的。我们将该问题的最优值记为 $p^* = \min_w \theta_p(w)$，也就是原问题的最优值。
接下来我们看一个不同的问题。定义 $$ \theta_D(\alpha, \beta) = \min_w L(w,\alpha,\beta) $$ 对于 $\theta_p$，我们优化的参数是 $\alpha, \beta$，而对于 $\theta_D$，我们优化的参数是 $w$。于是我们可以提出这个对偶问题 dual problem： $$ \max_{\alpha,\beta: \alpha_i \geq 0}\theta_D(\alpha,\beta) = \max_{\alpha,\beta: \alpha_i \geq 0} \min_w L(w,\alpha, \beta) $$
除去求最大值和最小值的顺序之外，原问题和对偶问题是完全相同的。我们假定对偶问题的最优值为 $d^* = \max_{\alpha,\beta: \alpha_i \geq 0} \theta_D(w)$，易知： $$ d^* = \max_{\alpha,\beta: \alpha_i \geq 0} \min_w L(w,\alpha, \beta) \leq \min_w {\max_{\alpha,\beta:\alpha \geq 0}L(w,\alpha,\beta)} = p^* $$ 在某种条件满足的情况下，有 $$ d^* = p^* $$ 这时，我们可以通过解对偶问题来解原问题。
而原问题和对偶问题相等的条件为：假设 $f$ 和 $g_i$ 都是凸函数，$h_i$ 远交（affine），$g_i$ 是可行约束。
在上述条件满足时，必定存在 $w^*, \alpha^*, \beta^*$ 使得 $w^*$ 是原问题的解，$\alpha^*, \beta^*$ 是对偶问题的解，同时 $p^* = d^* = L(w^*, \alpha^*, \beta^*)$。并且，$w^*, \alpha^*, \beta^*$ 满足 KKT条件 Karush-Kuhn-Tucker条件： $$ \begin{split} \frac{\partial}{\partial w_i} L(w^*, \alpha^*, \beta^*) &= 0, i=1,...,n \\ \frac{\partial}{\partial \beta_i} L(w^*, \alpha^*, \beta^*) &= 0, i=1,...,l \\ \alpha^*_i g_i(w^*) &= 0, i=1,...,k \\ g_i(w^*) &\leq 0,i=1,...,k \\ \alpha^* &\geq 0,i=1,...,k \end{split} $$ 逆命题也是成立的，如果 $w^*, \alpha^*, \beta^*$ 满足KKT条件，则它们一定分别是原问题和对偶问题的解。
$\alpha^*_i g_i(w^*) = 0$ 也称为对偶互补约束 dual complementarity condition，这个约束满足意味着，如果 $\alpha_i^* > 0$，则 $g_i(w^*) = 0$。这个特性后面会用于证实，支持向量机只有少数几个支持向量。当介绍SMO算法时，对偶互补约束也会用于给出收敛测试。
对于最大间隔分类器，我们的原问题是 $$ \begin{split} & \min_{\gamma,w,b}\frac{1}{2}||w||^2 \\ & s.t. y^{(i)}(w^Tx^{(i)}+b) \geq 1, i=1,...,m \\ \end{split} $$ 其中，约束条件可以写成 $$ g_i(w) = -y^{(i)}(w^Tx^{(i)}+b)+1 \leq 0 $$ 每一个训练样本，都有这样一个约束。注意到，根据KKT条件的对偶互补约束，只有函数间隔正好等于 $1$ 的训练样本，其 $\alpha_i > 0$ （也就是说，约束条件是等值约束，$g_i(w)=0$）。而其它训练样本的函数间隔均大于 $1$，其对应的 $\alpha_i = 0$。
而函数间隔最小的点，也是离决策边界最近的点，只有这几个最近的点的 $\alpha_i$ 非零。这些点叫做支持向量 support vectors。支持向量的数量远小于训练集的总样本数，后面我们会用到这个特性。
接下来，我们将研究这个特定问题的对偶问题。其中一个关键的要素，在于把算法写成输入特征空间内积 $<x^{(i)}, x^{(j)}>（即(x^{(i)})^Tx^{(j)}）$的函数，这在后边将会应用于核方法。
构造拉格朗日函数 $$ L(w,b,\alpha) = \frac{1}{2}||w||^2 - \sum_{i=1}^m \alpha_i[y^{(i)}(w^Tx^{(i)}+b)-1] $$ 注意到，因为约束条件只包含不等式，这里的拉格朗日乘子只有 $\alpha_i$ 而没有 $\beta_i$ 。
对于对偶问题，首先需要针对固定的 $\alpha$，找到$w$ 和 $b$，使 $\theta_D = \min_{w, b}L(w, b, \alpha)$ 取得最小值。令 $L$ 对 $w$ 和 $b$ 的偏导分别为零，得到 $$ \nabla_wL(w,b,\alpha) = w - \sum_{i=1}^m \alpha_iy^{(i)}x^{(i)} = 0 $$ 也即 $$ w=\sum_{i=1}^m \alpha_iy^{(i)}x^{(i)} $$ 而对于 $b$ 求偏导，得 $$ \nabla_bL(w,b,\alpha) = \sum_{i=1}^m \alpha_iy^{(i)} = 0 $$
将这两个结果，代入回拉格朗日函数，并化简，得到 $$ L(w,b,\alpha) = W(\alpha) = \sum_{i=1}^m\alpha_i - \frac{1}{2}\sum_{i,j=1}^my^{(i)}y^{(j)}\alpha_i\alpha_j(x^{(i)})^Tx^{(j)} $$
于是我们得到了对偶问题 $$ \begin{split} \max_{\alpha} & W(\alpha) = \sum_{i=1}^m\alpha_i - \frac{1}{2}\sum_{i,j=1}^my^{(i)}y^{(j)}\alpha_i\alpha_j(x^{(i)})^Tx^{(j)} \\ s.t. \, & \alpha_i \geq 0, i=1,...,m \\ & \sum_{i=1}^m \alpha_iy^{(i)} = 0 \end{split} $$
可以证实，在这个问题中，KKT条件是满足的，从而 $p^* = d^*$。可以直接解对偶问题来替代原问题。注意到，对偶问题的优化参数是 $\alpha_i$，后面我们会介绍求解的具体算法，当我们解出 $\alpha_i$ 之后，我们可以根据之前求的偏导，计算出 $w^*$。而再回到原问题，截距项 $b$ 也可以求出 $$ b^* = -\frac{\max_{i:y^{(i)}=-1}{w^*}^Tx^{(i)} + \min_{i:y^{(i)}=1}{w^*}^Tx^{(i)}}{2} $$
再观察一下拉格朗日函数关于 $w$ 的偏导，这是一个 $w$ 关于 $\alpha$ 的函数。假设我们已经训练好了模型，希望对于一个新输入 $x$ 做出预测，可以计算 $w^T+b$ 的值，但注意到 $$ \begin{split} w^T+b &= (\sum_{i=1}^m \alpha_iy^{(i)}x^{(i)})^Tx +b \\ &= \sum_{i=1}^m \alpha_iy^{(i)}<x^{(i)}, x> + b \end{split} $$ 所以，如果我们已经求出 $\alpha_i$，剩下的只需要再计算 $x$ 和训练集中所有点的内积。而前面提到，除去支持向量外，训练集其它样本的 $\alpha_i$ 均等于零。实际上，我们只需要计算 $x$ 和支持向量的内积即可。
通过将原优化问题转为对偶问题，我们已经能够将整个算法写作输入特征向量的内积。下一节，利用这个特性，引入核方法，最终得到的支持向量机 support vector machines算法，将可以高效地在高维空间内学习。
在讨论线性回归时，面对一元变量 $x$，我们有时会考虑使用特征 $x, x^2, x^3$ 来获得一个三次函数进行拟合。这里，我们将原始输入称为输入属性 input attributes，而将处理后的输入称为输入特征 input features，而我们用 $\phi$ 来表示将输入属性转换为输入特征的特征映射 feature mapping。比如，在刚才的例子中： $$ \phi(x)=\begin{bmatrix} x \\ x^2 \\ x^3 \\ \end{bmatrix} $$
有时，比起原始的输入属性 $x$，我们更希望使用输入特征 $\phi(x)$ 来训练支持向量机。
只需要将之前的算法中所有的 $x$ 替换为 $\phi(x)$ 即可，由于我们的算法完全可以用内积 $<x, z>$ 来表示，这意味着算法可以表示为 $<\phi(x), \phi(z)>$ 的函数。具体来说，给定一个特征映射 $\phi$，我们定义对应的核函数 Kernel为 $$ K(x,z)=\phi(x)^T\phi(z) $$ 这样，我们的算法将使用新的输入特征来进行学习。
正常流程下，我们可以轻易地计算出 $\phi(x)$ 和 $\phi(z)$，然后再求它们的内积得到 $K(x,z)$。但核方法引人入胜之处在于，$\phi(x)$ 可能由于维度较高，计算的代价非常昂贵，在这个前提下，我们可以不需要显式地计算 $\phi(x)$，非常高效地计算出 $K(x,z)$。
看个例子，假设 $x,z \in \mathbb{R}^n$，考虑 $$ \begin{split} K(x,z) &= (x^Tz)^2 \\ &= (\sum_{i=1}^n x_iz_i)(\sum_{i=j}^n x_jz_j) \\ &= \sum_{i=1}^n\sum_{j=1}^n x_ix_jz_iz_j \\ &= \sum_{i,j=1}^n (x_ix_j)(z_iz_j) \end{split} $$ 从而，$K(x,z) = \phi(x)^T\phi(z)$，考虑到 $n=3$ 时，$\phi$ 就是： $$ \phi(x) = \begin{bmatrix} x_1x_1 \\ x_1x_2 \\ x_1x_3 \\ x_2x_1 \\ x_2x_2 \\ x_2x_3 \\ x_3x_1 \\ x_3x_2 \\ x_3x_3 \\ \end{bmatrix} $$
直接计算高维度的 $\phi(x)$ 需要 $O(n^2)$ 的时间，而直接计算 $K(x,z)$ 仅需要 $O(n)$ 的时间。
另一个相关的核函数是 $$ \begin{split} K(x,z) &= (x^Tz+c)^2 \\ &= \sum_{i,j=1}^n (x_ix_j)(z_iz_j) + \sum_{i=1}^n (\sqrt{2c}x_i)(\sqrt{2c}z_i) + c^2 \end{split} $$ 其对应的特征映射为（依然以 $n=3$ 为例）： $$ \phi(x) = \begin{bmatrix} x_1x_1 \\ x_1x_2 \\ x_1x_3 \\ x_2x_1 \\ x_2x_2 \\ x_2x_3 \\ x_3x_1 \\ x_3x_2 \\ x_3x_3 \\ \sqrt{2c}x_1 \\ \sqrt{2c}x_2 \\ \sqrt{2c}x_3 \\ c \end{bmatrix} $$ 其中参数 $c$ 控制 $x_i$（一阶）和 $x_ix_j$（二阶）项的相对权重。
更广义地看，核函数 $K(x,z)=(x^Tz+c)^d$ 对应着到 $\binom{n+d}{d}$ 特征空间的特征映射，特征空间中的每一项为 $x_{i_1},x_{i_2},...,x_{i_k} $ 一直到 $n$ 阶的所有单项式。尽管特征空间是 $O(n^d)$ 维，计算 $K(x,z)$ 依然只花费 $O(n)$ 的时间，因此，我们从来不显式地表示非常高维度的特征空间。
接下来，我们考虑另一种核函数。直觉上看，如果 $\phi(x)$ 和 $\phi(z)$ 非常接近，我们会希望 $K(x,z)=\phi(x)^T\phi(z)$ 非常大。相反地，如果 $\phi(x)$ 和 $\phi(z)$ 相互远离，或者比如说接近正交，那么 $K(x,z)=\phi(x)^T\phi(z)$ 比较小会比较好。所以我们可以认为 $K(x,z)$ 是 $\phi(x)$ 和 $\phi(z)$ 相似性的度量。
出于上述的考虑，我们可以选择 $$ K(x,z) = exp(-\frac{||x-z||^2}{2\sigma^2}) $$ 当 $x,z$ 比较接近时，$K \rightarrow 1$；当 $x,z$ 远离时，$K \rightarrow 0$。使用这个 $K$ 作为SVM的核函数，这时的特征映射 $\phi$ 将 $x$ 投射到了无限维度的空间，而这个核函数称为高斯核。
不过新的问题是，给定一个函数 $K$，如何判定这个函数是不是一个核函数？换言之，是否存在一个特征映射 $\phi$ 使得 $K(x,z)=\phi(x)^T\phi(z)$ 对所有 $x,z$ 成立？
我们首先假设 $K$ 是一个核函数。考虑 $m$ 个有限点集 $\{x^{(1)},...,x^{(m)}\}$，构造一个 $m \times m$ 的方阵 $K$ 使得 $K_{ij}=K(x^{(i)}, x^{(j)})$。这个矩阵称为核函数矩阵 Kernel matrix。由于显而易见的关联，这里我们重载了符号 $K$ 使其同时表示核函数以及核函数矩阵。
如果 $K$ 是一个核函数，那么 $K_{ij}=K(x^{(i)}, x^{(j)})=\phi(x^{(i)})^T\phi(x^{(j)})=\phi(x^{(j)})^T\phi(x^{(i)})=K(x^{(j)}, x^{(i)})=K_{ji}$，因此 $K$ 必然是对称矩阵。此外，还可以证明，$K$ 是半正定矩阵。根据Mercer定理，K是对称半正定矩阵是K为核函数的充分必要条件。
最后，值得提出的一点是，尽管核方法常常与支持向量机放在一起使用，但只要你的学习算法能够表示为输入向量的点积，就可以利用核方法将输入属性高效地投射到高维空间。
目前，关于支持向量机的推导，我们都假定数据是线性可分的。通过 $\phi$ 将数据投射到高维空间当然会增加数据可分的似然性，但投射过程并不能完全保证这一点。另外，目标仅仅是找到分割超平面也不一定是我们所希望的，强制要求找到分割超平面，可能会使算法更容易收到异常点的影响，从而导致更小的间隔。
为了让我们的算法对非线性可分的数据集可用，同时不易受到异常点的影响，我们使用 $L1$ 正则化，来改进优化问题如下：
$$ \begin{split} & min_{\gamma,w,b} \frac{1}{2}||w||^2 + C\sum_{i=1}^m \xi_i \\ s.t. & y^{(i)}(w^Tx^{(i)}+b) \geq 1-\xi_i, i=1,...,m \\ & \xi_i \geq 0, i=1,...,m \end{split} $$这样，训练样本的函数间隔允许小于 $1$，如果某个训练样本的函数间隔是 $1-\xi_i$，目标函数则会增加 $C\xi_i$。参数 $C$ 控制着 $||w||^2$ 尽可能大（从而函数间隔小）以及绝大多数训练样本的函数间隔大于 $1$ 这两个目标之间的相对权重。
此时的拉格朗日函数为 $$ L(w,b,\xi,\alpha,r) = \frac{1}{2}w^Tw + C\sum_{i=1}^m\xi_i - \sum_{i=1}^m\alpha_i[y^{(i)}(x^Tw+b)-1+\xi_i] - \sum_{i=1}^m r_i\xi_i $$
这里，$\alpha_i$ 和 $r_i$ 是拉格朗日乘子。令拉格朗日函数对 $w$ 和 $b$ 的偏导为零，代入回函数，可以得到如下对偶问题： $$ \begin{split} & \max_\alpha W(\alpha) = \sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{i,j=1}^m y^{(i)}y{(j)}\alpha_i\alpha_j<x^{(i)},x^{(j)}> \\ s.t. & 0 \leq \alpha_i \leq C, i=1,...,m \\ & \sum_{i=1}^m \alpha_iy^{(i)} = 0 \end{split} $$
求得 $\alpha_i$ 之后，可以相应地求得 $w$ 和 $b^*$。
同时，KKT对偶互补约束为 $$ \begin{split} \alpha_i=0 &\Rightarrow y^{(i)}(w^Tx^{(i)}+b) \geq 1 \\ \alpha_i=C &\Rightarrow y^{(i)}(w^Tx^{(i)}+b) \leq 1 \\ 0 < \alpha_i < C &\Rightarrow y^{(i)}(w^Tx^{(i)}+b) = 1 \\ \end{split} $$
这样，放宽了线性可分的假定。最后剩下的就是解出对偶问题。
John Platt发明的SMO算法，能够高效地解出SVM对偶问题。在介绍SMO算法之前，作为启发，我们先简单介绍坐标上升法。
考虑解下列这个非约束优化问题 $$ \max_{\alpha}W(\alpha_1,\alpha_2,...,\alpha_m) $$ 这里，$W$ 是关于 $\alpha_i$ 的函数，我们先忽略这个问题和SVM的关联。之前，我们已经学习过两种优化算法，梯度下降和牛顿法。而这里我们将考虑的算法叫做坐标上升法 coordinate ascent，重复以下过程直至收敛: $$ \alpha_i = arg\max_{\hat{\alpha}_i}W(\alpha_1,...,\alpha_{i-1},\hat{\alpha}_i,\alpha_{i+1},...,\alpha_m), for\,i=1,...,m $$
因此，在最内层的循环中，我们保持除 $\alpha_i$ 外的其它 $\alpha$ 不变，只针对 $\alpha_i$ 这单个参数优化 $W$。在上面这个版本的坐标上升中，我们按照顺序重复更新各个 $\alpha$ 直至收敛，$\alpha$ 的顺序也可以根据一定的策略变更。
只要 $W$ 能够高效地做 $arg\max$ 运算，坐标上升法就会有一个不错的效率。但通常而言，坐标上升的迭代次数远多于牛顿法。
再次列出我们需要求解的对偶问题 $$ \begin{split} & \max_\alpha W(\alpha) = \sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{i,j=1}^m y^{(i)}y{(j)}\alpha_i\alpha_j<x^{(i)},x^{(j)}> \\ s.t. & 0 \leq \alpha_i \leq C, i=1,...,m \\ & \sum_{i=1}^m \alpha_iy^{(i)} = 0 \end{split} $$
假定我们有一组 $\alpha$ 满足上述两个约束。现在，如果我们保持 $\alpha_2,...,\alpha_m$ 不变，使用坐标上升法，针对参数 $\alpha_1$ 优化目标函数，这个方案是行不通的，因为约束条件已经保证了 $$ \alpha_1y^{(1)} = -\sum_{i=2}^m \alpha_iy^{(i)} $$ 或者，对上式两边同时乘以 $y^{(i)}$，可以得到 $$ \alpha_1 = -y^{(1)}\sum_{i=2}^m \alpha_iy^{(i)} $$ （由于 $y^{(1)} \in \{-1,1\}$，因此 $(y^{(1)})^2 = 1$），所以 $\alpha_1$ 的值是由其余 $\alpha_i$ 确定的。如果我们保持 $\alpha_2,...,\alpha_m$ 不变，在保证约束满足的前提下，$\alpha_1$ 也不能变。
因此，要更新 $\alpha_i$ 并同时保证约束条件满足，我们需要至少同时改变两个 $\alpha_i$，从而有了SMO算法。重复以下步骤直至收敛：
SMO之所以高效，是因为 $\alpha_i$ 和 $\alpha_j$ 的计算过程十分高效。为了方便起见，我们假定待更新的一组 $\alpha_i, \alpha_j$ 为 $\alpha_1$ 和 $\alpha_2$，而 $\alpha_3,...,\alpha_m$ 保持不变。优化 $W(\alpha)$ 的同时保持约束条件满足，有 $$ \alpha_1y^{(1)} + \alpha_2y^{(2)} = -\sum_{i=3}^m \alpha_iy^{(i)} $$ 考虑到等式右边的值是确定的，暂且将其记为 $\zeta$： $$ \alpha_1y^{(1)} + \alpha_2y^{(2)} = \zeta $$ $\alpha_1$ 和 $\alpha_2$ 一定落在上述这条直线上。于此同时，另一个约束条件要求 $\alpha_1$ 和 $\alpha_2$ 还必须落在 $[0, C] \times [0, C]$ 的区域内。换言之，对于所有满足依赖的 $\alpha_1$ 和 $\alpha_2$，都存在对于 $\alpha_2$ 的上限 $H$ 和下限 $L$。
将 $\alpha_1$ 写成关于 $\alpha_2$ 的函数： $$ \alpha_1 = (\zeta - \alpha_2y^{(2)})y^{(1)} $$ 从而： $$ W(\alpha_1, \alpha_2, ..., \alpha_m) = W((\zeta - \alpha_2y^{(2)})y^{(1)}, \alpha_2,..., \alpha_m) $$ 由于 $\alpha_3,...,\alpha_m$ 都是常数项，实际上这里就成为了关于 $\alpha_2$ 的二次方程。换句话说，方程可以表达为 $a\alpha^2+b\alpha+c$ 的形式。不考虑约束，我们可以轻易地求得使方程最大化的 $\alpha_2^{new,unclipped}$，而考虑约束时，有： $$ \alpha_2^{new} = \left\{ \begin{aligned} &H & if \alpha_2^{new,unclipped} > H \\ &\alpha_2^{new,unclipped} & if L \leq \alpha_2^{new,unclipped} \leq H \\ &L & if \alpha_2^{new,unclipped} < L \\ \end{aligned} \right. $$
有了 $\alpha_2^{new}$，就可以计算 $\alpha_1^{new}$。更多的细节，比如如何经验性地选择待更新的 $\alpha_i, \alpha_j$，以及随着SMO算法的执行，如何更新 $b$，可以参见Platt的论文。
In [ ]: