\documentclass[letterpaper,twoside,11pt]{article}
%\documentstyle[jair,twoside,11pt,theapa]{article}
\usepackage{jair}
\usepackage{theapa}
\input epsf
\usepackage[dvips]{graphicx}
\usepackage[latin1]{inputenc}

\jairheading{15}{2001}{263-287}{3/01}{10/01}
\ShortHeadings{Computational Approach to Anaphora Resolution in
Spanish Dialogues} {Palomar  \& Mart\'{\i}nez-Barco}
\firstpageno{263}


\begin{document}

\title{Computational Approach to Anaphora Resolution\\ in Spanish Dialogues}


%\author{Manuel Palomar and Patricio Mart\'{\i}nez-Barco\\
%{\normalsize Departamento de Lenguajes y Sistemas Inform\'aticos\\
%Universidad de Alicante \\ Carretera de San Vicente del Raspeig -
%Alicante - Spain \\ Tel. +34965903653 Fax. +34965909326\\
%\{mpalomar, patricio\}@dlsi.ua.es} }


\author{\name Manuel Palomar \email mpalomar@dlsi.ua.es \\
       \addr Dept. Lenguajes y Sistemas Inform\'aticos\\
       Universidad de Alicante\\
       Alicante, SPAIN
       \AND
       \name Patricio Mart\'{\i}nez-Barco \email patricio@dlsi.ua.es \\
        \addr Dept. Lenguajes y Sistemas Inform\'aticos\\
       Universidad de Alicante\\
       Alicante, SPAIN}


\maketitle

\begin{abstract}
This paper presents an algorithm for identifying noun-phrase
antecedents of pronouns and adjectival anaphors in Spanish
dialogues. We believe that anaphora resolution requires numerous sources
of information in order to find the correct antecedent of the
anaphor. These sources can be of different kinds,
e.g., linguistic information, discourse/dialogue structure
information, or topic information. For this reason, our algorithm
uses various different kinds of information (hybrid information). The
algorithm is based on linguistic constraints and preferences and
uses an anaphoric accessibility space within which the algorithm
finds the noun phrase. We present some experiments related to this
algorithm and this space using a corpus of 204 dialogues. The
algorithm is implemented in Prolog. According to this study,
95.9\% of antecedents were located in the proposed space, a
precision of 81.3\% was obtained for pronominal anaphora
resolution, and 81.5\% for adjectival anaphora.

\end{abstract}


\section{Introduction}

Anaphora resolution is one of the most active areas of research in
Natural Language Processing (NLP). The comprehension of anaphora
is an important process in any NLP system, yet it is among the
toughest problems in computational linguistics and NLP. According
to Hirst \citeyear{Hirst81}:

\begin{quote}
\emph{Ana\-pho\-ra, in discourse, is a device for making an
abbreviated reference (containing fewer bits of disambiguating
information, rather than being lexically or phonetically shorter)
to some entity (or entities) in the expectation that the receiver
of the discourse will be able to dis\-abbreviate the reference
and, thereby, determine the identity of the entity.}
\end{quote}

The reference to an entity (e.g., a
pronoun) is generally called an \emph{anaphor}, the entity to which the anaphor refers is its
\emph{referent}, and the previous reference to the same entity is the
anaphor's \emph{antecedent}. For instance, in the statement \emph{``John$_i$ ate an
apple. He$_i$ was hungry''}, the pronoun \emph{he} is the anaphor
and the noun \emph{John} is the antecedent.

An anaphoric problem can be described as lying somewhere between
the resolution and the generation of anaphora, the former term
being the dis\-abbreviating of the reference and the latter being
the abbreviating form of the reference to an entity. This paper
focuses exclusively on the resolution of anaphora and not on their
generation. Anaphora can be classified in many different ways,
depending upon the particular criteria one chooses to employ.
Regarding the element that carries out the reference (the
anaphor), for example, clear distinctions should be made between
pronominal anaphora, adjectival anaphora, definite descriptions,
one-anaphora, surface-count anaphora, verbal-phrase anaphora, and
time and/or location references. This paper focuses on the
resolution of pronominal and adjectival anaphora.\footnote{We have
dealt exclusively with pronominal and adjectival anaphora because
they appeared most frequently in the dialogues we evaluated, but
our algorithm can easily be extended to other kinds of anaphora.}

It is widely agreed that the process of resolving
anaphora in natural language texts may be supported by a variety of
strategies that employ different kinds of knowledge. By different
kinds of knowledge we mean the various sources of information
usually employed for anaphora resolution, including morphological agreement, syntactic
parallelism, semantic information, discourse structure, topical
knowledge, and so on.

Natural language processing (NLP), and, specifically, anaphora
resolution, uses many resources and sources of
information for two reasons: (1) numerous
resources are available to the scientific community; and (2) humans employ
many sources of information in order to resolve different
linguistic phenomena.

We present an algorithm that coordinates different forms of
knowledge by distinguishing between linguistic knowledge
(constraints and preferences) and dialogue-structure knowledge
(anaphoric accessibility space). The algorithm identifies the noun
phrase to which a third-person personal or demonstrative pronoun
or adjectival anaphor\footnote{A Spanish adjectival anaphor is a
kind of English one-anaphora where the word {\em one} is omitted.
For example, {\em el rojo (the red [one])}.} refers in a Spanish
dialogue. We call this algorithm ARDi (anaphora resolution in
dialogues). ARDi was implemented in Prolog.

In Section 2 below, we present related work on anaphora resolution
in dialogues. In Section 3, we suggest an annotation scheme for
capturing Spanish dialogue structure. In Section 4, an
accessibility space based on this annotation scheme is defined. In
Section 5, we present the algorithm ARDi. Finally, an experimental study of the
algorithm is presented in Section 6.

\label{intro}

\section{Related work on anaphora resolution in dialogues}
\label{relwork}

For anaphora resolution in dialogues, a proliferation of methods
based on dialogue structure (discourse-oriented approaches) have
been developed. Among these, we should like to especially
acknowledge the work of Grosz \citeyear{Grosz77,Grosz81}, in which
the influence of dialogue structure in anaphora resolution is
justified. Grosz's work focuses specifically on task-oriented
dialogues. Other studies, such as those published by Grosz {\em et
al.}~\citeyear{Grosz83,Grosz95}, present a centering framework as
a model to explain the coherence of local discourse segments in
which the speaker's focus of attention is related to referring
expressions. This model has achieved successful results in
anaphora resolution in monologues, but would require certain
modifications to be successfully applied to dialogues. Along those
lines, Byron and Stent \citeyear{Byron98b} have developed
extensions of the centering method for application to dialogues.
They conclude that centering is as consistent in dialogues as it
is in monologues.

Nevertheless, according to Strube and Hahn \citeyear{Strube99},
the crucial point of the centering model is the candidate list.
Grosz {\em et al.}~\citeyear{Grosz95} state that this list may be
ordered using different factors, but they only use information
about grammatical roles. However, it is difficult to define
grammatical roles in free-word-order languages like German or
Spanish without using semantic information.\footnote{A possible
grammatical role definition in free-word-order languages, e.g.,
subject, direct object, etc., can be recovered to a large extent
by inspecting NP-verb agreement, NP-clitic agreement, and case or
prepositional markers. This task requires adding word-order
heuristics to the parser.}

On the other hand, work carried out by Eckert and Strube
\citeyear{Eckert99b} on English details a method for resolving
pronominal anaphora in dialogues with a precision of 66.2\% and a
recall rate of 68.2\%. This method is based on the distribution of
dialogue acts as an alternative to the centering method.

