ISSN 0918-2802
Technical ReportL

Fast EM Learning of a Family of PCFGs
Sato, Taisuke (TIT, sato@mi.cs.titech.ac.jp)
Kameya, Yoshitaka (NS solutions)Abe, Shigeru (TIT, abe@mi.cs.titech.ac.jp)

Shirai, Kiyoaki (JAIST, kshirai@jaist.ac.jp)

TR01-0006 May

Department of Computer Science
Tokyo Institute of TechnologyO^ okayama 2-12-1 Meguro Tokyo 152-8552, Japan

http://www.cs.titech.ac.jp/

c The author(s) of this report reserves all the rights.

Abstract

The purpose of this report is to optimize the Inside-Outside algorithm
and realize fast EM learning of various extensions of PCFGs. The
point of our optimization is the introduction of a new data structure
called support graphs hierarchically
representing a set of parse trees
and a new EM learning algorithm
called the graphical EM algorithm
that runs on them. Learning experiments with PCFGs using Japanese
corpora of moderate size with contrasting characters indicate that interms of updating time per iteration, the graphical EM algorithm
can learn parameters of PCFGs orders of magnitude faster than the
Inside-Outside algorithm. We also
experimentally show that the graphical EM algorithm requires at mostabout twice as much time as a pure
PCFG to learn parameters of extended PCFGs (a Pseudo PCSG andand a lexicalized PCFG).
1 Introduction

PCFGs (probabilistic context free grammars)
have been recognized as a basic mechanism
to express a probability distribution over syntactic objects described by CFGs (Manningand Schutze, 1999). Despite their popularity however, they have two major problems.
One is their poor modeling capability as astatistical language model and the other istheir slow speed of unsupervised parameter
learning (Pereira and Schabes, 1992; Lari andYoung, 1990). As solutions to the rst problem, several elaborations of PCFGs were proposed including Pseudo PCSGs (probabilistic
context sensitive grammars) (Charniak andCarroll, 1994) and lexicalizations (Charniak,
1997; Collins, 1997; Carroll and Rooth, 1998;
Beil et al., 1999; Charniak, 2000).
The second problem, the computational
cost of unsupervised parameter learning, on

the other hand, has been paid relatively little
attention since the proposal of the I-O (insideoutside) algorithm by Baker (Baker, 1979) as
the EM algorithm for PCFGs.1 Time complexity in one iteration of the I-O algorithm
is known to be O(N 3 L3) where N is the number of symbols in a grammar and L the lengthof an input sentence (Lari and Young, 1990).
And it is not unusual for the I-O algorithm
to take days to learn parameters from a large
corpus.2
The purpose of this paper is to optimize
the I-O algorithm and realize fast EM learning for various extensions of PCFGs. The optimization is done by introducing a new data
structure called support graph s representing
a set of parse trees and a new EM learningalgorithm called the graphical EM algorithm(Kameya and Sato, 2000) that runs on them.
They are explained in Section 3. Learning
experiments with PCFGs in Section 4 using
Japanese corpora of moderate size with contrasting characters indicate that the graphicalEM algorithm can learn parameters of PCFGs
orders of magnitude faster than the I-O algorithm, thus solving the second problem to alarge extent.
We also experimentally show by learning
experiments with the graphical EM algorithm
in Section 5 that although extended PCFGs
mentioned above require learning time longer
than pure PCFGs, they do so only marginally(at most twice), which makes it computationally feasible to adopt even more linguisticallysophisticated models in natural language processing, thereby indirectly contributing to thesolution of the rst problem.
1 The EM algorithm is an iterative algorithm for
maximum likelihood estimation. It nds parameters
values that maximize the likelihood of observations
by repeating the E(-expectation) step and the M(aximization)
step alternately (Dempster et al., 1977).
2 It is reported in (Beil et al., 1999) that to traina PCFG with 5,508 rules from a corpus of 450,526
German subordinate clauses whose average ambiguity
is 9,202 trees/clause, it takes 2.5 hours for 4 CPUs tocomplete one iteration of the I-O algorithm.

2 Previous EM algorithms for
PCFGs

