Conférence Nationale d'Intelligence Artificielle Année
2018

Sandra Bringay, Olivier Buffet, Alain Dutech, Jérôme Euzenat, Juliette Mattioli, Sylvie Ranwez, François Schwarzentruber, Vincent Thomas, Yves Demazeau, Dominique Longin

<figure><img src="image_1.png" /></figure>

To cite this version:

Sandra Bringay, Olivier Buffet, Alain Dutech, Jérôme Euzenat, Juliette Mattioli, et al. Conférence Nationale d'Intelligence Artificielle Année 2018. Association Française pour l'Intelligence Artificielle, 2018. hal-02189744

HAL Id: hal-02189744

https://hal.science/hal-02189744v1

Submitted on 19 Jul 2019

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
<figure><img src="image_3.png" /></figure>

Conférence Nationale
d'Intelligence Artificielle
Année 2018

Sections Spéciales

Sandra Bringay
Olivier Buffet
Alain Dutech
Jérôme Euzenat
Juliette Mattioli
Sylvie Ranwez
François Schwarzentruber
Vincent Thomas

Coordination AfIA

Yves Demazeau
Dominique Longin

<figure><img src="image_4.png" /></figure>

AfIA

Association française
pour l'intelligence artificielle
Conférence Nationale
d'Intelligence Artificielle
Année 2018
<figure><img src="image_5.png" /></figure>
# Actes CNIA 2018

## Conférence Nationale d'Intelligence Artificielle

Éditeurs : Président(e)s des CP de CNIA 2018
<figure><img src="image_6.png" /></figure>
Table des matières

<table><tr><td>Mot des Présidents.</td><td></td></tr><tr><td>Nancy au cœur de l'IA de demain</td><td>5</td></tr><tr><td>Comités.</td><td></td></tr><tr><td>Comités 2018 de programmation, de programme, et d'organisation</td><td>7</td></tr><tr><td>Partenaires.</td><td></td></tr><tr><td>Partenaires PFIA 2018</td><td>13</td></tr><tr><td>I. Badache, S. Fournier, A.-G. Chifu (IC).</td><td></td></tr><tr><td>Prédire l'intensité de contradiction dans les commentaires : faible, forte ou très forte?</td><td>15</td></tr><tr><td>G. Bono, J. Dibangoye, L. Matignon, F. Pereyron, O. Simonin (JFPDA).</td><td></td></tr><tr><td>Sur le gradient de la politique pour les systèmes multi-agents coopératifs</td><td>29</td></tr><tr><td>F. Chiaroni, M.-C. Rahal, F. Dufaux, N. Hueber (RJCIA).</td><td></td></tr><tr><td>Classification d'images en apprenant sur des échantillons positifs et non labélisés avec un réseau antagoniste génératif</td><td>41</td></tr><tr><td>C. Comparot, C. Trojahn, H. Arenas, N. Aussenac-Gilles (IC).</td><td></td></tr><tr><td>Ontologie pour l'intégration de données d'observation de la Terre et contextuelles basée sur les relations topologiques</td><td>49</td></tr><tr><td>T. Delacroix (CNIA).</td><td></td></tr><tr><td>Choisir un encodage CNF de contraintes de cardinalité performant pour SA</td><td>61</td></tr><tr><td>T. Deregnaucourt, C. Samir, A.-F. Yao (RJCIA).</td><td></td></tr><tr><td>Inférence bayésienne pour l'estimation de déformations larges par champs Gaussien : application au recalage d'images multi-modales</td><td>69</td></tr><tr><td>S. Despres (IC).</td><td></td></tr><tr><td>oogo : ontologie des outils utiles à la gestion d'ontologies</td><td>77</td></tr><tr><td>M.T. Dhouib, C. Faron-Zucker, A. Tettamanzi (APIA).</td><td></td></tr><tr><td>Categorization of B2B Service Offers : Lessons learnt from the Silex Use case</td><td>87</td></tr><tr><td>G. Gadek, A. Pauchet, S. Brunessaux, K. Khelif, B. Grilhères (APIA).</td><td></td></tr><tr><td>AI techniques to analyse a social network on text, user and group level : application on Galaxy2</td><td>95</td></tr><tr><td>A. Giboin (IC).</td><td></td></tr><tr><td>Étude de l'évolution du modèle de l'utilisateur des systèmes de construction collaborative d'ontologies</td><td>105</td></tr><tr><td>N. Gutowski, T. Amghar, O. Camp, F. Chhel (APIA).</td><td></td></tr><tr><td>Bandits-manchots contextuels : précision globale versus individuelle</td><td>119</td></tr><tr><td>G. Kassel (IC).</td><td></td></tr><tr><td>Une alternative à la distinction 'continuant' vs 'occurrent'</td><td>127</td></tr><tr><td>F. Koriche (JFPDA).</td><td></td></tr><tr><td>Sur la compilation de jeux de prédictions combinatoires</td><td>137</td></tr><tr><td>D. Lahoual, M. Fréjus (APIA).</td><td></td></tr><tr><td>Utilisation des systèmes d'interaction vocale dans l'habitat : quels retours d'expérience utilisateur et quels critères d'interaction à intégrer en conception?</td><td>145</td></tr></table>
<table>
  <tbody>
    <tr>
      <td>F. Maris, M. Valais, J. Vianey (JFPDA).<br/>Codage SMT dans un espace de plans (liens causaux) pour la planification temporelle en temps continu</td>
      <td>157</td>
    </tr>
    <tr>
      <td>J. Mattioli, P.-O. Robic, T. Reydellet (APIA).<br/>L'intelligence artificielle au service de la maintenance prévisionnelle</td>
      <td>163</td>
    </tr>
    <tr>
      <td>J.-C. Mensonides, S. Harispe, J. Montmain, V. Thireau (CNIA).<br/>Réseaux de neurones récurrents multi-tâches pour l'analyse automatique d'arguments</td>
      <td>167</td>
    </tr>
    <tr>
      <td>Y. Mercadier, J. Azé, S. Bringay, V. Clavier, E. Cuenca, C. Paganelli, P. Poncelet, A. Sallaberry (IC).<br/>#AIDS Analyse Information Dangers Sexualité : caractériser les discours à propos du VIH dans les forums de santé</td>
      <td>175</td>
    </tr>
    <tr>
      <td>V. Pozzoli, F. Ramond (APIA).<br/>Optimisation en temps réel de la gestion des convergences ferroviaires</td>
      <td>187</td>
    </tr>
    <tr>
      <td>J. Reynaud, Y. Toussaint, A. Napoli (CNIA).<br/>Trois approches pour classifier les données du web des données</td>
      <td>195</td>
    </tr>
    <tr>
      <td>E.A. Sidi Aly, M.L. Diakité, A. Giacometti, B. Markhoff, A. Soulet (CNIA).<br/>Découverte de cardinalité maximale contextuelle dans les bases de connaissances</td>
      <td>203</td>
    </tr>
  </tbody>
</table>
# Nancy, au cœur de l'Intelligence Artificielle de demain

## Armelle Brun et Davy Monticolo

Maîtres de Conférence Habilités à l'Université de Lorraine
Co-Présidents du comité d'organisation de la Plate-Forme IA 2018

## Yves Demazeau

Directeur de Recherche au CNRS
Président de l'Association Française pour l'Intelligence Artificielle

L'AFIA et l'Université de Lorraine organisent à Nancy du 02 au 06 juillet 2018 la onzième Plate-Forme Intelligence Artificielle (PFIA). Les précédentes éditions se sont tenues à Palaiseau (1999), Grenoble (2001), Laval (2003), Nice (2005), Grenoble (2007), Hammamet (2009), Chambéry (2011), Lille (2013), Rennes (2015) et Caen (2017).

La plate-forme IA constitue un point de rencontre unique pour la communauté IA permettant de rapprocher les différentes disciplines qui la composent et d'établir des passerelles entre elles. A cette intention, la plate-forme IA s'adresse à l'ensemble de la communauté francophone d'Intelligence Artificielle pour aborder des problématiques communes.

Pour son édition 2018, la plate-forme IA héberge les cinq conférences suivantes, ainsi que leurs ateliers associés :

**APIA** 4ème Conférence Nationale sur les Applications Pratiques de l'IA

**CNIA** 22ème Conférence Nationale d'Intelligence Artificielle

**IC** 29èmes Journées Francophones d'Ingénierie des Connaissances

**JFPDA** 13ème Journées Francophone Planification, Décision et Apprentissage

**RJCIA** 16ème Rencontres des Jeunes Chercheurs en Intelligence Artificielle

Mais aussi les autres événements :

**Education & IA** 1ère Journée IA pour l'Education (avec MEN/DNE)

**Ethique & IA** 3ème Journée Ethique et IA (avec INRIA/COERLE)

**France @ IJCAI** Présentation par leurs auteurs français d'articles acceptés à IJCAI 2018

**Robotique & IA** 3ème Journée Robotique et IA (avec CNRS/GdR Robotique)

**Santé & IA** 3ème Journée Santé et IA (avec AIM)

**TAL & IA** 4ème Journée Traitement Automatique des Langues et IA (avec ATALA)

Sept conférenciers ont également été invités pour des conférences plénières :

<table><tr><td>Nawal Benabbou</td><td>Prix de Thèse IA 2018</td><td>France</td></tr><tr><td>Daniele Calandriello</td><td>Prix de Thèse IA 2018</td><td>France</td></tr><tr><td>Aldo Gangemi</td><td>Université Paris Nord</td><td>France</td></tr><tr><td>Nicola Guarino</td><td>CNR Trento</td><td>Italie</td></tr><tr><td>Daniela Rus</td><td>MIT Boston</td><td>USA</td></tr><tr><td>Zhongzhi Shi</td><td>CAS Beijing</td><td>Chine</td></tr><tr><td>Moshe Vardi</td><td>Rice University</td><td>USA</td></tr></table>

L'ensemble des informations sur ces événements est disponible à partir du site de la Plate-Forme IA 2018 (http://pfia2018.loria.fr/) dont le contenu sera maintenu jusqu'à l'été 2022.

Nous remercions les présidents de comités de programme des conférences et journées hébergées, les membres de leurs comités de programme, les orateurs, les membres des comités de programmation et d'organisation, nos partenaires institutionnels et industriels, ainsi que tous les participants, pour leurs contributions précieuses à la réussite de cette plate-forme.
<figure><img src="image_7.png" /></figure>
# Comité de programmation

## Conseil d'Administration de l'Association Française pour l'Intelligence Artificielle

Président : Yves Demazeau

* Sandra Bringay

* Yves Demazeau

* Catherine Faron-Zucker

* Dominique Longin

* Frédéric Maris

* Engelbert Nguifo Mephu

# Comités de programme

## 4ème Conférence Applications Pratiques de l'Intelligence Artificielle (APIA)

Présidentes : Sandra Bringay LIRMM, (Université Paul-Valéry Montpellier 3)
Juliette Mattioli (Thales)

* Carole Adam,

* Florence Amardeilh,

* Ghislain Atemezing,

* Jérôme Azé,

* Alain Berger,

* Matthieu Boussard,

* Bertrand Braunschweig,

* Stéphan Brunessaux,

* Moez Bouchouicha,

* Nathalie Chaignaud,

* Caroline Chopinaud,

* Jan Ciger,

* Laurent Cosserat,

* Jean-Marc David,

* Philippe David,

* Nicolas Delaforge,

* Etienne de Sevin,

* Yves Demazeau,

* Christian de Sainte Marie,

* Sylvie Despres,

* Sébastien Destercke,

* Jean-Yves Donnart,

* Béatrice Fuchs,

* Christophe Guettier,

* Céline Hudelot,

LIG CNRS UMR 5217 - Université Grenoble-Alpes

créatrice d'entreprise en Ingénierie des Connaissances

Mondeca

LIRMM-UM-CNRS

Ardans

Craft AI

Inria Saclay

AIRBUS

Université du Sud Toulon-Var

LITIS - INSA Rouen Normandie

Craft AI

Reviatech SAS

Renault

Renault

SNCF

mnemotix

SANPSY - University of Bordeaux

CNRS - LIG

IBM

LIMICS - Université Paris 13

CNRS, UMR Heudiasyc

THALES

LIRIS, IAE - Université Lyon 3

Safran Electronique et Défense

École Centrale Paris
* Philippe Laborie,

* Christophe Labreuche,

* Arnaud Lallouet,

* Christine Largouët,

* Vincent Lemaire,

* Dominique Lenne,

* Domitile Lourdeaux,

* Sylvain Mahe,

* Philippe Mathieu,

* Nada Matta,

* Eunika Mercier-Laurent,

* Christophe Menichetti,

* Philippe Morignot,

* Selmin Nurcan,

* Jean-Marc Ogier,

* Benoit Ricard,

* Jean Rohmer,

* Dominique Romary,

* Catherine Tessier,

* Erwan Tranvouez,

* Brigitte Trousse,

* Amel Yessad,

IBM

Thales

Huawei

Irisa /Agrocampus Ouest

Orange

Heudiasyc - Université de Technologie de Compiègne

Heudiasyc - Université de Technologie de Compiègne

EDF Recherche et Développement

University of Lille 1

University of Technology of Troyes

CRESTIC- Université Reims Champagne Ardennes

IBM

SAFRAN

Université Paris 1 Panthéon - Sorbonne

L3i - University of La Rochelle

EDF R&D

De Vinci Research Center (DVRC)

ODΣFI

Onera

LSIS - Polytech'Marseille - Université d'Aix-Marseille

Université Côte d'Azur, INRIA Sophia Antipolis - Méditerranée

LIP 6 - Université Pierre et Marie Curie

## 21<sup>ème</sup> Conférence Nationale en Intelligence Artificielle

## 16<sup>ème</sup> Rencontre des Jeunes Chercheurs en Intelligence Artificielle (RJCIA)

Présidents CNIA : Jérôme Euzenat (INRIA & LIG, Grenoble)

RJCIA : François Schwarzentruber (ENS Rennes)

* Carole Adam

* Emmanuel Adam

* Audrey Baneyx

* Nicolas Béchet

* Isabelle Bichindaritz

* Meghyn Bienvenu

* Isabelle Bloch

* Olivier Boissier

* Grégory Bonnet

* Sylvain Bouveret

* Elena Cabrio

* François Charpillet

* Mohamed Chetouani

* Laurence Cholvy

* Rémy Courrier

* Bruno Cremilleux

* Jérôme David

* Tiago de Lima

* Cyril de Runz

* Nicolas Delestre

* Yves Demazeau

* Gaël Dias

* Catherine Faron Zucker

* Jérémy Fix

* Catherine Garbay

* Serge Garlatti

* Thomas Guyet

LIG, CNRS - UJF

Univ. Lille Nord de France

Médialab, Sciences Po

IRISA

State University of New York at Oswego

CNRS - Université de Montpellier - INRIA

ENST - CNRS LTCI

Lab. Hubert Curien, Mines Saint-Etienne, Institut Henri Fayol

Université de Caen Normandie

LIG, Grenoble INP - Université Grenoble Alpes

I3S, Université Côte d'Azur - CNRS - INRIA

LORIA, INRIA

ISIR

ONERA-Toulouse

LIM, Université de la Réunion

Université de Caen Normandie

LIG, Université Grenoble-Alpes - INRIA

Université d'Artois - CNRS

CRESTIC

LITIS, Université de Caen Normandie - INSA de Rouen

LIG, CNRS

Université de Caen Normandie

Université Nice Sophia Antipolis

SUPELEC

LIG, CNRS

ENST Bretagne

IRISA
<figure><img src="image_8.png" /></figure>

AfIA

Association française
pour l'Intelligence Artificielle

* Salima Hassas

* Abir Beatrice Karami

* Sébastien Konieczny

* Philippe Laborie

* Nicolas Lachiche

* Jean-Marie Lagniez

* Arnaud Lallouet

* Robin Lamarche-Perrin

* Philippe Lamarre

* Jérôme Lang

* Fabien Lauer

* Florence Le Ber

* Christophe Lecoutre

* Marie Lefevre

* Jean-Guy Mailly

* Pierre Marquis

* Philippe Mathieu

* Nicolas Maudet

* Engelbert Mephu Nguifo

* Fabien Michel

* Frédéric Migeon

* Davy Monticolo

* Maxime Morge

* Abdel-Illah Mouaddib

* Philippe Muller

* Amedeo Napoli

* Alexandre Niveau

* Antoine Nongaillard

* Wassila Ouerdane

* Odile Papini

* Alexandre Pauchet

* Damien Pellier

* Frédéric Pennerath

* Henri Prade

* Chedy Raïssi

* Sylvie Ranwez

* Regis Riveret

* Mathieu Roche

* Marie-Christine Rousset

* Catherine Roussey

* Nicolas Sabouret

* Thomas Schiex

* Karima Sedki

* Christine Solnon

* Isabelle Tellier

* Alexandre Termier

* Konstantin Todorov

* Charlotte Truchet

* Tim Van de Cruys

* Laurent Vercouter

* Srdjan Vesic

* Serena Villata

* Christel Vrain

Université Claude Bernard-Lyon 1

LIRIS, CNRS

CRIL, CNRS

IBM

Université de Strasbourg

CRIL

Huawei Technologies Ltd

Laboratoire d'Informatique de Paris 6

LIRIS

LAMSADE, CNRS – Université Paris-Dauphine

LORIA, Université de Lorraine

iCube, Strasbourg

CRIL, Université d'Artois

LIRIS, Université Lyon 1

LIPADE, Université Paris Descartes

CRIL, Université d'Artois – CNRS

Université de Lille

Université Pierre et Marie Curie

LIMOS, Université Clermont Auvergne

LIRMM, Université de Montpellier

IRIT, Toulouse

Université de Lorraine

Computer Science Laboratory of Lille

Université de Caen Normandie

IRIT, Toulouse University

LORIA, CNRS – Inria – Université de Lorraine

GREYC

Université de Lille

LGI, CentraleSupelec

LSIS, CNRS

LITIS, INSA Rouen – Normandy University

LIG

Supelec, Metz

IRIT, CNRS

INRIA

LGI2P, Ecole des mines d'Alès

CSIRO

TETIS, Cirad

Université Grenoble Alpes

Irstea

LIMSI, CNRS

INRA

CRIL, Université d'Artois

LIRIS, CNRS – INSA Lyon

Lattice

Université de Rennes 1

LIRMM

LINA, CNRS – Université de Nantes

IRIT, CNRS

LITIS, INSA de Rouen

IRIT, Toulouse

I3S, Université Côte d'Azur – CNRS – Inria

LIFO, Université d'Orléans
* Bruno Zanuttini GREYC, Université de Caen Normandie, CNRS, ENSICAEN

* Antoine Zimmermann École des Mines de Saint-Étienne

* Pierre Zweigenbaum LIMSI, CNRS – Université Paris-Saclay

## 29es Journées Francophones Ingénierie des Connaissances (IC)

Présidente : Sylvie Ranwez, LGI2P, IMT Mines Alès

* Marie-Hélène Abel HEUDIASYC, Université de Technologie de Compiègne

* Xavier Aimé LIMICS, Université Paris 13

* Yamine Ait Ameur IRIT, INP Toulouse

* Florence Amardeilh Créatrice d'entreprise en Ingénierie des Connaissances

* Bruno Bachimont COSTECH, Université de Technologie de Compiègne

* Jean-Paul Barthès HEUDIASYC, Université de Technologie de Compiègne

* Aurélien Bénel ICD, Université de Technologie de Troyes

* Nacéra Bennacer LRI, Centrale Supélec campus de Gif-sur-Yvette

* Pierre Bourhis LIFL, CNRS

* Bertrand Braunschweig Inria Saclay-Île-de-France

* Nathalie Bricon-Souf IRIT, Université Paul Sabatier Toulouse 3

* Sandra Bringay LIRMM, Université Paul-Valéry Montpellier 3

* Patrice Buche IATE, INRA Montpellier

* Davide Buscald LIPN, Université Paris 13

* Elena Cabri I3S, INRIA Sophia Antipolis - Méditerranée

* Sylvie Calabretto LIRIS, INSA de Lyon

* Gaoussou Camara Université Alioune Diop de Bambey

* Pierre-Antoine Champin LIRIS, Université Claude Bernard Lyon 1

* Jean-Pierre Chanet TSCF, Irstea de Clermont Ferrand

* Jean Charlet LIMICS, APHP INSERM Paris

* Olivier Corby Université Côte d'Azur, Inria

* Amélie Cordier Hoomano, Université de Lyon

* Mathieu D'Aquin Insight Centre for Data Analytics, NUI Galway, Ireland

* Jérôme David LIG, INRIA Grenoble

* Sylvie Despres LIMICS, Université Paris 13

* Rim Djedidi, LIMICS, Université Paris 13

* Jean-Pierre Evain EBU Suisse

* Gilles Falquet, CUI, Université de Genève

* Catherine Faron-Zucker I3S, Université Nice Sophia Antipolis

* Cécile Favre ERIC, Université Lumière Lyon 2

* Béatrice Fuchs LIRIS, IAE - université Lyon 3

* Frédéric Fürst MIS, Université de Picardie Jules Verne

* Jean-Gabriel Ganascia LIP6, Université Pierre et Marie Curie

* Serge Garlatti IMT Atlantique

* Alain Giboin I3S, INRIA Sophia Antipolis - Méditerranée

* Nathalie Guin LIRIS, Université Claude Bernard Lyon 1

* Ollivier Haemmerlé IRIT, Université Toulouse le Mirail

* Sébastien Harispe LGI2P, IMT Mines Alès

* Mounira Harzallah LS2N, Université de Nantes

* Nathalie Hernandez IRIT, Université Toulouse le Mirail

* Liliana Ibanescu MIA, INRA AgroParistech Paris

* Sébastien Iksal LIUM, IUT Le Mans

* Antoine Isaac Europeana & VU University Amsterdam

* Clement Jonquet LIRMM, Université de Montpellier

* Mouna Kamel IRIT, Université de Perpignan Via Domitia

* Gilles Kassel MIS, Université de Picardie Jules Verne

* Pascale Kuntz LS2N, Université de Nantes

* Florence Le Ber ICUBE, Université de Strasbourg / ENGEES
<figure><img src="image_9.png" /></figure>

AfIA

Association française
pour l'Intelligence Artificielle

* Michel Leclère

* Maxime Lefrançois

* Alain Léger

* Dominique Lenne

* Moussa Lo

* Cédric Lopez

* Nada Matta

* Pascal Molli

* Alexandre Monnin

* Isabelle Mougenot

* Fleur Mougin

* Amedeo Napoli

* Emmanuel Nauer

* Jérôme Nobécourt

* Nathalie Pernelle

* Yannick Prié

* Cédric Pruski

* Chantal Reynaud

* Catherine Roussey

* Fatiha Saïs

* Pascal Salembier

* Karim Sehaba

* Hassina Seridi-Bouchelaghem

* Andrea Tettamanzi

* Konstantin Todorov

* Francky Trichet

* Raphaël Troncy

* Serena Villata

* Amel Yessad

* Haïfa Zargayouna

* Pierre Zweigenbaum

LIRMM, Université de Montpellier

laboratoire Hubert Curien, IMT Mines Saint-Étienne

Orange Labs, France Telecom Rennes

HEUDIASYC, Université de Technologie de Compiègne

Université Gaston Berger de Saint Louis

Emvista, Montpellier

ICD, Université de Technologie de Troyes

LS2N, Université de Nantes

Origens Medialab et ESC Clermont

UMR Espace dev, Université de Montpellier

ERIAS/INSERM BPH U1219, Université de Bordeaux

LORIA, CNRS Nancy

LORIA, Université de Metz

LIMICS, Université Paris 13

LRI, Université Paris Sud

LS2N, Université de Nantes

Luxembourg Institute of Science and Technology

LRI, Université Paris Sud

TSCF, Irstea

LRI, Université Paris Sud

ICD, Université de Technologie de Troyes

LIRIS, Université Lumière Lyon 2

LabGED, Badji Mokhtar University

I3S, Université Nice Sophia Antipolis

LIRMM, Université de Montpellier

LS2N, Université de Nantes

Data Science, EURECOM

I3S, CNRS

LIP6, Université Pierre et Marie Curie

LIPN, Université Paris 13

LIMSI, CNRS, Université Paris-Saclay, Orsay

## 13es Journées Planification, Décision et Apprentissage (JFPDA)

Présidents : Olivier Buffet, LORIA, INRIA

Alain Dutech, LORIA, INRIA

Vincent Thomas, LORIA, Université de Lorraine

* Aurélie Beynier

* Martin Cooper

* Jilles Dibangoye

* Humbert Fiorino

* Matthieu Geist

* Laurent Jeanpierre

* Emilie Kaufmann

* Frédéric Maris

* Marc Metivier

* Abdel-Illah Mouaddib

* Damien Pellier

* Philippe Preux

* Emmanuel Rachelson

* Bruno Zanuttini

LIP6, Université Pierre et Marie Curie (Paris 6)

IRIT, Université Paul Sabatier

CITI, INSA-Lyon, Université de Lyon, INRIA

LIG, Université Grenoble Alpes

LIEC, Université de Lorraine

GREYC, Université Caen-Normandie

CRISTAL, CNRS, Lille

IRIT, Université Paul Sabatier - Toulouse III

LIPADE, Université Paris Descartes (Paris 5)

GREYC, Université Caen-Normandie

LIG, Université Grenoble Alpes

CRISTAL, INRIA, Université de Lille

ISAE-SUPAERO, Toulouse

GREYC, Université Caen-Normandie
# Comité d'organisation

## Laboratoire LORIA

**Présidents** : Armelle Brun et Davy Monticolo

* Anne Bonneau

* Anne Boyer

* Olivier Buffet

* Sylvain Castagnos

* Vincent Chevrier

* Alain Dutech

* Audrey Knauf

* David Langlois

* Slim Ouni

* Azim Roussanaly

* Romain Serizel

* Vincent Thomas

* Olivia Brenner

* Chantal Chrétien

CNRS

Université de Lorraine

Inria

Université de Lorraine

Université de Lorraine

Inria

Université de Lorraine

Université de Lorraine

Université de Lorraine

Université de Lorraine

Université de Lorraine

Université de Lorraine

Université de Lorraine

Université de Lorraine
Partenaires PFIA 2018

<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /></figure>

ARDANS
Knowledge Consulting & Software Solution

Cdiscount
N ÉCONOMISEZ PAS VOTRE PLAISIR

<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>

MINISTÈRE
DES ARMÉES

<figure><img src="image_15.png" /></figure>

<figure><img src="image_16.png" /></figure>

<figure><img src="image_17.png" /></figure>

