Speech Understanding Through Syntactic and Semantic Analysis

Introduction

In the first version of the SRI system for speech understanding, there were t hree major components: a set of procedures for syntactic and semantic analysis; programs for acoustic processing; and a word verifier rou tine that links the other two. Successive versions will include additional components and require major changes in all three of the present ones, as well as much more complex interre lationships. Nevertheless, this version of the system does illustrate an approach to speech understanding that is distinctive because of its dependence on syntactic and semantic processing .

The syntactic and semantic component, named Pintle, is a major modification (in ways described below) of Terry Winograd's system for procedural analysis of lan­ guage (Winograd, 1971). A grammar--wri tten as a set of programs--is combined with semantic routines that model changes in the arrangement of a set of blocks. A sen­ tence constitutes a path through the grammar. Branching at choice points is det e rmined by the order of the rules, by features on other constituents, and by semantic data. At the e nd of each branch in the parse tree is a set of words from a particular grammatical class (e.g., deter­ miners, adjectives, nouns, verbs), from which a subset can be sel ected on semant i c grounds.

The acoustic routines convert the recorded analog voice inpu t to digital form. The digitized signal is then fed into a bank of digital filters, which make it possibl e to assign successive acoustic segments to one of a set of small, crude, but highly r e liable classes. The signal a lso is processed by a more complex acoustic analysis procedure that identifies the frequency and amplitude for the first three spectral peaks of the vowel-like sounds. The parametrized data from these two analyses are stored in files.

The word verification routines take a set of words produced by Pintl e and test each word against the acoustic data for a particular portion of the utterance. The result is a (possibly empty) subset of the words, ordered according to agreement with the acoustic data, with each wo rd containing a pointer to identify its approximate endpo·int in the acoustic stream. Pintle takes the most likely word first and then proceeds on its path through the grammar to select the next set of words for processing by the wo rd verifier. Testing this new set against the acoustic data begins at the point designated by the endpoint for the word previously accep ted . If none of the proposed words agrees with the acous tic data, Pintle backs up to the most recent choice point and tries another alternative.

An example is considered next, and a more detailed description of each o f the components is presented in Sect ion I I I.

Understanding a Sample Sentence

A brief description of the "blocks world" problem domain used in the SRI system is necessary as background fo r the analysis of the sample sentence. Visualize a tabl e containing a box and several objects of different sizes, shapes, and colors. There are five blocks (two red, one black, one green, one blue) and three pyramids ( green, blue, and red); the box is white . The objects a re arranged in a particular configuration in the com­ puter representation of the scene, but the details of the arrangement are not necessary to understand the exampl e . Commands given to a simulated robot arm cause it to move the blocks. Alternatively, the person inter­ acting with the system can ask questions or provide information that will augment or change the semantic

structure of the world in some way.

PUT THE BLACK BLOCK IN THE BOX.

It was recorded, digitized, and parametrized in advance , and the results stored in a fil e that was loaded into the system for the test. Al l of the steps involved in its analysis are presented as they occurred in an acutal demonstration . The capabilities shown reflect the state of the system as of December 1972 . (The speech under­ standing system is implemented in BBN- LISP and is run on a PDP-10 computer under the Tenex Operating System. Lines prefixed by an arrow represent entries by the use r . )

~#(PUT THE($ 37) ($ *) IN THE($ 134) . )

Analysis of the sentence by Pintle is initiated . At the time this protocol was made, the word verifier did not have word functions available for the sets of words including PUT, THE or IN. Under these circum­ stances--and in general to a l low more flexible testing of the system--it is possible to enter text to specify a word. For convenience, the word verifier checks the input text first to see whether any of the words in the set predicted has been typed in. Finding none, it will use the appropriate word functions, if they are avail ­ able. If none are present, the words in the set will be rejected .

PUT

Pintle begins by looking for a major clause; branching along the imperative path, it looks for com­ mand verbs. The word PUT is among those in the set generated at this point, and it is found in the text input .

THE

Having found a verb, Pintle begins its s earch for a noun group by looking for a de termine r. THE is confirmed from the text input.

BLACK

