2014 IEEE International Conference on Acoustic, Speech and Signal Processing (ICASSP)NARROW ADAPTIVE REGULARIZATION OF WEIGHTSFOR GRAPHEME-TO-PHONEME CONVERSION
Keigo Kubo

Sakriani Sakti

Graham Neubig

Tomoki Toda

Satoshi Nakamura

Graduate School of Information Science, Nara Institute of Science and Technology (NAIST), Japan
ABSTRACTAs the speech recognition field proceeds to open domain
and multilingual tasks, the need for robust g2p conversion
has been increasing. Towards this objective, we propose
a new g2p conversion training method based on the Narrow Adaptive Regularization of Weights (NAROW) online
learning algorithm. NAROW improves over its predecessor
AROW by automatically adjusting hyperparameters to reduce mistake bounds, and ensuring that the learning rate is
not updated when features for the input data have alreadybeen updated enough. The contribution of this paper is first to
extend NAROW to structured learning, and show the inequality to bound the maximum number of errors in structured
NAROW. In experiments, our proposed approach significantly improved over MIRA with consistent phoneme error
rate reductions of 1.3-3.8% on a variety of dictionaries.
Index Terms— g2p conversion, out-of-vocabulary word,
online discriminative training, structured learning, NAROW
1. INTRODUCTION
Out-of-vocabulary (OOV) words are the bottleneck in largevocabulary open-domain speech recognition systems [1] andtext-to-speech systems [2]. In order to solve the problem of
OOV words, Grapheme-to-phoneme (g2p) conversion, whichis structured learning problems for which there are an extremely large number of candidate answers, has been used
for a long time. As the speech recognition field proceeds tothe open-domain and the multilingual [3] the need for robust
g2p conversion has been increasing.
Rule-based approaches [4] and statistical approaches
based on methods such as neural networks [5], decision trees[6], maximum entropy [7], joint sequence model [8, 9] haveall been proposed for the g2p task. Most recent attempts
have applied online discriminative training employing richfeatures [10, 11, 12]. One of the representative methods is the
Margin Infused Relaxed Algorithm (MIRA) [13], an online
structured learning method extended to g2p conversion by
Jiampojamarn et al. [10, 11]. We have also recently proposeda method for g2p conversion based on structured Adaptive
Regularization of Weight Vectors (AROW) [12], an online
learning method designed to resolve MIRA’s overfitting problems by estimating the confidence of each weight represented

978-1-4799-2893-4/14/$31.00 ©2014 IEEE2608

by a second order information matrix. However, structured
AROW is still not a complete solution. The inverse of thesecond order information matrix representing the confidenceof the weights serves as a learning rate for each weight, andthese values are reduced with each update. This can cause
cases where a particular weight converges to an inappropriate value, and cannot be updated further because its learning
rate approaches zero. Also, it is difficult to choose AROW’s
hyperparameter to adjust the generalization of learning [14].
In order to solve the above problems, an expansion of
AROW called Narrow Adaptive Regularization of Weights(NAROW) [15] has been proposed. Specifically, NAROW
chooses a better value of the hyperparameter on each update
to minimize the mistake bound. In addition, the second moment is not updated when features for input data have highconfidence, preventing early convergence to bad weights. In
order to incorporate these advantages into g2p conversion,
we propose an online structured learning algorithm based on
NAROW, which we call structured NAROW.
The first contribution in this paper is to extend NAROW
to structured learning problems, and show the inequality tobound the maximum number of errors in this context. The
inequality is derived based on the online convex optimization
framework [15]. We also evaluate structured NAROW on a
g2p task comparing with the joint sequence model, structured
learning based on MIRA, and structured AROW.
2. G2P CONVERSION
2.1. Formalization
We define g2p conversion as a process of converting agrapheme sequence x into a phoneme sequence y. Givena correct phoneme sequence y for a grapheme sequence x,
we formalize g2p conversion asŷ = arg max wT Φ(x, y),(1)ywhere w indicates the classifier’s weight vector and Φ(x, y)
indicates a feature vector which consists of arbitrary values
such as frequencies of joint n-gram features [11] on x and
y. In Eq.(1), ŷ can be efficiently obtained using dynamic
programming. Structured learning can be employed to obtaina w that allows for accurate prediction of the correct phoneme
sequence in this framework.

