Алгоритмическая вероятность - Algorithmic probability

В алгоритмической теории информации , алгоритмическая вероятности , также известная как вероятность Соломонов , представляет собой математический метод присвоения предшествующей вероятности для данного наблюдения. Он был изобретен Рэем Соломоновым в 1960-х годах. Он используется в теории индуктивного вывода и анализе алгоритмов. В своей общей теории индуктивного вывода Соломонов использует априорность, полученную по этой формуле, в правиле предсказания Байеса .

В используемом математическом формализме наблюдения имеют форму конечных двоичных строк, а универсальный априор - это распределение вероятностей по набору конечных двоичных строк. Априор универсален в смысле вычислимости по Тьюрингу, т.е. ни одна строка не имеет нулевой вероятности. Это не вычислимо, но можно приблизить.


Обзор

Алгоритмическая вероятность связана со следующими вопросами: Учитывая совокупность данных о каком-то явлении, которое мы хотим понять, как мы можем выбрать наиболее вероятную гипотезу о том, как оно было вызвано из всех возможных гипотез, и как мы можем оценить различные гипотезы? Как мы можем предсказать будущие данные и как измерить вероятность того, что этот прогноз окажется правильным?

Четыре основных источника вдохновения для алгоритмической вероятности Соломонова были: бритва Оккама , принцип множественных объяснений Эпикура , современная теория вычислений (например, использование универсальной машины Тьюринга ) и правило Байеса для предсказания.

Бритва Оккама и принцип Эпикура по сути являются двумя разными нематематическими приближениями универсального априори .

  • Бритва Оккама: среди теорий, согласующихся с наблюдаемыми явлениями, следует выбрать самую простую теорию .
  • Принцип множественности объяснений Эпикура: если наблюдениям соответствуют несколько теорий, сохраняйте все такие теории .

В основе универсальной априорной теории лежит абстрактная модель компьютера, например универсальная машина Тьюринга . Подойдет любой абстрактный компьютер, если он является полным по Тьюрингу, т.е. каждая конечная двоичная строка имеет по крайней мере одну программу, которая будет вычислять ее на абстрактном компьютере.

Абстрактный компьютер используется для придания точного значения фразе «простое объяснение». В используемом формализме объяснения или теории явлений - это компьютерные программы, которые генерируют строки наблюдений при запуске на абстрактном компьютере. Простое объяснение - это небольшая компьютерная программа. Сложное объяснение - это длинная компьютерная программа. Более вероятны простые объяснения, поэтому строка наблюдения с высокой вероятностью - это строка, созданная короткой компьютерной программой или, возможно, любой из большого количества немного более длинных компьютерных программ. Строка наблюдения с низкой вероятностью может быть создана только длинной компьютерной программой.

Эти идеи можно конкретизировать, а вероятности использовать для построения априорного распределения вероятностей для данного наблюдения. Основная причина, по которой Соломонов изобрел это априорное значение, состоит в том, что его можно использовать в правиле Байеса, когда фактическое априорное значение неизвестно, что позволяет прогнозировать в условиях неопределенности. Он предсказывает наиболее вероятное продолжение этого наблюдения и дает меру того, насколько вероятно это продолжение.

Хотя универсальная вероятность наблюдения (и ее расширение) не поддается исчислению, существует компьютерный алгоритм поиска Левина, который при выполнении в течение более длительных периодов времени генерирует последовательность приближений, сходящихся к универсальному распределению вероятностей .

Соломонов доказал, что это распределение машинно-инвариантно с точностью до постоянного множителя (так называемая теорема инвариантности ).

Соломонов изобрел концепцию алгоритмической вероятности и связанную с ней теорему об инвариантности примерно в 1960 году, опубликовав отчет об этом: «Предварительный отчет по общей теории индуктивного вывода». Он более полно прояснил эти идеи в 1964 году в «Формальной теории индуктивного вывода», часть I и часть II.

Дальнейшее обсуждение

Соломонов описал универсальный компьютер со случайно сгенерированной программой ввода. Программа вычисляет некоторый, возможно, бесконечный вывод. Универсальное распределение вероятностей - это распределение вероятностей по всем возможным выходным строкам со случайным входом.

Алгоритмическая вероятность любого заданного конечного выходного префикса q - это сумма вероятностей программ, которые вычисляют что-то, начиная с q . Некоторые длинные объекты с короткими программами имеют высокую вероятность.

Алгоритмическая вероятность - главный компонент теории индуктивного вывода Соломонова, теории предсказания, основанной на наблюдениях; он был изобретен с целью использования его для машинного обучения; учитывая последовательность символов, какой из них будет следующим? Теория Соломонова дает ответ, в определенном смысле оптимальный, хотя и невыполнимый. В отличие, например, от неформальной теории индуктивного вывода Карла Поппера, теория Соломонова математически строга.

Алгоритмическая вероятность тесно связана с понятием колмогоровской сложности . Введение Колмогоровым сложности было мотивировано теорией информации и проблемами случайности, в то время как Соломонов ввел алгоритмическую сложность по другой причине: индуктивным рассуждениям. Единственная универсальная априорная вероятность, которая может быть заменена каждой фактической априорной вероятностью в правиле Байеса, была изобретена Соломоновым с колмогоровской сложностью в качестве побочного продукта.

Перечислимая мера Соломонова в определенном смысле универсальна , но время вычисления может быть бесконечным. Одним из способов решения этой проблемы является вариант алгоритма поиска Леонида Левина, который ограничивает время, затрачиваемое на вычисление успешности возможных программ, с более короткими программами, отводящими больше времени. Другие методы ограничения пространства поиска включают обучающие последовательности.

Ключевые люди

Смотрите также

Ссылки

Источники

  • Ли, М. и Витани, П., Введение в сложность Колмогорова и ее приложения , 3-е издание, Springer Science and Business Media, Нью-Йорк, 2008 г.

дальнейшее чтение

внешние ссылки