University College Cork

1. Home
2. Computer Science
3. People
4. Gregory Provan

Biography

Research Interests

My research has focused on the design and analysis of complex systems. A complex system (or system-of-systems), such as the internet, an electric power-grid or a bio-/eco-system, consists of a collection of interacting sub-systems. One of the key issues in understanding and analysing complex systems is modelling their behaviour, as well as developing methods for performing various types of inference on these systems, such as diagnosis or control. Our work over the past year has developed more efficient inference algorithms and extended previously-developed frameworks for the modelling, analysis and control of complex systems.

We have developed several techniques for overcoming the intractability associated with performing inference on large complex systems. Our techniques focus on computing approximate solutions in an efficient manner. In one approach, we have developed methods for quickly diagnosing large complex systems by calculating only the most-likely faults; this has led to order-or-magnitude speedups in inference time (or embedded model size) with the loss of only highly-unlikely faults. This approach can enable faults in systems like complex hardware systems or electric power-grids to be computed quickly, as opposed to requiring hours for exact approaches of similar fidelity. In another approach, we have adopted stochastic inference algorithms that significantly extend the size and complexity of systems that can be analysed.

Our research has also led to methods for characterising the properties of a complex system based on the system structure and function. Using such a characterisation, we have developed a system for automatically generating benchmark models for complex systems of pre-specified size and properties; this auto-generation tool has proven very useful in real-world domains where there are insufficient real-world models to test of modelling approaches and new algorithms, such as diagnosis, control and configuration applications.

We have developed a framework for modelling complex systems that describes such systems as a set of constraints defined by system topology and system functionality. This framework is general, in that it covers a broad range of complex systems, and it also has an associated set of algorithms that can be used for performing inference on such systems. We have applied this framework to modelling heating and lighting in intelligent building systems, where we have extended hybrid-systems models with decision-theoretic models of occupant preferences.

TOP THREE RESEARCH OUTPUTS
We have addressed three key problems, which are noted below, along with the most important publication describing the research output.
[1] Embedded inference algorithms for several classes of complex systems [A. Venturini and G. Provan. Proc. AAAI, "Incremental Algorithms for Approximate Compilation", July 2008.]

This work has addressed the need for reducing the size and complexity of code that is embedded in distributed processors. We have demonstrated that such code-compression is possible for several representations, including the languages DNNF, OBDD, prime implicants, Decision-Tree Models, and Bayesian-Network models. For such embedded model-based languages, we have improved a range of approximation algorithms that successfully trade off model size (or inference complexity) for completeness. Given a system f and a preference relation &#61546; over f, this approach can generate a set of models 10-1000X smaller than the complete set of models, such that we trade off only 5-15% of the least-important models. This advance now makes it possible to embed significantly larger system descriptions in real-world applications, given target languages like Decomposable Negation Normal Form (DNNF) and prime implicants. For the target language of Bayesian Networks, we have developed approximation techniques that can embed space- and computationally-efficient networks with little loss of inference accuracy. Given a complete Bayesian Network B with evidence e, this approach can generate an approximate network B that can compute posterior probabilities for target variables, e.g., PB (V|e), 5-1000X times faster than computing PB(V|e) in the full network, with small loss of accuracy, i.e., |PB(V|e) - PB(V|e)|< &#61540; for &#61540; small.

[B] Stochastic Model-Based Diagnosis algorithms for a range of complex systems models.[A. Feldman, G. Provan and A. van Gemund. J. AI Research, 2009, to appear, "Approximate Model-Based Diagnosis Using Greedy Stochastic Search]

This work has developed a number of approximation techniques for model-based diagnostics which are orders of magnitude faster than any competing technique. In the area of model-based diagnosis, we have co-developed a greedy stochastic search algorithm, SAFARI, which yields a 10-1000X speedup. This algorithm offers potentially the largest improvement in diagnosis algorithms in the past 10 years. The greedy stochastic search algorithm, together with the subsequent extensions, was developed jointly with colleagues at the Technical University of Delft. In the area of Test-Vector Generation, we have adapted SAFARI to develop an algorithm for computing diagnostic test-vectors that can compute test-vectors for maximum-cardinality faults more efficiently than any existing approach. In the area of Sequential Diagnosis, we have extended the stochastic test-vector approach to enable a form of sequential diagnosis, called active testing, which has been shown to be faster than existing approaches on benchmark problems. For all these techniques, we have demonstrated theoretically and empirically (on a range of circuit benchmark models) the conditions under which stochastic diagnosis can yield order-of-magnitude reductions in time for diagnostic inference.

[C] A system for automatically generating benchmark models for complex systems. [J. Wang and G. Provan. IEEE Transactions on Systems, Man and Cybernetics-Part A (SMCA), 2009, to appear, "A Benchmark Diagnostic Model Generation System]
This work has developed a system for automatically generating benchmark models for complex systems, in order to enable the comparison of modelling approaches and algorithms for domains with few real-world models. The lack of real-world benchmark models is a significant hindrance in the many areas with few real-world models, such as diagnosis, in that it prevents the comparison of modelling approaches and algorithms within realistic application settings.
In our work we have used machine-learning approach to classify domain parameters, which can be used to enhance model-generation by producing models more closely matching real-world models than can previous automatic generators. This work has demonstrated the auto-generation algorithm on several different domains, e.g., circuit benchmarks, brain networks, and process-control systems. In addition, we can tailor the auto-generation methodology to optimise model structure for several functional properties, e.g., diagnosability (i.e., the ability to isolate faults in the system). We have compared several current model auto-generation algorithms to proposed algorithm, to compare the relative merits of each approach. We have made the auto-generation software available to other complex-systems researchers.

Research Grants

Publications

Peer Reviewed Journals

Book Chapters

Conference Publications

Professional Activities

Honours and Awards

Conference Contributions

Employment

Education

Journal Activities

Teaching Activities

Teaching Interests

Recent Postgraduates

Current Postgraduate Students