Stochastic Inversion Transduction Grammars, with Application to Segmentation, Bracketing, and Alignment of Parallel Corpora

1 Introduction

We introduce a general formalism for modeling of bilingual sentence pairs, known as an inversion transduction grammar, with potential application in a variety of corpus analysis areas. Transducer models, especially of the finite-state family, have long been known. However, finite-state transducers impose identical ordering constraints upon both streams, confining their applicability to NLP tasks to narrowly restricted do­ mains outside of which transduction has received relatively little attention. The inversion transduction grammar formal­ ism skips directly to a context-free rather than finite-state base and permits one extra degree of ordering flexibility, while re­ taining properties necessary for efficient computation, thereby sidestepping the limitations of traditional transducers.

In tandem with the concept of bilingual language model­ ing, we propose the concept of bilingual parsing, where the input is a sentence-pair rather than a sentence. Though inver­ sion transduction grammars remain inadequate as full-fledged translation models, bilingual parsing with simple inversion transduction grammars turns out to be very useful for parallel corpus analysis when the true grammar is not fully known. Parallel bilingual corpora have been shown to provide a rich source of constraints for statistical analysis (e.g., Brown et al. I 990; Gale & Church I 991; Gale et al. 1992; Church 1993; Brown et al. I 993; Dagan et al. 1993; Fung & Church I 994; Wu & Xia 1994; Fung & McKeown 1994). The primary purpose of bilingual parsing with inversion transduction gram­ mars is not to flag ungrammatical inputs; rather the aim is to extract structure from the input data which is assumed to be grammatical, in kindred spirit with robust parsing. Sample applications to segmentation, bracketing, phrasal alignment, and parsing are surveyed later in this paper. The formal­ ism's uniform integration of various types of bracketing and alignment constraints is one of its chief strengths.

We begin below by laying out the basic formalism, then show that reduction to a normal form is possible. Afterwards we introduce a stochastic version and give an algorithm for finding the optimal bilingual parse of a sentence-pair. The formalism is independent of the languages; we give exam­ ples and applications using Chinese and English, because lan­ guages from different families provide a more rigorous testing ground.

2 Inversion Transduction Grammars

As a stepping stone to inversion transduction grammarss, we first consider what a symmetric context-free transduction grammar (CFTG) would look like. The utility of finite-state transducers is well-known for narrow tasks such as nominal, number, and temporal phrase normalization, text-to-speech conversion, and analysis of inflectional morphology (Gazdar & Mellish 1989), but for general corpus analysis FSTs are inadequate.

