Sema Akkoyunlu
email: sema.akkoyunlu@agroparistech.fr

Cristina Manfredotti
email: cristina.manfredotti@agroparistech.fr

Antoine Cornuéjols
email: antoine.cornuejols@agroparistech.fr

Nicolas Darcel
email: nicolas.darcel@agroparistech.fr

Fabien Delaere
email: fabien.delaere@danone.com

Investigating substitutability of food items in consumption data

Keywords: Information systems → Information extraction, Recommender systems, recommender system, substitution, food consumption, nutrition

Food based dietary guidelines are insufficiently followed by consumers. One of the principal explanations of this failure is that they are too general and do not take into account eating habits. Providing personalized dietary recommendations via nutrition recommender system can hence help people improve their eating habits. Understanding eating habits is a keystone in order to build a context aware recommender system that delivers personalized dietary recommendations. As a first step towards this goal, we explore food relationships on real-world data using the INCA 2 dataset, a French consumption survey. We particularly focus on extracting food substitutions, i.e food items that can replace each other. We consider that two food items can be substituted if they are consumed during similar contexts. We define the context in the nutrition field and we introduce a measure of substitutability between food items based on consumption data that encodes the context.

INTRODUCTION

Nutritional quality of diets is proven to be an important factor in health dysfunctions. The risk of developing modern chronic diseases such as cardiovascular diseases, obesity or diabetes is linked to unhealthy eating habits [START_REF]Diet, nutrition and the prevention of chronic diseases: report of a joint who/fao expert consultation[END_REF].

In order to promote healthy and sustainable diet and prevent chronic diseases, dietary guidelines targeted to the general population are produced by public health agencies. However, it has been noted that the compliance to the guidelines is usually low although the awareness concerning the food based dietary recommendations is rather good [START_REF] Ivens | Translating the Dietary Guidelines to Promote Behavior Change: Perspectives from the Food and Nutrition Science Solutions Joint Task Force[END_REF]. Nutrition related knowledge does not imply adherence to dietary guidelines. Several causes explain this phenomenon: cultural and personal preferences, difficulty of implementing dietary changes, availability of food items [START_REF] Webb | Overcoming consumer inertia to dietary guidance[END_REF]. Nutritionists stress the fact that it is crucial to understand consumers' behaviours in order to make practical food-based recommendations because making changes is challenging [START_REF] Bier | Improving compliance with dietary recommendations[END_REF].

One fair assumption is that people are more likely to follow recommendations if these are acceptable from their point of view. We hypothesize that the user acceptance is a prerequisite for the compliance and could be improved by producing user-tailored recommendations that take into account dietary habits. On the long term, our objective is to build a nutrition recommender system taking into account dietary habits in order to encourage people toward healthier alternatives with high compliance.

In food related recommender systems, the recommended items are recipes [START_REF] Freyne | Intelligent food planning: personalized recipe recommendation[END_REF], [START_REF] Harvey | You are what you eat: Learning user tastes for rating prediction[END_REF] or food items themselves [START_REF] Ge | Using tags and latent factors in a food recommender system[END_REF]. We rather want to build a food item based recommender system that delivers message such as "instead of eating X, eat Y". In order to deliver relevant recommendations, it is important for a recommender systems to know substitutability relationships between items [START_REF] Mcauley | Inferring networks of substitutable and complementary products[END_REF], [START_REF] Zheng | Substitutes or complements: another step forward in recommendations[END_REF]. This is important in food recommender systems as well.

Moreover, it has been shown that context-aware recommender systems produce better recommendations than recommender systems that do not take into account the context [START_REF] Adomavicius | Context-aware recommender systems[END_REF]. In order to extract meaningful relationships between food items, in our model we consider contextual information. To the best of our knowledge, one study tackled the subject of food substitutability based on real-world consumption data [START_REF] Achananuparp | Extracting food substitutes from food diary via distributional similarity[END_REF]. However, they do not take into account contextual information such as the type of meal where substitutability relationships can be highly different.

In this paper, we specifically investigate food substitutability. To do that, we define the concept of dietary context as the set of food items a food is consumed with and the concept of food intake context as the setting of food consumption. Our intuition is that two food items are substitutable if they are consumed in similar dietary contexts and that substitutability differs according to the food intake context.

The rest of the paper is organized as follows. Section 2 describes our methodology. Section 3 reports the results. Finally in section 4, we discuss our results and present our future perspectives.

OUR APPROACH 2.1 Notations and problem statement

Let X be the set of food items. A meal is a collection of food items consumed at the same timeframe. For instance, {coffee, bread, jam, juice} is a meal. The meal database DB is the set of all meals. Let us denote DB br eak f ast the database of breakfasts and DB lunch the database of lunches.

Our objective is to mine food pair substitutability applied by consumers when they compose their meals. Given a database of meals, we want to extract substitutability relationships based on the way people consume food. No nutritional information is used during this process. Instead, contextual information is used in order to extract meaningful substitutability relationships.

Defining Context

The notion of context is quite complex and difficult to define universally. In the field of recommender systems, the context is usually defined according to the field of application of the system.

In the nutrition field, we define two types of contexts: the dietary context and the food intake context. The dietary context of a food item x is the set of food items c with which x is consumed. For instance, in the meal {coffee, bread, jam, juice}, the dietary context of {coffee} is {bread, jam, juice}. We think that the dietary context is fundamental when seeking substitutability of food items because the way people compose their meals is intrinsically dependent on the relationships between the items.

The food intake context is defined as the set of all variables such as the type of the meal (breakfast, lunch, dinner, snack), the location (home, workplace, restaurant), the participants (family, friend, coworkers, alone). This corresponds to the notion of context usually used in context-aware recommender systems [START_REF] Adomavicius | Context-aware recommender systems[END_REF].

There are three paradigms for incorporating context in recommender systems : contextual pre-filtering, contextual post-filtering and contextual modelling [START_REF] Adomavicius | Context-aware recommender systems[END_REF]. Contextual pre (post)-filtering consists in splitting the dataset according to contextual variables before (after) applying algorithms. Contextual modelling consists in incorporating contextual information in the algorithm. In our framework, dietary context is used in order to model substitutability whereas the food intake context is used for contextual pre-filtering.

Our objective is to investigate substitutability among food items based on the assumption that two food items are highly substitutable if they are consumed in similar dietary contexts and in the same intake context. Investigating all possible dietary contexts of a food item is computationally expensive because the number of possible dietary context is exponential in the number of food items and the length of the dietary context. The number of interesting contexts is actually limited by the characteristics of the available data. Instead of investigating all the dietary contexts of a food item, we decided to explore collections of meals that differ only by one item. We define the dietary context of a meal database c as the intersection of a set of meals S m such that :

len(c) = max x ∈S m (len(x)) -1 (1)
Let us define the substitutable set S c associated to a dietary context c as the set of food items such that the context c plus one item of S c can be effectively consumed together. For instance, the substitutable set of the dietary context c = {bread, jam, juice} might be S c = {co f f ee, tea, yoдurt }.

Mining substitutable items

To efficiently retrieve interesting sets of dietary contexts and their substitutable set, in this paper, we propose an approach based on graph mining techniques. Let us denote the meal graph G = (V , E) where V is the set of nodes representing meals from the database and E is the set of edges such that two nodes are connected if there is at most one item that changes between them. A meal should appear at least once in the database in order to appear as a node in the graph. Figure 1 is a simple illustration of a meal network. Designed in this way, the nodes of the substitutable set of a dietary context are adjacent. They form a sub-graph that is completely connected. Such an object is called a clique in graph mining. More specifically, the nodes form a maximal clique. A maximal clique is a clique to which another node cannot be added. In our setting, discovering substitutable sets is similar to mining maximal cliques in a graph. In this paper we use the algorithm of Bron-Kerbosh [START_REF] Bron | Algorithm 457: Finding all cliques of an undirected graph[END_REF] to search for maximal cliques.

All discovered maximal cliques are not cliques that are interesting for our study. We want cliques such that the size of the intersection of the nodes is a dietary context as defined above. We denote these cliques as substitutable cliques. However, we may encounter cliques as in Figure 2. In this case, the intersection of the nodes is {A} and we cannot derive a substitutable set from this clique.

To avoid retrieving uninteresting cliques, we apply Algorithm 1 that filters out substitutable cliques. For instance, when we apply our algorithm to the example of Figure 1, we get that this graph is a maximal clique and a substitutable clique more particularly. The context is {bread, butter} and the substitutable set associated to this context is {coffee, tea, milk, jam, nothing}. In this particular case, it is possible to substitute an item by nothing because {bread, butter } can be consumed as such.

Investigating substitutability of food items in consumption data

Computing a substitutability score

Substitutability is not a binary relationship because there are different degrees of substitutability. Moreover, if two items are consumed together, they are less substitutable because they might be associated. Therefore, we need a function to quantify the relationship of substitutability that incorporates the possibility of associativity. Our hypothesis is that two items are highly substitutable if they are consumed in similar dietary contexts.

We want to compute a substitutability score such as :

(1) Two items are highly substitutable if they are consumed in similar contexts. (2) Two items are less substitutable if they are consumed together. (3) Substitutability is a symmetrical relationship.

Let us denote, for an item x, the context set C x as the set of dietary contexts in which x is a substitutable item. If the cardinality of C x denoted as |C x | is high, then x is substitutable in many dietary contexts.

For two items x and y, the condition ( 1) is described by the intersection of C x and C y . If |C x ∩ C y | is high, then x and y are consumed in similar contexts.

