This paper considers the task of learning the preferences of users on a combinatorial set of alternatives, as it can be the case for example with online configurators. In many settings, what is available to the learner is a set of positive examples of alternatives that have been selected during past interactions. We propose to learn a model of the users' preferences that ranks previously chosen alternatives as high as possible. In this paper, we study the particular task of learning conditional lexicographic preferences. We present an algorithm to learn several classes of lexicographic preference trees, prove convergence properties of the algorithm, and experiment on both synthetic data and on a real-world bench in the domain of recommendation in interactive configuration.

Introduction

Modern, interactive decision support systems like recommender systems or configurators often handle a very large set of possible decisions/alternatives. The task of finding the alternatives that best suit their preferences can be challenging for users, but the system can guide them towards their optimal decision if it has some knowledge of their preferences. In many settings, the users' preferences are not known in advance. This is especially the case of systems that enable anonymous users to browse the catalogues: such systems must be able to acquire users' preferences.

That is why preference learning has emerged in the last decade as an important field; many interesting results are reported in e.g. the book edited by (Fürnkranz and Hüllermeier 2011), or the proceedings of recent Preference Learning or DA2PL (Decision Aid to Preference Learning) workshops. A general problem is: given a set of observed preferences, induce a model of preferences that best explains these observations, within a certain class of models. As input, it is often assumed that the observed preferences are given as a set of pairwise comparisons or partial rankings of alternatives [START_REF] Joachims | Optimizing search engines using clickthrough data[END_REF]; or can be elicitated online by asking the user to choose between two alternatives [START_REF] Viappiani | Preferencebased search using example-critiquing with suggestions[END_REF][START_REF] Koriche | Learning conditional preference networks with queries[END_REF].

But in some circumstances, such input is not available. This is especially the case of some anonymous on-line configurators, where little information is stored about interac-tions. However, e-commerce companies in general keep a history of past sales. Sold items have been chosen by users, so they must be ranked high in their preferences, but not necessarily in the very top; indeed a user may be led to eventually choose an item which is not the optimal one in her preference order: for instance because of the difficulty to grasp all possible options, a phenomenon called "mass confusion" [START_REF] Huffman | Variety for sale: Mass customization or mass confusion?[END_REF], because of the influence of an advertisement, or because her preferred item is unavailable. Yet, this list of highly ranked items does provide information about the users' preferences.

Our aim in this paper is to study how the users' preferences can be learnt from this sales history. Note that this is different from a classification problem where one would want to separate alternatives between, say, acceptable ones and not acceptable ones. In our problem, we want to rank the alternatives. If, for instance, the colour red appears more often in the sales history than the colour yellow, then we want to induce a model that ranks alternatives with the colour red higher than alternatives with the colour yellow -maybe in association with some other criteria.

Research on the representation and learning of preferences has brought forward several types of models. Numerical models, like linear ranking functions or additive utilities [START_REF] Joachims | Optimizing search engines using clickthrough data[END_REF][START_REF] Freund | An efficient boosting algorithm for combining preferences[END_REF][START_REF] Schiex | Valued constraint satisfaction problems: Hard and easy problems[END_REF][START_REF] Gonzales | GAI networks for utility elicitation[END_REF][START_REF] Braziunas | Local utility elicitation in GAI models[END_REF], are rich families of models, especially if one allows high-dimensional feature spaces. Research in Artificial Intelligence has also brought forward ordinal models, like CPnets [START_REF] Boutilier | CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF]) and several extensions or variants. Lexicographic preferences are another family of ordinal models. This kind of preference is based on the importance of the attributes: when comparing two outcomes, their values for the most important attribute are compared; if the two outcomes have different values for that attribute, then the one with the preferred value is deemed preferable to the other; otherwise one looks at the next most important attribute, and so on. This model can be extended by allowing the preferences on the values of an issue to depend on the values of more important ones. The relative importance of issues is no longer a linear order, but a "lexicographic preference" tree [START_REF] Fraser | Applications of preference trees[END_REF][START_REF] Fraser | Ordinal preference representations[END_REF]Brewka and others 2006;[START_REF] Wallace | Conditional lexicographic orders in constraint satisfaction problems[END_REF][START_REF] Booth | Learning conditionally lexicographic preference relations[END_REF].

Lexicographic preference trees are the model that we

Learning Lexicographic Preference Trees from Positive Examples

Hélène Fargier, Pierre-Franc ¸ois Gimenez, Jérôme Mengin IRIT, CNRS, University of Toulouse, 31000 Toulouse, France {fargier, pgimenez, mengin}@irit.fr choose in this paper for two main reasons. First, this is an ordinal model, which is sufficient to represent a ranking of alternatives. Furthermore, the restricted expressivity of the lexicographic preference trees makes them easier to learn while being generally an accurate representation of human behaviours [START_REF] Gigerenzer | Reasoning the fast and frugal way: Models of bounded rationality[END_REF]. Finally, one can quickly (in polytime) perform some interesting requests for recommendation, such as finding an optimal object or an optimal value for some attribute.

Learning lexicographic preference models have been studied by e.g. [START_REF] Schmitt | On the complexity of learning lexicographic strategies[END_REF][START_REF] Dombi | Learning lexicographic orders[END_REF][START_REF] Yaman | Democratic approximation of lexicographic preference models[END_REF], while [START_REF] Booth | Learning conditionally lexicographic preference relations[END_REF][START_REF] Bräuning | Learning conditional lexicographic preference trees[END_REF][START_REF] Bräuning | Lexicographic preferences for predictive modeling of human decision making: A new machine learning method with an application in accounting[END_REF][START_REF] Liu | Learning partial lexicographic preference trees over combinatorial domains[END_REF] studied learning of lexicographic preference trees. But all these works assume sets of pairwise comparisons as inputs, while we seek to learn from sales history. Preference learning is also different from learning a (lexicographic) rank-based classifier, as proposed by e.g. [START_REF] Flach | A simple lexicographic ranker and probability estimator[END_REF]: the latter task takes as input a set of positive and negative instances of a concept.

The paper is structured as follows. The next Section summarizes the lexicographic preference tree models and introduces the LP-tree classes we aim to learn. Section 3 details the probabilistic model on which our approach is based. The algorithmics is developed in Section 4. Section 5 describes experiments on synthetic data and Section 6 on a real-world dataset in the domain of recommendation in interactive configuration.

Lexicographic preference trees Notations

We consider a combinatorial domain over a set X of n discrete attributes, each attribute X having a finite domain X. An outcome is an instantiation of X . We use upper-case, bold letters to represent tuples of attributes; if U is such a tuple, then the set of assignments of U is denoted by U, and the corresponding lower-case letter will generally denote such an assignment: u ∈ U. A (complete) outcome is therefore a tuple o ∈ X∈X X; we denote by X the set of all of them. o[U] denotes the projection of o onto U: it is a partial outcome, i.e. an instantiation of U; we say that o extends o[U].

If U and V are disjoint tuples of attributes, UV will denote their concatenation -with similar notations for assignments: if u ∈ U and v ∈ V then uv ∈ UV. If U and V are not disjoint, we say that u and v are compatible if

u[U ∩ V] = v[U ∩ V].
A preference is modelled as a transitive binary relation over the domain of interest, X in our case. We consider in this paper that indifference is not allowed; the relation is said to be strict and we denote it ≻: o ≻ o ′ indicates that o is (strictly) preferred to o ′ . We denote by rank(≻, o) the rank of outcome o in the relation ≻: the "best" outcome has rank 1, the worst has rank |X |.

Lexicographic preference trees

In the formal model proposed by [START_REF] Booth | Learning conditionally lexicographic preference relations[END_REF]), a lexicographic preference tree, or LP-tree for short, is composed of two parts: a rooted tree indicating the relative importance of the attributes, and tables indicating how to compare outcomes that agree on some attributes. Each node of the importance tree is labelled with an attribute X ∈ X , and is either a leaf of the tree, or has one single, unlabelled outgoing edge, or has |X| outgoing edges, each one being labelled with one of these values. No attribute can appear twice in a branch. For a given node N , Anc(N ) denotes the set of attributes that label nodes above N . The values of attributes that are at a node above N with a labelled outgoing edge influence the preference at N . We denote by Inst(N ) the set of nodes above N with a labelled outgoing edge and inst(N ) the tuple of values of the labels between the root and N . Moreover, one conditional preference table CPT(N ) is associated to each node N of the tree: if X is the attribute that labels N , then the table contains (consistent) rules of the form v : >, where v is a (possibly partial) instantiation of the attributes in Anc(N ) Inst(N ), and > is a strict total order > over X. Every LP-tree L induces a (possibly partial) strict order over X , denoted ≻ L , as follows: for any node N labelled by X, consider a pair of complete outcomes

o and o ′ such that o[Inst(N )] = o ′ [Inst(N )] = inst(N ) and o[V] = o ′ [V] = v for some rule v : > in CPT(N ) with v ∈ V; N is said to decide the pair (o, o ′ ), and o ≻ L o ′ if and only if o[X] > o ′ [X].
A branch of a tree is complete iff all attributes appear in it; if all the branches of a tree are complete, then the tree itself is said to be complete. The preference relation induced by a LP-tree is total if and only if the tree is complete [START_REF] Bräuning | Learning conditional lexicographic preference trees[END_REF]. In this case, every outcome has a well-defined rank in the preference relation (and there is only one optimal outcome, ranked 1). [START_REF] Lang | Aggregating conditionally lexicographic preferences on multi-issue domains[END_REF]) have shown that it can be computed in polytime and that, for a given rank, finding an outcome with that rank can also be done in polytime. In the following, we will deal with complete trees and ranking only.

Linear LP-trees and k-LP-trees

In this paper, in addition to general LP-trees, we will be interested in a syntactic restriction called linear LP-tree and a extension called k-LP-tree.

