    \documentclass[english]{jnlp_2.2}

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

\usepackage{bm}
\usepackage{multirow}
\usepackage{arydshln}
\newcommand{\argmax}{}


\Volume{26}
\Number{1}
\Month{March}
\Year{2019}

\received{2018}{8}{1}
\revised{2018}{10}{30}
\accepted{2018}{12}{10}

\setcounter{page}{83}

\esubject{Paper}
\etitle{A* CCG Parsing with a Supertag and Dependency Factored Model}
\eauthor{Masashi Yoshikawa\affiref{Author_1} \and Hiroshi Noji\affiref{Author_2} \and Yuji Matsumoto\affiref{Author_1}}
\eabstract{
Combinatory Categorial Grammar (CCG) is a strongly lexicalized grammatical formalism, in which the vast majority of parsing decisions involve assigning a supertag to indicate the correct syntactic role. We propose an A* parsing model for CCG that exploits this characteristics, by modeling the probability of a tree through the supertags and resolving the remaining ambiguities by its syntactic dependencies. The key of our method is that it predicts the probabilities of supertags and dependency heads independently using a strong unigram model defined over bi-directional LSTMs. The factorization allows precomputation of probabilities for all possible trees for a sentence, which, combined with an A* algorithm, enables very efficient decoding. The proposed model achieves the state-of-the-art results on English and Japanese CCG parsing. In addition, we conduct Recognizing Textual Entailment (RTE) experiments by integrating the proposed parser within logic-based RTE systems. We demonstrate that such integration leads to improved performance in English RTE experiments.
}
\ekeywords{Combinatory Categorial Grammar, Syntax, Parsing}

\headauthor{Yoshikawa, Noji, Matsumoto}
\headtitle{A* CCG Parsing with a Supertag and Dependency Factored Model}

\affilabel{Author_1}{}{Nara Institute of Science and Technology}
\affilabel{Author_2}{}{Artificial Intelligence Research Center, AIST}


\begin{document}

\maketitle

\section{Introduction}
\label{intro}

In lexicalized grammar parsing, supertagging is known as {\it almost parsing} \cite{bangalore1999supertagging}, in that each supertag is syntactically informative and most ambiguities are resolved once a correct supertag is assigned to each word.
Recently this property has been effectively exploited in A* CCG \cite{steedman:syntactic_process} parsing \cite{lewis-steedman:2014:EMNLP2014,lewis-lee-zettlemoyer:2016:N16-1},
in which the probability of a CCG tree ${\bm y}$ for sentence ${\bm x}$ of length $N$ is the product of the probabilities of supertags (categories) $c_i$ (locally factored model):
\begin{equation}
\label{lew}
P({\bm y} | {\bm x}) = \prod_{i \in [1,N]} P_{tag}(c_i | {\bm x}).
\end{equation}
By not modeling every combinatory rule in a derivation, this formulation enables us to employ an efficient A* search (Section \ref{related}) that finds the most probable supertag sequence that can construct a well-formed CCG tree.

Although supertagging can resolve considerable ambiguity, some ambiguity remains.
Figure~\ref{example} shows an example, where two CCG parses are derived from the same supertags.
Lewis et al. proposed an approach to this problem that involved a deterministic rule.
For example, motivated by the right-branching tendency of English, \cite{lewis-lee-zettlemoyer:2016:N16-1} employ the attach low heuristics, and always prioritizes the result shown in Figure~\ref{example}(b) for this type of ambiguity.
Though this approach works well for English empirically, an obvious limitation is that it does not always derive the correct parse.
For example, consider the phrase ``{\it a house in Paris with a garden}'', for which the structure of the correct parse corresponds to Figure~\ref{example}(a).

\begin{figure}[b]
\begin{center}
\includegraphics{26-1ia4f1.eps}
\end{center}
\hangcaption{CCG trees that are equally likely under Eq.~(\ref{lew}). The proposed model resolves this ambiguity by modeling the head of each word (dependencies).}
\label{example}
\end{figure}

In this paper, we provide a way to resolve these remaining ambiguities under the locally factored model by explicitly modeling bilexical dependencies, as shown in Figure~\ref{example}.\footnote{In English CCG parsing literature, the evaluation is performed in terms of ``semantic dependencies'', i.e., a meaning representation similar to predicate argument structure that is obtainable from a CCG parse tree. Some studies in the literature define ``{\it dependency models}'', where the optimization is done in terms of this meaning representation (Section~\ref{sec:related}). Our work is different in that we utilize ``syntactic dependencies'', a common syntactic representation in dependency parsing literature. In this work, unless otherwise stated, the term ``dependencies'' stands for syntactic dependencies.}
The proposed model is still locally factored so that an efficient A* search can be applied.
Here, the key idea is to predict the head of each word independently, as in Eq.~(\ref{lew}), using a strong unigram model. Here we utilize the scoring model employed in the recent successful graph-based dependency parsing on LSTMs \cite{TACL885,DBLP:journals/corr/DozatM16}.
Specifically, we extend the bi-directional LSTM (bi-LSTM) architecture of \cite{lewis-lee-zettlemoyer:2016:N16-1} to predict the supertag and head
of a word simultaneously using a bilinear transformation.

The importance of modeling structures beyond supertags is demonstrated by the performance gain reported by \cite{lee-lewis-zettlemoyer:2016:EMNLP2016}, which adds a recursive component to the model of Eq.~(\ref{lew}).
Unfortunately, compared to the original formulation, this formulation is less efficient because it must compute a recursive neural network each time it searches for a new node.
The proposed model does not resort to the recursive networks while modeling tree structures via dependencies.

We also extend the tri-training method of \cite{lewis-lee-zettlemoyer:2016:N16-1} to learn our model with dependencies from unlabeled data.
With this technique, on English CCGbank test data, the proposed model achieves 88.8\% and 94.0\% in terms of labeled and unlabeled F1, which mark the best scores so far.

In addition to English, we conducted experiments on Japanese CCG parsing.
In Japanese, word order is relatively free and is dominated by case markers; thus, a deterministic rule, such as the attach low method, may not work well.
The proposed method outperforms the simple application of \cite{lewis-lee-zettlemoyer:2016:N16-1} by a large margin, i.e., 10.0 points in terms of bunsetsu\footnote{A {\it bunsetsu} is a Japanese phrasal unit consisting of one or more adjoining content words (noun, verb, adjective, etc.) and zero or more functional words (postposition, auxiliary verb, etc.) \cite{bunsetsu}.} dependency accuracy.

CCG parsing is an important intermediate step of logic-based Recognizing Textual Entailment
(RTE) systems \cite{Bos:2008:WSA:1626481.1626503,mineshima-EtAl:2015:EMNLP,abzianidze:2017:EMNLP2017Demos}; thus,
CCG parsing accuracy significantly affects RTE results.
We evaluate the proposed method in terms of RTE by combining it with existing state-of-the-art RTE systems:
ccg2lambda \cite{mineshima-EtAl:2015:EMNLP} and LangPro \cite{abzianidze:2017:EMNLP2017Demos}.
We observe that it consistently leads to better recalls, showing that
it can parse a broader range of sentences robustly.


\section{Background}
\label{related}

Our work is built on A* CCG parsing (Section \ref{astar}),
which we extend in Section \ref{proposed} with a head prediction model based on bi-LSTMs (Section \ref{bi-dep}).
First, we briefly introduce CCG
and describe English and Japanese grammars adopted in this work (Section \ref{ccg_intro}).


\subsection{Combinatory Categorial Grammar}
\label{ccg_intro}

CCG \cite{bekki:book,steedman:syntactic_process} is a lexicalized grammatical formalism that is
characterized by categories with rich internal structures, and a limited number of derivational rules (combinatory rules).
A CCG category is either atomic ($S$, $N$, $NP$, etc.) or functional (complex),
where a complex category of the form $A/B$ (or $B\backslash A$) is equivalent to
a functional type $B \to A$, representing a function that returns a result of type $A$ when applied to an argument of type $B$.
A forward slash $/$ (or backward $\backslash$) indicates that the argument of type $B$ must appear to the right (or left) of that functor.
A category can be marked with {\it feature values}, such as ${\tt adj}$ in $S_{\tt adj}$,
which are rather language-specific, fine-grained controls over which pairs of categories can be combined
(See the documentation of respective CCGbanks for detailed specifications).

\begin{table}[b]
\caption{Set of common combinatory rules}
\label{general_binary_rules}
\input{04table01.tex}
\par\vspace{4pt}\small
Each English and Japanese parser developed in this work uses a subset of these rules.
A vertical $|$ bar can match both forward and backward slashes.
All $/$, $\backslash$ and $|$ are left-associative.
See the text and Appendices~\ref{appendix:english_grammar} and \ref{appendix:japanese_grammar} for details.
\end{table}
\begin{figure}[b]
\begin{center}
\includegraphics{26-1ia4f2.eps}
\end{center}
\hangcaption{Example CCG derivation for a complex coordination structure, where type raising $<\!tr\!>$ and forward composition $>\!\!{\bf B}^1$ play important roles.}
\label{example_ccg_tree}
\end{figure}

In Table~\ref{general_binary_rules}, the forward application, denoted as $>$, is a basic combinatory rule that
combines categories $X/Y$ and $Y$ (occurring in this order) into $X$.
Note that, in Table~\ref{general_binary_rules}, a $\lambda$-term is assigned to each category, as in ``$X/Y : \lambda x.f (x)$''.
One of the notable features of CCG is that it provides a transparent interface to semantic theories,
i.e., a meaning representation of a sentence is constructed concurrently with a derivation.
This is the fundamental principle that most of the logic-based RTE systems, some of which we evaluate in the RTE experiments,
are based on (Section~\ref{rte_experiment}).
Figure~\ref{example} shows an example CCG derivation using forward (and similarly defined backward $<$) application.
Conventionally, a CCG derivation is drawn top-down, resembling a proof diagram in natural deduction \cite{natded}.
Since we are particularly interested in the construction algorithm of derivations,
$\lambda$-terms are omitted when they are not relevant.
Figure~\ref{example_ccg_tree} shows a derivation (using combinatory rules explained below),
where a meaning representation is constructed according to the derivation.

Forward and backward composition rules ($>\!\!{\bf B}^1$ and $<\!\!{\bf B}^1$) and
their crossed variants ($>\!\!{\bf B}^1_{\times}$ and $<\!\!{\bf B}^1_{\times}$)
compose a pair of complex categories (the third through sixth rows in Table~\ref{general_binary_rules});
you can see from the operation performed on the $\lambda$-terms
that they literally correspond to function composition $f \circ g$.
They can be generalized to $n \geq 2$ (in the last four rows),
where a vertical bar $|$ means that it can be either of $/$ or $\backslash$.
Many elegant CCG analyses for complex syntactic phenomena employ composition rules;
Figure~\ref{example_ccg_tree} is one of such cases, where forward composition married with a unary {\it type raising rule}
($X \Rightarrow Y\backslash (Y/X)$, denoted as $<\!\!tr\!\!>$) explains a complex coordination structure.
Composition rules are also employed to capture phenomena that involve long-range dependencies, such as {\it wh}-extraction.

Following \cite{lewis-steedman:2014:EMNLP2014},
our English parser uses the standard binary rules from \cite{steedman:taking_scope}:
{\it forward and backward application}~($>$, $<$),
{\it (generalized) forward composition}~($>\!\!{\bf B}^n$ for $n \in \{1, 2\}$) and
{\it (generalized) backward crossed composition}~($<\!\!{\bf B}^n_{\times}$ for $n \in \{1, 2\}$).
In addition, the parser uses five binary rules that include a coordination-specific {\it conjunction} rule ($<\!\!\Phi\!\!>$)
and exactly the same set of unary rules in \cite{lewis-steedman:2014:EMNLP2014}, including type raising.
Note that the complete set of combinatory rules is summarized in Appendix~\ref{appendix:english_grammar}.

In Japanese CCG parsing, we use the set of binary rules found in the annotation of Japanese CCGbank, which basically follows \cite{bekki:book}:
{\it forward and backward application}~($>$, $<$),
{\it forward and backward composition}~($>\!\!{\bf B}^1$, $<\!\!{\bf B}^1$),
{\it generalized backward composition}~($<\!\!{\bf B}^n$ for $n \in \{2,3,4\}$),
{\it generalized forward crossed composition}~($>\!\!{\bf B}^n_{\times}$ for $n \in \{2,3\}$),
and a ``{\it SSEQ}'' rule.
{\it SSEQ} is rather specific to the corpus, where multiple sentences can occur within a ``sentence'' when they are quoted:

\begin{quotation}
「 $[_{\it S}$~$[_{\it S}$ 突然家が崩れ、着のみ着のまま飛びだした。$]$~$[_{\it S}$ 生きているのが不思議 $]]$ 」と話した。
(translation: ``The house collapsed all of a sudden and I ran out with nothing but the clothes on my back. I cannot believe that I am still alive'', he said.)
\end{quotation}
In this example, the SSEQ rule performs $S~S \Rightarrow S$.
For the unary rules, we select rules based on frequencies in the CCGbank.
Most rules are related to sentential noun modifiers
that turn a sentence-like category ($S$ and $S\backslash NP$) into a nominal modifier ($N/N$).
A complete list of the rules used is provided in Appendix~\ref{appendix:japanese_grammar}.

