Christel Vrain Christel.Vrain@univ-orleans · Apprentissage Statistique Relationnel Christel Vrain [email protected] LIFO Université d’Orléans Journées AAFD 12 Ch

Apprentissage Statistique Relationnel

Christel [email protected]

LIFOUniversité d’Orléans

Journées AAFD 12

Ch. Vrain (LIFO) exposé SRL 1 / 49

Plan

1 Introduction sur l’apprentissage de concepts

2 Apprentissage relationnel - Programmation logique inductiveGénéralitésPropositionnalisation

3 Statistical Relational LearningFormalismesApprentissage

4 Travaux au LIFOPropositionnalisationGraphe des prédicats

5 Conclusion


Introduction sur l’apprentissage de concepts

Apprentissage de concepts : "âge de raison"2 espaces

I X : espace de représentation des exemplesI H : espace de représentation des hypothèses

Deux relationsinstance : teste si un exemple est instance d’une hypothèse

relation de généralité ≥ sur H

h1 est plus général que h2 ssi les instances de h2 sont instances de h1

≥ est un préordre : réflexif et transitifCh. Vrain (LIFO) exposé SRL 3 / 49


Apprentissage supervisé conjonctif

SoientI X : espace de représentation des exemplesI H : espace des hypothèsesI X+ = {e1, . . . ,en} : exemples positifs du conceptI X− = {ce1, . . . , cep} : exemples négatifs du concept

trouver une hypothèse h correcte, i.e. satisfaisant :I ∀e ∈ X+,h ≥ e (complétude)I ∀e ∈ X−,h ≥/ e (cohérence)

Deux sous-problèmes (Espace des versions [Mitchell, 1982])trouver les hypothèses les plus générales discriminant lesexemples positifs des négatifstrouver les hypothèses les plus spécifiques couvrant les exemplespositifs.



Exemple

Météo Température Humidité Vent Classesoleil chaud élevé non Nsoleil chaud élevé oui Ncouvert chaud élevé non Ppluie doux élevé non Ppluie frais normal non Ppluie frais normal oui Ncouvert frais normal oui Psoleil doux élevé non Nsoleil frais normal non Ppluie doux normal non P. . . . . . . . . . . .→ Meteo = pluie couvre 3 exemples positifs et 1 négatif.→ Meteo = pluie &Vent = non couvre 3 exemples positifs et 0 négatif.



Stratégies de recherche pour l’apprentissageconjonctif

Opérateurs de généralisation (resp. spécialisation)But : transforme une hypothèse en une hypothèse plus générale(respectivement spécifique).

→ exploration de l’espace des hypothèsesplusieurs stratégies d’exploration

I descendante (top down)I ascendante (bottom up)



Apprentissage supervisé disjonctif

SoientI E : espace de représentation des exemplesI H : espace des hypothèsesI X+ = {e1, . . . ,en} : exemples positifs du conceptI X− = {ce1, . . . , cep} : exemples négatifs du concept

trouver un ensemble d’hypothèses H tel que , satisfaisant lescontraintes suivantes :

I ∀e ∈ X+,∃h ∈ H,h ≥ e(complétude)

I ∀e ∈ X−,∀h ∈ H,h ≥/ e


Apprentissage relationnel - Programmation logique inductive Généralités

L’exemple classique : les trains de Michalski

Plusieurs objets de types différents



Plusieurs représentations

une clause instanciéetrain(t2, east) ←

has_car(t2, c21, 1, rectangle, long, not_double, flat, 2, 3),has_load(c21, l211, rectangle),has_load(c21, l212, triangle),has_load(c21, l213, rectangle),has_car(t2, c22, 2, rectangle, short, not_double, none, 2, 1),has_load(c22, l221, triangle)

une base de données

#Train Dir.t1 westt2 east. . . . . .

#Load #Car Shape. . . . . . . . .l211 c21 rectanglel212 c21 trianglel213 c21 rectanglel221 c22 cercle. . . . . . . . .

[C. Rouveirol]



Rappel : atome, littéral, clauseCalcul des prédicats : L = (V, C,P)

