Пересмотр убеждений

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

Что делает пересмотр убеждений нетривиальным, так это то, что возможны несколько разных способов выполнения этой операции. Например, если текущие знания включают три факта: $A$ это правда», « $B$ верно» и «если $A$ и $B$ тогда это правда $C$ верно», введение новой информации» $C$ ложно» может быть сделано с сохранением последовательности только путем удаления хотя бы одного из трех фактов. В этом случае существует как минимум три различных способа выполнения пересмотра. В общем, может быть несколько различных способов изменения знаний.

Пересмотр и обновление

Обычно выделяют два вида изменений:

обновлять

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

пересмотр

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

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

Пример

Следующий классический пример показывает, что операции, выполняемые в двух настройках обновления и версии, не одинаковы. Пример основан на двух разных интерпретациях набора убеждений. $\{a\vee b\}$ и новая информация $\neg a$:

обновлять

в этом сценарии два спутника, Unit A и Unit B, вращаются вокруг Марса; спутники запрограммированы на приземление и передачу своего статуса на Землю; и Земля получила сообщение от одного из спутников, сообщающее, что она все еще находится на орбите. Однако из-за помех неизвестно, какой спутник отправил сигнал; впоследствии Земля получает сообщение о приземлении Блока А. Этот сценарий можно смоделировать следующим образом: две пропозициональные переменные. $a$ и $b$ указать, что Блок А и Блок Б, соответственно, все еще находятся на орбите; первоначальный набор убеждений $\{a\vee b\}$ (либо один из двух спутников все еще находится на орбите), и новая информация $\neg a$ (Блок А приземлился и поэтому не находится на орбите). Единственным рациональным результатом обновления является $\neg a$; поскольку первоначальная информация о том, что один из двух спутников еще не приземлился, возможно, исходила от блока А, положение блока Б неизвестно.

пересмотр

Спектакль «Шесть персонажей в поисках автора» будет показан в одном из двух местных театров. Эту информацию можно обозначить $\{a\vee b\}$, где $a$ и $b$ указывает, что спектакль будет идти в первом или во втором театре соответственно; дополнительная информация о том, что «Иисус Христос-суперзвезда» будет показан в первом театре, указывает на то, что $\neg a$ держит. В этом случае напрашивается очевидный вывод: «Шесть персонажей в поисках автора» будут идти во втором, а не в первом театре, что логически представляется $\neg a\wedge b$.

Этот пример показывает, что пересмотр убеждения $a\vee b$ с новой информацией $\neg a$ дает два разных результата $\neg a$ и $\neg a\wedge b$ в зависимости от того, является ли настройка обновлением или версией.

Сокращение, расширение, пересмотр, консолидация и слияние

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

сокращение

удаление убеждения;

расширение

добавление убеждения без проверки согласованности;

пересмотр

добавление убеждения при сохранении последовательности;

добыча

извлечение последовательного набора убеждений и/или упорядочения эпистемических закреплений;

консолидация

восстановление последовательности набора убеждений;

слияние

слияние двух или более наборов убеждений при сохранении последовательности.

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

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

Постулаты годового общего собрания акционеров

Постулаты AGM (названные в честь их сторонников Альчуррона, Герденфорса и Макинсона ) — это свойства, которым оператор, выполняющий пересмотр, должен удовлетворять, чтобы этот оператор считался рациональным. Рассматриваемая установка — это настройка пересмотра, то есть разные фрагменты информации, относящиеся к одной и той же ситуации. Рассматриваются три операции: расширение (добавление убеждения без проверки непротиворечивости), пересмотр (добавление убеждения с сохранением непротиворечивости) и сжатие (удаление убеждения).

Первые шесть постулатов называются «основными постулатами ГОСА». В условиях, рассмотренных Альчурроном, Герденфорсом и Макинсоном, текущий набор убеждений представлен дедуктивно замкнутым набором логических формул. $K$ называется набором убеждений, новая порция информации представляет собой логическую формулу $P$, а редакция выполняется бинарным оператором $*$ который принимает в качестве операндов текущие убеждения и новую информацию и создает в результате набор убеждений, представляющий результат пересмотра. $+$ оператор, обозначающий расширение: $K+P$ это дедуктивное замыкание $K\cup \{P\}$. Постулаты годового общего собрания акционеров, требующие пересмотра:

1. Закрытие: $K*P$ является набором убеждений (т.е. дедуктивно замкнутым набором формул);
2. Успех: $P\in K*P$
3. Включение: $K*P\subseteq K+P$
4. Вакуумность: ${\text{If }}(\neg P)\not \in K,{\text{ then }}K*P=K+P$
5. Последовательность: $K*P$ противоречиво если только в том случае, $P$ непоследовательно
6. Расширение: ${\text{If }}P{\text{ and }}Q{\text{ are logically equivalent, then }}K*P=K*Q$ (см. логическую эквивалентность )
7. Суперрасширение: $K*(P\wedge Q)\subseteq (K*P)+Q$
8. Подрасширение: ${\text{If }}(\neg Q)\not \in K*P{\text{ then }}(K*P)+Q\subseteq K*(P\wedge Q)$

Оператор ревизии, удовлетворяющий всем восьми постулатам, является полной ревизией, в которой $K*P$ равно $K+P$ если непротиворечиво, и к дедуктивному замыканию $P$ в противном случае. Несмотря на то, что этот оператор пересмотра удовлетворяет всем постулатам годового общего собрания акционеров, он считается слишком консервативным, поскольку никакая информация из старой базы знаний не сохраняется, если формула пересмотра несовместима с ней.

Условия, эквивалентные постулатам годового общего собрания акционеров

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

Каждый оператор редакции $*$ Удовлетворение постулатов годового общего собрания связано с набором отношений предпочтений. $\leq _{K}$, по одному на каждый возможный набор убеждений $K$, такие, что модели $K$ являются именно минимальными из всех моделей по $\leq _{K}$. Оператор ревизии и связанное с ним семейство упорядочивания связаны тем фактом, что $K*P$ — это набор формул, набор моделей которого содержит все минимальные модели $P$ в соответствии с $\leq _{K}$. Это условие эквивалентно множеству моделей $K*P$ являющийся в точности набором минимальных моделей $P$ согласно заказу $\leq _{K}$.

Порядок предпочтений $\leq _{K}$ представляет собой порядок неправдоподобия среди всех ситуаций, включая те, которые мыслимы, но в настоящее время считаются ложными. Минимальные модели в соответствии с таким упорядочением — это именно те модели базы знаний, которые в настоящее время считаются наиболее вероятными. Все другие модели превосходят эти и действительно считаются менее правдоподобными. В общем, $I<_{K}J$ указывает на то, что ситуация, представленная моделью $I$ считается более правдоподобной, чем ситуация, представленная $J$. В результате пересмотр по формуле, имеющей $I$ и $J$ поскольку модели следует выбирать только $I$ быть моделью пересмотренной базы знаний, поскольку эта модель представляет собой наиболее вероятный сценарий среди поддерживаемых $P$.

Сокращение

Сокращение – это операция по устранению убеждения. $P$ из базы знаний $K$; результат этой операции обозначается $K-P$. Операторы ревизии и сжатия связаны тождествами Леви и Харпера:

$K*P=(K-\neg P)+P$

$K-P=K\cap (K*\neg P)$

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

Один из постулатов сокращения уже давно обсуждается: постулат восстановления:

$K=(K-P)+P$

Согласно этому постулату, устранение убеждения $P$ с последующим повторным введением того же убеждения в набор убеждений должно привести к исходному набору убеждений. Есть несколько примеров, показывающих, что такое поведение не всегда разумно: в частности, сокращение общим условием, таким как $a\vee b$ приводит к устранению более специфических условий, таких как $a$ из набора убеждений; тогда неясно, почему повторное введение $a\vee b$ должно также привести к повторному введению более специфического состояния $a$. Например, если раньше считалось, что Джордж имеет немецкое гражданство, то его также считали европейцем. Принятие этого последнего убеждения равносильно прекращению веры в то, что Джордж — европеец; следовательно, то, что Джордж имеет немецкое гражданство, также исключается из набора убеждений. Если позже выяснится, что у Джорджа есть австрийское гражданство, то тот факт, что он европейец, также будет вновь введен. Однако, согласно постулату о выздоровлении, необходимо восстановить веру в то, что он также имеет немецкое гражданство.

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

Тест Рэмси

Оценка контрфактического условного предложения $a>b$ можно сделать, согласно тесту Рэмси (названному в честь Фрэнка П. Рэмси ), к гипотетическому добавлению $a$ набору текущих убеждений с последующей проверкой истинности $b$. Если $K$ представляет собой набор убеждений, существующих в данный момент, тест Рамсея формализуется следующим соответствием:

$a>b\in K$ тогда и только тогда, когда $b\in K*a$

