View
258
Download
2
Category
Preview:
Citation preview
MASTER WEB INTELLIGENCE
PLATE-FORME ET
COMPÉTITION POUR
L’APPRENTISSAGE ACTIF
David Combe 16 juin 2009
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
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…
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.
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.
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.
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.
Tâche
Tâche
Tableau de bord
Evaluation
Et aussi
Création de challenge pour comparer son
score à celui d’un autre joueur
Panneau d’administration
Fil RSS des scores publiés
Cible et challenge
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
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*.
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.
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.
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.
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
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
Nombre de requêtes / score lors
des simulations de requêtes
d’équivalence
Sur un même problème
de 107 états
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
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
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.
Perspectives
Autres requêtes (telles que les requêtes de
correction)
Autres grammaires (langages hors-contexte)
Fin
Recommended