機(jī)器學(xué)習(xí)算法工程師精選的算法面試這些知識(shí)你多了解嗎？

通往機(jī)器學(xué)習(xí)算法工程師的進(jìn)階之路是崎嶇險(xiǎn)阻的?！毒€性代數(shù)》《統(tǒng)計(jì)學(xué)習(xí)方法》《機(jī)器學(xué)習(xí)》《模式識(shí)別》《深度學(xué)習(xí)》，以及《頸椎病康復(fù)指南》，這些書(shū)籍將長(zhǎng)久地伴隨著你的工作生涯。

除了擁有全面、有條理的知識(shí)儲(chǔ)備，我認(rèn)為，想成為一名優(yōu)秀的算法工程師，更重要的是對(duì)算法模型有著發(fā)自心底的熱忱，對(duì)研究工作有一種匠心精神。這種匠心精神，直白來(lái)講，可以概括為：發(fā)現(xiàn)問(wèn)題的眼光、解決問(wèn)題的探索精神，以及對(duì)問(wèn)題究原竟委的執(zhí)著追求。這里，我想給大家分享一個(gè)發(fā)生在我身邊的真實(shí)情景。

在微信紅包占領(lǐng)家家戶戶年夜飯的那個(gè)時(shí)代，我們的小伙伴也沒(méi)有例外。一群心有猛虎、細(xì)嗅薔薇的算法研究員深切意識(shí)到自己不僅手速慢，運(yùn)氣也可謂糟糕。在埋頭瘋點(diǎn)手機(jī)屏幕的間隙，他們查閱了搶紅包策略的相關(guān)文獻(xiàn)，發(fā)現(xiàn)國(guó)內(nèi)外對(duì)這一理論框架的探究極度匱乏。

知識(shí)拯救命運(yùn)，他們決定將紅包機(jī)制的公平性提升到理論高度。通過(guò)大量的模擬實(shí)驗(yàn)，統(tǒng)計(jì)在不同順位領(lǐng)到紅包的大小。數(shù)據(jù)分析顯示，越后面領(lǐng)到紅包的人，雖然紅包金額的期望（均值）和前面的人相同，但方差會(huì)更大，這也意味著他們更容易獲得一些大額紅包。從此，掌握這一規(guī)律的研究員們?cè)诟鱾€(gè)群中“屢試不爽”，再也沒(méi)有搶到過(guò)紅包，留下的只有“手慢了，紅包派完了”幾個(gè)大字。

*編輯配圖

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

當(dāng)然，故事不止于此。他們還利用紅包的特性編寫(xiě)了一系列面試題——《百面機(jī)器學(xué)習(xí)——算法工程師帶你去面試》，篩選著一批又一批的機(jī)器學(xué)習(xí)算法工程師。

工作中的算法工程師，很多時(shí)候，會(huì)將生活中轉(zhuǎn)瞬即逝的靈感，付諸產(chǎn)品化。

將算法研究應(yīng)用到工作中，與純粹的學(xué)術(shù)研究有著一點(diǎn)最大的不同，即需要從用戶的角度思考問(wèn)題。很多時(shí)候，你需要明確設(shè)計(jì)的產(chǎn)品特征、提升的數(shù)據(jù)指標(biāo)，是不是能真正迎合用戶的需求，這便要求算法工程師能在多個(gè)模型間選擇出最合適的那個(gè)，然后通過(guò)快速迭代達(dá)到一個(gè)可以走向產(chǎn)品化的結(jié)果。這種創(chuàng)新精神與嘗試精神便是“匠心”一詞在工作中的體現(xiàn)。

當(dāng)然，匠心精神誠(chéng)可貴，知識(shí)儲(chǔ)備作為成功的根底亦必不可少，以下是營(yíng)長(zhǎng)為你精選的算法面試，幫你檢查下自己的技能是否在線。

*編輯配圖

▌1. LDA(線性判別分析) 和 PCA 的區(qū)別與聯(lián)系

首先將LDA 擴(kuò)展到多類高維的情況，以和問(wèn)題1 中PCA 的求解對(duì)應(yīng)。假設(shè)有N 個(gè)類別，并需要最終將特征降維至d 維。因此，我們要找到一個(gè)d 維投影超平面，使得投影后的樣本點(diǎn)滿足LDA 的目標(biāo)—最大化類間距離和最小化類內(nèi)距離。

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

如果把全局散度定義為類內(nèi)散度與類間散度之和，即St=Sb+Sw，那么類間散度矩陣可表示為

其中mj 是第j 個(gè)類別中的樣本個(gè)數(shù)，N 是總的類別個(gè)數(shù)。從式（4.29）可以看出，類間散度表示的就是每個(gè)類別中心到全局中心的一種加權(quán)距離。我們最大化類間散度實(shí)際上優(yōu)化的是每個(gè)類別的中心經(jīng)過(guò)投影后離全局中心的投影足夠遠(yuǎn)。

根據(jù)LDA 的原理，可以將最大化的目標(biāo)定義為

其中W是需要求解的投影超平面，WTW=I，根據(jù)問(wèn)題2 和問(wèn)題3 中的部分結(jié)論，我們可以推導(dǎo)出最大化J(W) 對(duì)應(yīng)了以下廣義特征值求解的問(wèn)題

求解最佳投影平面即求解矩陣特征值前d 大對(duì)應(yīng)的特征向量組成的矩陣，這就將原始的特征空間投影到了新的d 維空間中。至此我們得到了與PCA 步驟類似，但具有多個(gè)類別標(biāo)簽高維數(shù)據(jù)的LDA求解方法。

（1）計(jì)算數(shù)據(jù)集中每個(gè)類別樣本的均值向量μj，及總體均值向量μ。

（2）計(jì)算類內(nèi)散度矩陣Sw，全局散度矩陣St，并得到類間散度矩陣。

（3）對(duì)矩陣行特征值分解，將特征值從大到小排列。

（4）取特征值前 d 大的對(duì)應(yīng)的特征向量，通過(guò)以下映射將n 維樣本映射到d 維?

從PCA 和LDA 兩種降維方法的求解過(guò)程來(lái)看，它們確實(shí)有著很大的相似性，但對(duì)應(yīng)的原理卻有所區(qū)別。

