{'fraction_non_alphanumeric': 0.03220164609053498, 'fraction_numerical': 0.009526748971193415, 'mean_word_length': 5.176261278434363, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Stochastic Inversion Transduction Grammars and Bilingual Parsing of Parallel Corpora

We introduce (1) a novel stochastic inversion transduction grammar formalism for bilingual language modeling of sentence-pairs, and (2) the concept of bilingual parsing with a variety of parallel corpus analysis applications. Aside from the bilingual orientation, three major features distinguish the formalism from the finite-state transducers more traditionally found in computational linguistics: it skips directly to a context-free rather than finite-state base, it permits a minimal extra degree of ordering flexibility, and its probabilistic formulation admits an efficient maximum-likelihood bilingual parsing algorithm. A convenient normal form is shown to exist. Analysis of the formalism's expressiveness suggests that it is particularly well suited to modeling ordering shifts between languages, balancing needed flexibility against complexity constraints. We discuss a number of examples of how stochastic inversion transduction grammars bring bilingual constraints to bear upon problematic corpus analysis tasks such as segmentation, bracketing, phrasal alignment, and parsing.


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. Transduction grammar models, especially of the finite-state family, have long been known. However, the imposition of identical ordering constraints upon both streams severely restricts their applicability, and thus transduction grammars have received relatively little attention in language-modeling research. The inversion transduction grammar formalism skips directly to a context-free, rather than finite-state, base and permits one extra degree of ordering flexibility, while retaining properties necessary for efficient computation, thereby sidestepping the limitations of traditional transduction grammars.
In tandem with the concept of bilingual language-modeling, we propose the concept of bilingual parsing, where the input is a sentence-pair rather than a sentence.
Though inversion 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 (Brown et al. 1990; Gale and Church 1991;Gale, Church, and Yarowsky 1992;Church 1993;Brown et al. 1993;Dagan, Church, and Gale 1993;Fung and Church 1994;Wu and Xia 1994;Fung and McKeown 1994). The primary purpose of bilingual parsing with inversion transduction grammars is not to flag ungrammatical inputs; rather, the aim is to extract structure from the input data, which is assumed to be grammatical, in keeping with the spirit of robust parsing. The formalism's uniform integration of various types of bracketing and alignment constraints is one of its chief strengths. The paper is divided into two main parts. We begin in the first part below by laying out the basic formalism, then show that reduction to a normal form is possible. We then raise several desiderata for the expressiveness of any bilingual languagemodeling formalism in terms of its constituent-matching flexibility and discuss how the characteristics of the inversion transduction formalism are particularly suited to address these criteria. 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 examples and applications using Chinese and English because languages from different families provide a more rigorous testing ground. In the second part, we survey a number of sample applications and extensions of bilingual parsing for segmentation, bracketing, phrasal alignment, and other parsing tasks.

Inversion Transduction Grammars
A transduction grammar describes a structurally correlated pair of languages. For our purposes, the generative view is most convenient: the grammar generates transductions, so that two output streams are simultaneously generated, one for each language. This contrasts with the common input-output view popularized by both syntaxdirected transduction grammars and finite-state transducers. The generative view is more appropriate for our applications because the roles of the two languages are symmetrical, in contrast to the usual applications of syntax-directed transduction grammars. Moreover, the input-output view works better when a machine for accepting one of the languages (the input language) has a high degree of determinism, which is not the case here.
Our transduction model is context-free, rather than finite-state. Finite-state transducers, or FSTs, are well known to be useful for specific tasks such as analysis of inflectional morphology (Koskenniemi 1983), text-to-speech conversion (Kaplan and Kay 1994), and nominal, number, and temporal phrase normalization (Gazdar and Mellish 1989). FSTs may also be used to parse restricted classes of context-free grammars (Pereira 1991;Roche 1994;Laporte 1996). However, the bilingual corpus analysis tasks we consider in this paper are quite different from the tasks for which FSTs are apparently well suited. Our domain is broader, and the model possesses very little a priori specific structural knowledge of the language.
As a stepping stone to inversion transduction grammars, we first consider what a context-free model known as a simple transduction grammar (Lewis and Stearns 1968) would look like. Simple transduction grammars (as well as inversion transduction grammars) are restricted cases of the general class of context-free syntax-directed transduction grammars (Aho and Ullman 1969a, 1969b, 1972; however, we will avoid the term syntax-directed here, so as to de-emphasize the input-output connotation as discussed above. A simple transduction grammar can be written by marking every terminal symbol for a particular output stream. Thus, each rewrite rule emits not one but two streams. For example, a rewrite rule of the form A ~ Bxly2Czl means that the terminal symbols x and z are symbols of. the language L1 emitted on stream 1, while y is a symbol of (a)

Figure 1
A simple transduction grammar (a) and an inverted-orientation production (b).
the language L2 emitted on stream 2. It follows that every nonterminal stands for a class of derivable substring pairs. We can use a simple transduction grammar to model the generation of bilingual sentence pairs. As a mnemonic convention, we usually use the alternative notation A --. B x/y C z/c to associate matching output tokens. Though this additional information has no formal generative effect, it reminds us that x/y must be a valid entry in the translation lexicon. We call a matched terminal symbol pair such as x/y a couple. The null symbol ¢ means that no output token is generated. We call x/¢ an Ll-singleton, and ¢/y an L2-singleton.
Consider the simple transduction grammar fragment shown in Figure l(a). (It will become apparent below why we explicitly include brackets around right-hand sides containing nonterminals, which are usually omitted with standard CFGs.) The simple transduction grammar can generate, for instance, the following pair of English and Chinese sentences in translation: ( Of course, in general, simple 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: (3) a. The Authority will be accountable to the Financial Secretary. To make transduction grammars truly useful for bilingual tasks, we must escape the rigid parallel ordering constraint of simple transduction grammars. At the same time, any relaxation of constraints must be traded off against increases in the computational complexity of parsing, which may easily become exponential. The key is to make the relaxation relatively modest but still handle a wide range of ordering variations.
The inversion transduction grammar (ITG) formalism only minimally extends the generative power of a simple transduction grammar, yet turns out to be surprisingly effective. 1 Like simple transduction grammars, ITGs remain a subset of context-free (syntax-directed) transduction grammars (Lewis and Steams 1968) but this view is too general to be of much help. 2 The productions of an inversion transduction grammar are interpreted just as in a simple transduction grammar, except that two possible orientations are allowed. Pure simple transduction grammars have the implicit characteristic that for both output streams, the symbols generated by the right-hand-side constituents of a production are concatenated in the same left-to-right order. Inversion transduction grammars also allow such productions, which are said to have straight orientation. In addition, however, inversion transduction grammars allow productions with inverted orientation, 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 lAB] yields the string-pair (C1, C2) where C1 = AtB1 and C2 = A2B2. But the operator 0 concatenates constituents on output stream I while reversing them on stream 2, so that Ct = A1B1 but C2 = B2A2. Since inversion is permitted at any level of rule expansion, a derivation may intermix productions of either orientation within the parse tree. For example, if the inverted-orientation production of Figure l(b) is added to the earlier simple transduction grammar, sentence-pair (3) can then be generated as follows: Alternatively, a graphical parse tree notation is shown in Figure 2, where the (/ level of bracketing is indicated by a horizontal line. The English is read in the usual depthfirst 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 ITG, means building matched constituents for input sentence-pairs rather than sentences. This means that the adjacency constraints given by the nested levels must be obeyed in the bracketings of both languages. The result of the parse yields labeled bracketings for both sentences, as well as a bracket alignment indicating the parallel constituents between the sentences. The constituent alignment includes a word alignment as a by-product.
The nonterminals may not always look like those of an ordinary CFG. Clearly, the nonterminals of an ITG must be chosen in a somewhat different manner than for a monolingual grammar, since they must simultaneously account for syntactic patterns of both languages. One might even decide to choose nonterminals for an ITG that do not match linguistic categories, sacrificing this to the goal of ensuring that all corresponding substrings can be aligned.
An ITG can accommodate a wider range of ordering variation between the lan- An extremely distorted alignment that can be accommodated by an ITG.
guages than might appear at first blush, through appropriate decomposition of productions (and thus constituents), in conjuction with introduction of new auxiliary nonterminals where needed. For instance, even messy alignments such as that in Figure 3 can be handled by interleaving orientations: This bracketing is of course linguistically implausible, so whether such parses are acceptable depends on one's objective. Moreover, it may even remain possible to align constituents for phenomena whose underlying structure is not context-free--say, ellipsis or coordination--as long as the surface structures of the two languages fortuitously parallel each other (though again the bracketing would be linguistically implausible). We will return to the subject of ITGs' ordering flexibility in Section 4. We stress again that the primary purpose of ITGs is to maximize robustness for parallel corpus analysis rather than to verify grammaticality, and therefore writing grammars is made much easier since the grammars 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 1995). As the applications below demonstrate, the bilingual lexical constraints carry greater importance than the tightness of the grammar.
Formally, an inversion transduction grammar, or ITG, is denoted by G = (N, W1,W2,T¢,S), where dV is a finite set of nonterminals, W1 is a finite set of words (terminals) of language 1, }4;2 is a finite set of words (terminals) of language 2, T¢ is a finite set of rewrite rules (productions), and S E A/" is the start symbol. The space of word-pairs (terminal-pairs) X = (W1 U {c}) x (W2 U {c}) contains lexical translations denoted x/y and singletons denoted x/¢ or ¢/y, where x E W1 and y E W2. Each production is either of straight orientation written A --~ [ala2 ... ar], or of inverted orientation written A ~ (ala2.. • ar), where ai E A/" U X and r is the rank of the production. The set of transductions generated by G is denoted T(G). The sets of (monolingual) strings generated by G for the first and second output languages are denoted LffG) and L2(G), respectively.

