\documentclass[10pt]{llncs}
%\usepackage{a4}
%\usepackage{a4wide}
\usepackage{psfig}
\usepackage{linguex}
\newcommand{\ign}[1]{} 
\newcommand{\ea}{{\it et al.}} 
\setlength{\parskip}{2mm}
\setlength{\parindent}{0mm}
\hyphenation{in-de-pen-dent} 
\hyphenation{in-com-pat-i-ble}
\hyphenation{com-ple-ments}  
\hyphenation{past-par-ti-ci-ple}
\hyphenation{rec-og-nize} 
\hyphenation{spe-cif-iers}
\title{Centering-based Anaphora Resolution in Danish Dialogues} 
\author{Costanza Navarretta}
\institute{Center for Language Technology\\
Njalsgade 80\\
2300 Copenhagen S - DK\\
tel. 45 + 35 32 90 65\\
fax. 45 + 35 32 90 89 \\
\texttt{costanza@cst.ku.dk}} 
\date{}
\begin{document}
%\bibliographystyle{plain}
\maketitle
\begin{abstract}
In this paper\footnote{The research described has partially been funded by
the Staging project which is funded by the Danish Research Councils.}
we present the results of applying two different 
centering algorithms (\cite{Brennan+al:1987} and
\cite{Strube:1998})  to Danish discourses. Then we describe
how we have adapted the algorithm for resolving 
anaphora referring to both individual NPs and discourse deictics
presented in \cite{Eckert+Strube:1999} so that it covers Danish
discourse deictics. 
The modified algorithm has been manually tested on Danish
dialogues and the obtained results have been evaluated.  
\end{abstract}
\section{Introduction}
\label{sec:intro}
Resolving anaphors is an important task in many NLP applications. 
Most of the current anaphora resolution algorithms only deal with
coreference between anaphors and individual NPs in written texts. In
particular algorithms based on centering theory \cite{Grosz+al:1995}
have been studied and tested extensively in many languages, but not
for Danish. Recently centering has also been applied to dialogues,
i.a. \cite{Byron+Stent:1998} and \cite{Eckert+Strube:1999}. 
 Eckert and Strube \cite{Eckert+Strube:1999}, in particular, present 
 an algorithm, henceforth the ES99-algorithm, for the resolution of
 anaphors in English dialogues. The ES99-algorithm  which applies to
 both anaphors referring to individual NPs and discourse deictics is
 based  on rules for discriminating among individual NPs and discourse 
 deictics, mainly determined by the  syntactic constructions in which
 the anaphors occur. After having tested whether centering
 works on Danish texts, we have adapted the rules of the ES99-algorithm 
to Danish and applied the modified algorithm to Danish dialogues.

This paper is organized as follows. In section~\ref{sec:cent} we
shortly describe two centering algorithms, the BFP-algorithm
\cite{Brennan+al:1987} and the S98-algorithm
\cite{Strube:1998} and we
present the results of their application on Danish texts. In
section~\ref{sec:ES99}  we outline the ES99-algorithm. In
section~\ref{sec:modi} we shortly present the Danish discourse deictics
found in the two dialogue corpora Bysoc and
SL\footnote{Both corpora have been collected by researchers 
 at the Department of General and Applied Linguistics at the
 University of Copenhagen.} 
 and we describe the modified ES99-algorithm accounting for Danish data.  
Finally (section~\ref{sec:conc}) we evaluate the results obtained 
by manually testing the ES99-algorithm on the SL dialogues.
\section{Centering and Danish data}
\label{sec:cent}
The centering theory fits into Grosz and Sidner's model
of discourse structure \cite{Grosz+Sidner:1986}, according to which
a discourse is composed of discourse segments which exhibit \emph{global
  coherence}. A discourse segment is composed of a sequence of
utterances which exhibit \emph{local coherence}. The latter phenomenon is
accounted for by the centering theory. The basic assumption behind
centering is that some entities in an utterance are more central than
others and this fact influences the use of referring expressions. The
entities which link an utterance $U_{n}$ to the others in the same discourse
segment are called the \emph{centers} of that utterance. 
Each utterance is assigned a set of \emph{forward-looking centers}, 
$C_f$,  and, with the exception of the initial utterance of the segment, a 
\emph{backword-looking center}, $C_b$. The $C_b$ of an utterance
$U_{n}$ connects with one of the \emph{forward-looking centers} of the
preceding utterance $U_{n-1}$, while the \emph{forward-looking centers}
exclusively depend on the expressions in $U_{n}$.  The \emph{forward-looking
  centers} are partially ordered to reflect relative
prominence. In the BFP-algorithm \emph{forward-looking
  centers} are ranked  according to