首先從目標(biāo)出發(fā)，PCA 選擇的是投影后數(shù)據(jù)方差最大的方向。由于它是無(wú)監(jiān)督的，因此PCA 假設(shè)方差越大，信息量越多，用主成分來(lái)表示原始數(shù)據(jù)可以去除冗余的維度，達(dá)到降維。而LDA 選擇的是投影后類內(nèi)方差小、類間方差大的方向。其用到了類別標(biāo)簽信息，為了找到數(shù)據(jù)中具有判別性的維度，使得原始數(shù)據(jù)在這些方向上投影后，不同類別盡可能區(qū)分開(kāi)。

舉一個(gè)簡(jiǎn)單的例子，在語(yǔ)音識(shí)別中，我們想從一段音頻中提取出人的語(yǔ)音信號(hào)，這時(shí)可以使用PCA 先進(jìn)行降維，過(guò)濾掉一些固定頻率（方差較?。┑谋尘霸肼暋５绻覀兊男枨笫菑倪@段音頻中區(qū)分出聲音屬于哪個(gè)人，那么我們應(yīng)該使用LDA 對(duì)數(shù)據(jù)進(jìn)行降維，使每個(gè)人的語(yǔ)音信號(hào)具有區(qū)分性。

另外，在人臉識(shí)別領(lǐng)域中，PCA 和LDA 都會(huì)被頻繁使用。基于PCA 的人臉識(shí)別方法也稱為特征臉（Eigenface）方法，該方法將人臉圖像按行展開(kāi)形成一個(gè)高維向量，對(duì)多個(gè)人臉特征的協(xié)方差矩陣做特征值分解，其中較大特征值對(duì)應(yīng)的特征向量具有與人臉相似的形狀，故稱為特征臉。Eigenface forRecognition 一文中將人臉用7 個(gè)特征臉表示（見(jiàn)圖4.7），于是可以把原始65536 維的圖像特征瞬間降到7 維， 人臉識(shí)別在降維后的空間上進(jìn)行。然而由于其利用PCA 進(jìn)行降維，一般情況下保留的是最佳描述特征（主成分），而非分類特征。如果我們想要達(dá)到更好的人臉識(shí)別效果，應(yīng)該用LDA 方法對(duì)數(shù)據(jù)集進(jìn)行降維， 使得不同人臉在投影后的特征具有一定區(qū)分性。

從應(yīng)用的角度，我們可以掌握一個(gè)基本的原則—對(duì)無(wú)監(jiān)督的任務(wù)使用PCA 進(jìn)行降維，對(duì)有監(jiān)督的則應(yīng)用LDA。

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

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

當(dāng)概率模型中含有無(wú)法被觀測(cè)的隱含變量時(shí)，參數(shù)的最大似然估計(jì)變?yōu)?/p>

由于z(i) 是未知的， 無(wú)法直接通過(guò)最大似然估計(jì)求解參數(shù)，這時(shí)就需要利用EM 算法來(lái)求解。假設(shè)z(i) 對(duì)應(yīng)的分布為，并滿足。利用Jensen 不等式，可以得到?

要使上式中的等號(hào)成立，需要滿足

其中c 為常數(shù)，且滿足

因此

不等式右側(cè)函數(shù)記為r(x|θ)。當(dāng)?shù)仁匠闪r(shí)，我們相當(dāng)于為待優(yōu)化的函數(shù)找到了一個(gè)逼近的下界，然后通過(guò)最大化這個(gè)下界可以使得待優(yōu)化函數(shù)向更好的方向改進(jìn)。

圖5.5 是一個(gè)θ 為一維的例子，其中棕色的曲線代表我們待優(yōu)化的函數(shù)，記為f(θ)，優(yōu)化過(guò)程即為找到使得f(θ) 取值最大的θ。在當(dāng)前θ 的取值下（即圖中綠色的位置），可以計(jì)算，此時(shí)不等式右側(cè)的函數(shù)（記為r(x|θ)）給出了優(yōu)化函數(shù)的一個(gè)下界，如圖中藍(lán)色曲線所示，其中在θ 處兩條曲線的取值時(shí)相等的。接下來(lái)找到使得r(x|θ) 最大化的參數(shù)θ′，即圖中紅色的位置，此時(shí)f(θ′) 的取值比f(wàn)(θ)（綠色的位置處）有所提升?？梢宰C明，f(θ′) ≥ r(x|θ)=f(θ)，因此函數(shù)是單調(diào)的，而且從而函數(shù)是有界的。根據(jù)函數(shù)單調(diào)有界必收斂的性質(zhì)，EM 算法的收斂性得證。但是EM 算法只保證收斂到局部最優(yōu)解。當(dāng)函數(shù)為非凸時(shí)，以圖5.5 為例，如果初始化在左邊的區(qū)域時(shí)，則無(wú)法找到右側(cè)的高點(diǎn)。

由上面的推導(dǎo)，EM 算法框架可以總結(jié)如下，由以下兩個(gè)步驟交替進(jìn)行直到收斂。

（1）E 步驟：計(jì)算隱變量的期望

（2）M 步驟：最大化

剩下的事情就是說(shuō)明K 均值算法與EM 算法的關(guān)系了。K 均值算法等價(jià)于用EM 算法求解以下含隱變量的最大似然問(wèn)題：

其中是模型的隱變量。直觀地理解，就是當(dāng)樣本x 離第k個(gè)簇的中心點(diǎn)μk 距離最近時(shí)，概率正比于，否則為0。

在 E 步驟，計(jì)算

這等同于在K 均值算法中對(duì)于每一個(gè)點(diǎn)x(i) 找到當(dāng)前最近的簇z(i)。

在M步驟，找到最優(yōu)的參數(shù)，使得似然函數(shù)最大：

經(jīng)過(guò)推導(dǎo)可得

因此，這一步驟等同于找到最優(yōu)的中心點(diǎn)，使得損失函數(shù)

達(dá)到最小，此時(shí)每個(gè)樣本x(i) 對(duì)應(yīng)的簇z(i) 已確定，因此每個(gè)簇k 對(duì)應(yīng)的最優(yōu)中心點(diǎn)μk 可以由該簇中所有點(diǎn)的平均計(jì)算得到，這與K 均值算法中根據(jù)當(dāng)前簇的分配更新聚類中心的步驟是等同的。

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