Если рассматриваемый язык формул, представляющих убеждения, является пропозициональным, тест Рэмси дает последовательное определение контрфактических условных предложений в терминах оператора пересмотра убеждений. Однако если сам язык формул, представляющих убеждения, включает контрфактическую условную связку $>$, тест Рэмси приводит к результату тривиальности Герденфорса: не существует нетривиального оператора пересмотра, который удовлетворял бы как постулатам AGM для пересмотра, так и условию теста Рамсея. Этот результат справедлив в предположении, что контрфактические формулы типа $a>b$ могут присутствовать в наборах убеждений и формулах пересмотра. Было предложено несколько решений этой проблемы.

Немонотонное отношение вывода

При наличии фиксированной базы знаний $K$ и оператор проверки $*$, можно определить немонотонное отношение вывода, используя следующее определение: $P\vdash Q$ тогда и только тогда, когда $K*P\models Q$. Другими словами, формула $P$ влечет за собой другую формулу $Q$ если добавление первой формулы в текущую базу знаний приводит к выводу $Q$. Это соотношение вывода немонотонно.

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

Фундаментальный пересмотр

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

Этот принцип обсуждался и обсуждается в настоящее время: в то время как $\{a,b\}$ и $\{a\wedge b\}$ представляют собой два эквивалентных набора, пересмотренных $\neg a$ должно давать разные результаты. В первом случае $a$ и $b$ это два отдельных убеждения; поэтому пересмотр по $\neg a$ не должно оказывать никакого влияния на $b$, а результат ревизии $\{\neg a,b\}$. Во втором случае $a\wedge b$ принимается одно убеждение. Тот факт, что $a$ ложно, противоречит этому убеждению, которое поэтому следует удалить из набора убеждений. Таким образом, результат пересмотра $\{\neg a\}$ в этом случае.

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

Операторы ревизий-фундаменталистов, работающие над недедуктивно закрытыми наборами убеждений, обычно выбирают некоторые подмножества $K$ которые соответствуют $P$, объединил их каким-то образом, а затем соединил с $P$. Ниже приведены два недедуктивно закрытых оператора базовой редакции.

ВИДТИО

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

Уильямс

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

Гинзберг–Фегин–Ульман–Варди

максимальные подмножества $K\cup \{P\}$ которые непротиворечивы и содержат $P$ соединяются дизъюнкцией;

Туман

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

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

Пересмотр и обновление на основе модели

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

Операторы пересмотра и обновления, основанные на моделях, обычно идентифицируются по именам их авторов: Уинслетт , Форбус, Сато, Далал , Хегнер и Вебер. Согласно первым четырем из этих предложений, результат пересмотра/обновления формулы $K$ по другой формуле $P$ характеризуется набором моделей $P$ которые наиболее близки к моделям $K$. Можно определить разные понятия близости, что приводит к различию между этими предложениями.

Пеппас и Уильямс

обеспечил формальную связь между пересмотром и обновлением. Они представили тождество Уинслетта в журнале формальной логики Нотр-Дам .

Страны

модели $P$ имеющие минимальное расстояние Хэмминга до моделей $K$ выбраны в качестве моделей, возникших в результате изменения;

Сато

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

Уинслетт

для каждой модели $K$, ближайшие модели $P$ выбраны; сравнение осуществляется с использованием множества различий;

Боргида

равен Уинслетту, если $K$ и $P$ противоречивы; в противном случае результатом пересмотра будет $K\wedge P$;

Форбус

аналогично Уинслетту, но используется расстояние Хэмминга.

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

Повторная редакция

Постулаты AGM эквивалентны упорядочению предпочтений (упорядочению моделей), которое должно быть связано с каждой базой знаний. $K$. Однако они не связывают порядки, соответствующие двум неэквивалентным базам знаний. В частности, упорядочение, связанное с базой знаний $K$ и его исправленная версия $K*P$ может быть совершенно разным. Это проблема при выполнении второй ревизии, поскольку порядок, связанный с $K*P$ необходимо рассчитать $K*P*Q$.

