最全常見演算法工程師面試題目整理(二)

歡迎關注我們的微信公眾號「人工智慧LeadAI」（ID：atleadai）

接著上回寫的《最全常見演算法工程師面試題目整理(一)》,繼續填接下來的坑。

11

boost演算法的思路是什麼樣的？講一下你對adaboost 和 gbdt的了解？

答案：

boost的核心思想不同於bagging，它在基於樣本預測結果對照與真實值得差距，進行修正，再預測再修正，逐步靠近正確值。

我對adaboost和gbdt了解的也不算很全面：大概的梳理如下：

不足：

1、adaboost存在異常點敏感的問題；

2、gbdt一定程度上優化了adaboost異常點敏感的問題，但是存在難以並行的缺點；

3、兩者的目標都是優化bias，必然導致訓練出來的數據var的不穩定。

亮點：

1.發現非線性的特徵關係，網格化的切分feature

2.擬合的效果相較於其他分類器更加精準，且訓練參數較少

Adaboost:

adaboost初始數據權重都是1/M，然後通過訓練每一個弱分類器Classifier使得在每一次y_pred誤差最小，得到每一個弱Classifier的權重方法對：（αi，yi）然後提高錯分了的數據的權重，降低正確分類的數據權重，循環訓練，最後組合最後若干次的訓練弱Classifier對，得到強分類器。

其中，αi由誤差決定：

該弱分類器分類錯誤率em越大，則該若分類器作用越小。

剖析了原理之後，我們發現，這樣做對異常點非常敏感，異常點非常容易錯分，會影響後續若干個弱分類器。

gbdt:

gbdt的核心在於下面這個公式：

L（y，y_pred）：預測值與實際值間的誤差

F(x):前若干個弱分類器的組合。

關鍵的在於當前預測結果=對前若干個弱分類器+當前弱分類器修正，所以對前若干個分類器組合求偏導的方向進行梯度處理，保證L（x）出來的值最小。

這邊結果在於你選取什麼樣的誤差函數：

Loss即為損失函數，Derivative即為導數。

除此之外，在每一步弱分類器構建的同時，它還考慮了正則化：

Ω=入T+μ*linalg.norm(f(xi))

T為子葉節點數目，同時也對預測結果得分的值進行了l1或者l2壓縮，避免過擬合。

我個人更喜歡用xgboost，在求解速度上，對異常值處理上面都要比gbdt要快，而且基於R、python版本都有package。

12

聽說你做過用戶關係，你用的什麼方法？社群演算法有了解，講講什麼叫做Modularity Q？

答案一、我用的是Jaccard相關。

比如，用戶1一共收過150個紅包，發了100個紅包，其中20個被用戶2搶過。

用戶2一共收過100個紅包，發了50個紅包，其中30個被用戶1搶過。

similarity(user1=>user2)=(30+20)/(150+100) similarity(user2=>user1)=(30+20)/(50+100) similarity(user2=>user1)=(30+20+30+20)/(150+100+50+100)

答案2、社區演算法主要是用來衡量用戶關係網中，不同用戶、鏈接、信息之間的相似程度。

本來這邊我準備講pagerank的，結果被打斷了，說需要講內部結構相關的，其實我覺得PageRank這邊來描述更加合適。不過，無所謂，我這邊談的是一個很基本的叫做：Kernighan-Lin演算法（後面簡稱了KL演算法）

KL演算法中，先隨機切分原數據集群，得到不同社區集，隨機交換不同社區集內的不同點，觀察優化值得變化程度是否為正向，循環即可。

共需執行次數：循環次數x集群A內點的個數x集群B內點的個數

感覺這邊答的不行，被嫌棄了，有知道的大神可以自行去研究一下相關的社區演算法，我這邊只了解PageRank和LK。

答案3、Q-modularity：

這個簡單，E：關係點連接線之間的個數，I：關係點連接線兩端都在社群內的數量，O：關係點連接線有至少一端在社群外的連接線的數量。

這個指標是用來衡量社群劃分的穩定性的，講真我也沒用過，只是在周志華的演算法的書上看過。

13

如果讓你設計一套推薦演算法，請說出你的思路？

講真，這個點，我起碼說了有25分種，對面的面試管也很耐心的聽完了，並且還給予了很多點的反饋，個人覺得非常受到尊重，我下面細節梳理一下。

首先，我個人非常贊同阿里現在的推薦演算法這邊的設計思路：

推薦＝人＋場景＋物

其中，

人＝新用戶＋老用戶＋綜合特徵＋...

場景＝屬性偏好＋周期屬性＋黏度偏好＋...

物＝相關性＋物品價值＋特殊屬性＋...

接下來，我簡單的剖析三個最常見也最重要的問題：

冷啟動

很多人有一種錯覺，只要業務上線時間長了就不存在所謂的冷啟動問題，實則不是，新用戶是持續進入的、流失用戶也是在增長的、很多盲目用戶（沒有有價值行為）等等都可以歸納為冷啟動問題，這類問題的核心在於你可用的數據很少，甚至沒有，我這邊採取的是熱門推薦的方法。

然而在熱門推薦的演算法中，我這邊推薦一些方法：

威爾遜區間法：綜合考慮總的行為用戶中，支持率與支持總數的平衡 hacker new排序：綜合考慮時間對支持率的影響 pagerank排序：考慮用戶流向下的頁面權重排序 梯度效率排序：考慮商品增速下的支持率的影響 ...

