前言
真的是千呼万唤始出来emmmm，去年春招结束写了篇面试的经验分享。在文中提到和小伙伴整理了算法岗面试时遇到的常见知识点及回答，本想着授人以渔，但没想到大家都看上了我家的 ！但因本人执行力不足，被大家催到现在才终于想着行动起来分享给大家，笔者在这里给各位读者一个大大的抱歉，求原谅呜呜~~相信今年参加秋招的小伙伴们一定都拿到理想的offer啦，明年准备找工作的小盆友如果觉得本文还有些用可以收藏哈。
由于篇幅限制，就先发出前半部分，后面等下回笔者得空哈~另外欢迎小伙伴们转发！转发！再转发呀！！转发请注明出处，且谢绝一切利用本文档的商业行为！！
第一章 机器学习
1.Batch Normalization
背景：由于Internal Covariate Shift(Google)效应，即深度神经网络涉及到很多层的叠加，而每一层的参数更新会导致上层的输入数据分布发生变化，通过层层叠加，高层的输入分布变化会非常剧烈，这就使得高层需要不断去重新适应底层的参数更新。为了训好模型，我们需要非常谨慎地去设定学习率、初始化权重、以及尽可能细致的参数更新策略。 也就是随是着网络加深，参数分布不断往激活函数两端移动(梯度变小)，导致反向传播出现梯度消失，收敛困难。
原理：可在每层的激活函数前，加入BN，将参数重新拉回0-1正态分布，加速收敛。(理想情况下，Normalize的均值和方差应当是整个数据集的，但为了简化计算，就采用了mini_batch的操作)
*机器学习中的白化（eg.PCA）也可以起到规范化分布的作用，但是计算成本过高。
*BN不是简单的归一化，还加入了一个y = γx+β的操作，用于保持模型的表达能力。否则相当于仅使用了激活函数的线性部分，会降低模型的表达能力。
训练与测试：测试时均值和方差不再用每个mini-batch来替代，而是训练过程中每次都记录下每个batch的均值和方差，训练完成后计算整体均值和方差用于测试。
参考：https://blog.csdn.net/sinat_33741547/article/details/87158830
https://blog.csdn.net/qq_34484472/article/details/77982224
https://zhuanlan.zhihu.com/p/33173246
*BN对于Relu是否仍然有效？
有效，学习率稍微设置大一些，ReLU函数就会落入负区间(梯度为0)，神经元就会永远无法激活，导致dead relu问题。BN可以将数据分布拉回来。
*四种主流规范化方法
Batch Normalization(BN):纵向规范化
Layer Normalization(LN):横向规范化 对于单个样本
Weight Normalization(WN):参数规范化 对于参数
Cosine Normalization(CN):余弦规范化 同时考虑参数和x数据
*多卡同步
原因：
对于BN来说,用Batch的均值和方差来估计全局的均值和方差,但因此Batch越大越好.但一个卡的容量是有限的,有时可能batch过小,就起不到BN的归一化效果.
原理：
利用多卡同步,单卡进行计算后,多卡之间通信计算出整体的均值和方差,用于BN计算, 等同于增大batch size 大小.
2次同步? 第一次同步获得全局均值,然后第二次计算全局方差
1次同步! 直接传递一次X和X2,就可直接计算出全局均值和方差.
操作(pytorch)
注:
- 对于目标检测和分类而言,batch size 通常可以设置的比较大,因此不用多卡否则反而会因为卡间通讯,拖慢训练速度.
- 对于语义分割这种稠密的问题而言,分辨率越高效果越好,因此一张卡上容纳的batch size 比较小,需要多卡同步.
- 数据被可使用的GPU卡分割（通常是均分）,因此每张卡上BN层的batch size（批次大小）实际为:Batch Size/nGpu
2.VGG使用使用3*3卷积核的优势是什么？
2个3x3的卷积核串联和一个5x5的卷积核拥有相同的感受野，但是，2个3x3的卷积核拥有更少的参数，对于通道为1的5x5特征图得到通道为1的输出特征图，前者有3x3x2=18个参数，后者5x5=25个参数，其次，多个3x3的卷积核比一个较大的尺寸的卷积核加入了更多的非线性函数，增强了模型的非线性表达能力。
1x1卷积核的作用：改变通道数目，保持尺度不变情况下增强非线性表达能力，可以实现跨通道的信息交互。
VGG：
ResNet:
3.逻辑斯蒂回归（LR, Logistic Regression)
3.1 模型简介
分布函数与概率密度函数：
其中，μ表示位置参数，γ为形状参数。在深度学习中常用到的 Sigmoid 函数就是 Logistic 的分布函数在μ=0，γ=1的特殊形式。
损失函数：
求解方法：1.随机梯度下降法 2.牛顿法
参考 https://zhuanlan.zhihu.com/p/74874291
3.2 相关问题
一、LR有什么特点？
简单、容易欠拟合、值域为(0,1)、无穷阶连续可导。
各feature之间不需要满足条件独立假设，但各个feature的贡献独立计算
二、Sigmoid变化的理解？
a) sigmoid函数光滑，处处可导，导数还能用自己表示
b) sigmoid能把数据从负无穷到正无穷压缩到0，1之间，压缩掉了长尾，扩展了核心分辨率。
c) sigmoid在有观测误差的情况下最优的保证了输入信号的信息。
三、与SVM、线性回归等模型对比
参考 https://zhuanlan.zhihu.com/p/74874291
因为阶跃函数不连续，寻找替代函数如 sigmoid：
作变换可得到：
即用线性回归的结果去拟合事件发生几率(“几率”是事件发生与不发生的概率比值)的对数，这就是“对数几率回归”的名称来由，其名为回归，实际上是做分类任务。
为什么不用均方误差作为损失：
4.卷积
原理:卷积过程就是卷积核行列对称翻转后,在图像上滑动,并且依次相乘求和.(与滤波器不同的一点就是多了一个卷积核翻转的过程).然后经过池化,激活后输入下一层. 单个卷积层可以提取特征,当多个卷积叠加后即可逐步学习出更高语义的抽象特征.
*这里提到了卷积,池化以及激活,那么池化以及激活的顺序如何考虑?一般来说池化和激活的顺序对计算结果没有影响(其实是maxpooling无影响,但是如果用avgpooling的话,先后顺序还是会影响结果一点的),但先池化可以减小接下来激活的计算量.
卷积核:其中卷积核主要有两类,普通卷积核和1*1的卷积核.
普通卷积核同时改变图像的空间域和通道域,如下图所示,每个卷积核的通道数与输入相同,卷积后会得到一个通道为一的特征图,我们希望卷积后的通道数有几个,卷积核就有几个.
1*1卷积核,视野大小为单个特征位点,能够实现在空间域不改变的情况下实现通道域信息的交流,并且获得我们想要的通道数量(一般是降维).
另外,1*1的卷积可以看作全连接.
_参考:
_https://blog.csdn.net/amusi1994/article/details/81091145?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
反卷积：上采样有3种常见的方法：双线性插值(bilinear)，反卷积(Transposed Convolution)，反池化(Unpooling)，我们这里只讨论反卷积。这里指的反卷积，也叫转置卷积，它并不是正向卷积的完全逆过程，用一句话来解释：反卷积是一种特殊的正向卷积，先按照一定的比例通过补0来扩大输入图像的尺寸，接着旋转卷积核，再进行正向卷积。
https://www.zhihu.com/question/48279880
空洞卷积
诞生背景
在图像分割领域，图像输入到CNN（典型的网络比如FCN[3]）中，FCN先像传统的CNN那样对图像做卷积再pooling，降低图像尺寸的同时增大感受野，但是由于图像分割预测是pixel-wise的输出，所以要将pooling后较小的图像尺寸upsampling到原始的图像尺寸进行预测，在先减小后增大尺寸的过程中，肯定有些信息损失掉了，如何避免？答案就是空洞卷积。
(a)图对应3x3的1-dilated conv，和普通的卷积操作一样，(b)图对应3x3的2-dilated conv，实际的卷积kernel size还是3x3，但是空洞为1，也就是对于一个7x7的图像patch，只有9个红色的点和3x3的kernel发生卷积操作，其余的点略过。也可以理解为kernel的size为7x7，但是只有图中的9个点的权重不为0，其余都为0。©图是4-dilated conv操作
优点
dilated的好处是不做pooling损失信息的情况下，加大了感受野，让每个卷积输出都包含较大范围的信息。在图像需要全局信息或者语音文本需要较长的sequence信息依赖的问题中，都能很好的应用dilated conv，比如图像分割、语音合成WaveNet、机器翻译ByteNet中。
潜在问题 1：The Gridding Effect
我们发现我们的 kernel 并不连续，也就是并不是所有的 pixel 都用来计算了，因此这里将信息看做 checker-board 的方式会损失信息的连续性。这对 pixel-level dense prediction 的任务来说是致命的。
潜在问题 2：Long-ranged information might be not relevant.
我们从 dilated convolution 的设计背景来看就能推测出这样的设计是用来获取 long-ranged information。然而光采用大 dilation rate 的信息或许只对一些大物体分割有效果，而对小物体来说可能则有弊无利了。如何同时处理不同大小的物体的关系，则是设计好 dilated convolution 网络的关键。
通向标准化设计：Hybrid Dilated Convolution (HDC)
对于上个 section 里提到的几个问题，图森组的文章对其提出了较好的解决的方法。他们设计了一个称之为 HDC 的设计结构。
第一个特性是，叠加卷积的 dilation rate 不能有大于1的公约数。比如 [2, 4, 6] 则不是一个好的三层卷积，依然会出现 gridding effect。
第二个特性是，我们将 dilation rate 设计成 锯齿状结构，例如 [1, 2, 5, 1, 2, 5] 循环结构。
第三个特性是，我们需要满足一下这个式子：
ri 是i层的dilation rate, Mi是i层的最大dilation rate, 那么假设总共有n层的话，默认 Mn = rn 。假设我们应用于 kernel 为 k x k 的话，我们的目标则是M2 <= k ，这样我们至少可以用 dilation rate 1 即 standard convolution 的方式来覆盖掉所有洞。
基于港中文和商汤组的 PSPNet 里的 Pooling module （其网络同样获得当年的SOTA结果），ASPP 则在网络 decoder 上对于不同尺度上用不同大小的 dilation rate 来抓去多尺度信息，每个尺度则为一个独立的分支，在网络最后把他合并起来再接一个卷积层输出预测 label。这样的设计则有效避免了在 encoder 上冗余的信息的获取，直接关注与物体之间之内的相关性。
https://www.zhihu.com/question/54149221
卷积的三种模式：
通常用外部api进行卷积的时候，会面临mode选择
其实这三种不同模式是对卷积核移动范围的不同限制
设 image的大小是7x7，filter的大小是3x3
full mode：
橙色部分为image, 蓝色部分为filter。full模式的意思是，从filter和image刚相交开始做卷积，白色部分为填0。filter的运动范围如图所示。
same mode：
当filter的中心(K)与image的边角重合时，开始做卷积运算，可见filter的运动范围比full模式小了一圈。注意：这里的same还有一个意思，卷积之后输出的feature map尺寸保持不变(相对于输入图片)。当然，same模式不代表完全输入输出尺寸一样，也跟卷积核的步长有关系。same模式也是最常见的模式，因为这种模式可以在前向传播的过程中让特征图的大小保持不变，调参师不需要精准计算其尺寸变化(因为尺寸根本就没变化)。
valid mode：
当filter全部在image里面的时候，进行卷积运算，可见filter的移动范围较same更小了。
5.交叉熵与softmax
5.1 数学原理
交叉熵刻画的是实际输出（概率）与期望输出（概率）的距离，也就是交叉熵的值越小，两个概率分布就越接近。假设概率分布p为期望输出(标签)，概率分布q为实际输出，H(p,q)为交叉熵。
第一种交叉熵损失函数的形式：
第二种交叉熵损失函数的形式：
5.2 交叉熵不适用于回归问题
当MSE和交叉熵同时应用到多分类场景下时，（标签的值为1时表示属于此分类，标签值为0时表示不属于此分类），MSE对于每一个输出的结果都非常看重，而交叉熵只对正确分类的结果看重。例如：在一个三分类模型中，模型的输出结果为（a,b,c)，而真实的输出结果为(1,0,0)，那么MSE与cross-entropy相对应的损失函数的值如下：
MSE：
cross-entropy：
从上述的公式可以看出，交叉熵的损失函数只和分类正确的预测结果有关系，而MSE的损失函数还和错误的分类有关系，该分类函数除了让正确的分类尽量变大，还会让错误的分类变得平均，但实际在分类问题中这个调整是没有必要的。但是对于回归问题来说，这样的考虑就显得很重要了。所以，回归问题熵使用交叉上并不合适。
5.3 交叉熵与softmax
交叉熵损失函数经常用于分类问题中，特别是神经网络分类问题，由于交叉熵涉及到计算每个类别的概率，所以在神经网络中，交叉熵与softmax函数紧密相关。在神经网络中，Softmax通常作用于分类模型最后的输出，将分类结果归一化为（0，1）区间，表示各分类结果的概率。它的函数形式为：
1）为什么softmax分母是所有类别的加权和？
归一化操作，将输入映射为（0，1）之间的概率值。
2）为什么要引入指数形式？
如果使用max函数，虽然能完美的进行分类但函数不可微从而无法进行训练，引入以 e 为底的指数并加权归一化，一方面指数函数使得结果将分类概率拉开了距离，另一方面函数可微。
3）为什么不用2、4、10等自然数为底而要以 e 为底呢？
主要是以e为底在求导的时候比较方便。
参考：https://www.jianshu.com/p/1536f98c659c
6. 激活函数的意义
激活函数的主要作用是提供网络的非线性建模能力。如果没有激活函数，那么该网络仅能够表达线性映射，即便有再多的隐藏层，其整个网络跟单层神经网络也是等价的。
Sigmoid
可以被表示作概率，或用于输入的归一化。
sigmoid函数连续，光滑，严格单调，以(0,0.5)中心对称，是一个非常良好的阈值函数。
Sigmoid函数的导数是其本身的函数，即f′(x)=f(x)(1−f(x))，计算非常方便，也非常节省计算时间。
【补充：
具有这种性质的称为软饱和激活函数。具体的，饱和又可分为左饱和与右饱和。与软饱和对应的是硬饱和, 即 f′(x)=0，当|x|>c，其中c为常数。f′(x)=0，当|x|>c，其中c为常数。】
一旦输入落入饱和区，f′(x)f′(x) 就会变得接近于0，导致了向底层传递的梯度也变得非常小。此时，网络参数很难得到有效训练。这种现象被称为梯度消失。
此外，sigmoid函数的输出均大于0，使得输出不是0均值，这称为偏移现象，这会导致后一层的神经元将得到上一层输出的非0均值的信号作为输入。
tanh
tanh也是一种非常常见的激活函数。与sigmoid相比，它的输出均值是0，使得其收敛速度要比sigmoid快，减少迭代次数。然而，从途中可以看出，tanh一样具有软饱和性，从而造成梯度消失。
tanh 的导数为 1-(tanh(x))2
RELU
当x<0时，ReLU硬饱和，而当x>0时，则不存在饱和问题。所以，ReLU 能够在x>0时保持梯度不衰减，从而缓解梯度消失问题。
然而，随着训练的推进，部分输入会落入硬饱和区，导致对应权重无法更新。这种现象被称为“神经元死亡”。与sigmoid类似，ReLU的输出均值也大于0，偏移现象和 神经元死亡会共同影响网络的收敛性。针对在x<0的硬饱和问题，Leaky-ReLU对ReLU做出相应的改进，使得
7. pooling有什么意义，和卷积有什么区别
1、降维减少计算量和内存消耗
2、增大深层卷积的感受野
3、压缩特征图，提取主要特征
反向传播
设卷积核尺寸为p x q, 步长为t,为保证整除,填充后的X是m x n 矩阵, 经MaxPooling 卷积得到g x h矩阵Y, 前向传播得到误差值error(标量e)。上游的误差梯度向量
已在反向传播时得到, 求 e 对 X 的梯度.
已知 :
e=forward(Y)
其中：
其中，
由上游计算得出。
参考：https://www.nowcoder.com/discuss/371584
https://www.nowcoder.com/tutorial/95/ea84cef4fb2c4555a7a4c24ea2f6b6e8
https://blog.csdn.net/oBrightLamp/article/details/84635346
8.泛化误差（过拟合）
训练误差与泛化误差：训练误差：
泛化误差：
泛化误差表达模型的泛化能力，可以理解为样本误差的期望，p(x)为表示全集合X中x出现的概率（x可以是一个样本，也可以是一个集合）
训练误差只能代表选定的部分数据的误差，但泛化误差能考虑到全数据集。
泛化误差分解：
即泛化误差 = 方差 + 偏差 + 噪声
1，噪声是模型训练的上限，也可以说是误差的下限，噪声无法避免。
2，方差表示不同样本下模型预测的稳定程度（方差大其实就是过拟合，预测不稳定）
3，偏差表示模型对训练数据的拟合程度 （偏差大就是欠拟合，预测效果不好）
训练过程中方差和偏差此消彼涨
降低方差的方法：（其实就是防止过拟合）
数据：
1. 增大数据量，进行数据增强
2. 进行数据清洗（纠正错误数据）
3. 进行特征选择，降低特征维度
4. 类别平衡（欠采样、过采样）
网络结构：
1，正则化L1,L2, BN 2,dropout
宏观：
1. 选择合适复杂度的模型，或对已有模型进行剪枝、删减
2. 集成学习(Ensemble)
3. 限制训练
降低偏差的方法：（防止欠拟合）
输入：优化特征，检查特征工程是否有漏掉的具有预测意义的特征
网络中间：削弱或者去除已有的正则化约束
宏观：1,增加模型复杂度， 2，集成学习(Ensemble) 3,增大训练轮数
*注：集成学习可以同时降低方差与偏差
参考 ：https://www.sohu.com/a/317862976_654419
9. LR相关
手推：
zhx:
最大似然<-> 最小化损失
优缺点：
优点：
1. 参数代表每个特征对输出的影响，可解释性强
2. 简单，计算量小、存储占用低，可以在大数据场景中使用
缺点
1. 容易欠拟合，精度不高
2. 对异常值比较敏感
LR如何解决低维不可分：通过核函数将特征把低维空间转换到高维空间，在低维空间不可分的数据，到高维空间中线性可分的几率会高一些
怎么防止过拟合：L1正则与L2正则
10. SVM
1. 基本原理、意义(4)
SVM需要找到一个超平面，将所有的样本点都正确分类，并且其与所有样本点的几何间隔最大化；通过变换可以将其化为凸二次规划问题，是一个带有不等式约束的求最小值的问题。二次规划问题可以直接解，但通常的做法是利用拉格朗日乘子法去解它的对偶问题，解法如 SMO；而根据其所需满足的 KKT 条件，可以知道该解仅和几何间隔最小的那部分样本有关，这些样本就叫支持向量。
1. 软间隔、损失函数(3)
2. 核函数列举、选择(3)
3. 为什么用对偶函数(2)
4. SVM与LR (2)
基本原理与推导 ：
点到超平面的距离：
令(样本确定后，最优的r就固定了，可以通过改变分母来调整分子的大小，得出下式)
：
最大化r，也就是最小化下式 (约束中有不等式，需要满足KKT条件)：
KKT条件：乘子、约束、约束*乘子：
必有：
前者表明样本无影响，后者表明样本是支持向量。
核函数：
当样本是线性不可分的时候，需要将其特征映射到高维空间，使其线性可分；而在解对偶问题时涉及到两个样本的内积运算，直接在高维空间计算太困难；因此引入核函数，其值等于样本在高维空间的内积，就能在低维空间计算。
核函数的作用：
1. 将特征空间从低维映射到高维，使得原本线性不可分的问题变为线性可分。
2. 使用核函数计算，避免了在高维空间中进行复杂计算，且不影响其效果。
常见的核函数如下：
核函数的选择：
1. 样本特征较多、维数较高、线性可分时，通常采用线性核。
2. 样本特征较少，样本数适中、线性不可分、情况不明时可先尝试高斯核。高斯核参数较多，结果对参数的敏感性较高，通过交叉验证可以寻找到合适的参数，但比较耗时
软间隔与损失函数：
现实任务中很难确定核函数是否使得样本线性可分了(即便找到了某个核函数使得样本线性可分，也不能保证它不是过拟合产生的结果。)。
软间隔意味着SVM允许部分样本不满足约束条件，即不要求所有样本都被正确分类。
此时，优化目标为：
式中的后一项表示被错误分类的数目，C是权重，单纯的0/1损失显然不好用，于是引入替代的损失函数，常见如下：
11. 约束优化问题的对偶问题
参考链接：https://www.bilibili.com/video/BV1Hs411w7ci
对偶性的几何解释：
d* <= p* （弱对偶性）
凸优化+Slater条件 => d* = p*
充分非必要
参考链接：https://www.bilibili.com/video/BV1aE411o7qd?p=33
凸优化（百科）：凸优化是指一种比较特殊的优化，是指求取最小值的目标函数为凸函数的一类优化问题。其中，目标函数为凸函数且定义域为凸集的优化问题称为无约束凸优化问题。而目标函数和不等式约束函数均为凸函数，等式约束函数为仿射函数，并且定义域为凸集的优化问题为约束优化问题。
仿射函数：仿射函数即由由1阶多项式构成的函数，一般形式为f(x)=Ax+b，其中的特例是，函数f(x)=ax+b，其中a、x、b都是标量。此时严格讲，只有b=0时，仿射函数才可以叫“线性函数”（“正比例”关系）。
Slater条件：
relint：relative interior，除去边界的定义域
1. 对于大多数凸优化，slater条件成立。
有时候在定义域内部求fi(x)是否<0比较困难
1. 放松的slater：m中有k个仿射函数，那么只检查剩下m-k个是否满足条件。
SVM天生：凸二次优化+slater条件 => 强对偶性(p*=d*) <=> KKT条件
KKT条件：
原问题如下，其最优解p*
其对偶问题，最优解d*
KKT条件：给定了x*，λ*,η*求解关系。
1. 梯度为0，L`=0
2. 原问题可行条件， mi(x)<=0, nj(x)=0
3. 对偶问题可行，λi>=0
4. 互补松弛条件：λi * mi=0
互补松弛条件和梯度=0条件推导。
参考资料：https://zhuanlan.zhihu.com/p/58064316
https://www.bilibili.com/video/BV1aE411o7qd?p=34
https://blog.csdn.net/feilong_csdn/article/details/62427148
11.Dropout
背景：为了减轻过拟合问题，2012年Hintion在论文中提出Dropout方法
原理：
1，前向传播时按概率p随机关闭神经元（每个neuron, 有p%的可能性被去除;（注意不是去除p比例的神经元），本次反向传播时，只更新未关闭的神经元
2，下一次训练时，恢复上一轮被更新的神经元，然后重复操作1
其中，Bernoulli函数是为了生成概率r向量，也就是随机生成一个0、1的向量
训练与测试：
测试时需要关闭dropout,否则仍然按概率抛弃神经元会导致网络不稳定，即同一样本多次预测结果不同。
但若什么处理都不做，会导致训练与测试结果不同。
为了平衡训练与测试的差异，可以采取使得训练与测试的输出期望值相等的操作：
[补]：
1，训练时除以p：假设一个神经元的输出激活值为a，在不使用dropout的情况下，其输出期望值为a，如果使用了dropout，神经元就可能有保留和关闭两种状态，把它看作一个离散型随机变量，它就符合概率论中的0-1分布，其输出激活值的期望变为 p*a+(1-p)*0=pa，此时若要保持期望和不使用dropout时一致，就要除以 p
2, 测试时乘p
为什么可以减轻过拟合？
1，ensemble效果：训练过程中每次随机关闭不同的神经元，网络结构已经发生了改变，整个dropout的训练过程就相当于很多个不同的网络取平均，进而达到ensemble的效果。
2，减少神经元之间复杂的共适应关系：dropout导致每两个神经元不一定每一次都在网络中出现，减轻神经元之间的依赖关系。阻止了某些特征仅仅在其它特定特征下才有效果的情况，从而迫使网络无法关注特殊情况，而只能去学习一些更加鲁棒的特征。
BN和Dropout共同使用出现的问题
Dropout为了平衡训练和测试的差异，会通过随机失活的概率来对神经元进行放缩，进而会改变其方差。如果再加一层BN，又会将方差拉回至（0-1）分布，进而产生方差冲突。
处理方法：1，始终将Dropout放在BN后 2，使用高斯Dropout
参考 ：
https://zhuanlan.zhihu.com/p/38200980
https://blog.csdn.net/songyunli1111/article/details/89071021
