我們所做的topic，一般有幾個(gè)階段：

Analysis: 分析問題，找到問題的關(guān)鍵

Modeling / Formulation:  對(duì)問題進(jìn)行數(shù)學(xué)抽象，建立模型，或者formulate目標(biāo)函數(shù)

Solving: 設(shè)計(jì)出求解的算法

Experiments: 實(shí)驗(yàn)

最近的工作都集中在Solving這部分，就說說這個(gè)吧。

求解的方法

求解問題有很多不同的方法，就我知道的來說，大概有這么幾個(gè)大家族。

1. Heuristics。 就是根據(jù)對(duì)問題的觀察而設(shè) 計(jì)的一些簡單的方法，不一定遵循什么規(guī)范，或者有什么深刻的數(shù)學(xué)根據(jù)。這類方法往往比較簡單易懂，intuition比較明顯，很多時(shí)候 performance也挺不錯(cuò)的，不見得比高深的方法差，因而在實(shí)際工程中很受歡迎，幾乎應(yīng)用在全部的學(xué)科。不過，好像很多朋友對(duì)這類方法頗為不屑，認(rèn) 為“沒有技術(shù)含量”，或者叫做“沒有理論深度”。

   確實(shí)，有相當(dāng)部分的Heuristics純粹粗制濫造，投機(jī)取巧。不過，還有很多Heuristics雖然簡單，但是切中問題要害，在 長期的復(fù)雜的實(shí)際應(yīng)用中經(jīng)受住了考驗(yàn)。這些方法，表面看來可能只是再簡單不過的幾條四則運(yùn)算公式，說不上多少理論，但是并不代表它沒有深刻的理論基礎(chǔ)。一 個(gè)典型的例子是Google PageRank中使用的傳導(dǎo)公式（簡單版本），道理和公式都很簡單，可是，做過類似工作的朋友可能都知道，它和代數(shù)圖論以及馬爾可夫隨機(jī)過程有著很深的 聯(lián)系。 又比如，F(xiàn)ourier Transform在剛出來的時(shí)候，僅僅是工程師的一些heuristics，后來關(guān)于它的理論已經(jīng)成為了泛函分析的一個(gè)核心組成部分，也是信號(hào)處理的理 論基礎(chǔ)之一。

   真正好的heuristics，它的好處肯定不是瞎懵出來，而是有內(nèi)在原因的。對(duì)它們的原理的探索，不斷帶動(dòng)理論方面的發(fā)展，甚至創(chuàng)造 了新的理論方向。說到這里，有人可能會(huì)argue，這是“理論家們?cè)诠逝摶祜埑?#8221;。Hmm，這種說法我不能認(rèn)同，但是，確實(shí)存在“把工程方法胡亂進(jìn)行 理論化”的事實(shí)。什么才叫有價(jià)值的理論化，而不是故弄玄虛，確實(shí)值得思考，這里先不展開了。

2. Analytical Solution。 當(dāng)你把 問題formulate出來后，有些情況是直接可以從問題推導(dǎo)出解析解的。這種情況通常存在于objective function是Linear或者Quadratic的情況。大家都很喜歡這種情況的出現(xiàn)，理論漂亮，實(shí)現(xiàn)簡潔。但是，據(jù)我的觀察，很多情況下，這種 elegance是通過減化模型換取的。把cost寫成quadratic term，把distribution假設(shè)為Gauss，很多時(shí)候都能得到這樣的結(jié)果。

   我不反對(duì)進(jìn)行簡化，也欣賞漂亮的analytical solution，如果它把問題解決得很好。但是，這里面有個(gè)問題，很多能獲得簡單解析解的問題已經(jīng)被做過了，剩下的很多難點(diǎn)，未必是一個(gè)簡化模型能有效 解決的。簡化是一種很好的方法，但是，使用起來，尤其是在實(shí)際中的應(yīng)用必須慎重，要清楚了解它們可能帶來的問題。

   比如說，很多模型喜歡使用差的平方來衡量誤差大小。但是，這很早就被指出是unrobust的，一個(gè)很大的deviation會(huì) dominate整個(gè)optimization，使得solution嚴(yán)重偏離方向。如果這種robustness在帶解決的問題中是一個(gè)必須考慮的要 素，那么用平方誤差就要仔細(xì)考慮了。

