Apprentissage bayésien


Introduction | Théorème de Bayes | Apprentissage de concepts | Apprentissage d'une fonction à valeurs réelles | Longueur de description minimale | Classeur bayésien optimal | Classeur bayésien naïf | Réseaux bayésiens


Introduction

Deux rôles des méthodes bayésiennes

Fournir des algorithmes d'apprentissage

Fournir un cadre conceptuel utile

Caractéristiques de l'apprentissage bayésien

^

Théorème de Bayes

P(h|D) = P(D|h)P(h)/P(D)
P(h)
Probabilité a-priori de l'hypothèse h
P(D)
Probabilité a-priori des données D
P(h|D)
Probabilité de h étant donné D
P(D|h)
Probabilité de D étant donné h

Choix des hypothèses

P(h|D) = P(D|h)P(h)/P(D)

On veut généralement l'hypothèse la plus probable étant donné l'observation : hypothèse MAP (Maximum A Posteriori) :

hMAP= argmaxh ∈ H P(h|D)
 = argmaxh ∈ H P(D|h)P(h)/P(D)
 = argmaxh ∈ H P(D|h)P(h)

Si on suppose en plus que P(h) est constant, on obtient l'hypothèse la plus vraisemblable ML (Maximum Likelihood) :

hML= argmaxh ∈ H P(D|h)

Exemple d'application du théorème de Bayes

Est-ce qu'un patient a un cancer ou non ?

Un patient subit des analyses médicales et le résultat du laboratoire est positif. Le test qu'il a subit rend un résultat positif dans 98% des cas où la maladie est vraiment présente, et un résultat négatif dans 97% des cas où il n'y a pas de maladie. On sait de plus que 0,8% de la population souffre de ce cancer.

P(cancer) = 0,008P(¬ cancer) = 0,992
P(+|cancer) = 0,98P(-|cancer) = 0,02
P(+|¬ cancer) = 0,03P(-|¬ cancer) = 0,97

Hypothèse MAP :

hMAP = ¬ cancer
P(cancer|+) = 0,0078 / (0,0078 + 0,0289) = 0,21


Formules de base pour le calcul de probabilités

Règle du produit

P(A ∧ B) = P(A|B)P(B) = P(B|A)P(A)

Règle de la somme

P(A ∨ B) = P(A) + P(B) - P(A ∧ B)

Théorème de la probabilité totale

Soient des événements A1, A2, ...,An mutuellement exclusifs avec ∑i P(Ai) = 1, alors

P(B) = ∑i P(B|Ai)P(Ai)

^

Théorème de Bayes et apprentissage de concepts

Algorithme d'apprentissage MAP par force brute

  1. Pour chaque hypothèse h de H, calculer la probabilité a-posteriori P(h|D) = P(D|h)P(h)/P(D)
  2. Rendre l'hypothèse hMAP de plus grande probabilité a-posteriori hMAP = argmaxh ∈ H P(h|D)

Relation avec l'apprentissage de concepts

Considérons la tâche d'apprentissage usuelle :

Quelle est l'hypothèse MAP produite par la règle de Bayes ? Est-ce que TrouverS rend l'hypothèse MAP ?

On considère un ensemble fixe d'instances {x1, x2, ..., xm}. On suppose que D est l'ensemble des classes {c(x1), c(x2), ..., c(xm)}.

Hypothèses

  1. Ensemble d'apprentissage sans bruit
  2. H contient le concept cible c
  3. Il n'y a pas de raison a-priori qu'une hypothèse soit plus probable qu'une autre

On choisit P(h) constant : ∀ h ∈ H, P(h) = 1 / |H|.

On définit P(D|h) :

Alors P(h|D) = 1/|VSH,D| si h est cohérente avec D, O sinon.

Preuve

Si h n'est pas cohérente avec D, P(D|h) = 0, donc P(h|D) = P(D|h)P(h)/P(D) = 0

