Julien Audiffren

Hachem Kadri

Equivalence of Learning Algorithms

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Equivalence is a fundamental concept that defines a relationship between two objects and allows the inference of properties of one object from the properties of the other. In the field of machine learning, several theoretical concepts have been proposed in order to estimate the accuracy of learning algorithms, among which complexity of the hypothesis set [START_REF] Vapnik | The necessary and sufficient conditions for consistency in the empirical risk minimization method[END_REF][START_REF] Evgeniou | Regularization networks and support vector machines[END_REF][START_REF] Bartlett | Rademacher and gaussian complexities: Risk bounds and structural results[END_REF], stability [START_REF] Bousquet | Stability and generalization[END_REF] and robustness [START_REF] Xu | Robustness and generalization[END_REF], but little can be said concerning how these learning properties can be moved from one learning algorithm to another one. This raises the question of how equivalence between two learning algorithms might be defined such that some learning characteristics could be transferred between them.

When are two learning algorithms equivalent? More precisely, given {Z, λ i , A i }, i = 1, 2, where Z is a training set, A i is a learning algorithm that constructs to every training set Z a decision function f i Z,λ and λ i is a tuning parameter that balances the trade-off between fitness of f i Z,λ to the data Z and smoothness of f i Z,λ , under what conditions is A 1 equivalent to A 2 ? Many learning algorithms can be formulated as an optimization problem. In this case, it is often thought that two learning algorithms are equivalent if their associated optimization problems are. One purpose of this paper is to point out that showing that two optimization problems are equivalent is not adequate evidence that the underlying learning algorithms are exchangeable with each other or even share some learning properties. Indeed, restricting the analysis of equivalence between learning algorithms to that of their optimization problems tends to omit details and ignore steps forming the whole learning mechanism such as the selection of the tuning parameter λ or the change of the learning set Z. The notion of equivalence between learning algorithms needs thus to be clearly defined.

The concept of algorithmic equivalence in machine learning has never been properly defined; the degree of difference between an optimization problem and its associated learning algorithm is not defined anywhere, nor has an exact definition. In this work, we rigorously define two notions of equivalence for learning algorithms and show how to use these notions to transfer stability property from a learning algorithm to another. Algorithmic stability is of particular interest since it provides a sufficient condition for a learning algorithm to be consistent and generalizing [START_REF] Shalev-Shwartz | Learnability and stability in the general learning setting[END_REF]. The first notion of equivalence we define, called weak-equivalence, is related in some way to the equivalence between the associated minimization problems. By weak equivalence, we would like to emphasize here that this equivalence holds only when the algorithms are evaluated on a given training set Z. This matches in some manner the equivalence between the optimization problems since the objective function to minimize is evaluated only for the set Z of training examples (x i , y i ) n i=1 , which is fixed in advance. The second notion is stronger, in the sense that two learning algorithms are strongly equivalent when their equivalence does not depend on the training set Z.

As a case study, we consider regularized kernel methods which are learning algorithms with a regularization over a reproducing kernel Hilbert Space (RKHS) of functions. In particular, we study the regularized least squares regression problem when the RKHS regularization is raised to the power of m [START_REF] Mendelson | Regularization in kernel learning[END_REF][START_REF] Steinwart | Optimal rates for regularized least squares regression[END_REF], where m is a variable real exponent, and design an efficient algorithm for computing the solution, called M-RLSR (m-power regularized least squares regression). Using our algorithmic equivalence concept, we analyze the relation between M-RLSR and kernel ridge regression (KRR) algorithms.

In this paper, we make the following contributions: 1) we formalize the concept of equivalence between two learning algorithms and define two notions of algorithmic equivalence, namely, weak and strong equivalence (Section 3). 2) We show that the weak equivalence is not sufficient to allow the transfer of learning properties, such as stability, while strong equivalence is. Moreover, we provide sufficient assumptions under which the transfer of stability still holds even in the weak equivalence case (Section 4). 3) As a case study, we consider the equivalence between KRR and M-RLSR. More precisely, we derive a semi-analytic solution to the M-RLSR optimization problem, we design an efficient algorithm for computing it, and we show that M-RLSR and KRR algorithms are weakly and not strongly equivalent (Section 5).

Notations and Backround

In the following, X will denote the input space, Y the output space,

Z n = (X × Y) n , Z = ∪ n≥1 Z n , Z ∈ Z a training set, H ⊂ Y X the
Banach space of hypotheses (for instance a separable reproducing kernel Hilbert space (RKHS)). Here and throughout the paper we use both notations |Z| and #(Z) to denote the cardinal of the set Z.

Following the work of Bousquet and Elisseeff [START_REF] Bousquet | Stability and generalization[END_REF], a learning algorithm is defined as a mapping that takes a learning set made of input-output pairs and produces a function f that relates inputs to the corresponding outputs. For a large class of learning algorithms, the function f is obtained by solving an optimization problem. So before talking about algorithmic equivalence, it is helpful to discuss equivalence between optimization problems. A mathematical optimization problem [START_REF] Boyd | Convex Optimization[END_REF] has the form

minimize l(f ) subject to l i (f ) ≤ b i , i = 1, . . . , q.
Here f is the optimization variable of the problem, the function l : H → R is the objective function, the functions l i are the (inequality) constraint functions, and the constants b i are the limits for the constraints. A function f * is called optimal, or solution of the problem, if it has the smallest objective value among all functions that satisfy the constraints. We consider here only strictly convex objective and constraint functions, so that the minimization problem have an unique solution and f * is well defined. Two optimization problems are equivalent if both provide the same optimal solution.

The machine learning literature contains studies showing equivalence between learning algorithm (see, e.g., [START_REF] Girosi | An equivalence between sparse approximation and support vector machines[END_REF][START_REF] Rudin | Margin-based ranking and an equivalence between AdaBoost and RankBoost[END_REF][START_REF] Jaggi | An equivalence between the lasso and support vector machines[END_REF]); however, most of them have focused only on the equivalence that may occur between the associated optimization problems. In this sense, an equivalence between two optimization problems offers a way to relate the associated learning algorithms. However, this is not sufficient to decide whether the optimization equivalence allows to transfer theoretical properties from one learning algorithm to the other. A work that have indirectly supported this view is that of Rifkin [START_REF] Rifkin | Everything Old is New Again[END_REF], who studied learning algorithms related to Thikonov and Ivanov regularized optimization. In [START_REF] Rifkin | Everything Old is New Again[END_REF]Chapter 5], it was shown that even though these optimization problems are equivalent, i.e., they give the same optimal solution, the associated learning algorithms have not the same stability properties. From this point of view, equivalence between minimization problems does not imply that the underlying algorithms share the same learning characteristics. This consideration is closely related to our goal of identifying when properties of a learning algorithm can be moved from one to another. The concept of algorithmic equivalence emerges in response to this question.

Weak and Strong Equivalence Between Learning Algorithms

In this section, we provide a rigorous definition of the concept of equivalence between machine learning algorithms. The idea here is to extend the notion of equivalence of optimization problems to learning algorithms. We first start by recalling the definition of a learning algorithm as given by Bousquet and Elisseeff [START_REF] Bousquet | Stability and generalization[END_REF], and for simplicity we restrict ourselves to learning algorithms associated to strictly convex optimization problems.

Definition 3.1 (Learning Algorithm). A learning algorithm A is a function A : Z → H which maps learning set Z onto a function A(Z), such that

A(Z) = arg min g∈H R(Z, g), (1)
where R(Z, •) is a strictly convex objective function.

Since we consider only strictly convex objective functions, the minimization problem has an unique solution and (1) is well defined. From this definition, the following definition of equivalence between algorithm naturally follows. In other words, let A (resp. B) be a learning algorithm associated to the optimization problem R (resp. S), then A and B are equivalent on Z if and only if the optimal solution of R(Z, •) is the optimal solution of S(Z, •). It is important to point out that the optimal solutions of R and S are computed for a set Z, and even though they are equal on Z, there is no guarantee that this remains true if Z varies. This means that the two algorithms A and B provide the same output with the set Z, but this may not be necessarily the case with another set Z ′ .

In this paper, we pay special attention to regularized learning algorithms. These algorithms depend on a regularization parameter that plays a crucial role in controlling the trade-off between overfitting and underfitting. It is important to note that many widely used regularized learning algorithms are families of learning algorithms. Indeed, each value of the regularization parameter λ defines a different minimization problem. As an example, we consider Kernel ridge regression [START_REF] Saunders | Ridge regression learning algorithm in dual variables[END_REF] which is defined as follows arg min

f ∈H 1 |Z| (x,y)∈Z (y -f (x)) 2 + λ f 2 H . (2)
In the following, we denote by A(•) a regularized learning algorithm indexed by a regularization parameter in R * + . In other words, ∀λ ∈ R * + , A(•)

. = A(λ)(•) = A(λ,
•) defines a learning algorithm as in definition 3.1. Note that all the results we will state can be naturally extended to a larger class of family of learning algorithms.

Equivalence of regularized learning algorithms. We now define the notion of weak equivalence between regularized learning algorithms as an extension of definition 3.2. To illustrate this equivalence, we provide some basic examples in this section and an in-depth case study in Section 5.

∃Φ A→B : R * + × Z → R * + such that 1. ∀Z ∈ Z, Φ A→B (•, Z) is a bijection from R * + into R * + , 2. ∀Z ⊂ Z, ∀λ ∈ R * + , A(λ) and B(Φ A→B (λ, Z)) are equivalent on Z.
In the particular case where Φ A→B does not depend on Z, this assertion becomes much stronger than the weak equivalence, and will be referred as strong equivalence.

if it exists Φ A→B , a bijection from R * + into R * + such that A(•) = B(Φ A→B (•)) where the equality is among functions from R * + into H Z .
This notion of weak equivalence is frequently encountered in machine learning algorithms. For instance, it naturally occurs when using Lagrangian duality and when transiting from Ivanov's to Thikonov's method [START_REF] Rifkin | Everything Old is New Again[END_REF]Chapter 5]. Note that weak and strong equivalence between two learning algorithms have some immediate implications for interpreting their regularization paths (see the supplementary material for more details). The natural question which now arises is whether by knowing some learning properties of A and the weak equivalence of A and B it is possible to deduce learning properties for B. This question is studied in the next section.

Consequences of Equivalence Between Learning Algorithms

We now study the consequences of the algorithmic equivalences defined in the previous section. In particular we investigate wether these notions of equivalence allow the transfer of learning properties from one learning algorithm to another. We first begin by the following proposition which presents a main of the weak equivalence. Proposition 4.1 Let A(λ) and B(λ) two weakly equivalent regularized learning algorithms. Then

∀Z ⊂ X × Y, inf λ∈R A(λ)(Z) = inf λ∈R B(λ)(Z).
Proof : This Proposition directly follows from Definition 3.3. Proposition 4.1 means that the optimal solutions given by two weakly equivalent (regularized) learning algorithms are the same. However, without further assumptions, weak equivalence is of little consequence to the transfer of learning properties from one to the other, such as stability, consistency or generalization bounds. Indeed, these properties are defined for a varying training set either by altering it (such as in stability) or by making it increasingly large (such as in consistency). To illustrate this idea, we will address in particular the question whether weakly equivalence allows or not the transfer of stability.

Transfer of stability. In the following we choose to focus on uniform stability which is an important property of a learning rule that allows to get bounds on the generalization performance of learning algorithms. Following [START_REF] Bousquet | Stability and generalization[END_REF], the uniform stability of a regularized learning algorithm is defined as follows.

