30 LEARNING QUALITATIVE MODELS INFORMATICA 4/92 WITH INDUCTIVE LOGIC PROGRAMMING Keywords: machine learning, qualitative modelling, qualitative simulation, inductive logic Sašo Džeroski programming Institut Jožef Stefan Qualitative models can be used instead of traditional numerical models in a wide range of tasks. These tasks include diagnosis, generating explanations of the system's behaviour and designing novel devices from first principles. Also, qualitative models are in some cases sufficient for the synthesis of control rules for dynamic systems. An important task in the theory of dynamic systems is the problem of identification of a model that explains given examples of system behaviour. This task can be formulated as a machine learning task of. inducing a hypothesis that explains given examples. As the induced hypothesis (model) has to capture relations among the parameters of the observed system, we have to use an inductive tool for learning relations, i.e., an inductive logic programming system. In this paper we describe the application of the inductive logic programming system mFOIL to the problem of learning a qualitative model of the connected-containers dynamic system. Učenje kvalitativnih modelov z induktivnim logičnim programiranjem Kvalitativne modele lahko uporabimo za reševanje različnih nalog, npr. za diagnostiko, generiranje razlage obnašanja dinamičnega sistema ter načrtovanje naprav iz osnovnih načel delovanja. V nekaterih primerili zadošča kvalitativni model tudi za sintezo pravil vodenja dinamičnega sistema. Pomemben problem v teoriji dinamičnih sistemov je problem identifikacije modela, ki razloži znane primere obnašanja sistema. Omenjeni problem lahko formuliramo kot problem avtomatskega učenja kjer je treba generirati hipotezo, ki razloži podane primere. Glede na to, da sestoji model iz relacij med parametri sistema, uporabimo za reševanje problema sistem za avtomatsko učenje relacij oz. induktivno logično programiranje. V članku je opisana uporaba sistema za induktivno logično programiranje mFOIL pri problemu učenja kvalitativnega modela sistema povezanih posod. 1 Introduction Qualitative models can be used instead of traditional numerical models in a wide range of tasks [Bratko 1991]. These tasks include diagnosis (e.g., [Bratko et al. 1989]), generating explanations of the system's behaviour (e.g., [Falkenheiner and Forbus 1990]) and designing novel devices from first principles (e.g., [Williams 1990]). Bratko [1991] conjectures that qualitative models are sufficient for the synthesis of control rules for dynamic systems, and supports this conjecture with an example. Among several established formalisms for defining qualitative models of dynamic systems, the most widely known are qualitative differential equations called confluences [De Kleer and Brown 1984], Qualitative Process Theory [Forbus 1984] and QSIM [Kuipers 1986]. In this paper, we will adopt the QSIM (Qualitative SIMulation) formalism, as it has been already used for learning qualitative models. 31 A fundamental problem in the theory of dynamic systems is the identification problem, defined as follows [Bratko 1991]: given examples of the behaviour of a dynamic system, find a model that explains these examples. Motivated by the hypothesis that it should be easier to learn qualitative than quantitative models, [Bratko et al. 1992] have recently formulated the identification problem for QSIM models as a machine learning problem. Formulated in this framework, the task of learning QSIM-type qualitative models is as follows: given QSIMtheory and ExamplesOfBehaviour, find a Qualitatively odel, such that QSIMtheory and QualitativeModel explain the ExamplesO /Behaviour, or formally, In the paper, we describe the application of the inductive logic programming system mFOIL [Dzeroski 1991], which can use non-ground background knowledge, to the same task [Dzeroski and Bratko 1992]. A brief introduction to inductive logic programming is first given, followed by an outline of the main features of mFOIL. We proceed with an overview of the QSIM formalism and illustrate its use on the connected-containers (U-tube) system. The experiments and results of learning a qualitative model of the U-tube system with mFOIL are next presented, followed by a discussion of related work. Finally, we conclude with some directions for further work. QSIMtheory A QualitativeM odel |= ExamplesO f Behaviour. The identification task can be formulated as a machine learning task. Namely, the task of inductive machine learning is to find a hypothesis that explains a set of given examples. In some cases the learner can also make use of existing background knowledge about the given examples and the domain at hand. So, the learning task can be formulated as follows: given background knowledge B and examples S, find a hypothesis H, such that B and Tt explain i.e., B AH (= £. We can see that ExamplesO f Behaviour correspond to E, QSIMtheory corresponds to B and the target QualitativeM odel to Ti. As a qualitative model consists of relations among the parameters of the modelled system, we have to use an inductive system for learning relations. Systems that learn relations from examples and relational background knowledge, represented as a logic program, have been recently called inductive logic programming (ILP) systems [Muggleton 1992]. Bratko et al. [1992] describe the application of the inductive logic programming system GOLEM [Muggleton and Feng 1990] to the problem of learning a qualitative model of the dynamic system of connected containers, usually referred to as the U-tube system. There have been, however, several problems with the application of GOLEM, to this task, stemming from the inability of GOLEM to use non-ground and non-determinate background knowledge. 2 Inductive logic programming In this section we introduce the field of machine learning of relations, or, as it has been recently called, inductive logic programming (ILP). We first mention some systems for learning relations, define the task of empirical inductive logic programming and illustrate it on a simple example. We then briefly outline some features of the ILP system mFOIL, which was used in our experiments in learning qualitative models. Various logical formalisms have been used in inductive learning systems to represent examples and concept descriptions. These formalisms are similar to the formalisms for representing knowledge in general. Several widely known inductive learning systems, such as ID3 [Quinlan 1986] and AQ [Michalski 1983] use propositional languages to represent examples (objects) and concepts. In both cases objects are represented as tuples of attribute values, i.e, in terms of their global features. To represent concepts, decision trees are used in ID3 and if-then rules in AQ. Another class of learning systems induce descriptions of relations (definitions of predicates). In these systems, objects are described structurally, i.e., in terms of their components and the relations between them. Training examples are represented by tuples of their components, while the relations between components belong to background knowledge. The languages used to represent examples, background knowledge and concept descriptions are typically subsets of first-order logic (logic programs). In this case, learning is in 32 fact logic program 1 synthesis and has recently been named inductive logic programming (ILP) [Muggleton 1991, Muggleton 1992], Two different approaches can be distinguished in the ILP paradigm [De Raedt 1992]: the interactive and the empirical ILP approach. Interactive ILP systems include MIS [Shapiro 1983], MARVIN [Sammut and Banerji 1986] and CLINT [De Raedt 1992] as well as CIGOL [Muggleton and Buntine 1988] and other approaches based on inverting resolution [Rouveirol 1991,Wirth 1989]. These systems typically learn definitions of multiple predicates from a small set of examples and queries to the user. Empirical ILP, on the other hand, is typically concerned with learning a definition of a single predicate from a large collection of examples. This class of ILP systems includes FOIL [Quinlan 1990], mFOIL [Dzeroski 1991], GOLEM [Muggleton and Feng 1990] and LINUS [Lavrac et al. 1991]. LINUS, FOIL and mFOIL upgrade attribute-value learners from the ID3 and AQ family towards a first-order logic framework. A different approach is used in GOLEM which is based on Plotkin's-notion of relative least general generalization (rlgg) [Plotkin 1969]. Empirical ILP systems are more likely to be applied in practice for two reasons. First, there is more experience with learning single concepts from large collections of data than with deriving knowledge bases from a small number of examples. Second, empirical ILP systems are much more efficient because of the use of heuristics, because there is no need to take into account dependencies among different concepts, and because no examples are generated [De Raedt and Bruynooghe 1992]. In fact, they are already efficient enough to be applied to real-life domains [Bratko 1992]. Several applications have been reported, including learning qualitative models from example behaviours [Bratko et al. 1992] [Dzeroski and Bratko 1992], inducing temporal rules for satellite fault diagnosis [Feng 1991], learning to predict protein secondary structure [Muggleton et al. 1992] and learning rules for finite element mesh design [Dolsak and Muggleton 1992, Dzeroski and Dolsak 1991]. 1 For an introduction to logic programming we refer the reader to [Bratko 1990], A detailed theoretical treatment of the subject is given in [Lloyd 1987]. Empirical ILP The task of empirical ILP, which is concerned with learning a single predicate, can be formulated as follows. Given: • a set of training examples £, consisting of true £+ and false S~ facts of an unknown predicate p, • a description language £, specifying syntactic restrictions on the definition of predicate p, • background knowledge B, defining predicates qi (other than p) which may be used in the definition of p and which provide additional information about the arguments of the examples of predicate p, Find: • a definition 7i for p, expressed in C, such that H is complete, i.e., Ve € £+ : B A H \= e, and consistent with respect to the examples, i.e., Ve G £~ : B A 7i ^ e. The true facts £+ are called positive examples, the false facts £~ are called negative examples and the hypothesis H, i.e., the definition of p, is usually called the definition of the target predicate. When learning from noisy examples, the completeness and consistency criteria need to be relaxed in order to avoid overly specific hypotheses. The ILP system mFOIL The ILP system mFOIL [Dzeroski 1991] is largely based on the-FOIL [Quinlan 1990] approach. We thus briefly describe FOIL first and then outline some of the key features of mFOIL. FOIL extends some ideas from attribute-value learning algorithms to the ILP paradigm. In particular, it uses a covering approach similar to AQ's [Michalski 1983] and an information based search heuristic similar to ID3's [Quinlan 1986]. The hypothesis language C in FOIL is the language of function-free program clauses, which means that no constants or terms other than variables may appear in the induced clauses. Function-free ground facts (relational tuples) are used to represent both training examples and background knowledge. 33 After the pre-processing of the training set, which consists of generating negative examples if none are given, the outermost loop of the FOIL algorithm repeats the following two steps untill all positive facts are covered: • find a clause that covers some positive and no negative facts, • remove the facts covered by this clause from the training set. Finding a clause consists of a number of refinement steps. The search starts with the clause with empty body. At each step, the clause c built so far is refined by adding a-literal to its body. These literals are positive or negative atoms of the form Xi = Xj or qk(Yi,Y2,...,Ynk), where the X's appear in c, the Y's either appear in c or may be new variables and qk is a relation (predicate) from the background knowledge or the target predicate p itself. To stop the search for literals to be added to a clause, FOIL employs the encoding length restriction, which limits the number of bits used to encode a clause to the number of bits needed to explicitly indicate the positive examples covered by it. The construction of a clause is stopped when it covers only positive examples (is consistent) or when no more bits are available for adding literals to its body. The search for clauses stops when no new clause can be constructed under the encoding length restriction, or alternatively, when all positive examples are covered. One should be aware, however, that there are several problems with the encoding length restriction that actually degrade FOIL's performance on both noisy and non-noisy data as shown in [Dzeroski and Lavrac 1991]. The most important differences between mFOIL and FOIL are related to the noise-handling mechanism used. mFOIL uses Bayesian probability estimates, namely the Laplace and the m-estimate [Gestnik 1990], of expected clause accuracy as search heuristics. These estimates have been successfully used in a similar way in prepositional learning systems [Clark and Boswell 1991, Dzeroski et al. 1992], mFOIL also uses significance tests, similar to the ones in [Clark and Boswell 1991]. It achieved better results than FOIL on a test domain with artificially added noise and on a real-life domain of learning rules for finite element mesh design [Dzeroski 1991, Dzeroski and Bratko 1992], Another key difference is the capability of mFOIL to use background knowledge which may contain rules and not ground facts only. This feature is especially important for learning qualitative models, since the QSIMtheory consists of rules and not ground facts only. Other differences between FOIL and mFOIL are related to the search strategy and the space of possible hypotheses. As opposed to the hill-climbing search in FOIL, where only the best partially built clause is kept, mFOIL uses beam search and keeps several most promising clauses (the beam), which are refined gradually. mFOIL can also use information about the background knowledge, such as symmetry of predicates and types of predicate arguments, to reduce the space of possible hypotheses. 3 Qualitative modelling In this section, we first introduce the QSIM [Kuipers 1986] formalism and then illustrate it on the U-tube system. We also describe how the QSIM theory can be formulated in logic [Bratko et al. 1992], so that it can be used as background knowledge in the process of learning qualitative models from examples. The QSIM formalism In the theory of dynamic systems, a physical system is represented by a set of continuous variables, which may change over time. Sets of differential equations, relating the system variables, are typically used to model dynamic systems numerically. Given a model (a set of differential equations) of the system and its initial state, the behaviour of the system can be predicted by applying a numerical solver to the set of differential equations. A similar approach is taken in qualitative simulation [Kuipers 1986]. In QSIM, a physical system is described by a set of variables representing the physical parameters of the system (continuously differentiable real-valued functions) and a set of constraint equations describing how those parameters are related to each other. In this case, a (qualitative) model is a set of constraint equations. Given a qualitative model and a qualitative initial state of the system, the QSIM simula- 34 tion algorithm [Kuipers 1986] produces a directed graph consisting of possible future states and the immediate successor relation between the states. Paths in this graph starting from the initial state correspond to behaviours of the system. The value of a physical parameter is specified qualitatively in terms of its relationship with a totally ordered set of landmark values. The qualitative state of a parameter consists of its value and direction of change. The direction of change can be inc (increasing), std (steady) and dec (decreasing). Time is represented as a totally ordered set of symbolic distinguished time points. The current time is either at or between distinguished time-points. At a distinguished time-point, if several physical parameters linked by a single constraint are equal to landmark values, they are said to have corresponding values. The constraints used in QSIM are designed to permit a large class of differential equations to be mapped straightforwardly into qualitative constraint equations. They include mathematical relationships, such as deriv{Velocity, Acceleration) and mult(Mass, Acceleration, Force). In addition, constraints like M+ (Price, Power) and M~ (Current, Resistance) state that there is a monotonically increasing/decreasing functional relationship between two physical parameters, but do not specify the relationship completely. The U-tube system La Lb Fab Fba Figure 1: The U-tube system. Let us illustrate the above notions on the connected-containers (U-tube) example, adapted from [Bratko et al. 1992]. The U-tube system (illustrated in Figure 1) consists of two containers, A and B, connected with a pipe and filled with water to the corresponding levels La and Lb. Let the flow from A to B be denoted by Fab, the flow from B to A by Fba. The variables La,Lb,Fab and Fba are the parameters of the system. The flows Fab and Fba are the time derivatives of the water levels Lb and La, respectively, and run in opposite directions. Let the difference in the levels of the containers A and B be Diff = La — Lb. The pressure Press along the pipe influences the flow Fab: the higher the pressure, the greater the flow. A similar dependence exists between the level difference and the pressure. The above constraints can be formulated in QSIM as follows: d —La = Fba dt —Lb — Fab dt Fab = -Fba Diff = La -Lb Press = M+(Diff) Fab = M+(Press) If we are not explicitly interested in the pressure, the last two qualitative constraint equations can be simplified into one: Fab = M+(Di f f) For comparison, in a numerical model, the last two equations might have the form Press = c\ • Diff Fab = C2 ■ Press or, when simplified Fab = c • Diff where c, ci and c