Automatic Acquisition of Context-Specific Lexical Paraphrases

1 Introduction

Paraphrases are alternative ways that convey the same information. Paraphrasing tasks can be classified as lexical, phrase-level, sentence-level, and discourse-level. Lexical paraphrasing aims to acquire paraphrases of words.

Lexical paraphrasing is important in many NLP applications since it is an effective solution to the problem of "word mismatch". For example, in QA, expanding a question by paraphrasing its content words can make it easier to find the answer [Hermjakob et al., 2002]. In IE, words and phrases in the IE patterns should be paraphrased in order to extract the target information expressed in various ways [Shinyama and Sekine, 2003]. In MT, paraphrases of unseen source words can be incorporated into the statistical MT process. Specifically, paraphrases of unseen words can be translated rather than leave the words untranslated [Callison-Burch et al., 2006].

Two broad approaches to lexical paraphrasing have dominated the literature. One approach acquires paraphrases from dictionaries, such as WordNet. Some researchers extract WordNet synonyms as paraphrases [Langkilde and Knight, 1998], while some others use looser definitions [Barzilay and Elhadad, 1997]. In general, the correspondence between paraphrasing and types of lexical relations defined in WordNet is not clear [Barzilay and McKeown, 2001]. In Chinese, CilinE has been exploited for paraphrasing in stead of WordNet [Li et al., 2005].

The other approach collects lexical paraphrases from monolingual or bilingual corpora. Lin [1998] identified words that are similar in meaning by measuring the similarity of the contextual words. Barzilay and McKeown [2001] extracted paraphrases from a corpus of multiple English translations of the same source text. Bannard and Callison-Burch [2005] derived paraphrases using bilingual parallel corpora. Wu and Zhou [2003] extracted lexical paraphrases with multiple resources, including a monolingual dictionary, a bilingual corpus, and a monolingual corpus.

These methods facilitate the acquisition of paraphrases. However, none of them specify the contexts in which the paraphrases can be adapted. This problem is crucial as almost all paraphrases can only be adapted in certain contexts.

Recently, topic adaptation for paraphrasing has been researched. For example, Kaji and Kurohashi [2005] selected lexical paraphrases according to different topics. However, the topics are limited and predefined. Thus, their method cannot paraphrase a word according to any given context.

This paper addresses the problem of context-specific paraphrasing (CSP), which aims at acquiring specific paraphrases according to a given context. In lexical CSP, words are to be paraphrased. Accordingly, a specific context means a sentence in which a word occurs. Specifically, if a word occurs in different sentences, then different paraphrases should be extracted within each sentence.

The remainder of the paper is organized as follows: Section 2 introduces the context-specific paraphrasing method in detail. Section 3 describes the experiments and results. Conclusion and future work are presented in Section 4.

2 Method

Two main stages are included in the method: candidate paraphrase extraction and paraphrase validation. For a given sentence S, in the first stage, a set of similar sentences are retrieved from the web using a search engine (Baidu 1 in the experiments). From the similar sentences, candidate paraphrases for words in S are extracted by measuring syntactic similarities. The candidates are filtered using part-of-speech (POS) information. In the second stage, candidate paraphrases are validated using a combined similarity measurement, which integrates co-occurrence similarity, syntactic similarity, and semantic similarity. Both the web and CilinE are exploited in the validation stage.

2.1 Candidate Paraphrase Extraction

2.1.1 Motivation

Candidate paraphrase extraction is based on a web mining method. A similar method has been exploited for paraphrasing answer patterns in QA [Ravichandran and Hovy, 2002]. Using the web as a paraphrasing resource has three advantages compared with conventional resources (monolingual parallel corpora, monolingual unparallel corpora, and bilingual parallel corpora). First, the web is not domain limited. Almost all kinds of topics and contexts can be covered. Second, the scale of the web is extremely large, which makes it feasible to find any specific context on it. In addition, the web is dynamic, which means that new words and concepts can be retrieved from the web.

The method for candidate paraphrase extraction is based on two principles:

Principle 1: Authors on the web create information independently. Thus their "vocabularies" vary greatly [Cui et al., 2002].

This principle means that different people tend to use different words to express the same meaning. In other words, if a concept is widely discussed on the web, then various expressions (lexical paraphrases) will be found in the corresponding web documents. However, a principle for detecting these paraphrases and extracting them from the web is needed. Therefore, the second principle is introduced.

Principle 2: Lexical paraphrases play similar syntactic functions in sentences.

