\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
human-engineered semantic grammars \cite{ward90} 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.
We used sub-domain grammars whose outputs were combined into 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{amta98},\cite{mtj00}.

Within \spectrum, our goal is to fully address the issues of domain
portability and the intensive manual labor inherent in the development 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
domains.

\subsection{The IF Interlingua}

\nespole uses an interlingua-based approach with a relatively shallow
task-oriented interlingua representation~\cite{icslp98}, that
was initially designed for the C-STAR consortium and has been
significantly extended for the \nespole project.  The interlingua
approach is well known to be beneficial when there are more than two
language pairs~\cite{Nirenburg:92}.  The \nespole interlingua,
called Interchange Format (IF), consists of four representational
components: (1) the speaker tag (``{\em a:}'' stands for agent, ``{\em
c:}'' for client); (2) the speech act (e.g. {\em thank}, {\em
give-information}); (3) a possibly empty sequence of concepts,
describing the focus (e.g. {\em +hotel}, {\em +room}); (4) a possibly
empty list of arguments-value pairs (e.g. {\em room-type=double}).
The following are three examples of utterances tagged with their
corresponding IF label:

{\small
\begin{enumerate}
\item
{\tt Thank you very much}\\
{\em c:thank}
\item
{\tt And we'll see you on February twelfth}\\
{\em a:closing (time=(february, md12))}
\item
{\tt There is an hotel in the town}\\
{\em a:give-information+existence+accommodation
(ac\-com\-mo\-dation-spec=hotel, location=town)}
\end{enumerate}
}

\noindent
The same interlingua formalism will be used in the \spectrum project, with
appropriate extensions for coverage of the new domains and sub-domains.

\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.  A DA is
a combination of speech acts and concepts such as {\tt
give\--in\-for\-ma\-tion\-+ex\-ist\-ence\-+ac\-com\-mod\-ation} in the
examples above.  Complete IF 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
existing 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 availability 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 argument-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}.  The training data is 
a corpus of dialogues that were hand-tagged with DAs.

Two important questions are 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 these two questions, we recently 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 of a ten-fold cross-validation experiment indicate that the classifier
currently detects DAs with about 50\% accuracy (when the complete training
corpus is used), 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.  Furthermore, even with 50\% correct classification, when
the {\sc Dacp} parser was incorporated into our end-to-end translation system,
translation accuracy on an unseen test set was around 65\%.  We believe this
indicates that when fully developed, the {\sc Dacp} approach will be able to
produce accuracy levels comparable with manually well developed semantic
grammars.

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 boundary between
identified argument concepts as well as using knowledge from the interlingua
specification that defines well-formedness constraints on the sequences of
arguments 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
utterances.  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 in 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 (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
promising results.

\begin{figure}[t]
\centering
\centerline{\psfig{file=Ben-GI.ps,height=3in}}
\caption{Stages of Processing in Automatic Grammar Induction}
\label{Ben-GI}
\end{figure}


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 addressed are the following:

\begin{itemize}
\item {\bf Tree Matching:}
The skeletal tree is constructed by a reverse mapping from the
interlingua. Although the use of a semantic grammar makes such a mapping
easier, in certain cases the mapping produces more than one possible skeleton.
The tree matching algorithm thus needs to match parse fragments against a
collection of skeletons, and give an indication of the quality of the matches.
The algorithm could be made more robust by adopting approximate or
error-correcting matching techniques.

\item {\bf Linearization:}
Since the ordering of the meaning components within an interlingua is not
significant, the matches between a skeletal tree and the parse fragments need
to be linearized (reordered) with respect to the actual word ordering in the
utterance. The process also needs to detect any cross-branch violations, where
one meaning component is mapped to multiple non-contiguous words. The
violations can then be eliminated by certain meaning-preserving tree
transformations. Finally if more than one linearization is possible, the
algorithm needs to give indication of the quality of each linearization.

\item {\bf Hypothesis Generation:}
At this stage only a partial parse tree is reconstructed by attaching the
matched parse fragments with the skeletal tree. For any remaining unparsed
words and the meaning components which are not mapped with any words, the
correspondences between them needs to be hypothesized. The process could
benefit from using additional knowledge sources, such as statistical language
models or ontological information, to reliably map words to their most
relevant meaning components. Heuristics on which types of words/meaning
components need to be mapped first could also be helpful to achieve higher
accuracy.

\item {\bf Rule Induction:}
At this stage a complete parse tree is reconstructed, and a set of rules which
can be used to produce the tree are read off from the tree. The rules can be
made more robust by taking optionality and repeatability of part of the
right-hand side of the rules into consideration.

\item {\bf Rule Management:}
The rules induced are inserted back to the core grammar at this stage. In
updating the core grammar the algorithm should minimize the impact on the
existing rules so that the performance of the combined grammar does not
degenerate. It is also desirable to merge or rewrite rules to make the updated
grammar compact.  Theoretical results have shown that detecting rule
subsumption is an undecidable problem, thus further constraints that are
appropriate for a specific application domain need to be introduced to achieve
these goals.
\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:

\begin{itemize}
\item {\bf Learning Confirmation:}
Theoretical results have shown that grammar learning using only positive
examples is not feasible \cite{Gol67}. To avoid over-generalization, user
interactions can be introduced at the stage of hypothesis generation and rule
induction to confirm the learning results. However the interactions should be
designed in such a way that they do not require linguistic sophistication from
the users. For example, in hypothesizing correspondences between unparsed
words and unmapped meaning components, the system could generate alternative
utterances by realizing the meaning components with the other words known to
map to the components, and ask the user if the utterances convey legitimate
meaning. The correspondences can then be established if a confirmation is
obtained. Other alternative ways of taking advantages of user interactions
include asking ontological questions about unparsed words, and hypothesizing
the correspondences in light of the obtained ontological relations between the
words and the meaning components.

\item {\bf Proactive Learning:}
With user interaction the system can not only ask confirmation questions when
learning from problematic utterances, but is also able to resolve grammar
ambiguities by proactively planning experiments, i.e., by generating
utterances from potentially ambiguous rules and asking the user for
confirmation. This will enable the system to generalize the grammar even when
the relevant data is unknown at the point of learning.

\item {\bf Acquiring New Concepts:}
In addition to the incomplete grammar coverage, an utterance could be deemed
ungrammatical because of the lack of the appropriate concepts in the
interlingua. Via user interactions the system will be able to detect such
errors and initiate an interactive process to acquire the missing concepts,
thus making them available for later use. The interactive process itself
requires another set of grammars, for which the grammar learning approach
could also be useful.

\end{itemize}

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.