Terme : variable ou constanteAtome : p(t1, . . . , tn), p ∈ P, ti variable ou constante

Atome clos : atome sans variablesLittéral : p(t1, . . . , tn) ou ¬p(t1, . . . , tn)

HP ens. des atoms clos

Clause : A1 ∨ . . . ∨ An ∨ ¬B1 ∨ . . . ∨ BpClause définie : A← B1, . . . ,Bp avec A,B1, . . . ,Bp atomes

Monde : Affectation d’une valeur de véritéaux atomes clos

Exemple : ami(anna, bob), fan_ciné(anna), fan_ciné(bob)



Programmation Logique Inductive

Espace de recherche : Programme logiqueProblèmes de complexité

I Taille de l’espace de recherche→ Utilisation de biais de langage→ Construction du programme par ajout (ou suppression) de clauses→ Réduction du problème d’apprentissage d’un programme logique à

celui d’apprentissage d’une clauseI Evaluation des hypothèses

→ Utilisation d’un critère local de qualité d’une clause/ critère global dequalité du programme



Exemple

Apprendre les prédicats pair et impair :I E+ = {pair(0),pair(2), impair(1), impair(3)}I E− = {pair(1),pair(3), impair(0), impair(2)}I Σ = {zéro(0), succ(0,1), succ(1,2), succ(2,3)}I Biais de langage

F au plus 2 atomes dans le corpsF une seule variable existentielle

ConstructionI Première clause

pair(X )← succ(X ,Y ), impair(Y )I Deuxième clause

impair(X )← succ(Y ,X ),pair(Y )I Programme incorrect



Foil : algorithme. fondé sur la notion de couverture en extension

. Algorithme général

1. POS ← E+

2. Tant que POS 6= ∅ faire2.1 Ajouter à P une nouvelle clause qui couvre des

éléments de POS et rejette tous les éléments de E−

2.2 Supprimer de POS les exemples couverts.

. Algorithme de construction d’une clause

1. C := p(~x)← NEG := E−

2. Tant que NEG 6= ∅ faire2.1 Ajouter à C un nouveau littéral qui couvre des

éléments de POS et rejette des éléments de E−

2.2 Supprimer de NEG les exemples rejetés

. Choix du littéral : mesure du gain apportéCh. Vrain (LIFO) exposé SRL 13 / 49

Apprentissage relationnel - Programmation logique inductive Propositionnalisation

Propositionnalisation

Reformuler un problème relationnel en un problème attribut-valeurmulti-instance

Deux étapes :I trouver un schéma intéressant pour la règle à apprendreI trouver des contraintes intéressantes sur ce schéma



Un exemple Linus

Langage de représentation :

bases de données déductives hiérarchiquesrelation avec arguments typés

prédicat d’apprentissage : r(X ,Y ,Z ) (type1, type2, type2)prédicat de base : p(X ,Y ) (type1, type2)exemples : r(a1,b1,b1), r(a1,b2,b2), r(a2,b1,b2)



Principe de LINUS [Lavrac & al.] :

1) Transformation sous la forme :

X Y Z Y = Z p(X ,Y ) p(X ,Z )

a1 b1 b1 true true truea1 b2 b2 true true truea2 b1 b2 false false true

2) Application de mécanismes d’apprentissage (Assistant, Retis)⊕ si X = a1 ∧ (Y = Z ) = true⊕ si Z = b2 ∧ p(X ,Y ) = false

3) Transformation des connaissances apprises sous forme de clausesr(X ,Y ,Z )← X = a1,Y = Zr(X ,Y ,Z )← Z = b2,¬p(X ,Y )

→ aucune variable existentielle dans les clauses



Pas aussi simple !

Dans Linus, cas attribut-valeurI Pas de variables existentielles

I Pas de clauses récursives

I Apprentissage de clauses de la forme :

pole(F ,X ,X1,Y ,Y 1,G)← diff (X ,G,D),D > 0.1,F is 1.4D + 2.7X1 + 0.58Y + 0.15Y 1

