Method and apparatus for determining a measure of similarity between natural language sentences

• US 7,295,965 B2
• Filed: 06/29/2001
• Issued: 11/13/2007
• Est. Priority Date: 06/29/2001
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Haigh, Karen Z., Kramer, Kevin M.
• Primary Examiner(s): Harper; V. Paul
• Application Number:
  US09/896,846
• Publication Number:
  US 20030004716A1
• Time in Patent Office: 2,328 Days
• Field of Search: 704/227, 704/8, 704/9, 704/7, 704/238, 707/2, 707/3, 707/5, 707/6
• US Class Current: 704/9
• CPC Class Codes: G10L 15/10 using distance or distortion measures between unknown speech and reference templates
• CPC Class Codes: G10L 15/12 using dynamic programming techniques, e.g. dynamic time warping [DTW]
• CPC Class Codes: G10L 15/18 using natural language modelling
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

Systems and methods for classifying natural language (NL) sentences using a combination of NL algorithms or techniques is disclosed. Each NL algorithm or technique may identify a different similarity trait between two or more sentences, and each may help compare the meaning of the sentences. By combining the various similarity factors, preferably by various weighting factors, a distance metric can be computed. The distance metric provides a measure of the overall similarity between sentences, and can be used to assign a sentences to an appropriate sentence category.

Claims

1. A method for categorizing a sentence into one of two or more sentence categories, wherein each sentence category has at least one associated categorized sentence, and wherein the sentence and each categorized sentence has a number of words and/or phrases, the method comprising:

calculating one or more similarity factor between the sentence and at least one categorized sentence in each of the two or more sentence categories based on selections of words in the sentence and the least one categorized sentence in each of the two or more sentence categories;

generating a distance metric for each of the sentence categories using one or more of the similarity factors, the distance metric representing a measure of the similarity between the sentence and the least one categorized sentence in each of the two or more sentence categories;

categorizing the sentence into one of the sentence categories based on the distance metrics; and

providing a result that at least in part reflects the categorization of the sentence to a user and/or computer.

2. A method according to claim 1, further comprising the step of processing the sentence and the at least one categorized sentence with a natural language algorithm to identify and assign the words in each sentence to one or more natural language categories.

3. A method according to claim 1, wherein one or more similarity factors provide a measure of similarity according to natural language information.

4. A method according to claim 1, wherein one or more similarity factors provide a measure of similarity according to statistical methods.

5. A method according to claim 1, wherein one or more similarity factors provide a measure of similarity according to domain-specific information.

6. A method according to claim 1, wherein one or more similarity factors provide a measure of similarity according to other relevant information.

7. A method according to claim 1, wherein one or more similarity factors provide a measure of similarity according to a combination of any of natural language, statistical, or other technique.

8. A method according to claim 1, where the one or more similarity factors are combined to generate an overall estimate of the similarity of the sentences.

9. A method according to claim 1, wherein the one or more similarity factors result from one or more of a string overlap function, a keyword match function, a phrase match function, or a model match function.

10. A method according to claim 9, wherein the string overlap function returns how many words in the sentence match a word in the at least one categorized sentence, as a percentage of the number of words in the longest of the sentence and the at least one categorized sentence.

11. A method according to claim 9, wherein the keyword match function returns how many words in the sentence match a word in the at least one categorized sentence with both words having a common word type, as a percentage of the maximum number of keywords in the sentence and the at least one categorized sentence.

12. A method according to claim 11, wherein the common word type is a natural language category, including a noun, a verb, an adverb, a preposition, an object, a direct object, and a subject.

13. A method according to claim 9, wherein the phrase match function returns a sentence similarity value, wherein the sentence similarity value is related to the similarity of one or more selected phrases that exist in both the sentence and the at least one categorized sentences, with both phrases having a common phrase type.

14. A method according to claim 13, wherein the phrase type is one of a noun phrase, a verb phrase, and a prepositional phrase.

15. A method according to claim 9, wherein the model match function includes at least one set of model words, each model word having a corresponding correlation factor that correlates the model word to a category or domain.

16. A method according to claim 15, wherein the model match function returns a sentence similarity value, wherein the sentence similarity value is increased by the correlation factor of a model word when both the sentence and the at least one categorized sentence include the model word, and is decreased by the correlation factor of a model word when only one of the sentence and the at least one categorized sentences include the model word.

17. A method according to claim 1, further comprising the step of identifying words related to those in the sentences, and using the related words to complete the similarity factor.

18. A method according to claim 11, wherein the related words are identified using a domain thesaurus.

19. A method according to claim 17, wherein the related words are identified by removing a suffix or a prefix from selected words in the sentence and the at least one categorized sentences.

20. A method according to claim 1, further comprising the step of extracting one or more named entities from the sentence and the at least one categorized sentences to allow complex groups of nouns to be treated as a single object.

21. A method according to claim 1, further comprising the step of excluding from the comparing step selected words that are identified in a predefined stop list.

22. A method for determining a distance metric that indicates the similarity of a first sentence and a second sentence, wherein the first sentence and the second sentence are extracted from one or more documents, the method comprising the steps of:

comparing the first sentence and the second sentence using a first comparing function, the first comparing function including a string overlap function and providing a first similarity indicator, the string overlap function returning how many words in the first sentence match a word in the second sentence, as a percentage of the number of words of the longest of the first sentence and second sentence;

