Séminaires du département d'informatique et de génie logiciel

Les séminaires du département d'informatique et de génie logiciel ont lieu tous les vendredis à 13h00 au local PLT-3775 (sauf si indiqué autrement). Ces séminaires sont publics et tous peuvent y assister. Si vous désirez donner un séminaire, veuillez contacter Claude-Guy Quimper.

Séminaires passés

Mercredi 24 mai 2017

Maximum Margin Interval Trees
Alexandre Drouin et Toby Dylan Hocking

Heure: 13h00
Local: PLT-3775

Résumé: Learning a regression function using censored or interval-valued output data is an important problem in fields such as genomics and medicine. The goal is to learn a real-valued prediction function, and the training output labels indicate an interval of possible values. Whereas most existing algorithms for this task are linear models, in this paper we investigate learning nonlinear tree models. We propose to learn a tree by minimizing a margin-based discriminative objective function, and we provide a dynamic programming algorithm for computing the optimal solution in log-linear time. We show empirically that this algorithm achieves state-of-the-art speed and prediction accuracy in a benchmark of several data sets.

Note: Une partie de la présentation sera en français et une autre partie en anglais.

Vendredi 21 avril 2017

Reconnaissance visuelle des lieux à l'aide des réseaux de neurones profonds
Amar Ali-Bey
Étudiant au doctorat, Labaratoire Damas

Heure: 13h00
Local: PLT-3775

Résumé: En robotique mobile, reconnaitre un lieu déjà visité par le robot, à l'aide d'une caméra, représente une composante essentielle à la cartographie de l'environnement du robot. Cette reconnaissance visuelle des lieux est un problème qui n'a pas encore été résolu en raison des changements d'apparence des lieux du monde réel. Récemment les réseaux de neurones profonds ont montré de bonnes performances sur des tâches de vision très complexes. Les principaux facteurs derrière ces bons résultats résident dans la capacité des réseaux profonds à apprendre des millions de paramètres en utilisant de très grandes bases de données étiquetées. Encouragés par ces performances, beaucoup de chercheurs se sont orientés vers l'utilisation de ces réseaux pour faire la reconnaissance visuelle des lieux pour la robotique mobile. C'est dans ce cadre que se situe mon projet doctoral.

Dans ce séminaire, je ferai état des recherches actuelles en lien avec la reconnaissance visuelle des lieux pour la robotique mobile, je dégagerai alors des avenues de recherches pour mon doctorat et je donnerai enfin mes premiers résultats expérimentaux.

Vendredi 14 avril 2017

Vendredi Saint (pas de séminaire)

Vendredi 7 avril 2017

L'algorithme de Pacman pour la construction efficace des codes équilibrés
Mounir Mechqrane

Heure: 13h00
Local: PLT-3775

Résumé: Une chaîne de bits est équilibrée si elle contient un nombre de bits 0 égal au nombre de bits 1. Les codes équilibrés sont construits de chaînes de bits équilibrées. Ces codes sont appliqués dans plusieurs domaines. Par exemple, ils sont utilisés dans les systèmes VLSI, en télécommunication par fibre optique et dans les systèmes RFID. Mathématiquement, la construction de ces codes peut se faire en utilisant le codage énumératif. En informatique, cette méthode nécessite des tables de consultation qui peuvent devenir d'une grandeur inappropriée. Une grandeur qui peut être de l'ordre du nombre des atomes dans l'univers. Plusieurs travaux de recherche ont été menés pour optimiser la construction de ces codes. Toutefois, les codes créés par les techniques proposées contiennent plus de redondance que nécessaire, ce qui diminue leur efficacité. Nous présentons dans ce séminaire une nouvelle technique basée sur les permutations, le personnage de jeu vidéo PAC-MAN et les entiers à précision limitée. Nous allons montrer que la redondance introduite par notre technique est particulièrement faible, que les résultats sont nettement meilleurs que ceux des travaux antérieurs et que les complexités temporelle et spatiale utilisées sont linéaires.

Lien: diapositives

Vendredi 31 mars 2017

Andrana: Quick and Accurate Malware Detection for Android
Hana Ajakan et Andrew Bedford
Étudiants au doctorat en informatique

Heure: 13h00
Local: PLT-3775

Résumé: Android's domination of the mobile operating system market has attracted the attention of malware authors. In addition to its large user base, what makes Android attractive to malware authors is that, contrarily to iOS users, Android users can install applications from a wide variety of sources such as first and third-party application markets (e.g., Google Play Store, Samsung Apps), torrents and direct downloads.

In order to protect Android users and their information, we have developed a lightweight malware detection tool for Android called Andrana. It leverages machine learning techniques and static analysis to determine, with an accuracy of 94.90%, if an application is malicious. Its analysis can be performed directly on a mobile device in less than a second and using only 12 MB of memory.

Note: La présentation sera donnée en français.

Vendredi 24 mars 2017

Développement d'une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés
Fatma Haddad (remplacée par Danny Dubé)

Heure: 13h00
Local: PLT-3775

Résumé: En compression de données, une des techniques d'encodage les plus connues est celle de Huffman. Typiquement, la fonction d'encodage construite par la technique de Huffman associe chaque symbole de l'alphabet source à un mot de code fait de bits. La compression vient du fait qu'un symbole plus fréquent se voit associé à un mot de code plus court et vice-versa. Afin que le décodage soit possible, l'ensemble des mots de code doivent former un code préfixe. L'encodage de Huffman est un cas particulier de code fixe à variable (FV).

À l'inverse, d'autres techniques d'encodage visent à construire des fonctions d'encodage variables à fixes (VF). La fonction d'encodage associe les mots d'un dictionnaire source à des mots de code de taille fixe. Les mots du dictionnaire source sont de longueurs variables. Typiquement, on spécifie la taille désirée du dictionnaire; la longueur des mots de code découle de ce choix. La compression vient du fait que, dans le dictionnaire construit, les mots qui sont faits de symboles plus fréquents sont plus longs et vice-versa. La technique de Tunstall est la plus connue parmi celles qui construisent des fonctions d'encodage VF. Elle est considérée comme étant optimale; i.e. elle construit le meilleur dictionnaire de la taille spécifiée.

En fait, elle est optimale si on se restreint à des dictionnaires formant un code préfixe. Or, cette contrainte n'est pas obligatoire. Si on relaxe cette contrainte, il est parfois possible de construire de meilleurs fonctions d'encodage que celles de Tunstall. En particulier, Yamamoto et Yokoo (YY) ont proposé de construire des fonctions d'encodage qui utilisent des dictionnaires formant des codes quasi-instantanés (almost-instantaneous VF, AIVF). Ils ont proposé des algorithmes pour construire des arbres, lesquels représentent les dictionnaires, dans deux modes: le mode mono-arbre et le mode multi-arbre.

Nous avons identifié deux défauts dans les techniques de YY: celui de la racine complète dans le mode multi-arbre et celui de l'exécution complète des propositions d'ajout de noeuds. Nous avons proposé des correctifs à ces deux défauts. Enfin, nous avons proposé un nouvel algorithme de construction de fonctions d'encodage AIVF basé sur le principe de la programmation dynamique.

Lien: diapositives

Vendredi 17 mars 2017

Apprentissage de modèles à base de règles pour la prédiction de la résistance aux antibiotiques
Alexandre Drouin
Étudiant au doctorat, GRAAL

Heure: 13h00
Local: PLT-3775

Résumé: La résistance aux antibiotiques est un problème de santé publique majeur qui a des implications dans la pratique de la médecine à l'échelle mondiale. La prédiction du profil de résistance d'une bactérie à partir de son génome permettrait une meilleure utilisation des agents antimicrobiens. Par exemple, il serait possible de concevoir des plans de traitements personnalisés pour chaque individu, ce qui promouvrait une meilleure utilisation des antibiotiques et ralentirait le développement de résistances dans la population.

Dans ce contexte, les algorithmes d'apprentissage parcimonieux sont des outils intéressants, parce qu'ils apprennent des modèles qui dépendent d'un petit nombre de règles. Celles-ci peuvent ensuite être raffinées et interprétées par les experts du domaine. Toutefois, comme pour la majorité des problèmes d'apprentissage en génomique, les données sont peu nombreuses et de très grande dimensionnalité. Il est donc nécessaire de concevoir des algorithmes qui ont une forte résistance au surapprentissage.

Une étude récente a utilisé l'algorithme Set Covering Machine (SCM) pour obtenir des modèles concis et interprétables de la résistance aux antibiotiques de 6 pathogènes humains. En quelques minutes de calcul, des mécanismes de résistance connus et validés expérimentalement ont été retrouvés, confirmant ainsi la pertinence des modèles. De plus, une comparaison à d'autres algorithmes d'apprentissage a démontré qu'en plus d'être les plus parcimonieux, les modèles appris par SCM sont très compétitifs en matière d'erreur de prédiction. Finalement, une analyse théorique de la généralisation de cet algorithme lors de l'apprentissage à partir de données génomiques a démontré une forte résistance au surapprentissage.

Dans cette présentation, j'introduirai l'algorithme SCM, ainsi qu'une implémentation efficace pour les données génomiques (https://github.com/aldro61/kover). Je m'appuierai sur des résultats théoriques et empiriques pour démontrer que cet algorithme est bien adapté à l'apprentissage à partir de données génomiques. J'introduirai aussi une extension de ces travaux à l'apprentissage d'arbre de décision et je montrerai l'amélioration qui en découle.

Lien: diapositives

Vendredi 10 mars 2017

Semaine de lecture (pas de séminaire)

Vendredi 3 mars 2017

Généralisation de règles de filtrage pour la contrainte Cumulative
Vincent Gingras
Étudiant au doctorat, Laboratoire de programmation par contraintes

Heure: 13h00
Local: PLT-3775

Résumé: Les problèmes d'ordonnancement d'atelier occupent une place omniprésente dans la production industrielle. On définit un problème d'ordonnancement comme étant un ensemble de tâches devant être exécutées sur une ou plusieurs ressources partagées. Le lien avec la production industrielle est par conséquent très évident, alors qu'on peut imaginer la production des différents produits comme étant les tâches et la machinerie dont dispose l'entreprise comme étant la ressource partagée. Dans les récentes années, la programmation par contraintes s'est avérée très efficace pour la résolution de ces problèmes d'ordonnancement. Ce paradigme de programmation emploie des algorithmes de filtrage pour réduire l'espace de solution et par le fait même accélérer l'acquisition d'une solution dans celui-ci. Plusieurs règles et algorithmes de filtrage ont été proposés dans la littérature au cours des récentes années pour les contraintes d'ordonnancement. Le filtrage complet des valeurs incohérentes des domaines des variables ne peut être réalisé en temps raisonnable vu la NP-Complétude du problème général d'ordonnancement. Ces algorithmes reposent donc sur une relaxation du problème faisant référence à l'élasticité des tâches. Dans le cadre de ce séminaire, je présenterai une généralisation de deux de ces règles de filtrage basée sur une fonction estimant de façon optimiste le temps de fin le plus tôt d'un ensemble de tâches. Je présenterai également deux algorithmes permettant d'appliquer ces règles généralisées en utilisant une relaxation énergétique plus réaliste que celle utilisée dans la littérature, et permettant donc un meilleur filtrage. Les résultats expérimentaux démontrent les bienfaits de cette généralisation alors que le temps d'exécution du solveur, ainsi que le nombre de retours-arrières effectués par celui-ci, sont réduits lorsque la méthode proposée est utilisée.

Vendredi 24 février 2017

GPU et projets académiques
David Landry
Étudiant à la maîtrise, Laboratoire de robotique mobile

Heure: 13h00
Local: PLT-3775

Résumé: L'arrivée des GPGPU (General Purpose Graphics Processing Unit) a ouvert de nouvelles possibilités à la communauté scientifique. Des programmes autrefois trop coûteux à calculer, mais massivement parallélisables, sont désormais à notre portée. L'adoption des GPGPU a été rapide dans les domaines où leur utilisation est critique (réseaux neuronaux, vision numérique par exemple). Cependant, on peut argumenter que les GPGPU sont encore sous-utilisés dans d'autres domaines, malgré qu'il y ait des gains importants à faire sur le plan des performances. Notre objectif lors de ce séminaire sera de favoriser l'utilisation du GPGPU dans les projets programmés au département. Après un bref aperçu des particularités architecturales des GPU, nous décrirons quels programmes peuvent en bénéficier facilement. Par la suite nous étudierons différents outils qui permettent d'utiliser les GPU aisément. À la fin de ce tutoriel, les auditeurs sauront identifier les projets qui peuvent bénéficier des GPGPU. Ils sauront aussi à quel endroit débuter le travail pour améliorer les performances de leurs programmes.

Liens: Diapositives , code OpenCV, code ArrayFire, code OpenAcc

Vendredi 17 février 2017

Techniques de propagation de la contrainte de ressource en ordonnancement disjonctif et cumulatif
Roger Kameugne
Chercheur postdoctoral, Laboratoire de programmation par contraintes

Heure: 13h00
Local: PLT-3775

Résumé: L'approche par contraintes est de plus en plus appliquée pour la modélisation et la résolution des problèmes d'ordonnancement de la vie réels. Cet enthousiasme est dû essentiellement à l'efficacité et l'efficience des algorithmes utilisés pour propager les contraintes de ressources. Alors que les algorithmes de filtrage utilisés dans le cas disjonctif sont de faible complexité (entre O(n) et O(nlog n)), la complexité des algorithmes analogues dans le cas cumulatif sont encore de l'ordre O(n3) en moyenne. Cette différence est due au fait que dans le cas cumulatif, plusieurs tâches ou activités peuvent s'exécuter en parallèle tant que la capacité de la ressource n'est pas violée. Dans ce contexte, l'un des défis consiste alors à réduire la complexité de ces différents algorithmes tout en augmentant leur pouvoir de filtrage. Après une brève introduction à la programmation par contraintes et à l'ordonnancement, nous présenterons et illustrerons les règles utilisées pour propager les contraintes de ressource en ordonnancement disjonctif et cumulatif. On s'intéressera particulièrement à l'edge-finder, au not-first/not-last et au raisonnement énergétique.

Vendredi 10 février 2017

Contextual Suggestion - word vector model and global interest
Jian Mo
Étudiant à la maîtrise