A linear LP-tree is a LP-tree with a single branch and unconditional preference rules only, like the tree in Figure 1b. It is a strong expressive restriction: linear LP-trees represent the usual, unconditional lexicographic preference relations, and corresponds to LP-trees with unconditional local preferences and unconditional importance relation as defined by [START_REF] Booth | Learning conditionally lexicographic preference relations[END_REF]. [START_REF] Bräuning | Learning conditional lexicographic preference trees[END_REF][START_REF] Bräuning | Lexicographic preferences for predictive modeling of human decision making: A new machine learning method with an application in accounting[END_REF]) extend the expressiveness of LP-trees by allowing to label a node with a set of attributes, considered as a single highdimensional attribute: the rules in the conditional preference table of the node define orders on the Cartesian product of the domains of its attributes. Note that any (strict) preference relation can in principle be represented by such a LP-tree - possibly by labelling the root with a set that contains all attributes and an order over the full domain X . Generally, we restrict this expressivity by fixing the maximum number of attributes labelling a node. We denote k-LP-tree the trees whose nodes are labelled by at most k attributes. Figure 1c shows a 2-LP-tree whose preference relation cannot be expressed with a regular LP-tree.

A a > ā B a b > b C ā c > c C b : c > c b : c > c B b > b abc ≻ abc ≻ a bc ≻ a bc ≻ āb c ≻ ābc ≻ āb c ≻ ābc (a) A LP-tree. A a > ā B b > b C c > c abc ≻ abc ≻ a bc ≻ a bc ≻ ābc ≻ ābc ≻ āb c ≻ āb c (b) A linear LP-tree A a > ā BC bc > bc > bc > bc abc ≻ a bc ≻ a bc ≻ abc ≻ ābc ≻ āb c ≻ āb c ≻ ābc (c) A 2-LP-tree

Learning a preference relation from sales histories

The probabilistic model

As exposed in the introduction, the input of the learning process is a sales history, i.e. a multiset H ⊆ X . Its elements are positive examples, outcomes corresponding to products that may have been, for instance, configured by users of some configurator and bought. Each user has a preference relation ≻ among products, and is free to configure the products according to her preference. However, for some reasons like the influence of advertisements, she may end up with a product which is not her most preferred one.Yet, the higher an outcome is ranked in the user's preference, the greater the probability that she ends up with it. Formally, our idea is to consider that there is a ground, hidden preference relation ≻, and an associated probability distribution p ≻ over X which is decreasing and monotonic w.r.t.

≻, i.e. if o ≻ o ′ then p ≻(o) ≥ p ≻(o ′ ).
We consider that H is a set of outcomes that have been drawn according to the distribution p ≻. In this paper, we study the problem of learning a LP-tree L which explains H.

In practice, we can split the learning set H into several clusters and thus reduce the variability of the preferences inside each cluster. Even though each cluster includes the preference of multiple users, they have similar preferences, which can be represented with a unique ground preference relation, with p ≻ also accounting for the variations between the preferences of these users.

The ranking loss

In order to evaluate our learning algorithms, we must measure how good the learnt preference relation ≻ is w.r.t. the hidden preference relation ≻.

The two distances mostly used to compare preference relations are the Kendall distance and the Spearman distance.

These distances penalise as much a rank error on preferred items or on least preferred items.But for recommendation purposes, identifying the preference relation on the preferred items is more useful than identifying it on the least preferred ones.

In order to have a relevant measure, we introduce the notion of ranking loss, defined as the normalized difference between the expected ranks of the two relations according to the ground probability p ≻:

rloss p ≻ ( ≻, ≻) = 1 |X | E p ≻ [rank(≻, •)] -E p ≻ [rank( ≻, •)]
It is also equal to the mean of the rank differences for all items, weighted by their probabilities of appearance, and normalized by the maximum rank:

rloss p ≻ ( ≻, ≻) = 1 |X | o∈X p ≻(o)(rank(≻, o) -rank( ≻, o))
Proposition 1. Let ≻ and ≻ be two preference relations and p ≻ a probability distribution decreasing w.r.

+ . . . + r N p N ≤ r σ(1) p 1 + . . . + r σ(N )
p N for every permutation σ of {1, . . . , N }; if the sequences are strictly increasing / decreasing, the minimum is only attained when σ is the identity. In our case, the r i 's correspond to the ranks of the outcomes as ordered by ≻, the p i 's correspond to the probabilities and σ is the permutation that results in the ranks corresponding to ≻.

In our learning setting, the target preference is unknown, so we cannot measure the ranking loss of an induced preference. However, since the ranking loss of the induced preference is a sum of the ranks of the outcomes weighted by their probabilities of being drawn, we aim to minimize it by minimizing the normalized empirical mean rank of a set of positive training examples H drawn according to p ≻:

rank(≻, H) = 1 |X | 1 |H| o∈H rank(≻, o)
Note that this optimization problem does not directly depend on p ≻, only on the set of examples. Although p ≻ explains why H does not contain only one outcome -the optimal one according to a hidden target LP-tree -our algorithms below do not directly use it, only through the sample H.

A greedy learning algorithm

In this Section, we describe a greedy algorithm that learns a k-LP-tree and approximately minimizes this measure. The approach follows the generic scheme defined by [START_REF] Booth | Learning conditionally lexicographic preference relations[END_REF][START_REF] Bräuning | Learning conditional lexicographic preference trees[END_REF] to learn LP-trees from examples of pairwise comparisons, but we adapt it to learn from positive examples instead. Algorithm 1 builds the tree in a greedy way, from the root to the leaves, considering, at every step, the subset of the sales history compatible with the current partial instantiation. Given u ∈ U with U ⊆ X , let

H(u) = {o ∈ H | o[U] = u}
denote the set of outcomes in H that extend u. Then, at a given currently unlabelled node N (initially, the root node), line 3 considers the set H(inst(N )) of outcomes in the sales history that are compatible with the assignments made in the branch between the root and N . Function chooseAttributes returns the set of attributes and the CPT that will label the node. The tree is then expanded below N according to the set of labels returned by function generateLabels.

Algorithm 1: Learn a k-LP-tree from a sample H Input: X , a set of outcomes H over X Output: L the learnt k-LP-tree Algorithm LearnLPTree(X , H)

Choice of node labels

Given a node N , function chooseAttribute returns an attribute and a CPT so as to explain as well as possible the set of outcomes: we want to induce a LP-tree that ranks as high as possible the elements of H(n), where n = inst(N ).

Suppose first that we already know that N must be labelled with attribute set X. Our algorithm learns a CPT that consists of a single, unconditional preference rule.1 It is not difficult to see that the values of X should be ordered according to their number of occurrences in H(n) in order to minimize the empirical rank of H. Example 2. Consider two attributes A and B with respective domain {a, a ′ , a ′′ } and {b, b ′ }. Assume that H contains 45 outcomes distributed as follows:

ab ab ′ a ′ b a ′ b ′ a ′′ b a ′′ b ′ 10 9 8 7 6 5
Suppose that we have chosen attribute A to label the root of an induced LP-tree, then the associated CPT should contain the order a > a ′ > a ′′ over A, since a has 19 occurrences in H, a ′ has 15 occurrences, and a ′′ has 11 occurrences.

In order to decide which attribute, or set of attributes, should label N , consider two attributes X, Y / ∈ Anc(N ), and suppose that {X} is chosen for N . Then Y will appear below X in the induced LP-tree, and will be deemed less important. Let x * and y * be the values for X and Y respectively that have the most occurrences in H(n); then, according to the semantics of LP-trees, for every values x ′ ∈ X, x ′ = x * , and y ′ ∈ Y , y ′ = y * , every outcome that extends nx * y ′ will be considered to be preferred over every outcome that extends nx ′ y * . Since H is assumed to be representative of the preference relation, it should be the case that |H(nx * y ′ )| > |H(nx ′ y * )| for every pair (x ′ , y ′ ) ∈ (X \ {x * }) × (Y \ {y * }); thus the inequality should hold if we take averages as well:

y ′ ∈Y \{y * } |H(nx * y ′ )| |Y | -1 > x ′ ∈X\{x * } |H(x ′ y * )|

|X| -1

If the reverse inequality holds, then it cannot be the case that X is more important than Y , and X should not label N .

Example 3. Consider again the dataset of example 2:

|H(ab ′ )| |B| -1 = 9/1 > (8 + 6)/2 = |H(a ′ b)| + |H(a ′′ b)| |A| -1
therefore A is chosen for the root. The resulting LP-tree correctly orders the outcomes according to their numbers of occurrences in H.

We can generalize the approach to sets of attributes. Consider two sets of attributes X and Y that do not contain any attribute from Anc(N ) and that are not included into one another. Suppose that N is labelled with X, the associated CPT can order the instantiations of X according to their number of occurrences in H(n). Let U = X \ Y be the set of variables that are in X and not in Y and let V = Y \ X. Let x * (resp. y * ) be the most frequent instantiation of X (resp. Y) in H. Then for every x ′ ∈ X \ {x * }, v ′ , v ′′ ∈ V, every outcome that extends nx * v ′ will be preferred to every outcome that extends nx ′ v ′′ . In particular, if y * is the most frequent instantiation of Y in H, let v ′′ = y * [V], then for every instantiation u ′ of U which is not compatible with x * , if x ′ = u ′ • y * [X], it should be the case that outcomes that extend nx * v ′ are more frequent in H than those that extend nx ′ v ′′ = nu ′ y * . Hence it can be shown that we should have

v ′ ∈V\{y * [V]} |H(nx * v ′ )| |V| -1 > u ′ ∈U\{x * [U]} |H(nu ′ y * )| |U| -1 (1)
Note that, since we allow sets of attributes at the nodes of LP-trees, several LP-trees can represent the same relationthe extreme structure being a LP-tree with a single node that contains all the attributes and an order of the 2 n possible combinations of values. LP-tree nodes should not be larger than necessary: we now propose a way to recognise nodes that may be shrunk.

