21年7月底，字節(jié)推薦算法（DATA-EDU）面試題10道

問題1：bert蒸餾了解嗎

知識(shí)蒸餾的本質(zhì)是讓超大線下  teacher model來協(xié)助線上student model的training。

bert的知識(shí)蒸餾，大致分成兩種。

第一種，從transformer到非transformer框架的知識(shí)蒸餾

這種由于中間層參數(shù)的不可比性，導(dǎo)致從teacher model可學(xué)習(xí)的知識(shí)比較受限。但比較自由，可以把知識(shí)蒸餾到一個(gè)非常小的model，但效果肯定會(huì)差一些。

第二種，從transformer到transformer框架的知識(shí)蒸餾

由于中間層參數(shù)可利用，所以知識(shí)蒸餾的效果會(huì)好很多，甚至能夠接近原始bert的效果。但transformer即使只有三層，參數(shù)量其實(shí)也不少，另外蒸餾過程的計(jì)算也無法忽視。
所以最后用那種，還是要根據(jù)線上需求來取舍。


問題2：給你一些很稀疏的特征，用LR還是樹模型
參考：很稀疏的特征表明是高維稀疏，用樹模型（GBDT）容易過擬合。建議使用加正則化的LR。
假設(shè)有1w 個(gè)樣本， y類別0和1，100維特征，其中10個(gè)樣本都是類別1，而特征 f1的值為0，1，且剛好這10個(gè)樣本的 f1特征值都為1，其余9990樣本都為0(在高維稀疏的情況下這種情況很常見)，我們都知道這種情況在樹模型的時(shí)候，很容易優(yōu)化出含一個(gè)使用 f1為分裂節(jié)點(diǎn)的樹直接將數(shù)據(jù)劃分的很好，但是當(dāng)測(cè)試的時(shí)候，卻會(huì)發(fā)現(xiàn)效果很差，因?yàn)檫@個(gè)特征只是剛好偶然間跟 y擬合到了這個(gè)規(guī)律，這也是我們常說的過擬合。但是當(dāng)時(shí)我還是不太懂為什么線性模型就能對(duì)這種 case 處理的好？照理說 線性模型在優(yōu)化之后不也會(huì)產(chǎn)生這樣一個(gè)式子：y = W1*f1 + Wi*fi+….，其中 W1特別大以擬合這十個(gè)樣本嗎，因?yàn)榉凑?f1的值只有0和1，W1過大對(duì)其他9990樣本不會(huì)有任何影響。
現(xiàn)在的模型普遍都會(huì)帶著正則項(xiàng)，而 lr 等線性模型的正則項(xiàng)是對(duì)權(quán)重的懲罰，也就是 W1一旦過大，懲罰就會(huì)很大，進(jìn)一步壓縮 W1的值，使他不至于過大，而樹模型則不一樣，樹模型的懲罰項(xiàng)通常為葉子節(jié)點(diǎn)數(shù)和深度等，而我們都知道，對(duì)于上面這種 case，樹只需要一個(gè)節(jié)點(diǎn)就可以完美分割9990和10個(gè)樣本，懲罰項(xiàng)極其之小.
這也就是為什么在高維稀疏特征的時(shí)候，線性模型會(huì)比非線性模型好的原因了：帶正則化的線性模型比較不容易對(duì)稀疏特征過擬合。


問題3：LR的損失函數(shù)推導(dǎo)
 邏輯回歸損失函數(shù)及梯度推導(dǎo)公式如下：

求導(dǎo)：


問題4：為什么分類用交叉熵不用MSE（從梯度的角度想一下）
LR的基本表達(dá)形式如下：
使用交叉熵作為損失函數(shù)的梯度下降更新求導(dǎo)的結(jié)果如下：

首先得到損失函數(shù)如下：
如果我們使用MSE作為損失函數(shù)的話，那損失函數(shù)以及求導(dǎo)的結(jié)果如下所示：
使用平方損失函數(shù)，會(huì)發(fā)現(xiàn)梯度更新的速度和sigmod函數(shù)本身的梯度是很相關(guān)的。sigmod函數(shù)在它在定義域內(nèi)的梯度都不大于0.25。這樣訓(xùn)練會(huì)非常的慢。使用交叉熵的話就不會(huì)出現(xiàn)這樣的情況，它的導(dǎo)數(shù)就是一個(gè)差值，誤差大的話更新的就快，誤差小的話就更新的慢點(diǎn)，這正是我們想要的。

