Dm 1

1

Fouille de données (Data Mining) & Acquisition de connaissances {Vincent.Corruble,JeanDaniel.Zucker} @lip6.fr

http://www-poleia.lip6. fr/~zucker

© J-D. ZUCKER LIP6

Plan Plandu ducours coursDESS-GLA DESS-GLA2001/2002 2001/2002etetModalité Modalité

2

Contenu de ce cours: • Une introduction à diverses méthodes et techniques d’apprentissage automatique et des systèmes adaptatifs • La fouille de données: » » » »

Rappel base et entrepôts de données (ODBC, OLAP). L’analyse de données Le processus de la fouille de données Algorithmes pour la fouille de données et environnements

• Représentation des connaissances et acquisition: un rappel sur les systèmes à base de règles (SBR)

Modalité du module – 14 séances Cours-TP-TP-TD Mardi Matin (9h30-12h30) – Enseignants: V. Corruble, J-D. Zucker – 1 mini-projet (apprentissage par renforcement) + 1 DataMining. © J-D. ZUCKER LIP6

3

Plan du premier cours

I. L’apprentissage: généralités – Définition, exemples, motivations, historique

II. Construire un système capable apprenant III. L’apprentissage par renforcement IV. Exemple illustratif et MiniProjet (TD)

© J-D. ZUCKER LIP6

4

I. L’apprentissage pour une machine

Votre Votredéfinition: définition:

© J-D. ZUCKER LIP6

5

I.1 Définition •Qu’est-ce que l’apprentissage ? – “Changement(s) dans un système lui permettant d’améliorer ses performances sur une tâche déjà vue ou similaire” (Simon,83)

•Qu’est-ce qu’une tâche ? – Classification (diagnostic médical, détection de fraudes, qualité d’investissements, séquences ADN, parole, écriture, images astronomiques, etc.) – Résolution de problème, planification et action (problèmes calculatoires, jouer aux dames, commander un bras manipulateur, conduire une voiture, etc.)

•Comment mensurer les performances ? – Taux de classification sur des exemples tests, cohérence et qualité des solutions, ...

© J-D. ZUCKER LIP6

6

Exemples illustratifs d’apprentissages Classification, Organisation Diagnostiquer un churner Accorder un prêt Rejeter des pièces sur une chaîne de prod. Quelle bannière afficher sur mon site

vache saine

mange herbe

Améliorer une heuristique Conduire une voiture Jouer au football

vache folle possède pattes

reproduit vivipare

Résolution de problèmes, planification et action

reproduit ovipare

mange viande possède écaille

possède bec mange graines © J-D. ZUCKER LIP6

7

I.3 Quels “changements” pour apprendre?

Il

y a deux manières principales les performances d’un système:

pour

améliorer

➂- Acquérir de nouvelles connaissances – Acquérir de nouveaux faits (connaissances déclaratives) – Acquérir de nouvelles capacités (connaissances procédurales)

②- Adapter son comportement – résoudre les problèmes plus correctement, – résoudre les problèmes plus efficacement, ...

© J-D. ZUCKER LIP6

8

I.4 Importance de l’apprentissage ? (1/2)

Raisons pratiques/économiques: Découvrir de nouvelles K, de nouveaux motifs, des régularités (le Data Mining, Web Mining, Text Mining ) La nécessité de développer des systèmes adaptatifs (agents d’interfaces, filtreurs de courrier personnalisés, robots adaptatifs, agents virtuels) Le coût et la difficulté de construire de larges SBC (ou SE). C’est le goulot d’étranglement de l’acquisition des connaissances Ex: MYCIN 400 règles mais .... 100 ha !

© J-D. ZUCKER LIP6

9

I.4 Importance de l’apprentissage ? (2/2)

• Raisons scientifiques/théoriques – Mieux comprendre l’apprentissage humain – Modéliser les mécanismes d’apprentissage – Analyser le statut philosophique de l’induction

• Raisons historiques/expérimentales – La quantité d’information: WWW, Entrepots de données (Data Warehouse), etc. – Des algorithmes existent déjà et ils ont prouvé leur intérêt: BMT 30,000 règles et seulement 9 ha !

© J-D. ZUCKER LIP6

10

I.5 Enjeux pour l’e-commerce •

On-line Behaviour – Where are they now? – What are they reading? – Where did they come from?

•