2.2. Existing G2P online structured learnings
The most widely used method for online structured learning in g2p is based on MIRA [13]. Given the i-th example(xi , yi ) and the N -best hypotheses ŷ1 , . . . , ŷN , MIRA updates wt by solving
1
arg min ∥wt − wt−1 ∥2 ; s.t. ℓ(xi , yi , ŷn , wt ) = 0; ∀n, (2)2wt
where ℓ is a loss function that outputs zero when the correct
yt scores higher than the hypothesis ŷt with sufficient margin,
and a positive value otherwise. MIRA moves weights aggressively to correctly classify the N -best according to Eq.(2),and thus is prone to overfitting outliers or noisy data.
To resolve the overfitting, we have proposed structured
AROW, the binary classifier AROW [14] to online structured
learning. It updates wt by minimizing the following function
over ŷ1 , . . . , ŷN sequentially.
L(wt , Σt ) =DKL (N (wt , Σt )||N (wt−1 , Σt−1 ))
1
1 T
+ 2r
ℓ(xi , yi , ŷn , wt ) + 2r
ot Σt ot

(3)

DKL (N (wt , Σt )||N (wt−1 , Σt−1 )) is the Kullback-Leibler
divergence between the Gaussian distributions for wt andwt−1 , r > 0 is a hyperparameter to adjust the generalizationof learning and ot is Φ(xi , yi ) − Φ(xi , ŷn ). The covariancematrix Σ, roughly speaking, is a learning rate for w. Its inverse Σ−1 is a second order information matrix representing
the confidence of each feature. Σ is also updated so thatlearning rates for observed features decrease, namely, confidences for observed features increase. The minimizationof Eq.(3) updates the weights so that the correct hypothesis
scores higher than other hypotheses with minimal change
to the distribution, considering the variance of each weight.
By introducing the Σ, AROW avoids excessively moving theweights of the important features that have frequently been
observed and updated. This property reduces the overfitting problem. We showed that structured AROW improves
phoneme error rate and word error rate over MIRA in a g2p
task employing a dataset including artificial noisy data [12].
However, there are two main issues in structured AROW.
One is a problem where a some weights converge to inappropriate values for some orderings of the training data and cannot be updated further because their learning rates approachzero. Another is that it is difficult to choose a good r on eachround t.
3. STRUCTURED NAROWIn this section, we describe our proposed extension of NAROW
from binary classification to structured learning. We first
overview NAROW and note its differences from AROW.
The difference between AROW and NAROW is the settingof the r. AROW sets a fixed value to r in every round t,
and the setting increases confidences linearly. On the other
hand, the setting in NAROW increases confidences logarithmically when features for input data have low confidence,

2609

Algorithm 1 The proposed online structured learning algorithm based on Follow the Regularized Leader
Input:Training dataset D = {(x̄1 , ȳ1 ), ..., (x̄|D| , ȳ|D| )}and a series of regularizers f0 , . . . , fT −1
Output:weight vector wT
t = 1, θ0 = 0
repeatfor i = 1 to |D| do∗
wt = ∇ft−1(θt−1 ) = Σt−1 θt−1
Predict N -best hypotheses ỹ1 , ..., ỹN by wtT Φ(x̄i , ỹ)
for n = 1 to N do
Consider xt := x̄i , yt := ȳi , ŷt := ỹn andℓt (wt ) := max(0, vt dt − wtT ot )if ℓt (wt ) > 0 thenzt = −ot ∈ ∂ℓt (wt )θt = θt−1 − zt
t=t+1∗
wt = ∇ft−1(θt−1 ) = Σt−1 θt−1
end ifend forend foruntil Stop condition is met

and does not increase confidences otherwise. This implies
that NAROW, unlike AROW, does not reduce learning rates
close to zero, preventing early convergence to bad weights.
The setting of the r in NAROW derives from minimizing themistake bound for NAROW, namely, the setting chooses agood r on each round t, which we will describe in the structured learning context in Section 4. The rest of this section
describes a concrete algorithm for our structured NAROW.
The learning algorithm for structured NAROW builds on
the Follow the Regularized Leader (FTRL) defined in [15] forbinary classification. Our proposed method expands this to
structured prediction employing N -best candidates for learning, as shown in Algorithm 1. The FTRL updates the wt bysolving
wt = arg min
wt