the obliqueness of the grammatical relations of the subcategorized
functions of the main verb (subject $>$ object $>$ object2 $>$
complements $>$ adjuncts). The first element in the
$C_f$ list is called the preferred center, $C_p(U_n)$. In BFP
four types of transition relations across pairs of utterances,
\emph{continue, retain, shifting-1, shifting}, are identified. The
discriminating elements between the transitions are given in
table~\ref{tab:trans2} \cite{Brennan+al:1987}[p.~157]. 
\begin{table}[h]
  \begin{center}
\begin{tabular}[b]{|c|c|c|}\hline\hline
& $C_b$($U_{n}$) = $C_b$($U_{n-1}$)& $C_b$($U_{n}$) $\neq$
$C_b$($U_{n-1}$)\\
& OR no $C_b$($U_{n-1}$)&\\\hline
$C_b$($U_{n}$) = &&\\
$C_p$($U_{n}$)& \emph{continue}&\emph{shifting-1}\\\hline
$c_b$($U_{n}$)~$\neq$ &&\\
$c_p$($U_{n}$)& \emph{retain}&\emph{shifting}\\\hline\hline
\end{tabular}
    \caption{Transition States}
    \label{tab:trans2}
  \end{center}
\end{table}
The following two  rules constrain center realization in BFP:
\begin{description}
\item[Rule 1:] If any element of $C_f$($U_{n-1}$) is realized by a
  pronoun in $U_{n}$, then $C_b$($U_{n}$) must also  be realized by a
  pronoun 
\item[Rule 2:] The center transitions have  the following ranking:\\
\emph{continue} $>$ \emph{retain} $>$ \emph{shifting-1} $>$ \emph{shifting}
\end{description}
The BFP-algorithm consists of three steps:
%\small
\begin{enumerate}
\item \textbf{construct} the proposed anchors for an utterance and
  possible \emph{Cb-Cf} combinations 
\item \textbf{filter} by i.a.\ contra-indices, sortal predicates, centering
  rules and constraints 
\item \textbf{rank} by transition orderings.
\end{enumerate}
%\normalsize
The S98-algorithm \cite{Strube:1998} treats both intrasentential and
intersentential anaphors. In S98 the functions of the
\emph{backward-looking center} and 
the \emph{transitions} in the centering theory are replaced by
the order of elements in a list of salient discourse entities, the
\textbf{S-list}. The ranking criteria for the elements in the S-list
are based on \cite{Prince:1981} and \cite{Prince:1992}, where 
discourse entities are classified into  \emph{hearer-old}
(OLD), \emph{mediated} (MED) and \emph{hearer-new} (NEW). 
The two tuples ($x$, $utt_x$, $pos_x$)  and ($y$, $utt_y$, $pos_y$) 
 in the S-list indicate that the entity $x$ is evoked in  utterance
 $utt_x$ at position $pos_x$ and  that $y$ is evoked in the
 utterance $utt_y$ at position $pos_y$ respectively. Given that
 $utt_x$ and $utt_y$ refer to $U_{n}$ or $U_{n-1}$, the following ranking 
constraints on the S-list entities are valid
\cite{Strube:1998}[p.1253]:\footnote{We mark ranking precedence with $\prec$.} 
\small
\begin{enumerate}
\item if $x$ $\in$ OLD and $y$ $\in$ MED, then $x$ $\prec$  $y$ \\
if $x$ $\in$ OLD and $y$ $\in$ NEW, then $x$ $\prec$  $y$ \\
 if $x$ $\in$ MED and $y$ $\in$ NEW, then $x$ $\prec$  $y$ 
\item if $x$,$y$ $\in$ OLD or $x$,$y$ $\in$ MED or $x$,$y$ $\in$ NEW,\\
then if $utt_x$ $>$ $utt_y$ then $x$ $\prec$  $y$ \\
     if $utt_x$ $=$ $utt_y$ and $pos_x$ $<$ $pos_y$  then $x$ $\prec$  $y$
\end{enumerate}
\normalsize
Strube's algorithm for anaphora resolution consists in testing a
referring expression against the elements
in the S-list from left to right until the test succeeds. The S-list
is then updated so that new elements are inserted according to the
S-list ranking criteria. When the analysis of an utterance is finished 
all the entities which were not realized in the utterance are removed
from the S-list.

We have applied the two algorithms to randomly chosen
chapters of a  pc-manual (10,715 words) and newspaper articles (9,914 words).
In the test discourse segments were paragraphs and  utterances
were clauses. Following \cite{Strube:1998} we have extended the
BFP-algorithm to cover complex clauses following the strategy
described in \cite{Kameyama:1998}.\footnote{Kameyama treats
tensed clauses as independent utterances, while untensed clauses are
treated as part of the main clause. Tensed clauses comprise reported
speech, which is not accessible to 
the superordinate level, non-report complements and relative clauses
which are accessible to the superordinate level, but less salient. The
remaining types are processed at the same level as the 
main clause.}
We manually marked expletives and discourse deictics.

