Octobre 2015


Retour à la vue des calendrier
Jeudi 1 Octobre
Heure: 12:15 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Clustering sous contraintes en Programmation par Contraintes
Description: Christel Vrain La classification non supervisée sous contraintes (aussi appelée clustering sous contraintes) est une tâche importante de fouille de données, permettant de modéliser plus finement une tâche de clustering en intégrant des contraintes utilisateur. Divers types de contraintes peuvent être considérés ; les contraintes les plus courantes sont les contraintes must-link (ML) ou cannot-link (CL) spécifiant que des paires d’objets doivent être (respectivement, ne doivent pas être) dans le même cluster. D’autres contraintes peuvent aussi être posées sur les clusters, précisant par exemple, une borne sur leur diamètre ou sur leur taille. Néanmoins, concevoir un algorithme capable de traiter différents types de contraintes est difficile et la plupart des approches tendent à étendre les méthodes classiques de clustering en intégrant un unique type de contraintes.

Plusieurs travaux ont montré l’intérêt de la Programmation par Contraintes (PPC) pour la fouille de données. Modéliser en PPC a deux avantages : la déclarativité qui permet d’ajouter facilement de nouvelles contraintes, la capacité à énumérer toutes les solutions satisfaisant les contraintes et la capacité, dans le cas de l’optimisation d’un critère, à trouver une solution optimale satisfaisant toutes les contraintes (s’il en existe une).

Dans cet exposé, nous ne considérons que l’apprentissage de partitions et nous donnons deux exemples de l’utilisation de la Programmation par Contraintes pour le clustering sous contraintes. Le premier exemple, proposé par [T. Guns, S. Nijssen, .L De Raedt] modélise le clustering conceptuel : les données sont décrites par leurs propriétés et à chaque cluster est associé un motif, i.e, un ensemble de propriétés que toutes les données du cluster satisfont. Dans le second exemple, issu de nos travaux [T.B. H. Dao, K.C. Duong, C. Vrain], un cadre déclaratif et générique permet de modéliser différentes tâches de clustering sous contraintes, étant donnée une mesure de dissimilarité entre les objets.
Mardi 6 Octobre
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: The Johnson-Lindenstrauss Lemma in Linear and Integer Feasibility
Description: Leo Liberti The Johnson-Lindenstrauss lemma allows dimension reduction on real vectors with low distortion on their pairwise Euclidean distances. This result is often used in algorithms such as $k$-means or $k$ nearest neighbours since they only use Euclidean distances, and has sometimes been used in optimization algorithms involving the minimization of Euclidean distances. In this paper we introduce a first attempt at using this lemma in the context of feasibility problems in linear and integer programming, which cannot be expressed only in function of Euclidean distances.

Leo Liberti, Vu Khac Ky, Pierre-Louis Poirion
CNRS LIX, Ecole Polytechnique, Palaiseau, France
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Calculabilité et pavages
Description: Pascal Vanier Les pavages, ou sous-shifts de type fini sont des ensembles de coloriages du plan vérifiant des contraintes locales en nombre fini. Nous nous intéresserons en particulier au problèmes d'isomorphisme entre sous-shifts, connu sous le nom de conjugaison et plus particulièrement aux invariants de conjugaison, qui sont des "objets" permettant de caractériser certains aspects des sous-shifts. Nous donnerons en particulier des caractérisations calculatoires de ces derniers qui permettront de voir les liens intimes qui lient pavages et classes de complexité/calculabilité.
Jeudi 8 Octobre
Heure: 12:15 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Amélioration de l'apprentissage de forêts d'arbres latents : quelle mesure pour évaluer la qualité de clustering ? Application en bioinformatique.
Description: Christine Sinoquet Au carrefour entre théorie des graphes et théorie des probabilités, nous avons proposé une nouvelle classe de modèles graphiques probabilistes [1]. Ce type de modèle, ou forêt de modèles hiérarchiques à variables latentes (FLTM - Forest of latent tree models) [2], est dédié à la modélisation de données complexes, de grande dimension, et fortement corrélées. Le choix d'une modélisation hiérarchique a facilité la conception d'un algorithme d'apprentissage du modèle qui passe à l'échelle.

L'algorithme d'apprentissage du modèle FLTM repose sur un processus de clustering ascendant hiérarchique. Parmi un ensemble de méthodes de clustering compatibles avec la très grande dimension des données modélisées, le problème est d'identifier la meilleure méthode de clustering et le meilleur paramétrage pour cette dernière.

En préambule, les principes de l'évaluation extrinsèque et de l'évaluation intrinsèque de clustering seront rappelés. Les résultats d'une première étude focalisée sur la comparaison des comportements de quatre critères intrinsèques seront ensuite exposés [3]. Des partitions indépendantes, générées aléatoirement, selon divers protocoles, ont d'abord été comparées. Trois méthodes de clustering ont été considérées. Des couples de partitions (prédite, réelle) ont ensuite été comparées pour ces quatre critères extrinsèques, sur données génétiques. Cependant, la connaissance de la partition réelle n'étant elle-même qu'approchée, une utilisation réaliste doit recourir à un critère intrinsèque. Le choix s'est porté sur deux d'entre eux : le critère de redondance et la différence d'entropies normalisée, spécialement adaptée aux données génétiques. Pour chacune des trois méthodes de clustering utilisées, une deuxième étude s'est donc attachée à comparer les distributions des valeurs de ces deux critères, obtenues pour différents ajustements des paramètres de la méthode de clustering. Les résultats de cette étude seront présentés.

