Speech Understanding Using Con dence Measures and
Dependency Relations

Kazutaka Shimada, Yoshitaka Uchida3, Shizue Sato, Sayaka Minewaki, Tsutomu Endo
Department of Arti cial Intelligence
Kyushu Institute of Technology
680-4 Iizuka Fukuoka 820-8502 Japan

Abstract

Utterance

In this paper, we propose a method for speech un-

Speech Recognizer Julian

derstanding using a corpus. First, the method ex-

N-besttracts keywords from an N-best list of speech recognizer output. This process employs two measures:

Keyword Extraction

a con dence measure of speech recognizer output and an association probability between words.
Next, the method uses dependencies between key-

Keywords
Identification of Dependencies
between Keywords

words in a corpus. Our method obtained high accu-

Sets of Dependencies

racy as compared with a method with only the condence measure of the speech understanding module. The results show the e ectiveness of the pro-

Corpus

Evaluation of
Sets of Dependencies

posed method.

Keywords : Speech Understanding, Keyword Ex-

Outputtraction, Stochastic Association, Association Probabilities, Corpus

Figure 1: Outline of the proposed method.

1 Introduction
Speech understanding and dialogue systems havebeen developed to practical use recently.

These

systems often recognize user utterances incorrectly.
It is important to deal with this problem forspeech understanding systems.

Funakoshi et al.

[4] have reported a method to parse ill-formedness
in Japanese speech.

Although the accuracy forparsing the manual transcription was 90%, thatfor parsing the real speech recognizer output decreased to 60%. The results show the signi canceof handling speech recognition errors. However, it
is essentially inevitable in handling the natural language by computers, even if vocabulary and grammar of the systems are tuned. The systems need tohandle speech recognition errors appropriately.
As regards the problem, most of the researchers
have studied a speech understanding method using
keywords or key phrases [7][8][9]. Extracting keywords and understanding an utterance using them
reduce speech recognition errors. Also the method
allows spontaneous speech to a user.

Bouwmanet al. [1] and Komatani et al. [5] have reported amethod for understanding an utterance using con-3

He is now with Justsystem Corp.

dence measures calculated from an N-best list ofa speech understanding module.
In this paper, we propose a method for speech
understanding using con dence measures and dependencies. This proposed method di ers from thetraditional keyword based methods in that it uses
dependencies between the extracted keywords forspeech understanding. Also we employ a measureof semantic informativeness between words for the
keyword extraction. This measure is easily calculated from a corpus.
Figure 1 shows the process

ow of the proposed

method. First, the method extracts keywords froman N-best list of speech recognizer output. In thisprocess, we employ two measures for keyword extraction:

con dence of speech recognizer output

and association probabilities between words. Next,
we use dependencies between keywords for speech
understanding. We utilize a corpus for the association probabilities and dependencies.
In Sect. 2, we explain two measures for keyword
extraction and in Sect. 3, we describe a method
for identi cation of dependencies between the extracted keywords using a corpus.

In Sect. 4, we

evaluate the performance of our method, and con-clude the paper in Sect. 5.

Utterance: kono waku wo kazoete kudasai.
(Please count this rectangle.)

2 Keyword extraction

i=1

kou mo waku wo kazoete kudasai.
(Please count the rectangle in this way.)
i=2 kono waku wo kazoete kudasai(Please count this rectangle.)
i=3 go no waku mo kazoete kudasai.
(Please count the 5th rectangle.)

Keyword extraction consists of two processes: (1)calculation of a con dence measure from speech
recognizer output and (2) calculation of association
probabilities between words using a corpus.

Theassociation probabilities are meanings of a word bystochastic association.

i=1

2.1 Con dence measure for content
words

i=2

We use a grammar-based speech recognizer Julian.

i=3

It outputs the N-best candidates and their scores.

j=1
j=6
j=5
j=4
j=3
j=2
Word koumo waku. wo kazoete kudasai
POS DEM PP
VVPPNTime 1-15 16-24 25-46 47-58 59-107 108-156
Word kono
waku wo kazoete kudasai
POS DEM
V
V
PP
N
Time 1-24
25-46 47-58 59-107 108-156
Word gowaku wo kazoete kudasai
no
POS
N
V
V
PP
N
PP
Time 1-14 15-24 25-46 47-58 59-107 108-156

