Componentized slot-filling architecture

• US 7,328,199 B2
• Filed: 10/07/2005
• Issued: 02/05/2008
• Est. Priority Date: 10/07/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Katariya, Sanjeev, Ramsey, William D., Gao, Jianfeng
• Primary Examiner(s): STARKS, WILBERT L
• Application Number:
  US11/246,847
• Publication Number:
  US 20070094185A1
• Time in Patent Office: 851 Days
• Field of Search: 386/8, 704/1, 704/9, 704/4, 706/45, 715/716, 726/26
• US Class Current: 706/45
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

The subject disclosure pertains to systems and methods for performing natural language processing in which tokens are mapped to task slots. The system includes a mapper component that generates a lattice representing possible interpretations of the tokens, a decoder component that creates a ranked list of paths traversing the lattice, a scorer component that generates scores used to rank paths and post-processing components that format the paths for use by other software. Each of these components may be independent, such that the component may be modified or replaced without affecting the remaining components. This allows a variety of different mathematical models and algorithms to be tested or deployed without requiring changes to the remainder of the system.

Claims

1. A natural language processing machine interface system, comprising:

a mapper component that maps at least one token representing a string of characters broken out of a natural language command entered by a user to a user desired task performed by a downstream computer-implemented software application and generates a lattice that includes at least one interpretation for the at least one token;

a decoder component that generates at least one path that traverses the lattice, the mapper component and decoder component are independent, such that modification of at least one of the mapper component and the decoder component does not affect the other component; and

a post-processor component that generates a semantic solution, representing the at least one path, that the downstream software application uses as input data to implement the user desired task, wherein the semantic solution is at least one of stored on a computer readable storage medium, displayed on a display device, or employed by the downstream software application executing on one or more processors.

2. The system of claim 1, further comprising a scorer component that generates a score for the at least one path, the decoder component utilizes the score to rank the at least one path, the scorer component is independent of the mapper component and the decoder component, such that modification of at least one of the mapper component, the decoder component and the scorer component does not affect the other components.

3. The system of claim 2, the scorer component utilizes at least one of a heuristic function, a hidden Markov model, a Naï

ve Bayes based model, Maximum Entropy/Minimum Divergence Models (MEMD) and linear discriminative models to generate the score for the at least one path.

4. The system of claim 1, the post-processor component is independent of the mapper component and the decoder component, such that modification of at least one of the mapper component, the decoder component and the post-processor component does not affect the other components.

5. The system of claim 4, further comprising a scorer component that generates a score for the at least one path, the decoder component utilizes the score to rank the at least one path and the scorer component is independent of the mapper component, the decoder component and the post-processor component, such that modification of at least one of the mapper component, the decoder component, the post-processor component and the scorer component does not affect the other components.

6. The system of claim 4, the semantic solution is displayed to the user for verification.

7. The system of claim 1, the mapper component utilizes user feedback from prior processing to generate the lattice.

8. The system of claim 1, the decoder component utilizes at least one of beam search, Viterbi search or A* search to generate the at least one path.

9. The system of claim 1, the lattice includes at least one self-describing fragment.

10. A natural language analysis method, comprising:

mapping at least one token representing a string of characters broken out of a natural language command entered by a user to a user desired task performed by a downstream machine application using a mapper component;

generating a lattice that includes at least one interpretation of at least one token using the mapper component; and

generating at least one path that traverses the lattice using a decoder component, the mapper component and decoder component are independent;

modifying one of the mapper component and the decoder component does not entail modifying the other component; and

p1 generating a semantic solution, representing the at least one path, using a post-processor component, the downstream machine application uses the semantic solution as input data to implement the user desired task, wherein the semantic solution is at least one of stored on a computer readable storage medium, displayed on a display device, or employed by the downstream software application executing on one or more processors.

11. The method of claim 10, further comprising:

generating a score for the at least one path utilizing a scorer component; and

ranking the at least one path based at least in part upon the score for the at least one path, the scorer component is independent of the mapper component and the decoder component, such that modification of at least one of the mapper component, the decoder component and the scorer component does not affect the other components.

12. The method of claim 11, utilizing at least one of a heuristic function, a hidden Markov model, a Naï

ve Bayes based model, Maximum Entropy/Minimum Divergence Models (MEMD) and linear discriminative models to generate the score for the at least one path.

13. The method of claim 10, further comprising:

generating a semantic solution for the at least one path using a post-processor component, the post-processor component is independent of the mapper component and the decoder component, such that modification of at least one of the mapper component, the decoder component and the post-processor component does not affect the other components.

14. The method of claim 13, further comprising:

displaying the semantic solution for user verification.

15. The method of claim 10, further comprising using user feedback in generating the lattice.

16. The method of claim 10, further comprising:

utilizing at least one of beam search, Viterbi search or A* search to generate the at least one path.

17. The method of claim 10, the lattice includes at least one self-describing fragment.

18. A natural language system:

means for mapping at least one token representing a string of characters broken out of a natural language command entered by a user to a user desired task performed by a downstream machine application;

means for generating a lattice based at least in part upon the at least one token and the task;

means for generating at least one path that traverses the lattice, the means for mapping and the means for generating at least one path are independent, such that modification of at least one of the means for mapping and the means for generating at least one path does not affect the other component; and

means for generating a semantic solution, representing the at least one path, that the downstream machine application uses as input data to implement the user desired task, wherein the semantic solution is at least one of stored on a computer readable storage medium, displayed on a display device, or employed by the downstream software application executing on one or more processors.

19. The system of claim 18, further comprising:

means for generating a score for the at least one path; and

means for ranking the at least one path based at least in part upon the score for the at least one path, the means for generating a score is independent of the means for mapping and the means for generating at least one path, such that modification of at least one of the means for mapping and the means for generating at least one path and the means for generating a score does not affect the other components.

20. The system of claim 18, means for generating a semantic solution is independent of the means for mapping and the means for generating at least one path, such that modification of at least one of the means for mapping, the means for generating at least one path and the means for generating a semantic solution does not affect the other components.