机器学习面试基础1

为什么要对特征做归一化 (easy)
什么是组合特征（Categorical Feature的组合）？如何处理高维组合特征 (medium)
比较欧式距离与曼哈顿距离 (medium)
为什么一些场景中使用余弦相似度而不是欧式距离 (medium)
One-hot的作用是什么？为什么不直接使用数字作为表示？(medium)

在模型评估过程中，过拟合和欠拟合具体指什么现象 (easy)
降低过拟合和欠拟合的方法 (medium)
L1和L2正则先验分别服从什么分布 (medium)
对于树形结构为什么不需要归一化？ (medium)
什么是数据不平衡，如何解决？(medium)

逻辑回归相比线性回归，有何异同 (easy)
回归问题常用的性能度量指标 (medium)
分类问题常见的性能度量指标 (medium)
逻辑回归的损失函数 (medium)
逻辑回归处理多标签分类问题时，一般怎么做？(medium)

写出全概率公式 & 贝叶斯公式
朴素贝叶斯为什么“朴素”？
朴素贝叶斯的工作流程
朴素贝叶斯有没有超参数可以调？
朴素贝叶斯对异常值不敏感？

什么是集成学习算法
集成学习主要有哪几种框架？分别简述这几种集成学习框架的工作过程？
Boosting 算法有哪两类，它们之间的区别是什么？
什么是偏差和方差？
为什么说Bagging可以减少弱分类器的方差，而Boosting可以减少弱分类器的偏差？

简述一下随机森林算法的原理
随机森林的随机性体现在哪里？
随机森林的优缺点
随机森林为什么不能用全样本去训练m棵决策树？
随机森林为什么不能用全样本去训练m棵决策树？

简述GBDT原理
GBDT如何用于分类？
GBDT常用的损失函数有哪些？
为什么GBDT不适合使用高维稀疏特征？
GBDT算法的优缺点

简述XGBoost
XGBoost 和 GBDT有什么不同？
XGBoost为什么可以并行训练？
XGBoost防止或拟合的方法？
XGBoost为什么这么快？

_2020.11.10

1. 为什么要对特征做归一化 easy

首先分清归一化和标准化的区别：

归一化(normalization): $\frac{X_i - X_{min}}{X_{max} - X_{min}}$
标准化(standardization): $\frac{X_i - \mu}{\sigma}$
二者本质上都是线性变换，而线性变化不会改变原始数据的数值排序。

在采用基于梯度更新的学习方法（包括线性回归、逻辑回归、SVM、神经网络等）对模型求解的过程中，未归一化的数值特征在学习时，梯度下降较为抖动，模型难以收敛，通常需要较长的时间模型才能收敛。下图中，左边为特征未归一化时，模型的收敛过程，右边是经过特征归一化之后的模型的收敛过程。

未归一化/归一化后模型收敛过程

2. 什么是组合特征（Categorical Feature的组合）？如何处理高维组合特征 (medium)

狭义的组合特征即将类别特征（Categorical feature）两个或者多个特征组合（数字里面的组合概念）起来，构成高阶组合特征。

比如：假设Macbook的CPU型号和SSD大小对于是否购买行为的影响用下面的表格表示：

那么CPU型号和SSD大小的组合特征对是否购买行为的影响为：

组合特征的不同取值个数（number of unique values）为单个特征的不同取值的个数的乘积。假设数据的特征向量为 $X=(x_1, x_2, ..., x_k)$ 则 $|<x_i, x_j>| = |x_i| \cdot |x_j|$ （意义是： $x_i$ , $x_j$ 的组合特征的取值个数，是二者各自特征取值个数的乘积）。其中 $<x_i, x_j>$ 为特征 $x_i$ 和特征 $x_j$ 的组合特征， $|x_i|$ 表示特征 $x_i$ 不同取值的个数， $|x_j|$ 表示特征 $x_j$ 不同取值的个数。假设采用以线性模型为基础的模型来拟合特征时，比如以逻辑回归为例:
$Y = sigmoid (\sum_{i} \sum_{j} w_{ij} <x_i, x_j>)$

需要学习的参数 $w_{ij}$ 的长度为 $|<x_i, x_j>|$ ；如果 $|x_i| = m$ ， $|x_j| = n$ ，则参数规模为 $m*n$ 。当m和n非常大时，经过特征组合后的模型就会变得非常复杂。一个可行的方法是，做特征的embedding，即将 $x_i$ , $x_j$ 分别用长度为k的低维向量表示 (k << m, k << n)；那么学习参数的规模则变为 mk + nk + k*k

