演算法工程師養成記

科技 08-25

通往機器學習演算法工程師的進階之路是崎嶇險阻的。《線性代數》《統計學習方法》《機器學習》《模式識別》《深度學習》，以及《頸椎病康復指南》，這些書籍將長久地伴隨著你的工作生涯。

*編輯配圖

除了擁有全面、有條理的知識儲備，我認為，想成為一名優秀的演算法工程師，更重要的是對演算法模型有著發自心底的熱忱，對研究工作有一種匠心精神。這種匠心精神，直白來講，可以概括為：發現問題的眼光、解決問題的探索精神，以及對問題究原竟委的執著追求。這裡，我想給大家分享一個發生在我身邊的真實情景。

在微信紅包佔領家家戶戶年夜飯的那個時代，我們的小夥伴也沒有例外。一群心有猛虎、細嗅薔薇的演算法研究員深切意識到自己不僅手速慢，運氣也可謂糟糕。在埋頭瘋點手機屏幕的間隙，他們查閱了搶紅包策略的相關文獻，發現國內外對這一理論框架的探究極度匱乏。

知識拯救命運，他們決定將紅包機制的公平性提升到理論高度。通過大量的模擬實驗，統計在不同順位領到紅包的大小。數據分析顯示，越後面領到紅包的人，雖然紅包金額的期望（均值）和前面的人相同，但方差會更大，這也意味著他們更容易獲得一些大額紅包。從此，掌握這一規律的研究員們在各個群中「屢試不爽」，再也沒有搶到過紅包，留下的只有「手慢了，紅包派完了」幾個大字。

*編輯配圖

新年鐘聲敲響的時分臨近，Boss級別的人物往往會在群里發一些超級大額的紅包。最誇張的一次有一位幸運兒在10人紅包中領到2角錢，還沒來得及在心中完成「老闆真摳門」的碎碎念，抬頭定睛一看，最佳手氣500多元。判若雲泥的手氣雖沒有埋下同事關係間的芥蒂，卻讓這幫演算法工程師們產生了新的思考—如果把大額紅包分成多份給大家搶，會減小「人品」因素帶來的「貧富差距」嗎？理論結合實際，他們不僅通過數學推導確認這一結論，還設計了一系列實驗證明了多個紅包的確會縮小不同人領到紅包金額之間的差異性（方差）。從此，他們組的Leader在發大紅包的時候都會刻意平均分成幾份，既增加了大家搶紅包的樂趣，又避免了有人因運氣不佳而扼腕興嘆的憤懣。

當然，故事不止於此。他們還利用紅包的特性編寫了一系列面試題——《百面機器學習——演算法工程師帶你去面試》，篩選著一批又一批的機器學習演算法工程師。

*編輯配圖

工作中的演算法工程師，很多時候，會將生活中轉瞬即逝的靈感，付諸產品化。

將演算法研究應用到工作中，與純粹的學術研究有著一點最大的不同，即需要從用戶的角度思考問題。很多時候，你需要明確設計的產品特徵、提升的數據指標，是不是能真正迎合用戶的需求，這便要求演算法工程師能在多個模型間選擇出最合適的那個，然後通過快速迭代達到一個可以走向產品化的結果。這種創新精神與嘗試精神便是「匠心」一詞在工作中的體現。

當然，匠心精神誠可貴，知識儲備作為成功的根底亦必不可少，以下是營長為你精選的演算法面試，幫你檢查下自己的技能是否在線。

*編輯配圖

▌1. LDA(線性判別分析) 和 PCA 的區別與聯繫

首先將LDA 擴展到多類高維的情況，以和問題1 中PCA 的求解對應。假設有N 個類別，並需要最終將特徵降維至d 維。因此，我們要找到一個d 維投影超平面，使得投影后的樣本點滿足LDA 的目標—最大化類間距離和最小化類內距離。

回顧兩個散度矩陣，類內散度矩陣在類別增加至 N 時仍滿足定義，而之前兩類問題的類間散度矩陣在類別增加後就無法按照原始定義。圖4.6 是三類樣本的分布情況，其中分別表示棕綠黃三類樣本的中心，μ 表示這三個中心的均值（也即全部樣本的中心），Swi表示第i 類的類內散度。我們可以定義一個新的矩陣St，來表示全局整體的散度，稱為全局散度矩陣

如果把全局散度定義為類內散度與類間散度之和，即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 大的對應的特徵向量，通過以下映射將n 維樣本映射到d 維

