Viterbi training in PRISM

Taisuke Sato
Keiichi Kubota
Tokyo Institute of Technology, Oookayama 2-12-1, Meguro, Tokyo, Japan

Abstract
VT (Viterbi training), or hard EM, is an efﬁcient way of parameter learning for probabilistic models with hidden variables. Givenan observation y, it searches for a state ofhidden variables x that maximizes p(x, y | θ)by coordinate ascent on parameters θ. In
this paper we introduce VT to PRISM, alogic-based probabilistic modeling system forgenerative models. VT improves PRISM’s
probabilistic modeling in two ways. First although generative models are said to be inappropriate for discrimination tasks in general, when parameters are learned by VT,
models often show good discrimination performance. We conducted two parsing experiments with probabilistic grammars whilelearning parameters by a variety of inference
methods, i.e. VT,EM,MAP and VB. The result is that VT achieves the best parsing
accuracy among them in both experiments.
Second since VT always deals with a single
probability of a single explanation, Viterbi
explanation, the exclusiveness condition imposed on PRISM programs is no more required when we learn parameters by VT.
PRISM with VT thus allows us to write inclusive clause bodies, learn parameters andcompute Viterbi explanations.

1. Introduction
VT (Viterbi training) has been used for long time as
an eﬃcient parameter learning method in various research problems such as machine translation based onword alignment (Brown et al., 1993), speech recognition to estimate parameters of Hidden Markov Models (Juang & Rabiner, 1990; Strom et al., 1999), imAppearing in Proceedings of the 29 th International Conference on Machine Learning, Edinburgh, Scotland, UK, 2012.
Copyright 2012 by the author(s)/owner(s).

sato@mi.cs.titech.ac.jp
kubota@mi.cs.titech.ac.jp

age analysis for supervised and unsupervised learning of multi-dimensional HMMs (hidden Markov Models) (Joshi et al., 2006), parsing by unsupervised learning of dependency models (Spitkovsky et al., 2010),
and gene ﬁnding by unsupervised learning of HMMs
(Lomsadze et al., 2005). Although VT is NP-hardeven for PCFGs (probabilistic context free grammars),
which is proved by encoding the 3-SAT problem into
PCFGs (Cohen & Smith, 2010), and is not a consistent estimation method unlike MLE (maximum likelihood estimation)(Lember & Koloydenko, 2007), it often outperforms and runs faster than the conventional
EM algorithm.
We introduce this VT to PRISM which is a probabilistic extension of Prolog (Sato & Kameya, 2001; 2008).
There are already multiple parameter learning methods available in PRISM. One is the EM algorithm, or
more generally MAP (maximum a posteriori) estimation (Sato & Kameya, 2001). Another is VB (variational Bayes) (Sato et al., 2009) which approximately
realizes Bayesian inference and learns pseudo counts
assuming Dirichlet priors over parameters. They are
implemented on PRISM’s data structure called explanation graphs representing AND/OR boolean formulas
made up of probabilistic ground atoms. Probabilities
used in EM, MAP and VB are all computed by running the generalized IO algorithm or its variant on
explanation graphs.
VT in PRISM runs on explanation graphs just likeEM, MAP and VB but always computes a single probability of a single explanation called Viterbi explanation or most probable explanation. Not only this results in faster computation but thanks to the natureof VT’s objective function which diﬀers from the likelihood of data, VT tends to learn parameters yielding
better prediction performance in tasks such as parsing
as we see later.
In addition VT brings about a favorable side eﬀect on
PRISM. It makes unnecessary the exclusiveness condition imposed on PRISM programs to ensure eﬃcient
probability computation. This is because it always

Viterbi training in PRISM

deals with a single probability of Viterbi explanationand hence there is no need for summing up probabilities of non-exclusive explanations. Consequently
PRISM can learn parameters by VT from programs
that do not satisfy the exclusiveness condition andcompute Viterbi explanations using the learned parameters.

2. Viterbi training and PRISM
2.1. Viterbi training
Let x be hidden variables, y observed ones and p(x, y |θ) their joint distribution with parameters θ1 . MLE
estimates parameters θ from y as the maximizer of the(log) likelihood function LEM (y | θ):∑def
LEM (y | θ) = log
p(x, y | θ).
x

In the case of MAP (maximum a posteriori) estimation, we add a prior distribution p(θ) and use
LM AP (y | θ) as an objective function:∑def
LM AP (y | θ) = log
p(x, y | θ)p(θ).
xWhat VT does is similar to MLE and MAP but it uses
a diﬀerent objective function LV T (y | θ) deﬁned as
def