<figure><img src="image_18.png" /></figure>

<figure><img src="image_19.png" /></figure>

masa
www.masasim.com

métropole
 Grand Nancy

nexter
SYSTEMS

<figure><img src="image_20.png" /></figure>

<figure><img src="image_21.png" /></figure>

Pacte

Novation

<figure><img src="image_22.png" /></figure>

<figure><img src="image_23.png" /></figure>

<figure><img src="image_24.png" /></figure>

SOCIETE
GENERALE

sopra

<figure><img src="image_25.png" /></figure>

steria

<figure><img src="image_26.png" /></figure>

UNIVERSITÉ
DE LORRAINE
<figure><img src="image_27.png" /></figure>
# Prédire l'intensité de contradiction dans les commentaires : faible, forte ou très forte ?

Ismail Badache

Sébastien Fournier

Adrian-Gabriel Chifu

Aix Marseille Univ, Université de Toulon, CNRS, LIS, Marseille, France

{ismail.badache, sebastien.fournier, adrian.chifu}@lis-lab.fr

## Résumé

Les commentaires sur des ressources Web (ex. des cours, des films) deviennent de plus en plus exploitées dans des tâches d'analyse de texte (ex. détection d'opinion, détection de controverses). Cet article étudie l'intensité de contradiction dans les commentaires en exploitant différents critères tels que la variation des notations et la variation des polarités autour d'entités spécifiques (ex. aspects, sujets). Premièrement, les aspects sont identifiés en fonction des distributions des termes émotionnels à proximité des noms les plus fréquents dans la collection des commentaires. Deuxièmement, la polarité est estimée pour chaque segment de commentaire contenant un aspect. Seules les ressources ayant des commentaires contenant des aspects avec des polarités opposées sont prises en compte. Enfin, les critères sont évalués, en utilisant des algorithmes de sélection d'attributs, pour déterminer leur impact sur l'efficacité de la détection de l'intensité des contradictions. Les critères sélectionnés sont ensuite introduits dans des modèles d'apprentissage pour prédire l'intensité de contradiction. L'évaluation expérimentale est menée sur une collection contenant 2244 cours et leurs 73873 commentaires, collectés à partir de coursera.org. Les résultats montrent que la variation des notations, la variation des polarités et la quantité de commentaires sont les meilleurs prédicteurs de l'intensité de contradiction. En outre, J48 est l'approche d'apprentissage la plus efficace pour cette tâche.

## Mots Clef

Analyse de sentiments, Détection d'aspects, Évaluation des critères, Intensité de contradiction.

## Abstract

Reviews on web resources (e.g. courses, movies) become increasingly exploited in text analysis tasks (e.g. opinion detection, controversy detection). This paper investigates contradiction intensity in reviews exploiting different features such as variation of ratings and variation of polarities around specific entities (e.g. aspects, topics). Firstly, aspects are identified according to the distributions of the emotional terms in the vicinity of the most frequent nouns in the reviews collection. Secondly, the polarity of each

review segment containing an aspect is estimated. Only resources containing these aspects with opposite polarities are considered. Finally, some features are evaluated, using feature selection algorithms, to determine their impact on the effectiveness of contradiction intensity detection. The selected features are used to learn some state-of-the-art learning approaches. The experiments are conducted on the Massive Open Online Courses data set containing 2244 courses and their 73,873 reviews, collected from coursera.org. Results showed that variation of ratings, variation of polarities, and reviews quantity are the best predictors of contradiction intensity. Also, J48 was the most effective learning approach for this type of classification.

## Keywords

Sentiments analysis, Aspects detection, Criteria evaluation, Contradiction intensity.

## 1 Introduction

Au cours des dernières années, le web 2.0 est devenu un espace ouvert où les gens peuvent exprimer leurs opinions en laissant des traces (par exemple, un commentaire, une notation, un j'aime) sur les ressources Web. De nombreux services, tels que les blogs et les réseaux sociaux, représentent une source riche de ces données sociales, qui peuvent être analysées et exploitées dans diverses applications et contextes [2, 3, 4, 6, 17]. En particulier la détection d'opinion et l'analyse de sentiments [15], par exemple, pour connaître l'attitude d'un client vis-à-vis d'un produit ou de ses caractéristiques, ou pour révéler la réaction des gens à un événement. De tels problèmes nécessitent une analyse rigoureuse des aspects couverts par le sentiment pour produire un résultat représentatif et ciblé.

Une autre problématique concerne la diversité des opinions sur un sujet donné. Certains travaux l'abordent dans le contexte de différents domaines de recherche, avec une notion différente dans chaque cas. Par exemple, Wang et Cardie [40] visent à identifier des sentiments au niveau d'une phrase exprimée au cours d'une discussion et à les utiliser comme des caractéristiques dans un classifieur qui prédit

<footnote n="1">1. https://www.coursera.org/learn/dog-emotion-and-cognition</footnote>
<table><caption>TABLE 1 – Exemple de deux opinions contradictoires sur le "Speaker" d'un cours coursera</caption><thead><tr><th>Ressource</th><th>Commentaire (gauche)</th><th>Aspect</th><th>Commentaire (droite)</th><th>Polarité</th><th>Notation</th></tr></thead><tbody><tr><td rowspan="2">Cours <sup>1</sup></td><td>The lecturer was an <span style="color:red;">annoying</span> speaker</td><td></td><td>and <span style="color:red;">very repetitive</span>.</td><td><span style="color:red;">-0.9</span></td><td><span style="color:red;">1</span></td></tr><tr><td>Passionate speaker</td><td></td><td>and truly <span style="color:green;">amazing</span> things to learn</td><td><span style="color:green;">+0.7</span></td><td><span style="color:green;">4</span></td></tr></tbody></table>

la dispute dans la discussion. Qiu et al. [29] identifient automatiquement les débats entre des utilisateurs à partir du contenu textuel (interactions) dans les forums, en se basant sur des modèles de variables latentes. Il y a eu d'autres travaux dans l'analyse des interactions avec les utilisateurs, par exemple, l'extraction des expressions de type agreement et disagreement [24] et d'en déduire les relations de l'utilisateur en regardant leurs échanges textuels [1].

Cet article étudie les entités (par exemple, les aspects, les sujets) pour lesquelles des contradictions peuvent apparaître dans les commentaires associés à une ressource Web (par exemple des films, des cours) et comment estimer leur intensité. L'intérêt d'estimer l'intensité de la contradiction dépend du cadre d'application. Par exemple, suivre des événements ou des crises politiques controversés tels que la reconnaissance par les États-Unis de Jérusalem comme capitale d'Israël. Cela a généré des opinions (avis) contradictoires, dans les réseaux sociaux, entre différentes communautés à travers le monde. L'estimation de l'intensité de ce conflit peut être utile pour mieux analyser la tendance et les conséquences de cette décision politique. Dans le cas de la recherche d'information sociale, pour certains besoins d'information, mesurer l'intensité de la contradiction peut être utile pour identifier et classer les documents les plus controversés (par exemple les nouvelles, les événements, etc.). Dans notre cas, connaître l'intensité des opinions contradictoires sur un aspect spécifique (par exemple, Lectorer, Speaker, Slide, Quiz) d'un cours en ligne (en anglais) peut être utile pour savoir s'il y a certains éléments à améliorer dans ce cours. Table 1 présente une instance de commentaires contradictoires à propos de l'aspect Speaker (conférencier) d'un cours donné.

Afin de concevoir notre approche, des tâches fondamentales sont effectuées. Premièrement, l'extraction automatisque des aspects caractérisants ces commentaires. Deuxièmement, l'identification des opinions opposées autour de chacun de ces aspects en utilisant un modèle d'analyse des sentiments. Enfin, nous allons évaluer l'impact de certains critères (par exemple, le nombre de commentaires négatifs, le nombre de commentaires positifs) sur l'estimation de l'intensité de contradiction. Plus précisément, nous tenons de sélectionner les critères les plus efficaces et de les combiner avec des approches d'apprentissage pour prédire l'intensité de contradiction. Les principales contributions abordées dans cet article sont doubles :

* (C1). Une contradiction dans des commentaires liés à une ressource Web donnée signifie des opinions contradictoires exprimées sur un aspect spécifique, qui est une forme de diversité de sentiments autour de l'aspect au sein de la même ressource. Mais en plus de détecter la

contradiction, il est souhaitable d'estimer son intensité. Par conséquent, nous essayons de répondre aux questions de recherche suivantes :

◇ **QR1.** Comment estimer/prédire l'intensité de la contradiction ?

◇ **QR2.** Quel est l'impact de la prise en compte des polarités et des notations sur la prédiction de l'intensité des commentaires contradictoires ?

* (C2). La construction d'une collection de test issue du site Web des MOOC<fnref n="2" /> coursera.org. Cette collection est utile pour l'évaluation des systèmes mesurant l'intensité de contradiction. Des études expérimentales orientées utilisateurs - user studies - ont été menées pour collecter les jugements de l'intensité de contradiction (Not Contradictory, Very Low, Low, Strong and Very Strong).

L'article est organisé comme suit. La section 2 présente certains travaux connexes. La section 3 détaille notre approche pour la prédiction de l'intensité des contradictions autour de certains aspects spécifiques. L'évaluation expérimentale est présentée dans la section 4. Enfin, la section 5 conclut l'article en annonçant des perspectives.

## 2 Vue d'ensemble : État de l'art

La détection de contradictions est un processus complexe qui nécessite souvent l'utilisation de plusieurs méthodes. Plusieurs travaux ont été proposés pour ces méthodes (détection des aspects, analyse de sentiments) mais à notre connaissance, très peu de travaux traitent de la détection et de la mesure de l'intensité de la contradiction. Dans cette section, nous allons brièvement présenter quelques approches de détection de controverses proches de nos travaux puis nous allons présenter les approches liées à la détection des aspects et l'analyse de sentiments, qui sont utiles pour introduire notre approche.

### 2.1 Approches de détection des contradictoires et des controverses

Les études les plus liées à notre approche incluent [14, 9, 36] et [37], qui tentent de détecter une contradiction dans le texte. Il y a deux approches principales, où les contradictoires sont définies comme une forme d'inférence textuelle (par exemple, entailment identification) et analysées en utilisant des technologies linguistiques. Harabagiu et al. [14] ont proposé une approche d'analyse des contradictions en exploitant des caractéristiques linguistiques et sémantiques

<footnote n="2">2. Massive Open Online Course</footnote>
(ex. typologie de verbes), ainsi que des informations syn-
taxiques telles que la négation (ex. *I love you - I do not
love you*) ou l'antonyme (des mots qui ont des significa-
tions opposées, c.à-d. *hot-cold* ou *light-dark*). Leur travail
définit les contradictions comme une implication textuelle
(textual entailment<fnref n="3" />) qui est fausse, lorsque deux phrases
expriment des informations mutuellement exclusives sur le
même sujet. L'antonymie peut donner lieu à une contra-
diction lorsque les gens utilisent ces mots pour décrire un
sujet. Poursuivant l'amélioration des travaux dans ce sens,
De Marneffe et al. [9] a introduit une classification des
contradictions consistant en 7 types qui se distinguent par
les caractéristiques qui contribuent à une contradiction, par
exemple, l'antonyme, la négation, les discordances numé-
riques qui peuvent être causées par des données erronées :
«there are 7 wonders of the world - the number of wonders
of the world are 9». Ils ont défini les contradictions comme
une situation où il est extrêmement improbable que deux
phrases soient vraies lorsqu'elles sont ensemble. Tsytsa-
rau et al. [36, 37] ont proposé une solution automatique
et évolutive pour le problème de détection de contradic-
tions en utilisant l'analyse des sentiments. L'intuition de
leur approche est que lorsque la valeur agrégée des senti-
ments (sur un sujet et un intervalle de temps spécifiques)
est proche de zéro, alors que la diversité des sentiments est
élevée, la contradiction devrait être élevée.

Un autre thème lié à notre travail concerne la détection des
controverses et des disputes. Dans la littérature, la détec-
tion des controverses a été abordée à la fois par des mé-
thodes supervisées comme dans [27, 7, 41] ou par des
méthodes non supervisées comme dans [5, 10, 11, 19].
Pour détecter les événements controversés sur Twitter (par
exemple, l'accusation de viol de David Copperfield entre
2007 et 2010)<fnref n="4" />, Popescu et Pennacchiotti [27] ont proposé
un classifieur basé sur un apprentissage par arbre de déci-
sion et un ensemble de caractéristiques telles que les parties
du discours, la présence de mots issus du lexique d'opin-
ion ou de controverse, et les interactions des utilisateurs
(retweet et reply). Balasubramanyan et al. [7] ont étendu le
modèle LDA (Latent Dirichlet Allocation) supervisé pour
prédire comment les membres des différentes communau-
tés politiques réagiront émotionnellement au même sujet
c-à-d. la prédiction du niveau de controverse associé à ce
sujet. Des classifieurs de type machine à vecteurs de sup-
port et régression logistique ont également été proposés par
Wang et al. [41] et par Wang et Cardie [40] pour détecter
les disputes dans les discussions sur la page de Wikipedia.
Par exemple dans le cas des commentaires sur les modifi-
cations des pages Wikipedia.

D'autres travaux ont également exploité Wikipédia pour
détecter et identifier des sujets controversés sur le Web
[10, 18, 19]. Dori-Hacohens et Allan [10] et Jang et Al-
lan [18] ont proposé d'aligner les pages Web aux pages de

Wikipedia en supposant qu'une page traite un sujet contro-
versé si la page Wikipedia décrit un sujet lui-même contro-
versé. La nature controversée ou non controversée d'une
page Wikipedia est automatiquement détectée sur la base
des métadonnées et des discussions associées à la page.
Jang et al. [19] ont construit un modèle de langage des
sujets controversés appris sur des articles de Wikipédia et
utilisé ensuite pour identifier si une page Web est contro-
versée.

La détection des controverses dans les médias sociaux a également été abordée sans supervision en se basant sur les interactions entre les différents utilisateurs [11]. Garimella et al. [11] ont proposé d'autres approches de mesure de contradiction basées sur la topologie du réseau, telles que la marche aléatoire (random walk), la centralité intermédiaire (betweenness centrality) et le plongement de graphe à faible dimension (low-dimensional graph embeddings). Les auteurs ont testé des méthodes basées sur le contenu et ont noté leur inefficacité par rapport aux méthodes basées sur un graphe utilisateur. D'autres études tentent de détecer des controverses sur des domaines spécifiques, p. ex. dans les news [35] ou dans l'analyse du débat [29].

Cependant, à notre connaissance, aucun travail antérieur
n'a abordé, de manière explicite et concrète, l'intensité
de la contradiction ou de la controverse. Dans cet article,
contrairement aux travaux antérieurs, plutôt que d'iden-
tifier seulement la controverse autour d'un sujet choisi
au préalable (par exemple, aspect lié aux nouvelles poli-
tiques), nous nous concentrons également sur l'estimation
de l'intensité des opinions contradictoires autour de su-
jets spécifiques. Nous proposons de mesurer l'intensité de
la contradiction en utilisant certaines caractéristiques (par
exemple, la notation et la polarité).

2.2 Approches de détection des aspects

Les premières tentatives de détection d'aspects ont été ba-
sées sur l'approche classique d'extraction d'information
(IE) en exploitant les phrase nominales fréquentes [16].
De telles approches fonctionnent bien dans la détection
des aspects qui sont sous la forme d'un seul nom, mais
sont moins efficaces lorsque les aspects sont de faible fré-
quence. Dans le contexte de la détection d'aspects, bon
nombre de travaux utilisent les CRF (Conditional Ran-
dom Fields) ou les HMM (Hidden Markov Models). Parmi
ces travaux, nous pouvons citer [13] qui utilisent les CRF.
D'autres méthodes sont non supervisées et ont prouvé leur
efficacité tel que dans [34] qui construisent un modèle
thématique à grains multiples (Multi-Grain Topic Model).
Nous pouvons aussi citer le modèle HASM (unsupervised
Hierarchical Aspect Sentiment Model) proposé par Kim et
al. [20] qui permet de découvrir une structure hiérarchique
du sentiment fondée sur les aspects dans les avis en ligne
non labellés. Dans nos travaux, nous nous sommes inspirés
de la méthode non supervisée développée par Poria et al.
[28] basée sur l'utilisation de règles d'extraction pour les
avis sur les produits. Cette méthode est en cohérence avec

<footnote n="3">3. https://en.wikipedia.org/wiki/Textual entailment</footnote>

<footnote n="4">4. http://news.bbc.co.uk/2/hi/entertainment/8456070.stm</footnote>
nos données expérimentales issues de coursera.org.

## 2.3 Approches d'analyse de sentiments

L'analyse du sentiment a fait l'objet de très nombreuses recherches antérieures. Comme dans le cas de la détection d'aspects, les approches supervisées et non supervisées ont chacune leurs solutions. Ainsi, dans les approches non supervisées, nous pouvons citer les approches basées sur les lexiques telles que l'approche développée par Turney [38] ou bien des méthodes basées sur des corpus comme les travaux de Mohammad et al. [23]. Au rang des approches supervisées, nous pouvons citer [25] qui comme nombre de travaux perçoivent la tâche d'analyse de sentiments comme une tâche de classification et utilisent donc des méthodes comme les SVM (Support Vector Machines) ou les réseaux bayésiens. D'autres travaux récents sont basés sur les RNN (Recursive Neural Network) tels que les travaux de Socher et al. [32]. Comme le propos de cet article est de mesurer l'intensité de contradiction et que l'analyse de sentiments n'est qu'une étape du processus, nous avons utilisé l'approche proposée par Radford et al. [31], dont son implémentation est publiquement disponible<fnref n="5" />. Nous décrivons cette méthode dans la section 3.1.

# 3 Notre approche : Prédiction de l'intensité des contradictions

Notre approche est basée à la fois sur la détection d'aspects dans les commentaires ainsi que sur l'analyse des sentiments du texte autour de ces aspects. En plus de la détection de contradiction, notre objectif est de prédire le niveau d'intensité de la contradiction en utilisant certains critères et caractéristiques. Ces caractéristiques sont liées à la notation et à la polarité des commentaires-aspect (texte autour d'un aspect donné).

## 3.1 Pré-traitement : Identification des polarités autour des aspects

Le pré-traitement est une étape clé pour l'analyse des commentaires (aspects et sentiments). Le module de pré-traitement se compose de trois étapes principales : d'une part, le marquage des termes (identification des noms, verbes, etc), par une analyse syntaxique, au sein des commentaires. Deuxièmement, les noms les plus fréquents dans l'ensemble des commentaires des différents documents sont extraits. Troisièmement, uniquement les noms entourés par des termes émotionnels sont considérés comme des aspects. Nous détaillons ces étapes dans ce qui suit.

**Extraction des aspects.** Dans notre étude, un aspect est une entité nominale fréquente dans les commentaires et entourée par des termes émotionnels. Afin d'extraire les aspects à partir du texte des commentaires, nous nous

sommes basés sur le travail de Poria et al. [28]. Cette méthode correspond à nos données expérimentales (commentaires issus de coursera). De plus, les traitements suivants sont appliqués :

1. Calcul fréquentiel des termes constituant le corpus des commentaires,

2. Catégorisation des termes (Part-of-speech tagging) de chaque commentaire en utilisant Stanford Parser <fnref n="6" />,

3. Sélection des termes ayant la catégorie nominale (NN, NNS selon le Part of Speech Tags) <fnref n="7" />,

4. Sélection des noms avec des termes émotionnels dans leur voisinage de 5 mots (en utilisant SentiWordNet) <fnref n="8" />. Le choix de 5 mots a été fait après plusieurs expérimentations,

5. Extraction des termes les plus fréquents dans le corpus parmi ceux sélectionnés dans l'étape précédente. Ces termes seront considérés comme des aspects.

*Exemple :* Soit $C = \{c_1, c_2, c_3\}$ un ensemble de 3 commentaires associés à un document *D*. Nous voulons extraire les aspects à partir de chacun des commentaires en appliquant les étapes décrites ci-dessus.

Nous avons $c_1 = "The lecturer was an annoying speaker and very repetitive. I just couldn't listen to him. . . I'm sorry. There was also so much about human development etc that I started to wonder when the info about dogs would start. . . . I found the formatting so different from other courses I've taken, that it was hard to get started and figure things out. Adding to that, was the constant interruption of the "paid certificate" page. If I answer "no" once, please leave me alone! I also think it's a bit suspect for a prof to be plugging his own book for one of these courses.""$^8$