A Normal Form for Inversion Transduction Grammars
We now show that every ITG can be expressed as an equivalent ITG in a 2-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 availability of a 2-normal form is a noteworthy characteristic of ITGs; no such normal form is available for unrestricted context-free (syntax-directed) transduction grammars (Aho and Ullman 1969b). The proof closely follows that for standard CFGs, and the proofs of the lemmas are omitted.

Lemma
For any duction 1 inversion transduction grammar G, there exists an equivalent inversion transgrammar G' where T(G) = T(G'), such that: . .
If ¢ E LI(G) and ¢ C L2(G), then G' contains a single production of the form S ~ ~ c/c, where S ~ is the start symbol of G ~ and does not appear on the right-hand side of any production of G'; otherwise G' contains no productions of the form A ~ c/c.

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

Lemma
For any duction tions of

Theorem 1
For any inversion transduction grammar G, there exists an equivalent inversion transduction grammar G t in which every production takes one of the following forms: By Lemmas 1, 2, and 3, we may assume G contains only productions of the form 1 _~ i < n -1, so the new production A --* (B1Y1) also generates (e,c). Again, no additional string-pairs are generated due to the new productions.
[] Henceforth all transduction grammars will be assumed to be in normal form.

Expressiveness Characteristics
We now turn to the expressiveness desiderata for a matching formalism. It is of course difficult to make precise claims as to what characteristics are necessary and/or sufficient for such a model, since no cognitive studies that are directly pertinent to bilingual constituent alignment are available. Nonetheless, most related previous parallel corpus analysis models share certain conceptual approaches with ours, loosely based on cross-linguistic theories related to constituency, case frames, or thematic roles, as well as computational feasibility needs. Below we survey the most common constraints and discuss their relation to ITGs. Crossing Constraints. Arrangements where the matchings between subtrees cross each another are prohibited by crossing constraints, unless the subtrees' immediate parent constituents are also matched to each other. For example, given the constituent matchings depicted as solid lines in Figure 4, the dotted-line matchings corresponding to potential lexical translations would be ruled illegal. Crossing constraints are implicit in many phrasal matching approaches, both constituency-oriented (Kaji, Kida, and Morimoto 1992;Cranias, Papageorgiou, and Peperidis 1994;Grishman 1994) and dependency-oriented (Sadler and Vendelmans 1990;Matsumoto, Ishimoto, and Utsuro 1993). The theoretical cross-linguistic hypothesis here is that the core arguments of frames tend to stay together over different languages. The constraint is also useful for computational reasons, since it helps avoid exponential bilingual matching times.
ITGs inherently implement a crossing constraint; in fact, the version enforced by ITGs is even stronger. This is because even within a single constituent, immediate subtrees are only permitted to cross in exact inverted order. As we shall argue below, this restriction reduces matching flexibility in a desirable fashion.
Rank Constraints. The second expressiveness desideratum for a matching formalism is to somehow limit the rank of constituents (the number of children or righthand-side symbols), which dictates the span over which matchings may cross. As the number of subtrees of an Ll-constituent grows, the number of possible matchings to subtrees of the corresponding L2-constituent grows combinatorially, with corresponding time complexity growth on the matching process. Moreover, if constituents can immediately dominate too many tokens of the sentences, the crossing constraint loses effectiveness--in the extreme, if a single constituent immediately dominates the entire sentence-pair, then any permutation is permissible without violating the crossing constraint. Thus, we would like to constrain the rank as much as possible, while still permitting some reasonable degree of permutation flexibility.
Recasting this issue in terms of the general class of context-free (syntax-directed) transduction grammars, the number of possible subtree matchings for a single constituent grows combinatorially with the number of symbols on a production's righthand side. However, it turns out that the ITG restriction of allowing only matchings with straight or inverted orientation effectively cuts the combinatorial growth, while still maintaining flexibility where needed.
To see how ITGs maintain needed flexibility, consider Figure 5, which shows all 24 possible complete matchings between two constituents of length four each. Nearly all of these--22 out of 24--can be generated by an ITG, as shown by the parse trees (whose The Security Bureau grante / authority to__the polic~ station

Figure 4
The crossing constraint.
nonterminal labels are omitted). 3 The 22 permitted matchings are representative of real transpositions in word order between the English-Chinese sentences in our data. The only two matchings that cannot be generated are very distorted transpositions that we might call "inside-out" matchings. We have been unable to find real examples in our data of constituent arguments undergoing "inside-out" transposition. Note that this hypothesis is for fixed-word-order languages that are lightly inflected, such as English and Chinese. It would not be expected to hold for so-called scrambling or free-word-order languages, or heavily inflected languages. However, inflections provide alternative surface cues for determining constituent roles (and 3 As discussed later, in many cases more than one parse tree can generate the same subconstituent matching. The trees shown are the canonical parses, as generated by the grammar of Figure 10.

Figure 6
Growth in number of legal complete subconstituent matchings for context-free (syntax-directed) transduction grammars with rank r, versus ITGs on a pair of subconstituent sequences of length r each.

Stochastic Inversion Transduction Grammars
In a stochastic ITG (SITG), a probability is associated with each rewrite rule. Following the standard convention, we use a and b to denote probabilities for syntactic and lexical rules, respectively. For example, the probability of the rule NN 0~ [A N] is aNN-,[A N] = 0.4. The probability of a lexical rule A 0.0001 x/y is bA(X,y) ~-0.001. Let W1, W2 be the vocabulary sizes of the two languages, and X = {A1 ..... AN} be the set of nonterminals with indices 1,...,N. (For conciseness, we sometimes abuse the notation by writing an index when we mean the corresponding nonterminal symbol, as long as this introduces no confusion.) Then for every 1 < i < N, the production probabilities are subject to the constraint that We now introduce an algorithm for parsing with stochastic ITGs that computes an optimal parse given a sentence-pair using dynamic programming. In bilingual parsing, just as with ordinary monolinguat 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 CYK parsing (Kasami 1965;Younger 1967

Figure 7
Growth in number of all legal subconstituent matchings (complete or partial, meaning that some subconstituents are permitted to remain unmatched as singletons) for context-flee (syntax-directed) transduction grammars with rank r, versus ITGs on a pair of subconstituent sequences of length r each. subtrees of q 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 60,T,0,v(S). The algorithm computes 60,T,0,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 c 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 ~ instead.

Reconstruction
Initialize by setting the root of the parse tree to ql = (0, T, 0, V) and its nonterminal label to t(ql) = S. The remaining descendants in the optimal parse tree are then given recursively for any q = (s, t, u, v) by: -s+v-u>2 (11) (cr~) (f(q)), t, u, v~ ) (f(q))) if Oq(f(q)) = 0 and ,-s+v-u>2 ~?(LEFT(q)) = ~*(ffq))(~(q)) (12) The time complexity of this algorithm in the general case is O(N3T3V3), 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.

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; for example, 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 multiword matchings. 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 (5) demonstrate why the obvious trick of taking single characters as words is not a workable strategy.) The usual Chinese NLP architecture first preprocesses input text through a word segmentation module Su 1992, 1993;Chang and Chen 1993;Wu and Tseng 1993;Sproat et al. 1994;Wu and Fung 1994), but, clearly, bilingual parsing will be hampered by any errors arising from segmentation ambiguities that could not be resolved in the isolated monolingual context because even if the Chinese segmentation 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 process. Note that the notion of a Chinese "word" is a longstanding linguistic question, that our present notion of segmentation does not address. We adhere here to a purely task-driven definition of what a correct "segmentation" is, namely that longer segments are desirable only when no compositional translation is possible. The algorithm is modified to include the following computations, and remains the same otherwise:

Bracketing
Bracketing is another intermediate corpus annotation, useful especially when a fullcoverage 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 example, stochastic context-free grammars (Pereira and Schabes 1992;Black, Garside, and Leech 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 (Magerman and Marcus 1990).
Our method based on SITGs operates on the novel principle 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 differentiated. Instead, a generic bracketing transduction grammar is employed, containing only one nonterminal symbol, A, which rewrites either recursively as a pair of A's or as a single terminal-pair: Longer productions with rank > 2 are not needed; we show in the subsections below that this minimal transduction grammar in normal form is generatively equivalent to any reasonable bracketing transduction grammar. Moreover, we also show how postprocessing using rotation and flattening operations restores the rank flexibility so that an output bracketing can hold more than two immediate constituents, as shown in Figure 11.

A "~ Ui/V j A ~ ui/¢
The bq distribution actually encodes the English-Chinese translation lexicon with degrees of probability on each potential word translation. We have been using a lexicon that was automatically learned from the HKUST English-Chinese Parallel Bilingual Corpus via statistical sentence alignment (Wu 1994) and statistical Chinese word and collocation extraction (Fung and Wu 1994;Wu and Fung 1994), followed by an EM word-translation-learning procedure (Wu and Xia 1994). The latter stage gives us the bij probabilities directly. For the two singleton productions, which permit any word in either sentence to be unmatched, a small c-constant can be chosen for the probabilities bit and bq, so that the optimal bracketing resorts to these productions only when it is otherwise impossible to match the singletons. The parameter a here is of no practical effect, and is chosen to be very small relative to the bq probabilities of lexical translation pairs. The result is that the maximum-likelihood parser selects the parse tree that best meets the combined lexical translation preferences, as expressed by the bij probabilities.

Pre-/postpositional biases. Many bracketing errors are caused by singletons. With
singletons, there is no cross-lingual discrimination to increase the certainty between alternative bracketings. A heuristic to deal with this is to specify for each of the two languages whether prepositions or postpositions are more common, where "preposition" here is meant not in the usual part-of-speech sense, but rather in a broad sense of the tendency of function words to attach left or right. This simple strategem is effective because the majority of unmatched singletons are function words that lack counterparts in the other language. This observation holds assuming that the translation lexicon's coverage is reasonably good. For both English and Chinese, we specify a prepositional bias, which means that singletons are attached to the right whenever possible.
A Singleton-Rebalancing Algorithm. We give here an algorithm for further improving the bracketing accuracy in cases of singletons. Consider the following bracketing produced by the algorithm of the previous section: ( The prepositional bias has already correctly restricted the singleton The/¢ to attach to the right, but of course The does not belong outside the rest of the sentence, but rather with Authority. The problem is that singletons have no discriminative power between alternative bracket matchings--they only contribute to the ambiguity. We can minimize the impact by moving singletons as deep as possible, closer to the individual word they precede or succeed; or in other words, we can widen the scope of the brackets immediately following the singleton. In general this improves precision since widescope brackets are less constraining. The algorithm employs a rebalancing strategy reminiscent of balanced tree structures using left and right rotations. A left rotation changes a (A(BC)) structure to a ((AB)C) structure, and vice versa for a right rotation. The task is complicated by the presence of both [] and 0 brackets with both L1-and L2-singletons, since each combination presents different interactions. To be legal, a rotation must preserve symbol order on both output streams. However, the following lemma shows that any subtree can always be rebalanced at its root if either of its children is a singleton of either language.

Lemma 4
Let x be an Ll-singleton, y be an L2-singleton, and A, B, C be arbitrary terminal or nonterminal symbols. Then the following properties hold for the [] and () operators, where the ~ relation means that the same two output strings are generated, and the matching of the symbols is preserved: (Associativity)

(y[AB]) = [lAB]y] ~-[A[By]] ~ [A(yB)] [(AB)y] = (y(AB)) = ((yA)B) = ([Ay]B) ([ABly) = [y[AB]] = [[yA]B] = [(Ay)B]
The method of Figure 8 modifies the input tree to attach singletons as closely as possible to couples, but remaining consistent with the input tree in the following sense: singletons cannot "escape" their immediately surrounding brackets. The key is that for any given subtree, if the outermost bracket involves a singleton that should be rotated into a subtree, then exactly one of the singleton rotation properties will apply. The method proceeds depth-first, sinking each singleton as deeply as possible. (a) (b) Figure 9 Alternative ITG parse trees for the same matching. An inconvenient problem with ambiguity arises in the simple bracketing grammar above, illustrated by Figure 9; there is no justification for preferring either (a) or (b) over the other. In general the problem is that both the straight and inverted concatenation operations are associative. That is, [A [AA]] and [[AA]A] generate the same two output strings, which are also generated by [AAA]; and similarly with (A(AA)) and ((AA)A), which can also be generated by (AAA). Thus the parse shown in (c) is preferable to either (a) or (b) since it does not make an unjustifiable commitment either way.
Productions in the form of (c), however, are not permitted by the normal form we use, in which each bracket can only hold two constituents. Parsing must overcommit, since the algorithm is always forced to choose between (A(BC)) and ((AB)C) structures even when no choice is clearly better. We could relax the normal form constraint, but longer productions clutter the grammar unnecessarily and, in the case of generic bracketing grammars, reduce parsing efficiency considerably.
Instead, we employ a more complicated but better-constrained grammar as shown in Figure 10, designed to produce only canonical tail-recursive parses. We differentiate type A and B constituents, representing subtrees whose roots have straight and inverted orientation, respectively. Under this grammar, a series of nested constituents with the same orientation will always have a left-heavy derivation. The guarantee that parsing will produce a tail-recursive tree facilitates easily identification of those nesting levels that are associative (and therefore arbitrary), so that those levels can be "flattened" by a postprocessing stage after parsing into non-normal form trees like the one in Figure 9(c). The algorithm proceeds bottom-up, eliminating as many brackets as possible, by making use of the associativity equivalences [lAB]C] = [ABC] and ((ABIC) ~ (ABC). The singleton bidirectionality and flipping commutativity equivalences (see Lemma 4) can also be applied whenever they render the associativity equivalences applicable. Experiment. Approximately 2,000 sentence-pairs with both English and Chinese lengths of 30 words or less were extracted from our corpus and bracketed 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:1 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 lexicon 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 leverage; 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 11. The bracket precision was 80% for the English sentences, and 78% for the Chinese sentences, as judged against manual 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 and Xia 1994), so a better lexicon should yield substantial performance improvement. Moreover, if the resources for a good monolingual part-of-speech or grammar-based bracketer such as that of Magerman and Marcus (1990) are available, its output can readily be incorporated in complementary fashion as discussed in Section 9.

Phrasal Alignment
Phrasal translation examples at the subsentential level are an essential resource for many MT and MAT architectures. This requirement is becoming increasingly direct for the example-based machine translation paradigm (Nagao 1984), whose translation flexibility is strongly restricted if the examples are only at the sentential level. It can now be assumed that a parallel bilingual corpus may be aligned to the sentence level with reasonable accuracy (Kay and Ri3cheisen 1988;Catizone, Russel, and Warwick 1989;Gale and Church 1991;Brown, Lai, and Mercer 1991;Chen 1993), even for languages as disparate as Chinese and English (Wu 1994). Algorithms for subsentential alignment have been developed as well as granularities of the character (Church 1993), word (Dagan, Church, and Gale 1993;Fung and Church 1994;McKeown 1994), collocation (Smadja 1992), and specially segmented (Kupiec 1993) levels. However, the identification of subsentential, nested, phrasal translations within the parallel texts remains a nontrivial problem, due to the added complexity of dealing with constituent structure. Manual phrasal matching is feasible only for small corpora, either for toy-prototype testing or for narrowly restricted applications.
Automatic approaches to identification of subsentential translation units have largely followed what we might call a "parse-parse-match" procedure. Each half of the parallel corpus is first parsed individually using a monolingual grammar. Subsequently, the constituents of each sentence-pair are matched according to some heuristic procedure. A number of recent proposals can be cast in this framework (Sadler and Vendelmans 1990;Kaji, Kida, and Morimoto 1992;Matsumoto, Ishimoto, and Utsuro 1993;Cranias, Papageorgiou, and Peperidis 1994;Grishman 1994).
The parse-parse-match procedure is susceptible to three weaknesses: Appropriate, robust, monolingual grammars may not be available. This condition is particularly relevant for many non-Western European languages such as Chinese. A grammar for this purpose must be robust since it must still identify constituents for the subsequent matching process even for unanticipated or ill-formed input sentences.
The grammars may be incompatible across languages. The best-matching constituent types between the two languages may not include the same core arguments. While grammatical differences can make this problem unavoidable, there is often a degree of arbitrariness in a grammar's chosen set of syntactic categories, particularly if the grammar is designed to be robust. The mismatch can be exacerbated when the monolingual grammars are designed independently, or under different theoretical considerations.
Selection between multiple possible arrangements may be arbitrary. By an "arrangement" between any given pair of sentences from the parallel corpus, we mean a set of matchings between the constituents of the sentences. The problem is that in some cases, a constituent in one sentence may have several potential matches in the other, and the matching heuristic may be unable to discriminate between the options.
In the sentence pair of Figure 4, for example, both Security Bureau and police station are potential lexical matches to ~j.
To choose the best set of matchings, an optimization over some measure of overlap between the structural analysis of the two sentences is needed. Previous approaches to phrasal matching employ arbitrary heuristic functions on, say, the number of matched subconstituents.
Our method attacks the weaknesses of the parse-parse-match procedure by using (1) only a translation lexicon with no language-specific grammar, (2) a bilingual rather than monolingual formalism, and (3) a probabilistic formulation for resolving the choice between candidate arrangements. The approach differs in its single-stage operation that simultaneously chooses the constituents of each sentence and the matchings between them.
The raw phrasal translations suggested by the parse output were then filtered to remove those pairs containing more than 50% singletons, since such pairs are likely to be poor translation examples. Examples that occurred more than once in the corpus were also filtered out, since repetitive sequences in our corpus tend to be nongrammatical markup. This yielded approximately 2,800 filtered phrasal translations, some examples of which are shown in Figure 12. A random sample of the phrasal translation pairs was then drawn, giving a precision estimate of 81.5%.
Although this already represents a useful level of accuracy, it does not in our opinion reflect the full potential of the formalism. Inspection revealed that performance was greatly hampered by our noisy translation lexicon, which was automatically learned; it could be manually post-edited to reduce errors. Commercial on-line translation lexicons could also be employed if available. Higher precision could be also achieved without great effort by engineering a small number of broad nonterminal categories. This would reduce errors for known idiosyncratic patterns, at the cost of manual rule building.
The automatically extracted phrasal translation examples are especially useful where the phrases in the two languages are not compositionally derivable solely from obvious word translations. An example is [have acquired/¢ ¢/-~] new/~J~ skills/~ ~j~] in Figure 11. The same principle applies to nested structures also, such as ( of implementation year ended 3 1 March 1 9 9 1 ~_~Ph~J~ --n u-

Figure 12
Examples of extracted phrasal translations.

Word Alignment
Under the ITG model, word alignment becomes simply the special case of phrasal alignment at the parse tree leaves. This gives us an interesting alternative 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 anchor 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 that leads to high error rates. More sophisticated 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, Church, and Gale 1993;Dagan and Church 1994), a penalty is imposed according to the deviation from an ideal matching, as constructed by linear interpolation?
From this 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 crossings should not be penalized as long as they are consistent with constituent structure. Figure 7 gives theoretical upper bounds on the matching flexibility as the lengths of the sequences increase, where the constituent structure constraints are reflected by high flexibility up to length-4 sequences and a rapid drop-off thereafter. In other words, ITGs appeal to a language universals hypothesis, that the core arguments of frames, which exhibit great ordering variation between languages, are relatively few and surface in syntactic proximity. Of course, this assumption over-simplistically 4 Direct comparison with word_align should be avoided, however, since it is intended to work on corpora whose sentences are not aligned. blends syntactic and semantic notions. That semantic frames for different languages share common core arguments is more plausible than that syntactic frames do. 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--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 errors. Second, sentences containing nonliteral translations obviously cannot be aligned down to the word level. This accounted for another approximate 50% of the errors. Excluding these two types of errors, accuracy on word alignment 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.