We denote A x :y the set of contexts of x where y appears :

A x :y = {c ∈ C x |y ∈ c} (2)
The cardinality of A x :y denotes how y is associated to x.

Taking into account these considerations, we propose the substitutability score inspired by the Jaccard index [START_REF] Jaccard | The distribution of the flora in the alpine zone.1[END_REF]:

f (x, y) = |C x ∩ C y | |C x ∪ C y | + |A x :y | + |A y:x | (3)
The score equals 1 when x and y appear in exactly the same contexts and A x :y = A y:x = ∅. If x and y are never consumed in the same context then the score equals 0. The higher |A x :y | + |A y:x | is, the higher the association of x and y is and the lower the score is.

EXPERIMENTS 3.1 The INCA 2 database

The French dataset INCA 2 1 is the result of a survey conducted during 2006-2007 about individual food consumption. Individual 7-day food diaries are reported for 2624 adults and 1455 children over several months taking into account possible seasonality in eating habits. A day is composed of three main meals : breakfast, lunch and dinner. The moments in between are denoted as snacking.

For the main meals, the location (home, work, school, outdoor) and the companion (family, friends, coworkers, alone) are registered.

The 1280 food entries are organized in 44 groups and 110 subgroups of food items. We chose to consider the medium level of hierarchy in order to capture substitution relationships inter-groups and intra-groups.

Only adults are considered in this paper. All meals are gathered in a meal database DB meals regardless of the type of meal. The database can be split according to contextual information in order to get better results [START_REF] Baltrunas | Context-based splitting of item ratings in collaborative filtering[END_REF]. We compare the results of our methodology on three datasets : DB br eak f astlunch , DB br eak f ast and DB lunch .

Results

Applying our algorithm on DB br eak f ast yields 2368 contexts. Some of these and their substitutable sets are given in Table 1. Our results are coherent. For example, either bread, rusk or viennoiserie can be consumed for breakfast with coffee, sugar and water.

Context

Substitutable set coffee, sugar, water, butter bread rusk viennoiserie tea/infusions, donuts yogurt sugar jam/honey nothing Table 1: Results of context and substitutable set retrieval for breakfasts

We applied our algorithm to the three datasets. The results are reported in Table 2. We can see that we can obtain inter-group substitutions such as {potatoes ⇒ green beans} but also intra-group substitutions as {bread ⇒ rusk}.

The substitutions proposed are consistent with regards to eating habits. Substitutes of drinks are also drinks : the substitutes of coffee are tea, cocoa and chicory. It is also the case for spreadable food items : the substitutes for butter for breakfast are spreadable items. No semantic information describing how a food item can be eaten is available in the dataset and yet considering the dietary context helps us retrieving this kind of information.

Substitutions between food items of the same nutritional food groups are found. For instance, the substitutes for potatoes are pasta and rice: they all contain starches.

DISCUSSION AND CONCLUSIONS

We proposed a score of substitutability based on consumption data that can be used in a recommender system together with other scores such as a nutritional score that takes into account the nutritional contribution of the substitution and a user preference score. The substitutability score is based on the assumption that two items are substitutable if they are consumed in similar contexts. Preliminary results on the INCA2 dataset show that this assumption helps retrieving substitutability relationships based on consumption data.

When we split the dataset according to the contextual variable "type of meal", the substitutes and the scores are different. Coffee can be substituted by tea, chicory and coffee for breakfast whereas for lunch, it can be substituted by sodas, yogurt and fruits. Food items are consumed differently according to the type of meal. The relationship of substitutability is therefore different too.

Difference of scale in scores is noted according to the type of meal. It may be due to the fact that the diversity of food items consumed during lunch is higher than during breakfast. A rescaling factor based on the diversity of the type of meal can be introduced. As future work we plan to investigate this aspect and implement the nutritional score and the user preference related score.

ACKNOWLEDGEMENT

This study was funded by Danone Nutricia Research.

Figure 1 :

 1 Figure 1: Example of a simple meal network

HealthRecSysFigure 2 :

 2 Figure 2: Example of an uninteresting clique

Table 2 :

 2 Top 3 substitutable items for several items for breakfast and lunch

		Breakfast and lunch		Breakfast		Lunch
		Substitute item		Substitute item		Substitute item
	Food Item		Score		Score		Score
		(ordered by score)		(ordered by score)		(ordered by score)
		Rusk	0.2234	Rusk	0.3716	Fruits	0.0497
	Bread	Viennoiserie	0.1359	Viennoiserie	0.2010	Yogurt	0.0490
		Cakes	0.0745	Cakes	0.1243	Potatoes	0.0468
		Tea	0.2799	Tea	0.4219	Sodas	0.065
	Coffee	Cocoa	0.1729	Chicory	0.2550	Yogurt	0.0642
		Chicory	0.1486	Cocoa	0.2255	Fruits	0.0633
		Coffee	0.2799	Coffee	0.4219	Cakes	0.0536
	Tea	Cocoa	0.1721	Chicory	0.1965	Viennoiserie	0.0417
		Chicory	0.1289	Cocoa	0.1462	Coffee	0.0412
		Chicory	0.2171	Chicory	0.2211	Cereal bars	0.25
	Cocoa	Coffee	0.1729	Coffee	0.2077	Preprocessed vegetables	0.0526
		Tea	0.1289	Tea	0.1965	Hamburgers	0.0256
		Margarine	0.2413	Margarine	0.4030	Margarine	0.0602
	Butter	Honey/jam	0.0924	Chocolate spread	0.1240	Fruits	0.0431
		Chocolate spread	0.0786	Honey/jam	0.1175	Sauces	0.0431
		Juice	0.1409	Yogurt	0.1815	Doughnut	0.0869
	Milk	Yogurt	0.1264	Juice	0.1504	Other milk	0.0666
		Sugar	0.1089	Tap water	0.1361	Milk in powder	0.0625
		Sodas	0.0814			Sodas	0.0860
	Wine	Beer	0.0704	/	/	Tap water	0.0755
		Tap water	0.0412			Beer	0.0746
		Sandwich baguette	0.2429			Sandwiches baguette	0.2810
	Pizza	Other sandwiches	0.1729	/	/	Other sandwiches	0.2177
		Meals with pasta or potatoes	0.1513			Meal with pasta or potatoes	0.1658
		Pasta	0.1111			Pasta	0.1142
	Potatoes	Green beans	0.0922	/	/	Green beans	0.0941
		Rice	0.0602			Rice	0.0616

https://www.data.gouv.fr/fr/datasets/donnees-de-consommations-et-habitudesalimentaires-de-letude-inca-2-3/


V V Dotsenko

HOMOLOGY OF THE LIE ALGEBRA OF VECTOR FIELDS ON A LINE WITH COEFFICIENTS IN SYMMETRIC POWERS OF ITS ADJOINT REPRESENTATION

Keywords:

Homology of the Lie algebra of vector fields on the line

with coefficients in symmetric powers of its adjoint representation

Introduction.

Denote by W 1 the Lie algebra of polynomial vector fields on a line, i.e. the algebra of vector fields f (x) d dx , where f (x) is a polynomial. The vector fields e i = x i+1 d dx (i ≥ -1) form a basis in this algebra, and the commutation relations are [e i , e j ] = ( ji)e i+ j . We compute the homology of the Lie algebra W 1 with coefficients in modules S k W 1 , i.e. the symmetric powers of its adjoint representation. Namely, we prove the following results.

Main theorem. Let k > 0. Then

(i) H 2 (W 1 , gl 1 , S k W 1 ) = C, H i (W 1 , gl 1 , S k W 1 ) = 0 for i 2, (ii) H 2 (W 1 , S k W 1 ) = H 3 (W 1 , S k W 1 ) = C, H i (W 1 , S k W 1 ) = 0 for i 2, 3.
This proves the n = 1 case of the conjecture on the homology of the algebra W n with coefficients in symmetric powers of its adjoint representation stated by B. Feigin and B. Tsygan [START_REF] Feigin | Riemann-Roch theorem and Lie algebra cohomology[END_REF].

This computation is based on a partial computation of the homology (with the same coefficients) for a subalgebra of W 1 consisting of vector fields which vanish twice at x = 0. (This algebra is denoted by L 1 ; the elements e i with i ≥ 1 form a basis for this subalgebra. More generally, the subalgebra spanned by the elements e i with i ≥ k is denoted by L k .) In general, the homology of the Lie algebra L 1 with nontrivial coefficients are more complicated but in our case it turns out that L 1 -modules S k W 1 are free in low degrees. (To be more precise, this means that there exists a (homogeneous) homomorphism from a free L 1 -module onto S k W 1 , which has a trivial kernel on all homogeneous components whose degree is sufficiently small; see Corollary 2 below.) The homology with coefficients in a free module is known; if a module is free in low degrees, one can easily compute the corresponding graded component of its homology. Methods of studying the homology of W 1 on the basis of information about the homology of L 1 with the same coefficients are quite traditional (e.g., see [START_REF] Fuks | Cohomology of Infinite-Dimensional Lie Algebras[END_REF]).

The text is organised as follows. In the first part we study the symmetric powers in low degrees as L 1modules. This can be done by means of some linear algebra. (Actually, the point is that matrices of certain operators are upper-triangular.) In the second part of the paper, we use these results to obtain information about the homology of W 1 . This could be done by standard homological algebra techniques. We finish the paper with a discussion of the case of tensor powers of the adjoint representation; in particular, we suggest a (conjecturally almost exact) lower bound for the homology.