We do not want to build LP-trees with node sizes larger than necessary. We now propose a way to recognise when this may happen.

Suppose that X ⊃ Y and that for every

x, x ′ , x ′′ ∈ X such that |H(nx)| > |H(nx ′ )| > |H(nx ′′ )| and x[Y] = x ′′ [Y] we also have x ′ [Y] = x[Y] = x ′′ [Y]. Then we say that Y decomposes X at N (w.r.t. H).
The intuition is that Y decomposes X at N (w.r.t. H) if node N labelled with X could be replaced with a node labelled with Y just above a node labelled with X \ Y. Example 4. Consider again the attributes of example 2, and suppose that > orders {A, B} as follows:

ab > ab ′ > ab ′′ > a ′ b > a ′ b ′ > a ′ b ′′ Then ab > ab ′ > ab ′′ and ab[A] = ab ′′ [A] = a, and indeed ab ′′ [A] = ab[A] = ab ′ [A]; similarly, a ′ b > a ′ b ′ > a ′ b ′′ and a ′ b[A] = a ′ b ′′ [A] = a ′ , and indeed a ′ b ′′ [A] = a ′ b[A] = a ′ b ′ [A]
. This preference relation could be represented with a tree with a single node containing both variables, but also with a tree with A at the root and B below it.

Note that a k-LP-tree with decomposable nodes can always be transformed into a k-LP-tree without decomposable nodes, by "decomposing" these nodes.

Algorithm 2 enumerates the set G of all subsets of X -Anc(N ) with cardinality ≤ k for some fixed k, starting the search with some initial X ∈ G; every time it encounters a new Y ∈ G, it checks whether this Y proves that X cannot be the label of N . We say that Y disproves X if: • Y ⊃ X and X does not decompose Y; or • Y ⊂ X and Y decomposes X; or • Y ⊃ X and Y ⊂ X and the reverse of (1) holds.

The next result validates our method for choosing attributes, as it shows that, given enough examples, our algorithm correctly identifies a target LP-tree: Proposition 2. Consider a hidden k-LP-tree L with nondecomposable nodes only. Let H be a multiset of outcomes such that the empirical distribution p H , defined by p H (o) = |H(o)|/|H|, is strictly decreasing w.r.t. ≻ L. If Algorithm 1 uses Algorithm 2 for chooseAttributes and if generateLabels always returns X when called for attribute X, then the returned k-LP-tree exactly represents ≻ L.

Algorithm 2: Choose an attribute and its CPT Input: X , node N , a set of outcomes H over X , k the maximal number of attributes per label Output: A set of attributes X and a preference table

T Algorithm ChooseAttributes(X , N, H, k) 1 G ← the set of attributes sets of size at most k 2 n ← inst(N ) ; X ← any set of attributes of G 3 x * ← argmax x∈X |H(xn)| 4 for each Y ∈ G {X} do 5 y * ← argmax y∈Y |H(yn)| 6 if Y disproves X then X ← Y ; x * ← y * 7 > ← an order of X according to the counts {|H(xn)|} x∈X 8 return X, >
Proof. We will look for the root node label; the same reasoning applies to other nodes. Several k-LP-trees can usually correspond to a same relation. We will look for the label of the k-LP-tree L whose root node, labelled by X, is not decomposable.

Let Y i be a set of i attributes and Y j a set of j attributes different from Y i . Let i, j ∈ [1, k], i ≤ j and let compare Y i and Y j . There are two possibilities:

First case, suppose that Y i ⊂ Y j . We can use inequality (1) to determine which one is not the root.

Second case, suppose that Y i ⊂ Y j . We can't compare Y i and Y j with inequality (1). There are two possibilities : either

Y i decomposes Y j or not. If Y i decomposes Y j , then Y j is disproved because X is not decomposable. If Y i doesn't decompose Y j , then Y i is disproved. Indeed, if Y i were the root label, it would decompose Y j .
Ultimately, the correct, non-decomposable set of attributes X will eventually appear in the enumeration performed by chooseAttributes; it is the only one that disproves, and is not disproved by, all other candidates.

Managing the split

If function GenerateLabels always returns a blank label, then every node in the tree built by Algorithm 1 will have one child only, and the LP-tree produced will be a linear one. In this case, the algorithm returns a LP-tree that minimizes the empirical expected rank: Proposition 3. Let X be a set of binary attributes. Algorithm 1, when restricted to linear LP-trees, always returns the linear tree L that minimizes the empirical expected rank rank(≻ L , H).

Proof. Given some linear LP-tree L, let X(L, i) be the variable at depth i and x * (L, i) its preferred value. Then [START_REF] Lang | Aggregating conditionally lexicographic preferences on multi-issue domains[END_REF]. Thus:

rank(L, o) = 2 n - n i=1 2 n-i δ(L, i, o) where δ(L, i, o) = 1 if o[X(L, i)] = x * (L, i), 0 other- wise
argmin L 1 |H| o∈H rank(L, o) = argmin L o∈H rank(L, o) = argmin L o∈H 2 n - n i=1 2 n-i δ(L, i, o) = argmax L n i=1 2 n-i o∈H δ(L, i, o) = argmax L n i=1 2 n-i |H(x * (L, i))|
A linear LP-tree L * that maximises this sum must have, at every level i, x * (L * , i) = argmax x∈X |H(x)|. And the rearrangement inequality indicates that the variables must be ordered in L * in order of decreasing counts |H(x * (L, i))|, likewise Algorithm 1.

Learning unconditional lexicographic preferences may be too restrictive, but we do not want to learn fully conditional LP-trees, which would have a size exponential in the number of attributes. One way to learn conditional LP-trees without an exponential number of examples is to consider the number of examples that can be used to continue to induce the tree below a given node N : if there is a child N ′ of N such that |H(inst(N ′ ))| is below a fixed threshold τ , then we can decide not to split; if H(N ′ ) contains too few examples, it will not be useful anyway to induce the corresponding part of the LP-tree. We use a function GenerateLabels that implements this approach.

Using this threshold τ , the number of branches of the k-LP-tree learnt is limited because each branch corresponds to at least τ examples. So there are at most |H| τ branches and n|H| τ nodes. In Algorithm 2, at node N , one must count the occurrences in H(inst(N )) of every value of every set of at most k attributes; this can be done in O( n k d k |H|), where d is the maximum domain size of the attributes. decomposition check can be done in O(d k |H|). Furthermore, Algorithm 2 is called for each node. The overall time complexity of the learning algorithm is then O(n n k d 2k |H|2 /τ ).

Pruning

Algorithm 1 returns a tree L that approximately minimizes the empirical expected rank rank(≻ L , H) -within the class of acceptable trees, defined by the chosen threshold. This can lead to overfitting. A standard method to address this problem is to use a score function that trades off, for a given tree, a measure of how well the tree fits to the data with a measure of the complexity of the tree: small models tend to have better generalization properties. We define:

S φ (H, L) = -|H| • rank(≻ L , H) -|L| • φ(|H|)
where |L| denotes the size of the model, i.e. the number of its nodes, and φ is a penalty function. In our experiments, we choose φ(|H|) = c, for c a real constant. Once a LP-tree has been learnt, it can be pruned in order to improve its φ-score. This procedure is executed in a bottom-up fashion. For each non-leaf node N of L, we check whether this node has several outgoing edges. If so, each edge is redirected on the child of N associated to the preferred value of X. If the score is improved, we keep this pruned LP-tree; otherwise, we restore the original outgoing edges.

Experimental study on randomly generated data

The first experiments 2 are run on randomly generated, regular LP-trees to verify how well a hidden LP-tree can be rediscovered.

LP-tree generation

We randomly generated complete LP-trees (k = 1) with 10 attributes, each having 2 to 6 values (picked with uniform distribution). Each tree was generated in a top-down fashion, starting at the root: at each non-leaf node N , an attribute not already chosen above is picked at random, as well as an order of its values; with probability σ, where σ is a split coefficient, N has as many children as X has values; with probability 1 -σ, N has a single child.

Given such a randomly picked LP-tree L, we draw a fixed number of outcomes for H using a truncated geometric distribution: the probability of drawing an outcome o of rank r in L is p µ (r) = Kµ(1-µ) r-1 , where 1/µ is the mean of p µ .

In the experiments described below, we used a split coefficient σ = 0.2 and µ was chosen such that the expected value of the drawn rank is X /4: this value (which depends on the sizes that have been picked for the attributes) ensures that, if the root attribute has 2 values, then about 88% of the outcomes are in the preferred subtree.

Results

We compared the three variants of the algorithm -LP-Learning without pruning, LP-Learning with pruning and linear LP-Learning -in terms of ranking loss between the hidden and the learnt LP-trees, of size of the learnt tree, and of CPU time necessary to learn the tree (including the pruning when used). The splitting threshold was set to τ = 20 and the penalty function parameter c set equal to 1. Figure 2 shows the results 3 for different sample sizes. Each point represents the mean value on 750 hidden LP-trees.

Figure 2 shows a very good ranking loss. Notice that the ranking loss of linear LP-trees seems to reach a threshold: the hidden LP-trees are not linear, hence the relations they represent are hard to capture with linear structures.

The size of the induced trees increases with the sample size when no pruning is performed, but this size is significantly reduced by the pruning. This, together with the fact that the ranking loss of the pruned LP-trees is always better than that of the unpruned LP-trees, suggest an overfitting of the pre-pruning phase. The pruning reduces the size of the learnt LP-tree and enhances its precision, at the cost of a increase in CPU time -that remains sustainable though.

Application to value recommendation in product configuration

