接著上回寫的《總結(jié)：常見算法工程師面試題目整理(1)》,繼續(xù)填接下來的坑。
11.boost算法的思路是什么樣的？講一下你對adaboost 和 gbdt的了解？
答：
boost的核心思想不同于bagging，它在基于樣本預(yù)測結(jié)果對照與真實值得差距，進(jìn)行修正，再預(yù)測再修正，逐步靠近正確值。
我對adaboost和gbdt了解的也不算很全面：大概的梳理如下：
不足：
1.adaboost存在異常點敏感的問題
2.gbdt一定程度上優(yōu)化了adaboost異常點敏感的問題，但是存在難以并行的缺點
3.兩者的目標(biāo)都是優(yōu)化bias，必然導(dǎo)致訓(xùn)練出來的數(shù)據(jù)var的不穩(wěn)定
亮點：
1.發(fā)現(xiàn)非線性的特征關(guān)系，網(wǎng)格化的切分feature
2.擬合的效果相較于其他分類器更加精準(zhǔn)，且訓(xùn)練參數(shù)較少
Adaboost:
adaboost初始數(shù)據(jù)權(quán)重都是1/M，然后通過訓(xùn)練每一個弱分類器Classifier使得在每一次y_pred誤差最小，得到每一個弱Classifier的權(quán)重方法對：（αi，yi）然后提高錯分了的數(shù)據(jù)的權(quán)重，降低正確分類的數(shù)據(jù)權(quán)重，循環(huán)訓(xùn)練，最后組合最后若干次的訓(xùn)練弱Classifier對，得到強(qiáng)分類器。
其中，αi由誤差決定：
該弱分類器分類錯誤率em越大，則該若分類器作用越小。
1.剖析了原理之后，我們發(fā)現(xiàn)，這樣做對異常點非常敏感，異常點非常容易錯分，會影響后續(xù)若干個弱分類器
gbdt:
gbdt的核心在于下面這個公式：
L（y，y_pred）：預(yù)測值與實際值間的誤差
F(x):前若干個弱分類器的組合
關(guān)鍵的在于當(dāng)前預(yù)測結(jié)果=對前若干個弱分類器+當(dāng)前弱分類器修正，所以對前若干個分類器組合求偏導(dǎo)的方向進(jìn)行梯度處理，保證L（x）出來的值最小。
這邊結(jié)果在于你選取什么樣的誤差函數(shù)：
Loss即為損失函數(shù)，Derivative即為導(dǎo)數(shù)
除此之外，在每一步弱分類器構(gòu)建的同時，它還考慮了正則化：
Ω=入T+μ
*linalg.norm(f(xi))T為子葉節(jié)點數(shù)目，同時也對預(yù)測結(jié)果得分的值進(jìn)行了l1或者l2壓縮，避免過擬合。
我個人更喜歡用xgboost，在求解速度上，對異常值處理上面都要比gbdt要快，而且基于R、python版本都有package。
12.聽說你做過用戶關(guān)系，你用的什么方法？社群算法有了解，講講什么叫做Modularity Q？
1.我用的是Jaccard相關(guān)。
比如，用戶1一共收過150個紅包，發(fā)了100個紅包，其中20個被用戶2搶過
用戶2一共收過100個紅包，發(fā)了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.社區(qū)算法主要是用來衡量用戶關(guān)系網(wǎng)中，不同用戶、鏈接、信息之間的相似程度。
本來這邊我準(zhǔn)備講pagerank的，結(jié)果被打斷了，說需要講內(nèi)部結(jié)構(gòu)相關(guān)的，其實我覺得PageRank這邊來描述更加合適。不過，無所謂，我這邊談的是一個很基本的叫做：Kernighan-Lin算法（后面簡稱了KL算法）
KL算法中，先隨機(jī)切分原數(shù)據(jù)集群，得到不同社區(qū)集，隨機(jī)交換不同社區(qū)集內(nèi)的不同點，觀察優(yōu)化值得變化程度是否為正向，循環(huán)即可。
共需執(zhí)行次數(shù)：循環(huán)次數(shù)x集群A內(nèi)點的個數(shù)x集群B內(nèi)點的個數(shù)
感覺這邊答的不行，被嫌棄了，有知道的大神可以自行去研究一下相關(guān)的社區(qū)算法，我這邊只了解PageRank和LK。
3.Q-modularity：
這個簡單，E：關(guān)系點連接線之間的個數(shù)，I：關(guān)系點連接線兩端都在社群內(nèi)的數(shù)量，O：關(guān)系點連接線有至少一端在社群外的連接線的數(shù)量
這個指標(biāo)是用來衡量社群劃分的穩(wěn)定性的，講真我也沒用過，只是在周志華的算法的書上看過。
13.如果讓你設(shè)計一套推薦算法，請說出你的思路？
講真，這個點，我起碼說了有25分種，對面的面試管也很耐心的聽完了，并且還給予了很多點的反饋，個人覺得非常受到尊重，我下面細(xì)節(jié)梳理一下。
首先，我個人非常贊同阿里現(xiàn)在的推薦算法這邊的設(shè)計思路：
推薦＝人＋場景＋物
其中，
人＝新用戶＋老用戶＋綜合特征＋...
場景＝屬性偏好＋周期屬性＋黏度偏好＋...
物＝相關(guān)性＋物品價值＋特殊屬性＋...
接下來，我簡單的剖析三個最常見也最重要的問題：
- 冷啟動
很多人有一種錯覺，只要業(yè)務(wù)上線時間長了就不存在所謂的冷啟動問題，實則不是，新用戶是持續(xù)進(jìn)入的、流失用戶也是在增長的、很多盲目用戶（沒有有價值行為）等等都可以歸納為冷啟動問題，這類問題的核心在于你可用的數(shù)據(jù)很少，甚至沒有，我這邊采取的是熱門推薦的方法。
然而在熱門推薦的算法中，我這邊推薦一些方法：
威爾遜區(qū)間法：綜合考慮總的行為用戶中，支持率與支持總數(shù)的平衡
hacker new排序：綜合考慮時間對支持率的影響
pagerank排序：考慮用戶流向下的頁面權(quán)重排序
梯度效率排序：考慮商品增速下的支持率的影響
...
方法很多，但是核心的一點是熱門推薦是冷啟動及實時推薦必不可少的一環(huán)，優(yōu)化好實時推薦的算法是占到一個好的推薦算法的30%以上的權(quán)重的，切忌0推薦。
-
不同種算法產(chǎn)生的推薦內(nèi)容互不沖突
這個是蘇寧易購的首頁推薦位，1、2、3分別是三個推薦位，我們在做算法的時候常常會特別注意，不能用太多相關(guān)性比較高的變量，會產(chǎn)生共線性，但在推薦內(nèi)容上，“58同城”的算法推薦團(tuán)隊之前有一份研究證明，同一個頁面上由不同算法產(chǎn)出的推薦結(jié)果不存在相互影響。
所以，我非常贊同不同的算法產(chǎn)出不同的結(jié)果同時展示，因為我們不知道對目標(biāo)用戶是概率模型、距離模型、線性模型等不同模型中哪個產(chǎn)出的結(jié)果更加合適。
關(guān)于常用的推薦算法，我之前梳理過，這邊也不再多加重復(fù)，需要仔細(xì)研究的可看我上面的圖，或者看我之前的文章：《深度學(xué)習(xí)下的電商商品推薦》、《偏RSVD及擴(kuò)展的矩陣分解方法》等等 你的對象是用戶，不是冰冷的數(shù)字
我在蘇寧呆的時間不長，但是我有個感覺，身邊算法工程師很容易把自己陷入數(shù)字陷阱，近乎瘋狂去用各種算法去擬合當(dāng)前的用戶數(shù)據(jù)，以求得得到高的ctr或者轉(zhuǎn)化率。
不同的推薦場景需要使用不同的用戶行為。舉例假設(shè)存在經(jīng)典的關(guān)系：買了炸雞和番茄醬的用戶，接下來的一周有35%的用戶會來買汽水。所以，很多工程師會選擇只要買了炸雞和番茄醬的用戶，就彈窗汽水，因為就35%的百分比而言，是非常高的支持度了。其實只要有用戶畫像的支持就會發(fā)現(xiàn)，這35%的用戶中，80%的都是年齡在青少年，如果在推送之前做一個簡單的邏輯判斷只針對所有青少年進(jìn)行推送汽水的話，35%輕而易舉的上升到了70%，這是任何算都無法比擬的。
最上方的橙黃色的橫條中，橙色代表原始的目標(biāo)用戶，黃色代表非目標(biāo)用戶，假設(shè)我們知道黑色方框所框選的用戶的轉(zhuǎn)化率達(dá)到最小置信度的時候，我們可以通過特征映射、非線性分解、用戶畫像刻畫等不同方法得到左右完全不同的新的用戶分布，在同樣的用戶框選占比下，效果也是完全不同的。
真實推薦中，比如針對用戶冬裝推薦，我不僅僅以用戶近期的搜索、瀏覽、購買商品等行為判斷用戶的偏好，我也根據(jù)他夏天的購買風(fēng)格款式、他的年齡、生理性別、瀏覽性別等綜合判斷他可能會買什么。推薦算法才不會是冷漠的。
至于想要了解具體實現(xiàn)算法及創(chuàng)新的一些想法可以看上方的腦圖，但是我覺得那并不是最重要。
14.什么是P、NP、NP-Hard、NP-Complete問題？
P：很快可以得出解的問題
NP：一定有解，但可很快速驗證答案的問題
后面兩個我沒答出來，網(wǎng)上搜了下，分享下：
NP-Hard：比所有的NP問題都難的問題
NP-Complete：滿足兩點：
- 是NP-Hard的問題
- 是NP問題
個人不喜歡這種問題。
15.常見的防止過擬合的方法是什么？為什么l1、l2正則會防止過擬合？
當(dāng)被問了第一個問題的時候，我愣了下，因為我覺得挺簡單的，為什么要問這個，我感覺接下來有坑。
我回答的是：
先甩出了下面的圖解釋了一波欠擬合、正常、過擬合：
然后舉了幾個例子：
- 針對error遞歸的問題，l1，l2正則化
- 擴(kuò)充數(shù)據(jù)量，使得數(shù)據(jù)更加符合真實分布
- bagging等算法技巧
當(dāng)問到為什么的時候，我覺得自己回答的不好，有點蛋疼：
我說的是，l1以：
l2以：
l1中函數(shù)與約束點偏向相切于四個端點，端點處壓縮了某個特征＝0；l2中函數(shù)與約束點偏向相切于圓，會造成某些特征值壓縮的接近于0；
根據(jù)奧卡姆剃刀原理，當(dāng)兩個假說具有完全相同的解釋力和預(yù)測力時，我們以那個較為簡單的假說作為討論依據(jù)，而通常過擬合的模型的特征維度過高過多，所以一定程度可以緩解過擬合。
面試管以一種奇怪的眼神看著我，然后表示他其實想讓我通過先驗概率解釋，不過我這樣說仿佛也有道理。我回來之后就研究了一下，比如l2，大致如下：
首先，我們確定兩點：
l2，其實就給了系數(shù)w一個期望是0，協(xié)方差矩陣是 1/alpha的先驗分布。l1對應(yīng)的是Laplace先驗。
我們相當(dāng)于是給模型參數(shù)w設(shè)置一個協(xié)方差為1/alpha 的零均值高斯分布先驗。
根據(jù)貝葉斯定律：
這一步我沒看懂，我計算了半天也沒由最大似然估計算出下面這個式子，有會的朋友可以私信我一下。
有了上面的式子就很簡單了，alpha在0-正無窮之間，如果a接近0的話，左側(cè)及為正常的MSE也就是沒有做任何的懲罰。如果alpha越大的話，說明預(yù)測值越接近真實值的同時，協(xié)方差也控制的很小，模型越平穩(wěn)，Var也越小，所以整體的模型更加有效，避免了過擬合導(dǎo)致訓(xùn)練數(shù)據(jù)擬合效果很差的問題。
到這里，我覺得常見的算法題目都講完了，很多簡單的知識點我沒有提，上面這些算是比較經(jīng)典的，我沒答出來的，希望對大家有所幫助，最后謝謝大家的閱讀。
歡迎大家關(guān)注我的個人bolg，更多代碼內(nèi)容歡迎follow我的個人Github，如果有任何算法、代碼疑問都?xì)g迎通過公眾號發(fā)消息給我哦。
