    \documentclass[english]{jnlp_1.4}

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



\Volume{21}
\Number{6}
\Month{December}
\Year{2014}

\received{2014}{2}{20}
\revised{2014}{5}{2}
\rerevised{2014}{7}{6}
\accepted{2014}{8}{29}

\setcounter{page}{1163}


\etitle{Language-independent Approach to High Quality Dependency Selection from Automatic Parses}
\eauthor{Gongye Jin\affiref{Author_1} \and Daisuke Kawahara\affiref{Author_1} \and Sadao Kurohashi\affiref{Author_1}} 
\eabstract{
  Many knowledge acquisition tasks are tightly dependent on fundamental
  analysis technologies, such as part of speech (POS) tagging and parsing. Dependency
  parsing, in particular, has been widely employed for the acquisition of
  knowledge related to predicate-argument structures. For such tasks,
  the dependency parsing performance can determine quality of acquired knowledge, regardless of target
  languages. Therefore, reducing dependency parsing errors and selecting
  high quality dependencies is of primary importance. In this study, we
  present a language-independent approach for automatically selecting
  high quality dependencies from automatic parses. By considering several
  aspects that affect the accuracy of dependency parsing, we created a
  set of features for supervised classification of reliable
  dependencies. Experimental results on seven languages show that our
  approach can effectively select high quality dependencies from
  dependency parses.
}
\ekeywords{Dependency Parsing, Dependency Selection, Knowledge Acquisition}

\headauthor{Jin, Kawahara, Kurohashi}
\headtitle{High Quality Dependency Selection}

\affilabel{Author_1}{}{Graduate School of Informatics, Kyoto University}


\begin{document}

\maketitle


\section{Introduction}

Knowledge acquisition from a large corpus has been actively studied
in recent years. Fundamental analysis techniques have been applied to a corpus and
knowledge is acquired from the analysis. In particular, dependency
parsing has been used for tasks like case frame compilation \cite{Kawahara:2006},
relation extraction \cite{Saeger:2011}, and paraphrase
acquisition \cite{Hashimoto:2011}. For these tasks,
the accuracy of dependency parsing is vital. Although the accuracy of
state-of-the-art dependency parsers for some languages like English and Japanese is over
90\%, it is still not high enough to acquire accurate
knowledge. Furthermore, if one tries to apply this method of knowledge
acquisition to difficult-to-analyze languages like Chinese and Arabic,
the quality of the resulting knowledge worsens.

During the dependency parsing process, even if a parser's average performance is high, certain types of dependency relations are judged with high accuracy but other types with very low accuracy. In addition, some types of dependency structures are relatively difficult for any parser to correctly analyze.
As a result, a parser will tend to produce automatic parses of varying levels of quality, depending on the properties of dependency.
Using full structures of automatic parses for subsequent tasks, such as the extraction of predicate-argument structures, will inevitably lead to noisy results.
In practice, however, several tasks do not require full parse structures but only partial ones \cite{flannery}.
To avoid the propagation of errors from automatic analyses, it is preferable to use only high quality dependencies for knowledge acquisition rather than automatic parses. 
In this study, we present a supervised language-independent approach for selecting high quality
dependencies from automatic parses. This method considers
linguistic features that are related to the level of 
difficulty inherent in dependency parsing. We use a single set of dependency labeled data, such as Treebank, part of which is used to train a dependency
parser. We conduct experiments on seven languages, five of which are
Indo--European languages and two non-Indo--European languages (Chinese and
Japanese). The experimental results show that for all the languages, our proposed method can
select high quality dependencies than baseline methods.

This study is organized as follows. Section \ref{related} reviews some
research relevant to our approach.
Section \ref{system} describes the high quality dependency selection process.
Section \ref{exp} presents a detailed description of our research, conducted using three languages, along with the results.
Section \ref{additional} describes several additional experiments conducted using other languages.
Section \ref{discuss} presents a discussion of our results. 
Finally, Section \ref{conclusion} presents a conclusion of our approach and proposes future
work.


\section{Related Work}\label{related}

There have been several approaches devoted to automatic selection of
high quality parses or dependencies. According to selection
algorithms, they can be categorized as 
supervised and unsupervised methods.

Supervised methods primarily focus on the construction of a machine
learning classifier and predict the reliability of parses or dependencies
on the basis of various syntactic and semantic features. 
\citeA{Yates:2006} created WOODWARD, which is a
Web-based semantic filtering system. They first mapped the parses to a logic-based representation called {\it relational conjunction} (RC).
Thereafter, four different methods were employed to analyze whether a conjunct in the RC representation was likely to be reasonable.
\citeA{Kawahara:2008} built a binary classifier that determines the reliability of each parse. The linguistic
features they used for the classification, such as sentence length, the number of
unknown words, and the number of commas, are based on the idea that
the reliability of parses is determined by the degree of sentence difficulty.
The work most related to ours is that of \citeA{Yu:2008}.
They proposed a framework that selects high quality parses in the first
stage and then high quality dependencies from those parses. In comparison with their work, we consider that even some low
quality sentences can contain high quality dependencies. In addition, we take into
account other characteristics that can directly affect high quality dependency
selection, such as context information and tree features.

