Bertrand Charpentier
email: charpent@in.tum.de

Thomas Bonald
email: thomas.bonald@telecom-paristech.fr

Tree Sampling Divergence: An Information-Theoretic Metric for Hierarchical Graph Clustering

We introduce the tree sampling divergence (TSD), an information-theoretic metric for assessing the quality of the hierarchical clustering of a graph. Any hierarchical clustering of a graph can be represented as a tree whose nodes correspond to clusters of the graph. The TSD is the Kullback-Leibler divergence between two probability distributions over the nodes of this tree: those induced respectively by sampling at random edges and node pairs of the graph. A fundamental property of the proposed metric is that it is interpretable in terms of graph reconstruction. Specifically, it quantifies the ability to reconstruct the graph from the tree in terms of information loss. In particular, the TSD is maximum when perfect reconstruction is feasible, i.e., when the graph has a hierarchical structure and can be reconstructed exactly from the corresponding tree.

Another key property of TSD is that it applies to any tree, not necessarily binary. In particular, the TSD applies to trees of height 2, corresponding to the case of usual clustering (not hierarchical) whose output is a partition of the set of nodes. The TSD can thus be viewed as a universal metric, applicable to any type of clustering. Moreover, the TSD can be used in practice to compress a binary tree while minimizing the information loss in terms of graph reconstruction, so as to get a compact representation of the hierarchical structure of a graph. We illustrate the behavior of TSD compared to existing metrics on experiments based on both synthetic and real datasets.

Introduction

Many datasets have a graph structure. Examples include infrastructure networks, communication networks, social networks, databases and co-occurence networks, to quote a few. These graphs often exhibit a complex, multi-scale structure where each node belong to many groups of nodes, so-called clusters, of different sizes [START_REF] Caldarelli | Large scale structure and dynamics of complex networks: from information technology to finance and natural science[END_REF].

Hierarchical graph clustering is a common technique for the analysis of the multi-scale structure of large graphs. Rather than looking for a simple partition of the set of nodes, as in usual clustering techniques, the objective is to represent the graph by some rooted binary tree, whose leaves are the nodes of the graph. This tree can then be used to find relevant clusterings at different resolutions by suitable cuts at different levels of the tree.