Si h est cohérente avec D, P(D|h) = 1, donc P(h|D) = P(h)/P(D) = 1/[P(D)|H|]

h ∈ H P(h|D) = 1 = |VSH,D|/[P(D)|H|],
donc P(D) = |VSH,D|/|H|
Autre approche : P(D) = ∑h ∈ H P(D|h)P(h)
= ∑h ∈ VSH,D 1 × 1/|H| + ∑h ∉ VSH,D 0 × 1/|H|
= |VSH,D|/|H|


Evolution des probabilités a-posteriori


Caractérisation des algorithmes d'apprentissage par rapport à l'hypothèse MAP

Système inductif

Entrées
Exemples d'apprentissage D
Espace des hypothèses H
Sorties
Hypothèse résultat

Système bayésien équivalent

Entrées
Exemples d'apprentissage D
Espace des hypothèses H
Explicitation des hypothèses a-priori : P(h) uniforme
P(D|h) = 1 si cohérent, 0 sinon
Sorties
Hypothèse résultat

^

Apprentissage d'une fonction à valeurs réelles

Hypothèses du maximum de vraisemblance et de la moindre erreur quadratique

Considérons une fonction cible f à valeurs réelles. Soient les exemples d'apprentissage <xi, di> où di est une valeur bruitée : di = f(xi) + ei. ei est une variable aléatoire tirée indépendamment de chaque xi suivant une distribution gaussienne de moyenne égale à 0.

Alors l'hypothèse la plus vraisemblable hml est celle qui minimise la somme des carrés de l'erreur :

hml = argminh ∈ Hi (di - h(xi))2

Preuve

hml= argmaxh ∈ H p(D|h)
 = argmaxh ∈ Hi p(di|h)
 = argmaxh ∈ Hi 1/(2πσ2)1/2 e- 1/2 ((di - h(xi))/σ)2
 = argmaxh ∈ Hi ln(1/(2πσ2)1/2) - 1/2 ((di - h(xi))/σ)2
 = argmaxh ∈ Hi - 1/2 ((di - h(xi))/σ)2
 = argmaxh ∈ Hi - (di - h(xi))2
 = argminh ∈ Hi (di - h(xi))2

Remarques


Apprendre à prédire des probabilités

On veut, par exemple, prédire la probabilité de survie d'un patient

f'(x) = P(f(x)=1)

Les exemples d'apprentissage sont de la forme <xi,di> où d vaut 0 ou 1. On veut entrainer un réseau de neurones à rendre une probabilité étant donné xi (pas 0 ou 1).

Dans ce cas, on montre que :

hML = argmaxh ∈ Hi di ln h(xi) + (1-di) ln(1-h(xi))

Preuve

hML= argmaxh ∈ H P(D|h)
 = argmaxh ∈ Hi p(xi,di|h)
 = argmaxh ∈ Hi p(di|h,xi)p(xi)
Rq : P(di|h,xi) = h(xi) si di=1, (1-h(xi)) si di=0
 = argmaxh ∈ Hi h(xi)di (1-h(xi))1-dip(xi)
 = argmaxh ∈ Hi h(xi)di (1-h(xi))1-di
 = argmaxh ∈ Hi di ln(h(xi)) + (1-di) ln(1-h(xi))

Règle de modification des pondérations

wjk ← wjk + Δwjk
Δwjk = η ∑i (di - h(xi)) xijk

^

Principe de longueur de description minimale

Rasoir d'Occam

Préférer les hypothèses les plus courtes

MDL

Préférer l'hypothèse h qui minimise :

hMDL = argminh ∈ H LC1(h) + LC2(D|h)

où LC(x) est la longueur de la description de x dans l'encodage C

Exemple

H = arbres de décision, D = classes des exemples

LC2(D|h) = 0 pour les exemples classés correctement par h. On a seulement besoin de décrire les exceptions.

hMAP= argmaxh ∈ H P(D|h)P(h)
 = argmaxh ∈ H log2 P(D|h) + log2 P(h)
 = argminh ∈ H - log2 P(D|h) - log2 P(h)

