Notes de janvier
05 Feb 2019Quelques notes de janvier.
Rediffusion de géométrie aléatoire
Images des maths rediffuse un article à propos de la géométrie aléatoire pour fêter l’attribution du prix Wolf à Jean-François Le Gall. L’article de Nicolas Curien donne quelques résultats surprenants sur les cartes planaires, c’est-à-dire les graphes plongés dans le plan. Entre autres choses surprenantes : le concept est étudié dans l’optique d’une unification de la relativité générale et de la mécanique quantique (!).
Un document sur cette thématique est l’habilitation de Guillaume Chapuy, qui semble très bien écrite et que j’espère lire un jour.
(Si vous êtes fanatique de cartes, il y a une «journée carte» de prévue le 15 février à Paris.)
LIPIcs sans logos
J’aime bien la classe latex LIPICs qui est utilisée par la plupart des conférences ayant choisi l’accès ouvert. Pour l’utiliser dans d’autres contextes que ces conférences, par exemple pour des versions arxiv, il y avait jusqu’à récemment quelques difficultés: des logos, des références au numéro doi etc. Suivant l’exemple d’un collègue, j’avais modifié le fichier de classe, mais c’est désormais inutile : la commande \hideLIPICs cache les informations non-pertinentes. (Voir les recommendations aux auteurs, page 8.)
Apprentissage profond et apprentissage PAC
L’apprentissage profond est très populaire auprès d’à peu près tout le monde (d’un point de vue purement technique), sauf des informaticiens théoriciens qui lui reprochent son manque de garanties théoriques. Plusieurs groupes de recherches essayent de combler ce vide (par exemple autour d’Alexander Mądry et du ML theory group à Princeton).
Un des cadres rigoureux d’analyse de l’apprentissage est l’apprentissage PAC, et des liens sont en train d’être tissés entre les deux.
En parlant de PAC, Leslie Valiant a publié un livre disponible en français, à propos de ce concept (dont il est l’inventeur), et de ses liaisons avec la nature et l’évolution.
Éoliennes, apprentissage et algorithmes
Lance Fortnow bloguait ce mois-ci à propos des éoliennes et de l’apprentissage.
En un mot, les changements soudain de force et de direction du vent sont un problème récurrent pour les éoliennes, et causent de nombreux dégats si ils ne sont pas anticipés. Il est possible d’utiliser des simulations de mécaniques des fluides, mais c’est plutôt lent, et la tendance est à l’utilisation de l’apprentissage pour faire des prévisions rapides.
Ainsi, il existe une manière bien définie/comprise de procéder, mais l’on préfère l’apprentissage pour sa rapidité. Cela m’a rappelé un sujet sur stack exchange qui posait la question suivante : les algorithmes seront-ils encore utiles dans le futur (sachant que pour la majorité des problèmes que nous avons à résoudre, nous n’avons pas besoin d’une solution parfaite, et le plus souvent nous ne pouvons même pas mesurer la qualité de la solution) ? Malheuresement la question n’a pas reçu beaucoup de réponses…
Au-delà du pire cas et complexité fragile
Une nouvelle approche de recherche en informatique théorique consiste à aller «au-delà de la complexité dans le pire cas» («beyond worst-case»), c’est-à-dire à considérer d’autres mesures d’efficacité que le temps de calcul sur la pire instance, puisque cette dernière est parfois (souvent ?) peu pertinente. Il y a beaucoup de bonnes choses à découvrir dans ce domaine, comme la complexité lisse. Voir aussi les top 10 ideas du domaine par Tim Roughgarden.
Ce mois-ci, une nouvelle mesure est définie dans un papier arxiv : la complexité fragile. J’ai juste lu le résumé, et je ne comprends pas en quoi cette mesure est fragile, mais je comprends la définition dans le cas du tri : la complexité fragile d’un algorithme de tri sur une instance donnée est le nombre maximum de fois qu’un élément est comparé.