Furthermore, Mart\'{\i}nez-Barco {\em et
al.}~\citeyear{Martinez99a} emphasize the importance of
discourse-topic knowledge as a complementary method for anaphora
resolution in dialogues in which such knowledge is necessary for
long-distance anaphora resolution.

\section{An annotation scheme for dialogue structure}
\label{annsch}

For successful anaphora resolution in dialogues, we assume that it
is essential to identify dialogue structure. Therefore, we propose
an annotation scheme for Spanish dialogues that is based on work
carried out by Gallardo \citeyear{Gallardo96}, who applies the
theories put forward by Sacks {\em et al.}~\citeyear{Sacks74}
concerning (conversational) turn-taking.

We use an annotation scheme based on these theories for three main
reasons.  First, as it is a general approach to dialogue modeling,
it is applicable to all types of dialogues, including both
task-oriented and information-retrieval-oriented dialogues.
Consequently, the use of such a model as a basis for developing
our anaphor resolution procedure allows us to apply the procedure
to any type of domain, thus offering an advantage over procedures
based on discourse models specific to particular domains. Second,
this annotation scheme can be easily applied to automatic
processes without metalinguistic considerations.  Although in our
work the annotation task has been performed by hand, for
dialogue-based applications in which our procedure might be
embedded (e.g., in dialogue management systems),
annotation tasks must be performed automatically.  Finally, we
wanted to base our own procedure on studies of the influence of
dialogue structure on anaphora resolution that were carried out by Fox
\citeyear{Fox87}, whose approach, in turn, is based on that of
Sacks \emph{et al}.