Notation. ℓ : Y × Y → R + denotes a loss function on Y, and ∀Z ∈ Z, ∀1 ≤ i ≤ |Z|, Z i denotes the set Z minus its i-th element. + → R + be such that ∀λ > 0, lim n→∞ β(n, λ) = 0. A regularized learning algorithms A is said to be β-uniformly stable with respect to ℓ if

∀λ ∈ R * + , ∀Z ∈ Z ∀1 ≤ i ≤ n ∀(x, y) ∈ X × Y |ℓ(y, A(λ, Z)) -ℓ(y, A(λ, Z i ))| ≤ β(|Z|, λ).
We now give an example to show that weak equivalence is not a sufficient condition for the transfer of uniform stability.

Example: Let A(•) denotes the KRR as defined by (2) and B(•) denotes a modified KRR where the regularization term is λ/|Z| instead of λ. A and B are weakly equivalent with Φ A→B (λ, Z) = λ|Z|. Under some widely used hypotheses on the kernel and on the output random variable Y [START_REF] Bousquet | Stability and generalization[END_REF], A is known to be β uniformly stable with β(n, λ) = C 1 (1 + C 2 / √ λ)/nλ where C 1 and C 2 are constants, and n is the size of the training set Z (see e.g. [START_REF] Bousquet | Stability and generalization[END_REF] or [START_REF] Audiffren | Stability of multi task kernel regression algorithms[END_REF] for more details). Similarly, it is easy to see that B satisfies the same property but with β(n, λ)

= C 1 (1 + C 2 /
√ λn)/λ, which no longer tends to ∞ as n increases. Indeed, the regularization term in the learning algorithm B(λ) decreases as |Z| increases, and this leads to a decrease of the stability of the learning algorithm.

It is important to note that if A and B are strongly equivalent, then unlike in the weak equivalence case, many properties of B are transferred to A. The following Lemma illustrates this idea in the case of stability.

Lemma 4.3 If A and B are strongly equivalent and if B is β(•, •) uniformly stable, then A is β(•, Φ A→B (•)) uniformly stable. Proof : Let (x, y) ∈ X × Y, Z ∈ Z and λ ∈ R * + . It is easy to see that |ℓ(y, A(λ,Z)(x))-ℓ y, A(λ,Z i )(x) | = |ℓ(y, B(Φ A→B (λ), Z)(x))-ℓ y, B(Φ A→B (λ), Z i )(x) |, ≤ β(|Z|, Φ A→B (λ)).
We have shown that, contrarily to strong equivalence, weak equivalence is not sufficient to ensure the transfer of learning properties such as uniform stability.

In the following, we introduce two additional assumptions which are a sufficient condition for the transfer of the uniform stability under the weak equivalence. In order to clearly express these assumptions, we first introduce a metric on training set, that is to say a metric on unordered sequences of different lengths. To the best of our knowledge, this is a new metric, which allows to easily express learning properties such as stability. We will refer to this metric as the generalized Hamming metric1 (see e.g. [START_REF] Ash | Information theory[END_REF] for more details on the usual Hamming metric).

Definition 4.4 Let n > 0, Z 1 = z 1 1 , . . . , z 1 n and Z 2 = z 2 1 , . . . , z 2 n . Let Σ(n)
denotes the set of all the permutations of {1, . . . , n} and H denotes the usual Hamming metric on sequences. ∀σ ∈ Σ(n), we denote by Z 1 σ the sequence of n elements, whose i-th element is

z 1 σ (i). We define • G n : (X × Y) n × (X × Y) n → R + , such that G n (Z 1 , Z 2 ) = min σ∈Σ(n) H(Z 1 σ , Z 2 ), • H : Z × Z → R + , such that H(Z 1 , Z 2 ) =      #(Z 1 ) -#(Z 2 ) + min Z⊂Z1,#(Z)=#(Z2) G #(Z2) (Z, Z 2 ) if #(Z 1 ) ≥ #(Z 2 ), #(Z 2 ) -#(Z 1 ) + min Z⊂Z2,#(Z)=#(Z1) G #(Z1) (Z, Z 1 ) otherwise. (3)
The idea of this metric is to consider the number of deletion (i.e. removing an element), insertion (adding an element) and change (changing the value of one element) that allows to move from one training set to another (permutations of two elements among a training set are free). The following proposition proves that H is indeed a metric on Z. Proof : see the supplementary material.

Remark 4.6

The generalized Hamming metric can be used to reformulate the notion of stability. For instance, A is β uniformly stable if and only if A is β lipschitz with respect to the metric H.

With the help of the metric H, we now introduce two assumptions on the regularity of the functions Φ A→B and A.

Assumption 1 Φ A→B (λ, •) is C Lipschitz decreasing with respect to H, i.e. ∃c > 0 and C : N → R, decreasing, lim n→∞ C(n) = 0, such that 1. ∀λ ∈ R * + , ∀Z 1 , Z 2 ∈ Z, |Φ A→B (λ, Z 1 ) -Φ A→B (λ, Z 2 )| ≤ cH(Z 1 , Z 2 ), 2. ∀λ ∈ R * + , ∀ ∈ Z, ∀1 ≤ i ≤ |Z|, |Φ A→B (λ, Z) -Φ A→B (λ, Z i )| ≤ C(|Z|).
Assumption 2 Let γ > 0. A is γ Lipschitz with respect to its first variable, i.e. ∀Z ∈ Z,

∀λ 1 , λ 2 ∈ R * + , A(λ 1 )(Z) -A(λ 2 )(Z) H ≤ γ|λ 1 -λ 2 |.
These two assumptions are a sufficient condition to the transfer of stability in the weak equivalence case, as shown in the following Proposition. Proposition 4.7 Let A and B be two weakly equivalent regularized learning algorithms satisfying Assumptions 1 and 2. Moreover, let β be as in Definition 4.2 and locally Lipschitz with respect to its second variable. Suppose that ∃κ

> 0 such that ∀x ∈ X , ∀f ∈ H, f (x) Y ≤ κ f H . Then: If B is β uniformly stable, then A is β ′ uniformly stable with ∀λ ∈ R * + , β ′ (•, λ) = O(β(•, λ) + C(•)). Proof : Let (x, y) ∈ X × Y, Z ∈ Z, n = |Z| and λ ∈ R * + . First note that since ℓ is σ-admissible, by using λ ′ = Φ A→B (λ, Z) and λ ′′ = Φ A→B (λ, Z i ), |ℓ (y, A(λ, Z)(x)) -ℓ y, A(λ, Z i )(x) | = |ℓ (y, B(λ ′ , Z)(x)) -ℓ y, B(λ ′′ , Z i )(x) |, ≤ |ℓ (y, B(λ ′ , Z)(x)) -ℓ y, B(λ ′ , Z i )(x) | + |ℓ y, B(λ ′ , Z i )(x) -ℓ y, B(λ ′′ , Z i )(x) |, ≤ β(n, λ ′ ) + σκ B(λ ′ , Z i ) -B(λ ′′ , Z i ) H , ≤ β(n) + σκγ|λ ′ -λ ′′ |, ≤ β(n, λ) + δC(n) + σκγC(n),
where in the last line we used the fact that β is locally Lipschitz with respect to λ, hence ∃δ(λ, |λ -

λ ′ |) > 0 such that β(n, λ ′ ) ≤ β(n, λ) + δ|λ -λ ′ |. Now, since Φ A→B is C-Lipschitz decreasing, |λ ′ -λ| → n→∞ 0, hence the conclusion.
Remark 4.8 Proposition 4.7 can be extended to some non σ-admissible loss such as the the square loss by using the same ideas as in [START_REF] Bousquet | Stability and generalization[END_REF] and [START_REF] Audiffren | Stability of multi task kernel regression algorithms[END_REF].

The next section is devoted to present an in-depth case study of weak equivalence. It introduces a new regularized learning algorithm, M-RLSR, and studies the equivalence between KRR and M-RLSR.

Case Study: M-RLSR

Notation. In this section, m > 0 is a real number, X a Hilbert space, Y = R, H ⊂ R X a separable reproducing kernel Hilbert space (RKHS), and k : X × X → R its positive definite kernel. For all set of n elements of X × R, we denote by Z = {(x 1 , y 1 ), .., (x n , y n )} the training set, and by K the

Y = Q ⊤ Y ; y i = Y i , ∀1 ≤ i ≤ n 4.
Root-finding: Find the root C 0 of the function F defined in [START_REF] Girosi | An equivalence between sparse approximation and support vector machines[END_REF] 5. Solution: Compute α from ( 9) and reconstruct the weights

(α i ) 1≤i≤n = 2y i 2d i + λmnC 0 and α = Qα
Gram matrix associated to k for Z with (K Z ) i,j = k(x i , x j ). Finally, let Y = (y 1 , ..., y n ) ⊤ be the output vector.

The algorithm we investigate here combines a least squares regression with an RKHS regularization term raised to the power of m. Formally, we would like to solve the following optimization problem:

f Z = arg min f ∈H 1 n n i=1 (y i -f (x i )) 2 + λ f m H , (4)
where m is a suitable chosen exponent. Note that the classical kernel ridge regression (KRR) algorithm [START_REF] Saunders | Ridge regression learning algorithm in dual variables[END_REF] is recovered for m = 2. This problem has been studied from a theoretical point of view (see [START_REF] Mendelson | Regularization in kernel learning[END_REF][START_REF] Steinwart | Optimal rates for regularized least squares regression[END_REF]), and in this section we propose a practical way to solve it. The problem ( 8) is well posed for m > 1. We now introduce a novel m-power RLS regression algorithm, generalizing the kernel ridge regression algorithm to an arbitrary regularization exponent.

M-RLSR Algorithm

It is worth recalling that the minimization problem (8) with m = 2 becomes a standard kernel ridge regression, which has an explicit analytic solution. In the same spirit, the main idea of our algorithm is to derive analytically from (8) a reduced one-dimensional problem on which we apply a root-finding algorithm. By applying the generalized Representer Theorem from [START_REF] Dinuzzo | The representer theorem for Hilbert spaces: a necessary and sufficient condition[END_REF], we obtain that the solution of (8) can be written as f Z = n i=1 α i k(., x i ), with α i ∈ R. The following theorem gives an efficient way to compute the vector α = (α 1 , ..., α n ) ⊤ .

Theorem 1 Let Q an orthonormal matrix and D a diagonal matrix such that K = QDQ ⊤ . Let y ′ i be the coordinates of Q T Y , (d i ) 1≤i≤n the elements of the diagonal of D, C 0 ∈ R + and m > 1.

Then the vector α = Qα ′ with

α ′ i = 2y ′ i 2d i + λmnC 0 , ∀1 ≤ i ≤ n , (5)
is the solution of (8) if and only if C 0 is the root of the function F : R + → R defined by

F (C) = n i=1 4d i y ′2 i (2d i + λmnC) 2 m/2-1 -C. (6)
Proof : The proof of Theorem 2 can be found in the supplementary material.

It is important to note that for m > 1, F has a unique root C 0 and that since F is a function from R to R, computing C 0 using a root-finding algorithm, e.g. Newton's method, is a fast and accurate procedure. Our algorithm uses these results to provide an efficient solution to regularized least squares regression with a variable regularization exponent m (see Algorithm 1).

Equivalence Between M-RLSR and KRR

Here we will show that M-RLSR and KRR are only weakly equivalent but not strongly equivalent. The idea is that, when m > 1, the objective function of the M-RLSR optimization problem ( 8) is strictly convex, and then by Lagrangian duality it is equivalent to its unconstrained version. The weak equivalence is proved in the following proposition.