La table 2 récapitule les 5 étapes. Premièrement, nous calculons les fréquences des termes dans l'ensemble des commentaires (à titre d'exemple, les termes "course", "material", "assignments", "content", "lecturer" apparaissent 44219, 3286, 3118, 2947, 2705, respectivement). Deuxièmement, nous étiquetons grammaticalement chaque mots (par exemple, "NN", "NNS" signifient nom en singulier et nom en pluriel, respectivement <fnref n="9" />). Troisièmement, seul les termes de catégorie nominale sont sélectionnés. Quatrièmement, nous gardons uniquement les noms entourés par des termes appartenant au dictionnaire SentiWordNet (The lecturer was an annoying speaker and very repetitive). Enfin, nous considérons comme aspects utiles uniquement les noms qui figurent parmi les noms les plus fréquents dans le corpus des commentaires (l'aspect utile dans ce commentaire est lecturer).

Une fois la liste des aspects qui caractérisent notre collection de données est définie, nous devons estimer la polarité

<footnote n="6">6. http://nlp.stanford.edu:8080/parser/</footnote>

<footnote n="7">7. https://cs.nyu.edu/grishman/jet/guide/</footnote>

<footnote>PennPOS.html</footnote>

<footnote n="8">8. http://sentiwordnet.isti.cnr.it/</footnote>

<footnote n="9">9. http://www.ling.upenn.edu/courses/Fall_2003/ling001/penn_treebank_pos.html</footnote>

<footnote n="5">5. https://github.com/openai/generating-reviews-discovering-sentiment</footnote>
<table><caption>TABLE 2 – Les différentes étapes pour extraire les aspects dans un commentaire</caption><thead><tr><th>Étape</th><th>Description</th></tr></thead><tbody><tr><td>(1)</td><td>course : 44219, material : 3286, assignments : 3118, content : 2947, lecturer : 2705, ...... terme<sub>i</sub></td></tr><tr><td>(2)</td><td>The/DT <b>lecturer</b>/NN was/VBD an/DT annoying/VBG <b>speaker</b>/NN and/CC very/RB repetitive/JJ /.. I/PRP just/RB could/MD n't/RB listen/VB to/TO him/PRP .../ : I/PRP 'm/VBP sorry/JJ /.. There/EX was/VBD also/RB so/RB much/JJ about/IN human/JJ <b>development</b>/NN etc/NN that/IN I/PRP started/VBD to/TO wonder/VB when/WRB the/DT <b>info</b>/NN about/IN dogs/NNS would/MD start/VB .../ : /.. I/PRP found/VBD the/DT <b>formatting</b>/NN so/RB different/JJ from/IN other/JJ <b>courses</b>/NNS I/PRP 've/VBP taken/VBN /, that/IN it/PRP was/VBD hard/JJ to/TO get/VB started/VBN and/CC figure/VB <b>things</b>/NNS out/RP /.. Adding/VBG to/TO that/DT /, was/VBD the/DT constant/JJ <b>interruption</b>/NN of/IN the/DT "/" paid/VBN <b>certificate</b>/NN "/" page/NN /.. If/IN I/PRP answer/VBZ "/" no/UH "/" once/RB /, please/VB leave/VB me/PRP alone/RB !/.. I/PRP also/RB think/VBP it/PRP 's/VBZ a/DT bit/RB suspect/JJ for/IN a/DT <b>prof</b>/NN to/TO be/VB plugging/VBG his/PRP$ own/JJ <b>book</b>/NN for/IN one/CD of/IN these/DT <b>courses</b>/NNS /.</td></tr><tr><td>(3)</td><td>lecturer, speaker, development, dogs, formatting, courses, interruption, certificate, page, prof</td></tr><tr><td>(4)</td><td>lecturer, speaker</td></tr><tr><td>(5)</td><td>lecturer</td></tr></tbody></table>

des sentiments autour de ces aspects. La section suivante présente notre modèle d'analyse de sentiments.

**Analyse de sentiments.** Le sentiment porté par un commentaire sur un aspect donné (commentaire-aspect) est estimé en utilisant la méthode appelée *SentiNeuron*<fnref n="10" />. *SentiNeuron* est un modèle non supervisé proposé par Radford *et al.* [31] pour détecter les signaux de sentiment dans les commentaires. Cette approche est basée sur les réseaux de neurones récurrent (recurrent neural network) de type mLSTM (multiplicative Long Short-Term Memory). [31] ont également trouvé qu'une unité dans le mLSTM correspond directement au sentiment de la sortie. Les auteurs ont mené une série d'expérimentations sur plusieurs collections de tests telles que les collections des commentaires issues d'Amazon [22] et d'IMDb<fnref n="11" />. Cette approche fournie une précision de 91.8%, et surpasse de manière significative plusieurs approches de l'état de l'art telles que celles présentées dans [21]. Nous notons que le terme polarité signifie sentiment, c'est une valeur comprise entre -1 et 1.

## 3.2 Collection de test : coursera.org

**Données collectées.** A notre connaissance, il n'existe pas à ce jour de collection de test standard, contenant des informations comme les aspects, les notations et les polarités des commentaires, pour évaluer l'efficacité des systèmes de détection de contradictions dans les commentaires. De ce fait, dans le but d'expérimenter l'efficacité de notre approche, nous avons collecté 2244 ressources en anglais extraites du site "coursera.org" via son API<fnref n="12" />, entre le 10 et le 14 octobre 2016. Chaque ressource décrit un cours et est représentée par un ensemble de métadonnées. Pour chaque cours, nous avons collecté également ses commentaires et

ses notations via le *parsing* des pages web des cours (voir les statistiques sur la table 3).

<table><caption>TABLE 3 – Les chiffres des données coursera.org</caption><thead><tr><th>Champ</th><th>Nombre</th></tr></thead><tbody><tr><td>Cours</td><td>2244</td></tr><tr><td>Cours notés</td><td>1115</td></tr><tr><td>Commentaires</td><td>73873</td></tr><tr><td>notations</td><td>298326</td></tr><tr><td>Commentaires avec notation</td><td>1705</td></tr><tr><td>Commentaires avec notation</td><td>1443</td></tr><tr><td>Commentaires avec notation</td><td>3302</td></tr><tr><td>Commentaires avec notation</td><td>12202</td></tr><tr><td>Commentaires avec notation</td><td>55221</td></tr></tbody></table>

Nous avons pu capturer automatiquement 22 aspects utiles à partir de l'ensemble des commentaires (voir table 4). La table 4 présente les statistiques sur les 22 aspects détectés, par exemple, pour l'aspect *Slide* nous avons enregistré : 56 notations d'une étoile, 64 notations de deux étoiles, 81 notations de trois étoiles, 121 notations de quatre étoiles, 115 notations de cinq étoiles, 131 commentaires avec une polarité négative, 102 commentaires avec une polarité positive ainsi que 192 commentaires et 41 cours concernant cet aspect.

**Jugements par les utilisateurs (contradictions et sentiments).** Afin d'obtenir des jugements de contradictions et de sentiments pour un aspect donné : 1) nous avons demandé à trois utilisateurs d'évaluer la classe de sentiment pour chaque commentaires-aspect de 1100 cours ; 2) trois autres utilisateurs ont évalué le degré de contradiction entre les commentaires-aspect. En moyenne 60 commentaires-aspect par cours sont jugés manuellement pour chaque aspect (totalement : 66104 commentaires-aspect de 1100 cours, c'est-à-dire 50 cours pour chaque aspect). Nous notons que chaque aspect a été jugé par 3 utilisateurs. Pour évaluer les sentiments et les contradictions dans les

<footnote n="10">10. https://github.com/openai/generating-reviews-discovering-sentiment</footnote>

<footnote n="11">11. https://www.cs.cornell.edu/personnes/pabo/film-review-data/</footnote>

<footnote n="12">12. https://building.coursera.org/app-platform/catalog</footnote>
<table><caption>TABLE 4 – Statistiques sur les aspects issus des commentaires de Coursera.org</caption><thead><tr><th>Aspects</th><th>Not1</th><th>Not2</th><th>Not3</th><th>Not4</th><th>Not5</th><th>Négatif</th><th>Positif</th><th>Comment</th><th>Cours</th></tr></thead><tbody><tr><td>Assignment</td><td>204</td><td>208</td><td>333</td><td>840</td><td>1726</td><td>1057</td><td>1763</td><td>2384</td><td>186</td></tr><tr><td>Content</td><td>176</td><td>179</td><td>341</td><td>676</td><td>1641</td><td>505</td><td>1496</td><td>1883</td><td>207</td></tr><tr><td>Exercise</td><td>29</td><td>46</td><td>94</td><td>290</td><td>693</td><td>195</td><td>531</td><td>673</td><td>58</td></tr><tr><td>Information</td><td>100</td><td>123</td><td>238</td><td>523</td><td>1389</td><td>299</td><td>1165</td><td>1359</td><td>143</td></tr><tr><td>Instructor</td><td>129</td><td>106</td><td>122</td><td>302</td><td>1514</td><td>295</td><td>1107</td><td>1322</td><td>140</td></tr><tr><td>Knowledge</td><td>74</td><td>72</td><td>121</td><td>400</td><td>1604</td><td>905</td><td>791</td><td>1243</td><td>178</td></tr><tr><td>Lecture</td><td>185</td><td>206</td><td>290</td><td>613</td><td>1762</td><td>763</td><td>1508</td><td>1988</td><td>208</td></tr><tr><td>Lecturer</td><td>32</td><td>41</td><td>48</td><td>85</td><td>461</td><td>55</td><td>193</td><td>236</td><td>39</td></tr><tr><td>Lesson</td><td>40</td><td>59</td><td>75</td><td>224</td><td>712</td><td>187</td><td>420</td><td>554</td><td>84</td></tr><tr><td>Material</td><td>191</td><td>203</td><td>328</td><td>722</td><td>2234</td><td>784</td><td>1693</td><td>2254</td><td>237</td></tr><tr><td>Method</td><td>19</td><td>23</td><td>40</td><td>125</td><td>404</td><td>53</td><td>187</td><td>224</td><td>31</td></tr><tr><td>Presentation</td><td>46</td><td>50</td><td>75</td><td>142</td><td>413</td><td>93</td><td>196</td><td>274</td><td>54</td></tr><tr><td>Professor</td><td>76</td><td>74</td><td>129</td><td>452</td><td>3001</td><td>331</td><td>2234</td><td>2369</td><td>151</td></tr><tr><td>Quality</td><td>55</td><td>53</td><td>51</td><td>110</td><td>372</td><td>113</td><td>170</td><td>262</td><td>54</td></tr><tr><td>Question</td><td>94</td><td>98</td><td>172</td><td>284</td><td>356</td><td>311</td><td>289</td><td>502</td><td>104</td></tr><tr><td>Quiz</td><td>151</td><td>155</td><td>221</td><td>401</td><td>581</td><td>481</td><td>475</td><td>824</td><td>128</td></tr><tr><td>Slide</td><td>56</td><td>64</td><td>81</td><td>121</td><td>115</td><td>131</td><td>102</td><td>192</td><td>47</td></tr><tr><td>Speaker</td><td>17</td><td>15</td><td>34</td><td>70</td><td>170</td><td>34</td><td>72</td><td>103</td><td>24</td></tr><tr><td>Student</td><td>140</td><td>105</td><td>171</td><td>383</td><td>1035</td><td>519</td><td>709</td><td>1066</td><td>172</td></tr><tr><td>Teacher</td><td>62</td><td>46</td><td>82</td><td>293</td><td>2180</td><td>248</td><td>1481</td><td>1642</td><td>119</td></tr><tr><td>Topic</td><td>67</td><td>89</td><td>176</td><td>437</td><td>1154</td><td>236</td><td>951</td><td>1066</td><td>130</td></tr><tr><td>Video</td><td>228</td><td>238</td><td>356</td><td>707</td><td>1614</td><td>941</td><td>1421</td><td>2058</td><td>245</td></tr></tbody><tfoot><tr><td colspan="10">Nombre total : 22 aspects détectés</td></tr></tfoot></table>

<figure><img src="image_28.png" /><figcaption>FIGURE 1 – Interface du système d’évaluation</figcaption></figure>

commentaires-aspect de chaque cours, nous utilisons une échelle de notation de 3 points pour les sentiments : (Negative, Neutral, Positive) ; et une échelle de 5 points pour les contradictions : Not Contradictory, Very Low, Low, Strong et Very Strong (voir la figure 1).

Nous avons analysé le degré d'accord entre les évaluateurs des contradictions pour chaque aspect avec la mesure Kappa Cohen *k* [8]. Cet indicateur prend en compte la proportion d'accord entre les évaluateurs et la proportion de l'accord attendu entre les évaluateurs par hasard. La mesure de Kappa est égale à 1 si les évaluateurs sont complètement d'accord, 0 s'ils ne sont d'accord que par hasard. *k* est négatif si l'accord entre évaluateurs est pire que l'aléatoire. Comme nous avons trois évaluateurs par aspect, la

valeur Kappa a été calculée pour chaque paire d'évaluateurs, puis leur moyenne a été calculée.

La figure 2 montre la distribution de la mesure kappa pour chaque aspect. Nous constatons que la mesure de l'accord varie de 0.60 à 0.91. La mesure moyenne d'accord entre les évaluateurs est de 80%, ce qui correspond à un accord fort. Concernant l'analyse du degré d'accord entre les évaluateurs des sentiments, nous avons trouvé un accord de Kappa *k* = 0.78, qui correspond aussi à un accord fort.

## 3.3 Identification des critères les plus efficaces

Dans cette étude, nous nous sommes appuyés sur des algorithmes de sélection d'attributs pour déterminer les critères
<figure><img src="image_29.png" /><figcaption>FIGURE 2 – Répartition de la mesure Kappa *k* par aspect. < 0 désaccord, 0.0 – 0.2 accord très faible, 0.21 – 0.40 accord faible, 0,41 – 0,6 accord modéré, 0,61 – 0,80 accord fort, 0,81 – 1 accord parfait.</figcaption></figure>

<table><caption>TABLE 5 – Liste des critères exploités</caption><thead><tr><th>c<sub>i</sub></th><th>Critère</th><th>Description</th></tr></thead><tbody><tr><td>c<sub>1</sub></td><td>NegCom</td><td>Nombre de commentaires négatifs sur le document</td></tr><tr><td>c<sub>2</sub></td><td>PosCom</td><td>Nombre de commentaires positifs sur le document</td></tr><tr><td>c<sub>3</sub></td><td>TotalCom</td><td>Nombre total des commentaires sur le document</td></tr><tr><td>c<sub>4</sub></td><td>Not1</td><td>Nombre de commentaires avec notation ★★★★★</td></tr><tr><td>c<sub>5</sub></td><td>Not2</td><td>Nombre de commentaires avec notation ★★★★★</td></tr><tr><td>c<sub>6</sub></td><td>Not3</td><td>Nombre de commentaires avec notation ★★★★★</td></tr><tr><td>c<sub>7</sub></td><td>Not4</td><td>Nombre de commentaires avec notation ★★★★★</td></tr><tr><td>c<sub>8</sub></td><td>Not5</td><td>Nombre de commentaires avec notation ★★★★★</td></tr><tr><td>c<sub>9</sub></td><td>VarNot</td><td>Variation des notations (écart type selon [26])</td></tr><tr><td>c<sub>10</sub></td><td>VarPol</td><td>Variation des polarités (écart type selon [26])</td></tr></tbody></table>

les plus importants pour la tâche de prédiction d'intensité de contradiction. Les algorithmes de sélection d'attributs visent à identifier et supprimer le maximum d'information inutile, redondante et non pertinente en amont d'un processus à base d'apprentissage [12]. Ils permettent également de sélectionner de manière automatique les sous ensembles de critères permettant d'avoir les meilleurs résultats. Nous avons utilisé Weka<fnref n="13" /> (dernière version stable 2018 : 3.8.2), un outil open-source écrit entièrement en Java et qui rassemble un bon ensemble de techniques d'apprentissage et des techniques de sélection d'attributs.

La table 5 présente les 10 critères que nous avons considérés pour prédire l'intensité de contradiction dans les commentaires. La nature des critères $c_1$ jusqu'au critère $c_8$ est un simple comptage, par exemple les critères $c_1$ et $c_2$ liés à la polarité représentent le nombre de commentaires négatifs et positifs sur le document, respectivement. Les critères $c_4$, $c_5$, $c_6$, $c_7$ et $c_8$ sont liés à la notation. La notation est une note sur une échelle de 1 à une valeur max de 5, où 3 signifie "moyen" et 5 signifie "excellent". Concernant les deux derniers critères $c_9$ et $c_{10}$, ils représentent la variation des notations et des polarités des commentaires pour un aspect

donné associés à un document (un cours dans notre cas). Ces deux critères sont calculés en se basant sur la formule de l'écart type proposée par Pearson et Stephens [26] :

$$s = \sqrt{\frac{\sum_{i=1}^{n} (x - \bar{x})^2}{n}} \quad (1)$$

Où *x* est la valeur du critère (notation, polarité), $\bar{x}$ est la moyenne de l'échantillon du critère concerné, et *n* est la taille de l'échantillon.

Dans cette étude, nous avons procédé ainsi : 50 cours avec leurs commentaires pour chaque aspect (22 aspects) de la collection *coursera* ont été extraits aléatoirement. Ensuite, nous avons considéré l'échelle des 4 points comme des classes reflétant l'intensité des contradictions autour d'un aspect spécifique : *Very Low*, *Low*, *Strong* et *Very Strong*, selon les jugements des évaluateurs. L'ensemble résultant contient 1100 cours (instances) répartis selon leur classe d'intensité de contradiction comme suit :

- 230 Very Low

- 264 Low

- 330 Strong

<footnote n="13">13. http://www.cs.waikato.ac.nz/ml</footnote>
— 276 Very Strong

Les classes de ces ensembles sont déséquilibrées, or
lorsque le nombre d'éléments d'une classe dans une
collection d'apprentissage dépasse considérablement les
autres échantillons des autres classes, un classifieur tend
à prédire les échantillons de la classe majoritaire et peut
ignorer complètement les classes minoritaires [42]. Pour
cette raison, nous avons appliqué une approche de sous-
échantillonnage (en réduisant le nombre d'échantillons qui
ont la classe majoritaire) pour générer des collections équi-
librées composées de :

— 230 Very Low

— 230 Low

— 230 Strong

— 230 Very Strong

Les classes *Low*, *Strong* et *Very Strong* ont été sélectionnées aléatoirement. Enfin, nous avons appliqué les algorithmes de sélection d'attributs sur les quatre ensembles obtenus, pour 5 itérations de validation croisée (5-folds cross-validation).

Dans notre cas, les algorithmes de sélection d'attributs consistent à attribuer un score à chaque critère en fonction de sa signification vis-à-vis la classe d'intensité de contradiction (*Very Low*, *Low*, *Strong* et *Very Strong*). Ces algorithmes fonctionnent différemment : certains retournent un classement d'importance des critères (par exemple, *Filterer-dAttributeEval*), tandis que d'autres retournent le nombre de fois qu'un critère donné a été sélectionné par un algorithme dans une validation croisée (par exemple, *Filte-redSubsetEval*). Nous notons que nous avons utilisé pour chaque algorithme le paramétrage par défaut fourni par Weka.

Nous avons appliqué une validation croisée à 5 itérations pour 10 critères, c'est-à-dire $n = 10$. La table 6 présente les critères sélectionnés par les algorithmes de sélection d'attributs. Nous avons utilisé deux types de ces algorithmes : a) ceux qui utilisent des méthodes de classement pour ordonner les critères sélectionnés (la métrique dans la table est [Rank]) ; et b) ceux qui utilisent des méthodes de recherche qui indiquent combien de fois le critère a été sélectionné pendant la tâche de la validation croisée (la métrique dans la table est [Folds]). Un critère fortement préféré (choisi) par l'algorithme de sélection est un critère bien classé, c'est-à-dire Rank = 1 et fortement sélectionné, c'est-à-dire Folds = 5.

La table 6 montre que les critères $c_{10}$ : *VarPol*, $c_9$ : *VarNot*, $c_1$ : *NegCom* et $c_2$ : *PosCom* sont les plus sélectionnés et les mieux classés par rapport aux autres critères. Les critères $c_3$ : *TotalCom*, $c_4$ : *Not1* et $c_8$ : *Not5* sont modérément favorisés par les algorithmes de sélection d'attributs, à l'exception de l'algorithme *CfsSubsetEval* qui n'a pas sélectionné $c_4$ et $c_8$. Les critères $c_5$, $c_6$ et $c_7$ ne sont pas sélectionnés à la fois par les algorithmes *CfsSubsetEval* et *WrapperSubsetEval*. Enfin, les critères les plus faibles et les plus désa-

vantagés sont $c_5$ : *Not2* et $c_6$ : *Not3*, ils sont ordonnés au rang 9 et 10, respectivement.

3.4 Apprentissage des critères pour prédire l'intensité de contradiction

D'autres expérimentations ont été menées en exploitant ces
critères dans des approches supervisées basées sur des mo-
dèles d'apprentissage. Nous avons utilisé les instances (les
cours) des 22 aspects de la collection coursera.org comme
ensembles d'apprentissage. Nous avons ensuite utilisé trois
algorithmes d'apprentissage. Ce choix s'explique par le fait
qu'ils ont souvent montré leur efficacité dans les tâches
d'analyse de texte : SVM [39], J48 (implémentation C4.5)
[30] et Naïve Bayes [43]. L'entrée de chaque algorithme
est un vecteur de critères (voir table 5), soit tous les critères
ou seulement les critères sélectionnés par un algorithme de
sélection précis. Les algorithmes d'apprentissage prédisent
la classe d'intensité de contradiction pour les cours (*Very
Low*, *Low*, *Strong* et *Very Strong*). Enfin, nous avons appli-
qué une validation croisée pour 5 itérations (5-folds cross-
validation). La figure 3 illustre le processus d'apprentis-
sage que nous avons mis en place pour l'évaluation des cri-
tères. Nous rappelons que la phase des algorithmes de sé-
lection d'attributs a fait ressortir les ensembles de critères
suivants (voir la table 7).

La question à ce stade est liée à la spécification du vecteur
de critères d'entrée pour les algorithmes d'apprentissage,
soit on prend tous les critères, soit on garde uniquement
ceux sélectionnés par les techniques de sélection d'attri-
buts. Dans ce cas, avec quels algorithmes d'apprentissage
ces derniers seront combinés.

Afin de prendre en compte les critères choisis par les al-
gorithmes de sélection dans des modèles d'apprentissage,
nous nous sommes basés sur les travaux de Hall et Holmes
[12]. Ils ont étudié l'efficacité de certaines techniques de
sélection d'attributs en les confrontant avec les techniques
d'apprentissage. Étant donné que la performance des cri-
tères diffère d'une technique d'apprentissage à une autre,
ils ont identifié les meilleures techniques de sélection d'at-
tributs permettant de retrouver les critères les plus perfor-
mants en fonction des techniques d'apprentissage à utiliser.
En se basant sur leur étude, nous avons utilisé les mêmes
couples des techniques d'apprentissage et des techniques
de sélection d'attributs :

— L'ensemble des critères sélectionnés par *CfsSubsetEval* (CFS) et *WrapperSubsetEval* (WRP) sont appris par le modèle Naïve Bayes.

— L'ensemble des critères sélectionnés par *ReliefFAttribut-eEval* (RLF) sont appris par le modèle J48 (C4.5 implementation).

— L'ensemble des critères sélectionnés par SVMAttribu-
teEval (SVM) sont appris par le modèle SVM à multi-
classes (appelé SMO function sur Weka).

Afin de vérifier la significativité des résultats par rapport
aux résultats de Naïve Bayes (considérés comme réfé-
rences - résultats de base), nous avons effectué le test de
<table><caption>TABLE 6 – Les critères sélectionnés par les algorithmes de sélection d'attributs</caption><thead><tr><th>Algorithm</th><th>Metric</th><th>c<sub>1</sub></th><th>c<sub>2</sub></th><th>c<sub>3</sub></th><th>c<sub>4</sub></th><th>c<sub>5</sub></th><th>c<sub>6</sub></th><th>c<sub>7</sub></th><th>c<sub>8</sub></th><th>c<sub>9</sub></th><th>c<sub>10</sub></th></tr></thead><tbody><tr><td>CfsSubsetEval</td><td>[Folds]</td><td>5</td><td>5</td><td>2</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>5</td><td>5</td></tr><tr><td>WrapperSubsetEval</td><td>[Folds]</td><td>4</td><td>4</td><td>4</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>5</td><td>5</td></tr><tr><td>ConsistencySubsetEval</td><td>[Folds]</td><td>5</td><td>5</td><td>4</td><td>2</td><td>1</td><td>1</td><td>2</td><td>2</td><td>5</td><td>5</td></tr><tr><td>FilteredSubsetEval</td><td>[Folds]</td><td>5</td><td>5</td><td>4</td><td>3</td><td>2</td><td>2</td><td>3</td><td>3</td><td>5</td><td>5</td></tr><tr><td></td><td>Moyenne</td><td>4.75</td><td>4.75</td><td>3.5</td><td>1.75</td><td>0.75</td><td>0.75</td><td>1.25</td><td>1.75</td><td>5</td><td>5</td></tr><tr><td>ChiSquaredAttributeEval</td><td>[Rank]</td><td>3</td><td>4</td><td>5</td><td>7</td><td>9</td><td>10</td><td>8</td><td>6</td><td>2</td><td>1</td></tr><tr><td>FilteredAttributeEval</td><td>[Rank]</td><td>4</td><td>3</td><td>5</td><td>7</td><td>9</td><td>10</td><td>8</td><td>6</td><td>2</td><td>1</td></tr><tr><td>GainRatioAttributeEval</td><td>[Rank]</td><td>3</td><td>4</td><td>5</td><td>7</td><td>9</td><td>10</td><td>8</td><td>6</td><td>2</td><td>1</td></tr><tr><td>InfoGainAttributeEval</td><td>[Rank]</td><td>3</td><td>4</td><td>5</td><td>7</td><td>9</td><td>10</td><td>8</td><td>6</td><td>1</td><td>2</td></tr><tr><td>OneRAttributeEval</td><td>[Rank]</td><td>4</td><td>3</td><td>5</td><td>7</td><td>9</td><td>10</td><td>8</td><td>6</td><td>2</td><td>1</td></tr><tr><td>ReliefFAttributeEval</td><td>[Rank]</td><td>4</td><td>3</td><td>6</td><td>8</td><td>9</td><td>10</td><td>7</td><td>5</td><td>1</td><td>2</td></tr><tr><td>SVMAttributeEval</td><td>[Rank]</td><td>4</td><td>3</td><td>5</td><td>7</td><td>9</td><td>10</td><td>8</td><td>6</td><td>2</td><td>1</td></tr><tr><td>SymmetricalUncertEval</td><td>[Rank]</td><td>3</td><td>4</td><td>5</td><td>7</td><td>9</td><td>10</td><td>8</td><td>6</td><td>2</td><td>1</td></tr><tr><td></td><td>Moyenne</td><td>3.5</td><td>3.5</td><td>5.12</td><td>7.12</td><td>9</td><td>10</td><td>7.87</td><td>5.87</td><td>1.75</td><td>1.25</td></tr></tbody></table>

<figure><img src="image_30.png" /><figcaption>FIGURE 3 – Processus d'apprentissage en utilisant les algorithmes de sélection</figcaption></figure>

<table><caption>TABLE 7 – Ensembles des critères sélectionnés</caption><thead><tr><th>Algorithmes de sélection</th><th>Critères</th></tr></thead><tbody><tr><td>CfsSubsetEval</td><td>c<sub>1</sub>, c<sub>2</sub>, c<sub>3</sub>, c<sub>9</sub>, c<sub>10</sub></td></tr><tr><td>WrapperSubsetEval</td><td>c<sub>1</sub>, c<sub>2</sub>, c<sub>3</sub>, c<sub>4</sub>, c<sub>8</sub>, c<sub>9</sub>, c<sub>10</sub></td></tr><tr><td>Other algorithms</td><td>c<sub>1</sub>, c<sub>2</sub>, c<sub>3</sub>, c<sub>4</sub>, c<sub>5</sub>, c<sub>6</sub>, c<sub>7</sub>, c<sub>8</sub>, c<sub>9</sub>, c<sub>10</sub></td></tr></tbody></table>

Student [33]. Nous avons attaché * (forte signification) et ** (très forte signification) aux résultats de la table 8 quand *p-value* <0.05 et *p-value* <0.01, respectivement.

La table 8 présente les résultats des trois algorithmes d'apprentissage des critères ressortis de l'étude utilisant les techniques de sélection d'attributs. Les résultats sont discutés ci-dessous pour chaque algorithme d'apprentissage.

**Résultats obtenus par Naïve Bayes (Baseline).** Les résultats en termes de précision obtenus en utilisant des algorithmes de sélection CFS et WRP avec NaïveBayes, sont

