Пересмотр веры - Belief revision

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

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

Редакция и обновление

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

Обновить

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

пересмотр

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

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

Пример

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

Обновить

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

пересмотр

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

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

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

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

сокращение

устранение веры;

расширение

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

пересмотр

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

добыча

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

укрепление

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

слияние

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

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

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

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

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

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

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

Оператор ревизии, удовлетворяющий всем восьми постулатам, - это ревизия полного соответствия, в которой ${ displaystyle K * P}$ равно ${ displaystyle K + P}$ если согласовано, и дедуктивному закрытию ${ displaystyle P}$ иначе. Этот оператор проверки, удовлетворяющий всем постулатам AGM, был сочтен слишком консервативным в том смысле, что информация из старой базы знаний не сохраняется, если формула пересмотра несовместима с ней.^{[нужна цитата ]}

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

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

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

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

Сокращение

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

${ Displaystyle K * P = (K- neg P) + P}$

${ Displaystyle К-П = К крышка (К * отр. P)}$

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

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

${ Displaystyle К = (К-П) + Р}$

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

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

Тест Рамсея

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

${ displaystyle a> b in K}$ если и только если ${ displaystyle b in K * a}$

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

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

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

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

Основополагающая редакция

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

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

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

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

WIDTIO

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

Уильямс

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

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

максимальные подмножества ${ Displaystyle К чашка {P }}$ которые последовательны и содержат ${ displaystyle P}$ объединяются дизъюнкцией;

Небель

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

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

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

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

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

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

при условии формальной связи между редакцией и обновлением. Они представили идентичность Уинслетта в ^[3]

Далал

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

Сато

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

Winslett

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

Borgida

равно Уинслетту, если ${ displaystyle K}$ и ${ displaystyle P}$ непоследовательны; в противном случае результат пересмотра ${ Displaystyle K клин P}$;

Forbus

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

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

Повторная ревизия

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

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

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

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

Дарвича и Жемчужина^[4] сформулированы следующие постулаты для повторного пересмотра.

1. если ${ displaystyle alpha models mu}$ тогда ${ Displaystyle ( пси * му) * альфа эквив пси * альфа}$;
2. если ${ displaystyle alpha models neg mu}$, тогда ${ Displaystyle ( пси * му) * альфа эквив пси * альфа}$;
3. если ${ displaystyle psi * alpha models mu}$, тогда ${ Displaystyle ( пси * му) * альфа модели му}$;
4. если ${ displaystyle psi * alpha not models neg mu}$, тогда ${ Displaystyle ( psi * mu) * альфа not models neg mu}$.

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

Spohn отклонил пересмотр

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

Естественная доработка

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

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

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

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

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

Слияние

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

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

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

Арбитраж

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

Большинство

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

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

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

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

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

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

Сложность

Проблема пересмотра убеждений, наиболее изученная с точки зрения вычислительная сложность это ответ на запрос в пропозициональном случае. Это проблема установления того, следует ли формула из результата пересмотра, то есть ${ displaystyle K * P models Q}$, куда ${ displaystyle K}$, ${ displaystyle P}$, и ${ displaystyle Q}$ суть пропозициональные формулы. В более общем смысле, ответ на запрос - это проблема определения того, является ли формула результатом пересмотра убеждений, которым может быть обновление, слияние, ревизия, повторная ревизия и т. Д. Другая проблема, которая привлекла некоторое внимание, - это проблема проверка модели, то есть проверка того, удовлетворяет ли модель результату пересмотра убеждений. С этим связан вопрос, может ли такой результат быть представлен в пространстве, полиномиальном от его аргументов.

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

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

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

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

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

Реализации

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

• SATEN - объектно-ориентированный веб-движок для редактирования и извлечения (Уильямс, Sims)^[6]
• ОБЪЯВЛЕНИЯ - SAT решатель - пересмотр убеждений на основе (Бенферхат, Качи, Ле Бер, Уильямс )^[7]
• BReLS^[8]
• Бессмертный^[9]

Две системы, включая функцию пересмотра убеждений, - это SNePS.^[10] и Цикл.

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

Примечания

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

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

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