Historical Behaviour – What did they buy last time? – Where do they spend most of their time? – How long do they stay?

•

Customer Identity – Are they male or female? – What are their interests?

© J-D. ZUCKER LIP6

11

Know your eCustomers!

I.5 Enjeux pour l’e-commerce: CRM et l’eCRM

•

How effective are my marketing efforts?

•

What types of content, products, or services draw people back?

•

How do visitors respond to the different parts of my site?

•

When visitors use one site area or service, what else will they be interested in?

•

Were there any dramatic changes in PR or marketing-generated traffic yesterday?

•

When do certain segments of visitors visit?

© J-D. ZUCKER LIP6

12

I.5 Enjeux pour l’e-commerce: bénéfices Technique

Advantage

Path Analysis

Discover major paths through your web site, those that lead to sales and what drives web site performance.

Improve effectiveness of web site design, measure the impact of creatives (e.g. animated pictures)

Referral Analysis

Discover where your best customers are coming from.

Shopping Basket Analysis

Discover which products are bought together or in sequence

Assess success of advertising and affiliations with other web sites Recommend the mix of products,

Marketing Campaign Analysis

Predict who is most likely to respond to different marketing programs, measure campaing response.

Benefit

services and offers that customers are most likely to buy - increase sales. Improve response to campaings increase sales.

Gain deeper understanding of customers, develop personalised Curstomer Profiling and Segmentation behaviours and have similar needs or offers and campaigns - maximise your preferences. marketing ROI. Develop targeted customer retention Predict customers who are most likely Churn Modeling and loyalty programs - reduce to leave. customer attrition. Identify customers who exhibit similar

LifeTime Value Modeling

Understand customer lifetime value and profitability.

Maximise customer profitability © J-D. ZUCKER LIP6

13

Web Mining: déjà de nombreux outils

© J-D. ZUCKER LIP6

14

I.6. Différents types d’apprentissage • • • • • • • • • •

Apprentissage par renforcement (RL) Apprentissage symbolique (Concept Learning) Apprentissage à partir de cas (CBR) ; K-PPV Algorithmes génétiques (Genetic Algorithm) Construction de classifications (Clustering) Apprentissage de programmes (prolog (ILP); PG) Apprentissage neuronal (NN) Apprentissage probabiliste, par cœur, par analogie Apprentissage par explications (EBL) Approches hybrides, ....

© J-D. ZUCKER LIP6

15

I.7. Une taxinomie des apprentissages (intuitif) Méthodes d’apprentissage

Raisonnement déductif De l’explication à la révision de connaissances

Raisonnement inductif De l’expérimentation à l’acquisition de connaissances

Avec professeur (supervisé)

Sans professeur (non supervisé)

Action

Planification

(monde inconnu)

(monde connu)

© J-D. ZUCKER LIP6

16

Apprentissage inductif – – – – –

Etant donné un ensemble de pairs Trouver une généralisation f telle que

xi , yi

f (xi )

soit comme

yi

Etant donné un ensemble d'observations Faire une classification des x i,

Mangeable ?

© J-D. ZUCKER LIP6

17

Apprentissage par renforcement

– Etant donné un lien avec l'environnement (réel ou virtuel) – Trouver un comportement qui maximise le renforcement à long terme.

Etat Observation

Reinf

Action

© J-D. ZUCKER LIP6

18

II. Architecture générique d’un système d’apprentissage

Connaissances Apprises ou Révisées

Apprentissage Fonctionnalités

Environnement

© J-D. ZUCKER LIP6

19

II. Définir un système d’apprentissage

1) Définir la situation d’apprentissage: le problème 2) Choisir la fonction cible et sa représentation 3) Choisir un algorithme pour apprendre la fonction cible 4) Evaluer les résultats de l’apprentissage

© J-D. ZUCKER LIP6

20

II.1.a. Situations d’apprentissage

• Un Domaine: a) perception b) cognition c) action – a) Vision, Parole; b) lang. nat., design, diagnostic, raisonnement, planification ; c) contrôle de robot.

• Une tâche T – Apprendre un concept, des règles, une grammaire, ...

• Une évaluation des performances P de l’apprentissage – taux d’erreur de classification sur exemples nouveaux, efficacité, jugement d’un expert du domaine.

• Un protocole: l’experience E du système © J-D. ZUCKER LIP6

21