從PCA 和LDA 兩種降維方法的求解過程來看，它們確實有著很大的相似性，但對應的原理卻有所區別。

首先從目標出發，PCA 選擇的是投影后數據方差最大的方向。由於它是無監督的，因此PCA 假設方差越大，信息量越多，用主成分來表示原始數據可以去除冗餘的維度，達到降維。而LDA 選擇的是投影后類內方差小、類間方差大的方向。其用到了類別標籤信息，為了找到數據中具有判別性的維度，使得原始數據在這些方向上投影后，不同類別儘可能區分開。

舉一個簡單的例子，在語音識別中，我們想從一段音頻中提取出人的語音信號，這時可以使用PCA 先進行降維，過濾掉一些固定頻率（方差較小）的背景雜訊。但如果我們的需求是從這段音頻中區分出聲音屬於哪個人，那麼我們應該使用LDA 對數據進行降維，使每個人的語音信號具有區分性。

另外，在人臉識別領域中，PCA 和LDA 都會被頻繁使用。基於PCA 的人臉識別方法也稱為特徵臉（Eigenface）方法，該方法將人臉圖像按行展開形成一個高維向量，對多個人臉特徵的協方差矩陣做特徵值分解，其中較大特徵值對應的特徵向量具有與人臉相似的形狀，故稱為特徵臉。Eigenface forRecognition 一文中將人臉用7 個特徵臉表示（見圖4.7），於是可以把原始65536 維的圖像特徵瞬間降到7 維，人臉識別在降維後的空間上進行。然而由於其利用PCA 進行降維，一般情況下保留的是最佳描述特徵（主成分），而非分類特徵。如果我們想要達到更好的人臉識別效果，應該用LDA 方法對數據集進行降維，使得不同人臉在投影后的特徵具有一定區分性。

從應用的角度，我們可以掌握一個基本的原則—對無監督的任務使用PCA 進行降維，對有監督的則應用LDA。

▌2.K-均值演算法收斂性的證明

首先，我們需要知道K 均值聚類的迭代演算法實際上是一種最大期望演算法（Expectation-Maximizationalgorithm），簡稱EM演算法。EM演算法解決的是在概率模型中含有無法觀測的隱含變數情況下的參數估計問題。假設有m 個觀察樣本，模型的參數為θ，最大化對數似然函數可以寫成如下形式

當概率模型中含有無法被觀測的隱含變數時，參數的最大似然估計變為

由於z(i) 是未知的，無法直接通過最大似然估計求解參數，這時就需要利用EM 演算法來求解。假設z(i) 對應的分布為，並滿足。利用Jensen 不等式，可以得到

要使上式中的等號成立，需要滿足

其中c 為常數，且滿足

因此

不等式右側函數記為r(x|θ)。當等式成立時，我們相當於為待優化的函數找到了一個逼近的下界，然後通過最大化這個下界可以使得待優化函數向更好的方向改進。

圖5.5 是一個θ 為一維的例子，其中棕色的曲線代表我們待優化的函數，記為f(θ)，優化過程即為找到使得f(θ) 取值最大的θ。在當前θ 的取值下（即圖中綠色的位置），可以計算，此時不等式右側的函數（記為r(x|θ)）給出了優化函數的一個下界，如圖中藍色曲線所示，其中在θ 處兩條曲線的取值時相等的。接下來找到使得r(x|θ) 最大化的參數θ′，即圖中紅色的位置，此時f(θ′) 的取值比f(θ)（綠色的位置處）有所提升。可以證明，f(θ′) ≥ r(x|θ)=f(θ)，因此函數是單調的，而且從而函數是有界的。根據函數單調有界必收斂的性質，EM 演算法的收斂性得證。但是EM 演算法只保證收斂到局部最優解。當函數為非凸時，以圖5.5 為例，如果初始化在左邊的區域時，則無法找到右側的高點。

由上面的推導，EM 演算法框架可以總結如下，由以下兩個步驟交替進行直到收斂。

（1）E 步驟：計算隱變數的期望

（2）M 步驟：最大化

剩下的事情就是說明K 均值演算法與EM 演算法的關係了。K 均值演算法等價於用EM 演算法求解以下含隱變數的最大似然問題：

其中是模型的隱變數。直觀地理解，就是當樣本x 離第k個簇的中心點μk 距離最近時，概率正比於，否則為0。

在 E 步驟，計算