Having found a determiner, Pintl e looks for an adjective. Since there is no text input, the pre­ dicted words are t ested against the acoustic data . Beginning at a location 370 milliseconds into the utterance (the 37th 10- millisecond segment), the word verifier finds that BLACK corresponds to the acoustic data at the highest of four confidence levels; RED, GREEN, BLUE, and WHITE are rej e cted.

BLOCK

Pintle now looks for a noun to complete the noun group. It begins at the location in the acoustic data confirmed as the ending place for BLACK, the previous word accept ed. This condition is specified by the asterisk in the initial entry for the sentence to be processed. The word verifier finds that BLOCK corre­ sponds to the acoustic data at the highest confidence level; BALL, PYRAMID, and THING are r e jected.

With the noun group complete, Pintl e looks for a prepositional phrase to complete the action denoted by PUT. IN is confirmed from the text input.

THE

Looking for a noun group to complete the preposi­ tional phrase, Pintle begins with the determine rs. THE is confirmed from the text input.

BLACK

Pintle next looks for adjectives. Beginning at a location 1340 milliseconds into the utt e rance (the 134th segment), the word verifier finds that BLACK corresponds to the acoustic data at the third highest confidence leve l. RED, GREEN, BLUE, and WHITE are r e jected .

BOX

The location returned along with BLACK proves to be the end of the utt e rance . Consequently, BLACK i s rej ecte d because the string so ending would be un­ grammatical; it also would be semantically unacceptable. Pintle backtracks and begins looking for nouns . BOX corresponds to the a coustic data at the hi ghest con­ fidence leve l; BALL, PYRAMID, and THING are reject ed.

(PUT THE BLACK BLOCK I N THE BOX)

The s entence as identifi ed. At this point the system returns a printout showing the grammatical structure of the sentence.

(CLAUSE MAJOR IMPER ACTV TRANSL)

(VG IMPER)

PUT (INF PAST VB TRANS VPRT MVB)

(NG OBJ OBJl NOLOC DET DEF NS)

THE (DET NPL NS DEF)

BLACK (ADJ)

BLOCK (NOUN NS)

(PREPG PLACE LOBJ)

IN (PLACE PREP)

( NG OBJ PREPOBJ DET DEF NS)

THE (DET NPL NS DEF)

BOX ( NOUN NS )

Briefly summarized, the sentence is identified as an active imperative with the verb PUT, involving the movement of an obj ect, THE BLACK BLOCK, to a locat ion, IN THE BOX. (Se e Winograd, 1971, and Walker, 1973, for more extended discussions of the grammatical structure .)

This information is used to direct moveme nts of the simulated robot arm in conjunction with the semantic definitions for the words and the determination of their relevance for the current state of the problem domain, as indicated in the following steps.

MOVETO 472 192 128

The arm moves to the black block, specified by the three coordinates given .

GRASP :B3

The arm grasps B3, the black block .

MOVETO 448 448 129

The arm with the black block moves to the box, specified by the three coordinates.

UNGRASP

The arm releases the black block inside the box.

OK

The system indicates that it has completed the action identified in its "understanding" of the input utterance.

Provisional Features of the Implementation

In anticipation of a more detailed discussion of the system components in the next section, it is prob­ ably reasonable to note here some characteristics of the analysis of the sample sentence that were temporary expediencies even in this version of the system.

The system was not totally on-line; i.e., it was not possible to speak direct ly into the system and to initiate processing accordingly. Analog-to-digital conve rsion of the speech signal cannot be performed on our PDP-10 / 15 computer facility yet, pending completion of the necessary software. Consequently, the signal was digitized on a PDP-11 and the resulting files transferred by tape to the PDP-10 for the rest of the acoustic analysis.

The FORTRAN files accessed by the word verifica­ tion routines contained preprocessed data from both the digital filters and from the more complex analysis. Initially, we expected that in the final system we would only produce immediately on input the pre liminary classification of acoustic segments provided by the digital filters. Spectral analyses and other compli ­ cated acoustic processing were to be performed only as required to make the kinds of decisions necessary to distinguish among the predicted words in relation to the acoustic data. It now seems likely that complex analyses can be done in real time, so that we can get a riche r parametric representation of the utterance. Howeve r, we still do not want to make specific classi­ fication decisions apart from the word verification procedure.

