Introduction
In the early 1990s, machine learning research was largely bifurcated into two distinct paradigms: empirical (inductive) learning and analytic (deductive) learning. Empirical methods, such as FOIL, focused on deriving patterns from large sets of examples, which were often prone to noise. Conversely, analytic methods relied on pre-existing, correct theories to guide learning.
However, real-world applications rarely fit perfectly into either category. Experts often provide "approximate theories"—rules of thumb that are generally correct but incomplete or slightly flawed. Simultaneously, training data is frequently corrupted by noise. This paper introduces LATEX, a system designed to bridge this gap by effectively balancing confidence between a prior theory and noisy empirical data.
The LATEX Methodology
The core innovation of LATEX is an extension of the Minimum Description Length (MDL) principle. Traditional MDL posits that the best model is the one that minimizes the sum of the model's complexity and the length of the data encoded by that model.
LATEX shifts this focus from absolute complexity to refinement complexity. The system's cost function minimizes the sum of:
- Length(Refinement): The number of bits required to describe the specific changes (adding or deleting literals or clauses) made to the initial approximate theory.
- Length(Examples): The number of bits required to encode the training examples using the newly refined theory.
By treating the transformation from the old theory to the new one as the primary measure of complexity, LATEX is naturally biased toward staying "close" to prior knowledge unless the empirical evidence for a change is overwhelming. This "unified currency" of bit length allows the system to automatically balance theory and data without requiring manual hyperparameter tuning.
The Algorithm
LATEX operates on first-order Horn clauses and employs a greedy search strategy. In each iteration, it evaluates all possible refinements and selects the one providing the "maximal positive compression." The process terminates when no further refinement can reduce the total description length. Finally, a post-processing step prunes any clauses that cover more negative examples than positive ones, further mitigating the impact of noise.
Experimental Evaluation
The authors evaluated LATEX using the King-Rook-King (KRK) chess endgame classification domain. To simulate real-world conditions, they generated five "approximate" theories by intentionally corrupting a correct theory, resulting in an average initial accuracy of only 45.79%. They also introduced a 10% classification noise rate (flipping 10% of the labels).
Key Results
As shown in the figure above, LATEX with an initial theory (LATEX-Th) significantly outperformed both FOIL and a version of LATEX starting from scratch (LATEX-NoTh). With 60 training examples and 10% noise, LATEX-Th achieved approximately 95% accuracy, while LATEX-NoTh reached ~90% and FOIL lagged at ~85%.
These results demonstrate that even a highly flawed initial theory (~46% accuracy) provides a powerful "hint" that helps the learner navigate noisy data more effectively than inductive methods alone. LATEX avoids the common pitfall of inductive systems—overfitting to noise by creating overly complex clauses—because the MDL cost of such complexity eventually outweighs the gain in data compression.
Conclusion and Future Work
LATEX successfully demonstrates that the MDL principle can be adapted to integrate prior knowledge with noisy empirical evidence. By focusing on the complexity of theory refinement rather than absolute theory length, the system achieves superior robustness and accuracy.
Future research directions include moving beyond greedy search to avoid local optima, expanding the set of refinement operators (e.g., variable renaming), and validating the system on more complex, non-synthetic real-world datasets involving attribute noise.
Summary updated