The Vocal Speech Understanding System

Introduction

This paper describes the present state of the VOCAL speech understanding system. Briefly, VOCAL is a complete, self-contained speech understanding system that has undergone sufficient testing to in­ dicate that it has potential both as a practical voice programming system and as a research tool for the investigation of more general problems of nat­ ural, spoken man/machine communication.

VOCAL interprets a spoken utterance as the well formed, meaningful sentence that sounds most like its acoustic transcription of the input ac­ cording to a quantitative similarity measure and demonstrates its understanding by compiling the in­ put into executable machine language code. To ac­ complish this, VOCAL uses several relatively simple procedures linked by a control structure. The VOCAL language was designed to be simple and power­ ful in specifying numerical algorithms. Within the constraints of small vocabulary and simple syntax, the VOCAL language bears a reasonable similarity to the special subset of English used by a mathemati­ cian to describe equations he is writing on a black-board. Finally, VOCAL is fast, efficient,

and portable.

VOCAL operates on a limited vocabulary, as all speech understanding systems do [1,15,16,20,21,22, 23]. Sentences are spoken by cooperative subjects in quiet rooms. The VOCAL syntax is well defined by a mathematical model and the problem domain is limited to a specialized task so that heuristics

for semantic analysis are applicable .

VOCAL does not, however, accept truly continu­ ous speech input. Our data was recorded under i­ deal conditions and the subjects were required to articulate clearly. Thus VOCAL can reliabl::,· !~::ate

Stephen E. Levinson Yale University

New Haven, Connecticut USA

word boundaries by detecting brief pauses between words. As a result, VOCAL begins its acoustic processing at the lexical rather than the phonemic level.

There are 42 words in the VOCAL lexicon ("to" and "two" are considered the same word at the a­ coustic level) so that word identification becomes a difficult but tractable pattern recognition problem.

At the acoustic level, VOCAL represents lexi­ cal information in the form of a spectrogram. An extremely efficient Fast Fourier Transform (FFT) generates the spectrogram, which contains all the information necessary for word recognition in suf­ ficiently compact form so that the full power of mathematical pattern recognition techniques can be brought to bear. (Very early work by Potter, Kopp, and Kopp [14] and recent verification by Klatt and Stevens [7] demonstrate that a spectro­ gram can contain all this information, although the more recent trend in acoustic signal process­ ing has been toward digital filtering [17] and predictive coding [8,12,23] for spectral estima­

tion.)

In order to solve the grammatical problem of parsing unreliably transcribed input strings [11, 22], the parser is permitted to insert hypotheti­ cal words or strings based on acoustic and seman­ tic information while processing the input.

The difficulty often encountered is providing a speech understanding system with semantic capa­ bilities was partly solved by the choice of prob­ lem domain. Cherry [3] defines semantics as the relationship between the symbols of a language and the real objects or concepts for which they stand. For the VOCAL system the objects to which the sym­ bols are related are sets of machine language in­ structions that cause the computer to perform the operations specified by those symbols. The seman­ tic relationships are those required by an ordin­ ary compiler for the VOCAL language.

The control structure of VOCAL has two im­ portant properties. First, information extracted at each level of processing is used by every other level. Second, the actual strategy used by VOCAL to understand a sentence is largely determined by that utterance of that sentence. In this process, no absolute quantitative criteria (e.g . empirical­ ly determined confidence levels) are used and no unbounded computations (e.g. exhaustive searches) are performed.

Finally, there is the matter of the cost of speech understanding computations in processing time and resources. Because VOCAL is coded in FORTRAN at a level very close to the machine and uses efficient FFT, pattern recognition, and pars­ ing algorithms, it has only modest core require­ ments and will run on-line in real time on large minicomputers or medium-size machines. If the spectral analysis is performed by an easily con­ structed bank of five analog bandpass filters, the system can run on-line in real time even on a small minicomputer. This opens up avenues for testing, evaluation, and development that are closed to lar­ ger systems.

The VOCAL System

VOCAL is currently organized into one main program and six subroutines. The main program, called CNTRL, governs (and records for subsequent analysis) all of the operations of the subroutines. The subroutines and their tasks are listed below.