While many hierarchical graph clustering algorithms have recently been proposed, see for instance [Newman, 2004;[START_REF] Pons | [END_REF][START_REF] Sales-Pardo | [END_REF][START_REF] Clauset | [END_REF][START_REF] Lancichinetti | [END_REF][START_REF] Huang | [END_REF][START_REF][END_REF][START_REF] Tremblay | Graph wavelets for multiscale community mining[END_REF]Bateni et al., 2017;[START_REF] Bonald | [END_REF], it proves very difficult to evaluate their performance due to the absence of public datasets of graphs with ground-truth hierarchy. A natural approach is then to define some quality metric based on the graph itself, just like modularity is a popular metric for assessing the quality of a simple clustering [Newman and Girvan, 2004].

A cost function has recently been proposed by Dasgupta [Dasgupta, 2016] to assess the quality of a hierachical clustering and has been further analysed and extended in [START_REF] Roy | Aurko Roy and Sebastian Pokutta. Hierarchical clustering via spreading metrics[END_REF]Cohen-Addad et al., 2017;[START_REF] Cohen-Addad | [END_REF]; it can be viewed as the expected size of the smallest cluster encompassing two nodes sampled at random from the edges of the graph.

In this paper, we assess the quality of a hierarchical clustering through the Kullback-Leibler divergence between two probability distributions over the nodes of the tree: those induced respectively by sampling clusters encompassing random edges and node pairs of the graph. We refer to this metric as Tree Sampling Divergence (TSD). If the tree captures the hierarchical structure of the graph, the TSD tends to be large since most edges are sampled from nodes belonging to small clusters of the graph (i.e., deep nodes of the tree), whereas most node pairs, sampled independently, belong to large clusters of the graph (i.e., shallow nodes of the tree, close to the root).

A fundamental property of the proposed metric is that it is interpretable in terms of graph reconstruction. Specifically, it quantifies the ability to reconstruct the graph from the tree. In particular, the TSD is maximum when perfect reconstruction is feasible, i.e., when the graph has a full hierarchical structure and can be reconstructed exactly from the corresponding tree. While a similar property has been proved in [START_REF] Cohen-Addad | [END_REF] for Dasgupta's cost, this applies only to a graph that has a full hierarchical structure, when perfect reconstruction is possible; there is no interpretation in terms of graph reconstruction for an arbitrary graph. The TSD quantifies the gap to perfect reconstruction for any graph: this gap is exactly the information lost in the reconstruction of the graph.

Another key property of TSD is that it applies to any tree, not necessarily binary. In particular, the TSD applies to trees of height 2, corresponding to the case of usual clustering (not hierarchical) where the output is a partition of the set of nodes. The TSD can thus be viewed as a universal metric, applicable to any type of clustering. Moreover, the TSD can be used in practice to compress a binary tree while minimizing the information loss in terms of graph reconstruction, so as to get a compact representation of the hierarchical structure of a graph.

The paper is structured as follows. We first introduce in sections 2 and 3 the notions of graph sampling and graph distance, which play a key role in our approach. The Tree Sampling Divergence (TSD) is presented in section 4. In section 5, we show how to compute the TSD in practice through graph aggregation. The properties of the TSD in terms of graph reconstruction are presented in section 6. The case of general trees is considered in section 7, the practically interesting case of flat clustering (trees of height 2) being presented in section 8. Some extensions of the TSD are described in section 9. The behavior of the TSD is illustrated by experiments on both synthetic and real data in section 10. Section 11 concludes the paper.

Graph sampling

Consider a weighted, undirected, connected graph G = (V, E) of n nodes and m edges. Let w(u, v) be equal to the weight of edge u, v, if any, and to 0 otherwise. We refer to the weight of node u as:

w(u) = v∈V w(u, v).
We denote by w the total weight of nodes:

w = u∈V w(u) = u,v∈V w(u, v).
These weights induce two ways to sample the graph.

Edge sampling. Sampling edges at random in proportion to their weights yields the following joint probability distribution on V :

∀u, v ∈ V, P (u, v) = w(u, v) w .
This distribution is symmetric in the sense that:

∀u, v ∈ V, P (u, v) = P (v, u).
Observe that the graph G is fully characterized by its edge sampling distribution P and its total weight w, since the weight of edge u, v is given by w(u, v) = wP (u, v).

Node sampling. Sampling nodes at random in proportion to their weights yields the following probability distribution on V :

∀u ∈ V, P (u) = w(u) w .
This is the marginal distribution of the edge sampling distribution:

∀u ∈ V, P (u) = v∈V P (u, v)
Observe that the graph structure cannot be recovered from the node sampling distribution. The best reconstruction given this distribution and the total weight w consists in assigning the weight wP (u)P (v) to edge u, v. Following Newman [Newman and Girvan, 2004], we refer to this graph as the null model associated to graph G.

Graph distance

We have seen that any graph is characterized by its edge sampling distribution and its total weight. Thus the edge sampling distribution can be used to define a distance between two graphs, up to some multiplicative constant on the edge weights. Specifically, let G 1 , G 2 be two graphs over the same set of nodes V and denote by P 1 , P 2 the corresponding edge sampling distributions. We define the distance between G 1 and G 2 by the Kullback-Leibler divergence between P 1 and P 2 , that is:

D(G 1 , G 2 ) = D(P 1 ||P 2 ) = u,v∈V P 1 (u, v) log P 1 (u, v) P 2 (u, v) .
Observe that, like the Kullback-Leibler divergence, this distance is not symmetric. The graphs G 1 and G 2 are equivalent for this distance, in the sense that D(G 1 , G 2 ) = 0, if and only if P 1 = P 2 , i.e., edge weights are equal up to a multiplicative constant.

The above distance can be used to quantify the difference between the graph G and its null model. This distance is:

I = u,v∈V P (u, v) log P (u, v) P (u)P (v) , (1)
the mutual information between nodes when sampled from the edges. This is a simple yet meaningful metric to quantify the clustering structure of the graph: if nodes are organized in clusters, the mutual information between two nodes u, v sampled from an edge is expected to be large (given node u, you get information on the other node v); on the other hand, if the graph has no clustering structure (e.g., a complete graph), then the mutual information between two nodes u, v sampled from an edge is small (given node u, you have little information on the other node v; this information is null for a complete graph). We shall see in section 6 that the mutual information I is directly related to our metric: this is the maximum value of the TSD, which is attained by a tree if and only if perfect graph reconstruction from this tree is feasible.

Consider some hierarchical clustering of a graph, represented as a rooted binary tree whose leaves are the nodes of the graph. For any u, v ∈ V , we denote by u ∧ v the closest common ancestor of leaves u and v in the tree.

Let T be the set of nodes of the tree. Note that V ⊂ T and |T | = 2n -1. The graph sampling distributions introduced in section 2 induce the following probability distributions on

T : ∀x ∈ T, p(x) = u,v:u∧v=x P (u, v),
and ∀x ∈ T, q(x) = u,v:u∧v=x

P (u)P (v).
The former is that induced by edge sampling while the latter is that induced by independent node sampling. Equivalently, these are the distributions induced by edge sampling for the original graph and the null model, respectively. We expect these distributions to differ significantly if the tree indeed represents the hierarchical structure of the graph. Specifically, we expect p to be mostly concentrated on deep nodes of the tree (far from the root), as two nodes u, v connected with high weight w(u, v) in the graph typically belong to a small cluster, representative of the clustering structure of the graph; on the contrary, we expect q to be concentrated over shallow nodes (close to the root) as two nodes u, v sampled independently at random typically belong to large clusters, less representative of the clustering structure of the graph. This motivates the following metric for the quality of the tree T as hierarchical structure of the graph:

Q = x∈T p(x) log p(x) q(x) .
(2) This is the Kullback-Leibler divergence 1 between the probability distributions p and q. The larger the divergence, the better the tree for representing the graph. In the following, we refer to this metric as the Tree Sampling Divergence (TSD). We shall see in section 6 that the quantity I -Q, with I given by (1), can be interpreted in terms of information loss in the problem of graph reconstruction from the tree.

Graph aggregation

The sampling distributions p, q can be simply computed by graph aggregation (see Algorithm 1). The algorithm consists in iteratively merging two nodes u, v of the graph that are leaves of the tree into a single node x = u ∧ v, their common parent in the tree. This node has weight:

w(x) = w(u) + w(v),
and a self-loop with weight:

w(x, x) = w(u, u) + w(v, v) + 2w(u, v)
1 Note that Q is finite since the support of q is T (because P (u) > 0 for each u ∈ V ).

in the aggregate graph. We get the sampling probabilities of node x ∈ T as:

p(x) = w(x, x) w , q(x) = w(x) w 2 ,
and the TSD follows from (2).

Algorithm 1: Computation of TSD (binary trees) Input: Graph G = (V, E) with sampling distribution P ; Tree T Output: Tree sampling distributions p, q 1 for x ∈ V do 2 p(x) ← P (x, x); q(x) ← P (x) 2

+ P (v, v) + 2P (u, v) 11 P (x) ← P (u) + P (v) // update p, q 12 p(x) ← P (x, x); q(x) ← P (x) 2 // update T 13 T ← T \ {u, v}

Graph reconstruction

We consider the problem of graph reconstruction from the tree. Specifically, given the tree T and the weights of nodes, we would like to build some graph Ĝ that is as close as possible to G. The hierarchical clustering can then be viwed as the latent representation of the graph G in the auto-encoding process:

G → T → Ĝ. We first need to define the decoding scheme, that is the process to build some graph Ĝ from the tree T . To do this, we assign some weight σ(x) to each node x ∈ T \ V . This corresponds to the weight of cluster x and will be determined so as to minimize the distance between the original graph G and its reconstruction Ĝ. We let the weight of edge u, v in graph Ĝ equal to:

ŵ(u, v) = w(u)w(v)σ(u ∧ v).
Thus the weight of edge u, v is proportional to the respective weights of nodes u, v and to the weight of their smallest common cluster u ∧ v, as given by the tree.

It remains to find the cluster weights σ that minimize the distance between the original graph G and its reconstruction Ĝ. For this, we use the graph distance defined in section 3, corresponding to the Kullback-Leibler divergence between the corresponding edge sampling distributions, P and P . Observe that:

P (u, v) = CP (u)P (v)σ(u ∧ v),
with:

C =   u,v∈V P (u)P (v)σ(u ∧ v)   -1
.

We obtain:

D(G, Ĝ) = D(P || P ), = u,v∈V P (u, v) log P (u, v) P (u, v) , = u,v∈V P (u, v) log P (u, v) P (u)P (v) - u,v∈V P (u, v) log σ(u ∧ v) + log   u,v∈V P (u)P (v)σ(u ∧ v)   , = I -J,
where I , given by ( 1), is the mutual information between nodes when sampled from the edges and

J = u,v∈V P (u, v) log σ(u ∧ v) -log   u,v∈V P (u)P (v)σ(u ∧ v)   , = x∈T p(x) log σ(x) -log x∈T q(x)σ(x) .
Observe that I is independent of P so that J is the quantity to be maximized. Finding where the derivative of J with respect to σ(x) is equal to 0 yields:

p(x) σ(x) = q(x) α with α = x∈T q(x)σ(x).
We get:

∀x ∈ T, σ(x) = α p(x) q(x) .
For this optimal value of σ, we obtain:

J = x∈T p(x) log p(x) q(x) ,
which is equal to Q, the tree sampling divergence. Finally, the optimal reconstruction of the graph corresponds to the sampling distribution:

P (u, v) ∝ P (u)P (v) p(u ∧ v) q(u ∧ v)
and the distance between the original graph G and its optimal reconstruction G is:

D(G, G ) = D(P ||P ) = I -Q.
We deduce that the information loss in the optimal autoencoding process G → T → G is I -Q. In particular, Q ≤ I, with equality if and only if perfect reconstruction from the tree T is possible.

Tree compression

While existing quality metrics are typically defined for binary trees (see for instance Dasgupta's cost and extensions in [Cohen-Addad et al., 2017]), the TSD equally applies to general trees. The definition is exactly the same. As for the computation, Algorithm 1 applies except that the aggregation must be applied simultaneously to all leaves of the tree having the same parent (see Algorithm 2).

Algorithm 2: Computation of TSD (general trees) Input: Graph G = (V, E) with sampling distribution P ; Tree T Output: Tree sampling distributions p, q 1 for x ∈ V do 2 p(x) ← P (x, x); q(x) ← P (x) 2 // update p, q 12 p(x) ← P (x, x); q(x) ← P (x) 2 // update T 13 T ← T \ S This is a very interesting property as dense trees are sought in practice, the information provided by a binary tree being to rich to be directly exploited by data scientists or engineers. Moreover, it provides a way to compress a binary tree in an optimal way, by minimizing the information loss caused by tree compression. In view of (2), the information loss caused by the merge of cluster x ∈ T (internal node of the tree) with its parent y is: ∆(x, y) = (p(x) + p(y)) log p(x) + p(y) q(x) + q(y)

-p(x) log p(x) q(x) -p(y) log p(y) q(y) .

Observe that the merge of x and y does not modify the edge sampling distributions on the other nodes of the tree. In particular, the information loss ∆(x, y) can be computed for all branches of the tree, with a complexity in O(n) given p and q, and successive merges be done in increasing order of these information losses. The stopping criterion may be related to some target number of internal nodes in the tree, or some maximum total information loss.

Graph clustering

Since the TSD applies to any tree, it applies in particular to trees of height 2, corresponding to usual graph clustering (i.e., a partition of the nodes).

Let C 1 , . . . , C K be K clusters, forming a partition of V . This can be represented as a tree of height 2, with k internal nodes x 1 , . . . , x K at level 1 (the clusters) and n leaves at level 2 (the nodes of the graph). For each cluster k = 1, . . . , K, we have:

p(x k ) = u,v∈C k P (u, v) = w k w ,
where

w k = u,v∈C k w(u, v)
denotes the internal weight of cluster k (total weight of edges within the cluster). Similarly,

q(x k ) = u∈C k P (u) 2 = W k w 2 , where W k = u∈C k w(u)
denotes the weight of cluster k (total weight of nodes in the cluster). Assuming that there are no self loops, we get for the root, which we denote by 0,

p(0) = 1 - K k=1 p(x k ), q(0) = 1 - K k=1 q(x k ).
Thus the TSD takes the form:

Q = K k=1 w k w log ww k W 2 k + 1 - K k=1 w k w log 1 - K k=1 w k w 1 - K k=1 W k w 2 .
This is a novel metric for evaluating the quality of a clustering, different from modularity [Newman and Girvan, 2004], the usual metric given by:

M = K k=1 p(x k ) - K k=1 q(x k ) = K k=1 w k w - K k=1 W k w 2 .
The key property of the TSD is that it quantifies the ability to reconstruct the graph in terms of information loss; this applies to any tree and thus to usual graph clustering as well. There is no such interpretation with modularity.

Extensions

The TSD can be extended in several ways. First, the node pair sampling distribution q can be replaced by the uniform distribution (i.e., the null model is the complete graph). This boils down to the initialization P (x) ← 1 n for all x ∈ V before applying Algorithm 1 or 2. Second, the Kullback-Leibler divergence can be replaced by some other divergence, like the square Euclidean distance between the probability measures, x∈T (p(x) -q(x)) 2 . The experiments presented below suggest however that it is preferable to use the Kullback-Leibler divergence.

Experiments

The Python code and the datasets used for the experiments are available online 2 . Graph representation. We first show how TSD is able to detect the quality of a tree in terms of graph representation. For this, we generate two noisy versions of the same graph, say G 1 and G 2 , and return the corresponding trees, say T 1 and T 2 , by the hierarchical clustering algorithm described in [START_REF] Bonald | [END_REF]. We then assess the ability of TSD to identify the best tree associated to each graph (e.g., T 1 should be better than T 2 for graph G 1 ). The classification score (in proportion of correct answers) is given in Table 1 for two metrics, TSD and Dasgupta's cost. Each classification score is based on 1000 samples of the graphs G 1 and G 2 ; the original graph G, generated at random from a random hierarchy, has 100 nodes and average degree 10; the two graphs G 1 and G 2 are derived from G by replacing some edges at random (the higher the noise, the easier the classification task).

Noise

2% 5% 10% TSD 64% 82% 94% Dasgupta's cost 59% 72% 86% Graph reconstruction. Next, we show how TSD captures the quality of a tree in terms of graph reconstruction. To this end, we consider a hierarchical stochastic block model (HSBM) of 80 nodes and 3 levels of hierarchy (binary tree with leaves corresponding to clusters of 10 nodes) with different parameters, see [Lyzinski et al., 2017]. For each graph, we apply various graph clustering algorithms, so as to get hierarchies of different qualities. The reconstruction procedure is that described in section 6.

Figure 1 shows the quality of the reconstruction for usual scores (detailed below) with respect to the quality / cost of the hierarchy, for three metrics: TSD, Dasgupta's cost, and the version of the TSD based on the Euclidean distance, we refer to as the Euclidean divergence (see section 9). The results suggest that TSD is the best metric in terms of graph reconstruction, with a clear correlation between the metric and the reconstruction scores. The correlation is also present but more noisy for Dasgupta's cost; there is no correlation with the Euclidean divergence.

2 See https://github.com/sharpenb/Tree-Sampling-Divergence. The quality of the reconstruction is based on the following classical scores [START_REF] Bordes | [END_REF][START_REF] Nickel | Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representations[END_REF][START_REF] Nickel | [END_REF][START_REF] Bojchevski | Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking[END_REF]. First, keeping all edges of the reconstructed graph whose weight is larger than some threshold provides a set of graphs with different false positive and false negative rates, from which we get the Area Under ROC Curve (AUC) and the Average Precision Score (APS). Second, we compute the rank of each edge of the original graph among all possible edges ending in one of the two nodes in the reconstructed graph, in decreasing order of weights. This rank score is averaged over all nodes and normalized by the number of nodes to get a score between 0 and 1; the lower the rank, the better the reconstruction.

Tree compression. Next, we show the pratical interest of TSD in terms of tree compression. We consider Open-Flights 3 , a weighted graph of 3,092 nodes and 18,193 edges representing flights between the main airports of the world. We first apply the hierarchical clustering algorithm described in [START_REF] Bonald | [END_REF] then apply the algorithm described at the end of section 7 to compress the resulting tree with minimum information loss. Specifically, we merge 3, 000 levels among the 3, 092 levels of the original binary tree. The results are shown in Figure 2, together with a clustering derived from this compressed tree. We observe that the compressed tree still captures the hierarchical structure of the graph, despite the very high compression rate applied here (only 3% of the hierarchical levels are retained). The compressed tree is clearly much easier to exploit in practice than the original tree.

Conclusion

We have presented a novel quality metric for hierarchical graph clustering. This metric, inspired by information theory, reflects the ability to reconstruct the initial graph from a hierarchy representing this graph. It is applicable to general trees (not only binary trees) and can be used for tree compression.

3

  while |V | > 1 do 4 u, v ← leaves of the tree T , with common parent x // aggregate nodes u, v into x 5 V ← V \ {u, v}; V ← V ∪ {x} // update P 6 for y neighbor of u or v do 7 if y = x then 8 P (x, y) ← P (u, y) + P (v, y); P (y, x) ← P (x, y) 9 else 10 P (x, x) ← P (u, u)

3P

  while |V | > 1 do 4 S ← leaves of the tree T , with common parent x // aggregate nodes S into x 5 V ← V \ S; V ← V ∪ {x} // update P 6 for y neighbor of a node in S do 7 if y = x then 8 P (x, y) ← u∈S P (u, y); P (y, x) ← P (x, y) (x, x) ← u,v∈S P (u, v) 11 P (x) ← u∈S P (u)

Figure 1 :

 1 Figure 1: Reconstruction scores against quality / cost metrics.

  3 https://openflights.org

Figure 2 :

 2 Figure 2: Tree compression on the Openflights graph.

Table 1 :

 1 Classification scores.


Christophe Moy
email: christophe.moy@univ-rennes1.fr

Lilian Besson
email: lilian.besson@centralesupelec.fr

Decentralized Spectrum Learning for IoT Wireless Networks Collision Mitigation

Keywords: Internet of Things, IoT, machine learning, radio spectrum, collision mitigation, interference, LoRa, artificial intelligence, LoRaWAN, cognitive radio

This paper describes the principles and implementation results of reinforcement learning algorithms on IoT devices for radio collision mitigation in ISM unlicensed bands. Learning is here used to improve both the IoT network capability to support a larger number of objects as well as the autonomy of IoT devices. We first illustrate the efficiency of the proposed approach in a proof-of-concept based on USRP software radio platforms operating on real radio signals. It shows how collisions with other RF signals present in the ISM band are diminished for a given IoT device. Then we describe the first implementation of learning algorithms on LoRa devices operating in a real LoRaWAN network, that we named IoTligent. The proposed solution adds neither processing overhead so that it can be ran in the IoT devices, nor network overhead so that no change is required to LoRaWAN. Real life experiments have been done in a realistic LoRa network and they show that IoTligent device battery life can be extended by a factor 2 in the scenarios we faced during our experiment.

I. INTRODUCTION

Future Internet of Things (IoT) networks are expected to be used all around the world by thousands of devices with various wireless standards and abilities. In wireless IoT networks, and in particular in Low Power Wide Area Networks (LPWAN) operating in the unlicensed bands, the spectrum is shared by many end-devices without any coordination, neither between devices, nor between LPWAN networks themselves. This provokes collisions that could dramatically limit the promises expected for IoT applications. As a consequence, IoT wireless networks require to move towards smarter decentralized frequency resource allocation solutions. However, what will happen is hardly predictable at the expected scale of IoT devices life, which should be up to ten years. Due to both their extremely low cost and complexity requirements, IoT devices require distributed computational and energy efficient solutions that operate without any prior information, and that can deal with uncertainty. The aim of this article is to assess the potential benefit of reinforcement learning (RL) and especially of the Multi-Armed Bandit (MAB) framework, as a solution to the frequency allocation challenges arising in IoT networks.

We propose to show in this paper the theoretical foundation of this approach, and prove its viability at two levels in order to make IoT devices mitigate collisions with other Radio Frequency (RF) signals present in the ISM (Industrial Scientific and Medical) unlicensed band. The first step consists in a PoC (Proof-of-Concept) with a demonstrator running on real radio signals in laboratory conditions. Software Defined Radio (SDR) platforms are used here, and as far as we know it is the first implementation on real radio signals of learning running on the IoT devices side. The second step constitutes the first implementation of learning algorithms on devices deployed in a real LoRa network. The proposed implementation runs in the 868 MHz band, but could be used in any other ISM band, whatever the country. Any other IoT LPWAN (Low Power Wide Area Network) standard than LoRa could be targeted, as soon as channel assignation is not imposed by a central node in the network. We named IoTligent this decentralized (i.e., on device) and uncoordinated (devices do not communicate with each other) learning approach.

The rest of the article is organized as follows. The next section exposes the issue we target in this work and the corresponding hypotheses. Section II reminds the foundation of learning algorithms used in our appraoch. Then Section III details the IoT proof-of-concept design that has been done with USRP platforms, named MALIN. Section IV explains how this has been done in a real LoRa network using Pycom devices. Implementation details are given in Section V and finally Section VI gives results of experiments done in a real deployed LoRa network in the city of Rennes, France.

I. ISSUE, HYPOTHESES AND DECENTRALIZATION PROS

A. Collisions vs autonomy

The possibility of suffering from collisions is the main drawback of IoT in terms of battery autonomy at the first level, but also of IoT viability itself in the ISM bands. Indeed collisions may cause (many) retransmissions at the cost of an increase of the RF contention, and may lead to a lower battery lifetime. Even worse, this could derive to a total failure of the IoT device, either because it cannot succeed in sending data to the network, or because multiple repetitions could make it consume all its energy.

B. Analysis of collisions

Radio collisions will be the weak point of LPWAN It is also important to note that each IoT standard indeed uses its own rules for channeling, bandwidth, user repartition, etc. Therefore, all this leads to an heratic use of spectrum that cannot be planned, and has to be learnt « in vivo ». However, unlicensed band does not mean un-ruled band (duty cycle, power limit, etc), but they are more exposed to the non-respect of these few rules as regulation is relaxed and thus, controls as well.

C. A device-side solution for spectrum management

Our learning approach imposes no change on a normal IoT protocol (as for instance LoRaWAN [START_REF] Sornin | LoRaWAN specification[END_REF]): no extra retransmission, no extra-power to be sent, no data to be added in frames, etc. The only condition is that the proposed solution should work with the acknowledged mode for IoT. The underlying hypothesis is that "channels" (there are no official channels in ISM bands) occupancy by surrounding radio signals (IoT or not) is not equally balanced. In other words, some ISM sub-bands are less occupied or jammed than others, but it is not possible to predict it in time and space, so it has to be learnt on the fly.

The considered learning algorithm is a kind of artificial intelligence (AI) algorithm that is compatible with the IoT device low complexity, as we explain below. It is indeed much more efficient to implement radio collision mitigation approaches on the device side, as devices may be quite far away from gateways, and suffer from different radio and jamming/co-existence conditions. But they are the place where every Watt counts at transmission, and where sensitivity should be the best at reception, as no extraprocessing can be afforded.

D. Advantages of the proposed solution

The proposed approach is based on reinforcement learning algorithms such as those already studied [START_REF] Jouini | Upper Confidence Bound Based Decision Making Strategies and Dynamic Spectrum Access[END_REF] and experimented on real radio signals for Cognitive Radio and especially Opportunistic Spectrum Access (OSA) [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF]. We assert that, as for OSA, the IoT spectrum access issue can be modeled as a Multi-Armed Bandit (MAB) problem. Reinforcement learning is based on a feedback loop that gives a success measure of experience. In the IoT context, we propose to use the acknowledgement (ACK) sent by the gateway to the IoT device as a binary reward. Every device aims at maximizing its transmission success rate, or equivalently, at maximizing its cumulated reward.

The main advantages of our solution are:

 this algorithm has mathematical proofs of convergence,  proofs are verified in real radio conditions, thanks to the good matching between the model and reality,  learning converges effectively very fast in real experiments, thus it is adequate for radio applications [START_REF] Moy | Reinforcement Learning Real Experiments for Opportunistic Spectrum Access[END_REF],  implementation and execution both require very low processing and memory overhead, so that it is possible to add the proposed appraoch in IoT devices for a negligible money cost, negligible complexity (processing, hardware, memory) and no extra-energy consumption overhead,  learning starts from scratch, so there is no need for any prior knowledge at the beginning (and loose some time to acquire this knowledge),  using such learning algorithm will never give worse results than a state-of-the-art random solution, even before learning brings some advantage, for instance at the very beginning of the learning process [START_REF] Bonnefoi | Multi-Armed Bandit Learning in IoT Networks: Learning helps even in nonstationary settings[END_REF].

Hence we argue that the proposed approach can adapt to any kind of radio context, and we also note that:  the stationarity of the environment is a requirement for the proofs of convergence, but if conditions change, convergence is so fast that a simple solution consist in reseting learning from time to time [START_REF] Bonnefoi | Multi-Armed Bandit Learning in IoT Networks: Learning helps even in nonstationary settings[END_REF] (note that there also exist adaptive versions),  no coordination is required between devices, but benefits decrease with the number of devices using the proposed solution, when it represents a great majority of devices (see solutions in [6][7]),  as soon as a device is planned to receive an acknowledgment, no overhead is added neither in terms of protocol nor extra bits to be put into the LoRaWAN frames in uplink or downlink.

II. REINFORCEMENT LEARNING

We model the IoT wireless spectrum issue as a Multi-Armed Bandit (MAB) problem and we propose to use bandit algorithms at the IoT device side to solve this issue.

A. System model

We consider the system model presented in Fig. 1, where a set of object sends uplink packets to the network gateway. The communication between IoT devices and this gateway is done through a simple pure ALOHA-based protocol, where devices transmit uplink packets of fixed duration whenever they want. The devices can transmit their packets in K  2 channels. In the case where the gateway receives an uplink in one channel, it transmits an acknowledgement to the enddevice in the same channel, after a fixed delay. These communications operate in unlicensed ISM bands, and consequently, as stated in previous section, suffer in particular from interferences generated by uncoordinated neighboring networks. This interfering traffic is uncontrolled, and can be unevenly distributed over the K different channels.

We consider the network from the point of view of one IoT device. Every times the end-user has to communicate with the gateway (at each transmission t  1, t ∈ ℕ), it has to choose one channel , denoted as C(t) = k ∈ {1, . . . , K}. Then, the IoT device starts to wait in this channel C(t) for an acknowledgement sent by the gateway. Before sending another message (i.e., at time t + 1), the IoT device knows if it received or not this ACK message. For this reason, selecting the channel (or arm) k at time t yields a (random) feedback, called a reward, rk(t) ∈ {0, 1}, being 0 if no ACK was received before the next message, or 1 if ACK was successfully received. The goal of the IoT device is to minimize its packet loss ratio, or equivalently, it is to maximize its cumulative reward, as it is usually done in MAB problems [START_REF] Thompson | On the likelihood that one unknown probability exceeds another in view of the evidence of two samples[END_REF][9] [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF] :

𝑟 … ∶= ∑ 𝑟 ( ) (𝑡) (1)
This problem is a special case of the so-called "stochastic" MAB, where the sequence of rewards drawn from a given arm k is assumed to be i.i.d., under some distribution νk, that has a mean µk. Several types of reward distributions have been considered in the literature, for example distributions that belong to a one-dimensional exponential family (e.g., Gaussian, Exponential, Poisson or Bernoulli distributions). Rewards are binary in our model, and so we consider only Bernoulli distributions, in which rk(t) ∼ Bern(µk), that is, rk(t) ∈ {0, 1} and ℙ(rk(t) = 1) = µk ∈ [0, 1]. Contrary to many previous work done in the cognitive radio field (for instance in Opportunistic Spectrum Access [START_REF] Jouini | Upper Confidence Bound Based Decision Making Strategies and Dynamic Spectrum Access[END_REF]), the reward rk(t) does not come from a sensing phase before sending the t-th message, as it would do for any "listen-before-talk" model. Rewards come from receiving an acknowledgement from the gateway, between the t-th and t+1-th messages. The problem parameters µ1, ..., µK are of course unknown to the IoT device, so to maximize its cumulated reward, it must learn the distributions of the channels, in order to be able to progressively focus on the best arm (i.e., the arm with largest mean). This requires to tackle the so-called exploration-exploitation dilemma: a player (here, an IoT device) has to try all arms a sufficient number of times to get a robust estimate of their qualities, while not selecting the worst arms too many times.

Before discussing the relevance of a MAB model for our IoT application, we present two bandit algorithms, UCB1 and Thompson Sampling, which are both known to be efficient for stationary i.i.d. rewards and are shown below to be useful in our IoT application.

B. The UCB1 algorithm

A first naive approach could be to use an empirical mean estimator of the rewards for each channel, and select the channel with the highest estimated mean at each time; but this "greedy" approach is known to fail dramatically [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF]. Indeed, with this policy, the selection of arms is highly dependent on the first draws: if the first transmission in one channel fails and the first one on other channels succeed, the end-user will never use the first channel again, even it is the best one (i.e., the most available, in average).

Upper Confidence Bounds (UCB) algorithms instead use a confidence interval on the unknown mean µk of each arm, which can be viewed as adding a "bonus" exploration to the empirical mean. They follow the "optimism-in-face-ofuncertainty" principle: at each step, they play according to the best model, as the statistically best possible arm (i.e., the highest upper confidence bound) is selected. More formally, for one IoT device, we denote by

𝑁 (𝑡) = ∑ 1(𝐶(𝜏) = 𝑘) (2)
the number of times channel k was selected up-to time t  1. The empirical mean estimator of channel k is defined as the mean reward obtained by selecting it up to time t,

𝜇 (𝑡) = (1 𝑁 (𝑡) ⁄ ) ∑ 𝑟 (𝜏) 1(𝐶(𝜏) = 𝑘) (3)
For UCB1, the confidence term is

𝐴 (𝑡) = 𝛼 log(𝑡) 𝑁 (𝑡) ⁄ (4)
And the upper confidence bound is the sum of the confidence term and the empirical mean,

𝐵 (𝑡) = 𝜇 (𝑡) + 𝐴 (𝑡) (5)
which is used by the end-user to decide the channel for communicating at time step t + 1:

𝐶(𝑡 + 1) = arg max 𝐵 (𝑡) (6)
UCB1 is called an index policy. The UCB1 algorithm uses a parameter α > 0, originally α was set to 2 [START_REF] Bubeck | Regret analysis of Stochastic and Non-Stochastic Multi-Armed Bandit Problems[END_REF], but empirically α = 1/2 is known to work better (uniformly across problems), and α  1/2 is advised by the theory [START_REF] Bubeck | Regret analysis of Stochastic and Non-Stochastic Multi-Armed Bandit Problems[END_REF]. This algorithm is simple to implement and to use in practice, even on embedded micro-processors with limited computation and memory capabilities. In our model, every IoT device implements its own UCB1 algorithm, independently. For one IoT device, the time t is the total number of sent messages from the beginning, as rewards are only obtained after a transmission.

C. The Thompson sampling algorithm

Thompson Sampling (TS) [START_REF] Thompson | On the likelihood that one unknown probability exceeds another in view of the evidence of two samples[END_REF] was introduced early on, in 1933 as the very first bandit algorithm, in the context of clinical trials (in which each arm models the efficacy of one treatment across patients). Given a prior distribution on the mean of each arm, the algorithm selects the next arm to draw based on samples from the conjugated posterior distribution, which for Bernoulli rewards is a Beta distribution.

A Beta prior Beta(ak(0) = 1, bk(0) = 1) (initially uniform) is assumed on µk ∈ [0, 1], and at time t the posterior is Beta(ak(t), bk(t)). After every channel selection, the posterior is updated to have ak(t) and bk(t) counting the number of successful and failed transmissions made on channel k. More precisely, if the ACK message is received, the update is ak(t + 1) = ak(t) + 1, and bk(t + 1) = bk(t), otherwise the update is ak(t + 1) = ak(t), and bk(t + 1) = bk(t) + 1. Then, the decision is done by sampling an index for each arm, at each time step t, from the arm posteriors: Xk(t) ∼ Beta(ak(t), bk(t)), and the chosen channel is simply the channel C(t + 1) with highest index Xk(t). For this reason, Thompson Sampling is called a randomized index policy.

The TS algorithm, although being simple and easy to implement, is known to perform well for stochastic problems, for which it was proven to be asymptotically optimal [START_REF] Agrawal | Analysis of Thompson sampling for the Multi-Armed Bandit problem[END_REF] [START_REF] Kaufmann | Thompson Sampling: an Asymptotically Optimal Finite-Time Analysis[END_REF]. It is known to be empirically efficient, and for these reasons it has been used successfully in various applications, including on problems from Cognitive Radio [START_REF] Toldov | A Thompson Sampling approach to channel exploration-exploitation problem in multihop cognitive radio networks[END_REF] [START_REF] Maskooki | Competition: Channel Exploration/Exploitation Based on a Thompson Sampling Approach in a Radio Cognitive Environment[END_REF], and also in previous work on decentralized IoT-like networks [START_REF] Moy | Proof-of-Concept System for Opportunistic Spectrum Access in Multi-user Decentralized Networks[END_REF].

D. Multi-player bandit issue

We can prove that one single intelligent IoT can improve consequently its performance in LPWAN IoT networks using unlicensed band. But we have also shown that even if there are a lot of intelligent IoT devices, and the model of other surrounding IoT devices does not stay purely stochastic, learning still brings improvement [START_REF] Bonnefoi | Multi-Armed Bandit Learning in IoT Networks: Learning helps even in nonstationary settings[END_REF]. Further theoretical developments on this direction are an interesting future work.

III. IOT PROOF-OF-CONCEPT

We first developped a proof-of-concept named MALIN, demonstrating the feasibility of using learning algorithms on the IoT device side, on real radio signals in lab conditions [START_REF] Besson | MALIN: Multi-Armed bandit Learning for Iot Networks with GRC: A TestBed Implementation and Demonstration that Learning Helps[END_REF].

A. PoC setup

This PoC is based on 4 USRP platforms from Ettus Research and NI 1 . The development has been done using the GNU Radio 2 software, and the source code of the PoC can be found on-line3 in order to reproduce our results. We have not implemented a real IoT standard in this PoC, in order to show that it can be applicable for any IoT standard. However, we took some characteristics rather corresponding to the LoRa context (not ultra-narrow band, reduced number of channels, frame duration around a few hundreds of milliseconds, etc.).

One USRP platform is a traffic generator which emulates as much (random) IoT traffic as we want, to be able to tune each channel's load independently, on demand. We typically choose channel loads from 0% to 20%, which is the scale supported in theory by a pure ALOHA channel access scheme.

One or two USRP platforms are playing the role of IoT devices that can run (or not) the proposed learning algorithms. They transmit at their own initiative some very light modulated information (using QPSK) so as to be identified by the gateway and then wait during one second for the gateway ACK. Both uplink transmissions and downlink receptions are done on the same frequency channel. Whether the ACK is received or not, the learning algorithm updates its knowledge about the channel used during this iteration.

A fourth USRP platform is a gateway (GW) that is continuously scanning the IoT traffic composed of the artificial signals produced by the traffic generator and the IoT platforms signals. The gateway has the ability to answer to the IoT devices, while sending back to them an ACK message containing their identifier, which is the symbols corresponding to the QPSK complex conjugate of their identifier indeed.

In order to simplify the radio signal reception we use an artificial carrier synchronization between all USRP platforms, using an Ettus Octoclock 1 . However, a simple carrier recovery method could be used. Consequently, we just have a phase correction to implement at both gateway and IoT receiver sides, from the radio point of view.

B. PoC results

The number of IoT channels is a parameter, and we have set it to 4, 8 and 16 channels in our expermiments, but there is no limitation. For the of clarity in the figures, we give examples below with 4 channels that are separated by empty channels, but they could be contiguous with no change neither in the implementation nor in the results.

We can see on Fig. 2 a time-frequency waterfall view captured by the gateway, where we can observe the RF traffic in 4 channels. Time is vertical and going down and frequency is on the x axis. The difference of colors is a difference of received power, due to the distance of transmitters to the gateway receiver antenna. The gateway transmitter antenna is very close so signals transmitted by the gateway are red. The traffic generator and IoT devices are a little bit further away, so the gateway received weaker signals from them, one is blue and the other green, which reveals a low difference. In this experiment, we can see en Fig. 2 that channel 1 has been configured to have a dense IoT traffic, which appears as blue short transmissions (produced by the traffic generator). Some others appear on channel 2, but we do not see any blue short messages on channel 3 and 4. However, we see on these channels longer messages of two kinds: green messages which correspond to IoT devices transmissions. In order to rapidly have results on the demo, we make them transmit every 5 seconds, for a message of duration of one second. Then when an IoT device transmits a message, the gateway should answer and sends an ACK to the IoT device within 1 second if the gateway was able to demodulate the signal, if there is no collision in the radio channel: these correspond to the red blocks in Fig. 2. For instance, we can see in this screenshot that the IoT device moved from channel 3 to channel 2, and at each transmission of the IoT device, the gateway was able to answer, successfully sending an ACK response. Fig. 3 gives the perspective of the IoT device, at a different moment for the same scenario. Then we observe that colors have changed, as the received power is now device-centric. The IoT device transmitter antenna is now very close, so signals transmitted by the IoT device are red. The traffic generator, the other IoT devices, and then the gateway all are a little bit further away, so the IoT device received weaker signals from all of them, one is blue and the other green but inversed. However, it is not so obvious, so it is better to consider the message duration in the y axis indeed.

We can see on Fig. 3 that if we use the same scenario of traffic as in Fig. 2, with a very dense traffic on channel 1, less dense on channel 2, even less dense on channel 3, then transmission appears on channel 4 but it is indeed just even less dense. At that time of the experiment, our IoT device is moving from channel 3, where maybe it faced some collisions in the dowlink transmission of ACK, to channel 4, where several successive transmissions and receptions seem to occur. Fig. 4 is a screenshot taken at some moment during an experiment, that gives the details of the learning algorithm operation. We can see in top-left red data the number of times each channel has been used. There is a clear desequilibrium with channel 4 that has been much more (17 times) used than channel 3 (8 times), itself more used than channel 2 (6 times) and channel 1 (only once). This reveals the effect of the learning algorithm. It has analyzed which channels are more occupied and disturbed by other users of the band (emulated here by the traffic generator). The top-right green and as a consequence the bottom-right blue data explain such a choice. Channel 4 has known 16 successes (over 17), so a rate of 94%. Successes mean that the IoT device received on that channel 16 ACK from the GW after transmitting 17 times in this channel. So just one "exchange" was lost, either in UL, or in DL, due to a collision with some interferring signal in the channel. We can see on the opposite that no success has been obtained for channel 1, so it has a 0% rate. UCB data, in bottom-left green part, are harder to follow, as UCB indexes rapidly converge to very close values, but at each transmission, the IoT device chooses channel with highest UCB index, as in [START_REF] Bonnefoi | Multi-Armed Bandit Learning in IoT Networks: Learning helps even in nonstationary settings[END_REF]. IV. IOTLIGENT: LEARNING FOR NON COORDINATED AND DECENTRALIZED IOT DYNAMIC SPECTRUM ACCESS The next and last step after modeling and exposing our proof-of-concept consists in implementing our approach in real conditions of operation, that is, in a real IoT network. As far as the authors know, this is the first implementation of decentralized artificial intelligence algorithms in IoT devices to tackle the IoT spectrum contention mitigation problem and we named it IoTligent [START_REF] Moy | IoTligent: First World-Wide Implementation of Decentralized Spectrum Learning for IoT Wireless Networks[END_REF]. It is necessary, first, to remind quickly how a LoRaWAN network is constituted. We are using here a real LoRa network in the European ISM band, at 868 MHz.

A. LoRaWAN architecture

The implementation of the learning algorithm we propose is decentralized, it takes place only on the LoRa device side. As stated earlier, no aspect of the LoRaWAN network is impacted. We explain below a little bit more the LoRaWAN network side configuration [START_REF] Sornin | LoRaWAN specification[END_REF] [START_REF][END_REF].

A LoRaWAN network, as any other IoT network, can be summarized by four main elements, as shown in Fig. 5:  LoRa devices (our devices run the UCB algorithm here),  LoRa gateway(s) receiving all LoRa radio signals in their radio range,  A Lora Network Server (LNS) that discriminates devices subscribing to its network from others,  An Application Server (AS) that receives the data sent by devices and sends back ACK to them (mandatory here).

The IoT devices are associated to a given LoRaWAN network with a "join phase", at their very first communication through a gateway of this network. The appairment is done at the LoRa Network Server (LNS) side as explained below. Finally, data extracted from radio signals, sent by the IoT devices, are sent to the Application Server (AS) that manages data (i.e. processes them, sends them to a storing place in the cloud and/or an application). Then the role of the AS is to initiate a sending of an ACK to the IoT device, through LNS and a gateway, down to the IoT device.

B. Device side

As an IoT device, we use, as shown on Fig. 6, a Pycom card [17] composed of an Expansion Board and a LoPy module which can support LoRa wireless connectivity. The Pycom card is programmed in the Python language. The frequency channels used in the experiments are those authorized in the country of experimentation, i.e., France. Three channels are usually used in Europe for uplink (UL) with a duty cycle of 1%: 868.1 MHz, 868.3 MHz, 868.5 MHz. Our proposal IoTligent is completely agnostic to the number of channels in the standard, so it can be used in any country. Note that some amendment had to be done to the Pycom firmware in order to enable programming channel assignement in the Python program, in LORAWAN mode.

C. Network side

We have access to the LNS provided by the Acklio Company. Acklio has several gateways in the city of Rennes, where the experiments were made. LNS sends the received messages to an AS which is a Linux server, running in the cloud. AS is running a Python program that enables to display data and metadata (i.e., frequency, time of reception, etc). This programs also contains instructions to send an acknowledgment to the device, using in DL the same frequency used by the IoT device at UL. The transmit channel frequency is then chosen in a set of N channels which is set here at N = 3. We use standard Europe UL channels with the following frequency table (in MHz): IoTligent device infinite while loop is started, running the algorithm presented in the next section and [START_REF] Jouini | Upper Confidence Bound Based Decision Making Strategies and Dynamic Spectrum Access[END_REF], in order to choose which frequency to be selected at each iteration before executing a send operation. An ACK is then expected from the network side in non blocking mode so that when ACK is not received, device just updates its learning data and still goes on.

B. Network side -Lora Network Server

Devices should be declared to LNS with at least the following information: The address of the AS is also specified in Connectors, as well as the mode used to send data between LNS and AS (http callback chosen here).

C. Network side -Application Server

The AS runs a Python program that receives data from the LNS, as well as LoRa metadata with all parameters of LoRaWAN transmission (frequency, SF, BW, time of arrival, etc). This program also sends an acknowledgment message to the device in DL. First, an acknowledgment attempt is sent by default at the same frequency than the message transmitted by device it answers to. Then we block any other retransmission. This is exactly what is necessary for the learning of IoTligent:

 to use the same channel in both UL and DL,  to avoid retransmission in order to save batteries of devices on the one hand, and radio frequency overload on the other hand.

VI. LEARNING ALGORITHM IN PYCOM DEVICE

The learning algorithms used in IoTligent are (any) bandit algorithms, such as those first used for Cognitive Radio dynamic spectrum access in [START_REF] Jouini | Upper Confidence Bound Based Decision Making Strategies and Dynamic Spectrum Access[END_REF], and implemented in the SMPyBandits Python library [START_REF] Besson | SMPyBandits: an Open-Source Research Framework for Single and Multi-Players Multi-Arms Bandits (MAB) Algorithms in Python[END_REF]. We take here the example of UCB1 algorithm, as presented above [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF]. We have chosen these algorithms for their ease of implementation. The only data necessary to be stored for UCB1 algorithm are:  an iteration index initialized at 0: itindex,  a table of size N (the number of channels, 3 in this implementation example, but it could be arbitrarily high) for the number of times each channel has been chosen, representing Nk of (2): From the learning algorithm point of view, a success occurs when an IoT device receives an ACK from the IoT network (as explained above), which means that the currently used frequency channel suffered no collision both in UL and DL. Otherwise, a failure occurred. The update of the selected channel empirical mean Xk is reconstructed easily from the number of activations and previous Xk stored value. So it is not necessary to store in memory the results of all past iterations, but just only a summary of it (its mean).

Then after an initialization phase where each channel is selected alternatively once, UCB1 algorithm really starts [START_REF] Jouini | Upper Confidence Bound Based Decision Making Strategies and Dynamic Spectrum Access[END_REF] . It consists for each iteration in choosing the frequency channel with greatest index Bk as defined in ( 5), with bias Ak of (4), that is computed for each channel like this in a for loop on i index, and with alpha the UCB1 parameter α that sets the exploration vs. exploitation trade-off [START_REF] Jouini | Upper Confidence Bound Based Decision Making Strategies and Dynamic Spectrum Access[END_REF]:

Ak[i] = math.sqrt(alpha*math.log(it)/Tk[i])
IoTligent channel selection is then on the greatest Bk [START_REF] Jouini | Upper Confidence Bound Based Decision Making Strategies and Dynamic Spectrum Access[END_REF]:

for i in range(N): Bk[i] = Xk[i] + Ak[i] if Bk[i] > bestChannel: bestChannel = Bk[i] ; freq = tabFreq[i]
VII. RESULTS FOR THE IOTLIGENT DEMONSTRATION Experiments have been done on a real LoRa network currently deployed with 3 channels. More channels are expected to be used in the future, but it will not induce any implementation difference (only 2 extra numbers to be saved by added channel). We present results obtained on a IoTligent device, for 129 transmissions done every 2 hours, so a period of 11 days. Fig. 7 shows the evolution of the Tk index through time, the number of time each channel has been selected by the learning algorithm. In the figures, the black curve is for channel 0 (at 868.1 MHz), the blue curve is for channel 1 (868.3 MHz) and the red curve is for channel 2 (868.5 MHz). We can see that channel 1 gives the best results, before channel 2, but channel 0 always failed in sending back an ACK to the device. Each peak in Fig. 8 reveals a successful case where ACK has been received by IoTligent device. Fig. 8 gives the end results after 11 days. We can see that channel 0 has been tried 29 times with Sk[0] = 0 success (i.e., no ACK received by the device). So the learning algorithm made the device use 61 times channel 1 with Sk[1] = 7 successful bidirectional exchanges, and 39 times channel 2 with Sk[2] = 2 successes. This corresponds to 7 (respectively 2) peaks of Xk [START_REF] Sornin | LoRaWAN specification[END_REF] (respectively Xk [START_REF] Jouini | Upper Confidence Bound Based Decision Making Strategies and Dynamic Spectrum Access[END_REF]) on Fig. 2. The empirical mean gives the vision the device obtained from the channels, i.e., a mean probability of 11.5% of successful bi-directional connection for channel 1 and 5% for channel 2, whereas channel 0 never worked from the device point of view. With a normal device, i.e., a non IoTligent device, a random access is done, trying once over 3 times on each channel, for a global average successful rate of 5.5%.

It is important to note that here the learning algorithm is mostly in its exploration phase, but is learning very fast. Only during the last 2 days of the experimen, channel 1 has already been used 4 times more than channel 0 and 2.5 times more than channel 2, which means that learning is already effective. As proven for UCB algorithms [START_REF] Jouini | Upper Confidence Bound Based Decision Making Strategies and Dynamic Spectrum Access[END_REF][3], channel 1 will be more and more selected so that the global success rate will converge to the percentage of success of the best channel, which is 11.5% in this experiment (this estimate can be considered as a good evaluation as it is based on 61 trials). In other words, this means that a mean of 15 successes can be expected in the long term over the same period of 11 days with IoTligent. On the contrary, normal devices will never improve and stay in the current average, i.e. in average 7 successful transmission on the same period duration.

In order to have the same rate of successful transmissions, normal IoT devices should consequently transmit twice more often, which has two negatives impacts. The first impact is that normal IoT devices autonomy will be twice less than IoTligent devices. The second but not the least impact is that devices will occupy twice more times radio channels, hence contributing to increase even more the risks of radio collisions and thus the IoT bands congestion.

VIII. CONCLUSION AND PERSPECTIVES

We describe in this paper the solution we propose to mitigate radio collisions in IoT unlicensed bands. Our solution is based on learning algorithms to be implemented on the IoT device side, at a very low cost of implementation and no protocol overhead. We prove the efficiency of the method on a proof-of-concept demonstration based on USRP platforms in laboratory conditions (named MALIN), then we present the implementation of learning algorithms on devices deployed in a real IoT network. Implementation on LoRa devices in a real LoRaWAN network is demonstrated and is named IoTligent. As far as we know, we propose the first implementation of a decentralized spectrum learning scheme for IoT wireless networks. Even if the current IoT networks are (yet) not densely populated by devices, medium and even short term forecasts predict a high number of devices to overcrowd ISM unlicensed bands. The IoTligent approach is then a solution to extend IoT devices battery life, which is a key performance indicator in any IoT eco-system.

Fig. 1 .

 1 Fig. 1. System model used for IoT, with intelligent IoT devices that are able to dynamically set their transmission channel thanks to a learning algorithm, in order to minimize collisions and interference from other radio signals in the unlicensed ISM band, especially other IoT networks which will be responsible of most of future traffic.

Fig. 2 .

 2 Fig. 2. Spectrum waterfall on GRC received at gateway side in a 4 channels example, during exeriments. Time is in y axis (going down) and frequency in x axis. Blue short transmissions are those produced by the traffic generator, green blocks are our IoT transmissions and red blocks are the gateway transmissions itself.

Fig. 3 .

 3 Fig. 3. Spectrum waterfall on GRC received at IoT device side in a 4 channels example, during exeriments. Time is in y axis (going down) and frequency in x axis. Green short transmissions are those produced by the traffic generator, red blocks are the IoT device transmissions, and green blocks are gateway transmissions.

Fig. 4 .

 4 Fig. 4. Live results enabling to monitor the learning algorithm evolution at the IoT device side in a 4 channels example. Top-left red: number of trials on each channel, top-right green: number of successes on each channel (ACK received by IoT device), bottom-left green: UCB index B for each channel, bottom-rignt blue: success rate on each channel.

Fig. 5 .

 5 Fig. 5. LoRaWAN network parts: IoT devices, gateways, LNS and AS [19].

Fig. 6 .

 6 Fig. 6. Pycom module composed of a LoPy4 and an Expansion Board [17].

  V. IMPLEMENTATION OF IOTLIGENT IN A REAL LORA NETWORK A. Device side Based on on-line examples found in [17] we use LORAWAN mode with an Over-The-Air-Activation (OTAA) using app_EUI and app_key keys: lora = LoRa(mode=LoRa.LORAWAN,region=LoRa.EU868) lora.join(activation=LoRa.OTAA, auth=(app_EUI, app_key), timeout=0)

  tabFreq =[868100000, 868300000, 868500000]



  devEUI : ID of the device obtained by executing a « get_id.py » program from [17] on the Pycom device itself,  appEUI : which should correspond to app_eui chosen in the pycom device,  appKey: which should correspond to app_key chosen in the pycom device,  other parameters are let by default at SF=12 (spreading factor), and bandwidth BW=125kHz.

Fig. 7 .

 7 Fig. 7. Evolution of the Tk index through time (as learning happens).

Fig. 8

 8 Fig.8gives the empirical mean Xk experienced by the device on each of the 3 channels. Each peak corresponds to a successful LoRa bi-directional exchange between the device and AS: from device uplink transmission to ACK reception (downlink) by the device.

Fig. 8 .

 8 Fig. 8. Evolution of the Xk empirical mean through time. Black curve: channel 0 ;blue curve: channel 1 ; red curve: channel 2.

Tk

  Other IoT devices of surrounding networks others than the network of our device, but using the same IoT standard. This can occur both in UL and DL, as surrounding IoT gateways of different networks are not coordinated. They could use the same channels, or partly same and partly different channels.  Other IoT radio signals using other IoT radio standards. Each IoT standard uses its own rules for channeling, bandwidth, user repartition, etc.  Other radio signals present in the ISM band which are not IoT signals. By definition, they use completely different rules than IoT. They are "jammers" from the IoT networks point of view.

	IoT
	networks operating in the unlicensed bands, such as ISM
	bands. Collisions may occur with:

 other IoT devices of the same network, as several networks covering the same area are not coordinated. This can occur between IoT devices uplink (UL) transmissions, and between IoT UL and gateway downlink (DL) transmissions towards IoT devices.



  Tk[].

 another table of size N for the empirical mean of success of each channel, i.e., 𝜇 (𝑡) of (3): Xk[].

TABLE I .

 I RESULTS AT THE END OF THE EXPERIMENT

https://bitbucket.org/scee_ietr/malin-multi-armed-bandit-learning-for-iot-networkswith-grc is released publicly under the open-source GPLv3 license.

ACKNOWLEDGMENT

The authors would like to thank Rémi Bonnefoi for the MALIN implementation [4], as well as Laurent Toutain, from IMT Atlantique and the Acklio Company, and Yalla Diop for their technical support on LoRa network and Pycom programming.


ERIS Marie-Paule Lecoutre
email: marie-paule.lecoutre@univ-rouen.fr

Evelyne Clément
email: clement@epeire.univ-rouen.fr

Bruno Lecoutre
email: brunolecoutre@univ-rouen.fr

Some of the authors of this publication are also working on these related projects

Keywords: Complementary Problems, Equiprobability Bias, Isomorphic Problems, Learning, Poker chips, Probability judgment

) Students who performed correctly on the four geometric-figures problems also solved correctly the poker-chips problem. (The didactic implications of the results in teaching mathematical concepts are discussed.)

These results appear to have some significant implications in teaching mathematical concepts.

INTRODUCTION

The aim of this research is to study spontaneous representations and their evolution in «purely random» situations, e.g. situations where samples are drawn at random from a set. The experimental work presented below is in keeping with a research program which insists on the value, if not the necessity, of attempting to act upon the cognitive representations used by persons, by determining the best conditions under which the appropriate representations are activated. Indeed such an approach appears to have significant didactic implications, in particular concerning the teaching of certain mathematical concepts.

Let us consider the following situation: there are three poker chips in a jar, two red ones and one white one. Two chips are picked out together, and the following two results «a red chip and a white chip are obtained» or «two red chips are obtained» have to be compared regarding their probability. While the correct expected answer is "there is more chance of obtaining a red chip and a white chip", previous studies (Lecoutre and Durand, 1988;[START_REF] Lecoutre | Cognitive models and problem spaces in «purely random» situations[END_REF] have shown that in this case most adults answer erroneously that the two results are equiprobable «because it's a matter of chance». Analysis of the patterns of answers observed in a series of problems and of verbal reports has shown that random events are thought to be equiprobable «by nature». This representation, called the «equiprobability bias», is seen as an «implicit model» in the sense employed by Fischbein [START_REF] Fischbein | Intuition in Science and Mathematics: an Educational Approach[END_REF][START_REF] Fischbein | Tacit models and mathematical reasoning[END_REF][START_REF] Fischbein | Tacit models[END_REF][START_REF] Fischbein | The role of implicit models in solving verbal problems in multiplication and division[END_REF]. It can be compared to the «uniformity belief» reported by [START_REF] Falk | A closer look at the probabilities of the notorious three prisoners[END_REF] for solving the «problem of three prisoners», that is to say people have a strong intuitive tendency to assume equal probabilities for the various available options. Additional convergent findings on the prominence of this intuitive belief can be found in a didactical study on college students' conceptions of randomness in which some students only consider a phenomenon to be random when all its outcomes are equally likely [START_REF] Konold | Novices'views on randomness[END_REF].

In the context of elementary arithmetic tasks solved by children, [START_REF] Fischbein | The role of implicit models in solving verbal problems in multiplication and division[END_REF] hypothesize on the nature and the role of implicit models involved in constructing the representation of this type of problem. These implicit models are constructed using various everyday-life experiences as a basis, and they are the origin of spontaneous representations. In some cases, these representations are inadequate for solving problems and are responsible for misconceptions. The models are considered as a basis for the interpretation of mathematical concepts which are deeply rooted despite the acquisition of formal concepts, and as structural schemata on which most intuition is based [START_REF] Fischbein | Schemata and intuitions in combinatorial reasoning[END_REF][START_REF] Fischbein | The evolution with age of probabilistic, intuitively based misconceptions[END_REF][START_REF] Lecoutre | Evolution avec l'âge de «misconceptions» dans les intuitions probabilistes en France et en Israël[END_REF]In the problems involving drawing poker chips from a jar, it seems reasonable to assume that the implicit «equiprobability bias» guides the interpretation and explains the difficulties of perceiving the situation as an example of elementary combinatorial problems. We assumed that the main difficulties encountered by people were due to the same general phenomenon: the chance context of the «purely random» situation evokes an implicit model which is inadequate, and the misconceptions can be interpreted as a difficulty pertaining to gaining access to the adequate representation. More precisely in elementary uncertainty situations, the adequate combinatorial or logical representations are assumed to be available to most people, but not spontaneously evoked. Then the following question can be asked: what kind of experimental trick would be favorable to the activation of an adequate abstract representation of the situation? [START_REF] Ross | Shortcomings in the attribution process; On the origins and maintenance of erroneous social assessments[END_REF] suggested that effective experiences are those that require people to act upon their beliefs. As is demonstrated in recent research, learning would be enhanced by making students become aware of and confront their erroneous representations [START_REF] Delmas | Assessing the effects of a computer microworld on statistical reasoning[END_REF]. In this framework, we set up an experiment with a learning phase aiming at examining whether learners can construct adequate representations of the situation if they are forced to see that their beliefs on earlier problems led to erroneous answers, and so to test the instructional effectiveness of active problem comparison on abstraction. During this learning phase, the subjects had to solve a series of four study problems which were pair-wise related by complementarity and equivalence. Indeed, two of the problems were isomorphic (« equivalent »), and the other two had a complementary structure. Thus respectively the four problems concerned:

-Problem 1 (P1): one element drawn from the three; -Problem 2 (P2): the two remaining elements after having drawn one element. Problem P2 will be called the «complementary problem» to P1 because its correct answer can be deduced by a complementarity relation from P1;

-Problem 3 (P3): the remaining element after having drawn two elements. Problem P3 is equivalent to P1 but described differently. P1 and P3 will be called «equivalent problems»;

-Problem 4 (P4): two drawn elements. This problem is complementary to P3 and equivalent to P2. This is the «classic» standard problem [START_REF] Lecoutre | Cognitive models and problem spaces in «purely random» situations[END_REF].

The relations between these four problems are presented in Figure 1 and the wording of the four problems can be found in the method section.

Then a fifth « transfer » problem which was isomorphic to the fourth problem (P4) of the learning phase was given.

We predicted that if the students identified the relations, complementarity and equivalence relations, between the four study problems of the learning phase, , they would then succeed in constructing an adequate abstract representation, and a transfer to a fifth structurally isomorphic problem would then be observed.

Figure 1 -Relations between the four problems in the learning phase

Method

Participants

The participants were 42 students of both sexes, aged approximately 18-25 years old, and enrolled in an introductory statistics course open to psychologists at Rouen University (1 st year). The students participated in the experiment before any formal teaching of probability had taken place.

Materials

Learning phase

The four problems of the learning phase involved geometric figures, two triangles and a square. The size of the triangles was the same as the size of the square. The students were shown by means of visual animation on the computer screen that it was possible to construct either a house if a triangle and a square were drawn -therefore two ways of constructing a house-, or a rhombus if the two triangles were drawn -therefore only one way of constructing a rhombus-(see Figure 2).

Figure 2 -The geometric figures

Four problems reported in Table 1 were successively presented in the same order to all the participants. As referred to above, they are either «equivalent» (P1 and P3, P2 and P4), or «complementary» (P1 and P2; P3 and P4). Problem P4 corresponds to the «standard-problem» used in previous studies [START_REF] Lecoutre | Cognitive models and problem spaces in «purely random» situations[END_REF].

Table1 -The problems presented

Learning Phase

Problem P1. Suppose that the three figures are in a jar. After having mixed them up, I draw one figure from the jar, and am interested in the drawn figure. The following two results are considered Result R1: a triangle is obtained (1) Result R2: a square is obtained Do you think there is: more chance of obtaining R1? more chance of obtaining R2? an equal chance of obtaining R1 and R2? it is impossible to give an answer Justify your response out loud Problem P2. Suppose again that the three figures are in a jar. After having mixed them up, I have drawn one figure from the jar, and am interested in the two remaining figures in the jar after drawing this figure. The following two results are considered Result R1: with the two remaining figures in the jar, it's possible to construct a house Result R2: with the two remaining figures in the jar, it's possible to construct a rhombus Do you think there is: more chance of obtaining R1? more chance of obtaining R2? an equal chance of obtaining R1 and R2? it is impossible to give an answer Justify your response out loud Problem P3. Suppose again that the three figures are in a jar. After having mixed them up, I have drawn two figures from the jar, and am interested in the remaining figure in the jar after drawing these two figures. The following two results are considered Result R1: the remaining figure in the jar is a triangle Result R2: the remaining figure in the jar is a square Do you think there is: more chance of obtaining R1? more chance of obtaining R2? an equal chance of obtaining R1 and R2? it is impossible to give an answer Justify your response out loud Problem P4. (standard-problem). Suppose again that the three figures are in a jar. After having mixed them up, I draw two figures from the jar, and am interested in the two drawn figures. The following two results are considered Result R1: with the two drawn figures, it's possible to construct a house Result R2: with the two drawn figures, it's possible to construct a rhombus Do you think there is: more chance of obtaining R1? more chance of obtaining R2? an equal chance of obtaining R1 and R2? it is impossible to give an answer Justify your response out loud

Transfer Phase

Problem P5. Now suppose there are three chips are in a jar, two red chips and one white chip. After having mixed them up, I draw two chips from the jar, and am interested in the two drawn chips. The following two results are considered Result R1: the two chips are a red chip and a white chip Result R2: the two chips are two red chips Do you think there is: more chance of obtaining R1? more chance of obtaining R2? an equal chance of obtaining R1 and R2? it is impossible to give an answer Justify your response out loud (1) In the present Table, in order to simplify the presentation of the results, result R1 is always the correct one; in the experiment, the assignment of the correct response to either results R1 or R2 is uncertain.

For each problem, the participants were asked to give their answers by choosing one of the following four possibilities: (1) more chance of obtaining R1; (2) more chance of obtaining R2 (3) an equal chance of obtaining R1 and R2 (4) it is impossible to give an answer.

Transfer phase

The fifth problem P5 involved poker chips, two reds and one white (cf. Table 1). It was structurally isomorphic to the fourth geometric-figures problem P4.

Procedure

The problems were displayed on a computer, and the students were tested individually. First they were shown how to answer by using the mouse, and were asked to familiarise themselves with the computer environment. Then they were asked to solve the problems, and were informed that there was no time constraint.

The five problems were presented with feed-back: in the case of a correct answer, the participant was given the following positive encouragement «Bravo, your answer is correct», and then the next problem was presented. In the case of an incorrect answer, the participant was told that his answer was incorrect and was asked to give another one; he was then given help with the possibility of going back to the correct answers to the previous problems. Therefore the participants could not solve the next problem until they had correctly answered the problem in question. Furthermore for each problem, the participants had to justify their answers (correct ones as well as incorrect ones) out loud.Experimentation times ranged from quarter of an hour to half an hour, depending on the individual.

Results

Two indications of behavior will be considered: the first answer given for each problem with the associated justification, and the pattern of answers for the successive problems.

Statistical analysis

Following the recent guidelines proposed of the American Psychological Association's Manuel (APA, 2001), interval estimates are given for each proportion (or the difference between proportions) of interest. We used the standard non-informative Bayesian procedures (see e.g., [START_REF] Lecoutre | Bayesian predictive approach for inference about proportions[END_REF] in order to calculate 0.90 probability interval estimates. For inferences about proportions these intervals can be favorably compared to frequentist confidence intervals [START_REF] Lecoutre | Bayesian procedures for prediction analysis of implication hypotheses in 2 2 contingency tables[END_REF]Brown, Cai and Das Gupta,2001). The Bayesian interpretation is that there is a 90% chance that the true proportion falls within the computed interval estimates. For each analysis, we give the observed percentage of interest, followed by the corresponding interval estimate in brackets.

The Learning Phase: Problems P1 to P4

The results obtained for each problem are reported in Table 2.

Problem 1. This problem which is related to drawing one object out of three, and considered, a priori, as the easiest one, led to the largest rate of correct answers (74%). The observed difference between this percentage and the mean percentage of correct responses to the other three problems is equal to 17%, with the interval estimate [3%,29%]. The justifications given by the students revealed that the representation activated in this case was an adequate representation in which they consider the number of elements. Thus for example, «there are more triangles than squares, so there is more chance of drawing a triangle». This «numbers model» was the only representation used in this case as in previous studies (see for example [START_REF] Lecoutre | Jugements probabilistes chez des adultes: pratique des jeux de hasard et formation en théorie des probabilités[END_REF]. However we must emphasize the surprisingly relatively high percentage of equiprobability responses (19% [11%,30%]) related to the activation of the «equiprobability bias». If we first consider the 74% participants who correctly solved P1, it must be noted that only 64% of them [50%,77%] also gave the correct answer first time round to P2. So the complementarity relation between P1 and P2 was not salient for many of the afore-mentioned participants. Furthermore 29% of them [17%,43%] gave an equiprobability response, yet this result points out the strength of the equiprobability bias. The answers of the students who activated the equiprobability bias in P1 reveal that even though 75% [46%,92%] gave the correct answer, 25% [8%,54%] also used it in P2. These findings show the difficulties encountered by the participants in reasoning about what remains in an urn after a draw, and so to realize the complementary status of situations.

Problem 3. In problem P3, equivalent to P1, the rate of correct answers is quite low (48% [35%,60%]), and is also the smallest one.

Analysis of the bivariate data concerning P1 and P3 which are equivalent problems, is reported in Table 4. Only 42% [28%,57%] of the 74% participants who had correctly solved P1 gave the correct answer to P3. This result shows that the equivalence relation was not really accessible and in any case not perceived as a salient feature by most students. An equal percentage of students (42%) gave the equiprobability response. These findings show that people reason differently about structurally isomorphic problems. These findings are consistent with those generally reported in research literature on analogical processing. Indeed the analogy between isomorphs is hardly perceived or used, unless a hint is given that the solution to a first problem might have something to do with the solution to a second one (see for example, [START_REF] Hayes | Psychological differences among problem isomorphs[END_REF][START_REF] Keane | What makes an analogy difficult? The effect of order and causal structure on analogical mapping[END_REF].

In fact for this problem a little more than 15% of the subjects utilized an interesting representation called the «conditional model» (see [START_REF] Lecoutre | Cognitive models and problem spaces in «purely random» situations[END_REF] The reasoning was the following: knowing that in a pair of drawn elements, one of the two identical ones will inevitably be obtained (a triangle), consequently one element of each kind remains therefore there is an even chance for the second drawn object; as a result both results are equiprobable. Such a reasoning could be seen as a way to transform and cancel out the random aspect of the situation.

All these findings, like those previously reported for P2, clearly demonstrate that for most people it is difficult (or even impossible) to reason about what remains after a draw. Indeed in most every-day life situations we are led to reason about what has been drawn (in lotteries for example) and hardly ever about what remains. The activation of this model could be enough to «mask» the perception of the equivalence «drawn element (P1)/remaining element (P3)». This result could be interpreted as the expression of the general analogical transfer process. Indeed in this case the general knowledge constructed by experience of lotteries is imported into the new situation in which such knowledge is irrelevant.

Problem 4. 57% [44%,69%] of the participants correctly solved this problem. Analysis of the bivariate data concerning P4 and P2 (equivalent problems) on the one hand, and of P4 and P3 (complementary problems) on the other hand is reported respectively in Tables 5 and6.

(7) [14%,40%] 17% (2) [5%,39%] 0% (0) 0% (0) Result R2 18% (5) 33% (4) 0% (0) 0% (0) ? 0% (0) 0% (0) 0% (0) 0% (0) (/28) (/12) (/1) (/1)
Only a little more than half of the 67% participants who had correctly solved P2 gave the correct answer for P4 (57% [42%,72%]). This result is to be compared to the one previously reported for the other pair of equivalent problems (P1 and P3): for many participants, the equivalence relation did not appear to be a salient feature.

? 0% (0) 0% (0) 0% (0) 0% (0) (/20) (/15) (/5) (/2)
Only 60% [42%,76%] of the 48% students who had correctly solved P3 gave the correct answer for P4. This result is to be compared to the one obtained for the other pair of complementary problems (P1 and P2). It reveals yet again that the complementarity relation does not seem to have been used by most students when answering.

Thus, at the end of the learning phase, it appears that the instructional intervention used was not very effective : the learning effect was clearly below what might have been expected. To go into more detail in the interpretation of our findings, it is interesting to examine the sequences of four responses successively given from P1 to P4 during the learning phase. For example, «+R1 = +R2 =» is the pattern of a participant who answered «+R1» (correct response) for P1, «=» (equiprobability response) for P2, «+R2» (more chance of obtaining R2) for P3, and «=» for P4. Individual patterns were very heterogeneous from one participant to another: 26 different patterns (for 42 participants) were registered, amongst which 18 of them were only observed once. It is likely that this great heterogeneity is due to the fact that for most participants each problem was treated as a new problem, independently of the preceding ones. In the case of a first incorrect answer, only slightly less than a third of the participants (32%) asked to go back to the correct answers to the previous problems, which were rarely spontaneously perceived as relevant for solving a new problem.All these findings are convergent, and support the conclusion on the absence of construction of an adequate representation of the situation for many students at the end of the learning phase. This is due to the fact that the complementarity as well as the equivalence relations were not used to solve the problems because they were not salient features and therefore were not an efficient means of assistance for many participants.

The Transfer Phase: Problem P5

The findings for P5 are reported in Table 7.

(1) Only 64% [52%,75%] of the participants gave the correct answer for P5, and this is quite a low percentage which does not appear to be very different from the 57% observed for Problem 4. It is important to recall here that in the learning phase the problems were systematically presented until the participants gave the correct answer. Therefore all the participants knew all the solutions, and in particular the solution for P4, which is an isomorphic problem. Taking into account this fact it seems very surprising that more than a third of them still gave an incorrect answer for P5. These findings reveal that knowing the correct answers is not enough to be able to construct a correct representation. Indeed as long as the participants did not register the relations between the problems (complementarity and equivalence relations), they did not succeed in constructing the correct abstract representation of the structure of the problems.

(2) Analysis of the bivariate data concerning P5 and P4 (isomorphic problems) is reported in Table 8. This result appears compatible with the hypothesis according to which a transfer to isomorphic problems would be easier when the subjects succeed in processing the relations between the problems during the learning phase, and then succeed in constructing an abstract representation of the situation.

An exam of the individual patterns of the 79% subjects who transferred shows that for most of them (80%), there is no or at the most only one incorrect response during the learning phase. So most subjects who performed correctly at least three of the four training problems also solved correctly the transfer problem.

Conclusion

Our findings highlight three main points. (1) As far as the learning phase is concerned, only a little more than half of the participants (57%) correctly solved the classic standard problem (P4), whilst 21% of the participants gave the incorrect equiprobability answer for this problem («equiprobability bias»). Once again these findings point out the difficulties of this kind of problem despite the fact these problems are often considered self-evident. (2) The instructional intervention used in the learning phase was not very effective because for most students the two relations between the four training problems, complementarity and equivalence, which were supposed to help them for the construction of an adequate representation, were not perceived as salient features and therefore were not an efficient means of assistance. Indeed all four types of problems were quite independent for many students. These findings show that (a) people reason differently about structurally isomorphic problems and (b) fail to realize the complementary status of situations. (3) Transfer occurred only for the subset of subjects who performed correctly on the training problems of the learning phase. . O

In order to emphasize the salience of the relations between the four problems in the learning phase, two axes are being explored. (1) The effects of the order of presentation of the problems. Let us recall that in the present study, the equivalent problems were never consecutive unlike the complementary problems, and a crucial question can be formulated as follows: is there an order which is more conducive to constructing one representation than another? A series of new experiments in which the order of presentation is systematically counterbalanced, is being designed in order to answer this question. (2) The effects of the type of feedback and instructions. For instance the subjects could be asked to not only justify their own answers as in the present study, but also the correct answers to each problem. Indeed much recent work shows that the performance of some students can be improved when they are asked to systematically «self-explain» (see [START_REF] Robertson | Imitative problem solving: Why transfer of learning often fails to occur[END_REF]. Furthermore it would also be interesting to study the effects of providing the students explanation concerning the relations between the four problems proposed in our work at a level of generality which would be sufficient enough to enable them to first of all construct the adequate abstract representation, and then secondly to adapt the reasoning to suit various isomorphic problems. Such a result has recently been observed by [START_REF] Robertson | Imitative problem solving: Why transfer of learning often fails to occur[END_REF] with algebra word problems taken from [START_REF] Reed | Usefulness of analogous solutions for solving algebra word problems[END_REF].

Nevertheless the results obtained in the present study already appear to have some significant implications in the teaching of certain mathematical concepts. Indeed they suggest the value, if not the necessity, of attempting not only to « exhibit » the representations used by the subjects, but only to act upon these representations. With this purpose in mind, situations in which the students are led to construct by themselves the adequate representations are given priority.

Table 2 -

 2 Percentages of answers and corresponding 90% probability interval estimates in brackets for each problem in the learning phase Problem P2, complementary to P1, shows quite a similar distribution of responses. Analysis of the bivariate data concerning P1 and P2 is reported in Table3.

	Result R1	Equiprobable	Result R2	?
	Problem 1 74% (31) [62%,84%]	19% (8) [11%,30%]	7% (3)	0% (0)
	Problem 2 67% (28) [54%,78%] 29% (12) [18%,41%]	2% (1)	2% (1)
	Problem 3 48% (20) [35%,60%] 36% (15) [25%,48%]	12% (5)	5% (2)
	Problem 4 57% (24) [44%,69%]	21% (9) [13%,33%]	21% (9)	0% (0)
				(n=42)
	Problem 2.

Table 3 -

 3 Percentages of answers for P2 taking into account the answers for P1

	(complementary problems) and corresponding 90% probability interval estimates in
	brackets
			P1
	P2	Result R1	Equiprobable	Result R2	?
	Result R1	64% (20) [50%,77%]	75% (6) [46%,92%]	67% (2)	/
	Equiprobable 29% (9) [17%,43%]	25% (2) [8%,54%]	33% (1)	/
	Result R2	3% (1)	0% (0)	0% (0)	/
	?	3% (1)	0% (0)	0% (0)	/
		(/31)	(/8)	(/3)	(/0)

Table 4 -

 4 Percentages of answers for P3 taking into account the answers for P1 (equivalent problems) and corresponding 90% probability interval estimates in brackets

	P1

Table 5 -

 5 Percentages of answers for P4 given taking into account the answers for P2

	(symmetrical problems) and corresponding 90% probability interval estimates in
	brackets
			P2
	P4	Result R1	Equiprobable	Result R2	?
	Result R1	57% (16) [42%,72%]	50% (6) [28%,72%]	1% (1)	1% (1)
	Equiprobable 25%

Table 6 -

 6 Percentages of answers for P4 taking into account the answers for P3

	(complementary problems) and corresponding 90% probability interval estimates in
	brackets
			P3
	P4	Result R1	Equiprobable	Result R2	?
	Result R1	60% (12) [42%,76%]	53% (8) [33%,73%]	60% (3)	50% (1)
	Equiprobable 25% (5) [12%,43%]	13% (2) [4%,32%]	20% (1)	50% (1)
	Result R2	15% (3)	33% (5)	20% (1)	0% (0)

Table 7 -

 7 Percentages

	of answers for P5 and corresponding 90% probability interval
	estimates in brackets
	Result R1	Equiprobable	Result R2	?
	Problem 5 64% (27) [52%,75%]	10% (4) [4%,19%]	24% (10)	2% (1)

Table 8 -

 8 Percentages of answers for P5 taking into account the answers for P4

	(isomorphic problems) and corresponding 90% probability interval estimates in
	brackets
			P4
	P5	Result R1	Equiprobable	Result R2	?
	Result R1	79% (19) [63%,90%]	44% (4) [21%,70%]	44% (4)	/
	Equiprobable	12% (3) [5%,27%]	11% (1) [2%,36%]	0% (0)	/
	Result R2	8% (2)	33% (3)	56% (5)	/
	?	0% (0)	11% (1)	0% (0)	/
		(/24)	(/9)	(/9)	/
	Quite a high transfer rate was observed, as 79% [63%,90%] of the participants who
	correctly answered P4, gave a correct answer first time round for P5.