<  Back to the Polytechnique Montréal portal

Impact de l'hyperparamètre alpha sur l'algorithme d'analyse de textes Latent Dirichlet Allocation

Émile Ducrocq

Masters thesis (2014)

[img]
Preview
Download (1MB)
Cite this document: Ducrocq, É. (2014). Impact de l'hyperparamètre alpha sur l'algorithme d'analyse de textes Latent Dirichlet Allocation (Masters thesis, École Polytechnique de Montréal). Retrieved from https://publications.polymtl.ca/1601/
Show abstract Hide abstract

Abstract

Résumé L'algorithme de classification non supervisée de documents Latent Dirichlet Allocation (LDA) est devenu en l'espace d'une dizaine d'années l'un des plus cités dans la littérature du domaine de la classification. Cet algorithme a la particularité de permettre à un document d'appartenir à plusieurs thématiques dans des proportions variables. Celui-ci se base sur un hyper-paramètre encore peu étudié dans la communauté scientifique, le paramètre α qui contrôle la variabilité des thématiques pour chaque document. Ce paramètre correspond à l'unique paramètre de la distribution de Dirichlet. Il définit la probabilité initiale des documents dans le contexte du LDA. À chaque extrême du spectre des valeurs que l'on peut assigner à ce paramètre, il devient possible de limiter chaque document à une seule thématique, jusqu'à forcer tous les documents de partager toutes les thématiques uniformément. Le présent mémoire tente d'illustrer le rôle du paramètre α et de démontrer l'effet qu'il peut avoir sur la performance de l'algorithme. Le paramètre α est un vecteur dont la longueur correspond au nombre de thématiques et qui est généralement fixé à une valeur constante. Cette valeur peut être soit déterminée arbitrairement, soit estimée durant la phase d'apprentissage. Une valeur faible amène la classification vers un petit nombre de thématiques par document, et à l'inverse une valeur élevée amène à assigner plusieurs thématiques par documents. Certains travaux de Wallach et coll. ont démontré que des distributions non uniformes à ce paramètre pouvaient améliorer la mesure de classification de l'algorithme LDA. Ces travaux ont été effectués avec des données réelles pour lesquelles nous ne connaissons pas la distribution des thématiques sous-jacentes. Ces données ne permettent donc pas de valider si l'amélioration obtenue provient du fait que la distribution des thématiques correspond effectivement à une distribution non uniforme dans la réalité, ou si au contraire d'autres facteurs liés à des minimums locaux du LDA ou d'autres facteurs circonstanciels expliquent l'amélioration. Pour étudier cette question, notre étude porte sur des données synthétiques. Le LDA est un modèle génératif qui se prête naturellement à la création de documents synthétiques. Les documents sont générés à partir de paramètres latents connus. L'hypothèse naturelle qui est faite est évidemment de présumer qu'en arrimant le paramètre α utilisé avec l'algorithme LDA à la fois pour la génération des données et pour l'apprentissage, la performance sera la meilleure. Les résultats démontrent que, contrairement aux attentes, la performance du LDA n'est pas nécessairement optimale lorsque les α de la génération et de l'apprentissage sont identiques. Les performances optimales varient selon les valeurs α du corpus. Les différences les plus marquées se trouvent lorsque le corpus tend à être composé de documents mono-thématiques, auquel cas les α d'apprentissage uniformes fournissent les meilleures performances. Les différences de performance s'amenuisent à mesure que les valeurs de α deviennent grandes et que les corpus sont composés de thématiques multiples. On observe alors moins de différences de performance et aucune tendance claire ne surgit quant à la performance optimale. Wallach et coll. ont démontré qu'une distribution non uniforme pour α pouvait donner de meilleurs résultats, ce qui ne corrobore pas les conclusions de cette étude. Cependant, les raisons de l'amélioration obtenues demeurent encore hypothétiques. D'une part, les résultats proviennent de corpus réels, qui peuvent s'avérer plus complexes ou relativement différents du modèle du LDA. D'autre part, la différence peut aussi provenir de l'approche utilisée pour l'entraînement des variables latentes, ou encore parce que l'asymétrie du paramètre α était plus faible que pour notre étude. L'amélioration de leur performance pourrait provenir d'un maximum local. Car, contrairement à notre étude, il est difficile avec des données réelles de tenter d'explorer l'espace des paramètres latents d'un corpus puisqu'ils sont inconnus. Une autre contribution de cette étude est d'améliorer la performance du LDA par l'initialisation d'un de ses paramètres latents, la distribution des mots par thématique (la matrice β). Nous utilisons une méthode de classification non supervisée basée sur l'algorithme bayésien naïf. Il en est ressorti un gain de performance substantiel dans le cas de corpus mono-thématiques en plus d'une meilleure fiabilité par des résultats plus stables. Une dernière contribution aborde la problématique de la comparaison de classifications selon leur représentation des thématiques. Cela a amené à définir une mesure de similarité de matrices qui est robuste à la permutation et à la rotation. Ce travail est toujours en cours, mais nous rapportons les résultats partiels, car ils fournissent une contribution non négligeable. En plus de notre contexte, cette mesure peut avoir des applications dans plusieurs autres domaines où il faut évaluer et comparer des résultats d'algorithmes non supervisés, notamment comme la factorisation de matrices par valeurs non négatives (NMF), ou tout autre contexte où les résultats d'un algorithme s'expriment sous forme matricielle, mais où le résultat escompté peut être transformé par rotation et par permutation ce qui complexifie la comparaison.----------Abstract Latent Dirichlet Allocation (LDA) is an unsupervised text classification algorithm that has become one of the most famous and quoted algorithm within the last ten years. This algorithm allows documents to belongs to several topics. LDA relies on an hyperparameter that is generally fixed and received little attention in the scientific community. This variable, α, is a vector that controls the proportions of topics in documents. It is the sole parameter of the Dirichlet probability distribution and it defines the initial probability of documents in the LDA model. Through α, one can force every documents to be composed of a single topic, or conversely make every document share the same mixture of topics. This thesis investigates the role of the α hyperparameter on the document classification performance of LDA. The α vector's length corresponds to the number of topics, which is initially defined to a constant value. This value can either be defined arbitrarily, or estimated during the learning phase. A small value leads to a small number of topics per document and vice-versa. Work by Wallach and al. has demonstrated that non-uniform distributions of this vector parameter could enhance the classification performance of the LDA algorithm. This work has been conducted with real data, for which the underlying distribution of topics is unknown. Therefore, it does not allow to verify if the the improvement effectively comes from a better fit of the α parameter to real data, or if it comes from some other reasons such as better avoidance of local minima. To investigate this question, our study is conducted with synthetic data. The LDA is a generative model and the generation of documents from an underlying LDA latent parameter configuration is straightforward. The documents are generated from known distributions of topics. The obvious hypothesis is to expect that the best performance of the classification will be obtained when the vector α for the corpus generation is identical to the one of the LDA training. Contrary to expectations, results show that the performance is not better when α of the corpus is identical to the training one. The performances vary across the range of corpora α parameter. The strongest differences are observed when the corpus tends to be composed of mono-topics documents, in which case a uniform α tends to give better performance. The differences become smaller as α values get larger, until the corpus is composed of multiple well-distributed topics. In that case, we find smaller performance differences, and no clear performance trend emerges. These results run against Wallach and al. results who have demonstrated that a non-uniform distribution for α can lead to better results. However, the reasons for their improvements remain unclear. On one hand, they were relying on real corpus, that can be more complex or be relatively different from the LDA model. On the other hand, the differences could be related to the LDA latent variable training algorithm, and their improvements could be due to a local maximum, or because the α parameter distribution was flatter than in our study. Unlike our study, it is hard to explore the space of latent variable of a corpus with real data and therefore to rule out the possibility that the real data is subject to local tendencies. Another contribution of this study is the improvement of the LDA through the initialization of one of its latent parameter, namely the distribution of words per topic (the β matrix). We use an unsupervised classification method based on the naive Bayes algorithm. It yields a substantial improvement of performance in the case of uni-topic corpus, in addition to a greater reliability as the results are more stable across simulation runs. A last contribution of our work addresses the problem of comparing classifications along their topic representation. This lead us to define a new similarity measure, which is resilient to permutation and rotation. This is still ongoing work, but we present partial results as an appendix of this document, since we believe it is a significant contribution. In addition to its use in our own context, this measure can have applications in several other fields where we require to evaluate and compare results coming from unsupervised algorithm results, such as the non-negative matrix factorization (NMF), or any other applications where the results can be expressed as a matrix that can be subject to permutations and rotations of its dimensions, which makes the comparison complex.

Open Access document in PolyPublie
Department: Département de génie informatique et génie logiciel
Dissertation/thesis director: Michel C. Desmarais
Date Deposited: 01 Apr 2015 15:48
Last Modified: 24 Oct 2018 16:11
PolyPublie URL: https://publications.polymtl.ca/1601/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only