实习准备和总结

近两周的实习总结。

2021.10.19更新百度cv部门多模态research岗面经

目前研究内容

自己针对要面试的岗位和目前的研究内容准备咯

模型

BiLSTM 模型

BiLSTM 就是双向的 LSTM 模型。
LSTM 就是一个比较基本的 RNN 模型，每个 LSTM cell 有三个门控，遗忘门、输入门、输出门。分别控制要遗忘的信息多少、对输入信息进行限制以及 cell 的输出控制。它们的权重其实就是输入和上一次的输出 ht 拼接在一起，然后分别乘以权重向量，再通过 sigmoid 激活函数得到。
三个门但是有四个 MLP，因为还有一个是通过上一次的输出和这次的输入计算当前 cell 的输入，用 tanh 激活函数
当前 cell 状态的计算是上一次的单元状态*遗忘门+当前单元状态*输入门
梯度消失：
1. 如果 t-j 很大，也就是 j 距离 t 时间步很远，当时，会产生梯度爆炸问题，时，会产生梯度消失问题。
2. t 是当前时间步，j 是历史时间步，求 loss 损失偏导的时候是累乘的。
写 LSTM 的公式
1. 输入：
2. 输入门控向量：
3. 输出门控向量：
4. 遗忘门控向量：
5. 当前 cell state：
6. 隐藏状态 hidden state：
7. 输出 output：
LSTM 的优缺点
1. 优点：相比简单 RNN 可以记住更长的时间步骤，避免了无休止的连乘，而是边加边乘，一定程度上解决了梯度消失问题
2. 缺点：RNN 的梯度问题在 LSTM 及其变种里面得到了一定程度的解决，但还是不够。它可以处理 100 个量级的序列，而对于 1000 个量级，或者更长的序列则依然会显得很棘手。
3. 缺点 2：计算费时。每一个 LSTM 的 cell 里面都意味着有 4 个全连接层(MLP),如果 LSTM 的时间跨度很大，并且网络又很深，这个计算量会很大，很耗时。
4. 缺点 3：参数量过多就会存在过拟合的风险。

BERT 模型

BERT 主要是使用 transformer 的 encoder 模型堆叠起来。
BERT 的输入
1. 包含了 token embedding、position embedding 还有 segment embedding。
2. token embedding 是模型中关于词最主要的信息
3. segment embedding 是因为 BERT 里面的下一句的预测任务，所以会有两句拼接起来。比如前一句的 segment emebdding 为 1，后一句为 0。句子末尾都有加[SEP]结尾符，两句拼接开头有[CLS]符
4. position embedding 是表示文本不同位置的字/词所携带的语义信息存在差异，可以通过学习得到，也可以通过设置一个跟位置或者时序相关的函数得到，比如设置一个正弦或者余弦函数
特点是 MLM 和 NSP 机制。
1. MLM 就是 Masked Language Model 简单来说就是讲一句话盖住几个词，然后来预测它们。bert 中是将 15%的词 mask 掉，但是这 15%中又分为 80%用 mask 表示、10%随机表示、10%不变。
2. NSP 机制就是预测两句话是不是连续的。bert 在创建输入的时候就是设置 50%为正确的顺序关系，50%是随机语料中提取的。
BERT 相比 LSTM 的优点：
1. 包含词的信息和距离无关：LSTM 相比 RNN 能一定程度解决梯度消失问题，但依然无法解决太长的距离。而 BERT 基于 Transformer 的 encoder，使用多头自注意力，不管当前词和其他词的空间距离有多远，包含其他词的信息不取决于距离，而是取决于两者的相关性，这是 Transformer 的第一个优势
2. 用到后面的词：对于 Transformer 这样的结构来说，在对当前词进行计算的时候，不仅可以用到前面的词，也可以用到后面的词。而 RNN 只能用到前面的词，这并不是个严重的问题，因为这可以通过双向 RNN 来解决。
3. 计算效率：RNN 和 LSTM 都是顺序结构，必须算出一个隐向量才能计算后一个，那么这就意味着隐向量无法同时并行计算，导致计算效率低。而 Transformer 一次输入一整个句子的所有 embedding 计算，不存在这个问题。

Transformer

看博客Attention is all you need
self-attention 的计算
残差连接
输入的 position encoding
多头注意力
Batch Normalization Normalization

word2vec

word2vec 有两种方式，cbow 和 skip gram，前者是用周围词预测中心词，后者是用中心词预测周围词。实现方式上可以使用层次化 softmax 和负采样方式，这样对计算量来说和大规模词表的情况都比较好。
参考博客
负采样：采样的过程需要指定总体的概率分布，根据词的出现频率采样
损失函数：
2. 其中是输出单词，正样本
3. 是它的词向量
4. 是隐藏层输出，在 CBOW 中，，在 Skip-gram 中，就是中心词
5. 是负例采样的集合
6. 所以 skip-gram 的损失就是输入的中心词和整个正样本做 bmm，然后再和所有负采样得到的负样本做 bmm，然后做 logsigmoid，再求 batch 的平均

逻辑回归

SVM

HMM

CRF

Attention 机制