According to these theories, the basic unit of conversation is the
\emph{move}, which informs the listener about an action, request,
question, etc. Moves are carried out by means of
\emph{utterances}.\footnote{An \emph{utterance} in a dialogue is
equivalent to a sentence in a non-dialogue, although, because of
the lack of punctuation marks, utterances are recognized by means
of speakers' pauses.} And utterances are joined together to become
\emph{turns}.

Since our work was done using spoken dialogues that had been
transcribed, turns are annotated in the texts and utterances are
delimited by the use of punctuation marks or by the ends of turns.
Reading a punctuation mark (., ?, !, ...) allows us to recognize
the end of an utterance. These tasks do not affect the
anaphora-resolution process.

As a result, we propose the following annotation scheme for
dialogue structure:

\begin{description}

\item{\textbf{Turn (T)}} is identified by a change of speaker in
the dialogue; each change of speaker presupposes a new turn. On
this point, we make a distinction between two different kinds of
turns:

\begin{itemize}

\item{An \textbf{intervention turn (IT)}} is one that adds
information to the dialogue. Such turns constitute what is called
\emph{the primary system of conversation}. Speakers use their
interventions to provide information that facilitates the progress
of the topic of conversation. Interventions may be
\textbf{initiatives (IT$_{I}$)} when they formulate invitations,
requirements, offers, reports, etc., or \textbf{reactions
(IT$_{R}$)} when they answer or evaluate the previous speaker´s
intervention. Finally, they can also be \textbf{mixed
interventions (IT$_{R/I}$)}, which is a reaction that begins as a
response to the previous speaker's intervention, and ends as an
introduction of new information.

\item{A \textbf{continuing turn (CT)}} represents an empty turn,
which is quite typical of a listener whose aim is the formal
reinforcement and ratification of the cast of conversational
roles. Such interventions lack information.
\end{itemize}

\item{\textbf{Adjacency pair (AP)}} (also called \textbf{exchange}) is a sequence of turns
headed by an initiation intervention turn (IT$_I$) and ended by a
reaction intervention turn (IT$_R$). This form of anaphora, in
which the reference appears within an adjacency pair, appears to
be very common in dialogues \cite{Fox87}.

\item{\textbf{Topic (TOPIC)}. The topic must
be a lexical item that is referred to frequently. According to
Rocha \citeyear{Rocha98}, four features are taken into account in
the selection of the best candidate for a discourse topic:
frequency, even distribution, position of first token, and
semantic adequacy. A highly frequent element that occurs
intensively in a passage of the dialogue but does not appear for
long stretches is not likely to be a good choice for discourse
topic. In the same way, neither is an element whose first appearance occurs
a long way from the beginning the best choice. Moreover,
semantic adequacy must be considered for the candidate, and it
must be assessed by the annotator}.

\end{description}

Based on the above-mentioned structure, then, the following tags are
considered necessary for dialogue structure annotation:
\textbf{IT$_{I}$}, \textbf{IT$_{R}$}, \textbf{CT}, \textbf{AP},
and \textbf{TOPIC}. The AP and TOPIC tags will be used to define
the anaphoric accessibility space, and the remaining tags will be used
to obtain the adjacency pairs. The IT$_{R/I}$ tag, representing
mixed interventions, is not included since mixed interventions
can be annotated as IT$_{R}$ plus
IT$_{I}$. This task is done in the annotation phase.

An example of an annotated dialogue with tags is presented in
Figure \ref{fig1}. In the dialogue, the identifier (OP)
indicates the turn of a railway company employee, and the identifier (US)
indicates the client's turn.

\begin{figure*}[htpb]
\centering \mbox{}\hrulefill \vspace{-.3em}
  \begin{minipage}{\textwidth} \small
  \begin{sffamily}
    \begin{tabular}{lcll}
    & & & \\
    TOPIC& & &
     tren \\ & & &\emph{(train)}\\
& & & \\
 AP1& & $IT_{I}$ (OP) & informaci\'{o}n de Renfe, buenos
d\'{\i}as. \\ & & &\emph{(Renfe information, good morning.)}\\
    &   &$IT_{R}$ (US) &  hola, buenos d\'{\i}as. \\ & & &{\it(hello, good morning.)}\\
    &   &CT (OP) & hola.  \\ & & &\emph{(hello.)} \\ & & & \\

AP2 &  & $IT_I$ (US) &  me pod\'{e}is decir alg\'{u}n tren que
salga ma\~{n}ana por la tarde para ir \\

& & &a Monz\'{o}n?\\

& & &\emph{(could you tell me about any train that leaves tomorrow
evening} \\

& & &\emph{for Monzon?)}\\

    &   & $IT_R$ (OP)&   s\'{\i}, vamos, mira hay un talgo a
las tres y media de la tarde.\\

& & & \emph{(yes, let's see, there is a talgo at half-past
three.)}\\ & & & \\
 AP3 &     & $IT_I$ (US)&  s\'{\i}, tiene que
ser m\'{a}s tarde. \\ & & &\emph{(yes, it has to be later.)}\\
    &     & $IT_R$ (OP) & m\'{a}s tarde. hay
un intercity a las cinco y media, un expreso a las seis.\\

& & & y media\\
    & & & \emph{(later. there is an intercity at
half-past five, an express} \\

& & &\emph{at half-past six.)}\\ & & &
\\
%\noalign{\vspace {.5cm}}
    AP4&    & $IT_I$ (US) & el de las seis y media ¿llega a
Monz\'{o}n? \\

   & & & \emph{(the one at half-past six, does it go to Monzon?) }\\
    &     AP5\footnote{This adjacency pair is included within AP4.} &  $IT_I$ (OP) & a ver. el de las seis
y media me ha preguntado ¿verdad? \\
   & & & \emph{(let me see. you've
asked about the one at half-past six, right?)}\\
    &      &  $IT_R$ (US) &s\'{\i}. \\ & & &\emph{(yes.)}\\
    &       & $IT_R$ (OP)  &  a las nueve y veinticinco. \\ & & &{\it
(twenty-five past nine.)}\\ & & & \\ AP6    &       & $IT_I$
(US)  & a las nueve y veinticinco est\'{a} en Monz\'{o}n? \\
  & & & \emph{(at twenty-five past nine it is in Monzon?)}\\
 &       &  $IT_R$ (OP)  &s\'{\i} \\ & & &\emph{(yes)}\\
  &       & CT (US)  &vale, pues ya est\'{a}. esto ya es
suficiente. \\
   & & & \emph{(ok, that's it. that's enough for now.)}
\\
 AP7   &       & $IT_I$ (US)  &gracias, ¿eh? \\ & & &\emph{(thank you, eh?)}\\
     &       & $IT_R$ (OP)  & muy bien a usted. hasta luego. \\ & & &\emph{(very well, thanks to you. so long.)}
     \\

    \end{tabular}
    \vspace{.5cm}
  \end{sffamily}
  \end{minipage}
\mbox{}\hrulefill \vspace{-.6em}
  \caption{\label{fig1} Example of an annotated dialogue from {\em Corpus InfoTren: Person}}

\end{figure*}

One of the most important advantages of this annotation scheme is
its compatibility with most of the dialogue-annotation schemes
used in dialogue systems. Notice, for instance, that the adjacency
pairs show the same structure as the \emph{conversational game}
applied to task-oriented dialogues defined in the dialogue
structure by Carletta \emph{et al.}~\citeyear{Carletta97}.
Moreover, our scheme is also compatible with those that are based
on utterance functions, such as the one defined in DAMSL by Allen
and Core \citeyear{Allen97}. DAMSL indicates how utterances are
related to the discourse by means of \emph{forward- and
backward-looking functions}. The interpretation of these functions
builds the adjacency-pair structure. Finally, our topic structure
exhibits the same features as the \emph{transaction} structure of
Carletta \emph{et al.}~or the \emph{task level} defined by Allen
and Core.


\section{Accessibility space proposal}
\label{accspace}

Based upon the above-mentioned annotation, an anaphoric
accessibility space is proposed for Spanish in order to resolve
ana\-phors in the form of personal pronouns, demonstrative
pronouns, and adjectival ana\-phors.

\subsection{Description}

According to Fox \citeyear{Fox87}, the first mention of a referent
in a sequence of contexts is performed with a full noun phrase.
After that, by using an anaphor the speaker displays an
understanding that sequence has not been closed down. We assert
that two different sequences generate most of the ana\-phors to be
found in dialogues: the adjacency pair and the topic scope. The
former generates references to any local noun phrase, and the
latter generates references to the main topic of the dialogue.

Based on this, we propose that the anaphoric accessibility space for any
given anaphor may be defined as the set of noun phrases taken from:

\begin{itemize}
\item the adjacency pair containing the anaphor, plus
\item the adjacency pair preceding the adjacency pair containing the anaphor, plus
\item any adjacency pair including the adjacency pair containing the anaphor,
plus
\item the noun phrase representing the main topic of the dialogue.
\end{itemize}


\subsection{An automatic topic detection proposal}

Several works about automatic topic detection have been
published---Reynar \citeyear{Reynar99}, You\-mans
\citeyear{Youmans91} or Hearst \citeyear{Hearst94}---. In
Mart\'{\i}nez-Barco {\em et al.}~\citeyear{Martinez99a} an
automatic topic detection algorithm as applied to anaphora
resolution is presented.

This algorithm selects noun phrases (NP) occurring before an
anaphor. These NPs are included in a list that is then weighted.
Each time the NP appears in a new turn (frequency), its weight is
increased, and each time the NP does not appear in a new turn
(infrequency), its weight is decreased. According to this
algorithm, the dialogue topic may be determined by its salience,
i.e., by determining the NP with the heaviest weight (high
frequency in a short distance) occurring before an anaphor. In
order to obtain this information (weight), the algorithm uses the
following two coefficients:
\begin{itemize}
\item \textbf{C$_f$}: coefficient of frequency
\item \textbf{C$_i$}: coefficient of infrequency
\end{itemize}
C$_f$ increases the salience of a referring expression when the
entity appears in the current intervention turn. C$_i$ decreases
the salience of expressions that appeared in previous intervention
turns but not in the current one, indicating a loss of importance.
Both coefficients obviously affect the salience of expressions in
reflecting their frequency and their distance from the current
intervention turn where the anaphor has been found. The expression
with the highest salience will be the most favored candidate
antecedent on the whole list and therefore the most relevant topic
for the current intervention turn.

This automatic topic detection method has the following advantage
over other methods: it does not obtain a single topic, but rather a list
of topic candidates ordered by salience. That is important for our
anaphora resolution system because, if the highest-ranked
candidate does not fulfill the relevant constraints, then the next
highest candidate can be tested.

Initially, values of 10 units and 1 unit, respectively, were
assigned to C$_f$ and C$_i$. These values were arrived at
experimentally, but further study could lead to more precise
values.

\section{Anaphora resolution in Spanish dialogues}

In this section, the anaphora resolution algorithm based on a
constraint and preference approach is presented.

\subsection{Constraints and preferences as an approach to anaphora
resolution} \label{conpref}

According to Dahlb\"{a}ck \citeyear{Dahlback91}, there are at
present two basic approaches in anaphora resolution: (1) the
traditional approach, which generally depends upon linguistic
knowledge, and (2) the discourse-oriented approach, in which the
researcher tries to model complex discourse structures and then
uses these structures to resolve anaphora.

Among the traditional approaches, the work of Mitkov
\citeyear{Mitkov98}, Baldwin \citeyear{Baldwin97}, and
Ferr\'{a}ndez {\it et al.}~\citeyear{Ferrandez2000} are all based
on a combination of linguistic knowledge (lexical, morphological,
syntactic, and/or semantic) for the resolution of anaphora. These
approaches apply linguistic knowledge, in the way of constraints
and preferences, following the work of Carbonell and Brown
\citeyear{Carbonell88} and Rich and LuperFoy \citeyear{Rich88}, in
which such systems are proposed as a technique for combining
several information sources.

These approaches are based, intuitively, on the following three
steps: (1) defining an anaphoric accessibility space, (2) applying
constraints, and (3) applying preferences.

A constraint and preference system must define, on the one hand,
the anaphoric accessibility space. That is, it must obtain a list
with all the possible candidate antecedents. On the other hand, the
system must also define the text segments in which the antecedent can
be found. This step has a great importance for the remaining
steps in the process because a definition of the anaphoric accessibility space
that is too narrow results in the exclusion of valid antecedents.
Likewise, a definition of the anaphoric accessibility space that is too
broad results in large candidate lists, with a corresponding
increase in the likelihood of erroneous anaphora resolution.
Usually, anaphora resolution systems based on linguistic knowledge
\cite{Ferrandez2000} define an accessibility space using \emph{n}
previous sentences to the anaphor, where \emph{n} is variable
according to the kind of the anaphora.

Once the list of possible candidates is defined, several
constraints are applied in order to remove incompatible
antecedents. The constraint system consists of conditions that
must be met, and candidates that do not fulfill these conditions
will not be considered possible antecedents for the anaphor.
Lexical, morphological, syntactical, and semantic information are
traditionally used to define the constraints.

Finally, after removing incompatible candidates, if the remaining
list contains more than one antecedent, preferences are applied in
order to choose a single antecedent. In this case, unlike that of
constraints, preferences are associated with likelihood lower than
100\%. Candidates fulfilling a preference, then, have a greater
likelihood of being the antecedent than those not fulfilling it.
The preference system must be designed bearing in mind that only
one candidate must remain at the end. This final candidate will be
proposed as the antecedent for the anaphor. Lexical,
morphological, syntactic, and semantic information are usually
used in order to define the preference system.

The works of Mitkov \citeyear{Mitkov98} and Ferr\'{a}ndez {\it et
al.}~\citeyear{Ferrandez2000} show that anaphora resolution
systems based on constraints and preferences can yield successful
results when applied to non-dialogue texts. However, these works
lack adequate proposals for the anaphoric accessibility space.
Furthermore, these approaches lack consistency in the treatment of
other kinds of texts, for example, dialogues.