Among supervised methods, ensemble approaches were also proposed.
For example, Reichart and Rappoport (2007)\nocite{Reichart:2007} judged parse quality using a 
Sample Ensemble Parse Assessment (SEPA) algorithm. They trained several
different parsers by using samples from the training data. Thereafter,
the level of agreement among those parsers was used to predict the quality
of the parse. Another similar approach proposed by Sagae and Tsujii (2007)
\nocite{Sagae:2007} also selected high quality parses by computing the
level of agreement among different parser outputs. However, different from the
research previously mentioned, which used several constituency parsers trained with
different training data sets, they used a single data set to train different dependency parsing algorithms. 
Different from the abovementioned methods, our method judges the reliability of each dependency produced by a parser.

Unsupervised algorithms for detecting reliable dependency
parses have been proposed. 
Observing the score of each edge is a basic method for judging the reliability of each dependency \cite{Iwatate:2012}.
\nocite{Yoav2012} Goldberg and Elhadad (2012) proposed a method of assigning each edge a risk score as the inverse of the confidence score defined by a risk function.
However, selecting dependencies purely on the basis of such scores is not sufficient for judging high quality dependencies.
We reached this same conclusion in our comparative evaluations of dependency selection approaches on different languages.
Reichart and Rappoport (2009)\nocite{Reichart:2009}
proposed an unsupervised method for high quality parse selection, based on the idea that syntactic
structures frequently produced by a parser are more likely to
be accurate than those produced less frequently.
They developed POS-based Unsupervised Parse Assessment Algorithm (PUPA) to
calculate the statistics summarizing the POS tag sequences of parses produced
by an unsupervised constituency parser.

\citeA{Dell:2011} proposed 
ULISSE (Unsupervised LInguiStically driven Selection of
dEpendency parses), which is also an unsupervised system. Different from PUPA, 
this method addressed the reliable parse selection task using
an unsupervised method in a supervised parsing scenario. Rather than using constituency-related features, such as ordered POS tag sequences,
they used dependency-motivated features, such as parse tree depth and
dependency link length.
Although unsupervised methods may solve the domain adaption issue and
do not use costly annotated data, the
accuracy of selected parses, which is less than 95\%, still needs to be
improved for knowledge acquisition tasks.


\section{High Quality Dependency Selection}\label{system}

In this section, we present a framework for highly reliable dependency
selection from automatic parses. Figure 1 shows the overview of our
approach. We use a part of a treebank dataset to train a parser and another part to train a binary classifier that judges the reliability of a dependency. 
We use support vector machines (SVMs) for 
this classification.

\begin{figure}[b]
\begin{center}
\includegraphics{21-6ia3f1.eps}
\end{center}
\caption{Overview of high quality dependency selection}
\end{figure}


\subsection{Training Data for Dependency Selection}

Supervised methods always require manually annotated training data
that are usually very expensive to obtain. Owing to limited existing
resources, we train a classifier for selecting highly reliable
dependencies from parsing outputs using training data from the same
treebank that is used in the first stage dependency parsing.
In particular, the standard training section of the treebank is used to
train a dependency parser and then the development section is used to apply
dependency parsing using the previously trained parser.
From the output parses of the development section, we acquired
training data for dependency selection by collecting each dependency.
We then judge the success of each dependency according to the gold
standard data. All correct dependencies were used as positive training examples for dependency selection and
vice versa.


\subsection{Dependency Selection}\label{subsec-filtering}

\begin{table}[b]
\caption{Basic features for dependency selection}
\input{03table01.txt}
\end{table}
\begin{table}[b]
\caption{Context features for dependency selection}
\input{03table02.txt}
\end{table}
\begin{table}[b]
\caption{Tree features for dependency selection}
\input{03table03.txt}
\end{table}

We judge the dependency in each parse and retain only high quality output for knowledge acquisition. There are many factors that affect the parsing
performance, such as distance between dependencies and complexity of tree structures. By taking these
factors into consideration, we create sets of features for
selecting high quality dependencies. Tables 1, 2, and
3 present the details of these features.


\subsubsection{Basic Features}

If there is a comma, colon or semi-colon between two words, they are much less likely to have a dependency relation than those pairs that do not contain any punctuation. It is much more difficult for parsers to correctly analyze dependencies that contain punctuation than those without punctuation.
We use the most common punctuations as features for dependency selection. A dependency relation between words is much more likely when arguments are nearby \cite{McDonald:2007}. 
Therefore, distance between words is also an important factor that reflects
the difficulty of judging dependency relations. 
Yu et al. (2008) used the abovementioned features but did not use 
$\mathit{Word_{head}}$, $\mathit{Word_{mod}}$, or the context features, which are described in the next section.


\subsubsection{Context Features }

In addition to these basic features, we consider context features
that are thought to affect parsing performance. Table 2 lists
these context features.
For example, the two sentences ``they
eat salad with a fork'' and ``they eat salad with sauce'' contain the PP-attachment ambiguity
problem, which is one of the most difficult problems encountered in
parsing. The two prepositional phrases ``with a fork'' and ``with sauce''
depend on the verb ``eat'' and the noun ``sauce,'' respectively.
However, a dependency parser can hardly resolve these two cases.
Therefore, we tend to judge this type of structure as unreliable.
Consider another similar sentence ``they eat it
with a fork.'' Because the prepositional phrase ``with a fork'' cannot
depend on the pronoun ``it'' but only on the verb ``eat,'' this
case can be clearly judged as a highly reliable dependency. In some
more complex cases, it is also necessary to observe a larger span of
context. To learn such linguistic characteristics automatically, besides
POS tags and the head and modifier in a dependency, we also use the preceding and
following one and two words, respectively, along with the POS tags of the abovementioned linguistic characteristics.