The experiments described in this Section are based on a real world problem, car configuration, and the experimental results are drawn for a real world data set, namely a sales history provided by Renault, the French car manufacturer. 4 The idea is to use the sales history to build one or several LPtrees, representing the preferences of the past users (the attributes in the LP-tree are the configuration variables). These trees can then be used to recommend values during future configurations: given a partial configuration (a partial instantiation u ∈ U), the LP-tree builds in polynomial time [START_REF] Lang | Aggregating conditionally lexicographic preferences on multi-issue domains[END_REF]

Dataset and clustering

We use a dataset that is a genuine sales history containing vehicles of the same type sold by Renault, the French car manufacturer. The vehicles of this data set are described by 48 attributes (mostly binary) and the history contains 27088 items. This sales history correspond to many customers and there is not enough data to learn the preference relation of each customer (an individual does not often buy a car). However, we can expect clusters of similar users which imply clusters of similar sold products that can be found in the sales history, using some classical k-means algorithm.We can then learn a LP-tree for each cluster, that should approximate the preferences of the customers that bought the items in that cluster.

When making a recommendation for a partial outcome u, we use the LP-tree of the cluster that is the nearest to u. This means that, during a configuration session, different LP-trees can be used at different depth in the configuration process. We need to adjust our definition of the empirical mean rank for several LP-trees {L i } and the orders they represent

{≻ i }: rank({≻ i }, H) = 1 |H| o∈H min i rank(≻ i , o)
4 Datasets available at http://www.irit.fr/ ∼ Helene.Fargier/ BR4CP/benches.html

Experiment protocol

We use a 10 folds cross-validation protocol. For each item o in the test set, we simulate a configuration session: we start with an empty item u; for each attribute X ∈ X , chosen in a random order, the recommender makes a recommendation x given u; we then instantiate X with the value o[X] that has been really chosen by the user; the process is repeated until all attributes have been instantiated. When all items in the test set have been processed, we compute the ratio of accepted recommendations, when the recommended value x matched the value o[X] that had been really chosen.

Results

The learning parameter τ is set equal to 20. The results for the learning of unpruned LP-trees are shown in Figure 3. First, we can remark a positive correlation between the precision rate and the normalised empirical mean rank. This suggests that our theoretical score, the mean rank, is indeed correlated with the experimental precision results.

The precision rate ranges from 78.2% (k = 1, 1 cluster) to 88.0% (k=3, 3 clusters); this high precision confirms the practical interest of our approach on real dataset.

The value of the normalised mean rank is in itself interesting, because a random LP-tree would have a normalised mean rank equal to 50% while the LP-trees learnt have a normalised mean rank between 1.2% (k = 1, 1 cluster) and 7 • 10 -7 % (k = 3, 3 clusters).

The precision is maximum for 3 and 4 clusters. While having several clusters increases the expressiveness, each cluster contains fewer examples; this explains the drop in precision with 5 clusters. With more attributes per node (the parameter k) the expressivity is increased, hence a positive impact on the precision.

The size of the model induced (which is the sum of the sizes of the LP-trees learnt for each cluster) seems globally independent of the number of clusters. The effect of the maximum number of attributes per node is stunning, from 2300 nodes with k = 1 to 90 nodes with k = 3. Pruning did not seem to improve results on this dataset.

Conclusion and perspectives

This paper constitutes a first approach to the general problem of learning an ordinal preference model from positive examples (and not from pairwise comparisons). We plan to experiment our approach on more real-world datasets. We also plan to study the sample complexity of our algorithms in a PAC setting since the experiments suggest that the ranking loss is inversely proportional to the sample size. Another lead is the analysis of the computational complexity of finding a LP-tree minimizing the empirical mean rank. In parallel, searching for a scalable and practical algorithm of exact optimization is worth investigating. We also wish to extend the approach to other ordinal preference models like CP-nets; or, more generally, an extension of this framework to partial orders.

Example 1 .

 1 An example of a LP-tree is depicted in Figure 1a. Let N be the leftmost leaf labelled C, we have Anc(N ) = {A, B} and inst(N ) = a.

Figure 1 :

 1 Figure 1: Different LP-trees and the preference relations they induce.

Figure 2 :

 2 Figure 2: Ranking loss (left), size of the learnt LP-tree (middle) and learning time (right) w.r.t. the sample size.

  the best (according to the preference relation it represents) outcome o compatible with u, (i.e. o[U] = u[U]). The system then recommends the value o[X], i.e. the value of X in the preferred completion of u.

Figure 3 :

 3 Figure 3: Precision (left), normalised expected rank (middle) and size (right) of learnt unpruned LP-trees w.r.t. the number of clusters and the maximum number of attributes per node k.

This is not restrictive, since function chooseAttribute that we describe below separates the values of an attribute into several branches as long as there are enough examples to induce meaningful orders over the domains of subsequent attributes.

The algorithms have been implemented in Java and have been run on a computer with 8 GB of RAM, a single core

3.4 GHz. Code available at https://github.com/PFGimenez/PhD.3 Because the cardinality of X can be huge, the ranking loss is estimated with a Monte-Carlo sampling with 100,000 samples.


Mamadou Lakhassane Cisse
email: mamadou.cisse@irit.fr

Student Research Abstract: Collaborative Processes Behavioral Modeling

lays in the fact that our approach can ease collaboration between the tasks enacted in the different interconnect systems. Those systems can also share the same outputs/inputs. In that case, it is necessary to have a mechanism allowing to know which system must produce which specific part of the output and synchronize it. This abstract is structured as followed. The next section deals with the related work followed by the approach and its uniqueness. Implementation section briefly presents our prototype. Finally, we make a conclusion and introduce perspectives on future works.

BACKGROUND AND RELATED WORK

Many approaches for representing collaborative approaches have been proposed. We summarize here some of them. In previous works, we addressed this topic by producing CMSPEM [START_REF] Kedji | Supporting collaborative development using process models: a Tooled Integration-focused Approach[END_REF], a SPEM extension adding concepts to support collaboration in software processes. In CMSPEM, Kedji et al. introduced concepts to represent the stakeholders of a project, the artifacts manipulated and tasks to execute. Collaboration dynamic aspects are formalized through a system of events. Vo et al. [START_REF] Vo | An Approach to Define and Apply Collaboration Process Patterns for Software Development[END_REF] have defined some collaborations patterns that are a way of defining, reusing and enacting collaborative software development processes. In [START_REF] Vo | An Approach to Define and Apply Collaboration Process Patterns for Software Development[END_REF], they define two collaborations pattern which serve as collaboration strategies: Duplicate in Sequence with Multiple Actors and Duplicate in Parallel with Multiple Actors and Merge. Yakindu [6] provides an editor for editing and simulating statecharts but is not process-centered.

APPROACH AND UNIQUENESS

To bring solution to the issues addressed in the first section we propose an approach which allows to represent collaborative software processes and also their execution. Our approach includes the Collaborative Processes Behavioral Metamodel (CPBM). CPBM defines collaborative tasks behavior via UML state-machines. CPBM is composed of three packages: CPBM_Core, CPBM_Behavior and CPBM_Execution. The latter encompasses necessary concepts to execute a software process. It introduces concepts about tasks being performed by multiple actors. The behaviors of CPBM runtime elements are represented by states as Instantiated, In Progress, Finished, …. ResourceElement represents any kind of executor. It can be a human or a tool. A single task instance (STI) is the main executable concept. It represents a work unit assignable to a single actor or a tool. The execution of an STI depends on the definition of some collaboration strategies [START_REF] Vo | An Approach to Define and Apply Collaboration Process Patterns for Software Development[END_REF].

PROBLEM AND MOTIVATION

Software engineering is a deeply collaborative activity. Therefore, having tasks executed by more than one actor is common. Such collaborative processes allow development teams to be more efficient. They need to be adequately represented in order to serve as a development model (for example in agile developments). For that, we need a dedicated language allowing to model different collaborative situations. So far, some attempts to describe a collaborative process via models have been made [START_REF] Hawryszkiewycz | A metamodel for modeling collaborative systems[END_REF] [START_REF] Cánovas Izquierdo | Collaboro: a collaborative (meta) modeling tool[END_REF]. However, they do not address the topic of tasks and roles organization within the development team neither concepts about the states of each task and action to perform to go from one state to another. In the other hand, SPEM [START_REF]OMG-SPEM 2.0[END_REF], which is the standard for software processes modeling, does not address the execution of any kind of task and still less tasks executed by several persons. Some approaches [START_REF] Briggs | Defining key concepts for collaboration engineering[END_REF] deal with tasks sequencing but they remain insufficient to precisely describe the reality of software development. They depict a "weak collaboration" in contrast to "strong collaboration" that is how the same task is shared between actors playing the same role. Besides modeling, the question of collaborative processes execution is also hardly addressed, especially to support strong collaboration. For this purpose, we need an executable language to clearly define collaborative situation semantics. To address these issues, we have proposed to manage collaborative processes by providing (1) a metamodel equipped with constructs to describe multi-instance tasks; (2) a set of collaborative patterns; (3) an operational semantics enabling execute a multi-instance task based on the selected pattern; (4) a process management system supporting flexibility by late binding so that users can choose, at enactment time, appropriate collaborative patterns corresponding to their organizational model. Considering system-of-systems, the underlying interest https://doi.org/10.1145/3167132.3167457

For this purpose, we can use workflow patterns-based strategies [START_REF] Van Der Aalst | Workflow patterns[END_REF] to set the execution sequencing depending on the availability of resources and/or inputs and tasks synchronization. Strategies are dynamically chosen depending on the problem faced at enactment time. As an example, we can choose parallel or sequential execution depending on whether all the actors are available at the same time or not. Another reason motivating strategy choice, can be the link between instances. They can be linked through the sharing of artifact. This situation is observable when a given instance must use the output of another instance. Finally, we have developed a prototype of a process engine for executing collaborative process.

