System and method for identifying base noun phrases

• US 7,496,501 B2
• Filed: 10/29/2004
• Issued: 02/24/2009
• Est. Priority Date: 04/23/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Xun, Endong, Zhou, Ming, Huang, Chang-Ning
• Primary Examiner(s): Edouard; Patrick N
• Assistant Examiner(s): Spooner; Lamont M
• Application Number:
  US10/977,979
• Publication Number:
  US 20050071149A1
• Time in Patent Office: 1,579 Days
• Field of Search: 704/1, 704/9, 704/10, 704/231, 704/251, 715/255, 715/257, 715/259, 707 2- 6
• US Class Current: 704/9
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• 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 system and method identify base noun phrases (baseNP) in a linguistic input. A part-of-speech tagger identifies N-best part-of-speech tag sequences corresponding to the linguistic input. A baseNP identifier identifies baseNPs in the linguistic input using a unified statistical model that identifies the baseNPs, given the N-best POS sequences.

Claims

1. A computer readable medium having stored thereon instructions which, when executed, cause a computer to perform a method of processing a natural language input, comprising:

identifying a plurality of N-best part-of-speech (POS) tag sequences corresponding to the natural language input;

identifying a likely base noun phrase (baseNP) sequence based on the N-best POS tag sequences identified; and

outputting the likely baseNP sequence.

2. The computer readable medium of claim 1 wherein identifying a likely baseNP sequence comprises:

identifying a plurality of baseNP sequences for each of the N-best POS tag sequences that correspond to the natural language input; and

calculating which of the plurality of baseNP sequences is most likely.

3. The computer readable medium of claim 2 wherein calculating which of the plurality of baseNP sequences is most likely comprises:

calculating a likely baseNP sequence that is most likely based on lexical information indicative of a position of words in the natural language input relative to baseNPs identified in the baseNP sequences.

4. The computer readable medium of claim 3 wherein calculating a likely baseNP sequence that is most likely based on lexical information comprises:

calculating a likely baseNP sequence that is most likely based on lexical information indicative of POS tags assigned to the words in the natural language input.

5. The computer readable medium of claim 3 wherein calculating a likely baseNP sequence comprises:

calculating a likely baseNP sequence based on the lexical information for every word in the natural language input.

6. The computer readable medium of claim 3 wherein a baseNP rule comprises a sequence of POS tags corresponding to words in the natural language input identified as a baseNP and wherein calculating a likely baseNP sequence comprises:

calculating a probability of POS tags and baseNP rules, given their context.

7. The computer readable medium of claim 6 wherein calculating a probability of POS tags and baseNP rules comprises:

calculating the probability of POS tags and baseNP rules given n prior POS tags or baseNP rules.

8. The computer readable medium of claim 2 wherein the natural language input comprises a sentence and wherein calculating which of the plurality of baseNP sequences is most likely comprises:

calculating which of the plurality of baseNP sequences is most likely over the entire sentence.

9. The computer readable medium of claim 1 wherein identifying a likely baseNP sequence includes:

calculating a probability of each of the N-best POS tag sequences given the natural language input.

10. The computer readable medium of claim 1 wherein a component of the natural language input corresponds to a different part of speech tag in at least two of the identified N-best POS tag sequences.

11. The computer readable medium of claim 1 wherein one of the identified N-best POS tag sequences includes a POS tag that corresponds to a component of the natural language input and the POS tag is different than a POS tag that corresponds to the component of the natural language input in another one of the identified N-best POS tag sequences.

12. A computer readable medium storing instructions which, when executed by a computer, cause the computer to perform a method of processing a linguistic input, comprising:

identifying a plurality of N-best part-of-speech (POS) sequences corresponding to the linguistic input;

identifying one or more base noun phrases (baseNPs) for each of the N-best POS sequences to form a plurality of different possible baseNP sequences corresponding to each of the POS sequences;

for each baseNP sequence, identifying whether it is a likely baseNP sequence based on a probability of the associated POS sequence and a probability of the baseNP sequence, given lexical information indicative of a position of words in the linguistic input relative to the baseNPs identified in the baseNP sequence; and

outputting the likely baseNP sequence identified.

13. The computer readable medium of claim 12 wherein identifying one or more baseNPs for each of the N-best POS sequences comprises:

identifying baseNP rules for each of the N-best POS sequences, the baseNP rules comprising a sequence of POS tags corresponding to words in the linguistic input identified as a baseNP.

14. The computer readable medium of claim 13 wherein identifying whether each baseNP sequence is a likely baseNP sequence, comprises:

calculating a probability of POS tags and baseNP rules, given n prior POS tags or baseNP rules in the POS sequence.

15. The computer readable medium of claim 14 wherein the linguistic input comprises a sentence and wherein identifying whether each baseNP sequence is a likely baseNP sequence comprises:

identifying whether each baseNP sequence is a likely baseNP sequence over the entire sentence.

16. The computer readable medium of claim 12 wherein a component of the natural language input corresponds to a different part of speech tag in at least two of the identified N-best POS tag sequences.

17. A computer readable medium having stored thereon instructions which, when executed, cause a computer to perform a method of processing a natural language input, comprising:

identifying a plurality of N-best part-of-speech (POS) tag sequences corresponding to the natural language input, wherein each of the plurality of N-best POS tag sequences comprises a sequence of POS tags and wherein at least one of the plurality of N-best POS tag sequences includes a POS tag corresponding to a component of the natural language input and the POS tag is different than a POS tag corresponding to the component of the natural language input in another one of the N-best POS tag sequences;

identifying a likely base noun phrase (baseNP) sequence based on the N-best POS tag sequences identified; and

outputting the likely baseNP sequence.

18. The computer readable medium of claim 17 wherein the natural language input comprises a sequence of words.

19. The computer readable medium of claim 18 wherein each POS tag corresponds to a word in the sequence of words.

20. The computer readable medium of claim 17 wherein identifying a likely baseNP sequence comprises:

identifying a plurality of baseNP sequences for each of the N-best POS tag sequences; and

calculating which of the plurality of baseNP sequences is most likely.