TP++ - Représentations vectorielles avec pondérations TF-IDF. Analyse Sémantique Latente

(les TP++ sont des compléments à l’enseignement de base et ne font pas partie des séances de travaux pratiques avec encadrement)

Références externes utiles :

Introduction

L’objectif de cette séance de TP est d’apprendre à examiner, avec Spark, le contenu d’une base de textes d’assez grande taille, en utilisant l’analyse sémantique latente (LSA - Latent Semantic Analysis). Le but premier est d’explorer les données en déterminant quels sont les « concepts » (ou classes sémantiques) qui expliquent le mieux les données. Nous extrairons aussi les documents représentatifs et ferons des requêtes qui permettent de trouver les documents de la base qui mentionnent certains termes ou qui sont similaires à un document requête.

LSA vise à mieux représenter un corpus de documents en explorant les relations entre les mots dans les documents. Le but est de « distiller » à partir du corpus un ensemble de « concepts » pertinents. Chaque concept saisit une direction de variation dans les données, qui souvent correspond à un sujet abordé dans le corpus. En grandes lignes, chaque concept est décrit par trois caractéristiques : la pertinence du concept pour chaque document du corpus, l’affinité par rapport aux termes présents dans le corpus et l’utilité du concept dans la description de la variance des données. En sélectionnant seulement les concepts les plus importants, LSA peut décrire les données avec une représentation approximative qui emploie moins de concepts, qui élimine du « bruit » et fusionne des sujets similaires.

LSA découvre cette représentation en utilisant la décomposition en valeurs singulières (Singular Value Decomposition, SVD). SVD factorise la matrice TF-IDF (Term Frequency - Inverse Document Frequency) du corpus en trois matrices : une qui exprime l’importance des concepts par rapport aux autres documents, une qui exprime les concepts par rapport aux termes (mots) importants, et une troisième qui donne l’importance de chaque concept. La structure de ces matrices est telle qu’une approximation de rang plus faible de la matrice d’origine peut être obtenue par élimination des concepts les moins importants.