We set N=10. A score of each sentence output by

DEM: demonstrative, N: Noun, V: Verb,
PP: Postpositional Particle

the recognizer is a log-scaled likelihood.
The con dence measure from speech recognizer
output in this paper is an expanded model of the

Figure 2: An example of alignment.

method proposed in [5]. In [5], Komatani et al. calculated con dence measures of content words fromthe scores of speech recognizer output. The process
is as follows:

j -th morpheme in the i-th sentence is a word wj ,1. Each i-th score (1factorwhere j denotes the position of a morpheme. If the( i  N ) is multiplied by a let 

wj ;i< 1). Then, they are transformed

from log-scaled value to probability dimension= 1, and 0 otherwise.

If the con dence

is low, the word is rejected. We handle the words
with high con dence as keywords.

by taking its exponential, and calculate a posteriori probability for each i-th candidate.

pi =

P =1

1scoreieNke

1scorek

(1)

X 1
i

=1

pi

dence about speech recognizer outputs. Here wealso calculate con dence of a word in a domain for
keyword extraction. We employ association prob-

N

pw =

be-

Pc (w ) in the previous section is a measure of con-

2. A posteriori probability for a word is calculated as follows:

2.2 Association probabilities
tween words

w;i

(2)

abilities, which were proposed by Mochihashi etal. [6], between words for the con dence. The association probabilities are meanings of a word by

If the i-th sentence contains a word w , let w;i

stochastic association and are calculated from a= 1, and 0 otherwise. A posteriori probabil-

corpus.

ity (pw ) that a word w is contained is derived

tic informativeness of a word by its co-occurrence

as summation of a posteriori probabilities of

distribution.

sentences that contain the word.

tion information. The association probabilities are

They de ned pw of a content word as a con dence
measure.
Although they calculate pw for each i-th sentence
only, we expand that into each morpheme. First,

First, they de ned a measure of semanMochihashi et al. called it associa-

calculated from a combination of the association
information and co-occurrence probabilities.
The association information of a word x is calculated as follows:

we align morphemes in an N-best list. We employ

ap(x) = exp(

time and part of speech (POS) tags of morphemes
ple of the alignment. Next, we calculate con dence

1

X 1
pi

(4)

where w and L are a word and words in a corpusjrespectively. p(w x) denotes a co-occurrence probwj ;i(3)=1
1 Content words in this paper are verbs, nouns, demonstratives, adjectives, attributes and adverbs.
ijability of w and x. ap(x) is a mean co-occurrenceN

Pc (wj ) =jp(w x) log p(w x))

w2L

for the alignment process. Figure 2 shows an examof a content word :X

probability of the word x. It is low if a word co-2

occurs with various words on the average .

2

For example, postpositional particles.

Utterance: deha waku no naka no chou no kazu wo kazoete kudasaiWell, please count the number of butterflies in this rectangle.
N-bestj=1
i=1 deha
2
deha
3
deha
4
de
5
deha
6
deha
7
deha
8
ikeru
9
deha
10 deha

2

3
kou
kono
koko

waku
au
ato

kou
hou
hou

waku
ato
ato

kou
kono

4
mo
mo
mo
mo
mo
mo
mo
mo

5
chou
chou
chou
chou
chou
chou
chou
chou
chou
chou

6
no
no
no
no
no
no
no
no
no
no

7
kazu
kazu
kazu
kazu
kazu
kazu
kazu
kazu
kazu
kazu

8
no
no
no
no
no
no
no
no
no
no

9
kazoetekazoetekazoetekazoetekazoetekazoetekazoetekazoetekazoetekazoetePi
0.19600.17070.10850.10280.09550.07930.07690.06840.05440.047410
kudasaikudasaikudasaikudasaikudasaikudasaikudasaikudasaikudasaikudasai

Confidence
from Julian

j=3
5
7
9
kou (0.3459) chou (1) kazu (1) kazoeru(1)kono (0.2181)

Association Probabilities
from Corpus

j=1
2
3
4
i=1 kou (0.0000) chou (0.0651) kazu (0.0591) kazoeru (0.0604)
2 kono (0.0490) chou (0.0897) kazu (0.0862) kazoeru (0.0879)