3. 比较欧式距离与曼哈顿距离 (medium)

欧式距离(L2-距离)： $d = \sqrt{\sum_{k=1}^n |a_k - b_k|^2}$
曼哈顿距离(L1-距离)： $d = \sum_{k=1}^n |a_k - b_k|$

在基于地图、导航等应用中，欧式距离根据各个维度上的距离自动地给每个维度计算了一个“贡献权重”，这个权重会因为各个维度上距离的变化而动态地发生变化；而曼哈顿距离的每个维度对最终的距离都有同样的贡献权重。

欧式距离是两点间的直线距离，图中的绿线；
曼哈顿距离则是图中红色直角线。

4. 为什么一些场景中使用余弦相似度而不是欧式距离 (medium)

假设有A和B两个向量，其余弦相似度定义为 $cos(A, B) = \frac{A*B}{||A||_2 ||B||_2}$ ，即两个向量夹角的余弦。

它关注的是向量之间的角度关系、相对差异，而不关心它们的绝对大小。
其取值范围在 $[-1, 1]$ 之间。
两个向量相同时为1，正交时为0，相反时为-1。即在取值范围内，余弦距离值越大，两个向量越接近。

余弦距离为向量之间的相似度提供了一个稳定的指标，无论向量维度多与少；特征的取值范围大与小。余弦距离的取值范围始终都能保持在 $[-1, 1]$ 。余弦相似度广泛应用在文本、图像和视频领域。
相比之下欧式距离则受到维度多少，取值范围大小以及可解释性的限制。当特征的取值以及特征向量经过模长归一化之后，余弦距离和欧式距离又存在以下的单调关系。
$||A-B||_2 = \sqrt{2(1 - cos(A, B))}$

5. One-hot的作用是什么？为什么不直接使用数字作为表示？

One-hot主要用来编码类别特征，即采用哑变量(dummy variables)对类别进行编码。它的作用时避免因将类别用数字表示而给函数带来都懂。直接使用数字会将人工误差而导致的假设引入到类别特征中，比如类别之间的大小关系，以及差异关系等等。

_2020.11.11

6. 在模型评估过程中，过拟合和欠拟合具体指什么现象 (easy)

过拟合是指模型对于训练数据呈过当的情况，反映到评估指标上，就是模型在训练集上表现很好，但是在测试集和新数据上的表现差。
欠拟合指的是模型在训练和预测时表现都不好。
用模型在数据上的偏差和方差来表示就是：欠拟合时候，偏差较大，方差较小。过拟合时，偏差较小但是方差较大。

图中蓝点反应的是训练集上的样本在测试集的预测

7. 降低过拟合和欠拟合的方法 (medium)

降低过拟合：

特征：减少不必要的特征（降维）
<1> 根据特征的重要性，直接删除稀疏特征
<2> 通过收集更多的数据，或者用data augmentation的方法，产生更多的训练数据；从而阻止模型学习不相关的特征。
降低模型复杂度
<1> 神经网络：减少网络层数和神经元个数
<2> 决策树模型中降低树的深度，进行剪枝
正则化
<1> 加入正则化项并提高正则化的系数，对复杂模型和系数比较大的模型进行惩罚，使得算法倾向于训练简单的模型。
多模型决策
<1> 采用bagging或者stacking的集成方法，将多个模型融合起来共同决策。以减少模型预测的variance。
模型训练
<1> 训练模型时采用早停策略或采用知识蒸馏的方法进行训练。
数据目标
<1> 比如用分类任务的标签平滑方法，即在one-hot表示的GT标签里面，将值为1的一小部分值减小，均分到其他为0的位置上（还是teacher-student里面的概念）

降低欠拟合的方法

添加新特征，比如上下文特征、ID类特征、组合特征(feature crossing)等等
模型复杂度：增加模型复杂度
<1> 在线性模型中添加高次项。
<2> 在神经网络中增加网络层数或神经元个数。
正则化：减少正则化的系数。

8. L1和L2正则先验分别服从什么分布 (medium)

L1正则先验服从laplace分布：
$f(x|\mu, \delta) = \frac{1}{2 \delta} \exp{(-\frac{|x-\mu|}{\delta})}$

L2 正则服从Gaussian分布：
$f(x|\mu, \delta) = \frac{1}{\sqrt{2\pi}} \exp{(-\frac{(x-\mu)^2}{2\delta ^2})}$