II.1.b. Définir la tâche d’apprentissage T Améliorer les performances P d’un système sur une tache T à partir d’expériences E. • T: Jouer au dames • T: Reconnaître des mots écrits scannés • T: Conduire une voiture sur une autoroute • T: Diagnostic des vaches malades • T: Construire un plan de déplacement dans une pièce © J-D. ZUCKER LIP6

22

Superposé II.1

P: % de parties gagnées ; E: Jouer contre soi-même P: % mots correct. class. ; E: BDD de mots correc. classés. P: Distance moyenne sans erreur ; E: séquences vidéo P: % patient diagno. ; E: BDD dossiers patients et diagnos P: Temps moyen constr. plan ; E: situations enrregistrées © J-D. ZUCKER LIP6

23

II.1.c. Définir le protocole (l’experience E) • Formes des données – Supervisé / Non-supervisé – En ligne/ hors Ligne – Incrémentale ou non – bruitées ou non

• Origine des données – Aléatoire, expert, utilisateur – Possibilité d’interroger un oracle – Possibilité de faire ses propres expériences pour collecter des données.

• Représentativité des données © J-D. ZUCKER LIP6

24

II.1.d. Qu’est-ce qu’une bonne tâche d’apprentissage

1. La tâche ne doit pas être déterministe. Des problèmes qui ont des solutions ou des petits espaces de recherche(s) sont inintéressants ! 2. Il doit y avoir un but idéal et des buts intermédiaires dont on peut mesurer la distance au but idéal (ex: % de classif) 3. Il faut des connaissances sur la tâche pour l’évaluer. 4. La tâche doit être familière à suffisamment de personnes pour que son automatisation soit utile !

© J-D. ZUCKER LIP6

25

II.2.a. Choisir la fonction cible ...

• Question: que doit-on apprendre et comment la connaissance apprise sera utilisée ?

• Dans le jeux des dames anglaises [checkers (Samuel,59)]: – On peut apprendre à jouer les coups légaux: --> coup-légal

LEGAL(damier)

– On peut apprendre à choisir le meilleur des coups légaux: CHOIX(damier légaux) --> meilleur-coup – On peut chercher à apprendre à évaluer une position: V(damier) --> score © J-D. ZUCKER LIP6

26

II.2.b. fonction cible idéale ... et approximative

• Soit V(d) la fonction d’évaluation d’un damier – – – –

V(d)=1 si d est une position finale gagnante V(d)=-1 si d est une position finale perdante V(d)=0 si d est une position finale nulle Si d n’est pas une position finale: V(d)=v(d’) où d’ est la position finale ayant le meilleur score que l’on peut atteindre en jouant depuis la position d.

1040 • Cette définition n’est pas opérationnelle • Une définition opérationnelle: temps polynomial ^ • Une approximation V de la fonction idéale V

© J-D. ZUCKER LIP6

27

II.2.c. Choisir la représentation de la fonction cible • La fonction à apprendre peut se représenter par – – – – –

table de hachage règles symboliques réseau de neurones fonction numérique continue etc.

• Compromis représentativité/complexité d’apprentissage • Pour les dames: par ex. une combinaison linéaire ^

– V (d) = w 0 + w 1 x RN(d) + w 2 x RR(d) + w3 x DN(d) + w 4 x DR(d) + w5 x PNM(d) + w 6 x PRM(d) )

Caractéristiques Ci: RN=roi noirs, RR=roi rouge, DN=dames noires, DR=dames rouges, PNM=pieces noires menacées , PRM=pieces rouges menacées un exemple: ( (RN=3, RR=1, DN=2, DR=0, PNM=0, PRM=1), 1) © J-D. ZUCKER LIP6

28

II.3. Choisir un algorithme d’apprentissage et l’évaluer • Un algorithme d’apprentissage utilise des exemples d’une fonction pour en trouver une approximation qui est correcte vis à vis des exemples donnés. • Evaluation xpérimentale – tests (benchmarks), – vitesse, précision, évolution

• Evaluation théorique – complexité des algorithmes, – preuves sur l’apprenabilité © J-D. ZUCKER LIP6

29

I.

L’apprentissage: généralités –

Définition, exemples illustratifs, motivations, historique

II. Construire un système d’apprentissage

III.L’apprentissage par renforcement IV. Exemple illustratif (TD)

© J-D. ZUCKER LIP6

30

III. Apprentissage par renforcement: situation

Environnement

