\documentstyle[aaai,epsf]{article} 
\begin{document}
\title{An Application of Explanation-Based Learning to
       Discourse Generation and Interpretation}

% Submitted to 1998 AAAI Spring Symposium on 
%  Applying ML to DP - DUE TUES OCT 21!!!!! 8 pp max

\author{{\bf Nancy Green and Jill Fain Lehman}\\
        School of Computer Science\\
        Carnegie Mellon University \\ Pittsburgh, PA 15231 USA \\ 
        {\em nancy.green@cs.cmu.edu}}

\maketitle

\begin{abstract}
%\section*{Abstract}
\begin{quote}
This paper presents a brief description of Explanation-Based Learning (EBL),
and argues that it is an approach to machine learning with significant
potential for use in discourse processing.  More specifically, 
EBL can be used by systems that model discourse generation as goal-driven 
behavior, and that model discourse interpretation as recognizing the 
speaker's discourse goals.  As evidence, we describe
the discourse architecture of the NL-Soar dialogue system.
The architecture uses the EBL capabilities of Soar
to compile discourse recipes during discourse planning.  
The recipes can be reused to speed up discourse
generation and as a knowledge source during discourse interpretation.
\end{quote}
\end{abstract}

\section{Introduction}

This paper presents a brief description of Explanation-Based Learning (EBL),
and argues that it is an approach to machine learning with significant
potential for use in discourse processing.  More specifically, EBL
can be used by systems that model discourse generation as goal-driven 
behavior, and that model discourse interpretation as recognizing the 
speaker's discourse goals.  As evidence, we describe
the discourse architecture of the NL-Soar dialogue system.
The architecture uses the EBL capabilities of Soar
to compile discourse recipes during discourse planning.  
The recipes can be reused to speed up discourse
generation and as a knowledge source during discourse interpretation.

\section{Explanation-Based Learning}

{\em Explanation-Based Learning} (EBL) refers to an approach to
machine learning where a program learns by formulating an {\em explanation}
of why a single training example is an instance of the concept to
be learned.  This explanation is transformed into an operational 
description which can be used to identify new instances of the concept.
Formulating such an explanation requires domain knowledge.
In contrast to corpus-based approaches, EBL can make meaningful 
generalizations from a single example.
%This approach contrasts with inductive approaches which make use of
%many training examples. 
%and an inductive bias to constrain the search for a generalizaton.

In one of the first articles to survey and attempt to unify previous work
on explanation-based approaches, Mitchell et al. provide a definition of
and method for constructing an {\em explanation-based generalization} (EBG)
\cite{Mitchell-et-al-86}.  Knowledge about the training example and
domain is encoded as logical propositions and the process of finding an
explanation is characterized as finding a proof that the training example
satisfies a (non-operational) concept definition.
The proof is converted into an operational definition that can be used to 
identify other instances of the concept.
In other words, the explanation is used to find sufficient conditions for
recognizing new instances of the concept.

Dejong and Mooney propose a different characterization of explanation-based
approaches, which they term {\em Explanation-Based Learning} (EBL)
\cite{Dejong-Mooney-86} to reflect a broader range of phenomena than
considered by Mitchell et al.   While Mitchell et al. characterize
the approach in theorem-proving terms, Dejong and Mooney characterize
it in problem-solving terms, i.e., in terms of initial states, goal states,
operators, and plans to achieve the goal from the initial state.
Also, they distinguish two types of EBL systems.  In one, the explanation
is derived solely by an internal problem-solver making use of its domain 
theory.  While this approach is capable in theory of producing an optimal
solution, it may be inefficient.  Dejong and Mooney propose an alternative
approach to EBL in which the system constructs an explanation using
externally supplied ``hints'', which reduce the amount of search and which
bias the system towards certain explanations.  The hints are provided
to the system as a sequence of observed states and actions, representing
a partial explanation of how to achieve the goal.