While the strong expressivity of CCG plays various crucial roles in the analysis of complex constructions,
it also comes at a cost, i.e., it introduces {\it spurious ambiguity}. For example, ``{\it Kyle hates}'' is licensed as a constituent (Figure~\ref{example_ccg_tree}); thus, it can be combined
with ``{\it ziplining}'' to derive exactly the same interpretation as a derivation that combines ``{\it hates ziplining}'' first.
To avoid combinatorial explosion during parsing, a technique called {\it normal form parsing} \cite{P96-1011,C10-1053},
which imposes constraints such that only ``normal-form'' derivations are produced, has been developed.
One of the findings of this work is that the proposed dependency-augmented model can automatically learn softened versions of such constraints.
Experimental results demonstrate that, compared to baseline methods, even though the constraints are not given
explicitly, the proposed parser violates the constraints significantly fewer times.


\subsection{Supertag-factored A*~CCG Parsing}
\label{astar}

CCG has a nice property that every category is highly informative about attachment decisions and
assigning it to every word~({\it supertagging}) resolves most of its syntactic structure.
A previous work \cite{lewis-steedman:2014:EMNLP2014} utilizes this characteristics of the grammar.
Let a CCG tree ${\bm y}$ be a list of categories $\langle c_1, \ldots, c_N \rangle$ and a derivation on it.
Their model looks for the most probable ${\bm y}$ given sentence ${\bm x}$ of length $N$ from the set $Y({\bm x})$ of possible CCG trees under the model of Eq.~(\ref{lew}):
\[
\hat{{\bm y}} = \argmax_{{\bm y} \in Y({\bm x})} \sum_{i \in [1,N]} \log P_{tag}(c_i | {\bm x}).
\]
Since this score is factored into each supertag, they call the model a {\it supertag-factored} model.

Exact inference of this problem is possible by A* parsing \cite{klein:a_star}, which uses the following two scores on a chart:
\begin{align*}
b(C_{i,j}) & =  \sum_{c_k \in {\bm c}_{i,j}} \log P_{tag}(c_k | {\bm x}), \\
a(C_{i,j}) & =  \sum_{k \in [1,N] \setminus [i, j]} \max_{c_k} \log P_{tag}(c_k | {\bm x}),
\end{align*}
where $C_{i,j}$ is a chart item called an {\it edge}, which abstracts parses spanning interval $[i,j]$ rooted by category $C$.
The chart maps each edge to the derivation with the highest score, i.e., the Viterbi parse for $C_{i,j}$.
${\bm c}_{i,j}$ is the sequence of categories for such a Viterbi parse, and thus $b$ is called the Viterbi inside score, while $a$ is the approximation (upper bound) of the Viterbi outside score.

A* parsing is a kind of CKY chart parsing augmented with an agenda,
a priority queue that keeps the edges to be explored.
At each step it pops the edge $e$ with the highest priority $b(e) + a(e)$, inserts that into the chart, and enqueues any edges that can be
built by combining $e$ with other edges in the chart.
The algorithm terminates when an edge $C_{1,N}$ is popped from the agenda.

The A* search in this model is quite efficient because both $b$ and $a$ can be obtained from the unigram category distribution on all words, which can be precomputed prior to a search.
The heuristics $a$ gives an upper bound on the true Viterbi outside score (i.e., admissible).
In addition, the condition that the inside score never increases by expansion (monotonicity) guarantees that the first found derivation on $C_{1,N}$ is always optimal.
$a(C_{i,j})$ matches the true outside score if the one-best category assignments on the outside words ($\arg\max_{c_k} \log P_{tag}(c_k | {\bm x})$) can comprise a well-formed tree with $C_{i,j}$, which is generally not true.


\subsubsection{Scoring Model}

For modeling $P_{tag}$, a log-linear model with features from a fixed window context is used in \cite{lewis-steedman:2014:EMNLP2014}.
Later, the log-linear model is extended with bi-LSTMs, which encode the complete sentence and capture the long range syntactic information \cite{lewis-lee-zettlemoyer:2016:N16-1}.
We base the proposed model on this bi-LSTM architecture and extend it such that a head word can be modeled simultaneously.


\subsubsection{Attachment Ambiguity}
\label{sec:attachment_ambiguity}

In an A* search, an edge with the highest priority $b+a$ is searched first; however, as shown in Figure~\ref{example} the same categories (with the same priority) may sometimes derive more than one tree.
In \cite{lewis-steedman:2014:EMNLP2014}, they prioritize the parse with longer dependencies, which they determine using a conversion rule from a CCG tree to a dependency tree (Section \ref{conversion}).
It is later replaced with another heuristics that prioritizes low attachments of constituencies \cite{lewis-lee-zettlemoyer:2016:N16-1};
however inevitably these heuristics cannot be flawless in any situations.
We provide a simple solution to this problem by modeling bilexical dependencies explicitly.


\subsection{Bi-LSTM Dependency Parsing}
\label{bi-dep}

To model dependencies, we borrow the idea from the recent graph-based neural dependency parsing \cite{TACL885,DBLP:journals/corr/DozatM16} where each dependency arc is scored directly on the outputs of bi-LSTMs.
Although the model is first-order, bi-LSTMs enable conditioning on the entire sentence and lead to the state-of-the-art performance.
Note that this mechanism is similar to modeling of the supertag distribution discussed above, in that, for each word, the distribution of the head choice is unigram and can be precomputed.
As we will see this keeps our joint model still locally factored and A* search tractable.
For score calculation, we use an extended bilinear transformation proposed by \cite{DBLP:journals/corr/DozatM16} that models the headness of each token as well, which they call {\it biaffine}.



\section{Proposed Method}
\label{proposed}

\subsection{A* parsing with Supertag and Dependency Factored Model}
\label{proposedastar}

We define a CCG tree ${\bm y}$ for sentence ${\bm x}=\langle x_i, \ldots, x_N \rangle$
as a triplet of a list of CCG categories ${\bm c}=\langle c_1, \ldots, c_N \rangle$,
dependencies ${\bm h}=\langle h_1, \ldots, h_N \rangle$, and the derivation,
where $h_i \in [0, N]$ is the head index of $x_i$ (0 is the index for the root token).
The proposed model is defined as follows:
\begin{equation}
\label{our_model}
P({\bm y} | {\bm x})  = \prod_{i \in [1,N]} P_{tag}(c_i | {\bm x}) \prod_{i \in [1,N]} P_{dep}(h_i | {\bm x}).
\end{equation}
The added term $P_{dep}$ is a unigram distribution of the head choice.

A* search is still tractable under this model.
The search problem is changed as follows:
\[
 \hat{{\bm y}} = \argmax_{{\bm y} \in Y({\bm x})} \Biggl( \sum_{i \in [1,N]} \log P_{tag}(c_i | {\bm x})
+  \sum_{i \in [1,N]} \log P_{dep}(h_i | {\bm x}) \Biggr),
\]
and the inside score is expressed as follows:
\begin{equation}
b(C_{i,j})  = \sum_{c_k \in {\bm c}_{i,j}} \log P_{tag}(c_k | {\bm x})
+ \sum_{k \in [i,j]\setminus\{root({\bm h}^C_{i,j})\}} \log P_{dep}(h_k | {\bm x}), \label{eq:newinside}
\end{equation}
where ${\bm h}^C_{i,j}$ is a dependency subtree for the Viterbi parse on $C_{i,j}$, and $root({\bm h})$ returns the root index.
We exclude the head score for the subtree root token because its head does not appear in $[i,j]$.
This causes the discrepancy between the goal inside score $b(C_{1,N})$ and the true model score (log of Eq.~(\ref{our_model})),
which we adjust by applying a special unary rule to the goal edge $C_{1,N}$ that adds $\log P_{dep}(h_{root({\bm h}^C_{1,N})} = 0 | {\bm x})$.

We can calculate the dependency terms in Eq.~(\ref{eq:newinside}) on the fly when expanding the chart.
Let the currently popped edge be $A_{i,k}$, which will be combined with $B_{k,j}$ to form a new subtree in $C_{i,j}$.
The key observation is that only one dependency arc (between $root({\bm h}_{i,k}^A)$ and $root({\bm h}_{k,j}^B)$) is determined at every combination (Figure \ref{calc}).
For every rule $C \rightarrow A~B$ we can define the head direction (Section \ref{conversion}) and $P_{dep}$ is obtained accordingly.
For example, when the right child $B$ becomes the head,
$b(C_{i,j}) = b(A_{i,k}) + b(B_{k,j}) + \log P_{dep}(h_{l}=m|{\bm x})$, where $l=root({\bm h}_{i,k}^A)$ and $m=root({\bm h}_{k,j}^B)$ ($l < m$).

The Viterbi outside score is changed as follows:
\begin{equation}
 a(C_{i,j}) = \sum_{k \in [1,N] \setminus [i, j]} \max_{c_k} \log P_{tag}(c_k | {\bm x})
+ \sum_{k \in L} \max_{h_k} \log P_{dep}(h_k | {\bm x}),
\end{equation}
where $L = [1,N] \setminus ([i,j]\setminus \{root({\bm h}_{i,j}^C)\})$.
We consider $root({\bm h}_{i,j}^C)$ an outside word because its head is not yet defined.
For every outside word we independently assign the score of its argmax head, which may not comprise a well-formed dependency tree.
We initialize the agenda by adding an item for every supertag $C$ and word $x_i$ with the score
$a(C_{i,i}) = \sum_{k \in [1,N]\setminus \{i\}} \max \log P_{tag}(c_k | {\bm x})
+ \sum_{k \in [1,N]} \max \log P_{dep}(h_k | {\bm x})$.
Note that the dependency component of $a(C_{i,i})$ is the same for every word.

\begin{figure}[b]
\begin{center}
\includegraphics{26-1ia4f3.eps}
\end{center}
\hangcaption{In the proposed model, the Viterbi inside score for edge $e_3$ is the sum of the $e_1$ and $e_2$ scores and the score of dependency arc going from the head of $e_2$ to that of $e_1$. Note that the head direction changes according to the child categories.}
\label{calc}
\end{figure}

\begin{figure}[b]
\begin{center}
\includegraphics{26-1ia4f4.eps}
\end{center}
\hangcaption{Neural networks of the proposed supertag and dependency factored model. First, we map each word $x_i$ to a hidden vector ${\bm r}_i$ using bi-LSTMs, and then apply biaffine~(Eq.~(\ref{biaffine})) and bilinear~(Eq.~(\ref{bilinear})) transformations to obtain the distributions of dependency heads ($P_{dep}$) and supertags ($P_{tag}$).}
\label{arch}
\end{figure}


\subsection{Network Architecture}

Following \cite{lewis-lee-zettlemoyer:2016:N16-1} and \cite{DBLP:journals/corr/DozatM16},
we model $P_{tag}$ and $P_{dep}$ using bi-LSTMs to exploit the entire sentence to capture the long range phenomena.
The overall network architecture is shown in Figure~\ref{arch}, where $P_{tag}$ and $P_{dep}$ share common bi-LSTM hidden vectors.

First we map each word $x_i$ to their hidden vector ${\bm r}_i$ with bi-LSTMs.
The input to the LSTMs is word embeddings, which we describe in Section~\ref{experiment}.
We add special start and end tokens to each sentence with trainable
parameters following \cite{lewis-lee-zettlemoyer:2016:N16-1}.
For $P_{dep}$, we use the biaffine transformation in \cite{DBLP:journals/corr/DozatM16}:
\begin{align}
&{\bm g}_i^{dep} = MLP_{child}^{dep}({\bm r}_i), \nonumber \\
&{\bm g}_{h_i}^{dep} = MLP_{head}^{dep}({\bm r}_{h_i}), \nonumber \\
&P_{dep}(h_i | {\bm x}) \propto \exp(({\bm g}_i^{dep})^{\mathrm{T}} W_{dep} {\bm g}_{h_i}^{dep}
+ {\bm w}_{dep}^{\mathrm{T}} {\bm g}_{h_i}^{dep}), \label{biaffine}
\end{align}
where $MLP$ is a multilayered perceptron.
Although a previous work \cite{lewis-lee-zettlemoyer:2016:N16-1} simply uses an
MLP to map ${\bm r}_i$ to $P_{tag}$,
we also utilize the hidden vector of
the most probable head
$h_i = \arg\max_{h_i'} P_{dep}(h_i' | {\bm x})$ (which is not necessarily identical to the head in the final output tree),
and apply ${\bm r}_i$
and ${\bm r}_{h_i}$ to a bilinear function:\footnote{This is inspired by the formulation of label prediction in \cite{DBLP:journals/corr/DozatM16}.}
{\allowdisplaybreaks
\begin{align}
&{\bm g}_i^{tag} = MLP_{child}^{tag}({\bm r}_i), \nonumber \\
&{\bm g}_{h_i}^{tag} = MLP_{head}^{tag}({\bm r}_{h_i}), \label{bilinear} \\
&{\bm \ell}_i = ({\bm g}_i^{tag})^{\mathrm{T}} {\bm U}_{tag} {\bm g}_{h_i}^{tag} +
W_{tag}
\begin{bmatrix}
{\bm g}_i^{tag} \\ {\bm g}_{h_i}^{tag}
\end{bmatrix} + {\bm b}_{tag}, \nonumber \\
&P_{tag}(c_i | {\bm x}) \propto \exp(\ell_{i,c}), \nonumber
\end{align}
}
where ${\bm U}_{tag}$ is a third order tensor and $\ell_{i,c}$ is the c'th element in the vector ${\bm \ell}_{i}$.
Formulating the prediction of $P_{tag}$ this way performs the best among other settings that remove or reverse the
dependence between the head model and the supertag model empirically.
Despite the actual dependence of supertags on a dependency structure in the neural network prediction,
we formulate our probabilistic model of a CCG tree as in Eq.~(\ref{our_model}), where they are treated as independent.
As in Lewis et al., these values can be precomputed prior to search, which makes our A* parsing quite efficient.


