机器学习知识复习

机器学习

机器学习基础

偏差与方差

偏差.

偏差度量了学习算法预测的期望值与真实结果的偏离程度, 即 刻画了学习算法本身的拟合能力 .
方差.

方差表示模型预测的期望值与预测值之间的平方和，度量了同样大小的训练集的变动所导致的学习性能的变化, 即 刻画了数据扰动所造成的影响 .
噪声.

噪声表达了在当前任务上任何学习算法所能达到的期望泛化误差的下界, 即 刻画了学习问题本身的难度 . 巧妇难为无米之炊, 给一堆很差的食材, 要想做出一顿美味, 肯定是很有难度的.

导致偏差和方差的原因

偏差

通常是由于我们对学习算法做了错误的假设，或者模型的复杂度不够；
- 比如真实模型是一个二次函数，而我们假设模型为一次函数，这就会导致偏差的增大（欠拟合）；
- 由偏差引起的误差通常在训练误差上就能体现，或者说训练误差主要是由偏差造成的
方差

通常是由于模型的复杂度相对于训练集过高导致的；
- 比如真实模型是一个简单的二次函数，而我们假设模型是一个高次函数，这就会导致方差的增大（过拟合）；
- 由方差引起的误差通常体现在测试误差相对训练误差的增量上。

深度学习中的偏差与方差

神经网络的拟合能力非常强，因此它的训练误差（偏差）通常较小；
但是过强的拟合能力会导致较大的方差，使模型的测试误差（泛化误差）增大；
因此深度学习的核心工作之一就是研究如何降低模型的泛化误差，这类方法统称为

正则化方法
1. batch normalization
  
  1.1. BN的作用
  - BN 是一种正则化方法（减少泛化误差），主要作用有：
    - 加速网络的训练（缓解梯度消失，支持更大的学习率）
    - 防止过拟合
    - 降低了参数初始化的要求。
  1.2. 为什么要用BN?
  
  训练的本质是学习数据分布。如果训练数据与测试数据的分布不同会降低模型的泛化能力。因此，应该在开始训练前对所有输入数据做归一化处理。
  
  而在神经网络中，因为每个隐层的参数不同，会使下一层的输入发生变化，从而导致每一批数据的分布也发生改变；致使网络在每次迭代中都需要拟合不同的数据分布，增大了网络的训练难度与过拟合的风险。
  
  1.3. BN的基本原理
  - BN 方法会针对每一批数据，在网络的每一层输入之前增加归一化处理，使输入的均值为 0，标准差为 1。目的是将数据限制在统一的分布下。
  - 具体来说，针对每层的第 k 个神经元，计算这一批数据在第 k 个神经元的均值与标准差，然后将归一化后的值作为该神经元的激活值。
    $$\hat{x}{k} \leftarrow \frac{x{k}-\mathrm{E}\left[x_{k}\right]}{\sqrt{\operatorname{Var}\left[x_{k}\right]}}$$
  - 但同时 BN 也降低了模型的拟合能力，破坏了之前学到的特征分布；
  - 为了恢复数据的原始分布，BN 引入了一个重构变换来还原最优的输入数据分布
    
    $$y_{k} \leftarrow \gamma \hat{X}_{k}+\beta$$
  1.4. BN方法小结
  
  BN的过程可以归纳为一个函数：
  
  $$\begin{aligned} \mathrm{BN}\left(\boldsymbol{x}{i}\right) &=\gamma \hat{\boldsymbol{x}}{i}+\beta \ &=\gamma \frac{\boldsymbol{x}{i}-\mathbf{E}\left[\boldsymbol{x}{i}\right]}{\sqrt{\boldsymbol{\operatorname { V a r }}\left[\boldsymbol{x}_{i}\right]+\epsilon}}+\beta \end{aligned}$$
  
  1.5. BN在训练和测试时分别怎么做
  - 训练时每次会传入一批数据，做法如前述；
  - 当测试或预测时，每次可能只会传入单个数据，此时模型会使用全局统计量代替批统计量；
    - 训练每个 batch 时，都会得到一组（均值，方差）；
    - 所谓全局统计量，就是对这些均值和方差求其对应的数学期望；
    - 具体计算公式为：
      
      $$\begin{array}{c}{\mathrm{E}[x] \leftarrow \mathrm{E}\left[\mu_{i}\right]} \ {\operatorname{Var}[x] \leftarrow \frac{m}{m-1} \mathrm{E}\left[\sigma_{i}^{2}\right]}\end{array}$$
      
      其中 $μ_i$ 和 $σ_i$ 分别表示第 i 轮 batch 保存的均值和标准差；m 为 batch_size，系数 m/(m-1) 用于计算无偏方差估计
      
      原文称该方法为移动平均（moving averages）
    - 此时的BN调整为
      
      $$\begin{aligned} \mathrm{BN}\left(\boldsymbol{x}{i}\right) &=\gamma \frac{\boldsymbol{x}{i}-\mathbf{E}\left[\boldsymbol{x}{i}\right]}{\sqrt{\operatorname{Var}\left[\boldsymbol{x}{i}\right]+\epsilon}}+\beta \ &=\frac{\gamma}{\sqrt{\operatorname{Var}\left[\boldsymbol{x}{i}\right]+\epsilon}} \boldsymbol{x}{i}+\left(\beta-\frac{\gamma \mathbf{E}\left[\boldsymbol{x}{i}\right]}{\sqrt{\operatorname{Var}\left[\boldsymbol{x}{i}\right]+\epsilon}}\right)\end{aligned}$$
  具体来说：BN就是
  - 在训练时用每一批数据的均值和标准差做平均得到$\hat{X}_k$，然后用$y_k \leftarrow \gamma \hat X_k+\beta$做变换得到最终需要的x，进行训练。
  - 而测试时用每批数据得到的均值方差求平均来做归一化
