2021 年 4 月底，腾讯应用研究岗暑期实习面试题 12 道

问题 1：决策树有多少种，分别的损失函数是什么？

决策树有多少种，分别的损失函数是什么?决策树有三种:分别为 ID3，C4.5，Cart 树

ID3 损失函数︰

C4.5 损失函数 ∶

Cart 树损失函数 ∶

问题 2：决策树的两种剪枝策略分别是什么？

决策树的剪枝基本策略有预剪枝(Pre-Pruning)和后剪枝(Post-Pruning)。

预剪枝核心思想︰

在每一次实际对结点进行进一步划分之前，先采用验证集的数据来验证如果划分是否能提高划分的准确性。如果不能，就把结点标记为叶结点并退出进一步划分﹔如果可以就继续递归生成节点。

后剪枝核心思想︰

后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来泛化性能提升，则将该子树替换为叶结点。

问题 3：信息增益比跟信息增益相比，优势是什么？

以信息增益作为划分训练集的特征选取方案，存在偏向于选取值较多的特征的问题。信息增益比可以解决该问题。

问题 4：介绍 XdeepFM 算法，XdeepFM 跟 DeepFM 算法相比，优势是什么？

上图为 xDeepFM 的总体结构，有三个分支:Linear(稀疏的 01 向量作为输入)、DNN(经过 embedding 的稠密向量作为输入)、CIN（压缩感知层)。

xDeepFM 如果去掉 CIN 分支，就等同于 Wide & Deep。

xDeepFM 将基于 Field 的 vector-wise 思想引入 Cross，并且保留了 Cross 的优势，模型结构也很 elegant，实验效果也提升明显。如果说 DeepFM 只是“Deep & FM”，那么 xDeepFm 就真正做到了”Deep”Factorization Machine。xDeepFM 的时间复杂度会是其工业落地的一个主要性能瓶颈，需要重点优化。

问题 5：对于长度较长的语料，如何使用 Bert 进行训练？

对于长文本，有两种处理方式，截断和切分。

-截断 ∶ 一般来说文本中最重要的信息是开始和结尾，因此文中对于长文本做了截断处理。

head-only:保留前 510 个字符

tail-only:保留后 510 个字符

head+tail:保留前 128 个和后 382 个字符

-切分:将文本分成 k 段，每段的输入和 Bert 常规输入相同，第一个字符是[CLS]表示这段的加权信息。文中使用了 Max-pooling,Average pooling 和 self-attention 结合这些片段的表示。

问题 6：请介绍 k-mean 算法的原理。

1、选取 K 个点做为初始聚集的簇心

2、分别计算每个样本点到 K 个簇核心的距离（这里的距离一般取欧氏距离或余弦距离)，找到离该点最近的簇核心，将它归属到对应的簇

3、所有点都归属到簇之后，M 个点就分为了 K 个簇。之后重新计算每个簇的重心（平均距离中心)，将其定为新的“簇核心”;

4、反复迭代 2-3 步骤，直到达到某个中止条件。

问题 7：逻辑回归怎么分类非线性数据？

问题 8：逻辑回归引入核方法后损失函数如何求导？

用核函数的方法来解决一个 L2 正则化的逻辑回归如下图:

我们直接将 W*表示成 β 的形式带到我们最佳化的问题中，然后就得到一个关于 β 的无条件的最佳化问题。这时我们可以用梯度下降法或随机梯度下降法来得到问题的最优解。

再仔细观察核函数逻辑回归之后会发现它可以是一个关于 β 的线性模型:

其中 kernel 函数既充当了转换的角色有充当了正则化的角色，这种角度同样适用于 SVM 演算法。需要注意的是:SVM 的解 α 大多都是 O，核函数逻辑回归的解 β 大多都不是 0 这样我们会付出计算上的代价。

问题 9：请介绍几种常用的参数更新方法。

梯度下降︰在一个方向上更新和调整模型的参数，来最小化损失函数。

随机梯度下降(Stochastic gradient descent，SGD)对每个训练样本进行参数更新，每次执行都进行一次更新，且执行速度更快。

为了避免 SGD 和标准梯度下降中存在的问题，一个改进方法为小批量梯度下降（Mini BatchGradient Descent)，因为对每个批次中的 n 个训练样本，这种方法只执行一次更新。

使用小批量梯度下降的优点是︰

1)可以减少参数更新的波动，最终得到效果更好和更稳定的收敛。

2)还可以使用最新的深层学习库中通用的矩阵优化方法，使计算小批量数据的梯度更加高效。

3)通常来说，小批量样本的大小范围是从 50 到 256，可以根据实际问题而有所不同。

4)在训练神经网络时，通常都会选择小批量梯度下降算法。

SGD 方法中的高方差振荡使得网络很难稳定收敛，所以有研究者提出了一种称为动量(Momentum)的技术，通过优化相关方向的训练和弱化无关方向的振荡，来加速 SGD 训练。

Nesterov 梯度加速法，通过使网络更新与误差函数的斜率相适应，并依次加速 SGD，也可根据每个参数的重要性来调整和更新对应参数，以执行更大或更小的更新幅度。

