Индуктивная вероятность

Индуктивная вероятность пытается определить вероятность будущих событий на основе прошлых событий. Это основа индуктивного рассуждения и математическая основа для обучения и восприятия закономерностей. Это источник знаний о мире.

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

Информация, описывающая мир, записана на языке. Например, можно выбрать простой математический язык предложений. Предложения могут быть записаны на этом языке в виде строк символов. Но в компьютере эти предложения можно закодировать как строки битов (1 и 0). Затем язык можно закодировать так, чтобы наиболее часто используемые предложения были самыми короткими. Этот внутренний язык неявно представляет вероятности утверждений.

Бритва Оккама утверждает, что «самая простая теория, согласующаяся с данными, скорее всего, будет правильной». «Простейшая теория» интерпретируется как представление теории, записанное на этом внутреннем языке. Теория с кратчайшей кодировкой на этом внутреннем языке, скорее всего, верна.

История [ править ]

Вероятность и статистика были сосредоточены на вероятностных распределениях и критериях значимости. Вероятность была формальной, четко определенной, но ограниченной по объему. В частности, его применение ограничивалось ситуациями, которые можно было определить как эксперимент или испытание, с четко определенной популяцией.

Теорема Байеса названа в честь преподобного Томаса Байеса (1701–1761). Байесовский вывод расширил применение вероятности во многих ситуациях, когда популяция не была четко определена. Но теорема Байеса всегда зависела от предшествующих вероятностей, чтобы генерировать новые вероятности. Было неясно, откуда взялись эти априорные вероятности.

Примерно в 1964 году Рэй Соломонов разработал алгоритмическую вероятность , которая дала объяснение тому, что такое случайность и как закономерности в данных могут быть представлены компьютерными программами, которые дают более короткие представления данных.

Крис Уоллес и Д.М. Бултон разработали минимальную длину сообщения примерно в 1968 году. Позже Йорма Риссанен разработал минимальную длину описания примерно в 1978 году. Эти методы позволяют теории информации связать с вероятностью способом, который можно сравнить с применением теоремы Байеса, но которые дают источник и объяснение роли априорных вероятностей.

Маркус Хаттер объединил теорию принятия решений с работами Рэя Соломонова и Андрея Колмогорова , чтобы создать теорию оптимального по Парето поведения интеллектуального агента , примерно в 1998 году.

Минимальная длина описания/сообщения [ изменить ]

Программа с наименьшей длиной, соответствующей данным, с наибольшей вероятностью предскажет будущие данные. Это тезис о минимальной длине сообщения. ^[1] и минимальная длина описания ^[2] методы.

На первый взгляд теорема Байеса отличается от принципа минимальной длины сообщения/описания. При ближайшем рассмотрении оказывается то же самое. Теорема Байеса касается условных вероятностей и утверждает вероятность того, что событие B произойдет, если сначала произойдет событие A :

P(A\land B)=P(B)\cdot P(A|B)=P(A)\cdot P(B|A)

становится с точки зрения длины сообщения L ,

L(A\land B)=L(B)+L(A|B)=L(A)+L(B|A).

Это означает, что если дана вся информация, описывающая событие, то длину информации можно использовать для определения необработанной вероятности события. Таким образом, если дана информация, описывающая появление A , вместе с информацией, описывающей B при данном A , то вся информация, описывающая A и B , была дана. ^[3] ^[4]

Переоснащение [ править ]

Переобучение происходит, когда модель соответствует случайному шуму, а не шаблону данных. Например, возьмем ситуацию, когда кривая соответствует набору точек. Если подбирается полином со многими членами, он может более точно представлять данные. Тогда соответствие будет лучше, и информации, необходимой для описания отклонений от подобранной кривой, будет меньше. Меньшая длина информации означает более высокую вероятность.

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

на основе программы Вывод сложности

Теория индуктивного вывода Соломонова также является индуктивным выводом. битовая строка x Обнаружена . Затем рассмотрим все программы, генерирующие строки, начинающиеся с x . Представленные в форме индуктивного вывода, программы представляют собой теории, предполагающие наблюдение битовой строки x .

Используемый здесь метод определения вероятностей индуктивного вывода основан на теории индуктивного вывода Соломонова .

Обнаружение закономерностей в данных [ править ]

Если все биты равны 1, то люди делают вывод, что монета имеет смещение и что более вероятно, что следующий бит также будет равен 1. Это описывается как обучение на основе данных или обнаружение закономерностей в данных.

Такой шаблон может быть представлен компьютерной программой . Можно написать короткую компьютерную программу, которая выдает серию битов, все из которых равны 1. Если длина программы K равна $L(K)$ бит, то его априорная вероятность равна

P(K)=2^{-L(K)}

Длина кратчайшей программы, представляющей собой строку битов, называется колмогоровской сложностью .

Колмогоровская сложность невычислима. Это связано с проблемой остановки . При поиске самой короткой программы некоторые программы могут зайти в бесконечный цикл.

Учитывая все теории [ править ]

греческий философ Эпикур сказал: «Если более чем одна теория согласуется с наблюдениями, сохраните все теории». Цитируется, что ^[5]

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

Программы, длина которых уже превышает n, не обладают предсказательной силой. Необработанная (или априорная) вероятность того, что последовательность битов является случайной (не имеет последовательности), равна $2^{-n}$ .