LV T (y | θ)=log maxx p(x, y | θ)p(θ).

VT estimates parameters as the maximizer of LV T (y |θ) by coordinate ascent that alternates the maximization of log p(x, y | θ) w.r.t. x and the maximization oflog p(x, y | θ) w.r.t. θ:x(n)=argmaxx log p(x, y | θ(n) )(1)

θ(n+1)=

argmaxθ log p(x(n) , y | θ)(2)Starting with appropriate initial parameters θ(0) , VT
iterates the above two steps and terminates whenx(n+1) = x(n) holds (recall we assume random variables are discrete). Proving the convergence property
of VT is straightforward.

2.2. VT for PRISM
Here we reformulate VT in the context of PRISM.
We skip an introductory explanation of PRISM. The
reader is referred to (Sato & Kameya, 2001; 2008) for
its semantics, tabled search, explanation graph andprobability computation.
Let DB be a PRISM program with parameters θ and
PDB (· | θ) a probability measure deﬁned by DB. Also
let G = G1 , . . . , GT be a list of observed iid goals, andexpl(Gt ) (1 ≤ t ≤ T ) the set of explanations ²t (conjunctions of msw atoms) such that ²t , DB ` Gt . G corresponds to observed variables y and {²t }Tt=1 to hidden
variables x in p(x, y | θ) in the previous subsection. We
use θi,v for parameter s (probabilities) of multi-valued
switch msw(i,v) (v ∈ Vi ) where i is a switch identiﬁer (ground term) and Vi is a ﬁnite set of possible
outcomes (ground terms)∑ declared by values/3 declaration in DB. Soθ= 1 holds. We put
v∈V∪
i i,v
θ i = {θi,v }v∈Vi and θ = i θ i where i ranges overpossible switch identiﬁers.
introduce a prior distribution p(θ i )∝αi,v −1, Dirichlet distribution with hyperv∈Vi θi,v
parameters {αi,v }v∈Vi , over θ i . In the following, toavoid the diﬃculty of zero-probability encounteredin parameter learning, we assume pseudo countdef
δi,v = αi,v − 1 > 0 and use δi,v instead of αi,v .
We∏

Finally we deﬁne Viterbi explanation ²∗t for a goal Gt
as a most probable explanation for Gt given by²∗t= argmax²t ∈expl(Gt ) PDB (²t | θ)p(θ).

(3)

The objective function LV T (G | θ) for VT in PRISM
is now computed as follows.
LV T (G | θ)=log max²t ∈expl(Gt ),1≤t≤T

T∏

PDB (²t , Gt | θ)p(θ)

t=1

=

log

T
∏

max²t ∈expl(Gt ) PDB (²t | θ)p(θ)

t=1

LV T (y | θ

(n+1)

)

=

(n+1)

log p(x,y | θ

(n+1)

)p(θ

≥ log p(x , y | θ
)p(θ
(n)
(n)
≥ log p(x , y | θ )p(θ(n) )= LV T (y | θ(n) )
(n)

(n+1)

(n+1)

(n+1)

)

i,v

)

So LV T (y | θ(n) ) ≤ LV T (y | θ(n+1) ) ≤ 0 for everyn = 0, 1, . . . Since {LV T (y | θ(n) )}n is a monotonicallyincreasing sequence with an upper bound, it converges
as n goes to inﬁnity.
1=

In this paper, we assume distributions are discrete.

∏ ∑T σi,v (²∗t )+δi,v
log
θi,v t=1

=

( T
∑ ∑
i,v

)
σi,v (²∗t ) + δi,v

log θi,vt=1where “i, v” ranges over those satisfying msw(i,v) in ²∗tand σi,v (²∗t ) is the number of occurrences of msw(i,v)
in ²∗t .
By substituting various deﬁnitions and formulas into
equations (1) and and (2), we obtain the VT algorithm

Viterbi training in PRISM

for PRISM which alternately executes (4) and (5)(n)
where θ (n) stands for the set of parameters {θi,v }i,v
at step n.
∗(n)

²t

(n+1)

θi,v

= argmax²t ∈expl(Gt ) log PDB (²t | θ (n) )(4)
∝

T
∑

∗(n)

σi,v (²t) + δi,v(5)

t=1Here (4) corresponds to (1) and (5) to (2) respectively.
Given observed goals G = G1 , . . . , GT , we ﬁrst perform tabled search for all explanations to build explanations graphs representing expl(Gt ) for each t(1 ≤t ≤ T ). Then starting from the initial parametersθ (0) 2 , we repeat (4) and (5) alternately while eﬃciently
computing the Viterbi explanations (4) based on the∗(n+1)∗(n)explanation graphs until ²t= ²t
holds for all t(n+1)(1 ≤ t ≤ T ). {θi,v }i,v are then learned parameters.
One of the problems of VT is the sensitivity to theinitial condition. So we need to carefully choose θ (0) .
Uniform distributions for θ (0) (Spitkovsky et al., 2010)∗(0)
and ²t (1 ≤ t ≤ T ) (Cohen & Smith, 2010) are possible choices. In practice, we further add random restart
to alleviate the sensitivity problem.

3. Learning experiments withprobabilistic grammars
In this section3 we apply VT to parsing tasks in natural language processing where observable variables aresentences and hidden variables are parse trees. We
predict true parse trees for given sentences using probabilistic grammars (PCFG and PLCG) whose parameters are learned by VT and compare the parsing performance with EM, MAP and VT.
3.1. VT for PCFGs
Prior to describing the parameter learning experimentwith a PCFG by VT, we brieﬂy review how to write
PCFGs in PRISM. In PCFGs, sentence derivation iscarried out probabilistically. When there are k PCFG
rules θ1 : A → β1 , . . . , θk : A → βk for a nonterminal
A with probabilities θ1 , . . . , θk (θ1 + · · · + θk = 1), A
is expanded by A → βi into βi with probability θi .
The probability of a parse tree τ is the product ofprobabilities associated with occurrences of CFG rulesin τ and the probability of a sentence is the sum of
2∗(0)

We may start from some ²t
as well.
Experiments are done using PRISM augmented withpreliminarily implemented VT.
3values(’S’,[[’S’,’S’],[a],[b]],[0.4,0.3,0.3]).
pcfg(L):- pcfg([’S’],L,[]).
pcfg([A|R],L0,L2):( get_values(A,_) ->msw(A,RHS),
pcfg(RHS,L0,L1); L0=[A|L1] ),pcfg(R,L1,L2).
pcfg([],L,L).

% msw(A,_) exists, so% A is a nonterminal

Figure 1. A PCFG program

probabilities of parse tress for the sentence.
Writing PCFG programs is easy in PRISM. Figure 1
is a PRISM program for a PCFG { 0.4:S→S S,
0.3:S→a, 0.3:S→b }. In general, PCFG rules suchas { θ1 : A → β1 , . . . , θk : A → βk } are encoded byvalues/3 declaration asvalues(’A’,[β1 , . . . , βk ],[θ1 , . . . , θk ])where βi is a Prolog list of terminals and nonterminals.
We wrote a PCFG program like Figure 1 for ATR corpus (Uratani et al., 1994) using an associated CFG4 .
The corpus contains labeled parse trees for 10,995
Japanese sentences whose average length is about 10.
The associated hand-crafted CFG comprises 860 CFG
rules (172 non-terminals and 441 terminals) and yields
958 parses/sentence on average.
We applied four learning algorithms, i.e. VT, EM,
MAP and VB (Sato et al., 2009) available in PRISM
to the PCFG program for ATR corpus5 and compared
their parsing performance. We conducted eight-foldcross validation for each algorithm to evaluate thequality of learned parameters in terms of three perfor4
In the experiment, to speed up parsing, we partially evaluated the PCFG program with individual CFG
rules and obtained a specialized set of clauses representing
PCFG rules. We ran them as a PRISM program.
5
In PRISM, EM is a special case of MAP inference. We
used random but almost uniform initialization of parameters and set uniformly pseudo counts δi,v to 1.0−9 for EM
and 1.0 for MAP and VT, respectively. Similarly we uniformly set hyper parameters αi,v to 1.0 for VB. The number of candidates for re-ranking in VB (Sato et al., 2009)
was set to 5. In all cases, we set the number of random
restarts to 50 and used the best parameter set that gave thelargest value of objective functions, i.e. LEM for EM, LMAP
for MAP and LVT for VT. For the case of VB that learns
pseudo counts, we chose the best set of pseudo counts giving the highest free energy (Sato et al., 2009).

Viterbi training in PRISM

mance measures, i.e. LT(labeled tree), BT(bracketedtree) and 0-CB(zero crossing brackets)6 . The entire
corpus is partitioned into eight sections. In each fold,
one section is used as a test corpus and sentences in
the remaining sections are used as training data. For
each of EM, MAP, VT and VB, parameters (or pseudocounts) are learned by unsupervised learning from thetraining data. A parse tree is predicted, i.e. Viterbi
explanation is computed for each sentence in the test
corpus using learned parameters or using the approximate a posterior distribution learned by VB. The predicted trees are compared to answers, i.e. the labeledtrees in the test corpus to compute LT, BT and 0-CB
respectively. The performance ﬁgures are calculated as
averages over eight folds. The results are summarizedin Table 1.

Table 1. Parsing performance by PCFG

PCFG
Measure
LT
BT
0-CB

VT(%)
74.69
77.87
83.78

Learning method
EM(%) MAP(%)
70.02
70.31
73.10
73.45
84.44
84.89

values(lc(’S’,’S’),[rule(’S’,[’S’,’S’])]).
values(lc(’S’,a),[rule(’S’,[a])]).
values(lc(’S’,b),[rule(’S’,[b])]).
values(first(’S’),[a,b]).
values(att(’S’),[att,pro]).
plcg(L):- g_call([’S’],L,[]).
g_call([],L,L).
g_call([G|R],[Wd|L],L2):( G = Wd -> L1 = L% shift operation; msw(first(G),Wd),lc_call(G,Wd,L,L1) ),g_call(R,L1,L2).
lc_call(G,B,L,L2):% B-tree is completed
msw(lc(G,B),rule(A,[B|RHS2])),( G = A -> true ; values(lc(G,A),_) ),g_call(RHS2,L,L1),% complete A-tree( G = A -> att_or_pro(A,Op),( Op = att -> L2 = L1 ; lc_call(G,A,L1,L2) ); lc_call(G,A,L1,L2) ).
att_or_pro(A,Op):( values(lc(A,A),_) -> msw(att(A),Op) ; Op=att ).

VB(%)
72.13
75.46
87.08

Figure 2. A PLCG program

3.2. VT for PLCG
The table shows that VT clearly outperforms the otherthree in terms of LT and BT by a considerable margin
but it is the worst as far as 0-CB is concerned. This isunderstandable if we recall that VT looks for the bestparameters for the best parse tree and hence widens
the gap between the probability of the best tree andthose not, which is thought to negatively aﬀect lessstringent criteria such as 0-CB.
Another thing to note is that the objective functions
for EM, MAP and VB are similar in the sense thatthey all sum out hidden variables whereas the objective function for VT retains them. This fact together
with Figure 1 seems to suggest that parsing performance is more aﬀected by the diﬀerence among objective functions than the diﬀerence among learning
methods.
6

A parse tree is represented as a set of terms of the form
(NP, 1, 3) which means a nonterminal NP spans from the 1stword to the 3rd word in the given sentence. NP is called alabel. If two parse trees have the same representation, they
are identical. LT is the ratio of correctly predicted trees inthe test corpus, i.e. those that exactly match the labeledtrees in the test corpus. BT is the same as LT but only
cares about brackets and ignores labels. 0-CB is the ratio
of predicted trees with non-conﬂicting bracketing with thetest corpus.

PCFGs assume top-down parsing. Contrastingly,
there is a class of probabilistic grammars basedon bottom-up parsing for CFGs called PLCGs(probabilistic left-corner grammars)(Manning, 1997;
Roark & Johnson, 1999; Van Uytsel et al., 2001). Although they use the same set of CFG rules as PCFGs
but attach probabilities not to expansion of nonterminals but to three elementary operations in bottom-up
parsing, i.e. shift, attach and project. As a result theydeﬁne a diﬀerent class of distributions from PCFGs.
Programs for PLCGs look very diﬀerent from thosefor PCFGs. Figure 2 is a PLCG program which is adual version of the PCFG program in Figure 1 withthe same underlying CFG {S→S S, S→a, S→b}. It
generates sentences using the ﬁrst set of ’S’ and theleft-corner relation for this CFG7 .
The program works as follows. Suppose nonterminals
G and B are in the left-corner relation and G is waiting for a B-tree, i.e. a subtree with the root node labeled B, to be completed. When a B-tree is completed,the program probabilistically chooses a CFG rule ofthe form A → Bβ to further grow the B-tree using thisrule. Upon the completion of the A-tree and if G=A, theattach operation or the projection is probabilistically7

We assume the reader is familiar with parsing theory.

Viterbi training in PRISM

chosen. By replacing values/3 declarations appropriately, this program is applicable to any PLCG.
We have developed a PLCG program similarly to the
PCFG program for ATR corpus and applied VT, EM,
MAP and VB to measure their parsing performance interms of LT, BT and 0-CB by eight-fold cross validation. We obtained Table 2. As expected VT outperformed EM, MAP and VB in terms of LT and BT but
it was the second best in terms of 0-CB. Also we seethat the PCLG achieved better parsing performance
than the PCFG with VT,EM and MAP but no so with
VB.
Table 2. Parsing performance by PLCG

PLCG
Measure
LT
BT
0-CB

VT(%)
76.26
78.86
87.45

Learning method
EM(%) MAP(%)
71.81
71.17
75.17
74.28
95.92
86.03

VB(%)
71.15
74.28
86.04

4. Removing the exclusivenesscondition
PRISM assumes the exclusiveness condition on programs to simplify probability computation. It saysthat the clause bodies must be exclusive when successfully proved (Sato & Kameya, 2001). Althoughmost of generative probabilistic models such as BNs(Bayesian networks), HMMs and PCFGs are naturally
described as PRISM programs satisfying the condition,
removing it certainly gives us more freedom of probabilistic modeling. Theoretically it is possible to remove
it by introducing BDDs (binary decision diagrams) as
ProbLog (De Raedt et al., 2007; Kimmig et al., 2008)
and PITA (Riguzzi & Terrance Swift, 2011) do. If,
however, we are only interested in obtaining Viterbi
explanations determined by parameters learned fromdata as we are in many cases, we may forget about
BDDs and the exclusiveness condition because VT isapplicable to any programs regardless of the exclusiveness condition and learning parameters by VT andcomputing Viterbi explanations using the learned parameters is enough. Moreover, as we have seen in theprevious section, VT can learn parameters that exhibit
excellent performance in prediction tasks.
However, there is one caveat: While VT allows us to
use probabilistic inclusive-or in the clause bodies, parameters learned by VT might cause a heavily biased
selection of disjuncts. For example look at Figure 3.
This program represents a probabilistic version ofinclusive-or “b ∨ c” as a goal “a”. Note that eachvalues(cl(b),[yes,no]).
values(cl(c),[yes,no]).
a:- (b ; c).
b:- msw(cl(b),yes).
c:- msw(cl(c),yes).

Figure 3. Probabilistic inclusive orof msw(cl(b),yes) and msw(cl(c),yes) occurs only
once and hence their parameters are independently adjustable. Consequently learning parameters by VTfrom goals like [a,a,. . .] would inevitably result in
PDB (msw(cl(b), yes)) = 1 or PDB (msw(cl(b), yes)) =1 and never give, say, PDB (msw(cl(b), yes)) =PDB (msw(cl(b), yes)) = 0.5.
In general VT chooses best parameters for the Viterbi
explanations. It therefore prefers to assign probability
1 to msws that occur only once in a program and hence
often gives extreme probabilities to disjuncts. If one
considers such a behavior of VT undesirable, one way
to remedy it is to set large values to pseudo counts δi,v
in (5).

5. Discussion
In this paper we discussed VT for PRISM that runs on
explanation graphs, a single data structure in PRISM.
VT thus implemented requires time for all solution
search (by tabling) and also space to store discovered
explanation graphs. It is possible, however, to implement VT without explanation graphs, and to realize
much more memory eﬃcient VT by repeating search
for a Viterbi explanation in each cycle of VT. We
note this approach particularly ﬁts well with modedirected tabling (Zhou et al., 2010). In mode-directed
tabling, we can search for partial Viterbi explanations
for subgoals eﬃciently without constructing explanation graphs and put them together to form a larger
Viterbi explanation for the goal. Currently howevermode-directed tabling is not available in PRISM. We
are planing to incorporate it in PRISM in the near
future.

6. Conclusion
We enhanced PRISM’s probabilistic modeling by introducing VT (Viterbi training) to PRISM. Although
it has already been used in various models undervarious names (Brown et al., 1993; Juang & Rabiner,
1990;
Strom et al.,
1999;
Joshi et al.,2006;
Spitkovsky et al., 2010; Lomsadze et al., 2005),

Viterbi training in PRISM

we made the following contributions to VT. One isa generalization by deriving a generic VT algorithm
for PRISM, thereby making it applicable to a very
wide class of discrete models described by PRISM
programs that range from BNs to probabilistic grammars. The other is an empirical evaluation of VT thatcomplements the scarcity of literature on applicationsof VT to pure PCFGs and PLCGs. We conducted
two learning experiments with them using VT preliminarily implemented in PRISM and conﬁrmed VT’s
excellent parsing performance compared to EM, MAP
and VB.

References
Brown, P.F., Pietra, V.J.D., Pietra, S.A.D., and Mercer, R.L. The mathematics of statistical machinetranslation: Parameter estimation. Computational
Linguistics, 19:263–311, 1993.
Cohen, S.B. and Smith, N.A. Viterbi Training for
PCFGs: Hardness Results and Competitiveness ofUniform Initialization. In Proceedings of the 48th
Annual Meeting of the Association for Computational Linguistics (ACL’10), pp. 1502–1511, 2010.
De Raedt, L., Kimmig, A., and Toivonen, H. ProbLog:
A probabilistic Prolog and its application in link
discovery. In Proceedings of the 20th International Joint Conference on Artiﬁcial Intelligence(IJCAI’07), pp. 2468–2473, 2007.
Joshi, D., Li, J., and Wang, J.Z. A computationally efﬁcient approach to the estimation of two- and threedimensional hidden markov models. IEEE Transactions on Image Processing, 15(7):1871–1886, 2006.
Juang, B.H. and Rabiner, L.R. The segmental Kmeans algorithm for estimating parameters of hidden Markov models. IEEE Transactions on Signal
Processing, 38:1639 – 1641, 1990.
Kimmig, A., Costa, V., Rocha, R., Demoen, B, and
De Raedt, L. On the eﬃcient execution of problog
programs. In Proceedings of the 24th International
Conference on Logic Programming (ICLP’08), pp.
175–189, 2008.
Lember, J. and Koloydenko, A. Adjusted viterbi training. Probability in the Engineering and Informational Sciences, 21(3):451–475, 2007.
Lomsadze, A., Ter-Hovhannisyan, V., Chernoﬀ, Y.O.,
and Borodovsky, M. Gene identiﬁcation in novel eukaryotic genomes by self-training algorithm. Nucleic
Acids Research, 33:6494–6506, 2005.

Manning, C.D. Probabilistic parsing using left corner
language models. In Proceedings of the 5th International Conference on Parsing Technologies (IWPT97), pp. 147–158. MIT Press, 1997.
Riguzzi, F. and Terrance Swift, T. The PITA system:
Tabling and answer subsumption for reasoning under uncertainty. Theory and Practice of Logic Programming (TPLP), 11(4-5):433–449, 2011.
Roark, B. and Johnson, M. Eﬃcient probabilistic topdown and left-corner parsing. In Proceedings of the37th Annual Meeting of the Association for Computational Linguistics, pp. 421–428, 1999.
Sato, T. and Kameya, Y. Parameter learning of logic
programs for symbolic-statistical modeling. Journalof Artiﬁcial Intelligence Research, 15:391–454, 2001.
Sato, T. and Kameya, Y. New Advances in LogidBased Probabilistic Modeling by PRISM. In De
Raedt, L., Frasconi, P., Kersting, K., and Muggleton, S. (eds.), Probabilistic Inductive Logic Programming, pp. 118–155. LNAI 4911, Springer, 2008.
Sato, T., Kameya, Y., and Kurihara, K. Variational
Bayes via Propositionalized Probability Computation in PRISM. Annals of Mathematics and Artiﬁcial Intelligence, 54:135–158, 2009.
Spitkovsky, V.I., Alshawi, H., Jurafsky, D., and Manning, C.D. Viterbi training improves unsupervised
dependency parsing. In Proceedings of the Fourteenth Conference on Computational Natural Language Learning, pp. 9–17, July 2010.
Strom, N., Hetherington, L., Hazen, T.J., Sandness,
E., and Glass, J. Acoustic modeling improvements
in a segment-based speech recognizer. In Proceedingsof IEEE ASRU Workshop, 1999.
Uratani, N., Takezawa, T., Matsuo, H., and Morita,
C. ATR integrated speech and language database.
Technical Report TR-IT-0056, ATR Interpreting
Telecommunications Research Laboratories, 1994.
In Japanese.
Van Uytsel, D.H., Van Compernolle, D., andWambacq, P. Maximum-likelihood training of the
PLCG-based language model. In Proceedings ofthe IEEE Automatic Speech Recognition and Understanding Workshop 2001 (ASRU’01), 2001.
Zhou, N.-F., Kameya, Y., and Sato, T. Mode-directed
tabling for dynamic programming, machine learning, and constraint solving. In Proceedings of the22th International Conference on Tools with Artiﬁcial Intelligence (ICTAI-2010), 2010.