Power-Law Distributions for Paraphrases Extracted from Bilingual Corpora

Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 2–11, Avignon, France, April 23 - 27 2012. c⃝2012 Association for Computational Linguistics Power-Law Distributions for Paraphrases Extracted from Bilingual Corpora Spyros Martzoukos Christof Monz Informatics Institute, University of Amsterdam Science Park 904, 1098 XH Amsterdam, The Netherlands {s.martzoukos, c.monz}@uva.nl Abstract We describe a novel method that extracts paraphrases from a bitext, for both the source and target languages. In order to reduce the search space, we decom- pose the phrase-table into sub-phrase-tables and construct separate clusters for source and target phrases. We convert the clus- ters into graphs, add smoothing/syntactic- information-carrier vertices, and compute the similarity between phrases with a ran- dom walk-based measure, the commute time. The resulting phrase-paraphrase probabilities are built upon the conversion of the commute times into artificial co- occurrence counts with a novel technique. The co-occurrence count distribution be- longs to the power-law family. 1 Introduction Paraphrase extraction has emerged as an impor- tant problem in NLP. Currently, there exists an abundance of methods for extracting paraphrases from monolingual, comparable and bilingual cor- pora (Madnani and Dorr, 2010; Androutsopou- los and Malakasiotis, 2010); we focus on the lat- ter and specifically on the phrase-table that is ex- tracted from a bitext during the training stage of Statistical Machine Translation (SMT). Bannard and Callison-Burch (2005) introduced the pivot- ing approach, which relies on a 2-step transition from a phrase, via its translations, to a paraphrase candidate. By incorporating the syntactic struc- ture of phrases (Callison-Burch, 2005), the qual- ity of the paraphrases extracted with pivoting can be improved. Kok and Brockett (2010) (hence- forth KB) used a random walk framework to de- termine the similarity between phrases, which was shown to outperform pivoting with syntac- tic information, when multiple phrase-tables are used. In SMT, extracted paraphrases with asso- ciated pivot-based (Callison-Burch et al., 2006; Onishi et al., 2010) and cluster-based (Kuhn et al., 2010) probabilities have been found to im- prove the quality of translation. Pivoting has also been employed in the extraction of syntactic para- phrases, which are a mixture of phrases and non- terminals (Zhao et al., 2008; Ganitkevitch et al., 2011). We develop a method for extracting para- phrases from a bitext for both the source and tar- get languages. Emphasis is placed on the qual- ity of the phrase-paraphrase probabilities as well as on providing a stepping stone for extracting syntactic paraphrases with equally reliable prob- abilities. In line with previous work, our method depends on the connectivity of the phrase-table, but the resulting construction treats each side sep- arately, which can potentially be benefited from additional monolingual data. The initial problem in harvesting paraphrases from a phrase-table is the identification of the search space. Previous work has relied on breadth first search from the query phrase with a depth of 2 (pivoting) and 6 (KB). The former can be too restrictive and the latter can lead to excessive noise contamination when taking shallow syntac- …

Content truncated to 500 words