Speech recognizer

In the speech recognizer disclosed herein, alignment of an unknown speech sediment, represented by a finely gradiated sequence of frames, with a model sediment represented by a sequence of states is performed by first preparing respective coarse sequences representing the unknown and model segments thereby to define a coarse matrix representing possible alignments. The fine sequences correspondingly define a fine matrix. A best alignment of the coarse sequences is determined thereby to define a coarse path through the coarse matrix. The coarse path is overlaid on the fine matrix and a corridor is defined which includes fine matrix locations which lie within a preselected metric of the coarse path. Only transitions within the corridor are calculated in determining the fine alignment of the unknown speech segment with the model segment, thereby significantly reducing the number of computations required.

BACKGROUND OF THE INVENTION 
The present invention relates to speech recognition and more particularly 
to an improved method of aligning an unknown speech segment with a 
reference or model speech segment. 
As is understood by those skilled in the speech recognition art, 
differences in manner and speed of speaking, not only from one speaker to 
another but also from different instances of speech by the same speaker, 
require that some procedure be utilized for aligning an unknown speech 
segment with each of the vocabulary models with which it is to be compared 
before determining a score or measure representing the likelihood of match 
between the unknown and each model. These procedures are sometimes 
referred to as time warping. One common method of performing this 
alignment or matching is so-called Viterbi decoding. 
Typically, the unknown speech segment is represented by a segment of 
multi-dimensional frames and each of the vocabulary model segments is 
represented by a sequence of states which may themselves be frames or 
probability distributions of frames. The frames may, for example, comprise 
essentially instantaneous spectra of the speech sound but it should be 
understood that other characteristics, such as LPC coefficients, might 
also be used. In order to obtain a meaningful match calculation, the 
sequences of frames and states must be relatively finely gradiated. For 
example, a single vocabulary word or model may be represented by a 
sequence comprising in the order of 50 states. The number of states will 
of course vary from word to word. The unknown speech sequences will also 
typically comprise a similar quantity. 
A comparison between an unknown speech segment and a model segment can thus 
be thought of as a matrix, and the alignment process can be considered as 
determining a best path through the matrix, i.e. a path which results in 
the best possible score for the matching of the unknown with that 
particular model. A path is essentially a sequence of frame/state pairs 
which satisfies certain constraints: successive frame/state pairs are 
within a necessary grid distance of each other so that there is continuity 
along the path; time must not be reversed, i.e. the path cannot go back on 
itself; and all of the input and all of the model should be accounted for, 
i.e. the search is typically to determine a best path from the origin to 
the diagonally opposite corner of the matrix. 
To rigorously determine a best path through the matrix, it is essentially 
necessary to calculate the cost of each possible transition from one 
matrix location to its neighbors and to then calculate the cumulative 
costs of various paths through the matrix. In actual practice, the 
computational cost of exhaustive or rigorous determination of a best path 
can be practically prohibitive and, accordingly, various schemes have been 
proposed for limiting the search space. It has, for example, been proposed 
to limit the search area to a corridor which is of fixed width from a 
simple diagonal from the origin to the far corner. Other predetermined 
corridor shapes have also been proposed. With each of these schemes, 
however, there is substantial risk that, if the corridor is made narrow 
enough to appreciably reduce the level of computation required, the 
accuracy of the resultant score may be impacted, since there is an 
appreciable likelihood that the best path will lie outside the corridor. 
In other words, speed is considerably improved by the use of a narrow 
corridor but likelihood of error is also substantially increased. 
Conversely, if a very broad corridor is implemented, the decrease in 
computation required may mot be appreciable. 
Beside limitation of search space, other search techniques have been 
developed in attempts to reduce the computation required. Among these are 
the so-called "beam search". In this technique, at each input frame 
position in the grid, all the scores of the paths from the grid origin 
(typically the bottom left corner) are compared. Those whose scores are 
worse than the best score by some threshold are eliminated and not pursued 
further. This is a `local` decision in that it is based only on the 
patterns between this point and the origin. It is entirely possible that a 
path which seems poor may become the overall winner once all the data is 
accounted for. Path deletions based on local criteria are thus dangerous 
and the computational saving may come at the cost of lower accuracy. 
Other schemes, such as the `best-first` (also known as the stack or A*) 
algorithm, always first pursue the most promising path, frequently 
reevaluating which is the best path. The hope is that the correct path 
will be extended all the way across the grid before too much work is 
expended on the less successful paths. Like the beam-search, the 
best-first algorithm can suffer from the limitations of decisions which 
are only locally optimal. To overcome this drawback, these techniques have 
been enhanced by computing an estimate of the score of completing partial 
paths to the end. In order to reduce computation, these estimates must be 
inexpensive compared to the cost of computing the actual path score. The 
considerable overhead required to maintain complex structures, continually 
compare paths and make complex decisions based on these comparisons make 
such search techniques undesirable for the task of limiting the 
computational cost of aligning an input pattern with a reference model. 
Among the several objects of the present invention may be noted the 
provision of an improved speech recognizer; the provision of such a speech 
recognizer which utilizes a novel method of deter-mining alignment of an 
unknown speech segment with a model segment; the provision of such a 
recognizer which requires less computational effort to achieve a very good 
alignment; the provision of such a speech recognizer which involves very 
little risk of excluding a good or best alignment of an unknown speech 
segment with a model; the provision of such a speech recognizer which is 
highly reliable and which is of relatively simple and inexpensive 
implementation. Other objects and features will be in part apparent and in 
part pointed out hereinafter. 
SUMMARY OF THE PRESENT INVENTION 
In accordance with one aspect, the method of the present invention utilizes 
a corridor approach to limit calculation but the corridor is not 
predetermined in shape or even necessarily symmetrical. Rather, the 
corridor is defined by an initial coarse alignment calculation. 
The speech recognizer of the present invention operates to match an unknown 
speech segment represented by a finely gradiated sequence of frames with 
model segments represented by fine sequences of states. The recognizer 
determines an alignment of the unknown with a model segment by first 
preparing respective coarse sequences representing the unknown and the 
model, thereby defining a coarse matrix representing possible alignments. 
A best alignment through the coarse sequences is determined, e.g. by 
Viterbi decoding, thereby to determine a coarse path through the coarse 
matrix. The coarse path is overlaid on the fine matrix and a determination 
is made as to which fine matrix locations lie within a preselected metric 
of the coarse path, thereby defining a corridor of possible paths through 
the fine matrix. Calculating only transitions within the corridor, a fine 
alignment of the unknown segment with the model segment is determined, 
e.g. again by Viterbi decoding. While the method of the invention requires 
two steps of path determination, the total number of calculations can be 
markedly reduced without excluding likely search paths since the corridor 
can be relatively narrow as compared with a predetermined corridor shape.

