WikiDer > Алгоритмическая вероятность

Algorithmic probability

В алгоритмическая теория информации, алгоритмическая вероятность, также известный как Вероятность Соломонова, представляет собой математический метод задания априорной вероятность к данному наблюдению. Это было изобретено Рэй Соломонов в 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] что ограничивает время, затрачиваемое на вычисление успеха возможных программ, при этом более коротким программам отводится больше времени. Другие методы ограничения пространства поиска включают обучающие последовательности.

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

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

Рекомендации

  1. ^ Соломонов Р. "Предварительный отчет по общей теории индуктивного вывода", Отчет V-131, Zator Co., Кембридж, Массачусетс (редакция отчета от 4 февраля 1960 г., ноябрь 1960 г.).
  2. ^ Ли, М. и Витаньи, П., Введение в колмогоровскую сложность и ее приложения, 3-е издание, Springer Science and Business Media, Нью-Йорк, 2008 г.
  3. ^ Хаттер М., Легг С. и Витани П., «Алгоритмическая вероятность», Scholarpedia, 2 (8): 2572, 2007.
  4. ^ Ли и Витаньи, 2008 г., стр. 347
  5. ^ Ли и Витаньи, 2008 г., стр. 341
  6. ^ Ли и Витаньи, 2008 г., стр. 339.
  7. ^ Хаттер, М., «Алгоритмическая теория информации», Scholarpedia, 2 (3): 2519.
  8. ^ Левин Л.А. Задачи универсального поиска // Проблемы передачи информации. 9. С. 115–116.
  9. ^ Соломонов Р. "Индукционные системы на основе сложности: сравнения и теоремы сходимости, "IEEE Trans. On Information Theory, Vol. IT-24, No. 4, pp. 422-432, July 1978.
  10. ^ Соломонов, Р., «Открытие алгоритмической вероятности», Журнал компьютерных и системных наук, Vol. 55, No. 1, pp. 73-88, август 1997 г.
  11. ^ Соломонов Р. "Предварительный отчет по общей теории индуктивного вывода", Отчет V-131, Zator Co., Кембридж, Массачусетс (редакция отчета от 4 февраля 1960 г., ноябрь 1960 г.).
  12. ^ Соломонов Р. "Формальная теория индуктивного вывода, часть I". Информация и контроль, Vol 7, No. 1 pp 1-22, March 1964.
  13. ^ Соломонов Р. "Формальная теория индуктивного вывода, часть II" Информация и контроль, Vol 7, No. 2, pp. 224–254, июнь 1964 г.
  14. ^ Соломонов Р. "Лекция Колмогорова: Универсальное распределение и машинное обучение" Компьютерный журнал, Т. 46, № 6, с. 598, 2003 г.
  15. ^ Гач П. и Витаньи П., "In Memoriam Raymond J. Solomonoff", Информационный бюллетень общества теории информации IEEE, Vol. 61, No. 1, март 2011 г., стр. 11.
  16. ^ Левин Л.А. Задачи универсального поиска // Проблемы передачи информации. 9. С. 115–116.

Источники

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

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

внешняя ссылка