Установление связи между упорядочением, связанным с $K$ и $K*P$ однако было признано неправильным решением этой проблемы. Действительно, отношение предпочтений должно зависеть от предыдущей истории изменений, а не только от полученной базы знаний. В более общем плане отношение предпочтений дает больше информации о душевном состоянии агента, чем простая база знаний. Действительно, два состояния ума могут представлять собой одну и ту же часть знания. $K$ и в то же время они отличаются по способу включения новой части знаний. Например, у двух человек может быть одно и то же представление о том, куда поехать в отпуск, но они расходятся во мнениях относительно того, как они изменят эту идею, если выиграют в лотерею на миллион долларов. Поскольку основным условием упорядочения предпочтений является то, что их минимальные модели являются в точности моделями связанной с ними базы знаний, базу знаний можно считать неявно представленной упорядочением предпочтений (но не наоборот).

Учитывая, что упорядочение предпочтений позволяет получить связанную с ним базу знаний, но также позволяет выполнить один этап пересмотра, исследования итеративного пересмотра были сосредоточены на том, как следует изменить порядок предпочтений в ответ на пересмотр. В то время как одноэтапная ревизия касается того, как база знаний $K$ должна быть заменена на новую базу знаний $K*P$Итерированный пересмотр заключается в том, как порядок предпочтений (представляющий как текущие знания, так и то, сколько ситуаций, которые считаются ложными, считаются возможными) должен быть превращен в новое отношение предпочтений, когда $P$ изучается. Один шаг повторной проверки приводит к новому порядку, позволяющему вносить дальнейшие изменения.

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

Дарвич и Перл сформулировал следующие постулаты для повторного пересмотра.

1. если $\alpha \models \mu$ затем $(\psi *\mu )*\alpha \equiv \psi *\alpha$;
2. если $\alpha \models \neg \mu$, затем $(\psi *\mu )*\alpha \equiv \psi *\alpha$;
3. если $\psi *\alpha \models \mu$, затем $(\psi *\mu )*\alpha \models \mu$;
4. если $\psi *\alpha \not \models \neg \mu$, затем $(\psi *\mu )*\alpha \not \models \neg \mu$.

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

Спон отклонил редакцию

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

Естественная ревизия

при пересмотре порядка предпочтений по формуле $P$, все минимальные модели (в соответствии с порядком предпочтений) $P$ становятся более предпочтительными среди всех остальных; исходный порядок моделей сохраняется при сравнении двух моделей, не являющихся минимальными моделями $P$; этот оператор минимально меняет порядок среди моделей, сохраняя при этом свойство, которое модели базы знаний после проверки $P$ это минимальные модели $P$ в соответствии с порядком предпочтений;

Трансмутации

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

Рейтинговая версия

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

Слияние

Предположение, заложенное в операторе проверки, заключается в том, что новая порция информации $P$ всегда следует считать более надежным, чем старая база знаний $K$. Это формализовано вторым постулатом годового общего собрания: $P$ всегда верят после пересмотра $K$ с $P$. В более общем смысле можно рассматривать процесс объединения нескольких фрагментов информации (а не двух), которые могут иметь или не иметь одинаковую надежность. Пересмотр становится частным случаем этого процесса, когда менее надежная часть информации $K$ объединен с более надежным $P$.

Хотя входными данными для процесса пересмотра является пара формул $K$ и $P$, входными данными для слияния является мультинабор формул $K$, $T$и т. д. Использование мультинаборов необходимо, поскольку два источника для процесса слияния могут быть идентичными.

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

Арбитраж

результат арбитража двух баз знаний $K$ и $T$ влечет за собой $K\vee T$; это условие формализует предположение о сохранении как можно большего количества старой информации, поскольку оно эквивалентно предположению, что каждая формула, вытекающая из обеих баз знаний, также вытекает из результата их арбитража; в возможном мировоззрении «реальный» мир предполагается одним из миров, считающихся возможными согласно хотя бы одной из двух баз знаний;

Большинство

результат объединения базы знаний $K$ с другими базами знаний может быть вынуждено повлечь за собой $K$ путем добавления достаточного количества других баз знаний, эквивалентных $K$; это условие соответствует своего рода голосованию большинством: достаточно большое количество баз знаний всегда может превзойти «мнение» любого другого фиксированного набора баз знаний.

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

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

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

Теория социального выбора

Многие предложения по пересмотру включают в себя упорядочение моделей, отражающих относительную правдоподобность возможных альтернатив. Проблема слияния сводится к объединению набора порядков в один, выражающий совокупную правдоподобность альтернатив. Это похоже на то, что делается в теории социального выбора , которая изучает то, как предпочтения группы агентов могут быть рационально объединены. Пересмотр убеждений и теория социального выбора схожи в том, что они объединяют множество порядков в один. Они расходятся в том, как интерпретируются эти упорядочения: предпочтения в теории социального выбора; правдоподобие в пересмотре убеждений. Другое отличие состоит в том, что альтернативы явно перечисляются в теории социального выбора, тогда как они представляют собой пропозициональные модели для данного алфавита при пересмотре убеждений.

