Matwin 19991

La Classification des textes: à la recherche d’une représentation

Stan Matwin

École d’Ingénierie et de technologie de l’information

Université d’Ottawastan@site.uottawa.ca

Matwin 19992

Plan

Apprentissage supervisé (classification)Apprentissage automatique et fouille de

données (AA/FD) à l’ UOL’approche classiqueEssais de représentation linguistiqueLes N-grammes: comment les obtenir?Étiquetage et co-apprentissageRecherches futures

Matwin 19993

Apprentissage supervisé (classification)

étant donnés:un ensemble d’exemples T={et}, où chaque t

est l’étiquette d’une classe parmi C1,…Ck

un concept contenant k classes C1,…Ck (mais la définition du concept est inconnue)

Trouver: une description de chaque classe permettant

une bonne prédiction de la classe de nouveaux exemples

Matwin 19994

Classification

Approche habituelle:

les exemples sont représentés sous forme de vecteurs de valeurs d’attributs

La théorie est confirmée par l’expérience: plus il y a d’exemples, plus précise est la prédiction

Matwin 19995

L’AA/FD à l’UO

apprentissage à partir de classes déséquilibrées (imbalanced): application à la télédétection

une représentation relationnelle plutôt que propositionnelle: apprentissage du concept de maintenabilité d’un logiciel

apprentissage avec des connaissances du domaine. Les réseaux bayesiens et comment les obtenir. Application aux bases de données distribuées.

Matwin 19996

Á quoi sert la classification de textes?

Archivage automatiqueFiltrage de l’InternetSystèmes de recommandationExtraction d’information…

Matwin 19997

Bag of words

Classification de textes: approche habituelle

1. Enlever les mots-arrêt (stop words) et les marqueurs non-textuels

2. les mots restants sont tous pris comme des attributs

3. un document devient un vecteur <mot, fréquence>

4. Entraîner un classifieur booléen pour chaque classe

5. Évaluer les résultats sur un nouvel échantillon

Matwin 19998

Outils de classification des textes

RIPPERun système d’apprentissage ascendant

(covering)Fonctionne bien sur de gros ensembles

de traits binairesRéseaux bayesiens naïfs

Efficaces (pas de recherche)Simples à programmerIndiquent un “niveau de croyance”

Matwin 19999

Autres travaux

Yang: les meilleurs résultats obtenus avec k-NN: 82,3% de précision en micro-moyenne

Joachim: Support Vector Machine (SVM) + données non étiquetées

SVM n’est pas affectée par une forte dimensionnalité ni par la rareté des exemples.

Matwin 199910

SVM en classification de textes

SVM

SVM transductive Séparation maximale Marge pour le jeu de test

L’entraînement sur 17 exemples dans les 10 catégories les plus fréquentes donne une performance de 60% sur 3000+ cas de test disponibles pendant l’entraînement.

Matwin 199911

Problème 1: sélection de traits très sélective

“Machine”: 50%“Learning”: 75%“Machine Learning”: 50%

AI

“Machine”: 4%“Learning”: 75%“Machine Learning”: 0%

EP

“Machine”: 80%“Learning”: 5%“Machine Learning”: 0%

MT

RIPPER (BW: mots en vrac): machine & learning = AI �

FLIPPER (Cohen): machine & learning & near & after = AI �

RIPPER (expressions): “machine learning” = AI �

Matwin 199912

Problème 2: certaines relations sémantiques sont ignorées

couteau pistolet

poignard épée

carabine fronde

arme� Des mots reliés sémantiquement

peuvent être dispersés dans de nombreux documents.

� Un classifieur statistique peut parvernir à détecter ces corrélations.

� Les classifieurs à règles sont désavantagés.

Matwin 199913

Solution proposée (Sam Scott)

Extraire les groupes nominaux et/ou les expression-clefs (Extractor) et les ajouter à la liste de traits

Ajouter les hypernymes

Matwin 199914

Hypernymes dans WordNet

“synset” => SYNONYME“is a” => HYPERNYME“instance of” => HYPONYME

“is a”

“instance of”

“Synset”

arme

arme à feu

pistolet,fusil

couteau

Matwin 199915

Évaluation (Lewis)

•Changer le paramètre de “taux de perte” (loss ratio)

• Pour chaque valeur du paramètre,

• Apprendre une hypothèse pour chaque classe (classification binaire)

