深入理解機(jī)器學(xué)習(xí)：從原理到算法

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