    \documentclass[english]{jnlp_1.4_rep}

\usepackage{jnlpbbl_1.3}
\usepackage[dvipdfm]{graphicx}
\usepackage{udline}
\setulminsep{1.2ex}{0.2ex}
\usepackage{amsmath}

\input{figs-line-number.txt}




\newcommand{\q}{}
\newcommand{\iq}{}
\newcommand{\sym}[1]{}
\newcommand{\tuple}[1]{}
\newcommand{\defined}{}
\newcommand{\incby}{}
\newcommand{\Vn}{}
\newcommand{\Vt}{}
\newcommand{\dto}{}
\newcommand{\rderives}[1]{}
\newcommand{\derivesstar}{}
\newcommand{\derivesplus}{}
\newcommand{\win}{}
\newcommand{\rseq}{}
\newcommand{\trees}{}
\newcommand{\treesin}{}
\newcommand{\treesout}{}
\newcommand{\subtrees}{}
\newcommand{\corpus}{}
\newcommand{\labels}{}
\newcommand{\brackets}{}
\newcommand{\wfst}{}
\newcommand{\Rmax}{}
\newcommand{\condrule}[3]{}
\newcommand{\lastrule}{}
\newcommand{\sg}{}  
\newcommand{\subsg}{}
\newcommand{\occ}{} 
\newcommand{\Gtanaka}{}
\newcommand{\Rtanaka}{}
\newcommand{\Gchom}{}
\newcommand{\Rchom}{}
\newcommand{\bigbullet}{}
\newcommand{\varP}{}
\newcommand{\varQ}{}
\newcommand{\varR}{}
\newcommand{\varPstar}{}
\newcommand{\varRstar}{}
\newcommand{\varON}{}
\newcommand{\varComp}{}
\newcommand{\varLast}{}
\newcommand{\rw}[1]{}
\newcommand{\proc}[1]{}
\newcommand{\es}[3]{}
\newcommand{\esp}[4]{}
\newcommand{\ip}[3]{}
\newcommand{\op}[3]{}



\Volume{21}
\Number{4}
\Month{September}
\Year{2014}

\received{2000}{5}{10}
\accepted{2000}{10}{10}

\setcounter{page}{619}

\etitle{Using WFSTs for Efficient EM Learning of Probabilistic CFGs and Their Extensions\footnotetext{\llap{*~}This article has been partially revised for better understanding of overseas readers.}}
\eauthor{Yoshitaka Kameya\affiref{TiTech} \and Takashi Mori\affiref{TiTech} \and Taisuke Sato\affiref{TiTech}}
\eabstract{
Probabilistic context-free grammars (PCFGs) are a widely known class
of probabilistic language models. The Inside-Outside (I-O) algorithm
is well known as an efficient EM algorithm tailored for PCFGs.
Although the algorithm requires inexpensive linguistic resources,
there remains a problem in its efficiency.
This paper presents an efficient method for training PCFG
parameters in which the parser is separated from
the EM algorithm, assuming that the underlying CFG is given.
A new EM algorithm exploits the compactness
of well-formed substring tables (WFSTs) generated by the parser.
Our proposal is general in that the input grammar need not
take Chomsky normal form (CNF) while it is equivalent to
the I-O algorithm in the CNF case.
In addition, we propose a polynomial-time EM algorithm for
CFGs with context-sensitive probabilities, and report
experimental results with the ATR dialogue corpus
and a hand-crafted Japanese grammar.
}
\ekeywords{Probabilistic context-free grammars, EM algorithm, Inside-Outside algorithm, Well-formed substring tables}

\headauthor{Kameya et al.}
\headtitle{Efficient EM Learning of PCFGs and Their Extensions by Using WFSTs}

\affilabel{TiTech}{}{Department of Computer Science, Graduate School of Information Science and Engineering, Tokyo Institute of Technology}

\Reprint[T]{Vol.~8, No.~1, pp.~49--84}

\begin{document}

\maketitle

\section{Introduction}

{\em Probabilistic context-free grammars} (PCFGs) are a widely known class
of probabilistic language models.  They can be seen as context-free
grammars (CFGs) in which each production rule is associated with
a real number, interpreted as a probability or a {\em parameter}.
The probability of a sentence or its parse is computed from these
rule probabilities
and exploited in various predictive tasks.  However, practical problems,
such as cost and subjectivity, arise if we manually specify the
rule probabilities.  One solution for this is to train PCFGs,
i.e., to automatically estimate the rule probabilities from corpora.

From syntactically annotated corpora, it is straightforward
to estimate rule probabilities as the relative frequencies of rules
in the corpora.  However, we use unbracketed (only morphologically analyzed)
corpora as a less expensive training resource.
In the literature, the {\em Inside-Outside algorithm}
(hereafter the I-O algorithm) \cite{Baker79,Lari90}
is a well-known method for training PCFGs from such unbracketed corpora.
We can regard the I-O algorithm as an EM algorithm
\cite{Dempster77} tailored for PCFGs,
as it is built on a triangular matrix, that was originally used in
the Cocke-Younger-Kasami (CYK) parser.
The I-O algorithm is certainly a polynomial-time algorithm, but
its cubic computation time hinders us from handling large-scale
corpora.  Furthermore, it has a limitation in
applicability, in that the underlying CFG must take Chomsky normal form (CNF).

To overcome these shortcomings, we propose an efficient method for training
PCFG parameters by assuming that the underlying CFG is given.
In the proposed method, we introduce {\em well-formed substring tables}
(WFSTs), which are data structures originally used in efficient parsing algorithms.
The entire process of the proposed method is split into the following
two steps:
\begin{description}
\item[\textbf{Parsing:}]
  Using an efficient parser, we first obtain all parses of all sentences
  in the corpus, where the parses are kept implicitly in the form of a WFST.
\item[\textbf{EM learning:}]
  We then extract a data structure called {\em support graphs} from the
  WFST, and run the {\em graphical EM algorithm} (gEM), an EM algorithm
  tailored for the support graphs.
\end{description}
WFST is a generic name for data structures that contain all
partial parse trees obtained during parsing \cite{Tanaka88,Nagata99}.
Using WFSTs is a standard technique for preventing the parser
from re-analyzing phrases that have already been analyzed.
The parsers finally output full parses by assembling the partial
parses in a WFST.  Table~\ref{tab:WFST} lists WFSTs used in
well-known parsers.  \citeA{Fujisaki89} used parse information
in PCFG training, as we do in our proposal; however,
they did not exploit WFSTs.

\begin{table}[b]
\caption{Examples of WFSTs}
\label{tab:WFST}
\input{10table01.txt}
\end{table}

The proposed method makes substantial improvement in generality and
efficiency at the same time.  To be more concrete,
it has a couple of advantages:
\begin{description}
\item[\textbf{Advantage~1:}]
  The proposed method is a generalization of previous EM learning
  methods for PCFGs, such as the I-O algorithm and Fujisaki et~al.'s method.
\item[\textbf{Advantage~2:}]
  Given a practical grammar, the proposed method runs significantly
  (by orders of magnitude, in our experiments) faster than the I-O algorithm.
\item[\textbf{Advantage~3:}]
  The proposed method is a generalization of polynomial-time
  EM algorithms for
  ``context-free grammars with context-sensitive probability'' \cite{Magerman92},
  such as the rule bigram models \cite{Kita94}.
\end{description}
As stated before, the I-O algorithm works on a triangular
matrix, which is the WFST of the CYK parser, so it reduces to the
proposed algorithm, where the CYK parser and the gEM algorithm are
cascaded (Advantage~1).
On the other hand, the proposed algorithm does not require
the assumption that the underlying CFG takes CNF
when combining the Earley parser or the generalized LR (GLR) parser
\cite{Tomita91} with the gEM algorithm.
The paper will also show that the proposed method includes
Stolcke's probabilistic Earley parser \cite{Stolcke95}
and a training method from bracketed corpora,
proposed by \shortciteA{Pereira92}.\footnote{
To be precise, the proposed method includes Pereira and Schabes's
method when an underlying CFG is given.
}
Furthermore, Advantage~2 comes from the fact that the proposed
method only scans a compact data structure, i.e., a WFST.  A combination
with the GLR parser would further reduce the training time, thanks to
the parser's bottom-up nature and pre-compilation of CFGs into LR tables.
Advantage~3 exhibits a benefit from the generality of
the proposed method, and in this paper, we present a polynomial-time
EM algorithm for Kita et~al.'s (1994) rule bigram models. \nocite{Kita94}

The rest of the paper is outlined as follows.  First, Section~\ref{sec:PCFG}
formally introduces PCFG, the CYK parser, the I-O algorithm, and their
related notions.  Then, Section~\ref{sec:GEM}
describes a combination of the CYK parser and the gEM algorithm,
and compares the result with the I-O algorithm to see Advantage~1.
To examine Advantage~2, Section~\ref{sec:experiment} reports
an experimental result where the training time of a combination of
the GLR parser and the gEM algorithm is measured using
the ATR dialogue corpus (SLDB).
Section~\ref{sec:extensions} shows Advantage~3 specifically,
by presenting a polynomial-time EM algorithm for an extension of PCFG.
Lastly, Section~\ref{sec:related-work} describes related work and
provides an additional discussion on Advantage~1.
Most of the example grammars and sentences, and their parsing results
are borrowed from \cite{Nagata99}, possibly with some modifications.


\section{Preliminaries}
\label{sec:PCFG}

In this section, we introduce some concepts and notation related to
the paper.  First, we let $A,B,\ldots$ be non-terminal symbols in
a CFG, and $a,b,\ldots$ terminal symbols.  Also, $\rho$ indicates
a non-terminal or terminal symbol, and
$\zeta$, $\xi$, $\nu$ indicate an empty sequence or sequences that
comprise non-terminal and terminal symbols.  An empty sequence
is denoted by $\varepsilon$.  The symbols in example grammars are
written in typewriter fonts (e.g., $\sym{S},\sym{NP},\ldots$).
A list whose $n$-th element is denoted by $y_n$
is represented by $\tuple{y_1,y_2,\ldots}$.  For a list
$Y=\tuple{\ldots,y,\ldots}$, we can say $y\in Y$.  The cardinality
of a set $X$, the number of symbols in a sequence $\zeta$, and
the number of elements in a list $Y$ are denoted by $|X|$, $|\zeta|$,
and $|Y|$, respectively.


\subsection{Probabilistic context-free grammars}
\label{sec:PCFG:PCFG}

First, we define a CFG $G$ by a quadruple $\tuple{\Vn,\Vt,R,S}$,
where $\Vn$ is a set of non-terminal symbols,
$\Vt$ is a set of terminal symbols, $R$ is a set of production rules,
and $S$ is a starting symbol $(S\in \Vn)$.  A production rule $r$
in $R$ takes the form $A\to\zeta$ and replaces a non-terminal symbol
$A$ appearing in some sequence $\zeta'$ with $\zeta$.  In this paper, we always
apply a production rule that replaces the leftmost non-terminal symbol,
i.e., we focus only on leftmost derivations.  We write $\zeta\rderives{r}\xi$
when $\zeta$ is rewritten into $\xi$ by a production rule $r$.
When such rewritings are performed for zero or more times, we write
$\zeta\derivesstar\xi$ and say that $\xi$ is derived from $\zeta$.
If we emphasize that there is one or more rewritings,
we write $\zeta\derivesplus\xi$.  A sequence $\win$ of
terminal symbols that can be derived from the start symbol $S$
(i.e., $S\derivesstar\win$) is called a sentence.  The set of
sentences that can be derived using the production rules in
a CFG $G$ is called the language of $G$, and is denoted by $L_G$.

Then, we denote by $G(\theta)$ a PCFG whose underlying CFG is $G$.
Here, $\theta$ is a $|R|$-dimensional vector, and is called
the {\em parameters} of the PCFG.  Each element in $\theta$
is referred to by $\theta(r)$, where $r\in R$, and we assume that
$0\le \theta(r)\le 1$ and $\sum_{\zeta:(A\to\zeta)\in R}\theta(A\dto\zeta)=1$.
With a PCFG, the rules applied are supposed to be chosen
independently.  Thus, in a derivation
$\zeta_0\rderives{r_1}\zeta_1\rderives{r_2}\zeta_2
	\rderives{r_3}\cdots\rderives{r_{K}}\zeta_K$,
