Interview-Review(Algorithm)

本篇主要是面试复习内容的算法部分。

深度学习

模型评估方法

Accuracy作为指标有哪些局限性

准确率的定义是：分类正确的样本占总样本个数的比例，\(Accuracy = \frac{n_{correct}}{n_{total}}\)。但是此指标存在以下缺陷：

当正负样本非常不均衡时，占比大的类别就成为了影响准确率的主要因素，比如负样本占90%时，即使把所有样本都预测为负样本，也可以轻松获得90%的准确率，而这样的准确率是没有意义的，不足以说明分类器的好坏。
ROC曲线和PR曲线各是什么
编程实现AUC的计算，复杂度是多少
AUC指标有什么特点？放缩结果对AUC是否有影响
余弦距离与欧氏距离有什么特点

基本方法

如何划分训练集？如何选择验证集？

有以下几种不同的方法划分训练集与验证集：
- 留出法：
  1. 把数据集划分成互不相交的两部分，一部分作为训练集，一部分作为测试集；
  2. 保持数据的分布大致一致，类似分层抽样；
  3. 训练集数据所占比例应该为2/3或4/5左右
  4. 为了保证随机性，将数据集多次随机划分为训练集和测试集，然后再对多次划分的结果去平均
- k折交叉验证法：
  1. 将数据集随机分为互斥的k个子集，为保证随机性，使用p次随机划分取平均；
  2. 将k个子集随机分为k-1个组，剩下一个为另一组，有k种分法；
  3. 在每一种方法的分组结果中，那个k-1个子集的组都作为训练集，剩下的一个组作为测试集，这样就产生了k次预测，并对其取平均；
  4. 这种方法称为p次k折交叉验证，一般k取10
- 自助法：
  1. 当样本量足够时，使用自助法不如使用留出法和交叉验证法，因为无法满足数据分布一致。而如果样本量较小，无法划分，就可以使用自助法；
  2. 每次随机从数据集中抽取一个样本，然后再放回（可能会被重复抽出），m次之后会得到有m个样本的数据集，将其作为训练集；
  3. 始终没有抽到的样本的比例按概率算约是36.8%，这也保证了训练集占比大概在2/3左右
什么是偏差和方差？
什么是过拟合？在深度学习中，解决过拟合的方法有哪些？

过拟合（overfitting）是指在模型参数拟合过程中的问题。由于训练数据包含了抽样误差，而训练时，复杂的模型将抽样的误差也考虑在内。

过拟合具体的表现就是最终模型在训练集上效果很好，但测试集上效果很差。模型的泛化能力弱。

产生过拟合的原因有：
- 样本方面的原因。样本数量太少或者抽出的样本数据不能有效地代表场景；
- 样本里的噪声数据干扰过大，使得模型过分地记住了噪声特征，反而忽略了真实的输入输出间的关系；
- 参数太多以及模型复杂度高；
降低过拟合的方法有：
- 正则化：可以使用L0正则化、L1正则化或L2正则化，机器学习中一般采用L2正则化；
- dropout：可以随机地，以一定的概率让一部分神经元失活或者丢弃；
- batch normalization：BN在训练某层时，会对每一个batch数据都进行标准化或者叫归一化（normalization）处理，使得输出的规范呈正态分布；
- early stopping：当随着模型的能力提升，训练集的误差会先减小后增大，所以可以提前终止算法缓解过拟合的现象（例如决策树的预剪枝方法）；
- 重新清洗数据：有可能是因为数据不纯导致的，所以需要重新清洗数据；
- Data expending：增大数据的训练量。过拟合有可能是因为训练集的数据量太小导致的，或者训练数据占总数据的比例太小导致的；
深度模型参数调整的一般方法论

优化方法

简述了解的优化器

SGD(Stochastic Gradient Descent)

\(\theta=\theta-\eta \cdot \nabla_{\theta} J\left(\theta ; x^{(i)} ; y^{(i)}\right)\)

SGD随机梯度下降参数的更新原则是一条数据都可以对参数进行一次更新。其它的优化器都是在这个优化器的基础上改善得来的。

优点：参数的更新速度快；

缺点：由于每次参数更新时采用的数据量小，造成梯度更新时的震荡幅度较大，但是大多数情况是向着梯度较小的方向；

for i in range(nb_epochs):
    np.random.shuffle(data)
    for example in data:
        params_grad = eval_gradient(loss_function, example, params)
        params = params - learning_rate * params_grad