\section{CCG to Dependency Conversion}

In this section, we describe our conversion rules from a CCG tree to a dependency one, which we use in two purposes:
1) creation of the training data for the dependency component of our model;
and 2) extraction of a dependency arc at each combinatory rule during A* search (Section \ref{proposedastar}).
A previous work \cite{lewis-steedman:2014:EMNLP2014} describes one way to extract dependencies from a CCG tree ({\sc LewisRule}).
In addition to {\sc LewisRule}, we describe two simpler alternatives, i.e., {\sc HeadFirst} and {\sc HeadFinal},
and verify the effects on parsing performance in our experiments (Section \ref{experiment}).
An overview of the CCG to dependency conversion is shown in Figure~\ref{no_it_was}.

\begin{figure}[b]
\begin{center}
\includegraphics{26-1ia4f5.eps}
\end{center}
\caption{Examples of applying conversion rules (Section~\ref{conversion}) to English and Japanese sentences.}
\label{no_it_was}
\end{figure}
\label{conversion} 


\subsection{{\usefont{T1}{ptm}{b}{sc} LewisRule}}

The {\sc LewisRule} is the same as the conversion rule in \cite{lewis-steedman:2014:EMNLP2014}.
    As shown in Figure \ref{no_it_was}~(c), 
the output looks a familiar English dependency tree.

For forward application and (generalized) forward composition,
we define the head to be the left argument of the combinatory rule,
unless it matches either $X/X$ or $X/(X\backslash Y)$,
in which case the right argument is the head.
    For example, on {\it ``Black Monday''} in Figure~\ref{no_it_was}~(a), 
we select {\it Monday} as the head of {\it Black}.
For the backward rules, the conversions are defined as the reverse of
the corresponding forward rules.
For other rules, {\it remove punctuation}~($<\!\!rp\!\!>$) selects the non-punctuation argument as the head, while {\it conjunction}~($<\!\!\Phi\!\!>$) selects the right argument.\footnote{When applying {\sc LewisRule} to Japanese, we ignore feature values when determining the head argument, which often leads to a more natural dependency structure. For example, in ``tabe ta'' (eat {\it PAST}), the category of auxiliary verb ``ta'' is $S_{f_1}\backslash S_{f_2}$ with $f_1 \neq f_2$, thus $S_{f_1} \neq S_{f_2}$. In this case, we select ``tabe'' as the head by removing the feature values, which makes the category $X\backslash X$.}

One issue when using this method to obtain the training data is that due to the mismatch between the rule set of our CCG parser, for which we follow \cite{lewis-steedman:2014:EMNLP2014}, and the grammar in English CCGbank \cite{ccgbank}, we cannot extract dependencies from some of annotated CCG trees.\footnote{For example, the combinatory rules in \cite{lewis-steedman:2014:EMNLP2014} do not contain $N~N \Rightarrow N_{conj}$ in CCGbank. Another difficulty is that in English CCGbank the name of each combinatory rule is not annotated explicitly.}
Thus, we instead obtain training data for this method from the original CCGbank dependency annotations.
Fortunately, in most cases, the CCGbank dependency annotations match those of the {\sc LewisRule}; thus they can well-approximate {\sc LewisRule} dependencies.


\subsection{{\usefont{T1}{ptm}{b}{sc} HeadFinal}}

Among SOV languages, Japanese is a strictly head final language, i.e., the head of each word always follows the given word.
Japanese dependency parsing \cite{E99-1026,DBLP:conf/conll/KudoM02} has exploited this property explicitly by only allowing left-to-right dependency arcs.
Inspired by this tradition, we try a simple {\sc HeadFinal} rule in Japanese CCG parsing, where we always select the right argument as the head.
For example, 
    we obtain the head final dependency tree shown in Figure \ref{no_it_was}~(e), 
    from the Japanese CCG tree shown in Figure \ref{no_it_was}~(b).


\subsection{{\usefont{T1}{ptm}{b}{sc} HeadFirst}}

We apply an idea similar to {\sc HeadFinal} to English.
Differing from Japanese, English is an SVO language; therefore, we define a simple ``head first'' rule whereby the left argument always becomes the head 
    (Figure~\ref{no_it_was}~(d)).

Though this conversion may look odd at first, it has some advantages over the {\sc LewisRule}.
First, since a model that employs the {\sc LewisRule} is trained on CCGbank dependencies, at inference, occasionally the two components $P_{dep}$ and $P_{tag}$ result in conflicting predictions.
For example, the true Viterbi parse may have a lower score in terms of dependencies, in which case the parser slows down and may degrade the accuracy.
{\sc HeadFirst} does not suffer from such conflicts.
Second, because the arc directionality is fixed, the prediction of heads becomes easier, meaning that the dependency predictions become more reliable.
In Section \ref{sec:tritrain}, we demonstrate that this is the case for existing dependency parsers, and in practice, we find that the {\sc HeadFirst} conversion rule yields higher parsing scores than the {\sc LewisRule} on English (Section \ref{experiment}).



\section{Tri-training}
\label{sec:tritrain}

We extend the existing tri-training method and apply it to our English parsers.
Tri-training is one of the semi-supervised methods,
where the outputs of two parsers on unlabeled data
are intersected to create new (silver) training data.
This method has been successfully applied to dependency parsing \cite{weiss-EtAl:2015:ACL-IJCNLP}
and CCG supertagging \cite{lewis-lee-zettlemoyer:2016:N16-1}.

