Rewizja przekonań - Belief revision

Rewizja przekonań to proces zmiany przekonań w celu uwzględnienia nowej informacji. Logiczne formalizacja rewizji przekonań jest badane w filozofii , w bazach danych oraz w sztucznej inteligencji w projektowaniu czynników racjonalnych .

To, co sprawia, że ​​rewizja przekonań nie jest trywialna, to fakt, że możliwe jest kilka różnych sposobów wykonania tej operacji. Na przykład, jeśli aktualna wiedza obejmuje trzy fakty „ jest prawdą”, „ jest prawdą” oraz „jeśli i są prawdziwe to jest prawdą”, wprowadzenie nowej informacji „ jest fałszem” można dokonać z zachowaniem spójności tylko poprzez usunięcie przy przynajmniej jeden z trzech faktów. W takim przypadku istnieją co najmniej trzy różne sposoby wykonania rewizji. Ogólnie rzecz biorąc, może istnieć kilka różnych sposobów zmiany wiedzy. ${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle C}$${\ Displaystyle C}$

Rewizja i aktualizacja

Zwykle rozróżnia się dwa rodzaje zmian:

aktualizacja

nowe informacje dotyczą obecnej sytuacji, podczas gdy stare wierzenia odnoszą się do przeszłości; aktualizacja jest operacją zmiany starych przekonań w celu uwzględnienia zmiany;

rewizja

zarówno stare przekonania, jak i nowe informacje odnoszą się do tej samej sytuacji; niespójność między nową i starą informacją tłumaczy się tym, że stare informacje mogą być mniej wiarygodne niż nowe; rewizja to proces wprowadzania nowych informacji do zbioru starych przekonań bez generowania niespójności.

Głównym założeniem rewizji przekonań jest minimalna zmiana: wiedza przed i po zmianie powinna być jak najbardziej zbliżona. W przypadku aktualizacji zasada ta formalizuje założenie bezwładności. W przypadku rewizji zasada ta wymusza zachowanie jak największej ilości informacji w wyniku zmiany.

Przykład

Poniższy klasyczny przykład pokazuje, że operacje do wykonania w dwóch ustawieniach aktualizacji i rewizji nie są takie same. Przykład opiera się na dwóch różnych interpretacjach zestawu przekonań i nowej informacji : ${\displaystyle \{a\vee b\}}$${\ Displaystyle \ neg a}$

aktualizacja

w tym scenariuszu dwa satelity, Jednostka A i Jednostka B, krążą wokół Marsa; satelity są zaprogramowane do lądowania podczas przesyłania swojego statusu na Ziemię; a Ziemia otrzymała transmisję z jednego z satelitów, informując, że nadal znajduje się na orbicie. Jednak ze względu na zakłócenia nie wiadomo, który satelita wysłał sygnał; następnie Ziemia otrzymuje wiadomość, że Jednostka A wylądowała. Scenariusz ten można modelować w następujący sposób: dwie zmienne zdaniowe i wskazują, że odpowiednio Jednostka A i Jednostka B nadal znajdują się na orbicie; początkowy zestaw przekonań to (jeden z dwóch satelitów jest nadal na orbicie), a nowa informacja to (jednostka A wylądowała, a zatem nie znajduje się na orbicie). Jedynym racjonalnym wynikiem aktualizacji jest ; ponieważ początkowe informacje, że jeden z dwóch satelitów jeszcze nie wylądował, prawdopodobnie pochodziły z jednostki A, pozycja jednostki B nie jest znana.${\displaystyle a}$${\displaystyle b}$${\displaystyle \{a\vee b\}}$${\ Displaystyle \ neg a}$${\ Displaystyle \ neg a}$

rewizja

spektakl „Sześć postaci w poszukiwaniu autora” zostanie wystawiony w jednym z dwóch lokalnych teatrów. Informacja ta może być oznaczona przez , gdzie i wskazuje, że przedstawienie będzie wystawiane odpowiednio w pierwszym lub drugim teatrze; dalsze informacje, że w pierwszym teatrze zostanie wystawiony "Jesus Christ Superstar" wskazuje, że się zgadza. W tym przypadku oczywisty wniosek jest taki, że „Sześć postaci w poszukiwaniu autora” zostanie wystawionych w drugim, ale nie w pierwszym teatrze, co logicznie przedstawia .${\displaystyle \{a\vee b\}}$${\displaystyle a}$${\displaystyle b}$${\ Displaystyle \ neg a}$${\ Displaystyle \ neg a \ klin b}$

Ten przykład pokazuje, że rewizja przekonania za pomocą nowych informacji daje dwa różne wyniki i zależy od tego, czy ustawienie jest aktualizacją, czy zmianą. ${\displaystyle a\vee b}$${\ Displaystyle \ neg a}$${\ Displaystyle \ neg a}$${\ Displaystyle \ neg a \ klin b}$

Zmniejszanie, rozszerzanie, weryfikacja, konsolidacja i łączenie

W sytuacji, w której wszystkie przekonania odnoszą się do tej samej sytuacji, dokonuje się rozróżnienia między różnymi operacjami, które można wykonać:

skurcz

usunięcie przekonania;

ekspansja

dodanie przekonania bez sprawdzania spójności;