I am grateful to my teacher Boris Feigin for stating the problem and for stimulating discussions. I am also grateful to the anonymous referee for numerous suggestions for improving the text.

The work of the author is partially supported by the grant of the President of the Russian Federation 2044.2003.2 and by the INTAS grant 03-3350. [START_REF] Feigin | Riemann-Roch theorem and Lie algebra cohomology[END_REF]

Low degrees

We consider the standard grading on the Lie algebras W 1 and L 1 , deg e i = i. All the modules are supposed to be graded; the homomorphisms are assumed to be graded of degree zero.

Consider a natural ordering of the basis elements of W 1 : e i > e j for i > j. We take the standard monomial basis of S k W 1 consisting of the elements e i 1 e i 2 • . . . • e i k (-1 ≤ i 1 ≤ . . . ≤ i k ). Consider the following ordering of this basis: we drop all factors equal to e -1 compare the monomials e i 1 e i 2 • . . .• e i l with l ≤ k and 0 ≤ i 1 ≤ . . . ≤ i l ) using the degree-lexicographic ordering: the monomial with larger l is larger, and monomials having the same l are compared lexicographically. According to the Poincare-Birkhoff-Witt theorem [START_REF] Cartan | Homological algebra[END_REF], the elements E α := e α 1 e α 2 . . . e α n , where α runs over all multiindices (α 1 , . . . α n ) such that 0 < α 1 ≤ α 2 ≤ . . . ≤ α n , form a basis in the universal enveloping algebra U = U(L 1 ) for the Lie algebra L 1 . For these elements we also consider the degree-lexicographic ordering. For an element f ∈ S k W 1 , we denote by f its leading monomial with respect to the ordering introduced above.

Lemma 1. Let E α < E 1 k+1 = e k+1 1 . Then E α (e k -1 ) = k! (k -n)! (-1) n (1 + α 1 ) • • • (1 + α n )e k-n -1 e α 1 -1 . . . e α n -1 .
Proof. The proof is by a straightforward computation using the fact that the leading monomial is the monomial with the least number of occurrences of e -1 .

Corollary 1. Let E α < E β < e k+1 1 . Then E α (e k -1 ) < E β (e k -1
). For each module M we denote by M[p] the module obtained from M by the shift of grading by p, M [p]

i := M i-p . Corollary 2. The L 1 -module homomorphism ρ : U[-k] → S k W 1 mapping 1 to e k -1 is surjective. It is an isomorphism on the homogeneous components of degrees -k, 1 -k, . . .

, 0 in U[-k] and has one-dimensional kernel on the component of degree 1.

Proof. Surjectivity can be proved as follows: the leading monomials of the elements ρ(

E α ) = E α (e k -1
), where α runs over all multiindices (α 1 , . . . , α l ) of length l ≤ k (so that E α < e k+1 1 and we can use the previous corollary), are distinct. Moreover, all basis monomials of the symmetric power S k W 1 occur among these leading monomials. (By Lemma 1, the leading monomial of the element E α (e k -1 ) is, up to a constant factor, e k-l -1 e α 1 -1 • . . . • e α l -1 , and each basis monomial can be written in this form for a suitable α.) It follows that any monomial from the basis belongs to the image of ρ.

The statement concerning the isomorphism can be established in a similar way. The dimensions of the graded components of degrees -k, . . . , 0 in U[-k] coincide with the corresponding dimensions in the symmetric power (since for each basis element E α the length of of the multi-index α is at most k), and for the degree 1 the dimension differs by one (the only element for which the length of α is larger than k is e k+1 1 ). For subsequent use, we choose and fix a homogeneous element φ ∈ U[-k] of degree 1 such that ρ(φ) = 0.

Corollary 3. The L 1 -module S k W 1 has a free resolution of the type

0 ← S k W 1 ← U[-k] ← U[1] ⊕ M 1 ← M 2 ← . . . ← M i ← . . .

Here all the modules M i are free, and have nonzero graded components only in degrees larger than one.

Proof. We follow the general scheme for constructing a minimal resolution for a module. A surjective homomorphism ρ from U[-k] to S k W 1 is defined above. The next step is to construct a surjection from a free module onto its kernel. The kernel is generated by φ and finitely or infinitely many elements φ 1 , . . . , φ s , . . . of larger degrees n 1 , . . . , n s , . . .. It follows that there exists a surjection from the free module U [START_REF] Feigin | Riemann-Roch theorem and Lie algebra cohomology[END_REF] ⊕ s≥1 U[n s ] (the homomorphism maps the identity element of each summand to the corresponding generator), hence we may obtain the first module of the resolution by putting

M 1 := U[1] ⊕ s≥1 U[n s ].
The subsequent steps are similar; one should just note that the kernels of all the further homomorphisms may only contain elements of degrees larger than one.

It is known [START_REF] Fuks | Cohomology of Infinite-Dimensional Lie Algebras[END_REF] that homology of a Lie algebra A with coefficients in a module M can be computed in two different ways. First, this homology is equal to the homology of the Chevalley-Eilenberg complex C * (A, M) = Λ * (A)⊗M. Second, in terms of the universal enveloping algebra one has H * (A, M) = Tor U(A) * (M, C). In the latter case, we can use our results on the free resolution. To write out the result, we recall that the homology of a graded Lie algebra A with coefficients in a graded module M inherits the grading. We denote by H (p) * (A, M) the corresponding graded components. Proposition 1.

H 0 (L 1 , S k W 1 ) = H (-k) 0 (L 1 , S k W 1 ) = C, H (≤1) 1 (L 1 , S k W 1 ) = H (1) 1 (L 1 , S k W 1 ) = C, H (≤1) >1 (L 1 , S k W 1 ) = 0.
It is of interest to obtain some explicit formulae for the cycles representing these classes in the Chevalley-Eilenberg complex. Let ψ k be the unique nontrivial class of the first homology in degree 1 .

Proposition 2. The element

(1) k i=0 (-1) i k + 2 i e k+1-i ⊗ e k-i -1 e i 0 of the Chevalley-Eilenberg complex C * (L 1 , S k W 1 ) is a representative of ψ k .
Proof. A direct calculation shows that this element belongs to the kernel of the boundary map. It only remains to prove that this cycle is nontrivial. The easiest way to do this is to use the fact that the summand e 1 ⊗ e k 0 never occurs in a boundary map of some element of the Chevalley-Eilenberg complex. It is well known [START_REF] Fuks | Cohomology of Infinite-Dimensional Lie Algebras[END_REF] that L 1 is generated by e 1 and e 2 . Thus there exists also a representative of the type e 1 ⊗ m 1 + e 2 ⊗ m 2 . Let us give the corresponding explicit formulae, since they seem to be rather interesting. The main ingredient here is the "Casimir operator" e -1 e 1 -e 2 0 for the subalgebra sl 2 ⊂ W 1 spanned by e -1 , e 0 , e 1 . Proof. The reason for these cycles to be nontrivial is the same as above: a cycle containing e 1 ⊗ e k 0 with a nonzero coefficient does not belong to the image of the boundary map.

The main theorem

To calculate the homology of W 1 with coefficients in S k W 1 we use the Hochshild-Serre spectral sequence twice, in the absolute and in the relative case; we start with computation of the relative homology modulo the subalgebra gl 1 spanned by e 0 and then use the result of computation to prove the main theorem stated in the introduction.

Consider a chain of subalgebras gl 1 ⊂ L 0 ⊂ W 1 . The general description of the Hochshild-Serre spectral sequence for relative homology (see [START_REF] Fuks | Cohomology of Infinite-Dimensional Lie Algebras[END_REF]) in our case give a spectral sequence with the first page E 1 p,q = H q (L 0 , gl 1 , Λ p (W 1 /L 0 ) ⊗ S k W 1 ) which converges to the relative homology H * (W 1 , gl 1 , S k W 1 ). Let us calculate explicitly the space E 1 p,q . The relative homology are homology of the complex which is analogous to the Chevalley-Eilenberg complex. In our case for a fixed p it is a complex

Λ * (L 1 ) ⊗ Λ p (W 1 /L 0 ) ⊗ S k W 1 gl 1 .
It is easy to see that it can be identified with the subcomplex of all degree zero elements in the Chevalley-Eilenberg complex computing the homology of L 1 with coefficients in Λ p (W 1 /L 0 ) ⊗ S k W 1 . Using the results of the previous section, we obtain the complete information on the spectral sequence.

Lemma 2. The space E 1 1,1 is one-dimensional, and the other spaces E 1 p,q are zero. Proof. To reduce this statement to the results of the previous section, note that the L 1 -modules W 1 /L 0 and C[-1] (the trivial module with shifted grading) are isomorphic. Therefore E 1 1,q = E 1 1,q (0)

= H

(1)

q (L 1 , S k W 1 ). Moreover, E 1 0,q = E 1 0,q (0) = H (0) q (L 1 , S k W 1 )
. (The spaces E 1 p,q for p > 1 are obviously zero.) Now the lemma easily follows from these formulae.

Corollary 4. E n p,q = E 1 p,q .
Proof. This is true for all spectral sequences for which exactly one of the spaces E 1 p,q is nonzero.

Proof of the main theorem. By Corollary 4, the space E 1 1,1 survives in the page E ∞ of the spectral sequence. Since the spectral sequence converges to the desired homology, the first statement of the theorem follows.

To prove the second statement, we use the Hochshild-Serre spectral for subalgebra gl 1 ⊂ W 1 . The first term of this spectral sequence is E 1 p,q = H q (gl 1 , Λ p (W 1 /gl 1 ) ⊗ S k W 1 ), and so

