机器学习常见面试题(持续更新中...)

写在前面

本篇博客收集一些机器学习的常见面试题，题目主要为机器学习和自然语言处理相关，不包括计算机视觉。并附上个人答案，持续更新，直到今年秋招结束。欢迎大家在评论去贡献题目和讨论答案。

监督学习与非监督学习区别，非监督学习举例

主要是训练数据上的区别，监督学习的数据是有标记的，非监督学习的数据是没有标记的。
非监督学习举例：新闻聚类，用户人群分类

统计（传统）机器学习和深度学习的区别与联系

传统机器学习需要人工设计特征，特征工程很重要。
深度学习可以自动学习特征，特别是在图像、语音、文本方面，这些数据都有局部和整体的关系，DL能发挥很大作用。但是调参也是一个繁琐的事情。
联系：深度学习是一种实现机器学习的技术。

特征工程你一般怎么做

数据和特征决定了机器学习的上限，而模型和算法只是逼近这个上限而已。
特征工程的目的是获取更好的训练数据，把原始数据转变成特征。从数学的角度来看，特征工程就是人工的去设计输入变量X。
特征构建 -> 特征提取 -> 特征选择
特征构建
指从原始数据中人工的构建新的特征。
特征提取
自动的构建新的特征，将原始特征转换为一组有明显统计意义的特征。

PCA(Principal component analysis, 主成分分析)

ICA(Independent component analysis, 独立成分分析)

LDA(Linear Discriminant Analysis, 线性判别分析)

特征选择
从给定的特征集合中选择出相关特征子集的过程，称为特征选择。
原因：

维数灾难

去除不相关的特征往往会降低学习任务的难度

主要选择方式

过滤式选择

包裹式选择

嵌入式选择与L1正则化

什么是数据标准化，为什么要进行数据标准化？

数据标准化时预处理步骤，将数据标准化到一个特定的范围能够在反向传播中保证更好的收敛。一般来说，是将该值去平均值后再除以标准差。如果不进行标准化，有些特征值（值很大）将会对损失函数影响更大（即使这个特征改变很小）。因此数据标准化可以使得每个特征的重要性更加均衡。

机器学习中对样本数据不平衡的情况有哪些解决办法

假设正样本<<负样本
对数据进行重采样
(1) 对正样本的数据样本进行采样来增加正样本的数据样本个数，即过采样（over-sampling, 采样的次数大于改类样本个数）
(2) 对负样本的数据样本进行采样来减少该类数据样本的个数，即欠采样（under-sampling, 采样的次数少于该类样本的个数）
阈值移动
原来学习器在决策过程中假设真实正、反例可能性相同。
可以进行“再缩放”，改变学习器的评价标准，学习器的预测几率高于观测几率。

解释什么是降维，在哪里会用到降维，它的好处是什么？

降维是指通过保留一些比较重要的特征，去除一些冗余的特征，减少数据特征的维度。而特征的重要性取决于该特征能够表达多少数据集的信息，也取决于使用什么方法进行降维。使用哪种降维方法则是通过反复的试验和每种方法在该数据集上的效果。一般情况会先使用线性降维方法再使用非线性的降维方法。
好处：
(1) 节省存储空间
(2) 加速计算速度，维度越少，计算量越少，并且能够使用那些不适合高维度的算法
(3) 去除一些冗余特征，比如降维后使得数据不会即保存平方米又保存平方英里的表示地形大小的特征
(4) 将数据维度降到2维或者3维使之能可视化，便于观察和挖掘信息
(5) 特征太多或者太复杂会使得模型过拟合

如何处理缺失值

处理方法有两种，一种是删除整行或者整列的数据，另一种则是使用其他值去填充。

过拟合如何解决

获取更多的数据，数据越多越接近整体

使用简单的模型

训练时间，提前结束训练（Early stopping）

正则化（限制权值）

AUC是什么

AUC(Area Under ROC Curve)，即在ROC曲线下的面积。ROC曲线就是根据学习器的预测结果对样例进行排序，按此顺序逐个把样本作为正例进行预测，每次计算出两个重要的量，一个是真正例率，一个是假正例率(假例中预测为正例的比率)，真正例率(正例中预测为正例的比率)作为纵轴，假正例率作为横轴，作图，就得到ROC曲线。

