Martin V Butz
email: butz@psychologie.uni-wuerzburg.de

Olivier Sigaud
email: olivier.sigaud@upmc.fr

XCSF with Local Deletion: Preventing Detrimental Forgetting

Keywords: G.1.2 [Numerical Analysis]: Approximation-approximation of surfaces and contours, least squares approximation, nonlinear approximation; I.2.6 [Artificial Intelligence]: Learning Algorithms, Theory, Performance XCSF, function approximation, local deletion, unbalanced problem sampling, manifold

The XCSF classifier system solves regression problems iteratively online with a population of overlapping, local approximators. We show that problem solution stability and accuracy may be lost in particular settings -mainly due to XCSF's global deletion. We introduce local deletion, which prevents these detrimental effects to large extents. We show experimentally that local deletion can prevent forgetting in various problems -particularly where the problem space is non-uniformly or non-independently sampled. While we use XCSF with hyperellipsoidal receptive fields and linear approximations herein, local deletion can be applied to any XCS version where locality can be similarly defined. For future work, we propose to apply XCSF with local deletion to unbalanced, non-uniformly distributed, locally sampled problems with complex manifold structures, within which varying target error values may be reached selectively.

INTRODUCTION

Most challenging function approximation problems arise when the function class is unknown, which requires an online approximation of the function surface from incoming samples. Many regression algorithms are furthermore challenged when the sampled values are non-uniformly or nonindependently distributed. While facing these challenges, the applied regression algorithm is expected to yield results of a desired accuracy with a representation that approximates the function highly compactly. XCSF is a system that falls in this class of regression algorithms and that indeed also faces these challenges.

The XCS system was introduced in [START_REF] Wilson | Classifier fitness based on accuracy[END_REF] and was extended to the real-valued function approximation system XCSF in [START_REF] Wilson | Classifiers that approximate functions[END_REF]. In [START_REF] Butz | Kernel-based, ellipsoidal conditions in the real-valued XCS classifier system[END_REF], XCSF was modified to develop hyperellipsoidal receptive fields, that is, Gaussian kernels. In [START_REF] Butz | Function approximation with XCS: Hyperellipsoidal conditions, recursive least squares, and compaction[END_REF], XCSF with hyperellipsoids was extended with effective mutation operators and compared to similar state-of-the-art machine learning techniques, such as the constructive incremental learning approach [START_REF] Schaal | Constructive incremental learning from only local information[END_REF]. Most recently, it was shown that XCSF yields performance comparable or superior [START_REF] Stalph | A comparative study: Function approximation with LWPR and XCSF[END_REF] to the locally weighted projection algorithm (LWPR) [START_REF] Vijayakumar | Incremental online learning in high dimensions[END_REF] -a well-known tool in the learning robotics literature. Here, we investigate the performance of XCSF further and compare standard XCSF with a modified version, in which GA deletion is applied locally. The challenges we are facing are due to observations that XCSF sometimes does not yield stable approximation surfaces -particularly while applying condensation [START_REF] Wilson | Classifier fitness based on accuracy[END_REF][START_REF] Butz | Function approximation with XCS: Hyperellipsoidal conditions, recursive least squares, and compaction[END_REF]. Moreover, we are interested in approximating functions whose problem spaces are sampled non-uniformly or non-independently. We show that XCSF with local deletion (referred to as XCSFld) yields more stable and accurate function approximations in various problem settings. Additionally, we study approximation performance in lower dimensional manifolds, which are embedded in higher dimensional input spaces.

We now first motivate and detail the new local deletion mechanism. Next, we provide results for various problem sampling cases in the crossed-ridge function [START_REF] Schaal | Constructive incremental learning from only local information[END_REF][START_REF] Stalph | A comparative study: Function approximation with LWPR and XCSF[END_REF] and in the diagonal sine function [START_REF] Butz | Kernel-based, ellipsoidal conditions in the real-valued XCS classifier system[END_REF]. It is shown that local deletion yields performance that is either comparable or better than that of XCSF with global deletion. We conclude that local deletion is a powerful tool to avoid detrimental forgetting and to focus local search in XCSF.

XCSF WITH LOCAL DELETION

The evolutionary algorithm in XCSF can be characterized as a steady-state GA. Upon GA invocation, usually two classifiers are selected for reproduction in the current match set [M ]t at iteration t. Sometimes, it can also be advantageous to select a different amount of classifiers for reproduction (cf. [START_REF] Stalph | How fitness estimates interact with reproduction rates: Towards variable offspring set sizes in xcsf[END_REF]). More importantly for this study, however, is the fact that global deletion is applied [START_REF] Wilson | Classifier fitness based on accuracy[END_REF] -that is, classifiers are selected from the whole population for deletion.

This combination of local reproduction with global deletion yields a now well-documented evolutionary generalization pressure [START_REF] Butz | Toward a theory of generalization and learning in XCS[END_REF]: since the classifier conditions in the match set are on average more general (simply speaking, because more general classifiers will match more often on average) than the classifier conditions in the population as a whole, more general classifiers are favored during reproduction. The resulting generalization pressure has been quantified and verified exactly in various studies, cf. [START_REF] Butz | Toward a theory of generalization and learning in XCS[END_REF]. Recently, the same mechanism was also characterized in XCSF with respect to classifier volumes [START_REF] Butz | Function approximation with XCS: Hyperellipsoidal conditions, recursive least squares, and compaction[END_REF][START_REF] Stalph | Resource management and scalability of the XCSF learning classifier system[END_REF] and most of the theory of XCS was carried over to XCSF.

However, global deletion may result in the deletion of important classifiers when the problem space is non-uniformly sampled. For XCS, it has been shown that when the problem space is covered with highly overlapping conditions, local, random walk competitions can take place amongst the overlapping classifiers [START_REF] Butz | Problem solution sustenance in XCS: Markov chain analysis of niche support distributions and the impact on computational complexity[END_REF], which may lead to detrimental forgetting of small subspaces.

In data mining problems, it was shown that unbalanced data-sets may also lead to detrimental forgetting. In this case, the θGA threshold was reduced automatically, which results in a reduced reproduction rate in over-sampled problem subspaces [START_REF] Orriols-Puig | Facetwise analysis of xcs for problems with class imbalances[END_REF][START_REF] Orriols-Puig | Evolutionary rule-based systems for imbalanced data sets[END_REF]. However, the unbalance detection mechanism, which is used to tune the θGA threshold automatically, does not seem to be applicable in XCSF.

We propose to focus the deletion mechanism on the currently sampled, local sub-space, fostering local deletion. To avoid disrupting the generalization pressure of XCSF, mentioned above, a local deletion mechanism is necessary that does not favor more general classifiers. Deletion simply from the usual match set is not appropriate, because classifiers in the match set are on average more general than those in the whole population. Our mechanism deletes within the local sub-space, but it does not favor more general classifiers for deletion. The local subspace is determined by the condition of a randomly chosen classifier cl from the current match set. Classifiers whose condition center overlaps with the condition of cl are considered for deletion. Consequently, we scan the population for all those classifiers whose center of their condition are matched by the condition part of cl. The resulting subset of classifiers [D] is then treated as the candidate list for deletion -as previously the whole population was treated as the candidate list for deletion. Thus, the usual roulette wheel selection with the normal match set size estimate and accuracy estimate-based voting mechanism is applied in [D] -as it would be done in the population [P ] in the normal XCSF. That is, first the sum of all deletion votes in [D] is calculated and a classifier is chosen for deletion by roulette wheel selection. Next, the numerosity of that classifier is reduced by one. If its numerosity equals zero, it is deleted from the population. Algorithm 1 specifies this mechanism in algorithmic form. In the remainder of this work, we refer to this modification by XCSF with local deletion (XCSFld). which are sampled iteratively, that is, each time step a sample ( x, y) is given to the algorithm, where y = f ( x). The goal is to approximate the function surface online from the given samples. To increase the difficulty of the problem further, we add random Gaussian noise with a standard deviation of 0.001 to each sampled output value. The functions are defined in the interval [-1, 1] 2 . Without loss of generality, the input space is normalized to [0, 1] 2 for XCSF.

PERFORMANCE COMPARISON