En général, cas multi-instance (variables existentielles)Changement de représentation ordre 1→ AV : HIFI, RSD, [ZeleznyF., Lavrac N., 2006], utilisation d’aggrégats [Knobbe, A.J., Siebes, A., 2002]


Statistical Relational Learning

Apprentissage statistique relationnel

Coupler l’apprentissage relationnel et des outils probabilistes (modèlesgraphiques)

Extension du classifieur bayésien naïfProlog + statistiquesGraphes dirigés : réseaux bayésiens logiquesGraphes non dirigés : modèles de Markov



De nombreux modèles

PRISM : Kameya, Sato

SLP : Cussens, Muggleton

1BC : Flach, Lachiche

PRM : Friedman, Getoor, Koller, Pfefffer, Segal, Taskar

SRM : Getoor & al.

BLP : Kersting, de Raedt

CLP(BN) : Cussens, Page, Qazi, Santos Costa

Relational Dependency Networks : Neville & Jensen

MLN : Domingos & al.

Problog : deRaedt & al

. . .



Les principaux points

Représentation et sémantiqueInférenceApprentissage de paramètresApprentissage de la structure



Deux cadres pour le raisonnement probabiliste du 1erordre [Halpern, 1989]

Probabilités sur le domaine (Type 1) : (D,Π, µ) avecI D : domaineI Π : interprétation des prédicats et fonctions sur DI µ : fonction de probabilité discrète sur D

La probabilité qu’un oiseau choisi au hasard vole est 0.9.Probabilités sur les mondes possibles (Type 2) : (D,W ,Π, µ) avec

I D : domaine,I W : ensemble des mondes possibles,I Π : interprétation des prédicats et fonctions sur D,I µ : fonction de probabilité discrète sur W

La probabilité que Tweety vole est 0.9.


Statistical Relational Learning Formalismes

PRISM : un exemple

PRISM : http ://sato-www.cs.titech.ac.jp/prism/

Règles :btype(a) : −(gtype(a,a); gtype(a,o); gtype(o,a)).gtype(X ,Y ) : −gene(father ,X ),gene(mother ,Y ).gene(P,G) : −msw(gene,P,G)

Faits :msw(gene, father ,a),msw(gene, father ,b),msw(gene, father ,o)msw(gene,mother ,a),msw(gene,mother ,b),msw(gene,mother ,o)

Pr(msw(gene, t ,a) = x ,msw(gene, t ,b) = y ,msw(gene, t ,o) =z|θa, θb, θc) = θx

aθybθ

zo

x , y , z ∈ {0,1}, x + y + z = 1, θxa , θ

yb , θ

zo ∈ [0,1], θx

a + θyb + θz

o = 1



PRISM : un exemple

Règles :btype(a) : −(gtype(a,a); gtype(a,o); gtype(o,a)).gtype(X ,Y ) : −gene(father ,X ),gene(mother ,Y ).gene(P,G) : −msw(gene,P,G)

Faits :msw(gene, father ,a),msw(gene, father ,b),msw(gene, father ,o)msw(gene,mother ,a),msw(gene,mother ,b),msw(gene,mother ,o)

Résolution sur btype(a)→ 3 explications

msw(gene, father ,a) ∧msw(gene,mother ,a)

msw(gene, father ,a) ∧msw(gene,mother ,o)

msw(gene, father ,o) ∧msw(gene,mother ,a)

Pr(bype(a)|θa, θb, θc) = θ2a + 2× θaθo



PRISM [Poole & Sato]

programme logique = faits + clausesassociation d’une distribution de probabilités paramétrée surl’ensemble des faitsprobabilité de la preuve d’un atome : produit des probabilités desfaits intervenant dans cette preuve.probabilité d’un atome : somme des probabilités des preuves decet atome.

→ sémantique distributionnelleapplications : analyse de séquence biologique, musique,planification, . . .



Programme logique bayésien [de Raedt & al.]

Des prédicats logiques et bayésiensUn programme bayésien est composé de

I un ensemble fini de clauses bayésiennes

mother -of (ann,tom). pc(ann). mc(ann).father -of (john,tom). pc(john). mc(john).

