南大周志華、俞揚、錢超最新力作:《演化學習:理論與算法進展》正式上線

梯度下降或最速下降法,是機器學習最為重要的模塊之一。尤其是在深度學習時代,梯度下降已成為不可或缺的組成部分。但同時,梯度下降也限制了機器學習推廣到更廣泛的一些任務中,例如不可微的目标函數。這一缺陷,卻正好能被本書的主題「演化學習」解決。

最近,南京大學周志華教授、俞揚教授、錢超博士出版了一本名為「演化學習:理論與算法進展」的專著。在這本書中,總結了作者在這個主題上近二十年的研究成果,并從理論到算法概述了它對目前機器學習研究的意義。

目前,該書已在 Springer 官網正式上線,且開放了本書第一章的訪問,為期一個月。

書籍地址:https://www.springer.com/cn/book/9789811359552

書籍簡介

本世紀初,本書第一作者周志華與其合作者開展了「選擇性集成」的研究,通過從一批訓練好的神經網絡中選擇一個子集進行結合,泛化性能甚至優于結合所有神經網絡。該工作中引入了一種名為遺傳算法的演化算法(Evolutionary Algorithm, EA)。

周志華認為,演化算法作為一種強大的非經典優化方法,可能對許多機器學習任務都有用。但那時候,演化算法基本上都還是純啟發式的,理論氛圍濃厚的機器學習社區并不青睐這一類方法。周志華相信演化算法在應用中神秘成功的背後必有理論解釋,并決定開始研究。周志華的學生俞揚、錢超也相繼投入該領域的研究,這一研究就是十幾二十年。

最開始研究演化算法時,作者們遇到了很多困難。正如俞揚所說:「從 2005 年碩士入學開始,抱着演化算法理論這個硬骨頭就開始啃。這個領域真是四處不讨好,讓我深刻體驗了什麼叫冷闆凳。即使是在演化計算領域裡,對于搞應用的來說,理論太滞後,沒有指導意義,甚至關注理論進展的人都很少。而放在整個人工智能領域裡,更是艱難,當時演化計算就已經是在頂級會議上冷下去的話題了。」

經過周志華等研究者的共同努力,目前演化學習已經不再是完全缺乏理論支撐的「玄學」,其關鍵成分上已經有了理論結果,并且對算法設計能夠給出一定的指導,使得演化學習成為一個有理論基礎的研究領域。總而言之,這本書大部分内容都是三位作者在過去近二十年裡取得的研究成果,值得一讀。

内容概要

機器學習之所以稱之為「學習」,很大程度在于模型會通過最優化方法逐漸「學習」一些新知識。但目前主流模型常常要求目标函數是連續、可微的,不然的話梯度下降方法難以有效。這是一個很強的要求,别說可微的目标函數,在一些機器學習任務中甚至都難以定義明确的目标函數。

這時就可以考慮使用無需明确給出目标函數形式的演化學習技術。而演化算法确實在很多應用中産生了令人驚豔的結果。不過由于演化算法的「啟發式氛圍」太過濃厚,很多結果都是經驗性的,缺乏理論支持。最近很多研究者都在努力解決這個問題,而這本書則介紹了這方面的一系列探索與研究工作。

本書包含四部分内容:

  • 第一部分介紹了演化學習和一些基礎知識,它能為讀者提供一些預備知識。
  • 第二部分給出了關于演化學習的兩個最重要性質——時間複雜度和近似能力——的理論分析方法。這一部分給出的方法是演化學習理論分析的通用性基礎工具。
  • 第三部分給出了關于演化學習的關鍵技術環節的理論分析,包括演化算法的算子、表征、評估和種群等。
  • 第四部分以選擇性集成等機器學習任務為例,展示了如何分析和設計有理論支撐的演化學習算法。

作者們希望第二部分的通用理論工具可以幫助到有興趣探索演化學習理論基礎的讀者;希望第三部分的理論結果可以加深讀者對演化學習過程行為的理解,并且提供一些關于算法設計的見解;此外,作者們還希望第四部分的算法可以有效地用于機器學習實際應用中。

作者簡介

本文作者主要有三位:

周志華,現任南京大學人工智能學院院長,南京大學計算機科學與技術系主任、南京大學計算機軟件新技術國家重點實驗室常務副主任、機器學習與數據挖掘研究所 (LAMDA) 所長,校學術委員會委員。周志華是 ACM、AAAI、AAAS、IEEE 和 IAPR Fellow,主要從事人工智能、機器學習、數據挖掘等領域的研究工作。

俞揚,博士,南京大學教授,博士生導師。主要研究領域為人工智能、機器學習、強化學習。2011 年 8 月加入南京大學計算機科學與技術系、機器學習與數據挖掘研究所(LAMDA)從事教學與科研工作。俞揚獲得了 4 項國際論文獎勵和 2 項國際算法競賽冠軍,入選 2018 年 IEEE Intelligent Systems 雜志評選的「國際人工智能 10 大新星」,獲 2018 亞太數據挖掘「青年成就獎」,受邀在 IJCAI’18 作關于強化學習的「青年亮點」報告。

