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

直观解释

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

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

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

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

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

分类

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

符号表示

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

$$\begin{array}{}\text{(1)}& h_{w,b}(x)=g(wx+b)\end{array}$$

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

函数间隔和几何间隔

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

$$\begin{array}{}\text{(2)}& {\hat{\gamma }}^{(i)}=y^{(i)}(w^{T}x+b)\end{array}$$

当 $y^{(i)}=1$ 时，若要使函数间隔很大，则需要令 $w^{T}x+b$ 为一个很大的正数。相反，当 $y^{(i)}=-1$ 时，若要使函数间隔很大，则需要令 $w^{T}x+b$ 为一个绝对值很大的负数。进一步可得，如果 $y^{(i)}(w^{T}x+b)>0$，说明我们的预测是正确的。函数间隔越大，结果的可信度就越高

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

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

$$\begin{array}{}\text{(3)}& \hat{\gamma }=\underset{i=1,\dots m}{min}{\hat{\gamma }}^{(i)}\end{array}$$

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

函数间隔

图中展示了决策边界、向量 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^{T}x+b=0$。因此

$$\begin{array}{}\text{(4)}& w^T(x^{(i)}-{\gamma }^{(i)}\cdot \frac{w}{||w||})+b=0\end{array}$$

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

$$\begin{array}{}\text{(5)}& {\gamma }^{(i)}=\frac{w^T{x}^{(i)}+b}{||w||}=(\frac{w}{||w||}{)}^T{x}^{(i)}+\frac{b}{||w||}\end{array}$$

这表示的是正样本的情况。更一般地，几何间隔定义如下

$$\begin{array}{}\text{(6)}& {\gamma }^{(i)}=y^{(i)}((\frac{w}{||w||}{)}^T{x}^{(i)}+\frac{b}{||w||})\end{array}$$

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

$$\begin{array}{}\text{(7)}& \gamma =\underset{i=1,\dots m}{min}{\gamma }^{(i)}\end{array}$$

最优间隔分类器

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

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

最优化问题

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

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

改进的最优化问题

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

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

$$\begin{array}{}\text{(8)}& \hat{\gamma }=1\end{array}$$

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

便于求解的最优化问题

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

拉格朗日对偶

拉格朗日乘子法

考虑如下问题

拉格朗日乘子法

定义拉格朗日函数

$$\begin{array}{}\text{(9)}& L(w,\beta )=f(w)+\sum _{i=1}^l{\beta }_i{h}_i(w)\end{array}$$

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

原始问题

考虑如下原始最优化问题

原始最优化问题

它的广义拉格朗日函数为

$$\begin{array}{}\text{(10)}& L(w,\alpha ,\beta )=f(w)+\sum _{i=1}^k{\alpha }_i{g}_i(w)+\sum _{i=1}^l{\beta }_i{h}_i(w)\end{array}$$

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

$$\begin{array}{}\text{(11)}& {\theta }_P(w)=\underset{\alpha ,\beta :{\alpha }_i>0}{max}L(w,\alpha ,\beta )\end{array}$$

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

性质

相反，如果满足限制则 ${\theta }_P(w)=f(w)$

原始问题的值

$$\begin{array}{}\text{(12)}& p^{\ast }=\underset{w}{min}{\theta }_P(w)=\underset{w}{min}\underset{\alpha ,\beta :{\alpha }_i>0}{max}L(w,\alpha ,\beta )\end{array}$$

对偶问题

另一个问题，定义

$$\begin{array}{}\text{(13)}& {\theta }_D(\alpha ,\beta )=\underset{w}{min}L(w,\alpha ,\beta )\end{array}$$

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

$$\begin{array}{}\text{(14)}& d^{\ast }=\underset{\alpha ,\beta :{\alpha }_i>0}{max}{\theta }_D(\alpha ,\beta )=\underset{\alpha ,\beta :{\alpha }_i>0}{max}\underset{w}{min}L(w,\alpha ,\beta )\end{array}$$

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

$$\begin{array}{}\text{(15)}& d^{\ast }=\underset{\alpha ,\beta :{\alpha }_i>0}{max}\underset{w}{min}L(w,\alpha ,\beta )\le \underset{w}{min}\underset{\alpha ,\beta :{\alpha }_i>0}{max}L(w,\alpha ,\beta )=p^{\ast }\end{array}$$

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 条件

仿射函数

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

最优间隔分类器

回忆如下原始问题

便于求解的最优化问题

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

$$\begin{array}{}\text{(16)}& g_i(w)=-y^{(i)}(w^T{x}^{(i)}+b)+1\le 0\end{array}$$

补充

点到平面的距离

平面的表示

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

假设 $\overrightarrow{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)，展开后可得

$$\begin{array}{}\text{(17)}& A(x-x_0)+B(y-y_0)+C(z-z_0)=0\end{array}$$

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

$$\begin{array}{}\text{(18)}& Ax+By+Cz+D=0\end{array}$$

向量的投影长度

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

$$\begin{array}{}\text{(19)}& \overrightarrow{a}\cdot \frac{\overrightarrow{b}}{|b|}\end{array}$$

点到平面距离

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

$$\begin{array}{}\text{(20)}& d& =\frac{(x-x_0,y-y_0,z-z_0)(A,B,C)}{|(A,B,C)|}\text{(21)}& & =\frac{Ax+By+Cz-(A{x}_0+B{y}_0+C{z}_0)}{\sqrt{A^2+B^2+C^2}}\text{(22)}& & =\frac{Ax+By+Cz+D}{\sqrt{A^2+B^2+C^2}}\end{array}$$

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