%\section{Composante Apprentissage Symbolique}
{\it Participants : E. Alphonse, D. Bouthinon, M. Champesme, M. Elati, A. Osmani, C. Rouveirol, H. Soldano.}

Cet axe a pour but d'appréhender des quantités de données importantes
(cf. fouille de données) décrites de manière symbolique, i.e., telle
que les exemples et les hypothèses sont représentés par des formules
logiques. Dans ce cas, les exemples ainsi que les hypothèses
candidates pour le concept cible sont organisés dans des espaces
fortement structurés.  Les techniques d'apprentissage symbolique, par
opposition aux techniques d'apprentissage numérique, vont explorer
l'espace des hypothèses en tirant parti de la structure de l'espace de
recherche imposée par la relation structurant l'espace, afin d'identifier une
hypothèse satisfaisant des critères de couverture de l'ensemble
d'apprentissage.

L'équipe couvre un large spectre de techniques d'apprentissage
(apprentissage supervisé, apprentissage descriptif), et conçoit des
systèmes d'apprentissage pour des langages de concept allant de la
logique attribut-valeur à des restrictions de la logique des prédicats
comme Datalog non récursif avec négation. Orthogonalement, des travaux
sont menés sur un nouveau cadre d'apprentissage permettant de
formaliser l'apprentissage en présence d'exemples incomplets ou
incertains. 

Nous avons poursuivi des travaux dans le domaine de
l'apprentissage attribut-valeur, sur le thème des treillis de Galois
emboîtés et développé et étudié les performances d'un système
d'apprentissage multi-agent. L'équipe est également active dans le domaine de
l'apprentissage de structures (séquences, graphes) et en Programmation
Logique Inductive, domaine dédié à l'Apprentissage Symbolique dans des
langages de concepts restrictions de la logique du premier ordre.  Ces
langages de concept complexes sont requis dans le cadre d'applications
en fouille de données issues du Web (link mining, graph mining), de
développements en Bases de Données Inductives ou d'applications dans
les domaines du Traitement Automatique de la Langue, de la Bio-chimie
ou de la Bioinformatique.

Dans ces langages, les mécanismes associés à l'apprentissage sont
coûteux (voire indécidables), la recherche heuristique joue donc un
rôle primordial. Nous avons développé une nouvelle stratégie
d'apprentissage relationnel efficace, fondées sur un changement de
représentation, appelé propositionnalisation, qui projette un problème
d'apprentissage en un problème attribut-valeur. Enfin, nous étudions
les phénomènes de transition de phase liés à l'apprentissage
relationnel et leurs effets sur l'efficacité de la recherche
d'hypothèses, comme l'apparition d'importants phénomènes de plateaux au cours
de la recherche d'une hypothèse candidate, rendant ``aveugle'' le
système d'apprentissage. \\

\subsection{Les axes de recherche}

\begin{description}
\item[Treillis de Galois emboîtés - constructions de taxonomies]~\\

