Conférence d'APprentissage 2003 (CAP'2003)

Les 22 articles acceptés à CAp'2003

Article 3 - Construction de Modèles de Langages par Inférence d'Automates Typés à partir de Données Etiquetées Automatiquement

par Christopher Kermorvant, Colin de la Higuera, Pierre Dupont

Mots-clefs : Modèles de langage -- Inférence Grammaticale -- Connaissances du domaine
Nous proposons deux façons d'utiliser des connaissances a priori en inférence grammaticale d'automates probabilistes, dans le but de construire des modèles de langages. La première consiste à considérer des classes de mots et à inférer sur les classes de mots plutôt que sur les mots eux-mêmes ; la seconde à inférer des automates typés. Nous comparons ces approches en utilisant deux sources d'information a priori, ou deux façons distinctes de classifier les données avant l'inférence grammaticale : un algorithme de classification non supervisée et un part-of-speech tagger ont été utilisés pour étiqueter de façon automatique les données soit en fonction d'information statistique, soit en fonction d'information syntaxique. Ces données étiquetées sont ensuite utilisées pour l'inférence. Les meilleurs résultats sont obtenus avec les données étiquetées statistiquement dans un automate typé. Ces résultats sont comparables à ceux obtenus par les meilleurs modèles statistiques n-grammes sur les données ATIS (Air Travel Information System).

Article 4 - Etude sur l'Amélioration du Boosting : Réduction de l'Erreur et Accélération de la Convergence

par Marc Sebban et Henri-Maxime Suchier

Mots-clefs : boosting,agrégation de classifieurs
Le boosting est la méthode d'agrégation de classifieurs, non seulement la plus efficace en pratique, mais également celle reposant sur les propriétés théoriques les plus solides. La mise à jour adaptative de la distribution des exemples, visant à augmenter le poids de ceux mal appris par le classifieur précédent, permet d'améliorer les performances de n'importe quel algorithme d'apprentissage. Néanmoins, ses capacités à être immunisé contre le sur-apprentissage ont été remises en cause dès qu'il s'agit d'appliquer le boosting à des données fortement bruitées. Cette situation est fréquente avec les bases modernes, issues des nouvelles technologies d'acquisition de données, comme le Web. La vitesse de convergence du boosting se trouve également pénalisée sur ce type de bases, où le degré de chevauchement des densités de probabilités des classes à apprendre peut être grand (erreur bayésienne importante). Dans cet article, nous proposons une légère modification de la mise à jour des exemples telle qu'elle est effectuée dans l'algorithme {\sc Adaboost}. Nous montrons qu'en exploitant une mesure d'entropie locale adaptative, issue d'un graphe de voisinage construit sur les exemples, il est possible de déterminer non seulement les \textit{outliers} mais aussi les exemples situés en zone d'erreur bayésienne. Nous montrons qu'il est possible d'améliorer, en corrigeant le poids des exemples, les performances du boosting. Une large étude expérimentale montre l'intérêt de notre nouvel algorithme, appelé \it{i}{\sc Adaboost}.

Article 6 - Génération de la base de Guigues-Duquenne-Luxemburger pour les règles d'association par une approche utilisant des mesures de pseudo-similarités multivoies

par Jean Diatta