在使用 Sigmoid 函數(shù)作為正樣本的概率時(shí)，同時(shí)將平方損失作為損失函數(shù)，這時(shí)所構(gòu)造出來的損失函數(shù)是非凸的，不容易求解，容易得到其局部最優(yōu)解。如果使用極大似然，其目標(biāo)函數(shù)就是對(duì)數(shù)似然函數(shù)，該損失函數(shù)是關(guān)于未知參數(shù)的高階連續(xù)可導(dǎo)的凸函數(shù)，便于求其全局最優(yōu)解。（關(guān)于是否是凸函數(shù)，由凸函數(shù)的定義得，對(duì)于一元函數(shù)，其二階導(dǎo)數(shù)總是非負(fù)，對(duì)于多元函數(shù)，其Hessian矩陣（Hessian矩陣是由多元函數(shù)的二階導(dǎo)數(shù)組成的方陣）的正定性來判斷。如果Hessian矩陣是半正定矩陣）


問題5：BERT和Roberta的區(qū)別
RoBERTa 模型在 Bert 模型基礎(chǔ)上的調(diào)整：
訓(xùn)練時(shí)間更長，Batch_size 更大，（Bert 256，RoBERTa 8K）
訓(xùn)練數(shù)據(jù)更多（Bert 16G，RoBERTa 160G）
移除了 NPL（next predict loss）
動(dòng)態(tài)調(diào)整 Masking 機(jī)制
Token Encoding：使用基于  bytes-level 的 BPE

簡單總結(jié)如下：



問題6：分詞方法BPE和WordPiece的區(qū)別
BPE與Wordpiece都是首先初始化一個(gè)小詞表，再根據(jù)一定準(zhǔn)則將不同的子詞合并。詞表由小變大

BPE與Wordpiece的最大區(qū)別在于，如何選擇兩個(gè)子詞進(jìn)行合并：BPE選擇頻數(shù)最高的相鄰子詞合并，而WordPiece選擇能夠提升語言模型概率最大的相鄰子詞加入詞表。
 


問題7：殘差網(wǎng)絡(luò)有哪些作用？除了解決梯度消失？
解決梯度消失和網(wǎng)絡(luò)退化問題。

殘差網(wǎng)絡(luò)為什么能解決梯度消失？

殘差模塊能讓訓(xùn)練變得更加簡單，如果輸入值和輸出值的差值過小，那么可能梯度會(huì)過小，導(dǎo)致出現(xiàn)梯度小時(shí)的情況，殘差網(wǎng)絡(luò)的好處在于當(dāng)殘差為0時(shí)，改成神經(jīng)元只是對(duì)前層進(jìn)行一次線性堆疊，使得網(wǎng)絡(luò)梯度不容易消失，性能不會(huì)下降。
 
什么是網(wǎng)絡(luò)退化？

隨著網(wǎng)絡(luò)層數(shù)的增加，網(wǎng)絡(luò)會(huì)發(fā)生退化現(xiàn)象：隨著網(wǎng)絡(luò)層數(shù)的增加訓(xùn)練集loss逐漸下降，然后趨于飽和，如果再增加網(wǎng)絡(luò)深度的話，訓(xùn)練集loss反而會(huì)增大，注意這并不是過擬合，因?yàn)樵谶^擬合中訓(xùn)練loss是一直減小的。

殘差網(wǎng)絡(luò)為什么能解決網(wǎng)絡(luò)退化？

在前向傳播時(shí)，輸入信號(hào)可以從任意低層直接傳播到高層。由于包含了一個(gè)天然的恒等映射，一定程度上可以解決網(wǎng)絡(luò)退化問題。


問題8：交叉熵?fù)p失，二分類交叉熵?fù)p失和極大似然什么關(guān)系？
什么是交叉熵?fù)p失？

機(jī)器學(xué)習(xí)的交叉熵?fù)p失函數(shù)定義為：假設(shè)有N個(gè)樣本，
其中：
從一個(gè)直觀的例子感受最小化交叉熵?fù)p失與極大似然的關(guān)系。
去掉 1/N 并不影響函數(shù)的單調(diào)性，機(jī)器學(xué)習(xí)任務(wù)的也可以是最小化下面的交叉熵?fù)p失：
等價(jià)于最大化下面這個(gè)函數(shù)：
 不難看出，這其實(shí)就是對(duì)伯努利分布求極大似然中的對(duì)數(shù)似然函數(shù)(log-likelihood)。