Heure: 13h00
Local: PLT-3775

Résumé: The contextual suggestion task is how to generate better recommendations to users with prior knowledge including user background, preference history, city location, time of the year and many other contextual information. In this talk, we will introduce our approach to the task at TREC 2016. We have two major models. The first model is a global interest regressor trained to model popular interests loved by all users (E.g. Museums and National Parks). The second model introduces word embeddings to captures individual user preference. Both user profiles and candidate places are represented as word vectors in a same Euclidean space. So that a similarity score between user and attraction can be measured by their vector distance. The combined model of the two gained the highest Precision at 5 among all other track results.

Note: Cette présentation sera donnée en anglais.

Vendredi 3 février 2017

Optimisation de fonctions à haut coût
Ulysse Côté-Allard
Étudiant au doctorat, Département de génie informatique et de génie électrique

Heure: 13h00
Local: PLT-3775

Résumé: Une fonction à haut coût est une fonction pour laquelle chaque évaluation est coûteuse (nécessite beaucoup de ressources à calculer). Ce type de fonction ne peut être optimisée grâce aux techniques traditionnelles, car celles-ci assument des évaluations rapides et peu coûteuses. L'une des techniques les plus utilisées pour l'optimisation de fonctions à haut coût est l'optimisation bayésienne. Celle-ci consiste à utiliser un processus gaussien afin de simuler la fonction réelle. La fonction de régression ainsi obtenue est rapide à évaluer. Le but devient alors de trouver comment explorer et exploiter la fonction à haut coût ainsi que la meilleure façon de balancer ces deux comportements. Pour ce faire, nous proposons un nouvel algorithme (SquidSwarm) basé sur l'optimisation bayésienne. SquidSwarm est repose sur un nouvel algorithme d'optimisation de groupe de particules (Particle Swarm Optimization) nommé Time Adaptation Decay Particle Swarm Optimization (TAD-PSO). La première partie de l'exposé consistera à présenter ce nouvel algorithme ainsi qu'à le comparer à certains des autres algorithmes de PSO les plus utilisés (PSO-G, PSO-L, CLPSO, HPSO-TVAC, OLPSO-L, OLPSO-G). En second lieu, nous verrons comment utiliser TAD-PSO dans le contexte de l'optimisation bayésienne, afin de donner naissance à l'algorithme de SquidSwarm. Des résultats préliminaires pour SquidSwarm seront présentés.

Lien: diapositives

Vendredi 27 janvier 2017

Optimisation bayésienne pour espaces d'hyperparamètres avec conditions
Julien-Charles Lévesque
Étudiant au doctorat, Laboratoire de vision et systèmes numériques, Département de génie électrique et de génie informatique

Heure: 13h00
Local: PLT-3775

Résumé: L'optimisation bayésienne est couramment appliquée pour ajuster les hyperparamètres d'algorithmes d'apprentissage automatique. Ces hyperparamètres peuvent être structurés et il peut y avoir une relation de dépendance ou de condionalité entre certains hyper-paramètres. Dans cette présentation, nous allons cibler le problème combiné de la sélection d'un modèle d'apprentissage et de l'optimisation de ses hyperparamètres (en anglais, the combined algorithm selection and hyperparameter optimization problem). Ce problème comprend au moins un hyperparamètre conditionnel, le choix de l'algorithme d'apprentissage, et les hyperparamètres des modèles sous-jacents dépendent de ce choix. Nous verrons que l'optimisation bayésienne avec des processus gaussiens peut être utilisée pour l'optimisation d'espaces conditionnels avec l'injection de connaissances concernant les conditions dans les noyaux. Nous proposons et examinons le comportement de deux noyaux, un noyau conditionnel qui force une similarité nulle entre les échantillons provenant de différentes branches de condition, et le noyau de Laplace, basé sur des similitudes avec les processus de Mondrian et les forêts aléatoires. Nous démontrons l'intérêt d'utiliser ces noyaux ainsi que l'impact positif d'une imputation correcte des hyperparamètres inactifs sur un espace de classifieurs tirés de la librairie scikit-learn.

Vendredi 20 janvier 2017

Recherche d'information dynamique
Robin Joganah
Étudiant à la maîtrise, Département d'informatique et de génie logiciel

Heure: 13h00
Local: PLT-3775

Résumé: La recherche d'information dynamique a pour objectif de satisfaire le besoin d'information d'un utilisateur sur plusieurs concepts autour d'une requête initiale. L'utilisateur (simulé) participe à cette recherche en fournissant son avis sur la pertinence des documents tout au long du processus itératif. Dans ce contexte, le défi consiste à être capable de proposer un équilibre entre la diversité de concepts et la pertinence vis à vis de la requête initiale de l'utilisateur, afin de couvrir ses besoins d'information dans la période de temps la plus courte possible. Les enjeux de ce type de recherches sont notamment les domaines complexes tels que des événements récents (Épidémie du virus Ebola), le "Deep Web" et les différents trafics (humains, produits illégaux) qu'il peut abriter.

Lien: diapositives

Vendredi 11 novembre 2016

A linear time algorithm for constrained optimal segmentation
Toby Hocking
Post-doctoral researcher, McGill University

Heure: 11h00
Local: PLT-2783

Résumé: Accurately detecting "peaks" or up changes is important in the analysis of time series and genomic data. Our ICML2015 paper describes PeakSeg, a constrained optimization model with state-of-the-art accuracy. The algorithm proposed in that paper has two drawbacks (1) it does not find the optimal solution to the PeakSeg optimization problem, and (2) its time complexity is quadratic in the number of data points. In this presentation I will show how a new functional pruning algorithm can be used to overcome both of those drawbacks. I will discuss the computational complexity (time, memory, disk space) as well as the accuracy of this new algorithm, which we have implemented in an R package.

Note: Cette présentation sera donnée en anglais. Joint work with Guillem Rigaill, Paul Fearnhead, and Guillaume Bourque

Liens: diapositives , article, librairie

Lundi 19 septembre 2016

Tirer parti de la science des données pour apprendre directement des modèles traitables pour l'inférence probabiliste et la prise de décision
Pascal Poupart
Professeur agrégé à la David R. Cheriton School of Computer Science, University of Waterloo, Waterloo (Canada)

Heure: 13h30
Local: PLT-2700

Résumé: La plupart des problèmes en intelligence artificielle sont NP-difficiles et donc de nombreux travaux ont été consacrés à l'exploitation de structures spécifiques à certains problèmes et à la conception d'approximations pour la mise à l'échelle des algorithmes. Avec la montée de la science des données, un changement de paradigme est en cours. Au lieu de demander à un expert du domaine de spécifier un modèle pour lequel le raisonnement peut être intraitable, l'apprentissage machine nous permet d'apprendre des modèles traitables directement à partir des données. La réalité est que la plupart des modèles spécifiés par les experts du domaine sont approximatifs tandis que les modèles obtenus à partir de données peuvent être plus précis. En outre, en utilisant une hiérarchie de modèles pour lesquels la complexité de représentation est la même que la complexité du raisonnement, il est possible d'apprendre des modèles dont la complexité augmente avec la quantité de données et qui demeurent traitables. Par exemple, l'inférence dans les modèles graphiques probabilistes tels que les réseaux bayésiens et les réseaux markoviens sont #P-complet. Cependant, si nous estimons des réseaux somme-produit (type spécial de réseaux neuronaux profonds qui sont équivalents aux réseaux bayésiens et markoviens) directement à partir des données, l'inférence probabiliste exacte peut être faite en temps linéaire par rapport à la taille du réseau. Dans cet exposé, je vais expliquer comment apprendre les réseaux somme-produit à partir d'ensembles de données en transmission continue dans un mode en ligne et distribué pour une large gamme d'applications, y compris la modélisation du langage, la reconnaissance de l'écriture manuscrite, les systèmes de recommandation, les réseaux de communication, la classification et la prédiction de séries temporelles. Je vais aussi expliquer comment modéliser et estimer des extensions aux réseaux somme-produit pour la prise de décision dans diverses tâches de diagnostic. Cette présentation sera basée sur les articles suivants:

Han Zhao, Mazen Meliberi, Pascal Poupart, On the Relationship Between Sum-Product Networks and Bayesian Networks, ICML, 2015.

Abdullah Rashwan, Han Zhao and Pascal Poupart, Online and Distributed Bayesian Moment Matching for Parameter Learning in Sum-Product Networks, AISTATS, 2016.

Mazen Melibari, Pascal Poupart and Prashant Doshi, Sum-Product-Max Networks for Tractable Decision Making, IJCAI, 2016

Mazen Melibari, Pascal Poupart, Prashant Doshi, George Trimponias, Dynamic Sum-Product Networks for Tractable Inference on Sequence Data, PGM, 2016.

Priyank Jaini, Abdullah Rashwan, Han Zhao, Yue Liu, Ershad Banijamali, Zhitang Chen and Pascal Poupart, Online Algorithms for Sum-Product Networks with Continuous Variables, PGM, 2016.

Han Zhao and Pascal Poupart, A Unified Approach for Learning the Parameters of Sum-Product Networks, NIPS, 2016.

Biographie: Pascal Poupart is an Associate Professor in the David R. Cheriton School of Computer Science at the University of Waterloo, Waterloo (Canada). He received the B.Sc. in Mathematics and Computer Science at McGill University, Montreal (Canada) in 1998, the M.Sc. in Computer Science at the University of British Columbia, Vancouver (Canada) in 2000 and the Ph.D. in Computer Science at the University of Toronto, Toronto (Canada) in 2005. His research focuses on the development of algorithms for reasoning under uncertainty and machine learning with application to health informatics and natural language processing. He is most well known for his contributions to the development of approximate scalable algorithms for partially observable Markov decision processes (POMDPs) and their applications in assistive technologies, including automated prompting for people with dementia for the task of handwashing. Other notable projects that his research team are currently working on include chatbots for automated personalized conversations and wearable analytics to assess modifiable health risk factors. He co-founded Veedata, a startup that provides analytics services to the insurance industry and the research market. Pascal Poupart received a David R. Cheriton Faculty Award in 2015 and an Early Researcher Award (competitive honor for top Ontario researchers) by the Ontario Ministry of Research and Innovation in 2008. He was also a co-recipient of the Best Paper Award Runner Up at the 2008 Conference on Uncertainty in Artificial Intelligence (UAI) and the IAPR Best Paper Award at the 2007 International Conference on Computer Vision Systems (ICVS). He also serves on the editorial board of the Journal of Machine Learning Research (JMLR) (2009 - present) and the Journal of Artificial Intelligence Research (JAIR) (2008 - 2011). His research collaborators include Huawei, Google, Intel, Kik Interactive, In the Chat, Slyce, HockeyTech, the Alzheimer Association, the UW-Schlegel Research Institute for Aging, Sunnybrook Health Science Centre and the Toronto Rehabilitation Institute.

Note: La présentation sera donnée en français.

Lundi 11 juillet 2016

Variations on the PAC-Bayesian Bound
Pascal Germain
Chercheur postdoctoral, Centre de recherche Inria de Paris.

Heure: 14h00
Local: PLT-3775

Résumé: In the first part of this talk, I will present the main ideas underlying the PAC-Bayesian learning theory - which provides statistical guarantees on the generalization of a weighted majority vote of many classifiers - using a simplified approach. This approach leads to a general theorem that embraces several existing PAC-Bayesian results. Moreover, our proof process eases the "customization" of PAC-Bayesian theorems. In particular, I will show how this result can be extended to the transductive framework, and to theorems where the common Kullback-Leibler divergence (which, in usual PAC-Bayesian theorems, quantifies the "distance" between a prior and a posterior distribution over the voting classifiers) is replaced by the Rényi divergence. In the second part, I will exhibit a strong link between frequentist PAC-Bayesian bounds and the Bayesian marginal likelihood. That is, for the negative log-likelihood loss function, the minimization of PAC-Bayesian generalization bounds maximizes the Bayesian marginal likelihood. This provides an alternative explanation to the Bayesian Occam's razor criteria.

Note: La présentation sera donnée en français.

Lien: diapositives

Jeudi 26 mai 2016

A progress-sensitive flow-sensitive inlined information-flow control monitor
Andrew Bedford
Étudiant au doctorat

Heure: 11h00
Local: PLT-3904

Résumé: We present a novel progress-sensitive, flow-sensitive hybrid information-flow control monitor for an imperative interactive language. Progress-sensitive information-flow control is a strong information security guarantee which ensures that a program's progress (or lack of) does not leak information. Flow-sensitivity means that this strong security guarantee is enforced fairly precisely: we track information flow according to the source of information and not to an a priori given variable security level. We illustrate our approach on an imperative interactive language. Our hybrid monitor is inlined: source programs are translated, by a type-based analysis, into a target language that supports dynamic security levels. A key benefit of this is that the resulting monitored program is amenable to standard optimization techniques such as partial evaluation.

Note: Cette présentation de 30 minutes sera donnée en anglais.

Vendredi 6 mai 2016

Optimisation distribuée via des systèmes multi-agents
Marc-André Carle
Professeur sous octroi adjoint, Département d'opérations et systèmes de décision (FSA)

Heure: 13h30
Local: PLT-3775

Résumé: Au cours de ce séminaire, je présenterai en quoi l'optimisation distribuée constitue une stratégie des plus intéressantes pour résoudre des problèmes d'optimisation de très grande taille. Nous verrons comment CAT (collaborating agent teams), une approche inspirée des systèmes multi-agents, permet de diviser un problème complexe en différentes composantes et les résoudre séparément. Le développement de ce type d'approches devient sans cesse plus facile grâce à l'essor de nouvelles technologies (infonuagique, solveurs génériques). Des exemples d'application seront proposés pour l'optimisation stochastique ainsi que pour le design de chaînes logistiques.

Vendredi 29 avril 2016

Wireless Brain-machine Interfaces for Combined Optogenetics and Multichannel Electrophysiology
Benoît Gosselin
Professeur agrégé, Département génie électrique et génie informatique

Heure: 13h30
Local: PLT-3775