Fait intéressant de la théorie de l'information : le code optimal (la longueur de codage la plus courte) d'un événement de probabilité p est - log2 p bits. L'interprétation est donc :

hMAP préfére donc l'hypothèse qui minimise longueur(h) + longueur(erreurs de classification)

^

Classification la plus probable de nouvelles instances

Jusqu'à présent nous avons cherché l'hypothèse la plus probable étant donné les données D (hMAP). Etant donné une nouvelle instance x, quelle est sa classe la plus probable ?

Exemple

Classeur bayésien optimal

argmaxv ∈ Vh ∈ H P(v|h)P(h|D)

Exemple

P(h1|D) = 0,4P(-|h1) = 0P(+|h1) = 1
P(h2|D) = 0,3P(-|h2) = 1P(+|h2) = 0
P(h3|D) = 0,3P(-|h3) = 1P(+|h3) = 0

h ∈ H P(+|h)P(h|D) = 0,4

h ∈ H P(-|h)P(h|D) = 0,6

argmaxv ∈ Vh ∈ H P(v|h)P(h|D) = -


Classeur de Gibbs

Le classeur bayésien optimal fournit le meilleur résultat, mais il peut être coûteux s'il y a beaucoup d'hypothèses.

Algorithme de Gibbs

  1. Choisir une hypothèse au hasard en fonction de P(h|D)
  2. L'utiliser pour classer la nouvelle instance

Surprise

Si on suppose que les concepts cibles sont choisis au hasard dans H en fonction de la probabilité a-priori sur H, alors :

E[erreurGibbs] ≤ 2 × E[erreurBayésienOptimal]

Si on suppose une distribution de probabilité uniforme sur H, alors

^

Classeur bayésien naïf

Une des méthodes les plus pratiques avec les arbres de décision, réseaux de neurones et plus proches voisins.

Conditions d'emploi

Applications réussies

Soit une fonction cible f: X → V, où chaque instance x est décrite par ses valeurs <a1, a2, ..., an>. La valeur la plus probable de f(x) est :

vMAP= argmaxv ∈ V P(v|a1, a2, ..., an)
 = argmaxv ∈ V P(a1, a2, ..., an|v) P(v) / P(a1, a2, ..., an)
 = argmaxv ∈ V P(a1, a2, ..., an|v) P(v)

Hypothèse naïve de Bayes

P(a1, a2, ..., an|v) = ∏i P(ai|v)

Classeur bayésien naïf

vNB = argmaxv ∈ V P(v) ∏i P(ai|v)

Apprentissage

Pour chaque valeur v de la fonction cible
	estimer P(v)
	Pour chaque valeur a de chaque attribut A
		estimer P(a|v)

Classification d'une nouvelle instance

vNB = argmaxv ∈ V P(v) ∏i P(ai|v) à partir des estimations apprises


Exemple

Reprenons notre exemple JouerTennis, et considérons une nouvelle instance :

<Ciel = soleil; Température = froid; Humidité = élevée; Vent = fort>

P(o) P(soleil|o) P(froid|o) P(élevée|o) P(fort|o) = 0,005

P(n) P(soleil|n) P(froid|n) P(élevée|n) P(fort|n) = 0,021

vNB = n

Subtilités

La condition d'indépendance P(a1, a2, ..., an|v) = ∏i P(ai|v) est souvent violée.

Que se passe-t-il si aucun exemple de classe v ne prend la valeur a pour l'attribut A ? Si l'estimation de P(a|v) vaut 0, alors P(v) ∏i P(ai|v) = 0 !...

Une solution typique est d'utiliser un m-estimateur :

estimation de P(a|v) =(nc + m × p) / (n + m)

Apprendre à classer des textes

Pourquoi ?

Le classeur bayésien naïf est parmi les algorithmes les plus efficaces

