Speedup & Deductive Learning

notes by: Eyal Amir April 9, 1996

1 Introduction

Definition 1.1 Speedup Learning is a learning pattern in which the learner has no inputs besides its own doings, and has a way of increasing its efficiency by evaluating its own doings and learning from those evaluations.

• Ronny: This is a deductive method.

• Pat: There are many inductive processes that hold that property.

• Lise: Talk about Deductive Learning and the issues under the “speedup learning” bullet.

• Nils: Dietterich is the one that tokened speed-up learning, and he actually refered to Deductive Learning.

So, I will talk on:

• EBL

• Chunking

• Macrops

• Deductive Learning

2 EBL - Explanation Based Learning

• Caching succeeds only when exactly the same problem is encountered.

• EBL takes on several forms:

– Generalized Caching(my terminology) is Caching of generalized examples. These Generalizations may contain pattern variables, and tests for pattern applicability. To use such a pair of problem-solution, one should match the given problem to the cached ones, check for applicability, and then apply the matching to the solution. To obtain a new problem-solution pair, one should solve the problem, analyze the solution to determine what problems can be solved that way, and construct the two patterns: The problems, and the solutions.

– The Usual Approach takes the previously mentioned patterns and constructs a Macro, or a Rule, that is incorporated in the Rules DB of the system.

– The Explanation in EBL stands for ’given a rule, try to explain it’. Then, the system should do the same process of incorporating the new rule. Example: LEAP (Mitchell et al 85’) for VLSI design. Dietterich: Given

∗ a domain theory,

∗ a target concept,

∗ a training example,

∗ a pruning policy or an operationality criterion

find an operational sufficient condition for the target concept^{1}.

– mEBL uses multiple training examples to generalize a rule by finding the subtree shared by all the proof of the individual examples.

– Ronny: Another approach to EBL generates heuristics for problem solving (this is highly speedup learning).

• EBL is integrated in the meta-level of SOAR (Laird et al 82-96’), and Prodigy (Minton 88’) which are problem solving architechtures^{2}.

SOAR: GOAL ⟹ PROBLEM SPACE ⟹ STATE ⟹ OPERATOR

Both SOAR and Prodigy work with concepts of Good and Bad operators, and not a Best operator, because finding the best is very proof-expensive.

• Keep in Mind

– The vocabulary of the domain theory must be chosen carefully, or the EBL might degrade into Caching.

– The quality of the explanation affects the quality of the rule learned.

– Post acquisition optimization of the rule can improve the quality of the rule (e.g., in SOAR learned rules are optimized by ordering the conditions for each rule for efficient testing. In Prodigy: (a) partial evaluation, (b) condition ordering, (c) simplification via domain theorems).

– Selective EBL - taking only beneficial rules.

– Meta-level are significantly more effective than Base-level macros.

1notice that this is definitely not a Speedup Learning 2I found the Dietterich article most enlighting in terms of explaining what SOAR is, and how it works in general

• Recursive rules can be learned by specifying the proof tree with the n specified explicitly^{3}^{4}.

• Imperfect Domain Theories

– The domain theory is incomplete: one uses abduction theory completion - trying to guess the ’holes’ in the theory from the requested outcome. It is implemented by a parser that constructs the rule needed for the ’hole’ in the proof. Example: ODYSSEUS (Wilkins 88’) for learning diagnostic interviewing.

– The domain theory produces incorrect explanations: one uses Induction Over Explanations (Dietterich & Flann 88’), which takes a couple of examples, proves them all, and generalizes the proofs to produce a general explanation to them all.

2.1 Applications of EBL

Besides the applications mentioned so far (SOAR, Prodigy, ODYSSEUS, LEAP), Nilsson gives two applications of EBL: Macro-Operators in automatic planning and Learning how to control Search. The first is discussed in a separate section below, and the second is illustrated by the examples of SOAR and Prodigy (given below).

3 MACROPs

Macro Operators are acquired when a sequence of actions/productions is viewed as useful. The macro is then generalized, replacing constants with variables, and testing for preconditions on the variables. It is mostly implemented using EBL (according to Nilsson).

MACROPs were used in STRIPS.

4 Chunking

