Representation and Efficiency in a Production System for Speech Understanding

1. INTRODUCTION

A prime candidate organization for large knowledge-rich systems is that of a production system (PS) [10,2,15~ PSs are rule-based architectures that have been used successfully for tasks ranging from models of human behavior [ 11), to large application systems in chemistry [3] and medicine [13], to general artificial intelligence programming tasks [12~ The uniform rule structure of knowledge In PSs makes them particularly useful for tasks requiring Iterative upgrading of knowledge content.

The research question reported on In this paper* is whether a PS architectur!! (PSA) is adequate to represent the rich variety of speech knowledge contained in Hearsay-H. (HSII), a large artificial intelligence system for understanding speech, developed at Carnegie-Mellon University [n We consider explicitly the questions of representational adequacy, space efficiency and time efficiency.**

HSIJ is a system organization for the speech understanding task designed to coordinate the contributions of diverse, essentially independent sources of knowledge which operate at the different hierarchical levels of speech knowledge. The essential device for communication among knowledge sources (I<Ss) is a large shared working memory called the Blaclcbo4rd, which all KSs inspect and modify. The Blackboard is a medium for growing linked networks of hypotheses about what elements exist at the various levels and for various time Intervals of the utterance (e.g., words, syllables, etc.).

·rht· r1111rch Wll 1pon1ored In p1rl by the O.fen11 Advencld ReMerch Project· Acency (000), ARPA Order No. 3597, monitored by the Air Force Avionice lllboratory Under Conine! F33815-78-C-1551.

··rhe Ph.D. lhe1i1 the! lhi1 paper i· ba11d on (6) coneiclen th .. · ea""' que1tlon1 in treater dltai~ plu1 the queetiona of .,.ploitinc penlllli·m on muttiprociiiOrl and of dl<ompoeine ~ 1y1lam to run on proc111on with

· ·-II eddr111 1peca.

The KSs are structured to contribute their knowledge b) creating and modifying Blackboard hypotheses and links In response to relevant changes by other I<Ss (i.e., in a ~eta-directed fashion).

To carry out the research reported here, an actual production system (called HSP, for "HearSay-Product ion system") was implemented on C.mmp, the CMU multi-miniprocessor [ 16 ), with a portion of the HSII speech knowledge translated into productions. Two knowledge-source (KS) programs from a full HSII configuration were completely translated and run in HSP, and these provide a basis for some detailed comparisons between HSII and HSP. These KSs were (1) POM [14], which recognizes syllables from speech segments, using a complex, multi-phase process involving three interMediate levels of representation; and (2) RPOL (1 ), which propagates validity ratings for the Blackboard hypotheses along thfl links 'hat interconnect them. POM and RPOL together required 945 HSP productions. Ten other KSs were trar· -: lated, but with some simplific<>t ions and omissions, and were never completely debugged and run. However, their static structure does provide evidence for representation issues. The total number of HSP productions for all twelve KSs was 2211. If this count Is adjusted to discount highly similar product ions that simply enumerate cases for a single situation, the result is 293 substantially different productions out of the total of 2211.

2. THE PROMISE OF PRODUCTION SYSTEMS

A production system architecture (PSA), in the sense used here, consists of a set of rules, called productions, stored in a production memory (PM), plus a working memory (WM) which holds symbolic structures operated on by the productions. A production consists of a condition part which tests the current state of WM, and an action part which specifies additions, modifications and deletions to WM to take place In case the condition part Is true. The basic operating cycle of a PS Is a "recognize-act" cycle: I.e., recognize which production conditions are true of the current WM, then execute the corresponding production actions. Since each cycle makes some change to the WM state (which changes the set of productions that are true), iteration of the cycle produces (potentially, at least) an interesting stream of behavior.

PSAs at large show a great deal of diversity. The strain to which HSP belongs has a lineage beginning with studies of human problem solving [11] and a PSA called PSG [10], and extending to the more recent architectures of PSNLST [12] and OPS [4]. A variant strain with roots in performance-oriented, knowledge-based expert systems (DENDRAL [3] and MYCIN [13]) embodies a major architectural difference In the use of rules. These systems treat rules as declarative knowledge structures to be interpreted; i.e., the production rules are only 1 piece of the total system (though the most important p iece). On the other hand, PSG-Iike systems have no declarative long-term knowledge; all knowledge is encoded as (procedural) productions, which combine knowledge with how it is to be used (control information). The tradeoff between the two views is essentially this: PSG-Iike systems have more flexibility in representing control Information (i.e., knowledge Interactions), but at the cost of greater difficulties than MYCIN-Iike systems in augmentation and permitting multiple use of knowledge.

PSAs show substantial promise for large artificial Intelligence systems (specifically, speech understanding systems). In [6) this promise is enumerated for the following set of concerns: adequacy of representation, space efficiency, time efficiency, directionality, augmentation, performance analysis, testing, debugging, and handling of error. Unfortunately, adequacy, space efficiency, and time efficiency (the three aspects reported on here) are probably the least promising of those listed. The more promising aspects were not within the scope of the research, though some of them are mentioned in Section 4 on "Remaining Questions".

3 . THE RESULTS

For sake of clarity, the results of the research are presented in the form of assertions. The assertions are stated in a strong form. A discussion following each assertion explains It and summarizes some of the supporting evidence. In cases where the evidence is weak, the assertion is qualified appropriately. Figure 1 gives a preview.

I. HSP productions are adequate for representation of aU HSII speech knowledge.

The basic evidence for adequacy* is that a large number (12) of HSII KSs were translated to HSP productions. There are nearly 20 other KSs which have been used at some lime throughout HSII's development, but a moderate acquaintance with them has turned up no reasons to doubt HSP's adequacy. Efficiency is another matter (e.g., see assertion 11 ).

·av adequ1cx we .do not mean lheorelie~l 1dequecy (which ie trivielly preaenl), but r~lher aomelhint we mithl Clll "repre11nl·lional prlclle~lity". W1 1l1o do not m .. n to lncludl lime efficiency, linea lhlt le con1idered ··p~rltely.

Representation and Architecture

1. HSP productions are adequate for representation of all HSII speech knowledge:
2. The adequate architecture of HSP is simple.
3. Translating HSII declarative knowledge to HSP creates problems of multiple use.
4. Explicit conditionality on changes Is a strong feature of HSP's architecture.

Space Efficiency

1. Procedural HSll knowledge decreases slightly In size when translated to HSP.
2. Declarative HSII knowledge Increases in size by up to half an order of magnitude.
3. Total HSII knowledge increases in size by up to half an order of magnitude.
4. HSP requires a much larger global working memory than HSII.

Time Efficiency

1. The Implemented time efficiency mechanisms In HSP are critical for Its viability.
2. The time cost of HSP relative to HSIIIs at least two orders of magnitude.
3. Local working memory and control are the prime sources of HSII time efficiency.

Flaur· 11 Results in Assertion Form

There were several minor difficulties encountered in the KS translation process, for example: iteration over WM element list fields, controlling duplicate actions, tallying events, and redundant arithmetic expression evaluation. Yet these difficulties are not serious enough to constitute a refutation of HSP's adequacy. Most of them could be solved through design iteration of the HSP architecture, without deviating from basic PS philosophy.

HSII KSs do a significant arrount of simple table lookup from local arrays c(Jntaining long-term knowledge. This might at first seem tc cause a representation problem for HSP, but actually an array translates cleanly into a rnutually exclusive set of productions, one for each entry. Direct indexing to select an array entry in HSII is essentially the same as selecting the correct production from the set In HSP. In other words, a PS is really a large, complex table lookup, while an array access is just an optimization of the lookup process that is possible with a highly uniform set of productions. However, a PSA is overly general for simple table lookup, the resulting space and time costs are discussed below under assertions 6 and 10.

The adequacy of HSP for speech understanding provides an additional data point for the broader question of adequacy of PSAs for artificial intelligence applications. More extensive evidence for adequacy has already been reported by Rychener [12], In his study of six classical artificial Intelligence programs. The speech understanding task of HSP has some characteristics that set It apart from Rychener's tasks: (1) a rich set of relatively independent knowledge sources, (2) each of which has a sound theoretical basis, providing lexicons of basic entities and rules relat:ng entities, and (3) the large direct recognition componP.nt, i.e., no need for extensive serial reasoning.

2. The e1deque1te e1rchitecture of HSP u 1imple.

This assertion is of Interest only in the context of assertion 1. Simplicity without assurance of adequacy is trivial.

Contrary to standard architectural practice for PSs, HSP has no conflict re1olution; i.e., on each cycle it fires ever' true production rather than using a conflict resolution mechanism to select a single production to fire. This permits in HSP a natural expression of the multiple, independent KSs that come from HSil and the speech task. Perhaps more Importantly, it allows much greater parallelism: while PSG, PSNLST and OPS respond to only a few changes and fire only a single production each cycle, HSP can respond to hundreds of changes and fire a hundred productions or more. However, such a feature could seriously impair a PS's ability to switch focus rapidly In response to a novel situation or new external stimulus [7~ But this does not seem worrisome for HSP since most of the multiple firings are operating in parallel on separate levels or time regions of the representation of the speech utterance.

In the absence of conflict resolution, HSP must occasionally resort to a somewhat Inflexible mechanism called an n-c,cle dela.y. This Involves a chain of productions that waits for other activity to finish by ":'·rking time for a certain fixed number of cycles.

HSP permits neither disjunctions nor negated conjunctions within production conditions. (Negations of single condition elements are essential and of course permitted). These restrictions simplify the production Interpreter without seriously affecting adequacy of representation. Disjunctions or negated conjunctions can be eliminated from a production by splitting it into several productions, at the cost of some decrease ir. space and time efficiency.

HSP has no mechanism for 1pecial ca1e inhibition; i.e., preventing a true production from fir ing when another production representing a special case of the first one is . also true. Such a mechanism would have complicated the production interpreter and probably caused a serious reduction in parallelism. Doing without special case Inhibition Is an Inconvenience. Either the more general production must be augmented to make it complementary to the related speciill cases, or special productions must be added to detect when both general and special case productions fire and favor the special case result.

3. TrClnlla.tinfl HSll decla.rative knowledfle to HSP create1 probt.m1 of multiple &.ue.

A basic feature of the HSP architecture Is the absence of any form of declarative long- term memory. Thus all long-term knowledge must be encoded as productions. Since each production specifies under what conditions its piece of knowledge Is to apply, there is a problem with using that knowledge under different circumstances. In some cases the problem can be solved by merely duplicating the knowledge, with a different product ion for each different use. This was done frequently in the HSP KSs, but will not extend to systems of growing complexity where multiple use can be expected to Increase. Subroutines of product ions provide another solution to the problem of multiple use. But subrout ines require a high degree of similarity of the uses, plus rigid conventions for communication. A third, somewhat novel, solution employed in HSP is to deposil knowledge temporarily into WM whenever there is a reasonable expectation that it may be useful. In WM it is then available in declarative form to whatever product ion wants to make use of it. It Is not known whether these solutions to the problem of multiple use would be adequate for much larger and more complex systems than HSII, but the suspicion is that they would not.

4. Explicit conditionrllity on chanflel i1 a stronfl feature of HSP's Clrchitectu.rP..

The first condition element of every HSP production explicitly tests the nature of a WM change, and must match a change made In the previous cycle. Thus a production cannot fire any lime its condition (excluding the first element) is true, but only when a part icular type of change (tested by the first condition element) occurs in conjunction with a true condil ion. (Normally, the change cau.1e1 the condition to become true). This explicit condition on a change has two important uses in HSP: ( 1) It provides the basis for a time eff iciency mechanism called the PM inde1e (see assertion 9). (2) It solves the ucitlltor, in1tability problem; i.e., a production cannot COI'!tinue to f ire cycle after cycle once become true, because it is also conditional on the occurrence of the change that made it true.

5. Procedural HS/l knowledfle decrea1es sliflhtl, in 1ize when tran1la.ted to HSP.

Detailed space analysis of the POM KS shows that about 160 Kbits of long-term HSII procedural knowledge translated to only .7 times that much in HSP. There are two possible explanations for this decrease: ( 1) Since HSP productions are interpreted, a more compact representation is possible; and (2) HSP can represent condition testing and searching of the global working memory more concisely. However, the explanat ion is probably more complex than this, as suggested by high variation of the HSP/HSII space rat io over eleven subparts into which POM was partit ioned for analysis.

6. Decla.re1tive HS/l knowledfle increa1es in 1ize by up to ho.lf o.n order of maflnitude.

HSII declarative structures are mostly either simple arrays, dictionaries of spellings, or linked networks, although all are encoded internally as arrays for efficiency. Arrays translate to HSP as one production per entry; the networks are typically represented by one production for each transit ion, or one production for all transitions out of each state. In any case, the number of productions required is large.

Seven instances of large declarative knowledge structures in the translated KSs were compared for size. Simple arrays require almost a factor of 4 more space in HSP, but sparseness can be exploited to reduce that factor by the fraction of non-default array entries. Tables of spellings (actually arrays of strings) have HSP /HSII space r alios of about 1. Two examples of network structures have the following ratios: 1.2 (grammar) and 3.2 (state transition network). The overall HSP/HSII ratio for the seven instances compared, excluding one exceptional case (a huge bit matrix), is 1.6.

HSP facilities for condition and action procedures allow a sequence of similar condition or adion elements to be packaged as a parameterized procedure and then referenced in many different productions with appropriate parameters supplied.* These procedures are crucial for representation of HSII declarative structures because of the large number of similar productions involved. In the HSP POM KS, condition and action procedures give a savings of a factor of 10 in the number of condition and action elements that must be represented explicitly.

7. Total HSII knowledge increases tn size by up to half on order of magnitude.

In HSII POM, with an overall HSP/HSII space ratio of 1.1, the declarative/procedural split for long-term knowledge Is .3/.7. But this is not a typical split. Many of the large KSs most recently added to HSII are estimated to be split about .9/.1. Assuming a .9/.1 split for a full HSII configuration would give an overall HSP/HSII ratio of 1.5, assuming the declarative HSP/HSII ratio to hold at the value of 1.6 obtained above. If instead we assume a declarative ratio of 3.8 (the worst observed), we get an overall ratio of 3.5. We cannot be more precise than this because the declarat1ve stru~tures of the new KSs have not been analyzed. Their rahos may well be larger than 3 .8.

8. HSP requires a much loq1er fllobol workirtfl memory than HSII.

Many HSII KSs use large local working memories in addition to the global Blackboard, and these local memories can be highly specialized for efficiency. HSP has only Its global WM, and specialization of it is strongly limited by requirements of generality and uniform accessibility. This difference In specialization costs HSP less than half an order of magnitude in space for simple data Items. For more complex data structures such as network nodes the cost can be as much as a full order of magnitude. Furthermore, such complex structures are so abundant that they dominate the overall cost.

9. The implemented time efficiency mechanisms in HSP ore critical for its viability.

Three existing time efficiency mechanisms in HSP give a combined speedup of 3 or 4 orders of magnitude over · naive Implementation (I.e., one that evaluates every production as a result of t.:very WM change, and that searches WM for every condition element evaluated). All three mecha11isms are suggested by analogs In the HSII architecture.

·rhe.. procedure ftcilitie· .,, purely for 1p1ct tfficiency. A production utina them bthtvll ···ctly 11 if til itt tlemenh were upltcitly written out; tJ<cept for 1 1111111 lime efficiency loll ill euianina pertmeltrt to v~ritbtee.

The first, called the PM indu:, reduces a linear dependence of execution time on PM size to sublinear by associating subsets of relevant productions (i.e., exactly those to evaluate) from classes of WM changes. In the HSP POM + RPOL run this resulted in a speedup of about 200.

The second mechanism, use of explicit pointers between WM elements, reduces the amount of WM searching during condition element evaluation. This mechanism does not reduce the degree of execution time dependence on WM si:ze, but does give a constant factor of roughly 10 to 50 overall speedup.

The third mechanism, an index into WM according to the first two fields of a WM element, serves to reduce WM searching costs. Since it operates in the shadow of the second mechanism which greatly reduces the necessity for WM searching, the WM Index makes only . a small contribution.

These mechanisms bring HSP to roughly the same level of time efficiency as PSG with filters [81 PSNLST, and OPS.

10. The time co.rt of HSP reloti11e to HSll is 11t least two orders of magnitude.

In equivalent unlprocess runs of the POM + RPOL KS conflgur at ion, HSP took 255 times as long as HSII (917 sec as opposed to 3.6). This factor of 255 reduces to a range of 6 to 36 when corrected for eight underlying system differences: execution rate of machine, Instruction set of machine, address space size, operating system, implementation system, degree of system kernel optimization, speech knowledge content, and complications of parallelism.

There are problems with the generality of this comparison since it is based on a single run of a small configuration (i.e., containing only the two KSs: POM and RPOL), and on only a single syllable of input utterance. Correcting for syllable length and atypicality of the KSs gives a rough overall time efficiency loss of two to three-and-a-half orders of magnitude for a full configuration of KSs in HSP.

Related data by Rychener [12] shows a factor of 6 to 10 loss In time efficiency for PS translations vs. original versions of six classic artificial Intelligence systems.

11. LocaL controL and worlcirtfl memory ore the prime sources of HSII time efficiency.

Since HSP has such limited local control (its actions are simple sequences and cannot call other productions), it must rely on data-directed Invocation operating from the global WM. Much of the data-directed invocation might be avoided if productions could be much larger, compressing multiple PS cycles into single ones. But this is made difficult by an accompanying blowup in the number of productions.

The cost of data-directed control in HSP has several sources: ( 1) the creation/deletion of change elements, (2) creation/deletion of control signals in WM, (3) PM

Indexing (finding productions to evaluate based on the changes), and (4) an initial portion of condition evaluation for each production that is necessary to reoblain the context of the preceeding production. The total cost of these Is estimated to be 30-45l of execution lime. In HSII the cost of data-directed control is 97. of execution time, and would be much smaller except that the cost is dominated by the monitoring of Blackboard change! rather than by the number of actual invocations.

The other side of the coin from local control is local working memory use. HSII makes heavy use of local working memory for KS efficiency. Since a PSA contains no analogous facility, HSP Is forced to use its global WM for such functions. Thi5 puts HSP at a serious disadvantage. The HSP run of POM + RPOL made over 5 times as many global working memory reads as a corresponding HSII run, and more than twice as many creations. Further, as mentioned above, there are other KSs that make much heavier use of local data than POM and RPOL. We expect HSP versions of these others would make hundreds of times as many global working memory reads and creations as the HSII versions.

Two other sources of HSP inefficiency are identified: ( 1) the absence of a declarative long-term memory facility, and (2) searching of WM. The former consumes 151. of execution time in the HSP run (but some of this overlaps with the WM access costs discussed above). The latter is insignificant (31.) because of the explicit WM element references, but is projected to increase to around 301. of total time with a full input utterance.

Taking all the sources of inefficiency together, we can account for roughly a factor of 7 in execution lime. This takes us well on the way toward explaining the normalized HSII-HSP difference of 6 to 36 obtained for the HSP run. But it also suggests there may be other sources. One such possibility is the limited power of the HSP production language, as exemplified by the inability of a single production to deal with a data list of arbitrary length.

4. REMAINING QUESTIONS

From the vantage point of the research done, several questions emerae as the important ones yet to be answered for a thorough evaluation of an HSP-Iike version of HSII. Six such questions are discussed briefly below. Given the current state of the HSP-HSII comparison (I.e., considering only adequacy and efficiency), with HSP faring rather poorly, it is natural to ask about factors that might swing the balance back toward HSP. Questions (1) through (3) below are of this nature. Questions (4) through (6), on the other hand, ask about possible weaknesses of HSP that need to be probed further.

1. Do there uist situations that raqui.re the lnhomogeneit~ of representation in HSP?

The HSP architecture is better suited than HSII to representation of inhomogeneous knowledge, e.g., knowledge containing many special cases. HSII's strong point is homogeneous encodings; when it is forced out of these It must fall beck on more expensive and ad hoc representations. This could turn Into a strong advantage for HSP If the drive for imiJrOved performance pushed In the direction of Inhomogeneity, as we suspect it may.

2. Co.n o. significant improvement in ease of o.ugmento.ti.on be realized in a PSA?

Ease of augmentation Is one of the most promising aspects of a PSA, so we need to show a significant advantage here to balance negative aspects such as efficiency. HSP's current architecture, lacking conflict resolution, may not properly support augmentat ion. If necessary, conflict resolution can be added to HSP, at the risk of sharply reduced parallelism.

3. /1 the level of individucl productions right for performcnce analysis?

Performance analysis at the level of productions can be accomodated easily in HSP. The only issues are whether that level Is a useful one (It is perhaps too low), and whether performance analysis at higher levels (always necessary) is made more difficult in a PSA. These issues can be resolved only by experience with larger KS configurations in HSP; the current two-KS conf igurat ion Is too small to provide any significant insight.

4. Do there or can there e,;ist HSII KSs which cannot be represented adequately in .HSP?

Since there are about 20 HSII KSs that have nol been translated to HSP, plus a virtually open-ended set of others which might conceiv:1bly be added to HSII, o'ur evidence for adequacy is incomplete. Particularly suspicious are some of the most recently added HSII KSs that use highly specialized local data structures. The current belief is that HSP is adequate for these, though Inefficient. A more thorough HSII-HSP evaluation requires evidence for this belief.

5. Co.n HSI/ " KSs that heavily rely on local ef/tciency ultimo.tely be made tractable in HSP?

We have seen that the bulk of HSP's efficiency handicap relative to HSII comes from HSP's lack of local working memory and control. It is impor tant to make some inroads on this handicap if HSP is to be useful, and several possibilities present themselves: (1) optimization in the HSP kernel of data-directed invocat ion and WM access mechanisms, (2) permitting productions to have complex actions with their own condit ionality and local working memory, and (3) compiling many PS cycles into one by combining production sequences Into many complex productions that act within a single cycle.

6. Is the distributed control of directionality as dictated by o. PSA feo.sibl.s?

Claims have been made that PSAs are unsuitable for representation of directionality control [9). Thus it is Incumbent upon us to prove them wrong if HSP Is to survive its comparison with HSII. HSII has a special ized focussing mechanism which operates with global knowledge of the state of the computation [5). In HSP we must show (if possible) that the requisi te global state Information can be represented in WM, and cont inually updated by a set of special added productions; and that task productions can be made to schedule themselves with additional condition elements sensitive to this representation of global state.

5. CONCLUSION

We have shown that the HSP architecture Is almost surely adequate for representing the HSII speech knowledge. This includes HSII declarative knowledge which must translate to procedural form in HSP. Adequacy of HSP was not a foregone conclusion because the simplicity of the HSP architecture compared to HSII gave grounds for some doubt about adequacy. Space and time efficiency are another story. The moderate space penalty for representing declarative HSII knowledge in HSP is cause for concern since HSII does contain many large declarative knowledge structures. Even more serious concern arises over space inefficiency of the global HSP working memory, since it must be used in place of large, highly optimized local working memories that are typical in HSII KSs. HSP's lack of local working memory also causes a large loss of time efficiency because of greater creation/read/write costs and heavier use of relatively inefficient data-directed control. HSP's large lime efficiency handicap (two to three-and-a-half orders of magnitude) exists in spite of efficiency mechanisms which make HSP comparable In time efficiency to several oth.~r PSAs.

The partial evaluation of a PSA for HSII reported here is unfavorable for the PSA, bul there are still other aspects (such as augmentation or performance analysis) that hold promise for PSAs. At least we have quantified the efficiency aspects so that a complete picture can be fit together as additional questions are answered.

A side benefit of this research is in providing enhanced understanding of HSII, a system which is a highly visible and Important contribution to artificial intelligence. By Investigation through HSP of marked alternatives to HSII's philosophy, we shed light on it. For example, we have contributed a better understanding of HSII's use of local memory and control for efficiency.

Another result of this research is the existence of another data point for the applicability of PSAs to artificial intelligence systems. The significant aspect of speech understanding thai distinguishes it from the domains studied by Rychener [12] is the heavy use of declar alive knowledge structures.

HSP demonstrates several novel features thai are of possible interest to designers of PSAs. We have shown that permitting multiple firings per cycle of the PS has appeal (at least for some tasks), and that eliminating conflict resolution does not necessarily cripple; that writing productions to contain explicit conditions on changes is a simple way to avoid repeated firing, and has efficiency benefits as well; that an attribute-value structure for WM and condition elements adds a useful bit of flexibility; and finally, that allowing WM elements to contain explicit references to each other dramatically cuts WM searching during evaluation.

Finally, we have shown that it is possible to obtain meaningful comparisons of related but different complex systems. The field of artificial Intelligence could benefit from more comparisons of this sort.