Каждая программа, которая создает последовательность битов, но короче n, представляет собой теорию/шаблон о битах с вероятностью $2^{-k}$ где k — длина программы.

Вероятность получения последовательности битов y после получения серии битов x равна условной вероятности получения y при заданном x , которая представляет собой вероятность x с добавленным y , деленную на вероятность x . ^[6]^[7]^[8]

Универсальные приоры [ править ]

Язык программирования влияет на предсказания следующего бита в строке. Язык действует как априорная вероятность . Это особенно проблема, когда язык программирования кодирует числа и другие типы данных. Интуитивно мы думаем, что 0 и 1 — простые числа и что простые числа в некотором смысле более сложны, чем числа, которые могут быть составными.

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

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

Проблема возникает, когда предшествующие ожидания интеллектуального агента взаимодействуют с окружающей средой, образуя самоусиливающуюся петлю обратной связи. Это проблема предвзятости или предубеждений. Универсальные приоры уменьшают, но не устраняют эту проблему.

Универсальный искусственный интеллект [ править ]

Теория универсального искусственного интеллекта применяет теорию принятия решений к индуктивным вероятностям. Теория показывает, как можно выбрать лучшие действия для оптимизации функции вознаграждения. Результатом является теоретическая модель интеллекта. ^[9]

Это фундаментальная теория интеллекта, которая оптимизирует поведение агентов в:

Исследование окружающей среды; выполнение действий для получения ответов, которые расширяют знания агентов.
Конкуренция или сотрудничество с другим агентом; игры.
Балансирование краткосрочных и долгосрочных вознаграждений.

В общем, ни один агент не всегда будет действовать наилучшим образом во всех ситуациях. Конкретный выбор, сделанный агентом, может быть неправильным, и окружающая среда может не дать агенту возможности оправиться от первоначального неправильного выбора. Однако агент является оптимальным по Парето в том смысле, что ни один другой агент не будет действовать лучше, чем этот агент, в этой среде, не ухудшившись при этом в другой среде. Ни о каком другом агенте в этом смысле нельзя сказать, что он лучше.

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

Вероятность [ править ]

Вероятность — это представление неопределенного или частичного знания об истинности утверждений. Вероятности — это субъективные и личные оценки вероятных результатов, основанные на прошлом опыте и выводах, сделанных на основе данных.

Такое описание вероятности на первый взгляд может показаться странным. На естественном языке мы говорим о «вероятности» того, что солнце взойдет завтра. Мы не говорим о «вашей вероятности» того, что солнце взойдет. Но для того, чтобы вывод был правильно смоделирован, вероятность должна быть индивидуальной, а сам акт вывода генерирует новые апостериорные вероятности из предшествующих вероятностей.

Вероятности носят личный характер, поскольку они зависят от знаний человека. Вероятности субъективны, поскольку они всегда в некоторой степени зависят от априорных вероятностей, присвоенных человеком. Под субъективным здесь не следует понимать расплывчатое или неопределенное понятие.

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

Однако, если агент использует вероятность для взаимодействия со средой, может возникнуть обратная связь, так что два агента в идентичной среде, начиная с лишь немного отличающихся априорных значений, в конечном итоге получат совершенно разные вероятности. В этом случае теория оптимального решения , как в «Универсальном искусственном интеллекте » Маркуса Хаттера, даст оптимальную по Парето производительность агента. Это означает, что ни один другой интеллектуальный агент не может добиться большего успеха в одной среде, не ухудшившись при этом в другой среде.

с вероятностью Сравнение дедуктивной

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

Общие знания.
Предполагаемые факты, которые следует вывести из данных.

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

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

Вероятность оценка как

Принцип безразличия сыграл ключевую роль в теории вероятностей. Он гласит, что если N утверждений симметричны и одно условие не может быть предпочтительнее другого, то все утверждения равновероятны. ^[10]

Если серьезно, то при оценке вероятности этот принцип приводит к противоречиям. Предположим, на расстоянии лежат 3 мешка с золотом, и человека просят выбрать один. Тогда из-за расстояния не видно размеров сумки. Используя принцип безразличия, вы оцениваете, что в каждом мешке находится одинаковое количество золота, и в каждом мешке находится одна треть золота.

Теперь, пока один из нас не смотрит, другой берет один из мешков и делит его на 3 мешка. Теперь есть 5 мешков с золотом. Принцип безразличия теперь гласит, что в каждом мешке содержится пятая часть золота. Сумка, в которой, по оценкам, содержалась одна треть золота, теперь содержит одну пятую золота.

Если рассматривать ценность, связанную с сумкой, то эти ценности различны и поэтому противоречивы. Но если принять за оценку, данную для конкретного сценария, обе величины представляют собой отдельные оценки, полученные при разных обстоятельствах, и нет оснований полагать, что они равны.

Оценки априорных вероятностей вызывают особое подозрение. Оценки будут построены так, чтобы не следовать какому-либо последовательному частотному распределению. По этой причине априорные вероятности рассматриваются как оценки вероятностей, а не вероятностей.

Полное теоретическое рассмотрение будет связано с каждой вероятностью,