rewizja

dodanie przekonania przy zachowaniu spójności;

ekstrakcja

wydobywanie spójnego zestawu przekonań i/lub epistemicznego porządku okopów;

konsolidacja

przywracanie spójności zbioru przekonań;

scalanie

połączenie dwóch lub więcej zestawów przekonań przy zachowaniu spójności.

Rewizja i łączenie różnią się tym, że pierwsza operacja jest wykonywana, gdy nowe przekonanie do włączenia jest uważane za bardziej niezawodne niż stare; dlatego spójność jest utrzymywana przez usunięcie niektórych starych przekonań. Łączenie jest operacją bardziej ogólną, ponieważ priorytet wśród zestawów przekonań może być taki sam lub nie.

Rewizję można przeprowadzić, najpierw wprowadzając nowy fakt, a następnie przywracając spójność poprzez konsolidację. W rzeczywistości jest to raczej forma scalania niż rewizji, ponieważ nowe informacje nie zawsze są traktowane jako bardziej wiarygodne niż stara wiedza.

Postulaty ZWZ

Postulaty AGM (nazwane imionami ich zwolenników, Alchourrón, Gärdenfors i Makinson ) są właściwościami, które operator wykonujący rewizję powinien spełniać, aby można było uznać ten operator za racjonalny. Rozważane ustawienie to powtórka, czyli różne informacje odnoszące się do tej samej sytuacji. Rozważane są trzy operacje: rozwinięcie (dodanie przekonania bez sprawdzania spójności), korekta (dodanie przekonania przy zachowaniu spójności) i skrócenie (usunięcie przekonania).

Sześć pierwszych postulatów to „podstawowe postulaty ZWZ”. W ustawieniach rozważanych przez Alchourróna, Gärdenforsa i Makinsona obecny zestaw przekonań jest reprezentowany przez dedukcyjnie zamknięty zestaw logicznych formuł zwanego zbiorem przekonań, nową informacją jest formuła logiczna , a korekta jest wykonywana przez operator binarny, który przyjmuje jako operandy bieżące przekonania i nowe informacje i tworzy w rezultacie zestaw przekonań reprezentujący wynik rewizji. Operatora oznaczona rozprężania: jest dedukcji zamknięcia . Postulaty ZWZ do rewizji to: ${\ Displaystyle K}$${\displaystyle P}$${\ Displaystyle *}$${\displaystyle +}$${\ Displaystyle K+P}$${\ Displaystyle K \ filiżanka \ {P \}}$

1. Zamknięcie: jest zbiorem przekonań (tj. dedukcyjnie zamkniętym zbiorem formuł);${\ Displaystyle K * P}$
2. Sukces: ${\ Displaystyle P \ w K * P}$
3. Włączenie: ${\ Displaystyle K * P \ podseteq K + P}$
4. Pustka: ${\ Displaystyle {\ tekst {jeśli}} (\ neg P) \ nie \ w K {\ tekst {to}} K * P = K + P}$
5. ${\ Displaystyle K * P}$jest niespójny tylko wtedy, gdy jest niespójny${\displaystyle P}$
6. Rozszerzalność: (patrz równoważność logiczna )${\displaystyle {\text{Jeśli}}P{\text{i}}Q{\text{są logicznie równoważne, to }}K*P=K*Q}$
7. ${\ Displaystyle K * (P \ klin Q) \ subseteq (K * P) + Q}$
8. ${\ Displaystyle {\ tekst {jeśli}} (\ neg Q) \ nie \ w K * P {\ tekst {to}} (K * P) + Q \ podseteq K * (P \ klin Q)}$

Operatorem rewizji, który spełnia wszystkie osiem postulatów, jest pełna rewizja, w której jest równa, jeśli jest spójna, oraz dedukcyjne zamknięcie w przeciwnym wypadku. Spełniając wszystkie postulaty ZWZ, ten operator rewizji został uznany za zbyt konserwatywny, ponieważ nie są zachowywane żadne informacje ze starej bazy wiedzy, jeśli formuła rewizji jest z nią niezgodna. ${\ Displaystyle K * P}$${\ Displaystyle K+P}$${\displaystyle P}$

Warunki równoważne postulatom ZWZ

Postulaty ZWZ są równoważne kilku różnym warunkom dotyczącym operatora rewizji; w szczególności są one równoważne operatorowi rewizji, który można zdefiniować w kategoriach struktur zwanych funkcjami selekcji, okopami epistemicznymi, systemami sfer i relacjami preferencji. Te ostatnie są refleksyjnymi , przechodnimi i całkowitymi relacjami nad zbiorem modeli.

Każdy operator rewizji spełniający postulaty AGM jest powiązany ze zbiorem relacji preferencji , po jednym dla każdego możliwego zbioru przekonań , tak że modele są dokładnie minimalnym ze wszystkich modeli według . Operator rewizji i związana z nim rodzina porządków są powiązane tym, że jest to zbiór formuł, którego zbiór modeli zawiera wszystkie modele minimalne według . Warunek ten jest równoznaczny ze zbiorem modeli będącym dokładnie zbiorem modeli minimalnych według zamówienia . ${\ Displaystyle *}$${\ 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}}$

