Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Introduction aux CRF via l’annotation par des modèles graphiques Isabelle Telli

Introduction aux CRF via l’annotation par des modèles graphiques Isabelle Tellier LIFO, Université d’Orléans Plan 1. Annoter pour quoi faire 2. Apprendre avec un modèle graphique 3. Annnoter des chaînes avec un HMM 4. Les CRF et leur application aux chaînes 5. CRF sur les arbres 6. Conclusion 1. Annoter pour quoi faire Qu’est-ce qu’annoter ? – les données de départ peuvent être des textes ou des arbres ou... – texte = séquence d’items – arbre = structure hiérarchique d’items pris dans un vocabulaire ﬁni – annotation : l’association des données avec d’autres items pris dans un autre vocabulaire ﬁni – ici : les données et les annotation auront la même structure mais ce n’est pas obligatoire 1. Annoter pour quoi faire Exemples d’annotations sur des textes – étiquetage POS (“part of speech”) : item = “mot”, annotation = catégorie syntaxique (Det, Nom, etc.) dans le texte – reconnaissance des entités nommées, EI : item = “mot”, annotation = position de l’EN (B : “Begin”, I : “In”, O : “Out”) En 2008 les Jeux Olympiques ont eu lieu à Pékin O B O B I O O O O B – segmentation d’un texte en “chunks”, en “syntagmes”... – alignement de phrases : item = “mot”, annotation = le(s) mot(s) correspondant(s) dans une autre phrase (par exemple pour la traduction automatique) – annotation de phrases : item = “phrase”, annotation = “classe”... 1. Annoter pour quoi faire Exemples d’annotations sur des arbres – étiquetage fonctionnel d’arbres syntaxiques SENT NP SUJ Sligos VN PRED va VP OBJ VN PRED prendre NP OBJ pied PP MOD au NP Royaume-Uni . – étiquetage en rôles thématiques/sémantiques d’arbres syntaxiques : idem mais avec annotation agent, patient, etc. – extraction d’information sur le Web ou les documents XML 1. Annoter pour quoi faire Exemples d’annotations sur des arbres (suite) – transformation d’un arbre en un autre HTML BODY . . . DIV TABLE TR TD #text TD DIV #text A #text @href SPAN #text DIV . . . #text . . . Channel DelN DelST item DelN DelN DelST DelST DelN title 0 DelN DelN link description 0 DelST DelST DelN DelST – à gauche : un arbre HTML – à droite : une annotation avec des opérations d’édition – DelN, DelST : suppression de nœud/sous-arbre – channel, item, title, link, description : renommage de nœuds 1. Annoter pour quoi faire Exemples d’annotations sur des arbres (suite) – exécution des opérations d’édition HTML BODY . . . DIV TABLE TR TD #text TD DIV #text A #text @href SPAN #text DIV . . . #text . . . Channel item title link description – application implémentée : génération de ﬂux RSS à partir de pages HTML – passage d’une DTD à une autre 1. Annoter pour quoi faire Synthèse – de nombreuses tâches peuvent se formuler comme des tâches d’annotation – chaque tâche requiert de spéciﬁer : – la nature des items – les relations entre items : séquence, ordres dans un arbre... – la nature des annotations et leur interprétation – les relations entre annotations – les relations entre les items et leur annotation – pré-traitements et post-traitements souvent nécessaires Plan 1. Annoter pour quoi faire 2. Apprendre avec un modèle graphique 3. Annnoter des chaînes avec les HMM 4. Les CRF et leur application aux chaînes 5. CRF sur les arbres 6. Conclusion 2. Apprendre avec un modèle graphique Apprendre à annoter : pourquoi ? – ne requiert pas de ressources externes (dictionnaires, listes) – requiert (en principe) moins de travail – requiert (en principe) moins de compétences en programmation – le même programme s’adapte aux données, à la langue... – en étant plus robuste aux données bruitées A condition... – de disposer d’exemples annotés du domaine 2. Apprendre avec un modèle graphique Notations de base – notations classiques : x est une donnée, y est une annotation – on supposera ici que x et y ont la même structure – ex. sur les séquences : x = un chat dort et y =Det Nom Vintr – ex. sur les arbres : x à gauche, y à droite SENT NP Sligos VN va VP VN prendre NP pied PP au NP Royaume-Uni . ⊥ SUJ ⊥ PRED ⊥ OBJ PRED ⊥ OBJ ⊥ MOD ⊥ ⊥ ⊥ ⊥ 2. Apprendre avec un modèle graphique Apprendre à annoter : protocole classique – on dispose d’un ensemble d’exemples annotés S = {(x, y)} – on sépare S en deux sous-ensembles : S = A ∪T avec – A : ensemble d’apprentissage – T : ensemble de test – avec A, on apprend un étiqueteur f, qui prédit f(x) = ˆ y – ∀(x, y) ∈T, on compare f(x) = ˆ y avec y avec des mesures – précision de l’étiquette E : pE = |y=E ET ˆ y=E| |ˆ y=E| – rappel de l’étiquette E : rE = |y=E ET ˆ y=E| |y=E| – F1-mesure : 2pr p+r – si S est trop limité ou s’il y a des risques de biais dans le découpage S = A ∪T : validation croisée 2. Apprendre avec un modèle graphique Apprentissage automatique statistique – on suppose qu’il existe une distribution de probabilité p(y|x) – la forme du modèle p est ﬁxée, à des paramètres près – les deux problèmes qui se posent : – apprentissage : ﬁxer les paramètres du modèle p à l’aide des couples (x, y) – annotation : une fois p ﬁxé, pour tout nouveau x, trouver l’annotation y la plus probable, c’est-à-dire ˆ y = argmaxy p(y|x) 2. Apprendre avec un modèle graphique Apprentissage automatique statistique – une variable aléatoire est une variable pouvant prendre plusieurs valeurs données (cf. le dé...) – on décompose x et y en des ensembles de variables aléatoires : X = {X1, X2, ..., Xn} et Y = {Y1, Y2, ...Yn} – ex : les x sont des séquences de mots, les y leur étiquetage POS : – X1 : variable dont les valeurs sont les 1ers mots des séquences x – Y1 : variable dont les valeurs sont les 1ères étiquettes POS des séquences y, etc. – intuition : il y a des dépendances entre les variables : – ex : si Xi = le, alors Yi =Det ou Yi =Pro – si en plus Yi+1 =Nom alors Yi =Det... 2. Apprendre avec un modèle graphique Modèles graphiques – un modèle graphique déﬁnit les dépendances entre variables aléatoires par un graphe – les variables aléatoires sont les nœuds du graphe – Z1 Z2 : la valeur de Z2 dépend de celle de Z1 – Z1 Z2 : dépendances mutuelles entre Z1 et Z2 – dans un modèle graphique génératif, il y a des dépendances dirigées Yi Xj – exemples de modèle graphique génératif : les HMM, les PCFG – dans ce cas, on utilise : p(y|x) = p(x,y) p(x) Plan 1. Annoter pour quoi faire 2. Apprendre avec un modèle graphique 3. Annnoter des chaînes avec les HMM 4. Les CRF et leur application aux chaînes 5. CRF sur les arbres 6. Conclusion 3. Annnoter des chaînes avec les HMM Un HMM Adj bonne : 1/2, grande : 1/2 Det Nom V intr la : 2/3 bonne : 1/3 fume : 4/5 une : 1/3 soupe : 2/3 soupe : 1/5 1/3 1/3 2/3 2/3 1 3. Annnoter des chaînes avec les HMM Un HMM et le graphe correspondant Adj bonne : 1/2, grande : 1/2 Det Nom V intr la : 2/3 bonne : 1/3 fume : 4/5 une : 1/3 soupe : 2/3 soupe : 1/5 1/3 1/3 2/3 2/3 1 Y1 Y2 Y3 Y4 Y5 ... X1 X2 X3 X4 X5 3. Annnoter des chaînes avec les HMM Adj bonne : 1/2, grande : 1/2 Det Nom V intr la : 2/3 bonne : 1/3 fume : 4/5 une : 1/3 soupe : 2/3 soupe : 1/5 1/3 1/3 2/3 2/3 1 p(x =la bonne soupe,y = Det Adj Nom) = p(Det :la)p(Det →Adj)p(Adj :bonne)p(Adj →Nom)p(Nom :soupe) p(x =la bonne soupe,y = Det Adj Nom) = 2/3∗1/3∗1/2∗2/3∗2/3 = 4/81 p(x =la bonne soupe,y = Det Nom V intr) = 2/3∗2/3∗1/3∗1∗1/5 = 4/135 p(x =la bonne soupe) = P y p(x, y) = 4/81 + 4/135 3. Annnoter des chaînes avec les HMM Hypothèses préliminaires – la structure du HMM est supposée connue (ou hypothèse que tous les états sont connectés) – des exemples annotés (x, y) sont disponibles Les deux problèmes classiques – apprentissage : trouver les paramètres, c’est-à-dire les probabilités d’émissions/de transitions à partir des (x, y) – annotation : utiliser le modèle p appris sur une nouvelle donnée x, c’est-à-dire trouver l’annotation ˆ y qui maximise p(y|x) = p(x,y) p(x) : ˆ y = argmaxy p(x, y) 3. Annnoter des chaînes avec les HMM Adj bonne :1/2, grande :1/2 Det Nom V intr la : 2/3 bonne : 1/3 fume : 4/5 une : 1/3 soupe : 2/3 soupe : 1/5 1/3 1/3 2/3 2/3 1 p(x =une bonne soupe,y = uploads/Ingenierie_Lourd/ introduction-aux-crf-via-l-x27-annotation-par-des-modeles-graphiques.pdf