Method of and apparatus for recognizing and labeling instances of name classes in textual environments

• US 6,052,682 A
• Filed: 05/02/1997
• Issued: 04/18/2000
• Est. Priority Date: 05/02/1997
• Status: Expired due to Term

• Current Assignee: Cxense ASA
• Original Assignee: BBN Corporation (Verizon Communications Inc.)
• Inventors: Miller, Scott, Bikel, Daniel M., Schwartz, Richard M.
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US08/848,972
• Time in Patent Office: 1,082 Days
• Field of Search: 707/1, 707/3, 707/4, 707/5, 707/6
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A computer assisted method for recognizing and labeling instances of name classes in textual environments is described. The invention receives training text having instances of named-entity classes labeled, from which it generates a database of bigram and unigram occurrences. The invention uses the database of bigram and unigram occurrences to form a two level Hidden Markov Model with single output states at the lower level. The invention also receives a series of input text to be processed and labeled with respect to the name classes, and the invention uses the two level Hidden Markov Model to recognize and label instances of named-entity classes in the input text.

Claims

1. A named-entity recognition system comprising:

a multilevel hidden Markov model, said hidden Markov model including;

(a) at least one upper level representing named entities; and

(b) at least one lower level representing words generated by the upper level.

2. A named-entity recognition system according to claim 1, wherein the upper level includes a plurality of name classes, and said lower level includes a plurality of word states.

3. A named-entity recognition system according to claim 1, wherein said Markov model includes a first language model for assigning transition probabilities between the states of the upper level, and includes a second language model for assigning transition probabilities between the words of the lower level.

4. A named-entity recognition system according to claim 3, wherein said first language model is a bigram model, and said said second language model is a bigram model.

5. A named-entity recognition system according to claim 1, wherein at least one of the transitions between said upper levels is conditioned on the output of the previous lower states, and at least one of the transitions between the lower states is conditioned on the output of the previous upper state.

6. A named-entity recognition system comprising:

a multilevel hidden Markov model, said hidden Markov model including;

(a) at least one upper level including a first plurality of states of a predefined classification of named entities, and

(b) at least one lower level including a second plurality of states of a predefined classification of words,

wherein at least one of the transitions between the upper states is conditioned on the output of the previous lower states, and at least one of the transitions between the lower state is conditioned on the output of the previous upper state.

7. A named-entity recognition system according to claim 6, wherein said Markov model includes a first language model for assigning transition probabilities between the states of the upper level, and includes a second language model for assigning transition probabilities between the words of the lower level.

8. A named-entity recognition system according to claim 7, wherein said first language model is a bigram model, and said said second language model is a bigram model.

15. A apparatus according to claim 8, wherein some of said transitional probabilities are conditioned upon said name class states, some of said transitional probabilities are conditioned upon said member states, and some of said transitional probabilities are conditioned upon both name class states and said member states.

9. A computer-assisted method for recognizing and labeling instances of name classes in textual environments, comprising the following steps:

A. receiving a marked string of words and using said marked string to estimate a plurality of HMM parameters, and using said plurality of HMM parameters to generate an HMM having N states, each of said N states representing a name class and having a plurality of member states;

B. receiving an unmarked string of K words, K being an integer;

C. recognizing and labeling a plurality of name class instances in said unmarked string of K words, including the following substeps;

i. receiving a k^th and a (k+1)^th word from said unmarked string of K words;

ii. determining, from said HMM parameters, a transition probability representing a likelihood of said (k+1)^th word being a member of an i^th state, given said k^th word being a member of a j^th state, and given said (k+1)^th word immediately following said k^th word, said i^th and k^th states being member states of said N states;

iii. repeating step (ii) for all i from 1 to N and for all j from 1 to N, whereby N² transition probabilities are determined, and retaining the highest transition probability to the (k+1)^th word in each of the N states;

iv. repeating steps (i), (ii) and (iii) for all k from 1 to K, whereby N·

(K-1) transition probabilities are retained;

v. identifying a highest probability path from the K^th word back to the first word; and

,

vi. labeling each of said K words with said name class state through which said highest probability path from the N identified paths passes.

10. A method according to claim 9, wherein said HMM parameters include a plurality of bigram probabilities and a plurality of unigram probabilities, and said transitional probabilities are determined by selecting from said bigram probabilities and unigram probabilities, in a predetermined order, based upon said k^th and said (k+1)^th appearances in said marked string of words.

11. A method according to claim 9, wherein some of said transitional probabilities are conditioned upon said name class states, some of said transitional probabilities are conditioned upon said member states, and some of said transitional probabilities are conditioned upon both name class states and said member states.

12. A method according to claim 9, wherein said number of name class states N is 8.

13. A method according to claim 9, wherein each of said member states is representative of a single word.

14. A apparatus according to claim 9, wherein said HMM parameters include a plurality of bigram probabilities and a plurality of unigram probabilities, and said transitional probabilities are determined by selecting from said bigram probabilities and unigram probabilities, in a predetermined order, based upon said k^th and said (k+1)^th appearances in said marked string of words.

16. A computer system for recognizing and labeling instances of name classes in textual environments, comprising:

A. means for providing a marked string of words and using said marked string to estimate a plurality of HMM parameters, and using said plurality of HMM parameters to generate an HMM having N states, each of said N states representing a name class and having a plurality of member states;

B. means for receiving an unmarked string of K words, K being an integer;

C. means for recognizing and labeling a plurality of name class instances in said unmarked string of K words, including;

i. means for receiving a k^th and a (k+1)^th word from said unmarked string of K words;

ii. means for determining, from said HMM parameters, a transition probability representing a likelihood of said (k+1)^th word being a member of an i^th state, given said k^th word being a member of a j^th state, and given said (k+1)^th word immediately following said k^th word, said i^th and k^th states being member states of said N states;

iii. means for repeating step (ii) for all i from 1 to N and for all j from 1 to N, whereby N² transition probabilities are determined, and retaining the highest transition probability to the (k+1)^th word in each of the N states;

iv. means for repeating steps (i), (ii) and (iii) for all k from 1 to K, whereby N·

(K-1) transition probabilities are retained;

v. means for identifying a highest probability path from the K^th word back to the first word; and

,

vi. means for labeling each of said K words with said name class state through which said highest probability path from the N identified paths passes.