南大周志華、俞揚、錢超最新力作:演化學習:理論與演算法進展一書導讀
很多研究者已經利用演化演算法(Evolutionary Algorithm, EA) 來解決機器學習中的複雜最優化問題。例如,EA 可以用來優化神經網路,包括訓練連接權重、結構優化和超參數優化。這種演化的人工神經網路模型能取得非常好的性能,甚至能媲美手動設計的模型。儘管演化學習已經取得了很多成功,但也很難得到機器學習社區的廣泛認同,其中一個重要的原因是 一直以來演化學習缺少堅實的理論基礎,演化計算的研究者過於關注啟發式的策略設計演算法,缺乏對演化計算理論的關注。南大周志華,俞揚,錢超深耕演化計算理論近二十年,近期準備出版演化學習:理論與演算法進展一書將為演化學習提供理論框架支撐。本文嘗試為讀者解讀這一最新進展,希望能引起機器學習和演化計算領域的研究者更多的關注。
1 簡介之演化計算理論與機器學習的前世今生
2001年周志華教授與其合作者提出了selective ensemble approach,其主要思想是通過從一批訓練好的神經網路中選擇一個子集進行結合,泛化性能甚至優於結合所有神經網路。這項研究工作採用了遺傳演算法,是最為常見的一種演化演算法(Evolutionary Algorithm, EA)
周志華認為演化演算法作為一種強大的優化方法,演化演算法可能對許多機器學習任務都有用。那個時候,演化計算基本上都是純啟發式的,而機器學習社區更加青睞於傳統的數學優化方法,例如梯度法等等理論味道相對濃一點的優化方法,對演化演算法在機器學習方面的應用並沒有被廣泛接受。演化演算法在一些非凸優化問題,經典的組合優化問題上取得了不錯的效果,然而一直以來因為過於依賴啟發式的策略設計演算法並且包含複雜的隨機行為,使得很難對其進行理論分析,因而目前還缺乏嚴格的理論基礎,尤其是當演化演算法作為優化演算法應用時的性能缺乏理論保障。理論基礎的缺乏一方面阻礙了演化演算法的進一步發展,另一方面也阻礙了演化演算法在對計算性能有嚴格要求的問題上的應用。
周志華教授相信演化演算法在應用中神祕成功的背後必定有其理論解釋。在這樣一個想法的驅使之下,周志華教授的學生 俞揚博士以 演化計算的理論研究為博士研究課題,錢超博士也相繼投入該領域的研究。這一研究歷程經歷了十餘年之久。在開始研究演化演算法時,就面臨著一個非常尷尬的兩邊不討好的境地,在演化計算領域,理論研究過於滯後,根本無法對實際的演算法有指導意義,因此基本少有人關注演化計算的理論進展,而在人工智慧領域,更是艱難,當時演化計算已經是在頂級會議上冷下去的話題。
經過周志華等研究者的共同努力,目前演化學習已經不再是完全缺乏理論支撐的玄學,其關鍵部分上已經有了理論結果,並且對演算法設計能夠給出一定的指導,使得演化學習成為一個有理論基礎的研究領域。這本書大部分內容都是三位作者在過去近二十年裏取得的研究成果。
本書包含四部分內容:
第一部分介紹了演化學習,機器學習,多目標優化和一些基礎預備知識。
第二部分給出了關於演化學習最重要的兩個性質:時間複雜度和近似能力的理論分析方法。這一部分給出的方法是演化學習理論分析的通用性基礎工具。
第三部分給出了關於演化學習的關鍵技術環節的理論分析,包括演化演算法的運算元、表徵、評估和種羣等。
第四部分以選擇性集成等機器學習任務為例,展示瞭如何分析和設計有理論支撐的演化學習演算法。
2 分章節概覽
2.1 對應書的 part 2 Analysis Methodology
談到優化演算法有兩個最基本的命題:1演算法複雜度,2演算法能否收斂到最優(很多時候無法收斂到最優,則退而求其次分析與最優的距離)。這兩個命題在傳統的數學優化領域和機器學習領域的理論分析非常多。演化計算的理論核心問題也是上面這兩個點,我們想知道加入交叉運算元,變異運算元或者各種改進的策略對演算法到底有什麼影響,是否能夠使得演算法變好。演化計算中大量的參數到底代表著什麼意義,如何科學地選取這些參數。演化計算一般求到的是近似最優解,那麼這個近似到底有多麼近?實際上面的問題到目前為止也沒有一個非常完美的答案。
在過去的二十年間,在運行效率方面,演化計算的核心理論是平均演算法複雜度。舉例來說pseudu-Boolean linear problems 被廣泛的應用來分析演化計算的效率和演算法參數該如何給定。有趣的是,我們常常會得到相反的結論,例如在一些問題中加入 recombination operators 可以提升演算法的效率,但在另外一些問題上加入recombination operators 則沒有明顯的效果。又例如在一些問題中採用比較大的種羣規模會比較有效,而在另外一些問題中大的種羣規模並沒有顯著的作用。這是因為各式各樣不同類型的優化問題具有非常複雜和非常不同的特性。當演化計算面對各式各樣不同類型的優化問題的時候,我們需要一個相對一般的工具或者理論幫助和指導我們來設計更好的演化計算方法,而不是僅僅是完全盲目的從零開始去試湊。
本章的核心點是建立了首次達到時間(first hitting time)和收斂率(Convergence rate)之間的關係。並且依據這個橋樑關係提出了一種基於收斂率的演化演算法複雜度分析方法,並對多種演化演算法在困難問題上的複雜度下界進行了分析。如下圖所示是首次達到時間 和收斂率之間關係