\subsection{The anaphora resolution algorithm (ARDi)} \label{algo}

In this section, the intuitive algorithm for anaphora resolution
in spoken dialogue systems (ARDi) is presented. ARDi operates with
syntactic information provided by the SUPP partial parser
\cite{Ferrandez98a}. SUPP is based on a partial representation of
slot unification grammar analysis \cite{Ferrandez2000}. This
partial representation gives some of the utterance constituents,
such as NPs, PPs, verbal chunks, and partial information about
subordinated clauses. Thus, ARDi combines two kinds of knowledge
about dialogues: (1) linguistic knowledge, such as lexical,
morphological, and syntactic knowledge; and (2) knowledge about
the dialogue's structure itself, which is based on the annotation
of adjacency pairs\footnote{The use of adjacency pairs as dialogue
units for anaphora resolution is based on the work of Sacks {\em
et al.}~\citeyear{Sacks74}, in which they suggest that one form of
anaphora which appears to be very common in dialogues is reference
within an adjacency pair.} and knowledge about the topic of the
dialogue (manually annotated). Figure \ref{proced} shows the
anaphora resolution procedure.

\begin{figure}
\centering \mbox{}\hrulefill \vspace{-.3em}
{\small \begin{verbatim}

    Procedure RESOLUTION (A,L(AAS))
    Let ANAPHOR = the anaphor A
    Let AAS = anaphoric accessibility space from A
    Let LIST = a list L(AAS) of all NPs (antecedent candidates)
               from AAS
    For each NP in LIST, apply constrains of morphological
               agreement between NP and ANAPHOR to obtain LIST1
    end for
    For each NP in LIST1, apply constrains of syntactic conditions
               between NP and ANAPHOR to obtain LIST2
    end for
    For all NP in LIST2, apply linguistic and discourse structural
               preferences (in the order described in step 3 below )
               until |LIST2| = 1
    end for
    Return LIST2
    end procedure
\end{verbatim}

} \mbox{}\hrulefill \vspace{-.6em}
    \caption{Anaphora resolution procedure}
    \label{proced}

\end{figure}


ARDi is based, intuitively, on the following three steps:

\begin{enumerate}
\item Obtain all possible antecedents from dialogue structure and topic as follows:
    \begin{enumerate}
    \item take those NPs that are included in the same adjacency pair (AP) as the anaphor, and
    \item take those NPs that are included in the previous AP to that containing the anaphor, and
    \item take those NPs that are included in the most recent unclosed AP containing the AP containing the anaphor, and
    \item take the topic of the dialogue
    \end{enumerate}

\item Discard incompatible antecedents by applying linguistic constraints, as follows:
    \begin{enumerate}
    \item{for pronominal anaphora:}
    \begin{enumerate}
    \item discard those antecedents that do not agree in gender, number, and
    person
    \item discard the antecedents that are non-co-referent according to the following
    rule:

A pronoun P is non-co-referential with a (non-reflexive or
    non-reciprocal) noun phrase N if any of the following
    conditions\footnote{C-command and minimal governing category restrictions are
proposed, as formulated in Reinhart \citeyear{Reinhart83}. Based
on these restrictions and the non-co-reference conditions of
 Lappin and Leass \citeyear{Lappin94}, we propose conditions  for NP-pronoun
non-co-reference adapted for Spanish. These conditions are applied
to the syntactic information provided by the partial parser. They
are of great importance because we do not use semantic information
in our proposal.} hold:
    \begin{itemize}
    \item P and N are in the same utterance and clause, and P and N
    modify the head of the same NP
    \item P and N are in the same utterance and clause, and P does not
    modify the head of any NP
    \end{itemize}
    \end{enumerate}
    \item{for adjective anaphora:}
    \begin{enumerate}
    \item discard those antecedents that do not agree in gender
    \item discard those antecedents whose head noun is not of the lexical category ``COMMON''
    \end{enumerate}
    \end{enumerate}


\item If more than one antecedent is left, filter the remaining antecedents by applying the following
weighted preferences:

    \begin{enumerate}
    \item{for pronominal anaphora:}
    \begin{enumerate}
    \item antecedents that are in the same AP as the anaphor (weight = 35)
    \item antecedents that are in the previous AP to that containing the anaphor (weight = 20)
    \item antecedents that are in the most recent unclosed AP (weight = 30)
    \item antecedents in the topic (weight = 15)

    \item antecedents that appear with the verb of the anaphor more than once (weight = 5)
    \item antecedents that are in the same position with reference to the verb as the anaphor (before or
    after)(weight = 5)
    \item antecedents that are in the same position with reference to the utterance as the
    anaphor (weight = 5)
    \item the nearest antecedent to the anaphor (used when more than one candidate obtains the highest value)
    \end{enumerate}
    \item{for adjectival anaphora:}
    \begin{enumerate}
    \item antecedents that are in the same AP as the anaphor (weight = 35)
    \item antecedents that are in the previous AP to that containing the anaphor (weight = 10)
    \item antecedents that are in the most recent unclosed AP (weight = 10)
    \item antecedents in the topic (weight = 35)
    \item antecedents that share the same kind of modifiers (e.g., prepositional phrases, adjectives, and so
    on) (weight = 5)
    \item antecedents with exactly the same modifiers (e.g., the same adjective
    'red') (weight = 5)
    \item antecedents that agree in number (weight = 5)
    \item the nearest antecedent to the anaphor (used when more than one candidate obtains the highest value)
    \end{enumerate}
    \end{enumerate}
    \end{enumerate}


 These preferences were developed as a result of the empirical study explained in the following section.


\section{Experimental work}
\label{eval}

In this section, an experimental study of the algorithm is
presented, including a deep description of the experiments,
corpora and tools used, as well as a study about the importance of
the anaphoric accessibility space.

\subsection{Corpora, tools, and description of experiments}

In order to evaluate the anaphora resolution algorithm proposed in
this paper, the general process outlined in Figure \ref{fig3} was
followed.


\begin{figure*}[htbp]
\centering
  \includegraphics[width=7cm, clip]{fig01.eps}
  \caption{Full evaluation process}
  \label{fig3}
\end{figure*}

Data for the evaluation were taken from the {\em Corpus
InfoTren: Person}, a corpus of 204 transcribed spoken Spanish
dialogues provided by the Ba\-sur\-de Project
\cite{Basurde98}. These dialogues are conversations between a
railway company employee and a client. The trans\-crip\-tor used
in the Ba\-sur\-de Project provides turn and speaker markup.
 Out of 204 dialogues, 40 were selected for the training
(training corpus)  and the remaining 164 were reserved for the
final evaluation (test corpus). These 204 dialogues contain 345
pronominal anaphors and 257 adjectival anaphors.

We had two aims in using the training corpus: (1) to estimate
the importance of the structural anaphoric accessibility space,
and (2) to define an adequate set of constraints and
preferences (experiments 0, 1, 2, and 3). The test corpus was
reserved to obtain the final evaluation.

In addition, the entire corpus was manually annotated with two
different goals: (1) to identify further discourse structural
properties such as adjacency pairs and topics, and (2) to identify
anaphors and antecedents. Although we annotated the corpus
manually, there are at present some automatic systems for
performing adjacency pair tagging (the Ba\-sur\-de Project
\cite{Basurde98}, for example), as well as for automatic topic
tagging \cite{Reynar99} or automatic topic extraction (see the
method for anaphora resolution described in Section
\ref{accspace}).

