26
MASTER WEB INTELLIGENCE PLATE-FORME ET COMPÉTITION POUR L’APPRENTISSAGE ACTIF David Combe 16 juin 2009

Zulu DFA active learning

Embed Size (px)

Citation preview

Page 1: Zulu DFA active learning

MASTER WEB INTELLIGENCE

PLATE-FORME ET

COMPÉTITION POUR

L’APPRENTISSAGE ACTIF

David Combe 16 juin 2009

Page 2: Zulu DFA active learning

L’apprentissage actif

Il consiste à faire apprendre une machine sur la base d’une interaction avec une entité en connexion avec le concept à découvrir.

Il permet de se passer d’une phase de consolidation des données et, s’il est bien fait, de minimiser les données utilisées.

Exemples de la vie quotidienne Mastermind

Dichotomie

Page 3: Zulu DFA active learning

Applications

Filtrage d’e-mail

Wrapper induction (contexte de données dans

des pages web par exemple)

Etude de circuits intégrés

Robotique

Recherche d’information basée sur des

évaluations…

Page 4: Zulu DFA active learning

L’Oracle

C’est souvent un être humain, parfois même

un expert.

Il n’aime pas forcément être ennuyé.

Il est soucieux du nombre et la nature des

requêtes utilisées.

Plus encore que la complexité temporelle,

c’est le nombre de requêtes utilisées qui

distingue un bon algorithme.

Page 5: Zulu DFA active learning

Requêtes

La grammaire dont il est question ici est celle

des langages rationnels (AFD)

Requête d’appartenance

le mot « ab » appartient-il au langage étudié ?

Requête d’équivalence

l’automate que je propose pour le langage est-il

correct.

Page 6: Zulu DFA active learning

Zulu

Zulu propose de comparer l’efficacité des

algorithmes d’apprentissage actif d’automates

et d’en découvrir de nouveaux.

Proposer la génération de tâches

À partir du générateur d’automates de Gowachin.

Gowachin est aussi en charge de l’échantillon de

test de 1800 mots.

Page 7: Zulu DFA active learning

Tâche

Un automate tiré aléatoirement

On fixe une borne maximum du nombre d’états

On définit la taille de l’alphabet.

Le but

Après un nombre prédéterminé de requêtes d’appartenance autorisées, il faut arriver à classer 1800 mots dans les classes positif/négatif.

Page 8: Zulu DFA active learning

Tâche

Page 9: Zulu DFA active learning

Tâche

Page 10: Zulu DFA active learning

Tableau de bord

Page 11: Zulu DFA active learning

Evaluation

Page 12: Zulu DFA active learning

Et aussi

Création de challenge pour comparer son

score à celui d’un autre joueur

Panneau d’administration

Fil RSS des scores publiés

Page 13: Zulu DFA active learning

Cible et challenge

Page 14: Zulu DFA active learning

Déroulement

Phase d’entraînement

Communication auprès des personnes

concernées

Phase de compétition

Formation d’un comité scientifique

Evaluation des performances à définir

Page 15: Zulu DFA active learning

Algorithme de référence

Pour montrer que la problématique est réelle

Pour fournir un algorithme réalisant la tâche,

susceptible d’être amélioré et faciliter l’entrée

des participants dans le projet

L’algorithme proposé est L*.

Page 16: Zulu DFA active learning

Résultats théoriques

Il n’est pas possible d’apprendre de manière

exacte un automate avec uniquement des

requêtes d’appartenance.

Il n’est pas possible d’apprendre de manière

exacte un automate avec uniquement des

requêtes d’équivalence.

L’apprentissage d’un automate est possible

avec ces 2 types de requêtes

polynomialement sur le nombre de requêtes.

Page 17: Zulu DFA active learning

L*

Créé par Dana Angluin en 1989

L* renvoie toujours l’automate minimal.

L* construit une table d’observation et fait en

sorte qu’elle respecte 2 propriétés :

la fermeture

la consistance

Lorsque ces 2 propriétés sont vérifiées, L*

construit l’automate associé et le soumet à

l’Oracle pour validation.

Page 18: Zulu DFA active learning

Simulation

Exécution de L* sur un langage simple

L = {les mots qui finissent par « ba »}

Les requêtes d’équivalence sont en pratique

difficiles à formuler. D. Angluin propose de les

remplacer par un ensemble de requêtes

d’appartenance sur des mots choisis au

hasard.

L’apprentissage devient non déterministe et

statistique.

Page 19: Zulu DFA active learning

Comportement de L*

L* a un effet de palier important :

Un automate n’est constructible que lorsque la

table d’observation est fermée et consistante, ce

qui arrive entre 6 et 11 fois sur des problèmes

moyens à 2 lettres et encore moins souvent avec

3 lettres et plus.

Lorsque l’on a atteint la limite de requêtes on

retombe au palier précédent.

Pour avoir un bon score il faudra gommer ces

effets ou prévoir la fin des requêtes autorisées

Page 20: Zulu DFA active learning

Exemple

40

50

60

70

80

90

100

0 500 1000 1500 2000 2500 3000 3500 4000

Sc

ore

Nombre de requêtes d'appartenance

Page 21: Zulu DFA active learning

Nombre de requêtes / score lors

des simulations de requêtes

d’équivalence

Sur un même problème

de 107 états

Page 22: Zulu DFA active learning

Evaluation

Un problème multi-dimensions difficile à

évaluer

Dimensions à maximiser :

Score

Nombre d’états de l’automate

Taille de l’alphabet

Dimension à minimiser :

Nombre de requêtes

Page 23: Zulu DFA active learning

Différentes façons de proposer une

tâche évaluable

Fixer un score minimal à atteindre, par exemple 97% de l’automate appris, et un nombre de requêtes autorisées. Le gagnant est le joueur qui a appris de cette manière le plus gros automate. Similaire à Abbadingo

La baseline sert à établir un nombre de référence des requêtes autorisées. Le gagnant est la personne qui obtient le meilleur rapport « Score du joueur / Score de la baseline » pour le nombre de requêtes autorisées Sous réserve que la baseline soit suffisamment bonne

et que le score de la baseline ne soit pas trop aléatoire

Restreindre la classe des automates

Page 24: Zulu DFA active learning

Compétition : évaluation

Divers problèmes générés à

l’avance, identiques pour tous les joueurs

Le gagnant devra envoyer son programme

pour validation du classement.

Compétition en 2010.

Page 25: Zulu DFA active learning

Perspectives

Autres requêtes (telles que les requêtes de

correction)

Autres grammaires (langages hors-contexte)

Page 26: Zulu DFA active learning

Fin