在LDA中，主題的個(gè)數(shù)K 是一個(gè)預(yù)先指定的超參數(shù)。對(duì)于模型超參數(shù)的選擇，實(shí)踐中的做法一般是將全部數(shù)據(jù)集分成訓(xùn)練集、驗(yàn)證集、和測(cè)試集3 部分，然后利用驗(yàn)證集對(duì)超參數(shù)進(jìn)行選擇。例如，在確定LDA 的主題個(gè)數(shù)時(shí)，我們可以隨機(jī)選取60% 的文檔組成訓(xùn)練集，另外20% 的文檔組成驗(yàn)證集，剩下20% 的文檔組成測(cè)試集。在訓(xùn)練時(shí)，嘗試多組超參數(shù)的取值，并在驗(yàn)證集上檢驗(yàn)?zāi)囊唤M超參數(shù)所對(duì)應(yīng)的模型取得了最好的效果。最終，在驗(yàn)證集上效果最好的一組超參數(shù)和其對(duì)應(yīng)的模型將被選定，并在測(cè)試集上進(jìn)行測(cè)試。

為了衡量LDA 模型在驗(yàn)證集和測(cè)試集上的效果，需要尋找一個(gè)合適的評(píng)估指標(biāo)。一個(gè)常用的評(píng)估指標(biāo)是困惑度（perplexity）。在文檔集合D 上，模型的困惑度被定義為

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

一開(kāi)始，隨著主題個(gè)數(shù)的增多，模型在訓(xùn)練集和驗(yàn)證集的困惑度呈下降趨勢(shì)，但是當(dāng)主題數(shù)目足夠大的時(shí)候，會(huì)出現(xiàn)過(guò)擬合，導(dǎo)致困惑度指標(biāo)在訓(xùn)練集上繼續(xù)下降但在驗(yàn)證集上反而增長(zhǎng)。這時(shí)，可以取驗(yàn)證集的困惑度極小值點(diǎn)所對(duì)應(yīng)的主題個(gè)數(shù)作為超參數(shù)。在實(shí)踐中，困惑度的極小值點(diǎn)可能出現(xiàn)在主題數(shù)目非常大的時(shí)候，然而實(shí)際應(yīng)用并不能承受如此大的主題數(shù)目，這時(shí)就需要在實(shí)際應(yīng)用中合理的主題數(shù)目范圍內(nèi)進(jìn)行選擇，比如選擇合理范圍內(nèi)困惑度的下降明顯變慢（拐點(diǎn)）的時(shí)候。

另外一種方法是在LDA 基礎(chǔ)之上融入分層狄利克雷過(guò)程（Hierarchical Dirichlet Process，HDP），構(gòu)成一種非參數(shù)主題模型HDP-LDA。非參數(shù)主題模型的好處是不需要預(yù)先指定主題的個(gè)數(shù)，模型可以隨著文檔數(shù)目的變化而自動(dòng)對(duì)主題個(gè)數(shù)進(jìn)行調(diào)整；它的缺點(diǎn)是在LDA 基礎(chǔ)上融入HDP 之后使得整個(gè)概率圖模型更加復(fù)雜，訓(xùn)練速度也更加緩慢，因此在實(shí)際應(yīng)用中還是經(jīng)常采用第一種方法確定合適的主題數(shù)目。

▌4.隨機(jī)梯度下降法的一些改進(jìn)算法

隨機(jī)梯度下降法本質(zhì)上是采用迭代方式更新參數(shù)，每次迭代在當(dāng)前位置的基礎(chǔ)上，沿著某一方向邁一小步抵達(dá)下一位置，然后在下一位置重復(fù)上述步驟。隨機(jī)梯度下降法的更新公式表示為

其中，當(dāng)前估計(jì)的負(fù)梯度?gt 表示步子的方向，學(xué)習(xí)速率η 控制步幅。改造的隨機(jī)梯度下降法仍然基于這個(gè)更新公式。

動(dòng)量（Momentum）方法

為了解決隨機(jī)梯度下降法山谷震蕩和鞍點(diǎn)停滯的問(wèn)題，我們做一個(gè)簡(jiǎn)單的思維實(shí)驗(yàn)。想象一下紙團(tuán)在山谷和鞍點(diǎn)處的運(yùn)動(dòng)軌跡，在山谷中紙團(tuán)受重力作用沿山道滾下，兩邊是不規(guī)則的山壁，紙團(tuán)不可避免地撞在山壁，由于質(zhì)量小受山壁彈力的干擾大，從一側(cè)山壁反彈回來(lái)撞向另一側(cè)山壁，結(jié)果來(lái)回震蕩地滾下；如果當(dāng)紙團(tuán)來(lái)到鞍點(diǎn)的一片平坦之地時(shí)，還是由于質(zhì)量小，速度很快減為零。紙團(tuán)的情況和隨機(jī)梯度下降法遇到的問(wèn)題簡(jiǎn)直如出一轍。直觀地，如果換成一個(gè)鐵球，當(dāng)沿山谷滾下時(shí)，不容易受到途中旁力的干擾，軌跡會(huì)更穩(wěn)更直；當(dāng)來(lái)到鞍點(diǎn)中心處，在慣性作用下繼續(xù)前行，從而有機(jī)會(huì)沖出這片平坦的陷阱。因此，有了動(dòng)量方法，模型參數(shù)的迭代公式為

具體來(lái)說(shuō)，前進(jìn)步伐?vt由兩部分組成。一是學(xué)習(xí)速率η乘以當(dāng)前估計(jì)的梯度gt；二是帶衰減的前一次步伐vt?1。這里，慣性就體現(xiàn)在對(duì)前一次步伐信息的重利用上。類比中學(xué)物理知識(shí)，當(dāng)前梯度就好比當(dāng)前時(shí)刻受力產(chǎn)生的加速度，前一次步伐好比前一時(shí)刻的速度，當(dāng)前步伐好比當(dāng)前時(shí)刻的速度。為了計(jì)算當(dāng)前時(shí)刻的速度，應(yīng)當(dāng)考慮前一時(shí)刻速度和當(dāng)前加速度共同作用的結(jié)果，因此vt直接依賴于vt?1和gt，而不僅僅是gt。另外，衰減系數(shù)γ扮演了阻力的作用。

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

AdaGrad 方法

慣性的獲得是基于歷史信息的，那么，除了從過(guò)去的步伐中獲得一股子向前沖的勁兒，還能獲得什么呢？我們還期待獲得對(duì)周圍環(huán)境的感知，即使蒙上雙眼，依靠前幾次邁步的感覺(jué)，也應(yīng)該能判斷出一些信息，比如這個(gè)方向總是坑坑洼洼的，那個(gè)方向可能很平坦。

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

