In 1971, I was a member of a group of scientists,
who proposed a five year research
effort towards a demonstration of a large vocabulary,
connected speech understanding system.
Instead of setting vague objectives,
we propose specific performance goals.
The proposed speech understanding system
was required to accept phrases and sentences
from many speakers based on 1,000 word vocabulary using
a task oriented grammar within a constraining task.
We wanted the system to perform with less than 10%
semantic errors, using about 300 million computer instructions,
per second of speech.
Although these goals were highly ambitious
at the time of our proposal.
We felt that the required system could be
demonstrated within five years.
The Harpy system, developed at Carnegie Mellon University,
not only satisfies these goals but exceed
some of the stated objectives.
It recognizes connected speech from male and female speakers
using a 1011 word document retrieval task.
It achieved 95% semantic accuracy.
And runs an order of magnitude faster than expected.
Harpy is all the more interesting,
because it is one of the few examples
in artificial intelligence research of a five year
prediction that was in fact realized.
I am interested in speech understanding
[MUSIC PLAYING]
Harpy is the result of combining and improving
the best features from two speech systems previously
developed at Carnegie Mellon University.
Hearsay one and dragon.
Two features of the Harpy system that
led to a successful demonstration
over its representation of knowledge
and the use of new search techniques.
In developing speech recognition systems,
it is necessary to devise a means of acquiring
and representing the many diverse types of knowledge that
characterize speech.
We must also develop matching and search techniques,
that convert this passive knowledge
into an active process for understanding
an utterance in the presence of error, noise, and uncertainty.
First, let us consider some aspects
of knowledge representation.
The document retrieval task we saw earlier,
uses a vocabulary of 1,011 words.
When a user speaks of the system,
his utterance must conform to the grammar and vocabulary
for that task.
Internally, Harpy stores all legal sentences
in a finite state graph structure.
Here is a graph of a simple grammar.
This knowledge is organized as a network of nodes.
Or each node holds a word in the vocabulary.
The nodes are interconnected such that any path
through this word network constitutes
an acceptable sentence.
Tell us about Nexen.
Give me the headlines.
Tell me all about China.
Many words have more than one acceptable pronunciation.
Vodka and tomato juice.
We don't have any tomato juice
What?
The next time, the hot tomatoes are in town,
you better have tomato juice.
Alternative pronunciations can be
represented as a separate network of acoustic gestures
called phones.
Phones are the smallest elements of speech knowledge represented
in the Harpy network.
Each path through the network represents
an acceptable pronunciation of a word.
Tomato.
Dialects and accents can also be integrated
into these pronunciation networks as separate paths.
This is the pronunciation network for the word tell.
Tale.
Tail.
The pronunciation network for tell
is really a further specification
of tell in the word network.
Thus, we can replace tell in the word network
with its pronunciation network.
Likewise replacing every node in the word network
with its pronunciation network, generates
a new finite state graph, or each path
is the pronunciation of an acceptable sentence.
Tell me all about China.
The substitution of pronunciation networks
for words, adds a second level of knowledge to our graph.
Another aspect of speech knowledge
involves a phenomena that occur at word boundaries.
In written text, word boundaries are clearly defined by spaces.
Tell me all about China.
In spoken language, word boundaries tend to overlap.
Making it difficult to detect the end of one word
and the beginning of the next.
This problem is similar to writing,
tell me all about China without spaces,
or with spaces within words.
As a result of this, complex phenomena
arise where phones are inserted or deleted at word boundaries.
Knowledge about such phenomena can also
be represented in a Harpy network.
This third type of speech knowledge
completes the Harpy network representation.
The overall size of the network is
reduced by special heuristics.
This is achieved by detecting and removing redundant paths.
A separate knowledge network is compiled for each Harpy task.
This eliminates need for dynamic interpretation of knowledge
during the recognition process.
The finite state representation makes
it possible to store knowledge of grammar, vocabulary,
pronunciation, and acoustic phonetics in a single network.
Let's consider how this knowledge is used
in the recognition process.
Tell me all about China.
Utterances input through the computer.
Several preprocessing steps are taken
to repair the data for recognition.
The utterance is digitized, segmented into acoustic units,
and analyzed to determine the segmental features
and parameters.
This utterance has been divided into 23 segments.
At this point, an attempt is made
to match the first segment with one of the 98 possible phone
labels.
Since an absolute assignment cannot be made reliably,
the system calculates a match probability based
on the acoustic information in each segment.
Thus, the silence phone is given the highest acoustic match
for this segment, then the K phone, then TH and so on.
As the acoustic matches are generated,
Harpy begins the recognition process.
The goal of the recognition task is
to find an optimal sequence of phones satisfying two criteria.
The sequence must represent a legal path
through the knowledge network.
And should consist of phones with high acoustic matches.
Harpy uses a beam search to locate this optimal sequence
of phones.
This is a search technique in which
a group of near miss alternatives around the best
path are examined.
By searching many alternatives simultaneously,
the beam search eliminates the need for backtracking.
The search is executed by creating and examining
a tree structure of phones whose connections are
consistent with transitions in the knowledge network.
Each play in the recognition tree
represents one segment of the digitized utterance.
Harpy begins the beam surge, by taking
all legal forms for the start of a sentence from a knowledge
network, and entering them in the recognition tree.
Next, a path probability is calculated for each candidate.
This is a cumulative value based on the path of probability
for the previous node and the acoustic match probability
of the current node.
The path with the best probability is determined.
And remaining candidates are compared with it.
Those that fall below a threshold of acceptability
are prone from further searching.
The successors of the surviving candidates
are expanded, based on the information and the knowledge
network and the search continues.
When paths are expanded, two phones
may generate the same successor.
Instead of retaining two independent paths
through the same node, we can collapse them
into a common path avoiding redundant computation.
Only the path with the highest prior value
is relevant at this point.
Thus, lesser value paths can be discarded.
Because their path probabilities can never exceed the one
with the highest value.
The path probabilities are calculated as before.
The best path is established and unpromising alternatives
are pruned.
[MUSIC PLAYING]
The forward search continues.
Expanding the recognition tree and saving those connections
that satisfy the threshold until we
reach the end of the utterance.
[MUSIC PLAYING]
Of all the paths that survive to the end of the utterance,
the one with the best path probability
is the solution that we are seeking.
This is the only path that satisfies the two criteria
of the recognition process.
It provides the best interpretation of the acoustic
matches while satisfying the constraints of the knowledge
network.
A back trace through the recognition tree
reveals the desired solution.
This is purely a lookup operation
and does not involve any search.
What appears to be the best choice in the forward search,
may not in fact be part of the overall solution found
by the backtrace.
Thus, errors introduced by the acoustic matches
are easily recovered by delaying commitment to a particular path
until a forward search is completed.
Thus the forward search may be aerofoil without affecting
the final solution.
Let's look at the recognition process
again as it occurred on the computer.
Tell me all about China.
The utterance is digitized, segmented,
and acoustic matches are generated.
The four words with the best path probabilities
appear below each segment.
The backtrace selects words, leading to the optimal path.
This is an example of Harpy working with a very simple task
grammar.
Let's look at the systems performance
on several complex grammars.
Land subject to inundation point OK.
Speech understanding systems offer two advantages.
They allow humans to communicate in a natural manner.
Highway, double line.
And free their hands for other work.
The cartography task requires vocal identification
of topological features as they are traced into the computer.
What is beta times gamma?
This is an example of a desk calculator task.
The speaker request arithmetic operations
to be performed by the computer.
[MUSIC PLAYING]
Do any papers discuss your climbing?
[MUSIC PLAYING]
This is an example of the 1,000 word document retrieval task.
The knowledge network for this task
contains over 14,000 nodes.
It is the largest task currently running on the Harpy system.
[MUSIC PLAYING]
Night to King Bishop 3.
Here is an example of a voice chess system.
The player speaks his move to the computer
in standard rotation.
[MUSIC PLAYING]
Springer F-dry.
When the system is confronted with an utterance that
is inconsistent with a past vocabulary,
it still searches for the optimal path.
However, when the overall path probability
falls below an acceptable threshold,
the recognize utterance is rejected.
By combining the best features of earlier systems,
Harpy is able to recognize speed faster and more accurately.
Since the end of the five year project,
the system has been further improved and at present runs
an order of magnitude faster.
The two features of the system that
contribute to Harpy success are its representation of knowledge
and the beam surge technique.
By pre-compiling all the diverse sources of knowledge
into a single integrated network,
Harpy achieved the level of efficiency
that is unattainable by systems that dynamically interpret
their knowledge.
This permits Harpy to consider many more alternatives,
and deal with error and uncertainty gracefully.
Backtracking and redundant computations have always
been problematic in AI systems.
The Harpy system eliminates both of these in an elegant manner.
It is not always possible to capture all the language
constraints as a finite state graph.
A graph structure that attempts to represent
every possible variation requires a great deal
of memory.
More compact representations of knowledge involving a greater
degree of dynamic interpretation,
can certainly be used in Harpy-like-systems.
This is purely a space time trade off.
Occasionally, the heuristics associated with the beam surge
missed the optimal path.
But because the acoustic matches are less than accurate.
Attempting to find the optimal path at great cost and effort,
leads to little or no improvement
in the overall performance.
Everybody is an expert in speech.
And so we naturally expect flawless performance
from the computer.
However, given the immense complexity of the task.
We must continue to build more and more complex
speech understanding systems, so that we
may one day have systems approaching human performance.
Continued research in this area will also
teach us how to build complex knowledge based systems.
And provide us with a deeper insight into the nature
of intelligence.
[MUSIC PLAYING]