Dans le cas de données génétiques, bien qu'approchée, la connaissance de la partition réelle révèle certaines caractéristiques de la distribution des tailles de clusters. Une troisième étude s'est donc focalisée sur l'amélioration du critère de la différence d'entropies normalisée, afin de prendre en compte ces caractéristiques. Quatre versions de ce critère sont comparées, pour des données génétiques.

Enfin, ces études seront replacées dans le contexte plus vaste d'une campagne de tests intensifs visant la comparaison de trois méthodes alternatives aux GWAS classiques. L'objectif d'une GWAS (genome-wide association study - étude d'association à l'échelle du génome) est d'identifier les facteurs génétiques potentiellement responsables d'un phénotype (e.g. une pathologie génétique). Dans le contexte du projet ANR SAMOGWAS (Specific Advanced MOdels for Genome Wide Association Studies), trois stratégies GWAS sont comparées : l'une exploitant le modèle FLTM [3], l'une utilisant une variante des forêts aléatoires, la troisième combinant les deux approches précédentes. Des résultats préliminaires seront présentés.


[1] R. Mourad, C. Sinoquet and P. Leray (2011) A hierarchical Bayesian network approach for linkage disequilibrium modeling and data-dimensionality reduction prior to genome-wide association studies. BMC Bioinformatics, 12(1), 16, doi:10.1186/1471-2105-12-16.

[2] R. Mourad, C. Sinoquet, N. L. Zhang, T. Liu and P. Leray (2013) A survey on latent tree models and applications. Journal of Artificial Intelligence Research, 47, 157-203.

[3] D.-T. Phan, P. Leray and C. Sinoquet (2015) Latent Forests to Model Genetical Data for the Purpose of Multilocus Genome-wide Association Studies. Which clustering should be chosen? To appear in BIOSTEC2015, Communication in Computer and Information Science, Springer.
Vendredi 9 Octobre
Heure: 12:45 - 15:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Tenseurs aléatoires (soutenance de thèse)
Description: Stéphane Dartois During this defense I present pieces of the work I achieved on random tensor models (tensor models for short). I will define colored triangulations and then review their combinatorics. After this is done I show how one can write integral representation of their generating series. These representations are called tensor models. Using this representation I will describe the combinatorial 1/N expansion for two different kinds of models generating specific classes of colored and non-colored combinatorial maps. I will then concentrate on a specific model, that is the simpler non trivial tensor model and explore some of its properties. In particula r I review the properties of its double scaling limit, then using its Hubbard-Stratanovitch representation, I show how one can use matrix models techniques to recover results obtained using combinatorial techniques. I will finally present several results that point towards integrable structures in the framework of random tensor models.
Mardi 13 Octobre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Analyse asymptotique et génération aléatoire des structures en diamant
Description: Olivier Bodini Nous allons d'écrire et étudier une classe importante de DAG, appelé structure en diamant. Cette étude repose sur une analyse asymptotique d'équations différentielles non linéaires. Nous expliquerons aussi comment développer des générateurs aléatoires efficaces pources structures. Travail en commun avecHsien-Kuei Hwang, Antoine Genetrini et Xavier Fontaine.
Lundi 19 Octobre
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: An uncertainty approach (probabilistic + possibilistic) for analyzing users' attitudes (emotions & opinions (feelings & judgments)) from their literature
Description: Sayyed Ali Hossayni In this seminar, we adopt an uncertainty approach to attitude prediction. Uncertainty approach includes probabilistic and possibilistic approaches and attitude includes opinion and emotion. The seminar has two parts: probabilistic & possibilistic attitude mining. In the probabilistic part, we first propose a new approach to attitude mining and prove its efficiency by applying it on collaborative filtering. Our approach, unlike the existing ones in state of the art, does not represent the users’ attitudes as numbers, but as a probability/possibility distribution function (PDF) (mathematically speaking, not a whole graph but its few (normally 1 or 2) parameter(s)). Then, we suggest upgrading Sentilo (the existing opinion mining platform in state of the art) to become able to provide more knowledge about attitude of the users’ (or attitude of whom they wrote about) about the entities/topics. In the second part of the seminar, we explain a different type of uncertainty (possibility) and also its better impact (under some circumstances) on data mining. Then, we will propose application of a new possibilistic tools that we customize it for text mining for being utilizable in attitude prediction. It is notable that the second part of the presentation can also be useful for general data mining purposes.
Mardi 20 Octobre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Forme limite de tableaux de Young rectangulaires
Description: Philippe Marchal En 2004, Pittel et Romik ont montré l'existence d'une forme limitepour les tableaux de Young rectangulaires.Je montrerai comment la méthode probabiliste des "densités", que je développe depuis quelques travaux déjà, permet de retrouver cette forme limite et donne aussi les fluctuations sur lebord : on trouve une gaussienne dans les coins et Tracy-Widom ailleurs sur le bord.