To summarize the characterization of EBL given by Dejong and Mooney
(extending the one given by Mitchell et al.),
an EBL problem is said to consist of:
\begin{itemize}
\item a domain theory: a set of facts and inference rules about
      the domain and a library of primitive problem-solving operators and
      previously learned or hand-coded schemata (where a {\em schema}
      is defined as a partially-ordered set of operators for achieving
      a goal),
\item the goal state,
\item the initial world state, and
\item (optionally) an observed sequence of primitive operators which 
      specify (partially or completely) how to 
      achieve an instance of the goal. (If no observations are supplied, 
      then the system constructs a plan on its own to satisfy the goal.)
\end{itemize}

In the paper, they propose a domain-independent method for deriving
the explanation, and illustrate its application to the problem of
acquiring a schema for recognizing stories describing kidnapping events
from a single kidnapping narrative.
The domain theory provides schemata for actions described
in kidnapping narratives, as well as general inference rules
about this domain.  The goal state is the goal of the particular 
kidnapping narrative provided as input, e.g., that the kidnapper will
possess \$250,000. The initial state and observed operator sequence
is a story about a particular kidnapping event in the language of
the domain theory.  An explanation is derived and generalized from the
story.  The explanation is transformed into a schema with preconditions
(conditions under which the schema is applicable) and effects.

EBL has been used to learn rules for interpreting indirect speech acts
\cite{Schulenburg}.  Given a representation of the surface speech act
of an utterance used as an indirect speech act, the system uses the plan
inference technique of \cite{Allen80} to interpret the utterance.  EBL
techniques are then used to compile the chain of inference into rules for use
in future cases.

\section{An Integrated Discourse Architecture Using EBL}

We have developed an integrated discourse architecture for the NL-Soar 
dialogue system \cite{Lehman-JAIR}.
The goal of NL-Soar is 
a dialogue system enabling intelligent agents to communicate via
natural language with humans in task-oriented dialogues in restricted
domains.   Currently, inputs and outputs consist of written natural language.
The functional components of NL-Soar include sentence comprehension (parsing
and semantic interpretation), sentence generation (realization of
text), discourse generation, and discourse comprehension.
In the discourse architecture, discourse plan operators
or ``recipes'' are compiled automatically during discourse planning
using an EBL-style approach.  
In future situations, these discourse recipes are used to speed up 
discourse generation and as a knowledge source for discourse comprehension.
For a full description of the discourse architecture, see
\cite{Green-JAIR}.  In this paper, its features are summarized
and the use of EBL-style learning in it is explicated.

\subsection{Overview of Learning in NL-Soar}

NL-Soar is implemented using the Soar architecture
\cite{LairdRosenbloom,Gentle-Soar,Newell}.
Intended as an architecture for general intelligence,
Soar provides a general learning mechanism, called {\em chunking},
that operates automatically during problem-solving.
%Problem-solving is performed by applying operators to an initial state in 
%order to achieve some goal state.  
Problem-solving knowledge is encoded as productions (condition-action
rules) in the system.
As control returns from subgoals during problem-solving, Soar automatically
creates chunks, i.e., new productions which compile the results of the
problem-solving experience.  The conditions of a chunk reflect the 
aspects of the state that were relevant to achieving the subgoal.
The actions of a chunk reflect the changes to the state accomplished by
the subgoal.  (Both conditions and actions of chunks may contain variables.)
In future situations where the conditions of a chunk hold, Soar can apply
the chunk instead of performing the potentially costly problem-solving 
which gave rise to the chunk.  
Chunking can be regarded as a type of EBL, where the productions that
were applied during subgoaling constitute the explanation 
\cite{RosenbloomLaird86}.
The conversion of this explanation to chunks results in operational
knowledge which can be applied to future problem-solving. 