Mots-clefs : treillis de Galois, opérateur de fermeture, pseudo-similarité multivoies, règle d'association, motif fréquent
Nous présentons une approche directe par niveaux pour générer la base de Guigues-Duquenne-Luxemburger pour les règles d'association valides dans un contexte. L'approche proposée est une combinaison d'une technique de fouille de données (algorithme de type Apriori) avec des outils de l'analyse de données classique (mesures de pseudo-similarités multivoies). En effet, elle est fondée sur une caractérisation des motifs fermés via des mesures de pseudo-similarités multivoies en adéquation avec les données dans un sens assez naturel appelé delta-compatibilité. De telles mesures de pseudo-similarités sont dites delta-compatibles. Les pseudo-similarités strictement delta-compatibles appartiennent une famille de pseudo-similarités qui joue un rôle important en classification. De plus, des propriétés des mesures de pseudo-similarités multivoies permettent de générer la base de Guigues-Duquenne-Luxemburger, dans une approche ascendante de type Apriori, sans construction préalable de tous les motifs fréquents, comme c'est le cas des méthodes classiques, ou de tous les motifs fermés fréquents, comme c'est le cas des méthodes fondées sur l'analyse formelle de concepts. Une des clés de notre approche est de considérer des générateurs minimaux de motifs fermés fréquents $Q$, c'est--dire, des motifs $P\subseteq Q$ minimaux parmi ceux dont $Q$ est la fermeture. Il en résulte que le nombre de passages requis à travers la base de données est majoré par la taille maximum d'un générateur minimal d'un motif fermé fréquent plus $1$, un nombre qui peut être très petit par rapport la taille maximum d'un motif fermé fréquent.

Article 7 - Apprentissage de profil pour un agent de recherche d'information.

par J.C. Bottraud, G. Bisson, M.F. Bruandet

Mots-clefs : Recherche d'information, Agent Intelligent, Document, Classification automatique, WWW, Adaptation, Contexte.
Les outils disponibles de rechercher d'information sur le Web ont une approche généraliste, ne prenant pas en compte les caractéristiques de l'utilisateur, ce qui limite la qualité des résultats qu'ils sont susceptibles de fournir. L'agent présenté ici utilise les références documentaires rassemblées par l'utilisateur pour construire un profil le représentant, et qui est exploité pour interpréter et filtrer les résultats proposés par les moteurs de recherche. Il utilise également des informations obtenues en observant les activités en cours de l'utilisateur pour restreindre l'utilisation du profil aux parties les plus pertinentes.

Article 9 - Optimisation d'Extraction de Motifs : une nouvelle Méthode fondée sur la Transposition de Données

par François Rioult et Bruno Crémilleux

Mots-clefs : Fouille de données, extraction de motifs, connexion de Galois, transposition de données, données biologiques
Chercher dans une base de données les motifs d'attributs (les colonnes) ou les groupes d'objets (les lignes) qui vérifient certaines propriétés est une tâche classique de la fouille de données, aujourd'hui bien maîtrisée. Néanmoins, certains contextes difficiles comme les données issues de la bio-informatique restent impraticables, en raison d'un nombre d'attributs disproportionné devant le nombre d'objets.

Dans ces conditions, il est naturellement tentant de transposer la matrice des données pour y pratiquer plus efficacement l'extraction des motifs. Cet article expose cette nouvelle méthode et montre son intérêt mais aussi les difficultés à résoudre pour que cette approche soit fructueuse. En tirant profit de la connexion de Galois, l'extraction réalisée dans la base transposée permet d'inférer des résultats sur les données initiales. Nous montrons les apports de cette pratique sur des données contenant un grand nombre d'attributs, comme les données de génome, ainsi que son application possible à l'extraction sous contrainte monotone et l'obtention de la totalité de l'ensemble des motifs fermés.

Article 10 - Yet Another Optimization Criterion for Classification : The Area Under the ROC Curve

par Michèle Sebag, Jérôme Azé, Noël Lucas

Mots-clefs : ROC, optimisation, stabilite, skewed distribution, cost-sensitive learning
Reformulating supervised learning as an optimization problem is a tantalizing goal. This paper investigates a new optimization criterion for machine learning, the maximization of the area under the Receiver-Operating Characteristics (ROC) curve.

As this optimization problem is not tractable by standard combinatorial or numerical optimization methods, we employ evolutionary computation algorithms suited to parametric optimization.

The approach is experimentally validated on various problems from the Irvine repository, and compared to SVM methods. Its application on a real-world application, the identification of risk factors for atherosclerosis, is last described and discussed.

Article 11 - Génération de prosodie par apprentissage de structures arborescentes

par Lauren Blin

