Thibaud Hulin
email: thibaud.hulin@utc.fr

Analyser les traces d'activité pour évaluer les ressources électroniques

Keywords: évaluation, ressources électroniques, trace, activité, apprentissage, recherche d'information, documentation

Afin d'améliorer la qualité de l'évaluation des ressources électroniques, nous proposons une approche intermédiaire entre l'analyse des logs et l'étude clinique de l'activité de recherche d'information documentaire. Nous montrons comment construire un système d'évaluation automatique des ressources côté utilisateur. Le modèle que nous proposons suppose un ensemble de concepts fondamentaux, et un processus pour l'implémentation que nous présentons. Un tel système a de nombreux avantages : il renforce l'apprentissage de l'usager, il est peu coûteux, et il donne beaucoup plus de précisions sur l'utilisation réelle des ressources et de ses fonctionnalités.

Introduction

Les études récentes sur le « web log analysis » orientent volontiers l'étude des usages vers l'analyse des fichiers produits par des serveur de données. Ces approches privilégient les données quantitatives obtenues du côté du fournisseur de service, et tendent à se normaliser avec le projet Counter [Boukacem, 2005]. Ces résultats peuvent être nuancés par des analyse qualitatives de l'activité en étudiant les usages généraux des revues électroniques [Broudoux, 2008] ou les points des vue des auteurs [START_REF] Nicholas | On the tips of their tongues : authors and their views on scholarly publishing[END_REF]. Pourtant, force est de constater qu'approches qualitatives et quantitatives se rejoignent rarement en raison des objectifs qui différent : la question de l'évaluation des ressources est finalement isolée des questions à orientation clairement ergonomiques comme celle de la modélisation de l'activité de recherche d'information [START_REF] Tricot | Les hypermédias : approches cognitives et ergonomiques[END_REF]] ou celle de la normalisation des interfaces de bibliothèques numériques [START_REF] Lompré | Normes ergonomiques et usages des bibliothèques numériques. Usages et pratiques dans les bibliothèques numériques[END_REF]. Pourtant, l'approche statistique produit elle aussi des connaissances sur l'activité de recherche d'information, et a besoin d'une connaissance précise des usages pour s'affiner. D'où la nécessité de construire une méthodologie scientifique qui puisse récupérer des informations sur les usages du côté de l'utilisateur concret, tout en les rendant disponibles à l'analyse générale. Pour cela, nous proposons ici une méthodologie basée sur l'analyse des traces d'activité plutôt que sur les journaux systèmes. Notons que cette approche locale tend à renforcer la capacité des bibliothèques à comprendre les pratiques de ses usagers, sans dépendre des données fournies par les éditeur. L'enjeu est alors de réduire le coût de l'analyse tout en respectant des contraintes éthiques qui suppose pour l'usager comme pour la bibliothèque d'accéder à l'ensemble des traces d'activité. L'intérêt de manipuler ses traces d'activité a donc un intérêt double : assurer une meilleure transparence des investissements, mais aussi favoriser la recherche d'information par une meilleure prise de conscience de l'activité réalisée.

Exigences et prérequis pour la modélisation d'un système d'évaluation des ressources numériques « côté client »

Afin de construire un système d'évaluation des ressources documentaires à partir des traces de l'utilisateur, nous avons tenté dans un premier temps de rassembler les concepts fondamentaux qui président à une théorie de la trace numérique. Nous nous sommes pour cela appuyé sur l'expérience de différents dispositifs utilisant des traces d'interaction numériques, ayant pour but notamment d'enrichir une théorie de la trace numérique. Celle-ci s'appuie en partie sur les travaux des théoriciens de l'activité ainsi que sur les approches interactionnistes de la cognition [Ollagnier-Beldame, Magali 2006]. De ce point de vue, le processus d'apprentissage n'est compréhensible qu'à partir de sa situation dans l'environnement, et en tant qu'il est distribué entre les différents participants. En ce sens, l'évaluation des ressources ne peut se faire indépendamment de la compréhension des stratégies et méthodes mises en oeuvre par les chercheurs d'information. Or, la qualité de l'activité de recherche d'information est un processus complexe, voire non séquentiel [Dillon, 1996]. Il n'est pas purement intellectuel dans la mesure où l'ensemble de la vie psychique, comme les émotions, ont un rôle déterminant [START_REF] Kuhlthau | Seeking meaning : a process approach to library and information services[END_REF]. Dès lors, toute description de l'activité de recherche d'information ne saurait être exhaustive. Le sens des traces d'activité ne saurait donc être obtenu par la réduction de l'univers social, de l'univers documentaire et de l'univers du discours [START_REF] Metzger | Temps et documents numériques[END_REF] mais au contraire en replaçant ces traces dans ces univers de relations et d'interactions.

L'évaluation des ressources ne peut se faire uniquement en termes de quantité d'informations transmises. En bibliométrie, c'est plutôt « la perte d'information » qui est susceptible de fournir « un gain de signification » [Lafouge, 2002, p. 57]. L'activité de recherche elle-même ne consiste pas à accumuler un nombre de données importants : plus la quantité d'informations croit, plus sa synthèse est coûteuse. Dans le cadre d'une recherche documentaire, c'est donc en dernier ressort la satisfaction de l'utilisateur qui assure la qualité de la recherche : encore qu'un chercheur apprenti n'a peut-être pas encore tous les moyens de s'approprier toutes ses trouvailles.

Certes, les techniques de récupération des URLs côté serveur, c'est-à-dire côté fournisseur de ressources via un proxy, et les techniques de fouilles de données atteignent un niveau d'avancement important, par exemple avec [Hong, 2009]. Pour autant, en théorisant assez peu les traces, elles manquent le fait qu'une trace est déjà une construction théorique. La théorie de l'évaluation des ressources devrait donc se méfier davantage du fait que les traces ne sont pas des données brutes. Par exemple, une trace sans information temporelle minimale et sans contexte est trop peu pour faire sens : elle n'est plus qu'une inscription dans la matière, au mieux une empreinte, à condition qu'elle soit reliée à un sujet qui est à son origine. Ainsi, d'une part, la trace ne se réduit pas à l'ensemble des observés qui la composent ; d'autre part, la trace est elle-même une construction qui relie des observés entre eux.

Dans une certaine mesure, la série des observés ainsi reliés ne peut faire sens. Par exemple, la lecture d'une série de requêtes ou d'URLs ne nous apprend pas grand chose sur l'activité réalisée. Il nous faut des informations contextuelles qui puissent assurer les liens sémantiques. La possibilité de réunir ces URLs ou requêtes à un même sujet, voire à un même moment de la recherche permet en revanche de définir l'espace d'une session. Le repérage des termes sémantiques, par exemple en terme de classes de vocabulaires, peut permettre de définir le champ de la recherche : parfois son but, et l'information manquante.

À y regarder de plus près cependant, circonscrire un « but » de la recherche à partir de traces d'interaction nous paraît un projet fort ambitieux. Certes, il serait plus facile d'évaluer une ressources à partir du moment où elle répond ou non à un ensemble de questions que se pose le chercheur d'informations. Pourtant, même lorsque l'on formalise la recherche, le chercheur d'information modifie son approche au fur et à mesure des résultats obtenus. Ainsi, l'évaluation des ressources doit tenir compte du fait que le projet est mobile. La théorie du projet de recherche doit donc pouvoir évoluer. Les traces construites par l'analyste et l'évaluateur ne doivent pas être figées, mais évoluer à l'aide d'un ensemble de modèles. Pour évaluer les ressources, il nous faut donc : une théorie ou un modèle de la trace générale des interactions, à partir de laquelle on sait quelles informations collecter ; et un ensemble de théories ou modèles de traces composés à partir de cette trace originelle, qui permette de diversifier les points de vue sur l'activité d'un ou de plusieurs sujets. Par exemple, la série des URLs est une trace, mais la série des requêtes, issues de la série des URLs, est une trace composée susceptible d'apporter une signification plus profonde.

Afin d'assurer ces relations entre traces, il est nécessaire d'identifier les éléments qui les composent. Dans le cas de la trace première, c'est l'ensemble des observés qui la composent, dans notre exemple, une série d'URLs. Mais les éléments qui composent les traces de plus haut niveau ne sont pas nécessairement issus de la collecte des observés. Ils sont une série d'observés si l'on procède par sélection dans la trace première : les URLs reliées à tel sujet ou à tel IP. En revanche, la série des mot-clés, extraits des URLs, sont des éléments composés à partir d'une théorie de la composition : une série de transformations qui sont prédéfinies dans le modèle de la trace des requêtes. Cette théorie de la transformation va donc émettre des choix à partir des données d'interaction obtenues. D'où la nécessité de construire une théorie générale de la trace d'interaction, qui mette en évidence une structure commune aux différentes traces. Pour nous en tenir à notre exemple, on trouve des attributs communs aux traces d'URLs et de requêtes : des identificateurs, des dates, et des numéros d'IPs. Comme nous souhaitons construire un modèle côté client, on pourra préciser cette notion d'IP qui peut désigner plusieurs personnes assises derrière un même poste. Les attributs fondamentaux des traces sont donc : un identificateur, un descripteur ou une classe pour regroupes les éléments de type identique, une date, et un sujet à l'origine de l'action.

L'idée de s'intéresser aux traces d'un sujet identifié et non aux traces d'une machine (IP) entraîne davantage de précision dans l'analyse. Mais elle pose aussi de nouvelles questions. Ainsi, il devient possible de prendre en compte la diversité des stratégies de recherche. Les critères d'évaluation d'une ressource différeront entre chercheur d'informations, qui renvoient à un « style » différent lié à un « profile » adapté [Gauch, 2007]. La modélisation d'un profile est une étape indispensable pour définir les critères de l'évaluation, mais aussi un projet impossible, au sens où il ne recouvre jamais exhaustivement les spécificités de la personnalité du sujet. Il ne s'agit donc pas de faire des hypothèses sur ce que pense où ce que sait un sujet, mais plutôt de décrire des constantes comportementales, à l'intérieur du cadre de la trace première. Par exemple, on observera que tel acteur commence presque systématiquement sa recherche d'information par une recherche web avant d'utiliser des ressources électroniques académiques, tandis que tel autre acteur procède à l'inverse, alors qu'ils sont tous deux confrontés à la même lacune d'information. Il n'est pas nécessaire de se demander pourquoi ils agissent ainsi, ni si l'un des deux a raison : on se contentera de décrire ces comportements issus de l'observation des sujets, et d'inclure ces normes de comportements dans des modèles, afin d'affiner les calculs pour l'évaluation.