The annotation of conversational structure was carried out as
described in the next paragraph. An important aspect of dialogue
structure annotation is the training phase, which assures
reliability among annotators.

The annotation phase was accomplished as follows: (1) two
an\-not\-ators were selected, (2) an agreement\footnote{This
agreement is about what every tag means to every an\-not\-ator
when it is applied to the corpus.} was reached between the two
an\-not\-ators with regard to the annotation scheme using a
training corpus, (3) the annotation was then carried out by both
an\-not\-ators in parallel over the test corpus, and (4) a
reliability study was carried out on the annotation (Carletta {\it
et al.}~1997)\nocite{Carletta97}. The reliability study used the
{\it kappa} statistic that measures the affinity between the
annotations of the two an\-not\-ators by making judgments about
categories. For computing the \emph{kappa} ({\it k}) statistic,
see Siegel and Castellan \citeyear{Siegel88}.\footnote{Additional
information about this annotation process can be found in our
detailed reports \cite{Martinez2001,Martinez2000e}.}

Because turns are marked during the transcription phase, the
an\-not\-ator merely classifies turns according to the turn
types described in Section 3 and then relates each initiative
intervention $IT_I$ to its reaction intervention $IT_R$, thereby defining adjacency pairs. Since this task simply requires classification, it is easily measured using the
\emph{kappa} statistic.

Concurrently, topics were identified. This task was also simple,
since the corpus used for these experiments is organized into
short dialogues and each dialogue has only one main topic or
theme, and since these are introduced clearly by means of the client's
intervention at the beginning of each dialogue. As a result, we
detected no discrepancies between an\-not\-ators with regard to
the topic identification. Therefore, there was no
need to measure this task using the {\it kappa} statistic.

According to Carletta \emph{et al.}, a \emph{k} measurement
between $0.68$ and $0.80$ allows us to make positive conclusions,
and if $k$ is greater than $0.80$, we have total reliability
between the results of the an\-not\-ators.

In those cases where a discrepancy was found between the
an\-not\-ators, the following criterion was applied: each dialogue
was assigned a main an\-not\-ator whose annotation was considered
definitive in the event that there were discrepancies between the
two accounts. In order to guarantee balance, each an\-not\-ator
was the main an\-not\-ator for exactly 50\% of the dialogues.

Once both an\-not\-ators had finished the annotation, the
reliability study was carried out, with a resultant \emph{kappa}
measurement of $k=0.91$. We therefore consider the annotation
obtained for the evaluation to be totally reliable.

Since the annotated texts would be processed by an anaphora
resolution system, we developed an SGML tagging format.

Generally, this SGML markup will have the following form:

\begin{verbatim}
<ELEMENT-NAME ATTRIBUTE-NAME="VALUE" ...> text-string </ELEMENT-NAME>
\end{verbatim}

Thus, the following notations are used in each case:
\begin{itemize}
\item Topic:
\begin{verbatim}
<TOPIC> Topic-entity </TOPIC>
\end{verbatim}

\item Adjacency pairs:
\begin{verbatim}
<AP ID="number"> Adjacency-pair </AP>
\end{verbatim}
where ID is an identification number used to arrange the
adjacency pairs in sequential order

\item Intervention turns:
\begin{verbatim}
<IT TYPE="R|I" SPEAKER="speaker"> Intervention-turn </IT>
\end{verbatim}

where TYPE may be ``R'' or ``I'' (Reaction or Initiative) and SPEAKER
is the indicator for the speaker whose turn it is

\item Continuing turns:

\begin{verbatim}
<CT SPEAKER="speaker"> Continuing-turn </CT>
\end{verbatim}
\end{itemize}


The format is exemplified in Figure \ref{fig2}.

\begin{figure*}[htbp]
\centering \mbox{}\hrulefill \vspace{-.3em}
  \begin{minipage}{\textwidth} \small
  \begin{sffamily}
    \begin{tabular}{ll}
  & \\ $<$TOPIC$>$ & tren \\ & \emph{(train)} \\ $<$$/$TOPIC$>$ &