E 1 p,0 = E 1 p,1 = Λ p (W 1 /gl 1 ) ⊗ S k W 1 gl 1 , E 1 p,k = 0 for k > 1.
Furthemore, the homology of d 1 for each p = 0, 1 coincide with the relative homology H * (W 1 , gl 1 , S k W 1 ). It follows that the term E 2 of the spectral sequence has nonzero entries only in one column. Since the subsequent differentials d k map this column into other columns, they all vanish, so E 2 = E ∞ , and the proof is complete.

Tensor powers

A natural extension of this computation is the computation of the homology with coefficients in tensor powers of adjoint representation. In general, this problem seems to be rather difficult. Here we present the results of computations for the tensor powers W ⊗k 1 with 1 ≤ k ≤ 4, some conjectures concerning the general case, and some corollaries of our computations for homology of the current Lie algebra

W 1 ⊗ C[t].
To simplify the statements more simple, we give a more detailed discussion of the case of relative homology modulo the subalgebra gl 1 ⊂ W 1 spanned by e 0 .

Consider the mapping

(2) H * (sl 2 , gl 1 , C) ⊗ sl ⊗n 2 sl2 = H * (sl 2 , gl 1 , sl ⊗n 2 ) → H * (W 1 , gl 1 , W ⊗n 1 )
, induced by the embedding sl 2 ֒→ W 1 . The homology of sl 2 modulo gl 1 is zero, except for H 0 and H 2 . Thus to describe this mapping it suffices to consider only the zero and second homology.

Proposition 4. The mapping (2) is zero on the space H 0 and is an embedding on the space H 2 .

Proof. The first assertion is obvious, since

H 0 (W 1 , gl 1 , W ⊗n 1 ) = 0; in fact, already W ⊗n 1 /e -1 W ⊗n 1 = 0. Consider the second homology. Let e -1 ∧ e 1 ⊗ ψ = d         0<α<β e -1 ∧ e α ∧ e β ⊗ ψ αβ + 0<α<β<γ e α ∧ e β ∧ e γ ⊗ ψ αβγ         .
Then ψ = 1<β e β (ψ 1β ), which results in a contradiction, since ψ is an sl 2 -invariant element in sl ⊗n 2 , and e β W ⊗n do not even belong to sl ⊗n 2 , and for β = n = 2 the intersection with the tensor power of sl 2 is one-dimensional, and the corresponding element e 2 (e 2 -1 ) is not invariant.

Remark 1. We believe that the thus obtained lower bound for the second homology is almost sharp. Of course, for k = 2m + 1 the main theorem ensures that dim H 2 (W 1 , gl 1 , S k W 1 ) = 1, while dim H 2 (sl 2 , gl 1 , S k sl 2 ) = 0. However, all cycles known so far to lie outside the image of the embedding constructed here are the cycles ψ 2k-1 , k = 1, 2, . . . for odd symmetric powers.

For 1 ≤ k ≤ 4, an explicit calculation shows that the relative homology with coefficients in W ⊗n 1 is exhausted by the image of embedding from Proposition 4 and the homology with coefficients in symmetric powers. The results of this computation are gathered in the following proposition. The proof is technical and therefore omitted.

Proposition 5. H i (W 1 , gl 1 , W ⊗k 1 ) = 0 for i 2, 1 ≤ k ≤ 4. Furthermore, H 2 (W 1 , gl 1 , W 1 ) = H 2 (sl 2 , gl 1 , sl 2 ) ⊕ H 2 (W 1 , gl 1 , S 1 W 1 ) = C 0 ⊕ C 1 = C, H 2 (W 1 , gl 1 , W ⊗2 1 ) = H 2 (sl 2 , gl 1 , sl ⊗2 2 ) = C, H 2 (W 1 , gl 1 , W ⊗3 1 ) = H 2 (sl 2 , gl 1 , sl ⊗3 2 ) ⊕ H 2 (W 1 , gl 1 , S 3 W 1 ) = C 1 ⊕ C 1 = C 2 , H 2 (W 1 , gl 1 , W ⊗4 1 ) = H 2 (sl 2 , gl 1 , sl ⊗4 2 ) = C 3 . Corollary 5. H i (W 1 , W ⊗k 1 ) = 0 for i 2, 3, 1 ≤ k ≤ 4. Furthermore, H 2 (W 1 , W 1 ) = H 3 (W 1 , W 1 ) = C, H 2 (W 1 , W ⊗2 1 ) = H 3 (W 1 , W ⊗2 1 ) = C, H 2 (W 1 , W ⊗3 1 ) = H 3 (W 1 , W ⊗3 1 ) = C 2 , H 2 (W 1 , W ⊗4 1 ) = H 3 (W 1 , W ⊗4 1 ) = C 3 .
Conjecture. For i > 2 and all k, we have H i (W 1 , gl 1 , W ⊗k 1 ) = 0; for i > 3 and all k, we have H i (W 1 , W ⊗k 1 ) = 0.

Proposition 5 and Corollary 5 suggest that even the stronger conjecture replacing the condition i > 2 (respectively, i > 3) by i 2 (respectively, i 2, 3) might be true. It turns out that this is not the case: for example, the first homology is not zero for W ⊗5 1 . Indeed, let us consider the action of the symmetric group S 5 on W ⊗5 1 by permutations of the factors. The decomposition of the tensor power into the direct sum of isotypic components is known: this representation is obviously isomorphic to the representation in the space of all polynomials in five variables (the gradings of these vector spaces differ only by a shift), and the results on the decomposition of latter representation are standard. For the representation of S 5 corresponding to the partition 5 = 2 + 1 + 1 + 1, the minimal degree of homogeneous polynomials in five variables where that representation occurs is equal to 6; moreover, this representation occurs in the subspace of polynomials of degree 6 with multiplicity 1. Shifting the grading, we see that for W ⊗5 1 this representation occurs for the first time in degree 1 with multiplicity 1. Denote by V the corresponding subspace. Then it is easy to see that any element of the space e -1 ⊗ V is a cycle in the Chevalley-Eilenberg complex (both the relative one and the ordinary one) which is nontrivial, since this representation does not occur in lower degrees.

Information on the homology with coefficients in tensor powers is useful in that it can be used for homology computations for the Lie algebra of (polynomial) currents on a line with values in W 1 . Recall that the algebra of polynomial currents on a line with values in a Lie algebra A is the vector space A ⊗ C[t] equipped with a bracket [a ⊗ f, b ⊗ g] = [a, b] ⊗ ( f g). The computation uses the Hochshild-Serre spectral sequence modulo the subalgebra W 1 ⊗ 1. We list here without a proof the results on the relative homology modulo the subalgebra gl 1 :

= Ce 0 ⊗ 1 ⊂ W 1 ⊗ 1 ⊂ W 1 ⊗ C[t].
It is convenient to state the results as follows. The Lie algebra of vector fields on the t-line acts on the current algebra by an obvious rule ξ(a ⊗ f ) = a ⊗ ξ( f ). This action can be extended in a standard way to all tensor constructions, for example, to exterior powers and to the entire Chevalley-Eilenberg. Obviously, this action commutes with the boundary maps, and so the Lie algebra of vector fields on the line acts on the homology. These formulas should be interpreted as isomorphisms of modules over the Lie algebra of vector fields on the line.

Proposition 3 . 0 m-++ 2 0 m- 1 (e -1 e 2 -

 30212 For k = 2m the element e 1 ⊗ e -1 e 1 -e 2 0 m is a representative for ψ k , for k = 2m + 1 the formula is sligtly more complicated: e 2 ⊗ e -1 e -1 e 1 -e 2 (2m + 3)e 1 ⊗ e 0 e -1 e 1 -e 2 0 m me 1 ⊗ e -1 e -1 e 1 -e e 0 e 1 ) .

1 ∩ sl ⊗n 2 sl2= 0 :

 120 for β > 2 or β = 2, n > 2 the elements from e β W ⊗n

1

 1

  W 1 ⊗ C[t], gl 1 , C) C, H 1 (W 1 ⊗ C[t], gl 1 , C) 0, H 2 (W 1 ⊗ C[t], gl 1 , C) C, H 3 (W 1 ⊗ C[t], gl 1 , C) C[t] dt, H 4 (W 1 ⊗ C[t], gl 1 , C) 0, H 5 (W 1 ⊗ C[t], gl 1 , C) S 3 (C[t]dt).


Evelyne Cauzinille-Marmèche

Gérard Collet

Antoine Cornuéjols
email: antoine@lri.fr

Andrée Tiberghien
email: andree.tiberghien@cri.ens-lyon.fr

Co-Adaptation of Students' Knowledge Domains when Interpreting a Physical Situation in Terms of a New Theory

Keywords: Knowledge acquisition, didactics, learning complex knowledge, semantic matching, teaching of energy concept

In the context studied here, learning occurs in response to an interpretative task where the theoretical model is provided in a declarative format to the learners. Consequently, learning foremost implies setting up matches between the knowledge associated with the perception of the world and entities of the new knowledge domain, all being subjected to constraints from both knowledge domains. We have gathered evidence about failed attempts at matches by the subjects, and the "repair strategies" they use to overcome these obstacles, consisting mainly in changes of the knowledge representation primitives, activation of new classes, and creation of new ones.

INTRODUCTION