从上图可以看出，SGD的噪音较多，不是每次迭代都向着整体最优化方向。所以虽然训练速度快，但是准确率下降，并不是全局最优。

BGD(Batch Gradient Descent)

\(\theta=\theta-\eta \cdot \nabla_{\theta} J(\theta)\)

BGD批量梯度下降的参数更新原则是：所有数据都参与梯度的每一次更新。

优点：因为每次参数更新时采用的数据量都非常大，所以梯度更新时比较平滑；

缺点：由于参数更新时需要的数据量大，所以更新的速度非常慢；
1
2
3
for i in range(nb_epochs):
params_grad = eval_gradient(loss_function, example, params)
params = params - learning_rate * params_grad

MBGD(Mini-Batch Gradient Descent)

\(\theta=\theta-\eta \cdot \nabla_{\theta} J\left(\theta ; x^{(i: i+n)} ; y^{(i: i+n)}\right)\)

MBGD是每一次利用一小批样本，即n个样本进行计算，这样就可以降低参数更新时的方差，收敛更稳定。

优点：相比SGD，由于参与梯度更新的数据量大，所以梯度更新时较为平滑；相比BGD，参与梯度更新的数据量小，参数更新速度会更快一些。

缺点：

如果数据是稀疏的，希望对出现频率低的特征进行更大的更，learning_rate会随着更新的次数逐渐变小；
不能保证很好的收敛性，learning_rate如果选择得太小，收敛速度会很慢，如果太大，loss_function就会在极小值处不停地震荡甚至偏离。

for i in range(nb_epochs):
    np.random.shuffle(data)
    for batch in get_batches(data, batch_size=n):
        params_grad = eval_gradient(loss_function, batch, patams)
        params = params - learning_rate * params_grad

这里的batch_size=n的n一般取值在50~256之间。

Momentum

\(v_{n+1}=\gamma v_{n}+\eta \theta J(\theta)\)

\(\theta^{n+1}=\theta^{n}-v_{n+1}\)

Momenntum通过引入\(\gamma v_{n}\)，加速SGD，并且抑制震荡。\(\gamma\)一般取值为0.9左右，

优点：因为当我们将一个小球从山上滚下来时，没有阻力的话，它的动量就会越来越大，但是如果遇到了阻力，速度就会变小。所以加入了动量，**可以使得梯度方向不变的维度速度变快，梯度方向有所改变的维度上的更新速度变慢，这样就可以加快收敛并且减小震荡。

缺点：当梯度方向改变时，梯度更新速度不能及时减小导致适应性差。
Adagrad(Adaptive gradient algorithm)

Adagrad解决了不能根据参数重要性而对不同参数进行不同程度更新的问题。它的参数更新原则是：对低频的参数做较大的更新，对高频的参数做较小的更新。一般超参数\(\eta\)取值0.01。

\(\theta_{t+1, i}=\theta_{t, i}-\frac{\eta}{\sqrt{G_{t, i i}+\epsilon}} \cdot g_{t, i}\)

其中g是t时刻时参数\(\theta_i\)的梯度。

\(g_{t, i}=\nabla_{\theta} J\left(\theta_{i}\right)\)

优点：对于稀疏的数据它的表现很好，很好地提高了SGD的鲁棒性。

缺点：它的缺点是分母会不断的积累，这样学习率就会收缩最终会变得非常小。
Adadelta

Adadelta解决的就是Adagrad的缺点，即分母不断积累，导致学习率收缩变得非常小的问题。

Adadelta的参数更新原则就是和Adagrad相比，将分母的\(G_{t, i i}\)换成了过去的梯度平方的衰减平均值，指数衰减平均值。

\(\Delta \theta_{t}=-\frac{\eta}{\sqrt{E\left[g^{2}\right]_{t}}+\epsilon} g_{t}\)
RMSprop

同样是为了解决Adagrad的学习率急剧下降的问题。参数更新原则同样是使用指数加权平均。

\(E\left[g^{2}\right]_{t}=0.9 E\left[g^{2}\right]_{t-1}+0.1 g_{t}^{2}\)

\(\theta_{t+1}=\theta_{t}-\frac{\eta}{\sqrt{E\left[g_{t}^{2}\right]+\epsilon}} g_{t}\)

超参数\(\gamma\)为0.9，学习率\(\eta\)为0.001。
Adam(Adaptive Moment Estimation)