Заявление
Предварительные знания
Априорные вероятности
Процедура оценки, используемая для определения вероятности.

вероятностных подходов Объединение

Индуктивная вероятность сочетает в себе два разных подхода к вероятности.

Вероятность и информация
Вероятность и частота

Каждый подход дает немного разную точку зрения. Теория информации используется для связывания вероятностей с количеством информации. Этот подход часто используется для оценки априорных вероятностей.

Частотная вероятность определяет вероятности как объективные утверждения о том, как часто происходит событие. Этот подход можно расширить, определив испытания как возможные миры . Утверждения о возможных мирах определяют события .

Вероятность и информация [ править ]

Тогда как логика представляет только две ценности; true и false в качестве значений утверждения, вероятность связывает число в [0,1] с каждым утверждением. Если вероятность утверждения равна 0, утверждение ложно. Если вероятность утверждения равна 1, то утверждение истинно.

При рассмотрении некоторых данных как строки битов априорные вероятности для последовательности 1 и 0, вероятность 1 и 0 равны. Следовательно, каждый дополнительный бит вдвое уменьшает вероятность последовательности битов. Это приводит к выводу, что,

P(x)=2^{-L(x)}

Где $P(x)$ это вероятность строки битов $x$ и $L(x)$ это его длина.

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

Объединение информации [ править ]

Два заявления $A$ и $B$ может быть представлен двумя отдельными кодировками. Тогда длина кодирования равна

L(A\land B)=L(A)+L(B)

или с точки зрения вероятности,

P(A\land B)=P(A)P(B)

Но этот закон не всегда верен, поскольку может существовать более короткий метод кодирования. $B$ если мы предположим $A$ . Таким образом, приведенный выше закон вероятности применим только в том случае, если $A$ и $B$ являются «независимыми».

Внутренний язык информации [ править ]

Основное использование информационного подхода к вероятности состоит в том, чтобы дать оценки сложности утверждений. Вспомним, что бритва Оккама гласит: «При прочих равных условиях самая простая теория с наибольшей вероятностью будет правильной». Чтобы применить это правило, сначала необходимо дать определение тому, что означает «самый простой». Теория информации определяет самое простое как самое короткое кодирование.

Знания представлены в виде утверждений . Каждый оператор представляет собой логическое выражение . Выражения кодируются функцией, которая принимает описание (а не значение) выражения и кодирует его как битовую строку.

Длина кодирования утверждения дает оценку вероятности утверждения. Эта оценка вероятности часто будет использоваться в качестве априорной вероятности утверждения.

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

Кодирование выражений [ править ]

Выражение состоит из подвыражений,

Константы (включая идентификатор функции).
Применение функций.
квантификаторы .

Код Хаффмана должен различать эти 3 случая. Длина каждого кода зависит от частоты каждого типа подвыражений.

Первоначально всем константам присваивается одинаковая длина/вероятность. Более поздним константам можно присвоить вероятность с помощью кода Хаффмана на основе количества использований идентификатора функции во всех записанных на данный момент выражениях. Целью использования кода Хаффмана является оценка вероятностей, а не сжатие данных.

Длина приложения функции равна длине константы идентификатора функции плюс сумма размеров выражений для каждого параметра.

Длина квантора — это длина выражения, по которому вычисляется квантификатор.

Распределение чисел [ править ]

Явного представления натуральных чисел не дано. Однако натуральные числа можно построить, применив функцию-преемник к 0, а затем применив другие арифметические функции. При этом подразумевается распределение натуральных чисел, основанное на сложности построения каждого числа.

Рациональные числа образуются путем деления натуральных чисел. Простейшее представление не имеет общих множителей между числителем и знаменателем. Это позволяет распространить вероятностное распределение натуральных чисел на рациональные числа.

Вероятность и частота [ править ]

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

События – это наборы результатов. Высказывания могут быть связаны с событиями. Логическое утверждение B о результатах определяет набор результатов b,

b=\{x:B(x)\}

Условная вероятность [ править ]

Каждая вероятность всегда связана с состоянием знаний в конкретный момент аргумента. Вероятности до вывода известны как априорные вероятности, а вероятности после — как апостериорные вероятности.

Вероятность зависит от известных фактов. Истина факта ограничивает область результатов результатами, соответствующими этому факту. Априорные вероятности — это вероятности до того, как факт станет известен. Апостериорные вероятности возникают после того, как факт известен. Говорят, что апостериорные вероятности обусловлены фактом. вероятность того, что $B$ верно, учитывая, что $A$ верно, пишется так: $P(B|A).$

Все вероятности в некотором смысле условны. Априорная вероятность $B$ является,

P(B)=P(B|\top )

Частотный подход применительно мирам к возможным

В частотном подходе вероятности определяются как отношение количества исходов внутри события к общему числу исходов. В модели возможного мира каждый возможный мир является результатом, а утверждения о возможных мирах определяют события. Вероятность того, что утверждение истинно, равна количеству возможных миров, в которых утверждение истинно, деленное на общее количество возможных миров. Вероятность утверждения $A$ быть правдивым относительно возможных миров - это тогда,

P(A)={\frac {|\{x:A(x)\}|}{|x:\top |}}

Для условной вероятности.

P(B|A)={\frac {|\{x:A(x)\land B(x)\}|}{|x:A(x)|}}