Mots-clefs : apprentissage par plus proches voisins, structures arborescentes, synthèse automatique de la parole, prosodie
Nous présentons dans cet article une approche de prédiction de la prosodie pour la synthèse automatique de la parole. Celle-ci est basée sur la représentation arborescentes des énoncés manipulés, et sur la définition de mesures de similarité entre ces structures. Nous introduisons ici les différentes représentations arborescentes et distances utilisées, le processus de prédiction de la prosodie par plus proche voisin considéré, et présentons les résultats obtenus dans les différentes configurations de notre système.

Article 12 - Traitement du bruit en inférence exacte

par Marc Sebban, Jean-Christophe Janodet

Mots-clefs : Inférence grammaticale, traitement des données bruitées, RPNI, méthode wrapper
La tolérance au bruit est une qualité que tout algorithme d'apprentissage automatique doit avoir pour traiter des problèmes réels. De nombreuses techniques ont été développées pour traiter des données numériques bruitées, mais peu de méthodes semblent exister lorsque les données d'apprentissage sont des séquences non bornées de symboles, comme c'est le cas en inférence grammaticale. Dans ce papier, nous proposons une approche statistique de traitement du bruit pendant l'inférence d'un automate avec RPNI. Notre technique est basée sur un test de comparaison de proportions qui relâche les contraintes d'acceptation d'une fusion de RPNI sans mettre statistiquement en danger ses performances en généralisation. Outre l'approche elle-même, nous étudions les propriétés théoriques du comportement de RPNI*, notre nouvelle version de RPNI, puis nous faisons une étude expérimentale comparative de ces deux algorithmes.

Article 14 - WMplic: combiner des classeurs issus de représentations différentes pour une tâche d'identification d'objets par un robot situé

par Nicolas Bredeche et Jean-Daniel Zucker

Mots-clefs : Apprentissage -- Abstraction -- Perception -- Robotique située
Dans cet article, nous nous intéressons à l'utilisation de méca-nismes d'abstraction agissant sur les percepts visuels d'un robot mobile autonome Pioneer2dx en vue de permettre l'identification des objets que celui-ci peut rencontrer dans son environnement. L'ancrage des connaissances nécessaires pour cette tâche d'identification est réalisé grâce à des changements de représentation successifs dans le but de découvrir des propriétés visuelles invariantes pertinentes relatives aux objets à identifier.

Une fois la phase initiale d'apprentissage terminée se pose toutefois la question de la maintenance à long terme de cette capacité d'identification dans un environnement dynamique. Afin de résoudre ce problème, nous proposons une approche qui permet au robot de réacquérir partiellement ou complétement des ancrages déjà appris. En l'occurrence, le système WMplic que nous avons développé permet d'assurer un tel maintient de la capacité d'identification d'objets dans le temps grâce à des classeurs constamment renouvelés. Dans notre approche, chaque classeur a la particularité d'avoir été appris en utilisant une représentation particulière des données brutes issues des senseurs du robot.

Article 15 - Intégration de connaissances langagières et structurelles pour l'apprentissage d'automates

par F. Coste, D. Fredouille

Mots-clefs : Inférence de langages réguliers -- automates -- introduction de connaissances
Le problème de l'introduction de connaissances liées au domaine d'application dans un processus d'inférence d'automate a été soulevé récemment par \cite{KerHig02}. Cette connaissance permet de favoriser la convergence des algorithmes d'inférence. Nous présentons un algorithme permettant d'intégrer des connaissances sur le langage à inférer comme~: la connaissance d'un langage incluant le langage cible, d'un domaine pour les séquences à inférer ou l'ajout d'ensembles de contre-exemples possiblement infinis. On propose également un algorithme pour l'intégration de connaissances sur la structure de l'automate à inférer. Celui-ci permet de lever les restrictions importantes qui sont nécessaires à l'utilisation de l'algorithme de \cite{KerHig02} .

Article 17 - Application du renforcement à la gestion du risque

par René Aïd, Vincent Grellier, Arnaud Renaud, Olivier Teytaud

