Learning with the Minimum Description Length Principle

Foreword
Preface
Contents
Acronyms
1 Information and Coding
	1.1 Information, Probability, and Coding
		1.1.1 What is Information?
		1.1.2 Prefix Coding
		1.1.3 Kraft Inequality
	1.2 Shannon Information
		1.2.1 Probability Distribution
		1.2.2 Shannon\'s Coding Theorem
		1.2.3 Shannon Information
	1.3 Universal Coding
		1.3.1 Two-part Coding
		1.3.2 Bayes Coding
		1.3.3 Counting Coding
		1.3.4 Normalized Maximum Likelihood Coding
		1.3.5 Kolmogorov Complexity
	1.4 Stochastic Complexity
		1.4.1 Stochastic Complexity for Parametric Classes
		1.4.2 Shtarkov\'s Min-Max Regret
		1.4.3 Generalized Coding Theorem
	1.5 Parametric Complexity
		1.5.1 Asymptotic Approximation Method
		1.5.2 g-Function-Based Method*
		1.5.3 Fourier Method*
		1.5.4 Combinatorial Method
		1.5.5 Monte Carlo Method
	1.6 MDL Principle
		1.6.1 Machine Learning with MDL Principle
		1.6.2 Estimation
		1.6.3 Prediction
		1.6.4 Testing
	1.7 Summary of This Chapter
	References
2 Parameter Estimation
	2.1 Maximum Likelihood Estimation
		2.1.1 Maximum Likelihood Estimator
		2.1.2 MLE for Multivariate Gaussian and Outlier Detection
		2.1.3 MLE for Linear Regression
		2.1.4 Properties of Maximum Likelihood Estimator
	2.2 EM Algorithm
		2.2.1 EM Algorithm for Latent Variable Models
		2.2.2 Incremental EM Algorithm for Online Outlier Detection
	2.3 Maximum a Posteriori Estimation
		2.3.1 MAP Estimation and Regularization
		2.3.2 Sparse Regularized Linear Regression
		2.3.3 Sparse Regularized Graphical Model*
	2.4 Gradient Descent Methods
		2.4.1 Gradient Descent Algorithms
	2.5 High-Dimensional Penalty Selection
		2.5.1 Luckiness Normalized Maximum Likelihood Code-length
		2.5.2 Penalty Selection with LNML*
		2.5.3 Analytical Bounds for LNML Code-length*
	2.6 Bayesian Estimation
		2.6.1 Bayesian Estimator
		2.6.2 Gibbs Sampler
	2.7 Summary of This Chapter
	References
3 Model Selection
	3.1 Model Selection
		3.1.1 Problem Setting
		3.1.2 Akaike\'s Information Criterion
		3.1.3 Bayesian Information Criterion
		3.1.4 Minimum Message Length Criterion
		3.1.5 Cross-Validation
	3.2 Minimum Description Length Criterion
		3.2.1 MDL Criterion
		3.2.2 Consistency
		3.2.3 Estimation Optimality*
		3.2.4 Rate of Convergence
		3.2.5 Sequential Normalized Maximum Likelihood Criterion
	3.3 Applications of MDL Criterion
		3.3.1 Histogram Density Estimation
		3.3.2 Non-negative Matrix Factorization*
		3.3.3 Decision Tree Learning
		3.3.4 Dimensionality Selection for Word Embedding
		3.3.5 Time Series Model Selection
		3.3.6 Multivariate Linear Regression*
	3.4 Summary of This Chapter
	References
4 Latent Variable Model Selection
	4.1 MDL Approach to Latent Variable Model Selection
		4.1.1 Non-identifiability for Latent Variable Models
	4.2 Latent Stochastic Complexity
		4.2.1 LSC Criterion
		4.2.2 Computational Complexity of LSC
	4.3 Decomposed Normalized Maximum Likelihood Criterion
		4.3.1 DNML Criterion
		4.3.2 Computational Complexity of DNML
		4.3.3 Estimation Optimality*
	4.4 Applications of the DNML Criterion
		4.4.1 Naïve Bayes models
		4.4.2 Latent Dirichlet Allocation Model
		4.4.3 Stochastic Block Model
		4.4.4 Mixed Membership Stochastic Block Models*
		4.4.5 Multivariate Gaussian Mixture Model
		4.4.6 Approximating Inter-event Time Distributions
		4.4.7 Graph Summarization
		4.4.8 Probabilistic Principal Component Analysis*
		4.4.9 Non-negative Matrix Factorization Revisited*
		4.4.10 Dimensionality Selection of Hyperbolic Graph Embedding*
		4.4.11 Neural Network Model Selection*
	4.5 Summary of this Chapter
	References