IMPLEMENTATION

To handle the execution of collaborative processes, we have implemented a process engine Collaborative Process Engine. Mainly our prototype allows project teams to upload a process model formatted in xml and generate all the single task instances to be enacted. Given project development is collaborative, the project manager can, choose how many instances of every task he wishes and also the collaboration strategy for each. The strategies depend on the chosen workflow patterns among those we addressed in our approach section. To this date, our prototype is working with a set of patterns based on parallel or sequential execution. The parallel pattern means that the STIs are executed simultaneously followed by a merge of the different outputs. The sequential one means that every STI must wait for the precondition to be fulfilled. Those STIs are assigned to actors with inputs and expected outputs. The resource assignation will allow every stakeholder to know his own tasks and the sequencing between them. Finally, every actor will be able to graphically visualize the states of his tasks.

CONCLUSION AND FUTURE WORK

This paper addresses a real-life modeling issue. Collaboration processes behavioral modeling is indeed an interesting research domain and has to be more deeply exploited.

During collaboration modeling, many elements have to be taken into account such as how to represent collaboration processes, which collaboration strategy to use, how to follow the execution of every instance of tasks, among all. To answer those issues, our contribution has been to propose an approach to manage collaborative processes with a flexible PMS supporting unexpected situations at enactment time and collaborative tasks performed by several actors. Moreover, we have also implemented a Collaboration Process Engine (CPE) to support collaboration processes execution and tasks states visualization. This paper has potentially opened fruitful research directions. The use of collaboration strategies has to be extended in order to allow our CPE to support more complex strategies. The behavior of the runtime elements is expressed through UML State Machines. In addition, we plan on supporting dynamic addition, removal of instances of tasks during execution time. Also, events and actions to switch from a state to another (e.g. In Progress to Finished) have to be refined to take into account resources availability and work product instances states.

Figure 1 :

 1 Figure 1: CPBM_Execution package structure


Jean-Baptiste Lagrange

Philippe R Richard

In book: Mathematical Work in Educational Context, Springer

, 'artefact' and 'instrumental genesis', and the homonym notions in the theory of MWS. Following a brief overview of the Piagetian and Activity Theory perspectives which inspired Vérillon and Rabardel, we explore how didactic research on digital artefacts developed two viewpoints on the instrumental genesis: psychological and institutional. The idea of instrumental genesis in the theory of MWS is consistent with the concept of instrumented mediation by Vérillon and Rabardel, but is a more focused notion, since MWS include two additional geneses, semiotic and discursive. The theory of MWS moreover does not theorize about the mediation and as such, in a particular situation where a digital artefact is used, both viewpoints will be helpful. Regarding the poles of the instrumental genesis, we propose characterizing a digital artefact by the underlying data representations and algorithmic treatments, and constructions as data-result models of mathematical configurations, taking advantage of the representations and algorithms in the artefact.

Motivation

. This theory also puts forward the notions of artefact and instrumental genesis, furthermore including two other geneses: semiotic and discursive.

The central focus of this chapter is the relationship between notions introduced by Vérillon and Rabardel and the homonym notions in the theory of MWS. Previous presentations of the instrumental genesis in the theory of MWS [START_REF] Kuzniak | Mathematical Working Spaces in schooling: an introduction[END_REF] have briefly drawn on the work of Vérillon & Rabardel, but without taking into account how the two approaches derive from different research perspectives. The theory of MWS comes from didactic research in geometry, and the work of Vérillon and Rabardel from cognitive ergonomics, or in other words, psychology in the workplace. Arguably then, there is no reason why homonym notions should carry the same meaning. We consider that in mathematics education research, as in other scientific domains, it is important to work continuously on basic notions in order to specify the meanings we seek to convey in a specific theory, and to be cautious with regard to possible semantic bias when separate theories use a similar vocabulary.

This book is therefore an opportunity to accurately discuss instrumental genesis in the two theoretical perspectives and we expect this discussion to provide the firm foundations for further research. In order to retain specific focus, a first choice in this chapter is to consider digital artefacts rather than a broader category of artefacts.

The notion of digital artefact applies to a great diversity of devices ubiquitous in human activity and especially in cognition, some of which have been investigated in Chapter 8. 'Digital' fundamentally denotes a choice of data representation. For instance, to represent a color, a digital code enables the representation of a potentially great but finite number of colors, in contrast with an analog representation, which allows any combination. This choice of data representation has been adopted because it enables algorithmic treatment, i.e., treatment by an automatic device following given rules: in the example of colors, an algorithm triggers a display device to activate suitable light emitting diodes; other algorithms can be used for various processes on a colored picture… In this way, digital artefacts are characterized by data representation and algorithmic treatment. On the one hand, this characterization seems very simple with regard to the multiple roles digital technologies play in all domains and particularly in mathematics education, especially mediation and communication [START_REF] Clark-Wilson | Teaching with digital technology[END_REF]. On the other hand, a simple characterization by data representation and algorithms proved powerful enough to enable [START_REF] Turing | Computing machinery and intelligence[END_REF] to demonstrate the possibility for digital machines to perform processes which seemed restricted to human cognition and which became a reality more than a half century later. More modestly, we can assume that this simplicity will be helpful for an in-depth discussion about the notions of artefact and instrumental genesis.

Another choice made for this chapter is to return to founding texts: first the above-mentioned paper by [START_REF] Vérillon | Cognition and artefacts : A contribution to the study of thought in relation to instrumental activity[END_REF] and also Kuzniak's plenary address given at CERME 8 [START_REF] Kuzniak | Teaching and learning geometry and beyond… In B. Ubuz[END_REF] on Geometrical Working Spaces. The aim of this is to understand how the constructs of artefact and instrumental genesis were introduced respectively in cognitive ergonomics and in didactic research about geometry, along with their purpose. We then contrast the two frameworks, furthermore considering how they evolved after their introduction into the two perspectives. Of course, other works, such as those by Rabardel and colleagues in cognitive ergonomics, and by Kuzniak and colleagues in didactics, could be considered, but we prefer to concentrate on fundamental constructs rather than attempt to cover the whole range of aspects in the two frameworks.

Genesis and Schemes in Instrumented Activity

First of all, we consider the term "genesis" and its use in "mathematics education". [START_REF] Piaget | La genèse du nombre chez l'enfant[END_REF] use "genesis of the number" in their theoretical framework to denote the acquisition or construction of numerical knowledge in a developmental perspective (stages). At the same time, the notion of scheme, is one of the most important in the Piagetian conception of psychological activities. For Piaget, a scheme is the structure or organization of actions such that they transfer or generalize upon repetition of that action in similar or analogous circumstances. The genesis is thus that of schemes. Vérillon and Rabardel's approach is situated in a Piagetian perspective, drawing on the notions of schemes and genesis. But Vérillon and Rabardel also stress that classical approaches in the psychology of learning overlook situations of knowledge construction where the subject's action is not directed by an epistemic intention but is rather shaped by a practical and functional project. For Vérillon and Rabardel, this pragmatic dimension of learning situations is important, particularly in science teaching and in professional fields. Taking some distance from a pure Piagetian approach of cognition, they refer to an activity theory perspective (Leontiev 1976) considering that "development results from the progressive appropriation of (...) socially formed attainments". For them artefacts must be conceived as a component of such socially formed attainments: artefacts can be "all the objects of material culture to which an infant has access during his development". After the notion of artefact, the main construct of the instrumental approach for Vérillon and Rabardel is that of instrumented activity. This is illustrated in the SAI diagram (Fig. 9.1 below) where the "instrument" mediates the subject's relationship to the object of their activity. The authors stress that the "instrument" exists as an artefact, in the sense mentioned above, but it also has a psychological dimension due to its appropriation by the subject in the context of their instrumented activity. Vérillon and Rabardel describe processes of genesis in the context of the use of machines by students, a robot and a lathe. They observe that the geneses are not reduced to an adaptation (assimilation-accommodation in Piagetian terms) of the subject to the artefact. The student rather simultaneously constructs both an understanding of the functioning of the machine and a conception of the space. They conclude by stressing the consistency of the observations with the SAI diagram.

"The pupils' data acquisition strategies concerning the artefact, and their representative and operational activity during its operation (subject/instrument interaction) always turned out to be interdependent with their conceptions relative to the nature of the transforming process (instrument/object interaction), with the artefact mediating their action on the environment but also, in return, mediating their conceptualization of that environment (subject/object interaction mediated by the instrument)."

In short, Vérillon and Rabardel drew the concepts of scheme and genesis from Piaget and developed their notion of artefact from activity theory.

Genesis and Digital artefacts

In this subsection, we build upon Vérillon and Rabardel's observations in order to identify characteristics of geneses associated with digital artefacts. We contrast geneses of the lathe and of the robot. The lathe is used to cut a material into a shape of revolution. To create a desired shape, the material is put into rotation and the operator moves a cutting tool along two axes (respectively parallel and perpendicular to the axis of rotation) by way of visible screws. The robot is used to move objects in a 3D workspace. Externally, the robot is made of a mechanical device and a control box. The mechanical device is similar to a human arm: a succession of three mobile segments connect a fixed base to a clamp through four motorized articulations (joints). The control box is made of three cursors arranged like the three axes of an XYZ orthogonal system. Between the control box and the device there is a digital processor programmed in such a way that each position of the three cursors determines a position of the clamp in a Cartesian representation of the workspace. The consequence of this is that, in contrast with the lathe, there is no direct visible relationship between action on a cursor and movement of a part in the device. Above, we characterized digital artefacts by data representation and algorithmic treatment. According to this characterization, the robot is, for us, a digital artefact: the control box is represented as a triplet of coordinates and the robot is represented by the position of the clamp in the space. Internally, the algorithm implemented on the digital processor uses another representation of the robot made of an angular position for each of the four joints, consistent with the mechanical functioning of the robot: for a given triplet of coordinates, the algorithm computes values of the four angular positions in order to ensure adequate positioning of the clamp.

