    \documentclass[english]{jnlp_1.4}

\usepackage{jnlpbbl_1.3}
\usepackage[dvipdfmx]{graphicx}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{hangcaption_jnlp}

\newcommand{\hyp}{}
    \newcommand{\shift}{}
    \newcommand{\lc}{}
    \newcommand{\attach}{}
    \newcommand{\eshift}{}
    \newcommand{\headempty}{}
    \newcommand{\head}{}
    \newcommand{\type}{}
    \newcommand{\ncat}{}
    \newcommand{\posi}{}
    \newcommand{\match}{}
    \newcommand{\free}{}
    \newcommand{\remcrd}{}
    \newcommand{\ch}{}
    \newcommand{\de}{}
    \newcommand{\pa}{}
    \newcommand{\cat}{}
    \newcommand{\np}{}
    \newcommand{\pp}{}
    \newcommand{\sbj}{}
    \newcommand{\vp}{}

\Volume{24}
\Number{3}
\Month{June}
\Year{2017}

\received{2016}{9}{9}
\revised{2016}{12}{2}
\accepted{2017}{1}{27}

\setcounter{page}{371}

\etitle{Left-Corner Parsing for Identifying PTB-Style \\
	Nonlocal Dependencies}
\eauthor{Yoshihide Kato\affiref{IC} \and Shigeki Matsubara\affiref{IS}}

\eabstract{
Nonlocal dependencies represent syntactic phenomenon such as wh-movement, A-movement in passives, topicalization, raising, control, and right node raising. Nonlocal dependencies play an important role in semantic interpretation. This paper proposes a left-corner parser that identifies nonlocal dependencies. Our parser integrates nonlocal dependency identification into a transition-based system. We adopt a left-corner strategy in order to use the syntactic relation c-command, which plays an important role in nonlocal dependency identification. To utilize the global features captured by nonlocal dependencies, our parser uses a structured perceptron. In experimental evaluations, our parser achieved a good balance between constituent parsing and nonlocal dependency identification.
}

\ekeywords{Transition-based Parsing, Structured Perceptron, C-command Relation}

\headauthor{Kato, Matsubara}
\headtitle{Left-Corner Parsing for Identifying Nonlocal Dependencies}

\affilabel{IC}{}{Information \& Communications, Nagoya University}
\affilabel{IS}{}{Graduate School of Information Science, Nagoya University}



\begin{document}

\maketitle

\section{Introduction}

Many constituent parsers based on the Penn Treebank \cite{Marcus1993} are available, but most of them cannot handle nonlocal dependencies,
which represent syntactic phenomenon such as wh-movement, A-movement in passives, topicalization, raising, control, and right node raising.
Nonlocal dependencies play an important role in semantic interpretation.
In the Penn Treebank, a nonlocal dependency is represented as a pair comprising an empty element and a filler.

Several methods of nonlocal dependency identification have been proposed to date.\footnote{Several methods of empty element detection, a subtask of nonlocal dependency identification, also have been proposed \cite{Cai:2011:ACL-HLT,Xue2013,Xiang2013,Takeno2015,Hayashi2016ACL}.}
These methods can be divided into three approaches:
pre-processing approaches \cite{Dienes:2003:EMNLP,Dienes:2003:ACL},
in-processing approaches \cite{Dienes:2003:ACL,Schmid:2006:COLING-ACL,Kato2015}, and
post-processing approaches \cite{Johnson:2002:ACL,Levy:2004:ACL,Campbell:2004:ACL}.
In the pre-processing approach, empty elements are detected by a tagger called ``trace tagger'', which uses only the surface word information.
The in-processing approach integrates nonlocal dependency identification into a parser, which rank candidate parse trees by a probabilistic context-free grammar.
The post-processing approach recovers the nonlocal dependencies from a parser output lacking these nonlocal dependencies.

The parsing models of previous methods cannot use the global features captured by nonlocal dependencies.
Pre- and in-processing approaches adopt a probabilistic context-free grammar, which does not easily incorporate global features.
The post-processing approach performs constituent parsing and nonlocal dependency identification separately.
Consequently, the constituent parser cannot use the information of nonlocal dependencies.

This paper\footnote{A preliminary version of this paper was presented at the 54th Annual Meeting of the Association for Computational Linguistics (ACL2016) by the same authors \cite{Kato2016}.}
proposes a parser that integrates nonlocal dependency identification into constituent parsing.
Our method adopts an in-processing approach, but without a probabilistic context-free grammar.
Our parser is based on a transition system with a structured perceptron \cite{Collins2002}, which can easily introduce global features to its parsing model.
We adopt a left-corner strategy in order to use the syntactic relation {\it c-command}, which plays an important role in nonlocal dependency identification.
In previous transition-based constituent parsers \cite{Sagae2005,Sagae2006,Zhang2009,Zhu2013,Wang2014,Mi2015,Thang2015,Watanabe2015,Ballesteros2015,Hayashi2016,Cross2016},
the c-command relations were difficult to capture in the parsing process.

Our contributions are summarized below:
\begin{enumerate}
 \item We introduce empty element detection into transition-based left-corner constituent parsing.
 \item We extend the c-command relation to deal with nodes in {\it parse tree stack} in the transition system.
       Based on this extended relation, we develop heuristic rules for co-indexing the empty elements with their fillers.
 \item We introduce new nonlocal dependency features into our parsing model.
\end{enumerate}

The remainder of this paper is organized as follows:
Section 2 explains the representation of nonlocal dependencies in the Penn Treebank, and Section 3 describes our transition-based left-corner parser.
Section 4 introduces nonlocal dependency identification into our parser.
Section 5 describes the structured perceptron and features.
Section 6 reports our experimental results, demonstrating the good balance between constituent parsing and nonlocal dependency identification achieved by our parser.
Section 7 concludes the paper.


\begin{figure}[b]
\begin{center}
\includegraphics{24-3ia3f1.eps}
\end{center}
\caption{A parse tree in the Penn Treebank}
\label{ex}
\end{figure}
\begin{table}[b]
\caption{Empty elements in the Penn Treebank}
\label{nld}
\input{03table01.txt}
\end{table}

\section{Nonlocal Dependency}

This section describes nonlocal dependencies in the Penn Treebank \cite{Marcus1993}.
A nonlocal dependency is represented as a pair of an {\it empty element} and a {\it filler}.
Figure~\ref{ex} shows a (partial) parse tree with several nonlocal dependencies, extracted from the Penn Treebank.
The nodes labeled with ${\tt \hyp NONE\hyp}$ are empty elements.
The terminal symbols such as ${\tt *}$ and ${\tt *T*}$ represent different types of nonlocal dependency
(an unexpressed subject of a to-infinitive and a trace of wh-movement, respectively).
When the terminal symbol of an empty element is indexed, its filler (with the same number) exists in the parse tree.
For example, the corresponding filler of ${\tt {*T*}\hyp 1}$ is the node ${\tt WHNP\hyp 1}$.
Table~\ref{nld} briefly describes the empty elements quoted from the annotation guideline \cite{Bies1995}.
More details are provided in the guideline.


\section{Transition-Based Left-Corner Parsing}

This section describes our transition-based left-corner parser.

