\documentclass{llncs}
\usepackage{examples}

\input{psfig.sty}

\newcommand{\colinterm}[1]{\textsc{#1}}
\newcommand{\system}[1]{\textsc{#1}}
\newcommand{\logic}[1]{\emph{#1}}
\newcommand{\intextquote}[1]{``#1''}
\newcommand{\scare}[1]{`#1'}
\newcommand{\dact}[1]{\texttt{#1}}
\newcommand{\jorncmt}[1]{\textbf{#1}}

\begin{document}

\pagestyle{empty}

\mainmatter

\title{Reconstructing Conversational Games in an Obligation-Driven Dialogue Model}

\titlerunning{Lecture Notes in Computer Science}

\author{J\"{o}rn Kreutel}

\authorrunning{J\"orn Kreutel}

\institute{SAIL LABS S.L., Roger de Ll\'uria, 50 \\ 
E-08009 Barcelona, Spain \\ 
\texttt{jkreutel@sail-labs.es}}

\maketitle

\begin{abstract}
Departing from a dialogue model that uses \colinterm{discourse obligations} as 
basic expressive means we will propose a set of inference rules that assign intentional
structures to sequences of dialogue moves. We then can demonstrate that from our point of
view \colinterm{conversational games} can be seen as macro-structures
which are decomposable into smaller functional units where the
coherence between the latter is explained in terms of obligations.
\end{abstract}


\section{Introduction}

In the course of the last decade, research in dialogue modelling has
come to pay increasing attention to the language-specific aspects of
dialogue. This tendency, which has resulted in dialogue being dealt
with as a phenomenon of the use of natural language in a social
context rather than as just a particular case of rational agency, is
underlined by the use of \colinterm{discourse obligations} as expressive
means that allow the modelling of the actions of dialogue participants
(DPs) in an explanatorily more adequate way than mere intention-based
approaches (see \cite{traum allen obligations}, \cite{kreutel
  matheson 1999}).

It is in the context of obligation driven models for dialogue that a
concept of \colinterm{information state} (IS) has been developed which has
proved to be of considerable influence in dialogue related research
(see \cite{poesio traum 1998}, \cite{traum trindi is-revision}). 
Our aim here is to sketch the outlines of a very simple model of IS 
using discourse obligations, which adheres to the formalisation principles 
proposed by the TRINDI workgroup that stresses the idea of dialogue being 
describable in terms of \colinterm{information state updates} (see \cite{traum trindi is-revision}).
We will propose a set of inference rules for the dialogue model outlined by 
Kreutel \& Matheson in \cite{kreutel matheson 1999}
 that operate on ISs and assign an
intentional structure to a sequence of dialogue moves. This way we can
show that a \scare{bottom-up} approach to dialogue modelling yields
results at the descriptive level that are equivalent to the ones
proposed in intention based explanations while proving to be superior as
far as its explanatory power is concerned. In particular, we will show how 
the structuring aspect of \colinterm{conversational games} can be reconstructed in 
terms of obligations.

Thus we intend to provide arguments for the strong attractiveness a model using 
information states and discourse obligations as expressive means has for dialogue 
related research in the academic field as well as in the area of 
practically applied language technology. 


\section{Information States and Intentional Structure}

Kreutel \& Matheson \cite{kreutel matheson 1999} assume a very basic notion of IS
which includes just the \colinterm{dialogue history} (DH) as a sequence of
moves, and a representation of the DPs' obligations (OBL).  The
dialogue acts used are a subset of those proposed by Poesio \& Traum \cite{poesio
  traum 1998}, where the acts are sub-classified into \colinterm{core
  speech acts} (\dact{assert}, \dact{ask}, \dact{accept}, etc.) and
\colinterm{argumentation acts} (\dact{answer}, \dact{info\_request}, etc.).
This classification captures the idea that any speech act may appear
in a wider discourse context, where argumentation acts characterise
the context-dependent actions of core speech acts.  Obligations are
represented as stacks of \dact{address} and \dact{answer} elements.

The updating of information states is done based on the notion of
\colinterm{information state update scenarios}.  Update scenarios are meant
to specify certain \scare{constellations} of IS, corresponding to
situations like the turnholder's replying to an assertion, to a
question, or to an assertion that is meant as an answer to a question.
Each scenario can be defined based on the information in IS, i.e. on
the overall structure of the DPs' obligations and the history of the
dialogue.

The intentional structure INT is built up by means of inference rules
given the information in DH. Departing from the idea that dialogue acts dispose 
of an \scare{expressive} function, which is to convey the mental 
state of the speaker (see \cite{sadock 1990}), we assume that 
from the occurrence of  certain dialogue acts in DH 
the DPs can infer each other's intentions and the way 
they are related and managed:

\begin{itemize}

\item Formally, we represent INT as a quadruple $<I,\gg,sat,drop>$, where I
is the set of the DPs' intentions, $\gg$ is the two-place relation of
\emph{immediate dominance} in I, which is defined on the base of the \emph{dominance}
relation proposed by Grosz \& Sidner \cite{grosz sidner 1986}, and $sat$ and $drop$ are 1-place
relations in I that correspond to the sets of satisfied and dropped
intentions, respectively. 

\item After each move, I is updated according to inference rules that associate dialogue acts with intentions, e.g. $i_a: shared\_belief(p)$ and $i_b: resolved(q)$ with an assertion of $a$ that $p$ and a question of $b$ whether $q$, respectively. In the same way, we infer $i_a: resolved(q)$ from $a$'s performance of an \dact{answer} or an \dact{info\_request} argumentation act.

\item $sat$, on the other hand, is determined by inferring contents of intentions from dialogue acts, e.g. $shared\_belief(p)$ from the acceptance of an assertion that $p$ or $resolved(q)$ from the acceptance of an assertion as an answer to a question whether $q$. An intention is said to be satisfied iff its content occurs in DH.

\item Finally, for updating $\gg$ we attach a new intention as immediately dominated by
the last intention which has neither been satisfied nor dropped.

\end{itemize}

Given these rules we assume the structure below as the representation of an ordinary
question-answer sequence:

\begin{examples}
\item \label{ex200}
\begin{tabular}[t]{l l}
A[1]: & Did Helen come to the Party?\\
B[2]: & No.\\
A[3]: & Ok.\\
\end{tabular}

\centerline{\psfig{file=fig1.eps,height=3.5cm}}

\end{examples}

As the tree shows, we assume that the intentions associated with
dialogue acts reformulate the idea that an askee adopts an
asker's desire for information when answering a question (see
\cite{cohen levesque 1990}): $i_1$ and $i_2$ are identical with
respect to their content, but individualised over the two DPs.  The
tree also captures the notion that the intention $i_3$ associated with
the assertion in [2], which is offered as an answer to the question,
is \emph{dominated} by the askee's intention that the question should
be resolved, and thus significantly differs from a discourse-initial
assertion due to its context.  As $i_1$ and $i_2$ have the same
content, satisfaction of the latter by A's acceptance of B's answer
automatically means satisfaction of $i_1$.\footnote{see \cite{kreutel matheson 1999} 
for the motivation to analyse the evaluation of an assertion that is 
meant as an answer to a question as a two-fold process involving the dialogue acts \dact{accept} and
\dact{accept\_answer} in example (\ref{ex200}).}

Having thus outlined how the model proposed by Kreutel \& Matheson \cite{kreutel
  matheson 1999} can be extended to allow for an account of the
intentional structure of dialogue, the following section will discuss the advantages 
of the obligation-driven model as opposed to the notion of conversational games.

\section{Reconstructing Conversational Games}

The notion of conversational games has proved to be very useful in
dialogue modelling from the descriptive (see \cite{eklundh-1983},
\cite{carletta coding manual}) as well as from the computational
(see \cite{lewin-1998}, \cite{pulman-1998}) point of view. However, in terms
of explanatory power the games approach runs into similar difficulties
as the ones pointed out by Traum \& Allen in \cite{traum allen obligations}
for intention-based approaches to dialogue in that capturing uncooperative actions 
is at best very awkward \emph{within} the concept of a game. We argue that our 
own approach reconstructs the structural aspects of the games model 
and extends the coverage to include some data for which an approach 
using games is arguably too rigid.

Following a proposal by Eklundh \cite{eklundh-1983} to associate conversational games
with intentions - or \scare{discourse segment purposes} in Grosz \& Sidner's terms 
(see \cite{grosz sidner 1986}) - we could associate the games
\dact{question-answer}, \dact{answer} and \dact{assert} with $i_1$,
$i_2$ and $i_3$ in (\ref{ex200}), respectively, thus labelling the
discourse segments that correspond to the intentions in our model 
with types of games. So far, then, on a descriptive level our treatment of INT coincides
with the basic structural mechanisms of the games model.  However the
latter has problems in providing a satisfactory explanation of
sequences of moves that deviate significantly from the
\scare{canonical} structure of a game, but which nevertheless can be
seen as very common in human interaction.  For instance:

\begin{examples}
\item \label{helen}
\begin{tabular}[t]{l l}
A[1]: & Did Helen come to the Party?\\
B[2]: & Did Jack come?\\
A[3]: & Yes.\\
B[4]: & Ok.\\
B[5]: & Then Helen didn't come.\\
A[6]: & Ok.
\end{tabular}

\centerline{\psfig{file=fig2.eps,height=3.5cm}}

\end{examples}
 
In terms of dialogue processing, either by humans or machines, the
idea of a conversational game allows a distinction of the moves that
follow the initial one in terms of \scare{preferred} or
\scare{dispreferred} moves (see \cite{levinson 1983},
\cite{eklundh-1983}, \cite{lewin-1998}) and assumes an increased
processing effort for all the cases which are considered to be
dispreferred.  According to this point of view, for
\dact{question-answer} games an assertion which provides an answer
will always be considered the preferred follow-up move to a question.

The possibility of the askee replying to a question with a question,
as in (\ref{helen}), which can be considered a reasonably common case
in information-oriented interaction (see \colinterm{insertion sequences} in
\cite{levinson 1983}), will thus have to be treated as an exception
along with requests for clarification or utterances that express the
askee's inability or unwillingness to answer.  Apart from the fact
that the latter falls completely outside the scope of the games model
(if one does not assume the contradictory notion of an
\scare{uncooperativity game}), this way of prioritising the range of
possible follow-up moves in a dialogue must be seen as too strict.
The obligation-driven approach, on the other hand, simply assumes that
a question obliges the askee to provide an answer which resolves the
question, and thus a situation where an askee replies with a question
in order ultimately to provide an answer can be seen as just an
alternative to the \scare{canonical} case.

However, in spite of their explanatory weakness conversational games
have proved to be of great use in speech and language technology and
can still be seen as one of the leading notions in dialogue related
research.  In particular, the possibility of modelling games as
recursive transition networks (see for instance \cite{lewin-1998}),
and thus of determining significant \scare{states} of a game, has made
the games model an attractive candidate for dialogue systems which
make use of probabilistic heuristics to influence the behaviour of,
for example, modules for speech and speech act recognition (see
\cite{wright-et-al-1999}, \cite{poesio-mikheev-1998}).  However,
as we have pointed out above, our model defines a set of update
scenarios as the framework for determining or interpreting the DPs'
actual actions.  In terms of scenarios, the ordinary question-answer
sequence in example (\ref{ex200}) can be analysed as follows:

\begin{examples}
\item
\begin{tabular}[t]{l l l}
A[1]: & Did Helen come to the Party? \\
&  \colinterm{reply\_question}\\
B[2]: & No. \\
& \colinterm{reply\_answer} $\supset$ \colinterm{reply\_assert}\\ 
A[3]: & Ok.
\end{tabular}
\end{examples}

While B's move in [2] takes place in the context of a scenario in
which B has to answer a question, [2] itself results in an information
state in which $DP_1$ (A) is obliged to \dact{address} [2] and $DP_2$ (B) is obliged to
\dact{answer} [1].  This constellation of the DPs' obligations
characterises a scenario in which $DP_1$'s actions can be interpreted as
expressing his evaluation of the answer provided by $DP_2$ and is identical
with the situation after A's move [5] in the more complex example below:

\begin{examples}
\item\label{istates3}
\begin{tabular}[t]{l l}
A[1]: & Helen did not come to the Party.\\
B[2]: & How do you know that?\\
A[3]: & Her car wasn't there.\\
B[4]: & Ok. But she could have come by bicycle.\\
A[5]: & I stayed there until 4am and she didn't show up.\\
B[6]: & Ok.
\end{tabular}
\end{examples}

With our model assuming the classification of information states in
terms of update scenarios as part of the expressive means we
propose an alternative to the games approach also in terms of the
model's capacity to feed back heuristic analyses to other modules in a
dialogue system -- in the same way that a games-based account allows
follow-up moves to be ranked.  So, for each scenario, probabilities
can be assigned to each admissible subsequent action thus allowing for
the interpretation of ambiguous or \scare{noisy} responses.  This way we
are able to introduce a notion of prioritisation, which we have
argued is problematic for the games approach in explanatory terms,
at a higher level in our model.  It should be noted that we have not
undertaken such an analysis; however, it seems clear that the
scenario-based account can be used to provide the same formal
properties as conversational games, and hence similar predictive power
can be assumed.

\section{Conclusion}

Beginning with a dialogue model which uses discourse obligations as
basic means to predict the actions of participants in a dialogue, we
have proposed a set of inference rules which operate on the
information in the dialogue history to determine a representation of
the DPs' intentions. We have shown that the structures generated by 
our rules can be reinterpreted in terms of the notion of conversational games.

We have suggested that the obligation-based approach is able to
reconstruct games structures at the descriptive level and also to
flexibly integrate probabilities as developed in the games framework.
In addition to this, however, taking into account the equivalence between
\scare{states} in a games model and \scare{scenarios} on the one hand,
and the definition of scenarios in terms of the DPs' obligations on
the other, we claim that conversational games should be seen as
structures that emerge from the DPs' acting according to the
obligations imposed on them rather than as primitives in the theory of
dialogue modelling.


\begin{thebibliography}{4}

\bibitem{carletta coding manual}
Carletta, J., Isard, A., Isard, S., Kowtko, J., Doherty-Sneddon, G., Anderson, A.:
HCRC Dialogue Structure Coding Manual.
Research Paper~82, 
Human Communication Research Centre, University of Edinburgh (1996)

\bibitem{cohen levesque 1990}
Cohen, P.R., Levesque H.J.:
Performatives in a Rationally-based Speech Act Theory.
In: Proceedings of the 28th Annual Meeting of the Association for Computational Linguistics,
University of Pittsburgh, Pittsburgh, Pa. (1990)

\bibitem{eklundh-1983}
Eklundh, K.S.:
The Notion of Language Game: A Natural Unit of Dialogue and Discourse.
University of Link\"oping, Department of Communication Studies (1983)

\bibitem{grosz sidner 1986}
Grosz, B.J., Sidner, C.L.:
Attention, Intentions, and the Structure of Discourse.
In: Computational Linguistics {\bf 12(3)} (1986) 175--204

\bibitem{kreutel matheson 1999}
Kreutel, J., Matheson, C.:
Modelling Questions and Assertions in Dialogue Using Obligations.
In: Proceedings of Amstelogue 99, University of Amsterdam (1999) 

\bibitem{levinson 1983}
Levinson, S.C.:
Pragmatics.
Cambridge University Press, Cambridge (1983)

\bibitem{lewin-1998}
Lewin, I.:
The Autoroute Dialogue Demonstrator: Reconfigurable Architectures for Spoken Dialogue Understanding.
Technical report, prepared by SRI International Cambridge Computer Science Research Centre for the UK Defence Evaluation and Research Agency, Malvern (1998)

\bibitem{pulman-1998}
Pulman, S.:
The {TRINDI} Project: Some Preliminary Themes.
In: Proceedings of the Twente Workshop on Language Technology (1998)

\bibitem{poesio traum 1998}
Poesio, M., Traum, D.:
Towards an Axiomatisation of Dialogue Acts.
In: Proceedings of the Twente Workshop on Language Technology (1998)

\bibitem{poesio-mikheev-1998}
Poesio, M., Mikheev, A.:
The Predictive Power of Game Structure in Dialogue Act Recognition: Experimental Results Using Maximum Entropy Estimation.
In: Proceedings of ICSLP-98 (1998)

\bibitem{sadock 1990}
Sadock, J.:
Comments on Vanderveken and on Cohen and Levesque.
In: Cohen, P., Morgan, J., Pollack, M. (eds.):
Intentions in Communication.
MIT Press, Cambridge/MA (1990)

\bibitem{traum allen obligations}
Traum, D., Allen, J.:
Discourse Obligations in Dialogue Processing.
In: Proceedings of the 32nd Annual meeting of the Association for Computational Linguistics (1994)

\bibitem{traum trindi is-revision}
Traum, D., Bos, J., Cooper, R., Larsson, S., Lewin, I., Matheson, C., Poesio, M.:
A Model for Dialogue Moves and Information State Revision.
TRINDI Deliverable D2.1 (1999)

\bibitem{wright-et-al-1999}
Wright, H., Poesio, M., Isard, S.:
Using High Level Dialogue Information for Dialogue Act Recognition Using Prosodic Features. 
In: Proceedings of the ESCA Workshop on Prosody and Dialogue, 
Eindhoven (1999)

\end{thebibliography}


\end{document}



