Locating paraphrases through utilization of a multipartite graph

• US 8,484,016 B2
• Filed: 05/28/2010
• Issued: 07/09/2013
• Est. Priority Date: 05/28/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Brockett, Christopher John, Kok, Stanley, Zhou, Dengyong
• Primary Examiner(s): PULLIAS, JESSE SCOTT
• Application Number:
  US12/789,472
• Publication Number:
  US 20110295589A1
• Time in Patent Office: 1,138 Days
• Field of Search: 704 2- 9
• US Class Current: 704/9
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06F 40/45 Example-based machine translation; Alignment

Abstract

A method is described herein that includes acts of receiving a selection of a first phrase in a first language and executing a random walk over a computer-implemented multipartite graph, wherein the multipartite-graph includes a first set of nodes that are representative of phrases in the first language, a second set of nodes that are representative of phrases in a second language, and edges between nodes that are representative of relationships between the respective phrases. The random walk includes traversals over edges of the graph between nodes. The method also includes the act of indicating that a second phrase in the first language is a paraphrase of the first phrase based at least in part upon the random walk.

Claims

1. A method comprising the following computer-executable acts:

receiving a selection of a first phrase in a first language;

executing a random walk over a computer-implemented multipartite graph, wherein a number of steps undertaken during the random walk is limited to a threshold number, wherein the multipartite graph comprises a first set of nodes that are representative of phrases in the first language, a second set of nodes that are representative of phrases in a second language, and edges between nodes that are representative of relationships between the respective phrases, and wherein the random walk comprises traversals over edges of the graph between nodes; and

indicating that a second phrase in the first language is a paraphrase of the first phrase based at least in part upon the random walk.

2. The method of claim 1, wherein the multipartite graph comprises nodes that are representative of phrases in a third language.

3. The method of claim 1, further comprising:

receiving the first phrase as at least a portion of a query that is desirably input to a search engine; and

responsive to receiving the first phrase, causing the search engine to execute a search over a plurality of documents based at least in part upon the second phrase.

5. The method of claim 1, further comprising:

receiving the first phrase as at least a portion of a query that is desirably input to a search engine; and

responsive to receiving the first phrase, causing an advertisement to be displayed based at least in part upon the second phrase.

6. The method of claim 1, wherein an edge between a first node in the first set of nodes that represents a phrase in the first language and a second node in the second set of nodes that represents a phrase in the second language indicates that the phrase in the first language has a substantially similar semantic meaning to the phrase in the second language.

7. The method of claim 6, wherein the edges in the multipartite graph are assigned weights, and wherein a weight assigned to an edge is indicative of a probability that nodes connected by the edge have a substantially similar semantic meaning.

8. The method of claim 1, further comprising constructing the multipartite graph from phrase tables, wherein the phrase tables comprise phrases in the first language and translations of the phrases in the second language.

9. The method of claim 1, further comprising outputting a ranked list of phrases that are paraphrases of the first phrase based at least in part upon the random walk.

10. The method of claim 1, wherein the first phrase is represented by a first node in the multipartite graph and the second phrase is represented by a second node in the multipartite graph, and further comprising:

counting a number of steps in the random walk between the first node and the second node; and

indicating that the second phrase is a paraphrase of the first phrase based at least in part upon the number of steps.

11. The method of claim 1, wherein the multipartite graph further comprises a third set of nodes that are representative of domain knowledge with respect to a particular language, and wherein edges exist between a node in the third set of nodes and multiple nodes in the first set of nodes.

4. The method 1, further comprising:

receiving the first phrase as at least a portion of a query that is desirably input to a search engine; and

responsive to receiving the first phrase, causing the search engine to display the second phrase as a suggested query.

12. A computing apparatus, comprising:

a processor; and

a memory that comprises components that are executed by the processor, the components comprising;

a random walk component that executes a random walk over a multipartite graph, wherein the multipartite graph comprises a first set of nodes that represent phrases in a first language, a second set of nodes that represent phrases in a second language, and edges between nodes in the first set of nodes and nodes in the second set of nodes, wherein an edge between two nodes indicates that phrases represented by the two nodes have a substantially similar semantic meaning, wherein the edges in the multipartite graph are weighted, and wherein the random walk component considers weights assigned to the edges when undertaking the random walk; and

a paraphrase indicator component that outputs a ranked list of phrases in the first language that are found to be paraphrases of a first phrase in the first language based at least in part upon the random walk executed by the random walk component.

13. The computing apparatus of claim 12, wherein the multipartite graph comprises a third set of nodes that represent phrases in a third language.

14. The computing apparatus of claim 12, wherein the components further comprise a counter component that counts a number of steps taken during the random walk between a first node representing the first phrase and a second node representing a second phrase in the ranked list of phrases, and wherein the paraphrase indicator component ranks the second phrase amongst phrases in the ranked list of phrases based at least in part upon the number of steps taken during the random walk.

15. The computing apparatus of claim 14, wherein the number of steps is limited to a threshold value.

16. The computing apparatus of claim 12, further comprising a builder component that accesses a phrase table and builds the multipartite graph based at least in part upon contents of the phrase table, wherein the phrase table comprises phrases in the first language and translations of such phrases in the second language.

17. The computing apparatus of claim 12, wherein the multipartite graph comprises at least one feature node, wherein the at least one feature node is representative of domain-specific knowledge pertaining to two or more phrases in the first language, and wherein the at least one feature node is an intermediary between the two or more nodes in the first set of nodes.

18. A computing device comprising a computer-readable medium, the computer-readable medium comprising instructions that, when executed by a processor, cause the processor to perform acts comprising:

executing a random walk over a computer-implemented multipartite graph, wherein the multipartite graph comprises;

a first set of nodes that represent phrases in a first language;

a second set of nodes that represent phrases in a second language;

a third set of nodes that represent phrases in a third language;

at least one feature node that represents a feature pertaining to phrases in the first language; and

edges between nodes that represent relationships between nodes connected by the edges;

wherein the random walk begins at a first node in the first set of nodes and travels over edges to other nodes in the multipartite graph;

counting a number of steps in the random walk between the first node in the first set of nodes and a second node in the first set of nodes; and

assigning a score to a phrase pair comprising a first phrase represented by the first node and a second phrase represented by the second node based at least in part upon the number of steps taken in the random walk between the first node and the second node, wherein the score is indicative of whether the second phrase is a paraphrase of the first phrase.

19. The computing device of claim 18, wherein the number of steps undertaken during the random walk is limited to a threshold number.

20. The computing device of claim 18, wherein the edges in the multipartite graph are weighted, and wherein the weights assigned to the edges are considered when executing the random walk.