PC (kp i ) P a (kp i )P(kp i )0.557683 0.386659 0.999993
0.000014 0.613341 0.000007

kp i
kono (this) chou (butterflies) kazu (the number of) kazoeru (count)kou (in this way) chou (butterflies) kazu (the number of) kazoeru (count)

Figure 3: An example of keyword extraction.

j

The association probability a(wj wi ) is a co-kpi are calculated as follows:

occurrence probability weighted with the associa-ja(wj wi ) =Pj

Pc (kpi ) =p(wj wi )ap(wj )

j

j

(5)

p(wj wi )ap(wj )wjYmtion information of wj .

=1YPc (kj );(7)

Pa (kj )

(8)

m

j

Pa (kpi ) =where a(wj wi ) denotes the association of wi to wj .

2.3 Keyword extraction using two
measuresj

Next, we normalize Pc (kpi ) and Pa (kpi ).
N Pc (kpi ) =P

Pc (kpi )N Pa (kpi ) =P

Pa (kpi )We calculate a score using the con dence measure(C MCW ) in Sect. 2. 1 and the association probabilities in Sect. 2. 2. Figure 3 shows an example ofthe keyword extraction process.
First, keywords are extracted by using C MC W .

=1

n
k

=1 Pc (kpk )nk=1 Pa (kpk )

(9)

(10)

Finally, we calculate the harmonic mean of them.

We combine the extracted keywords. We call the
combined keywords a keyword list kp.

P (kpi ) =2

1
1+ N P (kp )N Pc (kpi )
a
i

(11)

fkp1 ; kp2 ; kp3 ; 1 1 1 ; kp g
where P (kp ) denotes the score of a keyword list
where kp = fk1 ; k2 ; 1 1 1 ; k ; 1 1 1 ; k g and k is a
kp . We calculate this score for K P and return
KP =

n

i

j

m

i

j

keyword. m is the number of keywords in a keyword
list. n is the number of keyword lists. In Figure 3,
m = 4 and n = 2.

Second, the association probability Pa (kj ) for kj
in kpi is calculated as follows:Xm

Pa (kj ) =

=1
=j

j

a(kl kj )

(6)

l
l6

i

them in descending order of the scores.

3 Dependencies between keywords
We proposed a method for keyword extractionin the previous section.

A speech understanding

method with keyword extraction, however, is in-Then, the con dence measure Pc (kpi ) and thesucient because a keyword possesses relations to

association probability Pa (kpi ) for a keyword list

other ones. In this section, we describe a method

Keyword lists
Rank: 1st
kaado
(card)

ten(dot)musubu(link)

Rank: 2nd
kaado
(card)

sen(line)

musubu(link)

ten(dot)musubu(link)

kaado(card)

sen(line)

musubu(link)

Dependencies
Weights
kaado(card)

kaado

Weight
mod
proe

kaado
(card)

ten
(dot)

sen
(line)

kaado(card)

musubu(link)

musubu(link)

ins
obj
ins

Re-ranking using SSkpi

....

ten
ten
sen
musubumusubu....

0.25560.11560.0502
0.4811
0.0211.....

Weights (POS)
noun

Dependencies
New Rank: 1st

mod

ins
sen
(line)

kaado(card)

Weightproe

musubu(link)

if needed

subj
obj

obj

....

noun
noun
verb
verb
....

0.03430.0121
0.06250.0711.....

Figure 4: An example of the scoring process

for extracting a correct keyword list using depen-

Table 1: Case labels

dencies between keywords.
Dependencies which are used in the process are

Label

Role

sbj

subject

based on the following characteristics of Japanese
dependencies:
1. dependencies are directed from left to right.
2. dependencies do not cross.

obj

objectloc

location

locf

location-fromins

instrument

3. all words except the rightmost one depend on
only one other word.
We generate combined keyword lists from the extracted keywords, on the basis of these 3 characteristics.
Next, we calculate a score for the keyword lists.
Weights of dependencies are computed from a corpus.
wx;yi =

P =1

is used for normalization of the number of

