Data processing: artificial intelligence – Knowledge processing system – Creation or modification
Reexamination Certificate
1999-06-04
2002-07-16
Black, Thomas (Department: 2121)
Data processing: artificial intelligence
Knowledge processing system
Creation or modification
Reexamination Certificate
active
06421655
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to computer-user interaction, and more particularly to such interaction between a computer and human that might be termed a conversation, accomplished through the use of a task abstraction hierarchy in combination with methods for inferring a user's goals under uncertainty from both linguistic and nonlinguistic information, computing the most important information it should gather to resolve that uncertainty, and for making decisions about progression or backtracking in the abstraction hierarchy
BACKGROUND OF THE INVENTION
Generally, computer-user interaction has focused on the user conforming more to idiosyncrasies of the computer than vice-versa. For example, while users in non-computer interactions (such as human-human interactions) typically communicate with a combination of verbal and nonverbal signals, this is generally not done with computer-user interactions. Rather, the user is forced to input information into a computer in a manner more easily understood by the computer—such as constrained voice inputs, text input from a keyboard, pointing, movement and clicking input from a mouse, etc. As a result, this imposed unnaturalness of the computer-user interface has played a part in hampering efforts to make computers easier to use and more an intuitive part of everyday life.
Interactive dialog in conversation lays at the foundation of communication between humans, where each has distinct needs, goals, and information. Conversations are typically initiated with the intention of acquiring, sharing, or critiquing information, and to express needs or request services. In general, information gathering and decision making under uncertainty play central roles in conversation. This may be at least part of the reason why there has been difficulty in attaining more natural computer-user interactions in computer-user conversation.
This difficulty is compounded by the fact that conversation is not just an auditory mode of communication. Rather, other types of information about one party can indicate to the other party how to react in conversation. For example, someone's appearance, behavior, spatial configuration, and props (viz., carried items), may all be considered when determining how to proceed with a conversation. Generally, however, the prior art relating to computer-user interactions through conversation has not focused on non-linguistic information regarding the user. Also, most interactions with computer systems do not allow for an interactive discussion about uncertainties and for the incremental inquiry of additional information via questioning or via directing information gathering to inspect a variety of sources of information including, distinctions recognized in an automated parsing of utterances with a natural language understanding system, words and phrases spotted in utterances, and a variety of acoustical and visual cues.
There is a need, therefore, for improved conversational computer-user interactions, to provide for more intuitive and natural communication between a user and a computer. For this and other reasons, there is a need for the present invention.
SUMMARY OF THE INVENTION
The invention relates to accomplishing computer-user interaction using a task abstraction hierarchy of user goals organized into a set of distinct levels of precision for engaging in dialog about a user's goals. In one embodiment, a computer-implemented method receives or actively inquires about information regarding a user's goal (i.e., the purpose of the computer-user interaction from the user's standpoint) at a current level of the abstraction hierarchy, to assess and refine the goal. The method determines the sufficiency of the information received, for example, by performing probabilistic inference from information already gathered to assign a probability to alternate goals of the user, and of performing a value-of-information analysis to acquire new information. If the information received is insufficient, then more information is received from the user, inference is performed, and the sufficiency is again assessed, centering on a decision-analytic assessment of the probability assigned to one or more leading hypotheses about the user's goals. Depending on a decision-analytic assessment with the current information, the system can either seek to acquire more information, assume a goal at the precision represented by the current level and then progress to an analysis of more specific goals at the next level of detail in the hierarchy, or can seek confirmation of the goal from the user before making the transition to the next level of analysis. The probability of alternate goals at each level are determined in one embodiment by a Bayesian network. In that embodiment, the goal with the leading probability is used to make such decisions. If the highest probability sub-goal exceeds a progression threshold as determined by a decision analysis that considers the costs and benefits of progressing, then this sub-goal is proceeded to—that is, the current level is advanced to the succeeding level—and information analysis and acquisition is initiated again at this new level.
The use of a task abstraction hierarchy provides for advantages not found in the prior art. Decomposing the user's goals into several layers allows for guiding conversation on a path of natural convergence towards shared understanding at progressively greater detail. Multiple levels also allow for the establishment of a common ground about uncertainties at each level, and for conversation about comprehension or misunderstandings at specific levels before progressing to the next level. The information gathered can include non-linguistic information, such as visual information regarding the user, in addition to linguistic information.
Embodiments of the invention include computer-implemented methods, computer-readable media, and computerized systems of varying embodiments. Still other embodiments, advantages and aspects of the invention will become apparent by reading the following detailed description, and by reference to the drawings.
REFERENCES:
patent: 4763277 (1988-08-01), Ashford et al.
patent: 4809219 (1989-02-01), Ashford et al.
patent: 5103498 (1992-04-01), Lanier et al.
patent: 5290381 (1994-03-01), Luciw et al.
patent: 5434777 (1995-07-01), Luciw .
patent: 5477447 (1995-12-01), Luciw et al.
patent: 5608624 (1997-03-01), Luciw
patent: 5621903 (1997-04-01), Luciw et al.
patent: 5625814 (1997-04-01), Luciw
patent: 5644735 (1997-07-01), Luciw et al.
patent: 5748841 (1998-05-01), Morin et al.
patent: 5774357 (1998-06-01), Hoftberg et al.
patent: 5809499 (1998-09-01), Wong et al.
patent: 5822218 (1998-10-01), Moosa et al.
patent: 5864848 (1999-01-01), Horvitz et al.
patent: 6327581 (2001-12-01), Platt
patent: WO 98/03907 a (1998-01-01), None
Anthony Jameson, “Numerical Uncertainty Management in User and Student Modeling: An Overview of Systems and Issues” Department of Computer Science, University of Saarbrucken, Germany, (May 1996).*
Combining Agoric and Genetic Methods in Stochastic Design, Published in Nanotechnology, vol. 9, No. 3 (Sep.), pp. 274-284. Presented at The Fifth Foresight Conference on Molecular Nanotechnology, Nov. 5-8, 1997, Palo Alto, CA.*
Decision-theoretic Planning, Jim Blythe, Feb. 11, 1999.*
Morphological Tagging Based Entirely on Bayesian Inference, Christer Samuelsson, Stockholm, (1994).*
Bauer, Logic-based plan recognition for intelligent help systems, Current trends in AI planning, European workshop on planning, pp. 60-73, no date.
Raskutti, Generation and selection of likely interpretations during plan recognition in task-oriented consultation systems, User modeling and user-adapted interaction, vol. 1, No. 4, 1991, pp. 323-353.
Horvitz, Principles of Mixed-initiative user interfaces, May 15-20, 1999, ACM, pp. 159-166.
Eric Horvitz, David Heckerman, et al., Heuristic Abstraction in the Decision-Theoretic Pathfinder System, Proceedings of the Thirteenth Symposium on Computer Applications in Medica
Horvitz Eric
Paek Timothy S.
Amin & Turocy LLP
Black Thomas
Holmes Michael B.
Microsoft Corporation
LandOfFree
Computer-based representations and reasoning methods for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer-based representations and reasoning methods for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer-based representations and reasoning methods for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2851974