這等同於在K 均值演算法中對於每一個點x(i) 找到當前最近的簇z(i)。

在M步驟，找到最優的參數，使得似然函數最大：

經過推導可得

因此，這一步驟等同於找到最優的中心點，使得損失函數

達到最小，此時每個樣本x(i) 對應的簇z(i) 已確定，因此每個簇k 對應的最優中心點μk 可以由該簇中所有點的平均計算得到，這與K 均值演算法中根據當前簇的分配更新聚類中心的步驟是等同的。

▌3.如何確定 LDA (隱狄利克雷模型) 中主題的個數

在LDA中，主題的個數K 是一個預先指定的超參數。對於模型超參數的選擇，實踐中的做法一般是將全部數據集分成訓練集、驗證集、和測試集3 部分，然後利用驗證集對超參數進行選擇。例如，在確定LDA 的主題個數時，我們可以隨機選取60% 的文檔組成訓練集，另外20% 的文檔組成驗證集，剩下20% 的文檔組成測試集。在訓練時，嘗試多組超參數的取值，並在驗證集上檢驗哪一組超參數所對應的模型取得了最好的效果。最終，在驗證集上效果最好的一組超參數和其對應的模型將被選定，並在測試集上進行測試。

為了衡量LDA 模型在驗證集和測試集上的效果，需要尋找一個合適的評估指標。一個常用的評估指標是困惑度（perplexity）。在文檔集合D 上，模型的困惑度被定義為

其中 M 為文檔的總數，wd 為文檔 d 中單詞所組成的詞袋向量，p(wd) 為模型所預測的文檔d 的生成概率，Nd 為文檔d 中單詞的總數。

一開始，隨著主題個數的增多，模型在訓練集和驗證集的困惑度呈下降趨勢，但是當主題數目足夠大的時候，會出現過擬合，導致困惑度指標在訓練集上繼續下降但在驗證集上反而增長。這時，可以取驗證集的困惑度極小值點所對應的主題個數作為超參數。在實踐中，困惑度的極小值點可能出現在主題數目非常大的時候，然而實際應用並不能承受如此大的主題數目，這時就需要在實際應用中合理的主題數目範圍內進行選擇，比如選擇合理範圍內困惑度的下降明顯變慢（拐點）的時候。

另外一種方法是在LDA 基礎之上融入分層狄利克雷過程（Hierarchical Dirichlet Process，HDP），構成一種非參數主題模型HDP-LDA。非參數主題模型的好處是不需要預先指定主題的個數，模型可以隨著文檔數目的變化而自動對主題個數進行調整；它的缺點是在LDA 基礎上融入HDP 之後使得整個概率圖模型更加複雜，訓練速度也更加緩慢，因此在實際應用中還是經常採用第一種方法確定合適的主題數目。

▌4.隨機梯度下降法的一些改進演算法

隨機梯度下降法本質上是採用迭代方式更新參數，每次迭代在當前位置的基礎上，沿著某一方向邁一小步抵達下一位置，然後在下一位置重複上述步驟。隨機梯度下降法的更新公式表示為

其中，當前估計的負梯度?gt 表示步子的方向，學習速率η 控制步幅。改造的隨機梯度下降法仍然基於這個更新公式。

動量（Momentum）方法

為了解決隨機梯度下降法山谷震蕩和鞍點停滯的問題，我們做一個簡單的思維實驗。想像一下紙團在山谷和鞍點處的運動軌跡，在山谷中紙團受重力作用沿山道滾下，兩邊是不規則的山壁，紙團不可避免地撞在山壁，由於質量小受山壁彈力的干擾大，從一側山壁反彈回來撞向另一側山壁，結果來回震蕩地滾下；如果當紙團來到鞍點的一片平坦之地時，還是由於質量小，速度很快減為零。紙團的情況和隨機梯度下降法遇到的問題簡直如出一轍。直觀地，如果換成一個鐵球，當沿山谷滾下時，不容易受到途中旁力的干擾，軌跡會更穩更直；當來到鞍點中心處，在慣性作用下繼續前行，從而有機會衝出這片平坦的陷阱。因此，有了動量方法，模型參數的迭代公式為

具體來說，前進步伐?vt由兩部分組成。一是學習速率η乘以當前估計的梯度gt；二是帶衰減的前一次步伐vt?1。這裡，慣性就體現在對前一次步伐信息的重利用上。類比中學物理知識，當前梯度就好比當前時刻受力產生的加速度，前一次步伐好比前一時刻的速度，當前步伐好比當前時刻的速度。為了計算當前時刻的速度，應當考慮前一時刻速度和當前加速度共同作用的結果，因此vt直接依賴於vt?1和gt，而不僅僅是gt。另外，衰減係數γ扮演了阻力的作用。