Another important fact is that verb phrases in the dependency tree structure of a
parse are normally the root node of the entire dependency tree or the parent node of
a subtree. When a word pair contains a verb phrase between them,
the two words are always on different sides of the parent node. Thus,
these kinds of word pairs normally have no dependency link between them. 
For example, in SVO (subject-verb-object) languages such as English and Chinese, the subject
appears first, the verb second, and then the object third.
The most common example of this is when the subjects and objects located on both sides of the
verb are the modifiers of the verb. Therefore, argument pairs that have a verb 
between them rarely have a dependency relation. Observing whether
there are verb phrases between head-modifier pairs can help judge
dependency reliability.


\subsubsection{Tree Features }

The input for our high quality dependency selection method is a dependency tree. It is natural to use tree
features to identify dependency quality.
On the basis of a head-modifier dependency, we observe modifiers of a modifier, i.e., children nodes, 
a head's parent node---which are called grandparent nodes---and children nodes of the grandparent node, which we call uncle nodes.


\subsubsection{Edge Score }

Some dependency parsers output the score of each dependency (i.e., edge confidence value) during the parsing process.
A high score indicates a high possibility that the dependency is correct.
However, utilizing this score as the only feature is not sufficient for acquiring high quality dependencies, especially in low quality parses.
We consider the real value of the score as an additional feature.


\section{Main Experiments}\label{subsec-construction}\label{exp}

\subsection{Experimental Settings}