Mots-clefs : Renforcement -- Risque -- Gestion de stock -- Optimisation dynamique stochastique
La programmation dynamique stochastique est un principe de décomposition classique pour l'optimisation dynamique. Elle permet l'optimisation de tout critère séparable. En particulier, l'espérance est un critère séparable. Par contre, l'ajout d'une prise en compte du risque par une mesure de type Value-At-Risk rend le problème non-séparable, donc le traitement par programmation dynamique stochastique standard est impossible. Cet article présente une application de techniques de renforcement compatibles avec un critère non-séparable. La mise en \oe uvre pratique est faite dans le cadre de la production électrique par le parc de production thermo-hydraulique d'EdF. Les courbes de Value-At-Risk obtenues montrent le succès de l'approche : augmenter le paramètre alpha du critère (1-alpha) E +alpha VaR conduit à des risques plus faibles.

Article 18 - Identification à la limite d'automates probabilistes avec probabilité de 1.

par Francois Denis et Yann Esposito

Mots-clefs : Automate probabilistes, Modèles de Markov cachés, Apprentissage, Langages résiduels stochastiques.
Les automates probabilistes (PFA) sont des objets permettant de modéliser des distributions de probabilités définie sur des ensembles de mots. Ils ont la même expressivité que les Modèles de Markov Cachés (HMM) utilisés dans de très nombreuses applications.

Pour une sous-classe des PFAs, les automates probabilistes déterministes (PDFA), des algorithmes d'identification à la limite ont été élaborés. Malheureusement les PDFAs sont beaucoup moins expressifs que les PFAs.

Aussi nous étudions une classe d'expressivité intermédiaire : les automates probabilistes à états résiduels (PRFA). Nous montrons que les PRFAs à paramètres rationnels sont indentifiables à la limite avec une probabilité de $1$.

Article 19 - Identification à la limite de langages réguliers d'arbres à résiduels premiers disjoints

par J. Carme A. Lemay A. Terlutte

Mots-clefs : inférence grammaticale, langages d'arbres, apprentissage par exemples positifs
Nous définissons deux classes de langages d'arbres. Ces deux classes contiennent strictement la classe des langages d'arbres réversibles.Nous montrons que les deux classes ainsi définies sont identifiables à la limite par exemples positifs seuls.

Article 20 - Mélange d'ACPs probabilistes et scores de Fisher pour la représentation de documents

par Georges Siolas et Florence d'Alché-Buc

Mots-clefs : modèles générateurs, acp probabiliste, représentation de textes, catégorisation
La mise en {\oe}uvre d'algorithmes d'apprentissage statistique sur des documentstextuels requiert l'élaboration d'un codage numérique. La pertinence de cette représentation dépend de sa capacité à refléter la sémantique des documents. Nous proposons ici une modélisation probabiliste des mots fondée sur l'idée que la sémantique des mots est de nature continue. Pour construire un modèle générateur de mots, nous apprenons un mélange d'Analyses en Composantes Principales probabilistes qui fournit les ``clusters'' de mots représentant des concepts sémantiques et une réduction de dimension pour chacun d'entre eux. Ce modèle peut ensuite servir de brique de base dans l'élaboration d'un modèle de document, qu'il soit plat ou structuré. A partir de cette modélisation, nous extrayons des scores de Fisher pour représenter les documents. La dimension de représentation est ainsi considérablement réduite. Nous montrons que malgré cette réduction, l'utilisation de noyaux appropriés permet d'obtenir un gain de performances par rapport au codages classiques pour la base de textes des 20 ``newsgroups''. \\

Article 21 - Modèle dynamique à noyaux pour la prévision de séries temporelles non linéaires

par Liva Ralaivola, Florence d'Alché-Buc

