Learning Qualitative Models from Numerical Data: Extended abstract

1 Introduction

People most often reason qualitatively. For example, playing with a simple pendulum, a five year old child discovers that the period of the pendulum increases if he uses a longer rope. Although most of us are later taught a more accurate numerical model describing the same behaviour, T = 2⇡pl◁g, we keep relying on the more "operational" qualitative relation in everyday's life. Still, despite Turing's proposition that artificial intelligence should mimic human intelligence, not much work has been done so far in trying to learn such models from data.

We can formally describe the relation between the period of a pendulum T, its length l and the gravitational acceleration g as T = Q(+l↪-g), meaning that the period increases with l and decreases with g. Our definition of qualitative relatonship is based on partial derivatives: a function f is in positive (negative) qualitative relation with x over a region R if the partial derivative of f with respect to x is positive (negative) over the entire R,

and

⇤This paper is an extended abstract of the AI Journal publication [ ˇZabkar et al., 2012].

Qualitative models are predictive models that describe qualitative relations between input variables and a continuous output, for instance

For the sake of clarity, we omitted specifying the region since it is obvious from the context.

In this paper we propose a new, two-step approach to induction of qualitative models from data. Let the data describe a sampled function given as a set of examples (x↪ y), where x are attributes and y is the function value. In the first step we estimate the partial derivative at each point covered by a learning example. We replace the value of the output y for each example with the sign of the corresponding derivative q. Each relabelled example, (x↪ q), describes the qualitative behaviour of the function at a single point. In the second step, a general-purpose machine learning algorithm is used to generalize from this relabelled data, resulting in a qualitative model describing the function's (qualitative) behaviour in the entire domain. Such models describe the relation between the output and a single input variable in dependence of other attributes.

The paper includes three major contributions: (1) the idea of transforming the problem of learning qualitative models to that of learning ordinary predictive models, (2) a new method called Pad´e for computing partial derivatives from data typical for machine learning, (3) an extensive experimental evaluation of the proposed setup.

The papers by Forbus [Forbus, 1984], de Kleer and Brown [de Kleer and Brown, 1984], and Kuipers [Kuipers, 1986] describe approaches that became the foundations of much of qualitative reasoning work in AI. Kalagnanam et al. [Kalagnanam et al., 1991; Kalagnanam, 1992; Kalagnanam and Simon, 1992] contributed to the mathematical foundations of qualitative reasoning.

There are a number of approaches to qualitative system identification, also known as learning qualitative models from data. Most of this work is concerned with the learning of QDE (Qualitative Differential Equations) models, e.g. GENMODEL [Coiera, 1989; Hau and Coiera, 1997], MISQ [Ramachandran et al., 1994; Richards et al., 1992] and QSI [Say and Kuru, 1996]. Similarly, a general purpose ILP system (Inductive Logic Programming) to induce a model from qualitative behaviours [Bratko et al., 1991; Coghill and King, 2002; Coghill et al., 2008].

The QUIN algorithm [ˇSuc and Bratko, 2001; ˇSuc, 2003; Bratko and ˇSuc, 2003] is the most relevant to the present paper. QUIN induces qualitative trees by computing the qualitative change vectors between all pairs of points in the data and then recursively splitting the space into regions which share common qualitative properties. Despite similarities, Pad´e and QUIN are significantly different in that Pad´e acts as a preprocessor of numerical data and can be used in combination with any attribute-value learning system. Pad´e computes qualitative partial derivatives in all example data points, and these derivatives become class values for the subsequent learning.

We overview the related work extensively in [ ˇZabkar et al., 2011].

2 Computation of Partial Derivatives

We will denote a learning example as (x↪ y), where x = (x1↪ x2↪ ▷ ▷ ▷ xn) and y is the value of the unknown sampled function, y = f(x).

