Apparatus and methods for developing conversational applications

• US 7,302,383 B2
• Filed: 08/08/2003
• Issued: 11/27/2007
• Est. Priority Date: 09/12/2002
• Status: Expired due to Fees

• Current Assignee: Gyrus Logic Incorporated
• Original Assignee: Luis Calixto Valles
• Inventors: Valles, Luis Calixto
• Primary Examiner(s): Hudspeth; David
• Assistant Examiner(s): Neway; Samuel G
• Application Number:
  US10/636,991
• Publication Number:
  US 20040083092A1
• Time in Patent Office: 1,572 Days
• Field of Search: 704/9
• 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: G06F 40/30 Semantic analysis

Abstract

Apparatus includes subsystems for handling different communication acts and a programming interface for configuring the apparatus into a variety of conversational systems, allowing users to communicate interactively in natural language without restrictions whatsoever, either by speech or keyboard, while at the same time the apparatus is capable to interact with external applications.

Claims

1. Apparatus for maintaining unrestricted natural language discourse with humans and interacting with third party application programs comprising:

a plurality of user interfaces for allowing humans to input natural language phrases selected from the group consisting of speech and written text,

a processor,

storage means for storing data on a storage medium and having groups of executable instructions stored therein and,

wherein said processor is configured to execute said groups of executable instructions stored in memory, and said groups of executable instructions further comprise;

a. program logic responsive to said natural language phrases input and configurable to determine whether said natural language is;

i. a precise request if and only if said natural language phrase successfully meets the syntactical rules of a context-free user grammar as defined by a user for a specific application or

ii. a fuzzy request if said natural language phrase successfully meets the syntactical rules of a context-free universal grammar for all possible natural language phrases, but does not meet the syntactical rules of a said user grammar

b. program logic responsive to said fuzzy request and configured to process said fuzzy request speculatively and returning an approximated answer

c. program logic responsive to said precise request and configured to process said precise request precisely and returning one of the following;

an answer that precisely answers said human'"'"'s request

a confirmation

a follow up prompt for specifying further information

d. program logic responsive to said natural language phrases and configured to;

identify said natural language phrases as a unexpected spontaneous request in the context of a dialog,

process said natural language phrases as a unexpected spontaneous request and,

reply to said unexpected spontaneous request

e. program logic responsive to said natural language phrases and configured to identify an expected human phrase that is a reply to a prompt previously made by said system and, to request further information from said human user.

2. The apparatus of claim 1, wherein said program logic responsive to said natural language phrases and configured to process said spontaneous human phrase is further configured to:

detect when said spontaneous phrase initiates a brand new discourse segment, detect when said spontaneous human phrase diverges in meaning or context from a discourse segment already in progress, so forth initiating a second discourse segment,

engage in said second discourse segment, and

resume to the initial discourse segment.

3. The apparatus of claim 1, wherein said program logic responsive to said fuzzy request is further configured to convert said fuzzy request into a plurality of fuzzy query objects and cause a plurality of heuristic, stochastic, fuzzy logic, or speculative retrieval steps from a repository of answers.

4. The apparatus of claim 1, wherein said program logic responsive to said precise request, is further configured to process precisely by:

a. converting said precise requests into a plurality transaction steps

b. converting said precise requests into a plurality of query steps

c. invoking and execute said transaction steps and said query steps.

5. The apparatus of claim 1, wherein said program logic responsive to said natural language phrase, is further configured to detect if:

a. said precise request is a complete request, thereby containing all the information necessary to invoke and execute said transaction steps and said query steps, or

b. said precise request is an incomplete request, thereby containing part of the information necessary to invoke and execute said transaction steps and said query steps.

6. The apparatus of claim 1, wherein said program logic responsive to said natural language phrase, is further configured to derive a semantic representation of said natural language phrase from the syntactical analysis performed with said context free grammars, and said semantic representation is arranged as a tree structure of semantic objects.

7. The apparatus of claim 1, wherein said program logic responsive to said fuzzy request is further configured to retrieve data and convert it to a natural language narrative being customized for each user, and further comprising:

a. a digital document containing narrative paragraphs and phrases for fulfilling any fuzzy request,

b. a plurality of value placeholders, which hold returned data values from a data source being embedded in said repository of narrative paragraphs,

c. first program object code for retrieving data from said data source and for replacing said value placeholders by the returned values,

d. second program object code for combining said returned values with said narrative paragraphs, whereby the complete answers within the paragraphs are customized for the human'"'"'s specific needs, and for returning a set of complete narrative answers,

e. third program object code for searching heuristically the answers within said narrative paragraphs and retrieving the narrative answer that best matches said fuzzy request.

8. The apparatus of claim 1, wherein program logic responsive to said fuzzy request and returning a narrative answer, is also configured to,

return a score relative to the approximation in which the answer satisfies said fuzzy request

return a score relative to the precise request and is further configured to ascertain the best recognition result produced by speech recognition system and further comprising,

a. first program object code for receiving from said recognition system a plurality of text strings, which are the candidate recognition results of a single utterance

b. second program object code for determining the best recognition result depending on said score.

9. The apparatus of claim 1 for searching heuristically through a plurality of natural language answers and retrieving the best answers pertaining to a question and further comprising:

groups of executable instructions comprising;

a. first program object code for converting said plurality of natural language answers into a vector of semantic objects, wherein each member of the set corresponds to a semantic object, each said semantic object containing semantic information about the word, its role in the phrase, and its offset position in the phrase

