支持向量机，决策树与集成学习
人工智能与机器学习基础的作业三和实验三下周三就要截止了，还是有必要简略地了解一下 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 的对偶形式中，所有 \(x_i\) 都是以内积的形式出现的；这启发我们可以用其他的方法定义内积，这就能引出核函数与核技巧
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）
核函数与核技巧
在现实世界中，很多数据集是线性不可分的，我们尝试构造一个数据空间到某个 Hilbert 空间（完备内积空间）的一个映射：
\[
\begin{gather}
\varphi(x):\mathbb R\to \mathcal H\\
f(x)=w^T\varphi(x)+b
\end{gather}
\]
由于 SVM 中所有与数据有关的项都是以内积的形式出现的，我们考虑不显式计算 \(\phi(x)\)，而定义核函数：
\[
K(x_i,x_j)=\varphi(x_i)^T\varphi(x_j)
\]
本质上，所有核函数都可以看作两个向量之间距离的度量，这个度量又对应某个 Hilbert 空间上的内积。
多项式核
Polynomial Kernel in Wikipedia
\[
\begin{gather}
\begin{aligned}
K(\mathbf x,\mathbf y)&=(\mathbf x^\intercal \mathbf y+c)^d \\
&= \sum_{\sum_{i=1}^{n+1}j_i=d}\left(\frac{d!}{\prod_{i=1}^{n+1}j_i!}c^{j_{n+1}}\prod_{i=1}^nx_i^{j_i}y_i^{j_i}\right)\\
&=\sum_{\sum_{i=1}^{n+1}j_i=d}\left(\sqrt{\frac{d!}{\prod_{i=1}^{n+1}j_i!}}\sqrt{c}^{j_{n+1}}\prod_{i=1}^nx_i^{j_i}\right)\cdot\left(\sqrt{\frac{d!}{\prod_{i=1}^{n+1}j_i!}}\sqrt{c}^{j_{n+1}}\prod_{i=1}^ny_i^{j_i}\right)\\
&=\langle\varphi(\mathbf x),\varphi(\mathbf y)\rangle
\end{aligned}
\end{gather}
\]
推导的过程中使用了多项式定理（multinomial therorem）因此，多项式核可以看成一个从 \(n\) 维到 \(l_d=\binom{n+d}{d}\) 维的映射，其中：
\[
\begin{gather}
\varphi(\mathbf x)=(a_1,\cdots,a_l,\cdots,a_{l_d}) \\
a_l=\sqrt{\frac{d!}{\prod_{i=1}^{n+1}j_i!}}\sqrt{c}^{j_{n+1}}\prod_{i=1}^nx_i^{j_i}\\
\text{coefficient of monomial of degree }j:\quad w_j\sim{p\choose j}c^{p-j}
\end{gather}
\]
形式上，它包含关于 \((x_1,x_2,\cdots,x_n)\) 的 \(d\) 次多项式的所有项，其中低次的项乘上了一个与 \(\sqrt{c}\) 有关的一个惩罚项——\(c\) 越大，低次项对内积的影响越大；特别地当 \(d=2\) 时：
\[
\varphi(\mathbf x) = (x^2_1,\cdots,x^2_n,\sqrt{2}x_1x_2,\cdots,\sqrt2x_{n-1}x_n,\sqrt{2c}x_1,\cdots\sqrt{2c}x_n,c)
\]
总结，在多项式核中：
- \(c\) 控制低阶项和高阶项对内积的影响大小，当 \(c=0\) 时，这个核被称为齐次的；
- \(d\) 控制多项式的最高次数；
径向基函数核
径向基函数核（Radial Basis Function kernel, RBF kernel）,有时也称为 Gaussian RBF 核。
\[
\begin{gather}
\begin{aligned}
K(\mathbf x,\mathbf y^\prime)&=\exp\left(-\frac{\|\mathbf x-\mathbf y\|^2}{2\sigma^2}\right)\\
&=\exp(-\gamma \|\mathbf x-\mathbf y\|^2)\\
&=\exp(2\gamma \mathbf x^\intercal\mathbf y-\gamma\|\mathbf x\|^2-\gamma\|\mathbf y\|^2) \\
&= \sum_{j=0}^{+\infty}\frac{(2\gamma\mathbf x^\intercal\mathbf y)^j}{j!}\exp(-\gamma\|\mathbf x\|^2)\exp(-\gamma\|\mathbf y\|^2)\\
&=\sum_{j=0}^{+\infty}\sum_{\sum_{i=1}^kn_i=j}\sqrt{2\gamma}^{j}\exp(-\gamma\|\mathbf x\|^2)\frac{\prod_{i=1}^kx_i^{n_i}}{\sqrt{\prod_{i=1}^kn_i!}}\sqrt{2\gamma}^j\exp(-\gamma\|\mathbf y\|^2)\frac{\prod_{i=1}^ky_i^{n_i}}{\sqrt{\prod_{i=1}^kn_i!}}\\
&=\langle\varphi(\mathbf x),\varphi(\mathbf y)\rangle
\end{aligned} \\
\implies \varphi(\mathbf x) = \exp(-\gamma\|\mathbf x\|^2)\left(a^{(0)}_{\ell_0},a^{(1)}_{1},\cdots,a^{(1)}_{\ell_1},\cdots,a^{(j)}_1,\cdots a^{(j)}_{\ell_j},\cdots\right)\\
\ell_j = {k+j-1 \choose j},\quad a^{(j)}_\ell=\left(\sqrt{2\gamma}\right)^j{\prod_{i=1}^kx_i^{n_i}\over \sqrt{\prod_{i=1}^k n_i!}},\quad \sum_{i=1}^kn_i=j~\land1\le\ell\le\ell_j\\
\text{coefficient of monomial of degree }j:\quad w_j\sim{(2\gamma)^j\over j!}
\end{gather}
\]
形式上，它包含关于 \((x_1,x_2,\cdots,x_n)\) 的所有单项式，一直到无穷次；但是，它的衰减速率比多项式核更快。\(\gamma\) 越小，系数衰减越快，高次项对内积的贡献越小；相反，\(\gamma\) 越大，高次项对内积的贡献越大。
决策树
算法思想
决策树，顾名思义是对决策过程的树形建模：每个结点按照一个相对简单的标准将数据分成两组或多组；以此形成递归的决策结构；
常用的决策树算法往往会做以下的妥协：
- 每个结点（也被称为 Decision Stump）只对一个特征进行分类——这样得到的决策树具有更强的可解释性；斜决策树（oblique decision tree）放宽了这一限制；
- 贪心构造，对每个结点，优先选择本次分裂后最优化某种分类判据的特征；这样就避免了最优决策树（Optimal Decision Tree, ODT）的求解（它是 NP-完全的）；比如 ID3 算法就以熵增最大化（entropy gain）作为分裂判据；
分裂判据
如何衡量决策树分裂的优劣？常见的方法有：
- 错误率（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'）、堆叠法（Stacking, Stacked Generalization）。
它们的基本思想分别是：
- 提升法（Boosting）：递增式地训练弱分类器弥补“损失”；
- 自助聚集法（'Bagging'）：使用自助采样增加模型的随机性，减少方差；
- 堆叠法（Stacking）：训练一个专门的模型合并其他模型的训练结果；
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
泛函梯度下降视角
可能有用的资料
我们可以把有监督学习看作一个泛函优化问题：
\[
\begin{matrix}
\text{learn} & F:\mathcal X \to \mathbb R~\text{(or }\{-1,1\}\text{ for binary task)}\\
\text{that minimizes} & \displaystyle \mathcal L(F)=\sum_{i=1}^n\ell(y_i,F(x_i))
\end{matrix}
\]
在 Boosting 中，我们解的结果局限于一个加法模型的形式。得到这种形式的一个可行的方法是泛函梯度下降，这就是 Gradient Boosting 的基本思想。
泛函梯度下降的算法大致如下所示：
-
初始化
\[
F_0(x)=\arg\min_c\sum_{i}\ell(y_i,c)
\]
-
对于 \(m=1,\cdots,M\)：
\[
g^{(m)}_i=-\frac{\partial \ell(y_i, F(x_i))}{\partial F(x_i)}
\]
- 用 \((x_i, g_i^{(m)})\) 训练 \(f_m(x)\) 这个弱学习器；
- \(F_m = F_{m-1} + \nu f_m\)：注意 \(\nu\) 这个乘子往往是显式计算的最优解（如在 AdaBoost 中）
- 这个迭代过程更数学上的表示可以写成（\(\operatorname{\Phi}_{\mathcal H}\) 指的是在假设类 \(\mathcal H\) 上的投影）：
\[
\begin{gather}
f_m = \operatorname{\Pi}_{\mathcal H}\left(-\nabla \mathcal L(F_{m-1})\right)\\
F_m = F_{m-1} + \eta_mf_m\\
\eta_m = \arg \min_{\eta} \mathcal L(F_{m-1}+\eta f_m)\quad \text{or}\quad\text{Learning Rate}
\end{gather}
\]
指数损失到 AdaBoost 的推导
Logistic Loss 与 LogitBoost
考虑二维 Logistic 损失的情况：
\[
\begin{gather}
\ell(y,p)=-y\log p-(1-y)\log(1-p),\quad p=\sigma(F)\\
\begin{aligned}
\frac{\partial \ell}{\partial F} &= \frac{\partial \ell}{\partial p}\cdot\frac{\partial p}{\partial F} \\
&= \left(-\frac{y}{p}+\frac{1-y}{1-p}\right)\cdot p(1-p)\\
&=p-y\\
&=\sigma(F)-y
\end{aligned} \\
\implies \text{Residual loss:}\quad r_{m,i}= y_i - \sigma(F_{m-1}(x_i))
\end{gather}
\]
因此，我们每步迭代要做（以决策树的集成模型为例）：
- 用决策树拟合 \((x_i, r_{m,i})\) 得到叶子结点区域 \(R_{m,j}\)；
-
对每个叶子结点求最佳输出常数（关于如何求最佳输出常数的内容不在本篇内容范围内）：
\[
c_{m,j} = \arg \min_c\sum_{x\in R_{m,j}}\ell(y_i, F_{m-1}(x_i)+c)
\]
-
更新模型：
\[
F_m(x)=F_{m-1}(x)+\sum_{j}c_{m,j}\mathbb 1[x\in R_{m,j}]
\]
泛函梯度下降
一些可能有用的资料：
策略梯度