the generative probability $P(\rseq|\theta)$ of a sequence
$\rseq=\tuple{r_1,r_2,\ldots,r_K}$ of the applied rules is computed by
\begin{equation}
\textstyle
P(\rseq|\theta)=\prod_{k=1}^K\theta(r_k).
\label{eq:derivation-prob}
\end{equation}
Letting $\occ(r,\rseq)$ be the number of occurrences of a rule $r$
in rule applications $\rseq$, the probability above can be
computationally simplified as
\begin{equation}
\textstyle
P(\rseq|\theta)=\prod_{r\in R}\theta(r)^{\occ(r,\rseq)}.
\label{eq:derivation-prob2}
\end{equation}
Furthermore, let $\trees(\win)$ be a set of possible rule applications
to generate a sentence $\win$.  Then, noting that $\win$ is uniquely
determined given rule applications $\rseq$, we have the following relation
concerning a joint probability $P(\win,\rseq|\theta)$:
\begin{equation}
P(\win,\rseq|\theta)=
	\left\{
		\begin{array}{ll}
		P(\rseq|\theta)&\mbox{if}\;\rseq\in\trees(\win),\\
		0&\mbox{otherwise}.
		\end{array}
	\right.
\label{eq:joint-prob}
\end{equation}
From this, we have the generative probability $P(\win|\theta)$ of
a sentence $\win$ being derived from the start symbol $S$ as follows:
\begin{equation}
\textstyle
P(\win)
	=\sum_{{\rm all}\;\rseq}P(\win,\rseq|\theta)
	=\sum_{\rseq\in\trees(\win)}P(\rseq|\theta).
	\label{eq:sentence-prob}
\end{equation}
If parameter $\theta$ is obvious from the context, we abbreviate
$P(\rseq,\ldots|\theta)$ and $P(\win,\ldots|\theta)$ as
$P(\rseq,\ldots)$ and $P(\win,\ldots)$, respectively.
In addition to the independence of rule applications,
any PCFG $G(\theta)$ in this paper is assumed to satisfy the following
conditions:
\begin{itemize}
\item
  $G(\theta)$ is consistent, i.e., $\sum_{\win\in L_G}P(\win|\theta)=1$ holds.
\item
  $G$ has no $\varepsilon$ rule, i.e., no production rule whose
  right hand side is $\varepsilon$.
\item
  There is no cyclic production w.r.t.\ $G$,
  i.e., $G$ has no nonterminal $A$ such that $A\derivesplus A$.
\end{itemize}
\shortciteA{Chi98} proved that, given an underlying CFG
satisfying the last two conditions and
unbracketed corpora $\corpus$ of finite-length sentences,
PCFG $G(\theta^{\ast})$ is consistent where 
$\theta^{\ast}$ is the parameters trained by the I-O algorithm.


\subsection{Corpora and parse trees}
\label{sec:PCFG:corpus}

In a sentence $\win = w_1w_2\cdots w_n\in L_G$,
each $w_j$ is called a word ($n>0$, $j=1\ldots n$).
Then, we introduce Earley-style word positions
$d=0\ldots n$ in $\win$.
For $0\le d\le d'\le n$, a subsequence or a {\em phrase}
$w_{d+1}\cdots w_{d'}$
between positions $d$ and $d'$ is denoted by $\win_{d,d'}$
(note that $\win=\win_{0,n}$).  A phrase $w_d\cdots w_{d'}$
may be written by a list $\tuple{w_d,\ldots,w_{d'}}$.
For a sentence $\win\in L_G$, a parse tree of $\win$ represents
a derivation process $S\derivesstar\win$ in a tree form.
Since we focus on leftmost derivations, 
a parse tree $t$ of $\win$ is uniquely determined
from rule applications $\rseq$ in $S\derivesstar\win$, and
thus, we will refer to $t$ and $\rseq$ interchangeably.
Having assumed that there is neither $\varepsilon$ rule nor
cyclic production, a subtree $t'$ of a parse tree $t$ of a
sentence $\win$ is uniquely identified by a pair $\tuple{d,d'}$
where the words in $w_{d,d'}$ are leaf nodes in $t'$.
From this observation, letting $A$ be the root node of $t'$,
we often refer to $t'$ by a label $A(d,d')$, called a
{\em subtree label}.
Then, a parse tree $t$ of a sentence $\win$ can be seen as
a set $\labels(t)$ of such subtree labels of non-leaf nodes.
$\labels(t)$ is called a {\em label set} of $t$.
Some may find that a pair $\tuple{d,d'}$ of word positions
corresponds to a bracket in bracketed corpora.  We define
$\brackets(t)\defined\{\tuple{d,d'}\mid A(d,d')\in\labels(t)\}$
and call $\brackets(t)$ the {\em bracket set} of $t$.

Furthermore, suppose that a production rule
$A\dto\rho_1\rho_2\cdots\rho_M$ is applied in a tree $t$,
and $\rho_1,\rho_2,\ldots,\rho_M$ are the root nodes
of subtrees $\rho_m(d_{m-1},d_m)$ ($m=1\ldots M$),
as illustrated in Figure~\ref{fig:parse-tree}.
Then, we introduce a partial order $@$ such that
$A(d_0,d_M)@\rho_m(d_{m-1},d_m)$,
and say that $A(d_0,d_M)$ is a parent of $\rho_m(d_{m-1},d_m)$,
or inversely, $\rho_m(d_{m-1},d_m)$ is a child of $A(d_0,d_M)$.
With a slight adjustment in notation, we jointly write
the partial orderings above as
\begin{equation}
A(d_0,d_M)@\rho_1(d_0,d_1)\rho_2(d_1,d_2)\cdots\rho_M(d_{M-1},d_M)
\label{eq:parent-children}
\end{equation}
and call this a {\em parent-children pair} of subtrees.
We define $\wfst(t)$ as the entire collection of such parent-children
pairs in a tree $t$.  For a sequence $\rseq$ of rule applications
that corresponds to a parse tree $t$, we define
$\labels(\rseq)\defined\labels(t)$,
$\brackets(\rseq)\defined\brackets(t)$,
and $\wfst(\rseq)\defined\wfst(t)$.

\begin{figure}[t]
\begin{center}
\includegraphics{21-4ia10f1.eps}
\end{center}
\caption{Parent-children pair of subtrees}
\label{fig:parse-tree}
\end{figure}

We consider four types of corpora for training PCFGs:\ 
(1) {\em labeled corpora},
(2) {\em fully bracketed corpora},
(3) {\em partially bracketed corpora},
and (4) {\em unbracketed corpora}. 
Our training scheme is maximum likelihood estimation,
where a corpus $\corpus\defined\tuple{c_1,c_2,\ldots,c_N}$
of $N$ sentences is considered as the result of $N$
independent samplings (i.e., probabilistic derivations)
using the rules with probabilities in PCFG $G(\theta)$.
Letting $\win_\ell$ and $\rseq_\ell$ be, respectively,
the sentence and the rule applications obtained in the $\ell$-th
sampling ($\ell=1\ldots N$), 
$c_\ell=\tuple{\win_\ell,\labels(\rseq_\ell)}$ when $\corpus$ is a labeled corpus,
$c_\ell=\tuple{\win_\ell,\brackets(\rseq_\ell)}$ when $\corpus$ is a fully bracketed corpus,
$c_\ell=\tuple{\win_\ell,\brackets_\ell}$ when $\corpus$ is a partially bracketed corpus,
and $c_\ell=\win_\ell$ when $\corpus$ is an unbracketed corpus
($\win_\ell\in L_G$, $\rseq_\ell\in\trees(\win_\ell)$, and
$\brackets_\ell\subseteq\brackets(\rseq_\ell)$).


\subsection{The CYK parser}
\label{sec:PCFG:CYK}

The CYK parser is applicable to the CFGs in CNF.
We prepare an $(n_\ell\times n_\ell)$ upper triangular matrix $T^{(\ell)}$
for a sentence $\win_\ell$ in an unbracketed corpus $\corpus$
($n_\ell=|\win_\ell|$).  Unlike a typical formulation of
the CYK parser, the row numbers of the triangular matrix are
decremented by one in order to maintain consistency with the Earley-style
word positions we use.  The element $T_{d,d'}$ at the $d$-th row
and the $d'$-th column in the triangular matrix stores all partial
parse trees for the phrase $\win_{d,d'}$.

Figure~\ref{alg:CYK} shows the routine $\proc{CYK-Parser}$, which
implements the CYK parser.
Starting from the diagonal elements in the triangular matrix,
we build up partial parse trees (parent-children pairs)
in non-diagonal elements towards the top-right corner of the matrix
(Lines~\ref{list:CYK:fill-diagonal:begin}--\ref{list:CYK:fill-non-diag:end}).
Finally, if we have a parent-children pair of the form ``$S(0,n_\ell)@\;\cdot$''
in the top-right corner $T_{0,n_\ell}$, we recognize that the parsing has
ended in success, and otherwise, the parsing has failed
(Line~\ref{list:CYK:accept}).  After a successful parsing, we can extract
a full parse tree by following the parent-children pairs 
from ``$S(0,n_\ell)@\;\cdot$'' stored in the top-right corner.
For example, following a Japanese CFG $G1$ shown in Figure~\ref{gram:ichiro-CNF},
we have a triangular matrix shown in Figure~\ref{fig:CYK-table}
for a sentence $\win=\tuple{急いで,走る,一郎,を,見た}$
([{\it Someone}] {\it saw Ichiro who is running in a hurry}).
From the parent-children pairs marked by $\bigcirc$, we can extract
parse tree $t1$ in Figure~\ref{fig:parse-tree-ichiro-CNF},
and from those marked by \bigbullet, parse tree $t2$ is extracted.

\begin{figure}[t]
\begin{center}
\includegraphics{21-4ia10f2.eps}
\end{center}
\caption{The CYK parser}
\label{alg:CYK}
\end{figure}
\begin{figure}[t]
\begin{center}
\includegraphics{21-4ia10f3.eps}
\end{center}
\caption{Example CFG $G1$}
\label{gram:ichiro-CNF}
\end{figure}


\subsection{The Inside-Outside algorithm}
\label{sec:PCFG:IO}

As mentioned before, we aim to train the parameters of a PCFG from
a given corpus $\corpus=\tuple{c_1,c_2,\ldots,c_N}$, following
a standard manner of maximum likelihood estimation.  For a labeled
corpus $\corpus$, the relative frequency $\theta^{\ast}(r)$ of
a rule $r$ is exactly the maximum likelihood estimate of
the parameter $\theta(r)$.
Generally, however, such labeled corpora are expensive, and
it seems more likely that only unbracketed corpora are available.
The I-O algorithm, an EM algorithm tailored for PCFGs,  is used
in such a case, since the relative frequency method cannot be
applied to unbracketed corpora.
The I-O algorithm is a maximum likelihood estimation method,
i.e., it finds the parameters $\theta^{\ast}$ that
locally maximize the likelihood $\prod_{\ell=1}^N P(\win_\ell\mid\theta)$
or its logarithm $\sum_{\ell=1}^N \log P(\win_\ell\mid\theta)$
(called the {\em log-likelihood}), given an unbracketed corpus
$\corpus=\tuple{\win_1,\win_2,\ldots,\win_N}$.

\begin{figure}[t]
\begin{center}
\includegraphics{21-4ia10f4.eps}
\end{center}
\caption{Triangular matrix for $G1$ and a sentence $\tuple{急いで,走る,一郎,を,見た}$}
\label{fig:CYK-table}
\end{figure}
\begin{figure}[t]
\begin{center}
\includegraphics{21-4ia10f5.eps}
\end{center}
\caption{Two full parse trees (numbers at the bottom are word positions)}
\label{fig:parse-tree-ichiro-CNF}
\end{figure}

In the literature including \shortciteA{Lari90}'s work,
the rule set $R$
of an underlying CFG is not given, while only set $\Vt$ of
terminals and set $\Vn$ of non-terminals are given.
For comparison, we describe the I-O algorithm
to which some rule set $R$ is given.  Indeed, the I-O algorithm
given $\Vt$ and $\Vn$ is equivalent to the one
given the following rule set (abbreviated as $\Rmax$ hereafter):
\begin{equation}
\Rmax(\Vn,\Vt)\defined
	\left\{A\dto BC\;\left|\; A,B,C\in \Vn\right.\right\}
	\;\cup\;
	\left\{A\dto a\;\left|\; A\in \Vn, a\in\Vt\right.\right\}.
\label{eq:Rmax}
\end{equation}
Note that, in both cases, the rule set needs to take CNF.
While \shortciteA{Lari90} used
the I-O algorithm for learning set $R$ of production
rules as well, we focus on the training of parameters $\theta$.

The central part of the I-O algorithm is the computation of
two types of probabilities:\ the {\em inside probabilities}
$P(A\derivesstar\win_{d,d'}^{(\ell)})$
and the {\em outside probabilities}
$P(S\derivesstar\win_{0,d}^{(\ell)}A\win_{d',n_\ell}^{(\ell)})$
($\ell=1\ldots N$, $A\in \Vn$, $0\le d < d'\le n_\ell$).
These probabilities are stored into the array variables
$\beta_{d,d'}^{(\ell)}[A]$ and $\alpha_{d,d'}^{(\ell)}[A]$,
respectively.  These array variables are prepared in the
element $T_{d,d'}$ in the triangular matrix.
The generative probability
$P(S\derivesstar\win_\ell)$ of a sentence $\win_\ell$ is
stored into $\beta_{0,n_\ell}^{(\ell)}[S]$.

\begin{figure}[b]
\begin{center}
\includegraphics{21-4ia10f6.eps}
\end{center}
\caption{Routines for computing the inside probabilities (above) and outside probabilities (below)}
\label{alg:get-beta-alpha}
\end{figure}

The routines $\proc{Get-Beta}$ and $\proc{Get-Alpha}$, which are
used for computing the inside and outside probabilities, respectively,
are presented in Figure~\ref{alg:get-beta-alpha}. In these routines,
for simplicity, we assume that the array variables 
$\alpha_{d,d'}^{(\ell)}[\cdot]$ and $\beta_{d,d'}^{(\ell)}[\cdot]$
are initialized as zero, whenever the routines are called.
Starting from the diagonal elements of the triangular matrix,
$\proc{Get-Beta}$ computes the inside probabilities towards the top-right
corner $\beta_{0,n_\ell}^{(\ell)}[\cdot]$, just like the CYK parser
builds up partial parse trees.  Conversely, $\proc{Get-Alpha}$
starts from the top-right corner $\alpha_{0,n_\ell}^{(\ell)}[\cdot]$
and computes the outside probabilities towards the diagonal elements.
This way of computing the inside and outside probabilities
can be seen as {\em dynamic programming}.  After having computed the inside and
outside probabilities, the conditional expected occurrences
(the {\em expected rule counts} hereafter) of $A\dto BC$ and
$A\dto a$ in rule applications, given a corpus $\corpus$, are computed as:
\pagebreak
\begin{align}
 \eta[A\dto BC]&:= 
	\sum_{\ell=1}^N
		\frac{1}{\beta_{0,n_\ell}^{(\ell)}[S]}
		\sum_{k=2}^{n_\ell}\sum_{d=0}^{n_\ell-k}\sum_{k'=1}^{k-1}
		\theta(A\dto BC)
		\alpha_{d,d+k}^{(\ell)}[A]
		\beta_{d,d+k'}^{(\ell)}[B]
		\beta_{d+k',d+k}^{(\ell)}[C]
	\label{eq:eta-ABC},\\
 \eta[A\dto a]&:=
		\sum_{\ell=1}^N
		\frac{1}{\beta_{0,n_\ell}^{(\ell)}[S]}
		\sum_{d=0}^{n_\ell-1}\theta(A\dto a)\alpha_{d,d+1}^{(\ell)}[A].
	\label{eq:eta-Aa}
\end{align}
Furthermore, parameters $\theta(A\dto\zeta)$ are re-estimated
from the expected rule counts above:
\begin{equation}
\textstyle
\theta(A\dto\zeta):=
		\eta[A\dto\zeta]\Big/
			\sum_{\zeta':(A\to\zeta')\in R}\eta[A\dto\zeta'].
\label{eq:update}
\end{equation}
In the I-O algorithm, we first initialize $\theta$ randomly, and then
iteratively update $\theta$ by $\proc{Get-Beta}$;
$\proc{Get-Alpha}$; and
Eqs.~\ref{eq:eta-ABC}, \ref{eq:eta-Aa}, and \ref{eq:update}.
With this iteration, the log-likelihood
$\sum_{\ell=1}^N \log P(\win_\ell)=
	\sum_{\ell=1}^N \log\beta_{0,n_\ell}^{(\ell)}[S]$
increases monotonically and finally converges.  After convergence,
the I-O algorithm terminates and outputs the parameters
at the same time as the trained ones.

Here, we evaluate the complexity of the I-O algorithm.
In general, the number of iterations is unknown in advance since
it depends on the initial parameters, so we evaluate the
complexity of the I-O algorithm with that of one iteration.
Given a set $\Vn$ of nonterminals and a set $\Vt$ of terminals,
the worst-case complexity is measured
considering the case with $R=\Rmax(\Vn,\Vt)$.  Let $L$ be
the length of the longest sentence in a training corpus
$\corpus$.  Then, by examining the {\bf for} or {\bf foreach} loops
and the ranges of the summations in $\proc{Get-Beta}$ and
$\proc{Get-Alpha}$ (Figure~\ref{alg:get-beta-alpha}),
the worst-case complexity of the I-O algorithm is
$O(|R|L^3N)=O(|\Vn|^3 L^3N)$.


\subsection{Additional notes on the Inside-Outside algorithm}
\label{sec:PCFG:IO-problems}

\begin{figure}[b]
\begin{center}
\includegraphics{21-4ia10f7.eps}
\end{center}
\caption{Situations considered in computing the inside and outside probabilities, where $n=n_\ell$}
\label{fig:get-beta-alpha}
\end{figure}

The most expensive part in the I-O algorithm is the computation
of the inside and outside probabilities.  That is,
at Line~\ref{list:get-beta:calc-beta} in $\proc{Get-Beta}$,
we compute the inside probabilities, taking into account all the situations
illustrated in Figure~\ref{fig:get-beta-alpha} (1).
For the outside probabilities, the first and second terms
on the right hand side
at Lines~\ref{list:get-alpha:calc-op:begin} and \ref{list:get-alpha:calc-op:end}
in $\proc{Get-Alpha}$ correspond to all the situations in
Figure~\ref{fig:get-beta-alpha} (2) and (3), respectively.
One may see that the process of probability computation in the I-O algorithm
is similar to top-down parsers, since it considers all possible
situations without taking into account the input sentences $\win_\ell$.
In general, ignoring the constraints from the
input sentences slows down the parser, and therefore, by analogy,
the I-O algorithm's top-down nature seems to produce an extra
computational cost.

To see this more formally, we revisit the derivation of the
I-O algorithm described in \shortciteA{Lafferty93}.\footnote{
\citeA{Lafferty93} describes the case where the corpus size $N=1$.
}
First, let us define $\occ(r,\rseq)$ as the occurrences
of a rule $r$ in rule applications $\rseq$, as we did in
Section~\ref{sec:PCFG:PCFG}.  Then, the I-O algorithm can be
obtained by first considering the computation of the expected
rule count $\eta[r]$ of a rule $r$:
\begin{equation}
\eta[r]
	=
	\sum_{\ell=1}^N
		\sum_{{\rm all}\;\rseq}
			P(\rseq|\win_\ell)
			\occ(r,\rseq)
	=
	\sum_{\ell=1}^N
		\frac{1}{P(\win_\ell)}
		\sum_{{\rm all}\;\rseq}
			P(\win_\ell,\rseq)\occ(r,\rseq),
\label{eq:naive-eta}
\end{equation}
second by rewriting Eq.~\ref{eq:naive-eta} into
the form using the partial derivative w.r.t.\ parameter $\theta(r)$:
\begin{equation}
\eta[r]
	\;=\;
	\theta(r)
	\cdot\sum_{\ell=1}^N
		\frac{1}{P(\win_\ell)}
		\frac{\partial P(\win_\ell)}{\partial \theta(r)}
	\;=\;
	\theta(r)
	\cdot\sum_{\ell=1}^N
		\frac{1}{P(\win_\ell)}
		\frac{\partial}{\partial \theta(r)}
		\sum_{{\rm all}\;\rseq}
			P(\win_\ell,\rseq),
	\label{eq:naive-eta2}
\end{equation}
and finally by rewriting Eq.~\ref{eq:naive-eta2} into
a dynamic programming style.
Specifically, substituting $r=(A\dto BC)$ into Eq.~\ref{eq:naive-eta2},
the I-O algorithm computes
$\frac{\partial}{\partial\theta(A\to BC)}
	\sum_{{\rm all}\;\rseq}P(\win_\ell,\rseq)$
as follows (here subscripts ${\cdot}_{\ell}$ and superscripts
${\cdot}^{(\ell)}$ are omitted):
\begin{align}
&\frac{\partial}{\partial\theta(A\to BC)}
	\sum_{\mbox{\footnotesize all $\rseq$}}
		P(\win,\rseq)\nonumber\\
	&\quad =\frac{\partial}{\partial\theta(A\to BC)}
		\sum_{\mbox{\footnotesize
					all $\rseq$ s.t. $A\to BC$ appears in $\rseq$}}
		\iq\iq
		P(\win,\rseq)\nonumber\\
	&\quad =\frac{\partial}{\partial\theta(A\to BC)}
		\sum_{d,k,k'}
		\sum_{\mbox{\footnotesize
				\begin{tabular}{l}
				all $\rseq$ s.t. $A\to BC$ appears in $\rseq$\\
				\q with the position $(d,d+k',d+k)$
				\end{tabular}}}
		\iq\iq\iq\iq
		P(\win,\rseq)
	\label{eq:with-position}\\
	&\quad =\frac{\partial}{\partial\theta(A\to BC)}
		\sum_{d,k,k'}
			P(S\derivesstar\win_{0,d}A\win_{d+k,n})
			\theta(A\dto BC)\cdot\nonumber\\
	&\quad \q\q\q\q\q\q\q\q\q\q\q\q\q
			P(B\derivesstar\win_{d,d+k'})
			P(C\derivesstar\win_{d+k',d+k})\nonumber\\
	&\quad =
		\sum_{d,k,k'}
			P(S\derivesstar\win_{0,d}A\win_{d+k,n})
			P(B\derivesstar\win_{d,d+k'})
			P(C\derivesstar\win_{d+k',d+k}).
\end{align}
The transformation in Eq.~\ref{eq:with-position} is done independently of
the input sentence $\win$ or its parse tree $t\in\trees(\win)$;
therefore, the I-O algorithm runs in a top-down manner.

Another approach to computing the expected rule counts $\eta[r]$ is
just to transform Eq.~\ref{eq:naive-eta} into Eq.~\ref{eq:naive-eta3} below
using Eq.~\ref{eq:joint-prob}, where the parse information
$\trees$ is exploited directly.  In this approach, $\trees$ is obtained
in advance using some efficient parser.  Now, we see that
Eq.~\ref{eq:naive-eta3} is the same as Fujisaki et al.'s
\citeyear{Fujisaki89} method in our notation.
\begin{equation}
\eta[r]	=
	\sum_{\ell=1}^N
		\frac{1}{P(\win_\ell)}
		\sum_{\rseq\in\trees(\win_\ell)}
			P(\rseq)\occ(r,\rseq)
	\label{eq:naive-eta3}
\end{equation}
By using Eq.~\ref{eq:naive-eta3}, unlike the I-O algorithm,
we can avoid probability computations that are not related to
$\psi$.
However in general, $|\trees(\win)|$ is exponential to the
sentence length $|\win|$, and thus, it is not feasible to compute
Eq.~\ref{eq:naive-eta3} as it is.
The proposed method, which is presented next, introduces the notion
of dynamic programming like the I-O algorithm, and computes
Eq.~\ref{eq:naive-eta3} quickly, using a WFST held in some efficient parser.
Thus, we can say that the proposed algorithm harmonizes the advantages
of Fujisaki et al.'s method and the I-O algorithm.


\section{Proposed method}
\label{sec:GEM}

\begin{figure}[b]
\begin{center}
\includegraphics{21-4ia10f8.eps}
\end{center}
\caption{Outline of the proposed method}
\label{fig:scheme}
\end{figure}

The outline of the proposed method is illustrated in Figure~\ref{fig:scheme}.
As inputs, the proposed method is given an underlying CFG
$G=\tuple{\Vn,\Vt,R,S}$ of the target probabilistic CFG
$G(\theta)$ and an unbracketed corpus $\corpus$.  Then, it returns
trained parameters $\theta$ as the output.
In the proposed method, we split the entire training process into
two steps:\ parsing and EM learning.
First, we analyze each sentence $\win_\ell$ in the corpus $\corpus$
by some efficient parser.
Then, the parse information is stored into a WFST
of the parser.  This parse information is collectively
equivalent to a set $\trees(\win_\ell)$ of parse trees of $\win_\ell$,
but is stored fragmentarily.  Therefore, we need an extraction step
for the fragmentary parse information
after parsing, and the extracted data structure is called a
{\em support graph}.
Finally, based on the support graphs, we run the gEM algorithm
and return $\theta$ as trained parameters.

In the case of a CFG $G1$ and a sentence
$\win_\ell=\tuple{急いで,走る,一郎,を,見た}$ in Figure~\ref{gram:ichiro-CNF},
a support graph is extracted from the parent-children pairs
marked with $\bigcirc$ and $\bigbullet$ in Figure~\ref{fig:CYK-table}.
As illustrated in this example,
the support graphs scanned by the gEM algorithm can be
much smaller than the entire triangular matrix,
and accordingly, we can gain a significant speed-up over
the I-O algorithm which inherently scans the entire matrix.


\subsection{Preliminaries}
\label{sec:GEM:preliminary}

As a preparation, we
introduce some notations.  In what follows, we will work for
$\ell=1\ldots N$.  First, we define
$\wfst_\ell\defined\bigcup_{\rseq\in\trees(\win_\ell)}\wfst(\rseq)$
and 
$V_\ell\defined\bigcup_{\rseq\in\trees(\win_\ell)}\labels(\rseq)=
\{\tau\mid\tau@\;\cdot\;\in\wfst_\ell\}$.\footnote{
We have defined $\labels(\rseq)$ and $\wfst(\rseq)$ in Section~\ref{sec:PCFG:corpus}.
} 
We then define $O_\ell\defined\tuple{\tau_1,\tau_2,\ldots,\tau_{|V_\ell|}}$
where the elements in $O_\ell$ are the members in $V_\ell$
and totally ordered so that
$\tau_k@\tau_{k_1}\tau_{k_2}\cdots\tau_{k_M}\in\wfst_\ell
	\Rightarrow k<k_1,k_2,\ldots,k_M$ holds.
Furthermore, we introduce:
\begin{equation}
\subtrees_\ell(A(d,d')) \defined 
	\left\{
	E
	\left|
	\begin{array}{l}
	A(d,d')@\rho_1(d_0,d_1)\rho_2(d_1,d_2)
		\cdots\rho_M(d_{M-1},d_M)\in\wfst_\ell,\\
	E=\{\rho_m(d_{m-1},d_m)\mid m=1\ldots M\}\\
	\q\q\q\q\cup\;\{A\dto\rho_1\rho_2\cdots\rho_M\},\q d=d_0,\;d'=d_M
	\end{array}
	\right.
	\right\}.
\end{equation}
$\wfst_\ell$ is a set of parent-children pairs of subtrees 
in the parse trees of $\win_\ell$.  We also define
$V_\ell$ as a set of subtree labels in the parse trees of
$\win_\ell$.
$O_\ell$ is an ordered set of members in $V_\ell$,
totally ordered satisfying the partial order
$@$ in $\wfst_\ell$.  The first element $\tau_1$
of $O_\ell$ is always $S(0,n_\ell)$.  $\subtrees_\ell$ represents
a logical relationship among subtrees and production rules.
For example, we interpret
\[
\subtrees_\ell(A(d,d'))=
	\bigl\{
		\{A\dto B_1 C_1,\;B_1(d,d''_1),\;C_1(d''_1,d')\},\;
		\{A\dto B_2 C_2,\;B_2(d,d''_2),\;C_2(d''_2,d')\}
        \bigr\},
\]
as the following statement:
\begin{quote}
To build up a subtree $A(d,d')$ for a sentence $\win_\ell$, there are
{\em only} two ways.  In the first way, we apply a rule $A\dto B_1 C_1$
and build subtrees $B_1(d,d''_1)$ and $C_1(d''_1,d')$.
In the second way, we apply a rule $A\dto B_2 C_2$ and build subtrees
$B_2(d,d''_2)$ and $C_2(d''_2,d')$.
\end{quote}
$O_\ell$ and $\subtrees_\ell$ jointly constitute a support graph
described in the next subsection.

Figure~\ref{fig:parse-tree-ichiro-CNF} shows two
parse trees $t1$ and $t2$ of a sentence
$\win_\ell=\tuple{急いで,走る,一郎,を,見た}$ given a CFG $G1$
in Figure~\ref{gram:ichiro-CNF}.  Let $\rseq_1$ and $\rseq_2$
be the corresponding rule applications, respectively.
Then, we have $\trees(\win_\ell)=\{\rseq_1, \rseq_2\}$, and
$\wfst_\ell$ is obtained as follows:
\pagebreak
{\small
\begin{align*}
	\wfst_\ell & = \wfst(\rseq_1)\cup\wfst(\rseq_2)\\
		&=\{\;\sym{S}(0,5)@\sym{PP}(0,4)\sym{V}(4,5),\;
			\sym{PP}(0,4)@\sym{NP}(0,3)\sym{P}(3,4),\;
			\sym{NP}(0,3)@\sym{VP}(0,2)\sym{N}(2,3),\\
		&\qquad \sym{VP}(0,2)@\sym{ADV}(0,1)\sym{V}(1,2),\;
			\sym{V}(4,5)@\sym{見た}(4,5),\;
			\sym{P}(3,4)@\sym{を}(3,4),\;
			\sym{N}(2,3)@\sym{一郎}(2,3),\\
		&\qquad \sym{V}(1,2)@\sym{走る}(1,2),\;
			\sym{ADV}(0,1)@\sym{急いで}(0,1)\;\}\\
		&\quad \cup 
		\{\;\sym{S}(0,5)@\sym{ADV}(0,1)\sym{VP}(1,5),\;
			\sym{ADV}(0,1)@\sym{急いで}(0,1),\;
			\sym{VP}(1,5)@\sym{PP}(1,4)\sym{V}(4,5),\\
		&\qquad \quad \sym{PP}(1,4)@\sym{NP}(1,3)\sym{P}(3,4),\;
			\sym{NP}(1,3)@\sym{V}(1,2)\sym{N}(2,3),\;
			\sym{V}(1,2)@\sym{走る}(1,2),\\
		& \qquad \quad \sym{N}(2,3)@\sym{一郎}(2,3),\;
			\sym{P}(3,4)@\sym{を}(3,4),\;
			\sym{V}(4,5)@\sym{見た}(4,5)\;\}
\end{align*}
}
$O_\ell$ is not determined uniquely in general, but it
is certain that $\sym{S}(0,5)$ is the first element.
For example, we have:
{\small
\begin{align*}
 O_\ell & =
	\langle
	\sym{S}(0,5),
	\sym{VP}(1,5),
	\sym{PP}(1,4),
	\sym{NP}(1,3),
	\sym{V}(4,5),
	\sym{PP}(0,4),
	\sym{P}(3,4),
	\\
 & \quad \sym{NP}(0,3),
	\sym{N}(2,3),
	\sym{VP}(0,2),
	\sym{V}(1,2),
	\sym{ADV}(0,1)
	\rangle.
\end{align*}
}
We also show $\subtrees_\ell$ according to the order of $O_\ell$:
{\small
\[
\begin{array}{lll|lll}
\subtrees_\ell(\sym{S}(0,5))&=&
		\{\;
		\{\sym{S}\dto\sym{PP}\;\sym{V},\;
					\sym{PP}(0,4),\;\sym{V}(4,5)\},&
	\subtrees_\ell(\sym{NP}(0,3))&=&
		\{\;\{\sym{NP}\dto\sym{VP}\;\sym{N},\\
&&\q\{\sym{S}\dto\sym{ADV}\;\sym{VP},\;
		\sym{ADV}(0,1),\;\sym{VP}(1,5)\}\;\}&
	&&\q\sym{VP}(0,2),\;\sym{N}(2,3)\}\;\}\\
\subtrees_\ell(\sym{VP}(1,5))&=&
		\{\;\{\sym{VP}\dto\sym{PP}\;\sym{V},\;
				\sym{PP}(1,4),\;\sym{V}(4,5)\}\;\}&
	\subtrees_\ell(\sym{N}(2,3))&=&
		\{\;\{\sym{N}\dto\sym{一郎}\}\;\}\\
\subtrees_\ell(\sym{PP}(1,4))&=&
		\{\;\{\sym{PP}\dto\sym{NP}\;\sym{P},\;
				\sym{NP}(1,3),\;\sym{P}(3,4)\}\;\}&
	\subtrees_\ell(\sym{VP}(0,2))&=&
		\{\;\{\sym{VP}\dto\sym{ADV}\;\sym{V},\\
\subtrees_\ell(\sym{NP}(1,3))&=&
		\{\;\{\sym{NP}\dto\sym{V}\;\sym{N},\;
				\sym{NP}(1,2),\;\sym{N}(2,3)\}\;\}&
		&&\q\sym{ADV}(0,1),\;\sym{V}(1,2)\}\;\}\\
\subtrees_\ell(\sym{V}(4,5))&=&
		\{\;\{\sym{V}\dto\sym{見た}\}\;\}&
	\subtrees_\ell(\sym{V}(1,2))&=&
			\{\;\{\sym{V}\dto\sym{走る}\}\;\}\\
\subtrees_\ell(\sym{PP}(0,4))&=&
		\{\;\{\sym{PP}\dto\sym{NP}\;\sym{P},\;
				\sym{NP}(0,3),\;\sym{P}(3,4)\}\;\}&
	\subtrees_\ell(\sym{ADV}(0,1))&=&
		\{\;\{\sym{ADV}\dto\sym{急いで}\}\;\}.\\
\subtrees_\ell(\sym{P}(3,4))&=&
	\{\;\{\sym{P}\dto\sym{を}\}\;\}
\end{array}
\]
}


\subsection{Support graphs}
\label{sec:GEM:support-graph}

It would be easier to understand the gEM algorithm
if we represent the pair $\tuple{O_\ell,\subtrees_\ell}$
as a data structure called a support graph $\sg_\ell$.
Indeed, the word ``graphical'' in the name comes from this
viewpoint.  First, Figure~\ref{fig:support-graph-ichiro} (a) shows
the support graph that corresponds to the example of $O_\ell$
and $\subtrees_\ell$ in the last subsection.  A support graph
$\sg_\ell$ is a directed acyclic graph that has a structure similar
to a recursive transition network (RTN), and consists of disconnected
subgraphs $\subsg_\ell(\tau)\defined\tuple{\tau,\subtrees_\ell(\tau)}$,
where $\tau\in O_\ell$.
Each $\subsg_\ell(\tau)$ is called a {\em support subgraph} for $\tau$
and labeled by $\tau=A(d,d')$.  Each
$\subsg_\ell(\tau)$ has two special nodes---called the {\em starting node} and the {\em ending node}---labeled by {\sf start} and {\sf end} in Figure~\ref{fig:support-graph-ichiro},
respectively.
For each $E\in\subtrees_\ell(\tau)$, the starting node, the nodes
labeled by an element in $E$ (a rule $A\dto\zeta$ or a subtree $A(d,d')$),
and the ending node are connected in this order.  Note that
two or more nodes can have the same label.
The path from the starting node to the ending node is called
the {\em local path}, which is also referred to by $E$.
In a local path, the nodes labeled by a rule $A\dto\zeta$ are
called {\em basic nodes} and those labeled by a subtree $A(d,d')$
are called {\em intermediate nodes}.  These nodes are denoted by
$\bigcirc$ and \textcircled{$\circ$}, respectively,
as in Figure~\ref{fig:support-graph-ichiro}.
Support graphs have the following features:
\begin{enumerate}
\item
  We can conduct a {\em recursive traversal} over a support graph
  $\sg_\ell$, like the way over an RTN.
\item
  There are multiple ways of traversal that share some partial paths.
\item 
  For each $E\in\subtrees_\ell(\tau)$ in a support subgraph
  $\subsg_\ell(\tau)=\tuple{\tau,\subtrees(\tau)}$,
  $\tau@\tau'$ holds for every $\tau'=A(d,d')\in E$.
\item
  The numbers of basic and intermediate nodes in a local path
  are not predefined.
\end{enumerate}

\begin{figure}[t]
\begin{center}
\includegraphics{21-4ia10f9.eps}
\end{center}
\caption{Example of support graphs}
\label{fig:support-graph-ichiro}
\end{figure}

A recursive traversal, the first feature, is performed as follows.
We first start from the starting node of a
support subgraph $S(0,n_\ell)$ and visit the nodes one by one
along the direct edges.  When visiting an intermediate node
$\tau=A(d,d')$, we jump to the starting node of the support subgraph
labeled by $\tau$.  Next, when reaching the ending node of
the current support subgraph, we go back to the original node.
After repeating such recursive visits, the traversal finishes
when we reach the ending node of the support subgraph of $S(0,n_\ell)$.
In a branch at some node, we choose one of the possible
destinations.  If we collect the subtree labels of the
intermediate nodes visited during a traversal, we have a label set
that means one parse tree of the sentence $\win_\ell$.
Similarly, collecting the rule labels of the basic nodes visited,
where the nodes are ordered as in Figure~\ref{fig:support-graph-ichiro},
we have a sequence of rule applications $\rseq\in\trees(\win_\ell)$
in the leftmost derivation of $\win_\ell$.  By exhaustive traversals,
we can find all possible sequences of rule applications in
$\trees(\win_\ell)$.  The notion of recursive traversal is
used in justifying the gEM algorithm (Appendix~\ref{sec:GEM-validity}).
Here, we show an example of a recursive traversal
in Figure~\ref{fig:support-graph-ichiro}~(b), where the path
of the traversal is drawn as a dotted line.

The second feature above is obtained because, in a recursive traversal,
we may jump into the same support subgraph $\subsg_\ell(\tau)$ from
two or more intermediate nodes labeled with $\tau$.
This structure sharing compresses support graphs,
and accordingly, the gEM algorithm efficiently computes various
probability values.  For example, we jump into subgraph
$\subsg_\ell(\sym{V}(4,5))$ from the nodes labeled with
$\sym{V}(4,5)$ and marked with $\times$
in Figure~\ref{fig:support-graph-ichiro} (a).

The third feature is obvious from the assumption on underlying CFGs
that we have neither $\varepsilon$ rule nor cyclic production
$A\derivesplus A$, and from the definitions of $O_\ell$
and $\subtrees_\ell$.  In other words, if $\tau@\tau'$,
then the nodes in the support subgraph $\subsg_\ell(\tau')$
of $\tau'$ never refer to $\tau$.
Based on this, the gEM algorithm works in a generalized
dynamic programming fashion in computing the inside and outside
probabilities (Section~\ref{sec:PCFG:IO}).
Finally, the fourth feature shows the generality of
support graphs, which is fully exploited by the gEM algorithm.


\subsection{Extracting support graphs}
\label{sec:GEM:extract-support-graph}

We next explain how to extract a support graph from the WFST
held in the parser.  As mentioned before, $O_\ell$ is an ordered
set of members in $V_\ell$ such that the total order in
$O_\ell$ satisfies the partial order $@$ in the WFST
$\wfst_\ell$.  In general, a total order that satisfies
a given partial order can be found by topological sorting,
and thus we conduct topological sorting to obtain $O_\ell$ and 
pick up $\subtrees_\ell$ during sorting.
Figure~\ref{alg:extract-sg} (above) shows a routine
$\proc{Extract-CYK}$ for extracting support graphs
in this way.  $\proc{Extract-CYK}$ is rather general,
while its subroutine should be tailored for the WFSTs of
the parser in use.  Figure~\ref{alg:extract-sg} (below) shows
a subroutine $\proc{Visit-CYK}$ that runs over a triangular matrix
of the CYK parser.

For these routines, we first prepare a stack\footnote{
For stack operation, we prepare $\proc{ClearStack}(U)$, which
clears the stack $U$; $\proc{PushStack}(x,U)$, which pushes an object
$x$ into $U$; and $\proc{PopStack}(U)$, which returns the popped object
from $U$.
}
$U$ and a flag array $\varComp[\cdot]$ in a global area.
Then, we call $\proc{Visit-CYK}$ recursively to visit the subtrees
$A(d,d')$ from the top-right corner of the triangular matrix
(Line~\ref{list:preproc-CYK:call-visit} in $\proc{Extract-CYK}$).
After returning from all recursive calls, we push the current
subtree label into the stack $U$ (Line~\ref{list:visit-CYK:push} in
$\proc{Visit-CYK}$).
During recursive calls, we record $\subtrees_\ell$
as well (Lines~\ref{list:visit-CYK:add1} and \ref{list:visit-CYK:add2}
in $\proc{Visit-CYK}$).  Note that
we put traces into the flags $\varComp[\cdot]$ to avoid revisits
(Lines~\ref{list:visit-CYK:mark}, 
\ref{list:visit-CYK:recursion:begin}, and \ref{list:visit-CYK:recursion:end}
in $\proc{Visit-CYK}$).
Finally, $O_\ell$ is obtained by popping up the subtree labels from $U$
(Lines~\ref{list:preproc-CYK:pop:begin} and \ref{list:preproc-CYK:pop:end}
in $\proc{Extract-CYK}$).

The GLR parser does not require CNF for the underlying CFG;
hence, for packed shared forests, we
need to introduce a more general routine than $\proc{Visit-CYK}$.
However, the basic structure should be the same in that
we use a stack, a flag array for traces and recursive calls.
Finally, the routines for extracting support
graphs often resemble a routine for outputting or counting
full parse trees, often provided in the parser software,
and so such a built-in routine can be a base for implementation.

\begin{figure}[b]
\begin{center}
\includegraphics{21-4ia10f10.eps}
\end{center}
\caption{ Routines for extracting support graphs:\ $\proc{Extract-CYK}$ (above) and $\proc{Visit-CYK}$ (below)}
\label{alg:extract-sg}
\end{figure}


\subsection{Graphical EM algorithm}
\label{sec:GEM:GEM}

\begin{figure}[b]
\begin{center}
\includegraphics{21-4ia10f11.eps}
\end{center}
\caption{Main routine $\proc{Learn-PCFG}$ for training PCFGs}
\label{alg:learn-PCFG}
\end{figure}

The proposed method's main routine $\proc{Learn-PCFG}$
is presented in Figure~\ref{alg:learn-PCFG}.
We have described two subroutines $\proc{CYK-Parser}$ and
$\proc{Extract-CYK}$, and in this subsection, we present
$\proc{Graphical-EM}$, which implements the gEM algorithm.
Similar to the I-O algorithm, the central part of
the gEM algorithm is computing the inside and outside
probabilities.  The inside and outside
probabilities of each $\tau\in O_\ell$ are, respectively,
stored into the array variables $\varP[\ell,\tau]$ and $\varQ[\ell,\tau]$,
kept in support subgraph
$\subsg_\ell(\tau)=\tuple{\tau,\subtrees_\ell(\tau)}$.
$\subsg_\ell(\tau)$ has an array variable
$\varR[\ell,\tau,E]$ for each local path $E\in\subtrees_\ell(\tau)$.
We also have an array variable $\varON[A\dto\zeta]$ that
stores the expected rule count of each rule $A\dto\zeta$.
$\proc{Graphical-EM}$
has two subroutines:\ $\proc{Get-Inside-Probs}$, which computes
the inside probabilities, and $\proc{Get-Expectations}$, which
simultaneously computes the outside probabilities and
the expected rule counts.

$\proc{Graphical-EM}$ is shown in Figure~\ref{alg:GEM}.
In $\proc{Graphical-EM}$, we first initialize all parameters
(Line~\ref{list:gEM:init}).  Then, we iterate $\proc{Get-Inside-Probs}$,
$\proc{Get-Expectations}$ and re-estimation of parameters
in this order (Lines~\ref{list:gEM:update:begin} and \ref{list:gEM:update:end}).
After the convergence of log-likelihood $\lambda$ (Line~\ref{list:gEM:repeat:end}),
we consider the parameters $\theta$ at the moment as the trained ones
$\theta^{\ast}$.  The log-likelihood is computed using the generative
probability $P(\win_\ell)$ of $\win_\ell$ stored in $\varP[\ell,S(0,n_\ell)]$
(Lines~\ref{list:gEM:loglike:1} and \ref{list:gEM:loglike:2}).
Figure~\ref{alg:GEM-sub} shows two subroutines $\proc{Get-Inside-Probs}$
and $\proc{Get-Expectations}$.  Figure~\ref{fig:GEM-sub} illustrates
how these subroutines work over an example support graph.

\begin{figure}[b]
\begin{center}
\includegraphics{21-4ia10f12.eps}
\end{center}
\caption{Routine $\proc{Graphical-EM}$ for the gEM algorithm}
\label{alg:GEM}
\end{figure}

\begin{figure}[p]
\begin{center}
\includegraphics{21-4ia10f13.eps}
\end{center}
\caption{Two subroutines $\proc{Get-Inside-Probs}$ (above) and $\proc{Get-Expectations}$ (below)}
\label{alg:GEM-sub}
\end{figure}
\begin{figure}[p]
\begin{center}
\includegraphics{21-4ia10f14.eps}
\end{center}
\caption{Probability computation in $\proc{Get-Inside-Probs}$ (left) and $\proc{Get-Expectations}$ (right)}
\label{fig:GEM-sub}
\end{figure}

The inside probabilities $\varP[\ell,\tau]$ in
$\proc{Get-Inside-Probs}$ are computed from the last support subgraph
according to $O_\ell$.  For each local path $E\in\subtrees_\ell(\tau_k)$
in $\tau_k$'s support subgraph
$\subsg_\ell(\tau_k)=\tuple{\tau_k,\subtrees_\ell(\tau_k)}$
($k=1\ldots |O_\ell|$),
we compute the product of inside probabilities of the nodes in
the local path and store the product into $\varR[\ell,\tau_k,E]$
(Lines~\ref{list:get-ip:for-tau:begin} and \ref{list:get-ip:for-tau:end}
and Figure~\ref{fig:GEM-sub} (1)).
In computing the product, we multiply the parameter $\theta(A\dto\zeta)$
for a basic node $A\dto\zeta$ or the inside probability $\varP[\ell,\tau']$
for an intermediate node $\tau'$ (Figure~\ref{fig:GEM-sub} (2)).\footnote{
From the third feature of support graphs (Section~\ref{sec:GEM:support-graph}),
letting $\tau'=\tau_{k'}$, we always have $k<k'$.  Also note that
the computation of $\varP$ is conducted from the last support subgraph
according to $O_\ell$.  Then, it is obvious that $\varP[\ell,\tau']$
has already been computed when it is referred to.
}
Finally, we compute $\varP[\tau_k]$ by summing $\varR[\ell,\tau_k,E]$
(Line~\ref{list:get-ip:calc-P} and Figure~\ref{fig:GEM-sub} (3)).

On the other hand, inversely with $\proc{Get-Inside-Probs}$,
$\proc{Get-Expectations}$ starts from the first support subgraph
according to $O_\ell$.  In this routine, we first initialize
the array variables $\varQ$ and $\varON$.
In particular, regarding the outside probabilities $\varQ[\ell,\cdot]$,
we set one for $\tau_1=S(0,n_\ell)$, which is the first element
of $O_\ell$, and set zero for the others
(Lines~\ref{list:get-exp:init:s:1} and \ref{list:get-exp:init:s:2}).
Next, for each $k=1\ldots |O_\ell|$, we consider a local path $E$
in the support subgraph $\subsg_\ell(\tau_k)$ of $\tau_k$
(Line~\ref{list:get-exp:foreach-E}), and the subtree $\tau'\in E$
whose outside probability $\varQ$ is to be updated at
Line~\ref{list:get-exp:updateQ}.  Then, the product of
the {\em local} outside probability of $\tau'$ in $E$
(the product of inside probabilities of the nodes {\em other than}
$\tau'$) and the outside probability of $\tau_k$ (the parent of $\tau'$)
is accumulated into $\varQ[\ell,\tau']$ (Figure~\ref{fig:GEM-sub} (4)).\footnote{
Letting $\tau'=\tau_{k'}$, $k<k'$ always holds from the third
feature of support graphs, and so $\tau'$ appears after $\tau_k$
in the order $O_\ell$.  Inversely, in a support subgraph
$\subsg_\ell(\tau_{k''})$ where $k''=k\ldots |O_\ell|$,
$\varQ[\ell,\tau_k]$ will never be modified, and hence the
computation of $\varQ[\ell,\tau_k]$ in the right hand side of
the substitution at Line~\ref{list:get-exp:updateQ}
has been completed.
}
However, at Line~\ref{list:get-exp:updateON}, for
a basic node $A\dto\zeta$, the product of the probability
$\varR[\ell,\tau_k,E]$ of the local path $E$ and the outside
probability $\varQ[\ell,\tau_k]$ of the parent $\tau_k$, divided by
the generative probability $P(\win_\ell)$ of the sentence $\win_\ell$,\footnote{
As shown at Line~\ref{list:gEM:init} in $\proc{Graphical-EM}$,
we initialize $\theta$ so that $P(\win_\ell|\theta)>0$
holds for all $\ell=1\ldots N$.  So, after any re-estimations of
$\theta$ in the gEM algorithm, it never happens that $P(\win_\ell|\theta)=0$.
Since, as roughly proved in Appendix~\ref{sec:GEM-validity},
the expected rule counts $\eta[r]$ in the gEM algorithm and
    those in Fujisaki et~al.'s (1989) method (Eq.~\ref{eq:naive-eta3})
are always equal, this property can be proved inductively as follows.
First, suppose that $P(\win_\ell|\theta^{(m)})>0$ holds under
the parameters after the $m$-th re-estimation.
Then, there should exist some $\rseq\in\subtrees(\win_\ell)$
that satisfies $P(\rseq|\theta^{(m)})>0$.
Furthermore, for any rule $r\in\rseq$, $\eta[r]>0$ should hold
under $\theta^{(m)}$, from the fact that $\occ(r,\rseq)>0$
    and Eq.~\ref{eq:naive-eta3}.
This implies that the parameter $\theta^{(m+1)}(r)$ after
the next re-estimation is also positive, as seen from
Line~\ref{list:gEM:update:end} in $\proc{Graphical-EM}$.
Again, for $\rseq$ considered above, we have $P(\rseq|\theta^{(m+1)})>0$,
and consequently, $P(\win_\ell|\theta^{(m+1)})>0$.
Now, we summarize that
$P(\win_\ell|\theta^{(m)})>0\Rightarrow P(\win_\ell|\theta^{(m+1)})>0$,
and therefore, if we initialize the parameters as $\theta^{(0)}$ such that
$P(\win_\ell|\theta^{(0)})>0$, then $P(\win_\ell|\theta^{(m)})>0$
after the subsequent re-estimations ($m=1,2,\ldots$). [Q.E.D.]
To make sure that $P(\win_\ell|\theta)>0$
in practical cases, it suffices to choose $\theta$
s.t.\ $\theta(r)>0$ holds for every $r\in R$.
} 
is accumulated into $\varON[A\dto\zeta]$
(Figure~\ref{fig:GEM-sub} (5)).
After such asynchronous accumulations into $\varON[A\dto\zeta]$,
$\varON[A\dto\zeta]$ contains the expected rule count
of rule $A\dto\zeta$ when $\proc{Get-Expectations}$ terminates.
The computations in the gEM algorithm described above are
justified with the notion of recursive traversal over
support graphs (Section~\ref{sec:GEM:support-graph}).
Such a justification will be made in Appendix~\ref{sec:GEM-validity}.

In general, the EM algorithm is a hill-climbing algorithm
targeting the log-likelihood function, and hence, only guarantees
a local maximum likelihood estimate.  As a result, the
quality of the trained parameters depends heavily on
the initial parameters.
\shortciteA{Lari90} proposed to initialize the parameters using
trained hidden Markov models.
One simple solution for local optimality is to first repeat
the EM algorithm $h$ times with random initial parameters,
and then to pick up the parameters in convergence
at the highest log-likelihood as the best trained parameters.
In this paper, this method is called {\em random restarting}.


\subsection{Probabilistic parsing}
\label{sec:GEM:ML-tree}

Having trained the parameters, we can find the most likely
derivation
$\rseq^{\ast}_\ell\defined
\mathrm{argmax}_{{\rm all}\;\rseq}P(\rseq|\win_\ell)
\linebreak 
=
\mathrm{argmax}_{{\rm all}\;\rseq}P(\rseq,\win_\ell)=
\mathrm{argmax}_{\rseq\in\trees(\win_\ell)}P(\rseq)$
for each input sentence $\win_\ell$ in the test corpus.  We define
$t^{\ast}_\ell$ as the parse tree corresponding
to $\rseq^{\ast}_\ell$, and resolve the syntactic
ambiguity in $\win_\ell$ by $t^{\ast}_\ell$.
$|\trees(\win_\ell)|$ is still exponential here, so we aim
to find $t^{\ast}_\ell$ on the basis of support graphs.

\begin{figure}[b]
\begin{center}
\includegraphics{21-4ia10f15.eps}
\end{center}
\caption{Routine $\proc{Predict}$ for finding the most likely parse and its two subroutines}
\label{alg:predict}
\end{figure}

Figure~\ref{alg:predict} shows a routine $\proc{Predict}$
for finding $t^{\ast}_\ell$, and its subroutines
$\proc{Get-Max-Probs}$ and $\proc{Construct-Tree}$.\footnote{
In the original Japanese version of this paper,
$\proc{Predict}$ does not work correctly, since it uses
the inside probabilities computed by $\proc{Get-Inside-Probs}$.
} 
$\proc{Predict}$ takes as input the corpus
$\corpus=\tuple{\win_1,\win_2,\ldots,\win_N}$,
and for each sentence $\win_\ell$, it outputs a set
$\labels(t^{\ast}_\ell)$ of subtree labels
in the most likely parse tree.
In $\proc{Predict}$, we first run a parser, a routine for
extracting support graphs, and a subroutine $\proc{Get-Max-Probs}$
(Line~\ref{line:predict-tree:parser}).
$\proc{Get-Max-Probs}$ determines the most likely subtrees
fragmentarily in a dynamic programming fashion.  Another
subroutine, $\proc{Construct-Tree}$, is then called for
building the most likely, full parse tree from such fragmentary
parse information (Line~\ref{line:predict-tree:construct}).

Here, we describe further details.
$\proc{Get-Max-Probs}$ works similarly to $\proc{Get-Inside-Probs}$,
but has two differences.  First, to find the most likely
local paths, $\proc{Get-Max-Probs}$ uses the maximization operator
instead of the summation at Line~\ref{list:get-mp:calc-P},
i.e., the meanings of two array variables, $\varP$ and $\varR$,
have been changed.
The second difference is that $\proc{Get-Max-Probs}$
uses an additional array variable $\delta[\ell,\tau_k]$
for recording the most likely local path itself (Line~\ref{list:get-mp:record}).
$\proc{Construct-Tree}$ conducts a recursive traversal over
$\delta[\ell,\tau_k]$ and adds the subtree labels $A(d,d')$
in the most likely local path $\delta[\ell,\tau]$ into
$\labels^{\ast}_\ell$ (Line~\ref{line:const-pred-tree:add}).
This process corresponds to building the most likely parse tree.
If we extend $\delta[\ell,\tau]$ to contain two or more
candidate local paths, we would have top-$n$ most likely
parse trees.


\subsection{Complexity}
\label{sec:GEM:complexity}

As stated before, since the number of iterations depends on
the initial parameters, we evaluate the complexity of
the I-O algorithm with that of one iteration.  This is exactly
the complexity inside the {\bf repeat} loop in $\proc{Graphical-EM}$.
First, let $O_\ell=\tuple{\tau_1^{(\ell)},
	\tau_2^{(\ell)},\ldots,\tau^{(\ell)}_{|O_\ell|}}$ for
each $\ell=1\ldots N$.  Note that, in the routine
$\proc{Get-Inside-Probs}$ called from $\proc{Graphical-EM}$,
we visit each element in $\subtrees_\ell(\tau_k^{(\ell)})$
once for all $k=1\ldots|O_\ell|$.
Then, the complexity of $\proc{Get-Inside-Probs}$ is evaluated
as $O(\mu_{\rm num}\mu_{\rm maxsize}N)$, where:
\begin{align}
\mu_{\rm num} & \defined
	\max_{\ell=1\ldots N}
		\sum_{k=1}^{|O_\ell|}\big|\subtrees_\ell(\tau_k^{(\ell)})\big|,
	\label{eq:xi-num}\\
\mu_{\rm maxsize} & \defined
	\max_{E:\;\ell=1\ldots N,\;k=1\ldots|O_\ell|,\;
			E\in\subtrees_\ell(\tau_k^{(\ell)})}
		|E|.
	\label{eq:xi-maxsize}
\end{align}
Similarly we see that $\proc{Get-Expectations}$ requires
$O(\mu_{\rm num}\mu_{\rm maxsize}N)$~time.

Let $L$ be the maximum sentence
length in a training corpus $\corpus$, and consider a set
$\Vn$ of nonterminals and a set $\Vt$ of terminals.
Here, we evaluate the worst-case complexity with the maximum
grammar $\Rmax$ (Eq.~\ref{eq:Rmax}) in CNF.
For such a grammar, we have
\begin{equation}
\subtrees_\ell(A(d,d'))=
	\bigl\{\{A\dto BC,\;B(d,d''),\;C(d'',d')\}\;\big|\;
		B,C\in \Vn,\;d<d''<d'\bigr\}
\label{eq:possible-psi}
\end{equation}
for all $A$, $d$ and $d'$, such that $A\in\Vn$, $0\le d, d'\le L$
and $d+2\le d'$ (the case with $d'=d+1$ is ignorable).  Then, since
$|O_\ell|=\bigl|\{A(d,d')\mid A\in\Vn,\;0\le d<d'\le L\}\bigr|
=O(|\Vn|L^2)$ and $\big|\subtrees_\ell(\tau)\big|=O(|\Vn|^2 L)$
hold, $\mu_{\rm num}=O(|\Vn|^3 L^3)$ from the definition
in Eq.~\ref{eq:xi-num}.  Also from the definition
in Eq.~\ref{eq:xi-maxsize}, $\mu_{\rm maxsize}=3=O(1)$.
The complexity of parameter re-estimation is $O(|\Rmax|)=O(|\Vn|^3)$,
which is ignorable.
From the discussion above, the complexity of the gEM algorithm
is $O(|\Vn|^3 L^3 N)$, i.e., the same as that of the I-O algorithm.

With a grammar in CNF, the worst-case
complexity of the CYK parser ($\proc{CYK-Parser}$) and
the routine for extracting support graphs ($\proc{Extract-CYK}$)
is $O(|\Vn|^3 L^3 N)$, which is the same as that of one EM iteration.
However, note that the EM algorithm usually iterates
for a few dozens or hundreds of times,
so the computation time of these routines is often ignorable
in the entire training process.  Similarly, assuming CNF, the complexity
of computing the generative probability or probabilistic parsing
for a sentence is $O(|\Vn|^3L^3)$ ($N=1$).  For the parsers
(e.g., CYK and GLR) that use WFSTs with parent-children pairs
of the form in Eq.~\ref{eq:parent-children}, we have the same 
support graphs $\tuple{O_\ell,\subtrees_\ell}$ and the same
complexity.  We evaluate the case with the Earley parser
in Appendix~\ref{sec:Stolcke}.


\section{Experiments on training time}
\label{sec:experiment}

To show Advantage~2 of our proposal, that it can run
significantly faster than the I-O algorithm with a practical
CFG, we measured the training time for the ATR dialogue corpus (SLDB).
The underlying CFG is a modified version of a Japanese grammar
$\Gtanaka$ by \citeA{Tanaka97}, which was originally hand-crafted
for speech recognition.
The modified grammar has 860 rules, and according to this
modified version, the corpus was also modified.
$\Gtanaka$ is a CFG whose terminal symbols are fine-grained
parts of speech, and has 173 nonterminals and 441 terminals.
The average, the minimum, and the maximum
sentence length in the corpus are 9.97, 2, and 49,
respectively.  Since the rule set $\Rtanaka$ in $\Gtanaka$
is not in CNF, we used a GLR parser
in the proposed method.\footnote{
More specifically, we cascaded the routine for extracting
support graphs and the routine for the gEM algorithm into
the MSLR (Morphological and Syntactic LR), which was available
from the Tanaka-Tokunaga Laboratory at Tokyo Institute of Technology
(http://tanaka-www.cs.titech.ac.jp/pub/mslr/).
Although the MSLR parser can perform morphological analysis
and syntactic analysis simultaneously, we used only the
syntactic analysis part.  Including the MSLR parser, the programs
used in the experiments are written in C language.
We used gcc 2.8.1 as a C compiler.  The CPU and OS of the computer
we used were Sun UltraSPARC-II 296 MHz and Solaris 2.6, respectively.
} 
However, since the I-O algorithm only works with
CFGs in CNF, we transformed $\Gtanaka$ into $\Gchom$ in CNF,
which has 2,308 rules, 210 nonterminals, and 441 terminals.

In our experiments, we compare the training time between
the proposed method and the I-O algorithm, given $\Gtanaka$
as an underlying CFG.  The I-O algorithm is the one described
in Section~\ref{sec:PCFG:IO}, and uses rule set $\Rchom$
in $\Gchom$ instead of $\Rmax$ (Eq.~\ref{eq:Rmax}).\footnote{
Of course, the I-O algorithm using $\Rchom$ runs faster
than the one using $\Rmax$, because of the additional constraint from
the grammar (e.g., it narrows the range of the outer summation
at Line~\ref{list:get-beta:calc-beta} in $\proc{Get-Beta}$).
} 
We measured the time consumed for a re-estimation of the parameters
(called the {\em re-estimation time}),
varying the sentence length $L$.
For this, we first gathered the sentences of lengths $L-1$ and $L$
into a group ($L=2,4,\ldots 26$), and from each group, we randomly
picked up 100 sentences as $\corpus_L$.\footnote{
In the experiments, to obtain stable statistics, we did not use
176 sentences that were longer than 26, which account for 1.6\%
in the corpus.
}
Then, for each $\corpus_L$ being treated as a training corpus,
we measured the re-estimation time.

Figure~\ref{graph:1} (left) shows the measurement results.
The y-axis indicates the average re-estimation time in seconds and
$L$ in the x-axis corresponds to the training corpus $\corpus_L$.
The curve ``{\it Inside-Outside}'' indicates the re-estimation
time in the I-O algorithm, and ``{\it IO with pruning}''
indicates the re-estimation time in a pruning-embedded
(or, in short, pruning) version of the I-O algorithm, which is
presented by \shortciteA{Kita99}.
This modified version is more efficient than the original,
in that it skips redundant zero-probability computations
in computing outside probabilities.  Finally, ``{\it Graphical EM}''
indicates the re-estimation time in the gEM algorithm.
To make the graph shapes readable, we magnify and
minify the scale of the y-axis of Figure~\ref{graph:1} (left)
as shown in Figure~\ref{graph:1} (center) and Figure~\ref{graph:1}
(right), respectively.

\begin{figure}[b]
\begin{center}
\includegraphics{21-4ia10f16.eps}
\end{center}
\caption{Re-estimation time (in seconds) in comparison}
\label{graph:1}
\end{figure}

As shown in Figure~\ref{graph:1} (left), the gEM algorithm runs
significantly faster than the I-O algorithm and its pruning version.
In addition, Figure~\ref{graph:1} (center) indicates that
the re-estimation time in the I-O algorithm draws
a cubic curve w.r.t.\ the sentence length $L$, as the theory
indicates.  The pruning version certainly runs
faster than the original but only in quadratic time
at best, since it still unconditionally scans all elements
in the triangular matrix.  Noting that we need to repeat
re-estimations several hundred times and conduct random restarts,
it is not practical to run the I-O algorithm or its pruning
version until convergence for the training corpora $\corpus_L$
where $L>20$.

In Contrast, as shown in Fig~\ref{graph:1} (right),
the proposed method runs almost in linear time in sentence length
$L$, where $L=2,4,\ldots, 26$.  This significant gap from the
worst-case complexity $O(|\Vn|^3 L^3)$ seems to be brought
by the grammatical constraints that greatly reduce the ambiguity
of the input sentences, or more specifically, the number of
subtrees stored in the WFSTs.  At sentence length $L=10$,
which is close to the average 9.97 in the ATR dialogue corpus,
the proposed method runs about one thousand times faster than
the I-O algorithm
(about seven hundred times faster than the pruning version).

When we use the random restarting method (Section~\ref{sec:GEM:GEM})
to obtain better parameters w.r.t.\ the log-likelihood, the entire
training time is broken down as follows:
\begin{align*}
(\mbox{Entire training time}) & = 
	(\mbox{Parsing time})\\
  & \quad + (\mbox{Time spent on extracting support graphs})\\
  & \quad + (\mbox{Time spent on the gEM algorithm}),\\
(\mbox{Time spent on the gEM algorithm}) & = 
	(\mbox{Re-estimation time})\\
  & \quad \times (\mbox{Number of re-estimations until convergence})\\
  & \quad \times(\mbox{Number $h$ of random restarts}).
\end{align*}
Using the length-wise training corpora $\corpus_L$ ($L=2,4,\ldots,26$)
described before, we measured the breakdowns of training time
(the parsing time, the time spent on extracting support graphs and
the time spent on the gEM algorithm), and the results are shown
in Figure~\ref{graph:2}.  The x-axis and the y-axis respectively
indicate the sentence length $L$ and the consumption time in seconds.
Also Figure~\ref{graph:2} (left) shows the case without restarts
(i.e., $h=1$) and Figure~\ref{graph:2} (right) shows the case with
10 restarts ($h=10$).  We fixed the number of re-estimations
until convergence as 100 because it varies depending on the corpus
$\corpus_L$.  The parsing time (``{\it Parsing}''), the time spent
for extracting support graphs (``{\it Support graph}'') and
the time spent on the gEM algorithm (``{\it Graphical EM}'') are
almost linear in sentence length $L$.
Figure~\ref{graph:2} (right) also indicates that,
when introducing random restarts, the parsing time and
the time spent on support-graph extraction are ignorable
in the entire training time, as we do not have
to repeat parsing and support-graph extraction in random restarts.
So these two steps can be seen as a small preprocessing
that yields a significant speed up of training, and in this way,
we enjoy the merit of separating the entire training process
into parsing and EM learning.

\begin{figure}[t]
\begin{center}
\includegraphics{21-4ia10f17.eps}
\end{center}
\caption{Breakdowns of training time:\ without restarts (left) and with 10 restarts (right)}
\label{graph:2}
\end{figure}


\section{EM learning of the extensions of PCFGs}
\label{sec:extensions}

So far, there have been several proposals that incorporate
context-sensitivity into PCFGs.  However, except for
Charniak and Carroll's \citeyear{Charniak94b}
pseudo probabilistic context-sensitive grammars,
no EM algorithms have been presented
for such extensions of PCFGs.  In this section, to show
Advantage~3 of the proposed method that it covers
polynomial-time EM algorithms for various extensions of
PCFGs, we select Kita et~al.'s \citeyear{Kita94}
rule bigram models and present their polynomial-time EM algorithm.


\subsection{The rule bigram models}
\label{sec:extensions:RB}

First, we concentrate on leftmost derivations
as in the case with PCFGs.  Then, relaxing the assumption
in PCFGs that production rules are chosen totally independently,
we assume that rules are chosen depending on the one
at the last choice.  By this relaxation, we can add some
context-sensitivity, which is not covered by PCFGs, into
the rule bigram models.  Under this assumption, the generative
probability of rule applications $\rseq$ is computed as
\begin{equation}
P(\rseq)=\theta(r_1\mid\#)\prod_{k=2}^K \theta(r_k\mid r_{k-1}).
\end{equation}
Here, \# is the marker that indicates a sentence boundary, and
$\theta(r\mid r')$ is a parameter associated with each rule
$r\in R$ ($r'\in R\cup\{\#\}$), in which
$\sum_{\zeta:(A\to\zeta)\in R}\theta(A\dto\zeta\mid r)=1$ holds
for $A\in\Vn$ and $r\in R\cup\{\#\}$.
In \shortciteA{Kita94}, given an unbracketed corpus
$\corpus=\tuple{\win_1,\ldots,\win_N}$,
a parameter $\theta(r_k|r_{k-1})$ is re-estimated as
\begin{equation}
\theta^{(m+1)}(r_k|r_{k-1}):=
	\left(
		{\displaystyle
		\sum_{\ell=1}^N
			\frac{
				\sum_{\rseq\in\trees(\win_\ell)}
					\occ(r_{k-1},r_k; \rseq)
			}{\displaystyle
				|\trees(\win_\ell)|}
		}
	\right)
	\left/
	\left(
	{\displaystyle
		\sum_{\ell=1}^N
			\frac{
				\sum_{\rseq\in\trees(\win_\ell)}
					\occ(r_{k-1}; \rseq)
			}{\displaystyle
				|\trees(\win_\ell)|
			}
	}
	\right)
	\right..
\label{eq:kita}
\end{equation}
Here, for rule applications $\rseq$, $\occ(r,r';\rseq)$ indicates
the number of occurrences of $r'$ just after $r$ in $\rseq$.
From this definition,
$\sum_{r'\in R}\occ(r,r';\rseq)=\occ(r;\rseq)$ obviously holds.

However, similar to Eqs.~\ref{eq:update} and \ref{eq:naive-eta3}
and in light of the original definition \cite{Dempster77},
the formula for re-estimation is derived as follows ($m=1,2,\ldots$):
\begin{align}
 & \theta^{(m+1)}(r_k|r_{k-1}):=\nonumber\\
 & \quad \left(
		{\displaystyle
			\sum_{\ell=1}^N
			\frac{
				\sum_{\rseq\in\trees(\win_\ell)}
					P(\rseq|\theta^{(m)})\occ(r_{k-1},r_k; \rseq)
			}{P(\win_\ell|\theta^{(m)})}
		}
	\right)
	\left/
	\left(
	{\displaystyle
		\sum_{\ell=1}^N
			\frac{
				\sum_{\rseq\in\trees(\win_\ell)}
					P(\rseq|\theta^{(m)})
					\occ(r_{k-1}; \rseq)
			}{P(\win_\ell|\theta^{(m)})}
	}
	\right)
	\right..
\label{eq:kita:EM}
\end{align}
By the re-estimation in Eq.~\ref{eq:kita:EM}, we can achieve
(local) maximum likelihood estimation, but obviously
Eq.~\ref{eq:kita:EM} is not feasible,
as $|\trees(\win)|$ is generally exponential in $|\win|$.


\subsection{Graphical EM algorithm applied to the rule bigram models}
\label{sec:extensions:RB-GEM}

To derive a polynomial-time EM algorithm for the rule bigram models,
whose re-estimation is equivalent to Eq.~\ref{eq:kita:EM},
we exploit the generality of the proposed method.
Before moving further, we introduce some notations.
We first consider the leftmost derivation $\rseq$
of a sentence $\win$ as follows:
\begin{equation}
S\derivesstar\cdots\rderives{r}\win_{0,d}A\xi\rderives{r''}
	\win_{0,d}\zeta\xi\derivesstar
	\cdots\derivesstar\win_{0,d}\zeta'\xi
		\rderives{r'}\win_{0,d}\win_{d,d'}
			\xi(=\win_{0,d'}\xi)\derivesstar\win\q.
\label{eq:RB-derivation}
\end{equation}
In Eq.~\ref{eq:RB-derivation}, $r$ is the rule applied just
before $A$ is expanded, and $r'$ is the last rule applied
in a partial derivation $A\derivesstar\win_{d,d'}$.
Considering $r$ and $r'$ as the context,
the subtree that governs $\win_{d,d'}$ is labeled as $A(d,d'|r,r')$.
We refer to rule $r'$ by $\lastrule(A,d,d'; \rseq)$,
and rule $r''$, which is applied just after $r$,
by $\condrule{A}{\zeta}{r}$.  In the rule bigram models,
we choose $\condrule{A}{\zeta}{r}$ with probability
$\theta(A\dto\zeta|r)$.  We also define
$\lastrule(A,d,d'; \win)\defined
  \{\lastrule(A,d,d'; \rseq)\mid\rseq\in\trees(\win)\}$,
the set of the last applied rules in deriving
a subtree $A(d,d')$ while $\win$ is being generated.

Now, we present an EM algorithm where
the CYK parser is adopted in the proposed method.
In this case, no change is required
for the CYK parser.  Furthermore, since the basic control flow
of the gEM algorithm can remain the same,
the only part we need to work out is the routine
for extracting support graphs.  For example, we have
the following logical relation $\subtrees_\ell$
for $t2$ in Figure~\ref{fig:parse-tree-ichiro-CNF}:
\begin{align*}
 & \subtrees_\ell(\sym{VP}(1,5\mid
	\sym{ADV}\dto\sym{急いで},\;\sym{V}\dto\sym{見た}))=\\
 & \qquad \Bigl\{\;
	\bigl\{
		\condrule{\sym{VP}}{\sym{PP}\;\sym{V}}
			{\mbox{\footnotesize\tt ADV}\to 急いで}\;,\;
		\sym{PP}(1,4\mid
			\sym{VP}\dto\sym{PP}\;\sym{V},\;\sym{P}\dto\sym{を}),\;
		\sym{V}(4,5\mid
			\sym{P}\dto\sym{を},\;
			\sym{V}\dto\sym{見た})
	\bigr\}.
\;\Bigr\}	
\end{align*}
Here,
a subtree label $A(d,d')$ is literally specialized into $A(d,d'|r,r')$ by
a pair $\tuple{r,r'}$ where $r$ is the rule applied just before
the corresponding partial derivation $A\derivesstar\win_{d,d'}$ occurs,
and $r'$ is the last applied rule in the partial derivation.
In the proposed method, context-sensitivity is typically incorporated
by literal specialization of subtree labels, as above.

Figure~\ref{alg:extract-CYK-RB} and \ref{alg:visit-CYK-RB},
respectively, show the support-graph extraction routine
$\proc{Extract-CYK-RB}$
tailored for the rule bigram models, and its recursive subroutine
$\proc{Visit-CYK-RB}$.  The subroutine
$\proc{Visit-CYK-RB}(\ell,r,A,d,d')$ visits the subtree $A(d,d')$
in the parse tree of $\win_\ell$, and adds $\lastrule(A,d,d';\win_\ell)$
into a global array variable $\varLast[A(d,d')]$.\footnote{
  For simplicity, in Figure~\ref{alg:visit-CYK-RB}, we present
  a somewhat redundant version of $\proc{Visit-CYK-RB}$.
  That is, it recomputes $\varLast[A(d,d')]$ for the calls with
  different $r$'s.
} 
What remains is to modify the gEM algorithm slightly.
More specifically, we first replace
$A\dto\zeta$, $\theta(A\dto\zeta)$ and $\varON[A\dto\zeta]$
with $\condrule{A}{\zeta}{r}$, $\theta(A\dto\zeta|r)$ and
$\varON[A\dto\zeta|r]$, respectively.
Then we wrap the \rw{foreach} loops at
Lines~\ref{list:gEM:update:begin} and \ref{list:gEM:update:end}
in $\proc{Graphical-EM}$ and 
Line~\ref{list:get-exp:init:eta} in $\proc{Get-Expectations}$
by the ``\rw{foreach} $r\in R$'' loop.

Next, we evaluate the worst-case complexity of the EM algorithm
for the rule bigram models.  Considering $\Rmax$, the worse-case complexity
is $O(|\Vn|^{12} L^3 N)$.\footnote{
First, for all $A\in\Vn$, $\tuple{d,d'}$
such that $0\le d<d'\le L$ and $d+2 \le d'$,
and $r,r'\in R$ ,
we have the following support subgraph for $A(d,d'|r,r')$:
\[
\subtrees_\ell(A(d,d'|r,r'))=
	\left\{
		\bigl\{
		\condrule{A}{BC}{r},\;B(d,d''|A\dto BC, r''),\;C(d'',d'|r'',r')
		\bigr\}
	\;\left|
	\begin{array}{l}
	B,C\in \Vn,\;d<d''<d',\\
	r''\in\lastrule(B,d,d'')\subseteq R
	\end{array}
	\right.
	\right\},
\]
and $A(d,d'|r,r')$ appears in $O_\ell$ ($\ell=1\ldots N$).
Then, it is obvious that
$|\subtrees_\ell(\tau)|=O(|\Vn|^2 L |R|)$.
In addition, $O_\ell$ is an ordered set of the members in
a subset of
$\big\{A(d,d'|r,r')\;\big|\;
	A\in\Vn,\;0\le d < d'\le L,\;r,r'\in R\big\}$,
we have $|O_\ell|=O(|\Vn| L^2 |R|^2)$.  So by definition
we have
$\mu_{\rm num}=O(|\Vn|^3 L^3 |R|^3)$ and $\mu_{\rm maxsize}=O(1)$.
Finally, considering the case with $R=\Rmax$,
the worst-case complexity of the gEM algorithm is
$O(|\Vn|^3 L^3 |\Rmax|^3 N)=O(|\Vn|^{12} L^3 N)$.
} 
This computational order is quite large, but is still cubic
in sentence length $L$.  Furthermore, the significant gap
between the worst-case complexity and the
actual computation time shown in Section~\ref{sec:experiment} also
seems applicable to the rule bigram models.
Indeed, \citeA{Mori00} reported that,
with a hand-crafted CFG $\Gtanaka$ in Section~\ref{sec:experiment},
the proposed method for the rule bigram models only runs
about 1.5 times slower than that for PCFGs.

\begin{figure}[t]
\begin{center}
\includegraphics{21-4ia10f18.eps}
\end{center}
\caption{Support-graph extraction routine $\proc{Extract-CYK-RB}$ tailored for the rule bigram models}
\label{alg:extract-CYK-RB}
\end{figure}
\begin{figure}[t]
\begin{center}
\includegraphics{21-4ia10f19.eps}
\end{center}
\caption{Subroutine $\proc{Visit-CYK-RB}$}
\label{alg:visit-CYK-RB}
\end{figure}


\section{Related work}
\label{sec:related-work}

In the literature, several probabilistic parsers have been
proposed, e.g., Magerman and 
\linebreak
Marcus's \citeyear{Magerman91}
$\mathcal{P}$earl; its successor, Magerman and Weir's \citeyear{Magerman92}
$\mathcal{P}$icky; and Stolcke's \citeyear{Stolcke95}
probabilistic Earley parser.
However, most probabilistic parsers (except Stolcke's)
assume as input an underlying grammar $G$ together with
parameters $\theta$, and do not consider how to train
the parameters.

As EM training methods for PCFGs not in CNF,
Kupiec's \citeyear{Kupiec92} method and
Stolcke's probabilistic Earley parser have been proposed.
Kupiec's method first considers PCFGs as recursive transition networks,
and trains them on an extended trellis diagram.  Kupiec's method
and the I-O algorithm are similar in their top-down approach.
WFSTs exploited in the proposed method are essential and
well-known in CFG-based parsing methods, so the proposed method
seems conceptually simpler than Kupiec's method, which uses
an extended trellis diagram.
For PCFGs with neither $\varepsilon$ rule nor cyclic production
$A\derivesplus A$, Stolcke's (1995) method is equivalent to the proposed
method, in which the Earley parser and the gEM algorithm are
cascaded (Appendix~\ref{sec:Stolcke}).
Therefore, for such PCFGs, the proposed method is a generalization
of Stolcke's method.  In addition, Stolcke did not mention any
training method for extensions of PCFGs.
It is an interesting future work
to extend it to work for PCFGs with $\varepsilon$ rules,
cyclic productions, or both.

\citeA{Pereira92} proposed a method that simultaneously
learns the structure and parameters of a grammar,
from a partially or fully bracketed corpus.
They also showed empirically that the quality of the grammar structure
and parameters learned by their method is significantly
improved compared to those learned from the corresponding
unbracketed corpus.  In the proposed method, it is possible
to train PCFGs from partially or fully bracketed corpora,
just by using a parser that outputs parse trees satisfying
the constraints from the brackets.\footnote{
The MSLR parser, which was used in our experiments (Section~\ref{sec:experiment}),
has such a functionality.
} 
This simplicity comes from a property whereby we only need the WFST
for EM learning.  The complexity of training PCFGs from
a fully bracketed corpus in the proposed method is $O(|\Vn|^3 L N)$,
which is the same as that of Pereira and Schabes's method.\footnote{
Pereira and Schabes only stated that the complexity is $O(L)$,
but it is immediately seen from their description of the algorithm
that it is $O(|\Vn|^3 L N)$ when using a rule set $\Rmax(\Vn,\Vt)$.
The complexity of the gEM algorithm with fully bracketed corpora
is evaluated as follows.
First, the size of the set $\brackets(\win_\ell)$ of brackets for
a sentence $\win_\ell$ is $O(|\win_\ell|)$, as Pereira and Schabes described.
Also note that the parse trees inconsistent with $\brackets(\win_\ell)$
cannot be the final parse trees, i.e., cannot be the members of $O_\ell$.
Then, for each $\ell=1\ldots N$, we have
$|O_\ell|=
	\left|\{A(d,d')\mid
			A\in\Vn\;\mbox{and}\;\tuple{d,d'}\in\brackets(\win_\ell)\}\right|
	=O(|\Vn|\cdot|\win_\ell|)=O(|\Vn|L)$.
Since the number of possible $d''$'s in Eq.~\ref{eq:possible-psi}
that are consistent with $\brackets(\win_\ell)$ is at most one,
$|\subtrees_\ell(A(d,d'))|=O(|\Vn|^2)$ holds for each $\ell=1\ldots N$.
Therefore, we have $\mu_{\rm num}=O(|\Vn|^3L)$ by definition
(Eq.~\ref{eq:xi-num}),
and also have $\mu_{\rm maxsize}=O(1)$ as discussed before.
Consequently, the complexity of re-estimation
in the gEM algorithm is $O(|\Vn|^3LN)$.
} 

In this paper, we have assumed that an underlying CFG is given.
However, automated learning of the grammar structure, or grammar induction,
is an important research topic, since it is quite costly
for a human to write precise grammars.  For instance,
given a set $\Vn$ of nonterminals and a set $\Vt$ of terminals,
Lari and Young proposed, first, to run the I-O algorithm with
the rule set $\Rmax(\Vn,\Vt)$, and second, to remove the rules
whose probabilities are sufficiently small \cite{Lari90}.
Pereira and Schabes's \citeyear{Pereira92} method,
which has been mentioned before, can also be understood as a method
for grammar induction from bracketed corpora.
One typical problem in such EM-based approaches is that they
only find a local maximum likelihood estimate, and hence the
quality of the learned grammar heavily depends on the initial parameters.
Against this problem of locality, there have been proposals
in training hidden Markov models (HMMs), such as
the successive state splitting (SSS) algorithm \cite{Takami93} and a structural learning method
based on model selection criteria \cite{Ikeda95}.
These methods separate the entire learning process into
two steps, training parameters and exploring the model structure,
and runs these two steps alternately.
When one extends these methods to the structural learning of PCFGs,
as a model (grammar) structure is given in the parameter training step,
the proposed method will effectively accelerate the learning.

The gEM algorithm was originally proposed by \citeA{Kameya00}
for a probabilistic logic programming language called PRISM \cite{Sato97}.
PRISM's semantic basis is the distribution semantics \cite{Sato95},
which is a probabilistic extension of the least model semantics
in logic programs.  The original proposal cascades
OLDT (Ordered Linear resolution for Definite clauses with Tabulation)
\cite{Tamaki86} and the gEM algorithm.  In this paper,
we replace OLDT by a CFG parser with a focus on training PCFGs and
their extensions.  
Although OLDT is a generic top-down search technique that is
applicable to parsing, the GLR parser runs faster for
practical grammars, thanks to pre-compilation
of CFGs into LR tables and its bottom-up search strategy.
In both cases, since the extracted support graphs are the same,
the time spent on the gEM algorithm is also the same.


\section{Conclusion}
\label{sec:conclusion}

In this paper, we proposed a generic method for training the
parameters in PCFGs from unbracketed corpora, under the assumption
that the underlying CFG is given.  The proposed method improves
the I-O algorithm on generality and efficiency
(with practical underlying CFGs) at the same time.

The proposed method separates the entire training process
into parsing and EM learning.  That is, it extracts
the parse information from the WFST stored in the parser
and exploits the extracted information, which is often compact,
in EM training.  Using this design, the proposed method overcomes
the efficiency of the I-O algorithm, which suffers
from its top-down nature.  Any technique that improves
parsing efficiency would accelerate the proposed method.

We implemented the proposed method and confirmed that,
given a hand-crafted Japanese grammar, it runs
significantly (one thousand times at the average sentence length)
faster than the I-O algorithm.  Based on the generality of
the proposed method, we also derived a polynomial-time EM
algorithm for CFGs with context-sensitive probabilities
(i.e., the rule bigram models) and showed that the proposed method
can cover previous methods such as Pereira and Schabes's (1992) method
and Stolcke's (1995) probabilistic Earley parsers.

In the future, we would like to conduct further experiments with
some extensions of PCFGs and work for grammar induction
using the proposed method.  Also, there is an interesting open
problem to derive an EM algorithm for the probabilistic
GLR model recently reformulated by \citeA{Inui98}.


\acknowledgment

A revised version of the ATR dialogue corpus and the Japanese grammar
used in the experiments were provided by the Tanaka-Tokunaga Laboratory
at Tokyo Institute of Technology.  We are deeply grateful for their
cooperation, and special thanks go to Kiyoaki Shirai
at the Tanaka-Tokunaga Laboratory for offering detailed information
on the corpus and the grammar, an auxiliary program for preprocessing,
and some key papers in the literature.
We also thank Nobuhisa Ueda for his insightful
comments from the early stage of the work.  The work is supported
in part by the Discovery Science project, promoted by Grant-in-Aid
for Scientific Research on Priority Areas~(A).


\bibliographystyle{jnlpbbl_1.5}
\begin{thebibliography}{}

\bibitem[\protect\BCAY{Baker}{Baker}{1979}]{Baker79}
Baker, J.~K. \BBOP 1979\BBCP.
\newblock \BBOQ Trainable Grammars for Speech Recognition.\BBCQ\
\newblock In {\Bem Proceedings of the Spring Conference of the Acoustical
  Society of America}, \mbox{\BPGS\ 547--550}.

\bibitem[\protect\BCAY{Charniak \BBA\ Carroll}{Charniak \BBA\
  Carroll}{1994}]{Charniak94b}
Charniak, E.\BBACOMMA\ \BBA\ Carroll, G. \BBOP 1994\BBCP.
\newblock \BBOQ Context-sensitive Statistics for Improved Grammatical Language
  Models.\BBCQ\
\newblock In {\Bem Proceedings of the 12th National Conference on Artificial
  Intelligence}, \mbox{\BPGS\ 728--733}.

\bibitem[\protect\BCAY{Chi \BBA\ Geman}{Chi \BBA\ Geman}{1998}]{Chi98}
Chi, Z.\BBACOMMA\ \BBA\ Geman, S. \BBOP 1998\BBCP.
\newblock \BBOQ Estimation of Probabilistic Context-free Grammars.\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 24}  (2), \mbox{\BPGS\
  299--305}.

\bibitem[\protect\BCAY{Dempster, Laird, \BBA\ Rubin}{Dempster
  et~al.}{1977}]{Dempster77}
Dempster, A.~P., Laird, N.~M., \BBA\ Rubin, D.~B. \BBOP 1977\BBCP.
\newblock \BBOQ Maximum Likelihood from Incomplete Data via the EM
  Algorithm.\BBCQ\
\newblock {\Bem Journal of Royal Statistical Society}, {\Bbf B39}  (1),
  \mbox{\BPGS\ 1--39}.

\bibitem[\protect\BCAY{Fujisaki, Jelinek, Cocke, Black, \BBA\ Nishino}{Fujisaki
  et~al.}{1989}]{Fujisaki89}
Fujisaki, T., Jelinek, F., Cocke, J., Black, E., \BBA\ Nishino, T. \BBOP
  1989\BBCP.
\newblock \BBOQ Probabilistic Parsing Method for Sentence Disambiguation.\BBCQ\
\newblock In {\Bem Proceedings of the 1st International Workshop on Parsing
  Technologies}, \mbox{\BPGS\ 85--94}.

\bibitem[\protect\BCAY{Ikeda}{Ikeda}{1995}]{Ikeda95}
Ikeda, S. \BBOP 1995\BBCP.
\newblock \BBOQ Construction of Phone HMM using Model Search Method.\BBCQ\
\newblock {\Bem IEICE Transactions D-II}, {\Bbf J78-D-II}  (1), \mbox{\BPGS\
  10--18}.
\newblock (in Japanese).

\bibitem[\protect\BCAY{Inui, Sornlertlemvanich, Tanaka, \BBA\ Tokunaga}{Inui
  et~al.}{1998}]{Inui98}
Inui, K., Sornlertlemvanich, V., Tanaka, H., \BBA\ Tokunaga, T. \BBOP
  1998\BBCP.
\newblock \BBOQ Probabilistic GLR Parsing: A New Formalization and Its Impact
  on Parsing Performance.\BBCQ\
\newblock {\Bem Journal of Natural Language Processing}, {\Bbf 5}  (3),
  \mbox{\BPGS\ 33--52}.

\bibitem[\protect\BCAY{Kameya \BBA\ Sato}{Kameya \BBA\ Sato}{2000}]{Kameya00}
Kameya, Y.\BBACOMMA\ \BBA\ Sato, T. \BBOP 2000\BBCP.
\newblock \BBOQ Efficient EM Learning with Tabulation for Parameterized Logic
  Programs.\BBCQ\
\newblock In {\Bem Proceedings of the 1st International Conference on
  Computational Logic}, \mbox{\BPGS\ 269--284}.

\bibitem[\protect\BCAY{Kita}{Kita}{1999}]{Kita99}
Kita, K. \BBOP 1999\BBCP.
\newblock {\Bem Kakuritu-teki Gengo Moderu (Probabilistic Language Models)}.
\newblock University of Tokyo Publishers.
\newblock (in Japanese).

\bibitem[\protect\BCAY{Kita, Morimoto, Ohkura, Sagayama, \BBA\ Yano}{Kita
  et~al.}{1994}]{Kita94}
Kita, K., Morimoto, T., Ohkura, K., Sagayama, S., \BBA\ Yano, Y. \BBOP
  1994\BBCP.
\newblock \BBOQ Spoken Sentence Recognition Based on HMM-LR with Hybrid
  Language Modeling.\BBCQ\
\newblock {\Bem IEICE Transactions on Information and Systems}, {\Bbf E77-D}
  (2), \mbox{\BPGS\ 258--265}.

\bibitem[\protect\BCAY{Kupiec}{Kupiec}{1992}]{Kupiec92}
Kupiec, J. \BBOP 1992\BBCP.
\newblock \BBOQ An Algorithm for Estimating the Parameters of Unrestricted
  Hidden Stochastic Context-free Grammars.\BBCQ\
\newblock In {\Bem Proceedings of the 14th International Conference on
  Computational Linguistics}, \mbox{\BPGS\ 387--393}.

\bibitem[\protect\BCAY{Lafferty}{Lafferty}{1993}]{Lafferty93}
Lafferty, J.~D. \BBOP 1993\BBCP.
\newblock \BBOQ A Derivation of the Inside-Outside Algorithm from the EM
  algorithm.\BBCQ\
\newblock In {\Bem IBM Research Report}. IBM T. J. Watson Research Center.

\bibitem[\protect\BCAY{Lari \BBA\ Young}{Lari \BBA\ Young}{1990}]{Lari90}
Lari, K.\BBACOMMA\ \BBA\ Young, S.~J. \BBOP 1990\BBCP.
\newblock \BBOQ The Estimation of Stochastic Context-free Grammars using the
  Inside-Outside Algorithm.\BBCQ\
\newblock {\Bem Computer Speech and Languages}, {\Bbf 4}  (1), \mbox{\BPGS\
  35--56}.

\bibitem[\protect\BCAY{Magerman \BBA\ Marcus}{Magerman \BBA\
  Marcus}{1991}]{Magerman91}
Magerman, D.\BBACOMMA\ \BBA\ Marcus, M. \BBOP 1991\BBCP.
\newblock \BBOQ $\mathcal{P}$earl: A Probabilistic Chart Parser.\BBCQ\
\newblock In {\Bem Proceedings of the 5th Conference on the European Chapter of
  the Association for Computational Linguistics}, \mbox{\BPGS\ 15--20}.

\bibitem[\protect\BCAY{Magerman \BBA\ Weir}{Magerman \BBA\
  Weir}{1992}]{Magerman92}
Magerman, D.\BBACOMMA\ \BBA\ Weir, C. \BBOP 1992\BBCP.
\newblock \BBOQ Efficiency, Robustness and Accuracy in $\mathcal{P}$icky Chart
  Parsing.\BBCQ\
\newblock In {\Bem Proceedings of the 30th Annual Meeting of the Association
  for Computational Linguistics}, \mbox{\BPGS\ 40--47}.

\bibitem[\protect\BCAY{Mori, Kameya, \BBA\ Sato}{Mori et~al.}{2000}]{Mori00}
Mori, T., Kameya, Y., \BBA\ Sato, T. \BBOP 2000\BBCP.
\newblock \BBOQ Efficient EM Learning of Probabilistic CFGs and their
  Extentions.\BBCQ\
\newblock In {\Bem Information Processing Society of Japan, SIG-NL 139-12},
  \mbox{\BPGS\ 85--92}.
\newblock (in Japanese).

\bibitem[\protect\BCAY{Nagata}{Nagata}{1999}]{Nagata99}
Nagata, M. \BBOP 1999\BBCP.
\newblock \BBOQ Keitai-so, Koubun Kaiseki (Morphological and Syntactic
  Analysis).\BBCQ\
\newblock In Tanaka, H.\BED, {\Bem Shizen Gengo Shori: Kiso to Oyo (Natural
  Language Processing: Foundations and Applications)}, \BCH~1, \mbox{\BPGS\
  2--45}. Institute of Electronics, Information and Communication Engineers.
\newblock (in Japanese).

\bibitem[\protect\BCAY{Pereira \BBA\ Schabes}{Pereira \BBA\
  Schabes}{1992}]{Pereira92}
Pereira, F.\BBACOMMA\ \BBA\ Schabes, Y. \BBOP 1992\BBCP.
\newblock \BBOQ Inside-Outside Reestimation from Partially Bracketed
  Corpora.\BBCQ\
\newblock In {\Bem Proceedings of the 30th Annual Meeting of the Association
  for Computational Linguistics}, \mbox{\BPGS\ 128--135}.

\bibitem[\protect\BCAY{Sato}{Sato}{1995}]{Sato95}
Sato, T. \BBOP 1995\BBCP.
\newblock \BBOQ A Statistical Learning Method for Logic Programs with
  Distribution Semantics.\BBCQ\
\newblock In {\Bem Proceedings of the 12th International Conference on Logic
  Programming}, \mbox{\BPGS\ 715--729}.

\bibitem[\protect\BCAY{Sato \BBA\ Kameya}{Sato \BBA\ Kameya}{1997}]{Sato97}
Sato, T.\BBACOMMA\ \BBA\ Kameya, Y. \BBOP 1997\BBCP.
\newblock \BBOQ PRISM: a Symbolic-statistical Modeling Language.\BBCQ\
\newblock In {\Bem Proceedings of the International Joint Conference on
  Artificial Intelligence}, \mbox{\BPGS\ 1330--1335}.

\bibitem[\protect\BCAY{Stolcke}{Stolcke}{1995}]{Stolcke95}
Stolcke, A. \BBOP 1995\BBCP.
\newblock \BBOQ An Efficient Probabilistic Context-free Parsing Algorithm that
  Computes Prefix Probabilities.\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 21}  (2), \mbox{\BPGS\
  165--201}.

\bibitem[\protect\BCAY{Takami \BBA\ Sagayama}{Takami \BBA\
  Sagayama}{1993}]{Takami93}
Takami, J.\BBACOMMA\ \BBA\ Sagayama, S. \BBOP 1993\BBCP.
\newblock \BBOQ Automatic Generation Hidden Markov Networks by a Successive
  State Splitting Algorithm.\BBCQ\
\newblock {\Bem IEICE Transactions D-II}, {\Bbf J76-D-II}  (10), \mbox{\BPGS\
  2155--2164}.
\newblock (in Japanese).

\bibitem[\protect\BCAY{Tamaki \BBA\ Sato}{Tamaki \BBA\ Sato}{1986}]{Tamaki86}
Tamaki, H.\BBACOMMA\ \BBA\ Sato, T. \BBOP 1986\BBCP.
\newblock \BBOQ OLD Resolution with Tabulation.\BBCQ\
\newblock In {\Bem Proceedings of the 3rd International Conference on Logic
  Programming}, \mbox{\BPGS\ 84--98}.

\bibitem[\protect\BCAY{Tanaka}{Tanaka}{1988}]{Tanaka88}
Tanaka, H. \BBOP 1988\BBCP.
\newblock {\Bem Shizen Gengo Kaiseki no Kiso (Fundamentals of Analysis of
  Natural Language)}.
\newblock Sangyo Tosho.
\newblock (in Japanese).

\bibitem[\protect\BCAY{Tanaka, Takezawa, \BBA\ Eto}{Tanaka
  et~al.}{1997}]{Tanaka97}
Tanaka, H., Takezawa, T., \BBA\ Eto, J. \BBOP 1997\BBCP.
\newblock \BBOQ Japanese Grammar for Speech Recognition Considering the MSLR
  Method.\BBCQ\
\newblock In {\Bem Information Processing Society of Japan, SIG-SLP 15--25},
  \mbox{\BPGS\ 145--150}.
\newblock (in Japanese).

\bibitem[\protect\BCAY{Tomita \BBA\ Ng}{Tomita \BBA\ Ng}{1991}]{Tomita91}
Tomita, M.\BBACOMMA\ \BBA\ Ng, S. \BBOP 1991\BBCP.
\newblock \BBOQ The Generalized LR Parsing Algorithm.\BBCQ\
\newblock In Tomita, M.\BED, {\Bem Generalized LR Parsing}. Kluwer Academic
  Publishers.

\end{thebibliography}


\appendix

\section{Justification of the graphical EM algorithm}
\label{sec:GEM-validity}

In this section, we roughly show that Fujisaki et~al.'s (1989) method,
the I-O algorithm and the gEM algorithm output the same
trained parameters, from the same initial parameters and
under the same convergence criterion.  For this purpose, we only
need to show that these three methods give the same expected
rule count $\eta[A\dto\zeta]$ for any rule $(A\dto\zeta)\in R$.
As seen in Section~\ref{sec:PCFG:IO-problems}, the expected
rule counts computed by Fujisaki et~al.'s method are equal
to those computed by the I-O algorithm, so it is sufficient to show that
the expected rule counts computed by the gEM algorithm
are equal to those computed by Fujisaki et~al.'s method.

First, we consider recursive traversal over
a support graph $\sg_\ell$,
which is described in Section~\ref{sec:GEM:support-graph}.
In what follows, the starting (resp.\ ending) node in
the subgraph of $\tau$ is called ``$\tau$'s starting (resp.\ ending) node.''
Now, we consider the traversals in which we collect the rule labels
associated with basic nodes, and focus on some basic node $v$
associated with $A\dto\zeta$ in a support graph $\sg_\ell$.
Also, suppose that $v$ is included in a subgraph of $\tau$,
and let $E$ be the local path in which $v$ appears.
This situation is depicted in Figure~\ref{fig:v-in-sg}.
Then, we consider all possible recursive traversals in which
we start from $S(0,n_\ell)$'s starting node and pass through $v$.
Note here that $S(0,n_\ell)$ is the first element of $O_\ell$.
We denote by $\trees(v,\win_\ell)$ the set of sequences of
the rule labels (rule applications) collected in such traversals
(obviously $\trees(v,\win_\ell)\subseteq\trees(\win_\ell)$).

\begin{figure}[b]
\begin{center}
\includegraphics{21-4ia10f20.eps}
\end{center}
\caption{Basic node $v$ associated with $A\dto\zeta$, appearing in a support graph $\sg_\ell$}
\label{fig:v-in-sg}
\end{figure}

We further introduce some notations.  Let $\rseq_1$ be the sequence
of the rule labels (partial rule applications) collected
in a partial recursive traversal from $\tau$'s starting node to
$\tau$'s ending node through the local path $E$ considered above.
Also let $\rseq_0$ be a sequence of the rule labels
collected in a partial traversal from $S(0,n_\ell)$'s starting
node to an intermediate node $u$ which is associated with $\tau$
(Figure~\ref{fig:v-in-sg}), and $\rseq_2$ be a sequence of
the rule labels collected in a partial traversal from $u$
to $S(0,n_\ell)$'s ending node.
Here, we let $\treesin(v,\win_\ell)=\{\rseq_1\}$ and obtain
the set $\treesout(v,\win_\ell)$ of possible pairs of $\rseq_0$
and $\rseq_2$ by varying $u$ above.
Then, $\trees(v,\win_\ell)$ defined above can be seen as
a Cartesian product of $\treesin(v,\win_\ell)$ and
$\treesout(v,\win_\ell)$.

From the definitions above and the independence assumption in PCFGs,
we have:
\begin{align*}
\textstyle
\sum_{\rseq'\in\trees(v,\win_\ell)}P(\rseq')
 & = \textstyle
	\sum_{\tuple{\rseq_0,\rseq_1,\rseq_2}\in\trees(v,\win_\ell)}
	P(\rseq_0,\rseq_1,\rseq_2)\\
 & = \textstyle
	\sum_{\rseq_1\in\treesin(v,\win_\ell)}
	\sum_{\tuple{\rseq_0,\rseq_2}\in\treesout(v,\win_\ell)}
	P(\rseq_1)P(\rseq_0,\rseq_2)\\
 & = \textstyle
	\left(
	\sum_{\rseq_1\in\treesin(v,\win_\ell)}
	P(\rseq_1)
	\right)
	\left(
	\sum_{\tuple{\rseq_0,\rseq_2}\in\treesout(v,\win_\ell)}
	P(\rseq_0,\rseq_2)
	\right)
\end{align*}
Examining recursively how $\varP$ and $\varR$ are computed
in the routine $\proc{Get-Inside-Probs}$, we see that
$\varR[\ell,\tau,E]=
\sum_{\rseq_1\in\treesin(v,\win_\ell)}P(\rseq_1)$.
Similarly, examining recursively how $\varQ$ is computed
in $\proc{Get-Expectations}$, it can be seen that
$\varQ[\ell,\tau]=
\sum_{\tuple{\rseq_0,\rseq_2}\in\treesout(v,\win_\ell)}
P(\rseq_0,\rseq_2)$.
As a result, we have
$\varQ[\ell,\tau]\cdot\varR[\ell,\tau,E]
=\sum_{\rseq'\in\trees(v,\win_\ell)}P(\rseq')$.
We then see that
the value accumulated into $\varON[A\dto\zeta]$ at Line~\ref{list:get-exp:updateON}
in $\proc{Get-Expectations}$ is equal to 
$\frac{1}{P(\win_\ell)}\sum_{\rseq'\in\trees(v,\win_\ell)}P(\rseq')$.

Disregarding the order of computations, the gEM substantially repeats
the computation above for each basic node $v$ associated with $A\dto\zeta$,
and for each support graph $\sg_\ell$ ($\ell=1\ldots N$).
The expected rule count $\varON[A\dto\zeta]$ is finally computed as:
\begin{equation}
\varON[A\dto\zeta]
=\sum_{\ell=1}^N
\frac{1}{P(\win_\ell)}
\sum_{v: \; A\to\zeta\; {\rm is\;attached}}\;
\sum_{\rseq'\in\trees(v,\win_\ell)}P(\rseq')\;.
\label{eq:naive-eta4}
\end{equation}

Now, let us consider a recursive traversal from $S(0,n_\ell)$'s
starting node, and let $\rseq$ be a sequence of the rule labels
(rule applications) collected in the traversal.
Then, the number of basic nodes
$A\dto\zeta$ we visit in the traversal is exactly
$\occ(A\dto\zeta,\rseq)$ in our notation.
So in the summation
$\sum_{v: \; A\to\zeta\; {\rm is\;attached}}\;
\sum_{\rseq'\in\trees(v,\win_\ell)}$,
a sequence $\rseq\in\trees(\win_\ell)$
of rule applications is taken into account
for $\occ(A\dto\zeta,\rseq)$ times.
This immediately implies that Eq.~\ref{eq:naive-eta4} is
    equivalent to Fujisaki et~al.'s formula (Eq.~\ref{eq:naive-eta3}).
From the discussions above, we can conclude that
Fujisaki et~al.'s method, the I-O algorithm, and the
gEM algorithm are equivalent to each other.


\section{Relation to Stolcke's probabilistic Earley parser}
\label{sec:Stolcke}

In this section, we roughly relate Stolcke's probabilistic
Earley parser~\cite{Stolcke95} and the proposed method when
the Earley parser and the gEM algorithm are cascaded.
First, we briefly describe the probabilistic Earley parser.\footnote{
  The description is based on Stolcke's notation
  with some exceptions to keep consistency with our notation.
} 


\subsection{Probabilistic Earley parser}
\label{sec:Stolcke:parser}

The Earley parser analyzes an input sentence $\win_\ell$
based on the set $I_\ell$ of items.
Each item is in the form $\es{d'}{d}{A\dto\zeta.\xi}$ and
indicates (i) $\win_{0,d'}^{(\ell)}=w_1^{(\ell)}\cdots w_{d'}^{(\ell)}$
has been analyzed,
(ii) the phrase governed by a nonterminal $A$ starts
from the position $d$,
(iii) $A$ is expanded by the rule $A\dto\zeta\xi$, and
analysis has been conducted until the point indicated by the dot symbol
on the right hand side.

Stolcke's (1995) probabilistic Earley parser is a natural extension of the
Earley parser, where each item $\es{d'}{d}{A\dto\zeta.\xi}$
is associated with its inside probability $\ip{d'}{d}{A\dto\zeta.\xi}$.\footnote{
  In addition to inside probabilities, \cite{Stolcke95} associates
  a probability called the forward probability with each item.
  In this paper, however, we omit forward probabilities since
  they have nothing to do with EM learning.
} 
From now on, we refer to such an item as $\esp{d'}{d}{A\dto\zeta.\xi}{\beta}$
(i.e., $\beta$ a shorthand of $\ip{d'}{d}{A\dto\zeta.\xi}$).
The inside probability $\ip{d'}{d}{A\dto\zeta.\xi}$ is
the sum of probabilities of the derivation paths
from an item $\es{d}{d}{A\dto.\zeta\xi}$ to another item
$\es{d'}{d}{A\dto\zeta.\xi}$~.
In the parser, the inside probabilities are computed by
three operations:
\begin{description}
\item[\textbf{$\diamond$ Prediction:}]
  If the current item set $I_\ell$ contains an item
  $\esp{d'}{d}{A\dto\zeta.B\xi}{\beta}$ and we have $(B\dto\nu)\in R$,
  then we add a new item $\esp{d'}{d'}{B\dto.\nu}{\beta'}$ into $I_\ell$
  unless it already exists.
  Here, we let $\beta'=\theta(B\dto\nu)$.
\item[\textbf{$\diamond$ Scanning:}]
  If the current item set $I_\ell$ contains an item
  $\esp{(d'-1)}{d}{A\dto\zeta.w_{d'}^{(\ell)}\xi}{\beta}$,
  then we add a new item $\esp{d'}{d}{A\dto\zeta w_{d'}^{(\ell)}.\xi}{\beta'}$
  into $I_\ell$ unless it already exists.
  Here, we let $\beta'=\beta$.
\item[\textbf{$\diamond$ Completion:}]
  If the current item set $I_\ell$ has two items
  $\esp{d'}{d''}{B\dto\nu.}{\beta''}$ and
  $\esp{d''}{d}{A\dto\zeta.B\xi}{\beta}$ such that $d''<d'$,\footnote{
    Stolcke's method allow the underlying CFG to have
    $\varepsilon$ rule and cyclic production $A\derivesplus A$.
    So in his description, the completion operation is also applicable
    to the case $d''=d'$.
  }
  then we add a new item $\esp{d'}{d}{A\dto\zeta B.\xi}{\beta'}$,
  where $\beta'=\beta\cdot\beta''$,
  into $I_\ell$ unless it already exists.
  If the new item already exists in $I_\ell$, we just increment
  $\beta'$ by $\beta\cdot\beta''$
  (i.e., $\beta'\;\incby\;\beta\cdot\beta''$).
\end{description}
In EM learning, we require the outside probability
$\op{d'}{d}{A\dto\zeta.\xi}$ for an item $\es{d'}{d}{A\dto\zeta.\xi}$~.
This probability is the sum of probabilities of the
paths where we
(i) start from the initial item $\es{0}{0}{\dto .S}$,
(ii) generate $\win_{0,d}^{(\ell)}$,
(iii) pass through ${}_{d} A\dto.\nu\xi$ for some $\nu$,
(iv) generate $\win_{d',n_\ell}^{(\ell)}$ starting from
${}_{d'}A\dto\nu.\xi$, and
(v) finish with $\es{n_\ell}{0}{\to S.}$~.
The outside probabilities are obtained by:
\begin{description}
\item[\textbf{$\diamond$ Reverse Completion:}]
For each pair
$\esp{d'}{d''}{B\dto\nu.}{\alpha'',\beta''}$
and $\esp{d''}{d}{A\dto\zeta.B\xi}{\alpha',\alpha'}$
in $I_\ell$, we find an item
$\esp{d'}{d}{A\dto\zeta B.\xi}{\alpha,\beta}$ in $I_\ell$
and make two increments:
$\alpha'\;\incby\;\beta''\cdot\alpha$ and
$\alpha''\;\incby\;\beta'\cdot\alpha$.
\end{description}
We initialize the outside probability as one
for the item $\es{n_\ell}{0}{S\dto\nu.}$, and as zero
for the other items.  After having computed
all inside and outside probabilities, we compute the expected
rule counts by Eq.~\ref{eq:update-Stolcke} and re-estimate the
parameters using Eq.~\ref{eq:update}, as with the I-O algorithm.
\begin{equation}
\varON[A\dto\zeta]=
\sum_{\ell=1}^N
\frac{1}{\ip{n_\ell}{0}{\to S.}}
\sum_{(d:{}_d {A\to.\zeta})\in I_\ell}
\op{d}{d}{A\dto.\zeta}\ip{d}{d}{A\dto.\zeta}
\label{eq:update-Stolcke}
\end{equation}


\subsection{Support graphs for the probabilistic Earley parser}
\label{sec:Stolcke:support-graph}

\begin{figure}[t]
\begin{center}
\includegraphics{21-4ia10f21.eps}
\end{center}
\caption{Support-graph extraction routine $\proc{Extract-Earley}()$ tailored for the Earley parser}
\label{alg:extract-Earley}
\end{figure}
\begin{figure}[t]
\begin{center}
\includegraphics{21-4ia10f22.eps}
\end{center}
\caption{Subroutine $\proc{Visit-Earley}$ of $\proc{Extract-Earley}$}
\label{alg:visit-Earley}
\vspace{-0.5\Cvs}
\end{figure}

To implement the probabilistic Earley parser, we replace
    $\proc{Extract-CYK}$ by \textsc{Extract-Earley}
(Figure~\ref{alg:extract-Earley}) in the main routine
(Figure~\ref{alg:learn-PCFG}). We also show the subroutine
$\proc{Visit-Earley}$ called from $\proc{Extract-Earley}$ in
Figure~\ref{alg:visit-Earley}.  In this case, we need not
modify the routines for the gEM algorithm.
Based on the routine for outputting the full parse trees,
$\proc{Extract-Earley}$ generates support graphs
$\sg_\ell=\tuple{O_\ell,\subtrees_\ell}$ ($\ell=1\ldots N$).
Each $\subtrees_\ell$ takes the following form:
\begin{align}
\subtrees_\ell(\es{d}{d}{B\dto.\nu}) & = \bigl\{\{B\dto\nu\}\bigr\},
	\label{eq:subtrees-earley:1}\\
\subtrees_\ell(\es{d'}{d}{A\dto\zeta w_{d'}^{(\ell)}.\xi}) & = 
			\bigl\{\{\es{(d'-1)}{d}{A\dto\zeta.w_{d'}^{(\ell)}\xi}\}\bigr\},
	\label{eq:subtrees-earley:2}\\
\subtrees_\ell(\es{d'}{d}{A\dto\zeta B.\xi}) & = 
				\Bigl\{
					\bigl\{
						(\es{d''}{d}{A\dto\zeta.B\xi}),\;
						(\es{d'}{d''}{B\dto\nu.})
					\bigr\}\nonumber\\
		& \qquad \Big|\;
					d\le d''< d',
					(\es{d'}{d''}{B\to\nu.})\in I_\ell
				\Bigr\}.
	\label{eq:subtrees-earley:3}
\end{align}

In the gEM algorithm, computing the inside probabilities
for a support subgraph in Eq.~\ref{eq:subtrees-earley:1} corresponds to
the Prediction operation in the probabilistic Earley parser.
Similarly, computing the inside probability for
Eq.~\ref{eq:subtrees-earley:2} corresponds to the Scanning operation,
and computing the inside (resp.\ outside) probability
for Eq.~\ref{eq:subtrees-earley:3} corresponds to the Completion
(resp.\ Reverse Completion) operation.  Last, computing the
expected rule counts for Eq.~\ref{eq:subtrees-earley:1}
corresponds to Eq.~\ref{eq:update-Stolcke}.

Now, we evaluate the complexity of the gEM algorithm for the support graphs
above.  Regarding time consumption, the computation related to the
support subgraphs in Eq.~\ref{eq:subtrees-earley:3} occupies
the largest part.  Given an underlying CFG in CNF,
the total number of nodes in such support subgraphs is obtained as
$O(|R|L^3)$ by considering all possible rules and word positions
($d$, $d'$, and $d''$), where $R$ is the rule set and $L$ is
the maximum sentence length.  When $R=\Rmax$,
the worse-case complexity of the gEM algorithm is $O(|\Vn|^3 L^3)$,
which is the same as that of the probabilistic Earley parser.

Here, we consider the case with an underlying CFG not in CNF,
and let $m$ be the maximum number of symbols on the right hand side of a rule.
Then, the complexity of the gEM algorithm cascaded after
a parser, e.g., the GLR parser, with WFSTs of the form
in Eq.~\ref{eq:parent-children} is $O(L^{m+1})$.
On the other hand, when cascaded after the Earley parser,
the complexity turns out to be $O(L^3)$, i.e., it does not depend on $m$.
However, the GLR parser has some advantages such as
pre-compilation of CFGs to LR tables and its bottom-up search strategy
over the Earley parser, and hence it seems worth choosing an
appropriate parser depending on the target grammar.


\begin{biography}

\bioauthor[:]{Yoshitaka Kameya}{
received his M.S. (1997) and his Ph.D. (2000) in Computer Science from Tokyo Institute of Technology. After working at NS Solutions Corporation, he worked as a research associate (2003--2007) and an assistant professor (2007--2012) at Tokyo Institute of Technology. He has been an associate professor at Meijo University since April 2012. His current interest is in knowledge representation and reasoning in machine learning and data mining. He is a member of the ACM and IEEE.}

\bioauthor[:]{Takashi Mori}{
received his M.S. in Computer Science in 2001 from Tokyo Institute of Technology. He joined Sun Microsystems Japan in April 2001.}

\bioauthor[:]{Taisuke Sato}{
is a professor of Computer Science department at Tokyo Institute of Technology. He received his M.S. in Electrical Engineering in 1975 and his Ph.D. in Computer Science in 1987 from Tokyo Institute of Technology. His early work includes program transformation and program synthesis based on fold/unfold transformation in logic programming. He is currently working on the integration of logical and probabilistic reasoning. Especially he has been developing a symbolic-statistical modeling language PRISM which is a logic-based probabilistic programming language for machine learning.}
\end{biography}



\biodate




\end{document}
