Bouchra Amaury

Davide Pilet

François Frey

Taïani

• Foiling Sybils with HAPS in Permissionless Systems: An Address-based Peer Sampling Service [BFT20]

malveillants.

[EN] Advice to reader

For legal reasons, this thesis includes a summary in French ("Résumé"). Non-french speaking readers can safely skip this part.

[FR] Avis au lecteur L'essentiel du contenu de cette thèse a été rédigé en langue anglaise, conformément aux pratiques usuelles dans le domaine de l'informatique. Comme prévu par la loi, un résumé en français est inclus et constitue légalement le corps de la thèse ; la partie en anglais constituant des annexes, détaillant le contenu scientifique de ce travail.

[…] And I'm a stodgy old scientist who believes, naively, that there exists an external world, that there exist objective truths about that world, and that my job is to discover some of them.

Alan Sokal

L'ensemble des problèmes résolubles en temps polynomial est inclus strictement dans celui des problèmes dont la solution est vérifiable en temps polynomial, tout comme l'ensemble des êtres censés est inclus strictement dans celui des humains

Bibliography

Résumé I Introduction

L'apprentissage machine est un des domaines les plus importants et les plus actifs dans l'informatique moderne. Ses applications vont de l'analyse de grandes quantités de données dans des centres de données à la fourniture de services basés sur l'intelligence artificielle sur de petits appareils personnels [START_REF] Hazelwood | Applied Machine Learning at Facebook: A Datacenter Infrastructure Perspective[END_REF][START_REF] Saeid Mahdavinejad | Machine learning for internet of things data analysis: a survey[END_REF] ; des applications qui connaissent un développement rapide et un intérêt certain de l'industrie.

Cependant, la plupart des systèmes d'apprentissage machine actuels utilisent encore une architecture essentiellement centralisée. Même si l'application finale doit être délivrée sur de nombreux systèmes, parfois des millions (voire des milliards) d'appareils individuels, le processus d'apprentissage est toujours centralisé dans un centre de calcul. Ce peut être un problème notamment si les données d'apprentissage sont sensibles, comme des conversations privées, des historiques de recherche ou des données médicales [START_REF] Chen | Disease Prediction by Machine Learning Over Big Data From Healthcare Communities[END_REF].

Une solution serait d'exécuter le processus d'apprentissage sur des systèmes appartenant aux utilisateurs finaux, plutôt que dans un centre de calcul. Cela permettrait également de transférer de couteuses tâches de calcul vers les systèmes des utilisateurs finaux, plutôt que de les effectuer sur une infrastructure dédiée. Ces avantages ont amené de grands noms de l'industrie, tels que Google et Facebook, à commencer des recherches sur des architectures fédérées, dans lesquelles un serveur central organise une tâche de calcul collaborative exécutée sur plusieurs systèmes distants.

Actuellement, la catégorie la plus connue d'algorithmes d'apprentissage machine est très probablement celle des réseaux de neurones. Bien qu'il existe d'autres types d'algorithmes, de nombreuses applications remarquables sont basées sur les réseaux de neurones. Ils permettent aux ordinateurs de se comparer aux humains dans des tâches qui seraient très difficiles, voire impossibles, à effectuer avec des systèmes moins avancés. Leurs principaux inconvénients sont leur complexité et leur comportement peu prévisible, ce qui rend les applications complexes, telles que les applications distribuées, plus difficiles à réaliser qu'avec des algorithmes plus simples.

Un autre défi important pour l'apprentissage machine moderne est l'apprentissage multitâche. Pour des applications telles que la reconnaissance de l'écriture manuscrite ou de la parole, la tâche spécifique consistant à reconnaitre l'écriture ou la voix d'un individu précis est différente d'un utilisateur à l'autre. De plus, certains utilisateurs peuvent avoir des tâches plus proches que d'autres, notamment en fonction de leur localisation. L'apprentissage machine multitâche a déjà reçu un certain intérêt dans un contexte centralisé, mais les approches distribuées manquent. Nous voudrions que l'apprentissage machine distribué soit capable d'apprendre des tâches similaires mais différentes et, idéalement, d'exploiter les différents niveaux de similarité entre les utilisateurs pour optimiser encore plus le processus.

Bien qu'une telle optimisation (regrouper certains utilisateurs pour l'apprentissage) puisse être réalisable manuellement dans certains contextes, cela pourrait être plus difficile dans d'autres. Par exemple, si, pour la reconnaissance vocale, les données de localisation peuvent être utilisées pour optimiser le processus (en regroupant les utilisateurs par localité), il serait en revanche difficile dans le cadre de la reconnaissance de l'écriture manuscrite, de classifier les utilisateurs (en fonction de leur « style » d'écriture). Un bon système d'apprentissage machine distribué devrait intégrer une méthode générale pour évaluer et exploiter les différents niveaux de similarité entre tâches.

II Problème & défis

Afin de rendre réalisables les applications mentionnées précédemment, nous avons besoin d'un système d'apprentissage machine distribué multitâche remplissant certains critères : large champ d'application, données d'apprentissage gardées locales, parallélisation effective, exploitation des différents degrés de similarité entre utilisateurs, flexibilité sur l'architecture (fédérée (avec un serveur pour la coordination) ou complètement décentralisée). Nous listons ci-après les objectifs non atteints par les solutions existantes et que nous nous proposons d'atteindre dans ce travail.

Nous avons besoin d'un système qui fonctionne avec des types de modèles (d'intelligence artificielle) variés, et notamment avec les réseaux de neurones. Afin de garantir cette généricité, nous assumerons simplement dans la suite de ce travail que les modèles appris peuvent se réduire à des collections (finies) de valeurs réelles (∈ ℝ). Ce système devra permettre l'apprentissage distribué sans que les utilisateurs aient à divulguer leurs données privées, tout en étant capable d'apprendre tous en même temps (calcul parallèle). Notre système devra permettre aux utilisateurs d'apprendre des modèles similaires mais différents, en même temps et de manière collaborative. Il devra prendre en compte des degrés variables de similarité.

Notre système devra fonctionner avec les deux types d'architectures distribuées : décentralisées et fédérées. Les architectures fédérées ont un serveur central coordonnant (et/ou agrégeant) le travail de plusieurs clients. Dans une architecture décentralisée, les clients deviennent des pairs qui communiquent entre eux et collaborent sans la coordination d'un serveur central.

Nous devons également fournir un système complémentaire, capable de gérer automatiquement les différents niveaux de similarité entre tâches et de configurer le système d'apprentissage en conséquence. Ce système devra être capable de déterminer quels utilisateurs ont les tâches les plus proches afin de les faire collaborer plus étroitement dans le processus d'apprentissage.

III Contributions

Afin de répondre aux exigences ci-avant, nous proposons trois contributions dans cette thèse :

• Apprentissage machine distribué multitâche en lui-même [Chapitre 3]

• Formation de coalition applicable à l'apprentissage machine distribué multitâche [Chapitre 4]

• Application effective de la formation de coalition à l'apprentissage machine distribué multitâche et exploration des implications pratiques de la vision associée [Chapitre 5]

III.1 Apprentissage machine distribué multitâche en lui-même

Notre première contribution est notre système d'apprentissage machine distribué en lui-même. Notre système est basé sur le moyennage, une méthode communément utilisée en apprentissage distribué. L'idée est simple ; pour permettre l'apprentissage machine sur un modelè constitué d'une collection de paramètres réels, les apprenants travaillent séparément et, périodiquement, un modèle commun est construit en prenant la moyenne des valeurs apprises par les apprenants individuels, qui prendront ce modèle commun comme base pour leur prochain cycle d'apprentissage. L'avantage de cette méthode est qu'elle peut fonctionner sur n'importe quel type de modèle basé sur des valeurs réelles (ℝ), indépendamment de l'algorithme d'apprentissage utilisé, tant que celui-ci implique uniquement de modifier les valeurs, pas d'en ajouter où d'en enlever ; dans ce travail, cependant, nous nous concentrerons sur les réseaux de neurones. Ce système peut également fonctionner aussi bien avec Figure 1: 3 apprenants avec 5 modèles partiels intégrés dans la géométrie des réseaux de neurones des apprenants une architecture fédérée (les modèles sont moyennés par un serveur central) que décentralisée (avec le moyennage épidémique [START_REF] Jelasity | Gossip-Based Aggregation in Large Dynamic Networks[END_REF]). Cette méthode en elle-même ne permet par l'apprentissage multitâche. Pour le permettre, deux types de solutions sont possibles (nous introduisons la terminologie) : le partage souple de tous les paramètres et le partage rigide de certains paramètres. Partage souple signifie que, plutôt que de faire converger tous les apprenants vers un modèle unique, il leur est permis de dévier légèrement de celui-ci. Partage rigide (de certains paramètres) signifie que le modèle commun ne couvre qu'une partie du modèle appris, certains paramètres étant spécifiques à chaque apprenant.

Nous avons choisi la deuxième solution : le partage rigide de certains paramètres. La raison de ce choix est que les réseaux de neurones ont généralement une structure « fonctionnelle » : les réseaux sont divisés en plusieurs parties, chacune étant supposée avoir une fonction plus ou moins spécifique. Par exemple, en vision artificielle, les réseaux de neurones sont généralement divisés en couches, dont les premières sont supposées reconnaitre des structures simples alors que les secondes devraient les interpréter. Contrairement au partage souple de tous les paramètres, un partage rigide de paramètres prédéterminés permet aux ingénieurs de choisir les parties des modèles qui doivent être partagées et celles qui doivent rester personnelles. Notez que les réseaux de neurones comportent généralement un grand nombre de neurones équivalents : mêmes valeurs d'entrée et sortie utilisée comme entrée par les mêmes neurones. Cela permet d'utiliser le partage rigide sans savoir précisément quelles parties doivent être partagées, en désignant dans chaque partie certains neurones comme partagés et d'autres comme personnels. Avec une telle configuration, le processus d'apprentissage lui-même devrait être capable de combiner les éléments partagés et personnels de manière optimale (dans la mesure de l'optimisation permise par les algorithmes d'apprentissage des réseaux de neurones), le processus d'apprentissage réglant les poids de manière appropriée.

Nous formalisons ce système avec la notion de modèle partiel. Les modèles partiels peuvent être vus comme des briques que l'on peut utiliser pour construire un modèle complet pour chaque utilisateur. Ces modèles peuvent être liés à des portions spécifiques du réseau de neurones de chaque utilisateur, permettant ainsi de sélectionner les portions les plus pertinentes pour le partage (concrètement, moyennage) si des informations préalables sont disponibles permettant d'optimiser ce choix (sinon, il est possible de simplement partager des portions de chaque partie et de laisser l'algorithme d'apprentissage régler les poids de manière appropriée). Les modèles partiels peuvent être partagés par tous les pairs (modèle global), être spécifiques à un utilisateur (modèle local) ou être partagés par un sous-ensemble précis d'utilisateurs (modèle semi-local). La Figure 1 présente un exemple de trois apprenants avec cinq modèles partiels implémentés à des emplacements précis dans la géométrie des réseaux de neurones. Le modèle 1 (cercles bleu) est global, le modèle 2 (carrés rouges) est semi-local et les modèles 3 (triangles verts), 4 (pentagones cyan) et 5 (octogones magenta) sont locaux.

Nous avons conduit des expériences sur différents jeux de données qui ont montré que notre concept fonctionne comme prévu. Dans ces expériences, nous avons testé différentes configurations pour notre système, ce qui nous a permis de déterminer quelles configurations donnaient les meilleurs résultats. Notamment, nous avons montré que la flexibilité permise par nos modèles semi-locaux peut être exploitée pour améliorer les résultats.

Ce travail a été présenté au « 19th Symposium on Intelligent Data Analysis (IDA 2021) » sous le titre « Simple, Efficient and Convenient Decentralized Multi-Task Learning for Neural Networks » [START_REF] Bouchra | Simple, Efficient and Convenient Decentralized Multi-Task Learning for Neural Networks[END_REF].

III.2 Formation de coalition applicable à l'apprentissage machine distribué multitâche

Notre système d'apprentissage multitâche suppose que les participants soient déjà regroupés en fonction des tâches qu'ils souhaitent apprendre. Une question assez naturelle est de savoir si l'assignation des participants à des sous-modèles particuliers pourrait être automatisée. Le problème est le suivant : nous avons différents agents qui pourraient vouloir collaborer pour atteindre un certain objectif (dans notre cas, l'apprentissage machine) et leur intérêt pour cette collaboration dépend d'avec qui ils vont effectivement collaborer (ils souhaitent que leurs collaborateurs aient des objectifs proches et soient suffisamment nombreux). Les agents sont des agents économiques rationnels et ils peuvent rejeter la recommandation si celle-ci n'est pas optimale pour eux, en termes d'intérêt individuel. Cela correspond à la classe de problèmes connus sous le nom de jeux hédoniques [START_REF] Drèze | Hedonic Coalitions: Optimality and Stability[END_REF], un sous-domaine de la théorie des jeux en lien avec l'économie.

Résoudre des jeux hédoniques signifie proposer aux agents une affectation à des groupes (coalitions) telle que les agents n'ont aucun intérêt (individuellement) à dévier de cette affectation (quitter leur groupe et/ou en rejoindre un autre). Résoudre les jeux hédoniques d'une manière générique, c'est à dire proposer une solution d'équilibre dont aucun agent n'a intérêt à dévier, est mathématiquement impossible [START_REF] Aziz | Hedonic Games[END_REF]. À notre connaissance, toutes les solutions existantes se concentrent sur des sousclasses du problème [Saa+10; Ang+18; ZCY17; Mei+19]. Ces solutions sont, ou bien centrées sur des applications auxquelles la recommandation de coopération ne peut être réduite, ou bien font des assertions mathématiques (existence d'un certain type d'équilibre) qui ne sont, en général, pas valides pour la collaboration en apprentissage machine. Nous proposons donc d'abandonner l'existence d'un équilibre et fournissons une heuristique qui produit des solutions approximatives proches d'un équilibre.

La notion centrale dans les jeux hédoniques est l'utilité : l'intérêt d'un agent donné pour la coalition proposée. Pour l'apprentissage machine collaboratif, nous avons développé une formule d'utilité basée sur deux variables : une distance entre les agents dans un certain espace métrique et le nombre d'agents par groupe. Cela transforme en fait notre problème en un problème de partitionnement, que nous avons donc décidé de résoudre avec un algorithme de partitionnement. À notre connaissance, aucun algorithme de partitionnement existant n'est conçu pour résoudre un tel problème, nous devons donc en créer un nouveau. Nous avons pris comme base le fameux algorithme des k-moyennes [START_REF] Stuart | Least squares quantization in PCM[END_REF]. Cet algorithme se concentre uniquement sur la distance, mais nous avons pu adapter sa conception basée sur une optimisation locale gloutonne à notre fonction d'utilité. En utilisant deux boucles imbriquées, contrairement à l'algorithme des k-moyennes qui n'en a qu'une, nous avons réussi à créer un algorithme de partitionnement qui optimise la fonction d'utilité bivariée que nous avons définie.

Notre évaluation a montré de bonnes performances (comparées à la référence) de notre algorithme de partitionnement, tant sur des données artificielles que réelles.

Ce travail a été présenté à la « 9th International Conference on Networked Systems (NETYS 2021) » sous le titre « AUCCCR: Agent Utility Centered Clustering for Cooperation Recommendation » [START_REF] Bouchra | AUCCCR: Agent Utility Centered Clustering for Cooperation Recommendation[END_REF].

III.3 Application effective de la formation de coalition à l'apprentissage machine distribué multitâche et exploration des implications pratiques de la vision associée

Une fois notre système d'apprentissage machine distribué multitâche créé et notre algorithme de partitionnement testé sur des problèmes synthétiques ainsi que sur des problèmes réels de collaboration, la dernière étape est l'application effective de notre algorithme de partitionnement à notre système d'apprentissage machine distribué multitâche, montrant ainsi qu'il permet une assignation automatique des modèles profitable. Pour rendre cette application effective possible, nous proposons une méthode pour associer un vecteur réel à chaque apprenant (sans quoi notre algorithme de partitionnement ne pourrait fonctionner) sans divulguer ses données, en se basant sur une séquence de tests commune, effectuée par chaque apprenant sur un réseau de neurones local pré-entrainé (courte séquence d'apprentissage).

Nous avons exploré plus avant la notion d'intérêt individuel, montrant comment elle interagit avec l'apprentissage machine collaboratif et révélant les limitations des configurations les plus « collectivistes ».

Nos résultats montrent que notre système d'apprentissage machine distribué multitâche et notre algorithme de partitionnement fonctionnent ensemble comme prévu. Nous voyons également que notre système respecte les intérêts individuels des utilisateurs (les gains en termes d'intérêt général ne se font pas au prix de pertes individuelles pour certains utilisateurs).

IV Conclusion

Dans cette thèse, nous nous sommes attaqué au problème de l'apprentissage machine distribué multitâche et avons fourni une solution effective à ce problème présentant de bonnes caractéristiques que nous pouvons considérer comme représentant désormais « l'état de l'art » en la matière.

Nous espérons maintenant que cette solution sera reprise par des acteurs industriels pour une application pratique et que ce type d'approche deviendra usuel dans le domaine de l'intelligence artificielle.

V Publications

L'auteur de cette thèse, en collaboration avec ses encadrants, a publié les articles revus par les pairs suivants (les deux premiers font partie de cette thèse, les deux autres concernent des travaux plus anciens) :

• Simple, Efficient and Convenient Decentralized Multi-Task Learning for Neural Networks [START_REF] Bouchra | Simple, Efficient and Convenient Decentralized Multi-Task Learning for Neural Networks[END_REF]: Cet article présente notre système d'apprentissage machine distribué multitâche. Présenté au 19th Symposium on Intelligent Data Analysis (IDA 2021). Auteurs: Amaury Bouchra Pilet, Davide Frey et François Taïani.

• AUCCCR: Agent Utility Centered Clustering for Cooperation Recommendation [START_REF] Bouchra | AUCCCR: Agent Utility Centered Clustering for Cooperation Recommendation[END_REF]: Cet article présente notre algorithme de partitionnement pour la recommandation de coopération. Présenté à la 9th International Conference on Networked Systems (NETYS 2021). Auteurs: Amaury Bouchra Pilet, Davide Frey et François Taïani.

• Robust Privacy-Preserving Gossip Averaging [BFT19]: Réalisé avant cette thèse, cet article présente un algorithme de moyennage épidémique privé, qui permet à notre système d'apprentissage distribué multitâche de protéger la vie privée dans un contexte décentralisé. Présenté au 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2019). Auteurs: Amaury Bouchra Pilet, Davide Frey et François Taïani.

Chapter 1

Introduction I Introduction

Machine learning is one of the most important and active fields in present computer science. Its applications range from analyzing large amount of data in datacenters to providing artificial intelligencebased end-user services on small personal devices [START_REF] Hazelwood | Applied Machine Learning at Facebook: A Datacenter Infrastructure Perspective[END_REF][START_REF] Saeid Mahdavinejad | Machine learning for internet of things data analysis: a survey[END_REF]; applications which enjoy a rapid growth and major industrial interest.

Most current machine learning systems, however, are still using a mainly centralized design. Even when the final application is to be delivered in several systems, potentially millions (and even billions) of personal devices, the learning process is still centralized in a large datacenter. This can be an issue if the training data is sensitive, like private conversations, browsing histories, or health-related data [START_REF] Chen | Disease Prediction by Machine Learning Over Big Data From Healthcare Communities[END_REF].

A solution to this is to make the training process happen on user-owned devices rather than in datacenters. This would also allow offloading costly computation tasks to users' devices, rather than having to handle them on dedicated infrastructure. These advantages have led industry leaders such as Google [START_REF] Bonawitz | Towards Federated Learning at Scale: System Design[END_REF] and Facebook [START_REF] Li | Fair Resource Allocation in Federated Learning[END_REF] to start working on federated setups, were a central server organize a collaborative computation task performed on multiple distant devices.

Currently, the best known class of machine learning algorithms are most probably neural networks. While there are other kinds of systems, many remarkable applications are relying on them. They allow computers to effectively compete with humans in tasks that would be very difficult or impossible to solve with less advanced systems. Their drawback are complexity and hardly predictable behavior, which makes advanced applications, including distributed one, more complex than with simpler systems.

Another important challenge for modern machine learning is multi-task learning. For applications such as handwriting recognition or speech recognition, the precise task of recognizing an individual user's handwriting or speech is different. And some users may also be closer than other, notably depending on their location. Multi-task machine learning has already received interest in a centralized context, but distributed approaches lack. We would like distributed machine learning to be able to learn similar but different tasks, and ideally, exploit different levels of similarity between users to further optimize the process.

While such optimization (grouping users for learning) may be doable manually in some contexts, that would be more difficult in others. For example, while for speech recognition, one may use location data to set up an optimized process (grouping learners by location), for handwriting recognition, classifying hand-writers (depending on their scripting "style") is not an obvious process. A good distributed multi-task machine learning system should come with a proper way to evaluate and exploit varying levels of similarity between tasks.

II Problem & challenges

To enable the above mentioned applications we need a distributed multi-task machine learning system that will have to meet several requirements: large range of application, training data kept local, effective parallelism, exploit varying level of similarity between learners, flexibility on setup (federated (with a server for coordination) or fully decentralized). Following are the objectives that are not meet by currently existing solutions, and we are giving ourselves for this work.

We need a system that works with various kinds of models and notably with neural networks. To support this genericity, we only assume in the rest of this work that the learned models can be reduced to (finite) collections of real (∈ ℝ) values. This system must enable distributed learning without learners needing to disclose their private data, with learners being able to all learn at the same time (parallel computation). Our system must be able to allow learners to learn similar but different models, to solve similar but different tasks, at the same time, collaboratively. It must be able to take varying level of similarity between tasks into account.

Our system must be able to work with the two classes of distributed setups: federated and decentralized. Federated setup have a central server coordinating (and/or aggregating) the work of several clients. In a distributed setup, clients become peers that communicate with each other and collaborate without coordination of a central server.

We also need to provide an additional system, that would be able to automatically manage the varying levels of similarity between tasks, configuring the learning system accordingly. This system should be able to determine which learners have closer tasks so that they will collaborate more strongly during the learning process.

III Contributions

To address the above challenges, we propose three contributions in this thesis:

III.1 Distributed multi-task learning proper

Our first contribution is our distributed multi-task learning system itself. Our system is based on averaging, a commonly used method in distributed learning. The idea is simple, to allow collaborative learning of a model consisting in a collection of real parameters, learners work separately and, periodically, a common model is build by taking the average of the values learned by individual learners, which take this common model as base for the next cycle. The advantage of this method is that it should work with any kind of model based on real (ℝ) values, independently of the learning algorithm used, as long as it only involves changing the values, not adding and removing values; in the present work, though, we focus on neural networks. It also can work either in a federated setup (models averaged on a central server) of in a decentralized setup (using gossip averaging [START_REF] Jelasity | Gossip-Based Aggregation in Large Dynamic Networks[END_REF]).

By itself, this method does not allow multi-task learning. To enable it, two kinds of solutions are possible (we introduce this terminology): soft sharing of all parameters and hard sharing of some parameters. Soft sharing means that, rather than having all learners converging on a common model, they are allowed to slightly diverge from it. Hard sharing (of some parameters) means that the common model does not cover the whole model learned, some parameters are specific to each learner.

We chose the second solution: hard sharing of some parameters. The reason behind this choice is that neural networks commonly have a "functional" structure: networks are divided in parts, each being Figure 1.1: 3 learners with 5 partial models integrated in learners' neural networks geometry supposed to have a more or less specific function. For example, in artificial visions, neural networks are commonly divided into layers, the first of which being supposed to recognize simple shapes and the last one to interpret those shapes. Unlike partially sharing all parameters, completely sharing predefined parameters allows engineers to select which parts should be shared and which should be kept individual. Notice that neural networks usually include significant amount of equivalent neurons: same input values and output used as input by the same neurons. This allows to use hard sharing without knowing exactly which parts must be shared, putting some neurons of a part in a common model and keeping the rest individual. With such a configuration, the learning process itself should be able to combine common and individual elements optimally (to the extent neural networks training algorithms can optimize), the learning process itself setting the weights appropriately. We formalize this system with the notion of partial model. Partial models can be seen as bricks that can be used to build a complete model for each learner. Those models are mapped to specific portions of each learner's neural network, which allows to select the most relevant parts to be shared (concretely, averaged) if previous knowledge about that is available (else, one may just set portions of each part to be shared and let the training algorithm set the weights appropriately). Partial models can be shared by all peers (global model), be specific to a single learner (local model) or shared among a specific subset of learners (semi-local model). Figure 1.1 show an example of three learners with five partial models implemented at specific places in the neural networks' geometry. Model 1 (blue circles) is global, model 2 (red squares) is semi-local and models 3 (green triangles), 4 (cyan pentagons) and 5 (magenta octagons) are local.

We conduce experiments on various dataset which show that our design works as expected. In these experiments, we tested different configurations for our system, allow us to see which configurations give the best results. Notably, we showed that the flexibility allowed by our semi-local models can be exploited to improve results.

This work has been presented at the 19th Symposium on Intelligent Data Analysis (IDA 2021) under the title "Simple, Efficient and Convenient Decentralized Multi-Task Learning for Neural Networks" [START_REF] Bouchra | Simple, Efficient and Convenient Decentralized Multi-Task Learning for Neural Networks[END_REF].

III.2 Coalition formation for automated model assignation

Our multi-task learning approach assumes that participants have already been grouped together according to the learning tasks they seek to perform. A natural question is whether this assignation of participants to particular sub-models can be automated. The problem is the following: we have several agents that may want to collaborate towards some goal (in our case machine learning) and their interest in this collaboration depends on whom they will actually collaborate with (they want their collaborators to have close objectives and be numerous enough). The agents are rational economic agents and may reject the recommendation if it is not optimal for them in terms of individual interest. This corresponds to a class of problems known as hedonic games [START_REF] Drèze | Hedonic Coalitions: Optimality and Stability[END_REF], a subdomain of game theory linked with economics.

Solving hedonic games consists in proposing to agents an affectation to groups (coalitions) such that agents have no interest (individually) to deviate from this affectation (leaving their group and/or joining another). Solving hedonic games in a generic manner, in terms of proposing an equilibrium solution which no individual agent has interest to deviate from, is mathematically impossible [START_REF] Aziz | Hedonic Games[END_REF]. To the best of our knowledge all existing solutions focuses on subclasses of the problem [Saa+10; Ang+18; ZCY17; Mei+19]. These solutions are either centered on applications to which collaboration in machine learning can not be translated, or assume mathematical conditions (existence of some kind of equilibrium) that collaboration in machine learning does not fulfill. What we propose then is to abandon the existence of an equilibrium and provide an heuristic that outputs approximate solutions close to an equilibrium.

The central notion in hedonic games is utility: the interest an agent has for the proposed coalition. For collaborative machine learning, we developed an utility formula based on two variables: a distance between agents in some metric space and the number of agents per group. This actually makes our formalism a clustering problem, which we decide to solve using a clustering algorithm. To the best of our knowledge, no existing clustering algorithm is designed to solve such a problem, so we need to create a new one. We take as base the well known k-means algorithm [START_REF] Stuart | Least squares quantization in PCM[END_REF]. This algorithm focuses exclusively on distance, but we found that its greedy local optimization-based design could be adapted to our utility formalism. Using two imbricated loops, unlike k-means which uses a simple loop, we managed to create a clustering algorithm that optimize the utility function we defined.

Our evaluation shows good performance (compared to baseline) of our clustering algorithm on both, artificial and real data.

This work has been presented at 9th International Conference on Networked Systems (NETYS 2021) under the title "AUCCCR: Agent Utility Centered Clustering for Cooperation Recommendation" [START_REF] Bouchra | AUCCCR: Agent Utility Centered Clustering for Cooperation Recommendation[END_REF].

III.3 Evaluation of our automated model assignation system and exploration of agents individual interest

After creating our distributed multi-task machine learning algorithm and testing our clustering algorithm on synthetic clustering problems and real collaboration-related datasets, the final step done is the actual application of our clustering algorithm to our distributed multi-task machine learning system, showing that it allows profitable automated model assignation. To allow this actual application, we propose a way to associate a real vector to each learner (required for clustering to work) without disclosing their data, relying on a common benchmark ran by each learner with a locally trained (short pre-training) neural network.

We further explored the notion of individual interest, showing how it interacts with collaborative machine learning and revealing the limitations of the more "collectivist" configurations.

Our results show that our distributed multi-task machine learning algorithm and our clustering algorithm work together as expected. We also see that our system respects learners individual interest (its gains in terms of general interest do not come at the cost of individual losses for some learners).

IV Plan

