Bayesian Reasoning and Machine Learning

Front Matter......Page 1
Preface......Page 2
BRML toolbox......Page 7
Contents......Page 11
I Inference in Probabilistic Models......Page 25
Probability Refresher......Page 31
Interpreting Conditional Probability......Page 33
Probability Tables......Page 35
Probabilistic Reasoning......Page 36
Prior, Likelihood and Posterior......Page 41
Two dice : what were the individual scores?......Page 42
Basic Probability code......Page 43
General utilities......Page 44
Exercises......Page 45
Graphs......Page 47
Adjacency matrix......Page 49
Clique matrix......Page 50
Summary......Page 51
Exercises......Page 52
The Benefits of Structure......Page 53
Modelling independencies......Page 54
Reducing the burden of specification......Page 56
Uncertain evidence......Page 57
Unreliable evidence......Page 58
Belief Networks......Page 59
Conditional independence......Page 61
The impact of collisions......Page 62
Graphical and distributional in/dependence......Page 65
Markov equivalence in belief networks......Page 67
Belief networks have limited expressibility......Page 68
Simpson's paradox......Page 69
Influence diagrams and the do-calculus......Page 71
Exercises......Page 72
Graphical Models......Page 77
Markov Networks......Page 78
Markov properties......Page 79
Hammersley-Clifford Theorem......Page 81
Conditional independence using Markov networks......Page 83
Lattice Models......Page 84
Chain Graphical Models......Page 85
Factor Graphs......Page 87
Expressiveness of Graphical Models......Page 88
Summary......Page 90
Exercises......Page 91
Variable elimination in a Markov chain and message passing......Page 95
The sum-product algorithm on factor graphs......Page 98
Computing the marginal likelihood......Page 101
The problem with loops......Page 102
Max-Product......Page 103
Finding the N most probable states......Page 105
Most probable path and shortest path......Page 107
Bucket elimination......Page 109
Loop-cut conditioning......Page 111
Most probable and shortest path......Page 112
Summary......Page 113
Exercises......Page 114
Reparameterisation......Page 117
Clique Graphs......Page 118
Absorption......Page 119
Absorption schedule on clique trees......Page 120
Junction Trees......Page 121
The running intersection property......Page 122
Moralisation......Page 123
Forming a junction tree from a clique graph......Page 124
Junction Trees for Multiply-Connected Distributions......Page 125
Triangulation algorithms......Page 126
The Junction Tree Algorithm......Page 128
Remarks on the JTA......Page 129
Computing the normalisation constant of a distribution......Page 130
The marginal likelihood......Page 131
Shafer-Shenoy propagation......Page 132
Reabsorption : Converting a Junction Tree to a Directed Network......Page 133
The Need For Approximations......Page 134
Summary......Page 135
Exercises......Page 136
Utility of money......Page 139
Decision Trees......Page 140
Extending Bayesian Networks for Decisions......Page 142
Syntax of influence diagrams......Page 143
Efficient inference......Page 147
Using a junction tree......Page 148
Markov Decision Processes......Page 151
Maximising expected utility by message passing......Page 152
Temporally Unbounded MDPs......Page 153
Policy iteration......Page 154
Time-dependent Markov decision processes and probabilistic planning......Page 155
Time-independent variational deterministic planner......Page 157
Options pricing and expected utility......Page 158
Binomial options pricing model......Page 159
Optimal investment......Page 161
Reinforcement learning......Page 162
Junction trees for influence diagrams......Page 164
Chest Clinic with Decisions......Page 165
Exercises......Page 166
II Learning in Probabilistic Models......Page 171
Numerical......Page 175
Distributions......Page 176
The Kullback-Leibler Divergence KL( q|p )......Page 179
Classical Distributions......Page 180
Multivariate Gaussian......Page 185
Completing the square......Page 187
Conditioning as system reversal......Page 188
Exponential Family......Page 189
Learning distributions......Page 190
Properties of Maximum Likelihood......Page 192
Maximum likelihood and the empirical distribution......Page 193
 Maximum likelihood training......Page 194