de 0.68 et 0.72, respectivement. Ces résultats dépassent ceux obtenus en utilisant tous les critères (précision : 0.60). En effet, nous avons enregistré des taux d'amélioration moyens de 14% et 20% pour Naïve Bayes en utilisant seulement les critères sélectionnés par CFS (0.68) et WRP (0.72), respectivement, par apport au résultat obtenu en utilisant tous les critères (0.60). Par conséquent, les approches d'apprentissage automatique peuvent donner une meilleure efficacité (précision) quand ils sont combinés avec des approches de sélection d'attributs. Les meilleures précisions
<table><caption>TABLE 8 – Les résultats de précision Weka pour les techniques d’apprentissage automatique</caption><thead><tr><th>Classifieurs</th><th>Classes (Niveaux d'intensité)</th><th>Techniques de sélection</th><th>Tous les critères</th></tr></thead><tbody><tr><td rowspan="10">Naïve Bayes (Baseline)</td><td>Very Low</td><td>0.81 (CFS)</td><td>0.71</td></tr><tr><td>Low</td><td>0.38 (CFS)</td><td>0.34</td></tr><tr><td>Strong</td><td>0.75 (CFS)</td><td>0.66</td></tr><tr><td>Very Strong</td><td>0.78 (CFS)</td><td>0.69</td></tr><tr><td>Moyenne</td><td>0.68 (CFS)</td><td>0.60</td></tr><tr><td>Very Low</td><td>0.86 (WRP)</td><td>0.72</td></tr><tr><td>Low</td><td>0.46 (WRP)</td><td>0.38</td></tr><tr><td>Strong</td><td>0.76 (WRP)</td><td>0.63</td></tr><tr><td>Very Strong</td><td>0.80 (WRP)</td><td>0.67</td></tr><tr><td>Moyenne</td><td>0.72 (WRP)</td><td>0.60</td></tr><tr><td rowspan="5">SVM</td><td>Very Low</td><td>0.88* (SVM)</td><td>0.88*</td></tr><tr><td>Low</td><td>0.72** (SVM)</td><td>0.72**</td></tr><tr><td>Strong</td><td>0.78* (SVM)</td><td>0.78*</td></tr><tr><td>Very Strong</td><td>0.90** (SVM)</td><td>0.90**</td></tr><tr><td>Moyenne</td><td>0.82** (SVM)</td><td>0.82**</td></tr><tr><td rowspan="5">J48</td><td>Very Low</td><td>0.97** (RLF)</td><td>0.97**</td></tr><tr><td>Low</td><td>0.92** (RLF)</td><td>0.92**</td></tr><tr><td>Strong</td><td>0.97** (RLF)</td><td>0.97**</td></tr><tr><td>Very Strong</td><td>0.98** (RLF)</td><td>0.98**</td></tr><tr><td>Moyenne</td><td>0.96** (RLF)</td><td>0.96**</td></tr></tbody></table>

sont obtenues pour les classes *Very Strong*, *Strong* et *Very Low*. Il semble que la classe *Low* est difficile à prédire avec Naïve Bayes, tout en utilisant à la fois les deux algorithmes de sélection CFS (0.38) et WRP (0.46).

**Résultats obtenus par SVM.** Les résultats obtenus par SVM en utilisant l’algorithme de sélection SVM*AttributeE-val*, où tous les critères ont été sélectionnés, sont meilleurs par rapport à ceux obtenus par Naïve Bayes. Nous avons enregistré des taux d’amélioration moyens de 21% et 14% pour SVM par rapport à Naïve Bayes en utilisant CFS et WRP, respectivement. Nous avons également remarqué que SVM était capable de prédire la classe *Low* avec une meilleure précision que celle fournie par Naïve Bayes. Même si l’algorithme SVM est un peu coûteux en termes de temps d’exécution par rapport à Naïve Bayes, il reste favoriser pour obtenir des résultats significatifs en termes de précision.

**Résultats obtenus par J48.** Les résultats confirment que l’arbre de décision J48 est le modèle le plus approprié, il prend en compte tous les critères de manière plus efficace que les autres configurations. Les taux d’améliora-

tion moyens par rapport à Naïve Bayes (en utilisant CFS et WRP) et SVM sont 41%, 33% et 17%, respectivement. En outre, les améliorations sont également fortement significatives pour chaque classe par rapport à SVM et Naïve Bayes. La classe *Low*, difficile à prédire avec les configurations précédentes, a été prédite avec une très forte précision de 92%. Comparées à Naïve Bayes (en utilisant CFS et WRP) et SVM, les améliorations enregistrées concernant la classe *Low* sont de 142%, 100% et 28%, respectivement.

Enfin, tous ces résultats expérimentaux montrent clairement que l’approche proposée permet de détecter de manière significative l’intensité de la contradiction dans les commentaires. Nous avons constaté que les résultats obtenus, par les deux algorithmes CFS et WRP, confirment l’hypothèse lancé par Hall et Holmes. C’est en effet les deux seuls cas pour lequel les résultats de précision obtenus avec la sélection d’attributs, soient 0.68 (CFS) et 0.72 (WRP), dépassent l’utilisation de tous les critères, 0.60 en termes de précision. Ces améliorations montrent l’intérêt de combiner les algorithmes de sélection d’attributs avec les modèles d’apprentissage. En outre, le modèle J48 a
donné les meilleures améliorations par rapport à toutes les autres configurations. Nous concluons que les ressources (cours) ayant des opinions plus diversifiées (commentaires positifs et négatifs), sont susceptibles d'avoir des contradictions avec différents niveaux d'intensité.

## 4 Conclusion

Cet article propose une approche supervisée exploitant un ensemble de critères permettant de prédire l'intensité de la contradiction, en attirant l'attention sur les aspects dans lesquels les utilisateurs ont des opinions contradictoires. L'intuition derrière l'approche proposée est que les notations et les sentiments associés aux commentaires sur un aspect spécifique peuvent être considérés comme des critères (ex. diversité des sentiments et des notations en fonction de l'écart-type) pour mesurer l'intensité de contradiction. L'évaluation expérimentale menée sur la collection issue de coursera.org montre que les critères NegCom, PosCom, VarNot et VarPol sont les plus fructueux pour prédire l'intensité de la contradiction. De plus, les algorithmes d'apprentissage basés sur les critères les plus pertinents selon les algorithmes de sélection d'attributs sont généralement mieux comparés à ceux obtenus lorsque les algorithmes de sélection d'attributs sont ignorés. L'algorithme J48 apporte les meilleurs résultats par rapport à Naïve Bayes et SVM. Enfin, nous notons que nous sommes conscients que l'évaluation de notre approche est encore limitée. La principale faiblesse de notre approche est sa dépendance à la qualité des modèles de sentiments et d'extraction d'aspect. D'autres expérimentations à plus grande échelle sur d'autres types de collections sont également envisagées. Ceci étant même avec ces éléments simples, les premiers résultats obtenus nous encouragent à investir davantage cette piste.

## Références

[1] Ahmed Hassan Awadallah, Amjad Abu-Jbara, and Dragomir R. Radev. Detecting subgroups in online discussions by modeling positive and negative relations among participants. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, EMNLP-CoNLL 2012, July 12-14, 2012, Jeju Island, Korea, pages 59–70, 2012.

[2] Ismail Badache and Mohand Boughanem. Harnessing social signals to enhance a search. In Proceedings of the 2014 IEEE/WIC/ACM International Joint Conferences on Web Intelligence (WI) and Intelligent Agent Technologies (IAT) - Volume 01, WI-IAT '14, pages 303–309, Washington, DC, USA, 2014.

[3] Ismail Badache and Mohand Boughanem. Emotional social signals for search ranking. In Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '17, pages 1053–1056, New York, NY, USA, 2017. ACM.

[4] Ismail Badache and Mohand Boughanem. Fresh and diverse social signals: Any impacts on search? In Proceedings of the 2017 Conference on Conference Human Information Interaction and Retrieval, CHIIR '17, pages 155–164, New York, NY, USA, 2017. ACM.

[5] Ismail Badache, Sébastien Fournier, and Adrian-Gabriel Chifu. Finding and quantifying temporal-aware contradiction in reviews. In Information Retrieval Technology - 13th Asia Information Retrieval Societies Conference, AIRS 2017, Jeju Island, South Korea, November 22-24, 2017, Proceedings, pages 167–180, 2017.

[6] Ismail Badache, Sébastien Fournier, and Adrian-Gabriel Chifu. Harnessing ratings and aspect-sentiment to estimate contradiction intensity in temporal-related reviews. In Knowledge-Based and Intelligent Information & Engineering Systems : Proceedings of the 21st International Conference KES-2017, Marseille, France, 6-8 September 2017., pages 1711–1720, 2017.

[7] Ramnath Balasubramanyan, William W. Cohen, Douglas Pierce, and David P. Redlawsk. Modeling polarizing topics: When do different political communities respond differently to the same news? In Proceedings of the Sixth International Conference on Weblogs and Social Media, Dublin, Ireland, June 4-7, 2012, 2012.

[8] Jacob Cohen. A coefficient of agreement for nominal scales. Educational and psychological measurement, 20(1):37–46, 1960.

[9] Marie-Catherine de Marneffe, Anna N. Rafferty, and Christopher D. Manning. Finding contradictions in text. In ACL 2008, Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics, June 15-20, 2008, Columbus, Ohio, USA, pages 1039–1047, 2008.

[10] Shiri Dori-Hacohen and James Allan. Automated controversy detection on the web. In Advances in Information Retrieval - 37th European Conference on IR Research, ECIR 2015, Vienna, Austria, March 29 - April 2, 2015. Proceedings, pages 423–434, 2015.

[11] Kiran Garimella, Gianmarco De Francisci Morales, Aristides Gionis, and Michael Mathioudakis. Quantifying controversy in social media. In Proceedings of the Ninth ACM International Conference on Web Search and Data Mining, San Francisco, CA, USA, February 22-25, 2016, pages 33–42, 2016.

[12] Mark A. Hall and Geoffrey Holmes. Benchmarking attribute selection techniques for discrete class data mining. IEEE Trans. Knowl. Data Eng., 15(6):1437–1447, 2003.

[13] Hussam Hamdan, Patrice Bellot, and Frédéric Béchet. Lsislif: CRF and logistic regression for opinion target extraction and sentiment polarity analysis.
In Proceedings of the 9th International Workshop on Semantic Evaluation, SemEval@NAACL-HLT, Colorado, USA, June 4-5, 2015, pages 753–758, 2015.

[14] Sanda M. Harabagiu, Andrew Hickl, and V. Finley Lacatusu. Negation, contrast and contradiction in text processing. In Proceedings, The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, July 16-20, 2006, Boston, Massachusetts, USA, pages 755–762, 2006.

[15] Amal Htait, Sébastien Fournier, and Patrice Bellot. LSIS at semeval-2016 task 7 : Using web search engines for english and arabic unsupervised sentiment intensity prediction. In Proceedings of the 10th International Workshop on Semantic Evaluation, SemEval@NAACL-HLT 2016, San Diego, CA, USA, June 16-17, 2016, pages 469–473, 2016.

[16] Minqing Hu and Bing Liu. Mining and summarizing customer reviews. In Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Seattle, Washington, USA, August 22-25, 2004, pages 168–177, 2004.

[17] Melanie Imhof, Ismail Badache, and Mohand Boughanem. Multimodal social book search. In Working Notes of CLEF 2015 - Conference and Labs of the Evaluation forum, Toulouse, France, September 8-11, 2015., 2015.

[18] Myungha Jang and James Allan. Improving automated controversy detection on the web. In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, SIGIR 2016, Pisa, Italy, July 17-21, 2016, pages 865–868, 2016.

[19] Myungha Jang, John Foley, Shiri Dori-Hacohen, and James Allan. Probabilistic approaches to controversy detection. In Proceedings of the 25th ACM International Conference on Information and Knowledge Management, CIKM 2016, Indianapolis, IN, USA, October 24-28, 2016, pages 2069–2072, 2016.

[20] Suin Kim, Jianwen Zhang, Zheng Chen, Alice H. Oh, and Shixia Liu. A hierarchical aspect-sentiment model for online reviews. In Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, July 14-18, 2013, Bellevue, Washington, USA., 2013.

[21] Moshe Looks, Marcello Herreshoff, DeLesley Hutchins, and Peter Norvig. Deep learning with dynamic computation graphs. CoRR, abs/1702.02181, 2017.

[22] Julian J. McAuley, Rahul Pandey, and Jure Leskovec. Inferring networks of substitutable and complementary products. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, August 10-13, 2015, pages 785–794, 2015.

[23] Saif Mohammad, Svetlana Kiritchenko, and Xiaodan Zhu. Nrc-canada : Building the state-of-the-art in sentiment analysis of tweets. In Proceedings of the 7th International Workshop on Semantic Evaluation, SemEval@NAACL-HLT 2013, Atlanta, Georgia, USA, June 14-15, 2013, pages 321–327, 2013.

[24] Arjun Mukherjee and Bing Liu. Mining contents from discussions and debates. In The 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '12, Beijing, China, August 12-16, 2012, pages 841–849, 2012.

[25] Bo Pang, Lillian Lee, and Shivakumar Vaithyanathan. Thumbs up ? sentiment classification using machine learning techniques. In Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing, EMNLP 2002, Philadelphia, PA, USA, July 6-7, 2002, 2002.

[26] ES Pearson and MA Stephens. The ratio of range to standard deviation in the same normal sample. Biometrika, 51(3/4) :484–487, 1964.

[27] Ana-Maria Popescu and Marco Pennacchiotti. Detecting controversial events from twitter. In Proceedings of the 19th ACM Conference on Information and Knowledge Management, CIKM 2010, Toronto, Ontario, Canada, October 26-30, 2010, pages 1873–1876, 2010.

[28] Soujanya Poria, Erik Cambria, Lun-Wei Ku, Chen Gui, and Alexander F. Gelbukh. A rule-based approach to aspect extraction from product reviews. In Proceedings of the Second Workshop on Natural Language Processing for Social Media, SocialNLP@COLING, Dublin, Ireland, August 24, 2014, pages 28–37, 2014.

[29] Minghui Qiu, Liu Yang, and Jing Jiang. Modeling interaction features for debate side clustering. In 22nd ACM International Conference on Information and Knowledge Management, CIKM'13, San Francisco, CA, USA, October 27 - November 1, 2013, pages 873–878, 2013.

[30] J. Ross Quinlan. C4.5 : Programs for Machine Learning. Morgan Kaufmann, 1993.

[31] Alec Radford, Rafal Józefowicz, and Ilya Sutskever. Learning to generate reviews and discovering sentiment. CoRR, abs/1704.01444, 2017.

[32] Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 conference on empirical methods in natural language processing, volume 1631, pages 1631–1642, 2013.

[33] Student. The probable error of a mean. Biometrika, 6(1) :1–25, 1908.
[34] Ivan Titov and Ryan T. McDonald. Modeling online reviews with multi-grain topic models. In Proceedings of the 17th International Conference on World Wide Web, WWW 2008, Beijing, China, April 21-25, 2008, pages 111–120, 2008.

[35] Mikalai Tsytsarau, Themis Palpanas, and Malú Castellanos. Dynamics of news events and social media reaction. In The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '14, New York, NY, USA - August 24 - 27, 2014, pages 901–910, 2014.

[36] Mikalai Tsytsarau, Themis Palpanas, and Kerstin DeNecke. Scalable discovery of contradictions on the web. In Proceedings of the 19th International Conference on World Wide Web, WWW 2010, Raleigh, North Carolina, USA, April 26-30, 2010, pages 1195–1196, 2010.

[37] Mikalai Tsytsarau, Themis Palpanas, and Kerstin DeNecke. Scalable detection of sentiment-based contradictions. DiversiWeb, WWW, 1:9–16, 2011.

[38] Peter D. Turney. Thumbs up or thumbs down? semantic orientation applied to unsupervised classification of reviews. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, July 6-12, 2002, Philadelphia, PA, USA., pages 417–424, 2002.

[39] Jan Vosecky, Kenneth Wai-Ting Leung, and Wilfred Ng. Searching for quality microblog posts: Filtering and ranking based on content analysis and implicit links. In Database Systems for Advanced Applications - 17th International Conference, DASFAA 2012, Busan, South Korea, April 15-19, 2012, Proceedings, Part I, pages 397–413, 2012.

[40] Lu Wang and Claire Cardie. A piece of my mind: A sentiment analysis approach for online dispute detection. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, ACL 2014, June 22-27, 2014, Baltimore, MD, USA, Volume 2, pages 693–699, 2014.

[41] Lu Wang, Hema Raghavan, Claire Cardie, and Vittorio Castelli. Query-focused opinion summarization for user-generated content. In COLING 2014, 25th International Conference on Computational Linguistics, August 23-29, 2014, Dublin, Ireland, pages 1660–1669, 2014.

[42] Show-Jane Yen and Yue-Shi Lee. Under-sampling approaches for improving prediction of the minority class in an imbalanced dataset. pages 731–740, 2006.

[43] Quan Yuan, Gao Cong, and Nadia Magnenat-Thalmann. Enhancing naive bayes with various smoothing methods for short text classification. In Proceedings of the 21st World Wide Web Conference, WWW 2012, Lyon, France, April 16-20, 2012 (Companion Volume), pages 645–646, 2012.
<figure><img src="image_31.png" /></figure>
# Sur le Gradient de la Politique pour les Systèmes Multi-Agents Coopératifs

G. Bono<fnref n="1" /> J. Dibangoye<fnref n="1" /> L. Matignon<fnref n="1" />,<fnref n="2" /> F. Pereyron<fnref n="3" /> O. Simonin<fnref n="1" />

guillaume.bono@inria.fr

## Résumé

L'apprentissage par renforcement (RL) pour les processus décisionnels de Markov partiellement observables décentralisés (Dec-POMDPs) accuse un certain retard par rapport aux progrès spectaculaires du RL mono-agent. Ceci s'explique en partie par un certain nombre d'hypothèses valables dans le cadre mono-agent, mais invalides dans les systèmes multi-agents. Pour combler ce retard, nous explorons les fondements mathématiques des méthodes par ascension du gradient de la politique dans le paradigme de l'entraînement centralisé pour un contrôle décentralisé (CTDC). Dans ce paradigme, l'apprentissage peut avoir lieu de façon centralisée tout en gardant la contrainte d'une exécution décentralisée. En partant de cette intuition, nous établissons dans ce document une extension multi-agents du théorème du gradient de la politique et du théorème de compatibilité des fonctions d'approximation de la valeur. Nous en tirons des méthodes « acteur critique » (AC) qui parviennent (i) à estimer le gradient de la politique à partir d'expériences collectives mais aussi (ii) à préserver le contrôle décentralisé du système à l'exécution. Nos expérimentations montrent que nos méthodes ne souffrent pas de la comparaison avec les techniques standard en RL sur un ensemble de bancs de test de la littérature.

## Mots Clef

Contrôle décentralisé et stochastique – Processus Décisionnel de Markov Partiellement Observable – Systèmes Multi-Agents – Méthodes Acteur Critique

## Abstract

Reinforcement Learning (RL) for decentralized partially observable Markov decision processes (Dec-POMDPs) is lagging behind the spectacular breakthroughs of single-agent RL. That is because assumptions that hold in single-agent settings are often obsolete in decentralized multi-agent systems. To tackle this issue, we investigate the foundations of policy gradient methods within the centralized training for decentralized control (CTDC) paradigm. In

this paradigm, learning can be accomplished in a centralized manner while each agent can still execute its policy independently at deployment. Using this insight, we establish a new policy gradient theorem and compatible function approximations for decentralized multi-agent systems. Resulting actor critic methods preserve the decentralized control at the execution phase, but can also estimate the policy gradient from collective experiences guided by a centralized critic at the training phase. Experiments demonstrate our policy gradient methods compare favorably against standard RL techniques in benchmarks from the literature.

## Keywords

Decentralized and Stochastic Control – Partially Observable Markov Decision Processes – Multi-Agent Systems – Actor Critic Methods.

## 1 Introduction

Ces dernières années, la capacité d'agents artificiels à apprendre des comportements par eux-mêmes en interagissant avec leur environnement s'est développée de façon spectaculaire [19, 20], promettant de grandes avancées dans la société et l'industrie. Une partie de ces progrès peut être imputée à l'apprentissage par renforcement (RL) mono-agent, particulièrement le RL profond. Il s'agit d'une branche de l'apprentissage automatique où le monde dans lequel évolue l'agent est décrit comme un processus décisionnel de Markov (MDP) [25]. Si d'autres agents interviennent, ils sont intégrés à cette description du monde, et les hypothèses considérées pendant l'apprentissage et l'exécution sont identiques. Dans ce modèle, les méthodes par ascension du gradient de la politique et les algorithmes acteur critique (AC) et acteur critique naturel (NAC) ont eu un certain succès, avec de bonnes garanties de convergence [1, 7, 13, 26]. Ces méthodes cherchent directement dans un espace de politiques stochastiques paramétrées en ajustant la valeur des paramètres dans la direction du gradient de la politique. Malheureusement, les adaptations de ces méthodes au cadre multi-agents se sont focalisées soit sur des agents indépendants [22, 29], soit sur des systèmes

<footnote n="1">¹ Univ Lyon, INSA Lyon, INRIA, CITI, F-69621 Villeurbanne, France</footnote>

<footnote n="2">² Univ Lyon, Université Lyon 1, LIRIS, CNRS, UMR5205, Villeurbanne, F-69622, France</footnote>

<footnote n="3">³ Volvo Group, Advanced Technology and Research</footnote>
où la connaissance du monde est commune [32]. Ces derniers peuvent en fait être ramenés à des systèmes mono-agent.

Au lieu de cela, nous considérons dans cet article un système multi-agents coopératif où l’apprentissage est centralisé, mais où l’exécution reste décentralisée. Grâce à ce paradigme, nous pouvons relâcher la contrainte de contrôle décentralisé pendant la phase d’apprentissage. Nous préservons néanmoins l’indépendance des politiques apprises pour leur exécution. Dans de nombreux cas d’application des systèmes multi-agents, les conditions lors de l’entraînement ne sont pas aussi strictes que les conditions à l’exécution : pendant les répétitions d’une pièce de théâtre, les acteurs peuvent lire le script, prendre des pauses ou échanger avec le metteur en scène ; pour gagner un match de football, les joueurs appliquent des tactiques développées avec leur entraîneur bien avant la rencontre, etc. Il est donc naturel de se demander si les méthodes d’ascension du gradient de la politique peuvent tirer profit de ce paradigme.

Le paradigme CTDC a été utilisé avec succès à des méthodes de planification pour les MDP partiellement observables décentralisés (Dec-POMDP), un modèle de choix pour la prise de décision séquentielle par un ensemble d’agents coopérant à la poursuite d’un objectif commun [4, 9, 10, 11, 14, 21, 27, 28]. Dans la littérature de la théorie des jeux, les Dec-POMDP sont des jeux stochastiques partiellement observables à gains identiques. Les Dec-POMDP généralisent d’autres modèles multi-agents collaboratifs, comme les MDP multi-agents [6], ou les jeux stochastiques à gains identiques [24] par exemple. L’hypothèse principale qui rend les Dec-POMDP fondamentalement différents et plus complexes que les MDP pourrait n’être pertinente que pendant la phase d’exécution : les agents n’ont pas accès au véritable état du monde, et ne peuvent pas transmettre aux autres agents leurs observations locales bruitées. Rien n’empêche les agents de partir their informations locales pendant l’entraînement à la condition qu’à l’exécution, ils ne basent leurs décisions que sur leurs expériences individuelles. De façon assez surprenante, cette intuition a été relativement peu exploitée, et le traitement formel du paradigme CTDC a fait l’objet de peu d’attention au sein de la communauté RL [17]. Quand cet entraînement centralisé a lieu en laboratoire ou se base sur un simulateur, il est possible d’exploiter l’information disponible plus riche que celle collectée lors de l’exécution, par exemple les états cachés, les informations locales d’autres agents, etc. Même si les travaux récents en RL multi-agents – et RL profond – partent de ce paradigme pour développer des méthodes spécifiques à certains domaines [12, 13, 18], les fondements théoriques du RL multi-agents décentralisé en sont encore à leurs balbutiements.

Cet article explore les fondements théoriques des méthodes du gradient de la politique dans le paradigme CTDC. Dans ce paradigme, les algorithmes acteur critique peuvent être adaptées pour entraîner plusieurs acteurs (ou politiques)

indépendants guidés par un critique centralisé (c.à.d. une approximation de la fonction de valeur état-action) [12]. Les méthodes de cette famille diffèrent seulement par la façon dont est représenté et mis à jour ce critique centralisé. Le résultat principal de ce papier est une généralisation du théorème du gradient de la politique et du théorème de compatibilité des approximations de la valeur pour les Dec-POMDP en s’inspirant de leurs équivalents en MDP. Nous montrons en particulier que le critique centralisé est compatible avec le gradient de la politique s’il se décompose en une somme de critiques individuels, eux-mêmes combinais linéaires des caractéristiques de la politique individuelle correspondante. De plus, nous dérivons des règles de mise à jour qui ajustent les paramètres des critiques individuels dans la direction du gradient du critique centralisé. Nos expérimentations tendent à montrer que notre approach est compétitive par rapport aux techniques issues des paradigmes classiques du RL sur un jeu de bancs de test de la littérature.

Le reste de l’article est structuré de la façon suivante. La Section 2 revient sur la définition formelle des MDP partiellement observables (POMDP) et Dec-POMDP, et rappelle un ensemble de propriétés pertinentes. Dans la Section 3, nous passons en revue les méthodes du gradient de la politique pour les POMDP (mono-agent), puis nous poursuivons par une analyse des travaux les utilisant dans le cadre multi-agents coopératif en Section 4. La Section 5 présente nos résultats sur les fondements théoriques des méthodes du gradient de la politique pour les Dec-POMDP, et en dérive des algorithmes acteur-critique. Nous concluons par la présentation et l’analyse de nos résultats empiriques dans la Section 6

## 2 Contexte

### 2.1 MDP partiellement observables

Considérons un agent jouant le rôle de coordinateur central chargé de contrôler le comportement d'un processus décisionnel de Markov partiellement observable (POMDP) au cours de son évolution dans le temps. Ce cadre sert souvent à formaliser les systèmes multi-agents coopératifs dans lesquels tous les agents se transmettent explicitement et instantanément leurs observations bruitées.

**Définition 1.** Soit $M_1 \doteq (\mathcal{X}, \mathcal{U}, \mathcal{Z}, p, R, T, s_0, \gamma)$ un POMDP. On note $X_t, U_t, Z_t$ et $R_t$ les variables aléatoires qui prennent respectivement leurs valeurs dans $\mathcal{X}, \mathcal{U}, \mathcal{Z}$ et $\mathbb{R}$ et qui décrivent : l'état de l'environnement, les commandes appliquées par l'agent, les observations et le signal de récompense qu'il a reçu à l'instant $t = 0, 1, \dots, T$. La dynamique de l'environnement est modélisée par les probabilités de transition et d'observation $p(x', z|x, u) \doteq \mathbb{P}(X_{t+1} = x', Z_{t+1} = z|X_t = x, U_t = u)$. $R(x, u) \doteq \mathbb{E}[R_{t+1}|X_t = x, U_t = u]$ dénote l'espérance de la récompense immédiate, $s_0(x) = \mathbb{P}(X_0 = x)$ la distribution initiale sur les états, et $\gamma \in [0, 1]$ le facteur d'amortissement des récompenses futures.
On définit récursivement l'historique $o_t \doteq (o_{t-1}, u_{t-1}, z_t)$ avec $o_0 \doteq \emptyset$, contenant la séquence de commandes et d'observations que l'agent a effectuées et perçues jusqu'au temps $t$. On note $\mathcal{O}_t$ l'ensemble des historiques potentiellement expérimentés par l'agent au temps $t$.

**Définition 2.** L'agent sélectionne à chaque instant une commande $u_t$ selon une politique paramétrée $\pi \doteq (a_0, a_1, \dots, a_T)$, où $a_t(u_t|o_t) \doteq \mathbb{P}(u_t|o_t; \theta_t)$ dénote la règle de décision appliquée au temps $t$, de paramètres $\theta_t \in \mathbb{R}^{\ell_t}$ avec $\ell_t \ll |\mathcal{O}_t|$, $\forall t \in \{0 \dots T\}$.

En pratique, la politique peut être construite comme par exemple un réseau de neurone profond, un contrôleur à états finis ou encore une simple structure linéaire normalisée par softmax. De telles représentations de la politique reposent sur différentes descriptions parfois incomplètes des historiques, appelées états internes de l'agent. Notons que si le modèle est connu ou estimé, il peut servir à calculer une forme d'états internes appelés croyances qui constituent une statistique exhaustive de l'historique [2]. Si on note $b^o \doteq \mathbb{P}(X_t|O_t = o)$ la croyance courante induit par l'historique $o$, avec une croyance initial $b^\emptyset \doteq s_0$, alors, après avoir effectué la commande $u \in \mathcal{U}$ et perçu l'observation $z \in \mathcal{Z}$, la nouvelle croyance se calcule ainsi : $\forall x' \in \mathcal{X}$,

$$b^{o,u,z}(x') \doteq \mathbb{P}(X_{t+1} = x'|O_{t+1} = (o, u, z)) \\ \propto \sum_{x \in \mathcal{X}} p(x', z|x, u)b^o(x).$$

Par conséquent, utiliser les croyances au lieu des historiques dans la description des politiques préserve la capacité à agir de façon optimale, tout en réduisant significativement l'empreinte mémoire de la représentation de l'état interne. Cela permet aussi de se focaliser sur des politiques stationnaires, particulièrement intéressantes dans le cadre à horizon infini ($T = \infty$). Une politique $\pi$ est dite stationnaire si $a_0 = a_1 = \dots = a$, ou dit autrement $\theta_0 = \theta_1 = \dots = \theta$ ; sinon, elle est non stationnaire.

En évoluant dans l'environnement guidé par la politique $\pi$, l'agent génère une trajectoire composée de récompenses, d'observations, de commandes et d'états $\omega_{t:T} \doteq (r_{t:T}, x_{t:T}, z_{t:T}, u_{t:T})$. Chaque trajectoire rapporte une récompense cumulée $R(\omega_{t:T}) \doteq \gamma^0 r_t + \dots + \gamma^{T-t} r_T$. Les meilleures politiques sont celles qui produisent à partir de $s_0$ les meilleures récompense cumulée en espérance :

$$J(s_0; \theta_{0:T}) \doteq \mathbb{E}_{\Omega_{0:T} \sim \mathbb{P}(\cdot | \pi, M_1)} [R(\Omega_{0:T})] \\ = \sum_{\omega_{0:T}} \mathbb{P}(\omega_{0:T} | \pi, M_1) R(\omega_{0:T}) \quad (1)$$

où on note $\mathbb{P}(\omega_{0:T}|\pi, M_1)$ la probabilité de générer la trajectoire $\omega_{0:T}$ en suivant $\pi$. Trouver le meilleur moyen pour l'agent d'interagir avec $M_1$ consiste à trouver le vecteur de paramètres $\theta_{0:T}^*$ solution de : $\theta_{0:T}^* \in \arg\max_{\theta_{0:T}} J(s_0; \theta_{0:T})$.

Il s'avère judicieux de subdiviser la performance d'une politique pour exploiter sa structure sous-jacente : en effet, les performances d'une politique $\pi$ à partir du temps $t$ ne dépendent des commandes antérieures à $t$ qu'à travers les états et historiques courants. Cela nous conduit à définir les fonctions de valeur, Q-valeur et avantage de $\pi$. La fonction de Q-valeur de $\pi$ est défini par :

$$Q_t^\pi : (x, o, u) \mapsto \mathbb{E}[R(\Omega_{t:T})] \quad (2)$$

où $\Omega_{t:T} \sim \mathbb{P}(\cdot | X_t = x, O_t = o, U_t = u; \pi, M_1)$. $Q_t^\pi(x, o, u)$ est l'espérance sur la récompense cumulée en exécutant au temps $t$ la commande $u$ à partir d'un état $x$ et d'un historique $o$, puis en choisissant par $\pi$ les futures commandes à partir de $t+1$. La fonction de valeur de $\pi$ est donnée par :

$$V_t^\pi : (x, o) \mapsto \mathbb{E}_{U \sim a_t(\cdot | o)} [Q_t^\pi(x, o, U)] \quad (3)$$

où $V_t^\pi(x, o)$ est l'espérance sur la récompense cumulée en suivant la politique $\pi$ à partir du temps $t$ depuis un état $x$ et un historique $o$. Enfin, la fonction avantage de $\pi$ est simplement la différence des deux :

$$A_t^\pi : (x, o, u) \mapsto Q_t^\pi(x, o, u) - V_t^\pi(x, o) \quad (4)$$

où $A_t^\pi(x, o, u)$ est donc l'avantage relatif à exécuter $u$ plutôt que de suivre $\pi$ au temps $t$ depuis un état $x$ et un historique $o$, puis en revenant à la politique $\pi$ par la suite. La propriété qui rend ces fonctions intéressantes est qu'elles vérifient la relation de récurrence suivante.

**Lemme 1** (Équations de Bellman [3]). $\forall t = 0, 1, \dots, T$, $\forall x \in \mathcal{X}, o \in \mathcal{O}_t, u \in \mathcal{U}$,

$$Q_t^\pi(x, o, u) = R(x, u) + \gamma \mathbb{E}[Q_{t+1}^\pi(X', O', U')] \quad (5)$$

$$\text{où } (X', O', U') \sim \mathbb{P}(\cdot | X_t = x, O_t = o, U_t = u; a_{t+1}, M_1)$$

(5) établit une relation temporelle entre les différents $V_{0:T}^\pi$, $Q_{0:T}^\pi$ et $A_{0:T}^\pi$, mais aussi $J(s_0; \theta_{0:T})$ :

$$J(s_0; \theta_{0:T}) = \mathbb{E}_{X_0 \sim \mathbb{P}(\cdot | s_0)} [V_0^\pi(X_0, o_0 = \emptyset)]. \quad (6)$$

Jusqu'à présent, nous nous sommes concentrés sur les systèmes contrôlés par un unique agent. La suite généralise aux systèmes décentralisés dans lesquels plusieurs agents doivent coopérer pour contrôler le même système.

## 2.2 POMDP Décentralisés

Considérons à présent un contexte où $n$ agents coopèrent pour influencer l'évolution d'un système décrit comme un POMDP, mais où aucun d'eux ne peut percevoir l'état du monde, ni communiquer ses observations bruitées aux autres.

**Définition 3.** Un Dec-POMDP $M_n \doteq (\mathcal{I}_n, \mathcal{X}, \mathcal{U}, \mathcal{Z}, p, R, T, \gamma, s_0)$ est défini tel que : $i \in \mathcal{I}_n$ dénote l'indice du ième agent impliqué dans le processus ; $\mathcal{X}, \mathcal{U}, \mathcal{Z}, p, R, T, \gamma$ et $s_0$ sont définis tels que dans
$M_1$, à la particularité que $\mathcal{U}$ et $\mathcal{Z}$ se décomposent en ensembles de commandes et d'observations individuelles $\mathcal{U} = \mathcal{U}^1 \times \dots \times \mathcal{U}^n$ et $\mathcal{Z} = \mathcal{Z}^1 \times \dots \times \mathcal{Z}^n$, avec $\mathcal{U}^i$ et $\mathcal{Z}^i$ l'ensemble des commandes et des observations propres au ième agent.

On appelle historique individuel de l'agent $i \in \mathcal{I}_n$ la séquence de commandes et d'observations individuelles exécutées et perçues jusqu'au temps $t = 0, 1, \dots, T$, notée $o_t^i = (o_{t-1}^i, u_{t-1}^i, z_t^i)$ avec $o_0^i = \emptyset$. On note $O_t^i$, l'ensemble des historiques individuels possible de l'agent $i$ au temps $t$.

**Définition 4.** L'agent $i \in \mathcal{I}_n$ sélectionne la commande $u_t^i$ au temps $t$ selon une politique paramétrée $\pi^i = (a_0^i, a_1^i, \dots, a_T^i)$ où $a_t^i(u_t^i|o_t^i) \doteq \mathbb{P}(u_t^i|o_t^i; \theta_t^i)$ est la règle de décision appliquée au temps $t$, de paramètres $\theta_t^i \in \mathbb{R}^{\ell_t^i}$, avec $\ell_t^i \ll |O_t^i|$.

De même que dans $M_1$, le nombre d'historiques individuels possibles grandit de façon exponentiel à chaque pas de temps. À ce jour, la seule statistique exhaustive connue pour les historiques individuels repose sur les états d'occupation définis par : $s_t(x, o) \doteq \mathbb{P}(x, o|\theta_{0:t}^{1:n})$, $\forall x \in \mathcal{X}, \forall o \in O_t$. L'état d'occupation individuel induit par l'historique $o^i \in O_t^i$ est une distribution de probabilité conditionnelle : $s_t^i(x, o^{-i}) \doteq \mathbb{P}(x, o^{-i}|o^i, s_t)$, où $o^{-i}$ dénote l'historique joint des $n-1$ agents autres que $i$. Il est très difficile d'apprendre à projeter les historiques individuels vers des états internes proches des états d'occupation individuels, ce qui limite la capacité des algorithmes d'apprentissage à trouver des politiques optimales dans un temps raisonnable pour $M_n$. On peut alors se focaliser sur des politiques stationnaires pour lesquelles l'espace des historiques est projeté sur un ensemble fini d'états internes $\zeta \doteq (\zeta^1, \dots, \zeta^n)$, qui sont des représentations – souvent à pertes – des états d'occupations individuels. Les $\zeta^i$ peuvent par exemple être les nœuds d'un contrôleur à états finis, ou encore les états internes d'un réseau de neurone récurrent (RNN). On note $\psi(\zeta'|\zeta, u, z)$ la probabilité de transition d'un état interne joint $\zeta$ à l'état interne suivant $\zeta'$ en fonction de la dernière commande effectuée $u$ et de l'observation reçue $z$. Cette loi de transition est décomposable en lois individuelles $\psi^i(\zeta'^i|\zeta^i, u^i, z^i)$. Dans la suite de cet article, nous considérerons la loi $\psi$ fixée à priori, même si en général, elle fait partie de la politique et possède des paramètres à optimiser. Résoudre $M_n$ revient à trouver une politique jointe $\pi \doteq (\pi^1, \dots, \pi^n)$ – un tuple de $n$ politiques individuelles – qui donne la meilleure récompense cumulée à partir d'une distribution d'états initiaux $s_0$. Autrement dit, $\theta_{0:T}^{*,1:n} \in \arg\max_{\theta_{0:T}^{1:n}} J(s_0; \theta_{0:T}^{1:n})$, avec

$$ 
\begin{aligned}
J(s_0; \theta_{0:T}^{1:n}) &\doteq \mathbb{E}_{\Omega_{0:T} \sim \mathbb{P}(\cdot|\pi, M_n)} [R(\Omega_{0:T})] \\
&= \sum_{\omega_{0:T}} \mathbb{P}(\omega_{0:T}|\pi, M_n) R(\omega_{0:T})
\end{aligned} 
\quad (7) 
$$

où $\mathbb{P}(\omega_{0:T}|\pi, M_n)$ est la probabilité de générer la trajetoire jointe $\omega_{0:T}$ en suivant la politique $\pi$. Étant donné une politique jointe $\pi, M_n$ hérite des mêmes définitions que $M_1$, en particulier pour les fonctions $V_{0:T}^{\pi}, Q_{0:T}^{\pi}$ et $A_{0:T}^{\pi}$.

# 3 Gradient de la politique

Dans cette section, nous passons en revue la littérature des méthodes du gradient de la politique pour le contrôle centralisé de systèmes mono-agent. Dans ce contexte, l'approche du gradient de la politique se base sur des algorithmes centralisés qui cherchent à optimiser la récompense cumulée directement dans l'espace des paramètres de la politique $\theta_{0:T}$. Bien que nous n'abordions ici que des politiques non stationnaires, les méthodes citées peuvent facilement être étendues au cas de politiques stationnaires pour lesquelles $a_t = a$ pour tout $t$. En considérant que la politique $\pi$ est différentiable par rapport à ses paramètres $\theta_{0:T}$, l'algorithme met à jour $\theta_{0:T}$ dans la direction du gradient :

$$ \Delta\theta_{0:T} = \alpha \frac{\partial J(s_0; \theta_{0:T})}{\partial \theta_{0:T}} \quad (8) $$

avec $\alpha$ un taux d'apprentissage. En itérant sur cette règle de mise à jour, pour peu que l'estimation du gradient soit correcte, $\theta_{0:T}$ converge vers un optima local. Malheureusement, estimer correctement le gradient peut se révéler impossible. Pour dépasser cette difficulté, le gradient peut être remplacé par une estimation non biaisée, ce qui revient à restreindre (8) à un gradient stochastique :

$$ \Delta\theta_{0:T} = \alpha R(\omega_{0:T}) \frac{\partial \log \mathbb{P}(\omega_{0:T}|\pi, M_1)}{\partial \theta_{0:T}} \quad (9) $$

On calcule $\frac{\partial}{\partial \theta_{0:T}} \log \mathbb{P}(\omega_{0:T}|\pi, M_1)$ sans connaissance à priori de la distribution sur les trajectoires $\mathbb{P}(\omega_{0:T}|\pi, M_1)$. En effet, les propriétés d'indépendance conditionnelle du processus donnent :

$$ \mathbb{P}(\omega_{0:T}|\pi, M_1) \doteq s_0(x_0) \prod_{t=0}^{T} p(x_{t+1}, z_{t+1}|x_t, u_t) a_t(u_t|o_t) \quad (10) $$

ce qui implique :

$$ \frac{\partial \log \mathbb{P}(\omega_{0:T}|\pi, M_1)}{\partial \theta_{0:T}} = \sum_{t=0}^{T} \frac{\partial \log a_t(u_t|o_t)}{\partial \theta_t} \quad (11) $$

## 3.1 Méthode du rapport de vraisemblance

Les méthodes du rapport de vraisemblances, e.g., Reinforce [30], exploitent la séparabilité du vecteur de paramètres $\theta_{0:T}$, qui mènent à la règle de mise à jour suivante : $\forall t = 0, 1, \dots, T$

$$ \Delta\theta_t = \alpha \mathbb{E}_D \left[ R(\omega_{0:T}) \frac{\partial \log a_t(u_t|o_t)}{\partial \theta_t} \right] \quad (12) $$

où $\mathbb{E}_D[\cdot]$ dénote une approximation de l'espérance par une moyenne empirique prise sur un ensemble de trajectoires $\mathcal{D} = \{\omega_{0:T,j}\}_{1\le j\le m}$ échantillonnées à partir de $\pi$ et $M_1$. Le principal problème rencontré en utilisant cette règle de mise à jour centralisé est la variance importante de $R(\omega_{0:T})$, qui peut fortement ralentir la convergence. Pour
compenser partiellement cette variance, deux constatations rapides permettent d'améliorer la règle de mise à jour. Premièrement, les futures actions ne dépendent pas des récompenses passées, c.à.d. $E_D[R(\omega_{0:t-1}) \frac{\partial}{\partial \theta_t} \log a_t(u_t|o_t)] = 0$, On peut donc utiliser $R(\omega_{t:T})$ au lieu de $R(\omega_{0:T})$ dans 12, ce qui réduit significativement la variance de notre estimation du gradient. Deuxièmement, l'estimation du gradient de la politique n'est pas biaisée par l'introduction d'une fonction de référence $\tilde{\beta}_t$ (en anglais : baseline) tant que celle-ci ne dépend pas de $\theta_{0:T}$. On peut ainsi remplacer $R(\omega_{t:T})$ par une récompense relative à cette référence $R(\omega_{t:T}) - \tilde{\beta}_t(x_t, o_t)$.

## 3.2 Acteur Critique

Pour améliorer la variance de l'estimation du gradient dans (12), le théorème du gradient de la politique [26] propose de remplacer $R(\omega_{t:T})$ par $Q_t^w(x_t, o_t, u_t)$, une approximation de la Q-valeur associée à la commande $u_t$ dans l'état $x_t$ et après un historique $o_t$ puis en complétant la trajectoire en suivant la politique $\pi: Q_t^w(x_t, o_t, u_t) \approx Q_t^\pi(x_t, o_t, u_t)$, où $w_t \in \mathbb{R}^{l_t}$ est un vecteur de paramètres, avec $l_t \ll |\mathcal{X}||\mathcal{O}_t||\mathcal{U}|$. Ceci conduit au schéma algorithmique acteur critique, dans lequel un algorithme centralisé met à jour à la fois les paramètres $\theta_{0:T}$ de la politique et les paramètres $w_{0:T}$ de l'approximation de la Q-valeur :

$$ \Delta w_t = \alpha E_D \left[ \delta_t \frac{\partial \log a_t(u_t|o_t)}{\partial \theta_t} \right] \quad (13a) $$

$$ \Delta \theta_t = \alpha E_D \left[ Q_t^w(x_t, o_t, u_t) \frac{\partial \log a_t(u_t|o_t)}{\partial \theta_t} \right] \quad (13b) $$

où on note $\delta_t \doteq \hat{Q}_t^\pi(x_t, o_t, u_t) - Q_t^w(x_t, o_t, u_t)$, avec $\hat{Q}_t^\pi(x_t, o_t, u_t)$ une estimation non-biaisée de la véritable Q-valeur $Q_t^\pi(x_t, o_t, u_t)$, utilisant par exemple une estimation Monte-Carlo (MC) de $R(\omega_{0:T})$ ou bien une différence temporelle (erreur TD) $r_t + \gamma Q_{t+1}^w(x_{t+1}, o_{t+1}, u_{t+1})$. Le choix des paramètres $w_{0:T}$ est crucial pour que l'estimation du gradient reste non-biaisée [26]. Il n'y a pas de biais si les approximations de Q-valeur $Q_{0:T}^w$ sont compatibles avec la politique $\pi$. Sans rentrer dans les détails formels, une approximation compatible $Q_{0:T}^w$ de la véritable fonction $Q_{0:T}^\pi$ peut être une combinaison linéaire des « caractéristiques » de la politique $\pi$, et ses paramètres $w_{0:T}$ constituent la solution du problème de régression linéaire qui estime $Q_{0:T}^\pi$ à partir de ces caractéristiques. En pratique, cette seconde condition n'est pas utilisée directement, et les paramètres $w_{0:T}$ sont mis à jour en utilisant par exemple des méthodes MC ou TD.

## 3.3 Acteur Critique Naturel

Suivre la direction du gradient n'est pas toujours le moyen le plus rapide pour converger. Le gradient naturel propose une mise à jour des paramètres $\theta_{0:T}$ selon la direction de plus rapide ascension par rapport à la métrique d'information de Fisher :

$$ \mathbf{\Phi} \doteq E_D \left[ \frac{\partial \log a_t(u_t|o_t)}{\partial \theta_t} \left( \frac{\partial \log a_t(u_t|o_t)}{\partial \theta_t} \right)^{\top} \right] \quad (14) $$

Cette métrique est invariante à une reparamétrisation de la politique. Combiner le théorème du gradient de la politique avec une approximation compatible de la Q-valeur, puis effectuer une mise à jour des paramètres dans la direction donnée par (14), donne naissance au schéma algorithmique acteur-critique naturel, qui remplace (13b) dans (13) par : $\Delta \theta_t = \alpha E_D[w_t]$.

# 4 Gradient de la politique pour les systèmes multi-agents

Dans cette section, nous passons en revue les extensions des méthodes du gradient de la politique mono-agent à des modèles multi-agents coopératifs. On distingue trois paradigmes, illustrés dans la Figure 1 : l'entraînement centralisé pour un contrôle centralisé (CTCC), l'entraînement distribué pour un contrôle décentralisé (DTDC), et l'entraînement centralisé pour un contrôle décentralisé (CTDC).

## 4.1 CTCC

Dans certaines applications des systèmes multi-agents coopératifs, on peut considérer des agents pouvant communiquer entre eux de façon parfaite, instantanée et illimitée. De telles applications peuvent être modélisées par des POMDP, ce qui rend possible d'utiliser les méthodes du gradient de la politique mono-agent (Section 3). Dans ce paradigme CTCC, illustré par la Figure 1 (gauche), un seul acteur « coordinateur » guidé par un critique unique est utilisé. Le principal défaut de ce paradigme fait aussi sa force : ce besoin de communication parfaite, instantanée et illimitée entre les agents d'un bout à l'autre de l'exécution, à la fois pendant l'entraînement et le déploiement.

## 4.2 DTDC

Assez étonnamment, il s'avère que la première adaptation des méthodes du gradient de la politique au cadre multi-agent visait à apprendre de façon distribuée les politiques à exécuter de façon décentralisée, comme par exemple l'algorithme Reinforce distribué [22]. Dans ce paradigme DTDC, les agents apprennent simultanément mais indépendamment leurs politiques individuelles en utilisant l'algorithme Reinforce avec chacun un critique et un acteur individuels, comme l'illustre la Figure 1 (droite). L'indépendance des vecteurs de paramètres $\theta_{0:T}^1, \theta_{0:T}^2, \dots, \theta_{0:T}^n$ donne lieu à la règle de mise à jour suivante : $\forall t = 0, 1, \dots, T, \forall i \in \mathcal{I}_n$,

$$ \Delta \theta_t^i = \alpha E_D \left[ R(\omega_{0:T}) \frac{\partial \log a_t^i(u_t^i|o_t^i)}{\partial \theta_t^i} \right] \quad (15) $$

Il est à noter que la somme des gradients des politiques individuelles est un estimateur non-biaisé du gradient de la politique jointe. Néanmoins, la question reste ouverte de savoir comment tirer profit des méthodes acteur-critique (voir Section 3) pour réduire la variance de cet estimateur joint. De plus, l'algorithme Reinforce distribué est restreint à un apprentissage où l'échantillonnage des trajets est dicté par la politique apprise $\pi$ (on-policy), quand
<figure><img src="image_32.png" /><figcaption>FIGURE 1 – Schéma algorithmique acteur-critique dans un modèle à deux agents pour les paradigmes : (gauche) CTCC, (centre) CTDC, et (droite) DTDC. Pour chaque figure, les flèches bleues représentent les commandes des agents sur l'environnement, les vertes montrent l'agrégation d'information pour le prochain pas de décision, et les rouges indiquent le signal de récompense propagé pour mettre à jour les différents paramètres.</figcaption></figure>

des politiques d'exploration mieux choisies $\bar{\pi}$ peuvent fortement améliorer la qualité de l'optimum local atteint à la convergence [7].

## 4.3 CTDC

Le paradigme CTDC a été employé avec succès pour résoudre des problèmes de planification de Dec-POMDP [4, 9, 10, 13, 17, 20, 27, 28]. Dans un tel paradigme, un coordinateur central apprend pour l'ensemble des agents pendant la phase d'entraînement puis assigne les politiques individuelles apprises aux agents correspondants avant le début de la phase d'exécution. Comme le montre la Figure 1 (centre), les algorithmes acteur critique dans ce paradigme CTDC mettent à jour un critique central mais optimisent un acteur par agent. Des travaux récents en apprentissage par renforcement (profond) [12, 13, 18] exploitent ce paradigme, en particulier l'approche par gradient de la politique multi-agents contrefactuel, et l'algorithme COMA qui en découle. Malheureusement, cette algorithme se focalise sur un critique central apportant une solution au problème de l'assignation des crédits. Pour un Dec-POMDP $M_n$ (faiblement) séparable [8], il est possible d'apprendre une contribution relative de chaque agent à la valeur de la politique jointe, apportant ainsi une réponse au problème d'assignation du crédit. En revanche, en général, la dynamique et les récompenses d'un Dec-POMDP peuvent être fortement corrélées, ce qui rend difficile voire impossible d'accorder du crédit à tel ou tel agent. Contrairement aux méthodes de planification, les méthodes d'ascension du gradient de la politique dans ce paradigme CTDC manquent de fondements théoriques, qui permettraient de définir la forme du critique centralisé et les règles de mise à jour préservant certaines garanties formelles.

# 5 Gradient de la politique pour les Dec-POMDP

Dans cette section, nous apportons une réponse aux limitations des paradigmes CTCC et DTDC, et étendons les schémas algorithmiques acteur-critique et acteur-critique naturel de $M_1$ vers $M_n$.

## 5.1 Théorème du Gradient de la Politique

Notre principal résultat est une extension du théorème du Gradient de la politique [26] de $M_1$ vers $M_n$. Avant de poursuivre, nous commençons par exposer quelques résultats préliminaires qui nous permettrons d'établir notre résultat principal de la section. Toutes les preuves sont disponibles dans le rapport de recherche [5].

Nous commençons par établir une expression des dérivées partielles des fonctions de valeurs $V_{0:T}^{\pi}$ par rapport aux vecteurs de paramètres $\theta_{0:T}^{1:n}$ dans le cas à horizon fini.

**Lemme 2.** Soit un Dec-POMDP $M_n$, une politique jointe à évaluer $\pi \doteq (a_0, \dots, a_T)$ et une politique d'exploration $\bar{\pi} \doteq (\bar{a}_0, \dots, \bar{a}_T)$. Pour tout temps $t = 0, 1, \dots, T$, agent $i \in \mathcal{I}_n$, état caché $x_t \in \mathcal{X}$, et historique joint $o_t \in \mathcal{O}_t$ :

$$ \frac{\partial V_t^\pi(x_t, o_t)}{\partial \theta_t^i} = \mathbb{E}_{U_t \sim \bar{a}_t(\cdot|o_t)} \left[ \frac{a_t(U_t|o_t)}{\bar{a}_t(U_t|o_t)} Q_t^\pi(x_t, o_t, U_t) \frac{\partial \log a_t^i(U_t^i|o_t^i)}{\partial \theta_t^i} \right]. \quad (16) $$

Voici à présent le résultat principal de la section.

**Théorème 1.** Soit un Dec-POMDP $M_n$, une politique à évaluer $\pi \doteq (a_0, \dots, a_T)$ et une politique d'exploration $\bar{\pi} \doteq (\bar{a}_0, \dots, \bar{a}_T)$.

1. Dans le cas à horizon fini $T < \infty$, pour tout temps
$t = 0, 1, \dots, T$ et agent $i \in \mathcal{I}_n$ :

$$
\frac{\partial J(s_0; \theta^{1:n}_{0:T})}{\partial \theta_t^i} = \gamma^t \mathbb{E}_{(X_t, O_t, U_t) \sim \mathbb{P}(\cdot | \bar{a}_t, M_n)} \left[ \frac{a_t(U_t | O_t)}{\bar{a}_t(U_t | O_t)} \right. \\
\left. Q_t^\pi(X_t, O_t, U_t) \frac{\partial \log a_t^i(U_t^i | O_t^i)}{\partial \theta_t^i} \right]
$$

2. Dans le cas à horizon infini $T = \infty$, pour tout agent $i \in \mathcal{I}_n$ :

$$
\frac{\partial J(s_0; \theta^{1:n})}{\partial \theta^i} = \mathbb{E}_{(X, \Sigma, U) \sim \mathbb{P}(\cdot | \bar{s}, \bar{a})} \left[ \frac{a(U|\Sigma)}{\bar{a}(U|\Sigma)} \right. \\
\left. Q^{\pi}(X, \Sigma, U) \frac{\partial \log a^i(U^i|\Sigma^i)}{\partial \theta^i} \right]
$$

où

$$
\bar{s}(x, \varsigma) \doteq \sum_{t=0}^{\infty} \gamma^t \mathbb{P}(X_t = x, \Sigma_t = \varsigma | M_n, \bar{a}, \psi, X_0, \varsigma_0)
$$

Le théorème du gradient de la politique pour $M_n$ (Théo-
ème 1) est différent de celui pour $M_1$ [26]. Ce dernier
part de l'hypothèse qu'un unique agent apprend à agir dans
un (PO)MDP. À l'inverse, le Théorème 1 s'applique à un
ensemble d'agents apprenant à contrôler l'évolution d'un
POMDP de façon décentralisée. Les agents agissent indé-
pendamment, mais leur estimation du gradient de la poli-
tique est guidée par une évaluation centralisée des fonc-
tions $Q_{0:T}^{\pi}$. Pour utiliser cette propriété en pratique, il faut
remplacer la véritable Q-valeur $Q_{0:T}^{\pi}$ par une approxima-
tion. Pour garantir que cette approximation est compatible
– c.à.d. que le gradient calculé avec l’approximation est
toujours dans la même direction que le véritable gradient
– il faut lui donner une structure particulière que nous dé-
taillons ci-dessous.

5.2 Approximations compatibles

Le résultat principal de cette section caractérise la forme
des approximations compatibles $V_{0:T}^{\sigma}$ et $A_{0:T}^{\nu}$ respective-
ment pour les fonctions de valeur $V_{0:T}^{\pi}$ et les fonctions
d'avantage $A_{0:T}^{\pi}$ pour un Dec-POMDP quelconque $M_n$.
Ensemble, ces deux approximations permettent d'évaluer
$Q_{0:T}^{\pi}(x_t, o_t, u_t) \doteq V_t^{\pi}(x_t, o_t) + A_t^{\pi}(x_t, o_t, u_t)$, pour tout
temps $t = 0, 1, \dots, T$, historique joint $o_t \in \mathcal{O}_t$ et com-
mande jointe $u_t \in \mathcal{U}$.

**Théorème 2.** Soit un Dec-POMDP $M_n$, des fonctions d'approximation $V_{0:T}^{\sigma}$ et $A_{0:T}^{\nu}$, de paramètres respectifs $\sigma_{0:T}^{1:n}$ et $\nu_{0:T}^{1:n}$. Ces approximations sont compatibles avec la politique jointe $\pi \doteq (a_0, \dots, a_T)$ paramétrée par $\theta_{0:T}^{1:n}$ si l'une des deux conditions suivantes est vérifiée $\forall t = 0, 1, \dots, T$ :

1. $\forall i \in \mathcal{I}_n, \forall x_t \in \mathcal{X}, \forall o_t \in \mathcal{O}_t,$

$$
\frac{\partial V_t^\sigma(x_t, o_t)}{\partial \sigma_t^i} = \mathbb{E}_{U_t^i \sim a_t^i(\cdot | o_t^i)} \left[ \frac{\partial \log a_t^i(U_t^i | o_t^i)}{\partial \theta_t^i} \right] \quad (17)
$$

et $\sigma$ minimise l'erreur quadratique moyenne (MSE)
$\mathbb{E}[\epsilon_t(X_t, O_t, U_t)^2]$

2. $\forall i \in \mathcal{I}_n, \forall x_t \in \mathcal{X}, \forall o_t \in \mathcal{O}_t, \forall u_t \in \mathcal{U},$
$$
\frac{\partial A_t^\nu(x_t, o_t, u_t)}{\partial \nu_t^i} = \frac{\partial \log a_t^i(u_t^i | o_t^i)}{\partial \theta_t^i} \quad (18)
$$

et $\nu$ minimise l'erreur quadratique moyenne (MSE)
$\mathbb{E}[\epsilon_t(X_t, O_t, U_t)^2]$

où $\epsilon_t(x_t, o_t, u_t) \doteq Q_t^\pi(x_t, o_t, u_t) - V_t^\sigma(x_t, o_t) - A_t^\nu(x_t, o_t, u_t)$.

Quand l'une de ces conditions est vérifiée, on a bien, pour
toute politique d'exploration $\bar{\pi} \doteq (\bar{a}_0, \dots, \bar{a}_T)$ :

$$
\frac{\partial V_t^\pi(x_t, o_t)}{\partial \theta_t^i} = \mathbb{E}_{U_t \sim \bar{a}_t(\cdot | o_t)} \left[ \frac{a_t(U_t | o_t)}{\bar{a}_t(U_t | o_t)} \right. \\
\left. (V_t^\sigma(x_t, o_t) + A_t^\nu(x_t, o_t, U_t)) \frac{\partial \log a_t^i(U_t^i | o_t^i)}{\partial \theta_t^i} \right] \quad (19)
$$

Le Théorème 2 est énoncé ci-dessus pour des politiques non-stationnaires et pour des problème à horizon fini $T < \infty$. Le résultat s'étend néanmoins très naturellement au cas à horizon infini et pour des politiques stationnaires où $a_t^i = a^i, \theta_t^i = \theta^i \quad \forall t = 0, 1, \dots, \infty, \forall i \in \mathcal{I}_n$. Le théorème montre comment les conditions de compatibilité d'une approximation de la Q-valeur pour $M_1$ se généralisent dans le cas d'un Dec-POMDP $M_n$. Parmi les propriétés notables de ces approximations centralisées compatibles, il faut relever leur séparabilité :

$$
V_t^\sigma : (x_t, o_t) \mapsto \sum_{i \in I_n} \mathbb{E} \left[ \left( \frac{\partial \log a_t^i (U_t^i | o_t^i)}{\partial \theta_t^i} \right)^\top \sigma_t^i \right] \quad (20)
$$

dans le premier cas, ou alors

$$
A_t^\nu : (x_t, o_t, u_t) \mapsto \sum_{i \in I_n} \left( \frac{\partial \log a_t^i (u_t^i | o_t^i)}{\partial \theta_t^i} \right)^\top \nu_t^i \quad (21)
$$

dans le second. Quel que soit le cas, à l'instar des résul-
tats existants pour $M_1$, l'approximation $A^\nu$ ou $V^\sigma$ dont la
structure n'est pas contrainte constitue un degré de liberté
très important pour tenter de réduire la variance de l'esti-
mation du gradient. Dans notre paradigme CTDC, elle peut
entre autre accéder aux état cachés $x_t$, ou encore combiner
de façon plus intriquée l'information jointe disponible. Par
ailleurs, il est tout à fait envisageable d'exploiter la sépara-
bilité des deux approximations compatibles :

$$
\begin{align}
Q_t^\pi(x_t, o_t, u_t) &\approx \sum_{i \in I_n} \left( \frac{\partial \log a_t^i (u_t^i | o_t^i)}{\partial \theta_t^i} \right)^\top \nu_t^i \nonumber \\
&\quad + \sum_{i \in I_n} \mathbb{E} \left[ \left( \frac{\partial \log a_t^i (U_t^i | o_t^i)}{\partial \theta_t^i} \right)^\top \sigma_t^i \right. \tag{22} \\
&\quad \left. + \tilde{\beta}_t(x_t, o_t, u_t) \right] \nonumber
\end{align}
$$

avec $\tilde{\beta}_t$ une fonction de référence arbitraire, ne dépendant
ni de $\nu$, ni de $\sigma$, ni de $\theta$ et ne perturbant donc pas le gra-
dient. Notons enfin que la séparabilité du critique centralisé
ne nous permet pas de considérer les critiques individuels
indépendamment l'un de l'autre, l'approximation du gra-
dient est toujours jointe et guidée par cet unique critique
centralisé.
## 5.3 Algorithmes Acteur Critique pour le Contrôle Décentralisé

Dans cette section, nous utilisons les résultats du Théorème 2 pour donner naissance à un schéma algorithmique acteur-critique pour $M_n$ adapté au paradigme CTDC, que nous appelons *acteur critique pour le contrôle décentralisé* (ACDC). Cet algorithme ne nécessite pas de connaissance à priori du modèle, et l'échantillonnage des trajectoires peut se servir d'une politique d'exploration différente de la politique à évaluer. Il est centralisé<fnref n="1" /> et itératif. Chaque itération consiste en une étape d'évaluation de la politique apprise, suivi d'une étape d'amélioration de celle-ci. L'étape d'évaluation crée une base d'échantillons de trajectoires (mini-batch) $\mathcal{D}$ à partir de $\mathbb{P}(\Omega_{0:T}|\pi, M_n)$ et stocke en mémoire les erreurs TD correspondantes (voir lignes 6–11). L'étape d'amélioration met à jour l'ensemble des paramètres $\theta$, $\nu$, et $\sigma$ dans la direction du gradient estimé à partir de la moyenne empirique sur la base $\mathcal{D}$ en exploitant la séparabilité des approximations compatibles (voir lignes 12–16).

<caption>**Algorithm 1:** Actor-Critic for Decentralized Control (ACDC).</caption>

1. **ACDC ()**
2. &nbsp;&nbsp;Initialize $\theta_0, \nu_0, \sigma_0$ arbitrarily and $h \leftarrow 0$.
3. &nbsp;&nbsp;**while** $\theta_h$ has not converged **do**
4. &nbsp;&nbsp;&nbsp;&nbsp;**evaluation ()** and **improvement ()**
5. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**h** $\leftarrow h + 1$
6. &nbsp;&nbsp;**evaluation ()**
7. &nbsp;&nbsp;&nbsp;&nbsp;Initialize $\mathcal{D}_{0:T}^h \leftarrow \emptyset$
8. &nbsp;&nbsp;&nbsp;&nbsp;**for** $j = 1 \dots m$ and $t = 0 \dots T$ **do**
9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Create trajectories $(x_{t:t+1}, o_{t:t+1}, u_t) \sim p(\cdot|\theta_{0:t}^{1:n})$
10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Evaluate $\delta_t \leftarrow r_t + \gamma V_{t+1}^\sigma(x_{t+1}, o_{t+1}) - V_t^\sigma(x_t, o_t)$
11. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Compose batch
12. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \mathcal{D}_{t,h} \leftarrow \{(o_t, u_t, \delta_t, a_t(u_t|o_t)/\bar{a}_t(u_t|o_t))\} \cup \mathcal{D}_{t,h} $$
13. &nbsp;&nbsp;**improvement ()**
14. &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 1 \dots n$ **do**
15. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Baseline update
16. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \sigma_{t,h+1}^i \leftarrow \sigma_{t,h}^i + \alpha_h^\sigma \mathbb{E}_{\mathcal{D}_{t,h}} \{\delta_t \frac{a_t(u_t|o_t)}{\bar{a}_t(u_t|o_t)} \phi_t^i(o_t^i)\} $$
17. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Critic update
18. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \nu_{t,h+1}^i \leftarrow \nu_{t,h}^i + \alpha_h^\nu \mathbb{E}_{\mathcal{D}_{t,h}} \{\delta_t \frac{a_t(u_t|o_t)}{\bar{a}_t(u_t|o_t)} \phi_t^i(o_t^i, u_t^i)\} $$
19. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Actor update
20. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \theta_{t,h+1}^i \leftarrow \theta_{t,h}^i + \alpha_h^\theta \mathbb{E}_{\mathcal{D}_{t,h}} \{\frac{a_t(u_t|o_t)}{\bar{a}_t(u_t|o_t)} \phi_t^i(o_t^i, u_t^i)\} $$

Les taux d'apprentissage $\alpha_h^\theta$, $\alpha_h^\nu$ et $\alpha_h^\sigma$ évoluent selon les conditions standard de Robbins et Monro pour les algorithmes d'approximation stochastiques [23], c.à.d. $\sum_{h=0}^\infty \alpha_h = \infty$, $\sum_{h=0}^\infty \alpha_h^2 < \infty$. De plus, si l'on suit les recommandations de [16], ces taux doivent être mis à jour à chaque itération tel que les paramètres des acteurs $\theta$ soient modifiés « plus lentement » que les paramètres $\nu$ et $\sigma$

pour garantir la convergence. Pour faciliter la convergence d'une politique jointe pour une modification constante de ses paramètres, une méthode de choix est l'utilisation gradient naturel [1, 15]. L'algorithme ACDC naturel (NACDC) ne diffère de sa version initiale que par la formule de mise à jour des acteurs :

$$ \theta_{t,h+1}^i \leftarrow \theta_{t,h}^i + \alpha_h^\theta \mathbb{E}_{\mathcal{D}_{t,h}} \left[ \frac{a_t(u_t|o_t)}{\bar{a}_t(u_t|o_t)} \nu_{t,h}^i \right] $$

Pour conclure, cette section, quelques remarques sur les propriétés théoriques des algorithmes ACDC. D'une part, moyennant quelques conditions mineures, ils convergent avec probabilité 1 vers un optimum local puisque ce sont de véritables algorithmes d'ascension du gradient [7]. L'argument repose sur le fait qu'ils minimisent l'erreur de projection quadratique par descente de gradient stochastique, mais nous renvoyons le lecteur vers [7] pour plus de détails. D'autre part, ils terminent sur un optimum local qui est aussi un équilibre de Nash. En effet les dérivées partielles du critique centralisé par rapport à n'importe lequel de ses paramètres ne sont nulles qu'en un point d'équilibre, qui est aussi un optimum local.

# 6 Expérimentations

Dans cette section, nous montrons empiriquement les avantages du paradigme CTDC sur les paradigmes classiques CTCC et DTDC. Nos résultats semblent indiquer que les méthodes ACDC se comparent favorablement aux algorithmes existants sur de nombreux domaines multi-agents décentralisés de la littérature. Nous illustrons également les limitations de l'implémentation actuelle qui l'empêchent d'obtenir de meilleures performances.

## 6.1 Conditions expérimentales

Comme nous l'avons laisser transparaître tout au long de cet article, plusieurs facteurs clés peuvent affecter les performances des méthodes acteur-critique. Parmi ceux-ci, nous relèverons : le paradigme d'entraînement utilisé (CTCC vs DTDC vs CTDC) ; la représentation de la politique (stationnaire vs non-stationnaire) ; les structures d'approximation (linéaires vs réseaux de neurones récurrents (RNN)) ; la représentation des historiques (troncatures à mémoire finie vs états cachés d'un RNN). Nous implémentons trois variantes des méthodes acteur-critique qui combinent ces différents facteurs. Sauf mention contraire, nous ferons référence à chaque variante mise en œuvre par le nom du paradigme qu'elle implémente, par exemple CTDC pour notre algorithme ACDC, suivi de la structure de représentation interne utilisée quand cela est pertinent, par exemple : « CTDC_trunc(K) » pour un algorithme ACDC utilisant un historique tronqué des K dernières observations comme entrée d'une politique linéaire non-stationnaire, ou encore « DTDC_rnn » pour l'algorithme Reinforce distribué utilisant un réseau de neurone récurrent dans une politique stationnaire (voir Figure 2).

<footnote n="1">1. Il est néanmoins possible de le faire tourner de façon distribuée en donnant le moyen aux agents de collaborer pendant l'entraînement en se communiquant leur informations locales.</footnote>
<figure><img src="image_33.png" /><figcaption>FIGURE 2 – Réseau de neurones récurrent utilisé comme structure « acteur » de chaque agent $i \in I_n$. Une couche LSTM met à jour un état caché interne à partir du précédent et d'une encapsulation (embedding) d'une paire commande-observation. Elle est suivie d'un perceptron dont les activations sont rectifiées linéairement (ReLU) qui génère un vecteur de caractéristiques (features) $\phi^i$, qui sont combinées linéairement par un second perceptron dont la sortie est normalisée par un softmax pour donner la règle de décision conditionnelle $a^i(\cdot|\zeta^i)$.</figcaption></figure>

Nous avons mené nos expérimentations sur une station de calcul *Dell Precision Tower 7910* équipé d'un CPU *Intel Xeon* à 16 cœurs cadencés à 3GHz, de 16Go de RAM et d'une carte graphique *nVIDIA Quadro K620* munie de 2Go de mémoire vidéo. Nous avons simulé plusieurs bancs de test standard de la littérature des Dec-POMDP, *Dec. Tiger*, *Broadcast Channel*, *Mars*, *Box Pushing*, *Meeting in a Grid*, et *Recycling Robots* pour les citer – tel qu’ils sont défini sur http://masplan.org. Le détail des meta-paramètres utilisés est donné dans le rapport de recherche [5].

## 6.2 Importance de la représentation de l'état interne

Dans cette section, nous mettons en place des expériences visant à comprendre la façon dont la représentation des historiques affectent les performances des méthodes ACDC. La Figure 3 comporte les récompenses cumulées moyennes obtenues avec des historiques tronqués de taille 1 et 3, celles obtenues avec des RNN, et la performance $\epsilon$-optimal donnée par l’algorithme de planification centralisé FB-HSVI [11]. Pour des horizons courts, ici $T = 10$, CTDC rnn converge rapidement vers de bonnes solutions par rapport à CTDC_trunc(1) et CTDC_trunc(3). Ceci laisse penser que CTDC_rnn apprends des représentations des historiques plus concises et discriminantes que la représentation tronquée. Il semblerait néanmoins que cette différence de performances s’amenuise quand l’horizon de planification augmente (non illustré ici). On notera néanmoins une certaine instabilité de la récompense cumulée empirique pour les RNN sur les tâches plus complexe comme Dec. Tiger, un banc de test mettant en avant l’importance de la collecte d’information avant de prendre une action décisive, où les pénalités en cas d’erreur sont, en valeur absolues, bien plus élevées que les récompenses en cas de succès.

Dans l’ensemble, nos expériences montrent un fort potentiel des RNN pour représenter les historiques. Ils ont l’avantage par rapport aux historiques tronqués d’apprendre automatiquement des classes d’équivalence et une représentation compacte de l’état interne, en se basant seulement sur la retro-propagation du gradient issu du si-

<figure><img src="image_34.png" /><figcaption>FIGURE 3 – Comparaison des différentes structures de représentation des historiques à $T = 10$.</figcaption></figure>

gnal de récompense. Il est aussi important de noter ici l’importance du choix des méta-paramètres, en particulier le taux d’apprentissage, qui, s’il est trop élevé, encourage des convergences prématurées vers des optima locaux insatisfaisants, sans laisser le temps à la politique d’explorer le reste des trajectoires possibles. Attention également à certaines propriétés spécifiques des modèles considérés, pour lesquelles les méthodes par ascension de gradient peinent à échapper au piège d’optima locaux. Nous n’avons pas pu identifier avec certitude quelles caractéristiques particulières avaient le plus d’impact négatif sur les performances, et nous laissons à de futures études l’analyse et l’exploration de méthodes plus fiables pour entraîner ces architectures.

## 6.3 Comparaison des différents paradigmes

Dans cette section, nous comparons les paradigmes CTCC, DTDC et CTDC en utilisant indifféremment les représentations ayant données les meilleurs résultats dans chaque cas. Nous incluons également à la comparaison les résultats issus de deux autres algorithmes de la littérature Dec-POMDP : un algorithme de planification $\epsilon$-optimal appelé FB-HSVI [11], et un algorithme de planification par échantillonnage appelé Espérance-Maximisation Monte-Carlo (MCEM) [31]; un choix justifié par de nombreuses similarités avec les méthodes acteur critique. Nous soulagnons le fait que nous ne cherchons pas à égaler les performances de FB-HSVI qui est un algorithme de planification centralisé nécessitant la connaissance à priori du modèle. Il nous fournit des performances de référence très proches de l’optimal global. Quant à MCEM, les résultats sont repris de [31]$^2$.

Pour presque tous les bancs de test, CTDC semble prendre le meilleur sur les deux autres paradigmes, que ce soit à horizon fini ou infini. CTCC pâtit probablement du fléau de la dimension dans l’espace des historiques joints, et ne parvient pas à l’explorer de façon suffisamment efficace avant que les taux d’apprentissage rendent les mises à jour des paramètres négligeables, ou que le nombre maximum

<footnote n="2">2. Sauf pour *Meeting in a Grid* et *Broadcast Channel* pour lesquels les valeurs indiquées dans [31] étaient bien au delà de l’optimal, laissant penser à une anomalie.</footnote>
<figure><img src="image_35.png" /><figcaption>FIGURE 4 – Comparaison des paradigmes pour $T = 10$.</figcaption></figure>

<figure><img src="image_36.png" /><figcaption>FIGURE 5 – Comparaison des paradigmes pour $T = \infty$.</figcaption></figure>

d'itérations fixé au départ ne soit atteint. Le fait d'utiliser la politique apprise comme politique d'échantillonnage (on-policy) amplifie très certainement cet effet. Ayant un espace d'historiques individuels bien plus réduit à exploiter, CTDC donne de meilleur résultats que CTCC dans ces expérimentations. Comparé à DTDC qui explore lui-aussi des espaces d'historiques de dimensions plus raisonnables, le paradigme CTDC a un net avantage, et l'utilisation d'un critique centralisé compatible donnent de meilleures performances sur la vitesse de convergence et la qualité de l'optimum local atteint. Bien que CTDC donnent des résultats favorables – ou au moins comparables – par rapport à l'algorithme de l'état de l'art MCEM, il y a encore une large marge d'amélioration pour atteindre les optima globaux donnés par FB-HSVI pour tous les bancs de test. Comme mentionné précédemment, c'est en partie dû à une compression encore imparfaite des historiques, mais aussi à des limitations intrinsèques des méthodes par ascension de gradient, qui ne peuvent garantir qu'un optimum local.

## 7 Conclusion

Cet article pose les fondations théoriques des méthodes acteur-critique pour les Dec-POMDP dans le paradigme CTDC. Dans ce paradigme, un algorithme acteur-critique centralisé apprend des politiques indépendantes, une par agent, guidé par un unique critique joint. Nous montrons qu'un critique centralisé compatible peut s'écrire comme la somme de critiques individuels, qui sont chacun des combinaisons linéaires des « caractéristiques » de la politique individuelle correspondante. Nos expérimenta-

tions montrent que nos méthodes acteur-critique appelées ACDC se démarquent favorablement des approches standard du RL pour un certain nombre de bancs de test de la littérature. L'implémentation actuelle de ACDC soulève deux problèmes bien connu du domaine : le compromis exploitation-exploration et la représentation des états internes individuels. En particulier pour ce dernier point, apprendre à projeter les historiques individuels vers des états internes proches des états d'occupation individuels est un défi de taille, auquel nous comptons continuer à contribuer dans le futur. Outre ce problème de représentation des historiques individuels, ACDC peut exploiter la séparabilité du critique joint compatible pour passer à l'échelle d'un assez grand nombre d'agents. Nous nous intéressons à présent à une application multi-agents décentralisée à large échelle, pour laquelle nous cherchons à exploiter cette propriété.

## Références

[1] Shun-Ichi AMARI. "Natural Gradient Works Efficiently in Learning". In : *Neural Comput.* 10.2 (1998). ISSN : 0899-7667.

[2] Karl J ASTRÖM. "Optimal Control of Markov Decision Processes with Incomplete State Estimation". In : *Journal of Mathematical Analysis and Applications* 10 (1965).

[3] Richard E BELLMAN. "The Theory of Dynamic Programming". In : *Bulletin of the American Mathematical Society* 60.6 (1954).

[4] Daniel S BERNSTEIN et al. "The Complexity of Decentralized Control of Markov Decision Processes". In : *Mathematics of Operations Research* 27.4 (2002).

[5] Guillaume BONO et al. *On the Study of Cooperative Multi-Agent Policy Gradient*. Research Report RR-9188. INSA Lyon, INRIA, 2018.

[6] Craig BOUTILIER. "Planning, Learning and Coordination in Multiagent Decision Processes". In : *Proc. of the Sixth Conf. on Theoretical Aspects of Rationality and Knowledge*. 1996.

[7] Thomas DEGRIS, Martha WHITE et Richard S. SUTTON. "Linear Off-Policy Actor-Critic". In : *Proc. of the 29th Int. Conf. on ML, ICML 2012*, Edinburgh, Scotland, UK, June 26 - July 1, 2012.

[8] Jilles Steeve DIBANGOYE et al. "Exploiting Separability in Multi-Agent Planning with Continuous-State MDPs". In : *Proc. of the Thirteenth Int. Conf. on Autonomous Agents and Multiagent Systems*. 2014.

[9] Jilles Steeve DIBANGOYE et al. "Optimally Solving Dec-POMDPs As Continuous-state MDPs". In : *Proc. of the Twenty-Fourth Int. Joint Conf. on AI*. 2013.
[10] Jilles Steeve DIBANGOYE et al. *Optimally solving Dec-POMDPs as Continuous-State MDPs: Theory and Algorithms*. Research Report RR-8517. 2014.

[11] Jilles S DIBANGOYE et al. "Optimally Solving Dec-POMDPs as Continuous-State MDPs". In: *Journal of AI Research* 55 (2016).

[12] Jakob FOERSTER et al. "Counterfactual Multi-Agent Policy Gradients". In: (2018).

[13] Jayesh K. GUPTA, Maxim EGOROV et Mykel KOCHENDERFER. "Cooperative Multi-agent Control Using Deep Reinforcement Learning". In: *Autonomous Agents and Multiagent Systems*. 2017.

[14] Eric A HANSEN, Daniel S BERNSTEIN et Shlomo ZILBERSTEIN. "Dynamic Programming for Partially Observable Stochastic Games". In: *Proc. of the Nineteenth National Conf. on AI*. 2004.

[15] Sham KAKADE. "A Natural Policy Gradient". In: *Advances in Neural Information Processing Systems 14* (NIPS 2001). 2001.

[16] Vijay R. KONDA et John N. TSITSIKLIS. "Actor-Critic Algorithms". In: *Adv. in Neural Information Processing Systems 12*. 2000.

[17] Landon KRAEMER et Bikramjit BANERJEE. "Multi-agent reinforcement learning as a rehearsal for decentralized planning". In: *Neurocomputing* 190 (2016).

[18] Ryan LOWE et al. "Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments". In: *Adv. in Neural Information Processing Systems 30*. 2017.

[19] Volodymyr MNIH et al. "Human-level control through deep reinforcement learning". In: *Nature* 518.7540 (fév. 2015). ISSN 0028-0836.

[20] Matej MORAVČÍK et al. "DeepStack: Expert-level artificial intelligence in heads-up no-limit poker". In: *Science* 356.6337 (2017).

[21] Frans A OLIEHOEK et al. "Incremental Clustering and Expansion for Faster Optimal Planning in Dec-POMDPs". In: *Journal of AI Research* 46 (2013).

[22] Leonid PESHKIN et al. "Learning to Cooperate via Policy Search". In: *Sixteenth Conf. on Uncertainty in Artificial Intelligence (UAI-2000)*. 2000.

[23] H ROBBINS et S MONRO. "A stochastic approximation method". In: *The annals of mathematical statistics* 22.3 (1951).

[24] Yoav SHOHAM et Kevin LEYTON-BROWN. *Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations*. New York, NY, USA, 2008. ISBN: 0521899435.

[25] Richard S SUTTON et Andrew G BARTO. *Introduction to Reinforcement Learning*. 2nd. Cambridge, MA, USA, 2016. ISBN: 0262193981.

[26] Richard S SUTTON et al. "Policy Gradient Methods for Reinforcement Learning with Function Approximation". In: *Proc. of the 12th Int. Conf. on Neural Information Processing Systems*. Cambridge, MA, USA, 1999.

[27] Daniel SZER et François CHARPILLET. "An Optimal Best-First Search Algorithm for Solving Infinite Horizon DEC-POMDPs". In: *Proc. of the Fifteenth European Conf. on ML*. 2005.

[28] Daniel SZER, François CHARPILLET et Shlomo ZILBERSTEIN. "MAA* : A Heuristic Search Algorithm for Solving Decentralized POMDPs". In: *Proc. of the Twenty-First Conf. on Uncertainty in AI*. 2005.

[29] Ming TAN. "Multi-agent Reinforcement Learning : Independent vs. Cooperative Agents". In: *Readings in Agents*. San Francisco, CA, USA, 1998.

[30] Ronald J WILLIAMS. "Simple statistical gradient-following algorithms for connectionist reinforcement learning". In: *ML* 8.3 (1992).

[31] Feng WU, Shlomo ZILBERSTEIN et Nicholas R JENNINGS. "Monte-Carlo Expectation Maximization for Decentralized POMDPs". In: *Proc. of the Twenty-Fourth Int. Joint Conf. on AI*. 2013.

[32] Xinhua ZHANG, Douglas ABERDEEN et S. V. N. VISHWANATHAN. "Conditional Random Fields for Multi-agent Reinforcement Learning". In: *Proc. of the 24th Int. Conf. on ML* (2007).
<figure><img src="image_37.png" /></figure>
# Classification d'images en apprenant sur des échantillons positifs et non labélisés avec un réseau antagoniste génératif

F. Chiaroni¹²

M-C. Rahal¹

F. Dufaux²

N. Hueber³

¹ Institut VEDECOM, équipe Perception du véhicule à conduite déléguée

² L2S, CNRS, CentraleSupelec, Univ Paris-Sud, Univ Paris-Saclay

³ Institut Saint-Louis Franco-Allemand (ISL), équipe ELSI

florent.chiaroni@l2s.centralesupelec.fr

## Abstract

In this article, we suggest a novel approach for image classification task from a positive unlabeled datased. Its proper functioning is based on generative adversarial networks (GANs) abilities. These allow us to generate fake images whose distribution is close to the distribution of the negative samples included in the unlabeled dataset available, while remaining different from the distribution of positive samples that are not labeled. Then we train a CNN classifier with the positive samples and the fake samples generated, as it would have been done with a classical Positive Negative dataset. Tests performed on three different image classification datasets show that the system is stable in its behavior with a non negligible fraction of positive samples present in the unlabeled dataset. Although very different, this method outperforms the state of the art in PU learning on the RGB CIFAR-10 dataset.

## Résumé

Dans ce document, nous proposons une nouvelle approche répondant à la tâche de classification d'images à partir d'un apprentissage sur données positives et non-labélisées. Son bon fonctionnement repose sur certaines particularités des réseaux antagonistes génératifs (GANs). Ces derniers nous permettent de générer des fausses images dont la distribution se rapproche de la distribution des échantillons négatifs inclus dans le jeu de données non labélisé disponible, tout en restant différente de la distribution des échantillons positifs non labélisés. Ensuite, nous entraînons un classifieur convolutif avec les échantillons positifs et les faux échantillons générés, tel que cela aurait été fait avec un jeu de données classique de type Positif Négatif. Les tests réalisés sur trois jeux de données différents de classification d'images montrent que le système est stable dans son comportement jusqu'à une fraction conséquente d'échantillons positifs présents dans le jeu de données non labélisé. Bien que très différente, cette méthode surpasse l'état de l'art PU learning sur le jeu de données RVB CIFAR-10.

## Mots Clef

Apprentissage Positif Non Labélisé (PU learning), Classification d'Images, Apprentissage Profond, Apprentissage de Représentations, Modèles Génératifs.

## 1 Introduction

Les méthodes d'apprentissage utilisant des filtres à noyaux de convolution ont démontré de bonnes performances de prédiction dans le domaine du traitement d'image, et plus particulièrement pour la tâche de classification d'images. Pour réaliser de telles performances, de grands jeux de données entièrement labélisés sont requis. De nos jours, plusieurs jeux de données distincts peuvent être amenés à être fusionnés pour cette raison afin d'augmenter la capacité de généralisation d'un modèle d'apprentissage tel que cela est proposé dans YOLO9000 [18]. Par ailleurs, pour atténuer ce besoin de grands jeux de données labélisés, des méthodes d'apprentissage semi-supervisé existent [16]. Mais, si un objet n'appartenant à aucune classe labélisée du jeu de données d'entraînement doit être traité, il reste difficile de prédire le comportement du modèle entraîné à son égard. Néanmoins, une idée pouvant répondre à ce problème consiste à se focaliser principalement sur les données qui nous intéressent. Cela est le cas pour les méthodes de One-Class Classification (OCC) [8], détection de nouveauté [14] où il est utilisé uniquement des échantillons de la classe d'intérêt ; la classe positive. Cependant, à notre connaissance, les méthodes OCC ont une performance limitée lorsqu'elles sont appliquées à des tenseurs de données de grande dimensionalité tels que des images. De plus, il est souvent facile d'acquérir des échantillons non labélisés susceptibles de contenir des informations pertinentes à propos des contre-exemples de la classe d'intérêt. De cette manière, nous abordons le problème d'apprentissage Positif Non labélisé (apprentissage PU). Il se trouve que les méthodes d'apprentissage Positif Non labélisé ont été appliquées récemment à des données de type images tel que la méthode Rank Pruning (RP) [13]. Cette méthode est la plus performante de l'état de l'art dans un contexte où l'on n'a pas de connais-
sances à priori sur les fractions d'échantillons bruités. Elle est cependant coûteuse en calculs car elle consiste à réaliser plusieurs entraînements consécutifs du même classifieur de manière à éliminer les échantillons les moins pertinents pendant la phase d'entraînement. De plus, selon [12], ces méthodes deviennent compétitives lorsque le nombre d'échantillons non labélisés dans le jeu de données d'entraînement augmente considérablement. Cela est un avantage lorsque l'on peut obtenir facilement des données non labélisées. Par ailleurs, les réseaux génératifs antagonistes (GANs) ont attiré notre attention en raison de leur capacité à générer de faux échantillons $x_F$ qui ont une distribution $p_G(x_F)$ qui tend vers la distribution $p_{data}(x_R)$ des échantillons réels $x_R$ utilisés pendant son entraînement. Le GAN original [5] contient un modèle génératif $G$ et un modèle discriminatif $D$. Ces deux modèles possèdent une structure de type perceptron multi-couche. Un vecteur de bruit $z$, composé de variables aléatoires continues, est placé en entrée de $G$. $D$ est entraîné à distinguer les échantillons réels des faux échantillons générés par $G$, pendant que ce dernier est entraîné à produire des faux échantillons qui doivent sembler réels au possible. Cet entraînement adversaire consiste à utiliser la fonction d'évaluation minimax $V(G, D)$ :

$$ \min_G \max_D V(G, D) = \mathbb{E}_{x_R \sim p_{data}(x_R)} \log D(x_R) + \mathbb{E}_{z \sim p_z(z)} \log[1 - D(G(z))]. $$

Lorsque $D$ ne peut plus distinguer les vrais échantillons des faux, nous obtenons la propriété suivante, avec $y_D$ le scalaire de sortie prédit :

$$ p_G(x_F) \xrightarrow{y_D \to \frac{1}{2}} p_{data}(x_R). $$

D'autres variantes du GAN sont apparues telles que le DC-GAN [15], qui adapte sa structure au traitement d'images en intégrant des couches convolutives. Le Wasserstein GAN (WGAN) [1] utilise d'une part la distance Earth-Mover (EM) dans sa fonction de coût, et d'autre part limite les valeurs des poids de son modèle à un certain intervalle, afin de rectifier le problème d'instabilité des précédentes versions du GAN.

En raison de leur capacité à apprendre des représentations pertinentes d'un point de vue sémantique et de leur efficacité déjà démontrée en apprentissage semi-supervisé [20], nous avons décidé d'exploiter d'une certaine manière leurs avancages pour une application d'apprentissage PU. Parallèlement à notre étude, l'approche [7] est apparue pour répondre à la même problématique en utilisant un modèle d'apprentissage de type GAN. [7] requière deux modèles génératifs et trois discriminateurs pour l'étape générative contre un générateur et un discriminateur pour notre approche. Cela devrait nous conférer un temps de calcul moindre et un apprentissage mieux maîtrisé. Mais leur étude s'est arrêtée à la description fonctionnelle de leur modèle<fnref n="1" />. Ici, l'approche proposée que l'on nomme Positive-GAN ("PGAN" par la

suite) a été testée sur trois jeux de données différents et dont les résultats sont très prometteurs en termes robustesse et de performance de prédiction pour le traitement d'images complexes. Il surpasse l'état de l'art sur le jeu de données le plus difficile que nous avons testé.

Le document est organisé tel que ci-dessous. Dans la section suivante nous présentons la méthode. Les expérimentations et les résultats sont présentés dans la troisième section. Pour finir, une conclusion est faite sur notre approche et de futures directions de recherche sont suggérées.

## 2 Méthode d'apprentissage propo-sée : Le Positive-GAN

Dans cette section, nous décrivons notre système d'apprentissage PU de manière générique et focalisons la description sur la méthode d'entraînement. Notre méthode d'apprentissage Positive-GAN (PGAN) consiste à substituer l'absence d'échantillons négatifs labélisés $x_N$ avec les faux échantillons $x_F$ générés par notre GAN, dont la distribution est proche au possible de celle des $x_N$, tout en étant différente de celle des échantillons positifs $x_P$. La figure 1 illustre le fonctionnement du système.

<figure><img src="image_38.png" /><figcaption>FIGURE 1 – Système d'apprentissage PU proposé : Positive-GAN.</figcaption></figure>

Lors de l'étape 1, le GAN est entraîné avec les échantillons non labélisés $x_U$ à partir du jeu de données d'entraînement

RJCIA, une nouvelle version de la publication [7] est apparue, en version pre-print, où l'étude de leur méthode a été complétée : Leur nouvelle version datant du 4 avril 2018 inclue une partie théorique et quelques tests comparatifs sur les jeux de données USPS et MNIST auxquels il aurait été pertinent de se comparer, s'il n'y avait pas eu de conflits de dates. Leur nouvelle version nécessite la connaissance à priori de la fraction d'échantillons positifs inclus dans le jeu de données non labélisé pour fonctionner. Les tests ont été réalisés avec une faible proportion d'échantillons positifs labélisés, ce qui met en avant l'intérêt des méthodes génératives pour l'augmentation de dataset. Cependant, des détails sur l'intialisation des hyper-paramètres $\lambda_P$, $\lambda_N$ et $\lambda_U$ auraient été appréciés, ainsi que la réalisation de tests sur des bases de données plus complexes telles que CIFAR-10 avec des structures de type réseaux convolutifs. En effet, bien que leur méthode semble fonctionnelle avec une structure de type perceptron multi-couche, les étapes de convolution rendent plus difficile l'effondrement d'un générateur et donc la divergence de leur générateur $G_N$ pour l'apprentissage de la distribution des échantillons négatifs à partir d'échantillons non labélisés et d'échantillons positifs labélisés.

<footnote n="1">1. À noter qu'après la date de soumission de notre article à CNIA-</footnote>
PU qui contient une fraction $\pi \in (0, 1)$ d'échantillons positifs et une fraction $1 - \pi$ d'échantillons négatifs $x_N$. Le système Positif-Non labélisé inclue trois modèles convolutifs avec différents rôles respectifs :

- Le modèle discriminateur $D_U$ est entraîné à distinguer les vrais échantillons $x_U$ des faux non labélisés générés $x_F$, avec $y_{D_U} \in (0, 1)$ sa valeur de sortie prédite.

- Le modèle génératif $G$ prend en entrée un vecteur de bruit $z$ constitué de variables aléatoires continues, et fournit en sortie, dans le même format que $x_U$, les faux échantillons $x_F = G(z)$. $G$ est entraîné de manière antagoniste à $D_U$ afin de générer des faux échantillons tels que leur distribution $p(x_F)$ tend vers $p(x_U)$.

- Lors de la deuxième étape, une fois que l'entraînement du GAN est considéré comme terminé, le classifieur binaire convolutif $D_B$ est entraîné à distinguer les échantillons réels positifs $x_P$ des faux échantillons $x_F$.

Les explications présentées ci-dessous ont pour objectif de développer l'intuition derrière le système proposé.

Nous rappelons que le jeu de données non labélisé est composé d'une fraction $\pi$ d'échantillons positifs $x_P$ et d'une fraction $1 - \pi$ d'échantillons négatifs $x_N$. Ainsi, si le GAN est correctement entraîné sur les échantillons non labélisés $x_U$, on peut en déduire que :

$$p(x_F) \underset{y_{D_U} \to \frac{1}{2}}{\longrightarrow} p(x_U) \\ \Leftrightarrow p(x_F) \underset{y_{D_U} \to \frac{1}{2}}{\longrightarrow} \pi p(x_P) + (1 - \pi) p(x_N),$$

et l'on admet alors comme forte hypothèse pour la suite que $p(x_F) = \pi p(x_{FP}) + (1 - \pi) p(x_{FN})$, avec :

$$\left\{ \begin{array}{l} p(x_{FP}) \underset{y_{D_U} \to \frac{1}{2}}{\longrightarrow} p(x_P) \\ p(x_{FN}) \underset{y_{D_U} \to \frac{1}{2}}{\longrightarrow} p(x_N). \end{array} \right.$$

Lorsque $y_{D_U} \to \frac{1}{2}$, nous démarrons la deuxième étape du PGAN. Par ailleurs, un GAN n'est pas parfait dans son fonctionnement lorsqu'il se voit être appliqué à des tenseurs de grandes dimensions, ainsi :

$$p(x_{FP}) \neq p(x_P), \text{ et } p(x_{FN}) \neq p(x_N). \quad (1)$$

Il est donc alors possible d'estimer une distance $d$ non nulle dans la fonction de coût du classifieur $D_B$, tel que :

$$d(p(x_P), p(x_F)) \Leftrightarrow \left\{ \begin{array}{l} d(p(x_P), p(x_{FP})) \\ d(p(x_P), p(x_{FN})). \end{array} \right.$$

Mais, bien que calculée, la distance $d(p(x_P), p(x_{FP}))$ n'est pas exploitée dans l'application finale où nous traitons uniquement des échantillons réels avec le classifieur $D_B$. Ainsi, lorsque $p(x_{FN}) \underset{y_{D_U} \to \frac{1}{2}}{\longrightarrow} p(x_N)$ et que $D_B$ a été également correctement entraîné, nous obtenons l'équivalence :

$$d(p(x_P), p(x_{FN})) \Leftrightarrow d(p(x_P), p(x_N)). \quad (2)$$

Nous sommes donc capable de calculer la distance qui nous intéresse. En transférant ce raisonnement dans notre méthode PU, cela revient à affirmer les équivalences suivantes à la sortie de la fonction de coût $L_{DB}$ du classifieur $D_B$ lorsque $y_{D_U} \to \frac{1}{2}$ :

$$\begin{align*} L_{DB} &= \mathbb{E}_{x_P \sim p(x_P)} \log D_B(x_P) \\ &\quad + \mathbb{E}_{z \sim p_z(z)} \log[1 - D_B(G(z))] \\ \Leftrightarrow L_{DB} &= \mathbb{E}_{x_P \sim p(x_P)} \log D_B(x_P) \\ &\quad + \mathbb{E}_{x_N \sim p(x_N)} \log[1 - D_B(x_N)]. \end{align*}$$

Ainsi, grâce à l'hypothèse de fonctionnement proposée ci-dessus on peut affirmer que la méthode PGAN devient similaire à un entraînement sur des échantillons positifs et négatifs respectivement labélisés, tout en s'éloignant d'un entraînement de type apprentissage PU, malgré le fait que le jeu de données que nous utilisons contienne uniquement des échantillons positifs labélisés et des échantillons non labélisés. De plus, intuitivement, calculer $d(p(x_P), p(x_{FP}))$ peut favoriser dans une certaine mesure, l'apprentissage des frontières de $p(x_P)$. Cependant, deux risques peuvent survenir avec cette méthode :

- Si les échantillons $x_U$ contiennent majoritairement des échantillons $x_P$, alors il est possible que $G$ ne soit plus apte à générer suffisamment de faux échantillons similaires aux échantillons $x_N$.

- Si $G$ génère des faux échantillons ayant une distribution égale à celle des vrais échantillons, contrairement à l'inégalité 1, alors le PGAN deviendrait équivalent en termes de performances à un entraînement classique PU. Mais lorsque la dimensionnalité des images à traiter devient large, alors ce risque disparaît. De plus, il peut être atténué en utilisant une structure pour le classifieur $D_B$ dont les performances en prédiction sont meilleures que celles de la structure utilisée pour le discriminateur $D_U$.

Trouver une solution permettant d'éviter ces deux risques de se produire reste une question ouverte très intéressante pour améliorer la fiabilité de la méthode.

# 3 Expérimentations

## 3.1 Réglages des tests

Les expériences ont été réalisées sur les trois jeux de données MNIST [10], Fashion-MNIST [21] et CIFAR-10 [9]. Nous avons comparé notre approche à RP [13], qui est à notre connaissance la meilleure méthode d'apprentissage bruité (noisy learning) et PU ne nécessitant pas de connaissances à priori de la fraction $\pi$. De plus, l'implémentation de l'auteur est disponible$^2$. Nous indiquons aussi la performance du classifieur entraîné sur le jeu de données d'entraînement initial contenant des échantillons entièrement labélisés positifs et négatifs, et nous appelons évidemment cette méthode PN, que nous considérons comme la référence du cadre idéal. Nous comparons aussi le PGAN à un

<footnote n="2">2. https://github.com/cgnorthcutt/rankpruning</footnote>
<table><caption>TABLE 1 – Résultats comparatifs en fonction des F1-Scores mesurés sur MNIST, Fashion-MNIST et CIFAR-10 avec le classifieur entraîné sur 20 époques.</caption><thead><tr><th rowspan="2">Jeux de données</th><th colspan="4">ρ = 0.5, π = 0.1</th><th colspan="4">ρ = 0.5, π = 0.3</th><th colspan="4">ρ = 0.5, π = 0.5</th><th colspan="4">ρ = 0.5, π = 0.7</th></tr><tr><th>PN</th><th>PU</th><th>PGAN</th><th>RP</th><th>PU</th><th>PGAN</th><th>RP</th><th>PU</th><th>PGAN</th><th>RP</th><th>PU</th><th>PGAN</th><th>RP</th><th>PU</th><th>PGAN</th><th>RP</th></tr></thead><tbody><tr><td>0</td><td>0.997</td><td>0.633</td><td>0.974</td><td><strong>0.992</strong></td><td>0.445</td><td><strong>0.973</strong></td><td>0.955</td><td>0.320</td><td>0.973</td><td><strong>0.991</strong></td><td>0.689</td><td><strong>0.902</strong></td><td>0.880</td><td>0.997</td><td>0.633</td><td>0.974</td><td>0.992</td></tr><tr><td>1</td><td>0.998</td><td>0.774</td><td>0.971</td><td><strong>0.995</strong></td><td>0.642</td><td>0.979</td><td><strong>0.996</strong></td><td>0.851</td><td>0.958</td><td><strong>0.994</strong></td><td>0.884</td><td>0.863</td><td><strong>0.993</strong></td><td>0.998</td><td>0.774</td><td>0.971</td><td>0.974</td></tr><tr><td>2</td><td>0.990</td><td>0.395</td><td>0.972</td><td><strong>0.975</strong></td><td>0.658</td><td><strong>0.959</strong></td><td>0.923</td><td>0.795</td><td><strong>0.947</strong></td><td>0.936</td><td>0.692</td><td>0.914</td><td><strong>0.987</strong></td><td>0.990</td><td>0.395</td><td>0.972</td><td>0.975</td></tr><tr><td>3</td><td>0.996</td><td>0.716</td><td>0.963</td><td><strong>0.991</strong></td><td>0.620</td><td>0.953</td><td><strong>0.991</strong></td><td>0.766</td><td><strong>0.934</strong></td><td>0.882</td><td>0.729</td><td><strong>0.885</strong></td><td>0.829</td><td>0.996</td><td>0.716</td><td>0.963</td><td>0.963</td></tr><tr><td>4</td><td>0.997</td><td>0.512</td><td>0.964</td><td><strong>0.972</strong></td><td>0.802</td><td>0.952</td><td><strong>0.995</strong></td><td>0.717</td><td><strong>0.945</strong></td><td>0.933</td><td>0.551</td><td>0.914</td><td><strong>0.977</strong></td><td>0.997</td><td>0.512</td><td>0.964</td><td>0.964</td></tr><tr><td>5</td><td>0.993</td><td>0.701</td><td>0.974</td><td><strong>0.985</strong></td><td>0.725</td><td><strong>0.950</strong></td><td>0.943</td><td>0.799</td><td><strong>0.949</strong></td><td>0.910</td><td>0.626</td><td>0.873</td><td><strong>0.973</strong></td><td>0.993</td><td>0.701</td><td>0.974</td><td>0.974</td></tr><tr><td>6</td><td>0.992</td><td>0.708</td><td><strong>0.962</strong></td><td>0.928</td><td>0.758</td><td>0.959</td><td><strong>0.992</strong></td><td>0.699</td><td>0.971</td><td><strong>0.993</strong></td><td>0.613</td><td>0.944</td><td><strong>0.990</strong></td><td>0.992</td><td>0.708</td><td><strong>0.962</strong></td><td>0.928</td></tr><tr><td>7</td><td>0.995</td><td>0.603</td><td><strong>0.962</strong></td><td>0.947</td><td>0.433</td><td>0.960</td><td><strong>0.991</strong></td><td>0.620</td><td>0.926</td><td><strong>0.988</strong></td><td>0.783</td><td>0.737</td><td><strong>0.979</strong></td><td>0.995</td><td>0.603</td><td><strong>0.962</strong></td><td>0.947</td></tr><tr><td>8</td><td>0.995</td><td>0.741</td><td><strong>0.949</strong></td><td>0.929</td><td>0.506</td><td>0.941</td><td><strong>0.982</strong></td><td>0.339</td><td>0.922</td><td><strong>0.941</strong></td><td>0.651</td><td><strong>0.849</strong></td><td>0.818</td><td>0.995</td><td>0.741</td><td><strong>0.949</strong></td><td>0.929</td></tr><tr><td>9</td><td>0.981</td><td>0.785</td><td><strong>0.959</strong></td><td>0.954</td><td>0.442</td><td>0.956</td><td><strong>0.979</strong></td><td>0.561</td><td>0.939</td><td><strong>0.941</strong></td><td>0.750</td><td>0.865</td><td><strong>0.904</strong></td><td>0.981</td><td>0.785</td><td><strong>0.959</strong></td><td>0.954</td></tr><tr><td>AVG<sub>MNIST</sub></td><td>0.993</td><td>0.657</td><td>0.965</td><td><strong>0.967</strong></td><td>0.603</td><td>0.958</td><td><strong>0.975</strong></td><td>0.647</td><td>0.946</td><td><strong>0.951</strong></td><td>0.697</td><td>0.875</td><td><strong>0.933</strong></td><td>0.993</td><td>0.657</td><td>0.965</td><td>0.965</td></tr><tr><td>T-shirt/top</td><td>0.908</td><td>0.724</td><td><strong>0.926</strong></td><td>0.899</td><td>0.206</td><td>0.91</td><td><strong>0.937</strong></td><td>0.821</td><td>0.873</td><td><strong>0.947</strong></td><td>0.695</td><td>0.802</td><td><strong>0.91</strong></td><td>0.908</td><td>0.724</td><td><strong>0.926</strong></td><td>0.899</td></tr><tr><td>Trouser</td><td>0.993</td><td>0.815</td><td>0.983</td><td><strong>0.993</strong></td><td>0.247</td><td>0.969</td><td><strong>0.989</strong></td><td>0.938</td><td>0.953</td><td><strong>0.99</strong></td><td>0.681</td><td>0.911</td><td><strong>0.984</strong></td><td>0.993</td><td>0.815</td><td>0.983</td><td>0.983</td></tr><tr><td>Pullover</td><td>0.932</td><td>0.635</td><td><strong>0.9</strong></td><td>0.887</td><td>0.29</td><td>0.885</td><td><strong>0.925</strong></td><td>0.695</td><td>0.865</td><td><strong>0.917</strong></td><td>0.657</td><td>0.842</td><td><strong>0.888</strong></td><td>0.932</td><td>0.635</td><td><strong>0.9</strong></td><td>0.887</td></tr><tr><td>Dress</td><td>0.952</td><td>0.601</td><td>0.941</td><td><strong>0.948</strong></td><td>0.312</td><td>0.925</td><td><strong>0.955</strong></td><td>0.852</td><td>0.893</td><td><strong>0.914</strong></td><td>0.631</td><td>0.853</td><td><strong>0.882</strong></td><td>0.952</td><td>0.601</td><td>0.941</td><td>0.948</td></tr><tr><td>Coat</td><td>0.882</td><td>0.614</td><td><strong>0.909</strong></td><td>0.847</td><td>0.252</td><td>0.889</td><td><strong>0.942</strong></td><td>0.788</td><td>0.845</td><td><strong>0.92</strong></td><td>0.686</td><td>0.83</td><td><strong>0.918</strong></td><td>0.882</td><td>0.614</td><td><strong>0.909</strong></td><td>0.847</td></tr><tr><td>Sandal</td><td>0.995</td><td>0.793</td><td>0.945</td><td><strong>0.977</strong></td><td>0.444</td><td>0.964</td><td><strong>0.98</strong></td><td>0.819</td><td>0.923</td><td><strong>0.985</strong></td><td>0.67</td><td>0.919</td><td><strong>0.981</strong></td><td>0.995</td><td>0.793</td><td>0.945</td><td>0.945</td></tr><tr><td>Shirt</td><td>0.818</td><td>0.446</td><td><strong>0.852</strong></td><td>0.758</td><td>0.398</td><td>0.846</td><td><strong>0.847</strong></td><td>0.797</td><td>0.819</td><td><strong>0.873</strong></td><td>0.554</td><td>0.792</td><td><strong>0.853</strong></td><td>0.818</td><td>0.446</td><td><strong>0.852</strong></td><td>0.758</td></tr><tr><td>Sneaker</td><td>0.983</td><td>0.73</td><td><strong>0.973</strong></td><td><strong>0.973</strong></td><td>0.271</td><td>0.952</td><td><strong>0.979</strong></td><td>0.865</td><td>0.943</td><td><strong>0.967</strong></td><td>0.64</td><td>0.922</td><td><strong>0.977</strong></td><td>0.983</td><td>0.73</td><td><strong>0.973</strong></td><td><strong>0.973</strong></td></tr><tr><td>Bag</td><td>0.989</td><td>0.772</td><td><strong>0.978</strong></td><td>0.976</td><td>0.536</td><td>0.947</td><td><strong>0.99</strong></td><td>0.837</td><td>0.96</td><td><strong>0.965</strong></td><td>0.685</td><td>0.757</td><td><strong>0.977</strong></td><td>0.989</td><td>0.772</td><td><strong>0.978</strong></td><td>0.976</td></tr><tr><td>Ankle boot</td><td>0.985</td><td>0.704</td><td>0.964</td><td><strong>0.979</strong></td><td>0.354</td><td>0.973</td><td><strong>0.986</strong></td><td>0.824</td><td>0.963</td><td><strong>0.976</strong></td><td>0.609</td><td>0.942</td><td><strong>0.976</strong></td><td>0.985</td><td>0.704</td><td>0.964</td><td>0.964</td></tr><tr><td>AVG<sub>F-MNIST</sub></td><td>0.944</td><td>0.683</td><td><strong>0.937</strong></td><td>0.924</td><td>0.331</td><td>0.926</td><td><strong>0.953</strong></td><td>0.824</td><td>0.904</td><td><strong>0.945</strong></td><td>0.651</td><td>0.857</td><td><strong>0.935</strong></td><td>0.944</td><td>0.683</td><td><strong>0.937</strong></td><td>0.924</td></tr><tr><td>Plane</td><td>0.727</td><td>0.341</td><td><strong>0.818</strong></td><td>0.669</td><td>0.557</td><td>0.784</td><td><strong>0.795</strong></td><td>0.295</td><td><strong>0.758</strong></td><td>0.743</td><td>0.621</td><td><strong>0.731</strong></td><td>0.718</td><td>0.727</td><td>0.341</td><td><strong>0.818</strong></td><td>0.669</td></tr><tr><td>Auto</td><td>0.78</td><td>0.506</td><td><strong>0.801</strong></td><td>0.695</td><td>0.492</td><td>0.737</td><td><strong>0.829</strong></td><td>0.414</td><td>0.789</td><td><strong>0.798</strong></td><td>0.521</td><td>0.734</td><td><strong>0.783</strong></td><td>0.78</td><td>0.506</td><td><strong>0.801</strong></td><td>0.695</td></tr><tr><td>Bird</td><td>0.447</td><td>0.175</td><td><strong>0.688</strong></td><td>0.56</td><td>0.439</td><td><strong>0.744</strong></td><td>0.68</td><td>0.184</td><td><strong>0.694</strong></td><td>0.644</td><td>0.359</td><td><strong>0.688</strong></td><td>0.542</td><td>0.447</td><td>0.175</td><td><strong>0.688</strong></td><td>0.56</td></tr><tr><td>Cat</td><td>0.5</td><td>0.125</td><td><strong>0.658</strong></td><td>0.384</td><td>0.272</td><td><strong>0.722</strong></td><td>0.651</td><td>0.249</td><td><strong>0.718</strong></td><td>0.67</td><td>0.446</td><td>0.69</td><td><strong>0.698</strong></td><td>0.5</td><td>0.125</td><td><strong>0.658</strong></td><td>0.384</td></tr><tr><td>Deer</td><td>0.698</td><td>0.272</td><td><strong>0.68</strong></td><td>0.605</td><td>0.232</td><td><strong>0.708</strong></td><td><strong>0.708</strong></td><td>0.3</td><td><strong>0.708</strong></td><td>0.64</td><td>0.43</td><td><strong>0.633</strong></td><td>0.602</td><td>0.698</td><td>0.272</td><td><strong>0.68</strong></td><td>0.605</td></tr><tr><td>Dog</td><td>0.567</td><td>0.2</td><td><strong>0.632</strong></td><td>0.539</td><td>0.37</td><td><strong>0.756</strong></td><td>0.648</td><td>0.258</td><td><strong>0.746</strong></td><td>0.733</td><td>0.514</td><td>0.678</td><td><strong>0.712</strong></td><td>0.567</td><td>0.2</td><td><strong>0.632</strong></td><td>0.539</td></tr><tr><td>Frog</td><td>0.691</td><td>0.35</td><td><strong>0.837</strong></td><td>0.666</td><td>0.418</td><td>0.793</td><td><strong>0.794</strong></td><td>0.256</td><td><strong>0.788</strong></td><td>0.769</td><td>0.693</td><td><strong>0.75</strong></td><td>0.749</td><td>0.691</td><td>0.35</td><td><strong>0.837</strong></td><td>0.666</td></tr><tr><td>Horse</td><td>0.786</td><td>0.373</td><td><strong>0.693</strong></td><td>0.653</td><td>0.515</td><td><strong>0.757</strong></td><td>0.723</td><td>0.26</td><td>0.751</td><td><strong>0.759</strong></td><td>0.611</td><td>0.675</td><td><strong>0.711</strong></td><td>0.786</td><td>0.373</td><td><strong>0.693</strong></td><td>0.653</td></tr><tr><td>Ship</td><td>0.832</td><td>0.313</td><td><strong>0.821</strong></td><td>0.764</td><td>0.565</td><td>0.809</td><td><strong>0.831</strong></td><td>0.324</td><td>0.775</td><td><strong>0.785</strong></td><td>0.623</td><td>0.716</td><td><strong>0.755</strong></td><td>0.832</td><td>0.313</td><td><strong>0.821</strong></td><td>0.764</td></tr><tr><td>Truck</td><td>0.771</td><td>0.462</td><td><strong>0.822</strong></td><td>0.685</td><td>0.367</td><td><strong>0.786</strong></td><td>0.637</td><td>0.272</td><td><strong>0.754</strong></td><td>0.617</td><td>0.539</td><td><strong>0.724</strong></td><td>0.564</td><td>0.771</td><td>0.462</td><td><strong>0.822</strong></td><td>0.685</td></tr><tr><td>AVG<sub>CIFAR-10</sub></td><td>0.680</td><td>0.312</td><td><strong>0.745</strong></td><td>0.622</td><td>0.423</td><td><strong>0.760</strong></td><td>0.730</td><td>0.281</td><td><strong>0.748</strong></td><td>0.716</td><td>0.536</td><td><strong>0.702</strong></td><td>0.684</td><td>0.680</td><td>0.312</td><td><strong>0.745</strong></td><td>0.622</td></tr></tbody></table>

<figure><img src="image_39.png" /><figcaption>FIGURE 2 – F1-Scores moyens après 20 époques d'entraînement pour le classifieur en fonction du taux $\pi$ qui varie entre 0.1 et 0.9 avec un pas de 0.1, pour PN (vert), PU (rouge), RP (bleu) et PGAN (orange) sur MNIST (a), Fashion-MNIST (b) et CIFAR-10 (c).</figcaption></figure>
entraînement que l'on nomme PU, qui est équivalent à PN, mais avec une substitution des échantillons négatifs par des échantillons non labélisés.

Pour ces expérimentations, les méthodes PN, PU, RP et PGAN sont testées avec exactement le même classifieur convolutif afin d'être impartial. Nous avons utilisé le modèle convolutif de classification d'imagettes proposé par tensor-flow<fnref n="3" /> pour rester générique. Il contient deux couches convolutives successives, respectivement suivies d'une étape de max-pooling, et se finit par deux couches entièrement connectées consécutives. La fonction d'activation en sortie de chaque couche est ReLU, mis à part pour la dernière où softmax est appliquée. Nous avons uniquement modifié la dimension de sortie de la dernière couche que l'on fait passer de 10 neurones à 2, afin d'être adapté à notre tâche de classification binaire. Le classifieur est entraîné sur 20 époques. Pour les images 32x32x3 de CIFAR-10, les largeurs et longueurs des tenseurs d'entrée et de sortie des deux couches convolutives sont adaptées, et la profondeur des filtres à noyaux de la première couche convolutive est établie à 3 afin de correspondre aux trois cannaux de ces images RVB. Mais le nombre de filtres et leurs largeur et longueur restent inchangés.

Pour l'étape générative du PGAN, nous avons associé la méthode d'entraînement du WGAN [1] à l'architecture du DCGAN [15] en raison de leurs performances. À noter qu'avec la distance EM, $p(x_F)$ tend vers $p(x_U)$ lorsque $y_{DU}$ tend vers 0. Bien que cela ne soit pas une nécessité, dans le cadre de ces expériences, le vecteur de bruit d'entrée $z$ est constitué de variables aléatoires continues de distributions uniformes. La durée d'entraînement de notre modèle génératif dépend de la complexité du jeu de données à traiter : 10 époques pour MNIST, 20 pour Fashion-MNIST, et 100 pour CIFAR-10. Pour ce dernier, nous faisons les mêmes modifications dans la structure de $D_U$ et $G$, tel que cela a été expliqué précédemment pour le classifieur.

Au sujet de la création de notre jeu de données d'entraînement, $\rho$ correspond à la fraction d'échantillons positifs du jeu de données initial qui contient $n_P$ échantillons positifs. Ces $\rho \times n_P$ échantillons collectés sont ensuite introduits dans notre jeu de données non-labellisé $U_{train}$, qui contient initiallement uniquement des échantillons négatifs $N$ dont le nombre total est $n_N$. $\pi$ est la fraction d'échantillons positifs $P$ que l'on impose dans le jeu de données non labelisée d'entraînement $U_{train}$. Pour se faire, nous retirons de $U_{train}$ un certain nombre d'échantillons négatifs que nous n'exploitons pas, de manière à respecter $\pi$. $U_{train}$ contient alors à la fois des $N$ et des $P$ selon les paramètres $\rho$ et $\pi$. Nous établissons qu'avec $\pi \in [\frac{1}{\rho}, \frac{1}{n_P}+1)$, $\rho \in (0, 1)$, nous pouvons alors obtenir consécutivement, avec $P_{train}$ l'ensemble d'échantillons positifs d'entraînement, les deux jeux de données d'entraînement suivants :

$$P_{train} = \{(1 - \rho) n_P P; 0 \le N\},$$

$$U_{train} = \{\rho n_P P; \frac{1-\rho}{\pi} \rho n_P N\},$$

où les notations $a P$ et $b N$ désignent respectivement $a$ éléments positifs et $b$ éléments négatifs.

Pour trouver les équations définissant $U_{train}$ selon les paramètres $\pi$ et $\rho$, et l'intervalle des valeurs possibles pour $\pi$, nous utilisons $n_U$ qui représente le nombre total d'échantillons non labélisés contenus dans l'ensemble $U_{train}$, tel que :

$$ \begin{aligned} U_{train} &= \{\pi n_U P; (1-\pi)n_U N\} \\ &= \{\rho n_P P; (1-\rho)\frac{\rho n_P}{\pi} N\}, \end{aligned} $$

car nous imposons $\rho n_P = \pi n_U$.

Or, pour que cela soit réalisable, il faut que $(1 - \pi)\frac{\rho n_P}{\pi}$ soit inférieur ou égal à $n_N$. Cela revient donc à dire que $\pi \in [\frac{1}{\rho}, \frac{1}{n_P}+1)$.

Les résultats présentés ci-dessous sont tous réalisés avec $\rho = 0.5$ et pour plusieurs valeurs de $\pi$.

## 3.2 Résultats

<figure><img src="image_40.png" /><figcaption>FIGURE 3 – Images générées par $G$ avec $\rho = 0.5$ et $\pi = 0.5$ après 10 époques sur MNIST (a), 20 sur Fashion-MNIST (b), et 100 sur CIFAR-10 (c). Les classes positives respectives sont ici "5", "trouser" and "automobile".</figcaption></figure>

Dans la figure 3, nous présentons quelques fausses images générées par $G$, respectivement pour MNIST, Fashion-MNIST et CIFAR-10. Nous pouvons remarquer que les images générées par $G$ semblent visuellement acceptables, ce qui indique d'un point de vue qualitatif le bon fonctionnement du modèle génératif. Afin d'obtenir un tel résultat, plus les images sont grandes et complexes, et plus il faut entraîner le GAN sur un grand nombre d'époques.

Pour calculer le F1-Score, la fonction ArgMax est appliquée aux deux neurones de sortie du classifieur. Si l'indice du premier neurone est renvoyé par ArgMax, alors l'échantillon traité est classifié comme négatif. Sinon, il est considéré comme positif. De plus, étant donné que les jeux de données de test contiennent 9 fois plus d'échantillons négatifs que d'échantillons positifs, une fois toutes les prédictions de test réalisées, nous adaptons les proportions des échantillons négatifs à celle des positifs de manière à obtenir un F1-Score pertinent. Le tableau 1 montre une partie des F1-Scores comparatifs mesurés pour chaque classe pour chacun des trois jeux de données exploités, et respectivement pour chaque méthode testée. Sur Fig. 2, il peut être

<footnote n="3">3. https://github.com/tensorflow/tensorflow/blob/master/tensorflow/examples/tutorials/mnist/mnistSoftmax.py</footnote>
observé que la méthode PN est une bonne référence sur MNIST et Fashion-MNIST. Nous trouvons que l'efficacité de la méthode d'apprentissage PGAN est équivalente à celle de la méthode RP jusqu'à $\pi = 0.5$ sur MNIST et $\pi = 0.3$ sur Fashion-MNIST. Son efficacité décline ensuite un peu plus vite que pour RP, mais tout en conservant un score acceptable. Sur CIFAR-10 le F1-Score moyen est systématiquement meilleur pour notre méthode PGAN. Aussi, notre méthode présente de meilleurs résultats que la référence PN jusqu'à $\pi = 0.8$, ce qui est très intéressant. Cela est probablement dû au fait que les échantillons générés représentent une plus grande variété de distributions d'échantillons néga-tifs que celles inclues dans le jeu de données initial. De plus, le F1-Score du PGAN est significativement et systématiquement meilleur que la méthode PU sur l'ensemble des trois jeux de données, même avec seulement 10% d'échantillons positifs parmis les échantillons non labélisés, autrement dit avec $\pi = 0.1$.

La figure 4 présente l'étude de la robustesse de l'approche PGAN. Les figures 4.a et 4.b montrent que la méthode PGAN a comparativement à RP une meilleure stabilité dans son fonctionnement de manière à permettre de prédire plus facilement l'évolution de son F1-Score en fonction de $\pi$ pour chaque classe du jeu de données. La figure 4.c nous montre que le classifieur se stabilise et converge après 10 époques d'entraînement. Pour réaliser l'histogramme de la figure. 4.d, nous avons récupéré la valeur du deuxième neurone de sortie du classifieur qui correspond à la probabilité prédite pour une image d'appartenir à la classe positive. On peut observer que les distributions respectives des échantillons de test positifs et négatifs estimées par le PGAN sont de forme gaussienne, ce qui est une caractéristique intéressante pour des applications réelles.

<table><caption>TABLE 2 – Stabilité moyenne des performances (F1-Scores) des méthodes PGAN et RP en fonction de $\pi$ sur les jeux de données MNIST, Fashion-MNIST et CIFAR-10</caption><thead><tr><th>jeux de données</th><th>PGAN</th><th>RP</th><th>E<sub>RP</sub>/E<sub>PGAN</sub></th></tr></thead><tbody><tr><td>MNIST</td><td><strong>0.00039</strong></td><td>0.00172</td><td>4.410</td></tr><tr><td>Fashion-MNIST</td><td><strong>0.00016</strong></td><td>0.00025</td><td>1.563</td></tr><tr><td>CIFAR-10</td><td><strong>0.00044</strong></td><td>0.00182</td><td>4.136</td></tr></tbody></table>

En complément aux figures 4.a et 4.b, le tableau 2 présente la quantification des robustesses réalisée pour RP et PGAN en fonction de $\pi$ en ce qui concerne leurs performances de prédiction, pour chacun des trois jeux de données de test. Pour ce faire, nous avons lissé respectivement la courbe $s(\pi)$ de chaque classe représentant l'évolution du F1-Score en fonction de $\pi$. Les courbes lissées $\tilde{s}(\pi)$ ont été obtenues en appliquant un filtre moyen avec un noyau de taille 3. Ensuite, l'erreur quadratique moyenne MSE pour chaque classe est calculée entre $\tilde{s}(\pi)$ et $s(\pi)$ tel que ci-dessous,

avec $k$ le nombre d'échantillons de $\tilde{s}(\pi)$ :

$$MSE = \frac{1}{k} \sum_{i=1}^{k} (\tilde{s}^{(i)} - s^{(i+1)})^2. \quad (3)$$

Puis, nous calculons les erreurs moyennes $E_{PGAN}$ et $E_{RP}$ pour chaque jeu de données, ainsi que le ratio $E_{RP} : E_{PGAN}$. On peut de cette manière constater que notre méthode a systématiquement un comportement plus stable, qui est d'un facteur 4 sur MNIST et CIFAR-10.

## 4 Conclusion

Ainsi, nous avons démontré que l'approche d'apprentissage PU proposée surpasse l'état de l'art sur les images RVB complexes du jeu de données CIFAR-10, et a un comportement plus stable sur l'ensemble des jeux de données testés jusqu'à une fraction acceptable $\pi$ d'échantillons positifs dans le jeu de données non labélisé d'entraînement. Ces résultats sont en cohérence avec le raisonnement formulé et permettent ainsi d'envisager des applications PU sur des données de plus grandes dimensions. Le PGAN ne nécessite pas de connaissances à priori sur la fraction d'échantillons positifs non labélisés. Cependant, il reste à étudier plus en profondeur les risques de fonctionnement indiqués dans la section 1, afin de garantir un fonctionnement idéal pour cette approche.

L'optimisation du système peut se prolonger en testant d'autres récentes variantes du GAN tels que le BEGAN [3], le WGAN-GP [6], ou bien d'autres modèles génératifs de type auto-encodeurs variationnels (VAEs) par exemple, afin de généraliser l'approche proposée aux réseaux génératifs. Une autre idée peut être d'exploiter le vecteur latent $z$ du GAN pour réaliser des opérations arithmétiques linéaires, tel que dans [4], afin de générer des faux échantillons dont on pourrait peut-être ainsi mieux gérer la distribution. Dans cette même idée, trouver un moyen d'exploiter les données positive labélisées pour la phase d'entraînement du générateur est envisagé.

Étant données les performances prometteuses obtenues, une future orientation certaine est d'étendre cette méthode à l'analyse de plus grandes images et donc permettre la réalisation de tâches plus complexes telles que la détection d'objets [19], [11], [17] ou la segmentation sémantique [2].

## Références

[1] M. Arjovsky, S. Chintala, and L. Bottou. Wasserstein generative adversarial networks. In *International Conference on Machine Learning*, pages 214–223, 2017.

[2] V. Badrinarayanan, A. Kendall, and R. Cipolla.SGAN : A deep convolutional encoder-decoder architecture for image segmentation. *IEEE transactions on pattern analysis and machine intelligence*, 39(12):2481–2495, 2017.
<figure><img src="image_41.png" /><figcaption>(a)</figcaption></figure>

<figure><img src="image_42.png" /><figcaption>(c)</figcaption></figure>

<figure><img src="image_43.png" /><figcaption>(b)</figcaption></figure>

<figure><img src="image_44.png" /><figcaption>(d)</figcaption></figure>

FIGURE 4 – Analyse de la robustesse sur MNIST. évolution du F1-Score pour chaque classe en fonction de π pour PGAN (a), et pour RP [13] (b). (c) montre l'évolution de l'Accuracy pendant l'entraînement du PGAN avec la classe positive "5" et π = 0.5. (d) est l'histogramme des distributions des valeurs de sortie du deuxième neurone du classifieur à son 20ème époque d'entraînement de (c) pour les échantillons de test positifs (vert) et négatifs (bleu).

[3] D. Berthelot, T. Schumm, and L. Metz. Began : Boundary equilibrium generative adversarial networks. *arXiv preprint arXiv :1703.10717*, 2017.

[4] P. Bojanowski, A. Joulin, D. Lopez-Paz, and A. Szlam. Optimizing the latent space of generative networks. *arXiv preprint arXiv :1707.05776*, 2017.

[5] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. In *Advances in neural information processing systems*, pages 2672–2680, 2014.

[6] I. Gulrajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and A. C. Courville. Improved training of wasserstein gans. In *Advances in Neural Information Processing Systems*, pages 5769–5779, 2017.

[7] M. Hou, Q. Zhao, C. Li, and B. Chaib-draa. A generative adversarial framework for positive-unlabeled classification. *arXiv preprint arXiv :1711.08054*, 2017.

[8] S. S. Khan and M. G. Madden. One-class classification : taxonomy of study and review of techniques. *The Knowledge Engineering Review*, 29(3) :345–374, 2014.

[9] A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. 2009.

[10] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. *Proceedings of the IEEE*, 86(11) :2278–2324, 1998.

[11] W. Liu, D. Anguelov, D. Erhan, C. Szegedy, S. Reed, C.-Y. Fu, and A. C. Berg. SSD : Single shot multibox detector. In *European Conference on Computer Vision*, pages 21–37. Springer, 2016.

[12] G. Niu, M. C. du Plessis, T. Sakai, Y. Ma, and M. Sugiyama. Theoretical comparisons of positive-unlabeled learning against positive-negative learning. In *Advances in Neural Information Processing Systems*, pages 1199–1207, 2016.
[13] C. G. Northcutt, T. Wu, and I. L. Chuang. Learning with confident examples: Rank pruning for robust classification with noisy labels. In *Proceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence*, UAI’17. AUAI Press, 2017.

[14] M. A. Pimentel, D. A. Clifton, L. Clifton, and L. Ta-rassenko. A review of novelty detection. *Signal Processing*, 99:215–249, 2014.

[15] A. Radford, L. Metz, and S. Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. *arXiv preprint arXiv:1511.06434*, 2015.

[16] A. Rasmus, M. Berglund, M. Honkala, H. Valpola, and T. Raiko. Semi-supervised learning with ladder networks. In *Advances in Neural Information Processing Systems*, pages 3546–3554, 2015.

[17] J. Redmon, S. Divvala, R. Girshick, and A. Farhadi. You only look once: Unified, real-time object detection. In *Proceedings of the IEEE conference on computer vision and pattern recognition*, pages 779–788, 2016.

[18] J. Redmon and A. Farhadi. YOLO9000: Better, Faster, Stronger. *arXiv preprint arXiv:1612.08242*, 2016.

[19] S. Ren, K. He, R. Girshick, and J. Sun. Faster R-CNN: Towards real-time object detection with region proposal networks. In *Advances in neural information processing systems*, pages 91–99, 2015.

[20] T. Salimans, I. Goodfellow, W. Zaremba, V. Cheung, A. Radford, and X. Chen. Improved techniques for training gans. In *Advances in Neural Information Processing Systems*, pages 2234–2242, 2016.

[21] H. Xiao, K. Rasul, and R. Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017.
# Ontologie pour l'intégration de données d'observation de la Terre et contextuelles basée sur les relations topologiques

C. Comparot<fnref n="1" />

C. Trojahn<fnref n="1" />

H. Arenas<fnref n="2" />

N. Aussenac-Gilles<fnref n="2" />

prenom.nom@irit.fr

## Résumé

Nous proposons une ontologie pour l'intégration de données d'observation de la Terre et de données contextuelles, à l'aide de propriétés et de relations spatiales et temporelles. Cette ontologie spécialise les standards SOSA, GeoSPARQL et OWL-Time. La base de connaissances décrite par cette ontologie est alimentée grâce à un processus qui sélectionne, transforme et intègre de données géospatiales hétérogènes (méta-données d'image satellite, données météorologiques, unités administratives, couverture terrestre, etc.). Ce processus s'appuie sur le tuilage des images pour traiter les données ayant une composante spatiale fixe, alors que les relations temporelles sont calculées à la volée à partir d'une topologie temporelle. Nous validons cette approche par un cas d'étude exploitant des méta-données d'image satellite Sentinel.

## Mots Clef

Ontologies, intégration de données, données spatiales et temporelles, SOSA.

## Abstract

We propose an ontology to support the integration of Earth observation data with contextual data, using spatial and temporal properties and relations. This ontology specializes several standard models: SOSA, GeoSPARQL and OWL-Time. The process that feeds the Knowledge Base structured by this ontology selects, transforms and integrates heterogeneous data with spatial features i.e. metadata of satellite images, weather report data, administrative units and land cover. This process relies on image timing to manage data with a fixed spatial property whereas temporal relations are evaluated when needed. We validate our approach on a case-study using the metadata of Sentinel satellite images.

## Keywords

Ontologies, data integration, spatial and temporal data, SOSA.

## 1 Introduction

L'observation de la Terre offre une valeur ajoutée à une grande diversité de domaines. Récemment l'Agence Spatiale Européenne (ESA) a lancé le programme Sentinel avec deux types de satellites, Sentinel-1 et Sentinel-2, qui transmettent des images de haute qualité (entre 8 à 10 To de données quotidiennement). Ces images de la Terre sont captées selon différentes technologies et libres d'accès. Cette disponibilité des données ouvre de nombreuses perspectives économiques grâce à de nouvelles applications dans des domaines aussi variés que l'agriculture, l'environnement, l'urbanisme, l'océanographie ou encore la climatologie. Ces applications métier ont néanmoins un besoin de coupler les images avec des données sur les zones observées. Ces données sont accessibles à partir de différentes sources dans des formats hétérogènes et des temporalités différentes : elles peuvent être statiques, comme les données sur la couverture terrestre, ou dynamiques, comme les observations météo. Elles peuvent être utiles par exemple pour indiquer qu'une image contient une région touchée par un phénomène tel qu'un tremblement de terre ou une canicule, et ensuite pour décider des actions à mener dans cette zone ou conduire à des analyses à plus long terme. Plus encore, en exploitant les caractéristiques spatio-temporelles d'un phénomène (son empreinte spatiale et sa date), il devient possible de savoir si une entité localisée dans l'empreinte de l'image (e.g. une ville) a subi le même phénomène.

Les images satellites étant décrites par des méta-données, le problème revient à intégrer à ces méta-données des données provenant de sources variées et très hétérogènes (format, représentation). L'apport des technologies séman-tiques pour faciliter cette tâche a été démontré dans des travaux antérieurs [25, 26], en particulier grâce à l'utilisation d'ontologies comme représentations formelles des connaissances d'un domaine donné. Ainsi, dans la continuité des travaux sur l'accès et l'intégration de données via les ontologies (i.e.OBDA pour "Ontology-based Data Access" et OBDI pour "Ontology-based Data Integration") [21, 20, 8], nous avons conçu un vocabulaire sé-mantique permettant de représenter les données des diffé-

<footnote n="1">¹ IRIT, CNRS et Université Toulouse 2, France</footnote>

<footnote n="2">² IRIT, CNRS et Université de Toulouse, France</footnote>