mc(X ) | mother -of (Y ,X ),mc(Y ),pc(Y ).pc(X ) | father -of (Y ,X ),mc(Y ),pc(Y ).bt(X ) | mc(X ),pc(X ).

pc, mc prennent leurs valeurs dans {a,b,o},et bt dans {a,b,ab,o}.

I une distribution de probabilité conditionnelle : Pr(t ete(c)|corps(c))

mother -of (Y ,X ) mc(Y ) pc(Y ) Pr(mc(X )|body)(mc(Xa,b,o)true a a (0.98,0.01,0.01). . . . . . . . . . . .

false a a (0.33,0.33,0.33)



Sémantique

Construction d’un réseau bayésien : nœuds = atomes closbayésiens du plus petit modèle de Herbrand du programme.Plusieurs clauses peuvent avoir la même tête : utilisation derègles de combinaison Max ou Noisy-Or

Pr(I|B) =∏A∈I

combine{cpd(cθ)|corps(cθ) ⊆ I, tete(cθ) = A}



Probabilistic Relational Models [Getoor & al.]

fondé sur le modèle entité-relation : person(Person,MC,PC,BT )

I un objet→ une relationI atome clos→ informations sur plusieurs attributs

dépendances entre attributsI à l’intérieur d’une relation : bt depend de mc et pcI dépendances entre attributs de relations différentes par des slot

chain :mc d’une personne dépend via mother(Person,Mother) des attributs mcet pc de la mère.

I Les relations entre entités sont déterministes ;

→ représentation graphique, efficacité de l’implantation et del’apprentissage, test assez facile de l’acyclicité.

SRM (stochastic relationnal model) : sémantique différente "probabilitéqu’une personne choisie au hasard vérifie telle propriété"



Markov Logic Network (MLN) [Domingos & al.]

Un MLN est un ensemble de couples (Fi ,wi), où :I Fi est une formule logique du 1er ordreI wi est un nombre réel

Exemple1.5 ∀X Smokes(X )⇒ Cancer(X )1.1 ∀X ,Y Friends(X ,Y )⇒ (Smokes(X )⇐⇒ Smokes(Y ))

Deux constantes : Anna(a) and Bob(b)



MLN : Probabilités

Probabilité d’un monde x : :

P(X = x) =1Z

exp(∑Fi

wini(x))

Où :I ni (x) est le nombre d’instances de Fi vraies dans xI Z est la fonction de partition servant à normaliser.

Par exemple,P(Smokes(a),¬Smokes(b),Cancer(a),Cancer(b),

Friends(a, a),Friends(a, b),Friends(b, a),¬Friends(b, b))



Tâches principales

Alchemy : http ://alchemy.cs.washington.edu/

Inférence :I Calculer P(requete)

P(smokes(a),¬smokes(b), cancer(a),¬cancer(b))I Calculer P(requete|observations)

P(cancer(a)|¬smokes(a), friends(a, b),¬cancer(b))

ApprentissageI Apprentissage de paramètres :→ étant donné un ensemble de clauses, apprendre leur poidsI Apprentissage de la structure :→ trouver l’ensemble des clauses et leurs poidsI Deux cadres : génératifs et discriminatifs


Statistical Relational Learning Apprentissage

Apprentissage génératif / Apprentissage discriminatif

Apprentissage génératifI Maximiser la PLL (Pseudo log likelihood)

log P∗w (X = x) = log

n∏l=1

Pw (Xl = xl |MBx (Xl ))

où MBx (Xl ) est l’état de la couverture de Markov de Xl dans lesdonnées

Apprentissage discriminatif : étant donné un prédicat Y àapprendre, des exemples Yj = yj , j = 1 . . . n, et des observationsX ,→ trouver un MLN maximisant la vraisemblance conditionnelle∑n

j=1 log P(Yj = yj |X = x)



Apprentissage de paramètres

Données complètesI Maximiser la PLL : L-BFGS (Nocedal et al., 1989) , . . .I Maximiser la CLL : PSCG (Lowd & Domingos 2007), . . .I Maximiser la marge : Max-MARGIN(Huynh & Mooney, 2009)→ Markov Logic Network

Données incomplètes : algorithme de type EMI E-Step : à partir des observations et des paramètres actuels, calcul

d’une distribution sur les différentes complétions des caspartiellement observés.

I M-Step : en utilisant les observations pondérées par eursprobabilités, mise à jour des paramètres

→ PRISM, BLP



Apprentissage de structures

Principalement sur les modèles de Markov logiquesI Apprentissage génératif

MSL (Kok and Domingos, ICML’05), BUSL (Mihalkova and Domingos,ICML’07), ILS (Biba et al. ECML’08), LHL (Kok and Domingos ICML’09),LSM (Kok and Domingos ICML’10),MBN (Khosravi et al. AAAI ’10), HGSM(Dinh et al. STAIRS ’10), . . .

I Apprentissage discriminatifILS-DSL (Biba & al. ), DMSP (Dinh & al. 2010), (Dinh & al. 2011)

Difficile sur les réseaux bayésiens : conditions d’acyclicité àvérifier

I Relational dependency networks (Neville & al 2007) : probabilitéjointe approchée par un produit de distributions conditionnelles surles atomes

I Gradient Based boosting : apprentissage d’arbres de régressionrelationnels.



Apprentissage de la structure

PropositionnalisationLHL (Learning via Hypergraph Lifting) [Kok & Domingos 2009]

LSM (Learning using Structural Motifs) [Kok & Domingos 2010]

MBN (Moralized Bayes Net) [Khosravi & al. 2009]I apprentissage d’un réseau bayésien paramètré (des atomes clos

dans un DAG)I transformation en un MLN



Hypergraphe lifté

Construction d’un hypergraphe lifté :

I nœud = constante, hyper-arête = ensemble des constantesapparaissant dans un même atome clos étiqueté par le prédicat

I regroupement des constantes de même type

Création de clauses à partir de ce graphe chemin = ensembled’hyper-arêtes telles que pour tout e0, en il existe une suite e0,e1,. . . en telles que ei et ei+1 partagent au moins un nœud.



Datasets

ImdbI Description de filmsI 316 constantes, 10 prédicats, 1540 atomes clos vraisI Exemple de prédicats : WorkUnder

Uw-cse :I Description d’un département académiqueI 1323 constantes,15 prédicats, 2673 atomes clos vraisI Exemple de prédicat : AdvisedBy

Cora :I Collections de citations de papiers en informatiqueI 3079 constantes, 10 prédicats, 70367 atoms clos vrais/fauxI Exemples de prédicats : SameAuthor, SameBib, SameAuthor,

SameVenue



Mesures CLL et AUC

CLLI Qualité des probabilité conditionnelles inférées pour chaque

prédicatI Moyenne sur l’ensemble des prédicats

AUC-PR : Aire sous la courbe précision/rappelI Un atome est considéré vrai si la probabilité qu’il le soit est

supérieure à un certain seuilI Mesure des couples précision / rappel pour différentes valeurs du

seuil→ courbe P/R→ aire sous la courbeI Plus adapté que courbe ROC quand déséquilibre vrai/faux


Travaux au LIFO

Deux approches [Q.T. Dinh, M. Exbrayat, C.Vrain]

Propositionnalisation : transformation d’un problèmed’apprentissage relationnel en un booléenSoit advBy le prédicat à apprendre.

Table booléenne : une colonne↔ un littéral avec variablesune ligne↔ un atome clos du prédicat à apprendre

Représentation synthétique de la base de données : graphe deprédicats


Travaux au LIFO Propositionnalisation

Schéma de la méthode



Propositionnalisation : recherche des liens entreatomes clos

A partir des chemins connectés

→

on construit l’ensembledes liens (DMSP)

Etape effectuée pour tous les littéraux clos du prédicatd’apprentissage.



Construction des littéraux

A partir des liens

→

on construit l’ensemble deslittéraux

Plus petit ensemble tel que pour chaque atome clos e du prédicat d’apprentissageQP, pour chaque chaîne g-chain(e), il existe au moins une variablilisation telle quevar(g-chain(e)) ⊆ SL.



Construction de la table booléenne


Travaux au LIFO Graphe des prédicats

Représentation synthétique : Graphe des PrédicatsUn graphe non-orienté G = (V ,E) de m prédicats p1, . . . ,pm :

Sommet (noeud) vi ∈ V ↔ prédicat/ négation de prédicatArête e(pi ,pj) ∈ E ↔ lien entre pi et pj .Label d’arête = link-label num-labelPondération des sommets

AdvisedBy

<0 0>23

<0 1>0

<1 0>0

<1 1>24

<0 0 | 1 0>0

<0 1 | 1 0>0

<0 1 | 1 1>0

!AdvisedBy

<0 0>26

<0 1>24

<1 0>26

<1 1>24

<0 0 | 1 0>8

<0 1 | 1 0>8

<0 1 | 1 1>8

<0 0>24

<0 1>24

<1 0>24

<1 1>23

<0 0 | 1 0>0

<0 1 | 1 0>8

<0 1 | 1 1>0

Professor!Professor

<0 0>8

<1 0>0

<0 0 | 1 0>0<0 0>5

<1 0>3

<0 0 | 1 0>4

<0 0>4

<1 0>2

<0 0 | 1 0>2

<0 0>6

<1 0>0

<0 0 | 1 0>1

Professor(Anna)

Professor(Bob)

AdvisedBy(Anna,Charles)

AdvisedBy(Anna,Diana)

AdvisedBy(Bob,Ella)

AdvisedBy(Bob,Francis)

...

!Professor.weight = (8+0+0+5+3+4)/6

= 3.33

somme (num-label) / | link-label |



Principe de l’Algorithme

Point de départ : un MLN donné en entréeI au minimum, le MLN unitaire (contenant tous les atomes)

Production d’une liste de clauses candidatesI Filtrage des clauses “intéressantes” (transparent suivant)I Tri par longueur croissante et gain décroissant

Ajout itératif de ces clauses dans le MLN solutionI Une clause est ajoutée si elle apporte un gainI Un élagage final est réalisé



Jeux de données

IMDB : base de filmsI Director(person), Actor(person), Movie(picture,person) ...

UW-CSE : département universitaireI Student(person), Professor(Person), AdvisedBy(person, person) ...

CORA : Citations d’articles scientifiquesI Title(class,nametitle), Author(class,nameauthor),

SameAuthor(nameauthor,nameauthor) ...

Jeu Type Constantes Prédicats Atomes vrais

IMDB 4 316 10 1540

UW-CSE 9 1323 15 2673

CORA 5 3079 10 70367



Systèmes Comparés

GSLPI Fondée sur les graphes de prédicats

LSM (Kok & Domingos, 2010)

I Le système comparable le plus performant à ce jourI Repose sur la recherche de motifs fréquents

HGSM (Stairs 2010)

I Repose sur l’utilisation de données statistiques (χ2 et couverturede Markov)



Résultats


Conclusion

Conclusion

Perspectives de nos travauxI Amélioration des performances : choix des clauses, lifted inferenceI Comparaison à d’autres méthodes génératives : Moralized

Bayesian Networks (Khosravi et al., 2010)I Application à des jeux de données plus structuréesI Relâcher l’hypothèse du monde clos

SRLI Choix des modèlesI Apprentissage des modèles dirigésI Inférence liftée :

tutorial à IJCAI 2011http ://www.biostat.wisc.edu/ natarasr/tutorials/lifted.htm

I Compréhensibilité


Conclusion

Merci pour votre attention !

13e conférence francophone sur l’Extraction et la Gestion desConnaissances EGC 2013

du 29 janvier - 01 février 2013, Toulouse, Francehttp ://www.irit.fr/EGC2013Président d’Honneur : Fionn Murtagh, University of LondonPrésidente du Comité d’Organisation : Florence Sèdes - IRITToulousePrésidente du Comité de Programme : Christel Vrain, LIFO,Université d’Orléans


Documents

Christel Vrain Christel.Vrain@univ-orleans · Apprentissage Statistique Relationnel Christel Vrain [email protected] LIFO Université d’Orléans Journées AAFD 12 Ch