機器學習理論導引（簡體書）

機器學習領域著名學者周志華教授領銜的南京大學LAMDA團隊四位教授合著

系統梳理機器學習理論中的七大重要概念或理論工具，並給出若干分析實例

機器學習理論內容浩瀚廣博，旨在為機器學習理論研究的讀者提供入門導引

本書旨在為有志於機器學習理論學習和研究的讀者提供一個入門導引。在預備知識之後，全書各章分別聚焦於：可學性、（假設空間）複雜度、泛化界、穩定性、一致性、收斂率、遺憾界。除介紹基本概念外，還給出若干分析實例，如顯示如何將不同理論工具應用於支持向量機這種常見機器學習技術。

周志華教授
南京大學計算機系主任、人工智能學院院長、校學術委員會委員。歐洲科學院外籍院士。人工智能相關五大主流國際學會ACM、AAAI、AAAS、IEEE、IAPR均入選Fellow的首位華人學者，中國計算機學會、中國人工智能學會會士。曾獲IEEE計算機學會Edward J. McCluskey技術成就獎、CCF王選獎等。著有《機器學習》（清華大學出版社）等。

王魏
南京大學計算機系副教授。主要研究方向為機器學習理論，曾獲中國計算機學會優秀博士學位論文獎、江蘇省優秀博士學位論文獎、CCF青年人才發展計劃等榮譽。

高尉
南京大學人工智能學院副教授。主要研究方向為機器學習理論，曾獲中國計算機學會優秀博士學位論文獎、江蘇省優秀博士學位論文獎等榮譽。

張利軍
南京大學計算機系副教授、博士生導師。主要研究方向為大規模機器學習與優化，曾獲首屆達摩院青橙獎、中國科協青年人才托舉工程、CCF青年人才發展計劃等榮譽。

前言

機器學習近年來備受關注，對機器學習理論感興趣的人士也日漸增多。然而這方面的專門書籍頗少，中文讀物尤甚。

顧名思義，機器學習理論研究的是關於機器學習的理論基礎，主要內容是分析學習任務的困難本質，為學習算法提供理論保證，並根據分析結果指導算法設計。雖然這方面的內容對深入理解機器學習技術甚為重要，但由於內容艱深廣袤，既需對機器學習問題有恰當把握，又需相當的數學技巧，且不少內容來源流派頗為不同，不僅初學者感覺難以下手，浸淫多年的學者往往也難縱覽全貌。

國際上關於機器學習理論的書籍大致有兩類，一類從介紹機器學習具體技術的角度展開，重點在於告訴讀者如何從理論角度來理解這些技術，學習理論自身的內容則散見於不同機器學習技術的討論中。另一類則聚焦於某項具體的學習理論，其他理論內容則需另尋相關讀物。

本書試圖為有志於機器學習理論學習和研究的讀者提供一個入門導引。作者以為，對理論學習和研究來說，弄清楚基礎概念和工具尤為重要。因此，本書採取了與上述書籍不同的組織方式。作者梳理出機器學習理論這個“百寶箱”中的七個重要概念或理論工具，姑且稱之為“七種武器”，即：可學性、(假設空間)複雜度、泛化界、穩定性、一致性、收斂率、遺憾界。本書每章聚焦其一，除介紹基本概念外，還給出若干分析實例，如展示出怎樣應用不同的理論工具來分析支持向量機這種常見機器學習技術。讀者今後對具體機器學習問題或技術作分析時，可根據條件選擇適用的“武器”。需說明的是，“泛化界”與其他內容並列稍有勉強， 因為書中多種理論工具都可用於泛化界分析；不過，領頭作者作為武俠愛好者，實難拒絕致敬《七種武器》的誘惑, 況且泛化界本身還真有那麼點神似古龍先生未完成的傳說中“什麼都能往裡裝”的第七種武器“箱子”。

本書由四位作者合作完成。周志華規劃了全書內容結構並撰寫了第1-2章，王魏撰寫了第3-4章，高尉撰寫了第5-6章，張利軍撰寫了第7-8章，周志華修訂統一了全書風格。機器學習理論內容浩瀚廣博，本書雖僅為入門一瞥，成書過程卻頗不易。鑑於中文機器學習理論讀物之缺乏，周志華在2016年組織LAMDA研究所中專長學習理論的幾位教師一起籌備本書。2017年春季在LAMDA內部學習班第一次試講，大部分學生反映困難。調整內容後，2017年秋季在LAMDA內部第二次試講，仍有部分學生感覺困難。進一步調整內容後，2018年春季學期在南京大學開設了計算機學科研究生選修課“機器學習理論研究導引”。學期結束後抽樣調查顯示，約1/3學生感覺難度較大. 再次調整內容後，在2019年春季學期研究生選修課上又講授一輪，學生反饋情況大致符合預期。於是在2019年中裁定內容，又經半年修改完稿，再於庚子年初之抗疫禁足期間靜修定稿。