siRNA 那个项目中的 Attention 主要是使用最后一层 LSTM 中的 hidden 向量进行 attention 计算，实验了简单的 dot attention、concat attention 和 general attention 几种方式，最后还是 dot attention 效果最好。
dot attention 是直接 encode output 和 hidden 点乘求和得到权重
concat attention 是 encoder output 和 hidden 拼接后使用一个带有 tanh 激活函数的全连接层处理，然后进行线性变换得到的
general attention 是对 encoder output 进行线性变换后，再与 hidden 进行点乘得到权重。
Transformer 中的 Attention 是 Self Attention，因为是通过对当前层的输入直接得到，因此叫 self attention

GBDT 模型

参考笔记

随机森林

首先，RF 使用了CART 决策树作为弱学习器，这让我们想到了梯度提升树 GBDT。
第二，在使用决策树的基础上，RF 对决策树的建立做了改进，对于普通的决策树，我们会在节点上所有的 n 个样本特征中选择一个最优的特征来做决策树的左右子树划分，但是 RF 通过随机选择节点上的一部分样本特征，这个数字小于 n，假设为，然后在这些随机选择的个样本特征中，选择一个最优的特征来做决策树的左右子树划分。这样进一步增强了模型的泛化能力。
RF 在数据采样上用的 booststrap 采样，即有放回采样。
RF 的主要优点有：
1. 训练可以高度并行化，对于大数据时代的大样本训练速度有优势。个人觉得这是的最主要的优点。
2. 由于可以随机选择决策树节点划分特征，这样在样本特征维度很高的时候，仍然能高效的训练模型。
3. 在训练后，可以给出各个特征对于输出的重要性
4. 由于采用了随机采样，训练出的模型的方差小，泛化能力强。
5. 相对于 Boosting 系列的 Adaboost 和 GBDT， RF 实现比较简单。
6. 对部分特征缺失不敏感。
RF 的主要缺点有：
- 在某些噪音比较大的样本集上，RF 模型容易陷入过拟合。
- 取值划分比较多的特征容易对 RF 的决策产生更大的影响，从而影响拟合的模型的效果。

Bagging 和 Boosting 的区别

偏差—方差
- Boosting：从偏差—方差分解角度看，降低偏差。
- Bagging：从偏差—方差分解角度看，降低方差。
样本选择：
- Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化.而权值是根据上一轮的分类结果进行调整。
- Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。
样例权重：
- Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。
- Bagging：使用均匀取样，每个样例的权重相等
基学习器权重：
- Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重.
- Bagging：所有弱分类器的权重相等.
串、并行计算：
- Boosting：串行，各个及学习器只能顺序生成，因为后一个模型参数需要前一轮模型的结果。
- Bagging：各个预测函数可以并行生成。

XGBoost

和 GBDT 区别和联系：
1. 同样是 CART 回归树
2. 和 GBDT 比较像，GBDT 使用平方误差作为损失函数，选取特征切分点的依据是最小化每个节点的损失函数，GBDT 拟合的是当前模型的残差。单独使用 GBDT 模型容易出现过拟合的现象，因为先前被选取的特征权重较大，留给后面特征的拟合是相对较小的残差。实际应用中会选择 GBDT+LR 的方式做模型训练。
3. GBDT 和 XGBoost 都是逐个添加树，属于 Boosting 算法。因此使用 Additive Traning 方式优化
XGBoost 的优化目标：
1. 除了拟合数据的损失，还有正则化项用于控制模型复杂度。这个正则化项和叶子节点数 T 以及每个叶子大小有关，要让他们尽可能小。
XGBoost 寻找最优节点值：
2. 此时目标函数为：。
3. 其中是第 j 个叶子节点中所有样本在损失函数对当前模型的一阶偏导数的求和。
4. 是二阶偏导数的求和。这个是通过泰勒二阶展开后，计算目标函数的二次项极值得到。
5. 这时候的目标函数是关于和的二次函数。
XGBoost 的分裂：
1. 从第一个节点分裂使用贪心算法，遍历所有特征的所有划分点选出增益最大的点。
2. 为了限制增长可以设置（1）分裂的增益阈值（2）最大深度（3）最小样本权重和（分裂后任意叶子节点值不能低于这个值）防止过拟合。
3. 分裂的增益定义为：，其实就是上一次的损失减去分裂后的损失差值。
加快分裂：
1. 分裂的时候贪心遍历分割点，称为全局扫描法。
2. 当数据量过大导致内存无法一次载入或者在分布式情况下，贪心算法的效率就会变得很低，全局扫描法不再适用。
3. 基于此，XGBoost 提出了一系列加快寻找最佳分裂点的方案：
  1. 特征预排序+缓存：XGBoost 在训练之前，预先对每个特征按照特征值大小进行排序，然后保存为 block 结构，后的迭代中会重复地使用这个结构，使计算量大大减小。
  2. 分位点近似法：对每个特征按照特征值排序后，采用类似分位点选取的方式，仅仅选出常数个特征值作为该特征的候选分割点，在寻找该特征的最佳分割点时，从候选分割点中选出最优的一个。
  3. 并行查找：由于各个特性已预先存储为 block 结构，XGBoost 支持利用多个线程并行地计算每个特征的最佳分割点，这不仅大大提升了结点的分裂速度，也极利于大规模训练集的适应性扩展。