-1 0 1 x1 -1 0 1 x2 1.25 0 0.5 1 f(x1,x2) (a) Crossed Ridge -1 0 1 x1 -1 0 1 x2 -1 0 1 f(x1,x2) (b) Sine
1. The Crossed Ridge function contains a mix of linear and non-linear subspaces.

f1(x1, x2) = max ˆexp(-10x 2 1 ), exp(-50x 2 2 ), 1.25 exp(-5(x 2 1 + x 2 2 )) 2.
The Sine function is constant in the (1, -1) direction but highly non-linear in the perpendicular (1, 1) direction.

f2(x1, x2) = sin (2π(x1 + x2))
Figure 1 shows surface plots of the two functions. We mostly use standard parameter settings for XCSF 1 , We conduct ten independent runs for each reported experimental setup. The currently sampled mean absolute prediction error (MAE), the root mean square error (RMS) of points sampled in a grid of 21 by 21 locations, as well as the 1 XCSF's parameters are set to N = 4000, ε0 = 0.002,

β = 0.1, δ = 0.1, α = 1, θGA = 50, θ del = θ sub = 20, χ = 1.
The mutation probability for each attribute of the rotating hyperellipsoidal structures (center, stretch, and angle) are set to µ = 1/n = 0.2. The center is mutated within the receptive field bounds, the stretches are decreased or increased in size maximally doubling or halving their current size; the angles are uniformly changed by maximally 45. The initial radius of receptive fields is taken uniformly random from [0.00, 1]. GA subsumption is applied. Condensation is applied after 80% of the learning iterations. number of distinct classifiers (number of macro-classifiers) and the average generality (volume) of the classifiers in the population are reported. In the case of Gaussian sampling, only those grid points are considered that lie in the 95% confidence interval.

We report results with various sampling approaches: First, standard uniform sampling is applied. Next, random walk sampling is investigated, where each successive sample depends on the previous sample. We add Gaussian noise to the previous sample to derive the next one. If the resulting x1 or x2 value lies outside of the input space [0, 1], a different Gaussian noise value is sampled. Note that such sampling mimics a continuous interaction with an environmentpreviously, for example, investigated in multi-step reinforcement learning problems (mazes) with XCS, where teletransportation was proposed to improve learning [START_REF] Lanzi | An analysis of generalization in the XCS classifier system[END_REF]. However, teletransportation cannot be used when the system is supposed to learn fully autonomously.

Moreover, we report results where sampling is restricted to a ring manifold in the two dimensional space, centered on .5, .5 and with a minimum radius of .3 and a maximum radius of .4, within which once again random walk sampling is applied. Furthermore, we report results on Gaussian problem sampling where samples are either generated by a Gaussian process with center .5, .5 and variable widths or where we apply a Gaussian ring sampling, in which case the average ring radius is sampled from a Gaussian process with mean .3 and particular standard deviations and the angle is chosen uniformly randomly between 0 and 2π.

Crossed Ridge Results

The results in figures 4(a), 4(b) suggest that XCSF with local deletion yields a more stable condensation process during uniform sampling in the crossed ridge function. During learning, learning progress and achieved values seem generally comparable. Similar differences during condensation as well as slight learning advantages during learning can be identified also for different random walk sampling cases (figures 4(c)-4(f)). Also the behavior of the generalization values and the population sizes are generally comparable. The number of macro-classifiers stays slightly higher when local deletion is applied -probably an additional indicator for the prevention of detrimental forgetting. Generally these results suggest that XCSF can deal rather well with sampling based on random walk. Only during condensation, during which neither mutation nor crossover operators are applied, the danger for detrimental forgetting is larger in XCSF. Figure 2 shows the developed classifier condition structures, which cover the problem input space, for the random walk sampling with σ = 0.1 after condensation. Local linearities appear nicely exploited. However, in this case a difference between XCSF and XCSFld cannot be deduced.

When sampling the Crossed Ridge function on a ring, figures 5(a), 5(b) show that performances are generally comparable. When Gaussian sampling is applied (figures 5(c), 5(d)), the same robustness is observable when XCSFld is applied. However, in this case a similar stable solution takes slightly longer to develop. Finally, when Gaussian ring sampling is applied (figures 5(e), 5(f)), we can observe the evolution of a final solution with lower prediction error and higher average rule generality when XCSFld is applied -indicating that detrimental forgetting due to global deletion in XCSF is prevented -once again particularly strongly during con- densation. Note also that these results show for the first time that XCSF -regardless if deleting globally or locallycan solve an approximation problem in a local manifold better than when approximating a function in a larger problem space (compare prediction errors in Figure 4 with those in Figure 5). In sum, the results show that XCSFld does not yield any worse performance than normal XCSF in any of the investigated cases in the Crossed Ridge function. However, in most cases, the prediction errors stay significantly more stable during condensation.

Sine Results

The sine function is a rather tough case to learn a fully accurate model that achieves an error below ǫ0 = .002 with N = 4000 classifiers. In the uniform sampling case (figures 6(a) and 6(b)) XCSFld yields better RMS values during learning and much more stable final solution sustenance, preventing detrimental forgetting. This result indicates that the local ellipsoidal structures, which typically orient themselves diagonally in space in this sine function, are strongly locally overlapping. When random walk sampling is applied, the problem space is more accurately approximated with XCSFld -as indicated by the RMS measure -and huge prediction error differences after condensation can be observed (figures 6(c)-6(f)). In the most extreme case, the final RMS for normal XCSF yields an error above 0.4 while the error of XCSFld stays below 0.004 -two orders of magnitude better performance due to the local deletion mechanism (see figures 6(c) and 6(d)). Figure 3 again shows the developed classifier condition structures after condensation for the random walk sampling with σ = 0.1. The local linearities are clearly exploited. In the case of XCSF, particularly the coverage at the two corners (0,0) and (1,1) has been lost. XCSFld maintains a full coverage, preventing detrimental forgetting.

Similar results can also be observed in the other sampling cases (Figure 7). While the random walk in ring sampling does not yield extreme differences (figures 7(a), 7(b)), in the case of Gaussian Centered sampling again detrimental forgetting is prevented during condensation due to the local deletion mechanism (figures 7(c)-7(f)).

SUMMARY AND CONCLUSIONS

This paper proposes for the first time that the "global deletion dogma" in XCS may be modified to prevent detrimental forgetting. XCSF appears to be particularly prone for detrimental forgetting when condensation is applied and when classifiers are locally highly overlapping. While condensation may be disregarded, it is certainly a very useful tool to extract a final, highly compact problem solution representation. Moreover, several results indicate that local deletion may also be advantageous during learning. However, for standard function approximation problems, the effect appears not to be as significant. Thus, partially the results also point out that XCSF indeed is a very robust, iterative, locally weighted regression system. However, local deletion appears to expand this robustness beyond the original capabilities without any apparent drawback. Indeed, we ran many more experiments with other step sizes in the random walk experiments, other Gaussian noise sampling widths, and XCSF parameter modifications, which all suggested the same tendencies reported here.

In conclusion, local deletion can improve problem solution sustenance in XCSF and thus the overall performance of the system, by preventing detrimental forgetting. A most exciting perspective that we believe opens up, besides this performance improvement, however, is that this local deletion mechanism may be also used to selectively learn higher accurate and lower accurate approximations in different problem subspaces. If this is desired, local deletion is expected to enable the selective improvement of the developing problem approximations. The selectivity may, for example, be determined by additional importance indicators, such as reward values. Thus, future research should further elaborate XCS-Fld and particularly investigate its potential in tasks where highly non-uniformly varying target errors are strived for in different problem subspaces.

Figure 1 :

 1 Figure 1: Surface plots of (a) the Crossed Ridge function f1 and (b) the Sine function f2.

Figure 2 :

 2 Figure 2: Structure of ellipsoids of XCSF and XCS-FLD after condensation in exemplary runs with random walk sampling, standard deviation σ = 0.1, in the crossed ridge problem. Shown are contour plots of 20% of the actual size of the classifier receptive fields with respect to matching. Darker blue indicates higher fitness values.

Figure 3 :

 3 Figure 3: Structure of ellipsoids of XCSF and XCS-FLD after condensation in the sine function.

1 Module 1 : 1 Module 1 : 1 Figure 4 :

 111114 Figure4: Crossed Ridge Function: Uniform Sampling and Random Walk Sampling. Condensation starts after 320k learning iterations. Reported are online prediction error and average root mean square prediction error (both log-scaled) as well as the number of distinct (that is, macro) classifiers and the average generality of classifier conditions.

