En stor och intressant familj av naturliga semantik för trosrevision definieras. Antag att man får ett avstånd d mellan två modeller. Man kan då definiera revideringen av en teori K med en formel α som den teori som definieras av uppsättningen av alla de modeller av α som är närmast, genom d, till uppsättningen modeller av K. Denna familj kännetecknas av en uppsättning rationalitet postulates som utökar AGM postulates. De nya postulaten beskriver egenskaperna hos itererade revideringar. 1 Introduktion Syftet med denna uppsats är att undersöka semantik och logiska egenskaper hos teorirevisioner baserade på ett underliggande begrepp om avstånd mellan enskilda modeller. I många situationer är det verkligen rimligt att anta att agenten har något naturligt sätt att utvärdera avståndet mellan två modeller av det logiska språket av intresse. Avståndet mellan modell m och modell m ′ är ett mått på hur långt m ′ verkar vara ur m-synpunkt. Detta avstånd kan mäta hur olika m ′ är från m under någon objektiv åtgärd: t.ex. antalet propositionella atomer på vilka m ′ skiljer sig från m om språket är propositionellt och finitt, men det kan också återspegla en subjektiv bedömning av agenten om sina egna förmågor såsom t.ex. sannolikheten för att, om m är fallet, agenten (felaktigt) tror att m ′ är fallet. Ett sådant avstånd mellan modeller kan användas för att definiera ett förfarande för teorirevision: både en teori T och en formel α definierar en uppsättning * Detta arbete stöddes delvis av Jean- och Helene Alfassa-fonden för forskning inom artificiell intelligens och av bidrag 136/94-1 från Israels vetenskapsstiftelse om "Nya perspektiv på ickemonotonisk resonans". 1 av modellerna M(T ) respektive M(α), och resultatet av revideringen av T av α, T * α, är teorin om uppsättningen av de modeller av M(α) som är närmast M(T ). Syftet med detta dokument är inte att föreslå specifika användbara begrepp om avstånd. Den antar en abstrakt uppfattning om ett avstånd ges och studerar egenskaperna hos de revideringar som definieras av detta avstånd. De avstånd som kommer att beaktas i denna tidning uppfyller inte alltid de egenskaper som allmänt accepteras för avstånd, de är verkligen pseudo-distanser. Det finns ingen uppenbar anledning till att i synnerhet vårt avstånd bör tillfredsställa den triangulära ojämlikheten eller till och med vara symmetriskt. Det kan vara så att, från perspektivet av m, m ′ ser mycket långt bort, men, från perspektivet av m ′, m ser i närheten. I termer av ett av våra exempel ovan: Om m är fallet, vår agent kan ge en mycket låg sannolikhet för m ′ vara fallet, men om m ′ är fallet, vår agent kan mycket väl tveka om m eller m ′ är fallet: anta, till exempel, att m och m ′ skiljer sig från värdet av ett atomförslag p som testas av vår agent. Testet för p kan mycket väl vara mycket tillförlitlig om p är fallet men ganska opålitlig om p är inte fallet. I [AGM85] introducerade Alcourrón, Gärdenfors och Makinson studiet av teorirevidering. Deras redovisning av revidering är indirekt: de beskriver sammandragningar i termer av maximal icke-implierande underteorier och de fortsätter att karakterisera revideringar, vilket minskar revideringen till sammandragning via Levi identitet. I [Gro88] gav Grove en direkt, semantisk, karakterisering av revideringen. Resultatet av att revidera en teori K genom ett proposition α bestäms av modellerna av α som individuellt, närmast uppsättningen, tas kollektivt, av alla modeller av K. På så sätt använder en relation mellan enskilda modeller och uppsättningar av modeller. Det är naturligt att försöka analysera sådan närhet i termer av en avståndsfunktion mellan modeller. Ett första försök gjordes av Becher i [Bec95], i syfte att jämföra revidering och uppdatering i en enhetlig miljö. Becher arbetade inte nödvändigtvis med symmetriska avstånd och visade att stämman postulerar hålla i distansbaserad revidering, men gav inget representationsresultat. Oberoende av detta presenterade författarna i [SLM96] en preliminär version av resultaten i detta dokument. Där behandlades endast det ändliga fallet med symmetriska avstånd. Vi behandlar här det oändliga fallet med symmetriska avstånd och det ändliga fallet med icke-symmetriska avstånd. Vi tillhandahåller också bevis och motexempel här. Vi presenterar först våra resultat på en abstrakt nivå, som handlar om abstrakta uppsättningar och sedan specialiserar våra resultat till fallet med uppsättningar av modeller. I det senaste arbetet (personlig kommunikation) gav Areces och Becher en representationseffekt för det godtyckliga, d.v.s. obegränsat och inte nödvändigtvis symmetriskt fall. Deras villkor skiljer sig från våra, baserat på fullständiga konsekventa teorier, d.v.s. Enstaka modeller, och delvis i en "existerande" stil, medan våra förutsättningar är "universella" och mer i Årsstämman stil. Vi vet inte om det finns en enkel direkt, dvs. Att inte gå via semantiken, bevis på likvärdigheten av Areces/Becher och våra villkor. Deras tillvägagångssätt är alltså en alternativ väg, vars förhållande till våra resultat är föremål för ytterligare forskning. Det oändliga fallet för icke-symmetriska avstånd med 2 villkor i vår stil är fortfarande öppet. Efter en kort motivering i avsnitt 1.1 presenterar och diskuterar vi årsstämmans ramverk för revidering i avsnitt 1.2 och ändrar det något. I avsnitt 1.3 introduceras pseudo-distanser, som är avstånd försvagade till de egenskaper som är väsentliga i vårt sammanhang. I synnerhet är pseudo-distanser inte nödvändigtvis symmetriska. Vi formaliserar revideringen baserat på ett (pseudo-) avstånd, och vi visar att de vanliga Årsstämmorna innehar sådana avståndsbaserade revideringar, åtminstone i det finita fallet. En ytterligare egendom (definibilitet bevarande) garanterar dem att hålla i det oändliga fallet också. Här diskuterar vi också vissa egenskaper hos distansbaserad revidering utöver årsstämmans postulat. Våra huvudsakliga resultat är algebraiska i naturen, och arbetar för godtyckliga uppsättningar, inte bara för uppsättningar av modeller. Översättningen till logik är då okomplicerad. I avsnitt 2 presenteras de algebraiska representationsresultaten, som beskriver de villkor som garanterar att en binär setoperatör kan representeras av ett pseudo-distans I avsnitt 2.2 behandlar vi fallet med symmetriska pseudo-distanser, resultatet gäller för uppsättningar av godtycklig kardinalitet. Observera att detta oändliga fall kräver en gräns villkor: För nonempty uppsättningar A, B finns det några b B med närmaste avstånd (bland elementen i B) till A. I avsnitt 2.3 behandlar vi inte nödvändigtvis det symmetriska fallet, men vårt resultat gäller endast den finita situationen. I avsnitt 3 översätts slutligen resultaten av avsnitt 2 till logik. Vi beskriver de villkor som garanterar att en revisionsoperatör * kan representeras av en pseudo-distans d mellan modeller, d.v.s. T * är uppsättningen av modeller av teorin T, och T h (X) uppsättningen av formler som gäller i uppsättningen av modeller X. Jämfört med algebraiska karakterisering, de logiska representationsresultaten är för möjligen oändliga språk i symmetriska fallet (med vissa förbehåll om definibilitet bevarande) och för finita i det inte nödvändigtvis symmetriska fallet. Intelligenta agenter måste samla in information om världen, utarbeta teorier om den och revidera dessa teorier med tanke på ny information som ibland motsäger de uppfattningar som tidigare funnits. Trosrevision är därför ett centralt ämne i Kunskapsrepresentationen. Det har studerats i olika former: numeriska eller symboliska, procedurmässiga eller deklarativa, logiska eller probabilistiska. Årsstämmans ramverk Ett av de mest framgångsrika ramverken inom vilka trosrevision har studerats har föreslagits av Alchourrón, Gärdenfors och Makinson, och är känt som Årsstämmans ramverk. Det handlar om åtgärder för revidering som reviderar en teori (uppsättningen av tidigare uppfattningar) med en formel (den nya informationen). I förslaget föreslås en uppsättning rationaliteter som innebär att alla rimliga revideringar bör vara tillfredsställande. Ett stort antal forskare inom AI har lockats av och utvecklat detta tillvägagångssätt ytterligare: både i det abstrakta och genom att utforma översynsförfaranden som uppfyller Årsstämmans rationalitet postulates. Två kommentarer bör göras omedelbart. För det första presenteras i ramen för årsstämman rationalitet postulates for revision. Den väljer inte någon särskild revidering bland de många möjliga revideringar som tillfredsställer dessa postulat. FH96] till den effekten att denna identifiering av epistemiska stater till tro uppsättningar är inte välkomna i många AI-tillämpningar. När itererade revideringar övervägs, är det rimligt att anta att agentens epistemiska tillstånd inkluderar information relaterad till dess historia av revideringar och att all denna historia, inte bara agentens nuvarande uppfattning, kan påverka framtida revideringar. Detta dokument behåller årsstämmans åtagande att identifiera epistemiska stater med trossatser, men föreslår ytterligare rationalitet postulates. Dessa ytterligare postulat kännetecknar exakt de revideringar som definieras av pseudo-distanser. De begränsar revideringar i det sätt på vilket de behandlar sina vänsterargument, den teori som ska revideras (i detta avseende är stämmans postulater extremt, förmodligen överdrivet liberala) och de innebär i hög grad icke-triviala egenskaper för itererade revideringar. I detta dokument behandlas därför upprepade revideringar inom ramen för den ursprungliga årsstämmans åtagande att identifiera epistemiska stater och trossatser. Resultat relaterade till idéerna i detta dokument kan hittas i [BGHPSW97]. Liknande idéer i ett sammanhang där epistemiska tillstånd inte är trosuppsättningar kan hittas i [BLS99]. Detta arbete ger en semantik för teorirevisionà la Årsstämma, eller för en underfamilj av sådana revideringar. Det är det första försöket att semantiskt beskriva hela revisionen * på ett enhetligt sätt. Tidigare försök [Gro88], [GM88] beskriver revideringen av varje teori K genom en annan struktur utan lim som relaterar de olika strukturerna: sfärsystem eller epistemiska entrechment relationer, som motsvarar olika K: s. I detta dokument erhålls revideringarna av de olika K:na från samma pseudo-distans. En snäv passform (sammanhållning) mellan revideringarna av olika K:s verkar avgörande för en användbar behandling av itererade revideringar: det måste vara samma revideringsoperation som utför de successiva revideringarna för att eventuella intressanta egenskaper ska framträda. Våra revideringar definieras därför av ett polynom (i antalet modeller som beaktas) antal pseudo-distanser i stället för ett exponentiellt antal sfärsystem eller epistemiska förenklingsrelationer (ett för varje teori K). Semantik baserad på ett mer eller mindre abstrakt begrepp om avstånd är inte en ny idé i icke-klassiska logiker. Det mest kända exemplet är kanske Stalnaker/Lewis distanssemantik för kontrafaktiska villkor, se t.ex. [Lew73].............................................................. Årsstämmans ramverk, definierat i [ÅRG85], studier revisionsverksamhet, betecknad *, som fungerar på två argument: en uppsättning K formler stängda under logiskt avdrag till vänster och en formel α till höger. Således K * α är resultatet av revidering av teori K med formel α, med hjälp av revisionsmetod *. Vår baslogik kommer att vara klassisk propositionslogik, även om våra huvudsakliga resultat är rent algebraiska i naturen, och därför också föra över till andra logiker. Genom missbruk av språket kallar vi ett språk ändligt vars uppsättning av propositionsvariabler är ändlig. En teori kommer att vara en godtycklig uppsättning formler, inte nödvändigtvis avdragsgillt slutna. Vi använder den sedvanliga notation Cn(T ) för uppsättningen av alla logiska konsekvenser av en teori T. Cn(T, α) kommer att stå för Cn(T) {α}. Kon(T ) kommer att stå för: T är (klassiskt) konsekvent, Con(T, T ′ ) abbreviates Con(T) ). .= kommer att vara klassisk giltighet, och  till = T  på T ′ kommer att förkorta det uppenbara:  till = T → på ′ för alla  ska T ′ och  till = T ′ →  på alla  och T. Med tanke på ett propositionsspråk L, M L kommer att vara uppsättningen av sina modeller. M(T ) kommer att vara modellerna för en teori T (likartat M(en) för en formel) och T h(X) den uppsättning formler som gäller i en uppsättning av modeller X. T  för T ′ := {... P kommer att vara kraftuttagsoperatören. De logiska bindväven och uppsättningen bindväv har alltid företräde framför revideringen och ange operatörer * och. Numrering av villkor: ( ska i) numrera villkor som är gemensamma för den symmetriska och inte nödvändigtvis symmetriska uppsättningen operatörer  på, ( till Si) och ( till Ai) villkor för respektive den symmetriska och inte nödvändigtvis symmetriska uppsättningen operatör. ( * i), ( * Si), ( * Ai) kommer att göra detsamma för teorin revision operatör *. Den ursprungliga rationaliteten postulates är följande, för K en avdragsgillt sluten uppsättning formler, och α, β formler. Vi föredrar att ändra den ursprungliga bolagsstämmans formalism på två konton något. För det första verkar det som om den skillnad som krävs i typerna av de två argumenten för en översyn: det vänstra argumentet är en teori och det rätta argumentet är en formel som inte är grundad. Bristen på symmetri är tvåfaldig: det vänstra argumentet, som är en teori, kan i sig självt vara oändligt och inte representeras av en enda formel medan det högra argumentet alltid är en enda formel, men även det vänstra argumentet är inte en godtycklig uppsättning formler, utan avslutas under logiska konsekvenser, medan det högra argumentet inte dras ifrån, vilket kräver Postulate K * 6 att hävda invariant under logisk likvärdighet. Det finns ingen allvarlig orsak till denna brist på symmetri. Vi kommer därför att föredra en formalism som är symmetrisk i båda argumenten. Våra resultat för symmetriska pseudo-distanser gäller för oändliga uppsättningar, våra resultat för inte nödvändigtvis symmetriska pseudo-distanser har bevisats endast för ändliga uppsättningar - där uppsättningar ska förstås som uppsättningar av modeller. De senare bevisas således endast för språk som är baserade på en begränsad uppsättning propositionsvariabler. Vi väljer därför en formalism där båda revisionsoperatörens argument är teorier, som i det inte nödvändigtvis symmetriska fallet kommer att antas vara likvärdiga med enskilda formler. Vi tittar alltså på T * T ′, den teori som är resultatet av att revidera teori T av den nya information som representeras av teori T ′. För det andra kan var och en av teorierna K och formeln α vara inkonsekventa vid stämman. Det skadar inte att göra detta, men de intressanta revideringarna är alltid revideringar av konsekventa teorier genom konsekventa formler och beaktandet av inkonsekventa argument gör behandlingen onödigt klumpig. Därför ska vi bara revidera konsekventa teorier genom konsekventa teorier, och anta att båda argumenten är konsekventa. Stämman kan nu skrivas om på följande sätt. Vi skriver om K * 3 och K * 4 i ett enda postulat, ( * 3) och på liknande sätt för K * 7 och K * 8, i ( * 4). K * 1 och K * 5 sammanfattas i vår allmänna förutsättning och ( * 1). Kom ihåg att T, T ′, T ′′, S, S ′ är nu godtyckliga konsekventa teorier. Revidering baserad på pseudo-distans Vi kommer att basera vår semantik för revidering på pseudo-distanser mellan modeller. Pseudoavstånd skiljer sig från avstånd i det att deras värden inte nödvändigtvis är verkliga, inget tillägg av värden behöver definieras, och symmetri behöver inte hålla. Allt vi behöver är en helt ordnad uppsättning värderingar. Om det finns ett minimalt element 0 så att d(x, y) = 0 iff x = y, säger vi att d respekterar identiteten. Pseudo-avstånd som inte respekterar identiteten har intresse av situationer där det krävs ansträngning för att stanna kvar på samma sätt. Vi minns först: En binär relation ≤ på X är en förorder, iff ≤ är reflexiv och transitiv. Om ≤ är totalt, dvs. Iff  på x, y x x ≤ y eller y ≤ x, då ≤ är en total förbeställning. En binär relation < på X är en total order, iff < är transitiv, oflexiv, dvs. x < x för alla x X, och för alla x, y X x < y eller y < x eller x = y. Anm. 1.1: Om ≤ är en total preorder på X, så är det motsvarande ekvivalensförhållandet definierat av x  ska y iff x ≤ y och y ≤ x, [x] x-ekvivalensklassen, och vi definierar [x] < [y] iff x ≤ y, men inte y ≤ x, är < en total order på {[x]: x X}. Definition 1.4 d : U × U → Z kallas pseudo-distans på U iff (d1) innehar: (d1) Z är helt beställd av en relation <. Om Z dessutom har ett < - minsta element 0, och (d2) håller, säger vi att d respekterar identitet: 7 Observera att vi kan tvinga triangeln ojämlikhet att hålla trivialt (om vi kan välja värdena i de verkliga talen): Det räcker att välja värdena i uppsättningen {0}  på [0.5, 1], dvs.. i intervallet från 0,5 till 1, eller som 0. Kom ihåg att våra huvudsakliga representationsresultat är rent algebraiska, och gäller godtyckliga uppsättningar U, som inte nödvändigtvis behöver vara uppsättningar av modeller. Intuitivt dock U ska förstås som en uppsättning modeller för vissa språk L, och avståndet från m till n, d(m, n) representerar "kostnaden" eller "svårigheten" av en förändring från situationen som representeras av m till den situation som representeras av n. M. Dalal [Dal88] har betraktat ett sådant avstånd: avståndet mellan två propositionsvärldar är det antal atomiska förslag på vilka de skiljer sig, dvs. hamming avståndet mellan världar som betraktas som binära kdimensionella vektorer, där k är antalet atomiska propositionsvariabler. A. Borgida [Bor85] anses vara ett liknande men annorlunda avstånd, baserat på inställd inkludering. Hans avstånd är inte helt beställda och därför passar den ram som presenteras här inte hans arbete. Ett annat exempel på ett sådant avstånd är det triviala avståndet: d(m, n) är 0 om m = n och 1 annars. Båda dessa avstånd tillfredsställer den triangulära ojämlikheten. I tillämpningar som handlar om resonemang om handlingar och förändring, kanske man vill överväga avståndet mellan två modeller för att representera hur svårt, eller oväntat, övergången är. I ett sådant fall kan ett naturligt pseudoavstånd mycket väl inte vara symmetriskt. Vi ger den formella definitionen av elementen i B d-clost till A: Definition 1.5 kan presenteras i ett något annorlunda ljus. vara uppsättningen av alla minimala element (under <) i uppsättningen A × B. Därefter är A  ska d B inget annat än den rätta projektionen (på B) av A × B. Således är A  på d B den delmängd av B som består av alla b B som är närmast A. Observera att om A eller B är oändligt, kan A  till d B vara tom, även om A och B inte är tomma. Ett villkor som garanterar icke-tomma kommer att införas när det är nödvändigt. Syftet med avsnitt 2 i denna artikel är att karakterisera dessa operatörer  på följande sätt: P(U) × P(U) → P(U), för vilken det finns en pseudo-distans d, så att A  och B = A  och d B. Vi kallar sådan. Representabel: obesvarad frågan om arten av beroendet av revisionen T * T ′ på dess vänstra argument, T. Eftersom vi, liksom de flesta forskare inom artificiell intelligens, är mest intresserade av itererade revideringar, korrekt förståelse, och semantik, för detta beroende är avgörande. Syftet med detta dokument är att besvara frågan genom att föreslå lämpliga semantik. Vi karakteriserar semantiken helt och hållet genom en uppsättning postulater. Vi hävdar inte att de semantiker som föreslås är de mest allmänna, vi presenterar en familj av förnuftiga semantik, baserad på pseudo-distanser mellan modeller. Följande är den centrala definitionen, den beskriver hur en revidering * d är kopplad till en pseudo-distans d på uppsättningen modeller. ).............................................................................................. * kallas representativ if det finns en pseudo-distans d på uppsättningen modeller s.t. Huvudsyftet med detta arbete är att karakterisera de egenskaper, d.v.s. rationalitet postulates tillfredsställda genom revideringar som kan representeras av pseudo-distanser. Revidering baserad på pseudo-distanser och årsstämman postulerar Årsstämman postulerar innehav för revidering baserat på pseudo-distanser i det ändliga fallet Definition 1.8 En operation på uppsättningar av modeller av någon logik kallas definibilitet bevara iff M(T ) M(T ′ ) är återigen en uppsättning modeller av vissa teori S för alla teorier T, T ′. Abstractly, definibilitet bevarande starkt par bevis teori och semantik. För att uppnå samma typ av resultat utan definibilitetsbevarande skulle vi behöva tillåta en "frikoppling" av en "liten" uppsättning undantag. Detta illustreras t.ex. med resultatet i Samma bevis visar att stämman postulerar också innehar i det oändliga fallet, om verksamheten är definibilitet bevara, och om vi inför ett gränsvärde villkor för postulat ( * 1). ( * 0) är uppenbart, eftersom vi arbetar med modeller.
Oberoende av detta presenterade författarna, i REF, en preliminär version av de resultat som ges i detta dokument.
Distance Semantics for Belief Revision
{'venue': 'Journal of Symbolic Logic, Vol. 66 No.1 (March 2001) pp. 295-317', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}