解释k-means原理

k均值算法针对聚类所得的簇划分最小化平方误差。
找到最优解需考察样本集D所有可能的簇划分，这是一个NP难问题。所有k-means采用了贪心策略，通过迭代优化来近似求解。

从D中随机选择k个样本作为初始均值向量，类别k是人为设定的。

计算各个样本与各个均值向量的距离，根据距离最近的均值向量确定样本的簇标记，并化入相应的簇。

更新均值向量，如果新的均值向量不等于之前的均值向量，则更新均值向量，否则保持不变。

重复2~3，直到当前均值向量均未更新，得到最终的簇划分。

Random forest原理

是Bagging的一个扩展变体。以决策树为基学习器。在决策树的训练过程中引入了随机属性选择。

假如m个训练样本，自助采样一个训练集

当每个样本有d个属性，在决策树的每个节点需要分裂时，随机从这d个属性中选取出k个属性，满足条件k << d。推荐值$k = log_{2}d$ ，再从这个k个属性值中采取某种策略（比如说信息增益）来选择一个属性作为该节点的分裂属性。

决策树形成过程的每个节点都要按照步骤2来分裂，一直到不能够再分裂位置。整个决策树形成过程没有剪枝。

按照步骤1~3建立大量的决策树，这样就构成了随机森林。

DBSCAN推导

全称为“Density-Based Spatial Clustering of Applications with Noise”，属于密度聚类。此类算法假设聚类结构能通过样本分布的紧密程度确定。
定义下面几个概念：

$\epsilon$-邻域：对$x{j} \in D$，其$\epsilon$邻域包含样本集D中与$x{j}$的距离不大于$\epsilon$的样本，即$N\epsilon (x{j}) = {x{i}\in D | dist(x{i}, x_{j})\leqslant \epsilon}$
核心对象：若$x{j}$的$\epsilon$-邻域至少包含MinPts个样本，这$x{j}$是一个核心对象。
密度直达：若$x{j}$位于$x{i}$的$\epsilon$-邻域中，且$x{i}$是核心对象，则称$x{j}$由$x_{i}$密度直达。
密度可达：对$x{i}$与$x{j}$，若存在样本序列$p{1},p{2},…,p{n}$，其中$p{1} = x{i}$, $p{n} = x{j}$且$p{i+1}$由$p{i}$密度直达，则称$x{j}$由$x_{i}$密度可达。

“簇”定义为：由密度可达关系导出的最大密度相连样本集合。

EM算法推导

LR和SVM的异同

相同点：

LR和SVM都是分类算法
如果不考虑核函数，他们的决策面都是线性的。
LR和SVM都是监督学习算法
LR和SVM都是判别模型
LR和SVM在学术界都广为认知并且应用广泛

不同点：

本质上其loss function不同。不同的loss function代表不同的前提假设，也就代表不同的分类原理。简单来说，逻辑回归方法是基于概率理论，假设样本为1的概率可以用sigmoid函数来表示，然后通过极大似然的方法可以估计出参数的值。支持向量则是基于几何间隔最大的原理，认为存在最大几何间隔的分类为最优分类面。
支持向量只考虑局部边界线附近的点，而逻辑回归考虑全局。从这一点可以得知：线性SVM不直接依赖于数据分布，分类平面不受一类点影响；LR则受所有数据点的影响，如果数据不同类别strongly unbalance，一般需要先对数据做balancing。
在解决非线性问题时，支持向量机采用核函数的机制，而LR通常不采用核函数的方法。这个问题理解起来非常简单。分类模型的结果就是计算决策面，模型训练的过程就是决策面的计算过程。通过上面的第二点可以了解，在计算决策面时，SVM算法里只有少数几个代表支持向量的样本参与计算，也就是只有少数几个样本需要参与核计算（即keranal machine解的系数是稀疏的）。然而，LR算法里，每个样本点都必须参与决策面的计算过程，也就是说，假设在LR里也运用核函数的原理，那么每个样本点都必须参与核计算，这带来的计算复杂度是相当高的。所以，在具体应用时，LR很少运用核函数机制。
线性SVM依赖数据表达的距离测量，所以需要对数据先做normalization，LR不受其影响。
SVM的损失函数自带正则项，这就是问什么SVM是结构风险最小化算法的原因。而LR必须在损失函数上添加正则项。