1 Module 1 1 Module 1

 1111 macro cl. (/2000), generality (/100) number of learning steps (1000s) XCSF in CRidge task, sample type = 2, standard deviation σ=.02 Module 1: pred.error RMSE macro cl. generality (a) XCSF: Random Walk in Ring macro cl. (/2000), generality (/100) number of learning steps (1000s) XCSFld in CRidge task, sample type = 2, standard deviation σ=.02 Module 1: pred.error RMSE macro cl. generality (b) XCSFld: Random Walk in Ring macro cl. (/2000), generality (/100) number of learning steps (1000s) XCSF in CRidge task, sample type = 3, standard deviation σ=.macro cl. (/2000), generality (/100) number of learning steps (1000s) XCSFld in CRidge task, sample type = 3, standard deviation σ=.macro cl. (/2000), generality (/100) number of learning steps (1000s) XCSF in CRidge task, sample type = 4, standard deviation σ=.05 Module 1: pred.error RMSE macro cl. generality (e) XCSF: Gaussian Ring Sampling macro cl. (/2000), generality (/100) number of learning steps (1000s) XCSFld in CRidge task, sample type = 4, standard deviation σ=.05 Module 1: pred.error RMSE macro cl. generality (f) XCSFld: Gaussian Ring Sampling

Figure 5 :

 5 Figure 5: Crossed Ridge Function: Random Walk in Ring, Gaussian Centered, and Gaussian Ring Sampling

1 Module 1 : 1 Module 1 :

 1111 macro cl. (/2000), generality (/100) number of learning steps (1000s) XCSF in Sine task, sample type = 1, standard deviation σ=.02 Module 1: pred.error RMSE macro cl. generality (c) XCSF: Rand.Walk Sampling, σ = .02 macro cl. (/2000), generality (/100) number of learning steps (1000s) XCSFld in Sine task, sample type = 1, standard deviation σ=.02 Module 1: pred.error RMSE macro cl. generality (d) XCSFld: Rand.Walk Sampling, σ = .02 macro cl. (/2000), generality (/100) number of learning steps (1000s) XCSF in Sine task, sample type = 1, standard deviation σ=.pred.error RMSE macro cl. generality (e) XCSF: Rand.Walk Sampling, σ = .1 macro cl. (/2000), generality (/100) number of learning steps (1000s) XCSFld in Sine task, sample type = 1, standard deviation σ=.pred.error RMSE macro cl. generality (f) XCSFld: Rand.Walk Sampling, σ = .1

Figure 6 :

 6 Figure 6: Sine Function: Uniform Sampling and Random Walk Sampling

1 Module 1 1 Module 1

 1111 macro cl. (/2000), generality (/100) number of learning steps (1000s) XCSF in Sine task, sample type = 2, standard deviation σ=.02 Module 1: pred.error RMSE macro cl. generality (a) XCSF: Random Walk in Ring macro cl. (/2000), generality (/100) number of learning steps (1000s) XCSFld in Sine task, sample type = 2, standard deviation σ=.02 Module 1: pred.error RMSE macro cl. generality (b) XCSFld: Random Walk in Ring macro cl. (/2000), generality (/100) number of learning steps (1000s) XCSF in Sine task, sample type = 3, standard deviation σ=.macro cl. (/2000), generality (/100) number of learning steps (1000s) XCSFld in Sine task, sample type = 3, standard deviation σ=.macro cl. (/2000), generality (/100) number of learning steps (1000s) XCSF in Sine task, sample type = 4, standard deviation σ=.05 Module 1: pred.error RMSE macro cl. generality (e) XCSF: Gaussian Ring Sampling macro cl. (/2000), generality (/100) number of learning steps (1000s) XCSFld in Sine task, sample type = 4, standard deviation σ=.05 Module 1: pred.error RMSE macro cl. generality (f) XCSFld: Gaussian Ring Sampling

Figure 7 :

 7 Figure 7: Sine Function: Random Walk in Ring, Gaussian Centered, and Gaussian Ring Sampling

Acknowledgments

The first author acknowledges funding from the Emmy Noether program (German Research Foundation, DFG, BU1335/3-1) and thanks the COBOSLAB team.


Patrick O Stalph
email: patrick.stalph@psychologie.uni-wuerzburg.de

Jérémie Rubinsztajn
email: jeremie.rubinsztajn@etu.upmc.fr

Olivier Sigaud
email: olivier.sigaud@upmc.fr

Martin V Butz
email: butz@psychologie.uni-wuerzburg.de

A Comparative Study: Function Approximation with LWPR and XCSF

Keywords: F.2.1 [Analysis of Algorithms and Problem Complexity]: Numerical Algorithms and Problems, G.1.2 [Numerical Analysis]: Approximation-approximation of surfaces and contours, least squares approximation, nonlinear approximation, I.2.6 [Artificial Intelligence]: Learning Algorithms, Theory, Performance XCSF, LWPR, function approximation

Function approximation is an important tool that is frequently used in numerical mathematics and engineering. The most challenging approximation problems arise, when even the function class is unknown and the surface has to be approximated online from incoming samples. One way to achieve good approximations of complex non-linear functions is to cluster the input space into small patches, apply linear models in each niche, and recombine these models via a weighted sum. While it is rather simple to optimally fit a linear model to given data, it is fairly complex to find a reasonable structuring of the input space in order to exploit linearities in the underlying function. We compare two algorithms that are able to approximate multi-dimensional, nonlinear functions online. The XCSF Learning Classifier System is a modified version of XCS, which is a genetics-based machine learning algorithm. Locally Weighted Projection Regression (LWPR) is a statistics-based machine learning technique that is widely used for function approximation, particularly in robotics. The two algorithms are compared on three benchmark functions by monitoring several performance related measures over the learning trials. Moreover, an illustration of the final input space structuring sheds light on the clustering capabilities.

INTRODUCTION

When an unknown function over an infinite input space is iteratively sampled, often generalization (interpolation) is desired. Such applications can be found in several areas, including numerical mathematics and robotics. However, without knowledge about the function class, the classical function fitting methods cannot be applied.

Alternatively, the input space can be clustered such that simple linear models suffice to fit the given data in each niche with sufficient accuracy. In turn, these models are recombined in a weighted sum to yield a smooth approximation of the whole function surface. This article compares two such methods, namely the Locally Weighted Projection Regression (LWPR) algorithm [START_REF] Vijayakumar | Locally weighted projection regression: An O(n) algorithm for incremental real time learning in high dimensional space[END_REF] and the XCSF Learning Classifier System [START_REF] Wilson | Classifiers that approximate functions[END_REF].

While it has been shown that the performance of XCSF is comparable to LWPR [START_REF] Butz | Function approximation with XCS: Hyperellipsoidal conditions, recursive least squares, and compaction[END_REF], the study was restricted to the final prediction error, only. We take the comparison one step further and analyze learning behavior and population structures in detail by monitoring the approximation error and population size during learning. Furthermore, the resulting input space clustering after learning is visualized and compared directly. A detailed discussion also tackles algorithmic complexity and emphasizes advantages and disadvantages of each algorithm.

The remainder of this article is structured as follows. First, we give a brief overview of the two algorithms in Section 2, where similarities and differences are highlighted. Section 3 discusses how these techniques can be compared objectively. Results of the conducted experiments from Section 4 are discussed in Section 5. The final section concludes this article.

LWPR AND XCSF

A detailed description of both algorithms is beyond the scope of this article-instead we give a rough idea how the systems approximate functions and highlight similarities and differences. For a detailed description of XCSF, please refer to [START_REF] Wilson | Classifier fitness based on accuracy[END_REF][START_REF] Wilson | Classifiers that approximate functions[END_REF]. Details of LWPR and its predecessor can be found in [START_REF] Schaal | Constructive incremental learning from only local information[END_REF][START_REF] Vijayakumar | Incremental online learning in high dimensions[END_REF].

Consider an n-dimensional real-valued function

f : R n → R,
that is sampled iteratively: each time step a sample ( x, y) is given to the algorithm, where y = f ( x). The goal is to approximate the whole function surface online from the given samples. The following section briefly describes the common workflow that enables both systems to solve this approximation problem, while the subsequent section in turn highlights the differences.