1. SPGRM generates the Spectrogram of single­ word utterances.
2. SWIFFT is a special purpose Fast Fourier Transform algorithm used to compute short duration spectra.
3. KNN3 is the pattern recognition algorithm. It uses a generalized k-nearest-neighbor scheme with preprocessing [13).
4. PARSE is a push-down automaton that not only accepts well formed sentences but also makes hypothetical insertions where the acoustic tran­ scription leads to an ungrammatical strin~.
5. SEMANT forms hypotheses about the meaning of a sentence from clues it finds in the acoustic transcription and grammatical structure.
6. COMPIL generates machine language code corresponding to the final interpreted meaning of input sentences. Unfortunately this routine is machine-dependent, so it now stops short of gener­ ating the actual machine language code and merely sets up the internal form representation from which the code can be generated.

Acoustic Processing

SPGRM performs all of the signal processing re­ quired to segment the speech along word bounaries and produce a compact representation of the spec­ trograms of each of the words.

Word boundaries are located by a simple thresholding technique. When the signal drops to a relative minimum and remains at that level for sev­ eral consecutive samples, a word boundary is as­ sumed.

The first stage in the generation of a spec­ trogram is the sampling of the short duration spec­ trum of the speech waveform every 3.2 msec. and storing the results in a matrix S = (Smn) given by equation (1).