The success rate for the BFP-algorithm was  72,5 \% while the
S98-algorithm had a success rate of 91,67 \%. 
The difference between the results obtained with the two algorithms is
mainly  due to the fact that the BFP-algorithm does not
account for intrasentential anaphors. The cases where both algorithms
failed in resolving pronominal anaphora comprise complex
plural antecedents (coordinated and split ones),  generic use of the 
neuter pronoun \emph{det} (it), plural pronouns without antecedents,
ambiguity of antecedents. Although the results obtained in tests
applied to different kinds of discourse in different languages
cannot be compared, the results obtained in our test are similar to
those obtained in other languages (i.a. \cite{Strube:1998},
\cite{Tetreault:1999}). This indicates that centering also works for
Danish.    
\section{The ES99-algorithm}
\label{sec:ES99}
In the ES99-algorithm the types of anaphor identified are individual
 anaphors, discourse deictics, inferrable-evoked anaphors and 
vague anaphors. Predicates that are preferably
associated with abstract objects are marked as \textbf{i-incompatible}
 (*I) while predicates that are preferably associated with
individual objects are marked  as \textbf{a-incompatible} (*A).
As an example we quote the \textbf{*I} predicates given in
\cite{Eckert+Strube:1999}[p.~40]:
\small
\begin{itemize}
\item Equating constructions where a pronominal referent is equated
  with an abstract object, e.g., \emph{x is making it easy, x is a
    suggestion}.