Quels attributs faut-il utiliser pour représenter des documents ?

  1. Représenter chaque document par un vecteur de mots : un attribut par position de mot dans le document
  2. Apprentissage : utiliser les exemples d'apprentissage pour estimer

Hypothèse de Bayes naïve d'indépendance conditionnelle

P(document|v) = ∏i P(ai = wk|v)

P(ai = wk|v) est la probabilité que le mot à la position i soit wk étant donné la classe w

Hypothèse supplémentaire : ∀ i,m, P(ai = wk|v) = P(am = wk|v)

Algorithme d'apprentissage

  1. Rassembler la liste des mots qui apparaissent dans les exemples pour constituer le vocabulaire
  2. Calculer les probabilités P(v) et P(wk|v)
    Pour chaque valeur v de la fonction cible

Algorithme de classification

Application à 20 newsgroups

Etant donné 1000 documents d'apprentissage de chaque groupe, apprendre à classer de nouveaux documents en fonction du groupe dont ils viennent

comp.graphicsmisc.forsale
comp.os.ms-windows.miscrec.auto
comp.sys.ibm.pc.hardwarerec.motorcycles
comp.sys.mac.hardwarerec.sport.baseball
comp.windows.xrec.sport.hockey
alt.atheismsoc.religion.christian
talk.religion.miscsci.space
talk.politics.mideastsci.electronics
talk.politics.miscsci.med
talk.politics.gunssci.crypt

Exemple d'article

Path: cantaloupe.srv.cs.cmu.edu!das-news.harvard.edu!ogicse!uwm.edu
From: xxx@yyy.zzz.edu (John Doe)
Subject: Re: This year's biggest and worst (opinion)...
Date: 5 Apr 93 09:53:39 GMT

I can only comment on the Kings, but the most 
obvious candidate for pleasant surprise is Alex
Zhitnik. He came highly touted as a defensive 
defenseman, but he's clearly much more than that. 
Great skater and hard shot (though wish he were 
more accurate). In fact, he pretty much allowed 
the Kings to trade away that huge defensive 
liability Paul Coffey. Kelly Hrudey is only the 
biggest disappointment if you thought he was any 
good to begin with. But, at best, he's only a 
mediocre goaltender. A better choice would be 
Tomas Sandstrom, though not through any fault of 
his own, but because some thugs in Toronto decided 

Classeur bayésien naïf : précision de classification de 89 %

^

Réseaux bayésiens

Intéressants pour les raisons suivantes :

Indépendance conditionnelle

X est conditionnellement indépendant de Y étant donné Z si la distribution de probabilité dirigeant X est indépendante de la valeur de Y étant donné la valeur de Z, c'est-à-dire :

∀ x,y,z, P(X=x|Y=y,Z=z) = P(X=x|Z=z)
P(X|Y,Z) = P(X|Z)

Par exemple, le tonnerre est indépendant de la pluie étant donné l'éclair :

P(tonnerre|pluie,éclair) = P(tonnerre|éclair)

Classeur bayésien naïf utilise l'indépendance conditionnelle pour justifier :

P(X,Y|Z) = P(X|Y,Z)P(Y|Z) = P(X|Z)P(Y|Z)

Réseau bayésien

Feu de campO,BO,¬B¬O,B¬O,¬B
F0,40,10,80,2
¬F0,60,90,20,8

Le réseau représente un ensemble d'hypothèses dindépendance conditionnelle :

Représente la distribution de probabilité jointe sur toutes ses variables

Inférence

Prédire la valeur (distribution de probabilité !) d'une variable étant données les valeurs de quelques autres variables

Apprentissage

Apprentissage des probabilités conditionnelles

Soient une variable Yi de Parents(Yi)=Ui, h l'hypothèse courante et wijk = P(Yi=yj|Ui=uk),
wijk ← wijk + η ∑exemples d de D P(Yi=yj, Ui=uk | h) / wijk

Apprentissage de la structure

Problème difficile


Nicolas Lachiche Master ILC 2009