Abstract
This paper introduces MDL/OC, an unsupervised learning algorithm that utilizes the Minimum Description Length (MDL) principle to extract human-interpretable concepts from relational datasets. By treating the discovery of features as a data compression problem, the system identifies latent categories like gender, nationality, and generational status within family tree data. While prioritizing interpretability over raw predictive accuracy, MDL/OC demonstrates that simplicity and orthogonality are key to robust feature discovery in symbolic domains.
Introduction
In the early 1990s, artificial intelligence research was characterized by a divide between connectionist models and symbolic learning. While neural networks were adept at searching large spaces for features, the resulting representations were often "black boxes." Conversely, symbolic algorithms provided interpretability but struggled to discover novel primitives. Mark Derthick’s MDL/OC (Minimum Description Length / Orthogonal Clustering) aims to bridge this gap by automatically discovering underlying concepts—such as "Gender" or "Age Group"—from relational facts without pre-existing labels.
The MDL/OC Methodology
The core of MDL/OC is the application of Occam’s Razor via the Minimum Description Length principle: the most effective theory is the one that describes the data using the fewest bits. The algorithm treats a dataset as a message to be transmitted to a receiver. By constructing a "theory" (a set of features), the algorithm can compress the data if the theory accurately captures regularities.
The discovery process involves assigning feature values to individuals. For instance, if assigning binary values (0 or 1) to individuals simplifies the compression of a "parent-of" relationship, the algorithm has effectively discovered a concept like Sex. Because finding the optimal set of features is computationally intractable, MDL/OC employs simulated annealing to navigate the search space and settle on a low-energy, short-description state.
Experimental Setup and Datasets
The primary benchmark for MDL/OC is Hinton’s Family Relations dataset, which consists of 112 triplets representing two family trees (English and Italian). The dataset includes 24 individuals and 12 predicates, such as "mother" and "uncle."
Beyond family trees, the algorithm was tested on the Cyc Knowledge Base (focusing on international trade partners) and the Soybean Disease Diagnosis dataset to evaluate its performance on noisy, real-world relational data and attribute-heavy non-relational data.
Key Results and Interpretability
MDL/OC demonstrated a remarkable ability to discover "intuitive" features. On the Family Relations problem, it consistently identified concepts that humans would label as Type (Person vs. Predicate), Sex, and Nationality. In 20 trials, 92% of the discovered features were recognizable human concepts.
Quantitatively, the algorithm achieved a total description length of 1260 bits, outperforming a hand-constructed "ideal" solution (1348 bits). However, a trade-off exists between interpretability and predictive power. While MDL/OC found cleaner, more readable features than connectionist models, its predictive accuracy (47-62%) was lower than supervised methods like FOIL (96%). This suggests that while MDL/OC is excellent for concept discovery, it may need to be paired with other logic-learning algorithms for high-accuracy prediction tasks.
Discussion and Limitations
The research highlights that learning is fundamentally a process of finding regularities for compression. By enforcing orthogonality—ensuring features are independent—the algorithm avoids redundancy and creates robust concepts suitable for analogical reasoning.
Despite its successes, MDL/OC faces challenges in scaling. The search process is computationally intensive, with CPU time increasing significantly as problem size grows. Additionally, real-world data from the Cyc KB proved more difficult to interpret than the clean family tree benchmarks, indicating that noise remains a hurdle for automated concept discovery. Future work may focus on integrating MDL/OC’s feature invention capabilities with supervised learners to combine the best of both worlds.
Summary updated