Abstract
Domain knowledge can often be encoded in the structure of a network, such as convolutional layers for vision, which has been shown to increase generalization and decrease sample complexity, or the number of samples required for successful learning. In this study, we ask whether sample complexity can be reduced for systems where the structure of the domain is unknown beforehand, and the structure and parameters must both be learned from the data. We show that sample complexity reduction through learning structure is possible for at least two simple cases. In studying these cases, we also gain insight into how this might be done for more complex domains.
Introduction
Modern deep learning models are notoriously data-hungry, often requiring millions of samples to achieve high performance. In contrast, humans exhibit a remarkable ability to learn from very few examples. One common technique to bridge this gap is hard-coding domain knowledge into network architectures—for instance, using convolutional layers in computer vision to exploit spatial translation invariance. However, in many domains, such as robotics or sensor networks, the underlying structure is not known a priori. This study investigates whether a system can simultaneously learn both the structure and the parameters of a domain from a limited number of samples, thereby achieving "in-domain transfer."
Methods
The researchers explored two primary toy problems using synthetic datasets to isolate the effects of structural priors:
1. The Four Urns Problem
This problem involves four urns containing colored balls. While there are four urns, the system assumes a "weak prior": that there are only two underlying probability distributions (types) governing them. Some urns are sampled frequently (32.5% each), while Urn 1 is rare (2.5%). An Expectation-Maximization (EM) approach is used to cluster the urns into types while simultaneously estimating their color distributions.
2. The 12-bit Vector Problem
In this more complex scenario, the system receives 12-bit strings. The hidden structure consists of four independent groups of 3 bits each, with only two types of distributions for these groups. Crucially, the system does not know the bit groupings or their order. The authors employ an exhaustive search over all possible permutations and group-to-type assignments, using Dirichlet distributions to model uncertainty and maximize data likelihood.
Key Results
The experiments demonstrate that incorporating structural priors significantly reduces sample complexity.
In-Domain Transfer and Faster Convergence
In the Four Urns problem, the model utilizing the "two types" prior reached low error rates thousands of samples earlier than a model with a uniform prior. A critical observation was the phenomenon of "in-domain transfer": once the system correctly clustered the rare Urn 1 with a more frequent urn of the same type, it could leverage the abundant data from the common urn to make accurate predictions for the rare one.
The "Aha!" Moment in Structure Discovery
For the 12-bit vector problem, the system typically required approximately 125 samples to identify the hidden grouping of bits. Before this point, the error remained high as the model struggled with incorrect structural hypotheses. Once the correct structure was discovered—the "Aha!" moment—the learning curve converged rapidly, matching the performance of a model that had been provided with the correct structure from the start.
Discussion and Limitations
The results suggest that learning structure from scratch is possible and beneficial for reducing sample complexity. Successful transfer appears to rely on a measure of parameter certainty; Bayesian approaches like Dirichlet priors allow the model to "freeze" its understanding of common structures and use them as templates for rare ones.
However, significant challenges remain for scaling these methods. The exhaustive search used for the 12-bit problem is computationally intractable for larger domains, such as high-resolution images. Future work must focus on developing efficient heuristics and exploring "Minimum Description Length" principles to find the simplest structural explanations. Additionally, extending these concepts from discrete to continuous data domains is a vital next step for real-world applications.
Summary updated