中學物理還告訴我們，刻畫慣性的物理量是動量，這也是演算法名字的由來。沿山谷滾下的鐵球，會受到沿坡道向下的力和與左右山壁碰撞的彈力。向下的力穩定不變，產生的動量不斷累積，速度越來越快；左右的彈力總是在不停切換，動量累積的結果是相互抵消，自然減弱了球的來回震蕩。因此，與隨機梯度下降法相比，動量方法的收斂速度更快，收斂曲線也更穩定，如圖7.5 所示。

AdaGrad 方法

慣性的獲得是基於歷史信息的，那麼，除了從過去的步伐中獲得一股子向前沖的勁兒，還能獲得什麼呢？我們還期待獲得對周圍環境的感知，即使蒙上雙眼，依靠前幾次邁步的感覺，也應該能判斷出一些信息，比如這個方向總是坑坑窪窪的，那個方向可能很平坦。

隨機梯度下降法對環境的感知是指在參數空間中，根據不同參數的一些經驗性判斷，自適應地確定參數的學習速率，不同參數的更新步幅是不同的。例如，在文本處理中訓練詞嵌入模型的參數時，有的詞或片語頻繁出現，有的詞或片語則極少出現。數據的稀疏性導致相應參數的梯度的稀疏性，不頻繁出現的詞或片語的參數的梯度在大多數情況下為零，從而這些參數被更新的頻率很低。在應用中，我們希望更新頻率低的參數可以擁有較大的更新步幅，而更新頻率高的參數的步幅可以減小。

AdaGrad 方法採用「歷史梯度平方和」來衡量不同參數的梯度的稀疏性，取值越小表明越稀疏，具體的更新公式表示為

其中θt+1,i 表示（t+1）時刻的參數向量θt+1的第i個參數，gk,i表示k時刻的梯度向量gk 的第i 個維度（方向）。另外，分母中求和的形式實現了退火過程，這是很多優化技術中常見的策略，意味著隨著時間推移，學習速率越

來越小，從而保證了演算法的最終收斂。

Adam 方法

Adam 方法將慣性保持和環境感知這兩個優點集於一身。一方面， Adam 記錄梯度的一階矩（first moment），即過往梯度與當前梯度的平均，這體現了慣性保持；另一方面，Adam 還記錄梯度的二階矩（second moment），即過往梯度平方與當前梯度平方的平均，這類似AdaGrad 方法，體現了環境感知能力，為不同參數產生自適應的學習速率。一階矩和二階矩採用類似於滑動窗口內求平均的思想進行融合，即當前梯度和近一段時間內梯度的平均值，時間久遠的梯度對當前平均值的貢獻呈指數衰減。具體來說，一階矩和二階矩採用指數衰退平均（exponential decayaverage）技術，計算公式為

其中β1，β2 為衰減係數，mt 是一階矩，vt 是二階矩。

如何理解一階矩和二階矩呢？一階矩相當於估計：由於當下梯度gt 是隨機採樣得到的估計結果，因此更關注它在統計意義上的期望；二階矩相當於估計，這點與AdaGrad 方法不同，不是gt2從開始到現在的加和，而是它的期望。它們的物理意義是，當||mt||大且vt 大時，梯度大且穩定，這表明遇到一個明顯的大坡，前進方向明確；當||mt||趨於零且vt大時，梯度不穩定，表明可能遇到一個峽谷，容易引起反彈震蕩；當||mt||大且vt趨於零時，這種情況不可能出現；當||mt|| 趨於零且vt 趨於零時，梯度趨於零，可能到達局部最低點，也可能走到一片坡度極緩的平地，此時要避免陷入平原（plateau）。另外，Adam 方法還考慮了mt，vt 在零初始值情況下的偏置矯正。具體來說，Adam 的更新公式為

其中,

▌5.L1正則化產生稀疏性的原因

角度1：解空間形狀

機器學習的經典之作給出的解釋無疑是權威且直觀的，面試者給出的答案多數也是從這個角度出發的。在二維的情況下，黃色的部分是L2 和L1 正則項約束後的解空間，綠色的等高線是凸優化問題中目標函數的等高線，如圖7.6 所示。由圖可知，L2 正則項約束後的解空間是圓形，而L1 正則項約束的解空間是多邊形。顯然，多邊形的解空間更容易在尖角處與等高線碰撞出稀疏解。

