好未来暑期算法实习面试题 5 道
文末彩蛋：七月在线干货组最新升级的《名企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而言，其存在三种情况:
- 只能由位置i的单独作为一个item，设为 a，转移的前提是| a的数值范围为[1,9]，转移逻辑为f=fi一 1]。
- 只能由位置i的与前一位置（i-1）共同作为一个item，设为 b，转移的前提是 b的数值范围为[10,26]，转移逻辑为f[间=f处一 2]。
- 位置i既能作为独立item也能与上一位置形成 item，转移逻辑为f[=f[i-1]+f(i-2]。
因此，我们有如下转移方程:
其他细节︰由于题目存在前导零，而前导零属于无效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题》电子书！