As noted in the analysis of the sample sentence, only a small number of word functions were written. Consequently, this version of the system was never used to process a complete sentence. The option of testing predicted words against textual, as well as acoustic, data proved useful for debugging the acoustic routines for particular sets of words . It also is useful in the absence of semantic and prosodic pro­ cedures for establishing cons t raints on paths through the grammar at the beginning of utte rances, and, in particular, at the begi nning of a dialog when no context has been established.

A final comment on the analysis embodied in the sample sentence is probably in order . We did not exercise this fir~t ve rsion of the speech understanding system to any great extent . There were only a few word functions, and they were tested against only two speakers. The flow of control was primarily from the syntactic and semantic component to the acoustic. It was clear from the beginning, however, that useful informat ion could pass in the opposite direction, not only from what a prosodic analysis mi ght provide, but also from what might be expected to arise in the course of testing words against the acoustic data. In addition, we envisioned ways in which the word verifier, which in this version of the system processed one word at a time, could operate more efficiently on the whole set of predicted words in relation to the acoustic data, thus reducing the search space involved.

COMPONENTS OF THE SYSTEM

Pintle--Procedures for Syntactic and Semantic Analysis

Pintle, the syntactic and semantic component of this version of the speech understanding system, is based on the Winograd "computer Program for Under­ standing Natural Language" (Winograd, 1971) . It is a top-down system for linguistic analysis in which syntax, semantics, and inference are combined to direct the · processing of quest ions, statements, and commands. As impl emented by SRI in BBN-LISP, Pintl e constitutes a substantial modification of Winograd's program.

In Winograd's work, as in most existing parsing systems, successive words from a typed input string guide the analysis. Since we proposed to use the parsing procedure to help segment and identify the words in the speech input, it was ne cessary to find other ways to control the generation of paths through the grammar. So syntactic and semantic constraints were established to influence successive choices, l eading to the selection of a subset of the words of a particular word c l ass. In what follows, the infor­ mation available in the grammar for this purpose is presented, with an explicit identification of the as­ sumptions required for effective use of the system in this context, and with some additional elaborations where appropriate .

Consider again the sample sentence discussed in the previous section, PUT THE BLACK BLOCK IN THE BOX.

Assuming that at the time this utterance is made in a hypothetical dialog of a user with the system it is reasonable to expect a command, the clause program would look for an imperative . Semantic information would be critical here, but knowledge about the use r also would be helpful, and prosodic data--discussed f urther be low--could provide useful guidance. Since imperative clauses generally start with verbs, the parser enters a verb group program looking for impera­ tives. Since imperat ives are in infinitive form, only those verbs with that featu r e are identified. The re­ sult of this path through the grammar is a small set of imperative verbs, one of which may correspond to the first word of the utterance . We expect to be able to constrain the set of verbs further by additional semantic information--perhaps regarding what command might be appropriate at this point in the dialog. And information specific to a particular user should be possible to capture; for exampl e , the frequent use of certain commands. However this verb group is con­ strained, the initial result is a set of words to check against the acoustic data .

Confirming one (or more) of the words from this initial set might result in Pintle looking for a noun group, as is the case with the word PUT, which requires an object. The use of the word "might" is deliberate, to indicate the possibility of alternative choices . Identif ication of a diffe rent imperat ive, PICK, could result in Pintle looking first for the particle UP. Accepting PUT in the sample sentence, Pintle might be­ gin the search for a noun group with a determiner. Since the set of determiners is small , off of them could be predicted. However, they are difficult to distinguish acoustically, and it might be r easonable , on semantic grounds, to look only for a definite or only for an indefinite determiner, e . g . , THE or A.

Finding a determiner, an adjective would be like ly to fo llow. There are various classes of adjectives, and in English there is an ordering controlling the sequence in which they typically modify a noun. For instance, size adjectives precede color adjectives; e .g. , BIG RED BLOCK but not RED BIG BLOCK. Again, in a dialog it would be reasonable at certain points to predict the amount of specificity required to identify an object on the basis of its qualities . Furthermore, some people may make things perfectly clear, while others are more sparing in their characterizations. Having models of the users could be valuable for pro­ viding t his informat ion. So, sets of adjectives would be checked against the acoustic data. Subsequently, and in a similar fashion, various paths among the nouns would be selected for testing . The kind of verb would influence the choice; verbs of manipul at ion call for nouns that represent manipul able objects . This infor­ mation also could be used to influence the choice of an adjective in the prior search, limiting it to those adjectives appropriate to manipulable objects.

