Trosrevisjon - Belief revision

Trosrevisjon er prosessen med å endre tro for å ta hensyn til en ny informasjon. Den logiske formaliseringen av trosrevisjonen er forsket i filosofi , i databaser og i kunstig intelligens for utforming av rasjonelle agenter .

Det som gjør trosrevisjon ikke trivielt er at flere forskjellige måter å utføre denne operasjonen kan være mulig. For eksempel, hvis den nåværende kunnskapen inkluderer de tre fakta " er sant", " er sant" og "hvis og er sant, så er sant", kan introduksjonen av den nye informasjonen " er usann" bare bevares konsistens ved å fjerne kl. minst en av de tre fakta. I dette tilfellet er det minst tre forskjellige måter å utføre revisjon på. Generelt kan det være flere forskjellige måter å endre kunnskap på. ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle C}$${\ displaystyle C}$

Revisjon og oppdatering

Det skilles vanligvis mellom to typer endringer:

Oppdater

den nye informasjonen handler om situasjonen for tiden, mens den gamle troen refererer til fortiden; oppdatering er operasjonen for å endre den gamle troen for å ta hensyn til endringen;

revisjon

både den gamle troen og den nye informasjonen refererer til den samme situasjonen; en inkonsekvens mellom ny og gammel informasjon forklares med muligheten for at gammel informasjon er mindre pålitelig enn den nye; revisjon er prosessen med å sette inn den nye informasjonen i settet med gammel tro uten å generere en inkonsekvens.

Hovedforutsetningen om trosrevisjon er at det er minimal endring: kunnskapen før og etter endringen skal være så lik som mulig. I tilfelle oppdatering formaliserer dette prinsippet antagelsen om treghet. I tilfelle revisjon håndhever dette prinsippet så mye informasjon som mulig for å bli bevart av endringen.

Eksempel

Følgende klassiske eksempel viser at operasjonene som skal utføres i de to innstillingene for oppdatering og revisjon, ikke er de samme. Eksemplet er basert på to forskjellige tolkninger av trossett og den nye informasjonen : ${\ displaystyle \ {a \ vee b \}}$${\ displaystyle \ neg a}$

Oppdater

i dette scenariet kretser to satellitter, enhet A og enhet B, rundt Mars; satellittene er programmert til å lande mens de overfører status til jorden; og Jorden har mottatt en overføring fra en av satellittene, og kommuniserer at den fortsatt er i bane. På grunn av forstyrrelser er det imidlertid ikke kjent hvilken satellitt som sendte signalet; deretter mottar Jorden kommunikasjonen om at Enhet A har landet. Dette scenariet kan modelleres på følgende måte: to proposisjonsvariabler og indikerer at henholdsvis enhet A og enhet B fortsatt er i bane; det første settet med tro er (den ene av de to satellittene er fortsatt i bane) og den nye informasjonen er (Enhet A har landet, og er derfor ikke i bane). Det eneste rasjonelle resultatet av oppdateringen er ; siden den første informasjonen om at en av de to satellittene ikke hadde landet ennå muligens kom fra enhet A, er ikke posisjonen til enhet B kjent.${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle \ {a \ vee b \}}$${\ displaystyle \ neg a}$${\ displaystyle \ neg a}$

revisjon

stykket "Six Characters in Search of an Author" vil bli spilt i et av de to lokale teatrene. Denne informasjonen kan betegnes med , hvor og indikerer at stykket vil bli fremført på henholdsvis første eller andre teater; en ytterligere informasjon om at "Jesus Christ Superstar" vil bli fremført på det første teatret indikerer at holder. I dette tilfellet er den åpenbare konklusjonen at "Six Characters in Search of an Author" vil bli fremført på det andre, men ikke det første teatret, som er representert i logikk av .${\ displaystyle \ {a \ vee b \}}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle \ neg a}$${\ displaystyle \ neg a \ wedge b}$

Dette eksemplet viser at å revidere troen med den nye informasjonen gir to forskjellige resultater, og avhengig av om innstillingen er den for oppdatering eller revisjon. ${\ displaystyle a \ vee b}$${\ displaystyle \ neg a}$${\ displaystyle \ neg a}$${\ displaystyle \ neg a \ wedge b}$

Sammentrekning, utvidelse, revisjon, konsolidering og sammenslåing

I omgivelsene der all tro refererer til den samme situasjonen, skilles det mellom forskjellige operasjoner som kan utføres:

kontraksjon

fjerning av en tro;

ekspansjon

tillegg av en tro uten å sjekke konsistens;

revisjon

tilsetning av en tro samtidig som konsistensen opprettholdes;

utdrag

trekke ut et konsistent sett med tro og / eller epistemisk ordning med skikkelig forankring;

konsolidering

gjenopprette konsistensen av et sett med tro;

sammenslåing