2. L1/L2 范数正则化
  
  2.1. L1/L2 范数的作用、异同
  相同点
  - 限制模型的学习能力——通过限制参数的规模，使模型偏好于权值较小的目标函数，防止过拟合。
  不同点
  - L1 正则化可以产生更稀疏的权值矩阵，可以用于特征选择，同时一定程度上防止过拟合；L2 正则化主要用于防止模型过拟合
  - L1 正则化适用于特征之间有关联的情况；L2 正则化适用于特征之间没有关联的情况。
  2.2. 为什么 L1 和 L2 正则化可以防止过拟合？
  - L1 & L2 正则化会使模型偏好于更小的权值。
  - 更小的权值意味着更低的模型复杂度；添加 L1 & L2 正则化相当于为模型添加了某种先验，限制了参数的分布，从而降低了模型的复杂度。
  - 模型的复杂度降低，意味着模型对于噪声与异常点的抗干扰性的能力增强，从而提高模型的泛化能力。——直观来说，就是对训练数据的拟合刚刚好，不会过分拟合训练数据（比如异常点，噪声）——奥卡姆剃刀原理
  2.3. 为什么 L1 正则化可以产生稀疏权值，而 L2 不会？
  L1正则化和L2正则化可以看做是损失函数的惩罚项。所谓『惩罚』是指对损失函数中的某些参数做一些限制。对于线性回归模型，使用L1正则化的模型建叫做Lasso回归，使用L2正则化的模型叫做Ridge回归（岭回归）。
  
  L1回归的公式如下：
  $$
  J=J_{0}+\alpha \sum_{w}|w|
  $$
  其中$J_0$是原始的损失函数，加号后面的一项是L1正则化项，α是正则化系数。
  
  注意到L1正则化是权值的绝对值之和，$J$是带有绝对值符号的函数，因此$J$是不完全可微的。机器学习的任务就是要通过一些方法（比如梯度下降）求出损失函数的最小值。当我们在原始损失函数$J_0$后添加L1正则化项时，相当于对$J_0$做了一个约束。令$L=\alpha \sum_w|w|$，则$J=J_0+L$，此时我们的任务变成在L1约束下求出$J_0$取最小值的解。考虑二维的情况，即只有两个权值$w^1$和$w^2$，此时$L=\left|w^1\right|+\left|w^2\right|$对于梯度下降法，求解$J_0$的过程可以画出等值线，同时L1正则化的函数L也可以在w1w2的二维平面上画出来。如下图：
  
  图中等值线是$J_0$的等值线，黑色方形是L函数的图形。在图中，当$J_0$等值线与$L$图形首次相交的地方就是最优解。上图中$J_0$与L在L的一个顶点处相交，这个顶点就是最优解。注意到这个顶点的值是$\left(w^1, w^2\right)=(0, w)$。可以直观想象，因为L函数有很多『突出的角』（二维情况下四个，多维情况下更多），$J_0$与这些角接触的机率会远大于与L其它部位接触的机率，而在这些角上，会有很多权值等于0，这就是为什么L1正则化可以产生稀疏模型，进而可以用于特征选择。
  
  而L2正则化的公式如下：
  
  $$J=J_{0}+\alpha \sum_{m} w^{2}$$
  
  平面图如下，因为此时L2的图形是一个圆，因此两者相交的点没有0的情况，这就是L2不产生稀疏矩阵的原因。

P.S. 为什么相切的点就是所求的点。我们要求$J_0$在L约束下的最小值，L是约束，那么我们就只能在下面的菱形和圆形里面取值，相切那个点。（彩色等值线是越靠近外面越大）

偏差与方差的权衡

给定一个机器学习任务：
- 训练不足时，模型拟合能力不足，此时偏差是主要影响模型泛化误差的原因。
- 随着训练进行，模型拟合能力增强，此时方差逐渐主导模型的泛化误差。
- 当训练充足后，模型拟合能力过强，此时发生过拟合
偏差和方差的关系和模型复杂度，欠拟合，过拟合的概念紧密关联。
- 当模型复杂度增大时，偏差随之减小，方差随之增大
- 泛化误差存在最小值，此时模型复杂度处于最优状态，增大模型复杂度会增大方差，减小模型复杂度会增大偏差。

生成模型与判别模型

监督学习的任务是学习一个模型，对给定的输入预测相应的输出
这个模型的一般形式为一个决策函数或一个条件概率分布（后验概率）：
$$
Y=f(X) \quad\text { or } \quad P(Y | X)
$$
- 决策函数：输入 X 返回 Y；其中 Y 与一个阈值比较，然后根据比较结果判定 X 的类别
- 条件概率分布：输入 X 返回 X 属于每个类别的概率；将其中概率最大的作为 X 所属的类别
监督学习模型可分为生成模型与判别模型
- 判别模型直接学习决策函数或者条件概率分布
  - 直观来说，判别模型学习的是类别之间的最优分隔面，反映的是不同类数据之间的差异
- 生成模型学习的是联合概率分布$P(X, Y)$，然后根据条件概率公式计算$P(Y|X)$
  $$
  P(Y | X)=\frac{P(X, Y)}{P(X)}
  $$

两者之间的联系

由生成模型可以得到判别模型，但由判别模型得不到生成模型。
当存在“隐变量”时，只能使用生成模型

隐变量：当我们找不到引起某一现象的原因时，就把这个在起作用，但无法确定的因素，叫“隐变量”

优缺点

判别模型
- 优点
  - 直接面对预测，往往学习的准确率更高
  - 由于直接学习 P(Y|X) 或 f(X)，可以对数据进行各种程度的抽象，定义特征并使用特征，以简化学习过程
- 缺点
  - 不能反映训练数据本身的特性
  - …
生成模型
- 优点
  - 可以还原出联合概率分布 P(X,Y)，判别方法不能
  - 学习收敛速度更快——即当样本容量增加时，学到的模型可以更快地收敛到真实模型
  - 当存在“隐变量”时，只能使用生成模型
- 缺点
  - 学习和计算过程比较复杂

常见模型

判别模型
- K 近邻、感知机（神经网络）、决策树、逻辑斯蒂回归、最大熵模型、SVM、提升方法、条件随机场
生成模型
- 朴素贝叶斯、隐马尔可夫模型、混合高斯模型、贝叶斯网络、马尔可夫随机场

先验概率与后验概率

先验概率，后验概率，似然概率，条件概率，贝叶斯，最大似然 - CSDN博客

条件概率（似然概率）

一个事件发生后另一个事件发生的概率。
一般的形式为 P(X|Y)，表示 y 发生的条件下 x 发生的概率。
有时为了区分一般意义上的条件概率，也称似然概率

先验概率

事件发生前的预判概率
可以是基于历史数据的统计，可以由背景常识得出，也可以是人的主观观点给出。
一般都是单独事件发生的概率，如 P(A)、P(B)。