接下来从最大后验概率的角度进行推导和分析。在机器学习建模中，我们知道了x和y之后，需要对参数进行建模。那么后验概率表达式如下：（后验概率 := 似然 * 先验概率）
$P = \log{(P(y | X, w)P(w))} = \log(P(y|X, w)) + \log(P(w))$

可以看出来后验概率函数为在似然函数的基础上增加了 $log P(w)$ ， $P(w)$ 的意义是对权重系数w的概率分布的先验证假设。在收集到训练样本X, y 后，则可根据w在X，y 下的后验概率对w进行修正，从而做出对w的更好的估计。若假设w是先验分布为0的均值高斯分布，即：
$P(w) = \frac{1}{\sqrt{2\pi} \delta} \exp(-\frac{x^2}{2 \delta ^2})$
则有:
$log P(w) = log(\prod_{j} P(w_j)) = \sum_j \log \Big( \Big[ \frac{1}{\sqrt{2\pi} \delta} \exp(-\frac{x_j^2}{2 \delta^2}) \Big] \Big) = -\frac{1}{2\delta^2} \sum_j x_j^2 + C$

可以看到，在高斯分布下的效果等价于在代价函数中增加L2正则项。

若假设w服从均值为0，参数为 $\delta$ 的拉普拉斯分布，即：
$P(w_j) = \frac{1}{2\delta} \exp(-\frac{|x|}{\delta})$
则有：
$log P(w) = log(\prod_j P(w_j)) = \sum_j log \Big( \frac{1}{2\delta} \exp(-\frac{|x|}{\delta}) \Big) = -\frac{1}{\delta} \sum_j |x_j| + C$

可以看到，在拉普拉斯分布下的效果等价于在代价函数增加L1正则项。

9. 对于树形结构为什么不需要归一化？ (medium)

决策树的学习过程本质上是选择合适的特征，分裂并构建树节点的过程；而分裂节点的标准是由树构建前后的信息增益，信息增益比以及Gini Index等指标决定的。这些指标与当前特征值的大小本身并无关系。

10. 什么是数据不平衡，如何解决？(medium)

数据不平衡主要指的是在有监督机器学习任务重，样本标签的分布不均匀。这将使得模型更倾向于将结果预测为样本标签分布较多的值，从而使得少数样本的预测性能下降。绝大多数常见的机器学习算法对于不平衡数据集都不能很好地工作。

解决方法：

重新采样训练集：
a. 欠采样 - 减少丰富类的大小来平衡数据集。
b. 过采样 - 增加稀有样本，通过使用重复、自举或合成少数类。
设计使用不平衡数据集的模型：
a. 在代价函数中惩罚稀有类别的错误分类。

拓展：

在论文 CReST: A Class-Rebalancing Self-Training Framework for Imbalanced Semi-Supervised Learning 中提出了一种新颖的观点：
作者观察到：

对于标注不完全的数据集，数据往往呈现“长尾效应”，即：多数的label集中在了常见的“头部类别”(Head Classes)上（person, car, dog 等），而不常见的“尾部类别”(Tail Classes)则标注很少。
当用常见的方法（过采样等）去训练网络并在验证集上预测时发现，对于头部类别，预测结果的Recall很高，而Precision很低。前者说明，对于训练样本充足的类别，模型可以很好地将它们识别说出来；后者则说明，模型对于不确定的尾部类别，会倾向于把它们分类到某一个“头部样本”中，从而导致了头部样本的假阳性(False Positive)变多，从而precision下降。
对于尾部样本，预测结果的Recall很低，而Precision很高。因为通常情况下，模型在头部样本是overfit的，而在尾部样本是underfit的，所以一旦模型认为某样本是尾部类别，那么这个预测的可信度就很高。

基于上述的实验观察，作者提出了解决方案：
用常见的方法训练模型，并让模型进行预测，从预测中挑出“尾部类别”。此时模型预测的“尾部类别”的可信度很高，把它们当作伪标签，加入一轮的训练当中。

_2020.11.12

11. 逻辑回归相比线性回归，有何异同 (easy)

逻辑回归解决的是分类问题，线性回归解决的是回归问题。逻辑回归又可以认为是广义线性回归的一种特殊形式，其特殊之处在于目标(label/target)的取值服从二元分布。

所谓逻辑回归是一种特殊的广义线性回归，我们可以通过狭义线性回归到逻辑回归的转化过程来理解。

狭义线性回归的表达式为： $y = w \cdot x + b$
如果我们希望这个模型可以对二分类任务做出预测，即目标满足0，1分布。那么希望预测出来的值经过某种转换之后，大部分可以分布在0，1两个值附近。