where: contiguous samples of the speech waveform {Xk}={ for0$k $ 3l

{Wk} are the prolate spheroidal weighting coefficients of Eberhard [4].

The computation of equation (1) continues for in­ creasing m until all the samples within the word boundary are used.

The matrix S defined by equation (1) is then reduced to a more compact formS' z (S~n) by aver­ aging its entries over predetermined time and fre­ quency intervals according to equation (2).

where

and where ti z [iM/10) i · 1,2, .·. ,10; [*) is the greatest integer function and {bi} · 3,7,12,20,32 This choice of {bi} results in band pass filtering the original speech waveform with a bank of con­ tiguous filters having cutoff frequencies of 450, 900, 1800, 3000, and 5000 hz. The choice of {ti} simply partitions the spectrogram into ten equal time segments.

Finally, the S' matrix is normalized by its largest entry to produce the matrix S" z (~n) given by equation (3).

The result of these transformations is a 5xl0 matrix that represents the normalized time and frequency smoothed spectrogram of a single spoken word.

The discrete Fourier Transform (DFT) implicit in equation (1) is actually performed by the special-purpose FFT algorithm of subroutine SWIFFT. The desired speed is achieved in this al­ gorithm by employing all of the following tech­ niques:

1. Real transform of length N computed as a com­ plex transform of length N/2
2. Mixed radix representation of subscripts [2,19]
3. Pruning the first stage to account for the zero padding [9)
4. Elimination of all trivial operations (e.g. multiplication by 0, ±1)
5. In-line coding with no loops and no address calculations
6. No explicit binary sort.

Pattern Recognition

KNN3 is the pattern recognition subroutine . It performs two separate operations, feature selec­ tion and nearest neighbor ordering, implicit in which is the identification process.

The feature selection process is accompl ished by means of a Karhunen L~ve expansion applied to feature selection problems according to methods described by Meisel [10] and Patrick [13]. Recall that the spectrogram for each word is represen~ed by the 5xl0 matrix, S", of equation (3). Let Y be a 50-vector whose components, Yi 1 s i s 50, are the elements 5!J S" ordered columnwise. We re~ce this vector, Y, to a ten-dimensional vector, X, by the linear transformation T.

T is a matrix whose rows are the eigenvectors cor­ responding to the ten largest eigenvalues of an estimate of the covariance matrix U of the training set. That is,

The yi are estimates of the mean of yi computed from

In equations (5) and (6) the summation is over all M samples in the training set.

Finally we take U computed from equation (5) and solve the eigenvalue problem.

The Ak are estimates of the variances of the kth !eature in the direction of the kth eigenvector, qk, and are the eigenvalues of U. The matrix Tis then expressed as

Of course, the computations described by equations (5), (6), (7), and (8) are done only once in an off-line step and the matrix T is stored in KNN3, which simply uses the transformation according to equation (4) to get a ten-feature representation of a spe.ctrogram.

An examination of the eigenvalues of U from equation (7) reveals that the intrinsic dimension­ ality of the feature space is between 6 and 16. That is, Ak becomes very small for k · 16. But in order to keep the implicit estimates of the proba­ bility distribution function of the feature values consistent with the number of samples in the train­ ing data, we restricted ourselves to a ten-dimen­ sional approximation.

~ The next function of KNN3 is to use the vector X from equation (4) in the generalized K Nearest Neighbor decision rule of Patrick [13] to classify an utterance.

where n is the class of the vector X, j = jth component of the neighbor to X in the 7 and 1 s n s 42. index, Xj is the jth component n(k) 1,2, .·· ,10, and xj is the vector of the kth nearest nth class. We have fixed k =

The decision ~ule of equation (9) simply says assign the vector X to class n if and only if~the total distance (in the Euclidean sense) from X to its k nearest neighbors in the nth class is less than its total distance to its k nearest neighbors in any other class.

In order to use the decision rule of~equation (9a) a set of discriminant functions {d 0 (X)} 1 < n < 42 are evaluated where

Then the {d <'x>} are sorted in ascending order so that n

_. The significance of the ordering (9c) is that X is classified as n1, but n2 is the next most likely candidate, followed by n3, etc. This in­ formation is stored for later use by PARSE and SEMANT.

The naive implementation of this algorithm requires one distance calculation for each train­ ing sample. But carefully reordering samples within each class and storing their positions on each axis can eliminate many distance calcula­ tions because it is known in advance that they cannot be candidates for nearest neighbors. This preprocessing technique outlined by Shustek et al. [18] greatly reduces the computation cost of im­ plementing equation (9a).

Syntax

PARSE is the subroutine that performs the neces­ sary analysis for understanding a sentence. PARSE also serves as a "front end" for the final compilation of subroutine COMPIL.

VOCAL has 43 symbols and eleven different sentence schemata, most of which have two forms. The first form permits the use of line numbers, which COMPIL treats as instruction addresses. The second form is a "stand alone" form in which each sentence is a complete program unto itself. These command structures are of three types, executive (e.g. start, stop, edit), minor utility (e.g. unconditional branching, subroutine linking, input), and major utility (e.g. conditional branching, assignment, indexing). The third are the real work horses of the language and contain arithmetic expressions composed of variables that may or may not be subscripted, floating-point con­ stants, and all the usual arithmetic operators, delimiters, and elementary functions.

The VOCAL language L(G) is generated by a context-free grammar, G(Vn,Vt,S,P), where

Vn is a set of non-terminal symbols Vt is the set of terminal symbols (i.e. the VOCAL alphabet) S is a start symbol S E Vn P is a set of production rules of the form

where V* implies the set of all strings of elements of v.

There are 192 productions of the form of e­ quation (10) in the VOCAL language so that the language is specified in the Greibach normal form [5]. In addition, we have the constraint

Equation (11) insures that the grammar G(Vn,Vt,S,P) is deterministic and can therefore be accepted by a deterministic push-down automaton. M(Vt,Vn, S,6) where Vt is the VOCAL alphabet Vn is a set of stack symbols s is the initial stack symbol

6 is a transition function I 6: (V t x Vn) -+ v~

so that whenever p:a-+Aa, there is an entry in 6 of the form:

(12) 6(A,a) · a.

Equation (12) then defines the operation of M as follows. On scanning input symbol A with non­ terminal symbol a on top of the stack, accept A and replace a by the string a . If the stack is empty after the input sentence has been scanned, it is a well formed sentence in L(G). This opera­ tion is the heart of PARSE.

The transition function of equation (12) is stored in the form of a table with two levels of pointers. One is for internal use and insures that the table will be scanned efficiently accord­ ing to an algorithm described by Gries [6]. The second level provides a link to SEMANT, which we shall describe shortly.

In addition to determining whether a sentence is well formed, PARSE is also capable of inserting words according to the ordering of (9c) in a sen­ tence to replace grammatically incorrect ones. This replacement routine involves a link to the acoustic and semantic levels and will therefore be

discussed when we consider the control structure.

Semantic Analysis

The function of SEMANT is to determine the meaning (in terms of what COMPIL can understand) of well formed sentences. SEMANT generates these hypothe­ ses on the basis of acoustic and grammatical clues plus some tabulated knowledge of its own.

SEMAN! treats phrases and sentences as mean­ ingful if COMPIL can either make appropriate en­ tries in its symbol table (e.g. data or instruction addresses) or can generate code (e.g. to compute the value of an arithmetic expression). For ex­ ample, the word "seven" by itself is semantically meaningless but the phrase "X seven" is a variable for which COMPIL would assi~n a storage location. Or the phrase "three point seven" could be a line number for which COMPIL would assign an entry ad­ dress . SEMANT scans the input strings for clues and uses acoustic information to form the best phrase (the smallest metric computed from equation (9b)) having the assumed meaning. Information con­ cerning the grammatical structure of the phrase is contained in the transition function of equation (12). The appropriate set of production rules are located by the second level of pointers in P~SE described above. For example, the words "three"

and "one" in the phrase

would serve as a clue to SEMANT that a floatin~­ point constant was present. SEHANT would then go to the transition table and look up the production rules for the formation of floating-point numbers. Then, referring to the values of the distance func­ tion computed by KNNJ according to equation (9b), the best such phrase would be formed and the result

might be three point one four one.

SEMANT forms four hypothetical command structures (since there are four major utility instructions). The arguments of the command structure are resolved (e.g. variable names, line numbers), and finally arithmetic expressions are determined including proper parenthesizin~. If the chosen command structure cannot contain an arithmetic expression, of course, SEMANT does not

look for clues for one.

COMPIL is not a necessary part of the speech understanding process but rather provides a means by which VOCAL can demonstrate that it has indeed understood a sentence. Unfortunately a subrou­ tine that produces machine langua~e code is nec­ essarily machine-dependent. For that reason, COMPIL has been purposely left unfinished. In its present state, COMPIL simply puts a sentence in a convenient internal form from which the ap­ propriate subroutines could generate the object

code.

Control Structure

The organization of VOCAL is shown in fi~ure 1. In this diagram the single lines represent logic paths and the double lines, data paths. The re­ quired control of its operation is performed by the main program, CNTRL, and may be described as follows.

Digitized speech is processed to produce t he nearest neighbor ordering for each word in the sentence according to equations (9b) and (9c) .

These results are stored for later use.

The sentence is then parsed. If the acous­ tic transcription of the sentence is grammatical­ ly well formed then all processing ends since no better interpretation for the sentence can be

found.

Most often, however, misclassifications do occur, and they result in ungrammatical strings. In this case the parser replaces the incorrect word by other words in the vocabulary in the or­ dering (9c) for the offending word. The values of the discriminant functions of (9b) are added up as the sentence is parsed. When the entire sentence has been scanned this total is a measure of the similarity of the modified strin~ to the acoustic transcription. For example, let the a­ coustic transcription of the sentence HQ be represented by v 1 , v 2 , . .. , V where each ,nl ,nl p,nl

vi,j is a member of Vt. Suppose that after this string was parsed it had been modified to H1 · V 1 , V 2 , ..· , V Then the similarity ·"k ·"k p,nk 1 2 p of Ho to H 1 is given by:

(13) p(H 0 ,H 1 )

·"k i

.... where d(Xi ) is the value of the first discrim­ ,nl inant function in the ord!Fi~ (9c) word, Vi , in H 0 and d(Xi ) is ,nl for the ith the value of the ing nkth discriminant function word, vi,~ , in H 1 . i for the correspond- After the acoustic transcription has been processed, PARSE only operates on sentences that have been generated by SEMANT. First SEMANT chooses the best (in the sense of equation (13)) command structure. Then it builds a sentence around this command structure by replacing words or groups of words with well formed, meaningful s tr i ngs. Replacements are always made in the or­ de r of (9c) and a total of the replacement simi­ l arities is kept. The resulting string, Hz, is re turned to PARSE for syntactic analysis and then sent back to SEMANT for refinement. This loop is executed until SEMANT cannot offer any more infor­ mation (i . e. Hi= Hi_ 1 ). Then the next command s tructure is tried and the process is repeated. The bes t four command structures are tried in this way.

When PARSE is called to analyze the i t h hy­ pothesis, Hi, it computes p(Ho,Hi) according to equa tion (13). At the i t h iteration, p (Ho,Hi) is compared to p (H 0 ,Hi_ 1 ); the sentence corresponding

to the smaller metri c is retained and the smaller me tric i s stored for comparison at the i+ls t stage.

When this process terminates, the well formed sentence corresponding to the smallest metric is compiled and executed. If no such sentence is found, VOCAL asks for help, indicating which parts of the sentence it finds confusing.

ln the course of the understanding procedure VOCAL may generate and test twenty hypotheses for a s hort sentence or fifty for a long, complicated one . In theory, there is no limit to the number of times i t may try to refine a hypothesis. In practice, however, the maximum observed has been twelve.

Test Da ta and Results

Tes t i ng of VOCAL thus far has been on a da ta set of 1266 words divided into a training set of 882 words and a tes t set of 22 sentences contain­ ing a total of 384 words. The training set con­ sis ts of 21 spoken samples of each of the 42 words Ln the VOCAL lexicon. The test set sentences are spoken by eleven different speakers, four of whom we re not subject s for the training set.

The s peech was recorded in an anechoic room on a NAGRA lV scientific recorder on low-noise t ape a t 15 ips. The analog signals we re then low pass filtered at 5 Khz, sampled to 10 bits at 10 Khz, and s tored on magnetic t ape.

The tra ining s et was, of cours e, used to com­ put e T of equation (4) and then the transformed, labeled training samples and T were stored in KNN3.

The acoustic r ecognition score on the test set was 210 correct i dentifications out of 384 words. This re s ulted in transc ribing two s entences cor­ r ec tl y . The number of correc t identi fi cations rose t o 317 fo r the full VOCAL s ys tem. This resulted in an exactly correc t unders t anding of e ight sentences, n nea r l y correct under s t anding of thirteen more, and a poor interpre t a ti on of one sentence. The mean i ng of "nearly correc t" and "poor" will be c l ea r f rom the example s be l ow. In each, the actual sentence appears first, f ollowed by its acous tic transcription and then by its final interpret a ­ tion. In the first example, the understanding i s perfect; in the second, nearly correct; and in the third, poor.

Aatual sent enae :

One point three read X two two next.

Aaoustia t ransari ption:

One close three read X two two scratch.

Peraeived sentenae:

One point three read X two two next.

Aatual sentenae :

Let X one five sub three three equal term minus X one times E two point oh close close over term sine X two close plus cosine X two sub thr ee close close to the two point seven eight one eight three five next.

Aaous t ia transaription:

Scratch X one five scratch three three equal s i ne minus X one times E two point oh close point over term sine X two close log cosine X two scratch three point oh to the two close sine three one eight three five read.

Peraeived sentenae :

Let X one five sub three three equal sine minus X one times E two point oh close close over t e rm sine X two close plus cosine X two sub three close close to the two point one three one eight three five next.

Aatual sentenae :

Four point five six step X seven from three point oh to eight point one by sine three of point oh close let X nine equal arctan X eight sub seven close next.

Aaous t ia transaription :

Four point by eight from X sine oh begin close oh equal eight point norm five norm three oh poin t oh log log X log equal arctan X link scrat ch close log norm.

Peraeived sentenae:

Four point five eight let X one oh sub one oh equal eight point one five one three oh one oh nine plus X nine to the arctan X eight s ub s even close next.

The 22 sentences of the test set r epresent about six minutes of speech. On Yale Unive r sity ' s IBM 370/158 computer, just under s i x minutes was required for VOCAL to process them.