Machine Learning 面试题

关于机器学习笔试面试的题：

1. 判别式模型 & 生成式模型

   • 判别式模型（Discriminative Model）是直接对条件概率p(y|x;θ)建模。如：线性回归模型、线性判别分析、支持向量机SVM、神经网络等
   • 生成式模型（Generative Model）则会对x和y的联合分布p(x,y)建模，然后通过贝叶斯公式来求得p(yi|x)，然后选取使得p(yi|x)最大的yi。如：隐马尔可夫模型HMM、朴素贝叶斯模型、高斯混合模型GMM、狄利克雷分布模型（Latent Dirichlet Allocation，LDA）等。

2. 激活函数
   sigmoid 函数映射之后取值范围为（0，1）
   tanh函数映射之后取值范围（-1，1）
   Relu函数映射之后取值范围（0，..）大于等于0

3. A,B,C 三个矩阵尺寸分别为 m∗n，n∗p，p∗q，且 $m < n < p < q$, 计算效率最高的是 (AB)C

4. 在统计模式识分类问题中，当先验概率未知时，可以使用 N-P判决和最小最大损失。
   在贝叶斯决策中，对于先验概率p(y)，分为已知和未知两种情况。

   • p(y)已知，直接使用贝叶斯公式求后验概率即可；
   • p(y)未知，可以使用聂曼-皮尔逊决策(N-P决策)来计算决策面。
     而最大最小损失规则主要就是使用解决最小损失规则时先验概率未知或难以计算的问题的。

5. 路径规划

   • A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。 公式表示为： f(n)=g(n)+h(n), 其中 f(n) 是从初始点经由节点n到目标点的估价函数， g(n) 是在状态空间中从初始节点到n节点的实际代价， h(n) 是从n到目标节点最佳路径的估计代价。 保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取： 估价值 h(n)\<= n 到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。 如果 估价值>实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
   • Dijkstra算法 戴克斯特拉算法（英语：Dijkstra’s algorithm，又译迪杰斯特拉算法）由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年提出。戴克斯特拉算法使用了广度优先搜索解决赋权有向图的单源最短路径问题。该算法存在很多变体；戴克斯特拉的原始版本找到两个顶点之间的最短路径，但是更常见的变体固定了一个顶点作为源节点然后找到该顶点到图中所有其它节点的最短路径，产生一个最短路径树。

6. K-Means算法事先确定常数K，常数K意味着最终的聚类类别数，首先随机选定初始点为质心，并通过计算每一个样本与质心之间的相似度(这里为欧式距离)，将样本点归到最相似的类中，接着，重新计算每个类的质心(即为类中心)，重复这样的过程，知道质心不再改变，最终就确定了每个样本所属的类别以及每个类的质心。由于每次都要计算所有的样本与每一个质心之间的相似度，故在大规模的数据集上，K-Means算法的收敛速度比较慢。

7. 特征提取算法分为特征选择和特征抽取两大类

   • 特征选择。常采用特征选择方法。常见的六种特征选择方法：

     • DF(Document Frequency) 文档频率
       DF:统计特征词出现的文档数量，用来衡量某个特征词的重要性

     • MI(Mutual Information) 互信息法
       互信息法用于衡量特征词与文档类别直接的信息量。
       如果某个特征词的频率很低，那么互信息得分就会很大，因此互信息法倾向”低频”的特征词。
       相对的词频很高的词，得分就会变低，如果这词携带了很高的信息量，互信息法就会变得低效。

     • (Information Gain) 信息增益法
       通过某个特征词的缺失与存在的两种情况下，语料中前后信息的增加，衡量某个特征词的重要性。

     • CHI(Chi-square) 卡方检验法
       利用了统计学中的”假设检验”的基本思想：首先假设特征词与类别直接是不相关的
       如果利用CHI分布计算出的检验值偏离阈值越大，那么更有信心否定原假设，接受原假设的备则假设：特征词与类别有着很高的关联度。
       卡方检验（χ2 test），是一种常用的特征选择方法，尤其是在生物和金融领域。χ2 用来描述两个事件的独立性或者说描述实际观察值与期望值的偏离程度。χ2值越大，则表明实际观察值与期望值偏离越大，也说明两个事件的相互独立性越弱。

     • WLLR(Weighted Log Likelihood Ration)加权对数似然

     • WFO（Weighted Frequency and Odds）加权频率和可能性

     • 期望交叉熵，以文本分类为例子，期望交叉熵用来度量一个词对于整体的重要程度

   • 特征抽取（降维）
     PCA, SVD等

   • 在ID3决策树中，也使用信息增益作为特征选择的方法，在C4.5决策树中，使用信息增益比作为特征选择的方法，在CART中，使用基尼指数作为特征选择的方法

