接着上回寫的《總結：常見算法工程師面試題目整理(1)》,繼續填接下來的坑。
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越大，則該若分類器作用越小。
1.剖析了原理之後，我們發現，這樣做對異常點非常敏感，異常點非常容易錯分，會影響後續若幹個弱分類器
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？
1.我用的是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：滿足兩點：
- 是NP-Hard的問題
- 是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也越小，是以整體的模型更加有效，避免了過拟合導緻訓練資料拟合效果很差的問題。
到這裡，我覺得常見的算法題目都講完了，很多簡單的知識點我沒有提，上面這些算是比較經典的，我沒答出來的，希望對大家有所幫助，最後謝謝大家的閱讀。