Overview and Similarities

In order to accurately approximate an unknown, nonlinear function 1 from a finite number of samples, the input space can be clustered into smaller subspaces such that simple linear models yield sufficient accuracy in each subspace. Consequently, learning takes place at two levels: (a) finding an appropriate structuring of the input space and (b) fitting linear models to each subspace. First, the basic representations are explained briefly before the learning mechanisms are introduced.

Concerning the input space structuring, LWPR is equipped with receptive fields (RFs) that essentially define an ellipsoidal shape. A receptive field in XCSF is called a classifier and ellipsoidal shapes are one possible choice [START_REF] Butz | Function approximation with XCS: Hyperellipsoidal conditions, recursive least squares, and compaction[END_REF]. From now on, the term receptive field is also used for XCSF's classifiers. Both systems are initialized with empty populations, and receptive fields are created, when a new input arrives that is not yet covered (so called covering mechanism). An n-dimensional, not necessarily axis-aligned ellipsoid positioned at center c ∈ R n can be described by a symmetric, positive semi-definite matrix D ∈ R (n×n) . A quadratic form specifies the squared distance

d 2 = ( x -c) T D ( x -c) (1)
from a point x to the center, where T is the transpose operator. Symmetry and positive semi-definiteness are necessary conditions for an ellipsoidal representation. Solving for d = 1 yields the points x on the surface of the ellipsoid. The other way around, given a point x, the equation may be used to specify the squared distance of x to the center of the receptive field, which in turn can be used to determine if 1 Simple least squares methods suffice if the data is linear.

a receptive field is responsible for an input. Given an eigendecomposition of D with eigenvectors vi and eigenvalues ei, the principal axes of the ellipsoid are the eigenvectors and the corresponding radii are given by ri = 1/ √ ei. The eigendecomposition of a symmetric positive semi-definite matrix always exists and only yields real eigenvalues.

Concerning the linear prediction, each receptive field contains n weights β k and the predicted function value is

p( x) = n X k=1 β k x k + β0, ( 2
)
where β0 is the intercept. Altogether, given an input x both systems scan their population P of receptive fields for those that match the input best and a weighted sum of individual approximations yields the final prediction ŷ =

P i∈M wipi( x) P i∈M wi , ( 3
)
where M is the set of matching receptive fields and each receptive field is connected to a weight wi (described later).

Matching and weighting slightly differ in LWPR and XCSF, but the main idea is that RFs close to the current input contribute the most to the final prediction.

Differences

In LWPR all receptive fields in the population are said to match, but their contribution wi to the final prediction equals their gaussian activity

ai( x) = exp(-0.5d 2 ), (4)
where d 2 is the squared distance from current input to the center of the receptive field (Equation 1). For computational efficiency, only those RFs with an activity ai ≥ 0.001 are included in LWPR's matchset. Furthermore, with wi = ai only those RFs close to the current input contribute significantly to the prediction in [START_REF] Souza | Learning inverse kinematics[END_REF]. By contrast, in XCSF only those RFs with distance d ≤ 1 to the center, that is, those RFs that contain the input, are said to match. Here, the weighting is based on a scaled inverse of the prediction error, that is, accurate RFs contribute more. To sum up, in both systems the prediction is governed by those RFs close to the input. While LWPR realizes a smooth transition from one RF to the other via an exponential weighting, XCSF's weighting emphasizes accuracy and less accurate RFs also contribute less to the prediction. Up to now, the actual learning mechanisms were not mentioned at all. We recall, that locally linear function approximation involves (a) learning the input space structuring, that is, size and rotation of the RFs and (b) fitting the data of an RFs subspace to a linear model. Furthermore, in an online learning environment, the first step can only be achieved when enough information about the linearity of the data that one receptive field receives is available.

Fitting a linear model to given data can be achieved easily with classical least squares methods and fast online versions of such algorithms are available as well. XCSF uses the recursive least squares (RLS) algorithm, which has been shown to yield good approximations fast [START_REF] Lanzi | Prediction update algorithms for XCSF: RLS, kalman filter, and gain adaptation[END_REF]. The predecessor of LWPR, that is RWFR [START_REF] Schaal | Constructive incremental learning from only local information[END_REF], also uses RLS.

In contrast, LWPR applies an incremental partial least squares algorithm, which is the incremental version of the partial least squares (PLS) method [START_REF] Frank | A statistical view of some chemometrics regression tools[END_REF]. The PLS technique is especially useful in high-dimensional problems with eventually irrelevant dimensions. Based on the direction of highest correlation of inputs and prediction error, PLS fits one gradient for the first projection. Further projections are added based on the correlation of the previous projected input and residual error, until the prediction error is not affected by additional projections. This way, the incremental PLS only picks relevant dimensions. Again, the updates to the incremental PLS model in LWPR are weighted with the activity ai of each receptive field. Thus, not only the RFs contribution to the prediction is modified by its distance to the input, but also the update rate of the linear prediction. In sum, both methods yield reliable linear predictions and apart from computational complexity, the differences are negligible in the context of this article. Now, one important question is left: How is the locality learned, that is, how is the shape and size of the RFs adapted?

It is non-trivial to find an input space clustering that allows for locally linear approximation and that's where the systems are very different. While XCSF builds on a steady state genetic algorithm (GA), the updates of the distance metric in LWPR are realized by pure statical gradient descent. XCSF has a maximum population size that allows for evolutionary competition between RFs, whereas LWPR's receptive fields are completely local and do not interact except for the final prediction. A detailed description is not possible in this context, but the rough idea is sketched in the following paragraphs.

Input Space Structuring in XCSF.

Each receptive field has an estimate of its current absolute prediction error, which is the basis of a sophisticated fitness scheme that also includes fitness sharing. Receptive fields with a low prediction error get a higher fitness value and if few receptive fields cover the same input, these receptive fields get a large share of the available fitness [START_REF] Wilson | Classifier fitness based on accuracy[END_REF]. Based on the fitness value, a steady state GA reproduces two receptive fields using tournament selection. Crossover and mutation operators are applied to the location c, stretch, and rotation (defined by D) of these receptive fields, which are in turn inserted back into the population. When the maximum population size is reached, a deletion mechanism kicks in and removes RFs from overcrowded regions using a proportionate selection probability. In order to allow for an accurate fitness evaluation, young RFs remain untouched. Another important detail is that fitness is flattened, when a maximum accuracy (as defined by the user) is achieved. Consequently, XCSF strives to evolve more accurate RFs until a given threshold is reached-thereupon, a generalization pressure pushes RFs to span larger areas as long as they are sufficiently accurate.

With the GA "working" on the population, there is always an evolutionary overhead of RFs that are freshly mutated but not yet evaluated. This dirty "workspace" can be purged towards the end of learning by either condensation [START_REF] Wilson | Generalization in the XCS classifier system[END_REF] or greedy compaction [START_REF] Butz | Function approximation with XCS: Hyperellipsoidal conditions, recursive least squares, and compaction[END_REF]. Both mechanisms reduce the population size by up to 90% and accurate RFs are left.

The clear advantage of an evolutionary mechanism is that the optimal structure for any shape or function can be found without knowledge of the fitness gradient. The disadvantage is an overhead in the number of receptive fields during learning and consequently higher computational cost. Further-more, the fitness signal might get lost in high-dimensional spaces due to a large number of mutation and crossover alternatives that do not improve the fitness significantly.

LWPR's Structuring Capability.

Once a receptive field in LWPR has seen enough inputs, its distance metric D is optimized by using an incremental gradient descent based on stochastic leave-one-out cross validation [START_REF] Vijayakumar | Locally weighted projection regression: An O(n) algorithm for incremental real time learning in high dimensional space[END_REF]. In contrast to XCSF, the center c is not modified. The high-level updates rules can be written in two steps, where a subscript t indicates the current iteration.

Dt = M T t Mt
, where M is upper-triangular, ( 5)

Mt = Mt-1 + α ∂J ∂Mt-1 , (6)
where the upper-triangular matrix M, which can be obtained by a cholesky decomposition of D, ensures that the distance metric stays positive semi-definite, α is the learning rate, and J is a sophisticated cost function to be minimized.

