Method and apparatus for providing improved HMM POS tagger for multi-word entries and factoids

• US 6,985,851 B2
• Filed: 07/17/2001
• Issued: 01/10/2006
• Est. Priority Date: 07/17/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Weise, David Neal, Bala, Aravind
• Primary Examiner(s): Dorvil, Richemond
• Assistant Examiner(s): Shortledge, Thomas E.
• Application Number:
  US09/907,315
• Publication Number:
  US 20030061027A1
• Time in Patent Office: 1,638 Days
• Field of Search: 704/9, 704/8, 704/1, 704/4, 704/10, 704/5
• US Class Current: 704/9
• CPC Class Codes: G06F 40/216 using statistical methods

Abstract

A method of calculating trigram path probabilities for an input string of text containing a multi-word-entry (MWE) or a factoid includes tokenizing the input string to create a plurality of parse leaf units (PLUs). A PosColumn is constructed for each word, MWE, factoid and character in the input string of text which has a unique first (Ft) and last (Lt) token pair. TrigramColumns are constructed which define corresponding TrigramNodes each representing a trigram for three PosColumns. Forward and backward trigram path probabilities are calculated for each separate TrigramNode. The sums of all trigram path probabilities through each PLU are then calculated as a function of the forward and backward trigram path probabilities. Systems and computer-readable medium configured to implement the methods are also provided.

Claims

1. A method calculating trigram path probabilities for an input string of text, the method comprising:

tokenizing the input string of text to create plurality of parse leaf units (PLUs), wherein tokenizing the input string of text further comprises;

assigning a token number, consecutively from left to right, to each word and character in the input string of text;

identifying multi-word-entries (MWEs) and factoids in the input string of text; and

assigning parts of speech to each token, MWE and factoid;

constructing a PosColumn for each word, MWE, factoid and character in the input string of text which has a unique first (Ft) and last (Lt) token pair associated therewith, wherein constructing the PosColumn for each word, MWE, factoid and character in the input string of text further comprises;

adding dummy tokens for positions immediately prior to the first word, MWE, factoid or character and for positions immediately after the last word, MWE, factoid or character of the input string of text; and

assigning a Begin part of speech to dummy tokens for positions immediately prior to the first word, MWE, factoid or character of the input string of text, and assigning an End part of speech for positions immediately after the last word, MWE, factoid or character of the text;

constructing all TrigramColumns corresponding to the input string of text, wherein each TrigramColumn defines a corresponding TrigramNode representing a trigram for three PosColumns in the TrigramColumn, each TrigramNode being identifiable by a unique set of three tokens;

determining, for each TrigramColumn, all neighboring TrigramColumns to the immediate left and to the immediate right;

calculating a forward trigram path probability, for each separate TrigramNode of each TrigramColumn, of all forward paths from a TrigramNode in a right neighboring TrigramColumn through the separate TrigramNode;

calculating a backward trigram path probability, for each separate TrigramNode of each TrigramColumn, of all backward paths from a TrigramNode in a left neighboring TrigramColumn through the separate TrigramNode; and

calculating sums of all trigram path probabilities through each PLU as a function of the calculated forward and backward trigram path probabilities.

2. The method of claim 1, wherein constructing the PosColumn for each word, MWE, factoid and character in the input string of text further comprises:

constructing a separate PosColumn for each word, character and dummy token such that for the unique Ft and Lt token pair for that PosColumn, Ft is equal to Lt; and

constructing a separate PosColumn for each MWE and factoid such that for the unique Ft and Lt token pair for that PosColumn, Ft is less than Lt.

3. The method of claim 2, wherein each PosColumn includes one or more PLUs, and wherein in addition to the unique Ft and Lt token pair, for each PLU in a particular PosColumn the PosColumn further includes the corresponding assigned part of speech and a path probability for the PLU.

9. A computer-readable medium having computer executable instructions for performing the trigram path probability calculating steps of claim 1.

10. A computer-readable medium having computer executable instructions for performing the trigram path probability calculating steps of claim 2.

11. A computer-readable medium having computer executable instructions for performing the trigram path probability calculating steps of claim 3.

4. A method of calculating trigram path probabilities for an input string of text, the method comprising:

tokenizing the input string of text to create a plurality of parse leaf units (PLUs);

constructing a PosColumn for each word, multi-word-entry (MWE), factoid and character in the input string of text which has a unique first (Ft) and last (Lt) token pair associated therewith;

