Apparatus and methods for developing conversational applications

• US 20040083092A1
• Filed: 08/08/2003
• Published: 04/29/2004
• Est. Priority Date: 09/12/2002
• Status: Active Grant

• Current Assignee: Gyrus Logic Incorporated
• Original Assignee: Luis Calixto Valles
• Inventors: Valles, Luis Calixto
• Granted Patent: US 7,302,383 B2
• Time in Patent Office: Days
• 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 with accompanying subsystems and methods for developing conversational computer applications. As a user interface, the apparatus allows for a user to initiate the conversation. The apparatus also answers simple and complex questions, understands complex requests, pursues the user for further information when the request is incomplete, and in general provides customer support with a human like conversation while, at the same time, it is capable to interact with a company'"'"'s proprietary database. As a development tool, the apparatus allows a software developer to implement a conversational system much faster than takes, with current commercial systems to implement basic dialog flows. The apparatus contains three major subsystems: a state transition inference engine, a heuristic answer engine and a parser generator with semantic augmentations. A main process broker controls the flow and the interaction between the different subsystems. The state transition inference engine handles requests that require processing a transaction or retrieving exact information. The heuristic answer engine answers questions that do not require exact answers but enough information to fulfill the user'"'"'s request. The parser generator processes the user'"'"'s natural language request, that is, it processes the syntactical structure of the natural language requests and it builds a conceptual structure of the request. After the parser generator processes the user'"'"'s request, a main process broker feeds the conceptual structure to either the heuristic answer engine or to the state transition inference engine. The interaction between the main process broker and the subsystems creates a conversational environment between the user and the apparatus, while the apparatus uses information from proprietary databases to provide information, or process information, during the course of the conversation. The apparatus is equipped with a programming interface that allows implementers to declare and specify transactions based requests and answers to a multiplicity of questions. The apparatus may be used with a speech recognition interface, in which case, the apparatus improves the recognition results through the context implicitly created by the apparatus.

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 configured to generate a semantic representation for each of the natural language phrases and to identify whether said semantic representation is

a fuzzy request, or

a precise request

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 semantic representation and configured to;

identify said semantic representation as a spontaneous request in the context of a dialog

process said semantic representation as a spontaneous request and,

reply to said spontaneous request

e. program logic responsive to said semantic representation 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, but not precluding potential interruptions by spontaneous human made requests

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

a. convert said precise requests into a plurality transaction steps

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

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

5. :

The apparatus of claim 4, wherein said program logic responsive to said precise request, is further configured to detect;

if said precise request is a complete request, thereby containing all the information necessary to invoke and execute said transactional steps and said query steps

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

6. :

The apparatus of claim 1, wherein said program logic responsive to said natural language phrases input, further comprises;

a. first program object code for parsing said natural language phrase with a user grammar that contains production rules for sentences specific to a transactional application

b. second program object code for parsing said natural language phrase with a predefined universal grammar that contains a comprehensive set of syntactical rules of a specific natural language and are independent of any application

c. third program object code for converting said natural language phrase into its semantic representation

d. forth program object code for determining;

whether said semantic representation is to be interpreted as a precise transaction and,

whether said semantic representation is to be interpreted as a precise query

 

whenever the first program object code successfully parses the natural language phrase with said user grammar

e. fifth program object code for determining whether said semantic representation is to be interpreted as a fuzzy query and cause a speculative search, whenever the first program object code is not successful and the second program object code is successful.

7. :

The apparatus of claim 6, wherein the semantic representation of the natural language phrase is arranged as a tree structure of semantic objects.

8. :

The apparatus of claim 1, wherein said program logic responsive to said fuzzy request is further configured to retrieve a plurality of answers, in the form of natural language, from a plurality of third party software application, regardless of;

how said third party software application stores information,

how said third party software application retrieves and delivers said information and

format in which said third party software application delivers said information,

and being said information customized for a human making said natural language request, and further comprising;

a. a plurality of references to sections in said storage means, having said references a plurality of call addresses to software applications and a plurality of addresses for value placeholders, which hold returned data values from said software applications

b. a plurality of references to sections in said storage means, having said references a copy of said value placeholders embedded in a narrative template of answers

c. first program object code for executing said third party software application as directed by said call addresses and for replacing said value placeholders embedded in said narrative template, by the returned values, from said third party software application,

whereby the result, from combining the returned values with the narrative template, is a set of complete answers customized for the human'"'"'s specific needs and for further retrieval

d. second program object code for searching heuristically said set of complete answers and retrieving the best answers pertaining to said fuzzy request

9. :

The apparatus of claim 8, wherein said program object code for searching heuristically said set of complete answers and retrieving the best answers pertaining to said fuzzy request, further comprises;

e. first program object code for converting said set of complete 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

f. 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

g. 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 5, wherein said program logic responsive to said precise request, further comprises;

a. 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

b. 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

