春（秋）招复习——机器学习篇

[TOC]

逻辑回归

参考1

1. 介绍下逻辑回归？

   逻辑回归假设数据服从伯努利分布，通过极大化似然函数的方法，运用梯度下降来求解参数，达到将数据二分类的目的。

   这里略微解释提到的几个概念。

   • 伯努利实验：单次随机试验，只有 “成功” 或 ”失败“ 这两种结果，例如抛硬币、买彩票（中奖or没中奖）

   • 伯努利分布：伯努利实验的概率分布称为伯努利分布，也称为两点分布或者0-1分布

     其概率质量函数为：
     $$
     P(x) = p^x (1 - p)^{1 - x} = \left{
     \begin{aligned}
     p \quad if \ x = 1 \
     q \quad if \ x = 0 \
     \end{aligned}
     \right.
     $$
     公式很好理解，即成功的概率为 $p$, 失败的概率为 $q$

     其期望值为：
     $$
     E(x) = \sum_{x = 0}^1 xP(x) = 0 \times q + 1 \times p = p
     $$
     其方差为：
     $$
     Var(x) = E[(x - E(x))^2] = \sum_{x = 0}^1 (x - p)^2P(x) = pq
     $$

   • 极大化似然函数：找到一组参数，使得在这组参数下，我们的数据似然度（概率）最大

2. 逻辑回归和线性回归的区别和联系

   • 线性回归： $y = w^Tx + b$
   • 线性回归的取值是连续的，条件概率 $p(Y = 1 | x)$ 的取值也是连续的，因此可以考虑用线性回归拟合条件概率，然而 $w^T x + b$ 的取值为 R，条件概率的取值为 [0, 1]，因此通过 sigmoid 函数将线性回归的输出从区间 R 转换到区间 [0, 1]

3. sigmoid 函数

   • 表达式：$\sigma(x) = \frac{1}{1 + e^{-x}}$

   • sigmoid 函数又被称为对数几率函数，假设 $y = \sigma(x)$ 表示正例的概率，$1- y$ 表示负例的概率，有
     $$
     ln\frac{y}{1 - y} = x
     $$

4. 逻辑回归模型
   $$
   y = \frac{1}{1 + e^{-(w^Tx+b)}}
   $$
   可以看到，$w^T x + b$ 拟合的是 $ln(y/1- y)$，再经过sigmoid 函数得到正例的概率

5. 最大化似然函数 / 最小化损失函数

   似然函数为：
   $$
   L(w) = \prod [p(x_i)]^{y_i}[1 - p(x_i)]^{1 - y_i}
   $$

   • $x_i$: 输入数据

   • $p(x_i)$: 预测为正例的概率

   • $y_i$: 正确类别 （1 表示正例，0表示负例）

   • 当 $y_i = 1$ 时，$[p(x_i)]^{y_i}[1 - p(x_i)]^{1 - y_i} = p(x_i)$，此时 $p(x_i)$越大，$L(w)$ 越大，因为正确标记为正例，我们期望 $p(x_i)$越大越好，因此期望$L(w)$ 越大越好

     当 $y_i = 0$时，$[p(x_i)]^{y_i}[1 - p(x_i)]^{1 - y_i} = 1 - p(x_i)$，此时 $p(x_i)$越小，$L(w)$ 越大，因为正确标记为负例，我们期望 $p(x_i)$越小越好，因此期望$L(w)$ 越大越好

   综上，我们期望 $L(w)$ 可以达到最大值。

   为方便求解，将似然函数转换为对数似然函数：
   $$
   \begin{aligned}
   ln L(w) &= \sum[y_ilnp(x_i) + (1 - y_i)ln(1 - p(x_i))] \
   &= \sum[y_i(w · x_i) - ln(1 + e^{w·x_i})]
   \end{aligned}
   $$
   因为损失函数越小，表示模型拟合效果越好，因此损失函数在对数似然函数的基础上取负号：
   $$
   J(w) = -\frac{1}{N} lnL(w)
   $$

6. 梯度下降

   • 三种常用梯度下降

     • 批梯度下降：会获得全局最优解，缺点是在更新每个参数的时候需要遍历所有的数据，计算量会很大，并且会有很多的冗余计算，导致的结果是当数据量大的时候，每个参数的更新都会很慢 （耗时）
     • 随机梯度下降：以高方差频繁更新，优点是使得sgd会跳到新的和潜在更好的局部最优解，缺点是使得收敛到局部最优解的过程更加的复杂 （稳定性下降）
     • 小批量梯度下降：结合了sgd和batch gd的优点，每次更新的时候使用n个样本。减少了参数更新的次数，可以达到更加稳定收敛结果，一般在深度学习当中我们采用这种方法

   • 如果采用随机梯度下降最小化损失函数

     更新后的权重 = 原来的权重 - 学习率 * 一阶导数
     $$
     g_i = \frac{\partial J(w)}{\partial w_i} = (p(x_i) - y_i)x_i \
     w^{k + 1}_i = w^k_i - \alpha · g_i
     $$

7. 逻辑回归为什么使用极大似然函数作为损失函数

   • 线性回归采用平方损失函数
   • 平方损失函数加上sigmoid的函数将会是一个非凸的函数，不易求解，会得到局部解，用对数似然函数得到高阶连续可导凸函数，可以得到最优解

8. 逻辑回归在训练过程中，如果有很多特征高度相关或者有一个特征重复了100遍，会造成这样的影响

   • 结论：在损失函数最终收敛的情况下，其实就算有很多特征高度相关也不会影响分类器的效果
   • 解释：可以认为这100个特征和原来那一个特征扮演的效果一样，因为这100个权重的权重值会发生变化

9. 逻辑回归如何做分类？

   把每一个标签看作二分类任务，划定一个阈值，y值大于这个阈值的是一类，y值小于这个阈值的是另外一类。阈值具体如何调整根据实际情况选择。

10. 逻辑回归的优缺点

    • 优点：
      1. 可解释性强，因为模型的参数简单，可以直接从权重矩阵 $w$ 看出不同特征对最后结果的影响程度
      2. 训练速度快，还是因为模型简单
    • 缺点：
      1. 准确率并不是很高。因为形式非常的简单(非常类似线性模型)，很难去拟合数据的真实分布
      2. 很难处理数据不平衡的问题。举个例子：如果我们对于一个正负样本非常不平衡的问题比如正负样本比 10000:1.我们把所有样本都预测为正也能使损失函数的值比较小。但是作为一个分类器，它对正负样本的区分能力不会很好。
      3. 处理非线性数据较麻烦。逻辑回归在不引入其他方法的情况下，只能处理线性可分的数据，或者进一步说，处理二分类的问题 。
      4. 逻辑回归本身无法筛选特征。有时候，我们会用GBDT来筛选特征，然后再上逻辑回归。

11. 手写逻辑回归

import numpy as np
import random
import math


def sigmoid(x):
    return 1/(1+math.exp(-x))

def epochs(data, label):
    # 初始化参数
    weights = [random.random() for x in range(len(data[0]))]
    bias = random.random()
    epoch_num = 10
    learn_rate = 0.01
    for i in range(epoch_num):
        for j in range(len(data)):
            # 前向
            out_before_active = np.sum(np.dot(weights, data[j])) + bias
            out_after_active = sigmoid(out_before_active)
            # 后向
            loss = -label[j]*math.log(out_after_active) - (1-label[j])*math.log(1-out_after_active)
            error = out_after_active - label[j]
            delta = learn_rate * error * data[j]
            weights = weights - delta
            bias = bias - learn_rate * error
    return weights, bias

if __name__ == '__main__':
    data = [[1,3,4,5,7],
            [1,6,3,6,6]]
    label = [0,1]

    weights, bias = epochs(data, label)

决策树

1. 介绍下决策树？

   决策树是基于树结构来进行决策的。决策树由节点（node）和有向边（directed edge）组成。节点有两种类型：内部节点（internal node）和叶节点（leaf node）。内部节点表示一个特征或属性，叶节点表示一个类。

   

   • 根节点包含样本全集
   • 每个非叶节点表示一个特征属性测试，每个节点包含的样本集合通过属性测试被划分到子节点中
   • 每个分支代表这个特征属相在某个值域上的输出
   • 每个叶子节点存放一个类别

2. 决策树的构造

   决策树的构造是一个递归的过程。

   • 构造根节点，将所有训练数据都放在根节点
   • 选择一个最优特征，按照该特征将训练数据分割成子集
   • 如果这些子集已经能够正确分类，那么构建叶节点，并将这些子集分到所对应的叶节点中去
   • 如果这些子集不能被基本正确分类，那么对这些子集选择新的最优特征，继续对其进行分割

   决策树学习的常用算法：

   • ID3算法
   • C4.5算法
   • CART算法

3. 决策树特征选择的准则？

   • 信息增益
   • 信息增益比
   • 基尼指数

在介绍上述两个 evaluation 前，先介绍下熵（entropy）。熵表示随机变量不确定性的度量，设 $X$ 是一个取有限个值的离散随机变量，其概率分布为：
$$
P(X = x_i) = p_i, \qquad i = 1,2,\cdots,n
$$
则随机变量 $X$ 的熵定义为：
$$
H(X) = -\sum^n_{i = 1} p_ilogp_i
$$

熵越大，随机变量的不确定性就越大

设有随机变量 $(X, Y)$，其联合概率分布为：
$$
P(X = x_i, Y = y_i) = p_{ij}, \qquad i = 1, 2, \cdots, n; j = 1, 2, \cdots, m
$$
条件熵：随机变量 $X$ 下随机变量 $Y$ 的不确定性：
$$
H(Y|X) = \sum^{n}_{i = 1}p_iH(Y|X = x_i), \qquad p_i = P(X = x_i)
$$
接下来引入信息增益的定义。

• 直观定义

  得知特征 $X$ 的信息而使类 $Y$ 的信息不确定性减少的程度

• 数学定义

  特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D, A)$，定义为集合 $D$ 的经验熵 $H(D)$ 与特征 $A$ 给定条件下 $D$ 的经验条件熵 $H(D|A)$ 之差，即
  $$
  g(D, A) = H(D) - H(D|A)
  $$