We simply combine the two previous approaches.
Lewis et al. (2016) obtained their silver data annotated
with the high quality supertags by parsing One Billion Word Benchmark dataset \cite{chelba}.
Since they make this data publicly available,\footnote{https://github.com/uwnlp/taggerflow} we obtain our silver data by
assigning dependency structures on top of them.

We train two very different dependency parsers using the training data extracted from CCGbank Section 02-21.\footnote{We annotate POS tags on this data using the Stanford POS tagger \cite{N03-1033}.}
This training data differs depending on our dependency conversion strategy employed (Section \ref{conversion}).
For the {\sc LewisRule}, we extract the original CCGbank dependency annotations.
For the {\sc HeadFirst}, we extract the head first dependencies from the CCG trees.
Note that we cannot annotate dependency labels; thus, we assign a dummy ``none'' label to each arc.
The first parser is the graph-based {\tt RBGParser} \cite{P14-1130}
with the default settings except that we train an unlabeled parser
and use the word embeddings of \cite{P10-1040}.
The second parser is
the transition-based {\tt lstm-parser} \cite{P15-1033} with the default parameters.

On the development set (Section 00),
with {\sc LewisRule} dependencies
the {\tt RBGParser} shows 93.8\% unlabeled attachment score while that of the {\tt lstm-parser} is 92.5\% using gold POS tags.
Interestingly, the parsers with {\sc HeadFirst} dependencies achieve higher scores:
94.9\% by {\tt RBGParser} and 94.6\% by {\tt lstm-parser}, suggesting that {\sc HeadFirst} dependencies are easier to parse.
For both dependencies, we obtain more than 1.7 million
sentences on which two parsers agree.

Following \cite{lewis-lee-zettlemoyer:2016:N16-1},
we include 15 copies of CCGbank training set when using these silver data.
In addition, we reduce the effects of the tri-training samples by multiplying their loss by 0.4.



\section{Parsing Experiments}
\label{experiment}


In this section, we describe experiments performed to evaluate the parsing performance of the proposed method on English and Japanese CCGbanks.


\subsection{English Experimental Settings}

In the English experiment, we use the CCGBank dataset \cite{ccgbank}, which was
constructed by converting the Wall Street Journal part of the Penn Treebank \cite{Marcus:1994:PTA:1075812.1075835},
and hence contains the same set of sentences annotated with CCG trees.
The data split is also defined in the same way; Sections 02-21 for training, Section 00 for development, and Section 23 for final evaluation,
each of which consists of 39,604/1,913/2,407 sentences.
The English CCGbank dataset contains 1,030,345 running words with 41,478 (lowercased) word types,
and the average sentence length is 23.45.
We report labeled and unlabeled F1 scores of the extracted CCG semantic dependencies obtained using {\tt generate} program supplied with {\tt C\&C} parser.

For our models, we adopt the pruning strategies proposed by \cite{lewis-steedman:2014:EMNLP2014} and
allow at most 50 categories per word,
use a variable-width beam with $\beta=0.00001$,
and utilize a tag dictionary, which maps frequent words to the possible supertags.\footnote{We use the tag dictionary provided with their bi-LSTM model.}
Unless otherwise stated, we only allow normal form parses \cite{P96-1011,C10-1053}, choosing the same subset of the constraints as \cite{lewis-steedman:2014:EMNLP2014}.

For word representation, we use the concatenation of word vectors
initialized to GloVe\footnote{http://nlp.stanford.edu/projects/glove/} \cite{pennington2014glove},
and randomly initialized prefix and suffix vectors of length 1 to 4,
which is inspired by \cite{lewis-lee-zettlemoyer:2016:N16-1}.
Affixes that only appear once in the training data are mapped to ``UNK''.

Other model configurations include:
4-layer bi-LSTMs with
left and right 300-dimensional LSTMs,
1-layer 100-dimensional MLPs with ELU non-linearity 
     (Clevert, Unterthiner, and \linebreak Hochreiter 2016)\nocite{DBLP:journals/corr/ClevertUH15}
for all $MLP_{child}^{dep}$,~$MLP_{head}^{dep}$,~$MLP_{child}^{tag}$ and $MLP_{head}^{tag}$,
and the Adam optimizer with $\beta_1=0.9, \beta_2=0.9$, L2 norm ($10^{-6}$), and learning rate decay with a ratio of 0.75 for every 2,500 iteration
starting from $0.002$,
which has been shown to be effective for training the biaffine parser \cite{DBLP:journals/corr/DozatM16}.

We compare the proposed method to the following baseline methods.\footnote{Note that only {\tt C\&C} and its extension contain the part-of-speech tagging phase (which is implemented internally). The inputs to the other parsers are untagged raw sentences.}
\begin{itemize}
\item {\tt C\&C} \cite{J07-4004} is a well-known CCG parser. It is based on a log-linear model defined over an entire parse tree
and finds an optimal tree using the CKY algorithm. The supertagger of {\tt C\&C}, which is also defined as a log-linear model,
first assigns the most probable supertags to the input sentence to help reduce the search space in the succeeding CKY stage.
We also report the performance of an extension with an LSTM supertagger \cite{N16-1027}.
\item {\tt EasySRL} \cite{lewis-lee-zettlemoyer:2016:N16-1} implements the A* parser introduced in Section~\ref{related},
which the current work is primarily based on.
{\tt EasySRL} adopts a supertag-factored model, where supertags probabilities are computed using bidirectional LSTMs,
and parsing ambiguities are resolved using attach-low heuristics (Section~\ref{sec:attachment_ambiguity}).
We also report results obtained with {\tt EasySRL\_reimpl}, our reimplemantation of {\tt EasySRL}.
\item {\tt neuralccg} \cite{lee-lewis-zettlemoyer:2016:EMNLP2016} extends {\tt EasySRL} with scores from a TreeLSTM \cite{P15-1150}.
Using globally conditioned score, {\tt neuralccg} achieves the current state-of-the-art results in the CCGBank parsing.
{\tt neuralccg} also uses A* parsing to obtain an optimal parse tree; however,
calculating the scores incurs significant computational costs thereby reducing processing speed (Section~\ref{sec:processing_speed}).
\end{itemize}


\subsection{Japanese Experimental Settings}
\label{japanese_experimental_settings}

In this experiment, we use the Japanese CCGbank \cite{uematsu-EtAl:2013:ACL2013}.
We follow the default train/dev/test splits, each of which contains of 23,375/\linebreak[2]4,645/8,948 sentences.
The Japanese CCGbank dataset contains 1,004,038 running words and 25,902 word types (both calculated in terms of lemma).
The average sentence length is 27.15.
As baselines, we use a shift-reduce CCG parser implemented in an NLP tool Jigg \cite{noji-miyao:2016:P16-4}\footnote{https://github.com/mynlp/jigg} (for simplicity, we refer to it as {\tt Jigg}) with beam size $= 64$,
and our adaptation of the supertag-factored model using bi-LSTMs.

For Japanese word representation, we use
the concatenation of word vectors
initialized to the Japanese Wikipedia Entity Vector,\footnote{http://www.cl.ecei.tohoku.ac.jp/{\textasciitilde}m-suzuki/jawiki\_vector/} 
and 100-dimensional vectors computed from randomly initialized
50-dimensional character embeddings through convolution \cite{santos:ICML}.
We do not use affix vectors as affixes are less informative in Japanese.
Characters that only appear once in the training data are mapped to ``UNK''.
For bi-LSTMs, MLPs, and optimization, we use the same parameter settings used in the English experiment.

One issue in Japanese experiments is evaluation.
The Japanese CCGbank is encoded in a different format than the English bank, and no stand-alone script for extracting semantic dependencies is available yet.
For this reason, we evaluate parser outputs by converting them to {\it bunsetsu dependencies}, the syntactic representation typically used in Japanese NLP \cite{DBLP:conf/conll/KudoM02}.
Given a CCG tree, we obtain bunsetsu dependencies by first segmenting a sentence into bunsetsu (chunks) using CaboCha.\footnote{http://taku910.github.io/cabocha/} After obtaining the word-level, 
    head final dependencies as in Figure \ref{no_it_was}~(b), 
dependencies that cross a bunsetsu boundary are extracted.
    For example, the sentence in Figure \ref{no_it_was}~(e) is 
segmented as ``{\it Boku wa $|$ eigo wo $|$ hanashi tai}'', from which we extract two dependencies ({\it Boku wa}) $\leftarrow$ ({\it hanashi tai}) and ({\it eigo wo}) $\leftarrow$ ({\it hanashi tai}).
We perform this conversion for both gold and output CCG trees and calculate the (unlabeled) attachment accuracy ({\bf Bunsetsu Dep.}).
We also report the accuracy of pre-terminal supertag assignment ({\bf Category}),
because it is crucial in determining the overall parse structure (Section~\ref{related}).
Though this process is imperfect, it can detect important parse errors such as attachment errors and thus can be a good proxy to evaluate the performance of a CCG parser.

\begin{table}[b]
\caption{Parsing results (F1) on English development set}
\label{english_experiment_dev}
\input{04table02.tex}
\end{table}


\subsection{English Parsing Results}

\subsubsection{Effect of Dependency}

We first see how the added dependency components in our model affect performance.
Table~\ref{english_experiment_dev} shows the results on the development set with several configurations. Here,
``w/o dep'' means the dependency terms of the model are discarded, and the attach low heuristics (Section \ref{intro}) is used instead, i.e., a supertag-factored model (Section \ref{astar}).
As can be seen, adding dependency terms improves the performance for both {\sc LewisRule} and {\sc HeadFirst} methods.


\subsubsection{Choice of Dependency Conversion Rule}

To our surprise, our simple {\sc HeadFirst} strategy always leads to better results than the linguistically motivated {\sc LewisRule}
(except for w/o dep settings).
The absolute improvements by tri-training are equally large (approximately 0.5 points), suggesting that the proposed model with dependencies can also benefit from the silver data.


\subsubsection{Excluding Normal Form Constraints}

One advantage of {\sc HeadFirst} is that the arc direction is always right, which makes the structures simpler and more accurately parsable (Section \ref{sec:tritrain}).
From another viewpoint, this fixed direction means that the constituent structure behind a (head first) dependency tree is almost unique.\footnote{There is a bijection between a head first dependency structure and an unlabeled binary constituency structure (modulo the use of unary rules). Basically we can recover a constituency tree by considering each dependency edge $i \to j$ as a constituent that spans from the $i$'th word to the rightmost descendant of the $j$'th word (or itself when there is none).}
Since the constituent structures of CCGbank trees basically follow the normal form (NF), we hypothesize that the model learned with {\sc HeadFirst} has an ability to force the outputs in NF automatically.
We summarize the results without the NF constraints in Table \ref{english_experiment_dev_wo_normalform}. These results demonstrates that the above argument is correct;
with {\sc HeadFirst}, the number of times NF rules are violated is significantly less than the number of time such rules are violated using {\sc LewisRule} (89 vs.~283).
Interestingly the scores of {\sc HeadFirst} models increase slightly compared to models with NF (e.g., 86.8 vs.~86.6 for CCGbank), suggesting that NF constraints occasionally hinder {\sc HeadFirst} models' search process.

\begin{table}[b]
\caption{Parsing results (F1) on English development set when normal form constraints are excluded}
\label{english_experiment_dev_wo_normalform}
\input{04table03.tex}
\vspace{4pt}\small
The \#~violations column shows the number of combinations that violate the constraints on the outputs.
\end{table}


\subsubsection{Results on Test Set}

Parsing results on the test set~(Section 23) are shown
in Table~\ref{english_experiment}. In Table~\ref{english_experiment}, we compare the {\sc HeadFirst} dependency model
without NF constraints that returns the best results to several existing parsers.
In the CCGbank experiment, the proposed parser demonstrates better results than
all the baseline parsers, except for C\&C with an LSTM supertagger \cite{N16-1027}.
In terms of labeled F1, the proposed parser outperforms {\tt EasySRL} and our reimplementation of that parser ({\tt EasySRL\_reimpl}) by 0.5\% and 0.9\%, respectively.
In the tri-training experiment, the proposed parser's performance increases significantly, i.e., 88.8\% for labeled F1 and 94.0\% for unlabeled F1.
Here, the proposed parser outperforms the state-of-the-art {\tt neuralccg} \cite{lee-lewis-zettlemoyer:2016:EMNLP2016}, which uses recursive neural networks,
by 0.1 and 0.3 points in terms of labeled and unlabeled F1, respectively.
To the best of our knowledge, these are the best reported F1 scores for English CCG parsing.
When three independent HeadFirst models are trained using the tri-training setup with different initial weight parameters,
they have resulted in the labeled and unlabeled F1 scores of $88.46 \pm 0.24$ and $93.80 \pm 0.13$, on average.

\begin{table}[tb]
\caption{Parsing results (F1) on English test set~(Section 23)}
\label{english_experiment}
\input{04table04.tex}
\end{table}


\subsubsection{Efficiency Comparison}
\label{sec:processing_speed}

We compare the efficiency of the proposed parser
to {\tt neuralccg} and {\tt EasySRL\_reimpl} 
\linebreak
(Table~\ref{efficiency_experiment}).\footnote{This experiment was conducted on a laptop with a 2-core 4-thread 2.0 GHz CPU.}
For overall speed~(the third row), the proposed parser is faster than {\tt neuralccg}; however it is slower than {\tt EasySRL\_reimpl}.
The proposed supertagger runs slower than those of {\tt neuralccg} and {\tt EasySRL\_reimpl}.
However, for A* search, the proposed parser processes over seven times more sentences than {\tt neuralccg}.
The delay in supertagging can be attributed to several factors, in particular
the differences in network architectures including the number of
bi-LSTM layers~(4 vs.~2) and the use of bilinear transformation
rather than linear transformation.
In addition, there are many implementation differences in our parsers~
(C\texttt{++} A* parser with a neural network model implemented with Chainer \cite{chainer_learningsys2015})
and {\tt neuralccg}~(Java parser with C\texttt{++} TensorFlow \cite{tensorflow2015-whitepaper}
supertagger and
recursive neural model in C\texttt{++} DyNet \cite{dynet}).\footnote{There seems to be room to optimize the proposed parser's efficiency. We found that our {\tt EasySRL\_reimpl} is slower than the original implementation of the supertag-factored model \cite{lewis-lee-zettlemoyer:2016:N16-1}, which {\tt neuralccg} uses internally.}

\begin{table}[b]
\hangcaption{Results of the efficiency experiment, where each number is the number of sentences processed per second}
\label{efficiency_experiment}
\input{04table05.tex}
\end{table}
\begin{table}[b]
\caption{Results of Japanese CCGbank}
\label{japanese_experiment}
\input{04table06.tex}
\end{table}


\subsection{Japanese Parsing Result}

We show the results of the Japanese parsing experiment in Table~\ref{japanese_experiment},
where the bunsetsu attachment accuracy of a Japanese dependency parser 
    CaboCha \cite{DBLP:conf/conll/KudoM02} is included for reference.
We train and evaluate the CaboCha parser on the same sets of sentences as CCGBank train and test sets, extracted from the Kyoto University Text Corpus \cite{kyodai}.
It achieves a slightly better score, presumably because it is directly optimized for this metric.
The simple application of the supertag-factored model \cite{lewis-lee-zettlemoyer:2016:N16-1} is not effective for Japanese,
showing the lowest attachment score of 81.5\%.
We observe a performance boost with the proposed method, particularly with {\sc HeadFinal} dependencies, which outperforms the baseline shift-reduce parser
by 1.1 points on category assignments and 4.0 points on bunsetsu dependencies.

The reduced performance of the simple application of the supertag-factored model can be attributed to
the fact that Japanese sentence structure is still highly ambiguous given the supertags.
This is particularly true for constructions where adverbial modifiers are involved~(Figure~\ref{ja_example}), i.e.,
which of succeeding verbs is modified cannot be determined only from the modifier's supertag $S/S$.
The result suggests the importance of modeling dependencies in some languages, e.g., Japanese.

\begin{figure}[t]
\begin{center}
\includegraphics{26-1ia4f6.eps}
\end{center}
\hangcaption{Examples of ambiguous Japanese sentence given fixed supertags. The left tree is the more probable (The translation is {\it ``I eat the curry I bought yesterday''}). In the right example, it is unlikely that ``昨日'' (yesterday) modifies the last verb in the present tense, when it is immediately followed by ``買った'' (buy-{\it PAST}).}
\label{ja_example}
\end{figure}


\subsubsection{Comparing A* Parser and Shift-Reduce Parser}

To the best of our knowledge, this is the first work that develops an A* CCG parsing method for the Japanese language.
{\tt Jigg} implements a transition-based parser adopting shift-reduce algorithm.
One of the critical issues with a transition-based method for CCG is that,
the sequence of predicted actions must be strictly consistent across time steps;
there can occur a situation wherein the transition system gets stuck in the middle of parsing and thus it cannot output a tree,
because there are no combinatory rules (correspondingly no transition actions) applicable to the root categories of the two top stack elements.
To overcome this situation, the {\tt Jigg} parser implements a heuristic rule that forcibly combines them into one. 
In fact, the {\tt Jigg} parser encountered such a situation in 7.2\% (642 out of 8,948) of the test sentences.
The proposed chart-based A* parser is guaranteed to output a well-formed tree.
It should be emphasized that in the conducted experiments throughout this paper (regardless of English or Japanese),
the proposed method always outputs a tree.
.

Transition-based parsers are well-known for their efficiency,
because their computational complexity only increases linearly in terms of the length of the input sentence.
Since we have also emphasized the efficiency of the proposed method, which results from the combination of a locally-factored model and A* parsing,
we compare the proposed method and the {\tt Jigg} parser in terms of processing speed using the Japanese CCGBank test set.\footnote{This experiment was conducted on a laptop with a 2-core 4-thread 2.5 GHz CPU.}
We found that the proposed method processes 14.2 sentences per second while {\tt Jigg} 16.0 sentences.
Although, in terms of processing speed, the transition-based parser outperforms the proposed parser, the gap is rather tolerable given the merits noted above.


\section{RTE Experiments}
\label{rte_experiment}

\newcommand{\LF}[1]{}
In addition to the parsing experiments, we conduct experiments to evaluate the proposed method in terms of RTE task.
RTE is an elemental technology for semantic analysis of multiple sentences, where, given premise(s) and a hypothesis, a system predicts
whether the former entails~({\it entailment}), contradicts~({\it contradiction}), or is neutral to~({\it unknown}), the latter.
The experiments are performed by combining the proposed CCG parser with logic-based RTE systems that
reason over meaning representations converted from CCG trees \cite{mineshima-EtAl:2015:EMNLP,abzianidze:2017:EMNLP2017Demos}.
Previously, it has been reported that one of such systems shows significantly improved RTE performance
by using gold CCG trees rather than predicted ones (from 74.1\% to 87.3\% accuracy, on the JSeM dataset),
implying the huge impact of the accuracy of CCG parsing on RTE \cite{D16-1242}.
We evaluate how much the parsing performance achieved in the previous section transfers to one of the other application tasks.


\subsection{Systems}


\subsubsection{ccg2lambda}

We use ccg2lambda \cite{mineshima-EtAl:2015:EMNLP}, a higher-order logic-based RTE system.
As shown in Figure~\ref{ccg2lambda_pipeline}, the ccg2lambda pipeline
first processes premise(s) and a hypothesis using a CCG parser.
The parse trees are converted into logical formulas by
composing $\lambda$-terms assigned to each terminal word in accordance with combinatory rules.
For the assignment of $\lambda$-terms, ccg2lambda adopts a template-based procedure,
where closed-class words (logical or functional expressions) are mapped to their specific meaning representations
and other words to schematic meaning representations based on CCG categories.
In this work, we adopt a semantic template based on Neo-Davidsonian Event Semantics \cite{parsons:event}, where a sentence is mapped to a formula involving
quantification over events and a verb is analyzed as a one-place predicate
over events using auxiliary predicates for semantic roles such as \LF{subj}. 
The system uses an automated theorem proving in Coq \cite{coq}
to determine whether entailment or contradiction holds between the premise(s) and the hypothesis.
The RTE system implements a specialized prover for higher-order features in natural language, which
is combined with Coq's built-in efficient first-order inference mechanism.

\begin{figure}[t]
\begin{center}
\includegraphics{26-1ia4f7.eps}
\end{center}
\hangcaption{Pipeline of ccg2lambda. First, it applies CCG parser to premise ($P$) and hypothesis ($H$) sentences~(a), and then converts them to logical formulas~(b). It attempts to prove if entailment (contradiction) can be established by applying Coq to the theorem $P \to H$ ($P \to \lnot H$)~(c). If the theorem proving fails, it tries axiom injection~(d). }
\label{ccg2lambda_pipeline}
\end{figure}


\subsubsection{LangPro}

LangPro \cite{abzianidze:2017:EMNLP2017Demos} is an analytic tableau system based on natural logic \cite{van2007brief}.
Natural logic seeks a formal logic whose formulas are as close as possible to linguistic expressions.
LangPro develops an efficient RTE system based on natural logic 
by extending a previously proposed analytic tableau system \cite{muskens2010},
where higher-order logic based on a simple type theory is used as natural logic and a version of an analytic tableau method is designed for it.

LangPro also constructs a meaning representation (Lambda Logical Form, LLF \cite{muskens2010}) for a sentence
in the accordance with CCG categories and combinatory rules.
LangPro constructs an intermediate representation by first mapping each CCG category in a tree to a function type of $\lambda$-terms
(e.g., mapping both $A/B$ and $B\backslash A$ to ${\tt \langle B,A \rangle}$,
an alternative notation of $B \to A$, which is common in formal semantics).
Then, its subtrees are rotated according to the order of the functional application of those types.
When this conversion is applied to a sentence ``{\it There is no one cutting a tomato}'',
the result is as in Eq.~(\ref{langpro:intermediate}).\footnote{Note that, in Abzianidze's method, via subtyping rules, $s$, $n$, $np$, etc. also qualify as semantic types in much the same way as traditional entity ``$e$'' and truth value ``$t$'' types do.}


This process also involves procedures that normalize the CCG tree (e.g., mapping ``{\it no one}'' to ``{\it no person}'').
Theorem proving operates on LLFs obtained from this representation
by mapping quantified noun phrases, such as ``{\it no person}'' and ``{\it a tomato}'' to
generalized quantifiers \cite{Barwise1981-BARGQA}.
Note that Eq.~(\ref{langpro:result}) represents such LLFs obtained from Eq.~(\ref{langpro:intermediate}).
The LangPro system is described in detail in Abzianidze's Ph.D. thesis \cite{lasha_phd_thesis}.
\begin{align}
& {\bf be}_{\tt \langle np,np,s \rangle}~(
{\bf no}_{\tt \langle n,np \rangle}~(
{\bf which}_{\tt \langle vp,n,n \rangle}~(
{\bf cut}_{\tt \langle np,vp \rangle}~(
{\bf a}_{\tt \langle n,np \rangle}~{\bf tomato}_{\tt n}
)
)~{\bf person}_{\tt n}
)
)~{\bf there}_{\tt np} \label{langpro:intermediate} \\
& {\bf no}_{\tt \langle n,vp,s \rangle}~(
{\bf which}_{\tt \langle vp,n,n \rangle}~(
\lambda x_{\tt np}.~{\bf a}_{\tt \langle n,vp,s \rangle}~{\bf tomato}_{\tt n} \nonumber \\
&       ~~~~~~~~~~~~~~~~~(\lambda y_{\tt np}.~{\bf cut}_{\tt \langle np,vp \rangle}~y~x)
)~{\bf person}_{\tt n}
)
(\lambda z_{\tt np}.~{\bf be}_{\tt \langle np,np,s \rangle}~z~{\bf there}_{\tt np}) \label{langpro:result}
\end{align}
While it implements some techniques to fix parse errors, the accurate CCG parsing is
important for the system, as demonstrated by the improved performance of a hybrid approach \cite{abzianidze:2015:EMNLP} that combines
RTE predictions obtained by parse trees of {\tt C\&C} and {\tt EasyCCG} parsers.

\begin{table}[b]
\caption{Example RTE problems from SICK dataset}
\label{sick_examples}
\input{04table07.tex}
\vspace{4pt}\small
To solve this dataset, capturing syntactic phenomena such as PP-attachment, passive construction and coordination accurately
is as important as logical reasoning and external lexical knowledge.
\end{table}


\subsection{Experimental Settings}

\subsubsection{English}
\label{english_rte_setting}

In the English experiment, we test the performance of ccg2lambda and LangPro combined with the proposed CCG parser
on the SICK dataset \cite{MARELLI14.363.L14-1314}.
This dataset was originally developed to test approaches of compositional distributional semantics
and includes a variety of syntactic, lexical, and semantic phenomena.
\linebreak
Table~\ref{sick_examples} shows some problems from the dataset,
that contain complex syntactic phenomena such as PP-attachment, passive construction and coordination.
It is evident that accurate CCG parsing is important to solve this dataset.

Here, we report results for ccg2lambda with the default settings~(with SPSA abduction; \cite{martinezgomez-EtAl:2017:EACLlong})
and results for two versions of LangPro, one described in \cite{abzianidze:2015:EMNLP} (henceforth we refer to it as LangPro15)
and the other in \cite{abzianidze:2017:EMNLP2017Demos} (LangPro17).
Briefly, the difference between the two versions is that LangPro17 is more robust to parse errors. 
We report accuracy/precision/recall/F1\footnote{In RTE literature, these metrics are defined as follows: recall is the number of correctly predicted entailments divided by the total number of premise-hypothesis pairs given to a system; precision is the number of correctly predicted entailments divided by the number of predictions made by the system.} values
of the two RTE systems that use the best performing {\sc HeadFirst} parser without NF constraints
trained on tri-training (hereafter {\tt depccg}) as a syntactic parsing component
instead of the baseline CCG parsers, i.e., {\tt C\&C} \cite{J07-4004} and {\tt EasyCCG} \cite{lewis-steedman:2014:EMNLP2014}.

It is well known that the CCG parsing accuracy is one of the bottlenecks of logic-based systems.
To mitigate the error propagation, ccg2lambda has an option to use multiple CCG parsers and aggregates their results ({\it multi-parsing} setting).
In this work, we also report RTE scores obtained by combining {\tt depccg} with {\tt C\&C} and {\tt EasyCCG}.
We regard two results as contradicted with each other if one is {\it entailment} and the other is {\it contradiction}.
In such cases the system outputs {\it unknown}; otherwise, if at least one parser results in {\it entailment} or {\it contradiction},
that is adopted as the system output.


\subsubsection{Japanese}

In the Japanese experiment, we evaluate the performance of the Japanese version of 
\linebreak
ccg2lambda, combined with
the best performing {\sc HeadFinal} ({\tt depccg}).
We use the JSeM RTE dataset \cite{Kawazoe2017} for evaluation.
Following \cite{D16-1242}, we report scores obtained for a subset of 523 problems, which includes Japanese translations of the FraCaS dataset \cite{fracas}.
These datasets focus on types of logical inferences that do not require world knowledge.
The problems used in the experiment are labeled with one of the tags from generalized quantifier, plural, adjective, verb, and attitude,
and treat linguistic phenomena related to it. Table~\ref{jsem_examples} shows the example problems.
We use the same baseline parser {\tt Jigg} \cite{noji-miyao:2016:P16-4} used in the CCGBank experiment.
We also report {\it multi-parsing} results obtained by combining {\tt depccg} and {\tt Jigg} (Section \ref{english_rte_setting}).


\subsection{English RTE Results}

Table~\ref{rte_english_experiment} shows the experimental results on the SICK dataset.
As can be seen, when combined with LangPro15 and 17, the proposed parser ({\tt depccg}) contributes to consistent improvement in the accuracy and recall (with a drop in precision),
which yields the improved overall F1 scores (0.87\% and 0.96\% up for both systems compared to {\tt C\&C}).
When combined with ccg2lambda, the proposed parser shows the same tendency as LangPro,
where better accuracy and recall yield the improved F1 score.
This is also evident in the multi-parsing setting where the proposed {\tt depccg} is used on top of {\tt C\&C} and {\tt EasyCCG}.

\begin{table}[b]
\caption{Example RTE problems from JSeM dataset}
\label{jsem_examples}
\input{04table08.tex}
\end{table}
\begin{table}[b]
\caption{RTE results on test section of SICK}
\label{rte_english_experiment}
\input{04table09.tex}
\end{table}

Interestingly, the proposed parser always contributes to improved recall under all settings.
When the proposed parser is used in combination with {\tt C\&C} and {\tt EasyCCG},
greater than 1\% recall improvement is observed,
which indicates that the proposed parser complements existing parsers.
Given the definition of recall in RTE, it can be speculated that the proposed parser can parse
a broader range of sentences (in terms of constructions) robustly. In error analysis, we find that this is actually the case.
In the SICK dataset, there are many examples of the ``{\it there is}'' construction, such as ``There is no dog barking'' (Figure~\ref{rte_example}),
which contains a noun phrase followed by a present participle adjective (with categories {\it NP/N}, {\it N}, {\it S$\backslash$NP}).
We have observed cases where {\tt C\&C} and {\tt EasyCCG} incorrectly parse the phrase as ``{\it N/N} {\it N/N} {\it N}'', where the last adjective
is analyzed as a noun modified by the preceding words. In contrast, the proposed parser correctly predicts the structure shown in Figure~\ref{rte_example}.

\begin{figure}[b]
\begin{center}
\includegraphics{26-1ia4f8.eps}
\end{center}
\hangcaption{In SICK, there are many examples of the ``{\it there is} $[_{{\it NP}}$ {\it NP} {\it PRP}$]$'' construction ({\it PRP}: present participle adjective). Existing parsers incorrectly analyze the {\it NP} constituent as a noun preceded by modifiers ({\it N/N} {\it N/N} {\it N}).}
\label{rte_example}
\end{figure}
\begin{table}[b]
\caption{RTE results using ccg2lambda on JSeM}
\label{rte_japanese_experiment}
\input{04table10.tex}
\end{table}


\subsection{Japanese RTE Results}

In the Japanese experiment, the proposed parser has resulted in poor RTE performance compared to the baseline Jigg parser (Table~\ref{rte_japanese_experiment}).
We hypothesize that this is due to the fact that the previous work created the semantic templates for this language
by analyzing Jigg's parse outputs (and thus designed them to absorb the errors of a specific parser).
We speculate that this resulted in a kind of ``overfitting'' in the templates.
In future work, we will conduct a detailed investigation of the issue.
The RTE performance has significantly improved when the parsers are combined in multi-parsing setting.
Among 538 test problems, ccg2lambda combined with {\tt depccg} has solved 30 problems for which the one with {\tt Jigg} has failed.
Conversely, the latter is successful in 44 problems for which the former is not,
which further indicates that the proposed parser works complementarily to existing parsers,
which is in accordance with the English RTE experiments.

\begin{figure}[b]
\begin{center}
\includegraphics{26-1ia4f9.eps}
\end{center}
\hangcaption{Examples of the use of {\it ADNint} (inner relationship) and {\it ADNext} (outer relationship) unary rules. The English translation is (a) {\it ``There exists a worker who wants to transfer his post''} and (b) {\it ``There is a reason why he wants to transfer his post''}.}
\label{relative_clause_examples}
\end{figure}

One critical issues with our model is that it does not consider the probability of applying a unary rule directly.
In Japanese CCGBank, the {\it ADNint} and {\it ADNext} unary rules are employed to account for
two classes of sentential noun modification \cite{10.2307/488720}: ``inner relationship'',
a relative clause equivalent in Japanese that involves argument extraction from within the subordinate clause (Figure~\ref{relative_clause_examples}a),
and ``outer relationship'', another broader class of sentential modifier that includes complements (Figure~\ref{relative_clause_examples}b).
As such, these unary rules result in largely different logical formulas in semantic parsing.
In the case of ccg2lambda, the former is converted to a conjunctive modifier, while the latter
to a higher-order ${\it Content}$ predicate, as shown in Figure~\ref{relative_clause_examples}.
Among the 44 problems for which only {\tt Jigg} is successful,
we have found examples where the proposed method predicts {\it ADNint} where {\it ADNext} is appropriate (and vice versa).
Currently, the adequacy of applying either of these rules is modeled indirectly through
the probability of the structure of the modifier clause.

In the current evaluation protocol of Japanese CCG parsing (Section~\ref{japanese_experimental_settings}),
misprediction of either of these unary rules is captured via the {\bf Category} metric (cf. Figure~\ref{relative_clause_examples}).
We approximate the accuracy of the use of {\it ADNint}/{\it ADNext} by computing that metric only on
those verbs (determined based on their gold part-of-speech tag) that appear under these unary rules in the Japanese CCGBank
test set (5,171 test sentences contain at least one such verb occurrence,
resulting in 12,227 verbs considered in total). Note that this is considered an ``approximation'' because not all of the verbs
may be involved with the constructions.
The result is 83.5\%, which is considerably low given that the metric on all words in the dataset is 94.1\%~(Table~\ref{japanese_experiment}).
Actually this is one of the causes of the large performance drop of the system combined with {\tt depccg} alone.
Its failure in analyzing the sentence ``会議に出席していたすべての人が新しい議長に投票した。''(``Everyone at the meeting voted for a new chairman.''),
which is contained in four test problems, has resulted in the failure of theorem proving on all of the problems.
Extending the proposed method to model unary rules explicitly is an important future direction relative to realizing robust semantic parsing using CCG.


\section{Related Work}
\label{sec:related}

Previous studies have utilized dependencies in lexicalized grammar parsing.

For Head-driven Phrase Structure Grammar~(HPSG; \cite{pollard1994head}),
several studies used the predicted dependency structure to improve the accuracy of HPSG parsing.
In \cite{P07-1079}, the form of the output tree is constrained to match the dependencies.
As in our method, for each rule~(schema) application, they define which child becomes the head
and impose a soft constraint that these dependencies agree with the output of a dependency parser.
The proposed method is different in that we do not use the one-best dependency structure alone.
Rather, we search for a CCG tree that is optimal in terms of dependencies and CCG supertags.
\cite{N10-1090} analyzes that capturing two syntactic properties, i.e., the subject and complements, is important for HPSG supertagging.
Based on this observation, they developed a two-stage method that first parses the input sentence into a dependency structure and
then uses dependency-based discrete features for an averaged perceptron-based supertagger, which results in improved tagging accuracy.

In CCG parsing literature, some studies have focused on the optimization of {\it dependency models} \cite{P14-1021,J07-4004}, which are
a class of models defined over semantic dependencies obtained from a CCG tree (similar to a predicate argument structure).
Such optimization is typically achieved by summing over all derivations that realize the same semantic dependencies.
This approach is reasonable given that the objective matches the evaluation metric.
Rather than modeling only dependencies, the proposed method finds a CCG derivation with a higher dependency score.
CCG-based semantic dependencies are also used as features in joint CCG parsing and semantic role labeling \cite{D15-1169};
however such features are ineffective to recover long-range dependencies over LSTMs in CCGbank parsing \cite{lewis-lee-zettlemoyer:2016:N16-1}.


\section{Conclusion}

We have proposed an A* CCG parsing method, in which the probability of a CCG tree is decomposed into
local factors of the CCG categories and its dependency structure.
By modeling the dependency structure explicitly,
we do not require any deterministic heuristics to resolve attachment ambiguities
and can keep the model locally factored such that all probabilities can be precomputed prior to running the search.
The proposed parser finds the optimal parses efficiently and achieves the state-of-the-art performance in both English and Japanese parsing.
We also evaluated the proposed parser in terms of logic-based RTE systems.
The experimental results demonstrate the proposed method's robustness against a wide range of constructions
while also highlighting the future direction of improvement in terms of the use of unary rules.



\acknowledgment

We would like to thank the anonymous reviewers for their detailed feedback, which has greatly improved the quality of this article.
We thank Yuichiro Sawai for the faster LSTM implementation and Koji Mineshima for conducting the RTE experiments.
This work was supported by JSPS KAKENHI Grant Number 18J12945, JST CREST Grant Number JPMJCR1301 and AIP Challenge Program, Japan.


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

\bibitem[\protect\BCAY{Abadi et~al.}{Abadi et~al.
  }{2016}]{tensorflow2015-whitepaper}
Abadi, M. et~al. \BBOP 2016\BBCP.
\newblock \BBOQ TensorFlow: A System for Large-scale Machine Learning.\BBCQ\
\newblock In {\Bem Proceedings of the 12th USENIX Conference on Operating
  Systems Design and Implementation}, OSDI'16, \mbox{\BPGS\ 265--283}.

\bibitem[\protect\BCAY{Abzianidze}{Abzianidze}{2015}]{abzianidze:2015:EMNLP}
Abzianidze, L. \BBOP 2015\BBCP.
\newblock \BBOQ A Tableau Prover for Natural Logic and Language.\BBCQ\
\newblock In {\Bem Proceedings of the 2015 Conference on Empirical Methods in
  Natural Language Processing}, \mbox{\BPGS\ 2492--2502}, Lisbon, Portugal.
  Association for Computational Linguistics.

\bibitem[\protect\BCAY{Abzianidze}{Abzianidze}{2016}]{lasha_phd_thesis}
Abzianidze, L. \BBOP 2016\BBCP.
\newblock {\Bem A Natural Proof System for Natural Language}.
\newblock Ph.D.\ thesis, Tilburg University.

\bibitem[\protect\BCAY{Abzianidze}{Abzianidze}{2017}]{abzianidze:2017:EMNLP2017Demos}
Abzianidze, L. \BBOP 2017\BBCP.
\newblock \BBOQ LangPro: Natural Language Theorem Prover.\BBCQ\
\newblock In {\Bem Proceedings of the 2017 Conference on Empirical Methods in
  Natural Language Processing: System Demonstrations}, \mbox{\BPGS\ 115--120},
  Copenhagen, Denmark. Association for Computational Linguistics.

\bibitem[\protect\BCAY{Bangalore \BBA\ Joshi}{Bangalore \BBA\
  Joshi}{1999}]{bangalore1999supertagging}
Bangalore, S.\BBACOMMA\ \BBA\ Joshi, A.~K. \BBOP 1999\BBCP.
\newblock \BBOQ Supertagging: An Approach to Almost Parsing.\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 25}  (2), \mbox{\BPGS\
  237--265}.

\bibitem[\protect\BCAY{Barwise \BBA\ Cooper}{Barwise \BBA\
  Cooper}{1981}]{Barwise1981-BARGQA}
Barwise, J.\BBACOMMA\ \BBA\ Cooper, R. \BBOP 1981\BBCP.
\newblock \BBOQ Generalized Quantifiers and Natural Language.\BBCQ\
\newblock {\Bem Linguistics and Philosophy}, {\Bbf 4}  (2), \mbox{\BPGS\
  159--219}.

\bibitem[\protect\BCAY{Bekki}{Bekki}{2010}]{bekki:book}
Bekki, D. \BBOP 2010\BBCP.
\newblock {\Bem A Formal Theory of Japanese Grammar: The Conjugation System,
  Syntactic Structures, and Semantic Composition}.
\newblock Kuroshio.
\newblock (In Japanese).

\bibitem[\protect\BCAY{Bos}{Bos}{2008}]{Bos:2008:WSA:1626481.1626503}
Bos, J. \BBOP 2008\BBCP.
\newblock \BBOQ Wide-coverage Semantic Analysis with Boxer.\BBCQ\
\newblock In {\Bem Proceedings of the 2008 Conference on Semantics in Text
  Processing}, STEP '08, \mbox{\BPGS\ 277--286}, Stroudsburg, PA, USA.
  Association for Computational Linguistics.

\bibitem[\protect\BCAY{Chelba, Mikolov, Schuster, Ge, Brants, Koehn, \BBA\
  Robinson}{Chelba et~al.}{2013}]{chelba}
Chelba, C., Mikolov, T., Schuster, M., Ge, Q., Brants, T., Koehn, P., \BBA\
  Robinson, T. \BBOP 2013\BBCP.
\newblock \BBOQ One Billion Word Benchmark for Measuring Progress in
  Statistical Language Modeling.\BBCQ\
\newblock {\Bem technical report}, {\Bbf abs/1312.3005}.

\bibitem[\protect\BCAY{Clark \BBA\ Curran}{Clark \BBA\ Curran}{2007}]{J07-4004}
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{Clevert, Unterthiner, \BBA\ \mbox{Hochreiter}}{Clevert
  et~al.}{2016}]{DBLP:journals/corr/ClevertUH15}
Clevert, D.-A., Unterthiner, T., \BBA\ \mbox{Hochreiter}, S. \BBOP 2016\BBCP.
\newblock \BBOQ Fast and Accurate Deep Network Learning by Exponential Linear
  Units (ELUs).\BBCQ\
\newblock {\Bem ICLR}.

\bibitem[\protect\BCAY{Cooper et~al.}{Cooper et~al. }{1996}]{fracas}
Cooper, R. et~al. \BBOP 1996\BBCP.
\newblock \BBOQ FraCaS: A Framework for Computational Semantics.\BBCQ.
\newblock Deliverable D16.

\bibitem[\protect\BCAY{dos Santos \BBA\ Zadrozny}{dos Santos \BBA\
  Zadrozny}{2014}]{santos:ICML}
dos Santos, C.~N.\BBACOMMA\ \BBA\ Zadrozny, B. \BBOP 2014\BBCP.
\newblock \BBOQ Learning Character-level Representations for Part-of-Speech
  Tagging.\BBCQ\
\newblock In {\Bem Proceedings of the 31st International Conference on
  International Conference on Machine Learning---Volume 32}, \mbox{\BPGS\
  1818--1826}. ICML.

\bibitem[\protect\BCAY{Dozat \BBA\ Manning}{Dozat \BBA\
  Manning}{2017}]{DBLP:journals/corr/DozatM16}
Dozat, T.\BBACOMMA\ \BBA\ Manning, C.~D. \BBOP 2017\BBCP.
\newblock \BBOQ Deep Biaffine Attention for Neural Dependency Parsing.\BBCQ\
\newblock {\Bem ICLR}.

\bibitem[\protect\BCAY{Dyer, Ballesteros, Ling, Matthews, \BBA\ Smith}{Dyer
  et~al.}{2015}]{P15-1033}
Dyer, C., Ballesteros, M., Ling, W., Matthews, A., \BBA\ Smith, A.~N. \BBOP
  2015\BBCP.
\newblock \BBOQ Transition-Based Dependency Parsing with Stack Long Short-Term
  Memory.\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\ 334--343}.
  Association for Computational Linguistics.

\bibitem[\protect\BCAY{Eisner}{Eisner}{1996}]{P96-1011}
Eisner, J. \BBOP 1996\BBCP.
\newblock \BBOQ Efficient Normal-Form Parsing for Combinatory Categorial
  Grammar.\BBCQ\
\newblock In {\Bem 34th Annual Meeting of the Association for Computational
  Linguistics}, \mbox{\BPGS\ 79--86}.

\bibitem[\protect\BCAY{Hashimoto}{Hashimoto}{1934}]{bunsetsu}
Hashimoto, S. \BBOP 1934\BBCP.
\newblock {\Bem Essentials of Japanese Grammar (Kokugoho Yousetsu)}.
\newblock Iwanami.

\bibitem[\protect\BCAY{Hockenmaier \BBA\ Bisk}{Hockenmaier \BBA\
  Bisk}{2010}]{C10-1053}
Hockenmaier, J.\BBACOMMA\ \BBA\ Bisk, Y. \BBOP 2010\BBCP.
\newblock \BBOQ Normal-form Parsing for Combinatory Categorial Grammars with
  Generalized Composition and Type-raising.\BBCQ\
\newblock In {\Bem Proceedings of the 23rd International Conference on
  Computational Linguistics (Coling 2010)}, \mbox{\BPGS\ 465--473}. Coling 2010
  Organizing Committee.

\bibitem[\protect\BCAY{Hockenmaier \BBA\ Steedman}{Hockenmaier \BBA\
  Steedman}{2007}]{ccgbank}
Hockenmaier, J.\BBACOMMA\ \BBA\ Steedman, M. \BBOP 2007\BBCP.
\newblock \BBOQ CCGbank: A Corpus of CCG Derivations and Dependency Structures
  Extracted from the Penn Treebank.\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 33}  (3), \mbox{\BPGS\
  355--396}.

\bibitem[\protect\BCAY{Kawahara, Kurohashi, \BBA\ Hasida}{Kawahara
  et~al.}{2002}]{kyodai}
Kawahara, D., Kurohashi, S., \BBA\ Hasida, K. \BBOP 2002\BBCP.
\newblock \BBOQ Construction of a Japanese Relevance-tagged Corpus.\BBCQ\
\newblock In {\Bem Proceedings of the 3rd International Conference on Language
  Resources and Evaluation (LREC2002)}, \mbox{\BPGS\ 2008--2013}.

\bibitem[\protect\BCAY{Kawazoe, Tanaka, Mineshima, \BBA\ Bekki}{Kawazoe
  et~al.}{2017}]{Kawazoe2017}
Kawazoe, A., Tanaka, R., Mineshima, K., \BBA\ Bekki, D. \BBOP 2017\BBCP.
\newblock \BBOQ An Inference Problem Set for Evaluating Semantic Theories and
  Semantic Processing Systems for Japanese.\BBCQ\
\newblock In Otake, M., Kurahashi, S., Ota, Y., Satoh, K., \BBA\ Bekki,
  D.\BEDS, {\Bem New Frontiers in Artificial Intelligence: JSAI-isAI 2015
  Workshops, LENLS, JURISIN, AAA, HAT-MASH, TSDAA, ASD-HR, and SKL, Kanagawa,
  Japan, November 16--18, 2015, Revised Selected Papers}, \mbox{\BPGS\ 58--65},
  Cham. Springer International Publishing.

\bibitem[\protect\BCAY{Kiperwasser \BBA\ Goldberg}{Kiperwasser \BBA\
  Goldberg}{2016}]{TACL885}
Kiperwasser, E.\BBACOMMA\ \BBA\ Goldberg, Y. \BBOP 2016\BBCP.
\newblock \BBOQ Simple and Accurate Dependency Parsing Using Bidirectional LSTM
  Feature Representations.\BBCQ\
\newblock {\Bem Transactions of the Association for Computational Linguistics},
  {\Bbf 4}, \mbox{\BPGS\ 313--327}.

\bibitem[\protect\BCAY{Klein \BBA\ Manning}{Klein \BBA\
  Manning}{2003}]{klein:a_star}
Klein, D.\BBACOMMA\ \BBA\ Manning, C.~D. \BBOP 2003\BBCP.
\newblock \BBOQ A* Parsing: Fast Exact Viterbi Parse Selection.\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\ 40--47}.

\bibitem[\protect\BCAY{Kudo \BBA\ Matsumoto}{Kudo \BBA\
  Matsumoto}{2002}]{DBLP:conf/conll/KudoM02}
Kudo, T.\BBACOMMA\ \BBA\ Matsumoto, Y. \BBOP 2002\BBCP.
\newblock \BBOQ Japanese Dependency Analysis using Cascaded Chunking.\BBCQ\
\newblock In {\Bem Proceedings of the 6th Conference on Natural Language
  Learning (CoNLL 2002) Held in cooperation with COLING 2002, Taipei, Taiwan,
  2002}, \mbox{\BPGS\ 63--69}.

\bibitem[\protect\BCAY{Lee, Lewis, \BBA\ Zettlemoyer}{Lee
  et~al.}{2016}]{lee-lewis-zettlemoyer:2016:EMNLP2016}
Lee, K., Lewis, M., \BBA\ Zettlemoyer, L. \BBOP 2016\BBCP.
\newblock \BBOQ Global Neural CCG Parsing with Optimality Guarantees.\BBCQ\
\newblock In {\Bem Proceedings of the 2016 Conference on Empirical Methods in
  Natural Language Processing}, \mbox{\BPGS\ 2366--2376}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Lei, Xin, Zhang, Barzilay, \BBA\ Jaakkola}{Lei
  et~al.}{2014}]{P14-1130}