Сложность

С точки зрения вычислительной сложности , наиболее изученной проблемой пересмотра убеждений является проблема ответа на запрос в пропозициональном случае. Это проблема установления того, следует ли формула из результата пересмотра, т. е. $K*P\models Q$, где $K$, $P$, и $Q$ являются формулами высказываний. В более общем смысле, ответ на запрос — это проблема определения того, является ли формула результатом пересмотра убеждений, который может быть обновлением, слиянием, пересмотром, повторным пересмотром и т. д. Еще одна проблема, которая привлекла некоторое внимание, — это проверка модели . то есть проверка того, удовлетворяет ли модель результату пересмотра убеждений. Связанный с этим вопрос заключается в том, может ли такой результат быть представлен в полиномиальном пространстве относительно его аргументов.

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

Различают операторы проверки убеждений и схемы проверки убеждений. В то время как первые представляют собой простые математические операторы, преобразующие пару формул в другую формулу, вторые зависят от дополнительной информации, такой как отношение предпочтения. Например, редакция Далаля является оператором, поскольку однажды две формулы $K$ и $P$ заданы, никакой другой информации для расчета не требуется. $K*P$. С другой стороны, пересмотр, основанный на отношении предпочтения, является схемой пересмотра, поскольку $K$ и $P$ не позволяют определить результат ревизии, если не задано семейство порядков предпочтений между моделями. Сложность схем ревизий определяется в предположении, что дополнительная информация, необходимая для расчета ревизии, задается в некоторой компактной форме. Например, отношение предпочтения может быть представлено последовательностью формул, модели которых становятся все более предпочтительными. Явное сохранение отношения в виде набора пар моделей не является компактным представлением предпочтений, поскольку требуемое пространство экспоненциально зависит от количества пропозициональных букв.

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

Актуальность

Были достигнуты новые прорывные результаты, которые демонстрируют, как релевантность может быть использована для пересмотра убеждений. Уильямс , Пеппас, Фу и Чопра сообщили о результатах в журнале «Искусственный интеллект» .

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

Реализации

Системы, специально реализующие пересмотр убеждений:

• SATEN — объектно-ориентированная веб-система редактирования и извлечения ( Williams , Sims)
• ADS – проверка убеждений на основе решателя SAT (Бенферхат, Качи, Ле Берр, Уильямс )
• БРЕЛС
• Бессмертный

Две системы, включающие функцию пересмотра убеждений, — это SNePS. и Цик .

См. также

• Байесовский вывод
• Распространение убеждений
• Оправданное рассуждение
• Дискурсивная дилемма
• Эпистемическое закрытие
• Расследование
• Представление знаний
• Лодка Нейрата
• Немонотонная логика
• Философия науки
• Ведение причины
• Рассуждение

Ссылки

