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

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

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

Индукция Соломонова естественным образом формализует бритву Оккама. ^[4]^[5]^[6]^[7]^[8] путем присвоения большего априорного доверия теориям, которые требуют более короткого алгоритмического описания.

Источник

Философский

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

Принцип

Утверждалось, что индукция Соломонова является вычислительной формализацией чистого байесовства . ^[3] Чтобы понять это, вспомним, что байесианство выводит апостериорную вероятность $\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, аппроксимируют его, чтобы заставить его работать на современном компьютере. Чем больше вычислительной мощности им предоставлено, тем ближе их предсказания к предсказаниям индуктивного вывода (их математическим пределом является индуктивный вывод Соломонова). ^[11]^[12]^[13]

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

См. также

Ссылки

^ Зенил, Гектор (11 февраля 2011 г.). Случайность посредством вычислений: несколько ответов, больше вопросов . Всемирная научная. ISBN 978-981-4462-63-1 .
↑ Перейти обратно: Перейти обратно: ^а ^б Соломонов, Рэй Дж. (2009), Эммерт-Страйб, Франк; Демер, Маттиас (ред.), «Алгоритмическая вероятность: теория и приложения» , Теория информации и статистическое обучение , Бостон, Массачусетс: Springer US, стр. 1–23, doi : 10.1007/978-0-387-84816-7_1 , ISBN 978-0-387-84816-7 , получено 21 июля 2020 г.
↑ Перейти обратно: Перейти обратно: ^а ^б Хоанг, Ле Нгуен (2020). Уравнение познания: от правила Байеса к единой философии науки (Первое изд.). Бока-Ратон, Флорида. ISBN 978-0-367-85530-7 . OCLC 1162366056 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
↑ Перейти обратно: Перейти обратно: ^а ^б Джей Джей Макколл. Введение: от Колмогорова и Соломонова к Де Финетти и обратно к Колмогорову – Метроэкономика, 2004 – Интернет-библиотека Wiley.
↑ Перейти обратно: Перейти обратно: ^а ^б Д Аист. Основы бритвы Оккама и экономности в обучении на ricoh.com - Семинар NIPS 2001, 2001 г.
↑ Перейти обратно: Перейти обратно: ^а ^б А. Н. Соклаков. Бритва Оккама как формальная основа физической теории с arxiv.org - Foundations of Physics Letters, 2002 - Springer
↑ Перейти обратно: Перейти обратно: ^а ^б Хосе Эрнандес-Оралло (1999). «За пределами теста Тьюринга» (PDF) . Журнал логики, языка и информации . 9 .
↑ Перейти обратно: Перейти обратно: ^а ^б М Хаттер. О существовании и конвергенции вычислимых универсальных априоров arxiv.org - Теория алгоритмического обучения, 2003 - Springer
^ Сэмюэл Ратманнер и Маркус Хаттер . Философский трактат универсальной индукции. Энтропия, 13(6):1076–1136, 2011 г.
^ Мин Ли и Пол Витаньи, Введение в колмогоровскую сложность и ее приложения. Спрингер-Верлаг, Нью-Йорк, 2008, стр. 339 и далее.
^ Дж. Венесс, К.С. Нг, М. Хаттер, В. Утер, Д. Сильвер. «Приближение Монте-Карло AIXI» - препринт Arxiv , 2009 г. arxiv.org
^ Дж. Венесс, К.С. Нг, М. Хаттер, Д. Сильвер. «Обучение с подкреплением посредством приближения AIXI» Препринт Arxiv , 2010 г. – aaai.org
^ С. Панков. Вычислительная аппроксимация модели AIXI с сайта agiri.org – Общий искусственный интеллект, 2008: материалы…, 2008 – book.google.com
^ Голд, Э. Марк (1967). «Языковая идентификация в лимите» (PDF) . Информация и контроль . 10 (5): 447–474. дои : 10.1016/S0019-9958(67)91165-5 .
^ Дж. Шмидхубер (2002). «Иерархии обобщенных колмогоровских сложностей и неисчислимые универсальные меры, вычислимые в пределе» (PDF) . Международный журнал основ компьютерных наук . 13 (4): 587–612. дои : 10.1142/S0129054102001291 .

