A randomized approximation of the MDL for stochastic models with hidden variables
Published 1 January 1996Open access
Kenji Yamanishi
Citations10
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A randomized algorithm, RAMDL, which efficiently approximates the SC for stochastic models with hidden variables, and quantifies the tradeoff relation between the statistical approximation accuracy and computational complexity, in general forms.
Abstract
Article Free Access Share on A randomized approximation of the MDL for stochastic models with hidden variables Author: Kenji Yamanishi C&C Research Laboratories, NEC Corporation, 1-1, 4-chome, Miyazaki, Miyamae-ku, Kawasaki, Kanagawa 216, Japan C&C Research Laboratories, NEC Corporation, 1-1, 4-chome, Miyazaki, Miyamae-ku, Kawasaki, Kanagawa 216, JapanView Profile Authors Info & Claims COLT '96: Proceedings of the ninth annual conference on Computational learning theoryJanuary 1996 Pages 99–109https://doi.org/10.1145/238061.238074Online:01 January 1996Publication History 4citation241DownloadsMetricsTotal Citations4Total Downloads241Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
Keywords
Computer ScienceMathematics
Journal of the Royal Statistical Society Series B (Statistical Methodology)Maximum Likelihood from Incomplete Data Via the <i>EM</i> Algorithm
49,657 Citations1977A. P. Dempster, N. M. Laird +1 more
IEEE Transactions on Pattern Analysis and Machine IntelligenceStochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
17,980 Citations1984Stuart Geman, Donald Geman
The analogy between images and statistical mechanics systems is made and the analogous operation under the posterior distribution yields the maximum a posteriori (MAP) estimate of the image given the degraded observations, creating a highly parallel ``relaxation'' algorithm for MAP estimation.
BiometrikaMonte Carlo sampling methods using Markov chains and their applications
15,200 Citations1970W. Keith Hastings
Journal of the American Statistical AssociationSampling-Based Approaches to Calculating Marginal Densities
6,616 Citations1990Alan E. Gelfand, A. F. M. Smith
Stochastic substitution, the Gibbs sampler, and the sampling-importance-resampling algorithm can be viewed as three alternative sampling- (or Monte Carlo-) based approaches to the calculation of numerical estimates of marginal probability distributions.
AutomaticaModeling by shortest data description
5,944 Citations1978J. Rissanen
The number of digits it takes to write down an observed sequence x1,...,xN of a time series depends on the model with its parameters that one assumes to have generated the observed data.
Digital Access to Scholarship at Harvard (DASH) (Harvard University)Maximum Likelihood from Incomplete Data via the EM Algorithm
4,523 Citations1977Dempster, Arthur P., Laird, Nan M. +1 more
Journal of the American Statistical AssociationThe Calculation of Posterior Distributions by Data Augmentation
3,782 Citations1987Martin A. Tanner, Wing Hung Wong
If data augmentation can be used in the calculation of the maximum likelihood estimate, then in the same cases one ought to be able to use it in the computation of the posterior distribution of parameters of interest.
Texts in computer scienceAn Introduction to Kolmogorov Complexity and Its Applications
3,734 Citations2019Ming Li, Paul Vitányi
The Annals of StatisticsOn the Convergence Properties of the EM Algorithm
3,252 Citations1983Changbao Wu
Journal of the Royal Statistical Society Series B (Statistical Methodology)Estimation of Finite Mixture Distributions Through Bayesian Sampling
913 Citations1994Jean Diebolt, Christian P. Robert
IEEE Transactions on Information TheoryFisher information and stochastic complexity
841 Citations1996J. Rissanen
A sharper code length is obtained as the stochastic complexity and the associated universal process are derived for a class of parametric processes by taking into account the Fisher information and removing an inherent redundancy in earlier two-part codes.
An Introduction to Kolmogorov Complexity and Its Applications
638 Citations1993Ming Li, Paul Vitányi
Journal of the Royal Statistical Society Series A (General)General Irreducible Markov Chains and Non-Negative Operators.
613 Citations1985M. Bhaskara Rao, Esa Nummelin
ACM SIGACT NewsBook Review: An introduction to Kolmogorov Complexity and its Applications Second Edition, 1997 by Ming Li and Paul Vitanyi (Springer (Graduate Text Series))
585 Citations1997William Gasarch
The complexity of a string is defined as the shortest description of x, and a formal definition is given that is equivalent to the one in the book.
Journal of the American Statistical AssociationMinorization Conditions and Convergence Rates for Markov Chain Monte Carlo
463 Citations1995Jeffrey S. Rosenthal
Journal of the Royal Statistical Society Series B (Statistical Methodology)Stochastic Complexity
343 Citations1987J. Rissanen
Neural NetworksInformation geometry of the EM and em algorithms for neural networks
333 Citations1995Шун-ичи Амари
A unified information geometrical framework for studying stochastic models of neural networks, by focusing on the EM and em algorithms, and proves a condition that guarantees their equivalence.
IEEE Transactions on Information TheoryDensity estimation by stochastic complexity
115 Citations1992J. Rissanen, Terence P. Speed +1 more
Two theoresms are proved, which together extend the universal coding theorems to a large class of data generating densities and give an asymptotic upper bound for the code redundancy in the order of magnitude, achieved with a special predictive type of histogram estimator, which sharpens a related bound.
Journal of the Royal Statistical Society Series B (Statistical Methodology)On the Geometric Convergence of the Gibbs Sampler
112 Citations1994Gareth O. Roberts, Nicholas G. Polson
This paper investigates conditions under which the Gibbs sampler (Gelfand and Smith, 1990; Tanner and Wong, 1987; Geman and Geman, 1984) converges at a geometric rate, and gives results which establish uniform convergence under different sets of conditions on the underlying density.
Journal of the American Statistical AssociationMinorization Conditions and Convergence Rates for Markov Chain Monte Carlo
85 Citations1995Jeffrey S. Rosenthal
Conference on Learning TheoryA learning criterion for stochastic rules
85 Citations1990Kenji Yamanishi
A comparison of new and old algorithms for a mixture estimation problem
78 Citations1995David P. Helmbold, Yoram Singer +2 more
Statistics and ComputingAnalysis of the Gibbs sampler for a model related to James-Stein estimators
75 Citations1996Jeffrey S. Rosenthal
A hierarchical Bayes model which is related to the usual empirical Bayes formulation of James-Stein estimators is analysed, and it is proved that the Gibbs sampler will fail to converge, and the associated posterior distribution is non-normalizable.
Exploring Posterior Distributions Using Markov Chains
65 Citations1992Luke Tierney
Some preliminary efforts to use Markov chains to control dynamic graphics for exploring higher-dimensional posterior distributions are outlined, and some theoretical and practical issues in the use of these strategies are discussed.
Information and ComputationA Loss Bound Model for On-Line Stochastic Prediction Algorithms
15 Citations1995Kenji Yamanishi
It is proved that WA is optimal in the sense that the upper bound on the expected cumulative logarithmic loss for WA asymptotically matches Rissanen′s coding-theoretic lower bound.
Machine LearningProbably Almost Discriminative Learning
12 Citations1995Kenji Yamanishi
This paper demonstrates that the sample complexity bound for the MDL-based discrimination algorithm is essentially related to Barron and Cover's index of resolvability, and gives a new view at the relationship between the index of RESOLvability and theMDL principle from the PAD-learning viewpoint.
Randomized approximate aggregating strategies and their applications to prediction and discrimination
12 Citations1995Kenji Yamanishi
Methods of efficient approximation of Bayes methods (aggregating strategy) are introduced and their effectiveness in the on-line prediction and discrimination scenarios and the algorithms introduced use randomizing techniques based on the Markov chain Monte Carlo method are demonstrated.