    \documentclass[english]{jnlp_1.4}

\usepackage{jnlpbbl_1.2}
\usepackage[dvips]{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{udline}
\setulminsep{1.2ex}{0.2ex}
\let\underline

\usepackage{lingmacros}
\usepackage{lflingmacros}
    \usepackage{jexample_plus_rev}
\usepackage{multicol}
\renewcommand{\cite}{}
\renewcommand{\citeA}{}
\newcommand{\newcite}{}
\input{macros}
\renewcommand{\emph}[1]{}



\Volume{17}
\Number{1}
\Month{January}
\Year{2010}

\received{2009}{7}{2}
\revised{2009}{8}{30}
\accepted{2009}{9}{30}

\setcounter{page}{183}

\etitle{Measuring the Appropriateness of \\
	Automatically Generated Phrasal Paraphrases}
\eauthor{Atsushi Fujita\affiref{FUN} \and Satoshi Sato\affiref{NU}}
\eabstract{
The most critical issue in generating and recognizing paraphrases is
developing a wide-coverage paraphrase knowledge base.
To attain the coverage of paraphrases that should not necessarily be
represented at surface level, researchers have attempted to represent
them with general transformation patterns.  However, this approach
does not prevent spurious paraphrases because there is no practical
method to assess whether or not each instance of those patterns
properly represents a pair of paraphrases.
This paper argues on the measurement of the appropriateness of such
automatically generated paraphrases, particularly targeting at
morpho-syntactic paraphrases of predicate phrases.
We first specify the criteria that a pair of expressions must satisfy
to be regarded as paraphrases.  On the basis of the criteria, we then
examine several measures for quantifying the appropriateness of a
given pair of expressions as paraphrases of each other.
In addition to existing measures, a probabilistic model consisting of
two distinct components is examined.  The first component of the
probabilistic model is a structured $N$-gram language model that
quantifies the grammaticality of automatically generated expressions.
The second component approximates the semantic equivalence and
substitutability of the given pair of expressions on the basis of the
distributional hypothesis.
Through an empirical experiment, we found (i)~the effectiveness of
contextual similarity in combination with the constituent similarity
of morpho-syntactic paraphrases and (ii)~the versatility of the Web
for representing the characteristics of predicate phrases.
}
\ekeywords{paraphrasing, appropriateness as paraphrases,
  morpho-syntactic paraphrase, predicate phrase, phrasal variants,
  semantic equivalence, substitutability, \\grammaticality}

\headauthor{Fujita and Sato}
\headtitle{Appropriateness of Automatically Generated
  Phrasal Paraphrases}


\affilabel{FUN}{
	}{School of Systems Information Science, Future University-Hakodate}
\affilabel{NU}{
	}{Graduate School of Engineering, Nagoya University}


\begin{document}

\maketitle


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

One of the common characteristics of human languages is that a concept
can be expressed with several different linguistic expressions.
Handling such synonymous expressions in a given language, i.e.,
\emph{paraphrases}, is one of the key issues in a broad range of
natural language processing (NLP) tasks \cite{inui:04:a-e}.
For example, the technology for recognizing whether or not a given
pair of expressions are paraphrases boosts the recall of information
retrieval, information extraction, and question answering.  The
technology also plays an important role in aggregating plenty of
uninhibited opinions about products and services available on the Web:
both the consumers and producers benefit from the summary.
On the other hand, a system that generates paraphrases of a given
expression is useful for text-transcoding tasks, such as machine
translation and summarization.  Such a system would also be extremely
beneficial to people by proposing alternative expressions for writing
assistance, simplifying texts for reading, and reducing homonyms for
improving text-to-speech quality.

The most critical issue in generating and recognizing paraphrases is
developing resources that cover a wide range of paraphrases.
One way of attaining such coverage was proposed by
\newcite{fujita:06:c-e}: first categorize paraphrases into several
classes by the knowledge required and generality, and then separately
develop resources for each class.
They divided paraphrases into the following four classes.
\numexs{classes}{
\item \emph{Lexical paraphrases}\\Emma \textit{burst into tears} and
  he tried to \textit{comfort} her.\\{\Lra} Emma \textit{cried} and he
  tried to \textit{console} her.\hfill\cite{barzilay:01}
\item \emph{Morpho-syntactic paraphrases}\\Employment \textit{showed a
  sharp decrease} in October.\\{\Lra} Employment \textit{decreased
  sharply} in October.\hfill\cite{iordanskaja:92}
\item \emph{(Pure) Syntactic paraphrases}\\\textit{It was his best
  suit that} John wore to the dance last night.\\{\Lra} John wore
  \textit{his best suit} to the dance last
  night.\hfill\cite{dras:99:a}
\item \emph{Inferential paraphrases}\\ There was no chance it would
  endanger our planet, astronomers said.\\{\Lra} NASA emphasized that
  there was never danger of a collision.\hfill\cite{dolan:04}}
Examples \refexs{classes}{a}, \refexs{classes}{b}, and
\refexs{classes}{c} have potential to be explained on the basis of
linguistic knowledge only, while some kinds of world knowledge is
necessary to identify the equivalence of example \refexs{classes}{d}.
Lexical and morpho-syntactic paraphrases involve changing the
constituent words, and thus have more variation than syntactic
paraphrases.  On that account, we believe that building resources for
lexical and morpho-syntactic paraphrases is essential for generating
and recognizing paraphrases robustly.

With the same line of thinking, most of the previous work on
generating and recognizing paraphrases has been dedicated to
developing resources for these classes.
Paraphrase knowledge for these classes is typically represented with
pairs of expressions that satisfy the following criteria.
\begin{description}
\item[Criterion 1.] Semantically equivalent
\item[Criterion 2.] Substitutable in some contexts
\end{description}
Examples of such paraphrase knowledge are shown in \refex{class1} and
\refex{class2}.
\numexs{class1}{
\item comfort {\Lra} console
\item burst into tears {\Lra} cried\hfill\cite{barzilay:01}}
\numexs{class2}{
\item show a sharp decrease {\Lra} decrease sharply
\item be in our favor {\Lra} be favorable to us\hfill\cite{fujita:07:a}}
The pairs of expressions in \refex{class1} exemplify atomic knowledge
for lexical paraphrases.  As they cannot be generalized into patterns,
a huge amount of fully lexicalized paraphrase knowledge should be
stored statically to generate and recognize this class of
paraphrases\footnote{Paraphrases of idiomatic and literal phrases,
  such as \pairs{kick the bucket}{die,} should also be included in
  this class of paraphrases \cite{fujita:06:c-e}.}.
On the other hand, morpho-syntactic paraphrases, such as verb
alternation, nominalization, and paraphrasing of light-verb
construction, exhibit a degree of generality as shown in
\refex{class2}.
It is therefore reasonable to represent them with a set of general
transformation patterns such as those shown in
\refex{pattern}\footnote{$X$ and $Y$ each denote a variable.  The
  subscript of a variable denotes its part-of-speech.
  $\mathit{v}(\cdot)$, $\mathit{adj}(\cdot)$, $\mathit{adv}(\cdot)$,
  and $\mathit{obj}(\cdot)$ are functions that return verb, adjective,
  adverb, and objective case of the given word, respectively.}.
\numexs{pattern}{
\item \begin{jexample}
\chunk{show}{show}
\chunk{a}{a}
\chunk{$X_{A}$}{sharp}
\chunk{$Y_{N}$}{decrease}
\chunk{\Lra}{}
\chunk{$\mathit{v}(Y_{N})$}{decrease}
\chunk{$\mathit{adv}(X_{A})$}{sharply}
\end{jexample}    
\item \begin{jexample}
\chunk{be}{is}
\chunk{in}{in}
\chunk{$X_{N}$}{our}
\chunk{$Y_{N}$}{favor}
\chunk{\Lra}{}
\chunk{be}{is}
\chunk{$\mathit{adj}(Y_{N})$}{favorable}
\chunk{to}{to}
\chunk{$\mathit{obj}(X_{N})$}{us}
\end{jexample}
}
The generalization enables us to attain higher coverage, keeping the
knowledge manageable.

Various methods have been proposed to acquire paraphrase knowledge
(see \ssec{acquisition}) where pairs of existing expressions are
collected from the given corpus, taking the above two criteria into
account.
However, another issue arises when paraphrase knowledge is generated
from the patterns for morpho-syntactic paraphrases, such as shown in
\refex{pattern}, by instantiating variables with specific words.
For example, neither of the following instances of pattern
\refexs{pattern}{a} is appropriate.
\numexs{instance}{
\item (statistics) show a gradual decline (of something) {\Lra}
  {\noteq} (statistics) decline gradually
\item (the data) show a specific distribution {\Lra} {\bad} (the data)
  distribute specifically}
The two phrases in \refexs{instance}{a} are not equivalent ($\neq$),
and the right-hand phrase of \refexs{instance}{b} is not even
grammatical, as indicated by the asterisk ($\ast$).
As exhibited by these examples, excessive generalization produces an
enormous number of spurious paraphrases.  To avoid this problem in
addition to criteria 1 and 2, the following criterion should be
adopted.
\begin{description}
\item[Criterion 3.] Both expressions are grammatical
\end{description}

We introduce the notion of ``\emph{appropriateness as paraphrases}''
as the degree to which a pair of expressions satisfies the
aforementioned three criteria, and examine several measures for
quantifying it.
While recent studies have tended to collect fully lexicalized
paraphrase knowledge as shown in \refex{class1} and \refex{class2}, we
focus on morpho-syntactic paraphrases generated from transformation
patterns such as those shown in \refex{pattern}.
In particular, we deal with morpho-syntactic paraphrases of predicate
phrases (henceforth, \emph{phrasal variants}) in Japanese, such as
follows\footnote{Abbreviations: \textsc{ACC} (accusative case),
  \textsc{COP} (copula), \textsc{DAT} (dative case), \textsc{GEN}
  (genitive case), \textsc{NEG} (negation), \textsc{NOM} (nominative
  case), \textsc{PAR} (particle), \textsc{PASS} (passive),
  \textsc{PUNC} (punctuation mark), and \textsc{TOP} (topic).}.
\numexs{ja-example}{
\item \begin{jexample}
\chunk{確認-を}{checking-\textsc{acc}}
\chunk{急ぐ}{to hurry}
\gloss{to hurry checking (something)}
\end{jexample}
{\Lra}\quad
\begin{jexample}
\chunk{急いで}{in a hurry}
\chunk{確認する}{to check}
\gloss{to check (something) in a hurry}
\end{jexample}
\item \begin{jexample}
\chunk{部屋-が}{room-\textsc{nom}}
\chunk{暖かく-なる}{be warm-to become}
\gloss{the room becomes warm}
\end{jexample}
{\Lra}\quad
\begin{jexample}
\chunk{部屋-が}{room-\textsc{nom}}
\chunk{暖まる}{to warm}
\gloss{the room becomes warm}
\end{jexample}
\item \begin{jexample}
\chunk{再現性-の}{reproducibility-\textsc{gen}}
\chunk{検証-を}{verification-\textsc{acc}}
\chunk{行う}{to do}
\gloss{to conduct a verification of the reproducibility}
\end{jexample}
{\Lra}\quad
\begin{jexample}
\chunk{再現-できる-かどうか-を}{to reproduce-able-whether-\textsc{acc}}
\chunk{検証する}{to verify}
\gloss{to verify whether it is reproducible}
\end{jexample}}
``Predicate phrase'' in this paper refers to a sub-parse governed by a
predicate, e.g., a verb and an adjective, and thus has a structure
that is bit more complex than words, word sequences, and paths in
dependency parses.  Furthermore, syntactic heads of phrasal variants
sometimes belong to different syntactic categories as the above
examples exhibit.

In this paper, we examine several measures to quantify the
appropriateness of given automatically generated pair of predicate
phrases.
Our first challenge in this paper is to investigate the applicability
of the distributional hypothesis \cite{harris:68} to the computation
of semantic equivalence and substitutability between predicate
phrases.
Another challenge is the data sparseness problem.  Generally speaking,
phrases appear less frequently than words.  This implies that we may
obtain only a small amount of contextual information for a given
phrase.  We therefore investigate the availability of the Web as a
corpus.
In addition to apply existing measures that are built upon the
distributional hypothesis, we propose and examine an novel
probabilistic model consisting of two distinct components.
The first component of our probabilistic model quantifies the
grammaticality, i.e., criterion 3, of each of the given phrases using
a structured $N$-gram language model.  The second component
approximates the semantic equivalence and substitutability of the
given pair of phrases, i.e., criteria 1 and 2, on the basis of the
distributional hypothesis.
Through an empirical experiment, we clarify the possibility and
effectiveness of explicitly assessing the grammaticality of the given
pair of phrases.

In the next section, we review the literature on developing paraphrase
knowledge and the characteristics and drawbacks of the existing
measures that have been used for acquiring paraphrase knowledge.
The proposed probabilistic model is then presented in \sec{proposed},
where the grammaticality and similarity factors are derived from a
conditional probability.  The setting of empirical evaluation is
described in \sec{setting}, and then the results and analyses are
shown in Sections \ref{sec:eval-gen} and \ref{sec:eval-rec}.
Following an error analysis in \sec{errors}, \sec{conclusion}
summarizes this paper.



\section{Related work}
\label{sec:relwork}

\subsection{Representation of paraphrase knowledge}
\label{ssec:representation}

Paraphrase knowledge for certain classes of paraphrases can be
represented with a set of general transformation patterns.  This makes
the knowledge manageable and attains higher coverage of paraphrases.
Following the transformation grammar \cite{harris:57}, many
researchers have attempted to develop transformation patterns
\cite{melcuk:87,dras:99:a,jacquemin:99,fujita:07:a}.

Lexical derivation has so far been the central topic in dealing with
phrasal variants, because it is indispensable for both generating and
constraining the instantiation of general transformation patterns.
Meaning-Text Theory \cite{melcuk:87} is one such framework, which
incorporates several types of lexical dependencies to deal with
various paraphrases.  A problem inherent in this theory is that a huge
amount of lexical knowledge is required to represent the more than 60
types of relationships between lexical items.
\newcite{jacquemin:99} represented the syntagmatic and paradigmatic
correspondences between paraphrases with context-free transformation
rules and morphological and/or semantic relations between lexical
items, targeting at morpho-syntactic paraphrases of technical terms
that are typically noun phrases consisting of more than one word.
Following the spirit of these previous studies, \newcite{fujita:07:a}
proposed a framework for generating phrasal variants and developed
resources in Japanese: a set of general transformation patterns and
dictionaries for handling lexical derivations.

However, no model in this approach is capable of preventing spurious
paraphrases because there is no practical method of measuring the
appropriateness of their instantiations.

\subsection{Automatic paraphrase acquisition}
\label{ssec:acquisition}

Since the late 1990's, the task of automatically acquiring paraphrase
knowledge has drawn the attention of an increasing number of
researchers.  They are tackling the problem, particularly focusing on
accuracy, although they have tended to notice that it is hard to
acquire paraphrase knowledge that ensures full coverage for various
paraphrases from existing text corpora alone.
To date, two streams of research have evolved: one acquires paraphrase
knowledge from parallel/comparable corpora, while the other uses a
regular corpus.

Several alignment techniques, which imitate those devised for machine
translation, have been proposed to acquire paraphrase knowledge from
parallel/comparable corpora.
Various sorts of parallel/comparable corpora have been used as a
source of paraphrase knowledge, such as multiple translations of the
same text \cite{barzilay:01,pang:03,ibrahim:03}, corresponding
articles from multiple news sources
\cite{shinyama:02,barzilay:03:a,dolan:04}, and bilingual corpora
\cite{wu:03:a,bannard:05}.
Unfortunately, this approach may not cover sufficiently wide variety
of paraphrases due to the difficulty of obtaining a
parallel/comparable corpus that contains all phrasal variants of all
predicate phrases.

In the second stream, i.e., paraphrase acquisition from a regular
corpus or the Web, the distributional hypothesis \cite{harris:68} has
been espoused.  The similarity of two expressions computed based on
this hypothesis is called distributional similarity.
This stream of measurement has the following three essential elements.
\begin{description}
\item[Representation of context:] To compute the similarity, a given
  expression is first represented with a set of expression that
  co-occur with it in a given corpus.  Expressions that co-occur with
  the given expression, such as adjacent words \cite{barzilay:01},
  adjacent character sequences \cite{yoshida:08}, complements of
  predicates \cite{torisawa:02:b}, modifiers/modifiees
  \cite{YamamotoKazuhide:02:d,weeds:05}, and indirect dependencies
  \cite{hagiwara:08:a} have so far been examined.  For the sake of
  convenience, we refer to those expressions as (contextual) features.
\item[Feature weighting:] To precisely compute the similarity, the
  weight for each feature is adjusted.  Point-wise mutual information
  \cite{lin:98:b} and Relative Feature Focus \cite{geffet:04} are
  well-known examples of methods for determining the weights.  A
  comparative study has been done by \newcite{hagiwara:08:b}.
\item[Similarity measures:] To convert two feature sets into a scalar
  value, several measures have been proposed, such as cosine, Lin's
  measure \cite{lin:98:b}, and Kullback-Leibler (KL) divergence and
  its variants.  Some of them will be explained in \ssec{existing}.
\end{description}

While most researchers have extracted only fully lexicalized pairs of
words or word sequences, two prominent algorithms have used dependency
parsers for collecting template-like knowledge that contains variable
slots, as shown in \refex{symmetric} and \refex{asymmetric}.
\numexs{symmetric}{
\item $X$ wrote $Y$ {\Lra} $X$ is the author of $Y$
\item $X$ solves $Y$ {\Lra} $X$ deals with $Y$\hfill\cite{lin:01}}
\numexs{asymmetric}{
\item $X$ prevents $Y$ {\Ra} $X$ decreases the risk of $Y$
\item $X$ goes back to $Y$ {\Ra} $Y$ allows $X$ to
  return\hfill\cite{szpektor:04}}
One of the algorithms, DIRT \cite{lin:01}, collects pairs of paths in
dependency parses that connect two nominal entities.  It utilizes
point-wise mutual information between paths and contextual features
for weighting and filtering operative features.  The similarity score
in DIRT is symmetrical for the given pair of paths and thus its
results are symmetric as in \refex{symmetric}.
On the other hand, TEASE algorithm \cite{szpektor:04} discovers
dependency sub-parses that are similar to a given transitive verb from
the Web using the sets of representative instances of subject and
direct object of the given verb.  As a result of taking the direction
into account, it outputs asymmetric patterns, such as exemplified in
\refex{asymmetric}.
Their approach acquires various types of relations between event
mentions: not only synonymous pairs of expressions, but also causal
and temporal relations.  The patterns that represent directional
relationship between expressions are thus called inference/entailment
rules.  The notion of paraphrase is defined as a bidirectional
inference/entailment relation.

The above knowledge falls between that in \refex{class1}, which is
fully lexicalized, and that in \refex{pattern}, which is almost fully
generalized.
As a way of enriching such template-like knowledge, several linguistic
clues, such as fine-grained classification of named entities
\cite{sekine:05}, have been utilized.  Although these clues restrict
the resultant paraphrases to those appearing in particular domains,
they enable us to collect paraphrases accurately.
\newcite{pantel:07} introduced the notion of Inferential Selectional
Preference (ISP) and collected expressions that would fill those
slots.  ISP can capture broader variety of paraphrases than the above
two; however, it cannot distinguish antonym relations.
\newcite{bhagat:07} proposed a method of determining the direction of
inference/entailment between given two templates.

As mentioned in \sec{intro}, the aim of the studies reviewed here is
to collect pairs of existing expressions likely to be paraphrases.
Therefore, they need not take the grammaticality of expressions into
account.

\subsection{Existing measures of the appropriateness as paraphrases}
\label{ssec:existing}

The appropriateness of the given pair of expressions as paraphrases
has so far been estimated on the basis of the distributional
hypothesis \cite{harris:68}, particularly targeting at relatively
short expressions, such as words, word sequences, and sub-parses.
\newcite{geffet:05} extended it to the distributional inclusion
hypothesis for recognizing the direction of lexical entailment.
\newcite{weeds:05}, on the other hand, pointed out the limitations of
lexical similarity and syntactic transformation and proposed directly
computing the distributional similarity between the given pair of
sub-parses using the distributions of their modifiers and modifiees.
To date, however, no model has been established that takes into
account all of the three aforementioned criteria.  With the ultimate
aim of building an ideal model, we present an overview of the
characteristics and drawbacks of the three existing measures closely
related to our work, leaving a comprehensive comparison of various
measures to \cite{weeds:03}.

\subsubsection{Focusing on the intersection of contextual features}

One way of implementing distributional similarity is to quantify the
overlap of the feature sets of each expression.
For example, \newcite{lin:98:b} proposed a symmetrical measure:
\begin{equation}
\mathit{Par_{Lin}}(s\Leftrightarrow t) = \frac{\sum_{f\in F_{s}\cap
    F_{t}}\bigl(w(s,f) + w(t,f)\bigr)}{\sum_{f\in F_{s}} w(s,f) +
  \sum_{f\in F_{t}} w(t,f)},\label{eq:lin}
\end{equation}
where $F_{s}$ and $F_{t}$ denote sets of features with positive
weights for words $s$ and $t$, respectively.

Although this measure has been widely cited and has so far performed
the task reasonably well, its symmetry seems unnatural (see example
\refex{asymmetric}).  Moreover, it may not work robustly when we deal
with general predicate phrases because it is not feasible to enumerate
all phrases to determine the weight of features $w(\cdot,\cdot)$.

\subsubsection{Divergence-based modeling}

Some researchers have modeled the distributional similarity with the
divergence of probability distributions.
The skew divergence, a variant of KL divergence, was proposed in
\cite{lee:99:a} on the basis of an insight: the substitutability of
one word for another need not be symmetrical.
The divergence is given by the following formula:
\begin{align*}
d_{\mathit{skew}}(t,s) &= D\bigl(P_{s}\|\alpha P_{t}+(1-\alpha)
	P_{s}\bigr),\\ 
D\bigl(P_{1}(X)\,\|\,P_{2}(X)\bigr)
	& = \sum_{x\in X}P_{1}(x)\log\frac{P_{1}(x)}{P_{2}(x)},
\end{align*}
where $P_{s}$ and $P_{t}$ are the probability distributions of
features of the given original and substituted words $s$ and $t$,
respectively.  How accurately $P_{t}$ approximates $P_{s}$ is
calculated on the basis of KL divergence $D$, where $\alpha$ ($0\leq
\alpha\leq 1$) is a parameter; it expresses KL divergence when
$\alpha=\text{1}$.
The divergence can be recast into a similarity score via, for example,
the following function.
\begin{equation}
\mathit{Par_{skew}}(s{\Rightarrow}t) =
	\exp\bigl(-d_{\mathit{skew}}(t,s)\bigr).\label{eq:skew}
\end{equation}

This measure offers an advantage over $\mathit{Par_{Lin}}$ (\eq{lin}):
the weight of each feature is determined on the basis of probability
theory.  However, the optimization of $\alpha$ is difficult because
the optimal value varies with the task and even the data size.

\subsubsection{Translation-based conditional probability}

\newcite{bannard:05} proposed a probabilistic model for acquiring
paraphrases of word sequences.  The likelihood of a word sequence $t$
as a paraphrase of the given word sequence $s$ is calculated by the
following formula:
\[
 P(t|s) = \sum_{f\in \mathit{tr}(s)\cap
  \mathit{tr}(t)} P(t|f)P(f|s),
\]
where $\mathit{tr}(e)$ stands for a set of word sequences in foreign
language that are aligned with $e$ in a given bilingual corpus.
Parameters $P(t|f)$ and $P(f|s)$ are estimated using the given
bilingual corpus.
A large-scale bilingual corpus may enable us to acquire a large amount
of paraphrase knowledge accurately.  However, it is not feasible to
build (or obtain) a bilingual corpus in which all the instances of
phrasal variants in one language are translated to at least one same
expression in the other side of language.

\subsection{Post-process for automatic paraphrase generation}
\label{ssec:generation}

When paraphrase knowledge, i.e., a pair of expression, is generated
from general transformation patterns by filling their variables with
specific words, the grammaticality of the expressions should be
assessed in addition to computing their semantic equivalence and
substitutability.  To the best of our knowledge, no work has taken all
of these criteria into account.  However, apart from our goal, i.e.,
automatic generation of paraphrase knowledge, there have been several
studies on measuring the appropriateness of applying paraphrase
knowledge in a specific context: how correct a sentence that is
partially/entirely paraphrased is.

\newcite{fujita:04:b} pointed out that case assignments of verbs tend
to be incorrect in paraphrasing Japanese sentences irrespective of the
class of paraphrases and applied a language model to the assessment of
case assignments as a post-process for paraphrase generation.  Their
model, however, cannot evaluate the semantic equivalence of the
resultant pairs of expressions.
\newcite{quirk:04} built a paraphrase generation model from a
monolingual comparable corpus on the basis of a statistical machine
translation framework, where the language model was used to quantify
the grammaticality of the translations, i.e., generated expressions.
The translation model, however, is not suitable for generating phrasal
variants, because it learns word/phrase alignments at the surface
level.  To cover all phrasal variants, we require a non-real
comparable corpus in which all instances of phrasal variants have a
chance of being aligned.  Furthermore, because the translation model
optimizes the word/phrase alignment at the sentence level, the
substitutability of the aligned pairs of word/phrase sequences cannot
be explicitly guaranteed.




\section{A probabilistic model for measuring appropriateness}
\label{sec:proposed}

\subsection{Formulation with conditional probability}
\label{ssec:framework}

As described in \sec{intro}, we regard sub-parses governed by
predicates as predicate phrases.
Our goal is to establish a measure that computes the appropriateness
of a given pair of automatically generated predicate phrases as
paraphrases on the basis of the following three criteria.
\begin{description}
\item[Criterion 1.] Both expressions are semantically equivalent
\item[Criterion 2.] Both expressions are substitutable in some
  contexts
\item[Criterion 3.] Both expressions are grammatical
\end{description}

Let $s$ and $t$ be the source (original) and target (paraphrased)
predicate phrase, respectively.  We introduce the following two
assumptions.
\begin{description}
\item[Assumption 1. $s$ is given and grammatical:] As a way of
  generating all the instances of phrasal variants from the given
  transformation pattern, it is reasonable to instantiate one side of
  the pattern with existing predicate phrases to generate the other
  side.  We adopt this approach, assuming that the existing predicate
  phrases are grammatical.
\item[Assumption 2. $s$ and $t$ do not co-occur:]  Provided that $s$
  and $t$ are paraphrases, they are members of a set of paradigmatic
  expressions, so do not co-occur.
\end{description}

On the basis of Assumption 1, the appropriateness of the given pair of
expressions as paraphrases is formulated with conditional probability
$P(t|s)$, as in \cite{bannard:05}.
It is then transformed as follows on the basis of Assumption 2:
\begin{equation}
\begin{aligned}[b]
 P(t|s) &= \sum_{f\in F}P(t|f)P(f|s) \\
 	&= \sum_{f\in F}\frac{P(f|t)P(t)}{P(f)}P(f|s) \\
	&= P(t)\sum_{f\in F}\frac{P(f|t)P(f|s)}{P(f)},
\end{aligned}
\label{eq:overall}
\end{equation}
where $F$ denotes a set of features.
The first factor $P(t)$ is the \emph{grammaticality factor}, which
quantifies the degree to which the third criterion is satisfied.  Note
that we assume that the given $s$ is grammatical.
The second factor $\sum_{f\in F}\frac{P(f|t)P(f|s)}{P(f)}$, on the
other hand, is the \emph{similarity factor}, which approximates the
degree to which the first and second criteria are satisfied by summing
up the overlap of the features of $s$ and $t$.
The characteristics and advantages of this probabilistic model are
summarized as follows.
\begin{itemize}
\item The model is asymmetric\footnote{Note that our formulation does
  not take inclusion of features into account:
  cf.~\cite{YamamotoKazuhide:02:d,geffet:05,bhagat:07}.}.
\item Grammaticality is explicitly assessed by $P(t)$.
\item There is no need to enumerate all the phrases.  $s$ and $t$ are
  merely the given conditions.
\item No heuristic is introduced.  The weight of the features can be
  determined by conditional probabilities $P(f|t)$ and $P(f|s)$ and
  marginal probability $P(f)$.
\end{itemize}
The rest of this section explains our implementation of each factor in
turn, taking Japanese as the target language.

\subsection{Grammaticality factor}
\label{ssec:grammaticality}

The factor $P(t)$ of \eq{overall} quantifies how a predicate phrase
$t$ is grammatical using a statistical language model.
Unlike English, in Japanese, predicates such as verbs and adjectives
do not necessarily determine the order of their complements and
adjuncts, although they have some preferences.  For example, both
sentences in \refex{order} are grammatical.
\numexs{order}{
\item \begin{jexample}
\chunk{彼-は}{he-\textsc{top}}
\chunk{\textbf{グラス-を}}{glass-\textsc{acc}}
\chunk{\textbf{いつも}}{always}
\chunk{\textbf{左手-で}}{left hand-with}
\chunk{持つ.}{to take-\textsc{punc}}
\gloss{He always holds glasses with his left hand.}
\end{jexample}
\item \begin{jexample}
\chunk{彼-は}{he-\textsc{top}}
\chunk{\textbf{いつも}}{always}
\chunk{\textbf{左手-で}}{left hand-with}
\chunk{\textbf{グラス-を}}{glass-\textsc{acc}}
\chunk{持つ.}{to take-\textsc{punc}}
\gloss{He always holds glasses with his left hand.}
\end{jexample}}
This motivates us to use structured $N$-gram language models
\cite{habash:04:a} for quantifying the grammaticality of predicate
phrase.
Given a predicate phrase $t$, its grammaticality $P(t)$ is estimated
on the basis of its dependency structure $T(t)$, assuming a
$(N-\text{1})$-th order Markov process for generating $T(t)$:
\[
  P(t) = \Biggl[\prod_{i=1\ldots |T(t)|}
	  P_{d}\bigl(c_{i}|d_{i}^{1},d_{i}^{2},\ldots,d_{i}^{N-1}\bigr)
  \Biggr]^{1/|T(t)|},
\]
where $|T(t)|$ stands for the number of nodes in $T(t)$.  $d_{i}^{j}$
denotes the direct ancestor node of the $i$-th node $c_{i}$, where $j$
is the distance from $c_{i}$; for example, $d_{i}^{1}$ and $d_{i}^{2}$
are the parent and grandparent nodes of $c_{i}$, respectively.
The normalization factor $1/|T(t)|$ is introduced for canceling out
the length bias of the given phrase.

Then, a concrete definition of dependency structure is given.
Widely-used Japanese dependency parsers consider a morpheme sequence
consisting of at least one content morpheme followed by a sequence of
function morphemes, if any, as a node called a ``\textit{bunsetsu}.''
\pagebreak
The chunks of \mbox{sentences} in \refex{order} and \refex{sample} exemplify
these nodes.
\numexs{sample}{
\item[] \begin{jexample}
\chunk{きっと}{surely}
\chunk{彼-は}{he-\textsc{top}}
\chunk{今日-の}{today-\textsc{gen}}
\chunk{監督-会議-に-は}{coach-meeting-\textsc{dat}-\textsc{top}}
\chunk{来-ない-だろ-う-.}{to come-\textsc{neg}-must-\textsc{par}-\textsc{punc}}
\gloss{He will surely not come to today's coach meeting.}
\end{jexample}}

\begin{figure}[t]
\begin{minipage}[t]{192pt}
\begin{center}
\includegraphics{17-1ia10f1.eps}
\end{center}
\caption{MDS of the sentence in \refex{sample}.}
\label{fig:mds}
\end{minipage}
\hfill
\begin{minipage}[t]{212pt}
\begin{center}
\includegraphics{17-1ia10f2.eps}
\end{center}
\caption{PWDS of the sentence in \refex{sample}.}
\label{fig:pwds}
\end{minipage}
\end{figure}

As a \textit{bunsetsu} can be quite long, involving many morphemes, to
regard it as a node will make the model complex.  We therefore use the
following two versions of dependency structures whose nodes are
smaller than a \textit{bunsetsu}.
\begin{description}
\item[MDS:] Morpheme-based dependency structure \cite{takahashi:01:c}
  regards a morpheme as a node. The MDS of the sentence in
  \refex{sample} is shown in \fig{mds}.
\item[PWDS:] MDS cannot assess the collocation between content
  morphemes when a number of function morphemes appear between them.
  Pseudo-word-based dependency structure (PWDS) with $N\ge\text{3}$ can
  do it by regarding the sequence of function morphemes as a single
  node, in addition to MDS, as exemplified in \fig{pwds}.
\end{description}
For both of the above models, dependencies between nodes are
determined on the basis of the \textit{bunsetsu} dependencies obtained
by using a morphological analyzer and dependency parser.
\begin{itemize}
\item The rightmost node of \textit{bunsetsu}$_{i}$ depends on the
  syntactic head of \textit{bunsetsu}$_{j}$ on which
  \textit{bunsetsu}$_{i}$ depends; for example, \ja{の (\textsc{gen})}
  depends on \ja{会議 (meeting)} in both Figures \ref{fig:mds} and
  \ref{fig:pwds}.  The rightmost node of the final \textit{bunsetsu}
  depends on a special node ``\bracket{ROS} (root-of-sentence).''
\item Other nodes depend on succeeding nodes of the \textit{bunsetsu}.
\end{itemize}

A conventional way of dealing with a node that has never appeared in
the given corpus is to use the linear interpolation of the lower
degrees of models.
For example, the 3-gram conditional probability
$P_{d}(c_{i}|d_{i}^{1},d_{i}^{2})$ is given by the following equation:
\begin{align*}
 P_{d}(c_{i}|d_{i}^{1},d_{i}^{2}) 
   & = \lambda_{3}\prob(c_{i}|d_{i}^{1},d_{i}^{2})
	+\lambda_{2}\prob(c_{i}|d_{i}^{1})
	+\lambda_{1}\prob(c_{i}),
	\\
 \text{s.t.}\quad \sum_{j}\lambda_{j} 
   &= 1,
\end{align*}
where $\prob$ stands for the empirical probability distribution
determined by maximum likelihood estimation.  The optimal mixture
weights $\lambda_{j}$ are determined via an EM algorithm using
development data that are not used for estimating $\prob$.

\subsection{Similarity factor}
\label{ssec:similarity}

The similarity factor of \eq{overall} computes how similar two phrases
$s$ and $t$ are by comparing two sets of contextual features $F_{s}$
of $s$ and $F_{t}$ of $t$.
On the basis of the findings in the previous work (see
\ssec{existing}), we use the following two types of feature sets, each
of which is composed of expressions that co-occur with the given
phrase $p$ in the given corpus.  Let $f$ be a feature consisting of a
tuple $\mathbrace{r,e}$ of such an expression $e$ and a relation $r$
between $p$ and $e$.
\begin{description}
\item[BOW:] A pair of phrases is likely to be semantically equivalent
  if the distributions of the words surrounding the phrases are
  similar.  The relation
  ``\texttt{co-occur\_in\_the\_same\_sentence}'' is considered as the
  only element of the relation set $R_{\mathit{BOW}}$.
\item[MOD:] A pair of phrases is likely to be substitutable with each
  other, provided they share a number of instances of modifiers and
  modifiees.  The set of the relation $R_{\mathit{MOD}}$ has two
  elements: ``\texttt{modifier}'' and ``\texttt{modifiee}.''
\end{description}

As reviewed in \ssec{acquisition}, subject/object slot fillers of verb
phrases (single verbs in most cases) in English have been used as
contextual features to acquire paraphrase templates, i.e., pairs of
templates such as those shown in \refex{symmetric} and
\refex{asymmetric}, where the grammaticality of their lexicalized
parts have been assumed.
What is actually quantified is, however, not the similarity between
the whole templates, but that between their lexicalized parts and
correspondences of slots.  Thus, the pair of templates cannot
necessarily be used as paraphrases in the given specific context (slot
fillers), as empirically confirmed in their following work
\cite{pantel:07,szpektor:08:a}.
In contrast, the MOD features capture more unrestricted
characteristics of each phrase, which enables us to compute the
similarity between phrases of arbitrary sizes.

\subsubsection{Web snippet retrieval}

In general, phrases appear less frequently than single words.  This
raises a crucial problem in computing the similarity between phrases,
i.e., the sparseness of contextual features.
One possible way to overcome the problem is to take back-off
statistics assuming the independence between constituent words
\cite{torisawa:06,pantel:07}.  This approach, however, has a risk of
involving noise due to the ambiguity of those words.

We take another approach that uses the Web as a corpus instead of a
corpus of limited size.  Given a phrase $p$, the snippets of Web pages
(henceforth, Web snippets) containing $p$ are retrieved via Yahoo! Web
    search API\footnote{http://developer.yahoo.co.jp/search/,
  version 1.0.  The API provides up to 1,000 Web snippets for a
  query.} by issuing quoted $p$ as a query.
The resultant Web snippets can be considered as a dense example
collection of contextual information for $p$.

\subsubsection{Feature extraction}

Both BOW and MOD features of the given phrase are extracted from the
sentences within the Web snippets.
To collect BOW features, first, the content morphemes, i.e., nouns,
verbs, adjectives, and adverbs, in the sentences that include the
phrase are extracted using morphological analyzer
    ChaSen\footnote{http://chasen.naist.jp/hiki/ChaSen/, version
  2.3.3 with IPADIC version 2.7.0.\\We first used MeCab
      (http://mecab.sourceforge.net/, version 0.96).  However, it
  excessively labels out-of-vocabulary morphemes including symbol
  sequences as ``deverbal nouns,'' which is wrong in most cases, and
  thus makes the features noisy.}.
Each feature is then composed of the base form of such a content
morpheme and its part-of-speech.  Note that we exclude morphemes that
are labeled as proper nouns, such as person names and location names,
because we expect that they will unworthily decrease the possibility
of overlap due to their much greater variation than common words.

On the other hand, to collect MOD features, we carried out structural
matching between the given phrase and the sentences within the Web
snippets, where the \textit{bunsetsu}-based dependency structure is
determined using ChaSen and
    CaboCha\footnote{http://chasen.org/\~{}taku/software/cabocha/,
  version 0.53.}.
\fig{extract_mod} depicts an example of extracting the MOD features
from a sentence that includes the given phrase.  As shown in the
figure, each feature is composed of the following four elements
extracted from a \textit{bunsetsu} that is either a modifier or a
modifiee of the given phrase.
\begin{itemize}
\item Modifier or modifiee
\item Relation type (Depending, Appositive, or Parallel)
\item Base form of the syntactic head
\item Several types of function morphemes, if any
\end{itemize}
Function morphemes are incorporated to capture the subtle difference
between the meanings of predicate phrases, such as voice, aspect, and
modality.  At present, we take into account only case markers
(including genitive \ja{の}) that immediately follow nouns, and
auxiliary verbs and verbal suffixes that do so for verbs and
adjectives.

\begin{figure}[t]
\begin{center}
\includegraphics{17-1ia10f3.eps}
\end{center}
\caption{An example of MOD feature extraction.}
\label{fig:extract_mod}
\end{figure}

\subsubsection{Parameter estimation}
\label{sssec:parameter}

Finally, conditional probability distributions $P(f|s)$ and $P(f|t)$
are estimated.  Given a phrase $p$, the conditional probability
distribution $P(f|p)$ is determined by maximum likelihood estimation
as follows, superficially assuming the mutual exclusiveness of
features:
\begin{align*}
 P(f|p) & = P(\mathbrace{r,e}|p)\\
	& = \frac{\mathit{freq_{sni}}(p,r,e)}
	{\sum_{r'\in R}\sum_{e'}\mathit{freq_{sni}}(p,r',e')},
\end{align*}
where $\mathit{freq_{sni}}(p,r,e)$ stands for the frequency of an
expression $e$ that appeared with the phrase $p$ in relation $r$
within the Web snippets retrieved by querying $p$.

On the other hand, the weight for features $P(f)$ can be estimated on
the basis of the following equation using a static corpus in an
offline manner:
\begin{align*}
  P(f) & = P(\mathbrace{r,e}) \\
	& = \frac{\sum_{p}\mathit{freq_{cp}}(p,r,e)}{\sum_{p}\sum_{r'\in
	    R}\sum_{e'}\mathit{freq_{cp}}(p,r',e')},
\end{align*}
where $\mathit{freq_{cp}}(p,r,e)$ denotes the frequency of an
expression $e$ that appeared with some expression $p$ in relation $r$
within the given corpus.  Features are again considered to be mutually
exclusive.




\section{Experimental settings}
\label{sec:setting}

We have conducted an experiment to assess the performance of the
existing measures and the probabilistic models on the task of
measuring the appropriateness of automatically generated candidates of
phrasal variants.
In this section, the settings of the experiment are described.

\subsection{Measures examined}
\label{ssec:measures}

The probabilistic model has several options.  In this experiment, we
have examined all combinations of the following four options: 48
versions in total.
\begin{description}
\item[Implementation of $P(t)$:] 3-gram language models based on MDS
  and PWDS were respectively built upon 15 years of Mainichi newspaper
  articles (1991--2005, 1.5~GB, 21~M sentences, henceforth, Mainichi)
  using morphological analyzer ChaSen and dependency parser CaboCha,
  with $N$ being varied from 1 to 3.  \tab{slm} shows the types of
  $N$-grams that each version of the statistical language model
  contains.  Yomiuri newspaper articles 2005 (350~MB, 4.7~M sentences)
  and Asahi news paper articles 2005 (180~MB, 2.7~M sentences) were used
  for optimizing the mixture weights of interpolating the lower
  degrees of models.

\begin{table}[t]
\caption{Types of $N$-grams observed in the corpus.}
\label{tab:slm}
\input{10table01.txt}
\end{table}

\item[The number of the Web snippets ($N_{S}$):] 100, 200, 500, and
  1,000.

\item[Contextual feature set:] BOW, MOD, and their combination, HAR,
  were examined, because they are supposed to be complementary (see
  \ssec{similarity}).  However, they cannot be merged directly,
  because they are not necessarily disjoint and the frequency of each
  feature is used in the probabilistic framework.  We therefore
  adopted the harmonic mean of the scores respectively derived using
  BOW and MOD, dealing with both scores equally.

\item[Corpus used for estimating $P(f)$:] Two different corpora were
  exclusively used to build two variations of $P(f)$.  One was
  Mainichi, which was also used for building structured $N$-gram
  language models.  The other was a much larger corpus consisting of
  470~M sentences collected from Web pages \cite{kawahara:06:b}.  We
  refer to the resultant parameter sets based on those corpora as
  NewsCP and WebCP, respectively.  The statistics in \tab{feature}
  show a larger variation of MOD than BOW.  WebCP is expected to have
  higher coverage and a smoother probability distribution, although
  the Web corpus may contain a lot of ungrammatical expressions, and a
  morphological analyzer and dependency parser would output some
  improper instances of features.

\end{description}

\begin{table}[t]
\caption{Types of features observed in the corpora.}
\label{tab:feature}
\input{10table02.txt}
\end{table}

In addition to the probabilistic models, we have examined several
conceivable measures.
\begin{description}
\item[Count-based measures:] A phrase should appear in a reasonably
  large corpus if it is grammatical.  Count-based measures assume that
  the more frequently a phrase appears, the more likely it is to be
  grammatical.  The following two implementations have been evaluated.
\end{description}
\begin{itemize}
\item \textbf{HITS-News}: The number of occurrences of $t$ in Mainichi
  is regarded as the score.
\item \textbf{HITS-Web}: The number of Web pages that contain $t$ is
  regarded as the score.  The estimated value can be retrieved via
  Yahoo! Web search API.
\end{itemize}
\begin{description}
\item[Distributional similarity measures:] Two versions of
  distributional similarity measures have also been examined.  The
  score, which falls within $[0,1]$, is computed using BOW, MOD, and
  HAR extracted from Web snippets.  We assume that the larger the
  value is, the more likely the pair of phrases is to be paraphrases.
\end{description}
\begin{itemize}
\item $\mathit{Par_{Lin}}$ (\eq{lin}): Unlike \newcite{lin:01}, which
  utilized a static corpus to determine feature weights, we directly
  used the frequency of each feature within the Web snippets retrieved
  by querying each phrase.
\item $\mathit{Par_{skew}}$ (\eq{skew}): The conditional probabilities
  $P(f|s)$ and $P(f|t)$ of the probabilistic model were used as the
  probability distributions $P_{s}$ and $P_{t}$.  As the value of the
  parameter $\alpha$, we examined 0.99 only, as an approximation of KL
  divergence \cite{lee:99:a}.
\end{itemize}

\subsection{Test collection}
\label{ssec:collection}

First, existing predicate phrases were collected from
Mainichi\footnote{The corpus was also used to build language models
  $P(t)$ and one version of $P(f)$.  However, we think it still
  enables us to conduct a fair experiment, because those models do not
  directly evaluate the source phrase $s$.}.
Referring to the dependency structures derived by ChaSen and CaboCha,
we extracted approximately 1,000 types of the most frequent phrases
for each of the following six phrase types.
\begin{multicols}{2}
\numexs{phrases}{
\item \textbf{$N$:$C$:$V$ type phrase}\par
\begin{jexample}
\chunk{確認-を}{checking-\textsc{acc}}
\chunk{急ぐ}{to hurry}
\gloss{to hurry checking (something)}
\end{jexample}
\item \textbf{$N_{1}$:$N_{2}$:$C$:$V$ type phrase}\par
\begin{jexample}
\chunk{損害-賠償-を}{damage-compensation-\textsc{acc}}
\chunk{求める}{to require}
\gloss{to demand compensation for damages}
\end{jexample}
\item \textbf{$N$:$C$:$V_{1}$:$V_{2}$ type phrase}\par
\begin{jexample}
\chunk{統計-を}{statistics-\textsc{acc}}
\chunk{取り-始める}{to take-to start}
\gloss{to start taking the statistics}
\end{jexample}
\item \textbf{$N$:$C$:$Adv$:$V$ type phrase}\par
\begin{jexample}
\chunk{検討-を}{consideration-\textsc{acc}}
\chunk{さらに}{further}
\chunk{進める}{to advance}
\gloss{to make a further consideration}
\end{jexample}
\item \textbf{$Adj$:$N$:$C$:$V$ type phrase}\par
\begin{jexample}
\chunk{早い}{rapid}
\chunk{復興-を}{recovery-\textsc{acc}}
\chunk{祈る}{to wish}
\gloss{to wish the rapid recovery}
\end{jexample}
\item \textbf{$N$:$C$:$Adj$ type phrase}\par
\begin{jexample}
\chunk{のど-が}{throat-\textsc{nom}}
\chunk{痛い}{be painful}
\gloss{to have a sore throat}
\end{jexample}
}
\end{multicols}

Assuming that these predicate phrases are grammatical, we then fed
them to a paraphrase generation system proposed in \cite{fujita:07:a}.
Given an input phrase, the system over-generates candidates of its
phrasal variants using a catalog of handcrafted syntactic
transformation patterns and dictionaries tailored for handling lexical
derivations.
Henceforth, we refer to those automatically generated candidates as
``{\pc}s'' and pairs of a source phrase, $s$, and one of its {\pc}s,
$t$, as ``{\pcp}s.''

\begin{table}[t]
\caption{Sampled source phrases $s$ and their {\pcp}s $\mathbrace{s,t}$.}
\label{tab:generated}
\input{10table03.txt}
\end{table}

\tab{generated} summarizes the statistics of our test collection,
where the ``Sampled/$s$'' column denotes the numbers of phrase types
sampled as the source, while the ``Generated/$s$'' and
``Generated/$\mathbrace{s,t}$'' columns present those of the
paraphrased source phrases and {\pcp}s, respectively.
At least one {\pc} was generated for 65\% (4,002/6,190) of the input
source phrases, although the ratio and the numbers of {\pc}s per
paraphrased source phrase (``Generated/Yld.'' column) were remarkably
different depending on the phrase type.
The system generated numerous {\pc}s (the maximum was 186); however,
most of them were not appropriate.  For example, among 159 {\pc}s for
the phrase in \refexs{phrases}{b}, only 8 phrases were grammatical,
and only 5 out of 8 were appropriate paraphrases.

Finally, the appropriateness of each {\pcp} as a paraphrase is
computed by each measure described in \ssec{measures}.
As those pairs include many inappropriate ones, the task can also be
illustrated as filtering them out and ranking the remaining pairs.
\tab{computed} shows the numbers of {\pcp}s whose appropriateness can
be computed\footnote{The Web snippets were retrieved from September 14
  to 17, 2008.}.  The numbers were diverse depending on the features
being referred to.
Approximately 90\% of the {\pcp}s were discarded because either $s$ or
$t$ did not appear at all.  On the other hand, at least one candidate
survived for 84\% (3,356/4,002) of the paraphrased source phrases and
54\% (3,356/6,190) of the input source phrases.
With the Web, we could compute the appropriateness score at a
significantly higher rate (267\%; 16,225/6,086) than with the limited
size of a well-controlled corpus, i.e., Mainichi, sacrificing only 352
pairs whose scores were computed only by HITS-News.

\begin{table}[t]
\caption{{\Pcp}s $\mathbrace{s,t}$ whose appropriateness was
  computed.}
\label{tab:computed}
\input{10table04.txt}
\end{table}

\tab{pfp} summarizes the statistics of the extracted BOW and MOD
features, revealing that fewer MOD features are obtainable than BOW
features.
The rightmost two columns in the table show the numbers of phrase
types among the union of sets of $s$ and $t$ (``Phrase'' column) and
{\pcp}s (``$\mathbrace{s,t}$'' column) for which we could retrieve at
least $N_{s}$ Web snippets.
We could retrieve 100 Web snippets for only 6,029 {\pcp}s and 1,000
Web snippets for 3,708 pairs within our test collection,
respectively.

\begin{table}[t]
\caption{Retrieved contextual features of phrases.}
\label{tab:pfp}
\input{10table05.txt}
\vspace{-1\baselineskip}
\end{table}


\subsection{Criteria for human judgment}
\label{ssec:judge}

The appropriateness of a pair of expressions as paraphrases can only
be judged by humans. We therefore asked assessors to answer the
following four questions, which reflect the criteria described in
\sec{intro}.
\begin{description}
\item[Q$_{\textrm{sc}}$:] Is $s$ an acceptable Japanese phrase?
\item[Q$_{\textrm{tc}}$:] Is $t$ an acceptable Japanese phrase?
\item[Q$_{\textrm{s2t}}$:] Does $t$ always hold if $s$ holds and can
  $t$ be substituted for $s$ in some contexts?
\item[Q$_{\textrm{t2s}}$:] Does $s$ always hold if $t$ holds and can
  $s$ be substituted for $t$ in some contexts?
\end{description}
To reduce the amount of labor, a assessor does not answer the latter
two questions if he/she answers either of the former questions ``No.''
The following examples are sampled from pairs on which the three
assessors in our experiment agreed for all of the above four
questions.
\numexs{judge}{
\item[] \hspace*{-2\labelsep}\hspace*{-.66zw}
\begin{tabular}[t]{rlll}
a.
&$s$. \begin{jexample}
\chunk{{\badex}基準-を}{criterion-\textsc{acc}}
\chunk{厳しい}{be severe}
\gloss{{\badex}(not translatable)}
\end{jexample}
&$t$. \begin{jexample}
\chunk{厳しい}{be severe}
\chunk{基準-だ}{criterion-\textsc{cop}}
\gloss{be a severe criterion}
\end{jexample}
&(No, Yes, -, -)\\

b.
&$s$. \begin{jexample}
\chunk{幅-が}{width-\textsc{nom}}
\chunk{広い}{be wide}
\gloss{the width is wide}
\end{jexample}
&$t$. \begin{jexample}
\chunk{{\badex}幅-が}{width-\textsc{nom}}
\chunk{広げる}{to widen}
\gloss{{\badex}the width widens}
\end{jexample}
&(Yes, No, -, -)\\

c.
&$s$. \begin{jexample}
\chunk{映画-を}{movie-\textsc{acc}}
\chunk{見-終わる}{to see-to finish}
\gloss{to finish seeing the movie}
\end{jexample}
&$t$. \begin{jexample}
\chunk{映画-が}{movie-\textsc{nom}}
\chunk{終わる}{to end}
\gloss{the movie ends}
\end{jexample}
&(Yes, Yes, Yes, No)\\

d.
&$s$. \begin{jexample}
\chunk{承認-を}{approval}
\chunk{得る}{to gain}
\gloss{to clear}
\end{jexample}
&$t$. \begin{jexample}
\chunk{承認-さ-れる}{to approve-\textsc{pass}}
\gloss{to be approved}
\end{jexample}
&(Yes, Yes, Yes, Yes)\\
\end{tabular}
}

Incidentally, while some previous studies have attempted to collect
knowledge even for plausible inferences, such as shown in
\refex{plausible}, our criteria regard them as inappropriate.
\numexs{plausible}{
\item $X$ marries $Y$ {\Ra} $X$ dates $Y$ (One may marry without
  dating)\hfill\cite{pantel:07}
\item $X$ eats $Y$ {\Ra} $X$ likes $Y$ (One may eat what he/she
  dislike)\hfill\cite{bhagat:07}}




\section{Input-wise evaluation}
\label{sec:eval-gen}

{\Pc}s for a given predicate phrase are ranked by each measure.  This
section describes how accurately each measure can rank an appropriate
candidate first for each source phrase.
To perform this evaluation, we randomly sampled 200 source phrases and
extracted all of their {\pc}s.  \tab{sample-generated} shows the
statistics of sampled data, where the ``Sampled/Yld.'' column denotes
that there is still a considerable diversity with regard to the
numbers of {\pc}s per source phrase.

\begin{table}[t]
\caption{{\Pcp}s $\mathbrace{s,t}$ for the 200 sampled source phrases.}
\label{tab:sample-generated}
\input{10table06.txt}
\end{table}

The rest of this section is devoted to answering the following
questions.
\begin{description}
\item[Q$_{1}$:] Which measure performs the task best in practice?
\item[Q$_{2}$:] Which contextual features are superior to the others?
\end{description}
\begin{itemize}
\item Which feature set performs the task better?
\item What happens when a larger number of Web snippets are used?
\end{itemize}
\begin{description}
\item[Q$_{3}$:] What the options of the probabilistic model lead to?
\end{description}
\begin{itemize}
\item Which language model is superior to the others?
\item Which corpus for estimating $P(f)$ results in better
  performance?
\end{itemize}

\subsection{Sampling and judgment}
\label{ssec:gen-sampling}

For each measure, 
\pagebreak
the top-ranked {\pcp} for each of 200 source phrases
was first selected.  Although we had 14,756 pairs for 74 measures in
total\footnote{HITS-News did not select any {\pc}s for 44 source
  phrases, because none of their {\pc}s appeared in the corpus (see
  \tab{sample-generated}).}, the union of resultant sets consisted of
only 469 {\pcp}s.
Then, three human assessors separately judged each {\pcp} by answering
the four questions shown in \ssec{judge}.

The inter-assessor agreement of each pair of assessors is summarized
in \tab{gen-judge}, where the ``Agr.'' column denotes the number of
{\pcp}s for which two assessors agreed on all of the four questions.
On the other hand, Kappa values were calculated on the basis of
{\pcp}s that passed both Q$_{\textrm{sc}}$ and Q$_{\textrm{tc}}$.
As shown in the table, the assessors agreed on all of the four
questions for 63 to 68\% of {\pcp}s.  We also obtained substantial
$\kappa$-values: 0.68 to 0.75 and 0.62 to 0.68 for judging
Q$_{\textrm{s2t}}$ and Q$_{\textrm{t2s}}$, respectively.


As the appropriateness of a {\pcp} is estimated with the assumption
that the source phrase $s$ is given, the rest of this section does not
refer to the answers for Q$_{\textrm{t2s}}$.

\begin{table}[t]
\caption{Agreement of human judgment ($n=\text{469}$).}
\label{tab:gen-judge}
\input{10table07.txt}
\end{table}
\begin{table}[t]
\caption{Appropriate paraphrases among the top-ranked candidates:
  summary.}
\label{tab:gen-overview}
\input{10table08.txt}
\end{table}


\subsection{Overview of the results}
\label{ssec:ev-gen-overview}

Although we have evaluated all 74 measures, we show the results of
selected combinations of parameters in \tab{gen-overview} as a brief
summary of the performance.
``$\sig\sig$'' and ``$\sig$'' in \tab{gen-overview} denote the
significance levels $p<\text{0.01}$ and $p<\text{0.05}$ of McNemar's
test between the best measure and each measure, respectively.
HITS-Web selected the grammatical {\pc} best, while
$\mathit{Par_{skew}}$ with $N_{S}=\text{1,000}$ and HAR performed the
best for the entire task.

As {\pc}s were generated from a given source phrase using a set of
handcrafted transformation patterns, their constituent words were
similar to those of their source phrase to some degree.  Thus, the
results of the count-based measures were tolerably high, considering
that they ranked {\pc}s without referring to their source phrases.
HITS-Web had a better coverage than HITS-News as a result of
harnessing the Web as a corpus.

$\mathit{Par_{Lin}}$ and $\mathit{Par_{skew}}$ do not explicitly
evaluate the grammaticality but only compare the feature sets of two
phrases; nevertheless, contrary to our expectation, they performed the
best among all the measures.
As a result of taking into account the similarity of contextual
features in addition to that of constituent words, these measures
performed significantly better than the count-based measures.
Distributional similarity measures were also superior to the
probabilistic model for assessing the grammaticality of {\pc}s.  This
implies that the grammaticality of a {\pc} could be assessed as a side
effect of querying the Web to extract its contextual features.  We
expect that this technique will work well as long as we deal with
relatively short phrases.

The aim in introducing the probabilistic model is to explicitly assess
the grammaticality and to combine it with the similarity measurement.
No combination of parameters, however, outperformed the existing
measures, $\mathit{Par_{Lin}}$ and $\mathit{Par_{skew}}$, which only
assessed similarity, nor even one of the count-based measures,
HITS-Web.
Furthermore, the accuracies of all versions of the probabilistic model
were significantly worse than that of the best measure.

\begin{figure}[t]
\begin{minipage}[t]{204pt}
\begin{center}
\includegraphics{17-1ia10f4.eps}
\end{center}
\caption{Comparison of measures (2 judges).}
\label{fig:har.2ok}
\end{minipage}
\hfill
\begin{minipage}[t]{203pt}
\begin{center}
\includegraphics{17-1ia10f5.eps}
\end{center}
\caption{Comparison of measures (3 judges).}
\label{fig:har.3ok}
\end{minipage}
\end{figure}

Figures \ref{fig:har.2ok} and \ref{fig:har.3ok} give a closer look at
the correlation between the score and accuracy.  The horizontal and
vertical axes denote the number of {\pcp}s with the highest scores
among 200 samples and the cumulative accuracy of those pairs,
respectively.
These graphs imply that if a top-ranked {\pc} for a given phrase is
assigned a high enough score, it is more likely to be appropriate.
However, some inappropriate {\pcp}s can accidentally have high scores.
Typical errors will be exemplified in \sec{errors}.

\subsection{Investigation into contextual features}
\label{ssec:ev-gen-common}

Before a detailed evaluation of the probabilistic model, we
investigate the use of contextual features retrieved from the Web
snippets.  \tab{gen-baseline} summarizes the results of distributional
similarity measures, where ``$\sig\sig$'' and ``$\sig$'' denote the
significance levels of McNemar's test on the performance compared to
that of the best measure, i.e., $\mathit{Par_{skew}}$ with
$N_{S}=\text{1,000}$ and HAR.

\begin{table}[t]
\caption{Appropriate paraphrases among the top-ranked candidates:
  distributional similarity measures.}
\label{tab:gen-baseline}
\input{10table09.txt}
\end{table}


\subsubsection{The type of contextual features}

In \ssec{similarity}, we mentioned that BOW and MOD gauge the
similarity of phrases from different viewpoints: semantic equivalence
and substitutability.  Yet, we expect that MOD also contributes to
quantifying the semantic equivalence, and thus it is superior to BOW.
The combination of BOW and MOD into HAR is introduced to further
enhance the performance.

The underlined numbers in \tab{gen-baseline} indicate {\compfeat}.
These results confirmed that MOD and HAR were superior to BOW for
$\mathit{Par_{Lin}}$ and $\mathit{Par_{skew}}$.  However, the impact
of introducing HAR seems small.  Nevertheless, we consider that HAR
must be practically important in terms of robustness, because MOD
features are relatively sparser than BOW features as we discussed
referring to \tab{pfp}.  This will be discussed in more detail in
\sssec{eval-sim}.

\subsubsection{The number of Web snippets}

We observed that a larger number of Web snippets led to better
results.  The extent of the improvement, however, became smaller when
more than 200 Web snippets were used.  This is because general
predicate phrases were in fact less frequent, and thus we can retrieve
only a small number of Web snippets and sparse contextual features for
each phrase.

As it is time-consuming to obtain a large number of Web snippets, the
trade-off between the number of Web snippets and the performance
should be investigated further.  However, as \newcite{kilgarriff:07}
has pointed out, the quality of Web snippets and what appears at the
top of search results that commercial search engines return will vary
according to several factors other than linguistic ones\footnote{We
  found that the rankings of {\pc}s changed slightly depending on when
  the Web snippets were retrieved.}.
To examine the proposed features and measures further in an unbiased
situation,
    TSUBAKI\footnote{http://tsubaki.ixnlp.nii.ac.jp/se/index.cgi}, a
search engine developed for NLP research, may be useful, because it
statically archives a huge number of Web pages written in Japanese,
and allows us to obtain all the Web pages in the archive that
correspond to the query.

\subsection{Characteristics of the probabilistic model}
\label{ssec:ev-gen-prob}

\tab{gen-prob} summarizes the experimental results of all versions of
the probabilistic model.
The underlined numbers in the table again indicate {\compfeat}.
The marks ``$\circ$'' and ``$\bullet$'' indicate the winners of
comparisons of each pair of measures that share all the parameters
except the model of $P(t)$ and the corpus for $P(f)$, respectively.
As described in \ssec{ev-gen-overview}, no combination of parameters
could achieve comparable performance to the existing measures
(cf.~\tab{gen-baseline}).  To clarify the reason, we analyze the
characteristics of the probabilistic model by evaluating the utility
of each option and their combinations in turn.


\subsubsection{Grammaticality factor}
\label{sssec:eval-gram}

Contrary to our expectation, comparisons between MDS and PWDS revealed
that PWDS do not always produce better results than MDS: ``$\circ$''
is marked 30 times on PWDS and 16 times on MDS.
To find the reason, we examined how accurately each language model was
able to select grammatical phrases.
We first extracted the {\pc}s that were given the highest probability
$P(t)$ among candidates for each of 200 source phrases, and then we
asked the assessors to judge only their grammaticality,
Q$_{\text{tc}}$.
\tab{gen-grammaticality} shows the numbers of grammatical phrases
among those each measure selected.  From the results, we confirmed
that PWDS is superior to MDS.  However, we have not clarified why the
advantage of PWDS is diminished when two factors are combined.

\begin{table}[t]
\caption{Appropriate paraphrases among the top-ranked candidates:
  probabilistic model.}
\label{tab:gen-prob}
\input{10table10.txt}
\end{table}
\begin{table}[t]
\caption{Grammatical phrases among the top-ranked candidates.}
\label{tab:gen-grammaticality}
\input{10table11.txt}
\end{table}

Unfortunately, both MDS and PWDS were significantly worse than the
other measures ($p<\text{0.01}$).  The results confirm that querying a
phrase to the Web contributes to assessing the grammaticality of the
phrase.
This may suggest that it is not necessary to assess the grammaticality
explicitly.
Another avenue for future work is to examine a more sophisticated
language model to enhance the probabilistic model.
Although the order of sibling nodes in the dependency structure is
disassembled by MDS and PWDS, it reflects some preferences; for
example, it sounds strange to a native speaker if \ja{左手で (with the
  left hand)} precedes \ja{いつも(always)} in sentence in
\refex{order}.
In addition to the depth of dependencies and syntactic conditions
\cite{uchimoto:00}, discourse elements also exert a degree of
influence upon the decision, e.g., highlighting old and new
information.
Obtaining a suitable granularity of nodes is another issue.  One
conceivable way is to introduce latent classes, such as the
Semi-Markov class model \cite{okanohara:07:b} and the hierarchical
Pitman-Yor language model \cite{mochihashi:07:c}.
The existence of many orthographic variants of both content and
function morphemes may prevent us from accurately estimating their
grammaticality.  To normalize these variations, methods and resources,
such as \cite{ohtake:04,matsuyoshi:08:c-e}, must be incorporated.

\subsubsection{Similarity factor}
\label{sssec:eval-sim}

We also conducted a component analysis for the similarity factor.
\tab{gen-similarity} shows the numbers of {\pcp}s that were selected
only on the basis of the similarity factor score and judged correct
for all of the questions Q$_{\text{sc}}$, Q$_{\text{tc}}$, and
Q$_{\text{s2t}}$.

\begin{table}[t]
\caption{Appropriate paraphrases that were selected only on the basis
  of similarity factor.}
\label{tab:gen-similarity}
\input{10table12.txt}
\end{table}


Basically, MOD outperformed BOW, and HAR did so for both BOW and MOD
as $\mathit{Par_{Lin}}$ and $\mathit{Par_{skew}}$, although we
sometimes observed converse results (see underlines in
\tab{gen-prob}).
The superiority of MOD and HAR was also observed when the similarity
factor was used alone (see \tab{gen-similarity}).  The impact of
combining BOW and MOD into HAR was more significant than the entire
probabilistic model.  This supports the importance of HAR, implying,
in contrast, that the single use of BOW and MOD in this probabilistic
framework is not useful.

We could not find any notable tendencies regarding the number of Web
snippets, $N_{s}$, from the results of the entire probabilistic model.
The results were still unexplainable when the similarity factor was
used alone: MOD somehow performed better when $N_{s}$ was small, while
the performance of HAR always peaked at $N_{s}=\text{500}$.

On the corpus used for $P(f)$, we found that the huge Web corpus did
not always produce a better result than the relatively small
controlled corpus: NewsCP was regarded as better by a single judge,
while WebCP was regarded as better by three judges (see ``$\bullet$''
of the columns MOD and HAR in \tab{gen-prob}).
Component analysis, on the other hand, showed that NewsCP tended to
perform better than WebCP when BOW or MOD was used alone (see
\tab{gen-similarity}).  We speculate that the morphological analyzer
and dependency parser produce errors when features are extracted from
the Web corpus, because those tools are tuned to newspaper articles.
Likewise, $P(f|s)$ and $P(f|t)$ are expected to involve noise even
though they are estimated using relatively clean parts of Web pages
retrieved by querying phrases.  Surprisingly, HAR compensated for the
inferiority of WebCP, achieving accuracies comparable to the entire
probabilistic model.

\subsection{Summary of the input-wise evaluation}
\label{ssec:summary1}

The probabilistic model was derived straightforwardly from the
conditional probability $P(t|s)$.  However, as shown above, no
combination of parameters could achieve the desired result.
The disappointing results might be due to the separate estimation of
each factor.  In other words, if the entire probabilistic model is
optimized according to their implementation, the performance may be
improved.
The component analyses, however, revealed the lack of utility of each
factor, underlining the difficulty of this complex approach.

The experiment produced two major findings.
The first is the utility of contextual similarity in combination with
the constituent similarity underlying morpho-syntactic paraphrases of
predicate phrases.  While a variety of measures have so far been
proposed and evaluated basically for lexical paraphrases of words and
word sequences for the paraphrase acquisition manner, we have
empirically confirmed their applicability to computing the semantic
similarity and substitutability of automatically generated {\pcp}s.
The second finding is the versatility of the Web for representing the
characteristics of predicate phrases.  We could use up to only 1,000
Web snippets for each predicate phrase; nevertheless, contextual
features extracted from the Web snippets enabled us to compute the
appropriateness of {\pcp}s as paraphrases at a tolerable accuracy.
The lack of a sophisticated weighting function suggests that we can
improve the measures further.




\section{Score-based evaluation}
\label{sec:eval-rec}

Previous work has acquired lexical paraphrases accurately by skimming
the most reliable portion of a huge number of {\pc}s.  Our second
evaluation attempts from this viewpoint, i.e., how accurately a method
gives higher scores to more appropriate {\pcp}s.

\subsection{Sampling and judgment}
\label{ssec:rec-sampling}

In this evaluation, we investigate the performance of only the
baseline measures, i.e., 2 count-based and 24 distributional
similarity measures, because one of the assumptions that we have
introduced to formalize the probabilistic model, i.e., $s$ is
grammatical, does not allow us to use the model for this purpose.
A {\pc} for an ungrammatical phrase may be improperly found to have a
high conditional probability $P(t|s)$.

We first extracted the 200 best {\pcp}s for each measure.  Three
assessors were then asked to separately judge all of the 627 {\pcp}s
that cover the 26 sample sets.
The inter-assessor agreement of each pair of assessors is summarized
in \tab{rec-judge}.  The columns in the table correspond to those of
\tab{gen-judge}.  As a result of extracting the most reliable pairs,
the agreement ratio of the four questions and the proportion of
grammatical phrase pairs were significantly higher than those of the
experiment in \sec{eval-gen} ($p<\text{0.01}$ of the 2-sample test for
equality of proportions).
$\kappa$-values for judging Q$_{\textrm{s2t}}$ were also remarkably
high, while those for judging Q$_{\textrm{t2s}}$ were at the same
range as the input-wise evaluation.

\begin{table}[t]
\caption{Agreement of human judgment ($n=\text{627}$).}
\label{tab:rec-judge}
\input{10table13.txt}
\end{table}

\subsection{Results}
\label{ssec:ev-rec}

\tab{rec-baseline} summarizes the numbers of the {\pc} pairs to which
questions Q$_{\text{sc}}$, Q$_{\text{tc}}$, and Q$_{\text{s2t}}$ were
answered ``Yes.''
The measures performed remarkably better in this traditional
evaluation method based on $N$-best samples than the input-wise
evaluation (cf.~\tab{gen-baseline}).
Unlike the input-wise evaluation in \sec{eval-gen}, two sample sets
derived by different measures do not necessarily contain samples for
the same sets of source phrases.  We therefore applied the 2-sample
test for equality of proportions to compare accuracies of two
arbitrary measures.
``$\sig\sig$'' and ``$\sig$'' denote the significance levels
$p<\text{0.01}$ and $p<\text{0.05}$ between the best measure and each
measure, respectively.

\begin{table}[t]
\caption{Appropriate paraphrases among 200 best candidates.}
\label{tab:rec-baseline}
\input{10table14.txt}
\end{table}

The results show the significant advantages of distributional
similarity measures over the count-based measures.  On the
distributional similarity measures, the lower number of ``$\sig$''
implies that the performance of these measures reached a ceiling.
The underlined numbers in \tab{rec-baseline} indicate {\compfeat}.
Fortunately, BOW performed the task as well as MOD and HAR.  This is a
favorable result because BOW features can be extracted much more
quickly and accurately than MOD features.




\section{Error analysis}
\label{sec:errors}

The accuracies based on the assessments of the three judges were
approximately 40\% in the input-wise evaluation and 80\% in the
200-best evaluation.
This section describes typical errors, i.e., inappropriate {\pcp}s
whose appropriateness was improperly estimated to be high.

Most of the common errors in our experiment were generated when the
following knowledge was applied to the given $N_{1}$:$N_{2}$:$C$:$V$
type phrase together \cite{fujita:07:a}.
\numexs{knowledge}{
\item Transformation pattern: $N_{1}$:$N_{2}$:$C$:$V$ {\Ra}
  $\mathit{np}(N_{1},N_{2})$:$C$:$V$
\item Generation function: $\mathit{np}(N_{1},N_{2})$ {\Ra} $N_{2}$}
Dropping a nominal element $N_{1}$ of the given nominal compound
$N_{1}$:$N_{2}$ by \refexs{knowledge}{b} normally generalizes the
meaning that the compound conveys, and thus generates appropriate
(directional) paraphrases such as those shown in \refex{acceptable}.
\begin{multicols}{2}
\numexs{acceptable}{
\item[$s.$] \begin{jexample}
\chunk{損害-賠償-を}{damage-compensation-\textsc{acc}}
\chunk{求める}{to require}
\gloss{to demand compensation for damages}
\end{jexample}
\item[$t.$] \begin{jexample}
\chunk{賠償-を}{compensation-\textsc{acc}}
\chunk{求める}{to require}
\gloss{to demand compensation}
\end{jexample}}
\end{multicols}
{\noindent}However, it caused errors in some cases; for example,
dropping $N_{1}$ of the source sentence in \refex{error1} generates an
anomaly, because it was the semantic head of the sentence.
\begin{multicols}{2}
\numexs{error1}{
\item[$s$.] \begin{jexample}
\chunk{出血-多量-で}{bleeding-much-because}
\chunk{死亡する}{to die}
\gloss{to die due to heavy blood loss}
\end{jexample}
\item[$t$.] \begin{jexample}
\chunk{{\badex}多量-で}{much-because}
\chunk{死亡する}{to die}
\gloss{{\badex}to die due to plenty}
\end{jexample}}
\end{multicols}

In our experiment, source phrases were assumed to be grammatical.
However, as exhibited by the examples \refexs{judge}{a} and
\refexs{error2}{$s$}, some of extracted sub-parses were ungrammatical.
\begin{multicols}{2}
\numexs{error2}{
\item[$s$.] \begin{jexample}
\chunk{{\badex}気圧-配置-が}{pressure-pattern-\textsc{nom}}
\chunk{強まる}{to be strengthened}
\gloss{{\badex}pressure pattern is strengthened}
\end{jexample}
\item[$t$.] \begin{jexample}
\chunk{{\badex}配置-が}{layout-\textsc{nom}}
\chunk{強まる}{to be strengthened}
\gloss{{\badex}layout is strengthened}
\end{jexample}}
\end{multicols}
{\noindent}For 11 source phrases among the 200 samples in the first
evaluation, Q$_{\textrm{sc}}$ was answered ``No,'' i.e.,
ungrammatical, by at least 1 judge.  Thus, for automatic generation of
paraphrase knowledge, the task of capturing the appropriate boundary
of a given phrase should be addressed.

The other notable observation is that the appropriateness of {\pc}s
for predicate phrases containing an adjective was poorly computed.
The primal source of the errors for $Adj$:$N$:$C$:$V$ type phrases was
the subtle change of nuance by switching syntactic heads as
illustrated in \refex{adj1}.
\begin{multicols}{2}
\numexs{adj1}{
\item[$s$.] \begin{jexample}
\chunk{良い}{be good}
\chunk{仕事-を}{work-\textsc{acc}}
\chunk{する}{to do}
\gloss{to do a good job}
\end{jexample}
\bigskip
\item[$t_{1}$.] \begin{jexample}
\chunk{{\noteqex}良く}{much}
\chunk{仕事-する}{to work}
\gloss{{\noteqex}to work hard}
\end{jexample}
\item[$t_{2}$.] \begin{jexample}
\chunk{{\noteqex}仕事-を}{work-\textsc{acc}}
\chunk{良く-する}{be good-to make}
\gloss{{\noteqex}to improve the work}
\end{jexample}}
\end{multicols}

Most errors in paraphrasing $N$:$C$:$Adj$ type phrases, on the other
hand, were caused due to the difference of the aspectual property and
agentivity between adjectives and verbs.
For example, \refexs{adj2}{$s$} can describe not only things whose
quality has been improved as inferred by \refexs{adj2}{$t$}, but also
those that were originally of high quality \cite{fujita:06:d}.
\begin{multicols}{2}
\numexs{adj2}{
\item[$s$.] \begin{jexample}
\chunk{質-が}{quality-\textsc{nom}}
\chunk{高い}{be high}
\gloss{(Its) quality is high}
\end{jexample}
\item [$t$.] \begin{jexample}
\chunk{{\noteqex}質-が}{quality-\textsc{nom}}
\chunk{高まる}{to rise}
\gloss{{\noteqex}(Its) quality rises}
\end{jexample}}
\end{multicols}
{\noindent}$\textrm{Q}_{\textrm{s2t}}$ for \refex{adj2} was thus
judged ``No.''  To realize paraphrases that involve the change of
syntactic categories, we need to enhance the lexical derivation
dictionary by capturing the subtle difference between the original and
derived words.



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

A pair of expressions qualifies as paraphrases if and only if they are
semantically equivalent, substitutable in some contexts, and
grammatical.  When paraphrase knowledge is represented with general
transformation patterns to attain high coverage of paraphrases, we
should assess not only the first and second criteria, but also the
third criterion.
On the basis of this recognition, in this paper, we address the task
of measuring the appropriateness of the given pair of phrases as
paraphrases, as a post-generation assessment of automatically
generated candidates of phrasal variants.  We examined several
measures including a novel probabilistic model, which consists of two
components: (i)~a structured $N$-gram language model that ensures
grammaticality and (ii)~a distributional similarity measure for
estimating semantic equivalence and substitutability between two
phrases.

Through the experiment, we empirically evaluated the performance of
the measures, analyzed the characteristics, and found the following.
\begin{itemize}
\item Contextual similarity in combination with the constituent
  similarity of morpho-syntactic paraphrases is effective for
  measuring the appropriateness of the given pair of predicate phrases
  as paraphrases.  Among several measures, two existing distributional
  similarity measures achieved a tolerable level of performance.  They
  performed the task significantly better than not only the
  count-based measures, which only assess the grammaticality of
  {\pc}s, but also the probabilistic model.  We also showed that
  combining two feature sets was beneficial.
\item The Web is versatile for representing the characteristics of
  predicate phrases.  Contextual features extracted from the Web
  snippets contributed to the task.  Our first aim in harnessing Web
  snippets was to overcome the data sparseness problem; however,
  additionally, issuing a phrase as a query to a commercial search
  engine also contributes to assessing the grammaticality of the
  phrase to some degree.
\end{itemize}
Two different evaluations also revealed the difference between the
difficulties of the recognition and generation tasks.

We are developing a two-step plan for our future work.
In the first step, we will attempt to enhance the measures by
incorporating a more sophisticated language model for the
probabilistic model, and further examining distributional similarity
measures: the three elements described in \ssec{acquisition}.
Once the performance reaches a reasonable level, we will generate a
huge paraphrase knowledge base consisting of millions of phrasal
variant pairs and provide it to the research community.



\bibliographystyle{jnlpbbl_1.4}
\newcommand{\bibsort}[1]{}
\begin{thebibliography}{}

\bibitem[\protect\BCAY{Bannard \BBA\ Callison-Burch}{Bannard \BBA\
  Callison-Burch}{2005}]{bannard:05}
Bannard, C.\BBACOMMA\ \BBA\ Callison-Burch, C. \BBOP 2005\BBCP.
\newblock \BBOQ Paraphrasing with bilingual parallel corpora.\BBCQ\
\newblock In {\Bem Proceedings of the 43rd Annual Meeting of the Association
  for Computational Linguistics {\rm (}ACL\/{\rm )}}, \mbox{\BPGS\ 597--604}.

\bibitem[\protect\BCAY{Barzilay \BBA\ McKeown}{Barzilay \BBA\
  McKeown}{2001}]{barzilay:01}
Barzilay, R.\BBACOMMA\ \BBA\ McKeown, K.~R. \BBOP 2001\BBCP.
\newblock \BBOQ Extracting paraphrases from a parallel corpus.\BBCQ\
\newblock In {\Bem Proceedings of the 39th Annual Meeting of the Association
  for Computational Linguistics {\rm (}ACL\/{\rm )}}, \mbox{\BPGS\ 50--57}.

\bibitem[\protect\BCAY{Barzilay \BBA\ Lee}{Barzilay \BBA\
  Lee}{2003}]{barzilay:03:a}
Barzilay, R.\BBACOMMA\ \BBA\ Lee, L. \BBOP 2003\BBCP.
\newblock \BBOQ Learning to paraphrase: an unsupervised approach using
  multiple-sequence alignment.\BBCQ\
\newblock In {\Bem Proceedings of the 2003 Human Language Technology Conference
  and the North American Chapter of the Association for Computational
  Linguistics {\rm (}HLT-NAACL\/{\rm )}}, \mbox{\BPGS\ 16--23}.

\bibitem[\protect\BCAY{Bhagat, Pantel, \BBA\ Hovy}{Bhagat
  et~al.}{2007}]{bhagat:07}
Bhagat, R., Pantel, P., \BBA\ Hovy, E. \BBOP 2007\BBCP.
\newblock \BBOQ {LEDIR}: an unsupervised algorithm for learning directionality
  of inference rules.\BBCQ\
\newblock In {\Bem Proceedings of the 2007 Conference on Empirical Methods in
  Natural Language Processing and Computational Natural Language Learning {\rm
  (}EMNLP-CoNLL\/{\rm )}}, \mbox{\BPGS\ 161--170}.

\bibitem[\protect\BCAY{Dolan, Quirk, \BBA\ Brockett}{Dolan
  et~al.}{2004}]{dolan:04}
Dolan, B., Quirk, C., \BBA\ Brockett, C. \BBOP 2004\BBCP.
\newblock \BBOQ Unsupervised construction of large paraphrase corpora:
  exploiting massively parallel news sources.\BBCQ\
\newblock In {\Bem Proceedings of the 20th International Conference on
  Computational Linguistics {\rm (}COLING\/{\rm )}}, \mbox{\BPGS\ 350--356}.

\bibitem[\protect\BCAY{Dras}{Dras}{1999}]{dras:99:a}
Dras, M. \BBOP 1999\BBCP.
\newblock {\Bem Tree adjoining grammar and the reluctant paraphrasing of text}.
\newblock Ph.D.\ thesis, Division of Information and Communication Science,
  Macquarie University.

\bibitem[\protect\BCAY{Fujita, Inui, \BBA\ Matsumoto}{Fujita
  et~al.}{2004}]{fujita:04:b}
Fujita, A., Inui, K., \BBA\ Matsumoto, Y. \BBOP 2004\BBCP.
\newblock \BBOQ Detection of incorrect case assignments in automatically
  generated paraphrases of {Japanese} sentences.\BBCQ\
\newblock In {\Bem Proceedings of the 1st International Joint Conference on
  Natural Language Processing {\rm (}IJCNLP\/{\rm )}}, \mbox{\BPGS\ 14--21}.

\bibitem[\protect\BCAY{Fujita \BBA\ Inui}{Fujita \BBA\
  Inui}{2006}]{fujita:06:c-e}
Fujita, A.\BBACOMMA\ \BBA\ Inui, K. \BBOP 2006\BBCP.
\newblock \BBOQ Building a paraphrase corpus based on class-oriented candidate
  generation.\BBCQ\
\newblock {\Bem Journal of Natural Language Processing}, {\Bbf 13}  (3),
  \mbox{\BPGS\ 133--150}.
\newblock (in Japanese).

\bibitem[\protect\BCAY{Fujita, Masuno, Sato, \BBA\ Utsuro}{Fujita
  et~al.}{2006}]{fujita:06:d}
Fujita, A., Masuno, N., Sato, S., \BBA\ Utsuro, T. \BBOP 2006\BBCP.
\newblock \BBOQ Adjective-to-verb paraphrasing in {Japanese} based on lexical
  constraints of verbs.\BBCQ\
\newblock In {\Bem Proceedings of the 4th International Natural Language
  Generation Conference {\rm (}INLG\/{\rm )}}, \mbox{\BPGS\ 41--43}.

\bibitem[\protect\BCAY{Fujita, Kato, Kato, \BBA\ Sato}{Fujita
  et~al.}{2007}]{fujita:07:a}
Fujita, A., Kato, S., Kato, N., \BBA\ Sato, S. \BBOP 2007\BBCP.
\newblock \BBOQ A compositional approach toward dynamic phrasal thesaurus.\BBCQ\
\newblock In {\Bem Proceedings of the ACL-PASCAL Workshop on Textual Entailment
  and Paraphrasing {\rm (}WTEP\/{\rm )}}, \mbox{\BPGS\ 151--158}.

\bibitem[\protect\BCAY{Geffet \BBA\ Dagan}{Geffet \BBA\
  Dagan}{2004}]{geffet:04}
Geffet, M.\BBACOMMA\ \BBA\ Dagan, I. \BBOP 2004\BBCP.
\newblock \BBOQ Feature vector quality and distributional similarity.\BBCQ\
\newblock In {\Bem Proceedings of the 20th International Conference on
  Computational Linguistics {\rm (}COLING\/{\rm )}}, \mbox{\BPGS\ 247--253}.

\bibitem[\protect\BCAY{Geffet \BBA\ Dagan}{Geffet \BBA\
  Dagan}{2005}]{geffet:05}
Geffet, M.\BBACOMMA\ \BBA\ Dagan, I. \BBOP 2005\BBCP.
\newblock \BBOQ The distributional inclusion hypotheses and lexical
  entailment.\BBCQ\
\newblock In {\Bem Proceedings of the 43rd Annual Meeting of the Association
  for Computational Linguistics {\rm (}ACL\/{\rm )}}, \mbox{\BPGS\ 107--116}.

\bibitem[\protect\BCAY{Habash}{Habash}{2004}]{habash:04:a}
Habash, N. \BBOP 2004\BBCP.
\newblock \BBOQ The use of a structural {N}-gram language model in
  generation-heavy hybrid machine translation.\BBCQ\
\newblock In {\Bem Proceedings of the 3rd International Natural Language
  Generation Conference {\rm (}INLG\/{\rm )}}, \mbox{\BPGS\ 61--69}.

\bibitem[\protect\BCAY{Hagiwara, Ogawa, \BBA\ Toyama}{Hagiwara
  et~al.}{2008a}]{hagiwara:08:a}
Hagiwara, M., Ogawa, Y., \BBA\ Toyama, K. \BBOP 2008a\BBCP.
\newblock \BBOQ Effective use of indirect dependency for distributional
  similarity.\BBCQ\
\newblock {\Bem Journal of Natural Language Processing}, {\Bbf 15}  (4),
  \mbox{\BPGS\ 19--42}.

\bibitem[\protect\BCAY{Hagiwara, Ogawa, \BBA\ Toyama}{Hagiwara
  et~al.}{2008b}]{hagiwara:08:b}
Hagiwara, M., Ogawa, Y., \BBA\ Toyama, K. \BBOP 2008b\BBCP.
\newblock \BBOQ A comparative study on effective context selection for
  distributional similarity.\BBCQ\
\newblock {\Bem Journal of Natural Language Processing}, {\Bbf 15}  (5),
  \mbox{\BPGS\ 119--150}.

\bibitem[\protect\BCAY{Harris}{Harris}{1957}]{harris:57}
Harris, Z. \BBOP 1957\BBCP.
\newblock \BBOQ Co-occurrence and transformation in linguistic structure.\BBCQ\
\newblock {\Bem Language}, {\Bbf 33}  (3), \mbox{\BPGS\ 283--340}.

\bibitem[\protect\BCAY{Harris}{Harris}{1968}]{harris:68}
Harris, Z. \BBOP 1968\BBCP.
\newblock {\Bem Mathematical structures of language}.
\newblock John Wiley \& Sons.

\bibitem[\protect\BCAY{Ibrahim, Katz, \BBA\ Lin}{Ibrahim
  et~al.}{2003}]{ibrahim:03}
Ibrahim, A., Katz, B., \BBA\ Lin, J. \BBOP 2003\BBCP.
\newblock \BBOQ Extracting structural paraphrases from aligned monolingual
  corpora.\BBCQ\
\newblock In {\Bem Proceedings of the 2nd International Workshop on
  Paraphrasing: Paraphrase Acquisition and Applications {\rm (}IWP\/{\rm )}},
  \mbox{\BPGS\ 57--64}.

\bibitem[\protect\BCAY{Inui \BBA\ Fujita}{Inui \BBA\
  Fujita}{2004}]{inui:04:a-e}
Inui, K.\BBACOMMA\ \BBA\ Fujita, A. \BBOP 2004\BBCP.
\newblock \BBOQ A survey on paraphrase generation and recognition.\BBCQ\
\newblock {\Bem Journal of Natural Language Processing}, {\Bbf 11}  (5),
  \mbox{\BPGS\ 151--198}.
\newblock (in Japanese).

\bibitem[\protect\BCAY{Iordanskaja, Kim, Kittredge, Lavoie, \BBA\
  Polgu\`{e}re}{Iordanskaja et~al.}{1992}]{iordanskaja:92}
Iordanskaja, L., Kim, M., Kittredge, R., Lavoie, B., \BBA\ Polgu\`{e}re, A.
  \BBOP 1992\BBCP.
\newblock \BBOQ Generation of extended bilingual statistical reports.\BBCQ\
\newblock In {\Bem Proceedings of the 14th International Conference on
  Computational Linguistics {\rm (}COLING\/{\rm )}}, \mbox{\BPGS\ 1019--1023}.

\bibitem[\protect\BCAY{Jacquemin}{Jacquemin}{1999}]{jacquemin:99}
Jacquemin, C. \BBOP 1999\BBCP.
\newblock \BBOQ Syntagmatic and Paradigmatic Representations of Term
  Variation.\BBCQ\
\newblock In {\Bem Proceedings of the 37th Annual Meeting of the Association
  for Computational Linguistics {\rm (}ACL\/{\rm )}}, \mbox{\BPGS\ 341--348}.

\bibitem[\protect\BCAY{Kawahara \BBA\ Kurohashi}{Kawahara \BBA\
  Kurohashi}{2006}]{kawahara:06:b}
Kawahara, D.\BBACOMMA\ \BBA\ Kurohashi, S. \BBOP 2006\BBCP.
\newblock \BBOQ Case frame compilation from the {Web} using high-performance
  computing.\BBCQ\
\newblock In {\Bem Proceedings of the 5th International Conference on Language
  Resources and Evaluation {\rm (}LREC\/{\rm )}}.

\bibitem[\protect\BCAY{Kilgarriff}{Kilgarriff}{2007}]{kilgarriff:07}
Kilgarriff, A. \BBOP 2007\BBCP.
\newblock \BBOQ Googleology is bad science.\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 33}  (1), \mbox{\BPGS\
  147--151}.

\bibitem[\protect\BCAY{Lee}{Lee}{1999}]{lee:99:a}
Lee, L. \BBOP 1999\BBCP.
\newblock \BBOQ Measures of distributional similarity.\BBCQ\
\newblock In {\Bem Proceedings of the 37th Annual Meeting of the Association
  for Computational Linguistics {\rm (}ACL\/{\rm )}}, \mbox{\BPGS\ 25--32}.

\bibitem[\protect\BCAY{Lin}{Lin}{1998}]{lin:98:b}
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 the 17th International Conference on
  Computational Linguistics {\rm (}COLING-ACL\/{\rm )}}, \mbox{\BPGS\
  768--774}.

\bibitem[\protect\BCAY{Lin \BBA\ Pantel}{Lin \BBA\ Pantel}{2001}]{lin:01}
Lin, D.\BBACOMMA\ \BBA\ Pantel, P. \BBOP 2001\BBCP.
\newblock \BBOQ Discovery of inference rules for question answering.\BBCQ\
\newblock {\Bem Natural Language Engineering}, {\Bbf 7}  (4), \mbox{\BPGS\
  343--360}.

\bibitem[\protect\BCAY{Matsuyoshi \BBA\ Sato}{Matsuyoshi \BBA\
  Sato}{2008}]{matsuyoshi:08:c-e}
Matsuyoshi, S.\BBACOMMA\ \BBA\ Sato, S. \BBOP 2008\BBCP.
\newblock \BBOQ Automatic paraphrasing of {Japanese} functional expressions
  under style and readability specifications.\BBCQ\
\newblock {\Bem Journal of Natural Language Processing}, {\Bbf 15}  (2),
  \mbox{\BPGS\ 75--99}.
\newblock (in Japanese).

\bibitem[\protect\BCAY{Mel'\v{c}uk \BBA\ Polgu\`{e}re}{Mel'\v{c}uk \BBA\
  Polgu\`{e}re}{1987}]{melcuk:87}
Mel'\v{c}uk, I.\BBACOMMA\ \BBA\ Polgu\`{e}re, A. \BBOP 1987\BBCP.
\newblock \BBOQ A formal lexicon in meaning-text theory (or how to do lexica
  with words).\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 13}  (3-4), \mbox{\BPGS\
  261--275}.

\bibitem[\protect\BCAY{Mochihashi \BBA\ Sumita}{Mochihashi \BBA\
  Sumita}{2007}]{mochihashi:07:c}
Mochihashi, D.\BBACOMMA\ \BBA\ Sumita, E. \BBOP 2007\BBCP.
\newblock \BBOQ The Infinite Markov Model.\BBCQ\
\newblock In {\Bem Proceedings of the 21st Annual Conference on Neural
  Information Processing Systems {\rm (}NIPS\/{\rm )}}.

\bibitem[\protect\BCAY{Ohtake, Sekiguchi, \BBA\ Yamamoto}{Ohtake
  et~al.}{2004}]{ohtake:04}
Ohtake, K., Sekiguchi, Y., \BBA\ Yamamoto, K. \BBOP 2004\BBCP.
\newblock \BBOQ Detecting transliterated orthographic variants via two
  similarity metrics.\BBCQ\
\newblock In {\Bem Proceedings of the 20th International Conference on
  Computational Linguistics {\rm (}COLING\/{\rm )}}, \mbox{\BPGS\ 709--715}.

\bibitem[\protect\BCAY{Okanohara \BBA\ Tsujii}{Okanohara \BBA\
  Tsujii}{2007}]{okanohara:07:b}
Okanohara, D.\BBACOMMA\ \BBA\ Tsujii, J. \BBOP 2007\BBCP.
\newblock \BBOQ A discriminative language model with pseudo-negative
  samples.\BBCQ\
\newblock In {\Bem Proceedings of the 45th Annual Meeting of the Association
  for Computational Linguistics {\rm (}ACL\/{\rm )}}, \mbox{\BPGS\ 73--80}.

\bibitem[\protect\BCAY{Pang, Knight, \BBA\ Marcu}{Pang et~al.}{2003}]{pang:03}
Pang, B., Knight, K., \BBA\ Marcu, D. \BBOP 2003\BBCP.
\newblock \BBOQ Syntax-based alignment of multiple translations: extracting
  paraphrases and generating new sentences.\BBCQ\
\newblock In {\Bem Proceedings of the 2003 Human Language Technology Conference
  and the North American Chapter of the Association for Computational
  Linguistics {\rm (}HLT-NAACL\/{\rm )}}, \mbox{\BPGS\ 102--109}.

\bibitem[\protect\BCAY{Pantel, Bhagat, Coppola, Chklovski, \BBA\ Hovy}{Pantel
  et~al.}{2007}]{pantel:07}
Pantel, P., Bhagat, R., Coppola, B., Chklovski, T., \BBA\ Hovy, E. \BBOP
  2007\BBCP.
\newblock \BBOQ {ISP}: Learning Inferential Selectional Preferences.\BBCQ\
\newblock In {\Bem Proceedings of Human Language Technologies 2007: The
  Conference of the North American Chapter of the Association for Computational
  Linguistics {\rm (}NAACL-HLT\/{\rm )}}, \mbox{\BPGS\ 564--571}.

\bibitem[\protect\BCAY{Quirk, Brockett, \BBA\ Dolan}{Quirk
  et~al.}{2004}]{quirk:04}
Quirk, C., Brockett, C., \BBA\ Dolan, W. \BBOP 2004\BBCP.
\newblock \BBOQ Monolingual machine translation for paraphrase generation.\BBCQ\
\newblock In {\Bem Proceedings of the 2004 Conference on Empirical Methods in
  Natural Language Processing {\rm (}EMNLP\/{\rm )}}, \mbox{\BPGS\ 142--149}.

\bibitem[\protect\BCAY{Sekine}{Sekine}{2005}]{sekine:05}
Sekine, S. \BBOP 2005\BBCP.
\newblock \BBOQ Automatic paraphrase discovery based on context and keywords
  between {NE} pairs.\BBCQ\
\newblock In {\Bem Proceedings of the 3rd International Workshop on
  Paraphrasing {\rm (}IWP\/{\rm )}}, \mbox{\BPGS\ 80--87}.

\bibitem[\protect\BCAY{Shinyama, Sekine, Sudo, \BBA\ Grishman}{Shinyama
  et~al.}{2002}]{shinyama:02}
Shinyama, Y., Sekine, S., Sudo, K., \BBA\ Grishman, R. \BBOP 2002\BBCP.
\newblock \BBOQ Automatic paraphrase acquisition from news articles.\BBCQ\
\newblock In {\Bem Proceedings of the 2002 Human Language Technology Conference
  {\rm (}HLT\/{\rm )}}.

\bibitem[\protect\BCAY{Szpektor, Tanev, Dagan, \BBA\ Coppola}{Szpektor
  et~al.}{2004}]{szpektor:04}
Szpektor, I., Tanev, H., Dagan, I., \BBA\ Coppola, B. \BBOP 2004\BBCP.
\newblock \BBOQ Scaling {Web}-based acquisition of entailment relations.\BBCQ\
\newblock In {\Bem Proceedings of the 2004 Conference on Empirical Methods in
  Natural Language Processing {\rm (}EMNLP\/{\rm )}}, \mbox{\BPGS\ 41--48}.

\bibitem[\protect\BCAY{Szpektor, Dagan, Bar-Haim, \BBA\ Goldberger}{Szpektor
  et~al.}{2008}]{szpektor:08:a}
Szpektor, I., Dagan, I., Bar-Haim, R., \BBA\ Goldberger, J. \BBOP 2008\BBCP.
\newblock \BBOQ Contextual preferences.\BBCQ\
\newblock In {\Bem Proceedings of the 46th Annual Meeting of the Association
  for Computational Linguistics {\rm (}ACL\/{\rm )}}, \mbox{\BPGS\ 683--691}.

\bibitem[\protect\BCAY{Takahashi, Iwakura, Iida, Fujita, \BBA\ Inui}{Takahashi
  et~al.}{2001}]{takahashi:01:c}
Takahashi, T., Iwakura, T., Iida, R., Fujita, A., \BBA\ Inui, K. \BBOP
  2001\BBCP.
\newblock \BBOQ {\sc Kura}: a transfer-based lexico-structural paraphrasing
  engine.\BBCQ\
\newblock In {\Bem Proceedings of the 6th Natural Language Processing Pacific
  Rim Symposium {\rm (}NLPRS\/{\rm )} Workshop on Automatic Paraphrasing:
  Theories and Applications}, \mbox{\BPGS\ 37--46}.

\bibitem[\protect\BCAY{Torisawa}{Torisawa}{2002}]{torisawa:02:b}
Torisawa, K. \BBOP 2002\BBCP.
\newblock \BBOQ An unsupervised learning method for associative relationships
  between verb phrases.\BBCQ\
\newblock In {\Bem Proceedings of the 19th International Conference on
  Computational Linguistics {\rm (}COLING\/{\rm )}}, \mbox{\BPGS\ 1009--1015}.

\bibitem[\protect\BCAY{Torisawa}{Torisawa}{2006}]{torisawa:06}
Torisawa, K. \BBOP 2006\BBCP.
\newblock \BBOQ Acquiring inference rules with temporal constraints by using
  {Japanese} coordinated sentences and noun-verb co-occurrences.\BBCQ\
\newblock In {\Bem Proceedings of the Human Language Technology Conference of
  the North American Chapter of the Association for Computational Linguistics
  {\rm (}HLT-NAACL\/{\rm )}}, \mbox{\BPGS\ 57--64}.

\bibitem[\protect\BCAY{Uchimoto, Murata, Ma, Sekine, \BBA\ Isahara}{Uchimoto
  et~al.}{2000}]{uchimoto:00}
Uchimoto, K., Murata, M., Ma, Q., Sekine, S., \BBA\ Isahara, H. \BBOP
  2000\BBCP.
\newblock \BBOQ Word order acquisition from corpora.\BBCQ\
\newblock In {\Bem Proceedings of the 18th International Conference on
  Computational Linguistics {\rm (}COLING\/{\rm )}}, \mbox{\BPGS\ 871--877}.

\bibitem[\protect\BCAY{Weeds}{Weeds}{2003}]{weeds:03}
Weeds, J. \BBOP 2003\BBCP.
\newblock {\Bem Measures and applications of lexical distributional
  similarity}.
\newblock Ph.D.\ thesis, University of Sussex.

\bibitem[\protect\BCAY{Weeds, Weir, \BBA\ Keller}{Weeds
  et~al.}{2005}]{weeds:05}
Weeds, J., Weir, D., \BBA\ Keller, B. \BBOP 2005\BBCP.
\newblock \BBOQ The distributional similarity of sub-parses.\BBCQ\
\newblock In {\Bem Proceedings of the ACL Workshop on Empirical Modeling of
  Semantic Equivalence and Entailment}, \mbox{\BPGS\ 7--12}.

\bibitem[\protect\BCAY{Wu \BBA\ Zhou}{Wu \BBA\ Zhou}{2003}]{wu:03:a}
Wu, H.\BBACOMMA\ \BBA\ Zhou, M. \BBOP 2003\BBCP.
\newblock \BBOQ Synonymous collocation extraction using translation
  information.\BBCQ\
\newblock In {\Bem Proceedings of the 41st Annual Meeting of the Association
  for Computational Linguistics {\rm (}ACL\/{\rm )}}, \mbox{\BPGS\ 120--127}.

\bibitem[\protect\BCAY{Yamamoto}{Yamamoto}{2002}]{YamamotoKazuhide:02:d}
Yamamoto, K. \BBOP 2002\BBCP.
\newblock \BBOQ Acquisition of lexical paraphrases from texts.\BBCQ\
\newblock In {\Bem Proceedings of the 2nd International Workshop on
  Computational Terminology {\rm (}CompuTerm\/{\rm )}}, \mbox{\BPGS\ 22--28}.

\bibitem[\protect\BCAY{Yoshida, Nakagawa, \BBA\ Terada}{Yoshida
  et~al.}{2008}]{yoshida:08}
Yoshida, M., Nakagawa, H., \BBA\ Terada, A. \BBOP 2008\BBCP.
\newblock \BBOQ Gram-free synonym extraction via suffix arrays.\BBCQ\
\newblock In {\Bem Proceedings of the 4th Asia Information Retrieval Symposium
  {\rm (}AIRS\/{\rm )}}, \mbox{\BPGS\ 282--291}.

\end{thebibliography}



\begin{biography}
\bioauthor[:]{Atsushi Fujita}{
Atsushi Fujita is an associate professor at the School of Systems
Information Science, Future University-Hakodate.  His research
interests include natural language processing and computational
linguistics, especially automatic paraphrasing and lexical semantics.
He received B.E. and M.E. from Kyushu Institute of Technology in 2000
and 2002, respectively.  He received Doctor of Engineering from Nara
Institute of Science and Technology in 2005.
}

\bioauthor[:]{Satoshi Sato}{
Satoshi Sato is a professor of Department of Electrical Engineering
and Computer Science in Nagoya University.  His recent work in natural
language processing focuses on automatic paraphrasing, controlled
language, and automatic lexicon compilation.  He received B.E.,
M.E., and Doctor of Engineering from Kyoto University in 1983, 1985,
and 1992, respectively.
}


\end{biography}








\biodate



\end{document}

