Индуктивная вероятность - Inductive probability - Wikipedia

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

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

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

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

История

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

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

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

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

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

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

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

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

${\displaystyle P(A\land B)=P(B)\cdot P(A|B)=P(A)\cdot P(B|A)}$

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

${\displaystyle L(A\land B)=L(B)+L(A|B)=L(A)+L(B|A).}$

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

Переоснащение

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

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

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

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

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

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

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

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

${\displaystyle P(K)=2^{-L(K)}}$

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

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

Учитывая все теории

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вероятность

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Комбинирование вероятностных подходов

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

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

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

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

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

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

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

${\displaystyle P(x)=2^{-L(x)}}$

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

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

Объединение информации

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

${\displaystyle L(A\land B)=L(A)+L(B)}$

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

${\displaystyle P(A\land B)=P(A)P(B)}$

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

Внутренний язык информации

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

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

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

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

Кодирование выражений

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

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

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

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

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

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

Распределение номеров

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

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

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

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

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

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

Условная возможность

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

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

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

${\displaystyle P(B)=P(B|\top )}$

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

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

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

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

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

тогда

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

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

${\displaystyle P(A\land B)=P(A)P(B|A)=P(B)P(A|B)}$

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

Написано в виде количества информации Теорема Байеса становится,

${\displaystyle L(A\land B)=L(A)+L(B|A)=L(B)+L(A|B)}$

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

${\displaystyle P(B)=P(B|A)}$

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

${\displaystyle P(A\land B)=P(A)P(B)}$

Закон общей вероятности

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

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

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

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

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

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

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

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

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

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

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

С помощью

${\displaystyle A\lor B=(A\land \neg (A\land B))\lor (B\land \neg (A\land B))\lor (A\land B)}$

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

${\displaystyle A\land \neg (A\land B),\quad B\land \neg (A\land B),\quad A\land B}$

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

${\displaystyle (A\land \neg (A\land B))\lor (A\land B)=A}$

${\displaystyle P(A\land \neg (A\land B))+P(A\land B)=P(A)}$

${\displaystyle P(A\land \neg (A\land B))=P(A)-P(A\land B)}$

Итак, собрав все вместе,

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

Отрицание

В качестве,

${\displaystyle A\lor \neg A=\top }$

тогда

${\displaystyle P(A)+P(\neg A)=1}$

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

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

${\displaystyle A\to B\iff P(B|A)=1}$

Вывод,

${\displaystyle {\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 равна

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

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

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

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

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

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

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

Набор гипотез

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

${\displaystyle L(H_{i})+L(F|H_{i})<L(F)}$

а также гипотеза R о том, что ни одна из гипотез не верна, тогда

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

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

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

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

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

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

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

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

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

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

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

Обобщение и специализация

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

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

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

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

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

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

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

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

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

• Центр объекта падает по направлению к центру другого объекта.

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

• Кажется, что планеты движутся по эллиптическому пути.

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

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

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

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

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

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

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

Следствие определяет вероятность состояния в качестве,

${\displaystyle T\to F\iff P(F|T)=1}$

Так,

${\displaystyle P(F|T)=1}$

${\displaystyle L(F|T)=0}$

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

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

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

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

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

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

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

давая

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

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

Производные

Вывод индуктивной вероятности

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

${\displaystyle T_{n}(R(K_{i}))=x}$

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

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

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

С использованием расширенная форма теоремы Байеса

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

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

В качестве ${\displaystyle K_{i}}$ выбраны так, чтобы ${\displaystyle T_{n}(R(K_{i}))=x,}$ тогда,

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

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

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

давая

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

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

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

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

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

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

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

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

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

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

Модель для индуктивного вывода

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

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

Если ш является битовой строкой, тогда мир создается таким образом, что ${\displaystyle R(w)}$ правда. An интеллектуальный агент содержит некоторые факты о слове, представленном битовой строкой c, что дает условие

${\displaystyle C=R(c)}$

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

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

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

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

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

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

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

куда,

${\displaystyle B=E(C)}$

${\displaystyle A_{i}=E(t)}$

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

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

${\displaystyle (N\in T)\land (N\in M)\land (N\neq M)\land (n\in E(N)\land n\in E(M))}$

${\displaystyle \implies (N\neq M)\land R(n)\equiv N\land R(n)\equiv M}$

${\displaystyle \implies \bot }$

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

Таким образом, теорема Байеса может быть применена как указанное значение

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

С использованием закон вероятности импликации и условия, определение ${\displaystyle T(C)}$ подразумевает,

${\displaystyle \forall t\in T(C),P(E(C)|E(t))=1}$

Вероятность каждой теории в Т дан кем-то,

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

так,

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

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

${\displaystyle \forall t\in T(C),P(E(t)|E(C))=P(t|C)}$

давая

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

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

Удаление теорий без предсказательной силы

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

${\displaystyle \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. Так,

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

Так что вероятность

${\displaystyle \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, записанная как ${\displaystyle \operatorname {random} (C)}$,

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

Вероятность состояния была задана как,

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

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

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

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

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

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

Ключевые люди

• Уильям Оккам
• Томас Байес
• Рэй Соломонов
• Андрей Колмогоров
• Крис Уоллес
• Д. М. Бултон
• Йорма Риссанен
• Маркус Хаттер

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

• Абдуктивное рассуждение
• Алгоритмическая вероятность
• Алгоритмическая теория информации
• Байесовский вывод
• Теория информации
• Индуктивный вывод
• Индуктивное логическое программирование
• Индуктивное мышление
• Учусь
• Минимальная длина сообщения
• Минимальная длина описания
• бритва Оккама
• Теория индуктивного вывода Соломонова
• Универсальный искусственный интеллект

Рекомендации

1. Уоллес, Крис; Бултон (1968). «Информационная мера для классификации». Компьютерный журнал. 11 (2): 185–194. Дои:10.1093 / comjnl / 11.2.185.
2. Риссанен, Дж. (1978). «Моделирование по кратчайшему описанию данных». Automatica. 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 " Информация и контроль, Vol 7, No. 2, pp. 224–254, июнь 1964 г.
9. Хаттер, Маркус (1998). Последовательные решения, основанные на алгоритмической вероятности. Springer. ISBN  3-540-22139-5.
10. Карнап, Рудольф. «СТАТИСТИЧЕСКАЯ И ИНДУКТИВНАЯ ВЕРОЯТНОСТЬ» (PDF).
11. Похищение. Лаборатория метафизических исследований Стэнфордского университета. 2017 г.
12. Пфайфер, Ники; Клейтер, Гернот Д. (2006). «ВЫВОД В ЛОГИКЕ УСЛОВНОЙ ВЕРОЯТНОСТИ». Кибернетика. 42 (4): 391–404.
13. "Условная возможность". Искусственный интеллект - основы вычислительных агентов.
14. «Введение в теорию индуктивного логического программирования (ILP)».
15. Плоткин, Гордон Д. (1970). Мельцер, Б .; Мичи, Д. (ред.). «Заметка об индуктивном обобщении». Машинный интеллект. Издательство Эдинбургского университета. 5: 153–163.
16. Плоткин, Гордон Д. (1971). Мельцер, Б .; Мичи, Д. (ред.). «Дальнейшее примечание об индуктивном обобщении». Машинный интеллект. Издательство Эдинбургского университета. 6: 101–124.
17. Исаак Ньютон: «В [экспериментальной] философии частные положения выводятся из явлений и впоследствии становятся общими посредством индукции»:Principia ", Книга 3, General Scholium, на стр. 392 во 2 томе английского перевода Эндрю Мотта, опубликованного в 1729 году.

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

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