• Micro-moyenne des matrices de confusion (ajout pour chaque composant)

• Calculer la précision et la couverture

• Interpoler (ou extrapoler) pour trouver le point où la micro-moyenne de la précision et celle de la couverture sont égales.

Matwin 199916

Résultats

Les représentations alternatives ne sont pas notablement meilleures que les mots en vrac (bag of words:BW)

mais…

la compréhensibilité…

Micromoyenne b.e.

Reuters DigiTradBW .821 .359BWS .810 .360NP .827 .357NPS .819 .356KP .817 .288e

KPS .816 .297e

H0 .741e .283H1 .734e .281NPW .823 N/A

Matwin 199917

Combination des classifieurs

Comparable aux meilleurs résultats possibles (Yang)

Reuters DigiTrad# représentations b.e. représentations b.e.1 NP .827 BWS .3603 BW, NP, NPS .845 BW, BWS, NP .404e

5 BW, NP, NPS, KP, KPS .849 BW, BWS, NP, KPS, KP .422e

Matwin 199918

Autres possibilités

Utilisation d’hypernymes avec un jeu d’apprentissage réduit (évite les mots ambigus)

Utilisation de Bayes+RIPPER, en cascade (Gama)

Autres représentations

Matwin 199919

Co-occurrences

Pas nécessairement des groupes nominaux: simplement des paires de mots, éventuellement séparés par des mots-arrêt (stop words)

Seuls les plus discriminants sont retenus

Ils sont mis dans l’ensemble non structuré (bag of words) et transmis à…

RIPPER

Matwin 199920

N-grammes

Les n-grammes sont des sous-chaînes d’une longueur donnée

Bons résultats sur Reuters [Mladenic, Grobelnik]

avec Bayes. Nous testons RIPPER.

Une tâche différente: la classification de fichiersattachés au texte principal

audio/vidéo

encodés

Des n-grammes aux traits relationnels

Matwin 199921

Comment obtenir de bons n-grammes?

Nous utilisons Ziv-Lempel pour la détection de sous-chaînes fréquentes (.gz!)

abababaa ba a

b

b

a

Matwin 199922

N-grammes

Comptage élimination:

si la fréquence d’une sous-chaîne < seuilConstruction de relations: la chaîne A

précède presque toujours la chaîne BTransmission à un système d’apprentissage

relationnel (FOIL)

Matwin 199923

Utilisation de l’induction grammaticale (fichiers texte)

L’idée est de détecter des formes (patterns) de sous-chaînes

Les formes correspondent à des langages réguliers

Méthodes de déduction d’automates: un automate de reconnaissance pour chaque classe de fichiers

Nous utilisons une version modifiée de RPNI2 [Dupont, Miclet]

Matwin 199924

Nouveautés

Travail sur le texte marqué (Word, Web)

XML avec des marqueurs sémantiques: avantages et inconvénients pour l’AA/FD

Co-apprentissageFouille de textes

Matwin 199925

Co-apprentissage

Comment utiliser les données non étiquetées? Ou comment limiter le nombre d’exemples à étiqueter?

Deux classifieurs et deux représentations “redondantes et suffisantes” (redundantly sufficient)

entraîner les deux, appliquer les deux sur le jeu de test,

ajouter les meilleures prédictions au jeu d’apprentissage.

Matwin 199926

Co-apprentissage

Le jeu d’entraînement s’accroît car ……chaque classifieur fait ses prédictions

indépendemment, à cause de la “suffisance redondante”) (représentations différentes)

Est-ce que cela marcherait avec nos classifieurs en utilisant Bayes?

Marcherait pour la classification du courrier électronique

Matwin 199927

Co-apprentissage

Mitchell a fait des expériences sur la classification des pages Web (profs, étudiants, cours, projets). C’est une tâche d’apprentissage supervisé.

Il utiliseles segments de texte associés aux liens

(anchor text)le contenu des pages

Le taux d’erreur est diminué de moitié (il passe de 11% à 5%).

Matwin 199928

Sciences cognitives?

Le co-apprentissage semble être justifié cognitivement

Modèle: apprentissage d’étudiants par groupes de deux

Quels autres mécanismes d’apprentissage pourraient fournir des modèles de l’apprentissage supervisé?

Matwin 199929

Conclusion

Une tâche pratique pour laquelle il faut trouver une solution

Aucune solution satisfaisante pour l’instant

Un domaine de recherche fertile