    \documentclass[english]{jnlp_1.4}

\usepackage{jnlpbbl_1.3}
\usepackage[dvips]{graphicx}
\usepackage{hangcaption_jnlp}
\usepackage{udline}
\setulminsep{1.2ex}{0.2ex}
\let\underline

\usepackage{epsfig}
\usepackage{url}
\def\BT{}                                 
\def\UW{}                                 
\def\Dder{}                            
\def\Ider{}              
\def\Nsum#1{}                      
\def\Bdma#1{}                
\def\Stri#1#2{} 
\def\Conc#1#2{}        
\def\argmax{}           
\def\argmin{}           
\def\MLE{}    
\def\QED{}             
\def\because{}
\def\MC1#1#2{}
\def\MC#1#2#3{}
\def\lineB#1#2{}
\def\lineC#1#2#3{}
\def\tabref#1{}
\def\figref#1{}
\def\equref#1{}
\def\secref#1{}
\def\subref#1{}
\def\appref#1{}
\def\ruleL{}
\def\ruleP{}
\def\ruleS{}
\def\ruleC{}
\def\ruleI{}
\def\ruleF{}
\def\fone{}
\def\ftwo{}
\def\fthree{}
\def\ffour{}
\def\ffive{}
\def\fsix{}
\def\fseven{}
\def\KKC#1{}
\def\BT{}
\def\UW{}
\def\UU{}
\def\unit{}
\def\unitA1#1{}
\def\pair#1#2{}
\def\lineB#1#2{}
\def\MC#1#2#3{}
\def\dg{}
\def\s{}
\def\e{}




\Volume{19}
\Number{3}
\Month{September}
\Year{2012}


\received{2011}{12}{5}
\revised{2012}{4}{28}
\accepted{2012}{6}{26}

\setcounter{page}{167}

\etitle{A Pointwise Approach to Training Dependency Parsers from Partially Annotated Corpora}
\eauthor{Daniel Flannery\affiref{KU} \and Yusuke Miyao\affiref{NII} \and
Graham Neubig\affiref{KU}\affiref{NAIST} \and Shinsuke Mori\affiref{ACCMS}} 
\eabstract{
  We introduce a word-based dependency parser for Japanese that
  can be trained from partially annotated corpora, allowing for 
  effective use of available linguistic resources and reduction of the
  costs of preparing new training data. This is especially important
  for domain adaptation in a real-world situation. We use a pointwise
  approach where each edge in the dependency tree for a sentence is
  estimated independently. Experiments on Japanese dependency parsing
  show that this approach allows for rapid training and achieves
  accuracy comparable to state-of-the-art dependency parsers trained
  on fully annotated data.
}
\ekeywords{Dependency parsing, partial annotation, domain adaptation}

\headauthor{Flannery et al.}
\headtitle{A Pointwise Approach to Training Dependency Parsers}

\affilabel{KU}{}{Graduate School of Informatics, Kyoto University}
\affilabel{NII}{}{National Institute of Informatics}
\affilabel{ACCMS}{}{Academic Center for Computing and Media Studies, Kyoto University}
\affilabel{NAIST}{}{Now affiliated with the Nara Institute of Science and Technology}


\begin{document}

\maketitle

\section{Introduction}
\label{sec:introduction}

Parsing is one of the fundamental building blocks of natural language processing, with applications
ranging from machine translation \cite{yamada01syntaxbasedmt} to information extraction
\cite{miyao09interactionextraction}.  However, while statistical parsers achieve higher and higher
accuracies on in-domain text, the creation of data to train these parsers is labor-intensive, which
becomes a bottleneck for smaller languages.  In addition, it is also a well known fact that accuracy
plummets when tested on sentences of a different domain than the training corpus
\cite{gildea2001corpus,petrov2010uptraining}, and that in-domain data can be annotated to make up for
this weakness.

In this paper, we propose a dependency parser for Japanese that helps ameliorate
these problems by allowing for the efficient development of training data.  This is done through a
combination of an efficient corpus annotation strategy and a novel parsing method.  We use the
assumption that Japanese is a head-final language to simplify decoding by constraining the size of
the search space.  For corpus construction, we use partial annotation, which allows an annotator to
skip annotation of unnecessary edges, focusing their efforts only on the ones that will provide the
maximal gains in accuracy.

While partial annotation has been shown to be an effective annotation strategy for a number of tasks
\cite{tsuboi2008,sassano2010using,neubig2010}, traditional parsers such as that of
\cite{mcdonald2005non} cannot be learned from partially annotated data. The reason for this is
that they use structural prediction methods that must be learned from fully annotated sentences.
However, a number of recent works \cite{liang08structurecompilation,neubig11aclshort} have found
that it is possible to ignore structure and still achieve competitive accuracy on tasks such as
part-of-speech (POS) tagging. 

Similarly, recent work on dependency parsing \cite{spreyer2009incomplete,spreyer2010training} has
shown that training constraints can be relaxed to allow parsers to be trained from partially
annotated sentences, with only a small reduction in parsing accuracy. In this approach the scoring
function used to evaluate potential dependency trees is modified so that it does not penalize trees
consistent with the partial annotations used for training. Our formulation is based on an even
stronger independence assumption, namely that the score of each edge is independent of the other
edges in the dependency tree. While this does have the potential to decrease accuracy, it has a
number of advantages such as the ability to use partially annotated data, faster speed, and simple
implementation.

We perform an evaluation of the proposed method on a Japanese dependency parsing task.  First, we
compare the proposed method to both \citeA{mcdonald2005non}'s parser and a deterministic parser
\cite{nivre2004deterministic}.  We find that despite the lack of structure in our prediction method,
the proposed method is still able to achieve accuracy similar to that of \citeA{mcdonald2005non}'s
parser, while training and testing speeds are similar to those of the deterministic parser.

In addition, we perform a case-study of the use of partial annotation in a practical scenario, where
we have data that follows a segmentation standard that differs from the one we would like to follow.
In Japanese dependency parsing, traditionally phrase segments ({\it bunsetsu}) have been used
instead of words as the minimal unit for parsing \cite{kudo2002,sassano2010using}, but these
segments are often too large or unwieldy for applications such as information extraction and
machine translation \cite{nakazawa08linguistically}.  In our case-study, we demonstrate that a
corpus labeled with phrase dependencies can be used as a partially annotated corpus in the
development of a word-based parser that is more appropriate for these applications.  The use of a
phrase-labeled corpus allows us to increase the accuracy of a word-based parser trained on a smaller
word-labeled data set by 2.75\%.


\section{Pointwise estimation for dependency parsing}

This work follows the standard setting of recent work on dependency
parsing \cite{buchholz2006}.  Given a sequence of words
$\Bdma{w}=\langle w_1,w_2,\ldots,w_n\rangle$ as input, the goal is to
output a dependency tree $\Bdma{d}=\langle d_1,d_2,\ldots,d_n\rangle$,
where $d_i\equiv j$ when the head of $w_i$ is $w_j$\footnote{While we
describe unlabeled dependency parsing for simplicity, it is trivial to
extend it to labeled dependency parsing.}.  We assume that $d_i=0$ for
some word $w_i$ in a sentence, which indicates that $w_i$ is the head
of the sentence.


\subsection{A pointwise dependency parser}
\label{sec:pointwisemst}

The parsing model we pursue in this paper is
\citeA{mcdonald2005non}'s edge-factored model.  A score,
$\sigma(\langle i, d_i \rangle, \Bdma{w})$, is assigned to each edge (i.e. dependency) $d_i$, and
parsing finds a dependency tree, $\hat{\Bdma{d}}$, that
maximizes the sum of the scores of all the edges
\begin{equation}
\hat{\Bdma{d}}=\argmax_{\Bdma{d} \in D}\sum \limits_{i=1}^n\sigma(\langle i, d_i \rangle, \Bdma{w}),
\end{equation}
where $D$ is the set of all possible spanning trees for the input
sentence.

It is known that, given $\sigma(\langle i, d_i \rangle, \Bdma{w})$ for all possible
dependencies in a sentence, $\hat{\Bdma{d}}$ can be computed by the
maximum spanning tree algorithm such as Chu-Liu/Edmonds' algorithm.

