支持向量机，决策树与集成学习
人工智能与机器学习基础的作业三和实验三下周三就要截止了，还是有必要简略地了解一下 SVM，决策树和集成学习是什么。这篇文章记录我完成作业时的简略笔记。
关于该文章的书写进度
这篇文章仍在撰写中，将在完成作业与实验时撰写完成。
支持向量机
可能有用的资料：
本篇文章还没有完成的部分：
- SVM 与 VC 维理论的联系
- SVM 优化——归约到二次规划问题——Sequential Minimal Optimization
- Gradient Boosting 与泛函梯度下降（感觉泛函分析在机器学习理论中还挺重要的，有机会可以好好研究）
普通 SVM
目标函数
下面我们证明对于线性可分数据集，（硬间隔）SVM 的目标是：
\[
\min_{w,b}\frac{1}{2}\|w\|^2\quad \text{s.t.}\quad y_i(w^Tx_i+b)\ge 1
\]
回想一下，由于 SVM 的目标是在线性分隔数据的同时最大化最小间隔；根据几何学的知识，点 \(x\) 到超平面 \(f_{w,b}(x) = w^T x + b = 0\) 的距离为 \(\frac{|f_{w,b}(x)|}{\|w\|}\)；因此所有样本的最小间隔可以表示为：
\[
\begin{aligned}
\gamma &= \min_{i}\frac{|f_{w,b}(x_i)|}{\|w\|} \\
&= \min_i\frac{y_if_{w,b}(x_i)}{\|w\|}
\end{aligned}
\]
该等号成立是因为 SVM 中我们只考虑分类正确的样本，而标签的取值被定义为 \(y_i \in \{+1, -1\}\)。这样，我们可以得到 SVM 的目标函数：
\[
\max_{w,b}\gamma = \max_{w,b}\min_i \frac{y_i f_{w,b}(x_i)}{\|w\|} = \max_{w,b}\min_i \frac{y_i (w^Tx_i+b)}{\|w\|}
\]
为了简化这个目标函数，需要利用 \(w,b\) 具有的一个性质——伸缩不变性，即，对于缩放操作 \(w^\ast = cw,~b^\ast = bw\)，\(\lambda\) 不变，因此我们可以对 \(w,b\) 增加正则化条件：
\[
\begin{gather}
y_i(w^Tx_i+b)\ge 1,\quad\exists i~~\text{s.t.}~\text{``}=\text{''} \\
\implies \gamma = \frac{1}{\|w\|} \\
\implies \arg\max_{w,b}\gamma = \arg\min_{w,b}\frac{1}{2}\|w\|^2
\end{gather}
\]
这样我们就完成了硬间隔 SVM 的目标函数推导。
Primal-Dual
详细过程见软间隔 SVM 的推导，这里直接放上结论（软间隔 SVM 只是加上了一项）：
\[
\begin{matrix}
\displaystyle\max_{\boldsymbol \alpha}&\displaystyle\sum_{i=1}^N\alpha_i -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)\\
\text{s.t.} & \displaystyle \sum_{i=1}^N\alpha_iy_i = 0, \quad \alpha_i\ge 0
\end{matrix}
\]
软间隔 SVM
关于严谨性
此“软间隔”SVM 指的其实是 L2 正则化的软间隔 SVM，由于这是我完成作业的笔记，所以会出现一些不严谨的地方。
目标函数
我们引入松弛因子，将正则化条件变化为：
\[
y_i(w^Tx_i + b) \ge 1 - \zeta_i
\]
在这个时候，最小化 \(\|w\|^2\) 并不等价于最大化 \(\lambda\)，但是，我们仍然模仿硬间隔 SVM 的形式，写出软间隔 SVM 的目标函数：
\[
\min_{w,b,\zeta}\frac{1}{2}\|w\|^2,\quad \sum_{i}\zeta_i\le \epsilon
\]
使用 Lagrange 乘子法，这个问题也可以转化为：
\[
\begin{gather}
\min_{w,b,\zeta}\frac{1}{2}\|w\|^2+C\sum_{i=1}^n\zeta_i^2 \\
\text{with}\quad y_i(w^Tx_i+b)\ge 1 - \zeta_i,~\zeta_i \ge 0
\end{gather}
\]
最小化范数与 VC 维理论
不管是在传统 SVM 中还是软间隔 SVM 中我们都在最小化一个 \(\frac{1}{2}\|w\|^2\)，这其实对应着一个原则——使用尽可能小、但仍包含正确/良好解的假设空间。这个原则叫做结构化风险最小化（structural risk minimization）。
这个原则其实来源于 VC 维理论（Vapnik-Chervonenkis dimension theory），由于：
\[
\text{VC dimension} \le \frac{R^2}{\gamma^2}\quad\text{with}\quad\gamma \le \frac{1}{\|w\|^2}
\]
我们在最小化 \(\frac{1}{2}\|w\|^2\) 的同时，也在最小化 \(w\) 的 VC 维，使模型尽可能地简单。
TODO：软间隔 SVM 原理的深入分析
Primal-Dual
由 Lagrange 乘子法：
\[
\begin{gather}
\min_{w}f(w)\\
g_{i} \le 0,~\forall 1\le i\le k\\
h_{i} = 0,~\forall 1\le i\le l\\
\implies \mathcal L(w,\boldsymbol\alpha,\boldsymbol\beta) = f(w)+\sum_{i}\alpha_i g_i(w) + \sum_{j}\beta_j h_j(w)
\end{gather}
\]
代入：
\[
\begin{gather}
f(w,b,\zeta) = \frac{1}{2}\|w\|^2+C\sum_{i=1}^{N}\zeta_i^2\\
g_i = 1 - \zeta_i - y_i(w\cdot x_i+b),\quad g_{i+N} = -\zeta_i\\
\implies \mathcal L(w,b,\zeta,\boldsymbol \alpha,\boldsymbol \mu) = \frac{1}{2}\|w\|^2+C\sum_{i=1}^N\zeta_{i}^2-\sum_{i=1}^N\alpha_i(y_i(w\cdot x_i+b) - (1-\zeta_i))-\sum_{i=1}^N\mu_{i}\zeta_i \\
\implies p^\ast = \min_{w,b,\zeta}f(w,b,\zeta)=\min_{w,b}\max_{\boldsymbol \alpha,\boldsymbol\mu:\alpha_i,\mu_i\ge 0}\mathcal L(w,b,\zeta,\boldsymbol \alpha,\boldsymbol \mu) \\
d^\ast = \max_{\boldsymbol\alpha,\boldsymbol \mu:\alpha_i,\mu_i\ge 0}\min_{w,b,\zeta}\mathcal L(w,b,\zeta,\boldsymbol \alpha,\boldsymbol \mu)
\end{gather}
\]
为了写出问题的对偶形式，我们要求出满足 Karush-Kuhn-Tucker 条件的一组 \((w,b,\boldsymbol \alpha, \boldsymbol \mu)\)，首先带入 KKT 条件的第一个要求（驻点）：
\[
\begin{gather}
\frac{\partial \mathcal L}{\partial w} = w - \sum_{i=1}^N\alpha_iy_ix_i=0\implies w=\sum_{u=1}^N\alpha_iy_ix_i\\
\frac{\partial \mathcal L}{\partial b} = -\sum_{i=1}^N\alpha_iy_i=0\implies \sum_{i=1}^N\alpha_iy_i = 0\\
\frac{\partial \mathcal L}{\partial \zeta_i} = 2C\zeta_i-\alpha_i-\mu_i=0\implies \zeta_i=\frac{\alpha_i + \mu_i}{2C}
\end{gather}
\]
考虑用 KKT 条件的其他项简化该式：
\[
\begin{gather}
\mu_i\zeta_i=0,\quad \mu_i\ge 0,\quad \zeta_i\ge 0 \\
\implies \mu_i=0\quad \implies \zeta_i = \frac{\alpha_i}{2C}
\end{gather}
\]
带入软间隔 SVM 的对偶形式 \(d^\ast\) 可以得到：
\[
\begin{gather}
\frac{1}{2}\|w\|^2=\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) \\
C\sum_{i=1}^N\zeta_i^2 = \frac{1}{4C}\sum_{i=1}^N\alpha_i^2\\
\begin{aligned}
-\sum_{i=1}^N\alpha_i(y_i(w\cdot x_i+b) - (1-\zeta_i))&= -\sum_{i=1}^N\alpha_iy_ix_i\cdot w-b\sum_{i=1}^N\alpha_iy_i+\sum_{i=1}^N\alpha_i-\sum_{i=1}^N\alpha_i\zeta_i\\
&=-\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-0+\sum_{i=1}^N\alpha_i-\frac{1}{2C}\sum_{i=1}^N\alpha^2
\end{aligned}\\
-\sum_{i=1}^N\mu_i\zeta_i=0\\
\implies \min_{w,b,\zeta}\mathcal L(w,b,\zeta,\boldsymbol \alpha, \boldsymbol \mu)=\sum_{i=1}^N\alpha_i - \frac{1}{4C}\sum_{i=1}^N\alpha_i^2-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)
\end{gather}
\]
整理知，软间隔 SVM 的对偶形式为：
\[
\begin{matrix}
\displaystyle\max_{\boldsymbol \alpha}&\displaystyle\sum_{i=1}^N\alpha_i - \frac{1}{4C}\sum_{i=1}^N\alpha_i^2-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)\\
\text{s.t.} & \displaystyle \sum_{i=1}^N\alpha_iy_i = 0, \quad \alpha_i\ge 0
\end{matrix}
\]
SVM 的优化
将 SVM 转化为对偶问题后，我们还要对对偶问题进行优化。下面以普通 SVM 为例，它实质上就是一个二次规划问题：
\[
\begin{matrix}
\displaystyle\max_{\boldsymbol \alpha}&\displaystyle\mathbf{1}^T\boldsymbol\alpha-\frac{1}{2}\boldsymbol \alpha^T(X^TX\odot yy^T)\boldsymbol \alpha\\
\text{s.t.} & \boldsymbol \alpha^Ty = 0, \quad \alpha_i\ge 0
\end{matrix}
\]
这样就有很多经典的算法可以求解此类问题了，比如序列最小优化算法（Sequential Minimal Optimization, SMO）
决策树
分裂判据
如何衡量决策树分裂的优劣？常见的方法有：
- 错误率（classification error）：\(R\) 中的一个随机样本，我们永远预测最多的标签，预测错误的概率；
- 基尼不纯度（Gini Impurity）：\(R\) 中的一个随机样本，我们按照标签的分布随机预测一个标签，预测错误的概率；
- 熵增/信息增益（entropy/information gain）：已知分类对标签进行编码的期望位数；
具体来说，我们定义一个域（结点）\(R\) 的类占比：
\[
\begin{gather}
p_k=\mathbb P(Y=k\mid X\in R),\quad k=1,2,\cdots,K \\
I_{\text{err}}(R)=1-\max_{k}p_k \\
I_{\text{gini}}(R)=\sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_k^2 \\
I_{\text{ent}}(R) = -\sum_{k=1}^Kp_k\log p_k
\end{gather}
\]
分类判据的优劣
分类错误率的问题——可能对部分“看似有效但局部不稳定”的分裂不敏感。
用分类错误率作为分类标准可能导致过拟合，
剪枝
决策树的剪枝分为两种：预剪枝（pre-pruning）和后剪枝（post-pruning）；预剪枝有时候也成为提前停止（early stopping）；
- 主要区别：“预剪枝”在生成决策树的过程中判断是否继续分裂，“后剪枝”在计算完过拟合的决策树后再判断把那些子树替换为叶结点后“损失”最小；“预剪枝”计算简单，但不精准（比如异或问题很难判断是否应当停止）；“后剪枝”计算复杂度相对较高，但是更为准确；
- 使用场景：“后剪枝”适用于数据集较小，对时间要求较低的场景，“预剪枝”相反。
集成学习
可能有用的资料：
常见的集成学习方法有提升法（Boosting）和自助聚集法（Bootstrap aggregating, 'Bagging'）
由于作业的原因，在这里不花费篇幅讲述集成学习的基本思想。
AdaBoost
AdaBoost 算法的流程如下：
- 初始化数据集权重：\(\alpha_i = \frac{1}{N}\)；
- 对于 \(t = 1,\cdots, T\)：
- 用 \(\alpha_i\) 训练模型 \(f_t\)；
- \(\hat{w}_t = \frac{1}{2}\ln\left(1-\epsilon_t\over \epsilon_t\right)\)；
- \(\alpha_i \gets \begin{cases}\alpha_i e^{-\hat{w}_t} & f_t(x_i)=y_i\\ \alpha_i e^{\hat{w}_t} & f_t(x_i)\ne y_i\end{cases}\)，也可以写作 \(\alpha_{i,t+1} = \alpha_{i,t} \exp\left(-y_i\hat w_tf_t(x_i)\right)\)
- 归一化 \(\alpha_i\)；
- \(\hat{y} = \operatorname{sgn}\left(\sum_{t=1}^T\hat{w}_t f_t(\boldsymbol{x})\right)\)；
训练样本权重的更新
\[
\alpha_{i,t+1} = \alpha_{i,t} \exp\left(-y_i\hat w_tf_t(x_i)\right)
\]
其中 \(\hat w_t\) 是第 \(t\) 个模型的权重。我们之所以要用这种方式更新样本权重，是因为只有这样更新才能允许我们将指数损失转化成一个漂亮的连乘形式。看了模型权重更新的证明就可以明白了。
更一般的，不管是训练样本权重的更新，还是模型权重的更新，都是指数损失唯一确定的——它们都可以从泛函梯度下降（functional gradient descent, FGD）的视角去理解。
模型权重的更新
AdaBoost 最终的分类器是：
\[
F(x)=\operatorname{sgn}(\operatorname{score}(x)),\quad \operatorname{score}(x) = \sum_{t=1}^T\hat{w}_tf_t(x)\\
\]
我们要最小化训练误差，这是一个 0-1 损失，我们可以使用指数损失对其进行放缩，并用 AdaBoost 的性质进行化简：
\[
\begin{aligned}
\frac{1}{N}\sum_{i=1}^N\mathbb 1[F(x_i)\ne y_i] &\le \frac{1}{N}\sum_{i=1}^N\exp(-y_i\operatorname{score}(x_i)) \\
&=\frac{1}{N}\sum_{i=1}^N\exp\left(-y_i\sum_{t=1}^T\hat{w}_tf_t(x_i)\right) \\
&= \frac1N\sum_{i=1}^N\prod_{t=1}^T\exp\left(-y_i\hat{w}_tf_t(x_i)\right) \\
&= \sum_{i=1}^N\alpha_{i,1}\prod_{t=1}^T\exp\left(-y_i\hat{w}_tf_t(x_i)\right)\\
&= \prod_{t=1}^T\sum_{i=1}^N\alpha_{i,t}\exp\left(-y_i\hat w_tf_t(x_i)\right)\\
&\triangleq \prod_{t=1}^TZ_t
\end{aligned}
\]
倒数第三个等式成立是因为我们初始化 \(\alpha_{i,1}=\frac{1}{N}\)，倒数第二个等式成立来自样本权重的更新公式。
由上面的不等式可知，控制 \(\prod_{t=1}^TZ_t\) 的方式相当于控制指数损失，从而控制训练误差，使用贪心的策略，每次优先选择最小的 \(Z_t\)。
设训练样本的权重分布为 \(D_t\)，定义加权错误率 \(\epsilon_t\)：
\[
\begin{aligned}
\epsilon_t&\triangleq P_{x,y\sim D_t}(f_t(x)\ne y)\\
&=\sum_{i=1}^n\alpha_{i,t}\mathbb 1[f_t(x_i)\ne y_i]
\end{aligned}
\]
我们可以用 \(\epsilon_t\) 来表示 \(Z_t\)，通过最小化 \(Z_t\) 得到 \(\hat w_t\) 的取值：
\[
\begin{gather}
\begin{aligned}
Z_t &= \sum_{i=1}^n\alpha_{i,t}\exp\left(-y_i\hat{w}_tf_t(x_i)\right)\\
&= \mathbb E_{x,y\sim D_t}\left[\exp(-y_t\hat w_t f_t(x))\right] \\
&=\mathbb E_{x,y\sim D_t}\left[\exp(-y_t\hat w_t f_t(x))\mid f_t(x)=y\right]P_{x,y\sim D_t}(f_t(x)=y)\\
&\quad+\mathbb E_{x,y\sim D_t}\left[\exp(-y_t\hat w_t f_t(x))\mid f_t(x)\ne y\right]P_{x,y\sim D_t}(f_t(x)\ne y)\\
&= e^{-\hat w_t}(1-\epsilon_t)+e^{\hat w_t}\epsilon_t\\
&\ge 2\sqrt{\epsilon_t(1-\epsilon_t)}
\end{aligned}\\
\frac{\partial L}{\partial \hat w_t} = -e^{-\hat w_t}(1-\epsilon_t)+e^{\hat w_t}=0\\
\implies \hat w_t =\frac{1}{2}\ln\frac{1-\epsilon_t}{\epsilon_t}
\end{gather}
\]
Gradient Boosting
泛函梯度下降