By transduction we mean that two output streams are gener­ ated, one for each language. (Transducers are often presented as having one input and one output stream, but this view works better for deterministic finite-state machines than for the non-deterministic models we are using here. Moreover for our application the two languages' role is symmetric.) In a CFTG, every terminal symbol is marked for a partic­ ular output stream. Thus, each rewrite rule emits not one but two streams. For example, a rewrite rule of the form A -+ Bx1 Y2C z 1 means that the terminal symbols x and z are symbols of the language £ 1 emitted on stream I, while y is a symbol of the language L 2 emitted on stream 2. It follows that every non terminal stands for a class of derivable substring pairs.

We can use a CFTG to model the generation of bilingual sentence pairs. As a mnemonic convention, we usually use the alternative notation A -+ B xI y C z If to associate matching output tokens. Though this additional information has no formal generative effect, it reminds us that xI y must be a valid entry in the translation lexicon. We call a matched terminal symbol pair such as xjy a couple. The null symbol f means that no output token is generated. We call x / f an L1-singleton., and E/y an L2-singleton.

Consider the simple context-free transduction grammar fragment shown in Figure 1 (a). (It will become apparent below why we explicitly include brackets around right-hand sides containing non terminals, which are usually omitted with standard CFGs.) The transduction grammar can generate, for instance, the following pair of English and Chinese sentences in translation:

• (I) a. [[[[The [Financial Secretary]NN ]NP and [I]NP ]NP [will [be accountable ]vv )vp )sp ./ o ]s
• [[[[[Mif.& 61]NN ]NP f[J [~]NP ]NP WJ'@ [~Jf]vv )vp )sp .I o ]s

Notice that each nonterminal derives two substrings, one in each language. The two substrings are counterparts of each other. In fact, it is natural to write the parse trees together:

1. [[[[Thelf [Financial/J!tif.& Secretary/61 lNN lNP and/f[J [1/f.Jt]NP lNP [will/~~'@ [belf accountable/~Jf]vv )vp )sp .I o ]s

Of course, in general context-free transduction grammars are not very useful, precisely because they require the two languages to share exactly the same grammatical structure (modulo those distinctions that can be handled with lexical singletons). For example, the following sentence pair from our corpus cannot be generated:

1. a. The Authority will be accountable to the Financial Secretary.
2. ~£!Jm~~'@[PJJ!fif.&61~Jf o

To make transduction grammars truly useful for bilingual tasks, we must escape the rigid parallel ordering constraint of context-free transduction grammars. At the same time, any relaxation of constraints must be traded off against increases in the computational complexity of parsing, which may eas­ ily become exponential. The key is to make the relaxation relatively modest but still handle a wide range of ordering variations.

The inversion transduction grammar (lTG) formalism only minimally extends the generative power of a context-free transduction grammar, 1 yet turns out to be surprisingly effec­ tive. The productions of an inversion transduction grammar are interpreted just as in a context-free transduction gram­ mar, except that two possible orientations are allowed. Pure context-free transduction grammars have the implicit charac­ teristic that for both output streams, the symbols generated by the right-hand side constituents of a production are con­ catenated in the same left-to-right order. Inversion transduc­ tion grammars also allow such productions, which are said to have straight orientation. In addition, however, inversion transduction grammars allow productions with inverted ori­ entation, which generate output for stream 2 by emitting the constituents on a production's right-hand side in right-to-left order. We indicate a production's orientation with explicit notation for the two varieties of concatenation operators on string-pairs. The operator [] performs the "usual" pairwise concatenation so that [AB] yields the string-pair ( C1 , C2 ) where C1 = A1B1 and C2 = A2B2. But the operator 0 concatenates constituents on output stream I while reversing them on stream 2, so that C1 = A1B1 but C2 = B2A2. Since inversion is permitted at any level of rule expansion, a deriva­ tion may intermix productions of either orientation within the parse tree. For example, if the inverted-orientation production of Figure 1 (b) is added to the earlier context-tree transduction grammar, sentence-pair (3) can then be generated as follows:

1. a. [[[The Authority]NP [will [[be accountable]vv [to [the [[Financial Secretary ]NN ]NNN ]NP )pp )vp )vp )sp .I o ]s
2. (((~f!Jm)NP (~~'@ ((rDJ (((J!tif.& 61)NN )NNN )NP )pp [~Jf]vv )vp )vp )sp .I o ]s

We can show the common structure of the two sentences more clearly and compactly with the aid of the 0 notation:

1. [[[Thelf Authority/~f!Jm ]NP [will/~~'@ ([belf accountable/~ jf ]vv [to/rDJ [thelf [[Financial/J!t if.& Secretary/61]NN ]NNN ]NP )pp )vp )vp )sp .lo ]s

Alternatively, a graphical parse tree notation is shown in Figure 2, where the 0 level of bracketing is indicated by a hor­ izontal line. The English is read in the usual depth-first left­ to-right order, but for the Chinese, a horizontal line means the right subtree is traversed before the left.

Parsing, in the case of an lTG, means building matched con­ stituents for input sentence-pairs rather than sentences. This means that the adjacency constraints given by the nested lev­ els must be obeyed in the bracketings of both languages. The result of the parse yields labelled bracketings for both sen­ tences, as well as a bracket alignment indicating the parallel constituents between the sentences. The constituent align­ ment includes a word alignment as a byproduct.

1 The expressiveness of CFTGs is equivalent to pushdown trans­ ducers (Savitch 1982). lTGs are of greater expressiveness and can be seen in terms of syntax-directed transduction (Lewis & Stearns 1968) but this view is too general to be of much help. Also note that parsing is bilingual with ITGs, whereas the pushdown and syntax-directed transduction frameworks are designed for monolingual parsing in tandem with generation.

Clearly, the nonterminals of an lTG must be chosen in a somewhat different manner than for a monolingual grammar, since they must simultaneously account for syntactic patterns of both languages. Moreover, certain phenomena with under­ lying structure that is not context-free-particularly, ellipsis and coordination-fall outside the expressiveness of ITGs if the surface structures of the two languages do not parallel each other. Nevertheless, a wide range of ordering variation between the languages can be accommodated by appropriate decomposition of productions (and thus constituents), in con­ juction with introduction of new auxiliary non terminals where needed. In fact ITGs can generate all 34 possible alignments between subsequences of length 3, and 207 out of the 209 possible alignments between length 4 subsequences. 2 Messy alignments such as that in Figure 3 can be handled by inter­ leaving orientations:

We stress again that the primary purpose of ITGs is robust analysis rather than grammaticality determination, and there­ fore writing grammars is made much easier since the gram­ mars can be minimal and very leaky. We consider elsewhere an extreme special case of leaky ITGs, inversion-invariant transduction grammars, in which all productions occur with both orientations (Wu 1995a). As the applications below demonstrate, the bilingual lexical constraints carry greater importance than the tightness of the grammar.

2 See also Section 7. The analysis of ordering flexibility is omitted for space reasons, but is given elsewhere (Wu 1995b).

3 A Normal Form for ITGs

We show here that every inversion transduction grammar can be expressed as an equivalent grammar in a normal form that simplifies algorithms and analyses on ITGs. In particular, the parsing algorithm of the next section operates on ITGs in normal form. The lemmas' proofs are omitted.

Lemma 1 For any inversion transduction grammar G, there exists an equivalent inversion transduction grammarG' where T( G) = T( G'), such that:

1. if f. E L1 (G) and f. E L2( G), then G' contains a single production of the form S' ---> f./ f., where S' is the start symbol ofG' and does not appear on the right-handside of any production of G';
2. else G' contains no productions of the form A---. c/c.

Lemma 2 For any inversion transduction grammar G, there exists an equivalent inversion transduction grammar G' where T( G) = T( G'), T( G) = T( G'), such that the right-hand side of any production of G' contains either a single terminal-pair or a list of nonterminals.

Lemma 3 For any inversion transduction grammar G. there exists an equivalent inversion transduction grammar G' where T( G) = T( G'). such that G' does not contain any productions of the form A---> B .

Theorem 1 For any inversion transductiongrammarG, there exists an equivalent inversion transduction grammar G' in which every production takes one of the following forms:

Proof By Lemmas 1, 2, and 3, we may assume G contains only productions of the form S ---+ <I<, A ---+ xI y, A ---+ xI<, A---+ <ly, A ---+ [E1E2J, A ---+ (E1E2), A ---+ [E1 .. . EnJ, and A ---+ (E1 .. . En) where n 2: 3. Include in G' all pro­ ductions of the first six types. The remaining two types are transformed as follows.

For each production of the form A ---+ [E1 ... En] we in­ troduce new nonterminals X 1 ... Xn_ 2 in order to replace the production with the set of rules A ---+ [E1XI], X1 ---+ [B2X2], . . . , Xn-3 ---+ [En-2Xn-2J, Xn-2 ---+ [En-lEn]­ Let (E, C) be any string-pair derivable from A ---+ [ B1 ... En], where E is output on stream I and Con stream 2. Define Ei as the substring of E derived from E;, and similarly define Ci. Then X; generates ( Ei+ 1 · · · En, ci+ 1 · · ·en) for alii S i < n, so the new production A---+ [E1X1] also gen­ erates (E, C). No additional string-pairs are generated due to the new productions (since each X; is only-reachable from X;_1 and X 1 is only reachable from A).

For each production of the form A ---+ (E1 ... En) were­ place the production with the set of rules A---+ (E1 XI) , X1 ---+ (B2X2), .. . , Xn-3---+ (En-2Xn-2), Xn-2---+ (En-1En)­ Let (E, C) be any string-pair derivable from A ---+ (B1 ... En ), where E is output on stream I and Con stream 2. Again define Ei and Ci as the substrings derived from the B;, but in this case (E, C) = (E 1 ···En, en· ·· C 1 ). Then Y; generates (Ei+ 1 ... En, cn-i+ 1 ... C 1 ) for all1 S i < n, so the new production A ---+ (E1 YI) also generates (E, C). Again no additional string-pairs are generated due to the new productions. D

Henceforth all transduction grammars will be assumed to be in normal form.

4 Stochastic Inversion Transduction Grammars

In a stochastic lTG (SITG), a probability is associated with each rewrite rule. For example, the probability of the rule NN ~ [AN] is aNN-+[A NJ = 0.4. The probability of a lexical rule A o~i xly is bA(x,y) = 0.001. Let W1, W2 be the vocabulary sizes of the two languages, and N be the set of non terminals with indices 1, ... , N. Then for every 1 S i S N, the production probabilities are subject to the constraint that

We now introduce an algorithm for parsing with stochas­ tic ITGs, that computes an optimal parse given a sentencepair using dynamic programming (DP). In bilingual parsing, just as with ordinary monolingual parsing, probabilizing the grammar permits ambiguities to be resolved by choosing the maximum likelihood parse. Our algorithm is similar in spirit to the recognition algorithm for HMMs (Viterbi 1967) and to chart parsers (Earley 1970).

Let the input English sentence be e1 , ... , er and the corresponding input Chinese sentence be c1 , ... , cv. As an abbreviation we write e · . t for the sequence of words es+l,es+2 , ... ,e1 , and similarly for Cu .. v· It is convenient to use a 4-tuple of the form q = ( s, t, u, v) to identify each node ofthe parse tree, where the substrings es . t and c, v both derive from the node q. Denote the nonterminallabel on q by f(q). Then for any node q = (s, t, u, v), define

as the maximum probability of any derivation from i that successfully parses both es .. t and Cu v· Then the best parse of the sentence pair has probability 8o,r,o,v(S).

The algorithm computes 8o ,r,o,v(S) using the following recurrences. Note that we generalize argmax to the case where maximization ranges over multiple indices, by making it vector-valued. Also note that []and 0 are simply constants, written mnemonically. The condition (S- s)(t- S) + (U­ u )( v - U) -:/: 0 is a way to specify that the substring in one but not both languages may be split into an empty string f and the substring itself; this ensures that the recursion terminates, but permits words that have no match in the other language to map to an f instead.

1. Initialization

3. Reconstruction Initialize by setting the root of the parse tree to q1 = (0 , T , 0, V) and its nonterminallabel to f(ql) = S. The remaining descendants in the optimal parse tree are then given recursively for any q = (s, t , u, v) by:

The time complexity of this algorithm in the general case is 0( N 3 T 3 V 3 ) where N is the number of distinct nonterminals and T and V are the lengths of the two sentences. This is a factor of V 3 more than monolingual chart parsing, but has turned out to remain quite practical for corpus analysis, where parsing need not be real-time.

5 Applications: Translation-Driven

Segmentation

Segmentation of the input sentences is an important step in preparing bilingual corpora for various learning procedures. Different languages realize the same concept using varying numbers of words; a single English word may surface as a compound in French. This complicates the problem of matching the words between a sentence pair, since it means that compounds or collocations must sometimes be treated as lexical units. The translation lexicon is assumed to contain collocation translations to facilitate such multi-word match­ ings. However, the input sentences do not come broken into appropriately matching chunks, so it is up to the parser to decide when to break up potential collocations into individual words.

The problem is particularly acute for English and Chinese because word boundaries are not orthographically marked in Chinese text, so not even a default chunking exists, upon which word matchings could be postulated. (Sentences (2) and (2) demonstrate why the obvious trick of taking sin­ gle characters as words is not a workable strategy.) The usual Chinese NLP architecture first preprocesses input text through a word segmentation module (Chiang et at. 1992; Chang & Chen 1993; Lin et at. 1993; Wu & Tseng 1993; Sproat et at. 1994; Wu & Fung 1994), but clearly bilingual parsing will be hampered by any errors arising from segmen­ tation ambiguities that could not be resolved in the isolated monolingual context because even if the Chinese segmenta­ tion is acceptable monolingually, it may not agree with the words present in the English sentence. Matters are made still worse by unpredictable omissions in the translation lexicon, even for valid compounds.

We therefore extend the algorithm to optimize the Chinese sentence segmentation in conjunction with the bracketing pro­ cess. Note that the notion of a Chinese "word" is a longstand­ ing linguistic question, that our present notion of segmentation does not address. We adhere here to a purely task-driven defi­ nition of what a correct "segmentation" is, namely that longer segments are desirable only when no compositional transla­ tion is possible. The algorithm is modified to include the following computations, and remains the same otherwise:

1. Initialization

2. Recursion

3. Reconstruction

In our experience this method has proven extremely effec­ tive for avoiding missegmentation pitfalls, essentially erring only in pathological cases involving coordination construc­ tions or lexicon coverage inadequacies. The method is also straightforward to employ in tandem with other applications such as those below.

6 Applications: Bracketing

Bracketing is another intermediate corpus annotation, useful especially when a full-coverage grammar with which to parse a corpus is unavailable (for Chinese, an even more common situation than with English). Aside from purely linguistic interest, bracket structure has been empirically shown to be highly effective at constraining subsequent training of, for ex­ ample, stochastic context-free grammars (Pereira & Schabes 1992; Black et al. 1993). Previous algorithms for automatic bracketing operate on monolingual texts and hence require more grammatical constraints; for example, tactics employing mutual information have been applied to tagged text (Mager­ man & Marcus 1990).

Our method based on SITGs operates on the novel prin­ ciple that lexical correspondences between parallel sentences yields information from which partial bracketings for both sentences can be extracted. The assumption that no grammar is available means that constituent categories are not differ­ entiated. Instead, a generic bracketing inversion transduction grammar is employed, containing only one non terminal sym­ bol , A, which rewrites either recursively as a pair of Ns or as a single terminal-pair:

Longer productions with fanout > 2 are not needed; we show in (Wu 1995a) that this minimal transduction grammar in normal form is generatively equivalent to any reasonable lTG for bracketing. Moreover, we also show how postprocessing using rotation and flattening operations restores the fanout flexibility so that an output bracketing can hold more than two immediate constituents, as shown in Figure 4.

The b;j distribution actually encodes the English-Chinese translation lexicon. We have been using a lexicon that was automatically learned from the HKUST English-Chinese Par­ allel Bilingual Corpus via statistical sentence alignment (Wu 1994) and statistical Chinese word and collocation extraction (Fung & Wu 1994; Wu & Fung 1994 ), followed by an EM word-translation learning procedure (Wu & Xia 1994). The latter stage gives us the b;j probabilities directly. For the two singleton productions, which permit any word in either sentence to be unmatched, a small f-constant can be chosen for the probabilities b;, and b,j, so that the optimal brack­ eting resorts to these productions only when it is otherwise impossible to match words.

An experiment was carried out as follows. Approximately 2,000 sentence~pairs with both English and Chinese lengths of30 words or less were extracted from our corpus and brack­ eted using the algorithm described. Several additional criteria were used to filter out unsuitable sentence-pairs. If the lengths of the pair of sentences differed by more than a 2: I ratio, the pair was rejected; such a difference usually arises as the result of an earlier error in automatic sentence alignment. Sentences containing more than one word absent from the translation lex­ icon were also rejected; the bracketing method is not intended to be robust against lexicon inadequacies. We also rejected sentence pairs with fewer than two matching words, since this gives the bracketing algorithm no discriminative lever­ age; such pairs accounted for less than 2% of the input data. A random sample of the bracketed sentence pairs was then drawn, and the bracket precision was computed under each criterion for correctness. Examples are shown in Figure 4.

The bracket precision was 80.4% for the English sentences, and 78.4% for the Chinese sentences, as judged against man­ ual bracketings. Inspection showed the errors to be due largely to imperfections of our translation lexicon, which contains approximately 6,500 English words and 5,500 Chinese words with about 86% translation accuracy (Wu & Xi a 1994 ), so a better lexicon should yield substantial performance improve­ ment. Moreover, if the resources for a good monolingual part-of-speech or grammar-based bracketer such as that of Magerman & Marcus (1990) are available, its output can read­ ily be incorporated in complementary fashion as discussed in Section 8.

7 Applications: Phrasal Alignment

Phrasal Alignment The parsing algorithm can be used to identify phrasal translations within sentence pairs. This is useful especially where the phrases in the two languages are not compositionally derivable solely from obvious word trans­ lations, such as [have acquiredlf fl~flj new/~JT skillsltiti~] in Figure 4. This principle applies to nested structures also, such as ([ fiB:! I who/ A. ] [ have acquiredlf fl~flj new/~JT skills/fit]~ ]), on up to the sentence level. These examples were found using the minimal bracketing transduction gram­ mar, a relatively weak strategy; we evaluated the precision at 72.5%, which is useful but rather low. Higher precision could be achieved without great effort by employing a small number of broad non terminal categories.

Word Alignment Under the lTG model, word alignment becomes simply the special case of phrasal alignment at the parse tree leaves. However, this gives us an interesting al­ ternative perspective, from the standpoint of algorithms that match the words between parallel sentences. By themselves word alignments are of little use, but they provide potential an­ chor points for other applications, or for subsequent learning stages to acquire more interesting structures.

Word alignment is difficult because correct matchings are not usually linearly ordered, i.e., there are crossings. Without some additional constraints, any word position in the source sentence can be matched to any position in the target sentence, an assumption which leads to high error rates. More sophisti­ cated word alignment algorithms therefore attempt to model the intuition that proximate constituents in close relationships in one language remain proximate in the other. The later IBM models are formulated to prefer collocations (Brown et al. 1993). In the case of word....align (Dagan et al. 1993; Dagan & Church 1994), a penalty is imposed according to the deviation from an ideal matching, as constructed by linear ical expertise in one language toward bootstrapping grammar acquisition in another.

A parsing algorithm for this case can be implemented very efficiently. Note that the English parse tree already deter­ mines the split point S for breaking e0 . . T into two constituent subtrees deriving eo .. s and es .. T respectively, as well as the nonterminal labels j and k for each subtree. The same then applies recursively to each subtree. We indicate this by turn­ ing S, j, and k into deterministic functions on the English constituents, writing Sst . Jst. and kst to denote the split point and the subtree labels for any constituent es .. t. The following simplifications can then be made to the parsing algorithm:

1. Recursion For all English constituents es .t and all i, u, v { l<i<N such that o::;ti<v::; v

3. Reconstruction

The time complexity for this constrained version of the algo­ rithm drops from 0(N 3 T 3 V 3 ) to 0(TV 3 ) .

Partial Parse Trees A more realistic in-between scenario occurs when partial parse information is available for one or both of the languages. Special cases of particular interest include applications where bracketing or word alignment con­ straints may be derived from external sources beforehand. For

interpolation . 3

From thi s point of view, the proposed technique is a word alignment method that imposes a more realistic distortion penalty. The tree structure reflects the assumption that cross­ ings should not be penalized as long as they are consistent with constituent structure. Figure 5 gives theoretical upper bounds on the matching flexibility as the lengths of the sequences increase, where the constituent structure constraints are re­ flected by high flexibility up to m = 4 and a rapid dropoff thereafter. 3 In other words, ITGs appeal to a language uni­ versals hypothesis, that the core arguments of frames , which exhibit great ordering variation between languages, are rel­ atively few and surface in syntactic proximity. Of course this assumption over-simplistically blends syntactic and se­ mantic notions. That semantic frames for different languages share common core arguments is more plausible than syntactic frames. In effect we are relying on the tendency of syntactic arguments to correlate closely with semantics. If in particular cases this assumption does not hold, however, the damage is not too great in that the model will simply drop the offending word matchings (dropping as few as possible).

In experiments with the minimal bracketing transduction grammar, the large majority of errors in word alignment were caused by two outside factors . First, word matchings can be overlooked simply due to deficiencies in our translation lexicon. This accounted for approximately 42% of the er­ rors. Second, sentences containing non-literal translations obviously cannot be aligned down to the word level. This accounted for another approximate 50% of the errors. Ex­ cluding these two types of errors, accuracy on word align­ ment was 96.3%. In other words, the tree-structure constraint is strong enough to prevent most false matches, but almost never inhibits correct word matches when they exist.

8 Applications: Bilingual Constraint Transfer

Monolingual Parse Tree A parse may be available for one of the languages, especially for well-studied languages such as English. Since this eliminates all degrees of freedom in the English sentence structure, the parse of the Chinese sentence must conform with that given for the English. Knowledge of English bracketing is thus used to help parse the Chinese sentence; this method facilitates a kind of transfer of grammatexample, a broad-coverage English bracketer may be avail­ able. If such constraints are reliable, it would be wasteful to ignore them.

3 Direct comparison with word..align should be avoided, however, since it is intended to work on corpora whose sentences are not aligned.

A straightforward extension to the original algorithm in­ hibits hypotheses that are inconsistent with given constraints. Any entries in the DP table corresponding to illegal sub­ hypotheses-i.e., those that would violate the given bracket­ nesti ng or word-alignment conditions-are pre-assigned neg­ ative infinity values during initialization indicating impossi­ bility. During the DP phase, computation of these entries is skipped. Since their probabilities remain impossible through­ out, the illegal sub-hypotheses will never participate in any ML bi-bracketing. The running time reduction in this case depends heavi ly on the domain. We have found this strategy to be useful for incorporating punctuation constraints.

9 Conclusion

The twin concepts of bilingual language modeling and bilin­ gual parsing have been proposed. We have introduced a new formalism, the inversion transduction grammar, and surveyed a variety of its applications to extracting linguistic informa­ tion from parallel corpora. Its amenability to stochastic for­ mulation, useful flexibility with leaky and minimal grammars, and tractability for practical applications are desirable proper­ ties. Various tasks such as segmentation, word alignment and bracket annotation are naturally incorporated as subproblems, and a high degree of compatibility with conventional monolin­ gual methods is retained. In conjunction with automatic pro­ cedures for learning word translation lexicons, SITGs bring relatively underexploited bilingual constraints to bear on the task of extracting linguistic information for languages less well-studied than English.

A current direction is to investigate automatic training of SITGs. We derive in Wu (1995c) an EM-based re-estimation method for SITGs, and describe preliminary experiments.

Acknowledgement

I would like to thank Xuanyin Xia, Eva Wai-Man Fong, Pas­ cale Fung, and Derick Wood.