Graph-based ranking algorithms for text processing

• US 7,809,548 B2
• Filed: 03/09/2005
• Issued: 10/05/2010
• Est. Priority Date: 06/14/2004
• Status: Expired due to Fees

• Current Assignee: University of North Texas
• Original Assignee: University of North Texas
• Inventors: Mihalcea, Rada, Tarau, Paul
• Primary Examiner(s): Smits; Talivaldis Ivars
• Assistant Examiner(s): Baker; Matthew H
• Application Number:
  US11/075,625
• Publication Number:
  US 20050278325A1
• Time in Patent Office: 2,036 Days
• Field of Search: 704 1- 10, 704/260
• US Class Current: 704/1
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

The present invention provides a method of processing at least one natural language text using a graph. The method includes determining a plurality of text units based upon the natural language text, associating the plurality of text units with a plurality of graph nodes, and determining at least one connecting relation between at least two of the plurality of text units. The method also includes associating the at least one connecting relation with at least one graph edge connecting at least two of the plurality of graph nodes and determining a plurality of rankings associated with the plurality of graph nodes based upon the at least one graph edge. The method can also include a graphical visualization of at least one important text unit in a natural language text or collection of texts. Methods for word sense disambiguation, keyword extraction, and sentence extraction are also provided.

Claims

1. A method of processing at least one natural language text using a graph, comprising:

selecting, using a processing unit, a plurality of text units from said at least one natural language text;

associating, using the processing, unit, the plurality of text units with a plurality of graph nodes such that each graph node corresponds to one of the text units selected from said at least one natural language text;

determining, using the processing unit, at least one connecting relation between at least two of the plurality of text units;

associating, using the processing unit, the at least one connecting relation with at least one graph edge connecting at least two of the plurality of graph nodes;

constructing, using the processing unit, a graph using only the plurality of graph nodes that correspond to one of the text units selected from said at least one natural language text and said at least one graph edge; and

determining, using the processing unit, at least one ranking by applying a graph-based ranking algorithm to the graph, wherein determining the at least one ranking comprises ranking the plurality of graph nodes based upon the at least one graph edge so that the ranking represents the relative importance, within the natural language text, of the text units associated with the graph nodes, and wherein ranking the plurality of graph nodes based upon the at least one graph edge comprises;

assigning a plurality of first scores to the plurality of graph nodes;

defining a relationship between a second score of each graph node and second scores, of graph nodes coupled to each graph node by a graph edge; and

determining a plurality of second scores associated with the plurality of graph nodes by applying an iterative recursive algorithm starting with the first plurality of scores and iterating until the relationship is satisfied.

2. The method of claim 1, wherein ranking the graph nodes comprises sorting the second plurality of scores to produce a plurality of rankings associated with the plurality of graph nodes.

4. The method of claim 1 or 3, further comprising selecting at least one keyword from the plurality of text units based upon the rankings.

5. The method of claim 1 or 3, wherein the plurality of text units comprises a plurality of sentences, and comprising selecting at least one of the plurality of sentences based upon the rankings.

6. The method of claim 5, further comprising forming a summary of the natural language text, the summary comprising the at least one selected sentence.

7. The method of claim 5, further comprising forming at least one summary of a plurality of natural language texts by combining sentences having the highest rankings determined using the rankings associated with the plurality of sentences in the plurality of texts.

8. The method of claim 1 or 6, further comprising selecting at least one word sense associated with at least one of the plurality of text units based upon the rankings.

3. A method of processing at least one natural language text using a graph, comprising:

selecting, using a processing unit, a plurality of text units from said at least one natural language text;

associating, using the processing unit, the plurality of text units with a plurality of graph nodes such that each graph node corresponds to one of the text units selected from said at least one natural language text;

determining, using the processing unit, at least one connecting relation between at least two of the plurality of text units;

associating, using the processing unit, the at least one connecting relation with at least one graph edge connecting at least two of the plurality of graph nodes;

constructing, using the processing unit, a graph using only the plurality of graph nodes that correspond to one of the text units selected from said at least one natural language text and said at least one graph edge; and

determining, using the processing unit, at least one ranking by applying a graph-based ranking algorithm to the graph, wherein said at least one graph edge comprises a plurality of graph edges and wherein determining said at least one ranking comprises ranking the graph edges based upon the plurality of graph nodes and wherein ranking the graph edges based upon the plurality of graph nodes comprises;

assigning a first score to each graph edge;

defining a relationship between a second score of each graph edge and second scores of graph edges coupled to a common graph node; and

determining a second score associated with each graph edge by applying an iterative recursive algorithm and iterating until the relationship is satisfied.

9. The method of claim 3, wherein ranking the graph edges comprises sorting the second scores to rank the graph edges.

10. A method of disambiguating word senses in at least one natural language text using a graph, comprising:

selecting, using a processing unit, a plurality of text units from said at least one natural language text;

associating, using the processing unit, at least one word sense with each text unit selected from said at least one natural language text;

associating, using the processing unit, the plurality of word senses with a plurality of graph nodes such that each graph node corresponds to one of the word senses that is associated with a text unit selected from said at least one natural language text;

determining, using the processing unit, at least one connecting relation between at least two of the plurality of word senses;

associating, using the processing unit, said at least one connecting relation with at least one graph edge connecting at least two of the plurality of graph nodes;

constructing, using the processing unit, a graph using only the plurality of graph nodes that are associated with one of the text units selected from said at least one natural language text and said at least one graph edge

ranking, using the processing unit, the plurality of graph nodes by applying a graph-based ranking algorithm to the graph so that the ranking represents the relative importance, within said at least one natural language text, of the word senses associated with the text units; and

selecting, using the processing unit, one word sense for each text unit based on the plurality of rankings.

11. The method of claim 10, wherein selecting the plurality of text units from the natural language text comprises selecting a plurality of open-class words from said at least one natural language text.

12. The method of claim 10, wherein associating at least one word sense with each text unit comprises determining at least one of a synonym word, word phrase, concept, and a definition associated with each text unit.

13. The method of claim 12, wherein determining the at least one synonym word, word phrase, concept, or definition comprises determining the at least one synonym word, word phrase, concept, or definition based upon a lexical knowledge base.

14. The method of claim 10, wherein determining the at least one connecting relation between at least two of the plurality of word senses comprises determining the at least one connecting relation between at least two of the plurality of word senses based upon a semantic, lexical, or syntactic relation.

15. The method of claim 14, wherein determining the at least one connecting relation between at least two of the plurality of word senses based upon the semantic, lexical, or syntactic relation comprises determining the at least one connecting relation between at least two of the plurality of word senses based on hypernymy, hyponomy, meronomy, holonomy, entailment, causality, attribute, and pertainimy, or based on co-occurrence information from a raw or annotated corpus.

16. The method of claim 15, wherein determining the at least one connecting relation between at least two of the plurality of word senses comprises forming a coordinate connecting relation based on a plurality of semantic relations.

17. The method of claim 10, wherein determining the at least one connecting relation between at least two of the plurality of word senses comprises forming a connecting relation between co-occurring text units.

18. The method of claim 10, wherein ranking the plurality of graph nodes comprises:

assigning a plurality of first scores to the plurality of graph nodes;

defining a relationship between a second score of each graph node and second scores of graph nodes coupled each graph node by a graph edge; and

determining a plurality of second scores associated with the plurality of graph nodes by applying an iterative recursive algorithm to the first plurality of scores and iterating until the relationship is satisfied.

19. The method of claim 10, wherein selecting one word sense for each text unit based on the plurality of rankings comprises selecting the word sense having the highest ranking associated with each text unit.

20. The method of claim 10, wherein selecting one word sense for each text unit based on the plurality of rankings comprises selecting one word sense for each text unit based on the plurality of rankings and at least one of a Lesk algorithm and a sense frequency.

21. The method of claim 10, wherein selecting one word sense for each text unit based on the plurality of rankings comprises selecting one word sense for each text unit using at least one of an uninformed and an informed algorithm.

22. A method of keyword extraction from at least one natural language text using a graph, comprising:

selecting, using a processing unit, a plurality of text units from said at least one natural language text;

associating, using the processing unit, the plurality of text units with a plurality of graph nodes so that each graph node is associated with one of the plurality of text units selected from said at least one natural language text;

determining, using the processing unit, at least one connecting relation between at least two of the plurality of text units;

associating, using the processing unit, the at least one connecting relation with at least one graph edge connecting at least two of the plurality of graph nodes;

constructing, using the processing unit, a graph using only the plurality of graph nodes that are associated with one of the text units selected from said at least one natural language text and said at least one graph edge;

ranking, using the processing unit, the plurality of graph nodes by applying a graph-based ranking algorithm to the graph; and

determine, using the processing unit, at least one keyword based on the plurality of text units and the plurality of rankings.

23. The method of claim 22, wherein selecting the plurality of text units from the natural language text comprises determining at least one sequence of at least one lexical unit extracted from the natural language text.

24. The method of claim 22, wherein associating the plurality of text units with the plurality of graph nodes comprises associating the plurality of text units with the plurality of graph nodes based upon at least one syntactic or lexical filter.

25. The method of claim 22, wherein determining at least one connecting relation between at least two of the plurality of text units comprises determining at least one connecting relation based on a co-occurrence relation.

26. The method of claim 22, wherein determining at least one connecting relation based on the co-occurrence relation comprises determining the at least one connecting relation based on a co-occurrence relation controlled by a distance between word occurrences.