The parsing actions of our parser are similar to those described in \citeA{Henderson2003}.
Here we define an action as a state-to-state mapping.
As in previous work \cite{Sagae2005,Sagae2006,Zhang2009,Zhu2013,Wang2014,Mi2015,Thang2015,Watanabe2015,Maier2015,Ballesteros2015,Hayashi2016,Cross2016},
our transition-based parsing system consists of a set of parser states and a finite set of transition actions, each of which maps a state into a new one.
A parser state consists of a stack of parse tree nodes and a buffer of input words.
A state is represented as a tuple $(\sigma,i)$, where $\sigma$ is the stack and $i$ is the position of the next input word in the buffer.
The initial state is $(\langle\rangle, 0)$.
The final states are in the form of $(\langle[\cdots]_{\tt TOP}\rangle, n)$, where ${\tt TOP}$ is a special symbol denoting the root of the parse tree and $n$ is the length of the input sentence.
Below, the notation $[\alpha]_X$ represents a node with label $X$ and children $\alpha$.
If the node is non-terminal, $\alpha$ is a list of nodes.
Otherwise, $\alpha$ is a terminal symbol.
Our parser performs the following transition actions:
\begin{itemize}
 \item $\shift(X)$:
       pop up the first word from the buffer, assign a POS tag $X$ to the word and push it onto the stack.
\end{itemize}
The {\sc Shift} action assigns a POS tag to the shifted word to simultaneously perform POS tagging and constituent parsing.
This is in the same way as \citeA{Wang2014}.
\begin{itemize}
 \item $\lc\hyp\headempty(X)$:
       pop up the first node from the stack, attach it with a new parent node labeled with $X$ and push it back onto the stack.
       
       {\sc H} and $\emptyset$ indicate whether or not the popped node is the head child of the new node.

 \item $\attach\hyp\headempty$:
       pop up the top two nodes from the stack, attach the first to the second as the rightmost child and push it back onto the stack.
       
       {\sc H} and $\emptyset$ indicate whether or not the first node is the head child of the second one.
\end{itemize}
The {\sc Attach} action is similar to the standard {\sc Reduce} action used in previous transition-based parsers.
However, there is an important difference between {\sc Attach} and {\sc Reduce}.
The {\sc Reduce} action cannot handle nodes with more than two children.
For this reason, the previous work converts parse trees into binarized ones.
This conversion makes it difficult to capture the hierarchical structure of the parse trees.
On the other hand, the {\sc Attach} action can handle more than two children.
Therefore, our parser does not require such kind of tree binarization.
The transition actions in our parser are summarized in Figure~\ref{action}.

To guarantee that every non-terminal node has exactly one head child, our parser imposes the following constraints:
\begin{itemize}
 \item $\lc$ and $\attach$ are not allowed when $s_0$ has no head child.
 \item $\attach\hyp\head$ is not allowed when $s_1$ has a head child.
\end{itemize}

Table~\ref{transition} shows the first several transition actions that derive the parse tree shown in Figure~\ref{ex}.
Superscript $^*$ indicates the head children.

\begin{figure}[b]
\begin{center}
\includegraphics{24-3ia3f2.eps}
\end{center}
\caption{Transition actions for left-corner parsing}
\label{action}
\end{figure}
\begin{table}[b]
\caption{Example of a transition action sequence}
\label{transition}
\input{03table02.txt}
\end{table}

Although most of the transition-based constituent parsers do not handle nonlocal dependencies,
there are two exceptions: one developed by \citeA{Maier2015}, the other by \citeA{Hayashi2016ACL}.
Maier proposes shift-reduce constituent parsing with swap action.
The parser can handle nonlocal dependencies represented as discontinuous constituents.
In this framework, discontinuities are directly annotated by allowing crossing branches.
As this annotation style cannot deal with one-to-many correspondences between fillers and empty elements,
the parser cannot identify any nonlocal dependency in which a filler is co-indexed with several empty elements.\footnote{Furthermore, the annotation style is unsuitable for nonlocal dependencies of type ${\tt *}$. In \citeA{Evang2011}, the PTB-style annotation of types ${\tt *EXP*}$, ${\tt *ICH*}$, ${\tt *RNR*}$, and ${\tt *T*}$ is transformed into an annotation with crossing branches by detaching each filler from a parse tree and reattaching it to the location of the corresponding empty element. If the transformation is applied to nonlocal dependencies of type ${\tt *}$, a problem arises. For example, in Figure~\ref{ex}, the information on the subject of ``managed'' is lost by detaching ${\tt NP\hyp SBJ\hyp 2}$.} 
Hayashi and Nagata integrated empty element detection into a transition-based spinal parser.
However, although their parser detects empty elements, it cannot find their corresponding fillers.


\section{Nonlocal Dependency Identification}

Nonlocal dependency identification consists of two subtasks:
\begin{itemize}
 \item empty element detection
 \item empty element resolution, which co-indexes empty elements with their fillers.
\end{itemize}
For empty element detection, our parser inserts empty elements at arbitrary positions similarly to in-processing approach.
Our method co-indexes empty elements with their fillers using simple heuristic rules developed for our transition system.


\vspace{0.5\Cvs}
\subsection{Empty Element Detection}