Uporządkowanie preferencji reprezentuje porządek nieprawdopodobny we wszystkich sytuacjach, w tym w tych, które są możliwe do wyobrażenia, ale obecnie uważane są za fałszywe. Modele minimalne według takiego uporządkowania są właśnie modelami bazy wiedzy, czyli modelami, które są obecnie uważane za najbardziej prawdopodobne. Wszystkie inne modele są większe niż te i rzeczywiście są uważane za mniej wiarygodne. Ogólnie wskazuje, że sytuacja reprezentowana przez model jest uważana za bardziej prawdopodobną niż sytuacja reprezentowana przez . W rezultacie, korekta według formuły zawierającej i jako modele powinna być wybierana tylko jako model zrewidowanej bazy wiedzy, ponieważ model ten reprezentuje najbardziej prawdopodobny scenariusz spośród tych wspieranych przez . ${\ Displaystyle \ Leq _ {K}}$${\ Displaystyle I<_ {K} J}$${\ Displaystyle I}$${\ Displaystyle J}$${\ Displaystyle I}$${\ Displaystyle J}$${\ Displaystyle I}$${\displaystyle P}$

Skurcz

Skrócenie to operacja usunięcia przekonania z bazy wiedzy ; wynik tej operacji jest oznaczony przez . Operatory rewizji i skurczów są powiązane tożsamościami Levi i Harper: ${\displaystyle P}$${\ Displaystyle K}$${\ Displaystyle KP}$

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

${\ Displaystyle KP = K \ czapka (K * \ neg P)}$

Określono osiem postulatów dotyczących skrócenia. Ilekroć operator rewizji spełnia osiem postulatów rewizji, odpowiadający mu operator skrócenia spełnia osiem postulatów skrócenia i vice versa. Jeśli operator skrócenia spełnia co najmniej sześć pierwszych postulatów skrócenia, przełożenie go na operator rewizji, a następnie z powrotem na operator skrócenia przy użyciu dwóch powyższych tożsamości prowadzi do pierwotnego operatora skrócenia. To samo obowiązuje, zaczynając od operatora rewizji.

Jeden z postulatów skurczu był długo omawiany: postulat zdrowienia:

${\ Displaystyle K = (KP) + P}$

Zgodnie z tym postulatem, usunięcie przekonania, a następnie ponowne wprowadzenie tego samego przekonania do zbioru przekonań powinno prowadzić do pierwotnego zbioru przekonań. Istnieje kilka przykładów pokazujących, że takie zachowanie nie zawsze jest rozsądne: w szczególności skrócenie przez warunek ogólny, taki jak prowadzi do usunięcia bardziej szczegółowych warunków, takich jak ze zbioru przekonań; nie jest więc jasne, dlaczego ponowne wprowadzenie powinno również prowadzić do ponownego wprowadzenia bardziej specyficznego stanu . Na przykład, jeśli wcześniej sądzono, że George ma obywatelstwo niemieckie, uważano go również za Europejczyka. Skrócenie tego ostatniego przekonania jest równoznaczne z przestaniem wierzyć, że George jest Europejczykiem; w związku z tym, że George ma obywatelstwo niemieckie jest również wycofane z zestawu przekonań. Jeśli później okaże się, że George ma obywatelstwo austriackie, przywrócono również fakt, że jest Europejczykiem. Zgodnie z postulatem uzdrowienia należy jednak przywrócić przekonanie, że ma on również obywatelstwo niemieckie. ${\displaystyle P}$${\displaystyle a\vee b}$${\displaystyle a}$${\displaystyle a\vee b}$${\displaystyle a}$

Korespondencja między rewizją a skróceniem wywołanym przez tożsamości Leviego i Harpera jest taka, że ​​skrócenie niespełniające postulatu uzdrowienia jest tłumaczone na rewizję spełniającą wszystkie osiem postulatów, a rewizja spełniająca wszystkie osiem postulatów jest tłumaczona na skrócenie spełniające wszystkie osiem postulatów , w tym odzyskiwanie. W rezultacie, jeśli odzyskiwanie jest wyłączone z rozważania, wiele operatorów skrócenia jest tłumaczonych na jeden operator zmiany, który można następnie przełożyć z powrotem na dokładnie jeden operator skrócenia. Ten operator jest jedynym z początkowej grupy operatorów skurczu, który spełnia warunki odzyskiwania; wśród tej grupy to operator przechowuje jak najwięcej informacji.

Test Ramseya

Ocenę kontrfaktycznego warunkowego można przeprowadzić, zgodnie z testem Ramseya (nazwanym na cześć Franka P. Ramseya ), do hipotetycznego dodania do zbioru aktualnych przekonań, a następnie sprawdzenia prawdziwości . Jeśli jest zbiorem obecnie posiadanych przekonań, test Ramseya jest sformalizowany przez następującą korespondencję: ${\displaystyle a>b}$${\displaystyle a}$${\displaystyle b}$${\ Displaystyle K}$

${\displaystyle a>b\w k}$ wtedy i tylko wtedy gdy ${\ Displaystyle b \ w K * a}$