防止过拟合：
1. Shrinkage：每次迭代中对树的每个叶子结点的分数乘上一个缩减权重 η，这可以使得每一棵树的影响力不会太大，留下更大的空间给后面生成的树去优化模型
2. Column subsampling：选取部分特征进行建树。其可分为两种，一种是按层随机采样，在对同一层内每个结点分裂之前，先随机选择一部分特征，然后只需要遍历这部分的特征，来确定最优的分割点。另一种是随机选择特征，则建树前随机选择一部分特征然后分裂就只遍历这些特征。一般情况下前者效果更好。
可并行的近似算法：
1. 对于连续型特征值，当样本数量非常大，该特征取值过多时，遍历所有取值会花费很多时间，且容易过拟合。因此 XGBoost 思想是对特征进行分桶，即找到 l 个划分点，将位于相邻分位点之间的样本分在一个桶中。在遍历该特征的时候，只需要遍历各个分位点，从而计算最优划分。和 LGBM 不一样的地方是，直方图算法是在统计了频次之后找分割点。
2. 从算法伪代码中该流程还可以分为两种，全局的近似是在新生成一棵树之前就对各个特征计算分位点并划分样本，之后在每次分裂过程中都采用近似划分，而局部近似就是在具体的某一次分裂节点的过程中采用近似算法。
缺失值处理：
1. 当样本的第个特征值缺失时，无法利用该特征进行划分时，XGBoost 的想法是将该样本分别划分到左结点和右结点，然后计算其增益，哪个大就划分到哪边。
优点：
1. GBDT 以 CART 为基分类器，XGBoost 还支持线性分类器。
2. 传统的 GBDT 只用到了一阶导数，XGBoost 还用到了二阶导数信息。XGBoost 工具还可以自定义代价函数，只要支持一阶和二阶求导。
3. 代价函数中加入了正则项，控制叶子节点数和叶子节点上的权重。降低了模型的复杂度，防止过拟合。
4. 有 Shrinkage 缩减的特性，在每次迭代完之后可以将叶子节点乘上一个权重，削弱每棵树的影响，让后面有更大的学习空间。
5. column subsampling 特征抽样，防止过拟合减少计算
6. 对缺失值的处理，XGBoost 可以自动学习出它的分裂方向。
7. 支持并行，是在特征粒度上的并行，没有改变 boost 的串行结构。决策树最耗时的是对特征的值排序，而 XGboost 使用了特征预排序，后面就可以在节点分裂的时候对每个特征使用多线程并行计算。
8. 可以并行的近似直方图算法。在数据量比较大的时候，贪心算法效率会很低，XGBoost 提出了可并行的近似直方图算法，能高效的生成候选分割点。
缺点：
1. 空间消耗大：预排序要保存数据的特征值，以及特征排序后的结果，需要消耗训练数据两倍的内存。
2. 时间上的开销大：遍历每个分割点的时候，都需要计算分裂增益。
3. 对 cache 的优化不友好：在预排序后，特征的访问是一种随机访问，并且不同的特征访问的顺序不一样，无法对 cache 进行优化。在每一层长树的时候，需要随机访问一个行索引到叶子索引的数组，并且不同特征访问的顺序也不一样，也会造成较大的 cache miss
4. 分裂的时候是贪心算法，不适合处理稀疏数据，会产生很多的子树，训练特别慢
5. level-wise 的生成策略，导致一些节点没必要的划分浪费时间
计算特征权重的方式一共五种，常用 Gain：
1. ‘weight’：权重形式，表示在所有树中，一个特征在分裂节点时被使用了多少次。
2. ‘gain’：（平均）增益形式，表示在所有树中，一个特征作为分裂节点存在时，带来的增益的平均值。
3. ‘cover’：（平均）覆盖度，表示在所有树中，一个特征作为分裂节点存在时，覆盖的样本数量的平均值。
4. ‘total_gain’：相对于’gain’，这里表示的是带来的总增益大小。
5. ‘total_cover’：相对于’cover’，这里表示的是覆盖的总样本数量

LGBM 模型

