Numerical reasoning with an ILP system capable of lazy evaluation and customised search

Numerical reasoning with an ILP system capable of lazy evaluation and customised search Ashwin Srinivasan and Rui Camacho Abstract Using problem-specific background knowledge, computer programs developed within the framework of Inductive Logic Programming (ILP) have been used to construct restricted first-order logic solutions to scientific problems. However, their approach to the analysis of data with substantial numerical content has been largely limited to constructing clauses that: (a) provide qualitative descriptions (“high”, “low” etc.) of the values of response variables; and (b) contain simple inequalities restricting the ranges of predictor variables. This has precluded the application of such techniques to scientific and engineering problems requiring a more sophisticated approach. A number of specialised methods have been suggested to remedy this. In contrast, we have chosen to take advantage of the fact that the existing theoretical framework for ILP places very few restrictions of the nature of the background knowledge. We describe two issues of implementation that make it possible to use background predicates that implement well-established statistical and numerical analysis procedures. Any improvements in analytical sophistication that result are evaluated empirically using artificial and real-life data. Experiments utilising artificial data are concerned with extracting constraints for response variables in the text-book problem of balancing a pole on a cart. They illustrate the use of clausal definitions of arithmetic and trigonometric functions, inequalities, multiple linear regression, and numerical derivatives. A non-trivial problem concerning the prediction of mutagenic activity of nitroaromatic molecules is also examined. In this case, expert chemists have been unable to devise a model for explaining the data. The result demonstrates the combined use by an ILP program of logical and numerical capabilities to achieve an analysis that includes linear modelling, clustering and classification. In all experiments, the predictions obtained compare favourably against benchmarks set by more traditional methods of quantitative methods, namely, regression and neural-network. 1 1 Introduction The framework defining Inductive Logic Programming (ILP: see [22]), has seen the advent of efficient, general-purpose programs capable of using domainspecific background knowledge to construct automatically clausal definitions that in some sense, generalise a set of instances. This has allowed a novel form of data analysis in molecular biology [15, 16, 26], stress analysis in engineering [7], electronic circuit diagnosis [11], environmental monitoring [10], software engineering [1], and natural language processing [49]. Of these, some, such as those described in [1, 10, 11, 26, 49], are naturally classificatory. Others, such as those described in [7, 15, 16], are essentially concerned with predicting values of a numerical “response” variable (for example, chemical activity of a compound). For problems of this latter type, ILP programs have largely been restricted to constructing definitions that are only capable of qualitative predictions (for example, “high”, “low” etc.). Further, if the definition involves the use of any numerical “predictor” variables, then this usually manifests itself as inequalities that restrict the ranges of such variables. This apparent limitation of ILP programs has been of some concern, and rates highly on the priorities of at least one prominent research programme designed to address the shortcomings of ILP [5]. In theory, any form of numerical reasoning could be achieved from first principles by an ILP program. Thus, much of the limitations stated above must stem from practical constraints placed on ILP programs. Some of these constraints pertain to ILP programs like those described in [29, 33], where background knowledge is restricted to ground unit clauses. But what about programs capable of understanding background knowledge that includes more complex logical descriptions? Such programs are in some sense closer to the spirit of the ILP framework defined in [22]. In this paper, we explore the possibility of improving the numerical capabilities of such an ILP program by the straightforward approach of including as background knowledge predicates that perform numerical and statistical calculations. In particular, by the phrase “numerical capabilities” we are referring to the ability to construct descriptions that may require at least the following: •Arithmetic and trigonometric functions; •Equalities and inequalities; •Regression models (including equations constructed by linear or nonlinear regression); and 2 •Geometric models (that is, planar shapes detected in the data). An ILP program capable of using such primitives would certainly be able to provide more quantitative solutions to the molecular biology and stress analysis problems cited earlier. In this paper we describe two implementation details that considerably improve the quantitative capabilities of the ILP program Progol [24]. The first allows the inclusion of arbitrary statistical and numerical procedures. The second allows, amongst others, a cost function to be minimised when obtaining predictions. It is important to note that these are implementation details only, and do not in anyway, compromise the general applicability of the ILP program. The capabilities for quantitative analysis are assessed empirically with experiments using artificial and natural data. Experiments with artificial data are concerned with extracting constraints – in the form of equations – for numerical variables from simulator data records of a control task. Balancing a pole on a cart is a text-book problem in control engineering, and has been a test-bed for evaluating the use of machine learning programs to extract comprehensible descriptions summarising extensive simulator records of controller behaviour. Data records are usually tabulations of the values of numerical-valued variables, and so far, feature-based machine learning programs either equipped with builtin definitions for inequalities or those capable of regression-like behaviour have been used to analyse such data. There are some advantages to the pole-and-cart problem. First, the simulations provide ready access to data records. Second, the nature of the equations to be extracted is relatively straightforward, and known prior to the experiments (from the dynamics of the physical system concerned: see Appendix B). This allows us to focus on the question of whether the ILP program is able to reconstruct these equations. The experiments with artificial data whilst being instructive, are unrepresentative. In most realistic scenarios, the nature of the underlying model is not known. Under this category, we examine the case of predicting the mutagenic activity of a set of nitroaromatic molecules as reported in [6]. In that study, the authors identify these compounds as belonging to two disparate groups of 188 and 42 compounds respectively. The main interest in the group of 42 compounds stems from the fact that they are poorly modelled by the analytic methods used by experts in the field. Elsewhere [16] an ILP program has been shown to find qualitative descriptions for activity amongst some of these molecules, but no models capable of quantitative pre3 diction was reported. The second set of experiments reported in this paper is concerned with constructing an explanation for this data. The paper is organised as follows. Section 2 introduces the main features of a general ILP algorithm, and how these are implemented within the Progol program. It also describes aspects within the Progol implementation that impede its use when analysing numerical data. Section 3 describes two general-purpose extensions to the implementation of an ILP algorithm that overcome such problems. Section 4 describes how this work contributes to existing research in this area. Section 5 contains the pole-and-cart experiment, and Section 6 the experiment with predicting mutagenic activity. Section 7 concludes this paper. 2 ILP and Progol 2.1 Specification Following [23], we can treat Progol as an algorithm that conforms to the following partial specifications (we refer the reader to [19] for definitions in logic programming). •Bis background knowledge consisting of a set of definite clauses C1∧ C2∧. . . •Eis a set of examples = E+∧E−where –E+=e1∧e2∧. . . are “positive examples” that are definite clauses. These are often ground unit clauses; –E−=f1∧f2∧. . . are “negative examples” that are Horn clauses. These are also often ground unit clauses; and –B6|=E+– that is, there is some prior necessity to construct a hypothesis. •H=D1∧D2∧. . ., the output of the algorithm given Band E, is a good, consistent explanation of the examples and is from a predefined language L. Such an output usually satisfies at least the following conditions: –Each Diin Hhas the property that it can explain at least one positive example. That is, B∧Di|=e1∨e2∨. . ., where {e1, e2, . . .} ⊆ E+ 4 –B∧H|=E+; –B∧H6|=2; and –B∧H∧E−6|=2 –|B∧H|<|B∧E+|where |. . . |denotes some measure of size. In practice, Progol typically does not meet the requirement for “Strong Consistency”, as some members of E−are treated as “noise”. This introduces some complications in the calculation of |B∧H|, which have to be augmented by an amount required to specify the noisy instances (or exceptions). The hypothesis language Lis specified by: •Predicate argument annotations (or “modes”). These are usually of the form: –Input/Output/Constant. An input argument is a variable that is expected to be instantiated, and will not be further instantiated by the predicate. An output argument is a variable that is not expected to be instantiated. This variable will be instantiated by the predicate. For predicates that are “non-deterministic”, multiple instantiations may be be possible on backtracking. An argument can be specified as being instantiated to a constant symbol. –Type. The type or domain of each argument. The set of acceptable values of each type may be specified by enumeration or by an intensional definition. •Other specifications concerning clauses acceptable for inclusion in the hypothesis. These are usually: –Variable depth. The maximum length “chain” of input and output variables in a clause. –Inconsistency. The extent to which the requirement of “Strong Consistency” can be violated by the clauses. This usually is an upper bound on the number of examples in E−that can be treated as “noise”. –Clause length. The maximum number of literals in any clause. 5 2.2 Implementation Progol [24] implements the specifications listed above by constructing the set Hone clause at a time. Each clause to be added to the set is obtained using an admissible search procedure that evaluates potential candidates along the criteria of sufficiency, consistency, and compression. Complete algorithmic descriptions of the Progol algorithm are available in [24], and only the main steps are shown in Figure 1. 1. B,Lare given. E=E+∪E−are given and have the same predicate symbol as the target relation. Let cbe the specification in Lof the maximum number of negative literals allowed. 2. If E=∅then return B. 3. Let ebe the first example in E. 4. Construct ⊥s.t. ⊥ |=B∪ {e} 5. Let Sc={C:2[C][⊥] and C has at most c negative literals } 6. Let D= bestclause(B, e, E, Sc) 7. Let B=B∪D 8. Let E0={e:e∈E+and B∪ {e} ` 2} 9. Let E=E−E0. 10. Goto 2. Figure 1: The Progol algorithm. Here denotes a subsumption ordering, and [.] denotes an equivalence class. The construction of ⊥in Step 4 is complicated and we refer the reader to [24]. For the purposes of this paper, it is sufficient to note that ⊥is usually a definite clause (typically with many 100s of literals), and anchors one end of the space of clauses to be searched (the other end being 2). Clauses in Sc(Step 5) are enumerated one at a time – starting from 2 – by using a built-in refinement operator (in the sense described by [42], 6 and denoted by ρ). The auxiliary function bestclause/4 (again, built-in to the implementation) returns the clause adjudged to be the best using some measure of “compression”. Two exceptional situations arise. First, there is no clause that passes the test of compression. In this case the example e selected is returned. Second, several clauses have equally good compression. In this case, the first one obtained is returned. 2.3 Shortcomings for numerical reasoning The implementation, as described in Section 2.2 poses some special difficulties when dealing with the analysis of numerical data. The first, concerns the use of functions whose functional result(s) depend on more than 1 example. For example, univariate regression can be seen as a function, that, given examples of (X,Y) pairs, returns the tuple (M,C) representing the slope and intercept of the line of best-fit through the (X,Y) pairs. A correct computation of (M,C) requires all the (X,Y) pairs. For such cases, the implementation of Progol is unable to return clauses containing the correctly computed values. This stems from the fact that clauses are constructed by selecting from a ⊥clause constructed from a randomly chosen, single example. Some attempt to overcome this can be made by “guessing” correct values of such functional outputs from the example chosen (for example, see [28]). However, there are obvious limitations to this approach. The second difficulty in the current implementation arises from a mismatch in the criterion being optimised during clause selection. This criterion, encoded within the bestclause/4 function in Section 2.2, is typically a description-length criterion. In dealing with numeric data, the criterion to be minimised is usually different (for example, expected mean-square error). A minor concern pertains to the fact that there may be no concept of “negative” examples when dealing with numerical data. Learning from positive examples only has recently been addressed within the ILP framework in various ways (see for example [25, 38, 37]). However, this has not proved a difficulty for the problems addressed here, and the changes to the implementation described in the next section adequately address these issues. Examples of their form and use are available in Appendix A. 7 3 Two changes to the implementation 3.1 Lazy evaluation of functions Using a most-specific clause from a single example to guide the search for clauses prevents Progol from using predicates like linear regression where the functional result (here the coefficients of regression) is determined from a set of values that arise from more than one example. To address this, we propose the technique of “lazily evaluating” functional outputs. For a particular function, this requires that the background knowledge Bhas the following: (1) a mode annotation specifying input and output argument(s) along with their types (in the sense described in Section 2.1); and (2) a definition specifying the procedure for evaluating the output argument(s) from sets of values for the input argument(s). Provided with this, the following modifications to the basic algorithm are implemented: 1. Notionally construct a sentence ⊥Xfrom the most-specific clause ⊥ constructed in Step 4. ⊥Xdiffers from ⊥only in the (negative) literals in ⊥that represent lazily-evaluated functions. For these, the corresponding literal in ⊥Xis obtained by replacing the output terms with existentially-quantified variables. Each such variable is distinct from any other output variable in ⊥X. For example, if q/2, r/2 represent lazily-evaluated functions whose second argument is denoted “output”, and ⊥:∀A∀Bp(A, B)←q(A, 3), r(B, 3) then ⊥X:∀A∀B∃Y∃Zp(A, B)← q(A, Y ), r(B, Z). ⊥Xwill take the place of ⊥in the search. 2. When incrementally constructing clauses, if the literal selected requires lazy evaluation then its output values are computed (see below). These values will appear in place of the existentially quantified variables introduced into the literal in ⊥X. If no output values are obtained, then the literal is not added to the clause. Without loss of generality, assume that the predicate q/2 has been marked for lazy evaluation, and the mode annotations state the first argument to be input and the second as output. This literal now appears as q(X, Sky) in ⊥X. Here Skyis an existentially quantified variable that does not appear as the output of any other literal in ⊥X. In the search, we are concerned with adding this literal to a definite clause C. The main steps of computing the output value of q/2 are shown in Figure 2 For a given h, the procedure in Figure 2 clearly terminates. Note that the procedure assumes that the background knowledge Bis complete to the 8 lazyeval(l, C, h, B, E+, E−) 1. Let l=q(X, Sky), C =head ←body 2. Let θX p={X/P1, X/P2, . . .}be the substitution instances for Xfrom each substitution θpisuch that head ·θpi∈E+and B`hbody ·θpi 3. Let θX n={X/N1, X/N2, . . .}be substitution instances of Xfrom each substitution θnisuch that head ·θni∈E−and B`hbody ·θni 4. If there is a ground term Tisuch that B`hQ([θX p, θX n], Ti) then θ= {Y/Ti}otherwise θ=∅ 5. return θ Figure 2: The lazy evaluation procedure. Here his a natural number, and `hdenotes derivation in at most hresolution steps. Qis used to distinguish the definition that allows computation of output values for q/2. extent that an answer substitution for Yis obtainable within hresolution steps by the query Q([θp, θn], Y )?. As stated, it is evident that even when several answer substitutions exist for Y, the procedure returns only one. This is not of concern if the literal being evaluated represents a function. We also note in passing that the θX p, θX nare similar to the “positive” and “negative” substitutions defined in [36, 37]. The inclusion of lazy evaluation results in one additional violation to the Progol algorithm described in Figure 1. There, any clause Cin the search is such that 2[C][⊥], where is a subsumption ordering – normally Plotkin’s θ-subsumption [32]. Analogously, with lazy evaluation it would be desirable to show a clause Cin the search is such that 2X[C]X[⊥X] where Xis a (possibly different) subsumption ordering. We do not explore this further here. The technique of lazy evaluation can be extended to handle multiple answer substitutions and even to the construction of new predicate definitions “on-the-fly.” However in this paper, its scope will be restricted to the evaluation of functions like linear regression. 9 for linear and angular acceleration are constructed separately. When obtaining constraints for ¨x, Progol has access to tabulated values of x, ˙x, θ, ˙ θ, and ¨ θfor the examples chosen. Similarly, when obtaining constraints for ¨ θthe ILP program has access to values of x, ˙x, θ, ˙ θ, and ¨x. The following method was adopted to generate data, obtain and test any constraints: 1. 1000 runs are performed with each of the following values of force (Fin N), mass of pole (min kg), and mass of cart (Min kg): (i) F= 0.0, m = 0.1, M = 1.0; (ii) F= 0.0, m = 1.0, M = 1.0; (iii) F= 0.0, m = 1.0, M = 0.1; (iv) F= +10.0, m = 0.1, M = 1.0; (v) F= +10.0, m = 1.0, M = 1.0; (vi) F= +10.0, m = 1.0, M = 0.1; (vii) F=±10.0, m = 0.1, M = 1.0; (viii) F=±10.0, m = 1.0, M = 1.0; and (ix) F=±10.0, m = 1.0, M = 0.1. On each run the values of x, ˙x, θ, and ˙ θ, ¨x, ¨ θare tabulated once every 0.02s. 2. For each configuration of F, m, M, a data record is selected at random. This yields 1000 data records for each configuration. The first 500 of these are used for “training” and the remainder are set aside to “test” any constraints obtained. 3. Using tabulated values for x, ˙x, θ, ˙ θ, ¨ θ, and the background knowledge obtain equations for ¨x. 4. Using tabulated values for x, ˙x, θ, ˙ θ, ¨x, and the background knowledge obtain equations for ¨ θ 5. Record ¨xand ¨ θvalues computed by these equations on the test set. 6. For each of ¨xand ¨ θ, use training-set values for the attributes in Section 5.2.3 to (a) obtain a linear equation using stepwise linear regression; (b) obtain a regression tree; and (c) train the neural net. Record ¨x and ¨ θvalues computed by each of these methods on the test set. 7. Compute the degree of agreement of each method to the actual values of ¨xand ¨ θby computing the mean of the squared difference between actual values and those predicted by each method. In keeping with [40], this statistic is termed the “mean square error of prediction” (MSEP). Parameter settings for the stepwise regression procedure control the inclusion and exclusion of variables in the equation. These parameters relate 16 to the level of significance that has to be achieved above (or below) which a variable is retained in the model (or removed from the model). There is no prescribed setting for these parameters (termed PIN and POUT respectively in SPSS). We have adopted the procedure of setting PIN, POUT to values that result in equations with no more than 2 independent variables on the training data, except when predicting ¨xwith F=±10N. In this case, up to 3 independent variables are allowed, to enable the program to use values of Fin the equation. This is in accordance with the restrictions provided to the ILP program. The regression-tree procedure implemented within CART is equipped with validation procedures that enable it to estimate automatically the parameters specifying the tree-construction. For the neural-network algorithm in SNNS, 10000 epochs were used with the “shuffle” option. In each epoch all training examples were presented. The net has one input unit for each attribute, 4 hidden units and 1 output unit and was fully connected. There is no accepted method for determining the number of hidden units. The settings chosen were obtained based on the fact that they yielded the lowest error on the training data across possible settings ranging from 0 to 5 units in the hidden layer. 5.4 Experimental results and discussion Figures 5 and 6 tabulate values of MSEP summarising the difference between actual values of ¨x, ¨ θand those predicted by each method. The actual equations on which these calculations are based are in Appendix C. The tabulations show that the mean-square-error of prediction (MSEP) from the ILP theory is usually lower than all programs other than regression. Figure 7 tabulates a comparison of the MSEP of Progol against that of the propositional learners for the 18 errors tabulated in Figures 5 and 6. In general, we would expect the predictivity of Progol’s theories to be at least comparable to those of linear regression given that the ILP program relies on regression definitions provided as background knowledge to construct its equations. Further, since by virtue of its search technique, Progol would do an “all-subsets” regression, it would seem to be surprising to find instances where the SPSS regression procedure (which implements “stepwise” regression) actually does perform better. Closer examination reveals that in 3 of the 4 cases that this occurs in Figure 7, Progol has identified the correct target equation. This suggests its higher error to be an artifact of the test sample. To this extent, the entries in the first row of Figure 7 17 Algorithm F= 0 F= +10 F=±10 m/M m/M m/M 0.1 1.0 10.0 0.1 1.0 10.0 0.1 1.0 10.0 Progol 9e−6 9e−6 2e−5 6e−5 1e−5 6e−4 4e−5 4e−4 2e−2 Regression 9e−6 9e−6 2e−5 6e−5 1e−5 6e−4 6e−5 1e−5 1e−2 Regression tree 3e−5 4e−4 3e−3 3e−5 7e−4 2e−2 5e−5 1e−3 3e−2 Neural network 2e−5 6e−4 5e−3 3e−5 1e−3 3e−2 8e−4 1e−2 1e−1 Figure 5: Mean square error of predicted values of ¨xon 500 test examples. The notation ae −bstands for a×10−b. are as expected. On both data sets, the regression tree’s predictions appear to be considerably worse than those made by Progol. By producing axis-parallel partitions and predicting mean values for each partition, the tree program is unable to capture the linear nature of the constraints involved. Definitive statements concerning the apparent poorer performance of the neural network are confounded by the absence of a principled technique for selecting the topology of the network. We can therefore do no more than state that for the particular topology used, the neural network’s predictions are consistently worse than Progol’s on the pole-and-cart data. Besides a comparison of predictive accuracies, it is instructive to examine, where possible, the nature of the theories obtained by each algorithm. Appendix C shows that for the pole-and-cart problem, Progol constructs 24 equations corresponding to different physical parameter settings. Of these, the reader can verify that the correct linear model is identified on 22 occasions. Here, by “correct” we mean that the linear model has the same predictor variables as those in the target model described in Appendix B – we will examine the issue of correctly estimating the coefficients for these variables in greater detail below. In contrast, linear regression constructs 18 equations, of which 9 are correct. The difference in the number of equations highlights an important point of difference between the two programs when constructing theories for the case where F=±10N. Here, Progol constructs a pair of equations corresponding to the situations arising from F= +10N, 18 Algorithm F= 0 F= +10 F=±10 m/M m/M m/M 0.1 1.0 10.0 0.1 1.0 10.0 0.1 1.0 10.0 Progol 2e−3 1e−3 2e−3 2e−3 2e−3 1e−3 2e−3 2e−3 2e−3 Regression 2e−3 4e−4 8e−4 2e−3 2e−3 5e−2 1e−2 8e−3 7e−2 Regression tree 3e−3 5e−3 2e−2 3e−3 1e−2 4e−2 5e−3 1e−2 1e−1 Neural network 6e−3 1e−2 3e−2 5e−3 9e−3 1e−1 1e−1 1e−1 4e−1 Figure 6: Mean square error of predicted values of ¨ θon 500 test examples. The notation ae −bstands for a×10−b. F=−10N. The regression program attempts to explain both situations by using Fas an independent variable in equations for ¨x. Given the nature of their theories, we are not in a position to directly compare the output of the regression tree and neural network against the target model. On the pole-and-cart data, the tree program produces reasonably complex theories (some upto 200 nodes), and the latter’s “theory” consisting of a listing of 25 floating-point numbers corresponding to the weights associated with each node in the network. The availability of an automated controller (here the BOXES program) and a known target theory allows us to investigate further the nature of theories obtainable from Progol. In what follows, we restrict attention to a commonly used pole-and-cart configuration, namely F=±10N, m = 0.1kg, M = 1.0kg. Within this setting, we are in a position to examine empirically: (a) the convergence of coefficients in Progol’s equations to the coefficients in the target theory; (b) bias in prediction and the estimation of the coefficients by Progol; and (c) extensions to the background knowledge to allow numerical differentiation by Progol. We first examine how Progol’s estimation of the target theory changes with increasing the number of training examples. Target theories for ¨xand ¨ θ are obtained from the equations of motion given in Appendix B. These are of the form ¨x=C1−M1¨ θcosθ+M2˙ θ2sinθ and ¨ θ=C2+K1sinθ−K2¨xcosθ. For the given set of physical parameters, namely F=±10N, m = 0.1kg, M = 1.0kg, the coefficients take the particular values: C1=±9.091, M1=M2= 19 Algorithm MSEP of Progol Better Worse Same Regression 5 4 9 Regression tree 16 1 1 Neural network 17 1 0 Figure 7: A comparison of the MSEPs on the pole-and-cart data. The terms “better”, “worse” and “same” denote the cases that the MSEP of Progol is lower, higher, or the same (up to the precision shown in Figures 5 and 6) as the corresponding propositional learner. 0.045, C2= 0.000, K1= 14.7, K2= 1.50 (the two values of C1result from F=±10N). Figure 8 tabulates the progressive change in error of the Progol estimates from these expected values, averaged over the two values of F. The tabulation suggests that Progol’s approximation of the target theory does improve as the number of training examples is increased. We now turn our attention to the question of bias in Progol’s predictions and estimates of the coefficients. For the physical settings under consideration, Figure 9 tabulates the frequencies of positive and negative residuals arising from over and under-estimates of ¨xand ¨ θon the 500 test examples. Also tabulated are the means of the predicted and actual values for each variable. The entries suggest that on Progol’s predictions appear to be largely unbiased. Consider now any bias in the estimation of coefficients that appear in equations for the dependent variables. Operating under the control of a two-sided force provides us with two estimates for each coefficient – one for which Fis positive (here +10N) and the other when it is negative (−10N). Calling these two estimates “duplicates” 1, and repeatedly performing the experiment of learning equations for ¨xand ¨ θallows us to record the number of occasions that (a) both duplicates overestimate a coefficient; (b) both duplicates underestimate a given coefficient; (c) the F-positive duplicate overestimates a coefficient while the F-negative underestimates; (d) the F-positive duplicate underestimates a coefficient while the F-negative overestimates; (e) one duplicate under or over-estimates a coefficient while 1This term and the analysis following are due to Donald Michie 20 Training Examples Error in coefficients for ¨xError in coefficients for ¨ θ 100 – 0.803 250 0.002 0.587 500 0.002 0.876 1000 0.002 0.350 1500 0.001 0.141 Figure 8: Error of coefficients estimated in the linear model obtained by Progol for the pole-and-cart data. For a given number of training examples, this error is the average of the total absolute deviation of estimates from expected values (from the target model) for F= +10 and F=−10. Estimates and expected values are recorded up to 3 significant figures. An entry of “–” denotes that the target model was not identified by Progol. the other is exact (up to some degree of precision); and (f) both duplicates estimate a coefficient exactly (again, up to some degree of precision). Severe discrepancies between the tallies in (a) and (b) would suggest that Progol’s estimation of that coefficient was biased. Discrepancies in the tallies (c) and (d) would suggest bias in the simulator. Tallies of (e) and (f) are not of particular interest here. Figure 10 tabulates these numbers over 10 repeats of obtaining equations for ¨xand ¨ θfrom independent training sets of 500 examples each. The 6 cases (a)–(f) in the tabulation correspond to the situations described above, and Dependent Frequency Mean variable + residuals −residuals Actual Predicted ¨x0.46 0.52 −0.195 −0.196 ¨ θ0.54 0.46 0.309 0.310 Figure 9: Examining residuals for bias in Progol’s prediction of the dependent variable on the pole-and-cart data. 21 the coefficients C1. . . K2are as before. The comparison of estimates and expected values proceeds to 3 significant figures. It is evident from this figure that for 4 of the 6 coefficients, there is no evidence of any bias. Of the remaining two, the evidence for bias in estimates of M1does not appear to be substantial. Some degree of uncertainty does however rest on the estimates of M2, and suggests further investigation. Case Predicting ¨xPredicting ¨ θ C1M1M2C2K1K2 (a) 0 0 5 1 0 3 (b) 0 3 0 1 0 3 (c) 0 0 2 5 0 1 (d) 0 0 0 3 0 1 (e) 0 5 3 0 2 2 (f) 10 2 0 0 8 0 Figure 10: Occurrences of cases arising from duplicate estimates over, under or exactly estimating a given coefficient in the linear models describing the pole-and-cart data. The cases (a) – (f) are as described in the text. As before, estimates and expected values are recorded up to 3 significant figures. In the experiments undertaken, the reader would have noticed that the target equations for ¨xrequire the values of ¨ θand vice-versa and that Progol obtained these values directly from the tabulated records. It is of interest to examine whether the ILP program could achieve comparable results by calculating the derivatives required by using background knowledge definitions for numerical differentiation. This would allow the ILP program to emulate other, more special purpose programs like LAGRANGE [8]. We close this discussion with a demonstration that such behaviour is possible by extracting constraints for ¨xand ¨ θusing x, ˙x, θ, and ˙ θin conjunction with a well-known 5-point formula for numerical differentiation. Examples are time-indexed to allow such a calculation. The physical parameters remain as before, namely F=±10N, m = 0.1kg, M = 1.0kg, and the corresponding mean-square-error on the test sample is in Figure 11. The errors can be seen to be comparable to the corresponding ones obtained earlier in Figures 22 5 and 6. However, it is important to note here that the 5-point formula for numerical derivatives are not calculable for examples that are too close to the edges of a run. Prediction of values is thus possible for only a subset of the data – an issue that is not peculiar to the use of Progol, but one that arises from the particular numerical method employed to obtain derivatives. Variable Mean square error ¨x3e−5 ¨ θ2e−3 Figure 11: Mean square error of Progol predictions for ¨xand ¨ θon test examples with programs for numerical differentiation provided as background knowledge. The notation ae −bstands for a×10−b. Note that the errors reported are calculated only on those examples in the test-set for which numerical derivatives are defined. 5.5 Conclusion The experiments in this section have concentrated on the relatively welldefined world of the pole-and-cart. The conclusions to be drawn from this are straightforward, namely: (1) when the data are fully predictable from simple linear equations, linear modelling does as well or better than methods unable to express such models; and (2) regression used within an ILP harness to exhaust the subsets of possibly predictive independent variables does better than following the greedy strategy of “stepwise” regression. There are thus, no surprises at all for data analysts. The experiments do however serve to illustrate the possibility of using statistical and numerical predicates within an ILP program. We now consider a case where there are no known models for predicting the data. This provides a sterner test of the capabilities of the ILP program. 6 Experiment 2: mutagenesis There are two broad stages in rational drug design [39]. The first involves the identification of one or more compounds – known as leads – with some suitable biological activity. This activity is obtained from historical records, 23 or chemical assays. The second stage involves optimising the activity of these leads. Typically, the medicinal chemist has access to the 2 and 3dimensional structure of the possible leads, along with their activities. Empirical Structure-Activity Relationships – or SARs – are concerned with obtaining accurate descriptions that describe levels of biological activity in terms of molecular structure. These descriptions can then be used to direct the synthesis of new compounds, possibly culminating in a new drug. The SAR problem here is taken from the chemical literature as reported by [6]. The authors are concerned with obtaining SARs describing mutagenicity in nitroaromatic compounds. These compounds occur in automobile exhaust fumes and are also common intermediates in the synthesis of many thousands of industrial compounds [6]. Highly mutagenic nitroaromatics have been found to be carcinogenic, and it is of considerable interest to the pharmaceutical industry to determine which molecular features result in compounds having mutagenic activity. Since its introduction in [45], the problem has become an important testbed for ILP programs. Most of this research has however concentrated in obtaining rules for classifying the compounds into one of several categories, although the original problem is concerned with the quantitative task of predicting actual mutagenic activity. In [6] the authors list the activity of 230 compounds, obtained from a procedure known as the Ames test. They further identify this set as being composed of two disparate groups of 188 and 42 compounds respectively. The first group is adequately explained by linear modelling using 5 specifically selected predictor variables. The remaining 42 compounds however form an “outlier” group for which no explanatory model has been proposed by the chemists. It is this subset of compounds that are of particular interest to us. They provide the opportunity of examining whether the first-order capabilities of a program like Progol provide the edge required to find explanatory models. This capability allows Progol to include relational descriptions in terms of molecular structure, thus going beyond the routine use of propositional algorithms like regression. Recent work on this subset of data [44] examines augmenting the independent variables used by linear regression with new “features” constructed by an ILP program. In some sense, the technique used in this paper can be seen as a dual to that work (in which the results of an ILP program are used by linear regression). The advantage of the technique adopted here, as seen below, is that it allows a uniform treatment of mixed class types (that is, both numerical and nominal). 24 6.1 Experimental aims For the 42 nitroaromatic molecules not explained by chemists: 1. Determine if Progol, equipped with background definitions for describing molecular structure, the expert selected predictor variables, and statistical predicates is capable of obtain an explanation for the mutagenic activity of the molecules. 2. Compare the predictions made by the Progol theory and those made by regression, regression-tree and neural-network methods using the expert selected predictor variables only. We note here that a chemical evaluation of any theory constructed by Progol is beyond the scope of this paper. 6.2 Materials 6.2.1 Data Data are available for the mutagenic activity of 42 compounds. Of these, 20 compounds have recordable levels of activity. The activity of the remaining 22 compounds is below the minimum levels measurable. These have been marked simply as “very low”. This poses special problems for programs that are incapable of dealing with mixed data types. While there is no natural notion of “negative” examples for the 20 compounds for which numeric activity levels are available, it is possible to view them as acting as negative examples when learning rules for “very low” activity (that is, for the remaining 22 compounds). 6.2.2 Background knowledge for ILP Besides the 5 predictor variables devised by the chemists (see Section 6.2.3), Progol has the following additional information as background knowledge (complete Prolog listings of these are available in [43]): 1. Molecular structure. These are primitive structural descriptions in terms of the atom and bond structures in each molecule, along with associated information concerning atom/bond types. They are represented by a pair of predicates atm/5 and bond/4 (as in [15]), and are obtained automatically from a molecular modelling package. 25 [3] R. Camacho. Learning stage transition rules with Indlog. In S. Wrobel, editor, Proceedings of the Fourth International Inductive Logic Programming W orkshop. Gesellschaft fur Mathematik und Datenverarbeitung MBH, 1994. GMD-Studien Nr 237. [4] R. H. Cannon. Dynamics of physical systems. McGraw-Hill, New York, 1967. [5] European Commission. ESPRIT Long Term Research Project 20237 – ILP II. Technical Annex I, European Commission, Directorate General, Industry, Brussels, 1996. [6] A.K. Debnath, R.L Lopez de Compadre, G. Debnath, A.J. Schusterman, and C. Hansch. Structure-Activity Relationship of Mutagenic Aromatic and Heteroaromatic Nitro compounds. Correlation with molecular orbital energies and hydrophobicity. Journal of Medicinal Chemistry, 34(2):786 – 797, 1991. [7] B. Dolsak and S. Muggleton. The application of Inductive Logic Programming to finite element mesh design. In S. Muggleton, editor, Inductive Logic Programming, pages 453–472. Academic Press, London, 1992. [8] S. Dˇzeroski and L. Todorovski. Discovering dynamics: From inductive logic programming to machine discovery. Journal of Intelligent Information Systems, 4:89–108, 1995. [9] S. Dzeroski. Numerical Constraints and Learnability in Inductive Logic Programming. University of Ljubljana, (PhD. Thesis), Ljubljana, 1995. [10] S. Dzeroski, L. Dehaspe, B. Ruck, and W. Walley. Classification of river water quality data using machine learning. In Proceedings of the Fifth International Conference on the Development and Application of Computer Techniques Environmental Studies, 1994. [11] C. Feng. Inducing temporal fault dignostic rules from a qualitative model. In S. Muggleton, editor, Inductive Logic Programming, pages 473–486. Academic Press, London, 1992. [12] C.D. Page Jr. and A.M. Frisch. Generalization and Learnability: A Study of Constrained Atoms. In S. Muggleton, editor, Inductive Logic Programming, pages 29–56. Academic Press, London, 1992. 32 [13] A. Karalic. Relational regression: first steps. Technical report ijs-dp7001, J. Stefan Institute, Ljubljana, Yugoslavia, 1994. [14] A. Karalic and I. Bratko. First-Order Regression. Machine Learning Journal, 26:147–176, 1997. Special Issue on ILP. [15] R.D. King, S.H. Muggleton, A. Srinivasan, and M.J.E. Sternberg. Structure-activity relationships derived by machine learning: The use of atoms and their bond connectivities to predict mutagenicity by inductive logic programming. Proc. of the National Academy of Sciences, 93:438–442, 1996. [16] R.D. King, S.H. Muggleton, and M.J.E. Sternberg. Drug design by machine learning: The use of inductive logic programming to model the structure-activity relationships of trimethoprim analogues binding to dihydrofolate reductase. Proc. of the National Academy of Sciences, 89(23):11322–11326, 1992. [17] S. Kramer. Structural regression trees. In Proc. of the Thirteenth National Conference on Artificial Intelligence (AAAI-96), pages 812– 819. MIT Press, 1996. [18] N. Lavrac and S. Dzeroski. ILP: Techniques and Applications. Ellis Horwood, London, 1994. [19] J.W. Lloyd. Foundations of Logic Programming. Springer-Verlag, Berlin, 1984. [20] D. Michie and R.A. Chambers. BOXES: An experiment in adaptive control. In E. Dale and D. Michie, editors, Machine Intelligence 2, pages 137–152. Oliver and Boyd, Edinburgh, 1968. [21] F. Mizoguchi and H. Ohwada. An Inductive Logic Programming approach to constraint acquisition for constraint-based problem solving. In L. De Raedt, editor, Fifth International Inductive Logic Programming Workshop. Katholieke Universiteit Leuven, Heverlee, Belgium, 1995. [22] S. Muggleton. Inductive logic programming. New Generation Computing, 8(4):295–318, 1991. [23] S. Muggleton. Inductive Logic Programming: derivations, successes and shortcomings. SIGART Bulletin, 5(1):5–11, 1994. 33 [24] S. Muggleton. Inverse Entailment and Progol. New Gen. Comput., 13:245–286, 1995. [25] S. Muggleton. Learning from positive data. In Proceedings of the Sixth Inductive Logic Programming Workshop, LNAI, pages 358–376, Berlin, 1996. Springer-Verlag. [26] S. Muggleton, R. King, and M. Sternberg. Predicting protein secondary structure using inductive logic programming. Protein Engineering, 5:647–657, 1992. [27] S. Muggleton, C.D. Page, and A. Srinivasan. An initial experiment into stereochemistry-based drug design using ILP. In Proceedings of the Sixth Inductive Logic Programming Workshop, LNAI, Berlin, 1996. Springer-Verlag. [28] S. Muggleton and D. Page. Beyond first-order learning: inductive learning with higher-order logic. PRG-TR 13-94, Oxford University Computing Laboratory, Oxford, 1994. [29] S.H. Muggleton and C. Feng. Efficient induction of logic programs. In Proceedings of the First Conference on Algorithmic Learning Theory, Tokyo, 1990. Ohmsha. [30] M.J. Norusis. SPSS: Base System User Guide. Release 6.0. SPSS Inc., 444 N Michigan Ave, Chicago, Illinois 60611, 1994. [31] University of Stuttgart. Snns user manual, version 4.1. Technical Report 6/95, Institute for Parallel and Distributed High Performance Systems, Stuttgart, 1995. [32] G.D. Plotkin. Automatic Methods of Inductive Inference. PhD thesis, Edinburgh University, August 1971. [33] J.R. Quinlan. Learning logical definitions from relations. Machine Learning, 5:239–266, 1990. [34] J.R. Quinlan. Learning with Continuous Classes. In A. Adams and L.Sterling, editors, Proceedings of the Fifth Australian Joint Conference on Artificial Intelligence, pages 343–348, Singapore, 1992. World Scientific. 34 [35] J.R. Quinlan and R.M. Cameron-Jones. Efficient top-down induction of logic programs. SIGART Bulletin, 5(1):33–42, 1994. [36] L. De Raedt and L. Dehaspe. Clausal Discovery. Technical Report CW 238, Katholieke Universiteit Leuven, Heverlee, Belgium, 1996. [37] L. De Raedt and L. Dehaspe. Clausal Discovery. Machine Learning, 26:99–146, 1997. Special Issue on ILP. [38] L. De Raedt and S. Dzeroski. First order jk-clausal theories are PAClearnable. Artificial Intelligence, 70:375–392, 1994. [39] C.A. Ramsden. Comprehensive medicinal chemistry (vol 4). Pergamon Press, Oxford, 1979. [40] J.O. Rawlings. Applied regression analysis : a research tool. Wadsworth and Brooks, Pacific Grove, California, 1988. [41] M. Sebag and C. Rouveirol. Constraint Inductive Logic Programming. In L. De Raedt, editor, Fifth International Inductive Logic Programming Workshop. Katholieke Universiteit Leuven, Heverlee, Belgium, 1995. [42] E.Y. Shapiro. Algorithmic program debugging. MIT Press, 1983. [43] A. Srinivasan and R.C. Camacho. Experiments in numerical reasoning with ILP. Technical Report PRG-TR-22-96, Oxford University Computing Laboratory, Oxford, 1996. [44] A. Srinivasan and R.D. King. Feature construction with inductive logic programming: a study of quantitative predictions of biological activity aided by structural attributes. In Proceedings of the Sixth Inductive Logic Programming Workshop, LNAI, Berlin, 1996. Springer-Verlag. [45] A. Srinivasan, S.H. Muggleton, R.D. King, and M.J.E. Sternberg. Mutagenesis: ILP experiments in a non-determinate biological domain. In S. Wrobel, editor, Proceedings of the Fourth International Inductive Logic Programming Workshop. Gesellschaft fur Mathematik und Datenverarbeitung MBH, 1994. GMD-Studien Nr 237. [46] R.E. Walpole and R.H. Myers. Probability and Statistics for Engineers and Scientists. Collier Macmillan, New York, 1978. 2nd Edition. 35 [47] S.M. Weiss and C.A. Kulikowski. Computer systems that learn. Morgan Kaufmann, San Mateo, CA, 1991. [48] D.M. Young and R.T. Gregory. A Survey of Numerical Mathematics, Volume I. Addison-Wesley, Reading, MA, 1972. [49] J. Zelle and R. Mooney. Learning semantic grammars with constructive inductive logic programming. In Proceedings of the Eleventh National Conference on Artificial Intelligence, pages 817–822. Morgan Kaufmann, 1993. A Examples of implementation changes This section gives some examples of the implementation, within P-Progol 2.3, of two changes proposed in Section 3 namely, lazy evaluation and userdefinable search functions. A.1 Lazy evaluation We demonstrate here the construction of a regression line between a pair of points. Suppose E+={p(0,1) ←, p(8,4) ←},E−=∅, and Bcontains a correct definition for computing least-square estimates for the slope (M) and intercept (K) of line drawn through a set of points. The target therefore, is to construct a clause of the form p(X, Y )←line(X, Y, m, k), where m, k are some specific values for M, K, with the first two arguments of line are “input”, and the remainder are constants to be computed lazily. In executing the lazy evaluation procedure described in Figure 2, the following steps are followed: lazyeval(l, C, h, B, E+, E−) 1. Here l=line(X, Y, ∃M, ∃K), C =p(X, Y ), E+={p(0,1), p(8,4)}, E−= ∅,B, h are given 2. Then θX p={X/0, X/8},θX n=∅and θY p={Y/1, Y/4},θY n=∅ 3. Call LINE([θX p, θX n],[θY p, θY n], M, K) 4. Background Bcontains definition LINE/4 that returns (within hresolution steps) the answer substitution {M/0.375, K/1}. Search now proceeds with the clause p(X, Y )←line(X, Y, 0.375,1). 36 A.2 User-defined search We give examples of the the three different search operations described in Section 3. Consider for example, the task undertaken in [27]. There, the task set for the ILP program is to find within an organic molecule, a conjunction functional classes – like hydrogen donors, hydrogen acceptors, and zincbinding sites – and the 3-dimensional distances between such classes. In [27] the authors use a rather circuitous method of specifying this requirement. The following refine clauses within Progol achieve the same effect more directly (we do not show definitions for auxiliary predicates like member and dist). refine(false,active(A)). refine(active(A),Clause):- member(Pred1,[hacc(A,B),hdonor(A,B),zincsite(A,B)]), member(Pred2,[hacc(A,C),hdonor(A,C),zincsite(A,C)]), member(Pred3,[hacc(A,D),hdonor(A,D),zincsite(A,D)]), member(Pred4,[hacc(A,E),hdonor(A,E),zincsite(A,E)]), Clause = (active(A):- Pred1, Pred2, dist(A,B,C,D1,E1), Pred3, dist(A,B,D,D2,E2), dist(A,C,D,D3,E3), Pred4, dist(A,B,E,D4,E4), dist(A,C,E,D5,E5), dist(A,D,E,D6,E6)). Cost specification takes the form of definition of a 3-place predicate. The one extra argument is an efficiency concern that provides some pre-computed statistics of the clause (like number of positive and negative examples derivable and clause length). Here are the cost functions used in the experiments in this paper – again without detail of intermediate predicates. % cost is mean-square-error for numeric calculations cost((Head:-Body),Label,Cost):- mse(Head,Body,Cost), Cost \= undef, !. % otherwise cost is compression cost(_,[P,N,L],Cost):- P > L, N = 0, !, Cost is -P. cost(_,_,inf). 37 A typical use of pruning statements may be to remove redundant literals in a search. A case in point are implication relationships arising from inequalities. Here is an example resulting from addition of a literal performing an inequality test. In the definition below, in(L1,L2) is a predicate that checks if a literal L1 is in a conjunction L2, and add(L1,L2,L3) adds a literal L1 to the end of a sequence of conjoined literals L2 to give L3. prune((Head:-Body)):- add((X =< N2),L,Body), in((Y =< N1),L), X == Y, N1 =< N2. B The pole-and-cart model Exact equations of motion for the pole-and-cart system are available in the literature, and we do not include their derivation here. For this, the reader is referred to the treatment in [4], pp 703-710. Instead, we merely reproduce the relevant equations here. The state of the system is given by θ: the angle of the pole from the upright position; ˙ θ: angular velocity of the pole; x: horizontal position of the cart’s center; and ˙x: the velocity of the cart. Given a force on the cart of fixed magnitude F, and a pole of length l, cart and pole masses of Mand m, the equations of motion are: (M+m)¨x+1 2ml(¨ θcosθ −˙ θ2sinθ) = F ¨xcosθ +2 3l¨ θ=gsinθ These can be re-arranged to give constraints for ¨xand ¨ θ: ¨x=F−1 2ml(¨ θcosθ −˙ θ2sinθ) M+m ¨ θ=gsinθ −¨xcosθ 2 3l C A selection of theories obtained from Progol C.1 Pole-and-cart Actual Prolog definitions found by Progol are only of interest for syntactic reasons, and are presented for one configuration only. A mathematical 38 representation of all equations obtained follow, and can be used to understand better the Prolog representation. In constructing these clauses, Progol treated lin regress2 as a lazily-evaluated literal, and the constants that appear are a result of the implementation described earlier. Thus, the literal lin regress2(G,I,K,14.667,-1.560,0.583,0.044,L) encodes the regression line G= 14.667 ×I−1.56 ×K+ 0.583, with standard deviation s= 0.044 and standard residual L. % F = +/- 10, m = 0.1, M = 1.0 accel(A,B,C,D,E,F,f(10.000),G,H) :- sin(A,B,E,I), cos(A,B,E,J), mult(A,B,J,H,K), lin_regress2(G,I,K,14.667,-1.560,0.583,0.044,L), lte(L,2.000). accel(A,B,C,D,E,F,f(-10.000),G,H) :- sin(A,B,E,I), cos(A,B,E,J), mult(A,B,J,H,K), lin_regress2(G,I,K,14.686,-1.565,-0.633,0.040,L), lte(L,2.000). accel(A,B,C,D,E,F,f(10.000),G,H) :- sin(A,B,E,I), cos(A,B,E,J), mult(A,B,J,G,K), pow(A,B,F,2,L), mult(A,B,I,L,M), lin_regress2(H,M,K,0.046,-0.046,9.088,0.003,N), lte(N,2.000). accel(A,B,C,D,E,F,f(-10.000),G,H) :- sin(A,B,E,I), cos(A,B,E,J), mult(A,B,J,G,K), pow(A,B,F,2,L), mult(A,B,I,L,M), lin_regress2(H,M,K,0.047,-0.046,-9.090,0.003,N), lte(N,2.000). C.2 Mutagenesis The complete theory in Prolog form is shown below. The text translation appearing in Figure 14 is of the non-ground clauses below. Both lin regress2 and expected value4 are lazily evaluated. The literal expected value(B,1.38,0.6144,F) states that the set of values Bhave expected value 1.38 with standard deviation s= 0.6144, and standard residual F. active(A,B) :- lumo(A,C), lteq(C,-1.35), logp(A,D), atm(A,E,c,22,F), bond(A,E,G,7), lin_regress2(B,C,D,-2.902,1.499,-12.72,0.6289,H), lte(H,2). active(A,B) :- atm(A,C,c,14,D), lteq(D,0.608), bond(A,C,E,1), expected_value(B,1.38,0.6144,F), lte(F,2). active(A,vlow) :- atm(A,B,o,45,C). active(e10,vlow). active(e11,vlow). active(e6,vlow). active(e16,vlow). active(e14,vlow). active(e3,vlow). active(e18,vlow). active(e24,vlow). active(e21,vlow). active(e9,vlow). active(e13,vlow). active(e12,vlow). active(e4,vlow). active(e7,vlow). active(e8,vlow). active(e5,vlow). 39 F m/M Target equation Equation obtained 0 0.1¨ θ= 0.0 + 14.7sinθ −1.5¨xcosθ ¨ θ=−0.002 + 12.644sinθ −4.543¨xcosθ ¨x= 0.0−0.045¨ θcosθ + 0.045 ˙ θ2sinθ ¨x= 0.0−0.045¨ θcosθ + 0.043 ˙ θ2sinθ 1.0¨ θ= 0.0 + 14.7sinθ −1.5¨xcosθ ¨ θ=−0.0003 −4.099¨xcosθ + 1.067 ˙ θ2sinθ ¨x= 0.0−0.25¨ θcosθ + 0.25 ˙ θ2sinθ ¨x= 0.0−0.25¨ θcosθ + 0.247 ˙ θ2sinθ 10.0¨ θ= 0.0 + 14.7sinθ −1.5¨xcosθ ¨ θ= 0.0 + 13.182sinθ −1.581¨xcosθ ¨x= 0.0−0.45¨ θcosθ + 0.45 ˙ θ2sinθ ¨x= 0.0−0.455¨ θcosθ + 0.457 ˙ θ2sinθ +10 0.1¨ θ= 0.0 + 14.7sinθ −1.5¨xcosθ ¨ θ= 0.253 + 14.68sinθ −1.526¨xcosθ ¨x= 9.09 −0.045¨ θcosθ + 0.045 ˙ θ2sinθ ¨x= 9.091 −0.045¨ θcosθ + 0.045 ˙ θ2sinθ 1.0¨ θ= 0.0 + 14.7sinθ −1.5¨xcosθ ¨ θ= 0.041 + 14.647sinθ −1.510¨xcosθ ¨x= 5.0−0.25¨ θcosθ + 0.25 ˙ θ2sinθ ¨x= 5.0−0.25¨ θcosθ + 0.251 ˙ θ2sinθ 10.0¨ θ= 0.0 + 14.7sinθ −1.5¨xcosθ ¨ θ= 0.0004 + 14.692sinθ −1.5¨xcosθ ¨x= 9.09 −0.45¨ θcosθ + 0.45 ˙ θ2sinθ ¨x= 9.094 −0.454¨ θcosθ + 0.453 ˙ θ2sinθ ±10 0.1¨ θ= 0.0 + 14.7sinθ −1.5¨xcosθ (F= +10) ¨ θ= 0.583 + 14.667sinθ −1.56¨xcosθ ¨ θ= 0.0 + 14.7sinθ −1.5¨xcosθ (F=−10) ¨ θ=−0.633 + 14.686sinθ −1.565¨xcosθ ¨x= 9.09 −0.045¨ θcosθ + 0.045 ˙ θ2sinθ (F= +10) ¨x= 9.088 −0.046¨ θcosθ + 0.046 ˙ θ2sinθ ¨x=−9.09 −0.045¨ θcosθ + 0.045 ˙ θ2sinθ (F=−10) ¨x=−9.09 −0.046¨ θcosθ + 0.047 ˙ θ2sinθ 1.0¨ θ= 0.0 + 14.7sinθ −1.5¨xcosθ (F= +10) ¨ θ= 0.556 + 14.338sinθ −1.57¨xcosθ ¨ θ= 0.0 + 14.7sinθ −1.5¨xcosθ (F=−10) ¨ θ=−0.574 + 14.314sinθ −1.573¨xcosθ ¨x= 5.0−0.25¨ θcosθ + 0.25 ˙ θ2sinθ (F= +10) ¨x= 5.103 −0.016¨ θcosθ + 0.241 ˙ θ2sinθ ¨x=−5.0−0.25¨ θcosθ + 0.25 ˙ θ2sinθ (F=−10) ¨x=−5.001 −0.250¨ θcosθ + 0.249 ˙ θ2sinθ 10.0¨ θ= 0.0 + 14.7sinθ −1.5¨xcosθ (F= +10) ¨ θ= 0.075 + 14.639sinθ −1.503¨xcosθ ¨ θ= 0.0 + 14.7sinθ −1.5¨xcosθ (F=−10) ¨ θ=−0.044 + 14.634sinθ −1.502¨xcosθ ¨x= 9.09 −0.45¨ θcosθ + 0.45 ˙ θ2sinθ (F= +10) ¨x= 9.096 −0.454¨ θcosθ + 0.451 ˙ θ2sinθ ¨x=−9.09 −0.45¨ θcosθ + 0.45 ˙ θ2sinθ (F=−10) ¨x=−9.096 −0.454¨ θcosθ + 0.453 ˙ θ2sinθ Figure 15: Descriptions of equations obtained by Progol on the pole-and-cart data. 40