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

• US 7,124,074 B2
• Filed: 06/14/2005
• Issued: 10/17/2006
• Est. Priority Date: 07/17/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bala, Aravind, Weise, David Neal
• Primary Examiner(s): Dorvil, Richemond
• Assistant Examiner(s): Shortledge, Thomas E.
• Application Number:
  US11/151,953
• Publication Number:
  US 20050234717A1
• Time in Patent Office: 490 Days
• Field of Search: 704/9, 704/8, 704/1, 704/10, 704/4
• 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 of calculating trigram path probabilities for an input string of text, the method comprising:

tokenizing the input string often 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 swing 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;

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 though 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 though the separate TrigramNode; and

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

2. The method of claim 1, and further comprising normalizing, for each PLU, the sums of all trigram path probabilities for the particular PLU.

3. The method of claim 2 wherein normalizing, for each PLU, the stuns of all trigram path probabilities for the particular PLU further comprises normalizing the sums of all path probabilities through the particular PLU such that the sums for the particular PLU total one.

4. The method of claim 1, wherein tokenizing the input string of text further comprises assigning it token number, consecutively from left to right, to each word and character in the input string of text.

5. The method of claim 4, wherein tokenizing the input string of text further comprises identifying MWEs and factoids in the input string of text.

6. The method of claim 5, wherein tokenizing the input string of text further comprises assigning parts of speech to each token, MWE and factoid.

7. The method of claim 1, and after the step of constructing all TrigramColumns corresponding to the input string of text, further comprising creating a Trigram Graph, the Trigram Graph including with each of the constructed TrigramColumns an array of associated TrigramNodes.

8. A computer-readable medium having computer executable instructions for performing the trigram path probability calculating steps comprising:

tokenizing an 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;

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.

9. The computer readable medium of claim 8, and further having computer executable instructions for performing the trigram path probability calculating step comprising normalizing, for each PLU, the sums of all trigram path probabilities for the particular PLU.

10. The computer readable medium of claim 8, 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.

11. The computer readable medium of claim 10, wherein tokenizing the input string of text further comprises identifying MWEs and factoids in the input string of text.

12. 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, 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.

13. The trigram path probability calculating system of claim 12, wherein the TrigramColumn generator is configured to construct the TrigramColumns corresponding to the input string often 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.

14. The trigram path probability calculating system of claim 13, 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.

15. The trigram path probability calculating system of claim 14, 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.

16. The trigram path probability calculating system of claim 15, and further comprising a normalizer configured to normalize, for each PLU, the sums of all trigram path probabilities for the particular PLU.

17. The trigram path probability calculating system of claim 15, 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.

18. The trigram path probability calculating system of claim 17, wherein the tokenizer is configured to tokenize the input string of text by further identifying MWEs and factoids in the input string of text.

19. The trigram path probability calculating system of claim 18, wherein the tokenizer is configured to tokenize the input string of text by further assigning parts of speech to each token, MWE and factoid.

20. The trigram path probability calculating system of claim 12, and further comprising 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.