    \documentclass[english]{jnlp_1.4_rep}

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



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

\received{2002}{8}{22}
\revised{2002}{12}{2}
\accepted{2003}{1}{10}

\setcounter{page}{659}

\etitle{Construction of Practical Japanese Parsing System \\Based on Lexical Functional Grammar\footnotetext{\llap{*~}This article has been partially revised for better understanding of overseas readers.}}
\eauthor{Hiroshi Masuichi\affiref{Author_1} \and Tomoko Ohkuma\affiref{Author_1}} 
\eabstract{
This paper describes a Japanese parsing system with a linguistically fine-grained grammar based on Lexical-Functional Grammar (LFG). The system is the first 
\linebreak
Japanese LFG parser with over 97\% coverage of real-world text. We evaluated the accuracy of the system by comparing it with standard Japanese dependency parsers. The LFG parser shows roughly equivalent performance in dependency accuracy with standard parsers. It also provides reasonably accurate results of case detection. 
}
\ekeywords{Lexical-Functional Grammar, Japanese grammar rule, dependency parser}

\headauthor{Masuichi and Ohkuma}
\headtitle{Construction of Practical Japanese Parsing System Based on LFG}

\affilabel{Author_1}{}{Research \& Technology Group, Fuji Xerox Co., Ltd.}

\Reprint[T]{Vol.~10, No.~2, pp.~79--109}

\begin{document}

\maketitle

\section{Introduction}\label{Intro}

Deep grammatical analyses of input sentences based on theoretically
sound grammar formalisms are essential for the further development of
such NLP applications as machine translation, question answering,
dialogue understanding, and message extraction.  In this paper, we
report on the development and performance of a parser for Japanese
based on the Lexical-Functional Grammar (LFG) formalism (Kaplan and
Bresnan 1982; Dalrymple 2001).

The Japanese LFG grammar used in this parser is being developed in
relation to the Parallel Grammar (ParGram) project (Butt, King, Nino, and Segond 1999; 
Butt, Dyvik, King, Masuichi and Rohrer 2002).  In this project, grammars for English, French, German,
Japanese, Norwegian, Urdu, and other languages are under-way, sharing
various design decisions within the LFG formalism.  LFG assumes two
levels of syntactic representation for a sentence: a
c(onstituent)-structure (a tree) and an f(unctional)-structure
(attribute value matrices: AVMs).  Within LFG, an f-structure is meant
to encode a language-universal level of analysis, allowing for
cross-linguistic parallelism\footnote{Butt et al.\ (2002) reported how
  far the parallelism of f-structures can be maintained across
  languages in the ParGram project. Frank (1999) reported on a machine
  translation system that takes advantage of the f-structure
  parallelism.}.

Our research goal is to construct a practical Japanese LFG parsing
system with broad coverage and deep analysis for real-world text.  In
this paper, we describe the details of the system and demonstrate its
coverage and accuracy.  For the evaluation of accuracy, we compared
the outputs of the Japanese LFG parsing system with outputs of standard
Bunsetsu\footnote{A Bunsetsu is a widely accepted unit of syntactic and phonological phrase structures in Japanese. It consists of at least one content word plus optionally following function words.} dependency parsers for Japanese.

This paper is organized as follows.  Section \ref{ParGram} introduces
the ParGram project. Section \ref{System} describes the architecture
of the Japanese LFG system in the ParGram project.  Section
\ref{Grammar} presents the Japanese grammar written in the LFG
formalism for the system described in Section \ref{System}.  Section
5.1 demonstrates the coverage of the system, and explains
our approach to evaluating the accuracy of the system and Section
\ref{Accuracy} reports experimental results.


\section{Parallel Grammar Project} \label{ParGram}

The Japanese LFG grammar is being developed within the ParGram
project.  In the ParGram project, a biannual meeting is held to provide
opportunities to increase consistency as much as possible and avoid
contradiction of f-structures among multiple languages. In the
meetings we discuss the details of f-structure specifications from
naming conventions and usage of attribute-values to construction
policies for various sentence structures to improve the standard
grammar specifications of ParGram(Butt et al.\ 1999).

For example, at the level of name specification, the attribute
``GEND'' was used to indicate the gender information for each noun in
all the languages within ParGram.  However, in the English and
Japanese grammars, modification was made to distinguish ``GEND-SEM''
from ``GEND''. This is because the English and Japanese grammars gave
``GEND'' to pronouns solely to indicate whether a pronoun refers to a
male or female entity, unlike the realization of morphological gender
for general nouns in the other languages such as German, French and
Norwegian.

\vspace{2pt}
\noindent
\begin{tabular}{ll@{ }l@{ }l@{ }l@{ }l@{ }l@{ }l@{ }l@{ }l@{ }l@{ }l}
(1a) & Zyon&wa&hon&o&sono&tukue&no&ue&ni&oku&ta.\\ 
     & John&TOPIC/SUBJ&book&OBJ&the&table&of&top&on&put&PAST.
\end{tabular}

\noindent
\begin{tabular}{ll}
(1b) & John put a book on the table.
\end{tabular}
\vspace{4pt}

\begin{figure}[t]
\begin{center}
\includegraphics{21-4ia2f1.eps}
\end{center}
\caption{F-structure corresponding to sentence (1a)}
\label{fig2-1jp}
\end{figure}
\begin{figure}[t]
\begin{center}
\includegraphics{21-4ia2f2.eps}
\end{center}
\caption{F-structure corresponding to sentence (1b)}
\label{fig2-1eng}
\end{figure}

