面试-NLP八股文_算法面试八股文

机器学习

• 交叉熵损失：$L=-(ylog(\hat{y})+(1-y)log(1-(\hat{y}))$
• 均方误差：$L=\frac{1}{n}\sum _{i=1}^n(y_i-{\hat{y}}_i{)}^2$
• BPR损失：$L={\sum }_{(u,i,j)\in O}-ln\sigma ({\hat{y}}_{ui}-{\hat{y}}_{uj})$
• Info loss：$L=-log\frac{exp(q\cdot k_{+}/\tau )}{{\sum }_{j=1}^{N}exp(q\cdot k_j/\tau )}$
• 最大似然估计：是一种在给定结果的情况下，使得选择的参数值观测到该结果的概率最大
• 交叉熵：衡量两个概率分布p和q之间差异的指标；最大化似然函数等价于最小化交叉熵
• LR和SVM的异同
  • LR是逻辑回归模型，在最后的结果上应用了sigmoid函数得到分布概率
  • SVM是为了寻找一个最优超平面，使得训练样本离该超平面的间隔最大化
  • 高斯核函数的核心思想是将样本数据进行升维，从而使得原本线性不可分的数据线性可分，$k_i=\exp (-\frac{(x_i-\mu {)}^2}{2{\sigma }^2})$
  • 同：
    • LR和SVM都可以处理分类问题，且一般都用于处理线性二分类问题
    • 两个方法都可以增加不同的正则化项，如L1、L2正则化
    • LR和SVM都可以用来做非线性分类，只要加核函数就好
  • 异：
    • LR是参数模型，SVM是非参数模型
    • 逻辑回归采用的是cross-entropy loss，SVM采用的是hinge loss
    • SVM分类只需要计算与少数几个支持向量的距离，而LR和所有点都有关系
• L1L2的特点
  • 正则化是防止模型在训练数据上过度拟合的技术，即通过在模型的损失函数中引入额外的惩罚项，来对模型的参数进行约束，从而降低模型的复杂度（使数值变小）
  • L1是权重参数的绝对值之和
  • L2是权重参数的平方，L2正则化又称为权重衰减
• dropout在训练过程中随机将部分神经元权重置为零
• Layer Normalization与Batch Normalization
  • 归一化是把数据特征映射到固定范围，以避免由于输入特征尺度存在较大差异，而使模型的优化方向可能会被尺度较大的特征所主导
  • BN层(Batch Normalization)：是在不同样本之间进行归一化
  • LN层(Layer Normalization)：是在同一样本内部进行归一化
• 如何缓解梯度消失问题
  • 梯度趋近于零，网络权重无法更新或更新的很微小，网络训练再久也不会有效果
  • 解决办法：选择合适的激活函数；批量归一化；使用残差网络
• 如何缓解梯度爆炸问题
  • 梯度呈指数级增长，变的非常大，然后导致网络权重的大幅更新，使网络变得不稳定
  • 解决办法：选择合适的权重初始化（Xavier或He）;梯度裁剪
• 防止过拟合的手段(训练时效果好，测试时效果拉)
  • 增加训练数据量，或数据增强
  • 简化模型结构
  • 早停策略
  • Dropout技术
  • 正则化方法
• Adam算法能够根据不同参数的梯度特性自适应地调整学习率。对于梯度较大的参数，学习率会相应减小，以避免参数更新过快导致震荡；对于梯度较小的参数，学习率会相应增大，以加速收敛。Adam优化器是由Momentum动量梯度与RMSProp算法构成
• 交叉验证：其基本思想是将数据分为K个互不重叠的子集（通常称为“折”），每次选取其中K-1个子集作为训练集，剩下的一个子集作为测试集，进行模型训练和评估。这个过程会重复K次，每次选择不同的子集作为测试集，最后将所有的测试结果求平均值。
• KNN是根据某一样本点距离最近的 K 个样本点的类别来判断该样本属于哪个类别（多数投票）
• K-means是无监督学习算法。根据输入无标签的数据，然后将数据聚类成不同的组。做法：随机初始化质心->计算每个数据点到每个质心的距离->根据距离将数据点到簇->重新计算簇的质心，重复这一过程直到质心不再变化或达到预定的迭代次数。
• 决策树是一种树形结构，主要用于分类，易过拟合，需要剪枝算法
• 随机森林是将多个决策树结合在一起，每次数据集是随机有放回的选出，而选出部分特征作为输入，最后将多个树的结果整合起来当作最后的结果输出。
• 归一化（Normalization）是将一列数据变化到某个固定区间(范围)中，通常，这个区间是[0, 1] 或者（-1,1）之间的小数
• 标准化（Standardization）是原始数据减均值之后，再除以标准差。将数据变换为均值为0，标准差为1的分布

深度学习

• Embedding技术是将单词转换为固定长度的向量

  • 作用（独热编码相比）：可以解决维度灾难，即独热编码（One-hot ）导致的维度激增；解决词汇鸿沟，即独热编码不能表达词汇之间的联系
  • 基于内容的word2vec方法是最经典的，其中包含框架CBOW连续词袋模型（Continuous Bag of Words）和Skip-gram跳字模型

    • CBOW预设好窗口大小，利用窗口内的上下文来预测目标词。

      • 模型输入是上下文词汇的One-hot编码；经过Embedding层，即词汇编码各自和嵌入矩阵相乘，得到词向量；然后计算上下文词向量的平均值；再输入线性层，得到输出向量；输入softmax层得到概率分布，最大概率位置对应的词即为预测结果；
      • 

    • Skip-gram跳字模型为CBOW的逆过程

      • 模型输入是目标词的独热编码向量；经过in嵌入层，得到隐藏层；再经过out嵌入层得到输出向量；输入softmax层得到字典中每个词汇是目标词上下文的概率
      • 

• 文本关键词抽取

  • textrank把文本拆分成词汇作为图节点， 然后对节点权重进行倒序排列，得到排名前TopN个词汇作为文本关键词
    • 节点间权重计算方式：两个节点之间仅当它们对应的词汇在长度为K的窗口中共现则存在边，K表示窗口大小即最多共现K个词汇
  • tf-idf
    • 词频（Term Frequency，TF）指某一给定词语在当前文件中出现的频率。$词频(TF)=\frac{词w在文档中出现的次数}{文档的总词数}$
    • 逆向文件频率（Inverse Document Frequency，IDF）是一个词语普遍重要性的度量。即如果一个词语只在很少的文件中出现，表示更能代表文件的主旨，它的权重也就越大；如果一个词在大量文件中都出现，表示不清楚代表什么内容，它的权重就应该小。$逆文档频率(IDF)=log(\frac{语料库的文档总数}{包含词w的文档数+1})$
    • 关键字抽取方式：计算所有词的TF-IDF=TF*IDF，对计算结果进行倒序排列，得到排名前TopN个词汇作为文本关键词

• CNN有卷积核，池化层，线性层。计算公式：$N=\frac{W-F+2P}{S}+1$

• RNN模型（处理序列数据）

  • 存在长期依赖缺失的问题：在处理长时间问题时，由于梯度消失造成的较远信息对此时几乎不产生影响
  • 长短期神经网络LSTM和门控循环单元GRU可以解决长距离依赖缺失问题
  • LSTM有遗忘门（决定遗忘的信息），更新门（更新细胞状态），输出门（由隐藏表示，输入变量，细胞状态决定）
  • GRU是在LSTM的基础上提出的，与LSTM相比取消了细胞状态向量，只有输出门和更新门（可同时可以进行遗忘和更新），简化了LSTM的结构并提高其计算效率。

• Transformer模型是基于自注意力机制的深度神经网络模型，提高了计算效率，并更好地捕捉长距离依赖关系

  • Positional Encoding： 区分单、双数，利用正、余弦函数进行位置编码
  • Multi-Head Attention：多头注意力机制是一种扩展自注意力机制的方法，它将自注意力机制分解为多个“头”，每个“头”都在不同的表示空间中学习信息，从而能够捕捉到更丰富的特征和关系，保证了可以学习到一个词的多个语义
    • $Attention(Q,K,V)=Softmax(\frac{Q{K}^T}{\sqrt{d_k}})V$
    • $\frac{\ast }{\sqrt{d_k}}$：首先要除以一个数，防止输入softmax的值过大，导致偏导数趋近于0；其次选择根号d_k是因为可以使得q*k的结果满足期望为0，方差为1的分布。
    • 掩码操作Mask： 包含Padding Mask和Sequence Mask两种。掩码就是让矩阵某些元素变为负无穷的数，使得其在后续Softmax中的概率为0。其中Padding Mask旨在消除输入序列中Padding的影响；而Sequence Mask只存在于解码器中，目的是在预测下一个词时，覆盖住后面的词汇注意力信息，达到只用前面序列来预测下一词的目的
  • FFN模块是为了增加模型的非线性能力（因为内部使用的激活函数）
  • NLP中Layer Normalization针对句内每个单词归一，Batch Normalization针对batch内同一位置单词的不同特征归一

• 模型的评价指标

  • TP（true positive-真阳性）：表示样本的真实类别为正，最后预测得到的结果也为正；FP（false positive-假阳性）：表示样本的真实类别为负，最后预测得到的结果却为正；FN（false negative-假阴性）：表示样本的真实类别为正，最后预测得到的结果却为负；TN（true negative-真阴性）：表示样本的真实类别为负，最后预测得到的结果也为负
  • 准确率表示预测正确的样本数占总样本书的比例。$Accuracy=\frac{TP+TN}{TP+TN+FP+FN}$
  • 精确率表示预测为正样本的样本中，正确预测为正样本的概率。$Precision=\frac{TP}{TP+FP}$
  • 召回率表示正确预测出正样本占实际正样本的概率。$Recall=\frac{TP}{TP+FN}$
  • F1 score折中了召回率与精确率。$F1=2\ast \frac{Recall\ast Precision}{Recall+Precision}$
  • HR （命中率-Hits Ratio）预测正确的用户占所有用户的比例，强调预测的“准确性”。$HR=\frac{1}{N}\sum _{i=1}^{N}hits(i)$
  • MRR （平均倒数排名-Mean Reciprocal Rank）表示待推荐的项目是否放在了用户更显眼的位置，强调“顺序性”。$MRR=\frac{1}{N}\sum _{i=1}^N\frac{1}{p_i}$，$p_i$表示第 i 个用户的真实访问值在推荐列表的位置
  • NDCG（归一化折损累计增益-Normalized Discounted Cumulative Gain）用于判断对于一个用户，返回的推荐item列表是否更好
    • Gain：一个列表中所有item的相关性分数。$Gain=rel(i)$
    • Cumulative Gain: 表示对K个item的Gain进行累加（没有考虑顺序）。$C{G}_k=\sum _{i=1}^{k}rel(i)$
    • Discounted Cumulative Gain：考虑排序顺序的因素，使得排名靠前的item增益更高，对排名靠后的item进行折损。$DC{G}_k=\sum _{i=1}^k\frac{rel(i)}{lo{g}_2(i+1)}$
    • IDGC(ideal DCG)：理想的DCG，IDCG的依据是：是根据rel(i)降序排列，即排列到最好状态。算出最好排列的DCG，就是IDCG。$NDCG=\frac{DCG}{IDCG}$

• 残差结构及意义：在结果上加输入，防止梯度消失和网络退化

• Bert是由多个Transformer Encoder一层一层地堆叠起来

  • Embedding由三种Embedding求和而成
    • Token Embeddings：针对单词，会在开头加入CLS，结尾加入SEP
    • Segment Embeddings：区别两种句子，前句赋0，后句赋1
    • Position Embeddings：针对位置，不同于Transformer使用正余弦函数，bert随机初始化位置嵌入。前者只能标记位置，后者不仅可以标记位置，还可以学习到这个位置有什么用。
  • 长度限制为512

简单代码

• 数据结构里面的算法，手撕就好（例如：—句话说快排）
• 每一个数有一个概率，要求写一个随机数发生器，使随机数产生概率符合要求
• 最大子矩形面积，(记得是leetcode原题，大家可以去看一下)
• 判断数独是否是有效数独(行、列、每个3*3矩阵判断)
• 矩阵中正方形最大面积
• 2D接雨水