Although some aspects of the design of a system implemented in Soar
are determined by the Soar architecture (e.g., how production rules are
selected and applied, automatic chunking), a system builder's organization
of the production rule system contributes to the behavior of the system, 
including what types of chunks are acquired.
In NL-Soar, the production rule system has been organized so that 
%chunking will occur under certain circumstances during discourse 
%generation, and so that 
the resulting chunks will have certain properties
which determine their potential
use in discourse generation and interpretation.  
(The organization of NL-Soar at the discourse-level
closely follows that at the sentence-level.
For information on NL-Soar's sentence-level
comprehension and generation processes, see \cite{Lehman-JAIR}.
Also, note that chunking has been put to a variety of other uses in other 
systems built in Soar, e.g., 
\cite{MillerLaird,Miller-et-al,Huffman,Johnson-et-al}.)

\subsection{Discourse Architecture}

The input to discourse generation in NL-Soar is the shared state of
the dialogue (the {\em conversational record} \cite{thomason90})
and the speaker's non-shared beliefs and desires.  The output is
a sequence of primitive discourse actions to be 
realized by the sentence-generator, and their anticipated effects
(e.g., updates to the conversational record).
In NL-Soar, discourse generation is modeled as goal-driven behavior.
During discourse planning, however, chunking results in the
automatic creation of discourse recipes as a side-effect of planning.  
(We describe below how these recipes differ from 
traditional hand-coded recipes.)  Thus, planning is integrated
with learning.  In future situations, whenever a learned discourse
recipe is applicable, it is used instead of planning.    

To describe this process in EBL terms, 
the domain theory consists of (1) knowledge
of primitive discourse actions and their preconditions and effects,
and (2) the planning algorithm.
The goal state is the desired state of the dialogue, and
the initial state is the current state of the dialogue.  
The plan provides an {\em explanation} of how these effects can be achieved.
The explanation is then generalized to provide a discourse recipe,
describing an abstract discourse action and its preconditions
and effects.  

In addition to using the recipes to speed up generation,
NL-Soar uses the recipes acquired during discourse generation 
for discourse comprehension.  
The input to discourse comprehension is the syntactic
and semantic interpretation of an utterance and the conversational
record.  
Recognizing the speaker's meaning
is modeled as recognizing which recipe must have given rise to the
observed utterance and was intended to be so recognized, in virtue
of the agents sharing similar processing mechanisms, similar sets of 
recipes (acquired through similar experience), and the conversational
record.  The output is the set of updates to the conversational 
record specified by the instantiated recipe that was recognized.

For details about the planning and plan recognition algorithms, see
\cite{Green-JAIR}.

\subsection{Discourse Recipes}

NL-Soar acquires recipes by use of Soar's built-in chunking
mechanism.  Because of how the discourse generator component of NL-Soar's
production system is organized, all recipes have a similar form.
Each recipe consists of a set of chunks (learned condition-action
rules).  One of the chunks, the {\em proposal} chunk, specifies when 
the recipe is applicable for generation.  The conditions of this chunk
specify a generalization of the conditions that were tested during
the planning that resulted in this recipe, e.g., particular features of the
conversational record, and possibly non-shared beliefs and/or goals
of the speaker.  The action of this chunk is to allow the rest of the
chunks (called {\em implementation chunks}) of the recipe to fire.  
The implementation chunks perform updates to the conversational record
and put primitive discourse actions into the sentence generator's
input buffer.


\subsection{Example}

\begin{figure}
\begin{verbatim}
      UTTERANCE           DISCOURSE ACT
 P2:  Parrot101.          summons        
      This is Parrot102.  self-introduction
      I have a contact    inform-description-of
        bearing 260.       
      Over.               end-turn
 P1:  Parrot102.          summons
      This is Parrot101.  self-introduction
      Roger.              acknowledge
      I have a contact    inform-description-of
        bearing 270.       
      Over.               end-turn
 P2:  Parrot101.          summons
      This is Parrot102.  self-introduction
      Roger.              acknowledge
      That is your bogey. inform-same-object
      Over.               end-turn