优化：
1. 基于 Histogram 的决策树算法。
2. 单边梯度采样 Gradient-based One-Side Sampling(GOSS)：使用 GOSS 可以减少大量只具有小梯度的数据实例，这样在计算信息增益的时候只利用剩下的具有高梯度的数据就可以了，相比 XGBoost 遍历所有特征值节省了不少时间和空间上的开销。
3. 互斥特征捆绑 Exclusive Feature Bundling(EFB)：使用 EFB 可以将许多互斥的特征绑定为一个特征，这样达到了降维的目的。
4. 带深度限制的 Leaf-wise 的叶子生长策略：大多数 GBDT 工具使用低效的按层生长 (level-wise) 的决策树生长策略，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销。实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。LightGBM 使用了带有深度限制的按叶子生长 (leaf-wise) 算法。（其实 XGBoost 也有）
5. 直接支持类别特征(Categorical Feature)
6. 支持高效并行
7. Cache 命中率优化
直方图算法：
1. 先把连续的浮点特征值离散化成 k 个整数，同时构造一个宽度为 k 的直方图
2. 在遍历数据的时候，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。
3. 内存占用更小：直方图算法不仅不需要额外存储预排序的结果，而且可以只保存特征离散化后的值，而这个值一般用 8 位整型存储就足够了，内存消耗可以降低为原来的。XGBoost 需要用 32 位的浮点数去存储特征值，并用 32 位的整形去存储索引，而 LightGBM 只需要用 8 位去存储直方图；
4. 计算代价更小：预排序算法 XGBoost 每遍历一个特征值就需要计算一次分裂的增益，而直方图算法 LightGBM 只需要计算 k 次。其实就是把搜索特征分裂值的复杂度降低了。
直方图做差加速：
1. 一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到，在速度上可以提升一倍。通常构造直方图时，需要遍历该叶子上的所有数据，但直方图做差仅需遍历直方图的 k 个桶。
2. 在实际构建树的过程中，LightGBM 还可以先计算直方图小的叶子节点，然后利用直方图做差来获得直方图大的叶子节点，这样就可以用非常微小的代价得到它兄弟叶子的直方图。
带深度限制的 Leaf-wise 算法：
1. 和 XGBoost 的 Level-wise 不同，xgb 遍历一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。但实际上 Level-wise 是一种低效的算法，因为它不加区分的对待同一层的叶子，实际上很多叶子的分裂增益较低，没必要进行搜索和分裂，因此带来了很多没必要的计算开销。
2. Leaf-wise：每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。
3. Leaf-wise 的优点是：在分裂次数相同的情况下，Leaf-wise 可以降低更多的误差，得到更好的精度
4. Leaf-wise 的缺点是：可能会长出比较深的决策树，产生过拟合。
5. LightGBM 会在 Leaf-wise 之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。
单边梯度采样算法：
1. Gradient-based One-Side Sampling，GOSS 算法从减少样本的角度出发，排除大部分小梯度的样本，仅用剩下的样本计算信息增益，它是一种在减少数据量和保证精度上平衡的算法。
2. 梯度小的样本，表示训练误差也比较小了，但是如果直接丢掉这部分数据会改变数据分布，影响准确度，因此提出 GOSS
3. GOSS 其实就是对要分裂的特征的所有取值按照梯度绝对值排序，选择绝对值最大的 $alen(I) $个，然后在剩下的里面随机选择$ blen(I) $个，对随机选的数据乘以$ \frac{1-a}{b}$，这样的好处是更关注训练不足的样本，而不会过多改变原数据集的分布
互斥特征捆绑算法(Exclusive Feature Bundling, EFB)：
1. 通常被捆绑的特征都是互斥的（即特征不会同时为非零值，像 one-hot），这样两个特征捆绑起来才不会丢失信息。
2. 如果两个特征并不是完全互斥（部分情况下两个特征都是非零值），可以用一个指标对特征不互斥程度进行衡量，称之为冲突比率，当这个值较小时，我们可以选择把不完全互斥的两个特征捆绑，而不影响最后的精度。
3. 优点：降低特征数量
4. 把哪些捆绑：
  1. 构造一个加权无向图，顶点是特征，边有权重，其权重与两个特征间冲突相关；
  2. 根据节点的度进行降序排序，度越大，与其它特征的冲突越大；
  3. 遍历每个特征，将它分配给现有特征包，或者新建一个特征包，使得总体冲突最小
5. 特征如何合并：
  1. 特征合并算法，其关键在于原始特征能从合并的特征中分离出来。
  2. 考虑到 histogram-based 算法将连续的值保存为离散的 bins，我们可以使得不同特征的值分到 bundle 中的不同 bin（箱子）中，这可以通过在特征值中加一个偏置常量来解决。
  3. 不同特征有对应的偏置，，，$binRanges 里面的就是每个特征的偏置。这样的结果就是不同特征的范围就不一样了。
直接支持类别特征：
1. 针对 one-hot 编码存在的问题：
  1. 产生样本切分不平衡的问题，导致切分增益很小，和不切分没什么区别。一系列特征上只有少量样本为 1，大量样本为 0，这时候切分样本会产生不平衡，这意味着切分增益也会很小。较小的那个切分样本集，它占总样本的比例太小，无论增益多大，乘以该比例之后几乎可以忽略；较大的那个拆分样本集，它几乎就是原始的样本集，增益几乎为零。
  2. 会影响决策树的学习。因为就算可以对这个类别特征进行切分，独热编码也会把数据切分到很多零散的小空间上，在这些数据量小的空间上，统计信息不准确，学习效果会变差
2. LGBM 优化了对类别特征的支持，可以直接输入类别特征，采用 many-vs-many 的切分方式，从 one-hot 的降到了
3. 算法流程：
  1. 在枚举分割点之前，先把直方图按照每个类别对应的 label 均值进行排序；然后按照排序的结果依次枚举最优分割点
  2. 这个方法容易过拟合，LGBM 增加了很多对这个方法的约束和正则化
支持高效并行：
1. 特征并行：
  1. XGBoost 使用特征并行，每个机器在不同的特征集合找最优分割点，然后同步最优分割点。这个缺点是每个机器数据不同，划分结果需要在机器间通信，增加了额外复杂度。
  2. LGBM 也是用特征并行，不进行数据垂直划分，在每台机器上保存所有数据，机器间传输最优分裂特征和分裂点，来得到全局最优分裂信息，（不需要广播分裂结果），然后直接在本地执行划分。
