В алгоритмической теории информации , алгоритмическая вероятности , также известная как вероятность Соломонов , представляет собой математический метод присвоения предшествующей вероятности для данного наблюдения. Он был изобретен Рэем Соломоновым в 1960-х годах. [1] Он используется в теории индуктивного вывода и анализе алгоритмов. В своей общей теории индуктивного вывода Соломонов использует предварительное [ необходимо пояснение ], полученное с помощью этой формулы [ какой? ] в правиле Байеса для предсказания [ необходим пример ][ требуется дальнейшее объяснение ] . [2]
В используемом математическом формализме наблюдения имеют форму конечных двоичных строк, а универсальный априор - это распределение вероятностей по набору конечных двоичных строк [ необходима ссылка ] . Априор универсален в смысле вычислимости по Тьюрингу, т.е. ни одна строка не имеет нулевой вероятности. Это не вычислимо, но можно приблизить. [3]
Обзор
Алгоритмическая вероятность связана со следующими вопросами: [ необходима цитата ] Учитывая совокупность данных о каком-то явлении, которое мы хотим понять, как мы можем выбрать наиболее вероятную гипотезу о том, как это было вызвано из всех возможных гипотез, и как мы можем оценить разные гипотезы? Как мы можем предсказать будущие данные и как измерить вероятность того, что этот прогноз окажется правильным?
Четыре основных источника вдохновения для алгоритмической вероятности Соломонова были: бритва Оккама , принцип множественных объяснений Эпикура , современная теория вычислений (например, использование универсальной машины Тьюринга ) и правило Байеса для предсказания. [4]
Бритва Оккама и принцип Эпикура - это, по сути, два разных нематематических приближения универсального априора . [ необходима цитата ]
- Бритва Оккама: среди теорий, согласующихся с наблюдаемыми явлениями, следует выбрать самую простую теорию . [5]
- Принцип множественных объяснений Эпикура: если наблюдениям соответствуют несколько теорий, сохраняйте все такие теории . [6]
В основе универсального априора лежит абстрактная модель компьютера, такая как универсальная машина Тьюринга . [7] Подойдет любой абстрактный компьютер, если он является полным по Тьюрингу, т.е. каждая конечная двоичная строка имеет по крайней мере одну программу, которая будет вычислять ее на абстрактном компьютере.
Абстрактный компьютер используется для придания точного значения фразе «простое объяснение» [ необходима цитата ] . В используемом формализме объяснения или теории явлений - это компьютерные программы, которые генерируют строки наблюдений при запуске на абстрактном компьютере. [ необходима цитата ] Простое объяснение - это короткая компьютерная программа. Сложное объяснение - это длинная компьютерная программа. [ необходима цитата ] Простые объяснения более вероятны, поэтому строка наблюдения с высокой вероятностью - это строка, созданная короткой компьютерной программой или, возможно, любой из большого количества немного более длинных компьютерных программ. Строка наблюдения с низкой вероятностью - это строка, которая может быть сгенерирована только длинной компьютерной программой [ необходима цитата ] .
Эти идеи могут быть конкретизированы [ необходим пример ], а вероятности могут использоваться для построения априорного распределения вероятностей для данного наблюдения. [ необходима цитата ] Основная причина, по которой Соломонов изобрел это априорное значение, состоит в том, чтобы его можно было использовать в правиле Байеса, когда фактическое априорное значение неизвестно, что позволяет прогнозировать в условиях неопределенности. [ необходима цитата ] Он предсказывает наиболее вероятное продолжение этого наблюдения и дает меру того, насколько вероятно это продолжение. [ необходима цитата ]
Хотя универсальная вероятность наблюдения (и ее расширение) не поддается исчислению, существует компьютерный алгоритм Levin Search [8], который при работе в течение более продолжительных периодов времени генерирует последовательность приближений, сходящихся к универсальной. распределение вероятностей . [ необходима цитата ]
Соломонов доказал, что это распределение машинно-инвариантно с точностью до постоянного множителя (так называемая теорема инвариантности ). [9]
Соломонов изобрел концепцию алгоритмической вероятности и связанную с ней теорему об инвариантности примерно в 1960 году [10], опубликовав отчет о ней: «Предварительный отчет по общей теории индуктивного вывода». [11] Он более полно разъяснил эти идеи в 1964 году в «Формальной теории индуктивного вывода», часть I [12] и часть II. [13]
Дальнейшее обсуждение
Соломонов описал универсальный компьютер со случайно сгенерированной программой ввода. Программа вычисляет некоторый, возможно, бесконечный вывод. Универсальное распределение вероятностей - это распределение вероятностей на всех возможных выходных строках со случайным вводом. [14]
Алгоритмическая вероятность любого заданного конечного выходного префикса q - это сумма вероятностей программ, которые вычисляют что-то, начиная с q . Некоторые длинные объекты с короткими программами имеют высокую вероятность.
Алгоритмическая вероятность - главный компонент теории индуктивного вывода Соломонова, теории предсказания, основанной на наблюдениях; он был изобретен с целью использования его для машинного обучения; учитывая последовательность символов, какой из них будет следующим? Теория Соломонова дает ответ, в определенном смысле оптимальный, хотя и невыполнимый. В отличие, например, от неформальной теории индуктивного вывода Карла Поппера , [ необходимо пояснение ] теория Соломонова математически строга.
Алгоритмическая вероятность тесно связана с понятием колмогоровской сложности . Введение Колмогоровым сложности было мотивировано теорией информации и проблемами случайности, в то время как Соломонов ввел алгоритмическую сложность по другой причине: индуктивным рассуждениям. Единственная универсальная априорная вероятность, которая может быть заменена каждой фактической априорной вероятностью в правиле Байеса, была изобретена Соломоновым с колмогоровской сложностью в качестве побочного продукта. [15]
Перечислимая мера Соломонова в определенном смысле универсальна , но время вычисления может быть бесконечным. Одним из способов решения этой проблемы является вариант алгоритма поиска Леонида Левина [16], который ограничивает время, затрачиваемое на вычисление успеха возможных программ, с более короткими программами, отводящими больше времени. Другие методы ограничения пространства поиска включают обучающие последовательности.
Ключевые люди
Смотрите также
Рекомендации
- ^ Соломонофф, Р., « Предварительный отчет по общей теории индуктивного вывода », Отчет V-131, Zator Co., Кембридж, Массачусетс. (Редакция отчета от 4 февраля 1960 г. за ноябрь 1960 г.).
- ^ Ли, М. и Витани, П., Введение в сложность Колмогорова и ее приложения , 3-е издание, Springer Science and Business Media, Нью-Йорк, 2008 г.
- ^ Хаттер, М., Легг, С., и Витани, П., «Алгоритмическая вероятность» , Scholarpedia, 2 (8): 2572, 2007.
- ^ Ли и Витаньи, 2008, стр. 347
- ^ Ли и Витаньи, 2008, стр. 341
- ^ Ли и Витаньи, 2008, стр. 339.
- ^ Хаттер, М., "Алгоритмическая теория информации" , Scholarpedia, 2 (3): 2519.
- ^ Левин, Л.А., "Универсальные проблемы поиска", в Проблемах передачи информации, 9, стр. 115–116, 1973
- ^ Соломонофф, Р., " Системы индукции на основе сложности: сравнения и теоремы сходимости ", IEEE Trans. по теории информации, Vol. ИТ-24, № 4, стр. 422-432, июль 1978 г.
- ^ Соломонофф, Р., "Открытие алгоритмической вероятности" , Журнал компьютерных и системных наук , Vol. 55, No. 1, pp. 73-88, август 1997 г.
- ^ Соломонофф, Р., « Предварительный отчет по общей теории индуктивного вывода », Отчет V-131, Zator Co., Кембридж, Массачусетс. (Редакция отчета от 4 февраля 1960 г. за ноябрь 1960 г.).
- ^ Соломонофф, Р., " Формальная теория индуктивного вывода, часть I ". Информация и контроль , Том 7, № 1, стр. 1-22, март 1964 г.
- ^ Соломонофф, Р., " Формальная теория индуктивного вывода, часть II " Информация и управление , Том 7, № 2, стр. 224–254, июнь 1964 г.
- ^ Соломонов Р., " Лекция Колмогорова: универсальное распределение и машинное обучение " Компьютерный журнал , Том 46, № 6, стр. 598, 2003.
- ^ Gács, П. и Vitányi П., "Памяти Raymond J. Соломонов", IEEE по теории информации общества бюллетень , Vol. 61, No. 1, март 2011 г., стр. 11.
- ^ Левин, Л.А., "Универсальные проблемы поиска", в Проблемах передачи информации, 9, стр. 115–116, 1973
Источники
- Ли, М. и Витани, П., Введение в сложность Колмогорова и ее приложения , 3-е издание, Springer Science and Business Media, Нью-Йорк, 2008 г.
дальнейшее чтение
- Ратманнер, С. и Хаттер, М., « Философский трактат универсальной индукции » в энтропии 2011, 13, 1076-1136: очень четкий философский и математический анализ теории индуктивного вывода Соломонова.
Внешние ссылки
- Алгоритмическая вероятность в Scholarpedia
- Публикации Соломонова