sammensmelting av to eller flere sett med tro, samtidig som konsistensen opprettholdes.

Revisjon og sammenslåing skiller seg ut ved at den første operasjonen gjøres når den nye troen på å innlemme anses som mer pålitelig enn den gamle; derfor opprettholdes konsistens ved å fjerne noen av de gamle troene. Fusjon er en mer generell operasjon ved at prioriteten blant trossettene kan være eller ikke være den samme.

Revisjon kan utføres ved først å innlemme det nye faktum og deretter gjenopprette konsistens via konsolidering. Dette er faktisk en form for sammenslåing i stedet for revisjon, da den nye informasjonen ikke alltid blir behandlet som mer pålitelig enn den gamle kunnskapen.

Generalforsamlingen postulerer

Generalforsamlingens postulater (oppkalt etter navnene på deres talsmenn, Alchourrón, Gärdenfors og Makinson ) er egenskaper som en operatør som utfører revisjon, skal tilfredsstille for at den operatøren skal bli ansett som rasjonell. Den vurderte innstillingen er den for revisjon, det vil si forskjellige informasjonstykker som refererer til samme situasjon. Tre operasjoner vurderes: utvidelse (tilsetning av en tro uten konsistensjekk), revisjon (tillegg av en tro samtidig som konsistensen opprettholdes) og sammentrekning (fjerning av en tro).

De seks første postulatene kalles "de grunnleggende generalforsamlingspostulatene". I innstillingene som betraktes av Alchourrón, Gärdenfors og Makinson, er det nåværende settet med tro representert av et deduktivt lukket sett med logiske formler som kalles trossett, den nye informasjonen er en logisk formel , og revisjon utføres av en binær operatør som tar den nåværende troen og den nye informasjonen og produserer som et resultat et trossett som representerer resultatet av revisjonen. Den operatør betegnet ekspansjons: er den deductive lukking av . Generalforsamlingens postulater for revisjon er: ${\ displaystyle K}$${\ displaystyle P}$${\ displaystyle *}$${\ displaystyle +}$${\ displaystyle K + P}$${\ displaystyle K \ cup \ {P \}}$

1. Lukking: er et trossett (dvs. et deduktivt lukket sett med formler);${\ displaystyle K * P}$
2. Suksess: ${\ displaystyle P \ i K * P}$
3. Inkludering: ${\ displaystyle K * P \ subseteq K + P}$
4. Vacuity: ${\ displaystyle {\ text {If}} (\ neg P) \ ikke \ i K, {\ text {da}} K * P = K + P}$
5. ${\ displaystyle K * P}$er inkonsekvent bare hvis er inkonsekvent${\ displaystyle P}$
6. Ekstensjonalitet: (se logisk ekvivalens )${\ displaystyle {\ text {If}} P {\ text {og}} Q {\ text {er logisk ekvivalente, så}} K * P = K * Q}$
7. ${\ displaystyle K * (P \ wedge Q) \ subseteq (K * P) + Q}$
8. ${\ displaystyle {\ text {If}} (\ neg Q) \ ikke \ i K * P {\ text {da}} (K * P) + Q \ subseteq K * (P \ kil Q)}$

En revisjonsoperatør som tilfredsstiller alle de åtte postulatene, er den fullstendige møteversjonen, der den er lik hvis den er konsistent, og den deduktive avslutningen av ellers. Selv om denne revisjonsoperatøren oppfyller alle generalforsamlingspostulatene, har han blitt ansett for å være for konservativ, ved at ingen informasjon fra den gamle kunnskapsbasen opprettholdes hvis den reviderte formelen ikke er i samsvar med den. ${\ displaystyle K * P}$${\ displaystyle K + P}$${\ displaystyle P}$

Forhold som tilsvarer generalforsamlingen

Generalforsamlingspostulatene tilsvarer flere forskjellige betingelser for revisjonsoperatøren; spesielt er de ekvivalente med at revisjonsoperatøren kan defineres når det gjelder strukturer kjent som valgfunksjoner, epistemiske forankringer, sfæresystemer og preferanseforhold. Sistnevnte er refleksive , transitive og totale relasjoner over settet med modeller.

Hver revisjonsoperatør som tilfredsstiller generalforsamlingspostulatene, er knyttet til et sett med preferanseforhold , en for hvert mulig trossett , slik at modellene av er nøyaktig de minimale av alle modeller i henhold til . Revisjonsoperatøren og tilhørende bestillingsfamilie er relatert av det faktum at det er settet med formler hvis sett med modeller inneholder alle de minimale modellene i henhold til . Denne tilstanden tilsvarer settet med modeller for å være nøyaktig settet med de minimale modellene i henhold til bestillingen . ${\ 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}}$

