今天上午11点进行了深信服算法工程师的第一次面试，由于事先准备不足，一些常规的面试套路题回答的并不好，这里主要记录一下面试问题到的题目。
一、引题 （自我介绍）
首先要求的是自我介绍，主要大概介绍做过的一些比赛、项目。面试官也比较直接，让自己选择介绍一个点。
二、竞赛与比赛介绍
我本身在做NLP知识图谱相关的技术，这里着重谈了下信息抽取中的NER。主要结合了两个比赛：CCKS和瑞金医院辅助构建知识图谱。
回答路线
- 比赛概述
- 着重负责部分
面试官根据自己介绍的部分，进行着重提问。我首先介绍了数据预处理、数据增强、模型，这三部分。可能面试官对于数据预处理以及数据增强没有什么兴趣或其他原因，没有过多地提及。
上述是一面的流程，下面按照时间线整理提问到的一些问题。
1. BERT的网络架构
我主要回答了BERT的核心过程包括两个训练任务：
- 从数据集抽取两个句子，已知上一句子预测下一句子，这样可以学习句子之间的关系。
- 随机去抽两个句子中的一些词，模型预测这些词，这样能够学习句子内部的关系。
对于细节问题问答的不好。
下面将借鉴机器之心的讲述，详细地介绍下BERT的网络架构以及工作原理。
1.1 BERT概述
BERT属于预训练NLP模型, Google开放了预训练的BERT-Base和BERT-Large模型。每一种模型都有uncased和cased版本。
uncased是指将所有的英文词转为小写，没有大小写之分。
cased是指保留文本所有的真实情况。
BERT的计算力是十分惊人的，模型总共有24层、2014个隐藏单元，在有33亿词量的数据集上需要训练40个Epoch，因此在8块P100可能需要1年。
1.2 BERT网络架构
BERT的全称是基于Transformer的双向编码器表征，其中“双向“就是模型在处理一个词时，能够同时利用前后两部分词的信息。但是这与常规的双向模型不同，主要体现在BERT会随机遮掩掉一些词，只能利用所有没被遮掩的词进行预测。
上图为BERT与GPT和ELMO的比较，BERT和ELMo都是使用双向信息，GPT使用单向信息。BERT结合了GPT和ELMo的优势，ELMo使用两条独立训练的LSTM获取双向信息，GPT使用新型Transformer模型获取单向信息。
这里介绍下Goolge提出的Transformer模型，具体可参考这篇paper《attenttion is all your need》。
1.2.1 Transformer模型
在整个Transformer架构中，只使用了注意力机制和全链接层来处理文本，没有使用RNN CNN进行特征提取。Transformer最重要的是自注意力机制，这种在序列内部执行注意力的方法可以看作搜索序列内部之间的隐藏关系。
Transformer使用了编码-解码框架，堆积了Multi-Head Attention 、前馈网络、层级归一化和残差连接等。
上图从左至右依次为Transformer架构、Multi-Head Attention、点乘注意力。
点乘注意力，其中 Query 向量与 Value 向量在 NMT 中相当于目标语输入序列与源语输入序列，Query 与 Key 向量的点乘相当于余弦相似性，经过 SoftMax 函数后可得出一组归一化的概率。这些概率相当于给源语输入序列做加权平均，即表示在生成一个目标语单词时源语序列中哪些词是重要的。（当然细节并不是那么简单，由于不是重点介绍部分，这里不再进行赘述）
Multi-Head Attention 其实就是多个点乘注意力并行处理并将最后的结果拼接在一起。这种注意力允许模型联合关注不同位置的不同表征子空间信息，我们可以理解为在参数不共享的情况下，多次执行点乘注意力。
Transformer 只堆叠了 6 个编码器解码器模块，即上图的 N=6。而 BERT 基础模型使用了 12 个编码器模块（N=12），BERT 大模型堆叠了 24 个编码器模块（N=24）。
1.2.2 BERT输入表征
由于其两个任务的要求，BERT的输入具有其特殊性。主要可由下图表示：
其中，该输入包含了两句话[my dog is cute] 和 [he likes playing] 其中特殊字符[SEP]为句子分隔符，首先将所有字符转化为词嵌入向量，前半部分会加上分隔编码A，后半部分加上分隔编码B。 对句子之间的关系建模需要用到A/B，其中[CLS]可视为该任务的汇集整个输入序列的表征。最后的位置编码是Transformer架构本身决定的，因为完全基于注意力的方法无法像CNN RNN那样编码词与词之间的位置关系，为了使得Transformer能够感知位置关系，需要使用位置编码给每个词加上位置信息。
2. 注意力机制的原理
注意力机制原理，我只简单介绍了点乘注意力，主要是其余弦计算表征相似度部分。
由于Attention相关的博客有很多，这里也不再加以赘述。具体可以参考苏神的博客。
3. Batch Normalization
主要参考该博客 https://www.cnblogs.com/guoyaohua/p/8724433.html
关于BN,我主要介绍了其作用，能够将神经元层保持统一分布，加快模型收敛。然后介绍为何能够加快收敛，借用了Ng机器学习课程中提到的特征缩放，便于后向传播的求导计算。面试官给出了补充，主要在于激活函数方面。下面我将对BN进行详细地讲解。
Batch Normalization就是在深度神经网络训练过程中使得每一层神经网络的输入保持相同分布的。
首先引入Internal Covariate Shift 问题
概念是这样介绍，如果机器学习的实例集合<X,Y>中X的分布不断变化，这不符合独立同分布假设，网络模型将很难学习。
在模型训练过程中，每层参数都在不停地变化，所以每个隐层都会面临Internal Covariate Shift问题。
如何能够让每个节点的激活输入分布固定下来？这样就可以解决上述问题。
3.1 Batch Normalization 的本质思想
深度神经网络在做非线性变换前的激活输入值随着网络层数的加深或者在训练过程中，其分布逐渐发生偏移，主要表现为整体分布逐渐往非线性函数的取值区间的上下限两端靠近。（对于sigmoid函数来说，集中于1或0），所以这就导致了反向传播时梯度消失。 BN就是通过一定的规范化手段，将偏移的分布强行拉回均值为0 方差为1的标准正态分布。
对于每个隐层神经元，把逐渐向非线性函数映射后向取值区间极限饱和区靠拢的输入分布强制拉回到均值为0方差为1的比较标准的正态分布，使得非线性变换函数的输入值落入对输入比较敏感的区域，以此避免梯度消失问题。
BN在实际使用时，位于激活值获得之后，非线性变换之前。
注意 经过变换后某个神经元的激活x形成了均值为0，方差为1的正态分布，目的是把值往后续要进行的非线性变换的线性区拉动，增大导数值，增强反向传播信息流动性，加快训练收敛速度。但是这样会导致网络表达能力下降，为了防止这一点，每个神经元增加两个调节参数（scale和shift），这两个参数是通过训练来学习到的，用来对变换后的激活反变换，使得网络表达能力增强，即对变换后的激活进行如下的scale和shift操作，这其实是变换的反操作。
3.2 BN延申
在面试后与陈道友交流后，他给出了面试官在进行BN提问后可能发散点：CNN和RNN中的BN使用位置上是相同的吗？
后续有时间我会再做介绍，有兴趣的可以了解一下Layer Norm | Instance Norm | Group Norm。
4. 已知一个数组，求数组第二大元素？
这是一个面试常考题，但是对于我还没有开始刷题来说，它是一道崭新的题目。。。
首先蹦入我脑海中的就是排序算法，然后我回答说使用堆排序。面试官紧接着询问堆排序的时间复杂度，我蒙蔽了。。。 有一段时间没有复习过数据结构了， O ( l o g n ) O(logn) O(logn)果不其然的错误了。正确的应该为 O ( n l o g n ) O(nlogn) O(nlogn)。当我回答错误之后，面试官很贼，并没有纠正我的错误而是追问为什么是 O ( l o g n ) O(logn) O(logn)。心里顿时一阵草泥马狂奔。。。。紧接着问到是否有不使用排序的方法解决，脑子已经短路了。
4.1 解体方法
1. 快速查找
设置一个最大值和第二大值，然后循环所有其他元素，首先与最大值比较，如果比最大值大则替换，比最大值小则与第二大进行比较，如果大则替换否则下一个。
2. 排序
排序的方法就很多了，冒泡、堆排序等，注意时间复杂度。
等等。。。
网上这道题的解法有很多，给出一个链接解法
4.2 延申
这道题不管回答的错误与否，正确的解答不应该是这样。首先需要向考官发问，数组内存是否放的下（考虑外存排序，内存排序，尽管一般都是内存排序）；对时间复杂度是否有限制等等。这样便于将主动权掌握在自己手里，以免当你给出一个解法之后，考官又向你抛出这些限制。。
5. 已知一篇文档和关键词，从文章中识别关键词。
这个考题也是在NLP算法面试中经常遇到的一个题目，我首先给出了使用字符串匹配的方法（最大前向匹配），考官主要想考察的应该是前缀树，这点我并没有复习到。并由陈道友提醒，接下来很可能会发文Jieba分词相关的知识。
这个我后续会追加更新。。。。。。
总结
总的来说，这次面试回答不好，主要体现在对于基础题的掌握程度不够，比如堆排序时间复杂度回答错误。还有发散思维不够，没有对面试题进一步了解，比如给定一个数组，并没有追问多大的数组，是否存在重复元素等等。。。这容易被面试官牵着走，另外主要是自己的知识储备不足，还是要多加努力！！！