How?to?get?a?solution?
我們所做的topic，一般有幾個階段：
Analysis:分析問題，找到問題的關(guān)鍵
Modeling?/?Formulation:對問題進行數(shù)學(xué)抽象，建立模型，或者formulate目標(biāo)函數(shù)
Solving:設(shè)計出求解的算法
Experiments:實驗
最近的工作都集中在Solving這部分，就說說這個吧。
求解的方法
求解問題有很多不同的方法，就我知道的來說，大概有這么幾個大家族。
Heuristics。
就是根據(jù)對問題的觀察而設(shè)計的一些簡單的方法，不一定遵循什么規(guī)范，或者有什么深刻的數(shù)學(xué)根據(jù)。這類方法往往比較簡單易懂，intuition比較明顯，很多時候performance也挺不錯的，不見得比高深的方法差，因而在實際工程中很受歡迎，幾乎應(yīng)用在全部的學(xué)科。不過，好像很多朋友對這類方法頗為不屑，認為“沒有技術(shù)含量”，或者叫做“沒有理論深度”。
確實，有相當(dāng)部分的Heuristics純粹粗制濫造，投機取巧。不過，還有很多Heuristics雖然簡單，但是切中問題要害，在長期的復(fù)雜的實際應(yīng)用中經(jīng)受住了考驗。這些方法，表面看來可能只是再簡單不過的幾條四則運算公式，說不上多少理論，但是并不代表它沒有深刻的理論基礎(chǔ)。一個典型的例子是Google?PageRank中使用的傳導(dǎo)公式（簡單版本），道理和公式都很簡單，可是，做過類似工作的朋友可能都知道，它和代數(shù)圖論以及馬爾可夫隨機過程有著很深的聯(lián)系。又比如，F(xiàn)ourier?Transform在剛出來的時候，僅僅是工程師的一些heuristics，后來關(guān)于它的理論已經(jīng)成為了泛函分析的一個核心組成部分，也是信號處理的理論基礎(chǔ)之一。
真正好的heuristics，它的好處肯定不是瞎懵出來，而是有內(nèi)在原因的。對它們的原理的探索，不斷帶動理論方面的發(fā)展，甚至創(chuàng)造了新的理論方向。說到這里，有人可能會argue，這是“理論家們在故弄玄虛混飯吃”。Hmm，這種說法我不能認同，但是，確實存在“把工程方法胡亂進行理論化”的事實。什么才叫有價值的理論化，而不是故弄玄虛，確實值得思考，這里先不展開了。
Analytical?Solution。
當(dāng)你把問題formulate出來后，有些情況是直接可以從問題推導(dǎo)出解析解的。這種情況通常存在于objective?function是Linear或者Quadratic的情況。大家都很喜歡這種情況的出現(xiàn)，理論漂亮，實現(xiàn)簡潔。但是，據(jù)我的觀察，很多情況下，這種elegance是通過減化模型換取的。把cost寫成quadratic?term，把distribution假設(shè)為Gauss，很多時候都能得到這樣的結(jié)果。
我不反對進行簡化，也欣賞漂亮的analytical?solution，如果它把問題解決得很好。但是，這里面有個問題，很多能獲得簡單解析解的問題已經(jīng)被做過了，剩下的很多難點，未必是一個簡化模型能有效解決的。簡化是一種很好的方法，但是，使用起來，尤其是在實際中的應(yīng)用必須慎重，要清楚了解它們可能帶來的問題。
比如說，很多模型喜歡使用差的平方來衡量誤差大小。但是，這很早就被指出是unrobust的，一個很大的deviation會dominate整個optimization，使得solution嚴(yán)重偏離方向。如果這種robustness在待解決的問題中是一個必須考慮的要素，那么用平方誤差就要仔細考慮了。
Numerical?Optimization。
如果formulation沒有解析解，那么自然的想法就是使用數(shù)值方法求解。目前大家常用的是基于Gradient/Hessian之類的local?optimization的方法，有時會加上random?initialization。如果objective?function是convex的，那么這種方法保證收斂到global?optimal，這是大家很希望的。convex?problem無論在formulation還是在solution的階段，都是很有學(xué)問的。很多問題可以formulate成convex的，但是未必都那么直接，這需要有這方面的基礎(chǔ)。Solving一個convex?problem有現(xiàn)成的方法，但是，如果能對問題的結(jié)構(gòu)有insightful的觀察，可能能利用問題本身的特點大幅度降低求解的復(fù)雜度——這往往比直接把問題扔進solver里面等答案更有意義。
除了convex?optimization，還有一種數(shù)值方法應(yīng)用非常廣泛，叫做coordinate?ascend或者alternate?optimization。大概的思路是，幾個有關(guān)的變量，輪流選擇某個去優(yōu)化，暫時固定其它的。在Machine?Learning里面非常重要的Expectation-Maximization?(EM算法)就屬于這個大家族。另外，很多復(fù)雜的graphical?model采用的variational?inference也是屬于此類。使用這類方法，有兩個問題：一個是如果幾個variable之間相互影響，變一個，其他跟著變的話，那么直接使用這種方法可能是錯誤的，并不能保證收斂。另外一個問題是，如果problem不是convex的話，可能沒有任何保證你得到的solution和global?solution有聯(lián)系。很可能，你得到的解和真正的全局最優(yōu)解相差十萬八千里。這個沒有什么通用有效的途徑來解決。不過，針對具體問題的結(jié)構(gòu)特點，在求解過程中施加一定的引導(dǎo)是有可能的。
Dynamic?Programming。
這個方法更多見于經(jīng)典計算機算法中，不過現(xiàn)在越來越多在Vision和Learning見到它的影子。主要思路是把大問題分解為小問題，總結(jié)小問題的solution為大問題的solution。至于如何設(shè)計分解和綜合的過程，依賴于對問題的觀察和分析，并無通用的法則可循。用DP解決問題的洞察力需要逐步的積累。不少經(jīng)典算法就源自于DP，比如shotest?path。一個可能有用的觀察是，如果問題或者模型呈現(xiàn)鏈狀、樹狀、或者有向無環(huán)圖結(jié)構(gòu)的，可能很有希望能通過DP高效解決。
Local?Exchange。
很多建立在圖上的問題，都可以通過某種局部交換來達到全局的平衡。像Belief?propagation,?Junction?tree等等在graphical?model的重要inference方法，還有tranduction?model，都用到了類似的策略。這在實踐中被證明為非常有效。但是，并不是隨便設(shè)計的局部交換過程都是收斂的。這里面需要關(guān)注兩個問題：
(1)交換過程是不是能保證某些重要的invariance不被破壞；
(2)交換過程中，是不是有一個objective，比如距離全局平衡的deviation，它在每一步都保持單調(diào)。有很多交換過程，在有向無環(huán)圖中保證收斂，但是，在帶環(huán)圖中由于信息的重復(fù)傳遞可能引起不穩(wěn)定，或者不能收斂到正確的解。
Monte?Carlo?Sampling。
蒙特卡羅采樣的原理非常簡單，就是用樣本平均，來逼近期望（這個可能需要用intractable的積分完成，沒法直接算）。求平均很簡單，關(guān)鍵在于采樣過程。我們求解問題，通常是在后驗分布中采樣，這種分布在大部分問題中，不要說直接采樣了，可能連解析形式都沒法給出。如果采樣問題有效解決了，基本上我們研究的大部分問題其實都可以通過采樣完成。
由于直接采樣往往非常困難，于是就產(chǎn)生了其它的方法，間接做這個事情。一種想法就是，既然p(x)不好直接采，我找一個比較容易采樣的q(x)來逼近p(x)，然后給從q(x)采出的每個樣本加一個weight，p(x)?/?q(x)。這在理論上被嚴(yán)格證明是對的——這種方法叫做Importance?Sampling。這里的問題在于，如果q(x)和p(x)不太接近，那么采樣效率非常低下，如果在一個高維空間，可能采1000年都達不到要求?？墒?，要得到一個approximate很好的q(x)本身不比直接從p(x)采樣來得容易。
還有一種聰明一點的方法，叫sequential?importance?sampling。在這里面q(x)，不是一蹴而就建立起來的，而是每個樣本先采一部分，然后根據(jù)那部分，確定下一部分的proposal?distribution，繼續(xù)采，也就是說q(x)和樣本都是dynamically?built?up。這個方法在vision里面一個非常著名的應(yīng)用是用于tracking，相應(yīng)發(fā)展出來的方法論叫做particle?filtering。
另外一大類重要的采樣方法，叫Markov?Chain?Monte?Carlo(MCMC)。這個的想法是，設(shè)計一個馬爾科夫鏈，讓它的平衡分布恰好是p(x)，那么等它平衡時開始采。以前我們做隨機過程作業(yè)是已知一個markov?chain，求equilibrium?distribution，設(shè)計MCMC就是反過來了。最重要的MCMC方法莫過于Metropolis-Hastings?Algorithm和Gibbs?Sampling，前者常被用于設(shè)計在solution?space的隨機游走(Random?walk)，后者則是conditional?sampling的基礎(chǔ)方法。
可是Markov過程怎么轉(zhuǎn)移呢。最簡單的Random?Walk結(jié)合acceptance?rate之后理論上是對的。可是，讓sampler隨便亂走，猴年馬月才能把solution?space走一遍阿。于是，有人提出結(jié)合一個solution?space的局部信息來引導(dǎo)它往有用的方向走。一個重要的方法叫做Hybric?Monte?Carlo(HMC)，想法就是把它模擬成一個物理場，把要sample的分布視為波爾茲曼分布后獲得物理場的勢能，通過哈密頓動力學(xué)模型（其實就是牛頓力學(xué)的推廣）來驅(qū)動sampler。可是，如果問題更為復(fù)雜呢，比如整個solution?space有幾個井，sample掉到某一個井可能出不來了。為了解決這個問題，一種重要的方法叫Tempering，就是開始給分子充分加熱，讓它獲得足夠的動能能在各個井之間來回跳，然后逐步冷卻，從而能捕捉到多個勢井。
Monte?Carlo方法較早的時候主要用于統(tǒng)計物理，目前已經(jīng)廣泛應(yīng)用于計算機，生物，化學(xué)，地質(zhì)學(xué)，經(jīng)濟學(xué)，社會學(xué)等等的研究。這是目前所知道的用于求解復(fù)雜的真實模型的最有效的方法。它的核心，就是猜——你直接解不出來，只好猜了，呵呵。但是，怎樣才能猜得準(zhǔn)，則是大有學(xué)問——幾十年來各個領(lǐng)域關(guān)于Monte?Carlo研究的工作汗牛充棟，有很多進展，但是還有很長的路要走。
和這里很多留學(xué)生一樣，我一向潛心于自己的學(xué)習(xí)和研究?？墒亲罱覀兊氖澜绮⒉粚庫o，我認識的不只一個在美國的朋友受到了不太友好的挑釁——在不知不覺中，我們可能已經(jīng)身處反分裂和支持奧運的前線。我看到包括MIT?CSSA在內(nèi)的很多學(xué)生團體開始組織起來支持自己的祖國。我沒有具體幫上什么，但是，我對所有在用自己的行動捍衛(wèi)國家榮譽的同胞懷有最深的敬意。我也希望，我的努力，能讓外國的朋友明白中國人是值得尊敬的。
Postscript:
以下是林達華(Dahua Lin)博士的經(jīng)驗。很棒的一個人，想要了解更多的可以點擊下面這張圖片：
他的個人主頁：http://dahua.me/