t−1
∑

ηi ziT wt + ft−1 (wt ),

(4)

i=1

where ηi and zi denote a learning rate and a subgradient ofa loss function in ∂ℓi (wi ) on round i respectively. ft−1 (wt )is a regularizer (also known as potential function) which controls the amount of generalization of learning. In the proposed
structured NAROW, the ηt is 1 on every round t and the loss
function ℓ is defined asℓt (wt ) = max(0, vt dt − wtT ot ),(5)

where vt = oTt Σt−1 ot > 0 adjusts differences in the number of features considering the variance Σt−1 . Also dt =d(yt , ŷt ) indicates the loss incurred by incorrectly classifying
yt as ŷt . We define dt as the number of phoneme errors forthe g2p task. As a subgradient zt of the above loss, we choose

−ot when ℓt (wt ) > 0 and 0 otherwise. Next, we define atured learning. We introduce the following condition

T

ot ot
−1
regularizer ft (o) as 12 oT Σ−1= Σ−1
t o, where Σtt−1 + rt ,rt > 0 and Σ0 = I. The update form of Σ−1is the same astthat of AROW when rt is a fixed value in every t. The settting of the rt in our structured NAROW is rt = bvvt −1
when
bvt > 1 and rt = +∞ otherwise, where b > 0 is a new
hyperparameter (for its derivation, see Section 4). Note thatin NAROW of binary classification, ft (o) is used instead of
ft−1 (o) as a regularizer at wt like second order perceptron[16]. However, we use ft−1 (o) for it because ot required forft (o) is unknown before the classifying in structured problem. Finally the updated weight for Eq.(4) is obtained by−1∗(θt−1 ) = Σt−1 θt−1 ,(6)wt = ∇ft−1(θt−1 ) = ∇ft−1∑t−1∗
where θt−1 = − i=1 zi , θ0 = 0 and ∇ft−1(θt−1 ) is∗∗a gradient of the Fenchel conjugate{ ft−1 for ft−1 . }ft−1∗
T
is defined as ft−1 (θt−1 ) := supv θt−1 v − ft−1 (v) =1 T
2 θt−1 Σt−1 θt−1 .

dt − ℓt (u) ≤ −uT zt ; ∀u ∈ S, vt ≥ 1,

(7)

where zt denotes any subgradient satisfying ℓt (wt ) > 0. For
now, we assume vt ≥ 1 in Eq.(7) is satisfied, and discuss
exceptions in Section 4.3. From Lemma 1 in [15], the setting
in section 3, Eq.(7), and ft (λu) ≤ λ2 ft (u), we have∑∑∑(dt − ℓt (u)) = D +dt −ℓt (u)t∈M ∪U

t∈U

≤
+

2

λ∥u∥
+
2

∑

(

t∈M ∪UTλ(u xt )2t∈M ∪U

2rt

m2t
mt
vt rt
−
+
),
2λ(rt + vt ) 2λ(rt + vt )λ(8)where mt = oTt Σt−1 θt−1 , u is any weight vector, λ ≥ 0 is
any scale factor, D is the number of errors, M is the setting ofround t for prediction mistakes and U is the setting of round t
for correct prediction, with ℓt (wt ) > 0.