27. The method of claim 22, wherein ranking the plurality of graph nodes comprises:

assigning a plurality of first scores to the plurality of graph nodes;

defining a relationship between a second score of each graph node and second scores of graph nodes coupled each graph node by a graph edge; and

determining a second plurality of scores associated with the plurality of graph nodes by applying an iterative recursive algorithm starting with the plurality of first scores and iterating until the relationship is satisfied.

28. The method of claim 22, wherein determining at least one keyword based on the plurality of text units and the plurality of rankings comprises sorting the graph nodes based upon the plurality of rankings.

29. The method of claim 28, wherein determining the at least one keyword comprises selecting at least one keyword based upon the ranking of the graph nodes.

30. The method of claim 29, wherein determining the at least one keyword comprises forming at least one multi-word key word from the selected keywords.

31. The method of claim 30, wherein forming at least one multi-word keyword comprises combining a plurality of adjacent selected keywords.

32. A method of sentence extraction from at least one natural language text using a graph, comprising:

selecting, using the processing unit, a plurality of sentences from said at least one natural language text;

associating, using the processing unit, the plurality of sentences with a plurality of graph nodes so that each graph node is associated with one of the plurality of sentences selected from said at least one natural language text;

determining, using the processing unit, at least one connecting relation between at least two of the plurality of sentences;

associating, using the processing unit, the at least one connecting relation with at least one graph edge connecting at least two of the plurality of graph nodes;

constructing, using the processing unit, a graph using only the plurality of graph nodes that are associated with one of the text units selected from said at least one natural language text and said at least one graph edge;

ranking, using the processing unit, the plurality of graph nodes by applying a graph-based ranking algorithm to the graph; and

selecting, using the processing unit, at least one of the plurality of sentences based on the plurality of text units and the plurality of rankings.

33. The method of claim 32, wherein determining at least one connecting relation between at least two of the plurality of sentences comprises determining at least one connecting relation based upon a similarity relation between the at least two of the plurality of sentences.

34. The method of claim 33, wherein determining at least one connecting relation based upon the similarity relation comprises determining at least one connecting relation as a function of contents overlap between at least two of the plurality of sentences.

35. The method of claim 33, wherein determining at least one connecting relation based upon the similarity relation comprises determining a number of common tokens in the at least two of the plurality of sentences.

36. The method of claim 33, wherein determining at least one connecting relation based upon the similarity relation comprises applying a syntactic or lexical filter to the plurality of sentences.

37. The method of claim 32, wherein associating the at least one connecting relation with at least one graph edge comprises associating a weight with each graph edge.

38. The method of claim 37, wherein associating the weight with each graph edge comprises determining the weight based upon the at least one connecting relation.

39. The method of claim 32, further comprising representing the graph as at least one of an undirected graph, a forward directed graph, and a backward directed graph.

40. The method of claim 32, wherein ranking the plurality of graph nodes comprises:

assigning a plurality of first scores to the plurality of graph nodes;

defining a relationship between a second score of each graph node and second scores of graph nodes coupled each graph node by a graph edge; and

determining a plurality of second scores associated with the plurality of graph nodes by applying an iterative recursive algorithm starting with the plurality of first scores and iterating until the relationship is satisfied.

41. The method of claim 40, wherein ranking the graph nodes comprises sorting the sentences in reverse order based upon the second plurality of scores.

42. The method of claim 41, wherein selecting at least one of the plurality of sentences comprises selecting a selected number of sentences having the highest rankings.

43. A method for graphical visualization of a natural language text, comprising:

selecting, using a processing unit, a plurality of text units from the natural language text;

associating, using the processing unit, the plurality of text units with a plurality of graph nodes so that each graph node is associated with one of the text units selected from the natural language text;

determining, using the processing unit, at least one connecting relation between at least two of the plurality of text units;

associating, using the processing unit, the at least one connecting relation with at least one graph edge connecting at least two of the plurality of graph nodes;

constructing, using the processing unit, a graph using only the plurality of graph nodes that are associated with one of the text units selected from the natural language text and said at least one graph edge;

ranking, using the processing unit, the plurality of graph nodes by applying a graph-based algorithm to the graph; and

providing, using the processing unit, a visual indication for each text unit based on the plurality of rankings.

44. The method of claim 43, wherein providing the visual indication comprises displaying at least one text unit using at least one color.

45. The method of claim 44, wherein displaying the at least one text unit using at least one color comprises displaying the at least one text unit using a plurality of colors representing the plurality of rankings.

46. The method of claim 43, comprising:

determining at least one keyword based on the plurality of text units and the plurality of rankings; and

providing at least one visual indication associated with the at least one keyword.

47. The method of claim 43, comprising:

selecting at least one sentence based on the plurality of text units and the plurality of rankings; and

providing at least one visual indication associated with the at least one sentence.