ApplyingTerm Rewriting to Speech Recognitionof Numbers
R. Shostak - November, 2012

Term rewriting is an important area of the branch ofartificial intelligence dealing with automated theorem
proving. In this talk, we discuss its application to speech
recognition grammar generation in Vocera.

The Human Speech MachinePhonemes – the Atoms ofSpeecha sunny day/s/ /u/ /n/ /I:/a rainy day/r/ /eI/ /n/ /I:/

Number of Phonemes in Different Languages!Xóõ
 English
 Mandarin
 French German Japanese Hawaiian
 Rotokas11244282424
22
1311

Rotokas - World’s Simplest Language•

12 Letters•

11 Phonemes•

4000 Speakers

Osireitoarei avukava iava ururupavira toupasiveira.

"The old woman's eyes are shut."Speech Recognition SystemInput Waveform

Recognition Grammar
Modified BNF Format:

Weather::= a Condition day

Condition ::= sunny | rainy

SRGS XML- Format:<rule id=weather>a<one-of><item> sunny </item><item> rainy </item></one-of>day</rule>Lexicon (Dictionary)
adayrainysunnythisis/L//d//r/ /eI/ /n/ /I://s/ /u/ /n/ /I:/
/ / /I / /s//I /A Three-State Hidden Markov Modelaij- probability of transition from state i to state jbi(k) - probability that observed symbol k is emitted from state iHMM’s for “A Sunny/Rainy Day”

Vocera Command Grammar Fragment
Command::=

CallCommand | MessageCommand

CallCommand ::=Call [Name | PhoneNumber]

Call::=

call | get me

Name::=

doctor smith| nurse betty| home| captain james kirk
| a cardiologist| room 2007

How do you pronounce “2007” in English?

two thousand seven twenty oh seven two oh oh seven two double oh seven two zero zero seven two nought nought seven two double nought seven two double zero sevenVocera Command Grammar Fragment
Command::= CallCommand | MessageCommand

CallCommand ::=Call [Name | PhoneNumber]

Call::=

call | get me

Name::=

doctor smith| nurse betty| home| captain james kirk
| a cardiologist| room [two thousand seven | two double oh seven …]

Pronounciations Depend Strongly on theLanguage and the Context
French

Mandarindeux mille septdeux zéro zéro sept
vingt zéro sept (for a phone extension)

二千零七
二零零七

Japanese



二千七
弐阡漆

The Problem


Find a way to quickly compute the set of all
natural pronunciations for a given string ofdigits
Find a way to compute a context-freegrammar that generates pronunciations for all
digit strings of a given length

The Solution

Number Generating Term Rewriting Systems(NGTRS) Efficient to compute Intutitive, easy to verify by inspection
 Easily adapted to different languages

Example of an NGTRS
S(dw)  T(d) S(w)S(d)  T(d)T(0)  zeroT(0)  oh
T(1)  one
T(2)  two…
T(9)  nine

Variables range over strings of digits, andcome in different “flavors”:

d represents a single digit (0 – 9)
n represents a single non-zero digit
w represents a non-empty string of digits
wn represents a string of n digits
Xd represents a digit other than dConstants are the members of:• The set D = {0, …, 9} of digits• A set P of pronunciation symbolssuch as “nine”, “oh”, “twenty”

Operators consist of:• A set of uninterpreted function symbols that map D+  P+
S is the start symbol• Concatenation (represented implicitly by juxtiposition)

Simple NGTRS Example
S(dw)  T(d) S(w)S(d)  T(d)T(0)  zeroT(0)  oh
T(1)  one
T(2)  two…
T(9)  nine

Given a natural number q
represented by a string q1q2 … qkof digits, we say that a string pof pronunciation symbols is apronunciation of q iff

S(q1q2…q,) + pSimple NGTRS Example
S(2007)
S(dw)  T(d) S(w)S(d)  T(d)T(0)  zeroT(0)  ohT(1)  one
T(2)  two…
T(9)  nineT(2) S(007) two S(007) two T(0) S(07) two oh S(07) two oh T(0) S(7)

 two oh oh T(7) two oh oh sevenExample using “double”
S(dw)  S(d) S(w)S(wd)  S(w) S(d)S(dd)  double T(d)S(d)  T(d)T(0)  zeroT(0)  ohT(1)  one
T(2)  two…
T(9)  nineS(2007)
 S(2) S(007) S(2) S(00) S(7)

 S(2) double T(0) S(7)
 S(2) double oh S(7)…

 two double oh sevenConstraints:• Left-hand sides of rules must consist of a single function symbol term
• Every variable on the left-hand side must occur exactly once on the right-hand side.






















; Room Number Generation Rules for North American English; For numbers with > 10 digits, we demand that they be spoken digit by digit.
S(y11)=>
G(d w)=>G(d)=>G(y11)
T(d) G(w)T(d); For numbers with <= 10 digits, we support natural pronunciation.
S(x10)
L(w)L(w 0 0 0)
L(w 0 0)

=>
=>
=>
=>

L(x10)
T(w)
T(w) "thousand"T(w) "hundred"T(w d1 d2)
T(d1 d2 d3 w)
T(d1 d2)
T(1 0)
T(1 1)
T(1 2)
T(1 3)
T(1 4)
T(1 5)
T(1 6)
T(1 7)
T(1 8)
T(1 9)
T(2 0)T(2 n)
T(3 0)
T(3 n)
T(4 0)
T(4 n)
T(5 0)T(5 n)
T(6 0)T(6 n)
T(7 0)
T(7 n)
T(8 0)
T(8 n)
T(9 0)T(9 n)
T(0)
T(1)
T(2)
T(3)
T(4)
T(5)
T(6)
T(7)
T(8)
T(9)

