Fast and Consistent Algorithm for the Latent Block Model
Algorithme rapide et consistant pour le modèle des blocs latents
Résumé
The latent block model is used to simultaneously rank the rows and columns of a matrix to reveal a block structure. The algorithms used for estimation are often time consuming. However, recent work shows that the log-likelihood ratios are equivalent under the complete and observed (with unknown labels) models and the groups posterior distribution to converge as the size of the data increases to a Dirac mass located at the actual groups configuration. Based on these observations, the algorithm Largest Gaps is proposed in this paper to perform clustering using only the marginals of the matrix, when the number of blocks is very small with respect to the size of the whole matrix in the case of binary data. In addition, a model selection method is incorporated with a proof of its consistency. Thus, this paper shows that studying simplistic configurations (few blocks compared to the size of the matrix or very contrasting blocks) with complex algorithms is useless since the marginals already give very good parameter and classification estimates.
Le modèle des blocs latents est utilisé pour classer simultanément les lignes et les colonnes d'une matrice afin de révéler une structure en blocs. Les algorithmes utilisés pour l'estimation prennent souvent beaucoup de temps. Cependant, des travaux récents montrent que les rapports de log-vraisemblance sont équivalents sous les modèles complet et observé (avec des étiquettes inconnues) et que la distribution postérieure des groupes converge à mesure que la taille des données augmente vers une masse de Dirac située au niveau de la configuration réelle des groupes. Sur la base de ces observations, l'algorithme Largest Gaps est proposé dans cet article pour effectuer le regroupement en utilisant uniquement les marginales de la matrice, lorsque le nombre de blocs est très petit par rapport à la taille de la matrice entière dans le cas de données binaires. En outre, une méthode de sélection de modèle est incorporée avec une preuve de sa consistance. Ainsi, cet article montre que l'étude de configurations simplistes (peu de blocs par rapport à la taille de la matrice ou des blocs très contrastés) avec des algorithmes complexes est inutile puisque les marginales donnent déjà de très bonnes estimations des paramètres et de la classification.
Origine : Fichiers produits par l'(les) auteur(s)
