An Analytic Learning System for Specializing Heuristics

Abstract

This paper describes how meta-level theories are used for analytic learning in Multi-tac. Multi-tac operationalizes generic heuristics for constraint-satisfaction problems, in order to create programs that are tailored to specific problems. For each of its generic heuristics, Multi-tac has a meta-theory specifically designed for operationalizing that heuristic. We present examples of the specialization process and discuss how the theories influence the tractability of the learning process. We also describe an empirical study showing that the specialized programs produced by Multi-tac compare favorably to hand-coded programs. 1 Introduction Multi-tac (Multi-Tactic Analytic Compiler) is a learning system for constraint-satisfaction problems (CSPs). The system operationalizes generic heuristics [ 11 ] , producing problem-specific versions of these heuristics, and then attempts to find the most useful combination of these heuristics on a set of training problems. This paper focuses on ...