• 根据信息增益准则的特征选择方法
  对训练数据集（或子集）$D$，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征

• 信息增益算法

  1. 计算数据集 $D$ 的经验熵 $H(D)$，$|C_k|$ 表示 $k$ 类别的数据量
     $$
     H(D) = -\sum^{K}_{k = 1}\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}
     $$

  2. 计算特征 $A$ 对数据集 $D$ 的经验条件熵 $H(D|A)$，$|D_i|$ 表示数据集中特征 $A$ 取值为 $i$ 的数量
     $$
     H(D|A) = \sum^{n}{i = 1} \frac{|D_i|}{|D|}H(D_i) = -\sum^{n}{i = 1}\frac{|D_i|}{|D|} \sum^K_{k = 1}\frac{|D_{ik|}}{|D_i|}log_2\frac{|D_{ik}|}{|D_i|}
     $$

  3. 计算信息增益
     $$
     g(D, A) = H(D) - H(D|A)
     $$

  4. 计算每个特征的信息增益，选择信息增益最大的特征

• 缺点：

  信息增益会偏向于选择值较多的特征。例如：如果对于某一个特征，有 $D$ 个取值，样本集D将会被划分为|D|个分支，每个分支只有一个样本，这样划分后的信息熵为零，十分纯净，但是对分类毫无用处

