Теория индуктивного вывода Соломонова - это математическая теория индукции, представленная Реем Соломоновым , основанная на теории вероятностей и теоретической информатике . [1] [2] [3] По сути, индукция Соломонова выводит апостериорную вероятность любой вычислимой теории с учетом последовательности наблюдаемых данных. Эта апостериорная вероятность выводится из правила Байеса и некоторого универсального априорного значения, то есть априорного значения, приписывающего положительную вероятность любой вычислимой теории.
Индукция Соломонова естественным образом формализует бритву Оккама [4] [5] [6] [7] [8] , приписывая большую априорную достоверность теориям, которые требуют более короткого алгоритмического описания.
Источник
Философский
Теория основана на философских основах и была основана Рэем Соломоновым около 1960 года. [9] Это математически формализованная комбинация бритвы Оккама [4] [5] [6] [7] [8] и принципа множественных объяснений. . [10] Все вычислимые теории, которые идеально описывают предыдущие наблюдения, используются для вычисления вероятности следующего наблюдения, при этом больший вес придается более коротким вычислимым теориям. Универсальный искусственный интеллект Маркуса Хаттера основан на этом для расчета ожидаемой ценности действия.
Принцип
Утверждалось, что индукция Соломонова является вычислительной формализацией чистого байесианства . [3] Чтобы понять это, вспомним, что байесовство выводит апостериорную вероятность теории данные данные применяя правило Байеса, которое дает , где теории альтернативы теории . Чтобы это уравнение имело смысл, величины а также должен быть четко определен для всех теорий а также . Другими словами, любая теория должна определять распределение вероятностей по наблюдаемым данным.. Индукция Соломонова сводится к дополнительному требованию, чтобы все такие распределения вероятностей были вычислимы .
Интересно, что набор вычислимых распределений вероятностей - это подмножество набора всех программ, которое является счетным . Точно так же наборы наблюдаемых данных, рассматриваемые Соломоновым, были конечными. Таким образом, без потери общности можно считать, что любые наблюдаемые данные являются конечной битовой строкой . В результате индукцию Соломонова можно определить, используя только дискретные распределения вероятностей.
Затем индукция Соломонова позволяет делать вероятностные прогнозы будущих данных. , просто подчиняясь законам вероятности. А именно у нас есть. Эту величину можно интерпретировать как средние прогнозы всех теорий учитывая прошлые данные , взвешенные по их апостериорной достоверности .
Математический
Доказательство «бритвы» основано на известных математических свойствах вероятностного распределения по счетному множеству . Эти свойства актуальны, потому что бесконечное множество всех программ является счетным множеством. Сумма S вероятностей всех программ должна быть точно равна единице (согласно определению вероятности ), поэтому вероятности должны примерно уменьшаться по мере того, как мы перечисляем бесконечное множество всех программ, иначе S будет строго больше единицы. Точнее, за каждый> 0, существует некоторая длина л такая , что вероятность всех программ больше , чем л не более. Это, однако, не препятствует очень длинным программам иметь очень высокую вероятность.
Основными составляющими теории являются понятия алгоритмической вероятности и колмогоровской сложности . Универсальная априорная вероятность любого префикса 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 , если М узнает весь п в S . Основные результаты заключаются в том, что все рекурсивно перечислимые классы функций доступны для обучения, в то время как класс REC всех вычислимых функций не обучается. [ необходима цитата ] Многие связанные модели были рассмотрены, а также изучение классов рекурсивно перечислимых множеств на основе положительных данных является темой, изученной в новаторской статье Голда, опубликованной в 1967 году. Далеко идущее расширение подхода Голда развивается в теории обобщенных колмогоровских сложностей Шмидхубера [15], которые представляют собой разновидности суперрекурсивных алгоритмов .
Машины Тьюринга
Третье математически обоснованное направление индуктивного вывода использует теорию автоматов и вычислений. В этом контексте процесс индуктивного вывода выполняется абстрактным автоматом, называемым индуктивной машиной Тьюринга (Burgin, 2005). Индуктивные машины Тьюринга представляют собой следующий шаг в развитии информатики, обеспечивая более совершенные модели для современных компьютеров и компьютерных сетей (Burgin, 2001) и формируя важный класс суперрекурсивных алгоритмов, поскольку они удовлетворяют всем условиям определения алгоритма . А именно, каждая индуктивная машина Тьюринга представляет собой тип эффективного метода, в котором определенный список четко определенных инструкций для выполнения задачи, когда задано начальное состояние, будет проходить через четко определенную серию последовательных состояний, в конечном итоге заканчиваясь концом. -государственный. Разница между индуктивной машиной Тьюринга и машиной Тьюринга заключается в том, что для получения результата машина Тьюринга должна остановиться, в то время как в некоторых случаях индукционная машина Тьюринга может сделать это без остановки. Стивен Клини назвал процедуры, которые могут выполняться бесконечно, не останавливаясь на процедуре или алгоритме вычисления имени (Kleene 1952: 137). Клини также потребовал, чтобы в таком алгоритме в конечном итоге был обнаружен «какой-то объект» (Kleene 1952: 137). Этому условию удовлетворяют индуктивные машины Тьюринга, поскольку их результаты отображаются после конечного числа шагов, но индуктивные машины Тьюринга не всегда говорят, на каком шаге был получен результат.
Простые индуктивные машины Тьюринга эквивалентны другим моделям вычислений. Более совершенные индуктивные машины Тьюринга намного мощнее. Доказано (Burgin, 2005), что ограничивающие частично рекурсивные функции, предикаты проб и ошибок, общие машины Тьюринга и простые индуктивные машины Тьюринга являются эквивалентными моделями вычислений. Однако простые индуктивные машины Тьюринга и общие машины Тьюринга дают прямые конструкции вычислительных автоматов, которые полностью основаны на физических машинах. Напротив, предикаты проб и ошибок, ограничивающие рекурсивные функции и ограничивающие частично рекурсивные функции представляют синтаксические системы символов с формальными правилами для их манипуляции. Простые индуктивные машины Тьюринга и общие машины Тьюринга связаны с ограничением частично рекурсивных функций и предикатов методом проб и ошибок, поскольку машины Тьюринга связаны с частично рекурсивными функциями и лямбда-исчислением.
Обратите внимание, что только простые индуктивные машины Тьюринга имеют ту же структуру (но другую семантику функционирования режима вывода), что и машины Тьюринга. Другие типы индуктивных машин Тьюринга имеют существенно более продвинутую структуру из-за структурированной памяти и более мощных инструкций. Их использование для вывода и обучения позволяет достичь более высокой эффективности и лучше отражает обучение людей (Burgin and Klinger, 2004).
Некоторые исследователи путают вычисления индуктивных машин Тьюринга с непрерывными вычислениями или вычислениями с бесконечным временем. Во-первых, прекращаются некоторые вычисления индуктивных машин Тьюринга. Как и в случае с обычными машинами Тьюринга, некоторые вычисления с остановкой дают результат, а другие нет. Во-вторых, одни непрерывные вычисления индуктивных машин Тьюринга дают результаты, а другие - нет. Правила индуктивных машин Тьюринга определяют, когда вычисление (с остановкой или без остановки) дает результат. А именно, индуктивная машина Тьюринга время от времени производит выходные данные, и как только эти выходные данные перестают изменяться, они считаются результатом вычислений. Необходимо знать, что описание этого правила в некоторых статьях неверно. Например, Дэвис (2006: 128) формулирует правило, когда результат получается без остановки, как «после того, как будет получен правильный результат, любой последующий результат будет просто повторять этот правильный результат». В-третьих, в отличие от широко распространенного заблуждения, индуктивные машины Тьюринга дают результаты (когда это происходит) всегда после конечного числа шагов (за конечное время), в отличие от бесконечных и бесконечных вычислений. Есть два основных различия между обычными машинами Тьюринга и простыми индуктивными машинами Тьюринга. Первое отличие состоит в том, что даже простые индуктивные машины Тьюринга могут делать гораздо больше, чем обычные машины Тьюринга. Второе отличие состоит в том, что обычная машина Тьюринга всегда информирует (останавливаясь или переходя в конечное состояние), когда результат получен, тогда как простая индуктивная машина Тьюринга в некоторых случаях сообщает о достижении результата, а в других случаях (где обычная машина Тьюринга беспомощна), она не сообщает. У людей есть иллюзия, что компьютер всегда сам информирует (останавливаясь или другими способами), когда результат получен. В отличие от этого, пользователи сами должны во многих случаях решать, является ли вычисленный результат тем, что им нужно, или необходимо продолжать вычисления. Действительно, повседневные настольные компьютерные приложения, такие как текстовые процессоры и электронные таблицы, проводят большую часть своего времени в ожидании в циклах событий и не завершают свою работу до тех пор, пока на это не обратят внимание пользователи.
Эволюционные индуктивные машины Тьюринга
Эволюционный подход к индуктивному выводу осуществляется с помощью другого класса автоматов, называемых эволюционными индуктивными машинами Тьюринга (Burgin and Eberbach, 2009; 2012). Эволюционная индуктивная машина Тьюринга является (возможно , бесконечная) последовательность Е = { [ т ]; t = 1, 2, 3, ...} индуктивных машин Тьюринга A [ t ], каждая из которых работает с поколениями X [t], которые закодированы как слова в алфавите машин A [ t ]. Цель состоит в том, чтобы построить «популяцию» Z, удовлетворяющую условию вывода. Автомат A [ t ], называемый компонентом или автоматом уровня E, представляет (кодирует) одноуровневый эволюционный алгоритм, который работает с входными поколениями X [ i ] популяции, применяя операторы вариации v и оператор выбора s. Первое поколение X [0] подается в качестве входных данных для E и обрабатывается автоматом A [1], который генерирует / производит первое поколение X [1] в качестве выходных данных для передачи, которые поступают в автомат A [2]. Для всех t = 1, 2, 3, ... автомат A [ t ] получает на вход генерацию X [ t - 1] от A [ t - 1], а затем применяет оператор вариации v и оператор выбора s , создавая поколение X [ i + 1] и отправляя его в A [ t + 1] для продолжения эволюции.
Смотрите также
- Алгоритмическая теория информации
- Байесовский вывод
- Определение языка в лимите
- Индуктивный вывод
- Индуктивная вероятность
- Методы Милля
- Минимальная длина описания
- Минимальная длина сообщения
- Для философской точки зрения см .: Проблема индукции и Новая загадка индукции.
Рекомендации
- ^ Zenil, Гектор (2011-02-11). Случайность посредством вычислений: некоторые ответы, еще вопросы . World Scientific. ISBN 978-981-4462-63-1.
- ^ Соломонов, Рэй Дж. (2009), Эммерт-Штрейб, Франк; Демер, Маттиас (ред.), «Алгоритмическая вероятность: теория и приложения» , Теория информации и статистическое обучение , Бостон, Массачусетс: Springer, США, стр. 1-23, DOI : 10.1007 / 978-0-387-84816-7_1 , ISBN 978-0-387-84816-7, дата обращения 21.07.2020
- ^ а б Хоанг, Ле Нгуен. Уравнение познания: от правила Байеса к единой философии науки (Первое изд.). Бока-Ратон, Флорида. ISBN 978-0-367-85530-7. OCLC 1162366056 .
- ^ а б Дж. Дж. МакКолл. Введение: От Колмогорова и Соломонова до Де Финетти и обратно к Колмогорову - Metroeconomica, 2004 - Интернет-библиотека Wiley.
- ^ a b D Аист. Основы бритвы Оккама и экономия в обучении на ricoh.com - семинар NIPS 2001, 2001
- ^ а б А. Соклаков. Бритва Оккама как формальная основа физической теории с сайта arxiv.org - Foundations of Physics Letters, 2002 - Springer
- ^ а б Хосе Эрнандес-Оралло (1999). «За пределами теста Тьюринга» (PDF) . Журнал логики, языка и информации . 9 .
- ^ а б М. Хаттер. О существовании и сходимости вычислимых универсальных априорных значений arxiv.org - Algorithmic Learning Theory, 2003 - Springer
- ^ Сэмюэл Ратманнер и Маркус Хаттер . Философский трактат универсальной индукции. Энтропия, 13 (6): 1076–1136, 2011
- ^ Мин Ли и Пол Витани, Введение в сложность Колмогорова и ее приложения. Springer-Verlag, NY, 2008, стр. 339 и далее.
- ^ J. Veness, KS Ng, M. Hutter, W. Uther, D. Silver. «Приближение Монте-Карло AIXI» - препринт Arxiv , 2009 arxiv.org
- ^ J. Венесс, К. С. Нг, М. Хуттер, Д. серебро. «Обучение с подкреплением через приближение AIXI» Препринт Arxiv , 2010 г. - aaai.org
- ^ С. Панков. Вычислительное приближение к модели AIXI от agiri.org - Общий искусственный интеллект, 2008: материалы…, 2008 - books.google.com
- ^ Золото, Э. Марк (1967). «Определение языка в пределе» (PDF) . Информация и контроль . 10 (5): 447–474. DOI : 10.1016 / S0019-9958 (67) 91165-5 .
- ^ Дж. Шмидхубер (2002). «Иерархии обобщенных колмогоровских сложностей и неисчислимых универсальных мер, вычислимых в пределе» (PDF) . Международный журнал основ информатики . 13 (4): 587–612. DOI : 10.1142 / S0129054102001291 .
Источники
- Англуин, Дана; Смит, Карл Х. (сентябрь 1983 г.). «Индуктивный вывод: теория и методы» . Вычислительные обзоры . 15 (3): 237–269. DOI : 10.1145 / 356914.356918 . S2CID 3209224 .
- Бургин М. (2005), Суперрекурсивные алгоритмы , Монографии по информатике, Springer. ISBN 0-387-95569-0
- Бургин, М., «Откуда мы знаем, на что способна технология», Коммуникации ACM , т. 44, № 11, 2001 г., стр. 82–88.
- Burgin, M .; Эбербах, Э., «Универсальность машин Тьюринга, индуктивных машин Тьюринга и эволюционных алгоритмов», Fundamenta Informaticae , т. 91, № 1, 2009 г., 53–77.
- Burgin, M .; Эбербах, Э., «Об основах эволюционных вычислений: подход эволюционных автоматов», в Справочнике по исследованиям в области искусственных иммунных систем и естественных вычислений: применение сложных адаптивных технологий (Хунвэй Мо, ред.), IGI Global, Херши, Пенсильвания, 2009 , 342–360.
- Burgin, M .; Эбербах, Э., "Эволюционные автоматы: выразительность и сходимость эволюционных вычислений", Компьютерный журнал , т. 55, № 9, 2012 г., стр. 1023–1029.
- Burgin, M .; Клингер, А. Опыт, поколения и ограничения в машинном обучении, Теоретическая информатика , т. 317, № 1/3, 2004 г., стр. 71–91.
- Дэвис, Мартин (2006) «Тезис Чёрча-Тьюринга: консенсус и оппозиция]». Proceedings, Computability in Europe 2006. Lecture Notes in Computer Science, 3988 pp. 125–132.
- Gasarch, W .; Смит, CH (1997) "Обзор индуктивного вывода с акцентом на запросы". Сложность, логика и теория рекурсии , Конспект лекций в чистом и прикладном языках. 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 . 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