后验概率

基于先验概率求得的反向条件概率，形式上与条件概率相同（若 P(X|Y) 为正向，则 P(Y|X) 为反向）

贝叶斯公式
$$
P(Y | X)=\frac{P(X | Y) * P(Y)}{P(X)}
$$

机器学习实践

超参数选择

Grid Search

网格搜索
在高维空间中对一定区域进行遍历

Random Search

在高维空间中随机选择若干超参数

余弦相似度（Cos距离）与欧氏距离的区别和联系

欧式距离和余弦相似度都能度量 2 个向量之间的相似度
放到向量空间中看，欧式距离衡量两点之间的直线距离，而余弦相似度计算的是两个向量之间的夹角
没有归一化时，欧式距离的范围是 [0, +∞]，而余弦相似度的范围是 [-1, 1]；余弦距离是计算相似程度，而欧氏距离计算的是相同程度（对应值的相同程度）
归一化的情况下，可以将空间想象成一个超球面（三维），欧氏距离就是球面上两点的直线距离，而向量余弦值等价于两点的球面距离，本质是一样。

监督学习和无监督学习

监督学习给定标签，无监督学习不给定标签
监督学习的任务是分类和回归，无监督学习的任务是聚类

熵，交叉熵和相对熵

信息熵代表的是随机变量或整个系统的不确定性，熵越大，随机变量或系统的不确定性就越大。
$$
-\sum_{i=1}^{n} P\left(X_{i}\right) \log P\left(X_{i}\right)
$$
交叉熵，其用来衡量在给定的真实分布下，使用非真实分布所指定的策略消除系统的不确定性所需要付出的努力的大小
$$
\sum_{k=1}^{N} p_{k} \log {2} \frac{1}{q{k}}
$$
其中$p_k$是真实分布，$q_k$为非真实分布

因此，交叉熵越低，这个消除系统不确定性的策略就越好，最低的交叉熵也就是使用了真实分布所计算出来的信息熵，因为此时$p_k=q_k$ ，交叉熵 = 信息熵。这也是为什么在机器学习中的分类算法中，我们总是最小化交叉熵，因为交叉熵越低，就证明由算法所产生的策略最接近最优策略，也间接证明我们算法所算出的非真实分布越接近真实分布。
相对熵，其用来衡量两个取值为正的函数或概率分布之间的差异，即：
相对熵 = 某个策略的交叉熵 - 信息熵

具体可以参考熵，交叉熵，相对熵

混淆矩阵、模型度量指标：准确率、精确率、召回率、F1 值等

混淆矩阵

True Positive(TP)：将正类预测为正类的数量.
True Negative(TN)：将负类预测为负类的数量.
False Positive(FP)：将负类预测为正类数 → 误报 (Type I error).
False Negative(FN)：将正类预测为负类数 → 漏报 (Type II error).

准确率：
$$
A C C=\frac{T P+T N}{T P+T N+F P+F N}
$$
精确率：
$$
P=\frac{T P}{T P+F P}
$$
召回率：
$$
R=\frac{T P}{T P+F N}
$$
准确率与精确率的区别：

在正负样本不平衡的情况下，准确率这个评价指标有很大的缺陷。比如在互联网广告里面，点击的数量是很少的，一般只有千分之几，如果用acc，即使全部预测成负类（不点击）acc 也有 99% 以上，没有意义。

F1值——精确率和召回率的调和均值：
$$
\begin{aligned} \frac{2}{F_{1}} &=\frac{1}{P}+\frac{1}{R} \ F_{1} &=\frac{2 T P}{2 T P+F P+F N} \end{aligned}
$$

只有当精确率和召回率都很高时，F1值才会高

如何处理数据中的缺失值

可以分为以下 2 种情况：

缺失值较多
- 直接舍弃该列特征，否则可能会带来较大的噪声，从而对结果造成不良影响。
缺失值较少
- 当缺失值较少（<10%）时，可以考虑对缺失值进行填充，以下是几种常用的填充策略：
1. 用一个异常值填充（比如 0），将缺失值作为一个特征处理
  
  data.fillna(0)
2. 用均值|条件均值填充
  
  如果数据是不平衡的，那么应该使用条件均值填充
  
  所谓条件均值，指的是与缺失值所属标签相同的所有数据的均值
  
  data.fillna(data.mean())
3. 用相邻数据填充
  1
  2
  3
  4
  # 用前一个数据填充
  data.fillna(method='pad')
  # 用后一个数据填充
  data.fillna(method='bfill')
4. 插值
  
  data.interpolate()
5. 拟合
  
  简单来说，就是将缺失值也作为一个预测问题来处理：将数据分为正常数据和缺失数据，对有值的数据采用随机森林等方法拟合，然后对有缺失值的数据进行预测，用预测的值来填充。

关联规则挖掘的 3 个度量指标：支持度、置信度、提升度

支持度（Support）

X → Y 的支持度表示项集 {X,Y} 在总项集中出现的概率
$$
\text { Support }(X \rightarrow Y)=\frac{P(X \cup Y)}{P(I)}=\frac{\operatorname{num}(X \cup Y)}{\operatorname{num}(I)}
$$

置信度（Confidence）

X → Y 的置信度表示在先决条件 X 发生的情况下，由规则 X → Y 推出 Y 的概率。

$$
\text { Con fidence }(X \rightarrow Y)=P(Y | X)=\frac{P(X \cup Y)}{P(X)}=\frac{\operatorname{num}(X \cup Y)}{\operatorname{num}(X)}
$$

提升度（Lift）

X → Y 的提升度表示含有X的条件下，同时含有Y的概率，与Y总体发生的概率之比。

$$
\begin{aligned} \operatorname{Lift}(X \rightarrow Y) &=\frac{P(Y | X)}{P(Y)}=\frac{\text { Con fidence }(X \rightarrow Y)}{\operatorname{num}(Y) / \operatorname{num}(I)} \ &=\frac{P(X \cup Y)}{P(X) P(Y)}=\frac{\operatorname{num}(X \cup Y) \operatorname{num}(I)}{\operatorname{num}(X) \operatorname{num}(Y)} \end{aligned}
$$

规则的有效性：

满足最小支持度和最小置信度的规则，叫做“强关联规则”

