文末彩蛋：七月在线干货组最新升级的《名企 AI 面试 100 题》免费送！

问题 1 ：讲一下 xgb 与 lgb 的特点与区别

xgboost 采用的是 level-wise 的分裂策略，而 lightGBM 采用了 leaf-wise 的策略，区别是 xgboost 对每一层所有节点做无差别分裂，可能有些节点的增益非常小，对结果影响不大，但是 xgboost 也进行了分裂，带来了不必要的开销。leaft-wise 的做法是在当前所有叶子节点中选择分裂收益最大的节点进行分裂，如此递归进行，很明显 leaf-wise 这种做法容易过拟合，因为容易陷入比较高的深度中，因此需要对最大深度做限制，从而避免过拟合。

lightgbm 使用了基于 histogram 的决策树算法，这一点不同与 xgboost 中的 exact 算法，histogram 算法在内存和计算代价上都有不小优势。

内存：直方图算法的内存消耗为(#data* #features * 1Bytes)(因为对特征分桶后只需保存特征离散化之后的值)，而 xgboost 的 exact 算法内存消耗为：(2 * #data * #features* 4Bytes)，因为 xgboost 既要保存原始 feature 的值，也要保存这个值的顺序索引，这些值需要 32 位的浮点数来保存。

计算：预排序算法在选择好分裂特征计算分裂收益时需要遍历所有样本的特征值，时间为(#data),而直方图算法只需要遍历桶就行了，时间为(#bin)

问题 2 ：讲一下 xgb 的二阶泰勒展开对于 GBDT 有什么优势

xgboost 是在 MSE 基础上推导出来的，在 MSE 的情况下，xgboost 的目标函数展开就是一阶项 + 二阶项的形式，而其他类似 log loss 这样的目标函数不能表示成这种形式。为了后续推导的统一，所以将目标函数进行二阶泰勒展开，就可以直接自定义损失函数了，只要损失函数是二阶可导的即可，增强了模型的扩展性。

二阶信息能够让梯度收敛的更快。一阶信息描述梯度变化方向，二阶信息可以描述梯度变化方向是如何变化的。

问题 3 ：算法题：字母 a-z 对应数字 1-26，给定一个数字序列， 求所有可能的解码总数，例如 1261 对应解码为 1 2 6 1 ， 12 6 1， 1 26 1 总共为 3 种方式

这其实是一道字符串类的动态规划题，不难发现对于字符串 s 的某个位置 i 而言，我们只关心「位置 i 自己能否形成独立 item」和「位置 i 能够与上一位置（i-1）能否形成 item」，而不关心 i-1 之前的位置。

有了以上分析，我们可以从前往后处理字符串 s，使用一个数组记录以字符串 s 的每一位作为结尾的解码方案数。即定义间为考虑前 i 个字符的解码方案数。对于字符串 s 的任意位置 i 而言，其存在三种情况：

1. 只能由位置 i 的单独作为一个 item，设为 a，转移的前提是 | a 的数值范围为[1,9]，转移逻辑为 f=fi 一 1]。
2. 只能由位置 i 的与前一位置（i-1）共同作为一个 item，设为 b，转移的前提是 b 的数值范围为[10,26]，转移逻辑为 f[间 =f 处一 2]。
3. 位置 i 既能作为独立 item 也能与上一位置形成 item，转移逻辑为 f[=f[i-1]+f(i-2]。

因此，我们有如下转移方程：

• 本文地址：好未来暑期算法实习面试题 5 道
• 本文版权归作者和AIQ共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出

其他细节︰由于题目存在前导零，而前导零属于无效 item。可以进行特判，但个人习惯往字符串头部追加空格作为哨兵，追加空格既可以避免讨论前导零，也能使下标从 1 开始，简化 f[i-1]等负数下标的判断。

代码如下：

问题 4 ：介绍 xgboost 和 gbdt 的区别

传统的 GBDT 以 CART 树作为基学习器，XGBoost 还支持线性分类器，这个时候 XGBoost 相当于 L1 和 L2 正则化的逻辑斯蒂回归(分类)或者线性回归(回归);

传统的 GBDT 在优化的时候只用到一阶导数信息，XGBoost 则对代价函数进行了二阶泰勒展开，得到一阶和二阶导数﹔

XGBoost 在代价函数中加入了正则项，用于控制模型的复杂度。从权衡方差偏差来看，它降低了模型的方差，使学习出来的模型更加简单，放置过拟合，这也是 XGBoost 优于传统 GBDT 的一个特性;

shrinkage (缩减)，相当于学习速率(XGBoost 中的 eta)。XGBoost 在进行完一次迭代时，会将叶子节点的权值乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。(GBDT 也有学习速率);

列抽样：XGBoost 借鉴了随机森林的做法，支持列抽样，不仅防止过拟合，还能减少计算;对缺失值的处理：对于特征的值有缺失的样本，XGBoost 还可以自动学习出它的分裂方向;

XGBoost 工具支持并行。Boosting 不是一种串行的结构吗？怎么并行的？注意 XGBoost 的并行不是 tree 粒度的并行，XGBoost 也是一次迭代完才能进行下一次迭代的（第 t 次迭代的代价函数里包含了前面 t-1 次迭代的预测值)。XGBoost 的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点)，XGBoost 在训练之前，预先对数据进行了排序，然后保存为 block 结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个 block 结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

问题 5 ：算法题：给定一个 int 数字，将其转换为中文描述，例如，1010 -> 一千零一十

关注微信公众号“七月在线实验室”，免费领取最新升级版《名企 AI 面试 100 题》电子书！