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

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

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

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

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

История

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

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

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

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

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

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

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

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

${\ Displaystyle P (A \ земля B) = P (B) \ cdot P (A | B) = P (A) \ cdot P (B | A)}$

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

${\ Displaystyle L (A \ земля B) = L (B) + L (A | B) = L (A) + L (B | A).}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вероятность

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\ Displaystyle L (A \ земля B) = L (A) + L (B)}$

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

${\ Displaystyle P (A \ земля B) = P (A) P (B)}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\ Displaystyle Ь = \ {х: В (х) \}}$

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

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

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

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

${\ Displaystyle P (B) = P (B | \ наверх)}$

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

В частотном подходе вероятности определяются как отношение количества исходов в событии к общему количеству исходов. В модели возможного мира каждый возможный мир является результатом, а утверждения о возможных мирах определяют события. Вероятность того, что утверждение истинно, - это количество возможных миров, в которых утверждение истинно, деленное на общее количество возможных миров. Тогда вероятность того, что утверждение о возможных мирах будет верным, равна ${\ 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 {align} 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 {выровнено}}}$

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

${\ Displaystyle P (A \ земля B) = P (A) P (B | A) = P (B) P (A | B)}$

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

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

${\ Displaystyle L (A \ земля B) = L (A) + L (B | A) = L (B) + L (A | B)}$

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

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

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

${\ Displaystyle P (A \ земля B) = P (A) P (B)}$

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

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

${\ Displaystyle \ сумма _ {я} {P (A_ {i} | B)} = 1}$

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

${\ Displaystyle \ сумма _ {я} {P (B | A_ {i}) P (A_ {i})} = \ sum _ {i} {P (A_ {i} | B) P (B)}}$

${\ Displaystyle P (B) = \ сумма _ {я} {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})}}}}$

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

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

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

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

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

${\ Displaystyle А \ лор В = (А \ земля \ нег (А \ земля В)) \ лор (В \ земля \ нег (А \ земля В)) \ лор (А \ земля В)}$

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

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

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

${\ Displaystyle (A \ земля \ neg (A \ земля B)) \ лор (A \ земля B) = A}$

${\ Displaystyle P (A \ земля \ neg (A \ земля B)) + P (A \ земля B) = P (A)}$

${\ Displaystyle P (A \ земля \ neg (A \ земля B)) = P (A) -P (A \ land B)}$

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

${\ Displaystyle {\ begin {выровнен} п (A \ лор В) & = п ((А \ земля \ нег (А \ земля В)) \ лор (В \ земля \ нег (А \ земля В)) \ лор (A \ земля 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 ( А \ земля В) \ конец {выровнено}}}$

Отрицание

В виде,

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

тогда

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

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

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

${\ Displaystyle А \ к В \ тогда и только тогда, когда Р (В | А) = 1}$

Вывод,

${\ Displaystyle {\ begin {выровнен} A \ к 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 \\ & \ тогда и только тогда, когда P (A \ land B) = P (A) \\ & \ iff P (A) \ cdot P (B | A) = P (A) \\ & \ тогда и только тогда, когда P (B | A) = 1 \ end {align}}}$

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

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

${\ Displaystyle P (H | F) = {\ гидроразрыва {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 истинно. - это количество информации, необходимое для представления F без гипотезы H. Разница в том, насколько сжато представление фактов, если предположить, что H истинно. Это свидетельство того, что гипотеза H верна. ${\ Displaystyle L (F)}$

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

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

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

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

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

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

${\ Displaystyle {\ begin {align} P (H_ {i} | F) & = {\ frac {P (H_ {i}) P (F | H_ {i})} {P (F | R) + \ сумма _ {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 {выровнено}}}$

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

${\ Displaystyle {\ begin {align} 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}))}}}} \ конец {выровнено}}}$

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

${\ displaystyle {\ begin {align} P (H_ {i} | F) & \ приблизительно {\ 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) & \ приблизительно {\ frac {2 ^ {- L (F)}} {2 ^ {- L (F)} + \ sum _ {j} {2 ^ {- (L (H_ { j}) + L (F | H_ {j}))}}}} \ end {выравнивается}}}$

Логический индуктивный вывод

Абдуктивный вывод начинается с набора фактов F, который является утверждением (логическим выражением). Абдуктивное рассуждение имеет форму:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\ 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 Т \ к F \ тогда и только тогда, когда P (F | T) = 1}$

Так,

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

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

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

${\ Displaystyle P (T | F) = {\ гидроразрыва {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) = {\ гидроразрыва {P (F | R)} {P (F | R) + \ sum _ {j} {P (T_ {j})}}}}$

давая

${\ Displaystyle P (T_ {i} | F) \ приблизительно {\ frac {2 ^ {- L (T_ {i})}} {2 ^ {- L (F)} + \ sum _ {j} {2 ^ {- L (T_ {j})}}}}}$

${\ Displaystyle P (R | F) \ приблизительно {\ гидроразрыва {2 ^ {- L (F)}} {2 ^ {- L (F)} + \ sum _ {j} {2 ^ {- L (T_ {j})}}}}}$

Производные

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

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

${\ Displaystyle Т_ {п} (Р (К_ {я})) = х}$

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

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

${\ 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 Т_ {п} (Р (К_ {я})) = х,}$

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

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

${\ 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 {имеет шаблон}}) = \ 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})}}$

Но априорная вероятность того, что x является случайным набором битов, равна . Так, ${\ 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})}}}.}$

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

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

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

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

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

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

${\ Displaystyle \ forall х, Е (х) = \ {ш: R (ш) \ экв х \}}$

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

${\ Displaystyle Т (С) = \ {т: т \ к С \}}$

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

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

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

где,

${\ Displaystyle В = Е (С)}$

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

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

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

${\ Displaystyle (N \ в T) \ земля (N \ в M) \ земля (N \ neq M) \ земля (п \ в E (N) \ земля п \ в E (M))}$

${\ Displaystyle \ подразумевает (N \ neq M) \ земля R (n) \ эквив N \ земля R (n) \ эквив M}$

${\ Displaystyle \ подразумевает \ бот}$

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

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

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

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

${\ 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)}} {\ сумма _ {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)) = \ сумма _ {J: J \ in T (C) \ земля 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) = {\ гидроразрыва {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 т, п (F (т, с)) = \ сумма _ {п: р (п) \ эквив т \ земля L (п) <L (с)} 2 ^ {- L (п) }}$

Используя 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 \ в T (C) \ land P (F (j, c))> P (F (C, c))} P (F (j, c))}}}$

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

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

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

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

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

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

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