HMM和CRF区别

HMM是生成模型，CRF是判别模型
HMM是概率有向图，CRF是概率无向图
HMM求解过程可能是局部最优，CRF可以全局最优
CRF概率归一化比较合理，HMM则会导致label bias问题

参考链接：
条件随机场（CRF）和隐马尔科夫模型（HMM）最大区别在哪里？CRF的全局最优体现在哪里？
如何用简单易懂的例子解释条件随机场（CRF）模型？它和HMM有什么区别？

集成学习介绍(boosting、bagging、stacking原理)

集成学习器通过构建并结合多个学习器（弱学习器）来完成学习任务，常可获得比单一学习器显著优越的泛化性能。
主要集成学习方法可以分为两大类：

1
2

个体学习器之间存在强依赖关系，必须串行生成序列化方法。(Boosting)
个体学习器间不存在强依赖关系，可同时生成的并行化算法。(Bagging和Random Forest)

Boosting
先从初始训练集训练出一个基学习器，再根据基学习器的表现对样本分布进行调整，使得先前基学习做错的训练样本在后续受到更多的关注，然后基于调整后的样本分布来训练下一个基学习器；如此反复进行，直到基学习器数目达到事先指定的值T，最终将这个T个基学习器进行加权组合。

Bagging
基于自助采样法（booststrap sampling）。
采样出T个含m个训练样本的采样集，然后基于每个采样集训练出一个基学习器，在将这些基学习器进行结合。结合时分类任务常使用简单投票法，回归任务使用简单平均法。

Stacking
Stacking其实是一种结合策略（本身也是一种著名的集成学习算法），即基学习器的结合策略。把个体学习器成为初级学习器，用于结合的学习器称为次级学习器或元学习器。
Stacking先从初始数据集训练出初级学习器，然后生成一个新的数据集用于训练次级学习器，初级学习器的输出被当做样例特征，而初始样本的标记仍被当作样例标记。
使用交叉验证或者留一法，用初级学习器为使用的样本来产生次级学习器的训练样本。
次级学习算法一般使用多响应线性回归效果较好。

随机梯度下降法和牛顿法的区别和定义

随机梯度下降是使用的一阶导，实现简单。当目标函数是凸函数时，梯度下降法的解是全局最优解，一般情况下，其解不保证是全局最优解。收敛速度未必是很快的。
牛顿法和拟牛顿法有收敛速度快的优点。需要求解目标函数的海赛矩阵的逆矩阵，计算比较复杂。拟牛顿法通过正定矩阵近似海赛矩阵的逆矩阵或海赛矩阵，简化了这一计算过程。
主要是使用二阶导数。

xgboost原理，怎么防止过拟合

XGBoost可以看做是对GradientBoost的优化。其原理还是基于GradientBoost，创新之处是用了二阶导数和正则项。

SVM与感知机的区别

GBDT推导

包含两个概念：GB(Gradient Boosting)和DT(Decision Tree)。因此，GBDT使用的弱分类器就是Decision Tree，而融合的方法叫做Gradient Boosting。
Gradient Boosting是一个Boosting框架，将梯度下降的思想引入Boosting算法，能处理不同的损失函数，较为实用。
本质是，每一次建立模型是在之前建立模型损失函数的梯度下降方向。

L1 L2正则化的区别

正则化定义：对学习算法的修改，旨在减少泛化误差而不是训练误差。
L2正则化是各个参数的平方和。
L1正则化时各个参数的绝对值之和。
相同点

都是用于避免过拟合

不同点：

L1可以让一部分特征的系数缩小到0，从而间接实现特征选择。所以L1适用于特征之间有关联的情况。L2让所有特征的系数都缩小，但是不会减为0，它会使优化求解稳定快速。所以L2适用于特征之间没有关联的情况。

常见的激活函数有哪些

加入激活函数是用来加入非线性因素的，解决线性模型所不能解决的问题。
(1) sigmoid
函数表达式：$f(x) = \frac {1}{1 + e^{-x}}$
存在梯度消失、不是关于原点对称、计算exp比较耗时等问题
(2) tanh
函数表达式：$f(x) =\frac {e^{x} - e^{-x}}{e^{x} + e^{-x}} =\frac{1 - e^{-2x}}{1 + e^{-2x}}$
收敛速度比sigmoid快
解决了原点对称问题，但是梯度弥散没有解决
(3) ReLU
函数表达式：$ f(x) = max(0, x)$
能够有效缓解梯度消失问题。
提供神经网络的稀疏表达能力。
ReLU在$x < 0$时，权重无法更新，会导致“神经元死亡”。
(4) Leaky-ReLu
函数表达式：

