\documentclass{llncs}
\usepackage{epsfig}

\begin{document}

\title{Information Retrieval by Means of Word Sense Disambiguation}

\author{L. Alfonso Ure\~na\inst{1}, J.M. G\'omez\inst{2} and M. de Buenaga\inst{2}}


\institute{Dpto. de Inform\'atica, Universidad de Ja\'en\\ Avda. Madrid 35, 23071 Ja\'en, Spain,\\
\email{laurena@ujaen.es},
\\ \and Dpto. de Inteligencia Artificial, Universidad Europea - CEES\\
 Villaviciosa de Od\'on, 28670 Madrid, Spain, \\ \email{\{jmgomez,buenaga\}@dinar.uem.es}}


\authorrunning{L. Alfonso Ure\~na et al.}

\maketitle

\begin{abstract}
The increasing problem of information overload can be reduced by the improvement of information access tasks like
Information Retrieval. Relevance Feedback plays a key role in this task, and is typically based only on the
information extracted from documents judged by the user for a given query. We propose to make use of a thesaurus
to complement this information to improve RF. This must be done by means of a Word Sense Disambiguation process
that correctly identifies the suitable information from the thesaurus {\sc WordNet}. The results of our
experiments show that the utilization of a thesaurus requires Word Sense Disambiguation, and that with this
process, Relevance Feedback is substantially improved.
\end{abstract}

\section{Introduction}

Information access methods must be improved to overcome the information overload that most professionals face
nowadays. Information access tasks, like Information Retrieval (IR), help the users to access a great amount of
text they find in the Internet and their organizations. For instance, about 90{\%} of the information in
corporations exists in the form of text \cite{oracle}.

In a typical IR environment, users perform a series of iterative searches refining the query after each search.
Many IR systems can automatically refine the user query making use of a set of documents that have been shown to
the user, and that he or she has marked as relevant or not relevant. This Relevance Feedback (RF) process usually
improves the quality of the search results.

The RF process is usually based only on the use of documents retrieved by the system and judged by the user. This
information can be complemented with other information extracted from additional resources like {\em thesauri}. In
this work, we explore the utilization of the lexical database {\sc WordNet} to complement documents' information
for RF.

Our experiments demonstrate that the use of {\sc WordNet} can improve RF results when a Word Sense Disambiguation
(WSD) process is applied. The raw data obtained from {\sc WordNet} must be refined by a sense identification
process for them to be effective. For automatically disambiguating query terms, more information than the query
itself is required, and provided in the form of the documents judged by the user in a RF setting. We have applied
a WSD algorithm based on the integration of resources that enables us to use {\sc WordNet} for RF.

The results of our experiments show that: first, using {\sc WordNet} without WSD to complement documents'
information decreases RF perfomance; and secondly, using WSD applied to {\sc WordNet} information substantially
improves RF based on the information of documents.

This paper is organized as follows. First we describe the RF approach used in this work. After that, the use of
{\sc WordNet} and WSD for RF is presented. Next, we describe our experiments and results. Finally, the conclusions
of our work are shown.

\section{Relevance Feedback by Query Expansion}

In most retrieval situations, it is customary to conduct searches iteratively as a sequence of partial search
operations, which allows the results of earlier searches to be used to improve the output of later searches. One
possibility consists of asking the user the relevance of certain documents retrieved in earlier search operations,
and using these assessments to construct improved query formulations. This process, known as Relevance Feedback,
has been shown experimentally to improve retrieval effectiveness greatly \cite{salton83}.

The most popular model for Information Retrieval is the Vector Space Model (VSM). In this framework, it has been
demonstrated that the {\em Ide dec-hi} RF method was the best performing one \cite{salton90}. This method is based
on expanding the original query with terms from retrieved documents, using all the ones considered relevant by the
user, and the first non-relevant document.

When evaluating RF effectiveness, it is preferrable to employ the residual collection method. For a given query,
the first $n$ documents retrieved are examined to assess relevance. Then, the query formulation is improved using
those documents, and a new search using the new query is performed over the document collection, excluding the
first $n$ documents retrieved for the previous query. This way, we can avoid the unfair and unrealistic situation
in which already seen documents can be retrieved again, biasing the results to be much better than the original
ones.

\section{Using Word Sense Disambiguation in Relevance Feedback}

The Query Expansion process described earlier is based only on the use of the documents retrieved. Nevertheless,
other resources like {\em thesauri} can be used to complement the information contained in documents
\cite{salton83}. An example of advanced thesaurus is the lexical database {\sc WordNet} \cite{miller95}, which has
been successfully employed in other classifications tasks like Text Categorization \cite{buenaga97}. In RF, and
for every word sense in a query, a set of synonyms can be extracted from {\sc Wordnet} and used to complement the
documents' information obtained from the previous query.

Unfortunately, the incorporation of many heterogeneous words can impact negatively on the RF perfomance. This is
caused by the great number of senses a word can have. We would not like to retrieve documents concerning ``river''
when we perform a query like ``bank'' to know about finantial interests. We require a WSD process to identify the
correct sense of the words occurring in the query in order to effectively use a thesaurus. This is just an example
of a Natural Language Processing task where WSD can improve the performance of the system, among others like Text
Categorization \cite{buenaga97}, Cross-Language Information Retrieval \cite{grefenstette98}, Information
Extraction, or Machine Translation \cite{kilgarriff97}.

The lexical database {\sc WordNet} has been used in IR before, but for it to be useful is essential to apply WSD
\cite{voorhees93}. In a general IR setting, the information of the query words is not enough to identify word
senses, but in RF we can take advantage of the retrieved documents as an additional context to perform an
effective WSD process.

In the latest years, many WSD approaches have been proposed, which can be classified according to the knowledge
sources they make use of. Some approaches are based on the utilization of some kind of lexicon or lexical database
\cite{xiaobin95}. Other people make use of unlabelled \cite{pedersen97} or semantically labelled \cite{bruce94}
text corpora as a training collection. Finally, recent works propose the combination of several knowledge sources
like lexical databases, text corpora, heuristics, collocations, etc. for WSD \cite{wilks98}. We follow the latter
approach, combining the utilization of the lexical database {\sc WordNet}, and the semantically-tagged text corpus
{\sc SemCor} \cite{miller93} as described in \cite{urena00}.

The main idea of our WSD method is taking advantage of {\sc WordNet} information as an initial base for refining
the representation of word senses through a learning algorithm. For instance, the Rocchio and the Widrow-Hoff
learning algorithms admit the definition of an initial representation of classes to be learned. A set of {\sc
WordNet} synonyms are extracted and used as initial representation of each word sense. Then, the learning
algorithm is applied taking as input a collection of labeled data ({\sc SemCor}) to refine the initial
representation of word senses, obtaining better results in final tagging of new words than the use of any of the
resources alone \cite{urena00}. The senses of new words (the query words) can be identified using the context of
documents where they occur, that happen to be the retrieved documents in the previous query.

As a concluding remark, we can observe that the utilization of WSD in other Natural Language Processing tasks like
RF is a natural and interesting way of evaluating WSD algorithms. WSD can hardly be considered an independent
task, and WSD techniques should be compared in the framework of the task where WSD is being applied. Then, a WSD
approach is better than others when the task where it is applied in, is improved by that approach more than by
others. This indirect evaluation must complement the direct, standalone evaluation of WSD approaches.

\section{Evaluation and Discussion of Results}

For the experiments developed in this paper, we have employed the IR system Smart \cite{salton83}. This system is
a well known standard that implements the RF option described erlier in this paper. The number $n$ of documents
considered in the RF process is $15$. Additionaly, a set of $5.000$ documents has been extracted from the Wall
Street Journal corpus in the IR test collection TREC, widely used in IR system evaluation \cite{harman96}. We have
also randomly selected a set of 50 queries (topics) among the first hundred, each one with at least one relevant
document in the subsed selected from the Wall Street Journal corpus.

The thesaurus employed in this work is the lexical database {\sc WordNet} \cite{miller95}. Among the several
lexical and concept relations in {\sc WordNet}, we have used only the synonymy relation.

The VSM employed promotes a recall/precision based evaluation. Recall is defined as the number of relevant
documents retrieved by the system over the number of relevant documents in the collection. Precision is defined as
the number of relevant documents retrieved by the system over the number of documents retrieved. These metrics are
calculated by a special module of Smart. Precision is calculated at the eleven levels of recall $0.0$, $0.1$,
$0.2$, \ldots , $1.0$, and averaged over them. Also the average over the three levels $0.2$, $0.5$ and $0.8$ is
calculated.

\begin{table}[h]
\caption{Precision averaged over the 11 standard levels of recall, and over the three levels $0.2$, $0.5$ and
$0.8$, for the initial run and the different queries constructed by the RF process} \centering
\begin{tabular}{|c|c|c|c|c|}
\hline & \multicolumn{2}{|c|}{Original} &
\multicolumn{1}{|c|}{Expanded} &
\multicolumn{1}{|c|}{Expanded+WSD}\\

& \multicolumn{2}{|c|}{Query} & \multicolumn{1}{|c|}{Query} &
\multicolumn{1}{|c|}{Query}\\ \hline \multicolumn{1}{|c|}{Level} &
{\it initial run} & {\it feedback} & {\it feedback} & {\it
feedback} \\ \hline

11-pt average: & 0,1094 & 0,1853 & 0,1693 & 0,2088 \\ \% change: &
& 69,4 & 54,75 & 84,73\\

3-pt average: & 0,1106 & 0,1894 & 0,1719 & 0,2176 \\\% change: &
& 71,20 & 55,42& 96,74 \\ \hline
\end{tabular}
\label{table1}
\end{table}

The results of our experiments are presented in Table \ref{table1} and Figure \ref{fig1}. The Table \ref{table1}
shows the precision averages over the eleven and three recall levels for: the original query; the RF process based
only on documents; the RF process based on documents and thesaurus without disambiguation; and the RF process
based on documents and thesaurus with disambiguation. The Figure \ref{fig1} shows the four approaches in a typical
recall/precision graph obtained from the precision at the eleven recall levels.

\begin{figure}[h]
\centerline{\epsfig{file=figure1.eps,width=12cm}} \caption{Recall/precision graph for the initial run and the
different queries expanded with documents, and synonyms with and without WSD} \label{fig1}
\end{figure}

The experiments results presented in Table \ref{table1} and Figure \ref{fig1} show that:

\begin{itemize}

\item Using a thesaurus to complement the information of documents in a
RF process ussually performs worse than using only the documents. The average precision shows a drop of $15$\% and
$25$\%. This is caused by the ambiguities in the query words and the high number of senses, and the great number
of synonyms extracted from {\sc WordNet}.

\item Using a thesaurus and a WSD algorithm to complement the
documents information leads to a substantial improvement in the perfomance. The average precision exhibits an
improvement of $15$\% and $25$\%. The reasons for this are the accuracy of the WSD algorithm and the restriction
of words obtained from the thesaurus to those strictly needed.

\end{itemize}

The set of words extracted from the retrieved documents for the query expansion process is complemented by a set
of precise and informative words obtained from the thesaurus, increasing the amount and quality of information
available for constructing the new query.

These results also show that the disambiguation method employed in this work is as effective as to be of practical
use. A direct evaluation was performed and reported elsewhere \cite{urena98}, showing that the WSD was very
effective. These indirect results complement the direct ones.

\section{Conclusions}

In this paper, we have presented an approach that integrates the use of documents and thesaurus information for
Relevance Feedback. The process is based on the utilization of a Word Sense Disambiguation algorithm that
effectively takes advantage of the information extracted from the lexical database {\sc WordNet} for Relevance
Feedback. The results of our experiments show that making use of {\sc WordNet} improves Relevance Feedback only
when performing a Word Sense Disambiguation process.

As a conclusion, we present an advance in the RF task that helps to alleviate the information overload problem.
Also, we outline an evaluation model for WSD approaches based on the evaluation of the task they are applied in.

\bibliographystyle{plain}
\bibliography{tsd2000}

\end{document}
