第1章 引言 1
1.1 学习问题的标准描述 2
1.2 设计一个学习系统 3
1.2.1 选择训练经验 4
1.2.2 选择目标函数 5
1.2.3 选择目标函数的表示 6
1.2.4 选择函数逼近算法 7
1.2.5 最终设计 8
1.3 机器学习的一些观点和问题 10
1.4 如何阅读本书 11
1.5 小结和补充读物 12
习题 13
第2章 概念学习和一般到特殊序 15
2.1 简介 15
2.2 概念学习任务 15
2.2.1 术语定义 16
2.2.2 归纳学习假设 17
2.3 作为搜索的概念学习 17
2.4 FIND-S：寻找极大特殊假设 19
2.5 变型空间和候选消除算法 21
2.5.1 表示 21
2.5.2 列表后消除算法 21
2.5.3 变型空间的更简洁表示 22
2.5.4 候选消除学习算法 23
2.5.5 算法的举例 24
2.6 关于变型空间和候选消除的说明 26
2.6.1 候选消除算法是否会收敛到正确的假设 26
2.6.2 下一步需要什么样的训练样例 27
2.6.3 怎样使用不完全学习概念 27
2.7 归纳偏置 28
2.7.1 一个有偏的假设空间 28
2.7.2 无偏的学习器 29
2.7.3 无偏学习的无用性 30
2.8 小结和补充读物 32
习题 34
第3章 决策树学习 38
3.1 简介 38
3.2 决策树表示法 38
3.3 决策树学习的适用问题 39
3.4 基本的决策树学习算法 40
3.4.1 哪个属性是最佳的分类属性 40
3.4.2 举例 43
3.5 决策树学习中的假设空间搜索 45
3.6 决策树学习的归纳偏置 46
3.6.1 限定偏置和优选偏置 46
3.6.2 为什么短的假设优先 47
3.7 决策树学习的常见问题 48
3.7.1 避免过度拟合数据 49
3.7.2 合并连续值属性 53
3.7.3 属性选择的其他度量标准 53
3.7.4 处理缺少属性值的训练样例 54
3.7.5 处理不同代价的属性 55
3.8 小结和补充读物 56
习题 56
第4章 人工神经网络 60
4.1 简介 60
4.2 神经网络表示 61
4.3 适合神经网络学习的问题 62
4.4 感知器 63
4.4.1 感知器的表征能力 63
4.4.2 感知器训练法则 64
4.4.3 梯度下降和 delta 法则 65
4.4.4 小结 69
4.5 多层网络和反向传播算法 70
4.5.1 可微阈值单元 70
4.5.2 反向传播算法 71
4.5.3 反向传播法则的推导 74
4.6 反向传播算法的说明 76
4.6.1 收敛性和局部极小值 76
4.6.2 前馈网络的表征能力 77
4.6.3 假设空间搜索和归纳偏置 77
4.6.4 隐藏层表示 78
4.6.5 泛化、过度拟合和停止判据 79
4.7 举例：人脸识别 82
4.7.1 任务 82
4.7.2 设计要素 83
4.7.3 学习到的隐藏层表示 85
4.8 人工神经网络的高级课题 86
4.8.1 其他可选的误差函数 86
4.8.2 其他可选的误差最小化过程 87
4.8.3 递归网络 87
4.8.4 动态修改网络结构 88
4.9 小结和补充读物 89
习题 90
第5章 评估假设 95
5.1 动机 95
5.2 估计假设精度 95
5.2.1 样本错误率和真实错误率 96
5.2.2 离散值假设的置信区间 96
5.3 采样理论基础 98
5.3.1 错误率估计和二项比例估计 98
5.3.2 二项分布 99
5.3.3 均值和方差 100
5.3.4 估计量、偏差和方差 100
5.3.5 置信区间 101
5.3.6 双侧和单侧边界 103
5.4 推导置信区间的一般方法 104
5.5 两个假设错误率间的差异 105
5.6 学习算法比较 106
5.6.1 配对 t 测试 108
5.6.2 实际考虑 109
5.7 小结和补充读物 109
习题 110
第6章 贝叶斯学习 112
6.1 简介 112
6.2 贝叶斯法则 113
6.3 贝叶斯法则和概念学习 115
6.3.1 BRUTE-FORCE 贝叶斯概念学习 115
6.3.2 MAP 假设和一致学习器 117
6.4 极大似然和最小误差平方假设 118
6.5 用于预测概率的极大似然假设 121
6.6 最小描述长度准则 123
6.7 贝叶斯最优分类器 125
6.8 GIBBS 算法 126
6.9 朴素贝叶斯分类器 126
6.10 举例：学习分类文本 129
6.11 贝叶斯信念网 132
6.11.1 条件独立性 132
6.11.2 表示 133
6.11.3 推理 134
6.11.4 学习贝叶斯信念网 134
6.11.5 贝叶斯网的梯度上升训练 134
6.11.6 学习贝叶斯网的结构 136
6.12 EM 算法 136
6.12.1 估计 k 个高斯分布的均值 137
6.12.2 EM 算法的一般表述 138
6.12.3 k 均值算法的推导 139
6.13 小结和补充读物 140
习题 141
第7章 计算学习理论 144
7.1 简介 144
7.2 可能学习近似正确假设 145
7.2.1 问题框架 145
7.2.2 假设的错误率 146
7.2.3 PAC 可学习性 147
7.3 有限假设空间的样本复杂度 148
7.3.1 不可知学习和不一致假设 150
7.3.2 布尔文字的合取是 PAC 可学习的 151
7.3.3 其他概念类别的 PAC 可学习性 152
7.4 无限假设空间的样本复杂度 153
7.4.1 打散一个实例集合 153
7.4.2 Vapnik-Chervonenkis 维度 154
7.4.3 样本复杂度和 VC 维 155
7.4.4 神经网络的 VC 维 156
7.5 学习的出错界限模型 157
7.5.1 FIND-S 算法的出错界限 157
7.5.2 HALVING 算法的出错界限 158
7.5.3 最优出错界限 159
7.5.4 加权多数算法 159
7.6 小结和补充读物 161
习题 162
第8章 基于实例的学习 165
8.1 简介 165
8.2 k-近邻算法 166
8.2.1 距离加权最近邻算法 167
8.2.2 对 k-近邻算法的说明 168
8.2.3 术语注解 169
8.3 局部加权回归 169
8.3.1 局部加权线性回归 169
8.3.2 局部加权回归的说明 170
8.4 径向基函数 170
8.5 基于案例的推理 172
8.6 对消极学习和积极学习的评论 175
8.7 小结和补充读物 176
习题 177
第9章 遗传算法 179
9.1 动机 179
9.2 遗传算法 179
9.2.1 表示假设 181
9.2.2 遗传算子 182
9.2.3 适应度函数和假设选择 183
9.3 举例 184
9.4 假设空间搜索 186
9.5 遗传编程 188
9.5.1 程序表示 188
9.5.2 举例 189
9.5.3 遗传编程说明 190
9.6 进化和学习模型 191
9.6.1 拉马克进化 191
9.6.2 鲍德温效应 191
9.7 并行遗传算法 192
9.8 小结和补充读物 192
习题 193
第10章 学习规则集合 197
10.1 简介 197
10.2 序列覆盖算法 198
10.2.1 一般到特殊的柱状搜索 198
10.2.2 几种变型 200
10.3 学习规则集：小结 201
10.4 学习一阶规则 202
1O.4.1 一阶 Horn 子句 203
10.4.2 术语 203
10.5 学习一阶规则集：FOIL 204
10.5.1 FOIL 中的候选特化式的生成 206
10.5.2 引导 FOIL 的搜索 206
10.5.3 学习递归规则集 208
10.5.4 FOIL 小结 208
10.6 作为逆演绎的归纳 208
10.7 逆归纳 210
10.7.1 一阶归纳 212
10.7.2 逆归纳：一阶情况 212
10.7.3 逆归纳小结 214
10.7.4 泛化、θ-包容和涵蕴 214
10.7.5 PROGOL 215
10.8 小结和补充读物 215
习题 217
第11章 分析学习 220
11.1 简介 220
11.2 用完美的领域理论学习：PROLOG-EBG 223
11.3 对基于解释的学习的说明 228
11.3.1 发现新特征 229
11.3.2 演绎学习 230
11.3.3 基于解释的学习的归纳偏置 230
11.3.4 知识级的学习 231
11.4 搜索控制知识的基于解释的学习 232
11.5 小结和补充读物 234
习题 236
第12章 归纳和分析学习的结合 239
12.1 动机 239
12.2 学习的归纳-分析途径 241
12.2.1 学习问题 241
12.2.2 假设空间搜索 242
12.3 使用先验知识得到初始假设 242
12.3.1 KBANN 算法 243
12.3.2 举例 243
12.3.3 说明 245
12.4 使用先验知识改变搜索目标 247
12.4.1 TANGENTPROP 算法 248
12.4.2 举例 249
12.4.3 说明 250
12.4.4 EBNN 算法 251
12.4.5 说明 254
12.5 使用先验知识来扩展搜索算子 255
12.5.1 FOCL 算法 255
12.5.2 说明 257
12.6 研究现状 258
12.7 小结和补充读物 258
习题 259
第13章 增强学习 263
13.1 简介 263
13.2 学习任务 265
13.3 Q 学习 267
13.3.1 Q 函数 267
13.3.2 一个学习 Q 的算法 268
13.3.3 举例 269
13.3.4 收敛性 270
13.3.5 实验策略 271
13.3.6 更新序列 271
13.4 非确定性回报和动作 272
13.5 时间差分学习 274
13.6 从样例中泛化 275
13.7 与动态规划的联系 275
13.8 小结和补充读物 276
习题 277
附录 符号约定 281