夏侯兴霸-SHEIN算法一面凉经——解答

从今天起，豆芽有空也尽己所能，帮助一下大家。

面经来源：https://www.nowcoder.com/discuss/690820?source_id=discuss_experience_nctrack&channel=-1

1. 深搜和广搜怎么做的

DFS（Deep First Search）深度优先搜索。

BFS（Breath First Search）广度优先搜索。

深度优先搜索的步骤分为

（1）递归下去

（2）回溯上来。

顾名思义，深度优先，则是以深度为准则，先一条路走到底，直到达到目标。这里称之为递归下去。

否则既没有达到目标又无路可走了，那么则退回到上一步的状态，走其他路。这便是回溯上来。
广度优先搜索较之深度优先搜索之不同在于，深度优先搜索旨在不管有多少条岔路，先一条路走到底，不成功就返回上一个路口然后就选择下一条岔路，而广度优先搜索旨在面临一个路口时，把所有的岔路口都记下来，然后选择其中一个进入，然后将它的分路情况记录下来，然后再返回来进入另外一个岔路，并重复这样的操作
区别
1. 数据结构上的运用
  
  DFS用递归的形式，用到了栈结构，先进后出。
  
  BFS选取状态用队列的形式，先进先出。
2. 复杂度
  
  DFS的复杂度与BFS的复杂度大体一致，不同之处在于遍历的方式与对于问题的解决出发点不同，DFS适合目标明确，而BFS适合大范围的寻找。
3. 思想
  
  思想上来说这两种方法都是穷竭列举所有的情况。

2. dropout

随机失活（dropout）是神经网络中相当常用的网络正则化方法。原理就在于，即使一张图像缺少少量部分，但我们人眼依然能分辨出目标。那一张图像可以有不同的地方缺失，这样就如同样本变多了，我们知道训练样本越大，网络越不容易拟合。

随机失活（dropout）在实际使用过程中，就有一个失活率 $\rho$ ，当然这个失活率不能太大。常用的0.2-0.3

3. 要同时使用BN和dropout该如何使用？

参考回答

同时使用BN和dropout时，可能存在方差偏移的问题

针对方差偏移，论文给出了两种解决方案：

拒绝方差偏移，只在所有BN层的后面采用dropout层（现在大部分开源的模型，都在网络的中间加了BN，我们也就只能在softmax的前一层加加dropout了，效果还行，至少不会比不加dropout差。还有另外一种方法是模型训练完后，固定参数，以测试模式对训练数据求BN的均值和方差，再对测试数据进行归一化，论文证明这种方法优于baseline）
dropout原文提出了一种高斯dropout，论文再进一步对高斯dropout进行扩展，提出了一个均匀分布Dropout，这样做带来了一个好处就是这个形式的Dropout（又称为“Uout”）对方差的偏移的敏感度降低了

4. 在预测的时候，是使用dropout训练出的权重还是要乘以keep-prib呢，为什么？

要乘以keep-prib。

因为神经元预测的时候就没办法随机丢弃，一种”补偿“的方案就是每个神经元的权重都乘以一个p，这样在“总体上”使得测试数据和训练数据是大致一样的。保证测试的时候把这个神经元的权重乘以p可以得到同样的期望。

注：目前主流是采用inverted dropout替代dropout，inverted dropout不需要乘以keep-prib。它的做法是在训练阶段对执行了dropout操作的层，其输出激活值要除以keep_prob，而测试的模型不用再做任何改动。

5. BN和LN

BatchNorm针对一个batch里面的数据进行规范化，针对单个神经元进行，比如batch里面有64个样本，那么BatchNorm得到的结果就是输入的这64个样本各自经过这个神经元后的规范化值；

LayerNorm则是针对单个样本的所有维度特征做归一化。比如batch里面有64个样本，那么LayerNorm得到的结果就是每一个样本经过该隐藏层（所有神经元）后的规范化值。

简单来说就是：batch normalization对一个神经元的batch所有样本进行标准化，layer normalization对一个样本同一层所有神经元进行标准化，前者纵向 normalization，后者横向 normalization。

6. 梯度消失怎么做的、梯度爆炸怎么做的

参考回答

假设我们有四层隐藏层，每层隐藏层只包含一个神经元节点。激活函数为sigmoid，输入为 $x$ ，则：

第一层的前向运算为 $z_1=w_1x+b_1$ ，经过激活函数后 $a_1=\sigma(z_1)$

第二层的前向运算为 $z_2=w_2a_1+b_2$ ，经过激活函数后 $a_2=\sigma(z_2)$

第三层的前向运算为 $z_3=w_3a_2+b_3$ ，经过激活函数后 $a_3=\sigma(z_3)$

第四层的前向运算为 $z_4=w_4a_3+b_4$ ，经过激活函数后 $a_4=\sigma(z_4)$

接着我们开始梯度反向求导：根据链式法则

$\frac{\partial C}{\partial b_1} = \frac{\partial C}{\partial a_4} \cdot \frac{\partial a_4}{\partial z_4} \cdot \frac{\partial z_4}{\partial a_3} \cdot \frac{\partial a_3}{\partial z_3} \cdot \frac{\partial z_3}{\partial a_2} \cdot \frac{\partial a_2}{\partial z_2} \cdot \frac{\partial z_2}{\partial a_1} \cdot \frac{\partial a_1}{\partial z_1} \cdot \frac{\partial z_1}{\partial b_1} \\ = \frac{\partial C}{\partial a_4} \cdot \sigma^{'}(z_4) \cdot w_4 \cdot \sigma^{'}(z_3) \cdot w_3 \cdot \sigma^{'}(z_2) \cdot w_2 \cdot \sigma^{'}(z_1) \cdot 1 \tag{.}$

当 $\sigma^{'}(z_i) < 1$ ， $\frac{\partial C}{\partial b_1} \rightarrow 0$ ，梯度消失

当 $\sigma^{'}(z_i) > 1$ ， $\frac{\partial C}{\partial b_1} \rightarrow \infty$ ，梯度爆炸

我们神经网络中的初始权值也一般是小于 1 的数，所以相当于公式中是多个小于 1 的数在不断的相乘，导致乘积和还很小。这只是有两层的时候，如果层数不断增多，乘积和会越来越趋近于 0，以至于当层数过多的时候，最底层的梯度会趋近于 0，无法进行更新，并且 Sigmoid 函数也会因为初始权值过小而趋近于 0，导致斜率趋近于 0，也导致了无法更新。

除了这个情况以外，还有一个情况会产生梯度消失的问题，即当我们的权重设置的过大时候，较高的层的激活函数会产生饱和现象，如果利用 Sigmoid 函数可能会无限趋近于 1，这个时候斜率接近 0，最终计算的梯度一样也会接近 0，最终导致无法更新。

7. 怎么缓解梯度消失、梯度爆炸

参考回答

预训练加微调
梯度剪切
使用合理的参数初始化方案，如He初始化
使用 ReLU、LReLU、ELU、maxout 等激活函数

sigmoid函数的梯度随着x的增大或减小和消失，而ReLU不会。
使用批规范化BN
残差结构

答案解析

无。

以上所有题的答案其实都来源于我的博客面经，欢迎大家围观：https://blog.nowcoder.net/jiangwenbo