上述這個解釋無疑是正確的，但卻不夠精確，面試者往往回答過於籠統，以至於忽視了幾個關鍵問題。比如，為什麼加入正則項就是定義了一個解空間約束？為什麼L1 和L2的解空間是不同的？面試官如果深究下去，很多面試者難以給出滿意的答案。其實可以通過KKT條件給出一種解釋。

事實上，「帶正則項」和「帶約束條件」是等價的。為了約束w 的可能取值空間從而防止過擬合，我們為該最優化問題加上一個約束，就是w 的L2 範數的平方不能大於m：

為了求解帶約束條件的凸優化問題，寫出拉格朗日函數

若w* 和λ* 分別是原問題和對偶問題的最優解，則根據KKT 條件，它們應滿足

仔細一看，第一個式子不就是w* 為帶L2 正則項的優化問題的最優解的條件嘛，而λ* 就是L2 正則項前面的正則參數。

這時回頭再看開頭的問題就清晰了。L2 正則化相當於為參數定義了一個圓形的解空間（因為必須保證L2 範數不能大於m），而L1 正則化相當於為參數定義了一個棱形的解空間。如果原問題目標函數的最優解不是恰好落在解空間內，那麼約束條件下的最優解一定是在解空間的邊界上，而L1「稜角分明」的解空間顯然更容易與目標函數等高線在角點碰撞，從而產生稀疏解。

角度2：函數疊加

第二個角度試圖用更直觀的圖示來解釋L1 產生稀疏性這一現象。僅考慮一維的情況，多維情況是類似的，如圖7.7 所示。假設棕線是原始目標函數L(w) 的曲線圖，顯然最小值點在藍點處，且對應的w* 值非0。

首先，考慮加上L2正則化項，目標函數變成L(w)+Cw2，其函數曲線為黃色。此時，最小值點在黃點處，對應的w* 的絕對值減小了，但仍然非0。

然後，考慮加上L1 正則化項，目標函數變成L(w)+C|w|，其函數曲線為綠色。此時，最小值點在紅點處，對應的w 是0，產生了稀疏性。

產生上述現象的原因也很直觀。加入L1 正則項後，對帶正則項的目標函數求導，正則項部分產生的導數在原點左邊部分是?C，在原點右邊部分是C，因此，只要原目標函數的導數絕對值小於C，那麼帶正則項的目標函數在原點左邊部分始終是遞減的，在原點右邊部分始終是遞增的，最小值點自然在原點處。相反，L2 正則項在原點處的導數是0，只要原目標函數在原點處的導數不為0，那麼最小值點就不會在原點，所以L2 只有減小w 絕對值的作用，對解空間的稀疏性沒有貢獻。

在一些在線梯度下降演算法中，往往會採用截斷梯度法來產生稀疏性，這同L1 正則項產生稀疏性的原理是類似的。

角度3：貝葉斯先驗

從貝葉斯的角度來理解L1 正則化和L2 正則化，簡單的解釋是， L1 正則化相當於對模型參數w 引入了拉普拉斯先驗，L2 正則化相當於引入了高斯先驗，而拉普拉斯先驗使參數為0 的可能性更大。

圖7.8 是高斯分布曲線圖。由圖可見，高斯分布在極值點（0 點）處是平滑的，也就是高斯先驗分布認為w 在極值點附近取不同值的可能性是接近的。這就是L2 正則化只會讓w 更接0點，但不會等於0 的原因。

相反，圖7.9 是拉普拉斯分布曲線圖。由圖可見，拉普拉斯分布在極值點（0 點）處是一個尖峰，所以拉普拉斯先驗分布中參數w 取值為0 的可能性要更高。在此我們不再給出L1 和L2 正則化分別對應拉普拉斯先驗分布和高斯先驗分布的詳細證明。

▌6.如何對貝葉斯網路進行採樣

對一個沒有觀測變數的貝葉斯網路進行採樣，最簡單的方法是祖先採樣（Ancestral Sampling），它的核心思想是根據有向圖的順序，先對祖先節點進行採樣，只有當某個節點的所有父節點都已完成採樣，才對該節點進行採樣。以場景描述中的圖8.9 為例，先對Cloudy 變數進行採樣，然後再對Sprinkler 和Rain 變數進行採樣，最後對WetGrass 變數採樣，如圖8.10 所示（圖中綠色表示變數取值為True，紅色表示取值為False）。根據貝葉斯網路的全概率公式