Résumé: Optogenetics is a neural stimulation technique that allows using light to control and monitor individual neurons in living tissue. Such innovative approach provides researchers with a strong tool of crucial importance for brain research and for the development of brain-computer interfaces. Optogenetics has recently been widely used to carry out various neuroscience experiments in freely-behaving rodents, especially mice, which serve as common disease models. As a result, the development of advanced optogenetic hardware combining multiple technologies, such as bioMEMS, optics, microelectronics, and wireless technology has become a source of significant interest. This talk presents advanced systems for enabling combined optogenetics and multichannel electrophysiology in freely moving transgenic rodents. First, we present a wireless headstage with real-time spike detection and data compression that includes 32 neural recording channels and 32 photo-stimulation channels at a wavelength of 465 nm. This system is based on a real time digital signal processor and a Microblaze microprocessor softcore that detects and compresses full action potential waveforms collected from 32 channels in parallel. We present experimental results obtained from simultaneous photo-stimulation and recording performed in-vivo in the somatosensory cortex and the Hippocampus of a ChannelRhodospin (Thy1::ChR2-YFP line4) transgenic mouse. Secondly, we present a fully-integrated, full-duplex transceiver that can interface with very high-density neural optrodes (>500 channels in parallel). It combines an ultra-wideband impulse radio transmitter with a 2.4-GHz narrowband receiver for providing asymmetric data rates above 100 Mbit/s in downlink, and above 500 Mbits/s in uplink over a single implantable antenna, and within a power consumption of 10.4 mW. Finally, we present a smart home-cage system based on arrays of parallel resonators and multicoil inductive links that provides uniform power distribution in 3D to power up small bioinstruments attached or implanted in the body of freely moving animal subjects. This system features a natural power localization mechanism that enables superior efficiency and simplified operation.

Biographie: Benoit Gosselin a obtenu son doctorat en Génie électrique de l'École Polytechnique de Montréal en 2009 et a effectué un stage postdoctoral à Georgia Tech en 2010. Il est présentement professeur agrégé au Départ. de génie électrique et de génie informatique de l'Université Laval où il dirige le Laboratoire de recherche sur les microsystèmes biomédicaux. Ses intérêts de recherche couvrent les microsystèmes sans fil dédiés aux interfaces cerveau-machine, les circuits intégrés analogiques/mixtes et RF pour la neuro-ingénierie, les circuits d'interface pour les capteurs et les actuateurs implantables et les microsystèmes de diagnostique et de soins mobiles. Le Dr Gosselin est Éditeur associé de la revue IEEE Transactions on Biomedical Circuits and Systems et Président-fondateur du Chapitre IEEE CAS/EMB de Québec (Prix du meilleur nouveau Chapitre IEEE, 2015). Il a siégé sur les comités de plusieurs conférences internationales dont IEEE BIOCAS, IEEE NEWCAS, IEEE EMBC/NER, et IEEE ISCAS, et participe présentement à l'organisation de IEEE ISCAS'16 et IEEE NEWCAS'16. Ses recherches consistent, entre autres, à développer des plateformes microélectroniques innovantes pour observer et étudier le cerveau de petits mammifères en temps réel. En plus de récolter plusieurs prix, dont le Prix d'Innovation Mitacs 2015 - Maîtrise et le Prix du meilleur article IEEE BioCAS'15, ses recherches ont mené à la commercialisation de la première plateforme sans fil incorporant l'optogénétique et le monitoring cérébral à grande échèle.

Note: Cette présentation sera donnée en français

Vendredi 22 avril 2016

Adaptation de domaine en apprentissage automatique
Hana Ajakan
Étudiante au doctorat (Graal)

Heure: 13h30
Local: PLT-3775

Résumé: L'adaptation de domaine est un problème d'apprentissage automatique rencontré lorsque la distribution d'apprentissage (appelée domaine source) diffère de la distribution de test (appelée domaine cible). Dans cette présentation, nous allons nous situer dans le cas de l'adaptation de domaine non-supervisé où les données du domaine source sont étiquetées et celles du domaine cible sont non-étiquetées. L'objectif est alors de créer des algorithmes capables d'appliquer les connaissances acquises sur le domaine source à un ou plusieurs nouveaux domaines cibles. Voilà quelques exemples d'applications de l'adaptation de domaine:

- Filtrage de Spams: On voudrait qu'un système de filtrage de Spams performant pour un utilisateur donné (domaine source) soit également bon pour un autre utilisateur recevant des e-mails de natures différentes (domaine cible).

- Analyse de sentiments: On possède deux ensembles de textes critiques concernant des films et des livres où chaque critique de film est accompagnée d'une côte, mais qu'aucune critique de livre ne possède sa côte. À partir de ces données, on désire avoir un modèle capable de prédire la côte d'un livre à partir de sa critique.

Afin de résoudre cette problématique, Nous proposons un algorithme d'apprentissage du type réseau de neurones (qu'on appelle DANN). Notre algorithme trouve une nouvelle représentation des données pour laquelle le réseau de neurones permet de bien classifier les données du domaine source et n'est pas capable de distinguer les données sources des données cibles.

Lors de cette présentation, nous allons commencer par voir comment et quand il est possible d'apprendre un modèle d'apprentissage performant sur le domaine cible, en utilisant seulement les données étiquetées de la distribution source et les données non-étiquetées de la distribution cible. Nous allons aussi voir les grands types d'algorithmes d'adaptation de domaine, les travaux théoriques et enfin nous présenterons notre algorithme DANN.

Lien: diapositives

Vendredi 15 avril 2016

Comprendre la stéréoscopie photométrique extérieure
Yannick Hold-Geoffroy
Étudiant au doctorat (Laboratoire de vision et systèmes numériques)

Heure: 13h30
Local: PLT-3775

Résumé: La stétéoscopie photométrique est une technique de reconstruction 3D analysée en profondeur depuis sa création il y a une trentaine d'année. Elle offre une grande qualité de reconstruction à faible coût, mais elle a été contrainte jusqu'à récemment aux environnements contrôlés en laboratoire. Depuis peu, elle est employée à la reconstruction de scènes extérieures, mais requiert plusieurs centaines de captures étalées sur plusieurs mois pour bien contraindre le problème. Nous présentons une nouvelle analyse permettant de réduire la quantité de captures requises à quelques unes, disséminées pendant une seule journée. Le concept clef pour rendre cette technique utilisable en plein air dans un laps de temps réduit est la compréhension de l'illumination extérieure. En particulier, qu'est-ce qui est important d'observer dans le ciel pour affecter la qualité de la reconstruction? Est-ce que ces événements peuvent survenir en quelques captures au sein d'une même journée? Le développement d'algorithmes de reconstruction à partir des analyses effectuées sera ensuite discuté. L'aboutissement de cette approche permettrait l'emploi du soleil comme scanner 3D.

Vendredi 8 avril 2016

Apprentissage profond: Raisons qui nous ont fait reconsidérer les réseaux de neurones.
Ludovic Trottier
Étudiant au doctorat (Damas)

Heure: 13h30
Local: PLT-3775

Résumé: Au cours des dernières années, les réseaux de neurones profonds ont remporté de nombreuses compétitions en apprentissage automatique, et connaissent actuellement beaucoup de succès en vision numérique et reconnaissance vocale. Leur habileté à construire une représentation hiérarchique à plusieurs couches leur permettent de mieux modéliser les abstractions de haut-niveau contenues dans les observations. Bien que plusieurs entreprises et laboratoires de recherche prennent actuellement le virage "apprentissage profond", les raisons qui expliquent la popularité grandissante de cette nouvelle vague de réseaux de neurones restent obscures. Le terme "deep learning" est souvent caractérisé comme un buzzword, et certains parlent même de rebranding. Au cours de cette présentation, nous examinerons les trois principales avancées théoriques et technologiques entre les années 2006 et 2012 qui ont lancé les réseaux de neurones profonds: (i) l'entraînement non-supervisé vorace, (ii) les fonctions d'activation non-saturées, et (iii) la redécouverte des réseaux à convolution. L'étude de ces développements récents nous permettra de mieux cerner la différence entre les réseaux pré-2006 et ceux d'aujourd'hui, et nous amènera à mieux apprécier le paradigme de l'apprentissage profond.

Lien: diapositives

Vendredi 1er avril 2016

Fast Recursive Tensor Sequential Learning
Ming Hou
Étudiant au doctorat (Damas)

Heure: 13h30
Local: PLT-3775

Résumé: Tensor-variate regression (learning) approaches arise frequently in machine learning community because of the increasing demands to deal with the problems that usually involve large-scale higher-order data with complex structure. Among them, higher-order partial least squares (HOPLS) is the state-of-the-art method for predicting tensor output from tensor input. However, HOPLS is a batch method which is computionally expensive and not suitable for dynamic environments. To this end, we develop a highly efficient sequential learning framework, namely recursive higher-order partial least squares (RHOPLS), that addresses the great challenge posed by the limited storage space and fast processing time allowed by huge high-speed dynamic tensor sequence environments. In conjunction with a fast modification strategy of Tucker model, the extracted factors from the proposed PLS-based framework successfully maximize the pairwise covariance between the whole input and output tensor sequences by recursively incorporating the maximum pairwise covariance between the incremental mini-batch pair into the previous low-rank approximation of model. Unlike batch or multi-pass iterative approaches, which require to access the entire data, RHOPLS conducts a singe-pass blockwise consecutive calculation scheme and thus only a small set of factors are needed to be stored. Our approach is orders of magnitude faster than the batch method while maintaining a comparable predictability. Finally, the effectiveness and efficiency of our method is verified on several real-life applications.

Note: The presentation will be given in English

Vendredi 25 mars 2016

Vendredi Saint (pas de séminaire)

Vendredi 18 mars 2016

Un cadre conceptuel pour la description et la classification des formes de terrain
Éric Guilbert
Professeur adjoint, Département des sciences géomatiques

Heure: 13h30
Local: PLT-3775

Résumé: Une forme de terrain est une partie de terrain reconnaissable à sa forme caractéristique. Bien que les formes de terrain, comme les montagnes ou les vallées, soient facilement reconnaissables par tout un chacun, en donner une définition formelle qui soit implantable est difficile. En effet, les formes de terrain sont souvent définies de manière qualitative par des termes vagues dont l'interprétation dépend du contexte culturel ou de l'expertise de la personne. Nous proposons dans cette présentation un cadre de travail où ces définitions qualitatives sont transformées successivement sur quatre niveaux pour aboutir à une définition formelle implantable. Le premier niveau correspond aux connaissances de l'utilisateur. Le second niveau définit les concepts généraux caractérisant les formes : les formes sont définies par un squelette formé d'éléments saillants du terrain et non pas des indicateurs quantitatifs. Le troisième niveau transforme ces concepts en s'appuyant sur le réseau de surface calculé sur le modèle numérique de terrain. Le dernier niveau est l'implantation dans un système d'information.

Vendredi 11 mars 2016

Apprentissage machine et neuroimagerie
Simon Duchesne
Professeur sous octroi agrégé, Faculté de médecine

Heure: 13h30
Local: PLT-3775

Résumé: Our main contribution to research lie in the extraction of biomarkers of interest useful in the diagnostic of neurodegenerative diseases and prediction of future clinical status in subjects with prodromal disease. Our goal is to contribute to the reduction of diagnostic uncertainty in clinical decision-making, therefore improving patient management. To do so we develop novel and robust methods for the analysis of structural magnetic resonance images (MRI) acquired in multi-centric settings. The central hypothesis underlying our techniques is that neurodegenerative processes exhibit macroscopic morphological changes whose features are detectable and quantifiable on MRI with advanced image processing. Using inductive machine learning techniques, clinically useful diagnostic information is extracted from the data. Now looking for a few good women/men, our current projects relate to the development of ontologies, novel image processing techniques, and classifiers using imaging and non-imaging data.

Lundi 7 mars 2016

Ordonnancement optimal des liens pertinents pour une requête dans un moteur de recherche
Pierre Lecuyer
Chaire de recherche du Canada en simulation et optimisation stochastique

Heure: 13h30
Local: PLT-2341

Résumé: When a keyword-based search query is received by a search engine (SE), a classified ads website, or an online retailer site, the platform has exponentially many choices in how to sort the output to the query. Two extreme rules are (a) to return a ranking based on relevance only, which attracts more requests (customers) in the long run because of perceived quality, and (b) to return a ranking based only on the expected revenue to be generated by immediate conversions, which maximizes short-term revenue. Typically, these two objectives (and the corresponding rankings) differ. A key question then is what middle ground between them should be chosen. We introduce stochastic models that yield elegant solutions for this situation, and we propose effective solution methods to compute a ranking strategy that optimizes long-term revenues. This strategy has a very simple form. The optimal ranking for each query is by decreasing order of a score attributed to each matching link. This score is a linear function of the estimated relevance and the expected revenue of the link, normalized by a function of the estimated link relevance. It contains a single real-valued parameter, which can be optimized via simulation combined with the use of a contraction mapping (or another optimization method).

Note: La présentation sera donnée en français.

Vendredi 4 mars 2016

Semaine de lecture (pas de séminaire)

Vendredi 19 février 2016

Algorithmes de recherche pour la prédiction de séquences en apprentissage automatique
Amélie Roland
Étudiante à la maîtrise (Graal)

Heure: 13h30
Local: PLT-3775

Résumé: La prédiction de séquences est un problème d'apprentissage automatique où l'on cherche à apprendre un prédicteur qui prédit correctement la séquence associée à une entrée. Par exemple, on pourrait vouloir prédire la séquence de caractères contenue dans une image, la séquence de phonèmes représentant la prononciation d'un mot ou la protéine ayant la plus grande affinité de liaison avec une molécule cible. Pour ce faire, l'algorithme d'apprentissage apprend d'abord une fonction qui permet de prédire le score d'une séquence pour une entrée donnée. Une fois cette fonction apprise, l'algorithme doit trouver, pour une entrée donnée, la séquence ayant le score maximal dans cette fonction. Puisque le nombre de séquences possibles est exponentiellement grand, il est souvent trop coûteux de calculer le score pour chacune de ces séquences. Dans ce travail, nous présentons un algorithme permettant d'effectuer cette recherche en temps polynomial pour certains cas. Pour les cas plus complexes, nous présentons des bornes spécialisées pouvant être utilisées avec un algorithme de «Branch and Bound» afin d'effectuer cette recherche efficacement. Enfin, nous présentons des résultats qui se comparent favorablement à l'état de l'art sur des tâches de reconnaissance de mots et de conception de médicaments assistée par ordinateur.

