Dans le deuxième épisode de la série The Big Bang Theory, Sheldon et Leonard tentent de porter un colis dans les escaliers jusqu’à l’appartement de leur voisine Penny. La boîte est énorme, presque aussi large que l’échelle elle-même, donc cela ne semble pas être une tâche facile.

Cependant, Leonard observe que, puisqu’il s’agit d’un plan incliné, la force nécessaire pour soulever le colis est réduite d’un facteur égal au sinus de l’angle de l’échelle avec l’horizontale. Cela dit, ils commencent tous les deux à pousser avec enthousiasme, jusqu’à ce que Sheldon demande : « Quelle est votre formule pour tourner ? »

Déplacer des meubles à l’intérieur d’une maison et, en particulier, les déplacer dans les coins n’a jamais été facile. On retrouve des références à ce problème dans d’autres séries célèbres, comme Friends , où (dans l’épisode 16 de la cinquième saison) trois des protagonistes tentent de porter un canapé dans les escaliers tandis que Ross crie encore et encore : « Spin it ! tournez-le! Faites-le tourner ! » Et dans le roman surréaliste de Douglas Adams Dirk Gently: Holistic Investigation Agency et ses suites (qui ont également inspiré quelques séries télévisées), le déplacement des canapés est un thème récurrent, un personnage allant jusqu’à affirmer que ce serait très utile de savoir à l’avance si un meuble s’adaptera dans les escaliers et dans les coins avant de l’acheter.

Toutes ces réflexions sont condensées dans un célèbre problème mathématique à l’approche très simple, mais qui reste ouvert à ce jour. Comme d’habitude en mathématiques, on va formuler le problème dans un monde idéalisé, ce qui permet de ne garder que l’essentiel et de supprimer toute complexité inutile. Pour ce faire, imaginons un monde en deux dimensions (comme une feuille de papier) où il y a un couloir de 1 mètre de large et avec un seul coin, en forme de lettre L. Et maintenant, nous allons essayer de déplacer un canapé le long le couloir. Ce canapé sera également en deux dimensions, il n’aura donc ni coussins, ni télécommande TV, ni repose-pieds motorisé : ce sera juste une figure géométrique plate qui s’intégrera dans le couloir.

Ce canapé plat ira-t-il au coin de la rue ? Bien sûr, cela dépendra de votre forme. Un canapé carré d’un mètre de côté glissera doucement dans le couloir, en supposant que les murs du couloir sont parfaitement lisses et sans frottement. En revanche, un canapé rectangulaire dont les côtés mesurent un et deux mètres pourra couvrir une partie du couloir, mais il n’arrivera jamais à tourner le coin. En général, on voit intuitivement que les canapés plus petits, avec une surface plus petite, seront plus faciles à déplacer que les plus grands. En 1966, le mathématicien austro-canadien Leo Moser s’est posé la question suivante : quelle est la surface maximale qu’un canapé peut avoir pour surmonter ce coin ? Et, au fait, quelle forme devrait avoir ce canapé ? Cette valeur maximale de surface est connue sous le nom de « constante de canapé ».

Répondre à ces questions n’est pas facile. En fait, c’est tellement difficile qu’à ce jour personne n’a été en mesure de prouver formellement quel est le plus grand canapé. Pourtant, il y a eu de très bonnes tentatives, et il semble que nous connaissions la constante du canapé avec une grande précision, bien que nous ne soyons pas encore certains qu’une meilleure solution soit impossible.

La première étape pour résoudre ce type de problème où l’on doit trouver un nombre inconnu est généralement d’établir des bornes. Comme nous venons de le mentionner, il existe une figure d’aire 1 (le carré 1×1) qui passe par notre coin. Il est donc certain que l’aire recherchée vaudra au moins 1. En termes mathématiques, on dit que 1 est une borne inférieure de la constante du canapé. Nous avons également vu qu’un rectangle 1 × 2 ne contournera pas le coin. Peut-on alors dire que 2 est une borne supérieure ? Non! Qui sait, peut-être y a-t-il des chiffres de zone 2, voire plus, qui fonctionneront pour nous. Et, en fait, nous verrons bientôt qu’il en est ainsi.

Au-delà des carrés et des rectangles, la prochaine chose qui peut nous venir à l’esprit est d’utiliser un demi-cercle de rayon 1, comme celui que nous voyons dans la figure suivante:

La première amélioration substantielle de cette référence a été proposée par John Hammersley en 1968, deux ans seulement après que Moser a soulevé le problème. Son idée consistait à allonger le canapé semi-circulaire que nous avons mentionné, en ajoutant une section droite au milieu avec un trou semi-circulaire à travers lequel le sommet du coin pouvait glisser pendant le virage. On aurait ainsi un canapé en forme de récepteur téléphonique rétro, comme celui de la figure suivante:

Ce chiffre devient déjà assez compliqué et il n’est pas facile de l’améliorer : le canapé peut tourner le coin, mais ça arrive tout seul. Peut-être avons-nous trouvé le canapé idéal, n’est-ce pas ? Et bien non. Vingt-quatre ans plus tard, en 1992, Joseph L. Gerver s’est plongé de plein fouet dans le problème et a commencé à analyser des formes vraiment complexes. Non content d’utiliser des rectangles, des cercles et des lignes droites, il représente le canapé comme une succession de courbes décrites par des fonctions mathématiques, collées les unes après les autres le long du périmètre de la figure. Comme un collier, mais avec des équations au lieu de perles. Croyez-moi quand je vous dis que le calcul est ahurissant. Gerver a trouvé un canapé capable de surmonter le coin, décrit par la concaténation de 18 courbes analytiques et très similaire à première vue à celui de Hammersley, mais un peu plus grand. Plus précisément, il a obtenu une superficie de 2,2195…,

À ce stade, cela semble être une histoire sans fin. Nous semblons condamnés à continuer à augmenter la surface petit à petit, par des calculs de plus en plus complexes, jusqu’à ce que nous abandonnions par épuisement. Peut-être que oui, mais la vérité est que personne n’a encore trouvé de meilleure solution que celle de Gerver. Au contraire, nous sommes de plus en plus convaincus que votre canapé est le meilleur possible. En 2014, Philip Gibbs a utilisé un ordinateur de pointe pour estimer la surface du canapé idéal… et le résultat qu’il a obtenu correspond à celui de Gerver à huit décimales près ! Si le canapé de Gerver n’est pas le meilleur, il y ressemble beaucoup. Cependant, le calcul de Gibbs est approximatif : personne ne nous assure que l’aire ne peut pas être augmentée un peu plus, même si c’est à partir de la neuvième décimale.

Nous parlons depuis longtemps de limites inférieures et nous avons oublié les limites supérieures. En fin de compte, ceux-ci sont un peu plus difficiles à trouver et sont, pour l’instant, assez éloignés de la valeur de Gerver. Hammersley lui-même a prouvé à l’époque que l’aire devait être inférieure à deux fois la racine carrée de 2, soit 2,83. Plus récemment, en 2018, Yoav Kallus et Dan Romik ont ​​démontré à l’aide d’ordinateurs qu’elle était inférieure à 2,37. El propio Romik, una de las personas que más ha trabajado en el problema, halló una posible solución para un «sofá ambidiestro» (también llamado coche de Conway o piano de Shepard), capaz de girar con la misma facilidad hacia la derecha y hacia la gauche. Dans ce cas, le canapé a une forme similaire à une paire de lunettes de soleil, et sa surface est un peu plus petite: 1,6450.

Mais pourquoi cette question est-elle si compliquée? Pour donner un exemple, nous connaissons aujourd’hui la valeur de π avec une précision étonnante. Pourquoi est-il si difficile pour nous de déterminer la constante du canapé ? Bien qu’il n’y ait pas de réponse simple, la vérité est que le problème a plusieurs caractéristiques qui le rendent extrêmement difficile à attaquer. Tout d’abord, c’est ce que nous appelons un problème d’optimisation. Dans cette classe de problèmes, nous devons ajuster certains paramètres pour rendre une quantité donnée aussi grande (ou petite) que possible sous certaines contraintes. Dans notre cas, ce que nous essayons de maximiser, c’est la surface, et la condition qui doit être remplie est que le canapé puisse dépasser le coin.

Inutile de dire que ces problèmes sont souvent très utiles dans la vraie vie. Nous voulons tous savoir quelles décisions prendre pour maximiser les profits et minimiser les pertes, dans la limite de nos limites. Et il existe un nombre immense d’énigmes de toutes sortes qui peuvent être exprimées en problèmes d’optimisation. Ainsi, on peut essayer de calculer quel est le meilleur moment pour acheter ou vendre un produit. Ou quelle géométrie une aile d’avion devrait avoir pour générer une portance maximale avec un poids minimal. Ou même quelle est la forme la plus probable que prendra une protéine dans notre corps. Je suis sûr que vous pouvez penser à d’autres exemples : la liste est interminable. Non seulement cela, mais presque tous les phénomènes qui se produisent dans la nature sont décrits en termes d’une certaine quantité qui est rendue minimale ou maximale. Ces grandeurs sont appelées potentiels.