Continuing the parse beyond the noun group wou ld lead to consideration of preposition groups because PUT requires a location. Identifying a place prep­ osition would lead to a search for an object noun g roup, with decisions being made similar to those dis­ cussed for the preceding noun group. Howeve r, only those nouns that can have obj ects PUT IN them need to be considered .· In this manner, a set of predict ions can be made regarding the sequence of sets of words like ly to occur in the u tterance .

The foregoing description presume s the accuracy of the initia l predictions. In the sample sentence, however, the adjective initially found in the second noun group proved to be in error. Thus, backtracking a nd tracing down an alternate path were required to find the noun. An interpreter for PROGRAMMAR was added to provide a backtracking mechanism not available in Winograd ' s system (and not necessa ry for Winograd, see below). The interpreter made it possible to specify a set of alternatives at a particular point in the g rammar and to try these in succession, backtracking automaticall y if the initial choice was not subsequently confirmed. This same mechanism made recovery possible following acceptance of a word that proved to b e in e rror , as in the sample sentence .

The requirement for speech input (the absence of words with identifiable features in the input string) and the availability of the backtracking facility re­ sulted in other modifications to Winograd's analysis procedure. Winograd teste.d to eliminate the least likely alternatives first, checking the longest pos­ s ible constituent and cutting back when that failed . PROGRAMMAR, in his original version, returned the first s uccessful analysis, having provided both syn­ tactic and semantic guidance to make that a likely interpretation within the model of the "blocks world. " Selective backup was possible in a particular situation, but it involved specifying a location to return to for a l ternative processing. With voice input, it is nec­ essary both to test for most like ly al ternatives first and to have a more general mechanism for following alternative paths through the grammar in case of fail­ ure. What i s needed further for speech understanding is the flexibility in the g rammar to allow dynamic reorde ring of rul es, depending on the state of the analysis at the moment. It wou l d be desirable to be able to identify at any particular choice point in the grammar the a l ternatives that are possible . In Wino­ g rad's system, alternative choices could only be identified serially after failure Of the predecessor.

Many more changes in the overall parsing strategy are needed to improve its ability to use syntactic, semantic, and- -hopefully--pragmatic constraints to make accurate predictions about the words likely to be present at any particular place. In Winograd and in our first version, checking against the actual configuration of obj ects on the "blocks world" could be done only after a group had been parsed. Thus, in the sample sentence, both BALL and PYRAMID were tested against the acoustic data. However, there were no balls in that configuration (although the word was in the lexicon), and there were no black pyramids. Infor­ mation of this kind can and should be used to influence the selection of words in a set as soon as it is relevant.

The introduction o f new structures for managing semantic and pragmatic information could be expected to have major consequences for parsing. It certainly is necessary to replace Winograd's MICROPLANNER code; exploratory development has been done using QA4, a procedure-oriented programming system particularly suited for work in artificial intelligence because of its flexibility and special features (see Rulifson, Derksen, & Waldinger, 1972), With revisions to the par­ ser in QA4; new techniques are necessary to facilitate the accommodation of semantic and pragmatic information and to simplify the dynamic reordering of paths through the grammar, At various times up to this point, prosodic infor­ mation has been mentioned. Knowledge abou t stress, intonation, and pauses should be valuable in any speech understanding system, but it assumes special importance in an approach like ours . Prosodic data perform some of the f unctions for spoken language that punctuation does for text. Intonation contours can suggest sen­ tence type--question, command, statement; together with stress and pause they may help identifying clause and phrase boundaries and signal parts of an utterance with particular semantic import ( see O'Malley, 1973). Our system requires contexts (of various kinds) for useful prediction. Prosodic information may provide guidance at the beginning of a dialog or even of an utterance when other kinds of constraints are less effective.

Acoustic Processing

The speech data currently used in the SRI system are obtained in a quiet room using a B&K 433 condenser microphone and an Ampex AG 500 tape recorder. An ana­ log tape is produced at 7-1/2 inches per second record­ ing speed. The speech data on the tape are then digi­ tized in segments of up to 3.1 seconds in length. A presampling low-pass filter with an 8-kHz bandwidth is employed to reduce aliasing errors, and the digi­ tization is accomplished by a 12-bit A/D converter operating at a rate of 20,000 samples per second,