\\ & ...
\\ $<$AP ID=''4''$>$ &
\\ $<$IT TYPE=''I'' SPEAKER=''CL''$>$ & el de las seis y media ¿llega a
Monz\'{o}n?
\\
& \emph{(the one at half-past six, does it go to Monzon?) }\\
$<$$/$IT$>$ & \\ $<$AP ID=''5''$>$ & \\ $<$IT TYPE=''I''
SPEAKER=''OP''$>$ & a ver. el de las seis y media me ha preguntado
¿verdad?
\\ & \emph{(let
me see. you've asked about the one at half-past six,}
\\ & \emph{
right?)}\\ $<$$/$IT$>$ & \\

$<$IT TYPE=''R'' SPEAKER=''CL''$>$ & si \\ & \emph{(yes)}\\
$<$$/$IT$>$ &
\\ $<$$/$AP$>$ & \\ $<$IT TYPE=''R'' SPEAKER=''OP''$>$ & a las nueve y
veinticinco.
\\ & \emph{(twenty-five past nine.)}\\ $<$$/$IT$>$ & \\
$<$$/$AP$>$ & \\ & ... \\
   % \hline

    \end{tabular}
    \end{sffamily}
    \end{minipage}
    \mbox{} \hrulefill \vspace{-.6em}
   \caption{\label{fig2}Example of SGML annotation}

\end{figure*}

As explained above, in addition to this structural annotation, the corpus was also
anaphorically annotated by marking up the anaphoric relations
between all pronominal and adjectival ana\-phors and their correct
antecedents. In order to guarantee the results, this annotation
was performed by two different an\-not\-ators in parallel and a reliability
study of the subsequent annotation was then carried out. Once again, the annotation was
treated as a classification task, consisting of selecting the
appropriate elements in the candidate list (we estimated an
average of 6.5 possible antecedents per anaphor after applying
constraints). The reliability study of the manual anaphoric
annotation resulted in a \emph{kappa} measurement of $k=0.87$.

In addition, the corpus was tagged using the POS tagger technique
described by Pla and Prieto \citeyear{Pla98}. From this, we
obtained morphological and lexical information. The corpus was
then parsed using the SUPP partial parser proposed by
Mart\'{\i}nez-Barco {\em et al.}~\citeyear{Martinez98} in order to
obtain syntactic information. Finally, the proposed anaphora
resolution algorithm was applied.

Several studies were then carried out in order to
identify the importance of defining an adequate anaphoric
accessibility space and of defining a constraint and preference
system based on this space. In these studies, we compared the output of the anaphora resolution
system with the manual annotation and generated several
statistical results.


\subsection{Importance of the anaphoric accessibility space}

In order to show the importance of defining an adequate anaphoric
accessibility space, a study of the location of the antecedent of
each pronominal and adjectival anaphora was done using the
training corpus. The results are given in Table
\ref{tab3}.\footnote{Notice that the study of the anaphoric
accessibility space was not carried out using output from the
automatic anaphora resolution system but rather from the manual
annotations (i.e., the correct solutions).}


\begin{table*}[t]

  \begin{minipage}{\textwidth} \small
  \begin{center}
    \begin{tabular}{|l|c|c|c|c|c|}
    \hline

    & Same AP\footnote{The antecedent is found in the same adjacency pair as the anaphor}
    & Previous AP\footnote{The antecedent is found in the previous adjacency pair to the one containing the anaphor}
    & Included AP\footnote{The antecedent is found in the adjacency pair containing the adjacency pair including the anaphor}&
   TOPIC\footnote{The antecedent is found in the topic of the dialogue}
    & Elsewhere\footnote{The antecedent is found elsewhere}\\

    \hline \hline
    Pronominal & 60.6\% & 24.6\% & 8.2\%& 4.9\% & 1.7\%\\

    Adjectival & 44.7\% & 28.9\% & 5.2\% & 13.4\% & 7.8\%\\

    \hline \hline

  Total Results & \multicolumn{4}{|c|}{Anaphoric accessibility space proposed: 95.9\% } & 4.1\%\\
 & \multicolumn{4}{|c|}{(pronominal:
98.3\%, adjectival: 92.2\%)} & \\
    \hline
    \end{tabular}
    \end{center}
    \end{minipage}
 \caption{\label{tab3}Structural anaphoric accessibility space results}
\end{table*}


As can be seen in the table, 95.9\% of the antecedents were
located in the proposed structural anaphoric accessibility space.
It is estimated that the remaining antecedents (4.1\%) are located
in the subtopics of the dialogues.\footnote{By subtopic, we mean
an NP that is not the main topic of the dialogue but contributes
to defining it.} In order to incorporate these remaining
antecedents into the anaphoric accessibility space, one might
employ a strategy that uses the \textbf{full space} (i.e., all the
noun phrases from the beginning of the dialogue to the anaphor
might be used). However, as shown in Table \ref{tab4}, our
proposal for the anaphoric accessibility space (hereafter referred
to as \textbf{structural}), reduces the average number of
candidates per anaphor (before applying constraints) to 10.74 from
the 34.14 that would be obtained if the \textbf{full space}
approach were adopted. In others words, using the \textbf{full
space} approach would increase the number of possible candidates
by a factor of three, thereby greatly increasing both the required
computational effort and the possibility of selecting incorrect
antecedents. Notice, too, that these experiments were performed
over a collection of short dialogues (around 332 words per
dialogue). These problems will be even more acute in longer
dialogues.

\begin{table}[htbp]
 % \begin{minipage}{\textwidth}

  \begin{center}
  %\scriptsize
     \begin{tabular}{|l|c|c|c|}
    \hline

    Anaphoric accessibility space& Structural & Full space & Window of utterances\\

    \hline \hline
    Total candidates & 1,063 & 3,380 &1,292\\

    Candidates per anaphor & 10.74 & 34.14 &13.05\\

    \hline \hline

    Proportion & 100\% & 318\% & 122\% \\
    \hline
    \end{tabular}
   \end{center}
  %  \end{minipage}
     \caption{\label{tab4}Candidates to be processed for each anaphoric accessibility space}
\end{table}

Other researchers have proposed using a window with a fixed number
of sentences to define the anaphoric accessibility space. This
type of approach might be called a \textbf{window of sentences}
approach. For example, Ferr\'andez \emph{et
al.}~\citeyear{Ferrandez2000} propose using the three previous
sentences to define the accessibility space for pronouns and the
four previous sentences for adjectival anaphora in Spanish. For
English, Kameyama \citeyear{Kameyama97} proposes the same space
for the pronominal. However, there is no structural justification
for these definitions. Ferr\'andez \emph{et al.}~and Kameyama
performed several empirical studies to show the optimal space for
each experiment. Table \ref{tab5} below shows the results of a
study which we performed using the \emph{Corpus Infotren: Person},
the goal of which was to define an anaphoric accessibility space
based on a \textbf{window of sentences} that can then be adapted
to dialogues by means of a \textbf{window of utterances}. As the
table shows, 11 utterances for pronominal anaphora and 10
utterances for adjectival anaphora are needed in order to cover
the same number of antecedents as was covered using the structural
anaphoric accessibility space (which was defined based on
adjacency pairs and the topic). Since the anaphoric space using a

window of utterances is not based on any principle, but rather on
empirical studies, it may vary from one text to another and
therefore is inadequate. Moreover, the structural anaphoric
accessibility space can cover only those cases that refer to NPs
introduced at the outset of the dialogue (topics), not those with
a window of sentences/utterances approach.

In conclusion, it would appear that the \textbf{structural}
anaphoric accessibility space is to be preferred, at least for
anaphora resolution in dialogues.

\begin{table}[h]

\begin{center}
    \begin{tabular}{|c|c|c|}
    \hline

    \textbf{Window of utterance}: & \% pronominal &\% adjectival \\
      {\it ``From Anaphor's} & anaphora & anaphora\\
    {\it utterance to'':} & antecedents &antecedents \\
    \hline \hline

    Anaphor's utterance &37.7 &18.4\\

    -1 & 54.1 & 44.7\\

    -2 & 70.5 & 52.6\\

    -3 & 77.0 & 55.3\\

    -4 & 80.3 & 57.9\\

    -5 & 83.6 & 71.0\\

    -6 & 88.5 & 73.7\\

    -7 & 91.8 & 76.3\\

    -8 & 91.8 & 81.6\\

    -9 & 95.1 & 81.6\\

    -10 & 96.7 & \textbf{92.1}\\

    -11 & \textbf{98.4} & 94.7\\

    -12 & 98.4 & 97.4\\

    -13 & 98.4 & 97.4\\

    -14 &100.0 &100.0\\

\hline

    \hline
    \end{tabular}

\end{center}
 \caption{\label{tab5}Empirical study of anaphoric accessibility space based on a window of utterances}
\end{table}

\subsection{Constraint and preference set}

As for the importance of defining an adequate constraint and
preference set based on dialogue structure using the accessibility
space defined in Section 4, we begin by adopting the constraint
and preference set developed by Ferr\'andez \emph{et
al.}~\citeyear{Ferrandez2000} and described below in Section 6.4.
This constraint and preference set has been shown to be adequate
for pronominal and adjectival anaphora in non-dialogue discourse.
To this set, information about dialogue structure will be applied
in order to take advantage of its influence. Not only is dialogue
structure used to define the anaphoric accessibility space, but it
is used to define preferences as well.

For this study, several experiments were carried out using the
training corpus. These experiments involved changes in the
constraint and preference set in order to define the
configuration\footnote{The term \emph{configuration} is used here
to define the set of constraints and preferences that makes up the
system used for a concrete instance of the experimental process.}
that would have optimum precision. Results are summarized in Table
\ref{table2}.


\begin{table*}[t]

\begin{minipage}{\textwidth}
\begin{center}
%\scriptsize
\begin{tabular}{|c|cccccccccccccc|c|}
\hline \hline \rule{0pt}{10pt}

& \multicolumn{14}{|c|}{Used preferences} & {Precision}\\

\hline \rule{0pt}{10pt}

Experiment & \multicolumn{14}{|c|}{Pronominal anaphora}  &\\

No. &1 &2 &2$_a$ &2$_b$ &3 &4 &5 &6 &7 &8 &9 &10 &11 &12  &\% \\

\hline \rule{0pt}{10pt}

0 &$\bullet$ &$\bullet$ & & &$\bullet$ &$\bullet$ &$\bullet$
&$\bullet$ &$\bullet$ &$\bullet$ &$\bullet$ &$\bullet$ &$\bullet$
&$\bullet$  &59.0 \\

1 &$\bullet$ &$\bullet$ &$\bullet$ &$\bullet$ & & & & & & & & &
&$\bullet$  &62.3 \\

2 &$\bullet$ &$\bullet$ &$\bullet$ &$\bullet$ & & & &$\bullet$
&$\bullet$ &$\bullet$ & & & &$\bullet$  &73.8 \\

3\footnote{Preference weighted management} &$\bullet$ &$\bullet$
&$\bullet$ &$\bullet$ & & & &$\bullet$
&$\bullet$ &$\bullet$ & & & &$\bullet$  &81.3 \\
\hline \hline

