Gregory M. Provan

SoCS Conference 2023 Conference Paper

Using Machine Learning Classifiers in SAT Branching [Extended Abstract]

• Ruth Helen Bergin
• Marco Dalla
• Andrea Visentin
• Barry O'Sullivan
• Gregory M. Provan

The Boolean Satisfiability Problem (SAT) can be framed as a binary classification task. Recently, numerous machine and deep learning techniques have been successfully deployed to predict whether a CNF has a solution. However, these approaches do not provide a variables assignment when the instance is satisfiable and have not been used as part of SAT solvers. In this work, we investigate the possibility of using a machine-learning SAT/UNSAT classifier to assign a truth value to a variable. A heuristic solver can be created by iteratively assigning one variable to the value that leads to higher predicted satisfiability. We test our approach with and without probing features and compare it to a heuristic assignment based on the variable

ICRA Conference 2021 Conference Paper

A Novel Hybrid Approach for Fault-Tolerant Control of UAVs based on Robust Reinforcement Learning

• Yves Sohege
• Marcos Quiñones-Grueiro
• Gregory M. Provan

The control of complex autonomous systems has significantly improved in recent years and unmanned aerial vehicles (UAVs) have become popular in the research community. Although the use of UAVs is increasing, much work remains to guarantee fault- tolerant control (FTC) properties of these vehicles. Model-based controllers are the standard way to control UAVs, however obtaining models of the system and environment for every possible operating condition a UAV can experience in a real-world scenario is not feasible. Reinforcement Learning has shown promise in controlling complex systems but requires training in a simulator (requiring a model) of the system. Further, stability guarantees do not exist for learning-based controllers, which limits their large scale application in the real-world. We propose a novel hybrid FTC approach that uses a learned supervisory controller (together with low-level PID controllers) with key stability guarantees. We use a robust reinforcement learning approach to learn the supervisory control parameters and prove stability. We empirically validate our framework using trajectory-following experiments (in simulation) for a quadcopter subject to rotor faults, wind disturbances, and severe position and attitude noise.

ECAI Conference 2016 Conference Paper

A General Characterization of Model-Based Diagnosis

• Gregory M. Provan

The Model-Based Diagnosis (MBD) framework developed by Reiter has been a strong theoretical foundation for MBD, yet is limited to models that are described in terms of logical sentences. We propose a more general framework that covers a wide range of modelling languages, ranging from AI-based languages (e. g. , logic and Bayesian networks) to FDI-based languages (e. g. , linear Gaussian models). We show that a graph-theoretic basis for decomposable system models can be augmented with several languages and corresponding inference algorithms based on valuation algebras.

ECAI Conference 2016 Conference Paper

An Improved State Filter Algorithm for SIR Epidemic Forecasting

• Weipéng Huáng
• Gregory M. Provan

In epidemic modeling, state filtering is an excellent tool for enhancing the performance of traditional epidemic models. We introduce a novel state filter algorithm to further improve the performance of state-of-the-art approaches based on Susceptible-Infected-Recovered (SIR) models. The proposed algorithm merges two techniques, which are typically used separately: linear correction, as seen in the Ensemble Kalman Filter (EnKF), and resampling, as used in the Particle Filter (PF). We compare the inferential accuracy of our approach against the EnKF and the Ensemble Adjustment Kalman Filter (EAKF), using algorithms employing both an uncentered covariance matrix (UCM) and the standard column-centered covariance matrix (CCM). Our algorithm requires O(DN) more time than EnKF does, where D is the ensemble dimension and N denotes the ensemble size. We demonstrate empirically that our algorithm with UCM achieves the lowest root-mean-square-error (RMSE) and the highest correlation coefficient (CORR) amongst the selected methods, in 11 out of 14 major real-world scenarios. We show that the EnKF with UCM outperforms the EnKF with CCM, while the EAKF gains better accuracy with CCM in most scenarios.

ECAI Conference 2008 Conference Paper

An Analysis of Bayesian Network Model-Approximation Techniques

• Adamo Santana
• Gregory M. Provan

Two approaches have been used to perform approximate inference in Bayesian networks for which exact inference is infeasible: employing an approximation algorithm, or approximating the structure. In this article we compare two structure-approximation techniques, edge-deletion and approximate structure learning based on sub-sampling, in terms of relative accuracy and computational efficiency. Our empirical results indicate that edge-deletion techniques dominate the subsampling/induction strategy, in both accuracy and performance of generating the approximate network. We show, for several large Bayesian networks, how edge-deletion can create approximate networks with order-of-magnitude inference speedups and relatively little loss of accuracy.

ECAI Conference 2008 Conference Paper

Test Generation for Model-Based Diagnosis

• Gregory M. Provan

This article formalises the dual problem to model-based diagnosis (MBD), i. e. , generating tests to isolate multiple simultaneous faults. Using a standard propositional MBD framework, we first define a test of minimal size that can isolate multiple simultaneous faults of an arbitrary nature. Second, we prove complexity results for multiplefault tests of minimal size in propositional system models, showing such problems have complexity similar to those of MBD problems, i. e. , complexity at the second level of the polynomial hierarchy.