затем

{\begin{aligned}P(A\land B)&={\frac {|\{x:A(x)\land B(x)\}|}{|x:\top |}}\\[8pt]&={\frac {|\{x:A(x)\land B(x)\}|}{|\{x:A(x)\}|}}{\frac {|\{x:A(x)\}|}{|x:\top |}}\\[8pt]&=P(A)P(B|A)\end{aligned}}

Используя симметрию, это уравнение можно записать как закон Байеса.

P(A\land B)=P(A)P(B|A)=P(B)P(A|B)

Этот закон описывает взаимосвязь между априорными и апостериорными вероятностями изучения новых фактов.

Записанная в виде количества информации , теорема Байеса выглядит следующим образом:

L(A\land B)=L(A)+L(B|A)=L(B)+L(A|B)

Два утверждения A и B называются независимыми, если знание истинности A не меняет вероятность B. Математически это так:

P(B)=P(B|A)

тогда теорема Байеса сводится к

P(A\land B)=P(A)P(B)

Закон суммы вероятностей [ править ]

За набор взаимоисключающих возможностей $A_{i}$ , сумма апостериорных вероятностей должна быть равна 1.

\sum _{i}{P(A_{i}|B)}=1

Замена с использованием теоремы Байеса дает закон полной вероятности.

\sum _{i}{P(B|A_{i})P(A_{i})}=\sum _{i}{P(A_{i}|B)P(B)}

P(B)=\sum _{i}{P(B|A_{i})P(A_{i})}

Этот результат используется для получения расширенной формы теоремы Байеса :

P(A_{i}|B)={\frac {P(B|A_{i})P(A_{i})}{\sum _{j}{P(B|A_{j})P(A_{j})}}}

Это обычная форма теоремы Байеса, используемая на практике, поскольку она гарантирует сумму всех апостериорных вероятностей для $A_{i}$ это 1.

Альтернативные возможности [ править ]

Для взаимоисключающих возможностей вероятности складываются.

P(A\lor B)=P(A)+P(B),\qquad {\text{if }}P(A\land B)=0

С использованием

A\lor B=(A\land \neg (A\land B))\lor (B\land \neg (A\land B))\lor (A\land B)

Тогда альтернативы

A\land \neg (A\land B),\quad B\land \neg (A\land B),\quad A\land B

все взаимоисключающие. Также,

(A\land \neg (A\land B))\lor (A\land B)=A

P(A\land \neg (A\land B))+P(A\land B)=P(A)

P(A\land \neg (A\land B))=P(A)-P(A\land B)

Итак, сложив все это вместе,