最小支持度和最小置信度是人工设置的阈值
Lift(X→Y) > 1 的 X→Y 是有效的强关联规则
Lift(X→Y) <=1 的 X→Y 是无效的强关联规则
特别地，Lift(X→Y) = 1 时，X 与 Y 相互独立。

判断规则的有效性

问题：已知有1000名顾客买年货，分为甲乙两组，每组各500人，其中甲组有500人买了茶叶，同时又有450人买了咖啡；乙组有450人买了咖啡，如表所示，请问“茶叶→咖啡”是一条有效的关联规则吗？

组次	买茶叶的人数	买咖啡的人数
甲组（500人）	500	450
乙组（500人）	0	450

答：

“茶叶→咖啡”的支持度：Support(X→Y) = 450 / 1000 = 45%
“茶叶→咖啡”的置信度：Confidence(X→Y) = 450 / 500 = 90%
“茶叶→咖啡”的提升度：Lift(X→Y) = 90% / 90% = 1

由于提升度 Lift(X→Y) = 1，表示 X 与 Y 相互独立。也就是说，是否购买咖啡，与是否购买茶叶无关联。规则“茶叶→咖啡”不成立，或者说几乎没有关联，虽然它的置信度高达90%，但它不是一条有效的关联规则。

机器学习算法

基本遵从《统计学习方法》一书中的符号表示。
除特别说明，默认w为行向量，x为列向量，以避免在wx中使用转置符号；但有些公式为了更清晰区分向量与标量，依然会使用^T的上标，注意区分。

输入实例x的特征向量记为：
$$
x=\left(x^{(1)}, x^{(2)}, \cdots, x^{(n)}\right)^{T}
$$

注意：x_i 和 x^(i) 含义不同，前者表示训练集中第 i 个实例，后者表示特征向量中的第 i 个分量；因此，通常记训练集为：
$$
T=\left{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right}
$$

特征向量用小n表示维数，训练集用大N表示个数

信息论

信息论的基本思想：一件不太可能的事发生，要比一件非常可能的事发生，提供更多的信息。
该想法可描述为以下性质：
1. 非常可能发生的事件信息量要比较少，并且极端情况下，一定能够发生的事件应该没有信息量。
2. 比较不可能发生的事件具有更大的信息量。
3. 独立事件应具有增量的信息。例如，投掷的硬币两次正面朝上传递的信息量，应该是投掷一次硬币正面朝上的信息量的两倍。

信息熵

信息熵可以参照第一章中的内容

逻辑回归

逻辑回归模型定义

二项逻辑回归模型即如下的条件概率分布
$$
\begin{array}{l}{P(Y=1 | x)=\frac{\exp (w x)}{1+\exp (w x)}=\frac{1}{1+\exp (-w x)}} \ {P(Y=0 | x)=1-P(Y=1 | x)}\end{array}
$$

逻辑回归的推导

逻辑回归推导的关键点 (3)

逻辑回归的定义
损失函数（极大似然）
参数优化（梯度下降）
逻辑斯蒂回归的定义：
$$
\begin{aligned} P(Y&=1 | x )=\frac{1}{1+\exp (-w x)}=\sigma(x) \ P(Y&=0 | x )=1-\sigma(x) \end{aligned}
$$
负对数函数作为损失函数：
$$
\begin{aligned} L(w) &=-\log \left(\prod_{i=1}^{N}\left[\sigma\left(x_{i}\right)\right]^{y_{i}}\left[1-\sigma\left(x_{i}\right)\right]^{1-y_{i}}\right) \ &=-\sum_{i=1}^{N}\left[y_{i} \log \sigma\left(x_{i}\right)+\left(1-y_{i}\right) \log \left(1-\sigma\left(x_{i}\right)\right)\right] \ &=-\sum_{i=1}^{N}\left[y_{i} \log \frac{\sigma\left(x_{i}\right)}{1-\sigma\left(x_{i}\right)}+\log \left(1-\sigma\left(x_{i}\right)\right)\right] \end{aligned}
$$

进一步代入 σ(x) 有：
$$
L(w)=-\sum_{i=1}^{N}\left[y_{i}\left(w x_{i}\right)-\log \left(1+\exp \left(w x_{i}\right)\right)\right]
$$

求梯度
$$
\begin{aligned} \frac{\partial L(w)}{\partial w} &=-\sum_{i=1}^{N}\left[y_{i} x_{i}-\frac{\exp \left(w x_{i}\right)}{1+\exp \left(w x_{i}\right)} x_{i}\right] \ &=\sum_{i=1}^{N}\left[\sigma\left(x_{i}\right)-y_{i}\right] x_{i} \end{aligned}
$$

多分类逻辑回归

设$Y \in{1,2, \ldots \mathrm{K}}$，则多项式逻辑回归模型为
$$
\begin{aligned} P(Y=k | x) &=\frac{\exp \left(w_{k} x\right)}{1+\sum_{k=1}^{K-1} \exp \left(w_{k} x\right)} \quad k=1,2, \ldots, K-1 \ P(Y=K | x) &=\frac{1}{1+\sum_{k=1}^{K-1} \exp \left(w_{k} x\right)} \end{aligned}
$$

最终推出来softmax回归
$$
h_{\theta}\left(x^{(i)}\right)=\left[ \begin{array}{c}{p\left(y^{(i)}=1 | x^{(i)} ; \theta\right)} \ {p\left(y^{(i)}=2 | x^{(i)} ; \theta\right)} \ {\vdots} \ {p\left(y^{(i)}=k | x^{(i)} ; \theta\right)}\end{array}\right]=\frac{1}{\sum_{j=1}^{k} e^{\theta_{j}^{T} x^{(i)}}} \left[ \begin{array}{c}{e^{\theta_{1}^{T} x^{(i)}}} \ {e^{\theta_{2}^{T} x^{(i)}}} \ {\vdots} \ {e^{\theta_{k}^{T} x^{(i)}}}\end{array}\right]
$$
定义了新的假设函数（hypothesis function）之后，我们要得到其对应的代价函数（cost function）。
$$
J(\theta)=-\frac{1}{m}\left[\sum_{i=1}^{m} \sum_{j=1}^{k} 1\left{y^{(i)}=j\right} \log \frac{e^{\theta_{j}^{T} x^{(i)}}}{\sum_{l=1}^{k} e^{\theta_{l}^{T} x^{(i)}}}\right]
$$
其中 $1\left\{ \cdot \right\}$ 的取值规则为大括号内的表达式值为真时，取 1，为假时取 0。