The raw digita l data are processed further by digital fi ltering . Five rms ·values (root-mean-squa r e, an energy measure) of the time series data are calcu­ lated in each 10-millisecond interval of time. The first provides an amplitude value for the unfiltered time series . The other four values are from digital filters with bandpass characteristics of 80-200 Hz, 300-1000 Hz, 500-2800 Hz, and 3.2-6,8 kHz. A linear predictive coding (LPC) analysis, using an algorithm developed by Markel (1971), provides formant frequen­ cies and amplitudes by finding peaks in a 128-point spectrum.

In the first version of the system the strings of rms values were us ed in an algorithm that cla~sified each 10-millisecond time segment as one of six events: silence, unvoiced turbulence, voiced turbulence, voiced stop, vowel-like, none of the preceding. The filter outputs and preliminary classifications of each segment are stored in disk files together with the formant frequency and amplitude data from the LPC analysis.

Word Verification

Procedures for word verification relate the words predicted by syntactic and semantic processing to the acoustic data. The input to the word verifier from Pintle was a set of words that could be expected to occupy the next position in the utterance. The result of word verification is a subset, possibly empty, of the candidate wo rds ordered according to degree of agreement with the acoustic data at that location in the utterance.

Since Pintle was written in LISP and the acoustic processing is done in FORTRAN, it was necessary to develop procedures for communication between the two languages. An interface package makes it possible for a LISP program to create a fork (an independent process in the time-sharing system) containing a FORTRAN pro­ gram, to share directly accessible data with that pro­ gram, and to call functions in that program according to standard FORTRAN conventions.

For each candidate word, there is a function that tests for that particular word. The correspondence be­ tween the expected form specified in the function and the contents of the acoustic stream is expressed as one of four confidence l evels : positive, possible, unlikely, and impossible. For the first three l evels, the f unc­ tion also returns an estimate of the e nding position of the word in the acoustic stream.

The word verifier collects the results for each word in a set, e liminates the impossible words, and constructs a list ordering the rest of the words according to confidence level. The word with the high­ est ranking is returned to Pintle; any others are saved on a backup list to be used successively if their pre­ decessor does not lead to the prediction of a new set of words, one or more of which can be found in the utterance. The ending position of the accepted word is used as the starting point for testing words in this new set.

To illustrate the word verification procedure, con­ sider the word BOX in the sample sentence. It was one of the words predicted by Pintle at a location begin­ ning approximately 1.34 seconds after the beginning of the utterance . The word function for BOX produced the following actions:

1. Increment the time pointer by 170 milliseconds.
2. Attempt to find a vowel-like string in a 200millisecond window centered at the incremented time pointer .
3. If Step 2 is successful:
4. ( a) Search for a voiced stop ahead of the vowel-like string ,
5. (b) Search for silence at the end of the vowel-like string . If a silence is found, search for unvoiced turbulence after the si lence . Return a confidence leve l, where appropriate, for each search.

• 4, Examine the vowel-like string as follows:
• (a) Calculate the average frequencies of the first and second formants.
• (b) Calculate the average slope of the first and second formants,
• (c) Look for discontinuities in the first and second formants .
• If the r e are significant discontinuities or rapid changes in formant frequencies, r e turn the value impossible.
• Combine the results of the consonant search from Step 3 and the analysis of the vowel-like string in Step 4 as follows:
• (a) If the average formant frequencies are reasonable for the vowel [a] and all consonant searches are successful, re­ turn positive.
• (b) If the average formant frequencies are reasonable, but a consonant search failed, return possible.
• (c) If the average formant frequencies are unreasonable but all consonant searches are successful, return unlikely.
• (d) If the average formant frequencies are unreasonable and at least one consonant search failed, return impossible,

In the example, the confidence level for BOX was positive. The results showed a vowel-like string with first and second formant values consistent with [a] in the interval 1420 to 1600, a voiced stop before the vowel-like string in the interval 1340 to 1410, silence after the vowel-like string from 1650 to 1690, and un­ voiced turbul ence from 1690 to 1910.