\hline \rule{0pt}{10pt}

Experiment & \multicolumn{14}{|c|}{Adjectival anaphora} &
\\

No. &1 &2 &2$_a$ &2$_b$ &3 &4 &5 &6 &7 &8 &&&&& \%\\ \hline
\rule{0pt}{10pt}

 0 &$\bullet$ &$\bullet$ & & &$\bullet$ &$\bullet$
&$\bullet$ &$\bullet$ &$\bullet$ &$\bullet$ & & & &  &23.7\\

1 &$\bullet$&$\bullet$ &$\bullet$ &$\bullet$ & & & & & &$\bullet$
&& & &  &65.8\\

2  &$\bullet$ &$\bullet$ &$\bullet$ &$\bullet$ &$\bullet$
&$\bullet$ &$\bullet$ & & &$\bullet$ && & &  &78.9\\

3\footnote{Preference weighted management}  &$\bullet$ &$\bullet$
&$\bullet$ &$\bullet$ &$\bullet$
&$\bullet$ &$\bullet$ & & &$\bullet$ && & &  &81.5\\

\hline \hline
\end{tabular}
\end{center}
\end{minipage}
\caption{\label{table2}Experiment summary}
\end{table*}

\subsubsection{Preference management}

There are two different approaches to managing the preference set,
ordered management and weighted management. Ordered management is
based on discarding those antecedents that do not fulfill a preference if
there is any candidate that fulfills it. Weighted management
is based on assigning a weight to each preference and then
selecting the candidate with the maximum value.

For these experiments, the system was trained so as to obtain
the best set of preferences. Subsequently, we applied both of the
approaches to preference management to obtain the best result with
the training corpus. Once we obtained the best set of
preferences and its best management, we evaluated the system with
the test corpus in order to obtain independent results.

So, for experiments 0, 1, and 2, ordered management was
applied to obtain the best set of preferences. Then, in experiment 3, we applied weighted management to
improve the results in the training corpus.

\subsection{Experiment 0 (baseline): Linguistic information only}

We began with the constraint and preference set used by
Ferr\'{a}ndez {\em et al.}~\citeyear{Ferrandez2000}. This
algorithm is based on linguistic information only, and its results
have been successfully tested over a non-dialogue corpus with a
resulting precision of 82\% for pronominal anaphora resolution (we
have no information about the precision for adjectival anaphora).

The initial configuration included the following constraint and
preference set and definition of anaphoric accessibility space.

\subsubsection{Anaphoric accessibility space}

For pronominal anaphora resolution, the anaphoric accessibility
space consisted of the three previous turns to the anaphor. For
adjectival anaphora, the space consisted of the previous four
turns.

\subsubsection{Constraints}

\begin{itemize}
\item In the case of pronominal anaphora, the constraints included:

\begin{enumerate}
    \item{morphological agreement: discard the antecedents which are incompatible morphologically (gender, number, and person)}
    \item{syntactic context: discard the antecedents which are non-co-referent according to Lappin and Leass \citeyear{Lappin94}}
\end{enumerate}

\item In the case of adjectival anaphora, the constraints included:

\begin{enumerate}
    \item{morphological agreement: discard the antecedents which are incompatible morphologically (gender)}
    \item{Proper-noun-phrase exclusion: exclude noun phrases having a proper noun\footnote{Proper nouns are not usually modified by adjectives.
    Thus, noun phrases having a proper noun as head are not likely candidates as antecedents of adjectival anaphors.} as head}
\end{enumerate}

\end{itemize}

\subsubsection{Preferences}

\begin{itemize}
\item In the case of pronominal anaphora, the preferences are for:

\begin{enumerate}
\item{candidates in the same turn as that of the anaphor}
\item{candidates in the previous turn}
\item{candidate proper nouns or indefinite NPs}
\item{(for personal pronouns) candidate proper nouns}
\item{candidates that have been repeated more than once (repeated forms and repeated mentions)}
\item{candidates that have appeared more than once in construction with the verb in construction with the anaphor}
\item{candidates in the same position as the anaphor with reference to the verb (before or after)}
\item{candidates in the same position with reference to the utterance as the anaphor}
\item{candidates not in circumstantial adjuncts}
\item{candidates most repeated in the text}
\item{candidates most often appearing in construction with the verb in construction with the anaphor}
\item{the closest candidate to the anaphor}
\end{enumerate}

\item In the case of adjectival anaphora, the preferences are for:

\begin{enumerate}
\item{candidates in the same turn as that of the anaphor}
\item{candidates in the previous turn}
\item{candidates sharing the same kind of modifier as the anaphor (e.g., a prepositional
phrase)}
\item{candidates sharing the same modifier as the anaphor (e.g., the same adjective: 'roja' red)}
\item{candidates agreeing in number}
\item{candidates most often repeated in the text}
\item{candidates appearing most often in construction with the verb in construction with the anaphor}
\item{the closest candidate to the anaphor}
\end{enumerate}

\end{itemize}

\subsubsection{Discussion}

Given this first configuration, an evaluation was carried out
which resulted in a precision of 59.0\% for pronominal anaphora
resolution and 23.7\% for adjectival anaphora resolution. Needless
to say, these results are very low for pronominal anaphora and
extremely poor for adjectival anaphora. In evaluating the errors, we concluded that the
defined anaphoric
accessibility space was too constrained and too arbitrarily
defined. It simply disregarded the relationship between anaphora
and dialogue structure. Consequently, we proposed the following changes
for the second experiment.

\subsection{Experiment 1: Dialogue structure information only}

For this experiment, the definition of the anaphoric accessibility
space was changed to employ information provided by the dialogue
structure, as suggested by
Mart\'{\i}nez-Barco \citeyear{Martinez99b}. In addition, the
preferences affected by this revised definition of anaphoric
accessibility space were modified as well.

\subsubsection{Anaphoric accessibility space}

The adjacency pair and the topic of the dialogue were used in
order to define the anaphoric accessibility space. Concretely, we
defined an anaphoric accessibility space by means of the adjacency
pair of the anaphor, the previous adjacency pair to the adjacency
pair of the anaphor, adjacency pairs containing the adjacency pair
of the anaphor, and, finally, the main topic of the dialogue (for
pronominal as well as adjectival anaphora).

\subsubsection{Preferences}

For Experiment 1, we removed the pronominal anaphora preferences
described above in items 3 through 11 and the adjectival anaphora preferences
described in items 3 through 7. Also, preferences 1 and 2 above were replaced
by the following four new preferences. Thus, both for pronominal
and adjectival anaphora, the preferences are for:

\begin{itemize}
\item{1. candidates in the same adjacency pair as that of the anaphor}
\item{2. candidates in the previous adjacency pair to the anaphor}
\item{2$_a$. candidates in any adjacency pair containing the adjacency pair of the anaphor}
\item{2$_b$. candidates that are in the topic}
\end{itemize}

This change was made in order to test the system's performance
when linguistic information is removed and only dialogue structure
information is used (preferences 1 through 2$_b$). In order to guarantee a
single final solution, only linguistic
preference item 12, for pronominal anaphora, and item 8, for adjectival
anaphora (the closest candidate), remain.

\subsubsection{Discussion}

After including information about dialogue structure and removing
the linguistic preferences, precision rates rose to 62.3\% for
pronominal anaphora resolution and 65.8\% for adjectival anaphora
resolution. A considerable increase is gained in the resolution of
adjectival anaphora by simply changing the definition of the
accessibility space. That is due to the fact that adjectival
anaphora need a larger space than that used in Experiment 0.

