第1页 / 共343页
第2页 / 共343页
第3页 / 共343页
第4页 / 共343页
第5页 / 共343页
第6页 / 共343页
第7页 / 共343页
第8页 / 共343页
Machine Learning: a probabilistic approach.pdf
Machine Learning
A Probabilistic Approach
David Barber
http://www.idiap.ch/∼barber
c David Barber 2001, 2002,2003,2004,2006
Contents
1 Introduction
1.1 Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1 Unsupervised Learning . . . . . . . . . . . . . . . . . . . . .
1.1.2
Supervised Learning . . . . . . . . . . . . . . . . . . . . . .
1.2 Supervised Learning Approaches . . . . . . . . . . . . . . . . . . .
1.2.1 Whence optimisation? Fitting a straight line . . . . . . . .
1.3 Problems
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Solutions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
I Machine Learning : The basics
2 Nearest Neighbour Classification
2.1 Nearest Neighbour . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 Problems with Nearest Neighbours . . . . . . . . . . . . . .
2.2 K Nearest Neighbours . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Handwritten digit Example . . . . . . . . . . . . . . . . . . . . . .
2.4 A Probabilistic Interpretation of Nearest Neighbours . . . . . . . .
3 Linear Dimension Reduction
3.1 Principal Components Analysis . . . . . . . . . . . . . . . . . . . .
3.1.1 Example : Reducing the dimension of digits . . . . . . . . .
3.1.2 PCA and Nearest Neighbours . . . . . . . . . . . . . . . . .
3.1.3 Mega Dimensional Data . . . . . . . . . . . . . . . . . . . .
3.1.4 PCA is good because it is a poor compressor! . . . . . . . .
3.2 Deriving the Optimal Linear Reconstruction . . . . . . . . . . . . .
3.3 Problems
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 Solutions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
12
12
12
14
17
18
19
20
21
21
22
23
24
25
27
27
30
30
31
31
32
33
36
1
Machine Learning : A probabilistic approach : c David Barber 2001,2002,2003,2004,2006
4 Generalisation
4.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1
Supervised Learning . . . . . . . . . . . . . . . . . . . . . .
4.1.2 Training Error
. . . . . . . . . . . . . . . . . . . . . . . . .
4.1.3 Test Error . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.4 Validation Data . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.5 Dodgy Joe and Lucky Jim . . . . . . . . . . . . . . . . . . .
4.1.6 Regularisation . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Problems
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Solutions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 Linear Discriminant Analysis
5.1 Unsupervised Dimension Reduction . . . . . . . . . . . . . . . . . .
5.1.1 Using PCA for visualisation . . . . . . . . . . . . . . . . . .
5.2 Fishers Linear Discriminant . . . . . . . . . . . . . . . . . . . . . .
5.2.1 One dimensional projection . . . . . . . . . . . . . . . . . .
5.3 Canonical Variates . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.1 Using Canonical variates on the Digits Data . . . . . . . . .
6 Linear Parameter Models
6.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1.1 Regression and PCA . . . . . . . . . . . . . . . . . . . . . .
6.2 Linear Parameter Models
. . . . . . . . . . . . . . . . . . . . . . .
6.2.1 Training LPMs . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.2 Regularisation and numerical stability . . . . . . . . . . . .
6.2.3 Higher Dimensional Outputs
. . . . . . . . . . . . . . . . .
6.2.4 Classification . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3 Radial Basis Functions . . . . . . . . . . . . . . . . . . . . . . . . .
6.4 The curse of Dimensionality . . . . . . . . . . . . . . . . . . . . . .
6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7 Layered Neural Networks
7.1 Sequential Layered Processing . . . . . . . . . . . . . . . . . . . . .
7.2 The Perceptron . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.3 Multilayer Perceptrons . . . . . . . . . . . . . . . . . . . . . . . . .
7.3.1 Understanding Neural Networks
. . . . . . . . . . . . . . .
2
39
39
39
40
41
41
41
43
44
44
45
45
45
45
46
47
48
49
49
50
50
51
51
52
52
52
53
54
55
55
55
56
58
Machine Learning : A probabilistic approach : c David Barber 2001,2002,2003,2004,2006
7.4 Training multi-layered perceptrons . . . . . . . . . . . . . . . . . .
7.4.1
Single Hidden Layer . . . . . . . . . . . . . . . . . . . . . .
7.4.2 Back Propagation . . . . . . . . . . . . . . . . . . . . . . .
7.4.3 Training ensembles of networks . . . . . . . . . . . . . . . .
7.5 Adaptive Basis Function Networks . . . . . . . . . . . . . . . . . .
7.5.1 Adaptive Basis Functions . . . . . . . . . . . . . . . . . . .
7.6 Training Adaptive Basis Functions . . . . . . . . . . . . . . . . . .
7.6.1 Non-local Basis Functions . . . . . . . . . . . . . . . . . . .
7.7 Committees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.8 Summary and Outlook . . . . . . . . . . . . . . . . . . . . . . . . .
8 Autoencoders
8.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.1.1 Linear Dimension Reduction (PCA)
. . . . . . . . . . . . .
8.1.2 Manifolds : The need for non-linearity . . . . . . . . . . . .
8.2 Non-linear Dimension Reduction . . . . . . . . . . . . . . . . . . .
8.2.1 Training Autoencoders . . . . . . . . . . . . . . . . . . . . .
8.3 Uses of Autoencoders
. . . . . . . . . . . . . . . . . . . . . . . . .
8.3.1 A Visualisation example . . . . . . . . . . . . . . . . . . . .
9 Data Visualisation
9.1 Classical Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.1.1 Finding the optimal points
. . . . . . . . . . . . . . . . . .
9.1.2 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . .
9.2 Sammon Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.3 A word of warning . . . . . . . . . . . . . . . . . . . . . . . . . . .
II
Inference and Learning in Probabilistic Models
10 Basic Concepts in Probability
10.1 What does random mean? . . . . . . . . . . . . . . . . . . . . . . .
10.2 What is Probability? . . . . . . . . . . . . . . . . . . . . . . . . . .
10.3 Rules of Probability . . . . . . . . . . . . . . . . . . . . . . . . . .
10.4 Problems
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.5 Solutions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
58
60
61
61
62
62
63
64
65
65
67
67
67
67
68
68
69
70
71
71
72
73
74
75
76
77
77
77
78
79
80
Machine Learning : A probabilistic approach : c David Barber 2001,2002,2003,2004,2006
11 Introducing Graphical Models
11.1 Belief Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.1.1 Tracey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.2 A word on notation . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.3 Example : Was it the Burglar? . . . . . . . . . . . . . . . . . . . .
11.4 Belief Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.4.1 Conditional Independence . . . . . . . . . . . . . . . . . . .
11.4.2 Intuition . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.4.3 d-Separation . . . . . . . . . . . . . . . . . . . . . . . . . .
11.5 Graphical Models . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.5.1 Markov Random Fields
. . . . . . . . . . . . . . . . . . . .
11.5.2 Expressiveness of Graphical Models
. . . . . . . . . . . . .
11.6 Problems
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12 Inference in Belief Networks
12.1 Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12.2 Variable Elimination in a simple chain . . . . . . . . . . . . . . . .
12.3 Bucket Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
81
81
81
84
84
86
87
87
88
90
92
93
93
97
97
97
99
12.4 Belief Propagtion : Inference in Singly Connected Graphs . . . . . 101
12.4.1 Undirected Belief Propagation . . . . . . . . . . . . . . . . 102
12.4.2 Directed Belief Propagation . . . . . . . . . . . . . . . . . . 103
12.4.3 Example : Directed Belief Propagation . . . . . . . . . . . . 106
12.5 Belief Revision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
12.6 The Generalised Distributive Law . . . . . . . . . . . . . . . . . . . 109
12.7 Inference in Multiply-Connected Graphs . . . . . . . . . . . . . . . 110
12.7.1 Conditioning . . . . . . . . . . . . . . . . . . . . . . . . . . 111
12.8 Cluster Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
12.9 KL divergence approach to marginalisation on Trees . . . . . . . . 114
12.10Problems
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
12.11Solutions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
13 The Junction Tree Algorithm
124
13.1 Absorption and Marginal Consistency . . . . . . . . . . . . . . . . 124
13.2 Junction Trees
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
13.3 Constructing Junction Trees for Singly-Connected Distributions . . 128
Machine Learning : A probabilistic approach : c David Barber 2001,2002,2003,2004,2006
5
13.4 Junction Trees for Multiply-Connected Distributions . . . . . . . . 130
13.5 Triangulation Algorithms
. . . . . . . . . . . . . . . . . . . . . . . 132
13.6 Finding a JT from a Triangulated Graph . . . . . . . . . . . . . . 133
13.7 The Junction Tree Algorithm . . . . . . . . . . . . . . . . . . . . . 133
13.7.1 Finding the Most Likely State
. . . . . . . . . . . . . . . . 134
13.8 Problems
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
13.9 Solutions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
14 Variational Learning and EM
138
14.1 Maximum Likelihood . . . . . . . . . . . . . . . . . . . . . . . . . . 138
14.1.1 Missing Data/Variables
. . . . . . . . . . . . . . . . . . . . 141
14.2 Variational Learning and Expectation Maximisation . . . . . . . . 142
14.3 Optimising the Likelihood by Gradient methods
. . . . . . . . . . 150
14.4 Iterated Proportional Fitting . . . . . . . . . . . . . . . . . . . . . 151
14.5 Bayesian Methods and ML-II . . . . . . . . . . . . . . . . . . . . . 152
14.6 Problems
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
14.7 Solutions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
III Probabilistic models in Machine Learning
15 Introduction to Bayesian Methods
156
157
15.1 Problems
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
15.2 Solutions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
16 Bayesian Regression
169
16.1 Problems
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
16.2 Solutions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
17 Logistic Regression
173
17.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
17.1.1 Training . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
17.1.2 Gradient Ascent
. . . . . . . . . . . . . . . . . . . . . . . . 176
17.1.3 Avoiding Overconfident Classification . . . . . . . . . . . . 179
17.1.4 Logistic Regression and PCA ? . . . . . . . . . . . . . . . . 179
17.1.5 An Example : Classifying Handwritten Digits . . . . . . . . 180
17.2 The Kernel Trick . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
Machine Learning : A probabilistic approach : c David Barber 2001,2002,2003,2004,2006
6
17.3 Mixture Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
17.3.1 Mixtures
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
17.3.2 Mixture of Experts . . . . . . . . . . . . . . . . . . . . . . . 183
17.3.3 A ‘Bayesian’ approach to setting the regularisation parameter184
17.3.4 Evidence Procedure . . . . . . . . . . . . . . . . . . . . . . 185
17.4 Problems
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
17.5 Solutions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
18 Naive Bayes
190
18.1 Why Naive Bayes? . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
18.2 Understanding Conditional Independence . . . . . . . . . . . . . . 190
18.3 Are they Scottish? . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
18.3.1 Further Issues . . . . . . . . . . . . . . . . . . . . . . . . . . 192
18.3.2 Text Classification . . . . . . . . . . . . . . . . . . . . . . . 193
18.4 Pitfalls with Naive Bayes
. . . . . . . . . . . . . . . . . . . . . . . 193
18.5 Estimation using Maximum Likelihood : Bernoulli Process . . . . . 194
18.5.1 Classification Boundary . . . . . . . . . . . . . . . . . . . . 195
18.6 Naive Bayes : The multinomial case . . . . . . . . . . . . . . . . . 195
18.6.1 Dirichlet Prior
. . . . . . . . . . . . . . . . . . . . . . . . . 196
18.7 Problems
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
18.8 Solutions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
19 Mixture Models : Discrete Hidden Variables
203
19.1 Mixture Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
19.2 Gaussian Mixture Models . . . . . . . . . . . . . . . . . . . . . . . 205
19.3 K Means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
19.3.1 The algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 210
19.3.2 Uses of K Means . . . . . . . . . . . . . . . . . . . . . . . . 211
19.4 Classification using Mixture Models
. . . . . . . . . . . . . . . . . 211
19.5 Mixture of Multi-nomials
. . . . . . . . . . . . . . . . . . . . . . . 212
19.6 Problems
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
19.7 Solutions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
Machine Learning : A probabilistic approach : c David Barber 2001,2002,2003,2004,2006
20 Factor Analysis and PPCA
7
217
20.1 Linear Subspace Methods . . . . . . . . . . . . . . . . . . . . . . . 217
20.2 A Toy Comparision of FA and PPCA . . . . . . . . . . . . . . . . 222
20.3 Non-linear Subspace Methods . . . . . . . . . . . . . . . . . . . . . 224
20.3.1 Non linear Factor Analysis
. . . . . . . . . . . . . . . . . . 224
20.4 Probabilistic PCA . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
20.5 Problems
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
20.6 Solutions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
21 Independent Component Analysis
230
21.0.1 An alternative variational approach . . . . . . . . . . . . . 235
21.0.2 Static Case : ICA with external Inputs
. . . . . . . . . . . 236
21.1 Expectation Propagation . . . . . . . . . . . . . . . . . . . . . . . . 236
21.1.1 A possible solution . . . . . . . . . . . . . . . . . . . . . . . 237
22 Dynamic Bayesian Networks : Discrete Hidden Variables
239
22.1 The Importance of Time . . . . . . . . . . . . . . . . . . . . . . . . 239
22.1.1 Parallel and Sequential Inference . . . . . . . . . . . . . . . 243
22.1.2 Rauch Tung Striebel and the α − γ recursions . . . . . . . . 246
22.1.3 Viterbi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
22.2 Applications of HMMs . . . . . . . . . . . . . . . . . . . . . . . . . 252
22.3 Problems
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
22.4 Solutions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
23 Dynamic Continuous Hiddens : Linear Dynamical Systems
258
23.1 Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
23.1.1 The Forward Pass : The Kalman Filter
. . . . . . . . . . . 259
23.1.2 The Kalman Smoother : The Rauch-Tung-Striebel Smoother 261
23.1.3 The Likelihood . . . . . . . . . . . . . . . . . . . . . . . . . 262
23.2 EM Algorithm for Learning . . . . . . . . . . . . . . . . . . . . . . 263
23.3 Problems
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
23.4 Solutions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
