本节首先介绍函数间隔和几何间隔的概念，进而引出最优间隔分类器和拉格朗日对偶，最后介绍核函数和 SMO algorithm

直观解释

逻辑回归算法中，使用 $h_\theta (x)=g (\theta^Tx)$ 对概率 $p (y=1|x;\theta)$ 建模。对于一个输入 $x$，若 $h_\theta (x)\geq 0.5$ 则预测为 1 (即 $\theta^Tx \geq 0$ 预测结果为 1)，否则预测结果为 0。

考虑正样本的情况 (y=1)。$\theta^Tx$ 的值越大，则 $h_\theta (x)=p (y=1|x;\omega;b)$ 的值越大，我们越有理由预测结果为 1。

也就是说如果 $\theta^Tx$ 远大于 0 则认为 y=1，若 $\theta^Tx$ 远小于 0 则认为 y=0。

对于给定的训练集，如果能够找到一个分界线，使得当 $y^{(i)}=1$ 时 $\theta^Tx \gg 0$，并且当 $y^{(i)}=0$ 时 $\theta^Tx \ll 0$，那么可以认为我们找到了一个对数据的合理划分方法

下图中 x 表示正样本，o 表示负样本，分界线为 $\theta^Tx = 0$，A、B、C 表示 3 个样本

分类

很明显对于 A 的预测结果应为 y=1，而对于 C，预测结果也应为 y=1，由于它离分界线很近，稍微移动就会是结果变为 y=0，直观上认为 A 的预测结果可信度比 C 更高，B 则介于两者之间

符号表示

同样是二分类问题，考虑线性分类器，与之前不同的是，这里 $y \in$ {-1,1} 表示分类标签，$w,b$ 为参数

$$h_{w,b}(x) = g(wx+b)$$

其中当 $z \geq 0$ 时 $g (z)=1$，当 $z < 0$ 时 $g (z)=-1$。该分类器直接产生结果 1 或 - 1，不需要先计算 y=1 的概率再生成结果 (逻辑回归使用的方法)

函数间隔和几何间隔

给定训练集 $(x^{(i)}, y^{(i)})$，定义函数间隔如下

$$
\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$，说明我们的预测是正确的。函数间隔越大，结果的可信度就越高

对于函数间隔的参数，如果将 $w、b$ 换成 $2w、2b$，$g (wx+b) = g (2wx+2b)$ 保持不变，不影响分类器的分类结果，但是函数间隔却变成了原来的 2 倍，这意味着我们可以随意等比例缩放 w 和 b 而不影响分类结果。

给定训练集 S = {$(x^{(i)}, y^{(i)}); i=1,…,m$}，定义最小函数间隔为

$$
\hat{\gamma} = \min_{i=1,…m} \hat{\gamma}^{(i)}
$$

下面讨论几何间隔，首先看下图

函数间隔

图中展示了决策边界、向量 w (和决策边界垂直)。A 点表示一个输入为 $x^{(i)}$、标签为 $y^{(i)}=1$ 的样本，它到决策边界的距离 $\gamma^{(i)}$ 可由线段 AB 表示。w 方向的单位向量可表示为 $\frac {w}{||w||}$，则 B 点可表示为 $x^{(i)}-\gamma^{(i)} \cdot \frac {w}{||w||}$。因为 B 点在决策边界上，所以它满足 $w^Tx + b = 0$。因此

$$
w^T(x^{(i)}-\gamma^{(i)} \cdot \frac{w}{||w||}) + b = 0
$$

求解 $\gamma^{(i)}$ 可得 (其中第 1 步也可根据点到平面的距离公式求得，可参考点到平面距离)

$$
\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||})
$$

注意如果 $||w||=1$，函数间隔和几何间隔相等，根据这个性质可以将两种间隔联系起来。最后，同样定义最小几何间隔

$$
\gamma = \min_{i=1,…m} \gamma^{(i)}
$$

最优间隔分类器

根据之前的讨论，一个很自然的想法是最大化几何间隔，这样可以对训练集进行很好地分类。

假定训练集是线性可分的，也就是说可以用超平面对正样本和负样本进行划分。如何找到这个使得几何间隔最大化的超平面呢？给出如下最优化问题

最优化问题

我们的目标是最大化 $\gamma$，需满足每个样本的函数间隔不小于 $\gamma$。条件 $||w||=1$ 使得函数间隔等于几何间隔，也就保证了几何间隔不小于 $\gamma$。求解此问题即可得到最大的几何间隔。

因为条件 $||w||=1$ 是非凸的，使得该问题不能直接使用标准的最优化软件求解。将该问题转换为如下问题

改进的最优化问题

我们最大化的目标变成了 $\frac {\hat {\gamma}}{||w||}$，需满足函数间隔不小于 $\hat {\gamma}$。几何间隔和函数间隔可通过 $\gamma = \frac {\hat {\gamma}}{||w||}$ 联系起来。$\frac {\hat {\gamma}}{||w||}$ 是非凸的，问题仍未解决

根据前面的讨论，我们可以随意等比例缩放 w、b 而不影响最终分类结果。这里考虑通过缩放使函数间隔满足

$$\hat{\gamma}=1$$

问题变为最大化 $\frac {\hat {\gamma}}{||w||} = \frac {1}{||w||}$，等价于最小化 $||w||^2$

便于求解的最优化问题

这是一个仅包含线性限制的凸二次最优化问题，可以很容易解决。这就是最优间隔分类器。

