Adjusting a hidden Markov model tagger for sentence fragments

• US 5,822,731 A
• Filed: 09/15/1995
• Issued: 10/13/1998
• Est. Priority Date: 09/15/1995
• Status: Expired due to Fees

• Current Assignee: BTG International Inc. (Boston Scientific Corporation)
• Original Assignee: Infonautics Corporation (Tucows Incorporated)
• Inventors: Schultz, John Michael
• Primary Examiner(s): Dorvil, Richemond
• Application Number:
  US08/528,884
• Time in Patent Office: 1,124 Days
• Field of Search: 395/2.65, 395/601, 395/603, 395/604, 395/605, 704/256, 704/254, 704/251, 704/239, 704/240, 704/200, 707/3, 707/4, 707/5
• US Class Current: 704/270.1
• CPC Class Codes: G06F 16/90332 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/907 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 40/216 using statistical methods

Abstract

A system for parsing information representative of a sequence of words having parts of speech. The sequence of words forms a sentence or sentence fragment. A hidden Markov model is provided for determining the most likely part of speech of a selected word of the sequence of words. The hidden Markov model has an initial transition matrix and a subsequent transition matrix for storing probabilities of occurrence of the parts of speech. The initial transition matrix of the hidden Markov model is removed to provide a modified hidden Markov model. The modified hidden Markov model is applied to the sequence of words to determine the most likely part of speech of a selected word within a sentence fragment with increased accuracy.

Claims

1. In a system for parsing information representative of a sequence of words having parts of speech, said sequence of words including at least one sentence fragment, a method for determining a part of speech of a word of said sequence of words, comprising the steps of:

providing a hidden Markov model for determining the most likely part of speech of a selected word of said sequence of words, said hidden Markov model having an initial transition matrix and a subsequent transition matrix for storing probabilities of occurrence of said parts of speech, wherein said probabilities of occurrence within said initial transition matrix of said hidden Markov model are equal to each other; and

applying said hidden Markov model to said sequence of words to determine said most likely part of speech of said selected word within said sentence fragment with increased accuracy.

2. The method for determining a part of speech of claim 1, wherein said initial transition matrix includes n probabilities of occurrence of n differing parts of speech, further comprising the step of making each probability of occurrence in said initial matrix equal to l/n.

3. The method for determining a part of speech of claim 1, wherein said sequence of words is a query for searching a database of an information retrieval system, further comprising the steps of:

providing a semantic network for determining an expansion word corresponding to a query word of said sequence of words for expanding said searching of said database; and

applying said expansion word to said database to expand said search of said database in accordance with said determined most likely part of speech of said selected word.

4. The method for determining a part of speech of claim 3, wherein said expansion word has a part of speech further comprising the step of applying said expansion word to said database if said part of speech of said expansion word is the same as said determined most likely part of speech of said selected word.

5. The method of determining a part of speech of claim 1, further comprising the steps of:

receiving first and second input words of said sequence of words;

determining a first part of speech of said first input word to provide a first determined part of speech; and

applying said hidden Markov model to determine the most likely part of speech of said second input word in accordance with said first determined part of speech.

6. The method of determining a part of speech of claim 5, wherein said first and second input words are adjacent words within said sequence of words.

7. The method for determining a part of speech of claim 1, wherein said selected word has relevance further comprising the step of increasing said relevance of said selected word when said most determined likely part of speech is a proper noun.

8. The method for determining a part of speech of claim 1, further comprising the step of determining whether a selected word is a slow word and decreasing the relevance of said selected word in accordance with said determining step.

9. A system for parsing information representative of a sequence of words having parts of speech, said sequence of words including at least one sentence fragment, said system having a probability system for determining a part of speech of a word of said sequence of words, comprising:

a hidden Markov model for determining the most likely part of speech of a selected word of said sequence of words, said hidden Markov model having an initial transition matrix and a subsequent transition matrix for storing probabilities of occurrence of said parts of speech;

said probabilities of occurrence of said initial transition matrix of said hidden Markov model being equal to each other; and

a part of speech tagger for applying said hidden Markov model to said sequence of words to determine said most likely part of speech of said selected word within said sentence fragment with increased accuracy.

10. The system for determining a part of speech of claim 9, wherein said initial transition matrix includes n probabilities of occurrence of n differing parts of speech and each probability of occurrence in said initial transition matrix equal to l/n.

11. The system for determining a part of speech of claim 9, wherein said sequence of words is a first query for searching a database of an information retrieval system containing words, further comprising:

a semantic network for determining an expansion word corresponding to a query word of said sequence of words for expanding said searching of said database; and

a second search query including said words of said first query and said expansion word in accordance with said determined most likely part of speech of said selected word.

12. The system for determining apart of speech of claim 11, wherein said expansion word has a part of speech and said expansion word is included in said second query and applied to said database if said part of speech of said expansion word is the same as said determined most likely part of speech of said selected word.

13. The system of determining a part of speech of claim 9, further comprising:

first and second input words selected from said sequence of words;

a first determined part of speech of said first input word; and

means for applying said hidden Markov model to determine the most likely part of speech of said second input word in accordance with said first determined part of speech.

14. The system of determining a part of speech of claim 13, wherein said first and second input words are adjacent words within said sequence of words.

15. The system for determining a part of speech of claim 9, wherein said selected word has query word weight further comprising the step of increasing said query word weight of said selected word when said most determined likely part of speech is a proper noun.