接下来引入信息增益比的定义。

• 直观定义

  在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小，计算得到的信息增益比越小；特征个数较少时，惩罚参数较大。

• 数学定义

  特征 $A$ 对训练数据集 $D$ 的信息增益之比 $g_R(D, A)$ 定义为其信息增益 $g(D, A)$ 与训练数据集 $D$ 关于特征 $A$ 的值的熵 $H_A(D)$ 之比
  $$
  g_R(D, A) = \frac{g(D, A)}{H_A(D)}
  $$
  其中，$H_A(D) = -\sum^{n}_{i = 1}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}$，其实就是根据特征 $A$ 计算数据集 $D$ 的熵值

• 缺点：信息增益比偏向取值较少的特征

接下来引入基尼指数的定义。

• 直观定义

  基尼指数反映的是从样本集 $D$ 中随机抽取两个样本，其类别标记不一致的概率，因此 $Gini(D)$ 越小越好

• 数学定义
  $$
  GiDi(D) = \sum^{|y|}{k = 1}\sum{k’ \neq k}p_kp_k’ = \sum^{|y|}{k = 1}p_k(1 - p_k) = 1 - \sum^{|y|}{k = 1}p_k^2
  $$

• 计算数据集 $D$ 的基尼指数
  $$
  Gini(D) = 1 - \sum^K_{k = 1}(\frac{|C_k|}{|D|})^2
  $$
  其中，$C_k$ 是 $D$ 中属于第 $k$ 类的样本数量，$K$ 是样本个数。

• 计算数据集 $D$ 在特征 $A$ 的条件下的基尼指数，根据特征 $A$ 是否取某一可能值 $a$ 将数据集分割为 $D_1$ 和 $D_2$ 两部分
  $$
  Gini(D, A) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)
  $$

4. ID3算法

   计算各特征对 $D$ 的信息增益，选择信息增益最大的特征 $A$。

   节点停止分裂的几种条件：

   • 如果该节点所有实例均属于同一个类
   • 特征集为空
   • 信息增益小于阈值

   否则，对特征 $A$ 的每一个可能值 $a_i$，依 $A = a_i$ 将 $D$ 分割为若干非空子集 $D_i$，再对每一个子节点重复上述步骤

5. C4.5算法

   计算各特征对 $D$ 的信息增益比，选择信息增益比最大的特征 $A$。

   其他步骤与ID3算法相同

6. ID3算法和C4.5算法的缺点

   • 只适用于特征值为离散性的数据
   • 每次选取当前最佳的特征来分割数据。一旦按某特征切分后，该特征在之后的算法执行过程中将不会再其作用

7. CART算法

   1. 设节点的训练数据集为 $D$，对每一个特征 $A$，对其可能取的每个值 $a$，根据样本点对 $A = a$ 的测试为 “是”或“否”将 $D$ 分割成 $D_1$ 和 $D_2$两部分，并计算 $Gini(D, A)$
   2. 在所有可能的特征 $A$ 以及其所有可能的切分点 $a$ 中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依次从现节点生成两个子节点，将训练数据集依特征分配到两个子节点中去。
   3. 对两个子节点递归地调用 1 和 2，直至满足停止条件

   停止条件：

   • 节点中的样本个数小于预定阈值
   • 样本集的基尼指数小于预定阈值

