Vincent
BLONDEL, TFE
pour 2007-2008
Cette page
se trouve
à l'adresse: http://www.inma.ucl.ac.be/~blondel/tfe2007.html
Captcha:
distinguer hommes et ordinateurs
Encadrement:
Vincent
Blondel
Un
captcha est un programme qui génère
automatiquement des
tests que la
plupart des humains passent sans difficultés alors que les
programmes
informatiques actuels n'y parviennent pas. Ainsi par exemple les
humains décodent sans
difficulté le texte déformé suivant
alors qu'un
ordinateur n'y parvient pas de manière
systématique.
Les premiers captchas
ont été introduits il y a
quelques
années et sont utilisés aujourd'hui, par exemple
par
Yahoo! ou Skynet,
pour éviter l'ouverture automatique d'un grand nombre
d'adresses
email gratuites. Les applications potentielles des captchas sont
nombreuses; ils permettent par exemple d'éviter des "votes
automatiques" sur internet et ils pourraient être
utilisés
pour combattre le spam en exigeant d'un émetteur qu'il
s'identifie comme humain en résolvant un captcha pour chaque
envoi.
Dans d'autres
contextes, la difficulté d'automatiser de
telles tâches de reconnaissance
(reconnaissance d'image, de voix, de spam, etc.) de manière
automatique est
un frein à la réalisation de ces tâches
à
grande échelle. Des auteurs ont proposé
récemment
d'effectuer ces tâches de manière
distribuée par
des humains soit en formulant le problème de
reconnaissance comme un jeux, soit en utilisant la tâche de
reconnaissance comme moyen de micro-paiement. Ainsi par exemple les
jeux interactifs Peekaboom (voir
http://www.peekaboom.org)
et esp (http://www.espgame.org)
sont des jeux qui
permettent à leurs concepteurs d'obtenir des descriptions
d'images comme résultat de jeux sur internet. Pour des
micro-paiements, on peut imaginer qu'en échange de
l'obtention du fichier électronique d'un article de journal
ou
en échange du déchargement d'un morceau de
musique il
soit demandé d'effectuer une petite tâche de
reconnaissance vocale.
Ces
différents exemples illustrent l'apparition d'un nouveau
paradigme en informatique. Dans le cadre de ce mémoire, on
s'intéressera à une description de
l'émergence de
ce nouveau paradigme et on s'intéressera tout
particulièrement aux premières tentatives de
description
formelle.
Références
Pour les captchas, voir
les pointeurs au départ du site http://www.captcha.net/
L. von Ahn, M. Blum, N.
Hopper and J. Langford. CAPTCHA: Using hard AI problems for security. In Advances in
CryptologyEurocrypt '03 (Volume 2656 of Lecture Notes in Computer
Science), pages 294311, 2003.
Secure Distributed
Human Computation, Gentry, Ramzan, Stubbledine, Financial
Cryptography
and Data Security, 2006.
Implémentation
et comparaison d'algorithmes pour le calcul du rayon spectral conjoint
Encadrement:
Vincent
Blondel,
Yurii Nesterov, Raphaël Jungers
Le
rayon spectral conjoint est
une quantité qui donne le
plus
grand taux de croissance asymptotique que l'on peut obtenir en
multipliant des matrices choisies dans un ensemble. C'est une
quantité qui apparaît dans un grand nombre d'applications,
en théorie du codage, en théorie des ondelettes, en
théorie des nombres, etc. Le rayon spectral conjoint est
connu pour être difficile
à
calculer et plusieurs
algorithmes d'approximation ont été proposés
récemment: méthodes
force brute,
branch and cut, programmation semi-définie, etc. Certaines
méthodes, quoique
très
séduisantes sur un plan théorique, n'ont jamais
été implémentées. Or, une telle
implémentation serait bénéfique
à plus d'un
titre: outre une plate forme utile pour le calcul du rayon spectral
conjoint servant aux applications pratiques, et un outil de comparaison
des diverses méthodes existantes, celle-ci pourrait servir
d'outil d'analyse théorique pour le comportement
asymptotique de
ces produits, comportement encore mal expliqué
à l'heure actuelle. En particulier, un tel
programme
pourrait aider à la compréhension de
problèmes
ouverts tels que la propriété de finitude pour
les
matrices rationnelles.
Références
G.C. Rota and C.
Strang, A note on the joint spectral radius, Indag.
Math., 22:379--381, 1960.
Vincent
D. Blondel,
Yurii Nesterov, Computationally efficient approximations of
the joint spectral radius, SIAM
Journal of Matrix
Analysis, 27:1, pp. 256-272, 2005
Graphes
observables et grands graphes
Encadrement: Vincent Blondel et Raphaël Jungers
La notion
de graphe observable a été introduite
récemment pour caractériser des
réseaux de
capteurs visant à la localisation d'agents
autonomes. Certains algorithmes efficaces ont été
proposés
afin de reconnaître algorithmiquement les graphes
observables. Dans le cadre de ce mémoire on s'intéressera
à des questions liées aux graphes observables: Combien de
couleurs
sont nécessaires en moyenne
pour faire d'un graphe
aléatoire un graphe observable? Quel est la
longueur minimale nécessaire pour aboutir à la
localisation de l'agent dans le graphe? Suivant
l'intérêt de l'étudiant, on s'intéressera
à des questions d'implémentation algorithmique ou
à des questions plus abstraites liées aux graphes
observables.
Références
R. M. Jungers and V. D.
Blondel, Observable graphs, 2007.
Similarité dans
les
graphes. Application à l'extraction de motifs biologiques
Encadrement: Vincent Blondel, en
collaboration avec le groupe de recherche Large graphs and
networks
Plusieurs mesures de
similarité dans les graphes et réseaux ont
été
proposées ces dernières
années et les liens que ces définitions
entretiennent
entre elles ne sont pas clairement identifiés. Dans ce
mémoire, nous souhaitons présenter les
différentes mesures
de manière unifiée, fournir une
interprétation pour certaines d'entre-elles au moyen de
marches
aléatoires et, finalement, envisager l'application de
certaines
de ces méthodes pour l'extraction de motifs dans des
réseaux biologiques.
Références
Vertex
similarity in networks, E.
A. Leicht, Petter Holme,
M.
E. J. Newman, Phys. Rev. E 73, 026120 (2006).
Vincent D. Blondel,
Anahí Gajardo, Maureen Heymans, Pierre Senellart, Paul Van
Dooren, A
measure of similarity between graph vertices. With applications to
synonym extraction and web searching, SIAM Review, 46:4, pp.
647-666,
2004.
R Milo, S Shen-Orr,
S Itzkovitz, N Kashtan, D Chklovskii & U Alon,
Network Motifs:
Simple Building Blocks of Complex Networks, Science,
298:824-827 (2002).
Effet
de la topologie d'un réseau sur la propagation
d'épidémies
Encadrement: Vincent Blondel, en
collaboration avec le groupe de recherche Large graphs and
networks
Collaboration éventuelle avec Dr A. Ganesh (Microsoft Research, Cambridge).
Un grand nombre de
phénomènes sont modélisés
par la
propogation d'épidémies sur des
réseaux. Dans certains cas l'épidémie
n'est pas souhaitée (comme
dans le cas d'un virus ou d'un virus informatique) et on recherche
alors des stratégies optimales pour éviter ou
atténuer la propagation (par vaccination par exemple); dans
d'autres cas le
souhait peut être d'obtenir une propagation aussi rapide que
possible (par exemple lorsqu'il s'agit de transmettre rapidemment une
information
à toute une population). Dans ce mémoire on
réalisera d'abord un compte-rendu des approches possibles de
tels
phénomènes. On s'intéressera ensuite
à la
quantification, pour un modèle
particulier, de la vitesse de propagation de
l'épidémie
et la dépendance de cette vitesse pour
différentes topologies de réseau ("random",
"scale-free",
"small-world"). On considèrera ensuite la
possibilité
d'étendre les résultats actuels à une
situation
dans laquelle le réseau évolue avec le temps. Une
première analyse de ce problème semble faire
apparaître de nouvelles questions qui se lient de
manière
élégante à des résultats
récents
obtenus pour le calcul du rayon spectral conjoint.
Références
The effect of network
topology on the spread of epidemics, A. Ganesh, L.
Massoulié, D. Towsley, Proc. IEEE Infocom, 2005.
Designing a Contact
Process : The Piecewise-Homogeneous Process on a Finite Set with
Applications, Aaron Wagner and Venkat Anantharam, Stochastic Processes
and their Applications, Vol. 115, No. 1, pp. 117 -153, January 2005.
Efficient algorithms
for
deciding the
type of growth of products of integer matrices, Raphaël
Jungers,
Vladimir Protasov, Vincent D. Blondel, Preprint, 2006
Physique
et informatique
Le professeur M.
Mézard est sur le point de publier un livre
(disponible sur le web gratuitement à l'adresse http://ipnweb.in2p3.fr/~lptms/membres/mezard/,
voir aussi la référence plus bas)
intitulé: Constraint
Satisfaction Networks in Physics and Computation.
L'ouvrage est passionnant et ouvre de nombreuses perspectives
innovantes à la frontière entre physique et
informatique
théorique. Presque chaque chapitre du livre peut faire
l'objet
d'une introduction à un sujet de mémoire. Nous
avons un
intérêt tout particulier pour les aspects
liés
à la propagation de croyance ("belief propagation") ainsi
qu'aux
développements relatifs aux fascinants verres de spin ("spin
glasses").
Références
Passing
Messages Between Disciplines, Marc Mézard, Science 19
September 2003, Vol.
301. no. 5640, pp. 1685 - 1686