对该代价函数求最优解同样可以使用如梯度下降之类的迭代算法，其梯度公式如下：
$$
\nabla_{\theta_{j}} J(\theta)=(-\frac{1}{m}\left[\sum_{i=1}^{m} \sum_{j=1}^{k} 1\left{y^{(i)}=j\right} \log \frac{e^{\theta_{j}^{T} x^{(i)}}}{\sum_{l=1}^{k} e^{\theta_{l}^{T} x^{(i)}}}\right])’\
=(-\frac{1}{m}\left[\sum_{i=1}^{m} \sum_{j=1}^{k} 1\left{y^{(i)}=j\right} (\log e^{\theta_{j}^{T} x^{(i)}}-\log {\sum_{l=1}^{k} e^{\theta_{l}^{T} x^{(i)}}})\right])’\
=(-\frac{1}{m}\left[\sum_{i=1}^{m} \sum_{j=1}^{k} 1\left{y^{(i)}=j\right} (\theta_{j}^{T} x^{(i)}-\log {\sum_{l=1}^{k} e^{\theta_{l}^{T} x^{(i)}}})\right])’\
\
=-\frac{1}{m}\left[\sum_{i=1}^{m} \sum_{j=1}^{k} 1\left{y^{(i)}=j\right} (x^{(i)}-(\log {\sum_{l=1}^{k} e^{\theta_{l}^{T} x^{(i)}}})’)\right]
\
==-\frac{1}{m}\left[\sum_{i=1}^{m} \sum_{j=1}^{k} 1\left{y^{(i)}=j\right} (x^{(i)}-\frac{x^{(i)}*e^{\theta_{l}^{T} x^{(i)}}}{\log {\sum_{l=1}^{k} e^{\theta_{l}^{T} x^{(i)}}}})\right]
\
=-\frac{1}{m} \sum_{i=1}^{m}\left[x^{(i)}\left(1\left{y^{(i)}=j\right}-p\left(y^{(i)}=j | x^{(i)} ; \theta\right)\right)\right]
$$
有了偏导数，就可以对代价函数进行优化，最终求解。

支持向量机

支持向量机（Support Vector Machines, SVM）是一种二分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；支持向量机还包括核技巧，这使其成为实质上的非线性分类器。
SVM 的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题。
SVM 的最优化算法是求解凸二次规划的最优化算法。

什么是支持向量

训练数据集中与分离超平面距离最近的样本点的实例称为支持向量（离超平面最近的点就是支持向量，包括正类和负类各自离超平面最近的点）
更通俗的解释：
- 数据集种的某些点，位置比较特殊。比如 x+y-2=0 这条直线，假设出现在直线上方的样本记为 A 类，下方的记为 B 类。
- 在寻找找这条直线的时候，一般只需看两类数据，它们各自最靠近划分直线的那些点，而其他的点起不了决定作用。
- 这些点就是所谓的“支持点”，在数学中，这些点称为向量，所以更正式的名称为“支持向量”。

支持向量机的分类

线性可分支持向量机
- 当训练数据线性可分时，通过硬间隔最大化，学习一个线性分类器，即线性可分支持向量机，又称硬间隔支持向量机。
线性支持向量机
- 当训练数据接近线性可分时，通过软间隔最大化，学习一个线性分类器，即线性支持向量机，又称软间隔支持向量机。
非线性支持向量机
- 当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。

核函数与核技巧

核函数表示将输入从输入空间映射到特征空间后得到的特征向量之间的内积

支持向量机推导

svm由简至繁包括：线性可分支持向量机，线性支持向量机，非线性支持向量机

线性可分支持向量机的推导

当训练数据线性可分时，通过硬间隔最大化，学习一个线性分类器，即线性可分支持向量机，又称硬间隔支持向量机。

线性 SVM 的推导分为两部分
1. 如何根据间隔最大化的目标导出 SVM 的标准问题；
2. 拉格朗日乘子法对偶问题的求解过程.

符号定义：

训练集T

$$
T=\left{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right}
$$

分离超平面(w,b)：

$$
w^{} \cdot x+b^{}=0
$$

如果使用映射函数，那么分离超平面为：

$$
w^{} \cdot \Phi(x)+b^{}=0
$$

映射函数 Φ(x) 定义了从输入空间到特征空间的变换，特征空间通常是更高维的，甚至无穷维；方便起见，这里假设 Φ(x) 做的是恒等变换。

分类决策函数 f(x)

$$
f(x)=\operatorname{sign}\left(w^{} \cdot x+b^{}\right)
$$

SVM 标准问题的推导(2)

从“函数间隔”到“几何间隔”

给定训练集T和超平面(w,b)，定义函数间隔$\hat{\gamma}$：
$$
\begin{aligned} \hat{\gamma} &=\min {i=1, \cdots, N} y{i}\left(w x_{i}+b\right) \ &=\min {i=1, \cdots, N} \hat{\gamma}{i} \end{aligned}
$$
对 w 作规范化，使函数间隔成为几何间隔$\gamma$
$$
\begin{aligned} \gamma &=\min {i=1, \cdots, N} y{i}\left(\frac{w}{|w|} x_{i}+\frac{b}{|w|}\right) \ &=\min {i=1, \cdots, N} \frac{\gamma{i}}{|w|} \end{aligned}
$$

最大化几何间隔

$$
\begin{array}{ll}{\max {w, b}} & \hat{\gamma} \ {\text { s.t. }} & {y{i}\left(wx_{i}+b\right) \geq \hat\gamma, \quad i=1,2, \cdots, N}\end{array}
$$

由函数间隔与几何间隔的关系，等价于
$$
\begin{array}{ll}{\max {w, b}} & {\gamma} \ {\text { s.t. }} & {y{i}\left(\frac{w}{|w|} x_{i}+\frac{b}{|w|}\right) \geq \gamma, \quad i=1,2, \cdots, N}\end{array}
$$

西瓜书的SVM推导

上面的两步推理方式感觉不如西瓜书上面的直接，下面用西瓜书的公式来证明：