keywords in keyword lists. distj is the weight forthe distance between kj and kl .
wx;yi is the weight between words that appear ina corpus. However, all dependencies do not exist
in the corpus. The score of dependencies is 0 if af req (x; yi ; label )mjwhere P (kpi ) is computed with Eq. (11) in Sect.
2.3.

(12)

f req (x; yj ; label )The score wx;y is a probability that a word x
depends on a word y with a relation label .

m isdependency between words in a keyword list does
not exist in a corpus. We employ dependencies between parts of speech (POS) in such a case. The
weight of POS is computed as follows.

the number of words which a word x depends on
with a relation label . The f req in Eq. (12) denotes
the frequency of x with y and label . Table 1 shows
examples of dependency relations.
The score for a keyword list is computed as follows:

SSkpi = P (kpi ) +

1

Y

m0

j

P =1

f req (posi ; posj ; label)nkf req (posi ; posk ; label)

wkj ;kl

1 dist2(14)

where posi , posj and posk are POS tags. n is thenumber of POS tags in a corpus.

1=1

pwposi ;posj =is a parameterfor decreasing the value of POS weights. We de nej(13)

as the average of minimum and maximum valuesof the weights between words. We use the weight ofself-correction and hesitation, in them.

Words inthe corpus have dependencies.

4.2 Experimental result
We used Julian, which is a grammar-based speech
recognizer. It contained 107 rules as the grammars,
and the number of vocabularies was 511 words.
Here we set N = 10 and= 0:05. For constructing

the model of association probabilities, we employ 72
dialogues consisting of 2211 utterances in our corpus and 51 dialogues consisting of 1084 utterances

3in the PASD corpus . We evaluated 300 utterances(6 test subjects

2 50 utterances). The average of

keywords in an utterance is 4.42 words (1326 words
S1: nanto onazi kazudesuka.
(What is the number equal to?)T1: kono waku no naka no chou wo kazoetekudasai.
(Count the number of butterflies in this frame)
S2: kore wo kazoerunodesune.
(May I count them?)
T2: soudesu.
(yes)
S3: dokokara kaado wo erabunodesuka.
(Where may I select from?)
T3: kokokara desu.
(From here.)S4: kono chou to kono kaado wo musubunodesune.
(May I link card(1) and butterfly(1)?).....
..... to be continued/ 300 utterances). We evaluated this process withthe following measures: accuracy of the 1st keyword list (Acc 1st), recall and precision rates forthe 1st keyword list. The recall and precision rates
are computed as follows:

extracted correctly
Recall = # of keywords# of keywords
(15)
#
of
keywords
extracted
correctly
Precision =# of extracted keywords(16)
Table 2 shows the results for keyword extraction.
We compared our methods with Julian and only

Figure 5: An example of a drill text and a dialogue

the con dence measure (C MCW ) described in Sect.
2.1.
The proposed methods outperformed output of

POS as a substitute for the weight between words
in this scoring process only if the weight between
words does not exist in a corpus.
Figure 4 shows an example of the scoring processwith dependencies.

4 Experiment
In this section, we evaluate the proposed method.

4.1 Task and corpus
We are developing a problem solving and knowledge
acquisition system based on co-reference between
drill texts and dialogue with a teacher, focusingon

rst-grade mathematics [2]. In this paper, we

handled this task as a domain.
We collected a corpus consisting of simulated dialogues for this domain. The number of test subjects
is 24. We obtained 2211 utterances (72 dialogues).
The 72 dialogues consist of 27 dialogues with 9
test subjects for person-to-person and 45 dialogues
with 15 test subjects for person-to-machine. The

Julian and C MCW , with respect to all measures
for the evaluation.

C MCW . The results show the e ectiveness of our

methods that used two measures and dependencies.
The reason why the accuracy was low is that theaccuracy of the speech recognizer was low. The accuracy of the 1st sentence by Julian was 22.33%.
In short, the speech recognizer output did not often contain keywords that we want. In future work
we can supplement keywords not containing in keyword lists by using the association probabilities because they denote the likelihood of co-occurrence
between words.
Next we discussed the accuracy of identi cationof dependencies.

an example of a drill text and a dialogue.
We transcribed the dialogues manually, and thentaggedllers and ill-formed expressions, such as

For the keyword list extraction