AdaDelta 方法是 AdaGrad 的延伸方法，它倾向于解决其学习率衰减的问题。Adadelta 不是累积所有之前的平方梯度，而是将累积之前梯度的窗口限制到某个固定大小 w。

Adam 算法即自适应时刻估计方法(Adaptive Moment Estimation)，能计算每个参数的自适应学习率。这个方法不仅存储了 AdaDelta 先前平方梯度的指数衰减平均值，而且保持了先前梯度 M(t)的指数衰减平均值，这一点与动量类似 Adagrad 方法是通过参数来调整合适的学习率 n，对稀疏参数进行大幅更新和对频繁参数进行小幅更新。

因此, Adagrad 方法非常适合处理稀疏数据。

问题 10：请介绍 Wide&Deep 模型。

1.1 Memorization 和 Generalization

Wide&Deep Mode 就是希望计算机可以像人脑一样，可以同时发挥 memorization 和 generalization 的作用。--Heng-Tze Cheng(Wide&Deep 作者)

1.2 Wide 和 Deep

同样，这两个词也是通篇出现，究竟什么意思你明白了没?其实，,Wide 也是一种特殊的神经网络，他的输入直接和输出相连。属于广义线性模型的范畴。Deep 就是指 Deep Neural Network，这个很好理解。Wide Linear Model 用于 memorization;Deep Neural Network 用于 generalization。左侧是 Wide-only，右侧是 Deep-only，中间是 wide & Deep:

1.3 Cross-product transformation

Wide 中不断提到这样一种变换用来生成组合特征，也必须搞懂才行哦。它的定义如下:

k 表示第 k 个组合特征。i 表示输入 × 的第 i 维特征。C_ki 表示这个第 i 维度特征是否要参与第 k 个组合特征的构造。d 表示输入 × 的维度。那么到底有哪些维度特征要参与构造组合特征那?这个是你之前自己定好的，在公式中没有体现。

饶了一大圈，整这么一个复杂的公式，其实就是我们之前一直在说的 one-hot 之后的组合特征︰仅仅在输入样本 × 中的特征 gender=female 和特征 language=en 同时为 1，新的组合特征 AND(gender=female, language=en)才为 1。所以只要把两个特征的值相乘就可以了。

Cross-product transformation 可以在二值特征中学习到组合特征，并且为模型增加非线性。

问题 11：Xgboost、lightGBM 和 Catboost 之间的异同？

树的特征

三种算法基学习器都是决策树，但是树的特征以及生成的过程仍然有很多不同

CatBoost 使用对称树，其节点可以是镜像的。CatBoost 基于的树模型其实都是完全二叉树。XGBoost 的决策树是 Level-wise 增长。Level-wise 可以同时分裂同一层的叶子，容易进行多线程优化，过拟合风险较小，但是这种分裂方式也有缺陷，Level-wise 对待同一层的叶子不加以区分，带来了很多没必要的开销。实际上很多叶子的分裂增益较低，没有搜索和分裂的必要。

LightGBM 的决策树是 Leaf-wise 增长。每次从当前所有叶子中找到分裂增益最大的一个叶子(通常来说是数据最多的一个)，其缺陷是容易生长出比较深的决策树，产生过拟合，为了解决这个问题，LightGBM 在 Leaf-wise 之上增加了一个最大深度的限制。

对于类别型变量

调用 boost 模型时，当遇到类别型变量， xgboost 需要先处理好，再输入到模型，而 lightgbm 可以指定类别型变量的名称，训练过程中自动处理。

具体来讲，CatBoost 可赋予分类变量指标，进而通过独热最大量得到独热编码形式的结果(独热最大量︰在所有特征上，对小于等于某个给定参数值的不同的数使用独热编码;同时，在 CatBoost 语句中设置“跳过”，CatBoost 就会将所有列当作数值变量处理)。

LighGBM 也可以通过使用特征名称的输入来处理属性数据﹔它没有对数据进行独热编码，因此速度比独热编码快得多。LGBM 使用了一个特殊的算法来确定属性特征的分割值。(注︰需要将分类变量转化为整型变量;此算法不允许将字符串数据传给分类变量参数)和 CatBoost 以及 LGBM 算法不同，XGBoost 本身无法处理分类变量，只接受数值数据，这点和 RF 很相似。实际使用中，在将分类数据传入 XGBoost 之前，必须通过标记编码、均值编码或独热编码等各种编码方式对数据进行处理。

问题 12：情景题：有一个大小为 1G 的文件，文件中每行有一个词，每个词最大为 16kb；现有内存为 1M 的计算机，找出词频前 100 的词。

1.分而治之/hash 映射

顺序读取文件，对于每个词 x，取 hash(x)%5000，然后把该值存到 5000 个小文件(记为 xO,x1,....4999)中。这样每个文件大概是 200k 左右。当然，如果其中有的小文件超过了 1M 大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过 1M。

2.hash_map

统计对每个小文件，采用 trie 树/hash_map 等统计每个文件中出现的词以及相应的频率。

3.堆/归并排序

取出出现频率最大的 100 个词(可以用含 100 个结点的最小堆)后，再把 100 个词及相应的频率存入文件，这样又得到了 5000 个文件。最后就是把这 5000 个文件进行归并（类似于归并排序)的过程了。