Mots-clefs : prévision de séries non linéaires, méthodes à noyaux, systèmes dynamiques linéaires, filtre de Kalman
Nous considérons le problème de la prévision de séries temporelles non linéaires et proposons une nouvelle méthode, appelée Kernel Dynamical Modelling. Cette méthode, fondée sur l'utilisation de fonctions noyaux, étend les modèles dynamiques linéaires classiques, en considérant des vecteurs d'un espace des caractéristiques (feature space) associé à un noyau. La mise en oeuvre de notre approche fait intervenir par deux fois l'astuce des noyaux (kernel trick): une première fois pour l'apprentissage des paramètres du modèle et une seconde fois pour le calcul des antécédents (pré-images) des points de la série, qui est prédite dans l'espace des caractéristiques. La détermination des antécédents se fait grâce à l'utilisation de machines à vecteurs de support pour la régression et permet de résoudre de manière originale le problème des pré-images.

Les capacités de prévision de notre modèle sont évaluées sur deux séries temporelles chaotiques. Les performances que nous obtenons sont de qualité équivalente ou supérieure à celles obtenues lorsque la prévision est effectuée par une machine à vecteurs de support classique.

Article 22 - Evaluation des cartes auto-organisatrices et de leur variante à noyaux

par Marie-Jeanne Lesot, Florence d'Alché-Buc, Georges Siolas

Mots-clefs : Cartes auto-organisatrices -- Clustering topographique -- Evaluation -- Méthodes à noyaux
Nous considérons la tâche de clustering topographique traitée par les cartes auto-organisatrices et le problème de leur évaluation : nous replaçons les variantes des algorithmes de clustering topographique, depuis les cartes de Kohonen jusqu'à leur extension basée sur les fonctions noyaux (STMK), dans un cadre commun du clustering contraint. Exploitant ce point de vue, nous discutons les mesures de qualité existantes et nous proposons un nouveau critère basé sur une F-mesure, qui combine une mesure de qualité de clustering avec un critère d'organisation et nous l'étendons aux cartes à noyaux.

Article 23 - Vers une méthodologie de fouille de textes s'appuyant sur l'extraction de motifs fréquents et de règles d'association

par Hacène Cherfi, Amedeo Napoli et Yannick Toussaint

Mots-clefs : Fouille de textes, règles d'association, mesures de qualité, interprétation, biologie moléculaire.
Nous proposons la description d'une méthodologie d'interprétation des règles d'association extraites à partir de textes. Le corpus qui a servi à notre expérience est une collection de textes sous forme de résumés d'articles scientifiques dans le domaine de la biologie moléculaire. Notre recherche porte sur: i) l'extraction des règles d'association à partir de la construction des motifs fermés fréquents générés par l'algorithme "Close"; ii) l'association de mesures {\em qualitatives} à chaque règle, ce qui permet de les ordonner; iii) l'interprétation des règles par un analyste (expert du domaine); iv) la mise en correspondance des points ii) et iii). Nous montrons comment aider l'analyste, grâce à des mesures de qualité, dans l'interprétation des règles. Une discussion sur nos résultats met en valeur des points qui nous paraissent fondamentaux dans l'interprétation des règles d'association.

Article 24 - Approche probabiliste pour la réduction de sous-arbres bruités

par Amaury Habrard, Marc Bernard, Marc Sebban

Mots-clefs : réduction de données, sélection de prototypes, données arborescentes, données bruitées
Cet article s'intéresse à l'élagage de sous-arbres bruités ou non pertinents au sein d'un ensemble d'arbres (ou forêt). L'originalité de cette approche, par rapport à des techniques classiques de sélection de prototypes, est qu'elle ne supprime pas un arbre en entier mais cherche plutôt à supprimer certains de ses sous-arbres. Notre méthode se base sur le calcul d'un intervalle de confiance sur un ensemble de sous-arbres en fonction d'une distribution de probabilité. Nous proposons deux approches pour supprimer les sous-arbres et montrons expérimentalement leur intérêt dans le contexte de l'apprentissage à partir de données bruitées.

Article 25 - Apprentissage des grammaires de Lambek rigides et d'arité bornée pour le traitement automatique des langues

par Denis Béchet et Annie Foret

