Bayesian Reasoning and Machine Learning

Preface......Page 2
BRML toolbox......Page 7
I Inference in Probabilistic Models......Page 25
Probability Refresher......Page 31
Interpreting Conditional Probability......Page 34
Probability Tables......Page 36
Probabilistic Reasoning......Page 37
Prior, Likelihood and Posterior......Page 41
Basic Probability code......Page 43
Summary......Page 45
Exercises......Page 46
Graphs......Page 49
Edge list......Page 51
Clique matrix......Page 52
Summary......Page 53
Exercises......Page 54
The Benefits of Structure......Page 55
Modelling independencies......Page 56
Reducing the burden of specification......Page 58
Uncertain evidence......Page 59
Unreliable evidence......Page 61
Belief Networks......Page 62
Conditional independence......Page 63
The impact of collisions......Page 65
d-Separation......Page 67
Graphical and distributional in/dependence......Page 68
Belief networks have limited expressibility......Page 70
Simpson\'s paradox......Page 71
Influence diagrams and the do-calculus......Page 73
Summary......Page 74
Exercises......Page 75
Graphical Models......Page 81
Markov Networks......Page 82
Markov properties......Page 83
Hammersley-Clifford Theorem......Page 85
Conditional independence using Markov networks......Page 87
Lattice Models......Page 88
Chain Graphical Models......Page 89
Factor Graphs......Page 91
Conditional independence in factor graphs......Page 92
Expressiveness of Graphical Models......Page 93
Exercises......Page 95
Variable elimination in a Markov chain and message passing......Page 99
The sum-product algorithm on factor graphs......Page 102
Computing the marginal likelihood......Page 105
The problem with loops......Page 106
Max-Product......Page 107
Finding the N most probable states......Page 109
Most probable path and shortest path......Page 111
Bucket elimination......Page 113
Loop-cut conditioning......Page 115
Most probable and shortest path......Page 116
Summary......Page 117
Exercises......Page 118
Reparameterisation......Page 121
Clique Graphs......Page 122
Absorption......Page 123
Absorption schedule on clique trees......Page 124
Junction Trees......Page 125
The running intersection property......Page 126
Forming a junction tree from a clique graph......Page 128
Junction Trees for Multiply-Connected Distributions......Page 129
Triangulation algorithms......Page 131
The Junction Tree Algorithm......Page 133
Remarks on the JTA......Page 134
The marginal likelihood......Page 135
Shafer-Shenoy propagation......Page 137
Reabsorption : Converting a Junction Tree to a Directed Network......Page 138
Bounded width junction trees......Page 139
Summary......Page 140
Exercises......Page 141
Utility of money......Page 143
Decision Trees......Page 144
Syntax of influence diagrams......Page 147
Efficient inference......Page 151
Using a junction tree......Page 152
Markov Decision Processes......Page 155
Maximising expected utility by message passing......Page 156
Bellman\'s equation......Page 157
Value iteration......Page 158
A curse of dimensionality......Page 159
Time-dependent Markov decision processes and probabilistic planning......Page 160
Time-independent variational deterministic planner......Page 161
Financial Matters......Page 162
Options pricing and expected utility......Page 163
Binomial options pricing model......Page 164
Optimal investment......Page 165
Partially observable MDPs......Page 166
Reinforcement learning......Page 167
Sum/Max under a partial order......Page 168
Chest Clinic with Decisions......Page 169
Summary......Page 170
Exercises......Page 171
II Learning in Probabilistic Models......Page 175
Numerical......Page 179
Distributions......Page 180
The Kullback-Leibler Divergence KL( q|p )......Page 183
Entropy......Page 184
Classical Distributions......Page 185
Multivariate Gaussian......Page 190
Completing the square......Page 191
Conditioning as system reversal......Page 192
Whitening and centering......Page 193
Conjugate priors......Page 194
Learning distributions......Page 195
Properties of Maximum Likelihood......Page 197
Maximum likelihood and the empirical distribution......Page 198
 Maximum likelihood training......Page 199
