Теория индуктивного вывода Соломонова

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

Соломонов доказал, что эта индукция неисчислима , но отметил, что «эта неисчислимость носит очень мягкий характер» и что она «ни в коей мере не препятствует ее использованию для практического предсказания».

Индукция Соломонова естественным образом формализует бритву Оккама. путем присвоения большего априорного доверия теориям, которые требуют более короткого алгоритмического описания.

Источник

Философский

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

Принцип

Утверждалось, что индукция Соломонова является вычислительной формализацией чистого байесовства . Чтобы понять это, вспомним, что байесианство выводит апостериорную вероятность $\mathbb {P} [T|D]$ теории $T$ данные данные $D$ применяя правило Байеса, которое дает

$\mathbb {P} [T|D]={\frac {\mathbb {P} [D|T]\mathbb {P} [T]}{\mathbb {P} [D|T]\mathbb {P} [T]+\sum _{A\neq T}\mathbb {P} [D|A]\mathbb {P} [A]}}$

где теории $A$ являются альтернативой теории $T$. Чтобы это уравнение имело смысл, величины $\mathbb {P} [D|T]$ и $\mathbb {P} [D|A]$ должны быть четко определены для всех теорий $T$ и $A$. Другими словами, любая теория должна определять распределение вероятностей по наблюдаемым данным. $D$. Индукция Соломонова, по сути, сводится к требованию, чтобы все такие распределения вероятностей были вычислимыми .

Интересно, что множество вычислимых распределений вероятностей является подмножеством множества всех программ, которое является счетным . Точно так же наборы наблюдаемых данных, рассматриваемые Соломоновым, были конечными. Таким образом, без потери общности мы можем считать, что любые наблюдаемые данные представляют собой конечную битовую строку . В результате индукцию Соломонова можно определить, используя только дискретные распределения вероятностей.

Затем индукция Соломонова позволяет делать вероятностные прогнозы будущих данных. $F$, просто подчиняясь законам вероятности. А именно, мы имеем $\mathbb {P} [F|D]=\mathbb {E} _{T}[\mathbb {P} [F|T,D]]=\sum _{T}\mathbb {P} [F|T,D]\mathbb {P} [T|D]$. Эту величину можно интерпретировать как среднее значение прогнозов. $\mathbb {P} [F|T,D]$ из всех теорий $T$ учитывая прошлые данные $D$, взвешенные по их апостериорным достоверностям $\mathbb {P} [T|D]$.

Математический

Доказательство «бритвы» основано на известных математических свойствах распределения вероятностей на счетном множестве . Эти свойства важны, поскольку бесконечное множество всех программ является счетным множеством. Сумма S вероятностей всех программ должна быть точно равна единице (согласно определению вероятности ), поэтому вероятности должны примерно уменьшаться по мере перечисления бесконечного множества всех программ, в противном случае S будет строго больше единицы. Точнее, для каждого $\epsilon$ > 0, существует некоторая длина l такая, что вероятность всех программ длиннее l не более $\epsilon$. Однако это не мешает очень длинным программам иметь очень высокую вероятность.

Основополагающими составляющими теории являются понятия алгоритмической вероятности и колмогоровской сложности . Универсальная априорная вероятность любого префикса p вычислимой последовательности x — это сумма вероятностей всех программ (для универсального компьютера ), которые вычисляют что-то, начиная с p . Учитывая некоторое p и любое вычислимое, но неизвестное распределение вероятностей, из которого выбрано x , универсальную априорную теорему и теорему Байеса можно использовать для предсказания еще невидимых частей x оптимального .

Математические гарантии

Полнота Соломонова

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

Неисчислимость Соломонова

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

Современные приложения

Искусственный интеллект

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

Другое направление индуктивного вывода основано на Э. Марка Голда модели обучения в пределе 1967 года и с тех пор разрабатывает все больше и больше моделей обучения. Общий сценарий следующий: для данного класса S вычислимых функций существует ли обучаемый (то есть рекурсивный функционал), который для любого входного сигнала формы ( f (0), f (1),..., f ( n )) выводит гипотезу (индекс e относительно заранее согласованной приемлемой нумерации всех вычислимых функций; может потребоваться, чтобы индексированная функция соответствовала заданным значениям f ). Учащийся M изучает функцию f, если почти все его гипотезы имеют один и тот же индекс e , который порождает функцию f ; M изучает S, M изучает каждое f в S. если Основные результаты заключаются в том, что все рекурсивно перечислимые классы функций обучаемы, в то время как класс REC всех вычислимых функций необучаем. Было рассмотрено множество связанных моделей, а также изучение классов рекурсивно перечислимых множеств на основе положительных данных - это тема, изучаемая начиная с новаторской статьи Голда, опубликованной в 1967 году. Далеко идущее расширение подхода Голда развито в теории обобщенных колмогоровских сложностей Шмидхубера. которые являются разновидностью суперрекурсивных алгоритмов .