constructing all TrigramColumns corresponding to the input string of text, wherein each TrigramColumn defines a corresponding TrigramNode representing a trigram for three PosColumns in the TrigramColumn, each TrigramNode being identifiable by a unique set of three tokens, wherein each TrigramNode contains a probability of the corresponding trigram, the forward probability of all forward paths through the TrigramNode, the backward probability of all backward paths through the TrigramNode, and the sum of all trigram paths probabilities of all paths through the TrigramNode;

creating a Trigram Graph, the Trigram Graph including with each of the constructed TrigramColumns an array of associated TrigramNodes;

determining, for each TrigramColumn, all neighboring TrigramColumns to the immediate left and to the immediate right;

calculating a forward trigram path probability, for each separate TrigramNode of each TrigramColumn, of all forward paths from a TrigramNode in a right neighboring TrigramColumn through the separate TrigramNode;

calculating a backward trigram path probability, for each separate TrigramNode of each TrigramColumn, of all backward paths from a TrigramNode in a left neighboring TrigramColumn through the separate TrigramNode; and

calculating sums of all trigram path probabilities through each PLU as a function of the calculated forward and backward trigram path probabilities.

5. The method of claim 4, and further comprising calculating, for each TrigramNode, the sum of all trigram path probabilities of all paths through the TrigramNode by multiplying the probability of the corresponding trigram, the forward probability of all forward paths through the TrigramNode, and the backward probability of all backward paths through the TrigramNode.

6. The method of claim 5, wherein calculating the sums of all trigram path probabilities through each PLU comprises adding the sums of all trigram path probabilities, from each TrigramNode, corresponding to a path through the PLU.

12. A computer-readable medium having computer executable instructions for performing the trigram path probability calculating steps of claim 4.

13. A computer-readable medium having computer executable instructions for performing the trigram path probability calculating steps of claim 5.

14. A computer-readable medium having computer executable instructions for performing the trigram path probability calculating steps of claim 6.

7. A method of calculating trigram path probabilities for an input string of text, the method comprising:

tokenizing the input string of text to create a plurality of parse leaf units (PLUs);

constructing a PosColumn for each word, multi-word-entry (MWE), factoid and character in the input string of text which has a unique first (Ft) and last (Lt) token pair associated therewith;

constructing all TrigramColumns corresponding to the input string of text, wherein each TrigramColumn defines a corresponding TrigramNode representing a trigram for three PosColumns in the TrigramColumn, each TrigramNode being identifiable by a unique set of three tokens;

determining, for each TrigramColumn, all neighboring TrigramColumns to the immediate left and to the immediate right, wherein determining, for each TrigramColumn, all TrigramColumns to the immediate left further comprises determining that a first TrigramColumn TCI having a set of PosColumns (PCA, PCB, PCC) is to the immediate left of a second TrigramColumn TCJ having a set of PosColumns (PCX, PCY, PCZ) if PCB is equal to PCX and if PCC is equal to PCY;

calculating a forward trigram path probability, for each separate TrigramNode of each TrigramColumn, of all forward paths from a TrigramNode in a right neighboring TrigramColumn through the separate TrigramNode;

calculating a backward trigram path probability, for each separate TrigramNode of each TrigramColumn, of all backward paths from a TrigramNode in a left neighboring TrigramColumn through the separate TrigramNode; and

calculating sums of all trigram path probabilities through each PLU as a function of the calculated forward and backward trigram path probabilities.

8. The method of claim 7, wherein determining, for each TrigramColumn, all TrigramColumns to the immediate right further comprises determining that the first TrigramColumn TCI having the set of PosColumns (PCA, PCB, PCC) is to the immediate right of the second TrigramColumn TCJ having the set of PosColumns (PCX, PCY, PCZ) if PCY is equal to PCA and if PCZ is equal to PCB.

15. A computer-readable medium having computer executable instructions for performing the trigram path probability calculating steps of claim 7.

16. A computer-readable medium having computer executable instructions for performing the trigram path probability calculating steps of claim 8.

17. A trigram path probability calculating system for calculating trigram path probabilities for an input string of text, the system comprising:

a tokenizer configured to tokenize the input string of text to create a plurality of parse leaf units (PLUs), wherein the tokenizer is configured to tokenize the input string of text by assigning a token number, consecutively from left to right, to each word and character in the input string of text, by further identifying multi-word entries (MWEs) and factoids in the input string of text, and by further assigning parts of speech to each token, MWE and factoid;