Monolingual Parse Trees
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 grammatical 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 determines the split point S for breaking e0. T into two constituent subtrees deriving e0..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 turning 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: .

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 constraints may be derived from external sources beforehand. For example, a broad-coverage English bracketer may be available. If such constraints are reliable, it would be wasteful to ignore them. A straightforward extension to the original algorithm inhibits hypotheses that are inconsistent with given constraints. Any entries in the dynamic programming table corresponding to illegal subhypotheses--i.e., those that would violate the given bracket-nesting or word alignment conditions--are preassigned negative infinity values during initialization indicating impossibility. During the recursion phase, computation of these entries is skipped. Since their probabilities remain impossible throughout, the illegal subhypotheses will never participate in any ML bibracketing. The running time reduction in this case depends heavily on the domain constraints.
We have found this strategy to be useful for incorporating punctuation constraints. Certain punctuation characters give constituency indications with high reliability; "perfect separators" include colons and Chinese full stops, while "perfect delimiters" include parentheses and quotation marks.

Unrestricted-Form Grammars
It is possible to construct a parser that accepts unrestricted-form, rather than normalform, grammars. In this case an Earley-style scheme (Earley 1970), employing an active chart, can be used. The time complexity remains the same as the normal-form case.
We have found this to be useful in practice. For bracketing grammars of the type considered in this paper, there is no advantage. However, for more complex, linguistically structured grammars, the more flexible parser does not require the unreasonable numbers of productions that can easily arise from normal-form requirements. For most grammars, we have found performance to be comparable or faster than the normalform parser.

Conclusion
The twin concepts of bilingual language modeling and bilingual parsing have been proposed. We have introduced a new formalism, the inversion transduction grammar, and surveyed a variety of its applications to extracting linguistic information from parallel corpora. Its amenability to stochastic formulation, useful flexibility with leaky and minimal grammars, and tractability for practical applications are desirable properties. Various tasks such as segmentation, word alignment, and bracket annotation are naturally incorporated as subproblems, and a high degree of compatibility with conventional monolingual methods is retained. In conjunction with automatic procedures for learning word translation lexicons, SITGs bring relatively underexploited bilingual correlations to bear on the task of extracting linguistic information for languages less studied than English.
We are currently pursuing several directions. We are developing an iterative training method based on expectation-maximization for estimating the probabilities from parallel training corpora. Also, in contrast to the applications discussed here, which deal with analysis and annotation of parallel corpora, we are working on incorporating the SITG model directly into our run-time translation architecture. The initial results indicate excellent performance gains.