The cost function includes the activity weighted errors and a penalty term that prevents RFs from indefinitely shrinking, because LWPR does not have a fixed target error. Details can be found in [START_REF] Schaal | Constructive incremental learning from only local information[END_REF][START_REF] Vijayakumar | Incremental online learning in high dimensions[END_REF]. In sum, LWPR tries to modify the distance metric such that the prediction error is minimized while indefinite shrinkage is prevented. When the residual errors have less influence than the penalty term, RFs can also enlarge.

One major benefit of statistics-based updates is the low population size. In contrast to an evolutionary search, no overhead in the number of RFs is required to evaluate different mutation directions, but instead the statistics should in theory point to the optimal direction. Given optimal parameter settings and perfect statistics, the system should work for any dimension with sufficient learning speed and an acceptable computational cost. However, incremental update rules can only approximate the statistics available from batch training and several parameters have to be tuned for each problem anew in order to achieve good results [START_REF] Klanke | A library for locally weighted projection regression -supplementary documentation[END_REF]. The following section briefly discusses how the machine learning techniques LWPR and XCSF can be compared objectively.

HOW TO GET A FAIR COMPARISON?

It is not trivial to compare LWPR and XCSF, since there are several relevant, eventually conflicting performance factors, including 1. learning time in milliseconds, 2. learning time in the number of samples, 3. algorithmic complexity in general, 4. approximation accuracy, or 5. population size.

Although computational time is a major decision variable in real-world applications, this measure highly depends on implementation and programming language-a more objective measure would be the learning time in the number of samples, which we monitor in our comparison. A detailed discussion on the complexity of both algorithms goes beyond this article, however, we also tackle this topic later.

Moreover, the approximation accuracy is an important factor that is directly connected to the population size. As a higher population size usually allows for higher accuracy, these measures cannot be compared individually. However, LWPR neither allows to fix a target error nor the population size. In XCSF, a target error and maximum population size might be specified, but the Learning Classifier System is not guaranteed to reach the target error, and the final population size (without the evolutionary overhead) largely depends on the function structure.

In order to make this comparison fair, we decided to first tune LWPR until a sufficiently low target error is reached. Parameter tuning is done manually by decreasing the initial receptive field size, modifying the learning rate α and penalty value according to the instructions in [START_REF] Klanke | A library for locally weighted projection regression -supplementary documentation[END_REF]. The chosen target error was close to XCSF's typical performance with default parameters on the same functions. Next, we modified XCSF's maximum population size such that the final number of RFs approximately equals LWPR's number of RFs (less than ±5% on average). Thus, the number of RFs and the final prediction error are somewhat similar. This procedure allows for a fair -albeit not exact -comparison of the learning behavior, that is, the input space clustering, which is the major challenge for locally linear function approximation algorithms. In order to analyze the structuring capabilities, we plot the final structure of the receptive fields (consequently, this study is restricted to two-dimensional input spaces) and also measure the average volume of the RFs. Concerning the computational time, we refrain from measuring it directly and restrict ourselves to a brief excursus on algorithmic complexity.

Developers of LWPR claim a linear complexity in the number of inputs [START_REF] Vijayakumar | Locally weighted projection regression: An O(n) algorithm for incremental real time learning in high dimensional space[END_REF], however, this is not generally true. In order to accurately approximate a non-linear function over an n-dimensional space, the number of receptive fields required is also exponential in the order n, when the function does not have irrelevant dimensions [START_REF] Stalph | Resource management and scalability of the XCSF learning classifier system[END_REF], which corresponds to the curse of dimensionality. Furthermore, the matching and update procedures involve matrix operations, which induce a quadratic complexity in the number of inputs, when the matrices are non-diagonal. Matrices that contain non-zero entries only on the diagonal (linear matching complexity) are possible in both systems corresponding to axis-aligned ellipsoids, which reduces the expressiveness of the developed solutions and eventually requires higher population sizes to achieve a similar target error. At best, the complexity is linear when diagonal-only matrices are used and the population size is fixed-consequently the prediction error usually strongly increases with increasing dimension n. Alternatively, a linear complexity is true for an n-dimensional function with n -1 irrelevant, empty dimensions. As soon as the input space increases, even with irrelevant dimensions, this claim does not hold.

Thus, the computational time for learning largely depends on the actual population size (exponential in n) and less on the complexity of update rules, which ranges from constant to polynomial complexity in n depending on the representational complexity (e.g. constant for spherical RFs that only modify the radius in conjunction with a simple prediction that resembles the average of seen samples). The population size, in turn, mainly depends on the required target error and the receptive field's ability to structurally align its shape to the structure of the underlying function. To sum up, as both systems use the same geometric structure, the complexity in terms of required population size is at least

EXPERIMENTS

In the following experiments, the up-to-date implementations of both systems are used, that is, the current version of the original C implementation of LWPR [START_REF]LWPR implementation in C (v. 1.2.3)[END_REF] and a Java implementation of XCSF [START_REF] Stalph | Documentation of JavaXCSF[END_REF]. We compare the machine learning algorithms on three typical benchmark problems, where one is taken from the LWPR side and two are taken from XCSF's benchmark repertoire. In order to visualize the population structure, this study is restricted to two-dimensional functions. Furthermore, we are not interested in noisy functions as this goes beyond the scope of this article. For algorithmic reasons, the functions are defined in the interval [-1, 1] 2 for LWPR, whereas for XCSF, the input space is normalized to [0, 1] 2 .

1. The Crossed Ridge function contains a mix of linear and non-linear subspaces.

f1(x1, x2) = max ˆexp(-10x 2 1 ), exp(-50x 2 2 ), 1.25 exp(-5(x 2 1 + x 2 2 )) 2.
The Sine function is constant in the (1, -1) direction but highly non-linear in the perpendicular (1, 1) direction.

f2(x1, x2) = sin (2π(x1 + x2))

3. The Sine-in-Sine function is completely non-linear and a high curvature makes f3 a challenging problem.

f3(x1, x2) = sin " 4π " x1 + 1 2 + sin " π x2 + 1 2 ««« Figure 1
includes surface plots of these functions to illustrate the corresponding learning task. According to the previous section, we manually tune both machine learning algorithms such that the final prediction error and population size are in similar bounds. For LWPR, we activate the distance metric learning (update_D=1), allow rotation of ellipsoids (diag_only=0), but deactivate second order learning (meta=0) since the achieved prediction error is worse using meta learning. The resulting parameters from manual tuning according to instructions from the authors [START_REF] Klanke | A library for locally weighted projection regression -supplementary documentation[END_REF] are summarized in Table 1.

-1 0 1 x 1 -1 0 1 x 2 1.25 0 0.5 1 f(x 1 ,x 2 ) (a) Crossed Ridge -1 0 1 x 1 -1 0 1 x 2 -1 0 1 f(x 1 ,x 2 ) (b) Sine -1 0 1 x 1 -1 0 1 x 2 -1 0 1 f(x 1 ,x 2 )
(c) Sine-in-Sine Concerning XCSF, we mostly used the default parameters2 , and only modify the maximum population size such that the final number of RFs after condensation approximately matches the number of RFs in LWPR. In particular, the maximum population size is set to 2500 for functions f1 and f2, while N = 3950 is used for f3. We conducted ten independent runs for both systems on each function over 100000 learning iterations, each. The mean absolute prediction error (MAE) and number of RFs after learning are contained in Table 2. The settings result in very similar population sizes for LWPR and XCSF and a reasonable prediction error is achieved. It seems that XCSF achieves better prediction performance on functions f2 and f3, which is analyzed in depth now.

In addition to prediction error and population size, we are interested in the actual clustering of the input space. Apart from a visualization that depicts the ellipsoidal structure, we can measure the average volume of RFs. This measure reflects the generalization capabilities as more general receptive fields cover a larger subspace. However, the representations are very different for the two algorithms in that LWPR's RFs are (almost) always active but the contribution to the prediction is exponentially scaled by the distance x -c to its center, while XCSF's RFs have a specific radius of activation and either fully contribute or do not contribute at all to the prediction. Consequently, there is no comparable volume measurement. However, in order to get an idea how the distance metric changes over time, we compute an average volume in LWPR using the radius from the receptive field's center c to the inflection point of the gaussian activity function, that is, when ai( x) = exp(-0.5) ≈ 0.6.

The Crossed Ridge Function.

