我們所做的topic，一般有幾個階段：

Analysis: 分析問題，找到問題的關鍵

Modeling / Formulation:  對問題進行數學抽象，建立模型，或者formulate目標函數

Solving: 設計出求解的算法

Experiments: 實驗

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

求解的方法

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

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

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

   真正好的heuristics，它的好處肯定不是瞎懵出來，而是有內在原因的。對它們的原理的探索，不斷帶動理論方面的發展，甚至創造 了新的理論方向。說到這里，有人可能會argue，這是“理論家們在故弄玄虛混飯吃”。Hmm，這種說法我不能認同，但是，確實存在“把工程方法胡亂進行 理論化”的事實。什么才叫有價值的理論化，而不是故弄玄虛，確實值得思考，這里先不展開了。

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

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

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

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

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

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

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

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

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

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

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

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

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

和這里很多留學生一樣，我一向潛心于自己的學習和研究。可是最近，我們的世界并不寧靜，我認識的不只一個在美國的朋友受到了不太友好的挑釁——在不 知不覺中，我們可能已經身處反分裂和支持奧運的前線。我看到包括MIT CSSA在內的很多學生團體開始組織起來支持自己的祖國。我沒有具體幫上什么，但是，我對所有在用自己的行動捍衛國家榮譽的同胞懷有最深的敬意。我也希 望，我的努力，能讓外國的朋友明白中國人是值得尊敬的。