Table 1. The explanation-based generalization problem Given Goal Concept: A concept definition describing the concept to be learned. (It is assumed that this concept definition fails to satisfy the Operationality Criterion. Training Example: An example of the goal concept Domain Theory: A set of rules and facts to be used in explaining how the training example is an example of the goal concept. Operationality Criterion: A predicate over concept definitions, specifying the form in which the learned concept definition must be expressed Determine a generalization of the training example that is a sufficient concept definition for the goal concept and that satisfies the operationality criterion
Table 2. The SAFE-To-STACK generalization problem after Borgida et al. (1985) Given Goal Concept: Pairs of objects <x, y> such that SAFE-TO-STACK (x, y), where SAFE-TO-STACK(x, y)* NOT(FRAGILE (y))V LIGHTER (x, y) Training Example. ON (OBJl, OBJ2) ISA(OBJ1, BOX) ISA(OBJ2, ENDTABLE) COLOR(OBJl, RED) COLOR(OBJ2, BLUE) VOLUME (OBJl, 1) DENSITY(OBJ1, 1) · Domain Theory. VOLUME (pl, v1)A DENSITY (pl, di)- WEIGHT(pl, v1.d1) WEIGHT(pl, wl)A WEIGHT (p2, w2)A LESS (wl, w2)- LIGHTER(pl, p2) ISA(pl, ENDTABLE)- WEIGHT(pl, 5)(default) LESS (.1, 5) G berationality Criterion The concept definition must be expressed in terms of the predicates used O describe examples(e. g, VOLUME, COLOR, DENSITY) or other selected, easily evaluated predicates from the domain theory (e. g, LESS). Determine A generalization of training example that is a sufficient concept definition for the goal concept and that satisfies the operationality criterion
EXPLANATION STRUCTURE. SAFE-TO-STACK (OBJ1,OBJ2) LIGHTER (OBJ1, OBJ2) WEIGHT (OBJ1, 1) LESS (1, 5) WEIGHT(OBJ2, 5) VOLUME (OBJ1, 1) DENSITY (OBJ1, .1) ISA(OBJ2, ENDTABLE)
GOAL CONCEPT SAFE-TO-STACK(x, y) R1: SAFE- TO- STACK(p1, p2) lx/p1, y/p2) LIGHTER (p1, D2) LIGHTER (x, y) R2 LIGHTER(p1, p2) x/pl, y/p2) WEIGHT (p1, w1) LESS (w1, w2) WEIGHT (p2, w2) WEIGHT(x, w1) LESS (wf, w2) WEIGHT (y, w2) R3 WEIGHT(p1,v1’d1 D4: WEIGHT (p2, 5) x/p1,v1d1/w11 ly/p2,5/w2 VOLUME(p1, v1) DENSITY (p1, d1) ISA(p2, ENDTABLE VOLUME (x, v1) DENSITY (x, d1) LESS (v1'd1, 5) /SA(, ENDTABLE
VOLUME(x, v1) ∧ DENSITY(x,d1) ∧LESS(v1*dl,S) ∧ISA(y, ENDTABLE)→ SAFE-TO-STACK(X,y)