A linear-time algorithm for computing the multinomial stochastic complexity

DOI10.1016/j.ipl.2007.04.003zbMath1184.68266OpenAlexW1980971799MaRDI QIDQ2379977

Petri Myllymäki, Petri Kontkanen

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.04.003

zbMATH Keywords

algorithmscomputational complexitycombinatorial problems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (9)

Graph Summarization with Latent Variable Probabilistic Models ⋮ Using the Bayesian Shtarkov solution for predictions ⋮ On model selection, Bayesian networks, and the Fisher information integral ⋮ Unsupervised discretization by two-dimensional MDL-based histogram ⋮ Fast and fully-automated histograms for large-scale data sets ⋮ The decomposed normalized maximum likelihood code-length criterion for selecting hierarchical latent variable models ⋮ Hierarchical two-part MDL code for multinomial distributions ⋮ Clustgrams: an extension to histogram densities based on the minimum description length principle ⋮ Minimum description length revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Modeling by shortest data description
• Estimating the dimension of a model
• On the Lambert \(w\) function
• Special issue: Average-case analysis of algorithms
• A Recurrence Related to Trees
• Asymptotic minimax regret for data compression, gambling, and prediction
• Strong optimality of the normalized ML models as universal codes and information in data
• The minimum description length principle in coding and modeling
• Fisher information and stochastic complexity

This page was built for publication: A linear-time algorithm for computing the multinomial stochastic complexity