We first conducted our experiment on three languages, including English, Japanese, and Chinese, using the data from the CoNLL-2009 shared task \cite{hajivc-EtAl:2009:CoNLL-2009-ST}.
For each language, we employed the MSTparser\footnote{http://www.seas.upenn.edu/{\textasciitilde}strctlrn/MSTParser/MSTParser.html} (version 0.5.0)
as a base dependency parser and use the training data to train a dependency parsing model. 
KD-Fix (0.05 * 20) confidence score \cite{KDFix} is one of the edge score calculation methods in the MSTparser,
which was reported as the best method for the MSTparser to predict edge scores. We used the KD-Fix value as the edge score in all experiments.
We applied the development data to the dependency parsing
model to acquire the training data for dependency selection.
We used automatic POS tags for the dependency selection approach (automatic segmentation for Japanese and Chinese).
The MXPOST\footnote{http://www.inf.ed.ac.uk/resources/nlp/local\_doc/MXPOST.html}
tagger was used for English automatic POS tagging, and for 
Chinese, we employed MMA \cite{Kruengkrai:2009}
to apply both segmentation and POS tagging.
We used JUMAN\footnote{http://nlp.ist.i.kyoto-u.ac.jp/EN/index.php?JUMAN}
for Japanese morphological analysis.

From the dependency parser output, we collected training data for
high quality dependency selection. All correct dependencies,
according to the gold standard data, were defined as positive examples and vice
versa. We utilized SVMs to complete this binary classification task, specifically,
we employed SVM-Light\footnote{http://svmlight.joachims.org/} with a linear kernel.
The option -j {\it ratio} was used to solve the positive and negative imbalance in the training data for the classifier, where
{\it ratio} was calculated by dividing the number of negative samples by the number of positive samples.

In order to compare these results with the work done by Yu et al. (2008), we set the basic feature as
a baseline. The evaluation data for each language was then used to evaluate the effectiveness of dependency selection.


\subsection{Evaluation Metrics}

On the basis of the output of the SVMs, we selected
dependencies with output scores greater than a specific threshold, with a higher output score indicating a more reliable dependency.
As a result, a high threshold meant a low recall. Thereafter, we
evaluated the selected dependencies by calculating the percentage of correct
head-modifier dependencies (excluding punctuations) according to the gold standard
data. Precision and recall were calculated as follows. 
\begin{gather*}
 \mathit{precision} = \frac{\#\ \text{\itshape of correctly retrieved dependencies}}{\#\ \text{\itshape of dependencies retrieved}} \\
 \mathit{recall} = \frac{\#\ \text{\itshape of correctly retrieved dependencies}}{\#\ \text{\itshape of correct dependencies in gold standard data}}
\end{gather*}
In automatically tagged and parsed Chinese and Japanese data, there were segmentations that were incorrectly produced.
These cases were treated as incorrect instances. Note that the maximum recall for each language was equal to the precision of the base parser.


\subsection{Experimental Results}

\subsubsection{Effectiveness of Dependency Selection }

Figure 2 shows the precision-recall curves of the selected dependencies
using SVMs. Different criteria were used for all languages.
The curves labeled ``basic feat.'' indicates that basic features were used for the dependency selection.
``Score'' is the method that selects dependencies with the edge scores (MSTparser's KD-Fix) higher than the threshold.
Note that this method does not use SVMs. ``Prop feat.'' indicates that proposed features were used, in which the real values of the edge scores were used as a feature in the classifier. We can see from the results that our proposed features outperformed the other feature sets in most cases, especially for Chinese and Japanese.

\begin{figure}[t]
\begin{center}
\includegraphics{21-6ia3f2.eps}
\end{center}
\hangcaption{Precision-recall curves of selected dependencies for English (left), Japanese (middle) and Chinese (right)}
\end{figure}
\begin{figure}[t]
\begin{center}
\includegraphics{21-6ia3f3.eps}
\end{center}
\hangcaption{Precision-recall curves of selected dependencies using different features for English (left), Japanese (middle) and Chinese (right)}
\end{figure}

To investigate the feature that is most effective on the dependency selection,
we plotted different precision-recall curves using different feature combinations (Figure 3).
Note that ``all'' is equal to our proposed method in Figure 2, which uses all features.
We can see that all features work differently for different languages.
For example, edge scores can effectively help select high quality dependency for English but context and tree-based features perform better on Japanese.
Those languages have different base parser's performance and different dependency styles (e.g., head-final for Japanese).
We speculate that features such as distance between arguments and comma have a significant influence on Japanese dependency selection.


\subsubsection{Statistics of Selected Dependencies }

In this section, we investigate the distribution of dependencies in order to determine the primary types selected.
This investigation lets us observe whether selected dependencies are biased towards certain types of POS (e.g., meaningless patterns, such as ``DT NN'').
Each dependency type was represented by coarse-grained POS pairs (the first two characters of the POS
names). Figures 4 and 5 summarize the statistics for selected dependency POS pairs
using different methods for different languages. In each figure, the left and middle
graphs represent the dependencies selected under different thresholds (i.e., 50\% and 20\% recall, respectively),
and the rightmost graphs are plotted without the dependency selection.

\begin{figure}[b]
\begin{center}
\includegraphics{21-6ia3f4.eps}
\end{center}
\hangcaption{Statistics summarizing dependency POS tags that use the proposed method: dependencies
 without selection (right), dependencies with 50\% recall (middle),
 dependencies with 20\% recall (left)}
\end{figure}

For all languages, under both selection methods (i.e., proposed method and the selection method by edge score), dependencies with nouns were dominant across all types.
For large-scale knowledge acquisition, however, dependencies with verbs
are most important because verb phrases always contain most of the
information about a specific event. Therefore, verb phrase extraction is key in recognizing predicate-argument 
structures in knowledge acquisition.
The pattern ``NN VB'' also was prominent, which indicates that 
predicate-argument dependencies were still selected quite frequently among the high quality
dependencies.

Selecting dependencies using different features will inevitably lead to the loss of 
some informative patterns along with those that are considered noisy.
From the results, both selection methods have similar tendencies in selecting various types of dependencies.
The key point here is that our proposed method, which used different types of features, still produced a high proportion of informative dependencies.

\begin{figure}[t]
\begin{center}
\includegraphics{21-6ia3f5.eps}
\end{center}
\hangcaption{Statistics summarizing dependency POS tags that use edge scores: dependencies
 without selection (right), dependencies with 50\% recall (middle),
 dependencies with 20\% recall (left)}
\end{figure}


\section{Additional Experiments}\label{additional}

\subsection{Experiments on Other Languages}

We applied additional multilingual experiments on Catalan, Czech, Spanish,
and German using the CoNLL-2009 shared task data. The MSTparser again was used for dependency parsing. Note that
these languages possess the non-projective property, which indicates crossing edges in a dependency tree.
They allow for more constructions than the projective constraint.
As a result, the non-projective option in
MSTparser was triggered. Figure 6 shows the precision-recall curves of dependency selection for these four languages.
We directly used the 6th column in the CoNLL-2009 shared task data as automatic POS tags.

\begin{figure}[b]
\begin{center}
\includegraphics{21-6ia3f6.eps}
\end{center}
\hangcaption{Precision-recall curves of dependency selection in four
 different Indo-European languages: \mbox{Catalan} (top left), Czech (top right),
 Spanish (bottom left), and German (bottom right)}
\end{figure}
\begin{table}[b]
\caption{Precision of selected dependencies under different criteria}
\input{03table04.txt}
\end{table}

For each language, we exhibited the precision at various recall values in order to highlight the quality of selected dependencies under different selection thresholds.
Table 4 shows the precision of dependencies selected by our method under 20\% and 50\% recall for all languages.
From the results, we can see that the dependency selection method that used our proposed features
outperformed the method that used the basic features for all languages. For Japanese, Chinese, and Catalan, using the proposed features had
a greater effect on high quality dependency selection than other languages, compared to the method only using the edge scores.


\subsection{Experiment on Different Domain}

One of the biggest problems that most data-driven parsers face 
is the domain adaptation problem in that their accuracy decreases significantly owing to the
lack of domain-specific knowledge. We applied the dependency parsing model trained on section 2 to section 21 of the Penn Treebank (PTB) to the Brown corpus, and obtained an
unlabeled attachment score of 0.832, which is significantly lower than
the in-domain score by 7.4\%.

\begin{figure}[b]
\begin{center}
\includegraphics{21-6ia3f7.eps}
\end{center}
 \caption{Precision-recall curves of dependency selection from the Brown corpus}
\end{figure}

We applied the same dependency selection model trained on the PTB training sections to the
pBrown corpus. Figure 7 shows the precision-recall curves for dependency
selection on the PTB test section (section 23) and the Brown corpus using different selecting methods.
Similarly to previous figures, ``brown basic'' indicates selection using basic features. ``Brown score'' indicates only edge scores were used for classification.
``Brown prop.'' and ``ptb prop.'' represent proposed features were used for dependency selection on brown corpus and PTB, respectively.
From the results, we can see that our proposed method outperforms the one that used basic features,
and also has an advantage over the method that used edge scores with low recall.
For examples, when the recall was 20\%, high quality dependencies with a precision greater than 
98\% could be acquired. This shows that our method works well on data
from different domains and that there is a way to acquire
knowledge from a large raw corpus in different domains (e.g., the Web).


\subsection{Experiment using Different Proportions of Training Data}

To determine the amount of training data required to achieve a reasonable dependency selection performance,
we used different proportions of the PTB development section to train different classifiers.
Thereafter, we used the same test set to evaluate each classifier using the same metric described in Section 4.
Note that the method that uses only the edge scores does not change with different data proportions
(i.e., one should get similar classification performance using the edge score as a feature regardless of the size of the training data set).
Thus, we only used features including ``basic'', ``context'', and ``tree'' in this experiment.
Figure 8 shows the precision-recall curves of dependency selection obtained using different sized training data sets.
The performance decreases slightly when the training data set decreases in size. 
However, a precision greater than 98\% is still achievable when the recall is 20\%, even when using only 25\% of the training data. 
From the results, we can see that training data sets of various sizes can be used to train effective classifiers.

\begin{figure}[b]
\begin{center}
\includegraphics{21-6ia3f8.eps}
\end{center}
 \caption{Precision-recall curves of dependency selection obtained using training data sets of various sizes}
\end{figure}


\subsection{Experiment using a Different Parser}

As MSTparser is a graph-based dependency parser, we wanted to further test our proposed framework on different types of syntactic parsers.
Therefore, we choose the Stanford parser\footnote{http://nlp.stanford.edu/software/lex-parser.shtml}, a probabilistic context-free grammar (PCFG) parser.
Although the output of the Stanford parser can be converted into dependency style,
it is unable to output an edge score.
As a result, we used features including ``basic'', ``context'' and ``tree'' in this experiment.
We conducted the experiment on English and Chinese. 
We directly used English raw text and Chinese segmented text by MMA as input, and employed the Stanford parser for POS tagging and parsing.
Figure~9 shows the precision-recall curves for English and Chinese.
English can achieve high precision around 98.5\% when the recall is 25\%.
Even though the base parser for Chinese achieved only 67.5\%, we can still extract dependencies with over 92\% precision.

\begin{figure}[t]
\begin{center}
\includegraphics{21-6ia3f9.eps}
\end{center}
 \caption{Precision-recall curves of dependency selection obtained using the Stanford parser}
\end{figure}


\subsection{Using Dependency Selection in Other Tasks}

We applied our proposed dependency selection approach to predicate-argument structure extraction and distributional similarity calculation.
First, we applied the dependency selection to automatic parses and used only high quality edges to extract predicate-argument structures. 
With a central focus on verbs in each dependency tree, we used only verb-dependent arguments and represented each argument by its syntactic surface case (i.e., subject, object, prepositional phrase, etc.) 
with sets of heuristic conversion rules.
Distributional similarity is a method that determines word similarity on the basis of a metric derived
from the distribution of the verb and its arguments 
in a large text corpus \cite{Lin:1998:ACLCOLING}.

For English, we used a large-scale Web corpus that contained 200 million sentences.
We employed the Wordsim353\footnote{http://alfonseca.org/eng/research/wordsim353.html} data set for evaluation,
which contains human-assigned similarities between each word pair.
For Chinese, five million sentences from the Chinese Gigaword were used for distributional similarity calculation.
We also used a manually constructed gold-standard data set\footnote{http://www.cs.york.ac.uk/semeval-2012/task4/} containing more than 500 word pairs for Chinese word similarity evaluation.

For each word pair in the evaluation set, we evaluated the word similarity using the distributional thesauri
calculated using the acquired predicate-argument pairs. We used spearman's correlation coefficient, calculated by comparing the ranks between the two sets of similarities (i.e., gold similarities, and automatically calculated similarities), to evaluate the quality of the thesauri.

Data size is an important factor that can affect distributional similarity calculations.
Therefore, to compare the thesauri calculated from predicate-argument pairs of various sizes, 
we randomly sampled different sized sets of predicate-argument pairs.
Figure 10 shows the Spearman coefficient values for the distributional similarity calculations under the three criteria mentioned above.
As we can see, performance of distributional similarity calculations can be improved by selecting high quality dependencies, for both Chinese and English.
Using the dependency selection process, the negative effects that the noisy data can have on semantic representation of word similarity can be effectively reduced.
The result shows that the quality of dependencies and data size are both important factors for distributional similarity calculation.

\begin{figure}[t]
\begin{center}
\includegraphics{21-6ia3f10.eps}
\end{center}
\caption{Spearman values under different selection thresholds}
\end{figure}


\section{Discussion}
\label{discuss}

We achieved dependency precisions of 99.6\%, 97.8\%, and 98.8\% for English, 
Chinese, and Japanese, respectively, using automatically tagged data with a recall of 20\%.
All four European languages have around 99.5\% precision under this recall.
Our proposed features show a significant advantage over the original feature set proposed in the
previous study of Yu et al. (2008). By taking into account context and tree information, we can
effectively help the system learn automatic dependency parse reliability not only from the same domain but also from other domains. 
As shown in the experiments, the results are quite promising for different types of syntactic parsers, as well.

The statistics calculated for selected dependencies showed that even when we adopted a
low recall value to obtain a high precision they contained many dependencies related to
nouns and verbs. The low recall (e.g., 20\%) can be compensated for by using very large raw
corpora, which are relatively easy to acquire. The applicability to different domains also allows us to
acquire knowledge from large raw corpora of various domains.
Moreover, our proposed approach can benefit subsequent NLP tasks, such as distributional similarity calculation.

Each feature type had a different influence on different languages. 
For example, English and Chinese performed similarly when using edge scores vs. proposed features.
However, Japanese showed better performance using our proposed features.
We speculate that features such as the distance between arguments and commas had a significant influence on Japanese dependency selection.
Even though selection using edge scores can help acquire high quality dependencies,
which sometimes have similar performance to our proposed features, it is very important to note that edge scores are not always available for different types of parsers (e.g., Stanford parser). 
Furthermore, producing edge scores (e.g., KD-Fix of MSTparser) demands a larger amount of computer memory, which
normally makes it impractical to apply parallel analyses to large-scale corpora in practice.


\section{Conclusion and Future Work}\label{conclusion}

In this study, we proposed a classification approach for high quality
dependency selection. We created a set of features that consider context and tree information in selecting highly reliable
dependencies from parsed sentences. This approach can extract high quality dependencies even from low quality parses.
The experiments showed that our method works for in-domain
parses as well as out-of-domain parses. 

We can extract high quality dependencies from a large corpus such as
the Web, and can subsequently assist knowledge acquisition tasks, such as
subcategorization frame acquisition \cite{Korhonen:2006} and case frame compilation \cite{Kawahara:2010}, which depend highly on the parse
quality. 

Since automatic parses can be used to improve the base parser itself \cite{Chen:2009},
we plan to use a bootstrapping strategy to improve dependency parsers based on high quality
knowledge acquired from large corpora.


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

\bibitem[\protect\BCAY{Chen, Kazama, \mbox{Uchimoto}, \BBA\ Torisawa}{Chen
  et~al.}{2009}]{Chen:2009}
Chen, W., Kazama, J., \mbox{Uchimoto}, K., \BBA\ Torisawa, K. \BBOP 2009\BBCP.
\newblock \BBOQ Improving Dependency Parsing with Subtrees from Auto-Parsed
  Data.\BBCQ\
\newblock In {\Bem Proceedings of EMNLP 2009}, \mbox{\BPGS\ 570--579}.

\bibitem[\protect\BCAY{Dell'Orletta, Venturi, \BBA\ Montemagni}{Dell'Orletta
  et~al.}{2011}]{Dell:2011}
Dell'Orletta, F., Venturi, G., \BBA\ Montemagni, S. \BBOP 2011\BBCP.
\newblock \BBOQ ULISSE: An Unsupervised Algorithm for Detecting Reliable
  Dependency Parses.\BBCQ\
\newblock In {\Bem Proceeding of CoNLL 2011}, \mbox{\BPGS\ 115--124}.

\bibitem[\protect\BCAY{Flannery, Miayo, Neubig, \BBA\ Mori}{Flannery
  et~al.}{2011}]{flannery}
Flannery, D., Miayo, Y., Neubig, G., \BBA\ Mori, S. \BBOP 2011\BBCP.
\newblock \BBOQ Training Dependency Parsers from Partially Annotated
  Corpora.\BBCQ\
\newblock In {\Bem Proceedings of IJCNLP 2011}, \mbox{\BPGS\ 776--784}.

\bibitem[\protect\BCAY{Goldberg \BBA\ Elhadad}{Goldberg \BBA\
  Elhadad}{2012}]{Yoav2012}
Goldberg, Y.\BBACOMMA\ \BBA\ Elhadad, M. \BBOP 2012\BBCP.
\newblock \BBOQ Precision-biased Parsing and High-Quality Parse
  Selection.\BBCQ\
  \texttt{http://www.cs.bgu.ac.il/{\textasciitilde}yoavg/publications/emnlp2012confidencea.pdf}.

\bibitem[\protect\BCAY{Haji\v{c}, Ciaramita, Johansson, Kawahara, Mart\'{\i},
  M\`{a}rquez, Meyers, Nivre, Pad\'{o}, \v{S}t\v{e}p\'{a}nek, Stra\v{n}\'{a}k,
  Surdeanu, Xue, \BBA\ Zhang}{Haji\v{c}
  et~al.}{2009}]{hajivc-EtAl:2009:CoNLL-2009-ST}
Haji\v{c}, J., Ciaramita, M., Johansson, R., Kawahara, D., Mart\'{\i}, M.~A.,
  M\`{a}rquez, L., Meyers, A., Nivre, J., Pad\'{o}, S., \v{S}t\v{e}p\'{a}nek,
  J., Stra\v{n}\'{a}k, P., Surdeanu, M., Xue, N., \BBA\ Zhang, Y. \BBOP
  2009\BBCP.
\newblock \BBOQ The CoNLL-2009 Shared Task: Syntactic and Semantic Dependencies
  in Multiple Languages.\BBCQ\
\newblock In {\Bem Proceedings of the 13th Conference on Computational Natural
  Language Learning (CoNLL 2009): Shared Task}, \mbox{\BPGS\ 1--18}, Boulder,
  Colorado. Association for Computational Linguistics.

\bibitem[\protect\BCAY{Hashimoto, \mbox{Torisawa}, Saeger, Kazama, \BBA\
  Kurohashi}{Hashimoto et~al.}{2011}]{Hashimoto:2011}
Hashimoto, C., \mbox{Torisawa}, K., Saeger, S.~D., Kazama, J., \BBA\ Kurohashi,
  S. \BBOP 2011\BBCP.
\newblock \BBOQ Extracting Paraphrases from Definition Sentences on the
  Web.\BBCQ\
\newblock In {\Bem Proceedings of ACL 2011}, \mbox{\BPGS\ 1087--1097}.

\bibitem[\protect\BCAY{Iwatate}{Iwatate}{2012}]{Iwatate:2012}
Iwatate, M. \BBOP 2012\BBCP.
\newblock {\Bem Development of Pairwise Comparison-based Japanese Dependency
  Parsers and Application to Corpus Annotation}.
\newblock Ph.D.\ thesis, NAIST, Japan.

\bibitem[\protect\BCAY{\mbox{Kawahara} \BBA\ Kurohashi}{\mbox{Kawahara} \BBA\
  Kurohashi}{2006}]{Kawahara:2006}
\mbox{Kawahara}, D.\BBACOMMA\ \BBA\ Kurohashi, S. \BBOP 2006\BBCP.
\newblock \BBOQ A Fully-Lexicalized Probabilistic Model for Japanese Syntactic
  and Case Structure Analysis.\BBCQ\
\newblock In {\Bem Proceedings of HLT-NAACL 2006}, \mbox{\BPGS\ 176--183}.

\bibitem[\protect\BCAY{Kawahara \BBA\ \mbox{Kurohashi}}{Kawahara \BBA\
  \mbox{Kurohashi}}{2010}]{Kawahara:2010}
Kawahara, D.\BBACOMMA\ \BBA\ \mbox{Kurohashi}, S. \BBOP 2010\BBCP.
\newblock \BBOQ Acquiring Reliable Predicate-argument Structures from Raw
  Corpora for Case Frame Compilation.\BBCQ\
\newblock In {\Bem Proceedings of LREC 2010}, \mbox{\BPGS\ 1389--1393}.

\bibitem[\protect\BCAY{Kawahara \BBA\ Uchimoto}{Kawahara \BBA\
  Uchimoto}{2008}]{Kawahara:2008}
Kawahara, D.\BBACOMMA\ \BBA\ Uchimoto, K. \BBOP 2008\BBCP.
\newblock \BBOQ Learning Reliability of Parses for Domain Adaptation.\BBCQ\
\newblock In {\Bem Proceedings of IJCNLP 2008}, \mbox{\BPGS\ 709--714}.

\bibitem[\protect\BCAY{\mbox{Korhonen}, Krymolowski, \BBA\
  Briscoe}{\mbox{Korhonen} et~al.}{2006}]{Korhonen:2006}
\mbox{Korhonen}, A., Krymolowski, Y., \BBA\ Briscoe, T. \BBOP 2006\BBCP.
\newblock \BBOQ A Large Subcategorization Lexicon for Natural Language
  Processing Applications.\BBCQ\
\newblock In {\Bem Proceedings of the 5th international conference on Language
  Resources and Evaluation}, \mbox{\BPGS\ 345--352}.

\bibitem[\protect\BCAY{Kruengkrai, Uchimoto, Kazama, Wang, Torisawa, \BBA\
  Isahara}{Kruengkrai et~al.}{2009}]{Kruengkrai:2009}
Kruengkrai, C., Uchimoto, K., Kazama, J., Wang, Y., Torisawa, K., \BBA\
  Isahara, H. \BBOP 2009\BBCP.
\newblock \BBOQ An Error-Driven Word-Character Hybrid Model for Joint Chinese
  Word Segmentation and POS Tagging.\BBCQ\
\newblock In {\Bem Proceedings of ACL-IJCNLP 2009}, \mbox{\BPGS\ 513--521}.

\bibitem[\protect\BCAY{Lin}{Lin}{1998}]{Lin:1998:ACLCOLING}
Lin, D. \BBOP 1998\BBCP.
\newblock \BBOQ Automatic Retrieval and Clustering of Similar Words.\BBCQ\
\newblock In {\Bem Proceedings of the 36th Annual Meeting of the Association
  for Computational Linguistics and 17th International Conference on
  Computational Linguistics, Volume 2}, \mbox{\BPGS\ 768--774}.

\bibitem[\protect\BCAY{McDonald \BBA\ Nivre}{McDonald \BBA\
  Nivre}{2007}]{McDonald:2007}
McDonald, R.\BBACOMMA\ \BBA\ Nivre, J. \BBOP 2007\BBCP.
\newblock \BBOQ Characterizing the Errors of Data-driven Dependency Parsing
  Models.\BBCQ\
\newblock In {\Bem Proceedings of EMNLP-CoNLL 2007}, \mbox{\BPGS\ 122--131}.

\bibitem[\protect\BCAY{Mejer \BBA\ Crammer}{Mejer \BBA\ Crammer}{2012}]{KDFix}
Mejer, A.\BBACOMMA\ \BBA\ Crammer, K. \BBOP 2012\BBCP.
\newblock \BBOQ Are You Sure? Condence in Prediction of Dependency Tree
  Edges.\BBCQ\
\newblock In {\Bem Proceedings of HLT-NAACL 2012}, \mbox{\BPGS\ 573--576}.

\bibitem[\protect\BCAY{Reichart \BBA\ Rappoport}{Reichart \BBA\
  Rappoport}{2007}]{Reichart:2007}
Reichart, R.\BBACOMMA\ \BBA\ Rappoport, A. \BBOP 2007\BBCP.
\newblock \BBOQ An Ensemble Method for Selection of High Quality Parses.\BBCQ\
\newblock In {\Bem Proceedings of ACL 2007}, \mbox{\BPGS\ 408--415}.

\bibitem[\protect\BCAY{Reichart \BBA\ Rappoport}{Reichart \BBA\
  Rappoport}{2009}]{Reichart:2009}
Reichart, R.\BBACOMMA\ \BBA\ Rappoport, A. \BBOP 2009\BBCP.
\newblock \BBOQ Automatic Selection of High Quality Parses Created By a Fully
  Unsupervised Parser.\BBCQ\
\newblock In {\Bem Proceedings of CoNLL 2009}, \mbox{\BPGS\ 156--164}.

\bibitem[\protect\BCAY{Saeger, Torisawa, Tsuchida, Kazama, Hashimoto, Yamada,
  Oh, Varga, \BBA\ Yan}{Saeger et~al.}{2011}]{Saeger:2011}
Saeger, S.~D., Torisawa, K., Tsuchida, M., Kazama, J., Hashimoto, C., Yamada,
  I., Oh, J.~H., Varga, I., \BBA\ Yan, Y. \BBOP 2011\BBCP.
\newblock \BBOQ Relation Acquisition using Word Classes and Partial
  Patterns.\BBCQ\
\newblock In {\Bem Proceedings of EMNLP 2011}, \mbox{\BPGS\ 825--835}.

\bibitem[\protect\BCAY{Sagae \BBA\ Tsujii}{Sagae \BBA\
  Tsujii}{2007}]{Sagae:2007}
Sagae, K.\BBACOMMA\ \BBA\ Tsujii, J. \BBOP 2007\BBCP.
\newblock \BBOQ Dependency parsing and Domain Adaptation with LR Models and
  Parser Ensemble.\BBCQ\
\newblock In {\Bem Proceedings of EMNLP-CoNLL 2007}, \mbox{\BPGS\ 408--415}.

\bibitem[\protect\BCAY{Yates, Schoenmackers, \BBA\ Etzioni}{Yates
  et~al.}{2006}]{Yates:2006}
Yates, A., Schoenmackers, S., \BBA\ Etzioni, O. \BBOP 2006\BBCP.
\newblock \BBOQ Detecting Parser Errors Using Web-based Semantic Filters.\BBCQ\
\newblock In {\Bem Proceedings of EMNLP 2006}, \mbox{\BPGS\ 27--34}.

\bibitem[\protect\BCAY{Yu, Kawahara, \BBA\ Kurohashi}{Yu
  et~al.}{2008}]{Yu:2008}
Yu, K., Kawahara, D., \BBA\ Kurohashi, S. \BBOP 2008\BBCP.
\newblock \BBOQ Cascaded Classification for High Quality Head-modifier Pair
  Selection.\BBCQ\
\newblock In {\Bem Proceedings of NLP 2008}, \mbox{\BPGS\ 1--8}.

\end{thebibliography}


\begin{biography}

\bioauthor[:]{Gongye Jin}{
   Gongye Jin received his B.S. in Computer and Computing Science from Zhejiang University City College (ZUCC) in 2009.
   He obtained his M.S. in Informatics from Kyoto University in 2012.
   He is currently a Ph.D. student in Informatics at Kyoto University.
 }

\bioauthor[:]{Daisuke Kawahara}{
   Daisuke Kawahara received his B.S. and M.S. in Electronic Science and
   Engineering from Kyoto University in 1997 and 1999, respectively. He
   obtained his Ph.D. in Informatics from Kyoto University in 2005. He is
   currently an associate professor at the Graduate School of Informatics
   at \mbox{Kyoto} University. His research interests center on natural language
   processing, particularly knowledge acquisition and text understanding.
 }

\bioauthor[:]{Sadao Kurohashi}{
   Sadao Kurohashi received the B.S., M.S., and Ph.D. in Electrical
   Engineering from Kyoto University in 1989, 1991 and 1994,
   respectively. He has been a visiting researcher of IRCS, University
   of Pennsylvania in 1994. He is currently a professor of the Graduate
   School of Informatics at Kyoto University. His research interests
   include natural language processing, knowledge
   acquisition/representation, and information retrieval. He received
   the 10th anniversary best paper award from journal of natural language
   processing in 2004, 2009 Funai IT promotion award, and 2009 IBM
   faculty award.
 }

\end{biography}

\biodate


\end{document}