Jeśli rozważany język formuł reprezentujących przekonania jest zdaniowy, test Ramseya daje spójną definicję kontrfaktycznych warunków warunkowych w postaci operatora rewizji przekonań. Jeśli jednak sam język formuł reprezentujących przekonania zawiera kontrfaktyczny spójnik warunkowy , test Ramseya prowadzi do wyniku trywialności Gärdenforsa: nie ma nietrywialnego operatora rewizji, który spełniałby zarówno postulaty AGM dotyczące rewizji, jak i warunek testu Ramseya. Wynik ten opiera się na założeniu, że formuły kontrfaktyczne, takie jak, mogą być obecne w zestawach przekonań i formułach poprawiających. Zaproponowano kilka rozwiązań tego problemu. ${\displaystyle>}$${\displaystyle a>b}$

Niemonotoniczna relacja wnioskowaniaonic

Mając ustaloną bazę wiedzy i operator rewizji , można zdefiniować niemonotoniczną relację wnioskowania za pomocą następującej definicji: wtedy i tylko wtedy . Innymi słowy, formuła pociąga za sobą inną formułę, jeśli dodanie pierwszej formuły do ​​bieżącej bazy wiedzy prowadzi do wyprowadzenia . Ta relacja wnioskowania jest niemonotoniczna. ${\ Displaystyle K}$${\ Displaystyle *}$${\displaystyle P\vdash Q}$${\ Displaystyle K * P \ modele Q}$${\displaystyle P}$ ${\displaystyle Q}$${\displaystyle Q}$

Postulaty ZWZ można przełożyć na zbiór postulatów dla tej relacji wnioskowania. Każdy z tych postulatów wiąże się z jakimś wcześniej rozważanym zbiorem postulatów dla niemonotonicznych relacji wnioskowania. I odwrotnie, warunki, które zostały uwzględnione dla niemonotonicznych relacji wnioskowania, można przełożyć na postulaty dla operatora rewizji. Wszystkie te postulaty wpisują się w postulaty ZWZ.

Rewizja podstawowa

W ramach AGM zbiór przekonań jest reprezentowany przez dedukcyjnie zamknięty zbiór formuł zdaniowych . Chociaż takie zbiory są nieskończone, zawsze można je skończenie reprezentować. Jednak praca z dedukcyjnie zamkniętymi zbiorami formuł prowadzi do domniemanego założenia, że ​​równoważne zbiory przekonań powinny być uważane za równe podczas rewizji. Nazywa się to zasadą nieistotności składni .

Ta zasada była i jest obecnie dyskutowana: chociaż i są dwoma równoważnymi zestawami, rewizja przez powinna przynieść różne wyniki. W pierwszym przypadku i są to dwa oddzielne przekonania; dlatego korekta przez nie powinna mieć żadnego wpływu na , a wynikiem korekty jest . W drugim przypadku brane jest jedno przekonanie. Fakt, że jest fałszem, przeczy temu przekonaniu, które należy zatem usunąć z zestawu przekonań. Wynik rewizji jest zatem w tym przypadku. ${\displaystyle \{a,b\}}$${\ Displaystyle \ {a \ klin b \}}$${\ Displaystyle \ neg a}$${\displaystyle a}$${\displaystyle b}$${\ Displaystyle \ neg a}$${\displaystyle b}$${\displaystyle \{\neg a,b\}}$${\displaystyle a\klin b}$${\displaystyle a}$${\displaystyle \{\neg a\}}$

Problem z wykorzystaniem dedukcyjnie zamkniętych baz wiedzy polega na tym, że nie dokonuje się rozróżnienia między fragmentami wiedzy, które są znane same z siebie, a fragmentami wiedzy, które są jedynie ich konsekwencjami. Rozróżnienie to jest natomiast dokonywane przez fundamentalne podejście do rewizji przekonań, które jest związane z fundamentalizmem w filozofii. Zgodnie z tym podejściem, wycofanie niepochodnej części wiedzy powinno prowadzić do wycofania wszystkich jej konsekwencji, które nie są w inny sposób wspierane (przez inne niepochodne części wiedzy). Podejście to można zrealizować, wykorzystując bazy wiedzy, które nie są dedukcyjnie zamknięte i zakładając, że wszystkie formuły w bazie wiedzy reprezentują samodzielne przekonania, to znaczy nie są przekonaniami pochodnymi. W celu odróżnienia fundamentalnego podejścia do rewizji przekonań od opartego na dedukcyjnie zamkniętych bazach wiedzy, to ostatnie nazywa się podejściem koherentnym . Nazwa ta została wybrana, ponieważ podejście koherentne ma na celu przywrócenie spójności (konsekwencji) pomiędzy wszystkimi przekonaniami, zarówno własnymi, jak i pochodnymi. To podejście jest związane z koherentyzmem w filozofii.

Fundamentalistyczne operatory rewizji pracujące na niededukcyjnie zamkniętych zbiorach przekonań zazwyczaj wybierają pewne podzbiory, które są zgodne z , łączą je w pewien sposób, a następnie łączą je z . Poniżej przedstawiono dwa niededukcyjnie zamknięte podstawowe operatory wersji. ${\ Displaystyle K}$${\displaystyle P}$${\displaystyle P}$

WIDTIO