錢超,南京大學,博士。主要研究方向為演化計算與機器學習。以第一作者在 AIJ、TEvC、ECJ、Algorithmica、NIPS、IJCAI、AAAI 等國際一流期刊和會議上發表二十餘篇論文。獲 ACM GECCO’11 最佳理論論文獎、IDEAL’16 最佳論文獎,擔任 IEEE 計算智能學會 Task Force on Theoretical Foundations of Bio-inspired Computation 主席,入選中國科協「青年人才托舉工程」。

什麼是演化學習

對于大部分讀者而言,機器學習和梯度下降已經是老朋友了,但演化學習卻相對陌生。我們可以将各種機器學習算法總結為三大主要模塊,即如下所示的模型表征、模型優化和模型評估。

原書圖 1.1:典型機器學習過程的三大組成模塊。

我們很容易理解,ML 需要支持向量機、神經網絡或決策樹等算法構建模型空間,然後在訓練數據上利用學習算法找更好的解決方案。當然,在找最優模型的過程中,模型評估會将模型的好壞直接反饋給學習算法,從而指導學習的持續進行。

那麼 EA 在機器學習中處于什麼位置呢?按照維基百科的描述:「演化算法啟發自生物的演化機制,模拟繁殖、突變、遺傳重組、自然選擇等演化進程,從而對最優化問題的候選解做演化計算。」所以,演化算法對應于上圖的學習算法,它是一種模拟自然演化的「學習過程」。

所以演化學習究竟是怎樣進行的,它會不會也有這樣一個整體框架?後面我們将介紹該書第一章描述的演化學習。

演化學習的主要流程

演化算法(EA)是一大類啟發式的随機優化算法,它受到了自然演化的很多啟發。一般 EA 會考慮兩個關鍵因素來模拟自然過程,即變異繁殖(variational reproduction)和擇優挑選(superior selection)。盡管演化算法有很多不同的實現,例如遺傳算法(GA)、遺傳規劃(GP)和進化策略(ES),但典型的 EA 主要能抽象為以下四個步驟:

1. 生成一組初始解(稱為種群/Population);

2. 基于現有的種群繁衍一些新的解(solution);

3. 移除種群中相對差的解;

4. 返回第二步并重複運行,直到遇到了終止标準。

這四步可以構成演化算法的主要流程:

原書圖 1.2:演化算法的一般結構。

演化算法實例

在使用 EA 解決最優化問題之前,我們需要決定如何表示解(solution)。例如,如果問題是從基準集中選擇一個子集,那麼一個解可以自然地表示為一個布爾值(0 或 1)向量。如下圖 1.3 所示,{v1, v2, . . . , v8} 的子集能自然地表示為長度為 8 的布爾值向量。其中第 i 個元素為 1 意味着選擇了 v_i,因此 {v1, v3, v4, v5} 能表示為 (1, 0, 1, 1, 1, 0, 0, 0)。

原書圖 1.3:表示解的一個案例。

基于解的表征方法,EA 通過圖 1.2 所示的循環就開始了演化。在循環演化過程中,EA 會保留解的整個種群,并通過疊代繁衍新的後代解而不停地更新種群。突變與重組(或稱為交叉)是繁衍的兩種常見操作方法。突變(Mutation)會随機修改一個解以生成新的解。

如下,圖 1.4 展示了布爾值向量所産生的單個元素突變,即随機選擇一個元素,并将其修改為另一個布爾值。

原書圖 1.4:布爾值向量解上的單比特變異。算法首先會随機選擇 Parent 解上的一個位置,然後改變該位置的布爾值,并生成後代解。

重組會混合 2 個或多個解以生成新的解。下圖 1.5 展示了兩個布爾值向量所完成的單點重組,即随機選擇一個位置,然後交換該位置後面的值。

原書圖 1.5:兩個布爾值向量上的單點重組。算法随機選擇兩個 Parent 解的某個相同位置,并交換該位置後面的值而生成兩個後代解。

新生成後代解之後,我們需要使用适應度函數(fitness function)度量它們的好壞。如果我們使用某些挑選機制,從老種群的解、新生成的後代解中擇優挑選,那麼就能構建新的種群。當滿足停止标準時,演化周期就結束了。目前有一些停止準則,例如是否有滿足預定義質量的解、計算資源的預算上限(例如運行時間)、或解不會随着疊代的進行繼續提升。

從整個疊代過程中可以看到,EA 在求解最優化問題時,它隻需要以某種方法表示解,并能夠對解的好壞進行評估,從而可以搜索更好的解。因此,EA 在沒有梯度信息、甚至在沒有明确目标函數時都能使用,它隻需要存在某種方法能通過實驗或模拟評估解的好壞就行。因此,EA 被視為一種通用的最優化算法,我們甚至能以「黑盒」的方式解決某個最優化問題。

由于通用屬性,很多研究者已經利用 EA 來解決機器學習中的複雜最優化問題。例如,EA 可以用來最優化神經網絡,包括連接權重、架構和學習規則。這種演化的人工神經網絡模型能實現非常好的性能,甚至能媲美手動設計的模型。然而,盡管演化學習已經取得了很多成功,但它缺少堅實的理論基礎,也很難受到機器學習社區的廣泛認同,本書介紹了作者們為此作出的努力。

附全書目錄

更新于:2019年09月03日

  • 智領江蘇(資訊)

  • 加入JSAI學會