2015


Retour à la vue des calendrier
Mardi 8 Septembre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Why and when does the half-normal distribution appear in combinatorics?
Description: Michael Wallner We present an extension of a theorem by Michael Drmota and Michèle Soria [1997] that can be used to identify the limiting distribution for a class of combinatorial schemata. This is achieved by determining analytical and algebraic properties of the associatedbivariate generating function. We give sufficient conditions implying a half-normal limiting distribution, extending the known conditions leading to either a Rayleigh, a Gaussian or a convolution of the last two distributions. Finally, we present some applications to lattice path and tree enumeration, images and preimages in random mappings.
Mardi 15 Septembre
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: A branch-and-cut-and-price algorithm for the green vehicle routing problem with partial recharges and multiple technologies
Description: Alberto Ceselli
Abstract: We tackle a variation of the vehicle routing problem in which the transportation fleet is composed of electric vehicles with limited autonomy in need for recharge during the execution of their duties. Different technologies can be chosen at each station, offering different trade-off between recharge cost and time.

We present an algorithm exploiting column generation, cutting planes and branch-and-bound for the exact solution of the problem. The pricing phase requires elementary resource constrained shortest path problems to be solved, and is carried out with both heuristics and an exact dynamic programming routine. The cut separation phase is performed by running heuristics from the literature on a particular support graph.

Experiments on benchmark instances from the VRP literature reveal that our algorithm is effective in solving instances with up to thirty customers, nine recharge stations, five vehicles and three technologies to optimality.
Mercredi 23 Septembre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: A fresh view on the matching problem (attention, c'est un mercredi)
Description: Sergio Caracciolo I will review some new results in the stochastic euclidean bipartitematching problem.First I will look at the simple one dimensional version, for whichmany exact results can be achieved. Afterwards, by discarding thediscrete nature of the problem, as usual in a critical system, I willshow how it is possible to resort to a continuous version for which ananalytical expression for the minimum cost and correlation functionscan be computed.
Heure: 14:00 - 16:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: A fresh view on the matching problem
Description: Sergio Caracciolo I will review some new results in the stochastic euclidean bipartite
matching problem.
First I will look at the simple one dimensional version, for which
many exact results can be achieved. Afterwards, by discarding the
discrete nature of the problem, as usual in a critical system, I will
show how it is possible to resort to a continuous version for which an
analytical expression for the minimum cost and correlation functions
can be computed.
Lundi 28 Septembre
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Golfred: Génération de récits à partir d'expériences spatiales d'un robot de service par extraction de connaissances textuelles
Description: Jorge Garcia Flores Le but du projet est de donner à un robot la capacité de lire les phrases écrites qu'il rencontre sur son chemin et d'en faire un compte rendu à la fin de son parcours. Notre hypothèse est que la production de ce genre de récits est possible en embarquant le système de lecture automatique (machine reading) FRED dans le robot Golem (développé par l'équipe de Luis A. Pineda, professeur à l'IIMAS) et en adaptant le système de génération de texte RTGen (développé par l'équipe de Claire Gardent au LORIA). Le robot a la capacité de se déplacer dans le labo et de reconnaître les messages textuels, tandis que FRED est capable de chercher et d'interpréter des mots clés à partir de DBPedia, la base de données de Wikipedia. Enfin l'adaptation de RTgen aux données RDF de DBPedia permettra de transformer le graphe RDF construits par FRED en un texte décrivant le parcours de Golem. Le principal critère discursif pour la génération du récit est le parcours spatial: Golem (aidé par FRED et RTGen) raconte ce qu'il a lu sur son chemin (et trouvé sur Wikipedia).
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.