An Automatically Compilable Recognition Network For Structured Patterns
Proceedings of the Fourth International Joint Conference on Artificial Intelligence. Learning Debugging And Automatic Programming. Pages 246-251.
© 1975 International Joint Conferences on Artificial Intelligence
Abstract
A new method for efficient recoanilion of aeneral relational structures is described and compared with existing methods. Patterns to be recognized are defined by templates consisting of a set of predicate calculus relations. Productions are representable by associating actions with templates. A network for recognizing occurrences of any of the template patterns in data may be automatically compiled. The compiled network is economical in the sense that conjunctive products (subsets) of relations common to several templates are represented in and computed by the network only once. The recognition network operates in a bottom-up fashion, in which all possibilities for pattern matches are evaluated simultaneously. The distribution of the recognition process throughout the network means that H can readily be decomposed into par aile I processes for use on a multiprocessor machine. The method is expected to be especially useful in errorful domains (!!.:&:, vision, speech) where par.llel treatment of alternative hypotheses is desired. The network is illustrated with an example from the current syntax and semantics module in the Hearsay II speech understandina system.
- Barrow, H.G., Ambler, A.P., & Burst~lll, R.M. Some techniques for recognising structures In pictures. In S. Watanabe (Ed.), Frontiers 2i pattern . recognition. New York: Academic Press, 1972.
- Colby, K.M., Faught, B., & P;~rkison, R.C. Pattern-matching rules for the recognition of natural langu1ge dialogue expressions. Memo AIM-234. Stanford: Stanford Artificial Intelligence Laboratory, Stanford University, 1974.
- Feldman, J.A., & Rovnar, F. An Algol-based associative language. Communications Qi the ACM, 1969, !l, 439- 449.
- Frost, M. The news service system. Operating Note SAILON 72-2. Stanford: Stanford Artificial Intelligence Laboratory, Stanford University, 1974.
- Hayes-Roth, F. An optimal network representation and other mechanisms for the recognition of structured events. Proceedings Qi the Second International Joint Conf.erence on Pattern Recognition, 1974. 251
- Hayes-Roth, F. The representation ol structured events and efficient procedures for their recognition. Pittsburgh: Department of Computer Science, Carnegie-Mellon University, 1974.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
AN AUTOMATICALLY COMPILABLE RECOGNITION NETWORK
FOR STRUCTURED PATTERNS
Frederick Hayes-Roth and Devid J. Mottow Computer Science Department 1 Carneaie-Mellon lkliversity Pittsburgh, Pa. 15213
described elsewhere [7) translates a given template grammar into an equivalent TNF grammar which is economical in thai it maximally exploits repealed sublemplates in the original grammar. The construction of an automatically compilable recognition network (ACORN) from a TNF grammar is described in the next sect ion. The definitions we use are tailored to natural language understanding, but are immediately generalizable to other applications (!!.:&:, vision).
A relation r(x 1, ... , xn) is an n-ary predicate corresponding to some element or pattern in the language. For example, the relation lell(x 1 , x 2 > holds if I he word "tell" occurs in I he input utterance beginning at lime x 1 and ending at lime x2. In general, x 1 and x2 are temporal arguments specifying the lime interval containing a recognized occurrence of the relaliqn, and x3, ... , xn are additional attributes of the occurrence. A relation is called primJ.I .iy~ if it corresponds to a primitive element (terminal symbol) of the language, rum: primitive if it corresponds tp a pattern of elements (non terminal symbol), and top-level if it corresponds to a complete
pattern (sentential form).
A template T is a Boolean combination of relations ri, i·1, ... , ITI, restricted as follows. It must be either a disjunction r1(x1 1 ... 1Xn) V r2(x1, ... , Xn) V ...
or a conjunction
In the first case (disjunction), the symbolic arguments (xl, ... , xn> are the same for each ri, i · I, ... , d. In the second case, a weaker condition must be satisfied: the relations must have enough symbolic arguments in common for the template to be connected, that is, for any partition of the p+q relat ions r I· ... , r p+q into two non-empty sets A and B, there must exist relations r a<x 1 , ... , ·n ) E A, rb(x 1 , ... , ·n ) E B with {xl, ... ,xn}n{x 1 a, ... ,x~J"'· b b
a a b b
A template grammar is a set of rules of the form [<template> R> <relation>; <action>~ The action optionally associated with each rule specifies what should be done in the event that an instance of the template is recognized in the input and the rule is invoked. Thus a template grammar is actually a production system of the sort described by Newell [12).
Table I. Sample Grammar (GAp)
- [ Ford(tl· t 2 > - > TOPIC(t 1 , t 2 , expr); expr ... "FORD" J
- [ Rockefeller(t 1 , t 2 > v Rocky(t 1 , t 2 ) ·> TOPIC(! I· l2, expr); expr ... "ROCKEFELLER" )
- [ Kissin&er(t I · I 2 > ·> .
- TOPIC(! I· l2, expr); expr ... "KISSINGER")
ABSTRACT
A new method for efficient recoanilion of aeneral relational structures is described and compared with existing methods. Patterns to be recognized are defined by templates consisting of a set of predicate calculus relations. Productions are representable by associating actions with templates. A network for recognizing occurrences of any of the template patterns in data may be automatically compiled. The compiled network is economical in the sense that conjunctive products (subsets) of relations common to several templates are represented in and computed by the network only once. The recognition network operates in a bottom-up fashion, in which all possibilities for pattern matches are evaluated simultaneously. The distribution of the recognition process throughout the network means that H can readily be decomposed into par aile I processes for use on a multi processor machine. The method is expected to be especially useful in errorful domains (!!.:&:, vision, speech) where par.llel treatment of alternative hypotheses is desired. The network is illustrated with an example from the current syntax and semantics module in the Hearsay II speech understandina system.
INTROQUCT!ON
The work described in this paper was motivated by certain problems involved in the task of recognizine eener.l structured patterns and, in particular, the problem of parsing contlnous spoken speech. From the point of view of the language parser, an essential quality of speech is its errorful nature. Ambiguities in acoustic seementation, phonetic labelling, word hypothesization, and semantic interpretation necessitate understanding systems which can deal efficiently with multiple alternative hypotheses about each portion of the input. [ 11) The usual methods of dealing with such multiple hypotheses typically entail an expensive search through 1 combinatorial space, since they consider only one hypothesis for each portion of input at a time, and then exploit contextual relationships to eliminate certain combinations of adjacent hypotheses as impossible. The data structure and associated recognition procedure described in this paper can be thought of as effectively reversing this process by first exploiting context -- thereby eliminating all but a few combinations from consideration -- and then testing contextually related hypotheses for adjacency. Since the contextual information is statically embedded in the data structure itself, comparatively lillie work needs to be done at recognition lime. This work requires only the computation of a few, simple operations rather than a complex search. Moreover, the method provides an efficient way to handle the spurious insertions and deletions characteristic of speech.
TEMPLATE GRAMMARS
In this section, we define template grammars for recogmzmg relational structures. A template normal form (TNF) for template grammars is defined. An algorithm
This research was supported in part by the Defense Adv;mced Research Projects Agency under contract no. F.:t/1620-73-C-0074 and monitored by the Air Force Office of Scientific Research.
- [ or(t 1 , t 2 ) 11. TOPIC(t 2 , t 3 , expr) ·> TOPIC·(tl, !3, expr);)
As an example, consider the sample template grammar GAP (Table 1) which is part of a much larger grammar for analyzing spoken queries .to a wire-service news retrieve! system. (4] GAp's lop-level relations are REQUEST and R£JECT. An instance of REQUEST is the utterance "Tell me all ebout Rocky." An instance of REJECT is the utterance "Tell me nothing about Ford, Rockefeller, or Kissinger." The primitive relation UTTERANCE(t 1 , t 2 ), used in rules 6, 7, and 8, simply signifies that the entire utterance spans the time interval [11, l2); this makes the beginning and ending limes of the utter a nee accessible as arguments to other relations, without violating the framework of the template grammar. Rule 2 illustrates the use of features and actions. The feature, expr, of TOPIC is the semantic expression eventually passed to · the actual news retrieval routine. The action of Rule 2 gives expr the value "ROCKEFELLER." Rule 5 is an example of recursion. It handles phrases of the form "topic!, topic2, ... , topicn-1· or topicn." The action of Rule 5 forms a compound semantic expression from the expressions associated with its individu1l constituents. Thus the instance "Ford, Rockefeller, or Kissinger" of the relation TOPIC* has expr · {"FORO", "ROCKEFELLER", "KISSINGER"}. Rule 6 shows how context sensitivity can be embedded in a template grammar. It sl1tes that any instance of TOPIC which occurs at the end of 1n utterance, and whose left conleKI is ABOUT, constitutes 1n instance of TOPIC·. Rule 8 illustrates the use of negation. It states that any utterance of the form "Tell me ... ebout X" is a request for information about X unless the gap " .. ." contains the word "nothing." Thus "Tell me about Ford," "Tell me ell about Ford," and "Tell me everything you know about Ford," are all instances of REQUEST. This illustrates I~ capacity of a template gr~mmar to ignore redundent portions of the input.
- A template grammar is in template normal form (TNF) if the following conditions are satisfied:
- ( 1) The template of each rule has one of the following types:
The relations in 1 disjunctive template heve the same symbolic arguments; the relations in a conjunctive or negative template are connected.
- Every non-primitive relation appears on the right side of eKactly one rule. Hence we can define the ~ of a relation to be the type of its unique defining template; a primitive relation is simply said to be of primitive type.
- It is clear that any template grammar G can be translated into an equivalent grammar G* in TNF by means of adding new relations and rules. The task of the automatic translator is to do this in suc.h a way as to minimize the number of new relations added. The algorithm we employ Is described in (7]. The result of applying the algorithm to the
sample grammar of Table 1 is grammar GAP*· shown in Table 2. Mnemonic conventions used in GAp* are these: "+" indicates concalenetion; "-" indicates temporal overlap; parenthetical phrases indicate temporal conteKis; and "/k" distinguishes different TNF relations arising from occurrences of a single relation in various different rules of the original grammar.
Table 2. Sample Grammar in TNF (GAp*)
6**. [ UTTERANCE(! 1 , !3) II. (ABOUT)TOPIC(t2, t3, expr) ·> TOPJC·/&(12, !3, expr); l
9. [ tell(t 1, t2) 11. me<t 2, t3) ·> TELL·ME(t 1· t3); 1
THE BECOGN!TION NETWORK
Given a template grammar in TNF, a corresponding recognition network (ACORN), as first described in [61 is constructed as follows. For each relation r appearing in the TNF grammar, there is a unique node, node(r), in the network. (Hence minimizing the number of relations in the TNF grammer is equivalent to minimizing the number of nodes in the network.) For every rule [T ·> r; A1 an . arc is drtwn from node(si) to node(r) for each relation si in the template T. Each node(si) is said to be a cons!i!yent of node(r), and node(r) a derivative of node(si). A node may have zero, one, or more derivatives. The recognition network for the sample grammar GAP· constructed from the TNF grammar GAP*· is shown in Figure 1.
Node(d contains various information: its type (!&, the type of relation r); the action A in the rule [T ·> r; A], if any; and the correspondence between the arguments of relation r and the arguments of its constituent relations si. This correspondence consists of two parts, a set of t!m and a generator. The tests represent any requirements for agreement between the arguments supplied by the constituents node(si). The generator is a list of the arguments which are to be supplied in turn to the derivatives of node(r). The arguments are encoded according to a canonical numbering scheme best described by a'n example. Consider node(TELL·t.AE). Its constituents are node(TELL), which supplies arguments I 1, t2, and node(t.AE), which supplies araumenls t3, tq. Let L be the concatenated argument list. (I 1· t2, t3, tq). Then node<TELL·t.AE) can specify its arguments by their indlces in L. Thus node(TELL·t.AE)'s only test is L(2) · L(3), denoted by "2:3" below node(TELL·t.AE) in the network. (See Fiaure 1.) Similarly, node(TELL·t.AE)'s generator is the list ( L(l ), l{4) ), denoted by "(1, 4)" above node(TELL·t.AE) in the network. Arguments which are not supplied by a node's constituents but instead originate at the node itself are specified by negative indices. For example, node(TOPIC/2)'s generator is denoted by "(1, 2, -1)," the -1 specifies the argument expr, which originates at node(TOPIC/2). The action stored in node(TOPlC/2) assigns this argument the value "ROCKEFELLER".
All of the recognition network components described so far are static. There is also associated with each node(r) a dynamic instance list IL. Each instance in the instance list of node(r) represents a single recognized occurrence (instantiation) of the relation r in the input utterance. An Instance has several components: a unique identification number I; the time interval [x 1 , x 2 ] containing the occ1,1rrence; the values x3, ... , xn of additional attributes of the occurrence; and a ~uppo..rJ ~!11 SS containing one or two instance identification numbers. An instance is denoted J:(x 1 , ... , xn; SS). During the recognition process, instances ar·e ·created and deleted dynamically.
The recognition process is bottom-up, as follows. Initially all instance lists are empty. A lexical analyzer is Invoked and begins to scan for occurrences of primitive relations in the input utterance. Since the lexical analyzer receives imperfect, incomplete information from. the phonetic labelling routine, the best it can do is to identify ~ occurrences. When it finds a possible occurrence of a relation r, it adds a new element to the instance list of node(r) containing the appropriate information. To understand the recoanition ·process, imagine each node(r) as having a demon. The node(r) demon continuously monitors the instance list of each constituent node(si) of node(r). Whenever a new instance is added to the instance list of node(si), the. node(r) demon adds a reference to this new instance to its node(si) add set. Similarly, whenever an existing instance of si is deleted, the node(r) demon saves a copy of it in its node(si) ~ set. Add sets and delete sets are referred to collectively as change sets. [9] The demon then activates (wakes) node(r) itself by invoking code pointed to by node(r).
When node(r) is activated, it updates its instance list according to the information in its constituents' instance lists and change sets. If node(r) can derive (construct) any new instances from instances of its consfituents·, it doe& so, adding the new instances to its instance list. The support set .of each lnstanc:e contains the identification numbers of the instances
from which it has been derived. Node(r) deletes from its instance list any instances supported by (derived from) the defunct instances listed in its constituents' delete sets. The exact way in which all this is done depends, of course, on the type of node(r).
If node(r) is disjunctive, then it has d constituents node(s 1 ), ... , node(sd). For each instance J:(x 1 , ... , xn; SS) in a node(si) add set, node(r) adds a new element lnew:(zl, ... , zk; Ill> to its own instance list, computing z 1 ,. .. , zk ~rom the values of x 1, ... , xn according to the generator stored 1n node(r). !new's support set is {I) because the instance I of r is derived from (supported by, dependent on) the insta":c': ·I of r's constituent relation si. For each defunct instance I in a node(si) delete set, node(r) deletes all instances lold:(z 1, ... , zk; SS) supported by I, !&, such that I ( SS. (Actually, for disjunctive r, all instances of r will have support sets of size one, so I< 55 iff SS · {1}. However, for conjunctive r, ISSI · 2; hence the set notation) . .
If node(r) is conjunctive, then it has exactly two constituents, node(s 1) and node(s 2 ), with respective instance lists IL 1 and 1~2· add sets AS 1 and AS 2 , and delete sets OS 1 and OS2. F~rsl node(r) deletes any of its instances lold:(z 1, ... , zk; SS) which were derived from instances in OS 1 or OS2, i,e., those for which SS n (OS 1 u OS 2 ) ~ t'. Then node(r) looks for new i~stance pairs li:<x 1 , ... , xn; SS 1 ) in IL 1 and l2:(yl, ... , Ym; SS2l 1n ll2 such that (x 1 , ... , xn) matches (yl, ... , Ym> according to the tests stored in node(r). For each such matching pair, node(r) adds a new element lnew:(z 1· ... , zk; {11, !2}) to its instance list, using its generator to select z 1, ... , zk from x 1, ... , xn, y 1 , ... , y m· It is sufficient to check only those pairs of instances 1 1 , 1 2 of which one or both are new, or more formally, such that either 1 1 f AS 1 and l2 f IL2 or l1 f IL 1 and 1 2 < AS 2 . For example, suppose the mput utterance is "Tell me nothing about Rockefeller," and the !exical analyzer finds an instance 1 1 :(0, 18; ... ) of tell and an mslance 12:(18, 23; ... ) of me. Then the test stored iri node(TELL·t.AE) becomes 18 · 18, which is true, sb ~ode(TELL.·t.AE) adds a new instance lnew:(O, 23; {1 1 , 1 2 }) to its mstance hst to represent the occurrence of wtell me" in the concatenated time interval [0, 23l (Time is measured in c.entiseconds since the beginning of the utterance.) Now suppose the lexical analyzer mistakenly identifies the syllable "fell" in "Rockefeller" as the word "tell," and adds an instance 13:(257, 269; ... ) to node(tell)'s instance list. This may happen, for example, if the phonetic labeller correctly identifies the "F" in "Rockefeller" as an unvoiced consonant but can't tell if it's an "F," a "T," or a "P." No harm is done, however, since when node(TELL·ME) matches 1 3 against 1 2 , the test 269 · 18 fails, and no new instance of TELL·t.AE is derived from 1 3 . This example shows how the ACORN automatically weeds out spurious instances hypothesized by the lexical analyzer on the basis of incomplete phonetic information.
Finally, if node(r) is negative, then it has two constituents, node(s 1 ) and node(s 2 ), where r · (s 1 " ~s 2 ). Let IL 1, IL2, AS 1, AS2, OS 1· DS2 be the instance lists, add sets, and dele~e s~ts !'f node(s 1) and node(s 2 ). First node(r) deletes any of 1ls mstances lold:(z 1, ... , zk; SS) derived from defunct instances in OS1 , i.e"' those for which SS n os 1 ~ t'. Then node(r) looks for any i~slance pairs 1 1 # 1 , ... , xn; SSt> in .IL 1 and l2:(yl, ... , Ym; SS2l '" AS2 such that (x1, ... , x.n> matches (y 1· ... , Ym) according to the tests stored in node(r). For each suc.h pair, node(r) deletes all of its instances t 01 d:(z 1 , ... , zk; SS) ~hiCh depended on 1 1 , i&, such that 1 1 < SS. This is done smce. eac~ such lold· previously an instance of (s 1 " ~s 2 ), is now mvahdated by a new instance of s 2 . Adding instances of node(r) is also a bit tricky, and proceeds as follows. First node(r) constructs the set IS of all instances 1 1 < IL 1 which match some l2 in OS2. Then node(r) looks for all instances l1 :(x 1, ... , xn; SS 1) in AS 1 u IS which match none of the ~nstances in IL2. For each such 1 1 , node(r) adds a new
mstance lnew:(zl, · ... , zk; {1 1}> to its instance list.
To illustrate this, lei us continue with our sample utterance, "Tell me nothing about Rockefeller." Suppose that at some point the lexical analyzer has recognized all the words in the utterance except the word "nothing," and node(TELL·t.AE UTTERANCE-ABOUT·TOPIC*) has
14:(23, 41, 0, 274, "ROCKEFELLER"; ... ) on its instance list. Since the instance list of node(nothin~t) is empty, node(REQUEST) will have an . instance ls:(O, 274, "ROCKEFELLER"; {1 4 }> on its mslance hst. Now suppose that the lexical analyzer finally recognizes the word "nothing," and puts the instance 16:(23, 41; ... ) on node(nothinc)'s instance list. This activates both of node(nothinc)'s derivatives. Node(REJECT) matches 1 6 agamsl l4, tests 23 ~ 23 and 41 · 41, and accordingly adds a .new insbnce 17:(0, 274, "ROCKEFELLER"; {1 4 , ~}) to its Instance hst. Node(REQUEST) matches 1 6 against 1 4 , tests 23 = 23 and 41 · 41, and accordingly deletes ls:(O, 274, "ROCKEFELLER"; {1 4 }) from its instance list. This example shows how information is accumulated and corrected dynamically during the ACORN recognition process. It also illustrates the ACORN's slate-saving nature and its sharing of information between lop-level nodes.
Once node(r) has examined its constituents' change sets and, if appropriate, revised its own instance list, it goes back to sleep. Meanwhile, the demons sitting on the derivatives of node(r) have been watching its instance list and, when changes occur, activate their nodes. This chain reaction continues, fuelled by new instances generated by the lexical analyzer, until the lexical analyzer has slopped, all nodes are asleep, and all change sets are empty.
AI this point each instance l:(x 1 , ... , xn; SS) of a non primitive node, node(r), may be interpreted as a partial parse of the interval [xl, x21 with relevant syntactic and semantic features given by x 3 , ... , xn. For example, when the recognition of our sample utterance terminates, the instance 1:(41, 274, "ROCKEFELLER"; ... ) of ABOUT·TOPIC* may be considered to be a partial parse of the input interval [41, 274) containing "about Rockefeller." Parse trees can easily be reconstructed from the information contained in the support sets. Parses of the entire utterance are given by instances of top-level nodes. Thus the instance I7:(0, 274, "ROCKEFELLER"; {1 4 , 1 6 }) of REJECT constitutes a total parse of the sample utterance, and supplies the semantic feature, expr, required by the action SUPP.RESS(expr).
RELATIONSHIP IO EXISTING PARSERS
ANQ PATTERN-MATCHERS
The original motivation which led to the ACORN concept was the development of a general automatic recognition system for spoken utterances, visual scenes, and other structured patterns in which context is a fruitful source of information. Since the speech understanding ACORN ·treats an utterance as a relational structure, it is related both. to natural language parsers and to general pattern-matching mechanisms.
The ACORN's closest relative among natural language parsers is PARRY [2], a program which simulates a paranoid individu.al being interviewed by a psychiatrist . PARRY employs a large library of stored concept sequence templates which are compared with segments of typewritten input sentences. Generalization is achieved by rules which rewrite words as synonymous concepts, delete unrecognized words and, if necessary, delete one recognized word at a lime until a template is matched. While the approach underlying PARRY is very successful with typed input, it appears lo be too risky for spoken input. Unlike the "perfect" input which PARRY receives, the input to the syntax module of a speech understanding system such as Hearsay II [9) is highly imperfect . PARRY can say, with confidence, "this portion of the input is such-and-such (~ the word "oh"), so I'll ignore it;" Hearsay II can only say "l! this portion of the input is "oh," I can ignore it; but if it's really the word "no," then I'll need it." An ACORN can be thought of as a non-deterministic version of a PARRY-like system in which all possible parses are followed simultaneously in parallel. On the other hand, an ACORN is capable of recognizing general graph structures and is more powerful than any context-sensitive language parser (string recognizer).
Woods' augmented transition network (ATN) [14) is a mechanism for parsing natural language. It works top-down, uses backtracking, and produces a formal parse of the input sentence. In contrast, an ACORN works bottom-up, does no backtracking, and extracts only those features of the utterance which are relevant to the particular application. An ACORN can be thought of as a slate-saving, bottom-up version of an A TN.
Miller [ 10) has proposed a parser for spoken English which builds multiple partial parse trees and employs a complicated and heuristic search to combine them. An ACORN differs from Miller's parser in handling all combinations simultaneously rather than sequentially, and in the simplicity of the matching operations il uses.
Current artificial intelligence programming systems such as PLANNER [8), QA4 [131 and SAIL [3) can match a given relational template against a data base. However, the method they use is an exhaustive, iterative, and associative search. If several templates are to be matched against the data base, they must be matched one at a lime. In contrast, the associative matching operation performed by ACORNs effectively tests all the relations of all the templates simultaneously.
The ACORN's nearest relative among general pattern matching methods is hierarchical synthesis [1l .Consider the task of malthing a template, such as 1 schematic representation of a building, against an input set of line segments. A recognition algorithm employing hierarchical synthesis replaces the single, many-component template for "building" with a hierarchy of templates lor "doors," "windows," "stories," etc. A higher-level template can be m1lched only if its lower-level constituents are. Hierarchical synthesis considerably reduces recognition lime for two reasons. First, it can exploit the repetition of subtemplates by recognizing all instances of a single subpattern just once. Second, before considering whether or not the entire pattern specified by a template is present, it can insure that all necessary subpatterns are present.
However, hierarchical synthesis as described in [1) depends on a hierarchy defined ! priori by the user. This limitation is transcended by Hayes-Roth's interference matching method [5 ), which does hierarchical synthesis in parallel in all possible directions, thereby obviating the need for a predefined hierarchy. In interference matching, a template is represented as a set of relations. Each relation is a predicate with one or more symbolic variables. The input is also a set of relations, whose arguments are constants. A partial match consists of an assignment of input constants to the symbolic variables of a subset of template relations which makes them all true. Interference matching works by finding partial matches and combining them into complete matches.
Like interference matching, the ACORN method is an improved version of hierarchical synthesis in that it requires no predefined hierarchy. The ACORN compiler itself determines an economical hierarchy, and embeds il in the form of a recognition network. Hierarchy selection can be factored out into a separate compilation phase because the choice of hierarchy depends only on the templates and not on the individual input utterance. In interference matching, on the other hand, hierarchy selection depends on the input pattern, and is therefore a part of the recognition process. Thus the ACORN method combines the convenience of automatic hierarchy selection with the efficiency which comes from using a predefined hierarchy in the recognition process.
In real-world applications, input is matched against several top-level templates. Current methods of hierarchical synthesis and interference matching involve malchina the input against one template at a lime. Such an approach Is clearly undesirable for tasks such as speech recognition, which may involve large numbers of templates. The ACORN compiler lakes a whole set of templates and produces a single, unified recognition network for II; common subtemplates are shared not just within top-level templates but also between them. An Instance of a subtemplllle is recognized just once -- not separately for each top-level template in which it occurs. Hence recognition lime depends not on the total number of templates, but just on the number of templates which match some portion of the input. This property is encouraging, since the number Of templates required IO recognize I significant ·subset of English would probably be several thousand.
In sum, an ACORN can be looked at as a bottom-up version of an ATN; a parallel and non-deterministic version of a PARRY-l ike system; a general pattern-matcher; or an improved mechanism for hierarchical synthesis, with automatic hierarchy selection and sublemplate sharing between templates.
APPLICATIONS. IMPLICATIONS. AND EXTENSIONS
In order for ar\ ACORN to be efficient, the templates and input data characteristic of the chosen problem domain should tend to be asymmetric, so that a template will usually match a given portion of the input in at most one way. Let us illustrate with a negative example. Suppose the template we wish to match ,is t< 5 (a, b, c, d, e), the complete graph on five vertices, represented by the conjunction of relations line(a, b) 11 line(a, c) 11 ... 11 line(d, e). Then any occurrence of t< 5 (as a subgraph, say) in the input corresponds to 5! · 120 instances of T, since there are 5! different ways to bind the variables a, b, c, d, e to the five vertices of the 1<5 in the input. For symmetries on a larger scale, the problem grows combinatorially worse. Clearly, an ACORN would be inefficient in such a domain, since it would insist on finding all instances
of every template.
Fortunately, many problem domains do not exhibit this bothersome properly. Speech, in particular, is highly asymmetric, partly because it is embedded in a one dimensional ordered temporal domain. If tell( I 1, 12) is true, then I 1 < t 2 , so le11(12· I 1 ) cannot be true. Symmetries at a higher level can occur only if there is more than one syntactically and semantically valid way to group the input words into phrases, !&, if lhe input is inherently ambiguous.
What are the advantages of ACORNs for speech understanding? The bottom-up template-oriented approach is especially conducive to handling natural, idiomatic, conversational natural language robustly. Consider the problem in spoken speech of spurious insertions such as "oh," "um," "er." We wish to treat them the same as silences. We do this by adding rules like [oh(t 1 , l2l ·> SILENCE(II, 12);] to our template grammar, and relax.ing the test l2·l3 for temporal adjacency be·lween two relation instances, such as tell(ll, 12) and me(l 3 , t 4l, to compute t 2 -t 3 v SILENCE(I2, l3l.
This example also illustrates the reason for non deterministic application of Colby's methods in 1 speech understanding system. Even if a spurious insertion is recognized, the corresponding portion of the input must not be discarded, $ince it may have been recognized incorrectly. If an ACORN recognizes an instance of "oh" in the interval [t 1· !2), it puts the instance (I 1· t 2 ; ... ) on the instance list of SILENCE, without discarding any information. That way, if the interval actually contains the word "no," it is still there for the lexical analyzer to find. In contrast, when PARRY ignores information, it throws it away altogether.
Another phenomenon common to conversational speech is the idiomatic expression, u, "How are you?" Using an ACORN, we can simply include explicit template rules for such expressions, ~
[how·are·you(l I· 12) ·>
GREETING( I 1, l2l; REPL Y("Fine, how are you?")].
thereby short-circuiting the detailed syntactic parse which would be attempted by a more formal system such as Woods'.
The two techniques just described can be combined. Certain idioms such as "by the way" carry essentially no useful Information end can be !reeled es spurious insertions by rules like
Some expressions occur either as meaningless idioms or as meaningful phrases, depending on conteKI. Consider, for example, the utterance "I see, could I see the midnight digest?," which occurred in an actual experimental protocol. The first occurrence of "I see" is idiomatic and can be ignored; the second is essential to the meaning of the utterance. An ACORN, in processing this utterance, would recognize both occurrences as instances of SILENCE, without discarding any information. The first occurrence would be . ignored, as desired, but the second one would still be available to match other templates.
Spurious deletions can also be handled by ACORNs. To handle spurious deletions, we want to permit partial matching of -templates. We can do this within the ACORN fremework simply by adding extra templates corresponding to commonly occurring partial matches of the original templates. The obvious weakness of this method is that it requires ! priori knowledge of which deletions are likely to occur. The success of the method might require many iterations over a large corpus of lest utterances, with new templates added as needed. Hopefully this process would converge, after a reasonable number of such iteration$, to acceptable performance with respect to handling sl)urious deletions. (Ttlis method of "massive iteration" seems to have worked successfully for PARRY.)
Partial templates can be used for another purpose as well. Although the bottom-up approach has severe! advantages, as described above, it is useful . to have certain properties associated with top-down processing. One such property is the ability to focus the attention of lower-level modules on critical portions of input. Another is the ability to hypothesize words from above, for lower-level modules to confirm or reject. Although we earlier referred ·to a lexicel analyzer which finds all instances of primitive relations (words) in the input utterance, this would in practice be too expensive. The actual Hearsay II system sl!eks to constrain hypothesization as much as possible; to do this it applies high level information to cut down the number of plausible words matched against each portion of the input . Thus it. is desirable to have a speech understanding ACORN generate intermediate partial information telling the lower level modules which portions of the input they should concentrate on processing, and which words are likely to occur It a given place in the input, on the basis of the already recognized portions of the surrounding context.
This lop-down extension to the basic bottom-up mechanism requires knowledge about the predictive value of partial templates. For example, we know that -what lime" often occurs in the phrase -what time is it?" We can incorporate this information in an ACORN by including 11 rule
where TEST is the action invoked upon recognition of the template. The effect of the TEST is to look for the missing instance of "is it" starling at the time t 3 in the input utterance. If it is found, it is added to the instance list for is·it, leading to the desired completion of the full template "What time is it."
In the above example, a partial template was used to predict downwards in the network. Partial templates can also be good upward predictors. For example, given an instance of the partial template T 1 · "time is it," the probability P(T 2IT 1) that it occurs as part of the template T 2 · "What time is it" may approach certainly. If P(T 2IT 1) is high enough, say .99, we may wish to save processing lime by simply predic1ling that T 2 does in fact occur. Such 1 scheme is currently being implemented.
EVALUATION AND CONCLUS1QNS
- A full evaluation of the ACORN method must of course await experience with large-scale implementations. In the meantime, there are several properties we observe from the current, partial implementation.
- ( 1) The recognizer is efficient.
- It is extremely easy to modify, since changes are restricted to the template grammar.
- Using an ACORN makes it possible to dispense with a lormal parse.
- Even when an ACORN cannot fully parse an utterance, it can still provide a partial parse.
- ACORNs are organized so as to factor recogr.ition processing into simple, universal, and indepe·ndent operations performed at the nodes. This has made them trivi1l to implement and, in addition, makes them well-suited to parallel execution on a multiprocessor.
Finally, we expect ACORNs to have a broad r1nge of ~pplications, since they seem well-sui.ted to recognizing 1ny sort of relational pattern which manifests few symmetries. Both spoken utterances and real-world scenes appear to be in this class. At this point, we have implemented one ACORN processor for the syntax and semantics in speech (SASS) module of Hearsay II. Another ACORN processor has been built for recognizing the occurrence of inferred patterns (abstractions) in pattern learning training data. The abstractions themselves are produced by a program called Sprouter which grows a minimal ACORN to recognize 111 subtemplates common to two or more relational patterns. [5) From these experiences, it seems that ACORNs may provide an effective mechanism for gener11l recognition.
@inproceedings{ijcai1975p38,
title = {An Automatically Compilable Recognition Network For Structured Patterns},
author = {Hayes-Roth, Frederick and Moslow, D.},
booktitle = {Proceedings of the Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-75}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Patrick Winston and Carl Hewitt},
pages = {246--251},
year = {1975},
note = {Learning Debugging And Automatic Programming},
url = {https://ijcai.org/proceedings/1975/38},
}
TY - CPAPER TI - An Automatically Compilable Recognition Network For Structured Patterns AU - Hayes-Roth, Frederick AU - Moslow, D. T2 - Proceedings of the Fourth International Joint Conference on Artificial Intelligence, IJCAI-75 PB - International Joint Conferences on Artificial Intelligence PY - 1975 SP - 246 EP - 251 UR - https://ijcai.org/proceedings/1975/38 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
Welcome
Future Conferences
AI Journal Division
IJCAI Proceedings
About IJCAI
IJCAI Awards