译者序
前言
第1章 引言
1.1 应用与问题
1.2 定义与术语
1.3 交叉验证
1.4 学习情境
1.5 本书概览
第2章 PAC学习框架
2.1 PAC学习模型
2.2 对有限假设集的学习保证——一致的情况
2.3 对有限假设集的学习保证——不一致的情况
2.4 泛化性
2.4.1 确定性与随机性情境
2.4.2 贝叶斯误差与噪声
2.4.3 估计误差与近似误差
2.4.4 模型选择
2.5 文献评注
2.6 习题
第3章 Rademacher复杂度和VC-维
3.1 Rademacher复杂度
3.2 生长函数
3.3 VC-维
3.4 下界
3.5 文献评注
3.6 习题
第4章 支持向量机
4.1 线性分类
4.2 可分情况下的支持向量机
4.2.1 原始优化问题
4.2.2 支持向量
4.2.3 对偶优化问题
4.2.4 留一法
4.3 不可分情况下的支持向量机
4.3.1 原始优化问题
4.3.2 支持向量
4.3.3 对偶优化问题
4.4 间隔理论
4.5 文献评注
4.6 习题
第5章 核方法
5.1 引言
5.2 正定对称核
5.2.1 定义
5.2.2 再生核希尔伯特空间
5.2.3 性质
5.3 基于核的算法
5.3.1 具有PDS核的SVM
5.3.2 表示定理
5.3.3 学习保证
5.4 负定对称核
5.5 序列核
5.5.1 加权转换器
5.5.2 有理核
5.6 文献评注
5.7 习题
第6章 boosting
6.1 引言
6.2 AdaBoost算法
6.2.1 经验误差的界
6.2.2 与坐标下降的关系
6.2.3 与逻辑回归的关系
6.2.4 实践中的标准使用方式
6.3 理论结果
6.3.1 基于VC-维的分析
6.3.2 基于间隔的分析
6.3.3 间隔最大化
6.3.4 博弈论解释
6.4 讨论
6.5 文献评注
6.6 习题
第7章 在线学习
7.1 引言
7.2 有专家建议的预测
7.2.1 错误界和折半算法
7.2.2 加权多数算法
7.2.3 随机加权多数算法
7.2.4 指数加权平均算法
7.3 线性分类
7.3.1 感知机算法
7.3.2 Winnow算法
7.4 在线到批处理的转换
7.5 与博弈论的联系
7.6 文献评注
7.7 习题
第8章 多分类
8.1 多分类问题
8.2 泛化界
8.3 直接型多分类算法
8.3.1 多分类SVM
8.3.2 多分类boosting算法
8.3.3 决策树
8.4 类别分解型多分类算法
8.4.1 一对多
8.4.2 一对一
8.4.3 纠错编码
8.5 结构化预测算法
8.6 文献评注
8.7 习题
第9章 排序
9.1 排序问题
9.2 泛化界
9.3 使用SVM进行排序
9.4 RankBoost
9.4.1 经验误差界
9.4.2 与坐标下降的关系
9.4.3 排序问题集成算法的间隔界
9.5 二部排序
9.5.1 二部排序中的boosting算法
9.5.2 ROC曲线下面积
9.6 基于偏好的情境
9.6.1 两阶段排序问题
9.6.2 确定性算法
9.6.3 随机性算法
9.6.4 关于其他损失函数的扩展
9.7 讨论
9.8 文献评注
9.9 习题
第10章 回归
10.1 回归问题
10.2 泛化界
10.2.1 有限假设集
10.2.2 Rademacher复杂度界
10.2.3 伪维度界
10.3 回归算法
10.3.1 线性回归
10.3.2 核岭回归
10.3.3 支持向量回归
10.3.4 Lasso
10.3.5 组范数回归算法
10.3.6 在线回归算法
10.4 文献评注
10.5 习题
第11章 算法稳定性
11.1 定义
11.2 基于稳定性的泛化保证
11.3 基于核的正则化算法的稳定性
11.3.1 应用于回归算法：SVR和KRR
11.3.2 应用于分类算法：SVM
11.3.3 讨论
11.4 文献评述
11.5 习题
第12章 降维
12.1 主成分分析
12.2 核主成分分析
12.3 KPCA和流形学习
12.3.1 等距映射
12.3.2 拉普拉斯特征映射
12.3.3 局部线性嵌入
12.4 Johnson-Lindenstrauss引理
12.5 文献评注
12.6 习题
第13章 学习自动机和语言
13.1 引言
13.2 有限自动机
13.3 高效精确学习
13.3.1 被动学习
13.3.2 通过查询学习
13.3.3 通过查询学习自动机
13.4 极限下的识别
13.5 文献评注
13.6 习题
第14章 强化学习
14.1 学习情境
14.2 马尔可夫决策过程模型
14.3 策略
14.3.1 定义
14.3.2 策略值
14.3.3 策略评估
14.3.4 最优策略
14.4 规划算法
14.4.1 值迭代
14.4.2 策略迭代
14.4.3 线性规划
14.5 学习算法
14.5.1 随机逼近
14.5.2 TD（0）算法
14.5.3 Q-学习算法
14.5.4 SARSA
14.5.5 TD（λ）算法
14.5.6 大状态空间
14.6 文献评注
结束语
附录A 线性代数回顾
附录B 凸优化
附录C 概率论回顾
附录D 集中不等式
附录E 符

本书从概率近似正确(PAC)理论出发探讨机器学习的基础理论与典型算法。包括PAC学习框架、VC-维、支持向量机、核方法、在线学习、多分类、排序、回归、降维、强化学习等丰富的内容。此外，附录部分简要回顾了与机器学习密切相关的概率论、凸优化、矩阵以及范数等必要的预备知识。
本书重在介绍典型算法的理论支撑并指出算法在实际应用中的关键点，注重理论细节与证明过程，可作为高等院校机器学习、统计学等课程的教材，或作为相关领域研究人员的参考读物。