Proposition 5.1 ∀m > 1, ∀Z ∈ Z, ∃F Z,m : R + → R + , bijective, such that ∀λ > 0, M-RLSR with regularization parameter λ and KRR with regularization parameter λ 2 = F Z,m (λ) are weakly equivalent. Moreover,

Φ A→B (λ, Z) = mλ 2 C 0 (Z, m, λ),
where C 0 (Z, m, λ) is the unique root of the function F defined in [START_REF] Girosi | An equivalence between sparse approximation and support vector machines[END_REF].

Proof : For m > 1, the equivalence between constrained and unconstrained strictly convex optimization problems [18, Appendix A] implies that ∃Γ m,Z,λ > 0 such that the minimization problem defined by ( 8) on Z it is equivalent to the following constrained problem:

arg min f ∈H 1 |Z| (x,y)∈Z (y -f (x)) 2 , s.t. f m H ≤ Γ m,Z,λ .
The constrain is equivalent to

f 2 H ≤ Γ 2/m
m,Z,λ , thus we deduce that ∃λ 2 (m, Z, λ) > 0 such that (8) with regularization parameter λ is equivalent to arg min

f ∈H 1 |Z| (x,y)∈Z (y -f (x)) 2 + λ 2 (m, Z, λ) f 2 H ,
i.e., the KRR minimization problem with a regularization parameter λ 2 (m, Z, λ). Hence M-RLSR with λ is weakly equivalent to KRR with λ 2 (m, Z, λ). It is easy to see from ( 9) that the function F Z,m that maps λ to the corresponding λ 2 has the form F Z,m (λ) := m 2 C 0 (Z, m, λ)λ.

Since Φ A→B (λ, Z) heavily depends on Z, M-RLSR and KRR are not strongly equivalent but only weakly equivalent. Moreover, Assumptions 1 and 2 are not satisfied in this case, hence stability of M-RLSR cannot be deduced from that of KRR. A stability analysis of M-RLSR can be found in the supplementary material.

Experiments on Weak Equivalence

In this subsection, we conduct experiments on synthetic and real-world datasets to illustrate the fact that M-RLSR and KRR algorithms are only weakly equivalent but not strongly equivalent. We use the Concrete Compressive Strength (1030 instances, 9 attributes) real-world dataset extracted from the UCI repository2 . Additionally, we also use a synthetic dataset (2000 instances, 10 attributes) described in [START_REF] Tsang | Core vector regression for very large regression problems[END_REF]. In this dataset, inputs (x 1 , ..., x 10 ) are generated independently and uniformly over [0, 1] and outputs are computed from y = 10 sin(πx 1 x 2 ) + 20(x 3 -0.5) 2 + 10x 4 + 5x 5 + N (0, 1). We randomly split these datasets into 4 parts of equal size Z 1 , . . . , Z 4 . Using Z 1 , m is fixed and the regularization parameter λ is chosen by a 10-fold cross-validation for M-RLSR. Then the equivalent λ 2 for KRR is computed using Proposition 5.1. For each part Z i , 1 ≤ i ≤ 4, we calculate the norm of the difference between the optimal solutions given by M-RLSR and KRR. The results are presented in Figure 1. The difference between the solutions of the two algorithms is equal to 0 on Z 1 , but since both algorithms are only weakly equivalent, the difference is strictly positive on Z 2 , Z 3 , Z 4 , showing that the algorithms are not strongly equivalent. Additional experiments regarding the M-RLSR and its algorithmic properties can be found in the supplementary material.

Conclusion

We have presented a novel way of theoretically analyzing and interpreting relations between machine learning algorithms, namely the concept of algorithmic equivalence. More precisely, we have proposed two notions of equivalence of learning algorithms, weak and strong equivalence, and we have shown how to use them to transfer learning properties, such as stability, from one learning algorithm to another.

Although this work has focused in particular on the transfer of stability using the concept of algorithmic equivalence, we believe that it can be extended to study the transfer of other algorithmic properties such as sparsity, robustness and generalization. Future work will also aim at further quantifying the equivalence relations introduced by providing efficient tools that can help to decide whether two learning algorithms are weakly or strongly equivalent. Then the vector α = Qα ′ with

α ′ i = 2y ′ i 2d i + λmnC 0 , ∀1 ≤ i ≤ n , (9)
is the solution of (11) if and only if C 0 is the root of the function F : R + → R defined by

F (C) = n i=1 4d i y ′2 i (2d i + λmnC) 2 m/2-1 -C. (10)
Proof : First notice that, the objective function to minimize is Gâteaux differentiable in every direction. Thus, since f Z is a minimum, we have:

0 = n i=1 -2k(., x i )(y i -f Z (x i )) + λmn f Z m-2 H f Z , i.e., f Z = n i=1 2k(., x i ) y i -f Z (x i ) λmn f Z m-2 H .
That is to say, f Z can be written in the following form:

f Z = n i=1 α i k(., x i ), (11)
with α i ∈ R. Notice, that we have recovered exactly the form of the representer theorem, which can also be derived from a result due to Dinuzzo and Schölkop [START_REF] Dinuzzo | The representer theorem for Hilbert spaces: a necessary and sufficient condition[END_REF]. Now by combining ( 8) and ( 11), the initial problem becomes

α = arg min a∈R n (Y -Ka) ⊤ (Y -Ka) + nλ(a ⊤ Ka) m/2 , (12)
where α = (α i ) 1≤i≤n is the vector to determine. The following theorem gives an explicit formula for α that solves the optimization problem [START_REF] Jaggi | An equivalence between the lasso and support vector machines[END_REF].

By computing the Gâteaux derivative of the objective function to minimize in [START_REF] Jaggi | An equivalence between the lasso and support vector machines[END_REF], we obtain that α must verify

Y = Kα + λ mn 2 (α ⊤ Kα) m/2-1 α.
Then, since K is symmetric and positive semidefinite, ∃Q an orthonormal matrix (the matrix of the eigenvectors) and D a diagonal matrix with eigenvalues

(d i ) 1≤i≤n ≥ 0 such that K = QDQ ⊤ . Hence, Y = QDQ ⊤ α + λ mn 2 ((Q ⊤ α) ⊤ D(Q ⊤ α)) m/2-1 α ⇒ Q ⊤ Y = DQ ⊤ α + λ mn 2 ((Q ⊤ α) ⊤ D(Q ⊤ α)) m/2-1 Q ⊤ α.
Given this, one can define a new representation by changing the basis such that

Y ′ = Q ⊤ Y and α ′ = Q ⊤ α. We obtain Y ′ = Dα ′ + λ mn 2 (α ′⊤ Dα ′ ) m/2-1 α ′ .
Now if we write the previous equation for every coefficient of the vectors, we obtain that

y ′ i = d i α ′ i + λ mn 2 ( n j=1 d j α ′2 j ) m/2-1 α ′ i , ∀1 ≤ i ≤ n.
Note that ( n j=1 d j α ′2 j ) m/2-1 is the same for every equation (i.e. it does not depend on i), so we can rewrite the system as follows, where

C ∈ R                C = n j=1 d j α ′2 j m/2-1 and α ′ i = 2y ′ i 2d i + λmnC , ∀1 ≤ i ≤ n. (13)
which is well defined if d i +λmnC = 0, which is the case when C > 0. Since C ≥ 0 by definition, the only possibly problematic case is C = 0, but this implies that Y = 0, which is a degenerated case. Now we just need to calculate C, which verifies:

C = n i=1 d i α ′2 i m/2-1 = n i=1 4d i y ′2 i (2d i + λmnC) 2 m/2-1 .
Thus to obtain an explicit value for α ′ , we need only to find a root of the function F defined as follows :

F (C) = n i=1 4d i y ′2 i (2d i + λmnC) 2 m/2-1 -C.
We have proven that any solution of ( 12) can be written as a function of C 0 , a root of F . But for m > 1, F is strictly concave, and F (0) > 0, hence it has at most one root in R + . Thus since lim C→+∞ F (C) = -∞, F has exactly one root, which proves Theorem 2.

D Stability Analysis of M-RLSR

The notion of algorithmic stability, which is the behavior of a learning algorithm following a change of the training data, was used successfully by Bousquet and Elisseeff [START_REF] Bousquet | Stability and generalization[END_REF] to derive bounds on the generalization error of kernel-based learning algorithms. In this section, we extend the stability results of [START_REF] Bousquet | Stability and generalization[END_REF] to cover the m-power RLSR algorithm. We show here that the algorithm is stable for m ≥ 2.

In this section we denote by X and Y a pair of random variables following the unknown distribution D of the data, X representing the input and Y the output, by Z i = Z \ (x i , y i ) the training set from which was removed the element i. Let c(y, f, x) = (yf (x)) 2 denotes the cost function used in the algorithm. For all f ∈ H, let R e (f, Z) = 1/n 1≤i≤n c(y i , f, x i ) be the empirical error and R r (f, Z) = R e (f, Z) + λ f m H be the regularized error. Let us recall the definition of uniform stability.

Definition D.1 An algorithm Z → f Z is said β uniformly stable if and only if ∀n ≥ 1, ∀1 ≤ i ≤ n, ∀Z a realization of n i.i.d. copies of (X, Y ),∀(x, y) ∈ X × Y a Z independent realization of (X, Y ),

we have |c(y, f Z , x) -c(y, f Z i , x)| ≤ β.
To prove the stability of a learning algorithm, it is common to make the following assumptions.

∀1 ≤ i ≤ n, ∀Z a realization of n i.i.d. copies of (X, Y ),∀(x, y) ∈ X × Y a Z independent realization of (X, Y ), |c(y, f Z , x) -c(y, f Z i , x)| ≤ C|f Z (x) -f Z i (x)|, with C = 2 C y + κ C 2 y λ 1 m .
Proof : Since H is a vector space, 0 ∈ H, and

λ f Z m ≤ 1 n n i=1 (y i -f Z (x i )) 2 + λ f Z m H ≤ 1 n n k=1 y k -0 2 + λ 0 m H ≤ C 2 y ,
where we used the definition of f Z as the minimum of (8) and Hypothesis 3. Using the reproducing property and Hypothesis 4, we deduce that

|f Z (x)| ≤ k(x, x) f Z H ≤ κ f Z H ≤ κ C 2 y λ 1 m
.

The same reasoning holds for f Z i . Finally,

|c(y,f Z , x) -c(y, f Z i , x)| = |(y -f Z (x)) 2 -(y -f Z i (x)) 2 | ≤ 2   C y + κ C 2 y λ 1 m   |f Z (x) -f Z i (x)|.
The stability of our algorithm when m ≥ 2 is established in the following theorem, whose proof is an extension of Theorem 22 in [START_REF] Bousquet | Stability and generalization[END_REF]. The original proof concerns the KRR case when m = 2. The beginning of our proof is similar to the original one; but starting from [START_REF] Dinuzzo | The representer theorem for Hilbert spaces: a necessary and sufficient condition[END_REF], the proof is modified to hold for m ≥ 2, since the equalities used in [START_REF] Bousquet | Stability and generalization[END_REF] no longer holds when m > 2,. We use inequalities involving generalized Newton binomial theorem instead.

Theorem 3 Under the assumptions 3 and 4, algorithm

Z → f Z defined in (8) is β stable ∀m >= 2 with β = Cκ 2 m-2 Cκ λn 1 m-1 . Proof : Since c is convex with respect to f , we have ∀0 ≤ t ≤ 1 c(y, f Z +t(f Z i -f Z ), x) -c(y, f Z , x) ≤ t (c(y, f Z i , x) -c(y, f Z , x)) .
Then, by summing over all couples (x k , y k ) in