8. 决策树的剪枝处理

   解决决策树的过拟合问题。剪枝策略有两种：

   • 预剪枝：在构造过程中先评估，再考虑是否分支。例如，在构造决策树的过程中，对一个节点考虑是否分支时，首先计算决策树不分支时在测试集上的性能，再计算分支之后的性能，若分支对性能没有提升，则选择不分支（即剪枝）。

   • 后剪枝：在构造好一棵完整的决策树后，自底向上，评估分支的必要性。例如，在构造好一颗完整的决策树后，从最下面的节点开始，考虑该节点分支对模型的性能是否有提升，若无则剪枝，即将该节点标记为叶子节点，类别标记为其包含样本最多的类别。

   • 预剪枝 vs 后剪枝

     预剪枝处理使得决策树的很多分支被剪掉，因此大大降低了训练时间开销，同时降低了过拟合的风险，但另一方面由于剪枝同时剪掉了当前节点后续子节点的分支，因此预剪枝“贪心”的本质阻止了分支的展开，在一定程度上带来了欠拟合的风险。而后剪枝则通常保留了更多的分支，因此采用后剪枝策略的决策树性能往往优于预剪枝，但其自底向上遍历了所有节点，并计算性能，训练时间开销相比预剪枝大大提升。

   一种后剪枝策略：

   • 损失函数的定义

     设树 $T$ 的叶节点个数为 $|T|$, $t$ 是树 $T$ 的叶节点，该节点有 $N_t$个样本点，其中 $k$ 类的样本点有 $N_{tk}$个， $k = 1, 2, \cdots, K, H_t(T)$为叶结点 $t$上的经验熵，$\alpha \ge 0$为参数，较大的 $\alpha$ 促使选择较简单的模型，较小的 $\alpha$ 促使选择较复杂的模型 ，则决策树学习的损失函数可以定义为
     $$
     G_{\alpha}(T) = \sum_{t = 1}^{|T|}N_tH_t(T) + \alpha|T|
     $$
     其中经验熵为：
     $$
     H_t(T) = -\sum_{k}\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}
     $$

   • 剪枝过程

     1. 计算每个节点的经验熵

     2. 递归地从树的叶节点向上回缩，设一组叶节点回缩到其父节点之前与之后的整体树分别为 $T_B$ 与 $T_A$，其对应的损失函数值分别是 $C_{\alpha}(T_B)$ 与 $C_{\alpha}(T_A)$，如果
        $$
        C_{\alpha} (T_A) <= C_{\alpha} (T_B)
        $$
        则进行剪枝，即将父节点变成新的叶节点

     3. 返回（2），直至不能继续为止，得到损失函数最小的子树 $T_{\alpha}$

9. 树形结构为什么不需要归一化？

   因为数值缩放不影响分裂点位置，每一个特征值的排列顺序不变，那么所属的分支以及分裂点就不会不同。而且，树模型是不能进行梯度下降的，因为构建树模型（回归树）寻找最优点时是通过寻找最优分裂点完成的，因此树模型是阶跃的，阶跃点是不可导的，也就不需要归一化

   而对于线性模型来说，特征值差别很大时，运用梯度下降时，损失等高线是椭圆形，需要进行多次迭代才能到达最优点。如果进行了归一化，那么等高线是圆形的，促使 SGD 往原点迭代，因而需要迭代次数较少

10. 决策树怎么处理连续值？

    CART回归树是假设树为二叉树，通过不断将特征进行分裂。比如当前树结点是基于第 $j$ 个特征值进行分裂的，设该特征值小于 $s$ 的样本划分为左子树，大于 $s$ 的样本划分为右子树。CART回归树实质上就是在该特征维度对样本空间进行划分，而这种空间划分的优化是一种NP难问题，因此，在决策树模型中是使用启发式方法解决。典型CART回归树（在《统计学习方法》中称为最小二乘回归树）产生的目标函数为：
    $$
    \sum_{x_i \in R_m}(y_i - f(x_i))^2
    $$
    因此，可以转换为求解以下目标函数：
    $$
    min_{j, s}[min_{c_1} \sum_{x_i \in R_1(j, s)} (y_i - c_1)^2 + min_{c_2} \sum_{x_i \in R_2(j,s) }(y_i - c_2)^2]
    $$
    其中，$R_1(j, s) = {x | x_j <= s}$，$R_2(j, s) = {x | x_j > s}$，$c_m = \frac{1}{N} \sum_{x_i \in R_m(j, s)}y_i (m = 1, 2)$

    ID3分类树和C4.5分类树基于信息增益和信息增益比处理连续值，遍历每一个特征值 $s$，将特征小于 $s$ 的样本划分为左子树，大于 $s$ 的样本划分为右子树，计算取不同 $s$ 时的信息增益，选取最大信息增益对应的特征值作为划分点。

11. 分类树和回归树的区别？

    • 回归树的每个节点都会得到一个预测值，例如第 10 点中提到的 $f(x_i)$，$c_1$ 和 $c_2$。（回归问题）
    • 分类树的每一个节点的类别取多数样本的类别（分类问题）
    • 回归树使用最小均方差划分节点
    • 分类树使用信息增益或增益比率来划分节点

12. 决策树如何处理缺失值？

    具体可参考 缺失值处理

    • 如何在训练样本属性缺失的情况下进行划分属性的选择？

      计算在该属性上没有缺失的样本集 $D’$ 的信息增益或其他指标，再乘以样本子集占样本集的比重。

    • 若样本在该属性上的值是缺失的，那么该如何对这个样本进行划分？

      将该样本划分到所有分支中，进入到每个分支后权重会被调整（每个样本的初始权重值为 1），更新后的权重值为 |子节点| / |父节点|

    • 测试样本中属性有缺失值？

      同时探查（计算）所有分支，然后算每个类别的概率，取概率最大的类别赋值给该样本