可以看出祖先採樣得到的樣本服從貝葉斯網路的聯合概率分布。

如果只需要對貝葉斯網路中一部分隨機變數的邊緣分布進行採樣，可以用祖先採樣先對全部隨機變數進行採樣，然後直接忽視那些不需要的變數的採樣值即可。由圖可見，如果需要對邊緣分布p(Rain) 進行採樣，先用祖先採樣得到全部變數的一個樣本，如（Cloudy=T， Sprinkler=F，Rain=T，WetGrass=T），然後忽略掉無關變數，直接把這個樣本看成是Cloudy=T 即可。

接下來考慮含有觀測變數的貝葉斯網路的採樣，如圖8.11 所示。網路中有觀測變數（Sprikler=T，WetGrass=T）（觀測變數用斜線陰影表示），又該如何採樣呢？最直接的方法是邏輯採樣，還是利用祖先採樣得到所有變數的取值。如果這個樣本在觀測變數上的採樣值與實際觀測值相同，則接受，否則拒絕，重新採樣。這種方法的缺點是採樣效率可能會非常低，隨著觀測變數個數的增加、每個變數狀態數目的上升，邏輯採樣法的採樣效率急劇下降，實際中基本不可用。

因此，在實際應用中，可以參考重要性採樣的思想，不再對觀測變數進行採樣，只對非觀測變數採樣，但是最終得到的樣本需要賦一個重要性權值：

其中E 是觀測變數集合。這種採樣方法稱作似然加權採樣（Likelihood Weighted Sampling），產生的樣本權值可以用於後續的積分操作。在有觀測變數（Sprikler=T，WetGrass=T）時，可以先對Cloudy 進行採樣，然後對Rain 進行採樣，不再對Sprinkler 和WetGrass 採樣（直接賦觀測值），如圖8.12 所示。這樣得到的樣本的重要性權值為

w ∝ p(Sprinkler=T|Cloudy=T)·p(WetGrass=T|Sprinkler=T，Rain=T)=0.1×0.99=0.099.

除此之外，還可以用MCMC採樣法來進行採樣。具體來說，如果採用Metropolis-Hastings 採樣法的話，如圖8.13所示，只需要在隨機向量（Cloudy, 、Rain）上選擇一個概率轉移矩陣，然後按照概率轉移矩陣不斷進行狀態轉換，每次轉移有一定概率的接受或拒絕，最終得到的樣本序列會收斂到目標分布。最簡單的概率轉移矩陣可以是：每次獨立地隨機選擇（Cloudy, Rain）的四種狀態之一。如果採用吉布斯採樣法的話，根據條件概率p(Cloudy|Rain,Sprinkler, WetGrass) 和p(Rain|Cloudy, Sprinkler,WetGrass)，每次只對（Cloudy, Rain）中的一個變數進行採樣，交替進行即可。

▌7.從方差、偏差角度解釋 Boosting 和 Bagging

簡單回答這個問題就是：Bagging能夠提高弱分類器性能的原因是降低了方差，Boosting能夠提升弱分類器性能的原因是降低了偏差。為什麼這麼講呢？

首先，Bagging是 Bootstrap Aggregating 的簡稱，意思就是再抽樣，然後在每個樣本上訓練出來的模型取平均。

假設有n 個隨機變數，方差記為σ2，兩兩變數之間的相關性為ρ，則n 個隨機變數的均值的方差為。在隨機變數完全獨立的情況下，n 個隨機變數的方差為σ2/n，也就是說方差減小到了原來的1/n。

再從模型的角度理解這個問題，對n 個獨立不相關的模型的預測結果取平均，方差是原來單個模型的1/n。這個描述不甚嚴謹，但原理已經講得很清楚了。當然，模型之間不可能完全獨立。為了追求模型的獨立性，諸多Bagging 的方法做了不同的改進。比如在隨機森林演算法中，每次選取節點分裂屬性時，會隨機抽取一個屬性子集，而不是從所有屬性中選取最優屬性，這就是為了避免弱分類器之間過強的相關性。通過訓練集的重採樣也能夠帶來弱分類器之間的一定獨立性，從而降低Bagging 後模型的方差。

