秋招常见面试问题总结

作者: 文哥的学习日记 | 来源:发表于2018-10-07 16:57 被阅读391次

1、常见的机器学习优化器

1.1 gradient descent

1.1.1 全量梯度下降(Batch gradient descent)
每次使用全量的训练集样本来更新模型参数，即θ=θ−η⋅∇_θJ(θ)。
优点:每次更新都会朝着正确的方向进行，最后能够保证收敛于极值点(凸函数收敛于全局极值点，非凸函数可能会收敛于局部极值点)，
缺点:在于每次学习时间过长，并且如果训练集很大以至于需要消耗大量的内存，并且全量梯度下降不能进行在线模型参数更新。

1.1.2 随机梯度下降(Stochastic gradient descent)
随机梯度下降算法每次从训练集中随机选择一个样本来进行学习，即:θ=θ−η⋅∇_θJ(θ;x_i;y_i)
优点：随机梯度下降算法每次只随机选择一个样本来更新模型参数，因此每次的学习是非常快速的，并且可以进行在线更新。
缺点：每次更新可能并不会按照正确的方向进行，因此可以带来优化波动，不过从另一个方面来看，随机梯度下降所带来的波动有个好处就是，对于类似盆地区域（即很多局部极小值点）那么这个波动的特点可能会使得优化的方向从当前的局部极小值点跳到另一个更好的局部极小值点，这样便可能对于非凸函数，最终收敛于一个较好的局部极值点，甚至全局极值点。由于波动，因此会使得迭代次数增多，即收敛速度变慢。

1.1.3 小批量梯度下降(Mini-batch gradient descent)
Mini-batch梯度下降综合了batch梯度下降与stochastic梯度下降，在每次更新速度与更新次数中间取得一个平衡，其每次更新从训练集中随机选择m,m<<n
个样本进行学习，即：
θ=θ−η⋅∇_θJ(θ;x_i:i+m;y_i:i+m)
优点：相对于随机梯度下降，Mini-batch梯度下降降低了收敛波动性，即降低了参数更新的方差，使得更新更加稳定。相对于全量梯度下降，其提高了每次学习的速度。并且其不用担心内存瓶颈从而可以利用矩阵运算进行高效计算。

1.1.4 梯度下降法的问题和挑战
学习率设定：学习率的设定带来的挑战有三方面。首先，选择一个合理的学习率很难，如果学习速率过小，则会导致收敛速度很慢。如果学习速率过大，那么其会阻碍收敛，即在极值点附近会振荡。其次，学习速率调整很难，我们一般使用某种事先设定的策略或者在每次迭代中衰减一个较小的阈值。无论哪种调整方法，都需要事先进行固定设置，这边便无法自适应每次学习的数据集特点。最后，模型所有的参数每次更新都是使用相同的学习速率。如果数据特征是稀疏的或者每个特征有着不同的取值统计特征与空间，那么便不能在每次更新中每个参数使用相同的学习速率，那些很少出现的特征应该使用一个相对较大的学习速率。

局部极小和鞍点：对于非凸目标函数，容易陷入那些次优的局部极值点或者鞍点中。

1.2 Momentum

如果在峡谷地区(某些方向较另一些方向上陡峭得多，常见于局部极值点)，SGD会在这些地方附近振荡，从而导致收敛速度慢。这种情况下，动量(Momentum)便可以解决。动量在参数更新项中加上一次更新量(即动量项,相当于指数加权平均),即：
ν_t=γν_t−1+η ∇_θJ(θ)
θ=θ−ν_t

其作用如下图所示：

没有动量

有动量

优点：对方向一致的参数能够加速学习，对梯度改变方向的参数能够减少其更新，因此就是momentum能够在相关方向上加速学习，抑制振荡，从而加速收敛。
缺点：比较难学习一个较好的学习率。

1.3 Adagrad

在前面介绍的算法中，每个模型参数θ_i使用相同的学习速率η，而Adagrad在每一个更新步骤中对于每一个模型参数θ_i使用不同的学习速率η_i。其更新方程为：

其中，G_t∈R^d×d是一个对角矩阵，其中第i行的对角元素e_ii为过去到当前第i个参数θ_i的梯度的平方和，epsilon是一个平滑参数，为了使得分母不为0。
进一步，将所有G_t,ii,g_t,i的元素写成向量G_t,g_t,这样便可以使用向量点乘操作：

优点：在于它能够为每个参数自适应不同的学习速率，而一般的人工都是设定为0.01。
缺点：在于需要计算参数梯度序列平方和，并且学习速率趋势是不断衰减最终达到一个非常小的值。

1.4 RMSprop

为了降低Adagrad中学习速率衰减过快的问题，RMSprop使用指数加权平均来代替历史梯度的平方和：