Lei, T., Xin, Y., Zhang, Y., Barzilay, R., \BBA\ Jaakkola, T. \BBOP 2014\BBCP.
\newblock \BBOQ Low-Rank Tensors for Scoring Dependency Structures.\BBCQ\
\newblock In {\Bem Proceedings of the 52nd Annual Meeting of the Association
  for Computational Linguistics (Volume 1: Long Papers)}, \mbox{\BPGS\
  1381--1391}. Association for Computational Linguistics.

\bibitem[\protect\BCAY{Lewis, He, \BBA\ Zettlemoyer}{Lewis
  et~al.}{2015}]{D15-1169}
Lewis, M., He, L., \BBA\ Zettlemoyer, L. \BBOP 2015\BBCP.
\newblock \BBOQ Joint A* CCG Parsing and Semantic Role Labelling.\BBCQ\
\newblock In {\Bem Proceedings of the 2015 Conference on Empirical Methods in
  Natural Language Processing}, \mbox{\BPGS\ 1444--1454}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Lewis, Lee, \BBA\ Zettlemoyer}{Lewis
  et~al.}{2016}]{lewis-lee-zettlemoyer:2016:N16-1}
Lewis, M., Lee, K., \BBA\ Zettlemoyer, L. \BBOP 2016\BBCP.
\newblock \BBOQ LSTM CCG Parsing.\BBCQ\
\newblock In {\Bem Proceedings of the 2016 Conference of the North American
  Chapter of the Association for Computational Linguistics: Human Language
  Technologies}, \mbox{\BPGS\ 221--231}. Association for Computational
  Linguistics.