AdaGrad 方法采用“歷史梯度平方和”來(lái)衡量不同參數(shù)的梯度的稀疏性，取值越小表明越稀疏，具體的更新公式表示為

其中θt+1,i 表示（t+1）時(shí)刻的參數(shù)向量θt+1的第i個(gè)參數(shù)，gk,i表示k時(shí)刻的梯度向量gk 的第i 個(gè)維度（方向）。另外，分母中求和的形式實(shí)現(xiàn)了退火過(guò)程，這是很多優(yōu)化技術(shù)中常見(jiàn)的策略，意味著隨著時(shí)間推移，學(xué)習(xí)速率越

來(lái)越小，從而保證了算法的最終收斂。

Adam 方法

Adam 方法將慣性保持和環(huán)境感知這兩個(gè)優(yōu)點(diǎn)集于一身。一方面， Adam 記錄梯度的一階矩（first moment），即過(guò)往梯度與當(dāng)前梯度的平均，這體現(xiàn)了慣性保持；另一方面，Adam 還記錄梯度的二階矩（second moment），即過(guò)往梯度平方與當(dāng)前梯度平方的平均，這類似AdaGrad 方法，體現(xiàn)了環(huán)境感知能力，為不同參數(shù)產(chǎn)生自適應(yīng)的學(xué)習(xí)速率。一階矩和二階矩采用類似于滑動(dòng)窗口內(nèi)求平均的思想進(jìn)行融合，即當(dāng)前梯度和近一段時(shí)間內(nèi)梯度的平均值，時(shí)間久遠(yuǎn)的梯度對(duì)當(dāng)前平均值的貢獻(xiàn)呈指數(shù)衰減。具體來(lái)說(shuō)，一階矩和二階矩采用指數(shù)衰退平均（exponential decayaverage）技術(shù)，計(jì)算公式為

其中β1，β2 為衰減系數(shù)，mt 是一階矩，vt 是二階矩。

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

其中,

▌5.L1正則化產(chǎn)生稀疏性的原因

角度1：解空間形狀

機(jī)器學(xué)習(xí)的經(jīng)典之作給出的解釋無(wú)疑是權(quán)威且直觀的，面試者給出的答案多數(shù)也是從這個(gè)角度出發(fā)的。在二維的情況下，黃色的部分是L2 和L1 正則項(xiàng)約束后的解空間，綠色的等高線是凸優(yōu)化問(wèn)題中目標(biāo)函數(shù)的等高線，如圖7.6 所示。由圖可知，L2 正則項(xiàng)約束后的解空間是圓形，而L1 正則項(xiàng)約束的解空間是多邊形。顯然，多邊形的解空間更容易在尖角處與等高線碰撞出稀疏解。

上述這個(gè)解釋無(wú)疑是正確的，但卻不夠精確，面試者往往回答過(guò)于籠統(tǒng)，以至于忽視了幾個(gè)關(guān)鍵問(wèn)題。比如，為什么加入正則項(xiàng)就是定義了一個(gè)解空間約束？為什么L1 和L2的解空間是不同的？面試官如果深究下去，很多面試者難以給出滿意的答案。其實(shí)可以通過(guò)KKT條件給出一種解釋。

事實(shí)上，“帶正則項(xiàng)”和“帶約束條件”是等價(jià)的。為了約束w 的可能取值空間從而防止過(guò)擬合，我們?yōu)樵撟顑?yōu)化問(wèn)題加上一個(gè)約束，就是w 的L2 范數(shù)的平方不能大于m：

為了求解帶約束條件的凸優(yōu)化問(wèn)題，寫(xiě)出拉格朗日函數(shù)

若w* 和λ* 分別是原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解，則根據(jù)KKT 條件，它們應(yīng)滿足

仔細(xì)一看，第一個(gè)式子不就是w* 為帶L2 正則項(xiàng)的優(yōu)化問(wèn)題的最優(yōu)解的條件嘛，而λ* 就是L2 正則項(xiàng)前面的正則參數(shù)。

這時(shí)回頭再看開(kāi)頭的問(wèn)題就清晰了。L2 正則化相當(dāng)于為參數(shù)定義了一個(gè)圓形的解空間（因?yàn)楸仨毐ＷCL2 范數(shù)不能大于m），而L1 正則化相當(dāng)于為參數(shù)定義了一個(gè)棱形的解空間。如果原問(wèn)題目標(biāo)函數(shù)的最優(yōu)解不是恰好落在解空間內(nèi)，那么約束條件下的最優(yōu)解一定是在解空間的邊界上，而L1“棱角分明”的解空間顯然更容易與目標(biāo)函數(shù)等高線在角點(diǎn)碰撞，從而產(chǎn)生稀疏解。

角度2：函數(shù)疊加

第二個(gè)角度試圖用更直觀的圖示來(lái)解釋L1 產(chǎn)生稀疏性這一現(xiàn)象。僅考慮一維的情況，多維情況是類似的，如圖7.7 所示。假設(shè)棕線是原始目標(biāo)函數(shù)L(w) 的曲線圖，顯然最小值點(diǎn)在藍(lán)點(diǎn)處，且對(duì)應(yīng)的w* 值非0。

首先，考慮加上L2正則化項(xiàng)，目標(biāo)函數(shù)變成L(w)+Cw2，其函數(shù)曲線為黃色。此時(shí)，最小值點(diǎn)在黃點(diǎn)處，對(duì)應(yīng)的w* 的絕對(duì)值減小了，但仍然非0。

然后，考慮加上L1 正則化項(xiàng)，目標(biāo)函數(shù)變成L(w)+C|w|，其函數(shù)曲線為綠色。此時(shí)，最小值點(diǎn)在紅點(diǎn)處，對(duì)應(yīng)的w 是0，產(chǎn)生了稀疏性。

