Université de

Faculté des arts et des sciences

Département d'informatique et de recherche opérationnelle

  

COLLOQUES du DIRO
Hiver 2008

Responsable:  Pierre McKenzie

Salle 6214, Pavillon André-Aisenstadt, Université de Montréal

Sauf exception mentionnée explicitement ci-dessous, nos colloques ont lieu les jeudis à 15h30 à la salle 6214.

Historique des colloques du DIRO                                 Prochain colloque prévu :  19 juin (salle 3195)

L'imagerie mentale pour penser en maths/informatique ?

Alain Finkel
ENS Cachan, France

Le jeudi 19 juin 2008 : 15h30, salle (attention!) 3195, pavillon André-Aisenstadt


Si la nature profonde de la pensée est encore un mystère (et le sera peut-être toujours), les processus mentaux qui permettent l'imagerie mentale ont été intensivement étudiés par les philosophes (par exemple, Berkeley 1734, Bergson 1900), par les psychologues entre 1850 et 1900 (par exemple, Binet, Tichener) et à nouveau depuis 1970 par beaucoup de scientifiques de différentes disciplines (par exemple, Kosslyn, Shepard).

L'imagerie mentale est la capacité que nous avons de créer un monde interne et de le manipuler, mémoriser, simuler, anticiper,...etc. Cette recréation utilise des processus mentaux de type différents  comme les processus visuo-spatiaux, verbaux et symboliques, phonologiques, de type ressenti.

Les processus de l'imagerie mentale sont encore largement méconnus par les enseignants (et même par les psychologues !). Pourtant, enseigner consiste, de fait, à faire découvrir, transmettre, co-créer des objets mentaux et à expliquer comment les manipuler efficacement.

Nous illustrerons sur des exemples choisis dans le domaine des maths et/ou de l'informatique les différentes représentations possibles d'une même notion ou preuve.

Bibliographie (sur le web):
http://www.lireimage.uqam.ca/mod1/chap/ch6.htm
http://lecerveau.mcgill.ca/
http://www.lsv.ens-cachan.fr/~finkel/ja2008.html
http://www.science.uva.nl/~seop/entries/mental-imagery/bibliography-mental-imagery.html
http://plato.stanford.edu/entries/mental-imagery/index.html#EarGreIdeIma
http://plato.stanford.edu/entries/mental-representation/



Le jeudi 28 février 2008 : conférencier Yoshua Bengio, DIRO:   Bébé IA: de l'humain à la machine

Le jeudi 24 avril 2008 : conférencier Harry Mairson , Brandeis University:   Linear Logic and the Complexity of Control Flow Analysis

Le jeudi 8 mail 2008 : conférencier Douglas Eck , DIRO:   Autotagger: an algorithm for automatically tagging music collections using large-scale data mining and supervised machine learning

Bébé IA: de l'humain à la machine

Yoshua Bengio
DIRO

Le jeudi 28 février 2008 : 15h30, salle habituelle, 6214

Quels sont les principes de traitement de l'information qui permettent aux humains d'agir de façon intelligente?  Est-ce que ces principes peuvent être utilisés pour faire avancer la recherche en intelligence artificielle  (IA)?  Malgré plus d'un demi-siècle d'efforts, l'IA semble encore bien loin,  pourquoi?  La capacité de comprendre la réalité qui nous entoure à partir de notre expérience individuelle serait une des clés de l'intelligence  humaine et animale. Cette clé passe par la capacité à s'adapter et à généraliser à de nouvelles situations, par opposition à l'apprentissage par coeur.  La recherche en apprentissage machine a beaucoup progressé dans la compréhension mathématique de la notion de généralisation, et a donné lieu à de nouvelles technologies d'analyse statistique dont les applicationsindustrielles et scientifiques sont multiples. Mais d'autres problèmes  fondamentaux de nature informatique et mathématique continuent à nous  narguer. Nous parlerons de travaux en IA s'inspirant de la manière dont les  humains réussissent peut-être à contourner ces difficultés. Nous  esquisserons ainsi certains principes qui émergent de recherches récentes et aussi plus anciennes et qui nous semblent essentiels, tels que les  représentations distribuées et la profondeur de circuit pour obtenir la  compositionalité et empêcher l'explosion combinatoire du fléau de la dimensionalité. Nous parlerons aussi des recherches en cours pour faire face à un problème d'optimisation fondamentalement difficile, pour entraîner des architectures profondes ayant le potentiel de représenter efficacement des abstractions de haut niveau. Pour y arriver nous voulons entraîner un bébé IA à comprendre d'abord des concepts simples avant de s'attaquer à des concepts plus complexes qui sont construits par dessus les concepts plus simples.


Linear Logic and the Complexity of Control Flow Analysis

Harry Mairson
BRANDEIS UNIVERSITY

Le jeudi 24 avril 2008 : 15h30, salle (attention!) 3195, pavillon André-Aisenstadt

Control flow analysis (CFA) is a kind of static program analysis performed by compilers, where the answers to questions like "can call site X ever call procedure P?" or "can procedure P ever be called with argument A?" can be used to optimize code output by the compiler.  Such questions can be answered exactly by Girard's geometry of interaction (GoI), but in the interest of efficiency and time-bounded computation, control flow analysis computes a crude approximation to GoI, possibly including false positives. 

