Calcul en ligne : améliorer ses performances en utilisant des prédictions

Dans notre quotidien, il nous arrive souvent de prendre des décisions en ne disposant que d’informations partielles, quand elles ne sont pas fausses, sur l’avenir. Imaginons par exemple que vous ayez un rendez-vous médical. Quand vous arrivez dans le bâtiment abritant le cabinet médical, vous découvrez que l’affichage lumineux des ascenseurs est hors service. Vous n’avez donc aucune idée du moment où arrivera l’ascenseur suite à votre appel ; pour ce que vous en savez, il pourrait tout aussi bien être en panne. Vous savez que vous aurez droit à la soupe à la grimace (ou à une consultation expéditive) de la part de votre médecin si vous arrivez en retard. Combien de temps devriez-vous attendre l’ascenseur avant de monter par les escaliers ? Prenons un second exemple. Supposons que vous mettiez une maison en vente. Cela implique que, au cours des semaines à venir, vous receviez des offres d’acheteurs potentiels. À chaque fois que vous recevez une offre, vous devez soit l’accepter soit la décliner immédiatement. Comment gérer ces offres ? Quand accepter une proposition de prix ?

Ces exemples ne sont pas seulement des illustrations de la prise de décision au quotidien, mais également des énoncés de problèmes de calcul avec incertitudes. Deux questions majeures émergent : comment peut-on formaliser le problème et les objectifs ? Et comment peut-on concevoir des algorithmes pour les résoudre et évaluer leur qualité ?

Le calcul en ligne : un paradigme pour le calcul avec incertitudes

En informatique, et plus spécifiquement dans le domaine de la théorie du calcul, les chercheurs et chercheuses ont proposé un modèle simple et cependant général du calcul avec incertitudes. En particulier, dans leur travail fondateur datant du milieu des années quatre-vingts, les informaticiens Sleator et Tarjan (voir la référence bibliographique [4]) ont proposé le modèle du calcul en ligne. Dans ce modèle, les entrées de l’algorithme peuvent ne pas être entièrement connues dès le départ, mais plutôt révélées au fur et à mesure que l’algorithme s’exécute, sous la forme de blocs ou de fragments de l’ensemble des valeurs. Pour chacun de ces fragments, le calcul en ligne doit prendre une décision de façon irrévocable, c’est-à-dire une décision sur laquelle on ne pourra pas revenir ultérieurement. De plus, l’algorithme ne dispose d’aucune information sur les entrées à venir.

Voyons comment nos exemples introductifs entrent dans le cadre des algorithmes en ligne. Dans le cas de la vente d’une maison, les données d’entrée sont les offres d’achat : dans cet exemple, l’algorithme du vendeur doit décider, pour chaque offre, de l’accepter ou de la décliner sans avoir connaissance des offres à venir et sans pouvoir réviser sa position sur une offre passée. À première vue, l’exemple de l’ascenseur ne semble pas entrer dans la catégorie des problèmes admettant un algorithme de résolution en ligne (que nous appellerons « problèmes en ligne » par la suite). Cependant, on peut le formuler comme un problème en ligne de la façon suivante : à chaque seconde, on doit décider si on cesse d’attendre l’ascenseur pour emprunter les escaliers, ou bien si on continue à attendre l’ascenseur dans l’espoir qu’il arrive rapidement. Maintenant que nous avons modélisé nos deux exemples sous la forme de problèmes en ligne, passons à une question plus délicate : comment mesurer la performance d’algorithmes en ligne, c’est-à-dire comment comparer des algorithmes en ligne et comment déterminer lequel est le meilleur ?

L’analyse de compétitivité pour mesurer la performance d’algorithmes en ligne

Pour trouver les réponses à ces questions, on s’est appuyé sur le succès remarquable de la théorie de la complexité, qui remonte aux années soixante-dix. Plus précisément, de la même façon que l’on établit la complexité d’un algorithme en la mesurant sur l’entrée (de longueur donnée) qui donne la plus grande complexité, pour évaluer un algorithme en ligne on considère sa performance dans le pire cas. De plus, la performance dans le pire cas est comparée à la performance d’un algorithme puissant, et même omniscient, qui tirerait parti de la connaissance à l’avance de la suite entière des entrées de l’algorithme.

