Machine Learning (2)（支持向量机）
预备知识：拉格朗日乘子，KKT 条件，拉格朗日对偶
没什么用的东西
下面两个结论从带约束函数极值问题的角度引入拉格朗日乘子和 KKT 条件，实际上用这个逻辑推出的拉格朗日乘子和 KKT 条件对你求解规划问题和理解 SVM 的 SMO 算法没有帮助甚至有阻碍（但是对复习数分高代可能有帮助）。而在下一节中叙述的从对偶理论导出的 KKT 条件则是有用的，这两个东西只是结果形式一样而已。
懒得喷
这两天的学习让我切实地意识到了国内的一些书籍和网络博客（暂时特指面向技术人员的 AI 博客）有多么不靠谱。
在写一个东西的证明时常常喜欢引入一些无关的东西，然后后面的证明当中根本不用。最常见的是证明拉格朗日乘子的时候先引入 Hessian，证明时却完全不用，或者索性不证。证明过程没有严格的数学推导，全是一些低维的几何直观和特例，因此常常因为其直觉错误所以得到一些荒谬的结论。各种专有的名词也常常是混用的，让人很摸不着头脑。
今后进行搜索时，但凡内容不全是技术而涉及一点数学，就应当屏蔽来自未刊载的低质量结果。原论文通常靠谱地多，但是读起来工程量太大，读综述文章应该是一个比较好的选择。
Theorem 1. 考虑条件极值问题
$$
\begin{align}
\min~ & f(\boldsymbol{x}) \\
\text{s.t. } & g_i(\boldsymbol{x}) = 0 & i = 1, …, m
\end{align}
$$
定义拉格朗日函数
$$
L(\boldsymbol{x}, \boldsymbol{\lambda}) = f(\boldsymbol{x}) + \sum_{i=1}^m \lambda_i g(\boldsymbol{x})
$$
原函数在条件下取极值的必要条件（同时是驻点的充要条件）是
$$
\frac{\partial L}{\partial \boldsymbol{x}} = \boldsymbol{0}, \frac{\partial L}{\partial \boldsymbol{\lambda}} = \boldsymbol{0}
$$
如果你可以接受“忽略二阶小量”这种阴间表述，那么你可以参考博客[1]，否则可以看下面我写的正确性未知的推导。
设曲面 $C_i = \{\boldsymbol{x} | g_i(\boldsymbol{x}) = 0\}, C = \cap_{i=1}^m C_i$，若 $\boldsymbol{x}\in C, \boldsymbol{x} + \boldsymbol{\varepsilon}\in C$，则对于任意的 $i$ 都有
$$
0 = g_i(\boldsymbol{x} + \boldsymbol{\varepsilon}) - g_i(\boldsymbol{x}) = \varepsilon^T\nabla g_i(\boldsymbol{x}) + O(||\boldsymbol{\varepsilon}||^2)
$$
换言之
$$
\boldsymbol{\varepsilon}^T\nabla g_i(\boldsymbol{x}) = O(||\boldsymbol{\varepsilon}||^2)
$$
考虑子空间 $V = \langle\nabla g_1(\boldsymbol{x}), …, \nabla g_m(\boldsymbol{x})\rangle$，欧氏空间中有 $\mathbb{R}^n = V \oplus V^\perp$，那么我们假设
$$
\boldsymbol{\varepsilon} = \boldsymbol{\varepsilon}_v + \boldsymbol{\varepsilon}_\perp \text{ where } \boldsymbol{\varepsilon}_v \in V, \boldsymbol{\varepsilon}_\perp \in V^\perp
$$
那么有 $\boldsymbol{\varepsilon}_v^T\nabla g_i(x) = O(||\boldsymbol{\varepsilon}||^2)$，由于 $||\nabla g_i(\boldsymbol{x})||$ 是常量，这里必然有 $||\boldsymbol{\varepsilon}_v|| = O(||\boldsymbol{\varepsilon}||^2)$，进一步可以推出 $||\boldsymbol{\varepsilon}_\perp|| = \Theta ||\varepsilon||$。
$\boldsymbol{x}$ 若是 $f(\boldsymbol{x})$ 在约束下的一个驻点，就必然有任取向量列 $\boldsymbol{\varepsilon}_1, \boldsymbol{\varepsilon}_2, …$，且
$$
\lim_{n\rightarrow \infty} ||\boldsymbol{\varepsilon}_n|| = 0
$$
都有
$$
\lim_{n\rightarrow \infty} \frac{f(\boldsymbol{x} + \boldsymbol{\varepsilon}_n) - f(\boldsymbol{x})}{||\boldsymbol{\varepsilon}_n||} = 0
$$
分子展开成二阶小量，并将 $\boldsymbol{\varepsilon}_n$ 做直和分解得到
$$
\lim_{n\rightarrow \infty}\frac{\boldsymbol{\varepsilon}_{n\perp}^T\nabla f(\boldsymbol{x}) + \boldsymbol{\varepsilon}_{nv}^T\nabla f(\boldsymbol{x}) + O(||\boldsymbol{\varepsilon}_n||^2)}{||\boldsymbol{\varepsilon}_n||} = 0
$$
观察上面的式子的长度关系并回忆 $\boldsymbol{\varepsilon}_n$ 的任意性，可以发现你必须有
$$
\forall \boldsymbol{\varepsilon}\in V^\perp, \boldsymbol{\varepsilon}^T\nabla f(\boldsymbol{x}) = 0
$$
这里我们偷偷使用了 $\boldsymbol{\varepsilon}_\perp$ 可以取到所有的方向，严格证明考虑使用隐函数存在性定理，这里跳过。
因此 $\nabla f(\boldsymbol{x})\in V$，换言之存在 $\lambda_1, …, \lambda_m$ 使得
$$
\nabla f(\boldsymbol{x}) + \sum_{i=1}^m \lambda_i \nabla g_i(\boldsymbol{x}) = 0
$$
反过来看，上面的推导都是充分必要的。
这蕴含着 $\frac{\partial L}{\partial \boldsymbol{x}} = \boldsymbol{0}$，同时你还要求 $\boldsymbol{x}$ 都是 $C$ 上的点，这等价于 $\frac{\partial L}{\partial \boldsymbol{\lambda}} = \boldsymbol{0}$。$\square$
考虑不等式约束条件，必要条件则是
Theorem 2. 考虑条件极值问题
$$
\begin{align}
\min~ & f(\boldsymbol{x}) \\
\text{s.t. } & g_i(\boldsymbol{x}) \leq 0 & i = 1, …, m
\end{align}
$$
类似地定义拉格朗日函数，那么最优解相当于在满足如下条件时优化 $L$：
$$
\begin{cases}
\frac{\partial L}{\partial \boldsymbol{x}} = \boldsymbol{0} \\
g_i(\boldsymbol{x}) \leq 0 \\
{\lambda}_i \geq 0 \\
g_i(\boldsymbol{x})\lambda_i = 0
\end{cases}
$$
这里我们不打算重新写一遍严格证明，只给出一个大概的框架：
对于一个极值点 $\boldsymbol{x}$
- 若 $g_i(\boldsymbol{x}) < 0$，那么此时必有 $\lambda_i = 0$（根据条件 $4$），此时称 $i$ 是 interior 的。
- 否则有 $g_i(\boldsymbol{x}) = 0$，此时称 $i$ 是 boundary 的。
我们对 $m$ 个条件是 interior / boundary 的分类，拆成 $2^m$ 个优化问题。
单独考虑一个优化问题，我们发现它规约到只保留 boundary 的 $i$ 的等式约束问题，可以用拉格朗日乘子法解决。但是此时 $\nabla f(\boldsymbol{x})$ 必须指向可行域外部，也就是必须有 $\lambda_i > 0$ 全部成立，否则这个解一定是只在边界上最优，在全局上并不最优。（严格证明时，可能考虑将上述证明过程中取边界上的点列改成取边界上的点列来得到 $\nabla f$ 是 $\nabla g$ 的线性组合，然后取可行域内部的点列来得到 $\lambda_i$ 的符号）
另外此时你发现满足约束条件时 $L(\boldsymbol{x}, \boldsymbol{\lambda}) = f(\boldsymbol{x})$，所以说结论确实是对的。
未知正确性的批话
我严重怀疑书上和绝大部分资料中常见的说法：
一个有约束的优化问题相当于对其拉格朗日函数的无约束优化问题。
是错误的。我们考虑这个优化问题：
$$
\begin{matrix}
\min & xy \\
\text{s.t.} x - y = 0
\end{matrix}
$$
其拉格朗日函数为
$$
L(x, y, \lambda) = xy + \lambda(x-y)
$$
它的 Hessian 总是不是正定的，这个函数根本没有极值点，但是有一个驻点是 $(0, 0, 0)$。
似乎下面提到的拉格朗日对偶理论和拉格朗日乘子只是一种长得很像的东西，实际上根本不是一回事。
考虑标准型的优化问题
$$
\begin{matrix}
\min & f(\boldsymbol{x}) \\
\text{s.t.} & y_i(\boldsymbol{x}) \leq 0 \\
& h_i(\boldsymbol{x}) = 0
\end{matrix}
$$
其中 $f(\boldsymbol{x})$ 定义域为 $\mathcal{D}$。其最优解为 $f^*$。
定义广义拉格朗日函数
$$
\mathcal{L}(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\nu}) = f(\boldsymbol{x}) + \boldsymbol{\lambda}^T\boldsymbol{y}(\boldsymbol{x}) + \boldsymbol{\nu}^T\boldsymbol{h}(\boldsymbol{x})
$$
这里的 $\boldsymbol{\lambda}$ 和 $\boldsymbol{\nu}$ 称为对偶变量，感性理解起来其相当于某种 regularization parameter 来惩罚违反的限制。
定义拉格朗日对偶函数
$$
g(\boldsymbol{\lambda}, \boldsymbol{\nu}) = \inf_{\boldsymbol{x}\in\mathcal{D}} \mathcal{L}(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\nu})
$$
考察拉格朗日函数各项符号立即得到当 $\boldsymbol{\lambda}\geq \boldsymbol{0}$ 时
$$
f^* \geq f(\bar{\boldsymbol{x}}) \geq \mathcal{L}(\bar{\boldsymbol{x}}, \boldsymbol{\lambda}, \boldsymbol{\nu}) \geq g(\boldsymbol{\lambda}, \boldsymbol{\nu})
$$
可以看到 $g$ 给出了 $f^*$ 的下界，于是我们可以讨论最紧的下界是多少。下面的优化问题称为原问题的对偶问题
$$
\begin{matrix}
\max & g(\boldsymbol{\lambda}, \boldsymbol{\nu}) \\
\text{s.t.} & \boldsymbol{\lambda} \geq \boldsymbol{0}
\end{matrix}
$$
对偶问题和原问题不总是等价的，但是我们有如下的引理：
Lemma(Slater, 1950). 凸优化问题的原问题和对偶问题有相同的最优值（strong duality）。
证明还没看，先相信。
如果一个问题有 strong duality，那么有
$$
\begin{align}
f(\boldsymbol{x}^*) &= g(\boldsymbol{\lambda}^*, \boldsymbol{\nu}^*) \\
&= \inf_{x\in\mathcal{D}} \mathcal{L}(\boldsymbol{x}, \boldsymbol{\lambda}^*, \boldsymbol{\nu}^*) \\
&\leq \mathcal{L}(\boldsymbol{x}^*, \boldsymbol{\lambda}^*, \boldsymbol{\nu}^*) \\
&\leq f(\boldsymbol{x}^*)
\end{align}
$$
这说明两个不等号都必须取等，因此有互补松弛条件（Complementary slackness）
$$
\lambda_iy_i(\boldsymbol{x}) = 0
$$
如果一个问题满足 strong duality，那么以下条件合起来构成对偶问题的 KKT 条件：
- 驻点条件 $\partial \mathcal{L} / \partial \boldsymbol{x} = 0$；
- 原始可行性 $y_i(\boldsymbol{x})\leq 0, h_i(\boldsymbol{x}) = 0$；
- 对偶可行性 $\boldsymbol{\lambda}\geq \boldsymbol{0}$；
- 互补松弛性 $\lambda_iy_i(\boldsymbol{x}) = 0$。
这是原问题的最优解满足的必要条件。
SVM
基本模型
考虑找一个超平面将正负类样本分开。用其他点到超平面的距离最大值来度量划分的好坏。令 $\boldsymbol{w}$ 为超平面的法向量，$b$ 为偏置（超平面到原点的距离），那么这个平面将正负类（正类记 $y_i = 1$，负类记 $y_i = -1$）完全分开即要求
$$
y_i(\boldsymbol{w}_i^T\boldsymbol{x}_i + b) \geq 1
$$
点到超平面的距离为
$$
\frac{|\boldsymbol{w}^T\boldsymbol{x}+b|}{||\boldsymbol{w}||}
$$
约束条件保证了所有点到超平面的距离大于 $1/||\boldsymbol{w}||$。因此我们最大化这个量来得到最好的超平面。SVM 本质上相当于下面的规划问题：
$$
\begin{matrix}
\min &\frac 12 ||\boldsymbol{w}||^2 \\
\text{s.t.} & y_i(\boldsymbol{w}^T\boldsymbol{x}_i + b)\geq 1
\end{matrix}
$$
方便起见定义
$$
f(\boldsymbol{x}) = \boldsymbol{w}^T\boldsymbol{x} + b
$$
发现存在一部分向量到平面的距离恰好为 $1/||\boldsymbol{w}||$，这些向量称为支持向量。
软间隔
实际情况中可能不能完美地将样本点分开，于是考虑将“违反限制”的多少加入目标函数当中。取惩罚系数 $C > 0$ 和损失函数 $\mathcal{L}$，优化
$$
\frac 12 ||\boldsymbol{w}||^2 + C\sum_{i=1}^m\mathcal{L}(y_if(\boldsymbol{x}_i))
$$
其中 $\mathcal{L}(x)$ 可以取
- 0/1 Loss $(1-\mathrm{sgn}(x - 1)) / 2$。
- Hinge Loss $\max(0, 1 - x)$。
- Exponential Loss $\exp(-x)$。
- Logistic Loss $\log(1+\exp(-x))$。
原来的问题相当于 $C=\infty$ 的特例。四个损失函数中只有 Hinge Loss 是对规划问题友好的。考虑优化
$$
\frac 12 ||\boldsymbol{w}||^2 + C\sum_{i=1}^m\max(0, 1-y_if(\boldsymbol{x}_i))
$$
这里 Hinge Loss 之于 0/1 Loss 有点类似于 Sparse Recovery 当中的 1 范数之于 0 范数，我们可以使用类似的技术，添加变量 $\xi_i > 0$，优化
$$
\begin{matrix}
\min & \frac 12 ||\boldsymbol{w}||^2 + C\sum_{i=1}^m\xi_i \\
\text{s.t.} & -\xi_i \leq 0 \\
& 1-y_if(\boldsymbol{x}_i)-\xi_i\leq 0
\end{matrix}
$$
模型求解
上面的问题是一个凸二次规划，但是有更高效的做法。
凸二次规划满足 strong duality，所以我们转而求解对偶问题。考察拉格朗日函数
$$
\mathcal{L}(\boldsymbol{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\mu}) = \frac 12 ||\boldsymbol{w}||^2 + C\sum_{i=1}^m\xi_i + \sum_{i=1}^m\alpha_i(1-y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)-\xi_i)-\mu_i\xi_i
$$
对偶问题的目标为
$$
g(\boldsymbol{\alpha}, \boldsymbol{\mu}) = \inf \mathcal{L}(\boldsymbol{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\mu})
$$
固定对偶变量之后的拉格朗日函数是凸的，所以其唯一驻点对应的函数值就是其下确界，驻点和对偶变量范围的条件合计起来为
$$
\begin{cases}
&\boldsymbol{w} - \sum_{i=1}^m\alpha_iy_i\boldsymbol{x}_i = \boldsymbol{0} \\
&\sum_{i=1}^m \alpha_iy_i = 0 \\
&\alpha_i + \mu_i = C \\
&\alpha_i, \mu_i \geq 0 \\
\end{cases}
$$
用等式条件可以消掉原来的变量，目标函数变成：
$$
\sum_{u-1}^m \alpha_i - \frac 12\sum_{1\leq i, j \leq m} \alpha_i\alpha_j y_iy_j\boldsymbol{x}_i^T\boldsymbol{x}_j
$$
现在目标函数不包含 $\boldsymbol{w}$，条件 $(1)$ 没有用，将 $(3), (4)$ 整合，得到对偶问题的一个比较简洁的形式：
$$
\begin{matrix}
\max & \sum\limits_{u-1}^m \alpha_i - \dfrac 12\sum\limits_{1\leq i, j \leq m} \alpha_i\alpha_j y_iy_j\boldsymbol{x}_i^T\boldsymbol{x}_j \\
\text{s.t.} & \sum\limits_{i=1}^m \alpha_iy_i = 0 \\
& 0\leq \alpha_i\leq C
\end{matrix}
$$
求解这个优化问题以后，可以用驻点条件得到 $\boldsymbol{w}$，然后代价是关于 $b$ 的凸函数，可以用二分之类的算法得到。
要解决这个问题，可以使用 SMO 算法：每次选择两个 $\alpha_i, \alpha_j$，固定其他的量，然后优化这两个量。
核函数
对于非线性可分数据，我们可以考虑将其打到高维空间。这个映射记为 $\phi(\boldsymbol{x})$。此时我们可能需要高维空间中的距离，即求解
$$
\phi(\boldsymbol{x})^T\phi(\boldsymbol{y})
$$
这里我们定义
Definition 1(Kernel Function). $\kappa(\cdot, \cdot)$ 是核函数（Kernel）若存在映射 $\phi$ 使得 $\kappa(\boldsymbol{x}, \boldsymbol{y}) = \langle\phi(\boldsymbol{x}), \phi(\boldsymbol{y})\rangle$
这样定义核函数导致你不常能拿到映射 $\phi$，但是基于下面的定义：
Definition 2(Positive Definite Kernel) 称 $\kappa$ 是正定（Positive Definite）的，若对于任意的 $x_1, …, x_m$ 都有矩阵
$$
\begin{pmatrix}
\kappa(x_1, x_1) & \cdot & \kappa(x_1, x_m) \\
\vdots & & \vdots \\
\kappa(x_m, x_1) & \cdot & \kappa(x_m, x_m) \\
\end{pmatrix}
$$
正定。
有如下的 Kernel Trick[2]：如果你的一个算法用到了一个正定核 $\kappa_1$，那么可以换成另一个正定核 $\kappa_2$。
比如说对于 LDA，我们可以只用核定义 $S_b, S_w$，得到 KLDA，实现某些非线性回归。
在 SVM 中我们疑似只用到了欧氏距离这个核，于是可以换成别的核函数，从而解决非线性可分的问题。
- 1.Lagrange 乘數法 | 線代啟示錄 ↩
- 2.Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, 34 ↩