Parfois, seuls quelques paramètres devront être ajustés, ce qui est généralement assez facile avec les outils d’aujourd’hui. Dans d’autres cas, comme le canapé, nous devrons ajuster une courbe entière, ce qui signifie un continuum de paramètres infinis. Cela nécessite des techniques mathématiques plus avancées, comme les équations différentielles, mais rien que nous n’ayons maîtrisé depuis l’époque d’Euler et de Lagrange au 18ème siècle. Cependant, le problème du canapé présente des difficultés supplémentaires, liées à la restriction que le meuble parvient à passer par le coin. Au fur et à mesure que le canapé tourne, différents points de son contour glissent le long des murs du couloir, limitant la forme qu’il peut prendre. Ceci implique que le problème est non local : chaque point de notre figure géométrique dépend de la position ( a priori inconnu) à partir d’autres points situés à l’extrémité opposée de la figure elle-même.

Tout cela nous amène à l’outil le plus polyvalent à notre disposition pour résoudre les problèmes d’optimisation : l’intelligence artificielle et les algorithmes d’apprentissage automatique. Dans la plupart de ces algorithmes, nous concevons un « modèle », une opération mathématique compliquée avec de nombreux paramètres que nous pouvons faire varier librement. L’objectif se réduit alors à savoir quelle valeur nous devons attribuer à chacun des paramètres pour que notre modèle accomplisse la tâche que nous voulons, qu’il s’agisse de reconnaître des images, d’écrire du texte ou de conduire une voiture autonome. Pour ce faire, on définit une quantité, appelée fonction de perte (ou simplement « perte »), qui représente l’erreur commise par le modèle. Plus cette fonction est petite, plus l’algorithme sera efficace, nous sommes donc à nouveau confrontés à un problème d’optimisation:

Puisque c’est nous qui choisissons comment calculer notre fonction de perte, nous savons quel effet chaque changement que nous apportons aux paramètres aura sur celle-ci. Ainsi, nous pouvons progressivement les ajuster pour réduire de plus en plus la perte. Cette procédure est connue sous le nom de « formation » du modèle, afin qu’il « apprenne » à faire son travail aussi bien que possible. Pour des tâches simples, quelques paramètres suffiront, mais dans les modèles les plus modernes et avancés, le nombre de paramètres peut devenir gigantesque. Le développement rapide des dispositifs de calcul tels que les processeurs (CPU) et les unités de traitement graphique (GPU) et les unités de tenseur (TPU) nous permettent de former d’énormes modèles, souvent, bien sûr, au prix d’un temps et d’une énergie considérables. 

L’un des modèles les plus utilisés est celui des réseaux de neurones. On ne parle pas de vrais neurones, comme ceux du cerveau, mais d’unités de calcul qui s’en inspirent fortement. Dans notre cas, chaque neurone est un simple objet mathématique qui reçoit certaines impulsions sous forme de nombres et en génère d’autres. Ces neurones sont généralement organisés en différentes couches, de sorte que les informations produites par une couche sont transmises à la suivante jusqu’au résultat final. Plus votre réseau comporte de couches, plus les tâches qu’il peut effectuer sont complexes, et les réseaux à plusieurs couches sont appelés « profonds », ce qui donne lieu au bien nommé apprentissage en profondeur. Il existe de nombreux types de réseaux de neurones, mais nous nous concentrerons ici sur le plus simple.

Notre réseau de neurones aura pour mission de déformer un cercle, transformant chacun de ses points en un point sur le contour du canapé. Puisqu’un point est défini par ses  coordonnées x  et  y , les première et dernière couches auront deux neurones. Nous devons maintenant définir une fonction de perte appropriée pour ce problème. Puisque nous voulons que l’aire soit maximale, la première chose qui nous vient à l’esprit est d’utiliser l’aire changée de signe : ainsi, une plus petite perte conduira à une plus grande aire. Mais comment imposer la condition que le canapé passe par le coin ? Le moyen d’y parvenir est d’ajouter une pénalité qui rend la perte très importante lorsque le canapé ne rentre pas.

Nous faisons pivoter le canapé d’un angle choisi au hasard et le poussons contre l’extérieur du coin, de sorte qu’il touche les deux murs. Et, ensuite, nous imposons une pénalité pour les points qui sont à l’extérieur du couloir de l’autre côté (ceux qui tombent sur le coin lui-même). Ainsi, le réseau apprendra qu’il doit éviter cette situation à tout prix. Pendant l’entraînement, nous répétons cette opération pour de nombreux angles aléatoires. Au début, le réseau produira un canapé en forme de pomme de terre qui ne fait rien de ce que nous recherchons. Cependant, la silhouette du canapé de Gerver apparaîtra comme par magie au fur et à mesure que l’entraînement progresse. Au terme de cela, notre canapé est quasiment identique à celui de Gerver et sa superficie nous donne la valeur attendue de 2,2195.

Previous articleLe big data transforme le football
Next articleL’intelligence artificielle écrit sur elle-même