Récompense

Perception Action

✓Agent autonome ✓Apprentissage en ligne ✓Apprentissage modifie l'env. ✓Monde peut être non déterministe © J-D. ZUCKER LIP6

31

III.1. Apprentissage par renforcement (définition) Apprentissage par renforcement (ou interaction) But: (Apprendre à) prendre la meilleure action dans une situation Si L'environnement donne une récompense r pour une action a dans l'état Si (ou pour une séquence d'actions) Origine: apprentissage des animaux (par exemple souris) Aujourd'hui: de l'essai-erreur à la planification controlée

≠ Apprentissage supervisé:

un professeur dit la bonne action à prendre en Si (par exemple: dans la position Si il faut jouer sur la case 33) © J-D. ZUCKER LIP6

32

Pourquoi apprendre par renforcement ?

• Le signal d'un professeur est rarement disponible • Une récompense est plus facile à spécifier qu'un comportement:

+ ----

for removing dirt for consuming energy for damaging furniture for terrorizing cat

© J-D. ZUCKER LIP6

33

I.2. Exemples illustratifs ✓ Les jeux (dans certains cas): jugements intuitifs, blitz... ✓ A la naissance, une gazelle tient à peine debout... ✓ Attraper son paquet de céréal favori, un ballon,... ✓ Stratégie d'un robot (se recharger)/(continuer) ✓ Contrôleurs adaptatifs temps réel (prod./coût/qualité) ✓ Equilibre

✓ Point communs: ✓ intéractions, sous-buts, incertitude de l'environnement. ✓ l'expérience permet d'apprendre... © J-D. ZUCKER LIP6

34

Exemple 1: Le problème du "bandit à k bras" p2=?

p1=? 0

pk=?

p3=? 1

1

0 .......

Bandit 1







Bandit 2

Bandit 3

Bandit k

Il y a k machines à sous Chacune donne 0 ou 1 avec une loi de probabilité cachée On peut jouer h coups. Comment choisir les machines pour optimiser le gain? © J-D. ZUCKER LIP6

35

Exemple 2: Le jeu de Tic-Tac-Toe Soit

• Un TicTacToe à 9 cases • Comment apprendre à évaluer une position ? Apprentissage Supervisé:

• Un ensemble de couple (positions notes):

, 10

Apprentissage par renforcement:

• On apprend la valeur des positions en fonction des parties jouées. © J-D. ZUCKER LIP6

36

I.4. Quand doit-on faire appel à l'app. par renf. ? ✔ Une tâche en plusieurs étapes où la récompense ne vient qu'à la fin d'une succession de choix (un état final) e.g. Recherche dans un labyrinthe

✔ La récompense peut venir plus fréquemment (perdre une pièce aux échec) mais celle-ci ne donne pas d'indication sur la solution optimale e.g. Prise de pièces (attention un sacrifice peut mener à la victoire)

✔ On ne sait pas quelle récompense attribuer à quelle action credit assigment problem

© J-D. ZUCKER LIP6

37

II.1. Deux types d'approche pour apprendre π π

A) Apprendre V la fonction d'utilité liée aux états (TD-learning) Dans l'état Si choisir l'action a qui maximise l'utilité V(Si+1) supposée de l'état Sj+1 obtenue après avoir fait l'action a. Requiert un modèle assez précis de l'environnement pour connaître les états où mènent les actions (exemple: Jeux de dame+Minimax)

π

B) Apprendre Q la fonction d'utilité liée aux actions (Q-learning) Choisir l'action a qui maximise Q(Si,a): l'utilité supposée de l'action a dans l'état Si Requiert un modèle limité de l'environnement: on n'a besoin que de mesurer la valeur d'une action et non l'état résultant de l'action (pas de look-ahead) (exemple: attraper une plume, blitz)

© J-D. ZUCKER LIP6

38

Modèlisation: états, actions et récompenses r(s,a) r(s,a)récompense récompenseimmédiate immédiate(inconnue (inconnueau audépart) départ) 0

100 But 0

0

0

0

0

0 0

100

0 0

0

➤ Dernière étape qui assure la récompense (jeux, monde des blocs, etc.) ➤ Tâche: apprendre la meilleure stratégie qui maximise le gain © J-D. ZUCKER LIP6

39

Critères de gains ➤ Horizon fini

k

∑ r = r + r +...+r t =0

t

0

