Artículo
Bienvenu, L.; Figueira, S.; Monin, B.; Shen, A. "Algorithmic identification of probabilities is hard" (2018) Journal of Computer and System Sciences. 95:98-108
Estamos trabajando para incorporar este artículo al repositorio
Consulte la política de Acceso Abierto del editor
Abstract:
Reading more and more bits from an infinite binary sequence that is random for a Bernoulli measure with parameter p, we can get better and better approximations of p using the strong law of large numbers. In this paper, we study a similar situation from the viewpoint of inductive inference. Assume that p is a computable real, and we have to eventually guess the program that computes p. We show that this cannot be done computably, and extend this result to more general computable distributions. We also provide a weak positive result showing that looking at a sequence X generated according to some computable probability measure, we can guess a sequence of algorithms that, starting from some point, compute a measure that makes X Martin-Löf random. © 2018 Elsevier Inc.
Registro:
| Documento: | Artículo |
| Título: | Algorithmic identification of probabilities is hard |
| Autor: | Bienvenu, L.; Figueira, S.; Monin, B.; Shen, A. |
| Filiación: | LIRMM, CNRS, Université de Montpellier, 161 rue Ada, Cedex 5, Montpellier, 34095, France Universidad de Buenos Aires, CONICET, Pabellón I – Ciudad Universitaria, Buenos Aires, Argentina LACL, Université Paris 12, 61 avenue du Général de Gaulle, Créteil Cedex, 94010, France |
| Palabras clave: | Algorithmic learning theory; Algorithmic randomness; Computer networks; Systems science; Algorithmic identification; Algorithmic learning theories; Algorithmic randomness; Bernoulli; Computable reals; Inductive inference; Probability measures; Strong law of large numbers; Binary sequences |
| Año: | 2018 |
| Volumen: | 95 |
| Página de inicio: | 98 |
| Página de fin: | 108 |
| DOI: | http://dx.doi.org/10.1016/j.jcss.2018.01.002 |
| Título revista: | Journal of Computer and System Sciences |
| Título revista abreviado: | J. Comput. Syst. Sci. |
| ISSN: | 00220000 |
| CODEN: | JCSSB |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00220000_v95_n_p98_Bienvenu |
Referencias:
- Bienvenu, L., Gács, P., Hoyrup, M., Rojas, C., Shen, A., Algorithmic tests and randomness with respect to a class of measures (2011) Proc. Steklov Inst. Math., 274, pp. 34-89
- Bienvenu, L., Merkle, W., Constructive equivalence relations for computable probability measures (2009) Ann. Pure Appl. Logic, 160, pp. 238-254
- Case, J., Smith, C., Comparison of identification criteria for machine inductive inference (1983) Theor. Comput. Sci., 25, pp. 193-220
- Gács, P., Uniform test of algorithmic randomness over a general space (2005) Theor. Comput. Sci., 341 (1-3), pp. 91-137
- Juedes, D., Lutz, J., Weak completeness in E1 and E2 (1995) Theor. Comput. Sci., 143 (1), pp. 149-158
- Li, M., Vitányi, P., An Introduction to Kolmogorov Complexity and Its Applications (2008) Texts in Computer Science, , 3rd edition Springer-Verlag New York
- Odifreddi, P., Classical Recursion Theory: Volume II (1999), Elsevier; Vitányi, P., Chater, N., Algorithmic identification of probabilities (2013), https://arxiv.org/abs/1311.7385v1; Vitányi, P.M., Chater, N., Identification of probabilities (2017) J. Math. Psychol., 76, pp. 13-24
- Weihrauch, K., Computable Analysis (2000), Springer Berlin; Zeugmann, T., Zilles, S., Learning recursive functions: a survey (2008) Theor. Comput. Sci., 397, pp. 4-56
Citas:
---------- APA ----------
Bienvenu, L., Figueira, S., Monin, B. & Shen, A. (2018) . Algorithmic identification of probabilities is hard. Journal of Computer and System Sciences, 95, 98-108.http://dx.doi.org/10.1016/j.jcss.2018.01.002
---------- CHICAGO ----------
Bienvenu, L., Figueira, S., Monin, B., Shen, A. "Algorithmic identification of probabilities is hard" . Journal of Computer and System Sciences 95 (2018) : 98-108.http://dx.doi.org/10.1016/j.jcss.2018.01.002
---------- MLA ----------
Bienvenu, L., Figueira, S., Monin, B., Shen, A. "Algorithmic identification of probabilities is hard" . Journal of Computer and System Sciences, vol. 95, 2018, pp. 98-108.http://dx.doi.org/10.1016/j.jcss.2018.01.002
---------- VANCOUVER ----------
Bienvenu, L., Figueira, S., Monin, B., Shen, A. Algorithmic identification of probabilities is hard. J. Comput. Syst. Sci. 2018;95:98-108.http://dx.doi.org/10.1016/j.jcss.2018.01.002