Lien: article

Vendredi 12 février 2016

Suivi du carbone en forêt, et liens structure-fonctions des forêt: une approche utilisant le LiDAR
Martin Béland

Heure: 13h30
Local: PLT-3775

Résumé: La technologie LiDAR représente un potentiel considérable pour mieux comprendre et suivre l'état de nos forêts. Dans le contexte actuel de forte compétition dans le marché forestier, et d'un effet potentiel des changements climatiques sur le fonctionnement des forêts, il est primordial de miser sur ce potentiel. Les systèmes LiDAR considérés ici sont le terrestre et aéroporté; ce dernier permet une couverture cartographique à grande échelle, alors que le premier permet une description détaillée de la structure des canopées forestières. Les deux systèmes sont complémentaires par leur capacité de couverture et niveau de détail. Deux thèmes de recherche utilisant le LiDAR sont abordés dans cette présentation : (1) le suivi du carbone en forêt, et (2) l'étude des liens entre la structure 3D des forêts et leurs fonctions (photosynthèse et évapotranspiration).

Vendredi 5 février 2016

Sythese de mécanismes à quatre barres par optimisation non-convexe
Vincent Goulet
Étudiant à la maîtrise (Laboratoire de programmation par contraintes)

Heure: 13h30
Local: PLT-3775

Résumé: Nous présenterons en quelques points l'optimisation non-convexe pour ensuite aborder une approche développée pour la conception de mécanismes à quatre barres. Un logiciel simple prend une courbe en entrée et retourne un mécanisme capable d'approximer cette courbe. Parmi les éléments clés de cette approche, on compte un modèle utilisant des contraintes quadratiques, ainsi qu'une technique d'échantillonnage basée sur les caractéristiques de la courbe.

Vendredi 29 janvier 2016

Doit-on avoir peur de l'IA ? La réponse est oui à moins que...
Brahim Chaib-draa
Professeur au département d'informatique et de génie logiciel

Heure: 13h30
Local: PLT-3775

Résumé: L'intelligence artificielle (IA) fait couler beaucoup d'encre ces derniers temps. Peut-elle nous surpasser dans les prochaines vingt à cent ans comme le prédisent certains ? Si oui, quelles sont les conséquences pour l'homme ? Peut-elle mettre en péril sa propre existence ? Si elle présente des dangers, que convient-il de faire ? Doit-on commencer à s'alarmer dès maintenant ou attendre et voir ? Dans ma présentation, je tenterai de répondre à ces questions en faisant état de l'intelligence faible et de l'intelligence forte et comment celle-ci risque de poser bien des problèmes si on n'y prend pas garde. Je mettrai en particulier l'accent sur ce qu'on peut faire pour éviter que l'IA nous mène trop loin en particulier : (i) ce qu'on peut faire comme société; (ii) ce qu'on peut imposer comme contraintes externes sur l'éventuel comportement de l'IA; et finalement (iii) comment on pourrait concevoir (via des contraintes internes) une IA sans danger (safe).

Lien: Diapositives

Vendredi 22 janvier 2016

Distribuer des événements dans un horaire cyclique
Émilie Picard-Cantin
Étudiante au doctorat (Laboratoire de programmation par contraintes)

Heure: 13h30
Local: PLT-2744

Résumé: La distribution équilibrée d'événements dans le temps (ou encore d'objets dans l'espace) est un problème qui touche beaucoup de domaines. On peut penser entre autres à la distribution des examens, au positionnement d'équipement dans une usine, ou plus particulièrement dans notre cas, l'espacement de tâches dans un horaire de travail. La présentation portera sur le concept de qualité d'un horaire par rapport à la distribution des tâches et son incorporation dans un modèle mathématique d'optimisation à plusieurs objectifs. Deux modèles mathématiques linéaires seront présentés pour résoudre le problème. Des connaissances de base en optimisation et en mathématiques favoriseront la compréhension de l'exposé mais ne sont pas requises.

Lundi 14 décembre 2015

STEP-archival: Storage Integrity and Tamper Resistance using Data Entanglement
Hugues Mercier (Joint work with Maxime Augier and Arjen Lenstra)

Heure: 10h30
Local: PLT-3904

Résumé: We present STEP-archives, a practical model for censorship-resistant storage systems where an attacker who wants to censor or tamper with data must cause a large amount of obvious collateral damage. MDS erasure codes are used to entangle unrelated data blocks, in addition to providing redundancy against storage failures. We show a trade-off for the attacker between attack complexity, irrecoverability, and collateral damage. We also show that the problem is asymmetric between attackers and defenders: while a defender can efficiently recover from imperfect attacks, an attacker must solve a NP- hard problem to find a perfect (irrecoverable) attack that minimizes collateral damage, or even just approximate this minimum within a reasonable ratio. We then study efficient sample heuristic attack algorithms that lead to irrecoverable but large damage, and demonstrate how some strategies and parameter choices allow to resist these sample attacks. Finally, we provide evidence that it is possible, using archives with constant time read-write operations, to force an attacker who wants to irrecoverably tamper with a document archived long enough to destroy a constant fraction of the archive. Index Terms-Distributed storage, anti-tampering, data integrity, data entanglement, MDS codes.

Biographie: I am maître-assistant for the Institutes of Computer Science and Mathematics at the Université de Neuchâtel in Switzerland. Prior to my appointment in Neuchâtel, I was a postdoctoral research fellow in Electrical and Computer Engineering at McGill University with Professor Fabrice Labeau and a postdoctoral research fellow at the Harvard School of Engineering and Applied Sciences with Professor Vahid Tarokh. I completed my doctoral studies in Electrical Engineering at the University of British Columbia under the supervision of Professor Vijay K. Bhargava. I received the B.Sc. degree in mathematics from Université Laval, and the M.Sc. degree in computer science from the Université de Montréal. I was born and raised in Québec, Canada. Outside of work, I enjoy running, anything played with a racket, any activity that can be done on snow, playing bridge, and spending time with my daughters.

Vendredi 20 novembre 2015

Routage géométrique dans les triangulations de Delaunay (2ième partie)
Jean-Lou De Carufel
Professeur à l'Université d'Ottawa

Heure: 10h30
Local: PLT-2704

Résumé: Savoir se déplacer efficacement dans un réseau est un problème fondamental en informatique et dans la vie de tous les jours. Par réseau (ou graphe), on entend un ensemble de points (noeuds ou sommets) reliés par des arêtes. Par exemple, la carte routière du Québec est un réseau où chaque ville est un noeud et chaque route est une arête. On retrouve plusieurs exemples de réseaux au quotidien: cartes routières, internet, le réseau des antennes cellulaires, etc. Dans cet exposé, nous nous concentrerons sur les réseaux géométriques, c'est-à-dire les réseaux qui sont plongés dans le plan ou dans l'espace. Étant donné deux noeuds s et t dans un réseau, le routage consiste à trouver un chemin de s vers t. Il existe plusieurs mesures de coût des algorithmes de routage. Nous nous intéresserons particulièrement au ratio de routage ("routing ratio"). On dit qu'un algorithme de routage admet un ratio de routage de c si l'algorithme nous fait parcourir un chemin de longueur au plus c|st| pour se déplacer de s vers t (où |st| représente la distance euclidienne entre s et t). Le routage est local si l'information disponible à chaque noeud ne concerne que le noeud lui-même et ses voisins directs. Nous discuterons des algorithmes de routage dans les triangulations en général. Nous étudierons le cas particulier des triangulations de Delaunay pour lesquelles il existe un algorithme de routage local avec un ratio de routage de 5,9. Nous discuterons aussi des liens entre ratio de routage et mémoire disponible.

Vendredi 13 novembre 2015

Jeux de policiers et de voleurs stochastiques
Frédéric Simard
Étudiant à la maîtrise en informatique

Heure: 10h30
Local: PLT-2704

Résumé: Les jeux de policiers-voleurs sont étudiés depuis longtemps en théorie des graphes et décrivent de manière générale un jeu dans lequel un ou plusieurs policiers tentent de capturer un certain nombre de voleurs. Dans cette présentation, on montre que l'étude de ces jeux peut avoir des applications concrètes. En effet, dans un article présenté récemment, il a été démontré qu'il est possible d'accélérer la résolution du problème de retrouver un objet caché sur un graphe à l'aide d'un jeu de policier-voleur. D'un autre côté, il est coutume que chaque jeu de policiers-voleurs soit formulé puis résolu de manière unique. Ainsi, on présentera aussi un modèle permettant d'encoder l'ensemble des jeux de policiers-voleurs et de tous les résoudre avec une même équation.

Vendredi 6 novembre 2015

Contrôle, localisation et interaction humaine avec un performeur plus léger que l'air
David St-Onge, ing. M.Sc.
Candidat au doctorat en génie mécanique à l'Université Laval, Laboratoire de robotique

Heure: 10h30
Local: PLT-2704

Résumé: Depuis plus de 3 ans, le professeur Philippe Giguère dirige un projet de recherche interuniversitaire portant sur le contrôle d'un dirigeable cubique autonome et son interaction dans des contextes artistiques avec des performeurs et le public. Un des prototypes de ces aérobots sera en fonction dans le hall du Pavillon Vachon la semaine du 9 au 15 novembre. Profitant de cette occasion, le coordonnateur technique et co-créateur du projet, David St-Onge, présentera le contexte particulier de cette plateforme de recherche ainsi que les derniers développements faits par les divers groupes de recherche.

Vendredi 9 octobre 2015

Apprentissage profond pour lire et "comprendre" le langage
Alexandre Lacoste
Ingénieur en logiciels, Google

Heure: 14h00
Local: PLT-2700

Résumé: L'apprentissage profond (deep learning) gagne en popularité et permet de résoudre des tâches de plus en plus complexes par le billet de l'apprentissage automatique. Dans cette présentation, je ferai une revu de l'apprentissage automatique et présenterai pourquoi l'apprentissage profond est une approche efficace. Finalement, je présenterai différentes architectures pour apprendre à lire des textes et parlerai des mécanismes d'attention.

Lundi 27 avril 2015

Optimal and Information Theoretic Syntactic Pattern Recognition
John Oommen
Chancellor's Professor; Fellow: IEEE; Fellow: IAPR; Carleton University
Adjunct Professor, University of Agder, Grimstad, Norway

Heure: 13h30
Local: PLT-2704

Résumé: In this talk we show how we can achieve Information Theoretic Optimal Syntactic Pattern Recognition for arbitrary systems. We do this by presenting a new model for noisy channels which permits arbitrarily distributed substitution, deletion and insertion errors. Apart from its straightforward applications in string generation and recognition, the model also has potential applications in speech and uni-dimensional signal processing. The model, which is specified in terms of a noisy string generation technique, is functionally complete and stochastically consistent.

Apart from presenting the channel we also specify a technique by which Pr[Y|U], the probability of receiving Y given that U was transmitted, can be computed in cubic time. This procedure involves dynamic programming, and is to our knowledge, among the few non-trivial applications of dynamic programming which evaluate quantities involving relatively complex combinatorial expressions and which simultaneously maintain rigid probability consistency constraints.

Biographie: Dr. John Oommen was born in Coonoor, India on September 9, 1953. He obtained his B.Tech. degree from the Indian Institute of Technology, Madras, India in 1975. He obtained his M.E. from the Indian Institute of Science in Bangalore, India in 1977. He then went on for his M.S. and Ph. D. which he obtained from Purdue University, in West Lafayettte, Indiana in 1979 and 1982 respectively. He joined the School of Computer Science at Carleton University in Ottawa, Canada, in the 1981-82 academic year. He is still at Carleton and holds the rank of a Full Professor. Since July 2006, he has been awarded the honorary rank of Chancellor's Professor, which is a lifetime award from Carleton University. His research interests include Automata Learning, Adaptive Data Structures, Statistical and Syntactic Pattern Recognition, Stochastic Algorithms and Partitioning Algorithms. He is the author of more than 415 refereed journal and conference publications, and is a Fellow of the IEEE and a Fellow of the IAPR. Dr. Oommen has also served on the Editorial Board of the IEEE Transactions on Systems, Man and Cybernetics, and Pattern Recognition.

Note: Cette présentation sera donnée en anglais.

Vendredi 24 avril 2015

Apprentissage de modèles parcimonieux à partir de génomes complets avec application à la résistance aux antibiotiques
Alexandre Drouin
Étudiant au doctorat au GRAAL

Heure: 11h30
Local: PLT-2704

Résumé: La diminution des coûts associés au séquençage d'ADN permet de faire des études à grandes échelles avec un flot constant de données génomiques. Ces données peuvent être analysées, dans le contexte d'études cas-témoin, en vue de déterminer les variations génétiques qui sont associées à un état biologique. Nous nous intéressons au problème d'apprentissage de modèles permettant de prédire l'occurence d'un état biologique chez un individu à partir de son génome complet, de la partie codante (exome) ou exprimée (transcriptome). Ce problème engendre son lot de défis, tant au niveau de la représentation des données, qu'au niveau computationnel. De plus, afin de contribuer à la compréhension des mécanismes biologiques sous-jacents, ces modèles doivent être interprétables par les experts du domaine. Nous cherchons donc des modèles qui sont parcimonieux et qui ont une structure propice à l'interprétation. Notre approche s'appuie sur une représentation de type "bag-of-words" des génomes et sur l'algorithme du Set Covering Machine. Nous présentons un exemple d'application à la prédiction de la résistance aux antibiotiques de 4 pathogènes humains importants.

Lien: diapositives

Vendredi 17 avril 2015

Distributions de probabilités sur l'espace des graphes orientés acycliques : une approche Bayésienne nonparamétrique
Patrick Dallaire
Étudiant au doctorat au DAMAS

Heure: 11h30
Local: PLT-2704

