深入理解機器學習：從原理到算法

目錄Understanding Machine Learning:From Theory to Algorithms出版者的話譯者序前言致謝第1章引論111什么是學習112什么時候需要機器學習213學習的種類314與其他領域的關系415如何閱讀本書416符號6第一部分理論基礎第2章簡易入門1021一般模型——統(tǒng)計學習理論框架1022經驗風險最小化1123考慮歸納偏置的經驗風險最小化1224練習15第3章一般學習模型1731PAC學習理論1732更常見的學習模型18321放寬可實現假設——不可知PAC學習18322學習問題建模1933小結2134文獻評注2135練習21第4章學習過程的一致收斂性2441一致收斂是可學習的充分條件2442有限類是不可知PAC可學習的2543小結2644文獻評注2745練習27第5章偏差與復雜性權衡2851“沒有免費的午餐”定理2852誤差分解3153小結3154文獻評注3255練習32第6章VC維3361無限的類也可學習3362VC維概述3463實例35631閾值函數35632區(qū)間35633平行于軸的矩形35634有限類36635VC維與參數個數3664PAC學習的基本定理3665定理67的證明37651Sauer引理及生長函數37652有小的有效規(guī)模的類的一致收斂性3966小結4067文獻評注4168練習41第7章不一致可學習4471不一致可學習概述4472結構風險最小化4673最小描述長度和奧卡姆剃刀4874可學習的其他概念——一致收斂性5075探討不同的可學習概念5176小結5377文獻評注5378練習54第8章學習的運行時間5681機器學習的計算復雜度5682ERM規(guī)則的實現58821有限集58822軸對稱矩形59823布爾合取式59824學習三項析取范式6083高效學習，而不通過合適的ERM6084學習的難度*6185小結6286文獻評注6287練習62第二部分從理論到算法第9章線性預測6691半空間66911半空間類線性規(guī)劃67912半空間感知器68913半空間的VC維6992線性回歸70921最小平方70922多項式線性回歸7193邏輯斯諦回歸7294小結7395文獻評注7396練習73第10章boosting75101弱可學習75102AdaBoost78103基礎假設類的線性組合80104AdaBoost用于人臉識別82105小結83106文獻評注83107練習84第11章模型選擇與驗證85111用結構風險最小化進行模型選擇85112驗證法861121留出的樣本集861122模型選擇的驗證法871123模型選擇曲線881124k折交叉驗證881125訓練驗證測試拆分89113如果學習失敗了應該做什么89114小結92115練習92第12章凸學習問題93121凸性、利普希茨性和光滑性931211凸性931212利普希茨性961213光滑性97122凸學習問題概述981221凸學習問題的可學習性991222凸利普希茨/光滑有界學習問題100123替代損失函數101124小結102125文獻評注102126練習102第13章正則化和穩(wěn)定性104131正則損失最小化104132穩(wěn)定規(guī)則不會過擬合105133Tikhonov正則化作為穩(wěn)定劑1061331利普希茨損失1081332光滑和非負損失108134控制適合與穩(wěn)定性的權衡109135小結111136文獻評注111137練習111第14章隨機梯度下降114141梯度下降法114142次梯度1161421計算次梯度1171422利普希茨函數的次梯度1181423次梯度下降118143隨機梯度下降118144SGD的變型1201441增加一個投影步1201442變步長1211443其他平均技巧1211444強凸函數*121145用SGD進行學習1231451SGD求解風險極小化1231452SGD求解凸光滑學習問題的分析1241453SGD求解正則化損失極小化125146小結125147文獻評注125148練習126第15章支持向量機127151間隔與硬SVM1271511齊次情況1291512硬SVM的樣本復雜度129152軟SVM與范數正則化1301521軟SVM的樣本復雜度1311522間隔、基于范數的界與維度1311523斜坡損失*132153最優(yōu)化條件與“支持向量”*133154對偶*133155用隨機梯度下降法實現軟SVM134156小結135157文獻評注135158練習135第16章核方法136161特征空間映射136162核技巧1371621核作為表達先驗的一種形式1401622核函數的特征*141163軟SVM應用核方法141164小結142165文獻評注143166練習143第17章多分類、排序與復雜預測問題145171一對多和一對一145172線性多分類預測1471721如何構建Ψ1471722對損失敏感的分類1481723經驗風險最小化1491724泛化合頁損失1491725多分類SVM和SGD150173結構化輸出預測151174排序153175二分排序以及多變量性能測量157176小結160177文獻評注160178練習161第18章決策樹162181采樣復雜度162182決策樹算法1631821增益測量的實現方式1641822剪枝1651823實值特征基于閾值的拆分規(guī)則165183隨機森林165184小結166185文獻評注166186練習166第19章最近鄰167191k近鄰法167192分析16819211NN準則的泛化界1681922“維數災難”170193效率實施*171194小結171195文獻評注171196練習171第20章神經元網絡174201前饋神經網絡174202神經網絡學習175203神經網絡的表達力176204神經網絡樣本復雜度178205學習神經網絡的運行時179206SGD和反向傳播179207小結182208文獻評注183209練習183第三部分其他學習模型第21章在線學習186211可實現情況下的在線分類186212不可實現情況下的在線識別191213在線凸優(yōu)化195214在線感知器算法197215小結199216文獻評注199217練習199第22章聚類201221基于鏈接的聚類算法203222k均值算法和其他代價最小聚類203223譜聚類2062231圖割2062232圖拉普拉斯與松弛圖割算法2062233非歸一化的譜聚類207224信息瓶頸*208225聚類的進階觀點208226小結209227文獻評注210228練習210第23章維度約簡212231主成分分析2122311當dm時一種更加有效的求解方法2142312應用與說明214232隨機投影216233壓縮感知217234PCA還是壓縮感知223235小結223236文獻評注223237練習223第24章生成模型226241極大似然估計2262411連續(xù)隨機變量的極大似然估計2272412極大似然與經驗風險最小化2282413泛化分析228242樸素貝葉斯229243線性判別分析230244隱變量與EM算法2302441EM是交替最大化算法2322442混合高斯模型參數估計的EM算法233245貝葉斯推理233246小結235247文獻評注235248練習235第25章特征選擇與特征生成237251特征選擇2372511濾波器2382512貪婪選擇方法2392513稀疏誘導范數241252特征操作和歸一化242253特征學習244254小結246255文獻評注246256練習246第四部分高級理論第26章拉德馬赫復雜度250261拉德馬赫復雜度概述250262線性類的拉德馬赫復雜度255263SVM的泛化誤差界256264低1范數預測器的泛化誤差界258265文獻評注259第27章覆蓋數260271覆蓋260272通過鏈式反應從覆蓋到拉德馬赫復雜度261273文獻評注262第28章學習理論基本定理的證明263281不可知情況的上界263282不可知情況的下界2642821證明m(ε，δ)≥05log(1/(4δ))/ε22642822證明m(ε，1/8)≥8d/ε2265283可實現情況的上界267第29章多分類可學習性271291納塔拉詹維271292多分類基本定理271293計算納塔拉詹維2722931基于類的一對多2722932一般的多分類到二分類約簡2732933線性多分類預測器273294好的與壞的ERM274295文獻評注275296練習276第30章壓縮界277301壓縮界概述277302例子2783021平行于軸的矩形2783022半空間2793023可分多項式2793024間隔可分的情況279303文獻評注280第31章PAC貝葉斯281311PAC貝葉斯界281312文獻評注282313練習282附錄A技術性引理284附錄B測度集中度287附錄C線性代數294參考文獻297索引305