System and method for matching a textual input to a lexical knowledge based and for utilizing results of that match

• US 20050065777A1
• Filed: 10/29/2004
• Published: 03/24/2005
• Est. Priority Date: 03/07/1997
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Vanderwende, Lucretia H., Barnett, Michael, Menezes, Arul A., Dolan, William B., Richardson, Stephen D.
• Granted Patent: US 7,013,264 B2
• Time in Patent Office: Days
• US Class Current: 704/10
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

The present invention can be used in a natural language processing system to determine a relationship (such as similarity in meaning) between two textual segments. The relationship can be identified or determined based on logical graphs generated from the textual segments. A relationship between first and second logical graphs is determined. This is accomplished regardless of whether there is an exact match between the first and second logical graphs. In one embodiment, the first graph represents an input textual discourse unit. The second graph, in one embodiment, represents information in a lexical knowledge base (LKB). The input graph can be matched against the second graph, if they have similar meaning, even if the two differ lexically or structurally.

Claims

1. A computer readable medium storing instructions which when executed by a computer, cause the computer to perform a method of determining a relationship between a first textual segment and textual information in a lexical knowledge base (LKB) having a plurality of interconnected logical graphs, each representative of a textual segment in a corpus, the method comprising:

obtaining in an input logical form based on the first textual segment;

matching the input logical form against the logical graphs in the LKB, identifying logical graphs as matching logical graphs even if the matching logical graphs differ from the input logical form lexically or structurally; and

providing an output based on the matching logical graphs.

2. The computer readable medium of claim 1 wherein

obtaining an input logical form comprises:

obtaining a set of logical relations indicative of the first textual segment, each logical relation including at least first and second words connected by a relation.

3. The computer readable medium of claim 2 wherein matching, comprises:

selecting a logical relation in the input logical form;

identifying a set of paths in the LKB which connect the first and second words of the selected logical relation;

determining whether each word in the identified paths, other than the first and second words in the logical relation, is similar to the first or second word in the logical relation and, if so, identifying the word in the path as a similar word (simword); and

identifying additional matching logical graphs based on the simwords identified.

4. The computer readable medium of claim 3 wherein the method further comprises:

repeating the steps of selecting a logical relation, identifying a set of paths, determining whether each word in the identified paths are similar to the first or second word in the selected logical relation, and identifying additional matching logical graphs, for each logical relation in the input logical form.

5. The computer readable medium of claim 3 wherein matching further comprises:

selecting one or more of a plurality of different combinations of the matching logical graphs and additional logical graphs as selected matching logical graphs, and wherein providing an output comprises providing the output based on the selected matching logical graphs.

6. The computer readable medium of claim 5 wherein selecting comprises:

weighting each of the plurality of different combinations with a weighting value; and

selecting the selected matching logical graphs based on the weighting values.

7. The computer readable medium of claim 6 wherein the LKB includes translation information indicative of a translation from a first language to a second language and wherein providing an output comprises:

providing the translation information associated with the selected matching logical graph.

8. The computer readable medium of claim 6 wherein the LKB is based on a first language, and wherein providing an output comprises:

providing a link to a logical graph in a second LKB which is based on a second language different from the first language.

9. The computer readable medium of claim 8 wherein providing an output comprises:

providing a textual output corresponding to a textual segment used in generating the logical graph pointed to in the second LKB.

10. The computer readable medium of claim 8 wherein providing an output comprises:

providing a pointer to a textual output corresponding to a textual segment used in generating the logical graph pointed to in the second LKB.

11. The computer readable medium of claim 6 wherein providing an output comprises:

providing a pointer to a textual segment which was used in generating the selected matching logical graph.

12. The computer readable medium of claim 6 wherein providing an output comprises:

providing a textual segment which was used in generating the selected matching logical graph.

13. The computer readable medium of claim 6 wherein providing an output comprises:

providing an input to an application program.

14. The computer readable medium of claim 13 wherein the application program includes one or more frames to be filled and wherein providing an input to an application program comprises:

providing a textual input to fill a frame in the application program.

15. The computer readable medium of claim 13 wherein the selected matching logical graph contains links to modules causing frames in the application program to be filled, and wherein providing an output comprises:

providing the links, along with the words in the input logical form, to fill the application program frames with the words.

16. The computer readable medium of claim 5 wherein the method further comprises:

receiving an nth textual segment;

obtaining an nth input logical form based on the nth textual segment; and

preferentially matching the nth logical form against logical graphs in a portion of the LKB proximate to the selected matching logical graph(s).

17. The computer readable medium of claim 16 wherein selecting one of a plurality of different combinations comprises:

weighting each of the plurality of different combinations with a weighting value; and

selecting the selected matching logical graph based on the weighting values.

18. The computer readable medium of claim 17 wherein preferentially matching comprises:

increasing the weighting values associated with the selected matching logical graph.

19. The computer readable medium of claim 1 wherein the method further comprises:

prior to matching, identifying a starting point in the input logical form; and

if the starting point is not a root of the input logical form, reconfiguring the input logical form such that the starting point comprises a root of the input logical form.

20. The computer readable medium of claim 19 wherein matching comprises:

identifying words in the LKB which are similar to the root (simwords); and

matching the input logical form against the root and simwords in the LKB.

21. The computer readable medium of claim 20 wherein identifying simwords comprises:

accessing a thesaurus.

22. The computer readable medium of claim 20 wherein identifying simwords further comprises:

scoring simwords based on a degree of similarity.

23. The computer readable medium of claim 20 wherein identifying simwords comprises:

restricting words identified as simwords based on part of speech or based on whether the paths used to identify the simwords came from logical graphs related to a context surrounding the input.

24. The computer readable medium of claim 19 wherein matching further comprises:

matching the words and relations in the input logical form against logical graphs in the LKB, to obtain one or more matching logical graphs.

25. The computer readable medium of claim 24 wherein matching further comprises:

identifying a candidate set of logical graphs in the LKB having, as a root, the root word of the input logical form, or a simword.

26. The computer readable medium of claim 25 wherein matching further comprises:

ordering the candidate set of logical graphs based on whether each candidate in the set of logical graphs contains words in the input logical form or simwords and the number of simwords contained; and

matching against the candidate set in order.

27. The computer readable medium of claim 25 wherein matching further comprises:

selecting a logical graph in the candidate set;

comparing words on nodes and relation types in the input logical form to words on nodes and relation types in the selected one of the logical graphs in the candidate set; and

repeating the steps of selecting and comparing a plurality of times.

28. The computer readable medium of claim 27 wherein comparing relation types comprises:

identifying relation types in the selected logical graph in the candidate set which are identical to relation types in the input logical form; and

assigning a highest score to the identical match of relation types.

29. The computer readable medium of claim 27 wherein comparing relation types comprises:

identifying relation types in the selected logical graph in the candidate set which are paraphrases of relation types in the input logical form; and

assigning a score to the match of relation types that is lower than a score for an identical match of relation types.

30. The computer readable medium of claim 27 wherein comparing relation types comprises:

matching patterns of subgraphs in the selected logical graph in the candidate set with patterns of subgraphs in the input logical form.

31. The computer readable medium of claim 27 wherein comparing words on nodes comprises:

identifying words on nodes in the selected logical graph in the candidate set which are identical to the words on nodes in the logical form; and

assigning a highest score to the identical match of words.

32. The computer readable medium of claim 27 wherein comparing words on nodes comprises:

identifying words on nodes in either the input logical form or the selected logical graph which are subcomponents of the other and thus partially match the other; and

assigning a score to the partial match of words.

33. The computer readable medium of claim 27 wherein comparing words on nodes comprises:

matching “

who”

with any word representing a human or animate entity; and

assigning a score to the match.

34. The computer readable medium of claim 27 wherein comparing words on nodes comprises:

matching “

when”

with any word representing a time or date entity; and

assigning a score to the match.

35. The computer readable medium of claim 27 wherein comparing words on nodes comprises:

matching “

where”

with any word representing a location entity; and

assigning a score to the match.

36. The computer readable medium of claim 27 wherein comparing words on nodes comprises:

matching question words with words having a corresponding feature; and

assigning a score to the match.

37. The computer readable medium of claim 27 wherein comparing words on nodes comprises:

matching personal pronouns with any personal pronouns or words referring to a human or animate entity, or having a corresponding feature; and

assigning a score to the match.

38. The computer readable medium of claim 27 wherein comparing words on nodes comprises:

matching two similar words; and

assigning a score to the match.

39. The computer readable medium of claim 27 wherein matching further comprises:

assigning a score to the comparison of the words on nodes and to the comparison of relation types; and

obtaining an overall score for the match of the input logical form and the selected logical graph in the candidate set by combining the scores assigned to the comparisons of words and relation types.

40. The computer readable medium of claim 39 wherein the method further comprises:

maintaining an ordered list of matches, arranged in order of the overall scores for the matches.

41. The computer readable medium of claim 40 wherein providing an output comprises:

providing the output as a copy of the logical graphs in the LKB having an overall score above a threshold score.

42. The computer readable medium of claim 24 wherein the LKB includes translation information indicative of a translation from a first language to a second language and wherein providing an output comprises:

providing the translation information associated with at least one of the matching logical graphs.

43. The computer readable medium of claim 24 wherein the LKB is based on a first language, and wherein providing an output comprises:

providing a link to a logical graph in a second LKB which is based on a second language different from the first language.

44. The computer readable medium of claim 43 wherein providing an output comprises:

providing a textual output corresponding to a textual segment used in generating the logical graph pointed to in the second LKB.

45. The computer readable medium of claim 43 wherein providing an output comprises:

providing a pointer to a textual output corresponding to a textual segment used in generating the logical graph pointed to in the second LKB.

46. The computer readable medium of claim 24 wherein providing an output comprises:

providing a pointer to a textual segment which was used in generating at least one of the matching logical graphs.

47. The computer readable medium of claim 24 wherein providing an output comprises:

providing a textual segment which was used in generating at least one of the matching logical graphs.

48. The computer readable medium of claim 24 wherein providing an output comprises:

providing an input to an application program.

49. The computer readable medium of claim 48 wherein the application program includes one or more frames to be filled and wherein providing an input to an application program comprises:

providing a textual input to fill a frame in the application program.

50. The computer readable medium of claim 48 wherein the selected matching logical graph contains links to modules causing the frames to be filled, and wherein providing an output comprises:

providing the links, along with the words in the input logical form, to fill the application program frames with the words.

51. The computer readable medium of claim 24 wherein the method further comprises:

receiving an nth textual segment;

obtaining an nth input logical form based on the nth textual segment; and

preferentially matching the nth input logical form against logical graphs in a portion of the LKB proximate to the one or more matching logical graphs.

52. The computer readable medium of claim 51 wherein preferentially matching comprises:

weighting each of the plurality of different combinations with a weighting value; and

selecting the one or more matching logical graphs based on the weighting values.

53. The computer readable medium of claim 52 wherein preferentially matching comprises:

increasing the weighting values associated with the one or more matching logical graphs.