Le résultat de cette comparaison est mesuré par ce qui s’appelle le ratio de compétitivité et la technique d’analyse correspondante est connue sous le nom d’analyse compétitive. Plus précisément, le ratio de compétitivité est une fraction faisant intervenir le résultat obtenu par notre algorithme et le résultat de l’algorithme omniscient et il s’agit d’une grandeur toujours supérieure ou égale à 1. On cherche à mettre au point un algorithme se comportant le mieux possible en comparaison de cet algorithme omniscient, autrement dit on souhaite que le ratio de compétitivité soit le plus faible possible. Dans le cas où l’on veut minimiser un coût, comme dans le problème de l’ascenseur par exemple, le ratio de compétitivité est défini comme la fraction obtenue en divisant le résultat obtenu par notre algorithme, par le résultat de l’algorithme omniscient. Dans le cas où l’on veut maximiser un profit, comme dans l’exemple de la vente d’une maison, le ratio de compétitivité est alors défini comme la fraction obtenue en divisant le résultat de l’algorithme omniscient par le résultat obtenu par notre algorithme.

Pour regarder de plus près comment l’analyse compétitive est appliquée au problème de l’ascenseur, commençons par noter \(S\) (comme « stairs » en anglais) le temps en secondes pour arriver au cabinet médical en montant par les escaliers, et \(L\) (comme « lift ») le temps en secondes pour monter avec l’ascenseur. Clairement, on suppose que \( S \gt L\) et même \( S \gg L\) (ce qui se lit « \(S\) est beaucoup plus grand que \(L\) »).

Voici un algorithme simple pour résoudre notre problème : nous attendons \(S-L\) secondes que l’ascenseur arrive, et s’il n’est pas là, nous montons par les escaliers. Si jamais l’ascenseur arrive au temps \(t\) qui est plus petit que ces \(S-L\) secondes, le temps que nous mettrons à arriver au cabinet médical est \(t+L\), ce qui est plus court que le temps \(S\) de monter par les escaliers, puisque \(t \leq S-L\) et donc \(t+L \leq S\). Dans le pire des cas, si nous jouons vraiment de malchance, l’ascenseur arrivera juste après que nous nous soyons engagés dans les escaliers : il nous faudra \( S-L +S = 2S-L\) secondes pour arriver au cabinet médical, alors que si nous avions pu prédire l’avenir et si nous avions attendu un peu plus que l’ascenseur arrive au temps \(S-L\), nous aurions mis un temps égal à \(S-L+L=S\) secondes pour monter. C’est le mieux que nous aurions pu faire, en disposant d’une information sur l’avenir. Le ratio de compétitivité de notre algorithme est donc \( (2S-L)/S\). Nous pouvons l’interpréter comme le facteur de ralentissement causé par le fait de ne pas connaître le futur, dans ce cas il s’agit d’un facteur au plus \( \frac{2S-L}{S} \leq 2\).