方法很多，但是核心的一點是熱門推薦是冷啟動及實時推薦必不可少的一環，優化好實時推薦的演算法是佔到一個好的推薦演算法的30%以上的權重的，切忌0推薦。

不同種演算法產生的推薦內容互不衝突

這個是蘇寧易購的首頁推薦位，1、2、3分別是三個推薦位，我們在做演算法的時候常常會特別注意，不能用太多相關性比較高的變數，會產生共線性，但在推薦內容上，「58同城」的演算法推薦團隊之前有一份研究證明，同一個頁面上由不同演算法產出的推薦結果不存在相互影響。

所以，我非常贊同不同的演算法產出不同的結果同時展示，因為我們不知道對目標用戶是概率模型、距離模型、線性模型等不同模型中哪個產出的結果更加合適。

關於常用的推薦演算法，我之前梳理過，這邊也不再多加重複，需要仔細研究的可看我上面的圖，或者看我之前的文章：《深度學習下的電商商品推薦》、《偏RSVD及擴展的矩陣分解方法》等等。

你的對象是用戶，不是冰冷的數字

我在蘇寧呆的時間不長，但是我有個感覺，身邊演算法工程師很容易把自己陷入數字陷阱，近乎瘋狂去用各種演算法去擬合當前的用戶數據，以求得得到高的ctr或者轉化率。

不同的推薦場景需要使用不同的用戶行為。舉例假設存在經典的關係：買了炸雞和番茄醬的用戶，接下來的一周有35%的用戶會來買汽水。所以，很多工程師會選擇只要買了炸雞和番茄醬的用戶，就彈窗汽水，因為就35%的百分比而言，是非常高的支持度了。其實只要有用戶畫像的支持就會發現，這35%的用戶中，80%的都是年齡在青少年，如果在推送之前做一個簡單的邏輯判斷只針對所有青少年進行推送汽水的話，35%輕而易舉的上升到了70%，這是任何算都無法比擬的。

最上方的橙黃色的橫條中，橙色代表原始的目標用戶，黃色代表非目標用戶，假設我們知道黑色方框所框選的用戶的轉化率達到最小置信度的時候，我們可以通過特徵映射、非線性分解、用戶畫像刻畫等不同方法得到左右完全不同的新的用戶分布，在同樣的用戶框選佔比下，效果也是完全不同的。

真實推薦中，比如針對用戶冬裝推薦，我不僅僅以用戶近期的搜索、瀏覽、購買商品等行為判斷用戶的偏好，我也根據他夏天的購買風格款式、他的年齡、生理性別、瀏覽性別等綜合判斷他可能會買什麼。推薦演算法才不會是冷漠的。

至於想要了解具體實現演算法及創新的一些想法可以看上方的腦圖，但是我覺得那並不是最重要。

14

什麼是P、NP、NP-Hard、NP-Complete問題？

P：很快可以得出解的問題

NP：一定有解，但可很快速驗證答案的問題

後面兩個我沒答出來，網上搜了下，分享下：

NP-Hard：比所有的NP問題都難的問題

NP-Complete：滿足兩點：

1、是NP-Hard的問題

2、是NP問題

個人不喜歡這種問題。

15

常見的防止過擬合的方法是什麼？為什麼l1、l2正則會防止過擬合？

當被問了第一個問題的時候，我愣了下，因為我覺得挺簡單的，為什麼要問這個，我感覺接下來有坑。

我回答的是：

先甩出了下面的圖解釋了一波欠擬合、正常、過擬合：

然後舉了幾個例子：

• 針對error遞歸的問題，l1，l2正則化
• 擴充數據量，使得數據更加符合真實分布
• bagging等演算法技巧

當問到為什麼的時候，我覺得自己回答的不好，有點蛋疼：

我說的是，l1以：

l2以：

l1中函數與約束點偏向相切於四個端點，端點處壓縮了某個特徵＝0；l2中函數與約束點偏向相切於圓，會造成某些特徵值壓縮的接近於0；

根據奧卡姆剃刀原理，當兩個假說具有完全相同的解釋力和預測力時，我們以那個較為簡單的假說作為討論依據，而通常過擬合的模型的特徵維度過高過多，所以一定程度可以緩解過擬合。

面試管以一種奇怪的眼神看著我，然後表示他其實想讓我通過先驗概率解釋，不過我這樣說彷彿也有道理。我回來之後就研究了一下，比如l2，大致如下：

首先，我們確定兩點：

l2，其實就給了係數w一個期望是0，協方差矩陣是 1/alpha的先驗分布。l1對應的是Laplace先驗。

我們相當於是給模型參數w設置一個協方差為1/alpha 的零均值高斯分布先驗。

根據貝葉斯定律：

這一步我沒看懂，我計算了半天也沒由最大似然估計算出下面這個式子，有會的朋友可以私信我一下。

有了上面的式子就很簡單了，alpha在0-正無窮之間，如果a接近0的話，左側及為正常的MSE也就是沒有做任何的懲罰。如果alpha越大的話，說明預測值越接近真實值的同時，協方差也控制的很小，模型越平穩，Var也越小，所以整體的模型更加有效，避免了過擬合導致訓練數據擬合效果很差的問題。

到這裡，我覺得常見的演算法題目都講完了，很多簡單的知識點我沒有提，上面這些算是比較經典的，我沒答出來的，希望對大家有所幫助，最後謝謝大家的閱讀。

推薦閱讀：