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

 

本书介绍机器学习方法的原理及方法，同时引入了学习的计算复杂性、凸性和稳定性、PAC贝叶斯方法、压缩界等概念，以及*梯度下降、神经元网络和结构化输出等方法。作者既讲述重要的机器学习算法的工作原理和动机，还指出其固有的优势和缺点，是有兴趣了解机器学习理论和方法以及应用的学生和专业人员的良好教材或参考书。

目录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

前言Understanding Machine Learning:From Theory to Algorithms“机器学习”旨在从数据中自动识别有意义的模式。过去几十年中，机器学习成为一项常用工具，几乎所有需要从大量数据集合中提取信息的任务都在使用它。我们身边的许多技术都以机器学习为基础：搜索引擎学习在带给我们的搜索结果的同时，植入可以盈利的广告；屏蔽软件学习过滤垃圾邮件；用于保护信用卡业务的软件学习识别欺诈。数码相机学习人脸识别，智能电话上的个人智能助手学习识别语音命令。汽车配备了用机器学习算法搭建的交通事故预警系统。同时机器学习还被广泛应用于各个科学领域，例如生物信息学、医药以及天文学等。 这些应用领域的一个共同特点在于，与相对传统的计算机应用相比，所需识别的模式更复杂。在这些情景中，对于任务应该如何执行，人类程序员无法提供明确的、细节优化的具体指令。以智能生物为例，我们人类的许多技能都是通过从经验中学习而取得并逐步提高的（而非遵从别人给我们的具体指令）。机器学习工具关注的正是赋予程序“学习”和适应不同情况的能力。 本书的个目标是，提供一个准确而简明易懂的导论，介绍机器学习的基本概念：什么是学习？机器怎样学习？学*概念时，如何量化所需资源？学习始终都是可能的吗？我们如何知道学习过程是成功或失败？本书的第二个目标是，为机器学习提供几个关键的算法。我们提供的算法，一方面已经成功投入实际应用，另一方面广泛地考虑到不同的学习技术。此外，我们特别将注意力放到了大规模学习（即俗称的“大数据”）上，因为近几年来，世界越来越“数字化”，需要学习的数据总量也在急剧增加。所以在许多应用中，数据量是充足的，而计算时间是主要瓶颈。因此，学*一概念时，我们会明确量化数据量和计算时间这两个数值。 本书分为四部分。部分对于“学习”的基础性问题给出初步而准确的定义。我们会介绍Valiant提出的“概率近似正确（PAC）”可学习模型的通用形式，它将是对“何为学习”这一问题的个有力回答。我们还会介绍“经验风险小化（ERM）”“结构风险小化（SRM）”和“小描述长度（MDL）”这几个学习规则，展现“机器是如何学习的”。我们量化使用ERM、SRM和MDL规则学习时所需的数据总量，并用“没有免费的午餐”定理说明，什么情况下学习可能会失败。此外,我们还探讨了学习需要多少计算时间。本书第二部分介绍多种算法。对于一些算法，我们先说明其主要学习原则，再介绍该算法是如何依据其原则运作的。前两部分将重点放在PAC模型上，第三部分将范围扩展到更广、更丰富的学习模型。后，第四部分讨论前沿的理论。 我们尽量让本书能够自成一体，不过我们假设读者熟悉概率论、线性代数、数学分析和算法设计的基本概念。前三部分为计算机科学、工程学、数学和统计学研究生一年级学生设计，具有相关背景的本科生也可以使用。高级章节适用于想要对理论有更深入理解的研究者。 致谢Understanding Machine Learning:From Theory to Algorithms本书以“机器学习入门”课程为蓝本，这门课程由Shai ShalevShwartz和Shai BenDavid分别在希伯来大学和滑铁卢大学讲授。本书的初稿由Shai ShalevShwartz在2010至2013年间在希伯来大学所开课程的教案整理而成。感谢2010年的助教Ohad Shamir和2011至2013年的助教Alon Gonen的帮助，他们为课堂准备了一些教案以及许多课后练习。特别感谢Alon在全书编写过程中所做出的贡献，此外他还撰写了一册习题答案。 我们由衷地感谢Dana Rubinstein的辛勤工作。Dana从科学的角度校对了书稿，对原稿进行了编辑，将它从章节教案的形式转换成连贯流畅的文本。 特别感谢Amit Daniely，他仔细阅读了本书的高级部分，并撰写了多分类可学习性的章节。我们还要感谢耶路撒冷的一个阅读俱乐部的成员们，他们认真阅读了原稿的每一页，并提出了建设性的意见。他们是：Maya Alroy, Yossi Arjevani, Aharon Birnbaum, Alon Cohen, Alon Gonen, Roi Livni, Ofer Meshi, Dan Rosenbaum, Dana Rubinstein, Shahar Somin, Alon Vinnikov和Yoav Wald。还要感谢Gal Elidan, Amir Globerson, Nika Haghtalab, Shie Mannor, Amnon Shashua, Nati Srebro和Ruth Urner参与的有益讨论。