再看Boosting，大家應該還記得Boosting 的訓練過程。在訓練好一個弱分類器後，我們需要計算弱分類器的錯誤或者殘差，作為下一個分類器的輸入。這個過程本身就是在不斷減小損失函數，來使模型不斷逼近「靶心」，使得模型偏差不斷降低。但Boosting 的過程並不會顯著降低方差。這是因為Boosting 的訓練過程使得各弱分類器之間是強相關的，缺乏獨立性，所以並不會對降低方差有作用。

關於泛化誤差、偏差、方差和模型複雜度的關係如圖12.5 所示。不難看出，方差和偏差是相輔相成，矛盾又統一的，二者並不能完全獨立的存在。對於給定的學習任務和訓練數據集，我們需要對模型的複雜度做合理的假設。如果模型複雜度過低，雖然方差很小，但是偏差會很高；如果模型複雜度過高，雖然偏差降低了，但是方差會很高。所以需要綜合考慮偏差和方差選擇合適複雜度的模型進行訓練。

▌8.ResNet的提出背景和核心理論

ResNet的提出背景是解決或緩解深層的神經網路訓練中的梯度消失問題。假設有一個L 層的深度神經網路，如果我們在上面加入一層，直觀來講得到的L+1 層深度神經網路的效果應該至少不會比L 層的差。因為我們簡單地設最後一層為前一層的拷貝（用一個恆等映射即可實現），並且其他層維持原來的參數即可。然而在進行反向傳播時，我們很難找到這種形式的解。實際上，通過實驗發現，層數更深的神經網路反而會具有更大的訓練誤差。在CIFAR-10 數據集上的一個結果如圖9.22 所示，56 層的網路反而比20 層的網路訓練誤差更大，這很大程度上歸結於深度神經網路的梯度消失問題。

為了解釋梯度消失問題是如何產生的。回顧第3 節推導出的誤差傳播公式

將式（9.31）再展開一層，可以得到

可以看到誤差傳播可以寫成參數、以及導數、連乘的形式。當誤差由第L 層（記為）傳播到除輸入以外的第一個隱含層（記為）的時候，會涉及非常多的參數和導數的連乘，這時誤差很容易產生消失或者膨脹，影響對該層參數的正確學習。因此深度神經網路的擬合和泛化能力較差，有時甚至不如淺層的神經網路模型精度更高。

ResNet過調整網路結構來解決上述問題。首先考慮兩層神經網路的簡單疊加（見圖9.23（a）），這時輸入x 經過兩個網路層的變換得到H(x)，激活函數採用ReLU。反向傳播時，梯度將涉及兩層參數的交叉相乘，可能會在離輸入近的網路層中產生梯度消失的現象。ResNet 把網路結構調整為，既然離輸入近的神經網路層較難訓練，那麼我們可以將它短接到更靠近輸出的層，如圖9.23（b）所示。輸入x經過兩個神經網路的變換得到F(x)，同時也短接到兩層之後，最後這個包含兩層的神經網路模塊輸出H(x)=F(x)+x。

這樣一來，F(x) 被設計為只需要擬合輸入x 與目標輸出的殘差，殘差網路的名稱也因此而來。如果某一層的輸出已經較好的擬合了期望結果，那麼多加入一層不會使得模型變得更差，因為該層的輸出將直接被短接到兩層之後，相當於直接學習了一個恆等映射，而跳過的兩層只需要擬合上層輸出和目標之間的殘差即可。

ResNet 可以有效改善深層的神經網路學習問題，使得訓練更深的網路成為可能，如圖9.24 所示。圖9.24（a）展示的是傳統神經網路的結果，可以看到隨著模型結構的加深訓練誤差反而上升；而圖9.24（b）是ResNet 的實驗結果，隨著模型結構的加深，訓練誤差逐漸降低，並且優於相同層數的傳統的神經網路。

▌9.LSTM是如何實現長短期記憶功能的

有圖有真相，我們首先結合LSTM 結構圖以及更新的計算公式探討這種網路如何實現其功能，如圖10.2 所示。

與傳統的循環神經網路相比，LSTM 仍然是基於xt 和ht?1來計算ht，只不過對內部的結構進行了更加精心的設計，加入了輸入門it、遺忘門ft以及輸出門ot 三個門和一個內部記憶單元ct。輸入門控制當前計算的新狀態以多大程度更新到記憶單元中；遺忘門控制前一步記憶單元中的信息有多大程度被遺忘掉；輸出門控制當前的輸出有多大程度上取決於當前的記憶單元。

