機器學習的演算法和普通《演算法導論》裡的演算法有什麼本質上的異同?
點選上方“Jerry的演算法和NLP”,選擇“星標”公眾號
重磅乾貨,第一時間送達
有一個笑話是:需要多少個數學家來修燈泡?
答案是3個:
1. 第一個數學家證明修燈泡的辦法存在(existence),
2. 第二數學家證明修燈泡的方法只有一個(uniqueness),
3. 第三個數學家找到了一個演算法 (constructive algorithm)。
因此一種定義演算法的方法就是把 演算法當成是解決一個問題的一系列步驟 。演算法導論裡面的大部分內容是符合這個描述的,比方說排序,動態規劃,深搜廣搜,字串處理。機器學習裡面常用的迭代優化的方法本質也是解決問題的一系列步驟。所以從 本質上他們和演算法導論裡面的演算法是一樣的 。
當然了,個人認為機器學習會需要區分建模(modelling) 和學習(inference)這兩個不同的部分,題主說到的
...是用數學的方式試圖去描述和理解我們的世界...
指的其實是建模的部分,大概的意思就是我們試圖去建立一個模型來描述我們想要解決的問題。比方說我們可以用一個線性模型來描述兩個變數之間的關係,用一個HMM來對自然語言建模等。
處理問題的部分在機器學習裡面我們叫做學習,這個就對應到給予我們一些給予某個模型假設下面的一些資料,我們如何找出最好的這個模型的引數(MLE),或者引數的後驗分佈(MAP),或者推斷這個模型裡面我們沒有觀察到的隱變數(latent variables)。解決這些問題的方法包括了比方優化(凸非凸,組合或者連續),或者蒙特卡洛類演算法(e.g. Policy Gradients, Black-box variational inference)。
另外,機器學習裡面的演算法長得跟演算法導論裡面的演算法不太像還和我們想要解決的問題有關。機器學習裡面大部分想要解決的問題是NP困難的 (比方說最寬泛的優化問題)。這類問題一般會考慮用迭代求解的辦法嘗試尋找一個近似解。又或者有時候直接求解一個問題的複雜度會是O(n^3)但是迭代的話現實中會比理論的更快收斂(e.g. matrix inversion by conjugate gradients vs. by direct inversion),演算法導論裡面的問題比如排序或者字串處理並不在這一類NP困難的問題內, 因此迭代的方法可能不那麼常見。
此外,演算法長得不太一樣還可能是因為演算法研究的關注點出現了變化,引用Sanjeev Arora的notes裡面的一番話。
> Undergrad algorithms is largely about algorithms discovered before 1990; grad algorithms is a lot about algorithms discovered since 1990. What happened in 1990 that caused
> this change, you may ask? Nothing. I chose this arbitrarily; maybe I could have said 1985
> or 1995. There was no single event but just a gradual shift in the emphasis and goals of
> computer science as it became a more mature field.
> In the first few decades of computer science, algorithms research was driven by the goal
> of designing basic components of a computer: operating systems, compilers, networks, etc.
> Other motivations were classical problems in discrete mathematics, operations research,
> graph theory. The algorithmic ideas that came out of these quests form the core of undergraduate course: data structures, graph traversal, string matching, parsing, network
> flows, matchings, etc. Starting around 1990 theoretical computer science broadened its
> horizons and started looking at new problems: algorithms for bioinformatics, algorithms
> and mechanism design for e-commerce, algorithms to understand big data or big networks.
> This changed algorithms research and the change is ongoing. One big change is that it is
> often unclear what the algorithmic problem even is. Identifying it is part of the challenge.
> Thus good modeling is important. This in turn is shaped by understanding what is possible
> (given our understanding of computational complexity) and what is reasonable given the
> limitations of the type of inputs we are given
總結下來就是演算法導論裡面的演算法大致是為了解決傳統CS領域比方說作業系統編譯器裡面會遇到的問題,而更新的演算法研究(包含了很多我們今天看到的機器學習演算法)則嘗試解決一些我們甚至不知道怎麼建模的問題。這也是為什麼在經典演算法裡面我們經常看到輸入是一個數組,或者一個圖,但是機器學習的問題裡面我們會看到輸入是矩陣,因為矩陣這種描述方法可以讓我們不給我們的問題的結構加上太多的假設,同時我們可以通過研究這些抽象的輸入的性質然後給他們賦予現實意義(SVD as best rank-k approximations vs. used it for collaborative filtering in recommender systems).
《演算法導論》的演算法與機器學習演算法的關係,就好像做數學題和數學建模的關係。
演算法導論的演算法是面向有精確解的問題的求解方法。而機器學習演算法更多的是一種面向無精確解(或精確解很難得到)的問題的一種逼近策略。
舉個栗子:
做一道數學題(演算法題),用到了麥克勞林公式(動態規劃演算法),得到了一個精確的解(最優的方案)。其中,數學題中精確的解、演算法問題中的最優方案,都是唯一的、精確的。《演算法導論》中涉及的演算法大多都是上述這樣有精確解的問題的求解方法。
而當需要預測明天的天氣時,沒有演算法可以百分之百地保證預測一定是準確的,不到明天沒有人能精確知道明天的天氣。但我可以瞭解今天晚上的風向、溼度等等資訊,利用機器學習演算法來預測明天是否會下雨。最後的預測結果會or不會下雨都不是一個精確的結果,機器學習預測的結果只是一個估計的、近似的結果,但仍是有價值。另外,機器學習演算法的一大特點是,它沒有面向問題直接編寫程式,而是建立學習模型解決問題,也是其與演算法導論中的演算法的一大不同。
演算法導論只用到了:數學分析、簡單概率論、線性代數;基本是工科大一大二所學;
而能用到的,基本都是證明演算法的正確性;不需要證明的話,基本用不到數學工具,實際應用,照抄其中的程式碼,可以直接應用到工程中;如果不考慮證明,基本不存在什麼數學模型(圖論除外),而是人們對實際工程應用的巧妙構思和巧妙解法。
而想要參透 機器學習 ,除了上述基本數學工具,必須掌握:概率論、數理統計、最優化、凸分析、甚至是泛函分析等等高階數學工具,這些就已經基本涉及到應用數學專業大三、大四的數學水平了。這裡面基本都是數學模型,解法基於數學理論;如果不搞懂這裡面的數學,連基本的原理都無法搞清楚,更何談應用了。
寒假馬上就來了,博主搜到了這本機器學習實戰的電子書,願與君共同進步
後臺回覆 「 機器學習實戰 」 ,將這本書PDF帶回家過年把!
Jerry的演算法和NLP,一個注重技術領域的平臺!