3月以來，「新基建」 成為熱詞，全國31個省份宣布未來投入「新基建」的投資總額已經超過40萬億！
這意味著，「新基建」所包含的七大領域：5G 基建、特高壓、城際高速鐵路和城際軌道交通、新能源汽車充電樁、大數據中心、人工智慧、工業網際網路，將迎來新的戰略增長。
其中，人工智慧在技術商業場景應用需求提升，產業規模將持續擴大。根據前瞻產業研究院預測，2020年我國人工智慧市場規模增速45%，遠超全球市場規模增速水平。
中央定調「新基建」，網際網路大廠繼續加碼人工智慧。然而，AI產業卻面臨著巨大的人才缺口！在這樣的大環境下，如果你有志應聘相關的技術崗，只有苦練內功，趁早磨刀，比如認真刷題，才有可能在面試中致勝。
以下分享2個算法崗的經典面試題，選自《百面機器學習：算法工程師帶你去面試》一書。
LDA (線性判別分析) 和 PCA 的區別與聯繫
首先將LDA 擴展到多類高維的情況，以和問題1 中PCA 的求解對應。假設有N 個類別，並需要最終將特徵降維至d 維。因此，我們要找到一個d 維投影超平面
回顧兩個散度矩陣， 類內散度矩陣
如果把全局散度定義為類內散度與類間散度之和，即St=Sb+Sw，那麼類間散度矩陣可表示為
其中mj 是第j 個類別中的樣本個數，N 是總的類別個數。從式（4.29）可以看出，類間散度表示的就是每個類別中心到全局中心的一種加權距離。我們最大化類間散度實際上優化的是每個類別的中心經過投影后離全局中心的投影足夠遠。
根據LDA 的原理，可以將最大化的目標定義為
其中W是需要求解的投影超平面，WTW=I，根據問題2 和問題3 中的部分結論，我們可以推導出最大化J(W) 對應了以下廣義特徵值求解的問題
求解最佳投影平面
即求解
矩陣特徵值前d 大對應的特徵向量組成的矩陣，這就將原始的特徵空間投影到了新的d 維空間中。至此我們得到了與PCA 步驟類似，但具有多個類別標籤高維數據的LDA 求解方法。
（1）計算數據集中每個類別樣本的均值向量μj，及總體均值向量μ。
（2）計算類內散度矩陣Sw，全局散度矩陣St，並得到類間散度矩陣
（3）對矩陣進行特徵值分解，將特徵值從大到小排列。
（4）取特徵值前d 大的對應的特徵向量
從PCA 和LDA 兩種降維方法的求解過程來看，它們確實有著很大的相似性，但對應的原理卻有所區別。
首先從目標出發，PCA 選擇的是投影后數據方差最大的方向。由於它是無監督的，因此PCA 假設方差越大，信息量越多，用主成分來表示原始數據可以去除冗餘的維度，達到降維。而LDA 選擇的是投影后類內方差小、類間方差大的方向。其用到了類別標籤信息，為了找到數據中具有判別性的維度，使得原始數據在這些方向上投影后，不同類別儘可能區分開。
舉一個簡單的例子，在語音識別中，我們想從一段音頻中提取出人的語音信號，這時可以使用PCA 先進行降維，過濾掉一些固定頻率（方差較小）的背景噪聲。但如果我們的需求是從這段音頻中區分出聲音屬於哪個人，那麼我們應該使用LDA 對數據進行降維，使每個人的語音信號具有區分性。
另外，在人臉識別領域中，PCA 和LDA 都會被頻繁使用。基於PCA 的人臉識別方法也稱為特徵臉（Eigenface）方法，該方法將人臉圖像按行展開形成一個高維向量，對多個人臉特徵的協方差矩陣做特徵值分解，其中較大特徵值對應的特徵向量具有與人臉相似的形狀，故稱為特徵臉。Eigenface for Recognition 一文中將人臉用7 個特徵臉表示（見圖4.7），於是可以把原始65536 維的圖像特徵瞬間降到7 維， 人臉識別在降維後的空間上進行。然而由於其利用PCA 進行降維，一般情況下保留的是最佳描述特徵（主成分），而非分類特徵。如果我們想要達到更好的人臉識別效果，應該用LDA 方法對數據集進行降維， 使得不同人臉在投影后的特徵具有一定區分性。
從應用的角度，我們可以掌握一個基本的原則—對無監督的任務使用PCA 進行降維，對有監督的則應用LDA。
K-均值算法收斂性的證明
首先，我們需要知道K 均值聚類的疊代算法實際上是一種最大期望算法（Expectation-Maximization algorithm），簡稱EM 算法。EM 算法解決的是在機率模型中含有無法觀測的隱含變量情況下的參數估計問題。假設有m 個觀察樣本，模型的參數為θ，最大化對數似然函數可以寫成如下形式：
當機率模型中含有無法被觀測的隱含變量時，參數的最大似然估計變為：
由於z(i) 是未知的， 無法直接通過最大似然估計求解參數， 這時就需要利用EM 算法來求解。假設z(i) 對應的分布為
，並滿足
。利用Jensen 不等式，可以得到：
要使上式中的等號成立，需要滿足
，其中c 為常數，且滿足
；因此，
，不等式右側函數記為r(x|θ)。當等式成立時，我們相當於為待優化的函數找到了一個逼近的下界，然後通過最大化這個下界可以使得待優化函數向更好的方向改進。
圖5.5 是一個θ 為一維的例子，其中棕色的曲線代表我們待優化的函數，記為f(θ)，優化過程即為找到使得f(θ) 取值最大的θ。在當前θ 的取值下（即圖中綠色的位置），可以計算
由上面的推導，EM 算法框架可以總結如下，由以下兩個步驟交替進行直到收斂（1）E 步驟：計算隱變量的期望
（2）M 步驟：最大化
剩下的事情就是說明K 均值算法與EM 算法的關係了。K 均值算法等價於用EM 算法求解以下含隱變量的最大似然問題：
其中
是模型的隱變量。直觀地理解，就是當樣本x 離第k個簇的中心點μk 距離最近時，機率正比於
，否則為0。
在E 步驟，計算
這等同於在K 均值算法中對於每一個點x(i) 找到當前最近的簇z(i)。
在M步驟，找到最優的參數
經過推導可得
因此，這一步驟等同於找到最優的中心點
......以上是《百面機器學習：算法工程師帶你去面試》中的部分精華。
15位一線算法工程師，
來自全球頂尖視頻流媒體公司hulu，
在面試過數百名候選人後，
公開124道基於真實場景的原創面試題，
歷時6個月集體編著，
上市首日即位列京東計算機新書榜第1名。
原價89元
上學季活動5折促銷，僅需44.5元哦~
此書已加入到VIP會員卡電子書庫中，只要購買VIP會員卡即可免費閱讀上百本電子書，這張VIP卡除了免費讓你讀書，還有更多的權益等你來領，往下↓拉
作者群像
《百面機器學習》學習脈絡圖
前微軟全球執行副總裁、美國工程院院士沈向洋，高度認可這本書：「這本書致力於普及人工智慧和機器學習，幫助每個軟體工程師成為自信的AI實踐者，每個數據科學家成為優秀的AI研究者。」
《浪潮之巔》《數學之美》作者吳軍亦很美譽此書：「這本書教授大家如何搭建計算機理論和算法與具體應用之間的橋樑。它可以讓計算機的從業者對理論的認識有一個飛躍，也可以讓非計算機專業的工程人員了解計算機科學這個強大的工具。」
掃碼5折購買
抓住AI風口，春招勝利，
就看《百面機器學習：算法工程師帶你去面試》！
此書已加入到VIP會員卡電子書庫中，只要購買VIP會員卡即可免費閱讀上百本電子書，這張VIP卡除了免費讓你讀書，還有更多的權益等你來領，往下↓拉
若想諮詢更多電子書或者視頻的
也可加入交流群哦~
添加小姐姐微信 備註碼書