De la même façon, nous pouvons appliquer l’analyse compétitive au problème de la vente d’une maison. Cependant, dans ce cas nous avons besoin d’une hypothèse sur la façon dont les prix vont fluctuer : sans cela, il nous sera impossible d’établir des garanties pertinentes. Supposons donc que l’on connaisse a priori la fourchette dans laquelle vont se situer les offres : toutes les propositions vont se trouver dans l’intervalle \([m,M]\) pour une certaine borne inférieure \(m\) et une certaine borne supérieure \(M\), avec \(m<M\). On peut établir que l’algorithme qui accepte la première offre qui est supérieure ou égale à \( \sqrt{mM}\) présente un ratio de \( \sqrt{\frac{M}{m}} \) : en effet, si on accepte la première offre supérieure ou égale à \( \sqrt{mM}\), au pire elle est égale à \( \sqrt{mM}\) — et si on n’est pas dans le cas le pire, elle est plus élevée. Dans le pire des cas, c’est-à-dire encore une fois le cas le plus défavorable pour nous, une offre plus tardive aurait pu être plus élevée et même égale au maximum possible qui est \(M\). Dans ce cas, le ratio entre ce que nous avons obtenu, à savoir \( \sqrt{mM}\), et le meilleur des cas, à savoir \(M\), est \( M / \sqrt{mM} = \sqrt{\frac{M}{m}}\) (voir par exemple le panorama de l’optimisation financière en ligne dressé par El-Yaniv, référence [2]). Pour que la description de cet exemple soit complète, il reste à préciser que cet exemple est limité dans le temps : quand le vendeur apprend qu’il arrive au bout du temps imparti, il accepte la première offre qui lui est faite et dont il sait qu’elle est au moins \(m\). Dans ce cas, on sait que la meilleure offre qui a été faite était inférieure ou égale à \(\sqrt{mM}\), et que celle qui a été acceptée était supérieure ou égale à \(m\) : dans ce cas encore, le ratio de compétitivité est inférieur ou égal à \(\sqrt{\frac{M}{m}}\) et le résultat précédent est encore valable.

Les exemples précédents illustrent comment mesurer la performance d’algorithmes en ligne, en utilisant l’analyse de compétitivité. Plus important peut-être, cette formalisation permet de quantifier non seulement la puissance des algorithmes en ligne, mais également leurs limites. Pour cela, on étudie un jeu entre l’algorithme en ligne et un adversaire, c’est-à-dire une entité malicieuse qui choisit les entrées de façon à maximiser l’inefficacité de l’algorithme en ligne. Par exemple, pour le problème de l’ascenseur, l’adversaire ferait arriver l’ascenseur pile au moment où nous renonçons à l’attendre et où nous nous résignons à emprunter les escaliers. Pour le problème de la vente d’une maison, l’adversaire ne fera plus que des offres basses après que nous ayons refusé une offre élevée, nous laissant peu de marge de manœuvre pour parvenir à un bon résultat.

Ce type de jeu nous permet de démontrer que les algorithmes que nous avons proposés plus haut pour ces deux problèmes sont optimaux, dans le sens suivant : aucun algorithme (déterministe) ne peut atteindre un meilleur ratio de compétitivité. On peut se demander ce qui change quand l’algorithme est probabiliste, c’est-à-dire quand ses décisions peuvent être basées sur le tirage à pile ou face d’une pièce. Le même cadre d’études s’applique, avec deux différences notables : les performances de l’algorithme sont mesurées en moyenne, et l’adversaire, probabiliste lui aussi, fournit des entrées qui mettent l’algorithme en difficulté en moyenne également. Nous ne détaillerons pas, dans le cas probabiliste, les interactions exactes entre l’adversaire et l’algorithme ni cette notion de « en moyenne », elles sont plus techniques à analyser et cela dépasserait le propos de cet article. Il faut simplement retenir que même si, pour certains problèmes, l’introduction d’aléa peut améliorer le ratio de compétitivité, l’analyse reste, dans son essence, similaire à celle pour le cas déterministe.

Durant ces quarante dernières années, un grand nombre de problèmes en ligne a été étudié en adoptant le point de vue de l’analyse de compétitivité ; parmi ces problèmes, nombreux sont ceux qui ont d’importantes applications pratiques, telles que l’allocation de fréquence dans les réseaux sans fil, le montant d’enchères pour des biens au fur et à mesure qu’ils sont mis en vente, les politiques de gestion de cache dans les systèmes d’exploitation ou encore la sélection de publicités personnalisées par les moteurs de recherche.

Calcul en ligne avec prédiction