3. Numerical Optimization。 如 果formulation沒有解析解，那么自然的想法就是使用數(shù)值方法求解。目前大家常用的是基于Gradient/Hessian之類的local optimization的方法，有時(shí)會(huì)加上random initialization。如果objective function是convex的，那么這種方法保證收斂到global optimal，這是大家很希望的。convex problem無論在formulation還是在solution的階段，都是很有學(xué)問的。很多問題可以formulate成convex的，但是未必 都那么直接，這需要有這方面的基礎(chǔ)。Solving一個(gè)convex problem有現(xiàn)成的方法，但是，如果能對(duì)問題的結(jié)構(gòu)有insightful的觀察，可能能利用問題本身的特點(diǎn)大幅度降低求解的復(fù)雜度——這往往比直接 把問題扔進(jìn)solver里面等答案更有意義。

   除了convex optimization，還有一種數(shù)值方法應(yīng)用非常廣泛，叫做coordinate ascend或者alternate optimization。大概的思路是，幾個(gè)有關(guān)的變量，輪流選擇某個(gè)去優(yōu)化，暫時(shí)固定其它的。在Machine Learning里面非常重要的Expectation-Maximization (EM算法)就屬于這個(gè)大家族。另外，很多復(fù)雜的graphical model采用的variational inference也是屬于此類。使用這類方法，有兩個(gè)問題：一個(gè)是如果幾個(gè)variable之間相互影響，變一個(gè)，其他跟著變的話，那么直接使用這種方 法可能是錯(cuò)誤的，并不能保證收斂。另外一個(gè)問題是，如果problem不是convex的話，可能沒有任何保證你得到的solution和global solution有聯(lián)系。很可能，你得到的解和真正的全局最優(yōu)解相差十萬八千里。這個(gè)沒有什么通用有效的途徑來解決。不過，針對(duì)具體問題的結(jié)構(gòu)特點(diǎn)，在求 解過程中施加一定的引導(dǎo)是有可能的。

4. Dynamic Programming。 這個(gè)方 法更多見于經(jīng)典計(jì)算機(jī)算法中，不過現(xiàn)在越來越多在Vision和Learning見到它的影子。主要思路是把大問題分解為小問題，總結(jié)小問題的 solution為大問題的solution。至于如何設(shè)計(jì)分解和綜合的過程，依賴于對(duì)問題的觀察和分析，并無通用的法則可循。用DP解決問題的洞察力需 要逐步的積累。不少經(jīng)典算法就源自于DP，比如shotest path。一個(gè)可能有用的觀察是，如果問題或者模型呈現(xiàn)鏈狀，樹狀，或者有向無環(huán)圖結(jié)構(gòu)的，可能很有希望能通過DP高效解決。

5. Local Exchange。 很多建立在圖上的 問題，都可以通過某種局部交換來達(dá)到全局的平衡。像Belief propagation, Junction tree等等在graphical model的重要inference方法，還有tranduction model，都用到了類似的策略。這在實(shí)踐中被證明為非常有效。但是，并不是隨便設(shè)計(jì)的局部交換過程都是收斂的。這里面需要關(guān)注兩個(gè)問題：(1)交換過程 是不是能保證某些重要的invariance不被破壞；(2)交換過程中，是不是有一個(gè)objective，比如距離全局平衡的deviation，它在 每一步都保持單調(diào)。有很多交換過程，在有向無環(huán)圖中保證收斂，但是，在帶環(huán)圖中由于信息的重復(fù)傳遞可能引起不穩(wěn)定，或者不能收斂到正確的解。