We start this thesis with a literature review in the relevant fields in Chapter 2, introducing neural networks, presenting their history and the modern developments related to our work as well as the field of clustering. We the present our distributed multi-task machine learning system and its evaluation in Chapter 3 on artificial tasks and three real datasets: MNIST [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF], FEMNIST [START_REF] Caldas | LEAF: A Benchmark for Federated Settings[END_REF] and VSN [START_REF] Duarte | Vehicle classification in distributed sensor networks[END_REF], showing its efficiency and the interest of its flexible design. Our clustering system and the associated experiments are presented in Chapter 4, showing the superiority of it against baseline on both, artificial data and two real datasets: BuddyMove [START_REF] Renjith | A personalized mobile travel recommender system using hybrid algorithm[END_REF] and Wholesale [START_REF] Gonçalo | Análise do perfil do cliente Recheio e desenvolvimento de um sistema promocional[END_REF]. Finally, the combined evaluation of our distributed multi-task machine learning system and our clustering algorithm on a real application (MNIST and VSN datasets) is shown in Chapter 5, as well as an analysis of how different learners are impacted with our distributed multi-task machine learning system (more profitable for some than others).

V Publications

The author of this thesis, in collaboration with their advisors, produced to following peer-reviewed papers (the two first are part of this thesis, the two others are previous work): Chapter 2

Field review

The present work is mostly part of the machine learning field, which is a major and rich field. In this chapter we present this field and, more specifically, neural networks. We explore its history and recent advances, particularly distributed and multi-task learning. Also presented is the field of clustering and how hedonic games, a subject of game theory, can link those two fields.

I Introducing Neural Networks

Artificial neural networks are designed to reproduce the behavior of a real brain. They consist of formal neurons. They are many ways to define a formal neuron, but we are going to give one that is representative of how formal neurons are used in modern systems.

You may refer to Figure 2.1 for a graphical representation of what we are going to describe. A formal neural has several inputs 𝑥 𝑖 . They are usually real numbers (often between 0 and 1 or -1 and 1) but may also be binary. They also have a unique output 𝑦 (when you see multiple outputs for a neuron, they are just "copies" of that only output sent to various receivers). Neurons also have an activation function 𝑓. The output 𝑦 of a formal neuron is the value of the activation function evaluated on the sum of all inputs 𝑥 𝑖 weighted by a certain input weight 𝑤 𝑖 . The function 𝑓 can also have additional parameters, p, commonly a bias, a value added to the sum before computing the function. Commonly used activation functions include sigmoids (𝑓(𝑥) = 1 1+𝑒 -𝛼𝑥 ), the hyperbolic tangent (𝑓(𝑥) = tanh(𝑥)) and simple binary thresholds (𝑓(𝑥) = 𝟙 𝑥⩾𝜃 ).

Weights 𝑤 𝑖 and parameters of the activation function 𝑝 are learned using some training algorithm. The (by far) most commonly used nowadays are based on Stochastic Gradient Descent with Backpropagation, in which weights are adjusted based on the errors (backpropagated through the network from the output) the network makes on training cases for which its expected output is known. This will be discussed in more detail in the relevant place of the historical section (II.3.a).

To perform actual computations, formal neurons have to be combined is large networks (usually more than several hundreds, potentially much more). They are various possible layouts. Figure 2.2 presents a very small neural network with a classical multi-layer architecture. In this network, the first layer (neurons to the left) are not actual neuron (with an activation function) but simple inputs. The output of the network is the output of the neuron (their may also be several) to the right (which is an actual formal neuron). [START_REF] Sturgis | A logical calculus of the ideas immanent in nervous activity[END_REF]. At this time, however, the focus was on modeling and studying natural brain rather than creating artificial intelligence, those researchers being more focused on confronting their work with experimental biological reality than considering their application to computing [START_REF] Lettvin | A logical calculus of the ideas immanent in nervous activity[END_REF]. These researchers were the first to introduce the idea of formal neuron, but with the goal to study actual neurons rather than to perform real computation.

II History

II.1 First works

In the same spirit, Donald Hebb formulated a learning rule that has been later used for machine learning in a neuroscience context [START_REF] Olding | The Organization of Behavior: A Neuropsychological Theory[END_REF]. This learning rule is based on the idea that when neurons get activated at the same time, they would "link" together and (a connection between them would be created, or the weight of an existing connection will be increased), latter, one of those neurons activating would tend to activate the other. While this rule is not the most common in artificial neural networks today, it is still considered by some researchers in machine learning [START_REF] Hawkins | Biological and Machine Intelligence (BAMI)[END_REF] and is used (secondarily) in this work 1 .

We can consider the Perceptron, introduced by Frank Rosenblatt in 1958 [START_REF] Rosenblatt | The perceptron: a probabilistic model for information storage and organization in the brain[END_REF] to be the first draft of a "modern" neural network, in the sense that derivatives of it are still very common today. This old perceptron, however, was still very limited. Other neural network models proposed in this period [START_REF] Nathaniel Rochester | Tests on a cell assembly theory of the action of the brain, using a large digital computer[END_REF] did not encounter significant success.

The research on neural networks mostly stalled in the late 60s, due to the limited capabilities of old neural networks models, not being able to compute non-linear functions as simple as XOR [START_REF] Lee | Perceptrons: An Introduction to Computational Geometry[END_REF]. Also, even the best computers of this era were far too limited to effectively perform computations considered very basic in current machine learning.

II.2 The Dark Age

During this dark age for machine learning in the West, sometimes called the "Winter of Artificial Intelligence", Vladimir Vapnik and Alexey Chervonenkis, working in the "Motherland of Statistics": the Soviet Union, established the theoretical basis of learning a predictive function from a data sample, initiation what will become Statistical Learning Theory [VC71; HTF09]. However, despite being translated to English, their work was largely ignored in the context of the Cold War. This work was rediscovered in the West after the end of the war.

In the same period in the West, Paul Werbos developed the idea of backpropagation of errors in his PhD thesis [START_REF] John | Beyond Regression: New Tools for Prediction and Analysis in the Behavioral Science[END_REF] (not for neural network, but for statistical models used in social science), which was going to become a key element of neural networks training after their renewal.

In the 80s, several models of neural networks where proposed, notably Hopfield networks [START_REF] Joseph | Neural networks and physical systems with emergent collective computational abilities[END_REF] and Boltzmann machines [AHS85; Smo86] but none achieved significant success. Hopfield networks, though, are significant because they introduced the concept of Recurrent Neural Network (RNN). The specificities of these networks is that they have loops in their structure (in the simplest case, a neuron taking its own output as input for a next iteration). Those loops allow RNNs to process sequences of elements, keeping information from previous elements in "memory", unlike other neural networks. While they were too limited for real applications, later improvements to the concept allowed it to meet success.

Hopfield networks are an attempt to allow storing information in a neural network. The original principle dates back to 1974 [START_REF] Little | The existence of persistent states in the brain[END_REF]. In these network, each neuron is associated with a bit and all neurons output are connected to all others input. Weights are learned with an associative rule, based on real neurons, "neurons that fires together bind together". This would, in theory, allow Hopfield networks to memorize bit patterns, this never encountered practical application though (poor performance a lack of viable application).

Boltzmann machines are designed to learn a probability distribution. Unlike Hopfield networks, they include hidden neurons (neurons not corresponding to bits of data to learn). They may, in theory, learn any probability distribution, but in practice, outside the smallest (and not really useful) ones, are computationally impossible to train. Paul Smolensky came with a solution with his Harmonium (nowadays, the term Restricted Boltzmann machines is used). In this kind of machines, neurons are strictly divided between visible and hidden and only inter-class connections, not intra-class ones, are allowed (making the network a bipartite graph). This enabled more efficient training but was not enough to get these machines to large application success.

II.3 Renewal

In the late 80s, however, initial works on neural network models still in use nowadays (in a form close to what is in use today) began. In these years, the focus of research had shifted from reproducing biological neurons to applying known mathematical methods to neural networks.

II.3.a Stochastic Gradient Descent

The backpropagation method was combined with the classical Gradient Descent used in numerical analysis, already known in the 19th century [START_REF] Louis | Méthode générale pour la résolution des systèmes d'équations simultanées[END_REF]. This method, when used with data selected randomly from a training data set, will become the most common method used for training neural networks in current applications: Stochastic Gradient Descent with Backpropagation (SGD-BP) [RHW86; WL90] (though modern applications of this method often include some variations [START_REF] Goodfellow | Deep Learning[END_REF]). The main principle of Gradient Descent is to compare the actual output of a neural network to the excepted output for some training case and modify the networks weights to make its output closer to the expectation (following the gradient). Denoting the parameters learned by the network by 𝑚, the difference between the expected output and the actual output (loss) by 𝐿(𝑚) (estimated by evaluating a batch of training cases) the generic formula for updating parameters with gradient descent is 𝑚(𝑡 + 1) = 𝑚(𝑡) -𝜆∇𝐿(𝑚). In this formula, 𝜆 is a parameter call the learning rate. If it is too low, the convergence will take too long, if it is too high, convergence may not happen. SGD adds the idea of randomly picking training cases from a pool. This is commonly implemented with mini-baches, which are sets of elements randomly selected from the whole pool of training data (training set). In SGD, the training process is done on a succession of such mini-batches, by opposition to classical Gradient Descent, where a succession of batches, consisting of the full training set, is used. Neural networks need a large amount of samples for training, but while it is necessary to have numerous different samples, processing the same sample several times, with other different samples in between, is also beneficial. Finally, backpropagation (applied in this context) consist in propagating the gradient value from output to input over the multiple layers of a multi-layer neural network (or over the multiple iterations of a recurrent neural network), effectively allowing using gradient descent to train modern neural networks.

The 90s saw interest in neural networks works grow gradually. We notice that, as early as in 1991, the concept of "transfer learning", which is the origin of works in both distributed machine learning and multi-task machine learning, was introduced [START_REF] Lorien | Direct Transfer of Learned Information Among Neural Networks[END_REF] (even though most researchers in these fields seem to have forgotten this pioneering work, maybe due to the lack of outcomes with the limited neural network models and computing power of the early 90s).

The renewal of neural networks was complete in 1998 with Yann LeCun's work with the Multi-Layer Perceptron (MLP) [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF]. In this kind of neural network, neurons are organized in successive layers from the input (data to classify) to the output (classification of data). In each layer, each neuron is connected to all neurons of the previous layer. Using this kind of neural network in conjunction with SGD, they managed to achieve very good accuracy in handwritten digit recognition, opening the world of real-life applications to neural networks. MLPs can be applied in many situations involving the interpretation of multiple real-valued inputs; for example when analyzing Fourier transformed acoustic or seismic waves [START_REF] Duarte | Vehicle classification in distributed sensor networks[END_REF].

II.4 Variants

In this history, we have focused on important direct-line ancestors of the work presented in this manuscript but other branches of the research on neural networks deserve to be mentioned, either because, while not used in this work, they are important in model artificial intelligence or because they inspired some secondary elements of this work.

A very well known type of neural network not directly liked with the present work is Long Short-Term Memory (LSTM) [HS97; Ger99; GSC00], which, unlike MLP, focuses on the analysis of sequences and next element prediction. LSTM is a Recurrent Neural Network (RNN) able to learn with Stochastic Gradient Descent with Backpropagation. While SGD-BP has always been technically applicable to RNN [START_REF] Rumelhart | Learning Internal Representations by Error Propagation[END_REF], it faced a serious issue called vanishing gradient, with the loops in the network causing the gradient to be lost over iterations due to numerous multiplications with < 1 values. LSTM's architecture solved the issue, introducing "Constant Error Carousel", additional values only present to keep errors over iterations by reducing the number of multiplications, allowing gradient to propagate over loops iterations. LSTM is probably the most used kind of neural network when it comes to prediction in sequences.

We should also mention Convolutional Neural Netowrks (CNN) [START_REF] Fukushima | Neocognitron: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position[END_REF], based on an idea that some structure should repeat at different position in a layer of neurons and often used with MLP. Being closer to how actual vision works [START_REF] Lindsay | Convolutional Neural Networks as a Model of the Visual System: Past, Present, and Future[END_REF]; this kind of neural networks met success in image recognition. MLP used in modern applications to image recognition usually have several convolutional layers as first layers.

We would also mention Hierarchical Temporal Memory [START_REF] Hawkins | Biological and Machine Intelligence (BAMI)[END_REF] which is an example of modern neural network research still based on the old principles of using biology as a source of inspiration and, while not being a mainstream approach, achieving good results in moving objects recognition. A significant particularity of this kind of neural network is its use of Sparse Distributed Representation (SDR) [START_REF] Ahmad | Properties of Sparse Distributed Representations and their Application to Hierarchical Temporal Memory[END_REF] to represent data. Unlike what is usually done in computers, were we use numerical indices, or a specific bit for each value, SDR represent each value with a sparse binary vector. Values having more "in common" (closer concepts) have more similar vectors. This is inspired from how human brain actually represent concepts. SDR inspired a data representation used in a few of our experiments2 .

III Distributed learning

With the development of both machine learning and distributed systems, distributed machine learning saw significant work in the past decade. In this work, we use the term distributed to refer to situations involving computers connected by a large scale network (typically Internet). For the more classical case of a workload done on several computers in a single datacenter (called "distributed" by some authors), we use the term parallelized. Distribution can address two issues of machine learning. The first is data privacy; in applications involving, for example, health data [START_REF] Chen | Disease Prediction by Machine Learning Over Big Data From Healthcare Communities[END_REF], people involved may not want such sensitive data to be sent to a third party over the Internet. The second is the large amount of computing power required for training. Distribution allows to spread the computational process over multiple infrastructures, improving performance [START_REF] Li | Scaling Distributed Machine Learning with the Parameter Server[END_REF]. For these reasons, industry leaders like Google [START_REF] Bonawitz | Towards Federated Learning at Scale: System Design[END_REF] or Facebook [START_REF] Li | Fair Resource Allocation in Federated Learning[END_REF] got involved in research on distributed machine learning.

III.1 Definitions

For large-scale applications over the Internet, two kinds of approaches of distribution can be distinguished. Figure 2.3 illustrates these two concepts, federation and decentralization, compared to centralization. Ω designate elements in charge of coordinating the system, Σ elements in charge of pure computation tasks. In a federated setup, most computation is done locally by peers but a central server synchronizes the work of all peers. This kind of setup is considered, for example, in [START_REF] Konečný | Federated Optimization: Distributed Machine Learning for On-Device Intelligence[END_REF]. In a decentralized setup, in which peers work together without a coordinating central server (selforganization). The approaches proposed in [START_REF] Bellet | Personalized and Private Peer-to-Peer Machine Learning[END_REF] is of this class. Not all distributed learning methods are necessarily bound to one of these two kinds of setups. Methods made for one situation may sometimes be trivially adapted to the other, and sometimes, methods designed for parallelization in a data-center can be used in a distributed setup over the Internet.

III.2 Challenges

Distributed computing in general implies multiple issues which researchers interested in this field have to solve. The central challenge is, of course, to distribute the computation. Proposing a solution that also works without a central sever (decentralized rather than federated) is a significant extension of this challenge.

It is also important that the proposed approaches actually benefit of advantages offered by distributed computing. For example, it is not very interesting to propose a distributed algorithm which does not effectively parallelize computation over the network. One may also like that distribution allow them to keep their data private, at least to some extent. While this is not a key element of distributed computing, it is something that it may provide over centralized systems.

Finally, distributed computing comes with its own set of problems which researcher wants to tackle. Issues such as latency (and jitter), reliability (of the network) and large amounts of data to transfer are typical problems that affects distributed specifically. Not even talking about malicious actions.

III.3 Approaches

Distributed learning as been studied in the context of linear models in [START_REF] Ormándi | Gossip learning with linear models on fully distributed data[END_REF]. This approach proposes a fully decentralized learning method for linear models (gossip algorithm [START_REF] Demers | Epidemic Algorithms for Replicated Database Maintenance[END_REF]), relying on model averaging. The idea of model averaging is that, when you have multiple learners trying to learn the same set of parameters and those parameters are averageable values (typically, real number (ℝ)), you can make those learners learn together by periodically averaging the values they are learning.

For neural networks, parallelization of Stochastic Gradient Descent, the most common learning algorithm for neural networks, was proposed in 2011 [START_REF] Recht | Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent[END_REF]. At this time, the idea was more to provide parallelization in a large computing infrastructure rather than on the Internet. Still, this approach had the significant advantage, over previous propositions, that it did not require costly synchronization methods, making it more suitable for larger-scale application. However, being based on communicating gradients it was limited to gradient-based training and could not be applied to other methods.

Most approaches focus on Stochastic Gradient Descent, since it is by far the most commonly used training algorithms, but not all actually require the use of a gradient. Some approach rather rely on communicating models, which allow them to be applied to other learning algorithms (such as associative learning). The Federated Averaging approach proposed in [START_REF] Brendan Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF], could work with other learning algorithm, being based on averaging the learned parameters (models) rather than gradients. Some researchers also tried to improve some properties of previous approaches. For example, the authors of [START_REF] Smith | CoCoA: A General Framework for Communication-Efficient Distributed Optimization[END_REF] and those of [START_REF] Kamp | Efficient Decentralized Deep Learning by Dynamic Model Averaging[END_REF] focused on reducing communication overhead. They achieved this by replacing strictly periodic synchronization by adaptive synchronization, communicating only when peers have sufficiently diverged from the common model. A system called Het-eroFL [START_REF] Diao | HeteroFL: Computation and Communication Efficient Federated Learning for Heterogeneous Clients[END_REF] has also been proposed to manage setups in which some, but not all, devices may have stronger computation or communication limitations. In this system, some (limited) clients may use simplified models, with fewer parameters, to reduce computation and communication costs3 .

It is actually possible to define an approach that can work in both kinds of setups, federated and decentralized, under the condition that this approach relies on some primitive that can be implemented for both kinds of setup. This is the case of averaging, which can be done on a central server or in a decentralized fashion with gossip averaging [START_REF] Jelasity | Gossip-Based Aggregation in Large Dynamic Networks[END_REF]. This is the choice we made.

IV Multi-task learning

Multi-task learning comes rather naturally when thinking about distributed learning. If we have different users learning collaboratively, then maybe the tasks they want to learn are not exactly the same. For example, if we consider handwriting recognition, everyone has their own script and the optimal model to recognize it differ from people to people. Multi-task learning has first been considered outside a distributed context, when a single system is learning similar but different tasks. Let us start by exploring this area before coming back to distributed.

IV.1 Non-distributed multi-task learning

The idea between multi-task learning is that learning several similar but different tasks at the same time may be more efficient than learning them separately. This allows each task to benefit from the knowledge obtained from learning other tasks. For example, when training a neural network to perform some optic recognition task, knowledge from other optic recognition tasks may be useful, since even if the objects we want to recognize are not the same, all optic recognition tasks need to recognize some simple shapes. The FEMNIST dataset [START_REF] Caldas | LEAF: A Benchmark for Federated Settings[END_REF] is an example. Here, all tasks are character recognition but each task is associated with a specific hand-writer, with their own personal writing.

Learning multiple similar but different task with neural networks, in a non-distributed context, was first studied in 1991 [START_REF] Lorien | Direct Transfer of Learned Information Among Neural Networks[END_REF]. This approach divides a single network between a common part, used for all tasks, and several task-specific parts. This work can be considered as the beginning of transfer-learning, but this historical approach has largely been forgotten due to arriving "too early", before the real take-off of neural networks.

While the term "transfer-learning" is commonly used to refer specifically to a method of transferlearning involving changing only the last layers of a multi-layer neural network to adapt it to different tasks, transfer-learning actually covers a wide range of cases and numerous methods exist [START_REF] Ruder | An Overview of Multi-Task Learning in Deep Neural Networks[END_REF]. In fact, transfer-learning even covers cases that are not multi-task learning [START_REF] Sinno | A Survey on Transfer Learning[END_REF], which is actually a subfield of (inductive) transfer learning. For example, reusing and adapting a model learned for a first task to a second task is (transductive) transfer learning.

Multi-task learning approaches are numerous4 , but we can identify two base methods on which those approaches are based. The first is hard-sharing of a subset of parameters, in which only some parameters are shared (commonly, averaged) and are kept identical for all tasks. A modern example of such an approach is [START_REF] Lu | Fully-adaptive Feature Sharing in Multi-Task Networks with Applications in Person Attribute Classification[END_REF], where the first layers of a multi-layer neural network are shared, while the others are task-specific. The other possibility is soft-sharing, in which no parameters are kept identical for all tasks but all parameters used for each task are allowed to differ a little from other tasks, but not too much [START_REF] Duong | Low Resource Dependency Parsing: Cross-lingual Parameter Sharing in a Neural Network Parser[END_REF], which can be presented (depending on approaches) either as tying separated models together or personalizing a common model. This can be done by integrating a cost for diverging from the common model in an objective function. It is possible to combine hard-sharing of some parameters with soft-sharing of other parameters, as in [START_REF] Long | Learning Multiple Tasks with Multilinear Relationship Networks[END_REF], where the first layer of a neural network are shared and the others are task-specifics but still tied with multilinear relationships.

IV.2 Distributed multi-task learning

At the time the present work began, solutions for distributed multi-task learning were very limited. An approach for distributed multi-task learning limited to linear models (not relevant for neural networks in their modern, non-linear, acceptation) was proposed in 2016 in [START_REF] Wang | Distributed Multi-Task Learning[END_REF] (local computation of client-specific solutions followed by aggregation on a server and final adaption of local solutions) a work later improved in [START_REF] Smith | Federated Multi-Task Learning[END_REF] (communication cost, fault tolerance). This method relies on including a cost for models divergence as part of the optimization process.

An extension multi-task learning to non-linear models was proposed by [START_REF] Caldas | Federated Kernelized Multi-Task Learning[END_REF], relying on kernel methods to capture non-linearity, albeit limited to convex problems. Another method, focused on convex models and allowing decentralized learning, was proposed in [START_REF] Bellet | Personalized and Private Peer-to-Peer Machine Learning[END_REF]. In this paper, then authors proposed to use neighborhood relationships in a collaboration graph to allow peers with more of less close relationships in their tasks to learn collaboratively. The optimization process keeps peers' models close by integrating a cost for divergence; this cost being dependent on the strength of the relationship between each pair of peers. Their work has since been improved, allowing the collaboration graph itself to be learned on the fly [START_REF] Zantedeschi | Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs[END_REF].

IV.3 Concurrent works

These existing works, however, are not satisfying. Neural networks in general are not limited to linear or even convex problems. Since several teams were working on solving the, apparently important, issue of generic distributed multi-task learning for neural networks at the same time, other researchers published their own methods while the present work was being prepared. Here we give a list of those concurrent publications and explain how our proposition is, by some criteria, superior.

A significant advance in solving the problem of general distributed multi-task learning with neural networks is [START_REF] Corinzia | Variational Federated Multi-Task Learning[END_REF], relying on soft-sharing of parameters. In this paper the server and its clients are modeled by a Bayesian network5 ; during training, a shared model a client-specific models are updated to minimize the divergence6 between the observations (training data), the shared model and each client's local model. This process is done in sequence, client after client7 . Their work, however, is limited to a federated setup (not decentralized) and, moreover, they do not propose effective parallelization. Clients are supposed to take turns for running their learning process, which makes this proposal unscalable and missing the most significant interest of distributed learning.

Taking a different approach, the authors of [Jia+19] also tried to provide a solution to the problem of general distributed multi-task learning with neural networks. This approach is relying on personalization of a common model, a form of soft-sharing of parameters. It consists mainly in training a shared model with Federated Averaging8 and then continue the training locally for each client; no actual novel algorithm is proposed. This approach, however, is still limited to federated setups, not decentralized ones, and did not allow, unlike ours, to define some peers as closest to others. Also, its more a demonstration that using a pretrained generic model as base for local training is an interesting workaround rather than a direct method for distributed multi-task learning. Such a method would be a serious barrier for online training.

These imperfect solutions close the list of approaches developed concurrently to ours and published earlier. Let us now talk about interesting related approaches published after ours.

After our prepublication, some researchers also (independently) published an approach that can be regarded as a significantly restricted version of ours (averaging of some, but not all, layers of a multi-layer neural network) in [START_REF] Manoj Ghuhan Arivazhagan | Federated Learning with Personalization Layers[END_REF] (authors did not claim decentralized learning explicitly but, since our own implementation of decentralized learning is also applicable to this method, we consider it as decentralized).

Authors of [START_REF] Fallah | Personalized Federated Learning with Theoretical Guarantees: A Model-Agnostic Meta-Learning Approach[END_REF] modified the Federated Averaging algorithm to make output a shared model that could easily be personalized with a method similar to that of [START_REF] Jiang | Improving Federated Learning Personalization via Model Agnostic Meta Learning[END_REF]. Actual simultaneous training of both, shared and personalized models, was finally achieved with [START_REF] Deng | Adaptive Personalized Federated Learning[END_REF] (mixing a federatedlearned model with a jointly trained local model using a ∈ [0, 1] parameter).

All this competition demonstrates the great interest of the community in the problem this work solves. Most significant distributed multi-task learning approached are summarized in Table 2.1. In this table, "flexibility" is a subjective notion referring to the ability of the proposed approach to be adapted to different use cases and tuned for optimal functioning in those cases.

Work

Decentralized Parallel Non-linear Generic NN Direct multi-task Flexibility

[WKS16] ✘ ✔ ✘ ✘ ✔ mid [CST18] ✘ ✔ ✔ ✘ ✔ mid [Bel+18] ✔ ✔ ✔ ✘ ✔ mid [CB19] ✘ ✘ ✔ ✔ ✔ mid [Jia+19] ✘ ✔ ✔ ✔ ✘ low [BFT21b] (ours) ✔ ✔ ✔ ✔ ✔ high [Ari+19] ✔ ✔ ✔ ✔ ✔ mid [FMO20] ✘ ✔ ✔ ✔ ➖ 9 mid [DKM20] ✘ ✔ ✔ ✔ ✔ mid
Table 2.1: Distributed multi-task learning approaches in chronological order

V From distributed multi-task machine learning to hedonic games and clustering

In distributed multi-task learning in general (and in our approach in particular), it is useful to identify learners having closer tasks, as it allows to make them collaborate more closely, optimizing the learning process. While we can find come contexts in which such affectation is straightforward, for example with speech recognition, grouping users by language and/or regional variant, it is not always that obvious (we studied a such case in our experiments).

V.1 Hedonic games

An automated way to solve this grouping issue in the general case would be an important improvement. A possible approach is to adopt a formalism from economics and game theory. This formalism would consider peers as (rational) agents, with a utility function they want to maximize. The output of this function being dependent on which other agents an agent is grouped with. This kind of formalism is called a Hedonic Game [START_REF] Drèze | Hedonic Coalitions: Optimality and Stability[END_REF].

While there are many algorithms targeted at hedonic games [START_REF] Aziz | Hedonic Games[END_REF], there is no generic solution for them. It can actually be established that some hedonic games do not admit game-theoretically acceptable solutions (no Nash equilibrium, or similar equilibrium10 ) and that application to distributed multi-task machine learning can produce such unsolvable cases. Some researchers considered using hedonic games to solve practical problems. For example, [START_REF] Saad | Coalition Formation Games for Distributed Cooperation Among Roadside Units in Vehicular Networks[END_REF] worked on collaboration between roadside units in Intelligent Transportation Systems. [START_REF] Anglano | A game-theoretic approach to coalition formation in fog provider federations[END_REF] considered hedonic games in the context of Fog Computing. Application of these games to edge computing is also proposed in [START_REF] Zhang | Data offloading in mobile edge computing: A coalitional game based pricing approach[END_REF]. These games can also be applied to energy networks, as suggested by [START_REF] Mei | Coalitional Game Theory Based Local Power Exchange Algorithm for Networked Microgrids[END_REF]. Each of these articles presents its own model and algorithm, to solve the specific problem they are considering. Those models being more constrained that what would be necessary (or, at least, desirable) for application to multi-task learning, they did not suffer from above mentioned equilibrium issue.

V.2 Solving hedonic games with clustering

A possible way to solve the considered problem is to rely on methods used for clustering, a subfield of data analysis. Clustering can be defined the following way: given a set of points in some space, find a pertinent way to put those points in groups (clusters) of relatively close points (the vagueness of this definition is a characteristic of clustering, and partly explains the variety of clustering algorithms) [START_REF] Estivill-Castro | Why so many clustering algorithms: a position paper[END_REF]. This problem can be related to community detection, which produces similar output but takes a (potentially weighted) graph as input (which, unlike clustering, does not fit the target use case [START_REF] Girvan | Community structure in social and biological networks[END_REF][START_REF] Vincent | Fast unfolding of communities in large networks[END_REF]).

Let us now explore the field of clustering and the two main classes of approaches to this issue: centroid-based clustering and density-based clustering. Both define clusters with a notion of "closeness" but, for centroid-based clustering, the closeness is defined relatively to the barycenter of the cluster while for density-based clustering, it is defined relatively to neighbors. There is no "superior" vision, the reason to choose one system or the other is more philosophical: do you favor the global closeness of points or their closeness to their neighbors.

Figure 2.4 illustrates those two visions. Centroid clusters are identified by shape and density clusters by color.

V.2.a Centroid-based clustering

In this vision of clustering, the determining criterion is geometry. A cluster is a group of points determined by their distance to the barycenter of the group. This distance is the essential criterion to determine if a point is part of a certain cluster or not.

The problem of dividing a collection of elements in a metric space in 𝑘 cohesive groups has first been formulated in 1956 [START_REF] Steinhaus | Sur la division des corps matériels en parties[END_REF], though its current common name, k-means is more recent [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF].

