INTERSPEECH 2012
ISCA's 13th Annual Conference
Portland, OR, USA
September 9-13, 2012

ISCA Archive
http://www.isca-speech.org/archive

Evaluation of Many-to-Many Alignment Algorithm by AutomaticPronunciation Annotation Using Web Text Mining
Keigo Kubo1 , Hiromichi Kawanami1 , Hiroshi Saruwatari1 , Kiyohiro Shikano1
1Graduate School of Information Science, Nara Institute of Science and Technology, Japankeigo-k@is.naist.jp, kawanami@is.naist.jp, sawatari@is.naist.jp, shikano@is.naist.jp

Abstract
The need for robust pronunciation annotation over
out-of-vocabulary (OOV) words has been increasing withthe development of an application that deals with proper
nouns and brand-new words, such as Voice Search. In
robust pronunciation annotation over OOV words, thealignment between graphemes and phonemes is vital
data. For a many-to-many alignment algorithm between
graphemes and phonemes, we describe its problems andmethods to overcome them. An evaluation experimentof a many-to-many alignment by automatic pronunciation annotation using Web text mining is also performed.
That experimental result shows that the proposed manyto-many alignment produces an alignment that has thehigh generalization ability for OOV words while avoiding degradation of the accuracy of the pronunciation annotation compared with the conventional approach.
Index Terms: string alignment, out-of-vocabulary word,
pronunciation annotation

1. Introduction
Recent advances in speech recognition have made it possible to attempt large-scale, open-domain, data-driven approaches. Out-of-vocabulary (OOV) words are the bottleneck in speech systems, and the need for robust pronunciation annotation has been increasing. For example,
voice search applications have attracted attention becauseof an increased demand for mobile device interfaces. A
variety of words, such as proper nouns and brand-newwords, must be dealt with in these applications. It is important to update the language model and the word dictionary to accommodate OOV terms. OOV words canbe collected easily from Web text resources, but generally, their pronunciation remains unknown. Therefore,
an automatic pronunciation annotation is desired. Statistical approaches, including grapheme-to-phoneme (g2p)
conversion[1-3] and a Web text mining approach that
identifies a part of the Web text that describes wordpronunciation pairs[4], have been proposed.
The alignment between graphemes and phonemes isvital data for these pronunciation annotation methods. In
this paper, we focus on alignment methods, such as a oneto-one alignment[5] and a many-to-many alignment[6-8].

INTERSPEECH 2012

In [6,7], the many-to-many alignment is referred to asa joint multigram. As this alignment and the one proposed in [8] are essentially the same, the two methods aretreated as a joint multigram approach in this paper. [8]explains the suitability of the joint multigram approachover a one-to-one alignment and demonstrates the better
performance of this approach. However, the joint multigram approach generally prefers a mapping consistingof longer substrings, which degrades the generalization
ability of automatic pronunciation annotation for OOVwords. To cope with this problem, we introduce the city
block distance, which is employed in dynamic time warping, to the joint multigram approach. The resulting mappings are pairs of substrings that are unconstrained inlength, yet sufficiently short to increase the generalization
ability[9]. Our many-to-many alignment has been shown
to be effective as a g2p conversion for OOV words.
For our many-to-many alignment, we describe theremaining problems and propose methods to overcome
them. Also, an evaluation experiment of these methods
by automatic pronunciation annotation using Web text
mining is shown.
The rest of this paper is organized as follows. In
Section 2, we explain many-to-many alignment methods.
The parameter estimation for our many-to-many alignment is described in Section 3, and the problems and their
proposed solutions are described in Section 4. In Section
5, we report the evaluation experiment by automatic pronunciation annotation using Web text mining. Finally,Section 6 states our conclusion.

2. Many-to-many alignment
2.1. Preliminaries
Let d be a tuple of a word and its pronunciation, and D
be a set of d tuples. Let Ud be a set of alignment candidates of graphemes and phonemes, generated from thed tuple. Let u be an alignment of the tuple d in the set
Ud , and u be a mapping in the alignment u. We denote a
mapping where ϵ is mapped in the phoneme side to be adeletion character. An example of a word-pronunciation

2318

pair ⟨able, éibl⟩ is shown below.
dDUduu3. Parameter estimation= ⟨able, éibl⟩= {⟨able, éibl⟩}= {able/éibl, abl/éib e/l, ...,a/éi b/b le/l, a/éi b/b l/l e/ϵ}
= a/éi b/b l/l e/ϵ= a/éi