Figure 2(a) shows the prediction error, the number of allocated RFs, and the generality as measured by the volume for both systems over the learning time. By definition of the experimental setup, the final number of receptive fields is similar and also the difference in MAE is negligible (see also Table 2). In contrast to LWPR, the initial prediction error in XCSF is much higher due to the large initial size of receptive fields during covering. The population size quickly increases and the evolutionary search for an optimal clustering begins. Over time, the MAE reaches a reasonable level and at iteration 90000 the condensation mechanism kicks in to remove evolutionary overhead from the population. As an expected side effect of the evolutionary mechanism, the variance is higher in all measures for XCSF.

Although the generality measures are not directly comparable, the graph illustrates that XCSF starts with a coarse clustering and the GA refines the structure until a sufficient MAE is achieved. Starting at 90000 iterations, the condensation technique emphasizes maximally general receptive fields. In contrast, the volume of LWPR's receptive fields is hardly changed at all (initial avg. volume is 0.006283, final avg. is 0.00623), which also explains the very good prediction performance at the initial stage of learning.

Going one step further, we analyze the actual clustering of the input space in Figures 2(b) and(c). Again, this visualization is not exactly comparable, as the RFs in LWPR have a much larger area of influence than the radius to the inflection point of the activity function, as depicted in the graphic. Furthermore, XCSF's receptive fields are depicted at 20% of their actual size to highlight the structure. Both systems develop larger RFs at the edges of the input space and thin RFs on the "ridges" (compare Figure 1(a)). However, XCSF's structure is more pronounced, while almost spherical RFs suffice in LWPR to reach a similar prediction error. On the other hand, LWPR develops a rather clean, non-overlapping structure while XCSF evolves strongly overlapping RFs. The Oblique Sine Function.

The same measurements are depicted in Figure 3 for the oblique sine function f2. While the number of receptive fields is comparable, XCSF reaches on average an MAE of 0.0045 compared to LWPR's average final prediction error of 0.0124, which is about 2.7 times higher. The optimal structure on f2 consists of needle-like ellipsoids in parallel to the (1, -1) axis, since the function is constant in this direction. High curvature on the orthogonal (1, 1) axis demands small extent in this direction. While LWPR's input space clustering only marginally aligns to the oblique linearity, XCSF's clustering is very extreme in that the axis ratio of the ellipsoids is on average 27.3315 0.0196 ≈ 1390, that is, the ellipsoids elongated axis is about 1390 times longer than the short axis. Thus, the ellipsoids appear as thin lines in Figure 3(c) and reach far beyond the actual input space borders.

LWPR and XCSF on Sine-in-Sine. tion. Small spherical RFs suffice to reach the target error at the center, while thin, elongated ellipsoids are evolved at the lower and upper borders. We can only speculate, that in LWPR either the penalty term prevents the development of such a structure, the statistics-based gradient is not strong enough, or the chosen parameter settings are not useful. However, manual trial-anderror with various settings did not yield better results. Setting the penalty to zero disables the ability of RFs to enlarge at all and using initially very large RFs also does not result in an appropriate structuring in even longer learning trials. The best "structuring" was found when activating second order learning in conjunction with large receptive fields (cf. Figure 5). It seems that the meta learning modifies the learning rates α for each matrix entry Dij such that the oblique structuring of the distance metric D is possible. Unfortunately, the effect is lost with smaller RFs and it is not strong enough to create thin ellipsoids, as XCSF does, to minimize the prediction error. Surprisingly, the use of meta learning usually results in a higher prediction error.

DISCUSSION

Generally, both systems are well applicable to the benchmarks problems in this article as an appropriate prediction error is achieved by LWPR and XCSF as well. However, the investigated functions only represent a small niche of twodimensional problems. From a broader viewpoint on function approximation, we now outline advantages and disadvantages of the genetics-based and the statistics-based machine learning techniques investigated here. Structuring Capabilities.

The current results suggest that the statistics-based approach in LWPR does not suffice to reliably find an optimal structuring for the linear predictor. While LWPR reaches a low error faster than XCSF, this is due to the fact that the initial size of receptive fields in LWPR is very small because of manual tuning. The crossover, mutation, and selection mechanism of XCSF's genetic algorithm works in any complex search space, as long as the fitness gradient is sufficiently strong. The assumption of smooth functions fits to the crossover operator, as the crossover distributes useful substructures in the local proximity of a receptive field, while LWPR's receptive fields have only local information. On the other hand, a statistical approach allows for a uniform distribution of RFs, which is more efficient than the evolved, typically overlapping structure in a Learning Classifier System. However, XCSF is the first choice when a uniform spherical structure does not suffice-either because the desired error cannot be reached with a reasonable population size or because the algorithm is applied for the sole purpose of gaining insights about the structure.

Parameter Sensitivity.

Parameter fine-tuning is usually an art-otherwise the algorithms could implement simple rules-of-thumb or adaptation schemes. Both systems have important parameters that might be tuned for any problem anew. However, XCSF's relevant parameters, that is, population size and target error, can be set intuitively by the user. In contrast, it is not as simple to determine appropriate learning rates and a suitable initial size for receptive fields in LWPR.

Computational Effort.

A huge population size is the major reason for slow learning times in both algorithms. For non-linear n-dimensional problems the required population size is usually also exponential in n and consequently LWPR's O(n) claim is questionable. Given a desired target error, it is crucial to allocate as few RFs as possible while structuring their shape such that the data within each receptive field is approximately linear. Here, XCSF's drawback is the evolutionary search that requires an overhead in RFs to evaluate different structural possibilities. Consequently, the computational time, in terms of milliseconds, speaks in LWPR's favor. However, as XCSF might be able to find a better structure than LWPR, the same number of receptive fields after learning may result in a reduced prediction error.

Higher Dimensions, Irrelevant Dimensions.

For high-dimensional problems, the computational effort is pronounced and dimensionality reduction is non-trivial. The incremental PLS predictor used with LWPR incrementally adds linear projections, until adding more projections does not increase the accuracy, and thus enables LWPR to ignore irrelevant input subspaces in the local linear models. This reduces the number of weights to be adapted to the number of required projections. For example, when a two-dimensional function is twisted into a 20-dimensional space, LWPR's linear predictor only requires two projection directions and two weights, while the other dimensions are ignored [START_REF] Vijayakumar | Incremental online learning in high dimensions[END_REF].

However, the computational benefit fades, as more dimensions become relevant, because the relevant space has to be spanned by orthogonal projections. When n projections are required, the recursive least squares algorithm, which spans all n dimensions with one projection, as applied in XCSF, is faster due to less complex update rules. More important, although the linear predictor might ignore certain dimensions, this is not true for the distance metric. When one dimension should be ignored by either LWPR or XCSF, this has to be realized within the distance metric such that the radius in this dimension is large enough to cover all samples in this particular direction. Consequently, if the user does not modify the initial size of the RFs beforehand, LWPR creates many RFs to cover this dimension although the linear models ignore it completely.

Although several successful applications of LWPR to so called "high-dimensional problems" can be found in the literature [START_REF] Schaal | Scalable techniques from nonparametric statistics for real time robot learning[END_REF][START_REF] Souza | Learning inverse kinematics[END_REF][START_REF] Vijayakumar | Incremental online learning in high dimensions[END_REF], these studies actually sample relatively small trajectories through these spaces. Therefore, the applicability of both systems to high-dimensional non-linear problems is an open research topic. From the results in this study, LWPR's structuring on high-dimensional functions is expected to be more or less spherical, which might suffice for a wide range of functions and a similar behavior can be produced with XCSF by using axis-parallel ellipsoids or even spherical receptive fields. The simplified representation enables XCSF to also work on high-dimensional problems.

However, when a more sophisticated structuring is required in higher dimensions, both systems reach their limits. XCSF has a hard time to follow the fitness gradient, as for complex representations such as rotating ellipsoids the number of elements to mutate is quadratic in n and, additionally, the rotation in higher dimensions is not unique. Consequently, redundant mutation options slow down the evolutionary search.

SUMMARY AND CONCLUSIONS

This study compared the genetics-based XCSF and the statistics-based LWPR machine learning algorithms for multidimensional real valued function approximation. We highlighted algorithmic similarities as well as important differences and discussed how these systems can be compared objectively. We monitored mean absolute prediction error, population size, and receptive field volume on three typical benchmark problems, namely the Crossed Ridge function from LWPR's repertoire and two sinusoidal functions from XCSF's side. Additionally, we plotted the final input space structuring defined by locality and shape of receptive fields.