这就自然而然想到了sigmoid函数： $\sigma(z) = \frac{1}{1 + e^{-z}}$
令： $y = \sigma(z)$ ，
则： $\log (\frac{y}{1-y}) = z = wx + b$

可以看到相比于狭义线性回归采用y作为预测结果，逻辑回归则采用 $log(\frac{y}{1-y})$ 作为预测结果。逻辑回归还可以表示为：
$y = \sigma(wx + b)$
通过以上的步骤推演，我们知道逻辑回归的求值计算其实就是在线性回归的基础上，再做一个sigmoid计算，所以它们都可以用相同的方法比如梯度下降来求解参数。

12. 回归问题常用的性能度量指标 (medium)

点对点误差：

MSE均方差 - 预测数据和原始数据对应误差的平方和的均值 (L2)
RMSE(Root Mean Square Error) - 观测值与真值偏差的平方和与观测次数n比值的平方根，用来衡量观测值同真值之间的偏差。
$RMSE = \sqrt{MSE}$
MAE(Mean Absolute Error) - 计算模型输出与真实值之间的平均绝对误差 (L1)

带归一化的误差求解方法

MAPE (Mean Absolute Percentage Error) - 不仅考虑预测值与真实值误差，还考虑误差与真实值之间的比例。
$MAPE = \frac{1}{n} \sum_{i=0}^n \Big( \frac{|y_i - \hat{y_i}|}{y_i} \Big)$
MASE (Mean Absolute Scaled Error) - 平均平方百分比误差
$MASE = \frac{1}{n} \sum_{i=0}^n \Big( \frac{y_i - \hat{y_i}}{y_i} \Big)^2$

13. 分类问题常见的性能度量指标 (medium)

Confusion Matrix

$Accuracy = \frac{TP + TN}{TP + FN + FP + TN}$
所有预测正确的样本与所有样本的比值。

$Precision = \frac{TP}{TP + FP}$
针对预测结果而言的。所有预测为正的样本中，有多少是真正的正样本。

$Recall = \frac{TP}{TP + FN}$
针对原来的样本而言的。

14. 逻辑回归的损失函数 (medium)

15. 逻辑回归处理多标签分类问题时，一般怎么做？(medium)

_2020.11.13

16. 写出全概率公式 & 贝叶斯公式

全概率公式： $P(A) = \sum_n P(A|B_n)P(B_n)$

贝叶斯公式： $P(A|B) = \frac{P(B|A) P(A)}{P(B)}$

17. 朴素贝叶斯为什么“朴素”？

朴素贝叶斯中的朴素可以理解为“简单、理想化”。它是假设了样本特征之间是相互独立、没有相关关系。这个假设在现实中是很不真实的，属性之间并不都是相互独立的，有些属性也会存在相关性。

18. 朴素贝叶斯的工作流程

三个阶段：1.准备阶段、2.分类器训练阶段、3.应用阶段。

准备阶段：根据具体情况确定特征属性，并对每个特征属性进行适当划分，去除高度相关性的属性（如果两个属性具有高度相关性的话，那么该属性将会在模型中发挥2次作用，会使得朴素贝叶斯所预测的结果向该属性所希望的方向偏离，导致分类出现偏差），然后人工对一部分待分类项进行分类，形成训练样本集合。这一阶段的输入是所有待分类数据，输出是特征属性和训练样本。（这一阶段是整个朴素贝叶斯分类中唯一需要人工完成的阶段，其质量对整个过程都有重要影响）。
分类器训练阶段：计算每个类别在训练样本中出现频率及每个特征属性划分对每个类别的条件概率估计，并将结果记录。其输入是特征属性和训练样本，输出是分类器。从公式上理解，朴素贝叶斯分类器模型的训练目的就是要计算一个后验概率 $P(c|x)$ 使得在给定特征的情况下，模型可以估计出每个类别出现的概率情况。
$$P(c|x) = \frac{P(c)P(x|c)}{P(x)} = $\frac{P(c)} {P(x)} \prod_{i=1}^d P(x_i|c)$

因为 $P(x)$ 是一个先验概率，它对所有类别来说都是相同的；而我们在预测的时候会比较每个类别相对的概率情况，选取最大的那个作为输出值。所以我们可以不计算 $P(x)$ 。所以贝叶斯学习的过程就是要根据训练数据统计计算先验概率 $P(c)$ 的后验概率 $P(x_i|c)$

应用阶段：这个阶段的任务使用分类器对待分类项进行分类，其输入是分类器和待分类项，输出是待分类项与类别的映射关系，并选出概率值最高所对应的类别；用公式表示即为：
$h(x) = argmax_{c \in y} P(c) \prod_{i=1}^d P(x_i|c)$