Adam相当于RMSprop+Momentum。

常用的损失函数有哪些，分别适用于场景

损失函数是用来估量模型的预测值\(f(x)\)与真实值Y的不一致程度。它是一个非负实值函数，通常使用\(L(Y, f(x))\)来表示。损失函数越小，模型的鲁棒性就越好。
- LogLoss对数损失函数
  
  可以适用于逻辑回归，交叉熵损失等。\(\log\)损失函数的标准形式是：
  
  \(L(Y, P(Y | X))=-\log P(Y | X)\)
  
  softmax使用的是交叉熵损失函数，binary_crossentropy使用的是二分类交叉熵损失函数，categorical_crossentropy使用的是多分类交叉熵损失函数。
- 平方损失函数
  
  可以适用于最小二乘法等。平方损失函数的标准形式如下：
  
  \(L(Y, f(X))=(Y-f(X))^{2}\)
  
  在实际应用中，通常使用均方差MSE作为一项衡量指标，公式如下：
  
  \(M S E=\frac{1}{n} \sum_{i=1}^{n}\left(\tilde{Y}_{i}-Y_{i}\right)^{2}\)
- 指数损失函数
  
  可以使用于Adaboost算法。
- Hinge损失函数
  
  在机器学习算法中，hinge损失函数与SVM是息息相关的。其标准形式是：
  
  \(L(y)=\max (0,1-y \tilde{y}), y=\pm 1\)