En preferansebestilling representerer en rekkefølelse av usannsynlighet blant alle situasjoner, inkludert de som kan tenkes, men som foreløpig anses som falske. De minimale modellene i henhold til en slik bestilling er nøyaktig modellene til kunnskapsbasen, som er modellene som for tiden anses som mest sannsynlige. Alle andre modeller er større enn disse og anses faktisk som mindre sannsynlige. Generelt, indikerer at situasjonen representert av modellen antas å være mer sannsynlig enn situasjonen representert av . Som et resultat bør revisjon av en formel som har og som modeller bare velge å være en modell av den reviderte kunnskapsbasen, da denne modellen representerer det mest sannsynlige scenariet blant de som støttes av . ${\ displaystyle \ leq _ {K}}$${\ displaystyle I <_ {K} J}$${\ displaystyle I}$${\ displaystyle J}$${\ displaystyle I}$${\ displaystyle J}$${\ displaystyle I}$${\ displaystyle P}$

Kontraksjon

Sammentrekning er operasjonen for å fjerne en tro fra en kunnskapsbase ; resultatet av denne operasjonen er betegnet med . Operatørene av revisjon og sammentrekninger er relatert av Levi og Harper identitetene: ${\ displaystyle P}$${\ displaystyle K}$${\ displaystyle KP}$

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

${\ displaystyle KP = K \ cap (K * \ neg P)}$

Åtte postulater er definert for sammentrekning. Hver gang en revisjonsoperatør tilfredsstiller de åtte postulatene for revisjon, tilfredsstiller den tilsvarende sammentrekningsoperatøren de åtte postulatene for sammentrekning og omvendt. Hvis en sammentrekningsoperatør tilfredsstiller minst de seks første postulatene for sammentrekning, fører oversettelse til en revisjonsoperatør og deretter tilbake til en sammentrekningsoperatør ved å bruke de to identitetene ovenfor til den opprinnelige sammentrekningsoperatøren. Det samme gjelder fra en revisjonsoperatør.

Et av postulatene for sammentrekning har lenge blitt diskutert: utvinningspostulatet:

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

I følge dette postulatet skal fjerning av en tro etterfulgt av gjeninnføring av samme tro på trossett føre til det opprinnelige trossettet. Det er noen eksempler som viser at slik oppførsel ikke alltid er rimelig: spesielt sammentrekning av en generell tilstand som fører til fjerning av mer spesifikke forhold som fra trossett; det er da uklart hvorfor gjeninnføring av også skulle føre til gjeninnføring av den mer spesifikke tilstanden . For eksempel, hvis George tidligere ble antatt å ha tysk statsborgerskap, ble han også antatt å være europeisk. Å trekke denne sistnevnte troen tilsvarer å slutte å tro at George er europeisk; derfor er at George har tysk statsborgerskap også trukket tilbake fra trossett. Hvis George senere blir oppdaget å ha østerriksk statsborgerskap, blir også det at han er europeisk gjeninnført. I følge gjenopprettingspostulatet skal imidlertid også troen på at han også har tysk statsborgerskap gjeninnføres. ${\ displaystyle P}$${\ displaystyle a \ vee b}$${\ displaystyle a}$${\ displaystyle a \ vee b}$${\ displaystyle a}$

Korrespondansen mellom revisjon og sammentrekning indusert av Levi og Harper-identitetene er slik at en sammentrekning som ikke tilfredsstiller utvinningspostulatet, blir oversatt til en revisjon som tilfredsstiller alle de åtte postulatene, og at en revisjon som tilfredsstiller alle de åtte postulatene, blir oversatt til en sammentrekning som tilfredsstiller alle de åtte postulatene. , inkludert utvinning. Som et resultat, hvis utvinning er ekskludert fra vurdering, blir et antall sammentrekningsoperatører oversatt til en enkelt revisjonsoperatør, som deretter kan oversettes til nøyaktig en sammentrekningsoperatør. Denne operatøren er den eneste av den første gruppen av sammentrekningsoperatører som tilfredsstiller utvinning; blant denne gruppen er det operatøren som bevarer så mye informasjon som mulig.

Ramsey-testen

Evalueringen av en kontrafaktisk betingelse kan gjøres, ifølge Ramsey-testen (oppkalt etter Frank P. Ramsey ), til det hypotetiske tillegget til settet med gjeldende tro, etterfulgt av en sjekk for sannheten om . Hvis det settes med troen som for øyeblikket holdes, blir Ramsey-testen formalisert av følgende korrespondanse: ${\ displaystyle a> b}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle K}$

${\ displaystyle a> b \ i K}$ hvis og bare hvis ${\ displaystyle b \ i K * a}$