1

k

➤ Horizon infini avec intérêt ∞

2 3 t γ r = r + γ r + γ r + γ ∑ t 0 1 2 r3 +... t =0

➤ En moyenne

1 k lim ∑ rt k →∞ k t =0 © J-D. ZUCKER LIP6

40

Comparaison des comportements k=4, γ=0.9

Quelle est la meilleure stratégie

k

∑ rt t =0

∞

1 k rt ∑ γ rt lim ∑ k →∞ k t =0 t =0 t

+2

6

16.0

2

0

59.0

10

0

58.4

11

+10

+11

© J-D. ZUCKER LIP6

41

Récompense Cumulée ∞

π

➤ On définit la récompense cumulée V (st) =

π

∑γ t =0

t

rt

π * = argmax( v (s))

➤ Le problème: trouver

π

90

100 But

90

81

0

100

π* V*(s)=V V*(s)=Vπ*(s) (s)récompense récompensecumulée cumuléeoptimale optimale © J-D. ZUCKER LIP6

42

Une stratégie

• Apprendre une fonction Q:

Q : S × A → valeur • L'utiliser pour choisir la meilleure action

π (s) = argmax Q(s, a) a ∈A

© J-D. ZUCKER LIP6

43

Choix d'une action

• Exploration versus exploitation: • Si vous avez confiance en vous: – choisissez

π (s) = argmax Q(s, a)

• Sinon,

a ∈A

10

– explorez

??

© J-D. ZUCKER LIP6

44

Processus de décision Markovien

• Propriété de Markov

P(s t | st −1 , at −1 ) = P(s t | st −1 , at −1 , st − 2 , a t − 2 ,...)

• Alors

Q(s, a) = R(s, a) + γ

∑ P( s ′ | s, a) max Q(′∈ s ′, a ′ )

s′ ∈S

récompense taux immédiate d'intérêt

a

prochain état espéré

A

Valeur future

• Theorem: Etant donné P et R, il y a une unique Q [Bellman] •

Mais si P et R sont inconnus... il faut apprendre une politique © J-D. ZUCKER LIP6

45

Trouver un algorithme: problèmes BUT: BUT:Trouver Trouverune unepolitique politiqueππ: :SS--> -->A,A, qui associel'action l'actionaat tqui quioptimise optimiseun uncritère critèrede degain. gain. quiààtout toutétat étatsst tassocie ➤ "Temporal Credit Assignment": quelles sont les actions qui doivent être créditées ? ➤ Exploration/exploition: quel compromis avoir ? ➤ Etats partiellement observables: si les capteurs ne donnent pas toutes les infos ? ➤ Apprentissage à long terme: ré-utiliser des connaissances apprises pour d'autres taches ? Performances: vitesse de convergence, regret © J-D. ZUCKER LIP6

46

Quelle fonction apprendre ? ➤ La politique optimale π* ? ➤pas d'exemples de la forme (s,a)

➤ La récompense cumulée V* ? ➤L'agent choisira alors s1 plutôt que s2 car V*(s1) > V*(s2) et comme il faut choisir une action.

π *( s) = argmax(r(s,a) + γ V * (δ (s,a))) a

➤Intéressant ssi r(s,a) et δ(s,a) sont totalement connues