Figure \ref{fig2-1jp} shows the f-structure generated by the Japanese
LFG system for Sentence (1a).  The content words \textit{Zyon} (John)
and \textit{hon} (book) are inserted into PRED (predicate) of SUBJ
(subject) and OBJ (object). On the other hand, the case maker
\textit{ni} (on) is inserted into PRED of OBL (oblique).  This is
derived from the fact that in European languages such as English,
content words corresponding to SUBJ and OBJ do not need prepositions,
whereas OBL and ADJUNCT are accompanied by prepositions. It is
possible to write Japanese grammar that takes PRED of SUBJ and OBJ
to be a case maker, or PRED of OBL and ADJUNCT to be a content
word. However, we have written the Japanese grammar to generate the
f-structure shown in Figure \ref{fig2-1jp} to maintain parallelism
with the other languages in ParGram. Figure \ref{fig2-1eng} shows the
f-structure generated by the English LFG system for (1b) corresponding
to (1a).  The structure of Figure \ref{fig2-1eng} is basically the
same as Figure \ref{fig2-1jp}.  On the other hand, the specifications
of c-structures, which are language-dependent structures are left to
grammar writers of each language in ParGram.  Figure \ref{fig2-2jp}
and \ref{fig2-2eng} are the c-structures for (1a) and (1b).  Their
structures are completely different.

\begin{figure}[t]
\begin{center}
\includegraphics{21-4ia2f3.eps}
\end{center}
\caption{C-structure corresponding to sentence (1a)}
\label{fig2-2jp}
\par\vspace{10pt}
\begin{center}
\includegraphics{21-4ia2f4.eps}
\end{center}
\caption{C-structure corresponding to sentence (1b)}
\label{fig2-2eng}
\end{figure}


\section{Japanese LFG system}\label{System}

The ParGram project employs the XLE parser and grammar development
platform (Maxwell III and Kaplan 1993).  XLE produces packed
representations, specifying all possible grammar analyses of the
input.  Japanese is the first Asian language employing the XLE platform.  

\begin{figure}[t]
\begin{center}
\includegraphics{21-4ia2f5.eps}
\end{center}
\caption{Diagram of the Japanese LFG system}
\label{fig1_PACLIC}
\end{figure}

Figure \ref{fig1_PACLIC} shows a diagram of the Japanese LFG system.
An input Japanese sentence is segmented and tagged by the ChaSen
morphological analyzer 
(Matsumoto, Kitauchi, Yamashita, Hirano, Matsuda, Takaoka and Asahara 1999).  
Then the lexical
entry for each word in the input is automatically created (Sentence
Lexical Entry: SLE).  We implemented 40 templates for lexical entries
and SLEs are produced by selecting an appropriate template for each
word on the basis of information of the word and the words around it,
such as part-of-speech, surface form, and conjugation.  Unknown words
are currently treated as nouns.

Verb Lexical Entries (VLEs), Adjective Lexical Entries (ALEs), and
Adjectival Noun Lexical Entries (ANLEs) were written on the basis of the case
frame information in the Japanese IPAL dictionary (IPA 1987) and have
been manually enhanced.  VLEs consist of 10,387 entries and 41,115
functional annotations for 2,366 verbs.  ALEs and ANLEs consist of 947
entries and 2,197 functional annotations for 369 words in total.  Core
Lexical Entries (CLEs) include entries for basic words such as
auxiliary verbs, postpositional particles and so forth, plus
syntactically important nouns such as \textit{toki} (time) and \textit{aida} (interval).
CLEs consist of 1,252 entries and 1,913 functional annotations for 675
words.


SLEs have the lowest preference; an SLE for a word is overwritten if
an entry for the same word already exists in another set of entries.
This mechanism is intended to recover from erroneous analyses by
ChaSen.  For instance, it is impossible to correctly distinguish the
Japanese case marker (postpositional particle) \textit{de} from the
conjugated form \textit{de}\footnote{This form behaves like a
  sentential conjunction.}  of the auxiliary verb \textit{da} at the
level of morphological analysis. Therefore, we ignore the SLE created
for \textit{de} regardless of the output of ChaSen. Instead, we wrote
CLEs for \textit{de} that represent the behaviors of both the case
marker \textit{de} and the conjugated form \textit{de} of the
auxiliary verb \textit{da}. XLE parses the input, considering both
possibilities before selecting the one that matches the syntactic
structure of the whole input sentence.

Grammar Rules (GRs) include 2,468 terms in their disjunctive normal
forms and 1,223 functional annotations.  GRs have been designed to
meet the specifications of f-structures mentioned in Section \ref{ParGram}.
We explain GRs in detail in Section \ref{Grammar}.  The words in the input are
delimited by spaces and passed on to XLE, and XLE outputs c-structures
and f-structures.

XLE implements a SKIMMING mechanism (Riezler, Kaplan, Crouch, Maxwell III and 
\linebreak
Johnson 2002) to increase
the coverage of a grammar.  XLE goes into the skimming mode when the
amount of time or memory used on the input exceeds a specified
threshold.  In this mode, XLE does a limited amount of work per
sub-tree on constituents whose processing is incompleted.
This mechanism enables the parser to avoid time-outs and
memory-shortage problems and can improve the robustness of the system.


\section{Japanese LFG grammar}
\label{Grammar}

\subsection{Basic Rules}\label{Basic}

Some of the most noticeable syntactic characteristics of Japanese
sentences are relatively free word order, frequent rampant pro-drop,
and extensive use of complex predication.  To account for the free
word order, we adopted (2) as the most basic rule of our grammar.

\vspace{2pt}
\noindent
\begin{tabular}{lllc@{}c}
(2) & S & $\longrightarrow$ & PP* & V\\
    &   &                   & ($\uparrow$ GF) = $\downarrow$ & $\uparrow$ = $\downarrow$