Rmsprop的的效果如下图所示，对梯度较大的方向减小其学习速率，相反的，在梯度较小的方向上增加其学习速率。

优点：RMSprop改进了Adagrad学习速率衰减过快的问题，同时其适用于处理非平稳。
缺点：依然依赖一个全局学习率。

1.5 Adam

Adam 算法结合了 Momentum 和 RMSprop 梯度下降法，并且是一种极其常
用的学习算法，被证明能有效适用于不同神经网络，适用于广泛的结构。其计算方式如下：

上式中使用的是经过偏差修正后的指数加权平均数：

2、常见的过拟合解决方法

2.1 L1和L2正则化

L1和L2正则化来避免过拟合是大家都知道的事情，而且我们都知道L1正则化可以得到稀疏解，L2正则化可以得到平滑解，这是为什么呢？有几种解释吧，可以参考文献8（https://blog.csdn.net/f156207495/article/details/82794151）。主要有几个方面：
1)直观的从图像上观察结论
2)通过对梯度的求解进行解释
3)通过L1正则和L2正则假设的参数先验上进行解释。

2.2 数据增强

通俗得讲，数据增强即需要得到更多的符合要求的数据，即和已有的数据是独立同分布的，或者近似独立同分布的。一般有以下方法：
1)从数据源头采集更多数据
2)复制原有数据并加上随机噪声
3)重采样
4)根据当前数据集估计数据分布参数，使用该分布产生更多数据等

2.3 Early stopping

Early stopping便是一种迭代次数截断的方法来防止过拟合的方法，即在模型对训练数据集迭代收敛之前停止迭代来防止过拟合。

Early stopping可以得到与L2类似的参数平滑效果，可以通过定性和定量两个方面进行分析，具体参考文献10:http://www.friskit.me/2017/03/27/l2-equals-to-stop-early/

2.4 dropout

dropout是指在深度学习网络的训练过程中，对于神经网络单元，按照一定的概率将其暂时从网络中丢弃。dropout为什么能防止过拟合，可以通过以下几个方面来解释：

它强迫一个神经单元，和随机挑选出来的其他神经单元共同工作，达到好的效果。消除减弱了神经元节点间的联合适应性，增强了泛化能力。
类似于bagging的集成效果
对于每一个dropout后的网络，进行训练时，相当于做了Data Augmentation，因为，总可以找到一个样本，使得在原始的网络上也能达到dropout单元后的效果。比如，对于某一层，dropout一些单元后，形成的结果是(1.5,0,2.5,0,1,2,0)，其中0是被drop的单元，那么总能找到一个样本，使得结果也是如此。这样，每一次dropout其实都相当于增加了样本。

2.5 交叉验证

交叉验证的基本思想就是将原始数据（dataset）进行分组，一部分做为训练集来训练模型，另一部分做为测试集来评价模型。我们常用的交叉验证方法有简单交叉验证、S折交叉验证和留一交叉验证。

2.6 决策树剪枝

在决策树学习中将已生成的树进行简化的过程称为剪枝。又分为前剪枝和后剪枝，这里我们就不细细介绍了。

3、CTR预估 & 推荐系统

3.1 FM的原理及化简

FM的计算公式如下：

化简过程如下：

求导结果如下：

3.2 FFM的原理

在FFM中，每一维特征 x_i，针对其它特征的每一种field f_j，都会学习一个隐向量 v_{i,f_j}。因此，隐向量不仅与特征相关，也与field相关。

假设样本的 n个特征属于f个field，那么FFM的二次项有 nf个隐向量。而在FM模型中，每一维特征的隐向量只有一个。FM可以看作FFM的特例，是把所有特征都归属到一个field时的FFM模型。根据FFM的field敏感特性，可以导出其模型方程。

可以看到，如果隐向量的长度为 k，那么FFM的二次参数有 nfk 个，远多于FM模型的 nk个。此外，由于隐向量与field相关，FFM二次项并不能够化简，其预测复杂度是 O(kn²)。

FFM将问题定义为分类问题，使用的是logistic loss，同时加入了正则项(这里是分类类别为-1和1时候的log loss)

3.3 wide & deep的原理

wide & deep的结构如下：

Wide Part
Wide Part其实是一个广义的线性模型，使用特征包括
raw input(原始特征)和cross-product transformation(组合特征)

Deep Part

Deep Part通过学习一个低纬度的dense representation（也叫做embedding vector）对于每一个query和item，来泛化给你推荐一些字符上看起来不那么相关，但是你可能也是需要的。比如说：你想要炸鸡，Embedding Space中，炸鸡和汉堡很接近，所以也会给你推荐汉堡。

Embedding vectors被随机初始化，并根据最终的loss来反向训练更新。这些低维度的dense embedding vectors被作为第一个隐藏层的输入。隐藏层的激活函数通常使用ReLU。

