Teaching - TAL

Page principale de l'UE


Traitement Automatique de la Langue

Le but de ce TME est d'étudier les méthodes d'analyse sémantique, c'est à dire:

  • répartir un corpus documentaire en plusieurs thématiques \approx comprendre le sens des documents
  • définir une distance entre les mots (trouver des synonymes ou isoler des champs lexicaux homogènes)

Le plan du TME est le suivant:

  1. Traitement d'un corpus textuel
    1. Chargement d'un corpus
    2. Pré-processing
    3. Construction d'un dictionnaire
    4. Calcul de la matrice des sacs de mots
  2. Algorithmiques
    1. k-means, PLSA, LDA
    2. Evaluation, introspection, mots clés...

Pour chaque étape, nous allons envisager une procédure manuelle et une procédure basée sur des outils de plus haut niveau

Traitement d'un corpus textuel

Chargement d'un corpus

Les corpus sont principalement fournis sous 3 formes distinctes: (a) un fichier contenant les textes dans un format spécifique, (b) un fichier XML, (c) une arborescence de répertoires contenant des fichiers textes.

La page suivante indique les procédure de chargement des principaux corpus utilisés dans le cadre de l'UE: lien

Dans le cadre du TME, nous allons travailler sur la base 20 newsgroups: c'est idéal pour de la catégorisation. Nous savons que la base est composée de 20 thématiques (plus ou moins proches), et nous allons voir ce que nous retrouvons ou pas. De plus, la base est étiquetée: nous aurons donc des possibilités d'évaluation quantitative.

Pre-processing

Le but de cette étape: éliminer du bruit dans les donnée. Par exemple:

  • éliminer des entêtes de fichier,
  • passer en minuscules,
  • remplacer les URL par un tag générique
  • ...

Détails sur les outils à maitriser, application sur un exemple jouet, passage au traitement du corpus entier : lien

Exercice

Au lieu de chercher le double saut de ligne pour délimiter les entêtes (méthode très peu fiable!!!), chercher toutes les lignes commençant par

  1MOT: ...

pour les supprimer.

Vérifier le résultat sur le corpus.

Construction d'un dictionnaire

1) Il faut répondre à la question suivante: Quels sont les mots (uniques) présents dans le corpus?

2) La question subsidiaire est: est-il possible de compter les termes?. Encore mieux, peut-on extraire la fréquence documentaire? (C'est à dire le pourcentage de documents dans lequel apparait chaque terme).

3) Enfin, une fois les termes comptés, comment filtrer éléments intéressant et ce qui risquent simplement de polluer les résultats?

4) Passer tout le processus aux n-grams de mots.

Tous les détails : lien

Exercice

Tracer les histogrammes d'apparition des mots (loi de Zipf) dans le cas des unigrammes et des bigrammes.

Afficher les mots les plus fréquents et les moins fréquents du dictionnaire.

Combien reste-t-il de trigrammes si on ne garde que les entrées du dictionnaire apparaissant dans au moins 5 documents? Sont-ils significatifs?

Projection du corpus sur le dictionnaire = BoW (sacs de mots)

Il est maintenant temps de retourner sur des matrices de nombres pour pouvoir se focaliser sur l'algorithmique.

Attention: 10000 documents avec un vocabulaire de 20000 mots = 2.\ 10^8 cases de 8 octets (64 bits) = 1.6 Go!!! Il est impératif de travailler sur des structures sparses (sans coder les 0).

Tous les détails : lien

Exercice

Transformer la matrice de sacs de mots pour passer en mode:

  • tf (chaque ligne somme à 1)
  • tf-idf multiplication par: \log(1/freqDoc)

Dans tous les cas, isoler le couple de mots le plus similaire parmi les 200 premiers mots du dictionnaire.

Algorithmique

Algorithme des k-means

1. Tirer aléatoirement k documents (nos k prototypes initiaux)

import numpy as np
import numpy.random as rand

# tirage de k prototypes
prototypes = bow[rand.permutation(N)[:k]].toarray() # conversion en array (dimension acceptable)

2. Trouver pour chaque document le prototype le plus proche

    sim = bow.dot(prototypes.T) # métrique type cos si les vecteurs sont normalisés
    y= sim.argmax(1) # comprendre les dimensions des matrices pour comprendre ce calcul

3. Calculer les nouveaux prototypes

for i in range(k):
    index = np.where(y==i)[0]
    prototypes[i] = np.sum(bow[index,:],0)
prototypes/=prototypes.sum(1).reshape(k,1) # normalisation

4. Retour en 2.

Il faut ensuite:

  • trouver un critère d'arrêt
  • inspecter les modèles pour comprendre la signification des prototypes

Exercice

Modifier l'initialisation pour avoir des prototypes orthogonaux (ou proches de l'orthogonalité) pour garantir la diversité des paquets obtenus.

Analyses quantitative et qualitative

Du point de vue quantitatif, l'analyse d'un clustering n'est pas évidente, du fait de l'absence de vérité terrain (la plupart du temps). Dans le cas de 20newsgroups, les étiquettes existent et il est possible d'analyser les résultats, par exemple en terme de pureté:

  • les identifiants de clusters ne correspondent pas aux classes,
  • mais dans chaque cluster, on peut identifier la classe majoritaire,
  • puis calculer quel pourcentage de documents appartient à cette classe majoritaire: c'est la pureté du cluster.
  • Il est ensuite possible d'étendre la métrique à l'ensemble du corpus en pondérant les puretés des clusters par leur taille (on calcule en réalité une espérance sur la pureté).

Il est aussi possible d'analyser la séparation des données en calculant pour chaque prototype la distance moyenne des documents au barycentre puis la distance entre barycentre.

Du point de la qualitatif, l'idée est de comprendre ce qu'il y a dans les clusters: il faut donc analyser le contenu des protoypes:

  • quels mots sont les plus fréquents dans le cluster,
  • quels mots sont les plus représentatifs (fréquents dans ce cluster mais pas dans les autres)...