4. MISTAKE BOUND FOR STRUCTURED NAROWIn the previous section, The setting of the rt in structuredt
NAROW was rt = bvvt −1
when bvt > 1 and rt = +∞ otherwise, For deriving the setting, we show the mistake bound of
structured NAROW based on online convex optimization.
4.1. Online convex optimization
Online convex optimization is a method for designing online learning algorithms and analyzing them through a potential function (regularizer) [17], and plays an integral role inderiving a mistake bound for NAROW. Online convex optimization based on primal-dual progress has been proposed in[18, 19, 20]. Orabona et al. [15] has generalized it to timevarying potential functions. The generalized online convex
optimization framework based on FTRL is employed to derive the mistake bound of NAROW.
We describe some definitions from convex analysis. A
β-strongly convex w.r.t a norm ∥ · ∥ is a function satisfying
f (v) ≥ f (u) + ∇f (u)T (v − u) + 12 β∥v − u∥2 , whereu, v ∈ ri(dom(f )). The functions ft (o) = 12 oT Σ−1
t o defined in Section 3 are 1-strongly convex w.r.t. the norms∥o∥2ft = oT Σ−1∥·∥t o. The dual norm{∥ · ∥∗ for a norm}
is the norm defined as ∥u∥∗ := sup uT v : ∥v∥ ≤ 1 . A βstrongly smooth w.r.t ∥·∥∗ is a function satisfying f∗ (u+v) ≤f∗ (u)+∇f∗ (u)T v+ 12 β∥v∥2∗ . The ft∗ (o) = 21 oT Σt o definedin Section 3 are 1-strongly smooth w.r.t ∥o∥2ft∗ = oT Σt o. The
β-strongly convex/smooth are important properties in order toderive a mistake bound.
4.2. Derivation of mistake boundThis section gives a brief sketch of the mistake bound derivation, and we refer readers to [15] for more detail although
there is a difference between binary classification and struc-2610

4.3. Selection of hyperparameters rt
We would like to choose better hyperparameters rt minimizing the right side of the above mistake bound. Orabona etT2
v t rtal. [15] focus on minimizing the terms λ(u2rxt t ) + 2λ(rt +vt )
in Eq.(8). The setting proposed by Orabona et al. was rt =vt
bvt −1 when bvt > 1 and rt = +∞ otherwise. The setting
implies we should increase confidences logarithmically whenfeatures for input data have low confidence, and not increase
confidences otherwise. Then, we have∑∑ λbvt (uT xt )2λ∥u∥2D≤ℓt (u) ++2
2(rt + vt )t∈M ∪U

t:bvt >1

∑
1 ∑
1
m2t
+
(min( , vt ) −+ 2mt ) −dt . (9)2λb(rt + vt )t∈M ∪Ut∈U