Résumé: L'apprentissage Bayésien requiert la spécification d'une distribution de probabilités a priori sur l'espace qui doit faire l'objet d'apprentissage, lequel pourrait être les paramètres d'un modèle de régression par exemple. Il existe des distributions de probabilités pour plusieurs types d'objets, tel que les réels (Gaussienne), les entiers positifs (Poisson), les distributions discrètes finies (Dirichlet), les matrices de covariances (Inverse Wishart), etc. Pour notre part, nous nous intéressons à l'apprentissage de graphes orientés acycliques. L'approche Bayésienne classique (paramétrique) à ce problème d'apprentissage consiste à définir le prior sur un espace fini de graphes, ce qui peut s'avérer contraignant pour certains problèmes. L'approche Bayésienne nonparamétrique, qui est plus flexible, repose quant à elle sur l'utilisation de distributions a priori sur des espaces dont le nombre de dimensions est infini, ce qui correspond dans notre cas à des graphes infinis. Il n'existe actuellement aucune distribution de probabilité ayant pour support l'entièreté de l'espace des graphes orientés acycliques infinis. Nous présenterons notre récente construction d'une telle distribution et discuterons de son application à l'apprentissage de structures.

Vendredi 10 avril 2015

Learning to represent relations
Roland Memisevic
Professeur à l'Université de Montréal

Heure: 11h30
Local: PLT-2704

Résumé: Many tasks in computer vision become easy, once images are encoded using the right kind of representation. Deep learning is an approach to image recognition and related tasks that attempts to learn the right representation along with any other system parameters from data. The approach has been highly successful recently, yielding break-through performance in problems like object, face, and activity recognition. After providing a brief overview of feature learning and deep learning, I will describe what is missing in my opinion in terms of extending deep learning beyond recognition, towards more general computer vision, and potentially towards more general AI. I will argue that the capability to represent relations, rather than "things", is what is needed to solve many tasks in vision and AI with a single kind of model. I will also describe how to encode relations in deep learning models, and I will demonstrate some of our recent work on training systems to perform depth inference, motion estimation and analogy-making.

Note: La présentation sera donnée en français

Vendredi 3 avril 2015

Vendredi Saint (pas de séminaire)

Vendredi 27 mars 2015

Bio-informatique des systèmes appliquée à la neuroscience. Du neurone au réseau
Simon Hardy
Professeur au département d'informatique et de génie logiciel

Heure: 13h00
Local: PLT-2704

Résumé: La bio-informatique des systèmes est un domaine multidisciplinaire qui exploite la puissance computationnelle et les analyses systémiques pour formuler et solutionner des problématiques biologiques complexes. Cette complexité peut être de deux natures : une complexité d'échelle ou une complexité dynamique. Dans mon groupe, nous utilisons la modélisation et la simulation pour étudier la complexité dynamique en collaboration avec les biologistes. Lors de cette présentation, je présenterai deux projets en cours en neurosciences et nos résultats préliminaires.

Note: Heure inhabituelle!

Lien: diapositives

Vendredi 20 mars 2015

Sélection de modèle sous la contrainte de la confidentialité différentielle
Anne-Sophie Charest
Professeure au département de mathématiques et de statistique

Heure: 13h30
Local: PLT-2704

Résumé: Toute organisation qui souhaite partager des données ou résultats d'analyses statistiques doit s'assurer de respecter la promesse de confidentialité offerte aux individus ou entreprises sur lesquels les données ont été collectées. Ce n'est pas une tâche facile, surtout avec l'augmentation rapide de la quantité d'informations personnelles disponibles facilement. La confidentialité différentielle est un critère rigoureux pour mesurer la protection de la confidentialité offerte par un mécanisme de divulgation de données ou de résultats statistiques. Après avoir établi les bases du problème de protection de la confidentialité, je décrirai en détails le critère de confidentialité différentielle. Je présenterai ensuite mes travaux récents sur la sélection de modèle sous la contrainte de la confidentialité différentielle.

Note: Heure inhabituelle!

Vendredi 13 mars 2015

Robot Learning: Algorithms and Applications
Abdeslam Boularias
Chercheur postdoctoral (Robotics Institute of Carnegie Mellon University)

Heure: 11h30
Local: PLT-2704

Résumé: Robot learning is a research area at the intersection of machine learning and robotics. The question driving research in this area is: How can a robot learn from data to perform complex tasks? Machine learning provides powerful tools for solving problems in robotics that, due to their complexity, cannot be addressed solely by engineering. Object recognition is a prime example of a robot vision problem that can hardly be solved without any learning. Grasping and manipulating unknown objects is another type of a robotic task that is difficult to solve by hand-coding. Robotics also provides researchers in machine learning with interesting new challenges. For instance, the field of reinforcement learning has been deeply influenced by problems that typically arise in robotics, such as partial observability. Another example is learning by demonstration, which is a particular type of supervised learning that is specific to robotics.

My talk will focus on problems in machine learning that originate from robotics. In particular, I will present challenging problems related to reinforcement learning and to learning by demonstration. I will show how these problems can be solved by formulating them as optimization problems, derived from a higher principle such as entropy minimization. I will also show how the proposed algorithms were used to solve problems in robotics.

Note: Cette présentation sera donnée en français.

Lien: diapositives

Vendredi 6 mars 2015

Semaine de lecture (pas de séminaire)

Vendredi 27 février 2015

Meilleures régressions quantiles grâce aux réseaux de neurones
Adam Salvail
Étudiant au doctorat à l'Université de Sherbrooke

Heure: 11h30
Local: PLT-2704

Résumé: Supposons que nous ayons un phénomène mesurable (ex.: la température qu'il fera demain), et que nous souhaitons prédire cette valeur en n'utilisant que l'information présentement disponible (ex.: température actuelle, vents, etc.). Pour y arriver, nous utilisons un outil, appeler régression, qui tente de modéliser le phénomène à l'étude et de faire une prédiction la plus précise possible. En général, nous voulons que le modèle puisse nous donner l'espérance de la valeur à prédire, c'est-à-dire la valeur qui minimise la différence au carré entre notre prédiction et la réalité. Or, cette prédiction ne donne aucune information sur la certitude du modèle concernant la valeur prédite!

Une autre possibilité intéressante est la régression quantile. Plutôt que de tenter de prédire l'espérance de la valeur recherchée, nous nous intéressons à prédire, par exemple, les quartiles de la distribution dont provient la valeur. De cette façon, il est plus facile de se faire une idée de la confiance que le modèle accorde à sa prédiction.

Cette présentation montre comment effectuer cette régression quantile à l'aide de réseaux de neurones, une méthode plus puissante que la régression quantile linéaire généralement utilisée.

Lien: diapositives

Vendredi 20 février 2015

A progress-sensitive flow-sensitive inlined information-flow control monitor
Andrew Bedford
Étudiant au doctorat au LSFM

Heure: 11h30
Local: PLT-2704

Résumé: We increasingly rely on computer systems to safeguard confidential information, and maintain the integrity of critical data and operations. But in our highly interconnected world, these trusted systems often need to communicate with untrusted parties. Trusted systems risk leaking confidential information to untrusted parties, or allowing input from untrusted parties to corrupt data or the operation of the trusted system.

Information-flow control is a promising approach that enable trusted systems to interact with untrusted parties, providing fine-grained application-specific control of confidential and untrusted information. Static mechanisms for information-flow control analyse a program before execution to determine whether the program's execution will satisfy the appropriate information flow requirements. This has low runtime overhead, but accepts or rejects a program in its entirety. Dynamic mechanisms accept or reject individual executions at runtime, without performing any static program analysis. Dynamic mechanisms can incur significant runtime overheads. Hybrid information-flow control techniques combine static and dynamic program analysis and strive to achieve the benefits of both static and dynamic approaches: precise (i.e., per-execution) enforcement of security, with low runtime overhead.

After introducing the concept of information-flow control (what? why? how?), I will present a progress-sensitive, flow-sensitive hybrid information-flow control monitor for an imperative interactive language.

Note: La présentation sera donnée en français.

Lien: diapositives

Vendredi 13 février 2015

Un algorithme d'apprentissage parcimonieux maximisant le désaccord
Jean-Francis Roy

Heure: 13h00
Local: PLT-2704

Résumé: En apprentissage automatique, ou plus précisément lors de la résolution d'un problème de classification, un algorithme d'apprentissage a pour tâche de prédire la catégorie d'un nouvel élément observé après avoir été entraîné sur un ensemble d'éléments déjà classifiés. Les applications sont multiples : on pourrait par exemple s'intéresser à prédire si oui ou non un client s'intéressera à un produit en fonction de ses achats antérieurs, ou bien déterminer si un courriel est un «spam» ou non à partir de son contenu. Plusieurs algorithmes d'apprentissage retournent la fonction de décision apprise sous la forme d'un vote de majorité pondéré de «votants» de base. Il est commun en pratique d'observer des votes de majorité dont la performance est très bonne, alors que les votants sont individuellement très peu performants. Nous présenterons une borne sur le risque du classificateur par vote de majorité expliquant ce phénomène en introduisant non seulement la performance individuelle des votants, mais aussi la corrélation de leurs erreurs (leur désaccord). Nous présenterons un programme quadratique nommé MinCq qui minimise directement cette borne, dont la performance est égale à l'état de l'art. Un désavantage de cette approche est que le vote de majorité obtenu est «dense», et donc difficile à interpréter par un être humain. Nous présenterons comment utiliser la dualité de Lagrange et la technique d'optimisation nommée «génération de colonnes» pour obtenir une nouvelle version de MinCq. L'algorithme résultant, nommé CqBoost, est plus performant que les autres algorithmes obtenus par génération de colonnes, et retourne un vote de majorité parcimonieux plus facile à interpréter par un humain.

Note: Heure inhabituelle!

Lien: diapositives

Vendredi 6 février 2015

Replanifier les opérations de production en minimisant les perturbations
Thierry Moisan

Heure: 11h30
Local: PLT-2704

Résumé: Dans un contexte de production manufacturière, il est courant d'avoir en main un plan de production prêt à être appliqué prochainement. Si une nouvelle commande arrive à la dernière minute, il peut être difficile de l'incorporer à ce plan sans le changer. Dans ce type de situation, l'approche typique est de replanifier l'ensemble de la production pour y inclure cette nouvelle demande. De plus, les commandes déjà garanties aux clients doivent demeurer dans le plan de production. Pour ce faire, les commandes garanties sont forcées dans cette replanification. Cette approche a l'inconvénient de créer un plan de production qui peut être radicalement différent du plan original. Cela peut créer des problèmes si son exécution a déjà débuté ou si des tâches préalables doivent être effectuées. Dans le contexte de l'industrie du bois, à l'étape de rabotage, le choix de la famille de bois traitée à chaque période a une grande influence sur la planification des opérations. Si des familles de bois différentes sont traitées dans deux quarts de travail subséquents, un changement de configuration de la machinerie doit être effectué entre ces quarts de travail. Ces changements de configurations sont coûteux en temps et financièrement, car des employés supplémentaires doivent être assignés à cette tâche. Si le plan de production change de façon drastique, la planification de ces changements de configuration doit aussi être modifiée ce qui perturbe l'ensemble des opérations. Afin de résoudre cette problématique, nous travaillons au développement d'outils de planification qui permettent de satisfaire les commandes tout en minimisant les différences entre l'ancien plan de production et le nouveau (c.-à-d. en minimisant les perturbations). Pour ce faire, nous modifions les modèles d'optimisation mathématique pour les inciter à produire des plans de production semblables aux précédents.

Lien: diapositives

Vendredi 30 janvier 2015

Analyse des études génétiques familiales : établir le lien variants rares - maladie et intégrer l'expression des gènes
Alexandre Bureau

Heure: 11h30
Local: PLT-2704

Résumé: Les échantillons familiaux présentent d'importants avantages pour étudier les variants génétiques impliqués dans les maladies complexes. Dans un premier volet, j'expliquerai comment l'observation du partage de variants génétiques rares par des malades apparentés peut servir à lier ces variants à la maladie étudiée. Je présenterai des expressions pour calculer des probabilités exactes de partage de variants génétiques rare parmi des sujets apparentés, et leur implantation dans un module pour l'environnement statistique R. Cette approche sera comparée à des alternatives impliquant un groupe témoin de la population. Dans un deuxième volet, je présenterai la problématique d'intégrer des mesures d'expression des gènes dans une analyse d'association entre une maladie et des variants génétiques fréquents, en soulignant les difficultés posées par la structure familiale. Une approche prometteuse qui pourrait être étendue au contexte des études familiales sera présentée.

Biographie: Professeur au département de médecine sociale et préventive. Voir sa page personnelle et son profil de recherche.

Lien: diapositives

Vendredi 23 janvier 2015

Un réseau de neurones pour l'adaptation de domaine
Pascal Germain

Heure: 11h30
Local: PLT-2704

Résumé: L'apprentissage automatique s'intéresse à la création de programmes qui apprennent à effectuer une tâche par l'observation d'exemples. En pratique, un algorithme d'apprentissage entraîne un classificateur par l'étude d'une série d'éléments déjà classés (par exemple, des textes de critiques de films associés à une cote de 1 à 5 étoiles). Ensuite, on utilise le classificateur obtenu afin de connaître la classe d'un nouvel élément (on demande au classificateur de prédire la cote que donnera un utilisateur à un film en se basant sur le texte de sa critique). Plus spécifiquement, le problème d'adaptation de domaine consiste à entraîner un classificateur sur une distribution de données source qui diffère (plus ou moins légèrement) de la distribution des données cible sur laquelle le classificateur devra effectuer une prédiction. Voici un exemple d'un tel problème: on possède deux ensembles de textes critiques concernant des films (le domaine source) et des livres (le domaine cible). Chaque critique de film est accompagnée d'une cote, mais on ne possède pas la cote associée aux critiques de livres. À partir de ces données, on désire entraîner un classificateur à prédire la cote d'un livre à partir de sa critique. Lors de l'apprentissage, il faudra non seulement minimiser l'erreur sur la classification de livres, mais aussi "s'adapter" à la tâche de classification de films. Les travaux présentés se basent sur une théorie de l'adaptation de domaine qui affirme qu'une famille de classificateurs permet de s'adapter au domaine cible si elle: (1) permet de bien classifier le domaine source; et (2) n'est pas capable de distinguer les exemples sources des exemples cibles. Nous intégrons cette idée à un algorithme d'apprentissage du type réseau de neurones. Notre algorithme trouve une nouvelle représentation des exemples d'apprentissage pour laquelle le réseau de neurones possède les caractériques (1) et (2).

Lien: diapositives

Vendredi 16 janvier 2015

Compréhension phonétique du texte écrit
Richard Khoury

Heure: 11h30
Local: PLT-2704

Résumé: Cette présentation détaille le développement de deux algorithmes de compréhension phonétique du texte écrit. Étant donné un nouveau mot, l'objectif de ces algorithmes est de déterminer la prononciation approximative. Le premier algorithme utilise une approche probabiliste, et le second utilise un ensemble de règles de décision. Deux domaines d'applications sont également présentés, soit la normalisation de mots mal épelés dans les microtexts envoyés par cellulaire, Facebook, Twitter et autre, et l'analyse de la littérature médiévale.

Lien: diapositives

Vendredi 14 novembre 2014

Routage géométrique dans les triangulations de Delaunay
Jean-Lou De Carufel

Heure: 13h30
Local: PLT-2700

Résumé: Un robot se déplace dans la ville de Québec à la recherche du campus de l'Université Laval. Il connaît les coordonnées GPS du campus, mais il n'a pas accès à la carte de la ville. Lorsqu'il se trouve à une intersection, il ne voit que les intersections adjacentes. De plus, le robot est sans mémoire: lorsqu'il arrive à une intersection, il oublie tout ce qui s'est passé au préalable. (Il ne retient que les coordonnées de l'université.) Notre objectif est de construire un algorithme de routage qui minimise la distance que le robot doit marcher pour atteindre sa destination. Lorsqu'un réseau est plongé dans le plan ou dans l'espace, il satisfait certaines propriétés géométriques qui peuvent être mises à profit pour concevoir des algorithmes de routage efficaces. Nous étudierons le cas des triangulations de Delaunay. Supposons qu'au départ la distance euclidienne entre le robot et sa destination est de D. Le meilleur algorithme connu jusqu'à tout récemment pour faire du routage sur les triangulations de Delaunay construisait un chemin de longueur 45 D. Nous présenterons un algorithme de routage qui mène à un chemin de longueur 15 D. De plus, nous expliquerons comment nous pensons être capable d'abaisser la longueur du chemin à moins de 6 D.

