\section{Learning Approaches to Spoken Language Analysis}

Our primary approach to speech translation within \spectrum will continue to
be anchored on our task-based interlingua representation.  The main approach
we have used in the past for analysis of spoken language into the interlingua
has been rule-based using full semantic grammars \cite{ward-90} and a robust
parser \cite{soup} designed to effectively parse with such grammars. This
approach has proven to be effective for large yet limited domains such as
travel planning, which can be broken down into several natural sub-domains.
Rather than focusing on the syntactic structure of the input, semantic
grammars list ways of expressing semantic concepts.  For example, the concept
of a service being available can be expressed with the phrases {\it we have
\ldots\/} or {\it there are \ldots\/}.  Because semantic grammars focus on 
identifying a set of predefined semantic concepts, they are relatively well
suited to handle the types of meaningful but ungrammatical disfluencies that
are typical of spoken language, and are also less sensitive to speech
recognition errors.  Semantic grammars are also relatively fast to develop for
limited domains, where the set of concepts being described is relatively
small.  However, they are usually hard to expand to cover new domains.  New
rules are required for each new semantic concept, since syntactic generalities
cannot usually be fully utilized.  

In the previous version of our speech-to-speech translation system we
developed a way to combine modular grammars in order to overcome some of the
problems associated with expanding semantic grammars to new domains.  Several
different semantic grammars for different sub-domains can share an underlying
library of shared grammar rules, thus reusing common underlying semantic
concepts while still being developed independently.  These can then be merged
at runtime into a comprehensive grammar for wide multi-domain coverage.  The
parser \cite{soup} applies multiple sub-grammars in parallel and stores the
outputs in a parse tree lattice.  A number of heuristics are used to rank the
paths through the lattice, including the likelihood of a string of words
belonging to a particular sub-domain module \cite{amta-98}.

Within \spectrum, our goal is to fully address the issues of domain
portability and the intensive manual labor inherent in the developemnt of 
semantic grammars.  We propose to focus on two different approaches that
are based on machine-learning to significantly reduce the amount of effort
required in expanding the coverage of semantic grammars to broader or new
doamins.

\subsection{The DA Classification Approach}

\begin{figure}[t]
  \centering \fbox{ 
    \centering \parbox[c]{130mm}{
      \centering \begin{math} \underbrace{
          \underbrace{\rm{Hello.}}_{a_1}}_{\tt{\scriptsize
            greeting}} \underbrace{ \underbrace{\rm{This\ is} }_{a_2}
          \underbrace{\rm{Bob.}}_{\tt{\scriptsize
              \parbox{11mm}{\centering
                person\\-name}}}}_{\tt{\scriptsize
            introduce-self}} \underbrace{
          \underbrace{\rm{I}}_{\tt{\scriptsize super\_who}}
          \underbrace{\rm{would\ like\ to\ book}}_{a_5}
          \underbrace{\rm{a\ flight}}_{\tt{\scriptsize
              \parbox{18mm}{\centering super\_flight\\-type}}}
          \underbrace{\rm{to\ Frankfurt.}}_{\tt{\scriptsize
              super\_destination}}}_{\tt{\scriptsize
            request-action+reservation+features+flight}}
      \end{math}}}
\caption{Example: Multi-level Analysis for an Input Utterance}
\label{cc-example}
\end{figure}

Within \nespole, we have begun developing a new Domain Action Classification
Parser, {\sc Dacp}, for analyzing task-oriented speech utterances.  The goal
of the parser is to analyze utterances directly into our domain-action (DA)
based interlingua representation.  Complete DA representations consist of a
speech-act, a collection of domain concepts and a list of arguments.  The {\sc
Dacp} parser operates in two stages.  In the first stage, the parser uses a
phrase-level semantic grammar for analyzing the input into a sequence of
arguments.  In the second stage, using the sequence of detected arguments and
the words in the utterance, the parser uses statistical classification methods
in order to identify the speech-act and the sequence of domain concepts that
form the Domain Action.  An example utterance and its levels of analysis is
shown in Figure~\ref{cc-example}.  The utterance {\tt I would like to book a
flight to Frankfurt} is analyzed first as a sequence of phrase arguments (such
as {\it to Frankfurt\/} analyzed as a {\tt destination}).  The sequence of
arguments then gets mapped to a speech-act, in this case {\tt request-action},
and a domain-concept --- {\tt reservation+features+flight}.

