Principled Approach to Paraphrasing

• US 20090119090A1
• Filed: 11/01/2007
• Published: 05/07/2009
• Est. Priority Date: 11/01/2007
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Niu, Cheng, Zhou, Ming
• Application Number:
  US11/934,010
• Publication Number:
  US 20090119090A1
• Time in Patent Office: Days
• US Class Current: 704/1
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 40/166 Editing, e.g. inserting or deleting
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models
• CPC Class Codes: G06F 40/45 Example-based machine translation; Alignment

Abstract

A principled approach to paraphrasing analyzes input text and paraphrases at atomic linguistic level, instead of analyzing the input text and paraphrases as a whole set at one time. The principled approach extracts atomic linguistic elements from the input text and identifies matching atomic paraphrasing elements to form candidate atomic paraphrasing pairs. A variety of atomic transformation types are identified to form atomic paraphrasing pairs. The candidate atomic paraphrasing pairs are evaluated using feature functions and a probability model. The principled approach scores a combination of multiple candidate atomic paraphrasing pairs using a score function which derives its value from the feature functions of the candidate atomic paraphrasing pairs. A combination which has a high score may be used for constructing a paraphrasing text.

Claims

1. A method for automatic paraphrasing, the method comprising:

selecting a plurality of atomic linguistic elements from an input text, the plurality of atomic linguistic elements including at least one atomic linguistic element kind selected from a word, a phrase, a pattern and a lexical dependency tree;

identifying a plurality of candidate atomic paraphrasing pairs each having one of the plurality of atomic linguistic elements and an atomic paraphrasing element;

selecting a combination of candidate atomic paraphrasing pairs; and

constructing a paraphrasing text of the input text using the atomic paraphrasing elements in the selected combination of candidate atomic paraphrasing pairs.

2. The method as recited in claim 1, wherein selecting the plurality of atomic linguistic elements comprises extracting atomic linguistic elements from the input text.

3. The method as recited in claim 1, wherein the at least one atomic linguistic element kind has multiple atomic linguistic elements.

4. The method as recited in claim 1, wherein identifying the plurality of candidate atomic paraphrasing pairs comprises:

for each atomic linguistic element, selecting at least one atomic paraphrasing element from a data source based on a probability model, wherein the atomic linguistic element relates to the selected at least one atomic paraphrasing element through an atomic transformation recognized by the data source.

5. The method as recited in claim 1, wherein the atomic linguistic element of each candidate atomic paraphrasing pair relates to the respective atomic paraphrasing element through an atomic transformation selected from a group consisted of lexical substitution, active and passive exchange, reordering of sentence components, realization in different syntactic components, head omission, prepositional phrase attachment, change into different sentence types, morphological derivation, light verb construction, exchange of comparatives and superlatives, converse word substitution, verb nominalization, substitution using words with overlapping meanings, inference, and different somatic role realization.

6. The method as recited in claim 1, wherein selecting the combination of candidate atomic paraphrasing pairs comprises:

for each atomic paraphrasing pair, obtaining a value of an appropriate feature function describing a probability of the atomic paraphrasing pair;

for each combination of candidate atomic paraphrasing pairs, computing a composite paraphrasing score based on the values of feature functions of the atomic paraphrasing pairs in the respective combination; and

selecting the combination of candidate atomic paraphrasing pair based on the composite paraphrasing score.

7. The method as recited in claim 1, further comprising:

forming a plurality of combinations of candidate atomic paraphrasing pairs; and

computing a composite paraphrasing score of each combination of candidate atomic paraphrasing pair, the composite paraphrasing score being used as a basis for selecting the combination of candidate atomic paraphrasing pairs used for constructing the paraphrasing text of the input text.

8. The method as recited in claim 1, wherein the method is incorporated in a word processor, the input text being generated by a user, and the paraphrasing text being output to the user as an alternative to the input text.

9. The method as recited in claim 1, wherein the method is incorporated in a search engine, the input text being generated by a user as a search query, and the paraphrasing text being used by the search engine as an alternative search query.