• CE Алчуррон, П. Гарденфорс и Д. Макинсон (1985). О логике изменения теории: Частичное соответствие функциям сжатия и пересмотра. Журнал символической логики , 50:510–530.
• Антониу, Г. и М.А. Уильямс (1997) Немонтоническое рассуждение, MIT Press.
• Антониу, Г. и М.А. Уильямс (1995) Рассуждения с неполной и изменяющейся информацией, в материалах Международной совместной конференции по информационным наукам, 568-572.
• Т. Араванис, П. Пеппас и М. А. Уильямс , (2017) Характеристика эпистемического закрепления аксиомы Париха, на Международной совместной конференции по искусственному интеллекту IJCAI-17, стр. 772-778.
• С. Бенферхат, Д. Дюбуа, Х. Прад и М. А. Уильямс (2002). Практический подход к объединению приоритетных баз знаний, Studia Logica: Международный журнал символической логики, 70 (1): 105-130.
• С. Бенферхат, С. Качи, Д. Ле Берр, М. А. Уильямс (2004) Ослабление противоречивой информации для повторного пересмотра и интеграции знаний, Журнал искусственного интеллекта, том 153, 1-2, 339-371.
• К. Бутилье (1993). Последовательности изменений и вложенные условия. В материалах тринадцатой Международной совместной конференции по искусственному интеллекту (IJCAI'93) , страницы 519–525.
• К. Бутилье (1995). Обобщенное обновление: изменение убеждений в динамических настройках. В материалах четырнадцатой международной совместной конференции по искусственному интеллекту (IJCAI'95) , страницы 1550–1556.
• К. Бутилье (1996). Похищение вероятных причин: событийно-ориентированная модель обновления убеждений. Искусственный интеллект , 83:143–166.
• М. Кадоли, Ф. М. Донини, П. Либераторе и М. Шарф (1999). Размер пересмотренной базы знаний. Искусственный интеллект , 115(1):25–64.
• Т. Чоу и М. Уинслетт (1991). Бессмертный: система пересмотра убеждений, основанная на моделях. В материалах Второй Международной конференции по принципам представления и рассуждения знаний (KR'91) , страницы 99–110. Издательство Морган Кауфманн.
• М. Далал (1988). Исследования по теории ревизии базы знаний: Предварительный отчет. В материалах седьмой национальной конференции по искусственному интеллекту (AAAI'88) , страницы 475–479.
• Т. Эйтер и Г. Готтлоб (1992). О сложности пропозициональной проверки базы знаний, обновлений и контрфактов. Искусственный интеллект , 57:227–270.
• Т. Эйтер и Г. Готтлоб (1996). Сложность вложенных контрфактов и повторяющихся изменений базы знаний. Журнал компьютерных и системных наук , 53 (3): 497–512.
• Р. Феджин, Дж. Д. Ульман и М. И. Варди (1983). О семантике обновлений в базах данных. В материалах второго симпозиума ACM SIGACT SIGMOD по принципам систем баз данных (PODS'83) , страницы 352–365.
• М. А. Фалаппа, Г. Керн-Исбернер, Г. Р. Симари (2002): Объяснения, пересмотр убеждений и опровергаемые рассуждения. Искусственный интеллект , 141(1–2): 1–28.
• М. Фройнд и Д. Леманн (2002). Пересмотр убеждений и рациональный вывод. Препринт Arxiv cs.AI/0204032 .
• Н. Фридман и Дж. Я. Халперн (1994). Основанная на знаниях основа изменения убеждений, часть II: Пересмотр и обновление. В материалах Четвертой Международной конференции по принципам представления и рассуждения знаний (KR'94) , страницы 190–200.
• А. Фурманн (1991). Теория сокращения через сокращение базы. Журнал философской логики , 20:175–203.
• Д. Габбай, Г. Пигоцци и Дж. Вудс (2003). Контролируемая ревизия - алгоритмический подход к пересмотру убеждений, Журнал логики и вычислений , 13 (1): 15–35.
• П. Герденфорс и Уильямс (2001). Рассуждения о категориях в концептуальных пространствах, в материалах Международной совместной конференции по искусственному интеллекту (IJCAI), 385–392.
• П. Герденфорс и Д. Макинсон (1988). Пересмотр систем знаний с использованием эпистемического закрепления. В материалах Второй конференции по теоретическим аспектам рассуждений о знаниях (TARK'88) , страницы 83–95.
• П. Герденфорс и Х. Ротт (1995). Пересмотр убеждений. В Справочнике по логике в искусственном интеллекте и логическом программировании, том 4 , страницы 35–132. Издательство Оксфордского университета.
• Г. Гране и Альберто О. Мендельзон (1995). Обновления и сослагательные запросы. Информация и вычисления , 2(116):241–252.
• Г. Гране, Альберто О. Мендельзон и П. Ревес (1992). Трансформации знаний. В материалах одиннадцатого симпозиума ACM SIGACT SIGMOD SIGART по принципам систем баз данных (PODS'92) , страницы 246–260.
• С.О. Ханссон (1999). Учебник динамики убеждений . Дордрехт: Kluwer Academic Publishers.
• А. Герциг (1996). ПМА пересмотрено. В материалах Пятой Международной конференции по принципам представления и рассуждения знаний (KR'96) , страницы 40–50.
• А. Герциг (1998). Логика обновления базы убеждений. В Д. Дюбуа, Д. Габбе, Х. Праде и П. Сметсе, редакторах, «Справочник по опровергаемым рассуждениям и управлению неопределенностью» , том 3 – Изменение убеждений, страницы 189–231. Академическое издательство Клювер.
• А. Кароль и М.А. Уильямс (2005). Понимание человеческих стратегий пересмотра убеждений: Конференция по теоретическим аспектам рациональности и знаний (TARK) Халперн, Дж. и ВандерМейден (ред.).
• Х. Кацуно и А.О. Мендельзон (1991). О разнице между обновлением базы знаний и ее пересмотром. В материалах Второй международной конференции по принципам представления и рассуждения знаний (KR'91) , страницы 387–394.
• Х. Кацуно и А.О. Мендельзон (1991). Предложенный пересмотр базы знаний и минимальные изменения. Искусственный интеллект , 52:263–294.
• С. Конечны и Р. Пино Перес (1998). По логике слияния. В материалах Шестой Международной конференции по принципам представления и рассуждения знаний (KR'98) , страницы 488–498.
• Д. Леманн (1995). Пересмотр убеждений, пересмотренный. В материалах четырнадцатой международной совместной конференции по искусственному интеллекту (IJCAI'95) , страницы 1534–1540.
• П. Либераторе (1997). Сложность повторного пересмотра убеждений. В материалах Шестой Международной конференции по теории баз данных (ICDT'97) , страницы 276–290.
• П. Либераторе и М. Шарф (1998). Арбитраж (или как объединить базы знаний). IEEE Transactions on Knowledge and Data Engineering , 10(1):76–90.
• П. Либераторе и М. Шерф (2000). BReLS: Система интеграции баз знаний. В материалах Седьмой Международной конференции по принципам представления и рассуждения знаний (KR 2000) , страницы 145–152.
• В. Лю и М. А. Уильямс (2001). Структура пересмотра многоагентных убеждений, Studia Logica: Международный журнал, том. 67(2), 219 – 312.
• В. Лю и Уильямс (2002). Надежность источников информации и интеллектуальные агенты происхождения информации VIII, Серия: Конспекты лекций по информатике. Том 2333: 290–306.
• В. Лю и Уильямс (1999) Структура пересмотра многоагентных убеждений, Часть I: Роль онтологии, LNAI № 1747, Расширенные темы искусственного интеллекта, Springer Verlag, 168–180.
• Д. Макинсон (1985). Как сдаться: обзор некоторых формальных аспектов логики изменения теории. Синтез , 62:347–363.
• Макниш, К. и М.А. Уильямс (1998). От пересмотра убеждений к пересмотру проекта: применение изменений теории к изменению требований, LNAI, Springer Verlag, 207–222.
• Б. Небель (1991). Пересмотр убеждений и рассуждения по умолчанию: подходы, основанные на синтаксисе. В материалах Второй Международной конференции по принципам представления и рассуждения знаний (KR'91) , страницы 417–428.
• Б. Небель (1994). Базовые операции и схемы ревизии: семантика, представление и сложность. В материалах одиннадцатой Европейской конференции по искусственному интеллекту (ECAI'94) , страницы 341–345.
• Б. Небель (1996). Насколько сложно пересмотреть базу знаний? Технический отчет 83, Фрайбургский университет Альберта Людвига, Институт компьютерных наук.
• П. Пеппас и М. А. Уильямс (1995). Конструктивное моделирование изменения теории, Журнал формальной логики Нотр-Дам, специальный выпуск о пересмотре убеждений, Kluwer, Том 36, № 1, 120–133.
• П. Пеппас, П., М.А. Уильямс , Чопра, С. и Фу, Н. (2015). Актуальность в пересмотре убеждений. Искусственный интеллект, 229, 126–138.
• П. Пеппас, М. А. Уильямс (2016). Кинетическая последовательность и актуальность в пересмотре убеждений. Европейская конференция по логике искусственного интеллекта (JELIA), LNCS, стр. 401–414.
• П. Пеппас и Уильямс (2014). Изменение убеждений и полупорядки. В Т. Эйтере, К. Барале и Г. Де Джакомо (ред.), http://www.aaai.org/Press/Proceedings/kr14.php . Менло-Парк, США: AAAI.
• А. Переа (2003). Правильная рационализация и пересмотр убеждений в динамических играх . Меморандум об исследовании 048: МЕТЕОР, Маастрихтская исследовательская школа экономики технологий и организации.
• Дж. Пигоцци (2005). Два парадокса агрегации в принятии социальных решений: парадокс Острогорского и дискурсивная дилемма , Эпистема: Журнал социальной эпистемологии , 2(2): 33–42.
• Дж. Пигоцци (2006). Слияние убеждений и дискурсивная дилемма: аргументированное объяснение парадоксов агрегирования суждений . Синтез 152 (2): 285–298.
• П. З. Ревес (1993). О семантике теории изменений: арбитраж между старой и новой информацией. В материалах двенадцатого симпозиума ACM SIGACT SIGMOD SIGART по принципам систем баз данных (PODS'93) , страницы 71–82.
• К. Сато (1988). Немонотонное рассуждение путем минимального пересмотра убеждений. В материалах Международной конференции по компьютерным системам пятого поколения (FGCS'88) , страницы 455–462.
• Шохам, Йоав; Лейтон-Браун, Кевин (2009). Мультиагентные системы: алгоритмические, теоретико-игровые и логические основы . Нью-Йорк: Издательство Кембриджского университета . ISBN  978-0-521-89943-7 . См. раздел 14.2; можно скачать бесплатно в Интернете .
• В. С. Субраманян (1994). Объединение баз знаний. Транзакции ACM в системах баз данных , 19(2):291–331.
• А. Вебер (1986). Обновление пропозициональных формул. В Proc. Первой конф. «Экспертные системы баз данных» , страницы 487–500.
• М. А. Уильямс и Ханс Ротт (2001). Границы в пересмотре убеждений, Клувер.
• МА. Уильямс (1994). Трансмутации систем знаний. В материалах Четвертой Международной конференции по принципам представления и рассуждения знаний (KR'94) , страницы 619–629.
• МА. Уильямс и А. Симс (2000). SATEN: Объектно-ориентированная веб-система проверки и извлечения, в материалах 8-го международного семинара по немонтоническому рассуждению, Барал, К. и Трушчински, М. (редакторы), Автоматизированные архивы электронной печати на https://arxiv. org/abs/cs.AI/0003059
• МА. Уильямс (1997). Пересмотр убеждений посредством обновления базы данных, в материалах Международной конференции по интеллектуальным информационным системам, 410-415.
• МА. Уильямс (1997). Anytime Revision, в материалах Международной совместной конференции по искусственному интеллекту (IJCAI), Морган Кауфманн, Сан-Франциско, 74–80.
• МА. Уильямс (1996). К практическому подходу к пересмотру убеждений: изменение, основанное на разуме, Proc International Conf on Principles of Knowledge and Reasoning KR'96, Morgan Kaufmann, 412-421.
• МА. Уильямс (1996) Здравый подход к пересмотру убеждений, в материалах Третьего международного симпозиума по здравому смыслу, 1996, Стэнфордский университет, 245–262.
• МА. Уильямс (1995) Изменение немонотонных отношений вывода, в материалах Второй Всемирной конференции по основам искусственного интеллекта, 469-482.
• МА. Уильямс (1995) Пересмотр базовой теории: вычислительная модель, в материалах четырнадцатой Международной совместной конференции по искусственному интеллекту (IJCAI), Морган Кауфманн, 1541–1550.
• МА. Уильямс , Паньюкко М., Фу Н. и Симс Б. (1995) Определение объяснений с использованием трансмутации знаний, Proc 14th Int. Объединенная конференция по искусственному интеллекту (IJCAI), Морган Кауфман 822-830.
• МА. Уильямс (1994). О логике изменения базы теории, в К. Макнише, Д. Пирсе, Л. Перриа (редакторы), Логика в искусственном интеллекте, Серия лекций по информатике, № 838, Springer-Verlag, 86-105.
• МА. Уильямс (1994). Объяснение и трансформация теоретической базы, в материалах Европейской конференции по искусственному интеллекту (ECAI), Wiley, Лондон, 341–346.
• МА. Уильямс и Фу, Нью-Йорк (1990) Немонотонная динамика логики по умолчанию, в материалах Европейской конференции по искусственному интеллекту (ECAI), Wiley, Лондон, 702-707.
• М. Уинслетт (1989). Иногда обновления ограничены. В материалах одиннадцатой Международной совместной конференции по искусственному интеллекту (IJCAI'89) , страницы 859–863.
• М. Уинслетт (1990). Обновление логических баз данных . Издательство Кембриджского университета.
• Ю. Чжан и Н. Фу (1996). Обновление баз знаний разъединительной информацией. В материалах тринадцатой национальной конференции по искусственному интеллекту (AAAI'96) , страницы 562–568.

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

• Пересмотр убеждений в PhilPapers
• Логика пересмотра убеждений в проекте онтологии философии Индианы
• Залта, Эдвард Н. (ред.). «Логика пересмотра убеждений» . Стэнфордская энциклопедия философии .
• Отменяемое рассуждение: 4.3 Теория пересмотра убеждений в Стэнфордской энциклопедии философии