b. second program object code for traversing the structure of said semantic representation and searching said semantic vector by logically comparing the semantic objects of said semantic representation with the semantic objects of said vector in the order directed by said traversing of the semantic representation

c. third program object code for converting said semantic vectors, which have been successfully matched by second program object code, into natural language phrases.

10. The apparatus of claim 6 for processing the semantic representation of a user request and further comprising:

groups of executable instructions comprising;

a. a reference to a section in said storage means storing said semantic representation of user requests being arranged as a structure of semantic objects

b. a reference to a section in said storage means storing a plurality of rule base systems or state machines, such that each rule base system makes reference to an third party application program and each rule in said rule base system is a state, which corresponds to a piece of information necessary to complete said third application program and further contains instruction steps

c. program object code for traversing said semantic representation and pattern-matching said semantic objects found of said semantic representation with the rules of said rule base system, such that the matching rules are inactive states and the unmatched rules are converted to active states

d. program object code for requesting said human for information associated to said active states until all information required for executing said third party application is provided by said human

e. program object code for executing the instruction steps of said active states and replying to said human

f. program object code for executing said third party application when all said states are inactive whereby the system understands and processes said human'"'"'s request and interacts with said human in the context of a dialog at the same time that interacts with a said third party application.

11. Method for distinguishing and categorizing a plurality of natural language requests from a human being, depending on whether or not said human being is demanding precise specific actions, into:

exact queries selected from the group of specific instructions and fuzzy queries selected from the group of fuzzy requests comprising the steps of;

a. receiving a natural language phrase from a plurality of user interfaces

b. sending requests to a parser generator, which takes as input a context free grammar and a natural language phrase

c. parsing said natural language phrase with said parser generator and a user grammar that contains production rules for requests specific to the functions available in a third party application

d. parsing said natural language phrase with said parser generator and a predefined universal grammar that contains a comprehensive set of syntactical rules for a specific natural language and said syntactical rule are independent of third party applications

e. determining whether said parser generator successfully parses the natural language phrase with said user grammar, or said parser generator successfully parses the natural language phrase with said universal grammar

f. producing a semantic representation of said phrase

g. sending said semantic representation to be interpreted as a precise transaction if said parser generator successfully parses said natural language phrase with said user grammar

h. sending said semantic representation to be interpreted as a precise query if said parser generator successfully parses said natural language phrase with said user grammar

i. sending said semantic representation to be interpreted as a fuzzy query to a heuristic search engine if the parsing with said user grammar is not successful, but the parsing with said universal grammar is successful.

12. The method of claim 11, wherein said natural language sentences can be further categorized in additional categories other than said fuzzy queries and said precise requests, comprising the steps of:

adding additional grammars that take third priority behind said user grammar and said universal grammar, such that if said parser fails with said user grammar and said universal grammar, said parser tries to parse said natural language request with said additional grammars, thereby categorizing said natural language request into said additional categories.

13. A method for reducing the development time of conversational dialogs by dividing user requirements into,

exact requests that can meet the syntactical rules of a user grammar as defined for a specific user application and that can be satisfied with precisions, and

fuzzy requests that can be parsed with the syntactical rules of a universal grammar, but not with said user grammar and that can be satisfied with approximated answers,

the method further comprising the steps of:

a. creating a template of answers, that map to said requests that can be satisfied with approximated answers, with reference calls to a plurality of third party software applications and value placeholders for holding returned data values from said software applications embedded in the narrative of said answers,

b. creating a grammar for said requests that must be satisfied with precision, and including ontological categories in the grammar rules of said grammar

c. creating a plurality of rule base systems, such that each rule base system corresponds to a transaction which in term corresponds to a plurality of said requests that must be satisfied with precision and such that each rule is tagged with the same ontological categories as in said grammar, and each said rule base system makes reference to an third party application program and each rule in said rule base system is a state, which corresponds to a piece of information necessary to complete said third application program.

14. Apparatus for managing a multiplicity of types of communicative acts in a natural language discourse comprising:

a plurality of user interfaces for allowing humans to input natural language phrases selected from the group consisting of speech and written text,

a processor,

storage means for storing data on a storage medium and having groups of executable instructions stored therein and,

wherein said processor is configured to execute said groups of executable instructions stored in memory, and said groups of executable instructions further comprise;

a. a multiplicity of context free grammars stored in said storage means wherein each grammar comprises syntactical rules for breaking down syntactically a natural language phrases that express one type of communicative act

b. program logic responsive to said natural language phrases input configured with said multiplicity of context free grammars in order to break down the syntactical structure of said natural language input, such that only one context free grammar is used successfully for breaking down the syntactical structure of one natural language phrase whenever said natural language phrase meets the syntactical rules of said context free grammar whereby, depending on which context free grammar is used successfully said program logic determines the type of communication act

c. program logic responsive to said natural language phrases input and to said multiplicity of context free grammars, is further configured to utilize said context free grammars according to priorities, such that once a type communication act has been identified, no other context free grammars are utilized

d. program logic responsive to the context free grammars that can process successfully said natural language phrase configured to traverse the grammar hierarchically and recursively and produce a hierarchical semantic structure containing semantic information including ontological categories, functions, lexicons and synonyms

e. program logic responsive to said semantic structure and said Boolean indicator and configured to determine the type of communicative act and to process said semantic structure depending on said type of communicative act unstructured data source.