\end{verbatim}
\caption{Sample Dialogue}
\label{SampleDialog}
\end{figure}

NL-Soar has been implemented in the air-combat training domain.
Figure~\ref{SampleDialog} shows a constructed dialogue
which is representative of transcripts of naturally occurring 
dialogues between human speakers in this domain.  
In the transcripts,
human speakers are communicating over a (simulated) two-way
radio channel while engaging in simulated air-combat exercises.
The goal of the current implementation of NL-Soar is for NL-Soar
to enable a human trainee to communicate with an
automated pilot agent playing the role of the other participant.
To comment on this sample dialogue, the speakers labeled P1 and P2
are known by the radio call-signs Parrot101 and Parrot102, respectively.
As in other domains involving two-way radio discourse
\cite{Gibbon}, a large portion of each turn is devoted
to discourse acts for regulating the turn \cite{Sacks74}
and grounding \cite{Clark89}.

Currently in NL-Soar, planning is performed for a single turn at a time.  
Thus, each learned recipe characterizes a set of similar
turns.  (The recipes do not specify the contents of the turn.  The
contents are determined when the recipe is instantiated.)  
As the sample dialogue shows,
a turn may consist of actions for 
managing the turn (e.g., {\em summons},{\em end-turn}),
grounding (e.g., {\em acknowledge}), and core
speech acts \cite{TraumHinkelman} (e.g., {\em inform-description-of}).

To give an example of a discourse recipe, let us consider the one
created during the
planning of turn 1 of Figure~\ref{SampleDialog}.
The left-hand side of 
the proposal chunk for this recipe can be paraphrased as:
\begin{itemize}
\item the agent's private beliefs include a belief that the agent is 
      certain that he can describe an object of type x (where
      x is a variable),
\item according to the conversational record, there is currently no 
      shared goal for the discourse segment,
      the medium is two-way radio, 
      and the turn is available, and
\item the agent has a private desire that speaker and hearer mutually 
      believe they are describing the same object, which is of type x.
\end{itemize}
The right-hand side of the chunk enables the recipe's implementation
chunks to fire in the current state.  (It is possible in theory for multiple
recipes to be proposed simultaneously.  Search control
productions would be used to decide among these alternatives.) 

The implementation chunks perform the following actions in parallel:
\begin{itemize}
\item records a discourse segment purpose \cite{Grosz86a}
      of {\em mb-describe-same-object}
      in the conversational record,
\item adds a {\em summons} 
      to the sentence generation input buffer,
\item adds a {\em self-introduction} 
      to the buffer,
\item adds an {\em inform-description-of} to the buffer,
\item adds an {\em end-turn} to the buffer, and
\item records the proposal to be made by the {\em inform-description-of} 
      act to the conversational record.
\end{itemize}
(Each of the above action is instantiated with information about
speaker, hearer, and the object.  Also,
although the discourse actions are added to the sentence generation
input buffer in parallel, the preferred relative order for realizing
each act is specified.)

To summarize the differences between the recipes acquired during 
chunking by NL-Soar and hand-coded recipes used in traditional systems:
\begin{itemize} 
\item They are designed for use in both generation and comprehension.
\item Whereas a traditional discourse recipe (as described in, e.g.,
      \cite{Cawsey,Hovy88,lambert,Litman87a,Maybury,Moore95})
      is a declarative specification,  
      which must be interpreted at run-time, these recipes are encoded
      as sets of productions.  The learned productions are incrementally
      acquired with experience, are in the same representation scheme
      as hand-coded productions, and are applied by the problem-solving
      architecture just as hand-coded productions are.
\item In the current implementation, the recipes do not encode relations
      between actions such as when an action contributes to the satisfaction
      of the preconditions of another action.  However, there is no reason
      in principle why the production system could not be designed so that
      this information was encoded in the recipes.
