%\section{Thème xx : Approches Transversales}
{\it Participants : P. Gérard, R. Kanawati, H. Karoui, C. Rouveirol}

Cet axe rassemble les deux approches qui font collaborer des
techniques d'apprentissage symbolique et numérique, l'apprentissage
par renforcement relationnel d'une part, et le raisonnement à partir
de cas. L'apprentissage par renforcement (A{R}) est une approche
classiquement numérique. Un système automatique d'apprentissage par
renforcement interagit avec son environnement et utilise l'information
récoltée pour apprendre un comportement adéquat. Dans chaque situation
qui peut se présenter, le système cherche à apprendre quelle action il
vaut mieux entreprendre parmi celles qui sont à sa
disposition. L'action la meilleure est celle qui devrait lui permettre
de maximiser un cumul de récompenses scalaires obtenues sur le long
terme. En effet, l'apprentissage se fonde sur une récompense scalaire
sporadique, plus facile à définir par un concepteur que le détail des
actions à entreprendre dans chaque situation possible. Le système
cherche à maximiser le cumul de ces récompenses successives, sans
connaître a priori son environnement, en effectuant un compromis entre
récompenses immédiates et récompenses attendues dans le futur. Les
systèmes d'AR peuvent être envisagés partout où un système autonome
doit s'améliorer au fur et à mesure de son expérience. Les domaines
d'application les plus courants sont la robotique, les jeux vidéo ou
la fabrication industrielle.

Un problème central de l'AR est celui de la généralisation. En effet,
dès que la taille des problèmes augmente, il est illusoire de vouloir
apprendre quelle action entreprendre dans chacune des multiples
situations possibles. Il est alors nécessaire d'utiliser des
représentations propres des espaces d'états et d'actions
de manière non-extensive. Depuis 2001, l'apprentissage par
renforcement relationnel commence à explorer les représentations
relationnelles pour remplacer les représentations attributs-valeurs,
peu concises, peu aisées à généraliser, mais
classiquement utilisées en apprentissage par renforcement. 
Les états et les actions sont alors représentés par des
prédicats relationnels plutôt que par des vecteurs d'attributs. A ce
jour, la plupart des travaux en AR relationnel portent sur les
systèmes de régression relationnelle employés.  Nous envisagerons plutôt
l'adaptation des algorithmes classiques d'apprentissage par
renforcement aux systèmes de PLI employés.

La deuxième approche transversale developpée dans l'équipe \acs{A3}
concerne les travaux menés dans le domaine du raisonnement à partir de
cas (RàPC). Le RàPC est une méthodologie de résolution de problèmes
fondée sur l'adaptation des solutions éprouvées afin de résoudre de
nouveaux problèmes similaires à ceux traités dans le
passé. Naturellement, l'emploi de cette méthodologie ne peut être
envisageable que dans des domaines où des problèmes similaires
acceptent des solutions similaires. La figure \ref{fig-rapc} illustre
le schéma classique d'une application RàPC : une base de cas dits cas
sources regroupe les problèmes résolus et leurs solutions. La
résolution d'un nouveau problème passe par cinq étapes successives :
1) l'élaboration qui permet de déterminer les attributs du nouveau
problème à résoudre (appelé cas cible), 2) la rémémoration qui permet
de trouver les cas sources les plus facilement adaptables par rapport
au cas cible, 3) l'adaptation dont le rôle est de concevoir une
solution au cas cible à partir des solutions appliquées aux cas
sources retenues, 4) la révision de la solution proposée et 5)
l'apprentissage qui permet d'ajouter le nouveau cas résolu si
opportun.

\floatstyle{plain} %<-- sans encadrement des figures
\restylefloat{figure}
\begin{figure}[h]
\centering\noindent
\scalebox{0.50}{\includegraphics{inputs/A3/Figures/cycle.eps}}
\caption{\sl \label{fig-rapc}\textit{Le cycle RàPC}}
\end{figure}

Ainsi, la relation entre le domaine du RàPC et de celui de
l'apprentissage automatique est double: d'une part, la cinquième
phase du cycle RàPC assure une fonction d'apprentissage incrémental et
paresseux, d'autre part des techniques d'apprentissage, numérique et
symbolique, peuvent être employées pour mettre en {\oe}uvre les
différentes phases du cycle RàPC. Nos travaux dans l'équipe \acs{A3}
traitent les deux aspects de la relation entre les deux domaines.