經典的LSTM 中，第t 步的更新計算公式為

其中it是通過輸入xt和上一步的隱含層輸出ht?1進行線性變換，再經過激活函數σ 得到的。輸入門it的結果是向量，其中每個元素是0 到1 之間的實數，用於控制各維度流過閥門的信息量；Wi、Ui兩個矩陣和向量bi 為輸入門的參數，是在訓練過程中需要學習得到的。遺忘門ft 和輸出門ot 的計算方式與輸入門類似，它們有各自的參數W、U 和b。與傳統的循環神經網路不同的是，從上一個記憶單元的狀態ct?1 到當前的狀態ct 的轉移不一定完全取決於激活函數計算得到的狀態，還由輸入門和遺忘門來共同控制。

在一個訓練好的網路中，當輸入的序列中沒有重要信息時，LSTM 的遺忘門的值接近於1，輸入門的值接近於0，此時過去的記憶會被保存，從而實現了長期記憶功能；當輸入的序列中出現了重要的信息時， LSTM 應當把其存入記憶中，此時其輸入門的值會接近於1；當輸入的序列中出現了重要信息，且該信息意味著之前的記憶不再重要時，輸入門的值接近1，而遺忘門的值接近於0，這樣舊的記憶被遺忘，新的重要信息被記憶。經過這樣的設計，整個網路更容易學習到序列之間的長期依賴。

▌10.WGAN解決了原始 GAN 中的什麼問題

直覺告訴我們：不要讓生成器在高維空間傻傻地布網，讓它直接到低維空間「抓」真實數據。道理雖然是這樣，但是在高維空間中藏著無數的低維子空間，如何找到目標子空間呢？站在大廈頂層，環眺四周，你可以迅速定位遠處的山巒和高塔，卻很難知曉一個個樓宇間辦公室里的事情。

你需要線索，而不是簡單撒網。處在高維空間，對抗隱秘的低維空間，不能再用粗暴簡陋的方法，需要有特殊武器，這就是Wasserstein 距離（見圖13.7），也稱推土機距離（EarthMover distance）

怎麼理解這個公式？想像你有一個很大的院子，院子里有幾處坑坑窪窪需要填平，四個牆角都有一堆沙子，沙子總量正好填平所有坑。搬運沙子很費力，你想知道有沒有一種方案，使得花的力氣最少。直覺上，每個坑都選擇最近的沙堆，搬運的距離最短。但是存在一些問題，如果最近的沙堆用完了，或者填完坑後近處還剩好多沙子，或者坑到幾個沙堆的距離一樣，我們該怎麼辦？所以需要設計一個系統的方案，通盤考慮這些問題。最佳方案是上面目標函數的最優解。

可以看到，當沙子分布和坑分布給定時，我們只關心搬運沙子的整體損耗，而不關心每粒沙子的具體擺放，在損耗不變的情況下，沙子擺放可能有很多選擇。對應式（13.16），當你選擇一對(x,y) 時，表示把x 處的一些沙子搬到y 處的坑，可能搬部分沙子，也可能搬全部沙子，可能只把坑填一部分，也可能都填滿了。x 處沙子總量為，y 處坑的大小為，從x 到y的沙子量為γ(x,y)，整體上滿足等式

為什麼Wasserstein 距離能克服JS 距離解決不了的問題？理論上的解釋很複雜，需要證明當生成器分布隨參數θ 變化而連續變化時，生成器分布與真實分布的Wasserstein 距離也隨θ 變化而連續變化，並且幾乎處處可導，而JS 距離不保證隨θ 變化而連續變化。

通俗的解釋，接著「布網」的比喻，現在生成器不再「布網」，改成「定位追蹤」了，不管真實分布藏在哪個低維子空間里，生成器都能感知它在哪，因為生成器只要將自身分布稍做變化，就會改變它到真實分布的推土機距離；而JS 距離是不敏感的，無論生成器怎麼變化，JS 距離都是一個常數。因此，使用推土機距離，能有效鎖定低維子空間中的真實數據分布。

▌11.解釋強化學習中的策略梯度

在策略梯度中，我們考慮前後兩個狀態之間的關係為，其中st、st+1 是相繼的兩個狀態，at 是t 步時所採取的行動，p 是環境所決定的下個時刻狀態分布。而動作at 的生成模型（策略）為，其中πθ 是以θ 為參變數的一個分布，at 從這個分布進行採樣。這樣，在同一個環境下，強化學習的總收益函數，