Bayesian inference of the mean and variance......Page 195
Summary......Page 197
Exercises......Page 198
Learning the bias of a coin......Page 207
Making decisions......Page 208
A continuum of parameters......Page 209
Decisions based on continuous intervals......Page 210
Maximum Likelihood Training of Belief Networks......Page 211
Global and local parameter independence......Page 214
Learning binary variable tables using a Beta prior......Page 216
Learning multivariate discrete tables using a Dirichlet prior......Page 217
Parents......Page 218
Structure learning......Page 220
Empirical independence......Page 221
Network scoring......Page 223
Chow-Liu Trees......Page 225
The likelihood gradient......Page 227
Decomposable Markov networks......Page 228
Non-decomposable Markov networks......Page 229
Constrained decomposable Markov networks......Page 230
Iterative scaling......Page 233
Conditional random fields......Page 234
Pseudo likelihood......Page 236
Bayesian Methods and ML-II......Page 237
Summary......Page 238
Exercises......Page 239
Naive Bayes and Conditional Independence......Page 243
Binary attributes......Page 244
Text classification......Page 247
Bayesian Naive Bayes......Page 248
Code......Page 250
Exercises......Page 251
Why hidden/missing variables can complicate proceedings......Page 255
The missing at random assumption......Page 256
Identifiability issues......Page 257
Variational EM......Page 258
Classical EM......Page 259
Application to Belief networks......Page 262
Partial E step......Page 266
A Failure Case for EM......Page 268
Variational Bayes......Page 269
EM is a special case of variational Bayes......Page 270
Factorising the parameter posterior......Page 271
Undirected models......Page 273
Exercises......Page 274
Comparing Models the Bayesian Way......Page 279
A continuous parameter space......Page 280
Occam's Razor and Bayesian Complexity Penalisation......Page 282
A continuous example : curve fitting......Page 283
Laplace's method......Page 284
Outcome analysis......Page 285
Hindep : model likelihood......Page 286
Hsame : model likelihood......Page 287
Dependent outcome analysis......Page 288
Code......Page 290
Exercises......Page 291
III Machine Learning......Page 295
Supervised learning......Page 299
Unsupervised learning......Page 300
Interacting with the environment......Page 301
Utility and Loss......Page 302
Using the empirical distribution......Page 303
Bayesian decision approach......Page 306
Bayes versus Empirical Decisions......Page 309
Summary......Page 310
Exercises......Page 311
Do As Your Neighbour Does......Page 313
K-Nearest Neighbours......Page 314
A Probabilistic Interpretation of Nearest Neighbours......Page 315
Exercises......Page 317
Principal Components Analysis......Page 319
Deriving the optimal linear reconstruction......Page 320
PCA algorithm......Page 322
PCA and nearest neighbours......Page 323
High Dimensional Data......Page 324
Eigen-decomposition for NLatent Semantic Analysis......Page 326
Information retrieval......Page 328
PCA With Missing Data......Page 329
Finding the principal directions......Page 330
Matrix Decomposition Methods......Page 331
Probabilistic latent semantic analysis......Page 332
Extensions and variations......Page 334
Applications of PLSA/NMF......Page 335
Kernel PCA......Page 337
Canonical Correlation Analysis......Page 338
SVD formulation......Page 339
Exercises......Page 340
Fisher's Linear Discriminant......Page 343
Canonical Variates......Page 345
Dealing with the nullspace......Page 346
Exercises......Page 348
Introduction: Fitting A Straight Line......Page 351
Linear Parameter Models for Regression......Page 352
Regularisation......Page 354
Radial basis functions......Page 355
The Dual Representation and Kernels......Page 356
Regression in the dual-space......Page 357
Linear Parameter Models for Classification......Page 358
Logistic regression......Page 359
Avoiding overconfident classification......Page 363
The Kernel Trick for Classification......Page 364
Maximum margin linear classifier......Page 365
Using kernels......Page 367
Soft Zero-One Loss for Outlier Robustness......Page 368
Summary......Page 369
Exercises......Page 370
Regression With Additive Gaussian Noise......Page 373
Bayesian linear parameter models......Page 374
Determining hyperparameters: ML-II......Page 375
Learning the hyperparameters using EM......Page 376
Hyperparameter optimisation : using the gradient......Page 377
Validation likelihood......Page 378
Classification......Page 379
Hyperparameter optimisation......Page 380
Laplace approximation......Page 381
Making predictions......Page 382
Variational Gaussian approximation......Page 383
Local variational approximation......Page 385
Code......Page 386
Exercises......Page 387
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 398
Smoothness of the functions......Page 399
Mercer kernels......Page 400
Fourier analysis for stationary kernels......Page 401
Binary classification......Page 402
Laplace's approximation......Page 403
Hyperparameter optimisation......Page 405
Exercises......Page 406
Density Estimation Using Mixtures......Page 409
Expectation Maximisation for Mixture Models......Page 410
Unconstrained discrete tables......Page 411
Mixture of product of Bernoulli distributions......Page 412
EM algorithm......Page 414
Practical issues......Page 416
Classification using Gaussian mixture models......Page 417
The Parzen estimator......Page 418
K-Means......Page 419
Mixture of Experts......Page 420
Indicator Models......Page 421
Joint indicator approach : Polya prior......Page 422
Latent Dirichlet allocation......Page 423
Graph based representations of data......Page 425
Monadic data......Page 426
Cliques and adjacency matrices for monadic binary data......Page 427
Code......Page 430
Exercises......Page 431
Factor Analysis......Page 433
Finding the optimal bias......Page 434
Direct likelihood optimisation......Page 435
Expectation maximisation......Page 437
Interlude: Modelling Faces......Page 439
Probabilistic Principal Components Analysis......Page 441
Canonical Correlation Analysis and Factor Analysis......Page 442
Independent Components Analysis......Page 443
Exercises......Page 445
The Rasch Model......Page 447
Bayesian Rasch models......Page 448
Bradley-Terry-Luce model......Page 449
Glicko and TrueSkill......Page 450
Exercises......Page 451
IV Dynamical Models......Page 453
Markov Models......Page 457
Equilibrium and stationary distribution of a Markov chain......Page 458
Fitting Markov models......Page 459
Mixture of Markov models......Page 460
The classical inference problems......Page 462
Filtering p(ht|v1:t)......Page 463
Correction smoothing......Page 464
Prediction......Page 466
Natural language models......Page 468
EM algorithm......Page 469
Mixture emission......Page 470
Discriminative training......Page 471
Explicit duration model......Page 472
Input-Output HMM......Page 473
Linear chain CRFs......Page 474
Dynamic Bayesian networks......Page 475
Automatic speech recognition......Page 476
Code......Page 477
Exercises......Page 478
Observed Linear Dynamical Systems......Page 483
Auto-Regressive Models......Page 484
Training an AR model......Page 485
Time-varying AR model......Page 486
Time-varying variance AR models......Page 487
Latent Linear Dynamical Systems......Page 488
Inference......Page 490
Filtering......Page 491
Smoothing : Rauch-Tung-Striebel correction method......Page 493
Most likely state......Page 494
Time independence and Riccati equations......Page 495
Identifiability issues......Page 496
EM algorithm......Page 497
Structured LDSs......Page 498
Inference......Page 499
Maximum Likelihood Learning using EM......Page 500
Code......Page 501
Exercises......Page 502
The Switching LDS......Page 505
Gaussian Sum Filtering......Page 506
Continuous filtering......Page 507
Collapsing Gaussians......Page 509
Gaussian Sum Smoothing......Page 510
Collapsing the mixture......Page 512
Using mixtures in smoothing......Page 513
Relation to other methods......Page 514
Reset Models......Page 515
A Poisson reset model......Page 518
Reset-HMM-LDS......Page 519
Exercises......Page 520
Stochastic Hopfield Networks......Page 523
A single sequence......Page 524
Boolean networks......Page 529
Deterministic latent variables......Page 530
An augmented Hopfield network......Page 531
Stochastically spiking neurons......Page 532
Dynamic synapses......Page 533
Leaky integrate and fire models......Page 534
Exercises......Page 535
V Approximate Inference......Page 537
Introduction......Page 541
Univariate sampling......Page 542
Rejection sampling......Page 543
Multi-variate sampling......Page 544
Dealing with evidence......Page 546
Gibbs Sampling......Page 547
Structured Gibbs sampling......Page 548
Remarks......Page 549
Markov chains......Page 550
Metropolis-Hastings sampling......Page 551
Auxiliary Variable Methods......Page 552
Hybrid Monte Carlo......Page 553
Swendson-Wang......Page 555
Slice sampling......Page 556
Importance Sampling......Page 558
Sequential importance sampling......Page 559
Particle filtering as an approximate forward pass......Page 560
Exercises......Page 563
The Laplace approximation......Page 567
Bounding the marginal likelihood......Page 568
Gaussian approximations using KL divergence......Page 569
Variational Bounding Using KL( q|p )......Page 570
Pairwise Markov random field......Page 571
Asynchronous updating guarantees approximation improvement......Page 574
Structured variational approximation......Page 575
Local and KL Variational Approximations......Page 576
Local approximation......Page 577
KL variational approximation......Page 578
The information maximisation algorithm......Page 579
Linear Gaussian decoder......Page 580
Classical BP on an undirected graph......Page 581
Loopy BP as a variational procedure......Page 582
Expectation Propagation......Page 585
Approximate MAP assignment......Page 588
Attractive binary MRFs......Page 590
Potts model......Page 592
Summary......Page 593
Exercises......Page 594
Vector algebra......Page 599
Planes and hyperplanes......Page 600
Matrices......Page 601
Determinants......Page 602
Computing the matrix inverse......Page 603
Eigenvalues and eigenvectors......Page 604
Matrix decompositions......Page 605
Interpreting the gradient vector......Page 606
Matrix calculus......Page 607
Optimisation......Page 608
Gradient descent with fixed stepsize......Page 609
Minimising quadratic functions using line search......Page 610
The conjugate vectors algorithm......Page 611
The conjugate gradients algorithm......Page 612
Quasi-Newton methods......Page 613
Constrained Optimisation using Lagrange Multipliers......Page 614
Lagrange Dual......Page 615
Bibliography......Page 617
Index......Page 631