Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-26T08:35:11.382Z Has data issue: false hasContentIssue false
  • English
  • Français

Learning Qualitative Differential Equation models: a survey of algorithms and applications

Published online by Cambridge University Press:  01 March 2010

Wei Pang  and
George M. Coghill
Wei Pang*
Affiliation:
Computational Intelligence Group, College of Computer Science and Technology, Jilin University, Changchun, P.R. China Department of Computing Science, School of Natural & Computing Sciences, University of Aberdeen, Aberdeen, UK
George M. Coghill*
Affiliation:
Department of Computing Science, School of Natural & Computing Sciences, University of Aberdeen, Aberdeen, UK
*
e-mail: [email protected], [email protected], [email protected]
e-mail: [email protected], [email protected], [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Over the last two decades, qualitative reasoning (QR) has become an important domain in Artificial Intelligence. QDE (Qualitative Differential Equation) model learning (QML), as a branch of QR, has also received an increasing amount of attention; many systems have been proposed to solve various significant problems in this field. QML has been applied to a wide range of fields, including physics, biology and medical science. In this paper, we first identify the scope of this review by distinguishing QML from other QML systems, and then review all the noteworthy QML systems within this scope. The applications of QML in several application domains are also introduced briefly. Finally, the future directions of QML are explored from different perspectives.

Type
Articles
Information
The Knowledge Engineering Review , Volume 25 , Issue 1 , March 2010 , pp. 69 - 107
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abe, S. 1993. A qualitative system idenditification method. In Proceedings of the Seventh International Workshop on Qualitative Reasoning about Physical Systems, 1–10. Orcas Island, Washington.Google Scholar
Alur, R., Courcoubetis, C., Halbwachs, N., Henzinger, T., Ho, P., Nicolin, X., Olivero, A., Sifakis, J. 2000. Discrete abstractions of hybrid systems. In Proceedings of the IEEE, 88, 971–984. Pennsylvania University, Philadelphia, PA. IEEE Press.CrossRefGoogle Scholar
Bellazzi, R., Ironi, L., Guglielmann, R., Stefanelli, M. 1998. Qualitative models and fuzzy systems: an integrated approach for learning from data. Artificial Intelligence in Medicine 14, 5–28.CrossRefGoogle ScholarPubMed
Bergadano, F., Gunetti, D. 1996. Inductive Logic Programming From Machine Learning to Software Engineering. MIT Press.Google Scholar
Bhaskar, R., Nigam, A. 1990. Qualitative physics using dimensional analysis. Artificial Intelligence 45, 73–111.CrossRefGoogle Scholar
Blackman, R., Tukey, J. 1958. The measurement of Power Spectra. Dover Publications Inc.Google Scholar
Bohte, Z. 1991. Numerical Method. The Society of Mathematicaians, Physicists and Astronomers of Slovenia.Google Scholar
Bradley, E., Easley, M., Stolle, R. 2001. Reasoning about nonlinear system identification. Artificial Intelligence 133, 139–188.CrossRefGoogle Scholar
Bradley, E., Stolle, R. 1996. Automatic construction of accurate models of physical systems. Annals of Mathematics and Artificial Intelligence 17, 1–28.CrossRefGoogle Scholar
Bratko, I., Muggleton, S., Varšek, A. 1991. Learning qualitative models of dynamic systems. In Proceedings of the 8th International Workshop on Machine Learning, Birnbaum, L. and Collins, G. (eds). Morgan Kaufmann.Google Scholar
Bratko, I., Šuc, D. 2003. Learning qualitative models. AI Magazine 240(4), 107–119.Google Scholar
Bruce, A. M. 2007. JMorven: A Framework for parallel non-constructive qualitative reasoning and fuzzy interval simulation. PhD thesis, Department of Computing Science, Univeristy of Aberdeen.Google Scholar
Bruce, A. M., Coghill, G. M. 2005. Parallel fuzzy qualitative reasoning. In Proceedings of the 19th International Workshop on Qualitative Reasoning. Graz, 110–116.Google Scholar
Burnet, F. M. 1959. The Clonal Selection Theory of Acquired Immunity. Cambridge University Press.CrossRefGoogle Scholar
Camacho, R. 2000. Inducing Models of Human Control Skills using Machine Learning Algorithms. PhD thesis, University of Porto.Google Scholar
Cellier, F. E. 1991. General system problem solving paradigm for qualitative modeling. In Qualitative Simulation Modeling and Analysis, Advances in Simulation 5, 51–71. Springer-Verlag.CrossRefGoogle Scholar
Coghill, G. M. 1992. Vector Envisionment of Compartmental Systems. Master’s thesis, University of Glasgow.Google Scholar
Coghill, G. M. 1996. Mycroft: A Framework for Constraint based Fuzzy Qualitative Reasoning. PhD thesis, Heriot-Watt University.Google Scholar
Coghill, G. M., Chantler, M. J. 1994. Mycroft: a framework for qualitative reasoning. In Second International Conference on Intelligent Systems Engineering, 43–48, Hamburg-Harburg, Germany.CrossRefGoogle Scholar
Coghill, G. M., Garrett, S., King, R. D. 2004. Learning qualitative metabolic models. In European Conference on Artificial Intelligence (ECAI’04). Valencia, Spain, 445–449.Google Scholar
Coghill, G. M., Srinivasan, A., King, R. D. 2008. Qualitative system identification from imperfect data. Journal of Artificial Intelligence Research 32, 825–877.CrossRefGoogle Scholar
Coiera, E. 1989a. Generating qualitative models from example behaviours. Technical Report DCS Report 8901, Department of Computer Science, University of New South Wales, Sydney, Australia.Google Scholar
Coiera, E. 1989b. Learning qualitative models from example behaviours. In Proceedings of the Third Workshop on Qualitative Physics. Stanford, 45–51.Google Scholar
de Almeida, C., Ozyamak, E., Miller, S., de Moura, A., Booth, I., Grebogi, C. 2008. Modelling of methylglyoxal detoxification pathway in enteric bacteria. In Abstract Book of the 9th International Conference on Systems Biology, 170. Goteborg.Google Scholar
de Castro, L. N., Timmis, J. 2002. An artificial immune network for multimodal function optimization. In Proceedings of IEEE Congress on Evolutionary Computation (CEC’02). IEEE Press, 674–699.Google Scholar
de Castro, L. N., Von Zuben, F. J. 2000. The clonal selection algorithm with engineering applications. In Proceedings of GECCO,Workshop on Artificial Immune Systems and Their Applications. Las Vegas, USA, 36–39.Google Scholar
de Castro, L. N., Von Zuben, F. J. 2002. Learning and optimization using the clonal selection principle. In IEEE Transactions on Evolutionary Computation, Special Issue on Artificial Immune Systems. IEEE Press, 6, 239–251.Google Scholar
de Jong, H., Gouze, J.-L., Hernandez, C., Page, M., Sari, T., Geiselmann, J. 2004. Qualitative simulation of genetic regulatory networks using piecewise-linear models. Mathematical Biology 66, 301–340.CrossRefGoogle ScholarPubMed
Drulhe, S., Ferrari-Trecate, G., de Jong, H., Viari, A. 2006. Reconstruction of switching thresholds in piecewise-affine models of genetic regulatory networks. Lecture Notes in Computer Science 3927, 184–199. Springer-Verlag.CrossRefGoogle Scholar
Džeroski, S., Todorovski, L. 1993. Discovering dynamics. In Proc. Tenth International Conference on Machine Learning. 97–103. Morgan Kaufman.Google Scholar
Džeroski, S., Todorovski, L. 1994. Discovering dynamics: From inductive logic programming to machine discovery. Journal of Intelligent Information Systems 3, 1–20.Google Scholar
Ferguson, G. P., Totemeyer, S., MacLean, M. J., Booth, I. R. 1998. Methylglyoxal production in bacteria: suicide or survival? Archives of Microbiology 170(4), 209–218.CrossRefGoogle ScholarPubMed
Forbus, K. D. 1997. Qualitative reasoning. In The Computer Science and Engineering Handbook, 715–733. CRC-Press.Google Scholar
Gerçeker, R. K., Say, A. C. C. 2006. Using polynomial approximations to discover qualitative models. In Proceedings of the 20th Annual Workshop on Qualitative Reasoning (QR06), 64–74.Google Scholar
Goldberg, D. E. 1989. Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley.Google Scholar
Hau, D. T., Coiera, E. W. 1993. Learning qualitative models of dynamic systems. Machine Learning 26, 177–211.CrossRefGoogle Scholar
Iwasaki, Y., Simon, H. A. 1986. Causality in device behavior. Artificial Intelligence 29, 3–32.CrossRefGoogle Scholar
Juloski, A. L., Heemels, W. P. M. H., Ferrari-Trecate, G., Vidal, R., Paoletti, S., Niessen, J. H. G. 2005. Comparison of four procedures for the identification of hybrid systems. In Proceedings of the Hybrid Systems: Computation and Control (HSCC-05), Morari, M., Thiele, L. & Rossi, F (ed.), Lecture Notes in Computer Science 3414, 354–369. Springer-Verlag.CrossRefGoogle Scholar
Kay, H., Rinner, B., Kuipers, B. 2000. Semi-quantitative system identification. Artificial Intelligence 119, 103–140.CrossRefGoogle Scholar
Keppens, J., Shen, Q. 2001. On compositional modelling. Knowledge Engineering Review 16(2), 157–200.CrossRefGoogle Scholar
Khoury, M., Guerin, F., Coghill, G. M. 2007. Learning dynamic models of compartment systems by combining symbolic regression with fuzzy vector envisionment. In Genetic and Evolutionary Computation Conference (GECCO07), Thierens, D. (ed.), 2887–2894. ACM Press.Google Scholar
King, R. D., Garrett, S. M., Coghill, G. M. 2005. On the use of qualitative reasoning to simulate and identify metabolic pathways. Bioinformatics 21(9), 2017–2026.CrossRefGoogle ScholarPubMed
Koza, J. R. 1992. Genetic Programming: On the Programming of Computers by means of Natural Evolution. MIT Press.Google Scholar
Kraan, I., Richards, B. L., Kuipers, B. 1991. Automatic abduction of qualitative models. In Proceedings of the Fifth International Workshop on Qualitative Reasoning about Physical Systems, 295–301.Google Scholar
Kuipers, B. 1986. Qualitative simulation. Artificial Intelligence 29, 289–338.CrossRefGoogle Scholar
Kuipers, B. 1994. Qualitative Reasoning: Modeling and Simulation with Incomplete Knowledge. MIT Press.Google Scholar
Kuipers, B., Kassirer, J. P. 1984. Causal reasoning in medicine: Analysis of a protocol. Cognitive Science: A Multidisciplinary Journal 8(4), 363–385.CrossRefGoogle Scholar
Ljung, L. 1999. System Identification—Theory For the User, 2nd edition. Prentice Hall.Google Scholar
Lotka, A. J. 1925. Elements of Physical Biology. Williams & Wilkins Co.Google Scholar
McCreath, E. 1999. Induction in First Order Logic From Noisy Training Samples and Fixed Sample Sizes. PhD thesis, University of New South Wales.Google Scholar
Michaelis, L., Menten, M. 1913. Die kinetik der invertinwirkung. biochemische zeitschrift 49, 333–369.Google Scholar
Mitchell, T. 1997. Machine Learning. McGraw Hill.Google Scholar
Morgan, A. 1988. Qualitative Behaviour of Dynamic Physical Systems. PhD thesis, University of Cambridge.Google Scholar
Muggleton, S. 1995. Inverse entailment and Progol. New Generation Computing, Special issue on Inductive Logic Programming 1314, 245–286. Springer-Verlag.CrossRefGoogle Scholar
Muggleton, S. 1996. Learning from positive data. Lecture Notes in AI, 358–376.Google Scholar
Muggleton, S., Feng, C. 1990. Efficient induction of logic programs. In Proceedings of the 1st Conference on Algorithmic Learning Theory. Ohmsma, Tokyo, Japan, 368–381.Google Scholar
Muggleton, S., King, R. D., Sternberg, M. J. 1992. Protein secondary structure prediction using logic-based machine learning. Protein Engineering 5(7), 647–657.CrossRefGoogle ScholarPubMed
Muggleton, S., Raedt, L. D. 1994. Inductive logic programming: Theory and methods. Journal of Logic Programming 19–20, 629–679.CrossRefGoogle Scholar
Pang, W., Coghill, G. M. 2007a. Modified clonal selection algorithm for learning qualitative compartmental models of metabolic systems. In Genetic and Evolutionary Computation Conference (GECCO07), Thierens, D. (ed.), 2887–2898. ACM Press.Google Scholar
Pang, W., Coghill, G. M. 2007b. Advanced experiments for learning qualitative compartment models. In The 21st Annual Workshop on Qualitative Reasoning. Aberystwhyth.Google Scholar
Pang, W., Coghill, G. M. 2009. An immune-inspired approach to qualitative system identification of the detoxification pathway of methylglyoxal. In Proceeding of 8th International Conference on Artificial Immune Systems (ICARIS 2009), Andrews, P. S. and Timmis, J. (eds), Lecture Notes in Computer Science 5666, 151–164. Springer-Verlag.Google Scholar
Papadimitriou, C. H., Steiglitz, K. 1982. Combinatorial optimization: algorithms and complexity. Prentice-Hall.Google Scholar
Pawlak, Z. 1991. Rough Sets: Theoretical Aspects of Reasoning About Data. Kluwer Academic Publishing.CrossRefGoogle Scholar
Platzner, M., Rinner, B., Weiss, R. 1997. Parallel qualitative simulation. Simulation Practice and Theory—International Journal of the Federation of European Simulation Societies 5(7–8), 623–638.CrossRefGoogle Scholar
Plotkin, G. D. 1971. A further note on inductive generalisation. Machine Intelligence 6, 101–124.Google Scholar
Price, C., Trave-Massuyes, L., Milne, R., Ironi, L., Forbus, K., Bredeweg, B., Lee, M., Struss, P., Snooke, N., Lucas, P., Cavazza, M., Coghill, G. 2006. Qualitative futures. The Knowledge Engineering Review 21(4), 317–334.CrossRefGoogle Scholar
Ralston, A., Rabinowitz, P. 2001. A first Course in Numerical Analysis, 2nd edition. Dover Publications.Google Scholar
Ramachandran, S.Mooney, R. J.Kuipers, B. J. 1994. Learning qualitative models for systems with multiple operating regions. In the Eighth International Workshop on Qualitative Reasoning about Physical Systems (QR-94). Nara.Google Scholar
Rebolledo, M. 2006. Rough intervals: enhancing intervals for qualitative modeling of technical systems. Artificial Intelligence 170, 667–685.CrossRefGoogle Scholar
Richards, B. L., Kraan, I., Kuipers, B 1992. Automatic abduction of qualitative models. In National Conference on Artificial Intelligence, 723–728. AAAI.Google Scholar
Richards, B. L., Mooney, R. J. 1992. Learning relations by pathfinding. In Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI-92). San Jose, 50–55.Google Scholar
Richards, B. L., Mooney, R. J. 1995. Automated refinement of first-order horn-clause domain theories. Machine Learning 19(2), 95–131.CrossRefGoogle Scholar
Say, A. C. C. 1992. Qualitative System Identification. PhD thesis, Bogˇaziçi University.Google Scholar
Say, A. C. C., Kuru, S. 1996. Qualitative system identification: deriving structure from behavior. Artificial Intelligence 83, 75–141.CrossRefGoogle Scholar
Selman, B., Levesque, H., Mitchell, D. 1992. A new method for solving hard satisfiability problems. In Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI-92). San Jose, 440–446.Google Scholar
Shen, Q., Leitch, R. 1993. Fuzzy qualitative simulation. IEEE Transactions on Systems, Man, and Cybernetics 23(4), 1038–1061.CrossRefGoogle Scholar
Shoup, T. E. 1979. A Practical Guide to Computer Methods for Engineers. Prentice-Hall.Google Scholar
Srinivasan, A. 1999. The Aleph Manual. http://web.comlab.ox.ac.uk/oucl/research/areas/machlearn/Aleph/aleph.htmlGoogle Scholar
Srinivasan, A., King, R. D. 2008. Incremental identification of qualitative models of biological systems using inductive logic programming. Journal of Machine Learning Research 9, 1475–1533.Google Scholar
Todorovski, L. 2003. Using domain knowledge for automated modeling of dynamic systems with equation discovery. PhD thesis, Faculty of Electrical Engineering and Computer Science, University of Ljubljana.Google Scholar
Todorovski, L., Džeroski, S. 1997. Declarative bias in equation discovery. In Proceedings of the 14th International Conference on Machine Learning. Morgan Kaufmann, 376–384.Google Scholar
Todorovski, L., Džeroski, S., Srinivasan, A., Whiteley, J., Gavaghan, D. 2000. Discovering the structure of partial differential equations from example behavior. In Proceedings of the 17th International Conference on Machine Learning. Morgan Kaufmann, 991–998.Google Scholar
Valdés-Pérez, R. E. 1994. Conjecturing hidden entities by means of simplicity and conservation laws: machine discovery in chemistry. Artificial Intelligence 65(2), 247–280.CrossRefGoogle Scholar
Varšek, A. 1991. Qualitative model evolution. In Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, Sydney, Australia.Google Scholar
Vatcheva, I., de Jong, H., Bernard, O., Mars, N. J. 2005. Experiment selection for the discrimination of semi-quantitative models of dynamical systems. Artificial Intelligence 170, 472–506.CrossRefGoogle Scholar
Wiegand, M. 1991. Constructive Qualitative Simulation of Continuous Dynamic Systems. PhD thesis, Heriot-Watt university.Google Scholar
Zadeh, L. A. 1965. Fuzzy sets. Information and Control 8, 338–353.CrossRefGoogle Scholar