Data processing: artificial intelligence – Knowledge processing system
Reexamination Certificate
2000-03-31
2004-01-27
Khatri, Anil (Department: 2121)
Data processing: artificial intelligence
Knowledge processing system
C706S046000, C706S047000
Reexamination Certificate
active
06684201
ABSTRACT:
TECHNICAL FIELD
This invention relates to linguistic ambiguity resolution. More particularly, this invention relates to systems and method for training linguistic disambiguators using string-based patterns.
BACKGROUND
Natural language processing systems are computer implemented software systems that intelligently derive meaning and context from natural language text. “Natural languages” are languages that are spoken by humans (e.g., English, French, Japanese). Computers cannot, without assistance, distinguish linguistic characteristics of natural language text. Natural language processing systems are employed in a wide range of products, including spell checkers, grammar checkers, machine translation systems, and speech synthesis programs.
Oftentimes, natural languages contain ambiguities that are difficult to resolve using computer automated techniques. Ambiguities come in many forms. Confusable words (e.g. then/than, its/it's, weather/whether) are one of the biggest sources of grammar errors by users. Possessive/plural types (e.g., kids/kid's) is another source for ambiguity. A third common example is part-of-speech tagging, such as differentiating whether “produce” is a noun or a verb. A fourth example is word sense disambiguation, such as deciding whether a particular instance of the word “crane” is referring to a bird or a machine.
Many natural language processing problems can be viewed as trying to disambiguate a token into one of a small number of possible labels, based upon the string context in which that token appears. For example, a spell checker may try to decide whether the word “then” or “than” is appropriate in the sentence “I am much smarter then/than you are.” A machine translation system may try to determine what the word sense is of the word “line” in the sentence “I am not going to wait in line”, so it can more accurately determine what the proper translation is. A speech synthesis program may try to decide whether the word “produce” is a noun or a verb in the sentence “This grocery store has beautiful produce”, in order to determine the proper pronunciation for the word.
To automatically perform disambiguations, the natural language processing system is provided with linguistic knowledge that it applies to the string context in order to disambiguate. Linguistic knowledge can either be entered manually or learned automatically. Typically, the manual approach has the advantage that people can provide linguistically sophisticated knowledge. Automatic approaches are beneficial in that the linguistic knowledge can be derived empirically from essentially unlimited amounts of data, can be rapidly ported to new domains, languages, or problems, and can be constantly and automatically adapted to a is particular individual or subpopulation.
To date, automatic approaches have been extremely constrained in the types of linguistic information they can learn. For example, conventional systems automatically learn how to disambiguate words/phrases by learning cues based on whether a specific word appears within a pre-specified window of words from a “disambiguation site” (i.e., the place in the text where the ambiguity to be resolved actually occurs), and what combinations of words and word features (such as part of speech) appear in immediate proximity to the disambiguation site. The contextual words and phrases surrounding the disambiguation site are commonly referred to as the “string context” or simply “string”.
To provide a concrete example of a token disambiguation problem, a spell/grammar checker may wish to check whether the words “then” and “than” are confused anywhere in a document. Suppose the sentence is:
I am much bigger then you.
The spell/grammar checker will try to determine whether “then” or “than” is the correct word. It does so by analyzing the string context (e.g., the sentence in which the word appears) and applying its linguistic knowledge to this string context to determine which word is more likely. In this particular example, it may make use of its linguistic knowledge that the word “than” immediately follows a comparative adjective much more often than the word “then”.
There are two primary components of a machine learning approach to the problem of token disambiguation based on a string context: (1) the algorithms used for learning and applying the learned knowledge to perform disambiguation and (2) the specification of features the learner is allowed to explore in training. Over the past decade, there have been many different approaches to (1), but very little progress in (2).
For confusable word set disambiguation, an article by Golding and Schabes, entitled “Combining Trigram-based and Feature-based Methods for Context-Sensitive Spelling Correction,”
Proceedings of the
34
th
Annual Meeting of the Association for Computational Linguistics
, 1996, describes training a naïve Bayes classifier using as features the set of words that appear within +/−3 words of the target word and patterns of up to 2 contiguous words and/or part of speech tags around the target word. In an article by Golding and Roth, entitled “A Winnow-Based Approach to Spelling Correction,”
Machine Learning
, Special issue on Machine Learning and Natural Language Processing, Volume 34, pp. 107-130, 1999, the authors propose using the Winnow machine-learning algorithm with essentially the same features. In an article by Mangu and Brill, entitled “Automatic Rule Acquisition for Spelling Correction,”
Proc. of the Fourteenth International Conference on Machine Learning
, ICML'97, Nashville, Tenn., 1997, the authors describe use of transformation-based learning, again using the same features. In an article by Jones and Martin, entitled, “Contextual Spelling Correction Using Latent Semantic Analysis,” Proceedings of the Fifth Conference on Applied Natural Language Processing, 1997, the authors propose use of latent semantic analysis as the learning algorithm, and features that include the set of words and contiguous word pairs (bigrams) that appear within a window of +/−7 words of the target word.
For word sense disambiguation, an article by Ng, entitled “Exemplar-Based Word Sense Disambiguation: Some Recent Improvements,” Proceedings of the Second Conference on Empirical Methods in Natural Language Processing, 1997, describes systems for word sense disambiguation that employ two different machine learning algorithms, naive Bayes and Nearest-Neighbor. In both systems, the features used were: word before, word after, word two before, word two after, the pair of words before, the pair of words after, and the two surrounding words. In an article by Yarowsky, entitled “One sense per collocation,”
In Proceedings of the ARPA Human Language Technology Workshop
, 1993, the author proposes using a decision list learning algorithm with a very similar set of features.
One attempt at a richer feature set was proposed by Christer Samuellson, Pasi Tapanainen and Atro Voutilainen in “Inducing Constraint Grammars,” published in Grammatical Inference: Learning Syntax from Sentences, Lecture Notes in Artificial Intelligence 1147, Springer (L. Miclet and C. del la Huguera eds), 1996. There they propose a system that can learn barrier rules for part of speech tagging. A barrier rule consists of a pair of symbols X and Y and a set of symbols S, and matches a string if that string contains X and Y, with X preceding Y and no symbols from the set S intervening between X and Y.
Despite these efforts, there remains a need for a method for learning much more expressive disambiguation cues. Such a method should be capable of being applied to virtually any problem involving token disambiguation in a string context, and should offer significant performance gains over current state of the art automatic linguistic knowledge acquisition solutions to these problems.
SUMMARY
A linguistic disambiguation system and method creates a knowledge base by training on patterns in strings that contain ambiguity sites. The system is trained on a training set, such as a properly labeled co
Hirl Joseph P.
Khatri Anil
Lee & Hayes PLLC
Microsoft Corporation
LandOfFree
Linguistic disambiguation system and method using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Linguistic disambiguation system and method using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linguistic disambiguation system and method using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3252699