In the research reported in this paper, we focus our attention on the learning of a new knowledge domain by highschool students. We have centered our investigation on the processes at play when two knowledge domains are confronted, one, the world of immediate perceptions, common sense knowledge and heretofore learned models, and the other, a new theory presented in a declarative format. The acquisition of this new theory can potentially transform the way some aspects of the world are interpreted and perceived. Learning is therefore considered as the acquisition of a new interpretative (and predictive) model of the world, by contrast to the acquisition of new categories or problem-solving strategies, and it is effected by the operationalization of a given declarative theory implying both learning to identify the terms of the theory and learning to make it effective.

New concepts, in this setting, cannot simply be added to the existing ones, they need to be articulated with the former knowledge, which means establishing new links with it and stressing what prove to be relevant aspects, but also, in return, modifying existing knowledge. In this process new concepts are to become operational, that is active in the whole interpretative process of the subject.

In this view, learning foremost implies attempts at matching active pieces of existing knowledge with new terms, under the requirements of both the rules of the new theory and constraints of the existing ones. We have therefore studied how different parts of knowledge are activated and how they are made to fit and reinforce each other in specific and controlled problem-solving activities. In this paper, we specifically study the failed attempts, when matches are problematic to the students, and the adaptation or repair strategies used to overcome these difficulties which usually correspond to modifications of the new concepts or the existing knowledge, or both. We make the hypothesis that this is where conceptual learning takes place.

The matches involved here, as well as the "repair mechanisms" that students use when direct matches fail, do not fit into the classical framework, regarding matching and knowledge acquisition, on several basic accounts. For instance, in analogical reasoning [START_REF] Gentner | Structure mapping: a theoretical framework for analogy[END_REF][START_REF] Gentner | The mechanisms of analogical learning[END_REF][START_REF] Holyoak | Surface and structural similarity in analogical transfer[END_REF][START_REF] Holyoak | A computational model of analogical problem solving[END_REF][START_REF] Ross | Remindings in learning and instruction[END_REF], only homogeneous entities, described within the same language and at the same abstraction level, are considered for matching. This is wholly inadequate to describe processes at work when subjects are struggling with a new conceptual domain, bringing into play knowledge pieces involving different abstraction levels and different backgrounds. In addition to this, most knowledge changes that follow analogical matches are viewed as discrimination or generalization operations whereas the transformations that accompany the interpretation and modeling of physical situations involve more complex knowledge structures and a wider class of processes.

TASKS PRESENTATION

In our study, highschool students (16-17 years old), working in pairs, are introduced to a pre-theory about energy. It is presented in a declarative form with a number of concepts and properties definitions alongside with class descriptions and fundamental principles (see Table 1).

Energy Theory / Model (Seed)

Theory (seed) Model (seed)

Energy can be characterized by : * its properties:

-Storage

The reservoir stores energy -Transformation

The transformer transforms energy -Transfer Between a reservoir and a transformer, or between two reservoirs, or between two transformers, there is transfer of energy. The different modes of transfer of energy from a system to another one are :

-by work , There is transfer of energy under the form of mechanical work when there is movement of an object or of a part of an object during an interaction, under the form of electrical work when there is an electrical current (displacement of charges) -by heat , -by radiation .

To build an energy chain * the drawn symbols are to be used: res.

tr.

for reservoir for transformer for transfer by indicating :

-in each rectangle the system corresponding to the experiment;

-under each arrow the mode of transfer;

by putting -an arrow by the mode of transfer.

Energy can also be characterized by : *a fundamental principle of conservation The energy is conserved whatever the transformations, transfer and forms of storage * the following rules are to be used: -a complete energy chain starts and ends with a reservoir; -the initial reservoir is different from the final reservoir.

Table 1. Text given to the students presenting a seed of energy theory/model.

Subjects must then interpret and explain a few physics experiments using this pre-theory, in the process turning it into an operational knowledge domain. (Task 1) Battery -bulb -two wires (Figure 1) ; (Task 2) An object is hanging on a string falls, and a bulb is connected to the terminals of the motor (Figure 2). (Task 3) A battery powers an electrical motor. On the axle of the motor a string is attached. An object is hanging on this string (Figure 2). This implies that connections be established between an existing and compelling perception of the world, the associated knowledge and a theoretic model under construction, all forms of knowledge that are quite disparate. Furthermore, the new theory, because it is described using known terms (such as "heat" or "reservoir"), and the knowledge about objects and events involved in the perception of the situation, are related to other interpretative domains (such as knowledge pertaining to electricity). As a result, the discovery and acquisition of a new conceptual domain not only requires that connections be set up between the knowledge directly associated with the perception of the situation and the theory, but also that this be done in the context of other, diverse and more or less related, knowledge domains [START_REF] Tiberghien | Modelling as a basis for analysing teaching-learning situations[END_REF][START_REF] Tiberghien | Construction of Prototypical Situations in Teaching the Concept of Energy[END_REF].

METHODOLOGY

Our analysis has concentrated on manifestations of difficulties in the course of the problem solving activity of the students as revealed in the dialogues. We take that a difficulty is encountered whenever there is an interrogation from the students that they are unable to solve immediately. For instance, the following exchange :

Lionel : "A reservoir to start and a reservoir to end" Fulvia : "Do we have two batteries Lionel ?" Lionel : "No !" Fulvia : "So what did we miss ?"

is interpreted as a difficulty to reconcile the needs of the Theory-Model World (W TM ) (demanding that an energetic chain starts and ends with a reservoir) and the perception of the experimental setting, in the Objets-Events World (W OE ), which includes only one battery (currently interpreted as a reservoir). We analyzed indepth the solving activity of six pairs of students.

ANALYSIS

The study of the students' difficulties, as disclosed from the analysis of the dialogues, shows that it is possible to categorize them into two main classes :

• Difficulties pertaining to the differences between entities that prevent direct matches. Mostly, there are where the "definitional attributes" of entities of each world to be matched do not fully fit.

• Difficulties due to global constraints on the interpretation under construction (for instance, the current interpretation demands that there are two transfers).

When encountering a difficulty, the subjects either can try to retract their attempt and backtrack on other alternatives, or, more interestingly, they can try to adapt their knowledge in order to ease the connection. Again, the potential changes can be organized along two categories that closely reflect the classification of the difficulties.

• Changes to the semantical primitives of the knowledge (e.g. modification or suppression of the attributes or creation of new ones, introduction or suppression of links between certain primitives, and so on).

• Changes to the structure of the current interpretation.

It is furthermore possible to distinguish changes according to the knowledge domain involved. There are thus changes that occur within W OE or within W TM or that occur in both. There are also changes consisting in introducing intermediary entities.

These changes are effected through procedures that we call repair strategies. They are mechanisms employed by the subjects in order to adapt the knowledge or interpretation and satisfy the constraints imposed by the task and the given theory/model. The analysis of the activity of the six chosen pairs of students led us to define three main repair strategies.

• Change of the knowledge representation primitives (e.g. addition of properties, modification of the range of the values of a property, deletion of properties, " reification " of a property, addition or deletion of links between certain primitives, etc.).

• Activation of new classes (selected through a change of point of view, by dissociation or fusion of new classes, and so on).

• Creation of new classes.

In the following, we illustrate some of these strategies, using data from our protocols.

Change of the knowledge representation primitives (in W OE and/or W TM ) Addition of a property

Example relative to the second task (falling weight). For reasons not to be detailed here, the students are ready to associate electrical wires to transfer. However, they do not find immediately a common definitional attribute (such as mode of transfer). But they know that solar rays are an instance of transfer. They make up an analogy between solar rays and electrical wires, by posing that both have the attribute 'hot', and because this attribute seems related to the reason why solar rays are transfer, they are content to associate, for the same reason, wires with transfer.

The obstacle to the match between an object of W OE , and a class from W TM is overcome here by assigning a new attribute to the object of W OE . This result is obtained by analogical reasoning. There is import of a relevant attribute from another entity in W OE that is known to be an instance of the entity of interest in W TM .

Deletion of properties.

Example relative to the second task (falling weight). The falling weight in task 2 would be a good candidate for being associated with the " reservoir " class of W TM . However, there is no enclosure for storage in that case. The students choose to ignore this property that, thus far, they always associated with reservoir.

The difficulty is here solved ignoring a property if there are other compelling reasons to match the two entities.

Reification of a property.

Example relative to the first task (battery -electrical bulb). The students are hinted that solar rays do play a transfer role in a given instance of an energy chain. One prominent property of solar rays is that they are hot. Besides, one mode of energy transfer is 'heat'. Students associate (to the point that they become identified) 'hot' with 'heat', and thus are content that solar rays transfer energy through a heat mode.

In this case, the difficulty is that one property of one entity in W TM is not shared by a would-be match in W OE .

The repair mechanism consists in reifiing this property so that it becomes a property of W OE and is found in the would-be match.

Activation of new classes. New classes selected through a change of point of view

A change of point of view regarding one (or more) entities may lead to changing their semantics, viewing them at a more abstract level, or selecting new classes. In the following, we produce three instances of such changes.

Transforming an isolated entity into a relational entity

Example relative to the third task (rising weight). Ruling out other possibilities, the students are led to the comparison of the rising weight and a transformer. Transformer is a relational concept implying that a mode of energy "before" the transformer be transformed into another "after" form. Students are therefore enticed to look up for energy modes "before" and "after" rising weight. They end up identifying energy mode "before" with work and energy mode "after" with heat (the string would get hot during the rise !).

The consists in transforming a non relational entity in W OE into a relational one. The problem is solved by importing the relations from the entity of W TM to be matched and identify potential candidates in W OE that could play the role for the relations. This example illustrates the modification of perceiving the W OE from the point of view of W TM constraints.