模型的训练

模型的最终输出为：

通过联合训练方式进行训练。之前面试问到两个部分是否可以用不同的优化器，论文中给出的是：Wide组件是用FTRL（Follow-the-regularized-leader） + L1正则化学习。Deep组件是用AdaGrad来学习。

3.4 DeepFM的原理

先来看一下DeepFM的模型结构：

DeepFM包含两部分：神经网络部分与因子分解机部分，分别负责低阶特征的提取和高阶特征的提取。这两部分共享同样的输入。DeepFM的预测结果可以写为：

FM部分

FM部分的详细结构如下：

FM的输出公式为：

深度部分

深度部分是一个前馈神经网络。与图像或者语音这类输入不同，图像语音的输入一般是连续而且密集的，然而用于CTR的输入一般是及其稀疏的。因此需要重新设计网络结构。具体实现中为，在第一层隐含层之前，引入一个嵌入层来完成将输入向量压缩到低维稠密向量。

嵌入层(embedding layer)的结构如上图所示。当前网络结构有两个有趣的特性，1）尽管不同field的输入长度不同，但是embedding之后向量的长度均为K。2)在FM里得到的隐变量Vik现在作为了嵌入层网络的权重。

4、Batch Normalization

4.1 为什么要做BN

我们首先来思考一个问题，为什么神经网络需要对输入做标准化处理？原因在于神经网络本身就是为了学习数据的分布，如果训练集和测试集的分布不同，那么导致学习的神经网络泛化性能大大降低。同时，我们在使用mini-batch对神经网络进行训练时，不同的batch的数据的分布也有可能不同，那么网络就要在每次迭代都去学习适应不同的分布，这样将会大大降低网络的训练速度。因此我们需要对输入数据进行标准化处理。

对于深度网络的训练是一个复杂的过程，只要网络的前面几层发生微小的改变，那么后面几层就会被累积放大下去。一旦网络某一层的输入数据的分布发生改变，那么这一层网络就需要去适应学习这个新的数据分布，所以如果训练过程中，训练数据的分布一直在发生变化，那么将会影响网络的训练速度。

我们知道网络一旦train起来，那么参数就要发生更新，除了输入层的数据外(因为输入层数据，我们已经人为的为每个样本归一化)，后面网络每一层的输入数据分布是一直在发生变化的，因为在训练的时候，前面层训练参数的更新将导致后面层输入数据分布的变化。我们把网络中间层在训练过程中，数据分布的改变称之为：Internal Covariate Shift。为了解决Internal Covariate Shift，便有了Batch Normalization的诞生。

4.2 如何做BN(训练和预测)

训练阶段

训练阶段对每一层，BN的计算过程如下：

可以看到，在BN的计算过程中，不仅仅有标准化的操作，还有最后一步，被称为变换重构。为什么要增加这一步呢？其实如果是仅仅使用上面的归一化公式，对网络某一层A的输出数据做归一化，然后送入网络下一层B，这样是会影响到本层网络A所学习到的特征的。打个比方，比如我网络中间某一层学习到特征数据本身就分布在S型激活函数的两侧，你强制把它给我归一化处理、标准差也限制在了1，把数据变换成分布于s函数的中间部分，这样就相当于我这一层网络所学习到的特征分布被你搞坏了。于是我们增加了变换重构，保留了网络所学习到的特征。

预测阶段

一个网络一旦训练完了，就没有了min-batch这个概念了。测试阶段我们一般只输入一个测试样本，看看结果而已。因此测试样本，前向传导的时候，上面的均值u、标准差σ 要哪里来？其实网络一旦训练完毕，参数都是固定的，这个时候即使是每批训练样本进入网络，那么BN层计算的均值u、和标准差都是固定不变的。
因此在预测阶段，对于均值来说直接计算所有训练batch u值的平均值；然后对于标准偏差采用训练阶段每个batch σB的无偏估计，过程如下：

5、集成学习

5.1 Bagging

Bagging即套袋法，其算法过程如下：
1、从原始样本集中抽取训练集.每轮从原始样本集中使用Bootstraping的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）.共进行k轮抽取，得到k个训练集.（k个训练集相互独立）
2、每次使用一个训练集得到一个模型，k个训练集共得到k个模型.（注：根据具体问题采用不同的分类或回归方法，如决策树、神经网络等）
3、对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果.

5.2 Boosting

Boosting是一族可将弱学习器提升为强学习器的算法。关于Boosting的两个核心问题：
1、在每一轮如何改变训练数据的权值或概率分布？
通过提高那些在前一轮被弱分类器分错样例的权值，减小前一轮分对样本的权值，而误分的样本在后续受到更多的关注.
2、通过什么方式来组合弱分类器？
通过加法模型将弱分类器进行线性组合，比如AdaBoost通过加权多数表决的方式，即增大错误率小的分类器的权值，同时减小错误率较大的分类器的权值。而提升树通过拟合残差的方式逐步减小残差，将每一步生成的模型叠加得到最终模型。