In this section, we review previous EM algorithms for PCFGs. The rst EM algorithm
for PCFGs was the I-O algorithm proposedby Baker (Baker, 1979). The grammar it
uses must be in Chomsky normal form andcontains all possible rules expressed by numbers like i j; k (1 i; j; k N , for N
non-terminals). Let w1; : : : ; wn be an input
sentence of length n and S (= 1) the starting symbol.3 In each iteration, the algorithm
rst computes in a bottom up manner inside probabilitiese(s; t; i), i.e. the probability
3 w ; : : : ; w ) while trying every possible
P (istcombination of rules. It next computes outside probabilitiesf (s; t; i), i.e. the probability P (S 3 w1 ; : : : ; ws01 i wt+1; : : : ; wn ) in a
top-down manner using previously computed
inside probabilities. After computing insideand outside probabilities, parameters are updated by using them. Update iterates until
the likelihood of the input sentence saturates.
When the grammar does not allow arbitrary rules, it is apparent that only combinations of rules appearing in parse trees are relevant to the computation of inside and outside
probabilities. Nonetheless the I-O algorithm
repeats in every iteration all possible combinations of the rules that derive the input sentence. In other words, the I-O algorithm lacks
parsing.
By contrast the EM algorithm proposedby Fujisaki et al. used probability P (Dm)of the m-th derivation Dm of an input sentence (Fujisaki et al., 1989).4 So irrelevant rules are excluded by parsing. Unfortunately, while inside probabilities are recursively computed like the I-O algorithm, outside probabilities
are naively computed as asum Pm P (Dm )#(i j; k Dm) in each iteration, where #(i j; k Dm) is the number of occurrences of the rule i j; k in them-th derivation. Since m can be exponential
in the length of an input sentence, it is di!





)

)

!

!

2

2

!

3 We assume only one input sentence for simplicity.
4 P (Dm ) is computed as the products of probabil-ities associated with production rules involved in thederivation.

cult to perform large scale learning by theirapproach.
Later Stolcke used an Earley chart generated by an Earley parser to compute insideand outside probabilities (Stolcke, 1995). The
chart is comprised of items augmented with
two types of probabilities and inside and outside probabilities are computed from them.
Accordingly, unlike (Fujisaki et al., 1989), his
approach incorporates both parsing and thesharing of processes of sentence derivations.
The problem is that the Earley chart may
possibly contain items not contributing to thenal outcome, a parse tree, but probabilities
are still computed for them as well.
To solve these problems, we completely separate EM learning from parsing. We rst introduce a new data structure, support graph sfor EM learning. A support graph (explainedin next section) is constructed from a WFST
(well-formed substring table) such as a triangular table used by a CYK parser and an
Earley chart used by an Earley parser. It isan ordered set of applied rules compactly representing all parse trees by structure sharing.
We also introduce a new EM algorithm called
the graphical EM algorithm that runs on thegraph to compute inside and outside probabilities.
Computationally, construction of a support
graph is an extra burden, but it pays o justlike compilation of programs pays o as time
per iteration in the EM algorithm can improve by orders of magnitude as we will see
in Section 4.
3 Support graphs and thegraphical EM algorithm
Suppose we are given a PCFG G 5 and T sampled sentences w(1); : : : ; w(T ) whose distribu-

