Binarized neural networks converge toward algorithmic simplicity: empirical support for the learning-as-compression...

Area of Science:

• Machine Learning
• Information Theory
• Computational Complexity

Background:

• Neural network complexity is a key challenge impacting generalization and capacity.
• Current entropy-based metrics often miss underlying algorithmic structures in network learning.

Purpose of the Study:

• To explore algorithmic information theory for characterizing neural network learning dynamics.
• To propose a novel approach using algorithmic complexity to understand network structure and training.

Main Methods:

• Utilized binarized neural networks (BNNs) as a model system.
• Applied the Block Decomposition Method (BDM), an approximation of algorithmic complexity based on algorithmic probability (AP).
• Compared BDM's tracking of training dynamics against traditional entropy-based measures.

Main Results:

• Algorithmic complexity, via BDM, more accurately reflects structural changes during BNN training than entropy.
• BDM showed stronger correlations with training loss across diverse architectures and datasets.
• Training dynamics in BNNs were characterized as a form of algorithmic compression.

Conclusions:

• Algorithmic information theory provides a principled framework for estimating learning progression in neural networks.
• This approach offers a new perspective on complexity-aware learning and regularization.
• The findings suggest that neural network training involves the internalization of structured regularities.