We will introduce three methods for estimation of partial derivative of f at point x0. The simplest one assumes that the function is linear in a small hyper-sphere around x0 (Figure 1a). It computes locally weighted linear regression on examples lying in the hyper-sphere and considers the computed coefficients as partial derivatives. The second method, ⌧-regression, computes a single partial derivative at a time. To avoid the influence of other arguments of the function, it considers only those points in the sphere which lie in a hypertube along the axis of differentiation (Figure 1b). The derivative can then be computed with weighted univariate regression. Finally, the parallel pairs method replaces the single hyper-tube with a set of pairs aligned with the axis of differentiation (Figure 1c), which allows it to focus on the direction of differentiation without decreasing the number of examples considered in the computation.

2.1 Locally weighted regression

Let N(x0) be a set of examples (xm↪ ym) such that xmi ⇡ x0i for all i (Figure 1a). According to Taylor's theorem, a differentiable function is approximately linear in a neighbourhood of x0,

Our task is to find the vector of partial derivatives, rf(x0). We can solve this as a linear regression problem by rephrasing (3) as a linear model

The size of the neighbourhood N(x0) should reflect the density of examples and the amplitude of noise. Instead of setting a predefined radius (e.g. ♣♣xm-x0♣♣ < δ), we consider a neighbourhood of k nearest examples and weigh the points according to their distance from x0,

The parameter σ2 is fitted so that the farthest example has a negligible weight of 0.001.

This transforms the problem into locally weighted regression (LWR) [Atkeson et al., 1997], where the regression coefficients represent partial derivatives,

where

The computed β estimates the vector of partial derivatives rf (x0).

As usual in linear regression, the inverse in (6) can be replaced by pseudo-inverse to increase the stability of the method.

2.2 ⌧-regression

The ⌧-regression algorithm differs from LWR in the shape of the neighbourhood of the reference point. It starts with  examples in a hyper-sphere, which is generally larger than that for LWR, but then keeps only k examples that lie closest to the axis of differentiation (Figure 1b). Let us assume without loss of generality that we compute the derivative with regard to the first argument x1. The neighbourhood N(x0) thus contains k examples with the smallest distance ♣♣xm - x0♣♣∩1 chosen from the  examples with the smallest distance ♣♣xm - x0♣♣, where ♣♣ · ♣♣∩i represents the distance computed over all dimensions except the i-th.

With a suitable selection of  and k, we can assume xm1 - x01 ≫ xmi - x0i for all i > 1 for most examples xm. If we also assume that partial derivatives with regard to different arguments are comparable in size, we get @f◁@x1(xm1 - x01) ≫ @f◁@xi(xmi - x0i) for i > 1. We can thus omit all dimensions but the first from the scalar product in (3):

for (xm↪ ym) 2 N(x0). We again set up a linear model,

where β1 approximates the derivative @f @x1 (x0). The task is to find the value of β1 which minimizes error over N(x0).

Examples in N(x0) are weighted according to their distance from x0 along the axis of differentiation,

where σ is again set so that the farthest example has a weight of 0.001.

The described linear model can be solved by weighted univariate linear regression over the neighbourhood N(x0),

2.3 Parallel pairs

Consider two examples (xm↪ ym) and (xl↪ yl) which are close to x0 and aligned with the x1 axis, ♣♣xm-xl♣♣ ⇡ ♣xm1-xl1♣. Under these premises we can suppose that both examples correspond to the same linear model (9) with the same coefficients β0 and β1. Subtracting (9) for ym and yl gives

or

To assess the accuracy of induced models, we compute the derivatives and the model from the entire data set. We then check whether the predictions of the model match the analytically computed partial derivatives. We define the accuracy of Pad´e as the proportion of examples with correctly predicted qualitative partial derivatives. Note that this procedure does not require separate training and testing data set since the correct answer with which the prediction is compared is not used in induction of the model. Where not stated otherwise, experimental results represent averages of ten trials. For LWR, we used ridge regression to compute the ill-posed inverse in (6).

We performed experiments with three mathematical functions: f(x↪ y) = x2 - y2 , f(x↪ y) = x3 - y, f(x↪ y) = sinxsiny. We sampled them uniform randomly in 1000 points in the range [-10↪ 10] ⇥ [-10↪ 10].

Function f(x↪ y) = x2 -y2 is a standard test function often used in [ ˇSuc, 2003]. Its partial derivative w.r.t. x is @f◁@x = 2x, so f = Q(+x) if x > 0 and f = Q(-x) if x < 0. Since the function's behaviour with respect to y is similar, we observed only results for @f◁@x. The accuracy of all methods is close to 100% (Table 1). Changing the values of parameters