Hvis det vurderte språket i formlene som representerer tro er proposisjonelt, gir Ramsey-testen en konsistent definisjon for kontrafaktiske betingelser når det gjelder en trosrevisjonsoperatør. Imidlertid, hvis språket til formler som representerer troen i seg selv inkluderer den kontrafaktiske betingede bindingen , fører Ramsey-testen til Gärdenfors trivialitetsresultat: det er ingen ikke-triviell revisjonsoperatør som tilfredsstiller både generalforsamlingspostulatene for revisjon og tilstanden til Ramsey-testen. Dette resultatet holder i antagelsen om at motfaktuelle formler som kan være til stede i trossett og revisjonsformler. Flere løsninger på dette problemet er blitt foreslått. ${\ displaystyle>}$${\ displaystyle a> b}$

Ikke-monoton inferensforhold

Gitt en fast kunnskapsbase og en revisjonsoperatør , kan man definere en ikke-monoton inferensrelasjon ved å bruke følgende definisjon: hvis og bare hvis . Med andre ord innebærer en formel en annen formel hvis tillegg av den første formelen til dagens kunnskapsbase fører til avledning av . Denne slutningsforholdet er ikke-monotont. ${\ displaystyle K}$${\ displaystyle *}$${\ displaystyle P \ vdash Q}$${\ displaystyle K * P \ modeller Q}$${\ displaystyle P}$ ${\ displaystyle Q}$${\ displaystyle Q}$

Generalforsamlingspostulatene kan oversettes til et sett med postulater for denne inferensrelasjonen. Hvert av disse postulatene medføres av noen tidligere ansett sett med postulater for ikke-monotone inferensrelasjoner. Omvendt, forhold som har blitt vurdert for ikke-monotone inferensrelasjoner kan oversettes til postulater for en revisjonsoperatør. Alle disse postulatene følger av generalforsamlingspostulatene.

Grunnleggende revisjon

I generalforsamlingsrammeverket er et trossett representert av et deduktivt lukket sett med proposisjonsformler . Selv om slike sett er uendelige, kan de alltid være endelig representable. Arbeid med deduktivt lukkede sett med formler fører imidlertid til den implisitte antagelsen om at tilsvarende trossett skal betraktes som like når de revideres. Dette kalles prinsippet om syntaksrelevans .

Dette prinsippet har vært og er for tiden debatteres: mens og er to likeverdige sett, revidere etter skal produsere forskjellige resultater. I det første tilfellet, og er to separate tro; Derfor bør revisjon av ikke ha noen effekt på , og resultatet av revisjonen er . I det andre tilfellet er det tatt en enkelt tro. Det faktum at det er falsk strider mot denne troen, som derfor bør fjernes fra trossettet. Resultatet av revisjon er derfor i dette tilfellet. ${\ displaystyle \ {a, b \}}$${\ displaystyle \ {a \ wedge b \}}$${\ displaystyle \ neg a}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle \ neg a}$${\ displaystyle b}$${\ displaystyle \ {\ neg a, b \}}$${\ displaystyle a \ wedge b}$${\ displaystyle a}$${\ displaystyle \ {\ neg a \}}$

Problemet med å bruke deduktivt lukkede kunnskapsbaser er at det ikke skilles mellom kunnskapsdeler som er kjent av seg selv og kunnskapsbiter som bare er konsekvenser av dem. Dette skillet gjøres i stedet av den grunnleggende tilnærmingen til trosrevisjon, som er relatert til grunnloven i filosofien. I følge denne tilnærmingen bør tilbaketrekking av en ikke-avledet kunnskap føre til å trekke tilbake alle dens konsekvenser som ellers ikke støttes (av andre ikke-avledede kunnskapsbiter). Denne tilnærmingen kan realiseres ved å bruke kunnskapsbaser som ikke er deduktivt lukket og forutsatt at alle formler i kunnskapsbasen representerer selvstendig tro, det vil si at de ikke er avledet tro. For å skille den grunnleggende tilnærmingen til trosrevisjon til den basert på deduktivt lukkede kunnskapsbaser, kalles sistnevnte den koherentistiske tilnærmingen. Dette navnet er valgt fordi den koherentistiske tilnærmingen tar sikte på å gjenopprette koherensen (konsistensen) blant alle trosoppfatninger, både selvstendige og avledede. Denne tilnærmingen er knyttet til sammenheng i filosofien.

Grunnleggende revisjonsoperatører som arbeider med ikke-deduktivt lukkede trossett, velger vanligvis noen undergrupper av det som er i samsvar med , kombinerte dem på en eller annen måte og sammenføyde dem med . Følgende er to ikke-deduktivt lukkede basisrevisjonsoperatører. ${\ displaystyle K}$${\ displaystyle P}$${\ displaystyle P}$

WIDTIO

(Når du er i tvil, kast det ut) krysses de maksimale delmengdene som samsvarer med , og blir lagt til det resulterende settet; med andre ord, resultatet av revisjon er sammensatt av og av alle formler som er i alle maksimale delmengder av det som er i samsvar med ;${\ displaystyle K}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle K}$${\ displaystyle K}$${\ displaystyle P}$