19. 朴素贝叶斯有没有超参数可以调？

朴素贝叶斯模型的训练过程，本质上是通过数学统计方法从训练数据中统计先验概率 $P(c)$ 和后验概率 $P(x_i | c)$ ，而这个过程是不需要超参数调节的。所以朴素贝叶斯模型没有可调节的参数。虽然在实际应用中朴素贝叶斯会与拉普拉斯平滑修正(Laplacian Smoothing Correction) 一起使用，而拉普拉斯平滑修正方法中有平滑系数这一超参数，但是这并不属于朴素贝叶斯模型本身的范畴。

20. 朴素贝叶斯对异常值不敏感？

朴素贝叶斯模型的训练过程，本质上是通过数学统计方法从训练数据中统计先验概率 $P(c)$ 和后验概率 $P(x_i | c)$ ，少数的异常值，不会对统计结果造成比较大的影响。所以朴素贝叶斯模型对异常值不敏感。

_2020.11.16

21. 什么是集成学习算法

集成学习（Ensemble Learning）就是将多个机器学习模型组合起来，共同工作以达到优化算法的目的。集成学习的一般步骤是：

生产一组“个体学习器（individual learner）”。
用某种策略将它们结合起来。

个体学习器通常由一个现有的学习算法从训练数据产生。在同质集成（系统中个体学习器的类型相同）中，个体学习器又被称为“基学习器”而在异质集成（系统中个体学习的类型不同）中，个体学习器又称为“组件学习器(component learner)”。

22. 集成学习主要有哪几种框架？分别简述这几种集成学习框架的工作过程？

集成学习主要的集成框架有，bagging，boosting和stacking，其中bagging和boosting为同质集成，而stacking和bossting为异质集成。

Bagging （Bootstrap Aggregating）：Bagging的核心思想为并行地训练一系列各自独立的同类模型，然后再将各个模型的输出结果按照某种策略进行聚合（例如分类中可采用投票策略，回归中可采用平均策略）。Bagging方法主要分为两个阶段：
- Bootstrap阶段，即采用有放回的抽样方法，将训练集分为n个子样本集：并用基学习器对每组样本分别进行训练，得到n个基模型。
- Aggregating阶段，将上一个阶段训练得到的n个基模型组合起来，共同做决策。在分类任务中，可采用投票法。比如相对多数投票法，即将结果预测为得票最多的类别。而在回归任务中可采用平均法，即将每个基模型预测得到的结果进行简答平均或者加权平均来获得最终的预测结果。
Stacking：Stacking的核心思想并行地训练一系列各自独立的不同类模型，然后通过训练一个元模型（meta-model）来将各个模型的输出结果进行结合。
- 第一阶段，分别采用全部训练样本训练n个组件模型，要求这些个体学习器必须是异构的，也就是说采用的学习方法不同；比如可以分别是线性学习器，SVM，决策树模型和深度模型。
- 第二阶段，训练一个元模型（meta-model）来将各个组件模型的输出结果进行结合。具体过程是，将各个学习器在训练集上得到的预测结果作为训练特征和训练集的真实结果组成新的训练集：用这个新组成的训练集来训练一个元模型。这个元模型可以是线性模型或者树模型。
Boosting：Boosting的核心思想为串行地训练一系列前后依赖的同类模型，即后一个模型用来对前一个模型的输出结果进行纠正。Boosting算法是可将弱学习器提升为强学习的算法。学习过程是：先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器数目达到实现指定的值T，最终将这T个基学习器进行结合。

23. Boosting 算法有哪两类，它们之间的区别是什么？

Boosting算法主要有AdaBoost (Adaptive Boost) 自适应提升算法和Gradient Boosting梯度提升算法。最主要的区别在于两者如何识别和解决模型的问题。AdaBoost 用分错的数据样本来识别问题，通过调整分错的数据样本的权重来改进模型。Gradient Boosting通过负梯度来识别问题，通过计算负梯度来改进模型。

24. 什么是偏差和方差？

偏差指的是预测值的期望与真实值之间的差距，偏差越大，预测值越偏离真实数据的标签。

方差描述的是预测值的变化范围，离散程度，也就是离预测值期望的距离，方差越大，数据的分布越分散。