Источники

Англуин, Дана; Смит, Карл Х. (сентябрь 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

[1] Зенил, Гектор (11 февраля 2011 г.). Случайность посредством вычислений: несколько ответов, больше вопросов . Всемирная научная. ISBN 978-981-4462-63-1 .

[Theory_and_Applications-2] Перейти обратно: Перейти обратно: ^а ^б Соломонов, Рэй Дж. (2009), Эммерт-Страйб, Франк; Демер, Маттиас (ред.), «Алгоритмическая вероятность: теория и приложения» , Теория информации и статистическое обучение , Бостон, Массачусетс: Springer US, стр. 1–23, doi : 10.1007/978-0-387-84816-7_1 , ISBN 978-0-387-84816-7 , получено 21 июля 2020 г.

[:0-3] Перейти обратно: Перейти обратно: ^а ^б Хоанг, Ле Нгуен (2020). Уравнение познания: от правила Байеса к единой философии науки (Первое изд.). Бока-Ратон, Флорида. ISBN 978-0-367-85530-7 . OCLC 1162366056 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[ReferenceA-4] Перейти обратно: Перейти обратно: ^а ^б Джей Джей Макколл. Введение: от Колмогорова и Соломонова к Де Финетти и обратно к Колмогорову – Метроэкономика, 2004 – Интернет-библиотека Wiley.

[ReferenceB-5] Перейти обратно: Перейти обратно: ^а ^б Д Аист. Основы бритвы Оккама и экономности в обучении на ricoh.com - Семинар NIPS 2001, 2001 г.

[ReferenceC-6] Перейти обратно: Перейти обратно: ^а ^б А. Н. Соклаков. Бритва Оккама как формальная основа физической теории с arxiv.org - Foundations of Physics Letters, 2002 - Springer

[Hernandez.1999-7] Перейти обратно: Перейти обратно: ^а ^б Хосе Эрнандес-Оралло (1999). «За пределами теста Тьюринга» (PDF) . Журнал логики, языка и информации . 9 .

[Hutter.2003-8] Перейти обратно: Перейти обратно: ^а ^б М Хаттер. О существовании и конвергенции вычислимых универсальных априоров arxiv.org - Теория алгоритмического обучения, 2003 - Springer

[9] Сэмюэл Ратманнер и Маркус Хаттер . Философский трактат универсальной индукции. Энтропия, 13(6):1076–1136, 2011 г.

[Paul_Vitanyi_p_339-10] Мин Ли и Пол Витаньи, Введение в колмогоровскую сложность и ее приложения. Спрингер-Верлаг, Нью-Йорк, 2008, стр. 339 и далее.

[11] Дж. Венесс, К.С. Нг, М. Хаттер, В. Утер, Д. Сильвер. «Приближение Монте-Карло AIXI» - препринт Arxiv , 2009 г. arxiv.org

[12] Дж. Венесс, К.С. Нг, М. Хаттер, Д. Сильвер. «Обучение с подкреплением посредством приближения AIXI» Препринт Arxiv , 2010 г. – aaai.org

[13] С. Панков. Вычислительная аппроксимация модели AIXI с сайта agiri.org – Общий искусственный интеллект, 2008: материалы…, 2008 – book.google.com

[14] Голд, Э. Марк (1967). «Языковая идентификация в лимите» (PDF) . Информация и контроль . 10 (5): 447–474. дои : 10.1016/S0019-9958(67)91165-5 .

[GenKolm-15] Дж. Шмидхубер (2002). «Иерархии обобщенных колмогоровских сложностей и неисчислимые универсальные меры, вычислимые в пределе» (PDF) . Международный журнал основ компьютерных наук . 13 (4): 587–612. дои : 10.1142/S0129054102001291 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]