Analytical Inductive Programming as a Cognitive Rule Acquisition Devise

One of the most admirable characteristic of the human cognitive system is its ability to extract generalized rules covering regularities from example experience presented by or experienced from the environment. Humans’ problem solving, reasoning and verbal behavior often shows a high degree of systematicity and productivity which can best be characterized by a competence level reflected by a set of recursive rules. While we assume that such rules are different for different domains, we believe that there exists a general mechanism to extract such rules from only positive examples from the environment. Our system Igor2 is an analytical approach to inductive programming which induces recursive rules by generalizing over regularities in a small set of positive input/output examples. We applied Igor2 to typical examples from cognitive domains and can show that the Igor2 mechanism is able to learn the rules which can best describe systematic and productive behavior in such domains. Introduction Research in inductive programming is concerned with the design of algorithms for synthesis of recursive programs from incomplete specifications such as input/output examples of the desired program behavior, possibly together with a set of constraints about size or time complexity (Biermann, Guiho, & Kodratoff 1984; Flener 1995). In general, there are two distinct approaches to inductive programming – search-based generate-and-test algorithms (Olsson 1995; Quinlan & Cameron-Jones 1995) and data-driven analytical algorithms (Summers 1977; Kitzelmann & Schmid 2006). In the first case, given some language restriction, hypothetical programs are generated, tested against the specification and modified until they meet some given criteria. In the second case, regularities in the input/output examples are identified and a generalized structure is built over the examples. While searchbased approaches – in principle – can generate each possible program and therefore might be able to find the ∗Research was supported by the German Research Community (DFG), grant SCHM 1239/6-1. Copyright c © 2008, The Second Conference on Artificial General Intelligence (AGI-09.org). All rights reserved. desired one given enough time, analytical approaches have a more restricted language bias. The advantage of analytical inductive programming is that programs are synthesized very fast, that the programs are guaranteed to be correct for all input/output examples and fulfill further characteristics such as guaranteed termination and being minimal generalizations over the examples. The main goal of inductive programming research is to provide assistance systems for programmers or to support end-user programming (Flener & Partridge 2001). From a broader perspective, analytical inductive programming provides algorithms for extracting generalized sets of recursive rules from small sets of positive examples of some behavior. Such algorithms can therefore be applied not only to input/output examples describing the behavior of some program but to arbitrary expressions. Taking this standpoint, analytical inductive programming provides a general device for the acquisition of generalized rules in all such domains where it is natural that people are typically exposed to only positive examples. This is, for example, the case in learning correct grammatical constructions where a child would never get explicitly exposed to scrambled sentences (such as house a is this). In the sixties, Chomsky proposed that the human mind possesses a language acquisition device (LAD) which allows us to extract grammar rules from the language experience we are exposed to (Chomsky 1959; 1965). Input to this device are the linguistic experiences of a child, output is a grammar reflecting the linguistic competence. The concept of an LAD can be seen as a special case of a general cognitive rule acquisition device. Unfortunately, this idea became quite unpopular (Levelt 1976): One reason is, that only performance and not competence is empirically testable and therefore the idea was only of limited interest to psycho-linguists. Second, Chomsky (1959) argued that there “is little point in speculating about the process of acquisition without much better understanding of what is acquired” and therefore linguistic research focussed on search for a universal grammar. Third, the LAD is concerned with learning and learning research was predominantly associated with Skinner’s reinforcement learning approach which clearly is unsuitable as a lanAGI-2009 Published by Atlantis Press, © the authors