Cependant, on prendra garde de ne pas faire de ces modèles a priori des lois comportementales. Il est donc nécessaire de ne pas se contenter de récupérer l'information « dans le dos » de l'utilisateur. Nous faisons ici l'hypothèse que l'évaluation gagne en précision lorsque l'on inclut les utilisateurs dans le processus de description de leur activité. Pour cela, nous restituons les traces d'activité à l'utilisateur plutôt que de faire du système à base de trace un système transparent, en lui donnant la possibilité d'annoter ses traces. Ainsi, la restitution de ses traces à l'utilisateur a ainsi un double avantage :

-elle renforce le processus d'apprentissage par la réflexivité de l'activité ; -elle permet d'enrichir les traces par les commentaires de l'utilisateur. Ainsi, le système doit inclure un modèle de visualisation des traces. Ceci signifie que les modèles de traces sont à destination de l'évaluateur et prescripteur du système à base de traces, mais aussi à destinataire de l'usager. Plusieurs modèles de traces peuvent donc être envisagées en fonction de ces deux types d'utilisateur. Les traces, qui sont signifiantes, sont donc associables à des vues sémantiquement pertinentes par rapport à des usages attendus, mais aussi inat-tendus, ce que doit permettre de mesurer l'analyse des annotations. La brique de visualisation des traces, qu'il s'agisse d'un tableau, d'une chronologie, d'un rapport, d'un film, etc., est déterminée en fonction des usages visés. Là encore, nous ne recherchons pas un modèle de visualisation a priori pertinent pour tout utilisateur et de manière générique, qui ferait abstraction de la situation concrète dans laquelle l'activité tisse des relations.

Enfin, une dernière brique est nécessaire pour comparer les ressources. Celleci n'est pas logiquement déduite de l'activité tracée, elle dépend d'indicateurs, de variables et d'équations. En revanche, elle s'appuie sur des sources d'informations beaucoup plus riches que si l'on avait une série d'URLs à des dates fixes, puisqu'elle exploite :

-des observés uniquement visible côté client, par exemple : est-ce que telle ressource a été vue ou seulement ouverte dans un onglet oublié par la suite ? -des séquences d'activité comparables entre elles, par exemple : si chaque requête donne lieu à l'ouverture d'un document en texte intégral chez un utilisateur, tandis qu'un second ouvre moins de documents mais prend le temps de lire les résumés, on peut penser que l'évaluation du second utilisateur sera de meilleure qualité que le second ; -des annotations, notamment sur les ressources à disposition.

Fondements du système à base de traces

Nous présentons ici les concepts fondamentaux d'un système informatique, avec ou sans mémoire, gérant une base de traces modélisées dans le cadre d'un système observé, et offrant des services de transformation, de requête, de partage, etc. Compte tenu des spécificités d'un tel système, nous le désignerons du nom de « système à base de traces », en suivant les conceptualisations et expérimentations de [Champin et al., 2004] ; [Champin, Prié et Mille, 2003] ; [START_REF] Settouti | Système à base de trace pour l'apprentissage humain. Colloque international TICE 2006[END_REF] ; [START_REF] Laflaquière | [END_REF] ; [Mille et Prié, 2006], qui nous fournissent une théorie générale de la trace d'interaction conforme aux exigences précédemment décrites.

Afin de construire une méthodologie pertinente, nous devons définir clairement les concepts que nous allons utiliser. En premier lieu, nous devons produire une analyse qui puisse donner des résultats quantifiables en terme d'interactions : nous saisirons donc des évènements côté machine que nous pouvons distinguer et situer dans le temps. Ces éléments minimaux destinés à fournir des traces d'activité sont des évènements numériques observés. Ainsi, un « observé » est un élément temporellement situé. Enregistré dans un système à base de traces, dans le cadre d'une future trace modélisée, il possède un type défini. Il est associé à un être humain en interaction avec la machine, le sujet. Enfin il est en relation avec d'autres évènements du même type. Nous appelons observés l'ensemble des évènements ainsi enregistrés dans notre système. Un observé peut correspondre à une action, comme par exemple un clic sur un lien ou l'ouverture du navigateur.

Les observés seront construit à partir d'un système d'enregistrement. Nous pouvons utiliser des sondes, des journaux systèmes déjà implantés, enregistrer une voix ou filmer le sujet qui interagit : tous ces dispositifs sont donc à l'origine d'une « source de collecte ». Celle-ci ne se confond pas avec le dispositif social mis en oeuvre par l'observateur, c'est plutôt le dispositif qui détermine la source de collecte. Le dispositif d'observation inclut donc un protocole d'observation, mais aussi le modèle de collecte. La collecte est donc à l'origine d'une série d'observations attendues enregistrées en série. Cette attente correspond donc à une modélisation effectuée en amont, c'est la « trace modélisée ».

Parmi les traces modélisées, on distingue la trace issue de la collecte d'observés, ou « trace première », des traces réalisées à partir de celle-ci. Tandis que la trace première correspond à l'inscription d'observés dans le système de gestion de bases de traces, les traces secondaires donnent lieu à un ensemble de calculs en vue de réaliser des « traces composées », dites aussi secondaires. En effet, il est difficile de recomposer l'activité effectuée à partir des observés bruts fournis par la source de collecte. Il faut donc envisager la modélisation de traces composées automatiquement, en vue d'une présentation signifiante des observés pour l'observateur ou pour le sujet observé.

Les calculs qui permettent d'obtenir de nouvelles traces à partir d'une trace première sont appelés des « transformations ». Ces opérations portent sur une ou plusieurs traces modélisées, et produisent elles-aussi une trace modélisée. Soit elle est décrite de manière automatique et systématique, dans le cadre du modèle de transformation, selon un échéancier donné ou de manière synchrone ; soit elle résulte d'une intervention ponctuelle ou manuelle.

La présentation des traces à l'utilisateur, ou « visualisation » interactive de traces, se fait alors en fonction de modalités prédéfinies, par consultation d'une représentation visuelle. Des vues peuvent être directement associées aux différentes traces calculées. Il peut s'agir d'un tableau, d'une chronologie, etc.

Le système à base de trace, qui comprend jusqu'ici un calculateur, un système de vues et un espace de stockage, peut aussi effectuer des enrichissements plus complexes de traces en vue d'une « documentarisation ». Tandis que les traces premières et secondaires sont régies par une structure identique, la documentarisation obéit à des normes très différentes. Par exemple, il peut s'agir de la création d'un rapport utilisable dans un traitement de texte, ou bien d'un document multimédia correspondant à une sélection d'évènement issus de l'observation native ou empirique, etc.

Processus de modélisation de notre système

Une fois les bases du système à base de traces postulées, nous nous attelons ici à décrire les étapes que nous suivons pour construire notre système à base de traces. [START_REF] Jermann | From mirroring to guiding : A review of state of the art technology for supporting collaborative learning[END_REF] a réalisé un état de l'art des technologies en la matière. À sa suite, on distinguera les systèmes de réflexivité, qui représente l'état d'une série d'interactions à partir d'indicateurs, des systèmes de conseils (coaching systems), qui propose des conseils à partir de l'interprétation de ces indicateurs. qui prescrit plusieurs étapes pour la conception d'un modèle de l'activité de recherche documentaire. Nous nous appuyons ici sur sa méthodologie pour construire les étapes de notre processus de modélisation. Chacune de ces étapes vise à construire une série de modèles pour :

-la collecte des évènements d'interaction ; -les traces qui interprète et relie ces évènements ; -les profils d'utilisateur ; -les visualisation des traces ; -le moteur de calcul des traces ; -le classement et l'évaluation des ressources. Nous entrons ainsi dans l'application concrète de notre projet. Dans la mesure où nous ne pouvons envisager l'analyse d'une situation hyper-générique, nous avons défini notre projet en fonction d'un cadre d'utilisateur précis. Nous espérons cependant décrire de manière suffisamment abstraite ce projet de manière à ce que l'on voit clairement qu'il est applicables à d'autres publics et à d'autres situations, voire, pourquoi pas, à n'importe quelle bibliothèque.

Première phase : la collecte des données

Dans un premier temps, nous réalisons une étude ergonomique sur les actions possibles de recherche documentaire à l'aide des logiciels appropriés. Dans le cas de l'évaluation des ressources électroniques, nous avons étudié les interfaces de Mozilla Firefox pour la navigation et de Zotero pour la gestion des références. Nous avons aussi étudié le comportement réel de formateurs et d'étudiants à la recherche documentaire, cependant il s'agit pour nous d'une plus-value d'informations, dont la description n'entre pas dans le projet de cette intervention. Toutefois, ces études permettent d'identifier les actions de l'utilisateur importantes en suivant les possibilités de l'interface. En effet, il n'est pas toujours possible d'étudier le code directement, qui n'est pas nécessairement structuré en terme d'actions, du point de vue de l'utilisateur. L'analyse des actions permet de construire une hiérarchie des actions utilisateurs. Cette analyse est doublement intéressante car elle permet de :

-définir une classe d'objets appelés « observés » qui possèdent un certain nombre d'attributs et qui définissent un modèle de trace première ; -définir les emplacements dans le code des logiciels où l'on placera des capteurs afin de journaliser les actions utilisateurs.

Seconde phase : la construction d'un modèle de traces

Une fois la liste des actions obtenues, celles-ci sont organisées en objets et attributs à partir d'un objet général dit « observé », composé d'attributs fondamentaux : un numéro d'identification, un descripteur et une date. De là, on définit des schémas de transformation de ce modèle de trace première. Par exemple, les actions de navigation vont donner lieu à des changements de focus sur telle ou telle ressource électronique, ce qui permet de mieux cerner son usage. Nous privilégions ici les traces suivantes :

-l'ensemble des observés ; -les sujets ; -les actions de gestion bibliographique ; -les actions concernant l'usage des documents téléchargés ; -les pages et leur focus (ayant été vues ou non, si elles sont ouvertes dans un onglet) ; -les URLs ouvertes ayant été vues une fois ou seulement ouvertes dans un onglet voisin ; -les ressources ; -les mots ayant fait l'objet d'une demande de traduction ; -les requêtes ; -les mot-clés issus des requêtes. L'intérêt de chacune de ces traces n'est pas égal pour l'utilisateur de ce système. Par exemple, la vue des URLs ouvertes n'est qu'une trace intermédiaire qui permet de construire la trace apportant des informations sur les ressources.

