
\documentstyle[epsf,theapa]{jnlp_e_b5}   

\setcounter{page}{111}
\setcounter{巻数}{4}
\setcounter{号数}{2}
\setcounter{年}{1997}
\setcounter{月}{4}
\受付{September}{10}{1996}
\採録{November}{11}{1996}

\setcounter{secnumdepth}{2}

\title{}
\author{}
\jkeywords{}

\etitle{Case Contribution in Example-Based Verb Sense \\ Disambiguation}

\eauthor{Atsushi Fujii\affiref{TITECH}    \and
        Kentaro Inui\affiref{TITECH}      \and
        Takenobu Tokunaga\affiref{TITECH} \and
        Hozumi Tanaka\affiref{TITECH}}

\headauthor{Fujii,~A.~et~al.}
\headtitle{Case Contribution in Example-Based Verb Sense Disambiguation}

\affilabel{TITECH}
          {Tokyo Institute of Technology, Department of Computer Science}
          {Tokyo Institute of Technology, Department of Computer Science}

\eabstract{
  Word sense disambiguation has recently been utilized in corpus-based
  approaches, reflecting the growth in the number of machine readable
  texts. One category of approaches disambiguates an input verb sense
  based on the similarity between its governing case fillers and those
  in given examples. In this paper, we introduce the degree of case
  contribution to verb sense disambiguation into this existing method. 
  In this, greater diversity of semantic range of case filler examples
  will lead to that case contributing to verb sense disambiguation
  more.  We also report the result of a comparative experiment, in
  which the performance of disambiguation is improved by considering
  this notion of semantic contribution.
}

\ekeywords{Word Sense Disambiguation, Example-Based Approach, Case
  Contribution to Disambiguation}

\begin{document}

\maketitle


\newcommand{\E}{}
\newcommand{\EX}{}
\newcommand{\EXi}[2]{}
\newcommand{\EXii}[3]{}
\newcommand{\V}{}
\newcommand{\SS}{}
\newcommand{\SSi}[1]{}
\newcommand{\C}{}
\newcommand{\Ci}[1]{}
\newcommand{\Ni}[1]{}
\newcommand{\Mi}[1]{}
\newcommand{\eq}[1]{}