\bibitem[\protect\BCAY{Lewis \BBA\ Steedman}{Lewis \BBA\
  Steedman}{2014}]{lewis-steedman:2014:EMNLP2014}
Lewis, M.\BBACOMMA\ \BBA\ Steedman, M. \BBOP 2014\BBCP.
\newblock \BBOQ A* CCG Parsing with a Supertag-factored Model.\BBCQ\
\newblock In {\Bem Proceedings of the 2014 Conference on Empirical Methods in
  Natural Language Processing (EMNLP)}, \mbox{\BPGS\ 990--1000}. Association
  for Computational Linguistics.

\bibitem[\protect\BCAY{Marcus, Kim, Marcinkiewicz, MacIntyre, Bies, Ferguson,
  Katz, \BBA\ Schasberger}{Marcus
  et~al.}{1994}]{Marcus:1994:PTA:1075812.1075835}
Marcus, M., Kim, G., Marcinkiewicz, M.~A., MacIntyre, R., Bies, A., Ferguson,
  M., Katz, K., \BBA\ Schasberger, B. \BBOP 1994\BBCP.
\newblock \BBOQ The Penn Treebank: Annotating Predicate Argument
  Structure.\BBCQ\
\newblock In {\Bem Proceedings of the Workshop on Human Language Technology},
  HLT '94, \mbox{\BPGS\ 114--119}, Stroudsburg, PA, USA. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Marelli, Menini, Baroni, Bentivogli, Bernardi, \BBA\
  Zamparelli}{Marelli et~al.}{2014}]{MARELLI14.363.L14-1314}