We introduce the following action to deal with empty elements:
\[
 \eshift(E,t): (\langle s_m,\ldots,s_0\rangle, i) \Rightarrow (\langle s_m,\ldots,s_0,[t]_E\rangle, i).
\]
This action simply inserts an empty element at an arbitrary position and pops up no element from the buffer
(for example, see the transition from \#11 to \#12 in Table~\ref{transition}).


\vspace{0.5\Cvs}
\subsection{Annotations}

For empty element resolution, we augment the Penn Treebank.
For the nonlocal dependency types ${\tt *EXP*}$, ${\tt *ICH*}$, ${\tt *RNR*}$, and ${\tt *T*}$, we assign the following information to each filler and each empty element:
\begin{itemize}
 \item The nonlocal dependency type (assigned to filler only).
 \item The nonlocal dependency category, defined as the category of the parent of the empty element.
 \item The relative position of the filler, which takes a value from $\{{\tt A}, {\tt L}, {\tt R}\}$.
       The relative position is ``${\tt A}$'' if the filler is an ancestor of the empty element, or ``${\tt L}$'' (``${\tt R}$'') if the filler occurs to the left (right) of the empty element.
       Table~\ref{nld} summarizes the allowed value for each empty element.
\end{itemize}
This information is utilized for co-indexing empty elements with fillers.
Below, we write $\type(x)$, $\ncat(x)$, and $\posi(x)$ for the information of a node $x$, respectively.

If an empty element of type ${\tt *}$ is indexed, it is annotated in the same way.\footnote{We omit its nonlocal dependency category, as it is always ${\tt NP}$.}
Furthermore, every empty element co-indexed to a constituent with no function tag ${\tt SBJ}$ is assigned a tag ${\tt OBJCTRL}$.\footnote{In the Penn Treebank, every subject has the tag ${\tt SBJ}$.}
This assignment enables our parser to distinguish between subject control and object control.

Figure~\ref{annotation} shows the augmented parse tree of Figure~\ref{ex}.

\begin{figure}[t]
\begin{center}
\includegraphics{24-3ia3f3.eps}
\end{center}
\caption{Augmented parse tree of Figure~\ref{ex}}
\label{annotation}
\end{figure}


\subsection{Empty Element Resolution}

Nonlocal dependency annotation in the Penn Treebank is based on Chomsky's GB-theory \cite{Chomsky1981}.
This means that there exist c-command relations between empty elements and fillers in many cases.
For example, all of the empty elements in Figure~\ref{ex} are c-commanded by their fillers.
Our method co-indexes the empty elements with their fillers by simple heuristic rules based on the c-command relation.


\subsubsection{C-command Relation}
\label{c-command}

Here, we define the c-command relation in a parse tree as follows:
\begin{itemize}
 \item A node $x$ {\it c-commands} a node $y$ if and only if there exists some node $z$ such that $z$ is a sibling of $x(x\neq z)$ and $y$ is a descendant of $z$.
\end{itemize}
Furthermore, we extend the c-command relation to handle nodes in a stack of our transition system.
For two nodes $x$ and $y$ in a stack, the following statement necessarily holds:
\begin{itemize}
 \item Let $S=(\langle s_m,\ldots , s_0\rangle, i)$ be a parser state.
       \begin{enumerate}
	\item Let $y$ be a node $s_j(0\leq j\leq m)$.
	      If $x$ is a child of some node $s_k(j<k\leq m)$, then $x$ c-commands $y$ in any final state derived from $S$.
	      The other nodes in the stack do not c-command $y$ in any final state derived from $S$.
	\item Let $y$ be a proper descendant of $s_j(0\leq j\leq m)$.
	      If $x$ is a child of some node $s_k(j<k\leq m)$, then $x$ c-commands $y$ in any final state derived from $S$.
	      Except $s_{j-1}$, none of the other nodes c-command $y$ in any final state derived from $S$.
	      If $s_{j-1}$ c-commands $y$ in some final state $S'$ derived from $S$,
	      then $s_{j-1}$ is attached to $s_j$ immediately after all children of $s_{j-1}$ are instantiated in the transition from $S$ to $S'$.
       \end{enumerate}
\end{itemize}
Below, we say that $x$ c-commands $y$ even when nodes $x$ and $y$ satisfy the above statement.

As an example, consider the state shown in Figure~\ref{control}.
The nodes are instantiated in order of their subscripts.
According to the above statement, the nodes in the dotted box c-command the shifted node ${\tt \hyp NONE\hyp{L}}_{14}$.
In the parse tree shown in Figure~\ref{annotation}, which is derived from this state, these nodes c-command ${\tt \hyp NONE\hyp{L}}_{14}$ under the original definition.

\begin{figure}[b]
\begin{center}
\includegraphics{24-3ia3f4.eps}
\end{center}
\caption{Example of resolution of $[*]_{\text{\ttfamily -NONE-L}}$}
\label{control}
\end{figure}

Previous transition-based constituent parsers cannot easily capture the c-command relations between nodes in a stack.
We first consider the case of shift-promote-adjoin constituent parsing \cite{Cross2016}.
The parser combines the top two nodes in a stack using two kinds of adjoin actions.
One action attaches the first node to the second node as a child,
the other attaches the second node to the first node as a child.
This means that the dominance relations (and consequently the c-command relations) between the nodes in the stack cannot be determined until the nodes are actually combined.
The same problem arises in transition-based spinal parsing \cite{Ballesteros2015,Hayashi2016}.
On the other hand, such problem does not occur in transition-based left-corner parsing,
because it is guaranteed that any node $s_j(0<j\leq m)$ dominates $s_{j-1}$ in any final state derived from $S=(\langle s_m,\ldots , s_0\rangle, i)$.

We next consider the case of shift-reduce constituent parsing \cite{Sagae2005,Sagae2006,Zhang2009,Zhu2013,Wang2014,Mi2015,Thang2015,Watanabe2015}.
Shift-reduce parsers combine the top two nodes in a stack using the reduce action, which generates a new node and attaches the two nodes as children to the generated node.
As these parsers cannot handle nodes with more than two children, the parse trees are converted into binarized trees by introducing {\it temporary} nodes,
which are collapsed and removed when detransforming the binarized trees into the original ones.
As an example, we focus on node $s_1$ in a stack $\langle s_2, s_1, s_0\rangle$.
After two consecutive reduce actions on the stack, we obtain a tree of the form $[s_2[s_1s_0]_{X}]_Y$.
If $X$ is temporary, the original form of the parse tree is $[s_2s_1s_0]_Y$, and $s_1$ c-commands the descendants of $s_2$.
If $X$ is not temporary, $s_1$ does not c-command the descendants of $s_2$.
Therefore, the c-command relation between nodes depends on whether the generated node is temporary or non-temporary.
Furthermore, it is notable that we must recognize $s_0$ to determine whether $s_1$ c-commands the descendants of $s_2$.
However, in left-corner parsing, whether or not $s_1$ c-commands the descendants of $s_2$ can be determined without recognizing $s_0$.
The corresponding transitions in left-corner parsing are as follows:
\begin{itemize}
 \item $(\langle s_2\rangle, i)\Rightarrow (\langle [s_2]_Y\rangle, i)\Rightarrow^* (\langle [s_2]_Y,s_1\rangle, i')\Rightarrow (\langle [s_2s_1]_Y\rangle, i')$
 \item $(\langle s_2\rangle, i)\Rightarrow (\langle [s_2]_Y\rangle, i)\Rightarrow^* (\langle [s_2]_Y,s_1\rangle, i')\Rightarrow (\langle [s_2]_Y,[s_1]_X\rangle, i')$
\end{itemize}
The first transition corresponds to the case of temporary $X$.
Clearly, $s_1$ c-commands the descendants of $s_2$.
In the second transition, the statement described in the first paragraph of this section guarantees that $s_1$ does not c-command the descendants of $s_2$.
In both transitions, $s_0$ is not yet recognized.


\subsubsection{Resolution Rules}
\label{identification}

When executing an {\sc E-shift} or {\sc Attach}, our parser co-indexes an empty element with its filler.
The {\sc E-shift} action co-indexes the shifted empty element $e$ such that $\posi(e)={\tt L}$ with its filler.
The {\sc Attach} action co-indexes the attached filler $s_0$ such that $\posi(s_0)={\tt R}$ with its corresponding empty element.
The resolution rules consist of three parts: {\sc Precondition}, {\sc Constraint}, and {\sc Select}.
Empty element resolution rule is applied to a state when the state satisfies {\sc Precondition} of the rule.
{\sc Constraint} represents the conditions which the co-indexed element must satisfy.
{\sc Select} takes two values, {\sc All} and {\sc Rightmost}.
When several elements satisfy {\sc Constraint}, {\sc Select} determines how to select co-indexed elements.
{\sc All} means that all of the elements satisfying the {\sc Constraint} are co-indexed, and {\sc Rightmost} selects the rightmost element satisfying the {\sc Constraint}.

The most frequent type of nonlocal dependency in the Penn Treebank is ${\tt *}$.
The resolution rules of this type are presented in Figure~\ref{rule*}.
Here, $\ch(s)$ designates the set of children of $s$.
$\sbj(x)$ means that $x$ has a function tag ${\tt SBJ}$.
$\pa(x)$ and $\cat(x)$ represent the parent and constituent category of $x$, respectively.
$\de(s)$ designates the set of proper descendants of $s$, and $\free(x,\sigma)$ denotes that $x$ is not co-indexed with any node in $\sigma$.

The first rule ${\tt *\hyp{L}}$ is applied to a state when the {\sc E-shift} action inserts an empty element $e=[{\tt *}]_{\tt \hyp NONE\hyp{L}}$.
This rule seeks a subject $x$ that c-commands the shifted empty element.
The first constraint means that the node $x$ c-commands the empty element $e$,
because the {\sc E-Shift} action generates the state $(\langle s_m,\ldots,s_0,e\rangle, i)$, and
$x$ and $e$ satisfy the statement in Section \ref{c-command}.
For example, the node ${\tt NP\hyp SBJ}_{10}$ in Figure~\ref{control} satisfies these constraints (the dotted box represents the first constraint).
Therefore, our parser co-indexes ${\tt NP\hyp SBJ}_{10}$ with ${\tt \hyp NONE\hyp{L}}_{14}$.

The second rule ${\tt *\hyp{L}\hyp{OBJCTRL}}$ seeks an object instead of a subject.
The second and third constraints identify whether or not $x$ is an argument.
If $x$ is a prepositional phrase, our parser co-indexes $e$ with the child noun phrase of $x$ rather than $x$ itself, to maintain the PTB-style annotation.

\begin{figure}[b]
\begin{center}
\includegraphics{24-3ia3f5.eps}
\end{center}
\caption{Resolution rules for type $*$}
\label{rule*}
\end{figure}
\begin{figure}[b]
\begin{center}
\includegraphics{24-3ia3f6.eps}
\end{center}
\caption{Example of resolution of $[*]_{\text{\ttfamily -NONE-R}}$}
\label{identify-ee}
\end{figure}

The third rule ${\tt *\hyp{R}}$ is for null subject of a participial clause.
Figure~\ref{identify-ee} demonstrates the application of rule ${\tt *\hyp{R}}$ to a state.
This rule is applied when the transition action is $\attach$ and $s_0$ is a subject.
By definition, the first constraint means that $s_0$ c-commands $x$.

The second most frequent type is ${\tt *T*}$.
Figure~\ref{rule*T*} shows the rule for ${\tt *T*}$.
This rule is applied to a state when the {\sc E-shift} action inserts an empty element of type ${\tt *T*}$.
Here, $\match(x,y)$ checks the consistency between $x$ and $y$; that is,
$\match(x,y)$ holds if and only if
$\type(x)=\type(y)$, $\ncat(x)=\ncat(y)$, $\posi(x)=\posi(y)$, $\cat(x)\neq{\tt \hyp{NONE}\hyp}$ and $\cat(y)={\tt \hyp{NONE}\hyp}$.
$\remcrd(\langle s_m,\ldots,s_0\rangle)$ is a stack which is obtained by removing $s_j(0\leq j\leq m)$ which is annotated with a tag ${\tt CRD}$.\footnote{The tag ${\tt CRD}$ is assigned to any node matching the pattern $[\cdots [\cdots]_X \cdots [\cdots]_{({\tt CC}|{\tt CONJP}|{\tt ,}|{\tt :})}\cdots [\cdots]_X \cdots]_X$.}
The tag ${\tt CRD}$ denotes that the node is a coordinate structure.
In general, each filler of type ${\tt *T*}$ is co-indexed with a single empty element.
However, a type ${\tt *T*}$ filler can be co-indexed with several empty elements if those empty elements are included in a coordinate structure.
This is the reason why our parser uses $\remcrd$.
Figures \ref{identify-wh} and \ref{coord} give examples of resolution for type ${\tt *T*}$.

\begin{figure}[b]
\begin{center}
\includegraphics{24-3ia3f7.eps}
\end{center}
\caption{Resolution rule for type $*\mathtt{T}*$}
\label{rule*T*}
\end{figure}
\begin{figure}[b]
\begin{center}
\includegraphics{24-3ia3f8.eps}
\end{center}
\caption{Example of resolution of $[*\mathtt{T}*]_{\text{\ttfamily -NONE-NP-L}}$}
\label{identify-wh}
\end{figure}

The empty elements $[{\tt *T*}]_{\tt \hyp{NONE}\hyp{A}}$ are handled by an exceptional process.
When an {\sc Attach} action is applied to a state $(\langle s_m,\ldots,s_0\rangle,i)$ such that $\cat(s_0)={\tt PRN}$,
the parser co-indexes the empty element $x=[{\tt *T*}]_{\tt\hyp{NONE}\hyp{A}}$ in $s_0$ with $s_1$.
More precisely, the co-indexation is executed if the following conditions hold:
\begin{itemize}
 \item $x\in\de(s_0)$
 \item $\match(s_1,x)$
 \item $\free(x,\langle s_m,\ldots,s_0\rangle)$
\end{itemize}

\begin{figure}[t]
\begin{center}
\includegraphics{24-3ia3f9.eps}
\end{center}
\caption{Example of resolution of $[*\mathtt{T}*]_{\text{\ttfamily -NONE-NP-L}}$ when the stack has a coordinate structure}
\label{coord}
\end{figure}

For the other types of nonlocal dependencies, that is, ${\tt *EXP*}$, ${\tt *ICH*}$, and ${\tt *RNR*}$, we use a similar idea to design the resolution rules.
Figure~\ref{rule-other} shows the resolution rules.

\begin{figure}[t]
\begin{center}
\includegraphics{24-3ia3f10.eps}
\end{center}
\caption{Resolution rules for $*\mathtt{EXP}*$, $*\mathtt{ICH}*$, and $*\mathtt{RNR}*$}
\label{rule-other}
\vspace{-1\Cvs}
\end{figure}

These heuristic resolution rules are similar to those described in the previous work \cite{Campbell:2004:ACL,Kato2015}, which also utilize the c-command relation.
However, whereas previous rules were designed for fully-connected parse trees, our heuristic rules apply to stacks of parse trees derived by left-corner parsing.
That is, the extended c-command relation plays an important role in our heuristic rules.


\section{Parsing with a Structured Perceptron}

We use a beam-search decoding with the structured perceptron \cite{Collins2002}.
A transition action $a$ for a state $S$ has a score defined as follows:
\[
score(S,a)={\bf w}\cdot{\bf f}(S,a),
\]
where ${\bf f}(S,a)$ is the feature vector for the state--action pair $(S,a)$, and ${\bf w}$ is a weight vector.
The score of a state $S'$ obtained by applying action $a$ to state $S$ is given by:
\[
 score(S')=score(S)+score(S,a).
\]
For the initial state $S_0$, $score(S_0)=0$.

We learn the weight vector ${\bf w}$ by the max-violation method \cite{Huang2012} and average the weight vector to avoid overfitting the training data \cite{Collins2002}.

In our method, action sequences for the same sentence have different number of actions because of {\sc E-Shift} action.
To absorb this difference, we use the {\sc Idle} action proposed in \citeA{Zhu2013}:
\[
\mbox{\sc Idle}: (\langle[\cdots]_{\tt TOP}\rangle, n) \Rightarrow
 (\langle[\cdots]_{\tt TOP}\rangle, n).
\]
Figure~\ref{beam-search} shows the details of our beam-search parsing.
The algorithm is identical to the previous transition-based parsing with structured perceptron.
However, here we must determine the maximum length $N$ of the action sequence allowed by the parser.
As the number of empty elements in a parse tree cannot be known in advance, this parameter must be set to a sufficiently large value.

\begin{figure}[t]
\begin{center}
\includegraphics{24-3ia3f11.eps}
\end{center}
\caption{Beam-search parsing}
\label{beam-search}
\end{figure}


\subsection{Features}
\label{feature}

A feature is defined as the concatenation of a transition action and a state feature extracted using a feature template.
Our baseline feature templates are presented in Table~\ref{template}.
These templates are similar to those of \citeA{Zhang2009}, which are standardly used as baseline templates for transition-based constituent parsing.
Here, $b_i$ and $s_i$ denote the $i$-th elements of the buffer and stack, respectively.
$x.{\tt c}$ represents the augmented label of $x$.
$x.{\tt l}$, $x.{\tt r}$, and $x.{\tt h}$ represent the leftmost, rightmost, and head children of $x$, respectively.
$x.{\tt t}$ and $x.{\tt w}$ represent the head POS tag and head word of $x$, respectively.
$x.{\tt i}$ indicates whether or not the initial letter of $x$ is capitalized.
When a non-terminal node has no head child, its head-based atomic features are set to a special symbol ${\tt nil}$.
To extract the features, we need to identify the head children in the parse trees.
For this purpose, we apply the head rules described in \citeA{Surdeanu2008}.

In addition to these features, we introduce a new feature related to empty element resolution.
When a transition action invokes the empty element resolution described in Section \ref{identification}, we use as a feature, whether or not the procedure co-indexes an empty element with a filler.
Such a feature is not easily captured by probabilistic context-free grammars.
This feature enables implicit learning of the resolution rule preferences, while the training process is performed only with oracle action sequences.

\begin{table}[t]
\caption{Baseline feature templates}
\label{template}
\input{03table03.txt}
\end{table}
\begin{table}[t]
\caption{Nonlocal dependency feature templates}
\label{nld-template}
\input{03table04.txt}
\end{table}

We also use the free empty elements and fillers as features.
These feature templates are summarized in Table~\ref{nld-template}.
Here, $x.{\tt n}_i$ denotes the $i$-th rightmost free element in $x$, and $rest_i$ is the stack $\langle s_m,\ldots,s_i\rangle$.


\section{Experiment}

We experimentally evaluated the performance of our parser on Penn Treebank data.
As the training, development and test data, we used sections 02--21, section 22 and section 23, respectively.

In the training phase, we set the beam size $k$ to 16 to achieve high efficiency.
We determined the optimal iteration number of perceptron training and the beam size ($k$ was set to 16, 32 and 64) for decoding on the development data.
The maximum length $N$ of the action sequences was set to $7n$, where $n$ is the length of the input sentence.
This maximum length was determined to deal with the sentences in the training data.

Table~\ref{parseval} presents the constituent parsing performances of our system and previous systems, evaluated by the labeled bracketing metric PARSEVAL \cite{Black1991}.
Here, ``CF'' is the parser learned from the training data without the nonlocal dependencies.
By removing these dependencies, we confirmed that our nonlocal dependency identification does not degrade the constituent parsing.
In transition-based constituent parsing, our left-corner parser is outperformed by other perceptron-based shift-reduce parsers.
On the other hand, our parser outperforms parsers that identify nonlocal dependencies by pre- and in-processing approaches.

\begin{table}[t]
\caption{Constituent parsing performances of our system and previous systems}
\label{parseval}
\input{03table05.txt}
\end{table}

We compared the parsing speeds (number of sentences parsed per second) of our parser and its CF version.
Our parser was implemented in CMUCL\footnote{https://www.cons.org/cmucl/} with a Xeon 3.47~GHz CPU.
The parsing speed was measured on the test data.
Our parser (1.22 sent./sec.) was slower than its CF version (1.87 sent./sec.).
We suspect that this is due to $\eshift$ action which increases the number of derived states.

The accuracy of nonlocal dependency identification was evaluated by the metric proposed in \citeA{Johnson:2002:ACL}.
Johnson's metric represents each nonlocal dependency as a tuple comprising
the type, category and position of the empty element, and the category and position of the filler.
For example, the type ${\tt *T*}$ nonlocal dependency in Figure~\ref{ex} is represented as $({\tt {*T*}}, {\tt NP}, [4,4], {\tt WHNP}, [3,4])$.
The precision and recall are measured using these tuples.
For more details, see \citeA{Johnson:2002:ACL}.

Table~\ref{comparison} shows the nonlocal dependency identification performances of our method and previous methods.
Previous in-processing approaches identified the nonlocal dependencies with state-of-the-art performance, but their constituent parsing accuracies were inferior.
In nonlocal dependency identification, our method fairly competed with previous in-processing approaches, while achieving more accurate constituent parsing.
Overall, our parser achieved a good balance between constituent parsing and nonlocal dependency identification.
Table~\ref{sum} summarizes the accuracies of different types of nonlocal dependencies identified by our parser.

\begin{table}[b]
\caption{Comparison for nonlocal dependency identification}
\label{comparison}
\input{03table06.txt}
\end{table}

Although the methods based on post-processing yield higher constituent parsing accuracy than our parser, their nonlocal dependency identifications are less accurate than ours,
partly because they do not reflect the nonlocal dependency features.
This is an intrinsic drawback of post-processing approaches.
Previous pre- and in-processing approaches yield relatively low constituent parsing accuracies,
probably because parsing models based on these approaches are probabilistic context-free grammars, which cannot easily capture the global features.
Finally, we compared our method with that proposed by \citeA{Kato2015}, which is similar to ours in many respects.
Both methods augment the Penn Treebank with nonlocal dependency information, and both employ a transition-based parser.
The main difference between them is that Kato and Matsubara's parser uses a probabilistic context-free grammar.
From the viewpoint of transition-based parsing, it has another drawback, that is, it cannot use look-ahead features.
Look-ahead features are useful not only in constituent parsing but also in nonlocal dependency identification.
For example, if the look-ahead word is ``to,'' it is a strong indicator that an empty element ${\tt *}$ should probably be inserted.
Our parser uses such kinds of features as shown in Section~\ref{feature}.

\begin{table}[t]
\caption{Accuracy of nonlocal dependency identification by our parser}
\label{sum}
\input{03table07.txt}
\vspace{4pt}\small
Evaluation was performed on all nonlocal dependencies occurring more than 5 times in section 23 of the Penn Treebank. $F$, $E$ and $T$ denote the filler category, empty element category, and type of nonlocal dependency, respectively.
\end{table}

Finally, to separately evaluate the empty element resolution rules proposed in Section \ref{identification},
we measured the precision and recall of nonlocal dependency identification when the oracle action sequences were given.\footnote{Note that the oracle action sequences insert empty elements correctly.}
The results are listed in Table~\ref{eval-rule}.
These results confirm the high accuracy of our resolution rules.

\begin{table}[t]
\hangcaption{Accuracy of nonlocal dependency identification by our parser when the oracle action sequences were given}
\label{eval-rule}
\input{03table08.txt}
\end{table}


\section{Conclusion}

This paper proposes a transition-based parser for nonlocal dependency identification.
Our parser achieves a good balance between constituent parsing and nonlocal dependency identification.
In the experiment reported in this paper, we used simple features captured by the nonlocal dependencies.
In future work, we will develop lexical features that are captured by nonlocal dependencies.

Another important issue is to compare our work with deep parsers based on different grammar formalisms, such as
the CCG-based parser \cite{Clark2007}, the HPSG-based parser \cite{Miyao2008} and the LFG-based parser \cite{Cahill2008}.
Because these parsers are not directly comparable to ours, the evaluation will largely follow that of \citeA{Miyao2004},
who evaluated deep parsers on PropBank data \cite{Palmer2005}.



\acknowledgment

This research was partially supported by the Grant-in-Aid for Scientific Research (B) \linebreak
(No.~26280082) of JSPS.

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

\bibitem[\protect\BCAY{Ballesteros \BBA\ Carreras}{Ballesteros \BBA\
  Carreras}{2015}]{Ballesteros2015}
Ballesteros, M.\BBACOMMA\ \BBA\ Carreras, X. \BBOP 2015\BBCP.
\newblock \BBOQ Transition-based Spinal Parsing.\BBCQ\
\newblock In {\Bem Proceedings of the 19th Conference on Computational Natural
  Language Learning}, \mbox{\BPGS\ 289--299}.

\bibitem[\protect\BCAY{Bies, Ferguson, Katz, \BBA\ MacIntyre}{Bies
  et~al.}{1995}]{Bies1995}
Bies, A., Ferguson, M., Katz, K., \BBA\ MacIntyre, R. \BBOP 1995\BBCP.
\newblock {\Bem Bracketing Guidelines for Treebank II Style Penn Treebank
  Project}.
\newblock University of Pennsylvania.

\bibitem[\protect\BCAY{Black, Abney, Flickenger, Gdaniec, Grishman, Harrison,
  Hindle, Ingria, Jelinek, Klavans, Liberman, Marcus, Roukos, Santorini, \BBA\
  Strzalkowski}{Black et~al.}{1991}]{Black1991}
Black, E., Abney, S., Flickenger, D., Gdaniec, C., Grishman, R., Harrison, P.,
  Hindle, D., Ingria, R., Jelinek, F., Klavans, J., Liberman, M., Marcus, M.,
  Roukos, S., Santorini, B., \BBA\ Strzalkowski, T. \BBOP 1991\BBCP.
\newblock \BBOQ A Procedure for Quantitatively Comparing the Syntactic Coverage
  of English Grammars.\BBCQ\
\newblock In {\Bem Proceedings of the 4th DARPA Speech and Natural Language
  Workshop}, \mbox{\BPGS\ 306--311}.

\bibitem[\protect\BCAY{Cahill, Burke, O'Donovan, Riezler, van \mbox{Genabith,} \BBA\
  Way}{Cahill et~al.}{2008}]{Cahill2008}
Cahill, A., Burke, M., O'Donovan, R., Riezler, S., van Genabith, J., \BBA\ Way,
  A. \BBOP 2008\BBCP.
\newblock \BBOQ Wide-coverage Deep Statistical Parsing using Automatic
  Dependency Structure Annotation.\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 34}  (1), \mbox{\BPGS\
  81--124}.

\bibitem[\protect\BCAY{Cai, Chiang, \BBA\ Goldberg}{Cai
  et~al.}{2011}]{Cai:2011:ACL-HLT}
Cai, S., Chiang, D., \BBA\ Goldberg, Y. \BBOP 2011\BBCP.
\newblock \BBOQ Language-Independent Parsing with Empty Elements.\BBCQ\
\newblock In {\Bem Proceedings of the 49th Annual Meeting of the Association
  for Computational Linguistics: Human Language Technologies}, \mbox{\BPGS\
  212--216}.

\bibitem[\protect\BCAY{Campbell}{Campbell}{2004}]{Campbell:2004:ACL}
Campbell, R. \BBOP 2004\BBCP.
\newblock \BBOQ Using Linguistic Principles to Recover Empty Categories.\BBCQ\
\newblock In {\Bem Proceedings of the 42nd Meeting of the Association for
  Computational Linguistics, Main Volume}, \mbox{\BPGS\ 645--652}.

\bibitem[\protect\BCAY{Charniak}{Charniak}{2000}]{Charniak2000}
Charniak, E. \BBOP 2000\BBCP.
\newblock \BBOQ A Maximum-Entropy-Inspired Parser.\BBCQ\
\newblock In {\Bem Proceedings of the 1st North American Chapter of the
  Association for Computational Linguistics}, \mbox{\BPGS\ 132--139}.

\bibitem[\protect\BCAY{Chomsky}{Chomsky}{1981}]{Chomsky1981}
Chomsky, N. \BBOP 1981\BBCP.
\newblock {\Bem Lectures on Government and Binding: The Pisa Lectures}.
\newblock Walter de Gruyter.

\bibitem[\protect\BCAY{Clark \BBA\ Curran}{Clark \BBA\
  Curran}{2007}]{Clark2007}
Clark, S.\BBACOMMA\ \BBA\ Curran, J.~R. \BBOP 2007\BBCP.
\newblock \BBOQ Wide-Coverage Efficient Statistical Parsing with CCG and
  Log-Linear Models.\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 33}  (4), \mbox{\BPGS\
  493--552}.

\bibitem[\protect\BCAY{Collins}{Collins}{2002}]{Collins2002}
Collins, M. \BBOP 2002\BBCP.
\newblock \BBOQ Discriminative Training Methods for Hidden Markov Models:
  Theory and Experiments with Perceptron Algorithms.\BBCQ\
\newblock In {\Bem Proceedings of the 2002 Conference on Empirical Methods in
  Natural Language Processing}, \mbox{\BPGS\ 1--8}.

\bibitem[\protect\BCAY{Cross \BBA\ Huang}{Cross \BBA\ Huang}{2016}]{Cross2016}
Cross, J.\BBACOMMA\ \BBA\ Huang, L. \BBOP 2016\BBCP.
\newblock \BBOQ Incremental Parsing with Minimal Features Using Bi-Directional
  LSTM.\BBCQ\
\newblock In {\Bem Proceedings of the 54th Annual Meeting of the Association
  for Computational Linguistics (Volume 2: Short Papers)}, \mbox{\BPGS\
  32--37}.

\bibitem[\protect\BCAY{Dienes \BBA\ Dubey}{Dienes \BBA\
  Dubey}{2003a}]{Dienes:2003:EMNLP}
Dienes, P.\BBACOMMA\ \BBA\ Dubey, A. \BBOP 2003a\BBCP.
\newblock \BBOQ Antecedent Recovery: Experiments with a Trace Tagger.\BBCQ\
\newblock In {\Bem Proceedings of the 2003 Conference on Empirical Methods in
  Natural Language Processing}, \mbox{\BPGS\ 33--40}.

\bibitem[\protect\BCAY{Dienes \BBA\ Dubey}{Dienes \BBA\
  Dubey}{2003b}]{Dienes:2003:ACL}
Dienes, P.\BBACOMMA\ \BBA\ Dubey, A. \BBOP 2003b\BBCP.
\newblock \BBOQ Deep Syntactic Processing by Combining Shallow Methods.\BBCQ\
\newblock In {\Bem Proceedings of the 41st Annual Meeting of the Association
  for Computational Linguistics}, \mbox{\BPGS\ 431--438}.

\bibitem[\protect\BCAY{Evang \BBA\ Kallmeyer}{Evang \BBA\
  Kallmeyer}{2011}]{Evang2011}
Evang, K.\BBACOMMA\ \BBA\ Kallmeyer, L. \BBOP 2011\BBCP.
\newblock \BBOQ PLCFRS Parsing of English Discontinuous Constituents.\BBCQ\
\newblock In {\Bem Proceedings of the 12th International Conference on Parsing
  Technologies}, \mbox{\BPGS\ 104--116}.

\bibitem[\protect\BCAY{Hayashi \BBA\ Nagata}{Hayashi \BBA\
  Nagata}{2016}]{Hayashi2016ACL}
Hayashi, K.\BBACOMMA\ \BBA\ Nagata, M. \BBOP 2016\BBCP.
\newblock \BBOQ Empty Element Recovery by Spinal Parser Operations.\BBCQ\
\newblock In {\Bem Proceedings of the 54th Annual Meeting of the Association
  for Computational Linguistics (Volume 2: Short Papers)}, \mbox{\BPGS\
  95--100}.

\bibitem[\protect\BCAY{Hayashi, Suzuki, \BBA\ Nagata}{Hayashi
  et~al.}{2016}]{Hayashi2016}
Hayashi, K., Suzuki, J., \BBA\ Nagata, M. \BBOP 2016\BBCP.
\newblock \BBOQ Shift-reduce Spinal TAG Parsing with Dynamic
  Programming.\BBCQ\
\newblock {\Bem Transactions of the Japanese Society for Artificial
  Intelligence}, {\Bbf 31}  (2), pp.~J-F83\_1--8.

\bibitem[\protect\BCAY{Henderson}{Henderson}{2003}]{Henderson2003}
Henderson, J. \BBOP 2003\BBCP.
\newblock \BBOQ Inducing History Representations for Broad Coverage Statistical
  Parsing.\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\ 24--31}.

\bibitem[\protect\BCAY{Huang, Fayong, \BBA\ Guo}{Huang
  et~al.}{2012}]{Huang2012}
Huang, L., Fayong, S., \BBA\ Guo, Y. \BBOP 2012\BBCP.
\newblock \BBOQ Structured Perceptron with Inexact Search.\BBCQ\
\newblock In {\Bem Proceedings of the 2012 Conference of the North American
  Chapter of the Association for Computational Linguistics: Human Language
  Technologies}, \mbox{\BPGS\ 142--151}.

\bibitem[\protect\BCAY{Johnson}{Johnson}{2002}]{Johnson:2002:ACL}
Johnson, M. \BBOP 2002\BBCP.
\newblock \BBOQ A Simple Pattern-matching Algorithm for Recovering Empty Nodes
  and their Antecedents.\BBCQ\
\newblock In {\Bem Proceedings of 40th Annual Meeting of the Association for
  Computational Linguistics}, \mbox{\BPGS\ 136--143}.

\bibitem[\protect\BCAY{Kato \BBA\ \mbox{Matsubara}}{Kato \BBA\
  Matsubara}{2015}]{Kato2015}
Kato, Y.\BBACOMMA\ \BBA\ Matsubara, S. \BBOP 2015\BBCP.
\newblock \BBOQ Identifying Nonlocal Dependencies in Incremental Parsing.\BBCQ\
\newblock {\Bem IEICE Transactions on Information and Systems}, {\Bbf E98-D}
  (4), \mbox{\BPGS\ 994--998}.

\bibitem[\protect\BCAY{Kato \BBA\ Matsubara}{Kato \BBA\
  Matsubara}{2016}]{Kato2016}
Kato, Y.\BBACOMMA\ \BBA\ Matsubara, S. \BBOP 2016\BBCP.
\newblock \BBOQ Transition-Based Left-Corner Parsing for Identifying
  PTB-Style Nonlocal Dependencies.\BBCQ\
\newblock In {\Bem Proceedings of the 54th Annual Meeting of the Association
  for Computational Linguistics (Volume 1: Long Papers)}, \mbox{\BPGS\
  930--940}.

\bibitem[\protect\BCAY{Levy \BBA\ Manning}{Levy \BBA\
  Manning}{2004}]{Levy:2004:ACL}
Levy, R.\BBACOMMA\ \BBA\ Manning, C. \BBOP 2004\BBCP.
\newblock \BBOQ Deep Dependencies from Context-Free Statistical Parsers:
  Correcting the Surface Dependency Approximation.\BBCQ\
\newblock In {\Bem Proceedings of the 42nd Meeting of the Association for
  Computational Linguistics, Main Volume}, \mbox{\BPGS\ 327--334}.

\bibitem[\protect\BCAY{Maier}{Maier}{2015}]{Maier2015}
Maier, W. \BBOP 2015\BBCP.
\newblock \BBOQ Discontinuous Incremental Shift-reduce Parsing.\BBCQ\
\newblock In {\Bem Proceedings of the 53rd Annual Meeting of the Association
  for Computational Linguistics and the 7th International Joint Conference on
  Natural Language Processing (Volume 1: Long Papers)}, \mbox{\BPGS\
  1202--1212}.

\bibitem[\protect\BCAY{Marcus, Santorini, \BBA\ Marcinkiewicz}{Marcus
  et~al.}{1993}]{Marcus1993}
Marcus, M.~P., Santorini, B., \BBA\ Marcinkiewicz, M.~A. \BBOP 1993\BBCP.
\newblock \BBOQ Building a Large Annotated Corpus of English: The Penn
  Treebank.\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 19}  (2), \mbox{\BPGS\
  310--330}.

\bibitem[\protect\BCAY{Mi \BBA\ Huang}{Mi \BBA\ Huang}{2015}]{Mi2015}
Mi, H.\BBACOMMA\ \BBA\ Huang, L. \BBOP 2015\BBCP.
\newblock \BBOQ Shift-Reduce Constituency Parsing with Dynamic Programming and
  POS Tag Lattice.\BBCQ\
\newblock In {\Bem Proceedings of the 2015 Conference of the North American
  Chapter of the Association for Computational Linguistics: Human Language
  Technologies}, \mbox{\BPGS\ 1030--1035}.

\bibitem[\protect\BCAY{Miyao \BBA\ Tsujii}{Miyao \BBA\
  Tsujii}{2004}]{Miyao2004}
Miyao, Y.\BBACOMMA\ \BBA\ Tsujii, J. \BBOP 2004\BBCP.
\newblock \BBOQ Deep Linguistic Analysis for the Accurate Identification of
  Predicate-Argument Relations.\BBCQ\
\newblock In {\Bem Proceedings of the 20th International Conference on
  Computational Linguistics}, \mbox{\BPGS\ 1392--1398}.

\bibitem[\protect\BCAY{Miyao \BBA\ Tsujii}{Miyao \BBA\
  Tsujii}{2008}]{Miyao2008}
Miyao, Y.\BBACOMMA\ \BBA\ Tsujii, J. \BBOP 2008\BBCP.
\newblock \BBOQ Feature Forest models for Probabilistic HPSG Parsing.\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 34}  (1), \mbox{\BPGS\
  35--80}.

