Индукция Соломонова: математическая теория вывода закономерностей на основе вероятности и теории вычислений. Оптимальное предсказание, несмотря на невычислимость.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Теория индуктивного вывода Соломонова — это математическая теория индукции, предложенная Рэем Соломонофом и основанная на теории вероятностей и теоретической информатике. По сути, индукция Соломонова выводит апостериорную вероятность любой вычислимой теории, учитывая последовательность наблюдаемых данных. Эта апостериорная вероятность выводится из правила Байеса и некоторого универсального априорного распределения, то есть такого априорного распределения, которое присваивает положительную вероятность любой вычислимой теории. Соломонов доказал, что эта индукция невычислима, но отметил, что "эта невычислимость носит весьма безобидный характер" и что она "никак не препятствует её использованию для практического предсказания", присваивая более высокую априорную вероятность теориям, требующим более короткого алгоритмического описания.
Solomonoff's theory of inductive inference is a mathematical theory of induction introduced by Ray Solomonoff, based on probability theory and theoretical computer science. In essence, Solomonoff's induction derives the posterior probability of any computable theory, given a sequence of observed data. This posterior probability is derived from Bayes' rule and some universal prior, that is, a prior that assigns a positive probability to any computable theory. Solomonoff proved that this induction is incomputable, but noted that "this incomputability is of a very benign kind", and that it "in no way inhibits its use for practical prediction". by assigning larger prior credences to theories that require a shorter algorithmic description.
Философские
Теория базируется на философских основаниях и была разработана Рэем Соломоновым примерно в 1960 году. Это математически формализованное сочетание принципа бритвы Оккама: для вычисления вероятности следующего наблюдения используются все вычислимые теории, идеально описывающие предыдущие наблюдения, при этом более коротким вычислимым теориям придается больший вес. Универсальный искусственный интеллект Маркуса Хаттера опирается на эту теорию для расчета ожидаемой ценности действия.
The theory is based in philosophical foundations, and was founded by Ray Solomonoff around 1960. It is a mathematically formalized combination of Occam's razor All computable theories which perfectly describe previous observations are used to calculate the probability of the next observation, with more weight put on the shorter computable theories. Marcus Hutter's universal artificial intelligence builds upon this to calculate the expected value of an action.
Принцип
Индукция Соломоноффа рассматривается как вычислительная формализация чистого байесианства. Другое направление индуктивного вывода основано на модели обучения в пределе, предложенной Э. Марком Голдом в 1967 году, и с тех пор породило множество моделей обучения. Общий сценарий следующий: задан класс S вычислимых функций. Существует ли обучающийся (то есть рекурсивный функционал), который для любого ввода вида (f(0), f(1), ..., f(n)) выдает гипотезу (индекс e относительно заранее согласованной допустимой нумерации всех вычислимых функций; индексированная функция должна быть согласована с заданными значениями f)? Обучающийся M изучает функцию f, если почти все его гипотезы имеют один и тот же индекс e, который генерирует функцию f; M изучает S, если M изучает каждую функцию f из S. Основные результаты заключаются в том, что все рекурсивно перечислимые классы функций могут быть изучены, в то время как класс REC всех вычислимых функций не может быть изучен. Рассмотрено множество связанных моделей, а также изучение классов рекурсивно перечислимых множеств по положительным данным – тема, исследуемая начиная с основополагающей работы Голда 1967 года. Дальнейшее развитие подхода Голда находит отражение в теории обобщенных сложностей Колмогорова, разработанной Шмидхубером, которые представляют собой разновидность суперрекурсивных алгоритмов.
Solomonoff's induction has been argued to be the computational formalization of pure Bayesianism. Another direction of inductive inference is based on E. Mark Gold's model of learning in the limit from 1967 and has developed since then more and more models of learning. The general scenario is the following: Given a class S of computable functions, is there a learner (that is, recursive functional) which for any input of the form (f(0),f(1), ,f(n)) outputs a hypothesis (an index e with respect to a previously agreed on acceptable numbering of all computable functions; the indexed function may be required consistent with the given values of f). A learner M learns a function f if almost all its hypotheses are the same index e, which generates the function f; M learns S if M learns every f in S. Basic results are that all recursively enumerable classes of functions are learnable while the class REC of all computable functions is not learnable. Many related models have been considered and also the learning of classes of recursively enumerable sets from positive data is a topic studied from Gold's pioneering paper in 1967 onwards. A far reaching extension of the Gold’s approach is developed by Schmidhuber's theory of generalized Kolmogorov complexities, which are kinds of super recursive algorithms.