6. Monte Carlo Sampling。 蒙特 卡羅采樣的原理非常簡單，就是用樣本平均，來逼近期望（這個(gè)可能需要用intractable的積分完成，沒法直接算）。求平均很簡單，關(guān)鍵在于采樣過 程。我們求解問題，通常是在后驗(yàn)分布中采樣，這種分布在大部分問題中，不要說直接采樣了，可能連解析形式都沒法給出。如果采樣問題有效解決了，基本上我們 研究的大部分問題其實(shí)都可以通過采樣完成。

   由于直接采樣往往非常困難，于是就產(chǎn)生了其它的方法，間接做這個(gè)事情。一種想法就是，既然p(x)不好直接采，我找一個(gè)比較容易采樣的 q(x)來逼近p(x)，然后給從q(x)采出的每個(gè)樣本加一個(gè)weight，p(x) / q(x)。這在理論上被嚴(yán)格證明是對(duì)的——這種方法叫做Importance Sampling。這里的問題在于，如果q(x)和p(x)不太接近，那么采樣效率非常低下，如果在一個(gè)高維空間，可能采1000年都達(dá)不到要求。可是， 要得到一個(gè)approximate很好的q(x)本身不比直接從p(x)采樣來得容易。

   還有一種聰明一點(diǎn)的方法，叫sequential importance sampling。在這里面q(x)，不是一蹴而就建立起來的，而是每個(gè)樣本先采一部分，然后根據(jù)那部分，確定下一部分的proposal distribution，繼續(xù)采，也就是說q(x)和樣本都是dynamically built up。這個(gè)方法在vision里面一個(gè)非常著名的應(yīng)用是用于tracking，相應(yīng)發(fā)展出來的方法論叫做particle filtering。

   另外一大類重要的采樣方法，叫Markov Chain Monte Carlo(MCMC)。這個(gè)的想法是，設(shè)計(jì)一個(gè)馬爾科夫鏈，讓它的平衡分布恰好是p(x)，那么等它平衡時(shí)開始采。以前我們做隨機(jī)過程作業(yè)是已知一個(gè) markov chain，求equilibrium distribution，設(shè)計(jì)MCMC就是反過來了。最重要的MCMC方法莫過于Metropolis-Hastings Algorithm和Gibbs Sampling，前者常被用于設(shè)計(jì)在solution space的隨機(jī)游走(Random walk)，后者則是conditional sampling的基礎(chǔ)方法。

   可是Markov過程怎么轉(zhuǎn)移呢。最簡單的Random Walk結(jié)合acceptance rate之后理論上是對(duì)的?？墒牵宻ampler隨便亂走，猴年馬月才能把solution space走一遍阿。于是，有人提出結(jié)合一個(gè)solution space的局部信息來引導(dǎo)它往有用的方向走。一個(gè)重要的方法叫做Hybric Monte Carlo(HMC)，想法就是把它模擬成一個(gè)物理場，把要sample的分布視為波爾茲曼分布后獲得物理場的勢能，通過哈密頓動(dòng)力學(xué)模型（其實(shí)就是牛頓 力學(xué)的推廣）來驅(qū)動(dòng)sampler?？墒?，如果問題更為復(fù)雜呢，比如整個(gè)solution space有幾個(gè)井，sample掉到某一個(gè)井可能出不來了。為了解決這個(gè)問題，一種重要的方法叫Tempering，就是開始給分子充分加熱，讓它獲得 足夠的動(dòng)能能在各個(gè)井之間來回跳，然后逐步冷卻，從而能捕捉到多個(gè)勢井。

   Monte Carlo方法較早的時(shí)候主要用于統(tǒng)計(jì)物理，目前已經(jīng)廣泛應(yīng)用于計(jì)算機(jī)，生物，化學(xué)，地質(zhì)學(xué)，經(jīng)濟(jì)學(xué)，社會(huì)學(xué)等等的研究。這是目前所知道的用于求解復(fù)雜的 真實(shí)模型的最有效的方法。它的核心，就是猜——你直接解不出來，只好猜了，呵呵。但是，怎樣才能猜得準(zhǔn)，則是大有學(xué)問——幾十年來各個(gè)領(lǐng)域關(guān)于Monte Carlo研究的工作汗牛充棟，有很多進(jìn)展，但是還有很長的路要走。

和這里很多留學(xué)生一樣，我一向潛心于自己的學(xué)習(xí)和研究?？墒亲罱?，我們的世界并不寧靜，我認(rèn)識(shí)的不只一個(gè)在美國的朋友受到了不太友好的挑釁——在不 知不覺中，我們可能已經(jīng)身處反分裂和支持奧運(yùn)的前線。我看到包括MIT CSSA在內(nèi)的很多學(xué)生團(tuán)體開始組織起來支持自己的祖國。我沒有具體幫上什么，但是，我對(duì)所有在用自己的行動(dòng)捍衛(wèi)國家榮譽(yù)的同胞懷有最深的敬意。我也希 望，我的努力，能讓外國的朋友明白中國人是值得尊敬的。