Z i , R e (f Z +t(f Z i -f Z ), Z i ) -R e (f Z , Z i ) ≤ t R e (f Z i , Z i ) -R e (f Z , Z i ) . (14)
By symmetry, ( 14) holds if Z and Z i are permuted. By summing this symmetric equation and ( 14), we obtain

R e (f Z + t(f Z i -f Z ), Z i ) -R e (f Z , Z i ) + R e (f Z i + t(f Z -f Z i ), Z i ) -R e (f Z i , Z i ) ≤ 0. (15)
Now, by definition of f Z and f

Z i , R r (f Z , Z) -R r (f Z + t(f Z i -f Z ), Z) + R r (f Z i , Z i ) -R r (f Z i + t(f Z -f Z i Z i ) ≤ 0. ( 16
)
By using ( 15) and ( 16) we get

c(y i , f Z , x i ) -c(y i , f Z + t(f Z i -f Z ), x i ) + λn ( f Z m H -f Z + t(f Z i -f Z ) m H + f Z i m H -f Z i + t(f Z -f Z i ) m H ) ≤ 0, (17)
This inequality holds ∀t ∈ [0, 1]. By choosing t = 1/2 in (17), we obtain that

|c(y i , f Z , x i ) -c(y i , f Z + 1 2 (f Z i -f Z ), x i )| ≥ nλ f Z m H -2 f Z i + f Z 2 m H + f Z i m H , (18)
Let u = (f Z + f Z i )/2 and v = (f Z -f Z i )/2. Then, u + v m H + u -v m H -2 u m H -2 v m H = f Z m H + f Z i m H -2 f Z i + f Z 2 m H -2 f Z i -f Z 2 m H = u 2 H + v 2 H +2 u, v H m/2 -2 u 2 H m/2 + u 2 H + v 2 H -2 u, v H m/2 -2 v 2 H m/2 ≥ 2 u 2 H + v 2 H m/2 -2 u 2 H m/2 -2 v 2 H m/2 ≥ 0,
where in the last transition we used both Newton's generalized binomial theorem for the first inequality and the fact that m/2 > 1 for the second one. Hence, we have shown that

f Z m H -2 f Z i + f Z 2 m H + f Z i m H ≥ 2 f Z i -f Z 2 m H . (19)
Now, by combining ( 18) and ( 19), we obtain by using Lemma D.2,

f Z -f Z i m H ≤ 2 m-1 λn c(y i , f Z + 1 2 (f Z i -f Z ), x i ) -c(y i , f Z , x i ) ≤ 2 m-2 C λn f Z i (x i ) -f Z (x i ) Y ≤ 2 m-2 Cκ λn f Z i -f Z H , which gives that f Z -f Z i H ≤ 2 m-2 Cκ λn 1 m-1 .
This implies that, ∀(x, y) a realization of (X, Y ),

|c(y, f Z , x) -c(y, f Z i , x)| ≤ C f Z (x) -f Z i (x) Y ≤ Cκ 2 m-2 Cκ λn 1 m-1 .
For 1 < m < 2, the problem ( 8) is well posed but the question whether the algorithm is stable or not in this case remains open. Future studies need to be conducted to further address this issue explicitly.

E Additional Experiments on M-RLSR

In this section, we conduct experiments on synthetic and real-world datasets to evaluate the efficiency of the proposed algorithm. We use the following real-world datasets extracted from the UCI repository3 : Concrete Compressive Strength (1030 instances, 9 attributes), Concrete Slump Test (103 instances, 10 attributes), Yacht Hydrodynamics (308 instances, 7 attributes), Wine Quality (4898 instances, 12 attributes), Energy Efficiency (768 instances, 8 attributes), Housing (506 instances, 14 attributes) and Parkinsons Telemonitoring (5875 instances, 26 attributes). Additionally, we also use a synthetic dataset (2000 instances, 10 attributes) described in [START_REF] Tsang | Core vector regression for very large regression problems[END_REF]. In this dataset, inputs (x 1 , ..., x 10 ) are generated independently and uniformly over [0, 1] and outputs are computed from y = 10 sin(πx 1 x 2 ) + 20(x 3 -0.5) 2 + 10x 4 + 5x 5 + N (0, 1). In all our experiments, we use a Gaussian kernel k µ (x, x ′ ) = exp(-xx ′ 2 2 /µ) with µ = 1 n 2 i,j x ix j 2 2 , and the scaled root mean square error (RMSE), defined by 1 max yi 1 n i (y if (x i )) 2 , as evaluation measure.

E.1 Speed of Convergence

We compare here the convergence speed of M-RLSR with m ≤ 1 and KRR on Concrete compressive strength, Yacht Hydrodynamics, Housing, and Synthetic datasets. As before, each dataset is randomly split into two parts (70% for learning and 30% for testing). The parameters m and λ are selected using cross-validation: we first fix λ to 1 and choose m over a grid ranging from 0.1 to 1, then λ is set by cross-validation when m is fixed. For KRR, λ 2 is computed from λ and m using Proposition 5.1.

Figure 3 shows the mean of RMSE over ten run for the four datasets with M-RLSR and KRR when varying the number of examples of training data from 10% to 100% with a step size of 5%. In this figure, we can see that M-RLSR with m < 1 can improve the speed of convergence of KRR. This confirms the theoretical expectation for this situation [START_REF] Mendelson | Regularization in kernel learning[END_REF], that is a regularization exponent that grows significantly slower than the standard quadratic growth in the RKHS norm can lead to better convergence behavior.

E.1.1 Prediction Accuracy

We evaluate the prediction accuracy of the M-RLSR algorithm using the datasets described above and compare it to KRR. For each dataset we proceed as follows: the dataset is split randomly into two parts (70% for training and 30% for testing), we set λ = 1, and we select m using crossvalidation in a grid varying from 0.1 to 2.9 with a step-size of 0.1. The value of m with the least mean RMSE over ten run is selected.Then, with m now fixed, λ is chosen by a ten-fold cross validation in a logarithmic grid of 7 values, ranging from 10 -5 to 10 2 . Likewise, λ 2 for KRR is chosen by 10-fold cross-validation on a larger logarithmic grid of 25 equally spaced values between 10 -7 and 10 3 . RMSE and standard deviation (STD) results for M-RLSR and KRR are reported in Table 1. It is important to note that the double cross-validation on m and λ for M-RLSR, and the crossvalidation on the greater grid for the KRR takes a similar amount of time. Table 1 shows that the m-power RLSR algorithm is capable of achieving a good performance results when m < 2. Note that the difference between the performance of the two algorithms M-RLSR and KRR decreases as the grid of λ becomes larger, but in practice we are limited by computational reasons. Table 1: Performance (RMSE and STD) of m-power RLSR (M-RLSR) and KRR algorithms on synthetic and UCI datasets. m is chosen by cross-validation on a grid ranging from 0.1 to 2.9 with a step-size of 0.1.

Definition 3 . 2 (

 32 Equivalence). Let Z be a training set. Two algorithms A and B are equivalent on Z if and only if A(Z) = B(Z).

Definition 3 . 3 (

 33 Weak Equivalence). Let A(•) and B(•) two regularized learning algorithms on R * + × Z. Then A(•) and B(•) are said to be weakly equivalent if and only if

Definition 3 . 4 (

 34 Strong Equivalence). Let A(•) and B(•) two regularized learning algorithms on R * + × Z. Then A(•) and B(•) are said to be strongly equivalent if and only

Definition 4 . 2 (

 42 Uniform stability). Let β : N + ×R *

Proposition 4 . 5

 45 The function H : Z × Z → R defined in definition 4.4 is a metric over Z.

Algorithm 1 M+ 1 . 2 . 3 .

 1123 -Power RLS Regression Algorithm (M-RLSR) Input: training data Z = {(x 1 , y 1 ), .., (x n , y n )}, parameter λ ∈ R * + , exponent m ∈ R * Kernel matrix: Compute the Gram matrix, K = k(x i , x j ) 1≤i,j≤n Matrix diagonalization: Diagonalize K in an orthonormal basis K = QDQ ⊤ ; d i = D ii , ∀1 ≤ i ≤ n Change of basis: Perform a basis transformation

Figure 1 :

 1 Figure 1: The norm of the difference between the optimal solutions given by M-RLSR and KRR on two datasets randomly split into 4 parts Z 1 , . . . , Z 4 . While the difference on Z 1 is zero for the two algorithms since they are weakly-equivalent, they give different solution for Z 1 , Z 2 and Z 3 . (left) Concrete compressive strength dataset: m = 1.5, λ = 1e -2 (obtained by 10-fold cross validation) and λ 2 = 5.6e -4 (computed from Proposition 5.1). (right) Synthetic dataset: m = 1.2, λ = 1e -5 (obtained by 10-fold cross validation) and λ 2 = 6.5e -7 (computed from the Proposition 5.1).

Figure 2 :

 2 Figure 2: Error curves for KRR, modified KRR defined by (??) and M-RLSR with m=1.5 on the dataset Yatch hydrodynamic(left) and (right), both extracted from the UCI repository,

Assumption 3

 3 ∃C y > 0 such that |Y | < C y a.s. Assumption 4 ∃κ > 0 such that sup x∈X k(x, x) < κ 2 Lemma D.2 If Hypotheses 3 and 4 hold, then ∀n ≥ 1,

Figure 3 :

 3 Figure 3: RMSE curve of M-RLSR (blue) and KRR (red) algorithms as a function of the dataset size. (top left) Concrete compressive strength (m = 0.1). (top right) Yacht Hydrodynamics (m = 0.5). (bottom left) Housing (m = 0.4). (bottom right) Synthetic (m = 0.1).

Note that the Hamming metric and the generalized Hamming metric do not coincide on the set of ordered sequences.

http://archive.ics.uci.edu/ml/datasets.

http://archive.ics.uci.edu/ml/datasets.

A Weak Equivalence and Regularization Path

Let Z ∈ Z be a fixed training set, and A and B two weakly equivalent algorithm. By definition of the weak equivalence A(•)(Z) = B(Φ A→B (•, Z))(Z). This formulation highlights the consequence of the weak equivalence with the regularization path: the regularization path of B can be obtained from the the regularization path of A with the bijective transformation Φ A→B (•, Z) of the variable λ. It is important to note that Φ A→B (•, Z) depends on Z, i.e. the relation between the regularization path of A and B depends on Z. The same can be said for the error curves, but Proposition 4.1 ensure that they share the same minimum value (see figure 1).

B Proof of Proposition 4.6

Proof : It is easy to see that H is symmetric and H(Z 1 , Z 2 ) ≥ 0 and is equal to 0 if and only if Z 1 = Z 2 . Now, in order to prove the sub-additivity of H, let Z 1 , Z 2 and Z 3 ∈ Z. Note that G n counts the number of elements which differs between two unordered sequences, and thus is sub-additive.

We only write here the case #(Z 2 ) ≥ #(Z 1 ) ≥ #(Z 3 ), the other cases are done likewise. Let for i = 1, 3

Without any loss of generality, suppose that #(Z 2 1 ) ≥ #(Z 2 3 ). Then,

3 ), where Ẑ = arg min

3 ). ( 7)

where, in the second line we used [START_REF] Mendelson | Regularization in kernel learning[END_REF], third line we used the sub-additivity of G, fourth line we used the fact that Ẑ ⊂ Z 2 1 , and last line we used #(Z 2 ) ≥ #(Z 1 ) ≥ #(Z 3 ).

C Proof of Theorem 1

Remember that we are trying to solve the following problem :

where m is a suitable chosen exponent.

For the convenience of the reader, let us rewrite the theorem we are going to prove


