<commit_before>---
layout:     post
title:      "机器学习面试准备"
subtitle:
date:       2017-7-11 11:00:00
author:     "随机漫步的傻瓜"
header-img: "img/post-bg-2015.jpg"
catalog: true
tags:
    - 机器学习
---
1. GBDT+LR? GBDT（Gradient Boost Decision Tree）是一种常用的非线性模型，它基于集成学习中的boosting，每次迭代都在减少残差的梯度方向新建立一颗决策树，迭代多少次就会生成多少颗决策树。GBDT的思想使其具有天然优势可以发现多种有区分性的特征以及特征组合，决策树的路径可以直接作为LR输入特征使用，省去了人工寻找特征、特征组合的步骤。GBDT做离线特征、LR做在线学习。先用已有特征训练GBDT模型，然后利用GBDT模型学习到的树来构造新特征，最后把这些新特征加入原有特征一起训练模型.构造的新特征向量是取值0/1的，向量的每个元素对应于GBDT模型中树的叶子结点。当一个样本点通过某棵树最终落在这棵树的一个叶子结点上，那么在新特征向量中这个叶子结点对应的元素值为1，而这棵树的其他叶子结点对应的元素值为0。新特征向量的长度等于GBDT模型里所有树包含的叶子结点数之和。为什么建树采用GBDT而非RF？RF也是多棵树，但从效果上有实践证明不如GBDT。且GBDT前面的树，特征分裂主要体现对多数样本有区分度的特征；后面的树，主要体现的是经过前N颗树，残差仍然较大的少数样本。优先选用在整体上有区分度的特征，再选用针对少数样本有区分度的特征，思路更加合理，这应该也是用GBDT的原因
2. GBDT和XGBOOST的区别有哪些？
- 传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。
- 传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。
- xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。
- Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（补充：传统GBDT的实现也有学习速率）
- 列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。
- 对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。
- xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
- 可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。
3. gcForest
- 深度神经网络需要花大力气调参，相比之下 gcForest 要容易训练得多。实际上，在几乎完全一样的超参数设置下，gcForest 在处理不同领域（domain）的不同数据时，也能达到极佳的性能。gcForest 的训练过程效率高且可扩展。在我们的实验中，它在一台 PC 上的训练时间和在 GPU 设施上跑的深度神经网络差不多，有鉴于 gcForest 天然适用于并行的部署，其效率高的优势就更为明显。此外，深度神经网络需要大规模的训练数据，而 gcForest 在仅有小规模训练数据的情况下也照常运转。不仅如此，作为一种基于树的方法，gcForest 在理论分析方面也应当比深度神经网络更加容易
- 其核心思想是：利用级联森林（决策树集成）方法去学习生成模型，一定程度上可以弥补DNN的部分劣势！
- 级联森林的构成：级联森林的每一层都是由好多个森林（既有随机森林，又有完全随机森林）组成，而每一个森林又是由好多个决策树（Decision Tree）组成，所以这种组合是集成的集成！其中每一层的随机森林和完全随机森林保证了模型的多样性！
- 每个森林中都包括好多棵决策树，每个决策树都会决策出一个类向量结果（以3类为例，下面也是），然后综合所有的决策树结果，再取均值，生成每个森林的最终决策结果。这样，每个森林都会决策出一个3维类向量，级联森林中的4个森林就都可以决策出一个3维类向量，然后对4*3维类向量取均值，最后取最大值对应的类别，作为最后的预测结果！
- 多粒度扫描是为了增强级联森林，为了对特征做更多的处理的一种技术手段
4. 逻辑回归
- 逻辑回归的并行化最主要的就是对目标函数梯度计算的并行化
![逻辑回归推导](/img/逻辑回归推导.png)
![逻辑回归推导](/img/逻辑回归推导2.png)
5. GBDT
- 用损失函数的负梯度来拟合本轮损失的近似值。通过损失函数的负梯度来拟合，我们找到了一种通用的拟合损失误差的办法，这样无轮是分类问题还是回归问题，我们通过其损失函数的负梯度的拟合，就可以用GBDT来解决我们的分类回归问题。区别仅仅在于损失函数不同导致的负梯度不同而已
- GBDT的分类算法从思想上和GBDT的回归算法没有区别，但是由于样本输出不是连续的值，而是离散的类别，导致我们无法直接从输出类别去拟合类别输出的误差。为了解决这个问题，主要有两个方法，一个是用指数损失函数，此时GBDT退化为Adaboost算法。另一种方法是用类似于逻辑回归的对数似然损失函数的方法。也就是说，我们用的是类别的预测概率值和真实概率值的差来拟合损失
- GBDT主要的优点有：1) 可以灵活处理各种类型的数据，包括连续值和离散值。2) 在相对少的调参时间情况下，预测的准备率也可以比较高。这个是相对SVM来说的。3）使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。
- GBDT的主要缺点有：1)由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。
6. SVM
- 如果样本数量小于特征数，那么就没必要选择非线性核，简单的使用线性核就可以了；也可以先对数据进行降维，然后使用非线性核
- 如果样本数量大于特征数目，这时可以使用非线性核，将样本映射到更高维度，一般可以得到更好的结果；
- 如果样本数目和特征数目相等，该情况可以使用非线性核，原理和第二种一样。
- svm的基本想法就是求解能正确划分训练样本并且其几何间隔最大化的超平面
7. 算法选择的建议：
- 首当其冲应该选择的就是逻辑回归，如果它的效果不怎么样，那么可以将它的结果作为基准来参考，在基础上与其他算法进行比较；
- 然后试试决策树（随机森林）看看是否可以大幅度提升你的模型性能。即便最后你并没有把它当做为最终模型，你也可以使用随机森林来移除噪声变量，做特征选择；
- 如果特征的数量和观测样本特别多，那么当资源和时间充足时（这个前提很重要），使用SVM不失为一种选择
8. K-means
KMeans初始类簇中心点的选取,首先随机选取一个点作为初始点，然后选择距离与该点最远的那个点作为中心点，再选择距离与前两个点最远的店作为第三个中心店，以此类推，直至选取大k个
9. ROC曲线建立
一般默认预测完成之后会有一个概率输出p，这个概率越高，表示它对positive的概率越大。现在假设我们有一个threshold，如果p>threshold，那么该预测结果为positive，否则为negitive，按照这个思路，我们多设置几个threshold,那么我们就可以得到多组positive和negitive的结果了，也就是我们可以得到多组FPR和TPR值了。将这些(FPR,TPR)点投射到坐标上再用线连接起来就是ROC曲线了。当threshold取1和0时，分别得到的就是(0,0)和(1,1)这两个点。（threshold=1，预测的样本全部为负样本，threshold=0，预测的样本全部为正样本
10. 为什么要使用ROC和AUC
因为当测试集中的正负样本发生变化时(类别不均衡问题)，ROC曲线能基本保持不变，但是precision和recall可能就会有较大的波动。
11. 对于神经网络和SVM，在数据输入前进行标准化可以非常有效的提升收敛速度和效果。数据归一化后，最优解的寻优过程明显会变得平缓，更容易正确的收敛到最优解
12. 离散化后的特征对异常数据有很强的鲁棒性；引入非线性，提升模型表达能力，加大拟合；离散化后可以进行交叉特征，进一步引入非线性；特征离散化后，起到了简化逻辑回归模型的作用，降低了模型过拟合的风险
13. 广告LR中，基本特征可以认为是用于全局建模，组合特征更加精细，是个性化建模，因为在这种大规模离散LR中，单对全局建模会对部分用户有偏，对每一用户建模又数据不足易过拟合同时带来模型数量爆炸，所以基本特征+组合特征兼顾了全局和个性化
14. GBDT与Adaboost的区别与联系是什么？
- 和AdaBoost一样，Gradient Boosting也是重复选择一个表现一般的模型并且每次基于先前模型的表现进行调整。不同的是，AdaBoost是通过提升错分数据点的权重来定位模型的不足而Gradient Boosting是通过算梯度（gradient）来定位模型的不足。因此相比AdaBoost, Gradient Boosting可以使用更多种类的目标函数
- 最主要的区别在于两者如何识别模型的问题。AdaBoost用错分数据点来识别问题，通过调整错分数据点的权重来改进模型。Gradient Boosting通过负梯度来识别问题，通过计算负梯度来改进模型。
<commit_msg>机器学习面试<commit_after>---
layout:     post
title:      "机器学习面试准备"
subtitle:
date:       2017-7-11 11:00:00
author:     "随机漫步的傻瓜"
header-img: "img/post-bg-2015.jpg"
catalog: true
tags:
    - 机器学习