DESCRIPTION OF THE PREFERRED EMBODIMENT 
Referring now to FIG. 1, the matrix illustrated there is simplified or 
abbreviated for the purpose of illustration and represents an unknown 
speech segment of twenty four frames being compared with a reference or 
model segment of thirty two states. As indicated previously, it is 
desirable in computing the likelihood of match between the unknown segment 
and the model segment that a best temporal alignment of the unknown with 
the model be achieved in conjunction with the similarity measurements. 
Transitions from one matrix intersection to the next can only be made 
upwards; to the right; or diagonally, as illustrated. In the Viterbi 
decoding employed in the particular embodiment illustrated, each 
intersection can only be approached from its immediate neighbor to the 
left; from directly below; or from the 45 degree diagonal. This is 
required essentially since the alignment process cannot move backward in 
time. While Viterbi decoding is assumed, it should be understood that 
other alignment strategies are known and could be employed in the present 
invention. 
The path represented by reference character 11 illustrates an entirely 
possible best alignment between an unknown speech segment and a model 
speech segment. As may be seen, this alignment path departs significantly 
from a straight line from the origin to the far corner, this latter line 
being indicated by reference character 13. 
As indicated previously, to absolutely and rigorously search for the best 
possible alignment path, it would be necessary to calculate values for 
each possible transition in the matrix and to determine the best path from 
combinations of these values. Viterbi decoding substantially reduces the 
number of calculations without significantly impacting the likelihood of 
finding the best path but is still computationally intensive if rigorously 
approached. 
As indicated earlier, one approach towards limiting the search space is to 
provide a predetermined corridor and to only calculate transition values 
which lie within that corridor. In FIG. 1, a corridor which extends eight 
increments above and eight increments below the straight line diagonal is 
marked by boundaries designated by reference characters 15A and 15B. 
Although this corridor envelopes a substantial part of the search space, 
it does not fully encompass the hypothesized best path 11 and thus a 
likelihood of match calculated using only values within the corridor will 
not accurately represent the best match between the unknown segment and 
the model. 
In accordance with one aspect of the invention, a corridor is employed for 
the limitation of computation but the corridor is not predetermined or 
preselected in relation to the straight line path between the origin and 
far corner of the matrix. 
Prior to doing the detailed or finely gradiated calculations which are 
appropriate for determining the final likelihood of match score, an 
alignment path is calculated using only coarse sequences to represent both 
the unknown and the model speech segments. In the simplified embodiment 
illustrated, the coarse sequences are obtained by merely selecting every 
fourth frame or state from the fine sequences. A coarse matrix defined by 
the coarse sequence is illustrated in FIG. 2. As is understood, a more 
representative frame or state may be determined by combining 
characteristics of the group of frames being spanned. Applying Viterbi 
decoding to the coarse sequences generates a coarse path through the 
corresponding coarse matrix, this path being represented by reference 
character 21 in FIG. 2. 
The coarse path decoded through the coarse matrix is then superimposed on 
the fine matrix interpolating between the points defining the coarse path 
thereby to define a base path 22 as illustrated in FIG. 3. A corridor is 
then defined which includes all matrix intersections which are within a 
predetermined metric or measure of the coarse or base path. As will be 
understood, this metric is not the same as the distance or likelihood 
measurements which are calculated in determining matching between unknown 
and model. In FIG. 3, the corridor is delineated by the lines designated 
by reference characters 23A and 23B which are merely determined as being 
plus and minus four increments or frames vertically from the coarse or 
base path 22. FIG. 4 shows the corridor boundaries 23A and 23B and also 
the best path 13 from FIG. 1 and it can be seen that this path lies 
entirely within the corridor defined by lines 23A and 23B. 
As indicated previously, the corridor of FIG. 3 was obtained by merely 
going above and below the coarse path by four frames. However, greater 
clearance and latitude in encompassing the best path can be obtained if 
both horizontal and vertical distance is considered in measuring the 
distance from the coarse path to the corridor boundary. 
As the best path 13 lies within the corridor defined by lines 23A and 23B, 
it will be understood that a likelihood of match score calculated using 
only values for transitions within the corridor will be highly accurate in 
reflecting the likelihood of match between the unknown speech segment and 
the model speech segment. Further, although the accuracy of match 
measurement will be better than that which would be obtained using the 
predetermined corridor of FIG. 1, the number of computations necessary 
during the Viterbi decoding of the fine matrix is significantly reduced 
since the area of the corridor of FIG. 3 is substantially less, i.e. about 
half, of the area of the corridor of FIG. 1. While the total number of 
calculations is increased by those necessary to perform the decoding of 
the coarse matrix, this is a relatively small cost since the number of 
matrix points is reduced by a factor of sixteen. 
As indicated previously, the coarse matrix of FIG. 2 was generated simply 
by taking every fourth frame or state to provide a simplified embodiment 
for clarity of explanation. A practical procedure for selecting frames in 
an arbitrary spacing and including the first and last frame is illustrated 
in the flowchart of FIG. 5. As indicated at block 31, the first frame of 
the input pattern is copied to an output buffer and then N-1 frames of the 
input pattern are skipped as indicated at block 33, the value N being the 
scale ratio between the fine and coarse matrices. If the last frame has 
not been reached or passed, the selected input pattern of the frame is 
copied to the output buffer, as indicated at block 37, and the skipping 
procedure is repeated. When the last frame is reached or passed, it is 
copied to the output buffer as indicated at block 41. 
The procedure for defining the corridor is illustrated in the flowchart 
FIGS. 6A and 6B. This corridor defining procedure incorporates, in blocks 
55 and 57, the subsampling procedure of FIG. 5 which subsamples, 
respectively, the unknown pattern, designated by reference character 51, 
and the reference pattern, designated by reference character 53. 
Using the coarse sequences obtained from blocks 55 and 57, a coarse grid, 
i.e. corresponding to FIG. 2, is defined as indicated by the block at 
reference character 59. As indicated at block 61, the best alignment path 
through the coarse grid is determined by dynamic programming and trace 
back (Viterbi decoding). For each coarse path point in the coarse grid, 
boundaries for the alignment corridor are determined as indicated at block 
63 and these boundaries are transferred or overlaid to the fine matrix or 
grid, as indicated at block 65. Using a predetermined metric, the corridor 
boundaries are interpolated in the fine grid as indicated at block 67. In 
FIG. 3 of the simplified embodiment described previously, this metric is 
established merely by going four frames above and below the best coarse 
path. 
Distances are then calculated for all pairs within the corridor, as 
indicated at block 69, and the score of the best alignment path through 
the fine grid or matrix is determined by dynamic programming such as 
Viterbi decoding, this procedure being indicated at block 71. 
A computer program providing a practical implementation of the procedures 
illustrated in the flowcharts of FIGS. 5 and 6A-B is shown in an Appendix 
accompanying this specification. This computer program is written in the C 
programming language. 
In view of the foregoing it may be seen that several objects of the present 
invention are achieved and other advantageous results have been attained. 
As various changes could be made in the above constructions without 
departing from the scope of the invention, it should be understood that 
all matter contained in the above description or shown in the accompanying 
drawings shall be interpreted as illustrative and not in a limiting sense. 
##SPC1##