$f(x) = ax (x < 0)$ $f(x) = x (x >= 0)$

(5) PReLU(parametric ReLU)
对于Leaky ReLU中的 $\alpha$ 作为一个参数进行训练。
如何选择
首先尝试ReLU

凸函数的定义，sigmoid是凸函数吗

对区间[a, b]上定义的函数f ，若它对区间中任意两点$x1,x2$均有$f(\frac{x1+x2}{2}\leq \frac{f(x1)+f(x2)}{2})$，则称$f$为区间[a, b]上的凸函数。对实数集上的函数，可以通过求二阶导数来判别，若二阶导数在区间上非负，则称为凸函数，若二阶导数在区间上恒大于0，则称为严格凸函数。

sigmoid不是凸函数，没有全局最小值。

softmax与cross entropy区别

Softmax函数，或称归一化指数函数，将一个含任意实数的K维向量$z$压缩到另一个k维实向量$softmax(z)$，使得每一个元素的范围都在(0, 1)之间，并且所有元素的和为1。

$S_{i} = \frac{e^i}{\sum_{j}{}e^j}$

主要应用于基于概率的多分类问题。

cross entropy为交叉熵代价函数。具体形式如下

$l(\hat y, y) = - \sum_{i=1}^{C}y^(i)log(\hat y^{(i)})$

所以，这两个是不同的，但是经常联合起来使用。在softmax + 交叉熵组合的情况下，导数的形式非常简洁。

Adam算法

Adam是一种学习率自适应的优化算法。

步长$\epsilon$(建议默认为0.001)
矩估计的指数衰减速率，$\rho{1}$和$\rho{2}$在区间[0, 1)内。(建议默认分别为0.9和0.999)
用于数值稳定的小常数$\delta$(建议默认为：$10^{-8}$)
初始参数$\theta$
初始化一阶和二阶矩变量$s = 0, r= 0$
初始化时间步t = 0
从训练集中采包含$m$个样本{$x^{(1)}, x^{(2)},…,x^{(m)}$}的小批量，对于目标为$y^{(i)}$
计算梯度： $g = \frac{1}{m}\bigtriangledown _{\theta}\sum_{i}L(f(x^{(i)};\theta), y^{(i)})$ 更新有偏一阶矩估计： $s = \rho_{1}s + (1-\rho_{1})g$ 更新有偏二阶矩估计： $r = \rho_{2}r + (1-\rho_{2})g\odot g$ 修正一阶矩的偏差： $\hat s \leftarrow \frac{s}{1-\rho_{1}^t}$ 修正二阶矩的偏差： $\hat r \leftarrow \frac{r}{1-\rho_{1}^t}$ 计算更新： $\bigtriangledown_{\theta} = -\epsilon\frac{\hat s}{\sqrt{\hat r}+\delta}$ 应用更新： $\theta \leftarrow \theta + \bigtriangledown_{\theta}$

反向传播，梯度检验怎么做？

对于一个函数来说，通常有两种计算梯度的方式：

数值梯度
解析梯度
神经网络算法使用反向传播计算目标函数关于每个参数的梯度，由于神经网络中函数都是可导的，所以求的是解析梯度。由于计算过程中涉及到的参数很多，反向传播计算的梯度很容易出现误差。

为了确认代码中反向传播计算的梯度是否正确，可以采用梯度检验(gradient check)的方法。通过计算数值梯度，得到梯度的近似值，然后和反向传播算法进行比较，若两者相差很小的话则证明反向传播的代码是正确的。
数值梯度：

$\frac{d}{d\theta}J(\theta) = \frac{J(\theta + \epsilon ) - J(\theta + \epsilon )}{2\epsilon}$

$epsilon$是一个很小的值，比如$10^{(-4)}$。
所以我们可以通过计算损失函数的数值梯度来检验解析梯度，如果二者很接近的话，则验证解析方法得到的梯度是正确的。