{\begin{aligned}P(A\lor B)&=P((A\land \neg (A\land B))\lor (B\land \neg (A\land B))\lor (A\land B))\\&=P(A\land \neg (A\land B)+P(B\land \neg (A\land B))+P(A\land B)\\&=P(A)-P(A\land B)+P(B)-P(A\land B)+P(A\land B)\\&=P(A)+P(B)-P(A\land B)\end{aligned}}

Отрицание [ править ]

Как,

A\lor \neg A=\top

затем

P(A)+P(\neg A)=1

последствий условий Вероятность и

Импликация связана с условной вероятностью следующим уравнением:

A\to B\iff P(B|A)=1

Вывод,

{\begin{aligned}A\to B&\iff P(A\to B)=1\\&\iff P(A\land B\lor \neg A)=1\\&\iff P(A\land B)+P(\neg A)=1\\&\iff P(A\land B)=P(A)\\&\iff P(A)\cdot P(B|A)=P(A)\\&\iff P(B|A)=1\end{aligned}}

байесовской Проверка гипотезы

Теорему Байеса можно использовать для оценки вероятности гипотезы или теории H с учетом некоторых фактов F. Тогда апостериорная вероятность H равна

P(H|F)={\frac {P(H)P(F|H)}{P(F)}}

или с точки зрения информации,

P(H|F)=2^{-(L(H)+L(F|H)-L(F))}

Если предположить, что гипотеза верна, можно дать более простое представление утверждения F. Длина кодирования этого более простого представления равна $L(F|H).$

$L(H)+L(F|H)$ представляет собой количество информации, необходимое для представления фактов F, если H истинно. $L(F)$ — это объем информации, необходимый для представления F без гипотезы H. Разница в том, насколько сжимается представление фактов при предположении, что H истинно. Это является доказательством того, что гипотеза H верна.

Если $L(F)$ оценивается на основе длины кодирования , то полученная вероятность не будет находиться в диапазоне от 0 до 1. Полученное значение пропорционально вероятности и не является хорошей оценкой вероятности. Полученное число иногда называют относительной вероятностью, поскольку она определяет, насколько более вероятна теория, чем ее несоблюдение.

Если известен полный набор взаимоисключающих гипотез, подтверждающих доказательства, можно дать правильную оценку априорной вероятности. $P(F)$ .

Набор гипотез [ править ]

Вероятности можно рассчитать на основе расширенной формы теоремы Байеса. Учитывая все взаимоисключающие гипотезы $H_{i}$ которые дают доказательства, такие, что,

L(H_{i})+L(F|H_{i})<L(F)

а также гипотеза R, согласно которой ни одна из гипотез не верна, тогда

{\begin{aligned}P(H_{i}|F)&={\frac {P(H_{i})P(F|H_{i})}{P(F|R)+\sum _{j}{P(H_{j})P(F|H_{j})}}}\\[8pt]P(R|F)&={\frac {P(F|R)}{P(F|R)+\sum _{j}{P(H_{j})P(F|H_{j})}}}\end{aligned}}

Что касается информации,

{\begin{aligned}P(H_{i}|F)&={\frac {2^{-(L(H_{i})+L(F|H_{i}))}}{2^{-L(F|R)}+\sum _{j}2^{-(L(H_{j})+L(F|H_{j}))}}}\\[8pt]P(R|F)&={\frac {2^{-L(F|R)}}{2^{-L(F|R)}+\sum _{j}{2^{-(L(H_{j})+L(F|H_{j}))}}}}\end{aligned}}

В большинстве ситуаций хорошим приближением будет предположение, что $F$ не зависит от $R$ , что значит $P(F|R)=P(F)$ предоставление,

{\begin{aligned}P(H_{i}|F)&\approx {\frac {2^{-(L(H_{i})+L(F|H_{i}))}}{2^{-L(F)}+\sum _{j}{2^{-(L(H_{j})+L(F|H_{j}))}}}}\\[8pt]P(R|F)&\approx {\frac {2^{-L(F)}}{2^{-L(F)}+\sum _{j}{2^{-(L(H_{j})+L(F|H_{j}))}}}}\end{aligned}}

Булев индуктивный вывод [ править ]

Абдуктивный вывод ^[11]^[12]^[13]^[14]начинается с набора фактов F , который представляет собой утверждение (логическое выражение). Абдуктивное рассуждение имеет форму:

Теория T подразумевает утверждение F. Поскольку теория T проще, чем F, абдукция говорит, что существует вероятность того, что теория T подразумевается из F .

Теория T , также называемая объяснением условия F , является ответом на вездесущий фактический вопрос «почему». Например, условие F — «Почему падают яблоки?». Ответом является теория Т , которая подразумевает, что яблоки падают;

F=G{\frac {m_{1}m_{2}}{r^{2}}}

Индуктивный вывод имеет вид

Все наблюдаемые объекты класса C обладают свойством P. Поэтому существует вероятность, что все объекты класса C обладают свойством P.

С точки зрения абдуктивного вывода, все объекты в классе C или наборе обладают свойством P. Это теория, которая подразумевает наблюдаемое условие. Все наблюдаемые объекты в классе C обладают свойством P.

Таким образом, индуктивный вывод является частным случаем абдуктивного вывода. В обычном использовании термин «индуктивный вывод» часто используется для обозначения как абдуктивного, так и индуктивного вывода.

Обобщение и специализация [ править ]

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

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

Классификация живых существ и объектов Линнена составляет основу обобщения и уточнения. Умение идентифицировать, распознавать и классифицировать является основой обобщения. Восприятие мира как набора объектов является ключевым аспектом человеческого интеллекта. Это объектно-ориентированная модель в некомпьютерном смысле .

Объектно-ориентированная модель строится на основе нашего восприятия . В частности, зрение основано на способности сравнивать два изображения и рассчитывать, сколько информации необходимо для трансформации или сопоставления одного изображения с другим. Компьютерное зрение использует это сопоставление для создания трехмерных изображений из пар стереоизображений .

Индуктивное логическое программирование — это средство построения теории, подразумевающей условие. Плоткина ^[15]^[16] Подход « относительно наименьшее общее обобщение (rlgg) » создает простейшее обобщение, соответствующее условию.

Ньютоном индукции Использование

Исаак Ньютон использовал индуктивные аргументы при построении своего закона всемирного тяготения . ^[17] Начиная с заявления,

Центр яблока падает к центру Земли.

Обобщение путем замены яблока на объект и Земли на объект дает в системе двух тел:

Центр объекта падает к центру другого объекта.

Теория объясняет падение всех объектов, поэтому имеются веские доказательства. Второе наблюдение,

Кажется, что планеты следуют по эллиптической траектории.

После некоторых сложных математических вычислений можно увидеть, что если ускорение подчиняется закону обратных квадратов, то объекты будут следовать по эллипсу. Таким образом, индукция доказывает существование закона обратных квадратов.

Используя наблюдение Галилея о том, что все объекты падают с одинаковой скоростью,

F_{1}=m_{1}a_{1}={\frac {m_{1}k_{1}}{r^{2}}}i_{1}

F_{2}=m_{2}a_{2}={\frac {m_{2}k_{2}}{r^{2}}}i_{2}

где $i_{1}$ и $i_{2}$ векторы к центру другого объекта. Тогда используя третий закон Ньютона $F_{1}=-F_{2}$

F=G{\frac {m_{1}m_{2}}{r^{2}}}

Вероятности индуктивного вывода [ править ]

Импликация определяет вероятность условия как:

T\to F\iff P(F|T)=1

Так,

P(F|T)=1

L(F|T)=0

Этот результат можно использовать при определении вероятностей для проверки байесовской гипотезы. Для одной теории H = T и

P(T|F)={\frac {P(T)}{P(F)}}

или с точки зрения информации, относительная вероятность равна:

P(T|F)=2^{-(L(T)-L(F))}

Обратите внимание, что эта оценка для P(T|F) не является истинной вероятностью. Если $L(T_{i})<L(F)$ тогда у теории есть доказательства, подтверждающие ее. Тогда для набора теорий $T_{i}=H_{i}$ , такой, что $L(T_{i})<L(F)$ ,

P(T_{i}|F)={\frac {P(T_{i})}{P(F|R)+\sum _{j}{P(T_{j})}}}

P(R|F)={\frac {P(F|R)}{P(F|R)+\sum _{j}{P(T_{j})}}}

предоставление,

P(T_{i}|F)\approx {\frac {2^{-L(T_{i})}}{2^{-L(F)}+\sum _{j}{2^{-L(T_{j})}}}}

P(R|F)\approx {\frac {2^{-L(F)}}{2^{-L(F)}+\sum _{j}{2^{-L(T_{j})}}}}

Производные [ править ]

Вывод индуктивной вероятности [ править ]

Составьте список всех самых коротких программ $K_{i}$ что каждый из них создает отдельную бесконечную строку битов и удовлетворяет соотношению:

T_{n}(R(K_{i}))=x

где $R(K_{i})$ это результат запуска программы $K_{i}$ и $T_{n}$ усекает строку после n бит.

Задача состоит в том, чтобы вычислить вероятность того, что источник создан программой. $K_{i},$ учитывая, что усеченный источник после n битов равен x . Это представлено условной вероятностью,

P(s=R(K_{i})|T_{n}(s)=x)

Используя расширенную форму теоремы Байеса

P(s=R(K_{i})|T_{n}(s)=x)={\frac {P(T_{n}(s)=x|s=R(K_{i}))P(s=R(K_{i}))}{\sum _{j}P(T_{n}(s)=x|s=R(K_{j}))P(s=R(K_{j}))}}.

Расширенная форма опирается на закон полной вероятности . Это означает, что $s=R(K_{i})$ должны быть различные возможности, что определяется условием, что каждая $K_{i}$ создать другую бесконечную строку. Также одно из условий $s=R(K_{i})$ должно быть правдой. Это должно быть верно, как в пределе, так и в $n\to \infty ,$ всегда есть хотя бы одна программа, которая производит $T_{n}(s)$ .

Как $K_{i}$ выбираются так, что $T_{n}(R(K_{i}))=x,$ затем,

P(T_{n}(s)=x|s=R(K_{i}))=1

Априорная вероятность того, что строка будет создана из программы при отсутствии информации о строке, зависит от размера программы.

P(s=R(K_{i}))=2^{-I(K_{i})}

предоставление,

P(s=R(K_{i})|T_{n}(s)=x)={\frac {2^{-I(K_{i})}}{\sum _{j}2^{-I(K_{j})}}}.

Программы, длина которых равна или превышает длину x , не обладают предсказательной силой. Разделите их, давая,

P(s=R(K_{i})|T_{n}(s)=x)={\frac {2^{-I(K_{i})}}{\sum _{j:I(K_{j})<n}2^{-I(K_{j})}+\sum _{j:I(K_{j})\geqslant n}2^{-I(K_{j})}}}.

Затем определите две вероятности как:

P(x{\text{ has pattern}})=\sum _{j:I(K_{j})<n}2^{-I(K_{j})}

P(x{\text{ is random}})=\sum _{j:I(K_{j})\geqslant n}2^{-I(K_{j})}

Но априорная вероятность того, что x представляет собой случайный набор битов, равна $2^{-n}$ . Так,

P(s=R(K_{i})|T_{n}(s)=x)={\frac {2^{-I(K_{i})}}{2^{-n}+\sum _{j:I(K_{j})<n}2^{-I(K_{j})}}}.

Вероятность того, что источник является случайным или непредсказуемым, равна

P(\operatorname {random} (s)|T_{n}(s)=x)={\frac {2^{-n}}{2^{-n}+\sum _{j:I(K_{j})<n}2^{-I(K_{j})}}}.

Модель индуктивного вывода [ править ]

Модель устройства миров используется при определении вероятностей теорий.

Выбирается случайная битовая строка.
Условие создается из битовой строки.
Мир конструируется, соответствующий условию.

Если w — битовая строка, то мир создается так, что $R(w)$ правда. Интеллектуальный агент располагает некоторыми фактами о слове, представленными битовой строкой c , которая задает условие:

C=R(c)

Набор битовых строк, идентичных любому условию x , равен $E(x)$ .

\forall x,E(x)=\{w:R(w)\equiv x\}

Теория — это более простое условие, которое объясняет (или подразумевает C. ) Множество всех таких теорий называется T ,

T(C)=\{t:t\to C\}

Байеса Применение теоремы

расширенная форма теоремы Байеса может быть применена

P(A_{i}|B)={\frac {P(B|A_{i})\,P(A_{i})}{\sum _{j}P(B|A_{j})\,P(A_{j})}},

где,

B=E(C)

A_{i}=E(t)

Для применения теоремы Байеса должно выполняться следующее: $A_{i}$ представляет собой раздел пространства событий.

Для $T(C)$ чтобы быть разделом, ни одна битовая строка n не может принадлежать двум теориям. Чтобы доказать это, предположим, что они могут это сделать, и получим противоречие:

(N\in T)\land (N\in M)\land (N\neq M)\land (n\in E(N)\land n\in E(M))

\implies (N\neq M)\land R(n)\equiv N\land R(n)\equiv M

\implies \bot

Во-вторых, докажите, что T включает в себя все исходы, соответствующие условию. Поскольку все теории, соответствующие C , включены, тогда $R(w)$ должен быть в этом наборе.

Таким образом, теорему Байеса можно применять как указано, давая:

\forall t\in T(C),P(E(t)|E(C))={\frac {P(E(t))\cdot P(E(C)|E(t))}{\sum _{j\in T(C)}P(E(j))\cdot P(E(C)|E(j))}}

Используя закон импликации и условной вероятности , определение $T(C)$ подразумевает,

\forall t\in T(C),P(E(C)|E(t))=1

Вероятность каждой теории в T определяется выражением:

\forall t\in T(C),P(E(t))=\sum _{n:R(n)\equiv t}2^{-L(n)}

так,

\forall t\in T(C),P(E(t)|E(C))={\frac {\sum _{n:R(n)\equiv t}2^{-L(n)}}{\sum _{j\in T(C)}\sum _{m:R(m)\equiv j}2^{-L(m)}}}

Наконец, вероятности событий можно отождествить с вероятностями условия, которому удовлетворяют результаты события:

\forall t\in T(C),P(E(t)|E(C))=P(t|C)

предоставление

\forall t\in T(C),P(t|C)={\frac {\sum _{n:R(n)\equiv t}2^{-L(n)}}{\sum _{j\in T(C)}\sum _{m:R(m)\equiv j}2^{-L(m)}}}

Это вероятность теории t условия C. после наблюдения выполнения

не обладающих предсказательной силой Удаление теорий ,

Теории, которые менее вероятны, чем условие C , не обладают предсказательной силой. Разделите их, давая,

\forall t\in T(C),P(t|C)={\frac {P(E(t))}{(\sum _{j:j\in T(C)\land P(E(j))>P(E(C))}P(E(j)))+(\sum _{j:j\in T(C)\land P(E(j))\leq P(E(C))}P(j))}}

Вероятность теорий, не обладающих предсказательной силой относительно C такая же, как и вероятность C. , Так,

P(E(C))=\sum _{j:j\in T(C)\land P(E(j))\leq P(E(C))}P(j)

Таким образом, вероятность

\forall t\in T(C),P(t|C)={\frac {P(E(t))}{P(E(C))+\sum _{j:j\in T(C)\land P(E(j))>P(E(C))}P(E(j))}}

и вероятность отсутствия прогноза для C, записанная как $\operatorname {random} (C)$ ,

P({\text{random}}(C)|C)={\frac {P(E(C))}{P(E(C))+\sum _{j:j\in T(C)\land P(E(j))>P(E(C))}P(E(j))}}

Вероятность состояния определялась как:

\forall t,P(E(t))=\sum _{n:R(n)\equiv t}2^{-L(n)}

Битовые строки для теорий, которые более сложны, чем битовая строка, переданная агенту в качестве входных данных, не обладают предсказательной силой. Вероятности лучше учитываются в случайном случае. Для реализации этого дано новое определение как F in,

\forall t,P(F(t,c))=\sum _{n:R(n)\equiv t\land L(n)<L(c)}2^{-L(n)}

Используя F , улучшенная версия абдуктивных вероятностей:

\forall t\in T(C),P(t|C)={\frac {P(F(t,c))}{P(F(C,c))+\sum _{j:j\in T(C)\land P(F(j,c))>P(F(C,c))}P(E(j,c))}}

P(\operatorname {random} (C)|C)={\frac {P(F(C,c))}{P(F(C,c))+\sum _{j:j\in T(C)\land P(F(j,c))>P(F(C,c))}P(F(j,c))}}

Ключевые люди [ править ]

См. также [ править ]

Ссылки [ править ]

^ Уоллес, Крис; Бултон (1968). «Информационная мера классификации» . Компьютерный журнал . 11 (2): 185–194. дои : 10.1093/comjnl/11.2.185 .
^ Риссанен, Дж. (1978). «Моделирование по кратчайшему описанию данных». Автоматика . 14 (5): 465–658. дои : 10.1016/0005-1098(78)90005-5 .
^ Эллисон, Ллойд. «Минимальная длина сообщения (MML) – введение в MML в Лос-Анджелесе» .
^ Оливер, Джей-Джей; Бакстер, Рохан А. (1994). «MML и байесианство: сходства и различия (Введение в минимальный вывод о кодировании - Часть II)» .
^ Ли, М. и Витаньи, П., Введение в колмогоровскую сложность и ее применение , 3-е издание, Springer Science and Business Media, Нью-Йорк, 2008, стр. 347.
^ Соломонов Р., « Предварительный отчет по общей теории индуктивного вывода », отчет V-131, Zator Co., Кембридж, Массачусетс. 4 февраля 1960 г., редакция - ноябрь 1960 г.
^ Соломонов, Р., « Формальная теория индуктивного вывода, часть I » , « Информация и контроль » , том 7, № 1, стр. 1–22, март 1964 г.
^ Соломонов, Р., « Формальная теория индуктивного вывода, Часть II », Информация и контроль , Том 7, № 2, стр. 224–254, июнь 1964.
^ Хаттер, Маркус (1998). Последовательные решения на основе алгоритмической вероятности . Спрингер. ISBN 3-540-22139-5 .
^ Карнап, Рудольф . «СТАТИСТИЧЕСКАЯ И ИНДУКТИВНАЯ ВЕРОЯТНОСТЬ» (PDF) .
^ Похищение . Лаборатория метафизических исследований Стэнфордского университета. 2017.
^ Пфайфер, Ники; Кляйтер, Гернот Д. (2006). «ВЫВОД В ЛОГИКЕ УСЛОВНОЙ ВЕРОЯТНОСТИ». Кибернетика . 42 (4): 391–404.
^ "Условная возможность" . Искусственный интеллект — Основы вычислительных агентов .
^ «Введение в теорию индуктивно-логического программирования (ИЛП)» .
^ Плоткин, Гордон Д. (1970). Мельцер, Б.; Мичи, Д. (ред.). «Заметка об индуктивном обобщении». Машинный интеллект . 5 . Издательство Эдинбургского университета: 153–163.
^ Плоткин, Гордон Д. (1971). Мельцер, Б.; Мичи, Д. (ред.). «Дальнейшее примечание об индуктивном обобщении». Машинный интеллект . 6 . Издательство Эдинбургского университета: 101–124.
^ Исаак Ньютон: «В [экспериментальной] философии частные положения выводятся из явлений, а затем становятся общими посредством индукции»: « Principia », Книга 3, General Scholium, стр. 392 во 2 томе английского перевода Эндрю Мотта, опубликованного в 1729 году.

Внешние ссылки [ править ]

Ратманнер С. и Хаттер М., «Философский трактат об универсальной индукции» в Entropy 2011, 13, 1076–1136: Очень четкий философский и математический анализ теории индуктивного вывода Соломонова.
К.С. Уоллес , Статистический и индуктивный вывод по минимальной длине сообщения , Springer-Verlag (Информатика и статистика), ISBN 0-387-23795-X , май 2005 г. — заголовки глав , оглавление и примеры страниц .

[1] Уоллес, Крис; Бултон (1968). «Информационная мера классификации» . Компьютерный журнал . 11 (2): 185–194. дои : 10.1093/comjnl/11.2.185 .

[2] Риссанен, Дж. (1978). «Моделирование по кратчайшему описанию данных». Автоматика . 14 (5): 465–658. дои : 10.1016/0005-1098(78)90005-5 .

[3] Эллисон, Ллойд. «Минимальная длина сообщения (MML) – введение в MML в Лос-Анджелесе» .

[4] Оливер, Джей-Джей; Бакстер, Рохан А. (1994). «MML и байесианство: сходства и различия (Введение в минимальный вывод о кодировании - Часть II)» .

[5] Ли, М. и Витаньи, П., Введение в колмогоровскую сложность и ее применение , 3-е издание, Springer Science and Business Media, Нью-Йорк, 2008, стр. 347.

[6] Соломонов Р., « Предварительный отчет по общей теории индуктивного вывода », отчет V-131, Zator Co., Кембридж, Массачусетс. 4 февраля 1960 г., редакция - ноябрь 1960 г.

[7] Соломонов, Р., « Формальная теория индуктивного вывода, часть I » , « Информация и контроль » , том 7, № 1, стр. 1–22, март 1964 г.

[8] Соломонов, Р., « Формальная теория индуктивного вывода, Часть II », Информация и контроль , Том 7, № 2, стр. 224–254, июнь 1964.

[9] Хаттер, Маркус (1998). Последовательные решения на основе алгоритмической вероятности . Спрингер. ISBN 3-540-22139-5 .

[10] Карнап, Рудольф . «СТАТИСТИЧЕСКАЯ И ИНДУКТИВНАЯ ВЕРОЯТНОСТЬ» (PDF) .

[11] Похищение . Лаборатория метафизических исследований Стэнфордского университета. 2017.

[12] Пфайфер, Ники; Кляйтер, Гернот Д. (2006). «ВЫВОД В ЛОГИКЕ УСЛОВНОЙ ВЕРОЯТНОСТИ». Кибернетика . 42 (4): 391–404.

[13] "Условная возможность" . Искусственный интеллект — Основы вычислительных агентов .

[14] «Введение в теорию индуктивно-логического программирования (ИЛП)» .

[15] Плоткин, Гордон Д. (1970). Мельцер, Б.; Мичи, Д. (ред.). «Заметка об индуктивном обобщении». Машинный интеллект . 5 . Издательство Эдинбургского университета: 153–163.

[16] Плоткин, Гордон Д. (1971). Мельцер, Б.; Мичи, Д. (ред.). «Дальнейшее примечание об индуктивном обобщении». Машинный интеллект . 6 . Издательство Эдинбургского университета: 101–124.

[17] Исаак Ньютон: «В [экспериментальной] философии частные положения выводятся из явлений, а затем становятся общими посредством индукции»: « Principia », Книга 3, General Scholium, стр. 392 во 2 томе английского перевода Эндрю Мотта, опубликованного в 1729 году.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]