掌握動(dòng)態(tài)規(guī)劃，助你成為優(yōu)秀的算法工程師
1.導(dǎo)論
相信很多同學(xué)已經(jīng)在為今年的校招做準(zhǔn)備了，隨著AI的火熱，越來越多的同學(xué)涌入了算法的行當(dāng)之中。那去年校招的算法崗是有多火熱？在知乎上看到這么一條帖子，先不說內(nèi)容哈，足足400w+的閱讀量啊。
不光是計(jì)算機(jī)或軟件專業(yè)的學(xué)生，很多電子，通信，自動(dòng)化等相關(guān)專業(yè)的同學(xué)也吸引了進(jìn)來。當(dāng)然，這應(yīng)該是件好事。但是相當(dāng)一部分同學(xué)，在學(xué)習(xí)的過程中，尤其是剛?cè)腴T的時(shí)候，可能會(huì)有這樣一個(gè)疑問：算法工程師的算法，為什么不是指《算法導(dǎo)論》中的算法（以下稱為經(jīng)典算法，用以區(qū)分），而是指機(jī)器學(xué)習(xí)里的算法。都叫算法（Algorithm），但好像不是一回事啊，兩者有什么關(guān)系，又有什么區(qū)別呢？
本文試圖通過動(dòng)態(tài)規(guī)劃這一經(jīng)典算法中的重要內(nèi)容，同時(shí)又在機(jī)器學(xué)習(xí)算法中有著廣泛的應(yīng)用，來簡單探討一下這兩種“算法”。
2.動(dòng)態(tài)規(guī)劃
首先，動(dòng)態(tài)規(guī)劃（Dynamic Programming）是《算法導(dǎo)論》中的重要章節(jié)，同時(shí)也是在機(jī)器學(xué)習(xí)算法中有著非常重要應(yīng)用的一種優(yōu)化算法?？梢哉f是，無論是否是算法工程師都應(yīng)該掌握的一種算法。再功利一點(diǎn)說，動(dòng)態(tài)規(guī)劃也是諸多面試官特別喜歡考的一種題型，下面就帶大家稍微溫故一下。
按照教材[1]的介紹，動(dòng)態(tài)規(guī)劃通常需要按如下4個(gè)步驟來進(jìn)行設(shè)計(jì)：
-
刻畫一個(gè)最優(yōu)解的結(jié)構(gòu)特征。
-
-
計(jì)算最優(yōu)解的值，通常采用自底向上的方法。
-
利用計(jì)算出信息構(gòu)造一個(gè)最優(yōu)解。
簡單點(diǎn)說，動(dòng)態(tài)規(guī)劃算法的核心就是大問題拆成重復(fù)的小問題，同時(shí)記住已經(jīng)解決了的小問題的解。那如果你去網(wǎng)上搜搞ACM或者OI大神的說法，他們都會(huì)說動(dòng)態(tài)規(guī)劃是一個(gè)框，是一種解決問題的思想，而不是某種具體的算法。下面我們詳細(xì)來看看，時(shí)髦的機(jī)器學(xué)習(xí)是怎么往動(dòng)態(tài)規(guī)劃這個(gè)框里填的。
2.1 編輯距離
說到編輯距離（Edit distance），大家可能都比較熟悉。在自然語言處理（Natural Language Processing，又NLP）中，編輯距離是計(jì)算文本相似度的一種基本距離計(jì)算方式。簡單來說，就是只能通過替換，刪除，插入操作，將一串字符串變?yōu)榱硪淮址牟僮鲾?shù)。而求最小編輯距離的過程，就是一個(gè)典型的動(dòng)態(tài)規(guī)劃的過程。
如果計(jì)算兩個(gè)字符串的編輯距離，我們可以看做是父問題，那他的子問題自然就是如何求更小字符串之間的編輯距離。那上面提到，動(dòng)態(tài)規(guī)劃不僅要將父問題拆分成子問題，更要記下子問題的解，以達(dá)到節(jié)省空間和時(shí)間的效果。
下圖可以看出，這個(gè)D矩陣，就是我們用來存儲(chǔ)這個(gè)子問題解的空間，假設(shè)兩個(gè)字符串的長度分別為m和n。而D(i, j)如圖所示，則是我們定義的最優(yōu)解的結(jié)構(gòu)特征，實(shí)際表示的就是長度為i和長度為j的兩個(gè)子序列之間的最小編輯距離，我們把它從左至右，從下到上填到每個(gè)格子里，一直到矩陣的右上角，就可以得到我們要的最小編輯距離。那么最終我們的空間復(fù)雜度為O(mn)，而時(shí)間復(fù)雜度同樣為O(mn)，相比采用分治的思想遞歸地進(jìn)行求解還是要快很多。（這里篇幅有限，就不贅述代碼了，有興趣的同學(xué)可以自行網(wǎng)上搜索）
https://web.stanford.edu/class/cs124/lec/med.pdf
2.2 動(dòng)態(tài)時(shí)間規(guī)整
說完NLP里的相似度計(jì)算，咱們再來看看語音識別里有沒有類似的算法用到動(dòng)態(tài)規(guī)劃呢？答案是肯定的。這個(gè)算法就叫動(dòng)態(tài)時(shí)間規(guī)整（Dynamic time warping），簡稱DTW，一聽名字是不是感覺就很動(dòng)態(tài)規(guī)劃。DTW算法是傳統(tǒng)語音識別中的重要方法，起初是用于孤立詞的語音識別，判斷兩段語音是否為同一個(gè)單詞。實(shí)際上，只要是時(shí)間序列，如下圖[2]，都可以用來計(jì)算相似度，不局限于語音識別當(dāng)中，例如股市的交易策略，手勢識別等等場景都有應(yīng)用。
在語音信號中，有一個(gè)很大的問題就是，信號長度并不相等，即使是同一個(gè)人說同一個(gè)單詞，也會(huì)有語速上的差別。那這個(gè)時(shí)候基于歐幾里得距離（Euclidean Distance）的方法就不奏效了，但是兩個(gè)時(shí)間序列形狀上又非常的相似，于是我們就希望可以通過某種對齊的方式來衡量這兩個(gè)時(shí)間序列的相似性。如上圖所示，箭頭代表了兩個(gè)時(shí)間序列中的相似點(diǎn)。我們用所有相似點(diǎn)之間的距離和來表示這種相似度，稱之為規(guī)整路徑距離。
大家看到這個(gè)“棋盤”好像和我們上面講到的編輯距離中的D矩陣很像。沒錯(cuò)，假設(shè)n為序列A的長度，m為序列B的長度，D(m, n)就是上面這兩個(gè)序列的規(guī)則路徑距離。至于D(m, n)怎么求？又到了我們的動(dòng)態(tài)規(guī)劃發(fā)揮威力的時(shí)候。還是像求最小編輯距離一樣，D(i, j)如下式所求，并且由左到右，由下到上填入D矩陣中，最終求得的右上角的值就是我們的規(guī)整路徑距離。時(shí)間復(fù)雜度依然為O(mn)。
說到這里，好像動(dòng)態(tài)規(guī)劃不就是畫個(gè)矩陣，按照D(i, j)的計(jì)算方法填滿矩陣，得到右上角的最終解。嗯，好像也有點(diǎn)道理。那我們接下來繼續(xù)看看，這樣說對不對。
2.3 維特比算法
如果說前面兩種算法和機(jī)器學(xué)習(xí)只能算沾邊的話，那我們現(xiàn)在要說的維特比算法（Viterbi Algorithm）可以說是動(dòng)態(tài)規(guī)劃在機(jī)器學(xué)習(xí)當(dāng)中的典范了，尤其如果是做自然語言處理方向的話，維特比算法更是不可不知，哪怕在如今deep learning當(dāng)?shù)赖臅r(shí)代。在自然語言處理中，像分詞、詞性標(biāo)注、命名實(shí)體識別、輸入法等等任務(wù)中都有非常重要的應(yīng)用。
除了前面介紹的計(jì)算兩個(gè)序列之間的距離以外，動(dòng)態(tài)規(guī)劃還有一個(gè)重要的應(yīng)用場景，就是計(jì)算有向無環(huán)圖（DAG）中兩個(gè)節(jié)點(diǎn)間的最短路徑，而維特比算法就是針對籬笆網(wǎng)絡(luò)（Lattice Network）這一特殊的有向無環(huán)圖而提出的。
如上圖所示，這是一個(gè)部分的籬笆網(wǎng)絡(luò)，中間我們假設(shè)有N列，每列有4個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)之間的權(quán)重我們暫時(shí)忽略。這個(gè)時(shí)候，網(wǎng)絡(luò)的最左邊有一個(gè)節(jié)點(diǎn)為S，最右端有一個(gè)節(jié)點(diǎn)為E。如果我想求S到E之間的最短路徑，理所當(dāng)然，我們?nèi)绻F舉出所有的路徑進(jìn)行比較，也就是4N條路徑，自然可以得到結(jié)果，但如果層數(shù)很多或者每層的節(jié)點(diǎn)數(shù)很多的時(shí)候，這種方法就顯得不夠友好了。
既然窮舉法太過暴力，自然我們想試試能不能用動(dòng)態(tài)規(guī)劃來解決。首先，籬笆網(wǎng)絡(luò)有這么一個(gè)特點(diǎn)，就是假設(shè)我們從第一列走到最后一列，我們一定會(huì)經(jīng)過其中的第i時(shí)刻的某個(gè)節(jié)點(diǎn)。這個(gè)當(dāng)然是顯而易見的，但給我們帶來了一個(gè)好處，那就是當(dāng)我們計(jì)算最終的最短路徑時(shí)，假設(shè)第i列有k個(gè)節(jié)點(diǎn)，如果我們已經(jīng)計(jì)算了從開頭到第i列所有k個(gè)節(jié)點(diǎn)的最短路徑，那最終的最短路徑一定是經(jīng)過其中之一。第二，如果說最短路徑P經(jīng)過某個(gè)節(jié)點(diǎn)xij，那么從起始節(jié)點(diǎn)S到節(jié)點(diǎn)xij的這段子路徑Q，一定是從起始節(jié)點(diǎn)S到xij的最短路徑，否則總路徑P也不再是最短路徑，這就自相矛盾了。
有了這兩個(gè)特性，終于可以試試動(dòng)態(tài)規(guī)劃了。同樣我們從最左邊的S節(jié)點(diǎn)出發(fā)，到第1列的4個(gè)節(jié)點(diǎn)，因?yàn)楦髦挥幸欢尉嚯x，那自然這4個(gè)距離d(S, x1i)為S節(jié)點(diǎn)到這4個(gè)節(jié)點(diǎn)的最短距離。當(dāng)我們走到第2列時(shí)，根據(jù)之前的特性，一定會(huì)經(jīng)過第1列的某個(gè)節(jié)點(diǎn)。此時(shí)的S節(jié)點(diǎn)到第2列某個(gè)節(jié)點(diǎn)的距離則為d(S, x2j)=d(S, x1i) + d(x1i, x2j)。而第1列有4個(gè)節(jié)點(diǎn)，所以d(S, x2j)應(yīng)該是取4個(gè)距離中的最小值，當(dāng)然在這一過程中，我們計(jì)算了4次，對于第2列的每個(gè)節(jié)點(diǎn)，我們都去進(jìn)行如上的計(jì)算。所以在從第1列走到第2列的過程中，我們計(jì)算了4×4次，更關(guān)鍵的是我們把d(S, x2j)都要保存下來，作為我們下一次計(jì)算的基礎(chǔ)。
而這個(gè)保存中間結(jié)果的過程，很明顯地體現(xiàn)出了前文所述的動(dòng)態(tài)規(guī)劃的特點(diǎn)。接下來，我們繼續(xù)走到第3列，同樣的，S節(jié)點(diǎn)到第3列某個(gè)節(jié)點(diǎn)的距離為d(S, x3k)=d(S, x2j) + d(x2j, x3k)。這個(gè)時(shí)候我們發(fā)現(xiàn)，等式右邊的第一項(xiàng)，可以直接取我們剛剛保存的中間結(jié)果。對于d(S, x3k)，我們依然是計(jì)算4次，取最小值保存下來。同樣，需要遍歷第3列的4個(gè)節(jié)點(diǎn)，所以又是4×4次計(jì)算。也就是說，每往前走1列，我們就計(jì)算了4×4次。以此類推，到最右邊的節(jié)點(diǎn)E的時(shí)候，我們需要計(jì)算N×42次，相比于窮舉法的4N條路徑，這個(gè)效率已經(jīng)是非常大的進(jìn)步，把指數(shù)級的復(fù)雜度降低到了多項(xiàng)式級別！
2.4 CYK算法
這個(gè)CYK算法大家可能會(huì)有點(diǎn)陌生，全名為Cocke–Younger–Kasami算法，是以三位作者的姓名共同命名的。這個(gè)算法其實(shí)是句法分析方向的一個(gè)經(jīng)典算法，因?yàn)樘岢龅臅r(shí)間是在基于規(guī)則的年代，所以即使是做NLP的同行，依然有很多同學(xué)并不了解。所以這里給大家多交代一些背景知識。
首先，CYK算法是基于喬姆斯基（Chomsky）范式的上下文無關(guān)語法（Context Free Grammar）。感覺越解釋概念越多了哈。簡單點(diǎn)說，喬姆斯基范式有兩種形式。
這里，ABC都是非終結(jié)符，就是像名詞短語（NP），動(dòng)詞短語（VP）等等，x是終結(jié)符，比如單詞就是終結(jié)符。對于A這個(gè)非終結(jié)符，要么拆分成更小的2個(gè)非終結(jié)符，要么就到此為止，右邊是一個(gè)單詞。例如：”吃藥“這個(gè)動(dòng)詞短語，就可以按下面的方式進(jìn)行句法分析。
好了，介紹完了背景知識，我們的任務(wù)就是給定一個(gè)句法規(guī)則的集合，對于任意一個(gè)句子，將它按照這個(gè)句法規(guī)則集合進(jìn)行解析。下圖就是我們的一個(gè)句法解析樹，也就是最終的一個(gè)結(jié)果。
對于一次解析來說，如果嘗試去解析出所有的結(jié)果，那將是指數(shù)級的復(fù)雜度，而CYK算法就是利用動(dòng)態(tài)規(guī)劃的思想將復(fù)雜度降低到了多項(xiàng)式級。假設(shè)我們的句子的單詞數(shù)為n，我們先畫一個(gè)如下圖的下三角矩陣，橫坐標(biāo)為位置i，縱坐標(biāo)為跨度j。
http://ccl.pku.edu.cn/doubtfire/Course/Computational%20Linguistics/contents/CYK_parsing.pdf
其中最關(guān)鍵的就是步驟2中的最內(nèi)層循環(huán)，對于一個(gè)跨度內(nèi)所有分割點(diǎn)k。簡單點(diǎn)說，就是在給定了位置和跨度的一個(gè)短語中，不斷調(diào)整中間的分割點(diǎn)位置，使得分割點(diǎn)兩邊的短語子串能夠符合給定的句法規(guī)則。當(dāng)子串符合句法規(guī)則時(shí)，把對應(yīng)的結(jié)果記錄下來，并為后續(xù)的解析所用，這就體現(xiàn)了動(dòng)態(tài)規(guī)劃思想的核心！
2.5 分詞
上面我們介紹過維特比算法，在分詞任務(wù)中有重要的應(yīng)用，但現(xiàn)在我們又要來提分詞了，那這里的動(dòng)態(tài)規(guī)劃和維特比有什么不一樣呢。首先，目前的分詞的主流算法里有這么兩種，一種是基于字的模型分詞算法，還有一種則是基于詞典的分詞方法。前者，主要有基于隱馬爾可夫（HMM）的生成式模型、基于條件隨機(jī)場（CRF）的判別式模型以及基于神經(jīng)網(wǎng)絡(luò)的分詞算法，在這些算法的解碼部分，都可以使用維特比算法進(jìn)行解碼。那這節(jié)要說的動(dòng)態(tài)規(guī)劃則是基于詞典的分詞算法里用到的。
基于詞典的分詞算法是如何工作的呢？舉一個(gè)簡單的例子，”我來到達(dá)觀數(shù)據(jù)”。首先，我們根據(jù)詞典將句子進(jìn)行簡單的匹配，將句中匹配到的詞典詞和所有的單字組合起來，作為節(jié)點(diǎn)，構(gòu)造成一個(gè)分詞的詞圖，如下圖所示（邊的權(quán)重假設(shè)都為1）。那這個(gè)圖里從S節(jié)點(diǎn)到E節(jié)點(diǎn)的每條路徑，都代表這一種分詞的結(jié)果。我們希望正確的分詞結(jié)果，理應(yīng)是一條概率最大的的路徑，這樣才能把一個(gè)語言學(xué)的問題轉(zhuǎn)化成一個(gè)數(shù)學(xué)的問題，從而讓計(jì)算機(jī)可以輔助我們得到正確的分詞結(jié)果。
因?yàn)榫渥邮琼樞虻?，所以這個(gè)詞圖表現(xiàn)為一個(gè)有向無環(huán)圖。還記得前面講到的維特比算法是針對特殊的有向無環(huán)圖來計(jì)算最短路徑，這里的詞圖就顯得更為一般些。如何求得有向無環(huán)圖的最短路徑呢，這個(gè)時(shí)候，我們需要先對詞圖進(jìn)行拓?fù)渑判?，然后再利用?dòng)態(tài)規(guī)劃求排序后的詞圖最大概率路徑。拓?fù)渑判虻慕Y(jié)果如下圖：
有了拓?fù)渑判虻慕Y(jié)果，我們就可以動(dòng)態(tài)規(guī)劃了。上面我們講Viterbi算法的時(shí)候，提到這么一個(gè)性質(zhì)，如果最終的最短路徑P經(jīng)過某個(gè)節(jié)點(diǎn)i，那么經(jīng)過這個(gè)節(jié)點(diǎn)的子路徑Q一定是起始節(jié)點(diǎn)S到節(jié)點(diǎn)i的最短路徑，否則最短路徑P一定有比它更短的路徑存在。在這里，我們是求最大概率路徑，其實(shí)原理是一樣的。對于到最終節(jié)點(diǎn)E的路徑Route(E)，有：
實(shí)際上，我們可以一直寫下去，而這些子路徑就是動(dòng)態(tài)規(guī)劃中的最優(yōu)子結(jié)構(gòu)，我們只需要再求解這些子結(jié)構(gòu)中的最優(yōu)解即可。相比于，列舉出所有的分詞路徑，這種計(jì)算方法是要快上很多。在計(jì)算最大概率的過程中，有不少小trick。期待后續(xù)的達(dá)觀技術(shù)分享為大家詳細(xì)介紹。
2.6 強(qiáng)化學(xué)習(xí)策略迭代
說到強(qiáng)化學(xué)習(xí)，這里不得不首先引用一下Sutton在《Reinforcement Learning: An Introduction》關(guān)于動(dòng)態(tài)規(guī)劃的一些表述。
DP provides an essential foundation for the understanding of the methods presented in the rest of this book. In fact, all of these methods can be viewed as attempts to achieve much the same effect as DP, only with less computation and without assuming a perfect model of the environment.
雖然動(dòng)態(tài)規(guī)劃在實(shí)際的強(qiáng)化學(xué)習(xí)中，有諸多的限制，但動(dòng)態(tài)規(guī)劃所具有的理論基礎(chǔ)是強(qiáng)化學(xué)習(xí)必不可少的，可見動(dòng)態(tài)規(guī)劃之于強(qiáng)化學(xué)習(xí)的重要意義！
強(qiáng)化學(xué)習(xí)和大家熟悉的機(jī)器學(xué)習(xí)有著很大的不同，它沒有用到標(biāo)注數(shù)據(jù)進(jìn)行supervise，而且當(dāng)前的動(dòng)作可能會(huì)影響到后續(xù)的結(jié)果。既然是動(dòng)作，肯定會(huì)考慮到很多因素。那么在強(qiáng)化學(xué)習(xí)里，我們需要考慮哪些變量呢？首先肯定是回報(bào)了，這里用R來表示，不同的回報(bào)決定了不同的動(dòng)作?；貓?bào)又分為長期的和短期的，就好比做基礎(chǔ)算法研究，短期看沒什么回報(bào)，但長期來說就是技術(shù)的護(hù)城河。我們通過衰減系數(shù)??來表示，0≤??<1。除此以外，我們還要看當(dāng)前所處的狀態(tài)S來決定所做的動(dòng)作。有了狀態(tài)的集合，那自然要考慮狀態(tài)之間的轉(zhuǎn)移關(guān)系，就是我們的P，狀態(tài)轉(zhuǎn)移矩陣，但因?yàn)閷τ诤芏鄬?shí)際問題，狀態(tài)實(shí)在太多，所以每個(gè)狀態(tài)只能考慮前一個(gè)狀態(tài)的相關(guān)情況，這樣就大大簡化了問題的復(fù)雜度，這種性質(zhì)我們也叫馬爾科夫性。最后，加上我們的一系列動(dòng)作A，就有了馬爾科夫決策過程(Markov Decision Process, MDP)。
http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/MDP.pdf
好了，現(xiàn)在有了這些基本要素了，下面要用這些要素做什么呢？比如機(jī)器學(xué)習(xí)里，我們希望是最小化損失函數(shù)。而在強(qiáng)化學(xué)習(xí)里，我們則是希望最大化的累積回報(bào)，比如下棋的時(shí)候，只要最終贏了即可，而不是要每步都要吃掉對方一些棋子。這時(shí)候，我們就先定義一下這個(gè)累積回報(bào)，假設(shè)從t時(shí)刻開始到最終時(shí)刻T，并且加上之前提到的衰減系數(shù)??，則有：
既然這個(gè)G~t~是從t時(shí)刻到最終狀態(tài)的累積回報(bào)，那就不光是一條路徑的累積，而是所有的路徑的總和，當(dāng)狀態(tài)過多的時(shí)候，我們就沒法計(jì)算。這個(gè)時(shí)候需要引入一個(gè)狀態(tài)值函數(shù)，作為從某狀態(tài)開始的回報(bào)總和的期望。
這個(gè)狀態(tài)值函數(shù)就是用來衡量某一個(gè)狀態(tài)的好壞。除了我們上面提到的幾個(gè)要素以外，我們在某個(gè)狀態(tài)執(zhí)行什么動(dòng)作，并不是固定的，那就需要引入新的概念策略??，作為動(dòng)作關(guān)于狀態(tài)的分布。則上式就變?yōu)椋?/span>
問題又來了，這個(gè)期望其實(shí)也不太好算，因?yàn)槠渲幸粋€(gè)狀態(tài)的價(jià)值函數(shù)需要計(jì)算后續(xù)所有狀態(tài)的回報(bào)。既然是馬爾科夫決策過程，那自然會(huì)想到用迭代的思想去計(jì)算。得到其遞歸的形式Bellman方程，如下式(詳細(xì)推導(dǎo)過程見7)
這樣，在給定策略的情況下，我們就可以迭代地去求每一個(gè)狀態(tài)的值函數(shù)了。從這個(gè)更新公式，也可以看出，強(qiáng)化學(xué)習(xí)里的動(dòng)態(tài)規(guī)劃將圍繞狀態(tài)值函數(shù)的更新這個(gè)最優(yōu)子結(jié)構(gòu)而做文章。
對于從v1到最終的v*的每次迭代vk，我們利用上式對值函數(shù)進(jìn)行更新，直到收斂于V*（證明略）。這一步就叫做策略評估。這時(shí)候，我們可以對于取得最大的動(dòng)作值函數(shù)q而得到的新策略，對新的策略進(jìn)行策略評估步驟。直到我們的策略不再變化，此時(shí)得到的策略即為最優(yōu)策略。
一下子說了那么多涉及到動(dòng)態(tài)規(guī)劃的機(jī)器學(xué)習(xí)算法，相信讀者朋友們還可以列舉出更多（歡迎評論區(qū)留言）。我們在動(dòng)態(tài)規(guī)劃這個(gè)框里填了那么多機(jī)器學(xué)習(xí)算法，而機(jī)器學(xué)習(xí)算法也非常依賴動(dòng)態(tài)規(guī)劃的高效率，可謂是你中有我，我中有你。
從上面舉的很多例子大家也可以看到，動(dòng)態(tài)規(guī)劃更側(cè)重于對問題求解的優(yōu)化，比如求最短距離，實(shí)際上是可以通過暴力方法進(jìn)行求解的，而動(dòng)態(tài)規(guī)劃則是提高了求解的效率。但機(jī)器學(xué)習(xí)算法可不僅僅是對問題的求解進(jìn)行優(yōu)化，它要解決的問題往往沒有精確解，同時(shí)也沒法通過窮舉等暴力方法進(jìn)行求解。需要對問題進(jìn)行清晰地定義并建模，重點(diǎn)在于學(xué)習(xí)的過程，基于對訓(xùn)練數(shù)據(jù)的擬合來預(yù)測新的樣本。
而說完動(dòng)態(tài)規(guī)劃，大家很容易又聯(lián)想到貪心算法，同樣也是經(jīng)典算法中的一個(gè)重要的優(yōu)化方法。比如word2vec中的霍夫曼樹（Huffman Tree），比如seq2seq中需要用到的集束搜索（Beam Search），都是借鑒了貪心算法的思想。前面我們提到了求最短路徑問題雖然是動(dòng)態(tài)規(guī)劃，這實(shí)際上又涉及到經(jīng)典算法中圖論里的內(nèi)容，類似的還有一系列的概率圖模型（Probabilistic Graphical Model）。事實(shí)上，還有很多機(jī)器學(xué)習(xí)算法運(yùn)用到了經(jīng)典算法里的內(nèi)容，這里就不一一列舉了。
總之，對于一名優(yōu)秀的算法工程師來說，經(jīng)典算法的掌握必不可少，對于機(jī)器學(xué)習(xí)算法的理解也有很大的幫助。希望大家能夠認(rèn)真掌握，”舉一反三”，在接下來的秋招中好好發(fā)揮。
1.Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. “算法導(dǎo)論.” 第 2 版 機(jī)械工業(yè)出版社 (2006).
2.Salvador, Stan, and Philip Chan. “FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space.”
3.吳軍. 數(shù)學(xué)之美. 人民郵電出版社, 2012.
4.宗成慶. 統(tǒng)計(jì)自然語言處理. 清華大學(xué)出版社, 2013
5.黃海安. https://www.zybuluo.com/Team/note/1123968
6.Wiering, Marco, and Martijn Van Otterlo. “強(qiáng)化學(xué)習(xí).” 機(jī)械工業(yè)出版社.
7.http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/MDP.pdf
楊慧宇：達(dá)觀數(shù)據(jù)NLP技術(shù)專家，負(fù)責(zé)達(dá)觀數(shù)據(jù)底層NLP算法效果的優(yōu)化，以及財(cái)務(wù)審核相關(guān)產(chǎn)品的研發(fā)工作。