Our many-to-many alignment estimates model parameters pu ≡ P (u) by employing the EM algorithm alongwith the joint multigram approach. The following is a
pseudocode for the EM algorithm of our many-to-manyalignment.
1. Set an initial value of pu .
2. Calculate an expectation (E-step),∏psuu∑ ∑u∈u∑ ∏γu =nu (u),psuud∈D u∈Ud

2.2. Joint multigram approach
The joint multigram approach proposed in [6] isû= arg max P (u|d)
u∈Ud≃ arg maxu∈Ud∏

u∈Ud u∈u

P (u).

(1)u∈u

P (u|d) is assumed to be the product of the unigram probabilities of a mapping included in u.
2.3. Basic idea of our many-to-many alignment=arg max P (u|d)
u∈Ud≃ arg maxu∈Ud∏

P (u)su ,(2)u∈uwhere su means the city block distance as an exponential
domain and is defined assu = iu + ju .

INTERSPEECH 2012

where nu (u) means a frequency of u in u.
3. Calculate the maximum likelihood (M-step),γup̂u = ∑ ,γu(5)u∈UThe joint multigram approach prefers longer mappings,
i.e., mappings of a longer grapheme sequence and/or alonger phoneme sequence (e.g., u = able/éibl), which
degrades the generalization ability of automatic pronunciation annotation for OOV words. To cope with thisproblem, the joint multigram approach limits the maximum length of graphemes and the maximum length ofphonemes in a single mapping. These maximum lengths
are both set to two in [8]. However, appropriate valuesof the parameters depend on the language. In the case ofJapanese words including kanji (Chinese characters), onegrapheme could be mapped to more than two phonemes.
If we set these maximum lengths to be more than two, theresulting mappings would no longer be short.
In order to suppress longer mappings without fixing
these maximum lengths, we introduce the city block distance in P (u|d) as an exponential[9] domain. As a consequence, longer mappings are not advantageous overshorter mappings because the difference in the number ofmultiplications in P (u|d), which causes the preference
for longer mappings in the joint multigram approach, isequalized in each alignment u. This leads to an improvement of the generalization ability of automatic pronunciation annotation for OOV words.
Let iu be the number of characters in graphemes andju be the number of characters in phonemes of mappingu. Then, our many-to-many alignment is defined asû

(4)

(3)

where U is the set of all mapping types.
4. Substitute p̂u for pu .
5. Finish if convergent, otherwise return to Step 2.
The initial value of pu is set uniformly. Our EM algorithm introduces the city block distance in (4), unlike thejoint multigram approach.

4. Problems and their proposed solutions
4.1. Deletion character
The deletion character differs from a mapping in which
pronunciation is mapped in terms of frequency. Whereasa mapping in which pronunciation is mapped is countedin (4) when only its graphemes and its phonemes appear for a d tuple concurrently, the deletion character iscounted when its graphemes appear for a d tuple. This
causes the problem that parameters for alignment are estimated such that an irrelevant deletion character is chosenwell.
To solve the above problem, we introduce n-best
Viterbi training[6] which employs only promising alignments U d instead of all possible alignments Ud in theE-step of the EM algorithm. An unpromising alignment
includes many irrelevant deletion characters. Since then-best Viterbi training removes such alignments from parameter estimation, the above problem is suppressed.
Initial values of parameters are estimated to acquire
promising alignments by employing our EM algorithm
described in Section 3. If the appearance of the deletion
character is permitted in our EM algorithm, these initialvalues are estimated such that an irrelevant deletion character is chosen well. Hence, we propose to utilize ourEM algorithm with prohibition of the appearance of thedeletion character. Next, we perform the special n-best2319