(Kiedy masz wątpliwości, wyrzuć to) maksymalne podzbiory zgodne z są przecinane i dodawane do zbioru wynikowego; innymi słowy, wynik rewizji składa się ze wszystkich formuł, które są we wszystkich maksymalnych podzbiorach, które są zgodne z ;${\ Displaystyle K}$${\displaystyle P}$${\displaystyle P}$${\displaystyle P}$${\ Displaystyle K}$${\ Displaystyle K}$${\displaystyle P}$

Williams

rozwiązał otwarty problem, opracowując nową reprezentację dla skończonych podstaw, która umożliwiła przeprowadzenie operacji rewizji i kontrakcji AGM. Ta reprezentacja została przełożona na model obliczeniowy i opracowano algorytm do rewizji przekonań w dowolnym momencie.

Ginsberg-Fagin-Ullman-Vardi

maksymalne podzbiory, które są spójne i zawierają, są łączone przez alternatywę;${\ Displaystyle K \ filiżanka \ {P \}}$${\displaystyle P}$

Nebel

podobny do powyższego, ale można nadać priorytet wśród formuł, dzięki czemu formuły o wyższym priorytecie będą mniej prawdopodobne, że zostaną wycofane niż formuły o niższym priorytecie.

Inna realizacja fundamentalnego podejścia do rewizji przekonań opiera się na jednoznacznym deklarowaniu zależności między przekonaniami. W systemach utrzymywania prawdy można określić powiązania zależności między przekonaniami. W innych światach można wyraźnie zadeklarować, że w dany fakt wierzy się z powodu jednego lub kilku innych faktów; taka zależność nazywana jest uzasadnieniem . Przekonania niemające żadnego uzasadnienia pełnią rolę przekonań niepochodnych w podejściu niededukcyjnie zamkniętej bazy wiedzy.

Weryfikacja i aktualizacja na podstawie modelu

Szereg propozycji rewizji i aktualizacji w oparciu o zestaw modeli zaangażowanych formuł zostało opracowanych niezależnie od ram AGM. Zasadą tego podejścia jest to, że baza wiedzy jest równoważna zestawowi możliwych światów , to znaczy zestawowi scenariuszy, które są uważane za możliwe zgodnie z tą bazą wiedzy. Rewizja może być zatem dokonywana na zbiorach możliwych światów, a nie na odpowiadających im bazach wiedzy.

Operatory rewizji i aktualizacji oparte na modelach są zwykle identyfikowane przez nazwiska ich autorów: Winslett , Forbus, Satoh, Dalal, Hegner i Weber. Zgodnie z pierwszymi czterema propozycjami wynik rewizji/aktualizacji formuły o inną formułę charakteryzuje zestaw modeli, które są najbliższe modelom . Można zdefiniować różne pojęcia bliskości, co prowadzi do różnic między tymi propozycjami. ${\ Displaystyle K}$${\displaystyle P}$${\displaystyle P}$${\ Displaystyle K}$

Peppas i Williams

zapewnił formalny związek między rewizją a aktualizacją. Wprowadzili tożsamość Winsletta ws

Dalal

modele mające minimalną odległość Hamminga do modeli są wybierane jako modele wynikające ze zmiany;${\displaystyle P}$${\ Displaystyle K}$

Satoh

podobny do Dalal, ale odległość między dwoma modelami jest definiowana jako zbiór literałów, którym nadawane są różne wartości; podobieństwo między modelami definiuje się jako zbiór zawierający te różnice;

Winsletta

dla każdego modelu wybierane są najbliższe modele ; porównanie odbywa się za pomocą zestawu zawierającego różnicę;${\ Displaystyle K}$${\displaystyle P}$

Borgida

równa się wartości Winsletta, jeśli i są niespójne; w przeciwnym razie wynikiem rewizji jest ;${\ Displaystyle K}$${\displaystyle P}$${\ Displaystyle K \ klin P}$

Forbus

podobny do Winsletta, ale używana jest odległość Hamminga.

