% Edit History
%
% Initial version:	Jonathan, 3/12/2008, ~6:30pm   Short version of Feature Detection paper
% Revision 1:           Lori, 3/13/2008, ~ 12:30am     Turned into position paper (Major rewrite)
% Revision 2:           Jon, 3/14/2008, ~ 12:00pm      Minor changes, added references
% Revision 3:           Lori, 3/14/2008, ~ 3:00pm      Added content
% Revision 4:           Jon, 3/14/2008, ~ 8:00pm       Shortened, added examples, & smoothed


%
% http://www.ling.ohio-state.edu/acl08/cfp.html


% NOTES:
% SOUND BYTES. Summarize, but don't be vague.
% Nitty gritty on 1 key point.
%
% Evaluation is important. Emphasize validity, e.g. unseen test data.


% Template file: acl08.tex
% Contact: nasmith@cs.cmu.edu

\documentclass[11pt]{article}
\usepackage{acl08}
\usepackage{times}
\usepackage{latexsym}
\usepackage{graphicx}
\usepackage{enumitem} % Variable space between list items
\setlength\titlebox{5.75cm}    % Expanding the titlebox

\title{Morpho-Syntax or Bust: \\ Why Translation into Some Languages is Busted Without It}

% \author{Jonathan H. Clark, Lori Levin, Robert Frederking \\
%  Language Technologies Institute \\
%  Carnegie Mellon University \\
%  Pittsburgh, PA 15213, USA\\
%  {\tt {jhclark, lsl, ref}@cs.cmu.edu}}
\date{}

\begin{document}
\maketitle
\begin{abstract}
  This position paper argues that the time is ripe for incorporating
  morphosyntactic constraints in to Statistical Machine Translation
  (SMT).  Morphosyntactic constraints, including agreement and case
  marking constraints, cannot always be captured by language models
  because the words that constrain each other may be separated by many
  words.  However, Statistical Syntax-based MT (SSMT) systems can now
  provide enough structure to express morpho-syntactic constraints.
  We describe how morpho-syntactic constraints can be learned by one
  hybrid MT system. We also highlight the fact that resources for
  training morpho-syntactic constraints already exist in the LDC's
  LCTL language packs, which contain a carefully constructed
  elicitation corpus of simple sentences, dense with examples of how
  morpho-syntax in encoded in each language pair.

\end{abstract}

\section{Introduction}

Recently, machine translation has recognized the potential for syntax
and structure to produce higher quality translations. These methods
have lead to systems that leverage structure to outperform traditional
phrase-based systems~\cite{chiang-hiero05}. However, these top systems
have not yet explored the depth of morphosyntax.  Morphosyntax
includes those parts of grammar that are expressed by morphemes rather
than by word order or separate words.  It covers phenomena such as
case marking, agreement between verbs and their subjects (and objects
in some languages), and agreement between nouns and their dependents
such as adjectives and numeral classifiers. 

Various methods of incorporating morphosyntactic information into
translation models have also been explored. In Huang and
Knight~\shortcite{huangknight06}, the need for more specific grammar
rules is argued via the relabeling of non-terminal
symbols. Bonneau-Maynard et al.~\shortcite{bonneau07} argue that
translation can be improved via the incorporation of morphosyntax in
the form of a part of speech (POS) language model. However, the
morphosyntax goes well beyond POS tagging.

% Most SMT systems rely on language models to choose the most
% likely target language sentence.  However, much of morphosyntax is
% beyond the capabilities of current language models because the words
% that constrain each other may be separated by many intervening words.
% Morphosyntax is nevertheless critical to comprehension of most
% languages. (English and Chinese being notable exceptions.)  We will
% present several examples of morphosyntactic constraints whose span is
% beyond the limits of simple language models.  We will remind readers
% of how these constraints are handled in good, old-fashioned
% unification based grammars, and we will show how morphosyntactic
% constraints are learned and used in one hybrid syntax-based MT
% system. 

% We also encourage readers to use an existing resource for
% experimenting with morphosyntactic constraints.  The language packs
% for less commonly taught languages (LCTL) that are available from LDC
% each contain a parallel corpus 3000 sentences that are designed for
% training of morphosyntactic constraints.  Language packs are available
% for Thai, Bengali, and Urdu, and may be available for other languages
% in the future.  We will describe the logic behind the 3000 sentences
% as well as additional resources that are available from our web site
% such as corrected translations, manually produced word alignments, and
% dependency trees with morphosyntacic features for each sentence.

\section{A note on syntax and language typology for speakers of
English and Chinese}

Syntax is often defined as the part of linguistics that deals with the
structure of sentences.  However, structure is not an end in itself.
One of the main functions of syntax is to encode meaning, for example
to identify the participants in an event such as an agent and a
patient argument and distinguish them from each other so that hearers
know who was acting on who.  

