Aligning Needles in a Haystack: Paraphrase Acquisition Across the Web

Aligning Needles in a Haystack: Paraphrase Acquisition Across the Web Marius Pa¸sca and P´eter Dienes Google Inc., 1600 Amphitheatre Parkway, Mountain View, California, 94043, USA {mars, dienes}@google.com Abstract. This paper presents a lightweight method for unsupervised extraction of paraphrases from arbitrary textual Web documents. The method differs from previous approaches to paraphrase acquisition in that 1) it removes the assumptions on the quality of the input data, by using inherently noisy, unreliable Web documents rather than clean, trustworthy, properly formatted documents; and 2) it does not require any explicit clue indicating which documents are likely to encode parallel paraphrases, as they report on the same events or describe the same sto- ries. Large sets of paraphrases are collected through exhaustive pairwise alignment of small needles, i.e., sentence fragments, across a haystack of Web document sentences. The paper describes experiments on a set of about one billion Web documents, and evaluates the extracted para- phrases in a natural-language Web search application. 1 Introduction The information captured in textual documents frequently encodes semantically equivalent ideas through different lexicalizations. Indeed, given the generative power of natural language, different people employ different words or phrases to convey the same meaning, depending on factors such as background knowledge, level of expertise, style, verbosity and personal preferences. Two equivalent frag- ments of text may differ only slightly, as a word or a phrase in one of them is paraphrased in the other, e.g., through a synonym. Yet even small lexical variations represent challenges to any automatic decision on whether two text fragments have the same meaning, or are relevant to each other, since they are no longer lexically identical. Many natural-language intensive applications make such decisions internally. In document summarization, the generated summaries have a higher quality if redundant information has been discarded by detecting text fragments with the same meaning [1]. In information extraction, extrac- tion templates will not be filled consistently whenever there is a mismatch in the trigger word or the applicable extraction pattern [2]. Similarly, a question answering system could incorrectly discard a relevant document passage based on the absence of a question phrase deemed as very important [3], even if the passage actually contains a legitimate paraphrase. R. Dale et al. (Eds.): IJCNLP 2005, LNAI 3651, pp. 119–130, 2005. c ⃝ Springer-Verlag Berlin Heidelberg 2005 120 M. Pa¸sca and P. Dienes In information retrieval, deciding whether a text fragment (e.g., a document) is relevant to another text fragment (i.e., the query) is crucial to the overall out- put, rather than merely useful within some internal system module. Indeed, relevant documents or passages may be missed, due to the apparent mismatch between their terms and the paraphrases occurring in the users’ queries. The previously proposed solutions to the mismatch problem vary with respect to the source of the data used for enriching the query with alternative terms. In auto- matic query expansion, the top documents provide additional query terms [4]. An alternative is to attempt to identify the concepts captured in the …

Content truncated to 500 words