The usual solution for this problem, Lloyd's Algorithm (commonly called k-means itself when used in the context of clustering), dates back to 1957, when it was designed as a method for pulsecode modulation (PCM, a usual way to numerically encode analog signals), even though its official publication happened in 1982 [START_REF] Stuart | Least squares quantization in PCM[END_REF]. The principle of this algorithm is to start from 𝑘 random points as "cluster centers" and then assign all points to the closest center (for them). Cluster centers are then updated (as the barycenters of the clusters) and the process is iterated until convergence (or some quality criterion is met, to shorten the process). This process is summarized in Algorithm 1.

This algorithm received a notable improvement in 2007 when its initialization phase was modified to prevent the pathological solutions this randomized local-optimizing algorithm often produced. The new algorithm is refereed to as k-means++ [START_REF] Arthur | K-means++: The Advantages of Careful Seeding[END_REF]. The principle of this new initialization process is to chose random starting points not uniformly but favoring locations far from already chosen points, to better distribute points in space.

A size-constrained variant of k-means was also proposed in 2014 [START_REF] Ganganath | Data Clustering with Cluster Size Constraints Using a Modified K-Means Algorithm[END_REF] and another in 2019 [START_REF] Tang | Size Constrained Clustering With MILP Formulation[END_REF] but these are designed to produce clusters of some target size rather than integrating cluster size in the optimization process. This is an issue for an application where a small cluster of Add 𝑝 to the group 𝑔 𝑖 for with the distance between 𝑏 𝑖 and 𝑝 is minimal 8 until No point changed group during last iteration very close points is as acceptable as a large cluster of sparser points (this issue is clearly outlined by the graphs in [START_REF] Ganganath | Data Clustering with Cluster Size Constraints Using a Modified K-Means Algorithm[END_REF]). This also holds for density-constrained variants of k-means such as [START_REF] Davidson | Agglomerative Hierarchical Clustering with Constraints: Theoretical and Empirical Results[END_REF].

A significant limitation of k-means comes for its formulation: dividing a set of points into 𝑘 clusters. k-means is not designed to leave alone points that are too far from all others. We would also note that all practical k-means algorithms are heuristics, converging to a local optimum. From a theoretical point of vue, it does not seem possible to provide a globally optimal solution to k-means in a practical way due to the k-means problem being NP-Hard [START_REF] Daniel Aloise | NP-hardness of Euclidean sum-of-squares clustering[END_REF].

Several authors tried to speed k-means up [START_REF] Elkan | Using the Triangle Inequality to Accelerate k-Means[END_REF] or to use an alternate metrics [START_REF] Paul | Clustering via concave minimization[END_REF]. The Hartigan-Wong [START_REF] Hartigan | Algorithm AS136 -A K-Means Clustering Algorithm[END_REF] is an alternative algorithm which starts with random clusters and then greedily perform exchanges between cluster to optimize the same objective as standard k-means. While the algorithm's presentation is different, this algorithm remains very similar to standard k-means. None of those work solve the limitations we identified in k-means.

V.2.b Density-based clustering

Density-based clustering identifies clusters based on density. Essentially, these algorithms consider that regions where points are closer to each other than elsewhere are clusters. The essential criterion for a point to be part of a cluster is that its closer neighbors are also part of that cluster.

The historical density-based clustering algorithm is DBSCAN, proposed in 1996 [START_REF] Ester | A Density-based Algorithm for Discovering Clusters a Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[END_REF]. Another similar algorithm was rapidly proposed to fix a defect in DBSCAN: its inability to operate in contexts where there are multiple clusters of different density. This algorithm is called OPTICS [START_REF] Ankerst | OPTICS: Ordering Points To Identify the Clustering Structure[END_REF]. DBSCAN and OPTICS are based on the same principle: starting from one point, identify how distant new points are from previously encountered points, and derive clusters from this. The main difference is that, while DBSCAN affects clusters directly based a predefined density, OPTICS orders points by distance and outputs a representation of the distances between points, from which clusters can later be extracted, usually based on a maximum distance. This is how OPTICS manages to fix DBSCAN's inability to find clusters of different density. Figure 2.5 illustrates this. This approach does not suffer from the inability to leave points alone, but the geometry of clusters it outputs is not satisfying for applications where the distance to the barycenter is the essential criterion (this criterion is ignored by OPTICS). From the output of OPTICS, it is easy to eliminate smaller clusters, leaving points alone, but this does not allow determining if those points may have joined or larger cluster. Also, there is no straightforward way to take relative distances into account when eliminating smaller clusters.

Despite those limitations, some authors still tried to use a variant of DBSCAN to solve a multitask learning problem [START_REF] Strezoski | Learning Task Relatedness in Multi-Task Learning for Images in Context[END_REF]. In this work, the problem is not formulated as a hedonic game but, in practice, it is similar. This solution, however, necessarily suffers from the above mentioned limitations of density-based clustering when applied to this domain. Another similar approach is Clustered Federated Learning [START_REF] Sattler | Clustered Federated Learning: Model-Agnostic Distributed Multitask Optimization Under Privacy Constraints[END_REF], developed in parallel to our approach, which cluster clients based on their data distribution in the context of personalized federated learning. This approach, Figure 2.5: Illustration of OPTICS however, does not take into account the size of clusters.

V.2.c Other visions of clustering

Outside the previous two main categories, we should also mention two other approaches of clustering. First, hierarchical clustering, in which the output is a hierarchy of clusters. Second, Expectation-maximization approaches, which tries to fit data with probability distributions.

Hierarchical clustering [START_REF] Rokach | Clustering methods[END_REF] is an extension of clustering in which the objective is not only to identify clusters but also sub-clusters, potentially with numerous levels (of clusters). This kind of clustering can be achieved using algorithms from the two previous categories. In the case of k-means, a possibility is simply to recursively run k-means on each of the clusters extracted. In the case of OPTICS, the post-processing algorithm can be adapted to output a hierarchy of clusters. Optimizing OPTICS application to hierarchical clustering received specific attention from some authors [START_REF] Achtert | Detection and Visualization of Subspace Cluster Hierarchies[END_REF]. A hierarchical variant of DBSCAN, HDBSCAN, also exists [START_REF] Ricardo | Hierarchical Density Estimates for Data Clustering, Visualization, and Outlier Detection[END_REF] (it is the algorithm used in [START_REF] Strezoski | Learning Task Relatedness in Multi-Task Learning for Images in Context[END_REF]).

Expectation-maximization's [START_REF] Dempster | Maximum Likelihood from Incomplete Data via the EM Algorithm[END_REF] objective is to tune the parameters of some probability distribution to fit given data. If this method is used with a mixture distribution, clusters can be derived from its output, associating each point with the sub-distribution it is the most likely to be generated by. The optimization procedure, however, is much more complex than classical clustering algorithms, which makes it less practical. Also, this approach requires the user to choose the right kind distribution to fit the data.

V.3 Finding the right clustering algorithm

This review of literature led to the following conclusion: no existing clustering algorithm fitted our needs. k-means variants do not take group size into account and lack the ability to leave agents alone, which is something that should be possible with our formalism. OPTICS can leave agents alone but its design is not connected to the geometry of groups, which we want, and it also does not take size into account. We do not consider the size-constrained variant of k-means as a solution as size, in this algorithm, is an "external" constraint, it can not be balanced with geometrical considerations.

In Table 2.2 what can be achieved with state-of-the-art k-means and OPTICS, compared to what the approach we developed, AUCCCR (pronounced "okr", IPA: [okʁ]) can achieve.

Algorithm

Geometry Leave alone Cluster size k-means

✔ ✘ ✘ OPTICS ✘ ✔ ✘ AUCCCR (ours) ✔ ✔ ✔
Table 2.2: Our clustering algorithm compared to state-of-the-art

VI Conclusion

Machine learning is a major and large field in modern computer science. Its history is rich of innovation, transdisciplinary work and creativity. While early works did not meet great success, causing artificial intelligence to remain regarded as science-fiction for decades, recent years took it to the path of glory. Machine learning is now an overactive field with numerous problems identified, formulated and solved. Distributed multi-task machine learning is one of those problems that receive significant attention since few years. A problem the present work contributes to solve.

While less prestigious than machine learning, clustering is also a rich domain of research. Subfield of the not less rich data analysis system, it has many applications and various formulations and associated algorithms. Adding distributed multi-task machine learning to the list of its applications and providing an associated algorithm is also a significant part of the present work.

Hedonic games are a rather theoretical subject, part of game theory and linked to economics. Making hedonic games a link between machine learning and clustering adds to the possible applications of this subject and contributes to enrich it.

24/116

Chapter 3

Simple, Efficient and Convenient Decentralized Multi-Task Learning for Neural Networks I Introduction

A critical requirement for machine learning is training data. In some cases, a great amount of data is available from different (potential) users of the system, but simply aggregating this data and using it for training is not always practical. The data might for instance be large and extremely distributed and collecting it may incur significant communication cost. Users may also be unwilling to share their data due to its potential sensitive nature, as is the case with private conversations, browsing histories, or health-related data [START_REF] Chen | Disease Prediction by Machine Learning Over Big Data From Healthcare Communities[END_REF].

To address these issues, several works have proposed to share model-related information (such as gradients or model coefficients) rather than raw data [START_REF] Recht | Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent[END_REF][START_REF] Konečný | Federated Optimization: Distributed Machine Learning for On-Device Intelligence[END_REF][START_REF] Brendan Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF]. These approaches are however typically mono-task, in the sense that all users are assumed to be solving the same ML task. Unfortunately, in a distributed setting, the problems that users want to solve may not be perfectly identical. Let us consider the example of speech recognition being performed on mobile device. At the user level, each has a different voice, and so the different devices do not perform exactly the same task. Similarly, at the level of a country or region, language variants also lead to variations between tasks. For example users from Quebec can clearly be separated from those from France. A decentralized or federated learning (a concept supported by industry leaders such as Google [START_REF] Bonawitz | Towards Federated Learning at Scale: System Design[END_REF] and Facebook [START_REF] Li | Fair Resource Allocation in Federated Learning[END_REF]) platform should therefore accommodate for both types of differences between tasks: at the level of single users and at the level of groups of users.

Multitask learning has been widely studied in a centralized setting [START_REF] Ruder | An Overview of Multi-Task Learning in Deep Neural Networks[END_REF]. Some distributed solutions for multitask learning exist, but they are typically limited to either linear [START_REF] Ormándi | Gossip learning with linear models on fully distributed data[END_REF] or convex [Smi+16; Bel+18; ZBT19] optimization problems. As a result, they are typically not applicable to neural networks, in spite of their high versatility and general success in solving a broad range of machine learning problems. Some recent preprints have proposed approaches for multitask learning with neural networks in federated setups, but they have more or less significant limitations (no parallelism, lack of flexibility, no decentralization) [CB19; Jia+19; Ari+19].

In this chapter, we introduce a novel effective solution for decentralized multi-task learning with neural networks, usable in a decentralized or federated setup. Its novelty is twofold. First, to the best of our knowledge, it is the first to combine decentralization, the ability to address multiple tasks, and support for general neural networks. Second, it provides a flexible approach that can operate without knowing the nature of the differences between peers' tasks, but can still benefit from such knowledge when available, as our experimental evaluation suggests.

Our approach relies on model averaging, already used in non-multi-tasks federated learning, but its key idea consists in making the averaging partial. First, it enables partial averaging of peer models by making it possible to average specifics subsets of model parameters. Second, it makes it possible to average those subsets only among peers that share similar tasks if this knowledge is available. Experimental results show that partial averaging outperforms both local learning and global averaging.

In the following, we present our distributed multi-task learning system (model, principle, algorithm), perform a theoretical study of the associated learning process and experimentally evaluate the system on various tasks.

II The method

II.1 Base system model

We consider a federated/peer-to peer-setup where each local device (peer), 𝑝, has an individual dataset, 𝐷 𝑝 , and maintains a model consisting of a neural network, 𝑁 𝑝 . We use the notation 𝑁 𝑝 .train(𝐷 𝑝 ) to mean that peer 𝑝 trains its neural network 𝑁 𝑝 with some training algorithm on dataset 𝐷 𝑝 . Similarly, the notation 𝑁 𝑝 .test(𝐷 𝑝 ) means that the network is tested using 𝐷 𝑝 , returning a success rate (accuracy) ∈ ℝ + . Each peer seeks to maximize the success rate of its neural network when tested with its data provider.

Each neural network, 𝑁 𝑝 , is divided into parts (one or more) of neurons consuming the same inputs (with different weights), activation function (with different parameters) and with their outputs treated equivalently:

𝑁 𝑝 = (𝑁 𝑝 0 , …, 𝑁 𝑝 𝑘 ) 1 .
The essential idea of a part is that neurons in a part can be treated equivalently and permuted without altering the computation. This corresponds, for example, to a fully connected layer, but not to a convolutional layer [START_REF] Lecun | Convolutional networks for images, speech, and timeseries[END_REF], which must be divided into several parts (since neurons in a convolution layer do not share the same inputs). Parts consist of several neurons and an associated activation function: 𝑁 𝑝 𝑖 = ((𝑁 𝑝 𝑖,0 , …, 𝑁 𝑝 𝑖,𝑘 ), 𝑓) (Theoretically this definition is actually equivalent to having specific activation functions for each neuron, since a real parameter can be used to index activation functions in a finite set of neurons)2 . The activation function 𝑓 is a real function with real parameters ℝ × ℝ 𝑘 → ℝ. Each neuron 𝑛(𝑛 is used instead of 𝑁 𝑝 𝑖,𝑘 for readability) consists of a weight vector and a vector of activation-function parameters, both vectors are real-valued, 𝑛 = (w, q) ∈ ℝ 𝑗 × ℝ 𝑘 . w and q may be learned by any training method. Neurons take an input vector, i ∈ ℝ 𝑘 , and return a real value, 𝑓(i ⋅ w, q).

The neurons of a part all have the same input (but some input coordinates may have a fixed 0 weight, as long as this is the case in all peers' neural networks), which can be either the output of another part or the input of the network itself. For modeling, we consider that the input arrives at designated input parts, consisting of neurons which just reproduce the input and are not updated in training. Bias neurons, outputting a constant value, are not considered, since their behavior is equivalent to introducing a bias as activation function parameter. Since they have fixed parameters, input parts are implicitly excluded from the collaborative learning process, since they simply do not learn.

A peer's neural network may include parts that do not exist for all peer's networks.

II.2 General idea

We reuse the mechanism of model averaging proposed for federated learning [START_REF] Brendan Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF], but adapt it to allow multi-task learning in a decentralized setup. More specifically, our intuition is that the model of similar but different tasks can be divided into different portions that represent different levels of "specialization" of each task. A simple application of this principle consists for instance in dividing the model of each task into a global section, shared by all tasks and used for collaborative learning, and a local section, specific to the task at hand. This is similar in a way to transfer learning [START_REF] Lorien | Direct Transfer of Learned Information Among Neural Networks[END_REF], albeit applied to a multi-task decentralized set-up.

A key property of our approach consists in not limiting this split to a pair of global/local submodels. Since different peers involved in multi-task learning may have more or less similar functions to learn, we allow peers to have portions of their neural networks that are averaged with only a subset of other peers. The result is a partitioning of each peer's neural-network into several portions, each to be averaged with a specific subset of the peers. We refer to such portions as slices and to the model associated with a slice as a partial model. Slices are independent of parts. They can correspond to a part, a set of parts or span over several parts they cover only partially.

Summing up, our system uses averaging to enable decentralized learning; but we make this averaging partial along two dimensions. First, peers average only limited portions of their neural networks. This causes peers to retain local portions of their models thereby enabling multi-task learning. Second, averaging operations do not necessarily involve all peers, rather a peer can average each of its slices with a different subset of peers. This makes it possible for peers that share similar tasks to share some parts of their models while further specializing others.

Unlike modern non-distributed multi-task learning approaches commonly referred to as "transfer learning" [Rud17], we do not constrain the task-specific local portions of a model to consists of its last few layers. Rather, we enable complete freedom in the definition of which portions of the neural network are averaged. Once slices have been defined, the decentralized learning process automatically captures the differences between the tasks associated with different peers. In general, the partitioning of a peer's neural network into slices can be completely independent of the nature or the number of tasks in the decentralized or federated learning environment. However, knowledge of the differences between tasks can enable further optimization, for example by defining that peers with similar tasks should average some of their slices together.

With our system, the differences between peers' respective tasks will automatically be integrated by the decentralized learning process, in the learned parameters, without requiring a specific learning process nor manual setting (using a generic configuration for hyperparameters). It would still be possible, though, to use knowledge of the differences to optimize the system (custom hyperparameters), by grouping peers with more similar tasks or choosing specific portions of the neural network for averaging.

In the following, we provide a formal description of our method.

II.3 Detailed approach

In local learning, each peer learns a specific model; in non-multi-task distributed learning, all peers learn a single model that is shared with every other peer. Our distributed multi-task learning system introduces the notion of partial models. Each peer learns a set of partial models; each of which can be learned by one, some or all peers. Figure 3.1 gives an example of peers with partial models. We can we classify models into three categories. A global model consists of a partial model shared by all the peers. A semi-local model consists of a partial model shared by several but not all peers, while a local model consists of a partial model associated with only one peer. A peer has at least one model of any type, but none of the types is required.

To implement our partial models, we define slices as disjoint sets of neurons that cover a peer's entire neural network: 𝑁 𝑝 = ⨄ 𝑖 𝑆 𝑝,𝑖 , where 𝑆 𝑝,𝑖 is a slice (⨄: disjoint union). Each slice consists of a portion of a peer's neural network that is averaged on a specific subset of peers. Figure 3.2 gives an example of neural network divided into parts (dashed rectangles) and slices (nodes (neurons) of same color and shape). A peer implements a partial model by associating one of its slices with it. If the implemented partial model is global or semi local, this involves averaging the slice with the peers that also implement the same partial model. We also define a notion of dependency between partial models. If a peer implements a partial model (associating it with one of its slices) it must also implement all the models on which it depends. For example a partial model that recognizes Québécois French may depend on a model that recognizes generic French. Dependency defines a partial order (the relationship is antisymmetric and transitive) on the set of models; if A depends on B, we say that A is lower than B. This allows us to determine how to average inter-model weights. An example of models of different types with dependency relationships is given in Figure 3.3 (boxes ares partial models, arrows are dependency relationships).

II.3.a Partial averaging

Partial models allow us to implement partial averaging, as opposed to global averaging of the whole neural network, as done in non-multi-task collaborative learning [START_REF] Brendan Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF]. For each partial model, we only average the slices associated with it at the different peers that implement it.