Dans le cadre de ce TP nous utiliserons une partie de la base de donnée Wikimedia (https://dumps.wikimedia.org). La base complète est d’env. 57 Go, pour des raisons de ressources disponibles nous travaillerons sur un échantillon de 200 Mo (approximativement 6000 pages).

Une suite utile de ce TP est la classification automatique de tweets avec des représentations Word2Vec, qui ne sera pas abordée dans les séances de travaux pratiques mais que vous pouvez suivre ou dont vous pouvez vous inspirer pour votre projet.

Création de l’environnement de travail

Exécutez les commandes suivantes pour créer l’environnement nécessaire (cela récupère une archive de texte de la Wikipedia anglophone).

Note

Sous Windows, il faudra créer un répertoire tptexte avec un sous-répertoire data dans votre dossier de travail (par exemple, le dossier d’installation de Zeppelin). Téléchargez puis décompressez l’archive enwiki.xml.bz2 (par exemple, avec 7-zip) dans le sous-répertoire data.

%%bash
mkdir -p tptexte/data
cd tptexte/data
wget -nc http://cedric.cnam.fr/~ferecatu/RCP216/tp/tptexte/enwiki.xml.bz2
bzip2 -d enwiki.xml.bz2
cd ..

La dernière commande vous positionne dans le répertoire tptexte, il faudra y rester pour entrer les commandes du bloc suivant.

Il est nécessaire maintenant de construire un .jar qui inclut les librairies externes employées avec toutes leurs dépendences. Cela exige normalement d’installer et lancer l’outil Maven, et peut prendre jusqu’à 30 minutes. Afin de vous faire gagner ce temps, nous avons déjà préparé le .jar qui sera téléchargé. Pour cela, entrez les commandes suivantes dans la fenêtre terminal :

Note

Sous Windows, téléchargez les fichiers lsa.jar et deps.zip et décompressez ce dernier (dans le répertoire tptexte).

%%bash
cd tptexte
wget -nc http://cedric.cnam.fr/~ferecatu/RCP216/tp/tptexte/lsa.jar
wget -nc http://cedric.cnam.fr/~ferecatu/RCP216/tp/tptexte/deps.zip
unzip deps.zip

Note

Si le .jar n’avait pas été déjà disponible, il aurait été nécessaire de le créer, en installant d’abord Maven avec mvn package dans le dossiers deps (n’exécutez pas cette commande si vous avez récupéré déjà le .jar).

On lance spark-shell dans ~/tptexte, avec un peu plus de mémoire à sa disposition (1 Go) et en ajoutant le fichier .jar avec les bonnes librairies et dépendances dans le chemin d’accès de Spark :

$ spark-shell --driver-memory 1g --jars lsa.jar

Dans Spark, on commence par importer les paquetages nécessaires.

Note

Il est possible de copier et coller dans spark-shell des instructions multi-lignes (comme le dernier import ci-dessous) en entrant d’abord :paste (Ctrl+D pour quitter).

import com.cloudera.datascience.lsa._
import com.cloudera.datascience.lsa.ParseWikipedia._
import com.cloudera.datascience.lsa.RunLSA._
import org.apache.spark.mllib.linalg._
import org.apache.spark.mllib.linalg.distributed.RowMatrix
import breeze.linalg.{DenseMatrix => BDenseMatrix,
              DenseVector => BDenseVector, SparseVector => BSparseVector}

Le TP utilise le projet Cloud9 pour lire la base de données Wikimedia en format XML et extraire les parties qui nous intéressent : les titres et les corps de texte. Nous utilisons aussi le projet Stanford Core NLP pour effectuer les traitements linguistiques necessaires (segmentation, étiquetage, lemmatisation).

Par la suite, à chaque fois que vous rencontrez un appel de méthode préfixée par les objets ParseWikipedia et RunLSA vous devez regarder l’implémentation correspondante dans les sources en scala : fichiers ParseWikipedia.scala et RunLSA.scala du répertoire tptexte/deps/lsa/src/main/scala/com/cloudera/datascience/lsa/. Vous les trouverez dans l’archive à cette adresse: http://cedric.cnam.fr/~ferecatu/RCP216/tp/tptexte/deps.zip (il s’agit de l’archive deps.zip téléchargée tout à l’heure).

Remarque générale :

Après avoir entré une commande (suivant le cas, soit dans la fenêtre terminal, soit dans Zeppelin ou spark-shell) regardez attentivement la réponse que vous obtenez. Si cette réponse indique une anomalie (par ex. suite à une faute de frappe), essayez de corriger cette anomalie avant d’aller plus loin. Il est inutile d’entrer les commandes suivantes sans avoir corrigé l’anomalie.

Chargement de la base de données

Nous construisons un RDD à partir des données situées sur le système de fichiers local. Nous allons charger en mémoire l’extrait de Wikipédia anglais contenu dans le fichier XML enwiki.xml (téléchargé précédemment). Ce fichier contient une collection d’articles représentés sous une forme structurée en XML.

val wikixmlfile = "tptexte/data/enwiki.xml"
val sampleSize = 0.3
val xmlPages = ParseWikipedia.readFile(wikixmlfile, sc).sample(false, sampleSize, 11L)
xmlPages.take(2)

Ceci produit un RDD contenant des documents au format XML. Nous allons convertir ces articles au format texte brut en utilisant la fonction wikiXmlToPlainText du module ParseWikipedia :

val plainText = xmlPages.filter(_ != null).flatMap(ParseWikipedia.wikiXmlToPlainText)
plainText.take(2)

Si vous voulez obtenir un échantillon différent à chaque fois que vous exécutez les commandes, enlevez le paramètre 11L (seed). Inspectez les types de données des valeurs xmlPages et plainText. Regardez le fichier source enwiki.xml et essayez de comprendre la chaîne de traitement (regardez aussi les sources en scala, comme demandé précédemment).

Lemmatisation

Chaque élément de plainText est une paire de chaînes de caractères (type string) : la première chaîne est le titre d’une page Wikimedia, la seconde chaîne est le contenu textuel de cette page. Pour chaque page il faut découper le texte en mots, mettre les mots dans leur forme canonique (lemmatisation) et ensuite éliminer les stop words.

Par exemple, l’adjectif petit est la lemmatisation de 4 formes dites fléchies : petit, petite, petits et petites. Les mots vides (stop words) sont des mots non significants et très communs, généralement des articles et des pronoms (la, le, un, du, etc.). La forme canonique dépend du rôle morphologique et syntaxique du mot. Il faut donc aussi appliquer un étiqueteur grammatical (tagger) sur le texte du contenu. On réalise cette chaîne de traitement en nous servant des outils Java issus du projet Stanford NLP, comme suit (rappelons qu’il est possible de copier et coller dans spark-shell des instructions multi-lignes en entrant d’abord :paste) :

val stopWords = sc.broadcast(ParseWikipedia
                         .loadStopWords("tptexte/deps/lsa/src/main/resources/stopwords.txt")).value
val lemmatized = plainText.mapPartitions(iter => {
           val pipeline = ParseWikipedia.createNLPPipeline();
           iter.map{ case(title, contents) =>
                         (title, ParseWikipedia.plainTextToLemmas(contents, stopWords, pipeline))};
       }).cache()

lemmatized.take(2)
val filtered = lemmatized.filter(_._2.size > 1)

Question :

Quel est le rôle de la dernière commande ?

Spark propose aussi un tokenizer et un outil de suppression des stop words (ainsi qu’un outil de calcul des représentations TF-IDF). En revanche, Spark ne propose pas la lemmatisation, ni l’étiquetage (tagging) préalable. En conséquence, en appliquant directement les outils proposés par Spark (tokenizer suivi de suppression des stop words), les formes fléchies d’un même lemme sont traitées comme des mots (termes) distincts. Cela est nocif pour les modèles construits sur ces représentations car leur dimension est inutilement élevée (chaque forme fléchie d’un mot est comptée comme mot distinct) et deux formes différentes d’un même mot qui apparaissent dans deux documents ne permettent pas de faire le lien entre ces documents. En revanche, le calcul des pondérations TF-IDF est plus efficace avec l’outil Spark qu’avec celui de ParseWikipedia employé dans la suite.

Nous pouvons voir quelques exemples de titres d’articles de notre corpus en créant un RDD qui ne contient que la première colonne et en tirer 10 lignes au hasard :

val titres = lemmatized.map(_._1)
titres.takeSample(false, 10)

Calcul de la matrice TF-IDF

Maintenant nous sommes prêts à calculer la matrice TF-IDF de la base de données. Pour chaque document nous obtenons la représentation TF-IDF mais pour alléger les calculs nous gardons seulement un nombre de numTerms termes (mots, ou plutôt lemmes), les plus fréquents dans les documents (cela peut toutefois réduire les capacités discriminantes des représentations ainsi obtenues).

val numTerms = 1000 // nombre de termes à garder (les plus fréquents)
val (termDocMatrix, termIds, docIds, idfs) = ParseWikipedia.termDocumentMatrix(filtered, stopWords, numTerms, sc)

Quelle est l’expression exacte de la pondération TF-IDF calculée ? Regardez les sources en scala.

Nous utiliserons beaucoup cette matrice par la suite et demandons donc à Spark de la garder en mémoire :

termDocMatrix.cache()

Analyse sémantique latente (LSA) et inspection des résultats

Il est utile de revoir la présentation de LSA dans le cours.

Nous appliquons une decomposition en valeurs singulières (SVD) de la matrice \(\mathbf{M}\) des représentations vectorielles TF-IDF. MLlib contient une implémentation de SVD qui garde les \(k\) plus grandes valeurs singulières et qui produit trois matrices \(\mathbf{U}\), \(\mathbf{S}\) et \(\mathbf{V}\) telles que \(\mathbf{M} \approx \mathbf{U}_k \cdot \mathbf{S}_k \cdot \mathbf{V}_k^T\). Si la matrice \(\mathbf{M}\) est de taille \(m \times n\) (\(m\) documents, \(n\) termes), alors :

  • \(\mathbf{U}_k\) est une matrice \(m \times k\) : ses colonnes forment une base orthonormale dans l’espace de dimension \(m\) ; l’élément \(u_{ij}\) de \(\mathbf{U}_k\) indique « l’importance » du concept \(j\) pour le document \(i\) ;

  • \(\mathbf{S}_k\) est une matrice diagonale \(k \times k\) : les éléments sur la diagonale principale représentent l’importance de chaque concept extrait (son « pouvoir à expliquer les données ») ;

  • \(\mathbf{V}_k\) est une matrice \(n \times k\) : ses colonnes forment une base orthonormale dans l’espace de dimension \(n\) ; l’élément \(v_{ij}\) de \(\mathbf{V}_k\) indique « l’implication » du mot (terme) \(i\) dans le concept \(j\).

La décomposition est paramétrée par \(k\), le nombre de concepts à garder. Si \(k = n\) alors la décomposition est exacte (on retrouve la matrice \(\mathbf{M}\) sans approximations). Normalement \(k \ll n\) et \(\mathbf{U}_k \mathbf{S}_k \mathbf{V}_k^T\) est une approximation de \(\mathbf{M}\) qui est optimale par rapport à la norme L2 (perte quadratique minimale).

val mat = new RowMatrix(termDocMatrix)
val k = 200 // nombre de valeurs singulières à garder
val svd = mat.computeSVD(k, computeU = true)

En utilisant cette décomposition, nous pouvons afficher les concepts importants à travers les termes qui les caractérisent et les documents dans lesquels ils se manifestent le plus :

val topConceptTerms = RunLSA.topTermsInTopConcepts(svd, 10, 10, termIds)
val topConceptDocs = RunLSA.topDocsInTopConcepts(svd, 10, 10, docIds)
for ((terms, docs) <- topConceptTerms.zip(topConceptDocs)) {
          println("Concept terms: " + terms.map(_._1).mkString(", "));
          println("Concept docs: " + docs.map(_._1).mkString(", "));
          println();
       }

Regardez l’implémentation des methodes RunLSA.topTermsInTopConcepts et RunLSA.topDocsInTopConcepts.

Question :

Faites varier le paramètre k : 100, 400. Comparez les concepts trouvés dans ces différents cas.

Question :

Faites varier numTerms : 500, 2000.

Optionnel : faites varier sampleSize : 0.5, 0.6 (attention, les calculs peuvent prendre beaucoup plus de temps).

Que constatez-vous ? Expliquez.

Recherches par rapport à un (groupe de) mot(s) ou à un document

Cette section du TP est optionnelle.

La decomposition précedente permet aussi de faire des recherches dans la base de données, en prenant comme requête un mot, un groupe de mots ou un document.

Trouver des termes similaires à un mot/terme

Dans la matrice \(\mathbf{M}\) des représentations vectorielles TF-IDF, un vecteur colonne correspond à un terme (mot), chaque composante de ce vecteur exprimant son poids TF-IDF par rapport au document correspondant. De ce fait, le cosinus entre deux vecteurs colonnes correspond à une similarité entre les deux mots, similarité induite par les fréquences d’apparition des mots et leurs cooccurrences dans les documents. Passer par la SVD à une matrice de rang réduit, comme expliqué plus haut, entraîne une perte d’information mais a aussi des avantages : prise en compte de la synonymie (par « condensation » des termes reliés) et, dans une certaine mesure, de la polysémie (en plaçant moins de poids sur les mots qui ont plusieurs sens), ainsi que l’élimination du « bruit ».

Cependant, il n’est pas nécessaire de calculer complètement la matrice de rang réduit pour évaluer la similarité cosinus entre des termes. En effet, on peut démontrer que la similarité cosinus entre deux colonnes de la matrice de rang réduit \(\mathbf{U}_k \mathbf{S}_k \mathbf{V}_k^T\) est strictement égale à la similarité cosinus entre les colonnes correspondantes de \(\mathbf{S}_k \mathbf{V}_k^T\).

Considérons la tâche de trouver l’ensemble des termes les plus similaires à un terme particulier. Trouver la similarité cosinus entre un terme et tous les autres termes équivaut à normaliser chaque ligne de \(\mathbf{V}_k \mathbf{S}_k\) à norme 1 et ensuite multiplier la ligne correspondant à ce terme par toutes les autres lignes de \(\mathbf{V}_k \mathbf{S}_k\) (les lignes de \(\mathbf{V}_k \mathbf{S}_k\) sont les colonnes de la matrice transposée, \(\mathbf{S}_k \mathbf{V}_k^T\)). Chaque élément du vecteur résultant contiendra la similarité entre le terme requête et le terme correspondant.

val VS = RunLSA.multiplyByDiagonalMatrix(svd.V, svd.s)
val normalizedVS = RunLSA.rowsNormalized(VS)
var idTerms = collection.mutable.Map[String,Int]()
for(pair <- termIds) idTerms(pair._2) = pair._1

RunLSA.printTopTermsForTerm(normalizedVS, "problem", idTerms, termIds)
RunLSA.printTopTermsForTerm(normalizedVS, "mother", idTerms, termIds)
RunLSA.printTopTermsForTerm(normalizedVS, "africa", idTerms, termIds)

Trouver des documents similaires à un mot/terme

Calculer la similarité entre un terme et un document revient à choisir la ligne \(\mathbf{u}\) correspondant au document dans la matrice \(\mathbf{U}_k\), la ligne \(\mathbf{v}\) correspondant au terme dans la matrice \(\mathbf{V}_k\), et ensuite calculer le produit \(\mathbf{u} \mathbf{S}_k \mathbf{v}^T\). Pour déterminer la similarité d’un terme à chacun des documents on calcule donc \(\mathbf{U}_k \mathbf{S}_k \mathbf{v}^T\). Dans l’autre sens, on peut déterminer les similarités entre un document \(\mathbf{u}\) et tous les termes par le produit \(\mathbf{u} \mathbf{S}_k \mathbf{V}_k^T\).

val US = RunLSA.multiplyByDiagonalMatrix(svd.U, svd.s)
RunLSA.printTopDocsForTerm(US, svd.V, "problem", idTerms, docIds)
RunLSA.printTopDocsForTerm(US, svd.V, "mother", idTerms, docIds)
RunLSA.printTopDocsForTerm(US, svd.V, "africa", idTerms, docIds)

Trouver des documents similaires à un autre document

La matrice \(\mathbf{U}_k\) décrit chaque document par les \(k\) concepts trouvés par la SVD. Pour trouver des documents similaires à un autre document, on pondère chaque colonne de la matrice \(\mathbf{U}_k\) par les valeurs singulières correspondantes (trouvées sur la diagonale de la matrice \(\mathbf{S}_k\)) en faisant le produit \(\mathbf{U}_k \mathbf{S}_k\). Ensuite, on normalise chaque ligne du résultat à une norme de 1 et on calcule la similarité entre deux documents comme le cosinus des deux lignes correspondantes de la matrice normalisée.

val normalizedUS = RunLSA.rowsNormalized(US)
var idDocs = collection.mutable.Map[String,Long]()
for(pair <- docIds) idDocs(pair._2) = pair._1
RunLSA.printTopDocsForDoc(normalizedUS, "P versus NP problem", idDocs, docIds)
RunLSA.printTopDocsForDoc(normalizedUS, "Commonwealth", idDocs, docIds)

Note

Si vous obtenez une erreur java.util.NoSuchElementException: key not found, c’est que le titre d’article que vous cherchez ne fait pas partie de votre corpus (cela peut arriver si vous avez changé la seed plus haut). Dans ce cas, choisissez un autre titre d’article.

Trouver des documents similaires à un groupe de plusieurs mots

Nous avons vu plus haut que pour trouver des documents pertinents à un seul terme il faut commencer par choisir la ligne correspondant à ce terme dans la matrice \(\mathbf{V}_k\). Cela revient à multiplier \(\mathbf{V}_k^T\) par un vecteur colonne de dimension \(n\) avec la composante correspondant au terme égale à 1 et les autres composantes nulles. Pour passer à plusieurs termes, on multiplie \(\mathbf{V}_k^T\) par un vecteur colonne de dimension \(n\) avec des composantes non nulles pour tous les termes impliqués dans la requête. Afin de garder le même système de pondération que pour la matrice TF-IDF originale, \(\mathbf{M}\), on considère le poids de chaque terme de la requête égal à son IDF. Ce type de requête équivaut à l’ajout d’un nouveau document au corpus, document qui contient les termes de la requête, et ensuite chercher les documents les plus proches par la méthode présentée plus haut.

Nous créeons une fonction printTopDocsForTerms qui permet d’obtenir les documents qui représentent le mieux une série de mots :

def termsToQueryVector(
    terms: Seq[String],
    idTerms: Map[String, Int],
    idfs: Map[String, Double]): BSparseVector[Double] = {
        val indices = terms.map(idTerms(_)).toArray
        val values = terms.map(idfs(_)).toArray
        new BSparseVector[Double](indices, values, idTerms.size)
}

def topDocsForTermQuery(
        US: RowMatrix,
        V: Matrix,
        query: BSparseVector[Double]): Seq[(Double, Long)] = {
            val breezeV = new BDenseMatrix[Double](V.numRows, V.numCols,
                V.toArray)
            val termRowArr = (breezeV.t * query).toArray
            val termRowVec = Matrices.dense(termRowArr.length, 1, termRowArr)
            val docScores = US.multiply(termRowVec)
            val allDocWeights = docScores.rows.map(_.toArray(0)).
            zipWithUniqueId
            allDocWeights.top(10)
}


def printTopDocsForTerms(terms: Seq[String]) {
    val queryVec = termsToQueryVector(terms, idTerms.toMap, idfs.toMap)
    printIdWeights(topDocsForTermQuery(US, svd.V, queryVec), docIds)
}
printTopDocsForTerms(Seq("birth", "control"))
printTopDocsForTerms(Seq("kingdom", "island"))

Regardez l’implementation des methodes utilisées de la classe RunLSA et essayez de suivre leur fonctionnemment à partir des explications précédentes.

Bibliographie

Karau, H., A. Konwinski, P. Wendell et M. Zaharia, Learning Spark, O’Reilly, 2015.

Ryza, S., U. Laserson, S. Owen and J. Wills, Advanced Analytics with Spark, O’Reilly, 2010.