Data processing: artificial intelligence – Knowledge processing system – Knowledge representation and reasoning technique
Reexamination Certificate
2000-08-22
2004-11-16
Patel, Ramesh (Department: 2121)
Data processing: artificial intelligence
Knowledge processing system
Knowledge representation and reasoning technique
C706S060000
Reexamination Certificate
active
06820072
ABSTRACT:
BACKGROUND
The present invention pertains to support of products and pertains particularly to validation of probabilistic troubleshooters and diagnostic systems.
Currently, it is highly expensive for manufacturers to diagnose the systems of their customers. Automation of this process has been attempted using probabilistic troubleshooters and other diagnostic systems. Some of these systems are based on Bayesian networks.
One troubleshooter based on Bayesian networks is described by Heckerman, D., Breese, J., and Rommelse, K. (1995), Decision-theoretic Troubleshooting,
Communications of the ACM
, 38:49-57 (herein “Heckerman et al. 1995”).
In scientific literature Bayesian networks are referred to by various names: Bayes nets, causal probabilistic networks, Bayesian belief networks or simply belief networks. Loosely defined Bayesian networks are a concise (acyclic) graphical structure for modeling probabilistic relationships among discrete random variables. Bayesian networks are used to efficiently model problem domains containing uncertainty in some manner and therein lies their utility. Since they can be easily modeled on a computer, they are the subject of increasing interest and use in automated decision-support systems, whether for medical diagnosis, automated automotive troubleshooting, economic or stock market forecasting or in other areas as mundane as predicting a computer user's likely requirements.
In general, a Bayesian network consists of a set of nodes representing discrete-valued variables connected by arcs representing the causal dependencies between the nodes. A set of conditional probability tables, one for each node, defines the dependency between the nodes and its parents. And, nodes without parents, sometimes called source nodes, have associated therewith a prior marginal probability table. For specific applications the data for the probability tables for all other nodes are provided by what is termed domain experts in whatever field is being modeled. This involves assigning prior probabilities for all nodes without parents, and conditional probabilities for all nodes with parents. In diagnostic Bayesian networks nodes can represent causes, or outcomes of actions and questions. In very large diagnostic Bayesian networks, most of the events are very rare with probabilities in the range of 0.001 to 0.000001. But, since a primary goal of a computer decision support system is to provide decisions as accurate as is possible, it is imperative that the domain experts provide probabilistic information that is highly reliable and their best estimate of the situation.
Bayesian networks provide a way to model problem areas using probability theory. The Bayesian network representation of a problem can be used to provide information on a subset of variables given information on others. A Bayesian network consists of a set of variables (nodes) and a set of directed edges (connections between variables). Each variable has a set of mutually exclusive states. The variables together with the directed edges form a directed acyclic graph (DAG). For each variable v with parents w1, . . . , w
n
, there is defined a conditional probability table P(v|w
1
, . . . , w
n
). Obviously, if v has no parents, this table reduces to the marginal probability P(v).
Bayesian networks have been used in many application domains with uncertainty, such as medical diagnosis, pedigree analysis, planning, debt detection, bottleneck detection, etc. However, one of the major application areas has been diagnosis. Diagnosis (i.e., underlying factors that cause diseases/malfunctions that again cause symptoms) lends itself nicely to the modeling techniques of Bayesian networks.
In the prior art, validation of probabilistic troubleshooters and diagnostic systems has been highly unstructured and time-consuming. Basically, a domain expert tests a new system by experimenting. The domain expert would try out different sequences with the system by answering suggested steps in different ways. The domain expert tracks coverage of the possible cases. This is very difficult because generally there are thousands of possible cases. The result is the domain expert's validation either covers only a very small part of the possible cases, or in order to cover a larger number of cases, validation is extremely time-consuming.
Currently no software testing programs exist for validation of probabilistic troubleshooters and diagnostic systems. The technique used by software testing programs to test functional software (known as an application) is as follows. In a recording phase, an application is monitored and all interactions and responses are saved into “cases”. After an application is possibly modified, the cases are tested during a testing phase. In the testing phase the interactions are regenerated on the new (possibly modified) application, and the responses are compared to the recorded responses in the case. If there is a deviation, the case is labeled a failure. If the response is identical on the entire case, the case is labeled a success. Software testing programs generally also record statistics on successes, failures, and allow a user to trace failures. Some software testers also can generate random interactions with the application (so the testing program generates the interactions).
SUMMARY OF THE INVENTION
In accordance with a preferred embodiment of the present invention, a probabilistic diagnostic system is validated. A diagnostic sequence is generated from a diagnostic model. The diagnostic sequence is evaluated to determine whether the diagnostic sequence provides an acceptable resolution to a problem. This is repeated for additional diagnostic sequences from the diagnostic model. It is determined whether at least a predetermined number of diagnostic sequences provide an acceptable resolution. When it is determined that a the predetermined number of diagnostic sequences provide an acceptable resolution, the diagnostic model is accepted.
In the preferred embodiment, when it is determined that not at least the predetermined number of diagnostic sequences provide an acceptable resolution, a new diagnostic model is generated. Diagnostic sequences previously evaluated for the diagnostic model are checked to see whether these diagnostic sequences provide acceptable resolutions in the new diagnostic model. When it is determined that not at least the predetermined number of diagnostic sequences provide an acceptable resolution, a new diagnostic model is generated. For diagnostic sequences previously evaluated for the diagnostic model, a check is made to see whether these diagnostic sequences provide acceptable resolutions in the new diagnostic model. When it is determined that the diagnostic sequences provide acceptable resolutions in the new diagnostic model, additional diagnostic sequences are tested to determine whether, for the new diagnostic model, at least the predetermined number of diagnostic sequences provide an acceptable resolution. When it is determined that the diagnostic sequences already checked do not provide acceptable resolutions in the new diagnostic model a new revised diagnostic model is generated.
In the preferred embodiment, a case generator comprising a first diagnostic engine and a second diagnostic engine are used to generate the diagnostic sequences. The second diagnostic engine selects a cause. The first diagnostic engine suggests a best next step. The first diagnostic engine does not know the cause selected by the second diagnostic engine. the second diagnostic engine selects an answer to the best next step. The answer is consistent with the cause previously selected. This is repeated until the problem is resolved or until the first diagnostic engine is unable to suggest a best next step.
The second diagnostic engine selects each cause using a random s process. Alternatively, cases can be generated by traversing all possible sequences and selecting those that fulfills one of the three criteria: length of diagnostic sequence, cost of performing diagnostic sequence, and
Jensen Finn Verner
Skaanning Claus
Suermondt Henri Jacques
Hewlett--Packard Development Company, L.P.
Holmes Michael B.
Patel Ramesh
LandOfFree
Validation of probabilistic troubleshooters and diagnostic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Validation of probabilistic troubleshooters and diagnostic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Validation of probabilistic troubleshooters and diagnostic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3301540