Vendredi 14 novembre 2014

Flips
Prosenjit Bose

Heure: 14h30
Local: PLT-2700

Résumé: We review results concerning edge flips in triangulations concentrating mainly on various aspects of the following question: Given two different triangulations of the same size, how many edge flips are necessary and sufficient to transform one triangulation into the other? We focus both on the combinatorial perspective (where only a combinatorial embedding of the graph is specified) and the geometric perspective (where the graph is embedded in the plane, vertices are points and edges are straight-line segments). We highlight some of the techniques used to prove the main results and mention a few of the challenges remaining in this area.

Note: Cette présentation sera donnée en français.

Lundi 22 septembre 2014

The Neural Autoregressive Distribution Estimator
Hugo Larochelle

Heure: 14h30
Local: PLT-2505

Résumé: The problem of estimating the distribution of multivariate data is one of the most general problems addressed by machine learning research. Good models of multivariate distributions can be used to extract meaningful features from unlabeled data, to provide a good prior over some output space in a structured prediction task (e.g. image denoising) or to provide regularization cues to a supervised model (e.g. a neural network classifier).

The most successful distribution/density models are usually based on graphical models, that represent the joint distribution p(x) of observations x using latent variables that explain the statistical structure within x. Mixture models are a well known example and rely on a latent representation with mutually exclusive components. For high dimensional data however, models that rely on a distributed representation, i.e. a representation where components can vary separately, are usually preferred. These include the very successful restricted Boltzmann machine (RBM) model. However, unlike mixture models, the RBM is not a tractable distribution estimator, in the sense that computing the probability of observations p(x) can only be computed up to a multiplicative constant and must be approximated.

In this talk, I'll describe the Neural Autoregressive Distribution Estimator (NADE), which combines the tractability of mixture models with the modeling power of the RBM, by relying on distributed representations. The main idea in NADE is to use the probability product rule to decompose the joint distribution p(x) into the sequential product of its conditionals, and model all these conditionals using a single neural network.

Note: Cette présentation sera donnée en français.

Vendredi 30 mai 2014

Applying Data Mining to Real-life Crime Investigation
Benjamin Fung

Heure: 13h00
Local: PLT-3775

Résumé: Data mining has demonstrated a lot of success in many domains, from direct marking to bioinformatics. Yet, limited research has been conducted to leverage the power of data mining in real-life crime investigation. In this presentation, I will discuss two data mining methods for crime investigation. The first method aims at identifying the true author of a given anonymous e-mail. The second method is a subject-based search engine that can help investigators to retrieve criminal information from a large collection of textual documents.

Biographie: Dr. Benjamin Fung is an Associate Professor of Information Studies (SIS) at McGill University and a Research Scientist in the National Cyber-Forensics and Training Alliance Canada (NCFTA Canada). He received a Ph.D. degree in computing science from Simon Fraser University in 2007. Dr. Fung collaborates closely with the national defense, law enforcement, and healthcare sectors. He has over 70 refereed publications that span across the prestigious research forums of data mining, privacy protection, cyber forensics, services computing, and building engineering. His data mining works in crime investigation and authorship analysis have been reported by media worldwide. Before pursuing his academic career, he worked at SAP Business Objects for four years. He is a licensed professional engineer in software engineering.

Note: Cette présentation sera donnée en anglais.

Lien: Page web

Vendredi 16 mai 2014

Robotique mobile et cartographie 3D dans un monde en mouvement
François Pomerleau

Heure: 13h00
Local: PLT-3775

Résumé: La robotique mobile a pour mission de créer des robots capables d'opérer de façon autonome dans des environnements complexes et divers. La première partie de la présentation a pour but de donner une vue d'ensemble sur la diversité des types de déplacements avec des exemples de robots, développés à Zurich, fonctionnant sous l'eau, sur l'eau, sur le sol et dans l'air. La deuxième partie focalisera sur deux exemples de plateformes utilisées sur le terrain et présentera quelques résultats reliés aux tâches 1) de surveillance d'algues toxiques en milieux pre-alpin et alpin et 2) de navigation en environnements urbains hautement dynamiques.

Biographie: François Pomerleau a commencé ses premières implications en recherche supervisée par l'agence spatiale canadienne et européenne lors de ses études en génie informatique à l'Université de Sherbrooke. Il a obtenu sa maîtrise de la même université en 2009 après un séjour d'un an à l'EPFL (Lausanne - Suisse). Il a complété son doctorat à l'ETH Zurich (Suisse) en 2013 durant lequel il a participé à plusieurs déploiements robotiques en environnements non contrôlés. Il est présentement chercheur postdoctoral à l'Université Laval dans le groupe de recherche de Philippe Giguère. Ses intérêts de recherches incluent la reconstruction 3D d'environnements basée sur les données laser, les activités de recherches et sauvetage, la planification de trajectoires et la méthodologie scientifique appliquée à la robotique.

Vendredi 25 avril 2014

Big Data, a statistician's perspective
Arthur Charpentier, professeur au département de mathématiques à l'UQAM

Heure: 13h00
Local: PLT-3775

Résumé: In this talk, I will get back on the "Big Data revolution". Big data is "high volume", "high velocity", and/or "high variety information assets" that require new forms of processing to enable enhanced decision making. Thus, this is a challenge for statisticians. As claimed by Alan Mitchell, "Big data is all about statistics: divining patterns and trends from large data sets. Statistics are incredibly powerful and useful for the way they challenge the assumptions and inferences naturally made by human minds - many of them faulty. As I said, that's great". I will discuss the epistemological challenge of big data, and the impact on statistical modeling. Several examples will also be discussed, based on some experiences in finance, insurance, and sports analytics.

Note: Cette présentation de sera donnée en français.

Liens: Freakonometrics, présentation

Vendredi 18 avril 2014

Vendredi Saint (pas de séminaire)

Vendredi 11 avril 2014

Balance : Une famille de contraintes
Émilie Picard-Cantin

Heure: 13h00
Local: PLT-3775

Résumé: Le balancement des charges de travail entre employés dans un horaire de travail et la répartition équilibrée des heures de cours dans l'horaire d'un étudiant sont de bons exemples de la nécessité d'une contrainte de balancement efficace en programmation par contraintes. Il existe déjà dans la littérature la contrainte Balance ayant pour objectif d'équilibrer des affectations. Nous avons montré que d'obtenir la cohérence de domaine sur cette contrainte est NP-difficle. C'est pourquoi nous proposons une nouvelle famille de contraintes. Pour chaque nouvelle contrainte, nous proposons une décomposition simple à encoder à l'aide d'un solveur standard. Nous proposons aussi un algorithme spécialisé de filtrage pour l'une de ces contraintes qui établit la cohérence de domaine en temps polynomial.

Lien: présentation

Vendredi 4 avril 2014

Point and shoot sky probes
Jean-François Lalonde

Heure: 13h00
Local: PLT-3775

Résumé: Image-based lighting has allowed the creation of photo-realistic computer-generated content. However, it requires specially designed calibration targets such as mirrored sphere or custom hardware, which may not be available to an average camera user. In this paper, we present an approach to directly estimate an HDR sky probe from a single LDR photograph of an outdoor scene shot with a consumer camera, without specialized calibration target or equipment. Our insight is that outdoor scenes contain several objects which can act as natural calibration targets. In this paper, we use LDR photographs of three such objects: landmarks, skies, and faces. To estimate the HDR sky probes from such objects, we propose a novel dataset of HDR sky probes, and employ it to learn the structure of outdoor illumination and its relationship to intensity variations across photographs of these objects. We use the learnt mapping to estimate sky probes directly from the LDR photographs, and show results of relighting objects inserted into them.

Note: Cette présentation sera donnée en français.

Vendredi 28 mars 2014

Le Cloud Computing : modèle et évaluation de performances
Valérie-Danielle Justafort

Heure: 13h00
Local: PLT-3775

Résumé: Depuis plusieurs années, nous assistons à l'essor d'un nouveau paradigme, le Cloud Computing. Ce dernier fait référence à l'utilisation de mémoires et de capacités d'énormes centres de traitement appelés Datacenters, dans le but de faciliter le stockage et le traitement d'un grand volume de données. Ces datacenters, essentiellement constitués de serveurs interconnectés et distants, peuvent être regroupés pour former un InterCloud, où les clients peuvent rapidement dimensionner des machines virtuelles (VMs) et y installer les applications voulues. Toutefois, malgré ces nombreux avantages, la gestion et le fonctionnement d'une telle infrastructure nécessitent de grandes quantités d'énergies électriques, ce qui, non seulement, entraîne des coûts d'opérations largement supérieurs aux coûts d'investissements, mais est également à l'origine d'émission de grandes quantités de gaz à effet de serre (GES) et particulièrement du CO2.

Dans cette présentation, nous adressons le problème de placement des VMs dans un InterCloud de manière à réduire l'empreinte carbone du système. Plus précisément, nous proposons un nouveau modèle de formulation mathématique qui se base sur la programmation en nombres entiers mixtes (MIP) pour minimiser l'impact environnemental d'un tel système. Plusieurs simulations ont montré que le modèle proposé permet d'obtenir des configurations optimales avec une empreinte carbone minimale à l'échelle de l'InterCloud.

Lien: présentation

Vendredi 21 mars 2014

Prédiction du mouvement humain au moyen d'un modèle dynamique basé sur les processus gaussiens
Yali Wang

Heure: 13h00
Local: PLT-3775

Résumé: La prédiction du mouvement humain est un défi pour la tâche de vision par ordinateur. Tout d'abord, les données relatives à ce mouvement sont généralement de hautes dimensions. Ensuite, les mouvements plus complexes sont souvent multi-modaux. Dans ce contexte, un modèle dynamique basé sur les processus gaussiens (GPDM) a été proposé pour le suivi du mouvement humain [J. M. Wang, D. J. Fleet and A. Hertzmann, NIPS 2005]. Dans GPDM, les processus gaussien (GPS) sont utilisés pour construire le modèle à la fois au niveau des transitions et au niveau de la vraisemblance. Dès lors, les états latents et les hyper-paramètres peuvent être efficacement tirés de la forme fermée au niveau du postérieur en utilisant une forme de gradient pour l'optimisation. Dans cette présentation, je me concentrerai principalement sur ce modèle GPDM, et je proposerai quelques extensions possibles.

Note: Cette présentation sera donnée en anglais.

Lien: présentation

Vendredi 14 mars 2014

Algorithmes de filtrage pour des problèmes d'ordonnancement disjonctif
Hamed Fahimi

Heure: 13h00
Local: PLT-3775

Résumé: La programmation par contraintes permet de résoudre de nombreux problèmes d'optimisation combinatoire, dont les problèmes d'ordonnancement de tâches. Ces problèmes consistent à déterminer dans quel ordre et à quel moment les tâches doivent être exécutées afin que les temps de sortie, les échéances et les temps de traitements de chaque tâche soient respectés. De plus, nous cherchons souvent à minimiser le « makespan », c'est-à-dire le moment de complétion de la dernière tâche. Les solveurs de contraintes procèdent à une exploration systématique de toutes les solutions candidates au problème. Afin d'accélérer le processus de recherche, des algorithmes de filtrage permettent d'éliminer des solutions partielles qui ne peuvent être complétées en solutions complètes. Nous présentons de nouveaux algorithmes de filtrage pour des problèmes d'ordonnancement.

Note: Cette présentation sera donnée en anglais

Lien: présentation

Vendredi 28 février 2014

Towards a Regression using Tensors
Hou Ming

Heure: 13h00
Local: PLT-3775

Résumé: Nowadays, more and more data of interest such as colored images and videos admits a natural tensorial representation. On one hand, the data represented by high order tensor promises to improve the generalization of machine learning problem by incorporating some structural prior information. On the other hand, such structured representation also poses great challenges for many classical machine learning problems including regression.

In this presentation, I will focus on the class of regression problems where the independent predictors take the form of tensor representation, namely, tensor regression. In contrast to classical regression approaches, the new problem bring the new challenges mainly in two aspects. First, the ultrahigh dimensionality of tensor input results in gigantic number of parameters; Furthermore, the complex multi-way structure embedding in the tensorial data is difficult to capture.

To deal with these challenges, I will briefly talk about the linear tensor regression by exploiting the well-studied tensor decomposition approaches. I will also talk about some typical regularization techniques tailored to tensorial format in order to improve the predictability of the regression model.