a PosColumn generator configured to construct a PosColumnfor each word, MWE factoid and character in the input string of text which has a unique first (Ft) and last (Lt) token pair associated therewith, wherein the PosColumn generator is configured to construct the PosColumn for each word, MWE, factoid and character in the input string of text by adding dummy tokens for positions immediately prior to the first word, MWE, factoid or character and for positions immediately after the last word, MWE, factoid or character of the input string of text, and by assigning a Begin part of speech to dummy tokens for positions immediately prior to the first word, MWE, factoid or character of the input string of text, and assigning an End part of speech for positions immediately after the last word, MWE, factoid or character of the input string of text;

a TrigramColumn generator configured to construct TrigramColumns corresponding to the input string of text, wherein each TrigramColumn defines a corresponding TrigramNode representing a trigram for three PosColumns in the TrigramColumn, wherein the TrigramColumn generator is configured to construct the TrigramColumns such that each TrigramNode is identifiable by a unique set of three tokens, the TrigramColumn generator also configured to determine for each TrigramColumn all neighboring TrigramColumns to the immediate left and to the immediate right; and

a trigram path probability calculator configured to calculate a forward trigram path probability and a backward trigram path probability for each separate TrigramNode of each TrigramColumn, wherein the trigram path probability calculator is configured to calculate the forward trigram path probability for each separate TrigramNode of each TrigramColumn by calculating the forward trigram path probability, for each separate TrigramNode of each TrigramColumn, of all forward paths from a TrigramNode in a right neighboring TrigramColumn through the separate TrigramNode, and wherein the trigram path probability calculator is configured to calculate the backward trigram path probability for each separate TrigramNode of each TrigramColumn by calculating the backward path probability, for each separate TrigramNode of each TrigramColumn, of all backward paths from a TrigramNode in a left neighboring TrigramColumn through the separate TrigramNode, the trigram path probability calculator further configured to calculate sums of all trigram path probabilities through each PLU as a function of the calculated forward and backward trigram path probabilities.

18. The trigram path probability calculating system of claim 17, wherein the PosColumn generator is configured to construct the PosColumn for each word, MWE, factoid and character in the input string of text by constructing a separate PosColumn for each word, character and dummy token such that for the unique Ft and Lt token pair for that PosColumn, Ft is equal to Lt, and by constructing a separate PosColumn for each MWE and factoid such that for the unique Ft and Lt token pair for that PosColumn, Ft is less than Lt.

19. The trigram path probability calculating system of claim 18, wherein the PosColumn generator is configured to construct the PosColumn for each word, MWE, factoid and character in the input string of text such that each PosColumn includes one or more PLUs, and wherein in addition to the unique Ft and Lt token pair, for each PLU in a particular PosColumn the PosColumn further includes the corresponding assigned part of speech and a path probability for the PLU.

20. A trigram path probability calculating system for calculating trigram path probabilities for an input string of text, the system comprising:

a tokenizer configured to tokenize the input string of text to create a plurality of parse leaf units (PLUs);

a PosColumn generator configured to construct a PosColumn for each word, multi-word entry (MWE), factoid and character in the input string of text which has a unique first (Ft) and last (Lt) token pair associated therewith;

a TrigramColumn generator configured to construct TrigramColumns corresponding to the input string of text, wherein each TrigramColumn defines a corresponding TrigramNode representing a trigram for three PosColumns in the TrigramColumn;

a trigram path probability calculator configured to calculate a forward trigram path probability and a backward trigram path probability for each separate TrigramNode of each TrigramColumn, the trigram path probability calculator further configured to calculate sums of all trigram path probabilities through each PLU as a function of the calculated forward and backward trigram path probabilities;

a Trigram Graph generator configured to construct a Trigram Graph, the Trigram Graph including with each of the constructed TrigramColumns an array of associated TrigramNodes; and

wherein each TrigramNode contains a probability of the corresponding trigram, the forward probability of all forward paths through the TrigramNode, the backward probability of all backward paths through the TrigramNode, and the sum of all trigram path probabilities of all paths through the TrigramNode.

21. The trigram path probability calculating system of claim 20, wherein the trigram path probability calculator is further configured to calculate, for each TrigramNode, the sum of all trigram path probabilities of all paths through the TrigramNode by multiplying the probability of the corresponding trigram, the forward probability of all forward paths through the TrigramNode, and the backward probability of all backward paths through the TrigramNode.

22. The trigram path probability calculating system of claim 21, wherein the trigram path probability calculator is further configured to calculate the sums of all trigram path probabilities through each PLU by adding the sums of all trigram path probabilities, from each TrigramNode, corresponding to a path through the PLU.