An important difference from \citeA{mcdonald2005non} is in the
estimation of $\sigma(\langle i, d_i \rangle, \Bdma{w})$.  \citeA{mcdonald2005non} applied a
perceptron-like algorithm that optimizes the score of entire
dependency trees.  However, we stick to pointwise prediction:
$\sigma(\langle i, d_i \rangle, \Bdma{w})$ is estimated for each $w_i$
independently.  Any variety of machine-learning-based classifiers can
be applied to the estimation of $\sigma(\langle i, d_i \rangle, \Bdma{w})$, because it is essentially
an $n$-class classification problem.

We define the edge score as a probability, $\sigma(\langle i, d_i
\rangle, \Bdma{w}) = \log{p(d_i)}$, and estimate a log-linear
model \cite{berger1996maximum}. We calculate the probability of a
dependency labeling $p(d_i=j)$ for a word $w_i$ from its context,
which is a tuple $x=\langle \Bdma{w},\Bdma{t},i \rangle$, where
$\Bdma{t}=\langle t_1,t_2,\ldots,t_n\rangle$ is a sequence of POS tags
assigned to $\Bdma{w}$ by a tagger. The conditional probability
$p(j|x)$ is given by the following equation.
\begin{equation}
p(j|x, \Bdma{\theta}) = \frac{\exp{( \Bdma{\theta} \cdot \Bdma{\phi}(x,j))}}
{\sum_{j' \in \mathcal{J}} \exp{( \Bdma{\theta} \cdot \Bdma{\phi}(x,j'))}}
\end{equation}

The feature vector $\Bdma{\phi}
= \langle \phi_1, \phi_2, \ldots, \phi_m\rangle$ is a vector of
non-negative values calculated from features on pairs $(x,j)$, with corresponding
weights given by the parameter vector $\Bdma{\theta}
= \langle \theta_1, \theta_2, \ldots, \theta_m\rangle$. We estimate
$\Bdma{\theta}$ from sentences annotated with dependencies. It should
be noted that the probability $p(d_i)$ depends only on $i$, $j$, and
the inputs $\Bdma{w}$, $\Bdma{t}$, which ensures that it is estimated
independently for each $w_i$.  Because parameter estimation does not
involve computing $\hat{\Bdma{d}}$, we do not apply the maximum
spanning tree algorithm in training.



\subsection{Features}

\begin{table}[b]
\hangcaption{An example of a partially annotated sentence and the
  features for a dependency between case marker は (\s) and the verb 歓迎 (welcomes).}
  \label{figure:features}
\input{03table01.txt}
\end{table}

Our current implementation uses the following features, both
individually and as combination features, for $\Bdma{\phi}$.

\begin{enumerate}
\item[F1:] The distance $j-i$ between a dependent word $w_i$ and its
  candidate head $w_j$.
\item[F2:] The surface forms $w_i$ and $w_j$.
\item[F3:] The parts-of-speech of $w_i$ and $w_j$.
\item[F4:] The surface forms of up to three words to the left of $w_i$ and $w_j$.
\item[F5:] The surface forms of up to three words to the right of $w_i$ and $w_j$.
\item[F6:] The parts-of-speech of the words selected for \ffour.
\item[F7:] The parts-of-speech of the words selected for \ffive.
\end{enumerate}

Table \ref{figure:features} shows the values of these features for a
partially annotated example sentence where one word, the case marker
は (\s), has been annotated with its head, the verb 歓迎 (welcomes).

Using pointwise prediction rather than structured prediction has the
potential to hurt parsing accuracy.  However, our method can enjoy
greater flexibility, which allows for training from partially
annotated corpora as will be described in
Section~\ref{sec:adaptation}. It also simplifies the implementation
and reduces the time necessary for training, which is important as
recent work on active learning for word segmentation and POS tagging
\cite{neubig11aclshort} has shown the importance of learning speed for
active learning strategies.



\subsection{First-order and second-order features}
\label{sec:first-order-second-order}

\citeA{mcdonald2005non}'s original approach is called a first-order
formulation because features are only defined over the dependent and
head words forming a single edge. The main features used are the
surface forms and POS tags of the dependent and head, and distance
between them. They also incorporate local context information by
defining features on words to the immediate left and right of both the
dependent and head, for a window size of three words. Similarly, they
make use of broader context information by defining features on the
POS tags of words that occur between the dependent and head.

\citeA{mcdonald2006online} later extended the first-order approach of
\citeA{mcdonald2005non} to a second-order approach, where information
about adjacent edges is also used as features. In this new formulation, the
score of the tree is factored into the sum of adjacent edge pair
scores instead of the sum of individual edge scores. Because up to two
adjacent dependency edges from the same head are considered when
computing an edge pair score, this has the effect of conditioning on
the last dependent chosen for the head.

In contrast to the second-order formulation described above, the
proposed method sticks to first-order features but refers to a larger
window of surrounding words for both the dependent and head. Up to
three words in each direction are considered, resulting in a window
size of seven words. This allows us to pick up context information
regardless of whether an adjacent edge exists for a
head. \citeA{sassano2009unified} showed that this kind of context
information can also be useful for phrase-based Japanese dependency
parsing.

There are three main motivations for our pointwise approach. First, we
wish to avoid feature sparsity in the training data by restricting
ourselves to first-order features. Second, we want to enable our
parser to be trained from partially annotated corpora, where only some
dependencies in a sentence are annotated. Finally, we seek to reduce
the amount of time necessary for training. We will show in
\secref{sec:withFAC} that for a Japanese dependency parsing task, the
proposed method achieves reasonably good parsing accuracy.


\subsection{Solution search}
\label{sec:solution-search}

The target of our experiments is written Japanese, which is a
head-final language. In line with \citeA{uchimoto1999japanese}, we
assume that in Japanese dependencies go from left to right and that
every word except for the last one in a sentence depends on exactly
one other word. Thus we assume that $d_i>i$ for all $i\ne n$ and
$d_n=0$. This assumption reduces the maximum spanning tree algorithm
to a simpler algorithm: for each word we select the dependency with
the maximum score. As this never creates a loop of dependencies, a
recursive process as in Chu-Liu/Edmonds' algorithm is not necessary.

In contrast to \citeA{uchimoto1999japanese} we do not make the
assumption that dependencies do not cross, because even in written
Japanese such dependencies may occur in informal contexts. Our
implementation does not enforce this projectivity constraint on
dependencies, so it can handle non-projective dependencies in the
training data which satisfy the head-final assumption.

This head-final assumption does not hold for spoken Japanese and
languages such as English, but it is easy to extend our implementation
to handle these cases. Specifically, this can be done by changing the
constraint on heads from $d_i>i$ to $d_i \ne i$ and using
Chu-Liu/Edmonds' algorithm to ensure that no loops of dependencies are
created while building the maximum spanning tree for the
sentence. This algorithm has the additional benefit of handling all
types of non-projective dependencies. Because the proposed method for
learning feature weights from partially annotated data does not depend
on the parsing algorithm, different parsing algorithms could also be
used, for example to enforce projectivity constraints.


\subsection{Japanese dependency parsing}
\label{sec:japanese-depparse}

\citeA{kudo2000svm} also proposed a probabalistic parser for Japanese
which uses the assumption that edges can be estimated
independently. Their approach uses \textit{bunsetsu} (chunks) instead of words
and is limited to projective dependencies, but is otherwise similar to
the proposed method. The key difference is how context information is
used in their feature set. During both training and parsing,
information about dependencies for chunks between a candidate
dependent and head is used for determining whether a dependency exists
between them. These are called ``dynamic features'' because they are
updated dynamically during parsing as dependencies in the sentence are
estimated, in contrast to ``static'' features like POS tags, which
depend only on the input string and do not change. While features
based on surrounding dependencies are trivial to use during training,
such features are difficult to use during parsing because the
structure for the dependency tree is not known. Dynamic features are
updated as the dependency tree structure for the sentence is built
incrementally, allowing dependencies that have been finalized to be
used as information for those that have not. \citeA{kudo2000svm}
conclude that models with these dynamic features consistently
outperform those without them.

