Data processing: artificial intelligence – Knowledge processing system – Knowledge representation and reasoning technique
Reexamination Certificate
2001-02-22
2004-04-13
Khatri, Anil (Department: 2121)
Data processing: artificial intelligence
Knowledge processing system
Knowledge representation and reasoning technique
C706S045000, C706S012000
Reexamination Certificate
active
06721720
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to the probabilistic diagnostics and procedures and more specifically relates to techniques and systems for estimating resource needs of Bayesian belief networks as applied to diagnostic systems.
2. Discussion of Related Art
In general, diagnostic techniques applied to a variety of problem domains evaluate particular evidence or constraints and determine an appropriate next step in the process based on probabilities associated with the particular evidence or constraints. Humans conduct such diagnosis on a regular basis in solving a variety of problems. Computing systems are often applied to resolving similar problems utilizing similar probabilistic techniques based on gathered evidence and constraints.
Troubleshooting and diagnostic “wizards” are exemplary of common automated diagnostic systems. Such wizards in computing systems usually accept input from a user indicating the nature of a problem to be resolved. Through a number of question and answer interactions with the user, the wizard narrows the possible solutions to the problem. In other words, the wizard diagnoses the problem by applying probabilistic analysis given a set of constraints supplied by the user. Troubleshooting and diagnostic wizards are frequently used to provide automated troubleshooting assistance for end-users of computing systems to enable end-users to rapidly diagnose unresolved problems without resorting to interaction with customer support representatives associated with the computing systems.
A variety of mathematical models have been applied to improve the diagnostic capability of such computing systems used for such problem diagnosis. One popular such model is often referred to as a Bayesian belief networks (“BBN”). Bayesian belief networks iteratively apply Bayes rule to infer a probable event or next step in the problem diagnosis based on evidence or constraints and associated probabilities. A Bayesian belief network is therefore often represented mathematically as a collection of nodes representing particular events or states associated with gathered evidence and arcs connecting the nodes representing probabilistic dependence between the various events represented by the nodes. By extending the representation of a Bayesian belief network with information such as cost of steps, explanations for steps and the like, BBNs can be usefully applied to troubleshooting of user problems.
Use of such BBN techniques and automated (computerized) problem diagnostic systems gives rise to a number of complexities due to the computational complexity of the BBN probability determinations. Use of a BBN technique requires substantial computational resources including CPU processing cycles and memory for computing possible states and associated probabilities. Lack of predictable available computing resources is problematic in performing BBN techniques. The computational resources consumed in applying BBN techniques has been heretofore viewed as highly unpredictable. No accurate model has been proposed to estimate the resources required for utilizing the BBN network for a particular problem resolution given a set of constraints. For this reason, known BBN diagnostic tools are limited, as a practical matter, to operation on a dedicated computational server. In other words, a single BBN diagnostic tool operating to resolve a single problem on behalf of a single user/client is permitted to consume all available resources on a single dedicated computational server.
This complexity and associated need for dedicated computing resources has diminished the utility of BBN diagnostic tool systems because they are not easily managed in a client/server computational architecture where a single BBN diagnostic server may provide services for a plurality of requesting clients. When a single computational server must be dedicated to one BBN network computation, the BBN diagnostic tool is not easily scaled in a client/server model to permit a larger number of clients to be serviced.
It is evident from the above discussion that a need exists to better characterize the computational resources required of a BBN diagnostic system to permit improved management of computational resources for BBN diagnostic tools in a client/server application architecture.
SUMMARY OF THE INVENTION
The present invention solves the above and other problems, thereby advancing the state of the useful arts, by providing a polynomial model of the computational resources required for a BBN diagnostic tool to resolve a particular constrained problem. Using such an improved characterization of BBN computational complexity, management techniques (outside the scope of the present invention) may appropriately manage the distribution of BBN diagnostic computations over one or more computational servers operating on behalf of a plurality of requesting client's. In other words the improved estimation of BBN computational resources in accordance with the present invention enables effective management of computational resources to permit better scaling of BBN server resources to service multiple clients.
Empirical data suggests that BBN diagnostic computations are both memory and CPU intensive. While CPU utilization is a well-known manageable problem, storage utilization must be carefully managed to avoid fatal errors in operation of a BBN computational models. Further empirical data shows that BBN storage requirements may be accurately estimated in accordance with polynomial computational complexity. This simply computed estimate of required resources allows well-known management techniques to more accurately distribute the load of BBN services over one or more servers to purposes of serving multiple clients.
A further advantage of the present invention is that by permitting management of multiple BBN services operable on one or more server nodes, multiple BBN models may be run in parallel on behalf of a single client request. Such parallel multiple model operation allows model matching processing. Model matching as used herein refers to the process of finding a model that best handles the problem of the user. This can be done, for example, by running a number of competing models in parallel until it becomes apparent which model is the most suitable. Running multiple models for such model matching is another benefit of managing the operation of multiple BBN model executions distributed over a network of servers.
The above, and other features, aspects and advantages of the present invention will become apparent from the following descriptions and attached drawings.
REFERENCES:
patent: 6535865 (2003-03-01), Skaaning et al.
Claus Skaanning, Acquisition and Transformation of Likelihoods to Conditional Probabilities for Bayesian Networks, Sep. 25, 1998, AAAI, Symposium on Al Equipment Maintenance, 1-17.*
Skaanning et al.; E-Decisions-on-Tap: E-Services for Decision Support; Conference Proceedings—HP-Word 2000, Philadelphia; Sep. 2000.
Skaanning et al.; Acquisition and Transformation of Liklihoods to Conditional Probabilities for Bayesian Networks; Conference Proceedings—AAAI Symposium on AI in Equipment Maintenance; Sep. 25, 1998.
Jensen et al.; The SACSO System for Troubleshooting of Printing Systems; Conference Proceedings—Scandinavian Conference of AI; Feb. 2001.
Skaanning; A Knowledge Acquisition Tool for Bayesian-Network Troubleshooters; Confrence Proceedings—UAI-2000, Stanford University; Jun. 2000.
Skaanning et al.; Printer Troubleshooting Using Bayesian Networks; Conference Proceedings—IEA/AIE-2000, New Orleans; Jun. 2000.
Skanning Claus
Wright David W.
Hewlett--Packard Development Company, L.P.
Hirl Joseph P.
LandOfFree
Methods and structure for characterization of bayesian... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and structure for characterization of bayesian..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and structure for characterization of bayesian... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3276637