Operator rewizji zdefiniowany przez Hegnera sprawia, że nie wpływa na wartość zmiennych wymienionych w . Wynikiem tej operacji jest formuła, która jest zgodna z , a zatem może być z nią połączona. Operator rewizji Webera jest podobny, ale literały, które są usuwane, nie są wszystkimi literałami , ale tylko literałami, które są oceniane inaczej przez parę najbliższych modeli i zgodnie z miarą bliskości Satoh. ${\ Displaystyle K}$${\displaystyle P}$${\ Displaystyle K'}$${\displaystyle P}$${\ Displaystyle K}$${\displaystyle P}$${\ Displaystyle K}$${\displaystyle P}$

Wersja iterowana

Postulaty ZWZ są równoważne z porządkowaniem preferencji (nad modelami), które ma być powiązane z każdą bazą wiedzy . Nie dotyczą jednak uporządkowań odpowiadających dwóm nierównoważnym bazom wiedzy. W szczególności porządki związane z bazą wiedzy i jej poprawioną wersją mogą być zupełnie inne. Jest to problem przy wykonywaniu drugiej rewizji, ponieważ kolejność związana z jest konieczna do obliczenia . ${\ Displaystyle K}$${\ Displaystyle K}$${\ Displaystyle K * P}$${\ Displaystyle K * P}$${\ Displaystyle K * P * Q}$

Ustalenie relacji pomiędzy porządkiem związanym z i uznano jednak za nieodpowiednie rozwiązanie tego problemu. Rzeczywiście, relacja preferencji powinna zależeć od wcześniejszej historii zmian, a nie tylko od wynikowej bazy wiedzy. Mówiąc bardziej ogólnie, relacja preferencji daje więcej informacji o stanie umysłu podmiotu niż prosta baza wiedzy. Rzeczywiście, dwa stany umysłu mogą reprezentować tę samą część wiedzy, a jednocześnie różnić się sposobem włączenia nowej wiedzy. Na przykład dwie osoby mogą mieć ten sam pomysł na to, dokąd pojechać na wakacje, ale różnią się tym, jak zmienią ten pomysł, jeśli wygrają milion dolarów na loterii. Ponieważ podstawowym warunkiem uporządkowania preferencji jest to, że ich modele minimalne są dokładnie modelami powiązanej z nimi bazy wiedzy, bazę wiedzy można uznać za niejawnie reprezentowaną przez uporządkowanie preferencji (ale nie odwrotnie). ${\ Displaystyle K}$${\ Displaystyle K * P}$${\ Displaystyle K}$

Biorąc pod uwagę, że kolejność preferencji pozwala na wyprowadzenie powiązanej z nią bazy wiedzy, ale także umożliwia wykonanie pojedynczego kroku rewizji, badania nad rewizją iterowaną koncentrowały się na tym, jak kolejność preferencji powinna zostać zmieniona w odpowiedzi na rewizję. Podczas gdy wersja jednoetapowa dotyczy tego, jak baza wiedzy musi zostać zmieniona w nową bazę wiedzy , wersja iterowana dotyczy tego, jak należy zmienić kolejność preferencji (reprezentującą zarówno aktualną wiedzę, jak i liczbę sytuacji uważanych za fałszywe, uważanych za możliwe) w nową relację preferencji, gdy się nauczysz. Pojedynczy krok iterowanej rewizji tworzy nową kolejność, która pozwala na dalsze rewizje. ${\ Displaystyle K}$${\ Displaystyle K * P}$${\displaystyle P}$

Zwykle rozważane są dwa rodzaje porządkowania preferencji: numeryczne i nienumeryczne. W pierwszym przypadku poziom wiarygodności modelu jest reprezentowany przez nieujemną liczbę całkowitą; im niższa ranga, tym bardziej prawdopodobna jest sytuacja odpowiadająca modelowi. Nieliczbowe uporządkowania preferencji odpowiadają relacjom preferencji stosowanym w ramach AGM: możliwie całkowite uporządkowanie nad modelami. Nienumeryczna relacja preferencji została początkowo uznana za nieodpowiednią dla iterowanej wersji ze względu na niemożność cofnięcia wersji przez szereg innych wersji, co jest zamiast tego możliwe w przypadku numerycznym.

Darwiche i Pearl sformułowali następujące postulaty iterowanej rewizji.

1. jeśli to ;${\ Displaystyle \ alfa \ modele \ mu}$${\ Displaystyle (\ psi * \ mu) * \ alfa \ równoważnik \ psi * \ alfa}$
2. jeśli , to ;${\ Displaystyle \ alfa \ modele \ neg \ mu}$${\ Displaystyle (\ psi * \ mu) * \ alfa \ równoważnik \ psi * \ alfa}$
3. jeśli , to ;${\ Displaystyle \ psi * \ alfa \ modele \ mu}$${\ Displaystyle (\ psi * \ mu) * \ alfa \ modele \ mu}$
4. jeśli , to .${\ Displaystyle \ psi * \ alfa \ nie \ modele \ neg \ mu}$${\ Displaystyle (\ psi * \ mu) * \ alfa \ nie \ modele \ neg \ mu}$

Spohn, Boutilier, Williams , Lehmann i inni zaproponowali konkretne iterowane operatory wersji . Williams udostępnił również ogólny operator iterowanej wersji.

Spohn odrzucił rewizję

ta nienumeryczna propozycja została po raz pierwszy rozważona przez Spohna, który odrzucił ją, ponieważ rewizje mogą zmienić niektóre porządki w taki sposób, że pierwotna kolejność nie może zostać przywrócona z sekwencją innych rewizji; operator ten zmienia kolejność preferencji w świetle nowych informacji , czyniąc wszystkie modele preferowanymi w stosunku do wszystkich innych modeli; pierwotne uporządkowanie preferencji jest zachowywane przy porównywaniu dwóch modeli, które są obydwoma modelami lub obydwoma niemodelami ;${\displaystyle P}$${\displaystyle P}$${\displaystyle P}$${\displaystyle P}$

Naturalna rewizja

podczas rewizji uporządkowania preferencji według formuły wszystkie modele minimalne (zgodnie z uporządkowaniem preferencji) są preferowane przez wszystkie pozostałe; pierwotna kolejność modeli jest zachowana przy porównywaniu dwóch modeli, które nie są minimalnymi modelami ; operator ten minimalnie zmienia kolejność modeli, zachowując przy tym właściwość, że modele bazy wiedzy po przejrzeniu są modelami minimalnymi zgodnie z porządkiem preferencji;${\displaystyle P}$${\displaystyle P}$${\displaystyle P}$${\displaystyle P}$${\displaystyle P}$

Transmutacje

Williams dostarczył pierwszego uogólnienia iteracji rewizji przekonań za pomocą transmutacji. Ilustrowała transmutacje za pomocą dwóch form rewizji, warunkowania i dostosowania, które działają na numerycznych porządkach preferencji; rewizja wymaga nie tylko formuły, ale także numeru lub rankingu istniejącego przekonania, wskazującego stopień jego wiarygodności; podczas gdy kolejność preferencji jest nadal odwrócona (im niższy model, tym najbardziej prawdopodobny), stopień prawdopodobieństwa rewizji formuły jest bezpośredni (im wyższy stopień, tym formuła jest najbardziej wiarygodna);

Wersja rankingowa

model rankingowy, czyli przypisanie nieujemnych liczb całkowitych do modeli, musi być określony na początku; ta ranga jest podobna do kolejności preferencji, ale nie zmienia się w wyniku rewizji; tym, co zmienia sekwencja rewizji, jest aktualny zestaw modeli (reprezentujący aktualną bazę wiedzy) oraz liczba zwana rangą sekwencji; ponieważ liczba ta może tylko monotonicznie nie maleć, niektóre sekwencje poprawek prowadzą do sytuacji, w których każda kolejna wersja jest wykonywana jako pełna wersja.

Scalanie

Założeniem ukrytym w operatorze rewizji jest to, że nowa informacja powinna być zawsze uważana za bardziej wiarygodną niż stara baza wiedzy . Jest to sformalizowane przez drugi z postulatów ZWZ: w to zawsze wierzy się po zrewidowaniu za pomocą . Ogólnie rzecz biorąc, można rozważyć proces łączenia kilku informacji (a nie tylko dwóch), które mogą, ale nie muszą, mieć taką samą wiarygodność. Rewizja staje się szczególną instancją tego procesu, gdy mniej wiarygodna informacja jest łączona z bardziej niezawodną . ${\displaystyle P}$${\ Displaystyle K}$${\displaystyle P}$${\ Displaystyle K}$${\displaystyle P}$${\ Displaystyle K}$${\displaystyle P}$

Natomiast wejście do procesu aktualizacji jest para o wzorach a , wejście do łączenia jest multiset wzorów , itp Zastosowanie multisets to konieczne, dwa źródła do procesu łączących może być identyczne. ${\ Displaystyle K}$${\displaystyle P}$${\ Displaystyle K}$${\ Displaystyle T}$

Przy łączeniu wielu baz wiedzy o tym samym stopniu wiarygodności rozróżnia się arbitraż i większość. To rozróżnienie zależy od założenia, jakie poczyniono na temat informacji i sposobu ich zestawienia.

Arbitraż

wynik arbitrażu dwóch baz wiedzy i pociąga za sobą ; warunek ten formalizuje założenie zachowania jak największej ilości starych informacji, ponieważ jest to równoznaczne z narzuceniem, że każda formuła wynikająca z obu baz wiedzy jest również zawarta w wyniku ich arbitrażu; w światopoglądzie możliwym zakłada się, że świat „rzeczywisty” jest jednym ze światów uważanych za możliwy według przynajmniej jednej z dwóch baz wiedzy;${\ Displaystyle K}$${\ Displaystyle T}$${\displaystyle K\vee T}$

Większość

wynik połączenia bazy wiedzy z innymi bazami wiedzy można wymusić poprzez dodanie wystarczającej liczby innych baz wiedzy równoważnych ; warunek ten odpowiada rodzajowi głosowania większością: wystarczająco duża liczba baz wiedzy zawsze może przezwyciężyć „opinię” dowolnego innego ustalonego zestawu baz wiedzy.${\ Displaystyle K}$${\ Displaystyle K}$${\ Displaystyle K}$

Powyższe jest pierwotną definicją arbitrażu. Zgodnie z nowszą definicją operator arbitrażu jest operatorem scalania, który jest niewrażliwy na liczbę równoważnych baz wiedzy do scalenia. Ta definicja czyni arbitraż dokładnym przeciwieństwem większości.

Zaproponowano postulaty zarówno arbitrażu, jak i połączenia. Przykładem operatora arbitrażu spełniającego wszystkie postulaty jest klasyczna alternatywa. Przykładem operatora większościowego spełniającego wszystkie postulaty jest wybranie wszystkich modeli, które mają minimalną całkowitą odległość Hamminga do modeli baz wiedzy do scalenia.

Operator scalania może być wyrażony jako rodzina uporządkowania modeli, po jednym dla każdego możliwego zbioru baz wiedzy do scalenia: modele wyniku scalenia zbioru baz wiedzy są minimalnymi modelami uporządkowania powiązanymi z tym zbiorem. Tak zdefiniowany operator łączenia spełnia postulaty łączenia wtedy i tylko wtedy, gdy rodzina uporządkowań spełnia dany zestaw warunków. W przypadku starej definicji arbitrażu uporządkowania nie dotyczą modeli, ale par (lub ogólnie krotek) modeli.

Teoria wyboru społecznego

Wiele propozycji zmian obejmuje porządkowanie modeli reprezentujących względną wiarygodność możliwych alternatyw. Problem scalania polega na połączeniu zestawu uporządkowań w jeden, wyrażający połączoną wiarygodność alternatyw. Jest to podobne do tego, co robi się w teorii wyboru społecznego , która polega na badaniu, w jaki sposób można połączyć preferencje grupy podmiotów w racjonalny sposób. Rewizja przekonań i teoria wyboru społecznego są podobne pod tym względem, że łączą zestaw uporządkowań w jeden. Różnią się one tym, jak interpretowane są te porządki: preferencje w teorii wyboru społecznego; wiarygodność rewizji przekonań. Inną różnicą jest to, że alternatywy są wyraźnie wymienione w teorii wyboru społecznego, podczas gdy są to modele propozycjonalne w odniesieniu do danego alfabetu w rewizji przekonań.

Złożoność

Najbardziej badanym z punktu widzenia złożoności obliczeniowej problemem dotyczącym rewizji przekonań jest odpowiadanie na pytania w przypadku zdaniowym. Jest to problem ustalenia, czy formuła wynika z wyniku rewizji, czyli , gdzie , , i są formułami zdaniowymi. Mówiąc bardziej ogólnie, odpowiadanie na zapytania to problem z określeniem, czy formuła jest związana z wynikiem rewizji przekonań, która może być aktualizacją, scaleniem, rewizją, rewizją iterowaną itp. Innym problemem, któremu poświęcono trochę uwagi, jest sprawdzanie modelu , to znaczy sprawdzenie, czy model spełnia wynik rewizji przekonań. Pokrewnym pytaniem jest, czy taki wynik może być reprezentowany w wielomianu przestrzennym w jego argumentach. ${\ Displaystyle K * P \ modele Q}$${\ Displaystyle K}$${\displaystyle P}$${\displaystyle Q}$

Ponieważ dedukcyjnie zamknięta baza wiedzy jest nieskończona, badania złożoności operatorów rewizji przekonań pracujących na dedukcyjnie zamkniętych bazach wiedzy są prowadzone przy założeniu, że taka dedukcyjnie zamknięta baza wiedzy jest podana w postaci równoważnej skończonej bazy wiedzy.

Rozróżnia się operatory rewizji przekonań i schematy rewizji przekonań. Podczas gdy te pierwsze są prostymi operatorami matematycznymi odwzorowującymi parę formuł na inną formułę, te drugie zależą od dalszych informacji, takich jak relacja preferencji. Na przykład wersja Dalal jest operatorem, ponieważ po podaniu dwóch formuł i do obliczenia nie są potrzebne żadne inne informacje . Z drugiej strony, rewizja oparta na relacji preferencji jest schematem rewizji, ponieważ i nie pozwala na określenie wyniku rewizji, jeśli nie podano rodziny uporządkowań preferencji między modelami. Złożoność schematów rewizji jest określona przy założeniu, że dodatkowe informacje potrzebne do obliczenia rewizji są podane w jakiejś zwięzłej formie. Na przykład relację preferencji można przedstawić za pomocą sekwencji formuł, których modele są coraz bardziej preferowane. Jawne przechowywanie relacji jako zbioru par modeli nie jest zwartą reprezentacją preferencji, ponieważ wymagana przestrzeń jest wykładnicza w liczbie liter zdaniowych. ${\ Displaystyle K}$${\displaystyle P}$${\ Displaystyle K * P}$${\ Displaystyle K}$${\displaystyle P}$

Złożoność odpowiadania na zapytania i sprawdzania modelu w przypadku zdań jest na drugim poziomie hierarchii wielomianowej dla większości operatorów i schematów rewizji przekonań. Większość operatorów rewizji boryka się z problemem rozsadzenia reprezentacji: wynik reprezentowania dwóch formuł niekoniecznie jest reprezentowany w wielomianu przestrzennym w dwóch oryginalnych formułach. Innymi słowy, rewizja może wykładniczo zwiększyć rozmiar bazy wiedzy.

Stosowność

Osiągnięto nowe przełomowe wyniki, które pokazują, w jaki sposób można zastosować trafność w rewizji przekonań. Williams , Peppas, Foo i Chopra ogłosili wyniki w czasopiśmie Sztucznej Inteligencji .

Rewizja przekonań została również wykorzystana do zademonstrowania uznania wewnętrznego kapitału społecznego w zamkniętych sieciach.

Realizacje

Systemy wdrażające konkretnie rewizję przekonań to:

• SATEN – obiektowo zorientowany webowy silnik do rewizji i ekstrakcji ( Williams , Sims)
• ADS – rewizja przekonań w oparciu o SAT solver (Benferhat, Kaci, Le Berre, Williams )
• BRELS
• Nieśmiertelny

Dwa systemy zawierające funkcję zmiany przekonań to SNePS i Cyc .

Zobacz też

Uwagi

Bibliografia

Linki zewnętrzne

• Rewizja przekonań w PhilPapers
• Logic of Belief Revision w Indiana Philosophy Ontology Project
• Zalta, Edward N. (red.). „Logika rewizji przekonań” . Stanford Encyclopedia of Philosophy .
• Rozumowanie możliwe do obalenia: 4.3 Teoria rewizji przekonań w Stanford Encyclopedia of Philosophy