David C. Wilkins

AIJ Journal 2006 Journal Article

Controlled generation of hard and easy Bayesian networks: Impact on maximal clique size in tree clustering

• Ole J. Mengshoel
• David C. Wilkins
• Dan Roth

This article presents and analyzes algorithms that systematically generate random Bayesian networks of varying difficulty levels, with respect to inference using tree clustering. The results are relevant to research on efficient Bayesian network inference, such as computing a most probable explanation or belief updating, since they allow controlled experimentation to determine the impact of improvements to inference algorithms. The results are also relevant to research on machine learning of Bayesian networks, since they support controlled generation of a large number of data sets at a given difficulty level. Our generation algorithms, called BPART and MPART, support controlled but random construction of bipartite and multipartite Bayesian networks. The Bayesian network parameters that we vary are the total number of nodes, degree of connectivity, the ratio of the number of non-root nodes to the number of root nodes, regularity of the underlying graph, and characteristics of the conditional probability tables. The main dependent parameter is the size of the maximal clique as generated by tree clustering. This article presents extensive empirical analysis using the Hugin tree clustering approach as well as theoretical analysis related to the random generation of Bayesian networks using BPART and MPART.

ICML Conference 2005 Conference Paper

Learning strategies for story comprehension: a reinforcement learning approach

• Eugene Grois
• David C. Wilkins

AIJ Journal 2003 Journal Article

Qualitative simulation of temporal concurrent processes using Time Interval Petri Nets

• Vadim Bulitko
• David C. Wilkins

This paper presents a formalism called Time Interval Petri Nets (TIPNs), which are designed to support a qualitative simulation of temporal concurrent processes. One of the key features of TIPNs is a uniform use of time intervals throughout the model. This enables a natural and efficient representation of temporal uncertainty in inputs, outputs, and intermediate states of the qualitative simulation. This is required because the exact time of key events, such as the start time of a fire crisis, is typically not known with certainty. Likewise, output conclusions of the qualitative simulation include earliest time and guaranteed time of key events that can be used by a decision maker to select the most appropriate action. Results are described of a TIPN-based qualitative simulator constructed in the domain of ship damage control. The simulator was created to replace an existing quantitative simulator which was too slow to support envisionment-based real-time decision making in this domain. The experimental results showed a speedup of four to five orders of magnitude which enables hyper-real time qualitative prediction of consequences of multiple competing actions. An automated shipboard damage control decision-making system incorporating a TIPN-based qualitative simulator achieved a 318% improvement over human subject matter experts in a large-scale simulated exercise of over 500 scenarios.

TIME Conference 1997 Conference Paper

Temporal Control Structures in Expert Critiquing Systems

• Surya Ramachandran
• David C. Wilkins

Critiquing in time critical and resource constrained domains requires special control structures that allow the expert critiquing system to compare user actions with that of its own. This is necessitated by the fact that the priorities of actions in such domains change over time and the system needs to be robust enough to reflect this in its critiques. This paper describes a model of expert critiquing where the use of blackboard architectures, temporal control structures and data manipulation and differential critiquing are effectively combined to tackle this issue. The proof-of-principal critiquing domain is novice experts training in the area of Ship Damage Control.

AIJ Journal 1994 Journal Article

The refinement of probabilistic rule sets: Sociopathic interactions

• David C. Wilkins
• Yong Ma

Probabilistic rules in a classification expert system can result in a sociopathic knowledge base, as a consequence of the assumption of conditional independence between observations and rule modularity. A sociopathic knowledge base has the property that all the rules are individually judged to be correct rules, yet a subset of the knowledge base gives better classification accuracy than the original knowledge base, independent of the amount of computational resources that are available. This paper describes how sociopathic interactions cause rule induction and refinement methods to converge to local optima with respect to maximizing classification accuracy. The problem of optimally refining sociopathic knowledge bases is modeled as a bipartite graph minimization problem and shown to be NP-hard. A heuristic rule refinement algorithm for sociopathic reduction, called SOCIO-REDUCER, is presented. Experimental results in a medical diagnosis domain show that it can reduce the diagnosis error rate by 10. 5%.

AAAI Conference 1988 Conference Paper

Knowledge Base Refinement Using Apprenticeship Learning Techniques

• David C. Wilkins

This paper describes how apprenticeship learning techniques can be used to refine the knowledge base of an expert system for heuristic classification problems. The described method is an alternative to the long-standing practice of creating such knowledge bases via induction from examples. The form of apprenticeship learning discussed in this paper is a form of learning by watching, in which learning occurs by completing failed explanations of human problem-solving actions. An apprenticeship is the most powerful method that human experts use to refine their expertise in knowledge-intensive domains such as medicine; this motivates giving such capabilities to an expert system. A major accomplishment in this work is showing how an explicit representation of the strategy knowledge to solve a general problem class, such as diagnosis, can provide a basis for learning the knowledge that is specific to a particular domain, such as medicine.

AAAI Conference 1986 Conference Paper

On Debugging Rule Sets When Reasoning Under Uncertainty

• David C. Wilkins

Heuristic inference rules with a measure of strength less than certaint, y have an unusual property: better individual rules do not necessarily lead to a better overall rule set. All less-than-certain rules contribute evidence towards erroneous conclusions for some problem instances, and the distribution of these erroneous conclusions over the instances is not necessarily related to individual rule quality. This has important consequences for automatic machine learning of rules, since rule selection is usually based on measures of quality of individual rules. In this paper, we explain why the most obvious and intuitively reasonable solut, ion to this problem, incremental modification and deletion of rules responsible for wrong conclusions a la Teiresias, is not always appropriate. In our experience, it usually fails to converge to an optimal set of rules. Given a set of heuristic rules, we explain why the the best rule set should be considered to be the element of the power set of rules that yields a global minimum error with respect to generating erroneous positive and negative conclusions. This selection process is modeled as a bipartite graph minimization problem and shown to be NP-complete. A solution method is described, the Antidote Algorithm, that performs a model-directed search of the rule space, On an example from medical diagnosis, the Antidote Algorithm significantly reduced the number of misdiagnoses when applied to a rule set. generated from 104 training instances.