Troisième phase : définition d'un profil évaluatif

Plutôt que de lier des variables aux actions tracées afin d'évaluer simplement les ressources, nous définissons un modèle d'activité normalisé fait d'une séquence d'actions types. Plus ce modèle est répété et suivi, plus la ressource sera évaluée positivement par rapport à ce modèle. Certes le système de calcul est plus complexe, mais il permet d'éviter de supposer qu'une suite d'actions isolées est nécessairement positive vis-à-vis d'une ressource.

Quatrième phase : construction du moteur de calcul de traces

Le moteur de calcul des traces définit quelles informations sont composées ou héritées à partir des traces intermédiaires, jusqu'à la trace première. Il prend aussi en charge la comparaison de la trace d'activité réelle d'un utilisateur avec une séquence attendue ou prescrite, par comparaison de séquences. L'évaluation se fait par le biais de constantes et de règles logiques qui permettent de calculer des écarts.

Cinquième phase : la représentation des traces pour l'utilisateur

La représentation des traces pour l'utilisateur est destinée au sujet qui fait l'action ou pour un sujet indépendant chargé d'évaluer le travail produit (formateur, bibliothécaire, responsable de l'évaluation d'une ressource...). Elle permet de construire au moins un tableau des actions réalisées, éventuellement liée à une représentation graphique chronologique. L'utilisateur a alors la possibilité de commenter ses traces. La présence d'un attribut « notation », à l'intérieur du champ de commentaire, lui permet d'évaluer précisément les résultats de ses recherches. Chacune des traces présentées ci-dessus est associable à un tableau de présentation et à une chronologie.

Sixième phase : le classement des ressources

Le classement et l'évaluation des ressources utilisées est ici résultat des comparaisons de séquences d'activité à l'aide du moteur de calcul de traces. Le groupement de règles agissent ici comme des automates finis au sens mathématique. La présentation de ce tableau se fait dans le cadre d'une présentation d'indicateurs en direct, ou bien sous la forme d'un rapport, dans le cadre d'une documentarisation de l'activité. Cette évaluation finale a bien sûr du sens à partir d'un nombre suffisant d'utilisateur, même s'il s'agit d'un groupe pilote, représentatif de l'ensemble des utilisateurs de la ressource.

Difficultés rencontrées et limites

Nous avons repéré un certain nombre d'avantages à notre système, pour la formation, l'apprentissage, la politique documentaire et l'amélioration des interfaces des ressources. Cependant, il existe aussi un certain nombre de difficulté que nous rencontrons et que nous présentons ici.

Première difficulté, le calcul et la comparaison de séquences reste relativement complexe sur le plan ergonomique et mathématique. En effet, si l'on part du point de vue qu'il n'y a pas de « one best way » en recherche documentaire, on considérera que la méthode du meilleur chercheur d'information n'est pas nécessairement transposable, elle inclut des variables propres au sujet de la recherche et au hasard si ce n'est la sérendipité. Par conséquent, il est plus facile d'évaluer la qualité des résultats obtenus que la qualité des ressources documentaires utilisées. Ce problème est d'ailleurs constant dés lors qu'il s'agit d'évaluer les ressources électroniques. Notre réponse est que notre approche ne vise pas à supprimer le travail des chercheurs sur la question de l'évaluation des ressources. Elle ne fait que transposer le questionnement dans un cadre où il est plus facile de saisir l'activité sans avoir besoin de faire appel à un protocole d'observation couteux en temps ou en énergie. A défaut de maîtrise, cette approche a l'avantage d'offrir un niveau de portée de vue sur l'activité important, tout en permettant l'usage de raisonnements mathématiques avancés sur les traces rendu envisageable par la construction d'automates [Diekert, 1995].

Seconde difficulté, comment transposer la situation qui a inspiré cette construction à l'ensemble des centres documentaires ? Sans doute la question de l'universalité de cette méthode se pose-t-elle avec légitimité. À l'origine, cette recherche est née de notre tentative de répondre aux besoins de formateurs et d'apprentis ingénieurs à la recherche d'information à la bibliothèque de l'INSA de Lyon au début de l'année 2009. Nous présentons ici la démarche suivie de manière suffisamment abstraite de ses conditions contextuelles afin qu'il soit envisageable de la poursuivre dans des espaces documentaires différents. Pourtant, en raison même de notre hypothèse initiale, centré sur l'irréductibilité de l'activité à une séquence fermée, nous ne pensons pas qu'il soit possible de proposer un modèle de traces qui soit valable en tout temps et en tout lieu. Notre projet est donc de partager notre expérience de conception de manière à ce qu'il soit possible de l'enrichir en fonction des exigences d'évaluation : le besoin d'un fournisseur de ressource n'est pas le même qu'un responsable de bibliothèque. Cependant, nous ne voyons pas en quoi ce modèle ne permettrait pas de répondre à ces besoins différents.

Ce problème de l'universalité de tout modèle, nous devons tenter de le résoudre, tout en ayant bien conscience que nous ne l'atteindrons pas. En effet, si nous interrogeons l'activité réelle à l'aide de traces, c'est bien que nous ne pouvons la décrire, qu'elle échapper à toute grille, qu'elle résiste à toute description, qu'elle est avant tout un « élan de vie et de santé sans borne définie » [START_REF] Schwartz | Travail & ergologie[END_REF]]. Ainsi l'activité du vivant ne se donne que de manière partielle, sous forme de traces justement. Il est donc bien difficile, dans ce cas, de tirer de notre système des conclusions pour une évaluation définitive des ressources ou de résoudre de manière tranchée l'interprétation des traces ainsi obtenues. Nous ne prétendons qu'affiner le processus d'observations des interactions et d'améliorer ainsi la connaissance de l'usage des ressources utilisées.

Conclusion

Nous recherchions un modèle pour évaluer les ressources électroniques en se rapprochant du faible coût de l'analyse automatique à de précision de la description ergonomique. Nous avons présenté un modèle qui réponde à cette double exigence, en décrivant un système à base de traces d'interaction pour l'évaluation des ressources documentaires. Celui-ci suppose un dispositif conceptuel rigoureux ainsi que la mise en oeuvre progressive d'un dispositif que nous avons ici décrit. Ainsi nous rapprochons-nous de la description automatique d'une activité complexe et continue : en effet, les objectifs d'une recherche documentaire peuvent être extrêmement variés et prendre des contours inattendus.

Appliqué à la question de l'évaluation des ressources électroniques, le système à base de traces d'interactions a pour but d'améliorer la réflexivité et donc l'apprentissage, la qualité de la formation à la recherche documentaire et de son évaluation, d'améliorer l'investissement des centres de documentation en terme de ressources et d'accompagnement, de mieux connaître les usages et les fonctionnalités pertinentes ou sous-utilisées des ressources électroniques académiques. La méthodologie proposée tente de concilier les avantages de l'analyse qualitative ou ergonomique et l'analyse quantitative, liée à la fouille de données. Elle n'évite pas les difficultés de comparaison de l'activité réelle avec l'activité anticipée ni pour l'interprétation statistique. Elle propose un cadre enrichi à partir d'une sémantique de l'activité.

Cependant, nous n'ignorons pas les difficultés rencontrées, qui tiennent à la difficulté de construire des modèles normatifs d'activité, d'assurer l'universalité de notre approche, enfin de proposer des conclusions définitives sur l'évaluation des ressources. Pour éclairer les problèmes de sens liés à l'interprétation des traces obtenues, une mise en oeuvre expérimentale est en cours de réalisation. Enfin, à l'heure où paraît cet article cependant, nous devrions avoir publié la version 0.2 de notre logiciel ergodoc [Hulin, 2009]. Ce logiciel, qui suit les prescriptions indiquées ci-dessus, se présente sous la forme d'un module pour Mozilla Firefox. Il devrait permettre de présenter un certain nombre des caractéristiques décrites ci-dessus.

Remerciements

Je remercie vivement toute l'équipe SILEX du LIRIS de l'Université de Lyon I, en particulier Yannick Prié pour m'avoir permis de réaliser cette intervention. Je remercie également l'équipe des formateurs de la bibliothèque de l'INSA de Lyon, les chercheurs et doctorants du laboratoire ELICO de Lyon pour leurs conseils, les étudiants de l'INSA de Lyon pour s'être soumis à mon examen. Je remercie les organisatrices et organisateurs du colloque de Lille pour leur accueil, en particulier Chérifa Boukacem. Merci au LASELDI, à Ioan Roxin et à son équipe de Montbéliard pour m'avoir permis de poursuivre mes recherches. Je remercie enfin et surtout ma famille, en particulier Michèle, Morgane et Mélisande pour leur soutien et pour leur compréhension. Références BOUKACEM, C., SCHÖPFEL, J., (2005). Statistiques d'utilisation des ressources électroniques : le projet COUNTER. Bulletin des Bibliothèques de France 50, no. 4, p. 62-64. BROUDOUX, E., et CHARTRON, G., (2008). Traitements et pratiques documentaires. Paris : ADBS. CHAMPIN, P.-A., LAFLAQUIÈRE, J., MILLE, A., PRIÉ, Y., (2004). Musette : a framework for Knowledge Capture from Experience. 12ème Atelier de Raisonnement à Partir de Cas. CHAMPIN, P.-A ., PRIÉ, Y., et MILLE, A., (2003). Musette : Modelling uses and tasks for tracing experience. ICCBR, n°3, p. 279-286. DIEKERT, V., (1995). The book of traces. River Edge, NJ (USA) : World Scientific. DILLON, A., (1996). TIMS : A Framework for the Design of Usable Electronic Text, Advances in discourse processes, n°58, p. 99-120. GAUCH, S., et al., (2007). User Profiles for Personalized Information Access, The Adaptive Web, vol. 4321, p. 54-89. HONG, H., (2009). On Application of Data Mining to Library and Information Science -A Content Analysis Based on CNKI Databases, Journal of Modern Information, sept. 2009. HULIN, T., (2009). Ergodoc, Module pour augmenter la réflexivité de la recherche d'information par la visualisation des traces d'activités, <https ://addons.mozilla.org/fr/firefox/addon/51326>.


Andrew Chee

Sébastien Loustau
email: sebastien.loustau@univ-pau.fr