Chunking is similar to Macro-operators. When a useful sequence of production firing is detected, a chunk is created, which is essentialy a large production that does the work of an entire sequence of smaller ones. Chunks are generalized before they are stored.

• Chunking can be used to learn general search control knowledge in addition to operator sequences.

3Dietterich does not deal with ’how will the system produce such a proof’, but there are ways to enable such recursive proofs in a theorem prover

4notice that EBL is presented again as a tool to ’generalize from the proof’ where the proof can be given as input. Thus, it is not necessarily Speedup Learning, in the form mentioned above

• It is inadequate for duplicating the contents of large, directly-computed macro-operator tables.

5 SOAR

SOAR is a general-purpose problem solver that searches a problem space of states by applying operators until some goal is achieved.

5.1 meta-level

At the meta-level, SOAR confronts four basic decisions:

• what goal should be processed next.

• what problem space should be searched to achieve that goal.

• what state in that problem space should be explored next.

• what operator (i.e. rule) should be applied to the selected state.

Like most meta-level problem solvers, SOAR operates in a continuous twophase loop called the decision cycle. Each time through the loop, SOAR confronts one of these four meta-level problems and selects a solution. Then it executes the solution (e.g., applies the chosen operator) at the base level.

To solve the four meta-level problems, SOAR applies a collevtion of control rules that identify and rank candidates. These rules and the learning at this meta-level is dealt with EBL (mentioned above).

5.2 base-level

SOAR uses Chunking for its base-level learning. It is based on the hypothesis that chunking is a universal learning method (i.e., it can account for all types of learning in intelligent systems).

6 Prodigy

Prodigy is a STRIPS-like system that solves planning problems in the blocksworld, in a simple mobile-robot world, and in job-shop scheduling.

It has a domain theory involving both the domain of the problem and a simple (meta) theory about planning. Its meta theory includes statements about whether a control choice about a subgoal to work on, an operator to apply, etc. either succeeds or fails. After producing a plan, it analyzes its successful and its unsuccessful choices and attempts to explain them in terms of its domain theory. Using EBL-like process, it is then able to produce useful control rules.

Prodigy keeps statistics on how often these learned rules are used, their saving, and their cost of application, saving only those whose utility is high (Minton 88,90).

7 Conclusions

Langley: EBL and especially Chunking and MACROPs turn the depth problem into a breadth problem Dietterich/Ronny: EBL converts a problem-solving search into a pattern-matching search. Nilsson: In EBL we specialize parts of a domain theory to explain a particular example, then we generalize the explanation to produce another element of the domain theory that will be useful on similar example.

7.1 Analytic/Deductive Learning

7.1.1 Nilsson’s view

Deductive methods are methods in which the conclusions logically follow from a set of input facts, if the system is sound. Nils furthermore says that Nonmonotonic Reasoning systems are thus Inductive (the classifier’s conclusion does not logically follow from the training set/input facts).

One should notice that although the actual outcome of Deductive Learning is (hopefully) speeding up the system, there are cases (e.g., chess playing) where this speed-up is the whole thing. There is a theoretical best-strategy, but it will take too much time to calculate. speeding-up actually enables us to do things we could’nt do before.

7.1.2 Ronny’s view

Ronny defines Deductive Learning as transforming existing domain knowledge into a more useful form. On the other hand, he counts Learning by taking advice as a deductive learning method (e.g., McCarthy proposed Advice Taker, TEIRESIAS (Davis 76), FOO (Mostow 83)). He therefore concludes that all deductive methods are meant at efficiency improvement (and it is therefore a subset of speedup learning methods).

He counts the following as deductive:

1. Compiling Explanations into rules (e.g., EBL).

2. Learning Macro Operators.

3. Learning Preference Rules for problem solving.

References

[Kohavi 91] Ronny Kohavi’s summary on Learning (Note #19).

[Dietterich 90] Thomas G. Dietterich, Machine Learning, Annu. Rev. Comput. Sci. 1990. 4:255-306.

[Nilsson 96] Nils Nilsson, Explanation-Based Leaning, in Introduction to Machine Learning, in preparation.

This is /u/eyal/ongo/quals/deductive learning.tex.