|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
On Algorithmic Statistics for Space-bounded Algorithmsстатья
- Автор: Milovanov A.
- Журнал: Theory of Computing Systems
- Год издания: 2018
- Издательство: Springer Verlag
- Местоположение издательства: Germany
- DOI: 10.1007/s00224-018-9845-6
- Аннотация: Algorithmic statistics looks for models of observed data that are good in the following sense: a model is simple (i.e., has small Kolmogorov complexity) and captures all the algorithmically discoverable regularities in the data. However, this idea can not be used in practice as is because Kolmogorov complexity is not computable. In this paper we develop an algorithmic version of algorithmic statistics that uses space-bounded Kolmogorov complexity. We prove a space-bounded version of a basic result from “classical” algorithmic statistics, the connection between optimality and randomness deficiences. The main tool is the Nisan–Wigderson pseudo-random generator. An extended abstract of this paper was presented at the 12th International Computer Science Symposium in Russia. Алгоритмическая статистика - наука об объяснениях (гипотезах) для некоторых данных. Гипотеза считается хорошей, если она простая (т.е. имеет маленькую колмогоровскую сложность) и при этом охватывает все закономерности в данных, которые можно выявить алгоритмическим образом. Эта идея не может быть использована на практике, т.к. колмогоровская сложность является невычислимой функцией. В этой статье мы развиваем версию алгоритмической статистики, которая использует Колмогоровскую сложность с ограничением на память. Для такого варианта сложности мы доказываем аналого одного из результатов классической алгоритмической статистики о связи между дефектом случайности и дефектом оптимальности. Основным инструментом доказательства является генератор Нисана-Вигдерсона. Это статья является расширенной версией статьи, принятой на конференции CSR 2017.
- Добавил в систему: Верещагин Николай Константинович