Probabilité algorithmique

En théorie algorithmique de l'information, la probabilité algorithmique, aussi connue comme probabilité de Solomonoff, est une méthode permettant d’assigner une probabilité à une observation donnée. Il a été inventé par Ray Solomonoff dans les années 1960[1]. Elle est utilisée dans la théorie de l'inférence inductive et dans l'analyse des algorithmes. En particulier, dans sa thèorie de l'induction, Solomonoff utilise une telle formulation pour exprimer la probabilité a priori dans la formule de Bayes[2].

Dans le formalisme mathématique utilisé, les observations se présentent sous la forme de chaînes binaires finies et l'a priori universel est une distribution de probabilité sur l'ensemble des chaînes binaires finies. Cet a priori est universel dans au sens de théorie de la calculabilité, c'est-à-dire qu'aucune chaîne n'a une probabilité nulle. Ce n'est pas calculable, mais on peut en faire une approximation[3].

Principe général

À partir d'un ensemble de données issues d'un phénomène étudié, la probabilité algorithmique vise à déterminer la manière de sélectionner l'hypothèse la plus probable de sa cause parmi toutes les hypothèses possibles et la manière d'évaluer les différentes hypothèses. Par suite, il s'agit de pouvoir prédire les données futures et mesurer la probabilité que cette prévision soit correcte.

Les quatre principales sources d'inspiration de Solomonoff étaient[4] le rasoir d'Ockham, la thèse de la pluralité des mondes d'Épicure, les machines de Turing universelles et la formule de Bayes.

Solomonoff a inventé le concept de probabilité algorithmique avec son théorème d'invariance associé vers 1960[5] et le publia dans un rapport[1] . Il a clarifié ces idées plus en détail en 1964 dans deux articles[6],[7].

Références
  1. Solomonoff, R., "A Preliminary Report on a General Theory of Inductive Inference", Report V-131, Zator Co., Cambridge, Ma. (Nov. 1960 revision of the Feb. 4, 1960 report).
  2. Li, M. and Vitanyi, P., An Introduction to Kolmogorov Complexity and Its Applications, 3rd Edition, Springer Science and Business Media, N.Y., 2008
  3. Hutter, M., Legg, S., and Vitanyi, P., "Algorithmic Probability", Scholarpedia, 2(8):2572, 2007.
  4. Li and Vitanyi, 2008, p. 347
  5. Solomonoff, R., "The Discovery of Algorithmic Probability", Journal of Computer and System Sciences, Vol. 55, No. 1, pp. 73-88, August 1997.
  6. Solomonoff, R., "A Formal Theory of Inductive Inference, Part I". Information and Control, Vol 7, No. 1 pp 1-22, March 1964.
  7. Solomonoff, R., "A Formal Theory of Inductive Inference, Part II" Information and Control, Vol 7, No. 2 pp 224–254, June 1964.

Voir aussi
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.