It is easy for English speakers to forget the importance of
morphosyntactic constraints in the process of identifying the
participants in an event.\footnote{This is is well known to many ACL
participants, especially those who speak Slavic languages.}  In
English, word order is the main mechanism for distinguishing agent
from patient.  The difference between {\it Sam interviewed Sue\/} and
{\it Sue interviewed Sam\/} is purely one of word order.  However, in
most languages, agent and patient are identified by agreement and/or
case marking, not by word order.  For example, the three Russian
sentences below all mean {\it Tanya killed Masha\/}.  The nominative
{\it -a\/} suffix identifies the agent and the accusative {\it -u\/}
suffix identifies the patient.  Generating case markers therefore
critically affects whether or not the sentence can be understood as
intended.  

\begin{centering}
\texttt{\noindent
Tanja ubila Ma\v{s}u. \\
Tanja Ma\v{s}u ubila. \\
Ma\v{s}u ubila Tanja. \\
}
\end{centering}
The danger here is clear: While neglecting English morphosyntax
typically results in a sentence that sounds a little strange,
neglecting Russian morphosyntax results in an utterance that is
unintelligible.

\section{The limits of language models}

Language models are commonly used in MT systems to choose target
language sentences from a lattice or n-best list, and have been
successful in systems where English is the target language.  However,
modern techniques based language models are limited by the length of
the n-grams they are based on.  Dependencies often exist between words
that are more than n words away from each other.  This would be often
be the case in a language like Urdu or Hindi, where the verb agrees
with the subject, but they are typically not next to each other since
the typical word order in Urdu and Hindi is subject-object-verb. This
distance can be very long, as evidenced by the 12 word separation in
Figure~\ref{sv_agreement}. It has also been pointed out that in
languages that have numerical classifiers, the classifier and the noun
it modifies may often be more than three words
away~\cite{zhang08}. Such agreement would be very difficult for a
language model to cope with. Even using a suffix array
LM~\cite{callison-burch05} or other techniques based on very long
n-grams LM~\cite{carbonell06}, n-grams of this length become very
rare.

