Теория индуктивного вывода Соломонова - Solomonoffs theory of inductive inference - Wikipedia

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

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

Источник

Философский

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

Принцип

Утверждалось, что индукция Соломонова является вычислительной формализацией чистого Байесовство^[3]. Чтобы понять это, вспомним, что байесианство выводит апостериорную вероятность ${ Displaystyle mathbb {P} [T | D]}$ теории ${ displaystyle T}$ данные данные ${ displaystyle D}$ применяя правило Байеса, которое дает ${ Displaystyle mathbb {P} [T | D] = 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 будет строго больше единицы. Точнее, за каждый ${ displaystyle epsilon}$ > 0, есть длина л так что вероятность всех программ длиннее, чем л самое большее ${ displaystyle epsilon}$ . Это, однако, не препятствует очень длинным программам иметь очень высокую вероятность.

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

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

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

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

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

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

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

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

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

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

Машины Тьюринга

Третье направление индуктивного вывода, основанное на математике, использует теорию автоматов и вычислений. В этом контексте процесс индуктивного вывода выполняется абстрактным автоматом, называемым индуктивным. Машина Тьюринга (Бургин, 2005).Индуктивные машины Тьюринга представляют собой следующий шаг в развитии информатики, предоставляя лучшие модели для современных компьютеров и компьютерных сетей (Burgin, 2001) и формируя важный класс суперрекурсивных алгоритмов, поскольку они удовлетворяют всем условиям в определении алгоритм. А именно, каждая индуктивная машина Тьюринга представляет собой тип эффективного метода, в котором определенный список четко определенных инструкций для выполнения задачи, когда ему задано начальное состояние, будет проходить через четко определенную серию последовательных состояний, в конечном итоге заканчиваясь концом. -государственный. Разница между индуктивной машиной Тьюринга и Машина Тьюринга состоит в том, что для получения результата машина Тьюринга должна остановиться, в то время как в некоторых случаях индукционная машина Тьюринга может сделать это без остановки. Стивен Клини вызываемые процедуры, которые могут работать бесконечно без остановки по имени процедура или алгоритм расчета (Клини 1952: 137). Клини также потребовал, чтобы такой алгоритм в конечном итоге обнаружил «какой-то объект» (Kleene 1952: 137). Этому условию удовлетворяют индуктивные машины Тьюринга, поскольку их результаты отображаются после конечного числа шагов, но индуктивные машины Тьюринга не всегда говорят, на каком шаге был получен результат.

Простые индуктивные машины Тьюринга эквивалентны другим моделям вычислений. Более совершенные индуктивные машины Тьюринга намного мощнее. Доказано (Burgin, 2005), что ограничивающие частично рекурсивные функции, предикаты проб и ошибок, общие машины Тьюринга и простые индуктивные машины Тьюринга являются эквивалентными моделями вычислений. Однако простые индуктивные машины Тьюринга и общие машины Тьюринга дают прямые конструкции вычислительных автоматов, которые полностью основаны на физических машинах. Напротив, предикаты проб и ошибок, ограничивающие рекурсивные функции и ограничивающие частично рекурсивные функции представляют синтаксические системы символов с формальными правилами для их манипуляции. Простые индуктивные машины Тьюринга и общие машины Тьюринга связаны с ограничением частично рекурсивных функций и предикатов методом проб и ошибок, поскольку машины Тьюринга связаны с частично рекурсивными функциями и лямбда-исчислением.

Обратите внимание, что только простые индуктивные машины Тьюринга имеют ту же структуру (но другую семантику функционирования режима вывода), что и машины Тьюринга. Другие типы индуктивных машин Тьюринга имеют существенно более совершенную структуру из-за структурированной памяти и более мощных инструкций. Их использование для вывода и обучения позволяет достичь более высокой эффективности и лучше отражает обучение людей (Burgin and Klinger, 2004).

Некоторые исследователи путают вычисления на индуктивных машинах Тьюринга с непрерывными вычислениями или вычислениями с бесконечным временем. Во-первых, прекращаются некоторые вычисления индуктивных машин Тьюринга. Как и в случае с обычными машинами Тьюринга, некоторые вычисления с остановкой дают результат, а другие нет. Во-вторых, одни безостановочные вычисления индуктивных машин Тьюринга дают результаты, а другие нет. Правила индуктивных машин Тьюринга определяют, когда вычисление (с остановкой или без остановки) дает результат. А именно, индуктивная машина Тьюринга время от времени производит выходные данные, и как только эти выходные данные перестают изменяться, они считаются результатом вычислений. Необходимо знать, что описание этого правила в некоторых статьях неверно. Например, Дэвис (2006: 128) формулирует правило, когда результат получается без остановки, как «после того, как будет получен правильный результат, любой последующий результат будет просто повторять этот правильный результат». В-третьих, в отличие от широко распространенного заблуждения, индуктивные машины Тьюринга дают результаты (когда это происходит) всегда после конечного числа шагов (за конечное время), в отличие от вычислений с бесконечным и бесконечным временем. Между обычными машинами Тьюринга есть два основных различия. и простые индуктивные машины Тьюринга. Первое отличие состоит в том, что даже простые индуктивные машины Тьюринга могут делать гораздо больше, чем обычные машины Тьюринга. Второе отличие заключается в том, что обычная машина Тьюринга всегда информирует (останавливая или переходя в конечное состояние), когда результат получен, тогда как простая индуктивная машина Тьюринга в некоторых случаях сообщает о достижении результата, а в других случаях (когда обычная машина Тьюринга беспомощна), она не сообщает. У людей есть иллюзия, что компьютер всегда сам информирует (останавливаясь или другими способами), когда результат получен. В отличие от этого, пользователи сами должны во многих случаях решать, является ли вычисленный результат тем, что им нужно, или необходимо продолжать вычисления. Действительно, повседневные настольные компьютерные приложения, такие как текстовые процессоры и электронные таблицы, большую часть времени проводят в ожидании петли событий, и не прекращайте действие, пока не получите указание сделать это от пользователей.

Эволюционные индуктивные машины Тьюринга

Эволюционный подход к индуктивному выводу достигается с помощью другого класса автоматов, называемых эволюционными индуктивными машинами Тьюринга (Burgin and Eberbach, 2009; 2012). An эволюционная индуктивная машина Тьюринга является (возможно, бесконечной) последовательностью E = {А[т]; т = 1, 2, 3, ...} индуктивных машин Тьюринга. А[т] каждый работает над поколениями X [t], которые закодированы как слова в алфавите машин А[т]. Цель - создать «популяцию» Z удовлетворяющие условию вывода. Автомат А[т], называемый компонентом или автоматом уровня E, представляет (кодирует) одноуровневый эволюционный алгоритм, который работает с входными поколениями Икс[я] совокупности, применяя операторы вариации v и оператор выбора s. Первое поколение Икс[0] дается как вход для E и обрабатывается автоматом А[1], который генерирует / производит первое поколение Икс[1] как его выход передачи, который идет к автомату А[2]. Для всех т = 1, 2, 3, ..., автомат А[т] получает поколение Икс[т - 1] как вход из А[т - 1], а затем применяет оператор вариации v и оператор выбора s, производя поколение Икс[я + 1] и отправив его на А[т + 1] для продолжения эволюции.

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

Примечания

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

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

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

[1] Зенил, Гектор (11.02.2011). Случайность посредством вычислений: некоторые ответы, еще вопросы. World Scientific. ISBN 978-981-4462-63-1.

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

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

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

[ReferenceB-5] а ^б D Аист. Основы бритвы Оккама и бережливость в обучении на ricoh.com - семинар NIPS 2001, 2001

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

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

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

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

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

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

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

[13] С. Панков. Вычислительное приближение к модели AIXI от agiri.org - Общий искусственный интеллект, 2008: материалы…, 2008 - books.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]