Gregory Provan

Professor
Computer Science
Wgb 1-71
University College Cork
Cork
Ireland

T: +353 21 4205928
E: g.provan@cs.ucc.ie
Web Page
Gregory Provan received his BSE from Princeton University, USA, his MSc from Stanford University, USA, and his DPhil from University of Oxford, UK. He is currently Director of the Complex Systems Lab (http://www.cs.ucc.ie/ccsl/) at UCC. Prior to joining UCC he was on faculty at the University of Pennsylvania, USA, and spent over 10 years in industrial research.

His interests are in complex systems (design, analysis and control), diagnostics, algorithm design, and bioinformatics. His current research focuses on modelling and analysis of sustainable energy systems, and co-design of embedded systems.

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.


Book Chapters

 YearPublication
(2008)'Generalizing Global Constraints based on Network Flows'
I. Razgon, B. O¿Sullivan and G. Provan, ; (2008) 'Generalizing Global Constraints based on Network Flows' In: Advances in Constraints. Springer LNAI 5129: Springer LNAI 5129. [No details]

Peer Reviewed Journals

 YearPublication
(2009)'Integrated stoichiometric, thermodynamic and kinetic modelling of steady state metabolism¿'
R. Fleming, I. Thiele, G. Provan, B. Palsson, H.Nasheuer; (2009) 'Integrated stoichiometric, thermodynamic and kinetic modelling of steady state metabolism¿' [Details]
(2009)'A Benchmark Diagnostic Model Generation System'
J. Wang and G. Provan; (2009) 'A Benchmark Diagnostic Model Generation System' [Details]

Conference Publications

 YearPublication
(2009)Proceedings of the International Conference on Complex Sciences: Theory and Applications (Complex-2009), Shanghai, China
Jun Wang and Gregory Provan; (2009) A Comparative Analysis of Specific Spatial Network Topological Models , 23-25 February, 2009 Proceedings of the International Conference on Complex Sciences: Theory and Applications (Complex-2009), Shanghai, China [Details]
(2009)Proceedings of the International Conference on Complex Sciences: Theory and Applications (Complex-2009), Shanghai, China
Jun Wang and Gregory Provan; (2009) Characterizing the Structural Complexity of Real-World Complex Networks , 23-25 February, 2009 Proceedings of the International Conference on Complex Sciences: Theory and Applications (Complex-2009), Shanghai, China [Details]
(2009)Proc. Safeprocess-2009
Gregory Provan; (2009) Approximating All Most Preferred Diagnoses using Greedy Algorithms, Barcelona, Spain, 30 June ¿ 3 July, 2009 Proc. Safeprocess-2009 [Details]
(2008)Proc. Conf. on Modeling, Identification and Control
Jun Wang and Gregory Provan; (2008) Automated Model Generation for Complex Systems, Innsbruck, Austria, February 2008 Proc. Conf. on Modeling, Identification and Control [Details]
(2008)Proc. Int'l Conference on Prognostics and Health Monitoring, Denver, USA
Alexander Feldman, Gregory Provan, and Arjan van Gemund; (2008) A Framework and Algorithm for Model-Based Active Testing, 6-9 October 2008 Proc. Int'l Conference on Prognostics and Health Monitoring, Denver, USA [Details]
(2008)Proc. European Conference on AI
A. Santana and Gregory Provan; (2008) An Analysis of Bayesian Network Model-Approximation Techniques , July 22-25 2008 Proc. European Conference on AI [Details]
(2008)Proc. European Conference on AI
Gregory Provan,; (2008) Test Generation for Model-Based Diagnosis , July 22-25 2008 Proc. European Conference on AI [Details]
(2008)Proc. AAAI
Jun Wang and Gregory Provan; (2008) Generating Application-Specific Benchmark Models for Complex Systems, July 2008 Proc. AAAI [Details]
(2008)Proc. AAAI
Alexander Feldman, Gregory Provan, and Arjan van Gemund; (2008) Computing Observation Vectors for Max-Fault-Min-Cardinality Diagnoses, July 2008 Proc. AAAI [Details]
(2008)Proc. AAAI
Alexander Feldman, Gregory Provan, and Arjan van Gemund; (2008) Computing Minimal Diagnoses by Greedy Stochastic Search, July 2008 Proc. AAAI [Details]
(2008)Proc. Int¿l Symposium on AI in Mathematics
G. Provan; (2008) Approximation Techniques for Space-Efficient Compilation in Abductive Inference, Ft. Lauderdale, USA, January 2008 Proc. Int¿l Symposium on AI in Mathematics [Details]
(2008)Proc. RECOMB Conference on Systems Biology
R.M.T. Fleming, I. Thiele, G. Provan, B. Palsson, H.P. Nasheuer; (2008) Integrated stoichiometric, thermodynamic and kinetic modelling of steady state metabolism¿, San Diego, November 30 - December 1, 2007 Proc. RECOMB Conference on Systems Biology [Details]
(2008)Proc. Itnl. Workshop on Principles of Diagnosis, Blue Mountain, Australia
Alexander Feldman, Gregory Provan, and Arjan van Gemund; (2008) Model-Based Active Testing, 22-23 September 2008 Proc. Itnl. Workshop on Principles of Diagnosis, Blue Mountain, Australia [Details]
(2008)Proc. IFAC World Congress
G. Provan; (2008) Embedded Diagnosis using Approximate Classifiers, Seoul, Korea, July 2008 Proc. IFAC World Congress [Details]
(2008)Proc. AAAI
A. Venturini and G. Provan; (2008) Incremental Algorithms for Approximate Compilation¿, July 2008 Proc. AAAI [Details]
(2008)Proc. 20th IEEE Int'l Conference on Tools with Artificial Intelligence, Dayton, USA
M. Razgon and G. Provan; (2008) Adding Flexibility to Russian Doll Search¿, 3-5 Nov. 2008 Proc. 20th IEEE Int'l Conference on Tools with Artificial Intelligence, Dayton, USA [Details]
(2007)Proc. International Joint Conference on AI (IJCAI)
[G. Provan and J. Wang; (2007) Evaluating the Adequacy of Automated Benchmark Model Generators for Model-Based Diagnostic Inference, Hyderabad, India, January 2007 Proc. International Joint Conference on AI (IJCAI) [Details]
(2007)Proc. European Conference on Complex Systems
Jun Wang and Gregory Provan; (2007) On the Role of Motifs and Functional Blocks in Complex Systems Proc. European Conference on Complex Systems [Details]
(2006)Proc. Conference of American Association of AI (AAAI)
Barry O¿Sullivan and Gregory Provan; (2006) Approximate Compilation for Embedded Model-based Reasoning Proc. Conference of American Association of AI (AAAI) [Details]
(2006)Proc. Conference on Information Processing and Management of Uncertainty
G. Provan; (2006) A Model-Based Framework for Stochastic Diagnosability Proc. Conference on Information Processing and Management of Uncertainty [Details]
(2006)Proc. American Control Conference
G. Provan; (2006) A Bayesian Network Framework for Stochastic Discrete-Event Control Proc. American Control Conference [Details]
(2006)Proc. European Conference on AI
G. Provan; (2006) An Empirical Analysis of the Complexity of Model-Based Diagnosis Proc. European Conference on AI [Details]
(2004)Proc. Itnl. Conf. On Principles of Knowledge Representation
G. Provan. ; (2004) Inferential Complexity Control for Model-Based Abduction Proc. Itnl. Conf. On Principles of Knowledge Representation [Details]

Conference Contributions

 YearPublication
(2008)Automated Model Generation for Complex Systems,
G. Provan; (2008) Automated Model Generation for Complex Systems. [Oral Presentation], Automated Model Generation for Complex Systems, Conf. on Modeling, Identification and Control, Innsbruck, Austria , 12-FEB-08 - 12-FEB-08
(2008)Complex Systems: Inference and Modeling,
G. Provan; (2008) Complex Systems: Inference and Modeling. [Oral Presentation], Complex Systems: Inference and Modeling, Henan University (China); Science Seminar Series , 10-JAN-08 - 10-JAN-08
(2008)Complex Systems: An Overview,
G. Provan; (2008) Complex Systems: An Overview. [Oral Presentation], Complex Systems: An Overview, Guilin Institute of Electronic Technology (GUET); , 14-JAN-08 - 14-JAN-08
(2008)Approximation Techniques for Space-Efficient Compilation,
G. Provan; (2008) Approximation Techniques for Space-Efficient Compilation. [Oral Presentation], Approximation Techniques for Space-Efficient Compilation, TU Delft Computer Science; Seminar Series , 31-JAN-08 - 31-JAN-08
(2008)Intelligent Building Systems Modelling,
G. Provan; (2008) Intelligent Building Systems Modelling. [Oral Presentation], Intelligent Building Systems Modelling, MIT, Boston, USA; , 26-JUN-08 - 26-JAN-08
(2008)Approximation Techniques for Space-Efficient Compilation in Abductive Inference,
G. Provan; (2008) Approximation Techniques for Space-Efficient Compilation in Abductive Inference. [Oral Presentation], Approximation Techniques for Space-Efficient Compilation in Abductive Inference, Int¿l Symposium on AI in Mathematics, Ft. Lauderdale, FL, USA , 02-JAN-08 - 02-JAN-08
(2008)An Analysis of Bayesian Network Model-Approximation Techniques,
G. Provan; (2008) An Analysis of Bayesian Network Model-Approximation Techniques. [Oral Presentation], An Analysis of Bayesian Network Model-Approximation Techniques, European Conference on AI, Patras, Greece , 23-JUL-08 - 23-JUL-08
(2008)On Learning Compressed Diagnosis Classifiers,
G. Provan; (2008) On Learning Compressed Diagnosis Classifiers. [Oral Presentation], On Learning Compressed Diagnosis Classifiers, IFAC World Congress, Seoul, Korea , 08-JUL-08 - 08-JUL-08
(2008)Computing Minimal Diagnoses by Greedy Stochastic Search,
G. Provan; (2008) Computing Minimal Diagnoses by Greedy Stochastic Search. [Oral Presentation], Computing Minimal Diagnoses by Greedy Stochastic Search, Conference of the American Association of AI, Chicago, USA , 15-JUL-08 - 15-JUL-08
(2008)Incremental Algorithms for Approximate Compilation,
G. Provan; (2008) Incremental Algorithms for Approximate Compilation. [Oral Presentation], Incremental Algorithms for Approximate Compilation, Conference of the American Association of AI, Chicago, USA , 16-JUL-08 - 16-JUL-08
(2008)Computing Observation Vectors for Max-Fault-Min-Cardinality Diagnoses,
G. Provan; (2008) Computing Observation Vectors for Max-Fault-Min-Cardinality Diagnoses. [Oral Presentation], Computing Observation Vectors for Max-Fault-Min-Cardinality Diagnoses, Conference of the American Association of AI, Chicago, USA , 15-JUL-08 - 15-JUL-08
(2008)Generating Application-Specific Benchmark Models for Complex Systems,
G. Provan; (2008) Generating Application-Specific Benchmark Models for Complex Systems. [Oral Presentation], Generating Application-Specific Benchmark Models for Complex Systems, Conference of the American Association of AI, Chicago, USA , 17-JUL-08 - 17-JUL-08
(2008)Test Generation for Model-Based Diagnosis,
G. Provan; (2008) Test Generation for Model-Based Diagnosis. [Oral Presentation], Test Generation for Model-Based Diagnosis, European Conference on AI, Patras, Greece , 22-JUL-08 - 22-JUL-08
(2006)Approximation Algorithms for Model-Based Diagnostics,
G. Provan; (2006) Approximation Algorithms for Model-Based Diagnostics. [Oral Presentation], Approximation Algorithms for Model-Based Diagnostics, Technical University Delft, Delft, Holland , 06-JAN-06 - 06-JAN-06

Honours and Awards

 YearTitleAwarding Body
2008Best Paper IEEE Prognostics and Health Management Conference Committee

Employment

 EmployerPositionFrom / To
UCC Professor Computer science01-JUL-04 / 01-JUL-10
Rockwell Scientific Company Technical Manager01-MAY-94 / 01-JUN-04
Institute for Decision Systems Research Deputy Director01-JAN-94 / 01-MAR-95
University of Pennsylvania Assistant Professor01-JUN-90 / 01-DEC-93

Education

 YearInstituionQualificationSubject
1990Oxford PHDPhD phil
1984Stanford MScMSc
1982Princeton BSCBSE

Reviews

 JournalRole
Artificial Intelligence Referee
Ieee Systems Man And Cybernetics, Part A Editor
J. Ai Research Referee
Ieee Trans. Smc Referee

algorithm design

performance analysis of networks

modeling and analysis of complex systems and networks

artificial intelligence

software development

embedded systems

machine learning

Ma JiDoctoral DegreeCo-Supervised