Minimum Description Length prevents overfitting in noisy data.
problem Learning from noisy data with overfitting risk.
method Minimum Description Length learning rule with tempered guarantees.
result Tempered agnostic finite sample learning guarantees and asymptotic behavior characterization.
Study shows LLC correlates with neural network compressibility.
problem Evaluating limits of neural network compression.
method Extended minimum description length principle using singular learning theory.
result Complexity estimates based on LLC are linearly correlated with compressibility.
This research simplifies PCA model selection using MDL principle.
problem Choosing the right number of principal components in PCA.
method Reduces NML problems to lower-dimension problems and bounds PCA NML.
result Bound the NML of PCA by terms of the NML of linear regression.
This paper proposes a new method for inferring the latent dimension of linear dynamical systems.
problem Manual specification of latent dimension is impractical and leads to model limitations.
method The paper introduces a minimum description length criterion to infer latent dimension.
result The proposed method effectively infers latent dimension and improves model performance.
FIA misleads in small samples; lower-bound sample size N′ prevents errors.
problem Misleading model selection by FIA in small samples.
method Proposes a lower-bound sample size N′ to prevent FIA's misleadingness. result Prevents inversion of model complexity ranks in FIA.
Method estimates dataset utility via minimal program length proxy.
problem Determining if data labels are generated by useful subroutines.
method Rissanen Data Analysis (RDA) estimates minimum description length (MDL) as a proxy.
result Method reveals dataset characteristics and utility in various NLP settings.
Neural networks generalize on simple data generated by a programming language.
problem Generalization of neural networks on low complexity data.
method Minimum description length (MDL) approach for feedforward neural networks.
result MDL feedforward neural networks generalize with high probability on simple data.
A comprehensive guide to MDL principle, a statistical inference theory.
problem Statistical inference and pattern recognition.
method MDL principle, model selection, hypothesis testing, averaging.
result Unified perspective on various statistical methods.
New method improves bivariate causal discovery by accurately estimating cause variable complexity.
problem Improper estimation of cause variable complexity in current MDL-based methods.
method Rate-distortion MDL (RDMDL) using information dimension for cause variable complexity estimation.
result RDMDL achieves competitive performance on Tübingen dataset.
A new objective function for NMF reduces model complexity and improves accuracy.
problem NMF's error-based objective function can lead to overly complex models.
method MDL-NMF uses minimum description length to balance model complexity and accuracy.
result MDL-NMF outperforms traditional NMF on various datasets.
We tackle the problem of penalty selection of regularization on the basis of the minimum description length (MDL) principle. In particular, we consider that the design space of the penalty function is high-dimensional. In this situation, the luckiness-normalized-maximum-likelihood(LNML)-minimization approach is favorab…
The paper introduces DDL, a method for predicting generalization error from training data alone.
problem Model selection and hyperparameter tuning in machine learning.
method Differential Description Length (DDL) method for predicting generalization error.
result DDL leads to smaller generalization error than cross-validation and traditional MDL and Bayes methods.
Paper establishes generalization bounds for representation learning using Minimum Description Length.
problem Designing efficient statistical supervised learning algorithms that generalize well to unseen data.
method Developed a compressibility framework using Minimum Description Length (MDL) to derive upper bounds on generalization error.
result Established the first theoretical generalization bounds for Information Bottleneck type encoders and representation learning.
Paper introduces Ddim, a new measure of model complexity, for MDL-based learning and change detection.
problem Characterizing the complexity of probabilistic models for efficient learning and change detection.
method Introduces descriptive dimension (Ddim) as a measure of model complexity. Derives convergence rates and error probabilities for MDL-based learning and change detection.
result Ddim characterizes the performance of MDL-based learning and change detection.
Kernel networks' stability edge linked to Fisher Information singularity.
problem Understanding the stability edge in high-capacity kernel Hopfield networks.
method Statistical manifold analysis and Riemannian geometry.
result The Ridge of Optimization corresponds to the Edge of Stability, revealing a dual equilibrium.
A new method avoids overfitting in network reconstruction by using the minimum description length principle.
problem Determining the optimal model complexity in network reconstruction to prevent overfitting.
method Hierarchical Bayesian inference and weight quantization based on the minimum description length principle.
result The method yields increased accuracy in reconstructing both artificial and empirical networks.
We analyze differences between two information-theoretically motivated approaches to statistical inference and model selection: the Minimum Description Length (MDL) principle, and the Minimum Message Length (MML) principle. Based on this analysis, we present two revised versions of MML: a pointwise estimator which give…
New metrics improve learning of Gaussian networks.
problem Lack of suitable metrics for continuous Bayesian network learning.
method Introduce three-part minimum description length and renormalized normalized maximum likelihood metrics.
result Proposed metrics outperform BIC/AIC metrics in accuracy and convergence.
Fast, fully-automated histograms for large data sets.
problem Efficiently constructing histograms for large-scale data.
method G-Enum histograms using Minimum Description Length (MDL) principle for model selection and a greedy search heuristic.
result Construct histograms in linearithmic time, significantly faster than previous methods.
New architectures improve KANs, making them more interpretable and accurate.
problem Improving Kolmogorov-Arnold networks while maintaining interpretability.
method Overprovisioned architectures combined with sparsification, deep supervision, and depth selection, optimized with a minimum description length objective.
result Combining sparsification with depth selection achieves competitive or superior accuracy while discovering smaller models.
Robust low-rank matrix estimation is a topic of increasing interest, with promising applications in a variety of fields, from computer vision to data mining and recommender systems. Recent theoretical results establish the ability of such data models to recover the true underlying low-rank matrix when a large portion o…
The paper explores how smaller data sets can lead to better model selection decisions.
problem Model selection in small data regimes.
method Empirical study of generalization performance with varying training set sizes.
result Training on smaller subsets of data can lead to more reliable model selection decisions.
Bayesian networks are convenient graphical expressions for high dimensional probability distributions representing complex relationships between a large number of random variables. They have been employed extensively in areas such as bioinformatics, artificial intelligence, diagnosis, and risk management. The recovery …
S2KAN integrates symbolic primitives into neural network activations for improved interpretability.
problem Training activations in KANs often lack symbolic fidelity, leading to unintelligible models.
method Softly Symbolified Kolmogorov-Arnold Networks (S2KAN) integrates symbolic primitives into training with learnable gates and a Minimum Description Length objective.
result S2KAN discovers interpretable forms when symbolic terms suffice, gracefully degrading to dense splines when necessary.
VASE learns disentangled representations that generalize across domains.
problem Learning new knowledge from diverse data sources while preserving old knowledge.
method VASE uses shared embeddings and Minimum Description Length principle to disentangle representations.
result VASE achieves better cross-domain inference and disentangled representations.
A new complexity measure MDL-COMP for overparameterized models improves generalization performance.
problem Complexity measures based on Rissanen's MDL principle are not well-suited for overparameterized models.
method Developed a novel MDL-based complexity (MDL-COMP) for overparameterized models, defined via an optimality criterion over Ridge estimators.
result MDL-COMP scales linearly with d when d<n, but exponentially smaller for d>n; it upper bounds in-sample MSE. The Minimum Description Length (MDL) principle states that the optimal model for a given data set is that which compresses it best. Due to practial limitations the model can be restricted to a class such as linear regression models, which we address in this study. As in other formulations such as the LASSO and forward …
Study improves neural network performance in sequential learning for image classification.
problem Improving neural network performance in sequential learning for image classification.
method Evaluation of approaches for computing prequential description lengths, proposing forward-calibration and replay-streams.
result Improved description lengths for image classification datasets, outperforming previous results.
New model explains how concepts grow based on experience.
problem Existing models assume fixed representation; new model allows for growth.
method Geometric framework with MDL criterion for basis extension.
result Conceptual growth is selective and conservative, exposing or amplifying residual error.
This study explores how feature graphs enhance GNNs' performance in modeling interactions.
problem Improving GNNs' ability to model feature interactions effectively.
method Investigates feature graphs and their importance in GNNs, using experiments and theoretical support.
result Edges between interacting features are crucial for GNNs, while non-interaction edges can degrade performance.
LMs perform poorly in true few-shot learning without held-out examples.
problem Evaluating few-shot performance of language models without access to held-out examples.
method Evaluated two model selection criteria (cross-validation and minimum description length) for choosing LM prompts and hyperparameters in true few-shot learning.
result Selection criteria often prefer models that perform worse than random selection, suggesting overestimation of few-shot ability.
Bayesian methods detect clusters in noisy data more reliably.
problem Noisy data distorts traditional clustering methods, leading to unreliable results.
method Bayesian community detection using Minimum Description Length principle.
result Bayesian methods identify more robust clusters in noisy data.
Tree Index evaluates cluster quality by creating decision trees from data.
problem Evaluating the quality of cluster results from various techniques.
method Tree Index creates a decision tree from clustered data, combining entropy and depth of leaves.
result Tree Index discriminates between sensible and non-sensible clusters on brain dataset.
Classy learns interpretable probabilistic rule lists for multiclass classification.
problem Creating interpretable multiclass classifiers that are both accurate and understandable.
method Probabilistic rule lists and minimum description length (MDL) principle for model selection.
result Classy selects small probabilistic rule lists that outperform state-of-the-art classifiers in terms of predictive performance and interpretability.
New methods evaluate data representations by complexity of low-loss predictor learning.
problem Evaluating quality of data representations for downstream tasks.
method Surplus Description Length (SDL) and ε Sample Complexity (εSC) methods.
result Methods measure the information needed to approximate optimal predictor up to specified tolerance.
The ropelength problem asks for the minimum-length configuration of a knotted diameter-one tube embedded in Euclidean three-space. The core curve of such a tube is called a tight knot, and its length is a knot invariant measuring complexity. In terms of the core curve, the thickness constraint has two parts: an upper b…
We analyze MDL for binary classification, quantifying overfitting and underfitting.
problem Understanding the trade-off between underfitting and overfitting in MDL for binary classification.
method Complete characterization of the regularization curve for MDL, extending previous work to all λ. result Precise quantitative description of the worst case limiting error as a function of λ and noise level. The minimum description length (MDL) principle in supervised learning is studied. One of the most important theories for the MDL principle is Barron and Cover's theory (BC theory), which gives a mathematical justification of the MDL principle. The original BC theory, however, can be applied to supervised learning only …
Knots are commonly found in molecular chains such as DNA and proteins, and they have been considered to be useful models for structural analysis of these molecules. One interested quantity is the minimum number of monomers necessary to realize a molecular knot. The minimum lattice length $\mbox{Len}(K)$ of a knot K i…
Investigates the long-only minimum variance portfolio in factor models.
problem Understanding the long-only minimum variance portfolio in factor models.
method Investigates the long-only global minimum variance portfolio in a factor model of returns, providing explicit and geometric descriptions for different factor models.
result Provides rigorous and explicit descriptions of the long-only solution in terms of covariance matrix parameters and geometric descriptions for multiple factors.
We introduce a deep, generative autoencoder capable of learning hierarchies of distributed representations from data. Successive deep stochastic hidden layers are equipped with autoregressive connections, which enable the model to be sampled from quickly and exactly via ancestral sampling. We derive an efficient approx…
The minimum number of self-intersection points for members of a free homotopy class of curves on the punctured torus is bounded above in terms of the number L of letters required for a minimal description of the class in terms of the generators of the fundamental group and their inverses: it is less than or equal to (L…
We show that the minimum of asymptotic translation lengths of all point-pushing pseudo-Anosov maps on any one punctured Riemann surface is one.
Method generates adversarial examples to improve classifier robustness.
problem Addressing adversarial examples in machine learning.
method MDL principle for generating adversarial examples.
result Evasion rate of 78.24% for adversarial examples compared to 8.16% for original malware.
Geometrically analyzes why deep neural networks perform well despite high parameter complexity.
problem Explains the good performance of deep neural networks with high parameter spaces.
method Introduces geometric information-theoretic approach using Fisher information matrix and singular semi-Riemannian geometry.
result Derives model complexity measures explaining the performance of deep neural networks.
New method learns convolution-like structures from scratch.
problem Learning convolution-like structures from data.
method Minimum description length principle and β-LASSO algorithm. result Learned architectures achieve state-of-the-art accuracies.
Data discretization is an important step in the process of machine learning, since it is easier for classifiers to deal with discrete attributes rather than continuous attributes. Over the years, several methods of performing discretization such as Boolean Reasoning, Equal Frequency Binning, Entropy have been proposed,…
This paper extends the work in [Suzuki, 1996] and presents an efficient depth-first branch-and-bound algorithm for learning Bayesian network structures, based on the minimum description length (MDL) principle, for a given (consistent) variable ordering. The algorithm exhaustively searches through all network structures…