13. 决策树和逻辑回归的区别？

    • 决策树可以处理缺失值，而逻辑回归需要挖掘人员预先对缺失数据进行处理
    • 逻辑回归对数据整体结构的分析优于决策树，而决策树对局部结构的分析优于逻辑回归；（决策树由于采用分割的方法，所以能够深入数据内部，但同时失去了对全局的把握。一个分层一旦形成，它和别的层面或节点的关系就被切断了，以后的挖掘只能在局部中进行。同时由于切分，样本数量不断萎缩，所以无法支持对多变量的同时检验。而逻辑回归，始终着眼整个数据的拟合，所以对全局把握较好。但无法兼顾局部数据，或者说缺乏探查局部结构的内在机制。）
    • 逻辑回归擅长分析线性关系，而决策树对线性关系的把握较差。
    • 逻辑回归对极值比较敏感，容易受极端值的影响，而决策树在这方面表现较好。
    • 应用上的区别：决策树的结果和逻辑回归相比略显粗糙。逻辑回归原则上可以提供数据中每个观察点的概率，而决策树只能把挖掘对象分为有限的概率组群。
    • 执行速度：当数据量很大的时候，逻辑回归的执行速度非常慢，而决策树的运行速度明显快于逻辑回归。

集成学习

1. 什么是集成学习（Ensemble Learning）？

   面对一个机器学习问题，通常有两种策略。一种是研发人员尝试各种模型，选择其中表现最好的模型做重点调参优化。另一种策略是集各家之长，如同贤明的君主广泛地听取众多谋臣的建议，然后综合考虑，得到最终决策。后一种决策的核心，是将多个分类器的结果统一成一个最终的决策。使用这类策略的机器学习方法统称为集成学习。其中的每个单独的分类器称为基分类器（Base Learner）。

   ——《百面机器学习》

2. 集成学习分为哪几种？他们有何异同？

   • Boosting

     1. 基本思路：采用串行的方式训练基分类器，将基分类器层层叠加，每一层在训练的时候，对前一层的基分类器分错的样本，给予更高的权重，使得后续基学习器更加关注这些打标错误的训练样本。测试时，根据各层分类器的结果的加权得到最终的结果。
     2. 类似于人类迭代式学习：第一遍记住一部分，但也会犯一部分错误；第二遍学习，就会针对犯过错误的知识加强学习，减少类似的错误，如此不断循环往复，直到犯错误的次数减少到很低的程度

   • Bagging

     1. 基本思路：在训练过程中，各基分类器之间并行训练。著名算法之一，随机森林。为了让基分类器之间互相独立，将训练集分为若干子集
     2. Bagging 方法更像是一个集体决策的过程，每个个体都进行单独学习，学习内容可以相同，也可以不同，也可以部分重叠。在最终做决策时，每个个体单独作出判断，再通过投票的方式做出最后的集体决策。

   • Boosting vs Bagging

     Boosting 方法是通过逐步聚焦于基分类器分错的样本，减少集成分类器的偏差。Bagging 方法则是采取分而治之的策略，假设所有基分类器出错的概率是独立的，在某个测试样本上，用简单多数投票方法来集成结果，超过半数基分类器出错的概率会随着基分类器的数量增加而下降

