Information Technology Reference
In-Depth Information
construct an explanation structure for a certain condition and generalize the
explanation structure to make it fit more general circumstances. Generalization of
EBL takes advantage of logical representation of knowledge and ways of
deductive problem solving.
In order to define the generalization problem considered here, we first
introduce some terminology. A concept is defined as a predicate over some
universe of instances, and thus characterizes some subset of the instances. Each
instance in this universe is described by a collection of ground literals that
represent its features and their values. A concept definition describes the
necessary and sufficient conditions for being an example of the concept, while a
sufficient concept definition describes sufficient conditions for being an example
of the concept. An instance that satisfies the concept definition is called an
example, or positive example of that concept, whereas an instance that does not
satisfy the concept definition is called a negative example of that concept. A
generalization of an example is a concept definition which describes a set
containing that example. An explanation of how an instance is an example of a
concept is a proof that the example satisfies the concept definition. An
explanation structure is the proof tree, modified by replacing each instantiated
rule by the associated general rule.
A formal specification of Explanation-Based Generalization can be formally
described as(Mitchell et al., 1986):
Given:
(1) Goal Concept: A concept definition describing the concept to be learned.
(2) Training Example: An example of the goal concept.
(3) Domain Theory: A set of rules and facts to be used in explaining how the
training example is an example of the goal concept.
(4) Operationality Criterion: A predicate over concept definitions, specifying
theform in which the learned concept definition must be expressed.
Determine:
• A generalization of the training example, and satisfies the two conditions:
(1) A sufficient concept definition for the goal concept.
(2) Satisfies the operationality criterion.
Explanation-Based Generalization can be divided into two steps: The first
step is to explain: that is to construct an explanation tree in terms of the domain
theory that proves how the training example satisfies the goal concept definition.
This explanation must be constructed so that each branch of the explanation
structure terminates in an expression that satisfies the operationality criterion.
The second step is to generalize: determine a set of sufficient conditions under