Investigating this through experiments with students, Vérillon and Rabardel observed, in the case of the lathe, a genesis of a geometrical relationship between the 2D profile created by activating the screws, and the resulting 3D shape of the rotating material. With the robot, the genesis is marked by a progressive awareness by the student of different representations (internal and external) of the 3D space. Vérillon and Rabardel distinguish five microgeneses:

(1) The cursors are considered to be associated with movements of the different parts of the arm (joints or segments).

(2) The relationships between the cursors and the parts of the machine vary depending on the zone where the arm is located. (3) In some zones, the cursors are also considered to be interacting with each other. (4) Pupils become aware of a homomorphism between the geometry of their actions and the geometry of movements of the clamp. (5) The relationship between the control space and the working space is no longer conceived in terms of movement but of positions. The action schemes, which were previously movement schemes, become schemes for defining positions inside these two spaces.

For us, the main purpose of the genesis is a better awareness of the algorithmic treatment between the control box and the mechanical part, as programmed by the designer. Paradoxically, because the mechanical part is open to observation, the internal representation (angular position of the four joints) is more visible that the external representation required by the user-interface, especially for students whose understanding of the 3D space has yet to be constructed. This is why students initially associate actions on cursors with changes in the angular positions of the joints. In this representation, action on cursors only works locally or when acting on three cursors together (stages 1 to 3). Students only gradually identify the fact that the position of the clamp is the object of control, implicitly becoming aware of the algorithm at work (microgenesis 4) before then understanding the representation of the robot in the 3D space chosen by the designer (microgenesis 5). In keeping with Vérillon and Rabardel's analysis, we see the robot as an instrument mediating the students' relationship with the 3D space, but we also stress the fact that the artefact becomes an instrument for a subject through their developing awareness of both the different representations and of the algorithm. Awareness is not in the details, but rather in a global understanding of the input and output, and of the nature of the transition between these: in the case of the robot, one must understand that some calculation on positions is made so as to pass from three coordinates to four angles 1 .

Psychological and institutional viewpoints on the instrumental genesis

At the end of the 1990s, researchers in mathematics didactics [START_REF] Lagrange | Technology and Mathematics Education: A Multidimensional Study of the Evolution of Research and Innovation[END_REF] stressed the need for a "multidimensional" approach to digital technologies in mathematics teaching. Conducting a review of a significant sample of research papers in this field Lagrange et al. highlighted the fact that a large majority of researchers adopted either an "epistemological and semiotic" perspective, centered on the influence of digital technologies on mathematical knowledge and practices and on the representations used, or a "cognitive" perspective, seeing technologies as opportunities to implement (socio)constructivist approaches. They proposed to break with unidimensional approaches and to consider additional dimensions more directly focused on an analysis of the specific characteristics of the artefacts used. They identified potential new viewpoints 2 characterized by the indicators of analyses they found in the papers they reviewed. The indicators of the psychological viewpoint were the analysis of the possibilities and constraints of digital artefacts for a given subject, and the evolution of schemes in instrumental geneses. The indicators of the institutional viewpoint were the analysis of the interaction of ICT with tasks and techniques in the culture of a school institution, and the consideration of the role of instrumented techniques in conceptualization of mathematics.

Compared to the majority of research studies on mathematics education about digital technologies currently published, this multidimensional approach has constituted a more nuanced and reflexive approach to the role digital artefacts can play, by showing their potentialities, but also the conditions necessary 1 It is tempting to refer here to the idea of a "black box" understanding of the algorithm, but it would be misleading since in the mediation, the box is never entirely black, but rather presented in varied "shades of gray". Lagrange et al refer to instrumental and institutional dimensions rather than psychological and institutional viewpoints. We adopt the latter formulation to avoid confusions with the use of the words instrumental and dimension in the theory of MWS.

for them to be implemented. This has made it possible to account for the role of "mathematical" digital artefacts (numerical and formal calculation, dynamic geometry, spreadsheets, ad hoc programming, etc.) for students' as well as teachers' conceptualizations, to show the complexity of the phenomena at hand and to develop didactic engineering which takes this complexity into account. The psychological viewpoint derives directly from Vérillon and Rabardel's pioneering work reported above. The link between this work and the institutional viewpoint is less obvious, since it uses the notion of praxeology and associated concepts (tasks, techniques, theorizations) from the Anthropological Theory of Didactics (ATD). Nevertheless, Vérillon and Rabardel stress that "(the) instrumental relation is the subject of real occultation, producing what Y. [START_REF] Chevallard | Dimension instrumentale, dimension sémiotique de l'activité mathématique[END_REF], in mathematics, called a phenomenon of hypostasiation, through which the artefact is seen as existing in a sort of ideality independently from the concrete practices from which it emerges or which constitute it." Indeed, according to Chevallard, knowledge itself is the object of hypostasiation when teaching/learning is reduced to visiting a scientific content as a "monument" overlooking its "raisons d'être", that is to say the questions and cultural environments (institutions in ATD) which motivated people to develop this content. The idea of praxeology is the theoretical tool helping to position a knowledge content in the development of human culture. Similarly, artefacts, especially digital artefacts, need not be seen as the result of some serendipitous invention, but rather the product of culturally (i.e. institutionally) situated activity. Thus, instruments exist through the praxeologies in which they are set into operation for a given type of task, and the instrumented techniques are not given with the artefact, but rather develop in a culture and in institutional practices. This is the case of the robot: the design with four joints results from mechanical constraints, but for tasks like moving objects under the control of a human operator, moving each joint individually would be a tedious technique. A technique based on a homomorphism between the control space and the workspace is more efficient and is therefore adopted in a workplace praxeology. The theoretical level of the praxeology consists in the 3D representation of the space and in the idea of an algorithm able to control the joints from this representation. Similarly, mathematical instruments exist through the techniques in which they are implemented for a given type of task:

"Taking techniques into account is, along with instrumentation, one of the keys to thinking about the integration of technology in teaching (...) The interest of introducing an instrument can be seen in the development by the students of new techniques that are integrated into renewed praxeologies [START_REF] Lagrange | L'Integration d'Instruments Informatiques dans l'Enseignement: Une Approche par les Techniques (The Integration of technological Instruments in teaching/learning: An Approach from the techniques)[END_REF]."

The psychological and institutional viewpoints are arguably complementary and should not be confused. This contrasts with the argument of [START_REF] Drijvers | Embodied instrumentation: combining different views on using digital technology in mathematics education[END_REF], who writes: "The observable parts of an instrumentation scheme, the concrete interactions between user and artefact, are called instrumented techniques (...) As such, an instrumentation scheme consists of one or more observable instrumented techniques...".

It is important to carefully distinguish between the subjective dimension of the scheme (How is it formed by the subject? What mental operations are at work?) and the institutional and social dimension of the techniques (In which praxeologies do they fit? In what conditions do these praxeologies develop?) Schemes and techniques each have their own identity, as do, fortunately, subjects and institutions!

Work, geneses and artefacts in the theory of MWS

We now examine the basic concepts of the theory of MWS in light of the psychological and institutional viewpoints set out above. The first concept is that of mathematical work. Vérillon and Rabardel's approach is primarily concerned with professional and technical domains, as shown by the empirical studies (lathe, robot) cited in the article, and is based on the idea of activity rather than work. Nevertheless, turning an object on a lathe, activating a robot for a given task, are not free activities carried out with the aim of developing abstract geometrical or computational knowledge, but rather activities aiming at the transformation of material entities, and developing in social contexts. In parallel, by emphasizing work and by considering mathematics both as a science and as a field of activity, the theory of MWS breaks with the idea of mathematics as an abstract field disconnected from social practices: like the lathe or robot operator, the mathematician works with instruments that have a psychological and an institutional value. Regarding geneses and artefacts, as in the previous sections, we refer to a text which was a precursor to the theory of MWS. In his plenary address to CERME 8, [START_REF] Kuzniak | Teaching and learning geometry and beyond… In B. Ubuz[END_REF] introduces Geometrical Working Spaces (GWS) and the geneses: "In our approach, both levels, cognitive and epistemological, need to be articulated in order to ensure a coherent and complete geometric work. This process supposes some transformations (...) Here, in order to insist on the developmental process involved in the constitution of GWS, the notion of genesis is used. For us, a genesis involves not only the origin but also the development of a process."

The instrumental genesis, on which we particularly focus here, connects artefacts, a pole of the epistemological plane, and construction, the corresponding pole in the cognitive plane. Three remarks seem important:

-On the MWS classical diagram and at a first glance, the geneses seem objective in character, since they connect components of the geometrical activity in its purely mathematical dimension to observable processes: the instrumental genesis with a drawing square, for example, would be simply the use of the square to draw right angles in a given construction. Nevertheless, the words used -"developmental", "transforms", "provides... status", "gives a meaning"all suggest that transformations take place within the subject(s) or institutions which use the artefacts. Further texts (Chapter 1 of this book) have explained how two views of the instrumental genesis can be considered. The bottom-up view describes the actions by which the user appropriates the various techniques of use related to the artefact. The top-down view begins from the user's intended accomplishment, to his or her adequate choice of the artefact with which to perform the required actions. As such, the instrumental genesis changes the way the user acts and thinks, and, in return, also transforms the mathematical knowledge. This is compatible with Vérillon and Rabardel's idea of instrumental mediation (SAI diagram fig. 9.1), but it is more upstream, because it does not theorize about dimensions relating to the subject (acting and thinking) and to institutions (instrumented techniques, impact on praxeologies).