Learning with BOT -Bregman and Optimal Transport divergences

Keywords: PAC-Bayesian theory, Convex duality, Bregman divergence, Optimal transport, Sequential learning, Regret bounds

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

Introduction 1.PAC-Bayesian theory

PAC-Bayesian machine learning theory can be traced back to the work of Shawe-Taylor and Williamson (see [START_REF] Shawe-Taylor | A pac-analysis of a bayesian estimator[END_REF][START_REF] Shawe-Taylor | Functional bregman divergence and bayesian estimation of distributions[END_REF]) and Mac-Allester ( [START_REF] David | Some pac-bayesian theorems[END_REF][START_REF] David | Pac-bayesian stochastic model selection[END_REF]). The goal of PAC-Bayesian theory is to get distribution free generalization bounds, ie that holds a priori, but where some prior or arbitrary domain knowledge is available on the set of candidate models. As in Bayesian statistics, it leads to a posteriori estimates of the generalization performances based on informative priors. Historically, it was proposed as an alternative to the structural risk minimization problem based on the Vapnik-Chervonenkis theory since Bayesian algorithms minimize a risk expression involving a likelihood or goodness of fit term based on the training data, and a prior probability, leading to a trade-off between empirical accuracy and complexity in terms of divergence from the prior. Formally, in the discrete case, for a set of finite weak learners G = {g 1 , . . . , g p } and a prior distribution π = (π k ) p k=1 over this set G, the first PAC-Bayesian bound appears in [START_REF] David | Some pac-bayesian theorems[END_REF]. Given a loss function (g, •) and a distribution S over a sample z 1 , . . . , z m , [START_REF] David | Some pac-bayesian theorems[END_REF] shows the existence of a decision ĝ ∈ G such that with probability 1 -δ, the generalization error R(•) := E z∼S (•, z) of ĝ is bounded as follows: R(ĝ) ≤ min

1

It leads to the model selection of a particular candidate ĝ ∈ G that trades off the goodness of fit with the minimum description length -log π(ĝ) (see [START_REF] Peter | The Minimum Description Length Principle (Adaptive Computation and Machine Learning)[END_REF]). The result holds for any prior π but is interesting if there exists a prior π giving high probabilities on rules g ∈ G that fit well to the training problem. In term of domain knowledge, this is equivalent to suppose that particular candidates g ∈ G with low complexity fit well to the learning problem. This model selection principle is outperformed in [START_REF] David | Pac-bayesian stochastic model selection[END_REF] where (1) is extended to uncountable set G. In this case, a stochastic algorithm is prefered and leads to the existence of a distribution ρ ∈ P ¸(G) the set of probability distributions over G such that with probability 1 -δ, the expected generalization error is bounded as follows:

E g∼ρ R(g) ≤ inf ρ∈P(G) E g∼ρ 1 m m t=1 (g, z t ) + K(ρ, π) + log 1 δ + log m + 2 λ , (2)
where K(ρ, π) is the Kullback-Leibler divergence from prior π to ρ. Noting that since K(δ g , π) = -log π(g) for any π and g, (2) appears as a powerfull generalization of [START_REF] David | Pac-bayesian stochastic model selection[END_REF]. Minimizing the RHS in (2) corresponds to compute the convex conjugate of K(•, π) and leads to a stochastic algorithm based on the following exponential weighted average or Gibbs posterior:

ρ(g) := 1 Z λ exp - λ m m t=1 (g, z t ) π(g), (3)
where λ > 0 is a temperature parameter. This distribution reaches a trade-off between accuracy over the sample and Kullback-Leibler divergence from the prior, where the introduction of the Kullback-Leibler divergence is based on a Chernoff bound in [1, Lemma 4].

Based on these theoretical foundations, PAC-Bayesian theory has been widely used in high dimensional statistics, where g = p i=1 θ i f i ∈ G often represents the linear span of a set of dictionary functions {f 1 , . . . , f p }, where p is potentially huge. In this context, a sparsity scenario means that a small subset of the dictionary provides a nearly complete description of the underlying phenomenon. [START_REF] Arnak S Dalalyan | Mirror averaging with sparsity priors[END_REF] proves generalization performances under this sparsity scenario (see also [START_REF] Audibert | Fast learning rates in statistical inference through aggregation[END_REF][START_REF] Gerchinovitz | Sparsity regret bounds for individual sequences in online linear regression[END_REF][START_REF] Li | A quasi-bayesian perspective to online clustering[END_REF]). Then, instead of using a model selection technique leading to sparse estimators such as the lasso (see [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF][START_REF] Bühlmann | Statistics for high-dimensional data[END_REF]), [START_REF] Arnak S Dalalyan | Mirror averaging with sparsity priors[END_REF] proposes a stochastic mirror averaging that reach a PAC-Bayesian inequality as in [START_REF] Shawe-Taylor | A pac-analysis of a bayesian estimator[END_REF]. Using a sparsity prior, one gets sparsity oracle inequalities. These techniques provide theoretical trade-off between goodness of fit and complexity in terms of 0 or 1 -norm of the solution. Whereas these complexity measures have been widely used in the literature (see [START_REF] Chee | Sparsity regret bounds for xnor-nets++[END_REF] for an application in deep learning), we expect in this paper more generic penalties to use any ad-hoc criterion for the set of candidates learning machines.

Main contributions

In this contribution we provide PAC-Bayesian bounds such as (2) replacing the Kullback-Leibler divergence and its usual convex conjugate (3) with Bregman and optimal transport divergences. We first extend the materials presented above to a more general divergence then the Kullback-Leibler divergence, namely Bregman divergences. In this context, we show that the two main ingredients, namely the convex duality gathering with the cancellation argument originated in [START_REF] Andrew R Barron | Are bayes rules consistent in information?[END_REF] can be still applied to our context. It leads to a new family of stochastic algorithms that generalize the previous exponential weighted averages with equivalent theoretical guarantees. We also propose to introduce optimal transport as a promising alternative to Bregman (or Kullback) divergences. Indeed, by proving the main assumption originated in [START_REF] Juditsky | Learning by mirror averaging[END_REF] (see Assumption A(Π, δ λ ) below), we lead to a new kind of procedure where the exponential averages are replaced by optimal transport optimization that satisfies a new PAC-Bayesian bound. With these theoretical results, we expect numerous possible regret bounds and new theoretical trade-off between goodness of fit and different complexity measures related with energy constraints (see [START_REF] Chee | Sparsity regret bounds for xnor-nets++[END_REF] for a survey of some recent advances in the environmental impact and electirc consumption of learning machines).

In the sequel, we adopt the online learning scenario where a sequence of deterministic values {z t , t = 1, . . . , T } is observed, where z t ∈ Z could be a couple (x t , y t ) in supervised learning, or an input data in unsupervised learning. Based on a loss function (g, z) that measures the loss of decision g ∈ G at observation z ∈ Z, the goal of the forecaster is to build a sequence of distributions {ρ t , t = 1, . . . , T } with small expected cumulative loss. We are hence looking at regret bounds of the following type:

T t=1 E g∼ρt (z t , g) ≤ inf g∈G T t=1 (z t , g) + pen(g) + δ T , (4)
where pen(g) extends the sparsity paradigm where pen(g) = g 0,1 thanks to the introduction of Bregman divergences in [START_REF] Shawe-Taylor | A pac-analysis of a bayesian estimator[END_REF], and δ T > 0 is a residual term. To build this sequence of mixtures, we act sequentially as follows. At each round t ≥ 1, we have timely access to a temporal prior ρt derived from the previous observations. More precisely, given z t , we are looking at a randomized decision g ∼ ρt+1 where the posterior distribution ρt+1 ∈ P(G) is the solution of the following minimization:

ρt+1 := arg min ρ∈P(G) E g∼ρ h t (g) + 1 λ D(ρ, ρt ) , (5)
where h t (g) is related with the loss of decision g ∈ G at z t and D(ρ, ρt ) is a suitable divergence from the temporal prior to the candidate posterior ρ. Parameter λ > 0 governs the trade-off between the two terms. Depending on the choice of λ > 0 and the penalty above, our procedure reaches automatically the desire trade-off between fitting the data and penalty in terms of domain knowledge. It is important to note that minimization (5) is equivalent to compute the Legendre-Fenchel transformation of D(•, ρt ) at each step t ≥ 1, and leads to different kind of posterior distribution. In this paper, we investigate two divergences:

• Bregman divergences D(ρ, π) = B Φ (ρ, π) (see Section 2.1), where Φ governs the explicit form of the penalty as well as the sequence of distributions {ρ t , t = 1 . . . , T }, • Optimal transport D(ρ, π) = W α (ρ, π) (see Section 2.2), where the introduction of a cost function C(•, •) : G × G lead to more flexibility.

Recall that in the PAC-Bayesian literature cited above, the proposed sequential procedure based on minimization (5) uses the classical Kullback-Leibler divergence where D(ρ, π) = K(ρ, π). It leads to the vanilla Gibbs posterior (3) since in this case the unique solution of (5) can be written explicitly as follows:

ρt+1 (dg) = 1 Z t exp(-h t (g))dρ t (g) = • • • = 1 Z exp - t u=1 h t (g) dπ(g),
where ρ1 = π is the prior distribution. Finally, the main results of the paper occur under an assumption on the same flavour as [START_REF] Audibert | Fast learning rates in statistical inference through aggregation[END_REF]. It can be generalized in our context as follows:

Assumption A(Π, δ λ ) ∀π ∈ P(G), ∃Π(π) ∈ P(G) : ∀z ∈ Z:

E g ∼Π(π) (g , z) ≤ 1 λ E g ∼Π(π) min ρ∈P(G) E g∼ρ [λ( (g, z)) + δ λ (z, g, g )] + D(ρ, π) .
Below we show particular cases when A(Π, δ λ ) holds for both Bregman divergences and Optimal Transport leading to regret bounds for weighted averages built sequentially following Algorithm 1 below.

Algorithm 1 General Algorithm init. λ > 0, t = 1, π ∈ P(G) a prior distribution. D a divergence such that A(Π, δ λ ) holds. Let ρ1 = Π • π.
repeat Predict z t according to ĝt ∼ ρt . Observe z t and compute h t (g) = (z t , g) + δ λ (z t , g, ĝt ) for all g ∈ G.

return ρt+1 = Π • ρt+1 where Π is defined in A(Π, δ λ ) and ρt+1 is the solution of the general optimisation problem:

min ρ∈P(G) {Eg∼ρ ( (g, z t ) + δ λ (z t , g, ĝt )) + D(ρ, ρt )} t = t + 1 until t = T + 1

PAC-Bayesian Inequalities

In this section we propose to state the main results of the paper. In the sequel, we consider a measurable space (G, Ω) endowed with a σ-finite measure ν, where G is a set of decisions. We denote by P(G) := {ρ : G → R + : ρ(g)ν(dg) = 1} the set of probability measure on G. The main objective of PAC-Bayesian theory is to propose data-dependent posterior distribution P(G) with some theoretical guarantees. In Theorem 2.2, we control the expected cumulative loss of Algorithm 2, where Bregman divergences are proposed as regularizers. It generalizes the classical setting based on the usual Kullback-Leibler divergence. In Theorem 2.4, we go one step further and propose to introduce optimal transport as a promising alternative to measure the divergences to the prior. It leads to a control of the expected cumulative loss of Algorithm 3 where the introduction of a generic cost function allows to launch more generic regularizers and regret bounds in Corollary 2.5 and Corollary 2.6.

Bregman divergences

Given a strictly convex function Φ : P(G) → R, twice-continuously Fréchet-differentiable on relint p P(G), the relative interior of P(G) with respect to L p (ν), we define the functional Bregman divergence between two probabilities on P(G) as follows:

B Φ (ρ, µ) := Φ(ρ) -Φ(µ) -∇Φ(µ), ρ -µ , (6)
where ∇Φ(µ) stands for the Fréchet derivative of Φ at point µ. Equation ( 6) generalizes the standard vector Bregman divergence

B Φ (u, v) = Φ(u) -Φ(v) -∇Φ(v) T (u -v) for u, v ∈ R p where ∇Φ(v) is the standard gradient of Φ at point v.
Morever, as a particular case, we also introduce the class of pointwise Bregman divergences introduced by Csiszár in [START_REF] Csiszár | Generalized projections for non-negative functions[END_REF] as:

B s (ρ, µ) = G s(ρ(g)) -s(µ(g)) -s (µ(g))(ρ(g) -µ(g))ν(dg), (7)
where s : R + → R is constrained to be differentiable and strictly convex and the limit lim x→0 s(x) and lim x→0 s (x) must exist. By definition, B s is non-negative and satisfies main properties of classical Bregman divergence such as convexity, linearity, and generalized Pythagorean theorem (see for instance [START_REF] Béla A Frigyik | Functional bregman divergence and bayesian estimation of distributions[END_REF] for a proof). An important fact with this pointwise Bregman divergence is the existence of an equivalent functional Φ : P(G) → R and a functional Bregman divergence for any pointwise Bregman divergence if the measure ν is finite. However, the reverse is not true. Different function s in pointwise Bregman divergences [START_REF] Audibert | Fast learning rates in statistical inference through aggregation[END_REF] leads to different Bregman divergences. For instance, let s

(x) = x log x. Then B s (ρ, µ) = K(ρ, µ) where K(•, •) is the Kullback-Leibler divergence. Moreover, if s(x) = x 2 , then B s (ρ, µ) = ρ -µ 2,ν whereas if s(x) = -log x we find the Itakura-Saito distance.
The following lemma is useful to state the main theoretical result.

Lemma 2.1. Let π ∈ P(G) where G is finite. For some function h : G → R + , let us consider the minimization problem:

min ρ∈P(G) E g∼ρ [h(g)] + B(ρ, π) , (8)
where B ∈ {B Φ , B s } is a Bregman divergence according to definition (6) or (7).

• If B = B Φ for Φ : P(G) → R a strictly convex and continuously differentiable function, and h(•) is convex and continuously differentiable, the minimization problem (8) admits an unique solution ρh,π such that:

ρh,π (g) = max 0, ((∇ g Φ) -1 ∇ g Φ(π(g)) -h(g) + c h,π ) , ∀g ∈ G,
where c h,π > 0 is uniquely defined such that g∈G ρh,π (g) = 1. • More generally if a minimizer ρh,π of (8) exists, we have:

ρh,π (g) = max 0, ((∇ g Φ) -1 ∇ g Φ(π(g)) -h(g) + c h,π ) , ∀g ∈ G,
for some constant c h,π > 0 such that g∈G ρh,π (g) = 1.

• If B = B s for some differentiable and strictly convex s : R + → R such that the limit lim x→0 s(x) as well as lim x→0 s (x) must exist and lim x→0 s (x) = -∞, the minimization problem (8) admits an unique solution

ρh,π (g) = (s ) -1 (s (π(g)) -h(g) + c h,π ),
where c h,π > 0 is uniquely defined such that g∈G ρh,π (g) = 1.

Moreover, for any sequence (h t ) T t=1 and prior distribution ρ1 ∈ P(G), under the previous assumptions, we have:

ρT +1 = ρ T t=1 ht,ρ 1 , ( 9
)
where ρT +1 is the solution of (8) with h = h T and π = ρT .

The proof is postponed to Section 3.

Remark 1. This lemma is useful to prove the PAC-Bayesian inequality stated in Theorem 2.2 for Algorithm 2. It generalizes the convex duality formula stated originally in [START_REF] Catoni | Statistical learning theory and stochastic optimization[END_REF] which corresponds in Lemma 2.1 to the particular case B = B s for s(x) = x log x. In this case, we deal with the Gibbs measure ρh,π (g) = exp{log π(g)

+ 1 -h(g) + c h,π -1} = 1 Z exp{-h(g)}π(g).
Remark 2. The last statement (9) is useful in the proof of Theorem 2.2 to extend the cancellation argument originally stated in [START_REF] Andrew R Barron | Are bayes rules consistent in information?[END_REF] in the classical Kullback-Leibler case.

Remark 3. Lemma 2.1 is restricted to a finite set of weak learners G for simplicity. Recent extensions of the KKT conditions to the infinite dimensional case (see [START_REF] Park | Wireless network intelligence at the edge[END_REF]) can be used in order to consider uncountable set G but it is out of the scope of the present paper.

Previous Lemma is useful to control the expected regret of Algorithm 2 as follows.

Theorem 2.2. Let λ > 0 and (Π, δ λ ) defined below such that A(Π, δ λ ) holds. Consider a sequence of distribution (ρ t ) T t=1 based on Algorithm 2, where B ∈ {B Φ , B s } and (h t ) T t=1 satisfy assumption of Lemma 2.1. Then for any deterministic sequence {z t , t = 1, . . . T }, for any prior π ∈ P(G), we have:

T t=1 E ĝt∼ρt (ĝ t , z t ) ≤ min ρ∈P(G) E g∼ρ T t=1 ¯ (g, z t ) + B(ρ, π) λ ,
where λ ¯ (g, z) := λ (g, z) + E (ĝ 1 ,...,ĝt) δ λ (z t , g, ĝt ).

Sketch of proof.

Since A(Π, δ λ ) holds, we have for any π ∈ P(G), for any z ∈ Z:

E g ∼Π(π) (g , z) ≤ 1 λ E g ∼Π(π) min ρ∈P(G) E g∼ρ λ (g, z) + δ λ (z, g, g ) + B(ρ, π) . (10)
We first apply [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF]

for t = 1, . . . , T z = z t , π = ρt := ρh t-1 ,ρ t-1 in minimization (8) for h t (g) = λ( (z t , g)) + δ λ (z t , g, ĝt )
, with h 0 ≡ 0 and ρ0 correspond to the prior π. Then, summing accross iterations yields:

T t=1 E (ĝ 1 ,...,ĝt) (z t , g ) ≤ 1 λ T t=1 E g ∼ρt E g∼ρ t+1 h t (g) + B Φ (ρ t+1 , ρt ) = 1 λ E (ĝ 1 ,...,ĝ T ) T t=1 E g∼ρ t+1 h t (g) + Φ(ρ t+1 ) -Φ(ρ t ) -∇Φ(ρ t )(ρ t+1 -ρt ) = 1 λ E (ĝ 1 ,...,ĝ T ) T t=1 E g∼ρ t+1 h t (g) + Φ(ρ T +1 ) -Φ(π) - T t=1 ∇Φ(ρ t )(ρ t+1 -ρt ) .
Moreover, notice that by Lemma 3.1 (see Section 3), we have under the assumptions of Lemma 2.1:

T t=1 ∇Φ(ρ t )(ρ t+1 -ρt ) = ∇Φ(π)(ρ T +1 -π) -E g∼ρ T +1 T -1 t=1 h t (g) + T -1 t=1 E g∼ρ t+1 h t (g).
Then, gathering with the previous computations, we arrive at:

T t=1 E g ∼ρt (z t , g ) ≤ 1 λ E (ĝ 1 ,...,ĝ T ) E g∼ρ T +1 T t=1 h t (g) + Φ(ρ T +1 ) -Φ(π) -∇Φ(π)(ρ T +1 -π) = 1 λ E (ĝ 1 ,...,ĝ T ) E g∼ρ T +1 T t=1 h t (g) + B Φ (ρ T +1 , π) = 1 λ E (ĝ 1 ,...,ĝ T ) min ρ∈P(G) E g∼ρ T t=1 h t (g) + B Φ (ρ, π)
where we use the last statement of Lemma 2.1 for the last equality.

Remark 4. Theorem 2.2 controls the expected cumulative loss of Algorithm 2 in the online learning scenario presented in Section 1. Similar results can be stated in the i.i.d. case to get a control of the expected risk of a slightly modified version of Algorithm 2 by using a mirror averaging (see [START_REF] Arnak S Dalalyan | Mirror averaging with sparsity priors[END_REF] or [START_REF] Audibert | Fast learning rates in statistical inference through aggregation[END_REF]).

Remark 5. Theorem 2.2 generalizes the standard PAC-Bayesian bounds with Kullback-Leibler divergences to Bregman divergences. Indeed, in Theorem 2.2, if Φ involves a Kullback-Leibler divergence, we get a Gibbs measure in Algorithm 2 and find the existing bounds stated in [START_REF] Audibert | Fast learning rates in statistical inference through aggregation[END_REF].