\makeatletter
\def\cons#1#2{}
\def\car#1{}
\def\cdr#1{}
\def\xmark{}
\def\nil{}
\def\settreesizes{}
\newdimen\treewidth
\def\setsizes{}
\def\inittreewidth{}
\newbox\treebox
\def\tree{}
\def\subtree{}
\def\leaf#1{}
\def\endsubtree{}
\def\endtree{}
\newif\iftreetext\treetextfalse
\def\boxtree{}
\def\ettext{}
\def\makesubtree{}
\def\addsubtreebox{}
\def\subtreebox{}
\def\treectrbox#1{}
\def\treehalfrule{}
\def\makeleaf{}
\def\makeparent{}
\def\sizesubtrees{}
\def\sizelevel{}
\newdimen\treeheight
\newif\ifleaf
\newif\ifbotsub
\newif\iftopsub
\def\typesettree{}
\def\maketree{}
{\catcode`@=11
\gdef\makesubtreebox{}}
\makeatother

\newcommand{\sstack}[1]{}
\newcommand{\nstack}[1]{}
\newcommand{\treeroot}[2]{}
\newcommand{\branch}[2]{}
\newcommand{\LEAF}[1]{}
\newcommand{\treerootf}[2]{}
\newcommand{\branchf}[2]{}
\newcommand{\LEAFf}[1]{}
\renewcommand{\subtreebox}{}
\renewcommand{\makeparent}{}
\renewcommand{\makesubtree}{}

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

Word sense disambiguation is a crucial task in many kinds of natural
language processing applications, such as word selection in machine
translation~\cite{brown:91}, pruning of syntactic structures in
parsing~\cite{lytinen:86,k.nagao:94} and text
retrieval~\cite{krovets:92,voorhees:93}.  Various researches on word
sense disambiguation have recently been utilized in corpus-based
approaches, reflecting the growth in the number of machine readable
texts.  Unlike rule-based approaches, corpus-based approaches free us
from the task of generalizing observed phenomena to produce rules for
word sense disambiguation, \hspace{-0.15mm}e.g.\hspace{-0.15mm} subcategorization \hspace{-0.15mm}rules. \hspace{-0.15mm}Corpus-based\hspace{-0.15mm} 
approaches\hspace{-0.15mm} are\hspace{-0.15mm} executed\hspace{-0.15mm} based\hspace{-0.15mm} on\hspace{-0.1mm} the\hspace{-0.1mm} intuitively\hspace{-0.1mm} feasible\hspace{-0.1mm} assumption
that\hspace{-0.1mm} the\hspace{-0.1mm} higher\hspace{-0.1mm} the\hspace{-0.1mm} degree\hspace{-0.1mm} of\hspace{-0.1mm} similarity\hspace{-0.1mm} between\hspace{-0.1mm} the\hspace{-0.1mm} context of an
input word and the context in which the word appears in a sense in a
corpus, the more plausible it becomes that the word is used in the
same sense.  Corpus-based methods are classified into two approaches:
example-based approaches~\cite{kurohashi:94,uramoto:94:a} and\hspace{-0.1mm}
statistics-based\hspace{-0.1mm} 
a\hspace{-0.1mm}pproaches\hspace{-0.1mm}~\cite{brown:91,dagan:94:a,niwa:94,schutze:92:a,yarowsky:95}.
We follow the example-based approach in explaining its effectivity for
verb sense disambiguation in Japanese.

A representative example-based method for verb sense disambiguation
was proposed by Kurohashi and Nagao (Kurohashi's
method)~\cite{kurohashi:94}.  Their method uses an example database
containing examples of collocations as in figure \ref{fig:toru}.
\begin{figure}[htbp]
  \begin{center}
    \scriptsize
    \leavevmode
    \begin{tabular}{|lll|} \hline
      & & \\ \framebox{{\it toru\/}:} & & \\ & & \\ \hline $\left\{
      \begin{tabular}{ll} {\it suri\/} & (pickpocket) \\
        {\it kanojo\/} & (she) \\ {\it ani\/} & (brother)
      \end{tabular}\right\}$ {\it ga\/} & $\left\{
      \begin{tabular}{ll}
        {\it kane\/} & (money) \\ {\it saifu\/} & (wallet) \\ {\it
          otoko\/} & (man) \\ {\it uma\/} & (horse) \\ {\it aidea\/} &
        (idea)
      \end{tabular}\right\}$ {\it wo\/} & {\it toru\/} (to
      take/steal) \\ \hline $\left\{
      \begin{tabular}{ll} {\it kare\/} &
        (he) \\ {\it kanojo\/} & (she) \\ {\it shachou\/} &
        (company president) \\ {\it gakusei\/} & (student)
      \end{tabular}\right\}$ {\it ga\/} & $\left\{
      \begin{tabular}{ll} {\it menkyoshou\/} &
        (license) \\ {\it shikaku\/} & (qualification) \\ {\it biza\/}
        & (visa)
      \end{tabular}\right\}$ {\it wo\/} & {\it toru\/} (to attain) \\
      \hline $\left\{
      \begin{tabular}{ll} {\it kare\/} &
        (he) \\ {\it chichi\/} & (father) \\ {\it kyaku\/} & (client)
      \end{tabular}\right\}$ {\it ga\/} & $\left\{
      \begin{tabular}{ll}
        {\it shinbun\/} & (newspaper) \\ {\it zasshi\/} & (journal)
      \end{tabular}\right\}$ {\it wo\/} & {\it toru\/} (to subscribe) \\ 
      \hline $\left\{
      \begin{tabular}{ll} {\it kare\/} & (he) \\ {\it
          dantai\/} & (group) \\ {\it ryokoukyaku\/} & (passenger)
        \\ {\it joshu\/} & (assistant)
      \end{tabular}\right\}$ {\it ga\/} & $\left\{
      \begin{tabular}{ll} {\it kippu\/} & (ticket) \\ {\it heya\/}
        & (room) \\ {\it hikouki\/} & (airplane)
      \end{tabular}\right\}$ {\it wo\/} & {\it toru\/} (to reserve) \\ \hline
      {\hfill \centering $\vdots$ \hfill} & {\hfill \centering
        $\vdots$ \hfill} & {\hfill \centering $\vdots$ \hfill} \\ 
      \hline
    \end{tabular}
  \end{center}
  \caption{A fragment of an example database, and the entry
    associated with Japanese verb {\it toru\/}}
  \label{fig:toru}
\end{figure}

Figure \ref{fig:toru} shows a fragment of the entry associated with
the Japanese verb {\it toru}. As with most words, the verb {\it
  toru\/} has multiple senses, examples of which are ``to
take/steal'', ``to attain'', ``to subscribe'' and ``to reserve''.  The
database gives one or more case frame(s) associated with the verbs for
each of their senses. In Japanese, a complement of a verb, which is a
constituent of the case frame of the verb, consists of a noun phrase
(case filler) followed by a case marker suffix such as {\it ga\/}
(nominative) or {\it wo\/} (accusative). The database has an example
set of case fillers for each case.  As shown in figure \ref{fig:toru},
examples of a complement can be considered as an extensional
description of the selectional restriction on it.

The task considered in this paper is ``to interpret'' a verb in an
input sentence, i.e. to choose one sense from a set of candidate
senses of the verb.  Given an input sentence, Kurohashi's method
interprets the verb in the input by computing semantic similarity
between the input and examples.  For this computation, Kurohashi's
method experimentally uses the Japanese word thesaurus {\it
  Bunruigoihyo\/}~\cite{bgh:64}.  As with most thesauruses, the length
of the path between two words in {\it Bunruigoihyo} is expected to
reflect the similarity between them.  Figure \ref{fig:bgh} illustrates
a fragment of {\it Bunruigoihyo\/} including nouns associated with the
nominative and the accusative in figure \ref{fig:toru} respectively.

\begin{figure}[htbp]
  \small
  \leavevmode
  \begin{minipage}[t]{.47\textwidth}
    \centering
    \parbox{\textwidth}{ \treerootf{human}
      {\branch{}{\branch{}{\branch{} {\LEAF{he} \LEAF{she}}}}
        \branch{}{\branch{}{\branch{} {\LEAF{father} \LEAF{brother}}}}
        \branch{}{\branch{}{\branch{} {\LEAF{client}}}}
        \branch{}{\branch{}{\branch{} {\LEAF{passenger}}}} \branch{}
        {\branch{}{\branch{}{\LEAF{assistant}}}
          \branch{}{\branch{}{\LEAF{company president}}} {\branch{}
            {\branch{}{\LEAF{student}} {\branch{}{\LEAF{secretary}}
                {\branch{}{\LEAF{pickpocket}}}}}}}
        \branch{}{\branch{}{\branch{} {\LEAF{group}}}}} } (nominative)
  \end{minipage}
  \hfill
  \begin{minipage}[t]{.47\textwidth}
    \centering
    \parbox{\textwidth}{ \treerootf{thing}
      {\branch{}{\branch{}{\branch{}{\branch{}{\LEAF{man}}}}}
        \branch{}{\branch{}{\branch{}{\branch{}{\LEAF{horse}}}}}
        \branch{}{\branch{}{\branch{}{\branch{}{\LEAF{idea}}}}
          \branch{}{\branch{}{\branch{} {\LEAF{newspaper}
                \LEAF{journal} \LEAF{magazine}}}}
          \branch{}{\branch{}{\branch{}{\LEAF{qualification}}}}
          \branch{}{\branch{}{\branch{}{\LEAF{license}
                \LEAF{visa}}}}
          \branch{}{\branch{}{\branch{}{\LEAF{money}}}}}
        \branch{}{\branch{}{\branch{}{\branch{}{\LEAF{wallet}}}}
          \branch{}{\branch{}{\branch{}{\LEAF{ticket}}}}
          \branch{}{\branch{}{\branch{}{\LEAF{airplane}}}
            {\branch{}{\branch{}{\LEAF{sleeping car}}}}}
          \branch{}{\branch{}{\branch{}{\LEAF{room}}}}
          \branch{}{\branch{}{\branch{}{\LEAF{toy}}}}}}}
    (accusative)
  \end{minipage}
  \caption{Showing a fragment of {\it Bunruigoihyo\/}}
  \label{fig:bgh}
\end{figure}

Let us take the example sentence (1).
\begin{list}{}{\setlength{\leftmargin}{0mm}}
\item
  \begin{tabular}{cccc}
    (1) & {\it hisho\/} {\it ga\/} & {\it shindaisha\/} {\it wo\/} &
    {\it toru}. \\ \multicolumn{2}{c}{(secretary-NOM)} & (sleeping
    car-ACC) & (?)
  \end{tabular}
\end{list}
In this example, it may be judged according to figure \ref{fig:bgh}
that {\it hisho\/} (``secretary'') and {\it shindaisha\/} (``sleeping
car'') in (1) are semantically similar to {\it joshu\/}
(``assistant'') and {\it hikouki\/} (``airplane''), respectively,
which are examples that collocate with {\it toru\/} (``to reserve'').
As such, the sense of {\it toru\/} in (1) can be interpreted as ``to
reserve''.  However, in Kurohashi's method, several useful properties
for verb disambiguation are missing:
\begin{enumerate}
\item Intuitively speaking, the contribution of the accusative to verb
  sense disambiguation is greater than that of the nominative with the
  case of verb ``toru''.
\item The selectional restriction of a certain case is stronger than
  those of others. For example, in the accusative, the selectional
  restriction of ``to subscribe'' is stronger than that of ``to
  take/steal'' which allows various kinds of objects as its case
  filler.
\end{enumerate}
In this paper, we improve on Kurohashi's method by introducing a
formalization of these notions, and report the result of a comparative
experiment.

\section{Motivation}
\label{sec:motivation}

Property 1 in section \ref{sec:intro} is exemplified by the input
sentence (2).
\begin{list}{}{\setlength{\leftmargin}{0mm}}
\item
  \begin{tabular}{cccc}
    (2) & {\it shachou\/} {\it ga\/} & {\it shuukanshi\/} {\it
      o\/} & {\it toru}. \\ & (company president-NOM) & (magazine-ACC)
    & (?)
  \end{tabular}
\end{list}
The nominative, {\it shachou\/} (``company president''), in (2) is
found in the ``to attain'' case frame of {\it toru\/} and there is no
other co-occurrence in any other sense of {\it toru\/}; therefore, the
nominative supports an interpretation ``to attain''.  On the other
hand, the accusative, {\it shuukanshi\/} (``magazine''), is most
similar to the examples included in the accusative of the ``to
subscribe'' and therefore the accusative supports another
interpretation ``to subscribe''. Although the most plausible
interpretation here is actually the latter, Kurohashi's method would
choose the former since (a) the degree in which the nominative
supports ``to attain'' happens to be stronger than the degree in which
the accusative supports ``to subscribe'', and (b) their method always
relies equally on the similarity in the nominative and the accusative.
However, in the case of {\it toru}, since the semantic range of nouns
collocating with the verb in the nominative does not seem to have a
strong delinearization in a semantic sense, it would be difficult, or
even risky, to properly interpret the verb sense based on the
similarity in the nominative. In contrast, since the ranges are
diverse in the accusative, it would be feasible to rely more strongly
on the similarity in the accusative.  This argument can be illustrated
as in figure \ref{fig:discussion}, in which the symbols ``{\tt 1}''
and ``{\tt 2}'' denote example case fillers of different case frames
respectively, and an input sentence includes two case fillers denoted
by ``x'' and ``y''.

\vspace{-4mm}
\begin{figure}[htbp]
  \begin{center}
    \leavevmode 
        
         \epsfile{file=06fig3new.eps}
  \end{center}
 \vspace{-1mm}
  \caption{The semantic ranges of the nominative and accusative
    with verb {\it toru\/}}
  \label{fig:discussion}
\end{figure}

\vspace{-2mm}
The figure shows the distribution of example case fillers denoted by
those symbols in a semantic space, where the semantic similarity
between two case fillers is represented by the physical distance
between two symbols.  In the nominative, since ``{\tt x}'' happens to
be much closer to a ``{\tt 2}'' than any ``{\tt 1}'', ``{\tt x}'' may
be estimated to belong to the range of ``{\tt 2}''s although ``{\tt
  x}'' actually belongs to both sets of ``{\tt 1}''s and ``{\tt 2}''s.
In the accusative, however, ``{\tt y}'' would be properly estimated to
belong to ``{\tt 1}''s due to the mutual independence of the two
accusative case filler sets, even though examples did not fully cover
each of the ranges of ``{\tt 1}''s and ``{\tt 2}''s. Note that this
difference would be critical if example data were sparse.  This
argument suggests that we introduce the degree of case contribution to
verb sense disambiguation.  One may argue that this property can be
generalized as the notion that the system always relies only on the
similarity in the accusative for verb sense disambiguation. Although
some typical verbs show this general notion, it is not guaranteed for
any kind of verb. Our approach, which computes the degree of
contribution for each verb respectively, can handle exceptional cases
as well as typical ones.

Property 2 is exemplified by the input sentence (3).
\begin{list}{}{\setlength{\leftmargin}{0mm}}
\item
  \begin{tabular}{cccc}
    (3) & {\it oniisan\/} {\it ga\/} & {\it omocha\/} {\it wo\/} &
    {\it toru}. \\ & (brother-NOM) & (toy-ACC) & (?)
  \end{tabular}
\end{list}
In (3) the most plausible interpretation of {\it toru\/} is ``to
steal''.  The nominative does not give much information for
interpreting the verb for the same reason as example (2). In the
accusative, the database in figure \ref{fig:toru} has two example case
fillers that are equally similar to {\it omocha\/} (``toy''): {\it
  saifu\/} (``wallet'') and {\it hikouki\/} (``airplane''). These
examples equally support two different interpretations: ``to steal''
and ``to reserve'', which means that the verb sense ambiguity still
remains.  Here, one may notice that since the accusative examples in
the case frame of {\it toru\/} (``to reserve'') are less diverse in
meaning than the other case frames, the selec- tional restriction on the
accusative of {\it toru\/} (``to reserve'') is relatively strong, and
thus that it can be estimated to be relatively implausible for {\it
  omocha\/} (``toy'') to satisfy it.  If such reasoning is correct,
given that the examples in the accusative of {\it toru\/} (``to
steal'') are most widely distributed, the input verb can be
interpreted as ``to steal''.  The consideration above motivated us to
introduce the notion of relative strength of selectional restriction
into our example-based verb sense disambiguation method.

\section{Algorithm}
\label{sec:algorithm}

\hspace{0.2mm}We\hspace{0.1mm} assume\hspace{0.1mm} that\hspace{0.1mm} inputs\hspace{0.1mm} are\hspace{0.1mm} simple\hspace{0.1mm} sentences, \hspace{0.1mm}each\hspace{0.1mm} one\hspace{0.1mm} of\hspace{0.1mm} which\hspace{0.1mm} consists\hspace{0.1mm} of\hspace{0.1mm} a \hspace{0.1mm}sequence of cases followed by their governing verb.  The task is
to identify the sense of each input verb.  The set of verb senses we
use are those defined in the existing machine readable dictionary
``IPAL''~\cite{ipal:87}, which also contains example case fillers as
shown in figure \ref{fig:toru}.  As well as Kurohashi's method the
similarity between two case fillers, or more precisely the
semantic-head nouns of them, is computed by using {\it
  Bunruigoihyo\/}~\cite{bgh:64}. Following Kurohashi's method, we
define $sim(X,Y)$, which stands for the similarity between words $X$
and $Y$, as in table \ref{tab:kuro}. It should be noted here that both
methods are theoretically independent of what resources are used.

\begin{table}[tbp]
  \caption{The relation between the length of path between two nouns $X$
    and $Y$ ($len(X,Y)$) \\ in {\it Bunruigoihyo\/} and the similarity
    between them ($sim(X,Y)$)}
  \label{tab:kuro}
  \begin{center}
    \leavevmode
    \begin{tabular}{|c|ccccccc|} \hline
      $len(X,Y)$ & 0 & 2 & 4 & 6 & 8 & 10 & 12 \\ \hline
      $sim(X,Y)$ & 11 & 10 & 9 & 8 & 7 & 5 & 0 \\ \hline
    \end{tabular}
  \end{center}
\end{table}

To illustrate the overall algorithm, we replace the illustrative cases
mentioned in section \ref{sec:intro} with a slightly more general case
as in figure \ref{fig:case-frame}. The input is
\{$\Ni{\Ci{1}}$-$\Mi{\Ci{1}}$, $\Ni{\Ci{2}}$-$\Mi{\Ci{2}}$,
$\Ni{\Ci{3}}$-$\Mi{\Ci{3}}$, $\V$\}, where $\Ni{\Ci{i}}$ denotes the
case filler in the case $\Ci{i}$, and $\Mi{\Ci{i}}$ denotes the case
maker of $\Ci{i}$.  The candidates of interpretation for $\V$, which
are $\SSi{1}$, $\SSi{2}$ and $\SSi{3}$, are derived from the database.
The database also gives a set $\EXi{\SSi{i}}{\Ci{j}}$ of case filler
examples for each case $\Ci{j}$ of each sense $\SSi{i}$.  ``---''
denotes that the corresponding case is not allowed.

\begin{figure}[htbp]
  \begin{center}
    \small
    \leavevmode
    \begin{tabular}{|c|ccccc|} \hline
      input & $\Ni{\Ci{1}}$-$\Mi{\Ci{1}}$ &
      $\Ni{\Ci{2}}$-$\Mi{\Ci{2}}$ & $\Ni{\Ci{3}}$-$\Mi{\Ci{3}}$ & &
      $\V$ (?) \\ \hline \hline & $\EXi{\SSi{1}}{\Ci{1}}$ &
      $\EXi{\SSi{1}}{\Ci{2}}$ & $\EXi{\SSi{1}}{\Ci{3}}$ & --- & $\V$
      ($\SSi{1}$) \\ database & $\EXi{\SSi{2}}{\Ci{1}}$ &
      $\EXi{\SSi{2}}{\Ci{2}}$ & $\EXi{\SSi{2}}{\Ci{3}}$ &
      $\EXi{\SSi{2}}{\Ci{4}}$ & $\V$ ($\SSi{2}$) \\ & --- &
      $\EXi{\SSi{3}}{\Ci{2}}$ & $\EXi{\SSi{3}}{\Ci{3}}$ & --- & $\V$
      ($\SSi{3}$) \\ \hline
    \end{tabular}
  \end{center}
  \caption{An input and the database}
  \label{fig:case-frame}
\end{figure}
  
In the course of the verb sense disambiguation process, the system
first discards the candidates whose case frame constraint is
grammatically violated by the input (this parallels Kurohashi's
method).  In the case of figure \ref{fig:case-frame}, $\SSi{3}$ is
discarded because the case frame of $\V$ ($\SSi{3}$) does not
subcategorize the case $\Ci{1}$\footnote{Since IPAL does not
  necessarily enumerate all the possible optional cases, the absence
  of case $\Ci{1}$ from $\V$ ($\SSi{3}$) in the figure may denote that
  $\Ci{1}$ is optional. If so, the interpretation $\SSi{3}$ should not
  be discarded in this stage. To avoid this problem, we use the same
  technique as used in Kurohashi's method. That is, we define several
  particular cases beforehand, such as the nominative, the accusative
  and the dative, to be obligatory, and impose the grammatical case
  frame constraint as above only in those obligatory cases.
  Optionality of case needs to be further explored.}.  In contrast,
$\SSi{2}$ will not be rejected at this step. This is based on the fact
that in Japanese, cases can be easily omitted if they are inferable
from the given context.

Thereafter, the system computes the plausibility of the remaining
candidates of interpretation and chooses the most plausible
interpretation as its output.  In Kurohashi's method, the plausibility
of an interpretation is computed by averaging the degree of similarity
between the input complement and the example complements\footnote
{ $\EXi{\SSi{2}}{\Ci{4}}$ is not taken into consideration in the
  computation since $\Ci{4}$ does not appear in the input.} for each
case as in equation \eq{eq:kuro}, where $P(\SS)$ is the plausibility
of interpreting the input verb as sense $\SS$, and
$SIM(\Ni{\C},\EXi{\SS}{\C})$ is the degree of the similarity between
the input complement $\Ni{\C}$ and example complements
$\EXi{\SS}{\C}$.

\begin{equation}
  P(\SS) = \sum_{c} SIM(\Ni{\C},\EXi{\SS}{\C})
  \label{eq:kuro}
\end{equation}
$SIM(\Ni{\C},\EXi{\SS}{\C})$ is the maximum degree of similarity
between $\Ni{\C}$ and each of $\EXi{\SS}{\C}$ as in equation \eq{eq:sim}.
\begin{equation}
  SIM(\Ni{\C},\EXi{\SS}{\C}) = {\displaystyle \max_{\E \in
      \EXi{\SS}{\C}}} sim(\Ni{\C},\E) \label{eq:sim}
\end{equation}

In our method, on the other hand, for the reason indicated in section
\ref{sec:intro}, we introduce two new factors:
\begin{itemize}
\item case contribution to disambiguation (CCD),
\item relative strength of selectional restriction (RSSR).
\end{itemize}

First, in regard to CCD, we compute the plausibility of an
interpretation by the {\em weighted\/} average of the degree of
similarity for each case as in equation \eq{eq:p}, replacing equation
\eq{eq:kuro}.
\begin{equation}
  P(\SS) = \frac{\textstyle \sum_{\C} SIM(\Ni{\C},\EXi{\SS}{\C})\cdot
    CCD(\C)}{\textstyle \sum_{\C} CCD(\C)} \label{eq:p}
\end{equation}
Here, $CCD(\C)$ is a newly introduced weight, such that $CCD(\C)$ is
greater when the degree of case $\C$'s contribution is higher.

Second, in regard to RSSR, the stronger the selectional restriction on
a case of a case frame is, the less plausible an input complement
satisfies that restriction as mentioned in section \ref{sec:intro}. 
Note here that the plausibility of an interpretation of an input verb
can be regarded as the plausibility that the input complements satisfy
the selectional restriction associated with that interpretation.  This
leads us to replace $SIM(\Ni{\C},\EXi{\SS}{\C})$ in equation \eq{eq:p}
with $PSS(\Ni{\C},\EXi{\SS}{\C})$, which denotes the plausibility that
the case filler $\Ni{\C}$ satisfies the selectional restriction
described by the example case fillers $\EXi{\SS}{\C}$.
\begin{equation}
  P(\SS) = \frac{\textstyle \sum_{\C} PSS(\Ni{\C},\EXi{\SS}{\C})\cdot
    CCD(\C)}{\textstyle \sum_{\C} CCD(\C)} \label{eq:p2}
\end{equation}
From the assumption that $PSS(\Ni{\C},\EXi{\SS}{\C})$ should be
greater for a larger $SIM(\Ni{\C},\EXi{\SS}{\C})$ and lesser relative
strength of the selectional restriction described by $\EXi{\SS}{\C}$,
we can derive equation \eq{eq:pss}.
\begin{equation}
  PSS(\Ni{\C},\EXi{\SS}{\C}) = SIM(\Ni{\C},\EXi{\SS}{\C}) -
  RSSR(\SS,\C) \label{eq:pss}
\end{equation}
Here, $RSSR(\SS,\C)$ denotes the relative strength of the selectional
restriction on a case $\C$ associated with a sense $\SS$.

\section{Computation of CCD and RSSR}
\label{sec:computation}

The degree of case contribution to verb sense disambiguation (CCD) is
computed in the following way.  The degree of contribution of a case
should be high if the semantic range of the example case fillers in
that case is diverse in the case frame (see figure
\ref{fig:discussion}).  Let a certain verb have $n$ senses ($\SSi{1},
\SSi{2}, \ldots, \SSi{n}$) and the set of example case fillers of a
case $\C$ associated with $\SSi{i}$ be $\EXi{\SSi{i}}{\C}$.  Then, the
degree of $\C$'s contribution to disambiguation, $CCD(\C)$, is
expected to be higher if the example case filler sets
\{$\EXi{\SSi{i}}{\C}~|~i = 1, \ldots, n$\} share less elements.  This
can be realized by equation \eq{eq:ccd}.
\begin{equation}
  \begin{array}{l}
    CCD(\C) = {\displaystyle \left(\frac{\displaystyle
        1}{\displaystyle _{\it n\/}C_{2}}\sum_{{\it i\/} = 1}^{{\it
          n\/}-1}\sum_{{\it j\/} = {\it i\/} +
        1}^{{\it n\/}}\frac{\displaystyle
        |\EXi{\SSi{i}}{\C}|+|\EXi{\SSi{j}}{\C}|-2|\EXi{\SSi{i}}{\C}\cap
        \EXi{\SSi{j}}{\C}|}{\displaystyle
        |\EXi{\SSi{i}}{\C}|+|\EXi{\SSi{j}}{\C}|}\right)^\alpha
      \label{eq:ccd} }
  \end{array}
\end{equation}
$\alpha$ is the constant for parameterizing to what extent CCD
influences verb sense disambiguation. When $\alpha$ is larger, CCD
more strongly influences the system's output.  Considering the data
sparseness problem, we do not distinguish two nouns $X$ and $Y$ in
equation \eq{eq:ccd} if $X$ and $Y$ are similar enough, as in equation
\eq{eq:x}.
\begin{equation}
  \label{eq:x}
  \{X\} \cup \{Y\} = \{X\}~~\mbox{\ if\ } sim(X,Y) >= 9
\end{equation}

Relative strength of selectional restriction (RSSR) is computed in the
following way.  The selectional restriction on a case of a case frame
is expected to be strong if the example case fillers of the case are
similar to each other.  Given a set of example case fillers in a case
associated with a verb sense, the strength of the selectional
restriction on that case (SSR) can be estimated by averaging the
similarity between any combination of two elements of that set.  Thus,
given a set $\EXi{\SS}{\C}$ of example case fillers in a case $\C$
associated with a verb sense $\SS$, the SSR of $\C$ associated with
$\SS$ can be estimated by equation \eq{eq:ssr}, where
$\EXii{i}{\SS}{\C}$ is an $i$-th element of $\EXi{\SS}{\C}$, and $m$
is the number of elements in $\EXi{\SS}{\C}$, i.e. $m =
|\EXi{\SS}{\C}|$.
\begin{equation}
  SSR(\SS,\C) = \left\{
\begin{array}{ll}
  \frac{\textstyle \sum_{i = 1}^{m-1}\sum_{j = i + 1}^{m}
    sim(\EXii{i}{\SS}{\C},\EXii{j}{\SS}{\C})}{\textstyle _{m}C_{2}} &
  \mbox{if $m > 1$} \\ \noalign{\vskip 1ex} \mbox{maximum} &
  \mbox{otherwise}
\end{array}
\right. \label{eq:ssr}
\end{equation}
In the case $m = 1$, that is, the case has only one example case
filler, the SSR becomes maximum, because the selectional constraint
associated with the case is highest (following table \ref{tab:kuro},
we assign 11 as the maximum to SSR).  The {\em relative\/} strength of
selectional restriction (RSSR) of a case associated with a verb sense
is estimated by the ratio of the SSR of the case to the summation of
the SSRs of each case associated with the verb sense, as in equation
\eq{eq:rssr} \footnote{Note that, in equation \eq{eq:pss}, while SIM
  is an integer, RSSR ranges in its value from 0 to 1. Therefore, RSSR
  is influential only when several verb senses take the same value of
  SIM for a given case.}.
\begin{equation}
  \label{eq:rssr}
  RSSR(\SS,\C) = \frac{\textstyle SSR(\SS,\C)}{\textstyle \sum_{i}
    SSR(\SSi{i},\C)}
\end{equation}

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

Our experiment compared the performance of the following methods:
\begin{enumerate}
\item the control (Kurohashi's method): equation \eq{eq:kuro}
\item our method (considering CCD): equation \eq{eq:p}
\item our method (considering both CCD and RSSR): equation \eq{eq:p2}
\end{enumerate}
In method (2) and (3), the influence of CCD, i.e. $\alpha$ in equation
\eq{eq:ccd}, was extremely large. We will show the relation between
the variation of $\alpha$ and the performance of the system later in
this section.

The training/test data used in the experiment contained over one
thousand simple Japanese sentences collected from news articles. The
examples given by IPAL were also used as training data\footnote{The
  number of examples given by IPAL was, on average, 3.7 for each case
  of each case frame.}.  Each of the sentences in the training/test
data used in our experiment consisted of one or more complement(s)
followed by one of the ten verbs enumerated in table
\ref{tab:compare}. For each of the ten verbs, we conducted six-fold
cross validation; that is, we divided the training/test data into six
equal parts, and conducted six trials in each of which a different one
of the six parts was used as test data and the rest was used as
training data. We shall call the former the ``test set'' and the
latter the ``training set'', in each case.

When more than one interpretation of an input verb is assigned the
highest plausibility score, any of the above methods will choose as
its output the one that appears most frequently in the training data. 
Therefore, the applicability in each method is 100\%, given that the
applicability is the ratio of the number of the cases where the system
gives only one interpretation, to the number of inputs. Thus, in the
experiment, we compared the precision of each method, which is in our
case equal to the ratio of the number of correct outputs, to the
number of inputs.

Since the performance of any corpus-based method depends on the size
of training data, we first investigated how the precision of each
method was improved as the training data increased. In this, we
initially used only the examples given by IPAL, and progressively
increased the size of the training data used, by considering an extra
part of the training set (five parts of the total six data portions
used) at each iteration, until finally taking all five parts in the
training of our system.  The results are shown in figure
\ref{fig:plot}, in which the x-axis denotes the ratio of the data used
from the training set, to the total size of the training set.

\begin{figure}[htbp]
  \begin{center}
    \leavevmode \epsfile{file=06fig5new.eps}
  \end{center}
  \caption{The precision of each method, for each size of training data}
  \label{fig:plot}
\end{figure}

What can be derived from figure \ref{fig:plot} are the following. 
First, as more training data was considered, the precision got higher
for each method. Second, the consideration of CCD, i.e. case
contribution to verb sense disambiguation, improved on Kurohashi's
method regardless of the size of training data. Given the whole
training set, the precision improved from 75.2\% to 82.4\% (7.2\%
gain).  Third, the introduction of the notion of RSSR did not further
improve on the method using only CCD.

Table \ref{tab:compare} shows the performance for each verb on using
the whole training set.  The column of ``lower bound'' denotes the
precision gained in a naive method such that the system always chooses
the interpretation most frequently appearing in the training
data~\cite{gale:92}.  The column of ``two highest CCDs'' gives the two
highest CCD values from the cases for each verb, which are calculated
using whole training set.

\begin{table}[htbp]
  \caption{Performance for each verb \\ ({\it ga\/}: nominative, {\it
      ni\/}: dative, {\it wo\/}: accusative, {\it kara\/}: locative, {\it
      de\/}: instrumental)}
  \begin{center}
    \leavevmode
    \begin{tabular}{|c||c|c|c||ll||c|c|} \hline
      & data & \# of & lower & & &
      \multicolumn{2}{c|}{precision (\%)} \\ \cline{7-8} verb & size &
      candidates & bound (\%) & \multicolumn{2}{c||}{two highest CCDs}
      & Kurohashi & CCD \\ \hline \hline
      {\it ataeru\/} & 136 & 4 & 66.9 & {\it wo\/} (0.98) & {\it ga\/}
      (0.86) & 77.2 & 86.0 \\ \hline
      {\it kakeru\/} & 160 & 29 & 25.6 & {\it wo\/} (0.99) & {\it ni\/}
      (0.98) & 66.3 & 76.9 \\ \hline
      {\it kuwaeru\/} & 167 & 5 & 53.9 & {\it wo\/} (0.98) & {\it ni\/}
      (0.95) & 82.6 & 88.0 \\ \hline
      {\it noru\/} & 126 & 10 & 45.2 & {\it ni\/} (0.96) & {\it ga\/}
      (0.92) & 82.5 & 81.0 \\ \hline
      {\it osameru\/} & 108 & 8 & 25.0 & {\it wo\/} (0.95) & {\it ni\/}
      (0.94) & 73.2 & 70.4 \\ \hline
      {\it tsukuru\/} & 126 & 15 & 19.8 & {\it de\/} (1.0) & {\it wo\/}
      (0.98) & 59.2 & 84.9 \\ \hline
      {\it toru\/} & 84 & 29 & 26.2 & {\it kara\/} (1.0) & {\it wo\/}
      (0.99) &  56.0 & 71.4 \\ \hline
      {\it umu\/} & 90 & 2 & 81.1 & {\it wo\/} (1.0) & {\it ga\/}
      (0.94) & 100 & 98.9 \\ \hline
      {\it wakaru\/} & 60 & 5 & 48.3 & {\it ga\/} (0.96) & {\it ni\/}
      (0.70) & 65.0 & 70.0 \\ \hline
      {\it yameru\/} & 54 & 2 & 59.3 & {\it wo\/} (1.0) & {\it de\/}
      (0.71) & 96.3 & 96.3 \\ \hline \hline
      total & 1111 & --- & 43.7 & \multicolumn{2}{c|}{---} & 75.2 & 82.4
      \\ \hline
    \end{tabular}
  \end{center}
  \label{tab:compare}
\end{table}

Finally, let us see to what extent we should allow CCD to influence
verb sense disambiguation. Figure \ref{fig:ccd} shows the performance
with the parametric constant $\alpha$ in equation \eq{eq:ccd} set to
various values. $\alpha = 0$ corresponds with Kurohashi's method, in
which CCD is never considered. As shown in figure \ref{fig:ccd}, the
stronger influence we allow CCD to have, the better performance we
gain.

\begin{figure}[htbp]
  \begin{center}
    \leavevmode \epsfile{file=06fig6new.eps}
    
  \end{center}
  \caption{The relation between the degree of CCD and precision}
  \label{fig:ccd}
\end{figure}

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

In this paper, we proposed a new example-based method for verb sense
disambiguation, which improved the performance of the existing methods
by considering the degree of case contribution to verb sense
disambiguation.

The performance of our method significantly depends on the method of
assigning degree of similarity to a pair of case fillers.  Since {\it
  Bunruigoihyo} is fundamentally based on human intuition, it does not
reflect the similarity between a pair of case fillers computationally. 
Proposed methods of word clustering ~\cite[etc.]{tokunaga:95} can
potentially be used in conjunction with our method to overcome this
human reliance.

In our current implementation, we consider the collocation between
case fillers and verbs, but ignore the combination of case fillers. 
Instead of a database as in figure \ref{fig:toru}, we could store a
set of combinations of example case fillers, e.g. the combination of
{\it suri\/} (``pickpocket'') and {\it saifu\/} (``wallet''), but not
that of {\it suri\/} and {\it otoko\/} (``man'').  However, this way
of data storage would require the collection of a much larger number
of examples than the current method.  This issue needs to be further
investigated.

\acknowledgment

The authors would like to thank Dr. Manabu Okumura (JAIST, Japan), Dr. 
Michael Zock (LIMSI, France) and Mr. Timothy Baldwin (TITech, Japan)
for their comments on the earlier version of this paper.

\bibliographystyle{theapa}
\bibliography{myeng}

\begin{biography}

\biotitle{}

\bioauthor{Atsushi Fujii} { He is a Ph.D. student of Department of
  Computer Science, Tokyo Institute of Technology. He received the
  B.S.  and the M.S. degrees from Tokyo Institute of Technology in
  1993 and 1995, respectively. His current interest is in natural
  language processing.  }

\bioauthor{Kentaro Inui} { He is a research associate of Department of
  Computer Science, Tokyo Institute of Technology. He received the
  B.S.  degree in 1990, the M.S. degree in 1992, and the Dr. Eng. 
  degree in 1995 from Tokyo Institute of Technology. His current
  interest is in natural language processing.  }

\bioauthor{Takenobu Tokunaga} { He is an associate professor of
  Department of Computer Science, Tokyo Institute of Technology. He
  received the B.S.  degree in 1983 from Tokyo Institute of
  Technology, the M.S. and the Dr. Eng. degrees from Tokyo Institute
  of Technology in 1985 and 1991, respectively. His current interests
  are natural language processing, information retrieval.  }

\bioauthor{Hozumi Tanaka} { He is a professor of Department of
  Computer Science, Tokyo Institute of Technology. He received the
  B.S. degree in 1964 and the M.S. degree in 1966 from Tokyo Institute
  of Technology. In 1966 he joined in the Electro Technical
  Laboratories, Tsukuba. He received the Dr. Eng. degree in 1980. He
  joined in Tokyo Institute of Technology in 1983. He has been engaged
  in artificial intelligence and natural language processing research.
  }


\bioreceived{Received}
\bioaccepted{Accepted}

\end{biography}

\end{document}