Table 1: Example of irrelevant mapping in the case of⟨AAA, trı́pléi⟩ and ⟨Ace, éis⟩. In this case, the irrelevant
mapping is AA/trı́pl.
⟨AAA, trı́pléi⟩ → {…, AA/trı́pl A/éi, …}⟨Ace, éis⟩ → {…, A/éi c/s e/ϵ, …}Viterbi training that updates a parameter only once to estimate the initial values of parameters where the irrelevant deletion character is not chosen. This permits theappearance of the deletion character and employs parameters estimated using the above EM algorithm as initialvalues. The parameter of the deletion character is approximated by the geometric mean of parameters of mappings
included in the alignment without the deletion character. Our parameter estimation introducing n-best Viterbi
training is shown as follows.
1. Employ our EM algorithm with prohibition of theappearance of the deletion character.
2. Carry out the special n-best Viterbi training that requires an n-best alignment using (6) and updates theparameter only once. This permits the appearanceof the deletion character and employs parameters
trained in Step 1 as initial values.
∏û = arg max
P (u)suuu∈u′×(∏

5. Experiments and results
We evaluate the conventional method (joint multigramapproach) and our many-to-many alignment including
the extensions described in Section 4, by automatic pronunciation annotation using Web text mining[4].
5.1. Experimental description
The methods compared are as follows.
1. Direct employment of aligned data withoutalignment[4] (baseline).
2. Joint multigram approach[6, 8] (joint).
3. Our many-to-many alignment with the city block
distance[9] (city).
4. Our n-best Viterbi training in Section 4.1 added tocity (city+del).
5. The mergence method of irrelevant mapping in Section 4.2 added to city+del (city+del+merge).
The experimental procedure is as follows.

P (u)su )DuIu +Ju −Du(6)u∈u′u′ is an alignment that removes the deletion character from u, Du is the total number of characters ofthe deletion character, Iu is the total number of characters of the word, Ju is the total number of characters of the pronunciation.
3. Carry out the n-best Viterbi training that requires an
n-best alignment using (2) permitting the appearanceof the deletion character. Initial values of parameters
are the same as for parameters trained in Step 2.
4.2. Irrelevant mapping
An alignment including an irrelevant mapping tends tobe chosen in a word that has a special pronunciation. Forexample, as shown in Table 1, the parameter of the mapping A/éi is estimated highly because it appears for otheraligned data such as ⟨Ace, éis⟩ except for the part of⟨AAA, trı́pléi⟩. Therefore, the alignment including theirrelevant mapping AA/trı́pl is chosen.
To solve this problem, after requiring an alignment using (2), we merge an irrelevant mapping (e.g.,AA/trı́pl) and its neighbor mapping (e.g., A/éi) by employing the number of possible mappings before and after
the mapping required by a mapping included in estimatedalignments. In our many-to-many alignment, a mapping

INTERSPEECH 2012

with multiple mappings in forward and backward contexts is more likely to be a correct mapping. On the otherhand, a mapping other than those above is more likely tobe an irrelevant mapping. By employing such heuristics,
we merge a mapping that has only one context in a forward or backward direction and a mapping present in that
direction to avoid an irrelevant mapping.

1. In each compared method except baseline, train theparameter for alignment using the aligned data, andestimate an alignment over the aligned data.
2. Perform automatic pronunciation annotation using
Web text mining[4] employing only mappings included in each estimated alignment. Baseline directly employs aligned data instead of these mappings.
3. Evaluate Recall, Precision and F-value.
Recall, Precision and F-value are shown as follows.
RecallPrecision
F-value

R
=C

(7)

R
=N
= 0.5(NR+C )

(8)
(9)

R is the number of keywords for which a correct pronunciation is accepted, C is the number of keywords forwhich a correct pronunciation is extracted from the Web,N is the number of keywords for which a pronunciation
extracted from the Web is accepted. Recall represents theheight of the generalization ability for OOV words. Precision represents the occurrences of an irrelevant mapping.
The experimental conditions are as follows. For maximum lengths of graphemes and phonemes in a single
mapping, baseline, city, city+del and city+del+merge2320

Table 3: Experimental result

Table 2: Experimental data
1aligned data

test data

2

Japanese Kanji dictionary (Wnn , Sanseido ),Naist Japanese dictionary3 , Eijiro4 . Totalamount of data is about 350 thousand words.
Search queries that could not annotate a correct pronunciation by employing Kytea5 insearch queries, where there are kanji, hiragana,katakana, and alphabetical characters, obtained
from Yahoo! search ranking6 , Google Trends7 ,and Goo keyword ranking8 excluding multiple
words and URLs. Total amount of data is about
two thousand querys.