ECAI Conference 2006 Conference Paper

An Empirical Analysis of the Complexity of Model-Based Diagnosis

• Gregory M. Provan

We empirically study the computational complexity of diagnosing systems with real-world structure. We adopt the structure specified by a small-world network, which is a graphical structure that is common to a wide variety of naturally-occurring systems, ranging from biological systems, the WWW, to human-designed mechanical systems. We randomly generate a suite of digital circuit models with small-world network structure, and show that diagnosing these models is computationally hard.

UAI Conference 1997 Conference Paper

A Standard Approach for Optimizing Belief Network Inference Using Query DAGs

• Adnan Darwiche
• Gregory M. Provan

This paper proposes a novel, algorithm-independent approach to optimizing belief network inference. rather than designing optimizations on an algorithm by algorithm basis, we argue that one should use an unoptimized algorithm to generate a Q-DAG, a compiled graphical representation of the belief network, and then optimize the Q-DAG and its evaluator instead. We present a set of Q-DAG optimizations that supplant optimizations designed for traditional inference algorithms, including zero compression, network pruning and caching. We show that our Q-DAG optimizations require time linear in the Q-DAG size, and significantly simplify the process of designing algorithms for optimizing belief network inference.

ICML Conference 1996 Conference Paper

Efficient Learning of Selective Bayesian Network Classifiers

• Moninder Singh
• Gregory M. Provan

UAI Conference 1996 Conference Paper

Query DAGs: A practical paradigm for implementing belief-network inference

• Adnan Darwiche
• Gregory M. Provan

UAI Conference 1996 Conference Paper

Why is diagnosis using belief networks insensitive to imprecision in probabilities?

• Max Henrion
• Malcolm Pradhan
• Brendan Del Favero
• Kurt Huang
• Gregory M. Provan
• Paul O'Rorke

Recent research has found that diagnostic performance with Bayesian belief networks is often surprisingly insensitive to imprecision in the numerical probabilities. For example, the authors have recently completed an extensive study in which they applied random noise to the numerical probabilities in a set of belief networks for medical diagnosis, subsets of the CPCS network, a subset of the QMR (Quick Medical Reference) focused on liver and bile diseases. The diagnostic performance in terms of the average probabilities assigned to the actual diseases showed small sensitivity even to large amounts of noise. In this paper, we summarize the findings of this study and discuss possible explanations of this low sensitivity. One reason is that the criterion for performance is average probability of the true hypotheses, rather than average error in probability, which is insensitive to symmetric noise distributions. But, we show that even asymmetric, logodds-normal noise has modest effects. A second reason is that the gold-standard posterior probabilities are often near zero or one, and are little disturbed by noise.

ICML Conference 1995 Conference Paper

A Comparison of Induction Algorithms for Selective and non-Selective Bayesian Classifiers

• Moninder Singh
• Gregory M. Provan

UAI Conference 1995 Conference Paper

Abstraction in Belief Networks: The Role of Intermediate States in Diagnostic Reasoning

• Gregory M. Provan

Bayesian belief networks are bing increasingly used as a knowledge representation for diagnostic reasoning. One simple method for conducting diagnostic reasoning is to represent system faults and observations only. In this paper, we investigate how having intermediate nodes-nodes other than fault and observation nodes affects the diagnostic performance of a Bayesian belief network. We conducted a series of experiments on a set of real belief networks for medical diagnosis in liver and bile disease. We compared the effects on diagnostic performance of a two-level network consisting just of disease and finding nodes with that of a network which models intermediate pathophysiological disease states as well. We provide some theoretical evidence for differences observed between the abstracted two-level network and the full network.

UAI Conference 1994 Conference Paper

An Experimental Comparison of Numerical and Qualitative Probabilistic Reasoning

• Max Henrion
• Gregory M. Provan
• Brendan Del Favero
• Gillian Sanders

Qualitative and infinitesimal probability schemes are consistent with the axioms of probability theory, but avoid the need for precise numerical probabilities. Using qualitative probabilities could substantially reduce the effort for knowledge engineering and improve the robustness of results. We examine experimentally how well infinitesimal probabilities (the kappa-calculus of Goldszmidt and Pearl) perform a diagnostic task Ñ troubleshooting a car that will not start by comparison with a conventional numerical belief network. We found the infinitesimal scheme to be as good as the numerical scheme in identifying the true fault. The performance of the infinitesimal scheme worsens significantly for prior fault probabilities greater than 0.03. These results suggest that infinitesimal probability methods may be of substantial practical value for machine diagnosis with small prior fault probabilities.

UAI Conference 1994 Conference Paper

Knowledge Engineering for Large Belief Networks

• Malcolm Pradhan
• Gregory M. Provan
• Blackford Middleton
• Max Henrion