5 Sequential Prediction
	5.1 Sequential Prediction
		5.1.1 Sequential Stochastic Prediction Algorithms
		5.1.2 Online Maximum Likelihood Prediction Algorithm
		5.1.3 Bayesian Prediction Algorithm
		5.1.4 Sequentially Normalized Maximum Likelihood Prediction Algorithm
		5.1.5 Discounting SNML Prediction with Application to Change Point Detection*
		5.1.6 Sequentially Luckiness Normalized Maximum Likelihood Prediction Algorithm
	5.2 High-Dimensional Asymptotics
		5.2.1 Prediction with Spike and Tails Prior*
	5.3 Summary of This Chapter
	References
6 MDL Change Detection
	6.1 A System of Change Detection
	6.2 Parameter Change Detection
		6.2.1 MDL Change Statistics
		6.2.2 Performance on Hypothesis Testing
		6.2.3 Sequential MDL Change Detection
		6.2.4 Network Change Detection
		6.2.5 Adaptive Windowing Method for Sequential MDL Change Detection
	6.3 Parameter Change Sign Detection
		6.3.1 Differential MDL Change Statistics*
		6.3.2 COVID-19 Pandemic Analysis*
	6.4 Latent Structure Change Detection
		6.4.1 Burst Detection
		6.4.2 Switching Distribution*
		6.4.3 Tracking Best Experts*
		6.4.4 Dynamic Model Selection
		6.4.5 Sequential Clustering Change Detection
		6.4.6 MDL Model Change Statistics
		6.4.7 Hierarchical Change Detection for Latent Variable Models*
	6.5 Latent Structure Change Sign Detection
		6.5.1 Structural Entropy
	6.6 Summary of this Chapter
	References
7 Continuous Model Selection
	7.1 Descriptive Dimensionality
		7.1.1 Motivation of Continuous Model Selection
		7.1.2 Definition of Descriptive Dimensionality*
	7.2 Continuous Model Selection
		7.2.1 Continuous Model Selection with Ddim
		7.2.2 Model Change Sign Detection Algorithms
	7.3 Applications of Continuous Model Selection
		7.3.1 Continuous Model Selection for GMM
		7.3.2 Continuous Model Selection for AR Model*
		7.3.3 Real Data Experiences for Model Change Sign Detection
	7.4 Summary of This Chapter
	References
8 Extension of Stochastic Complexity
	8.1 Extended Stochastic Complexity
		8.1.1 Decision-Theoretic Learning
		8.1.2 Extended Stochastic Complexity
	8.2 Function Estimation with ESC*
	8.3 Sequential Learning with ESC*
	8.4 Generalized Normalized Maximum Likelihood*
	8.5 Summary of This Chapter
	References
9 Mathematical Preliminaries
	9.1 Analytics
		9.1.1 Basic Notation
		9.1.2 Measure
		9.1.3 Max, Min, Sup, Inf
		9.1.4 Norm and Distance
		9.1.5 Taylor\'s Expansion
		9.1.6 Gamma Function and Stirling Formula
		9.1.7 Fubini\'s Theorem
		9.1.8 Fourier Transform
		9.1.9 Lebesgue\'s Dominated Convergence Theorem
	9.2 Probability
		9.2.1 Probability Space
		9.2.2 Random Variables
		9.2.3 Expectation
		9.2.4 Variable Transformation
		9.2.5 Inequalities
		9.2.6 Convergence
		9.2.7 Law of Large Numbers and Central Limit Theorem
		9.2.8 Entropy and Kullback–Leibler Divergence
		9.2.9 Probability Distance
		9.2.10 Monte Carlo Sampling Method
	9.3 Linear Algebra
		9.3.1 Eigenvalues and Quadratic Forms
		9.3.2 Matrix Algebra
	9.4 Time Complexity Notations
	References
Index