《机器学习》（英文版）Table 1. The explanation-based generalization problem Given

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 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)

Table 3.The CUP generalization problem after Winston et al. ( 1983) Given Goal Concept: Class of objects, x, such that CUP(x),where CUP(x)+ LIFTABLE(x)A STABLE(x)A OPEN-VESSEL(x) ng Example OWNER(OBJl, EDGAR) PART-OF(OBJ1, CONCAVITY-1) IS(OBJ1, LIGHT) · Domain Theory IS(x, LIGHT)A PART-OF(, y) A ISA(y, HANDLE)+ LIFTABLE(x) PART-OF(x, y)A ISA(y, BOTTOM)A IS(y, FLAT+ STABLE(x) PART-OF(x, y)A ISA(y, CONCAVITY)A IS(y, UPWARD-POINTING+ OPEN-VESSEL(x) Operationality Criterion: Concept definition must be expressed in terms of structural features used in describing examples(e. g, LIGHT, HANDLE, FLAT, etc. ) Determine A generalization of training example that is a sufficient concept definition for the goal concept and that satisfies the operationality criterion

EXPLANATION STRUCTURE CUP (OBJ1 OPEN-VESSEL (OBJ1) STABLE (OBJ1 LIFTABLE (OBJ1 PART-OF (OBJ1, CONCAVITY. 1) IS (OBJ1, LIGHT SA(CONCAVITY.1, CONCAVITY) PART-OF(OBJ1, HANDLE-1) IS(CONCAVITY-1, UPWARD-POINTING ISA(HANDLE-1, HANDLE PART-OF (OBJ1, BOTTOM-1 ISA(BOTTOM-1, BOTTOM) IS (BOTTOM.1, FLAT

(PART-OF(x, xc)A ISA(c, CONCAVITY) A IS(xc, UPWARD-POINTING) A PART-OF(X, x b)A ISA(xb, BOTTOM)A IS(xb, FLAT) A PART-OF (x, xh)A ISA(xh, HANDLE)A IS (x, LIGHT)+CUP (x)

LIFTABLE. DRINKABLE-FROM

LIFTABLE, DRINKABLE-FROM

Fred is the father of mary and is a millionaire. John approached Mary. She was wearing blue jeans. John pointed a gun at her and told her he wanted her to get into his car He drove her to his hotel and locked her in his room. John called Fred and told him John was holding Mary captive. John told Fred if Fred gave him $250,000 at Trenos then John would release Mary. Fred gave him the money and John released Mary

Fred is the father of Mary and is a millionaire. John approached Mary. She was wearing blue jeans. John pointed a gun at her and told her he wanted her to get into his car. He drove her to his hotel and locked her in his room. John called Fred and told him John was holding Mary captive. John told Fred if Fred gave him $250,000 at Trenos then John would release Mary. Fred gave him the money and John released Mary