\bibitem[\protect\BCAY{Palmer, Gildea, \BBA\ Kingsbury}{Palmer
  et~al.}{2005}]{Palmer2005}
Palmer, M., Gildea, D., \BBA\ Kingsbury, P. \BBOP 2005\BBCP.
\newblock \BBOQ The Proposition Bank: An Annotated Corpus of Semantic
  Roles.\BBCQ\
\newblock {\Bem Computational linguistics}, {\Bbf 31}  (1), \mbox{\BPGS\
  71--106}.

\bibitem[\protect\BCAY{Sagae \BBA\ Lavie}{Sagae \BBA\ Lavie}{2005}]{Sagae2005}
Sagae, K.\BBACOMMA\ \BBA\ Lavie, A. \BBOP 2005\BBCP.
\newblock \BBOQ A Classifier-Based Parser with Linear Run-Time
  Complexity.\BBCQ\
\newblock In {\Bem Proceedings of the 9th International Workshop on Parsing
  Technology}, \mbox{\BPGS\ 125--132}.

\bibitem[\protect\BCAY{Sagae \BBA\ Lavie}{Sagae \BBA\ Lavie}{2006}]{Sagae2006}
Sagae, K.\BBACOMMA\ \BBA\ Lavie, A. \BBOP 2006\BBCP.
\newblock \BBOQ A Best-First Probabilistic Shift-Reduce Parser.\BBCQ\
\newblock In {\Bem Proceedings of the COLING/ACL 2006 Main Conference Poster
  Sessions}, \mbox{\BPGS\ 691--698}.