Williams

løste et åpent problem ved å utvikle en ny representasjon for begrensede baser som gjorde det mulig å utføre generalforsamlingsrevisjon og sammentrekningsoperasjoner. Denne representasjonen ble oversatt til en beregningsmodell, og en algoritme for trosrevisjon når som helst ble utviklet.

Ginsberg – Fagin – Ullman – Vardi

de maksimale delmengdene av de som er konsistente og inneholder , kombineres ved disjunksjon;${\ displaystyle K \ cup \ {P \}}$${\ displaystyle P}$

Nebel

ligner på ovenstående, men det kan gis en prioritet blant formler, slik at det er mindre sannsynlig at formler med høyere prioritet blir trukket tilbake enn formler med lavere prioritet.

En annen erkjennelse av den grunnleggende tilnærmingen til trosrevisjon er basert på eksplisitt å erklære avhengigheten blant tro. I sannhetsvedlikeholdssystemene kan avhengighetsforbindelser mellom troenes spesifiseres. I andre verdener kan man eksplisitt erklære at et gitt faktum antas på grunn av en eller flere andre fakta; en slik avhengighet kalles en begrunnelse . Tro som ikke har noen begrunnelse spiller rollen som ikke-avledet tro i den ikke-deduktivt lukkede kunnskapsbase-tilnærmingen.

Modellbasert revisjon og oppdatering

En rekke forslag for revisjon og oppdatering basert på settet med modeller av de involverte formlene ble utviklet uavhengig av generalforsamlingsrammeverket. Prinsippet bak denne tilnærmingen er at en kunnskapsbase tilsvarer et sett med mulige verdener , det vil si et sett med scenarier som anses som mulig i henhold til det kunnskapsgrunnlaget. Revisjon kan derfor utføres på sett med mulige verdener snarere enn på tilsvarende kunnskapsbaser.

Revisjons- og oppdateringsoperatørene basert på modeller identifiseres vanligvis med navnet på forfatterne: Winslett , Forbus, Satoh, Dalal, Hegner og Weber. I henhold til de fire første av dette forslaget, er resultatet av å revidere / oppdatere en formel med en annen formel preget av settet med modeller som er nærmest modellene av . Ulike forestillinger om nærhet kan defineres, noe som fører til forskjellen mellom disse forslagene. ${\ displaystyle K}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle K}$

Peppas og Williams

gitt det formelle forholdet mellom revisjon og oppdatering. De introduserte Winslett Identity i

Dalal

modellene for å ha en minimal Hamming-avstand til modeller av er valgt for å være modellene som følger av endringen;${\ displaystyle P}$${\ displaystyle K}$

Satoh

ligner på Dalal, men avstanden mellom to modeller er definert som settet med bokstaver som får forskjellige verdier av dem; likhet mellom modeller er definert som satt inneslutning av disse forskjellene;

Winslett

for hver modell av er de nærmeste modellene valgt; sammenligning gjøres ved hjelp av sett inneslutning av forskjellen;${\ displaystyle K}$${\ displaystyle P}$

Borgida

lik Winsletts hvis og er inkonsekvente; ellers er resultatet av revisjonen ;${\ displaystyle K}$${\ displaystyle P}$${\ displaystyle K \ wedge P}$

Forbus

ligner på Winslett, men Hamming-avstanden brukes.