But these results are still low and demonstrate that dialogue
structure information alone is not sufficient. Thus, a third
experiment was carried out using both dialogue structure and
linguistic information. Several variations in the preference
system were investigated independently.

\subsection{Experiment 2: Linguistic information plus dialogue
structure information (with ordered management of preferences)}

Following, the preferences used in this experiment and their
justification are shown.

\subsubsection{Preferences}
In this experiment, we first used a preference set that included
all the linguistic and dialogue structure preferences described
above. Then, various alternatives were used in order to obtain an
optimal configuration. As a result, the following preferences
were arrived at for the final configuration:

\begin{itemize}
\item For pronominal anaphora, the preferences are for:
\begin{itemize}
\item dialogue structure preferences: 1 through 2$_b$
\item linguistic preferences: 6, 7, 8, and 12
\end{itemize}
\item For adjectival anaphora, the preferences are for:
\begin{itemize}
\item dialogue structure preferences: 1 through 2$_b$
\item linguistic preferences: 3, 4, 5, and 8
\end{itemize}

\end{itemize}

This final set of constraints and preferences is the one that is
presented in Section \ref{algo}.

\subsubsection{Discussion and justification}

It should be noted that information about repeated
candidates---for example, the pronominal anaphora preferences 5,
10, and 11, or the adjectival anaphora preferences 6 and 7---is
usually inserted into the preference system in order to achieve
knowledge about the main entities of the dialogue. However, in
this experiment, information about the main topic of the dialogue
has been included and so information about repeated candidates is
unnecessary. Those preferences were therefore removed, improving
the results.

Furthermore, we found that pronominal anaphora preferences 3 and 4
for proper nouns caused errors. This is because in the domain of
the experiment there is an exaggerated use of place names where
these preferences incorrectly apply. By removing them, better
results were obtained.

Finally, since the usefulness of preference 9 (candidates that are
not in circumstantial adjunct) has never been justified properly,
it too was omitted. After removal, the precision for pronominal
anaphora stayed the same.

Thus, having considered all possible applications for ordered
preference management, and given that this final set of preferences represented the minimum set of
preferences, we considered it to be the optimal set. We then applied this optimal set of preferences to the
training corpus, obtaining a precision
of 73.8\% for pronominal anaphora resolution and 78.9\% for
adjectival anaphora.

\subsection{Experiment 3: Linguistic information plus dialogue
structure information (with weighted management of preferences)}

Following, the preferences used in this experiment and their
justification are shown.

\subsubsection{Preferences}

\begin{table}[htbp]

 % \begin{minipage}{\textwidth}
  \begin{center}
  %\scriptsize
     \begin{tabular}{|l|l|c|}
    \hline

    Pref. No. & Description & Weight\\

    \hline \hline
    1 &Antecedents that are in the same AP as the anaphor &35\\
    2 &Antecedents that are in the previous AP to that &\\
     &containing the anaphor & 20\\
    2$_a$ &Antecedents that are in the most recent unclosed AP &30\\
    2$_b$ &Antecedents in the topic &15\\
    6 &Antecedents that appear with the verb of the anaphor more &\\
     &than once & 5\\
    7 &Antecedents that are in the same position with reference &\\
     & to the verb as the anaphor (before or after) & 5\\
    8 &Antecedents that are in the same position with reference  &\\
      & to the utterance as the anaphor & 5\\
    12 &The nearest antecedent to the anaphor &YES\\
    \hline
    \end{tabular}
   \end{center}
  %  \end{minipage}

\caption{\label{tab6}Preference weight assignment for pronominal
anaphora}
\end{table}

In this final experiment, the preference set obtained in the
previous experiment was used (including the minimum set of
preferences that we considered to be the optimal configuration).
Then, several alternatives were used in order to obtain an optimal
preference weight assignment. Tables \ref{tab6}
and \ref{tab7} show the preference weight assignments for pronominal and adjectival anaphora, respectively.

\begin{table}[htbp]
 % \begin{minipage}{\textwidth}

  \begin{center}
  %\scriptsize
     \begin{tabular}{|l|l|c|}
    \hline

    Pref. No. & Description & Weight\\

    \hline \hline
    1 &Antecedents that are in the same AP as the anaphor &35\\
    2 &Antecedents that are in the previous AP to that &\\
     &containing the anaphor & 10\\
    2$_a$ &Antecedents that are in the most recent unclosed AP &10\\
    2$_b$ &Antecedents in the topic &35\\
    3 & Antecedents that share the same kind of modifiers & 5\\
    4 &Antecedents with exactly the same modifiers & 5\\
    5 &Antecedents that agree in number  & 5\\
    8 &The nearest antecedent to the anaphor &YES\\
    \hline
    \end{tabular}
   \end{center}
  %  \end{minipage}

 \caption{\label{tab7}Preference weight assignment for adjectival anaphora}
\end{table}


This final set of constraints and preferences was presented in
Section \ref{algo}.

\subsubsection{Discussion and justification}
In order to obtain the optimal preference weight assignment, we
performed several tests with the training corpus. Thus, after
looking at all the possibilities and given that this was the set
of preferences having the best results, we considered it to be the
optimal configuration. With this configuration, we obtained a
precision of 80.3\% for pronominal anaphora resolution and 92.1\%
for adjectival anaphora resolution.


\subsection{Final evaluation (test corpus)}

Using the final preference set defined in Experiment 3 and the
proposed constraint set, a blind evaluation was carried out
over the entire test corpus. This evaluation was performed independent
of the training process so as to guarantee that the
training would have no influence over the final percentages.

As a result, we obtained a precision of 81.3\% for pronominal
anaphora resolution and 81.5\% for adjectival anaphora resolution.

\section{Conclusion}
\label{concl}

In this paper we have presented an algorithm for identifying the
noun phrase antecedents of pronouns and adjectival anaphors in
Spanish dialogues. This algorithm exploits different kinds of
information: linguistic knowledge, discourse/dialogue structure
information, and discourse topic knowledge. It is based on a set of
constraints and preferences which depend on all available
knowledge in order to resolve anaphora.

In addition, a definition of the anaphoric accessibility space
based on discourse/dialogue structure information was presented.
We have shown the importance of this accessibility space in
anaphora resolution, in contrast to algorithms that do not rely on
any such space. Results show that 95.9\% of the antecedents were
located in the proposed space.

Finally, we described a set of experiments concerning this
algorithm and accessibility space using a corpus of 204 dialogues.
The algorithm was implemented using Prolog. In our final experiment,
a precision of 81.3\% was achieved for pronominal anaphora
resolution and a precision of 81.5\% was achieved for adjectival
anaphora resolution.

As a tool for resolving pronominal and adjectival anaphora for
Spanish dialogues, this system can be used in support of various
NLP tasks, including machine translation, information
extraction, retrieval information, or question-answering.

Currently, the authors are working on incorporating semantic
information into the algorithm.

\section*{Acknowledgments} The authors wish to thank Natividad Prieto,
Ferran Pla, and Antonio Molina for having contributed their
tagger; Lidia Moreno for her helpful revisions of the ideas
presented in this paper; and Rafael Mu\~noz, Maximiliano
Saiz-Noeda, Antonio Ferr\'andez, and Jes\'us Peral for their
collaboration in performing the experiments. We are also grateful
to several anonymous reviewers of the {\it Journal of Artificial
Intelligence Research} for helpful comments on earlier drafts of
the paper.

This research has been supported by the Comisi\'on Interministerial
de Ciencia y Tecnolog\'{\i}a (CICYT) of the Spanish government,
under project numbers TIC97-0671-C02-01/02 and HB1998-0068.

%%{acknowledgments}

\bibliographystyle{theapa}
\bibliography{jairref}

\end{document}