Remark 6. The introduction of alternatives to the Kullback-Leibler divergence in PAC-Bayesian theory has been studied in the literature. [START_REF] Alquier | Simpler pac-bayesian bounds for hostile data[END_REF] studies Φ-divergence in a probabilistic context, whereas [START_REF] Li | Rényi divergence variational inference[END_REF] uses Renyi divergence. Moreover [START_REF] Knoblauch | Generalized variational inference: Three arguments for deriving new posteriors[END_REF] propose new posteriors in a Bayesians setting for variational inference for maximum likelihood estimators. Recently [START_REF] Alquier | Non-exponentially weighted aggregation: regret bounds for unbounded loss functions[END_REF] also states regret bounds for unbounded losses thanks to the introduction of a Φ-divergence.

Remark 7. Assumption A(Π, δ λ ) is necessary to conduct the proof. It can be traced back to [START_REF] Juditsky | Learning by mirror averaging[END_REF]. It is wellknown that this assumption is satisfied for any loss function in the Kullback-Leibler case for a particular quadratic function δ λ (see [START_REF] Audibert | Fast learning rates in statistical inference through aggregation[END_REF]). In the sequel, we prove this assumption in the Optimal Transport case to lead to a new kind of procedure where exponential averages are replaced by optimal transport optimization.

Remark 8. Theorem 2.2 is the main ingredient to derive the same kind of result for the optimal transport divergence, as well as regret bound in Section 2.2.

Algorithm 2 Bregman Algorithm init.λ > 0, t = 1, π ∈ P(G) a prior distribution. B Φ a Bregman divergence. Suppose A(Π, δ λ ) holds. Let ρ1 = Π • π.
repeat Predict z t with ĝt ∼ ρt . Observe z t and compute h t (g) = (g, z t ) + δ λ (z t , g, ĝt ) for all g ∈ G.

return ρt+1 = Π • ρt+1 where ρt+1 (g) = max 0, (∇gΦ) -1 ∇gΦ(ρ t (g)) -h t (g) + c h t , ρt for all g ∈ G.

t = t + 1 until t = T + 1

Optimal Transport

Given two probability measure ρ, π ∈ P(G), the Kantorovitch formulation of optimal transport between ρ and π is given by:

W C (ρ, π) := min Λ∈∆(ρ,π) G×G C(g, g )dΛ(g, g ), (11)
where ∆(ρ, π) = {Λ ∈ P(G × G) : Λ 1 = ρ and Λ 2 = π} and Λ 1 (resp. Λ 2 ) stands for the first (resp. second) marginal of Λ. An optimizer of ( 11) is called a transportation plan and quantifies how mass is moved from π to ρ whereas the cost function C(•, •) : G × G → R measure the cost of mooving a unit mass from g to g.

For an mathematical introduction of optimal transport, we refer to the monograph [START_REF] Villani | Optimal transport: old and new[END_REF].

Optimal transport has recently inspired the machine learning community to get a variety of divergences between probability distributions (see the monograph of [START_REF] Peyré | Computational optimal transport[END_REF]). It rises to several applications where comparisons of complex and high dimensional objects are needed : time series (see for instance [START_REF] Cuturi | A kernel for time series based on global alignments[END_REF][START_REF] Muskulus | Wasserstein distances in the analysis of time series and dynamical systems[END_REF]), images (see [START_REF] Courty | Joint distribution optimal transportation for domain adaptation[END_REF][START_REF] Salimans | Improving GANs using optimal transport[END_REF]) or neuro-images ( [START_REF] Gramfort | Fast optimal transport averaging of neuroimaging data[END_REF][START_REF] Janati | Multisubject meg/eeg source imaging with sparse multi-task regression[END_REF]). Moreover in these machine learning applications, some form of regularization has been proposed to avoid the curse of dimensionality as well as to build scalable versions of the original optimization problem [START_REF] Bühlmann | Statistics for high-dimensional data[END_REF] (see [START_REF] Cuturi | Sinkhorn distances: Lightspeed computation of optimal transport[END_REF]). For that purpose, entropy regularization makes the optimal transport problem more tractable and eliminates a number of analytic and computational difficulties. That is, we can consider a perturbation of the minimization problem [START_REF] Bühlmann | Statistics for high-dimensional data[END_REF] given by

W α (ρ, π) := min Λ∈∆(ρ,π) G×G C(g, g )dΛ(g, g ) + α(H(ρ) + H(π) -H(Λ)) , (12)
for some α > 0, where H is the Shannon entropy. Note that the quantity H(ρ) + H(π) -H(Λ) ≥ 0. Moreover, since W α (•, π) is strictly convex for any distribution π ∈ P(G), we use divergence [START_REF] Chee | Sparsity regret bounds for xnor-nets++[END_REF] in the rest of the paper.

min ρ∈P E g∼ρ [h(g)] + W α (ρ, π) . ( 13
)
Then we have:

min ρ∈P E g∼ρ [h(g)] + W α (ρ, π) = αH(π) -π, v ,
where v : G → R + is the KKT multiplier and satisfies:

v(g ) = -α log g∈G M α (g, g ) exp h(g) α , ∀g ∈ G,
for M α the inverse of the kernel matrix

K α = exp - C(g,g ) α g,g ∈G .
Then, for any λ > 0, A(Π, δ λ ) holds for:

δ λ (z, g, g ) = λ 2 2α ( (z, g) -(z, g )) 2 + α log A(π) Π(π)(g) = A(π)E g ∼π exp - C(g,g ) α , ∀g ∈ G, (14)
where A(π) is the normalizing constant.

Remark 9. The first statement is useful to prove [START_REF] Juditsky | Learning by mirror averaging[END_REF]. It uses the KKT conditions involved in the minimization problem [START_REF] Andrew R Barron | Are bayes rules consistent in information?[END_REF]. As before, the restriction to a finite set G only appears since we use the classical finite dimensional Lagrange theory. Extensions to infinite and uncountable set of candidates G is possible using recent extensions of the KKT conditions to the infinite dimensional case (see [START_REF] Park | Wireless network intelligence at the edge[END_REF]).

Remark 10. The second statement ensures the existence of a functional δ λ (z, •, •) and an operator Π(•) such that assumption A(Π, δ λ ) holds. As far as we know, this is the first time this assumption is used with non-trivial transformation Π(•) and Optimal Transport divergences instead of classical Kullback-Leibler divergence and duality. Operator Π depends on the cost function C(•, •) chosen in the optimal transport divergence and acts as a regularizer based on this cost.

This lemma is useful to prove the PAC-Bayesian bound for Algorithm 3.

Theorem 2.4. Assume G is finite. Let λ > 0. Consider a sequence of distribution (ρ t ) T t=1 based on Algorithm 3. Then for any deterministic sequence {z 1 , . . . , z T }, for any prior π ∈ P(G), we have:

T t=1 E ĝt∼ρt (ĝ t , z t ) ≤ min ρ∈P(G) E g∼ρ T t=1 ¯ (g, z t ) + W α (ρ, π) λ + ∆ T,λ (B Φα , W α ) ,
where ¯ (g, z) := (g, z)+ λ 2α E (ĝ 1 ,...,ĝt) ( (g, z) -(ĝ t , z)) 2 +α log A(π) and the extra-term ∆ T (B Φα , W α ) is defined in Section 3.

Remark 11. The proof uses Theorem 2.2 with a particular function Φ α : ρ → W α (ρ, ν) for some ν ∈ P(G) and allows us to extend the previous PAC-Bayesian bound to entropy regularized optimal transportation (see Section 3 for a detailled proof).

h t (g) = (g, z t ) + λ 2α ( (g, z t ) -(ĝ t , z t )) 2 + α log A(ρ t ), for all g ∈ G,
where A(ρ t ) is defined in Lemma 2.3. return ρt+1 = Π • ρt+1 where Π is defined in Lemma 2.3 and ρt+1 is the solution of the minimization problem in Lemma 2.3 with h = h t .

t = t + 1 until t = T

Generic regret bounds

We are now on time to apply Theorem 2.4 in the following toy generic example. Let us consider a finite set of learning machines G = {g 1 , . . . , , g p }, where p ≥ 1 is the number of learners. Suppose we have at hand a prior knowledge on these learning machines, in terms of generalization power, as well as another generic criterion to minimize (such as for instance energy consumption or carbon footprint, see [START_REF] Chee | Sparsity regret bounds for xnor-nets++[END_REF] and the references therein). We denote by {(Err 1 , Crit 1 ), . . . , (Err p , Crit p )} these sequences of criteria, where g i has generalization error estimate Err i and score Crit i for the generic criterion. We consider in the sequel two different scenarii corresponding to Corollary 2.5 and Corollary 2.6. In the first scenario, we suppose the simplest multiple-criteria decision-making problem, where for any η > 0, there exists an unique optimal decision g η = g i η ∈ G such that:

i η = arg min g∈G (Err i + ηCrit i ) ,
where η > 0 governs the trade-off between both criteria. Large value of η > 0 corresponds for instance to a small energy budget whereas η = 0 corresponds to a classical machine learning problem. With this in mind, consider a new task based on a deterministic sample {z 1 , . . . , z T } and a loss function (g, z). We want to draw a distribution, or mixture, on the finite set G able to trades off dynamically the loss over the new set of observations, and the generic criterion. For that purpose, we start from g η , the best compromise at hand and adapts sequentially the mixture thanks on Algorithm 3 as follows. At each round t ≥ 1, we choose a new distribution ρt+1 ∈ P(G) that minimizes the expected loss on new observation z t and the transport from ρt , where the optimal transport is based on a cost function depending on the sequence Crit, such as for instance C(g i , g j ) := Crit i -Crit j . We hence have the following result based on a direct application of Theorem 2.4: Corollary 2.5. Let π = δ g η the Dirac measure on g η and consider Algorithm 3 with C(g i , g j ) := C(Crit i , Crit j ) for any i, j = 1, . . . p in the optimal transport divergence (11). Then we have, for any deterministic sequence {z 1 , . . . , z T }:

T t=1 E ĝt∼ρt (ĝ t , z t ) ≤ min g∈G T t=1 ¯ (g, z t ) + C(g, g i ) λ + ∆ T ,
where ¯ and ∆ T > 0 are defined in Theorem 2.4 and λ > 0.

The proof is straightforward using Theorem 2.4 with Dirac prior δ g η . However, in practice, the existence and uniqueness of g η is rarely satisfied due to the unstability of the problem. Indeed, the generalization power, as well as the generic criterion, could be considered as stochastic values depending on unknown parameters such as the variability of the problem, the considered hardware, or some other practices. As a result, it could be more realistic to consider a prior π b based on a weighted average of candidate learners {g 1 , . . . , g p }. Moreover, if we have at hand a budget b > 0, we can choose π b as a solution of the following optimization:

min ρ E g∼ρ Err(g) s.t. E g∼ρ Crit(g) ≤ b,
where Err(g) and Crit(g) are respectively estimates of the true but untractable generalization power and, for instance, electric consumption of learner g ∈ G. In this case, strarting from π b for some b > 0, we have the following result:

Corollary 2.6. Let π = π b for some b > 0 in Algorithm 3 and C(g i , g j ) := C(Crit i , Crit j ) for any i, j = 1, . . . p in the optimal transport divergence (11). Then we have for the sequence of distribution {ρ t , t = 1 . . . , T } based on Algorithm 3:

T t=1 E ĝt∼ρt (ĝ t , z t ) ≤ inf i=1,...,p T t=1 ¯ (g, z t ) + E g ∼π b C(g i , g ) λ + ∆ T ,
where ¯ and ∆ T > 0 are defined in Theorem 2.4.

The proof is also straightforward using Theorem 2.4 with prior π b .

Proofs

Proof of Lemma 2.1

We start with the proof of Lemma 2.1. Since G is finite, the solution can be described directly by the Karush-Kuhn-Tucker (KKT) theory (see [START_REF] Cristianini | An introduction to support vector machines and other kernel-based learning methods. repr. Introduction to Support Vector Machines and other Kernel-Based Learning Methods[END_REF]). We first formally write the optimization problem as:

   min ρ F h,π (ρ) := E g∼ρ [h(g)] + B Φ (ρ, π) s.t. ρ(g) ≥ 0, ∀g ∈ G g∈G ρ(g) -1 = 0
For the first statement, since Φ and h are convex and continuously differentiable, F h,π (•) is convex and continuously differentiable and by the KKT conditions involved in the strong duality theorem, we first have for ρ := ρh,π minimizer of F h,π :

h(g) + ∇ g Φ(ρ(g)) -∇ g Φ(π(g)) = µ(g) -λ, ∀g ∈ G,
where µ : G → R + and λ ≥ 0 are KKT multipliers. Moreover, the complementary slackness condition (see [START_REF] Cristianini | An introduction to support vector machines and other kernel-based learning methods. repr. Introduction to Support Vector Machines and other Kernel-Based Learning Methods[END_REF], Theorem 5.21) implies that if ρ(g) = 0, then µ(g) = 0. That is, if ρ(g) = 0, then

∇ g Φ(ρ(g)) = ∇ g Φ(π(g)) -h(g) -λ (15)
while if ρ(g) = 0, then

∇ g Φ(0) = ∇ g Φ(ρ(g)) = ∇ g Φ(π(g)) -h(g) -λ + µ(g) ≥ ∇ g Φ(π(g)) -h(g) -λ.
Combining the above conditions, there is some constant c h,π such that for every g ∈ G:

∇ g Φ(ρ(g)) = max{a g , ∇ g Φ(π(g)) -h(g) + c h,π },
where a g = inf r∈(0,1) ∇ g Φ(r). In particular, for every g ∈ G,

ρ(g) = max 0, (∇ g Φ) -1 ∇ g Φ(π(g)) -h(g) + c h,π
where c h,π satisfies the following constraint:

g∈G ρ(g) = g∈G max{0, min{1, (∇ g Φ) -1 ∇ g Φ(π(g)) -h(g) + c h,π }} = 1.
Moreover, by strict convexity of Φ, it is straightforward to see that c h,π is unique.

For the second statement, we suppose the existence of a minimizer. Then, by KKT conditions, (15) holds. Moreover, the uniqueness of the minimizer follows for the dual convexity formula. Indeed, consider another distribution ρ and define the family of convex combinations ρ = (1

-)ρ + ρ for ∈ [0, 1].
Then, consider the first variation of ρ → B Φ (ρ, π):

d d E ρ h + B Φ (ρ , π) =0 = d d Φ(ρ ) - d d (∇Φ(π) -h)(ρ -π) =0 = ∇Φ(ρ )(ρ -ρ) -(∇Φ(π) -h)(ρ -ρ) =0 = ∇Φ(ρ)(ρ -ρ) -(∇Φ(π) -h)(ρ -ρ) = (∇Φ(π) -h + c1)(ρ -ρ) -(∇Φ(π) -h)(ρ -ρ) = 0.
Then, consider the second variation

d 2 d 2 E ρ h + B Φ (ρ , π) =0 = ∇ 2 Φ(ρ )(ρ -ρ) 2 =0 = ∇ 2 Φ(ρ)(ρ -ρ) 2 > 0.
This shows that ρ is indeed a local minimizer. Moreover, the global convexity of the Bregman divergence in the first argument yields to the uniqueness of the global minimizer.

For the third statement, we provide a pointwise Bregman divergence as in [START_REF] Audibert | Fast learning rates in statistical inference through aggregation[END_REF], where the measure ν is assumed to be finite. Moreover, suppose that lim x→0 s (x) → -∞.

As noted in the above remark, this is a special case of the general Bregman divergence. Naturally, B s = B Φ , where Φ(p) = s(p(x))ν(dx) and ∇Φ(p)(q) = s (p(x))q(x) ν(dx). Recall, as in the discrete case, that under the assumptions, the monotonicity of s implies that it is invertible on R. It follows that the inverse problem in [START_REF] Csiszár | Generalized projections for non-negative functions[END_REF] has solution ρ(g) = (s ) -1 (s (π(g)) -h(g) + c). Indeed, the fact that there is a unique c such that ρ is a distribution follows from the strict convexity of s and

d dc (s ) -1 (s (π(g)) -h(g) + c) ν(dg) = 1 s (ρ(g)) ν(dg) > 0.
Then, we use the intermediate value theorem with