3. Adaboost 算法

   • Adaboost 算法是 Boosting 算法的应用

   • 训练过程：

     1. 初始化训练数据的权值分布。如果有 $N$ 个样本，则每一个训练样本最开始时都被赋予相同的权值：$1/N$
     2. 训练弱分类器。具体训练过程中，如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它的权值就被降低；相反，如果某个样本点没有被准确地分类，那么它的权值就得到提高。然后，权值更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。
     3. 将各个训练得到的弱分类器组合成强分类器。加大分类误差率小的弱分类器的权重，降低分类误差率大的弱分类器的权重。

   • 算法流程：

     $N$：样本数量，$T$：基分类器数量

     • 初始化采样分布 $D_1(i) = 1 / N$ （初始化每个样本的权重）

     • 令 $t = 1, 2, \dots, T$ 循环：

       • 从训练集中，按照 $D_t$ 分布，采样出子集 $S_t = {x_i, y_i}, \ i = 1, \dots, N_t$

       • 用 $S_t$ 训练出基分类器 $h_t$

       • 计算 $h_t$ 的错误率
         $$
         \epsilon_t = \frac{\sum^{N_t}_{i = 1}I[h_t(x_i) \neq y_i]D_t(x_i)}{N_t}
         $$
         其中 $I[]$ 为判别函数

         为什么这里的分母是 $N_t$ 而不是 $\sum^{N_t}_{i = 1}D_t(x_i)$

       • 计算基分类器 $h_t$ 权重 $a_t = log\frac{(1 - \epsilon_t)}{\epsilon_t}$

       • 设置下一次采样（更新每个样本的权重）
         $$
         D_{t + 1} = \left{
         \begin{aligned}
         D_t(i) 或者 \frac{D_t(i)(1 - \epsilon_t)}{\epsilon_t}, \quad h_t(x_i) \neq y_i \
         \frac{D_t(i)\epsilon_t}{(1 - \epsilon_t)}, \quad h_t(x_i) = y_i \
         \end{aligned}
         \right.
         $$
         并将它归一化为一个概率分布函数

     • 合并基分类器：给定一个未知样本 $z$，输出分类结果为加权投票的结果 $Sign(\sum^T_{t = 1}h_t(z)a_t)$

4. Bagging 算法

   • Bagging使用“有放回”采样的方式选取训练集，对于包含m个样本的训练集，进行m次有放回的随机采样操作，从而得到m个样本的采样集，这样训练集中有接近36.8%的样本没有被采到。

   

   • 按照这种方式重复，采样得到 $T$ 个包含 $m$ 个样本的数据集，从而训练出 $T$ 个基分类器

   • 给定一个未知样本 $z$，由这 $T$ 个基分类器投票做出最后的决策

   • Bagging主要通过样本的扰动来增加基学习器之间的多样性，因此Bagging的基学习器应为那些对训练集十分敏感的不稳定学习算法，例如：神经网络与决策树等。

5. 如何从减小方差和偏差的角度解释 Boosting 和 Bagging 的原理

   • 偏差形容的是预测值和真实值间的偏差，偏差越小，则预测值越接近真实值；方差形容的是所有预测值的聚合程度，如果预测值越离散，则方差越高。
   • 在 Bagging 算法中，对 $n$ 个独立不相关的模型的预测结果取平均，方差变为原来单个模型的 $1 / n$。因此，诸多 Bagging 算法均追求模型的独立性。
   • 在Boosting 算法中，需要计算弱分类器的错误或者残差，作为下一个分类器的输入，这个过程本身就是在不断减少偏差的。但是 Boosting 的过程并不会显著降低方差，这是因为 Boosting 的训练过程是的各弱分类器之间是强相关的，缺乏独立性，所以并不会降低方差。

6. 最常用的基分类器是什么？为什么？

   最常用的基分类器是决策树，有以下 3 个方面的原因。

   • 决策树可以较为方便地将样本的权重整合到训练过程中，而不需要使用过采样的方法来调整样本的权重
   • 决策树的表达能力和泛化能力，可以通过调节树的层数来做折中
   • 数据样本的扰动对于决策树的影响较大，因此不同子样本集合生成的决策树基分类器随机性较大。

   除了决策树外，神经网络模型也适合作为基分类器，主要由于神经网络模型也比较“不稳定”，而且还可以通过调整神经元数量、连接方式、网络层数、初始权重等方式引入随机性。

7. 随机森林是什么？

   随机森林是一种基于树模型的 Bagging 的优化版本。随机森林中的基分类器具有多样性，这种基多样性不仅来自样本扰动，还来自属性扰动。

   • 样本扰动：有放回的取样
   • 属性扰动：在基决策树的训练过程中，在选择划分属性时，随机森林先从候选属性集中随机挑选出一个包含 $K$ 个属性的子集，再从这个子集中选择最优划分属性，一般推荐 $K = log_2(|D|)$
   • 建立过程
     • 如果训练集大小为N，对于每棵树而言，随机且有放回地从训练集中的抽取N个训练样本，作为该树的训练集
     • 如果每个样本的特征维度为M，指定一个常数 $m$，随机地从 $M$ 个特征中选取 $m$ 个特征子集，每次树进行分裂时，从特征子集中选择最优属性
     • 每棵树都尽最大程度的生长，并且没有剪枝过程
   • 优点
     1. 能够处理很高维度（feature很多）的数据，并且不用做特征选择（因为特征子集是随机选择的）
     2. 容易做成并行化方法（训练时树与树之间是相互独立的）
     3. 相比决策树的 Bagging 集成，训练速度更快，因为基决策树只在属性集的一个子集中选择划分属性
     4. 对于不平衡的数据集来说，它可以平衡误差
   • 缺点
     • 随机森林已经被证明在某些噪音较大的分类或回归问题上会过拟合
     • 对于有不同取值的属性的数据，取值划分较多的属性会对随机森林产生更大的影响，所以随机森林在这种数据上产出的属性权值是不可信的

8. 什么是 OOB？随机森林中的OOB是如何计算的？它有什么优缺点？

   • OOB：袋外错误率（Out-Of-Bag Error）
   • bagging方法中Bootstrap每次约有1/3的样本不会出现在Bootstrap所采集的样本集合中，当然也就没有参加决策树的建立，把这1/3的数据称为袋外数据，它可以用于取代测试集误差估计方法。
   • 可以通过计算袋外数据的误差来衡量模型的优劣，由于袋外数据是无偏估计的,所以在随机森林算法中不需要再进行交叉验证或者单独的测试集来获取测试集误差的无偏估计

9. 什么是梯度提升决策树（GBDT）？

   • 核心思想：基于树模型的Boosting思想，所有弱分类器的结果相加等于预测值。下一个弱分类器需要拟合之前所有弱分类器结论和的残差（这个残差就是预测值与真实值之间的误差）。这里的残差相当于当前模型的负梯度值。

     例如，用户 $A$ 的真实年龄是25岁，但第一棵决策树的预测年龄是 22 岁，差了 3 岁。那么在第二棵树里我们把 $A$ 的年龄设为 3 岁去学习；如果第二棵树的结论是 5 岁，则 $A$ 仍然存在 -2 岁的误差，第三棵树的年龄变为 -2 岁，继续学。

   • GBDT的会累加所有树的结果，而这种累加是无法通过分类完成的，因此GBDT的树都是CART回归树，而不是分类树

   • 训练过程

     假定训练集只有4个人：A, B, C, D，他们的年龄分别是14, 16, 24, 26。其中A、B分别是高一和高三学生；C, D分别是应届毕业生和工作两年的员工。如果是用一棵传统的回归决策树来训练，会得到如下图所示结果：

     

     现在我们使用GBDT来做这件事，由于数据太少，我们限定叶子节点做多有两个，即每棵树都只有一个分枝，并且限定只学两棵树。我们会得到如下图所示结果：

     

     第一棵树如上图左侧所示，每个节点使用平均年龄作为预测值。此时计算的残差如图所示，利用残差替代原值，在第二棵树（上图右侧）中学习。经过第二棵树，所有人的残差都为0，即每个人的预测值都等于真实值，预测值为所有树结论的累加。

10. GBDT的优点和局限性有哪些？

    • 优点：
      1. 预测阶段的计算速度快，树与树之间可并行化计算
      2. 在分布稠密的数据集上，泛化能力和表达能力都很好，这使得GBDT在Kaggle的众多竞赛中，经常名列榜首
      3. 采用决策树作为弱分类器使得GBDT模型具有较好的解释性和鲁棒性，能够自动发现特征间的高阶关系
    • 局限性
      1. GBDT在高维稀疏的数据集上，表现不如支持向量机或者神经网络
      2. GBDT在处理文本分类特征问题上，相对其他模型的优势不如它在处理数值特征时明显
      3. 训练过程需要串行训练，只能在决策树内部采用一些局部并行的手段提高训练速度

11. 因为 GBDT 对异常值明显，因此 GBDT 需要进行特征归一化（GBDT的学习过程有点类似于梯度下降）

12. 什么是 XGBoost？

    XGBoost 是 GBDT的优化版本，XGBoost 和 GBDT 比较大的不同就是目标函数的定义。XGBoost 的目标函数如下所示：
    $$
    Obj^{(t)} = \sum^n_{i = 1}l(y_i, \hat{y_i}^{(t - 1)} + f_t(x_i)) + \Omega(f_t) + constant
    $$
    其中，$l$ 表示损失函数（XGBoost 没有给出具体的损失函数定义），$\hat{y_i}^{(t - 1)}$ 是前一轮模型的预测值，即 $\hat{y_i}^{(t - 1)} = \sum^{t - 1}_{k = 1} f_k(x_i)$，$f_t(x_i)$ 是本轮模型的预测值，$\Omega(f_t)$ 是正则化项，是对模型复杂度的惩罚。

    接下来，就是利用泰勒二阶展开去做目标函数的近似。

    泰勒定理：

    如果 $n$ 是一个正整数，函数 $f$ 在 $a$ 点处 $n + 1$ 可导，那么对于这个区间上的任意 $x$，都有：
    $$
    f(x) = f(a) + \frac{f’(a)}{1!}(x - a) + \frac{f^{(2)}(a)}{2!}(x - a)^2 + \cdots + \frac{f^{(n)}(a)}{n!}(x - a)^n + R_n(x)
    $$
    其中，$R_n(x)$ 是泰勒公式的余项，是 $(x - a)^n$ 的高阶无穷小

    泰勒二阶展开为：
    $$
    f(x + \Delta x) \simeq f(x) + f’(x)\Delta x + \frac{1}{2}f’’(x)\Delta x^2
    $$
    将目标函数 $Obj^{(t)}$ 和泰勒二阶展开一一对应起来：

    • $Obj^{(t)} \rightarrow f$

    • $x \rightarrow \hat{y_i}^{(t - 1)}$

    • $\Delta x \rightarrow f_t(x_i)$

    因此目标函数 $Obj^{(t)}$ 经过泰勒二阶展开后得到：
    $$
    Obj^{(t)} \simeq \sum^{n}{i = 1}[l(y_i, \hat{y_i}^{(t- 1)}) + g_if_t(x_i) + \frac{1}{2}h_if^2_t(x_i)] + \Omega(f_t) + constant
    $$
    其中，$g_i = \partial{\hat{y}^{(t - 1)}}l(y_i, \hat{y}^{(t - 1)}), \quad h_i = \partial^2_{\hat{y}^{(t - 1)}}l(y_i, \hat{y}^{(t -1)})$

    因为 $\hat{y}^{(t -1)}$ 由前一轮的模型确定$\longrightarrow l(y_i, \hat{y}^{(t -1)}$) 确定，不影响目标函数优化，$l(y_i, \hat{y}^{(t -1)})$ 和常数项都可以从目标函数中移除，由此得到推导后的目标函数。
    $$
    Obj^{(t)} \simeq \sum^{n}_{i = 1}[g_if_t(x_i) + \frac{1}{2}h_if^2_t(x_i)] + \Omega(f_t)
    $$
    此时，目标函数仅依赖损失函数的一阶导数 $g_i$ 和二阶导数 $h_i$，而不依赖于损失函数。

    接下来，我们来看看 XGBoosting 中树的复杂度，树遵循以下几个规则：

    • 每个样本都落在叶子节点上
    • $q(x)$ 表示样本 $x$ 落在的叶子节点，每个样本 $x$ 都能通过函数 $q(x)$ 映射到树中的某一个叶子节点
    • $w_{q(x)}$ 表示样本 $x$ 在叶子节点 $q(x)$ 的预测值

    目标函数 $Obj^{(t)}$ 中的正则化项 $\Omega(f_t)$ 包含两个部分：
    $$
    \Omega(f_t) = \gamma T + \frac{1}{2} \lambda \sum^T_{j = 1} w^2_j
    $$
    其中，$T$ 表示叶子节点的个数，$w_j$ 表示叶子节点的预测值，$\frac{1}{2} \lambda \sum^T_{j = 1} w^2_j$ 的惩罚是为了避免某一个叶子节点的预测值过大。

    上述目标函数中的 $f_t(x_i)$，其实就是 $w_j$，因此目标函数可以进一步合并为：
    $$
    \begin{align}
    Obj^{(t)} &\simeq \sum^{n}{i = 1}[g_if_t(x_i) + \frac{1}{2}h_if^2_t(x_i)] + \Omega(f_t) \
    &= \sum^{n}{i = 1}[g_iw_q(x_i) + \frac{1}{2}h_iw^2_q(x_i)] + \gamma T + \frac{1}{2} \lambda \sum^T_{j = 1} w^2_j \
    &= \sum^T_{j = 1}[(\sum_{i \in I_j} g_i)w_j + \frac{1}{2}(\sum_{i \in I_j}h_i + \lambda)w^2_j] + \gamma T
    \end{align}
    $$
    其中，$I_j$ 为每个叶节点中的下标集合，$I_i = {i | q(x_i) = j }$

    令 $G_j = \sum_{i \in I_j} g_i, \quad H_j = \sum_{i \in I_j} h_i$

    最终，目标函数化简为：
    $$
    Obj^{(t)} = \sum^T_{j = 1}[(G_jw_j + \frac{1}{2}(H_j + \lambda)w^2_j] + \gamma T
    $$
    计算目标函数的极小值点：
    $$
    \partial w_j Obj^{(t)} = G_j + (H_j + \lambda)w_j
    $$
    令 $\partial w_j Obj^{(t)} = 0$， 得到：
    $$
    w_j = -\frac{G_j}{H_j + \lambda} \
    $$
    带入到目标函数中得到：
    $$
    Obj^{(t)} = -\frac{1}{2} \sum^T_{j = 1} \frac{G^2_j}{H_j + \lambda} + \gamma T
    $$
    目标函数可以直观理解为当我们指定一个树结构时，最多在目标函数减少多少。上面推导的目标函数为所有叶节点的求和，正如前面的 ID3树、C4.5树和 CART树，我们在确定某一个节点是否还要往下继续分裂时，需要比较节点分裂前后的增益 Gain，并根据增益 Gain 选择最优特征。增益Gain的表达式如下所示：

    

    XGBoost使用了和CART回归树一样的想法，利用贪婪算法，遍历所有特征的所有特征划分点，不同的是使用的目标函数不一样。

13. XGBoost 中树停止生长的条件？

    • 当引入的分裂带来的增益小于设定阀值
    • 当树达到最大深度时则停止建立决策树，设置一个超参数max_depth，避免树太深导致学习局部样本，从而防止过拟合
    • 样本权重和小于设定阈值时则停止建树。什么意思呢，即涉及到一个超参数-最小的样本权重和min_child_weight，和GBM的 min_child_leaf 参数类似，但不完全一样。大意就是一个叶子节点样本太少了，也终止同样是防止过拟合

14. XGBoost 和 GBDT 的区别是什么？

    XGBoost 可以理解为 GBDT 的优化版本，与 GBDT 相比，无论是精度还是效率上都有了提升。和 GBDT 相比，具体的优点有：

    • 损失函数使用了泰勒展开二项逼近，而不是像 GBDT 里是一阶导数
    • 对树的结构进行了正则化约束，防止模型过度复杂，降低了过拟合的可能性
    • 节点分裂的方式不同，GBDT 使用的是基尼系数（GBDT的每一棵树都是 CART 回归树），而 XGBoost 使用的是经过优化推导后得出的增益评分

15. XGBoost 为什么使用泰勒展开？优势在哪里？

    XGBoost 使用了一阶和二阶偏导, 二阶导数有利于梯度下降的更快更准。使用泰勒展开取得函数做自变量的二阶导数形式，可以在不选定损失函数具体形式的情况下，仅仅依靠输入数据的值就可以进行叶子分裂优化计算，本质上也就把损失函数的选取和模型算法优化/参数选择分开了（因为没有确定的损失函数）。这种去耦合增加了XGBoost的适用性, 使得它按需选取损失函数, 可以用于分类, 也可以用于回归。

16. 什么是 LightGBM