8. Naive Bayes是一种特殊的Bayes分类器,特征变量是X,类别标签是C,它的一个假定是特征变量X的各个维度是类别条件独立随机变量。

9. tp = true positive, tn = true negative, fp = false positive, fn = false negative

   • Precision= tp / (tp + fp)
   • Recall = tp / (tp + fn)

10. 解决隐马模型中预测问题的算法是维特比算法。

    • 前向、后向算法解决的是一个评估问题，即给定一个模型，求某特定观测序列的概率，用于评估该序列最匹配的模型。
    • Baum-Welch算法解决的是一个模型训练问题，即参数估计，是一种无监督的训练方法，主要通过EM迭代实现；
    • 维特比算法解决的是给定 一个模型和某个特定的输出序列，求最可能产生这个输出的状态序列。如通过海藻变化（输出序列）来观测天气（状态序列），是预测问题，通信中的解码问题。

11. N-gram是一种简单有效的统计语言模型，通常n采用1-3之间的值，它们分别称为unigram、bigram和trigram。现有给定训练语料合计三个文档如下：
    D1： John read Moby Dick
    D2： Mary read a different book,
    D3： She read a book by Cher
    利用bigram求出句子“John read a book”的概率大约是0.06

    2-gram公式

    $$P(s1,s2,s3...) = P(s1)*P(s2|s1)*P(s3|s2).....$$

    解：
    john在文章开头的概率：P（john） = 1/3
    P（read | John） = 1
    P(a|read) = 2/3
    P(book|a) = 1/2
    P(尾巴|book) = 1/2, book出现两次，其中一次是在句子结尾处
    P(“John read a book”) = $1/3*1*2/3*1/2*1/2 = 1/18 ≈ 0.06$

12. 如果假设h在n=65的独立抽取样本上出现r=10个错误，真实的错误率的90%的置信区间（双侧的）是0.16±0.073。

    $$error_D(h)$$ 的 N% 的置信区间： $$ errors(h) \pm zv \sqrt{\frac{errors(h)(1-erros(h))}{n}}$$

13. 正则化：

    • 正则化可以防止过拟合
    • L1正则化能得到稀疏解
    • L2正则化约束了解空间
    • Dropout也是一种正则化方法

14. 可以用来完成命名实体的任务的算法模型：HMM, CRF, LSTM, seq2seq

    • 基于规则的方法。根据语言学上预定义的规则。但是由于语言结构本身的不确定性，规则的制定上难度较大。
    • 基于统计学的方法。利用统计学找出文本中存在的规律。主要有隐马尔可夫(HMM)、条件随机场(CRF)模型和Viterbi算法、支持向量机（Support Vector Machine, SVM）。
    • 神经网络。 LSTM+CRF模型，基于RNN的seq2seq模型
    • LDA是主题模型，概括文本摘要啥的

15. 激活函数是非线性的，y=2x不可以做激活函数。

16. 朴素贝叶斯定理体现了后验概率 P(y|x) 、先验概率 P(y) 、条件概率 P(x|y)之间的关系：$P(y|x)=P(x|y)·P(y)/P(x)$
    朴素贝叶斯之所以叫“朴素”是因为它假设输入的不同特征之间是独立的。构建朴素贝叶斯分类器的步骤如下：

    • 根据训练样例分别计算每个类别出现的概率P(yi)，
    • 对每个特征属性计算所有划分的条件概率P(xi|yi),
    • 对每个类别计算 $P(X|yi)\*P(yi)$,
    • 选择3步骤中数值最大项作为X的类别yk。

17. resnet-34 和 resnet-50 都是有四组block，每组分别是 3 4 6 3个block，resnet-34 的每个block里面有两个卷积层，resnet-50的每个block里面有三个，另外这两个网络的最开始都有一个单独的卷积层
    (3+4+6+3)*3+1=49