comparing the first sentence and the second sentence using a second comparing function, the second comparing function providing a second similarity indicator;

calculating the distance metric by combining the first similarity indicator and the second similarity indicator; and

providing a result that at least in part reflects the distance metric to a user and/or computer.

23. A method according to claim 22, wherein a word in the first sentence is determined to match a word in the second sentence if the word in the first sentence and the word in the second sentence each exceed a minimum number of characters, and the word in the first sentence shares a predetermined minimum number of characters with the word in the second sentence.

24. A method according to claim 23, wherein a word in the first sentence is determined to match a word in the second sentence if the word in the first sentence and the word in the second sentence each have a minimum of four characters, and the word in the first sentence shares at least 80 percent of the characters with the word in the second sentence.

25. A method for determining a distance metric that indicates the similarity of a first sentence and a second sentence, wherein the first sentence and the second sentence are extracted from one or more documents, the method comprising the steps of:

comparing the first sentence and the second sentence using a first comparing function, the first comparing function including a keyword match function and providing a first similarity indicator, wherein the keyword match function returns how many words in the first sentence match a word in the second sentence with both words having a common word type, as a percentage of the maximum number of keywords in the first sentence and second sentence;

comparing the first sentence and the second sentence using a second comparing function, the second comparing function providing a second similarity indicator;

calculating the distance metric by combining the first similarity indicator and the second similarity indicator; and

providing a result that at least in part reflects the distance metric to a user and/or computer.

26. A method according to claim 25, wherein a word in the first sentence matches a word in the second sentence if the word in the first sentence and the word in the second sentence each exceed a minimum number of characters, and the word in the first sentence shares a predetermined minimum number of characters with the word in the second sentence.

27. A method according to claim 26, wherein the word type of each word is assigned by a part-of-speech tagger function.

28. A method according to claim 25, wherein the keyword match function only attempts to match those words that have a selected word type.

29. A method for determining a distance metric that indicates the similarity of a first sentence and a second sentence, wherein the first sentence and the second sentence are extracted from one or more documents, the method comprising the steps of:

comparing the first sentence and the second sentence using a first comparing function, the first comparing function including a phrase match function and providing a first similarity indicator, wherein the phrase match function determines a phrase similarity value for each phrase pair by identifying how many words in a first phrase match a word in a second phrase, as a percentage of the maximum number of words in the first phrase and second phrase;

comparing the first sentence and the second sentence using a second comparing function, the second comparing function providing a second similarity indicator;

calculating the distance metric by combining the first similarity indicator and the second similarity indicator; and

providing a result that at least in part reflects the distance metric to a user and/or computer.

30. A method according to claim 29, wherein a weighting factor is applied to each phrase similarity value, depending on the phrase type, to compute the phrase match similarity factor.

31. A method according to claim 29, wherein a word in the first phrase matches a word in the second phrase when the word in the first phrase and the word in the second phrase each exceed a minimum number of characters and share a predetermined minimum number of characters.

32. A method for categorizing sentences in a document, comprising:

processing a number of selected sentences, said processing step assigning each of the number of selected sentences to one or more predefined categories without using a user entered query, the particulars of the assignment of the number of selected sentences being dependent on a number of operating parameters;

displaying a correspondence between the one or more predefined categories and the selected sentences;

allowing a user to change the assigned category for selected sentences;

updating one or more of the operating parameters to reflect the change in the assigned categories; and

repeating the processing, displaying, allowing and updating steps until a desired accuracy level is achieved.

33. A method according to claim 32, further comprising the step of processing all sentences in the document once the repeating step is completed.

34. A method for providing a measure of similarity between a first sentence and a second sentence, each sentence having a number of words, the method comprising:

comparing one or more words of the first sentence with one or more words of the second sentence, the comparing step returning how many words in the first sentence match a word in the second sentence, as a percentage of the number of words in the longest of the first sentence and second sentence;

providing a result that is related the comparing step to a user and/or computer.

35. A method according to claim 34, wherein a word in the first sentence is determined to match a word in the second sentence if the word in the first sentence and the word in the second sentence each exceed a minimum number of characters, and the word in the first sentence shares a predetermined minimum number of characters with the word in the second sentence.

36. A method for providing a measure of similarity between a first phrase and a second phrase, each phrase having a number of words, the method comprising:

comparing one or more words of the first phrase with one or more words of the second phrase, the comparing step returning how many words in the first phrase match a word in the second phrase, as a percentage of the number of words in the longest of the first phrase and second phrase; and

providing a result that is related the comparing step to a user and/or computer.

37. A method according to claim 36, wherein a word in the first phrase matches a word in the second phrase when the word in the first phrase and the word in the second phrase each exceed a minimum number of characters and share a predetermined minimum number of characters.

38. A method of comparing a first sentence and a second sentence, the method comprising the steps of:

comparing a word in the first sentence with a word in the second sentence; and

determining that the word in the first sentence matches the word in the second sentence if the word in the first sentence and the word in the second sentence each have a minimum of four characters, and the word in the first sentence shares at least 80 percent of the characters with the word in the second sentence; and

providing a result to a user and/or computer.