CR01 Using Randomness in Science

Intervenants: Pierre Borgnat, Patrick Flandrin, Olivier Gandrillon et Nicolas Schabanel

Responsable du cours: N. Schabanel

Calendrier des cours

Date	8:00-10:00	13:30-15:30	15:45-17:45
Thursday Dec 12	Nicolas Schabanel (1/4)
Thursday Dec 19	Nicolas Schabanel (2/4) Lecture Notes: [ PDF ]
Tuesday Jan 7			Olivier Gandrillon (1/2) Slides: [ PDF \| PPT ]
Thursday Jan 9	Nicolas Schabanel (3/4) Lecture Notes: [ PDF ]
Thursday Jan 16	Nicolas Schabanel (4/4)	Olivier Gandrillon (2/2) Slides: [ PDF ]	Patrick Flandrin (1/2)
Thursday Jan 30	Patrick Flandrin (2/2)
Tuesday Feb 4		Pierre Borgnat (1/2)	Pierre Borgnat (2/2)
Tuesday Feb 6	Exam (9h30-11h30)

Présentation générale

La puissance offerte par le hasard s’est imposée dans différents champs de recherches durant ces dernières décennies et les techniques ont maintenant atteint une maturité suffisante pour être considérées comme classiques voire indispensables dans la plupart des domaines scientifiques. Après une présentation commune et synthétique des différentes bases mathématiques utilisées dans ce cours aussi bien en informatique qu’en physique ou encore en biologie, nous présenterons différents aspects des usages surprenants que l’on peut faire du hasard et leurs conséquences aussi puissantes qu’inattendues.

Partie Informatique : Possibilités inattendues offertes par le hasard en algorithmique (N. Schabanel) (env. 2/5ème du cours)

Depuis une trentaine d'années, les informaticiens ont révélé que l'on pouvait faire des usages assez étonnants du hasard, d'autant plus étonnants que ces résultats sont violemment contre-intuitifs. Nous verrons dans ce cours comment utiliser du hasard pour compter exactement avec une mémoire toute petite (randomized counters), comment corriger un programme buggé sans modifier son code (autocorrection de code), comment tester si quelqu'un sait quelque chose, sans rien apprendre ni savoir de son secret (zero-knowledge), étudier les étranges propriétés des graphes expandeurs et leurs étonnantes applications. Le plus surprenant est que ces méthodes sont très simples, tant à prouver et qu'à mettre en oeuvre, et sont le plus souvent bien plus efficaces que leurs alternatives déterministes: à la fois plus rapides et plus économiques en ressources. Ces techniques ont donc toutes les chances d'être favorisées par la sélection naturelle et pourraient donc bien se retrouver dans la nature, donc autant s'y préparer ! Le hasard est ainsi loin d'être seulement un bruit dont on chercherait à se débarrasser mais est au contraire appeler à jouer des rôles moteur insoupçonnés. Nous verrons également comment la notion de hasard peut être reliée à la notion de problèmes difficiles.

Quelques références bibliographiques :

S. Arora, B. Barak. Computational complexity : a modern approach, Princeton U. Press, 2010
S. Hoory, N. Linial, A. Wigderson. Expanders graphs and their applications, Bull . Amer. Math. Soc., 43:439-561, 2006.
L. Trevisan’s remarkable lecture notes : http://lucatrevisan.wordpress.com/lecture-notes/

Partie physique : Le point de vue de l'analyse de données Bruit et/ou information (P. Borgnat et P. Flandrin) (env. 2/5ème du cours)

Classiquement le bruit est vu comme une nuisance dont il faut s'affranchir dans des méthodes d'analyse de données, que ce soit en traitement du signal et des images, en statistiques ou dans des opérations d'acquisition de données. Cependant, au-delà de dire parfois que l'information peut être portée par du bruit, certaines méthodes proposent d'utiliser le bruit comme aide à l'analyse et à la décision. Plusieurs de ces approches ont une origine dans le monde des sciences physiques. On propose de couvrir trois familles d'approches en ce sens :

Accès à des données avec de l'aléatoire dans les mesures : échantillonnage ou quantification aléatoires ou irréguliers ; introduction à échantillonnage compressif ("compressed sensing") ; estimation par projections aléatoires (sketch, filtres de Bloom,...)
Méthodes de brassage aléatoire des données : "bootstrap" en statistiques ; données substituts ("surrogates") en physique non-linéaire et traitement du signal,...
Analyse assistée par le bruit : résonance stochastique ; moyennes robustes par l'ajout de bruit ; liens avec les algorithmes ou les simulations assistés par le bruit (gradients stochastiques, méthodes de Monte-Carlo, recuit simulé).

L'objectif du cours est de couvrir les principaux résultats sur ces trois manières où une composante aléatoire, éventuellement du bruit, peut être employée avec profit pour améliorer des méthodes d'analyse de données. Le cours couvrira les résultats de base de ces méthodes avant d'ouvrir sur les travaux récents dans ces domaines.

Quelques références :