產(chǎn)生上述現(xiàn)象的原因也很直觀。加入L1 正則項(xiàng)后，對(duì)帶正則項(xiàng)的目標(biāo)函數(shù)求導(dǎo)，正則項(xiàng)部分產(chǎn)生的導(dǎo)數(shù)在原點(diǎn)左邊部分是?C，在原點(diǎn)右邊部分是C，因此，只要原目標(biāo)函數(shù)的導(dǎo)數(shù)絕對(duì)值小于C，那么帶正則項(xiàng)的目標(biāo)函數(shù)在原點(diǎn)左邊部分始終是遞減的，在原點(diǎn)右邊部分始終是遞增的，最小值點(diǎn)自然在原點(diǎn)處。相反，L2 正則項(xiàng)在原點(diǎn)處的導(dǎo)數(shù)是0，只要原目標(biāo)函數(shù)在原點(diǎn)處的導(dǎo)數(shù)不為0，那么最小值點(diǎn)就不會(huì)在原點(diǎn)，所以L2 只有減小w 絕對(duì)值的作用，對(duì)解空間的稀疏性沒(méi)有貢獻(xiàn)。

在一些在線梯度下降算法中，往往會(huì)采用截?cái)嗵荻确▉?lái)產(chǎn)生稀疏性， 這同L1 正則項(xiàng)產(chǎn)生稀疏性的原理是類似的。

角度3：貝葉斯先驗(yàn)

從貝葉斯的角度來(lái)理解L1 正則化和L2 正則化，簡(jiǎn)單的解釋是， L1 正則化相當(dāng)于對(duì)模型參數(shù)w 引入了拉普拉斯先驗(yàn)，L2 正則化相當(dāng)于引入了高斯先驗(yàn)，而拉普拉斯先驗(yàn)使參數(shù)為0 的可能性更大。

圖7.8 是高斯分布曲線圖。由圖可見(jiàn)，高斯分布在極值點(diǎn)（0 點(diǎn)）處是平滑的，也就是高斯先驗(yàn)分布認(rèn)為w 在極值點(diǎn)附近取不同值的可能性是接近的。這就是L2 正則化只會(huì)讓w 更接0點(diǎn)，但不會(huì)等于0 的原因。

相反，圖7.9 是拉普拉斯分布曲線圖。由圖可見(jiàn)，拉普拉斯分布在極值點(diǎn)（0 點(diǎn)）處是一個(gè)尖峰，所以拉普拉斯先驗(yàn)分布中參數(shù)w 取值為0 的可能性要更高。在此我們不再給出L1 和L2 正則化分別對(duì)應(yīng)拉普拉斯先驗(yàn)分布和高斯先驗(yàn)分布的詳細(xì)證明。

▌6.如何對(duì)貝葉斯網(wǎng)絡(luò)進(jìn)行采樣

對(duì)一個(gè)沒(méi)有觀測(cè)變量的貝葉斯網(wǎng)絡(luò)進(jìn)行采樣，最簡(jiǎn)單的方法是祖先采樣（Ancestral Sampling），它的核心思想是根據(jù)有向圖的順序，先對(duì)祖先節(jié)點(diǎn)進(jìn)行采樣，只有當(dāng)某個(gè)節(jié)點(diǎn)的所有父節(jié)點(diǎn)都已完成采樣，才對(duì)該節(jié)點(diǎn)進(jìn)行采樣。以場(chǎng)景描述中的圖8.9 為例，先對(duì)Cloudy 變量進(jìn)行采樣，然后再對(duì)Sprinkler 和Rain 變量進(jìn)行采樣，最后對(duì)WetGrass 變量采樣，如圖8.10 所示（圖中綠色表示變量取值為T(mén)rue，紅色表示取值為False）。根據(jù)貝葉斯網(wǎng)絡(luò)的全概率公式

可以看出祖先采樣得到的樣本服從貝葉斯網(wǎng)絡(luò)的聯(lián)合概率分布。

如果只需要對(duì)貝葉斯網(wǎng)絡(luò)中一部分隨機(jī)變量的邊緣分布進(jìn)行采樣， 可以用祖先采樣先對(duì)全部隨機(jī)變量進(jìn)行采樣，然后直接忽視那些不需要的變量的采樣值即可。由圖可見(jiàn)，如果需要對(duì)邊緣分布p(Rain) 進(jìn)行采樣，先用祖先采樣得到全部變量的一個(gè)樣本，如（Cloudy=T， Sprinkler=F，Rain=T，WetGrass=T），然后忽略掉無(wú)關(guān)變量，直接把這個(gè)樣本看成是Cloudy=T 即可。

接下來(lái)考慮含有觀測(cè)變量的貝葉斯網(wǎng)絡(luò)的采樣，如圖8.11 所示。網(wǎng)絡(luò)中有觀測(cè)變量（Sprikler=T，WetGrass=T）（觀測(cè)變量用斜線陰影表示），又該如何采樣呢？最直接的方法是邏輯采樣，還是利用祖先采樣得到所有變量的取值。如果這個(gè)樣本在觀測(cè)變量上的采樣值與實(shí)際觀測(cè)值相同，則接受，否則拒絕，重新采樣。這種方法的缺點(diǎn)是采樣效率可能會(huì)非常低，隨著觀測(cè)變量個(gè)數(shù)的增加、每個(gè)變量狀態(tài)數(shù)目的上升，邏輯采樣法的采樣效率急劇下降，實(shí)際中基本不可用。

因此，在實(shí)際應(yīng)用中，可以參考重要性采樣的思想，不再對(duì)觀測(cè)變量進(jìn)行采樣，只對(duì)非觀測(cè)變量采樣，但是最終得到的樣本需要賦一個(gè)重要性權(quán)值：

其中E 是觀測(cè)變量集合。這種采樣方法稱作似然加權(quán)采樣（Likelihood Weighted Sampling），產(chǎn)生的樣本權(quán)值可以用于后續(xù)的積分操作。在有觀測(cè)變量（Sprikler=T，WetGrass=T）時(shí)，可以先對(duì)Cloudy 進(jìn)行采樣，然后對(duì)Rain 進(jìn)行采樣，不再對(duì)Sprinkler 和WetGrass 采樣（直接賦觀測(cè)值），如圖8.12 所示。這樣得到的樣本的重要性權(quán)值為

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