Notre travail utilise essentiellement des structures latticielles basées
sur des correspondances de Galois définies entre les objets observés et
leur description.  L'inconvénient principal de ces structures est leur
grande taille (en nombre de n{\oe}uds) qui en rend très difficile
l'exploration directe par l'utilisateur, nous avons défini une notion de
<<projection>> sur l'ensemble des objets que nous utilisons pour faire
varier la granularité de cette structure en offrant à l'utilisateur la
possibilité d'explorer les données selon un point de vue d'abord
grossier (pour appréhender globalement l'ensemble des données) puis de
plus en plus détaillé à mesure que l'intérêt de l'utilisateur se
focalise.  


\floatstyle{plain} %<-- sans encadrement des figures
\restylefloat{figure}
\begin{figure}[h]
\centering\noindent
\includegraphics[width=0.8\textwidth]{inputs/A3/Figures/Galicia}\\
\caption{\small La plate-forme Galicia étendue pour la prise en compte de la projection alpha
(ici, treillis construit sur les données C/NET pour $\alpha = 60\%$)}
%  \label{fig:budget_ratio_cercle}
\end{figure}
\floatstyle{boxed} %<-- avec encadrement des figures
\restylefloat{figure}


La notion de projection "alpha" \cite{Ventos:2005vp} 
(cas particulier de
projection que nous avons définie) permet en outre d'utiliser, quand
elle existe, une partition des objets en classes, l'exploration des
données étant alors guidée par cette partition. L'utilisation de
telles partitions nous permet alors d'ignorer des propriétés marginales
des objets, de manière analogue aux théories avec défauts exceptions,
mais en restant dans le cadre théorique simple des correspondances de
Galois "ordinaires" (i.e. domaine de l'analyse formelle de concept).
Notre travail s'intéresse par ailleurs à l'extraction des règles 
induites par cette structuration.

\item [Apprentissage dans un système multi-agents cognitif]~\\

Dans le cadre de la thèse d'A. Guerra Hernandez, nous nous
sommes intéressés avec A. Elfallah-Segrouchni, à l'apprentissage
symbolique multi-agents. Le SMA considéré est composé d'agents
communicants de type BDI (Beliefs, Desires, Intentions).  Au niveau
collectif, un groupe d'agents BDI améliore son apprentissage de
contextes de plans en échangeant des croyances avec d'autres agents
\cite{Guerra-Hernandez:2004xi}. Nous nous intéressons
actuellement à l'apprentissage incrémental collectif dans les Systèmes
Multi-Agents dans le cas où les agents sont complètement autonomes.  


\item[Analyse de l'information mise en jeu au cours de l'apprentissage]~\\ 

  Ce thème s'articule autour de 2 axes.  D'une part, nous avons
  proposé une formalisation en logique du premier ordre de différents
  cadres d'apprentissage dont les données recèlent des formes variées
  d'incomplétude ou d'ambiguïté. En particulier, nous présentons un
  nouveau cadre d'apprentissage qui rend compte de situations
  jusqu'ici inexprimables du fait de la nature de l'incomplétude
  (incertitude sur les exemples positifs et négatifs + abstraction).
  Ce cadre permet de plus de représenter tout problème d'apprentissage
  multi-instances introduit par Dietterich ou d'apprentissage par
  satisfiabilité introduit par de Raedt.

D'autre part, nous menons une analyse de l'information mise en jeu au
    cours de l'apprentissage, qui vise à identifier et quantifier
    l'information fournie à l'apprenant.  Le modèle d'information que
    nous proposons, fondé sur la théorie de l'information, permet de
    mesurer et comparer l'information apportée par différents types
    d'exemples incomplets ou ambigus. En particulier, nous mettons en
    évidence un fort déséquilibre informationnel entre les exemples
    positifs et négatifs en apprentissage multi-instances.  Un
    approfondissement de cet axe nous a permis d'établir des
    définitions et propriétés relatives à la corrélation existant
    entre éléments informationnels.  Nous démontrons qu'un ensemble
    d'éléments informationnels apporte plus d'information que la somme
    des contributions de chacun d'eux. Enfin nous avons exhibé un
    critère informationnel permettant de guider des changements
    dynamiques de représentations au sein d'un espace de
    représentations possibles.

\item [Apprentissage de structures]~\\

Nous nous intéressons à deux types de structures qui
apparaissent dans un grand nombre d'applications, notamment en
Bioinformatique: les séquences et les graphes. En ce qui concerne la
recherche de structures séquentielles, nous avons
travaillé sur la détection de {\em motifs relationnels répétés} dans les
séquences, c'est-à-dire de motifs décrivant non seulement leurs
composants mais aussi les relations qui les lient. L'algorithme
KMRRelat et les conditions de son application à la recherche de motifs
structuraux 3D sur les protéines ont fait l'objet de la thèse de N.
El-Zant. Des recherches récentes nous ont conduits, avec N. Pisanti,
en post-doc \acs{CNRS} au \acs{LIPN}, et M. Carpentier 
(thèse en sciences de la Vie à Paris VI, soutenue en décembre 2005) 
à une amélioration de cet algorithme permettant d'éviter la génération
de (parfois très nombreux) candidats inutiles lors de la recherche de
répétitions et aux représentations de ces motifs
en vue de leur recherche dans les séquences de structures de protéines
\cite{Pisanti:2006li}. Nous nous intéressons actuellement à la
sélection et l'ordonnancement de ces motifs (de différentes longueurs)
en vue d'obtenir des signatures structurales pour différentes familles
de protéines.

\afterpage{\clearpage
\floatstyle{plain} %<-- sans encadrement des figures
\restylefloat{figure}
\begin{figure}[H]
\centering\noindent
\includegraphics[width=0.8\textwidth]{inputs/A3/Figures/genes}
\caption{\small Motifs relationnels structuraux et analyse intégrée d'une duplication 3D}
%  \label{fig:budget_ratio_cercle}
\end{figure}
\floatstyle{boxed} %<-- avec encadrement des figures
\restylefloat{figure}
}

D'autre part, dans le cadre de la thèse de M. Elati, nous abordons
l'apprentissage de structures de graphes sous-jacentes à des données
propositionnelles. Ce travail est appliqué à l'extraction de réseaux de
régulation à partir de données d'expression de gènes, en collaboration
avec l'Institut Curie et l'Institut de Génétique Moléculaire de
l'Université Paris 11. 
%% Le problème est d'identifier, à partir de
%% données d'expression représentant pour un ensemble de situations
%% l'expression simultanée d'une dizaine de milliers de gènes et
%% régulateurs l'ensemble des régulateurs affectant la transcription (et
%% indirectement l'expression) de
%% chaque gène. 
La détection de relations de régulation repose la plupart du temps sur
l'hypothèse qu'un régulateur et son gène cible sont
corrélés. Construire un graphe acyclique où chaque lien est une
relation orientée de régulation et maximisant une mesure de corrélation
donnée est un problème NP-complet, et a donné lieu aux
développements de multiples approches heuristiques, dont
bayésiennes. Cependant, ces méthodes sont peu adaptées à la détection
de régulation coopératives, où plusieurs régulateurs se coordonnent
pour affecter un gène cible et pour lesquelles l'expression d'un gène
et d'un de ses régulateurs n'est pas nécessairement fortement
corrélée.  Nous avons développé une approche heuristique originale qui
recherche pour chaque gène un réseau ``local'' représentant l'ensemble
de ses régulateurs (activateurs et/ou inhibiteurs).  La recherche du
meilleur ensemble de régulateurs pour chaque gène cible est restreinte
à l'ensemble des régulateurs fréquemment co-exprimés.  Cette approche
limite drastiquement le nombre d'ensemble de régulateurs candidats à
explorer, tout en préservant les régulations coopératives. Elle a été
appliquée avec succès à des données d'expression de levure et de
patients atteints de tumeurs de vessie. Nous collaborons
actuellement avec des statisticiens de l'Université d'Evry pour
construire, à partir des réseaux locaux ainsi obtenus, un réseau
global reliant les gènes et/ou les régulateurs entre eux, et qui
s'appuie sur une information plus complexe que sur la détection de
corrélations d'expression directes.

\item[Programmation Logique Inductive]~\\

 L'équipe aborde dans ce thème les développements algorithmiques pour
 l'apprentissage dans des fragments de la logique du premier ordre,
 comme le Datalog non-recursif avec negation, selon deux axes
 privilégiés : l'utilisation de macro-opérateurs pour l'abstraction
 de l'espace de recherche, qui bénéficie de l'expertise acquise dans
 le cadre du thème <<Treillis de Galois emboîtés - constructions de
 taxonomies>>, et la résolution algébrique du problème
 d'apprentissage dans des treillis distributifs. Ce deuxième axe
 s'intéresse à la formalisation et au développement de solveurs
 algébriques de problèmes d'apprentissage. Cela nous a notamment
 permis d'identifier des problèmes clés d'apprentissage de type
 MAX-CSP et CSP pondérés (\textit{Weighted CSP}) qui sont des
 problèmes déjà étudiés dans l'équipe \cite{Bennaceur:2003mw}.
 Notamment sur ce dernier point, nous avons formalisé et développé
 une technique de résolution efficace dite <<descendante dirigée par
 les données>> dans des restrictions de la logique du premier ordre.

 Dans un cadre transversal, nous étudions l'efficacité de ces
 techniques dans le cadre empirique de la \textit{transition de
   phase}. Ce cadre est une étude topologique de la complexité en
 moyenne de problèmes combinatoires NP-complets en fonction de
 paramètres d'ordre. Ce travail au sein de l'équipe fait suite aux
 nombreuses études et publications des différentes communautés
 d'Optimisation Combinatoire sur les problèmes de type SAT, CSP, TSP
 etc, avec la même finalité de développer un cadre d'analyse et de
 comparaison des approches algorithmiques proposées. Notamment,
 l'étude des transitions de phase permet le développement de
 générateurs de problèmes difficiles pour tout algorithme afin de
 faciliter l'analyse des performances des algorithmes en moyenne.
 Nous avons montré notamment que l'apparition d'une transition de
 phase (du test de couverture) en PLI était un cas pathologique pour
 la recherche heuristique des algorithmes d'apprentissage. Cependant,
 nos premiers résultats montrent que ce cas pathologique n'affecte
 systématiquement que les stratégies dites « générer-tester » et non
 pas la stratégie « descendante dirigée par les données ».
\end{description}

\subsection{Résultats significatifs}

\begin{itemize}
\item formalisation et développement d'une technique de résolution algébrique dite <<descendante dirigée par
 les données>> dans des restrictions de la logique du premier ordre \cite{Alphonse2006b};
\item étude de l'impact de la transition de phase du test de couverture sur la recherche heuristique en Programmation Logique Inductive \cite{Alphonse2007c}
\end{itemize}

\subsection{Domaines d'applications}
Les domaines visés par les méthodes d'apprentissage symbolique sont
multiples, et en pleine extension, car de nombreux utilisateurs
réclament des méthodes d'apprentissage dont les résultats sont
exprimés sous forme de règles utilisant un vocabulaire explicite pour
ces utilisateurs. Par exemple, nous avons
travaillé sur des données semi-structurées décrivant des produits
informatiques (données C/NET). Les deux autres axes applicatifs
privilégiés de l'équipe sont: 
\begin{itemize}
\item la Bioinformatique. Plus précisément l'équipe collabore avec le
laboratoire MIG de l'\textsc{inra} Jouy-en-Josas, avec l'Atelier de
Bioinformatique, de l'Université Paris 6, ainsi qu'avec l'Institut
Curie (Paris) 
\item le traitement de
connaissances textuelles, avec le
laboratoire MIG de l'\textsc{inra} Jouy-en-Josas également
\end{itemize} 
Ces domaines d'applications nous permettent d'établir des
collaborations au sein de l'Université Paris 13 avec l'équipe
\acs{RCLN} et le Lim\&Bio.



\subsection{Perspectives de recherche}

Les perspectives de l'apprentissage à partir d'exemples incomplets et
 de l'analyse de l'information mise en jeu au cours du processus
 d'apprentissage, sont à la fois appliquées et théoriques. Sur le plan
 des applications, la Bioinformatique est un terrain prometteur. En
 effet les changements de représentations en fonction de critères
 informationnels semblent intéressants pour guider la recherche de
 motifs répétés au sein de séquences biologiques : ainsi une séquence de
 nucléotides (ADN ou ARN) peut être représentée de façon plus
 abstraite comme une séquence d'acides aminés. Sur le plan théorique,
 nous nous intéressons à reproduire cette étude en présence
 d'informations révisables (non monotones).

Une part importante de notre activité est consacrée au développement
d'un système hautement configurable d'apprentissage dans des langages
de représentation au moins aussi riches que le Datalog
non-récursif. Nous allons valoriser à court terme ce développement en
offrant à la fois aux spécialistes et aux praticiens de
l'apprentissage une plate-forme pour l'expérimentation et pour la
résolution de problèmes d'apprentissage. Cette mise à disposition va
permettre de centraliser et de diffuser les différentes spécialisations
de la plate-forme effectuées pour les applications ; elle servira
également de plate-forme expérimentale pour le développement et la
validation d'approches algorithmiques de l'apprentissage développées
dans l'équipe \acs{A3} et notamment en Programmation
Logique Inductive. Les problèmes ouverts de recherche dans le cadre
relationnel que nous comptons aborder avec cette plate-forme
sont la sélection/réduction du langage de concepts, en particulier à
l'aide de macro-opérateurs, et le traitement de données incomplètes et
bruitées.

Enfin, à plus long terme, nous souhaiterions développer un axe de
recherche transversal (relationnel et numérique) dans l'équipe sur le
thème de de l'{\it apprentissage relationnel probabiliste}, dont le
but est d'effectuer du raisonnement de l'inférence probabiliste
sur des représentations logiques, qui nous permettra de modéliser et
d'apprendre des connaissances en utilisant la souplesse des
représentations probabilistes et l'intelligibilité des représentations
logiques.