BAT機器學習面試1000題系列（第1~10題）

近期和，七月團隊整理了BAT機器學習面試1000題系列，側重機器學習、深度學習。我們將通過這個系列索引絕大部分機器學習和深度學習的筆試面試題、知識點，它將是一個足夠龐大的機器學習和深度學習面試庫/知識庫，通俗成體系且循序漸進。

今天將會發布【BAT機器學習面試1000題系列】前100道題的匯總和勘誤。

此外，有三點得強調下：

1.雖然本系列主要是機器學習、深度學習相關的考題，其他類型的題不多，但不代表應聘機器學習或深度學習的崗位時，公司或面試官就只問這兩項，雖說是做數據或AI相關，但基本的語言（比如Python）、編碼coding能力（對於開發，編碼coding能力怎麼強調都不過分，比如最簡單的手寫快速排序、手寫二分查找）、數據結構、演算法、計算機體系結構、操作系統、概率統計等等也必須掌握。對於數據結構和演算法，一者 重點推薦前面說的微軟面試100題系列（後來這個系列整理成了新書《編程之法：面試和演算法心得》），二者 多刷 leetcode，看1000道題不如實際動手刷100道。

2.本系列會盡量讓考察同一個部分（比如同是模型/演算法相關的）、同一個方向（比如同是屬於最優化的演算法）的題整理到一塊，為的是讓大家做到舉一反三、構建完整知識體系，在準備筆試面試的過程中，通過懂一題懂一片。

3.本系列每一道題的答案都會確保邏輯清晰、通俗易懂（當你學習某個知識點感覺學不懂時，十有八九不是你不夠聰明，十有八九是你所看的資料不夠通俗、不夠易懂），如有更好意見，歡迎在評論下共同探討。

【BAT機器學習面試1000題】

1.請簡要介紹下SVM

SVM，全稱是support vector machine，中文名叫支持向量機。SVM是一個面向數據的分類演算法，它的目標是為確定一個分類超平面，從而將不同的數據分隔開。

擴展：這裡有篇文章詳盡介紹了SVM的原理、推導，http://blog.csdn.net/v_july_v/article/details/7624837。

此外，這裡有個視頻也是關於SVM的推導：http://www.julyedu.com/video/play/18/429

2.請簡要介紹下tensorflow的計算圖

@寒小陽：Tensorflow是一個通過計算圖的形式來表述計算的編程系統，計算圖也叫數據流圖，可以把計算圖看做是一種有向圖，Tensorflow中的每一個計算都是計算圖上的一個節點，而節點之間的邊描述了計算之間的依賴關係。

3.在k-means或kNN，我們常用歐氏距離來計算最近的鄰居之間的距離，有時也用曼哈頓距離，請對比下這兩種距離的差別。

歐氏距離，最常見的兩點之間或多點之間的距離表示法，又稱之為歐幾里得度量，它定義於歐幾里得空間中，如點 x = (x1,...,xn) 和 y = (y1,...,yn) 之間的距離為：

曼哈頓距離，我們可以定義曼哈頓距離的正式意義為L1-距離或城市區塊距離，也就是在歐幾里得空間的固定直角坐標繫上兩點所形成的線段對軸產生的投影的距離總和。例如在平面上，坐標（x1, y1）的點P1與坐標（x2, y2）的點P2的曼哈頓距離為：

，要注意的是，曼哈頓距離依賴座標系統的轉度，而非系統在座標軸上的平移或映射。

通俗來講，想像你在曼哈頓要從一個十字路口開車到另外一個十字路口，駕駛距離是兩點間的直線距離嗎？顯然不是，除非你能穿越大樓。而實際駕駛距離就是這個「曼哈頓距離」，這也是曼哈頓距離名稱的來源， 同時，曼哈頓距離也稱為城市街區距離(City Block distance)。

另，關於各種距離的比較參看http://blog.csdn.net/v_july_v/article/details/8203674

4.百度2015校招機器學習筆試題

參見http://www.itmian4.com/thread-7042-1-1.html

5.關於LR

@rickjin：把LR從頭到腳都給講一遍。建模，現場數學推導，每種解法的原理，正則化，LR和maxent模型啥關係，lr為啥比線性回歸好。有不少會背答案的人，問邏輯細節就糊塗了。原理都會? 那就問工程，並行化怎麼做，有幾種並行化方式，讀過哪些開源的實現。還會，那就準備收了吧，順便逼問LR模型發展歷史。

另外，關於答案這篇文章可以做參考：

http://blog.csdn.net/cyh_24/article/details/50359055.html

http://blog.csdn.net/zouxy09/article/details/20319673

6.overfitting怎麼解決？

dropout、regularization、batch normalizatin

7.LR和SVM的聯繫與區別

@朝陽在望，聯繫：