c. 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

d. 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. :

The apparatus of claim 1, wherein program logic responsive to said fuzzy request and returning an answer, is configured to also return a score relative to the approximation in which the answer satisfies said fuzzy request.

12. :

The apparatus of claim 11, wherein program logic responsive to said precise request, is configured to always return a perfect score.

13. :

The apparatus of claim 12, further comprising a speech recognition system that converts speech to a plurality of orthographic transcriptions or strings.

14. :

The apparatus of claim 13, further comprising program logic responsive to said orthographic transcription and configured to determine the best recognition result depending on the score associated with each reply provided by said program logic responsive to said precise request and said program logic responsive to said fuzzy request

whereby the speech recognition of a speech recognition system is improved.

15. :

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 questions and specific instructions

fuzzy queries selected from the group of fuzzy questions and fuzzy requests

comprising the steps of;

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

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.

16. :

The method of claim 15, 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.

17. :

The method of claim 16, 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

16-1. :

A method for reducing development time of a natural language application comprising the steps of;

a. mapping user requirements to sample requests

b. dividing said sample requests into;

requests that can be satisfied with approximated answers and,

requests that must be satisfied with precision

18. :

Method for taking a natural language request as input and for retrieving a plurality of answers, in the form of natural language, from a plurality of third party software application, regardless of;

how said third party software application stores information,

how said third party software application retrieves and delivers said information and

format in which said third party software application delivers said information,

such that said plurality of answers are customized for a human making said natural language request, comprising;

a. receiving from humans information in natural language selected from the group consisting of speech and written text

b. parsing said natural language phrase and converting said phrase to a structure of semantic objects,

whereby said structure of semantic objects is a semantic representation of the natural language phrase

c. storing reference calls to a plurality of software applications and value placeholders, which hold returned data values from said software applications

d. storing said value place holders embedded in a narrative template of answers

d. invoking said third party software application as directed by said reference calls and replacing said value placeholders embedded in said narrative template, by the returned values, from said third party software application,

whereby the result, from combining the returned values with the narrative template, is a set of complete answers customized for the human'"'"'s specific needs and for further retrieval

e. converting said customized text of answers into a vector of semantic objects, each object containing semantic information about the word, its role in the phrase, and its offset position in the phrase

f. traversing said structure of semantic objects and searching said semantic vector by logically comparing the semantic objects of said structure with the semantic objects of said vector in the order directed by traversing said structure of semantic objects

g. assigning to each semantic vector a score, which indicates the relevance of the answers in relation to the natural language request made by said human and said score depends on the number of the matches found

h. converting said semantic vectors to natural language phrases

2. :

The apparatus of claim 1, wherein said program logic responsive to said semantic representation and configured to process said spontaneous human phrase and to reply to said spontaneous phrase is further configured to;

detect when said spontaneous phrase initiates a brand new discourse segment

detect when said spontaneous phrase interrupts a discourse segment already in progress, so forth initiating a second discourse segment

engaged in said second discourse segment, and

resume to the interrupted discourse segment

19. :

The method of claim 18, wherein said structure of semantic object representing a natural language phrase is arranged as a hierarchical or treelike structure and further comprises;

a plurality of sub-trees each representing a conceptual constituents.

nodes containing;

the ontological category of the conceptual constituent

the word in the phrase

super classes of the word

the children of the node

a set of synonyms for the conceptual constituent, and

the phrasal category of the conceptual constituent

and said tree structure is stored as a tree data structure, which can be traversed by the program code of said system

whereby the closer to the root that the nodes are in the hierarchy of said tree, the more general information they provide about a phrase, and

whereby the closer the nodes are to the leaves of said tree, the more specific the information is within the tree.

20. :

The method of claim 19, where in said tree structure representing a natural language phrase is arranged such that every word is a function with arguments such that said function corresponds to a node in the tree and each argument is a conceptual constituent, each said argument corresponding to a children of said node.

21. :

The method of claim 20, wherein the step for parsing said natural language phrase and converting said phrase to a tree structure of semantic objects further comprises the steps of;

a. retrieving said function and said functional arguments from said database of functions based on the words in the nodes of said tree structure

b. logically comparing a node of said tree structure to said retrieved function and logically comparing the children of the node, in type and number, to the arguments of the function, such that the comparison is recursive until said tree structure is traversed

c. rejecting the natural language request if the comparison fails

d. accepting the natural language request if the comparison does not fail

whereby the correctness of the syntax of a natural language phrase is thereby augmented with semantic correctness.

22. :

The method of claim 20 further comprising the steps of;

a. traversing said tree structure and logically comparing the semantic objects in said tree structure with the semantic objects in said vector of semantic objects.

b. searching said vector of semantic objects, within the limits of a pre-established threshold value, forwards and backwards from the each previous match encountered as the tree structure is continued to be traversed from the root node to the leave nodes,