2. 数据并行：
  1. 传统的数据并行策略为水平划分数据，不同机器在本地构造直方图然后全局合并，这样的划分有很大的缺点是通信开销太大。
  2. LGBM 数据并行中使用分散规约 (Reduce scatter) 把直方图合并的任务分摊到不同的机器，降低通信和计算，并利用直方图做差，进一步减少了一半的通信量。
3. 投票并行：
  1. 基于投票的数据并行进一步优化了数据并行中的通信代价
  2. 数据量很大的时候，投票并行只合并部分特征的直方图，从而达到降低通信量的目的
  3. 分两步：1. 在本地找出 Top K 的特征，基于投片筛选出可能是最优分割点的特征，合并时只合并每个机器选出来的特征
4. Cache 命中率优化：
  1. 相对 XGBoost：特征对梯度访问是随机访问，不同特征访问的顺序不同，无法对 cache 优化，且每层长树的时候，要随机访问一个行索引到叶子索引的数组，也会造成很大的 cache miss
  2. LGBM 所有的特征都采用相同的方式获得梯度，只需要对梯度进行排序并可实现连续访问，大大提高了缓存命中率。
  3. 其次，因为不需要存储行索引到叶子索引的数组，降低了存储消耗，而且也不存在 Cache Miss 的问题。
相对 XGBoost 优点：
1. 速度更快
  1. 遍历样本->遍历直方图
  2. 单边梯度采样->过滤梯度小的样本
  3. Level-wise -> Leaf-wise，减少不必要计算
  4. 优化后的特征并行、数据并行，以及投票并行
  5. 缓存优化
2. 内存更小
  1. 相比 XGBoost 不用存储特征值和样本统计值的索引，使用 bin 值，内存变为原本的
  2. 存储特征值变为存储 bin 值
  3. 互斥特征捆绑减少了特征数量
缺点：
1. 可能会长出比较深的决策树，过拟合，因此要增加一个最大深度限制
2. LGBM 对噪声比较敏感
3. 寻找最优解的时候，依据的是最优切分变量，没有把最优解是全部特征考虑进去

模型评价指标

分类指标