См. также

• Алгоритмическая теория информации
• Байесовский вывод
• Индуктивный вывод
• Индуктивная вероятность
• Методы Милля
• Минимальная длина описания
• Минимальная длина сообщения
• С философской точки зрения см.: Проблема индукции и Новая загадка индукции.

Источники

• Англуин, Дана; Смит, Карл Х. (сентябрь 1983 г.). «Индуктивный вывод: теория и методы» . Вычислительные опросы . 15 (3): 237–269. дои : 10.1145/356914.356918 . S2CID   3209224 .
• Бургин, М. (2005), Суперрекурсивные алгоритмы , Монографии по информатике, Springer. ISBN   0-387-95569-0
• Бургин М., «Откуда мы знаем, на что способны технологии», Communications of the ACM , т. 44, № 11, 2001 г., стр. 82–88.
• Бургин, М.; Эбербах Э., «Универсальность машин Тьюринга, индуктивных машин Тьюринга и эволюционных алгоритмов», Fundamenta Informaticae , т. 91, № 1, 2009 г., 53–77.
• Бургин, М.; Эбербах, Э., «Об основах эволюционных вычислений: подход эволюционных автоматов», в Справочнике по исследованиям искусственных иммунных систем и естественных вычислений: применение сложных адаптивных технологий (Хунвэй Мо, редактор), IGI Global, Херши, Пенсильвания, 2009 г. , 342–360.
• Бургин, М.; Эбербах Э., «Эволюционные автоматы: выразительность и конвергенция эволюционных вычислений», Computer Journal , т. 55, № 9, 2012 г., стр. 1023–1029.
• Бургин, М.; Клингер, А. Опыт, поколения и ограничения в машинном обучении, Теоретическая информатика , т. 317, № 1/3, 2004 г., стр. 71–91.
• Дэвис, Мартин (2006) «Тезис Церкви – Тьюринга: консенсус и оппозиция]». Труды, Вычислимость в Европе, 2006. Конспекты лекций по информатике, 3988, стр. 125–132.
• Гасарч, В. ; Смит, CH (1997) «Обзор индуктивного вывода с акцентом на запросы». Сложность, логика и теория рекурсии , Конспекты лекций в Pure и Appl. Math., 187, Деккер, Нью-Йорк, стр. 225–260.
• Привет, Ник. « Универсальные полумеры: введение », Серия исследовательских отчетов CDMTCS, Оклендский университет, февраль 2007 г.
• Джайн, Санджай; Ошерсон, Дэниел; Ройер, Джеймс; Шарма, Арун, Системы, которые обучаются: введение в теорию обучения (второе издание), MIT Press , 1999.
• Клини, Стивен К. (1952), Введение в метаматематику (первое изд.), Амстердам: Северная Голландия .
• Ли Мин; Витаний, Пол, Введение в колмогоровскую сложность и ее приложения , 2-е издание, Springer Verlag, 1997.
• Ошерсон, Дэниел; Стоб, Майкл; Вайнштейн, Скотт, Системы, которые обучаются, Введение в теорию обучения для ученых-когнитивистов и компьютерщиков , MIT Press , 1986.
• Соломонов, Рэй Дж. (1999). «Два вида вероятностной индукции» (PDF) . Компьютерный журнал . 42 (4): 256. CiteSeerX   10.1.1.68.8941 . дои : 10.1093/comjnl/42.4.256 .
• Соломонов, Рэй (март 1964 г.). «Формальная теория индуктивного вывода, часть I» (PDF) . Информация и контроль . 7 (1): 1–22. дои : 10.1016/S0019-9958(64)90223-2 .
• Соломонов, Рэй (июнь 1964 г.). «Формальная теория индуктивного вывода, часть II» (PDF) . Информация и контроль . 7 (2): 224–254. дои : 10.1016/S0019-9958(64)90131-7 .

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

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