为什么引入非线性激励函数

对于线性函数，其实相当于$f(x) = x$，那么在线性激活函数下，每一层相当于用一个矩阵去乘以x，那么多层就是反复的用矩阵去乘以输入，根据矩阵的乘法法则，多个矩阵相乘得到一个大矩阵，所以线性激励函数下，多层网络与一层网络是一样的。
非线性变化是深度学习有效的原因之一。原因在于非线性相当于对空间进行变换，变换完成后相当于对问题空间进行简化，原来线性不可解的问题现在变得可解了。

非线性激励函数可以逼近任意函数，最早的想法是sigmoid函数或者tanh函数，含有一定的生物解释。

什么样的数据集不适合用深度学习

(1) 数据集太小，数据样本不足时，深度学习相对于其他机器学习算法，没有明显优势。
(2) 数据集没有局部相关特性，目前深度学习表现好的领域主要是图像、语音、自然语言处理等领域，这些领域的一个共性是局部相关性。图像中像素组成物体，语音信号中音位组合成单词，文本数据中单词组合成句子，这些特征元素一旦被打乱，表示的含义同时也被改变。对于没有这样的局部相关性的数据集，不适合使用深度学习算法进行处理。
举个例子：预测一个人的健康状况，相关的特征会有年龄、职业、收入、家庭状况等，将这些元素打乱，并不会影响相关的结果。

CNN最早成功应用在CV，为什么NLP和Speech里面很多问题也可以用CNN，为什么AlphaGo里面也用了CNN，这些问题的相似性在哪里，CNN通过什么手段抓住了这个共性。

以上几个不相关问题的相关性在于，都存在局部与整体的关系，由低层次的特征经过组合，组成高层次的特征，并且得到不同特征之间的空间相关性。
CNN抓住此共性的手段主要有四个：局部连接、权值共享、池化操作、多层次结构
局部连接使网络可以提取数据的局部特征，权值共享大大降低了网络的训练难度，一个Filter只提取一个特征，在这个图片（或者语音/文本）中进行卷积，池化操作与多层次结构一起，实现了数据的降维。将低层次的局部特征组合成为较高层次的特征，从而对整个图片进行表示。

神经网络中激活函数的真正意义，一个激活函数需要具有哪些必要的属性，还有哪些属性是好的属性但不必要的。

(1) 非线性：即导数不是常数。这个条件是多层神经网络的基础，保证多层网络不会退化成单层线性网络。这也是激活函数的意义所在。
(2) 几乎处处可微：可微性保证了在优化中梯度的可计算性。对于SGD算法来说，由于几乎不可能收敛到梯度接近零的位置，有限的不可微点对于优化结果不会有很大影响。
(3) 计算简单：非线性函数有很多。激活函数在神经网络前向的计算次数与神经元个数成正比，因此简单的非线性函数自然更适合用作激活函数。这也是ReLU之流比其他使用exp操作的激活函数更受欢迎的其中一个原因。
(4) 非饱和性：饱和指的是在某些区间梯度解决于零（即梯度消失），使得参数无法继续更新的问题。典型的例子就是Sigmoid，它的导数在x为比较大的正值和比较小的负值时都会接近于0。
(5) 单调性：即导数符号不变。单调性使得激活函数处的梯度方向不会经常发生改变，从而让训练变得更容易。
(6) 参数少：大部分激活函数都是没有参数的。
(7) 归一化：这是最近才出来的概率，对应的激活函数是SELU，主要思想是使样本分布自动归一化到零均值、单位方差的分布，从而稳定训练。在这之前，这种归一化思想也被用于网络结构的设计，比如Batch Normalization。

为什么实现分类的CNN中需要进行Max-pooling

Max-pooling可以将特征维度变小，使得减小计算时间，同时，不会损失太多重要的信息，因为我们是保存最大值，这个最大值可以理解为该窗口下的最重要信息。同时Max-pooling也对CNN具有平移不变性提供了很多理论支撑。

RNN为什么会梯度消失，LSTM是怎么避免梯度消失的

可以参考我的另一博客吴恩达序列模型：循环序列模型

nlp中未登录词怎么处理

未登录词就是未在词表中出现的词。可以使用标记表示未登录词，在表示词向量时，可以将未登录词进行标准初始化。