Si les techniques d'apprentissage automatique continuent de s'améliorer, quel sera le rôle de l'algorithmique à l'avenir?

Regardons l'avenir dans une trentaine d'années. Soyons optimistes et supposons que les domaines liés à l'apprentissage automatique continuent de se développer aussi rapidement que ce que nous avons vu au cours des 10 dernières années. Ce serait formidable, mais alors quel serait le rôle de l'algorithmique traditionnelle dans un tel avenir?

Ici, par «algorithmique traditionnelle», je me réfère au processus habituel que nous suivons dans TCS: formaliser un problème de calcul bien défini , concevoir des algorithmes pour résoudre le problème et prouver des garanties de performance formelles .

Maintenant, quels sont les domaines d'application dans lesquels nous devons également utiliser la conception et l'analyse d'algorithmes traditionnels à l'avenir, et il est très peu probable que des progrès de l'apprentissage automatique rendent la algorithmique traditionnelle pour la plupart non pertinente?

Au début, cela peut sembler une question stupide: bien sûr, nous devrons être en mesure de faire du tri, de la recherche, de l'indexation, etc. à l'avenir également! Bien sûr, nous devrons être capables de faire des transformées de Fourier efficacement, multiplier les grandes matrices, trouver les chemins les plus courts, résoudre les problèmes d'optimisation linéaire!

Mais là encore, une fois que vous commencez à approfondir les applications dans lesquelles nous utilisons traditionnellement les algorithmes que nous concevons, il n'est pas du tout clair que la conception et l'analyse d'algorithmes traditionnels soient la bonne réponse à de tels problèmes: dans les applications liées à la recherche , en général, nous sommes intéressés à trouver quelque chose qui correspond étroitement à un être humain dans un sens vague et mal défini (par exemple, une similitude sémantique), et non quelque chose qui est optimal au sens mathématique (par exemple, une distance d'édition minimale). Dans les applications liées à la planification d'itinéraire, généralement, nous sommes intéressés à trouver des itinéraires qui sont bons sur la base d'exemples (par exemple, d'autres personnes le préfèrent), pas des itinéraires qui sont optimaux dans un sens mathématique (par exemple, la distance la plus courte ou le prix le moins cher). Et une fois que vous avez une composante humaine vague et mal définie dans l'image, il pourrait être préférable d'essayer d'enseigner à l'ordinateur à produire de bonnes réponses basées sur des exemples, au lieu d'essayer de laisser un chercheur du SDC venir avec un problème de calcul formel que nous pouvons résoudre au moyen de la conception et de l'analyse d'algorithmes traditionnels.

Alors, quels sont les domaines d'application (de préférence les applications industrielles réelles et directes) dans lesquels il est absolument clair que ce que nous avons fait dans le passé par l'algorithmique sera également la bonne manière (et la seule manière possible) de progresser dans le futur?

Les algorithmes utilisés comme sous-programmes dans les techniques d'apprentissage automatique semblent être un candidat à l'épreuve du temps évident, mais cela dépend fortement de la technique d'apprentissage automatique particulière que nous utilisons, et comme nous l'avons vu au cours des dix dernières années, cela pourrait rapidement changer .

C'est une question qui me hante récemment, je suis donc ravie que vous la posiez.
Cependant, je suis moins intéressé par la classification des domaines d'application pour lesquels le machine learning dominera l'approche informatique que par l'impact sur l'avancement dans le domaine des algorithmes (traditionnels). À quel type de recherche sur les «algorithmes fabriqués par l'homme» serons-nous encore intéressés dans 30 ans? Certes, c'est la question la plus difficile à répondre en général, car c'est l'application qui détermine la qualité du résultat recherchée.

Je pense que les algorithmes d'énumération compteront parmi les survivants. Il restera nécessaire de tester toutes les entrées d'une puce ou d'effectuer une recherche exhaustive. L'attention spécifique à l'objet, la conception finement ajustée requise pour générer chaque instance d'objet exactement (ou au moins) une fois; et l'amplification du temps d'exécution de tout effort inutile (il peut y avoir un nombre exponentiel d'instances, en fonction de la description de l'objet) - ces facteurs me rendent sceptique qu'un processus d'apprentissage automatisé à usage général puisse correspondre à un intelligent, solution spécialement conçue dans ce domaine.

Le problème avec les solutions d'apprentissage automatique est qu'il n'y a aucun moyen de savoir si elles ont vraiment calculé ce que vous vouliez.

Je m'attendrais à ce qu'ils prennent le relais dans tous les domaines où un mauvais résultat n'est pas catastrophique (c'est-à-dire partout où nous utilisons actuellement des heuristiques) ou le résultat peut être facilement vérifié (problèmes de recherche pour lesquels vous savez qu'une solution existe (car vérifier "là n'est pas une solution "pourrait être difficile)).

Pour les domaines restants, je m'attendrais à ce que les algorithmes soient prouvés formellement (par exemple en utilisant Coq / Gallina) de plus en plus souvent. Avec un peu de chance, l'apprentissage automatique rendra les preuves dans ces systèmes aussi simples que sur papier (ou même plus faciles). Il pourrait même arriver au point où les humains n'écrivent que la spécification et l'algorithme et sa preuve d'exactitude sont trouvés en utilisant l'apprentissage automatique. (Notez que l'algorithme lui-même n'utilise pas l'apprentissage automatique, mais lui et ses preuves d'exactitude ont été trouvés en utilisant l'apprentissage automatique)

Nous pouvons donc nous retrouver à n'écrire que des assistants de preuve, des spécifications de programme et des algorithmes d'apprentissage automatique.