The second principle indicates that paraphrases of a given word w can be derived by extracting words whose syntactic functions are similar with w.

In fact, the principles above have been used in recognizing paraphrases in previous work. Shinyama et al. [2002] acquired paraphrases using different reports on the same event of the same day (based on Principle 1). Lin [1998] clustered similar words by measuring syntactic similarities (based on Principle 2). The rationality of the principles has been verified in their work.

1 http://www.baidu.com

2.1.2 Procedure of Candidate Paraphrase Extraction

Two steps are included in candidate paraphrase extraction:

Step1: Query S on the web and retrieve similar sentences. Obviously, only similar sentences of the given sentence S need to be considered when extracting candidate paraphrases since if two words are context-specific paraphrases they should occur in identical or at least similar sentences. In this step, S is searched on the web using Baidu. From the retrieved snippets, sentences whose similarities with S exceed a predefined threshold TCE (TCE=0.3 in our case) are retained for further candidate extraction (these sentences are called candidate sentences hereafter). Word overlapping rate (WOR) is used here for computing the similarity between S and any candidate sentence SC:

where "S SC" denotes the common words in both S and SC. "|.|" denotes the number of words.

Step2: Extract candidates according to syntactic similarity. As stated in Principle 2, lexical paraphrases usually play similar syntactic functions in sentences. This is an important clue for candidate extraction. In this step, sentence S and all the candidate sentences obtained in the Step1 are first parsed by a Chinese dependency parser, in which 24 dependency relations (e.g. SBV, VOB, ATT…) are defined. Figure 1 depicts the dependency tree of an input sentence.

In a dependency tree of a sentence, two words and their dependency relation are represented as a triple. For example, "< , SBV, >" is a triple. The criterion shown in Figure 2 is used for extracting candidate paraphrases:

It is obvious that, a word and its paraphrases should have identical POS. Therefore, if the word w and its candidate paraphrase w' have different POSes, w' is filtered.

2.2 Paraphrase Validation

Since the constraints in the candidate extraction stage are quite loose for the sake of recall, there exists much noise in the candidates. The experiments show that over 70% of the candidates are incorrect. Therefore, a paraphrase validation stage is necessary.

Paraphrase validation is one of the key issues in the research of paraphrasing. Hence many methods have been presented. For example, Barzilay and McKeown [2001] recognized phrasal paraphrases using rules automatically extracted from the contexts. However, the method must be based on monolingual parallel corpora. Bannard and Callison-Burch [2005] validated paraphrases by computing the probability that two phrases can be translated to (or from) the same foreign language phrases. Nevertheless, a large bilingual corpus is needed. Lin [1998] identified lexical paraphrases based on Distributional Hypothesis, which computes the similarity of two words' contexts to judge whether they are paraphrases.

The main disadvantage of the above methods is that none of them can determine whether two words are paraphrases within a certain sentence. In other words, they are not context-specific paraphrasing methods. In our work, a novel paraphrase validation method is proposed, in which both web information and a thesaurus are exploited.

2.2.1 Paraphrase Validation Using Web Mining

Generally, when a query is searched using a search engine, the retrieved snippets are related to the query and can be viewed as "description" of the query. Therefore, it can be assumed that if two queries can retrieve similar snippets, then they are similar.

This assumption is used in paraphrase validation. In detail, let w be a paraphrased word in sentence S, w' be a candidate paraphrase of w within S, and S' be a sentence constructed by replacing w with w' in S. If similar snippets are retrieved by searching S and S', then we can say that replacing w with w' does not notably change the meaning of S. In other words, w and w' can be viewed as paraphrases in S.

Suppose Sni(S) and Sni(S') are the snippets corresponding to S and S' respectively. Here, sentences that do not contain w (w') are removed from Sni(S) (Sni(S')) to filter noise.

Two similarity measurements are defined to measure the snippet-based similarity between w and w', i.e. the Vector Space Model (VSM) similarity (SimVSM) and the syntactic similarity (SimSYN).

SimVSM: In VSM, snippets Sni(S) and Sni(S') are represented as vectors V(S) and V(S'). The weight of each word is calculated using a tf itf heuristic (Equation 2).

where tf(t, Sni(S)) denotes the term frequency of term t in snippets Sni(S). tf(t, CCD) is t's term frequency counted on a China Daily Corpus (CCD). max(tf(t', CCD)) is the largest term frequency obtained on the corpus. Note that the itf part in the equation is similar to the idf part in tf idf heuristic which is widely used in NLP and Information Retrieval (IR) applications. The underlying hypothesis is that the words occur frequently in the whole corpus should be "punished" when weighing the words.