Nous proposons une approche RàPC originale, que nous appelons RàPC
guidé par les données. Selon cette approche, la mémoire d'un système
RàPC est organisée en deux niveaux : la base de cas source et une base
de données brutes qui alimente la base de cas. Le cycle RàPC est
modifié pour assurer une fonction de maintenance permanante du système
(maintenance de la base de cas, des fonctions de similarité et des
connsissance d'adaptation). Dans ce cadre, deux axes de recherche sont
explorés :
\begin{itemize}
\item le dévelopement de systèmes RàPC hybrides combinant des approches symboliques et numériques,
\item le dévelopement de systèmes RàPC coopératifs. 
\end{itemize} 

\subsection{Les axes de recherche}

\begin{description}
\item[Apprentissage par renforcement relationnel]
Le recherche en apprentissage par renforcement relationnel peut pourtant suivre deux
voies complémentaires : d'une part, l'adaptation des algorithmes de
programmation logique inductive (PLI) aux contraintes spécifiques des
problèmes d'apprentissage par renforcement, largement étudiées à
l'heure actuelle dans la communauté de PLI ; d'autre part, l'adaptation
d'algorithmes  de l'état de l'art d'apprentissage par renforcement aux systèmes
de PLI employés, pour l'instant plus confidentielle. 

Dans un premier temps, nous nous intéressons plus à
l'exploitation de la nature relationnelle des données pour améliorer à
la fois les techniques d'AR (indirect, hiérarchique etc) de manière à
produire des algorithmes efficaces. 

\item[Raisonnement à partir de cas] A la différence d'un système RàPC
  classique qui repose pour son fonctionnement sur la disponibilité
  préalable d'une base de cas sources, un système RàPC guidé par les
  données vise à alimenter une base de cas, initialement vide, au fur
  et à mesure de la présentation de nouveaux problèmes à résoudre. La
  mémoire d'un système RàPC guidée par les données est composée de
  deux parties : a) une base de cas source initialement vide et b) une
  base de données brutes contenant des observations sur le système
  cible. Par exemple, dans le cadre d'une application de
  personnalisation automatique de sites Web, les données de trace de
  navigations (i.e. données de log web) constituent la base de données
  brutes, et la base de cas est composée d'un ensemble de motifs de
  navigation qui ont permis de prédire le comportement d'un
  utilisateur du site cible \cite{zehraoui07}.

  Le cycle RàPC classique est modifié afin de prendre en compte la
  nature de la mémoire du système. D'une manière simplifiée, le
  nouveau cycle consiste à explorer la base de données brutes afin de
  proposer des cas sources dits potentiels lorsqu'une des phases de
  recherche, d'adaptation ou de révision du cycle RàPC classique,
  échoue. La phase d'apprentissage est aussi modifiée pour ne retenire
  dans la base de cas que les cas potentiels à partir desquels des
  bonnes solutions ont été derivées. Ce nouveau cycle permet de
  constituer une base de cas qui évolue avec la nature des problèmes à
  résoudre. Des techniques de maintenance asynchrones sont proposées
  afin d'éliminer de la base les cas à faible contribution \cite{MMaRK05}.

  Nous appliquons cette approche dans deux domaines, la {\em
    classification et prédiction de séquences} et les {\em systèmes de
    recommandations coopératifs}. Le premier axe a fait le sujet de la
  thèse de F. Zehraoui où nous avons proposé un système hybride de
  classification et de prédiction de séqeunces de navigation dans un
  site web. Dans ce travail, les étapes de remémoration et
  d'adaptation des cas sont implantées sous forme d'une carte
  auto-organisatrice (la carte M-SOM-ART \cite{Zehraoui:2004xc}) conçue
  pour la classification des séquences et qui possède les deux
  propriétés de plasticité et de stabilité.  Le deuxième axe fait le
  sujet de la thèse de H. Karoui. Une application pilote de partage et
  de recommendation de références bibliographiques est
  développée. Chaque utilisateur est assisté par un agent personel qui
  observe ses actions afin de détecter ses centres d'intérêt et qui
  coopère avec les autrs agents afin de recommander de nouvelles
  références pertinentes pour l'utilisateur associé. Chaque agent
  implante deux systèmes RàPC guidés par les données afin de 1)
  calculer les recommandations \cite{karoui06b} et 2) apprendre à associer une
  communauté d'agents à chaque centre d'intérêt détecté \cite{karoui06d}.
\end{description}