\end{tabular}
\vspace{4pt}

For each sentence in Japanese, native speaker judgements tend to
converge on an ``optimal'' word order (Shibatani 1990).  For instance,
(3a) is an intuitively strange Japanese sentence, while (3b) is felt
to be more natural.  It is possible to write a grammar that does not
allow sentences such as (3a).  Ohtani, Miyata and Matsumoto (2000) proposed a
Japanese Head-driven Phrase Structure Grammar that is very sensitive
to the word order.  We, however, adopt (2) to achieve broader coverage
because sentences such as (3a) frequently appear in real-world text.

\vspace{2pt}
\noindent
\begin{tabular}{ll@{ }l@{ }l@{ }l@{ }l@{ }l@{ }l@{ }l}
(3a)& Singaporu&e&Zyon&ga&Tokyo&kara&iku&ta.\\
    & Singapore&to&John&SUBJ&Tokyo&from&go&PAST.\\
    & \multicolumn{8}{l}{\quad John went from Tokyo to Singapore.}
\end{tabular}

\noindent
\begin{tabular}{ll@{ }l@{ }l@{ }l@{ }l@{ }l@{ }l@{ }l}
(3b) & Zyon&ga&Tokyo&kara&simgaporu&e&iku&ta.\\
     & John&SUBJ&Tokyo&from&Tokyo&to&go&PAST.\\
     & \multicolumn{8}{l}{\quad John went from Tokyo to Singapore.}
\end{tabular}
\vspace{4pt}

We use the following type of lexical entry to handle pro-drop.  (4) is
the (simplified) entry for the verb \textit{yomu} (read).

\vspace{2pt}
\noindent
\begin{tabular}{ll}
(4) & yomu \quad V \quad (PRED)= `yomu($\uparrow$ SUBJ)($\uparrow$ OBJ)'\\
    & \quad \qquad \qquad @(PD SUBJ)\\
    & \quad \qquad \qquad @(PD OBJ)\\
    & PD(GF) = @(DEFAULT ($\uparrow$ GF PRED) `pro' \\
    & \qquad \qquad \qquad \qquad($\uparrow$ GF PRON-TYPE) null)\\
    & DEFAULT(ATTRIBUTE1 VALUE1 ATTRIBUTE2 VALUE2) = \\
    & \quad\qquad \qquad ATTRIBUTE1 = VALUE1\\
    & \quad\qquad \qquad ATTRIBUTE2 = VALUE2\\
    & \quad\qquad \qquad ProDrop: OT
\end{tabular}
\vspace{4pt}

``PD'' and ``DEFAULT'' are macro definitions, and ``@'' indicates a macro
call.  ``ProDrop: OT'' indicates that the Optimality Theory (Bresnan,
2000) mark ``ProDrop'' is added.  We set the preference of ``ProDrop'' at
the lowest level.  Therefore, ``@(PD SUBJ)'' and ``@(PD OBJ)'' work only if
no constituent that can be subcategorized for by the verb \textit{yomu} exists
in the input.  Because pro-drop frequently occurs in Japanese, lexical
entries such as (4) are important for achieving broad coverage.  (Frank, King, Kuhn and Maxwell III 
2001)

We adopted relatively loosely constrained mono-clausal analyses for
verbs to accoomodate various types of complex predications.  However,
we employed multi-clausal analyses when it was reasonable to consider
that a verb includes multiple predicate-argument relations (PARs).
This treatment is essential for such NLP applications as question
answering, dialogue understanding, and machine translation.  We
describe the multi-clausal analyses in \ref{PAR}.


\subsection{Predicate-Argument Relations and Cases}
\label{PAR}

Japanese case markers (e.g., \textit{ga}, \textit{o}) are frequently
omitted when a particular particle, such as a topic particle
(e.g., \textit{wa}, \textit{mo}, or \textit{koso}) or a focus particle
(e.g., \textit{made}, \textit{bakari}, or \textit{sae}), is added to a
noun phrase.  Moreover, a case marker can denote a different case than
it typically does, in particular syntactic constructions.  In addition
to these problems, the problem of rampant pro-drop makes it a
difficult task to capture the correct PARs and detect correct
cases in Japanese.  Our grammar pays maximum attention to this task.

\vspace{2pt}
\noindent
\begin{tabular}{ll@{ }l@{ }l@{ }l@{ }l}
(5a) & Zyon&ga&yomu&ta&hon\\
     & John&SUBJ&read&PAST&book\\
     & \multicolumn{5}{l}{\quad John read the book.}
\end{tabular}

\noindent
\begin{tabular}{ll@{ }l@{ }l@{ }l@{ }l}
(5b) & Zyon&no&yomu&ta&hon\\
     & John&SUBJ&read&PAST&book\\
     & \multicolumn{5}{l}{\quad The book John read}
\end{tabular}

