23-09-2013, 04:41 PM
Explanation-Based Learning (EBL)
Explanation-Based Learning.ppt (Size: 211.5 KB / Downloads: 15)
The EBL Hypothesis
By understanding why an example is a member of a concept, can learn the essential properties of the concept
Trade-off
the need to collect many examples
for
the ability to “explain” single examples (a “domain” theory)
Learning by Generalizing Explanations
Given
Goal (e.g., some predicate calculus statement)
Situation Description (facts)
Domain Theory (inference rules)
Operationality Criterion
Use problem solver to justify, using the rules, the goal in terms of the facts.
Generalize the justification as much as possible.
The operationality criterion states which other terms can appear in the generalized result.
Unification-Based Generalization
An explanation is an inter-connected collection of “pieces” of knowledge (inference rules, rewrite rules, etc.)
These “rules” are connected using unification, as in Prolog
The generalization task is to compute the most general unifier that allows the “knowledge pieces” to be connected together as generally as possible
Imperfect Theories and EBL
Incomplete Theory Problem
Cannot build explanations of specific problems because of missing knowledge
Intractable Theory Problem
Have enough knowledge, but not enough computer time to build specific explanation
Inconsistent Theory Problem
Can derive inconsistent results from a theory (e.g., because of default rules)
Issues with Imperfect Theories
Detecting imperfections
“broken” explanations (missing clause)
contradiction detection (proving P and not P)
multiple explanations (but expected!)
resources exceeded
Correcting imperfections
experimentation - motivated by failure type (explanation-based)
make approximations/assumptions - assume something is true
Learning for Search-Based Planners
Two options
1) Save composite collections of primitive operators, called MACROPS
explanation turned into rule added to knowledge base
2) Have a domain theory about your problem solver
use explicit declarative representation
build explanations about how problems were solved
which choices lead to failure, success, etc.
learn evaluation functions (prefer pursuing certain operations in certain situations)
Reasons for Control Rules
Improve search efficiency (prevent going down “blind alleys”)
To improve solution quality (don’t necessarily want first solution found via depth-first search)
To lead problem solver down seemingly unpromising paths
overcome default heuristics designed to keep problem solver from being overly combinatoric