\subsection{Domaines d'applications}
Un domaine d'applications priviligié pour nos travaux en RàPC concerne le dévelopement de système de recommandations \cite{RK07}. Deux champs d'activités sont particulièrement visés:
\begin{itemize}
\item le commerce électronique. Notre approche de traitement et de
  classification de séquences a été appliquée pour prédire le
  comportement d'utilisateurs d'un site de E-commerce afin de
  reconnaître leur intention (i.e. achat ou non achat). Le site peut
  alors être adapté dynamiquement en fonction de la classe
  prédite. Cette même approche peut servir aussi pour l'adaptation
  dynamique d'un site web afin de proposer des raccourcis de
  navigation.
\item l'accès coopératif et intelligent à l'information
  distribuée. Notre objectif est de permettre à un groupe organisé
  d'utilisateurs (ex. équipe de recherche) de partager, d'une manière
  implicite et automatique, leurs expériences de recherche
  d'information. Trois applications différentes, construites selon la
  même architecture de type égal-à-égal (P2P), sont proposées : une
  application de partage de signets web {\cite{RK07}}, une application de
  recommandation de références bibliographiques \cite{HK-RK-LP-SGAI-06} et un
  méta-moteur de recherche d'information sur le web orienté communautés
  \cite{kanawati07b}.
\end{itemize}

\subsection{Résultats significatifs}
Sur le plan théorique les résultats les plus signficatifs sont :
\begin{itemize}
\item la définition et la validation de l'approche RàPC guidée par les
  données \cite{MMaRK05}
\item la proposition et la validation d'un système hybride RàPC connexionniste pour la classification et la prédiction de séquences \cite{zehraoui07}
\end{itemize}

Sur le plan applicatif, les réalisations les plus significatives sont :
\begin{itemize}
\item Le prototype COBRAS: un système égal à égal pour la
  recommandation de références bibliographiques. Ce système implante
  une approche RàPC pour la formation de comité dans les systèmes de
  type égal à égal \cite{karoui06b} 
\item Le prototype d'un moteur de recherche orienté communauté. Le principe est d'explorer les traces de l'utilisdation du moteur par une communauté d'utilisateurs afin d'améliorer le tri des résultats obtenus par des moteurs classiques de recherche sur le web \cite{kanawati03b,kanawati07b}.
\end{itemize}

\subsection{Perspectives de recherche}
L'axe d'apprentissage par renforcement relationnel est un axe qui
débute tout juste, et qui est amené à se développer dans le futur. 
Il s'agit d'un travail novateur et
exploratoire qui permet en outre d'initier une collaboration entre le
LIPN et l'équipe de Luc de Raedt de l'Université Catholique de Leuven
(Belgique).


En ce qui concerne l'axe RàPC, deux axes de recherche reliés sont en
cours d'exploration :
\begin{itemize}
\item {\bf L'apprentissage coopératif}. Deux problèmes nous semblent
  particulièrement intéressants : 1) l'identification de commaunautés
  d'experts dans un système RàPC coopératif et 2) l'étude des
  différents niveaux de coopération envisageables entre des systèmes
  RàPC autonomes. En ce qui concerne le premier problème, nous
  explorons une approche fondée sur l'utilisation des systèmes de
  réputations et d'analyse de communautés web. En ce qui concerne le deuxième problème, les travaux dans
  l'état de l'art se concentrent sur des stratégies d'échange de cas
  entre systèmes RàPC autonomes afin d'améliorer les performances
  globales du système. Nous voudrons explorer l'utilité d'autres types
  de coopération notamment la coopération pour la mise en place de
  chacune des phases du raisonnement, en particulier les phases de la
  recherche et de l'adaptation. Des algorithmes coopératifs pour le
  calcul de similarité de structures complexes (i.e. des séquences,
  des graphes) sont aussi à l'étude.
\item {\bf Techniques RàPC pour l'analyse des réseaux
    sociaux}. L'objectif est d'explorer l'application de la
  méthodologie RàPC guidé par les données dans des tâches
  d'identification des réseaux sociaux par l'exploration des traces
  d'interactions entre acteurs, mais aussi pour des tâches d'analyse
  des réseaux identifiés notamment pour la prédiction de l'évolution
  des réseaux et pour la prédiction de flux d'influences dans ce type
  de réseaux. Les systèmes de recommandation restent des applications
  cibles favorites, où les réseaux sociaux peuvent être employés à la
  fois pour enrichir les profils utilisateurs mais aussi pour cibler
  les utilisateurs de manière à augmenter l'impact des recommendations
  dans une communauté cible.
\end{itemize}