In contrast, our approach does not use estimated values such as these
dynamic features when determining whether a dependency exists between
a given pair of words when parsing. Instead, our feature set uses a
larger number of static features to capture context information. When
evaluating a potential dependency between a dependent and a head word,
surface forms and POS tags in a window of seven words for both are
used as features. Dependencies are estimated independently to enable
training from partial annotation.

Because \citeA{kudo2000svm}'s model assumes that edges are independent
of each other, it is theoretically possible to adapt it so that it can
use partially annotated training data. Dynamic features based on
chunks between a candidate dependent and head chunk are an important
part of their approach, so to annotate a single dependency for a pair
of chunks an annotator would have to annotate the heads for chunks in
between them. This makes partial annotation time-consuming for chunks
which are not adjacent.  \citeA{sassano2005} showed how partial
annotation can be used for Japanese dependency parsing, but only
considered partial annotations consisting of adjacent chunks for this
reason.

In our model it is sufficient to annotate individual dependencies
between words, so even long-distance dependencies are easy to use as
partial annotations. We leave the problem of finding an informative
criterion for selecting annotations for Japanese dependency parsing as
future work.



\section{Domain adaptation for dependency parsing}
\label{sec:adaptation}

Assuming that the cost of annotation corresponds roughly to the number of annotations performed, out
of all possible annotations to have annotators perform for a target domain corpus we want to select
the ones which provide the greatest benefit to accuracy when training. The high cost of annotation work is the
primary motivation for this approach.


\subsection{Partial annotation for a parser}

In the context of dependency parsing, partial annotation refers to annotating only certain
dependencies between words in a sentence. Dependencies which are assumed to have little to no value
for training are left unannotated. Table \ref{figure:features} shows an example of a partially annotated
sentence that can be used as training data by our system.

Before text can be annotated with dependencies, it must first be tokenized and
labeled with POS tags\footnote{We take a language-independent approach that does not make any
assumptions about the unit of tokenization or the meaning of tags used.}. We assume that the results
of this tokenization and POS tagging are accurate enough that we need to manually
annotate only the dependencies between the tokenized words.


\subsection{Learning feature weights from partial annotations}

As explained in \secref{sec:pointwisemst}, edge scores, $\sigma(\langle i, d_i \rangle, \Bdma{w})$, are estimated for each $w_i$
independently.  This means that the estimation of $\sigma(\langle i,d_i \rangle, \Bdma{w})$ requires only a gold dependency of
$w_i$, and the other dependencies in a sentence are not necessary.  This allows us to learn weights
$\Bdma{\theta}$ for features from partially annotated corpora.  When training data includes a gold
dependency that $w_i$ depends on $w_j$, a discriminative classifier can be trained by regarding
$d_i=j$ as a positive sample and $d_i=j'$ where $j'\ne j$ as negative samples.

In the case of Japanese parsing, because $j>i$ for all $d_i=j$, negative samples are
$d_i=j'$ where $j'\ne j$ and $j'>i$.  For example, from the partial annotation
given in Table \ref{figure:features}, we can create a training instance for $w_2$, は (\textit{subj.}),
where the positive sample is $d_2=8$ and the negative samples are $d_2 = 3, 4, \ldots,
7, 9$.


\subsection{Domain adaptation with a partially annotated training corpus}
\label{sec:conversion_rules}

As a case study, we show how partial annotation can be used as a low-cost method of converting the
annotation standard of an existing linguistic resource. As we mentioned in \secref{sec:introduction},
traditional frameworks for Japanese dependency parsing are phrase-based. Many existing dependency
corpora use phrases as the unit of annotation, and these resources are a valuable potential source
of data for mining word dependencies. However, phrase dependencies alone do not provide enough
information for an automatic conversion to word dependencies. One of the advantages of our parser is
that it can be trained on a partially annotated corpus, so if we can derive even some word
dependencies from phrase dependencies we can quickly and easily make use of existing resources.

To take advantage of these linguistic resources, we created a number of rules to derive word-based
dependency annotations from phrase-based annotations. Instead of trying to convert all phrase
dependencies, we focused on heuristics that provide only reliable word dependencies. The
word-based dependency set produced by these rules is a partial annotation of the original corpus.

For the domain adaptation experiments described in Section~\ref{sec:experiments}, we used this
procedure on the NAIST Text Corpus (NTC) \cite{iida2007} to create a small
partially-annotated target domain corpus. The NTC consists of newspaper articles from the Mainichi
Shimbun\footnote{In addition to phrase dependency annotations, the NTC also contains
  predicate-argument and coreference tags that are useful for deriving
  reliable word dependencies.}. \figref{figure:phrase} shows an example sentence from this corpus annotated with phrase
dependencies.

\begin{figure}[b]
\begin{center}
\includegraphics{19-3ia944f2.eps}
\end{center}
\caption{An example of phrase-based dependency annotation for a sentence}
\label{figure:phrase}
\end{figure}

To aid the construction of conversion rules, we chose three broad categories of words---content
words, function words, and punctuation symbols---that provide clues to the structure of a
phrase. Before we explain our rules, we will give a short explanation of these three categories.

We defined content words as nouns, verbs, adjectives, interjections, prenominal adjectives,
suffixes, and prefixes. Function words are auxiliary verbs, particles, inflections, and
conjunctions. In this context, punctuation symbols are both the English and Japanese versions of
period and comma characters. These three categories are used to determine phrases which can be mined
for relatively accurate word dependencies.

\figref{figure:conv} shows an example of how the rules explained below are used to derive word-based
dependencies from phrase-based dependencies for the sentence given in \figref{figure:phrase}.

\begin{figure}[t]
\begin{center}
\includegraphics{19-3ia944f3.eps}
\end{center}
\caption{An example of word-based dependencies derived from
  phrase-based dependencies for a sentence}
  \label{figure:conv}
\vspace{-0.5\Cvs}
\end{figure}

The first two rules are inter-phrase rules, which are concerned with the relationship between words
located in different phrases.

\begin{enumerate}
\item \ruleL: Given a dependent phrase and its head phrase in the original annotation, set the
  head of the last word in the dependent phrase to the last content word in the head phrase. Note,
  we only apply this rule if the head phrase consists of a content word followed by zero or more
  function words, followed by an optional punctuation symbol.
\item \ruleP: Set the head of a left parenthesis (or left bracket) to the first right parenthesis (or right
  bracket) that follows it in the sentence.

\end{enumerate}

The last four rules are intra-phrase rules that are concerned with the
dependencies between words in the same phrase. The following rules were found to be effective.

\begin{enumerate}
\setcounter{enumi}{2} 
\item \ruleS: If a phrase consists of zero or more content words, function words, or punctuation symbols
  followed by a sequence of two function words and a punctuation symbol, then set the head of the
  first function word in the sequence to the second function word and the head of the second
  function word to the punctuation symbol.
\item \ruleC: If a phrase consists of zero or more content words followed by a sequence of a
  content word and a function word, then set the head of the content word to the function word.
\item \ruleI: If a word that is inflected in Japanese (verb, auxiliary verb,
  or adjective\footnote{In Japanese there are two types of adjectives, {\it i}-type adjectives and {\it na}-type
adjectives. Both types are inflected.}) is followed by an inflection, the first word depends on the inflection.
\item \ruleF: If a function word is followed by a punctuation symbol, set the head of the function word
  to the punctuation symbol.

\end{enumerate}


\section{Evaluation}
\label{sec:experiments}

As an evaluation of our parser, 
we measured parsing accuracies of several systems on test corpora in
two domains: 
\pagebreak
one is a general domain in which a corpus fully annotated with word
boundary and dependency information is available, and the other is a target domain assuming an
adaptation situation in which only a partially annotated corpus is available for quick and low-cost
domain adaptation.



\subsection{Experimental settings}
\label{sec:experimental-settings}

In the experiments we used example sentences from a dictionary
\cite{Japanese-English.Sentence.Equivalents} as the general (source) domain data, and business
newspaper articles (Nikkei), similar to the Wall Street Journal, for the target domain test
set. Compared to the dictionary examples, the newspaper articles use a more formal writing style,
specialized vocabulary, and longer sentences. Thus, the domains of the two corpora are
different enough to justify domain adaptation techniques.