1、LR和SVM都可以處理分類問題，且一般都用於處理線性二分類問題（在改進的情況下可以處理多分類問題）

2、兩個方法都可以增加不同的正則化項，如l1、l2等等。所以在很多實驗中，兩種演算法的結果是很接近的。

區別： 1、LR是參數模型，SVM是非參數模型。

2、從目標函數來看，區別在於邏輯回歸採用的是logistical loss，SVM採用的是hinge loss.這兩個損失函數的目的都是增加對分類影響較大的數據點的權重，減少與分類關係較小的數據點的權重。

3、SVM的處理方法是只考慮support vectors，也就是和分類最相關的少數點，去學習分類器。而邏輯回歸通過非線性映射，大大減小了離分類平面較遠的點的權重，相對提升了與分類最相關的數據點的權重。

4、邏輯回歸相對來說模型更簡單，好理解，特別是大規模線性分類時比較方便。而SVM的理解和優化相對來說複雜一些，SVM轉化為對偶問題後,分類只需要計算與少數幾個支持向量的距離,這個在進行複雜核函數計算時優勢很明顯,能夠大大簡化模型和計算。

5、logic 能做的 svm能做，但可能在準確率上有問題，svm能做的logic有的做不了。

來源：http://blog.csdn.net/timcompp/article/details/62237986

8.說說你知道的核函數

通常人們會從一些常用的核函數中選擇（根據問題和數據的不同，選擇不同的參數，實際上就是得到了不同的核函數），例如：

多項式核

，顯然剛才我們舉的例子是這裡多項式核的一個特例（R = 1，d = 2）。雖然比較麻煩，而且沒有必要，不過這個核所對應的映射實際上是可以寫出來的，該空間的維度是

，其中 m是原始空間的維度。

高斯核

，這個核就是最開始提到過的會將原始空間映射為無窮維空間的那個傢伙。不過，如果

選得很大的話，高次特徵上的權重實際上衰減得非常快，所以實際上（數值上近似一下）相當於一個低維的子空間；反過來，如果

選得很小，則可以將任意的數據映射為線性可分——當然，這並不一定是好事，因為隨之而來的可能是非常嚴重的過擬合問題。不過，總的來說，通過調控參數

，高斯核實際上具有相當高的靈活性，也是使用最廣泛的核函數之一。下圖所示的例子便是把低維線性不可分的數據通過高斯核函數映射到了高維空間：

線性核

，這實際上就是原始空間中的內積。這個核存在的主要目的是使得「映射後空間中的問題」和「映射前空間中的問題」兩者在形式上統一起來了(意思是說，咱們有的時候，寫代碼，或寫公式的時候，只要寫個模板或通用表達式，然後再代入不同的核，便可以了，於此，便在形式上統一了起來，不用再分別寫一個線性的，和一個非線性的)。

9.LR與線性回歸的區別與聯繫

@nishizhen：個人感覺邏輯回歸和線性回歸首先都是廣義的線性回歸，其次經典線性模型的優化目標函數是最小二乘，而邏輯回歸則是似然函數，另外線性回歸在整個實數域範圍內進行預測，敏感度一致，而分類範圍，需要在[0,1]。邏輯回歸就是一種減小預測範圍，將預測值限定為[0,1]間的一種回歸模型，因而對於這類問題來說，邏輯回歸的魯棒性比線性回歸的要好。

@乖乖癩皮狗：邏輯回歸的模型本質上是一個線性回歸模型，邏輯回歸都是以線性回歸為理論支持的。但線性回歸模型無法做到sigmoid的非線性形式，sigmoid可以輕鬆處理0/1分類問題。

10.請問（決策樹、Random Forest、Booting、Adaboot）GBDT和XGBoost的區別是什麼？ 關於決策樹，這裡有篇《決策樹演算法》。而隨機森林Random Forest是一個包含多個決策樹的分類器。至於AdaBoost，則是英文"Adaptive Boosting"（自適應增強）的縮寫，關於AdaBoost可以看下這篇文章《Adaboost 演算法的原理與推導》。GBDT（Gradient Boosting Decision Tree），即梯度上升決策樹演算法，相當於融合決策樹和梯度上升boosting演算法。

@Xijun LI：xgboost類似於gbdt的優化版，不論是精度還是效率上都有了提升。與gbdt相比，具體的優點有：

1.損失函數是用泰勒展式二項逼近，而不是像gbdt里的就是一階導數

2.對樹的結構進行了正則化約束，防止模型過度複雜，降低了過擬合的可能性

3.節點分裂的方式不同，gbdt是用的gini係數，xgboost是經過優化推導後的

更多詳見：https://xijunlee.github.io/2017/06/03/%E9%9B%86%E6%88%90%E5%AD%A6%E4%B9%A0%E6%80%BB%E7%BB%93/

推薦閱讀：