While both algorithms achieve a suitable performance on the investigated functions, the results suggest that the evolutionary structuring capability of XCSF is more powerful than LWPR's statistical gradient descent. Although LWPR is said to be well suited for high-dimensional spaces, this claim remains to be validated in future studies.

Figure 1 :

 1 Figure 1: Surface plots of (a) the Crossed Ridge function f1, (b) the Sine function f2, and (c) the Sine-in-Sine function f3.

Figure 2 :

 2 Figure 2: Performance measures and input space clustering on the Crossed Ridge function f1. (a) Mean absolute error, number of receptive fields, and the generality measure (mean plus standard deviation; vertical axis is log-scaled). (b) Visualization of LWPR's distance metrics D after learning. The ellipsoidal lines represent the inflection point of the gaussian activity. (c) Visualization of XCSF's distance metrics. RFs are scaled to 20% size in order to highlight the structure.

Figure 4

 4 Figure 4 reveals a similar scenario with respect to the completely non-linear function f3. While the number of RFs is similar, XCSF strongly structures the input space by means of rotated thin ellipsoids along the curvature of the func-

Figure 3 :

 3 Figure 3: Performance measurements and population visualizations for the Sine function.

Figure 4 :

 4 Figure 4: Performance measurements and population visualizations for the Sine-in-Sine function.

Figure 5 :

 5 Figure 5: LWPR's final structure on f3 with different parameters (init_D=50, alpha=50, penalty=0.000001, meta=1). Due to the coarse structuring, the final error is 0.1725.

Table 1 :

 1 LWPR's parameters after manual tuning.

	Parameter Value Meaning
	init_D	500	initial (inverse quadratic) size
			of RFs
	alpha	1000	learning rate for the distance
			metric
	penalty	10 -9	penalty term to avoid indefi-
			nite shrinking
	w_gen	0.2	threshold that specifies, when
			to create new RFs
	in the same order. Admittedly, the required number of RFs
	is by a constant larger for XCSF due to evolutionary over-
	head [10].

Table 2

 2

	: Rounded prediction error and population
	size measures (E ± σ) after learning.
	f1	MAE	Number of RFs
	LWPR 0.0055 ± 0.0004	439.2 ± 8.35
	XCSF 0.0053 ± 0.0008	434.5 ± 17.45
	f2	MAE	Number of RFs
	LWPR 0.0124 ± 0.0004	460.8 ± 4.54
	XCSF 0.0045 ± 0.0011	462.4 ± 13.32
	f3	MAE	Number of RFs
	LWPR 0.0352 ± 0.0009	534.9 ± 6.40
	XCSF 0.0259 ± 0.0013	543.1 ± 10.14

As in[START_REF] Butz | Function approximation with XCS: Hyperellipsoidal conditions, recursive least squares, and compaction[END_REF], XCSF's parameters are set to ε0 = 0.01, β = 0.1, δ = 0.1, α = 1, θGA = 50, θ del = θ sub = 20, χ = 1. Mutation rate is set to µ = 1/n = 0.2. Receptive field's initial radius is taken uniformly random from [0.005, 1]. GA subsumption is applied. Condensation is applied after 90000 iterations.


L. Saint-Bauzel V Pasqui

O Sigaud

Characterization of a least effort user-centered trajectory for sit-to-stand assistance

Sit-to-stand transfer is a prerequisite for locomotion and induces a lot of effort from elderly or disabled people. In the context of a project based on a locomotion and sit-to-stand assistance robotics device, we present a methodology to tune the trajectory of active handles so that the verticalisation effort of the user is minimised. The methodology is user-centered in the sense that the robot will generate a specific trajectory for each particular user.

Introduction

A robotic device to assist the locomotion function of elderly and disabled people may improve a lot their autonomy, the efficacy of rehabilitation efforts and, more generally, may improve their quality of life. But assisting locomotion is of less interest if it does not help the user in transfering himself or herself from the sitted position to the standing position. As a matter of fact, very few robotics systems are endowed with both a locomotion assistance and a verticalisation assistance capability [START_REF] Lee | A system for gait rehabilitation: mobile manipulator approach[END_REF], [START_REF] Chuy | Approach in assisting a sit-to-stand movement using robotic walking support system[END_REF], [START_REF] Médéric | An optimized design for an intelligent walking aid[END_REF]. However the sit-to-stand motion induces a lot of effort from the patient. Thus it is of the most importance to design the robotic assistance device so that this effort is minimised. In this paper, we present a preliminary study of a user-centered methodology that is designed to generate an assistance trajectory for robotic handles that minimises the effort from the user depending on his/her own sit-to-stand transfert strategy. The generated trajectories are tailored to a particular user using a set of five parameters:

• P I and P F , the initial and final positions of the trajectory, are chosen by the user, Viviane Pasqui, Ludovic Saint-Bauzel, Olivier Sigaud Institut des Systèmes Intelligents et de Robotique -CNRS UMR 7222 Université Pierre et Marie Curie, Pyramide Tour 55 -Boîte Courrier 173, 4 Place Jussieu, 75252 Paris CEDEX 5, France. e-mail: pasqui@isir.upmc.fr, saintbauzel@isir.upmc.fr, olivier.sigaud@upmc.fr

• T F , the sit-to-stand transfert time, is set by the experimenter, • (dev 1 , dev 2 ) describe the shape of the trajectory, they must be different for each user. Our method tunes dev 1 and dev 2 so as to minimise the effort.

The paper is organised as follows. In Section 2, we present Monimad, the robotic assistance device that we use, as well as our method to generate trajectories. In Section 3, we describe our method to choose among five trajectories the one that is most adequate for a particular user, and then our method to tune dev 1 and dev 2 depending on the user effort. In Section 4, we present the preliminary empirical results that we obtained with the method. These results are discussed in Section 5 before we conclude.

Robotic device

Monimad is an original assistive device, combining sit-to-stand transfer and walking aid for elderly and disabled people. It allows mobility rehabilitation and assistance, safe walking (postural stabilization) and safe sit-to-stand transfer [START_REF] Médéric | An optimized design for an intelligent walking aid[END_REF]. The designed robotic system is basically a two degrees of freedom arms mechanism mounted on an active mobile platform (Fig. 1). The lower part (mobile platform) consists of two electric motors actuating the wheels. The upper part of the mechanism (articulated arms) consists of two plane parallelograms to maintain the handles horizontally, actuated by linear actuators. In addition, they are independent in order to restore lateral balance. The end effectors consists of handles equipped with a six axis forces/torques sensor that are used in the experiments presented below to evaluate the relevance of the sit-to-stand trajectory. A preliminary analysis of the movement in elderly sit-to-stand clinical trials, with a specific measurement system [START_REF] Médéric | An optimized design for an intelligent walking aid[END_REF], has allowed to describe the trajectory of the hands during assisted movements. First, the handles must pull slowly the patient to an antepulsion configuration (see Fig. 2). Then, they go from this down position to the up position, used for walking. For each patient, several sit-to-stand transfer trajectories were recorded, some examples of these trajectories are given in Fig. 2. The analysis of these transfer trajectories shows that the global shape of the trajectory is a "s-like" curve and is not directly related to the age or height of the patient but seems to be correlated with its own personal strategy to stand up or sit-down. This seems to reflect invariants of the trajectory generation [START_REF] Médéric | Elderly people sit-to-stand transfert experimental analysis[END_REF]. The trajectory of the handles has to be similar to the general curve presented in Fig. 3. The term "trajectory" refers here to Cartesian-space Fig. 3 The handles trajectory in cartesian space. This kind of curves look like a third order polynom in the (P i , e P i P f , e ⊥ P i P f ) frame. The input of these curves are the initial and final handles positions (P i and P f ) and the curvatures of both pieces of the curve (dev 1 and dev 2 ). planning of the handle movement. A "natural" trajectory is requested for comfortable human movement assisted by robotic devices. From our point of view, "natural" means that the trajectory path must be compatible with hand movements when the sit-to-stand transfer is assisted by someone else. It must also be smooth and generate a continuous motion of the hand. As proposed in [START_REF] Flash | The coordination of arm movements : an experimentally confirmed mathematical model[END_REF], smoothness can be quantified as a function of jerk, which is the time derivative of the acceleration. The method to obtain such a trajectory consists in decomposing its characteristics into a physiological part and a mechanical part. The minimum jerk criterion is a physiological constraint for smoothness and is only related to trajectory quality. Thus, the curvilinear abscissa is used to describe the law of motion satisfying the minimum jerk criterion. Let s(t) represents the distance that the handles have moved along the curve at instant t. The curvilinear abscissa s(t) defined by Eq. 1 (see [START_REF] Flash | The coordination of arm movements : an experimentally confirmed mathematical model[END_REF]), guarantees the smoothness of the handles trajectory.