除此之外，還可以用MCMC采樣法來(lái)進(jìn)行采樣。具體來(lái)說(shuō)，如果采用Metropolis-Hastings 采樣法的話，如圖8.13所示，只需要在隨機(jī)向量（Cloudy, 、Rain）上選擇一個(gè)概率轉(zhuǎn)移矩陣，然后按照概率轉(zhuǎn)移矩陣不斷進(jìn)行狀態(tài)轉(zhuǎn)換，每次轉(zhuǎn)移有一定概率的接受或拒絕，最終得到的樣本序列會(huì)收斂到目標(biāo)分布。最簡(jiǎn)單的概率轉(zhuǎn)移矩陣可以是：每次獨(dú)立地隨機(jī)選擇（Cloudy, Rain）的四種狀態(tài)之一。如果采用吉布斯采樣法的話，根據(jù)條件概率p(Cloudy|Rain,Sprinkler, WetGrass) 和p(Rain|Cloudy, Sprinkler,WetGrass)， 每次只對(duì)（Cloudy, Rain）中的一個(gè)變量進(jìn)行采樣，交替進(jìn)行即可。

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

簡(jiǎn)單回答這個(gè)問(wèn)題就是：Bagging能夠提高弱分類器性能的原因是降低了方差，Boosting能夠提升弱分類器性能的原因是降低了偏差。為什么這么講呢？

首先，Bagging是 Bootstrap Aggregating 的簡(jiǎn)稱，意思就是再抽樣，然后在每個(gè)樣本上訓(xùn)練出來(lái)的模型取平均。

假設(shè)有n 個(gè)隨機(jī)變量，方差記為σ2，兩兩變量之間的相關(guān)性為ρ， 則n 個(gè)隨機(jī)變量的均值的方差為。在隨機(jī)變量完全獨(dú)立的情況下，n 個(gè)隨機(jī)變量的方差為σ2/n，也就是說(shuō)方差減小到了原來(lái)的1/n。

再?gòu)哪Ｐ偷慕嵌壤斫膺@個(gè)問(wèn)題，對(duì)n 個(gè)獨(dú)立不相關(guān)的模型的預(yù)測(cè)結(jié)果取平均，方差是原來(lái)單個(gè)模型的1/n。這個(gè)描述不甚嚴(yán)謹(jǐn)，但原理已經(jīng)講得很清楚了。當(dāng)然，模型之間不可能完全獨(dú)立。為了追求模型的獨(dú)立性，諸多Bagging 的方法做了不同的改進(jìn)。比如在隨機(jī)森林算法中，每次選取節(jié)點(diǎn)分裂屬性時(shí)，會(huì)隨機(jī)抽取一個(gè)屬性子集，而不是從所有屬性中選取最優(yōu)屬性，這就是為了避免弱分類器之間過(guò)強(qiáng)的相關(guān)性。通過(guò)訓(xùn)練集的重采樣也能夠帶來(lái)弱分類器之間的一定獨(dú)立性，從而降低Bagging 后模型的方差。

再看Boosting，大家應(yīng)該還記得Boosting 的訓(xùn)練過(guò)程。在訓(xùn)練好一個(gè)弱分類器后，我們需要計(jì)算弱分類器的錯(cuò)誤或者殘差，作為下一個(gè)分類器的輸入。這個(gè)過(guò)程本身就是在不斷減小損失函數(shù)，來(lái)使模型不斷逼近“靶心”，使得模型偏差不斷降低。但Boosting 的過(guò)程并不會(huì)顯著降低方差。這是因?yàn)锽oosting 的訓(xùn)練過(guò)程使得各弱分類器之間是強(qiáng)相關(guān)的，缺乏獨(dú)立性，所以并不會(huì)對(duì)降低方差有作用。

關(guān)于泛化誤差、偏差、方差和模型復(fù)雜度的關(guān)系如圖12.5 所示。不難看出，方差和偏差是相輔相成，矛盾又統(tǒng)一的，二者并不能完全獨(dú)立的存在。對(duì)于給定的學(xué)習(xí)任務(wù)和訓(xùn)練數(shù)據(jù)集，我們需要對(duì)模型的復(fù)雜度做合理的假設(shè)。如果模型復(fù)雜度過(guò)低，雖然方差很小，但是偏差會(huì)很高；如果模型復(fù)雜度過(guò)高，雖然偏差降低了，但是方差會(huì)很高。所以需要綜合考慮偏差和方差選擇合適復(fù)雜度的模型進(jìn)行訓(xùn)練。

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

ResNet的提出背景是解決或緩解深層的神經(jīng)網(wǎng)絡(luò)訓(xùn)練中的梯度消失問(wèn)題。假設(shè)有一個(gè)L 層的深度神經(jīng)網(wǎng)絡(luò)，如果我們?cè)谏厦婕尤胍粚樱?直觀來(lái)講得到的L+1 層深度神經(jīng)網(wǎng)絡(luò)的效果應(yīng)該至少不會(huì)比L 層的差。因?yàn)槲覀兒?jiǎn)單地設(shè)最后一層為前一層的拷貝（用一個(gè)恒等映射即可實(shí)現(xiàn)），并且其他層維持原來(lái)的參數(shù)即可。然而在進(jìn)行反向傳播時(shí)，我們很難找到這種形式的解。實(shí)際上，通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，層數(shù)更深的神經(jīng)網(wǎng)絡(luò)反而會(huì)具有更大的訓(xùn)練誤差。在CIFAR-10 數(shù)據(jù)集上的一個(gè)結(jié)果如圖9.22 所示，56 層的網(wǎng)絡(luò)反而比20 層的網(wǎng)絡(luò)訓(xùn)練誤差更大，這很大程度上歸結(jié)于深度神經(jīng)網(wǎng)絡(luò)的梯度消失問(wèn)題。

為了解釋梯度消失問(wèn)題是如何產(chǎn)生的?；仡櫟? 節(jié)推導(dǎo)出的誤差傳播公式

將式（9.31）再展開(kāi)一層，可以得到

可以看到誤差傳播可以寫(xiě)成參數(shù)、以及導(dǎo)數(shù)、連乘的形式。當(dāng)誤差由第L 層（記為）傳播到除輸入以外的第一個(gè)隱含層（記為）的時(shí)候，會(huì)涉及非常多的參數(shù)和導(dǎo)數(shù)的連乘，這時(shí)誤差很容易產(chǎn)生消失或者膨脹，影響對(duì)該層參數(shù)的正確學(xué)習(xí)。因此深度神經(jīng)網(wǎng)絡(luò)的擬合和泛化能力較差，有時(shí)甚至不如淺層的神經(jīng)網(wǎng)絡(luò)模型精度更高。