---
1. GBDT+LR? GBDT（Gradient Boost Decision Tree）是一种常用的非线性模型，它基于集成学习中的boosting，每次迭代都在减少残差的梯度方向新建立一颗决策树，迭代多少次就会生成多少颗决策树。GBDT的思想使其具有天然优势可以发现多种有区分性的特征以及特征组合，决策树的路径可以直接作为LR输入特征使用，省去了人工寻找特征、特征组合的步骤。GBDT做离线特征、LR做在线学习。先用已有特征训练GBDT模型，然后利用GBDT模型学习到的树来构造新特征，最后把这些新特征加入原有特征一起训练模型.构造的新特征向量是取值0/1的，向量的每个元素对应于GBDT模型中树的叶子结点。当一个样本点通过某棵树最终落在这棵树的一个叶子结点上，那么在新特征向量中这个叶子结点对应的元素值为1，而这棵树的其他叶子结点对应的元素值为0。新特征向量的长度等于GBDT模型里所有树包含的叶子结点数之和。为什么建树采用GBDT而非RF？RF也是多棵树，但从效果上有实践证明不如GBDT。且GBDT前面的树，特征分裂主要体现对多数样本有区分度的特征；后面的树，主要体现的是经过前N颗树，残差仍然较大的少数样本。优先选用在整体上有区分度的特征，再选用针对少数样本有区分度的特征，思路更加合理，这应该也是用GBDT的原因
2. GBDT和XGBOOST的区别有哪些？
- 传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。
- 传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。
- xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。
- Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（补充：传统GBDT的实现也有学习速率）
- 列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。
- 对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。
- xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
- 可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。
3. gcForest
- 深度神经网络需要花大力气调参，相比之下 gcForest 要容易训练得多。实际上，在几乎完全一样的超参数设置下，gcForest 在处理不同领域（domain）的不同数据时，也能达到极佳的性能。gcForest 的训练过程效率高且可扩展。在我们的实验中，它在一台 PC 上的训练时间和在 GPU 设施上跑的深度神经网络差不多，有鉴于 gcForest 天然适用于并行的部署，其效率高的优势就更为明显。此外，深度神经网络需要大规模的训练数据，而 gcForest 在仅有小规模训练数据的情况下也照常运转。不仅如此，作为一种基于树的方法，gcForest 在理论分析方面也应当比深度神经网络更加容易
- 其核心思想是：利用级联森林（决策树集成）方法去学习生成模型，一定程度上可以弥补DNN的部分劣势！
- 级联森林的构成：级联森林的每一层都是由好多个森林（既有随机森林，又有完全随机森林）组成，而每一个森林又是由好多个决策树（Decision Tree）组成，所以这种组合是集成的集成！其中每一层的随机森林和完全随机森林保证了模型的多样性！
- 每个森林中都包括好多棵决策树，每个决策树都会决策出一个类向量结果（以3类为例，下面也是），然后综合所有的决策树结果，再取均值，生成每个森林的最终决策结果。这样，每个森林都会决策出一个3维类向量，级联森林中的4个森林就都可以决策出一个3维类向量，然后对4*3维类向量取均值，最后取最大值对应的类别，作为最后的预测结果！
- 多粒度扫描是为了增强级联森林，为了对特征做更多的处理的一种技术手段
4. 逻辑回归
- 逻辑回归的并行化最主要的就是对目标函数梯度计算的并行化
![逻辑回归推导](/img/逻辑回归推导.png)
![逻辑回归推导](/img/逻辑回归推导2.png)
5. GBDT
- 用损失函数的负梯度来拟合本轮损失的近似值。通过损失函数的负梯度来拟合，我们找到了一种通用的拟合损失误差的办法，这样无轮是分类问题还是回归问题，我们通过其损失函数的负梯度的拟合，就可以用GBDT来解决我们的分类回归问题。区别仅仅在于损失函数不同导致的负梯度不同而已
- GBDT的分类算法从思想上和GBDT的回归算法没有区别，但是由于样本输出不是连续的值，而是离散的类别，导致我们无法直接从输出类别去拟合类别输出的误差。为了解决这个问题，主要有两个方法，一个是用指数损失函数，此时GBDT退化为Adaboost算法。另一种方法是用类似于逻辑回归的对数似然损失函数的方法。也就是说，我们用的是类别的预测概率值和真实概率值的差来拟合损失
- GBDT主要的优点有：1) 可以灵活处理各种类型的数据，包括连续值和离散值。2) 在相对少的调参时间情况下，预测的准备率也可以比较高。这个是相对SVM来说的。3）使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。
- GBDT的主要缺点有：1)由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。
6. SVM
- 如果样本数量小于特征数，那么就没必要选择非线性核，简单的使用线性核就可以了；也可以先对数据进行降维，然后使用非线性核
- 如果样本数量大于特征数目，这时可以使用非线性核，将样本映射到更高维度，一般可以得到更好的结果；
- 如果样本数目和特征数目相等，该情况可以使用非线性核，原理和第二种一样。
- svm的基本想法就是求解能正确划分训练样本并且其几何间隔最大化的超平面
7. 算法选择的建议：
- 首当其冲应该选择的就是逻辑回归，如果它的效果不怎么样，那么可以将它的结果作为基准来参考，在基础上与其他算法进行比较；
- 然后试试决策树（随机森林）看看是否可以大幅度提升你的模型性能。即便最后你并没有把它当做为最终模型，你也可以使用随机森林来移除噪声变量，做特征选择；
- 如果特征的数量和观测样本特别多，那么当资源和时间充足时（这个前提很重要），使用SVM不失为一种选择
8. KMeans初始类簇中心点的选取,首先随机选取一个点作为初始点，然后选择距离与该点最远的那个点作为中心点，再选择距离与前两个点最远的点作为第三个中心点，以此类推，直至选取大k个
9. ROC曲线建立
一般默认预测完成之后会有一个概率输出p，这个概率越高，表示它对positive的概率越大。现在假设我们有一个threshold，如果p>threshold，那么该预测结果为positive，否则为negitive，按照这个思路，我们多设置几个threshold,那么我们就可以得到多组positive和negitive的结果了，也就是我们可以得到多组FPR和TPR值了。将这些(FPR,TPR)点投射到坐标上再用线连接起来就是ROC曲线了。当threshold取1和0时，分别得到的就是(0,0)和(1,1)这两个点。（threshold=1，预测的样本全部为负样本，threshold=0，预测的样本全部为正样本
10. 为什么要使用ROC和AUC
因为当测试集中的正负样本发生变化时(类别不均衡问题)，ROC曲线能基本保持不变，但是precision和recall可能就会有较大的波动。
11. 对于神经网络和SVM，在数据输入前进行标准化可以非常有效的提升收敛速度和效果。数据归一化后，最优解的寻优过程明显会变得平缓，更容易正确的收敛到最优解
12. 离散化后的特征对异常数据有很强的鲁棒性；引入非线性，提升模型表达能力，加大拟合；离散化后可以进行交叉特征，进一步引入非线性；特征离散化后，起到了简化逻辑回归模型的作用，降低了模型过拟合的风险
13. 广告LR中，基本特征可以认为是用于全局建模，组合特征更加精细，是个性化建模，因为在这种大规模离散LR中，单对全局建模会对部分用户有偏，对每一用户建模又数据不足易过拟合同时带来模型数量爆炸，所以基本特征+组合特征兼顾了全局和个性化
14. GBDT与Adaboost的区别与联系是什么？
- 和AdaBoost一样，Gradient Boosting也是重复选择一个表现一般的模型并且每次基于先前模型的表现进行调整。不同的是，AdaBoost是通过提升错分数据点的权重来定位模型的不足而Gradient Boosting是通过算梯度（gradient）来定位模型的不足。因此相比AdaBoost, Gradient Boosting可以使用更多种类的目标函数
- 最主要的区别在于两者如何识别模型的问题。AdaBoost用错分数据点来识别问题，通过调整错分数据点的权重来改进模型。Gradient Boosting通过负梯度来识别问题，通过计算负梯度来改进模型。

{'fraction_non_alphanumeric': 0.08289768483943241, 'fraction_numerical': 0.01344286781179985, 'mean_word_length': 20.065168539325843, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6097965', 'n_tokens_mistral': 8355, 'n_tokens_neox': 9932, 'n_words': 209}