=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>

T(w) T(d1 d2)
T(d1 d2) T(d3 w)
T(d1) T(d2)"ten""eleven""twelve""thirteen""fourteen""fifteen""sixteen""seventeen""eighteen""nineteen""twenty""twenty" T(n)"thirty""thirty" T(n)"forty""forty" T(n)"fifty""fifty" T(n)"sixty""sixty" T(n)"seventy""seventy" T(n)"eighty""eighty" T(n)"ninety""ninety" T(n)"[zero oh]"
"one"
"two"
"three""four""five""six""seven""eight""nine"NGTRS used for room
numbers in the Vocera
SystemNG TRS for Japanese
S(0w)S(nw)
T(10)
T(1n)
T(x1d)T(100)T(10n)
T(1n0)T(1n1n2) T(x1d1d2) T(1000) T(100n) T(10n0) T(10n1n2) T(1n00) T(1n10n2) T(1n1n20) T(1n1n2n3) T(x1d1d2d3)

S(w)
T(nw)
十十T(n)
T(x1) T(1d)百百 T(n)
百 T(n0)
百 T(n1n2)
T(x1) T(1d1d2)
千千T(n)
千T(n0)
千T(n1n2)
千 T(n00)
千 T(n10n2)
千 T(1n1n20)
千 T(n1n2n3)
T(x1) T(1d1d2d3)

T(0)  零T(1)  一T(2)  二T(3)  三…
T(9)  九S(2007)
 T(2007)
 T(2) T(1007)
 二千T(7) 二千七

NG TRS for Mandarin
S(0w)S(nw)
T(10)
T(x10)T(n1n2)
T(n00)T(n10n2) T(n1n20) T(n1n2n3) T(n000) T(n100n2) T(n10n20) T(n10n2n3) T(n1n200) T(n1n20n3) T(n1n2n30) T(n1n2n3n4) S(w)
T(nw)
十T(x1) 十T(n10)T(n2)
T(n) 百T(n100) 零T(n2)T(n100) T(n2) 十T(n1n20)T(n3)
T(n) 千T(n1000) 零 T(n2)
T(n100n2) 十T(n10n20) T(n3)
T(n1000) T(n2) 百T(n1n200) 零 T(n3)T(n1n200) T(n3) 十T(n1n2n30) T(n4)

T(0)  零T(1)  一T(2)  二T(3)  三…
T(9)  九S(2007)
 T(2000) 零 T(7)
 T(2) 千零 T(7)
 二千零 T(7)

 二千零七Constructing a Grammar from an NGTRS

Speech apps often require grammars for recognizing
all phone numbers, tracking numbers, etc. of acertain length
Such grammars are most often constructed by hand,and are often buggy or incomplete

Given an NGTRS that generates pronunciations forsuch numbers, one can mechanically generate anequivalent CF grammar

Grammar Construction Algorithm
Construct a grammar GN from NGTRS N:
Terminal symbols are the pronunciation symbols of N
 Nonterminal symbols are certain terms of N
 The start symbol is S(d1..dk) where k is the # of digits in the numbers whose
pronunciations are to be generated
 Additional nonterminal symbols and rules are addedusing the following closure operation:Adding Rules to GNFor each nonterminal symbol T of GN
and each rule L  R of N such that Tand L are unifiable with m.g.u. s :Add the functional terms in Rs as newnonterminal symbols
 Add a new rule T  RsExample with Two-Digit Numbers

NS(dw)  T(d) S(w)S(d)  T(d)T(0)  zeroT(1)  one
T(2)  two…
T(9)  nineGnS(d1d2) T(d1) S(d2)

S(d2)

T(d2)

T(d1)

zero

T(d1)

oneT(d1)nineT(d2)zero

nine…

…

T(d2)

Claim

The language of GN is the set ofpronunications of k-digit numbers
generated by N

Proof Outline
Need to show that:1)

2)

3)

Each terminal string in the language of GN is apronunciation of some k-digit number q in N
Each pronunciation of a k-digit number in N is aterminal string in the language of GN(Lifting Lemma) Each term of N derivable froman instance of S(d1d2 … dk) is an instance of a
derivable string in GN

The Language of GN Consists of Pronunications of NTo Show: Each terminal string s of GN is a pronunciation of a k-digit number in N
Lemma 1: Each derivable string s of GN, considered as a term of N, is derivable in N fromS(d1d2…dk)

Lemma 2: If t * u in N, then for each instance ua of u, there is an
instance t’ of t such that t’a * ua(Proofs by induction on the length of the derivations).

From Lemma 1, S(d1…dk) * s in N. Applying Lemma 2, there exists a groundinstance S(q1…qk) of S(d1…dk) with S(q1…qk) * s. Hence s is apronunciation of the k-digit number q1…qk.

The Language of GN Contains All Pronuniciations of NTo Show: Each pronunication of N is a terminal string s of GN
Lemma (Lifting): Each term of N derivable from an instance of S(d1… dk) is an
instance of a derivable string in GN.
(Proof by induction on the length of derivations)
In particular, each pronunciation string s for a k-digit number q1…qk in N must be an
instance of a derivable string in GN. But since s consists only of pronunciation
symbols, s must be a terminal string of GN.

サンキュー谢谢你
Hey! Thanks, man!