Thomas Lopez

Rozenn Bouville Berthelot

Emilie Loup-Escande

Florian Nouviale

Valérie Gouranton

Bruno Arnaldi

Rozenn Bouville

Val Érie Gouranton

Exchange of avatars : Toward a better perception and understanding

Keywords: Perception, User-centered evaluations, Virtual environments for training, Multi-user virtual environments

come

INTRODUCTION

Multi-actor virtual reality applications aim at immersing users in virtual environments populated with other actors, represented by avatars. Such virtual environments allow them to perform various actions and interactions that may be impossible in the real world. One of the most desired actions is perhaps taking control over another avatar, changing its incarnation on the fly to see the world through someone else's eyes. This takeover could have a wide range of motives: making another actor perform a specific action, accessing some knowledge possessed only by a particular avatar, resolving conflicts and deadlock situations or assisting another actor. The main difficulty in multi-actor environments is that avatars can be controlled by either real users or virtual agents. The takeover may then imply an exchange of control of the owners of the involved avatars. Moreover, in some environments, each avatar is also associated with specific metadata such as its own knowledge on the world and on the entities therein. Therefore, metadata coherence also needs to be taken into account during exchanges of avatars. For instance, in Virtual Environments for Training (VET), knowledge gathered by an avatar must remain available to its new owner after an exchange.

In the literature, recent contributions have described exchange protocols. To our knowledge, however, no user-centered evaluation focuses on the perception and understanding of the exchange of avatars. Following this idea, our work attempts to assess the key elements in the representation of an exchange between two actors' avatars, either real users or virtual agents, given one of its aims is to be understood by the users. In this study, we focus on multi-actor virtual environments where the user is embodied in an avatar with a first-person view. In the context of this paper, we are only interested in the visual represen- tation of the exchange. Nevertheless, many visual parameters remain available to represent the same exchange of avatar, such as color, animation, duration, etc. In this paper, we refer to a specific configuration of these parameters as an exchange metaphor.

This study tries to analyze the key elements in the design of an exchange metaphor. We hypothesize that whether the user is involved in the exchange or just witnessing it a different metaphor should be used. Therefore, we designed two experiments to compare several exchange metaphors. In the first experiment, users witness exchanges, whereas in the second they are directly involved in the exchange. We also think that exchange metaphors should be tailored to the user's familiarity with virtual reality applications. We also explore the effect of abstract vs. explicit metaphors, as well as static vs. dynamic representations. We present here the results of these two experiments and highlight relevant elements that impact the design of an exchange metaphor for a virtual reality application. Results notably show that the use of visual feedback globally helps better understanding of the exchange mechanism. Visual feedback, however, can be less efficient than a simple popup notification in terms of task duration. Moreover, the use of simpler metaphors with no visual effect is generally preferred in triggering an exchange because of their efficiency.

The rest of the paper is organized as follows. First, the following Section 2 presents related work on role exchanges. In Section 3, we explain the concept of the exchange metaphor and the experiment's motivations. In Section 4 we describe our two experiments and give an analysis of the obtained results. Section 5 concludes.

RELATED WORK

The role of an actor in a virtual environment has been defined as a coherent set of standard behaviors [START_REF] Guye-Vuilleme | A high-level architecture for believable social agents[END_REF]. Role exchange, also termed role switching or role swapping, has been studied for many years in the Intelligent Robots field [START_REF] Martinson | Learning to role-switch in multi-robot systems[END_REF][START_REF] Monacelli | A reactive assistive role switching for interaction management in cooperative tasks[END_REF] where it is used to improve the achievement of collaborative tasks. Indeed, the possibility of switching the role assigned to robots between leader and follower is an efficient way to speed up a task and to resolve conflicts. In the Virtual Reality domain, Evrard et al. [START_REF] Evrard | Homotopy switching model for dyad haptic interaction in physical collaborative tasks[END_REF] also take advantage of the possibility of switching between a leader and a follower role to improve the collaboration of users involved in a dyad haptic interaction for a physical collaborative task. More recently, role exchanges have also taken place in the context of human computer haptic collaboration [START_REF] Oguz | Haptic negotiation and role exchange for collaboration in virtual environments[END_REF]. The system provides haptic feedback to the user through a force negotiation mechanism, in order to help him/her achieve a dynamic task. Furthermore, the system is able to detect if the user needs help and, if necessary, switches from an assistive role to an equal-control role to complete the task.

The role notion is also very common in areas such as Interactive Storytelling [START_REF] Machado | Is the wolf angry or... just hungry[END_REF] or Collaborative Virtual Environments for Training (CVET) [START_REF] Dugdale | Emergency fire incident training in a virtual world[END_REF][START_REF] Rickel | Virtual humans for team training in virtual reality[END_REF][START_REF] Sycara | Literature review of teamwork models[END_REF], notably to define interactions between autonomous agents. In virtual environments, the notion of role exchange and exchange of avatars are often mixed as each avatar possesses its own capabilities and thus exchanging roles includes exchanging of avatars. Role exchange is a particularly interesting feature for CVET. Indeed, Seers et al. [START_REF] Seers | Team-member exchange quality: A new construct for rolemaking research[END_REF][START_REF] Seers | Team-member exchange under team and traditional management: A naturally occurring quasiexperiment[END_REF] studied team-member relationships and showed that the quality of lateral (within-group) relationships is as important as that of vertical relationships (with hierarchical supervisors) and even observed gains in production efficiency in self-managing teams. Therefore, the chance to learn the different roles associated with a procedure and to understand the work as a whole can reinforce the cohesion of the team. Thus, it is important for a trainee to be able to exchange his/her role with one of his/her teammates during training, so that he/she can better overview the collaborative procedure as a whole and understand more than a simple sequence of individual actions. In fact, role exchange proposes new usages for both designers and users for CVET and is also a promising and challenging trend for this area. It generates new concepts; for instance, in [START_REF] Luna | The perceptive puppet: Seamless embodiment exchange between real and virtual humans in virtual environments for training[END_REF], an entity called the Perceptive Puppet and an interaction model [START_REF] Luna | Collaborative Virtual Environments For Training: A Unified Interaction Model For Real Humans And Virtual Humans[END_REF] are described to allow trainees to exchange their avatars on the fly without interrupting the training procedure. Other CVETs also propose after-action review tools using role exchange to enhance experiences between users and virtual humans such as that used by Raij et al. [START_REF] Raij | Ipsviz: An after-action review tool for humanvirtual human experiences[END_REF]. Using the IPSViz tool, they offer the trainee the chance to take the role of an avatar that was previously his/her conversation partner. This is done during the review process so that the user can see how his/her performance was perceived through someone else's eyes and improve his/her behavior later on. Moreover, various perception studies have been interested in the link between a user and the avatar he/she controls in the virtual world [START_REF] Maselli | The building blocks of the full body ownership illusion[END_REF]. Such studies have been interested in disrupting the spatial unity between the self and the body [START_REF] Lenggenhager | Video ergo sum: manipulating bodily self-consciousness[END_REF] or in triggering the illusion that an artificial body was the user's one [START_REF] Petkova | If i were you: perceptual illusion of body swapping[END_REF]. In these studies, multisensory information is manipulated to make users believe they are embodied in a new body, or avatar, and to analyze for instance their feeling of ownership toward their new body. Slater et al. [START_REF] Slater | First person experience of body transfer in virtual reality[END_REF] conducted a perception study about the experience of body transfer in a virtual environment. In this study, the user point of view was modified during the experimentation allowing the user to watch the same scene sequentially from different perspectives, from an external viewpoint to a view embodied in the main character's eyes. This study aimed at analyzing differences in the users reactions depending on their point of view, in other word their role, in the virtual environment. The exchange metaphor used in this experimentation was not analyzed, however.

The exchange of avatars or roles is a useful tool for virtual reality applications, CVET and perception studies. This concept is also used in video games when a user has to control different characters, such as in the last Grand Theft Auto 5 1 where the player can swap character to enhance his/her game experience. Despite the increasing interest in exchanges of avatars, however, no user-centered evaluation has yet focused on the perception and understanding of this mechanism.

TOWARD THE EVALUATION OF EXCHANGE METAPHORS

Motivations

The exchange of avatars gives the user the possibility of taking control over another avatar to see and act in the environment from a brand new perspective. This exchange can result from different reasons: control of multiple avatars at the same time, making an avatar perform a specific action, or accessing some knowledge it possesses but also resolving conflicts and deadlock situations or assisting another actor. For instance, in some video games, this exchange is used so that the player can control one of many characters and change at any time. Moreover, in the context of VET, the exchange allows a trainer to switch his/her role with a trainee so that he/she can show a particular manipulation or gesture, for instance in a surgery procedure.

This exchange brings new challenges to multi-user virtual environments. First, users must comprehend they are involved in an exchange process. Second, they must understand they are now embodied in a new avatar. Third, they must be able to locate themselves in the virtual environment as the exchange might disorient them. Moreover, they also need to deal with various metadata associated with their new avatars such as new capabilities, different knowledge on the environment or on simulation history and so on. Although exchanges of avatar have often been used in the literature [START_REF] Raij | Ipsviz: An after-action review tool for humanvirtual human experiences[END_REF][START_REF] Luna | The perceptive puppet: Seamless embodiment exchange between real and virtual humans in virtual environments for training[END_REF][START_REF] Slater | First person experience of body transfer in virtual reality[END_REF], the method of representing this exchange has never been evaluated.

This study proposes to tackle this issue by proposing a first evaluation of different exchange metaphors. The term Exchange Metaphor refers to the set of parameters defining such a representation of an exchange of avatars in a virtual environment. This metaphor can use various multisensory information such as sounds or visual effects to represent the exchange. In this study, we only focus on the visual representation of these metaphors. Still, a multitude of parameters are available to define a metaphor as a combination of visual elements : color, animation, speed, duration, text display, camera effects, etc. As a study covering the set of all possible parameters is impossible to conduct, this paper focuses on exchange metaphors using an intentionally limited set of these parameters.

Design of the metaphor evaluation

The purpose of this study is more to determine the relevant criteria involved in designing exchange metaphors for a given application than to highlight the best metaphor. In order to design our experiments, we distinguished two groups of exchange metaphors as follows:

• The user witnesses the exchange. In this case, the user needs to perceive and comprehend an exchange of avatars between other actors in the environment. For instance, a trainee is learning a procedure which requires the help of his/her trainer while this trainer is exchanging his/her avatar with another actor in the environment. Therefore, the trainee needs to understand the exchanges in order to ask for his/her assistance. Our first evaluation focuses on comparing different metaphors with this witness condition of the user.

• The user triggers the exchange of his/her own avatar. Here, the user needs to be able to easily trigger his/her exchange with another avatar and acknowledge that the exchange is being performed. Unlike the previous experiment, the participant is now involved in his/her own exchange. For example, the user is watching a surgical procedure and wants to pursue the surgical procedure by exchanging his/her avatar with the current surgeon. He/she then asks for control of the surgeon's avatar and processes to the exchange of avatars. Therefore, our second evaluation compares several metaphors designed specifically for this experimental condition.

These two groups are complementary as they target two different conditions of exchange of avatars, depending on whether the user is involved or not. We do not study the case where users are involved in an exchange they did not trigger. We consider that, in this situation, a notification would appear to inform the user that another actor is asking for an exchange of avatar. If the user then accepts the request, the exchange should be triggered, which is equivalent to our second experiment.