-Vérillon and Rabardel, referring to Vygotsky's psychological instruments, explain in their conclusion that their remarks "are not only valid for the activities instrumented by material artefacts (...) the instrumental dimension also concerns the mastery of language, writing and numbers which may be considered as technologies intended to communicate, to represent and conserve information and to calculate."

It is somehow paradoxical to see Vérillon and Rabardel studying psychological processes related to technical artefacts which they recognize regretfully to be overlooked by psychology and then, in their conclusion, to enlarge the scope to geneses of every kind of artefact. There is arguably therefore a risk that the idea of instrumental genesis loses some of its potential by being absorbed into an overly large class of cognitive processes. In contrast, the epistemological plane of the MWS distinguishes three poles, and each can be considered as artefacts in the sense of potential psychological instruments. Consequently, the figurative and semiotic genesis proposed by Kuzniak is an instrumental genesis in accordance with the work of Vérillon and Rabardel. The same observation applies to the discursive genesis of proof, definitions and properties of the corpus of reference being artefacts instrumenting reasoning. It seems that the theory of MWS brings clarification, helping us to consider the specificity of instrumental genesis, among others. We also note that Vérillon and Rabardel distinguish between material and immaterial artefacts, only to then discard this distinction with regard to instrumentation. We can further observe that in the epistemological plane of the MWS, each pole may have a possible material basis, not only artefacts. This is obvious for signs in semiotic systems. As for the corpus of reference, Richard, Venant and Gagnon (2018) provide evidence that this is often "materialized" in varied ways for different types of proofs.

- [START_REF] Kuzniak | Teaching and learning geometry and beyond… In B. Ubuz[END_REF] explains in detail the semiotic genesis and the discursive genesis. In contrast, instrumental genesis seems to be a blind spot. Consider the example given at the end of the text. The students (10 th grade) are faced with a task of constructing a triangle with the same angles as a given triangle. The teacher assumes that the variety of triangles obtained will enable them to infer the proportionality between the dimensions of the initial triangle and those of the triangle constructed. He aims to institutionalize proportionality without demonstration, but he nevertheless wants the students to be aware that it is an unproven conjecture, the imprecision of measurements enabling this awareness. Kuzniak illustrates these expectations in a first diagram (Fig. 9.2). Although the students are required to complete a construction task, the diagram mentions no instrumental genesis. The artefacts and the construction are connected to the semiotic (figurative) genesis (in blue): they are simply "serving" the visualization, and their connection is not discussed. The construction is also supposed to "trigger" a discursive conjecture-proof genesis (in red). The second diagram (Fig. 9.3) illustrates what actually happens in the classroom after the students have not achieved the construction task or have failed to engage in a process of conjecture: the teacher presents a dynamic geometry (DG) figure on a computer, makes the software calculate the ratios between the measurements of the sides for a variety of configurations, and then asks the students to observe the invariance of the ratios. The dynamic geometry figure enables the students to pass "directly" from the visualization to an empirical "proof" based on the observation of the invariance for several configurations. The precision of the measurements using the software and the plurality of the configurations make the students think that they have carried out a "true demonstration", which was not the teacher's aim. Again, the diagram mentions no instrumental genesis3 .

Reflecting on key issues about the instrumental genesis in MWS

After situating the instrumental genesis among basic constructs of the theory of MWS, we look more closely in this section at this notion from both the "psychological" and "institutional" viewpoints. We start by investigating the two poles of the genesis.

Construction

It is useful to revisit the definition of a construction proposed by [START_REF] Duval | Why to teach geometry[END_REF]: "(a) construction (...) can work like a model in that the actions on the representative and the observed results are related to the mathematical objects which are represented." Construction is thus the elaboration of data-result models of mathematical configurations. By configuration, we mean that the construction models a set of interrelated objects, rather than one or more isolated objects. Models here are not the models of some reality studied in Chapter 11, but they rather share a common operationality and then proximity with simulation. This fits well with traditional geometrical figures that model the properties of a set of geometrical objects. Digital geometry software adds dynamicity, enhancing the data-result (simulation) character of the model. In algebra, a digital calculator helps to make a formula work as a model of a function by providing computed values for given inputs. Interpreting Vérillon and Rabardel's robot study in the theory of MWS, we must understand that construction is what the students do when they operate the robot across the five microgenesis. Like a figure in geometry is just one of all possible realizations of a configuration, an action on the cursors is just one of all possible actions. However, it is known that drawing a figure helps to think of all possible realizations, i.e. it is considered a model of the configuration. Similarly, students' actions on cursors are a way to test an implicit model of the robot and to make this model evolve. This sheds light on one characteristic of the instrumental genesis: it is not a passive application of techniques but rather an active process of selecting actions in order to observe relevant results. Resulting from this active process, the instrumental genesis can foster cognition and contribute to the "work on techniques" [START_REF] Chevallard | Organiser l'etude 1. Structures et fonctions[END_REF].

Digital artefacts, data representation and algorithms

Since Kuzniak's 2013 plenary, the notion of 'artefact' has been vastly investigated.

"In the theory of MWS, mathematical artefacts will generally be associated with material objects to avoid confusion with other components of the epistemological plane. But these objects will be intimately linked to rules and techniques of construction or calculation (Euclidean division, "classical" constructions using a ruler and compass, etc.). These techniques are based on algorithms, the validation and theoretical status of which are no longer problematic (This book 1.4.2.1)."

To delve deeper in a reflection on digital artefacts, we return to didactical work about computer algebra systems (CAS). For the sake of simplicity and consistency with the idea of construction as a data-result model, we restrict the focus here to symbolic calculators like Maple or Derive conceived as input/output systems. While these systems presuppose a material basis, this aspect is not decisive. Certainly, the uses of CAS can be different according to whether they are carried out on a calculator or on a computer, but the stakes for the conceptualizations go beyond this material dimension. Computer algebra can be characterized as a set of internal representations of algebraic entities and algorithms, "transparent" to the user, in principle [START_REF] Elbaz-Vincent | A CAS as an assistant to reasoned instrumentation[END_REF]. It also offers a user interface with a symbolism which is similar to usual mathematical symbolism. In mathematical work, the algorithms can be seen as playing an analogous role to routinized paper-and-pencil techniques mentioned in the citation above. However, there is a difference concerning one fundamental issue: controlling (pilotage in French) a mathematical calculation, without which applying algorithms is useless. In paper-and-pencil techniques, initiation to calculation algorithms is generally carried out in coordination with the learning of this subtle control, whereas with formal calculation it is precisely this control of CAS by the student user that is at stake [START_REF] Lagrange | L'Integration d'Instruments Informatiques dans l'Enseignement: Une Approche par les Techniques (The Integration of technological Instruments in teaching/learning: An Approach from the techniques)[END_REF]. How can CAS be used for a given task? What awareness of the underlying representation and algorithm does this imply? What mastery of the semiotic system specific to the software is necessary 4 ? How can one control a mathematical calculation as-sisted by CAS? On what set of reference knowledge can this control be based? Questions linked to CAS-instrumented techniques have been investigated theoretically and empirically [START_REF] Artigue | Learning mathematics in a CAS environment: The genesis of a reflection about instrumentation and the dialectics between technical and conceptualwork[END_REF][START_REF] Lagrange | Transposing computer tools from the mathematical sciences into Teaching[END_REF] but this seems to have little effect, and in countries which have not ruled out the use of CAS for educational purposes, it is very deceptive [START_REF] Jankvist | What happens when CAS-procedures are objectified? -the case of "solve" and "desolve[END_REF]. The theory of MWS has the potential to make us reconsider and "untangle" these questions by differentiating between what is properly instrumental -here the implemented representations and algorithms and the awareness of these by the user, and what belongs to other geneses, semiotic and discursive. The instrumental genesis (in the sense of the MWS) is not isolated, it is rather articulated with other geneses in the working space where the artefact is used (see Chapters 1 and 2).

We note that the idea of digital artefacts based on data representation and algorithm is not present in the research by Vérillon and Rabardel. In the present chapter, we see a difference between the lathe and the robot, because action on the lathe is not mediated via a computerized interface: the genesis is different in the sense that the link between an action on a screw and a movement of the tool is not problematic. Indeed, the real problem for a beginner is the effect of a movement on the shape cut into the material; this effect cannot be thought of as a process of computation on representations. In mathematics education, there is a tendency to overlook the representational and algorithmic character of a digital artefact. Common approaches favor the vision of a digital artefact integrating the mathematical field for which it was designed without modification. For instance, publications for teachers present dynamic geometry (DG) as "embedding" elementary Euclidean geometry. They neglect the representations and algorithms underpinning DG and overlook notions which do not exist in classical geometry, such as the notions of free object and dependent object. These publications suggest that the practice of dynamic geometry could immediately be integrated into a usual working space, presenting extended possibilities of action without transforming its nature. This is a double illusion. On the one hand, the extended possibilities are in no way spontaneous in the absence of an awareness of the data representation and algorithms at work. On the other hand, by depriving the students of a working space which enables this awareness and association with the semiotic and discursive aspects, teaching also deprives students of opportunities to learn. In a suitable working space, attention to the insion it is not evaluated to 1, even if a is declared real. In contrast it is simplified to 1, The reason is that evaluation and simplification are different algorithms, The first one performs a standard syntactic treatment in order to get a canonical expression and the second applies heuristically a set of transformations based on mathematical rules and properties, aiming at decreasing the complexity of the expression.

As for symbolism, it is very often only partially similar to the usual mathematical symbolism; the reason for this is that canonical expressions have to be compatible with internal representations and algorithms. For example, summations, limits and integrals must be entered with functional symbolism. In addition to this, output rarely directly conforms to what a student expects, especially at a secondary level: an example of this is x strumental genesis of computer algebra could help students to explicitly learn how to control a calculation. Taking advantage of the functional aspect specific to dynamic geometry (identifying dependencies in a dynamic construction) could support effective approaches to geometry or functions.