For the domain adaptation experiments, we used the partially-annotated corpus mentioned in
Section~\ref{sec:conversion_rules} as a target domain training corpus. This corpus consists of
newspaper articles that are similar to the target domain test set.

Usages and specifications of the various corpora are shown in \tabref{table:corpus}. All the
sentences are segmented into words manually and all the words are annotated with their heads
manually, except for NTC-train. The Japanese data provided by the CoNLL organizers
\cite{buchholz2006} are the result of an automatic conversion from phrase ({\it bunsetsu})
dependencies. For a more appropriate evaluation we have prepared a word-based dependency data set.

\begin{table}[b]
\caption{Sizes of Corpora.}
  \label{table:corpus}
\input{03table02.txt}
\end{table}

The dependencies have no labels because almost all nouns are connected to a verb with a case marker
and many important labels are obvious. The words are not annotated with POS tags,
so we used a Japanese POS tagger, KyTea \cite{neubig11aclshort}, trained on about 40~k sentences from
the Balanced Corpus of Contemporary Written Japanese (BCCWJ) \cite{maekawa08bccwj}.

For the general domain experiments we compared the following systems.

\begin{enumerate}
\item {\bf Malt}: \citeA{nivre2006maltparser}'s MaltParser. We chose the projective arc-eager
algorithm and {\sc HEAD} option (\texttt{-pp head}) to projectivize the training data because these
  settings\footnote{See \protect\url{http://www.maltparser.org/conll/conllx/} for details on the optimal
hyperparameter settings for Japanese. We also chose LIBLINEAR (with MaltParser's default choice of a
multi-class SVM) as the learner instead of LIBSVM, as recommended in the MaltParser optimization
  guide available at \linebreak\protect\url{http://www.maltparser.org/guides/opt/quick-opt.pdf} (links accessed April
2012).} achieved the best performance for Japanese on the CoNLL-X shared task
\cite{nivre2006labeled}.
\item {\bf 1st-order MST}: \citeA{mcdonald2005non}'s MST Parser, using the options for first-order
parsing, non-projective decoding, and $k$-best parse size with $k$=1. We chose the non-projective
decoding option for a fairer comparison with the proposed method, which does not enforce
projectivity constraints.
\item {\bf 2nd-order MST}: The same as 1st-order MST, but with the option for second-order parsing \cite{mcdonald2006online}.
\item {\bf EDA}: Our system (``Easily adaptable Dependency Analyzer''\footnote{Available at
  \url{http://plata.ar.media.kyoto-u.ac.jp/tool/EDA/}}), which uses pointwise estimation
  and first-order features to estimate dependencies. We used stochastic gradient descent for
  training.
\end{enumerate}


\subsection{With a fully annotated training corpus}
\label{sec:withFAC}

For the first experiment, we measured the accuracy of each system on an in-domain test set when
training on a fully annotated corpus. Our goal is to see how our method performs in comparison to
state-of-the art multilingual parsers when parsing Japanese. The results are shown in
\tabref{table:result-EHJ}. All systems achieve high accuracy on this task, and no differences
between systems were statistically significant ($p > 0.05$, according to Pearson's $\chi^2$
test). Malt and EDA have similar accuracy, while both variations of MST have only slightly lower
accuracy.

\begin{table}[b]
  \caption{Parsing Accuracy on EHJ-test.}
  \label{table:result-EHJ}
\input{03table03.txt}
\end{table}

Our model factors the score for a dependency tree into the sum of individual edge scores in the same
way as the 1st-order MST model, so we expected their performance to be close. The richer feature set
of our method is most likely the reason for the small difference in performance between EDA and
1st-order MST. This result shows that our pointwise approach achieves comparable accuracy on
Japanese to that of state-of-the art parsers while allowing for much more flexible use of language
resources. This flexibility is very important in practical situations.

In contrast, Malt and 2nd-order MST both use a history-based feature set, which incorporates more
context than the edge-factored approaches of EDA and 1st-order MST. In the case of Malt, the
partially built dependency structure of a sentence is used as features \cite{nivre2006maltparser},
which are similar to the ``dynamic features'' used by \citeA{kudo2000svm} and discussed in Section
\ref{sec:japanese-depparse}. As discussed in Section \ref{sec:first-order-second-order}, 2nd-order
MST factors the sentence into a set of edge pairs instead of individual edges.

We also measured the training time and the parsing speed of each system. \tabref{table:learning}
shows the results. From this table, first we see that both 1st-order and 2nd-order versions of MST
are much slower than Malt, as is well known. 2nd-order MST takes more than three times as long to train
as 1st-order MST, but their parsing speed is almost identical. The training time of our method is in
between Malt and both versions of MST---while it is much slower than the shift-reduce based Malt,
this result shows that our method is fast enough to be used for active learning. Training speed is
crucial for active learning because the annotator must wait while the model is retrained after each
round of annotation. \citeA{neubig11aclshort} demonstrated the effectiveness of the pointwise
approach in a realistic active learning scenario.

\begin{table}[b]
  \caption{Training Time and Parsing Speed.}
  \label{table:learning}
\input{03table04.txt}
\end{table}

Theoretically the training time of our method is proportional to the number of annotated
dependencies. The assumptions outlined in Section \ref{sec:solution-search} are most likely the main
reason for the difference in training times between EDA and the two versions of MST. For other
languages where possible heads can be located both to the left and right of a word, we expect
training and parsing times to increase. Our pointwise approach can be extended to handle these
languages by changing the constraint on heads from $j>i$ to $j \ne i$ for all $d_i=j$. This is an
important direction for future work now that we have confirmed that this approach is effective for
Japanese.

We performed a second experiment in the general domain to measure the impact of the training corpus
size on parsing accuracy. To make smaller training corpora, we set a fixed number of dependency
annotations and then sequentially selected sentences from EHJ-train until the desired number of
dependency annotations were collected. The results are shown in \figref{figure:ACC}. For smaller
training corpora Malt outperforms all other systems, but the difference is less pronounced when at
least half of the training corpus is used. The proposed method's performance lags behind the other
systems when little training data is available, but is comparable when at least half of the training
data is used. While 2nd-order MST outperforms 1st-order MST, the difference is not pronounced. This
is probably because dependency arcs in this data set always point to the right---in a standard
dependency parsing task where arcs may go in either direction, we expect 2nd-order MST to
consistently outperform 1st-order MST.

\begin{figure}[t]
  \begin{center}
  \includegraphics{19-3ia944f4.eps}
  \end{center}
  \caption{Comparison of parsing accuracy for different parsers}
  \label{figure:ACC}
\end{figure}



\subsection{Domain adaptation with a partially annotated training corpus}

Tasks that make use of parsers, such as machine translation \cite{yamada01syntaxbasedmt}, often
require word-based models. However, because phrase-based approaches have traditionally been used for
Japanese dependency parsing \cite{kudo2002,sassano2010using}, word-based linguistic resources for
Japanese are scarce. Preparing the fully annotated corpora required by existing word-based parsers
such as \citeA{mcdonald2005non}'s is an expensive and laborious task.

Our parser attempts to address these problems by introducing a word-based framework for
dependency parsing that can use partially annotated training data. Partial annotation is one way
to efficiently make use of existing resources in the target domain without incurring high annotation costs. 

We used each rule described in \secref{sec:conversion_rules} individually to convert the annotations
in the NTC-train and produce a pool of word-based dependencies. We then selected 5~k of those
dependencies to add to EHJ-train, and measured the results on NKN-test. We also used all rules
simultaneously to produce word-based dependencies and measured the results in the same way as the
individual rules. The total size of the partial annotation pool produced by using all rules was
248,148 dependencies out of 1,010,648 annotation candidates (not counting the last word of
sentences, which has no dependency). The baseline case only used the EHJ-train with no partial
annotations from the pool. The results are shown in \figref{figure:rules}.

\begin{figure}[b]
  \begin{center}
  \includegraphics{19-3ia944f5.eps}
  \end{center}
  \caption{Parsing Accuracy on NKN-test}
  \label{figure:rules}
\end{figure}

It can be seen that the \ruleL \ rule is the most effective, followed by the \ruleP \ rule. This suggests that the
long-distance dependencies provided by these rules are more useful for domain adaptation than the
short-distance dependency information that the intra-phrase rules provide.


Combining all of the rules increases the accuracy on NKN-test to 88.44\%, an increase of
2.75\% over the baseline. This combination of rules results in lower accuracy gains than the sum of the
gains from individual rules because different rules may convert the same phrase dependencies. These
results show that our pointwise approach allows for effective use of existing target domain
resources and increased parsing accuracy in the target domain through partial annotation.



\section{Comparison with a phrase-based dependency parser}
\label{sec:comp-with-phrase}

Because the phrase-based approach is the most commonly used in work on
Japanese dependency parsing, we also compared the performance of our
word-based method to a traditional phrase-based method, the cascaded
chunking approach of \citeA{kudo2002}. A direct comparison is
difficult because it would require data annotated with both word and
phrase dependencies. However, if a corpus is annotated with word
dependencies and POS tags, and we have an assignment of words to
phrases, it is possible to use heuristics to estimate the corresponding phrase
dependency annotations. This is because the information provided by
word dependencies is more fine-grained than the information provided
by phrase dependencies, and the former can be seen as a superset of
the latter. Phrase dependencies can be viewed as modeling only the
relationships among each phrase's key words, ignoring any dependency
information between words in the same
phrase. \figref{figure:word_cabocha} shows a sentence annotated with
word-based dependencies and POS tags which will be used to create
phrase dependency annotations.

\begin{figure}[b]
  \begin{center}
\includegraphics{19-3ia944f6.eps}
  \end{center}
  \caption{An example of word-based dependency annotation for a sentence}
  \label{figure:word_cabocha}
\end{figure}



\subsection{Converting word dependencies to phrase dependencies}
\label{sec:conv-word-depend}

The conversion is a two-step process: we first use only POS tags to
group words into phrases, and then we use dependencies between words
in different phrases to assign phrase dependencies. The second step is
straightforward because of our assumption that Japanese is
head-final. Just as in the case of word dependencies, when estimating
phrase dependencies we only consider heads which occur to the right of
their dependents and do not allow non-projective
dependencies. Therefore a single scan through all phrases in sentence
order is sufficient to assign their heads. For a given phrase, we
simply scan through each of its words in order, checking to see if the
word's head belongs to a different phrase than the current one. If it
does, we set the current phrase's head to the one containing the head
word and then begin processing the next phrase in the
sentence\footnote{We always choose the first available head for phrase
to avoid possible conflicts, though in practice these rarely
occurred.}. We stop processing when we reach the last phrase, because
by convention its head is the root.

The first step is more difficult and required us to develop some
heuristic rules. To formulate these rules, we made use of the idea
of function words and content words described in
\secref{sec:conversion_rules}. We used the same set of function words,
but we added pronouns and adverbs to the set of content words. This is
because we took a bottom-up approach to building phrases where we
incrementally add words to a phrase, deciding whether or not to insert
a phrase boundary after each word.

The basic procedure is as follows. We begin with an empty phrase and
then examine each word in order, considering whether or not to add it
to the current phrase. We first check to see whether the POS tag for
the word belongs to the set of function words. If the word's tag is
not in the set of function words, we add the word to the current
phrase. If the word is a prenominal adjective, adverb, conjunction,
or adverbial noun\footnote{Adverbial nouns are nouns which can also
function as adverbs by indicating a frequency or amount.}, we insert a
phrase boundary after the word. We refer to this set of words as
\emph{boundary words} because they are likely to indicate a phrase
boundary. On the other hand, if the word is in the set of function
words we add it to the current phrase and examine the next word,
adding it to the current phrase only if it is also a function
word. However, if the next word is a boundary word or there are no
more function words remaining in the sentence we insert a phrase
boundary between the first word and the next word.

The procedure outlined above will give us a coarse-grained phrase
segmentation for the sentence, but there are some edge cases which
require further segmentation of these phrases. We identified four of
these cases and checked each phrase created by the original
phrase segmentation against them. Note that in both the initial
coarse-grained phrase segmentation and the subsequent fine-grained
segmentation, before inserting a phrase boundary we check the
surrounding words to avoid splitting constructions commonly treated as
a single phrase in Japanese.

\begin{enumerate}
\item When a phrase contains a right quote or
  parenthesis followed by the corresponding left quote or parenthesis,
  insert a phrase boundary between them.
\item Insert a phrase boundary between a function word that is
  immediately followed by a content word.
\item When there is a noun or pronoun immediately followed by a verb, insert a
  phrase boundary between them. We do not apply this rule when
  the verb is する (to do) or a related verb, because this indicates
  that the noun is acting as a verbal noun.
\item When dictionary form of the verb する (to do) is followed by a
  noun, insert a phrase boundary between the two words.
\end{enumerate}


\figref{figure:phrase_cabocha} shows the result of applying the steps
outlined above to convert the word dependencies shown in
\figref{figure:word_cabocha} to phrase dependencies. After the
coarse-grained phrase segmentation the words in phrases 02 and 03 are
initially grouped into a single phrase. This phrase corresponds to case
(3) above because it contains the noun 全部 (all) followed by a verb,
so a phrase boundary is inserted between these two words.

\begin{figure}[t]
  \begin{center}
\includegraphics{19-3ia944f7.eps}
\end{center}
  \caption{An example of phrase-based dependencies derived from word dependencies}
  \label{figure:phrase_cabocha}
\end{figure}



\subsection{Evaluation on a phrase-based test set}
\label{sec:eval-phrase-based}

After both corpora were annotated with phrase dependencies, we
performed an experiment to measure the unlabeled phrase dependency
accuracy of the cascaded chunking method (CC) and the proposed method
(EDA). First, we converted the gold word-based dependencies for
EHJ-test to phrase-based dependencies. For EDA, we trained a parser as
described in \secref{sec:withFAC} and then converted the parser's
output on the word-based version of EHJ-test to phrase-based
dependencies. The same procedure was used to convert both the gold
dependencies and the parser output for the test set, ensuring that the
phrase segmentation was consistent between them. It should be noted
that the training and test data sets consist of example sentences from
a dictionary, which in general are much shorter than sentences from
common domains such as newspaper articles. Thus, the results on these
types of data sets are likely to differ from the ones we report below.

For CC, we first converted EHJ-train to phrase-based dependencies and
then used \citeA{kudo2002}'s implementation,
CaboCha\footnote{Available at \url{http://code.google.com/p/cabocha/}
  (accessed November 2011).}, to train a dependency parsing model. We
chose 3 as the degree of the polynomial kernel since this setting has
been demonstrated to be effective for Japanese dependency parsing
\cite{kudo2000svm,kudo2002}. We then used that model to parse the
phrase-based version of EHJ-test created from the gold word
dependencies. To ensure that the phrase segmentation and POS tags were
consistent for the test set, we did not use the phrase segmentation or
POS tagging features of their implementation.

\citeA{kudo2002}'s cascaded chunking approach uses the base feature
set of \citeA{kudo2000svm}'s probabalistic model (discussed in Section
\ref{sec:japanese-depparse}) and adds additional dynamic features
based on the chunks that modify the dependent chunk and the chunk
which the head chunk modifies. They report that the cascaded chunking
model requires fewer training examples and is thus much faster to
train than the probabalistic model, which uses all candidate
dependencies as training data. This is because the cascaded chunking
model uses heuristics to prune exceptional dependencies (where
possible correct heads are not selected because better one exists in
the same sentence or because of projectivity constraints) from the
training data. The training time for the proposed method is
theoretically longer than that of the cascaded chunking method,
because it uses a smaller unit (words instead of chunks) and uses all
candidate dependencies as training data in the same way as the
probabalistic model. However, for tasks like machine translation which
require smaller units than chunks, the fine-grained dependency
information of our approach is worth the additional training time.

\begin{table}[b]
  \caption{\emph{Bunsetsu} Parsing Accuracy on EHJ-test.}
  \label{table:cabocha_comparison}
\input{03table05.txt}
\end{table}

The results are shown in \tabref{table:cabocha_comparison}. Though
EDA's parsing speed is reasonably fast, CC's is much faster. It can
also be seen that EDA outperforms CC by a small margin in terms of
parsing accuracy\footnote{This improvement in accuracy is
statistically significant, with $p < 0.05$.}. Even though several of
the dependencies between words may be obvious, the word-based
dependency annotation provides us with richer information about the
structure of the sentence than phrase dependencies. One possible cause
for the difference in accuracy between CC and EDA is the POS tagging
standard. CC is designed to use a detailed set of fine-grained POS
tags, where broad categories such as nouns and verbs are further
separated into several subcategories. We use \citeA{maekawa08bccwj}'s
POS tagging standard, which defines both coarse-grained and
fine-grained tags. However, we only make use of the coarse-grained
tags because these are more likely to be available in a realistic
domain adaptation situation. Tagging words with fine-grained tags
requires annotators to have experience with the tagging standard in
addition to domain knowledge, which limits the number of potential
annotators. Sticking to coarse-grained tags reduces the burden on
annotators. Thus CC's accuracy suffers on this ``poor'' feature set
because fine-grained POS tags are not available. Another possible
cause for the differing accuracy may be the difference in granularity
between word-based and phrase-based segmentation. For the same
training data, there will be more examples of word dependencies than
phrase dependencies.





\section{Related work}

There has been a significant amount of work on how to utilize in-domain data to improve the accuracy
of parsing. The majority of this work has focused on using unlabeled data in combination with
self-training \cite{roark03parseradaptation,mcclosky06reranking} or other semi-supervised learning
methods \cite{blitzer06structuralcorrespondence,nivre07conll,suzuki09ssparsing}.

\citeA{roark03parseradaptation} also present work on supervised domain adaptation, although this
focuses on the utilization of an already-existing in-domain corpus.

There has also been some work on efficient annotation of data for parsing
\cite{tang02alparsing,osborne04ensemble,sassano2010using}. Most previous work focuses on picking
efficient sentences to annotate for parsing, but \citeA{sassano2010using} also present a method
for using partially annotated data with deterministic dependency parsers, which can be trivially
estimated from partially annotated data. Other recent work
\cite{spreyer2009incomplete,spreyer2010training} has shown how both \citeA{nivre2006maltparser}'s
MaltParser and \citeA{mcdonald2005non}'s MST Parser can be adapted to use partially annotated training
data.

Traditional parsers such as \citeA{mcdonald2005non}'s use structured prediction methods.
\citeA{wang2007simple} showed that local classification methods can be used to train structured
predictors. Their approach also uses ``dynamic'' features, where the predictions for some
surrounding edges are used as features when estimating a possible edge between a dependent and head
word.

Our parser also makes use of local classification methods for training, but in contrast to
\citeA{wang2007simple} we take a pointwise approach based on the assumption that edge scores can
be estimated independently. This work follows in the thread of \citeA{liang08structurecompilation}
and \citeA{neubig11aclshort}, who demonstrated that these assumptions can be made without a
significant degradation in accuracy for word segmentation and POS
tagging. Here we demonstrated that the same approach can be used for dependency parsing.



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

We introduced a parser that evaluates the score for each edge in a
dependency tree independently, which allows for the use of partially
annotated corpora in training. We demonstrated that target domain data
annotated in this way can be combined with available source domain
data to increase parsing accuracy in the target domain. We also showed
how partial annotation can be leveraged to make use of corpora in
different formats when a full conversion is not feasible.

In our evaluation on a Japanese dependency parsing task we found that
our parser delivers accuracy comparable to that of state-of-the-art
dependency parsers that use much more complex models, and has parsing
and training speeds that are fast enough to allow for rapid domain
adaptation. On a phrase-based Japanese dependency parsing task, our
word-based parser slightly outperformed a traditional phrase-based
parser. While our parser could not match the fast parsing speed of the
traditional one, the training speeds and accuracy of both were
comparable. The increased flexibility of simpler parsing models often
comes at the price of decreased accuracy, but these results show that
a simple model can be used to enable flexible domain adaptation
without sacrificing accuracy.




\acknowledgment

This work was supported by Grant-in-Aid for Scientific Research of the
government of Japan (23500177).

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

\bibitem[\protect\BCAY{Berger, Della~Pietra, \BBA\ Della~Pietra}{Berger
  et~al.}{1996}]{berger1996maximum}
Berger, A.~L., Della~Pietra, V.~J., \BBA\ Della~Pietra, S.~A. \BBOP 1996\BBCP.
\newblock \BBOQ A maximum entropy approach to natural language
  processing.\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 22}  (1), \mbox{\BPGS\
  39--71}.

\bibitem[\protect\BCAY{Blitzer, McDonald, \BBA\ Pereira}{Blitzer
  et~al.}{2006}]{blitzer06structuralcorrespondence}
Blitzer, J., McDonald, R., \BBA\ Pereira, F. \BBOP 2006\BBCP.
\newblock \BBOQ Domain Adaptation with Structural Correspondence
  Learning.\BBCQ\
\newblock In {\Bem Proceedings of the 2006 Conference on Empirical Methods in
  Natural Language Processing}, \mbox{\BPGS\ 120--128}.

\bibitem[\protect\BCAY{Buchholz \BBA\ Marsi}{Buchholz \BBA\
  Marsi}{2006}]{buchholz2006}
Buchholz, S.\BBACOMMA\ \BBA\ Marsi, E. \BBOP 2006\BBCP.
\newblock \BBOQ {CoNLL-X} Shared Task on Multilingual Dependency Parsing.\BBCQ\
\newblock In {\Bem Proceedings of the Tenth Conference on Computational Natural
  Language Learning (CoNLL-X)}, \mbox{\BPGS\ 149--164}.

\bibitem[\protect\BCAY{Gildea}{Gildea}{2001}]{gildea2001corpus}
Gildea, D. \BBOP 2001\BBCP.
\newblock \BBOQ Corpus Variation and Parser Performance.\BBCQ\
\newblock In {\Bem Proceedings of the 2001 Conference on Empirical Methods in
  Natural Language Processing}, \mbox{\BPGS\ 167--202}.

\bibitem[\protect\BCAY{Iida, Komachi, Inui, \BBA\ Matsumoto}{Iida
  et~al.}{2007}]{iida2007}
Iida, R., Komachi, M., Inui, K., \BBA\ Matsumoto, Y. \BBOP 2007\BBCP.
\newblock \BBOQ Annotating a {J}apanese Text Corpus with Predicate-argument and
  Coreference Relations.\BBCQ\
\newblock In {\Bem Proceedings of the Linguistic Annotation Workshop},
  \mbox{\BPGS\ 132--139}.

\bibitem[\protect\BCAY{Keene, Hatori, Yamada, \BBA\ Irabu}{Keene
  et~al.}{1992}]{Japanese-English.Sentence.Equivalents}
Keene, D., Hatori, H., Yamada, H., \BBA\ Irabu, S. \BBOP 1992\BBCP.
\newblock {\Bem {J}apanese-English Sentence Equivalents (in {J}apanese)\/}
  ({E}lectronic Book \BEd).
\newblock Asahi Press.

\bibitem[\protect\BCAY{Kudo \BBA\ Matsumoto}{Kudo \BBA\
  Matsumoto}{2000}]{kudo2000svm}
Kudo, T.\BBACOMMA\ \BBA\ Matsumoto, Y. \BBOP 2000\BBCP.
\newblock \BBOQ Japanese dependency structure analysis based on support vector
  machines.\BBCQ\
\newblock In {\Bem Proceedings of the 38th Annual Meeting of the Association
  for Computational Linguistics}, \mbox{\BPGS\ 18--25}.

\bibitem[\protect\BCAY{Kudo \BBA\ Matsumoto}{Kudo \BBA\
  Matsumoto}{2002}]{kudo2002}
Kudo, T.\BBACOMMA\ \BBA\ Matsumoto, Y. \BBOP 2002\BBCP.
\newblock \BBOQ {J}apanese dependency analysis using cascaded chunking.\BBCQ\
\newblock In {\Bem Proceedings of the Sixth Conference on Computational Natural
  Language Learning}, \lowercase{\BVOL}~25, \mbox{\BPGS\ 1--7}.

\bibitem[\protect\BCAY{Liang, Daum{\'e}~III, \BBA\ Klein}{Liang
  et~al.}{2008}]{liang08structurecompilation}
Liang, P., Daum{\'e}~III, H., \BBA\ Klein, D. \BBOP 2008\BBCP.
\newblock \BBOQ {Structure compilation: trading structure for features}.\BBCQ\
\newblock In {\Bem Proceedings of the 25th International Conference on Machine
  Learning}.

\bibitem[\protect\BCAY{Maekawa}{Maekawa}{2008}]{maekawa08bccwj}
Maekawa, K. \BBOP 2008\BBCP.
\newblock \BBOQ Balanced Corpus of Contemporary Written {Japanese}.\BBCQ\
\newblock In {\Bem Proceedings of the 6th Workshop on Asian Language
  Resources}, \mbox{\BPGS\ 101--102}.

\bibitem[\protect\BCAY{McClosky, Charniak, \BBA\ Johnson}{McClosky
  et~al.}{2006}]{mcclosky06reranking}
McClosky, D., Charniak, E., \BBA\ Johnson, M. \BBOP 2006\BBCP.
\newblock \BBOQ Reranking and Self-training for Parser Adaptation.\BBCQ\
\newblock In {\Bem Proceedings of the 44th Annual Meeting of the Association
  for Computational Linguistics}, \mbox{\BPGS\ 337--344}.

\bibitem[\protect\BCAY{McDonald \BBA\ Pereira}{McDonald \BBA\
  Pereira}{2006}]{mcdonald2006online}
McDonald, R.\BBACOMMA\ \BBA\ Pereira, F. \BBOP 2006\BBCP.
\newblock \BBOQ {Online Learning of Approximate Dependency Parsing
  Algorithms}.\BBCQ\
\newblock In {\Bem Proceedings of the Eleventh European Chapter of the
  Association for Computational Linguistics}, \lowercase{\BVOL}~6.

\bibitem[\protect\BCAY{McDonald, Pereira, Ribarov, \BBA\ Haji{\v{c}}}{McDonald
  et~al.}{2005}]{mcdonald2005non}
McDonald, R., Pereira, F., Ribarov, K., \BBA\ Haji{\v{c}}, J. \BBOP 2005\BBCP.
\newblock \BBOQ Non-projective Dependency Parsing Using Spanning Tree
  Algorithms.\BBCQ\
\newblock In {\Bem Proceedings of the 2005 Conference on Empirical Methods in
  Natural Language Processing}, \mbox{\BPGS\ 523--530}.

\bibitem[\protect\BCAY{Miyao, Sagae, Saetre, Matsuzaki, \BBA\ Tsujii}{Miyao
  et~al.}{2009}]{miyao09interactionextraction}
Miyao, Y., Sagae, K., Saetre, R., Matsuzaki, T., \BBA\ Tsujii, J. \BBOP
  2009\BBCP.
\newblock \BBOQ Evaluating Contributions of Natural Language Parsers to
  Protein-Protein Interaction Extraction.\BBCQ\
\newblock {\Bem Bioinformatics}, {\Bbf 25}  (3).

\bibitem[\protect\BCAY{Nakazawa \BBA\ Kurohashi}{Nakazawa \BBA\
  Kurohashi}{2008}]{nakazawa08linguistically}
Nakazawa, T.\BBACOMMA\ \BBA\ Kurohashi, S. \BBOP 2008\BBCP.
\newblock \BBOQ Linguistically-motivated tree-based probabilistic phrase
  alignment.\BBCQ\
\newblock In {\Bem Proceedings of the Eighth Conference of the Association for
  Machine Translation in the Americas (AMTA2008)}.

\bibitem[\protect\BCAY{Neubig \BBA\ Mori}{Neubig \BBA\ Mori}{2010}]{neubig2010}
Neubig, G.\BBACOMMA\ \BBA\ Mori, S. \BBOP 2010\BBCP.
\newblock \BBOQ Word-based Partial Annotation for Efficient Corpus
  Construction.\BBCQ\
\newblock In {\Bem Proceedings of the Seventh International Conference on
  Language Resources and Evaluation}.

\bibitem[\protect\BCAY{Neubig, Nakata, \BBA\ Mori}{Neubig
  et~al.}{2011}]{neubig11aclshort}
Neubig, G., Nakata, Y., \BBA\ Mori, S. \BBOP 2011\BBCP.
\newblock \BBOQ Pointwise Prediction for Robust, Adaptable {J}apanese
  Morphological Analysis.\BBCQ\
\newblock In {\Bem The 49th Annual Meeting of the Association for Computational
  Linguistics: Human Language Technologies Short Paper Track}.

\bibitem[\protect\BCAY{Nivre, Hall, K{\"u}bler, McDonald, Nilsson, Riedel,
  \BBA\ Yuret}{Nivre et~al.}{2007}]{nivre07conll}
Nivre, J., Hall, J., K{\"u}bler, S., McDonald, R., Nilsson, J., Riedel, S.,
  \BBA\ Yuret, D. \BBOP 2007\BBCP.
\newblock \BBOQ The {CoNLL} 2007 Shared Task on Dependency Parsing.\BBCQ\
\newblock In {\Bem Proceedings of the CoNLL Shared Task Session of EMNLP-CoNLL
  2007}.

\bibitem[\protect\BCAY{Nivre, Hall, \BBA\ Nilsson}{Nivre
  et~al.}{2006a}]{nivre2006maltparser}
Nivre, J., Hall, J., \BBA\ Nilsson, J. \BBOP 2006a\BBCP.
\newblock \BBOQ MaltParser: A Data-driven Parser-generator for Dependency
  Parsing.\BBCQ\
\newblock In {\Bem Proceedings of the Fifth International Conference on
  Language Resources and Evaluation}.

\bibitem[\protect\BCAY{Nivre, Hall, Nilsson, Eryi{\v{g}}it, \BBA\
  Marinov}{Nivre et~al.}{2006b}]{nivre2006labeled}
Nivre, J., Hall, J., Nilsson, J., Eryi{\v{g}}it, G., \BBA\ Marinov, S. \BBOP
  2006b\BBCP.
\newblock \BBOQ Labeled Pseudo-projective Dependency Parsing with Support
  Vector Machines.\BBCQ\
\newblock In {\Bem Proceedings of the Tenth Conference on Computational Natural
  Language Learning}, \mbox{\BPGS\ 221--225}.

\bibitem[\protect\BCAY{Nivre \BBA\ Scholz}{Nivre \BBA\
  Scholz}{2004}]{nivre2004deterministic}
Nivre, J.\BBACOMMA\ \BBA\ Scholz, M. \BBOP 2004\BBCP.
\newblock \BBOQ Deterministic Dependency Parsing of {English} Text.\BBCQ\
\newblock In {\Bem Proceedings of the 20th International Conference on
  Computational Linguistics}.

\bibitem[\protect\BCAY{Osborne \BBA\ Baldridge}{Osborne \BBA\
  Baldridge}{2004}]{osborne04ensemble}
Osborne, M.\BBACOMMA\ \BBA\ Baldridge, J. \BBOP 2004\BBCP.
\newblock \BBOQ Ensemble-based Active Learning for Parse Selection.\BBCQ\
\newblock In {\Bem Proceedings of the Human Language Technology Conference of
  the North American Chapter of the Association for Computational Linguistics},
  \mbox{\BPGS\ 89--96}.

\bibitem[\protect\BCAY{Petrov, Chang, Ringgaard, \BBA\ Alshawi}{Petrov
  et~al.}{2010}]{petrov2010uptraining}
Petrov, S., Chang, P.-C., Ringgaard, M., \BBA\ Alshawi, H. \BBOP 2010\BBCP.
\newblock \BBOQ Uptraining for Accurate Deterministic Question Parsing.\BBCQ\
\newblock In {\Bem Proceedings of the 2010 Conference on Empirical Methods in
  Natural Language Processing}, \mbox{\BPGS\ 705--713}.

\bibitem[\protect\BCAY{Roark \BBA\ Bacchiani}{Roark \BBA\
  Bacchiani}{2003}]{roark03parseradaptation}
Roark, B.\BBACOMMA\ \BBA\ Bacchiani, M. \BBOP 2003\BBCP.
\newblock \BBOQ Supervised and Unsupervised {PCFG} Adaptation to Novel
  Domains.\BBCQ\
\newblock In {\Bem Proceedings of the 2003 Human Language Technology Conference
  of the North American Chapter of the Association for Computational
  Linguistics}, \mbox{\BPGS\ 126--133}.

\bibitem[\protect\BCAY{Sassano}{Sassano}{2005}]{sassano2005}
Sassano, M. \BBOP 2005\BBCP.
\newblock \BBOQ Using a Partially Annotated Corpus to Build a Dependency Parser
  for {J}apanese.\BBCQ\
\newblock In {\Bem Proceedings of the Second International Joint Conference on
  Natural Language Processing}.

\bibitem[\protect\BCAY{Sassano \BBA\ Kurohashi}{Sassano \BBA\
  Kurohashi}{2009}]{sassano2009unified}
Sassano, M.\BBACOMMA\ \BBA\ Kurohashi, S. \BBOP 2009\BBCP.
\newblock \BBOQ A Unified Single Scan Algorithm for {J}apanese Base Phrase
  Chunking and Dependency Parsing.\BBCQ\
\newblock In {\Bem Proceedings of the Joint Conference of the 47th Annual
  Meeting of the Association for Computational Linguistics and the 4th
  International Joint Conference on Natural Language Processing of the AFNLP}.

\bibitem[\protect\BCAY{Sassano \BBA\ Kurohashi}{Sassano \BBA\
  Kurohashi}{2010}]{sassano2010using}
Sassano, M.\BBACOMMA\ \BBA\ Kurohashi, S. \BBOP 2010\BBCP.
\newblock \BBOQ {Using smaller constituents rather than sentences in active
  learning for {J}apanese dependency parsing}.\BBCQ\
\newblock In {\Bem Proceedings of the 48th Annual Meeting of the Association
  for Computational Linguistics}, \mbox{\BPGS\ 356--365}.

\bibitem[\protect\BCAY{Spreyer \BBA\ Kuhn}{Spreyer \BBA\
  Kuhn}{2009}]{spreyer2009incomplete}
Spreyer, K.\BBACOMMA\ \BBA\ Kuhn, J. \BBOP 2009\BBCP.
\newblock \BBOQ Data-Driven Dependency Parsing of New Languages Using
  Incomplete and Noisy Training Data.\BBCQ\
\newblock In {\Bem Proceedings of the Thirteenth Conference on Computational
  Natural Language Learning (CoNLL-2009)}, \mbox{\BPGS\ 12--20}.

\bibitem[\protect\BCAY{Spreyer, {\O}vrelid, \BBA\ Kuhn}{Spreyer
  et~al.}{2010}]{spreyer2010training}
Spreyer, K., {\O}vrelid, L., \BBA\ Kuhn, J. \BBOP 2010\BBCP.
\newblock \BBOQ Training parsers on partial trees: a cross-language
  comparison.\BBCQ\
\newblock In {\Bem Proceedings of the Seventh International Conference on
  Language Resources and Evaluation}.

\bibitem[\protect\BCAY{Suzuki, Isozaki, Carreras, \BBA\ Collins}{Suzuki
  et~al.}{2009}]{suzuki09ssparsing}
Suzuki, J., Isozaki, H., Carreras, X., \BBA\ Collins, M. \BBOP 2009\BBCP.
\newblock \BBOQ An Empirical Study of Semi-supervised Structured Conditional
  Models for Dependency Parsing.\BBCQ\
\newblock In {\Bem Proceedings of the 2009 Conference on Empirical Methods in
  Natural Language Processing}, \mbox{\BPGS\ 551--560}.

\bibitem[\protect\BCAY{Tang, Luo, \BBA\ Roukos}{Tang
  et~al.}{2002}]{tang02alparsing}
Tang, M., Luo, X., \BBA\ Roukos, S. \BBOP 2002\BBCP.
\newblock \BBOQ Active Learning for Statistical Natural Language Parsing.\BBCQ\
\newblock In {\Bem Proceedings of the 40th Annual Meeting of the Association
  for Computational Linguistics}, \mbox{\BPGS\ 120--127}.

\bibitem[\protect\BCAY{Tsuboi, Kashima, Mori, Oda, \BBA\ Matsumoto}{Tsuboi
  et~al.}{2008}]{tsuboi2008}
Tsuboi, Y., Kashima, H., Mori, S., Oda, H., \BBA\ Matsumoto, Y. \BBOP
  2008\BBCP.
\newblock \BBOQ Training Conditional Random Fields Using Incomplete
  Annotations.\BBCQ\
\newblock In {\Bem Proceedings of the 22th International Conference on
  Computational Linguistics}.

\bibitem[\protect\BCAY{Uchimoto, Sekine, \BBA\ Isahara}{Uchimoto
  et~al.}{1999}]{uchimoto1999japanese}
Uchimoto, K., Sekine, S., \BBA\ Isahara, H. \BBOP 1999\BBCP.
\newblock \BBOQ {J}apanese dependency structure analysis based on maximum
  entropy models.\BBCQ\
\newblock In {\Bem Proceedings of the Ninth European Chapter of the Association
  for Computational Linguistics}, \mbox{\BPGS\ 196--203}.

\bibitem[\protect\BCAY{Wang, Lin, \BBA\ Schuurmans}{Wang
  et~al.}{2007}]{wang2007simple}
Wang, Q.~I., Lin, D., \BBA\ Schuurmans, D. \BBOP 2007\BBCP.
\newblock \BBOQ Simple training of dependency parsers via structured
  boosting.\BBCQ\
\newblock In {\Bem Proceedings of the Twentieth International Joint Conference
  on Artificial Intelligence}.

\bibitem[\protect\BCAY{Yamada \BBA\ Knight}{Yamada \BBA\
  Knight}{2001}]{yamada01syntaxbasedmt}
Yamada, K.\BBACOMMA\ \BBA\ Knight, K. \BBOP 2001\BBCP.
\newblock \BBOQ A Syntax-Based Statistical Machine Translation Model.\BBCQ\
\newblock In {\Bem Proceedings of the 39th Annual Meeting of the Association
  for Computational Linguistics}.

\end{thebibliography}

\begin{biography}

\bioauthor[:]{Daniel Flannery}{
Daniel Flannery received his B.S. from Michigan State University in
2005. He is currently a masters student in the Graduate School of
Informatics at Kyoto University. His research interests include
dependency parsing and machine translation. He is a member of the
Association for Natural Language Processing.
}

\bioauthor[:]{Yusuke Miyao}{
Yusuke Miyao received his BSc and MSc from the University of Tokyo in
1998 and in 2000 respectively, and his PhD from the University of
Tokyo in 2006.  He has been a research associate at the University of
Tokyo from 2001, and an associate professor at the National Institute
of Informatics from 2010.  Member of Japan Association for Natural
Language Processing, Information Processing Society of Japan, Japan
Society for Artificial Intelligence, and Association for Computational
Linguistics. 
}

\bioauthor[:]{Graham Neubig}{
Graham Neubig received his B.S. from University of Illinois,
Urbana-Champaign, U.S.A, in 2005, and his M.E. and Ph.D. in
informatics from Kyoto University, Kyoto, Japan in 2010 and 2012
respectively. From 2012, he has served as an Assistant Professor at
the Nara Institute of Science and Technology. His research interests
include speech and natural language processing, with a focus on
unsupervised learning for applications such as automatic speech
recognition and machine translation.
}

\bioauthor[:]{Shinsuke Mori}{
Shinsuke Mori received his B.S., M.S., and Ph.D. in electrical
engineering from Kyoto University, Kyoto, Japan in 1993, 1995, and
1998, respectively. After joining the Tokyo Research Laboratory of
International Business Machines (IBM) in 1998, he studied language
modeling and its application to speech recognition and language
processing. He is currently an associate professor at the Academic Center
for Computing and Media Studies, Kyoto University. His research
interests include speech recognition and natural language
processing. He is a member of Japan Association for Natural Language
Processing, and the Information Processing Society of Japan.
}

\end{biography}

\biodate

\end{document}