也就是說，在伯努利分布下，極大似然估計(jì)與最小化交叉熵?fù)p失其實(shí)是同一回事。

可參考：https://zhuanlan.zhihu.com/p/51099880


問題9：二叉樹最大路徑和（路徑上的所有節(jié)點(diǎn)的價(jià)值和最大）
方法一：遞歸

首先，考慮實(shí)現(xiàn)一個(gè)簡化的函數(shù) maxGain(node)，該函數(shù)計(jì)算二叉樹中的一個(gè)節(jié)點(diǎn)的最大貢獻(xiàn)值，具體而言，就是在以該節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹中尋找以該節(jié)點(diǎn)為起點(diǎn)的一條路徑，使得該路徑上的節(jié)點(diǎn)值之和最大。
具體而言，該函數(shù)的計(jì)算如下。
空節(jié)點(diǎn)的最大貢獻(xiàn)值等于 00。
 
非空節(jié)點(diǎn)的最大貢獻(xiàn)值等于節(jié)點(diǎn)值與其子節(jié)點(diǎn)中的最大貢獻(xiàn)值之和（對(duì)于葉節(jié)點(diǎn)而言，最大貢獻(xiàn)值等于節(jié)點(diǎn)值）。
 
例如，考慮如下二叉樹。
葉節(jié)點(diǎn) 99、1515、77 的最大貢獻(xiàn)值分別為 99、1515、77。


得到葉節(jié)點(diǎn)的最大貢獻(xiàn)值之后，再計(jì)算非葉節(jié)點(diǎn)的最大貢獻(xiàn)值。節(jié)點(diǎn) 2020 的最大貢獻(xiàn)值等于 20+max(15,7)=35，節(jié)點(diǎn) -10 的最大貢獻(xiàn)值等于 -10+max(9,35)=25。
上述計(jì)算過程是遞歸的過程，因此，對(duì)根節(jié)點(diǎn)調(diào)用函數(shù) maxGain，即可得到每個(gè)節(jié)點(diǎn)的最大貢獻(xiàn)值。
 
根據(jù)函數(shù) maxGain 得到每個(gè)節(jié)點(diǎn)的最大貢獻(xiàn)值之后，如何得到二叉樹的最大路徑和？對(duì)于二叉樹中的一個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)的最大路徑和取決于該節(jié)點(diǎn)的值與該節(jié)點(diǎn)的左右子節(jié)點(diǎn)的最大貢獻(xiàn)值，如果子節(jié)點(diǎn)的最大貢獻(xiàn)值為正，則計(jì)入該節(jié)點(diǎn)的最大路徑和，否則不計(jì)入該節(jié)點(diǎn)的最大路徑和。維護(hù)一個(gè)全局變量 maxSum 存儲(chǔ)最大路徑和，在遞歸過程中更新 maxSum 的值，最后得到的 maxSum 的值即為二叉樹中的最大路徑和。



問題10：寫題：找數(shù)組中第k大的數(shù)，復(fù)雜度
三種思路：一種是直接使用sorted函數(shù)進(jìn)行排序，一種是使用小頂堆，一種是使用快排（雙指針 + 分治）。
 
方法一：直接使用sorted函數(shù)進(jìn)行排序
 
代碼如下：


方法二：

維護(hù)一個(gè)size為 k 的小頂堆，把每個(gè)數(shù)丟進(jìn)去，如果堆的 size > k，就把堆頂pop掉（因?yàn)樗亲钚〉模?，這樣可以保證堆頂元素一定是第 k 大的數(shù)。
 
代碼如下：
時(shí)間復(fù)雜度：O(nlogk)
空間復(fù)雜度：O(k)
 
方法三：雙指針 + 分治
 
partition部分
定義兩個(gè)指針left 和 right，還要指定一個(gè)中心pivot（這里直接取最左邊的元素為中心，即 nums[i]）

不斷將兩個(gè)指針向中間移動(dòng)，使得大于pivot的元素都在pivot的右邊，小于pivot的元素都在pivot的左邊，注意最后滿足時(shí)，left是和right相等的，因此需要將pivot賦給此時(shí)的left或right。

然后再將中心點(diǎn)的索引和 k - 1 進(jìn)行比較，通過不斷更新left和right找到最終的第 k 個(gè)位置。
 
代碼如下：


時(shí)間復(fù)雜度：O(n)，原版快排是O(nlogn)，而這里只需要在一個(gè)分支遞歸，因此降為O(n)
空間復(fù)雜度：O(logn)