Despite the need to separate our analysis into two experiments, we want to analyze common criteria for both conditions. These criteria can be categorized in two groups: Understanding and Perception of the metaphor. Therefore, we used for this analysis several variables that fall within the user experience. This user experience is defined as a consequence of an interaction between a user (with his/her characteristics) and a product (with its features and qualities) after an evaluation process [START_REF] Hassenzahl | User experience-a research agenda[END_REF]. The criteria we use to measure this user experience for the different exchange metaphors are defined as follows:

• Understanding: the user should easily and quickly understand what is happening and who is involved in the exchange. To evaluate comprehension, we use criteria such as the ease of understanding, the users' subjective feelings, the number of errors and the duration of sessions.

• Perception: the exchange metaphor should be pleasant to use. Moreover, it should not be disturbing for the user as this could dissuade him/her from using it. It is evaluated with criteria such as the aesthetic aspect, the originality of the metaphor, or the degree of excitement and pleasant assessed by the user.

EVALUATION OF THE EXCHANGE METAPHORS

We present two complementary experiments defined as follows. Our first experiment compares three exchange metaphors. Here, participants are not involved in the exchange but are only witnesses of several exchanges of avatars. Our second experiment compares five exchange metaphors. Unlike the first experiment, participants are now involved in the exchange as they trigger the exchange of their own avatar. The purpose of these two experiments is to analyze the perception and the comprehension of the exchange of both a spectator and an actor in the exchange.

In this section we present the two experimental protocols we used as well as the results we obtained. The first experiment is presented in Section 4.2 and the second in Section 4.3. For each experiment, Subsection (1) presents the goal and the design of the metaphors. Then, we detail the experimental groups (2), the procedure (3) and the collected data [START_REF] Guye-Vuilleme | A high-level architecture for believable social agents[END_REF]. The results we obtained are explained in Subsections [START_REF] Hassenzahl | User experience-a research agenda[END_REF]. Through these two experiments we noted some interesting differences but also some commonalities between the novice and the expert users which are detailed in Subsections (6).

Experimental Setup

Experiment 1 took approximately 30 minutes to complete and experiment 2 took approximately 20 minutes. Participants were encouraged to take breaks between each trial to avoid fatigue. Participants came from various educational backgrounds and were all unaware of the purpose of the experiments. We also balanced the groups to get a similar number of male and female participants. They were mainly recruited from a university and administration background.

Participants used an application designed with the engine Unity 4 and RocketBox Studios characters. The experiment for all of the participants ran on a 30 inch monitor with a resolution of 1920 x 1200 pixels. Participants were not able to see the different experimental conditions beforehand. Moreover, the experiments were conducted in a room without environmental noise or any other source of distraction.

Experiment 1: The User Witnesses the Exchange

Objective and Study Design

This first experiment compares several exchange metaphors in order to evaluate which one is more usable or provides a more positive experience to a user who witnesses an exchange. To do this, we decided to compare different metaphors using static visual feedback, animated visual feedback or simple 2D-GUI. Therefore, we designed three metaphors: (1) an on-site visual metaphor, (2) a moving and animated visual metaphor and (3) a 2D-GUI with a text and a static image. These representations used a color code; each virtual owner of an avatar was represented by a different color in the metaphor. The exchange metaphors are defined as follows:

1. Flickering avatar (M A (⊛)): the two avatar textures blink several times from white to the color of their new owner (cf. Fig. 1(a)).

Ghost translation (M B (∄))

: a ghost appears besides each of the two original avatars and moves to the location of the newly possessed avatar. Each ghost is colored according to the owner's color representation (cf. Fig. 1(b)). These ghosts materialize owners in a visual transition representing their disembodiments from their former avatar and their embodiments in the new one.

3.

Popup notification (M C ( )): For each of the two avatars involved in an exchange, a textbox displays the picture of the avatar, with a background color matching the new owner's color and a label specifying the new owner's name (cf. Fig. 1(c)).