Mathematics education is increasingly confronted with diverse and complex artefacts, among which some based on artificial intelligence algorithms: proof support software, virtual or augmented reality, data mining, machine learning, deep learning, large-scale data analysis, etc. (Richard, Vélez Melón & Van Vaerenbergh, in preparation). Designers are working hard to develop increasingly "accessible" and "transparent" interfaces. Even CAS and DG software have been augmented with new features and their analysis is not reducible to that of the preceding paragraph. However, we hypothesize that a similar analysis is possible: the simplicity and efficiency of the theoretical constructs (one working space, three geneses...) of MWS should make it possible to both guard against presupposed epistemic effects of the use of a given software and to ask the right questions: what are the underlying representations and algorithms, what are the new semiotic systems that the student will be confronted with and the coordination between objects which they presuppose, what theoretical frame of reference can be used to guide them, what praxeologies can develop, how can these aspects and the associated geneses be articulated in a (personal, suitable, reference) MWS?

Schemes and techniques in the instrumental genesis of MWS

We noted above that the instrumental genesis in MWS is, in a certain way, upstream of the approach of Vérillon and Rabardel and then further analyzed from a psychological viewpoint (development of schemes allowing the use of an artefact), as well as from an institutional viewpoint (development of instrumented techniques and associated praxeologies) in a given MWS. In this subsection, we illustrate how the two viewpoints can shed light on the example (9.4) proposed by [START_REF] Kuzniak | Teaching and learning geometry and beyond… In B. Ubuz[END_REF].

In this example, students have not integrated the use of an angle transfer artefact (protractor or tracing paper), or this use does not lead them to the side measurements on which visualization and reasoning would operate. Instrumental genesis is nonexistent, no scheme is developed and no technique emerges. The teacher's use of DG in the second phase denotes the widespread conception that we mentioned above, assuming that simply making students look at DG figures and software calculated ratios will trigger a conceptual reflection. Focusing on digital artefacts, we propose an alternative situation assuming that students have the use of DG software (not only the teacher). A strategy often proposed in DG research studies is to let students start by performing a soft construction 5 .

Starting from a triangle ABC, a segment DE and a free point F, they have to guess one or several positions of F, such that DEF has the same shape as ABC (i.e. corresponding angles have the same value). It can be expected that students will mark angles in the two triangles and drag F to a suitable position. Students could then be advised that their construction is not robust in the sense that it does not resist dragging of one end of segment DE. The ability of DG to provide automatic proof (oracle) can also be a reason to reject this construction, because, in spite of visible angle equalities, the oracle will declare that it is not proven (Richard, Venant and Gagnon 2018). Students could then be asked to harden the construction. The assumption is that they will think of transporting angles, but transporting is incommodious in dynamic geometry. Students will then have to infer the equality of ratios from various configurations and transpose the procedure for constructing a triangle into DG, knowing its dimensions.

The path that students are expected to follow includes movements along the instrumental genesis and between the construction pole and the two other cognitive poles (figure).

-A first movement connects the dragging capability in the DG artefact and the soft construction. -A second movement involving the construction and the proving poles of the cognitive plane consists in becoming aware of the limits of this construction. -In a third movement, the visualizing and construction poles are involved in order to explore relations between distances. -The fourth movement connects different capabilities of DG, especially an intersection of circles and a hard construction. From a psychological viewpoint, the instrumental genesis in the first movement consists in appropriating (i.e. build schemes of) the use of a free point F and the dragging gesture to find an adequate position. In the second movement, understanding why the construction does not resist and/or why the oracle denies proof implies some awareness of DG (algorithmic) functioning. In the third movement, students would have to appropriate DG capabilities related to measures, and in the fourth movement, capabilities related to circles and intersection.

From an institutional viewpoint, soft and hard constructions are two instrumented techniques for the same task, using different capabilities of DG and belonging to different praxeologies: one based on visualization and approximation, and the second on geometrical properties. It can be expected that students will not easily abandon a soft construction "that works" to adopt a more intellectually demanding hard construction. It is therefore essential that the teacher involves students in a discussion on techniques, stressing the interest of adopting robust procedures consistent with digital software. This discussion is central to the second movement 6 .

Conclusion

We conclude with a summary of the main points of our contribution. Vérillon and Rabardel's instrumental genesis is one of schemes anchored in a Piagetian perspective. Their analysis implies a fine-grained identification of microgeneses specific to the type of artefact used. Focusing on digital artefacts, we observed how schemes develop through the subject's emerging awareness of the representations and algorithms which underpin the artefact. Consistent with Chevallard's (YEAR) ATD and Leontev's (YEAR) activity theory, Vérillon & Rabardel also insist on breaking with an idealistic view of artefacts, consider-6 [START_REF] Lagrange | Teacher's emergent goals in spreadsheet based lessons: Analysing the complexity of technology integration[END_REF] present a similar case illustrating the importance of a discussion on techniques. Students in two classes (11 th grade, not scientific majors) have to implement a recurrence relationship on a spreadsheet from a real-life situation. The teachers in both classes expect students to implement the relationship by way of a formula copied down along a column. The goal is that they understand the interest of an algebraic formula as a model of the real-life situation. Contrary to this expectation, students easily compute the requested values by hand, enter these values into the cells, and decline to enter any formula. Using colors and borders, they are happy to use the spreadsheet as a tool to display data. Both teachers are disconcerted. One teacher tries ineffectively to instruct students to make a formula. The other teacher, better prepared for situations where technology is used, starts an improvised whole-class discussion on techniques for calculating values of series, stressing the respective values of by hand and automatic calculation. Students become aware of the actual potentialities of the spreadsheet as a calculation tool and of the power of the algebraic symbolism.

ing them as emerging from socially situated practices and constitutive of these. Building on the theoretical elaboration of Vérillon and Rabardel, and of Chevallard, didactic research introduced two complementary viewpoints or angles from which to consider the instrumental genesis of digital artefacts: the psychological viewpoint deals with the formation of schemes and associated mental operations; the institutional viewpoint focuses on instrumented techniques, the praxeologies in which they fit and the social conditions in which they develop.

As for the instrumental genesis in the theory of MWS, it is first an objective entity, linking tangible artefacts and observable processes of construction. Because it also comprises a conceptual dimension transforming both the user and the mathematical knowledge, it is compatible with Vérillon and Rabardel's idea of instrumental mediation. However, instrumental genesis in the theory of MWS is based on different choices compared to Vérillon and Rabardel's notion: on the one hand, it is part of a theorization of mathematical work in educational settings not limited to the use of instruments, and on the other hand, it does not theorize about the transformation occurring in the instrumental genesis. The two complementary viewpoints, psychological and institutional (one providing insight into the cognitive work, the other into how techniques are understood and implemented), derived from the works of Vérillon and Rabardel, and of Chevallard, can therefore help to "flesh out" an analysis of the instrumental genesis in a particular MWS, on the condition of being cautious not to merge or confuse ideas drawn from different theoretical perspectives.

Looking at the poles of the instrumental genesis in MWS, we see construction as data-result models of mathematical configurations. In this modelling perspective, the instrumental genesis is not a passive application of techniques, but rather an active process of selecting actions and data in order to observe relevant results. Regarding artefacts, we noted that Vérillon and Rabardel enlarged the scope, and we stressed the risk that the idea of instrumental genesis loose some of its potential by being "absorbed" into a too large class of cognitive processes. In contrast, the epistemological plane of MWS distinguishes three poles, and each of these can be considered as artefacts potentially integrated by the subject through a specific genesis. This clarification is very helpful, yet implies that characterization of artefacts in the instrumental genesis of MWS is not straightforward. Indeed, it requires us to precisely identify capabilities which intervene in the modelling process, beyond their material aspect. Regarding digital artefacts, these capabilities derive from the representations and algorithms implemented. We have given an example demonstrating how it is possible to propose an efficient strategy for using a digital artefact, how an a priori analysis in the MWS framework gives a central role to the instrumental genesis and how this analysis can be enriched by considering the genesis from two complementary viewpoints: psychological and institutional.

Our focus on digital artefacts was productive in the sense that it helped to question notions in the theory of MWS, and also because it enabled us to better characterize these artefacts: a contribution to didactic research on digital environments. As mentioned in this chapter, digital artefacts are ubiquitous, yet their educational use is not often straightforward in real-life teaching contexts, meaning that both empirical and theoretical research is more necessary than ever. We illustrated how a simple characterization of these artefacts, combined with the potential of the theory of MWS helps us to gain a more precise perception of situations of use. Our focus is certainly also a limitation with regard to other artefacts such as the mathematical machines (Bartolini-Bussi & Maschietto, 2006) mentioned in Chapter 8. We nevertheless believe that the ideas presented in this chapter will be useful to analyze other types of artefacts in a MWS framework.

Fig. 9

 9 Fig. 9.1. The SAI diagram, taken from Vérillon and Rabardel (1995).

  2

Fig

  Fig. 9.2

Fig

  Fig. 9.3

Fig 9. 4

 4 Fig 9.4 The path students are expected to follow in four movements. 5 Leung (2014) presents in more depth how "soft constructions" can be productively implemented in relation to conservation properties.

The fact that the instrumental genesis is overlooked in this example actually reflects the teacher's lack of attention to the role of instruments in designing and conducting the situation. Subsection 9.5.3 herein will come back to this issue and discuss an alternative design.

Concerning the necessary awareness of underlying algorithms, consider the example in the work of[START_REF] Elbaz-Vincent | A CAS as an assistant to reasoned instrumentation[END_REF] of the treatment of the expression cos(a)²+sin(a)² by CAS. This expres-

when the user expects x √ x .