The first stage, parsing of argument level phrases is done using the robust
SOUP parser \cite{soup}.  The phrase-level semantic grammars are still
developed manually, but we expect to leverage coverage off of portions of our
current semantic grammars.  We also expect the phrase-level semantic grammars
to be far less domain dependent (thus far more portable) than complete
semantic grammars.

The second stage, speech-act and concept classification will be based on data
trainable classification technology.  We will experiment with hidden markov
models (HMMs), neural nets, and decision trees.  These techniques are by
design more robust and portable than complete semantic grammars, but their
accuracy depends on the availabilty of adequate accurate training data.

We have so far put together a baseline prototype of the new {sc Dacp} parser
and have tested it within the \nespole project.  Semantic grammars were
developed for analyzing the argumant-level concepts within the \nespole
travel-domain scenarios.  These grammars are significantly more compact and
were faster to develop than full semantic grammars.  The speech-act and
concept sequence classification task is currently done using TiMBL --- a
classifier based on a ``k-nearest neighbor'' approach \cite{TiMBL:00}.

One important question is whether the statistical methods used for classifying
strings of arguments into domain actions are accurate enough, and what amounts
of tagged data are required to obtain reasonable levels of performance.  To
assess this last question, we tested the performance of the current speech-act
and concept classifiers for the expanded travel-domain when trained with
increasing amounts of training data.  The results indicate that the classifier
currently detects DAs with about 50% accuracy, and that the performance
reaches a relative plateau at around 4000-5000 training utterances.  We see
these results as indicative that this approach should indeed prove to be
significantly easier to port to new domains.  Creating a tagged database of
this order of magnitude can be done in a few weeks, rather than the months
required for complete manual grammar development time.

All aspects of the {\sc Dacp} analyzer require significant further research
and development.  The main research issues are the following:

\begin{itemize}
\item {\bf Segmentation:} Developing methods for reliably segmenting
utterances that consist of multiple domain actions.  We will investigate using
statistical information that can model the likelihood of a boundry between
identified argument concepts as well as using knowledge from the interlingua
specification that defines well-formedness constraints on the sequences of
argumants that can belong to a single DA.  Other approaches will also be
considered.

\item {\bf Argument Parsing:} Investigating methods for dealing with ambiguity 
at the level of argument parses.  The underlying {\sc Soup} parser for
arguments currently uses a set of heuristics for selecting a single sequence
of argument parses for a given input utterance.  These were originally
developed for disambiguation when parsing with full semantic grammars and need 
to be revisited in the context of argument parsing.  We also intend to
consider passing multiple sequences of argument parses to the classification
stage of the parser, either in the form of an n-best list or in the form of a
lattice.

\item {\bf Classification Approaches:} Performing a detailed investigation of
several different classification approaches and analyzing their effectiveness
and appropriateness to the task of domain action classification.  These will
include the current k-NN approach (TiMBL), Decision Trees (i.e C5.0), Neural
Networks, Statistical Language Models and possibly others.  Both accuracy and
classification speed need to be taken into account.

\item {\bf Feature Set for Classification:} Investigating the set of features
that should be provided to the classifier for optimal classification
performance. The space of features includes the words in the utterance,
n-grams of words, information about whether words were parsable or not, the
semantic labels of the argument parses, the detected speech-act (for concept
classification),and contextual information (DA of previous utterance of the
same speaker and other speaker).  Additional features will also be considered.

\item {\bf Concept-sequence Classification:} Investigating whether concept
sequences that form the DA should be classified jointly or as individual
concepts that are then combined together.

\item {\bf Use of Interlingua Specification Constraints:}  Investigating how
to use the the well-formedness constraints of the interlingua specification in 
order to augment the statistical approach used by the classifier.  This
includes using information about which arguments are licensed by each DA,
information about which concept sequences are semantically allowed, and
devising fall-back strategies for cases where the best classified DA is not
legal according to the interlingua specification.