Note: Cette présentation sera donnée en anglais.

Lien: présentation

Vendredi 21 février 2014

Parallel Discrepancy-Based Search
Thierry Moisan

Heure: 13h00
Local: PLT-3775

Résumé: Les stratégies de recherche basées sur le calcul de divergences se sont démontrées très utiles pour résoudre des problèmes combinatoires de grande taille. Elles démontrent de très bonnes performances lorsqu'elles sont utilisées en combinaison avec des heuristiques de branchement spécifiques au domaine du problème à résoudre (heuristique de choix de variable et de valeur). De telles heuristiques existent pour de nombreux problèmes industriels. Nous proposons une nouvelle approche, Parallel Limited Discrepancy-depth based Search (PLDS), qui permet de paralléliser une stratégie de recherche basée sur les divergences. L'ensemble de processeurs visite les feuilles de l'arbre de recherche exactement dans le même ordre que le ferait l'algorithme centralisé. Cela est fait en assignant implicitement un seul processeur à chaque feuille de l'arbre de recherche. Cette implémentation permet un équilibre naturel de la charge de travail. En effet, il est possible de borner théoriquement les changements de la charge de travail entre les processeurs lorsqu'un filtrage est effectué sur le domaine des variables. De plus, aucune communication n'existe entre les processeurs. Les propriétés de PLDS en font un algorithme qui peut être déployé sur des superordinateurs massivement parallèles comprenant plusieurs milliers de processeurs, tels que Colosse de l'Université Laval.

Nous avons appliqué cet algorithme à des problèmes industriels de rabotage du bois grâce à des jeux de données provenant de compagnies forestières québécoises. Cela nous a permis d'obtenir des solutions de meilleure qualité que les meilleures connues jusqu'à maintenant.

Note: Thierry a remporté le prix du meilleur article à CP 2013.

Liens: présentation , article

Vendredi 14 février 2014

Introduction aux algorithmes MapReduce
Mathieu Dumoulin

Heure: 13h00
Local: PLT-3775

Résumé: Le monde du big data prend de plus en plus de place dans l'actualité technologique. La plate-forme distribuée Hadoop est au coeur de ce mouvement. Hadoop a récemment fait son entrée à l'Université Laval, étant maintenant disponible sur Colosse (en test).

Au-delà du « hype », il y a bien une classe de problèmes qui justifient d'utiliser Hadoop. Lorsque confronté à un tel problème, il devient nécessaire de formuler une solution au problème pour qu'elle puisse fonctionner sur Hadoop. Hadoop est basé sur le modèle de programmation fonctionnel MapReduce. Comment formuler une solution MapReduce? À quoi ressemble un algorithme MapReduce au-delà de l'omniprésent WordCount?

Afin de répondre à ce genre de questions, je vais présenter MapReduce d'un point de vue algorithmique. J'entends aller plus en profondeur que les nombreuses "introductions à Hadoop" pour bien expliquer comment un algorithme peut être formulé "façon MapReduce". Divers algorithmes seront vus comme le tri, le calcul de moyenne et des algorithmes de graphes comme PageRank.

Aucune connaissance préalable de Hadoop ou MapReduce ne sera nécessaire. Ce ne sera pas une présentation Hadoop mais bien sur l'algorithme MapReduce.

Lien: presentation

Vendredi 7 février 2014

Algorithmes d'apprentissage et bornes sur le risque pour l'approche de la régression à la prédiction de structures
Mario Marchand

Heure: 13h00
Local: PLT-3775

Résumé: Nous présentons des garanties rigoureuses sur l'approche de la régression à la prédiction de sorties structurées. Nous montrons que le risque quadratique (de régression) borne supérieurement le risque de prédiction lorsque le noyau de sortie vérifie certaines conditions relativement au risque de prédiction. Nous proposons deux bornes sur le risque de prédiction qui dépendent du risque empirique quadratique. Le minimiseur de la première borne se trouve à être le prédicteur proposé par Cortes et al (2007). Le minimiseur de la deuxième borne est un prédicteur proposé pour la première fois. Ces deux prédicteurs sont comparés sur la reconnaissance de mots manuscrits et la classification hiérarchique d'enzymes.

Lien: présentation

Vendredi 31 janvier 2014

Un algorithme hybride pour la planification de chemins couvrants avec capteurs imparfaits
Michael Morin

Heure: 13h00
Local: PLT-3775

Résumé: Nous nous intéressons aux problèmes de couverture avec capteurs imparfaits dans le contexte des opérations de déminage robotisées. Dans le problème étudié, un véhicule autonome sous-marin (AUV) équipé d'un sonar balaye le fond marin à la recherche de mines. Dans notre formalisme, le fond marin est discrétisé par une grille uniforme de cellules carrées et un nombre constant de cellules est balayé par le capteur de chaque côté du robot au fil de ses mouvements. La probabilité de détecter une mine lors du balayage d'une cellule distante est fonction de deux paramètres : la distance entre la position du robot et la cellule balayée ainsi que le type de fond marin de la cellule balayée. L'objectif est de trouver le chemin de longueur minimale avec le moins de virages possible atteignant la couverture minimale requise dans chacune des cellules (définie en termes de probabilité de détection). Nous proposons un algorithme hybride basé sur la programmation dynamique qui utilise une réduction vers le problème du voyageur de commerce (TSP). Par nos résultats expérimentaux, nous démontrons l'efficacité de l'algorithme en termes de qualité de la solution et de temps de calcul par rapport aux résultats précédemment publiés rendant ainsi l'algorithme utilisable dans un contexte pratique.

Liens: article, présentation

Vendredi 24 janvier 2014

Une approche hybride combinant analyse statique et dynamique pour l'application de la politique de flot d'information sécuritaire
Andrew Bedford, Josée Desharnais, Théophane Gloria Godonou et Nadia Tawbi

Heure: 13h00
Local: PLT-3775

Résumé: Cette présentation porte sur une approche d'application de politiques de sécurité utilisant une analyse multi-valuée basée sur un système de types. Cette analyse est suivie d'une instrumentation lorsque nécessaire. Le langage cible est un langage impératif. Notre approche vise à réduire les faux positifs générés par une analyse statique, et à réduire la surcharge d'exécution en n'instrumentant que lorsque nécessaire. Les faux-positifs surviennent dans l'analyse statique de systèmes informatiques lorsqu'il est impossible ou difficile de décider, souvent à cause d'une information manquante, par exemple le nom d'un fichier, et par conséquent, son niveau de sécurité. L'idée principale de notre approche est de distinguer les réponses négatives des réponses incertaines. Au lieu de rejeter les commandes potentiellement non sécuritaires, elles sont identifiées et étiquetées pour la seconde phase de l'analyse. Les réponses négatives et positives sont traitées comme cela se fait d'habitude. Pour augmenter la précision de l,analyse nous avons opté pour une analyse est sensible au flot. Ainsi, une variable a le niveau de sécurité de l'information qu'elle contient. Seules les sources et les cibles d'information, les canaux, ont des niveaux de sécurité fixés a priori. Le résultat est une analyse hybride d'application de politique de sécurité : les points potentiellement sécuritaires du programme détectés par notre analyse par typage sont instrumentés par la suite avec des tests dynamiques. Cela garantit moins de faux positifs et moins de surcharge à l'exécution.

Liens: présentation , article

Vendredi 13 décembre 2013

Dynamique de la Topologie de l'Internet. Outil de Mesure et analyse préliminaire
Frédéric Tounwendyam Ouédraogo, Université de Koudougou, Burkina Faso

Heure: 10h00
Local: PLT-2548

Résumé: Le réseau Internet est une structure de grande taille qui évolue très rapidement ce qui rend complexe l'étude de la dynamique de sa topologie. Nous proposons de se focaliser sur ce qu'une machine peut observer de cette topologie, appellé vue ego-centrée. En faisant des mesures périodiques de vues ego-centrées, que nous apellons mesures radar, nous pouvons observer la dynamique de l'Internet. Nous avons conçu et implémenté un outil de mesure ego-centrée appelé tracetree qui fait des mesures de type radar. A l'aide de cet outil, nous avons conduit plusieurs mesures à partir d'une centaine de machines et obtenu des données. Les premières analyses des données ont permis de montrer des propriétés importantes de la dynamique de l'Internet.

Biographie: Frédéric Ouédraogo a obtenu un doctorat en informatique à l'Université Pierre et Marie Curie (Paris 6), en 2009. Il a publié plusieurs articles dans des conférences et des revues internationales. Depuis 2006, il enseigne à l'Université de Koudougou et y occupe maintenant un poste permanent. En plus de son enseignement et de sa recherche, il intervient dans la mise en place des technologies d'information et de communication sur le campus de l'université.

Vendredi 22 novembre 2013

Formal Probabilistic Analysis using Theorem Proving
Dr. Sofiene Tahar, Professor & Tier 1 Research Chair, ECE Department, Concordia University

Heure: 10h00
Local: PLT-3904

Résumé: Probabilistic analysis is a tool of fundamental importance to virtually all scientists and engineers as they often have to deal with systems that exhibit random or unpredictable elements. Traditionally, computer simulation techniques are used to perform probabilistic analysis. However, they provide less accurate results and cannot handle large-scale problems due to their enormous computer processing time requirements. To overcome these limitations, we propose to perform formal probabilistic and statistical analysis using higher-order logic theorem proving. We provide a framework for the formalization of both discrete and continuous random variables and the ability to formally verify system's probabilistic and statistical properties. The analysis carried out in this way is free from any approximation or precision issues due to the mathematical nature of the models and the inherent soundness of the theorem proving approach. In order to illustrate the practical effectiveness of the proposed framework, we present the probabilistic analysis of four examples across four application areas: the Coupon Collector's problem (software), the Stop-and-Wait protocol (telecommunications), the reliability of memory arrays (microelectronics), and floating-point error analysis (computer hardware).

Biographie: Sofiene Tahar is Professor in the Department of Electrical and Computer Engineering at Concordia University, Montreal, Quebec, Canada. He received his PhD in Computer Science in 1994 from the University of Karlsruhe and his Diploma in Computer Engineering in 1990 from the University of Darmstadt. Prof. Tahar has made contributions and published papers in the areas of formal hardware verification, microprocessor and system-on-chip verification, analog and mixed signal circuits verification, VLSI design automation, and formal probabilistic, statistical and reliability analysis of systems. Prof. Tahar is founder and director of the Hardware Verification Group. Since 2007 he is holding a Senior Research Chair in Formal Verification of System-on-Chip.

Vendredi 27 septembre 2013

On Geometric Spanners
Prosenjit Bose, School of Computer Science, Carleton University

Heure: 13h30
Local: PLT-3904

Résumé: A geometric graph G is a graph whose vertices are points in the plane and whose edges are line segments weighted by the Euclidean distance between their endpoints. Geometric graphs are often used to model different networks such as road networks, or communication networks. An important property to strive for in a network is connectivity. The most connected network is the compete network where every pair of points is connected. However, this is problematic since connecting every pair of points is expensive and results in too many connections. As such, to address this, one tries to build networks that approximate the complete network. What does it mean to approximate? This brings us to the notion of a t-spanner.

In this setting, a t-spanner of G is a spanning subgraph G' with the property that for every pair of vertices x, y, the shortest path from x to y in G' has weight at most t times the shortest path from x to y in G. The parameter t is commonly referred to as the spanning ratio, or the stretch factor. In addition to having bounded spanning ratio, it is desireable to build t-spanners that possess other properties, such as bounded degree, low weight, small spanning ratio, planarity, high connectivity and/or fault-tolerance to name a few. Notice that many of these properties are competing in the sense that achieving them simultaneously is not possible. In this talk, we review various results on how to build spanners.

Note: Cette présentation sera donnée en français avec support visuel en anglais.

Vendredi 27 septembre 2013

Chercher à l'aveuglette
Jean-Lou De Carufel, School of Computer Science, Carleton University

Heure: 12h30
Local: PLT-3904

Résumé: Le titre est une traduction volontairement maladroite du problème intitulé "Searching on a Line". Dans ce problème, un robot se déplace sur une droite à la recherche d'un objet déposé à un endroit inconnu. Pour trouver l'objet, le robot doit passer par le point où se trouve cet objet. Quelle est la stratégie optimale pour le robot ?