拉格朗日对偶

拉格朗日乘子法

考虑如下问题

拉格朗日乘子法

定义拉格朗日函数

$$
L(w,\beta)=f(w) + \sum_{i=1}^{l} \beta_i h_i(w)
$$

这里 $\beta_i$ 是拉格朗日乘子，令 $\frac {\partial L}{\partial w_i} = 0; \frac {\partial L}{\partial \beta_i} = 0$ 可求出 w 和 $\beta$

原始问题

考虑如下原始最优化问题

原始最优化问题

它的广义拉格朗日函数为

$$
L(w,\alpha,\beta)=f(w) + \sum_{i=1}^{k}\alpha_i g_i(w) + \sum_{i=1}^{l} \beta_i h_i(w)
$$

对于它的最大值 (其中 $P$ 表示 “原始的”)

$$
\theta_P(w) = \max_{\alpha,\beta:\alpha_i > 0} L(w, \alpha, \beta)
$$

如果 w 违反了任何原始限制 (比如 $g_i (w)>0$ 或 $h_i (w) \neq 0$)，则可以得到如下结果

性质

相反，如果满足限制则 $\theta_P (w) = f (w)$

原始问题的值

$$
p^\ast = \min_w \theta_P(w) = \min_w \max_{\alpha,\beta:\alpha_i > 0} L(w, \alpha, \beta)
$$

对偶问题

另一个问题，定义

$$
\theta_D(\alpha,\beta) = \min_w L(w, \alpha, \beta)
$$

其中下标 $D$ 表示 “对偶”。对偶最优化问题如下

$$
d^\ast = \max_{\alpha,\beta:\alpha_i > 0} \theta_D(\alpha,\beta) = \max_{\alpha,\beta:\alpha_i > 0} \min_w L(w, \alpha, \beta)
$$

很容易证明，这两种问题之间的关系如下 (先取 max 再取 min 的值总是大于等于先取 min 再取 max 的值)，并且在特定条件下两者相等

$$
d^\ast = \max_{\alpha,\beta:\alpha_i > 0} \min_w L(w, \alpha, \beta) \leq \min_w \max_{\alpha,\beta:\alpha_i > 0} L(w, \alpha, \beta) = p^\ast
$$

KKT 条件

KKT 条件是拉格朗日乘子法的推广。如果只包含等式约束条件，可以用拉格朗日乘子法求解最优值。如果约束条件中还包含不等式约束，则可以用 KKT 条件求解。

假设: 1. f 和 g 是凸函数 2. h 是仿射函数 3. 存在 w 使得对于所有的 i 均满足 $g_i (w)<0$。基于以上假设，一定存在 $w^\ast,\alpha^\ast,\beta^\ast$ 使得 $w^\ast$ 是原始问题的解、$\alpha^\ast,\beta^\ast$ 是对偶问题的解，并且 $p^\ast=d^\ast=L (w^\ast,\alpha^\ast,\beta^\ast)$。更进一步，如果某些 $w^\ast,\alpha^\ast,\beta^\ast$ 满足如下 KKT 条件 (Karush-Kuhn-Tucker conditions)，则它们是原始问题和对偶问题的解

KKT 条件

仿射函数

仿射函数是特殊的凸函数，它是线性函数和常数之和

最优间隔分类器

回忆如下原始问题

便于求解的最优化问题

可以把约束条件写为如下形式

$$
g_i(w) = -y^{(i)}(w^T x^{(i)} + b) + 1 \leq 0
$$

补充

点到平面的距离

平面的表示

平面的常用表示方法有点法式、一般式和截距式。

假设 $\vec {n} = (A,B,C)$ 为平面的法向量。$(x_0,y_0,z_0)$ 为平面上的一点，令 $(x,y,z)$ 表示平面上的任意一点，$(x - x_0,y - y_0, z - z_0)$ 表示平面上的一个向量。

因为法向量垂直于平面上任意的向量，所以 $(A,B,C) \cdot (x - x_0,y - y_0, z - z_0) = 0$(平面上的向量与法向量的内积为 0)，展开后可得

$$
A(x - x_0) + B(y - y_0) + C(z - z_0) = 0
$$

这就是平面的点法式方程。替换常量，得到平面的一般式方程如下

$$
Ax + By + Cz + D = 0
$$

向量的投影长度

向量 $\vec {a}$ 在向量 $\vec {b}$ 上的投影长度可表示为 $|\vec {a}| cos \theta$(其中 $\theta$ 为两个向量的夹角)，因为 $\vec {a} \cdot \vec {b} = |\vec {a}| |\vec {b}| cos \theta$，两边同时除以 $|b|$

$$
\vec{a} \cdot \frac{\vec{b}}{|b|}
$$

点到平面距离

点 (x,y,z) 为平面外一点，则它到平面的距离如下

$$
\begin{align}
d &= \frac{(x-x_0,y-y_0,z-z_0)(A,B,C)}{|(A,B,C)|} \\
&= \frac{Ax + By + Cz - (Ax_0 + By_0 + Cz_0)}{\sqrt{A^2 + B^2 + C^2}} \\
&= \frac{Ax + By + Cz + D}{\sqrt{A^2 + B^2 + C^2}}
\end{align}
$$

其中 $(x-x_0,y-y_0,z-z_0)$ 为平面上的点，其满足平面的方程 $Ax_0 + By_0 + Cz_0 + D = 0$。上式第 3 步用到该等式