機械工業出版社華章分社溫莉芳和姚蕾二位老師十年前赴寧約稿，此後數次登門、經年常遇，敬業精神令作者感慨。陳朝暉老師友情協助封面設計，使本書蓬蓽生輝。完稿校勘時得到趙鵬、呂沈歡、譚志豪、張騰、王璐、吳錦輝等同學協助，在此一併致謝。

需強調的是，本書雖已盡量降低難度, 但由於機器學習理論學習本身的要求，本書讀者必須具備較為紮實的理工科高年級本科生的數學知識，至少應該有較好的線性代數、數學分析、概率統計、最優化方法的基礎。本書讀者還必須具備機器學習的基礎知識，至少應該系統性地學習過機器學習的專門性教科書。機器學習理論內容學之不易，且不像機器學習技術工具那樣可以立即付諸應用，學習過程難免有焦躁感，自學尤易陷入困局，讀者務須有充分的心理準備。但是深入學習下來，不僅有助於理解機器學習的重要思想，更有助於感受和體會這個學科領域的美，一切努力最終都是值得的。

本書雖經多輪試講修改，但由於每輪均有較多內容調整，且作者學識淺陋，對博大精深之機器學習理論僅略知皮毛，因此書中錯謬之處在所難免，若蒙讀者諸君不吝指正，將不勝感激。

作者

2020年4月於南京

前言

主要符號表

第1章預備知識……………………………………………………………… 1

1.1 函數的性質………………………………………………………………… 1

1.2 重要不等式……………………………………………………………… 5

1.3 最優化基礎……………………………………………………………… 9

1.4 支持向量機……………………………………………………………… 13

1.5 理論的作用……………………………………………………………… 18

1.6 閱讀材料………………………………………………………………… 19

習題……………………………………………………………………………… 21

參考文獻………………………………………………………………………… 22

第2章可學性……………………………………………………………… 25

2.1 基本概念…………………………………………………………………25

2.2 PAC學習…………………………………………………………………… 26

2.3 分析實例………………………………………………………………… 30

2.4 閱讀材料………………………………………………………………… 35

習題……………………………………………………………………………… 36

參考文獻……………………………………………………………………… 37

第3章複雜度……………………………………………………………39

3.1 數據分佈無關………………………………………………………… 39

3.2 數據分佈相關………………………………………………………… 46

3.3 分析實例……………………………………………………………… 50

3.4 閱讀材料…………………………………………………………………56

習題..……………………………………………………………………………… 58

參考文獻……………………………………………………………………… 59

第4章泛化界……………………………………………………………… 61

4.1 泛化誤差上界………………………………………………………… 61

4.2 泛化誤差下界………………………………………………………… 71

4.3 分析實例………………………………………………………………… 78

4.4 閱讀材料………………………………………………………………… 83

習題……………………………………………………………………………… 84

參考文獻……………………………………………………………………… 86

第5章穩定性​​…………………………………………………………… 89

5.1 基本概念………………………………………………………………… 89

5.2 重要性質………………………………………………………………… 92

5.3 分析實例………………………………………………………………… 98

5.4 閱讀材料………………………………………………………………… 107

習題……………………………………………………………………………… 108

參考文獻……………………………………………………………………… 110

第6章一致性…………………………………………………………… 113

6.1 基本概念……………………………………………………………… 113

6.2 替代函數……………………………………………………………… 117

6.3 劃分機制……………………………………………………………… 122

6.4 分析實例……………………………………………………………… 125

6.5 閱讀材料……………………………………………………………… 132

習題………………………………………………………………………… 134

參考文獻………………………………………………………………… 135

第7章收斂率…………………………………………………………… 137

7.1 基本概念……………………………………………………………… 137

7.2 確定優化……………………………………………………………… 139

7.3 隨機優化……………………………………………………………… 143

7.4 分析實例………………………………………………………………155

7.5 閱讀材料……………………………………………………………… 157

習題……………………………………………………………………………… 159

參考文獻……………………………………………………………………… 161

第8章遺憾界…………………………………………………………… 163

8.1 基本概念……………………………………………………………… 163

8.2 完全信息在線學習……………………………………………… 165

8.3 賭博機在線學習………………………………………………….170

8.4 分析實例……………………………………………………………184

8.5 閱讀材料…………………………………………………………… 188

習題…………………………………………………………………………… 189

參考文獻…………………………………………………………………… 191

索引………………………………………………………………………… 193