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

Математическая теория

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

Соломонофф доказал, что эта индукция невычислима (или, точнее, полувычислима снизу), но отметил, что «эта невычислимость очень мягкого рода», и что она «никоим образом не препятствует ее использованию для практического предсказания» (поскольку ее можно аппроксимировать снизу более точно с большими вычислительными ресурсами). ^[3] Она «невычислима» только в мягком смысле, что никакой научный консенсус не способен доказать, что лучшая текущая научная теория является лучшей из всех возможных теорий. Однако теория Соломоноффа дает объективный критерий для принятия решения среди текущих научных теорий, объясняющих данный набор наблюдений.

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

Источник

Философский

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

Принцип

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

${\displaystyle \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]}}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

1. Ратманнер, Сэмюэл (3 июня 2011 г.). «Философский трактат об универсальной индукции». Энтропия . 13 (6): 1076–1136. arXiv : 1105.5721 . doi : 10.3390/e13061076 .
2. Зенил, Гектор (2011-02-11). Случайность через вычисления: некоторые ответы, больше вопросов. World Scientific. ISBN 978-981-4462-63-1.
3. Solomonoff, Ray J. (2009), Emmert-Streib, Frank; Dehmer, Matthias (ред.), "Алгоритмическая вероятность: теория и приложения", Information Theory and Statistical Learning , Boston, MA: Springer US, стр. 1–23, doi :10.1007/978-0-387-84816-7_1, ISBN 978-0-387-84816-7, получено 2020-07-21
4. Hoang, Lê Nguyên (2020). Уравнение знания: от правила Байеса к единой философии науки (Первое изд.). Бока-Ратон, Флорида. ISBN 978-0-367-85530-7. OCLC  1162366056.{{cite book}}: CS1 maint: location missing publisher (link)
5. JJ McCall. Индукция: от Колмогорова и Соломонова к Де Финетти и обратно к Колмогорову – Metroeconomica, 2004 – Wiley Online Library.
6. D Stork. Основы бритвы Оккама и бережливость в обучении на ricoh.com – Семинар NIPS 2001, 2001
7. А. Н. Соклаков. Бритва Оккама как формальная основа физической теории из arxiv.org – Foundations of Physics Letters, 2002 – Springer
8. Хосе Эрнандес-Оралло (1999). "За пределами теста Тьюринга" (PDF) . Журнал логики, языка и информации . 9 .
9. M Hutter. О существовании и сходимости вычислимых универсальных априорных вероятностей arxiv.org – Алгоритмическая теория обучения, 2003 – Springer
10. Сэмюэл Ратманнер и Маркус Хуттер . Философский трактат универсальной индукции. Энтропия, 13(6):1076–1136, 2011
11. Минг Ли и Пол Витаний, Введение в сложность Колмогорова и ее приложения. Springer-Verlag, Нью-Йорк, 2008, стр. 339 и далее.
12. J. Veness, KS Ng, M. Hutter, W. Uther, D. Silver. «Приближение Монте-Карло AIXI» – Препринт Arxiv, 2009 arxiv.org
13. J. Veness, KS Ng, M. Hutter, D. Silver. «Обучение с подкреплением посредством аппроксимации AIXI» Препринт Arxiv, 2010 – aaai.org
14. С. Панков. Вычислительное приближение к модели AIXI из agiri.org – Искусственный интеллект, 2008: труды …, 2008 – books.google.com
15. Голд, Э. Марк (1967). «Языковая идентификация в пределе» (PDF) . Информация и управление . 10 (5): 447–474. doi : 10.1016/S0019-9958(67)91165-5 .
16. J. Schmidhuber (2002). "Иерархии обобщенных сложностей Колмогорова и неперечислимые универсальные меры, вычислимые в пределе" (PDF) . International Journal of Foundations of Computer Science . 13 (4): 587–612. doi :10.1142/S0129054102001291.

Источники

• Angluin, Dana; Smith, Carl H. (сентябрь 1983 г.). «Индуктивный вывод: теория и методы». Computing Surveys . 15 (3): 237–269. doi :10.1145/356914.356918. S2CID  3209224.
• Burgin, M. (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) «Тезис Чёрча–Тьюринга: консенсус и оппозиция». Труды, Computability in Europe 2006. Lecture Notes in Computer Science, 3988 стр. 125–132.
• Gasarch, W .; Smith, CH (1997) «Обзор индуктивного вывода с акцентом на запросы». Сложность, логика и теория рекурсии , Lecture Notes in Pure and Appl. Math., 187, Dekker, Нью-Йорк, стр. 225–260.
• Хей, Ник. «Универсальные полумеры: введение», Серия исследовательских отчетов CDMTCS, Оклендский университет, февраль 2007 г.
• Джайн, Санджай; Ошерсон, Дэниел; Ройер, Джеймс; Шарма, Арун, Системы, которые обучаются: Введение в теорию обучения (второе издание), MIT Press , 1999.
• Клини, Стивен С. (1952), Введение в метаматематику (первое издание), Амстердам: Северная Голландия.
• Ли Мин; Витаний, Пол, Введение в сложность Колмогорова и ее приложения , 2-е издание, Springer Verlag, 1997.
• Ошерсон, Дэниел; Стоб, Майкл; Вайнштейн, Скотт, Системы, которые обучаются. Введение в теорию обучения для когнитивных и компьютерных специалистов , MIT Press , 1986.
• Соломонофф, Рэй Дж. (1999). «Два вида вероятностной индукции» (PDF) . The Computer Journal . 42 (4): 256. CiteSeerX  10.1.1.68.8941 . doi :10.1093/comjnl/42.4.256.
• Соломонофф, Рэй (март 1964 г.). "Формальная теория индуктивного вывода. Часть I" (PDF) . Информация и управление . 7 (1): 1–22. doi : 10.1016/S0019-9958(64)90223-2 .
• Соломонофф, Рэй (июнь 1964 г.). "Формальная теория индуктивного вывода, часть II" (PDF) . Информация и управление . 7 (2): 224–254. doi : 10.1016/S0019-9958(64)90131-7 .

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

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