\item The discourse architecture enables the system to fall back upon 
      planning whenever the system has no recipe applicable to the current
      situation.
\end{itemize}

\subsection{Training}

Discourse recipes are acquired during training sessions in order
to provide real-time performance during deployment of NL-Soar.  However,
except for the time required for planning, there is no reason why
recipe acquisition cannot be performed during deployment.  NL-Soar
automatically falls back upon discourse planning whenever it has no applicable
discourse recipe.  During training,
an NL-Soar process is used to generate the contributions of both
participants in representative dialogues.  The contributions are
elicited by an interactive program which enables the system builder
to add the speaker's private beliefs and desires to working memory.
(During deployment, these beliefs and desires are generated by the
automated pilot agent.)
Discourse recipes are added to production memory by Soar
as a by-product of discourse planning during these sessions.
Note that only a single example of a class of turns is required
for each recipe. The recipes, which are in the same representational 
format as hand-coded productions, can be examined (and even modified) 
by the system builder if desired.
They can be saved and reloaded with hand-coded productions at a
later time.

\section{Comments}

We have not yet attempted to model dialogues with nesting, such as
clarification subdialogues.   
Also, the planning algorithm is simple and does not address issues
such as determining whether multiple goals can be achieved by the same
act, or whether the achievement of one goal interferes with the
achievement of another goal.  
However, our implementation demonstrates the potential of an architecture
integrating discourse planning and explanation-based learning.
Also, although Soar is not required in order to implement such an
architecture, we made use of it for two reasons.  First, we wanted to
see if the building blocks of NL-Soar's syntactic and semantic
processing components, could be adapted to discourse processing.  
More generally, Soar is an experimental platform for the development 
of computational models of intelligence.  
Thus, it is interesting to see how this platform
constrains the discourse architectures that can be developed.

Other uses of EBL might be incorporated into a discourse
architecture such as this.  One is 
the use of learning during discourse comprehension.  
For example, given an example segment of a persuasive text as a ``hint'', 
if a system can construct an explanation of how the effects are 
achieved by the text, then EBL techniques could be used
to derive a general discourse strategy for use 
in the future in comprehension or generation.  Another 
possibility is to use EBL during discourse planning to acquire search 
control knowledge rather than recipes.  
This search control knowledge would be used by the discourse planner 
in the future to make discourse planning more efficient.  
For example in PRODIGY, EBL is integrated with a means-end 
problem-solver to acquire domain-specific search control rules to improve 
future problem-solving performance in domains such as 
machine-shop scheduling \cite{Minton-et-al-89}.  These search control rules
help select operators during the planning process reducing the amount
of search performed by the planner.  Similarly, during discourse planning
search control rules could be learned to avoid exploring discourse 
strategies which would be ineffective.


\section{Conclusions}

We argue that EBL has potential for use in dialogue systems
that model discourse generation as goal-driven behavior, and that
model discourse interpretation as recognizing the speaker's discourse
goals.  As evidence, we describe the discourse architecture of 
NL-Soar.  The architecture uses the EBL capabilities of Soar to
compile discourse recipes during discourse planning.  The recipes
can be used to speed up discourse generation and as a knowledge 
source during interpretation.  

\section{Acknowledgments}
Research on NL-Soar was supported in part by the Wright Laboratory,
Aeronautical Systems Center, Air Force Materiel Command, USAF, and the
Advanced Research Projects Agency under grant number F33615-93-1-1330.
The views and conclusions contained in this document are those of the
authors and should not be interpreted as necessarily representing the
official policies or endorsements, either expressed or implied, of
Wright Laboratory or the U.S.~government.

\bibliography{/afs/cs.cmu.edu/user/ngreen/bibfile}
%\bibliography{/afs/cs.cmu.edu/project/soar/utc/nl/ngreen/bibfile}
% was: \bibliographystyle{alpha}, changed to below on Aug 22:
\bibliographystyle{aaai}
\end{document}