Marelli, M., Menini, S., Baroni, M., Bentivogli, L., Bernardi, R., \BBA\
  Zamparelli, R. \BBOP 2014\BBCP.
\newblock \BBOQ A SICK cure for the evaluation of compositional distributional
  semantic models.\BBCQ\
\newblock In Calzolari, N., Choukri, K., Declerck, T., Loftsson, H., Maegaard,
  B., Mariani, J., Moreno, A., Odijk, J., \BBA\ Piperidis, S.\BEDS, {\Bem
  Proceedings of the 9th International Conference on Language Resources and
  Evaluation (LREC'14)}, \mbox{\BPGS\ 216--223}, Reykjavik, Iceland. European
  Language Resources Association (ELRA).
\newblock ACL Anthology Identifier: L14-1314.

\bibitem[\protect\BCAY{Mart{\'{i}}nez-G{\'{o}}mez, Mineshima, Miyao, \BBA\
  Bekki}{Mart{\'{i}}nez-G{\'{o}}mez
  et~al.}{2017}]{martinezgomez-EtAl:2017:EACLlong}
Mart{\'{i}}nez-G{\'{o}}mez, P., Mineshima, K., Miyao, Y., \BBA\ Bekki, D. \BBOP
  2017\BBCP.
\newblock \BBOQ On-demand Injection of Lexical Knowledge for Recognising
  Textual Entailment.\BBCQ\
\newblock In {\Bem Proceedings of the 15th Conference of the European Chapter
  of the Association for Computational Linguistics: Volume 1, Long Papers},
  \mbox{\BPGS\ 710--720}, Valencia, Spain. Association for Computational
  Linguistics.

\bibitem[\protect\BCAY{\mbox{Pennington}, Socher, \BBA\
  Manning}{\mbox{Pennington} et~al.}{2014}]{pennington2014glove}
\mbox{Pennington}, J., Socher, R., \BBA\ Manning, C.~D. \BBOP 2014\BBCP.
\newblock \BBOQ GloVe: Global Vectors for Word Representation.\BBCQ\
\newblock In {\Bem Empirical Methods in Natural Language Processing (EMNLP)},
  \mbox{\BPGS\ 1532--1543}.

\bibitem[\protect\BCAY{Mineshima, Mart{\'{i}}nez-G{\'{o}}mez, Miyao, \BBA\
  Bekki}{Mineshima et~al.}{2015}]{mineshima-EtAl:2015:EMNLP}
Mineshima, K., Mart{\'{i}}nez-G{\'{o}}mez, P., Miyao, Y., \BBA\ Bekki, D. \BBOP
  2015\BBCP.
\newblock \BBOQ Higher-order logical inference with compositional
  semantics.\BBCQ\
\newblock In {\Bem Proceedings of EMNLP}, \mbox{\BPGS\ 2055--2061}.

\bibitem[\protect\BCAY{Mineshima, Tanaka, Mart{\'{i}}nez-G{\'{o}}mez, Miyao,
  \BBA\ Bekki}{Mineshima et~al.}{2016}]{D16-1242}
Mineshima, K., Tanaka, R., Mart{\'{i}}nez-G{\'{o}}mez, P., Miyao, Y., \BBA\
  Bekki, D. \BBOP 2016\BBCP.
\newblock \BBOQ Building Compositional Semantics and Higher-order Inference
  System for a Wide-coverage Japanese CCG Parser.\BBCQ\
\newblock In {\Bem Proceedings of the 2016 Conference on Empirical Methods in
  Natural Language Processing}, \mbox{\BPGS\ 2236--2242}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Muskens}{Muskens}{2010}]{muskens2010}
Muskens, R. \BBOP 2010\BBCP.
\newblock \BBOQ An Analytic Tableau System for Natural Logic.\BBCQ\
\newblock In Aloni, M., Bastiaanse, H., de~Jager, T., \BBA\ Schulz, K.\BEDS,
  {\Bem Logic, Language and Meaning}, \mbox{\BPGS\ 104--113}, Berlin,
  Heidelberg. Springer Berlin Heidelberg.

\bibitem[\protect\BCAY{Neubig et~al.}{Neubig et~al. }{2017}]{dynet}
Neubig, G. et~al. \BBOP 2017\BBCP.
\newblock \BBOQ DyNet: The Dynamic Neural Network Toolkit.\BBCQ\ {\bfseries
  abs/1701.03980}.

\bibitem[\protect\BCAY{Noji \BBA\ Miyao}{Noji \BBA\
  Miyao}{2016}]{noji-miyao:2016:P16-4}
Noji, H.\BBACOMMA\ \BBA\ Miyao, Y. \BBOP 2016\BBCP.
\newblock \BBOQ Jigg: A Framework for an Easy Natural Language Processing
  Pipeline.\BBCQ\
\newblock In {\Bem Proceedings of ACL-2016 System Demonstrations}, \mbox{\BPGS\
  103--108}. Association for Computational Linguistics.

\bibitem[\protect\BCAY{Parsons}{Parsons}{1990}]{parsons:event}
Parsons, T. \BBOP 1990\BBCP.
\newblock {\Bem Events in The Semantics of English: A Study in Subatomic
  Semantics}.
\newblock The MIT Press.

\bibitem[\protect\BCAY{Pollard \BBA\ Sag}{Pollard \BBA\
  Sag}{1994}]{pollard1994head}
Pollard, C.\BBACOMMA\ \BBA\ Sag, I.~A. \BBOP 1994\BBCP.
\newblock {\Bem Head-driven Phrase Structure Grammar}.
\newblock University of Chicago Press.

\bibitem[\protect\BCAY{Prawitz}{Prawitz}{1965}]{natded}
Prawitz, D. \BBOP 1965\BBCP.
\newblock {\Bem Natural Deduction---A ProofTheoretical Study}.
\newblock Almqvist \& Wiksell.

\bibitem[\protect\BCAY{Sagae, Miyao, \BBA\ Tsujii}{Sagae
  et~al.}{2007}]{P07-1079}
Sagae, K., Miyao, Y., \BBA\ Tsujii, J. \BBOP 2007\BBCP.
\newblock \BBOQ HPSG Parsing with Shallow Dependency Constraints.\BBCQ\
\newblock In {\Bem Proceedings of the 45th Annual Meeting of the Association of
  Computational Linguistics}, \mbox{\BPGS\ 624--631}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Steedman}{Steedman}{2000}]{steedman:syntactic_process}
Steedman, M. \BBOP 2000\BBCP.
\newblock {\Bem The Syntactic Process}.
\newblock The MIT Press.

\bibitem[\protect\BCAY{Steedman}{Steedman}{2012}]{steedman:taking_scope}
Steedman, M. \BBOP 2012\BBCP.
\newblock {\Bem Taking Scope: The Natural Semantics of Quantifiers}.
\newblock The MIT Press.

\bibitem[\protect\BCAY{Tai, Socher, \BBA\ Manning}{Tai et~al.}{2015}]{P15-1150}
Tai, K.~S., Socher, R., \BBA\ Manning, C.~D. \BBOP 2015\BBCP.
\newblock \BBOQ Improved Semantic Representations From Tree-Structured Long
  Short-Term Memory Networks.\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\
  1556--1566}. Association for Computational Linguistics.

\bibitem[\protect\BCAY{Teramura}{Teramura}{1969}]{10.2307/488720}
Teramura, H. \BBOP 1969\BBCP.
\newblock \BBOQ The Syntax of Noun Modification in Japanese.\BBCQ\
\newblock {\Bem The Journal-Newsletter of the Association of Teachers of
  Japanese}, {\Bbf 6}  (1), \mbox{\BPGS\ 64--74}.

\bibitem[\protect\BCAY{{The Coq Development Team}}{{The Coq Development
  Team}}{2017}]{coq}
{The Coq Development Team} \BBOP 2017\BBCP.
\newblock \BBOQ The Coq Proof Assistant: Reference Manual: Version 8.7.1.\BBCQ.
\newblock INRIA.

\bibitem[\protect\BCAY{Tokui, Oono, Hido, \BBA\ Clayton}{Tokui
  et~al.}{2015}]{chainer_learningsys2015}
Tokui, S., Oono, K., Hido, S., \BBA\ Clayton, J. \BBOP 2015\BBCP.
\newblock \BBOQ Chainer: A Next-Generation Open Source Framework for Deep
  Learning.\BBCQ\
\newblock In {\Bem Proceedings of Workshop on Machine Learning Systems
  (LearningSys) in the 29th Annual Conference on Neural Information Processing
  Systems (NIPS)}.

\bibitem[\protect\BCAY{Toutanova, Klein, Manning, \BBA\ Singer}{Toutanova
  et~al.}{2003}]{N03-1033}
Toutanova, K., Klein, D., Manning, C.~D., \BBA\ Singer, Y. \BBOP 2003\BBCP.
\newblock \BBOQ Feature-Rich Part-of-Speech Tagging with a Cyclic Dependency
  Network.\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\ 173--180}.

\bibitem[\protect\BCAY{Turian, Ratinov, \BBA\ Bengio}{Turian
  et~al.}{2010}]{P10-1040}
Turian, J., Ratinov, L.-A., \BBA\ Bengio, Y. \BBOP 2010\BBCP.
\newblock \BBOQ Word Representations: A Simple and General Method for
  Semi-Supervised Learning.\BBCQ\
\newblock In {\Bem Proceedings of the 48th Annual Meeting of the Association
  for Computational Linguistics}, \mbox{\BPGS\ 384--394}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Uchimoto, Sekine, \BBA\ Isahara}{Uchimoto
  et~al.}{1999}]{E99-1026}
Uchimoto, K., Sekine, S., \BBA\ Isahara, H. \BBOP 1999\BBCP.
\newblock \BBOQ Japanese Dependency Structure Analysis Based on Maximum Entropy
  Models.\BBCQ\
\newblock In {\Bem 9th Conference of the European Chapter of the Association
  for Computational Linguistics}, \mbox{\BPGS\ 196--203}.

\bibitem[\protect\BCAY{Uematsu, Matsuzaki, Hanaoka, Miyao, \BBA\ Mima}{Uematsu
  et~al.}{2013}]{uematsu-EtAl:2013:ACL2013}
Uematsu, S., Matsuzaki, T., Hanaoka, H., Miyao, Y., \BBA\ Mima, H. \BBOP
  2013\BBCP.
\newblock \BBOQ Integrating Multiple Dependency Corpora for Inducing
  Wide-coverage Japanese CCG Resources.\BBCQ\
\newblock In {\Bem Proceedings of the 51st Annual Meeting of the Association
  for Computational Linguistics (Volume 1: Long Papers)}, \mbox{\BPGS\
  1042--1051}, Sofia, Bulgaria. Association for Computational Linguistics.

\bibitem[\protect\BCAY{van Benthem}{van Benthem}{2008}]{van2007brief}
van Benthem, J. \BBOP 2008\BBCP.
\newblock \BBOQ A Brief History of Natural Logic.\BBCQ\
\newblock In {\Bem Logic, Navya-Ny{\={a}}ya \& Applications: Homage to Bimal
  Krishna Matilal}, \mbox{\BPGS\ 21--42}. College Publications.

\bibitem[\protect\BCAY{Vaswani, Bisk, Sagae, \BBA\ Musa}{Vaswani
  et~al.}{2016}]{N16-1027}
Vaswani, A., Bisk, Y., Sagae, K., \BBA\ Musa, R. \BBOP 2016\BBCP.
\newblock \BBOQ Supertagging With LSTMs.\BBCQ\
\newblock In {\Bem Proceedings of the 2016 Conference of the North American
  Chapter of the Association for Computational Linguistics: Human Language
  Technologies}, \mbox{\BPGS\ 232--237}. Association for Computational
  Linguistics.

\bibitem[\protect\BCAY{Weiss, Alberti, Collins, \BBA\ Petrov}{Weiss
  et~al.}{2015}]{weiss-EtAl:2015:ACL-IJCNLP}
Weiss, D., Alberti, C., Collins, M., \BBA\ Petrov, S. \BBOP 2015\BBCP.
\newblock \BBOQ Structured Training for Neural Network Transition-Based
  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\ 323--333}.
  Association for Computational Linguistics.

\bibitem[\protect\BCAY{Xu, Clark, \BBA\ Zhang}{Xu et~al.}{2014}]{P14-1021}
Xu, W., Clark, S., \BBA\ Zhang, Y. \BBOP 2014\BBCP.
\newblock \BBOQ Shift-Reduce CCG Parsing with a Dependency Model.\BBCQ\
\newblock In {\Bem Proceedings of the 52nd Annual Meeting of the Association
  for Computational Linguistics (Volume 1: Long Papers)}, \mbox{\BPGS\
  218--227}. Association for Computational Linguistics.

\bibitem[\protect\BCAY{Zhang, Matsuzaki, \BBA\ Tsujii}{Zhang
  et~al.}{2010}]{N10-1090}
Zhang, Y.-z., Matsuzaki, T., \BBA\ Tsujii, J. \BBOP 2010\BBCP.
\newblock \BBOQ A Simple Approach for HPSG Supertagging Using Dependency
  Information.\BBCQ\
\newblock In {\Bem Human Language Technologies: The 2010 Annual Conference of
  the North American Chapter of the Association for Computational Linguistics},
  \mbox{\BPGS\ 645--648}. Association for Computational Linguistics.

\end{thebibliography}


\appendix

In the following we summarize the details of English and Japanese CCG grammars implemented in our parser.
Please refer to Table~\ref{general_binary_rules}, for the details of the basic combinatory rules.

\section{Details of English CCG Grammar}
\label{appendix:english_grammar}

The set of binary combinatory rules:
\begin{itemize}
\item {\it forward application}~$>$
\item {\it backward application}~$<$
\item {\it forward composition}~$>\!\!{\bf B}^1$
\item {\it backward crossed composition}~$<\!\!{\bf B}^1_{\times}$
\item {\it generalized forward composition}~$>\!\!{\bf B}^n$, where $n = 2$
\item {\it generalized backward crossed composition}~$<\!\!{\bf B}^n_{\times}$, where $n = 2$
\end{itemize}

\vspace{0.2in}
The other binary rules are as follow.
Here, ${\it PUNCT} \in \{{\it comma}, {\it conj}, {\it semicolon}\}$.
Rules marked with $^*$ are found in the implementation of {\tt EasySRL}.
In this work, we also employ these rules.

\begin{center}
\begin{tabular}{llll}
{\it conjunction} ($<\!\!\Phi\!\!>$) & ${\it conj}$ & $X$ & $\Rightarrow X\backslash X$ \\
{\it remove puctuation right} ($<\!\!rp\!\!>$) & ${\it PUNCT}$ & $X$ & $\Rightarrow X$ \\
{\it remove puctuation left} ($<\!\!lp\!\!>$) & $X$ & ${\it PUNCT}$ & $\Rightarrow X$ \\
{\it comma\_verb\_phrase\_to\_adverb}$^*$ & ${\it comma}$ & $S_{\tt ng|pass}\backslash NP$ & $\Rightarrow (S\backslash NP)\backslash (S\backslash NP)$ \\
{\it parenthetical\_direct\_speech}$^*$ & ${\it comma}$ & $S_{\tt dcl}/S_{\tt dcl}$ & $\Rightarrow (S\backslash NP)/(S\backslash NP)$
\end{tabular}
\end{center}

\vspace{0.2in}
The set of unary rules:
\begin{itemize}
\item Bare noun phrases
\begin{itemize}
\item $N \Rightarrow NP$
\end{itemize}
\item  Type raising
\begin{itemize}
\item $NP \Rightarrow S/(S\backslash NP)$
\item $NP \Rightarrow (S\backslash NP)/((S\backslash NP)/NP)$
\item $PP \Rightarrow (S\backslash NP)/((S\backslash NP)/PP)$
\end{itemize}
\item Reduced relative clause
\begin{itemize}
\item $S_{\tt pss|ng|adj|to}\backslash NP \Rightarrow NP\backslash NP$ 
\item $S_{\tt to}\backslash NP \Rightarrow N\backslash N$
\item $S_{\tt dcl}/NP \Rightarrow  NP\backslash NP$
\end{itemize}
\item VP Sentence Modifiers
\begin{itemize}
\item $S_{\tt pss|ng|to}\backslash NP \Rightarrow S/S$ 
\end{itemize}
\end{itemize}

Our parser outputs only derivations whose root category is from the following list:
\begin{quote}
$S_{\tt dcl}$, $S_{\tt wq}$, $S_{\tt q}$, $S_{\tt qem}$, $NP$
\end{quote}


\section{Details of Japanese CCG Grammar}
\label{appendix:japanese_grammar}

The set of binary combinatory rules:
\begin{itemize}
\item {\it forward application}~$>$
\item {\it backward application}~$<$
\item {\it forward composition}~$>\!\!{\bf B}^1$
\item {\it backward composition}~$<\!\!{\bf B}^1$
\item {\it generalized backward composition}~$<\!\!{\bf B}^n$ for $n \in \{2,3,4\}$
\item {\it cross forward composition}~$>\!\!{\bf B}^n$ for $n \in \{2,3\}$
\item {\it SSEQ}
\end{itemize}
where {\it SSEQ} combines two constituents each licensed as a sentence;
for all category $X$ in the set of categories that can appear at a root of a CCG tree (defined below), $X X \Rightarrow X$.

\vspace{0.2in}
The set of unary rules
(here, for simplicity, $S_{\tt mod=X,form=Y,fin=Z}$ is abbreviated as $S_{\tt X,Y,Z}$ 
and $NP_{\tt case=X,mod=Y,fin=Z}$ as $NP_{\tt X,Y,Z}$):
\begin{itemize}
\item Adnominal Modifier (Inner relationship)
\begin{itemize}
\item $S_{\tt adn,attr,f}\backslash NP_{\tt ga,nm,f} \Rightarrow NP_{\tt nc,X1,X2}/NP_{\tt nc,X1,X2}$
\item $S_{\tt adn,attr,f}\backslash NP_{\tt o,nm,f} \Rightarrow NP_{\tt nc,X1,X2}/NP_{\tt nc,X1,X2}$
\item $S_{\tt adn,base,f}\backslash NP_{\tt ga,nm,f} \Rightarrow NP_{\tt nc,X1,X2}/NP_{\tt nc,X1,X2}$
\item $S_{\tt adn,base,f}\backslash NP_{\tt o,nm,f} \Rightarrow NP_{\tt nc,X1,X2}/NP_{\tt nc,X1,X2}$
\end{itemize}
\item Adnominal Modifier (Outer relationship)
\begin{itemize}
\item $S_{\tt adn,attr,f} \Rightarrow NP_{\tt nc,X1,X2}/NP_{\tt nc,X1,X2}$
\item $S_{\tt adn,base,f} \Rightarrow NP_{\tt nc,X1,X2}/NP_{\tt nc,X1,X2}$
\item $S_{\tt adn,cont,f} \Rightarrow NP_{\tt nc,X1,X2}/NP_{\tt nc,X1,X2}$
\item $S_{\tt adn,hyp,f} \Rightarrow NP_{\tt nc,X1,X2}/NP_{\tt nc,X1,X2}$
\item $S_{\tt adn,imp,f} \Rightarrow NP_{\tt nc,X1,X2}/NP_{\tt nc,X1,X2}$
\item $S_{\tt adn,stem,f} \Rightarrow NP_{\tt nc,X1,X2}/NP_{\tt nc,X1,X2}$
\end{itemize}
\item Adverbial Modifier
\begin{itemize}
\item $S_{\tt adv,stem,f} \Rightarrow S_{\tt X1,X2,X3}/S_{\tt X1,X2,X3}$
\item $S_{\tt adv,cont,f}\backslash NP_{\tt ga,nm,f} \Rightarrow (S_{\tt X1,X2,X3}\backslash NP_{\tt ga,nm,f})/(S_{\tt X1,X2,X3}\backslash NP_{\tt ga,nm,f})$
\item $S_{\tt adv,cont,f} \Rightarrow S_{\tt X1,X2,X3}/S_{\tt X1,X2,X3}$
\item $S_{\tt adv,hyp,f} \Rightarrow S_{\tt X1,X2,X3}/S_{\tt X1,X2,X3}$
\end{itemize}
\item $NP_{\tt nc,adv,f} \Rightarrow S_{\tt X1,X2,X3}/S_{\tt X1,X2,X3}$
\end{itemize}

\vspace{0.2in}
Our parser outputs only derivations whose root category is from the following list:
\begin{quote}
$NP_{\tt nc,nm,f}$,
$NP_{\tt nc,nm,t}$,
$S_{\tt nm,attr,t}$,
$S_{\tt nm,base,f}$,
$S_{\tt nm,base,t}$,
$S_{\tt nm,cont,f}$,
$S_{\tt nm,cont,t}$,
$S_{\tt nm,da,f}$, \\
$S_{\tt nm,da,t}$,
$S_{\tt nm,hyp,t}$,
$S_{\tt nm,imp,f}$,
$S_{\tt nm,imp,t}$,
$S_{\tt nm,r,t}$,
$S_{\tt nm,s,t}$,
$S_{\tt nm,stem,f}$,
$S_{\tt nm,stem,t}$
\end{quote}



\begin{biography}
\bioauthor[:]{Masashi Yoshikawa}{
received his B.S. degree from Osaka University in 2015 in foreign studies
and M.S. degree from Nara Institute of Science and Technology (NAIST) in 2017, in information science.
He is currently a Ph.D. student at NAIST.
His research interests include intersection of natural language processing and machine learning,
in particular in areas relating syntactic and semantic parsing.
}

\bioauthor[:]{Hiroshi Noji}{
received his Ph.D. from the Graduate University for Advanced Studies.
He was Assistant Professor at the Graduate School of Information Science, Nara Institute of Science and Technology from 2016 to 2018,
and is currently a researcher at Artificial Intelligence Research Center, AIST.
His research interests are syntactic parsing as well as modeling of human language processing such as language acquisition.
}

\bioauthor[:]{Yuji Matsumoto}{
received his M.S. and Ph.D. degrees in information science from Kyoto University in 1979 and in 1989.
He joined Machine Inference Section of Electrotechnical Laboratory in 1979.
He has then experienced an academic visitor at Imperial College of Science and Technology, a deputy
chief of First Laboratory at ICOT, and an associate professor at Kyoto University.
He is currently a professor at Nara Institute of Science and Technology.
His main research interests are natural language understanding and machine learning.
}
\end{biography}


\biodate





\end{document}