Different versions of CFA are parameterized by their sensitivity to calling contexts, as represented by a contour--- a sequence of k labels representing these contexts, analogous to Lévy's labelled lambda calculus.  CFA with larger contours is designed to make the approximation more precise.  A naive calculation shows that 0CFA (i.e., with k=0) can be solved in polynomial time, and kCFA (k>0, a constant) can be solved in exponential time.  We show that these bounds are tight, namely, that the decision problem for 0CFA is PTIME-hard, and for kCFA is EXPTIME-hard.  Each proof depends on fundamental insights about the linearity of programs.  In both the linear and nonlinear case, contrasting simulations of the linear logic exponential are used in the analysis.  The key idea is to take the approximation mechanism inherent in CFA, and exploit its crudeness to do real computation.

This is joint work with David Van Horn (Brandeis University).

Autotagger: an algorithm for automatically tagging music collections using large-scale data mining and supervised machine learning.

Douglas Eck
DIRO

Le jeudi 8 mai 2008 : 15h30, salle (attention attention!) 1177, pavillon André-Aisenstadt
La conférence sera présentée en français et les transparents seront rédigés en anglais

RÉSUMÉ (for English see below): Les "étiquettes sociales" ("social tags", i.e. les mots appliqués aux items du web par les usagers) sont devenues de plus un plus populaires comme outil pour la recommandation.  Par exemple, si vous visitez le site web flickr.com et chercher pour "poissons heureux", les résultats de la recherche sont générés en utilisant les étiquettes sociales appliquées aux photos. Dans le domaine de la musique, le site web last.fm utilise les étiquettes sociales pour recommander des chansons en utilisant la similarité au niveau des artistes. Si vous faites une requête sur last.fm pour le group e "art rock" canadien Rush, vous êtes aussi invités à écouter Emerson Lake & Palmer, Yes, et Genesis. Bien que last.fm soit très agréable à utiliser, le site souffre de quelques faiblesses, incluant un biais de popularité et une incapacité à recommander de la musique qui n'a jamais été étiquetée. Nous nous attaquons à ces faiblesses au moyen de l'apprentissage automatique. Notre modèle Autotagger [1] consiste en un ensemble de classifieurs, chacun entraîné à prévoir la présence ou l'absence d'une étiquette sociale, étant donné des attribues extrait de l'audio. Les étiquettes pour l'apprentissage sont obtenues du site last.fm par data mining (~20M étiquette sociales sont associées à une collection audio personnelle comprenant ~120M pistes et ~550 artistes).  Le principal atout de notre approche est que nous pouvons générer des étiquettes pour de nouvelles chansons, o u pour des chansons peu populaires, et ce d'une façon similaire aux usagers su site. En plus, du fait que le modèle génère un "sac de mots" ("bag of words") qui vient du même vocabulaire que les usagers du site, nous pouvons facilement incorporer les résultats dans un système de recommandation existant. La présenta tion met l'accent sur (a) les défis au niveau du data mining (b) l'extraction des attributs ("features") d'un fichier audio (c) la classification via FilterBoost, une version "en ligne" du modèle d'apprentissage automatique de type "ensemble" AdaBoost (d) l'analyse des résultats. Ce travail est fait en collaboration avec Sun Labs, Boston.

ABSTRACT: Social tags (i.e. words applied by users to items on the web) have become an increasingly popular data source for recommendation.  For example if you go to the photo website flickr.com and search for "happy fish" the resulting photo stream of happy looking fish is generated based on social tags.  In the music domain, the website last.fm uses social tags to recommend tracks based on artist similarity.  If you query last.fm for the Canadian art rock band Rush you'll be allowed to (doomed to?) listen to Emerson Lake & Palmer, Yes, and Genesis as well.  Though last.fm is fun to listen to, it suffers from some weaknesses including a popularity bias and an inability to recommend untagged music.  We address these weaknesses using machine learning. Our model Autotagger [1] consists of a set of classifiers each trained to predict the presence or absence of a social tag given acoustic features extracted from an audio file. Training labels are obtained from last.fm using data mining (~20M social tags mapped onto an in-house music collection of ~120K tracks spanning ~5500 artists).  The main strength of our approach is that we can label new and unpopular tracks in a way similar to how real social taggers might label them.  Furthermore, because the output of the model is a bag of words drawn from the same vocabulary used by social taggers, we can easy incorporate the results into an existing recommender.  The talk will focus on (a) data mining challenges encountered in building a large in-house training set of tagged mp3s (b) acoustic feature extraction (c) classification via FilterBoost, an online version of the AdaBoost ensemble learner (d) analysis of results.  This work was done in collaboration with Sun Labs in Boston.

--------------
[1] D. Eck, P. Lamere, T. Bertin-Mahieux, and S. Green. Automatic generation of social tags for music recommendation. In Neural Information Processing Systems Conference (NIPS) 20, 2007. Available at www.iro.umontreal.ca/~eckdoug/publications.html