18. 数据挖掘的挖掘方法包括:决策树 、神经网络 、回归 、聚类 、关联规则 、贝叶斯分类

19. 类别不平衡（class-imbanlance）就是指分类问题中不同类别的训练样本相差悬殊的情况，例如正例有900个，而反例只有100个，这个时候我们就需要进行相应的处理来平衡这个问题：

    • 在训练样本较多的类别中进行欠采样
    • 直接基于原数据集进行学习，对预测值进行再缩放处理（weighted loss)
    • 通过对反例中的数据进行插值，来产生额外的反例

20. 置信度计算规则为： 同时购买商品A和商品B的交易次数/购买了商品A的次数
    支持度计算规则为： 同时购买了商品A和商品B的交易次数/总的交易次数
    支持度表示 Support(X→Y) = P(X,Y) / P(I) = P(X∩Y) / P(I) = num(X∩Y) / num(I)
    可信度表示 Confidence(X→Y) = P(Y|X) = P(X,Y) / P(X) = P(X∩Y) / P(X)
    提升度表示 可信度/支持度

21. Adaboost算法的思想是在前一轮识别过程中识别错误的样本会在下一轮中提升权重，而那些识别正确的样本会降低权重。所以不是独立的学习弱分类器。
    AdaBoost模型是弱分类器的线性组合。
    提升树是以分类树或者回归树为基本分类器的提升办法，提升树被认为是统计学习中最有效的办法之一。
    AdaBoost算法的一个解释是该算法实际上是前向分步算法的一个实现，在这个方法里，模型是加法模型，损失函数是指数损失，算法是前向分步算法。

22. 假如使用一个较复杂的脊回归模型 (Ridge Regression)，来拟合样本数据时，通过调整正则化参数λ，来调整模型复杂度。当λ较大时，当λ增大时，偏差增大，方差减小。
    .λ越大，对模型中参数的惩罚力度越大，因此会有更多的参数被训练为0，模型也就变得更加简单了。模型复杂度越低，方差小，但偏差大。

23. CNN常见的Loss函数:softmax_loss, sigmoid_loss, siamese_loss
    在传统的siamese network中一般使用Contrastive Loss作为损失函数，这种损失函数可以有效的处理孪生神经网络中的paired data的关系。参考

24. 优化方法：

    • 批量梯度下降法在每次参数更新时同时迭代所有样本，优点是迭代次数少，并行计算，缺点是在样本规模大时训练缓慢。
    • 随机梯度下降法在每次参数更新时迭代一个样本，优点时在样本规模大时训练快，缺点是迭代次数多，且容易收敛到局部最优解；
    • 牛顿法是一种计算二阶梯度的算法，与梯度下降法相比，收敛速度更快，但计算复杂，每次参数更新都要计算Hession矩阵的逆；
    • 梯度下降法是利用当前位置的负梯度作为搜索方向的方法。
    • 牛顿法和梯度下降法相比，一个劣势是求解复杂，一个优势是收敛速度加快。
    • 共轭梯度法仅需利用一阶导数的信息，但是收敛速度高于梯度下降法

25. AR模型：自回归模型，是一种线性模型
    MA模型：移动平均法模型，其中使用趋势移动平均法建立直线趋势的预测模型
    ARMA模型：自回归滑动平均模型，拟合较高阶模型
    GARCH模型：广义回归模型，对误差的方差建模，适用于波动性的分析和预测

26. spss中交叉分析主要用来检验两个变量之间是否存在关系，或者说是否独立，其零假设为两个变量之间没有关系。在实际工作中，经常用交叉表来分析比例是否相等。例如分析不同的性别对不同的报纸的选择有什么不同。

27. 均值移动（Mean Shift）算法的核心思想是：找到概率密度梯度为零的采样点，并以此作为特征空间聚类的模式点。
    ttps://blog.csdn.net/hjimce/article/details/45718593
    基于核密度估计的爬山算法，基本形式是：
    给d维空间的n个数据点集X，那么对于空间中任一点x的meanshift就可以表示为漂移向量（表示圆心的向量），用sk表示数据集的点到x的距离小于球半径h的数据点集。漂移过程就是不断加入新的点（就是到x距离小于求半径的点），一边更新球圆心x。圆心会向数据集密度最大的地方移动。