tion is supposedly modeled by . In our
approach to EM learning, for each sentencew(`) (1 ` T ), we rst parse w(`), construct a WFST and extract from the WFSTa support graph 1` = 1; : : : ; j1 j for w(`).
We then run the graphical EM algorithm on
G





h

`

i

5 We assume that there is neither the empty production rule nor non-terminal A such that A )+ A in

the grammar.

15

S(0,5)

S(0,3)@
NP(0,1)VP(1,3)

S(0,5)@
NP(0,1)VP(1,5)

start

VP(1,3)@V(1,2)NP(2,3)

VP(1,5)@V(1,2)NP(2,5)
VP(1,5)@
VP(1,3)PP(3,5)

NP(2,3)@stars(2,3)

NP(2,5)@NP(2,3)PP(3,5)

2

3NP(0,1)@astronomers(0,1)
V(1,2)@
saw(1,2)

4

P(3,4)@
with(3,4)PP(3,5)@P(3,4)NP(4,5)

end

0

VP

V NP

start

VP

VP PP VP(1,3) PP(3,5)

PP(3,5)PP

P NP

NP(4,5)@ears(4,5)

V(1,2) NP(2,5)

VP(1,5)
1

P(3,4) NP(4,5)

start

end

3
VP

V NP

V(1,2) NP(2,3)

start

end

4
NP(2,5)VP

NP

NP PP NP(2,3) PP(3,5)

PP

P NP

NP

ears

start

end

PP(3,5)NP

P(3,4) NP(4,5)

start
PP
NP

V

NP

P

S
NP

end

NP(4,5)
start

VP

end

P(3,4)

P

with

NP

stars

V(1,2)
start

V

saw

NP(0,1)NP

astronomers saw stars with ears

start

end

NP(2,3)
VP
NP

V

PP
NP

P

end

2

VP(1,3)SNP VP NP(0,1) VP(1,5)

S

start
NP

end

end

astronomers saw stars with ears
astronomers

start

end

Figure 1: Parsing \astronomers saw stars with ears" and its support graph1` 1 ` T to statistically learn parameters associated with .
In the following, we use R for the rule set of, Vn for its non-terminal set and (A  )for the parameter associated with a rule A
R. n` stands for w (`) , i.e. the length of(`)
w and w(`)[i; j] denotes a substring of w(`)
starting at the i + 1-th word and ending at
the j -th word.
A support graph 1` for w(`) is a linearlyordered set 1 ; : : : ; M of disconnected subgraphs k (1 k M ) which can be read ofrom the WFST for w(`). Each k is labeledlike A(i; j) and comprised of linear graphs of the form
start-(A B1 BM )B1 (i; h1 )- -BM (hM ; j )-end
which records that A is expanded by ruleA
B1
BM to span w(`) [i; j ] in some(`)
parse of w . Here start is a fork node andend is a join node and Bk (hk01 ; hk ) (1 k
M; h0 = i; hM = j ) is the label of the corresponding subgraph which is recursively conf

j





g

G

G

!

!

2

j

h

j

i



!



111

111

!

111





structed. De ne () and ~`( ) by( ) def= A B1 BM ;B1 (i; h1 ); : : : ; BM (hM ; j )~`(k ) def=( )  is a linear graph in kSuppose for example A is expanded by A
BC and A
D respectively in some parse of(`)
w and happens to span the same substringw(`)[i; j]. Then the disconnected subgraph labeled A(i; j ) contains two linear graphs,
start-(ABC )-B (i; k)-C (k; j )-end andstart-(A
D)-D (i; j )-end, and we have~( )) = A BC; B(i; k); C (k; j) ; A
D; D (i; j ) .
The total ordering 1 < < M over the
disconnected subgraphs is introduced as follows. First de ne a partial ordering overthe k 's as A(i; j ) B(i0 ; j 0 ) i B is expanded
in a partial derivation from A of w(`)[i; j ]and spans a substring w(`)[i0; j 0 ] of w(`)[i; j ](i i0 j 0 j ) in some successful parse ofw(`). A support graph 1` for w(`) is then obN

N

f

1

!

111

g

fN

j

g

!

!

!

!

ff

!

g f

g

111











!