c. measuring the distance between the previous match and the new match

d. retrieving a plurality of vectors of semantic objects that provide a close match and said vector is stored a candidate answer vector and

e. assembling textual answers from said candidate answer vector.

23. :

The method of claim 22, wherein said step of traversing said tree structure and logically comparing the semantic objects, a match between said semantic objects is successful if;

a literal comparison between words matches or,

a comparison based on synonyms of the word matches or,

a comparison based on super-classes of the word matches or,

a comparison based on the ontological categories existing in the node and in the semantic object matches

and depending of which comparison matches, each type of match has a specific score, the lowest score given by a match based on ontological categories and the highest score given by a literal match between words.

24. :

The method of claim 23, further comprising the step of calculating a weight representing a correspondence between the relation between two words in said vector of objects to the relation between two nodes in said tree, by multiplying the pre-calculated distance between the two semantic objects times said score

whereby the semantic objects, in said vector of objects, with the highest and lowest offset positions provide the boundaries of the answer within the text, and such positions are used to retrieve the answer and to store it in an answer object.

25. :

The method of claim 24, wherein said step for calculating said weight, further comprises the steps of;

calculating a tree measurement for said tree of semantic objects by multiplying the number of nodes times said threshold value

calculating a score for said answer object as a percentage relation between said weight and said tree measurement

whereby the best answer from the answer vector is the answer with the highest score.

26. :

The method of claim 18, wherein multimedia related to a user'"'"'s question, is retrieved, by establishing a correspondence between the answers and said multimedia such that in said template of answers a reference to said multimedia address is made.

20-2. :

The method of claim 19 further comprising a database of functions, each function having zero or many arguments, and each function representing each of said words and each argument of said function is the type of conceptual constituent that must be used with said function, being said type of conceptual constituent an ontological category.

27. :

A method for discourse management between a human user and a plurality of third party application programs that lack a natural language interface, comprising the steps of;

a. receiving from humans a request in natural language initiating a dialog and selected from the group consisting of speech and written text

b. providing 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 the execution of said third application program

c. parsing said request through a context free grammar and converting said request to a semantic structure of conceptual constituents

d. traversing said semantic structure and pattern-matching said conceptual constituents with the states found in said state machine, such that the matching states are inactive states and the unmatched states are converted to active states

e. requesting said human for information associated to said active states

f. executing said third party application program

whereby said request is interpreted semantically,

whereby said request is associated to said third party application program and,

whereby missing information is identified from the human'"'"'s phrase necessary to execute said third party application program

28. :

The method of claim 27, further comprising the step of;

requesting information from a user when an active state is encountered and flagging information that has been fulfilled by the conceptual constituents when an inactive state is encountered.

30. :

The method of claim 27, wherein said step for requesting said human for information associated to said active states further comprises the step of;

logically comparing new conceptual constituents to the states and causing a plurality of said active states to become inactive.

31. :

The method of claim 30, wherein said step of traversing said semantic structure and pattern-matching said conceptual constituents with the states found in said state machine, such that the matching states are inactive states and the unmatched states are converted to active states, said states are dependent on one another, such that a state cannot become active, if said state depends on another state.

32. :

The method of claim 27, wherein said third party application program is only ready to be executed when all the states are inactive.

33. :

The method of claim 32, wherein the information from the conceptual constituents that is matched for each state, is passed to said third party application for execution.

34. :

The method of claim 27, further comprising the step of providing an ontological category for each rule in said context free grammar.

35. :

The method of claim 34, wherein the step for providing a plurality of state machines further comprising ontological categories, such that each ontological category labels a state and each said ontological category corresponds to the ontological categories in the rules of said context free grammar.

36. :

The method of claim 31, wherein said step of traversing said semantic structure and pattern-matching said conceptual constituents with the states found in said state machine, such that the matching states are inactive states and the unmatched states are converted to active states, said structure of conceptual constituents is arranged as a hierarchical or treelike structure and further comprises;

a plurality of sub-trees each representing a conceptual constituents.

nodes containing;

the ontological category of the conceptual constituent

the word in the phrase

super classes of the word

the children of the node

a set of synonyms for the conceptual constituent, and

the phrasal category of the conceptual constituent

and said states are labeled with an ontological category

and if a matching between states and conceptual constituents is successful if the ontological category of a state and the ontological category of a conceptual constituent match.

37. :

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 logic to analyze syntactically one type of communicative act

b. program logic responsive to said natural language phrases input and said multiplicity of context free grammars, configured to parse said natural language input with said multiplicity of context free grammars, such that only one context free grammar is used successfully for parsing one natural language phrase, and to produce a semantic structure and a Boolean indicator that indicates which said context free grammar is used successfully for parsing said natural language input

c. 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

38. :

The apparatus of claim 37, wherein said 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 when one context free grammar is used for successfully parsing said natural language phrase, no other context free grammars are utilized.