When averaging the slices (one for each peer) associated with a partial model, we average all the activation-function parameter vectors, q, of associated neurons, and a subset of the input weights (a subset of each of w's elements). Specifically, we average all the intra-model weights, i.e. those connecting two neurons in the same slice. For inter-model input weights, we rely on the notion of dependency between partial models. Specifically, we average only inter-model weights that connect a model to the models it depends on in either direction. If we have model A that depends on model B, we average inter-model weights of neurons of A from neurons of B and those of neurons of B from neurons of A. In other words, the input weights of neurons are not necessarily averaged with the model associated with the neurons they are part of, but rather with the model that is lower in the dependency hierarchy between the model of the neuron they are part of and the model of the neuron from which the input comes; if no such hierarchical relationship exists (the set of all models being only partially ordered by the dependency relationship), the weights are kept local.

The notion of dependency ensures that inter-model weights have the same meaning for all the peers implementing a model. For example, in Figure 3.4b, the red model can be Québécois, while the blue model may be generic French. We average inter-model weights among the peers that implement the Québécois model. If there is no dependency between two models (Figure 3 remain local to each peer. It would in principle be possible to average such weights among all peers that implement both partial models at the same time, but this would add significant complexity to the process for limited gain. An example of 3 peers with 5 partial models and dependency relationships is given in Figure 3.5.

II.4 Mathematical formalization

Our system has been developed with an operational approach. For this reason, the description we provided, while detailing how our system effectively works in its application context, does not include a mathematical formalization. Averaging is nothing new or complex but our partial averaging and associated dependency system follows a logic which is interesting to formalize. Let us now present such a mathematical formalization. This generic mathematical formalization is abstracted from the neural network context, which would allow it to be extended to other machine learning systems.

As explained before (Section II.3.a), the dependencies are a design choice of engineers under the constraint that the dependency relationship must be an order relationship (antisymmetric and transitive). Since a model does not depend on itself, this order is strict and will be noted 𝑚 2 ≺ 𝑚 1 (𝑚 2 depends on 𝑚 1 ).

For this more generic formalism, we use the generic notion of parameter, which, in the case of neural network, is a generalization of weights and activation function parameters.

An important feature of neural network is their geometry, all parameters are not equivalent. This fact is largely used by our partial averaging system, so we need to preserve it for this more generic formalism. To this end, we introduce the notion of cell, in order to capture this geometrical organization of parameters. In the case of neural network, a cell represents a neuron, though it may be associated Obviously, the developers creating the models and implementing them locally have to ensure that all models implementation have the same internal topology on all peers, same for the connections between a model's implementation and its dependencies' implementations. Cells being local to each peer, the formalism itself does not guarantee that local topologies will be compatible. Models' topologies must be defined once before being implemented by peers. We denote the fact that some cell 𝑐 is part of an implementation of model 𝑚 by 𝑐 ⊢ 𝑚. Let us now explain how we formalize model topologies to allow the system to know exactly which elements should be averaged together.

With our formalism, machine learning models (e.g. neural networks) are seen as (undirected) multi-hypergraphs (hypergraphs with "loops" and duplicate hyperedges)3 , with cells as vertices (which we consider to be numbered and, thus, ordered) and parameters as hyperedges 4 . In this formalization, we will consider cells and vertices, as well as parameters and hyperedges, to be equivalent. With this visualization, each peer has a local multi-hypergraph and each model an associated multi-hypergraph. Each peer's implementation of a model corresponds to the sub-multi-hypergraph of the peer's multihypergraph restricted to the cells (vertices) associated with the said model. We assume that each model's multi-hypergraph's vertices (cells) are identified by an index and, when extracting a submulti-hypergraph, vertices (cells) are renumbered from 0 (or 1) preserving their order. We call this index 𝜒 𝑚 (𝑐) (for cell 𝑐 and model 𝑚). We also assume that hyperedges (parameters) sharing the same set of associated vertices are indexed by a function 𝜛(𝑒) (these indexes are not unique among all hyperedges, just among those sharing the same "ends"). The structure of each model is capture by a multi-hypergraph, and each peer that implements this model must have a sub-multi-hypergraph, the implementation of the model, that is identical (indexes taken into account) to the multi-hypergraph of the model.

In addition, we assume that there is only one proper (known to all peers) way to connect a given set of cells from different models 5 . This means that, when two peers have parameters connecting different models, these parameters can be considered to be equivalent (with indexes respected). We also assume that models themselves share a common indexing 𝜒(𝑚) (i.e., a model is number 1, another number 2, etc, and these indexes are common to all peers, no matter which models they implement).

Since we work in a distributed context, we call the parameter vector of each peer z 𝑝 , and individual parameters (elements of this vector) 𝑧 𝑝 𝑖 (𝑧 𝑝 𝑖 ∈ ℝ). Now, we call Π the set of all valid references ("pointer") to some 𝑧 𝑝 𝑖 (∼ a couple (𝑝, 𝑖)). In the following, 𝜋 ∈ Π is some element of Π (𝜋 is a generic way to refer to a parameter as a variable, not as its value). Each 𝜋 is associated with one or more cell(s) (in a neural network, one for activation function parameters, two for weights). We denote 𝐶(𝜋) the set of cells associated with a parameter. We also denote by 𝜇(𝑐) the model a cell 𝑐 is associated with. Now, we can define 𝑀 (𝜋) = {𝜇(𝑐)|𝑐 ∈ 𝐶(𝜋)} the set of all models associated with a parameter 𝜋, which we could also write 𝑀 (𝜋) = 𝜇[𝐶(𝜋)].

Noting 𝒞 the set of all cells and ℳ the set of all models, we have: Now, we want to find a minimal set of models (ideally a singleton) to associate each 𝜋 with for averaging. To this end, we define the reduced set of models associated with 𝜋 as follows 𝑅(𝜋) = {𝑚|𝑚 ∈ 𝑀 (𝜋) ∧ ¬∃𝑚 ′ ∈ 𝑀 (𝜋), 𝑚 ′ ≺ 𝑚}. In a less formal language, we obtain 𝑅(𝜋) from 𝑀 (𝜋) by removing models which have other models depending on them in the set; 𝑅(𝜋) is the set of all minimal elements (relatively to ≺) of 𝑀 (𝜋). For example, if 𝑀 (𝜋) = {𝑚 1 , 𝑚 2 , 𝑚 3 } and 𝑚 2 ≺ 𝑚 1 then 𝑅(𝜋) = {𝑚 2 , 𝑚 3 }. Let us prove the existence and unicity of 𝑅(𝜋).

𝐶 ∶ Π → 2 𝒞 , 𝜇 ∶ 𝒞 → ℳ and 𝑀 ∶ Π → 2 ℳ . Taking ∶ 2 𝒞 → 2 ℳ

Existence (constructive):

To construct 𝑅(𝜋) you can simply remove from 𝑀 (𝜋) all elements which are greater than some other element of 𝑀 (𝜋). 𝑅(𝜋) is not empty since, being a partial order on a finite set (ℳ), ≺ is well-founded, which means all subset of ℳ (notably 𝑀 (𝜋)) contain at least one element 𝑚 verifying (∀ 𝑚 ′ ∈𝑀(𝜋) ¬𝑚 ′ ≺ 𝑚).

Unicity: Suppose that we have two set different sets 𝑅(𝜋) and 𝑅(𝜋) ′ all ∈ 𝑀 (𝜋). We can suppose without loss of generality that there is some 𝑚 such that 𝑚 ∈ 𝑅(𝜋) ∧ 𝑚 ∉ 𝑅 ′ (𝜋). Then there are two cases.

First case, ∃𝑚 ′ ∈ 𝑀 (𝜋), 𝑚 ′ ≺ 𝑚 which is in contradiction with the definition of 𝑅(𝜋). Second, ∀𝑚 ′ ∈ 𝑀 (𝜋), ¬(𝑚 ′ ≺ 𝑚), but in that case, 𝑚 ′ should be ∈ 𝑅 ′ (𝜋) by definition, so this is also a contradiction.

If 𝑅(𝜋) is a singleton, the parameter 𝜋 will be averaged as part of the unique element (model) of 𝑅(𝜋). If 𝑅(𝜋) is not a singleton, the less complex solution is to keep 𝜋 local, but theoretically 𝜋 could be averaged among all peers implementing all elements (models) of 𝑅(𝜋). In that case, 𝑅(𝜋) as a set of models could be considered equivalent to a single model 𝑚 such that ∀𝑚 ′ ∈ 𝑅(𝜋), 𝑚 ≺ 𝑚 ′ . This would however add significant practical complexity.

Note that mathematically we could have used something stronger than 𝑅(𝜋), a minimal lower bound of 𝑀 (𝜋) (a minimal set 𝐿 of elements such that ∀𝑚 ∈ 𝑀 (𝜋), (𝑚 ∈ 𝐿 ∨ ∃𝑚 ′ ∈ 𝐿, 𝑚 ′ ≺ 𝑚)) but such a set is not necessarily unique (if you have 𝑚 1 , 𝑚 2 , 𝑚 3 , 𝑚 4 , with 𝑚 3 ≺ 𝑚 1 , 𝑚 3 ≺ 𝑚 2 , 𝑚 4 ≺ 𝑚 1 , 𝑚 4 ≺ 𝑚 2 , then {𝑚 3 } and {𝑚 4 } both correspond to the definition for set {𝑚 1 , 𝑚 2 }) and this has not much sens from engineering point of view due to the fact that such a set could include models not associated with any cell associated with 𝜋. Once each parameter 𝜋 reduced associated models set 𝑅(𝜋) defined, it can be averaged over all peers implementing all the models of 𝑅(𝜋). As explained before, averaging is only possible provided the different peers implement models respecting a common internal topology. To determine, among all parameters having the same 𝑅(𝜋), which should be averaged together, we rely on this common topology.

𝐶(𝜋 1 ) = {𝑐 1 }, 𝐶(𝜋 14 ) = {𝑐 2 , 𝑐 5 }, 𝐶(𝜋 9 ) = {𝑐 1 , 𝑐 3 }, 𝜇(𝑐 1 ) = 𝑚 1 , 𝑀 (𝜋 1 ) = {𝑚 1 }, 𝑀 (𝜋 14 ) = {𝑚 1 }, 𝑀 (𝜋 9 ) = {𝑚 2 }. 𝜋 1 𝜋 2 𝜋 3 𝜋 4 𝜋 5 𝜋 6 𝜋 7 𝜋 8 𝑐 1 𝑐 2 𝑐 3 𝑐 4 𝑐
We defined common topology in terms of multi-hypergraphs, requiring compatible vertices (cells) and hyperedges (parameters) indexations. With these assumptions, we can assume that there is a generic way (function (𝜋)) to index all parameters associated with a certain set of models on all peers implementing it, so these weight can effectively be averaged (all parameters with the same index are averaged together). Such a common index can be derived from the sub-multi-hypergraphs associated with 𝜌 = 𝑅(𝜋) extracted from each peer, which are identical due to assumptions (all peers share identical implementations of models and connections between models are also identical, we just need to add the rule that cells in the sub-multi-hypergraphs must be indexed first based on their model's common index and then on their index in each model's multi-hypergraphs) 6 . It is then possible to average together all parameters 𝜋 which have identical 𝑅(𝜋) and (𝜋).

II.5 Algorithm

We detail our multi-task learning process in Algorithm 2. Algorithm 3 presents a modified main loop (and an additional function) to allow cross-model averaging. We use the following notation: 𝑝 ⊩ 𝑚 means that peer 𝑝 implements model 𝑚; 𝑛 ⊢ 𝑚 (resp. 𝑖 ⊢ 𝑚) means that the neuron 𝑛 (resp. indexed by 𝑖) is part of (an implementation of) model 𝑚; 𝑚.𝑑𝑒𝑝𝑠 denotes the dependencies of model 𝑚. The notation 𝑛 ⊢ 𝑚.𝑑𝑒𝑝𝑠 (resp. 𝑖 ⊢ 𝑚.𝑑𝑒𝑝𝑠) is a short for ⋁ 𝑚 ′ ∈𝑚.𝑑𝑒𝑝𝑠 𝑛 ⊢ 𝑚 ′ (resp. ⋁ 𝑚 ′ ∈𝑚.𝑑𝑒𝑝𝑠 𝑖 ⊢ 𝑚 ′ ). For simplification, this formalization does not address index differences between peers for equivalent neurons and use 𝐼 for the set of all neuron indices. This issue can be addressed in an implementation by adding index-offset values for each model and each peer.

Those algorithms use two primitives, average and averageRestricted. The first averages a set of vectors, the second averages predefined coordinates (second parameter) of the vectors from a set (first parameter). In a decentralized setup, these functions can be implemented with a gossip-based averaging protocol [START_REF] Jelasity | Gossip-Based Aggregation in Large Dynamic Networks[END_REF], or with a private one [START_REF] Bouchra | Robust Privacy-Preserving Gossip Averaging[END_REF] for improved privacy protection. It is also possible to implement these primitives on a central server, to which peers send their models for averaging, in a federated, rather than decentralized, setup.

Essentially, all peers independently train their neural network, using some training algorithm with their local training data. Regularly, all peers synchronize and, for each model, relevant values are averaged for peers implementing this model. Relevant values being local parameters of neurons implementing the model, as well as their weights associated with neurons implementing the same model or one of its dependencies. In the cross-model averaging variant, an additional averaging is done for all pairs of models. In that case, we also average weights corresponding to links between neurons from the two models of the pair.

II.6 Discussion on implementation

II.6.a Decentralization

While our method has been designed to be applicable in a decentralized setup, it can also be used in a federated setup. Is this case, on just have to implement the averaging primitives on a central server, to which peers send their models for averaging, rather than using gossip averaging.

It is possible to have several servers as long as a model is associated with only one server. For cross-model averaging, it is required that each pair of models is associated to a unique server.

Since most computing work is done by peers and several servers can be used, this architecture belongs to Edge Computing [START_REF] Shi | Edge Computing: Vision and Challenges[END_REF].

II.6.b Privacy

While the decentralized multi-task learning method we propose does not include specific privacy protection mechanism, the way it works naturally offers some protection for users' privacy. First, only models are transmitted, not the actual (training) data, thus, the only information transmitted is about the whole data-set and not individual data elements. While this does not completely prevent inference on training data from the trained model [START_REF] Nasr | Comprehensive Privacy Analysis of Deep Learning: Passive and Active White-box Inference Attacks against Centralized and Federated Learning[END_REF], it is still a significant protection compared to transmitting the training data itself.

Also, only portions of each node's model are averaged. When the network converges to a stable state, all averaged slices will converge to the same value for all peers. All peer-specific information will end up in the non-averaged portion of the neural network, which is never transmitted, since this portion is the only thing that differentiate peers. During the first rounds, the information transmitted will be more peer specific, but since the models will not have converged to a stable state yet, this information will be very noisy.

In federated setups, since semi-locals models (see Section II.3) can be averaged on dedicated servers, this also reduces the amount of information that has to be transmitted to the central server (which averages the global model). Semi-local models may, for example, be private and limited to a specific organization's members, among all the organizations involved in the process. On a distributed setup, semi-local models are only transmitted to a limited set of peers.

Also, peers will never get to see any part of another peer's model with a centralized implementation. When implementing the method using gossip averaging, a private gossip averaging protocol, like the one proposed in [START_REF] Bouchra | Robust Privacy-Preserving Gossip Averaging[END_REF], can also be used to further limit the ability of potential malicious peers to deduce information about other peers.

III Theoretical analysis

We now present a theoretical analysis of our distributed multi-task learning process. Due to the high level of generality of our system (not limited to one specific kind of neural network or learning rule), we provide an analysis of our system's behavior compared to local learning, which can be used to adapt existing convergence proofs to our model. More precisely, we show that in the case of loss-based learning (e.g. SGD), our decentralized system is essentially equivalent to a single model that comprises the whole set of partial models on a single system.

Algorithm 3: Decentralized multi-task learning, cross-model averaging extension

Data: 𝑛𝑢𝑚 number of peers, 𝑚𝑏𝑛 number of training rounds between averaging, 𝑀, the set of all models, 𝑇, the set of all neurons' index grouped by slice (index differences between peers are ignored for concision), 𝑁 and 𝐷 as defined before Each peer 𝑝 has a parameter vector depending on time 𝑡 (discrete, ∈ ℕ; 𝑡 is incremented after each averaging step, which we assume to happen after each peers' models' updates; averaging steps synchronize all peers) 𝑥 𝑝 (𝑡) ∈ ℝ 𝑛 𝑝7 and a loss function 𝑙 𝑝 ∈ ℝ 𝑛 𝑝 → ℝ.

We start by defining a global loss function for our problem. Since all peers' parameters are associated with a partial model (which can be local, for the parameters that are not averaged; note that coordinates not averaged must be considered part of the local model of a peer, also if the cross-model averaging extension is used, each pair of models have to be considered as one additional model for this analysis), we define a global parameter vector. To this end, we just take all partial models used (in the whole system), 𝑚 0 (𝑡) ∈ ℝ 𝑟 0 , 𝑚 1 (𝑡) ∈ ℝ 𝑟 1 , …, 𝑚 𝑞 (𝑡) ∈ ℝ 𝑟 𝑞 and concatenate them: 𝑀 (𝑡) = 𝑚 0 (𝑡)𝑚 1 (𝑡)…𝑚 𝑞 (𝑡) ∈ ℝ 𝑢 (𝑢 = ∑ 𝑖 𝑟 𝑖 ). If a peer 𝑝 implements models 1, 3 and 5, then, after averaging, we have 𝑥 𝑝 (𝑡) = 𝑚 1 (𝑡)𝑚 3 (𝑡)𝑚 5 (𝑡).

To define our global loss function, 𝐿 ∈ ℝ 𝑢 → ℝ, we first define a set of functions ℎ 𝑝 ∈ ℝ 𝑢 → ℝ. ℎ 𝑝 (𝑣) is simply equal to 𝑙 𝑝 (𝑣 ′ ) where 𝑣 ′ is the vector 𝑣 restricted to the coordinates that corresponds to models implemented by peer 𝑝. For example, if 𝑣 = 𝑤 0 𝑤 1 𝑤 2 𝑤 3 𝑤 4 and the peer 𝑝 implements models 1, 2 and 4, then ℎ 𝑝 (𝑣) = 𝑙 𝑝 (𝑤 1 𝑤 2 𝑤 4 ). Since the values of parameters associated with models not implemented by peer 𝑝 have no direct influence on the output of 𝑝's neural network, it is logical that they have no influence on 𝑝's loss. Now we can simply define our global loss function as the sum of all ℎ's: 𝐿(𝑣) = ∑ 𝑝 ℎ 𝑝 (𝑣).

Let 𝑣⌞𝑘⌟ correspond to the coordinates of vector 𝑣 associated with model 𝑘. We assume that each peer uses a learning rule satisfying the following property, which holds true for common variants of SGD:

𝔼[𝑥 𝑝 (𝑡 + 1) -𝑥 𝑝 (𝑡)] = -𝜆 𝑝 (𝑡) ∘ ∇𝑙 𝑝 (𝑥 𝑝 (𝑡))
Where 𝑧 ∘ 𝑧 ′ is the element-wise product of vectors 𝑧 and 𝑧 ′ and 𝜆 𝑝 (𝑡) is the vector of the learning rates of peer 𝑝 at time 𝑡 for all parameters. Notice that we allow different parameters to have different learning rates (the learning rate is a vector, not a scalar); an idea first suggested in [START_REF] Jacobs | Increased rates of convergence through learning rate adaptation[END_REF] and on which some modern SGD-derived optimization algorithms, notably Adam [START_REF] Diederik | Adam: A Method for Stochastic Optimization[END_REF], are based. Since we use model averaging, we need to distinguish the values of peers' models before and after averaging; we use 𝑥 𝑝 (𝑡) for the value before averaging and 𝑥 ′ 𝑝 (𝑡) for the value after averaging (𝑥 ′ 𝑝 (𝑡)⌞𝑘⌟ = 𝑚 𝑘 (𝑡)) and the version of the previous formula that we apply is:

𝔼[𝑥 𝑝 (𝑡 + 1) -𝑥 ′ 𝑝 (𝑡)] = -𝜆 𝑝 (𝑡) ∘ ∇𝑙 𝑝 (𝑥 ′ 𝑝 (𝑡))
Now, for each model 𝑚 𝑘 we have:

𝑚 𝑘 (𝑡) = ∑ 𝑝|𝑝⊩𝑚 𝑘 𝑥 𝑝 (𝑡)⌞𝑘⌟ #{𝑝 | 𝑝 ⊩ 𝑚 𝑘 } 𝑚 𝑘 (𝑡 + 1) -𝑚 𝑘 (𝑡) = ∑ 𝑝|𝑝⊩𝑚 𝑘 𝑥 𝑝 (𝑡 + 1)⌞𝑘⌟ #{𝑝 | 𝑝 ⊩ 𝑚 𝑘 } -𝑚 𝑘 (𝑡) 𝑚 𝑘 (𝑡 + 1) -𝑚 𝑘 (𝑡) = ∑ 𝑝|𝑝⊩𝑚 𝑘 𝑥 𝑝 (𝑡 + 1)⌞𝑘⌟ #{𝑝 | 𝑝 ⊩ 𝑚 𝑘 } - ∑ 𝑝|𝑝⊩𝑚 𝑘 𝑥 ′ 𝑝 (𝑡)⌞𝑘⌟ #{𝑝 | 𝑝 ⊩ 𝑚 𝑘 } 𝑚 𝑘 (𝑡 + 1) -𝑚 𝑘 (𝑡) = ∑ 𝑝|𝑝⊩𝑚 𝑘 𝑥 𝑝 (𝑡 + 1)⌞𝑘⌟ -∑ 𝑝|𝑝⊩𝑚 𝑘 𝑥 ′ 𝑝 (𝑡)⌞𝑘⌟ #{𝑝 | 𝑝 ⊩ 𝑚 𝑘 } 𝑚 𝑘 (𝑡 + 1) -𝑚 𝑘 (𝑡) = ∑ 𝑝|𝑝⊩𝑚 𝑘 𝑥 𝑝 (𝑡 + 1)⌞𝑘⌟ -𝑥 ′ 𝑝 (𝑡)⌞𝑘⌟ #{𝑝 | 𝑝 ⊩ 𝑚 𝑘 } 𝔼[𝑚 𝑘 (𝑡 + 1) -𝑚 𝑘 (𝑡)] = ∑ 𝑝|𝑝⊩𝑚 𝑘 𝔼[𝑥 𝑝 (𝑡 + 1)⌞𝑘⌟ -𝑥 ′ 𝑝 (𝑡)⌞𝑘⌟] #{𝑝 | 𝑝 ⊩ 𝑚 𝑘 } 𝔼[𝑚 𝑘 (𝑡 + 1) -𝑚 𝑘 (𝑡)] = - ∑ 𝑝|𝑝⊩𝑚 𝑘 𝜆 𝑝 (𝑡)⌞𝑘⌟ ∘ ∇𝑙 𝑝 (𝑥 ′ 𝑝 (𝑡))⌞𝑘⌟ #{𝑝 | 𝑝 ⊩ 𝑚 𝑘 }
We now add the assertion that all peers implementing a model use the same learning rate for each parameter that is part of this model ∀ 𝑘,𝑝,𝑝 ′ |𝑝⊩𝑚 𝑘 ∧𝑝 ′ ⊩𝑚 𝑘 𝜆 𝑝 (𝑡)⌞𝑘⌟ = 𝜆 𝑝 ′ (𝑡)⌞𝑘⌟ = Λ 𝑘 (𝑡). If the learning rate is supposed to be variable and not depending only on 𝑡, it is possible to compute a single learning rate for all peers implementing a model or to compute an optimal learning rate locally for each peer, average all value and use this averaged value. Now we can write 𝑘 (𝑡) =

Λ 𝑘 (𝑡) #{𝑝|𝑝⊩𝑚 𝑘 } and (𝑡) = 0 (𝑡) 1 (𝑡)… 𝑞 (𝑡). 𝔼[𝑚 𝑘 (𝑡 + 1) -𝑚 𝑘 (𝑡)] = - ∑ 𝑝|𝑝⊩𝑚 𝑘 Λ 𝑘 (𝑡) ∘ ∇𝑙 𝑝 (𝑥 ′ 𝑝 (𝑡))⌞𝑘⌟ #{𝑝 | 𝑝 ⊩ 𝑚 𝑘 } 𝔼[𝑚 𝑘 (𝑡 + 1) -𝑚 𝑘 (𝑡)] = - Λ 𝑘 (𝑡) #{𝑝 | 𝑝 ⊩ 𝑚 𝑘 } ∘ ∑ 𝑝|𝑝⊩𝑚 𝑘 ∇𝑙 𝑝 (𝑥 ′ 𝑝 (𝑡))⌞𝑘⌟ 𝔼[𝑚 𝑘 (𝑡 + 1) -𝑚 𝑘 (𝑡)] = - Λ 𝑘 (𝑡) #{𝑝 | 𝑝 ⊩ 𝑚 𝑘 } ∘ ∇𝐿(𝑀 (𝑡))⌞𝑘⌟ 𝔼[𝑚 𝑘 (𝑡 + 1) -𝑚 𝑘 (𝑡)] = -𝑘 (𝑡) ∘ ∇𝐿(𝑀 (𝑡))⌞𝑘⌟
Which, when we consider all models at the same time, gives us:

𝔼[𝑀 (𝑡 + 1) -𝑀 (𝑡)] = -(𝑡) ∘ ∇𝐿(𝑀 (𝑡)) (3.1)
We are back to the same property for the global learning rule as for the local ones except that the loss function is the sum of the local losses and the learning rate of each parameter is divided by the number of peers having this parameter as part of their model.

This requires some discussion. Is having the learning rates divided by the number of peers implementing the corresponding model bad? Remember that the global loss function is a sum. If you consider the simple case where all peers have the same loss function, this mean that, compared to local learning, the (global) loss function will have its values, and thus its gradient, multiplied by the number of peers. This means that, in this case, if the learning rate was not divided by the number of peers, federated learning would be equivalent to learning with a higher learning rate, while it is reasonable to think that it should be equivalent to local learning with no modification of the learning rate, which is what we achieve with our reduced global learning rate. Put more succinctly, the reduced learning rate compensates the increased gradient.

We can summarize this analysis the following way: for a loss-based learning algorithm (typically SGD), our decentralized system is equivalent to training the whole set of partial models at once (on a single system) with a loss function that is the sum of peers local loss functions and a learning rate that is, for each partial model, divided by the number of peers implementing the model (which compensates the increased gradient induced by the sum).

In particular, we see with equation (3.1) that if the system is in a converged state, 𝔼[𝑀 (𝑡 + 1) -𝑀 (𝑡)] = ⃗ 0, then we have -(𝑡) ∘ ∇𝐿(𝑀 (𝑡)) = ⃗ 0 which means, assuming a > 0 learning rate for all parameters, that ∇𝐿(𝑀 (𝑡)) = ⃗ 0. This means that function 𝐿(𝑀 (𝑡)) is at an extremum. In practice, except if the system started at a maximum, this extremum will be a (local) minimum (since the process is descending the gradient). If the function is convex, it will in all cases be the minimum of the function 𝐿, the sum of all peers loss functions, which is thus effectively the exact function optimized by our system.

IV Application to specific neural networks

Our method is general and, to be useful, needs to be implemented with some kind of neural network.

For our experiments, we focus on the Multi-Layer Perceptron (MLP), because it is a well-known, simple and efficient kind of neural network that is easy to train (with gradient descent). We also conduct additional experiments with a second kind of neural network, a custom neural network relying on associative learning, to prove that our method is not limited to MLP and SGD.

IV.1 Multi-Layer Perceptron

We worked with a basic MLP [START_REF] Goodfellow | Deep Learning[END_REF], without convolutional layers [START_REF] Lecun | Convolutional networks for images, speech, and timeseries[END_REF]. The simple design of this kind of this well-known neural network being well suited for testing. For the same reason, we trained it using classical Stochastic Gradient Descent with Back Propagation [START_REF] Rumelhart | Learning Internal Representations by Error Propagation[END_REF], without any additions (variable learning-rate, momentum). While such additions may give better performance, we wanted to stick to the most classical case possible to keep our results clean from potential side effects of more complex designs.

For this kind of neural networks the parts are, naturally, the layers. For each layer, we can associate a fixed number of neurons with each model we want to use.

Note that, in the case of Convolution Neural Networks (CNN) [START_REF] Lecun | Convolutional networks for images, speech, and timeseries[END_REF], unlike MLP, each convolution layer is not a single part, since neurons constituting it have different inputs. Those layers could easily be kept in a single slice but partial averaging is also possible, if the layers uses siblings cells: a few constitutional cells sharing the same inputs. In that case, a set of sibling cells is a part.

Figure 3.8 gives an example of an MLP with 4 models. Here, the red model depends on green and yellow, which themselves depends on blue. Grey lines are the ones that can not be associated with a unique model (they can be associated with the (unordered) pair (𝑔𝑟𝑒𝑒𝑛, 𝑦𝑒𝑙𝑙𝑜𝑤)).

MLP will be our main test case for experiments. It will allow us to evaluate how our method works depending on various parameters.

IV.2 Associative neural network

To show how our method performs on a network that differs significantly from MLP and uses a learning algorithm different from gradient descent, we designed a custom kind of neural network using an associative learning rule (proof of concept).

A simple kind of task for an associative neural network is a completion task: given some partial input, return the complete item as output. The precise task we use is a sparse binary vector (i.e, binary vectors with few "1"s) completion task. The network must be able to complete (i.e., find missing "1"s) incomplete binary vectors after being trained on a set of (complete) vectors (the vectors the network have to be able to complete are exactly those of the training set). For example, some learned vector could be [0, 0, 1, 0, 1, 1, 0, 0, 1] and the neural network should be able to return it if given the complete vector [0, 0, 1, 0, 0, 1, 0, 0, 0] as input.

We took elements from Hopfield Networks [START_REF] Joseph | Neural networks and physical systems with emergent collective computational abilities[END_REF] for the neurons themselves and Restricted Boltzmann Machines [START_REF] Smolensky | Information Processing in Dynamical Systems: Foundations of Harmony Theory[END_REF] for the structure of the network and the data is represented using Sparse Distributed Representation [START_REF] Ahmad | Properties of Sparse Distributed Representations and their Application to Hierarchical Temporal Memory[END_REF] (a concept of sparse binary vectors in the context of neural networks). Our network is divided into a visible and a hidden layer, forming a complete (directed) bipartite graph. The activation functions are fixed thresholds (output is either 1 or 0) and the network is used for completion tasks: a partial vector (with 0 instead of 1 for some of its coordinates) is given as input and the network must return the complete vector as output. A sample of this architecture is The process is the following: the visible layer's neurons outputs are set to the values of the input vector, the hidden layers' neuron's output is computed from the values of the visible layer, finally, the visible neurons' values are updated, based on the hidden layer's values. The computation is simple: if the weighted sum of the inputs is ⩾ some threshold (hyperparameter), the output is 1, 0 otherwise. See Algorithm 4 for pseudo-code.

For learning, the network is given a complete vector as input, then the hidden layer's values are computed, finally, both layers' neurons' weights are updated. The learning rule is the following: if two neurons are active together, the weight of the link between them is increased, if one is active and not the other, this weight is decreased. Increment values depend on a fixed learning rate (half of the distance from the extreme value times the learning rate) and weights are in the interval [-1; 1]. See Algorithm 5 for pseudo-code.

V Experiments

Our experiments aim to show the efficiency of our method on simple examples and evaluate how this efficiency is affected by various parameters. While real world applications of our method are likely to be more complex, these simple examples are an efficient way to provide detailed results about our 2 𝑙 method's behavior. 8As it is classically done in machine learning, our learning process relies on the notions of batch and mini-batch. A batch is a set of training data and a mini-batch is a subset of a batch (chosen randomly). During learning, neural networks process a determined number of mini-batches.

Our results from different tasks are summarized in Figure 3.10. We see that our approach systematically outperforms local training and global training (non-multi-task federated averaging). More details in the followings subsections.

V.1 Multi-Layer Perceptron -General considerations

This section summarizes the general considerations applicable to the two test series we performed on the Multi-Layer Perceptron.

In both cases, we used a classical Stochastic-Gradient-Descent algorithm with Back Propagation [START_REF] Rumelhart | Learning Internal Representations by Error Propagation[END_REF] with a fixed learning rate of 0.1 and a sigmoid activation function 𝑓(𝑥) = 1 1+𝑒 -𝑥 . We use the following notation to describe our MLP layouts: 𝑛=𝑚=𝑝=𝑞 means that we have a four-layer MLP (input, output, and two hidden layers) with 𝑛 neurons in the first (input) layer, 𝑚 in the second, and so on. We use a similar notation to describe partial models: 𝑛-𝑚-𝑝-𝑞 means that the described model has 𝑛 neurons for the first layer, 𝑚 for the second, and so on. Since classical MLPs use full connected layers, all neurons of a layer are equivalent, thus models can be distinguished only by the number of neurons they include in each layer.

Unless explicitly stated otherwise, we use a 784=300=100=𝑘 configuration, were 𝑘 is the number of classes for the relevant task, for our MLP (two hidden layers), unless explicitly stated otherwise, a fixed learning rate of 0.1 and a sigmoid activation function 𝑓(𝑥) = 1 1+𝑒 -𝑥 . The "Accuracy" metrics, since the tasks we used with MLP are symbol recognition tasks, is simply the proportion of recognized symbols. A symbol is considered recognized if the most active neuron of the last layer corresponds to this symbol.

The "averaging level" is the number of neurons in the global model (shared by all peers), others neurons being in local models, in the second hidden layers, which contains a total of 100 neurons. The Global (∼federated averaging)

Figure 3.10: Results summary Partial averaging is 80% for all but Associative, 70% levels we commonly test are 0, 15, 30, 60, 80 and 100. Some neurons from the first hidden layer are also averaged, the exact numbers are, respectively, 0, 50, 100, 200, 250, 300 (proportional to the numbers in the first layer). The input and output layers are completely shared, except for an averaging level of 0. An averaging level of 0 is equivalent to local learning, 100 is equivalent to training a single global model (with averaging), similar to federated averaging.

In general, we present results as median values of a series of 10 independent runs with second and third quintiles in error bars. Due to the variety of setups tested, there are not many common parameters statically shared in different tests; we also have a wide variety of tests. For this reason, most test parameters are presented in each test's specific section.

V.2 Multi-Layer Perceptron -FEMNIST

The FEMNIST dataset [START_REF] Caldas | LEAF: A Benchmark for Federated Settings[END_REF] targets the recognition of 62 classes of handwritten characters (uppercase and lowercase letters, plus digits). FEMNIST is derived from the NIST Special Database 19 [Nat16], as is the well-known MNIST [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF] dataset. Compared to MNIST, FEMNIST adds non-digit characters and groups characters by hand-writer. This grouping, originally intended for nonmulti-task federated learning, can also be used for multi-task federated/decentralized learning since different writers do not have the same handwriting, creating the similar but different tasks we need to evaluate our system.

To adapt FEMNIST to the multi-task setup, we preprocess the dataset as follows. First, after partitioning the data by writer, we sort the writers by descending numbers of samples. This allows us to select the writers with the largest samples in each experiment. We also had to perform a random shuffle on the samples for each writer, since the natural order of the samples has obvious bias (big clusters of digits notably).

Our experiments simulate a peer-to-peer/federated setup. We assign exactly one writer to each peer and randomly shuffle its samples. Then we limit all peers' (writers') sets of samples to the same size, truncating the largest sets. This prevents a "super peer" bias, where one peer with a very large dataset could, alone, allow the learning process to gain greater general accuracy than all other peers. This bias would artificially increase the average accuracy, masking the interest of collaboration between multiple smaller peers. While this anti-bias rule is a great constraint that poses limitations on both, the number of peers we can include in our tests and the number of samples we can use, effectively reducing the maximum possible accuracy, we believe that it is very important to try to eliminate, has much as possible, such bias in the dataset to really prove the efficiency of distributed multi-task learning itself, without any side effects. While some could argue that dataset size disparity is present in real-world datasets, we can answer that, if the only interest of federated learning is transferring information from "rich" peers to "poor" peers, then, nothing would force those rich peers to share with poor, preferring to keep their large dataset for themselves or sell them or sell the models learned from them, making federated/distributed learning effectively useless. Thus, we will perform our analysis on peers with same size dataset, to prove the efficiency our system, even when it can not benefit from this wealth redistribution effect.

Each peers data is divided in a training and a testing section. Each test is done on three variants of the FEMNIST task. FEMNIST-A, the classical FEMNIST task, with all characters (62 classes). FEMNIST-M, were some similar-looking characters are merged in a single class as proposed in the NIST Special Database 19 documentation [Nat16] (47 classes). FEMNIST-D, limited to digits (10 classes).

We performe a total of 3 independent tests with MLP on FEMNIST, each designed to evaluate one specific aspect of our system: partial averaging efficiency (Section V.2.a), different averaging schemes (Section V.2.b), effect of the number of peers (Section V.2.c). Results are median values of 10 runs.

V.2.a Averaging level

This first experiment aims to show that performing a partial averaging is better, in the considered multi-task situation, than a complete averaging or no averaging and to determine which level of averaging is the best.

For this experiment we use 16 peers, each with a training set of 360 characters for the A and M variants, 100 for the D variant. The test set is 60 characters long for the A and M variants and 30 characters long for the D variant. The mini-batch size is 180 for the A and M variants and 50 for the D variant.

For recall, the "averaging level" is the number of neurons in the global model (shared by all peers), others neurons being in local models, in the second hidden layers, which contains a total of 100 neurons. Some neurons from the first hidden layer are also averaged, in equivalent proportion.

Each curve corresponds to a different number of mini-batch (from 30 to 1000). The averaging process is done after every mini-batch. The results are presented in Figures 3.11, 3.12 and 3.13 (in order, A, M and D variants).

From those results, we can conclude that, whatever the mini-batch number is, the best performance is always achieved using partial averaging. In general, the best performance is achieved with an averaging level of 80. This validates our partial averaging concept.

V.2.b Averaging scheme

In this experiment, we compare our approach of partial averaging of each hidden layer (in its best performing variant, 784-250-80-62, with other partial averaging schemes based on complete averaging of specific layers. Notably, this includes a configuration similar to what is commonly used in local multi-task learning approaches design as "transfer learning": sharing everything but the last layer (784-300-100-0).

For this experiment we use 16 peers, each with a training set of 360 characters for the A and M variants, 100 for the D variant. The test set is 60 characters long for the A and M variants and 30 This experiment shows that, in the FEMNIST case, whatever the mini-batch number is, partially averaging hidden layers is superior to all tested schemes based on averaging specific layers, including 784-300-100-0. This proves the interest of having a flexible system allow partial averaging of layers rather than specific layers averaging.

V.2.c Number of peers

In this experiment, we evaluate how our system's performance is affected by the number of peers. Due to the nature of the FEMNIST dataset, with hand-writers that can in no way be considered "uniform" either themselves or in their respective differences, this test will present the following particularities. First, for all "numbers of peers" tested, we actually tested 64 peers and the "number of peers" value is the number of peers sharing the same "global model". For example, the value for 16 peers is obtained by taking 4 groups of 16 peers (64 total) and performing the averaging process separately for each group. This eliminates any bias that could be exhibited if, for example, the first peers in our dataset were actually "easier". Secondly, we need to admit that another bias can still exist in our results. Even with our grouping method, some groups can be harder than others, notably, it is likely that multi-task learning is easier if you only have 4 different tasks rather than 16. Due to the nature of the FEMNIST dataset, each peer has its own, specific, task, thus, more peers mean more tasks. As a consequence, this tests is not only testing the effect of the number of peers but also the number of different tasks. While the number of peers should increase accuracy, the number of tasks Figure 3.12: Averaging level on FEMNIST-M -Accuracy for various averaging levels and numbers of mini-batches should decrease it. We have to keep this in mind when interpreting our results. Also, in addition to the number of peers, the different sets of peers may have unknown and unpredictable biases, so, we have to be careful with our conclusions. For this experiment, each peer has a training set of 350 characters for the A and M variants, 100 for the D variant. The test set is 60 characters long for the A and M variants and 30 characters long for the D variant. The mini-batch size is 175 for the A and M variants and 50 for the D variant.

Each curve corresponds to a different averaging level. 200 mini-batches were used for training. The averaging process is done after every mini-batch. The results are presented in Figures 3.17 Obviously, the line for a 0 averaging level is flat, since the number of peers has no influence in this case. It clearly appears that full averaging (100) rapidly loses efficiency when the number of peers increases, specifically at the beginning. This is due to the increased number of different tasks; an averaging level of 100 being unable to perform multi-task learning. For an averaging level of 80, we observe, however, that our multi-task learning system seems to allow effective gains.

V.3 Multi-Layer Perceptron -modified MNIST

We continue our experiments with the MLP on the well-known MNIST dataset [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF]. The task is simple: recognizing handwritten digits. To generate different but related learning tasks for each peer, we permute digits (e.g., a [9] will be labeled as "8" and vice versa). Compared to FEMNIST, this more artificial testing allows us to perform a more precise evaluation, by providing better control on the respective tasks of peers.

To obtain different training sets for different peers, we divide the MNIST training set in successive sequences. This is important because practical implementations will be likely to have peers with completely independent data; as keeping data local being one of the key features of our method. The We perform a total of 9 independent tests with MLP on MNIST, each designed to evaluate one specific aspect of our system: partial averaging efficiency (Section V.3.a), convergence (Section V.3.b), effect of the number of peers (Section V.3.c), semi-local models (Section V.3.d), semi-local+local models (Section V.3.e), effect of the level of difference between tasks (Section V.3.f), effect on the number of peers with modified tasks (Section V.3.g), effect of the training set size (Section V.3.h), use of a more problem-specific layout (Section V.3.i).

Similarly to previous experiments, results are median values of 10 runs, except for semi-local averaging, which has 20 runs (since results were closer, we wanted more samples). The error bars corresponds to the second and third quintiles.

V.3.a Averaging level

This first experiment aims to show that performing a partial averaging is better, in the considered multi-task situation, than a complete averaging or no averaging and to determine which level of averaging is the best.

For this experiment we use 16 peers, each with a training set of 3500 digits. All the training sets are different, not overlapping, parts of the whole MNIST training set (60000 digits). These choices are a compromise to have a sufficient number of peers while not reducing the training set size too much and maintaining independent training sets, with MNIST training set size limitation.

For recall, the "averaging level" is the number of neurons in the global model (shared by all peers), others neurons being in local models, in the second hidden layers, which contains a total of 100 neurons. Some neurons from the first hidden layer are also averaged, in equivalent proportion.

The averaging process is done after every mini-batch. 30 mini-batches are used for training. Differences between peers are induced by permuting digits 8 and 9 for 7 of the 16 peers, giving us a close to but not even split. The results are presented in Figure 3.20.

From those results, we can conclude that, whatever the mini-batch size is, the best performance is always achieved using partial averaging. For higher mini-batch sizes, the best performance is achieved with an averaging level of 80.

The significant drop of performance observed with an averaging level of 100 is due to fact that a unique model can not address the permutation of 8 and 9 for certain peers. This validates our partial averaging concept.

V.3.b Convergence

The point of this test is to see how the accuracy evolves during the training process.

For this experiment we tested different averaging levels, with 16 peers, a fixed mini-batch size of 100. Training sets are independent and of size 3500. The smaller mini-batch size allows finer grain in accuracy sampling (since the curve is drawn from accuracy evaluations on the test set taken after every mini-batch).

The "averaging level" is the number of neurons of the global model (shared by all peers ; others neurons being in local models) in the second hidden layer, which contains a total of 100 neurons. The levels we tested are 0, 80 and 100. Some neurons from the first hidden layer are also averaged, the At the beginning of the training, no averaging is leading and 80 averaging is last but when approaching maximum accuracy, 80 becomes first and 100 last. The three curves have similar shapes and remain very close.

V.3.c Number of peers

In this experiment, we want to evaluate how different averaging levels' performances are affected by the number of peers.

For this experiment we tested different numbers of peers, from 4 to 16, and different averaging levels with a fixed mini-batch size of 500. Training sets are independent and of size 3500.

The "averaging level" is the number of neurons in the global model (shared by all peers), others neurons being in local models, in the second hidden layers, which contains a total of 100 neurons. The levels we tested are 0, 15, 30, 60, 80 and 100. Some neurons from the first hidden layer are also averaged, the exact numbers are, respectively, 0, 50, 100, 200, 250, 300. Each curve corresponds to a different averaging level. The averaging process was done after every mini-batch. 30 mini-batches were used for training. Differences between peers are induced by permuting digits 8 and 9 for one fourth of peers (this ratio dividing evenly all tested numbers of peers). The results are presented in Figure 3.22. We see here that, obviously, the number of peers has no effect when averaging is not used. It also has a small effect with a limited averaging level but, with high level partial averaging (60-80), we get a significant performance gain when increasing the number of peers. The performance of full averaging, despite gaining from peer number increase, remains low. This indicates that partial averaging allows for performance gain when connecting more peers, giving access to more training examples.

V.3.d Semi-local averaging

Here, we want to see how semi-local models (i.e. partial models shared by several but no all peers) can improve performance, compared to just using global and local models.

For this experiment we tested different averaging schemes with different mini-batch sizes (from 25 to 150). Smaller mini-batches allowing more frequent averaging for this more difficult context. Training sets are independent and of size 200, so that the smaller mini-batches would still cover a significant portion of the training sets. We used 12 peers; a highly divisible number allowing more complex permutation patterns.

Differences between peers are induced by applying all elements of 𝔖 3 (permutations on a set of 3 elements) to the last 3 digits. The schemes tested are the following: no averaging, complete averaging of all peers' neural networks, complete averaging limited to peers with identical permutation, averaging with an 80 level of all peers' neural networks, averaging with an 80 level (784-250-80-10) of all peers' neural networks + averaging with a 20 level (0-50-20-0) of peers with identical permutation. For the Figure 3.17: Number of peers on FEMNIST-A -Accuracy for various numbers of peers per group and averaging levels last scheme, we tested two variants: in the first case, no model was declared dependent of another one, which meant that no inter-model weight was averaged, in the second case, the semi-local models were declared dependent on the global model, allowing inter-model weights between global and semi-local to be averaged with the semi-local models' internal weights. Each curve corresponds to a different averaging scheme. The averaging process was done after every mini-batch. 100 mini-batches were used for training. Each permutation is used for 2 peers (12 peers total).

Results are median values of 20 runs (more precise than 10, since results were close). The error bars corresponds to the second and third quintiles. The results are presented in Figure 3.23.

On this test, we observe that no averaging is the method with the worst performance. Full averaging is better but still less efficient than averaging per class or 80 averaging. Having a 80 global model + a 20 semi-local model ended-up being the best solution here and declaring the dependency allowed greater gains and declaring the dependency allowed greater gains, very significant for higher mini-bash sizes.

V.3.e Semi-local averaging with local models

In this test, we evaluate how a combination of global, semi-local and locals models performs.

For this experiment we tested different averaging schemes with different mini-batch sizes (from 100 to 800), allowing a medium averaging frequency, adapted to the difficulty of the task (complex permutation set, but with few peers). Training sets are independent and of size 1000. We used 4 peers, fewer peers implying that some would have unique permutations, the natural use-case for local models.

Differences between peers are induced by permuting digits 8 and 9 for peer 2 and 3 + digits 6 and 7 for peer 3. The schemes tested are the following: no averaging, complete averaging of all peers' neural networks, complete averaging limited to peers with identical permutation, averaging with an 80 level of all peers' neural networks, averaging with a 70 level (784-220-70-10) of all peers' neural networks + averaging with a 30 level (0-80-30-0) for peers 0 and 1 (id class, no intra-class difference) and an averaging with a 15 level (0-40-15-0) for peers 2 and 3 (semi-id class, some intra-class difference). For the last scheme, we tested two variants: in the first case, no model was declared dependent of another one, which meant that no inter-model weight was averaged, in the second case, the semi-local models were declared dependent on the global model, allowing inter-model weights between global and semi-local to be averaged with the semi-local models' internal weights. Each curve corresponds to a different averaging scheme. The averaging process was done after every mini-batch. 50 mini-batches were used for training.

Results are median values of 20 runs (more precise than 10, since results were close). The error bars corresponds to the second and third quintiles. The results are presented in Figure 3.24.

On this test, due to the important differences between peers, full averaging was clearly inferior to all other schemes, including no averaging. 80 averaging was better than no averaging, but still inferior to 100 averaging per class (pairs of peers with closer tasks, 0, 1 and 2, 3) with big enough mini-batches. 70 + 30 for identical peers and 15 for peers with only one common inversion was the best and declaring the dependency allowed greater gains.

V.3.f Difference rate

Here we want to see how the efficiency of different averaging levels is affected by the level of difference between peers' tasks.

We tested different averaging levels for different difference rates. The difference rate being the number of digits affected by a different permutation between peers, ranging from 0 to 10. Training sets are independent and of size 3500; mini-batch size is 500. We used 16 peers. Each curve corresponds to a different averaging level. The averaging process was done after every mini-batch. 30 mini-batches were used for training. Differences between peers are induced by applying the cycle (10 -𝑟…9) where 𝑟 is the difference rate (or no permutation if 𝑟 = 0, 𝑟 = 1 being impossible with this system) to 7 of the 16 peers output. The results are presented in Figure 3.25.

We observe that, while 100 averaging seems to be the best when there is no difference (the gap with 80 and 60 is too low to officially conclude), it is the only scheme severely affected by the difference rate, loosing more than 50% of accuracy. For other schemes, 80 and 60 are the best for low difference rate but the gap is significantly reduced when the difference rate increases. For 10, 80 seems to be inferior to other partial averaging scheme, with a level of accuracy similar to no averaging.

V.3.g Number of peers with permutation

Here we want to see how the efficiency of different averaging levels is affected by the proportion of peers with a non-trivial (id) permutation.

We tested different averaging levels for number of peers with permutation. Training sets are independent and of size 3500; mini-batch size is 500. We used 16 peers. Each curve corresponds to a different averaging level. The averaging process was done after every mini-batch. 30 mini-batches were used for training. The peers with a non-trivial permutation have 8 and 9 permuted.

Results are median values of 20 runs (more precise than 10, since results were close). The error bars corresponds to the second and third quintiles. The results are presented in Figure 3.26.

We observe that full averaging's accuracy significantly drops when the number of permuted peers increases. Full averaging is the most accurate with 0 peers with permutations (as it should be) but is only third with 2 and last for 4 to 8. As one could expect, no averaging is not affected by the number of peers with permutation. More interestingly, partial averaging schemes do not seem to be much affected by the number of peers with permutation; only a limited drop is observed for 30, 60 and 80.

V.3.h Training set size

Here we want to see how the efficiency of different averaging levels is affected by the size of each peer's training set.

We tested different averaging levels for different training set sizes (ranging from 250 to 3500). The mini-batch size is fixed at 200. We used 16 peers. Each curve corresponds to a different averaging level. The averaging process was done after every mini-batch. 50 mini-batches were used for training. Differences between peers are induced by permuting digits 8 and 9 for 7 of the 16 peers. The results are presented in Figure 3.27.

We see that the lower the averaging level is, the more the training set size is important. 100 averaging is the best for 250 set size, third behind 80 and 60 for 500, beats only 0 for 1000 and last after that. 80 is the best averaging level, except for very small training sets (size 250); 60 being second. Figure 3.20: Averaging level on modified MNIST -Accuracy for various averaging levels and minibatch sizes

V.3.i Different layouts

Due to the way we induce differences between peers, a simple post-treatment consisting in a permutation inversion would allow 100 averaging to outperform any scheme. We did not try to use this fact before to improve our averaging schemes to remain general. In this test, we evaluate how a partial averaging scheme crafted more specifically for this problem will perform.

Here we test different averaging schemes and layouts for different difference rates. The first four schemes are used with a 784=300=100=10 network layout (4 layers), while the last 4 have a 784=300=100=10=10 (5 layers) layout. Each curve corresponds to a different averaging scheme. The key difference between these two layouts is the addition of a fifth layer, which would (intuitively) learn the permutation. Training sets are independent and of size 3500; mini-batch size is 500. We used 16 peers. The averaging process was done after every mini-batch. 50 mini-batches were used for training (longer training, since some layouts are deeper than usual). Differences between peers are induced by applying the cycle (10 -𝑟…9) where 𝑟 is the difference rate (or no permutation if 𝑟 = 0, 𝑟 = 1 being impossible with this system) to 7 of the 16 peers output. The results are presented in Figure 3.28.

Complete averaging schemes see their accuracy drop severely when the difference rate increases. The 80 variant used on 784=300=100=10=10 has an accuracy close to no averaging on the same layout, lower for high difference rates. 784=300=100=10=10 layout seems less efficient than 784=300=100=10 in general, but with a 784-300-100-10-0 averaging scheme, it outperforms no averaging on 784=300=100=10 and even (but not much significantly) 784-250-80-10 for high difference rates. 784-300-100-0 appears to be the best scheme in general, beating any other scheme significantly, except in the no difference case and being less affected than 784-250-80-10 by difference rate. It is important to remember that the 784-300-100-0 was the best here due to the particular nature of the differences between peers, a permutation. This scheme was crafted specifically for this problem, which is a luxury, we could not have done this if the exact nature of the differences between peers was not precisely known. Moreover, this kind of layout is not easy to generalize to semi-local models.

V.4 Multi-Layer Perceptron -VSN

We finally test MLP on a significantly different task: vehicle recognition from sensors. We use a dataset from [START_REF] Duarte | Vehicle classification in distributed sensor networks[END_REF]. This dataset contains data from sensors (notably seismic and acoustic sensors) produced while some (military) vehicle passes near the sensors (grouped in nodes, which will be our peers).

The task proposed is to recognize the class of vehicle (assault amphibious or dragon wagon) from each sensor's data (binary classification). To allow an MLP to perform this task, the data from each set of sensors (node) is first transformed into 50 seismic and 50 acoustic features (100 total inputs). This process (based on Fast Fourier Transform) is described in the original paper ([DH04]).

For our distributed multi-task setup, we consider each node as a peer. The tasks are similar, since all peers want to classify the same kinds of vehicles from the same kind of data, but different due to the location of sensors influencing their output.

For this experiment we use 16 peers, each with a training set of 50 samples. The test set contains 200 samples. The mini-batch size is 25. We use an MLP with a 100=50=20=1 layout.

The "averaging level" is the number of neurons of the global model (shared by all peers), others neurons being part of local models, in the first hidden layer, which contains a total of 50 neurons. The levels we test are 0, 7, 15, 30, 40 and 50. Some neurons from the second hidden layer are also averaged, the exact numbers are, respectively, 0, 3, 6, 12, 16, 20. Each curve corresponds to a different mini-batch number (from 100 to 400). The averaging process was done after every mini-batch. Similarly to previous experiments, results are median values of 10 runs. The error bars corresponds to the second and third quintiles. The results are presented in Figure 3.29. This test's results are very similar to our other MLP tests. We get an optimum around 80% averaging.

V.5 Associative neural network

All our previous experiments used MLPs with SGD; now we want to see how our system performs on a different kind of neural network, with a different training method. We test associative neural networks on the following task.

We generate binary vectors of size 𝑛 (∈ 0, 1 𝑛 ) with 2𝑚 1s (and 𝑛 -2𝑚 0s). The task of the neural network is to be able to reconstruct each learned vector from an input with only 𝑚 1s. For example, the learned vector could be [0, 0, 1, 0, 1, 1, 0, 0, 1], the neural network will be given [0, 0, 1, 0, 0, 1, 0, 0, 0] as input and should be able to return the learned vector.

For training, we give the network the full vectors as input; for testing, we give the network a partial input with only 𝑚 1's and observe the output. To complicate the task, we add noise to the vectors: a fixed number 𝑧 of random bits are flipped (1 becomes 0 and 0 becomes 1) in all vectors (training and testing) before feeding them to the network.

For accuracy evaluation, the task is considered successfully accomplished if the number of matching 1's between the expected output and the actual output is greater than or equal to the number of nonmatching 1's. More formally (c is expected output, a is actual output), a test is considered successful if and only if c ∧ a contains at least as many 1's as c ⊕ a. To generate differences between peers, we simply changed, for some peers, half of the 1's that are not in the testing input. For example, from [0, 0, 1, 0, 0, 1, 0, 0, 0], some peers will have to find [0, 0, 1, 0, 1, 1, 0, 0, 1] and others [1, 0, 1, 0, 0, 1, 1, 0, 0].

Our vector generator works in the following way: it takes as input an integer 𝑘 ∈ ℕ and has a periodicity parameter 𝑠. The 1s of the vector that will be given as input for both training and testing corresponds to the coordinates 3𝑚(𝑘[𝑠]) + 𝑖 (.[.] is the modulo operation: 𝑘[𝑠] is the remainder of the Euclidean division of 𝑘 by 𝑠) with 𝑖 ranging from 0 to 𝑚 -1. The 1s of the vector that will be given as input only for training (that should be guessed for testing) corresponds to the coordinates 3𝑚(𝑘[𝑠]) + 𝑖 with 𝑖 ranging from 𝑚 to 2𝑚 -1 in the general case and, in the modified case (when we want to make a peer different), with 𝑖 ranging from 2𝑚 to 3𝑚 -1. This allows use to general pseudo-random sparse binary vectors which are similar but not identical among all peers. To add noise, we simply flip bits with coordinates ((𝑘/𝑠) + 𝑖(𝑛/𝑧))[𝑛] (/ representing integer division) with 𝑖 ranging from 0 to 𝑧 -1.

For this test, we use 15 peers, 2 of them having 1 out of 3 vectors modified (𝑖 ranging from 2𝑚 to 3𝑚 -1 rather than 𝑚 to 2𝑚 -1). Each vector is 50 bits long, with 𝑚 = 8 (non-zero bits) and 𝑧 = 2 (noise). The periodicity of the generators is 3, the batch size is 9 (𝑘 ∈ ⟦0, 9⟦) and the mini-batch size is 3. The tests consider 100 consecutive values of 𝑘 (starting at 1000). The learning rate is 0.1 and the activation threshold for neurons is 0.5. The visible layer has 50 neurons (the length of an input/output vector), while the hidden layer comprises 400 neurons.

We compare no averaging at all, complete averaging of both layers (visible and hidden) and several partial averaging schemes. For partial averaging schemes, the visible layer was completely averaged and 100, 200, 300 or 350 neurons of the hidden layer were averaged. Each curve corresponds to a We observe here that an averaging level of 300 (over 400) seems optimal for lower numbers of mini-batches (10,20), while 350 is for higher numbers (30,40). Except for 40 mini-batches, partial averaging schemes are always the best. Complete averaging was the worst for all tests but the 40 mini-batches one. For 40 mini-batches, complete averaging, while still worse than partial 350, is better than most partial averaging schemes. For all numbers of mini-batches, the optimal averaging level remained around 300-350. These results with associative neural network are consistent with those obtained with MLP, which indicates that our system works similarly on these different kinds of neural networks.

V.6 General analysis of results

The various experiments we made, and their parameters, are summarized in Table 3.1. Our experiments show that our method effectively enables distributed multi-task learning with neural networks. From the presented results, we can make the following detailed statements.

Partial model averaging yields better results than no averaging or complete averaging on different tasks, synthetic and real, with a variety of parameters, different kinds of neural networks and learning algorithms.

Among the considered tasks, a high level of averaging (60-80% of hidden layers) usually turns out to be the best solution and the level of difference between peers' tasks only has a low influence on the Semi-local averaging and the associated dependency system further improve performance when groups of peers share more similar functions than the whole system.

Multi-task learning with MLP benefits in FEMNIST from the possibility to share portions of layers rather than just complete layers, while more task-specific layouts, averaging limited to specific layers, have proved to be more efficient in modified MNIST but require more knowledge about the differences between peers. A mix of both kinds of schemes could be interesting in certain cases.

While those tests are done on simple cases, they allowed us to examine numerous parameters changes and their effect on the efficiency of our method. This makes this chapter a good base for applying our work to more complex real use cases.

VI Conclusion

In this chapter, we have introduced an effective solution for distributed multi-task learning with neural networks, applicable to different kinds of learning algorithms and not requiring mandatory prior knowledge about the nature, nor magnitude, of the differences between tasks, while still being able to benefit from such knowledge when available. The simplicity, range of application, and flexibility of our method significantly distinguishes it from existing works.

This work also opens several new directions in different fields. First, in the context of machine learning, we plan to design an algorithm that allows peers to be grouped automatically to share semi-local models. Second, it would be interesting to reduce communication overhead similarly to . Third, it would be interesting to apply our method to other kinds of neural networks, like LSTM [HS97; Ger99; GSC00]. One may also want to extend our experiments to other datasets and ranges of parameters and compare to more competitors, like the configurations presented in [START_REF] Marfoq | Federated Multi-Task Learning under a Mixture of Distributions[END_REF], including several cases where federated averaging exhibits great performance compared to our experiments; it would be interesting to see how our system performs is such configurations.

In the next chapter of this work, we explore the first direction: automatically assign models to peers, using clustering-based approach.

AUCCCR: Agent Utility Centered Clustering for Cooperation Recommendation I Introduction

In this chapter, we examine the problem of automatically assigning models to peers for our distributed multi-task machine learning system. To maximize the impact of this work, we decided not to focus on machine learning but to consider a more general problem. Model assignment for distributed multi-task machine learning is only an instance of a problem we will refer to as cooperation recommendation.

We define cooperation recommendation as follows. We have a set of agents (people, organizations…) who want to perform similar tasks that can be done collaboratively (machine learning, grouped or-ders…). These agents may benefit from collaboration but only if other agents have sufficiently similar expectations (function to learn, goods to buy) and are sufficiently numerous (larger groups compensate divergences). Agents would like to know who they could collaborate with and think in terms of individual interest; they can and will refuse to collaborate if the proposed recommendation does not benefit them individually. Given data on agents preferences, we want to provide cooperation recommendations that agents will accept.

This definition leads us to a formalism based on economics and prescriptive decision theory [vM44] 1 . The utility an agent obtains from belonging to a group is positively correlated to the group's size (larger is better), but negatively correlated with its distance from the group's barycenter (closer is better). Such a model can capture various practical problems: in collaborative machine learning, for instance, learners with similar but different tasks may or may not collaborate with each other, depending on the effect of this collaboration on the efficiency of their learning process; in grouped purchases, potential buyers will search for other people with similar buying habits to save money by placing grouped orders, but will not benefit if the products bought deviates too much from their preferred options; when planing organized vacations, most people want to save money with group rates, but not at the cost of visiting too many places they are not interested in. If agents are too unsatisfied by the recommendation (worse than being alone), they may reject it. We also consider the case where people want to be in groups that are large enough but not too large.

An algorithm that solves this problem should provide collaboration recommendations (e.g. with whom each agent should share parts of a machine learning model or perform a grouped order) that agents find acceptable and from which they do not deviate. Since, in this context, the relative utility of different options for an agent depends on the choices of other agents, it is crucial to prevent situations where a few agents reject the recommendation, as this could lead to a complete collapse of the solution. The departure of a dissatisfied agent can decrease the group's value for other agents, which may in turn leave the group, etc.

In economic terms, this problem can be modeled as a hedonic game [START_REF] Drèze | Hedonic Coalitions: Optimality and Stability[END_REF], but this formalization tends unfortunately to be too general to allow for effective algorithmic solutions. Existing algorithms that solve generic hedonic games, summarized in [START_REF] Aziz | Hedonic Games[END_REF], need to constrain them by requiring the existence of some kind of equilibrium (Nash equilibrium or a similar definition), which is not guaranteed by the generic definition of hedonic games and may not exist in practice. In our work, we instead consider a more restricted class of games, where agents' utility is given by a certain formula, and we provide an heuristic that also works in cases where no kind of equilibrium exists (though the solution is necessarily imperfect).

Hedonic games designed for specific problems have been proposed in the past, for example in [START_REF] Saad | Coalition Formation Games for Distributed Cooperation Among Roadside Units in Vehicular Networks[END_REF], but the practical problems they consider do not apply to our context. The cited example presents the case of roadside units in intelligent transportation systems. In particular, these works tend to adopt a formalization that ensures the existence of some kind of equilibrium, while we want solutions for cases where no equilibrium exists.

Our insight is that the hedonic games corresponding to our coalition-formation problem can be interpreted as a clustering problem. We want to identify groups of close and numerous agents, which is essentially a clustering task. However, commonly used clustering algorithms, while technically applicable, are not adapted to this particular task, as they can not work with the kind of utility formula we want to use. To address this gap, this chapter proposes a novel clustering algorithm, that is specifically designed to address the task we want to solve.

We begin this chapter with a formal definition of the class of hedonic games we use to model collaboration. We then propose AUCCCR (pronounced "okr", IPA: [okʁ]), a clustering algorithm able to provide solutions to the considered problem. We present a theoretical and experimental evaluation of our algorithm on both synthetic and real data. From this evaluation, we conclude that our algorithm respects individual agents interests better than other clustering algorithms.

II Our approach

II.1 Problem statement and formalization

We consider a set of agents 𝑎 0 , ..., 𝑎 𝑚 ∈ 𝐴 that seek to form groups so that every agent in a group effectively benefits from belonging to this group. We represent agents' preferences using an ℓ-dimensional real vector given by a projector function, 𝑝 ∶ 𝐴 → ℝ ℓ , which allows us to measure similarity between agents as a distance. In our model, the benefit from being in a group depends on two factors: the size of the group (the larger the better), and the similarity between an agent and the (average of) the group (the more similar the better). In practice, the chosen projector function is likely to associate each agent with a vector of real values taken from a database; for example (what is used in our experiments) statistics on review for holiday destinations or annual spending in different types of goods.

More concretely, we define a utility function 𝑈 𝑝 (𝑎, 𝑔) that expresses the interest of an agent, 𝑎, in a group, 𝑔, using a projector, 𝑝, as the product of two factors: (i) the value of the group (function 𝑣), which grows with the group's size; and (ii) a decreasing function (𝑛(...)) of the distance between an agent and the group's barycenter (as measured by a distance function 𝑑(...)). This is formally captured by the following formula:

𝑈 𝑝 (𝑎, 𝑔) ∶ 𝐴 × 𝒫(𝐴) → ℝ + = 𝑛(𝑑(𝑝(𝑎), 𝑏𝑎𝑟𝑦 𝑝 (𝑔))) × 𝑣(#𝑔) (4.1)
Where 𝒫(𝐴) is the power set of 𝐴, #𝑔 is the size of group 𝑔, bary 𝑝 (𝑔) is the barycenter of group 𝑔 with projector 𝑝, and the functions 𝑑, 𝑣, and 𝑛 are defined as follows: 𝑑(𝑥, 𝑦) ∶ ℝ 𝑙 × ℝ 𝑙 → ℝ is the and 𝑛(𝑑) ∶ ℝ + → [0, 1] is the normalizer for an agent at distance 𝑑 from its group's barycenter (decreasing, 𝑛(0) = 1). In the following we will also use 𝑔(𝑎) to denote the group of agent 𝑎. These definitions associate a utility value of 1 with an agent that remains alone (since the interest of joining a group with a barycenter at distance 0 and consisting of 1 element (itself) is 𝑛(0) × 𝑣(1) = 1 × 1).

Given 𝐴, 𝑝(), 𝑑(), 𝑛() and 𝑣(), the group formation problem we seek to solve consists in finding a partition of 𝐴 (representing the groups), that maximizes the sum of every agent's utility, while minimizing (or even eliminating) the benefit individual agents could gain by either changing group or remaining alone (to ensure the solution's stability). Table 4.1 summarizes these notations.

More formally, our objective is: Given 𝐴 (agents), 𝑝() (projector function), 𝑑() (distance metric), 𝑛() (normalizer) and 𝑣() (generic group value for given size). With 𝑈 𝑝 (𝑎, 𝑔) defined as above (𝑈 𝑝 (𝑎, 𝑔) ∶ 𝐴 × 𝒫(𝐴) → ℝ + = 𝑛(𝑑(𝑝(𝑎), 𝑏𝑎𝑟𝑦 𝑝 (𝑔))) × 𝑣(#𝑔)). Find some group affectation 𝑔() (𝑔(𝑎) may be "no group"). That maximize ∑ 𝑎∈𝐴 𝑈 𝑝 (𝑎, 𝑔(𝑎)). Subject to ∀ 𝑎∈𝐴 ¬∃ 𝑔 ′ 𝑈 𝑝 (𝑎, 𝑔(𝑎)) < 𝑈 𝑝 (𝑎, 𝑔 ′ ) (𝑔 ′ may be "no group"). Or (if the above condition can not be meet) minimizing ∑ 𝑎∈𝐴 max 𝑔 ′ (𝑈 𝑝 (𝑎, 𝑔 ′ ) -𝑈 𝑝 (𝑎, 𝑔(𝑎))).

II.2 Algorithm

In this section, we present our algorithms and define them precisely. In the following pseudocode, the member function * .𝑖𝑛𝑣𝑒𝑟𝑡𝑘𝑣() inverts keys and values of an associative container (data structure) with unique values, the member function * .𝑔𝑟𝑜𝑢𝑝(𝑥) returns the set of all elements in the container associated with the same key as 𝑥, singleton 𝑥 if 𝑥 is not in the container. Table 4.2 summarizes these and defines the variables and parameters appearing in algorithms.

Algorithm 6 presents the control function (loop) of our group recommendation algorithm. It loops over the parameter 𝑘 (number of groups), increasing it until no significant global utility (sum of all agents utility) gains have been achieved. To reduce the randomness of the process (our clustering algorithm being randomized) each 𝑘 value is tried several times (parameter 𝑝𝑟𝑐) and the loop will only terminate if no gain happen for several 𝑘 increments (momentum, parameter 𝑚𝑚𝑡).

Algorithm 7 is based on k-means [START_REF] Stuart | Least squares quantization in PCM[END_REF]. The first step is the initialization of groups, which is a k-means++ [START_REF] Arthur | K-means++: The Advantages of Careful Seeding[END_REF] initialization (each group is given one single random member sequentially, with probability increasing with the distance to existing groups). After initialization, the process consists of two nested loops (inner and outer). Since, unlike k-means, we take group size into account, we need two loops, one for distance changes (as k-means) and one for group size changes (the inner loop). In the inner loop, at initialization, each group, has a fixed barycenter and is given a potential size of #𝐴. At each turn, agents compute their utility for each group with the potential sizes and choose their group accordingly. After that, the potential size of each group is set to the number of agents choosing this group, the barycenters are not updated. The process is repeated until no change occur in one turn. Working on the basis of potential size (i.e. maximum number of agents potentially interested in joining a group) rather than actual size resolves the "chicken or the egg" problem caused by the fact that, to appeal to potential members in terms of utility, a group needs to be already large enough. In the outer loop, at each turn, the inner loop is executed and the barycenters are updated. The loop Compared with k-means, the interesting part of our algorithm is the inner loop. Since, unlike k-means, our algorithm take the size of groups into account, we need this inner loop. It allows us to compute agents' utility with bigger groups. For agents to join groups, these groups have to be big enough and for groups to be big, agents have to join them. Our inner loop, with its over-evaluated groups' initial potential sizes, breaks this circle. The main limitation of this algorithm is that we do not have a theoretical termination proof for it. It could potentially, in very rare cases, get stuck in an infinite loop. So, we propose variation with guaranteed termination in Algorithm 8.

Algorithm 8 terminates the inner loop if the total number of agents member of any group does not change in one turn and the outer loop if the global utility of the affectation does not increase in one turn. This way, the algorithm is guaranteed to converge.

Both algorithms include a somewhat complex formula to compute agent's interest. For large instances, with very big clusters, individual agents influence on a cluster can be considered negligible. We call this situation "agents' atomicity" (agents are "atoms", too small relatively to the whole system to have significant influence individually) and use the adjective atomic to qualify things liked to this property2 . Thus, we can make an agents' atomicity hypothesis to simplify the formulas.

𝑛(𝑑(𝑝(𝑎), 𝑏𝑎𝑟𝑦(𝑔𝑟𝑝[𝑖] ∪ 𝑎))) × 𝑣(𝑠𝑖𝑧𝑒[𝑖] + 𝟙 𝑎∉𝑔𝑟𝑝[𝑖] ) can be replaced by 𝑛(𝑑(𝑝(𝑎), 𝑏𝑎𝑟𝑦(𝑔𝑟𝑝[𝑖]))) × 𝑣(𝑠𝑖𝑧𝑒[𝑖]

). This possibility may be used for a production implementation.

III Theoretical analysis

Here we prove the essential property of the clustering algorithm presented in Algorithm 7: equilibrium. After which, we consider the one of Algorithm 8: convergence.

Property (Nash equilibrium). If we consider a game where each agent's (player) possible choices are 𝑘 different groups to join, or not choosing any group, and each agent's, 𝑎, utility (payoff ) for choosing group 𝑔 is given by 𝑈 𝑝 (𝑎, 𝑔) as defined before and 1 for no choosing any group, the affectation produced by Algorithm 7, if it exists, is a (weak) Nash equilibrium for this game.

Algorithm 6: Recommendation algorithm

Data: 𝐴 set of agents, 𝑝 projector, 𝑝𝑟𝑐 is the number of (random) initial values to try, 𝑚𝑚𝑡 momentum effect Result: A pair of a group affectations of agents and its value Proof (Nash equilibrium). We assume that our algorithm as converged, we consider the last iteration of the loop guarded by 𝑛𝑔𝑟𝑝 = 𝑔𝑟𝑝 (line 11) and, in this iteration, the last iteration of the loop guarded by 𝑛𝑠𝑖𝑧𝑒 = 𝑠𝑖𝑧𝑒 (line 15). Let's assume that the output of the function, 𝑛𝑔𝑟𝑝 = 𝑔𝑟𝑝, is not a (weak) Nash equilibrium. Then ∃𝑎 ∈ 𝐴, 𝑔 ∈ ⊥ ∪ ⟦0, 𝑘 -1⟧(𝑈 𝑝 (𝑎, 𝑔) > 𝑈 𝑝 (𝑎, 𝑔𝑟𝑝.𝑔𝑟𝑜𝑢𝑝(𝑎))). Since at the end of the loop iteration 𝑛𝑠𝑖𝑧𝑒 = 𝑠𝑖𝑧𝑒 and 𝑛𝑠𝑖𝑧𝑒 is, by design, the vector of the sizes of the groups given by 𝑛𝑔𝑟𝑝, we can affirm that, during the considered loop iteration (assimilating 𝑖 with a group),

1 𝑣𝑎𝑙 ← #𝐴 2 𝑘 ← 1 3 𝑝𝑚𝑚 ← 𝑚𝑚𝑡 4 repeat 5 𝑝𝑣𝑎𝑙 ← 𝑣𝑎𝑙 6 𝑣𝑎𝑙 ← #𝐴
𝑈 𝑝 (𝑎, 𝑔𝑟𝑝[𝑖]) = 𝑛(𝑑(𝑝(𝑎), 𝑏𝑎𝑟𝑦(𝑔𝑟𝑝[𝑖] ∪ 𝑎))) × 𝑣(𝑠𝑖𝑧𝑒[𝑖] + 𝟙 𝑎∉𝑔𝑟𝑝[𝑖] ).

Since, by design, our algorithm selects 𝑖 to maximize 𝑛(𝑑(𝑝(𝑎), 𝑏𝑎𝑟𝑦(𝑔𝑟𝑝[𝑖]∪𝑎)))×𝑣(𝑠𝑖𝑧𝑒[𝑖]+𝟙 𝑎∉𝑔𝑟𝑝[𝑖]

), we can affirm that, in this loop iteration, a different group would have been selected for at least one 𝑎. Now, either that changes the size of at least one group, implying 𝑛𝑠𝑖𝑧𝑒 ≠ 𝑠𝑖𝑧𝑒 at the end of the loop, which is a contradiction. Or, if the sizes remains identical (exchange of members), then, the loop guarded by 𝑛𝑠𝑖𝑧𝑒 = 𝑠𝑖𝑧𝑒 exists, and we get 𝑛𝑔𝑟𝑝 ≠ 𝑔𝑟𝑝, which also is a contradiction.

Since the existence of a Nash equilibrium for this game is not guaranteed, it is possible that Algorithm 7 does not terminate. Now, we prove that Algorithm 8, for which we do not have an equilibrium proof, will always terminate.

Property (Convergence). Algorithm 8 always terminates.

Proof (Convergence). Among the control structures used in Algorithm 8, the two repeat…until loops are the only that do not trivially terminate (for loops terminate trivially). For the inner loop, we replaced 𝑛𝑠𝑖𝑧𝑒 = 𝑠𝑖𝑧𝑒 by 𝑛𝑠𝑖𝑧𝑒.𝑠𝑢𝑚() ⩾ 𝑠𝑖𝑧𝑒.𝑠𝑢𝑚() as termination condition. This implies that, during the loop, 𝑠𝑖𝑧𝑒.𝑠𝑢𝑚()'s values are a strictly decreasing natural (ℕ) sequence. Such a sequence can not be infinite, thus, the inner loop terminates. For the outer loop, we replaced 𝑛𝑔𝑟𝑝 = 𝑔𝑟𝑝 by 𝑛𝑣𝑎𝑙 ⩽ 𝑣𝑎𝑙 as termination condition. This implies that, during the loop, 𝑣𝑎𝑙's values are a strictly increasing real sequence. Moreover, those values are given by a formula taking as parameter an affectation of a finite number of agents in a finite number of groups. The possible inputs for this formula for a given execution of the algorithm (fixed parameters) are a finite set. This implies that the possible values for 𝑣𝑎𝑙 (output of this formula) are also a finite set (for a given execution of the algorithm). Thus, 𝑣𝑎𝑙's values are a strictly increasing sequence of elements of a finite set (the order is given by the classical order for real number). Such a sequence can not be infinite, thus, the outer loop terminates. We can now conclude that our algorithm will always terminate.

We note that Algorithm 8 is not guaranteed to give a Nash equilibrium. Such an equilibrium may simply not exist, but even if it exists, the algorithm is not guaranteed to find it. Due to the end condition of its outer loop, Algorithm 8, while still based on agents' self-interest, is more centered on attaining general optimality (maximizing the sum of all agents utilities) than Algorithm 7.

An important thing that differentiates our algorithm from generic approaches to solve hedonic games presented in [START_REF] Aziz | Hedonic Games[END_REF] is the inner loop of our algorithm, which allows groups to grow to a point that is better for every agent even in situations where individual rational decisions could not. Let's examine this simple example : We have four agents, 𝐴, 𝐵, 𝐶 and 𝐷. 𝑛(𝑥) = 1 1+𝑥 , 𝑣(𝑥) = 𝑥, 𝑝's values in ℝ 2 , 𝑝(𝐴) = [0, 0], 𝑝(𝐵) = [0, 2.5], 𝑝(𝐶) = [2.5, 0] and 𝑝(𝐷) = [2.5, 2.5] (a square).

In this example, having all agents in a single group, 𝒢, is the best solution. ∀ 𝑎∈{𝐴,𝐵,𝐶,𝐷} 𝑈 𝑝 (𝑎, 𝒢) = 4 1+2.5 √ 2/2 > 1. But this situation could not be reached from groups consisting of a single agent by individual rational decisions, since the best interest one single agent could get from grouping with another agent would be 2 2.25 < 1, so no agent would want to group with any other. With our algorithm, if we start with a group 𝒢 = {𝐴}, due to making computations based on the potential maximum size of the group rather than its actual size, individual interest of 𝐵 and 𝐶 for join the group would be estimated at 4 3.5 > 1 with an atomic variant (even more with a non-atomic variant) and the group 𝒢 will be updated 𝒢 = {𝐴, 𝐵, 𝐶}. On the second run of the inner loop, with the bary center of 𝒢 being at [ 2.5 /3, 2.5 /3], the atomic-estimated interest for 𝐷 to join 𝒢 would be 4 1+ 5 /3 √ 2 > 1. We end up with 𝒢 = {𝐴, 𝐵, 𝐶, 𝐷}.

IV Experimentation

In this section, we evaluate Algorithm 8, in normal and atomic agents variants and see how much, in practice, it deviates from Algorithm 7's Nash equilibrium property. We compare our algorithm with two reference clustering algorithms: OPTICS [Ank+99] and k-means [START_REF] Stuart | Least squares quantization in PCM[END_REF] with k-means++ [START_REF] Arthur | K-means++: The Advantages of Careful Seeding[END_REF] initialization. All algorithms evaluated have guaranteed termination. We perform this evaluation on four kinds of datasets: synthetic data and two real data applications: leisure travel and wholesale purchases.3

IV.1 Metrics

We rely on the notion of loss of each agent for a given cluster affectation. Intuitively, the loss of an agent in a given configuration is the difference between the utility of the agent in this configuration and the maximum utility the agent could have if the agent deviates from this configuration (leave and/or join clusters) without any other agent moving. Said otherwise, the loss of an agent 𝑎 for a given cluster affectation 𝒞 is defined as the difference (⩾ 0) between the utility the agent gets in this affectation and the maximum utility the agent could get in another affectation that only differs from 𝒞 by the position of 𝑎 in the affectation (𝑎 can leave its group and potentially join another one but no other agent can move). For example, if in a situation, an agent 𝑎 is affected to the cluster {𝑎, 𝑏, 𝑐} and gets a utility of 3 but could get a maximum (over all configurations possible without changing the position of any agent other than 𝑎) utility of 4 if in cluster {𝑎, 𝑑, 𝑒}, then its loss is 1. The targeted value is 0.

We use the following three metrics to measure the performance of each algorithm:

• The losses of agents (summed among all agents).

• The share of agents having losses (loss > 0).

• The global utility of agents (sum of all utilities).

A good group formation algorithm (according to our definition of this problem) should deliver a closeto-maximum global utility, along with a low sum of agents' losses, and a low rate of losing agents (in the ideal case these last two metrics should have value 0). In addition to the above metrics, we also display the results of example runs (in the case of random synthetic data, using the same data for all algorithms). In these, a color identifies a cluster, gray points represent isolated agents (or agents in a cluster of size 1). Results are averaged over 10 runs; error bars indicate the standard deviation.

IV.1.a Clusters visualization

While our synthetic data is bidimensional and thus easily representable in a figure, the real data we use have a larger dimension (6 for both datasets), thus, we provide views in reduced dimensions, 2 and 3. We propose two different kinds of dimension reduction methods. The first simply presents the dimensions were the original dataset has higher standard deviation. See Figure 4.20 for 2D and Figure 4.21 for 3D. The second uses the scikit-learn [START_REF] Pedregosa | Scikit-learn: Machine Learning in Python[END_REF] Python library, which implements various algorithms that can perform non-linear dimension reduction (Manifold). The specific algorithm we used is MDS (Multi-Dimensional Scaling) [START_REF] Borg | Modern Multidimensional Scaling -Theory and Applications[END_REF].

IV.2 Synthetic Data

We first evaluate our algorithm on ℝ 2 data generated using a combination of Gaussian distributions. We choose Gaussians because these distributions are usually considered good models of characteristics distribution in real populations. A fixed number of points is generated, the distribution used to generate each vector is chosen randomly according to a predetermined ratio. Parameters of these laws will be detailed in each specific tests. We used the usual Euclidean distance for 𝑑, 𝑛(𝑥) = 1 1+𝑥 and 𝑣(𝑥) = √ 𝑥4 . 𝑝𝑟𝑐 = 20 (number of trials (execution of the clustering algorithm itself) with the same parameters), 𝑚𝑚𝑡 = 5 (momentum). k-means' parameter 𝑘 is searched for in the same way as for AUCCCR. For OPTICS, which is not randomized and, as such, does not suffer from the same instability (as k-means and our algorithm) in its output, the procedure used to select the proper minimum reachability distance (points closer than this distance are considered close enough to be part of the same cluster) is equivalent but with prc = mmt = 1. For OPTICS-specifics parameters, we use 𝜖 = ∞ (maximum distance to consider, mostly a speedup parameter so ∞ is an acceptable (official) default), 𝑀 𝑖𝑛𝑃 𝑡𝑠 = 1 (number of points of a cluster that should be close enough for a certain point to be considered part of this cluster, we considered 1 to be an acceptable default).

Results are average values over 10 runs (execution of the whole recommendation algorithm), error bars indicate standard deviation. Example results, based on a single run (same data for all algorithms), are also given. In these, a color identify a cluster, gray points are alone (or in a cluster of size 1). "AUCCCR-C" is Algorithm 8 in its normal variant, "AUCCCR-CA" is the atomic variant.

IV.2.a Bi-Gaussian

For this test, we used two (0, 0)-centered Gaussian distributions with 1 and 8 as standard deviations and a 0.5 -0.5 ratio (same probability for each distribution). The number of point is 100.

Figure 4.1 presents a sample output of the four algorithms. In these, a color identify a cluster, gray points are alone (or in a cluster of size 1). Figure 4.2c shows the global utility, as a sum of all agents' utility, for each algorithm. Figure 4.2a shows the sum of the losses of agents, which is the difference between the utility an agent gets from the present cluster affectation and the maximum utility the agent could get if the agent chooses its cluster (or being alone) following its own interest (given by Formula 4.1). Figure 4.2b shows the share of agents experiencing losses.

In this test, we see that AUCCCR-C(A) yields a lower global utility but also that its output is very close to a Nash equilibrium (near 0 losses), while k-means and OPTICS have more than 25% of agents experiencing losses. Looking at individual runs, we see that k-mean and OPTICS just produce a single giant cluster, maximizing its value for all agent but causing losses for agents that lie far away from the barycenter, while our algorithm, because it allows agent to stay on their own, took more care of their individual interest.

IV.2.b 3 Gaussians

For this test, we used three Gaussian distributions, (-6, 0), (0, 0) and (0, 6)-centered with 1.5 as standard deviations and a 0.33-0.33-0.33 ratio (same probability for each distribution). The number of point is 200.

Figure 4.3 presents a sample output of the four algorithms. In these, a color identify a cluster, gray points are alone (or in a cluster of size 1). Figure 4.4c shows the global utility, as a sum of all agents' utility, for each algorithm. Figure 4.4a shows the sum of the losses of agents, which is the difference between the utility an agent gets from the present cluster affectation and the maximum utility the agent could get if the agent chooses its cluster (or being alone) following its own interest. Figure 4.4b shows the share of agents experiencing losses.

In this test, we see that AUCCCR-C(A) and k-means both perform well it terms of global utility, better than OPTICS, likely due to OPTICS density-centered design being ineffective for this kind of pattern ; OPTICS has difficulties in distinguishing close but clearly distinct distributions. Losses were limited but AUCCCR clearly outperformed k-mean and, even more, OPTICS.

IV.2.c Gaussians Star

For this test, we used five Gaussian distributions, (0, 0), (-10, -10), (-10, 10), (10, -10) and (10, 10)-centered with 5 for the (0, 0) and 2 for others as standard deviations and a 0.5 -0.125 -0.125 -0.125 -0.125 ratio. The number of point is 300.

Figure 4.5 presents a sample output of the four algorithms. In these, a color identify a cluster, gray points are alone (or in a cluster of size 1). Figure 4.6c shows the global utility, as a sum of all agents' utility, for each algorithm. Figure 4.6a shows the sum of the losses of agents, which is the difference between the utility an agent gets from the present cluster affectation and the maximum utility the agent could get if the agent chose its cluster (or being alone) following its own interest. shows the share of agents experiencing losses.

In this test, all algorithms gave similar results in terms of global utility (slightly lower for AUCCCR on average). The gap much higher on losses, with AUCCCR clearly leading. Looking at samples, it seems that AUCCCR performed pretty well for identifying the five Gaussians mixed in the input data compared to k-means and OPTICS.

IV.2.d Effect of the number of agents

In this test we reuse our Gaussians Star setup, but we test different numbers of agents. Figure 4.7c shows the global utility, as an average of all agents' utility, for each algorithm. Figure 4.7a shows the average of the losses of agents, which is the difference between the utility an agent gets from the present cluster affectation and the maximum utility the agent could get if the agent chooses its cluster (or being alone) following its own interest. Figure 4.7b shows the share of agents experiencing losses.

We see here that all algorithms have similar performances in terms of global utility; AUCCCR being slightly better for a high number of agents. In terms of losses, however, OPTICS and k-means perform significantly worse for low numbers of agents.

IV.2.e Effect of the standard deviations

In this test we reused our Gaussians Star setup, but we tested different standard deviations. Figure 4.8c shows the global utility, as an average of all agents' utility, for each algorithm. Figure 4.8a shows the average of the losses of agents, which is the difference between the utility an agent gets from the present cluster affectation and the maximum utility the agent could get if the agent chooses its cluster (or being alone) following its own interest. Figure 4.8b shows the share of agents experiencing losses.

For recall, the Gaussian Star is a mixture of 5 distribution, a (0, 0)-centered distribution with a certain standard deviation and 4 others, with their centers at a certain distance from (0, 0) and a lower (same for the 4) standard deviation. The value used in the "Standard deviations" axis is the (0, 0)-centered distribution's standard deviations. Others' standard deviations are modified by the same factor, as well as the distances between distributions' centers.

With a high standard deviation, the optimal solution becomes essentially to have nearly as many clusters as agents. k-means performs much worse than other algorithms (nearly all agents have losses, while nearly none have for other algorithms) because it is not designed to find this kind of affectation. AUCCCR and OPTICS have similar performance overall, except for a standard deviation of 10. In losses, AUCCCR is the only algorithm to always remain at very low values. For the value 10, while AUCCCR was slightly lower for global utility, it is by far the best for losses.

IV.2.f Effect of scale

In this test we reused our Gaussians Star setup and combined the two previous tests, modifying at the same time, standard deviations, number of agents and mean values separations by the same scale factor (for geometrical reasons, this implies that the distances were increased by the square root of this factor).

Figure 4.9c shows the global utility, as an average of all agents' utility, for each algorithm. Figure 4.9a shows the average of the losses of agents, which is the difference between the utility an agent gets from the present cluster affectation and the maximum utility the agent could get if the agent chooses its cluster (or being alone) following its own interest. Figure 4.9b shows the share of agents experiencing losses.

Here we observe that AUCCCR can have difficulties with certain scale values, around 2 or 4, in terms of global utility, while being more competitive for a higher value of 8. This is probably due to such scales offering more opportunity for AUCCCR to deviate from the global optimum in favor of reducing individual losses. In terms of losses, however, AUCCCR remains extremely low for all value, while other algorithms get much worse results.

IV.2.g Size constraint

While our algorithm is originally designed for cases where larger clusters are always the best (in terms of agents utility), we show here how it can be modified to accommodate cases where, passed a certain threshold, larger group become not more desirable or even less desirable. To integrate this in our algorithm, we simply need to modify the 𝑣(𝑥) (effect of the group size on utility) from a strictly increasing function to a function that reaches a maximum, or even starts decreasing, at some point.

To evaluate the ability of our algorithm to manage cases where very large clusters are not desirable (agents want to be in a sufficiently large group but not too large) we take a simple case, with a single Gaussian, in which our usual 𝑣(𝑥) = √ 𝑥 function would make a single cluster (with all agents in it) optimal. We then change 𝑣(𝑥) so that too large clusters are not optimal.

We test two different functions, both = √ 𝑥 for 𝑥 ⩽ 20, but for 𝑥 > 20 the first function is constant √ 20 while the second is decreasing √ 20 1+ |20-𝑥| 20 (both functions are continuous). The number 20 is an arbitrary choice and can be considered as a target size for clusters. See Figure 4.10 for a plot. We see that changing the 𝑣(𝑥) function is a good way to adapt AUCCCR to size constraints. √ 20 is sufficient as the effect of distance reduces interest for larger (necessarily sparser) groups, even through √ 20 1+ |20-𝑥| 20 has a stronger effect. A downside of √ 20 1+ |20-𝑥| 20 is that AUCCCR is not designed for decreasing 𝑣(𝑥) functions (k-means and OPTICS are even worse, as they are not designed for utility functions at all) and we see that we get (too) small clusters in that case, but this does not prevent the algorithm from working correctly. Still, AUCCCR performs quite well in terms of size of cluster (close to the target size) in general, while k-means and OPTICS produce many smaller clusters with √ 20 1+

IV.3 The BuddyMove dataset

The BuddyMove [START_REF] Renjith | A personalized mobile travel recommender system using hybrid algorithm[END_REF] dataset consists of statistics from users of a travel review website. For each user, the dataset provides the number of reviews written for each of 6 classes of destination (e.g. religious sites, parks, etc). From these data, we derived for each user the share of reviews written for each destination class. This can be interpreted as the relative interest of a user for each kind of destination. This could allow providing recommendation to users on whom they should go with for group travels, based on the similarity of their preferences.

IV.3.a Hyperparameters

Our clustering algorithms used Euclidean distance for 𝑑, 𝑛(𝑥) = 1 1+𝑥 and 𝑣(𝑥) = √ 𝑥. 𝑝𝑟𝑐 = 20, 𝑚𝑚𝑡 = 5. Results are average over 10 runs, error bars indicates standard deviation. Sample examples, based on a single run, are also given. In these, a color identify a cluster, gray points are alone (or in a cluster of size 1). "AUCCCR-C" is Algorithm 8 in its normal variant, "AUCCCR-CA" is the atomic We introduce an additional hyperparameter when working with real datasets: scale. The scale describes how "far" a given distance is considered by the algorithm and can be seen as parameter of the projector function 𝑝 we presented earlier. The distances naturally present in the dataset must be given an absolute cardinal signification for the algorithm, the right choice is up to the user, we variate it to see how this choice affects the results. For example, if the scale is 10, a distance of 1 will be computed as 10 for computation. As the scale grows, the distance between points will be considered longer by the algorithm.

IV.3.b Metrics

The graphs in The range of scale is selected to cover all the range of cases from a situation where everyone alone is optimal to a situation were a universal cluster is optimal.

We note that, is those graphs, the lines for the two variants of AUCCCR are largely superposed, and k-means and OPTICS are identical. For a low scale, users are considered close and all algorithms will detect a single cluster but, as the scale increases, the results become very different. AUCCCR, contrary to the reference algorithms, will prevent individual losses ; as we can see, losses are very low for AUCCCR, especially for large scales, while, for other algorithms, losses increase dramatically. For a scale of 130, AUCCCR has nearly 0 agents losses while k-mean and OPTICS have 30%. This comes at the cost of a reduced global utility, which slowly drops until it nearly hits 1 (equivalent to everyone alone) at 130. For midrange values, we see that AUCCCR has nearly no losses with a still high global utility (1.5, 1.7 for reference algorithms; this lower value being due to the small size of clusters possible with minimal individual losses) while reference algorithms have 15% to 20% of losses.

IV.3.c Clusters size

The graphs in Figure 4.19 gives the obtained clusters sizes for the different algorithms with a scale of 115. We see that, for this midrange scale, k-means and OPTICS identified only a universal cluster, while both AUCCCR variants identified 3 and let numerous users alone.

IV.3.d Clusters visualization

We propose visualizations of clusters in reduced dimension (2D and 3D) obtained as described in Section IV.1.a. See Figure 4.20 for 2D and Figure 4.21 for 3D with classical (standard deviation-based) dimension reduction. See Figure 4.22 for 2D and Figure 4.23 for 3D with Manifold MDS visualization. We see that AUCCCR is able to identify clusters in the dataset, unlike k-means and OPTICS.

IV.4 The Wholesale dataset

The Wholesale [START_REF] Gonçalo | Análise do perfil do cliente Recheio e desenvolvimento de um sistema promocional[END_REF] dataset consists of statistics from customers of a wholesale vendor. For each customer, the dataset indicates the annual spending for each of 6 classes of products (e.g. fresh, frozen, etc). From these data, we derive for each customer the share of reviews written for each product class. This result could for instance be used to provide recommendations to customers on whom they should collaborate with to make grouped orders more directly, removing the wholesale distributor from the circuit (short circuit distribution), based on which kind of products they usually order.

IV.4.a Hyperparameters

We configure our clustering algorithms the same way as for the previous experiment (most significant elements recalled here, for the rest see Section IV.3.a): Euclidean distance for 𝑑, 𝑛(𝑥) = 1 1+𝑥 and 𝑣(𝑥) = √ 𝑥. 𝑝𝑟𝑐 = 20, 𝑚𝑚𝑡 = 5. "AUCCCR-C" is Algorithm 8 in its normal variant, 'AUCCCR-CA" is the atomic variant.

IV.4.b Metrics

The graphs in Figure 4.24 presents the 3 following metrics : the average utility of agents (Figure 4.24c), the average losses of agents (Figure 4.24a) and the share of agents having losses (Figure 4.24b) for a range of scale values. The range of scale is selected to cover all the range of cases from a situation where everyone alone is optimal to a situation were a universal cluster is optimal.

We note that, is those graphs, the lines for the two variants of AUCCCR are largely superposed. For a low scale, users are considered close and all algorithms will detect a single cluster but, as the scale increases, the results become very different. AUCCCR, contrary to the reference algorithms, will prevent individual losses ; as we can see, losses are close to 0 for AUCCCR, especially for large scales, while, for other algorithms, losses increase dramatically. For a scale of 60, AUCCCR has nearly 0 agents losses while k-mean has > 30% and OPTICS has > 40%. The global utility remains similar to k-means and greater than OPTICS for the lower half of scales, only higher values have a utility lower than OPTICS but still very close from both, OPTICS and k-means. For midrange values, we see that AUCCCR has nearly no losses with a global utility close to k-means and higher than OPTICS, while

IV.4.c Clusters size

The graphs in Figure 4.25 gives the obtained clusters sizes for the different algorithms with a scale of 45. We see that, for this midrange scale, k-means and OPTICS identified only a universal cluster, while both AUCCCR variants identified 3 and let numerous users alone.

IV.4.d Clusters visualization

We propose visualizations of clusters in reduced dimension (2D and 3D) obtained as described in Section IV.1.a. See Figure 4.26 for 2D and Figure 4.27 for 3D with classical (standard deviation-based) dimension reduction. See Figure 4.28 for 2D and Figure 4.29 for 3D with Manifold MDS visualization. We see that AUCCCR is able to identify clusters in the dataset, unlike OPTICS, and also to leave to some points alone, unlike both, k-means and OPTICS.

Since the dataset has a large dimension (6), we provide views in reduced dimensions, 2 and 3. We propose two different kinds of dimension reduction methods. The first simply presents the dimensions were the original dataset has higher standard deviation. See Figure 4.26 for 2D and Figure 4.27 for 3D. The second uses the scikit-learn [START_REF] Pedregosa | Scikit-learn: Machine Learning in Python[END_REF] Python library, which implements various algorithms that can perform non-linear dimension reduction. The specific algorithm we used is MDS (Multi-Dimensional Scaling) [START_REF] Borg | Modern Multidimensional Scaling -Theory and Applications[END_REF]. See Figure 4.28 for 2D and Figure 4.29 for 3D.

IV.5 General analysis of results

On our synthetic data tests, we showed that our algorithm is more efficient for cluster identification than classical clustering algorithms. It also appeared that, as intended, our algorithm causes much lower individual losses to agent than other algorithms. While it is not possible to completely remove losses in the absence of a Nash (or similar) equilibrium for mathematical reasons, our algorithm manages to keep such losses low, reducing the risk of agent unsatisfaction and collapse. Our algorithm also exhibited good performance on the two real datasets, BuddyMove and Wholesale, proving its applicability to real use cases.

V Conclusion

In this chapter, we defined a new class of hedonic games on which we based a algorithm for providing cooperation recommendation. We compared our algorithm to classical clustering algorithm that could also have been used for the same recommendation problem. We proved that our algorithm yields results that exhibit close to no losses and are thus similar to a Nash equilibrium (which does not exist in the general case) than other algorithms.

A possible way this work could be extended would be to adapt it to hierarchical clustering [START_REF] Rokach | Clustering methods[END_REF]. Hierarchical clustering, unlike classical clustering, can produce a complete hierarchy of clusters, subclusters, etc. Chapter 5

Application of clustering to distributed multi-task machine learning and individual interest analysis I Introduction

In the two previous chapters, we presented our distributed multi-task machine learning system and a clustering algorithm designed to be used for cooperation recommendation. This chapter focuses on the application of our clustering algorithm to provide good recommendation for cooperation with our machine learning system.

Our original formalism for distributed multi-task machine learning involves a set of peers wanting to collaborate to learn similar but different functions, using a certain (common) machine learning method. Notice that, while we commonly use the term peer in Chapter 3, because of the original focus of that chapter on decentralized systems, the term client may also be used when talking about a federated setup1 . In Chapter 4, we used the term agent to describe the same kind of entity, because agent is the term that fits our game theory-based formalism. In this chapter, as we do not want to use a term specific to a formalism that is not dominant in our analysis, we use the term learner.

Since our distributed multi-task learning system can use semi-local models (set of parameters shared by some but not all learners), tying similar learners together to improve the learning process, it can take advantage from an algorithm that can identify clusters of similar learners to automatically associate semi-local models with learners.

In the following, we evaluate how the use of semi-local models to which learners are assigned based on the output of our clustering algorithm can improve the multi-task learning process. We also see how, in practice, a vision centered in individual interests fits well with distributed multi-task machine learning.

II Method

We have our distributed multi-task machine learning system and our clustering algorithm designed to work with it to optimize the learning process by identifying similar learners, but how exactly do we make the two work together?

In our machine learning system, we have three kinds of models: global (shared by all learners), local (specific to one learner) and semi-local (shared by a subset of learners). A global model represents what all learners have in common. A local model represents what a specific learner does not share with others. A semi-local models represents what some learners, but not all (a cluster of learners), have in common. Semi-local models allow more similar peers to have closer collaboration, sharing something that other learners do not share, which leads to better performance in situations where this is relevant (as shown in Chapter 3 in Sections II.1 and V.3.e). Semi-local models are where a clustering algorithm can be useful. Since clusters are subsets of relatively closer points, with points representing learners, it is logical to think that learners in a cluster would share a common semi-local model.

Since our clustering algorithms takes real vectors as input, we need to extract real vectors from our learners' neural networks. The most straightforward way would be to directly take the neural networks learned parameters, which are real values, but this is not a good way. Due to the nature of neural networks, similar learned tasks absolutely do not imply similar learned parameters. Neural network training algorithms are non-deterministic and even when two neural networks do compute the same function, it is very unlikely that their internal structure is similar. For this reason, we prefer a different method. Our intuition is that the identity of a neural network is more the function it is computing (output given a certain input) rather than the computation itself (the parameters). Thus, we decide to rely on the output of each learner's network on some input to describe it relatively to others. The idea is to start with a local pre-training phase before using our clustering algorithm to define semi-local models and proceed with distributed training. Each learner starts with a blank (randomly initialized) neural network with a (common) layout (defined by the designer of the system); these networks will later be used for distributed training but, for now, averaging is disabled and the training happens locally, on each learner's local training set. After the local pre-training phase, consisting in a reasonable amount of training (task dependent but should not be too long, or the time cost may offset the benefits, while still enough for learners models to converge to clearly different models, otherwise the process would not attain its goal, the right setting is a trade off), we have all neural networks work on the same benchmark data (a specific portion of dataset dedicated to this purpose). From the outputs of this phase, a real vector is extracted for each learner, the learner's representative vector. This real vector is to be used as input for our clustering algorithm.

The exact way real vectors should be extracted from the output of each learner's neural network depends on the task type. Vectors should describe what is each neural network's output for different types of input. Typically, for a classification task, we would group inputs in classes and then, for each learner, get a vector by averaging all output vectors (the real vector outputted by the neural network) for each given class input and concatenating the averaged vectors. This means that, if we have a classification task with 10 classes and 10 output values (like digit recognition), the representative vector would be in ℝ 100 . More formally, if we have 𝑛 input classes and 𝑚 output values, then the representative vector is ∈ ℝ 𝑛×𝑚 . The case 𝑛 = 𝑚 is very likely (ℝ 𝑛 2 ) but it is also possible for 𝑛 and 𝑚 to be different. For example, a binary classification task may use only one output (𝑛 = 2, 𝑚 = 1), this is the case in our VSN experiment.

It is also possible to extract this real vector from each learner's dataset or some learners' metadata (like location), if the one in charge of the configuration of the system knows a good way to perform such a classification. In that case, the algorithm responsible for this process is completely dependent on the task and thus we will not consider that possibility here (as this is a general evaluation).

The process of obtaining these vectors corresponds to the projector function 𝑝 of our clustering model, as defined in Chapter 4 in Section II.1, as such we call it projection (as it is a projection function from the set of learners to a real vector space in which clustering takes place). As a consequence, the representative vector of a learner/learner 𝑎 is called 𝑝(𝑎). For recall, the objective of the projector function is to associate a real vector (usable as input for our clustering algorithm) with each learner. After running the clustering algorithm, semi-local models (implemented in predefined parts of the neural networks) are assigned directly from clusters (one cluster, one semi-local model), then we can average models normally. The process is described visually in Figure 5.1. This process is tailored for a federated setup, in which the clustering process can be done on a

Local learning Projection Clustering Distributed multi-task learning Figure 5.1: How clustering can be used to improve distributed multi-task machine learning central server. However, it should be possible (not studied here) to adapt it to a decentralized setup. Since decentralized k-means is possible [START_REF] Fellus | Decentralized K-Means Using Randomized Gossip Protocols for Clustering Large Datasets[END_REF], adapting our own clustering algorithm (k-meansbased) may also be possible. Some kind of gossip consensus system [START_REF] Maria | Discrete consensus in networks with constrained capacity[END_REF] could make it possible to select a common set of benchmark cases. We leave the study of such a setup and the definition of a protocol to future work (we also cannot conclude on the possibility of such a setup). Rather that projecting learners onto a real space (ℝ 𝑛 ), other authors[Lon+17; ZBT19] proposed systems in which differences between learners are not represented by a distance in a real vector space but by the weighted edges of a graph (learners are nodes). Like us, these authors designed their representation of difference specifically for their learning system, as a consequence, they could not be applied directly to ours. These formalisms only consider proximity between learners individually rather than considering groups of learners (clusters), as it fits the way learners collaborate in these systems (putting a, difference-dependent, cost on the divergence learners' models). However, it would be possible to adapt such a formalization of similarity to our system using a community-detection algorithm [START_REF] Vincent | Fast unfolding of communities in large networks[END_REF] in place of the clustering algorithm. For our system, we preferred to use a formalism that directly fits our system rather than twisting an existing formalism designed for a different kind of collaboration method.

III Experimentation

For our experiments, we reuse two datasets used in Chapter 3: modified MNIST and VSN2 . We first present VSN results, which are from a real application. Modified MNIST results are also presented but the clusters here are more obvious and, thus, do not allow comparing the performance of different clustering algorithms.

III.1 VSN

To evaluate our system in a real use case, we use the following task: vehicle recognition from sensors. We use a dataset from [START_REF] Duarte | Vehicle classification in distributed sensor networks[END_REF], which contains data from sensors (notably seismic and acoustic sensors) produced while some (military) vehicle passes near the sensors (grouped in nodes, which will be our learners). In this case, no obvious group affectation is possible without relying on clustering, allowing us to evaluate how our approach enables to effectively get better performance than a baseline.

The task proposed is to recognize the class of each vehicle (between assault amphibious or dragon wagon) from each sensor node's data (binary classification). To allow an MLP to perform this task, the data from each set of sensors (node) is first transformed into 50 seismic and 50 acoustic features (100 total inputs). This process (based on the Fast Fourier Transform) is described in the original paper ([DH04]).

For our distributed multi-task setup, we consider each sensors node as a learner. Each learner's task is to classify vehicles only from its local data. The tasks are similar, since all learners want to classify the same kinds of vehicles from the same kind of data, but different due to the location of sensors influencing their output.

To get real vectors for our clustering algorithms, we take locally pre-trained networks (one for each learner) and test them on a standard set of inputs. From the obtained output, we construct vectors 𝑝(𝑎) ∈ ℝ 2 from the average output of networks on each type of vehicle. For this experiment we use 16 peers, each with a training set of 50 samples. The mini-batch size is 25. We use an MLP with a 100=50=20=1 layout (for details on this notation and on experiments with MLP in general, see Chapter 3, Section V.1), trained with stochastic gradient descent, 𝜆 = 1 sigmoid activation functions and a 0.1 learning rate. Our clustering algorithms use Euclidean distance for 𝑑, 𝑛(𝑥) = 1 1+15𝑥 and 𝑣(𝑥) = √ 𝑥. 𝑝𝑟𝑐 = 20, 𝑚𝑚𝑡 = 5. Results are average values over 10 runs. We start with a local pre-training phase of 400 mini-batches. Then, we use the output of the pre-trained networks on a (identical for all peers) test set of 1000 samples to get inputs for clustering. With the output of our clustering algorithm, we define partial models to use for the real training phase of 400 mini-batches (we restart from scratch, using a new network with randomly initialized parameters, for a fair comparison with baseline results) and perform tests on 200 samples (specific to each learner). Here, the performance of our clustering algorithm is not evaluated by the affectation itself but by the performance of the resulting machine learning process (median accuracy).

Figure 5.2 gives examples of cluster affectations produced by different algorithms. Figure 5.3 compares the learning performance of the baseline from Chapter 3, the same distributed multi-task learning approach without benefits from clustering, to what can be achieved using affectations obtained from our clustering algorithms (k-means and OPTICS both failed to identify any cluster, returning a single global cluster containing all peers, thus we ignore them in the rest of this experiment, as they are equivalent to "no clustering").

While no obvious cluster affectation is visible, AUCCCR manages to find some clusters (differences between samples from the two variants of AUCCCR are more likely due to randomness than real differences between the two algorithms). k-means and OPTICS however both fail in this difficult case (using them would be equivalent to the baseline).

k-means and OPTICS fail to provide meaningful clustering information, not allowing any gain over the baseline (all logical affectations derivable from their outputs are in the baseline). With AUCCCR, Interpreting clusters to define models can be done in various ways. We could have peers in each cluster learn a single, cluster-specific, model, without individual divergence nor collaboration outside a cluster. We could have collaboration between clusters but keep models completely identical in each cluster. Finally, we could allow divergence inside a cluster and collaboration between clusters while still maintaining closer collaboration inside each cluster. Here, we present the results of three different schemes, which implement, using partial models, the configurations we described (other configurations are possible but these seemed to be the most obvious to us):

• global per cluster: A 100-50-20-1 (full network) model for each cluster (clusterless peers are trained locally).

• semi-local: A 100-35-14-1 model for all peers and a 0-15-6-0 one (dependent on the previous one; see Chapter 3, Section II.3 for the definition of "dependency") for each cluster (leaving nothing local for peers in clusters).

• semi-local+local: A 100-35-14-1 model for all peers and a 0-7-3-0 one (dependent on the previous one; see Chapter 3, Section II.3 for the definition of "dependency") for each cluster (leaving a 0-8-3-0 local model for peers in clusters).

Notice that these are only three of the numerous possibilities offered in our case by our distributed multi-task machine learning approach. We chose them because they gave good results in Chapter 3 (in terms of configuration to use) but further optimizations are possible and may lead to better results, even though in Chapter 3 we concluded that the solution we used in semi-local+local was the best in those experiments.

96/116

As we see in our results (Figure 5.3), global per cluster does not beat the baseline (no clustering), likely due to many peers (6 out of 16) being out of clusters and therefore performing purely local learning (the performance is slightly higher than that of local learning). Semi-local achieve a baselinelike performance, likely because the gain from the clusters is cancelled by the loss caused by a lack of intra-cluster differentiation. Semi-local+local, however, manages to obtain (slightly) better-thanbaseline results. The gain is limited but similar to what the baseline achieved with partial averaging compared to global.

III.2 Modified MNIST

The task associated with the MNIST dataset [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF] is handwritten digit recognition. From this task, we want to obtain a cooperation recommendation task, paving the way for the application of AUCCCR to the distributed multi-task learning method presented in Chapter 3. This method implies cooperation between different MLPs (Multi Layer Perceptrons). Now, we want our MLPs to have more or less similar tasks. To this aim, like in Chapter 3, we simply modified the MNIST task for some of those MLPs: part of our MLPs have to perform the standard digit recognition task, while others have to perform a modified task where two digits are exchanged, so a [9] would be classified as an "eight" and vice versa. The clustering task consists in assigning MLPs with the same task to the same cluster and MLPs with different tasks to different clusters. Since the optimal affectation is known for this test (as tasks differences are set manually), the objective of this test is to obtain this optimal clustering affectation, we do not consider the distributed training that would come after (since it would be the same as what is obtained with the manual affectation studied in Chapter 3).

Regarding the input vectors for our clustering algorithm, we use the method described earlier, adapted to the MNIST dataset. After a reasonable amount of (independent) training (from 25 to 100 mini-batch of 1000 samples each), we made each MLP work on the test part of the MNIST dataset. For each different digit tested (from 0 to 9), we took the average of the output vectors of each MLP (10 real values, which are the MLPs' estimated likeliness of the input image to be each of the digits from 0 to 9) and concatenated them in one vector 𝑝(𝑎) ∈ ℝ 100 . These vectors will be used as input for our clustering algorithms.

We use two metrics to evaluate the quality of the resulting affectation (of learners to models): the Identification rate, which is the proportion of the pairs of MLPs with identical tasks being in the same cluster, and the differentiation rate, which is the proportion of the pairs of MLPs with different tasks being in different clusters. Since in this task, the optimal affectation is known (a cluster = a permutation), these two metrics allow evaluating how the results of the clustering is close to this optimal affectation. We want both values to be as close to 1 as possible, which corresponds to the optimal affectation. A lower identification rate means that some learners that should have been part of the same cluster are not part of the same cluster. A lower differentiation rate means that some learners that should not have been part of the same cluster are part of the same cluster.

We train 16 MLPs, nine of them performing a standard classification task and seven of them having digits 8 and 9 permuted. MLPs are trained each on a different (disjoint) part of the MNIST dataset training set of size 3500. The MLPs have a 784=300=100=10 configuration with 𝜆 = 1 sigmoid activation functions and a 0.1 learning rate. The 𝑝(𝑎) ∈ ℝ 100 vectors are built from the 1000 first values of the MNIST dataset test part. Since this is just the pre-model affectation phase, as defined earlier, the training is purely local (no global no semi-local models).

Our clustering algorithms use Euclidean distance for 𝑑, 𝑛(𝑥) = 1 1+15𝑥 and 𝑣(𝑥) = √ 𝑥. 𝑝𝑟𝑐 = 20, 𝑚𝑚𝑡 = 5. Results are average values over 10 runs, error bars indicate standard deviation. Sample examples, based on a single run, are also given. In these, a color identifies a cluster, gray points represent standalone peers (or peers in a cluster of size 1). "AUCCCR-C" is Algorithm 8 in its normal variant, 'AUCCCR-CA" is the atomic variant.

The MLPs are trained with stochastic gradient descent, with a mini-batch size of 1000 and different numbers of mini-batches. Figure 5.4a presents the identification rate for various numbers of mini- We essentially observe that all algorithms remain close to perfect for all tests. While these tests on a very simple case do not allow determining which algorithm would be the best, they prove the validity of the idea of using clustering algorithms to provide cooperation recommendations for distributed machine learning.

Figure 5.5 gives examples of cluster affectations produced by AUCCCR-C. Since we used vectors from a space of dimension 100 (𝑝(𝑎) ∈ ℝ 100 ), we selected two relevant dimensions, 89 and 99 (corresponding to permuted digits), to make these 2D plots.

In that case, the clusters output are the same that an optimal manual affectation would have give.

III.3 General analysis of results

We proved that our idea of using clustering algorithms to identify good collaboration opportunities in distributed machine learning is valid, with our modified MNIST example, and that it could lead to performance improvement in cases where no manual affectation is possible, with our VSN example.

We can conclude that our initial idea of using clustering to improve performance in distributed multi-task machine learning works as expected. Also, our VSN results show that AUCCCR is superior to k-means and OPTICS in this context.

IV Individual interest analysis

Our clustering system's design is based on the individual interest of learners. Such a design comes from the idea that learners may have more or less interest for collaboration in different contexts. This question is not only important in contexts where such a clustering algorithm can be used. More generally, we would like to see if distributed machine learning is in the interest of learners individually and not just collectively. The point of this section is to evaluate the benefits learners get from our distributed machine learning system in both kinds of situations: where clustering is used and where it is not used. In this figure, we see that global averaging would have caused significant losses (compared to local learning) to many learners. The "global per cluster" clustering solution (the least efficient) may also cause losses compared to local training, but this effect is significantly lower than for global training, despite its better average accuracy. All other clustering solutions did not cause losses. This is also the case of partial averaging. Partial averaging seem to prevent losses by itself, even though clusteringbased solutions, other than "global per cluster", give better results.

IV.2 Without clustering

IV.2.a FEMNIST

Among the datasets we tested in Chapter 3, VSN and FEMNIST differentiate by the fact that they have real learners. Thus, let us study FEMNIST to evaluate how our multi-task learning system performs regarding individual losses without clustering. Our FEMNIST task has three variants. FEMNIST-A, the classical FEMNIST task, with all characters (62 classes). FEMNIST-M, were some similar-looking characters are merged in a single class as proposed in the NIST Special Database 19 documentation [Nat16] (47 classes). FEMNIST-D, limited to digits (10 classes). The results are pre- .9 (in order, A, M and D variants). The raw data from which those results are extracted is the same as for Figures 3.11, 3.12 and 3.13. Peers are ordered by average (over configurations) median (over runs) accuracy for aesthetic reasons. These figures show that partial averaging is over local learning for nearly all learners. The same is not true for global training. This last case can be better for some learners but it also causes significant losses to several learners. In an application with rational learners, this means that a global averaging solution would suffer from the collapse we mentioned when designing AUCCCR (learners preferring to be alone leaving clusters, reducing their value for other learners, which in turn leave and so on), unlike partial averaging. Some learners would have found global averaging better but this is not a stable situation, as several learners have interest to leave. We can conjecture that learners more "in the middle of the crowd" (with expectations close to the average of the group) would prefer global averaging above anything, while it would be the worst solution for more "dropout" learners.

IV.2.b Modified MNIST

Figure 5.10 represents the accuracy for each peer in the same experiment as Figure 3.20. Since in this experiment the original position of peers are directly linked to their tasks, the original order of peers is kept.

This figure shows us an interesting phenomenon. In this test, peers 1 to 9 have the same task, Figure 5.9: Individual peers' accuracies for various averaging levels on FEMNIST-D (peers sorted by average (over configurations) median (over runs) accuracy) -Same experiment (other perspective) as Figure 3.13 so do peers 10 to 16. The first group consists of 9 peers, the other of 7 peers. There is no notable difference between these two groups with local training nor with partial averaging. We just see that partial averaging is significantly better than local training for all peers. However, when it comes to global averaging, we see that some peers from the first group may benefit from it but others not, more importantly, global averaging causes a major loss for all peers of the second group. We can conjecture that, when using global averaging, a "majority voting" effect appears. The first group, the larger, "dominates" the second, forcing the global solution to be optimal for the first group and bad for the second. That said, even the first group does not significantly benefit from global averaging.

The "struggle" between the two groups for the "control" of the training offsets any gain, even for the larger group. Such a "struggle" does not appear with partial averaging.

To complete this evaluation on modified MNIST, we analyze individual peers over two variables defined in Chapter 3: difference rate (number of digits permuted) and number of peers with permutation. These results are presented in Figure 5.11 for the difference rate, which is obtained for the same raw data as Figure 3.25 and Figure 5.12 for the numbers of peers with permutations, which is obtained for the same raw data as for Figure 3.26.

Figure 5.11 confirms that the difference rates strongly affect minority peers' performance. We see that majority peers suffer from losses also. This is likely due to reduced efficiency of the training process. The difference rate has a much lower effect on partial averaging, but we still see that a very high difference also affects partial averaging performance and some kind of majority effect becomes visible on it only for 10 permuted digits. Figure 5.12 confirms that the effect on modified MNIST is more due to a majority vote than just distance to the average. Effectively, increasing the number of peers with permutation only slightly reduces the advantage of majority peers, though this reduction is still clearly visible, proving the existence of a distance effect. However, when groups are of equal sizes, the gap is much lower. Notice that this majority effect is specific to modified MNIST, due to the "binary" nature of the differences (permutation or no permutation). No such effect is visible on the digit-classification task FEMNIST-D (Figure 5.9).

IV.3 General analysis of results

We confirmed that our clustering system, and partial averaging, when clustering is not relevant, respect the individual interest of learners. Also, we saw that, when forced to collaborate without any freedom, learners tend to enter a form of competition, which is won by the most "central" or the most "numerous" learners.

While one may fear that distributed multi-task learning could lead to losses for some learners, our results indicate that our partial averaging system is rather resilient to that issue, unlike complete averaging.

V Conclusion

In this chapter, we showed that our idea of using clustering algorithms to identify good collaboration opportunities in distributed machine learning can help determine how peers should collaborate with each other in a decentralized learning context. We showed that this idea, when applied with our clustering algorithm AUCCCR, could lead to performance improvement in cases where no manual affectation is possible (with our VSN example).

We also showed that partial averaging in general is much more respectful of individual interests than global averaging, which can cause significant losses to "dropout" learners.

A possible extension of this work would be to use a hierarchical version of AUCCCR (future work) with our distributed multi-task machine learning system on a task where this would be pertinent, such as natural language processing with national variants of a language as a first level of hierarchy and regional variants as a second. Hierarchical clustering, unlike classical clustering, can produce a complete hierarchy of clusters, subclusters, etc. Our multi-task machine learning system allowing a complex hierarchy of semi-local models, a hierarchical clustering collaboration recommender would be able to exploit its flexibility better than with classical clustering. With such a system, we could have a semi-local model covering a certain set of peers and several other semi-local models covering subsets of this set. This way, we could exploit different levels of similarity between learners more deeply.

Conclusion I Objective

Machine learning is widely used in industry and lots of research works have been produced in this field. Despite this, effective application of machine learning in a distributed context remains rare, and this situation is partially caused by a relative lack of research work in this direction. Notably, the problem of distributed multi-task machine learning with neural networks lacked effective solution prior to our work.

This thesis started with the following question: "How can we have several agents aiming to learn similar but different functions collaborate to achieve their objective better than alone?". We identified several challenges to overcome in order to find an answer to this question.

Our main challenge was the combination of two elements: distributed learning and multi-task learning. Distributed learning comes in two variants: decentralized and federated. In a federated setup, while the learning process itself is done on clients, the coordination of clients is managed by a central server. In a decentralized setup, peers have to coordinate themselves, without the help of a central server.

Outside a multi-task context, this problem had already been studied by other researchers. This allowed us to find a proper existing solution: Federated Averaging [START_REF] Brendan Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF]. While designed for a federated setup, this solution can be extended to decentralized setups, relying on gossip averaging [START_REF] Jelasity | Gossip-Based Aggregation in Large Dynamic Networks[END_REF].

However, Federated Averaging does not tackle the other element of our main challenge: multi-task learning. A large part of our work thus consisted in proposing a solution for distributed multitask learning. We wanted our approach to be flexible, enabling engineers to optimize the learning process notably based on which learners have the most similar tasks and on which parts of those tasks (implemented in different parts of the learned models) are the most similar.

The ability to optimize the learning process based on the similarity of learners' tasks leads to another question. Since learners are likely to be numerous, this process should be automated. Furthermore, while in some situations metadata about learners may enable to easily perform this process automatically (e.g. natural language processing, when location can be used) in some other situations (e.g. handwriting recognition), it is harder to define which learners are more similar than others.

To tackle this issue, we decided to abstract this problem to something more general: cooperation recommendation. The principle of cooperation recommendation is to provide recommendations to agents on groups they should form with other agents to cooperate on some task; recommendations agents may reject if they are not in their individual interest. This left us with two question to solve: first, find a proper solution to cooperation recommendation and second, effectively use this general approach in a machine learning context.

In addition, another question emerged: may collaborative learning have negative impact for some learners while still being positive for the whole population of learners?

We first evaluated our clustering algorithm on synthetic data: Gaussian mixtures. It exhibited good performance compared to reference (k-means and OPTICS [START_REF] Ankerst | OPTICS: Ordering Points To Identify the Clustering Structure[END_REF]). Also, while our original idea was that larger groups would always be better, we showed that this algorithm still works well in situations were the utility function of agents is defined to prefer large enough but not too large groups.

We also evaluated our clustering algorithm on two real datasets: the BuddyMove [RA14] dataset and the Wholesale [START_REF] Gonçalo | Análise do perfil do cliente Recheio e desenvolvimento de um sistema promocional[END_REF] dataset, which corresponds to potential real applications of cooperation recommendation. Similarly to the case of Gaussian mixtures, our algorithm showed good performance compared to reference (k-means and OPTICS).

II.3 Evaluation of our cooperation recommendation system and exploration of learners individual interest

For this part of our work, we combined our cooperation recommendation system and our distributed multi-task learning system and study more precisely the implication of the notion of individual interest in this context. The first step for this contribution was to precisely define how our cooperation recommendation system and our distributed multi-task learning system could work together. While the data, extracted from learners, to be used as input for the clustering algorithm could come from any source (the most likely, outside what we did with benchmarking pre-trained models, is metadata on the learner), we still had to choose one to use for our experiments, and we wanted it to be as general as possible.

We choose to extract this data from outputs of locally pre-trained neural networks on a common benchmark dataset. With this approach, we showed the efficiency of our cooperation recommendation system combined with our distributed multi-task learning system, notably its ability to reach a global optimum (it terms of quality of learner groups) on a modified MNIST task and its ability to improve performance in a VSN task, where manual optimization is not straightforward.

We further explored the question of individual interest of agents and found that, while Federated Averaging often caused individual losses (in cases where it is globally better than local learning), our distributed multi-task learning system is more respectful of individual interest. Performance in this context is also improved by our cooperation recommendation system. This answers our question on possible negative individual impact of collaborative learning: it is not a significant issue with our system.

III Future developments

III.1 Technical aspects

Our system was tested on a range of possible applications, but this does not cover the whole range of neural networks applications. The networks we considered we rather small compared to what is used in modern deep learning. We also did not test our system with recurrent neural networks like LSTM, Convolutional Neural Networks or on more complex deep neural networks. Evaluating our system in these contexts would be a major step toward effective adoption for several applications. Also, while our distributed multi-task machine learning system is working, it can still be improved. Notably, we did not consider practical communication limitations. Working on reducing the communication overhead or adaptation to unreliable networks may be interesting.

Also, neither our distributed multi-task machine learning system nor our cooperation recommendation system were created for hostile contexts. Working on protecting our system for potential attackers could be interesting, notably with its ability to be used in decentralized contexts. This may notably include application with our previous work on Robust Privacy-Preserving Gossip Averaging [START_REF] Bouchra | Robust Privacy-Preserving Gossip Averaging[END_REF].

Concerning our cooperation recommendation system, a significant development would be to create a hierarchical version of our clustering algorithm, AUCCCR, and to use it with our distributed multitask machine learning system to create a hierarchy of semi-local models that would exploit more of 107/116 the possibilities of the dependency system in more complex applications (such as natural language processing).

Finally, the considerations on individual interest we presented may benefit from a more advanced game theoretical study (where individual unsatisfaction may occur and affect the whole system).

III.2 Practical aspects

Outside technical considerations, effective adoption of the methods proposed in this thesis will imply several practical challenges. The first of these would be to appeal to actors of the machine learning ecosystem. This should not be too hard, as major companies are already working on federated machine learning and non-profit organizations are interested in decentralized solutions to provide alternatives to large companies. Organizations adopting our system would also have to make users adopt our system and get benefits from it. For the federated variant, we can assume that major technological companies, already working on federated learning, will find a way to make our system profitable. It will improve the efficiency of their machine learning based services (multi-task aspect) while delegating training tasks to clients' devices (distributed aspect). The idea of "personalized" machine learning and keeping data local could appeal to users wanting more efficient and personalized services while still preserving their privacy. The decentralized variant (or a potential lightweight federated variant, with low synchronization overhead) may also enable non-profit organizations to provide effective machine learning-based services without having to invest in costly infrastructure. They may thus become a more effective alternative to major companies. While the respect of individual interest may also appear as a good feature to client, this affirmation must be moderated. In the past, Google's game theory-optimized advertisement auction system did not convince clients unaware of game theory, even though they were professional clients. However, in our case, the system is no unintuitive as this example was (the auction was won by the highest bidder but the price was the second bidder's one, which is an optimal auction system), so math-free communication should work to present this feature of our system to the general public.

Other practical concerns include legal considerations, notably data protection regulations such as the European General Data Protection Regulation (GDPR), or similar regulations that can be adopted elsewhere (CCPA, PIPL…). At the time of writing this text, GDPR is still too recent to know how courts will effectively rule cases linked to it, notably in the case of machine learning. While some raised concerns on GDPR making most machine learning applications effectively illegal (due to models being based on private data), it seems highly improbable that effective application of the law will be restrictive to such an extreme point, due to the major business interests associated with machine learning. We may thus assume that if our system gets adopted by major companies, such extreme law interpretations would not challenge it. Since machine learning models, while derived from private data, are likely to be, in practice, not considered as private data themselves, companies' lawyers are likely to present valuables arguments in favor of federated/decentralized learning (including our system), which is more protective of the training (private) data (kept local rather than sent to a central server). Abstract: Machine learning is one of the most important and active fields in present computer science. Currently, most machine learning systems are still using a mainly centralized design. Even when the final application is to be delivered in several systems, potentially millions (and even billions) of personal devices, the learning process is still centralized in a large datacenter. This can be an issue if the training data is sensitive, like private conversations, browsing histories, or health-related data.

In this thesis, we tackle the problem of distributed machine learning in its multi-task form: a situation where different users of a common machine learning system have similar but different tasks to learn, which corresponds to major modern applications of machine learning, such as handwriting recognition or speech recognition.

We start by proposing a design of an effective distributed multi-task machine learning system for neural networks. We then propose a method to automatically optimize the learning process based on which tasks are more similar than others. Finally, we study how our propositions fit the individual interests of users.

•

  Distributed multi-task learning proper [Chapter 3] • Coalition formation applicable to distributed multi-task learning [Chapter 4] • Effective application of coalition formation to distributed multi-task learning and exploration of the associated vision's practical implications [Chapter 5]

Figure 2 . 3 :

 23 Figure 2.3: Illustration of the concept of centralized, federated and decentralized architectures. Ω indicates coordination tasks, Σ computation tasks.

Figure 2 . 4 :

 24 Figure 2.4: Centroid clusters (shapes) vs density clusters (colors)

Algorithm 1 :5

 1 k-means 1 function k-means(𝑃 , 𝑘) is 2 Randomly select 𝑘 starting points in 𝑃 3 Initialize the 𝑘 groups 𝑔 𝑖 with the previously selected points 4 repeat Compute barycenters 𝑏 𝑖 of groups 𝑔 𝑖 6 for 𝑝 ∈ 𝑃 do 7

Figure 3

 3 Figure 3.1: 3 peers with 5 models

Figure 3

 3 Figure 3.3: Models with dependency relationships (A →B ⇔ A depends on B)

  Figure 3.5: The neural networks three peers implementing five models (Blue global; Red semi-local; Green, Cyan and Purple local) and the corresponding dependency graph (A →B ⇔ A depends on B). We that links (weights) connecting two neurons from different models are considered par of the dependent model (if any) for averaging purposes.

  as the set variant of 𝜇: (𝑋) = {𝜇(𝑐)|𝑐 ∈ 𝑋}, we can write 𝑀 = ∘ 𝐶 (𝑀 = 𝜇 ∘ 𝐶 would have been an abuse of notation).

Figure 3

 3 Figure 3.6: Sets and functions we defined. Π: set of all parameters. 𝒞: set of all cells. ℳ: set of all models.

  Figure 3.7 gives an example of what could be a neural network with our generic formalism. In this figure we have for example:

Figure 3

 3 Figure 3.8: A multi-layer perceptron with 4 partial models (one per color)

Figure 3 ℎ𝑖𝑑𝑑𝑒𝑛

 3 Figure 3.9: Our Associative Neural Network model

Algorithm 5 :

 5 Learning Data: 𝑡ℎ𝑙𝑑 threshold for neurons' activation, 𝑙 the learning rate 1 for 0 ⩽ 𝑖 < ℎ𝑖𝑑𝑑𝑒𝑛.𝑠𝑖𝑧𝑒 do 2 for 0 ⩽ 𝑗 < 𝑣𝑖𝑠𝑖𝑏𝑙𝑒.𝑠𝑖𝑧𝑒 do 3 if 𝑣𝑖𝑠𝑖𝑏𝑙𝑒.𝑜𝑢𝑡𝑝𝑢𝑡[𝑗] == 1 then 4 if ℎ𝑖𝑑𝑑𝑒𝑛.𝑜𝑢𝑡𝑝𝑢𝑡[𝑖] == 1 then 5 ℎ𝑖𝑑𝑑𝑒𝑛.𝑤𝑒𝑖𝑔ℎ𝑡[𝑖][𝑗]+ = 1-ℎ𝑖𝑑𝑑𝑒𝑛.𝑤𝑒𝑖𝑔ℎ𝑡[𝑖][𝑗] [𝑖][𝑗]-= 1+ℎ𝑖𝑑𝑑𝑒𝑛.𝑤𝑒𝑖𝑔ℎ𝑡[𝑖][𝑗] 2 𝑙 8 for 0 ⩽ 𝑖 < 𝑣𝑖𝑠𝑖𝑏𝑙𝑒.𝑠𝑖𝑧𝑒 do 9 for 0 ⩽ 𝑗 < ℎ𝑖𝑑𝑑𝑒𝑛.𝑠𝑖𝑧𝑒 do 10 if ℎ𝑖𝑑𝑑𝑒𝑛.𝑜𝑢𝑡𝑝𝑢𝑡[𝑗] == 1 then 11 if 𝑣𝑖𝑠𝑖𝑏𝑙𝑒.𝑜𝑢𝑡𝑝𝑢𝑡[𝑖] == 1 then 12 𝑣𝑖𝑠𝑖𝑏𝑙𝑒.𝑤𝑒𝑖𝑔ℎ𝑡[𝑖][𝑗]+ = 1-𝑣𝑖𝑠𝑖𝑏𝑙𝑒.𝑤𝑒𝑖𝑔ℎ𝑡[𝑖][𝑗] [𝑖][𝑗]-= 1+𝑣𝑖𝑠𝑖𝑏𝑙𝑒.𝑤𝑒𝑖𝑔ℎ𝑡[𝑖][𝑗]

Figure 3

 3 Figure 3.11: Averaging level on FEMNIST-A -Accuracy for various averaging levels and numbers of mini-batches

  , 3.18 and 3.19 (in order, A, M and D variants).

Figure 3

 3 Figure 3.13: Averaging level on FEMNIST-D -Accuracy for various averaging levels and numbers of mini-batches

Figure 3

 3 Figure 3.14: Averaging scheme on FEMNIST-A -Accuracy for various numbers of mini-batches and schemes

Figure 3

 3 Figure 3.15: Averaging scheme on FEMNIST-M -Accuracy for various numbers of mini-batches and schemes

Figure 3

 3 Figure 3.16: Averaging scheme on FEMNIST-D -Accuracy for various numbers of mini-batches and schemes

Figure 3

 3 Figure 3.18: Number of peers on FEMNIST-M -Accuracy for various numbers of peers per group and averaging levels

Figure 3

 3 Figure 3.19: Number of peers on FEMNIST-D -Accuracy for various numbers of peers per group and averaging levels

Figure 3

 3 Figure 3.21: Convergence on modified MNIST -Accuracy over time (convergence) for various averaging levels

Figure 3

 3 Figure 3.22: Number of peers on modified MNIST -Accuracy for various numbers of peers and averaging levels

  Figure 3.23: Semi-local averaging on modified MNIST -Accuracy for various mini-batch sizes and averaging schemes

  Figure 3.24: Semi-local averaging with local models on modified MNIST -Accuracy for various minibatch sizes and averaging schemes

Figure 3

 3 Figure 3.25: Difference rate on modified MNIST -Accuracy for various difference rates and averaging levels

Figure 3

 3 Figure 3.26: Number of peers with permutation on modified MNIST -Accuracy for various numbers of peers with permutation and averaging levels

Figure 3 .Figure 3

 33 Figure 3.29: Averaging on VSN -Accuracy for various averaging levels and numbers of mini-batches

  cluster(𝐴, 𝑝, 𝑘) 9 𝑛𝑣𝑎𝑙 ← ∑ 𝑎∈𝐴 𝑛(𝑑(𝑝(𝑎), 𝑏𝑎𝑟𝑦 𝑝 (𝑎𝑓𝑒𝑐𝑡.𝑔𝑟𝑜𝑢𝑝(𝑎)))) × 𝑣(#𝑎𝑓𝑒𝑐𝑡.𝑔𝑟𝑜𝑢𝑝(𝑎))

Algorithm 7 : 2 𝑟𝑎

 72 Clustering algorithm 1 function cluster(𝐴, 𝑝, 𝑘) is /* k-means++ initialization */ (𝐴, 𝑑𝑚𝑖𝑛2) /* random element from 𝐴, relatives probabilities given by 𝑑𝑚𝑖𝑛2 */ 8 𝑛𝑔𝑟𝑝[𝑖] ← {𝑛𝑎} // appends {𝑛𝑎} to ngrp 9 foreach 𝑎 ∈ 𝐴 do 10 𝑑𝑚𝑖𝑛2[𝑎] ← min(𝑑(𝑝(𝑎), 𝑝(𝑛𝑎)) 2 , 𝑑𝑚𝑖𝑛2[𝑎]) /* main loop */ ] ← argmax 𝑖∈⊥∪⟦0,𝑘-1⟧ (𝑛(𝑑(𝑝(𝑎), 𝑏𝑎𝑟𝑦 𝑝 (𝑔𝑟𝑝[𝑖] ∪ 𝑎))) × 𝑣(𝑠𝑖𝑧𝑒[𝑖] + 𝟙 𝑎∉𝑔𝑟𝑝[𝑖] )) /* assuming 𝑔𝑟𝑝[⊥] = ∅ and 𝑠𝑖𝑧𝑒[⊥] = 0 */ 20 𝑛𝑠𝑖𝑧𝑒[𝑏𝑔𝑟𝑝[𝑎]] + + // does nothing if 𝑏𝑔𝑟𝑝[𝑎]

Figure 4 . 1 :

 41 Figure 4.1: Clusters found in Bi-Gaussian (colors are clusters, grey points are alone)

FigureFigure 4 . 2 :

 42 Figure 4.2: Metrics in Bi-Gaussian for all algorithms

Figure 4 . 3 :

 43 Figure 4.3: Clusters found in 3 Gaussians (colors are clusters, grey points are alone)

Figure 4 . 4 :

 44 Figure 4.4: Metrics in 3 Gaussians for all algorithms

Figure 4 .

 4 11 presents the clusters obtained with the different algorithms and 𝑣(𝑥) functions. You can see the precise size of each cluster in Figures 4.12(

Figure 4 . 5 :

 45 Figure 4.5: Clusters found in Gaussians Star (colors are clusters, grey points are alone)

Figure 4 .

 4 18 presents the 3 following metrics : the average utility of agents (Figure 4.18c), the average losses of agents (Figure 4.18a) and the share of agents having losses (Figure 4.18b) for a range of scale values.

  Figure 4.6: Metrics in Gaussians Star for all algorithms

Figure 4 . 7 :

 47 Figure 4.7: Metrics in Gaussians Star for different numbers of agents by different algorithms

Figure 4 . 8 :

 48 Figure 4.8: Metrics in Gaussians Star for different standard deviations by different algorithms

Figure 4 . 9 :

 49 Figure 4.9: Metrics in Gaussians Star for different scales by different algorithms

)Figure 4

 4 Figure 4.10: Group value functions

Figure 4

 4 Figure 4.11: Clusters with various algorithms and different 𝑣(𝑥)

Figure 4 . 2 𝑟𝑎Figure 4 Figure 4 Figure 4

 42444 Figure 4.12: Clusters size with 𝑣(𝑥) = √ 𝑥 by different algorithms

Figure 4 .Figure 4 Figure 4 Figure 4

 4444 Figure 4.18: Metrics in BuddyMove for different scales by different algorithms

Figure 4 .Figure 4 Figure 4 Figure 4

 4444 Figure 4.24: Metrics in Wholesale for different scales by different algorithms

Figure 5 . 2 :

 52 Figure 5.2: Clusters found by various algorithms in VSN (colors are clusters, grey points are alone)

Figure 5 . 3 :

 53 Figure 5.3: Different configurations possible with AUCCCR clustering compared to baseline configurations (no clustering) on the VSN dataset

Figure 5

 5 Figure 5.4: Metrics for various mini-batches numbers and different clustering algorithms for modified MNIST

Figure 5 . 5 :

 55 Figure 5.5: Clusters found by AUCCCR-C in MNIST for various numbers of mini-batches (colors are clusters, grey points are alone)

Figure 5 . 6 :Figure 5 . 7 :

 5657 Figure 5.6: Individual peers' accuracies for various averaging levels on VSN (peers sorted by average (over configurations) median (over runs) accuracy) -Same experiment (other perspective) as Figure 5.3

Figure 5 . 8 :

 58 Figure 5.8: Individual peers' accuracies for various averaging levels on FEMNIST-M (peers sorted by average (over configurations) median (over runs) accuracy) -Same experiment (other perspective) as Figure 3.12

Figure 5

 5 Figure 5.10: Individual peers' accuracies for various averaging levels on modified MNIST (peers in original order) -Same experiment (other perspective) as Figure 3.20

Figure 5

 5 Figure 5.11: Individual peers' accuracies for various averaging levels and difference rates on modified MNIST (peers in original order) -Same experiment (other perspective) as Figure 3.25

Figure 5

 5 Figure5.12: Individual peers' accuracies for various averaging levels and numbers of peers with permutation on modified MNIST (peers in original order) -Same experiment (other perspective) as Figure3.26

Titre:

  Contributions à l'apprentissage machine distribué multitâche Mot clés : Distribué, Décentralisé, Fédéré, Apprentissage machine, Multitâche, Réseaux de neurones Résumé : L'apprentissage machine est un des domaines les plus importants et les plus actifs dans l'informatique moderne. La plupart des systèmes d'apprentissage machine actuels utilisent encore une architecture essentiellement centralisée. Même si l'application finale doit être délivrée sur de nombreux systèmes, parfois des millions (voire des milliards) d'appareils individuels, le processus d'apprentissage est toujours centralisé dans un centre de calcul. Ce peut être un problème notamment si les données d'apprentissage sont sensibles, comme des conversations privées, des historiques de recherche ou des données médicales. Dans cette thèse, nous nous intéressons au problème de l'apprentissage machine distribué dans sa forme multitâche : une situa-tion dans laquelle différents utilisateurs d'un même système d'apprentissage machine ont des tâches similaires, mais différentes, à apprendre, ce qui correspond à des applications majeures de l'apprentissage machine moderne, comme la reconnaissance de l'écriture ou de la parole. Nous proposons tout d'abord le concept d'un système d'apprentissage machine distribué multitâche pour les réseaux de neurones. Ensuite, nous proposons une méthode permettant d'optimiser automatiquement le processus d'apprentissage en identifiant les tâches les plus similaires. Enfin, nous étudions comment nos propositions correspondent aux intérêts individuels des utilisateurs. Title: Contributions to distributed multi-task machine learning Keywords: Distributed, Decentralized, Federated, Machine learning, Multi-task, Neural networks

  , encore que je ne sois pas tout à fait sûr pour 𝑃 ≠ 𝑁 𝑃. General analysis of results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . V Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . II Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . II.1 Distributed multi-task learning proper . . . . . . . . . . . . . . . . . . . . . . . II.2 Cooperation recommendation applicable to distributed multi-task learning . . . II.3 Evaluation of our cooperation recommendation system and exploration of learners individual interest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III Future developments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III.1 Technical aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III.2 Practical aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	IV.3 6 Conclusion
	I
	Pour paraphraser Albert Einstein

• Simple, Efficient and Convenient Decentralized Multi-Task Learning for Neural Net- works [BFT21b]:

  Which presents our distributed multi-task learning system. Presented at the 19th Symposium on Intelligent Data Analysis (IDA 2021). Authors: Amaury Bouchra Pilet, Davide Frey and François Taïani.

• AUCCCR: Agent Utility Centered Clustering for Cooperation Recommendation [BFT21a]: Which presents our clustering algorithm for collaboration recommendation. Presented at the 9th International Conference on Networked Systems (NETYS 2021). Authors: Amaury Bouchra Pilet, Davide Frey and François Taïani. • Robust Privacy-Preserving Gossip Averaging [BFT19]: Done previous to this thesis itself, this paper presents a private gossip averaging algorithm, which empowers our distributed multi-task learning system to protect privacy in a decentralized context. Presented at the 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2019). Authors: Amaury Bouchra Pilet, Davide Frey and François Taïani. • Foiling Sybils with HAPS in Permissionless Systems: An Address-based Peer Sampling Service [BFT20]: Done previous to this thesis itself, this paper tackles the issue of attackers trying to flood open decentralized systems with malicious peers. Presented at the 25th IEEE Symposium on Computers and Communications (ISCC 2020). Authors: Amaury Bouchra Pilet, Davide Frey and François Taïani. 11/116

  Work on artificial intelligence began with the study of natural intelligence. In 1943, Warren McCulloch and Walter Pitts proposed a mathematical modelization of animal 12/116 𝑦 = 𝑓 𝑝 (∑ 𝑖 𝑤 𝑖 𝑥 𝑖 )

	𝑥 1
	𝑥 2	𝑦
	𝑥 3
	Figure 2.1: A formal neuron
	In
		Out
	In
	Figure 2.2: A neural network
	brains

Algorithm 2 :

 2 Decentralized multi-task learning Data: 𝑛𝑢𝑚 number of peers, 𝑚𝑏𝑛 number of training rounds between averaging, 𝑀, the set of all models, 𝑇, the set of all neurons' index grouped by slice (index differences between peers are ignored for concision), 𝑁 and 𝐷 as defined before

	1 loop
	2	each peer 0 ⩽ 𝑝 < 𝑛𝑢𝑚 does
	3	for 0 ⩽ 𝑖 < 𝑚𝑏𝑛 do
	4	𝑁 𝑝 .train(𝐷 𝑝 )
	5	foreach 𝑚 ∈ 𝑀 do
	6	averageModel({𝑝 ∈ ⟦0, 𝑛𝑢𝑚⟦|𝑝 ⊩ 𝑚},𝑚) // Does nothing if model 𝑚 is local
	7 function averageModel(𝑃,𝑚) is
	8	foreach 𝑖 ∈ 𝑇 do
	9 10	foreach 𝑘 ∈ 𝑇 𝑖 |𝑘 ⊢ 𝑚 do average({𝑁 𝑝 𝑖,𝑘 .q|𝑝 ∈ 𝑃 })

11 averageRestricted({𝑁 𝑝 𝑖,𝑘 .w|𝑝 ∈ 𝑃 },{𝑗|𝑗 ⊢ 𝑚 ∨ 𝑗 ⊢ 𝑚.𝑑𝑒𝑝𝑠}) 12 foreach 𝑘 ∈ 𝑇 𝑖 |𝑘 ⊢ 𝑚.𝑑𝑒𝑝𝑠 do 13 averageRestricted({𝑁 𝑝 𝑖,𝑘 .w|𝑝 ∈ 𝑃 },{𝑗|𝑗 ⊢ 𝑚})

Table 3

 3

	.1: Summary of experiments

Table 4 .

 4 1: Symbols used in formulas and algorithms distance between 𝑥 and 𝑦; 𝑣(𝑛) ∶ ℕ → [1, +∞[ is the value of a group of size 𝑛 (increasing, 𝑣(1) = 1);

Associative Neural Network presented in Section IV.2

Associative Neural Network presented in Section IV.2

This work uses the term "local model" to designate each client's instance of the generic model the system is learning and "global model" to designate the common model managed by the server. This terminology shall be distinguished from the (anterior) "local model", "semi-local model" and "global model" terminology we use in this work, which designates portions of a complete model that are implemented by either a single, a subset or all clients/peers.

Some authors use the term "personalization", rather than multi-task learning, to describe their approach.

A way to model conditional dependencies between variables[START_REF] Pearl | Bayesian networks: A model of self-activated memory for evidential reasoning[END_REF].

, also called relative entropy.

Authors themselves point the similarity of their work with a previous approach for non-distributed sequential learning of different tasks[START_REF] Schwarz | Progress & Compress: A scalable framework for continual learning[END_REF], even though they do not present this work as a source of inspiration.

Authors include an additional fine-tuning phase with the Reptile algorithm[START_REF] Nichol | On First-Order Meta-Learning Algorithms[END_REF].

Different formalizations of equilibrium exist for hedonic games, in which "options" available to players are not as clearly, and statically, defined as in other games, but all have the same philosophy: no player should have interest in leaving its group and/or joining a foreign group. 20/116

𝑖, 𝑗 and 𝑘 are used as generic index variables. Unless explicitly stated otherwise, 𝑖, 𝑗 and 𝑘 from different formulas have not the same meaning.

#ℝ = ℶ 1 > ℶ 0 = ℵ 0 > 𝑘(∀ 𝑘∈ℕ ), since the set of neurons is finite, it is not an issue to use a real index to define each neuron's activation function, even if #ℝ ℝ = ℶ 2 > ℶ 1 = #ℝ implies that a real value can not index the set of all real functions

Formally, a(n undirected) multi-hypergraph is a pair 𝐻 = (𝑉 , 𝐸) where 𝑉 is the set of vertices and 𝐸 the multi-set of edges, which are non-empty subsets of 𝑉.

In the case of neural networks, these are, more simply, multi-graphs, or even simple graphs (with "loops") if neurons' activations functions have no more than one parameter (and no "loops" if activation functions are not parameterized). Notice that, while neural networks induce directed graphs, direction is not needed here and, thus, not included in the formalism.

We could impose the same restriction to all sets of cells or even to parameters associated with a single cell without much loss of generality but this is not necessary.

With the previous assumptions, a possible way to get indexes (identical for all peers) for parameters is to take cells (vertices) common index (function 𝜉 𝜌 (𝑐), which is obtained by indexing all pairs (𝜒(𝑚), 𝜒 𝑚 (𝑐))|𝑚 ∈ 𝜌 ∧ 𝑐 ⊢ 𝑚, with some integer pairs indexing function common to all peers) and hyperedges indexes (among other hyperedges share the same "ends") (function 𝜛(𝜋) = 𝜛(𝑒) with 𝑒 being the edge corresponding to 𝜋). Once this is done, you take for each parameter the set Ξ(𝜋) = {𝑛 = 2 𝜉 𝜌 (𝑐) |𝑐 ∈ 𝐶(𝜋)} ∪ {3 𝜛(𝜋) }. Then index all parameters based on Ξ(𝜋) (the set of all finite sets of integers can be indexed by integers; just take, for each integer 𝑛 in the set, the 𝑛th prime number and multiply all those primes, you have a unique index due to the unicity of prime numbers decomposition) to obtain (𝜋). Notice this process can be done locally by each peer only based on common information and its local parameters and will return the same result.

we use 𝑥 to contrast with the notation 𝑧 used for parameter vectors in Section II.4 as this analysis focuses on the evolution of these vectors over time and uses different indexing for better readability in this context

Our code is available at https //gitlab inria fr/abouchra/distributed neural net orks

While descriptive decision theory has shifted to the more exact Prospect theory[START_REF] Kahneman | Prospect Theory: An Analysis of Decision under Risk[END_REF], this work is about automated decision support and, thus, based on expected utility[START_REF] Ranganathan | An Automated Decision Support System Based on Game Theoretic Optimization for Emergency Management in Urban Environments[END_REF].

The term "atomic" here is not to be understood as commonly used by computer scientists in the field of concurrency; this terminology comes from economics where it is used with a similar meaning as in this work, to describe competitive markets

Our code is available at https //gitlab inria fr/abouchra/distributed neural net orks

We chose these functions because they are simple functions that have the right shape; we did not optimize this choice.

See Chapter

2, Section III.1 and Figure 2.3 for a definition of the different kinds of setups

We do not use FEMNIST due to its the lack of clusters. Maybe a similar dataset not limited to US hand-writers would have offered more interesting features.

Difference rate

Accuracy

Accuracy depending on difference rate and layout-scheme 0-0-0-0 784-250-80-10 784-300-100-10 784-300-100-0 784-300-100-10-0 0-0-0-0-0 784-250-80-8-10 784-300-100-10-10 Figure 3.28: Different layouts on modified MNIST -Accuracy for various difference rates and layoutsschemes

II Contributions

Our contributions can be divided in three parts, each corresponding to a chapter of this thesis:

II.1 Distributed multi-task learning proper

The motivation of this work is to provide an effective solution to the distributed multi-task machine learning problem we defined as our main objective. Our approach is based on the same principle as Federated Averaging [START_REF] Brendan Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF] to enable distributed learning: averaging the parameters (real values) learned by learners. While this base approach is simple, enabling multi-task learning with this system required developing new concepts.

The key concept of this approach is the notion of partial model, enabling a partial averaging process where only portions of learners' neural networks are averaged, rather than the whole neural network. Partial models allow learners to learn collaboratively (on a shared model) while still being able to diverge from each other (with their personal model).

We extended this beyond just having shared models (global model) and personal models (local models) with semi-local models, shared by several learners but not all. This enables to group more similar learners together, further optimizing the collaborative learning process.

Since the geometry of neural networks is defined by the neurons, we wanted the models to be associated with neurons, but the parameters to be averaged are (mostly) weights connecting two neurons. This raised the question of which model parameters connecting two neurons from different models should be part of. To answer this question, we introduced the notion of dependency between models. If a model A depends on a model B, then all learners implementing model A must also implement model B. This allowed us to assign the parameters connecting two neurons from different models to a single model, the lower in the hierarchy of dependencies.

We evaluated our approach with several experiments on various datasets: FEMNIST [Cal+19], modified MNIST [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF], VSN [START_REF] Duarte | Vehicle classification in distributed sensor networks[END_REF] and an artificial associative task. This evaluation showed that our system performs better than reference (non multi-task distributed learning and local learning) and proved the interest of the two novel notions we introduced: partial models and dependency.

II.2 Cooperation recommendation applicable to distributed multi-task learning

Our objective for this work was to create an algorithm that would enable to automatically group learners together for optimized multi-task learning. To create our cooperation recommendation system, we started from the general formalism of Hedonic Games. There is no general solution to the problem formalized by hedonic games and existing algorithms based on this formalism were not applicable to our situation.

Hedonic games rely on the notion of utility, the interest each agent (for example, a learner) has for a certain group. Assuming that this utility can be computed by a certain formula based only on the size of the group and the distance between the agent and the barycenter of the group, we managed to reformulate our hedonic game as a clustering problem that can be solved by an algorithm similar in its principle to what is used for centroid-based clustering.

The best known algorithm for centroid-based clustering is k-means [START_REF] Stuart | Least squares quantization in PCM[END_REF]. However, this algorithm is only based on distance to barycenter, not on the size of groups. Thus, we created a novel algorithm using the same iterative local optimization principle as k-means, but able to take the group size into account.