可通过打靶射击的例子来做类比理解，我们假设一次射击就是一个机器学习模型对一个样本进行预测，射中红色靶心位置代表预测准确，偏离靶心越远代表预测误差越大。偏差则是衡量射击的蓝点离红圈的远近，射击位置即蓝点离红点把心越近则偏差越小，蓝点离红色靶心越远则偏差越大；方差衡量的是射击时手是否稳即射击的位置蓝点是否聚集，蓝点越集中则方差越小，蓝点越分散则方差越大。

25. 为什么说Bagging可以减少弱分类器的方差，而Boosting可以减少弱分类器的偏差？

Bagging算法对数据重采样，然后在每个样本集训练出来的模型上取平均值。假设有n个随机变量，方差记为 $\delta ^2$ ，两两变量之间的相关性是 $0 < \rho < 1$ ，则n个随机变量的均值的方差为：
$var( \frac{1}{n} \sum_{i=1}^n X_i ) = \frac{\delta ^2}{n} + \frac{n-1}{n} \rho \delta ^2$

上式中随着n增大，第一项趋于0，第二项趋于 $\rho \delta^2$ ，所以Bagging能够降低整体方差。在随机变量完全独立的情况下，n个随机变量的方差为 $\frac{\delta ^2}{n}$ ，n个随机变量的方差是原来的 $\frac{1}{n}$ 。

Bagging算法对n个独立不相关的模型的预测结果取平均，方差可以得到减少，如果模型之间相互独立，则集成后模型的方差可以降为原来的
$\frac{1}{n}$ ，但是在现实情况下，模型不可能完全独立，为了追求模型的独立性，Bagging的方法做了不同的改进，比如随机森林算法中，每次选取节点为分裂属性时，会随机抽样一个属性子集，而不是从所有的属性中选最有属性，这就为了避免弱分类器之间过强的关联性，通过训练集的重采样也能够带来弱分类器之间的一定独立性，这样多个模型学习数据，不会因为一个模型学习到数据某个特殊性而造成方差过高。

设单模型的期望为 $\mu$ ，则bagging的期望预测为：
$E(\frac{1}{n} \sum_{i=1}^n X_i) = \frac{1}{n} E(\sum_{i=1}^n X_i) = E(X_i) \approx \mu$
说明Bagging整体模型的期望近似于单模型的期望，这意味模型的偏差也与单模型的偏差近似。所以Bagging不能减少偏差。

Boosting算法训练过程中，我们计算弱分类器的错误和残差，作为下一个分类器的输入，这个过程本身就在不断减小损失函数，其偏差自然逐步下降。但由于是采取这种串行和自适应的策略，各子模型之间是强相关的，于是子模型之和并不能显著降低方差。所以说boosting主要还是靠降低偏差来提升预测精度。

_2020.11.17

26. 简述一下随机森林算法的原理

随机森林算法是Bagging集成框架下的一种算法，它同时对训练数据和特征采用随机抽样的方法来构建更加多样化的基模型。随机森林具体的步骤如下：

假如有N个样本，则有放回地随机选择N个样本。这N个样本用来训练一个决策树，作为决策树根节点处的样本
假设每个样本有M个属性，在决策树的每个节点需要分裂时，随机从这个M个属性中选取处m个属性，满足条件 $m << M$ 。然后从这m个属性中采用某种策略（比如信息增益）来选择1个属性作为该节点的分裂属性。
决策树形成过程中每个节点都要按照步骤2来分裂（很容易理解，如果下一次该节点选出来的那一个属性是刚刚其父节点分裂时用过的属性，则该节点已经达到了叶节点，无须继续分裂了）。一直到不能够再分裂为止。注意整个觉额书形成过程中没有进行剪枝。
按照步骤1-3建立大量的决策树，这样就构成了随机森林。

27. 随机森林的随机性体现在哪里？

体现在每颗树的训练样本是随机的，树中的每个节点的分裂属性集合也是随机选择确定的。

随机采样：随机森林在计算每棵树时，从全部训练样本（样本数为n）中选取一个可能有重复的，大小同样为n的数据集进行训练（即bootstrap采样）。
特征选取的随机性：在每个节点随机选取所有特征的一个子集

28. 随机森林的优缺点

优点：

特征和数据的随机抽样

它可以处理很高维度（特征很多）的数据，并且不用降维，无需做特征选择。
如果有很大一部分的特征遗失，仍可以维持准确度。
不容易过拟合。
对于不平衡的数据集来说，它可以平衡误差。
可以判读出不同特征之间的相互影响（类似于控制变量法）

树模型的特性：

它可以判断特征的重要程度。

算法结构：

训练速度比较快，容易做成并行方法。
实现起来比较简单。

缺点：