the results of the method with POS weights andwithout POS weights were not signi cantly di erent (see Table 2).

We compared the accuracy ofthe methods. We evaluated them with the following points.

Eval (1)

Accuracy of identi cation of a dependency be-

simulated dialogues for person-to-machine were collected by Wizard of OZ method [3]. Figure 5 shows

For the 1st keyword set, theaccuracy increased by 16% as compared with thetween two words.

Eval (2)Accuracy of identi cation of dependencies of3

http://winnie.kuis.kyoto-u.ac.jp/taiwa-corpus/doc/Table 2: The results of keyword extraction

with Dependency with Dependency
without POS
with POS

JulianC MC W

Two measures

Acc 1st

43.67

34.33

46.00

49.48

50.87

Precision

80.64

78.21

81.86

84.34

84.45

Recall

85.14

82.58

86.43

88.39

88.24

Table 3: The results of identi cation of dependen-

References

cies[1] C. Bouwman, J. Sturm and L. Boves, \In-Eval(1)
Eval(2)
Eval(3)

without POS with POS
83.97

90.37

36.21

47.64

64.25

79.13

corporating Con dence Measures in the Dutch
Train Timetable Information System Developedin the ARICE project," Proc. ICASSP, 1999.
[2] T.

EndoandUnderstandinginDialogue-based

Problem

Systems,"

all words in the keyword lists which were ex-

Vol.5, No.1, pp.81-99, 1991.

tracted correctly.

Sys-

The accuracy of the method with POS

weights was higher than that without POS weights.
These results show the signi cance of POS weights
dependency

identi cation.

Toaccomplish

higher accuracy in the keyword extraction process,we need to examine some parameters, such as distj
in Eq. (13) andComputer Speech and Language,[4] K. Funakoshi, T. Tokunaga and H. Tanaka,

Table 3 shows the results of the identi cation pro-in Eq. (14).

ofarobustparserforspokentaneous Speech Workshop, pp. 53{56, 2003.
[5] K.

Komatani

mixed-initiative

and

T.

Kawahara,

dialogue\Flexible

management

using

concept-level con dence measures of speech recognizer output," Proc. COLING 2000, Vol. 1,[6] D. Mochihashi and Y. Matsumoto, \Meanings
as association," IPSJ SIGNL-134 pp. 155{162,1999.

In this paper, we reported a method for speech unThe method was based on the fol-lowing processes: (1) keyword extraction using a
corpus and (2) identi cation of dependencies between keywords for speech understanding.

\Evaluation

Japanese," Proceedings of Dis uency in Spon-pp. 467-473, 2000.

5 Conclusions
This

method dealt with speech recognition errors appropriately. The keyword extraction process employed
two measures: con dence of results of the speech
understanding module, and stochastic associations
between words. The accuracy of the 1st keywords
list that was produced by the method consisting of
two measures and dependencies increased by 16%,
as compared with the method with one con dence
measure. The experimental results showed the effectiveness of the proposed method.
Our future work includes (1) a large-scale experiment for this task and evaluation for other domains
with the proposed method, and (2) applying thecontext and utterance intentions in dialogue to themethod.

Gestures

Solving[3] N. Fraser and G. Gilbert, \Simulating Speech

Accuracy of identi cation of dependencies of

derstanding.

\Cooperativeandpp.152{169, 1999.

Eval (3)forKagawa,Utterancestem," Computational Intelligence, Vol.5, No.2,

all words in the extracted keyword lists.

cess.

a

T.
of

[7] M. Nakano, N. Miyazaki and J. Hirasawa, \Understanding Unsegmented User Utterances in
Real-Time Spoken Dialogue Systems," Proc.
37th Annual Meeting of the Association for
Computational Linguistics (ACL), pp.200{207,1999.
[8] Y. Takebayashi, \Spontaneous speech dialoguesystemTOSBURG

II-

towards

the

user-

centered multimodal interface -," IEICE Transaction on Information and Systems, Vol.J77-DII No.8 pp.1417-1428, 1994.
[9] T. Yano, M. Sasajima and Y. Kono, \BTH::an ecient parsing algorithm for keyword spotting," Journals of JSAI, Vol.17, No.6, pp.658{
666, 2002.