We present several techniques for knowledge engineering of large belief networks (BNs) based on the our experiences with a network derived from a large medical knowledge base. The noisyMAX, a generalization of the noisy-OR gate, is used to model causal in dependence in a BN with multi-valued variables. We describe the use of leak probabilities to enforce the closed-world assumption in our model. We present Netview, a visualization tool based on causal independence and the use of leak probabilities. The Netview software allows knowledge engineers to dynamically view sub-networks for knowledge engineering, and it provides version control for editing a BN. Netview generates sub-networks in which leak probabilities are dynamically updated to reflect the missing portions of the network.

UAI Conference 1993 Conference Paper

Tradeoffs in Constructing and Evaluating Temporal Influence Diagrams

• Gregory M. Provan

This paper addresses the tradeoffs which need to be considered in reasoning using probabilistic network representations, such as Influence Diagrams (IDs). In particular, we examine the tradeoffs entailed in using Temporal Influence Diagrams (TIDs) which adequately capture the temporal evolution of a dynamic system without prohibitive data and computational requirements. Three approaches for TID construction which make different tradeoffs are examined: (1) tailoring the network at each time interval to the data available (rather then just copying the original Bayes Network for all time intervals); (2) modeling the evolution of a parsimonious subset of variables (rather than all variables); and (3) model selection approaches, which seek to minimize some measure of the predictive accuracy of the model without introducing too many parameters, which might cause "overfitting" of the model. Methods of evaluating the accuracy/efficiency of the tradeoffs are proposed.

UAI Conference 1991 Conference Paper

Dynamic Network Updating Techniques for Diagnostic Reasoning

• Gregory M. Provan

A new probabilistic network construction system, DYNASTY, is proposed for diagnostic reasoning given variables whose probabilities change over time. Diagnostic reasoning is formulated as a sequential stochastic process, and is modeled using influence diagrams. Given a set O of observations, DYNASTY creates an influence diagram in order to devise the best action given O. Sensitivity analyses are conducted to determine if the best network has been created, given the uncertainty in network parameters and topology. DYNASTY uses an equivalence class approach to provide decision thresholds for the sensitivity analysis. This equivalence-class approach to diagnostic reasoning differentiates diagnoses only if the required actions are different. A set of network-topology updating algorithms are proposed for dynamically updating the network when necessary.

ECAI Conference 1990 Conference Paper

The Computational Complexity of Multiple-Context Truth Maintenance Systems

• Gregory M. Provan

UAI Conference 1990 Conference Paper

What is the most likely diagnosis?

• David Poole 0001
• Gregory M. Provan

Within diagnostic reasoning there have been a number of proposed definitions of a diagnosis, and thus of the most likely diagnosis, including most probable posterior hypothesis, most probable interpretation, most probable covering hypothesis, etc. Most of these approaches assume that the most likely diagnosis must be computed, and that a definition of what should be computed can be made a priori, independent of what the diagnosis is used for. We argue that the diagnostic problem, as currently posed, is incomplete: it does not consider how the diagnosis is to be used, or the utility associated with the treatment of the abnormalities. In this paper we analyze several well-known definitions of diagnosis, showing that the different definitions of the most likely diagnosis have different qualitative meanings, even given the same input data. We argue that the most appropriate definition of (optimal) diagnosis needs to take into account the utility of outcomes and what the diagnosis is used for.

UAI Conference 1989 Conference Paper

The Application of Dempster Shafer Theory to a Logic-Based Visual Recognition System

• Gregory M. Provan

We formulate Dempster Shafer Belief functions in terms of Propositional Logic using the implicit notion of provability underlying Dempster Shafer Theory. Given a set of propositional clauses, assigning weights to certain propositional literals enables the Belief functions to be explicitly computed using Network Reliability techniques. Also, the logical procedure corresponding to updating Belief functions using Dempster's Rule of Combination is shown. This analysis formalizes the implementation of Belief functions within an Assumption-based Truth Maintenance System (ATMS). We describe the extension of an ATMS-based visual recognition system, VICTORS, with this logical formulation of Dempster Shafer theory. Without Dempster Shafer theory, VICTORS computes all possible visual interpretations (i.e. all logical models) without determining the best interpretation(s). Incorporating Dempster Shafer theory enables optimal visual interpretations to be computed and a logical semantics to be maintained.

ECAI Conference 1988 Conference Paper

Solving Diagnostic Problems Using Extended Truth Maintenance Systems

• Gregory M. Provan

AAAI Conference 1987 Conference Paper

Efficiency Analysis of Multiple-Context TMSs in Scene Representation

• Gregory M. Provan

Multiple possible solutions can arise in many domains, such as scene interpretation and speech recognition. This paper examines the eficiency of multiple-context TMSs, such as the ATMS, in solving a scene representation problem which we call the Vision Constraint Recognition problem. The ATMS has been claimed to be quite eficient for solving problems with multiple possible solutions, even for problems with large databases. However, we present evidence that for large databases with multiple possible solutions (which we argue occur frequently in practice), such multiple-context TMSs can be very inefficient. We present a class of problems for which using a multiple-context TMS is both intrinsically interesting and ideal, but which will be computationally infeasible because of the exponential size of the database which the TMS must explore. To circumvent such infeasiblity, appropriate control must be exerted by the problem solver.