By tuning λ, the mistake bound for structured NAROW isvu∑∑ bvt (uT xt )2uD≤ℓt (u) +t∥u∥2 +(rt + vt )t∈M ∪U
t:bvt >1
v
u ∑
∑
u
m2t
1
×t
+ 2mt ) −dt . (10)(min( , vt ) −b(rt + vt )t∈M ∪Ut∈U

Note that because the number of features in g2p conversion
is large, we employ a diagonalorder{ matrix} as the second
information matrix using diag Σ−1
instead of Σ−1tt .
For the inequality vt ≥ 1 in Eq.(7), the vt is not too small
when b is a small value. So we attempt to satisfy the inequality by setting b to a small value. 1
1 Note that g2p conversion employs rich feature set and therefore the inequality is almost always satisfied.

Table 1. Dataset used in the experiment on the g2p
task; dataset name (Dataset), the number of grapheme andphoneme symbols (g/p), vocabulary sizes of training data
(Train), development data (Dev), and test data (Test) and thenumber of trials of cross-validation (K-fold)
DatasetNETtalk
BrulexCELEXEnglishCMUdict

g/p
26/50
40/39

Train
17595
23353

Vocabulary size
Dev
Test
1000
1000
1373
2747

26/53

39995

15000

5000

1

27/39

100886

5941

12000

2

K-fold10
5

Table 2. Parameter settings for the experiment.
joint n-gramcontext
window
N -besthypotheses
hyperparameter r
hyperparameter b
beam width

Sequitur7

DirecTL+
5

SAROW
5

SNAROW
5

-

6

6

6

-

5

5

5

-

-

500,
1000,1500

-

-

-

-

-

50

50

0.0075,0.01,0.0125
50

5. EXPERIMENT AND RESULT
We evaluated our structured NAROW on the g2p task. Table
1 shows datasets employed in the experiment. The development data is employed to determine the optimal number oftraining iterations. For datasets in Table 1, NETtalk (English)
and Brulex (French) were obtained from the Pascal Letterto-Phoneme Conversion Challenge2 . CMUdict (English) and
CELEX (English) were also obtained from their corresponding Web pages3 4 . We attempted to faithfully follow the convention in [9] in terms of data exclusion and data split, except
extracting development data from training data.
We employed Sequitur5 , DirecTL+6 and structured AROW
(SAROW) as baseline g2p conversion tools in this experiment. Sequitur is based on the generative model employing
joint n-grams for graphemes and phonemes. DirecTL+ uses
structured learning based on MIRA. The implementation of
SAROW and structured NAROW (SNAROW) used in thisexperiment is implemented in slearp7 . DirecTL+, SAROW
and SNAROW, which is our proposed approach, employedcontext features, chain features, and joint n-gram features.
For alignment used in DirecTL+, SAROW and SNAROW,
2 http://pascallin.ecs.soton.ac.uk/Challenges/PRONALSYL/Datasets

Table 3. Evaluation result for phoneme error rate (PER) andword error rate (WER) in the g2p task. Values on NETtalk,
Brulex and CMUdict in this table are obtained by averaging
results on each cross-validation. The best performance andperformances that have no significant difference according toPaired Bootstrap Resampling [22] at a level of 0.05 over thebest performance are written in bold.
Dataset Measure Sequitur DirecTL+ SAROW NAROW
NETtalk PER(%)
7.71
6.70
6.75
6.53
WER(%) 31.6
28.18
28.66
27.97
BrulexPER(%)
1.26
1.03
1.09
0.99
WER(%) 6.57
5.24
5.59
5.14
CELEX PER(%)
2.62
2.39
2.51
2.30
11.07
11.81
11.17
English WER(%) 12.15
CMUdict PER(%)
6.77
6.19
6.15
6.11
WER(%) 28.55
26.35
26.48
26.46

we used the unconstrained many-to-many alignment methodof [21] as implemented in mpaligner8 . The context window
size, joint n-gram size, hyperparameter r and N -best hypotheses for training were determined based on our previous
work [12], except beam width for beam-search pruning andhyperparameter b. Table 2 shows their details. The training iterations, the hyperparameter r and b are determined byphoneme error rate on the development data.
Table 3 shows the evaluation result on the g2p task. From
Table 3, for the PER, SNAROW improved over all other approaches with a significant difference on all datasets except
CMUdict according to Paired Bootstrap Resampling [22] at
a level of 0.05. The error rate reduction (ERR) over MIRA
was 2.5% on NETtalk, 3.9% on Brulex, 3.8% on CELEX and1.3% on CMUdict. Thus, we can see that replacing structured
AROW with structured NAROW is effective on real datasets,even the relatively clean ones used in our experiments.
6. CONCLUSION
We proposed structured NAROW, extending NAROW tostructured learning, and evaluated it on the g2p task. Structured NAROW solves structured AROW’s problems bychoosing a better value of the hyperparameter r on each
update so that the mistake bound is low and avoiding updating the second-moment when features for input data havehigh confidence. In the experiment, our proposed approachsignificantly improved over MIRA, with consistent ERRs of
1.3-3.8% in PER on a variety of dictionaries.
7. ACKNOWLEDGMENTS
Part of this work was supported by JSPS KAKENHI Grant
Number 24240032 and by the Commissioned Research of National Institute of Information and Communications Technology (NICT), Japan.

3 http://www.speech.cs.cmu.edu/cgi-bin/cmudict
4 http://www.ldc.upenn.edu/Catalog/

catalogEntry.jsp?catalogId=LDC96L14
5 http://sequitur.info/
6 http://code.google.com/p/directl-p/
7 http://sourceforge.jp/projects/slearp/

8 http://sourceforge.jp/projects/mpaligner/2611

8. REFERENCES[1] Bahl et al., “Automatic phonetic baseform determination,” in Proc. ICASSP. 1991, pp. 173–176, IEEE.
[2] Juergen Schroeter, Alistair Conkie, Ann Syrdal, Mark
Beutnagel, Matthias Jilka, Volker Strom, Yeon-Jun Kim,
Hong-Goo Kang, and David Kapilow, “A perspectiveon the next challenges for tts research,” in Speech Synthesis, 2002. Proceedings of 2002 IEEE Workshop on,
2002, pp. 211–214.

[13] Koby Crammer and Yoram Singer, “Ultraconservative
online algorithms for multiclass problems,” Journal of
Machine Learning Research, vol. 3, pp. 951–991, 2003.
[14] Koby Crammer, Alex Kulesza, and Mark Dredze,“Adaptive regularization of weight vectors,” in Advances In Neural Information Processing Systems,
2009, vol. 23, pp. 414–422.
[15] Francesco Orabona and Koby Crammer, “New adaptive algorithms for online classification,” in Proc. NIPS,
2010, pp. 1840–1848.

[3] Tim Schlippe, Sebastian Ochs, and Tanja Schultz,“Grapheme-to-phoneme model generation for IndoEuropean languages,” in Proc. ICASSP, 2012, pp. 4801–
4804.

[16] Nicolò Cesa-Bianchi, Alex Conconi, and Claudio Gentile, “A second-order perceptron algorithm,” SIAM Journal on Computing, vol. 34, no. 3, pp. 640–668, 2005.

[4] Ronald M Kaplan and Martin Kay, “Regular models ofphonological rule systems,” Computational linguistics,
vol. 20, pp. 331–378, 1994.

[17] Nicolo Cesa-Bianchi and Gábor Lugosi, “Potentialbased algorithms in on-line prediction and game theory,”
Machine Learning, vol. 51, no. 3, pp. 239–261, 2003.

[5] Terrence J Sejnowski and Charles R Rosenberg, “Parallel networks that learn to pronounce English text,” Complex Syst., vol. 1, pp. 145–168, 1987.

[18] Shai Shalev-shwartz and Yoram Singer, “Convex repeated games and fenchel duality,” in Advances in Neural Information Processing Systems 19, pp. 1265–1272.
MIT Press, Cambridge, MA, 2006.

[6] Walter Daelemans and Antal Van Den Bosch,“Language-independent
data-oriented
graphemeto-phoneme conversion,”in Progress in Speech
Processing. 1997, pp. 77–89, Springer-Verlag.

[19] Shai Shalev-Shwartz, Online learning: Theory, algorithms, and applications, Ph.D. thesis, The Hebrew University, 2007.

[7] Stanley F Chen et al., “Conditional and joint models
for grapheme-to-phoneme conversion,” in Proc. EUROSPEECH, 2003, pp. 2033–2036.
[8] Sabine Deligne and Frédéric Bimbot, “Inference ofvariable-length linguistic and acoustic units by multigrams,” Speech Communication, vol. 23, no. 3, pp. 223–
241, 1997.
[9] Maximilian Bisani and Hermann Ney, “Joint-sequencemodels for grapheme-to-phoneme conversion,” SpeechCommunication, vol. 50, no. 5, pp. 434–451, 2008.
[10] Sittichai Jiampojamarn and Grzegorz Kondrak, “Online
discriminative training for grapheme-to-phoneme conversion,” in Proc. INTERSPEECH, 2009, pp. 1303–
1306.
[11] Sittichai Jiampojamarn, Colin Cherry, and Grzegorz
Kondrak, “Integrating joint n-gram features into a discriminative training framework,” in Proc. NAACL-HLT,
2010, pp. 697–700.
[12] Keigo Kubo, Sakriani Sakti, Graham Neubig, Tomoki
Toda, and Satoshi Nakamura, “Grapheme-to-phoneme
conversion based on adaptive regularization of weightvectors,” in Proc. INTERSPEECH, 2013, pp. 1946–
1950.

2612

[20] S Kakade, Shai Shalev-Shwartz, and Ambuj Tewari,“On the duality of strong convexity and strong smoothness: Learning applications and matrix regularization,” Unpublished Manuscript, http://ttic. uchicago.
edu/shai/papers/KakadeShalevTewari09. pdf, 2009.
[21] Keigo Kubo, Hiromichi Kawanami, Hiroshi Saruwatari,
and Kiyohiro Shikano, “Unconstrained many-to-manyalignment for automatic pronunciation annotation,” inProc. APSIPA, 2011, pp. 1–4.
[22] Philipp Koehn, “Statistical significance tests for machine translation evaluation.,” in EMNLP, 2004, pp.
388–395.