Prepositional Phrase (PP) attachment disambiguation is an important problem in NLP, for it often gives rise to incorrect parse trees . Statistical parsers often predict incorrect attachment for prepositional phrases. For applications like Machine Translation, incorrect PP-attachment leads to serious errors in translation. Several approaches have been proposed to solve this problem. We attempt to tackle this problem for English. English is a syntactically ambiguous language with respect to PP attachments. For example, consider the following sentence where the prepositional phrase with pockets may attach either to the verb washed or to the noun jeans.Sentence INLINEFORM0 : I washed the jeans with pockets.Below is the correct dependency parse tree (for sentence 1) where the prepositional phrase with pockets is attached to the noun jeans.Another possible parse tree for the same sentence could be as shown in Figure FIGREF2 :A statistical parser often predicts the PP-attachment incorrectly, and may lead to incorrect parse trees. Let us now look at another sentence.Sentence INLINEFORM0 : I washed the jeans with soap.The correct dependency tree for sentence INLINEFORM0 is the following (Figure FIGREF3 ), where the prepositional phrase with soap attaches to the verb washed.Clearly, there is a case of ambiguity that can be resolved only if the semantics are known. In this case, the fact that soap is an aid to the verb washed disambiguates its attachment to the verb rather than the noun jeans. For correctly translating such an English sentence to another language, the attachments need to be marked correctly.In this work, we propose a Dual Decomposition (DD) based algorithm for solving the PP attachment problem. We try to disambiguate the PP attachments for English using the corresponding parallel Hindi corpora. Hindi is a syntactically rich language and in most cases exhibits no attachment ambiguities. The use of case markers and the inherent construction of sentences in Hindi make cases of ambiguity rarer. Let us examine how sentences 1 and 2 would look like in Hindi, and if there is a case for ambiguity.Sentence (3) and sentence (4) are the respective Hindi translations of sentence (1) and (2)). Sentence INLINEFORM0 : mn jb vAlF jF06ws DoyF INLINEFORM1 Sentence INLINEFORM0 : mn sAbn s jF06ws DoyF INLINEFORM1 In sentence (3), the prepositional phrase jeb waali attaches to the noun jeans as shown in the figure FIGREF4 .The parse tree for sentence (4) is shown in figure FIGREF5 , where the prepositional phrase saabun se attaches to the verb dhoyee.The case markers waali and se in the two sentences in Hindi make the pp-atttachment clear. In our approach, we make use of the parallel Hindi sentences to disambiguate the PP attachments for English sentences. The roadmap of the paper is as follows: We discuss the literature and related work for solving the PP-attachment problem in section [ SECREF2 ]. Section [ SECREF3 ] describes our approach, and the Dual Decomposition algorithm in detail. The setup, data, and experiments are covered in Section [ SECREF4 ]. With Section [ SECREF5 ], we conclude our work and discuss scope for future work.A number of supervised and unsupervised approaches for solving the PP-attachment problem have been proposed in the literature. Ratnaparkhi:94 use a Maximum Entropy Model for solving the PP-attachment decision. Schwartz:03 propose an unsupervised approach for solving PP attachment using multilingual aligned data. They transform the data into high-level linguistic representations and use it make reattachment decisions. The intuition is similar to our work, but the approach is entirely different. Brill:94 discuss a transformation-based rule derivation method for PP-attachment disambiguation. It is a simple learning algorithm which derives a set of transformation rules from training corpus, which are then used for solving the PP-attachment problem. Stetina:97 make use of the semantic dictionary to solve the problem of disambiguating PP attachments. Their work describes use of word sense disambiguation (WSD) for both supervised and unsupervised techniques. Agirre Agirre:08 and Medimi Medimi:07 have used WSD-based strategies in different capacities to solve the problem of PP-attachment. Olteanu:05 have attempted to solve the pp-attachment problem as a classification problem of attachment either to the preceding verb or the noun, and have used Support Vector Machines (SVMs) that use complex syntactic and semantic features.We propose a Dual Decomposition based inference algorithm to look at the problem of PP-attachment disambiguation. Dual decomposition, or more generally, Lagrangian Relaxation, is a classical method for combinatorial optimization and has been applied to several inference problems in NLP BIBREF0 . We train two separate parser models for English and Hindi each, using the MSTParser, and make use of these models in the inferencing step. The input to the algorithm is a parallel English-Hindi sentence pair, with its word alignments given. We first obtain the predicted parse trees for the English and Hindi sentences from the respective trained parser models as an initialsiation step. The DD algorithm then tries to enforce agreement between the two parse trees subject to the given alignments.Let us take a closer look at what we mean by agreement between the two parse trees. Essentially, if we have two words in the English sentence denoted by i and i', aligned to words j and j' in the parallel Hindi sentence respectively, we can expect a dependency edge between i and i' in the English parse tree to correspond to an edge between j and j' in the Hindi parse tree, and vice versa. Also, in order to accommodate structural diversity in languages BIBREF1 , we can expect an edge in the parse tree in one language to correspond to more than one edge, or rather, a path, in the other language parse tree. This has been captured in the examples in figures FIGREF6 (A) and FIGREF6 (B). For an edge in the English parse tree, we term the corresponding edge or path in the Hindi parse tree as the projection or projected path of the English edge on the Hindi parse tree, and similarly there are projected paths from Hindi to English. For matters of simplicity, we ignore the direction of the edges in the parse trees. The dual decomposition inference algorithm tries to bring the parse trees in the two languages through its constraints.The problem is formulated as below:In the above formulation, INLINEFORM0 and INLINEFORM1 represent a English and Hindi sentence respectively. INLINEFORM2 and INLINEFORM3 are the corresponding parse trees. INLINEFORM4 and INLINEFORM5 are the model parameters for the edge-factored parser models trained for English and Hindi respectively. INLINEFORM6 represents an edge in the English parse tree INLINEFORM7 . INLINEFORM8 is a projected path in Hindi parse tree INLINEFORM9 for a given English edge INLINEFORM10 . The term INLINEFORM11 stands for the score of a projected path in Hindi parse tree INLINEFORM12 for a given English edge INLINEFORM13 .The score of the projected path is calculated as the sum of scores of all edges in the path. Let INLINEFORM0 denote the projected path on sentence h in Hindi for the edge INLINEFORM1 in the English parse tree. We assume INLINEFORM2 where INLINEFORM3 is the score of edge a in the projected path INLINEFORM4 . In the other direction, INLINEFORM5 and INLINEFORM6 is similarly defined.To solve this maximization problem in figure FIGREF7 , we assume one tree to be given and maximize the other and the score of its projected path. The algorithm is described in detail in section SECREF8 .We use an iterative Coordinate Descent algorithm (Algorithm 1) which calls the Project Algorithm until convergence. The trees INLINEFORM0 and INLINEFORM1 are initialized by the previously trained parser models for the respective languages.Coordinate Descent Algorithm [1] Initialize INLINEFORM0 and INLINEFORM1 from the MSTParser models for INLINEFORM2 to INLINEFORM3 INLINEFORM4 INLINEFORM5 if INLINEFORM6 or INLINEFORM7 break else INLINEFORM8 INLINEFORM9 end forFor INLINEFORM0 iterations, the project function returns a parse tree for English which maximizes the agreement between the English and Hindi parse tree when the Hindi parse tree is fixed, and likewise for the Hindi parse tree. The algorithm converges when the trees no longer change,Let us now look at the Project algorithm (Algorithm 2) in detail. It predicts the tree for a sentence in the target language, given the parse tree in the source language, and the word alignments between the parallel sentence.Project Algorithm (tree T, sen S) [1] A parse tree T (Hindi) and sentence S (English) Initialize INLINEFORM0 INLINEFORM1 = 0 for INLINEFORM2 to INLINEFORM3 INLINEFORM4 for INLINEFORM5 INLINEFORM6  INLINEFORM0 end for if INLINEFORM1 then return INLINEFORM2 else INLINEFORM3 INLINEFORM4 end forThe lagrangian multipliers are initialized to zero. The best tree in the target language is predicted by the argmax computation in step 4. This maximization involves the parser model parameters INLINEFORM0 and the score of the best projected path in the source tree for all edges. INLINEFORM1 denotes the score of the projected path of the edge INLINEFORM2 on the source tree T. In steps 6 and 7, the best projected path for every edge of the source tree is predicted on the target tree using the classifiers described in section . The constraints here are that the edges in the projected paths from the classifiers and the predicted trees are in agreement.In order to predict the projected path in one language for an edge in the other language, we use a set of two classifiers in a pipeline. Let us recall that we have two nodes in one language with an edge between them, and we are trying to predict the path of the corresponding aligned nodes in the other language. The first classifier predicts the length of the projected path, and the second predicts the predicted path itself, given the path length from the first classifier. Let us look at these classifiers separately.The classifier for path length prediction is a set of five binary classifiers, which predict the path length to be 1, 2, 3, 4 or 5. We assume projected path lengths to be no greater than 5. These classifiers are perceptrons trained on separate annotated data. The features used were the words and POS tags of the four nodes in the pair of alignments under consideration.The classifier for path prediction is a set of four structured perceptron classifiers. We train four classifiers to predict the paths of length 2, 3, 4 and 5. These set of classifiers were trained on separate annotated data, and the features used were the same as in the set of classifiers for path length prediction.A parser model was trained for Hindi using the MSTParser BIBREF2 by a part of the the Hindi Dependency Treebank data (18708 sentences) from IIIT-Hyderabad BIBREF3 . A part of the Penn Treebank (28188 sentences) was used for training an English parser BIBREF4 . The treebanks were converted to MSTParser format from ConLL format for training. A part of the ILCI English-Hindi Tourism parallel corpus (1500 sentences) was used for training the classifiers. This corpus was POS-tagged using the Stanford POS Tagger BIBREF5 for English and using the Hindi POS Tagger BIBREF6 from IIIT-Hyderabad for Hindi. It was then automatically annotated with dependency parse trees by the parsers we had trained before English and Hindi.For testing, we created a corpus of 100 parallel sentences and their word alignments from the Hindi-English Tourism parallel corpus. We manually annotated the instances of pp-attachment ambiguity. We examine the prediction for attachment of only these cases. The baseline system used is the attachment predicted by the parser models trained using the MSTParser. We ran experiments on the test set for iterations 10 to 60, in steps of 10. The outputs from the MSTParser trained model and the DD algorithm were compared against the gold data for English.Our observations have been tabulated in Table TABREF10 . The MSTParser model was able to correctly disambiguate 54 number of PP-attachments. Our algorithm, however, performed better and marked 64 number of attachments correctly, in the best case. The baseline accuracy for PP attachment was 54%. With our approach, we were able to achieve an improvement of 10% over the baseline.We also experimented with the number of iterations to see if the attachment predictions got any better. The observations have been plotted in the graph in figure FIGREF11 . Our algorithm performed best at 30 iterations.In the event of lack of gold standard data for our experiments, we have used statistical POS taggers for POS tagging the data. Also, for getting word alignments, we have used GIZA++ BIBREF7 , which again has scope for errors. These kind of errors may cascade and cause our system to underperform.We were able to achieve an accuracy of 10% over the baseline using our approach. However, in terms of overall dependency parsing and not just with respect to PP-attachment, our system is unable to beat the MSTParser model. However, we need to test our approach on a larger dataset, and across other domains besides Tourism. Besides Hindi, there is also scope for exploring other languages as an aid for pp-attachment disambiguation in English. Our approach could also be used for wh-clause attachment. Since incorrect pp-attachment has a direct consequence on Machine Translation, one interesting analysis could be to use pp-attachments from our system and check for improvement in the quality of translation.

Q: What is the size of the parallel corpus used to train the model constraints?

Q: How does enforcing agreement between parse trees work across different languages?