用r表示一个点到分类超平面的距离：
$$
r=\frac{\left|w^{T} x+b\right|}{|w|}
$$
假设超平面(w,b)能够正确分类，也就是对于$y_i=1$，有$w^T x_i+b>0$；对于$y_i=-1$，有$w^{T} x_{i}+b<0$，则：
$$
\left{\begin{array}{ll}{w^{\mathrm{T}} x_{i}+b \geqslant+1,} & {y_{i}=+1} \ {w^{T} x_{i}+b \leqslant-1,} & {y_{i}=-1}\end{array}\right.
$$
对于距离超平面最近（支持向量）的点，r的距离为1，那么两个异类支持向量到超平面距离和为

$$\gamma = \frac{2}{|w|}$$

这被称为“间隔”

我们要最大化间隔，也就是要找到$w, b$，使得$\gamma$最大，即：
$$
\begin{array}{l}{\max {w, b} \frac{2}{|w|}} \ {\text {s.t.} y{i}\left(w^{T} x_{i}+b\right) \geqslant 1, \quad i=1,2, \ldots, m}\end{array}
$$
为了最大化间隔，仅需要最大化$\frac{1}{|w|}$，等价于最小化$|w|^2$，上面的问题转化为：
$$
\begin{array}{l}{\min {\boldsymbol{w}, b} \frac{1}{2}|\boldsymbol{w}|^{2}} \ {\text { s.t. } y{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1, \quad i=1,2, \ldots, m}\end{array}
$$
这是一个规划问题，在运筹学里面，这样的问题可以通过拉格朗日方程，求他的对偶问题来求解。

令$\alpha_i \ge 0$，上面问题的拉格朗日函数如下：
$$
L(\boldsymbol{w}, b, \boldsymbol{\alpha})=\frac{1}{2}|\boldsymbol{w}|^{2}+\sum_{i=1}^{m} \alpha_{i}\left(1-y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}{i}+b\right)\right)
$$
令拉格朗日函数对$w,b$求导为0可得:
$$
\begin{aligned} \boldsymbol{w} &=\sum{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{x}{i} \ 0 &=\sum{i=1}^{m} \alpha_{i} y_{i} \end{aligned}
$$
将解得的$w$带入拉格朗日方程可得对偶问题:
$$
\max {\alpha} \quad \sum{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} x_{i}^{T} x_{j} \
\text { s.t. } \quad {\sum_{i=1}^{m} a_{i} y_{i}=0} \ {\alpha_{i} \geqslant 0, \quad i=1,2, \ldots, m}
$$
解出$\alpha$之后，带入原分类超平面方程可得:
$$
\begin{aligned} f(x) &=w^{T} x+b \ &=\sum_{i=1}^{m} \alpha_{i} y_{i} x_{i}^{T} x+b \end{aligned}
$$
对偶问题是一个二次规划问题，求解对偶问题的方法是SMO（sequential minimal optimization）

核函数

对于在原始空间中不可分的问题，可以将原始空间映射到一个更高维度的特征空间，是的样本在这个特征空间中线性可分。用$\phi(x)$表示将x映射之后的特征向量，那么特征空间中的超平面可以表示为:
$$
f(x)=w^{T} \phi(x)+b
$$
类似的，对于$w,b$，有：
$$
\begin{array}{l}{\min {w, b} \frac{1}{2}|w|^{2}} \ {\text { s.t. } y{i}\left(w^{T} \phi\left(x_{i}\right)+b\right) \geqslant 1, \quad i=1,2, \ldots, m}\end{array}
$$
其对偶问题为：
$$
\max {\alpha} \quad \sum{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \phi (x_{i})^{T} \phi (x_{j}) \\text { s.t. } \quad {\sum_{i=1}^{m} a_{i} y_{i}=0} \ {\alpha_{i} \geqslant 0, \quad i=1,2, \ldots, m}
$$
求解上面的问题涉及到计算$\phi (x_{i})^{T} \phi (x_{j}) $，这是样本$x_i$和$x_j$映射到特征空间之后的内积，由于特征空间维数很高，甚至可能是无穷维，因此直接计算$\phi (x_{i})^{T} \phi (x_{j})$通常比较难，为了避开这个问题，设计了核函数：
$$
\kappa\left(\boldsymbol{x}{i}, \boldsymbol{x}{j}\right)=\left\langle\phi\left(\boldsymbol{x}{i}\right), \phi\left(\boldsymbol{x}{j}\right)\right\rangle=\phi\left(\boldsymbol{x}{i}\right)^{\mathrm{T}} \phi\left(\boldsymbol{x}{j}\right)
$$
在高维中的内积可以通过低维度中的核函数来求取。

于是上面的对偶问题可以写为：
$$
\begin{array}{ll}{\max {\alpha}} & {\sum{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m}}\alpha_{i} \alpha_{j} y_{i} y_{j} \kappa\left(x_{i}, x_{j}\right) \ {\text { s.t. }} & {\sum_{i=1}^{m} \alpha_{i} y_{i}=0}\end{array}\
\alpha_{i} \geqslant 0, \quad i=1,2, \ldots, m
$$
求解得到：
$$
\begin{aligned} f(\boldsymbol{x}) &=\boldsymbol{w}^{\mathrm{T}} \phi(\boldsymbol{x})+b \ &=\sum_{i=1}^{m} \alpha_{i} y_{i} \phi\left(\boldsymbol{x}{i}\right)^{\mathrm{T}} \phi(\boldsymbol{x})+b \ &=\sum{i=1}^{m} \alpha_{i} y_{i} \kappa\left(\boldsymbol{x}, \boldsymbol{x}_{i}\right)+b \end{aligned}
$$
常用核函数
软间隔

上面求解最大最小值的时候，约束条件是必须全部满足。但是一个超平面不一定在特征空间中是线性可分的。即使存在一个超平面能分开，要找到合适的核函数也很难，因此有了软间隔。

软间隔的意思就是某些点可以不满足约束。用替代损失来表示因为某些点不满足造成的损失。

决策树

分类树 - ID3 决策树与 C4.5 决策树 TODO

ID3 决策树和 C4.5 决策树的区别在于：前者使用信息增益来进行特征选择，而后者使用信息增益比。

回归树 - CART 决策树

CART 算法是在给定输入随机变量 X 条件下输出随机变量 Y 的条件概率分布的学习方法。

CART 算法假设决策树是二叉树，内部节点特征的取值为“是”和“否”。

这样的决策树等价于递归地二分每个特征，将输入空间/特征空间划分为有限个单元，然后在这些单元上确定在输入给定的条件下输出的条件概率分布。
CART 决策树既可以用于分类，也可以用于回归；

对回归树 CART 算法用平方误差最小化准则来选择特征，对分类树用基尼指数最小化准则选择特征

CART 回归树算法推导

一个回归树对应着输入空间/特征空间的一个划分以及在划分单元上的输出值；
假设已将输入空间划分为 M 个单元：{R_1,..,R_m,..,R_M}，并在每个单元上对应有输出值 c_m，则该回归树可表示为:
$$
f(x)=\sum_{m=1}^{M} c_{m} I\left(x \in R_{m}\right)
$$

I(x) 为指示函数

如果已经划分好了输入空间，通常使用平方误差作为损失函数来表示回归树对于训练数据的预测误差，通过最小化损失函数来求解每个划分单元的最优输出值。

如何划分输入空间

一个启发式方法是：以特征向量中的某一个特征为标准进行切分。

假设选择特征向量中第 j 个变量作为切分变量，然后选择某个实例中第 j 个值 s 作为切分点，则定义如下两个划分单元
$$
R_{1}(j, s)={x | x^{(j)} \leq s}, \quad R_{2}(j, s)={x | x^{(j)}>s}
$$
遍历每个实例的第j个值s，选择满足以下条件的作为最优切分变量j和切分点s

$$
\min {j, s}\left[\min {c{1}} \sum{x_{i} \in R_{1}(j, s)}\left(y_{i}-c_{1}\right)^{2}+\min {c{2}} \sum_{x_{i} \in R_{2}(j, s)}\left(y_{i}-c_{2}\right)^{2}\right]
$$

其中输出值 c1 和 c2 分别为
$$
\hat{c}{1}=\operatorname{avg}\left(y{i} | x_{i} \in R_{1}(j, s)\right), \quad \hat{c}{2}=\operatorname{avg}\left(y{i} | x_{i} \in R_{2}(j, s)\right)
$$
接着，继续对两个子空间重复以上步骤，直到满足条件为止；得到将输入空间划分为M个区域的决策树
$$
f(x)=\sum_{m=1}^{M} \hat{c}{m} I\left(x \in R{m}\right)
$$

示例: 选择切分变量与切分点

《统计学习方法》 8.4.2

训练集

x_i	1	2	3	4	5	6	7	8	9	10
y_i	5.56	5.70	5.91	6.40	6.80	7.05	8.90	8.70	9.00	9.05

这里只有一个特征，即j=1；然后遍历每个实例的值作为切分点

s = {1, 2, 3, 4, 5, 6, 7, 8, 9}

原书使用的切分点为 {1.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, 8.5, 9.5}，即相邻两个点的均值；因为切分点并没有参与运算，所以我觉得两者没有区别；

最后一个点无法将数据划分为两个空间，所以不需要
以 s=1 为例

$$
\begin{array}{l}{R_{1}(1,1)={x | x \leq 1}={1}} \ {R_{2}(1,1)={x | x>1}={2,3,4,5,6,7,8,9,10}} \ {c_{1}=\frac{1}{\left|R_{1}\right|}=\frac{1}{1} \sum_{x_{i} \in R_{1}} y_{i}=5.56} \ {c_{2}=\frac{1}{\left|R_{2}\right|}=\frac{1}{9} \sum_{x_{i} \in R_{2}} y_{i}=7.50} \ {m(s)=\min {c{1}} \sum_{x_{i} \in R_{1}}\left(y_{i}-c_{1}\right)^{2}+\min {c{2}} \sum_{x_{i} \in R_{2}}\left(y_{i}-c_{2}\right)^{2}=0+15.72=15.72}\end{array}
$$

所有 m(s) 的计算结果如下

s	1	2	3	4	5	6	7	8	9
m(s)	15.72	12.07	8.36	5.78	3.91	1.93	8.01	11.73	15.74

当 s=6 时 m(s) 达到最小值，此时
$$
\begin{array}{l}{R_{1}(1,6)={x | x \leq 6}={1,2,3,4,5,6}} \ {R_{2}(1,6)={x | x>6}={7,8,9,10}} \ {c_{1}=\frac{1}{\left|R_{1}\right|}=\frac{1}{6} \sum_{x_{i} \in R_{1}} y_{i}=6.24} \ {c_{2}=\frac{1}{\left|R_{2}\right|}=\frac{1}{4} \sum_{x_{i} \in R_{2}} y_{i}=8.91}\end{array}
$$
所以第一棵决策树为
$$
\begin{array}{l}T_{1}(x)=\left{\begin{array}{ll}{6.24,} & {x<6} \ {8.91,} & {x \geq 6}\end{array}\right.\
f_1(x)=T_1(x)\end{array}
$$

集成学习

基本思想：由多个学习器组合成一个性能更好的学习器
集成学习为什么有效？——不同的模型通常会在测试集上产生不同的误差。平均上，集成模型能至少与其任一成员表现一致；并且如果成员的误差是独立的，集成模型将显著地比其成员表现更好。

1. Boosting

Boosting（提升）方法从某个基学习器出发，反复学习，得到一系列基学习器，然后组合它们构成一个强学习器。
Boosting 基于串行策略：基学习器之间存在依赖关系，新的学习器需要依据旧的学习器生成。
代表算法/模型:
- 提升方法 AdaBoost
- 提升树
- 梯度提升树 GBDT

Boosting 策略要解决的两个基本问题

每一轮如何改变数据的权值或概率分布？
如何将弱分类器组合成一个强分类器？

基于串行策略：基学习器之间存在依赖关系，新的学习器需要根据上一个学习器生成。
基本思路：
- 先从初始训练集训练一个基学习器；初始训练集中各样本的权重是相同的；
- 根据上一个基学习器的表现，调整样本权重，使分类错误的样本得到更多的关注；
- 基于调整后的样本分布，训练下一个基学习器；
- 测试时，对各基学习器加权得到最终结果

AdaBoost 算法

AdaBoost 是 Boosting 策略的一种具体算法

AdaBoost 算法解决 Boosting 两个基本问题的方法

每一轮如何改变数据的权值或概率分布？——开始时，每个样本的权值是一样的，AdaBoost 的做法是提高上一轮弱分类器错误分类样本的权值，同时降低那些被正确分类样本的权值。
如何将弱分类器组合成一个强分类器？—— AdaBoost 采取加权表决的方法（加法模型）。具体的，AdaBoost 会加大分类误差率小的基学习器的权值，使其在表决中起到更大的作用，同时减小分类误差率大的基学习器的权值。

AdaBoost 算法描述

输入：训练集 T={(x1,y1),..,(xN,yN)}, xi ∈ R^n, yi ∈ {-1,+1}，基学习器 G1(x)
输出：最终学习器 G(x)

初始化训练数据的权值分布

$$
D_{1}=\left(w_{1,1}, \cdots, w_{1, i}, \cdots, w_{1, N}\right), \quad w_{1, i}=\frac{1}{N}, \quad i=1,2, \cdots, N
$$

对 m=1,2,..,M

i. 使用权值分布为D_m的训练集，得到基分类器：
$$
G_{m}(x) : \chi \rightarrow{-1,+1}
$$
ii. 计算 G_m(x) 在训练集上的分类误差率
$$
\begin{aligned} e_{m} &=P\left(G_{m}\left(x_{i}\right) \neq y_{i}\right) \ &=\sum_{i=1}^{N} w_{m, i} \cdot I\left(G_{m}\left(x_{i}\right) \neq y_{i}\right) \end{aligned}
$$

I(x) 为指示函数：若G(x)!=y为真，则I(G(x)!=y)=1，反之为 0

实际上分类误差率就等于所有分类错误的数据的权值之和

iii. 计算 G_m(x) 的系数
$$
\alpha_{m}=\frac{1}{2} \ln \frac{1-e_{m}}{e_{m}}
$$
iv. 更新训练街的权值分布
$$
\begin{aligned} D_{m+1} &=\left(w_{m+1,1}, \cdots, w_{m+1, i}, \cdots, w_{m+1, N}\right) \ w_{m+1, i} &=\frac{w_{m, i} \cdot \exp \left(-\alpha_{m} \cdot y_{i} G_{m}\left(x_{i}\right)\right)}{Z_{m}} \ Z_{m} &=\sum_{i=1}^{N} w_{m, i} \cdot \exp \left(-\alpha_{m} \cdot y_{i} G_{m}\left(x_{i}\right)\right) \end{aligned}
$$
其中 Z_m 为规范化因子，使 D_m+1 成为一个概率分布，类似 Softmax 函数

因为 y, G(x) ∈ {-1, 1}，所以实际上
$$
y_{i} G_{m}\left(x_{i}\right)=\left{\begin{array}{cl}{1,} & {G_{m}\left(x_{i}\right)=y_{i}} \ {-1,} & {G_{m}\left(x_{i}\right) \neq y_{i}}\end{array}\right.
$$
因此 $w_{m+1,i}$ 也可以写作
$$
w_{m+1, i}=\left{\begin{array}{ll}{\frac{w_{m, i}}{Z_{m}} e^{-\alpha_{m}},} & {G_{m}\left(x_{i}\right)=y_{i}} \ {\frac{w_{m, i}}{Z_{m}} e^{\alpha_{m}},} & {G_{m}\left(x_{i}\right) \neq y_{i}}\end{array}\right.
$$

模型的更新算法：
$$
f_{k}(x)=f_{k-1}(x)+\alpha_{k} G_{k}(x)
$$
构建基学习器的线性组合

$$
G(x)=\operatorname{sign}\left(\sum_{m=1}^{M} \alpha_{m} G_{m}(x)\right)
$$

AdaBoost 算法要点说明

开始时，训练集中所有数据具有均匀的权值分布
计算分类误差率，实际上就是计算所有分类错误的数据的权值之和
G_m(x) 的系数 α_m 表示该学习器在最终学习器中的重要性；公式$\alpha_{m}=\frac{1}{2} \ln \frac{1-e_{m}}{e_{m}}$表明当分类错误率 $e_m \le 1/2$时，$α_m \ge 0$，并且 $α_m$ 随 $e_m$ 的减小而增大
被基分类器分类错误的样本权值会扩大，而分类正确的权值会缩小——不改变训练数据，而不断改变训练数据权值的分布，使训练数据在基学习器的学习中起到不同的作用，这是 AdaBoost 的一个特点。

梯度提升决策树 GBDT(Gradient Boosting Decision Tree)

GBDT 是以决策树为基学习器、采用 Boosting 策略的一种集成学习模型
与提升树的区别：残差的计算不同，提升树使用的是真正的残差，梯度提升树用当前模型的负梯度来拟合残差。

提升树

以决策树为基学习器，对分类问题使用二叉分类树，回归问题使用二叉回归树。
解决回归问题时，通过不断拟合残差得到新的树。

提升树模型可表示为决策树的加法模型：
$$
f_{M}(x)=\sum_{m=1}^{M} T\left(x ; \Theta_{m}\right)
$$

首先初始化提升树 f_0(x)=0，则第 m 步的模型为

$$
f_{m}(x)=f_{m-1}(x)+T\left(x ; \Theta_{m}\right)
$$

然后通过最小化损失函数决定下一个决策树的参数
$$
\hat{\Theta}{m}=\arg \min {\Theta{m}} \sum{i=1}^{N} L\left(y_{i}, f_{m-1}\left(x_{i}\right)+T\left(x_{i} ; \Theta_{m}\right)\right)
$$

对于二分类问题，提升树算法只需要将AdaBoost 算法中的基学习器限制为二叉分类树即可

提升树算法描述

在回归问题中，新的树是通过不断拟合残差（residual）得到的。

输入：训练集 T={(x1,y1),..,(xN,yN)}, xi ∈ R^n, yi ∈ R
输出：回归提升树 f_M(x)

初始化 f_0(x)=0
对 m=1,2,..,M

i.计算残差
$$
r_{m, i}=y_{i}-f_{m-1}\left(x_{i}\right), \quad i=1,2, \dots, N
$$
ii.拟合残差学习下一个回归树的参数
$$
\hat{\Theta}{m}=\arg \min {\Theta{m}} \sum{i=1}^{N} L\left(r_{m, i}, T\left(x_{i} ; \Theta_{m}\right)\right)
$$
iii. 更新 f_m(x)