1er thème:
- P. Babu, P. Stoica (2010). "Spectral analysis of nonuniformly sampled data – a review," Digital Signal Processing, vol. 20(2), pp. 359–378
- R.G. Baraniuk, E. Candès, R. Nowak, M. Vetterli eds. (2008). "Special Section on Compressive Sampling," IEEE Sig. Proc. Mag., vol. 25(2), pp. 12–101. See also: http://dsp.rice.edu/cs/
- S. Muthukrishnan (2003). "Data streams: Algorithms and applications," in ACM SIAM SODA.
2ème thème:
- B. Efron, R. Tibshirani (1994). An Introduction to the Bootstrap. Chapman & Hall/CRC.
- B. Efron, B. (1982). The jackknife, the bootstrap, and other resampling plans. CBMS-NSF Monographs.
- T. Schreiber, A. Schmitz (2000) "Surrogate time series," Physica D, vol. 142(3-4), pp. 346–382.
- A. Zoubir, D.R Iskander (2004). Bootstrap Techniques for Signal Processing, Cambridge University Press.
3ème thème:
- A. Bulsara, P. Hänggi, F. Marchesoni, F. Moss, M. Shlesinger, eds. (1993). Stochastic Resonance in Physics and Biology, J. Stat. Phys. 70, 1-512.
- T. Wellens, V. Shatokhin, A.Buchleitner (2004). "Stochastic resonance," Rep. Prog. Phys., vol. 67, pp. 45–105.
- F. Mossa, L.M. Ward, W.G. Sannita (2004). "Stochastic resonance and sensory information processing: a tutorial and review of application," Clinical Neurophysiology, vol. 115, pp. 267–281.
- D. Rousseau, F. Chapeau-Blondeau (2005). "Stochastic resonance and improvement by noise in optimal detection strategies," Digital Signal Processing, vol. 15, pp. 19-32.

Partie biologie : le hasard au cœur de la cellule (O. Gandrillon) (env. 1/5ème du cours)

L’idée que le hasard puisse jouer un rôle moteur en biologie doit évidemment énormément à Charles Darwin, qui le premier l’a postulé comme principe moteur de l’évolution. Il est cependant clair que cette idée n’a que peu, voire pas du tout, diffusé au sein des biologistes moléculaires, qui dans la continuité des vues de Schrödinger (« What is Life ») et de Monod et Jacob ont œuvré ces cinquante dernières années au sein d’un paradigme programmatique (« le programme génétique ») que l’aléatoire ne pouvait que perturber. Ici où là se sont bien élevées quelques voix discordantes ((Novick and Weiner, 1957) ; (Spudich and Koshland, 1976) ; (Rigney and Schieve, 1977) ; (Berg, 1978) ; (Kupiec, 1983)), mais il a fallu attendre un article de 2002 ((Elowitz et al., 2002)) pour que la démonstration expérimentale de la variabilité de l’expression génique force une partie de la communauté à reconsidérer le rôle que pouvait jouer l’aléatoire en biologie (pour des revues récentes, voir (Huang, 2010) ; (Eldar and Elowitz, 2010)). Ces dernières années une importante littérature s’est attachée à démontrer que le hasard pouvait jouer :

Un rôle adaptatif;
Un rôle dans le cycle cellulaire;
Un rôle dans les prises de décisions chez le virus HIV et à l’échelle cellulaire chez certains procaryotes pouvant conduire à un rôle dans la pathogénèse;
Un rôle au cours du développement embryonnaire et dans certains processus de différenciation cellulaire.
Un rôle dans le développement des cancers.
Un rôle dans le vieillissement.
Un rôle dans la variabilité dans cellules cancéreuses en réponse aux traitements.

Nous essaierons au sein de ce cours d’aborder deux questions :

Comment mesurer et modéliser la stochasticité de l’expression génique
Au travers d’un ou deux exemples, illustrer son rôle possible en biologie.

Quelques références :

Berg, O.G. (1978). A model for the statistical fluctuations of protein numbers in a microbial population. J Theor Biol 71, 587-603.
Eldar, A., and Elowitz, M.B. (2010). Functional roles for noise in genetic circuits. Nature 467, 167-173.
Elowitz, M.B., Levine, A.J., Siggia, E.D., and Swain, P.S. (2002). Stochastic gene expression in a single cell. Science 297, 1183-1186.
Huang, S. (2010). Cell Lineage Determination in State Space: A Systems View Brings Flexibility to Dogmatic Canonical Rules. PLOS Biol 8, e1000380.
Kupiec, J.J. (1983). A probabilistic theory for cell differentiation, embryonic mortality and DNA C-value paradox. Speculations in Science and Technology 6, 471-478.
Novick, A., and Weiner, M. (1957). Enzyme Induction as an All-or-None Phenomenon. Proc Natl Acad Sci U S A 43, 553-566.
Rigney, D.R., and Schieve, W.C. (1977). Stochastic model of linear, continuous protein synthesis in bacterial populations. J Theor Biol 69, 761-766.
Spudich, J.L., and Koshland, D.E., Jr. (1976). Non-genetic individuality: chance in the single cell. Nature 262, 467-471.

Modalités d’évaluation (données à titre indicatif)

Chaque partie fera l'objet d'une brève évaluation, parmi: devoir à la maison, lecture d'article, réalisation d'un petit programme, rédaction d'un rapport.