随机森林已经被证明在某些噪音较大的分类或回归问题上会过拟合。（决策树的学习本质上进行的是决策节点的分裂，依赖于训练数据的空间分布）
对于有不同取值的属性的数据，取值划分较多的属性会对随机森林产生更大的影响，所以随机森林在这种数据上阐述的属性权值是不可信的。

29. 随机森林为什么不能用全样本去训练m棵决策树？

随机森林的基学习器是同构的，都是决策树，如果用全样本去训练m棵决策树的话；
基模型之间的多样性减少，互相相关的程度增加，不能够有效起到减少方差的作用；对于模型的泛化能力是有害的。

30. 随机森林和GBDT的区别

随机森林采用的bagging思想，而GBDT采用的boosting思想
组成随机森林的树可以并行生成；而GBDT只能是串行生成。
随机森林对异常值不敏感；GBDT对异常值非常敏感。
随机森林对训练集一视同仁；GBDT对训练集中预测错误的样本给予了更多关注。
随机森林是通过减少模型方差提高性能；GBDT是通过减少模型偏差提高性能。
对于最终的输出结果而言，随机森林采用多数投票等；而GBDT则是将所有结果累加起来，或者加权累加起来。
组成随机森林的树可以是分类书，也可以是回归树；而GBDT只能由回归树组成。

_2020.11.18

31. 简述GBDT原理

梯度提升树的训练过程大致是这样的：

根据训练集训练一颗初始决策树
计算之前所有树在此数据集上预测结果之和与真实结果的差值，又叫做残差。
把残差作为当前树拟合的目标，在训练集上训练。
重复2、3步骤，直到达到设置的阈值（树的个数、早停策略等）

采用伪代码表示如下：
输入：训练数据集 $D = {(x_1, y_1), (x_2, y_2), ..., (x_n, y_n)}$ ，其中 $x_i \in \mathbf{x} \subseteq \mathbb{R}^n$ , $y_i \in y \subseteq \mathbb{R}$

输出：提升树 $f_M(x)$
$\space \space$ (1) 初始化f_0(x) = 0
$\space \space$ (2) 对 $m = 1, 2, ..., M$ :
$\space \space \space \space$ a. 计算残差: $r_{mi} = y_i - f_{m-1}(x_i)$ , $i = 1, 2, ..., N$
$\space \space \space \space$ b. 拟合残差: $r_{mi}$ 学习一个回归树，得到 $T(x, \theta_m)$
$\space \space \space \space$ c. 更新 $f_m(x) = f_{m-1}(x) + T(x, \theta_m)$

$\space \space$ (3) 得到回归问题的提升树： $f_M(x) = f_m(x) = \sum_{m=1}^M T(x, \theta_m)$

上述的伪代码中，我们对GBDT算法做了以下三个简化：

用残差来表示提升树的负梯度。
假设所有树的贡献权重都相同。
没有把回归树在叶子节点上的拟合信息体现出来。