Dans les exemples précédents, les algorithmes fonctionnaient en étant presque totalement ignorants de ce que le futur leur réservait. Cependant, en pratique on dispose souvent de formes de prédictions. Par exemple, quand vous allez à votre rendez-vous médical, la réception peut vous glisser que « l’ascenseur sera de retour dans une minute ou deux », ou bien, pour la vente d’une maison, l’agence immobilière peut vous conseiller d’ « accepter une offre qui est au-dessus de 300 k€ » , si c’est un peu au-dessus de l’estimation qui a été faite de la maison.

Il n’est pas difficile d’incorporer ces prédictions dans la conception d’algorithmes en ligne. Par exemple on peut intégrer l’information de la réception et attendre l’ascenseur, puis, s’il n’est toujours arrivé au bout de deux minutes, revenir à l’algorithme initial. Toutefois, prendre en compte les prédictions dans l’analyse de compétitivité et être capable d’établir mathématiquement des garanties sur le ratio de compétitivité rend la tâche beaucoup plus ardue. Il y a plusieurs difficultés à surmonter. Tout d’abord, comment définir formellement une prédiction ? Comment mesurer l’erreur de prédiction, autrement dit comment quantifier l’écart entre la prédiction et ce qui se produit réellement ? Et comment incorporer cette erreur de prédiction dans l’étude du ratio de compétitivité ?

Mesurer l’erreur de prédiction

Il y a eu deux approches fondamentalement différentes de ces questions. La première approche est appelée modèle de la complexité avec conseil (voir référence [1]). Ici la prédiction, aussi dénommée conseil, est une information fournie à l’algorithme par ce qui s’appelle classiquement en informatique un oracle, c’est-à-dire un dispositif omniscient à nouveau, infaillible. Autrement dit, dans ce modèle, on a l’assurance que le conseil est toujours parfait, que l’erreur qui lui est associée est toujours nulle. On s’intéresse au compromis entre la taille du conseil, qui est le nombre de bits nécessaires pour représenter ce conseil en binaire, et le ratio de compétitivité. Dans le cas du problème de l’ascenseur, on peut remarquer qu’en utilisant un seul bit pour le conseil, on peut résoudre le problème de façon optimale : supposons que la réception connaisse le moment exact où l’ascenseur arrivera, dans ce cas le bit de conseil encode le fait que nous devions attendre l’ascenseur ou emprunter les escaliers sans attendre. Pour le problème de la vente d’une maison, un bit de conseil peut nous offrir l’information suivante : oui ou non, « une offre d’un montant supérieur ou égal à \(B\) nous sera faite dans le futur » où \(B\) est un montant donné, par exemple \(B = 300 K€\). Si on autorise plus de bits pour représenter le conseil, on peut obtenir une meilleure précision si le conseil est une information de la forme « une offre comprise entre \(B_1\) et \(B_2\) sera proposée » et ici les bits de conseil encodent les deux valeurs \(B_1\) et \(B_2\). Avec ce type d’information, les décisions algorithmiques peuvent être améliorées, ce qui conduit à de meilleurs ratios de compétitivité.

Le modèle de complexité avec conseil étant un modèle purement mathématique, il peut déboucher sur des questions intéressantes mais a peu de lien avec le monde réel et les applications pratiques. Par exemple, dans le monde réel, il paraît inconcevable qu’une prédiction corresponde parfaitement à la vérité à venir : par exemple, seriez-vous prêt ou prête à attendre un ascenseur un jour entier et à faire confiance à une personne qui vous assurerait qu’il va arriver « d’une minute à l’autre » ? Vous savez que, dans les applications réelles, fournir un conseil est un processus entaché d’erreur, de façon inhérente, comme tout ce qui est basé sur des estimations et sur l’utilisation d’un historique ; il suffit de songer aux prévisions météorologiques pour s’en convaincre. De plus, dans le monde réel, on ne se préoccupe guère de la taille du conseil, ce qui compte est sa qualité. 

