INTEGRATION OF DOMAIN INFORMATION INTO STATE TRANSITIONS OF A FINITE STATE TRANSDUCER FOR NATURAL LANGUAGE PROCESSING

• US 20160188573A1
• Filed: 09/15/2015
• Published: 06/30/2016
• Est. Priority Date: 09/16/2014
• Status: Active Grant

• Current Assignee: Cerence Inc.
• Original Assignee: VoiceBox Technologies Corporation (Microsoft Corporation)
• Inventors: TANG, Min
• Granted Patent: US 9,898,459 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30
• CPC Class Codes: G10L 15/1815 Semantic context, e.g. disambiguation of the recognition hypotheses based on word meaning
• CPC Class Codes: G10L 2015/025 Phonemes, fenemes or fenones being the recognition units

Abstract

The invention relates to a system and method for integrating domain information into state transitions of a Finite State Transducer (“FST”) for natural language processing. A system may integrate semantic parsing and information retrieval from an information domain to generate an FST parser that represents the information domain. The FST parser may include a plurality of FST paths, at least one of which may be used to generate a meaning representation from a natural language input. As such, the system may perform domain-based semantic parsing of a natural language input, generating more robust meaning representations using domain information. The system may be applied to a wide range of natural language applications that use natural language input from a user such as, for example, natural language interfaces to computing systems, communication with robots in natural language, personalized digital assistants, question-answer query systems, and/or other natural language processing applications.

Claims

1. A computer implemented method for integrating domain information and semantic parsing to generate meaning representations from natural language input, the method being implemented on a computer system having one or more physical processors programmed with computer program instructions to perform the method, the method comprising:

receiving, by the computer system, a natural language input comprising at least a first input token;

obtaining, by the computer system, a semantic grammar;

determining, by the computer system, a semantic structure of the natural language input based on the semantic grammar;

retrieving, by the computer system, from an information domain, a plurality of domain tokens that match the first token of the natural language input; and

generating, by the computer system, a meaning representation based on the semantic structure and the plurality of domain tokens, wherein the meaning representation is used to execute a computer executable action.

2. The method of claim 1, wherein the plurality of domain tokens are structured into a domain information FST parser that includes at least a first FST path comprising a first set of domain tokens and a second FST path comprising a second set of domain tokens, and wherein generating the meaning representation further comprises:

selecting the first FST path based on a first score of the first FST path and a second score of the second FST path, wherein the first FST path is used to generate the meaning representation.

3. The method of claim 2, wherein the first score is based on a first sum of weights of each domain token among the first set of domain tokens and the second score is based on a second sum of weights of each domain token among the second set of domain tokens, and wherein a given weight for a domain token is based on a level of frequency that the domain token appears in the information domain.

4. The method of claim 2, wherein retrieving the plurality of domain tokens comprises:

initializing an input FST based on the first token and the semantic structure; and

composing the input FST based on the first FST path and the second FST path, wherein the first FST path and the second FST path are integrated with the input FST, and wherein the first FST is selected from the input FST.

5. The method of claim 4, wherein selecting the first FST path comprises selecting a shortest path in the input FST.

6. The method of claim 4, wherein retrieving the plurality of domain tokens comprises:

performing fuzzy or exact matching between domain tokens from the information domain and the first token, wherein the plurality of domain tokens comprises fuzzy or exact matches to the first token.

7. The method of claim 1, the method further comprising:

identifying a second token that is relevant to the first token and the information domain, wherein the second token is not initially included in the natural language input; and

adding the second token to the meaning representation.

8. The method of claim 1, wherein the natural language input comprises at least a second token, the method further comprising:

determining that the second token is not relevant to the information domain; and

omitting the second token from the meaning representation responsive to the determination that the second token is not relevant.

9. The method of claim 1, the method further comprising:

obtaining a phoneme confusion matrix comprising at least two similar sounding words that are disambiguated based on previous training from one or more user utterances; and

disambiguating the first token based on the phoneme confusion matrix.

10. The method of claim 1, the method further comprising:

obtaining one or more dynamic data tokens from a dynamic data source; and

integrating the one or more dynamic data tokens with the plurality of tokens from the information domain, wherein the meaning representation is determined based on the integrated dynamic data tokens.

11. The method of claim 10, wherein the plurality of domain tokens are structured into a domain information FST parser that includes at least a first FST path comprising a first set of domain tokens and a second FST path comprising a second set of domain tokens, and wherein integrating the one or more dynamic data tokens comprises:

generating a dynamic FST based on the one or more dynamic data tokens; and

inserting the dynamic FST into a slot of the domain information FST parser reserved for dynamic data.

12. The method of claim 1, wherein the computer executable action comprises an execution of:

a natural language-based search request or a natural language-based command.

13. The method of claim 1, wherein the information domain comprises a plurality of entries of searchable information, and wherein retrieving the plurality of domain tokens that match the first token comprises:

determining at least one entry, which includes the plurality of domain tokens, that is likely being searched for based on the first token.

14. A system for integrating domain information and semantic parsing to generate meaning representations from natural language input, the system comprising:

a computer system comprising one or more physical processors programmed with computer program instructions to;

receive a natural language input comprising at least a first input token;

obtain a semantic grammar;

determine a semantic structure of the natural language input based on the semantic grammar;

retrieve from an information domain, a plurality of domain tokens that match the first token of the natural language input; and

generate a meaning representation based on the semantic structure and the plurality of domain tokens, wherein the meaning representation is used to execute a computer executable action.

15. The system of claim 14, wherein the plurality of domain tokens are structured into a domain information FST parser that includes at least a first FST path comprising a first set of domain tokens and a second FST path comprising a second set of domain tokens, and wherein to generate the meaning representation, the computer system is further programmed to:

select the first FST path based on a first score of the first FST path and a second score of the second FST path, wherein the first FST path is used to generate the meaning representation.

16. The system of claim 15, wherein the first score is based on a first sum of weights of each domain token among the first set of domain tokens and the second score is based on a second sum of weights of each domain token among the second set of domain tokens, and wherein a given weight for a domain token is based on a level of frequency that the domain token appears in the information domain.

17. The system of claim 16, wherein to retrieve the plurality of domain tokens, the computer system is further programmed to:

initialize an input FST based on the first token and the semantic structure; and

compose the input FST based on the first FST path and the second FST path, wherein the first FST path and the second FST path are integrated with the input FST, and wherein the first FST is selected from the input FST.

18. The system of claim 17, wherein to select the first FST path, the computer system is further programmed to:

select a shortest path in the input FST.

19. The system of claim 17, wherein to retrieve the plurality of domain tokens, the computer system is further programmed to:

perform fuzzy or exact matching between domain tokens from the information domain and the first token, wherein the plurality of domain tokens comprises fuzzy or exact matches to the first token.

20. The system of claim 14, wherein the computer system is further programmed to:

identify a second token that is relevant to the first token and the information domain, wherein the second token is not initially included in the natural language input; and

add the second token to the meaning representation.

21. The system of claim 14, wherein the natural language input comprises at least a second token, and wherein the computer system is further programmed to:

determine that the second token is not relevant to the information domain; and

omit the second token from the meaning representation responsive to the determination that the second token is not relevant.

22. The system of claim 14, wherein the computer system is further programmed to:

obtain a phoneme confusion matrix comprising at least two similar sounding words that are disambiguated based on previous training from one or more user utterances; and

disambiguate the first token based on the phoneme confusion matrix.

23. The system of claim 14, wherein the computer system is further programmed to:

obtain one or more dynamic data tokens from a dynamic data source; and

integrate the one or more dynamic data tokens with the plurality of tokens from the information domain, wherein the meaning representation is determined based on the integrated dynamic data tokens.

24. The system of claim 23, wherein the plurality of domain tokens are structured into a domain information FST parser that includes at least a first FST path comprising a first set of domain tokens and a second FST path comprising a second set of domain tokens, and wherein to integrate the one or more dynamic data tokens, the computer system is further programmed to:

generate a dynamic FST based on the one or more dynamic data tokens; and

insert the dynamic FST into a slot of the domain information FST parser reserved for dynamic data.

25. The system of claim 14, wherein the computer executable action comprises an execution of:

a natural language-based search request or a natural language-based command.

26. The system of claim 14, wherein the information domain comprises a plurality of entries of searchable information, and wherein to retrieve the plurality of domain tokens that match the first token, the computer system is further programmed to:

determine at least one entry, which includes the plurality of domain tokens, that is likely being searched for based on the first token.

27. A method of generating an information domain FST parser for integrating domain information with semantic parsing to generate a meaning representation, the method being implemented on a computer system having one or more physical processors programmed with computer program instructions to perform the method, the method comprising:

obtaining, by the computer system, a plurality of entries of an information domain, wherein each entry comprises one or more domain tokens;

determining, by the computer system, a weight for each domain token, irrespective of whether a given domain token appears in more than one entry, wherein the weight indicates a level of frequency in which the given token appears in the information domain;

defining, by the computer system, for a given entry, a plurality of combinations of the one or more domain tokens, wherein each combination of the one or more domain tokens represent a different order of the one or more domain tokens and include some or all of the one or more domain tokens for the given entry;

determining, by the computer system, a score for each combination, wherein the score is based on the weight for each domain token involved in the combination; and

storing, by the computer system, the plurality of combinations for each of the plurality of entries.

28. The method of claim 27, wherein the plurality of combinations for each of the plurality of entries are collectively stored as an information domain FST parser, and wherein each combination represents an FST path of the information domain FST parser.

29. The method of claim 28, wherein the score for each combination comprises a path score for each FST path.

30. The method of claim 28, the method further comprising:

optimizing the information domain FST parser.