(s ) -1 (s (π(g)) -h(g) + M ) ν(dg) ≥ (s ) -1 (s (π(g)) ν(dg) = 1 and (s ) -1 (s (π(g)) -h(g) + m) ν(dg) ≤ (s ) -1 (s (π(g)) ν(dg) = 1,
where M = sup g h(g) and m = inf g h(g).

For the last statement, considering for concision a pointwise Bregman divergence as above, we have coarselly:

ρT +1 (g) := (s ) -1 (s(ρ T (g)) -h T (g) + c T ) = (s ) -1 (s(ρ T -1 (g)) -h T -1 (g) + c T -1 -h T (g) + c T ) . . . = (s ) -1 (s(ρ 1 (g)) - T t=1 h t (g) + c).

Proof of Theorem 2.2

The proof of Lemma 2.2 is based on the following lemma.

Lemma 3.1. Let (ρ t ) T +1
t=1 the sequence of distribution defined in the proof of Theorem 2.2. Then under the assumptions of Lemma 2.1:

T t=1 ∇Φ(ρ t )(ρ t+1 -ρt ) = ∇Φ(π)(ρ T +1 -π) -E g∼ρ T +1 T -1 t=1 h t (g) + T -1 t=1 E g∼ρ t+1 h t (g).
Proof. From Lemma 2.1, since G is finite and using KKT conditions, [START_REF] Csiszár | Generalized projections for non-negative functions[END_REF] holds. Then by definition of the sequence (ρ t ) T +1 t=1 , we have for any t = 1, . . . , T , and any ρ, ρ ∈ P(G):

∇Φ(ρ t )(ρ -ρ ) = ∇Φ(ρ t-1 ) -h t-1 + c ht,ρ t-1 (ρ -ρ ) = ∇Φ(ρ t-1 )(ρ -ρ ) - g∈G h t-1 (g) ρ(g) -ρ (g) ,
where ρ0 = ρ1 . Then, applying extensively this equality and telescoping terms, we hence have:

T t=1 ∇Φ(ρ t )(ρ t+1 -ρt ) = T -1 t=1 ∇Φ(ρ t )(ρ t+1 -ρt ) + ∇Φ(ρ T -1 )(ρ T +1 -ρT ) - g∈G h T -1 (g) (ρ T +1 (g) -ρT (g)) = T -2 t=1 ∇Φ(ρ t )(ρ t+1 -ρt ) + ∇Φ(ρ T -1 )(ρ T +1 -ρT -1 ) - g∈G h T -1 (g) (ρ T +1 (g) -ρT (g)) = T -2 t=1 ∇Φ(ρ t )(ρ t+1 -ρt ) + ∇Φ(ρ T -2 )(ρ T +1 -ρT -1 ) - T -1 t=T -2 g∈G h t (g) (ρ T +1 (g) -ρt+1 (g)) . . . = ∇Φ(π)(ρ T +1 -π) - T -1 t=1 g∈G h t (g) (ρ T +1 (g) -ρt+1 (g)) = ∇Φ(π)(ρ T +1 -π) -E g∼ρ T +1 T -1 t=1 h t (g) + T -1 t=1
E g∼ρ t+1 h t (g).

Proof of Lemma 2.3

We write the minimization problem of Lemma 2.3 with the embedded optimal transport problem to consider a single minimization problem over Λ ∈ ∆(π), the space of couplings whose right marginal is π.

     min g,g ∈G Λ(g, g )(C(g, g ) + h(g)) + α H(π) + g,g ∈G Λ(g, g )(log Λ(g, g ) -log g ∈G Λ(g, g )) s.t. g∈G Λ(g, g ) = π(g ) ∀g ∈ G Λ(g, g ) ≥ 0, ∀g, g ∈ G.
(16) Then, by the Karush-Kuhn-Tucker (KKT) conditions, there exist

u ∈ R G×G + , v ∈ R G + such that for every g, g ∈ G, C(g, g ) + h(g) -u(g, g ) + v(g ) + α   log Λ(g, g ) -log ḡ∈G Λ(g, ḡ)   = 0. (17)
Moreover, Λ(g, g ) • u(g, g ) = 0 for all g, g ∈ G, so either u(g, g ) or Λ(g, g ) is zero. Thus, when multiplying the constraint by Λ(g, g ), we can assume in general that u(g, g ) = 0. Multiplying by Λ(g, g ) and summing in both g and g yields:

F (h, π) -αH(π) = g,g Λ(g, g ) C(g, g ) + h(g) + α   g,g Λ(g, g ) log Λ(g, g ) - g g Λ(g, g ) log g Λ(g, g )   = - g,g ∈G Λ(g, g )v(g ) = -π, v .
Thus, the optimal value satisfies

F (h, π) = αH(π) -π, v .
We use the other constraints to solve for v explicitly. Denote ρ(g) = ḡ∈G Λ(g, ḡ). Exponentiating the KKT conditions yields:

Λ(g, g ) = ρ(g) exp - C(g, g ) + h(g) -u(g, g ) + v(g ) α .
Summing in g yields:

π(g ) = g∈G ρ(g) exp - C(g, g ) + h(g) -u(g, g ) + v(g ) α . (18)
On the other hand, we see that Λ(g, g ) = 0 if and only if ρ(g) = 0. Consequently, the equation holds in general with u(g, g ) = 0. For ρ(g) = 0, summing in g yields

1 = g ∈G exp - C(g, g ) + h(g) + v(g ) α .
Let v±α (g ) = e ±v(g )/α and ĥ±α (g) = e ±h(g)/α . Let Ĉ-α be the matrix with entries exp(-C(g, g )/α) and under the assumption that it is invertible, let B α be its inverse. Then, we rewrite the equation above in matrix form

ĥ+α = Ĉ-α v-α =⇒ v-α = B α ĥ+α . That is, v(g ) = -α log   g∈G B α (g, g )e h(g)/α   .
Finally, to prove the second statement, let λ > 0. Let ρ be the minimizer of (13) and let Π : P(G) → P(G) such that for any g ∈ G:

Π(π)(g) := A(π) -1 E g ∼π e -C(g,g )/α , where A(π) is the normalizing constant defined as:

A(π) = g∈G E g ∼π e -C(g,g )/α .
By equation [START_REF] Park | Wireless network intelligence at the edge[END_REF], we have:

π(g )v +α (g ) = g∈G ρ(g) exp - C(g, g ) + h(g) α .
Recall that

F (h, π) = αH(π) -π, v = -α π, log π + v α = π, -α log(πe v/α ) = π, -α log(πv +α ) = -αE g ∼π log   g∈G ρ(g) exp - C(g, g ) + h(g) α  
Then by Jensen's inequality, to show A(Π, δ λ ), it suffices to show:

E g ∼Π(π) E g ∼π g∈G ρ(g) exp - C(g, g ) + h(z, g, g ) α ≤ 1
Compute:

E g ∼Π(π) E g ∼π g∈G ρ(g) exp - C(g, g ) + h(z, g, g ) α = E g ∼Π(π) g∈G ρ(g)E g ∼π exp - C(g, g ) α exp - h(z, g, g ) α ≤ g∈G E g ∼π exp - C(g, g ) α E g ∼Π(π) exp - h(z, g, g ) α = A(π) E g,g ∼Π(π) exp - h(z, g, g ) α = A(π) E g∼ρ,g ∼Π(π) exp - λ( (g, z) -(g , z)) + δ λ (z, g, g ) α = E g,g ∼Π(π) exp - λ α ( (g, z) -(g , z)) - 1 2 λ α ( (g, z) -(g , z)) 2 ≤ 1.

Proof of Theorem 2.4

Let α > 0. First note that from Lemma 2.3, we have for any π ∈ P(G), for any z ∈ Z:

E g ∼Π(π) (g , z) ≤ 1 λ E g ∼Π(π) min ρ∈P(G) E g∼ρ λ (g, z) + δ λ (z, g, g ) + W α (ρ, π) , (19)
where Π and δ λ are defined in Lemma 2.3. Then applying [START_REF] Alquier | Simpler pac-bayesian bounds for hostile data[END_REF] for t = 1, . . . , T , with π = ρt minimizer of (13) in Lemma 2.3 for h t-1 = λ (z t-1 , g) + δ λ (z t-1 , g, ĝt-1 ) and h 0 ≡ 0 and summing accross iterations yields:

T t=1 E g ∼Π(ρt) (g , z t ) ≤ 1 λ T t=1 E g ∼Π(ρt) min ρ∈P(G) {E g∼ρ h t (g) + W α (ρ, ρt )}. (20)
The idea of the proof is to decompose the RHS in (20) by introducing a particular Bregman divergence, and to use Theorem 2.2 as a main ingredient. For that purpose, let π ∈ P(G) and consider the function Φ α : ρ → W α (ρ, π ) based on the regularized optimal transport [START_REF] Chee | Sparsity regret bounds for xnor-nets++[END_REF]. First, note that by the entropy regularization, Φ α is strictly convex and differentiable is its arguments for any α > 0. Then we can decompose the RHS in [START_REF] Li | Rényi divergence variational inference[END_REF] as follows:

T (W α (ρ t+1 , ρt ) -B Φα (ρ t+1 , ρt ) + B Φα (ν t+1 , ρt ) -B Φα (ν t+1 , νt )) .

Lemma 3.2. Let α > 0 and π ∈ P(G). Let Φ α : ρ → W α (ρ, π ). Then we have:

B Φα (ρ, π) = W α (ρ, π ) -W α (π, π ) + v, ρ -π ,
where v := v(ρ, π ) ∈ R G + is the KKT multiplier based on the optimization W α (ρ, π ) defined in [START_REF] Chee | Sparsity regret bounds for xnor-nets++[END_REF].

Proof First note that by the entropy regularization, Φ α is strictly convex and differentiable is its arguments for any α > 0. Then B Φα is well defined in [START_REF] Arnak S Dalalyan | Mirror averaging with sparsity priors[END_REF]. Moreover since G is finite, Φ α can be described directly by the Karush-Kuhn-Tucker (KKT) multipliers. We first formally write the optimization problem as:

        
min Λ g,g ∈G Λ(g, g )C(g, g ) + α H(π ) + g,g ∈G Λ(g, g ) log Λ(g, g ) -log ρ(g) s.t. Λ(g, g ) ≥ 0, ∀g, g ∈ G g ∈G Λ(g, g ) -ρ(g) = 0, ∀g ∈ G g∈G Λ(g, g ) -π (g ) = 0, ∀g ∈ G

By the KKT conditions and the strong duality theorem, there exist u ∈ R G×G + , v, v ∈ R G + such that for every g, g ∈ G:

C(g, g ) -u(g, g ) + v(g) + v (g ) + α log Λ (g, g ) -log ρ(g) = 0, where Λ is the solution of [START_REF] Knoblauch | Generalized variational inference: Three arguments for deriving new posteriors[END_REF]. Then, gathering with the same computations as in the proof of Lemma 2.3, we have:

W α (ρ, π ) = αH(π ) -ρ, v -π , v
By definition of the Bregman divergence [START_REF] Arnak S Dalalyan | Mirror averaging with sparsity priors[END_REF] and the choice of Φ α , we hence have:

B Φα (ρ, π) = W α (ρ, π ) -W α (π, π ) + v, ρ -π .

g∈{g 1 ,

 1

Lemma 2 . 3 .

 23 Assume G is finite. Let π ∈ P(G), α > 0 and C : G × G → R a cost function and consider the minimization problem:

Remark 12 .Algorithm 3

 123 Theorem 2.4 allows us to derive regret bounds for Algorithm 3. It gives more flexibility into the regularization thanks to the introduction of a particular cost function C in (12). Optimal transport PAC-Bayesian Algorithm init.λ, α > 0, t = 1, π ∈ P(G) a prior distribution. C a cost function in Wα. Let ρ1 = Π • π. repeat Observe z t and predict ĝt ∼ ρt . Compute:

  {E g∼ρ h t (g) + W α (ρ, ρ t )} {E g∼ρ h t (g) + B Φα (ρ, ρ t ) + t (ρ)}, where t (ρ) is defined as : By definition of the sequence {ρ t , t = 1, . . . , T }, we can now decompose the RHS as follows:{E g∼ρ h t (g) + B Φα (ρ, ρt ) + t (ρ)}We start with the control of Σ T (B Φα ). To use Theorem 2.2, we introduce the sequence {ν t , t = 1, . . . T } where νt+1 is the solution of the minimization[START_REF] Gerchinovitz | Sparsity regret bounds for individual sequences in online linear regression[END_REF] with couple (h, π) = (h t , νt ) and where ν1 = ρ1 corresponds to the prior π. Then we can write:{E g∼ρ h t (g) + B Φα (ρ, ρt )} ∼Π(ρt) E g∼ν t+1 h t (g) + B Φα (ν t+1 , νt ) + Φα (ν t+1 , ρt ) -B Φα (ν t+1 , νt )] ∼Π(ρt) E g∼ν t+1 h t (g) + B Φα (ν t+1 , νt ) +where δ t is defined by:δ t = B Φα (ν t+1 , ρt ) -B Φα (ν t+1 , νt ).Then, following the same lines as in the proof of Theorem 2.2, Lemma 3.1 allows us to write: ∼Π(ρt) h t (g) + B Φα (ρ, π) + where 1 (ρ) is defined above. Hence we get the result by choosing π in Lemma 3.2 in order to control the residual term:∆ T (B Φα , W α ) := 1 λ

				Σ T (B Φα ) ≤	1 λ	min ρ∈P(G)	E g∼ρ	T t=1	E g 1 λ	T t=1	δ t
		t=1	E g ∼Π(ρt) (z t , g ) ≤ ≤ 1 λ min ρ∈P(G) 1 λ	T t=1 E g∼ρ E g ∼Π(ρt) min ρ∈P(G) T t=1 ¯ (z t , g) + W α (ρ, π) -1 (ρ) +	1 λ	T t=1	δ t ,
									T	=	1 λ	T t=1	E g ∼Π(ρt) min ρ∈P(G)
									( t (ρ t+1 ) + δ t )
									t=1
						=	1 λ	T t=1
	T t=1	E g ∼Π(ρt) (z t , g ) =	1 λ	T t=1	E g ∼Π(ρ t ) min ρ∈P(G)
									≤	1 λ	T t=1	t (ρ t+1 )
									:= Σ T (B Φα ) +	1 λ	T t=1	t (ρ t+1 ).
	Σ T (B Φα ) =	1 λ	T t=1	E g ∼Π(ρt) min ρ∈P(G)
		≤ [B := 1 λ T t=1 T E g 1 λ t=1 1 λ T t=1 T E g 1 t=1 λ δ t ,

t (ρ) = W α (ρ, ρ t ) -B Φα (ρ, ρ t ). T t=1 E g ∼Π(ρt) min ρ∈P(G) {E g∼ρ h t (g) + B Φα (ρ, ρt )} + 1 λ