Mots-clefs : Apprentissage, Inférence grammaticale, Traitement automatique des langues, Linguistique informatique, Grammaires catégorielles de Lambek, Modèle de Gold
Nous nous intéressons au problème de l'apprentissage des grammaires catégorielles utilisées pour la modélisation syntaxique des langues.

Récemment, des algorithmes ont été proposés dans le modèle d'apprentissage de Gold, pour certaines classes de grammaires catégorielles.En revanche, les grammaires de Lambek rigides ou k-valuées ne sont pas apprenables à partir des chaînes.

Nous nous intéressons ici à une autre classification de ces grammaires selon l'arité des dérivations.Nous montrons ainsi qu'une borne sur l'arité des dérivations permet d'identifier à la limite les grammaires de Lambek rigides ou k-valuées dans le cas non associatif.

Ces résultats répondent à certaines questions de linguistique mathématique et d'inférence grammaticale et indiquent une direction dans laquelle poursuivre l'étude de l'acquisition automatique de ressources lexicales.

Article 26 - Une classe de grammaires catégorielles apprenable à partir d'exemples typés

par Daniela Dudau, Isabelle Tellier, Marc Tommasi

Mots-clefs : inférence grammaticale, grammaires catégorielles, langage naturel
La classe des grammaires catégorielles dites AB ou classiques a donné lieu ces dernières années à des résultats d'apprenabilité au sens de Gold (principalement dus à Kanazawa) intéressants. Cette classe mérite d'être étudiée parce que ses membres permettent de générer l'ensemble des langages context-free ou algébriques et parce que l'interface qu'elle permet avec une interprétation sémantique la rend apte à modéliser certaines particularités des langues naturelles. Mais les résultats d'apprenabilité connus ne concernent que des sous-classes triviales (classe des grammaires rigides) ou donnent lieu à des algorithmes rédhibitoires (classes des grammaires $k$-valuées avec $k\geq 1$). Nous définissons dans cet article une nouvelle sous-classe de grammaires catégorielles classiques à la fois intéressante d'un point de vue de la théorie des langages (puisque ses représentants permettent de générer l'ensembles des langages de structures de toutes les grammaires categorielles classiques) et d'un point de vue apprentissage (puisqu'elle est apprenable au sens de Gold à condition de fournir des données adaptées).

Article 28 - Apprentissage des langages réguliers d'arbres à l'aide d'un expert

par Jérôme Besombes et Jean-Yves Marion

Mots-clefs : langages réguliers d'arbres, expert, oracle
Nous nous intéressons à l'apprentissage des langages réguliers d'arbres à partir d'exemples positifs et en interaction avec un expert. L'expert est un oracle qui connaît le langage appris et qui répond à des questions d'appartenance. Nous donnons un algorithme efficace d'apprentissage dans ce paradigme, nous montrons sa correction et l'illustrons sur un exemple détaillé.

Article 29 - Prédiction de ponts disulfures par langages de contrôle

par Ingrid Jacquemin et Jacques Nicolas

Mots-clefs : inférence grammaticale, langages de contrôle, bioinformatique, prédiction de structures de protéines
L'inférence grammaticale s'intéresse à l'apprentissage à partir de séquences dans le cadre de la théorie des langages. Il existe de nombreux algorithmes d'apprentissage pour les langages réguliers. Par contre peu de résultats ont été obtenus pour les classes de langages plus larges car la plupart des méthodes d'apprentissage pour les langages réguliers ne sont pas directement applicables à celles-ci. Nous proposons ici d'explorer une méthode d'inférence grammaticale qui permet d'apprendre des langages de classe supérieure au régulier par inférence régulière sur un langage de contrôle. Cette approche a été proposée sur un plan théorique par Takada \cite{Takada94}. Cet article est une première tentative de délimitation des problèmes rencontrés dans l'inférence pratique de langages de contrôle. Nous présentons quelques expérimentations effectuées afin de prédire les ponts cystéines dans les protéines en utilisant des algorithmes existants pour l'inférence de langages réguliers et soulignons les difficultés auxquelles sont confrontés ceux-ci dans un tel cadre.