第04章：深入浅出ML之Kernel-Based家族
- author: zhouyongsdzh@foxmail.com
- date: 2015-11-12
- weibo: @周永_52ML
内容列表
- 写在前面
- 对偶优化问题
- 核方法
- 支持向量机
写在前面
机器学习中有这样一个结论：低维空间线性不可分的数据通过非线性映射到高维特征空间则可能线性可分。极端地，假设数据集中有\(m\)个样本，一定可以在\(m-1\)维空间中线性可分。
每一个样本在特征空间中对应一个点，试想一下，2个点可以用一维空间分开；3个点可以在2维空间（平面）上线性可分；… ；\(m\)个点，可以在\(m-1\)维空间中线性可分。
高维空间可以让样本线性可分，这固然是优点。但是如果直接采用非线性映射技术在高维空间进行一个学习任务（如分类或回归），则需要确定非线性映射函数的形式和参数、高维特征空间维数等问题；而最大的问题在于在高维特征空间运算时可能存在的“维数灾难“。How to solve it?
本章要介绍的核函数方法可以有效地解决这类问题。这里先给出核函数工作的基本思路：
设样本集\(X\)（\(X \in R^k\)）中有两条样本\(x和z\)，非线性函数\(\phi\)实现输入空间\(R^k\)到特征空间\(R^n\)的映射（即\(\phi(z) \in R^n\)），\( k << n\)。核函数公式：
$$
k(x,z) = <\phi(x), \phi(z)>
$$其中，
< , >表示内积计算，\(k(x,z)\)为核函数。
从上式可以看出，核函数将\(n\)维高维特征空间的内积计算转化为\(k\)维低维输入空间的核函数计算，巧妙地解决了在高维特征空间中计算可能出现的“维数灾难”等问题。从而为高维特征空间解决复杂的学习问题奠定了理论基础。
本章的安排是这样。首先介绍一些对偶优化问题的基本形式，引出核函数并且为后面的SVM做铺垫；然后给出核函数的发展、常用的核函数等方法；最后详细介绍核函数在分类方法中的经典应用－支持向量机。
对偶优化问题
我们都知道，机器学习模型参数学习过程，大多要通过《最优化算法》中的一些方法来求解。其中，带约束条件的最优化问题（极值求解问题）一般是引入拉格朗日乘子法，构建拉格朗日对偶函数，通过求其对偶函数的解，从而得到原始问题的最优解。
其实不仅是带约束的最优化问题，任何一个最优化问题都伴随着一个”影子”最优化问题。其中一个称为原始问题，另一个称为对偶问题。
这里，先以回归模型的目标函数为例，给出其对偶形式；然后在简要描述带约束的最优化问题求解的一般思路，引出核函数。
无约束优化问题的对偶形式
在《第01章：深入浅出ML之Regression家族》中，我们给出了回归模型的目标函数：
$$
\begin{align}
\min_{w} \quad J(w) &= \frac{1}{2} \sum_{i=0}^{m} \left(h_{w}(x^{(i)}) - y^{(i)} \right)^2 ＋ \frac{\lambda}{2} {\Vert w \Vert}_{2}^{2} \\
&= \frac{1}{2} \sum_{i=0}^{m} \left(w^T \phi(x^{(i)}) - y^{(i)} \right)^2 ＋ \frac{\lambda}{2} w^T w
\end{align} \qquad(n.ml.1.4.1)
$$
回归模型通用形式：\(h_w(x) = w^T \phi(x)\)，其中\(\phi(x)\)是一个\(n \times 1\)的向量。对参数向量\(w\)求导，可得：
$$
\begin{align}
w = -\frac{1}{\lambda} \sum_{i=1}^{m} \underline{ \left(w^T \phi(x^{(i)}) - y^{(i)}\right) } \cdot \phi(x^{(i)}) = \sum_{i=1}^{m} \alpha^{(i)} \cdot \phi(x^{(i)}) = \Phi^T \alpha
\end{align} \qquad(ml.1.4.1)
$$
其中
\(
\alpha^{(i)} = -\frac{1}{\lambda} \left( w^T \phi(x^{(i)}) - y^{(i)} \right) \qquad
\)\(\alpha_{m \times 1} = (\alpha^{(1)}, \alpha^{(2)}, \cdots, \alpha^{(m)})^T\)是一个向量；\(\Phi_{m \times n} = (\phi(x^{(1)}), \phi(x^{(2)}), \cdots, \phi(x^{(m)}))\) 称为设计矩阵。
接下来，按照对偶表示的思路，重新定义目标函数。将\(w = \Phi^T \alpha\)带入公式\((n.ml.1.4.1)\)可得：
$$
J(\alpha) = \frac{1}{2} a^T \Phi \Phi^T \Phi \Phi^T a - \frac{1}{2} a^T \Phi \Phi^T \cdot Y + \frac{1}{2} Y^T Y + \frac{\lambda}{2} a^T \Phi \Phi^T \alpha \qquad(n.ml.1.4.2)
$$
其中真实结果集合\(Y = (y^{(1)}, y^{(2)}, \cdots, y^{(m)})^T\)。定义格拉姆矩阵(Gramian Matrix) \(K = \Phi \Phi^T\)一个\(m \times m\)的对称矩阵，每一个元素：
$$
K_{ij} = \phi(x^{(i)})^T \cdot \phi(x^{(j)}) = k(x^{(i)}, x^{(j)}) \qquad (ml.1.4.2)
$$
格拉姆矩阵形式：
$$
K =
\begin{bmatrix}
(x^{(1)}, x^{(1)}) & (x^{(1)}, x^{(2)}) & \cdots & (x^{(1)}, x^{(m)}) \\
(x^{(2)}, x^{(1)}) & (x^{(2)}, x^{(2)}) & \cdots & (x^{(2)}, x^{(m)}) \\
\vdots & \vdots & \ddots & \vdots \\
(x^{(m)}, x^{(1)}) & (x^{(m)}, x^{(2)}) & \cdots & (x^{(m)}, x^{(m)})
\end{bmatrix} \qquad(n.ml.1.4.3)
$$格拉姆矩阵的一个重要应用是计算线性无关：一组向量线性无关 当且仅当 格拉姆矩阵行列式不等于0。
（如果\(\phi(x)\)是随机变量，得到的格拉姆矩阵是协方差矩阵。）
公式\((ml.1.4.4)\)是一个表示任意两个样本之间关系的函数。后面会提到，每一个玉树值可通过定义核函数来计算。
约束优化问题求解一般思路
拉格朗日乘子（Lagrange Multiplier）
拉格朗日乘子法通常用于求解带等式约束的极值问题，一个典型的最优化问题形式化表示如下：
$$
\begin{align}
& \min_{w} \quad f(w) \\
& s.t. \; h_i(w) = 0, \quad i=1,\cdots,k
\end{align} \qquad\quad(ml.1.4.3)
$$目标函数是\(f(w)\)，\(w \in R^n\) （\(n\)表示参数向量个数）；下面是等式约束，其中\(k\)为等式约束的个数。这类问题通常解法是引入拉格朗日乘子（又称算子），这里用\(\beta\)表示乘子，得到的拉格朗日公式为：
$$
\mathcal{L}(w,\beta) = f(w) + \sum_{i=1}^{k} \beta_i \cdot h_i(w) \qquad(n.ml.1.4.4)
$$然后分别对\(w\)和\(\beta\)求偏导，使得偏导数等于0，进而求解出\(w\)和\(\beta\)。
为什么引入拉格朗日乘子就可以求解出极值？
主要原因是\(f(w)\)的切线方向（\(dw\)变化方向）受其它等式的约束，\(dw\)的变化方向与\(f(w)\)的梯度方向垂直时才能获得极值。并且在极值点处，\(f(w)\)的梯度与其它等式梯度的线性组合平行。因此它们之间存在线性关系。具体可参考《最优化算法》系列。
拉格朗日对偶（Lagrange Duality）
对于带有不等式约束的极值问题，形式化表示如下：
$$
\begin{align}
& \min_{w} \quad f(w) \\
& s.t. \; g_i(w) \leq 0, \quad i = 1, \cdots, l \\
& \quad\;\;\, h_i(w) = 0, \quad i =1, \cdots, k
\end{align} \qquad(n.ml.1.4.5)
$$定义拉格朗日公式：
$$
\mathcal{L}(w, \alpha, \beta) = f(w) + \sum_{i=1}^{l} \alpha_i g_i(w) + \sum_{i=1}^{k} \beta_i h_i(w) \quad(n.ml.1.4.6)
$$公式\((n.ml.1.4.6)\)中的\(\alpha_i\)和\(\beta_i\)都是拉格朗日乘子。但如果按照该公式求解会出现以下问题。
因为目标函数要求的是最小值，而约束条件\(h_i(w) \le 0\)，如果将\(\alpha_i\)调整为很大的正数，会使得最后的函数结果为负无穷（\(-\infty\)）。
因此，我们需要排除上述情况的发生。策略如下，定义函数：
$$
\theta_{\mathcal{P}}(w) = \max_{\alpha, \beta;\, \alpha_i \geq 0} \mathcal{L}(w, \alpha, \beta) \qquad\quad (n.ml.1.4.7)
$$公式\((n.ml.1.4.5)\)中的\(\mathcal{P}\)表示原问题，即primal。_假设\(g_i(w) > 0\)或者\(h_i(w) \neq 0\)，那么我们总可以通过调整\(\alpha_i\)和\(\beta_i\)，使得\(\theta_{\mathcal{P}}(w)\)趋向正无穷。而只有当函数\(g\)和\(h\)满足约束条件时，\(\theta_{\mathcal{P}}(w)\)为\(f(w)\)。_
公式\((n.ml.1.4.7)\)精妙之处就在于\(\alpha_i \ge 0\)，而且是求极大值。因此公式\((n.ml.1.4.7)\)可以写为：
$$
\theta_{\mathcal{P}}(w) =
\begin{cases}
f(w), \quad & 如果w满足原问题约束; \\
\; \infty, \quad & otherwise.
\end{cases} \qquad(n.ml.1.4.8)
$$公式\((n.ml.1.4.7)\)和\((n.ml.1.4.8)\)是理解拉格朗日对偶的关键。
如此，我们原来要求解的\(\min_w f(w)\)可以转化为求解\(\min_w \theta_{\mathcal{P}}(w)\)了。即：
$$
\min_w f(w) = \min_w \theta_{\mathcal{P}}(w) = \min_{w} \max_{\alpha, \beta;\, \alpha_i \geq 0} \mathcal{L}(w, \alpha, \beta) \qquad (n.ml.1.4.9)
$$这里先用\(\mathcal{P}^{\ast}\)表示\(\min_w \theta_{\mathcal{P}}(w)\)。如果直接求解，又会面临如下问题：
首先面对两个参数\(\alpha、\beta\)，并且参数\(\alpha_i\)也是一个不等式约束；然后再在\(w\)上求极小值。这个过程不容易做，可否有相对容易的解法呢？
我们换一个角度考虑该问题，令\(\theta_{\mathcal{D}}(\alpha, \beta) = \min_{w} \mathcal{L}(w, \alpha, \beta)\)。\(\mathcal{D}\)是对偶的意思，\(\theta_{\mathcal{D}}(\alpha, \beta)\)将问题转化为**先求拉格朗日关于\(w\)的最小值，将\(\alpha\)和\(\beta\)看作是固定值。然后再求\(\theta_{\mathcal{D}}(\alpha, \beta)\)的极大值**。即：
$$
\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) \qquad (n.ml.1.4.10)
$$问题转化为原问题的对偶问题来求解。其实，相对于原问题来说只是更换了\(max\)和\(min\)的顺序，而一般更换顺序的结果是：\(max \; min \; f(x) \le min \; max \; f(x)\)。用\(\mathcal{D}^{\ast}\)表示对偶问题，与原问题\(\mathcal{P}^{\ast}\)关系如下：
$$
\mathcal{D}^{\ast} = \max_{\alpha,\beta; \; \alpha_i \ge 0} \min_{w} \mathcal{L}(w, \alpha, \beta) \le \min_{w} \max_{\alpha,\beta; \; \alpha_i \ge 0} \mathcal{L}(w, \alpha, \beta) = \mathcal{P}^{\ast} \quad (ml.1.4.4)
$$即将_最小最大问题_转化为_最大最小问题。_
(这部分可与《第02章：深入浅出ML之Entropy-Based家族》结合起来理解，更容易理解并能建立起优化问题、最大熵以及后面要介绍的SVM之间的公式关联。)
这里我们总结下拉格朗日对偶的精髓：
| 将原有参数\(w\)的计算提前并消除\(w\)，使得优化函数变为拉格朗日乘子的单一参数优化问题。 |
|---|
核方法
在机器学习中，核方法被形式化为特征空间的向量内积。又被称为核技巧（kernel trick），或核置换（kernel substitution）。
核函数介绍
早在机器学习学科成立之前，核函数相关理论、核函数技术以及核函数的有效性定理就已经存在。1964年Aizerman等人把势函数（potential function）相关研究引入到模式识别领域。中间过去很多年，直到1992年Boser等人在研究机器学习中最大间隔分类器中再次将核函数引入进来，产生了支持向量机技术。从这开始，核函数在机器学习的理论和应用得到了更多地关注和极大的兴趣。
例如，Scholkopf等人将核函数应用到主成分分析PCA中产生了核主元分析法（kernel PCA），Mika等人将核函数引入到Fisher判别中产生了核Fisher判别分析（kernel Fisher discriminant）等等。这些技术在机器学习、模式识别等不同领域中起到了很重要的作用。
核函数有效性Mercer定理可追溯至1909年。
核函数引入
Andrew Ng男神在《机器学习》课程第一讲的线性回归中提到例子，用回归模型拟合房屋面积（\(x\)表示）与价格（\(y\)表示）之间的关系。示例中的回归模型用\(y=w_0 + w_1 x\)方程拟合。假设从样本的分布中可以看到\(x\)与\(y\)符合3次曲线关系，那么我们希望使用\(x\)的3次多项式来逼近这些样本点。
首先要做的是将一维特征\(x\)映射至三维\((x,x^2,x^3)\)，然后再根据新特征与结果之间的关系模型。我们将这种特征变换称作特征映射（Feature Mapping）。映射函数这里用\(\phi(x)\)表示，该例中可表示为：
$$
\phi(x): \;\; x \longrightarrow
\begin{bmatrix}
x \\
x^2 \\
x^3 \\
\end{bmatrix} \qquad\qquad(exp.ml.1.4.1)
$$
我们希望将映射后的特征应用于后面要介绍的SVM分类中，而不直接用原始特征（Raw Feature）。
为什么要用映射后的特征，而不是原始特征来计算呢?
为了更好的拟合数据是其中一个原因。另外一个重要原因是本章写在前面提到的：样本可能存在在低维空间线性不可分的情况，而将其映射到高维空间中往往就可分。
核函数方法
核函数形式化定义：如果原始特征内积\(\langle x,z \rangle\)，映射后为\(\langle \phi(x), \phi(z) \rangle\)，那么核函数定义为：
$$
K(x,z) = \phi(x)^T \phi(z) \qquad (ml.1.4.5)
$$
如果要实现\(\phi(x)^T \phi(z)\)的计算，只需要先计算\(\phi(x)\)，然后再计算\(\phi(z)^T \phi(z)\)即可。然而这种计算方式是非常低效的。如果最初特征是\(n\)维的，现在将其映射到\(n^2\)维，然后再计算，此时时间复杂度从\(O(n)\)上升为\(O(n^2)\)。
核函数无需知道非线性映射函数\(\phi\)的形式和参数，它会隐式地改变从输入空间到特征空间的映射，进而对特征空间产生影响。 举例：假设\(x\)和\(z\)都是\(n\)维的，有:
$$
K(x,z) = (x^Tz)^2 \qquad\quad(ml.1.4.6)
$$
公式\((ml.1.4.6)\)称为多项式核函数（polynomial kernel），它是对原始输入空间到特征空进行多项式映射（非线性变换）。假设\(x,z\)都是\(n\)维向量，对公式\((ml.1.4.6)\)展开后，可得：
$$
\begin{align}
K(x,z) &= (x^Tz)^2 = \left( \sum_{i=1}^{n} x_i z_i \right) \cdot \left( \sum_{i=1}^{n} x_i z_i \right) \\
& = \sum_{i=1}^{n} \sum_{j=1}^{n} (x_i x_j) (z_i z_j) = \phi(x)^T \phi(z)
\end{align} \qquad(n.ml.1.4.11)
$$
从公式\((n.ml.1.4.11)\)可以看出，只要计算原始特征\(x\)和\(z\)的平方（时间复杂度\(O(n)\)），就等价于映射后特征的内积。
举例：当\(n\)=2时，根据上面的公式可得映射函数：
$$
\phi(x) =
\begin{bmatrix}
x_1^2 \\
\sqrt{2} x_1 x_2 \\
x_2^2 \\
\end{bmatrix} \qquad\qquad(exp.ml.1.4.2)
$$令\(x = (x_1, x_2), z = (z_1, z_2)\)
$$
\begin{align}
K(x,z) &= (x^T z)^2 = (x_1 z_1 + x_2 z_2)^2 \\
&= (x_1^2 z_1^2 + 2 x_1 x_2 z_1 z_2 + x_2^2 z_2^2) \\
&= \underline { (x_1^2, \sqrt{2} x_1 x_2, x_2^2) } \cdot \underline { (z_1^2, \sqrt{2} z_1 z_2, z_2^2)^T } \\
&= \phi(x)^T \phi(z)
\end{align} \qquad(exp.ml.1.4.3)
$$
也就是说，核函数\(K(x,z) = (x^Tz)^2\)只能选择这样的映射函数\(\phi\)时，才能等价于映射后特征的内积。下面再看一个核函数：
$$
\begin{align}
K(x,z) & = (x^Tz + c)^2 \\
& = \sum_{i=1}^{n} \sum_{j=1}^{n} (x_i x_j)(z_i z_j) + \sum_{i=1}^{n} (\sqrt{2c} x_i) (\sqrt{2c} z_i) + c^2
\end{align} \qquad(n.ml.1.4.12)
$$那么其对应的映射函数应该为：
$$
\phi(x) =
\begin{bmatrix}
x_1 x_1 \\
x_1 x_2 \\
x_1 x_3 \\
x_2 x_1 \\
x_2 x_2 \\
x_2 x_3 \\
x_3 x_1 \\
x_3 x_2 \\
x_3 x_3 \\
\sqrt{2c}x_1 \\
\sqrt{2c}x_2 \\
\sqrt{2c}x_3 \\
c \\
\end{bmatrix} \qquad\qquad(exp.ml.1.4.4)
$$
由于计算的是内积，我们联想一下余弦相似度：如果\(x\)和\(z\)向量夹角越小，那么么核函数值就越大，反之就越小。因此，核函数值大小与 \(\phi(x)\)和\(\phi(z)\)相似度 成正相关。下面再看一个核函数:
$$
K(x,z) = \exp \left( -\frac{|x-z|^2}{2\sigma^2} \right) \qquad(ml.1.4.7)
$$
从公式\((ml.1.4.7)\)可以看出，如果\(x\)和\(z\)很近（\(|x-z| \thickapprox 0\)），那么核函数值为1；如果\(x\)和\(z\)相差很大（\(|x-z| \gg 0\)），那么核函数值约等于0。由于这个函数类似于高斯分布，因此称为高斯核函数，也叫做径向基函数（Radial Basic Function，简称RBF）。它能够把原始函数映射到无穷维。
下面在看一个核函数：
$$
K(x,z) = \tanh(a x^T z + b) \qquad\qquad(ml.1.4.8)
$$
上式称为Sigmoid核函数（sigmoidal kenel）。Sigmoid核多用于多层感知机神经网络，隐含层节点数目、隐含节点对输入节点的权值都是在训练过程中自动确定。
注意：sigmoid核对应的核函数矩阵不是正定的。之所以仍作为kernel的一种是因为给了kernel在实际应用中更多的扩展，包括在svm、神经网络等方法中的应用。
核函数有效性判定
问题：
给定一个函数\(K\)，我们能否使用\(K\)来替代计算\(\phi(x)^T \phi(z)\)？也就是说，能否找出一个\(\phi\)，使得对于所有的\(x\)和\(z\)，都有\(K(x,z) = \phi(x)^T \phi(z)\)？
公式\((n.ml.1.4.11)\)描述的核函数\(K(x,z) = (x^T z)^2\)，是否能够认为\(K\)是一个有效的核函数？
Mercer定理
在介绍Mercer定理之前，我们先解决上面的问题：
给定\(m\)个训练样本\(\{x^{(1)}, x^{(2)}, \cdots, x^{(m)}\}\)，每一个\(x^{(i)}\)对应一个特征向量。那么，我们可以将任意两个样本\(x^{(i)}\)和\(x^{(j)}\)带入函数\(K\)中，计算得到\( K_{ij} = K(x^{(i)}, x^{(j)})\)，其中\(1 \le i \le m\)，\(1 \le j \le m\)。
这样，我们就可以计算得到一个\(m*m\)的核函数矩阵（Kernel Matrix）。这里为了方便，将和函数矩阵和核函数\(K(x,z)\)都用\(K\)来表示。
假设\(K\)是有效的核函数，那么根据核函数定义：
$$
\begin{align}
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}
\end{align} \qquad(ml.1.4.9)
$$可见，核函数矩阵\(K\)应该是个对称阵。下面的公式推导会给出更明确的结论。
首先，使用符号\(\phi_k(x)\)来表示映射函数\(\phi(x)\)的第\(k\)维属性值。那么，对于任意向量\(z\)，可得：
$$
\begin{align}
z^T K z & = \sum_{i=1}^{m} \sum_{j=1}^{m} z_i K_{ij} z_j \\
& = \sum_{i=1}^{m} \sum_{j=1}^{m} z_i \phi(x^{(i)})^T \phi(x^{(j)}) z_j \\
& = \sum_{i=1}^{m} \sum_{j=1}^{m} z_i \sum_{k=1}^{n} \phi_k(x^{(i)})\phi_k(x^{(j)}) z_j \\
& = \sum_{k=1}^{n} \sum_{i=1}^{m} \sum_{j=1}^{m} z_i \phi_k(x^{(i)})\phi_k(x^{(j)}) z_j \\
& = \sum_{k=1}^{n} \left( \sum_{i=1}^{m} z_i \phi(x^{(i)}) \right)^2 \\
& \ge 0
\end{align} \qquad\quad(n.ml.1.4.13)
$$从公式\((n.ml.1.4.13)\)可以看出，如果\(K\)是个有效的核函数（即\(K(x,z)\)与\(\phi(x)^T \phi(z)\)等价），那么，在训练集上得到的核函数矩阵\(K\)应该是半正定的（\(K \ge 0\))。
如此，我们可以得出核函数的必要条件是：
\(K\)是有效的核函数 \(\Longrightarrow\) 核函数矩阵\(K\)半正定。
比较幸运的是，这个条件也是充分的。具体由Mercer定理来表达:
| Mercer定理： |
|---|
| 如果函数\(K\)是\(R^n \times R^n \rightarrow R\)上的映射（即从两个\(n\)维向量映射到实数域）并且如果\(K\)是个有效的核函数（也称为Mercer核函数），那么当且仅当对于训练样例\( \{x^{(1)}, \cdots, x^{(m)}\}\)来说，其相应的核函数矩阵是半正定的。 |
Mercer定理可以说明：为了证明\(K\)是有效的核函数，我们不用直接去寻找\(\phi\)，只需要在训练集上求出各个\(K_{ij}\)，然后判定矩阵\(K\)是否是半正定即可。
注：使用矩阵左上角主子式 \(\ge 0\)等方法可判定矩阵是否是半正定的。
当然，Mercer定理证明过程中可以通过\(L2\)范数和再生希尔伯特空间等概念，但在\(n\)维情况下，这里给出的证明是等价的。
Kernel方法不仅用在SVM上，只要在模型的计算过程中出现\(\langle x,z \rangle\)，我们都可以使用\(K(x,z)\)去替换，通过特征空间变换解决本章开头所提到的特征映射问题。
支持向量机
支持向量机（Support Vector Machine，简称SVM）是建立在统计学习理论之上的学习算法，其主要优势体现在解决线性不可分问题，通过引入核函数，巧妙地解决了在高维空间的内积运算复杂度的问题，从而很好的解决了非线性分类问题。
这里我们先通过LR模型与SVM比较，建立二者之间的基本认知。
LR与SVM
LR模型回顾
在第1章，我们详细阐述了Logistic Regression模型。我们直接地可理解为，LR的目的是从特征中学习出一个0/1分类或回归模型。
LR特点：
LR模型将特征的线性组合作为自变量（取值范围\((-\infty, \infty)\)），使用logistic函数（又称sigmoid函数）将自变量映射到\((0,1)\)上，映射后的值被认为是y=1的概率（如果是分类问题），表达式 \(P(y=1|x;w)=h_w(x)\)。（具体细节可参考《第01章：深入浅出ML之Regression家族》）
当我们要判别一个样本（用一组特征表示）属于哪个类时，只需求出\(h_w(x)\)即可；若\(h_w(x)>0.5\)，则属于y=1的类；反之属于y=0的类。（阈值0.5的前提条件：当正负样本基本均衡时）
再次审视\(h_w(x)\)：
$$
P(Y=1|X=x; w) = h_w(x) = \frac{1}{1+e^{-w^T \cdot x}}
$$我们可以发现， \(h_w(x)\)只与\(w^Tx\)有关：若\(w^Tx \geq 0\)，则\(h_w(x) \geq 0.5\)；\(w^Tx < 0\)，则\(h_w(x) < 0.5\)。也就是说，一个样本真实类别的决定权还在\(w^Tx\)。
从几何角度可这样理解：当\(w^Tx \gg 0\)时，\(h_w(x)=1\)；反之，\(h_w(x)=0\)。
如果我们从\(w^Tx\)出发，希望LR模型最终达到的目标就是：让训练数据中y=1的特征组合尽可能远大于0（即\(w^Tx \gg 0\)）；让训练数据中y=0的特征组合尽可能远小于0（即\(w^Tx \ll 0\)）。
LogReg模型要用全部训练数据学习参数\(w\)，学习过程中尽可能使正样本的特征组合远大于0，负样本的特征组合远小于0。
注意：LR强调的是在全部训练样本上达到这个目标，采用MLE作为求参准则。
SVM直观引入
假设\(w^Tx=0\)是正负样本的分割线（或分割面，SVM中称为超平面），存在a、b、c三个样本点（如右图所示），它们到\(w^Tx=0\)的距离分别表示为\(h(a)、h(b)、h(c)\)（其中\(h(a) > h(b) > h(c)\)），即a点距离分割面的距离最远，c点距离最近。
相对于c点来说，我们更有把握的确定a点的类别，b点类别基本也可以确定。c点因为距离分割面比较近，没有把握确定其类别。
因为c点距离\(w^Tx=0\)比较近，而训练出来的模型存在一定的误差。参数\(w\)稍微变动一些，可能直接导致c点类别的判断结果截然不同。
因此我们可以得出如下总结：我们更关心的是靠近中间分割面的点，如果让它们尽可能的远离分割面即可，没必要在所有点上达到最优。 如果这样的话，就需要使得一部分点（距离中间线较远的点）靠近中间线来换取另一部分点（距离中间线较近的点）更加远离中间线。
也许这就是SVM与LR不同的学习思想和出发点：前者考虑局部（只关心距离较近的点，不太关心已经确定远离的点），后者考虑全局（整体上达到最远，会出现已经远离的点调整中间线后更加远离）。
其实SVM仅利用支持向量（少部分样本）表示训练样本，非全部样本。
函数间隔与几何间隔
形式化表示
这里，我们先定义SVM中使用的样本标签为\(\{-1, 1\}\)（与LR中的\(\{0, 1\}\)不同）。同时LR中的参数\(w \in R^{n+1}\)，在这里\(w \in R^{n}, b \in R\)。SVM中要求的分类器可表示为：
$$
h_{w,b}(x) = g(z) = g(w^Tx + b) \qquad\qquad(ml.1.4.10)
$$由于是分类问题，我们只需要考虑\(w^Tx + b\)的正负问题即可，不用关心\(g(z)\)绝对大小。因此我们这里将\(g(z)\)做一个简化，将其简单映射到\(y=1\)和\(y=-1\)上。映射关系如下：
$$
g(z) =
\begin{cases}
\quad 1, & z \ge 0 \\
\;\, -1, & z < 0
\end{cases} \qquad\quad(n.ml.1.4.14)
$$函数间隔（Functional Margin）
任意给定一个训练样本\((x^{(i)}, y^{(i)})\)，用\(x^{(i)}\)表示样本特征（向量），\(y^{(i)}\)表示样本标签，\(i\)表示第\(i\)个样本。定义函数间隔：
$$
\hat{\gamma}^{(i)} = y^{(i)} \left(w^T x^{(i)} + b\right) \qquad(ml.1.4.11)
$$当\(y^{(i)}=1\)时，在公式\((n.ml.1.4.14)\)定义中，\(w^Tx^{(i)}+b \ge 0\)，\(\hat{\gamma}^{(i)}\)的值实际上就是\(\left|w^Tx^{(i)}+b\right|\)，反之亦然。
为了使函数间隔最大（如此我们就更有信心确认该样本是正例还是反例），当\(y^{(i)}=1\)时，\(w^Tx^{(i)}+b\)应该是个比较大的正数，反之是个较大的负数。
因此，函数间隔可以表示我们认为样本（一组特征表示）是正例还是反例的确信度。
公式\((ml.1.4.11)\)定义的是一个样本的函数间隔，现在我们定义在全局样本上的函数间隔：
$$
\hat{\gamma} = \min_{i=1,2,\cdots, m} \hat{\gamma}^{(i)} \qquad\quad(ml.1.4.12)
$$即全局函数间隔就是在所有训练样本上分类正例和负例确信度最小的那个函数间隔。
继续考虑参数\(w、b\)，如果同时加大这两个值，比如在\(w^Tx+b\)前面乘一个系数\(n\)(\(n>1\))，那么所有点的函数间隔都会增加\(n\)倍，参数倍数缩放对求解问题不应该有影响。
因为我们要求的是\(w^Tx+b=0\)，参数同比例缩放对结果是无影响的。
为了限制\(w和b\)，需要加入归一化条件，毕竟求解的目标是确定唯一一个\(w和b\)，而不是多组线性相关的向量。
几何间隔（Geometric Margin）
如右图所示，假设分割面\(w^Tx+b=0\)上有了点B，\(n\)维空间任意一点A\((x^{(i)}, y^{(i)})\)到该分割面的距离用\(\gamma^{(i)}\)表示，假设B点就是A在分割面上的投影。利用中学的几何知识可知，向量\(\overrightarrow{BA}\)的方向是\(w\)（分割面的梯度），单位向量是\(\frac{w}{| w |}\)。
那么B点的坐标可以求得：
$$
x = x^{(i)} - \gamma^{(i)} \frac{w}{|w|} \qquad (n.ml.1.4.15)
$$将公式\((n.ml.1.4.15)\)带入\(w^Tx+b=0\)得到：
$$
w^T (x^{(i)} - \gamma^{(i)} \frac{w}{|w|}) + b =0 \qquad(n.ml.1.4.16)
$$进一步整理得到：
$$
\gamma^{(i)} = \left(\frac{w}{|w|}\right)^T x^{(i)} + \frac{b}{|w|} \qquad(n.ml.1.4.17)
$$\(\gamma^{(i)}实际上就是n维空间中点到超平面的距离。\)
主要考查点：
在我们广告算法组的相关面试中，经常会请求职者推导\(n\)维空间中点到超平面的距离公式（如果求职者知道SVM），但是能完整推导出来的只有十之二三 …
几何间隔在分类问题中，可表示为：
$$
\gamma^{(i)} = y^{(i)} \left( \left(\frac{w}{|w|}\right)^T x^{(i)} + \frac{b}{|w|} \right) \qquad(ml.1.4.13)
$$可以发现，当\(|w|=1\)时，就是函数间隔。其实几何间隔是函数间隔归一化的结果。那么，全局几何间隔定义为：
$$
\gamma = \min_{i=1,2,\cdots, m} \gamma^{(i)} \qquad(ml.1.4.14)
$$
最优间隔分类器
在前面也提到，SVM的目标是寻找一个超平面，使得距离超平面最近的点能有更大的间距。不考虑所有的点都必须远离超平面，只关心求得的超平面能够让所有的点中离它最近的点具有最大间距。因此，我们需要数学化表示最优间隔（optimal margin classifier）。
形式化表示
最优间隔形式化可表示为：
$$
\begin{align}
& \max_{w, b} \; \gamma \\
& s.t. \; y^{(i)}(w^Tx+b) \ge \gamma, \; i=1,\cdots,m \\
& \qquad |w|=1
\end{align} \qquad(ml.1.4.15)
$$这里利用\(|w|=1\)约束\(w\)，使得\(w^Tx+b\)是几何间隔。
到这里其实已经将SVM的模型定义出来了，求解出来的模型称为最优间隔分类器。如果求得了\(w\)和\(b\)，对于任意一个样本\(x\)，我们就能够分类了。那么，接下来主要工作就是围绕如何求解参数\(w\)和\(b\)来展开的。
由于\(|w|=1\)不是凸函数，那么先利用几何间隔和函数间隔的关系转化一下\(\gamma=\frac{\hat{\gamma}}{|w|}\)，因此公式\((ml.1.4.6)\)可改写为：
$$
\begin{align}
& \max_{w, b} \; \frac {\hat{\gamma}} {|w|} \\
& s.t. \; y^{(i)}(w^Tx+b) \ge \gamma, \; i=1,\cdots,m
\end{align} \qquad(ml.1.4.16)
$$上式所求的极大值仍然是几何间隔，只不过此时的\(w\)不再受\(|w|=1\)的约束了。
然而此时的目标函数仍然不是凸函数，无法方便求解。继续改写目标函数…
前面说过同时缩放\(w\)和\(b\)对结果没有影响，但最后希望求得的是确定值，不是一组倍数值。为了达到这个目的，需要对\(\hat{\gamma}\)做一些限制，以保证最终解是唯一的。为了简便，取\(\hat{\gamma}=1\)。
将全局函数间隔定义为1，即将离超平面最近的点的距离定义为\(\frac{1}{|w|}\)（当然定义为其它非0常数也可以，不影响最终的参数求解）。
由于求\(\frac{1}{|w|}\)的极大值等价于求\(\frac{1}{2} |w|^2\)的极小值，因此目标函数可进一步改写为：
$$
\begin{align}
& \max_{w, b} \; \frac{1}{2} |w|^2 \\
& s.t. \; y^{(i)}(w^Tx+b) \ge 1, \; i=1,\cdots,m
\end{align} \qquad(ml.1.4.17)
$$公式\((ml.1.4.17)\)是一个典型的带不等式约束的二次规划求解问题（目标函数是自变量的二次函数）。
到此为止，我们完成了目标函数由非凸到凸的转变.
最优间隔分类器学习过程
KKT条件
第一节对偶优化问题中，公式\((ml.1.4.4)\)有一个问题：在什么条件下\(\mathcal{P}^{\ast}\)与\(\mathcal{D}^{\ast}\) 两者等价？
暂时先不回答这个问题，我们假设函数\(f(w)\)和\(g(w)\)是凸函数，\(h(w)\)是仿射的（affine，仿射的含义是指存在\(a_i、b_i\)，能够使得\(h_i(w)=a_i^T w + b_i成立\)）。并且存在\(w\)使得对于所有的\(i\)，\(g_i(w)<0\)。在这种假设下，一定存在\(w^{\ast}、\alpha^{\ast}、 \beta^{\ast}\)使得\(w^{\ast}\)是原问题的解，\(\alpha^{\ast}、\beta^{\ast}\)是对偶问题的解。此时也满足\(\mathcal{P}=\mathcal{D}=\mathcal{L}(w^{\ast},\alpha^{\ast},\beta^{\ast})\)。
另外，解\(w^{\ast}、\alpha^{\ast}、 \beta^{\ast}\)满足库恩-塔克条件(Karush-Kuhn-Tucker, 简称KKT条件)，该条件表示如下：
$$
\begin{align}
\frac{\partial} {\partial w_i} \mathcal{L}(w^{\ast}, \alpha^{\ast}, \beta^{\ast}) & = 0, \quad i=1,\cdots,n \qquad(1)\\
\frac{\partial}{\partial \beta_i} \mathcal{L}(w^{\ast}, \alpha^{\ast}, \beta^{\ast}) & = 0, \quad i =1, \cdots, k \qquad(2)\\
a^{\ast} g_i(w^{\ast}) & = 0, \quad i=1,\cdots, l \qquad\;(3)\\
g_i(w^{\ast}) & \le 0, \quad i = 1,\cdots, l \qquad\;(4)\\
a^{\ast} & \geq 0, \quad i=1,\cdots, l \qquad\;(5)
\end{align} \qquad (ml.1.4.18)
$$所以，如果\(w^{\ast}、\alpha^{\ast}、\beta^{\ast}\)满足了库恩-塔克条件，那么它们就是原问题与对偶问题的解。
在这里我重点关注公式\((ml.1.4.18)-(3)\)，这个条件称作是KKT Dual Complementarity条件。这个条件隐含了如果\(\alpha^{\ast} > 0\)，那么\(g_i(w) = 0\)。
从集合的角度可这样理解：\(g_i(w^{\ast})=0\)时，\(w\)处在可行域的边界上，这时才是真正起作用的约束。而位于可行域内部\(（即g_i(w^{\ast})<0）\)的点都是不起作用的约束，对应的\(\alpha^{\ast}=0\)。
这个KKT双重补足条件会用来解释SVM中的支持向量和SMO的收敛测试。KKT思想可总结如下：
| KKT总体思想是认为极值会在可行域边界上取得，也就是不等式为0或等式约束的条件下取得，而最优下降（或上升）方向一般是这些等式的线性组合，其中每个元素要么是不等式为0的约束，要么是等式约束。对于在可行域边界内的点，对目标函数最优解不起作用，因此前面的系数为0。 |
|---|
优化目标
重新前面的SVM的优化问题：
$$
\begin{align}
& \max_{w, b} \; \frac{1}{2} |w|^2 \\
& s.t. \; y^{(i)}(w^Tx+b) \ge 1, \; i=1,\cdots,m
\end{align} \qquad(n.ml.1.4.18)
$$首先将约束条件改写为：
$$
g_i(w) = -y^{(i)} (w^T x^{(i)} + b) + 1 \le 0 \qquad\quad(n.ml.1.4.19)
$$
根据上一节中的KKT条件可知，只有函数间隔是1（离超平面最近的点）的线性约束式前面的系数\(\alpha_i > 0\)，也就是说这些对应的约束式\(g_i(w) = 0\)。对于其它的不在线上的点\(g_i(w) < 0\)，极值不会在它们所在的范围内取得，因此前面的系数\(\alpha_i = 0\)。
这里每一个约束式对应一个训练样本。
如右图所示，实线是最大间隔超平面，用”×”表示正样本，”o”表示负样本。在虚线上的点（两个”×”和一个”o”）就是函数间隔是1的点（又称支持向量），那么它们前面的系数\(\alpha_i > 0\)，其它点都是\(\alpha_i = 0\)。
因此，可构造拉格朗日函数如下：
$$
\mathcal{L}(w,b,\alpha) = \frac{1}{2} |w|^2 - \sum_{i=1}^{m} \alpha_i \cdot \left(y^{(i)} (w^Tx + b) - 1\right) \qquad(ml.1.4.19)
$$说明：这里面只有\(\alpha_i\)而没有\(\beta_i\)，是因为SVM原问题中没有等式约束，只有不等式约束。
SVM对偶问题
下面我们看着拉格朗日的对偶问题来求解，对偶函数表达式如下：
$$
\mathcal{D} = \max_{\alpha;\; \alpha \ge 0} \min_{w,b} \mathcal{L}(w,b,\alpha) \qquad\qquad(ml.1.4.20)
$$首先，极小化过程。固定参数\(\alpha\)，求\(\mathcal{L}(w,b,\alpha)\)关于\(w\)和\(b\)的最小值。分别对\(w\)和\(b\)求偏导：
$$
\begin{align}
\nabla_w \mathcal{L}(w,b,\alpha) = w - \sum_{i=1}^{m} \alpha_i y^{(i)} x^{(i)} = 0 \qquad(1)\\
\frac{\partial}{\partial b} \mathcal{L}(w,b,\alpha) = \sum_{i=1}^{m} \alpha_i y^{(i)} = 0 \qquad\qquad\;\;\;(2)
\end{align} \qquad(ml.1.4.21)
$$根据公式\((ml.1.4.21)\)-\((1)\)可得到：
\(
\qquad\qquad w = \sum_{i=1}^{m} \alpha_i y^{(i)} x^{(i)} \qquad(n.ml.1.4.20)
\)将公式\((n.ml.1.4.20)\)带入\((ml.1.4.18)\)，此时得到的是该目标函数的最小部分（因为目标函数是凸函数）。公式推导如下：
$$
\begin{align}
\mathcal{L}(w,b,\alpha) & = \frac{1}{2} w^T w - \sum_{i=1}^{m} \alpha_i y^{(i)} w^T x^{(i)} - b \cdot \sum_{i=1}^{m} \alpha_i y^{(i)} + \sum_{i=1}^{m} \alpha_i \qquad\quad (1)\\
& = \frac{1}{2} w^T \cdot \sum_{i=1}^{m} \alpha_i y^{(i)} x^{(i)} - w^T \cdot \sum_{i=1}^{m} \alpha_i y^{(i)} x^{(i)} + \sum_{i=1}^{m} \alpha_i - b \sum_{i=1}^{m} \alpha_i y^{(i)} \quad(2) \\
& = -\frac{1}{2} w^T \sum_{i=1}^{m} \alpha_i y^{(i)} x^{(i)} + \sum_{i=1}^{m} \alpha_i - b \sum_{i=1}^{m} \alpha_i y^{(i)} \qquad\quad(3) \\
& = -\frac{1}{2} \left(\sum_{i=1}^{m} \alpha_i y^{(i)} x^{(i)} \right)^T \cdot\sum_{i=1}^{m} \alpha_i y^{(i)} x^{(i)} + \sum_{i=1}^{m} \alpha_i - b\sum_{i=1}^{m} \alpha_i y^{(i)} \quad(4) \\
& = -\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_i \alpha_j y^{(i)} y^{(j)} \cdot (x^{(i)})^T x^{(j)} + \sum_{i=1}^{m} \alpha_i - b \sum_{i=1}^{m} \alpha_i y^{(i)} \quad(5)
\end{align} \;(n.ml.1.4.21)
$$说明：第\((3)\)步到第\((4)\)步使用了线性代数中的转置运算，由于\(\alpha_i\)和\(y^{(i)}\)都是实数，因此转置后一样。第\((4)\)步到第\((5)\)步使用了乘法运算规则: \((a+b)(a+b) = aa + ab + ba + bb\)。
公式\((n.ml.1.4.21)\)主要目的是将\(\mathcal{L}(w,b,\alpha)\)转化为关于拉格朗日乘子\(\alpha\)的函数。
又因为有\((ml.1.4.21)-(2)\)成立，所以公式\((n.ml.1.4.21)-(5)\)最后一项为0。因此，目标函数最后整理为：
$$
\mathcal{L}(w,b,\alpha) = -\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_i \alpha_j y^{(i)} y^{(j)} (x^{(i)})^T x^{(j)} + \sum_{i=1}^{m} \alpha_i \qquad(ml.1.4.22)
$$这里我们将向量内积\((x^{(i)})^T x^{(j)}\)表示为\(\langle x^{(i)}, x^{(j)} \rangle\)。正因为有向量内积的（复杂）计算，才有后面Kernal的出现。
接着，求极大化过程。此时极值问题可表示为：
$$
\begin{align}
& \max_{\alpha} \quad -\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_i \alpha_j y^{(i)} y^{(j)} (x^{(i)})^T x^{(j)} + \sum_{i=1}^{m} \alpha_i \\
& s.t. \quad \alpha_i \ge 0, \quad i=1,\cdots, m \\
& \qquad \sum_{i=1}^{m} \alpha_i y^{(i)} = 0.
\end{align} \qquad\quad(ml.1.4.23)
$$从公式\((ml.1.4.23)\)中可以看出，目标函数和线性约束都是凸函数，并且这里不存在不等式约束。根据4.1.4节中介绍的KKT条件可知：存在\(w\)使得对于所有的\(i，g_i(w) < 0\)。因此，一定存在\(w^{\ast}、\alpha^{\ast}\)使得\(w^{\ast}\)是原问题的解，\(\alpha^{\ast}\)是对偶问题的解。（在这里，求\(\alpha_i\)就是求\(\alpha^{\ast}\)了。）
对偶问题求解思路
如果求出\(\alpha_i\)，根据\((n.ml.1.4.20)\)可求出\(w\)（即\(w^{\ast}\)，原问题的解）。参数\(b\)的求解可利用下面的公式：
$$
b^{\ast} = - \frac{\max_{i:y^{(i)}=-1} {w^{\ast}}^T x^{(i)} + \min_{i:y^{(i)}=1} {w^{\ast}}^T x^{(i)}} {2} \qquad\quad (n.ml.1.4.22)
$$即离超平面最近的正的函数间隔要等于离超平面最近的负的函数间隔。这样，我们就可以求出最优间隔分类器\(w^T x + b = 0\)。
此外，我们根据公式\((n.ml.1.4.20)\)得到了参数\(w\)的表达式。但别忘了，我们SVM通篇考虑的是最优间隔分类器\(w^x+b=0\)的求解。根据\(w\)的表达式，我们带入方程可得：
$$
w^T x + b = \left(\sum_{i=1}^{m} \alpha_i y^{(i)} x^{(i)}\right)^T x + b = \sum_{i=1}^{m} \alpha_i y^{(i)} \langle x^{(i)}, x \rangle + b \qquad(n.ml.1.4.23)
$$也就是说，如果按照\(w^T x + b\)为新来的样本做分类，首先根据\(w\)和\(b\)做一次线性运算，然后看求出来的结果是大于0还是小于0，以此来判断样本是正例还是负例。现在有了\(\alpha_i\)，我们不需要求\(w\)，只需要将新来的样本与训练数据中的所有样本做内积即可。
或许存在这样一个疑问：与所有样本做内积是否太耗时了？ 其实不然，根据KKT条件可知，只有支持向量的参数\(\alpha_i\)是大于0的，其它情况都等于0。因此，我们只需要求新样本与支持向量的内积，然后运算即可。
上面的讨论都是建立在样本线性可分的假设前提下，当样本不可分时，我们可以尝试利用核函数将特征映射到高维空间，这样很可能就可分了。然而，映射后也不能保证样本100%线性可分，那又该如何？这就是下面通过引入松弛变量的软间隔模型和正则化要解决的问题。
软间隔与正则化
为了解决上述问题，这里需要将模型做一个调整，以保证在不可分的情况下，也能够尽可能地找出分隔超平面。
软间隔与惩罚项
从右图可以看到，如果多一个离群点（也许是噪声，黑圆圈表示）可能造成超平面的移动，求出来的最优间隔在缩小（实线部分），那么之前的模型对噪声非常敏感。更有甚者，如果离群点在另一个类中，此时就线性不可分了。
如何解决这个问题呢？
我们可以考虑允许一些点游离并在模型求解中违背约束条件（函数间隔\(\ge 1\)）。那么新的模型就可以定义如下：
$$
\begin{align}
& \min_{w,b,\gamma} \quad \frac{1}{2} |w|^2 + C \sum_{i=1}^{m} \xi_i \\
& s.t \quad y^{(i)} (w^T x^{(i)} + b) \ge 1-\xi_i, \; i=1,2,\cdots,m \\
& \qquad \xi_i \ge 0, \quad i=1,2,\cdots, m
\end{align} \qquad(ml.1.4.24)
$$公式\((ml.1.4.24)\)被称为SVM的软间隔模型，非负参数\(\xi_i\)称为松弛变量。
引入松弛变量就是允许样本点的函数间隔小于1，即在最大间隔区间里面，或者函数间隔可以为负数，即样本点在对方的区域中。
而放松限制条件后，我们需要重新调整目标函数，以对离群点进行惩罚。目标函数后面的\(C\sum_{i=1}^{m} \xi_i\)就表示离群点越多，目标函数值就越大，而我们要求的事尽可能小的目标函数值。
这里的参数\(C\)表现离群点的权重（在《深入浅出ML》系列第7章正则化部分有详细介绍，那里称为惩罚因子，与这里的离群点权重是同一个意思）。\(C\)越大，表明离群点对目标函数影响越大，也就越不希望看到离群点。
我们可以给出以下总结：
目标函数控制了离群点的数据和程度，使大部分样本点仍然遵守限制条件。同时，考虑了离群点对模型的影响。
模型修改后，同时也需要对\((ml.1.4.19)\)拉格朗日公式进行修改如下：
$$
\mathcal{L}(w,b,\alpha) = \frac{1}{2} |w|^2 + C\sum_{i=1}^{m} \xi_i - \sum_{i=1}^{m} \alpha_i \cdot \left(y^{(i)} (w^Tx + b) - 1 + \xi_i \right) - \sum_{i=1}^{m} \gamma_i \xi_i \quad(ml.1.4.25)
$$这里的\(\alpha_i、\gamma_i\)都是拉格朗日乘子。
回想4.1.4节中介绍的拉格朗日对偶中提到的求法。
- 首先，写出拉格朗日公式（如\((ml.1.4.25)\)）；
- 然后，将其看作是变量\(w\)和\(b\)的函数，分别对其求偏导，得到\(w\)和\(b\)的表达式；
- 最后，把表达式带入拉格朗日公式中，求带入公式后的极大值。
整体推导过程如4.1.5节类似，这里只给出最后结果：
$$
\begin{align}
& \max_{\alpha} \quad W(\alpha) = - \frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} y^{(i)} y^{(j)} \alpha_i \alpha_j \langle x^{(i)}, x^{(j)}\rangle + \sum_{i=1}^{m} \alpha_i \\
& s.t. \quad 0 \le \alpha_i \le C, \quad i=1,\cdots,m \\
& \qquad \sum_{i=1}^{m} \alpha_i y^{(i)} = 0
\end{align} \qquad(ml.1.4.26)
$$此时我们会发现，新的目标函数中没有了参数\(\xi_i\)，与之前的模型（公式\((ml.1.4.23)\)）唯一的不同在于\(\alpha_i\)又多了\(\alpha_i \le C\)的限制条件。
需要注意的是：参数\(b\)的求值公式也发生了变化，改变结果在SMO算法里面介绍。
软间隔模型对应的KKT条件，变化如下：
$$
\begin{align}
\alpha_i = 0 & \Rightarrow y^{(i)} (w^T x^{(i)} + b ) \ge 1 \qquad (1) \\
\alpha_i = C & \Rightarrow y^{(i)} (w^T x^{(i)} + b ) \le 1 \qquad (2) \\
0 < \alpha_i < C & \Rightarrow y^{(i)} (w^T x^{(i)} + b ) = 1 \qquad (3) \\
\end{align} \qquad(ml.1.4.27)
$$公式\((ml.1.4.27)\)第\((1)\)式子表明，在两条间隔线外的样本点前面的系数为0；第\((2)\)个式子表明，在间隔线内的样本点（离群点）前面的系数为\(C\)；第\((3)\)个式子表明，支持向量（即在超平面两边的最大间隔线上）的样本想前面系数在\((0, C)\)上。
通过KKT条件克制，某些在最大间隔线上的样本点也不是支持向量，相反可能是离群点（\((1)、(2)中等号成立时\)）。
SMO算法（Sequential Minimal Optimization）用于求解目标函数\(W(\alpha)\)的极大值。
SMO算法将在《最优化算法》系列给出详细介绍。
- 首先，写出拉格朗日公式（如\((ml.1.4.25)\)）；
总结
这里中带你介绍了SVM的基本公式推导，并就其中的关键点给予了介绍。
首先，通过LR与SVM两个经典模型的比较，前者全局，后者局部（从对参数起作用的训练样本角度），引入SVM；通过函数间隔和几何间隔的介绍，明确了最优间隔的公式表达以及带优化的目标函数；并且将非凸函数转化为凸函数，以便于后续求解；
其次，我们详细地给出了求解带约束的极值优化问题的求解方法：拉格朗日乘子法与拉格朗日对偶法。并且详细推导了最优间隔分类器的优化学习过程，发现参数\(w\)可以用特征向量内积表示，进而引入核函数。此时，我们通过调整核函数就可以完成特征从低维到高维的映射，在低维上计算，实则表现在高位空间上。
核函数主要用来解决特征空间变换（线性不可分、特征映射等）以及在高维空间计算效率问题。
由于在实际场景中，训练样本不一定都线性可分。为了提升SVM算法的通用性，引入了松弛变量对优化模型进行软间隔处理，导致的结果就是优化问题变得更加复杂。然而，拉格朗日对偶求解结果中，松弛变量并没有出现在带优化的目标函数中。最后的优化求解问题，也通过SMO算法得到了解决。
最后，值得一提的是：支持向量机的理论基础决定了它最终求得的是全局最优值而不是局部最小值，也保证了它对于未知样本的良好泛化能力而不容易出现过拟合现象。
- 参考资料：
- 斯坦福大学《机器学习》课程与讲义（Andrew Ng男神）；
- 台湾大学《机器学习技法》课程与讲义 （林老师）；
- 《Pattern Recognition and Machine Learning》
- 技术博客：http://www.cnblogs.com/jerrylead
- 更多信息请关注：计算广告与机器学习－CAML 技术共享平台