It should be clear that a word verification pro­ cedure of this kind was designed for use in a system with powerful syntactic and semantic constraints . In the analysis of the second noun group in the sample sentence, before BOX was confirmed, a set of adjectives was processed by the word verifier. All of the words were rejected except BLACK, for which the confidence level was unlikely. Pintle accepted BLACK tentatively, but that would have had to be the end of the sentence, and PUT THE BLACK BLOCK IN THE BLACK is syntactically and semantically unacceptable in the current system. Consequently, Pintle backtracked and looked for nouns. Of the set predicted, BOX was confirmed with the high­ est confidence l evel . If BLOCKS had been a member of that set, the word ve rifier might have returned positive as well. However, since things cannot be put in blocks, that word would be excluded, on semantic grounds, from the set to be considered.

It is obvious that the word verification pro­ cedures in this form would not allow subtle discrimina­ tions. Howeve r, the addition of more complex and powe rful acoustic/ phonetic rules to the analysis and decision-making parts of each word function should per­ mit significant expansions of the system capabilities . The word verifier strategy is particul a rly appropriate for our system design, since the syntactic and seman­ tic decisions involve words rather than phonemes, allophones, or other phone-like units. Furthermore, the word verifier provides a way to deal with a sig­ nificant subset of coarticulation problems that would be quite troublesome in a phoneme-verifier approach, To a considerable extent, changes in the word verification procedures depend directly on increasing sophistication in acoustic proc~ssing. However, as indicated in the previous section, the need is not for new techniques for acoustic analysis but rather for ways to extract more information from the data we have. Furthermore, we believe that the motivation for changes should come primarily from the requirement~ of word verification. Our current efforts are directed toward providing more subroutines for acoustic parameterization in order to refine the initial classification provided by the digital filter analysis and to provide additional formant data. For example, detectors have been added that allow fricatives to be distinguished reliably, so that s, sh, f-th, and their voiced counterparts now are classified, We also have developed vowel seg­ mentation and classification procedures that extract boundaries within vowel-like strings, smooth formant curves, and plot slopes and standard deviations of formants. Our goal is to provide a variety of general procedures that can be used in the preparation of word functions for use in word verification.

DISCUSSION

The major focus in this paper has been on the rol e of syntactic and semantic analysis in our speech unde rstanding system- - and appropriately so for pre­ sentation at a conference on artificial intelligence. But in describing the first version of the system, we have emphasized the inadequacies of that imptementation and the r e quirements we see as necessary in succeeding versions. Probably the major result of this early work is the design of a parser that we believe can accommo­ date al l of the sources of knowledge required for un­ derstanding speech. It is described in detail in the paper by Paxton and Robinson (1973) presented at this Conference . Such a parser would be well suited to the word verification procedures and the kind of acoustic processing performed in our system ..

Another result of our first year is an appreciation of the interdependence of the task domain and the sys­ tem design, A system like ours, which stresses syntax and semantics, is particularly appropriate for conver­ sations with a person that involve some relatively com­ plex task and that require a sequence of interactions. Dynamic changes in the situation reflecting progress toward some goal can provide the kind of semantic con­ straints that will improve the accuracy of its pre­ dictions. The "blocks world" is relatively shallow; it does not easily accommodate dialogs of the kind desired. Consequently, we have changed our task domain to the assembly and repair of small appliances, begin­ ning with a l eaky faucet. In the course of modelling this world and establishing the knowledge necessary for its understanding, we will be addressing problems central to the whole field of artificial intelligence.

Our proj ect can benefit from any work in artificial intelligence that illuminates semantics, pragmatics, and the process of representation. Of course, we will not rej ect insights that reflect on acoustics, phonetics, prosodies, and ancillary aspects of linguistics. We do need to address all of these facets for a successful system, but we certainly cannot expect to solve a ll of the problems ourselves.

ACKNOWLEDGEMENTS

The following people have been involved in the re­ search on speech understanding at SRI refl e cted in this paper: Sharon Baranofsky, Dick Becker, Steve Coles, Earl Craighill, Mike Hecker, Grant Hoyt, Bob McPartland, Bill Paxton, Tito Poza, Ann Robinson, Jeff Rulifson, Jim Young. We are also indebted to other participants in the ARPA Program on Speech Understanding for the per­ spectives they have provided.