Data processing: artificial intelligence – Having particular user interface
Reexamination Certificate
1998-02-03
2003-08-05
Davis, George B. (Department: 2121)
Data processing: artificial intelligence
Having particular user interface
C345S215000, C345S215000, C345S215000, C345S182000, C345S215000, C345S215000, C345S215000, C345S215000, C345S950000, C707S793000
Reexamination Certificate
active
06604090
ABSTRACT:
REFERENCE TO A “MICROFICHE APPENDIX”
Submitted herewith this present application (and on deposit in the United States Patent and Trademark Office) is a microfiche appendix comprising source code of a present embodiment of the present invention. There are 178 frames contained in 2 pages of microfiche.
BACKGROUND OF THE ART
For the purposes of the present invention, “virtual robots” (or “BOTs”) are software programs that interact and/or communicate with users (human, machine or otherwise) that take actions or make responses according to input from these users. BOTs are the subject of the co-pending and co-assigned parent application entitled “Methods for Automatically Focusing the Attention of a Virtual Robot Interacting with Users”, filed Jun. 4, 1997, Ser. No. 08/868,713, and incorporated by reference in its entirety herein. A common use of such a BOT is as an interface to a web site wherein the administrator of that site has programmed the BOT to answer simple inquiries that are typically asked by visitors to the site. The above identified application discloses a method of creating BOTs according to “scripts”—i.e. programs that are written in a very high level language that closely resembles a human natural language. These scripts embody a certain amount of information concerning the site that the administrator desires the BOT to communicate to a user during a connection session.
In such a BOT controlled by a script, it is the function of the BOT script to determine the response to any given user input. Ordinarily, a BOT script is written in such a way that, for each response it might make, it explicitly states a set of conditions (which may relate to both the input and the internal state of the BOT) that must be true in order for that response to be appropriate. Thus, for any particular input and internal BOT state, zero or more responses will be appropriate. These responses are said to “match” the input, although there is no requirement that the selection of responses is based on pattern-matching.
A BOT script can be written in such a way that at most one response will match any input. One way to achieve this is by requiring the conditions associated with the responses to be mutually exclusive, so that at most one response has a true condition for any input. Another way is to impose a fixed total ordering on any set of responses in the script that might conflict—for instance, by assigning a priority according to the order in which the responses appear in the script or by attaching explicit priority numbers to each response.
Such solutions are particularly difficult to implement in natural language systems, in which there are often a large number of rules in the script and an unbounded variety of probable inputs. If the conditions are made mutually exclusive, then the addition of a new rule may require modification of an arbitrary number of other rules. While if the conditions are kept in a fixed order, the addition of a new rule requires a complicated decision about where in the fixed order it belongs. Therefore, in designing a BOT script, it is useful to allow a particular input to be matched by more than one possible response.
If the BOT script allows more than one response to match an input, and does not provide any explicit total ordering on the possible responses, there are several ways in which the set of possible responses could be used. The BOT execution system might present all of the possible responses to the user, either in ordered or unordered form, or it might select one, or several, of the possible responses. In the case where the BOT execution system is either ordering the possible responses or selecting some subset of the responses, the execution system must have an automated way of deciding among the set of possible responses. One such mechanism is to “focus” the attention of the BOT to a particular set of conversational categories, as discussed in the above-incorporated application.
However, there are many instances where a method based purely on the context of the conversation is insufficient. For instance, consider the following two inputs that might be given to a BOT: “What is a bot?”, “What is a sales bot?”. The first input might be handled in the BOT script by a condition that checks to see whether the input starts with the word “what” and contains the word “bot”, while the second input might be handled by a condition that checks to see whether the input starts with the word “what” and contains the words “sales bot”. Clearly both conditions are true for the input “What is a sales bot?”; but (presumably) the BOT should give the answer to the second condition regardless of the context of the question. Of course, in this case, the BOT author could resolve the problem by modifying the first condition so that it checks to see whether the starts with the word “what”, contains the word “bot”, and does not contain the word “sales”, but in general it is difficult and time-consuming for the BOT author to anticipate every possible such conflict between answers, and difficult to add to the script once written. Similarly, the BOT author could resolve the problem by insuring that the second condition is always tested before the first condition, but maintaining an ordering on all the possible conditions that might be added makes the BOT authoring task considerably more difficult.
Therefore, in the case where a BOT script provides conditions under which a response is appropriate, there is a need in the art for an automatic method of selecting a response from a number of possible responses such that the BOT author does not need to make the conditions mutually exclusive nor impose a fixed ordering on the conditions.
There is also a need for this mechanism to produce appropriate responses to both context-sensitive and context-independent inputs. For example, on an input such as “Who is he?”, the context of such an input is not entirely obvious. But, other inputs such as “Who is the president of Neuromedia?”, should elicit a unique response that is less dependent on the context of the statement. Thus, this mechanism should attempt to work equally well on both types of statements. In particular, there is a need to handle the problem of ambiguity that the pronouns inject into a conversation.
In addition, there is a need for this response selection mechanism to be efficient for large BOT scripts. As most BOTs are designed to handle queries from one to many simultaneous users, real-time performance is a practical consideration for such a mechanism.
SUMMARY OF THE INVENTION
The present invention meets these aforementioned needs by providing a variety of mechanisms for automatically and efficiently selecting a response from a number of possibilities. In one aspect of the present invention, in an automated interface program designed to interact and communicate with users, said program executing actions when a category among a set of predefined categories is activated, a method is disclosed for selecting a category given a situation or user input, the steps of said method comprising:
(a) defining a list of categories activatable by said program;
(b) for an input,
(i) identifying a first set of categories activated by said input;
(ii) selecting a second set of categories from said first set of activated categories based upon a metric, said metric computed based on the conditions located within each said activated category;
(iii) executing actions associated with said second set of categories.
In one aspect of the present invention, the metric disclosed in the selecting step above is an estimate of the appropriateness of the particular response included in an activated category. This estimate is currently based on the current input and the current state of the BOT upon said input.
In one aspect, the metric is a numeric value computed for each activated category, the value being based upon the frequency of matched words, partial words, symbols and the like found in the current input with words, partial words, symbols and the like found in the conditio
Benson Scott S.
Tackett Walter A.
Davis George B.
Morrison & Foerster / LLP
Nativeminds, Inc.
LandOfFree
System and method for selecting responses to user input in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for selecting responses to user input in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for selecting responses to user input in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3126142