where y(m↪l) = ym - yl and x(m↪l)1 = xm1 - yl1. The difference ym - yl is therefore linear with the difference in the attribute values xm1 and xl1

Coefficient β1 again approximates the derivative @f @x1 (x0). Note that the model has no intercept term, β0.

To compute the derivative using (12) we take the spherical neighbourhood like the one from the first method, LWR. For each pair we compute its alignment with the x1 axis using a scalar product with the base vector e1,

We select the k best aligned pairs from  points in the hypersphere around x0 (Figure 1c) and assign them weights corresponding to the alignment,

with σ2 set so that the smallest weight equals 0.001.

The derivative is again computed using univariate linear regression, @f @x1 (x0) = β1 =

3 Experiments

We present the experiments on artificially constructed data sets to test Pad´e with respect to accuracy and the effect of noise in the data. Further experiments are described in [ ˇZabkar et al., 2011].

has no major effect except for ⌧ regression, where short ( = 30 and  = 50) and wide (k ≥ 10) tubes give better accuracy while for very long tubes ( = 100) the accuracy decreases with k. The latter can indicate that longer tubes reach across the boundary between the positive and negative values of x. Induced tree models have the same high accuracy.

Function f(x↪ y) = x3 - y is globally monotone, increasing in x and decreasing in y in the whole region. The function is interesting because its much stronger dependency on x can obscure the role of y. All methods have a 100% accuracy with regard to x. Prediction of function's behaviour w.r.t. y proves to be difficult: the accuracy of ⌧ -regression is 50-60% and the accuracy of LWR is just over 70% (Table 2). Parallel pairs seem undisturbed by the influence of x and estimate the sign of @f◁@y with accuracy of more than 95% with proper parameter settings.

An interesting observation here is that the accuracy of induced qualitative tree models highly exceeds that of pointwise partial derivatives. For instance, qualitative models for derivatives by LWR reach 95-100% despite the low, 70% accuracy of estimates of the derivative. When generalizing from labels denoting qualitative derivatives, incorrect labels are scattered randomly enough that C4.5 recognizes them as noise and induces a tree with a single node.

Function f(x↪ y) = sinxsiny has partial derivatives @f◁@x = cos x sin y and @f◁@y = cos y sin x, which change their signs multiple times in the observed region. The accuracy of all methods is mostly between 80 and 90 percent, degrading with larger neighbourhoods (Table 3). However, the accuracy of C4.5 barely exceeds 50% which we would get by making random predictions. Rather than a limitation of Pad´e, this shows the (expected) inability of C4.5 to learn this checkboard-like concept.

Finally, we add various amounts of noise to the function value. The target function is f(x↪ y) = x2 - y2 defined on [-10↪ 10]⇥[-10↪ 10] which puts f in [-100↪ 100]. We added Gaussian noise with a mean of 0 and variance 0, 10, 30, and 50, i.e. from no noise to the noise in the range comparable Table 4: Effect of noise on the accuracy of computed qualitative partial derivatives for f(x↪ y) = x2 - y2 with random noise from N(0↪ σ).

(b) Correctness of qualitative models induced by C4.5

to the signal itself. We measured the accuracy of derivatives and models induced by C4.5. Since the data contains noise, we set the C4.5's parameter m (minimal number of examples in a leaf) to 10% of the examples of our data set, m = 100. We repeated the experiment with each amount of noise 100 times and computed the average accuracies.

The results are shown in Table 4. Pad´e is quite robust despite the huge amount of noise. As in other experiments on artificial data sets, we again observed that C4.5 is able to learn almost perfect models despite the drop in correctness of derivatives at higher noise levels.

4 Conclusion

We introduced a new approach to learning qualitative models which differs from existing approaches by its trick of translating the learning problem into a classification problem and then applying the general-purpose learning methods to solve it. We mostly explored the first step that involves the estimation of partial derivatives. The second step opens a number of other interesting research problems, which we leave open for further research in the area.