Climbing to a more general point of view by considering superclasses

Example relative to the second task (falling weight). Falling weight does not have the definitional attributes provided in the W TM (i.e. storage property). However, there are reasons based on global considerations, not detailed here, why falling weight should be matched against initial reservoir. It happens that (initial) reservoir has increasingly be associated with the abstract superclass Causal_Agent. And it is indisputable that falling weight is the cause of the phenomena observed in the experimental situation (e.g. rotating motor, enlightening bulb). Therefore, reservoir and falling weight are instances of the same superclass that take a definitional role, and thus they can be matched.

The nature of the difficulty was to find a new definitional attribute between entities of each world to be matched so that they share the same value for this attribute. The repair mechanism consists in finding a common superclass, and take it as a new definitional attribute.

Modifying the semantics of entities and properties by appealing to intermediary concepts.

Example relative to the second task (falling weight). The students are not sure about the first reservoir. They have learnt that it is a Causal_Agent, they want to check if falling weight is a Causal_Agent too. To this purpose, they try to interpret the experiments in terms of the behavior of energy going through the different elements in the experiment. They provide energy with behavioral properties : moving, going through. That way, they satisfy themselves that falling weight is the starting "cause".

The difficulty was to verify that some property is shared by would-be matched entities in W TM and W OE . The repair mechanism consists in interpreting this property in modifying the level of a theory concept and giving it properties of the material world. This "new" concept becomes an intermediary between the two worlds.

New classes selected by dissociation of existing classes

Example relative to the first task (battery-electrical bulb). According to the W TM , an energy chain includes at least two different reservoirs, one starting the chain and one ending it. Thus far in the dialogue, the students have interpreted the battery as the first reservoir. Now they are looking for the final one. Because of the electrical model where the experimental setting can be interpreted as a closed circuit starting and ending in the battery, they are led to consider the possibility that the battery be also the final reservoir. But then, how to make it different from the starting one ? They end up dissociating the battery into two virtual batteries : a first one, the starting reservoir when the battery is full, a second one, the final reservoir, when the battery is empty.

The difficulty was to satisfy a global constraint on the interpretation that imposes finding in the W OE world one or more new entities that are copies of an existing one (e.g. having two different reservoirs instead of one currently). The repair mechanism consists in dissociating one existing entity in W OE to make two or more.

Students consider one entity of W OE (e.g. the battery) that is currently associated with the entity that must exist in two or more exemplars (e.g. reservoir). They then consider one attribute (e.g. state) of this entity, and specialize (dissociate) that entity by taking two or more different values of this attribute (e.g. state = full; state = empty). Finally, they associate each of these new entities of W OE to counterparts as required by the constraints.

Here again, the modification of perceiving the W OE is involved

CONCLUSION

This research calls attention to forms of learning that are not as-well documented than generalization, categorization or operationalization of problem-solving strategies are. In the context studied here, learning occurs in response to an interpretative task where the theoretical model is provided in a declarative format to the learners. Consequently, learning foremost implies setting up matches between the knowledge associated the perception of the world and entities of the new knowledge domain, all being subjected to constraints from both knowledge domains. Our experimental methodology allows to gather evidence about failed attempts at matches by the subjects, and the "repair strategies" they use in order to overcome these obstacles and satisfy the constraints.

Our analysis has brought up three main categories of repairs: change of the knowledge representation primitives, activation of new classes (through a change of point of view, or by dissociation or fusion of existing classes), and creation of new ones. This grid may be useful to interpret how students gradually acquire a new conceptual domain, specially when they have to put in correspondence very disparate entities.

Figure 1 :

 1 Figure 1 : The first experimental setting and its corresponding energy chain.

Figure 2 :

 2 Figure 2 : Experiments (2) and (3) with expert solutions


Antoine Cornuéjols
email: antoine@lri.lri.fr

Getting Order Independence in Incremental Learning

It is empirically known that most incremental learning systems are order dependent, i.e. provide results that depend on the particular order of the data presentation. This paper aims at uncovering the reasons behind this, and at specifying the conditions that would guarantee order independence. It is shown that both an optimality and a storage criteria are sufficient for ensuring order independence. Given that these correspond to very strong requirements however, it is interesting to study necessary, hopefully less stringent, conditions. The results obtained prove that these necessary conditions are equally difficult to meet in practice.

Besides its main outcome, this paper provides an interesting method to transform an history dependent bias into an history independent one.

Introduction

Ordering effects in Incremental Learning have been widely mentioned in the literature without, however, being the subject of much specific study except for some rare pioneering works [START_REF] C O R N U É J O L S | An Exploration into Incremental Learning : the INFLUENCE System[END_REF][START_REF] Fisher | Ordering Effects in COBWEB and an Order-Independent Method[END_REF][START_REF] M A C G R E G O R | The Effects of Order on Learning Classifications by Example: Heuristics for Finding the Optimal Order[END_REF], and, incidentally, in 2] 1 . In short, ordering effects are observed when, given a collection of data (e.g. examples in inductive concept learning), different ordered sequences of these data lead to different learning results. In this respect, ordering of data therefore seems to be equivalent to a preference bias that makes a choice among all the models or hypotheses that the learning system could reach given the collection of data (that is the models that would be obtained had the collection of data been presented in every possible orders). Hence, ordering undoubtedly amounts to some additional knowledge supplied to the system. This is why teachers have some value: by selecting suitable pedagogical presentations of the material to be learned they provide further knowledge that hopefully helps the learning process.

Learning without some bias that allows the reduction of the search space for the target concept or model is impossible except in the crudest form of rote learning. When looking more closely, it is usual to distinguish between :

-representation bias : where the search space is constrained because all partitions of the example space can not be expressed in the hypothesis space considered by the system (this is the basis for inductive generalization and is the main topic of current Machine Learning theory [START_REF]Machine Learning. A Theoretical Approach[END_REF]), and -preference bias : which dictates which subspace should be preferred in the search space (e.g. prefer simple hypotheses over more complex ones) (this type of bias has been much less studied because it touches on procedural aspects instead of declarative ones only).

Because ordering of inputs allows one to favor some models over some others, it seems to amount to a preference bias that chooses between competing hypotheses. In spite of this resemblance however, there is a deep difference with the biases generally discussed in Machine Learning. Indeed, with ordering effects, one observes the preference but cannot pinpoint directly where in the learning system it lies and how it works. This is in contrast with what is considered classically as a bias, where one can identify operational constraints _e.g. isolate representation constraints or procedures for choice between hypotheses. Thus we use the term global preference bias to denote preference among models due to ordering effects after a sequence of inputs has been observed, and the term local preference bias to denote the local choice strategy followed by the system when at each learning step it must choose to follow some paths and discard others.

Two questions then immediately come up :

1-What is the relationship between a global preference bias and a local one ?

2-What is the relationship between a global preference bias that is observed or aimed at and a corresponding teaching strategy that specifies the order of inputs ? In other words, how to design a teaching strategy so as to get a certain global preference bias ?

The second question is related to the recently introduced concept of teachability [START_REF] Goldman | On the Complexity of Teaching[END_REF][START_REF]Inductive Learning from Good Examples[END_REF][START_REF] Rivest | Learning Complicated Concepts Reliably and Usefully[END_REF][START_REF] Shinohara | Teachability in Computational Learning[END_REF][START_REF] Salzberg | Learning with a helpful teacher[END_REF] and the not so recent concern for good training sequences [START_REF] Van Lehn | Learning one subprocedure per lesson[END_REF][START_REF]Learning structural descriptions from examples[END_REF]. However, it differs in a fundamental point in that, in the former the problem is essentially the determination of good examples to speed up learning, whereas in our setting we assume that the collection of instances is given a priori and our only degree of freedom lies in the choice of a good ordering. Additionally, researchers in the teachability concept have not been interested with the idea of guiding the learner toward some preferred model and away from others, they seek to characterize the learnability of concept classes irrelevant of particular preferences within the classes. Keeping in mind these differences, the emphasis on providing additional knowledge to the learner through an educational strategy is the same.

In order to answer these questions, and particularly the first one, it is necessary to determine the causes of the ordering effects.

Causes of ordering effects

It is instructive to look at incremental learners that are NOT order dependent, like the candidate elimination (CE) algorithm in Version Space [START_REF] Mitchell | Version Spaces : an Approach to Concept Learning[END_REF][START_REF] Mitchell | Generalization as Search[END_REF], ID5R [START_REF] Utgoff | Incremental Induction of Decision Trees[END_REF], or systems that are not usually considered as learning systems but could be, such as TMS [START_REF]A truth maintenance system[END_REF] or some versions of the Bayesian Inference nets of Pearl [START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF]. They all have in common that they do not forget any information present in the input data. Thus, even when they make a choice between alternative hypotheses, like ID5 or TMS and unlike the CE algorithm, they keep enough information to be able to compare all potential competing models so as to select the best one at any moment, and change their mind if needed. They are therefore equivalent to non-incremental learning systems that get all the data at once and focus on the best hypothesis given the information supplied.

To sum up, order independent incremental learners (i) are able to focus on a optimal hypothesis when they have to choose among the current potential ones; and (ii) they do keep enough informations so as to not forget any potential hypothesis. If one or both of these properties is lacking, then incremental learning is prone to be order dependent. A closer look at each of these property in turn will help to see why.

(i) Optimality vs. non optimality.