Supposons qu'au départ, la distance entre le robot et l'objet est de D. Dans ce type de problèmes de recherche, on utilise habituellement D comme unité de mesure. Par exemple, si le robot connaît D, sa stratégie optimale coûte 3D en pire cas. En effet, dans le pire des cas, il parcourt D en s'éloignant de l'objet, revient à son point de départ puis se rend jusqu'à l'objet dans le sens opposé. (On suppose que le robot est capable d'évaluer les distances.)

Si le robot ne connaît pas D, on peut montrer que sa stratégie optimale coûte 9D en pire cas [Baeza-Yates et al., 1993]. Si on ne connaît pas D, mais qu'on connaît une borne supérieure sur D, quelle est la stratégie optimale ? Nous ferons un survol des résultats les plus récents à propos de ce dernier problème. Nous expliquerons aussi comment ces résultats permettent de concevoir des algorithmes de routage dans des graphes plus complexes qu'une droite.

Vendredi 26 avril 2013

Apprentissage de structure de modèle graphique probabiliste avec des graphes dirigés acycliques infinis
Patrick Dallaire

Heure: 12h00
Local: PLT-3775

Résumé: L'une des tâches fondamentales de l'apprentissage automatique est de découvrir de la structure dans les données, un processus pouvant s'avérer difficile. Lorsqu'il est question de modèles graphiques, ce processus pourrait être d'apprendre la structure de dépendance entre les variables aléatoires pour ensuite la décrire sous forme de graphe. Nous nous intéresserons à un processus stochastique définissant une distribution de probabilité dans l'espace des graphes dirigés acycliques, lequel peut être utilisé dans un cadre bayésien à des fins d'apprentissage de structure. L'un des avantages de ce processus est qu'il permet de considérer des structures ayant un nombre illimité de variables cachées, et ce, tout en pénalisant la complexité du modèle. Le processus stochastique en question est une extension du processus du buffet indien en cascade dont le support ne se limite plus uniquement à des structures stratifiées, mais permet aux connexions d'outrepasser plusieurs couches pour en rejoindre une autre. Les performances du processus étendu ont été évaluées sur des problèmes d'estimation de densité à plusieurs variables et montre que notre approche est capable d'apprendre des fonctions de densités reposant sur des structures plus simple.

Lien: Présentation

Vendredi 19 avril 2013

Quelles politiques de sécurités sont applicables par les Moniteurs?
Raphaël Khoury

Heure: 12h00
Local: PLT-3775

Résumé: Le monitorage (runtime monitoring) est une méthode bien établie pour assurer la sûreté du code et la littérature sur le sujet fait état de plusieurs implémentations de moniteurs. Ceux-ci diffèrent cependant quant aux politiques de sécurité qu'ils sont capables d'appliquer. Dans cette présentation, j'examine la question de déterminer exactement quelles politiques de sécurité peuvent être appliquées par les moniteurs. Il s'agit des politiques pour lesquelles un moniteur qui opère sous certaines contraintes peut assurer qu'une violation ne se produit pas tout au long de l'exécution du programme. Cette question, en apparence simple, n'admet pas une réponse aisée et a été le sujet de plusieurs études académiques. Pourtant, la question de déterminer dans quel contexte une politique de sécurité donnée est applicable est centrale à la sélection et même la conception des mécanismes d'application. J'examine les différentes réponses qui ont été suggérées à cet égard et j'identifie les problèmes qui demeurent sans réponse dans la littérature.

Liens: article, présentation

Vendredi 12 avril 2013

Clustering and Non-negative Matrix Factorization
Mohammad Sajjad Ghaemi

Heure: 12h00
Local: PLT-3775

Résumé: In recent years, clustering has become a progressively important research topic in the machine learning field, pattern recognition area and several different disciplines such as data mining, bioinformatics, computer vision, page ranking, social network, etc. In this presentation I am going to talk about preliminary definition of cluster, conventional existing approaches that extract the clusters from the data with an emphasis on the Non-negative Matrix Factorization (NMF) as a new advancement in recent years to both clustering problem and dimension reduction task. NMF has been investigated and applied for various purposes especially for high-dimensional data with elements containing non-negative values. The ultimate goal of the NMF is to provide a non-negative low-rank approximation of the original data. Directly imposing the non-negativity constraints on both factors and reconstruction co-efficients results in finding a lower rank approximation of the data that is often more meaningful and interpretable than other similar low-rank estimations such as SVD with even lesser reconstruction error. In other words, due to the NP-hardness of the clustering analysis as a discrete optimization problem, NMF based low-rank approximation gives a relaxation for clustering with equivalent variants to K-means family and spectral clustering.

Note: Cette présentation sera donnée en anglais.

Lien: Présentation

Vendredi 5 avril 2013

L'adaptation de domaine en apprentissage automatique: introduction et approche PAC-bayesienne
Pascal Germain

Heure: 12h00
Local: PLT-3775

Résumé: En apprentissage automatique, le problème d'adaptation de domaine consiste à entraîner un classificateur sur une distribution de données qui diffère (plus ou moins légèrement) de la distribution des données sur laquelle le classificateur devra effectuer une prédiction. Voici un exemple d'un tel problème: on possède deux ensembles de textes critiques concernant des livres et des films. Chaque critique de livre est accompagnée d'une appréciation (une côte numérique), mais on ne possède pas l'appréciation associée aux critiques de films. À partir de ces données, on désire entraîner un classificateur à prédire l'appréciation d'un film à partir de sa critique. Lors de l'apprentissage, il faudra non seulement minimiser l'erreur sur la classification de livres, mais aussi "s'adapter" à la tâche de classification de film. Pour ce faire, il faut analyser la divergence entre les distributions de critiques de livres et de critiques de films. Lors de la présentation, j'introduirai une analyse de l'adaptation de domaines inspirée de la théorie PAC-Bayésienne et je présenterai un algorithme d'apprentissage que nous avons développé à partir de cette analyse théorique.

Lien: Présentation

Vendredi 29 mars 2013

Vendredi saint (congé)

Vendredi 22 mars 2013

Comparaison d'algorithmes d'apprentissage et combinaison de modèles, une approche Bayesienne
Alexandre Lacoste

Heure: 12h00
Local: PLT-3775

Résumé: Bien que le théorème du « no free lunch » nous indique que l'algorithme d'apprentissage optimal soit une utopie, nous proposons une approche pour déterminer si un algorithme est meilleur qu'on autre dans un contexte donné. Ceci est possible, car le théorème du « no free lunch » suppose une distribution uniforme sur toutes les tâches possibles. Dans notre approche, nous faisons autrement en supposant que les jeux de données observés proviennent d'une distribution quelconque sur l'ensemble des tâches. Avec uniquement cette supposition et quelques données de test, nous pouvons répondre de manière probabiliste à la question suivante : « Est-ce que l'algorithme A produira plus fréquemment un meilleur classificateur que l'algorithme B dans le contexte donné? » En appliquant cette même idée sur la validation croisée, nous obtenons une distribution a posteriori sur les différents hyperparamètres. À l'aide de ce postérieur, il nous est possible de faire de la marginalisation de modèles pour améliorer notre performance de généralisation. Plusieurs tests empiriques montrent que cette combinaison de modèles apporte un gain significatif et systématique.

Lien: présentation

Vendredi 15 mars 2013

Semaine de lecture

Vendredi 8 mars 2013

La planification d'horaires de ligues sportives par programmation par contraintes
Gilles Pesant, École polytechnique de Montréal

Heure: 12h00
Local: PLT-3775

Résumé: Le sport professionnel soulève les passions populaires et anime de nombreux secteurs de l'économie. Un facteur méconnu du succès d'une ligue sportive est la planification du calendrier des matchs. Au-delà d'une structure combinatoire assez rigide, des considérations diverses font qu'il est difficile de produire un calendrier optimal (et souvent même d'exprimer ce qu'on doit optimiser) ou parfois simplement de trouver un calendrier respectant les différentes restrictions. On doit par exemple considérer l'équité entre les horaires individuels des équipes, la montée d'un suspense de fin de saison, les conflits potentiels avec l'horaire d'autres compétitions, l'intérêt suscité par certains matchs pour les revenus de diffusion et la sécurité des partisans lors de matchs à forte rivalité.

La programmation par contraintes est une approche de représentation et de résolution de problèmes combinatoires qui est particulièrement bien adaptée au contexte des horaires de ligues sportives. Elle exploite les structures combinatoires d'un problème, exprimées sous la forme de contraintes, pour restreindre dynamiquement l'espace de recherche d'une solution et pour guider cette recherche. Or notre problème regorge de telles structures.

Deux exemples, le premier étant une abstraction et le second très concret, serviront à illustrer la complexité du domaine et comment on peut produire de bons calendriers avec la programmation par contraintes.

Lien: présentation

Vendredi 1er mars 2013

Assemblage de novo distribué de génomes avec Ray et RayPlatform: des graphes de Bruijn aux polytopes
Sébastien Boisvert

Heure: 12h00
Local: PLT-3775

Résumé: Deux concepts intéressants - la granularité et le passage de messages - permettent d'architecturer des systèmes distribués pour l'analyse de données, les cadriciels, ou encore la visualisation dans les nuages. Un système distribué est strictement composé de composantes orthogonales et indépendantes. La composition peut se faire à la construction ou à l'utilisation. Les composantes de ces systèmes distribués peuvent être liées par différents graphes. Les modules d'extension par dessus un coeur sont souvent liés dans un arbre. Les données génétiques peuvent être liées dans un graphe de Bruijn. Et les 4096 processus d'un calcul distribué peut être liés par la surface d'un polytope régulier convexe. Dans cette présentation, les graphes présents dans les systèmes Ray, RayPlatform, et Ray Cloud Browser seront présentés. L'importance de la granularité des opérations ainsi que le passage de messages entre les composantes sera soulignée.

Liens: présentation , article, article, démo, code

Vendredi 22 février 2013

Modeling the data manifold with autoencoders and unnormalized probability density models
Pascal Vincent, Université de Montréal

Heure: 12h00
Local: PLT-3775

Résumé: The manifold hypothesis, according to which real-world high dimensional data likely concentrates near a lower dimensional non-linear manifold embedded in high dimensional input space, brings a fruitful geometric perspective to the problem of learning meaningful representations. It naturally arises from our intuitive notion of continuous underlying factors (e.g. pose and color parameters of an object in an image) that we would like to uncover. It also has the seductive potential to reduce the curse of dimensionality to a more manageable size. In this presentation I will explain my view on the best angle of attack for modeling data that is believed to have such a manifold support structure and how it has evolved, form simple local non-parametric approaches, to implicit modeling of tangent spaces with regularized autoencoders and energy-based models. I will also showcase how tangent space information extracted from such models can be leveraged e.g. to build better classifiers. From a geometric interpretation of familiar single layer representations as realizing manifold modeling through a patchwork of local linear tangent spaces, I will discuss the strengths, limits and potential of such representations in the quest towards building yet more meaning-carrying high-level ones. Finally I will propose modifications to established training criteria to explicitly incorporate a manifold inductive bias.

Biographie: Pascal Vincent est professeur agrégé au Département d'Informatique et de Recherche Opérationnelle de l'Université de Montréal. Son domaine de recherche est l'apprentissage machine. Depuis 2011, il est également membre associé du Canadian Institute for Advanced Research (CIfAR), dans le programme Neural Computation and Adaptive Perception. Pascal Vincent est diplômé d'une grande école d'ingénieurs Française (ESIEE Paris, 1996), et a complété un doctorat en informatique à l'Université de Montréal en 2004. Il a aussi eu l'occasion de travailler dans des laboratoires de recherche industriels renommés (Bell Labs, AT&T Labs Research, Microsoft Research), et a co-fondé et co-dirigé une entreprise dans le domaine du data-mining. Son principal intérêt de recherche actuel est la découverte de principes et d'algorithmes qui, à partir de données représentant des perceptions sensorielles brutes, permettent de construire, couche par couche et de façon autonome, à la manière des réseaux de neurones du cerveau, des représentations de plus haut niveau porteuses de sens. Cela correspond à modéliser la structure de la réalité observée en y découvrant des régularités statistiques complexes.

Note: Cette présentation sera donnée en français.

Lien: présentation

Vendredi 15 février 2013

Programmation par contraintes pour la planification de chemins sous incertitude: résoudre le problème du chemin de recherche optimal
Michael Morin

Heure: 12h00
Local: PLT-3775

Résumé: Le problème de chemin de recherche optimal (de l'anglais Optimal Search Path problem) est un problème de détection issu de la théorie de la recherche où la position et la détectabilité d'un objet mobile sont incertaines. Une solution à ce problème NP-difficile est un chemin sur les sommets d'un graphe visant à maximiser la probabilité de trouver l'objet. La connaissance sur la position de l'objet est représentée par une distribution de probabilité sur les sommets du graphe et varie dans le temps en fonction de son modèle de déplacement Markovien et des observations antérieures du ou des chercheurs. Nous présentons deux modèles de programmation par contraintes développés pour le cas à un seul chercheur ainsi qu'une nouvelle heuristique de branchement performante basée sur la probabilité totale de détection. Le problème de l'OSP est particulièrement intéressant en ce qu'il généralise plusieurs problèmes de recherche probabiliste tels que la détection d'intrusions, l'identification de code malveillant dans les réseaux distribués, la recherche sauvetage et la surveillance.

Liens: article, présentation

Vendredi 8 février 2013

Learning a peptide-protein binding affinity predictor with kernel ridge regression
Sébastien Giguère

Heure: 12h00
Local: PLT-3775

Résumé: We propose a specialized string kernel for small bio-molecules, peptides and pseudo-sequences of binding interfaces. The kernel incorporates physico-chemical properties of amino acids and elegantly generalize eight kernels, such as the Oligo, the Weighted Degree, the Blended Spectrum, and the Radial Basis Function. We provide a low complexity dynamic programming algorithm for the exact computation of the kernel and a linear time algorithm for it's approximation. Combined with kernel ridge regression and SupCK, a novel binding pocket kernel, the proposed kernel yields biologically relevant and good prediction accuracy on the PepX database. For the first time, a machine learning predictor is capable of accurately predicting the binding affinity of any peptide to any protein. The method was also applied to both single-target and pan-specific Major Histocompatibility Complex class II benchmark datasets and three Quantitative Structure Affinity Model benchmark datasets. On all benchmarks, our method significantly (p-value < 0.057) outperforms the current state-of-the-art methods at predicting peptide-protein binding affinities. The proposed approach is flexible and can be applied to predict any quantitative biological activity. The method should be of value to a large segment of the research community with the potential to accelerate peptide-based drug and vaccine development.

Note: La présentation sera en français. Aucune connaissance en biologie, en biochimie ou en immunologie n'est requise pour comprendre la présentation, je présenterai tous les concepts nécessaire à la compréhension de nos travaux. Il s'agit de la méthode qui nous a mérité le premier prix lors du 2nd Machine Learning Competition in Immunology 2012.

Liens: article, présentation

Vendredi 1er février 2013

I see you, you see me: Cooperative Localization through Bearing-Only Mutually Observing Robots
Philippe Giguère

Heure: 12h00
Local: PLT-3775

Résumé: Plusieurs environnements ne permettent pas l'utilisation de signaux GPS pour la localisation : milieu sous-marin, à l'intérieur d'édifices ou tout simplement sur d'autres planètes. La localisation coopérative, qui se base sur l'estimation des positions relatives entre les membres d'un essaim de robots mobiles, est l'une des approches proposées pour faciliter la localisation globale de ces membres. Ce séminaire propose une nouvelle approche de localisation relative, basée sur l'utilisation de marqueurs lumineux et d'une caméra par robot. Cette technique peu coûteuse nécessite deux conditions essentielles : la prise synchronisée de photos, et l'observation mutuelle des robots et de leur caméra. Le séminaire présentera la solution géométrique analytique pour le problème minimal en 2D, comprenant une paire de robots. Au passage seront introduits certains principes de base de la localisation par caméra. Des comparaisons avec des méthodes classiques de localisation (caméras stéréo, utilisation d'une seule caméra et de nombreux marqueurs, capteurs lasers) seront présentées, ainsi que la validation expérimentale sur du matériel. Finalement, l'ébauche de la solution en 3D sera abordée.

Liens: article, présentation