1: procedure Extract-CYK () begin
2: for ` := 1 to T do begin
3:
Initialize all ~` (1) to ; and4:
all Visited [1] to NO;
5:
ClearStack (U );6:Visit-CYK (`; S; 0; n` );7:
for k := 1 to jU j do k := PopStack (U );8:1` := h1; 2; : : : ; jU j i
9: end10: end.

the procedure Extract-CYK () in Fig. 2.6 It is(we only show labels)
1 =< S(0,5), VP(1,5), PP(3,5), VP(1,3),
NP(2,5), PP(3,5), NP(4,5), P(3,4),NP(2,3), V(1,2), NP(0,1) > :Note that in the support graph, two disconnected graphs VP(1,5) and NP(2,5) havePP(3,5) as a child node and precede it in 1.

After constructing support graphs 1`
1 ` T , we run the graphical EM algorithm on them. It is driven by one main
routine gEM () (Fig. 3) for updating parameters7 and two subroutines, Get-Inside-Probs ()(Fig. 4) for computing inside probabilities
and Get-Expectations () (Fig. 5) for computing outside probabilities and the expected
number of occurrences [A  ] of a production rule A  R given the sentence.
Let A(i; j) be the label of a disconnected subgraph k in 1`. In each
iteration of gEM (), Get-Inside-Probs ()is called and recursively computes in abottom-up
manner the inside probability
3 w(`) [i; j ]) and stores it in arP (Aray [`; A(i; j )].8 Get-Inside-Probs () alsouses array [`; A(i; j); E] to store probability
P
Figure 2: A routine for support graph extrac- (E) where E = e0; : : : ; eM ~(k ). P (E )tion from a triangular table generated by a is computed as a product P (e1 ) P (eM )where P (e) = (A  ) if node e is a ruleCYK parserAR, or P (e) =[`; B(i0 ; j 0 )]00
if e is a Plabel B (i ; j ).
We see
[
`;
A
(
i;
j
)]
=
P
(
E
).
tained by topologically sorting the k 's so thatE 2 ~( )k < k0 implies kk0 . As a result, the laAfter computing all [`; A(i; j)]s,
bel of 1 always takes the form S (0; n` ) where Get-Expectations () is called to compute
S is the starting symbol of the grammar.
each [`; A(i; j)], the outside probability
6 Here U in
In what follows, for descriptive conve() is a stack holding distheir labels)
nience, we sometimes treat 1` = 1; : : : ; M connected subgraphs (or equivalently( ) inconstitutingasupportgraph
1.
T
as an ordered labels of the k 's together with is an element stored at (i; j) in the triangular ta-()a function ~`( ) de ned over them.
ble T ( ) (1; 1) for w( ) . w( ) is the j -th word of w( ) .
Fig. 1 illustrates parses of sentence \as- Since there exist only O(N 3 L3) elements possibly lltronomers saw stars with ears" (taken from ing T ( )(1; 1) where L = jw( )j and V = jVnj, andall di erent, time complexity of(Manning and Schutze, 1999)) by a CYK lled elements() areisO (N 3 L3 ). Another support graphparser and the resulting triangular table, i.e. extraction routine for an Earley parser is described in
et al., 2001).
a WFST for CYK parsing. \@" in the table is (Kameya
7 P (1 j ) infor a distribution undera symbol separating a parent label from child the current parameter() stands
values.
8 For intuitiveness and readability, we use A(i; j ) as
labels. The right graph in Fig. 1 is a support
graph extracted from the triangular table by a substitute for  .
1: procedure Visit-CYK (`; A; i; j ) begin
2: Put  = A(i; j ); Visited [ ] := YES;
3: if j = i + 1 and A(i; j )@w(j`) 2 Ti;j(`)
4: then Add a set fA ! wj(`) g to ~` ( )5: else6:
foreach(`)
7:
A(i; j )@B (i; k)C (k; j ) 2 Ti;j8:
do begin
9:
Add to ~` ( ) a set
10:
fA ! BC; B (i; k); C (k; j )g;11:
if Visited [B (i; k)] = NO
12:then Visit-CYK (`; B; i; k);13:
if Visited [C (k; j )] = NO
14:then Visit-CYK (`; C; k; j )15:
end;
16: PushStack (; U )17: end.

f





j

g

2

)

P

R

f

g 2

111

2

P

P

k



P

Q

Extract-CYK

h

i

`

1

`

`

`

j

`

gEM

k

Visit-CYK``

Extract-CYK`i;j

1: procedure gEM () begin
2: Initialize all parameters (A !  );3: such that P (w(`) j) > 0 for all ` = 1; : : : ; T ;4: Get-Inside-Probs();
5: (0) := PT`=1 log P [`; S (0; n` )];6: repeat
7:
Get-Expectations ();8:
foreach (A !  ) 2 R do
P [A ! 0 ];9:
(A !  ) := [A !  ]=10:m += 1;
11:
Get-Inside-Probs ();PT log P [`; S(0; n`)]12:
(m) :=`=1
13: until (m) 0 (m01) is suciently small
14: end.

focus on the actual behavior of the graphicalEM algorithm w.r.t. real corpora.
1: procedure Get-Inside-Probs () begin
2: for ` := 1 to T do begin3:
Put 1` = h1; 2; : : : ; j1 j i;
4:
for k := j1` j downto 1 do begin
5:
foreach E 2 ~(k ) do begin
6:R[`; k ; E ] := 1;
7:foreach e 2 E do
8:
if e = (A !  )9:then R[`; k ; E ] 3= (A !  )10:else R[`; k ; E ] 3= P [`; e];
11:
end;
P
12:
P [`; k ] := E 2 ~( ) R[`; k ; E ]13:
end /* for k */14: end /* for ` */15: end.
`0k

Figure 3: Main routine gEM( 3 w(`)[0; i] A w(`)[j; n` ]) in a top-downmanner from 1 = S(0,n` ) where n` = w(`)(the length of w(`)), while incrementing the
expected counts [A  ] of A  in aparse of w(`).
gEM () iterates to update parameters until an increase in the log likelihood ofw(1) ; : : : ; w(T ) is less than a threshold, say
1006 .
It is proved in (Kameya, 2000; Kameya etal., 2001) that the graphical EM algorithm
computes the same values (inside and outside
probabilities, update values of parameters) as
the I-O algorithm, hence the di erence only
lies in computational eciency. Since timecomplexity of parsing and that of one iteration for updating all parameters in one iteration by the graphical EM algorithm are bothO(N 3 L3 ) where N is the number of terminal symbols in a grammar and L the lengthof an input sentence,9 we can say that thegraphical EM algorithm is as ecient as the
I-O algorithm. Likewise we can analyze timecomplexity by the graphical EM algorithm ofvarious extensions of PCFGs. For example,
parsing and parameter updating in one iteration for Pseudo PCSGs (Charniak and Carroll, 1994) take O(N 4 L3 ). In what follows, we
P S )

j

j

9 It is easy to see that time complexity of the graphical EM algorithm in one iteration is proportional
to the size of a support graph which is O(N 3L3 )(Kameya, 2000; Kameya et al., 2001).

Figure 4: Subroutine Get-Inside-Probs
4 Learning experiments with pure
PCFGs using two corpora

In this section, we experimentally compare
the graphical EM algorithm with the I-O algorithm in terms of time per iteration (= time
for updating parameters) by letting themlearn PCFG parameters from a corpus. Support graphs were generated by using a Tomita(Generalized LR) parser.10 All measurements
were made on a 296MHz Sun UltraSPARC-IIwith Solaris 2.6.
We used two corpora. One was a POS(part of speech)-tagged corpus converted from
ATR corpus and the other is EDR corpus.
ATR corpus is a Japanese-English corpus (weused only the Japanese part) developed by
ATR (Uratani et al., 1994). It contains
10,995 conversational sentences, whose minimum length, average length and maximum
length are respectively 2, 9.97 and 49. As askeleton of PCFG, we employed a context free
10 More speci cally, we combined MSLR (Morphological and Syntactic LR) parser with our routine forthe graphical EM algorithm. MSLR parser is a Tomita
parser, developed by Tanaka-Tokunaga Laboratory inTokyo Institute of Technology (Tanaka et al., 1997).
Although MSLR parser provides several useful functions (e.g. morphological analysis), we used only thebasic one (i.e. parsing of the tagged sentence).

1: procedure Get-Expectations () begin
2: foreach (A !  ) 2 R do [A !  ] := 0;
3: for ` := 1 to T do begin4:
Put 1` = h1 ; 2; : : : ; j1 ji;
5:Q[`; 1] := 1;
6:
for k := 2 to j1` j do Q[`; k ] := 0;7:
for k := 1 to j1` j do
8:foreach E 2 ~(k ) do
9:foreach e 2 E do
10:
if e = (A !  ) then [A !  ] += Q[`; k ] 1 R[`; k ; E ]=P [`; S (0; n` )]11:else if P [`; e] > 0 then Q[`; e] += Q[`; k ] 1 R[`; k ; E ]=P [`; e]
12: end /* for ` */13: end.
`Figure 5: Subroutine Get-Expectations
grammar Gatr comprising 860 rules (172 nonterminals and 441 terminals) manually developed for ATR corpus (Tanaka et al., 1997)
which generates 958 parses/sentence.
Because the I-O algorithm only accepts
CFGs in Chomsky normal form, we converted
Gatr into Chomsky normal form G3atr . G3atr
contains 2,105 rules (196 non-terminals and
441 terminals). We then divided the corpus
into subgroups of similar length like (L =1; 2); (L = 3; 4); : : : ; (L = 25; 26), each containing randomly chosen 100 sentences. Afterthese preparations, we compare the graphical EM algorithm applied to Gatr and G3atr
against the I-O algorithm applied to G3atr interms of updating time per iteration.11 The
results are shown in Fig. 6.
In the left graph, the I-O algorithm draws
a cubic curve labeled \I-O".12 The curves
drawn by the graphical EM algorithm coincide with the x axis and are not plotted. The
middle graph magni es the left graph. The
curve labeled \gEM (original)" is drawn by
the graphical EM algorithm applied to theoriginal grammar Gatr whereas the one labeled \gEM (Chomsky CF)" used G3atr. Seeing \gEM (original)" at length 10, the average sentence length, we know that the graphical EM algorithm runs about 850 times fasterthan the I-O algorithm. The right graphshows (almost) linear dependency of updating time of the graphical EM algorithm on
the sentence length.
This rather striking di erence needs explanation, but the reason looks simple. Whenthe I-O algorithm is applied to a speci cgrammar such as G3atr , it tries all possiblecombinations of CFG rules in every iteration.
In other words, it parses a sentence anew ineach iteration. The graphical EM algorithm
on the other hand uses support graphs representing already parsed trees.
It is conceivable however that such a big
di erence in updating time is ascribed to thefact that ATR corpus only contains short sentences and Gatr is not very ambiguous so thatthe resulting WFST is sparse. If the WFST
is not sparse, and hence the support graph islarger, we might not be able to expect such a
big di erence.
We therefore conducted the same experiment with another corpus, EDR Japanese
corpus which contains much longer sentencesusing a highly ambiguous grammar. EDR
Japanese corpus (Japan Electronic Dictionary
Research Institute, 1995) contains 220,000
Japanese news article sentences. It is however under the process of re-annotation, andonly part of it (randomly sampled 9,900 sen11 The stopping threshold was 1006 .
tences) is available as a labeled corpus at the
12 An x-axis is the length L of an input sentence anda y-axis is time taken by the EM algorithm to update moment. Compared with ATR corpus, sentences are much longer (the average length
all parameters in the grammar in one iteration.

(sec)

(sec)

(sec)

60
I-O
50

0.7

0.04

0.6

0.035
0.03

I-O
gEM (original)gEM (Chomsky NF)

0.5

40

0.4

gEM (original)gEM (Chomsky NF)

0.025
0.02

30
0.3
20

0.015

0.2

10

0.01

0.1

0.005

5

10

15

20

25

L

L

L
0

0

5

10

15

20

0

25

5

10 15 20 25

Figure 6: Time per iteration : I-O vs. gEM (ATR)
(sec)

5000

(sec)

(sec)
3

10

6000
I-O

8

I-O
gEM (original)

2.5

gEM (original)

2

4000

6
1.5

3000

4
1

2000

2

1000
0

L
5 10 15 20 25 30 35 40

0

0.5

L

0

5 10 15 20 25 30 35 40

L
5 10 15 20 25 30 35 40

Figure 7: Time per iteration : I-O vs. gEM (EDR)of 9,900 sentences is 20, the minimum length
5, the maximum length 63) and a CFG grammar Gedr (2,687 rules, converted to Chomsky
normal form grammar G3edr containing 12,798
rules) developed for it is very ambiguous, having 3:0 108 parses/sentence at length 20 and
6:7 1019 at length 38. The graphs in Fig. 7
show the results of the same experiment with
EDR corpus as with ATR corpus, i.e. thegraphical EM algorithm applied Gedr vs. theI-O algorithm applied to G3edr.
We found that at average sentence length
20, the former runs 1,300 times faster the latter per iteration. Thus the speed ratio evenwidens compared to the case of ATR corpus.
This can be explained by the mixed e ectsof time complexity O(L3) for the I-O algorithm and a slow increase in the size of support graphs for the graphical EM algorithm.
2

2

One might argue that the comparison wemade is not fair as what we are comparing istime per iteration of the EM algorithms, butproper comparison must be based on the total
learning time which is calculated as(A : time for constructing support graphs)+ (B : time per iteration)(C : the number of iterations)for the graphical EM algorithm whereas it ismerely B C for the I-O algorithm. To answer this question, we estimated total learning time for both of the EM algorithms using
the entire ATR corpus as input.
B for the I-O algorithm applied to G3atr
was 1,215 seconds (average of 20 iterations)whereas for the graphical EM algorithm applied to Gatr, A was 279 seconds and B was
22

0.661 second respectively.13 Assuming C = A(i; j A0 ) and so on.
100 iterations,14 the ratio of total learning
As Fig. 8 shows, despite higher time comtime using the entire corpus is calculated as plexity, extended models draw similar curves(1215 100)=(279 + 0:661 100) = 352, and to the PCFG model and they require at mosthence the graphical EM algorithm will still be twice as much time as the PCFG model.
orders of magnitude faster than the I-O algo(sec)rithm in terms of total learning time.15
0.00045j2

2

5 Learning experiments withextended PCFGs

Finally we turn to extensions of PCFGs incorporating context sensitiveness in rule application. We consider two extensions. One
is Pseudo PCSGs (pseudo probabilistic context sensitive grammar) (Charniak and Carroll, 1994) in which the probability of selecting a rule for expanding a non-terminal depends on its parent category. The other islexicalized PCFGs (Charniak, 1997; Collins,
1997; Carroll and Rooth, 1998; Beil et al.,
1999; Charniak, 2000) but in the most basic
form such that the probability of rule application is conditioned on a \head" associatedwith the non-terminal to be expanded.
We conducted learning experiments withthese extensions by the graphical EM algorithm just like the experiments in Section 4,
using ATR corpus and Gatr. We, however,
had to modify the parser to generate appropriate support graphs for each grammar
model, but the modi cation was straightforward; just make every thing conditioned. For
example, in the case of a Pseudo PCSG, therule application of A  is conditioned on
the parent category A0 of A so that the label of a disconnected graph takes the form!

13 An attempt to measure B for the EDR corpus

available (9,900 sentences) was abandoned due tomemoryover ow.
14 The plausible number of iterations until convergence by the graphical EM algorithm using the entire
ATR corpus is 260 (this is the average of 3 trials),
which would give more favorable ratio to the graphical15EM algorithm.
We also conducted a learning experiment tomeasure time per iteration for the entire ATR
corpus using an implementation by Mark Johnson of the I-O algorithm down-loadable fromhttp://www.cog.brown.edu/%7Emj/. This implementation turned out to be twice as fast as our naive implementation but gave B=630 seconds which is ordersof magnitude slower than the graphical EM algorithm.

Lexicalized
PCFG

0.00040.000350.0003

psuedo PCSG

0.00025

PCFG

0.00020.000150.00015e-05

L
0

5 10 15 20 25 30

Figure 8: Time per iteration w.r.t. various
extensions of PCFGs
For the sake of completeness, we summarize the performance measures in the Table 1
which is obtained by 11 fold cross-validationof various PCFGs using ATR corpus, Gatr
and the Viterbi-parser combined with learned
parameters.16 Clearly these extended models perform better than the pure PCFG, andit appears that provided the grammar is notvery ambiguous, we may expect that performance using parameters obtained by unsupervised learning (EM) comes close to the performance using those obtained by supervised
learning (counting).
6 Conclusion

We have proposed a new data structure, support graphs, and a new EM algorithm, thegraphical EM algorithm for PCFGs (and theirextensions) that runs on support graphs. We
have conducted learning experiments using
two corpora, ATR corpus and EDR corpus
which are contrasting in sentence length and
16 PPCSG stands for Pseudo PCSG and LLPCFG

for lexicalized PCFG. \Labeled Tree" means exact
match and 0-CB is zero cross brackets. The base lineis the performance in the case of randomly choosing asentence and its labeled tree.

Labeled Tree PCFG PPCSG LPCFG
counting
81.09 84.90 83.97
EM
71.88 76.03 78.68
Baseline
64.37
0-CB
PCFG PPCSG LPCFG
counting 87.89 92.08 92.39
EM
86.83 89.24 89.75
Table 1: Evaluation of extended PCFGs
the ambiguity of the CFG grammars developed for them. In both cases however, thegraphical EM algorithm outperformed the IO algorithm by orders of magnitude in termsof updating time per iteration (and also interms of total learning time with ATR corpus). We have also observed, experimentallyusing ATR corpus, that learning time by thegraphical EM algorithm applied to extended
PCFGs (a Pseudo PCSG and a lexicalized
PCFG) does not deteriorate much compared
to a pure PCFG.
References

North American Cahpter of the Association for
Computational Lingusitics.
M. Collins. 1997. Three generative, lexicalized
models for statistical parsing. In Proceedingsof the 35th Annual Meeting of the Association
for Computational Linguistics (ACL'97), pages
16{23.
A. P. Dempster, N. M. Laird, and D. B. Rubin.
1977. Maximum likelihood from incomplete
data via the EM algorithm. Royal StatisticalSociety, B39(1):1{38.
T. Fujisaki, F. Jelinek, J. Cocke, E. Black, andT. Nishino. 1989. A probabilisitic parsing method for sentence disambiguation. In
Proceedings of International Parsing Workshop'89, pages 85{94.
Ltd. Japan Electronic Dictionary Research Institute. 1995. Edr electronic dictionary technical guide (2nd edition). Technical Report EDR
TR{045.
Y. Kameya and T. Sato. 2000. Ecient EM
learning for parameterized logic programs. In
Proceedings of the 1st Conference on Computational Logic (CL2000), volume 1861 of Lecture
Notes in Arti cial Intelligence, pages 269{294.
Springer.

J. K. Baker. 1979. Trainable grammars for speech
recognition. In Proceedings of Spring Conference of the Acoustical Society of America, pages
547{550.

Y. Kameya, T. Mori, and T. Sato. 2001. Fastem learning based on wfst of pcfgs and theirextensions (in j). Journal of Natural Language
Processing, Vol.8(No.1):49{84.

F. Beil, G. Carroll, D. Prescher, S. Riezler, and
M. Rooth. 1999. Inside-outside estimation of alexicalized pcfg for german. In Proceedings ofthe 37th Annual Meeting of the Association for
Computational Linguistics (ACL'99), pages {.

Y. Kameya. 2000. Learning and Representation of Symbolic-Statistical Knowledge (inJapanese). Ph. D. dissertation, Tokyo Instituteof Technology.

G. Carroll and M. Rooth. 1998. Valence induction with a head-lexicalized pcfg. In Proceedings of the 3rd Conference on Empirical Methods in Natural Language Processing (EMNLP
3).
E. Charniak and G. Carroll. 1994. Contextsensitive statistics for improved grammaticallanguage models. In Proceedings of the 12th
National Conference on Arti cial Intelligence(AAAI'94), pages 728{733.
E. Charniak. 1997. Statistical parsing with aconttext-free grammar and word statistics. In
Proceedings of the 14th National Conference on
Arti cial Intelligence (AAAI'97).
E. Charniak. 2000. A maximum-entropy-inspiredparser. In Proceedings of 1st Meeting of theK. Lari and S. J. Young. 1990. The estimation of stochastic context-free grammars using
the Inside-Outside algorithm. Computer Speechand Language, 4:35{56.
C. D. Manning and H. Schutze. 1999. Foundations of Statistical Natural Language Processing. The MIT Press.
F. C. N. Pereira and Y. Schabes. 1992. InsideOutside reestimation from partially bracketed
corpora. In Proceedings of the 30th Annual
Meeting of the Association for Computational
Linguistics (ACL'92), pages 128{135.
A. Stolcke. 1995. An ecient probabilistic
context-free parsing algorithm that computes
pre x probabilities. Computational Linguistics,
21(2):165{201.

H. Tanaka, T. Takezawa, and J. Etoh. 1997.
Japanese grammar for speech recognition considering the MSLR method. In Proc. of themeeting of SIG-SLP (Spoken Language Processing), 97-SLP-15-25, pages 145{150. Information
Processing Society of Japan. In Japanese.
N. Uratani, T. Takezawa, H. Matsuo, and
C. Morita. 1994. ATR integrated speech andlanguage database. Technical Report TR-IT0056, ATR Interpreting Telecommunications
Research Laboratories. In Japanese.