\item Copula constructions whose adjectives can only be applied
  to abstract entities, e.g., \emph{x is true, xis false, x is
    correct, x is right, x isn't right}.
\item Arguments of verbs describing propositional attitude which only take
  S'-complements, e.g., \emph{assume}.
\item Object of \emph{do}.
\item  Predicate or anaphoric referent is "a reason", e.g., \emph{x is
    because I like her, x is why he's late}. 
\end{itemize}
\normalsize
Individual anaphors are resolved with the S98-algorithm, while 
abstract objects are treated in a 
so called A-list. The A-list is filled when
discourse deictics occur and  elements remain 
in the list only for one dialogue act (I, Initiation).\footnote{In
  \cite{Eckert+Strube:1999} 
grounded acts are used as domain for the resolution 
algorithm instead of clauses. We have followed the same discourse model.}
A context ranking procedure describes
the order in which the parts of the linguistic contexts are accessed.
\section{The Modified Algorithm}
\label{sec:modi}
We have adapted the ES99-algorithm so that it covers Danish data
identified in our dialogue corpora. The focus in our description is on
discourse deictics. In Danish the most used 
discourse deictic is  
\emph{det} which corresponds to 
both  \emph{it} and \emph{that}.\footnote{ 
The pronoun  \emph{det}
usually co-refers with (from now on we simply write \emph{refers to})
nominals in neuter gender. It is also used as expletive.
\emph{Det} is also the neuter definite
article (the) and the demonstrative adjective (that).} 
\emph{Dette} (this) is another discourse deictic, but it is mainly used in
written language and did not occur at all in our dialogues. 

When used as discourse deictic \emph{det} can refer to 
an infinitive or a finite clause, as it is the case
in the following examples:
\ex.
\a. \emph{At ryge er farligt og det er ogs{\aa} dyrt}\\
(Smoking is dangerous and it is also expensive)
\b. \emph{Jeg skal m{\aa}le dit blodtryk}.\\
(I have to measure your blood pressure.)\\
\emph{Hvorfor det?} (Why (that)?)

\emph{Det}refers to a verb phrase when it is used
as the object  complement with \emph{have} (have),
modal verbs and with the verb \emph{g{\o}re}
(do).  
\ex. \a.\emph{Jeg faldt, men det gjorde hun ikke}\\
(I fell, but she did not)

\emph{Det} refers to a clause in constructions with verbs such
as \emph{tro} (think), \emph{sige} (say), \emph{vide} (know):
\ex.
\emph{Han lyver.} (He is lying)\\
 \emph{Det tror jeg ikke} (I do not think so)

\emph{Det} can also refer to more clauses, or to something that can
be vaguely inferred from the previous discourse.
On the basis of the deictics in the Danish dialogues 
we have defined the following types of \textbf{*I} predicate
for Danish:
\small
\begin{itemize}
\item constructions where a pronoun is equated.
  with an abstract object,  e.g., \emph{x g{\o}r det sv{\ae}rt} (x is
  making it difficult)
\item copula constructions with adjectives which can only be applied
  to abstract entities, such as \emph{x er sandt} (x is true)
\item arguments of verbs indicating propositional attitudes which take
  S'-complements, such as \emph{tro} (believe), \emph{antage} (assume)
\item arguments of verbs such as \emph{sige} (say) and \emph{vide} (know)
\item object of \emph{g{\o}re} (do)
\item object of \emph{have} (have) if  the verb was not used as a main
  verb in the previous clause 
\item object of modal verbs
\item predicate or anaphoric referent is a reason, such as \emph{x er
 fordi\ldots} (x is because)
\end{itemize} \normalsize
Our \textbf{*A} predicates are the following:
\small
\begin{itemize}
\item constructions where a pronominal referent is equated
  with a concrete individual referent, such as \emph{x er en
    legemsdel} (x is a body part)
\item copula constructions with adjectives which can only be applied
  to concrete entities, such as \emph{x er dyr} (x is expensive),
  \emph{x er r{\o}d} (x is red)
\item  arguments of verbs describing physical contact/stimulation, 
e.g., \emph{sl{\aa} x} (hit x), \emph{spise x} (eat x)
\end{itemize} \normalsize
\section{Evaluation and Conclusion}
\label{sec:conc}
We have applied the modified ES99-algorithm to randomly chosen SL
dialogues (9,728 words).
It must be noted that we only used one annotator in our test, while in
the test reported in \cite{Eckert+Strube:1999} there were two
annotators. The precision and recall of the modified algorithm on our
dialogues were of 64.7\% and 70,4 \%, respectively. These results are
similar to those reported in \cite{Eckert+Strube:1999}.  Most of
the wrongly resolved anaphors are due to the fact that the 
algorithm cannot distinguish between discourse
deictics and vague anaphors. Some errors are due to missing
information on nominals referring to abstract objects, some depended
on the chosen discourse model.

In conclusion, both centering algorithms  and the ES99-algorithm  seem
to perform as well for Danish as for English. Future work consists in
testing the algorithms on more types of dialogue, identifying more
discriminating predicates and adding more lexical and domain knowledge
to the modified ES99-algorithm.  
%\bibliography{/users/costanza/media/biblio/media.bib}
\begin{thebibliography}{99}
 %
\bibitem{Brennan+al:1987}
Brennan, S.~F., Friedman, M.~W. and Pollard, C.~J.:
{A Centering Approach to Pronouns}.
In {\em Proceedings of the ACL-87}. Stanford University,California, 
USA  (1987) 155--162.
\bibitem{Byron+Stent:1998}
Byron,  D.,  Stent, A.:
 {A Preliminary Model of Centering in Dialog}.
In {\em Proceedings of the ACL-98}.
Universit\'{e} de Montr\'{e}al, Quebec, Canada  
(1998) vol~II, 1475--1477.
\bibitem{Eckert+Strube:1999}
Eckert, M., Strube, M.: 
Resolving Discourse Deictic Anaphora in Dialogues.
In {\em Proceedings of the EACL-99}. (1999) 37--44.
\bibitem{Grosz+al:1995}
Grosz, B., Joshi, A.~K. and Weinstein, S.:
 {Centering:A Framework for Modeling the Local Coherence of
  Discourse}.
 {\em Computational Linguistics}. \textbf{21(2)} (1995) 203--225
\bibitem{Grosz+Sidner:1986}
Grosz, B.~J., Sidner, C.~L.:
{Attention, Intentions, and the Structure of Discourse}.
{\em Computational Linguistics}. \textbf{ 12(3)} (1986) 175--284.
\bibitem{Kameyama:1998}
Kameyama, M.:
 {Intrasentential centering: A case study.}
 In Walker, M.,  Joshi, A.,  and Prince, E. editors. 
{\em Centering Theory  in Discourse}. Oxford University Press, 
Oxford, U.K. (1998) 89--112. 
\bibitem{Prince:1981}
Prince, E.~F.:
{Toward a taxonomy of given-new information}.
In Cole, P., editor, {\em Radical Pragmatics}.
 Academic Press (1981) 223--255.
\bibitem{Prince:1992}
Prince, E.~F.:
{The ZPG Letter: Subjects, definiteness, and Information-status}.
In Mann, W., Thompson, S.~A., editors, {\em Discourse Description.
  Diverse Linguistic Analyses of a Fund-Raising Text.}.
John Benjamins (1992) 295--325. 
\bibitem{Strube:1998}
Strube, M.:
 Never look back: An alternative to centering.
 In {\em Proceedings of the ACL-98}, 
Universit\'{e} de Montr\'{e}al, Quebec, Canada (1998) 
vol~II, 1251--1257.
\bibitem{Tetreault:1999}
Tetreault, J.R.:
{Analysis of Syntax-Based Pronoun Resolution Methods}.
In {\em Proceedings of the 37th ACL}. Maryland, USA (1999) 602--605.
  1999.


\end{thebibliography}

\end{document}






