Word disambiguation apparatus and methods

• US 5,541,836 A
• Filed: 12/30/1991
• Issued: 07/30/1996
• Est. Priority Date: 12/30/1991
• Status: Expired due to Term

• Current Assignee: AT&T IPM Corp. (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Yarowsky, David E., Gale, William A., Church, Kenneth W.
• Primary Examiner(s): McElheny, Jr., Donald E.
• Application Number:
  US07/814,850
• Time in Patent Office: 1,674 Days
• Field of Search: 364/419, 364/419.07, 364/419.08, 364/419.12, 364/419.13
• US Class Current: 704/7
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models
• CPC Class Codes: G06F 40/45 Example-based machine translation; Alignment

Abstract

Apparatus and methods for determining whether a word/sense pair is proper for a context. Wide contexts (100 words) are employed for both training and testing, and testing is done by adding the weights of vocabulary words from the context. The weights are determined by Bayesian techniques which interpolate between the probability of occurrence of a vocabulary word in a conditional sample of the training text and the probability of its occurrence in the entire training text. A further improvement in testing takes advantage of the fact that a word is generally used in only a single sense in a single discourse. Also disclosed are automated training techniques including training on bilingual bodies of text and training using categories from Roget'"'"'s Thesaurus.

Claims

1. A method performed in a computer system of determining whether a sense for a word is lexically appropriate to a given position in a text accessible to the computer system, the method comprising the steps of:

using the computer system to obtain a sequence of words in the text which includes the given position and is predominantly substantially longer than the average length of the sentences of the text and to store the sequence; and

using the computer system to make a word sense determination of whether a sense specified in a word/sense pair for the word which is stored in the computer system is a sense which is lexically appropriate to the given position by automatically analyzing the sequence.

3. The method set forth in claim 1 wherein:

the step of using the computer system to obtain a sequence of words obtains a sequence whose length is approximately 100 words.

4. The method set forth in claim 1 further including the steps performed in the computer system of of:

determining whether the word sense determination indicates beyond a predetermined threshold whether the sense specified in the word sense pair is lexically appropriate to the given position; and

if the word sense determination does not so indicate, making a final determination of the sense of the word in the word/sense pair by comparing the result of the word sense determination with the result of another word sense determination of a sense of the word which is lexically appropriate at another position in the text.

5. The method set forth in claim 1 wherein:

in the step of using the computer system to make a word sense determination, the sequence is automatically analyzed by employing a Bayesian discrimination technique involving the words in the sequence and the sense of the word-sense pair to determine the probability that the sense of the word/sense pair is lexically appropriate for the given position.

6. The method set forth in claim 1 wherein:

there is a plurality of the word/sense pairs;

the step of using the computer system to make a word sense determination is performed for each of the word/sense pairs; and

the method further includes the step of selecting the word/sense pair whose sense is lexically most appropriate for the given position.

7. The method set forth in claim 6 wherein:

the step of selecting the word/sense pair includes the step of comparing the result of the word sense determination with the result of another word sense determination at another position in the text.

8. The method set forth in claim 1 wherein the step of using the computer system to make the word sense determination includes the steps of:

for words in the sequence, obtaining weights from a table stored in the computer system which indicates the weight of certain words for determining whether the sense specified in the word/sense pair is lexically appropriate to the given position and

summing the weights to determine a likelihood that the sense specified in the word/sense pair is lexically appropriate to the given position.

9. The method set forth in claim 8 wherein:

there is a plurality of the word/sense pairs;

the steps of obtaining the weights and summing the weights are performed for each word/sense pair; and

the method includes the further step of

selecting the word/sense pair having the summed weights which indicate the greatest likelihood that the sense of the word/sense pair is lexically appropriate to the given position.

10. The method set forth in claim 9 wherein the step of selecting the word/sense pair includes the step of:

comparing the sense of the selected word/sense pair with the result of another word sense determination of a sense for the word in the word/sense pair which is lexically most appropriate at another position.

11. The method of any one of claims 1 or 3 through 10 wherein

there is an occurrence of the word specified in the word/sense pair at the given position.

2. A method used in a computer system of determining a probability that a sense for a word is lexically appropriate to a given position in a text accessible to the computer system, the method comprising the steps of:

using the computer system to obtain a sequence of words in the text which includes the given position and to store the sequence; and

using the computer system to make a probability determination of the probability that the sense specified in a word/sense pair for the word is a sense which is lexically appropriate to the given position, the word-sense pair being stored in the computer system and the probability determination being made by employing a Bayesian discrimination technique involving the words in the sequence and a sense specified in the word/sense pair.

12. The method set forth in claim 2 wherein:

there is a plurality of the word/sense pairs;

the step of using the computer system to make a probability determination is performed for each of the word/sense pairs; and

the method includes the additional step performed in the computer system of selecting the word/sense pair whose sense is lexically most appropriate to the given position.

13. The method set forth in claim 12 wherein the step of selecting the word/sense pair includes the step of:

comparing the sense of the selected word/sense pair with the sense of the word/sense pair resulting from another probability determination of the lexically most appropriate sense at another position in the text.

14. The method set forth in claim 2 wherein the step of using the computer system to make a probability determination includes the steps of:

for words in the sequence, obtaining weights from a table stored in the computer system which indicates the weights of certain words for determining whether the word/sense pair has a sense which is lexically appropriate, the weights being computed using the Bayesian discrimination technique, and

summing the weights to determine a likelihood that the word/sense pair is lexically appropriate to the given position in the text.

15. The method set forth in claim 14 wherein:

there is plurality of the word/sense pairs;

the steps of obtaining the weights and summing the weights are performed for each word/sense pair; and

the method includes the further step performed in the computer system of

selecting the word/sense pair having the summed weights which indicate the greatest likelihood that the word/sense pair is lexically appropriate for the given position in the text.

16. The method set forth in claim 15 wherein the step of selecting the word/sense pair includes the step of:

comparing the sense of the selected word/sense pair with the sense of the word/sense pair resulting from another probability determination of the lexically most appropriate sense at another position in the text.

17. The method set forth in claim 2 further including the steps performed in the computer system of:

determining whether the step of using the computer system to make a probability determination produces a probability which is above a predetermined threshold that the word/sense pair is lexically appropriate to the given position in the text; and

if the indication does not exceed the threshold, making a final determination of the suitable sense by comparing the sense of the word/sense pair with the sense of the word/sense pair resulting from another probability determination of the lexically appropriate sense at another position in the text.

18. The method of any one of claims 2 or 12 through 17 wherein:

there is an occurence of the word specified in the word/sense pair at the given position.

19. A method of using a computer system to determine whether a sense for a word is lexically appropriate to a given position in a text accessible to the computer system, the method comprising the steps of:

using the computer system to make a first determination of whether a sense specified in a word/sense pair for the word which is stored in the computer system is a sense which is lexically appropriate to the given position in the text; and

using the computer system to make a final determination that the sense in the word/sense pair is lexically appropriate to the given position by determining that the sense in the word sense pair is lexically appropriate to another position in the text.

20. The method set forth in claim 19 wherein the method further includes the step performed in the computer system of:

determining whether the first determination indicates beyond a predetermined threshold whether the sense specified in the word sense pair is lexically appropriate to the given position; and

the step of making a final determination is performed when the indication produced by the first determination does not so indicate.

21. The method set forth in any one of claims 19 or 20 wherein:

there is an occurrence of the word specified in the word/sense pair at the given position.

22. Apparatus for determining whether a sense for a word is lexically appropriate to a given position in a text, the apparatus comprising:

means for obtaining a sequence of words in the text which includes the given position and is predominantly substantially longer than the average length of the sentences of the text; and

means for analyzing the sequence to determine whether a sense specified in a word/sense pair for the word is a sense which is lexically appropriate to the given position.

23. The apparatus set forth in claim 22 wherein:

the means for obtaining a sequence obtains a sequence whose length is approximately 100 words.

24. The apparatus set forth in claim 22 wherein:

the means for analyzing the sequence employs a Bayesian discrimination technique involving the words in the sequence and the sense of the word-sense pair to determine a probability that the sense specified in the word/sense pair is a sense which is lexically appropriate to given position.

25. The apparatus set forth in claim 22 wherein:

the means for analyzing the sequence further includes

a table which indicates the weights of certain words in the text for determining whether the sense specified in the word/sense pair is lexically appropriate to the given position and

the means for analyzing the sequence analyzes the sequence by obtaining weights of words in the sequence from the table and summing the weights of those words to determine a likelihood that the sense specified in the word/sense pair is lexically appropriate to the given position.

26. The apparatus set forth in claim 25 wherein:

the weight, wt of each of the certain words is determined by the equation ##EQU10## where π

is the condition probability of the word, a is the frequency of the word in a conditional sample, and E is the expectation of π

given a.

27. The apparatus set forth in any one of claims 22 through 26 wherein:

there is an occurrence of the word specified in the word/sense pair at the given position.

28. A method of using a computer to make a probability table for use in apparatus for determining whether a sense for a word is lexically appropriate to a given position in a text, the method of making the table comprising the steps of:

using the computer system to make and store a conditional sample of a text corpus accessible to the computer system, the conditional sample including contexts from the text corpus which are semantically related to the sense specified in a given word/sense pair;

using the computer system to determine for each word which occurs in the conditional sample a weight of that word in the conditional sample with regard to the probability that the word of the given word/sense pair has the sense specified in the given word/sense pair, the determination of the weight being done using a Bayesian technique; and

storing a table entry in the computer system which includes the weight of the word for each of the occurring words which has more than a given weight.

29. The method set forth in claim 28 wherein:

the step of making a conditional sample is done using contexts which are predominantly substantially longer than the average length of the sentences in the text corpus.

30. The method set forth in claim 29 wherein:

the step of making a conditional sample is done using contexts whose lengths are approximately 100 words.

31. The method set forth in claim 28 wherein:

in the step of determining the weight of each word, the weight, wt for each word which occurs in the conditional sample is determined by the equation ##EQU11## where π

is the conditional probability of the word, a is the frequency of the word in the conditional sample, and E is the expectation of π

given a.

32. The method set forth in claim 28 wherein:

there exists a translation into another language of the text corpus from which the conditional sample is made; and

in the step of making a conditional sample, a determination that the word of the given word/sense pair is used in the sense specified in the word/sense pair is made with reference to the corresponding word in the translation.

33. The method set forth in claim 28 wherein:

there exists a list of categorized words which belong to the same semantic category as the given word/sense pair; and

in the step of making a conditional sample, the contexts contain words from the list.

34. The method set forth in claim 33 wherein:

in the step of determining the weight of each word, the weight, wt for each word which occurs in the conditional sample is determined by the equation ##EQU12## where π

is the conditional probability of the word, a is a value for the frequency of the word in the conditional sample, and E is the expectation of π

given a.

35. The method set forth in claim 34 wherein:

in the step of determining the weight of each word, a is derived by determining for each word from the list which is contained in a context the number of times k the word from the list appears in the corpus and letting all words in the context of such a word contribute a weight of 1/k to a.

36. A probability table for use in apparatus for determining whether a sense for a word is lexically appropriate to a given position in a text, the probability table being made by a method comprising the steps of:

making a conditional sample of the text corpus which includes contexts which are semantically related to a sense specified in a given word/sense pair;

employing a Bayesian technique to determine for each word which occurs in the conditional sample a weight of that word in the conditional sample with regard to the probability that the word of the given word/sense pair has the sense specified in the given word/sense pair; and

making a table entry including the weight of the word for each of the occurring words which has more than a given weight.

37. The probability table set forth in claim 36, wherein:

in the step of employing the Bayesian technique, the weight, wt for each word which occurs in the condition sample is determined by the equation ##EQU13## where π

is the conditional probability of the word, a is the frequency of the word in the conditional sample, and E is the expectation of π

given a.