Войти
В теории алгоритмической информации, алгоритмическая вероятность, также известная как Соломонов. вероятность - это математический метод присвоения априорной вероятности данному наблюдению. Его изобрел Рэй Соломонов в 1960-х годах. Он используется в теории индуктивного вывода и анализе алгоритмов. В своей общей теории индуктивного вывода Соломонов использует полученные по этой формуле в правиле Байеса для предсказания.
В используемом математическом формализме наблюдения имеют форма конечных двоичных строк, а универсальный априор - это распределение вероятностей по набору конечных двоичных строк. Априор универсален в смысле вычислимости по Тьюрингу, т.е. ни одна строка не имеет нулевой вероятности. Это не вычислимо, но его можно приблизить.
.
Алгоритмическая вероятность связана со следующими вопросами: Учитывая совокупность данных о каком-то явлении, которое мы хотим понять, как мы можем выбрать наиболее вероятное гипотеза о том, как это было вызвано из всех возможных гипотез, и как мы можем оценить различные гипотезы? Как мы можем предсказать будущие данные и как измерить вероятность того, что этот прогноз окажется верным?
Четыре основных источника алгоритмической вероятности Соломонова: бритва Оккама, принцип множественных объяснений Эпикура, современная теория вычислений (например, использование универсальной теории Тьюринга машина ) и правило Байеса для предсказания.
бритва Оккама и принцип Эпикура по сути являются двумя разными нематематическими приближениями.
В основе всеобщего априорного значения лежит абстрактная модель компьютер, такой как универсальная машина Тьюринга. Подойдет любой абстрактный компьютер, если он является полным по Тьюрингу, то есть каждая конечная двоичная строка имеет хотя бы одну программу, которая будет вычислять ее на абстрактном компьютере.
Абстрактный компьютер используется для придания точного значения фразе «простое объяснение». В используемом формализме объяснения или теории явлений - это компьютерные программы, которые генерируют строки наблюдений при запуске на абстрактном компьютере. Простое объяснение - небольшая компьютерная программа. Сложное объяснение - это длинная компьютерная программа. Более вероятны простые объяснения, поэтому строка наблюдения с высокой вероятностью - это строка, созданная короткой компьютерной программой или, возможно, любой из большого количества немного более длинных компьютерных программ. Строка наблюдения с низкой вероятностью может быть создана только длинной компьютерной программой.
Эти идеи можно конкретизировать, а вероятности использовать для построения априорного распределения вероятностей для данного наблюдения. Основная причина, по которой Соломонов изобрел это априорное значение, состоит в том, что его можно использовать в правиле Байеса, когда фактическое априорное значение неизвестно, что позволяет прогнозировать в условиях неопределенности. Он предсказывает наиболее вероятное продолжение этого наблюдения и дает меру того, насколько вероятно это продолжение.
Хотя результат наблюдения (и его расширение) не поддается вычислению, существует компьютерный алгоритм Levin Search, которое при работе в течение более длительных периодов времени будет генерировать последовательность приближений, которые сходятся к.
Соломонов доказал, что это распределение машинно-инвариантно с постоянным множителем (так называемая теорема инвариантности ).
Соломонов изобрел концепцию алгоритмической вероятности с связанной с ней теоремой инвариантности примерно в 1960 году, опубликовав отчет о ней: «Предварительный отчет по общей теории индуктивного вывода». Он более полно разъяснил эти идеи в 1964 году в статье «Формальная теория». индуктивного вывода », Часть I и Часть II.
Соломонофф описал универсальный компьютер со случайно сгенерированной входной программой. Программа вычисляет некоторый, возможно, бесконечный выход. Распределение наблюдаемости - это распределение вероятностей для всех возможных выходных строк со случайным входом.
Алгоритмическая вероятность любого заданного конечного выходного префикса q - это сумма вероятностей программ, которые вычисляют что-то, начинающееся с q. Некоторые длинные объекты с короткими программами имеют высокую вероятность.
Алгоритмическая вероятность - главный компонент теории индуктивного вывода, теории предсказания, основанной на наблюдениях; он был изобретен с целью использования его для машинного обучения; учитывая последовательность символов, какой из них будет следующим? Теория Соломонова дает ответ, в определенном смысле оптимальный, хотя и невыполнимый. В отличие от, например, неформальной теории индуктивного вывода Карла Поппера, теория Соломонова математически строга.
Алгоритмическая вероятность тесно связана с понятием колмогоровской сложности. Введение Колмогоровым сложности было мотивировано теорией информации и проблемами случайности, в то время как Соломонов ввел алгоритмическую сложность по другой причине: индуктивным рассуждениям. Единая универсальная априорная вероятность, которая может быть заменена каждой действительной априорной вероятностью в правиле Байеса, была изобретена Соломоновым с колмогоровской сложностью в качестве побочного продукта. смысл, но время вычислений может быть бесконечным. Одним из способов решения этой проблемы является вариант алгоритма поиска Леонида Левина, который ограничивает время, затрачиваемое на вычисление успешности возможных программ, с более короткими программами, отводящими больше времени. Другие методы ограничения пространства поиска включают обучающие последовательности.
