机器学习面试知识点总结

对面试中机器学习模型常碰到的问题进行总结对比。

模型汇总

Decision Tree
1. ID3
  多叉树：按选择的特征个数分叉;
  信息增益：max（A）：I(D,A) = H(D) - H(D|A);
  无法处理连续特征;
  信息增益倾向于选择特征个数多的特征;
  无法处理缺失值;
  没考虑过拟合;
  不支持缺失值处理;
2. C4.5
  多叉树，连续节点处为二叉树;
  信息增益比;
  剪枝：预剪枝，后剪枝;
  只能用于分类;
  支持缺失值处理;
3. cart
  二叉树，支持缺失值处理;
  分类：gini系数;
  回归：均方差;

Boost（改变样本分布）

Adaboost
- 分类：
  - 指数损失函数 + 加法模型 + 前向分步算法
  - 根据当前的学习误差率更新训练样本的权重
  - 样本权重w->分类器样本误差率e->分类器权重α->样本权重w（和前一个总分类器有关）
- 回归：
  - 平方损失函数，拟合残差
  - 根据划分区域，搜索使得损失函数最小的取值
- 弱学习器不固定；对异常点敏感，样本权重较高；精度高

GBDT

弱学习器固定为cart树;
损失函数不固定;
拟合损失函数的负梯度;
分类：对数似然损失函数（指数损失变为adaboost）;
回归：均方差，绝对损失;
采样是不放回采样;

Q：怎样设置单棵树的停止生长条件？  
A：节点分裂时的最小样本数，最大深度，最多叶子节点数，loss满足约束条件  

Q：评估特征的权重大小  
A：  
1. 通过计算每个特征在训练集下的信息增益，最后计算每个特征信息增益与所有特征信息增益之和的比例为权重值；  
2. 借鉴投票机制。用相同的gbdt参数对w每个特征训练出一个模型，然后在该模型下计算每个特征正确分类的个数，最后计算每个特征正确分类的个数与所有正确分类个数之和的比例为权重值。  

Q：增加样本数量时，训练时长是线性增加吗？  
A：不是。因为生成单棵决策树时，损失函数极小值与样本数量N不是线性相关  ？？？  

Q：增加树的棵树时，训练时长是线性增加吗？  
A：不是。因为每棵树的生成的时间复杂度不一样。   

Q：如何防止过拟合  
A：  
1. 增加样本（data bias or small data的缘故），移除噪声。  
2. 减少特征，保留重要的特征（可以用PCA等对特征进行降维）。  
3. 对样本进行采样（类似bagging）。就是建树的时候，不是把所有的样本都作为输入，而是选择一个子集。  
4. 对特征进行采样。类似样本采样一样,每次建树的时候，只对部分的特征进行切分。  
5. 加正则项，剪枝  

Q：gbdt在训练和预测的时候都用到了步长，这两个步长一样么？  
A：一样。 ？？？  

Q：gbdt中哪些部分可以并行？  
A：  
1. 计算每个样本的负梯度  
2. 分裂挑选最佳特征及其分割点时，对特征计算相应的误差及均值时  
3. 更新每个样本的负梯度时  
4. 最后预测过程中，每个样本将之前的所有树的结果累加的时候

xgboost

图模型
1. HMM
  - 两个假设：
    - 齐次马尔科夫链假设：
      隐藏状态之和之前的一个有关
    - 观测独立假设：
      观测状态之和当前的隐藏状态有关
  - 三个问题：
    - 已知参数，观测序列，求观测序列概率，前向后向算法
    - 已知观测序列，估计模型参数，EM算法
    - 已知参数，观测序列，推测状态序列，维特比算法
2. CRF
  参数估计，极大似然估计
  推测状态序列，维特比算法
  特征函数设计
  
  HMM 生成模型，马尔可夫假设
  CRF 判别模型，没有马尔可夫假设（所以容易更好的采纳上下文信息）

模型对比

LR vs SVM
- 不同
  - LR的损失函数是Cross entropy loss，SVM的损失函数是Hinge loss，自带L2正则
  - LR的解是受数据本身分布影响的，而SVM的解不受数据分布的影响（支持向量）
  - LR的输出具有自然的概率意义，而SVM的输出不具有概率意义
  - SVM依赖数据表达的距离测度，需要对数据normalization，LR则不需要
  - SVM受惩罚系数C的影响较大，实验中需要做Validation，LR则不需要
  - LR适合于大样本学习，SVM适合于小样本学习？？？
  - SVM可以处理大型特征空间，LR对此性能不好？？？
  - SVM 回归
- 相同
  - 线性决策
  - kernel trick，ker-SVM只需要计算支持向量的核函数；而ker-LR需要所有的样本？？？
  - 都会受到outlier的影响
  只有将最优解w表示为xi的线性组合，才能够利用核函数K
  如果样本数量小于特征数，那么就没必要选择非线性核，简单的使用线性核就可以了
  如果样本数量大于特征数目，这时可以使用非线性核，将样本映射到更高维度，一般可以得到更好的结果
  
  https://shomy.top/archives/page/2/
LR vs 决策树
- 决策树可以处理缺失值，LR不可以
- LR线性决策边界，可能欠拟合（但是可以核方法），决策树非线性决策边界，但是对线性拟合效果容易过拟合。（如；x+y=1）（但是可以剪枝，正则，bagging）
- LR有概率值解释，决策树有决策过程直观解释
- LR对数据整体结构的分析优于决策树，而决策树对局部结构的分析优于LR。
- LR对极值比较敏感，容易受极端值的影响
- 决策树容易过拟合；
- GDBT + LR 融合
RF vs GDBT
- 不同
  - 组成随机森林的树可以并行生成，而GBDT是串行生成
  - 随机森林的结果是多数表决表决的，而GBDT则是多棵树累加之和
  - 随机森林对异常值不敏感，而GBDT对异常值比较敏感
  - 随机森林是通过减少模型的方差来提高性能，而GBDT是减少模型的偏差来提高性能的
  - 随机森林不需要进行数据预处理，即特征归一化。GBDT则需要进行特征归一化？？？为什么要归一化
  - 组成随机森林的树可以分类树也可以是回归树，GBDT由cart树组成
- 相同
  - 集成算法
XgBoost vs GBDT

https://zhuanlan.zhihu.com/p/46831267
https://zhuanlan.zhihu.com/p/34679467

模型汇总

Decision Tree

ID3

C4.5

cart

Boost（改变样本分布）

Adaboost

GBDT

xgboost

图模型

HMM

CRF

模型对比

LR vs SVM

LR vs 决策树

RF vs GDBT

XgBoost vs GBDT