10. The method as recited in claim 1, wherein the method is incorporated in a search engine, the input text being provided by a data source as a search object, and the paraphrasing text being used by the search engine as an alternative search object.

11. A method for automatic paraphrasing, the method comprising:

selecting a plurality of atomic linguistic elements from an input text, the plurality of atomic linguistic elements including at least one linguistic element kind selected from a word, a phrase, a pattern and a lexical dependency tree;

for each atomic linguistic element, selecting at least one atomic paraphrasing element, wherein the atomic linguistic element relates to the selected at least one atomic paraphrasing element through an atomic transformation to form a candidate atomic paraphrasing pair;

obtaining a probability value of each candidate atomic paraphrasing pair;

computing a composite paraphrasing score of a combination of candidate atomic paraphrasing pairs based on the probability values of the candidate atomic paraphrasing pairs;

selecting the combination of candidate atomic paraphrasing pairs if the respective composite paraphrasing score satisfies a preset condition; and

constructing a paraphrasing text using the atomic paraphrasing elements in the selected combination of candidate atomic paraphrasing pairs.

12. The method as recited in claim 11, wherein the at least one atomic paraphrasing element of each atomic linguistic element is selected from a data source based on a probability model, wherein the atomic transformation between the atomic linguistic element and the respective at least one atomic paraphrasing element is recognized by the data source.

13. The method as recited in claim 11, wherein the probability value of each candidate atomic paraphrasing pair is obtained using an appropriate feature function of the atomic paraphrasing pair.

14. The method as recited in claim 11, wherein obtaining the probability value of each candidate atomic paraphrasing pair comprises determining a value of an appropriate feature function of the atomic paraphrasing pair;

and wherein computing the composite paraphrasing score of a combination of candidate atomic paraphrasing pairs comprises computing a value of a score function which is a product of the appropriate feature functions of the candidate atomic paraphrasing pairs in the combination.

15. The method as recited in claim 11, further comprising:

forming a plurality of combinations of candidate atomic paraphrasing pairs from a plurality of candidate atomic paraphrasing pairs; and

computing the composite paraphrasing score of each of the plurality of combinations of candidate atomic paraphrasing pairs.

16. The method as recited in claim 11, wherein the atomic transformation relating each atomic linguistic element to the respective atomic paraphrasing element is selected from a group consisted of lexical substitution, active and passive exchange, reordering of sentence components, realization in different syntactic components, head omission, prepositional phrase attachment, change into different sentence types, morphological derivation, light verb construction, exchange of comparatives and superlatives, converse word substitution, verb nominalization, substitution using words with overlapping meanings, inference, and different somatic role realization.

17. The method as recited in claim 11, wherein the method is incorporated in a word processor, the input text being generated by a user, and the paraphrasing text being output to the user as an alternative to the input text.

18. The method as recited in claim 11, wherein the method is incorporated in a search engine, the input text being either generated by a user as a search query or provided by a data source as a search object, and the paraphrasing text being either used by the search engine as an alternative search query or used by the search engine as an alternative search object.

19. One or more computer readable media having stored thereupon a plurality of instructions that, when executed by a processor, causes the processor to:

select a plurality of atomic linguistic elements from an input text, the plurality of atomic linguistic elements including at least one atomic linguistic element kind selected from a word, a phrase, a pattern and a lexical dependency tree;

identify a plurality of candidate atomic paraphrasing pairs each having one of the plurality of atomic linguistic elements and an atomic paraphrasing element;

select a combination of candidate atomic paraphrasing pairs; and

construct a paraphrasing text of the input text using the atomic paraphrasing elements in the selected combination of candidate atomic paraphrasing pairs.

20. The one or more computer readable media as recited in claim 19, wherein in order to identify the plurality of candidate atomic paraphrasing pairs, the plurality of instructions, when executed by the processor, causes the processor to:

for each atomic linguistic element, select at least one atomic paraphrasing element from a data source based on a probability model, wherein the atomic linguistic element relates to the selected at least one atomic paraphrasing element through an atomic transformation recognized by the data source.