Bayesian inference of the mean and variance......Page 200
Gauss-Gamma distribution......Page 201
Exercises......Page 202
Learning the bias of a coin......Page 211
Making decisions......Page 212
A continuum of parameters......Page 213
Decisions based on continuous intervals......Page 214
Maximum Likelihood Training of Belief Networks......Page 215
Global and local parameter independence......Page 218
Learning binary variable tables using a Beta prior......Page 220
Learning multivariate discrete tables using a Dirichlet prior......Page 222
Parents......Page 223
Structure learning......Page 224
Empirical independence......Page 226
Network scoring......Page 227
Chow-Liu Trees......Page 229
The likelihood gradient......Page 231
Decomposable Markov networks......Page 232
Non-decomposable Markov networks......Page 234
Constrained decomposable Markov networks......Page 235
Iterative scaling......Page 237
Conditional random fields......Page 239
Learning the structure......Page 241
Demo of empirical conditional independence......Page 242
Exercises......Page 243
Naive Bayes and Conditional Independence......Page 247
Binary attributes......Page 248
Multi-state variables......Page 251
Bayesian Naive Bayes......Page 252
Learning tree augmented Naive Bayes networks......Page 254
Exercises......Page 255
Why hidden/missing variables can complicate proceedings......Page 259
The missing at random assumption......Page 260
Maximum likelihood......Page 261
Variational EM......Page 262
Classical EM......Page 264
Application to Belief networks......Page 266
Application to Markov networks......Page 270
Partial E step......Page 271
A Failure Case for EM......Page 272
Variational Bayes......Page 273
Factorising the parameter posterior......Page 275
Code......Page 278
Exercises......Page 279
Comparing Models the Bayesian Way......Page 283
A continuous parameter space......Page 284
Occam\'s Razor and Bayesian Complexity Penalisation......Page 286
A continuous example : curve fitting......Page 287
Laplace\'s method......Page 288
Outcome analysis......Page 289
Hindep : model likelihood......Page 290
Hsame : model likelihood......Page 291
Dependent outcome analysis......Page 292
Code......Page 294
Exercises......Page 295
III Machine Learning......Page 299
Supervised learning......Page 303
Unsupervised learning......Page 304
Interacting with the environment......Page 305
Utility and Loss......Page 306
Using the empirical distribution......Page 307
Bayesian decision approach......Page 310
Learning lower-dimensional representations in semi-supervised learning......Page 313
Bayes versus Empirical Decisions......Page 314
Exercises......Page 315
Do As Your Neighbour Does......Page 317
K-Nearest Neighbours......Page 318
A Probabilistic Interpretation of Nearest Neighbours......Page 319
Exercises......Page 321
Principal Components Analysis......Page 323
Deriving the optimal linear reconstruction......Page 324
PCA algorithm......Page 326
PCA and nearest neighbours......Page 328
High Dimensional Data......Page 329
Latent Semantic Analysis......Page 330
Information retrieval......Page 332
PCA With Missing Data......Page 333
Finding the principal directions......Page 334
Collaborative filtering using PCA with missing data......Page 335
Probabilistic latent semantic analysis......Page 336
Extensions and variations......Page 339
Applications of PLSA/NMF......Page 340
Kernel PCA......Page 341
Canonical Correlation Analysis......Page 343
Code......Page 344
Exercises......Page 345
Fisher\'s Linear Discriminant......Page 347
Canonical Variates......Page 349
Dealing with the nullspace......Page 351
Exercises......Page 352
Introduction: Fitting A Straight Line......Page 355
Linear Parameter Models for Regression......Page 356
Regularisation......Page 358
Radial basis functions......Page 359
The Dual Representation and Kernels......Page 360
Regression in the dual-space......Page 361
Linear Parameter Models for Classification......Page 362
Logistic regression......Page 363
Avoiding overconfident classification......Page 367
The Kernel Trick for Classification......Page 368
Maximum margin linear classifier......Page 369
Using kernels......Page 371
Soft Zero-One Loss for Outlier Robustness......Page 372
Summary......Page 373
Exercises......Page 374
Regression With Additive Gaussian Noise......Page 377
Bayesian linear parameter models......Page 378
Determining hyperparameters: ML-II......Page 379
Learning the hyperparameters using EM......Page 380
Hyperparameter optimisation : using the gradient......Page 381
Validation likelihood......Page 382
Classification......Page 383
Hyperparameter optimisation......Page 384
Laplace approximation......Page 385
Making predictions......Page 386
Relevance vector machine for classification......Page 387
Summary......Page 388
Exercises......Page 389
From parametric to non-parametric......Page 391
From Bayesian linear models to Gaussian processes......Page 392
A prior on functions......Page 393
Regression with noisy training outputs......Page 394
Covariance Functions......Page 395
Making new covariance functions from old......Page 396
Stationary covariance functions......Page 397
Non-stationary covariance functions......Page 399
Mercer kernels......Page 400
Gaussian Processes for Classification......Page 402
Laplace\'s approximation......Page 403
Summary......Page 406
Exercises......Page 407
Density Estimation Using Mixtures......Page 411
Unconstrained discrete tables......Page 412
Mixture of product of Bernoulli distributions......Page 414
EM algorithm......Page 416
Practical issues......Page 418
Classification using Gaussian mixture models......Page 419
The Parzen estimator......Page 420
K-Means......Page 421
Mixture of Experts......Page 422
Indicator Models......Page 423
Joint indicator approach : Polya prior......Page 424
Latent Dirichlet allocation......Page 425
Graph based representations of data......Page 427
Monadic data......Page 428
Cliques and adjacency matrices for monadic binary data......Page 429
Code......Page 432
Exercises......Page 433
Factor Analysis......Page 435
Finding the optimal bias......Page 436
Direct likelihood optimisation......Page 437
Expectation maximisation......Page 439
Interlude: Modelling Faces......Page 441
Probabilistic Principal Components Analysis......Page 443
Canonical Correlation Analysis and Factor Analysis......Page 444
Independent Components Analysis......Page 445
Exercises......Page 447
The Rasch Model......Page 449
Bayesian Rasch models......Page 450
Bradly-Terry-Luce model......Page 451
Glicko and TrueSkill......Page 452
Exercises......Page 453
IV Dynamical Models......Page 455
Markov Models......Page 459
Equilibrium and stationary distribution of a Markov chain......Page 460
Fitting Markov models......Page 461
Mixture of Markov models......Page 462
The classical inference problems......Page 464
Filtering p(ht|v1:t)......Page 465
Parallel smoothing p(ht|v1:T)......Page 466
Correction smoothing......Page 467
Most likely joint state......Page 468
Natural language models......Page 470
EM algorithm......Page 471
Mixture emission......Page 473
Discriminative training......Page 474
Input-Output HMM......Page 475
Linear chain CRFs......Page 476
Dynamic Bayesian networks......Page 477
Automatic speech recognition......Page 478
Part-of-speech tagging......Page 479
Summary......Page 480
Exercises......Page 481
Observed Linear Dynamical Systems......Page 487
Auto-Regressive Models......Page 488
Training an AR model......Page 489
Time-varying AR model......Page 490
Latent Linear Dynamical Systems......Page 492
Inference......Page 493
Filtering......Page 495
Smoothing : Rauch-Tung-Striebel correction method......Page 496
Time independence and Riccati equations......Page 498
EM algorithm......Page 500
Subspace Methods......Page 501
Structured LDSs......Page 502
Maximum Likelihood Learning using EM......Page 503
Code......Page 504
Exercises......Page 505
The Switching LDS......Page 511
Gaussian Sum Filtering......Page 512
Continuous filtering......Page 513
Collapsing Gaussians......Page 515
Gaussian Sum Smoothing......Page 516
Collapsing the mixture......Page 518
Using mixtures in smoothing......Page 519
Relation to other methods......Page 520
Reset Models......Page 522
A Poisson reset model......Page 524
Reset-HMM-LDS......Page 525
Exercises......Page 526
Stochastic Hopfield Networks......Page 529
A single sequence......Page 530
Boolean networks......Page 535
Deterministic latent variables......Page 536
An augmented Hopfield network......Page 537
Neural Models......Page 538
Dynamic synapses......Page 539
Leaky integrate and fire models......Page 540
Exercises......Page 541
V Approximate Inference......Page 543
Introduction......Page 547
Univariate sampling......Page 548
Rejection sampling......Page 549
Multi-variate sampling......Page 550
Ancestral Sampling......Page 551
Gibbs Sampling......Page 552
Gibbs sampling as a Markov chain......Page 553
Structured Gibbs sampling......Page 554
Markov Chain Monte Carlo (MCMC)......Page 555
Metropolis-Hastings sampling......Page 556
Hybrid Monte Carlo......Page 558
Swendson-Wang......Page 560
Slice sampling......Page 562
Importance Sampling......Page 563
Sequential importance sampling......Page 565
Particle filtering as an approximate forward pass......Page 566
Summary......Page 568
Exercises......Page 569
The Laplace approximation......Page 571
Bounding the marginal likelihood......Page 572
Gaussian approximations using KL divergence......Page 573
Variational Bounding Using KL( q|p )......Page 574
Pairwise Markov random field......Page 575
Asynchronous updating guarantees approximation improvement......Page 578
Structured variational approximation......Page 579
Mutual Information Maximisation : A KL Variational Approach......Page 580
The information maximisation algorithm......Page 582
Classical BP on an undirected graph......Page 583
Loopy BP as a variational procedure......Page 584
Expectation Propagation......Page 587
MAP assignment......Page 590
Attractive binary MRFs......Page 591
Potts model......Page 593
Further Reading......Page 594
Exercises......Page 595
VI Appendix......Page 601
Vector algebra......Page 603
Planes and hyperplanes......Page 604
Matrices......Page 605
Determinants......Page 606
Matrix inversion......Page 607
Eigenvalues and eigenvectors......Page 608
Matrix decompositions......Page 609
Higher derivatives......Page 611
Matrix calculus......Page 612
Optimisation......Page 613
Gradient descent with fixed stepsize......Page 614
Minimising quadratic functions using line search......Page 615
The conjugate gradients algorithm......Page 616
Quasi-Newton methods......Page 618
Constrained Optimisation using Lagrange Multipliers......Page 619
Bibliography......Page 621
Index......Page 635