- 其它损失函数
  
  0-1损失函数：\(L(Y, f(X))=\left\{\begin{array}{ll} 1, & Y \neq f(X) \\ 0, & y=f(X) \end{array}\right.\)
  
  绝对值损失函数：\(L(Y, f(X))=|Y-f(X)|\)
- Keras/Tensorflow中常用的cost function：
  - mean_squared_error或者MSE
  - mean_absolute_error或者MAE
  - mean_absolute_percentage_error或者MAPE
  - mean_squared_logarithmic_error或者MSLE
  - squared_hinge
  - hinge
  - categorical_hinge
  - binary_crossentropy
  - logcosh
  - categorical_crossentropy
梯度下降与牛顿法、拟牛顿法的异同
L1和L2正则分别有什么特点？为什么L1更稀疏
如何提高小型网络的精度

深度学习基础

用一层隐藏层的神经网络，以ReLU作为激活函数，MSE作为损失函数推导反向传播
NN的权重参数能否初始化为0
什么是梯度消失和梯度爆炸，梯度爆炸的解决方法
常用的激活函数和导数
ReLU的优点和局限性，改进方法是什么
sigmoid和tanh为什么会导致梯度消失
相比sigmoid激活函数，ReLU激活函数有什么优势
一个隐藏层需要多少个节点能实现包含n元输入的任意布尔函数
多个隐藏层实现包含n元输入的任意布尔函数，需要多少个节点和网络层
Dropout为什么能够防止过拟合
Dropout和BN在前向传播和反向传播阶段的区别
解释批量归一化的原理
什么是反卷积，有哪些用途

CNN

给定卷积核的尺寸，特征图大小的计算方法
网络容量的计算方法
共享参数有什么优点
常用的池化操作有哪些，有什么特点，池化层有什么作用
CNN如何用于文本分类
ResNet提出的背景和核心理论是什么
空洞卷积是什么？有什么应用场景，作用是什么

RNN

简述RNN，LSTM，GRU的区别和联系
画出LSTM的结构图，写出公式
RNN的梯度消失问题，如何解决
LSTM中是否可以用ReLU作为激活函数
LSTM各个门分别使用什么作为激活函数
简述seq2seq模型
seq2seq在解码的时候有哪些方法
注意力机制是什么

机器学习

基础

样本不均衡如何处理（如何解决不平衡数据集的分类问题）

样本不均衡是指不同类别样本的比例相差悬殊，就会对算法的学习过程造成重大的干扰。例如，有1000个样本，只有5个正样本，995个负样本，那么算法把所有的样本都预测为负样本，精度也能达到99.5%。虽然精度很高，但是没有任何意义。

解决方法有：
- 欠采样，减少数量较多的那一类的样本的数量，使得正负样本的比例均衡。
  
  欠采样又分为随机欠采样、EasyEnsemble和BalanceCascade以及基于KNN欠采样。
  - 随机欠采样是指随机从多数类样本中抽取一部分数据进行删除。缺点就是未考虑到样本的分布情况，而采样过程又具有很大的随机性，可能会误删多数类样本中的一些重要信息。
  - EasyEnsemble是通过从多数的那一类样本中有放回的随机抽取一部分样本生成多个子数据集，将每个子集与少数类数据联合起来进行训练生成多个模型，然后综合多个模型的结果进行判断。方法和随机森林的原理很相似。
  - BalanceCascade是通过一次随机欠采样产生训练集，训练一个分类器，对于那些分类正确的多数类的样本不放回，然后剩下的多数类样本再次进行欠采样产生第二个训练器，训练第二个分类器，同样进行操作，以此类推，直到满足某个停止条件。最终的模型也是多个分类器的组合。
  - 基于KNN欠采样：有四种KNN欠采样的方法。
    - NearMiss-1：选择到最近的三个少数类样本平均距离最小的那些多数类样本
    - NearMiss-2：选择到最远的三个少数类样本平均距离最小的那些多数类样本
    - NearMiss-3：为每个少数类样本选择给定数目的最近多数类样本，目的是保证每个少数类样本都被一些多数类样本包围
    - 最远距离：选择到最近的三个少数类样本平均距离最大的那些多数类样本
- 过采样，增加数量较少的那一类的样本的数量，使得正负样本的比例均衡。
  
  过采样又分为随机过采样、SMOTE算法和Borderline-SMOTE算法以及基于K-means过采样。
  - 随机过采样是指多次随机从少数类样本中有放回的抽取数据，采取数量大于原有的少数类样本的数量。其中的有一部分数据会出现重复，而重复数据的出现会增大方差造成模型的过拟合。
  - SMOTE的全称是Synthetic Minority Oversampling Technique，即合成少数类过采样技术。它是基于随机过采样算法的一种改机方案。SMOTE算法的基本思想是对少数类样本进行分析并根据少数类样本人工合成新样本添加到数据集中。
  - Borderline-SMOTE算法较SMOTE算法提升的地方是只为那些K近邻中有一半以上多数类样本的少数类样本生成新样本，因为这些样本容易被错分，而在这些少数类样本附近生存人工合成样本，有助于少数类样本的分类正确。而如果少数类样本周围全是多数类样本，这种情况下，这个样本会被认定为噪声样本。
  - 基于K-means聚类过采样方法是首先分别对正负例进行K-means聚类，聚类之后，对其中较小的蔟进行上面的过采样方法扩充样本数量。然后再进行正负类样本的均衡扩充。
- 不处理样本，样本分类阈值移动。
什么是生成模型什么是判别模型
什么是鞍点问题
集成学习的分类？有什么代表性的模型和方法
常用的特征筛选方法有哪些
文本如何构造特征
类别变量如何构造特征
连续值变量如何构造特征
哪些模型需要对特征进行归一化
什么是组合特征？如何处理高维组合特征

处理分类问题常用算法

逻辑回归

逻辑回归怎么实现多分类

我们知道，普通的逻辑回归只能解决二分类问题。要想实现多分类，就要改进逻辑回归。
1. 第一种方式是One-Vs-All（或者叫One-Vs-Rest）。直接根据每个类别，都建立一个二分类器。带有这个类别的样本标记为1，带有其它样本的标记为0。如果有k个类别，那么最终就得到了k个针对不同标记的普通的逻辑分类器。
2. 第二种方式是One-Vs-One。让不同类别的数据两两组合训练分类器。
3. 第三种方式是修改逻辑回归的损失函数，让其适应多分类问题。即softmax回归。
交叉熵公式
LR公式，LR的推导和损失函数
LR与SVM的区别和联系

相同点有：
- 都是监督的分类算法
- 都会线性分类算法
- 都会判别模型
不同点有：
- 损失函数不同。LR的损失函数是cross entropy：，SVM的损失函数是最大化间隔距离：
- SVM不能产生概率，LR可以产生概率
- SVM依赖于数据的测度，而LR不受影响
- SVM自带结构风险最小化，LR是经验风险最小化
- SVM会用核函数而LR一般不用核函数的原因
LR和线性回归的区别
为什么正则化可以防止过拟合（为什么L1和L2正则化可以降低过拟合）
L1正则和L2正则有什么区别
L1正则化不可导，怎么求解
逻辑回归为什么一般性能差
如何使用LR解决非线性问题

SVM

SVM什么时候使用线性核，什么时候使用高斯核
SVM的作用和基本实现原理
SVM的硬间隔和软间隔表达式
SVM使用对偶计算的目的是什么，如何推导出来的，手写推导
SVM为什么要求解决对偶问题？为什么对偶问题与原问题等价
SVM的物理意义是什么
SVM的核函数的选择
SVM的核函数的作用
SVM的核函数的原理
SVM为什么采用间隔最大化（与感知机的区别）
为什么SVM对缺失数据敏感
SVM的优缺点
SVM如何调节惩罚因子C
如何处理SVM中样本不平衡的问题
SVM如何处理多分类问题
SVM对噪声敏感的原因
如何使用SMO最优化方法求解SVM模型
SMO算法优化的终止条件是什么
是否一定存在参数使得SVM的训练误差到0

随机森林

随机森林与SVM的区别
随机森林不会发生过拟合的原因
随机森林与梯度提升树（GBDT）的区别
随机森林是怎么避免ID3算法信息增益的缺点的
为什么随机森林能降低方差

朴素贝叶斯

朴素贝叶斯的要求（前提假设）是？
朴素贝叶斯算法原理和工作流程
什么是先验概率和后验概率
什么是条件概率
朴素贝叶斯为什么“朴素”
朴素贝叶斯可以做多分类吗
什么是朴素贝叶斯中的零概率问题？如何解决
朴素贝叶斯中概率计算的下溢问题如何解决
朴素贝叶斯分类器对异常值敏感吗
朴素贝叶斯对缺失值敏感吗
朴素贝叶斯有哪几种常用的分类模型
朴素贝叶斯算法中使用拉普拉斯平滑，拉普拉斯因子的大小如何确定
为什么说是朴素贝叶斯是高偏差低方差的
朴素贝叶斯为什么是增量计算
高度相关的特征对朴素贝叶斯有什么影响
朴素贝叶斯有什么优缺点

决策树

ID3，C4.5和CART三种决策树的区别
简述决策树的原理
简述决策树的构建过程
决策树有哪些划分指标，其区别和联系
信息增益率有什么优缺点
如何对决策树进行剪枝操作，为什么要进行剪枝
树模型如何调参
树模型如何剪枝
预剪枝和后剪枝
简述一下分类树和回归树
决策树对缺失值如何处理
如果决策树属性用完了，但仍未对决策树完成划分该怎么办
如何避免决策树的过拟合
决策树需要进行归一化处理吗
与其它模型比较，决策树有哪些优点和缺点

处理回归问题常用算法

线性回归

简单介绍一下线性回归的原理（什么是线性回归）
线性回归的求解方法有哪些
线性回归为什么用均方差

普通最小二乘回归

最小二乘法的推导
最小二乘法和梯度下降法有哪些区别

逐步回归

简述逐步回归算法

多元自适应回归样条

简述多元自适应回归样条

处理聚类问题常用算法

K均值（基于划分的聚类）

简述一下K-means算法的原理和工作流程
K-means有什么缺点
K值如何确定
初始点选择方法
K-means不能处理哪种数据
K-means如何处理大数据（几十亿）
K-means与KNN有何不同

DBSCAN（基于密度的聚类）

DBSCAN与传统的K-means的不同
DBSCAN的聚类法原理

LDA

模型融合和提升的常用算法

Bagging

Adaboost

GBDT

GBRT

Stacking

Blending

XGBoost

其它重要算法

CV

NLP

word2vec的原理
glove的原理
fasttext的原理
了解elmo和bert吗？简述与word embedding的联系与趋避

常用算法

搜索回溯

八皇后，全排列，组合
重复数字的排列，重复数字的组合
图的搜索
A star

概率题

用rand7构造rand10
轮盘赌

动态规划

编辑距离
背包问题
LCS
备忘录方法

字符串

给定字符串是否符合正则表达式
给定字符串是否是数字
KMP
超大数相加

海量数据

海量日志的出现最多的K个字符串
10亿个1-10的数字排序
trie树
布隆过滤器

基本概念

算法的几个特征是什么
算法复杂性的定义，大O、θ、Ω、小o分别表示的含义
递归算法的定义、递归算法的两个要素
分治算法的思想
动态规划算法的两个要素是什么
贪心算法的思想，贪心算法的两个要素
回溯法的思想，回溯法中有哪两种典型的模型
分支限界法思想，有哪两种分支限界法