5.3 Bagging和Boosting的方差-偏差分析

我们都知道，Bagging主要降低的是模型的方差，而Boosting主要减小的是模型的偏差，这是为什么呢？

这里我们主要引用参考文献13中的解释：

5.4 Stacking

stacking 就是当用初始训练数据学习出若干个基学习器后，将这几个学习器的预测结果作为新的训练集，来学习一个新的学习器。

在stacking的模型训练阶段，二级模型的训练集是使用一级模型产生的，如果直接使用一级模型对初始的训练集样本进行预测来产生二级模型的训练集，这样会有极大的过拟合的风险，因此一般是用训练一级模型未使用的样本来产生二级模型的训练集，交叉验证方法是比较常用的方法。

Stacking的二级模型的训练样本的shape应该是训练集长度 * 基分类器个数，因此对于每个一级模型来说的，通过下面的图示来产生部分该模型对应的部分，最后进行横向拼接：

而对于二级模型的测试集来说，由于每次交叉验证的过程中都要进行一次预测，假设我们是5折交叉验证，那么对于每个一级模型来说，得到的shape是测试集行数 * 交叉验证折数，此时的做法是，对axis=1方向取平均值，以得到测试集行数 * 1 的测试数据，最后将每个一级模型的结果进行横向拼接，得到二级模型的测试样本的shape是测试集行数 * 基分类器个数，可以跟训练集保持一致：

6、梯度消失、爆炸及解决方案

想必大家对梯度消失和梯度爆炸的概念都很了解了，这里我们只谈一谈如何避免梯度消失和爆炸。

6.1 预训练加微调

该方案的基本思想是每次训练一层隐节点，训练时将上一层隐节点的输出作为输入，而本层隐节点的输出作为下一层隐节点的输入，此过程就是逐层“预训练”（pre-training）；在预训练完成后，再对整个网络进行“微调”（fine-tunning）。此思想相当于是先寻找局部最优，然后整合起来寻找全局最优，此方法有一定的好处，但是目前应用的不是很多了。

6.2 梯度裁切

梯度剪切这个方案主要是针对梯度爆炸提出的，其思想是设置一个梯度剪切阈值，然后更新梯度的时候，如果梯度超过这个阈值，那么就将其强制限制在这个范围之内。这可以防止梯度爆炸。

6.3 正则化

正则化在一定程度上也可以避免梯度爆炸的问题，比较常见的是l1
正则和l2正则。

6.4 relu、leakrelu、elu等激活函数

relu
relu的数学表达式为f(x) = max(0, x)，图像如下：

我们可以很容易看出，relu函数的导数在正数部分是恒等于1的，因此在深层网络中使用relu激活函数就不会导致梯度消失和爆炸的问题。但由于负数部分恒为0，会导致一些神经元无法激活。

leak relu

leakrelu就是为了解决relu的0区间带来的影响，其数学表达为：f(x)=max(k∗x,x)。其中k是leak系数，一般选择0.01或者0.02，或者通过学习而来，其图像如下：

elu

elu激活函数也是为了解决relu的0区间带来的影响，其表达式为：

其图像如下：

6.5 batch normalization

有关batch normalization内容，可以参考本文的第四部分。多说一句，我们可以理解BN将输出从饱和区拉倒了非饱和区。尤其在使用sigmoid激活函数或者tanh激活函数时，这个作用更加明显。

6.6 残差结构

在一定深度下，深层网络的训练误差大于浅层网络的训练误差，我们称之为网络退化问题。而残差结构有效的解决了这个问题，使得深层网络的训练效果好于浅层网络。

ResNet中的残差块如下图所示：

我们可以看出此时将A网络的输出误差应该与B网络相同（暂时不考虑网络中的维度大小的细节），因为残差块的输出为F(x) + x,如果将网络中的参数置为0，则F(x)=0,因此得到的输出为0+x=x。因此使用ResNet结构搭建的深度网络至少与浅层网络具有相同的拟合能力，不会出现之前的网络退化问题。

6.7 LSTM

LSTM主要解决的是循环神经网络中的梯度消失问题，传统RNN中为什么会出现梯度消失或爆炸，以及LSTM是如何解决的，参考文献14 和 15.

RNN梯度消失和爆炸的原因：https://zhuanlan.zhihu.com/p/28687529
LSTM如何解决梯度消失问题：https://zhuanlan.zhihu.com/p/28749444

另外还有一个常见的问题就是，LSTM和RNN中为什么选择tanh作为激活函数，而非relu。可以参考文献16。

参考文献