La probabilité algorithmique, également connue sous le nom de théorie de l'inférence inductive de Solomonoff, est un cadre formel pour attribuer des probabilités aux séquences possibles d'observations. Elle fournit une définition mathématique de la probabilité qu'une chaîne binaire donnée soit produite par une machine de Turing universelle, en fonction de la longueur du programme de la machine. La théorie a été introduite par Ray Solomonoff dans les années 1960 et affinée plus tard par Leonid Levin et d'autres, formant une pierre angulaire de la théorie algorithmique de l'information et influençant des domaines tels que l'apprentissage automatique et intelligence artificielle.
L'idée centrale est que la probabilité d'une chaîne est proportionnelle à 2 élevé à la puissance négative de la longueur de son programme le plus court, un concept connu sous le nom de complexité de Kolmogorov. Cela favorise intrinsèquement les explications plus simples, car les programmes plus courts reçoivent une probabilité plus élevée. La probabilité algorithmique est non calculable dans le cas général, mais elle sert d'idéal théorique pour la prédiction et la reconnaissance de formes, souvent contrastée avec des approches pratiques comme apprentissage automatique et apprentissage profond.
Développement historique
Ray Solomonoff a décrit pour la première fois la probabilité algorithmique dans un rapport technique de 1960 et a publié un article fondateur en 1964 intitulé « A Formal Theory of Inductive Inference ». Son travail visait à résoudre le problème de l'induction en fournissant un a priori universel pour toutes les séquences possibles. Dans les années 1970, Leonid Levin a contribué indépendamment en définissant le concept connexe de recherche de Levin et la distribution universelle, qui relie la probabilité algorithmique à la complexité computationnelle. Plus tard, dans les années 1980 et 1990, des chercheurs comme Ming Li et Paul Vitányi ont intégré ces idées dans le domaine plus large de la théorie algorithmique de l'information, publiant des textes complets qui ont formalisé les relations entre la complexité de Kolmogorov, la probabilité algorithmique et l'induction universelle.
Définition formelle
Pour une machine de Turing universelle U, la probabilité algorithmique d'une chaîne binaire x est définie comme la somme des probabilités de tous les programmes p qui produisent x puis s'arrêtent. Formellement, P_U(x) = Σ_{p: U(p)=x} 2^{-|p|}, où |p| est la longueur du programme p en bits. Cette somme converge car la probabilité totale sur tous les programmes est bornée par l'inégalité de Kraft. La version sans préfixe, où aucun programme n'est un préfixe d'un autre, garantit que la somme est bien définie et conduit à l'a priori universel. La probabilité algorithmique est liée à la complexité de Kolmogorov K(x) par l'inégalité -log P_U(x) ≤ K(x) + O(1), ce qui signifie que les chaînes de faible complexité ont une probabilité élevée.
Lien avec le rasoir d'Occam
La probabilité algorithmique fournit une justification mathématique rigoureuse du rasoir d'Occam, le principe selon lequel les explications plus simples sont plus susceptibles d'être correctes. Dans ce cadre, la simplicité est mesurée par la longueur du programme, et les programmes plus courts se voient attribuer des probabilités a priori exponentiellement plus élevées. Ce n'est pas un choix arbitraire mais découle des propriétés des machines de Turing universelles et de l'exigence que l'a priori soit calculable et cohérent. La théorie implique que, parmi toutes les hypothèses cohérentes avec les données observées, celle avec la description la plus courte est la plus probable, un principe qui sous-tend de nombreux algorithmes pratiques en apprentissage automatique et dans l'entraînement de grands modèles de langage.
Rôle dans l'inférence inductive
Le cadre de Solomonoff formalise l'inférence inductive comme une mise à jour bayésienne sur toutes les hypothèses calculables possibles. Étant donné une séquence de données observées, la probabilité a posteriori de chaque hypothèse est proportionnelle à son a priori (probabilité algorithmique) multiplié par sa vraisemblance. Cela donne une méthode de prédiction universelle qui est optimale en ce sens qu'elle converge vers le véritable processus générateur de données avec une probabilité de un, à condition que le processus soit calculable. Ce résultat est connu sous le nom de théorème de complétude de Solomonoff. Cependant, la méthode n'est pas directement implémentable car elle nécessite de sommer sur une infinité de programmes, ce qui la rend computationnellement intraitable. Néanmoins, elle sert de référence théorique pour évaluer les algorithmes de prédiction pratiques.
Relation avec la recherche universelle et la recherche de Levin
La probabilité algorithmique est étroitement liée à la recherche de Levin, une méthode pour résoudre des problèmes en cherchant parmi les programmes dans l'ordre de leur probabilité. La recherche de Levin utilise la distribution universelle pour prioriser les programmes à haute probabilité algorithmique, atteignant une complexité temporelle quasi optimale pour les problèmes ayant des solutions courtes. Cette connexion relie la probabilité algorithmique à la théorie de la complexité computationnelle, montrant que l'a priori universel peut guider une recherche efficace dans les systèmes d'intelligence artificielle. Le concept a influencé la conception des architectures de réseaux de neurones et des méthodes d'entraînement, bien que les approches modernes comme les modèles transformers reposent sur des a priori empiriques plutôt que sur des probabilités algorithmiques explicites.
Applications en intelligence artificielle
Bien que la probabilité algorithmique ne soit pas directement utilisée dans la plupart des systèmes d'IA contemporains, ses principes ont façonné les fondements théoriques. Par exemple, le principe de longueur de description minimale (MDL), dérivé de la probabilité algorithmique, est appliqué dans la sélection de modèles et la régularisation en apprentissage automatique. L'inférence bayésienne en apprentissage profond intègre souvent des a priori qui approximent la simplicité, faisant écho aux idées de Solomonoff. La recherche sur la sécurité et l'interprétabilité de l'intelligence artificielle fait parfois référence à la probabilité algorithmique pour plaider en faveur de modèles plus simples. Des entreprises comme OpenAI et Google DeepMind ont exploré des concepts connexes dans des travaux théoriques, bien que les implémentations pratiques reposent sur la descente de gradient stochastique et des données à grande échelle plutôt que sur une recherche explicite de programmes.
Limites et critiques
La probabilité algorithmique fait face à plusieurs limitations fondamentales. Elle est non calculable, ce qui signifie qu'aucun algorithme ne peut calculer la probabilité exacte pour toutes les chaînes. La dépendance à une machine de Turing universelle spécifique introduit une constante additive qui affecte les probabilités absolues, bien que les classements relatifs soient indépendants de la machine à une constante près. Les critiques soutiennent que le cadre suppose un modèle computationnel fixe et ne tient pas compte de la complexité de l'observateur ou de l'environnement. De plus, l'a priori attribue une probabilité nulle aux séquences non calculables, ce qui limite son applicabilité aux données réelles qui peuvent ne pas être générées par des processus calculables. Ces problèmes ont conduit certains chercheurs à développer des cadres alternatifs, tels que les modèles de processus stochastiques et les méthodes bayésiennes empiriques, qui sont plus traitables en pratique.
Influence sur la recherche moderne
Malgré ses limites, la probabilité algorithmique continue d'influencer la recherche théorique en apprentissage automatique et en sciences cognitives. Elle a inspiré des travaux sur l'induction universelle, l'aléatoire algorithmique et les fondements de la IA générative. Des chercheurs d'institutions comme MIT CSAIL et Stanford AI Lab ont étudié les connexions entre la probabilité algorithmique et la généralisation des réseaux de neurones. Le concept apparaît également dans les discussions sur l'intelligence artificielle générale, où il est proposé comme composant d'un agent d'apprentissage universel. Des travaux récents sur l'interprétabilité des grands modèles de langage ont établi des parallèles entre la prédiction du prochain jeton et l'induction de Solomonoff, bien que les mécanismes pratiques diffèrent considérablement.
Voir aussi
- Complexité de Kolmogorov (concept connexe, bien que non inclus dans la liste fournie, utiliser apprentissage automatique comme lien)
- intelligence artificielle
- apprentissage profond
- réseau de neurones
Références
- Solomonoff, R. J. (1964). « A Formal Theory of Inductive Inference. » Information and Control, 7(1), 1-22.
- Li, M., & Vitányi, P. (2008). « An Introduction to Kolmogorov Complexity and Its Applications. » Springer.
- Hutter, M. (2005). « Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability. » Springer.