ResNet過(guò)調(diào)整網(wǎng)絡(luò)結(jié)構(gòu)來(lái)解決上述問(wèn)題。首先考慮兩層神經(jīng)網(wǎng)絡(luò)的簡(jiǎn)單疊加（見(jiàn)圖9.23（a）），這時(shí)輸入x 經(jīng)過(guò)兩個(gè)網(wǎng)絡(luò)層的變換得到H(x)，激活函數(shù)采用ReLU。反向傳播時(shí)，梯度將涉及兩層參數(shù)的交叉相乘，可能會(huì)在離輸入近的網(wǎng)絡(luò)層中產(chǎn)生梯度消失的現(xiàn)象。ResNet 把網(wǎng)絡(luò)結(jié)構(gòu)調(diào)整為，既然離輸入近的神經(jīng)網(wǎng)絡(luò)層較難訓(xùn)練，那么我們可以將它短接到更靠近輸出的層，如圖9.23（b）所示。輸入x經(jīng)過(guò)兩個(gè)神經(jīng)網(wǎng)絡(luò)的變換得到F(x)，同時(shí)也短接到兩層之后，最后這個(gè)包含兩層的神經(jīng)網(wǎng)絡(luò)模塊輸出H(x)=F(x)+x。

這樣一來(lái)，F(xiàn)(x) 被設(shè)計(jì)為只需要擬合輸入x 與目標(biāo)輸出的殘差，殘差網(wǎng)絡(luò)的名稱也因此而來(lái)。如果某一層的輸出已經(jīng)較好的擬合了期望結(jié)果，那么多加入一層不會(huì)使得模型變得更差，因?yàn)樵搶拥妮敵鰧⒅苯颖欢探拥絻蓪又螅喈?dāng)于直接學(xué)習(xí)了一個(gè)恒等映射，而跳過(guò)的兩層只需要擬合上層輸出和目標(biāo)之間的殘差即可。?

ResNet 可以有效改善深層的神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)問(wèn)題，使得訓(xùn)練更深的網(wǎng)絡(luò)成為可能，如圖9.24 所示。圖9.24（a）展示的是傳統(tǒng)神經(jīng)網(wǎng)絡(luò)的結(jié)果，可以看到隨著模型結(jié)構(gòu)的加深訓(xùn)練誤差反而上升；而圖9.24（b） 是ResNet 的實(shí)驗(yàn)結(jié)果，隨著模型結(jié)構(gòu)的加深，訓(xùn)練誤差逐漸降低，并且優(yōu)于相同層數(shù)的傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)。

▌9.LSTM是如何實(shí)現(xiàn)長(zhǎng)短期記憶功能的

有圖有真相，我們首先結(jié)合LSTM 結(jié)構(gòu)圖以及更新的計(jì)算公式探討這種網(wǎng)絡(luò)如何實(shí)現(xiàn)其功能，如圖10.2 所示。

與傳統(tǒng)的循環(huán)神經(jīng)網(wǎng)絡(luò)相比，LSTM 仍然是基于xt 和ht?1來(lái)計(jì)算ht，只不過(guò)對(duì)內(nèi)部的結(jié)構(gòu)進(jìn)行了更加精心的設(shè)計(jì)，加入了輸入門(mén)it、遺忘門(mén)ft以及輸出門(mén)ot 三個(gè)門(mén)和一個(gè)內(nèi)部記憶單元ct。輸入門(mén)控制當(dāng)前計(jì)算的新?tīng)顟B(tài)以多大程度更新到記憶單元中；遺忘門(mén)控制前一步記憶單元中的信息有多大程度被遺忘掉；輸出門(mén)控制當(dāng)前的輸出有多大程度上取決于當(dāng)前的記憶單元。

經(jīng)典的LSTM 中，第t 步的更新計(jì)算公式為

其中it是通過(guò)輸入xt和上一步的隱含層輸出ht?1進(jìn)行線性變換，再經(jīng)過(guò)激活函數(shù)σ 得到的。輸入門(mén)it的結(jié)果是向量，其中每個(gè)元素是0 到1 之間的實(shí)數(shù)，用于控制各維度流過(guò)閥門(mén)的信息量；Wi、Ui兩個(gè)矩陣和向量bi 為輸入門(mén)的參數(shù)，是在訓(xùn)練過(guò)程中需要學(xué)習(xí)得到的。遺忘門(mén)ft 和輸出門(mén)ot 的計(jì)算方式與輸入門(mén)類似，它們有各自的參數(shù)W、U 和b。與傳統(tǒng)的循環(huán)神經(jīng)網(wǎng)絡(luò)不同的是，從上一個(gè)記憶單元的狀態(tài)ct?1 到當(dāng)前的狀態(tài)ct 的轉(zhuǎn)移不一定完全取決于激活函數(shù)計(jì)算得到的狀態(tài)，還由輸入門(mén)和遺忘門(mén)來(lái)共同控制。

在一個(gè)訓(xùn)練好的網(wǎng)絡(luò)中，當(dāng)輸入的序列中沒(méi)有重要信息時(shí)，LSTM 的遺忘門(mén)的值接近于1，輸入門(mén)的值接近于0，此時(shí)過(guò)去的記憶會(huì)被保存，從而實(shí)現(xiàn)了長(zhǎng)期記憶功能；當(dāng)輸入的序列中出現(xiàn)了重要的信息時(shí)， LSTM 應(yīng)當(dāng)把其存入記憶中，此時(shí)其輸入門(mén)的值會(huì)接近于1；當(dāng)輸入的序列中出現(xiàn)了重要信息，且該信息意味著之前的記憶不再重要時(shí)，輸入門(mén)的值接近1，而遺忘門(mén)的值接近于0，這樣舊的記憶被遺忘，新的重要信息被記憶。經(jīng)過(guò)這樣的設(shè)計(jì)，整個(gè)網(wǎng)絡(luò)更容易學(xué)習(xí)到序列之間的長(zhǎng)期依賴。

▌10.WGAN解決了原始 GAN 中的什么問(wèn)題

直覺(jué)告訴我們：不要讓生成器在高維空間傻傻地布網(wǎng)，讓它直接到低維空間“抓”真實(shí)數(shù)據(jù)。道理雖然是這樣，但是在高維空間中藏著無(wú)數(shù)的低維子空間，如何找到目標(biāo)子空間呢？站在大廈頂層，環(huán)眺四周，你可以迅速定位遠(yuǎn)處的山巒和高塔，卻很難知曉一個(gè)個(gè)樓宇間辦公室里的事情。

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