Revisjonsoperatøren definert av Hegner gjør ikke å påvirke verdien av variablene som er nevnt i . Det som resulterer fra denne operasjonen er en formel som er i samsvar med , og som derfor kan sammenføyes med den. Revisjonsoperatøren av Weber er lik, men bokstavene som fjernes fra er ikke alle bokstaver av , men bare bokstavene som blir vurdert forskjellig av et par nærmeste modeller av og i henhold til Satoh-mål for nærhet. ${\ displaystyle K}$${\ displaystyle P}$${\ displaystyle K '}$${\ displaystyle P}$${\ displaystyle K}$${\ displaystyle P}$${\ displaystyle K}$${\ displaystyle P}$

Iterert revisjon

Generalforsamlingspostulatene tilsvarer en preferansebestilling (en bestilling over modeller) som skal knyttes til enhver kunnskapsbase . Imidlertid forholder de ikke bestillingene som tilsvarer to ikke-likeverdige kunnskapsbaser. Spesielt kan bestillingene knyttet til en kunnskapsbase og dens reviderte versjon være helt forskjellige. Dette er et problem for å utføre en ny revisjon, ettersom bestillingen tilknyttet er nødvendig å beregne . ${\ displaystyle K}$${\ displaystyle K}$${\ displaystyle K * P}$${\ displaystyle K * P}$${\ displaystyle K * P * Q}$

Å etablere en sammenheng mellom bestillingen knyttet til og har imidlertid blitt anerkjent som ikke den rette løsningen på dette problemet. Faktisk bør preferanseforholdet avhenge av den tidligere revisjonshistorikken, snarere enn bare av den resulterende kunnskapsbasen. Mer generelt gir en preferanseforhold mer informasjon om sinnets tilstand til en agent enn en enkel kunnskapsbase. Faktisk kan to sinnstilstander representere den samme kunnskapen samtidig som de er forskjellige i måten et nytt stykke kunnskap vil bli innlemmet på. For eksempel kan to personer ha den samme ideen om hvor de skal dra på ferie, men de er forskjellige om hvordan de vil endre denne ideen hvis de vinner et lotteri på en million dollar. Siden den grunnleggende forutsetningen for preferansebestillingen er at deres minimale modeller er nøyaktig modellene til deres tilknyttede kunnskapsbase, kan en kunnskapsbase betraktes som implisitt representert av en preferansebestilling (men ikke omvendt). ${\ displaystyle K}$${\ displaystyle K * P}$${\ displaystyle K}$

Gitt at en preferansebestilling tillater å utlede den tilknyttede kunnskapsbasen, men også tillate å utføre et enkelt revisjonstrinn, har studier om iterert revisjon vært konsentrert om hvordan en preferansebestilling skal endres som svar på en revisjon. Mens en-trinns revisjon handler om hvordan en kunnskapsbase må endres til en ny kunnskapsbase , handler iterert revisjon om hvordan en preferansebestilling (som representerer både den nåværende kunnskapen og hvor mange situasjoner som antas å være falske, anses som mulig) inn i en ny preferanseforhold når læres. Ett enkelt trinn med iterert revisjon produserer en ny bestilling som gir mulighet for ytterligere revisjoner. ${\ displaystyle K}$${\ displaystyle K * P}$${\ displaystyle P}$

To typer preferansebestilling blir vanligvis vurdert: numerisk og ikke-numerisk. I det første tilfellet representerer nivået av sannsynligheten til en modell et ikke-negativt heltall; jo lavere rang, jo mer sannsynlig er situasjonen som tilsvarer modellen. Ikke-numeriske preferansebestillinger tilsvarer preferanseforholdene som brukes i generalforsamlingsrammeverket: en mulig totalbestilling over modeller. Den ikke-numeriske preferanseforholdet ble opprinnelig ansett som uegnet for iterert revisjon på grunn av umuligheten av å tilbakeføre en revisjon av en rekke andre revisjoner, noe som i stedet er mulig i det numeriske tilfellet.

Darwiche og Pearl formulerte følgende postulater for iterert revisjon.

1. hvis da ;${\ displaystyle \ alpha \ models \ mu}$${\ displaystyle (\ psi * \ mu) * \ alpha \ equiv \ psi * \ alpha}$
2. hvis , da ;${\ displaystyle \ alpha \ models \ neg \ mu}$${\ displaystyle (\ psi * \ mu) * \ alpha \ equiv \ psi * \ alpha}$
3. hvis , da ;${\ displaystyle \ psi * \ alpha \ models \ mu}$${\ displaystyle (\ psi * \ mu) * \ alpha \ models \ mu}$
4. hvis , da .${\ displaystyle \ psi * \ alpha \ not \ models \ neg \ mu}$${\ displaystyle (\ psi * \ mu) * \ alpha \ not \ models \ neg \ mu}$

Spesifikke itererte revisjonsoperatører er blitt foreslått av Spohn, Boutilier, Williams , Lehmann og andre. Williams ga også en generell iterert revisjonsoperatør.

Spohn avviste revisjon

Dette ikke-numeriske forslaget ble først vurdert av Spohn, som avviste det basert på det faktum at revisjoner kan endre noen bestillinger på en slik måte at den opprinnelige bestillingen ikke kan gjenopprettes med en rekke andre revisjoner; denne operatøren endrer en preferansebestilling med tanke på ny informasjon ved å gjøre alle modeller for å være foretrukket fremfor alle andre modeller; den opprinnelige preferansebestillingen opprettholdes når man sammenligner to modeller som begge er modeller av eller begge ikke-modeller av ;${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle P}$

Naturlig revisjon

mens du reviderer en preferansebestilling etter en formel , blir alle minimale modeller (i henhold til preferansebestillingen) av foretrukket av alle andre; den opprinnelige bestillingen av modeller er bevart når man sammenligner to modeller som ikke er minimale modeller av ; denne operatøren endrer rekkefølgen mellom modeller minimalt mens den bevarer eiendommen som modellene i kunnskapsbasen etter revisjon av er de minimale modellene i henhold til preferansebestillingen;${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle P}$

Transmutasjoner

Williams ga den første generaliseringen av trosrevisjon iterasjon ved hjelp av transmutasjoner. Hun illustrerte transmutasjoner ved hjelp av to former for revisjon, betingelse og justering, som fungerer på numeriske preferansebestillinger; revisjon krever ikke bare en formel, men også et tall eller rangering av en eksisterende tro som indikerer graden av sannsynlighet; mens preferansebestillingen fremdeles er invertert (jo lavere en modell, den mest sannsynlige er den) er graden av sannsynligheten til en revisjonsformel direkte (jo høyere grad, den mest antatte formelen er);

Rangert revisjon

en rangert modell, som er en tildeling av ikke-negative heltall til modeller, må spesifiseres i begynnelsen; denne rangeringen er lik en preferansebestilling, men endres ikke ved revisjon; det som endres av en revisjonssekvens er et gjeldende sett med modeller (som representerer den nåværende kunnskapsbasen) og et tall som kalles rangeringen av sekvensen; siden dette tallet bare kan reduseres monotont, fører noen revisjonssekvenser til situasjoner der hver ytterligere revisjon utføres som en fullstendig møte-revisjon.

Sammenslåing

Antagelsen implisitt i revisjonsoperatøren er at den nye informasjonen alltid skal betraktes som mer pålitelig enn den gamle kunnskapsbasen . Dette formaliseres av den andre av generalforsamlingspostulatene: blir alltid trodd etter revisjon med . Mer generelt kan man vurdere prosessen med å slå sammen flere informasjonstyper (i stedet for bare to) som kanskje eller ikke har samme pålitelighet. Revisjon blir den spesielle forekomsten av denne prosessen når en mindre pålitelig informasjon blir slått sammen med en mer pålitelig . ${\ displaystyle P}$${\ displaystyle K}$${\ displaystyle P}$${\ displaystyle K}$${\ displaystyle P}$${\ displaystyle K}$${\ displaystyle P}$

Mens inngangen til revisjonsarbeidet er et par av formler og er inngangen til sammenslåing er en multiset av formler , etc. Bruken av multisets er nødvendig som to kilder for fusjonsprosessen kan være identiske. ${\ displaystyle K}$${\ displaystyle P}$${\ displaystyle K}$${\ displaystyle T}$

Ved sammenslåing av en rekke kunnskapsbaser med samme grad av sannsynlighet skilles det mellom voldgift og flertall. Dette skillet avhenger av antagelsen om informasjonen og hvordan den må settes sammen.

Megling

resultatet av voldgift mellom to kunnskapsbaser og innebærer ; denne tilstanden formaliserer antagelsen om å opprettholde så mye som den gamle informasjonen som mulig, da det tilsvarer å innføre at hver formel som begge kunnskapsbaser innebærer også er medført av resultatet av deres voldgift; i et mulig verdensbilde antas den "virkelige" verdenen en av de verdenene som anses som mulig i henhold til minst en av de to kunnskapsgrunnlagene;${\ displaystyle K}$${\ displaystyle T}$${\ displaystyle K \ vee T}$

Flertall

resultatet av å slå sammen en kunnskapsbase med andre kunnskapsbaser kan bli tvunget til å medføre ved å legge til et tilstrekkelig antall andre kunnskapsbaser som tilsvarer ; denne tilstanden tilsvarer en slags stemmegivning ved flertall: et tilstrekkelig stort antall kunnskapsbaser kan alltid overvinne "mening" fra ethvert annet fast sett med kunnskapsbaser.${\ displaystyle K}$${\ displaystyle K}$${\ displaystyle K}$

Ovennevnte er den opprinnelige definisjonen av voldgift. I følge en nyere definisjon er en voldgiftsoperatør en sammenslående operatør som er ufølsom for antall likeverdige kunnskapsbaser som skal slås sammen. Denne definisjonen gjør voldgift til det stikk motsatte av flertallet.

Postulater for både voldgift og sammenslåing er foreslått. Et eksempel på en voldgiftsoperatør som tilfredsstiller alle postulater er det klassiske skillet. Et eksempel på at en majoritetsoperatør tilfredsstiller alle postulater, er at valg av alle modeller som har en minimal total Hamming-avstand til modeller av kunnskapsbaser som skal slås sammen.

En sammenslåing av operatør kan uttrykkes som en familie av bestillinger over modeller, en for hvert mulige flersett av kunnskapsbaser som skal slås sammen: modellene av resultatet av sammenslåing av et flersett av kunnskapsbaser er de minimale modellene for bestillingen knyttet til multisettet. En sammenslående operatør definert på denne måten tilfredsstiller postulatene for sammenslåing hvis og bare hvis familien av bestillinger oppfyller et gitt sett med betingelser. For den gamle definisjonen av voldgift er ikke rekkefølgen på modeller, men på par (eller generelt tupler) av modeller.

Teori om sosialt valg

Mange revisjonsforslag innebærer bestillinger over modeller som representerer den relative sannsynligheten for de mulige alternativene. Problemet med å slå sammen beløp for å kombinere et sett med bestillinger til en enkelt som uttrykker den kombinerte sannsynligheten for alternativene. Dette ligner på hva som gjøres i sosialvalgsteorien , som er studiet av hvordan preferansene til en gruppe agenter kan kombineres på en rasjonell måte. Trosrevisjon og teori om samfunnsvalg er like ved at de kombinerer et sett med bestillinger i en. De skiller seg på hvordan disse ordningene tolkes: preferanser i sosialvalgsteori; plausibilitet i trosrevisjon. En annen forskjell er at alternativene er eksplisitt oppført i sosialvalgsteori, mens de er proposisjonsmodellene over et gitt alfabet i trosrevisjon.

Kompleksitet

Problemet med trosrevisjon som er mest studert ut fra beregningskompleksitetens synspunkt, er problemet med svar på spørsmål i proposisjonssaken. Dette er problemet med å etablere hvorvidt en formel som følger av resultatet av en revisjon, det vil si , hvor , , og er propositional formler. Mer generelt, svar på spørsmål er problemet med å fortelle om en formel er medført av resultatet av en trosrevisjon, som kan være oppdatering, sammenslåing, revisjon, iterert revisjon, etc. Et annet problem som har fått litt oppmerksomhet er det ved modellkontroll , det vil si å sjekke om en modell tilfredsstiller resultatet av en trosrevisjon. Et beslektet spørsmål er om et slikt resultat kan bli representert i rompolynomet i argumentene. ${\ displaystyle K * P \ modeller Q}$${\ displaystyle K}$${\ displaystyle P}$${\ displaystyle Q}$

Siden en deduktivt lukket kunnskapsbase er uendelig, gjøres kompleksitetsstudier av trosrevisjonsoperatører som arbeider med deduktivt lukkede kunnskapsbaser i den antagelsen at en slik deduktivt lukket kunnskapsbase er gitt i form av en tilsvarende begrenset kunnskapsbase.

Det skilles mellom operatører for trosrevisjoner og ordninger for trosrevisjon. Mens førstnevnte er enkle matematiske operatører som kartlegger et par formler til en annen formel, er sistnevnte avhengig av ytterligere informasjon, for eksempel en preferanseforhold. For eksempel, er det Dalal revisjon en operatør fordi, når to formler og er gitt, er ingen annen informasjon som er nødvendig for å beregne . På den annen side er revisjon basert på en preferanseforhold en revisjonsplan, fordi og ikke tillater å bestemme resultatet av revisjonen hvis familien av preferansebestillinger mellom modeller ikke er gitt. Kompleksiteten for revisjonsordninger bestemmes i forutsetningen om at den ekstra informasjonen som trengs for å beregne revisjon, er gitt i en eller annen kompakt form. For eksempel kan en preferanseforhold representeres av en sekvens av formler hvis modeller i økende grad foretrekkes. Å lagre forholdet eksplisitt som et sett med par modeller er i stedet ikke en kompakt representasjon av preferanser fordi den nødvendige plassen er eksponentiell i antall proposisjonsbokstaver. ${\ displaystyle K}$${\ displaystyle P}$${\ displaystyle K * P}$${\ displaystyle K}$${\ displaystyle P}$

Kompleksiteten i spørresvar og modellkontroll i proposisjonssaken er i det andre nivået av polynomhierarkiet for de fleste trosrevisjonsoperatører og skjemaer. De fleste revisjonsoperatører lider av problemet med representasjonssprengning: resultatet av å revidere to formler er ikke nødvendigvis representabel i rompolynom i de to originale formlene. Med andre ord kan revisjon eksponentielt øke størrelsen på kunnskapsbasen.

Relevans

Nye gjennombruddsresultater som viser hvordan relevans kan benyttes i trosrevisjon er oppnådd. Williams , Peppas, Foo og Chopra rapporterte resultatene i Artificial Intelligence journal.

Trosrevisjon har også blitt brukt for å demonstrere anerkjennelsen av egenkapital i lukkede nettverk.

Implementeringer

Systemer som spesielt implementerer trosrevisjon er:

• SATEN - en objektorientert nettbasert revisjons- og utvinningsmotor ( Williams , Sims)
• ADS - SAT-løsningsbasert trosrevisjon (Benferhat, Kaci, Le Berre, Williams )
• Merker
• Udødelig

To systemer, inkludert en trosrevisjonsfunksjon, er SNePS og Cyc .

Se også

Merknader

Referanser

Eksterne linker

• Troen revisjon på PhilPapers
• Logic of Belief Revision ved Indiana Philosophy Ontology Project
• Zalta, Edward N. (red.). "Logic of Belief Revision" . Stanford Encyclopedia of Philosophy .
• Defeasible Reasoning: 4.3 Tro Revision Theory at Stanford Encyclopedia of Philosophy