Since the influential thesis and papers of Mitchell [START_REF] Mitchell | Version Spaces : an Approach to Concept Learning[END_REF][START_REF] Mitchell | Generalization as Search[END_REF], is has become commonplace to consider learning as a search process in a concept or solution space. Whatever the form (generalization, explanation,...) and the constraints on the hypothesis space (e.g. representation language bias), the learner is searching the best solution in this space given the data at hand. In order to compare the solutions in the search space, it is possible to imagine that the learner evaluates and grades each one of them and then chooses the top one. Of course, the grade and therefore the rank of these solutions can be modified if the data are changed.

Because incremental learners usually function by adapting a current solution (or a small solution set) to cope with new informations, they proceed typically in a hillclimbing fashion (see figure 1) open to the draw-back of missing the global optimum solution in favor of local ones.

State of the system at time n-1

Direction of the gradient at time n Fig. 1. At time n-1, the system is in a state corresponding to a given hypothesis. At time n, with a new arriving piece of data, the value of each hypothesis is re-evaluated and the system follows the direction of greatest gradient to reach a new state.

As underlined above, one must realize that in contrast to the common optimization problems where the optimums and the whole topology of the search space are set once and for all before the search starts, in incremental learning the topology is changed with each new input and the solutions in the hypothesis space are therefore open to reevaluation, new optimums replacing old ones. Because of this, incremental learning wandering from one local and temporary optimum to the next can be order dependent unless it reaches the global current optimum at each step that is with each arriving data 2 . In that case of course, at the end of the training period and given that all the training data have been observed, the system would reach the global optimum for this set of data regardless of its ordering during learning.

In fact, it is easy to see that there is a second caveat in addition to the requirement of finding the global optimum at each time.

(ii) To forget or not to forget.

Finding the optimal solution at each step is operating only to the extent that the set of all possible solutions is brought to consideration; if only part of it is available then the whole optimization process is bound to be suboptimal. Now, beside adapting the current solution to new constraints expressed under the form of new data, 2 Finding the global optimum at each step requires either to keep in memory all possible hypotheses, re-evaluate them and take the best one, or, short to this memory intensive method, to be able to re-construct any possible hypothesis with enough accuracy and keep track to the best one so far. This latter method is closed in spirit to Simulated Annealing or to Genetic Algorithms. In mathematics, this corresponds to ergodic systems.

incremental learners because they entertain only some preferred hypothesis or model, can also discard in the process part of the information present in the past inputs. If this forgetting is dependent upon the current state of the system, then it follows that it may also be dependent upon the ordering of the inputs. Therefore the resulting learning may be order dependent.

It is important to note that these two reasons if often tied (this is because one keeps only a current solution for adaptation that one is tempted to forget informations about other possibilities) are nonetheless independent in principle and can be observed and studied separately. For reasons that will be exposed shortly, we will concentrate on the forgetting aspect of incremental learning and will accordingly assume, by way of an adequate framework, that the best alternatives among the available ones can always be chosen by the learner.

Forgetting of information lies therefore at the heart of order dependence in incremental learning. But forgetting can take two faces. In the first one, information present in the input data is lost, meaning that the current hypothesis space considered by the learner is underconstrained . In the second one, by contrast, what is lost are potential alternatives to the current preferred hypotheses, which amounts to overconstraining the space of possibilities.

This last form of forgetting is equivalent to a local preference bias which chooses among competing hypotheses which ones to pursue.

This raises then a more specific question than the aforementioned ones, but which contributes to the same overall goal :

3. In which case an incremental learner can be order independent ? Or, in other words, which information can be safely forgotten without altering the result of learning whatever is the ordering of inputs ?

It is this last question that this paper focuses on. It must be kept in mind that it is equivalent to the question : what local preference bias leads to a null global preference bias (i.e. to order independence) ?

In the following of the paper, we will restrict ourselves to a simple concept learning model in which the learner attempts to infer an unknown target concept f, chosen from a known concept class F of {0,1}valued functions over an instance space X. This framework allows us, in the next section, to define a measure of the information gained by the learning system and of the effect of a local bias on this information. This measure naturally suggests an equivalence relation between local preference bias and additional instances, which is detailed in section 4. Then, in section 5, it becomes a relatively simple matter to answer question 3 above. The conclusion compares the framework adopted here with the emerging one of teachability and discusses the results obtained.

Information measure and local preference bias

In this section, we are interested in formalizing and quantifying the effect of a local preference bias on what is learned by the system. For this, we first define a characterization of the information maintained by a learner.

Let F be a concept class over the instance space X, and fOEF be a target concept. The teacher has a collection of examples EX={x i ,f(x i )} at his disposal, and makes a sequence x=x 1 ,x 2 ,...,x m ,x m+1 ,... with x m OE EX for all m. The learner receives information about f incrementally via the label sequence f(x 1 ),...,f(x m ),f(x m+1 ),... For any m≥1, we define (with respect to x ,f) the mth version space :

F m (x,f) = {f ^ OEF : f ^(x 1 ) = f(x 1 ),...,f ^(x m ) = f(x m )}
The version space at time m is simply the class of all concepts in F consistent with the first m labels of f (with respect to x). F m (x,f) will serve as a characterization of what is known to the learner at time m about the target concept f.

We know from Mitchell [START_REF] Mitchell | Version Spaces : an Approach to Concept Learning[END_REF] that the version space can be economically represented and stored using the boundary sets S-set (set of the most general hypotheses that are more specific than the concepts in the version space), and G-set (set of the most specific hypotheses that are more general than the concepts in the version space) 3 . Each new example (x m ,f(x m )) provides new information if it allows to reduce the version space by modifying, through the CE algorithm, either one of the boundary sets. Generally, the S-set and the G-set contain many elements, and in worst cases, they can grow exponentially over some sequences of examples [START_REF] Haussler | Quantifying inductive bias: AI learning algorithms and Valiant's learning framework[END_REF].

A local preference bias is a choice strategy which, at any time m, discards parts of the current version space, generally in order to keep the boundary sets manageable.

In this way, it reduces the version space and acts as if there had been some additional information that had allowed to constrain the space of hypotheses. The next section gives a closer look at this equivalence.

Bias and additional instances

We assume that the incremental learner maintains a version space of potential concepts by keeping the boundary sets. We assume further that the local preference bias, if any, acts by removing elements of the S-set and/or of the G-set, thus reducing the version space. Indeed, in so doing, it removes from the version space all concepts or hypotheses that are no longer more general than some element of the S-set and more specific than some element of the G-set. Besides, the resulting version space keeps its consistency since, in this operation, no element of the resulting S-set become more general than other elements of the S-set or of the G-set, and vice-versa, no element of the G-set can become more specific than other elements of the G-set or of the S-set. 3 To be exact, a subset of the concept space can be represented by its S-set and G-set if and only if it is closed under the partial order of generality of the description language and bounded. This is the case for most learning tasks and concept representations and particularly when the description language consists in the set of all conjunctive expressions over a finite set of boolean features. See [START_REF]Incremental Version-Space Merging[END_REF] for more details.

To sum up, we now have a learning system that forgets pieces of information during learning by discarding potential hypotheses, but at the same time is optimal since, in principle, by keeping the set of all the remaining hypotheses, it could select the best among them. In that way, we isolate the effect of forgetting without intermingling with non optimality effects.

We are interested in studying the action of a local preference bias (which has been shown to be equivalent to the forgetting of potential hypotheses) along all possible sequences of data. More specifically, we want to find what type of local bias (or forgetting strategy) leads to no ordering effects, that is for which all training sequences conduct to the same resulting state.

Initial state

State after learning

n! sequences What makes this problem difficult is that the action of the local preference bias depends on which state the system is in, and therefore depends on the training sequence followed. This implies in turn that all training sequences should be compared in order to find conditions on the local bias.

A very simple but very important idea will allow to circumvent this obstacle. It has three parts : (i) and (ii) allow to realize (iii) if it can be shown that the effect of the local bias b 1 is the same as the effect of additional instances given by an oracle or bias b 2 to an order independent learner. In other words, if it can be proved that any forgetting of hypothesis is equivalent to observing extra instances, then, conditions on b 1 will amount to conditions on the addition of fictitious instances to an order independent learning algorithm. Of this powerful idea, we will make a theorem.

Theorem 1 : With each choice it makes, the local preference bias acts as if additional examples had been known to an order independent learner.

Proof : (i) Case of the reduction of the S-set. For each element g i of the S-set it is possible to find additional fictitious examples which, if considered by the CE algorithm, would lead to its elimination of the S-set. It suffices to take the positive instances covered by (or more specific than) all g j such that (g j OE S-set and j≠i) and not covered by g i or excluded by the G-set . As a result, the CE algorithm would not have to modify the G-set nor the g j such that (g j OE S-set and j≠i) and it would generalize g i just enough to cover the new instances. But since {g j / (g j OE S-set and j≠i)} is the Sset of all past instances plus the new fictitious ones, g i can only become more general than one or several g j , and hence will be eliminated from the new S-set.

(ii) Case of the reduction of the G-set. In the same way, in order to eliminate an element g i of the G-set through the CE algorithm, it suffices to provide the negative instances covered by g i but not covered by the other elements of the G-set and by the S-set . As for (i) above, the CE algorithm would then specialize g i just enough to exclude the negative instances, and this would result in an element of the G-set that would be more specific than others, hence eliminated. P P ). If E4 is observed, then neither g1 nor g2 need to be modified. In fact {g1,g2} is the S-set of all positive instances that belong to the gray area. g3 will need to be generalized just enough to cover E4, and this will make it more general than g1 and g2, hence it will be eliminated from the S-set.

The following example will help to understand this.