s(t) = s(T i ) + (s(T f ) -s(T i ))(10( t T f -T i ) 3 -15( t T f -T i ) 4 + 6( t T f -T i ) 5 ) (1)
Where T i is the initial time and T f is the final one.

The geometrical path describing the hand are not time dependent and may be expressed in terms of Euclidean coordinates. An assisted sit-to-stand transfer trajectory follows a path similar to the one shown in Fig. 3. This kind of curve will be defined by a third order polynomial in the (P i , e P i P f , e ⊥ P i P f ) plane (with : e ⊥ P i P f = z ∧ e P i P f ). Considering the point P j on the handle path curve: P i P j = U j e P i P f + V j e ⊥ P i P f , with :

V j = ∑ 3 i=0 α i U i j .
The knowledge of the coordinates of the points P k (k = 0, . . . , 4, Fig. 3) leads to the equations below:

                     α 0 = 0 α 1 U 1 + α 2 U 2 1 + α 3 U 3 1 = V 1 (= dev 1 ) (A) α 1 U 2 + α 2 U 2 2 + α 3 U 3 2 = 0 (B) α 1 U 3 + α 2 U 2 3 + α 3 U 3 3 = V 3 (= dev 2 ) (C) α 1 U 4 + α 2 U 2 4 + α 3 U 3 4 = 0 (where U 4 = P i P f ) (D) dV dU U 1 = α 1 + 2α 2 U 1 + 3α 3 U 2 1 = 0 (E) dV dU U 3 = α 1 + 2α 2 U 3 + 3α 3 U 2 3 = 0 (F)
A solution of this system is obtained in two steps. First, solving the linear system {(A), (B), (C)}, α i coefficients can be expressed in term of U 1 ,U 2 ,U 3 . In a second step, U 1 ,U 2 ,U 3 values are the solutions of the minimisation problem based on equations {(D), (E), (F)} defined as:

min((D) 2 + (E) 2 + (F) 2 ) under        -U 1 < 0 U 1 -U 2 < 0 U 2 -U 3 < 0 U 3 -U 4 < 0 (2)
The starting point of the optimization procedure, is taken such that:

       -U 1 < 2% of the length curve (s(T f ) -s(T i )) U 1 -U 2 < 2% of the length curve U 2 -U 3 < 2% of the length curve U 3 -U 4 < 2% of the length curve (3)
We have observed that the resulting polynomial is always very close to the experimental curve. The handle trajectory in spatiotemporal space is defined by U and V coordinates as time functions, such that

( dU ds ) 2 + ( d ds ( 3 ∑ i=1 α i U i )) 2 = 1
Finally, the trajectory is a time function of Cartesian coordinates generating a smooth movement. Estimated coordinates of the point P are computed with the following recursive scheme:

       U(k + 1) = (t(k+1)-t(k))(4 ṡM •t(k)•(T f -t(k))) (T 2 f 1+(∑ 3 i=1 iα i U(k) i-1 ) 2 ) + U(k) V (k + 1) = ∑ 3 i=1 α i U(k + 1) i (4)
And ṡM is computed with the handle path length using simultaneously the curvilinear abscissa and the Euclidean coordinates:

ṡM = 3(∑ N i=0 (U i+1 -U i ) 2 + (V i+1 -V i ) 2 ) 2T f ( 5
)
In order to observe the posture of the user, a six axis force/torque sensor is placed under the user's feet to measure the ground contact forces and the forces applied to the handles. As a consequence, the anticipatory postural adjustement (APA) determination can be used to initiate the sit-to-stand motion of the robot handles. Both ground and hand forces, treated with fuzzy logic laws, give information on the sitto-stand transfer phase and on the stability state of the user [START_REF] Saint-Bauzel | A reactive robotized interface for lower limb Rehabilitation: Clinical results[END_REF].

Experimental study

The goal of our experiment is to tune the dev 1 and dev 2 parameters of the trajectory so as to ensure that the user makes as few effort as possible. Our methology consists of three steps:

• First, we recorded the global effort of the users along a set of five trajectories that have been shown through clinical experiments to provide a satisfactory basis for sit-to-stand assistance trajectory generation [START_REF] Médéric | Elderly people sit-to-stand transfert experimental analysis[END_REF]. The active handles are con-Fig. 4 Trajectories for experiments trolled in position, than the user has no other choice then following the imposed trajectory. The difference between the natural trajectory the subject would use if helped by a human assistant and the imposed trajectory generates an additional effort from the user. Thus we assume that the most natural trajectory is one that generates the least global effort from the user. • In a second step, we control the active handles with some impedance, so that the user can locally alter the handles trajectory. We assume that the subject will alter the handles trajectory so as to make it more comfortable, provided that the corresponding additionnal effort is not too high. The altered trajectory corresponds to modified dev 1 and dev 2 parameters that can be extracted from this second step [START_REF] Pasqui | Bio-mimetic trajectory generation for guided arm movement during assisted sit-to-stand transfer[END_REF]. • In the third step, we record again the total effort of the user with a position controlled handles trajectory, where the trajectory is generated according to the dev 1 and dev 2 values determined in the second step. We check that the global effort is smaller than initially.

Results

The experiments were performed with 8 subjects. All were healthy male volunteers between 25 and 30 years old (average: height :175,3 ± 5,36 cm, weight : 66,2 ± 9,91 kg). They were instructed to stand-up as naturally as possible.

Every subject performed 10 sit-to-stand tranfers. The data corresponding to one subject has been discarded as inconsistent. Among the subjects, three select traj5 in Fig. 4, two select traj2 and, traj1 and traj3 are selected by one subject. These trajectories are the least deformed when the verticalisation is made with the active handles controled with an impedance law. That is that among the proposed trajectories, the one that is followed most closely is the one where the sum of efforts measured at the hands and at the feet are the least. The new parameters dev 1 , dev 2 are determined from the average of ten sit-to-stand trajectories recorded, when the active handles are controled with an impedance law. Now these trajectory are used again with the active handles controlled in position. Fig. 5 shows, for one subject, that the resulting trajectory is not deformed a lot, so validating the hypothesis according to which the most comfortable trajectory is the one which brings the least effort.

Discussion

The fact that different subjects select diverse trajectories among our basis of five trajectories reveals the importance of a user-centered approach. Indeed, given that each subject has his own sit-to-stand transfer strategy, any methodology that would propose an unique trajectory as optimal for all the subjects Fig. 5 The blue trajectory is made with the active handles controlled in position and the red ones are recorded when the active handles are controled with an impedance law would fail to take their specificities into account and would generate unnecessary effort and discomfort for some of these subjects.

Second, the fact that our method effectively results in a global decrease of effort for all subjects is encouraging. However, we cannot claim for any of the subject that we have found the trajectory that would minimize his effort. To further optimize the dev 1 and dev 2 parameters, we will call in the future upon gradient descent approaches that are guaranteed to reach at least a local optimum, provided enough data.

Conclusion and future work

In this paper, we have presented a preliminary methodology that validated the feasability of minimising the effort of users in the context of robot-assisted sitto-stand transfert. The method shapes the active handles trajectory just by tuning two parameters, dev 1 and dev 2 . Immediate future work will consist in calling upon gradient descent tools to further optimize the parameters. Then, the next step will consist in incorporating the method in the broader context of our robotic-assisted locomotion project and, in parallel, in evaluating its benefits with elderly and disabled patients.

Fig. 1

 1 Fig. 1 Description of Monimad a Robotic assistant for sit-to-stand and walking

Fig. 2

 2 Fig. 2 Experimental sit-to-stand transfer trajectories

Acknowledgements This work is supported by the French ANR (Agence Nationale de la Recherche) TecSan program under grant No ANR-08-TECS-009-02 (MIRAS Project).