LEARNING TO IMPROVE REASONING

Most people consider learning to be a critical component of intelligence. Machine learning— the field that aims at designing algorithms that can, over time, measurably improve their performance on a well defined task—is crucial to the development of intelligent systems. In recent years, machine learning has made great strides in maturing as a cohesive research topic and producing real-world applications, but most progress has been in the sub-topics of classification and reactive control. However, machine learning also aims to contribute in more complex tasks that involve multi-step reasoning and inference. The multi-step reasoning systems are designed to address problems characterized by large search spaces making it all but impossible to compute solutions through an uninformed brute-force search and forcing the incorporation of domain-specific heuristic information (Simon and Newell 1958) into search. However, manually acquiring such heuristics from domain experts, incorporating them into problem solving algorithm, and revising them when needed is a challenging task requiring significant investment of time and effort by domain experts and knowledge engineers. Learning to improve reasoning algorithms attempt to automate part/all of this process and eliminate the need for knowledge engineers. Given initial knowledge elements for a particular domain and a performance system that can compose these elements dynamically to solve problems, these learning algorithms find new or revised knowledge elements that improve system performance on novel problems (Langley 2004). Even though much early work in machine learning (Winston 1970; Fikes, Hart, and Nilsson 1972; Lenat 1977; deJong 1981; Mitchell, Utgoff, and Benerji 1983; Langley, Simon, Bradshaw, and Zytkow 1987; Minton 1988) aimed to improve the performance of such multi-step reasoning systems, most recent work focuses on performance tasks that involve one-step decisions for classification or regression and utilize simple reactive control for acting in the world. Recently, there has been a resurgence of interest in the area of learning to improve multistep reasoning. Pat Langley and Seth Rogers successfully organized a symposium at Stanford on March 21–22, 2004 to encourage this trend and to make researchers aware of each other’s work. Many contributors to this special issue participated in that workshop. The seven articles included here use different learning techniques but all aim to improve the performance of a reasoning system capable of performing complex tasks. “Learning to Support Constraint Programmers,” presents the Adaptive Constraint Engine (ACE) to automatically tune a constraint satisfaction (CSP) solver to a target class of constraint satisfaction problems. ACE is based on heuristic search (Epstein, Wallace, and Freuder 2005). Each possible “search action” is described by a set of human-provided features (or advisors). Learning is accomplished by generating examples of good and bad search decisions, based on solved problems, and then adjusting the feature weights to ensure that the subsequent decisions based on a weighted vote of the features would be able to discriminate between the good and bad decisions. The approach is evaluated on a number of problem classes showing some evidence for learning. Carchrae and Beck (2005) also utilize machine learning to provide meta-control over base algorithm selection. They target the scheduling domain, where different algorithms are effective on different problems. In their approach, each scheduler is run for some time on a new problem, and the one predicted to improve the result the most gets additional time to