参考链接
混淆矩阵
1. TP=11(真实-预测），FP=01，FN=10，TN=00
准确率：
误差率：
召回率/查全率：
2. 针对原始样本而言，召回率越高表示目标被预测出的概率越高
精准率/查准率：
2. 针对预测结果而言，在预测结果中，有多少把握可以预测正确。
PR 曲线：
1. 纵坐标是 Precision，横坐标是 Recall。
2. 拿逻辑回归来说，它输出的是 0-1 之间的数，如果要用这个判断正负样本，就需要确定一个阈值，然后这个阈值的前提下可以得到一个查准率和查全率。
3. 要想知道这个阈值是否符合我们要求，就需要遍历 0-1 之间所有阈值，然后就可以得到这个曲线。
4. 想要平衡 P 和 R，就需要用 F1 分数。
5. 同样也是 AUC 越大越好，也可以在能接受的 Precision 下选比较大的 Recall，把更多的正样本分类出来
F1 分数：
2. 是为了在查准和查全之间找到一个平衡点，让二者都比较高。
3. 作用相当于 AUC 对 ROC 曲线的作用，一个指标比一条曲线更方便调模型
真阳率：
2. 针对原始真样本来说，预测对的概率，等价于查全率
假阳率：
2. 针对原始假样本来说，预测错的概率
TPR=FPR：
1. 若二者相等，意味着无论一个样本本身是正例还是负例，分类器预测其为正例的概率是一样的，这等同于随机猜测
ROC:
1. 用 TPR 和 FPR 分别在实际的正样本和负样本中观察相关概率问题，因此无论样本是否平衡都不会被影响。所以采用 TPR 和 FPR 作为 ROC、AUC 的指标
2. ROC 曲线横坐标是 FPR，纵坐标是 TPR
3. 和 PR 曲线一样，也是遍历所有阈值
4. 如何判断 ROC 曲线好坏？纵坐标 TPR 越高，横坐标 FPR 越低，即曲线越陡峭，性能越好
AUC：
1. 表示 ROC 曲线下面积
2. 如果直接通过不同阈值多次评估模型的话效率很低，因此用 AUC 来提供这类信息。
3. 对角线下面的面积是 0.5，表示随机判断相应和不响应，正负样本覆盖率都是 50%，表示随机效果。所以理想值 AUC=1，最差的随机判断为 0.5。

搜索问题指标

上面的都没有考虑到检索结果的先后顺序，而像搜索问题中我们通常希望第一个结果是与查询最相关的，第二个则是次相关的，以此类推，因而有时候不仅要预测准确，对于相关性的顺序也非常看重。

MAP（Mean Average Precision）平均准确率均值：
1. AP: 对于单个信息需求，返回结果中在每篇相关文档上 Precision 的平均值被称为 Average Precision (AP)，然后对所有查询取平均得到 MAP。
2. 1. P(k)是取前 k 个结果算出来的 Precision，也可写成 [email protected]
  2. rel(k)表示第 𝑘 个结果是否为相关文档，相关为 1 不相关为 0。
  3. M 表示相关文档的数量
  4. n 表示所有文档数量
  5. 所以分子上，对一个有序的表，若该位置返回的结果相关，计算截止到该位置的正确率，若不相关，正确率置为 0
  6. 计算方法是对排序位置敏感的，相关文档排序的位置越靠前，检出的相关文档越多，AP 值越大。
3. 1. Q 是查询次数
  2. 是第 q 次查询算出来的 AP 值
  3. 也可以只关注前 k 个结果，把 n 换成 k 就行
  4. 对于单个信息需求来说，Average Precision 是 PR 曲线下面积的近似值，因此 MAP 可粗略地认为是某个查询集合对应的多条 PR 曲线下面积的平均值。
NDCG(Normalized Discounted Cumulative Gain)
1. 归一化折扣累计增益：
  1. N 指的是归一化，
  2. D 指的是衰减率，
  3. C 指的累加，
  4. G 指的是熵，
  5. 其实这个公式的关键就是就是熵，再多了三个形容词：归一化的，带有衰减函数的，再带有累加的熵。
  6. 如果说 MAP 是基于 0/1 二值描述相关性，那么 NDCG 则是可将相关性分为多个等级的指标。
2. 两个思想：
  1. 高关联度的结果比一般关联度的结果更影响最终的指标得分；
  2. 有高关联度的结果出现在更靠前的位置的时候，指标会越高；
3. 1. 表示第 i 这个位置上的相关度
  2. k 表示前 k 个结果
  3. CG 没有考虑推荐的次序，所以在此基础上引入对结果顺序的考虑，即相关性高的结果若排在后面则会受更多的惩罚，即 DCG
4. 1. 如果该结果 rel 很高，但排在后面，意味着分母 log2(i+1) 会变大，则相应的总体 DCG 会变小 (注意这里的 log 是以 2 为底的)
  2. 不同的查询，往往会返回不同的结果集，而不同结果集之间因为大小不同难以直接用 DCG 进行比较，所以需要进行归一化
5. 1. ，为理想情况下最大的 DCG 值，其中表示按相关性顺序排列的结果集，取前 p 个结果组成的集合
  2. IDCG 是 DCG 能取到的最大值，因此 NDCG 范围为(0,1]
  3. 缺点是需要预先指定每一个返回结果的相关性，这个超参数需要人为指定
  4. 参考链接

采样方法

过采样

随机采样

从样本少的类别中随机抽样，再将抽样得来的样本添加到数据集中
已经不大使用了，因为重复采样往往会导致严重的过拟合，因而现在的主流过采样方法是通过某种方式人工合成一些少数类样本，从而达到类别平衡的目的，而这其中的鼻祖就是 SMOTE。

SMOTE(synthetic minority oversampling technique)

概括起来就是在少数类样本之间进行插值来产生额外的样本。
步骤 1：对一个少数类样本，用 K 近邻法求出离它最近的 k 个少数类样本
步骤 2：从 k 个近邻点中随机选取一个，用它生成一个新样本：，其中是随机选出的样本，是 0-1 之间的数，因此新样本在和的连线上
缺陷（没有考虑周边样本）：
1. 如果选取的少数类样本周围也都是少数类样本，则新合成的样本不会提供太多有用信息。这就像支持向量机中远离 margin 的点对决策边界影响不大。
2. 如果选取的少数类样本周围都是多数类样本，这类的样本可能是噪音，则新合成的样本会与周围的多数类样本产生大部分重叠，致使分类困难。

Border-line SMOTE

将所有的少数类样本分成三类：
1. “noise” ：所有的 k 近邻个样本都属于多数类
2. “danger” ：超过一半的 k 近邻样本属于多数类
3. “safe”：超过一半的 k 近邻样本属于少数类
算法只会从处于”danger“状态的样本中随机选择样本使用 SMOTE，处于”danger“状态的样本更靠近”边界“，往往更容易被误分类。
和传统 SMOTE 区别是，它只用边界附近的少数类样本进行人工合成，而 SMOTE 不区分是不是边界。
有两种模式：1. 公式中的是一个少数类样本，或者，2. 是 k 近邻中的任意一个样本

自适应合成抽样 ADASYN(adaptive synthetic sampling)

最大的特点是采用某种机制自动决定每个少数类样本需要产生多少合成样本，而不是像 SMOTE 那样对每个少数类样本合成同数量的样本
计算需要合成的样本总量：
2. 为多数类样本数量
3. 为少数类样本数
5. G 即为总共想要合成的少数类样本数量
每个少类别样本，找出其 K 近邻个点，计算：
2. 为 K 近邻个点中多数类样本的数量
3. Z 为规范化因子以确保构成一个分布
4. 这样若一个少数类样本的周围多数类样本越多，则其也就越高。
对每个少类别样本计算需要合成的样本数量，再用 SMOTE 算法合成新样本
缺点是：易受离群点的影响，如果一个少数类样本的 K 近邻都是多数类样本，则其权重会变得相当大，进而会在其周围生成较多的样本

对比

SMOTE 合成的样本分布比较平均，
Border-line SMOTE合成的样本则集中在类别边界处。
ADASYN的特性是一个少数类样本周围多数类样本越多，则算法会为其生成越多的样本，生成的样本大都来自于原来与多数类比较靠近的那些少数类样本

欠采样

随机欠采样

随机欠采样的思想同样比较简单，就是从多数类样本中随机选取一些剔除掉。
这种方法的缺点是被剔除的样本可能包含着一些重要信息，致使学习出来的模型效果不好。

EasyEnsemble 和 BalanceCascade

它们集成学习机制来处理传统随机欠采样中的信息丢失问题。

EasyEnsemble：
1. 将多数类样本随机划分成 n 个子集，每个子集的数量等于少数类样本的数量，这相当于欠采样。
2. 接着将每个子集与少数类样本结合起来分别训练一个模型，最后将 n 个模型集成，这样虽然每个子集的样本少于总体样本，但集成后总信息量并不减少。

如果说 EasyEnsemble 是基于无监督的方式从多数类样本中生成子集进行欠采样，那么 BalanceCascade 则是采用了有监督结合 Boosting 的方式

BalanceCascade:
1. 在第 n 轮训练中，将从多数类样本中抽样得来的子集与少数类样本结合起来训练一个基学习器 H，训练完后多数类中能被H 正确分类的样本会被剔除。
2. 在接下来的第 n+1 轮中，从被剔除后的多数类样本中产生子集用于与少数类样本结合起来训练，最后将不同的基学习器集成起来。
3. BalanceCascade 的有监督表现在每一轮的基学习器起到了在多数类中选择样本的作用，而其 Boosting 特点则体现在每一轮丢弃被正确分类的样本，进而后续基学习器会更注重那些之前分类错误的样本。

NearMiss

NearMiss 本质上是一种原型选择(prototype selection)方法，即从多数类样本中选取最具代表性的样本用于训练，主要是为了缓解随机欠采样中的信息丢失问题。
NearMiss 采用一些启发式的规则来选择样本，根据规则的不同可分为 3 类，1 和 2 要计算 KNN：
1. NearMiss-1：选择多数类样本中，到最近的 K 个少数类样本平均距离最近的
2. NearMiss-2：选择多数类样本中，到最远的 K 个少数类样本，平均距离最近的
3. NearMiss-3：对于每个少数类样本，选择 K 个最近的多数类样本，目的是保证每个少数类样本都被多数类样本包围
NearMiss-1 和 NearMiss-2 的计算开销很大，因为需要计算每个多类别样本的 K 近邻点。另外，NearMiss-1 易受离群点的影响，处于边界附近的多数类样本会被选中，然而由于右下方一些少数类离群点的存在，其附近的多数类样本就被选择了。相比之下 NearMiss-2 和 NearMiss-3 不易产生这方面的问题。

数据清洗方法

主要通过某种规则来清洗重叠的数据，从而达到欠采样的目的，而这些规则往往也是启发性的

Tomek Link：
1. Tomek Link 表示不同类别之间距离最近的一对样本，即这两个样本互为最近邻且分属不同类别。
2. 这样如果两个样本形成了一个 Tomek Link，则要么其中一个是噪音，要么两个样本都在边界附近，都可以去掉。
3. 这样通过移除 Tomek Link 就能“清洗掉”类间重叠样本，使得互为最近邻的样本皆属于同一类别，从而能更好地进行分类。
Edited Nearest Neighbours(ENN)：
1. 对于属于多数类的一个样本，如果其 K 个近邻点有超过一半都不属于多数类，则这个样本会被剔除。
2. 这个方法的另一个变种是所有的 K 个近邻点都不属于多数类，则这个样本会被剔除。

数据清洗技术最大的缺点是无法控制欠采样的数量。由于都在某种程度上采用了 K 近邻法，而事实上大部分多数类样本周围也都是多数类，因而能剔除的多数类样本比较有限。

深度学习和机器学习

直接看另一篇笔记吧，没有合并在这里。ML/DL面试问题笔记

面试总结

京东

京东是第一个面试，一面挂
存在问题：没有和 HR 沟通好时间，预期是下周面试，HR 确定时间在第二天也没有沟通调整。导致一面的时候还没有过完简历。

字节跳动

一面和二面是一起的，所以整个的压力会比较大。如果全程都很紧张的话，会导致做算法题的时候头脑不清楚。可以在一面二面的间隔出去走走，放松下脑子。
字节跳动比较看重算法基础。可能和他们是偏向业务有关系，所以不怎么在意 NLP 理论 or 数学方面的知识。这意味着杂活可能会比较多。
字节跳动三面挂了，问题是在算法题上。是一道有把握的题，但是输在细节上。平时刷题要注意细节和易错点的整理，光刷题不积累下次遇到了还是会错。

字节一面题

在有序旋转数组中找到一个数
有序数组 arr 可能经过一次旋转处理，也可能没有，且 arr 可能存在重复的数。例如，有序数组[1, 2, 3, 4, 5, 6, 7]，可以旋转处理成[4, 5, 6, 7, 1, 2, 3]等。给定一个可能旋转过的有序数组 arr，再给定一个数 num，返回 arr 中是否含有 num
关于旋转操作：可以简单的理解为把序列从某个位置切成两段然后交换位置
期望复杂度为 O(\log n)O(logn)
示例 1
输入
[4,5,6,7,1,2,3],7
输出
true

字节二面算法题

跳方格问题（类似 LeetCode 青蛙跳）
N 个方格，每个方格上有加体力值的，也可能是减体力值的。给定初始体力值，每次可以跳任意步，问能否到达终点，到达终点时能剩余的最大体力值是多少。

字节三面题

建树和之字形遍历
给一串数字，自己建树，然后打印出这个树之字形遍历的结果。

第二次字节一面题

阶乘末尾为 0 的个数
求大整数 N 的阶乘，末尾有多少个 0。
3! = 6, res = 0
5! = 120, res = 1

快手

一面二面在一起，但是没有三面
整体难度比字节低一个 level，问的问题也不是很深，面试官也不会像字节那么严肃，会和你聊天，全程下来都不紧张。
还是那句话，所有命运的馈赠，都在暗中标好了价格。组越好那肯定面试越难进。

快手一面题

数值的整数次方
给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent。求 base 的 exponent 次方。
没有限制底数和 exponent 的范围，所以都可能是负数。
连续子数组的最大和
HZ 偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为 8(从第 0 个开始,到第 3 个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是 1)

快手二面题

最长回文串
对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。给定字符串 A 以及它的长度 n，请返回最长回文子串的长度。
牛客/LeetCode 原题。直接中心扩散法，初始化中心两个位置，然后 dp。
链式 A+B
有两个用链表表示的整数，每个结点包含一个数位。这些数位是反向存放的，也就是个位排在链表的首部。编写函数对这两个整数求和，并用链表形式返回结果。
给定两个链表 ListNode* A，ListNode* B，请返回 A+B 的结果(ListNode*)。
测试样例：{1,2,3},{3,2,1}
返回：{4,4,4}

百度cv部门research

一面

要求做个PPT介绍以前的工作，腾讯会议讲。没有算法题，因为招人过去就是做research，不需要LeetCode那一套。

ppt讲的过程中，会针对你的内容提问一些问题，这部分花的时间比较长，也可能是因为我做的内容比较多，花了70min。

然后是会问一些深度学习机器学习的问题。

讲一下SENet（Squeeze-and-Excitation Networks）
word2vec和Glove的，以及它们的损失函数区别
讲一下BERT和GPT的区别
GPT是用的Transformer的encoder还是decoder
Transformer中两个地方用到了mask，讲一下
Transformer的decoder中的mask作用是啥
讲一下ViT
讲一下Swin Transformer
Swin Transformer相比ViT的优势（为什么它的shift window能work，优势）
其他不太记得了…

最后会写一个题

给数据集，8w左右的训练数据，对图像做多标签三分类。
加载resnet50，要求对图像进行增强，随机翻转，随机裁剪，随机旋转
要求写出完整的训练代码，从import都要写。开放式，不要求能直接运行，最后面试官会看写的咋样。

二面

主要在问一些实习期间的工作…

总结

积累阶段

自己打比赛的时候要注意选择和自己想做方向相关的比赛，不然帮助不大
多打比赛增加实战经验
对于一些算法不能停留表面，要理解底层的原理和数学知识，不然面试官会问你为什么，就答不出来
还是得看 paper，要有基本的科研素质，投 research 岗位的时候才会有人要。
招聘写的论文优先，主要目的是想让招进来的人知道怎么科研，少走弯路。所以自己如果想投 research，就算没论文，也得有基本的科研素质。多看论文，了解前沿动态。
综合多种信息之后，模型的能力会更好，不要光局限于文本序列信息，还有很多 Structured Data。
算法题还是要多练，做笔记整理，不然总是忘。以及一些 STL 的东西，很不熟练。刷完的题得积累，方便查阅。
算法不要光停留在理解思路上，还要有很强的把思路转换为code的能力

准备阶段

自己的项目，一定要很熟悉，熟悉到特征维数、输入输出、shape 转换情况之类的。
面试的之前还是得自己问自己点问题，然后自己说出来，多练习，不然知道会问啥也懂但是说不清楚，这就很糟糕。
有时间的多准备准备，可以做个 PPT 讲自己的项目细节，不然你感觉自己讲的很清楚了，面试官还不清楚你说的是啥。
每个类型的题目最好都过一遍，每个结构的都要熟悉一遍。不然基础的东西反而可能会坑到自己。

面试阶段

面试过程中语速不要太快，不要慌，分点说，一定要说的逻辑比较清楚，不然会让面试官觉得你这方面不熟。
面试官提问之后的思考过程不能太久，会显得反应迟钝，最好先从一个很清楚的点说起，然后边理思路边说。

面试的算法题

算法题要先审题，不要拿到题目就冲上去写。如果没思路可以试试最简单的 case。
算法题的过程中，如果卡住了，一定要和面试官交流，不要一直埋头 debug。
算法题不仅考察 coding 能力，还看你解决问题的能力，以及沟通交流能力。所以可以和面试官聊聊解题思路，讲讲自己的代码怎么写的，面试官一般也会给提示，千万不要啥都不说，这样显得沟通能力很差，毕竟工作中的交流和沟通很重要。

最后的问答

面试结束的时候，面试官会问有什么要问的，这时候可以问下面这些：

感觉我的面试过程怎么样，对我的面试有什么建议？这可以对下一轮面试有帮助。因为面试官写面评的时候，会给下一轮面试的面试官建议考察的偏向。比如算法基础不行，就让下一轮重点考察算法。所以问面试官这个可以针对性地准备和心里准备。
可以聊实习的内容，具体的问细节，防止最后不清楚工作内容，导致工作不满意。