\bibitem[\protect\BCAY{Schmid}{Schmid}{2006}]{Schmid:2006:COLING-ACL}
Schmid, H. \BBOP 2006\BBCP.
\newblock \BBOQ Trace Prediction and Recovery with Unlexicalized PCFGs and
  Slash Features.\BBCQ\
\newblock In {\Bem Proceedings of the 21st International Conference on
  Computational Linguistics and 44th Annual Meeting of the Association for
  Computational Linguistics}, \mbox{\BPGS\ 177--184}.

\bibitem[\protect\BCAY{Surdeanu, Johansson, Meyers, M\`{a}rquez, \BBA\
  Nivre}{Surdeanu et~al.}{2008}]{Surdeanu2008}
Surdeanu, M., Johansson, R., Meyers, A., M{\`{a}}rquez, L., \BBA\ Nivre, J. \BBOP
  2008\BBCP.
\newblock \BBOQ The CoNLL 2008 Shared Task on Joint Parsing of Syntactic and
  Semantic Dependencies.\BBCQ\
\newblock In {\Bem Proceedings of the 12th Conference on Computational Natural
  Language Learning}, \mbox{\BPGS\ 159--177}.

\bibitem[\protect\BCAY{Takeno, Nagata, \BBA\ Yamamoto}{Takeno
  et~al.}{2015}]{Takeno2015}
Takeno, S., Nagata, M., \BBA\ Yamamoto, K. \BBOP 2015\BBCP.
\newblock \BBOQ Empty Category Detection using Path Features and Distributed
  Case Frames.\BBCQ\
\newblock In {\Bem Proceedings of the 2015 Conference on Empirical Methods in
  Natural Language Processing}, \mbox{\BPGS\ 1335--1340}.

\bibitem[\protect\BCAY{Thang, Noji, \BBA\ Miyao}{Thang
  et~al.}{2015}]{Thang2015}
Thang, L.~Q., Noji, H., \BBA\ Miyao, Y. \BBOP 2015\BBCP.
\newblock \BBOQ Optimal Shift-Reduce Constituent Parsing with Structured
  Perceptron.\BBCQ\
\newblock In {\Bem Proceedings of the 53rd Annual Meeting of the Association
  for Computational Linguistics and the 7th International Joint Conference on
  Natural Language Processing (Volume 1: Long Papers)}, \mbox{\BPGS\
  1534--1544}.

\bibitem[\protect\BCAY{Wang \BBA\ Xue}{Wang \BBA\ Xue}{2014}]{Wang2014}
Wang, Z.\BBACOMMA\ \BBA\ Xue, N. \BBOP 2014\BBCP.
\newblock \BBOQ Joint POS Tagging and Transition-based Constituent Parsing in
  Chinese with Non-local Features.\BBCQ\
\newblock In {\Bem Proceedings of the 52nd Annual Meeting of the Association
  for Computational Linguistics (Volume 1: Long Papers)}, \mbox{\BPGS\
  733--742}.

\bibitem[\protect\BCAY{Watanabe \BBA\ Sumita}{Watanabe \BBA\
  Sumita}{2015}]{Watanabe2015}
Watanabe, T.\BBACOMMA\ \BBA\ Sumita, E. \BBOP 2015\BBCP.
\newblock \BBOQ Transition-based Neural Constituent Parsing.\BBCQ\
\newblock In {\Bem Proceedings of the 53rd Annual Meeting of the Association
  for Computational Linguistics and the 7th International Joint Conference on
  Natural Language Processing (Volume 1: Long Papers)}, \mbox{\BPGS\
  1169--1179}.

\bibitem[\protect\BCAY{Xiang, Luo, \BBA\ Zhou}{Xiang et~al.}{2013}]{Xiang2013}
Xiang, B., Luo, X., \BBA\ Zhou, B. \BBOP 2013\BBCP.
\newblock \BBOQ Enlisting the Ghost: Modeling Empty Categories for Machine
  Translation.\BBCQ\
\newblock In {\Bem Proceedings of the 51st Annual Meeting of the Association
  for Computational Linguistics (Volume 1: Long Papers)}, \mbox{\BPGS\
  822--831}.

\bibitem[\protect\BCAY{Xue \BBA\ Yang}{Xue \BBA\ Yang}{2013}]{Xue2013}
Xue, N.\BBACOMMA\ \BBA\ Yang, Y. \BBOP 2013\BBCP.
\newblock \BBOQ Dependency-based Empty Category Detection via Phrase Structure
  Trees.\BBCQ\
\newblock In {\Bem Proceedings of the 2013 Conference of the North American
  Chapter of the Association for Computational Linguistics: Human Language
  Technologies}, \mbox{\BPGS\ 1051--1060}.

\bibitem[\protect\BCAY{Zhang \BBA\ Clark}{Zhang \BBA\ Clark}{2009}]{Zhang2009}
Zhang, Y.\BBACOMMA\ \BBA\ Clark, S. \BBOP 2009\BBCP.
\newblock \BBOQ Transition-Based Parsing of the Chinese Treebank using a Global
  Discriminative Model.\BBCQ\
\newblock In {\Bem Proceedings of the 11th International Conference on Parsing
  Technologies}, \mbox{\BPGS\ 162--171}.

\bibitem[\protect\BCAY{Zhu, Zhang, Chen, Zhang, \BBA\ Zhu}{Zhu
  et~al.}{2013}]{Zhu2013}
Zhu, M., Zhang, Y., Chen, W., Zhang, M., \BBA\ Zhu, J. \BBOP 2013\BBCP.
\newblock \BBOQ Fast and Accurate Shift-Reduce Constituent Parsing.\BBCQ\
\newblock In {\Bem Proceedings of the 51st Annual Meeting of the Association
  for Computational Linguistics (Volume 1: Long Papers)}, \mbox{\BPGS\
  434--443}.

\end{thebibliography}

\begin{biography}
\bioauthor[:]{Yoshihide Kato}{
received the B.E. degree, the M.E. degree, and the Dr. of
Engineering degree in information engineering from Nagoya University,
in 1997, 1999, and 2003, respectively.
He was an Assistant Professor in Graduate School of International
Development, Nagoya University, from 2003 to 2009.
He was a Researcher at Information Technology Center, Nagoya University,
from 2009 to September 2011, and a Designated Assistant Professor, from October 2011 to March
2012.
He is currently an Associate Professor at Information \& Communications,
Nagoya University.
His research interests include natural language processing and
information retrieval.
He is a member of the IPSJ, the IEICE, and the ACL.
}

\bioauthor[:]{Shigeki Matsubara}{
received the B.E. degree in electrical and computer engineering from 
Nagoya Institute of Technology in 1993, and the M.E. degree, and the
Dr. of Engineering from Nagoya University in 1995 and 1998, respectively.
After becoming an Assistant Professor at Nagoya University,
he became an Associate Professor at Information Technology Center in
2002, and he is currently an Associate Professor in Graduate School of Information
Science.
His research interests include natural language processing, information
retrieval and digital library.
He is a member of the IPSJ, the JSAI, and the IEICE.
}

\end{biography}

\biodate



\end{document}