➤ La fonction Q ci-dessous offre une réponse δ(s,a)) ➤On définit Q(s,a)= r(s,a) + γ V*(δ ➤ Point clef: l'agent pourra prendre les décisions optimales sans connaissances des fonctions r(s,a) et δ(s,a) © J-D. ZUCKER LIP6

47

La "beauté" de la fonction Q ➤ La fonction Q est définit comme étant LA fonction qui résume en UN nombre toute l'info nécessaire sur le gain cumulé d'une action a, prise dans l'état s. Q(s,a) Q(s,a) 90

100 But

0

81 72

81

81

90 81

100

90 72

81

© J-D. ZUCKER LIP6

48

III. Un algorithme pour apprendre Q(s,a) (cas déterministe) Q(S,a)=r(s,a) + γ V*(δ(s,a))

➤ On a :

V * ( s) = max Q(s,a') a'

Q( s, a ) = r ( s, a ) + γ max Q(δ (s,a),a' )

➤ Définition récursive:

a'

Pour chaque couple s, a initialisé la table Q(s,a) à zéro.

^

Pour l'état courant s Répéter Choisir une action a et l'exécuter (exploration vs. exploitation) Réception d'une récompense immédiate r Observer le nouvel état s' MAJ de

∧

∧

Q( s, a ) ← r ( s, a ) + γ max Q(δ (s,a),a') a'

s <-- s' © J-D. ZUCKER LIP6

49

Exemple illustratif... On Prend γ =0.9

72

^ Q(s,a)

100 63 81

∧

∧

Q( s, a ) ← r + γ max Q(δ (s,a),a' ) )

adroite

a'

← 0 + 0.9 max{63,81,100}}

9090

← 90

^ Q(s,a)

100 63 81

© J-D. ZUCKER LIP6

50

Convergence ➤ Théorème: convergence de l'algo Q-learning déterministe ^

^

➤Soit Qn(s,a) l'hypothèse de Q(s,a) après la nième mise à jour. ➤Si chaque couple (état,action) est visité un nombre infiniment souvent, alors Qn(s,a) converge vers Q(s,a) quand n tend vers l'infini.

➤ Démonstration

∆

∧

n

≡ max Qn( s, a ) − Q( s, a ) s ,a

∧

∧

Q n + 1( s, a ) − Q( s, a ) = ( r + γ max Qn( s' ,a')) - ( r + γ max Q( s' ,a' )) a'

∧

a'

∧

Q n + 1( s, a ) − Q( s, a ) = γ max Qn ( s' ,a') − max Q( s' ,a' ) a'

∧

a'

∧

Q n + 1( s, a ) − Q( s, a ) ≤ γ max Qn( s' ,a') − Q( s' ,a' ) a'

∧

∧

Q n + 1( s, a ) − Q( s, a ) ≤ γ max Qn( s' ' ),a' ) − Q( s' ' ,a' ) s ,a '

∧

Q n + 1( s, a ) − Q( s, a ) ≤ γ

∆

n

© J-D. ZUCKER LIP6

51

Critères de gains espérés: cas non déterministe ➤ Horizon fini

 k  E  ∑ rt  = r0 + r1 +...+ rk  t =0 

➤ Horizon infini avec intérêt

 ∞ t  E  ∑ γ rt  = E (r0 + γr1 + γ 2r2 + γ 3r3 +...)  t =0  ➤ En moyenne

1 k  lim E  ∑ rt  k →∞  k t =0  © J-D. ZUCKER LIP6

52

Récompenses et actions non déterministes ➤ e.g. au BackGammon: récompense dépend des dés Pour chaque couple s, a initialisé la table Q(s,a) à zéro.

^

Pour l'état courant s Répéter Choisir une action a et l'exécuter Réception d'une récompense immédiate r Observer le nouvel état s' ∧

MAJ de s <-- s'

∧

∧



∧



Q n ( s, a ) ← Q n − 1( s, a ) + αn r ( s,a ) +γ max Q n-1( δ (s,a),a') ) −Q n −1( s ,a )  a' 



erreur temporelle (TD error)

➤ Théorème de convergence (Watkins & Dayan 92)

αn

1 = 1+ visites ( s ,a ) n © J-D. ZUCKER LIP6

53

Temporal Difference Learning TD(λ) ï

Idée: ne pas mettre à jour que les successeurs ou prédécesseurs immédiats. ∧

Q(1) ( st , at ) = rt + γ max Q( st + 1,a) a

∧

Q(2 ) ( st , at ) = rt + γrt + 1 + γ 2 max Q( st + 2,a) a

... ∧

Q(n ) ( st , at ) = rt + γrt + 1+...+ γ n max Q( st + n,a) a

[

]

Q(λ ) ( st , at ) = (1 − λ ) Q(1) ( st , at ) + λ Q(2 ) ( st , at ) + λ 2 Q(3) ( st , at ) +.... ∧ Q(λ ) ( st , at ) = rt + γ (1 − λ ) max Q( st,a) + λQ(λ ) ( st + 1, at + 1)  a  

© J-D. ZUCKER LIP6

54

TD /TP: le jeux de Tic-Tac-Toe Soit

➤ Un damier à 9 cases Donner

➤ Construire un programme qui apprenne à gagner Approche

➤ a) un apprentissage par renforcement basé sur l'action

© J-D. ZUCKER LIP6

55

IV.1. Exemple illustratif du tic-tac-toe Renforcement par différence temporelle (TD-learning [temporal difference]) On associe à chacune des 512 positions une valeur initiale égale à V(st=0)=0.5 (sauf pour les positions perdantes 0. et gagnantes 1.). On joue ensuite contre un opposant en choisissant l'action qui mène à la position de plus haute récompense (pour laquelle V(s) est maximale) ou parfois on choisit β) un autre coup, dit exploratoire. aléatoirement (β Après chaque coup non exploratoires on met à jour les valeurs: α fonct. décroissante) V(st+1) := V(s t) + α [ (γγ=1) x max(V(δδ(st)) - V(s t)] (α ==> converge vers une décision optimale dans chaque état

© J-D. ZUCKER LIP6

56

IV.2. Exemple illustratif du tic-tac-toe (suite) Position de départ a Mouvement de l'adversaire Notre mouvement Mouvement de l'adversaire Notre mouvement Mouvement de l'adversaire Notre mouvement

{ { { { { {

MAJ b

c*

c

d

e*

e f

MAJ

g* © J-D. ZUCKER LIP6

57

IV.3. Exemple illustratif du tic-tac-toe (suite)

Mouvement de l'adversaire Notre mouvement Mouvement de l'adversaire Notre mouvement

{ { { {

α = 0.1

V(x) := 0.5 + 0.1 x [1. - 0.5] x y

MAJ

V(z) = 1 z*

MAJ

Position Positiongagnante gagnante ï ï

L'état x passe d'une valeur de 0.5 à 0.55 Si l'adversaire joue toujours y dans la position x sa valeur ne cessera d'augmenter [m'me si x est, dans l'absolu, une position perdante] © J-D. ZUCKER LIP6

58

Résumé ➤ L'apprentissage par renforcement concerne les problèmes d'apprentissage par des agents autonomes de Tâches où le but est de maximiser les récompenses reçues. ➤ Le Q-learning est une forme d'apprentissage par renforcement qui a des bonnes propriétés de convergence. ➤ Le Q-learning fait partie d'une famille plus large d'algorithme: Temporal Difference Learning ➤ Lien entre l'Apprentissage par renforcement et les processus décisionnels markovien (PDM ou MDP) et la programmation dynamique. ➤ Renouveau actuel de l'apprentissage par renforcement...

© J-D. ZUCKER LIP6

59

Bibliographie

Apprentissage en général Dietterich, T. (1990). Readings in Machine Learning. Morgan Kaufmann. Langley. P. (1996). Elements of Machine Learning. Morgan Kaufmann. Mitchell, T. (1998). Machine Learning. MacGraw Hill. http://www.ai.univie.ac.at/oefai/ml/ml-resources.html

Apprentissage par renforcement Samuel, A. (1967). Some studies in machine learning using the game of checkers. IIó recent progress. IBM Journal on Research and Development, (pp. 601-617). Sutton, R. (1998). Introduction to Reinforcement Learning. http://envy.cs.umass.edu/People/sutton/sutton.html

© J-D. ZUCKER LIP6

60

V. Conclusions ➤ Apprendre c'est chercher une fonction d'approximation: ➤recherche dans un espace d'hypothèses

➤ Différentes méthodes d'apprentissage emploient différentes techniques de recherche ➤ Différentes représentations ➤numériques, ➤règles ou fonction logique, ➤cas, ➤polynômes, ...

➤ Différents algorithmes ➤Descente du gradient ➤Généralisation ➤Plus proches voisins ➤Renforcement temporel, ... © J-D. ZUCKER LIP6

61

Exemple: TD-Gammon

Démarre avec un réseau aléatoire Joue des millions de parties contre soi-même Apprend une fonction d’évaluation Donnerait le meilleur joueur de BackGammon du monde ! © J-D. ZUCKER LIP6

62

Bibliographie

Apprentissage en général Dietterich, T. (1990). Readings in Machine Learning. Morgan Kaufmann. Langley. P. (1996). Elements of Machine Learning. Morgan Kaufmann. http://www.ai.univie.ac.at/oefai/ml/ml-resources.html

Apprentissage par renforcement Samuel, A. (1967). Some studies in machine learning using the game of checkers. IIó recent progress. IBM Journal on Research and Development, (pp. 601-617). Sutton, R. (1998). Introduction to Reinforcement Learning. http://envy.cs.umass.edu/People/sutton/sutton.html

© J-D. ZUCKER LIP6