Characterising the Inductive Biases of Neural Networks on Boolean Data

2025/05/29 by Chris Mingard, Mingard, Chris, Lukas Seier +9 · 1 citation
Computer Science · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Neural Networks and Applications

paper · pdf · doi:10.48550/arxiv.2505.24060

openalex publication_date 2025/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Deep neural networks are renowned for their ability to generalise well across diverse tasks, even when heavily overparameterized. Existing works offer only partial explanations (for example, the NTK-based task-model alignment explanation neglects feature learning). Here, we provide an end-to-end, analytically tractable case study that links a network's inductive prior, its training dynamics including feature learning, and its eventual generalisation. Specifically, we exploit the one-to-one correspondence between depth-2 discrete fully connected networks and disjunctive normal form (DNF) formulas by training on Boolean functions. Under a Monte Carlo learning algorithm, our model exhibits predictable training dynamics and the emergence of interpretable features. This framework allows us to trace, in detail, how inductive bias and feature formation drive generalisation.

Citations

• Uncovering Branch specialization in InceptionV1 using k sparse autoencoders
• Do We Always Need the Simplicity Bias? Looking for Optimal Inductive Biases in the Wild
• Learning High-Degree Parities: The Crucial Role of the Initialization
• How Feature Learning Can Improve Neural Scaling Laws
• Understanding Visual Feature Reliance through the Lens of Complexity
• Neural Redshift: Random Networks are not Random Functions
• Identifying Semantic Induction Heads to Understand In-Context Learning
• Deep neural networks have an inbuilt Occam's razor
• The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning
• SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics
• Progress measures for grokking via mechanistic interpretability
• Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions
• In-context Learning and Induction Heads
• Spectral Bias Outside the Training Set for Deep Networks in the Kernel Regime
• On the Spectral Bias of Convolutional Neural Tangent and Gaussian Process Kernels
• The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks
• Highly accurate protein structure prediction with AlphaFold
• Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation
• How rotational invariance of common kernels prevents generalization in high dimensions
• Generalization bounds for deep learning
• On the Similarity between the Laplace and Neural Tangent Kernels
• Language Models are Few-Shot Learners
• Frequency Bias in Neural Networks for Input of Non-Uniform Density
• Generic predictions of output probability based on complexities of\n inputs and outputs
• Neural networks are a priori biased towards Boolean functions with low entropy
• A Fine-Grained Spectral Perspective on Neural Networks
• SGD on Neural Networks Learns Functions of Increasing Complexity
• Why ResNet Works? Residuals Generalize
• Wide neural networks of any depth evolve as linear models under gradient descent *
• ImageNet-trained CNNs are biased towards texture; increasing shape bias improves accuracy and robustness
• On the Spectral Bias of Neural Networks
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Deep learning generalizes because the parameter-function map is biased towards simple functions
• Visualizing the Loss Landscape of Neural Nets
• A Bayesian Perspective on Generalization and Stochastic Gradient Descent
• Understanding deep learning requires rethinking generalization
• Analysis of Boolean Functions

Cited by

• Mitigating the Curse of Detail: Scaling Arguments for Feature Learning and Sample Complexity

Related

• Deep Learning is Not So Mysterious or Different
• Feature contamination: Neural networks learn uncorrelated features and fail to generalize
• Deep neural networks have an inbuilt Occam's razor
• Towards Exact Computation of Inductive Bias
• Data Distributional Properties As Inductive Bias for Systematic Generalization