接下来我们将简化的信息补全，得到下面GBDT算法的伪代码：
$\space \space$ (1) 通过最小化损失最小化初始模型：
$F_0(x) = \underset{\gamma}{\mathrm{argmin}}(\sum_{n=1}^N L(y_i, \gamma))$
$\space \space$ (2) 对 $m = 1,2, ..., M$ :
$\space \space \space \space$ a. 计算负梯度：
$r_{im} = - \Big[ \frac{\partial L(y_i, F(x_i)} {\partial F(x_i)} \Big]_{F(x) = F_{m-1}(x)}, \space \space i = 1,2, ..., n$

$\space \space \space \space$ b. 训练一个回归树去拟合目标值 $r_{im}$ ，树的终端区域为 $R_{jm}(j = 1,2, ..., J_m)$

$\space \space \space \space$ c. 对 $j = 1,2, ..., J_m$ , 计算步长 $\gamma_{jm}$
$\gamma_{jm} = \underset{\gamma}{\mathrm{argmin}} (\sum_{x_i \in R_{jm}} L(y_i, F_{m-1}(x_i) + \gamma))$
$\space \space \space \space$ d. 更新模型：
$F_m(x) = F_{m-1}(x) + \sum_{j=1}^{Jm} \gamma_{jm} \mathbb{I}(x \in R_{jm})$

$\space \space$ (3) 输出 $F_M(x)$
其中每个树的终端区域代表当前树上叶子节点所包含的区域，步长 $\gamma_{jm}$ 为第m棵树上第j个叶子节点的预测结果。

32. GBDT如何用于分类？

GBDT在做分类任务时于回归任务类似，所不同的是损失函数的形式不同。我们以二分类的指数损失函数为例来说明：
我们定义损失函数为：
$L(y, f(x)) = e^{-yf(x)}$
其中 $y_i \in y = \{-1, +1\}$ ，则此时负梯度为：
$r_{im} = - \Big[ \frac{\partial L(y_i, F(x_i))}{\partial F(x_i)} \Big]_{F(x) = F_{m-1}(x)} = y_i e^{-y_if(x_i)}, \space \space i = 1,2, ..., n$
对于各个叶子节点最佳拟合的值为：
$\gamma_{jm} = \underset{\gamma}{\mathrm{argmin}} \Big( \sum_{x_i \in R_{jm}} exp(-y_i (F_{m-1}(x_i) + \gamma) \Big)$

通过GBDT伪代码中步骤b和步骤c类比来理解。

33. GBDT常用的损失函数有哪些？

回归问题：MAE，MSE，RMSE，huber loss（见12.回归问题常用的性能度量指标）

34. 为什么GBDT不适合使用高维稀疏特征？

高维稀疏的ID类特征会使树模型的训练变得极为低效，且容易过拟合。

树模型训练过程是一个贪婪选择特征的过程，要从候选特征集合中选择一个使分裂后收益函数增益最大的特征来分裂。按照高维的ID特征做分裂时，子树数量非常多，计算量会非常大，训练很慢。
同时，按ID分裂得到的子树的泛化性能也比较弱，由于只包含了对应ID值的样本，样本稀疏时也很容易过拟合。

35. GBDT算法的优缺点

优点：

预测阶段的计算速度快，树与树之间可并行计算（注意预测时可并行）
在分布稠密的数据集上，泛化能力和表达能力都很好。
采用决策树作为弱分类器使得GBDT模型具有：

较好的解释性和鲁棒性，
能够自动发现特征间的高阶关系，并且
也不需要对数据进行特殊的预处理（如归一化等）

缺点:

GBDT在高维稀疏的数据集上，表现不佳
训练过程需要串行训练，只能在决策树内部采用一些局部并行的手段提高训练速度。

_2020.11.19

36. 简述XGBoost

略

37. XGBoost 和 GBDT有什么不同？

GBDT是机器学习算法，XGBoost是该算饭的工程实现。
在使用CART作为基础分类器时，XGBoost对代价函数进行二阶taylor展开，可以同时使用一阶和二阶导数。
传统的GBDT采用CART作为基础分类器，XGBoost支持多种类型的基础分类器，比如线性分类器。
传统的GBDT在每轮迭代时使用全部的数据，XGBoost则支持对数据进行采样。
传统的GBDT没有涉及对缺失值进行处理，XGBoost能够自动学习出缺失值的处理策略。
XGBoost还支持并行计算，XGBoost的并行是基于特征计算的并行，将特征列排序后以block的形式存储在内存中，在后面的迭代中重复使用这个结构。

38. XGBoost为什么可以并行训练？

注意xgboost的并行并不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）

xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法枚举所有可能的分割点。当数据无法一次载入内存或者分布式情况下，贪心算法效率就会变得很低。所以xgboost还提出了一种可并行的直方图算法，用于高效地生成候选的分割点。

39. XGBoost防止或拟合的方法？

数据

样本采样 - 在生成每棵树的时候可以对数据进行随机采样。
特征采样 - 在生成每棵树的时候，每棵树生成每一层子节点的时候，以及在每次做节点分裂的时候，选择是否对特征进行采样。

模型

限制树的深度，树的深度越深模型越复杂。
设置叶子节点上样本的最小数量，这个值越小则树的枝叶越多模型越复杂；相反如果这个值越大，则树的枝叶越少，模型越简单。这个值太小会导致过拟合，太大会导致欠拟合。

正则化

L1和L2正则化损失项的权重。
叶子节点数量惩罚项的权重值。

40. XGBoost为什么这么快？

同时采用了损失函数的一阶导数和二阶导数，使得目标函数收敛更快。
在进行节点分类时采用的贪心算法和直方图算法，大大加速了节点分裂的计算过程。
工程优化，使得模型训练时可进行并行计算。

最后编辑于：2021.04.11 22:19:23

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 212,294评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,493评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 157,790评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,595评论 1赞 284
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,718评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,906评论 1赞 290
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,053评论 3赞 410
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,797评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,250评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,570评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,711评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,388评论 4赞 332
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,018评论 3赞 316
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,796评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,023评论 1赞 266
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,461评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,595评论 2赞 350