本节首先介绍函数间隔和几何间隔的概念，进而引出最优间隔分类器和拉格朗日对偶，最后介绍核函数和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)，则它们是原始问题和对偶问题的解

仿射函数

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

最优间隔分类器

回忆如下原始问题

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

$$
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步用到该等式