今天上午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分詞相關的知識。
這個我後續會追加更新。。。。。。
總結
總的來說，這次面試回答不好，主要展現在對于基礎題的掌握程度不夠，比如堆排序時間複雜度回答錯誤。還有發散思維不夠，沒有對面試題進一步了解，比如給定一個數組，并沒有追問多大的數組，是否存在重複元素等等。。。這容易被面試官牽着走，另外主要是自己的知識儲備不足，還是要多加努力！！！