深入理解机器学习：从原理到算法

目录Understanding Machine Learning:From Theory to Algorithms出版者的话译者序前言致谢第1章引论111什么是学习112什么时候需要机器学习213学习的种类314与其他领域的关系415如何阅读本书416符号6第一部分理论基础第2章简易入门1021一般模型——统计学习理论框架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区间35633平行于轴的矩形35634有限类36635VC维与参数个数3664PAC学习的基本定理3665定理67的证明37651Sauer引理及生长函数37652有小的有效规模的类的一致收敛性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规则的实现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半空间类线性规划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章正则化和稳定性104131正则损失最小化104132稳定规则不会过拟合105133Tikhonov正则化作为稳定剂1061331利普希茨损失1081332光滑和非负损失108134控制适合与稳定性的权衡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最优化条件与“支持向量”*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实值特征基于阈值的拆分规则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在线凸优化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连续随机变量的极大似然估计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