\noindent
\begin{tabular}{ll@{ }l@{ }l@{ }l@{ }l@{ }l}
(5c) & Zyon&no&hon&o&yomu&ta.\\
     & John&GEN&book&OBJ&read&PAST \\
     & \multicolumn{6}{l}{\quad (Someone) read John's book.}
\end{tabular}

\noindent
\begin{tabular}{ll@{ }l@{ }l@{ }l@{ }l@{ }l}
(5d) & Zyon&ga&hon&o&yomu&ta.\\
     & John &SUBJ&book&OBJ&read&PAST\\
     & \multicolumn{6}{l}{\quad John read the book.}
\end{tabular}

\noindent
\begin{tabular}{ll@{ }l@{ }l@{ }l@{ }l@{ }l}
(5e) & Zyon&wa&hon&o&yomu&ta.\\
     & John&TOPIC/SUBJ&book&OBJ&read&PAST \\
     & \multicolumn{6}{l}{\quad John read the book.}
\end{tabular}

\noindent
\begin{tabular}{ll@{ }l@{ }l@{ }l@{ }l@{ }l@{ }l@{ }l@{ }l}
(5f) & Zyon&wa&yomu&ta&hon&o&nagesuteru&ta.\\
     & John&TOPIC/SUBJ&read&PAST&book&OBJ&throw away&PAST \\
     & \multicolumn{9}{l}{\quad John threw away the book (someone) read.}
\end{tabular}
\vspace{4pt}

For instance, \textit{no} can be used as a SUBJ marker as seen in (5b) instead of \textit{ga}
as in (5a).  However, \textit{no} in (5c) cannot be interpreted as a SUBJ
marker.  \textit{Wa} in (5e) triggers the omission of the SUBJ marker \textit{ga} in (5d).
On the other hand, \textit{wa} in (5f) also triggers the omission of the SUBJ
marker but ``John'' is the SUBJ of ``throw away'' and the SUBJ of ``read''
is dropped, that is, ``\textit{Zyon wa}'' modifies \textit{nagesuteru} rather than \textit{yomu}.

The generalized rules for these grammatical phenomena are as follows:
(I) \textit{no} can be a SUBJ marker only in a relative clause, and
(II) \textit{wa} cannot cause a topicalization and an omission of a
SUBJ marker in a relative clause.  Although these rules have been
widely discussed, no Japanese syntactic parser with formal rules
for treating (I) and (II) has been reported.  We can write the following
simple rule (6) based on the LFG formalism, which represents (I) and
(II).  ``PPsubj-no'' in (6) represents a postpositional phrase with
\textit{no}, and ``PPsubj'' represents a postpositional phrase with a
SUBJ marker other than \textit{no}.

\vspace{2pt}
\noindent
\begin{tabular}{ll@{ }l@{ }c@{ }c@{ }c}
(6) & Srel & $\longrightarrow$  & \{ PPsubj $|$  PPsubj-no \} & PP* & V\\
    &      &                    & ($\uparrow$SUBJ)=$\downarrow$ & $\uparrow$GF = $\downarrow$ & $\uparrow$ = $\downarrow$ \\
    & & & ($\downarrow$TOPICALIZATION-FORM)$\neq$ 'wa' & & 
\end{tabular}

\noindent
Another type of construction that relates to PAR analysis and case
detection is a verb (a bunsetsu) which includes multiple PARs.

\vspace{2pt}
\noindent
\begin{tabular}{ll@{ }l@{ }l@{ }l@{ }l@{ }l@{ }l@{ }l@{ }l@{ }l@{ }l}
(7) & kare&ga&9gatu&ni&Tokyo&de&yuki&ni&huru&rareru&ta\\
    & he&SUBJ&September&in&Tokyo&in&snow&by&fall&PASSIVE&PAST  \\
    & \multicolumn{10}{l}{\quad $*$He was fallen by snow in Tokyo in September.}
\end{tabular}

\noindent
\begin{tabular}{ll@{ }l@{ }l@{ }l@{ }l@{ }l@{ }l@{ }l@{ }l@{ }l@{ }l}
(8) & zyoo&ga&Sirayukihime&ni&ringo&o&taberu&saseru&ta\\
    & queen&SUBJ&Snow-White&by&apple&OBJ&eat&let&PAST  \\
    & \multicolumn{10}{p{380pt}}{\quad The queen made Snow White eat an apple. (The queen tempted Snow White to eat an apple.)}\\
\end{tabular}

Sentence (7) is an example of the indirect passive (Masuoka, Nitta, Gunji and Kinsui 
1997).  In this case, the intransitive verb \textit{huru} (fall) is
passivized.  Sentence (8) is an example of a causative sentence.  We
adopted multi-clausal analyses for indirect passives and causative
sentences, by regarding auxiliary verbs (fragments of bunsetsus) that
cause passives (e.g., \textit{reru} and \textit{rareru}), causatives
(e.g., \textit{seru}, \textit{saseru}, \textit{(te-)morau}, and
\textit{(te-)itadaku}) as having PREDs.\footnote{Within LFG, although
  the analysis for Japanese causative sentences adopted here has
  already been proposed (Sells, 1985), the debate has not yet been
  settled as to whether Japanese causative structures are
  multi-clausal or mono-clausal (Matsumoto, 1996 ; Yokota, 2001).}
These analyses enable us to capture the PARs
``\textit{huru-yuki}(SUBJ)'' in (7) and
``\textit{taberu-Sirayukihime}(SUBJ)-\textit{ringo}(OBJ)'' in (8) as
well as the main PARs
``\textit{reru-kare}(SUBJ)-\textit{yuki}(OBL)-\textit{huru}(XCOMP)''
in (7) and
``\textit{saseru-zyoo}(SUBJ)-\textit{Sirayukihime}(OBL)-\textit{taberu}(XCOMP)''
in (8).  Figure \ref{paclic_fig2} shows the f-structure generated by
the LFG system for (7); Figure 8 shows the f-structure for (8). The
standard Bunsetsu dependency parsers for Japanese cannot capture
``snow falls in Tokyo in September'' or ``Snow White eats an apple''
because they consider a Bunsetsu as the unit of analysis.

\begin{figure}[b]
\begin{center}
\includegraphics{21-4ia2f6.eps}
\end{center}
\caption{F-structure for sentence (7)}
\label{paclic_fig2}
\end{figure}

Several grammatical issues involve PAR analysis and case detection.
Table \ref{table_figure3} shows a list of examples of the grammatical
issues for which we have already written LFG rules.

\begin{table}[t]
\caption{Examples of Japanese grammatical issues related to PAR and case detection}
\label{table_figure3}
\input{02table01.txt}
\end{table}


\subsection{Robustness Techniques}

As mentioned in \ref{Basic}, we use Optimality Theory (OT) marks to
delete dispreferred parses.  We also use OT marks for efficiency.
When ranked OT constraints are divided into groups by relative
ranking, XLE processes the input in multiple passes.  The core grammar
consisting of the rules with OT marks in the highest ranked group is
used for the first pass.  If a valid parse is found, then XLE will
stop.  In contrast, XLE will process the input again with the core
grammar plus the rules with OT marks in the second-highest-ranked
group for the second pass.  This multiple-pass-parsing mechanism is
useful for writing rules for rare grammatical phenomena without
increasing unintended ambiguity.

\vspace{2pt}
\noindent
\begin{tabular}{ll@{ }l@{ }l@{ }l@{ }l}
(9a) & aruku&koto&ga&itiban&da\\
     & walk&NOMINALIZER&SUBJ&best&be\\
     & \multicolumn{5}{l}{\quad To walk is best.}
\end{tabular}

\noindent
\begin{tabular}{ll@{ }l@{ }l@{ }l}
(9b) & $*$aruku&ga&itiban&da\\
     & walk&SUBJ&best&be
\end{tabular}

\noindent
\begin{tabular}{ll@{ }l@{ }l@{ }l}
(9c) & makeru&ga&kati&da\\
     & lose&SUBJ&victory&be\\
     & \multicolumn{4}{l}{\quad To lose is a victory.}
\end{tabular}
         
For instance, the SUBJ marker \textit{ga} ordinarily does not follow
the canonical form of verbs as shown in (9a) and (9b).  However, it
exceptionally occurs in some idiomatic expressions as shown in (9c).
We divided the 42 OT marks in our grammar into four groups, and we put
the OT mark for the rule for sentences such as (9c) in the
lowest-ranked preference group.  The OT marks in the
lowest-ranked-preference group are added to the rules for rare
idiomatic expressions or colloquial expressions so that those rules do
not affect the core grammar.

\begin{figure}[b] 
\begin{center}
\includegraphics{21-4ia2f7.eps}
\end{center}
\caption{Examples of fragment c-/f-structures}
\label{paclic_fig4}
\end{figure}

When the STANDARD grammar, which consists of all the rules described
above, does not produce a complete parse, a FRAGMENT grammar (Riezler
et al.\ 2002) that we wrote for Japanese is used.  This grammar parses the
input as a sequence of well-formed chunks.  These chunks have both
c-structures and f-structures.  The set of fragment parses is then
chosen on the basis of a fewest-chunk method.
The ungrammatical constituents in Japanese sentences that the STANDARD
grammar does not cover tend to appear in sentence-final position.
Therefore, the fragment grammar is likely to output a meaningful chunk
for the major part of the input sentence.  Examples of fragment
c-structures and f-structures are shown in Figure \ref{paclic_fig4}.  

In this case, the adverb \textit{tinamini} (for your information) in
sentence-final position is regarded as an ungrammatical constituent;
the STANDARD grammar assumes that a Japanese adverb cannot modify a
verb to its left.\footnote{It is one of the principles of
Japanese syntax that a bunsetsu should modify another bunsetsu to the
right of it.\\\llap{$^{6}$~}2.8~GHz CPU/2~GB memory}  Figure \ref{paclic_fig4} shows that the whole sentence
except \textit{tinamini} is correctly analyzed.




\section{Experimental Evaluation}

\subsection{Coverage}
\label{Coverage}

We prepared 3 types of Japanese text for evaluating the coverage of the Japanese LFG system:  
\begin{itemize}
\item[(A)]{ 10,000 sentences from the Japanese EDR corpus (EDR 1996), mainly composed of newspaper text}
\item[(B)]{ 460 sentences from a copier manual (Fuji Xerox 2000)} 
\item[(C)]{ 9,637 sentences of eCRM text}  
\end{itemize}

The coverage in this paper refers to the percentage of the sentences
for which the system returns at least one f-structure.  All three text
types consist of randomly selected unseen sentences.  Most sentences
in (A) and (B) are grammatical.  On the other hand, (C) includes many
ungrammatical and colloquial sentences, because (C) consists of
transcriptions of telephone calls from customers to a customer service
center.

\begin{table}[b]
\caption{Results of the coverage test}
\label{table1_PACLIC}
\input{02table02.txt}
\end{table}



\addtocounter{footnote}{1}
Table \ref{table1_PACLIC} lists the coverage results.  The total
coverage for (C) is almost the same as that for (A) and (B).  On the
other hand, the STANDARD coverage for (C) is lower than for (A) and (B).

This difference is due to the large number of ungrammatical sentences
in (C) , which implies that the ratio of sentences that could be
covered by the STANDARD grammar was low; the FRAGMENT grammar covered
the ungrammatical sentences.  The main reason for failure of analysis
in all three types was time-outs caused by the sentences that even the
skimming mode could not cover.  Table 2 shows that the system has
over 97\% coverage in total and 87\% coverage with the STANDARD
grammar, even for (C).


\subsection{Accuracy}
\label{Accuracy}

\subsubsection{Approach}

Outputs of standard Japanese parsers such as KNP (Kurohashi and Nagao 
1994) and CaboCha (Kudo and Matsumoto 2002) are trees expressing
Bunsetsu dependencies (Bunsetsu Trees).  It is quite natural and
reasonable to compare a Bunsetsu Tree with an f-structure, because a
Bunsetsu Tree is essentially a simplified f-structure.  We can convert
an f-structure into a dependency tree by regarding a PRED in the
f-structure as a node in the tree, and the outside-inside relation of
the nested AVMs of the f-structure as the parent-child relation
between the nodes (Pred Tree).

A problem is that one Bunsetsu unit can correspond to more than one
PRED.  For instance, (10a) has one Bunsetsu, but the f-structure for
(10a) includes two PREDs as described in \ref{PAR}.  (10b) has also one
Bunsetsu but its f-structure includes two PREDs: one for the verb
\textit{kaku} (write) and the other for the auxiliary verb
\textit{nai} (not).  A compound noun is also regarded as one Bunsetsu
as in (10c), but its f-structure can include multiple PREDs
corresponding to the nouns that form the compound noun.

\vspace{2pt}
\noindent
\begin{tabular}{ll@{ }l}
(10a) & kakaseru&(one bunsetsu)\\
      & kaku(write)\enskip seru(make)&(two morphemes)
\end{tabular}

\noindent
\begin{tabular}{ll@{ }l}
(10b) & kakanai&(one bunsetsu)\\
      & kaku(write)\enskip nai(not)&(two morphemes)
\end{tabular}

\noindent
\begin{tabular}{ll@{ }l}
(10c) & sekisyokuzetuenwaiya&(one bunsetsu)\\
      & sekisyoku(red)\enskip zetuen(insulation)\enskip waiya(wire)&(three nouns)
\end{tabular}

Another problem is that a Bunsetsu is a language-dependent and phrase-structural constituent.  As previously noted, an f-structure is meant
to encode a more language universal level of analysis.  On the other
hand, a c-structure encodes language-particular differences in
syntactic structures and constituency.  Thus, information about
Bunsetsus should appear in c-structures, but not in f-structures.
This means that we cannot detect which part of an f-structure
corresponds to a Bunsetsu.  However, it is easy in general to list the
grammatical categories in c-structures for Japanese, which correspond
to Bunsetsus.  We created a Bunsetsu Tree from a c-structure and an
f-structure as follows:

\begin{enumerate}
\item
List the grammatical categories corresponding to Bunsetsus.
\item
Specify the nodes in a c-structure that, correspond to Bunsetsus, referring to the category list in 1.
\item
Specify the f-structure AVMs, which correspond to the nodes specified in 2 (Bunsetsu AVMs).
\item
Create a Bunsetsu Tree by treating ``a set of PREDs'' in a Bunsetsu AVM as a node in the Bunsetsu Tree, and the outside-inside relation of the nested Bunsetsu AVMs as the parent-child relation between the nodes.
\end{enumerate}  

\begin{figure}[t] 
\begin{center}
\includegraphics{21-4ia2f8.eps}
\end{center}
\caption{C-/f-structure and Pred/Bunsetsu trees for sentence (7)}
\label{paclic_fig5}
\end{figure}

Figure \ref{paclic_fig5} shows the c-/f-structures and the
Pred/Bunsetsu Trees for Sentence (8).  ``NP'', ``NPobl'' and ``Vverb''
in the c-structure are the grammatical categories corresponding to
Bunsetsu. The numbers in Figure \ref{paclic_fig5} indicate the
correspondence of the grammatical categories in the c-structure to the
AVMs in the f-structure.  We can specify the Bunsetu AVM by referring
to the correspondence, and thus create the Bunsetsu Tree\footnote{When we
  created the Pred Trees and the Bunsetsu Trees for our tests, we did
  not make a node correspondings to a PRED of an OBL as in Figure
  \ref{paclic_fig5}.  Instead we included the PRED information in the
  link labels.}.  The Bunsetsu Trees are comparable to the trees
generated by the standard Bunsetsu dependency parsers for Japanese.


\subsubsection{Experiments and results} 

We randomly selected 200 unseen sentences from the EDR corpus for
which the Japanese LFG system returned at least one f-structure.  The
200 sentences were analyzed with KNP, CaboCha and the Japanese LFG
system. The outputs of KNP and CaboCha are Bunsetsu Trees, and Pred
Trees and Bunsetus Trees were created from the outputs of the LFG
system.  In this experiment, the link labels in the trees are
grammatical functions as in Figure \ref{paclic_fig5}, and we omitted
other attributes and values in f-structures, such as TENSE and MOOD.

A Japanese linguist and Japanese native speaker created gold
standard Pred Trees and 
\linebreak
Bunsetsu Trees for the 200 sentences
consulting the outputs of the KNP, CaboCha and the LFG system.\footnote{We
  did not refer to the syntactic annotations of the EDR corpus.
  Comparing our gold standard with these annotations is a future work.}
We compared the gold standard Bunsetsu Trees with the Bunsetsu Trees
generated by KNP, CaboCha and the LFG system (Bunsetsu Comparison).
We also compared the gold standard Pred Trees with the Pred Trees
generated by the LFG system (Pred Comparison).

Table \ref{table2_PACLIC} shows the results of the Bunsetsu
Comparison.  The precision and recall are based on the number of
correct Bunsetsu-Bunsetsu (B-B) dependencies.  The precision and
recall of ``B-G-B'' in the table are based on the number of the correct
triplets of a bunsetsu, its parent Bunsetsu and a link label (a
grammatical function) between them.  The LFG system outputs all
possible grammar analyses (as in \ref{System}).  The Upper Bound is
the average for 200 parses each of which is the best parse for a
sentence.  The Average is the macro average (that is, the average of
the 200 averages for all parses for each sentence).  The BASELINE is
for the Bunsetsu Trees obtained assuming all Bunsetsus modify their
right-hand neighbors.

\begin{table}[b]
\caption{Results of the Bunsetsu comparison}
\label{table2_PACLIC}
\input{02table03.txt}
\end{table}
\begin{table}[b]
\caption{Results of the Pred comparison}
\label{table3_PACLIC}
\input{02table04.txt}
\vspace{-1\Cvs}
\end{table}

Table \ref{table3_PACLIC} shows results of the Pred Comparison.  The `P-G-P' is based on the number of correct triplets of a PRED, its parent PRED and a link label between them.  The `P-P' is based on the number of the correct parent-child PRED pairs. 


\subsubsection{Discussion} 

Table 3 shows that the Average ``B-B'' of the LFG system is roughly
equivalent to that of KNP and CaboCha.  The results of ``B-G-B'' are
encouraging, because the ``B-G-B'' results are not substantially worse
than the ``B-B'' results of the LFG system.  This means the case
detection by the LFG system works well.

We examined the Bunsetsu Trees to investigate differences among the
three systems, and found the LFG system based on the linguistically
fine-grained grammar advantageous in some regards.  For example, KNP
and CaboCha output parses in which a noun phrase ending with $no$
modifies a verb that is not in a relative clause.  This never happens
with the LFG system as described in \ref{PAR}.  As another example,
the dependencies of noun phrases topicalized by \textit{wa} were more
correctly analyzed by the LFG system than by the other systems,
because of the precise grammar rules for case detection described in
\ref{PAR}.  On the other hand, rules for coordination in our grammar
are not adequately sophisticated; therefore, the analyses for the
sentences including coordination structures using the non-linguistic
methods of KNP and CaboCha were better.

The results in Table 4 show that both precision and recall of the LFG
system in the Pred comparison are higher than those in the Bunsetsu
Comparison.  This means the accuracy of the intra-Bunsetsu analyses by
the LFG system is reliable.  Examples of the intra-Bunsetsu analyses
are shown in (10a--10c).  For instance, the LFG system is
required to determine the dependencies of the nouns in the compound
noun (10c), that is, both \textit{sekisyoku} (red-color) and
\textit{zetuen} (insulation) modify \textit{waiya} (wire).

The LFG system is based on a hand-coded grammar.  We think we will be
able to increase the accuracy of our system by continuing the
development to address grammatical issues that have not yet been
considered.  In addition, by using a statistical method for
disambiguation (such as the method proposed in Riezler et al.\ (2002)),
it will be possible to select better parses from among the parses XLE
generates for a sentence than random selection.


\section{Conclusion} 

We have described a Japanese parsing system based on the LFG
formalism.  The system is the first Japanese LFG parser with over 97\%
coverage (91\% on average without FRAGMENT analyses) for real-world
text.  We evaluated the accuracy of the system by comparing it with
standard Japanese dependency parsers.  The LFG parser shows a roughly
equivalent performance on the Bunsetsu dependency accuracy to the
standard Japanese parsers.  It also provides reasonably accurate
results for case detection and intra-Bunsetsu analyses.

We are incorporating the LFG system into off-line NLP applications.
However, the processing speed of the system is not yet sufficient for
real-time applications; therefore we will customize XLE for the
Japanese grammar to achieve better performance.



\acknowledgment

We acknowledge our indebtedness to all the members of the ParGram
project, especially Ronald Kaplan, Tracy Holloway King, John Maxwell,
Mary Dalrymple and Yasunari Harada for their comments and discussions
on early versions of the Japanese LFG grammar and system.


\bibliographystyle{jnlpbbl_1.5}

\begin{thebibliography}{}

\bibitem[{Bresnan }{2000}]{B2000}
Bresnan, J. (2000).
\newblock ``Optimal syntax.'' 
\newblock In Dekkers, J., van der Leeuw, F. R. H., and van de Weijer, J. M. (Eds.), \textit{Optimality Theory: Phonology, Syntax and
Acquisition},\ 334--385.
  Oxford University Press.

\bibitem[{Butt et~al. }{2002}]{B2002}
Butt, M., Dyvik, H., King, T.~H., Masuichi, H., and Rohrer, C. (2002). 
\newblock ``The Parallel Grammar Project.'' 
\newblock In {\em Proceedings of the 19th International Conference on
  Computational Linguistics (COLING 2002) Workshop `Grammar Engineering and
  Evaluation'}, pp.~1--7.

\bibitem[{Butt et~al. }{1999}]{B1999}
Butt, M., King, T.~H., Nino, M.~E., and Segond, F. (1999). 
\newblock {\em A Grammar Writer Cookbook}.
\newblock CSLI Publications.

\bibitem[{Dalrymple }{2001}]{D2001}
Dalrymple, M. (2001). 
\newblock {\em SYNTAX and SEMANTICS Lexical Functional Grammar}.
\newblock Academic Press.

\bibitem[{EDR }{1996}]{EDR}
EDR (Japanese Electronic Dictionary Research Institute, Ltd.) (1996). 
\newblock {\em EDR Electronic Dictionary Version 1.5 Technical Guide. (in Japanese)}.
\newblock EDR.

\bibitem[{Frank }{1999}]{F1999}
Frank, A. (1999). 
\newblock From Parallel ``Grammar Development towards Machine
  Translation.'' 
\newblock In {\em Proceedings of MT Summit VII}, pp.~134--142.

\bibitem[{Frank et~al. }{2001}]{Frank}
Frank, A., King, T.~H., Kuhn, J., and Maxwell~III, J.~T.
(2001). 
\newblock ``Optimality Theory Style Constraint Ranking in Large-scale LFG grammars.''  
\newblock In Sells, P., Bresnan, J., Butt, M., and King, T. H. (Eds.) 
{\em Formal and Empirical Issues in Optimality Theoretic Syntax}, pp. 367--397.
CSLI Publication.

\bibitem[{Fuji Xerox. }{2000}]{manual}
Fuji Xerox Co., Ltd. (2000).
\newblock {Document Gate operation manual first edition, DE-1006 (in Japanese)\em }.

\bibitem[{IPA }{1987}]{IPAL}
IPA (Information-technology Promotion Agency) (1987).
\newblock {\em IPA Lexicon of the Japanese Language for Computers IPAL.  (in Japanese)}.
\newblock IPA.

\bibitem[{Kaplan and Bresnan }{1982}]{KandB1982}
Kaplan, R.~M. and Bresnan, J. (1982).
\newblock ``Lexical-Functional Grammar: A Formal System for Grammatical
  Representation. 
\newblock In Bresnan, J. (Ed.) {\em The Mental Representation of Grammatical Relations}, pp. 173--281. The MIT press.

\bibitem[{Kudo and Matsumoto }{2002}]{cabocha}
Kudo, T. and  Matsumoto, M. (2002).
\newblock ``Japanese Dependency Analysis using Cascaded Chunking.''
\newblock In {\em Proceedings of 6th Conference on
Natural Language Learning (CoNLL02)}, pp. 63--69.

\bibitem[{Kurohashi and Nagao }{1994}]{kurohshi}
Kurohashi, S., and Nagao, M. (1994). 
\newblock ``A Syntactic Analysis Method of Long Japanese Sentences Based on the Detection of Conjunctive Structures.'' 
\newblock {\em Computational Linguistics}, \textbf{20}(4), pp. 507--534.

\bibitem[{Masuoka et~al. }{1997}]{masuoka1997}
Masuoka, T., Nitta, Y., Gunji, T., and Kinsui, S. (1997). 
\newblock {\em Grammar}.
\newblock Iwanami Press (in Japanese).


\bibitem[{Matsumoto }{1996}]{matsumoto1996}
Matsumoto, Y. (1996). 
\newblock {\em Complex Predicates in Japanese}.
\newblock CSLI Publications.


\bibitem[{Matsumoto et~al. }{1999}]{chasen}
Matsumoto, Y., Kitauchi, A., Yamashita, T., Hirano, Y., Matsuda, H., Takaoka, K., and  Asahara, M.  (1999).
\newblock {\em Japanese Morphological Analysis System ChaSen version 2.0 Manual 2nd edition. Technical report (in Japanese)}.
\newblock Nara Institute of Science and
Technology, Japan.

\bibitem[{Maxwell and Kaplan }{1993}]{MandK1993}
Maxwell~III, J.~T. and\  \ Kaplan, R.~M. (1993).
\newblock ``The Interface between Phrasal and Functional Constraints.'' 
\newblock {\em Computational Linguistics}, \textbf{19}(4), pp.~571--590.

\bibitem[{Ohtani et~al. }{2000}]{otani2000}
Ohtani, A.,  Miyata, T., and Matsumoto, Y. (2000). 
\newblock ``On HPSG-Based Japanese Grammar 
---Refinement and Extension for Implementation---.'' 
\newblock {\em Journal of Natural Language Processing}, \textbf{9}(1), 3--19.

\bibitem[{Riezler et~al. }{2002}]{Riezler}
Riezler., S., Kaplan, R. M., Crouch, R., and Maxwell~III, J.~T., Johnson, M. (2002).
\newblock ``Parsing the Wall
Street Journal using a Lexical-Functional Grammar and Discriminative Estimation Techniques.'' 
\newblock In {\em Proceedings of the 40th AnnualMeeting of the Association for Computational Linguistics (ACL'02)}, pp.~217--278.

\bibitem[{Sells }{1985}]{S1985}
Sells, P. (1985).
\newblock {\em Lectures on Contemporary Syntactic Theories: An Introduction to
  Government-Binding Theory, Generalized Phrase Structure Grammar, and
  Lexical-Functional Grammar}.
\newblock CSLI Publications.

\bibitem[{Shibatani }{1990}]{Shibatani}
Shibatani, M. (1990).
\newblock {\em The Languages of Japan}.
\newblock Campridge University Press.

\bibitem[{Yokota }{2001}]{Yokota2001}
Yokota, K. (2001).
\newblock Complex-predicate Formation and Some Consequences in
  Japanese\
\newblock In {\em Proceedings of the LFG01 Conference}. 
\texttt{http://csli--publications.stanford.edu/}


\end{thebibliography}






\begin{biography}
\bioauthor[:]{Hiroshi Masuichi}{
He is an executive research principal at Research \& Technology Group of Fuji Xerox Co., Ltd.  He received his Bachelor's, Master's degrees in engineering from Kyoto University and doctorate degree in engineering from Tokyo University of Agriculture and Technology in 1989, 1991, and 2004, respectively. He is a member of the Japanese Society for Artificial Intelligence, the Information Processing Society of Japan, and the Association for Natural Language Processing, and an executive board member of the Japanese Society for Artificial Intelligence.  His research interests include data mining, knowledge processing, and natural language processing.
}
\bioauthor[:]{Tomoko Ohkuma}{
She is a research principal at Research \& Technology Group of Fuji Xerox Co., Ltd. Her main research interest is Information Extraction Technology based on Natural Language Processing (NLP). She is a member of organizers in NTCIR-11 MedNLP-2. She was a part-time lecturer of Tokyo Woman's Christian University (in 4 years). She earned her Ph.D and M.A. from Keio University, where she majored NLP. She also earned B.A. in linguistics from Tokyo Woman's Christian University.
}
\end{biography}


\biodate



\end{document}


