內容簡介
《支持嚮量機:理論、算法與拓展》以分類問題(模式識彆、判彆分析)和迴歸問題為背景,介紹支持嚮量機的基本理論、方法和應用。特彆強調對所討論的問題和處理方法的實質進行直觀的解釋和說明,因此具有很強的可讀性。為使具有一般高等數學知識的讀者能夠順利閱讀,書中首先介紹瞭優化的基礎知識。
《支持嚮量機:理論、算法與拓展》可作為理工類、管理學等專業的高年級本科生、研究生和教師的教材或教學參考書,也可供相關領域的科研人員和實際工作者閱讀參考。
內頁插圖
目錄
序言
符號錶
第1章 最優化基礎
1.1 歐式空間上的最優化問題
1.1.1 最優化問題實例
1.1.2 最優化問題及其解
1.1.3 最優化問題的幾何解釋
1.2 歐式空間上的凸規劃
1.2.1 凸集和凸函數
1.2.2 凸規劃問題及其基本性質
1.2.3 凸規劃的對偶理論
1.2.4 凸規劃的最優性條件
1.2.5 綫性規劃
1.3 Hilbert空間上的凸規劃
1.3.1 凸函數及Frechet導數
1.3.2 凸規劃問題
1.3.3 凸規劃的對偶理論
1.3.4 凸規劃的最優性條件
1.4 歐式空間上帶有廣義不等式約束的凸規劃
1.4.1 帶有廣義不等式約束的凸規劃
1.4.2 帶有廣義不等式約束的凸規劃的對偶理論
1.4.3 帶有廣義不等式約束的凸規劃的最優性條件
1.4.4 二階錐規劃
1.4.5 半定規劃
1.5 Hilbert空間上帶有廣義不等式約束的凸規劃
1.5.1 K-凸函數與Frechet導數
1.5.2 凸規劃問題
1.5.3 凸規劃的對偶理論
1.5.4 凸規劃的最優性條件
第2章 綫性分類機
2.1 分類問題的提齣
2.1.1 例子(心髒病診斷)
2.1.2 分類問題和分類機
2.2 綫性可分問題的支持嚮量分類機
2.2.1 最大間隔法_
2.2.2 綫性可分問題的支持嚮量分類機
2.2.3 支持嚮量
2.3 綫性支持嚮量分類機
2.3.1 最大間隔法
2.3.2 綫性支持嚮量分類機
第3章 綫性迴歸機
3.1 迴歸問題和綫性迴歸問題
3.2 硬ε帶超平麵
3.2.1 從綫性迴歸問題到硬乒帶超平麵
3.2.2 硬ε-帶超平麵與綫性分劃
3.2.3 構造硬ε帶超平麵的最優化問題
3.3 綫性硬ε-帶支持嚮量迴歸機
3.3.1 原始問題
3.3.2 對偶問題及其與原始問題解的關係
3.3.3 綫性硬ε-帶支持嚮量迴歸機
3.4 綫性ε-支持嚮量迴歸機
3.4.1 原始問題
3.4.2 對偶問題及其與原始問題解的關係
3.4.3 綫性ε-支持嚮量迴歸機
第4章 核與支持嚮量機
4.1 從綫性分劃到非綫性分劃
4.1.1 非綫性分劃的例子
4.1.2 基於非綫性分劃的分類算法
4.1.3 基於非綫性分劃的迴歸算法
4.2 核函數
4.2.1 核函數及其特徵
4.2.2 核函數的判定和常用的核函數
4.3 支持嚮量機及其性質
4.3.1 支持嚮量分類機
4.3.2 支持嚮量迴歸機
4.4 支持嚮量機中核函數的選取
4.4.1 已知訓練集時核函數的選取
4.4.2 核函數的直接構造
第5章 C-支持嚮量分類機的統計學基礎
5.1 分類問
5.1.1 概率分布
5.1.2 分類問題的統計學提法
5.2 經驗風險最小化原則
5.3 VC維
5.4 結構風險最小化原則
5.5 結構風險最小化原則的一個直接實現
5.5.1 原始問題
5.5.2 擬對偶問題及其與原始問題的關係
5.5.3 結構風險最小化分類機
5.6 C-支持嚮量分類機的統計學習理論基礎
5.6.1 C-支持嚮量分類機的迴顧
5.6.2 對偶問題與擬對偶問題的關係
5.6.3 C-綫性支持嚮量分類機的統計學習理論解釋
……
第6章模型選擇
第7章算法
第8章支持嚮量機的變形與拓廣
參考文獻
索引
前言/序言
支持嚮量機是藉助於優化方法解決數據挖掘中若乾問題的有力工具,它在一定程度上剋服瞭“維數災難”和“過學習”等傳統睏難,並在文本分類、生物信息、語音識彆、遙感圖像分析、故障識彆和預測、時間序列預測、信息安全等諸多領域有瞭成功的應用。
支持嚮量機不僅有著統計學習理論的堅實理論基礎,而且具有直觀的幾何解釋和完美的數學形式。雖然自20世紀90年代由Vapnik提齣以來一直處於飛速發展的階段,但是支持嚮量機的理論基礎和各種算法實現的基本框架已經形成。自2000年開始,國外已陸續有專著齣版。
2004年,作者在科學齣版社齣版瞭學術專著《數據挖掘中的新方法——支持嚮量機》,該書是國內一本專門對支持嚮量機進行全麵完整介紹和論述的著作,齣版後讀者反映良好,並被中國科學院研究生院、清華大學、中國農業大學等用作研究生教材,被評為2006年北京市精品教材。經過五年的繼續研究與教學實踐,我們決定對該書進行全麵改寫,增加新的研究成果,並更名為“支持嚮量機——理論、算法與拓展”。
本書特彆強調可讀性,強調直觀對理解問題實質的重要作用。在給齣係統嚴謹的論述之前,一般先用圖像等直觀手段引進各種概念、方法和結論,並特彆注意對它們的本質給予形象的解釋和說明。對於原始文獻中沒有提及直觀解釋的內容,我們也盡可能予以補充,例如,對求解多類分類問題的Crammer-Singer支持嚮量機,我們給齣瞭清晰的幾何解釋。與第一部著作相比,本書的邏輯係統更加清晰,對問題的闡述也更加簡明,
本書主要討論分類問題和迴歸問題,基於把迴歸問題轉化為分類問題的研究工作,全書以分類問題為主綫,形成瞭統一的格局。主要內容如下:第1章介紹優化基礎。該章著重於凸規劃的介紹,添加瞭引領優化方法應用研究的錐規劃(包括二階錐規劃和半定規劃),以及Hilbert空間中的凸規劃理論。這是以後章節以及進一步研究新的支持嚮量機的優化基礎。第2章和第3章則分彆對綫性分類問題和綫性迴歸問題直觀地導齣最基本的綫性支持嚮量機。第4章介紹核的基本概念,並在此基礎上介紹求解一般的分類問題和迴歸問題的支持嚮量機。第5章則從間隔法的統計學解釋入手,討論支持嚮量機的統計學習理論基礎。第6章介紹支持嚮量機實際應用中的模型選擇問題,第7章介紹實現支持內量機的幾個主流算法。第8章是前麵討論過的基本的支持嚮量機的變形與拓廣,包括求解多類分類問題、半監督問題、帶有擾動的問題和多示例問題的支持嚮量機。
本書包含瞭我們自己的研究工作,例如第5。6節,就是我們完善支持嚮量機的統計學習理論基礎的研究成果。我們相信,這是迄今為止對C-支持嚮量分類機的一種最確切、最直接、最簡明的統計學習理論解釋。此外,這裏還給齣瞭C-支持嚮量分類機中的參數C以全新的意義。又如第8章中給齣的利用順序迴歸的思想求解多類分類問題的支持嚮量機,通過構建二階錐規劃或者半定規劃模型求解半監督問題和帶有擾動的問題的支持嚮量機,以及處理多示例問題的支持嚮量機等內容。
本書所設定的讀者範圍較廣,既包括初涉支持嚮量機的人員,也包括希望利用支持嚮量機解決實際問題的人士,還可作為對支持嚮量機進行深入研究的參考書,
本書得以齣版,我們要感謝國傢自然科學基金連續多年對我們研究工作的資助和國傢科學技術學術著作齣版基金的資助;感謝北京航空航天大學的王日爽教授、麯阜師範大學的王長鈺和王宜舉教授、大連理工大學的夏尊銓和張立衛教授、北京交通大學的修乃華教授、北京理工大學的劉寶光教授、空軍指揮學院的李意起教授、上海大學的白延琴教授、中國農業大學的經玲教授和甄苓副教授,感謝中國科學院馬誌明院士、章祥蓀研究員、石勇教授,中國微軟亞洲研究院李航研究員,香港中文大學張樹中教授對本書的關心和支持,感謝桂林電子科技大學的硃誌斌教授和中國人民大學的張春華博士給予的寶貴建議,同時感謝我們討論班的成員:楊誌霞博士、趙琨博士和王永翠、邵小健、秦如新、趙艷梅、高婷婷、邵元海、徐岩、李玉欣等同學,他們都對本書提供瞭幫助。
機器學習的基石:深度解析統計學習的經典範式 在這浩瀚的算法海洋中,總有一些經典的身影,它們不僅奠定瞭今日機器學習研究的基石,更以其優雅的數學理論和強大的實踐能力,持續影響著人工智能的演進。本書,正是這樣一部對機器學習領域中一類核心理論——統計學習理論——進行的深度挖掘與係統闡釋。它並非聚焦於某個具體模型的技術細節,而是旨在勾勒齣統計學習方法的宏觀圖景,展現其背後的數學邏輯、核心思想以及解決各類問題的普適性框架。 理論的深度:洞察學習的本質 統計學習理論,其核心在於為“學習”賦予一個嚴謹的數學定義。它認為,學習的過程本質上是從數據中尋找一個能夠最好地逼近真實世界規律的模型。那麼,何為“最好”?如何衡量“逼近”的程度?本書將帶領讀者深入探索這些根本性問題。 首先,我們將追溯統計學習的源頭,理解其與概率論、信息論、最優化等數學學科的緊密聯係。我們將詳細介紹PAC(Probably Approximately Correct)學習理論,這是一種旨在為學習算法提供理論保證的框架。在PAC框架下,一個成功的學習算法必須滿足兩個條件:其一,以很高的概率(Probably)輸齣一個近似(Approximately)真實函數(Correct)的模型。我們將剖析PAC理論中的關鍵概念,如樣本復雜度(需要多少數據纔能保證學習的成功)和算法復雜度(學習算法的效率),以及它們如何共同決定一個學習算法的性能上限。 接著,本書將聚焦於 VC(Vapnik-Chervonenkis)維的概念。VC維是衡量一個函數類(hypothesis class)“復雜度”的刻度尺。它直觀地反映瞭一個模型族“記憶”數據的能力,即能夠“打散”(shatter)多少個數據點。我們將詳細闡述VC維的定義,並通過具體的例子展示如何計算不同函數族的VC維。更重要的是,我們將揭示VC維與泛化誤差(generalization error)之間的深刻聯係。泛化誤差是衡量模型在未見過數據上錶現好壞的關鍵指標,而VC維則為控製泛化誤差提供瞭理論依據。本書將詳細推導VC維界,展示VC維如何作為數據樣本量和模型復雜度之間的權衡因子,指導我們選擇閤適的模型復雜度以避免過擬閤(overfitting)和欠擬閤(underfitting)的問題。 此外,我們還將探討Rademacher 復雜度,作為VC維的一種更普適且更精細的刻度尺。Rademacher 復雜度能夠更準確地衡量函數類在不同分布下的泛化能力,並在許多情況下提供比VC維更緊緻的界。我們將介紹Rademacher 隨機變量及其期望的意義,以及Rademacher 復雜度如何與經驗風險(empirical risk)和期望風險(expected risk)建立聯係,從而進一步深化對模型泛化能力的理解。 理論部分還將深入剖析經驗風險最小化(Empirical Risk Minimization, ERM)原理。ERM是統計學習中最基本也是最強大的學習範式之一,其核心思想是找到在訓練數據上錶現最好的模型。然而,僅僅最小化訓練誤差並不足以保證模型在未知數據上的良好錶現。本書將深入探討ERM的局限性,以及如何通過引入正則化(regularization)等技術來剋服這些局限,從而提升模型的泛化能力。我們將討論不同類型的正則化方法,例如L1和L2正則化,以及它們如何通過增加模型復雜度上的懲罰項來約束模型,從而實現更好的泛化。 算法的邏輯:構建有效的學習機器 在堅實的理論基礎上,本書將轉嚮構建實際的學習算法。這裏的“算法”並非特指某一個模型的訓練過程,而是更廣泛地指代用於從數據中學習模型參數或結構的一係列計算步驟和優化策略。 我們將詳細介紹損失函數(loss function)的設計原則。損失函數是衡量模型預測與真實值之間差異的數學工具,它是模型學習過程中優化的目標。本書將涵蓋各種經典的損失函數,如0-1損失(用於分類問題)、平方損失(用於迴歸問題)、絕對損失以及交叉熵損失等。我們將分析不同損失函數在數學性質和實際應用中的優劣,以及它們如何影響模型的學習過程和最終性能。 對於凸優化(convex optimization),本書將給予重點關注。許多統計學習算法的訓練過程都可以轉化為一個凸優化問題,其目標是最小化某個凸函數。我們將介紹凸函數、凸集、梯度下降法(gradient descent)、牛頓法(Newton's method)等基本的凸優化算法,並分析它們在解決大規模學習問題時的效率和收斂性。此外,我們還將探討次梯度法(subgradient method),用於處理非光滑凸函數,這在處理諸如L1正則化等情況下尤為重要。 除瞭通用的優化技術,本書還將介紹一些針對特定學習任務的算法設計思想。例如,在分類問題中,我們將探討如何設計能夠有效區分不同類彆的決策邊界。在迴歸問題中,我們將關注如何精確地預測連續數值。本書還將觸及集成學習(ensemble learning)的基本思想,即通過組閤多個弱學習器來構建一個強學習器,例如AdaBoost和Bagging等方法,並分析它們在提升模型魯棒性和泛化能力方麵的作用。 拓展的視野:從理論到實踐的橋梁 本書的價值不僅在於對基礎理論和核心算法的深入剖析,更在於其理論聯係實際、拓展應用邊界的視野。 在理論層麵,我們將探討核方法(kernel methods)的核心思想。核方法提供瞭一種在原始特徵空間中計算內積的便捷方式,從而能夠在更高維度的特徵空間中隱式地進行計算,極大地增強瞭模型的錶達能力。我們將詳細介紹核技巧的原理,以及核函數(如多項式核、高斯核、Sigmoid核)的選擇原則。 在算法層麵,本書將討論在綫學習(online learning)的模式。與傳統的批量學習不同,在綫學習算法能夠逐個處理數據樣本,並能夠不斷地更新模型,這在處理大規模、流式數據時具有顯著優勢。我們將探討在綫學習算法的設計思路,以及其在動態環境下的適應性。 此外,本書還將觸及半監督學習(semi-supervised learning)和無監督學習(unsupervised learning)的一些基礎概念。我們將探討如何在隻有少量標注數據的情況下,利用大量的未標注數據來提升學習效果,以及如何從無標注數據中發現隱藏的結構和模式。 本書的另一重要貢獻在於,它將以一種係統、嚴謹的視角來解讀機器學習領域中的各種算法和方法。讀者將能夠理解,許多看似不同的算法,其背後可能共享著相同的統計學習原理。這種深刻的理解,將有助於讀者在麵對新的問題和新的算法時,能夠更快地抓住核心,做齣明智的選擇,並能夠根據具體需求對現有算法進行改進和創新。 總而言之,本書旨在為讀者構建一個關於機器學習的理論認知框架。它強調的是“為什麼”和“怎麼做”背後的根本原因,而非僅僅停留在“是什麼”的錶麵描述。通過對統計學習理論的深度解析,以及對核心算法的邏輯梳理,本書將賦予讀者一種洞察機器學習本質的能力,為他們在數據科學、模式識彆、人工智能等領域的進一步探索打下堅實的基礎。這本書將成為任何渴望真正理解機器學習,而非僅僅掌握皮毛的讀者的必備參考。