The VSM similarity between w and w' is calculated as the cosine similarity between V(S) and V(S'):

where " " denotes the inner product of two vectors. " " denotes the length of a vector.

SimSYN: In order to compute the syntactic similarity, Sni(S) and Sni(S') are first parsed using the same dependency parser described above. The syntactic similarity is calculated with the same method as described in [Lin, 1998b], which is rewritten in Equation (4). The similarity is calculated through the surrounding contextual words which have dependency relationships with the investigated words according to the parsing results.

where T(w) denotes the set of words which have the dependency relation rel with w. I(w,rel,t) is the point-wise mutual information, as defined in Equation (5):

SimVSM and SimSYN measure the snippet-based similarity of two words from different aspects. SimVSM can also be called co-occurrence similarity since it measures whether w and w' co-occur with similar words in the snippets. All words in the snippets are assumed to be independent with each other and no syntactic relations are considered. In contrast, SimSYN measures whether w and w' play similar syntactic functions in the snippets. Only the words that have dependency relations with w (or w') in the snippets are counted and the dependency relation types are taken into account.

2.2.2 Paraphrase Validation Using CilinE

Beside SimVSM and SimSYN, the semantic similarity (SimSEM) is also investigated for paraphrase validation.

SimSEM: CilinE is organized as a hierarchy of five levels, in which the first level is the highest and the fifth is the lowest (Figure 3 (a)). Given two words, the lower their common ancestor node is, the more similar their word senses are. Each word in CilinE has a sense code, determining its position in each level of the hierarchy (Figure 3 (b)).

For word w and its candidate paraphrase w', wsi and ws j' denote the i-th sense of w and the j-th sense of w' (Note that a word may have more than one word sense). SimSEM of w and w' is defined in Equation (6):

where L(F(wsi, ws j')) is the lowest ancestor node that two sense codes have in the hierarchy. LTotal is the number of total levels (LTotal =5). For w and w', the maximal similarity of their senses is defined as the semantic similarity.

Obviously, SimSEM only measures the semantic distance between two words, in which no context information is considered. However, it is useful in paraphrase validation as a supplement to the snippet-based similarity. In our future work, a refined semantic similarity measurement [Lin, 1998a] will be investigated.

2.2.3 Linear Combination of Similarities

The three similarities defined above measure the similarity of two words from different sides. In order to integrate the similarities, we get them linearly combined:

where , , and are positive and 1 . The combined similarity SimCOM is used in paraphrase validation. Detailedly, for word w and its candidate paraphrase w', if SimCOM(w,w')>T (T is a predefined threshold), then the candidate w' will be validated as a true paraphrase. Otherwise, w' will be filtered. , , and T are estimated using a development set (Section 3.2.1).

3 Evaluation

3.1 Data and Metrics

In order to evaluate the CSP method, a sentence corpus is needed. In our experiments, a corpus of news titles is used as test data. The reasons are two folded. On the one hand, news titles are usually well-formed sentences. On the other hand, in many applications, such as QA, IE, and multi-document summarization, the words and sentences to be paraphrased are usually from news articles. The news titles are from the "important news" section of "Sina news 2 ". All titles from March 15, 2006 to April 5, 2006 are downloaded. After removing some duplicated ones, 257 titles are left for constructing the test data. Likewise, another 210 titles from April 6, 2006 to April 30, 2006 are downloaded to form the development data.

The metrics in the experiments are macro-averaged precision, recall, and f-measure. Let M1, …, MT be T paraphrasing methods to be compared (in our experiments, the compared methods are MCSP, MCilinE, MCSP-CAN, MVSM+SYN, MVSM+SEM, and MSYN+SEM, which will be described in the next section), N the number of sentences in test data, nti the number of words in the i-th sentence that can be paraphrased by method Mt (1 t T), ntij the number of acquired paraphrases for the j-th paraphrased word in the i-th sentence using method Mt, mtij the number of correct paraphrases (judged manually) in the ntij paraphrases. The precision of method Mt is defined as:

Compared with precision, recall is more difficult to calculate since it is impossible to enumerate all paraphrases that a word has within a context. Therefore, an approximate approach is used to calculate recall of each method. Specifically, for the j-th paraphrased word in the i-th sentence, all its correct paraphrases acquired by the T methods are put together (with duplication removed). Let ni be the number of words in the i-th sentence that can be paraphrased by at least one method, mij the total number of correct paraphrases for the j-th word. We assume that mij is the number of paraphrases that the word can really have within this specific sentence. Then the recall of method Mt is defined as:

Note that, the recall of a method will be over-estimated using the definition of Equation (9), since some correct paraphrases may be absent. However, it is reasonable to get a set of methods compared in this way.

The f-measure of method Mt is defined as:

3.2 Results and Analysis

3.2.1 Comparison between MCSP and MCilinE

In this section, we compare the CSP method (MCSP) with the method extracting CilinE synonyms as paraphrases (MCilinE).

2 http://news.sina.com.cn

In MCilinE, word sense disambiguation (WSD) is first conducted. A supervised method based on Bayesian Model is used in the WSD module, which can achieve a precision of 89.67% in our evaluation. Then, all synonyms of a word under the chosen sense are extracted as its paraphrases. In MCSP, the development data is used to determine the parameters. The parameters for getting highest f-measure scores on the development data are selected. As a result, the coefficients , and in Equation (7) are 0.74, 0.10, and 0.16 respectively. The similarity threshold T is 0.12. The comparison results are shown in Table 1:

It can be seen from Table 1 that the precision of MCilinE is quite low, which shows that most synonyms defined in CilinE are not paraphrases in specific contexts. On the other hand, the recall of MCSP is lower than MCilinE, this is mainly because CilinE can provide some correct paraphrases that are not used in web documents. However, it is found that over 85% of the correct paraphrases derived in MCSP are not synonyms in CilinE. This suggests that MCSP is effective in extracting "new" paraphrases. An example of the derived paraphrases of the two methods is illustrated in Figure 4 (words in bold are manually judged correct paraphrases):

3.2.2 Evaluation of Validation Methods

In this section, we first evaluate the paraphrase validation method. Therefore, we compare MCSP with the method that only extracts candidate paraphrases as described in Section 2.1 without validation (MCSP-CAN). The comparison results are shown in Table 2.

It can be found that MCSP outperforms MCSP-CAN greatly in precision, which indicates that the validation method is effective in filtering incorrect candidates. At the same time, recall decreases after validation, which suggests that some correct paraphrases are filtered by mistake. Nevertheless, the increase in F-measure demonstrates the effectiveness of paraphrase validation.

As mentioned before, three kinds of similarities are combined during paraphrase validation in MCSP. The contribution of each one should be evaluated. Therefore we compare MCSP with MVSM+SYN (combining SimVSM and SimSYN), MVSM+SEM (combining SimVSM and SimSEM), and MSYN+SEM (combining SimSYN and SimSEM).

For the three methods to be compared, the coefficients , and in Equation (7) and the similarity threshold T are also estimated using the development data (Table 3). The comparison results are shown in Table 4.

We can find from Table 4 that eliminating each similarity in the paraphrase validation can produce a notable degradation in precision (drop 28.10%, 21.07%, and 18.59%, respectively) and f-measure (drop 11.23%, 10.72%, and 6.49%, respectively), while the impact on recall is slight.

The comparison results suggest that each of the similarity measurements is useful in filtering incorrect candidates and the combination of all the three similarities can achieve the best performance.

We believe that three major factors should be taken into consideration in paraphrase validation, that is, whether two words co-occur with similar contextual words, whether they play similar syntactic functions in sentences, and whether their semantic distance is small. The combined similarity in Equation (7) integrates all these factors. Hence the f-measure is significantly enhanced.

3.2.3 Error Analysis

False positives 3 are analyzed after experiments. It is found that nearly 84% of the false positives are due to the reason that non-paraphrases occur in similar contexts. For example, in sentence " (Ding Junhui failed to enter the final of the snooker match)", " (final)" is paraphrased into " (main draw match)", since these two words have occurred in very similar sentences from the reports about Ding's two different matches. In order to solve this problem, we believe that, some new features should be used when representing contexts, such as Named Entities (NE).

3 False positives are word pairs recognized as paraphrases, but actually are not.

Another 10% mistakes are owing to CilinE, because it assigns high semantic similarities to some non-paraphrase word pairs (such as " (Tsinghua university)" and " (Renmin University)") during paraphrase validation.

The other 6% false positives are due to mistakes of the preprocessing modules, including word segmentation, POS tagging, and syntactic parsing.

4 Conclusion

This paper proposes a web mining method to automatically acquire context-specific lexical paraphrases. There are three main contributions. First, this work focuses on the problem of context-specific paraphrasing, which is very important but has seldom been addressed before. Second, a novel two-stage method is presented, which uses the web as resource instead of monolingual or bilingual corpora used in conventional work. Third, three similarity measurements are investigated and combined for paraphrase validation.

Experiments are carried out on a news title corpus and the results show that our method can achieve a precision of 0.6380, which is dramatically higher than the method extracting paraphrases from CilinE (0.0630). In addition, over 85% of the paraphrases derived by MCSP cannot be extracted from CilinE, which suggests that the web is an eligible resource for acquiring context-specific paraphrases and the presented method is effective. Results also show that all the similarity measurements introduced in paraphrase validation make notable contribution to filtering incorrect candidates.

The main disadvantage of this method is that its time complexity is high, as snippets must be downloaded in the validation of each candidate paraphrase. This may make the method impractical in some applications, such as IR and QA. In the future work, we will construct a context-specific paraphrase corpus using the CSP method, which contains not only paraphrase pairs, but also contexts in which the paraphrases can be adapted. Context-specific paraphrases can be extracted directly from the corpus in practice.

Besides, the CSP method will be extended to the acquisition of phrase-level paraphrases. In addition, this method will be tested on normal sentences other than news titles.

Acknowledgments

This research was supported by National Natural Science Foundation of China (60575042, 60503072, 60675034). We thank Wanxiang Che for his valuable advice and comments.

Reference

• [Bannard and Callison-Burch, 2005] Colin Bannard and Chris Callison-Burch. Paraphrasing with Bilingual Parallel Corpora. In Proceedings of ACL, 2005.
• [Barzilay and Elhadad, 1997] Regina Barzilay and Michael Elhadad. Using Lexical Chains for Text Summarization. In Proceedings of the ACL Workshop on Intelligent Scalable Text Summarization, 1997.
• [Barzilay and McKeown, 2001] Regina Barzilay and Kathleen R. McKeown. Extracting Paraphrases from a Parallel Corpus. In Proceedings of the ACL/EACL, 2001.
• [Callison-Burch et al., 2006] Chris Callison-Burch, Philipp Koehn, and Miles Osborne. Improved Statistical Machine Translation Using Paraphrases. In Proceedings of NAACL, 2006.
• [Cui et al., 2002] Hang Cui, Ji-Rong Wen, Jian-Yun Nie, and Wei-Ying Ma. Probabilistic Query Expansion Using Query Logs. In Proceedings of WWW, 2002.
• [Hermjakob et al., 2002] Ulf Hermjakob, Abdessamad Echihabi, and Daniel Marcu. Natural Language Based Reformulation Resource and Web Exploitation for Question Answering. In Proceedings of the TREC-2002 Conference, 2002.
• [Kaji and Kurohashi, 2005] Nobuhiro Kaji and Sadao Kurohashi. Lexical Choice via Topic Adaptation for Paraphrasing Written Language to Spoken Language. In Proceedings of IJCNLP, 2005.
• [Langkilde and Knight, 1998] Irene Langkilde and Kevin Knight. Generation that Exploits Corpus-based Statistical Knowledge. In Proceedings of the COLING/ACL, 1998.
• [Li et al., 2005] Weigang Li, Ting Liu, Yu Zhang, Sheng Li, and Wei He. Automated Generalization of Phrasal Paraphrases from the Web. In Proceedings of IWP, 2005.
• [Lin, 1998a] Dekang Lin. An Information-Theoretic Definition of Similarity. In Proceedings of ICML, 1998.
• [Lin, 1998b] Dekang Lin. Optimizing Synonym Extraction Using Monolingual and Bilingual Resources. In Proceedings of COLING/ACL, 1998.
• [Ravichandran and Hovy, 2002] Deepak Ravichandran and Eduard Hovy. Learning Surface Text Patterns for a Question Answering System. In Proceedings of ACL, 2002.
• [Shinyama and Sekine, 2003] Yusuke Shinyama and Satoshi Sekine. Paraphrase Acquisition for Information Extraction. In Proceedings of IWP, 2003.
• [Shinyama et al., 2002] Yusuke Shinyama, Satoshi Sekine, Kiyoshi Sudo, and Ralph Grishman. Automatic Paraphrase Acquisition from News Articles. In Proceedings of HLT, 2002.
• [Wu and Zhou, 2003] Hua Wu and Ming Zhou. Optimizing Synonym Extraction Using Monolingual and Bilingual Resources. In Proceedings of IWP, 2003.