\begin{figure*}[ht]
\fbox{
\begin{minipage}{6.4in}
\begin{center}

\newcommand{\s}{@{\hspace{4pt}}}
\begin{tabular*}{\textwidth}{l\s l\s l\s l\s l\s l\s l\s l\s l\s l\s l\s l\s l\s l\s l\s l\s l\s l\s l\s l\s l\s l\s l\s l\s l\s l\s l\s l\s l\s l\s l\s }
{\bf ek} & {\bf talb} & alm & arshad & jo & mchhlyoN & ke liye & pani & maiN & aata & phink & {\bf raha} & {\bf tha} \ldots \\
{\bf a.\scriptsize SG} & {\bf student} & named & Irshad & who & fish & for & water & in & flour & throw & {\bf \scriptsize PROG.SG.M} & {\bf be.\scriptsize PAST.SG.M} \\
\end{tabular*}
\normalsize
``A student named Irshad who was throwing flour in the water for the fish \ldots''

\end{center}
\end{minipage}
}
\caption{An Urdu example from the LDC's LCTL language pack showing subject-verb agreement being separated by 12 words.}
\label{sv_agreement}
\end{figure*}


% Limits of context-free grammars
%Even most syntax-based systems would not be able to detect
%this problem without using a huge number of non-terminals, each marked
%for all possible agreements. 

A syntax-based system might be able to check this sort of agreement if
it produced a target-side dependency tree as in Ding and
Palmer~\shortcite{ding-acl05}. However, we are not aware of any
systems that attempt this. That said, the correct hypotheses, which
have correct agreement, will likely be produced as hypotheses of
traditional beam-search MT systems, but their features might not be
able to discern the correct hypothesis, allowing it to fall below the 1-best or out of the beam entirely.

% Returning to the example of subject-verb, consider the following Urdu
% sentences: \\

% \footnotesize
% \begin{tabular}{cccccc}
% Danish & ne  & Amna & ko & sza & di \\
% Danish & \scriptsize ERG & Amna & \scriptsize DAT & punish & give.\scriptsize PERF  \\
% \end{tabular}
% \indent ``Danish punished Amna.''

% \footnotesize
% \begin{tabular}{cccccc}
% Danish &Amna &ko &sza &dita &hai \\
% Danish &Amna &\scriptsize DAT &punish &give.\scriptsize HAB &be.\scriptsize PRES \\
% \end{tabular}
% \indent ``Danish punishes Amna.'' \\
% \normalsize
% These examples show the split-ergativity of Urdu in which the ergative
% marker {\it ne} is used only for the subject of transitive, perfect
% aspect verbs. In particular, since these sentences have the perfect
% aspect marked on the light verb {\it di}, a closed
% class~\cite{poornima08},

\section{Good, old-fashioned unification based grammars}

% For example, {\it student\/} is not next to {\it studies\/} in {\it
%   The student that the teachers like studies linguistics\/}, but it is
% the head of its noun phrase {\it the student that the teachers
%   like\/}, which is in a local relation with the verb {\it studies\/}.
% The property of singular number is passed up from {\it student\/} to
% the noun phrase that it heads, and then a constraint is enforced
% locally between that noun phrase and the verb.

% AVENUE~\cite{carbonell:amta02}

Unification based grammars make use of phrasal heads and constraints
that hold between constituents rather than between words. By
constructing a feature-rich grammar in a framework that allows
unification-based feature constraints, we can prune these bad hypotheses
having disagreement from the search space thereby reducing search
errors. Consider the example in Figure~\ref{sv_agreement}. Using a
resource such as an elicitation corpus, we can induce a grammar that
percolates a feature up from the VP containing {\it raha tha}
indicating that it requires a subject that is singular. Likewise, the
NP containing {\it ek talb} will percolate a feature up through the
phrasal heads indicating that the subject is in fact singular. If,
during translation, a hypothesis is proposed that does not match these
constraints, unification will fail and the bad hypothesis will be
rejected~\footnote{If the reader is unfamiliar with Unification
  Grammars, we refer you to~\cite{kaplan95}}.

\section{Learning morphosyntactic constraints in a hybrid MT system}

In our research, we have developed a hybrid MT system that uses
syntactic transfer rules as well as statistical decoding.  The grammar
rules are syncrhonous context free rules that relate a source language
strucure such as adjective followed by noun to a target language
structure such as noun followed by adjective.  The rules are augmented
with unification, which serves several purposes: passing features up
from heads to the phrases that they head, applying morphosyntactic
constraints in the source language to eliminate ambiguity, passing
meaningful morphosyntactic information such as number and tense from
the source to the target language, and enforcing morphosyntactic
constraints in the target language in order to ensure grammaticality.
The rules can be written by a human or can be automatically learned.
Over the last 5 years we have seen that rules can be learned
automatically and that baseline systems without rules can be improved
by the addition of rules. (Self-citations will be provided.)

In our MT system, morphosyntactic constraints can be learned
automatically or written by hand.  {\it Feature Detection} is the
process of determining from an annotated corpus which feature values
(e.g. singular, dual, plural) have a distinct encoding (i.e. different
morphemes or ordering) in a target language.  The input to feature
detection is an {\it elicitation corpus\/} (as described below).  The
output is a set of discoveries such as ``negation is marked by a verbal
affix,'' ``there is agreement in gender among the elements of the noun
phrase,'' or ``this language distinguishes between dual and plural
number.''  Feature detection has two purposes:  to tell the automatic
rule learner which rules are likely to need unification-based
constraints, and to guide an active learning process called {\it
navigation\/}, which decides which piece of data is the most valuable
to train on next.  The goal of navigation is to reduce the cost of
data aquisition by achieving similar performance with less training
data.  

One might argue that feature detection merely discovers information
that is available in grammatical sketch or reference grammar of a
language. However, these sketches often focus on the ``interesting''
features of a language, rather than those that are most important for
machine translation.  Feature detection, on the other hand, allows
allows us to specify which features we need to analyze. 

Furthermore, feature detection goes beyond what is grammaticalized in
the morphology of the language and also discovers what is expressed in
{\it constructions\/}~\cite{kay02}.  For example, reference grammars
and textbooks for Japanese may say that there is no morpheme for
marking future tense.  It generally uses the same morphology as
present tense.  However, it may be expressed by circumlocutions such
as \emph{watashi wa gakoo ni iku yode desu} (lit. \emph{``I have a
  plan to go to school.''}) for {\it I will go to school\/}. Feature
detection is capable of detecting such constructionalized encodings of
language features so that they can be used in
translation. (Self-citations will be provided.)

\section{The Elicitation Corpus}

Though many modern corpora contain feature-annotated utterances, these
corpora are often not designed for feature detection. For this
purpose, we use an Elicitation Corpus (see
Figure~\ref{example_sentence}), a corpus that has been carefully
constructed to provide a large number of {\it minimal pairs\/} of
sentences such as {\it He sings\/} and {\it She sings\/} so that only
a single feature (e.g., gender) differs between the two sentences. If
two features had varied at once (e.g. {\it He sings\/} vs {\it It
sang\/}) or lexical choice varied (e.g. {\it He sings\/} vs {\it She
reads}), then making assertations about which features the language
does and does not express becomes much more difficult. Though any
feature-annotated corpus can be used in feature detection, the amount
of useful information extracted from the corpus is directly dependent
on how many minimal pairs can be formed from the corpus.

The Elicitation Corpus is described in detail in our other
publications.  (Self-citations will be provided.)  It is a set of
about 3100 feature structures, which are essentially dependency trees
annotated with many morphosyntactic features.  Each feature structure
represents a meaning that we want to elicit in the target language.
Accompanying each feature structure, there is an English sentence that
expresses the meaning.  A literate, bilingual speaker translates the
English sentences (not looking at the feature structure!)  into his or
her language and graphically aligns the words.  If there are meanings
that are not clearly expressed in English, a contextual hint is
provided for the translator.  In Figure~\ref{example_sentence} the
translator is informed that the sentence is supposed to be interpreted
as a habitual action.  

The Elicitation Corpus covers things that are found in all languages
such as negation ({\it He didn't sing\/}), questions ({\it Did he
sing?\/}), and possession ({\it the student's book\/}).  It also
covers things that are not found in all languages such as distinctions
between formal and informal pronouns, the existence of different past
tenses with different degrees of remoteness, and the existence of dual
number.  It is also constructed to find dependencies between elements
such as agreement of nouns and verbs in number, gender, and person,
and it also covers interactions of features such as case marking and
tense, as in the split ergativity of Hindi and Urdu where
case marker is used only in a particular tense.  

The Elicitation Corpus is included in the LCTL language packs that are
available from LDC in Thai, Bengali, Urdu, Hungarian, Punjabi, Tamil,
and Yoruba (See http://projects.ldc.upenn.edu/LCTL/).  However, the
language packs contain only the English sentence and its translation.
To promote research in this area, we are providing additional
resources as illustrated in Figure~\ref{example_sentence} that are
downloadable from the Web at (URL anonymized for review).  These
include a dependency feature structure for each sentence, alignment of
the English and target language words, and the constituent structure
tree for Urdu.

\begin{figure}[t]
	\begin{center}
	\fbox{
	\begin{minipage}{\textwidth}
	\begin{tabbing}
	context: \= Maria bakes often or habitually. \\
	srcsent: \> Maria bakes cookies . \\
	tgtsent: \> Maria hornea galletas . \\
	aligned: \> ((1,1),(2,2),(3,3),(4,4)) \\
	fstruct: \> ((actor ((gender f)(anim human))) \\
                 \>(undergoer ((person 3))) (tense pres)) \\
	cstruct: \> (S1 (S (NP (NNP Maria)) \\ 
                 \> (VP (VBZ bakes) (NP (NNS cookies)))))
% 	fstruct: \> [f1]( [f2](actor ((gender f)(anim human))) [f3](undergoer ((person 3))) (tense pres)) \\
% 	cstruct: \> [n1](S1 [n2](S [n3](NP [n4](NNP Maria)) \\
% 		 \> [n5](VP [n6](VBZ bakes) [n7](NP [n8](NNS cookies)))))
	%phimap: \> phi(n1)=f1; phi(n3)=f2; phi(n7)=f3; \\
	%headmap: \> h(n1)=n2; h(n2)=n5; h(n3)=n4; h(n4)=n4; h(n5)=n6; h(n6)=n6; h(n7)=n8; h(n8)=n8;
	\end{tabbing}
	\end{minipage}
	}
	\caption{An example Spanish-English pair from an elicitation corpus.}
	\label{example_sentence}
	\end{center}
\end{figure}

Note that the dependency feature structures are the same for all
languages -- a kind of interlingua of grammar -- even if not all of
the features are expressed in the morphosyntax of each languages.

\section{Our Position and Recommendations}

We make the following recommendations to researchers working on
syntax-based SMT:

\begin{itemize}[itemsep=0pt]
\item Research target languages other than English.  This will make
  future MT systems more accessible to people around the world for
  international business, maintenance of language vitality, and
  security.
\item Use the Elicitation Corpus in the LCTL language packs to
  experiment with automatic learning of morphosyntax.
\item Use phrasal heads and unification based constraints to capture
  morphosyntactic dependencies whose span is larger than your n-grams.
\end{itemize}

\section{Acknowledgements}

We would like to thank our colleagues for their helpful input on this
paper. This work was supported by a grant from the National Science
Foundation.

% ACKNOWLEDGEMENTS FOR FINAL VERSION
% Abhaya, Vamshi, Alon, NSF Grant, Purnima, Kavita, Asim, Paul. Keisuke for Japanese example

\bibliographystyle{acl}
\bibliography{references_acl2008}

\end{document}