怎么理解這個(gè)公式？想象你有一個(gè)很大的院子，院子里有幾處坑坑洼洼需要填平，四個(gè)墻角都有一堆沙子，沙子總量正好填平所有坑。搬運(yùn)沙子很費(fèi)力，你想知道有沒(méi)有一種方案，使得花的力氣最少。直覺(jué)上，每個(gè)坑都選擇最近的沙堆，搬運(yùn)的距離最短。但是存在一些問(wèn)題，如果最近的沙堆用完了，或者填完坑后近處還剩好多沙子，或者坑到幾個(gè)沙堆的距離一樣，我們?cè)撛趺崔k？所以需要設(shè)計(jì)一個(gè)系統(tǒng)的方案，通盤(pán)考慮這些問(wèn)題。最佳方案是上面目標(biāo)函數(shù)的最優(yōu)解。

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

為什么Wasserstein 距離能克服JS 距離解決不了的問(wèn)題？理論上的解釋很復(fù)雜，需要證明當(dāng)生成器分布隨參數(shù)θ 變化而連續(xù)變化時(shí)，生成器分布與真實(shí)分布的Wasserstein 距離也隨θ 變化而連續(xù)變化，并且?guī)缀跆幪幙蓪?dǎo)，而JS 距離不保證隨θ 變化而連續(xù)變化。

通俗的解釋，接著“布網(wǎng)”的比喻，現(xiàn)在生成器不再“布網(wǎng)”，改成“定位追蹤”了，不管真實(shí)分布藏在哪個(gè)低維子空間里，生成器都能感知它在哪，因?yàn)樯善髦灰獙⒆陨矸植忌宰鲎兓蜁?huì)改變它到真實(shí)分布的推土機(jī)距離；而JS 距離是不敏感的，無(wú)論生成器怎么變化，JS 距離都是一個(gè)常數(shù)。因此，使用推土機(jī)距離，能有效鎖定低維子空間中的真實(shí)數(shù)據(jù)分布。

▌11.解釋強(qiáng)化學(xué)習(xí)中的策略梯度

在策略梯度中，我們考慮前后兩個(gè)狀態(tài)之間的關(guān)系為，其中st、st+1 是相繼的兩個(gè)狀態(tài)，at 是t 步時(shí)所采取的行動(dòng)，p 是環(huán)境所決定的下個(gè)時(shí)刻狀態(tài)分布。而動(dòng)作at 的生成模型（策略）為，其中πθ 是以θ 為參變量的一個(gè)分布，at 從這個(gè)分布進(jìn)行采樣。這樣，在同一個(gè)環(huán)境下，強(qiáng)化學(xué)習(xí)的總收益函數(shù)，完全由θ 所決定。策略梯度的基本思想就是，直接用梯度方法來(lái)優(yōu)化R(θ)。

可以看出，和Q-learning 不同的是，策略梯度并不估算Q 函數(shù)本身，而是利用當(dāng)前狀態(tài)直接生成動(dòng)作at。這有效避免了在連續(xù)狀態(tài)空間上最大化Q 函數(shù)的困難。同時(shí)，直接用梯度的方法優(yōu)化R(θ) 可以保證至少是局部收斂的。

要使用梯度法，首先要知道如何計(jì)算R(θ) 的導(dǎo)數(shù)。設(shè)τ 為某一次0到T 時(shí)間所有狀態(tài)及行動(dòng)的集合（稱作一條軌跡），則R(θ)=E(r(τ))，其中函數(shù)r 計(jì)算了軌跡τ的得分。我們有，所以

注意最后一步是因?yàn)?img src="http://file.elecfans.com/web1/M00/61/46/pIYBAFuCCcWAeL7eAAAC5X7Weec249.png" />環(huán)境決定從而與θ 無(wú)關(guān)，因此。每個(gè)軌跡τ 所對(duì)應(yīng)的梯度為?

其中sk，ak 為軌跡τ 上每一步的狀態(tài)和動(dòng)作。這樣，給定一個(gè)策略πθ，我們可以通過(guò)模擬獲得一些軌跡，對(duì)于每條軌跡，可以獲得其收益r(τ) 以及每一步的<狀態(tài)、行動(dòng)>對(duì)，從而可以通過(guò)式（11.2）和式（11.3） 獲得當(dāng)前參數(shù)下對(duì)梯度的估計(jì)。一個(gè)簡(jiǎn)單的算法描述如圖11.7 所示。

注意到，?θR(θ) 實(shí)際上是一個(gè)隨機(jī)變量g(τ) 的期望。我們對(duì)g(τ) 進(jìn)行若干次獨(dú)立采樣， 可以獲得對(duì)其期望的一個(gè)估計(jì)。如果能在不改變期望的前提下減少g(τ) 的方差，則能有效提高對(duì)其期望估計(jì)的效率。我們注意到， 所以有

對(duì)于任一個(gè)常量b，我們定義一個(gè)強(qiáng)化梯度

易知，而維持期望不變。經(jīng)過(guò)計(jì)算可以得到最優(yōu)的 b 為

于是，得到一個(gè)改良的算法，如圖11.8 所示。

在上述策略梯度算法中，通過(guò)估算一個(gè)新的強(qiáng)化梯度可以有效縮減原來(lái)梯度的方差，從而提高梯度估算的效率，那么如何推出最優(yōu)的b值呢？

我們回到策略梯度算法，

定義隨機(jī)變量

即式（11.4）中的結(jié)果。

以上內(nèi)容來(lái)自《百面機(jī)器學(xué)習(xí)》，有刪改

本文作者：葫蘆娃

作者：諸葛越 主編，葫蘆娃 著

出版時(shí)間：2018年8月

《百面機(jī)器學(xué)習(xí)——算法工程師帶你去面試》學(xué)習(xí)脈絡(luò)圖

該書(shū)收錄了超過(guò)100道機(jī)器學(xué)習(xí)算法工程師的面試題目和解答，其中大部分源于Hulu算法研究崗位的真實(shí)場(chǎng)景。本書(shū)從日常工作、生活中各種有趣的現(xiàn)象出發(fā)，不僅囊括了機(jī)器學(xué)習(xí)的基本知識(shí)，而且還包含了成為優(yōu)秀算法工程師的相關(guān)技能。