TEACH PARPAR Chris Mellish, February 1983 === PARTIAL PARSE TREES, CONCEPT LEARNING ============================ === and INCREMENTAL DESCRIPTION REFINEMENT =========================== This TEACH file presents the notion of a partial parse tree as a representation for an object or class of objects. Partial parse trees are easily implemented and show how an object or objects fit into a hierarchical view of the world. Indeed, they have no doubt appeared under many names before (such as, perhaps, "and/or trees", "frames", ???) Partial parse trees are shown to be relevant to both a Winston-like concept learning task, and also the notion of Incremental Description Refinement, used by Bobrow and Webber. There is a library program using partial parse trees for concept learning (see *LERNGRAM). --- PARTIAL PARSE TREES ------------------------------------------------------- The function of a parse tree is to give a STRUCTURAL DESCRIPTION of some object. When a linguist uses a parse tree to describe a sentence, it actually conveys two kinds of information: - the part-whole relationships between phrases - the left-right relationships between phrases In the following, we will be using parse trees in domains where there is no corrolate to left-right ordering. It follows that we will concentrate on the first kind of information. We will denote trees using a standard list notation (with square brackets) and adopt the convention that the number of subtrees associated with any one label is always the same. Thus the first element of a list always determines exactly how many elements that list has. A parse tree can be seen as indicating the sequence of DECISIONS taken in the creation of the object described. For instance, the following parse tree for a sentence: [s [np [pn john]] [vp [v hit] [np [pn steve]]]] indicates something like the following going on in an imaginary creator's mind: - First of all, the object will be a s (with two parts) - The first part will be a np (with one part) - That part will be a pn (with one part) ..... Given an appropriate view of the world, we can use a parse tree as a description of an object. This description expresses how this particular object relates to the particular "options" available for "constructing" objects in general. For instance, consider the following "grammar" for possible worlds involving two objects: world --> object + object + relations object --> block object --> wedge relations --> touchrel + displacementrel touchrel --> touchingrel touchrel --> apart touchingrel --> overlaps touchingrel --> abuts displacementrel --> above displacementrel --> below A world consists of two objects and the relations that are true between them. Each object can be a block or a wedge. The relations must consist of a relation saying whether they are touching, together with a relation specifying their relative displacement. If the objects are touching, then in addition one can specify whether they overlap or abut. Given this grammar, the parse tree: [world [object block] [object wedge] [relations [touchrel [touchingrel overlaps]] [displacementrel above] ] ] would represent something like the following (we must have a convention about which objects are the subjects and objects of the relations specified): /\ / \ / \ *--------* | | | | --------*--------*-------- A PARTIAL PARSE TREE is like a parse tree, except that it may include the special symbol "=" in the place of a leaf or subtree. For instance, the following is a partial parse tree relevant to the above grammar for worlds: [world [object block] [object =] [relations [touchrel =] [displacementrel =] ] ] A normal parse tree is a description of some particular object (here a world with two things in it). What meaning might we attach to a partial parse tree? One possibility is to see it as standing for a whole CLASS of objects, whose descriptions agree with the partial parse tree everywhere except where there is a "=", at which point any subtree can appear. Under this interpretation, the above partial parse tree would stand for a class which includes the following objects: [world [object block] [object wedge] [relations [touchrel [touchingrel overlaps]] [displacementrel above] ] ] [world [object block] [object block] [relations [touchrel apart] [displacementrel above] ] ] and various others. Another way of looking at this would be to say that the partial parse tree represents a CONCEPT, and that any object whose description "matches" the partial parse tree is an instance of that object. In this case, the above partial parse tree would represent something like the concept of any situation where there is a block and some other object. --- THE CONCEPT LEARNING TASK ------------------------------------------------ Given the partial parse tree representation for objects and concepts, we might ask how one could generate the description of some desired concept, given examples and non-examples of that concept. This is the concept learning task that Winston discusses. It is desirable for a concept learning program to have a PARTIAL model of the desired concept at intermediate stages in the learning sequence. Ideally, it should progress by gradually refining this partial model in a way that does not require making decisions that may later have to be revoked. The key to using partial parse trees in the concept learning task is to have the program's partial model of the concept in the form of TWO partial parse trees. These represent roughly the aspects of the object that MUST BE in a particular form and the aspects that CAN BE in a particular form. So, for instance, a partial model of a concept in the above world might be: CAN BE MUST BE [world [world [object block] [object =] [object wedge] [object wedge] [relations [relations [touchrel apart] [touchrel =] [displacementrel =] [displacementrel =] ] ] ] ] How are we to interpret this model, in terms of what we can say about the objects that are and are not examples of the desired concept. The rule is: If an object's description "matches" the CAN BE tree, it is an example If an object's description doesn't "match" the MUST BE tree, it is not an example Otherwise the partial model does not determine whether it is an example or not So the model that has been built up by this time is partial, inasmuch as there are some objects that it cannot decide about. If the concept learning program is to eventually understand the concept, it must eventually get to the state where the CAN BE and MUST BE trees are identical. It will then be able to say for certain whether any given object is an example of the concept or not. Exercise: What objects are classified by the above partial model as examples and non-examples? The following rules ensure that the CAN BE and MUST BE trees eventually converge to the same tree that represents the desired concept. 1. The MUST BE tree starts off as the tree = The CAN BE tree starts off as the tree for the first example given 2. When a new example is given, which cannot already be diagnosed as an example, the CAN BE tree is changed to be a tree as similar as possible to its previous value, such that it now matches the new example. This will involve replacing bits of the old value with =s. For example, if the CAN BE tree is: [world [object =] [object wedge] [relations [touchrel [touchingrel overlaps]] [displacementrel above] ] ] and the new example is: [world [object block] [object wedge] [relations [touchrel [touchingrel abuts]] [displacementrel above] ] ] then the new CAN BE tree is: [world [object =] [object wedge] [relations [touchrel [touchingrel =]] [displacementrel above] ] ] 3. If a new near miss (non-example) is given and cannot be diagnosed as a non-example, then the MUST BE tree must be changed in a minimal way so that it is consistent with the CAN BE tree but no longer matches the data. This involves finding some part of the CAN BE tree which is not = but where the corresponding part of the MUST BE tree is =, and replacing the = in the MUST BE tree by the value in the CAN BE tree. For instance, if the partial model is: CAN BE MUST BE [world [world [object block] [object =] [object wedge] [object wedge] [relations [relations [touchrel apart] [touchrel apart] [displacementrel above] [displacementrel =] ] ] ] ] and the data is: [world [object wedge] [object wedge] [relations [touchrel apart] [displacementrel below] ] ] then the new MUST BE tree could be either of: [world [world [object block] [object =] [object wedge] [object wedge] [relations [relations [touchrel apart] [touchrel apart] [displacementrel =] [displacementrel above] ] ] ] ] Notice that there may be several possible choices at this point, and so one choice must be made non-deterministically. This ends the short description of the concept learning algorithm. You might like to try going through some cases by hand to see how it works. There is one problem that may arise: the trees never quite get to be equal, even though they are sufficient to say whether any world satisfying the grammar is an example or non-example. This is because, in order to REALLY pin down the concept, it is necessary to give non-examples which are not legal according to the grammar. --- INCREMENTAL DESCRIPTION REFINEMENT -------------------------------------- Partial parse trees can be used as a representation for another task, called "Incremental Description Refinement". In this task, there is an object about which one initially knows nothing, and about which evidence is gradually accumulating. The idea is to be able to represent the partial information available about the object at any stage, and draw inferences where appropriate. This idea has been used by Bobrow and Webber and by Mellish (see references below). Under certain conditions, a partial parse tree can be an appropriate representation for this task. For instance, if the object being discussed was a world according to the "grammar" above, we might start by representing our knowledge about it as: [world = = =] If we then discover that the world contains a block, this description might be "refined" (or "instantiated") to [world [object block] = =] We might next find that the block is touching something. This leads to: [world [object block] = [relations [touchrel =] = ] ] and so on. One could write procedures to look at the partial parse tree at any time and say which properties DEFINITELY hold of the world, which properties DEFINITELY DO NOT hold, and which properties are as yet unknown. I hypothesise that the incremental description refinement task is not very different from the concept learning task, and that they are in fact both examples of a more general problem. However, the generalisation is currently beyond me. --- ACKNOWLEDGEMENTS -------------------------------------------------------- This whole approach is secretly modelled on a "rational reconstruction" of Winston's concept learning program undertaken by Young, Plotkin and Linz. Alan Bundy has also played an important role in making the ideas clear to me. --- EXERCISES --------------------------------------------------------------- 1. Write a "grammar" for a small world and use the above concept learning algorithm to learn concepts from examples and non-examples. Since the algorithm is non-deterministic at one place, it might be appropriately programmed in Prolog. 2. How do the ideas presented here relate to: Halliday's Systemic Grammar? Frames? And/Or trees? Winston's concept learning program? --- REFERENCES -------------------------------------------------------------- Winston, P.H., "Learning Structural Descriptions from Examples", in Winston (Ed), "The Psychology of Computer Vision", McGraw-Hill, 1975. Other articles by Winston on the same topic are to be found in Winston, P.H., "Artificial Intelligence" (Addison Wesley, 1977) and Johnson-Laird, P.N. and Wason, P.C., (Eds) "Thinking" (Cambridge University Press, 1977). Young, R.M., Plotkin, G.D. and Linz, R.F., "Analysis of an Extended Concept Learning Task", IJCAI-77. Bobrow, R.J. and Webber, B.L., "Parsing and Semantic Interpretation in the BBN Natural Language Understanding System", Proceedings of the CSCSI/SCEIO Conference, 1980. Mellish, C.S., "Incremental Evaluation: An Approach to the Semantic Interpretation of Noun Phrases", Cognitive Studies Memo 82-1, University of Sussex.