\item {\bf Portability Across Domains and Across Languages:}  Evaluating the 
extent to which the new {sc Dacp} approach is in fact more portable to new
domains and to new languages.
\end{itemize}


\subsection{Automatic and Interactive Semantic Grammar Induction}

To further facilitate the development of semantic grammar coverage for a
domain and in support of faster portability to new semantic domains, we plan
to develop a new approach to semantic grammar induction.  The premise here is
that once the interlingua representation for a new domain or sub-domain has
been defined, it is fairly fast and straightforward to develop a small core
semantic grammar for the new domain, based on a small set of example
utterance.  The most labor intensive and time consuming task is to then expand
the coverage of the grammar to correctly parse the wide variety of ways in
which concepts of the new domain can be expressed in spoken language. Grammar
induction tools can therefore significantly speed up this process.  Our past
experience has shown that our grammar and interlingua developers can annotate
utterances with their corresponding interlingua representations relatively
fast and with high reliability.  It is far more time consuming to expand the
coverage of the semantic grammars to correctly produce the interlingua
representations for new previously unseen utterances.  Our key goal is
therefore to develop tools for expanding the coverage of an initial core
grammar by learning new grammar rules semi-automatically using partial parse
information from the existing grammar and the ``target representation''
information provided by the interlingua.  We plan to first investigate the
extent to which grammar rules can be learned completely automatically, with no 
interaction with an actual human developer.  At a second stage, we plan on
adding interactivity, to fill in knowledge gaps and resolve ambiguity a more
reliable fashion.  Previous work within our project \cite{Gav00b} has 
already partly investigated the learning of grammar rules with user 
interaction.

\begin{figure}[t]
\centering
\vspace{-0.8in}
\centerline{\psfig{file=ben-tree-2.ps,height=5in,angle=270}}
%\resizebox{5in}{5in}{
%\includegraphics{ben-tree-2.ps}
%}

\vspace{-2.5in}

\begin{verbatim}
Original interlingua:
give-information+onset+symptom
(symptom-name=(abnormal,attribute=color_attribute),symptom-location=urine,
manner=sudden)

Learned Grammar Rule:
s[give-information+onset+symptom]
	( [manner=] [symptom-location=] *+became [adj:symptom-name=] )
\end{verbatim}
\caption{A reconstructed parse tree from the Interlingua}
\label{learned-tree}
\end{figure}


We have already begun implementing an initial prototype of the completely
automatic grammar induction component.  The automatic induction is based on
performing tree matching between a skeletal tree representation obtained from
the interlingua, and a collection of parse fragments that is derived from
parsing the new sentence with the core grammar. Extensions to the existing
rules are hypothesized in a way that would produce the correct interlingua
representation for the input utterance.  Figure~\ref{learned-tree} shows a
tree corresponding to an automatically learned rule.  The input to the
learning algorithm is the interlingua (shown in bold boxes in the figure) and
three parse chunks (circled in the figure).  The dashed edges are augmented by
the learning algorithm.  Preliminary tests of the current prototype have shown 
very promising results...

The main stages of processing can be seen in Figure~\ref{Ben-GI}.  All of the
above stages require significant research and development.  The main issues
to be addresed are the following:
\begin{itemize}
\item {\bf Tree Matching:}
\item {\bf Linearization:}
\item {\bf Hypothesis Generation:}
\item {\bf Rule Induction:}
\item {\bf Rule Management:}
\end{itemize}

Once these issues are well addressed, we will turn our attention to how to
boost the accuracy of the approach by adding user interaction for better 
ambiguity resolution and validation of the induced grammar rules.  User
interaction will play a role in the following ways:

...

The grammar induction techniques we plan to develop are complimentary to the 
work on the Domain-action Classification parser described earlier. The grammar
induction method can be used to learn either full semantic grammars or
semantic grammars limited to the argument-level representations, from which we
can then rely on the {\sc Dacp} parser to complete the analysis process.
We plan to investigate both, with the goal of devising the most effective
and accurate way to leverage from these two approaches.