Let us assume that we present positive and negative instances of scenes made of several objects each one described by a conjunction of attribute-values, and that we use three families of attributes, each one organized as a tree with increasing order of generality toward the root. In the following, we show how an element of the S-set could be removed by observing more instances.

Sizes

Let us suppose that we observe the following sequence of positive instances : The very same S-set would be obtained if the learning algorithm was the CE algorithm that after E1, E2 and E3 observed a new instance covered by g1 and by g2 and not by g3 such as :

-E4: + {(large yellow parallelogram) & (small black pentagon)}

Bias and order independence

What we have seen so far is that a local preference bias (forgetting hypotheses) can be made equivalent to another bias that would throw in chosen extra instances for the learner to observe. Thanks to this we can now tackle the main topic of this paper, namely what kind of local preference bias a learner can implement so as to stay order independent. Indeed, instead of studying a strategy of forgetting of hypotheses that depend on the current version space, and therefore on the past history, we now study addition of extra fictitious instances to the CE algorithm that is order independent. In other words, we are now in a position to specify conditions on the local preference bias by stating to which extra instances it should amount to.

We assume that the teacher has a set of n examples EX, and draws a sequence x of these according to her requirements.

Furthermore, we assume order independence, i.e. :

( Let S nb and G nb be respectively the S-set and the G-set that the CE algorithm would obtain from the collection of instances EX, and let S wb and G wb be respectively the S-set and the G-set of VS wb in (1) (the version space obtained on any sequence x of EX by the learner implementing the local preference bias).

Theorem 3 : For an incremental learner implementing a local preference bias to be order independent for EX leading to the version space C, it is necessary that the action of this bias be equivalent to the supply of :

-a set of fictitious positive instances such that they together with the real positive instances are covered and bounded by S wb , and, -a set of fictitious negative instances such that they together with the real negative ones are excluded and bounded by G wb .

Proof : Self-evident. P P

The next theorem is the application of theorem 3 to the case where VS wb = F n (EX,f) = VS nb , that is the case where the local preference bias leads to the null global preference bias, i.e. has no effect. Such a local bias can be seen as eliminating options judiciously since the result obtained after any sequence x of EX is the same as what the CE algorithm would get on EX. In this case S nb and S wb are one and the same as are G nb and G wb .

Theorem 4 : For an incremental learner implementing a local preference bias leading to the same result as an incremental learner without a local bias, it is necessary that the action of this bias be equivalent to the supply of :

-a set of positive instances such that each one is covered by elements of S nb , and , -a set of negative instances such that each one is covering all elements of G nb .

It is as if this local preference bias knew "in advance" the collection EX of instances, and eliminated elements of the S-set and of the G-set judiciously. This leads to the final theorem.

Theorem 5 : It is not possible for a local deterministic preference bias to lead to a null global preference bias for any arbitrary collection EX of examples.

Proof : Indeed, at each step, the action of the local bias can only depend on the past training instances and the current state. In order to lead to order independence it would have to be equivalent to an oracle that provides instances drawn from an array of the instance space that can be defined only with respect to all the training instances. This would mean that the learner, through its preference bias, was always perfectly informed in advance on the collection EX of examples held by the teacher. P P

Conclusion

In this research, we are interested in the following general question : given a collection of examples (or data in general), how can a teacher, a priori, best put them in sequence so that the learner, a deterministic incremental learning system that does not ask questions during learning, can acquire some target concept (or knowledge)?

This question, that corresponds to situations where the teacher does not have the choice of the examples and can not interpret the progress made by the student until the end of the learning period, leads to the study of incremental learning per se, independently of any particular system. The solution to this general interrogation could be of some use to several realistic settings where a teacher has an incremental learning system and a collection of data, or when data arrive sequentially but time allows to keep them in small buffers that can be ordered before being processed.

This framework is to be compared with the recent surge of interest for "teaching strategies" that allow to optimally teach a concept to a learner, thus providing lower bounds on learnability complexity [START_REF] Goldman | On the Complexity of Teaching[END_REF][START_REF] Salzberg | Learning with a helpful teacher[END_REF]. The difference with the former framework is that in one case the teacher can only play on the order of the sequence of inputs, whether in the other case, the teacher chooses the most informative ideal examples but does not look for the best order (there are some exceptions such as [START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF]).

This paper has outlined some first results concerning order sensitivity in supervised conceptual incremental learning.

The most important ones are :

(i) that order dependence is due non-optimality and/or to forgetting of possibilities corresponding to a local preference bias that heuristically selects the most promising hypotheses, (ii) that this bias can be seen as the result of additional instances given to the learner (i.e. prior knowledge built into the system),

(iii) that (ii) allows to replace the difficult problem of determining the action of the local bias along different sequences of instances by a problem of addition (which is commutative, i.e. order independent) of instances to an order independent learner, which leads to (iv) that there are strong contingencies for an incremental learner to be order independent on some collections of instances (either the corresponding prior knowledge is well-tailored to the future potential collections of inputs, or there is no prior knowledge, thus no reduction of storage and computational complexity).

In this study, we have given sufficient conditions only on the fictitious examples that should be provided by an oracle equivalent to a local preference bias. It would be nice to obtain necessary conditions that state which instances should necessarily be given by the oracle to get order independence. We are currently working on this question.

It should be clear that the problem of noisy data is of no concern to us here. We characterize through the version space what is known to the learner irrespective of the quality of the data. Noise would become an important issue if it was dependent on the ordering of the data (e.g. a sensor equipment that would degrade with time).

Issues for future research include : are these results extensible to more general learning situations (e.g. unsupervised) ? given a local preference bias, how to determine a good sequence ordering so as to best guide the system towards the target knowledge ?

Fig. 2 .

 2 Fig. 2. For n instances, there are n! possible training sequences. We look for conditions under which all sequences would result in the same state.

1 (

 1 (i) forgetting hypotheses amounts to overconstrain the search space (ii) extra instances to an order independent learning algorithm would result in constraining the search space (iii) if an incremental learner using a local bias b leading to forgetting of hypotheses) could be made equivalent to an order independent incremental learner using bias b 2 , (leading to the consideration of extra instances) then, finding conditions on the local bias b 1 would be the same as finding conditions on the bias b 2, only this time irrelevant of the training sequence (since b 2 is used by an order independent learner).

  g. the CE algorithm) Effect of new fictitious instances Action of the local bias

Fig. 3 .

 3 Fig.3. The equivalence needed to allow the study of conditions on the local bias. The effect of the local bias (forgetting of some element of the S-set or G-set) is the same as the effect of additional instances made available to an order independent algorithm such as the CE algorithm.

Fig. 4 .

 4 Fig. 4. In this figure, {g1,g2,g3} are assumed to be the S-set of the positive instances (E1,E2,E3). If E4 is observed, then

2 (

 2 red square) & (small white lozenge)} ∅ S-set-1 = {(large red square) & (small white lozenge)} -E2: + {(large red parallelogram) & (small blue equilateral)} ∅ S-set-2 = {(large red parallelogram) & (small col.-base polygon), (? R-Y-B polygon) & (? col.-base parallelogram)} -E3: + {(large yellow right) & (small blue rectangle)} ∅ S-set-3 = {(large R-Y-B polygon) & (small col.-base polygon), ® g 1 (? R-Y-B parallelogram) & (? col.-base polygon), ® g ? R-Y-B polygon) & (? col.-base parallelogram)} ® g 3 Let us assume that at this point the local bias for some reasons decides to discard g3 from the S-set. This would result in S-set-4 = {(large R-Y-B polygon) & (small col.-base polygon), (? R-Y-B parallelogram) & (? col.-base polygon)}.

  Which fictitious instances should the oracle corresponding to the local bias provide to the CE algorithm so that it get to the version space VS wb ? Answering this question amounts to give conditions on the local bias that would conduct a learner using it to VS wb irrespective of the training sequence followed. The answer is that fictitious positive instances should be drawn from the gray array, whereas fictitious negative instances should be drawn from the stripped array. The '+' and '-' figure the real instances that conduct the CE algorithm to the VS nb version space.

		--	G	nb	-	-	-
				G	wb
	Version
	spaces
	VS and VS nb wb
							S-set with bias : S wb
	+	+				+	+	(We use the notation F n LB to differentiate a learner +
	implementing a local bias (LB) from one that does not and only implements the CE algorithm noted F n (x ,f) in S-set with no bias : S nb +
	Fig. 5.						section 3. VS wb means the version space obtained with
							bias).
							Theorem 2 : An incremental learner implementing a
							local preference bias is order independent for a collection
							EX of instances if the action of this bias is equivalent for
							all possible sequences x of elements of EX to the supply
							of the same set of additional instances.
							Proof : It follows immediately from theorem 1. P P
							Now, we want to enlarge theorem 2, and give conditions
							upon the set of fictitious examples that the local bias
							acting as an oracle can provide to the learner so that the
							learner be order independent and reach VS wb possibly
							different fromVS nb .
							The CE algorithm without bias would reach the state
							VS nb (Version Space with no bias). If VS wb ≠ VS nb ,
							then it follows that extra instances should be provided to
							the CE algorithm so that it reaches VS wb . Theorem 3
	1) "x, F n LB (x,f) = VS wb , where						states which ones.
	VS wb is constant.
							n! sequences
							State after
	Initial state						learning without bias
							State after
							learning
							with bias

Acknowledgments : I thank all the members of the Equipe Inference et Apprentisssage, and particularly Yves Kodratoff, for the good humored and research conducive atmosphere so beneficial to intellectual work. Comments from the reviewers helped to make this paper clearer.