模式识别与机器学习 马春鹏 October 26,2014
模式识别与机器学习 马春鹏 October 26, 2014 1
目录 1绪论 9 1.1 例子：多项式曲线拟合 o 1.2概率论 16 1.2.1 概率密度 20 1.2.2 期望和协方差 21 1.2.3 贝叶斯概率······. 22 1.2.4 高斯分布 24 1.2.5 重新考察曲线拟合问题 。4 ···· 26 1.2.6 贝叶斯曲线拟合 28 1.3 模型选择。·······… 44 29 1.4 维度灾难 。。。。。。 30 1.5 决策论 33 1.5.1 最小化错误分类率 34 1.5.2 最小化期望损失 35 1.5.3 拒绝选项······ 35 1.5.4 推断和决策 36 1.5.5 回归问题的损失函数 38 1.6 信息论 1.6.1 相对熵和互信息 44 1.7 练习 4 2概率分布 52 2.1 二元变量. 52 2.1.1Beta分布 54 2.2 多项式变量 56 2.2.1狄利克雷分布 8 2.3高斯分布.. 59 2.3.1 条件高斯分布 63 2.3.2 边缘高斯分布 65 2.3.3 高斯变量的贝叶斯定理 67 2.3.4 高斯分布的最大似然估计 。4 69 2.3.5 顺序估计 69 2.3.6 高斯分布的贝叶斯推断 71 2.3.7 学生分布 15 2.3.8 周期变量 7 2.3.9 混合高斯模型 81 2.4 指数族分布 83 2.4.1 最大似然与充分统计量 86 2.4.2 共轭先验 87 2.4.3 无信息先验 2.5非参数化方法 8 2.5.1 核密度估计 9 2.5.2 近邻方法 92 2.6练习 94 3回归的线性模型 101 3.1线性基函数模型 101 3.1.1最大似然与最小平方 。 102 3.1.2 最小平方的几何描述 444 105 3.1.3 顺序学习 105 2
⽬录 1 绪论 9 1.1 例⼦：多项式曲线拟合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2 概率论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.2.1 概率密度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.2.2 期望和协⽅差 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.2.3 贝叶斯概率 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.2.4 ⾼斯分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.2.5 重新考察曲线拟合问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.2.6 贝叶斯曲线拟合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.3 模型选择 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.4 维度灾难 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 1.5 决策论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.5.1 最⼩化错误分类率 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 1.5.2 最⼩化期望损失 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 1.5.3 拒绝选项 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 1.5.4 推断和决策 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 1.5.5 回归问题的损失函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 1.6 信息论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 1.6.1 相对熵和互信息 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 1.7 练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2 概率分布 52 2.1 ⼆元变量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.1.1 Beta分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.2 多项式变量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.2.1 狄利克雷分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.3 ⾼斯分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.3.1 条件⾼斯分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 2.3.2 边缘⾼斯分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 2.3.3 ⾼斯变量的贝叶斯定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 2.3.4 ⾼斯分布的最⼤似然估计 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 2.3.5 顺序估计 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 2.3.6 ⾼斯分布的贝叶斯推断 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 2.3.7 学⽣t分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 2.3.8 周期变量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 2.3.9 混合⾼斯模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 2.4 指数族分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 2.4.1 最⼤似然与充分统计量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 2.4.2 共轭先验 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 2.4.3 ⽆信息先验 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 2.5 ⾮参数化⽅法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 2.5.1 核密度估计 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 2.5.2 近邻⽅法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 2.6 练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 3 回归的线性模型 101 3.1 线性基函数模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 3.1.1 最⼤似然与最⼩平⽅ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 3.1.2 最⼩平⽅的⼏何描述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 3.1.3 顺序学习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 2
3.1.4 正则化最小平方 105 3.1.5 多个输出 106 3.2 偏置-方差分解 108 3.3 贝叶斯线性回归 111 3.3.1 参数分布 111 3.3.2 预测分布 113 3.3.3 等价核·· 116 3.4 贝叶斯模型比较 118 3.5 证据近似.··· 121 3.5.1 计算证据函数 121 3.5.2 最大化证据函数 123 3.5.3 参数的有效数量 124 3.6 固定基函数的局限性·· 126 3.7 练习 126 4分类的线性模型 130 4.1 判别函数。。····。·· 131 4.1.1 131 4.1.2 132 4.1.3 用于分类的最小平方方法 133 4.1.4 Fisher线性判别函数 ，。 135 4.1.5 与最小平方的关系 。。 。 137 4.1.6 多分类的Fisher判别函数 4 138 4.1.7 感知器算法 139 4.2概率生成式模型 141 4.2.1 连续输入 143 4.2.2 最大似然解 144 4.2.3 离散特征 146 4.2.4 指数族分布 146 4.3 概率判别式模型 147 4.3.1 固定基函数 147 4.3.2 logistic回归 148 4.3.3 迭代重加权最小平方 149 4.3.4 多类logistic回归 150 4.3.5 probit回归 151 4.3.6 标准链接函数 152 4.4拉普拉斯近似 154 4.4.1 模型比较和BIC 155 4.5贝叶斯logistic回归 4 156 4.5.1 拉普拉斯近似 156 4.5.2 预测分布 157 4.6练习 158 5神经网络 161 5.1前馈神经网络 。，， 161 5.1.1 权空间对称性 4 165 5.2网络训练...·.... 165 5.2.1 参数最优化 168 5.2.2 局部二次近似 169 5.2.3 使用梯度信息 170 5.2.4 梯度下降最优化 170 5.3误差反向传播..·... 171 3
3.1.4 正则化最⼩平⽅ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 3.1.5 多个输出 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 3.2 偏置-⽅差分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 3.3 贝叶斯线性回归 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 3.3.1 参数分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 3.3.2 预测分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 3.3.3 等价核 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 3.4 贝叶斯模型⽐较 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 3.5 证据近似 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 3.5.1 计算证据函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 3.5.2 最⼤化证据函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 3.5.3 参数的有效数量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 3.6 固定基函数的局限性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 3.7 练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 4 分类的线性模型 130 4.1 判别函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 4.1.1 ⼆分类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 4.1.2 多分类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 4.1.3 ⽤于分类的最⼩平⽅⽅法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 4.1.4 Fisher线性判别函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 4.1.5 与最⼩平⽅的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 4.1.6 多分类的Fisher判别函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 4.1.7 感知器算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 4.2 概率⽣成式模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 4.2.1 连续输⼊ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 4.2.2 最⼤似然解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 4.2.3 离散特征 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 4.2.4 指数族分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 4.3 概率判别式模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 4.3.1 固定基函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 4.3.2 logistic回归 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 4.3.3 迭代重加权最⼩平⽅ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 4.3.4 多类logistic回归 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 4.3.5 probit回归 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 4.3.6 标准链接函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 4.4 拉普拉斯近似 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 4.4.1 模型⽐较和BIC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 4.5 贝叶斯logistic回归 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 4.5.1 拉普拉斯近似 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 4.5.2 预测分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 4.6 练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 5 神经⽹络 161 5.1 前馈神经⽹络 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 5.1.1 权空间对称性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 5.2 ⽹络训练 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 5.2.1 参数最优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 5.2.2 局部⼆次近似 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 5.2.3 使⽤梯度信息 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 5.2.4 梯度下降最优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 5.3 误差反向传播 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 3
5.3.1 误差函数导数的计算 172 5.3.2 一个简单的例子 174 5.3.3 反向传播的效率 175 5.3.4 Jacobian矩阵 175 5.4 Hessian矩阵 177 5.4.1 对角近似 177 5.4.2 外积近似 178 5.4.3 Hessian矩阵的逆矩阵 178 5.4.4 有限差.. 179 5.4.5 Hessian矩阵的精确计算 179 5.4.6 Hessian矩阵的快速乘法 180 5.5神经网络的正则化 182 5.5.1 相容的高斯先验 。。 183 5.5.2 早停止········ 185 5.5.3 不变性.······ 186 5.5.4 切线传播 187 5.5.5 用变换后的数据训练 189 5.5.6 卷积神经网络 190 5.5.7 软权值共享 191 5.6 混合密度网络 。 193 5.7 贝叶斯神经网络 197 5.7.1 后验参数分布 198 5.7.2 超参数最优化 199 5.7.3 用于分类的贝叶斯神经网络 200 5.8练习 202 6核方法 206 61对偶表示....·. 206 6.2 构造核 207 6.3 径向基函数网络 211 6.3.1 Nadaraya-Watson模型 212 6.4 高斯过程.·· 4.4，4 214 6.4.1 重新考虑线性回归问题 4 214 6.4.2 用于回归的高斯过程 216 6.4.3 学习超参数.... 219 6.4.4 自动相关性确定 220 6.4.5 用于分类的高斯过程 221 6.4.6 拉普拉斯近似 222 6.4.7 与神经网络的联系·· 225 6.5 练习 225 7 稀疏核机 228 7.1 最大边缘分类器 228 7.1.1 重叠类分布··· 231 7.1.2 与logistic回归的关系 235 7.1.3 多类SVM 236 7.1.4 回归问题的SVM 237 7.1.5 计算学习理论 。。 240 7.2相关向量机 241 7.2.1 用于回归的RVM·· 241 7.2.2 稀疏性分析···· 244 7.2.3 RVM用于分类 247
5.3.1 误差函数导数的计算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 5.3.2 ⼀个简单的例⼦ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 5.3.3 反向传播的效率 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 5.3.4 Jacobian矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 5.4 Hessian矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 5.4.1 对⾓近似 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 5.4.2 外积近似 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 5.4.3 Hessian矩阵的逆矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 5.4.4 有限差 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 5.4.5 Hessian矩阵的精确计算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 5.4.6 Hessian矩阵的快速乘法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 5.5 神经⽹络的正则化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 5.5.1 相容的⾼斯先验 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 5.5.2 早停⽌ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 5.5.3 不变性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 5.5.4 切线传播 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 5.5.5 ⽤变换后的数据训练 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 5.5.6 卷积神经⽹络 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 5.5.7 软权值共享 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 5.6 混合密度⽹络 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 5.7 贝叶斯神经⽹络 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 5.7.1 后验参数分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 5.7.2 超参数最优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 5.7.3 ⽤于分类的贝叶斯神经⽹络 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 5.8 练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 6 核⽅法 206 6.1 对偶表⽰ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 6.2 构造核 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 6.3 径向基函数⽹络 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 6.3.1 Nadaraya-Watson模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 6.4 ⾼斯过程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 6.4.1 重新考虑线性回归问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 6.4.2 ⽤于回归的⾼斯过程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 6.4.3 学习超参数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 6.4.4 ⾃动相关性确定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 6.4.5 ⽤于分类的⾼斯过程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 6.4.6 拉普拉斯近似 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 6.4.7 与神经⽹络的联系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 6.5 练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 7 稀疏核机 228 7.1 最⼤边缘分类器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 7.1.1 重叠类分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 7.1.2 与logistic回归的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 7.1.3 多类SVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 7.1.4 回归问题的SVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 7.1.5 计算学习理论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 7.2 相关向量机 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 7.2.1 ⽤于回归的RVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 7.2.2 稀疏性分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 7.2.3 RVM⽤于分类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 4
7.3练习 249 8图模型 251 8.1贝叶斯网络 251 81.1例子：多项式回归 253 8.1.2 生成式模型 255 8.1.3 离散变量 255 8.1.4 线性高斯模型 257 8.2条件独立 259 8.2.1图的三个例子 260 8.2.2 d-划分·· 264 8.3马尔科夫随机场 266 8.3.1 条件独立性质 267 8.3.2 分解性质 268 8.3.3 例子：图像去噪 269 8.3.4 与有向图的关系 271 8.4 图模型中的推断 274 8.4.1 链推断。·。··· 274 8.4.2 277 8.4.3 因子图·· 277 8.4.4 加和-乘积算法 279 8.4.5 最大加和算法 4，。 285 8.4.6 一般图的精确推断· 289 8.4.7 循环置信传播 289 8.4.8 学习图结构····· 290 8.5 练习 290 9混合模型和EM 293 9.1 K均值聚类 293 9.1.1图像分割与压缩 296 92混合高斯..。。。.。。。·····..·..·..。······ 297 9.2.1最大似然 298 9.2.2 用于高斯混合模型的EM 300 9.3EM的另一种观点········ 303 9.3.1 重新考察高斯混合模型 304 9.3.2 与K均值的关系··· 305 9.3.3 伯努利分布的混合···· 306 9.3.4 贝叶斯线性回归的EM算法 309 9.4 一般形式的EM算法 310 9.5练习 313 10近似推断 316 10.1变分推断.··········· 316 10.1.1分解概率分布 317 10.1.2分解近似的性质 319 10.1.3例子：一元高斯分布 321 10.1.4 模型比较 324 10.2例子：高斯的变分混合 324 10.2.1变分分布 325 10.2.2变分下界 329 10.2.3预测概率密度 330 10.2.4确定分量的数量 331
7.3 练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 8 图模型 251 8.1 贝叶斯⽹络 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 8.1.1 例⼦：多项式回归 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 8.1.2 ⽣成式模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 8.1.3 离散变量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 8.1.4 线性⾼斯模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 8.2 条件独⽴ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 8.2.1 图的三个例⼦ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260 8.2.2 d-划分 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264 8.3 马尔科夫随机场 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266 8.3.1 条件独⽴性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267 8.3.2 分解性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 8.3.3 例⼦：图像去噪 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 8.3.4 与有向图的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271 8.4 图模型中的推断 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 8.4.1 链推断 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 8.4.2 树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 8.4.3 因⼦图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 8.4.4 加和-乘积算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279 8.4.5 最⼤加和算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285 8.4.6 ⼀般图的精确推断 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289 8.4.7 循环置信传播 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289 8.4.8 学习图结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 8.5 练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 9 混合模型和EM 293 9.1 K均值聚类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 9.1.1 图像分割与压缩 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 9.2 混合⾼斯 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 9.2.1 最⼤似然 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298 9.2.2 ⽤于⾼斯混合模型的EM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300 9.3 EM的另⼀种观点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 9.3.1 重新考察⾼斯混合模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 9.3.2 与K均值的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 9.3.3 伯努利分布的混合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 9.3.4 贝叶斯线性回归的EM算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309 9.4 ⼀般形式的EM算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310 9.5 练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313 10 近似推断 316 10.1 变分推断 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 10.1.1 分解概率分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 10.1.2 分解近似的性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 10.1.3 例⼦：⼀元⾼斯分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 10.1.4 模型⽐较 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324 10.2 例⼦：⾼斯的变分混合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324 10.2.1 变分分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 10.2.2 变分下界 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 10.2.3 预测概率密度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330 10.2.4 确定分量的数量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331 5
10.2.5诱导分解 332 10.3变分线性回归· 332 10.3.1变分分布 333 10.3.2 预测分布 334 10.3.3下界 335 10.4指数族分布 335 10.4.1变分信息传递 337 10.5局部变分方法······ 337 10.6 变分logistic回归.· 341 10.6.1变分后验概率分布 341 10.6.2最优化变分参数 343 10.6.3超参数的推断 344 107期望传播。········ 346 10.7.1例子：聚类问题 350 10.7.2图的期望传播 352 10.8练习 355 11采样方法 358 111基本采样算法····· 359 11.1.1标准概率分布 359 11.1.2拒绝采样 361 11.1.3可调节的拒绝采样 4，。 362 11.1.4重要采样 363 11.1.5采样-重要性-重采样 365 11.1.6采样与EM算法 366 11.2马尔科夫链蒙特卡罗 367 11.2.1马尔科夫链.·. 368 11.2.2 Metropolis-Hastings算法 370 11.3吉布斯采样 370 11.4切片采样 373 11.5混合蒙特卡罗算法 374 11.5.1动态系统 374 11.5.2混合蒙特卡罗方法 376 11.6估计划分函数.· 378 11.7练习 379 12连续潜在变量 381 12.1主成分分析 381 12.1.1最大方差形式 382 12.1.2最小误差形式 383 12.1.3PCA的应用 385 12.1.4高维数据的PCA 388 12.2 概率PCA····· 388 12.2.1最大似然PCA 391 12.2.2 用于PCA的EM算法 393 12.2.3贝叶斯PCA 4 395 12.2.4因子分析 397 12.3核PCA········ 399 12.4非线性隐含变量模型 402 12.4.1独立成分分析 402 12.4.2自关联网络··· 403 12.4.3对非线性流形建模·· 405
10.2.5 诱导分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 10.3 变分线性回归 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 10.3.1 变分分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 10.3.2 预测分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334 10.3.3 下界 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 10.4 指数族分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 10.4.1 变分信息传递 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337 10.5 局部变分⽅法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337 10.6 变分logistic回归 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 10.6.1 变分后验概率分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 10.6.2 最优化变分参数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 10.6.3 超参数的推断 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344 10.7 期望传播 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 10.7.1 例⼦：聚类问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350 10.7.2 图的期望传播 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352 10.8 练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355 11 采样⽅法 358 11.1 基本采样算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359 11.1.1 标准概率分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359 11.1.2 拒绝采样 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361 11.1.3 可调节的拒绝采样 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362 11.1.4 重要采样 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363 11.1.5 采样-重要性-重采样 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365 11.1.6 采样与EM算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366 11.2 马尔科夫链蒙特卡罗 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367 11.2.1 马尔科夫链 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368 11.2.2 Metropolis-Hastings算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370 11.3 吉布斯采样 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370 11.4 切⽚采样 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373 11.5 混合蒙特卡罗算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374 11.5.1 动态系统 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374 11.5.2 混合蒙特卡罗⽅法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376 11.6 估计划分函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378 11.7 练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379 12 连续潜在变量 381 12.1 主成分分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381 12.1.1 最⼤⽅差形式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382 12.1.2 最⼩误差形式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383 12.1.3 PCA的应⽤ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385 12.1.4 ⾼维数据的PCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388 12.2 概率PCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388 12.2.1 最⼤似然PCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391 12.2.2 ⽤于PCA的EM算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393 12.2.3 贝叶斯PCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395 12.2.4 因⼦分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397 12.3 核PCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399 12.4 ⾮线性隐含变量模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402 12.4.1 独⽴成分分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402 12.4.2 ⾃关联⽹络 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403 12.4.3 对⾮线性流形建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405 6
12.5练习 407 13顺序数据 410 13.1马尔科夫模型·····。······ 410 13.2隐马尔科夫模型 413 13.2.1用于HMM的最大似然法 417 13.2.2前向后向算法 418 13.2.3用于HMM的加和-乘积算法 423 132.4缩放因子···························· 425 13.2.5维特比算法 426 13.2.6隐马尔科夫模型的扩展·. 427 13.3 线性动态系统····· 430 13.3.1LDS中的推断 432 13.3.2 ,LDS中的学习 434 13.3.3LDS的推广 436 13.3.4 粒子滤波 437 13.4练习 438 14组合模型 441 14.1贝叶斯模型平均 441 14.2委员会 442 14.3提升方法 443 14.3.1最小化指数误差 444 14.3.2提升方法的误差函数 446 14.4基于树的模型 4444.4.4 447 14.5条件混合模型 449 14.5.1线性回归模型的混合 449 14.6 logistic模型的混合 452 14.6.1 专家混合 453 14.7练习 。。 454 A附录A.数据集 456 A1手写数字 456 A.2石油流 456 A.3 老忠实间歇喷泉 458 A.4人工生成数据·· 459 B附录B.概率分布 460 B.1伯努利分布 460 B.2Beta分布 460 B.3 二项分布 461 B.4 狄利克雷分布 461 B.5 Gamma分布 。。 462 B.6 高斯分布 462 B.7 高斯-Gamma分布 463 B.8 高斯-Wishart分布 464 B9多项式分布 464 B.10正态分布.·· 464 B.11学生t分布 465 B.12均匀分布 465 B.13 Von Mises分布 465 B.14 Wishart分布 466 >
12.5 练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407 13 顺序数据 410 13.1 马尔科夫模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410 13.2 隐马尔科夫模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413 13.2.1 ⽤于HMM的最⼤似然法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417 13.2.2 前向后向算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418 13.2.3 ⽤于HMM的加和-乘积算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423 13.2.4 缩放因⼦ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425 13.2.5 维特⽐算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426 13.2.6 隐马尔科夫模型的扩展 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427 13.3 线性动态系统 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430 13.3.1 LDS中的推断 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432 13.3.2 LDS中的学习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434 13.3.3 LDS的推⼴ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436 13.3.4 粒⼦滤波 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437 13.4 练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438 14 组合模型 441 14.1 贝叶斯模型平均 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441 14.2 委员会 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442 14.3 提升⽅法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443 14.3.1 最⼩化指数误差 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444 14.3.2 提升⽅法的误差函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446 14.4 基于树的模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447 14.5 条件混合模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449 14.5.1 线性回归模型的混合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449 14.6 logistic模型的混合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452 14.6.1 专家混合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453 14.7 练习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454 A 附录A. 数据集 456 A.1 ⼿写数字 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456 A.2 ⽯油流 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456 A.3 ⽼忠实间歇喷泉 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458 A.4 ⼈⼯⽣成数据 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459 B 附录B. 概率分布 460 B.1 伯努利分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460 B.2 Beta分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460 B.3 ⼆项分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461 B.4 狄利克雷分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461 B.5 Gamma分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462 B.6 ⾼斯分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462 B.7 ⾼斯-Gamma分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463 B.8 ⾼斯-Wishart分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464 B.9 多项式分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464 B.10 正态分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464 B.11 学⽣t分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465 B.12 均匀分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465 B.13 Von Mises分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465 B.14 Wishart分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466 7
C附录C.矩阵的性质 467 C.1矩阵的基本性质 444 467 C2迹和行列式······· 467 C.3矩阵的导数 468 C4特征向量方程····· 469 D附录D.变分法 472 E附录E.拉格朗日乘数法 474
C 附录C. 矩阵的性质 467 C.1 矩阵的基本性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467 C.2 迹和⾏列式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467 C.3 矩阵的导数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468 C.4 特征向量⽅程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469 D 附录D. 变分法 472 E 附录E. 拉格朗⽇乘数法 474 8
1 绪论 寻找数据中模式的问题是一个基本的问题，有着很长的很成功的历史。例如，16世纪Tycho Brahe的大量的观测使得Johannes Kepler发现行星运行的经验性规律，这反过来给经典力学的发 展提供了跳板。类似地，原子光谱的规律的发现在20世纪初期对于量子力学的发展和证明有着 重要的作用。模式识别领域关注的是利用计算机算法自动发现数据中的规律，以及使用这些规 律采取将数据分类等行动。 考虑手写数字识别的例子，如图1.1所示。每个数字对应一个28×28像素的图像，因此可以 表示为一个由784个实数组成的向量x。目标是建立一个机器，能够以这样的向量x作为输入， 以数字0到9为输出。这不是一个简单的问题，因为手写体变化多端。这个问题可以使用人工编 写的规则解决，或者依据笔画的形状启发式地区分数字，但是实际中这样的方法导致了规则数 量的激增，以及不符合规则的例外等等，并且始终给出较差的结果。 使用机器学习的方法可以得到好得多的结果。这个方法中，一个由N个数字{x1,·,cN}组 成的大的集合被叫做训练集(training set),用来调节模型的参数。训练集中数字的类别实现已 知，通常是被独立考察、人工标注的。我们可以使用目标向量(target vector)t来表示数字的类 别，它代表对应数字的标签。使用向量来表示类别的合适的技术将在后面讨论。注意对于每个 数字图像x只有一个目标向量t。 运行机器学习算法的结果可以被表示为一个函数y(x),它以一个新的数字的图像x为输入， 产生向量y,与目标向量的形式相同。函数y(x)的精确形式在训练（女aining）)阶段被确定，这 个阶段也被称为学习(learning)阶段，以训练数据为基础。一旦模型被训练出来，它就能确定 新的数字的图像集合中图像的标签。这些新的数字的图像集合组成了测试集(test set)。正确 分类与训练集不同的新样本的能力叫做泛化(generalization)。在实际应用中，输入向量的变 化性是相当大的，以至于训练数据只所有可能的输入向量中相当小得一部分，所以泛化是模式 识别的一个中心问题。 对于大部分实际应用，原始输入向量通常被预处理(pre-processed),变换到新的变量空 间。人们期望在新的变量空间中模式识别问题可以更容易地被解决。例如，在数字识别的问题 中，数字的图像通常被转化缩放，使得每个数字能够被包含到一个固定大小的盒子中。这极大 地减少了每个数字类别的变化性，因为现在所有数字的位置和大小现在相同，这使得后续的 区分不同类别的模式识别算法变得更加容易。这个预处理阶段有时被叫做特征抽取(feature extraction)。注意新的测试集必须使用与训练集相同的方法进行预处理。 为了加快计算速度，也可能进行预处理。例如，如果目标是高清视频中得实时人脸检测，计 算机每秒钟必须处理大量的像素。将这些像素直接传递给一个复杂的模式识别算法在计算上是 不可行的。相反，目标是找到可以快速计算的有用的特征，这些特征还能够保存有用的判别信 息使得人脸和非人脸可以被区分开。这些特征之后被用作模式识别算法的输入。例如，一个矩 形小区域内图像灰度的平均值可以被快速计算(Viola and Jones,2014),并且一组这样的特征 被证明在快速人脸检测中很有效。由于这样的特征的数量小于像素的数量，因此这种预处理代 表了一种形式的维数降低。必须注意，由于在预处理阶段信息通常被遗弃，因此如果信息对于 问题的解决很重要的话，系统整体的精度会下降。 训练数据的样本包含输入向量以及对应的目标向量的应用叫做有监督学习(supervised learning)问题。数字识别就是这个问题的一个例子，它的目标是给每个输入向量分配到有限数 图1.1：来自美国邮政编码的手写数字的例子
1 绪论 寻找数据中模式的问题是⼀个基本的问题，有着很长的很成功的历史。例如，16世纪Tycho Brahe的⼤量的观测使得Johannes Kepler发现⾏星运⾏的经验性规律，这反过来给经典⼒学的发 展提供了跳板。类似地，原⼦光谱的规律的发现在20世纪初期对于量⼦⼒学的发展和证明有着 重要的作⽤。模式识别领域关注的是利⽤计算机算法⾃动发现数据中的规律，以及使⽤这些规 律采取将数据分类等⾏动。 考虑⼿写数字识别的例⼦，如图1.1所⽰。每个数字对应⼀个28 × 28像素的图像，因此可以 表⽰为⼀个由784个实数组成的向量x。⽬标是建⽴⼀个机器，能够以这样的向量x作为输⼊， 以数字0到9为输出。这不是⼀个简单的问题，因为⼿写体变化多端。这个问题可以使⽤⼈⼯编 写的规则解决，或者依据笔画的形状启发式地区分数字，但是实际中这样的⽅法导致了规则数 量的激增，以及不符合规则的例外等等，并且始终给出较差的结果。 使⽤机器学习的⽅法可以得到好得多的结果。这个⽅法中，⼀个由N个数字{x1, …, xN }组 成的⼤的集合被叫做训练集（training set），⽤来调节模型的参数。训练集中数字的类别实现已 知，通常是被独⽴考察、⼈⼯标注的。我们可以使⽤⽬标向量（target vector）t来表⽰数字的类 别，它代表对应数字的标签。使⽤向量来表⽰类别的合适的技术将在后⾯讨论。注意对于每个 数字图像x只有⼀个⽬标向量t。 运⾏机器学习算法的结果可以被表⽰为⼀个函数y(x)，它以⼀个新的数字的图像x为输⼊， 产⽣向量y，与⽬标向量的形式相同。函数y(x)的精确形式在训练（training）阶段被确定，这 个阶段也被称为学习（learning）阶段，以训练数据为基础。⼀旦模型被训练出来，它就能确定 新的数字的图像集合中图像的标签。这些新的数字的图像集合组成了测试集（test set）。正确 分类与训练集不同的新样本的能⼒叫做泛化（generalization）。在实际应⽤中，输⼊向量的变 化性是相当⼤的，以⾄于训练数据只所有可能的输⼊向量中相当⼩得⼀部分，所以泛化是模式 识别的⼀个中⼼问题。 对于⼤部分实际应⽤，原始输⼊向量通常被预处理（pre-processed），变换到新的变量空 间。⼈们期望在新的变量空间中模式识别问题可以更容易地被解决。例如，在数字识别的问题 中，数字的图像通常被转化缩放，使得每个数字能够被包含到⼀个固定⼤⼩的盒⼦中。这极⼤ 地减少了每个数字类别的变化性，因为现在所有数字的位置和⼤⼩现在相同，这使得后续的 区分不同类别的模式识别算法变得更加容易。这个预处理阶段有时被叫做特征抽取（feature extraction）。注意新的测试集必须使⽤与训练集相同的⽅法进⾏预处理。 为了加快计算速度，也可能进⾏预处理。例如，如果⽬标是⾼清视频中得实时⼈脸检测，计 算机每秒钟必须处理⼤量的像素。将这些像素直接传递给⼀个复杂的模式识别算法在计算上是 不可⾏的。相反，⽬标是找到可以快速计算的有⽤的特征，这些特征还能够保存有⽤的判别信 息使得⼈脸和⾮⼈脸可以被区分开。这些特征之后被⽤作模式识别算法的输⼊。例如，⼀个矩 形⼩区域内图像灰度的平均值可以被快速计算（Viola and Jones, 2014），并且⼀组这样的特征 被证明在快速⼈脸检测中很有效。由于这样的特征的数量⼩于像素的数量，因此这种预处理代 表了⼀种形式的维数降低。必须注意，由于在预处理阶段信息通常被遗弃，因此如果信息对于 问题的解决很重要的话，系统整体的精度会下降。 训练数据的样本包含输⼊向量以及对应的⽬标向量的应⽤叫做有监督学习（supervised learning）问题。数字识别就是这个问题的⼀个例⼦，它的⽬标是给每个输⼊向量分配到有限数 图 1.1: 来⾃美国邮政编码的⼿写数字的例⼦ 9
量离散标签中的一个，被称为分类(classification)问题。如果要求的输出由一个或者多个连续 变量组成，那么这个任务被称为回归(regression)。回归问题的一个例子是化学药品制造过程 中产量的预测。在这个问题中，输入由反应物、温度、压力组成。 在其他的模式识别问题中，训练数据由一组输入向量x组成，没有任何对应的目标值。 在这样的无监督学习(unsupervised learning)问题中，目标可能是发现数据中相似样本的 分组，这被称为聚类(clustering),或者决定输入空间中数据的分布，这被称为密度估计 (density estimation),或者把数据从高维空间投影到二维或者三维空间，为了数据可视化 (visualization) 最后，反馈学习(reinforcement learning)(Sutton and Barto,I998)技术关注的问题是在给 定的条件下，找到合适的动作，使得奖励达到最大值。这里，学习问题没有给定最优输出的用 例。这些用例必须在一系列的实验和错误中被发现。这与有监督学习相反。通常，有一个状态 和动作的序列，其中学习算法与环境交互。在许多情况下，当前动作不仅影响直接的奖励，也 对所有后续时刻的奖励有影响。例如，通过使用合适的反馈学习技术，一个神经网络可以学 会backgammon游戏的玩法，并且玩得很好(Tesauro,1994)。这里神经网络必须学习把一大组 位置信息、骰子投掷的结果作为输入，产生一个移动的方式作为输出。通过让神经网络自己和 自己玩一百万局，这个目的就可以达到。一个主要的挑战是backgammon游戏会涉及到相当多次 的移动，但是只有在游戏结束的时候才能给出奖励（以胜利的形式）。奖励必须被合理地分配 给所有引起胜利的移动步骤。这些移动中，有些移动很好，其他的移动不是那么好。这是信用 分配(credit assignment)问题的一个例子。反馈学习的一个通用的特征是探索(exploration)和 利用(exploitation)的折中。“探索”是指系统尝试新类型的动作，“利用”是指系统使用已知能产 生较高奖励的动作。过分地集中于探索或者利用都会产生较差的结果。反馈学习继续是机器学 习研究中得一个活跃的领域。然而，详细讨论反馈学习不在本书的范围内。 虽然这些任务中每一个都需要自己的工具和技术，但是在这些任务背后的许多关键思想都是 相通的。本章的主要目标是以一种相对非正式的形式介绍最重要的概念，并且使用简单的例子 来说明。稍后在本书中，我们将看到同样的思想以更加复杂的模型的形式重新出现，这些模型 能够应用于真实世界中模式识别的应用中。本章也将介绍将自始至终在本书中使用的三个重要 工具：概率论、决策论、信息论。虽然这些东西听起来让人感觉害怕，但是实际上它们非常直 观。并且，在实际应用中，如果想让机器学习技术发挥最大作用的话，清楚地理解它们是必须 的。 1.1例子：多项式曲线拟合 我们以一个简单的回归问题开始。本章中，我们将以这个问题为例，说明许多关键的概念。 假设我们观察到一个实值输入变量x,我们想使用这个观察来预测实值目标变量的值。对于这 个目的，一个很好的方法是考虑一个使用已知的产生方式人工制造出的例子，因为这样我们就 知道生成数据的精确过程，从而能够和我们学习到得模型进行比较。这个例子的数据由函 数si(2πx)产生，目标变量带有随机的噪声。详细的描述见附录A。 现在假设给定一个训练集。这个训练集由x的N次观测组成，写作x三(x1,…,xN)T,伴随这 对应的t的观测值，记作t三(t1,…,tv)T。图1.2展示了由N=10个数据点组成的图像。图1.2中 的输入数据集合x通过选择xn(m=1,·,N)的值来生成。这些xn均匀分布在区间[0,1刂，目标数 据集t的获得方式是：首先计算函数sn(2πx)的对应的值，然后给每个点增加一个小的符合高斯 分布的随机噪声（高斯分布将在1.2.4节讨论），从而得到对应的t的值。通过使用这种方式产 生数据，我们利用了许多真实数据集合的一个性质，即它们拥有一个内在的规律，这个规律是 我们想要学习的，但是独自的观察被随机噪声干扰。这种噪声可能由一个本质上随机的过程产 生，例如放射性衰变。但是更典型的情况是由于存在没有被观察到的具有变化性的噪声源。 我们的目标是利用这个训练集预测对于输入变量的新值的目标变量的值。正如我们将要看 到的那样，这涉及到隐式地发现内在的函数s(2πx)。这本质上是一个困难的问题，因为我们不 得不从有限的数据中生成。并且观察到得数据被噪声干扰，因此对于一个给定的蛇，合适的值 具有不确定性。概率论（在1.2节讨论）提供了一个框架，用来以精确的数学的形式描述这种不 确定性。决策论（在15节讨论）让我们能够根据合适的标准，利用这种概率的表示，进行最优 的预测。 10
量离散标签中的⼀个，被称为分类（classification）问题。如果要求的输出由⼀个或者多个连续 变量组成，那么这个任务被称为回归（regression）。回归问题的⼀个例⼦是化学药品制造过程 中产量的预测。在这个问题中，输⼊由反应物、温度、压⼒组成。 在其他的模式识别问题中，训练数据由⼀组输⼊向量x组成，没有任何对应的⽬标值。 在这样的⽆监督学习（unsupervised learning）问题中，⽬标可能是发现数据中相似样本的 分组，这被称为聚类（clustering），或者决定输⼊空间中数据的分布，这被称为密度估计 （density estimation），或者把数据从⾼维空间投影到⼆维或者三维空间，为了数据可视化 （visualization）。 最后，反馈学习（reinforcement learning）（Sutton and Barto, 1998）技术关注的问题是在给 定的条件下，找到合适的动作，使得奖励达到最⼤值。这⾥，学习问题没有给定最优输出的⽤ 例。这些⽤例必须在⼀系列的实验和错误中被发现。这与有监督学习相反。通常，有⼀个状态 和动作的序列，其中学习算法与环境交互。在许多情况下，当前动作不仅影响直接的奖励，也 对所有后续时刻的奖励有影响。例如，通过使⽤合适的反馈学习技术，⼀个神经⽹络可以学 会backgammon游戏的玩法，并且玩得很好（Tesauro, 1994）。这⾥神经⽹络必须学习把⼀⼤组 位置信息、骰⼦投掷的结果作为输⼊，产⽣⼀个移动的⽅式作为输出。通过让神经⽹络⾃⼰和 ⾃⼰玩⼀百万局，这个⽬的就可以达到。⼀个主要的挑战是backgammon游戏会涉及到相当多次 的移动，但是只有在游戏结束的时候才能给出奖励（以胜利的形式）。奖励必须被合理地分配 给所有引起胜利的移动步骤。这些移动中，有些移动很好，其他的移动不是那么好。这是信⽤ 分配（credit assignment）问题的⼀个例⼦。反馈学习的⼀个通⽤的特征是探索（exploration）和 利⽤（exploitation）的折中。“探索”是指系统尝试新类型的动作，“利⽤”是指系统使⽤已知能产 ⽣较⾼奖励的动作。过分地集中于探索或者利⽤都会产⽣较差的结果。反馈学习继续是机器学 习研究中得⼀个活跃的领域。然⽽，详细讨论反馈学习不在本书的范围内。 虽然这些任务中每⼀个都需要⾃⼰的⼯具和技术，但是在这些任务背后的许多关键思想都是 相通的。本章的主要⽬标是以⼀种相对⾮正式的形式介绍最重要的概念，并且使⽤简单的例⼦ 来说明。稍后在本书中，我们将看到同样的思想以更加复杂的模型的形式重新出现，这些模型 能够应⽤于真实世界中模式识别的应⽤中。本章也将介绍将⾃始⾄终在本书中使⽤的三个重要 ⼯具：概率论、决策论、信息论。虽然这些东西听起来让⼈感觉害怕，但是实际上它们⾮常直 观。并且，在实际应⽤中，如果想让机器学习技术发挥最⼤作⽤的话，清楚地理解它们是必须 的。 1.1 例⼦：多项式曲线拟合 我们以⼀个简单的回归问题开始。本章中，我们将以这个问题为例，说明许多关键的概念。 假设我们观察到⼀个实值输⼊变量x，我们想使⽤这个观察来预测实值⽬标变量t的值。对于这 个⽬的，⼀个很好的⽅法是考虑⼀个使⽤已知的产⽣⽅式⼈⼯制造出的例⼦，因为这样我们就 知道⽣成数据的精确过程，从⽽能够和我们学习到得模型进⾏⽐较。这个例⼦的数据由函 数sin(2πx)产⽣，⽬标变量带有随机的噪声。详细的描述见附录A。 现在假设给定⼀个训练集。这个训练集由x的N次观测组成，写作x ≡ (x1, …, xN ) T，伴随这 对应的t的观测值，记作t ≡ (t1, …, tN ) T。图1.2展⽰了由N = 10个数据点组成的图像。图1.2中 的输⼊数据集合x通过选择xn(n = 1, . . . , N)的值来⽣成。这些xn均匀分布在区间[0, 1]，⽬标数 据集t的获得⽅式是：⾸先计算函数sin(2πx)的对应的值，然后给每个点增加⼀个⼩的符合⾼斯 分布的随机噪声（⾼斯分布将在1.2.4节讨论），从⽽得到对应的tn的值。通过使⽤这种⽅式产 ⽣数据，我们利⽤了许多真实数据集合的⼀个性质，即它们拥有⼀个内在的规律，这个规律是 我们想要学习的，但是独⾃的观察被随机噪声⼲扰。这种噪声可能由⼀个本质上随机的过程产 ⽣，例如放射性衰变。但是更典型的情况是由于存在没有被观察到的具有变化性的噪声源。 我们的⽬标是利⽤这个训练集预测对于输⼊变量的新值xb的⽬标变量的值bt。正如我们将要看 到的那样，这涉及到隐式地发现内在的函数sin(2πx)。这本质上是⼀个困难的问题，因为我们不 得不从有限的数据中⽣成。并且观察到得数据被噪声⼲扰，因此对于⼀个给定的xb，合适的bt值 具有不确定性。概率论（在1.2节讨论）提供了⼀个框架，⽤来以精确的数学的形式描述这种不 确定性。决策论（在1.5节讨论）让我们能够根据合适的标准，利⽤这种概率的表⽰，进⾏最优 的预测。 10