have no limit, whereas joint has limits of 1-3, 1-6, 2-3, 26, 3-3, and 3-6, where N-M denotes the maximum lengthsof N graphemes and M phonemes, respectively. The nbest Viterbi training in city+del and city+del+merge employs only 2-best alignments. The hypothesis that thedeletion character continuously appears in the expansionof the pronunciation hypothesis is prohibited. The number of Web pages used in mining is 500 pages per keyword. The threshold of confidence, which means the similarity based on DP matching, for accepting a pronunciation extracted from Web is 1. Details of experimental
data are shown in Table 2.
5.2. Experimental result
The experimental result is shown in Table 3. In the comparison of Recall, city+del+merge was found to outperform joint 1-6, which has the highest Recall in joint,
by about 1.9 points. The difference between these Recall results is significant according to paired t-testing at
a level of 0.05. In the comparison of Precision, joint
3-6, which has the highest Precision in joint, outperformed city+del+merge by about 0.6 points. However,the difference between those values of Precision is notsignificant according to paired t-testing at a level of 0.05.
These results shows that our many-to-many alignment including extensions in Step 4 produces an alignment thathas a high generalization ability for OOV words without
degrading Precision compared with the joint multigram
approach of the conventional method. Additionally, interms of F-value, city+del+merge outperformed joint 23, which has the highest F-value in joint, by about 1.9
points.

baselineconventional
methods

proposedmethods

5 http://searchranking.yahoo.co.jp/F-value
(%)
84.91
90.54
90.54
90.9090.22
90.15
89.55
91.29
92.61

90.31

95.33

92.75

We proposed a many-to-many alignment including extensions, which are parameter estimation that considers theproperty of the deletion character by employing n-best
Viterbi training, and the mergence method of an irrelevant
mapping, and performed the evaluation experiment of ourexpanded many-to-many alignment by automatic pronunciation annotation using Web text mining. The experiment revealed that our expanded many-to-many alignment improves the generalization ability for OOV words
compared with the joint multigram approach of the conventional method.

7. References[1]

M. Bisani and H. Ney, “Joint-sequence models for grapheme-tophoneme conversion,” Speech Communication, vol. 50, no. 5, pp.
434–451, 2008.

[2]

S. Jiampojamarn and G. Kondrak, “Online discriminative training
for grapheme-to-phoneme conversion,” In Proc. INTERSPEECH,
pp. 1303–1306, September 2009.

[3]

S. Jiampojamarn, C. Cherry and G. Kondrak, “Integrating joint
n-gram features into a discriminative training framework,” Human Language Technologies: The 2010 Annual Conference of theNorth American Chapter of the ACL, pp. 697–700, June 2010.

[4]

J. Miyake, S. Takeuchi, H. Kawanami, H. Saruwatari andK. Shikano, “Automatic reading annotation to Japanese trendy
words based on parentheses expression,” In Proc. Oriental COCOSDA 2008, November 2008.

[5]

R. I. Damper, Y. Marchand, J. D. S. Marsters and A. I. Bazin,“Aligning text and phonemes for speech technology applications
using an EM-like algorithm,” In Journal of Speech Technology,
Vol. 8, No. 2, pp. 147-160, June 2005.

[6]

S. Deligne, F. Yvon and F. Bimbot, “Variable-length sequence
matching for phonetic transcription using joint multigrams,” InProc. EUROSPEECH, pp. 2243–2246, September 1995.

[7]

S. Deligne and F. Bimbot, “Inference of variable-length acoustic
units for continuous speech recognition,” Speech Communication,
vol. 23, no. 3, pp. 223–241, 1997.

[8]

S. Jiampojamarn, G. Kondrak and T. Sherif, “Applying many-tomany alignments and hidden Markov models to letter-to-phoneme
conversion,” In Proc. NAACL HLT 2007, pp. 372-379, April 2007.

[9]

K. Kubo, H. Kawanami, H. Saruwatari and K. Shikano, “Unconstrained many-to-many alignment for automatic pronunciation annotation,” In Proc. APSIPA 2011, October 2011.

2 http://www.sanseido-publ.co.jp/
4 http://www.eijiro.jp

Precision
(%)
95.87
93.27
92.81
95.81
95.54
95.83
95.93
93.43
95.12

6. Conclusion

1 http://freewnn.sourceforge.jp/
3 http://sourceforge.jp/projects/naist-jdic/

joint 1-3
joint 1-6
joint 2-3
joint 2-6
joint 3-3
joint 3-6
city
city+delcity+del+merge

Recall
(%)
76.19
87.95
88.38
86.46
85.46
85.10
83.96
89.24
90.24

6 http://www.google.co.jp/m/trends
7 http://ranking.goo.ne.jp/keyword/
8 http://www.phontron.com/kytea/index-ja.html

INTERSPEECH 20122321