28. 随机抽样一致算法（random sample consensus,RANSAC）,采用迭代的方式从一组包含离群的被观测数据中估算出数学模型的参数。
    给定一组（通常很小）的内群，存在一个程序，这个程序可以估算最佳解释或最适用于这一数据模型的参数。
    “内群”数据可以通过几组模型的参数来叙述其分别，而“离群”数据则是不适合模型化的数据。
    数据会受噪声影响，噪声指的是离群，例如从极端的噪声或错误解释有关数据的测量或不正确的假设

29. BatchNorm 层对于 input batch 会统计出 mean 和 variance 用于计算 EMA。如果input batch 的 shape 为(B, C, H, W)，统计出的 mean 和 variance 的 shape 为: 1*C*1*1
    BN 层的目的本就是用于归一化，所以显而易见要保证通道数C不变，其余长宽为0

30. p(w1 | xi) = p(xiw1) / p(xi) = p(xi | w1) p(w1) / p(xi)
    根据贝叶斯定理：P(Y = 1|X = 1) = P(X = 1|Y =1) P(Y = 1)/P(X = 1)
    根据全概率公式：P(X =1) = P(X = 1|Y = 1) P(Y = 1) + P(X = 1|Y = 0) P(Y = 0)

31. 基于核的机器学习算法: Radial Basis Function, Linear Discrimimate Analysis, Support Vector Machine

32. SPSS的界面中，主窗口是数据编辑窗口
    SPSS中，数据整理的功能主要集中在数据和转换等菜单中

33. 假设你需要调整超参数来最小化代价函数（cost function），可使用：穷举搜索，随机搜索，Bayesian优化

34. 假设你有5个大小为7x7、边界值为0的卷积核，同时卷积神经网络第一层的深度为1。此时如果你向这一层传入一个维度为224x224x3的数据，那么神经网络下一层所接收到的数据维度是218x218x5
    (input - kernel_width+1) / step_length

35. 关于支持向量机SVM：
    L2正则项，作用是最大化分类间隔，使得分类器拥有更强的泛化能力
    Hinge 损失函数，作用是最小化经验分类错误
    当参数C越小时，分类间隔越大，分类错误越多，趋于欠学习
    间隔应该是2/||w||才对，向量的模通常指的就是||w||。

36. 随机森林不需要剪枝，因为本来就很大方差，防止过拟合
    GBDT核心在于每一棵树学的是之前所有树的结论和的残差，残差是一个加预测值后能得到真实值得累加量。
    xgboost和GBDT差不多，不过还支持线性分类器
    xgboost可以自定损失函数，速度很快，但是对异常值很敏感。
    SVM的目标是找到使得训练数据尽可能分开且分类间隔最大的超平面，属于结构风险最小化
    Naive Bayes是一种特殊的Bayes分类器，其一个假定是每个变量相互独立。

