Thursday, April 22, 2010

如何找研究題目(四):使用有效的工具,尋找適合的問題 - Calculus of Variations


如何找研究題目?
                                                         
(How to come up with new research ideas?) 

Jia-Bin Huang 

jbhuang0604@gmail.com

                                                                                          
Latest update: April 12nd, 2010


If the only tool you have is a hammer, you tend to see every problem as a nail. - Abraham Maslow


四、使用有效的工具,尋找適合的問題  neXt = T(X), T: X->Y

  這類找新問題的方法基本上就是先熟悉一種工具的使用方式,然後尋找適當的問題來解決。對這個工具特性和效能的熟悉程度以及對於問題癥結點的處理恰當與否是運用這類方法的成功關鍵。每個年代往往都有各自主流的方法來解決各領域的問題,了解這些主流方法的原理和運用方式,對於處理自己手邊的問題有相當大的幫助。使用這類找問題的方法時,有個缺點是容易將手上每個問題都用相同的方式來解決,而忽略了問題的核心本質。因此,當你/妳想要應用某種方法時來解決問題時,必須先對於該問題有深刻的理解。
  在這個章節我介紹幾個在電腦視覺、機器學習、訊號處理領域中重要的方法,還有其應用的方向,了解這些領域除了對於理解前人的作品時有很大的幫助,也可以使自己在適當的時機引入正確的工具來解決問題。由於這些領域內容非常豐富,每一個主題都可以各自寫成一本教科書,所以在這裡我只介紹概念並指出相關的參考文獻。
  接下來依序介紹七個重要且廣泛被應用的方法,了解這些方法並不需要太艱深的數學,大一學的微積分、線性代數、機率與統計等基礎科目便非常足夠了
1.    Calculus of variations
2.    Dimensionality reduction
3.    Spectral clustering
4.    Graphical model
5.    Structured prediction
6.    Bilateral Filtering, Adaptive Smoothing, and the Nonlinear Diffusion Equation
7.    Sparse representation





Calculus of Variations


1. Introduction
                                                                                                    
  大學一年級時所學的微積分(Ordinary Calculus)處理的是函數(Function),也就是實數的函數,而Calculus of Variations (or Variational Calculus)處理的則是泛函(Functional),也就是函數的函數。在微分中有個重要的問題:計算函數的極值,給定一個實數函數,我們往往希望知道是哪一個實數使得該函數產生極大值或極小值,在Calculus of Variations中我們關心的則是那一個函數使得該泛函產生極大值或極小值。換句話說,前者在找Stationary points而後者在找Stationary functions。微積分中函數的極值必定會發生在微分為零的地方,而使泛函產生極值的解(某個函數)必定會符合Euler-Lagrange equation (Chain ruleIntegration by part等技巧和fundamental lemma in the calculus of variations可以推導得知 [1-2])
        Calculus of Variations中最簡單的問題是找到空間中兩點的最短路徑,如果沒有任何限制的話,不需要百萬小學堂裡的小學生也知道直線最短,但是若限制該路徑(i.e. 函數)在某個表面時,答案就沒有這麼簡單明顯了,比如說計算台灣到洛杉磯的最短距離(路徑被限制在地球表面上)或是台中到花蓮 (路徑被限制在中央山脈的表面上),這種在曲面上的直線即是所謂的Geodesic,在黎曼幾何 (Riemannian geometry中來表示黎曼流形(Riemannian manifold)上點與點之間的路徑,這觀念在愛因斯坦的廣義相對論 (General Relativity中尤其重要,geodesic (general relativity) 表示粒子在受重力影響而彎曲的時空中的運動路徑
  類似的觀念在物理(e.g., 光學及力學)也有很廣泛的應用,光學中即是Fermat's principle (i.e., principle of least time):兩點之間光走的路徑的長度必定是stationary( either minimal, maximal or a saddle point),此定理可以用來描述光線於不同介質中的折射反射性質(e.g., Snell's law)。在光學之後,力學部分也出現了principle of least action,中心思想是自然對所有的動作都是節儉的(Nature is thrifty in all its actions),此定理的發展影響之後 LagrangianHamiltonian 對古典物理(classical mechanics)的重新詮釋。
  


[3] MIT OpenCourseWare Mathematical Methods for Engineers II Lecture 23 Calculus of Variations

2. Application

  在九零年代SVDSpectral方法大行其道,或是在兩千年時的Boosting熱潮出現以前,Variational Calculus理論是最廣泛被使用的工具,主要是在電腦視覺中往往可以將要處理的問題轉換成泛函的形式,之後便可應用Calculus of Variations來處理這些泛函的極值(e.g., energy minimization),從Optical Flow [1]Shape-from-shading [2]Edge Detection [3-4]Active contours model [5-6]Image segmentation和使用Total VariationRegularizationImage Restoration [8-11]都可以看見運用Variational Calculus來解決各式各樣的問題。至今許多研究仍以Total Variation做為影像的Prior (Regularization) [12]



[7] Variational methods in image segmentation, Progress in Nonlinear Differential Equations and Their Applications 1995
[8] A variational method in image recovery, SIAM Journal on Numerical Analysis 1997
[9] Nonlinear total variation based noise removal algorithms, Physica D: Nonlinear Phenomena, 1992

No comments :

Post a Comment