Ces considérations sur la qualité des conseils sont prises en compte dans un modèle différent et beaucoup plus récent (voir référence [3]) qui a été développé dans le cadre de l’apprentissage machine ou Machine Learning (ML) en anglais, il s’agit de la seconde approche possible. Dans ce modèle, à chaque prédiction est associée une erreur, qui n’est pas connue de l’algorithme en ligne. Pour le problème de l’ascenseur, la prédiction peut être par exemple « l’ascenseur arrivera au cours des 3 prochaines minutes » ; si l’ascenseur arrive au bout de 4 minutes, alors l’erreur est de 1 minute. L’objectif est alors de concevoir des algorithmes dont le ratio de compétitivité s’améliore quand l’erreur de prédiction s’amenuise, mais ne se dégrade pas trop quand cette erreur augmente. Optimiser la performance d’un algorithme devient un problème d’optimisation compliqué : il faut être capable d’exprimer le ratio de compétitivité en fonction de l’erreur de prédiction. Cela permet de concevoir des algorithmes intéressants à la fois en théorie et en pratique, tout en conservant le cadre mathématique rigoureux de l’analyse compétitive.

Ce nouveau modèle a d’ores et déjà permis d’étudier plusieurs problèmes d’optimisation en ligne avec prédiction. Ce modèle combine à la fois la rigueur de l’analyse et l’applicabilité en pratique. La grande majorité des algorithmes qui ont été proposés dans ce cadre sont évalués non seulement d’un point de vue théorique, mais également expérimentalement, sur des données réelles : cela manquait jusqu’à présent dans ce domaine.

Conclusion

Il reste encore beaucoup de questions à explorer à l’avenir autour du modèle ML de calcul en ligne. Parmi les défis à résoudre, on aimerait que l’art d’effectuer des prédictions puisse être appris par une machine. Sans entrer dans les détails, cela signifie que l’on peut produire des prédictions de qualité en observant le passé, de la même façon que nous pourrions estimer le temps qu’il faudra pour réparer l’ascenseur en nous basant sur les pannes passées. 

Parfois, les prédictions peuvent aussi être obtenues en réponse à des questions concernant les entrées futures. Par exemple, dans le problème de l’ascenseur, à la place d’une prédiction telle que l’affirmation « l’ascenseur va arriver dans 2 minutes », on pourrait obtenir une forme plus « faible » de prédiction en demandant « l’ascenseur va-t-il arriver au cours des 5 prochaines minutes ? ». On obtient un problème relié mais différent, et toujours aussi intéressant. Pour illustrer cette situation par un autre exemple, imaginons que vous jouiez au jeu des « 20 questions » : une personne A effectue un choix, par exemple elle choisit un personnage historique, et une personne B peut poser 20 questions, auxquelles A répondra par « oui » ou « non », et B devra deviner qui a été choisi. Vous pouvez jouer à ce jeu, connu sous le nom de « Akinator web game ». Supposons maintenant que le joueur ou la joueuse A donne quelques réponses fausses, soit par ignorance pure, soit délibérément pour compliquer la tâche de B. Est-ce que le joueur ou la joueuse B peut quand même trouver la réponse, même si certaines réponses sont incorrectes ? Ce type d’interrogation est au cœur du calcul tolérant aux pannes et pourra se révéler fort utile dans l’analyse, encore à inventer, des algorithmes avec prédiction.

L’analyse compétitive des algorithmes en ligne est née du besoin de pouvoir établir des résultats concernant les performances d’un algorithme en ligne quand on ne sait rien, ou si peu, sur ce qui se produira dans le futur. Au fil des ans, l’évaluation théorique des algorithmes en ligne a évolué pour ne plus se limiter à ce qui se passe dans le pire des cas, mais aussi dans les cas plus « réalistes », quelle que soit la signification tangible que l’on puisse mettre derrière ce terme. Cependant, s’il y a une leçon que la pandémie de Covid peut nous offrir, c’est que l’étude et les garanties établies pour les pires des cas possibles ne sont pas prêtes à être détrônées : en effet, la sagesse ancestrale qui invite à « espérer le meilleur et se préparer au pire » reste le plan d’action le plus sensé. Il est fort probable que cette optique prévale encore plus à l’avenir pour la conception et l’évaluation des algorithmes.