To avoid introducing a confounding factor from variable exposure durations, all the metaphors have the same display duration. Moreover, as we wanted to assess if the participants were aware of the exchanges of avatar in the environment, no information was displayed apart from the metaphors to inform the participant of who was controlling which avatars (A demonstration video of these three metaphors is presented here : http://youtu.be/Yu4YpGzKXes ). Table 1 sums up these different representations. Moreover, a glimpse of these metaphors is presented in Fig. 1 which shows the same exchange with the three metaphors used in this experiment.

Metaphor name Visual representation Symbol

Metaphor A Flickering avatar M A (⊛)

Metaphor B Ghost translation M B (∄) Metaphor C Popup Notification M C ( )

Participants

Fifty-four participants (7 females and 47 males, aged from 18 to 63, mean=28.6, sd=7.8) took part in the experiment. The experiment was divided into three experimental groups, one for each of our three metaphors. Each participant was assigned to one of these experimental groups according to four criteria: gender, age, occupation and knowledge in virtual reality (VR). The experimental groups are balanced as homogeneous as possible using those four criteria and consisted of 18 participants. The groups were characterized in Table 2.

Procedure

Each participant was first informed about the complete study proceedings. Then, they completed an identification questionnaire allowing us to collect general information about their demographics, occupation and experience with VR. Next, a demonstration video introduced the exchange metaphor associated with their experimental group and gave instructions about the objective. The objective consisted in performing a scenario composed of nine tasks in order to repair a vehicle in the environment presented in Fig. 2. Participants had to perform the tasks presented in Table 3. For each task, participants had to go to a specified area of the environment and then to act on the designated elements. The scenario alternated between individual (I) and collaborative tasks (C) which were displayed one after the other during the session. These tasks did not require any a priori knowledge on the vehicle or on mechanics and were explained to the participants one after the other during each session. During the experiment, participants viewed three avatars whose purpose was to assist the user during collaborative tasks. Participants were informed that each avatar was controlled by an agent who was an expert in a specific area (a wheel expert, a window expert and an engine expert) and that they must ask the appropriate expert for help with each collaborative task. For example, the wheel expert was required to change a wheel. Each expert was also associated with a specific color: yellow (wheel expert), blue (window expert) and red (engine expert). These colors were the same across all experimental conditions so that participants could recognize which experts were exchanging their avatars. We also presented participants at the beginning of the experiment with the avatars and their controlling experts (avatar A is controlled by the wheel expert,...). During each individual task in the scenario, exchanges of avatars were performed between the three experts. All the exchanges were scripted to ensure similar conditions for all the participants. During these exchanges participants were able to continue the task they were doing and were not forced to watch the whole exchange protocol. All participants performed the same scenario three times, with different expert exchanges for each trial. After each trial, participants had to indicate in which avatar each of the three experts was embodied. After the third and final trial, participants were asked to fill in a questionnaire to provide their impressions, comments and subjective judgments. They were not asked to perform the scenario as quickly as possible; we expected, however, to observe some learning effect on the procedure completion time regardless of the metaphor used.

Collected Data

For each trial and each participant, we recorded the total duration of the trials as well as the number of errors (i.e., a wrong expert has been selected). At the end of the experiment, the participants had to fill in a subjective questionnaire with [A] a Likert-scale (1: not agree at all, 7: totally agree) for the following criteria: (1) the metaphor is easy to understand, (2) the metaphor is easy to use, (3) the metaphor distracts you from the task and (4) this metaphor is a good idea; and [B] a semantic differential: this exchange metaphor is (5) strange versus familiar, (6) obstructing versus supporting, (7) ordinary versus original, (8) boring versus exciting, (9) unpleasant versus pleasant and (10) unaesthetic versus aesthetic Open-ended questions concerning positive and negative aspects as well as suggestions to improve the metaphor where also added in the questionnaire. The significant results obtained for this experiment are summed up in Table 6 and detailed in Section 4.2.5.

Results

In this experiment, each participant was testing only one metaphor. Therefore, we used the independent-sample measurement techniques for the statistical analysis.

When the Test of Normality (i.e., Shapiro Wilk test) indicated a significant result (p < 0.05), suggesting a violation of the assumption of normality, we used Kruskal-Wallis and Mann-Whitney tests. Sig- nificant differences between the three metaphors were found for six criteria: ease of understanding, good idea, originality of the metaphor, exciting degree, pleasant degree and task duration. The computed significant differences are presented in Table 4. No significant difference was computed for the remaining criteria using this test. The significant differences between the pairs of metaphors using Mann-Whitney tests for the different criteria are summed up in Table 5. Whenever a significant difference is observed in our results, please refer to this table to find the associated values. When the Test of Normality (i.e., Shapiro Wilk test) indicated a non-significant difference (p > 0.05), suggesting a validation of the assumption of normality, we used One-Way Between-Groups ANOVA and Tukey HSD tests. Thus, with regard to the aesthetic degree, we performed an ANOVA analysis of variance that showed a statistically significant difference between the metaphors (F(2, 51) = 3.78, p < 0.05). Most of our results are presented in boxplots (see Fig. 3). These boxplots are delimited by the quartiles (25%-and 75%-quartile) of the distribution of the condition over all the individuals. Moreover, the medians, minima and maxima are given for each boxplot. Each significant result is explained in a paragraph where the first bold sentence presents the conclusion and the relevant tests are detailed after. Metaphor M B (∄) is easier to understand, perceived as a better idea and more aesthetic than metaphor M C ( ). The Mann-Whitney test indicated a significant difference only between M B (∄) and M C ( ), which suggests that metaphor M B (∄) is easier to understand than metaphor M C ( ) (see Fig. 3(a)). In the same vein, this test also suggests that metaphor M B (∄) is globally a better idea than metaphor M C ( ) (see Fig. 3(b)). Concerning the aesthetic degree, post-hoc comparisons using the Tukey HSD test indicated that metaphor M B (∄) was perceived as more aesthetic than metaphor M C ( ) (see Fig. 3(c)). M A (⊛) showed no significant difference from either M B (∄) or M C ( ).

Metaphor M B (∄) is more original than the others. The Mann-Whitney test indicated significant differences between M A (⊛) and M B (∄), and between M B (∄) and M C ( ). This suggests that metaphor M B (∄) was judged more original than both M A (⊛) and M C ( ) (see Fig. 3(d)). Table 6. Categorization of the Relevance of each Metaphor by Significant Differences (+ rated Significantly Higher, -rated Significantly Lower, 0 no Significant Difference).

Ease of understanding Good idea Aesthetic Originality Excitement degree

Pleasant Task duration

M A (⊛) 0 0 0 - + + - M B (∄) + + + + + + - M C ( ) - - - - - - +
Metaphor M C ( ) is more boring and unpleasant than the others. With the Mann-Whitney test, significant differences were observed between M A (⊛) and M C ( ) concerning the boring and pleasant degrees as well as between M B (∄) and M C ( ). This suggests that metaphor M C ( ) was judged more boring than the metaphors M A (⊛) and M B (∄) (see Fig. 3(e)) but also less pleasant (see Fig. 3(f)).

The group using M C ( ) was faster than the other groups. In this case, a Mann-Whitney test indicated significant difference between M A (⊛) and M C ( ) as well as between M B (∄) and M C ( ). This suggests that the mean duration of the task accomplishment with metaphor M C ( ) (214 sec) was shorter than with M A (⊛)(256 sec) and M B (∄)(247 sec) (see Fig. 4).

No difference in terms of ease of use, distraction, facility, obstruction and number of errors was found between these metaphors. This suggests that no metaphor is better than another regarding these criteria. For this experiment, we had a total of 32 novice users and 22 expert users. We did not find any significant differences between novice and expert ratings for ease of understanding, excitement, and pleasant and aesthetic degrees. Whatever the metaphor, however, the exchange metaphors were considered a better idea by the novice users (mean= 4.53) than by the expert users (mean= 3.72). Finally, the most interesting difference between these two groups concerns the duration of the task. We globally observed that there was a similar learning effect for all the users, as the completion task improved along the three trials. It is interesting to note, however, that the mean completion time for the expert users was globally the same whatever the metaphor, unlike the case with novice users (see Table 7). We can see that using visual metaphors M A (⊛) and M B (∄) makes the task harder for novice users as they spend more time completing it. Yet it is particularly interesting that not only the use of a popup notification helps the novice users to achieve their task faster (mean = 205 sec), but also that, using this metaphor, the novice users are even faster than the expert users. This difference is not statistically significant (p > 0.05), however.

Novice versus Expert Users

Conclusion

The significant differences on the various variables of this experiment are summed up in Table 6. To conclude, it appears that metaphor M B (∄) was perceived by participants as being the easiest to understand, the best idea, the most original and the most aesthetic. Conversely, metaphor M C ( ) was perceived as the most unpleasant and boring. This metaphor M C ( ) was the fastest one regarding the session duration, however. Thus, depending on the purpose of the application, the metaphor has to be different. On the one hand, for a userfriendly application, a visual metaphor such as M B (∄) would be more suitable. On the other hand, for an application requiring a fast task accomplishment, a pop-up notification in the user interface would be more efficient. Whatever the choice, it should have no consequences for either ease of use or the number of errors made. Finally, it would also be interesting to combine the two metaphors M B (∄) and M C ( ) in order to test if this combination improve or, on the contrary, creates an important workload for the user that complicates his/her work and understanding. The better perception of visual feedback by the participants as witnesses of the exchanges led us to conduct the second experiment to check if the use of visual feedback also helps when the participants trigger their own exchange.

Experiment 2: The User Triggers the Exchange of

His/Her Own Avatar

Objective and Study Design

This second experiment aims at comparing five exchange metaphors to study, if and why one is preferred and provides a more positive user experience. Differently from the previous experiment, participants were now involved in their exchanges as they triggered them. In this experiment, the exchange metaphors were designed with two parameters : the camera motion and the visual feedback. We used two camera motions : a straight linear motion between the two avatars (։) and an external point of view combined with a camera motion ( ). The straight linear motion followed a direct camera trajectory from the participant avatar's perspective to that of his/her new avatar. The external point of view (external-PoV) motion started and ended at the same positions as the previous motion but pauses at an intermediate point, showing both avatars involved in the exchange. The second parameter concerns the visual feedback. We designed metaphors with visual feedback (noted ✚) and others without visual feedback (noted / 0). Metaphors with visual effects used the same feedback defined in the first experiment (Ghost translations + Flickering avatars) in order to provide additional information about the exchange. Combining the camera parameter (։ / ) and the visual feedback parameter (✚ / / 0) gave us four different metaphors : M 1 (։,✚), M 2 (։, / 0), M 3 ( ,✚) and M 4 ( , / 0). In addition to these four metaphors, we added another, M 5 ( / 0, / 0), which used neither camera motions nor visual feedback: the camera was instantly set to the new avatar's perspective. We assumed that this fifth metaphor defined the simplest representation for taking control over a new avatar. Table 8 gives the definitions of these five metaphors. Figure 6 presents a user's view of this experiment. A demonstration video of these metaphors is presented here : http: //youtu.be/Yu4YpGzKXes.

Participants

Forty-two participants (3 females and 39 males, aged from 18 to 63, mean=29.2, sd=9.3) took part in this experiment. They were distributed as presented in Table 9.

Procedure

Each participant was first informed about the complete test proceedings. Then they were asked to complete an identification questionnaire allowing us to collect general information about their demographics, occupation and experience with VR. After that, a demonstration video introduced the five exchange metaphors to them and gave instructions about the task they had to complete. The participants were asked to compare each of the five metaphors two by two which led to a total of ten comparisons. These ten comparisons were presented in a different order for each participant to avoid any undesirable learning effect. The participants completed different questionnaires. First, a questionnaire was filled in after each comparison to collect their preferences between the two compared metaphors. Then, at the end of the experiment, they filled in a final questionnaire to provide more global impressions, comments and subjective judgments.

Collected Data

We first counted the number of times each metaphor was preferred to another. In addition, at the end of the experiment, participants had to fill in a subjective questionnaire on each of the five metaphors with [A] a Likert scale (1: not agree at all, 7: totally agree) for the following criteria: (1) this metaphor is easy to understand, (2) this metaphor is a good idea; and [B] a semantic differential such as: this exchange metaphor is (3) Ordinary versus Original, (4) Boring versus Excitement, and (5) Unpleasant versus Pleasant. Open-ended questions concerning positive and negative aspects as well as suggestions to improve the metaphor where also added in the questionnaire. Finally, at the end of the questionnaire, participants were asked to rank the five metaphors in order of preference and to indicate the metaphor they would retain if they had to design a virtual environment with an exchange of avatars. The significant results obtained are summed up in Table 12 and detailed in the Section 4.3.5.

Results

In this experiment, participants had to test five exchange metaphors. Therefore, we used paired-sample measurement techniques for the statistical analysis. A Test of Normality (i.e., Shapiro Wilk) indicated a significant result (p < 0.05) suggesting a violation of the assumption of normality for all the tested variables, i.e. the population of participants was never normally distributed for the considered variables.

For this reason, we used Friedman and Wilcoxon Signed Rank tests for numerical variables (e.g., mark assigned by the participants to the item "Good idea": scores ranging from 1 to 7) while we used the Chi-Square test for independence for categorical variables (e.g., rank of metaphor: first, second, third, fourth and fifth). In order to facilitate the reading of the results, all Friedman test results showing significant differences are presented in Table 11. Table 10 sums up all of the computed Wilcoxon test values for the different criteria. Most of our results are presented in boxplots (see Fig. 8). These boxplots are delimited by the quartiles (25%-and 75%-quartile) of the distribution of the condition over all the individuals. Moreover, the medians, minima and maxima are represented in each boxplot. Each significant result is explained in a small paragraph where the first bold sentence presents the conclusion and the rest of the paragraph details the tests we used.

Metaphors M 1 (։,✚), M 2 (։, / 0) and M 5 ( / 0, / 0) were globally preferred. Concerning the participants' preferred metaphors, Wilcoxon tests indicated significant differences between M 3 ( ,✚) and the other four metaphors (M 1 (։,✚), M 2 (։, / 0), M 4 ( , / 0) and M 5 ( / 0, / 0)) and also between M 4 ( , / 0) and the four other metaphors. Comparing the number of times each metaphor was preferred by participants, we found that M 3 ( ,✚) and M 4 ( , / 0) were less popular than metaphors M 1 (։,✚), M 2 (։, / 0) and M 5 ( / 0, / 0). The resulting histogram is presented in Figure 7(a). Moreover, the fact that metaphor M 4 ( , / 0) was the least favorite is also confirmed by the question "If you had to design an environment needing an exchange metaphor, which exchange metaphor would you keep?" with a Wilcoxon test that showed significant differences between M 4 ( , / 0) and metaphors M 1 (։,✚), M 2 (։, / 0) and M 5 ( / 0, / 0). This suggests participants would retain metaphors M 5 ( / 0, / 0), M 1 (։,✚) and M 2 (։, / 0) and would not keep the metaphor M 4 ( , / 0) (see Fig. 7(b) for values). The preference for metaphors M 1 (։,✚), M 2 (։, / 0) and M 5 ( / 0, / 0), and the rejection of M 3 ( ,✚) and M 4 ( , / 0) were also corroborated by the final ranking performed by the participants. Indeed, a Chi-Square test for independence indicated a significant association between metaphor and rank ( χ 2 (16, n = 210) = 91.76, p < 0.0005). Figure 7(c) shows that metaphor M 5 ( / 0, / 0) was mainly ranked first, that M 2 (։, / 0) was mainly ranked second and that M 1 (։,✚) was mainly ranked second and third. Metaphors M 3 ( ,✚) and M 4 ( , / 0) were respectively mainly ranked fourth and fifth.

Metaphors M 1 (։,✚), M 2 (։, / 0) and M 3 ( ,✚) were easier to understand than M 4 ( , / 0) and M 5 ( / 0, / 0). Concerning the ease of understanding, a Wilcoxon test indicated significant differences between:

• M 1 (։,✚) and metaphors M 2 (։, / 0), M 4 ( , / 0),M 5 ( / 0, / 0);

• M 2 (։, / 0) and metaphors M 1 (։,✚), M 4 ( , / 0),M 5 ( / 0, / 0);

• M 3 ( ,✚) and metaphors M 4 ( , / 0),M 5 ( / 0, / 0).

Regarding Figure 8(a), this suggests that metaphors M 1 (։,✚), M 3 ( ,✚) and also M 2 (։, / 0) were perceived as easier to understand than metaphors M 4 ( , / 0) and M 5 ( / 0, / 0). Metaphor M 4 ( , / 0) is more boring, unpleasant and a bad idea compared with the other metaphors. Wilcoxon test indicated significant differences between M 4 ( , / 0) and the other four metaphors (for details, see Table 10) suggesting that metaphor M 4 ( , / 0) was less liked by the participants. Figure 8 presents the resulting boxplots for the experiment on the excitement degree (Fig. 8(c)), the pleasant degree (Fig. 8(d)) and whether the metaphor was a good idea (Fig. 8(b)).

Metaphors M 3 ( ,✚), M 1 (։,✚) and M 4 ( , / 0) are more original than metaphors M 2 (։, / 0) and M 5 ( / 0, / 0). Concerning originality, a Wilcoxon test indicated significant differences between M 3 ( ,✚),M 2 (։, / 0) and M 5 ( / 0, / 0) from the four other metaphors. Regarding Figure 8(e), this suggests that M 3 ( ,✚), M 1 (։,✚) and M 4 ( , / 0) were perceived as more original than M 2 (։, / 0) and M 5 ( / 0, / 0) but also that metaphor M 3 ( ,✚) was considered as the most original one.

Novice versus Expert Users

In this experiment, we employed 18 novice and 24 expert users. The novice users showed significant results (p < 0.05) for two criteria: originality and ease of understanding. On these criteria, novice and expert users globally had the same significant differences regarding the metaphors. They notably agreed on the originality of the metaphors, i.e. M 3 ( ,✚) was very original and M 5 ( / 0, / 0) very ordinary. Expert users also showed significant differences for ease of understanding, pleasant degree and whether the metaphor was a good idea or not. On these criteria, they strongly rejected M 4 ( , / 0). Regarding users comments, this was caused by the "loss of reference points" during the "perturbing camera motions" and because M 4 ( , / 0) was "too slow".

Conclusion

Table 12 sums up the significant differences observed on the variables. To conclude, the use of the linear motion (։) of the camera is preferred to the use of the curved motion ( ). Indeed, regarding the participants' comments, the immersion feeling is better with the linear motion as users ''feel" they are moving from one avatar to the other. Moreover, the use of visual feedback helps users to understand the ex-change, as it strengthens the impression of several users in the same environment. Regarding the comments of the participants, these visual effects also helped them to understand that they were not "moving" in the environment but "exchanging" avatars. Some participants felt, however, that the visual feedback distracted them (i.e. some explained that the vivid colors and ghosts attention, causing a of focus on what was happening around). This distraction explains why the same number chose to keep M 1 (։,✚) or M 2 (։, / 0). Finally, the simplest metaphor, M 5 ( / 0, / 0), was the one the mostly ranked first by users. This can be explained by its "execution speed", as underlined by the comments of several participants but also because it was judged as ordinary by the participants (see Fig. 8(e)) who might have been more familiar with its use. This metaphor was judged hard to understand and some participants suggested a learning phase using a metaphor such as M 1 (։,✚) for better understanding of the exchange before the use of M 5 ( / 0, / 0) for the efficiency of the real application. Not surprisingly, these results are in accordance with studies on travel in virtual environments [START_REF] Bowman | Travel in immersive virtual environments: an evaluation of viewpoint motion control techniques[END_REF], as exchange could indeed be seen as a particular case of navigation in a virtual environment.

CONCLUSION

The exchange of avatars opens new perspectives for multi-actor virtual applications, notably in the field of virtual environments for training where several studies reveal that the exchange of avatars is an efficient way to improve the training [START_REF] Raij | Ipsviz: An after-action review tool for humanvirtual human experiences[END_REF][START_REF] Luna | The perceptive puppet: Seamless embodiment exchange between real and virtual humans in virtual environments for training[END_REF]. To our knowledge, however, no study has focused on how to represent an exchange of avatar efficiently. To that end, we proposed two complementary experiments that aim at assessing the crucial parameters that make the representation of an exchange, called an exchange metaphor, more comprehensible to and better perceived by the user. The first experiment focused on exchanges witnessed by the user, whereas the second experiment, focused on exchanges triggered by the user for his/her own avatar. These experiments enable us to offer several recommendations for the design of comprehensible and well-perceived exchange metaphors.

First, the experiments confirmed that different parameters should be taken into account to define the exchange metaphor depending on whether the user is involved or not in the exchange. In both cases, however, the use of visual effects generally helps to explain the exchange mechanism but could distract the user from the task.

Second, several metaphors can be proposed depending on the level of familiarity of the end-user with VR. Comprehensible and familiar metaphors should be proposed to novice users whereas expert users will prefer efficient metaphors. Moreover, a learning phase should be available for novice users to allow them to use more efficient metaphors once they are used to the exchange mechanism.

Finally, metaphors must be adapted to the targeted application: user-friendly metaphors, despite being well-appreciated by users, often lead to a longer task accomplishment time, especially for novice users, even though no difference has been found in terms of either ease of use or exchange awareness. Further, we claim that the metaphor must be adapted to the context of the exchange. An example of such a context-dependent exchange metaphor, based on the distance, is present in the video game Grand Theft Auto 5. Here, a metaphor close to M 5 ( / 0, / 0) is used when avatars are next to each other and a metaphor using the principle of M 4 ( , / 0) is used when characters are distant. We have considered several ways to extend this work. We could, for instance, combine visual feedback with other stimuli, like auditory feedback, in order to improve the exchange metaphors. Finally, we would like to extend our experiment as we strongly believe that depending on conditions the metaphors should also be different. For instance, we could investigate whether the present results would be confirmed in more complex and larger virtual environments. Moreover, we intend to examine the influence of the user's immersion degree or the distance between the avatars involved in the exchange. Regarding the immersion degree of the application, we believe that when the user triggers the exchange, a direct forward camera motion should be preferred to preserve the immersion feeling rather than an instantaneous viewpoint change that could introduce disorientation and sickness.

Fig. 1 .

 1 Fig. 1. Presentation of the metaphors used in experiment 1: the blue expert is exchanging its avatar with the red expert, taking control of the right avatar.

Fig. 2 .

 2 Fig. 2. Environment used in experiment 1.

Fig. 3 .

 3 Fig. 3. Boxplots of the marks attributed to each metaphor in experiment 1.

Fig. 4 .

 4 Fig. 4. Boxplots of the "duration of the task accomplishment" for each metaphor.

Fig. 5 .

 5 Fig. 5. Task duration for the novice and expert users : boxplots of the three trials and mean time.

Fig. 6 .

 6 Fig. 6. Presentation of the environment of the second experimentation: the use can trigger the exchange of his own avatar with any of the three other avatars in the environment.

  (a) Number of times each metaphor has been preferred for all of the comparisons. (b) Metaphor finally selected by participants to represent the exchange (c) Ranking of the metaphor from first to fifth.

Fig. 7 .Fig. 8 .

 78 Fig. 7. The metaphors M 1 (։,✚), M 2 (։, / 0) and M 5 ( / 0, / 0) were globally preferred to M 3 ( ,✚) and M 4 ( , / 0).

Table 1 .

 1 Metaphors Compared in Experiment 1.

Table 2 .

 2 Distribution of the Participants among our Three Experimental Groups for Experiment 1.

	Criteria	M A (⊛)	M B (∄)	M C ( )
	Gender	Man Woman	15 3	16 2	16 2
		15-25	5	6	7
	Age	25-35 35-45	10 2	10 2	10 0
		> 45	1	0	1
		Administration	2	1	0
		Technician	0	1	0
		PhD Student	3	2	4
	Occupation	Other Student	5	5	5
		Post-doctoral	3	2	1
		Engineer	4	6	7
		Lecturer	1	1	1
		None	1	2	2
	VR	Minimal	4	4	4
	Knowledge	Some	6	4	5
		Good	7	8	7

Table 3 .

 3 Tasks Composing the Scenario the Participants had to Perform.

	Task	Required Expert
	Recharge the battery (I)	-
	Replace the engine (C)	Engine Expert
	Check the tire pressure (I)	-
	Replace a front wheel (C)	Wheel Expert
	Change the rear light bulb (I)	-
	Replace the windscreen (C)	Window Expert
	Repair the front bumper (I)	-
	Add oil to the engine (C)	Engine Expert
	Clean the windows (I)	-

A Task is either Individual (I) or Collaborative (C).

Table 4 .

 4 Significant Differences Computed with the Kruskal-Wallis Test.

	Variable	Kruskal-Wallis test
		χ 2 (2, n = 54)	p
	Ease of understanding	8.61	< 0.05
	Good idea	7.31	< 0.05
	Originality	9.87	< 0.05
	Exciting degree	9.23	< 0.05
	Pleasant degree	8.37	< 0.05
	Task duration	9.59	< 0.05

Table 5 .

 5 Significant Differences Computed with the Mann-Whitney Test Between Two Metaphors (p < 0.05).

	Metaphor Comparison	U	p
	Criterion : Ease of understanding
	M B (∄)vs M C ( )	78	< 0.05
	Criterion : Good idea
	M B (∄)vs M C ( )	82.50	< 0.05
	Criterion : Originality
	M A (⊛)vs M B (∄)	91.50	< 0.05
	M B (∄)vs M C ( )	70.50	< 0.005
	Criterion : Excitement degree
	M A (⊛)vs M C ( )	74.50	< 0.005
	M B (∄)vs M C ( )	92.50	< 0.05
	Criterion : Pleasant degree
	M A (⊛)vs M C ( )	91.50	< 0.05
	M B (∄)vs M C ( )	83.50	< 0.05
	Criterion : Task duration
	M A (⊛)vs M C ( )	69	< 0.005
	M B (∄)vs M C ( )	92.50	< 0.05

Table 7 .

 7 Task Duration (in seconds) by User Expertise: Novice Users are Faster than Expert Users with M C ( ).

	Metaphor	Expert Mean	Novice Mean
	M A (⊛)	235	270
	M B (∄)	240	252
	M C ( )	228	205

Table 8 .

 8 Metaphors Compared in Experiment 2.

Table 9 .

 9 Distribution of the Participants by Criteria for Experiment 2.

	Age	N(/42)	Occupation	N(/42)	VR Skills	N(/42)
			PhD Student	11
	15-25	16	Other Student	12	None	3
	25-35	21	Post-doctoral	2	Minimal	10
	35-45	1	Engineer	12	Some	11
	> 45	4	Lecturer	3	Good	18
			Researcher	2

Table 10 .

 10 Results Computed with Wilcoxon's Test: White Cells Indicate a Significant Difference Between the Two Variables (p < 0.05) in Contrast to Gray Cells.

	Metaphor	M 1 (։,✚)	M 2 (։, / 0)	M 3 ( ,✚)	M 4 ( , / 0)
		z	p	z	p	z	p	z	p
				Criterion : Preferred Metaphors
	M 3 ( ,✚)	-3.25	< 0.005	-3.06	< 0.005
	M 4 ( , / 0)	-4.38	< 5.10 -4	-4.83	< 0.005	-3.01	< 0.005
	M 5 ( / 0, / 0)		> 0.05	-3.34	0.005	-2.13	< 0.05	-3.68	< 5.10 -4
				Criterion : Kept Metaphor
	M 4 ( , / 0)	-2.31	< 0.05	-2.11	< 0.05		> 0.05
	M 5 ( / 0, / 0)		> 0.05		> 0.05		> 0.05	-3.15	< 0.005
				Criterion : Ease of understanding
	M 2 (։, / 0)	-2.83	< 0.005
	M 4 ( , / 0)	-5.01	< 5.10 -4	-3.55	< 5.10 -4	-4.34	< 5.10 -4
	M 5 ( / 0, / 0)	-3.95	< 5.10 -4	-2.13	< 0.05	-2.39	< 0.05		> 0.05
				Criterion : Excitement degree
	M 4 ( , / 0)	-3.50	< 5.10 -4	-2.93	< 0.005	-2.47	< 0.05
	M 5 ( / 0, / 0)		> 0.05		> 0.05		> 0.05	-2.90	< 0.005
				Criterion : Pleasant degree
	M 4 ( , / 0)	-2.29	< 0.05	-3.70	< 5.10 -4	-2.86	< 0.005
	M 5 ( / 0, / 0)		> 0.05		> 0.05		> 0.05	-3.34	< 0.005
				Criterion : Good Idea
	M 2 (։, / 0)		> 0.05
	M 3 ( ,✚)		> 0.05		> 0.05
	M 4 ( , / 0)	-3.55	< 5.10 -4	-3.77	< 5.10 -4	-4.14	< 5.10 -4
	M 5 ( / 0, / 0)		> 0.05		> 0.05		> 0.05	-3.13	0.005
				Criterion : Original
	M 2 (։, / 0)	-3.48	0.005
	M 3 ( ,✚)	-3.73	5.10 -4	-4.96	5.10 -4
	M 4 ( , / 0)		> 0.05	-3.83	5.10 -4	-3.73	5.10 -4
	M 5 ( / 0, / 0)	-3.88	5.10 -4	-2.80	0.005	-5.03	5.10 -4	-4.53	5.10 -4

Table 11 .

 11 Significant Differences Computed with the Friedman's Test for Each Variable.

	Variable	Friedman values
		χ 2 (4, n = 42)	p
	"Preferred metaphor"	44.24	< 5.10 -4
	"Kept metaphor"	11.10	< 0.05
	Ease of understanding	45.43	< 5.10 -4
	Excitement degree	16.42	< 0.005
	Pleasant degree	16.62	< 0.005
	Good idea	22.17	< 5.10 -4
	Originality	68.138	< 5.10 -4

Table 12 .

 12 Categorization of the Relevance of Each Metaphor by Significant Difference (+ Rated Significantly Higher, -Rated Significantly Lower, 0 No Significant Difference).

		Preferred Easier to understand	Excitement Pleasant	Good idea More original
	M 1 (։,✚)	+	++	+	+	+	+
	M 2 (։, / 0)	+	+	+	+	+	-
	M 3 ( ,✚)	-	+	+	+	+	++
	M 4 ( , / 0)	-	-	-	-	-	+
	M 5 ( / 0, / 0)	+	-	+	+	+	--

http://www.rockstargames.com/V/

ACKNOWLEDGMENTS

This work was supported by the French Research National Agency project named CORVETTE (ANR-10-CONTINT-CORD-012) and by the French Unique Interdepartmental Funds SIFORAS (FUI 11).