37. 输入图片大小为200×200，依次经过一层卷积（kernel size 5×5，padding 1，stride 2），pooling（kernel size 3×3，padding 0，stride 1），又一层卷积（kernel size 3×3，padding 1，stride 1）之后，输出特征图大小为97。
    计算尺寸不被整除只在GoogLeNet中遇到过。卷积向下取整，池化向上取整。
    本题 （200-5+2*1）/2+1 为99.5，取99
    （99-3）/1+1 为97
    （97-3+2*1）/1+1 为97
    研究过网络的话看到stride为1的时候，当kernel为 3 padding为1或者kernel为5 padding为2 一看就是卷积前后尺寸不变。
    计算GoogLeNet全过程的尺寸也一样。
    输出尺寸=(输入尺寸-filter尺寸+2*padding）/stride+1

38. 在机器学习中需要划分数据集，常用的划分测试集和训练集的划分方法有:留出法,交叉验证法,自助法
    自助法，又称为自助抽样法

39. 决策树常用三种指标来确定是否继续划分集合：信息增益、信息增益率，基尼指数。
    信息熵：即数据样本的纯度，纯度越高，熵越小。
    信息增益：按照某一特征划分数据集后熵的减少量，选择减少量最多的特征进行划分，但是偏好特征取值较多的特征，常见模型ID3。
    信息增益率：在信息怎亿的基础上除以一个固有值（intrinsic value，和取值数目有关），会对取值数目较多的特征有更多惩罚，偏好取值数较少的特征，常见模型C4.5
    基尼指数：从样本集D中随机抽取两个样本，其类别标记不一致的概率，因此越小越好
    ID3决策树是根据信息增益来划分属性
    C4.5决策树是根据增益率来划分属性
    CART决策树是根据基尼指数来划分属性

40. 分支定界法类似决策树的决策特征，要选择那些具有强可分辨性的少量特征。
    在选用的可分性判据J对特征数目单调不减情况下,用分支定界法做特征选择计算量相对较少
    C_n^d >> n, n为原特征个数，d为要选出来的特征个数

41. 激活函数的特性：

    1. 非线性：
       即导数不是常数。这个条件是多层神经网络的基础，保证多层网络不退化成单层线性网络。这也是激活函数的意义所在。
    2. 几乎处处可微：
       可微性保证了在优化中梯度的可计算性。传统的激活函数如sigmoid等满足处处可微。对于分段线性函数比如ReLU，只满足几乎处处可微（即仅在有限个点处不可微）。对于SGD算法来说，由于几乎不可能收敛到梯度接近零的位置，有限的不可微点对于优化结果不会有很大影响。
    3. 计算简单：
       非线性函数有很多。极端的说，一个多层神经网络也可以作为一个非线性函数，类似于Network In Network中把它当做卷积操作的做法。但激活函数在神经网络前向的计算次数与神经元的个数成正比，因此简单的非线性函数自然更适合用作激活函数。这也是ReLU之流比其它使用Exp等操作的激活函数更受欢迎的其中一个原因。
    4. 非饱和性（saturation）：
       饱和指的是在某些区间梯度接近于零（即梯度消失），使得参数无法继续更新的问题。最经典的例子是Sigmoid，它的导数在x为比较大的正值和比较小的负值时都会接近于0。更极端的例子是阶跃函数，由于它在几乎所有位置的梯度都为0，因此处处饱和，无法作为激活函数。ReLU在x>0时导数恒为1，因此对于再大的正值也不会饱和。但同时对于x<0，其梯度恒为0，这时候它也会出现饱和的现象（在这种情况下通常称为dying ReLU）。Leaky ReLU和PReLU的提出正是为了解决这一问题。
    5. 单调性（monotonic）：
       即导数符号不变。这个性质大部分激活函数都有，除了诸如sin、cos等。个人理解，单调性使得在激活函数处的梯度方向不会经常改变，从而让训练更容易收敛。
    6. 输出范围有限：
       有限的输出范围使得网络对于一些比较大的输入也会比较稳定，这也是为什么早期的激活函数都以此类函数为主，如Sigmoid、TanH。但这导致了前面提到的梯度消失问题，而且强行让每一层的输出限制到固定范围会限制其表达能力。因此现在这类函数仅用于某些需要特定输出范围的场合，比如概率输出（此时loss函数中的log操作能够抵消其梯度消失的影响）、LSTM里的gate函数。
    7. 接近恒等变换（identity）：
       即约等于x。这样的好处是使得输出的幅值不会随着深度的增加而发生显著的增加，从而使网络更为稳定，同时梯度也能够更容易地回传。这个与非线性是有点矛盾的，因此激活函数基本只是部分满足这个条件，比如TanH只在原点附近有线性区（在原点为0且在原点的导数为1），而ReLU只在x>0时为线性。这个性质也让初始化参数范围的推导更为简单。这种恒等变换的性质也被其他一些网络结构设计所借鉴，比如CNN中的ResNet和RNN中的LSTM。
    8. 参数少：
       大部分激活函数都是没有参数的。像PReLU带单个参数会略微增加网络的大小。还有一个例外是Maxout，尽管本身没有参数，但在同样输出通道数下k路Maxout需要的输入通道数是其它函数的k倍，这意味着神经元数目也需要变为k倍；但如果不考虑维持输出通道数的情况下，该激活函数又能将参数个数减少为原来的k倍。
       归一化（normalization）：
       这个是最近才出来的概念，对应的激活函数是SELU，主要思想是使样本分布自动归一化到零均值、单位方差的分布，从而稳定训练。在这之前，这种归一化的思想也被用于网络结构的设计，比如Batch Normalization。

42. HK算法思想很朴实,就是在最小均方误差准则下求得权矢量.
    他相对于感知器算法的优点在于,他适用于线性可分和非线性可分得情况,对于线性可分的情况,给出最优权矢量,对于非线性可分得情况,能够判别出来,以退出迭代过程.

43. 深度学习优化算法

    • Gradient Desent: 梯度下降
      • SGD: 收敛慢，可能在鞍点处震荡，在如何选择学习率上有难点。
    • Momentum: 在SGD上引入动量，加速 SGD 在正确方向的下降并抑制震荡。
      • SGD-M： 在原步长之上，增加了与上一时刻步长相关的优化内容。
    • Nesterov Accelerated Gradient (NAG) :在目标函数有增高趋势之前，减缓更新速率。
    • Adagrad: 引入了二阶动量。其二阶动量的对应分量较大，学习率就较小。这一方法在稀疏数据的场景下表现很好。
    • RMSprop: 只关注最近某一时间窗口内的下降梯度。
    • Adadelta: 不积累所有过去的平方梯度，而是将积累的过去梯度的窗口限制在一定的大小。
    • Adam: RMSprop 和 Momentum 的结合。和 RMSprop 对二阶动量使用指数移动平均类似，Adam 中对一阶动量也是用指数移动平均计算。
    • NAdam: 在 Adam 之上融合了 NAG 的思想。
    • keras实现

44. LDA主题模型

45. RNN, LSTM, GRU

    • LSTM vs. GRU: 遗忘门、更新门和输出门
    • GRU: 重置门和更新门

46. 马尔可夫链
    马尔可夫链是满足马尔可夫性质的随机变量序列X1, X2, X3, …，即给出当前状态，将来状态和过去状态是相互独立的。

47. 受限玻尔兹曼机

48. 关联规则学习
    假设 $I=\{I_{1},I_{2},\ldots ,I_{m}\}$ 是项的集合。给定一个交易数据库 $D=\{t_{1},t_{2},\ldots ,t_{n}\}$，其中每个事务（Transaction）t是I的非空子集，即$t\subseteq I$，每一个交易都与一个唯一的标识符TID（Transaction ID）对应。关联规则是形如$X\Rightarrow Y$的蕴涵式，其中$X,Y\subseteq I$ 且 $X\cap Y=\emptyset$ ，$X$ 和 $Y$ 分别称为关联规则的先导(antecedent或left-hand-side, LHS)和后继(consequent或right-hand-side, RHS) 。关联规则 $X\Rightarrow Y$ 在 $D$中的支持度（support）是D中事务包含 $X\cup Y$ 的百分比，即概率 $P(X\cup Y)$；置信度（confidence）是包含X的事务中同时包含Y的百分比，即条件概率$P\left(Y|X\right)$。如果同时满足最小支持度阈值和最小置信度阈值，则认为关联规则是有趣的。这些阈值由用户或者专家设定。

49. Keras applications
    提供了如 VGG, RESNET, Inceptionv3等网络模型。

50. Keras 损失函数

    • mean squared error
    • mean absolute error
    • hinge
    • categorical crossentropy
    • sparse categorical crossentropy
    • binary crossentropy

51. keras 评估标准

    • binary accuracy
    • categorical accuracy
    • sparse categorical accuracy
    • top-k categorical accuracy
    • sparse top-k categorical accuracy

52. 二叉树遍历：

    • 前序遍历：根结点 —-> 左子树 —-> 右子树
    • 中序遍历：左子树—-> 根结点 —-> 右子树
    • 后序遍历：左子树 —-> 右子树 —-> 根结点
    • 层次遍历：只需按层次遍历即可

53. 神经网络不work：

    • 数据规范化：从数据中减去均值再除以标准差
    • 可视化过程：检查网络是否有效
    • 数据预处理
    • 正则化：
    • 批次大小
    • 学习率
    • 激活函数
    • 不良梯度：relu->leaky relu or elu
    • 初始化网络权重
    • 网络层数
    • 隐神经元个数