Small is Beautiful: A Brute-Force Approach to Learning First-Order Formulas

Steven Minton, Ian UnderwoodAAAI 1994

In the landscape of machine learning, brute-force search is often dismissed as a "naive" baseline to be superseded by sophisticated heuristics. However, in their seminal 1994 paper Small is Beautiful, Steven Minton and Ian Underwood challenge this notion. They argue that for learning first-order logic formulas, a systematic, exhaustive search—prioritizing the smallest formulas first—is not only viable but highly effective. Their system, MULTI-TAC, demonstrates that discovering simple, accurate rules can significantly enhance the performance of automated problem solvers.

The Challenge of Logic Learning

Developing automated systems for combinatorial optimization (e.g., scheduling, bin packing) requires two critical components: axioms that define the problem constraints and search control rules that guide the solver toward a solution efficiently.

Historically, these have been hand-coded by experts. However, humans are prone to overlooking subtle constraints or creating overly complex rules that introduce significant computational overhead. While many machine learning approaches prioritize accuracy, they often neglect the utility of the learned rules. A rule that is 100% accurate but takes seconds to evaluate at every node of a search tree is practically useless. The core challenge is finding a learning bias that balances correctness with extreme computational efficiency.

Methodology: Brute-Force, Smallest-First (BFSF)

The authors propose a Brute-Force, Smallest-First (BFSF) approach integrated into the MULTI-TAC system. The methodology consists of several key stages:

  1. Systematic Enumeration: Using a recursive grammar, the system generates every possible "irreducible" well-formed formula in first-order logic. It begins with the smallest possible formulas (single atomic formulas) and incrementally increases the size.
  2. Axiom Induction: To learn domain axioms, candidate formulas are tested against positive problem instances. Formulas that hold true across all examples are retained. A theorem prover is then employed to prune redundant formulas—for instance, if Rule A is a logical consequence of Rule B, Rule A is discarded.
  3. Search Control Induction: The system generates "preference rules" (e.g., "prioritize the variable with the fewest remaining values") to optimize solver speed. It evaluates these rules at various choice points during problem-solving to identify which ones most effectively pinpoint the "most-constrained" variable.
Table showing the number of formulas generated at different sizes (s) and the final number of rules kept after pruning.

As shown in the table above, while the number of candidate formulas grows exponentially with size ($s$), the final set of selected rules remains remarkably small, highlighting the effectiveness of the pruning process.

Experimental Evaluation

The BFSF approach was evaluated on six classic NP-complete combinatorial problems from the Garey & Johnson (1979) benchmark: Bin Packing, Dominating Set, Graph 3-Colorability, Not-All-Equal 3-SAT, Partition-Into-Triangles, and Minimum Maximal Matching (MMM). Training typically involved small sets of 15-30 instances.

Key Results and Performance

The empirical results demonstrated several surprising advantages of the BFSF approach:

  • Outperforming Human Experts: In the Minimum Maximal Matching task, the axioms generated by MULTI-TAC were more concise and complete than those authored by human volunteers, including the researchers themselves.
  • Superiority over Analytic Learning: When compared to more complex "analytic" learning methods, the inductive BFSF approach produced superior programs for four out of the six benchmark problems.
Comparison of Analytic Learning versus Inductive Learning (BFSF) across benchmark problems, showing solved instances, execution time, and rule counts.

The data in the table above illustrates that Inductive Learning often solves a comparable or greater number of instances than Analytic Learning, frequently with better or competitive execution times. Notably, for problems like Bin Packing and Dominating Set, the inductive approach significantly outperformed the analytic alternative in terms of instances solved.

Insights and Implications

The success of Small is Beautiful rests on several key insights:

  • Simplicity as Utility: In logic-based reasoning, smaller formulas are inherently more efficient. They result in fewer clauses for theorem provers, reducing the branching factor and accelerating the solver.
  • The "Drunkard’s Search" Justification: While not all useful formulas are small, human-designed problem languages are typically structured to be concise. Therefore, the most impactful axioms and rules are likely expressible through simple formulas.
  • Data Efficiency: Valid formulas often stabilize after seeing only a few examples. While theoretical frameworks like PAC learning suggest a need for large datasets, in practice, most random formulas are quickly falsified, allowing for rapid filtering.

Limitations and Future Directions

Despite its success, the BFSF approach faces an "exponential wall"; the number of formulas grows so rapidly that size 5 is currently the practical limit. Furthermore, the generator often produces "nonsensical" subformulas. Future work suggests interleaving generation and testing to prune the search space earlier. Additionally, the authors highlight the potential for "predicate invention"—allowing the system to create new vocabulary to represent complex constraints more simply.

In conclusion, the MULTI-TAC system proves that for certain domains, a "dumb" brute-force search, when guided by a strong bias toward simplicity, can outperform both human experts and more sophisticated learning algorithms.

Summary updated

BibTeX
@inproceedings{minton1994small,
  author = {Steven Minton and Ian Underwood},
  title = {{Small is Beautiful: A Brute-Force Approach to Learning First-Order Formulas}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure