Informační algebra - Information algebra

Termín "informační algebra"odkazuje na matematické techniky zpracování informací. Klasický teorie informace se vrací do Claude Shannon. Je to teorie přenosu informací, která se zaměřuje na komunikaci a ukládání. Dosud však nebylo bráno v úvahu, že informace pocházejí z různých zdrojů, a proto jsou obvykle kombinovány. V klasické teorii informací bylo navíc opomíjeno, že je třeba extrahovat ty části z části informací, které jsou relevantní pro konkrétní otázky.

Matematické formulace těchto operací vede k algebra informací, popisující základní režimy zpracování informací. Taková algebra zahrnuje několik formalismů počítačová věda, které se na první pohled zdají odlišné: relační databáze, více systémů formální logiky nebo numerické problémy lineární algebry. Umožňuje vývoj obecných postupů zpracování informací a tím i sjednocení základních metod informatiky, zejména distribuované zpracování informací.

Informace se týkají přesných otázek, pocházejí z různých zdrojů, musí být agregovány a mohou být zaměřeny na zajímavé otázky. Z těchto úvah vycházejí informační algebry (Kohlas 2003 ) jsou dva tříděné algebry ${displaystyle (Phi, D)}$ , kde ${displaystyle Phi}$ je poloskupina, představující kombinaci nebo agregaci informací, ${displaystyle D}$ je mříž z domén (související s otázkami) jehož částečná objednávka odráží zrnitost domény nebo otázky a a smíšený provoz představující zaměření nebo extrakci informací.

Informace a jejich operace

Přesněji řečeno v algebře dvou tříd ${displaystyle (Phi, D)}$ , jsou definovány následující operace

Kombinace: ${displaystyle otimes: Phi otimes Phi ightarrow Phi, ~ (phi, psi) mapsto phi otimes psi}$
Se zaměřením: ${displaystyle Rightarrow: Phi otimes Dightarrow Phi, ~ (phi, x) mapsto phi ^ {Rightarrow x}}$

Navíc v ${displaystyle D}$ jsou definovány obvyklé mřížkové operace (setkání a připojení).

Axiomy a definice

Axiomy dvousložkové algebry ${displaystyle (Phi, D)}$ , kromě axiomů mřížky ${displaystyle D}$ :

Poloskupina: ${displaystyle Phi}$ je komutativní poloskupina v kombinaci s neutrálním prvkem (představujícím prázdnou informaci).
Distributivita zaostřování nad kombinací: ${displaystyle (phi ^ {Rightarrow x} další psi) ^ {Rightarrow x} = phi ^ {Rightarrow x} další psi ^ {Rightarrow x}}$

Zaměřit informace na ${displaystyle x}$ v kombinaci s dalšími informacemi do domény ${displaystyle x}$ , lze také nejprve zaměřit druhou informaci ${displaystyle x}$ a poté kombinovat.

Transitivita zaostřování: ${displaystyle (phi ^ {Rightarrow x}) ^ {Rightarrow y} = phi ^ {Rightarrow xwedge y}}$

Zaměřit informace na ${displaystyle x}$ a ${displaystyle y}$ , lze to zaměřit ${displaystyle xwedge y}$ .

Idempotence: ${displaystyle phi otimes phi ^ {Rightarrow x} = phi}$

Informace kombinovaná s částí sebe sama nepřináší nic nového.

Podpěra, podpora: ${displaystyle forall phi in Phi, ~ exists xin D}$ takhle ${displaystyle phi = phi ^ {Rightarrow x}}$

Každá informace se týká alespoň jedné domény (otázka).

Dvouřadá algebra ${displaystyle (Phi, D)}$ splnění těchto axiomů se nazývá Informační algebra.

Pořadí informací

Částečné pořadí informací lze zavést definováním ${displaystyle phi leq psi}$ -li ${displaystyle phi otimes psi = psi}$ . Tohle znamená tamto ${displaystyle phi}$ je méně informativní než ${displaystyle psi}$ pokud nepřidá žádné nové informace ${displaystyle psi}$ . Poloskupina ${displaystyle Phi}$ je semilattice vzhledem k tomuto řádu, tj. ${displaystyle phi otimes psi = phi vee psi}$ . Relativní k jakékoli doméně (otázka) ${displaystyle xin D}$ částečnou objednávku lze zavést definováním ${displaystyle phi leq _ {x} psi}$ -li ${displaystyle phi ^ {Rightarrow x} leq psi ^ {Rightarrow x}}$ . Představuje pořadí informačního obsahu ${displaystyle phi}$ a ${displaystyle psi}$ vzhledem k doméně (otázka) ${displaystyle x}$ .

Informační algebra se štítky

Tyto páry ${displaystyle (phi, x)}$ , kde ${displaystyle phi in Phi}$ a ${displaystyle xin D}$ takhle ${displaystyle phi ^ {Rightarrow x} = phi}$ tvoří a označená Informační algebra. Přesněji řečeno v algebře dvou tříd ${displaystyle (Phi, D)}$ , jsou definovány následující operace

Značení: ${displaystyle d (phi, x) = x}$
Kombinace: ${displaystyle (phi, x) otimes (psi, y) = (phi otimes psi, xvee y) ~~~~}$
Projekce: ${displaystyle (phi, x) ^ {downarrow y} = (phi ^ {Rightarrow y}, y) {ext {for}} yleq x}$

Modely informačních algeber

Následuje neúplný seznam instancí informačních algeber:

Relační algebra: Redukce relační algebry s přirozeným spojením jako kombinací a obvyklou projekcí je označená informační algebra, viz Příklad.
Omezovací systémy: Omezení tvoří informační algebru (Jaffar a Maher 1994 ).
Semiring hodnotné algebry: C-Semirings indukují informační algebry (Bistarelli, Montanari & Rossi, 1997 );(Bistarelli a kol. 1999 );(Kohlas & Wilson 2006 ).
Logika: Mnoho logických systémů indukuje informační algebry (Wilson & Mengin 1999 ). Snižuje válcové algebry (Henkin, Monk & Tarski 1971 ) nebo polyadické algebry jsou informační algebry související s predikátová logika (Halmos 2000 ).
Modul algebry: (Bergstra, Heering & Klint 1990 );(de Lavalette 1992 ).
Lineární systémy: Systémy lineárních rovnic nebo lineárních nerovností indukují informační algebry (Kohlas 2003 ).

Vypracovaný příklad: relační algebra

Nechat ${displaystyle {mathcal {A}}}$ být sada symbolů, tzv atributy (nebo sloupecjména). Pro každého ${displaystyle alpha v {mathcal {A}}}$ nechat ${displaystyle U_ {alpha}}$ být neprázdná množina,sada všech možných hodnot atributu ${displaystyle alpha}$ . Například pokud ${displaystyle {mathcal {A}} = {{exttt {name}}, {exttt {age}}, {exttt {income}}}}$ , pak ${displaystyle U_ {exttt {name}}}$ mohla být sada řetězců, zatímco ${displaystyle U_ {exttt {age}}}$ a ${displaystyle U_ {exttt {příjem}}}$ jsou obě množina nezáporných celých čísel.

Nechat ${displaystyle xsubseteq {mathcal {A}}}$ . An ${displaystyle x}$ -tuple je funkce ${displaystyle f}$ aby ${displaystyle {hbox {dom}} (f) = x}$ a ${displaystyle f (alfa) v U_ {alpha}}$ pro každého ${displaystyle alfa v x}$ Vše v bezpečí ${displaystyle x}$ -tuples je označen ${displaystyle E_ {x}}$ . Pro ${displaystyle x}$ -tuple ${displaystyle f}$ a podmnožina ${displaystyle ysubseteq x}$ omezení ${displaystyle f [y]}$ je definován jako ${displaystyle y}$ -tuple ${displaystyle g}$ aby ${displaystyle g (alfa) = f (alfa)}$ pro všechny ${displaystyle alfa v y}$ .

A vztah ${displaystyle R}$ přes ${displaystyle x}$ je sada ${displaystyle x}$ -tuples, tj. podmnožina ${displaystyle E_ {x}}$ Sada atributů ${displaystyle x}$ se nazývá doména z ${displaystyle R}$ a označeno ${displaystyle d (R)}$ . Pro ${displaystyle ysubseteq d (R)}$ the projekce z ${displaystyle R}$ na ${displaystyle y}$ je definován takto:

{displaystyle pi _ {y} (R): = {f [y] mid fin R}.}

The připojit se vztahu ${displaystyle R}$ přes ${displaystyle x}$ a vztah ${displaystyle S}$ přes ${displaystyle y}$ je definován následovně:

{displaystyle R owtie S: = {fmid fquad (xcup y) {hbox {-tuple}}, quad f [x] v R,; f [y] v S}.}

Jako příklad, pojďme ${displaystyle R}$ a ${displaystyle S}$ být následující vztahy:

{displaystyle R = {egin {matrix} {exttt {name}} & {exttt {age}} {exttt {A}} & {exttt {34}} {exttt {B}} & {exttt {47}} end {matrix}} qquad S = {egin {matrix} {exttt {name}} & {exttt {income}} {exttt {A}} & {exttt {20'000}} {exttt {B}} & {exttt {32'000}} end {matrix}}}

Pak se připojte k ${displaystyle R}$ a ${displaystyle S}$ je:

{displaystyle R owtie S = {egin {matrix} {exttt {name}} & {exttt {age}} & {exttt {income}} {exttt {A}} & {exttt {34}} & {exttt {20 '000}} {exttt {B}} a {exttt {47}} a {exttt {32'000}} end {matrix}}}

Relační databáze s přirozeným spojením ${displaystyle owtie}$ jako kombinace a obvyklá projekce ${displaystyle pi}$ je informační algebra. Od té doby jsou operace dobře definované

${displaystyle d (R owtie S) = d (R) šálek d (S)}$
Li ${displaystyle xsubseteq d (R)}$ , pak ${displaystyle d (pi _ {x} (R)) = x}$ .

Je snadné vidět, že relační databáze splňují axiomy označené algebry s informacemi:

poloskupina: ${displaystyle (R_ {1} owtie R_ {2}) owtie R_ {3} = R_ {1} owtie (R_ {2} owtie R_ {3})}$ a ${displaystyle R owtie S = S owtie R}$
tranzitivita: Li ${displaystyle xsubseteq ysubseteq d (R)}$ , pak ${displaystyle pi _ {x} (pi _ {y} (R)) = pi _ {x} (R)}$ .
kombinace: Li ${displaystyle d (R) = x}$ a ${displaystyle d (S) = y}$ , pak ${displaystyle pi _ {x} (R owtie S) = R owtie pi _ {xcap y} (S)}$ .
idempotence: Li ${displaystyle xsubseteq d (R)}$ , pak ${displaystyle R owtie pi _ {x} (R) = R}$ .
Podpěra, podpora: Li ${displaystyle x = d (R)}$ , pak ${displaystyle pi _ {x} (R) = R}$ .

Připojení

Oceňovací algebry: Zrušení idempotenční axiomu vede k oceňovací algebry. Tyto axiomy byly zavedeny (Shenoy & Shafer 1990 ) zobecnit místní výpočetní schémata (Lauritzen & Spiegelhalter 1988 ) od Bayesovských sítí po obecnější formalizmy, včetně funkce víry, potenciálních potenciálů atd. (Kohlas a Shenoy 2000 ). Expozici na dané téma v délce knihy viz Pouly & Kohlas (2011).
Domény a informační systémy: Kompaktní informační algebry (Kohlas 2003 ) souvisí s Scott domény a Scott informační systémy (Scott 1970 );(Scott 1982 );(Larsen & Winskel 1984 ).
Nejisté informace: Náhodné proměnné s hodnotami v informačních algebrách představují pravděpodobnostní argumentace systémy (Haenni, Kohlas & Lehmann 2000 ).
Sémantické informace: Informační algebry zavádějí sémantiku spojením informací s otázkami prostřednictvím zaměření a kombinace (Groenendijk a Stokhof 1984 );(Floridi 2004 ).
Informační tok: Informační algebry souvisí s tokem informací, zejména s klasifikacemi (Barwise a Seligman 1997 ).
Rozklad stromů: ...
Teorie poloskupin: ...
Kompoziční modely: Takové modely lze definovat v rámci informačních algeber: https://arxiv.org/abs/1612.02587
Rozšířené axiomatické základy informací a oceňovací algebry: Koncept podmíněné nezávislosti je základní pro informační algebry a je k dispozici nový axiomatický základ informačních algeber, založený na podmíněné nezávislosti, rozšiřující starou (viz výše): https://arxiv.org/abs/1701.02658

Historické kořeny

Axiomy pro informační algebry jsou odvozeny ze systému axiomů navrženého v (Shenoy a Shafer, 1990), viz také (Shafer, 1991).

Reference

Barwise, J.; Seligman, J. (1997), Informační tok: Logika distribuovaných systémů„Cambridge UK: Number 44 in Cambridge Tracts in Theoretical Computer Science, Cambridge University Press
Bergstra, J. A.; Heering, J .; Klint, P. (1990), "Modulová algebra", Deník ACM, 73 (2): 335–372, doi:10.1145/77600.77621, S2CID 7910431
Bistarelli, S .; Fargier, H .; Montanari, U .; Rossi, F .; Schiex, T .; Verfaillie, G. (1999), „Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison“, Omezení, 4 (3): 199–240, doi:10.1023 / A: 1026441215081, S2CID 17232456^{[trvalý mrtvý odkaz ]}
Bistarelli, Stefano; Montanari, Ugo; Rossi, Francesca (1997), „Spokojenost a optimalizace na základě semiring omezení“, Deník ACM, 44 (2): 201–236, CiteSeerX 10.1.1.45.5110, doi:10.1145/256303.256306, S2CID 4003767^{[trvalý mrtvý odkaz ]}
de Lavalette, Gerard R. Renardel (1992), „Logická sémantika modularizace“, v Egonu Börgerovi; Gerhard Jäger; Hans Kleine Büning; Michael M. Richter (eds.), CSL: 5. Workshop on Computer Science Logic, Volume 626 of Lecture Notes in Computer Science, Springer, pp. 306–315, ISBN 978-3-540-55789-0
Floridi, Luciano (2004), „Nástin teorie silně sémantické informace“ (PDF), Mysl a stroje, 14 (2): 197–221, doi:10.1023 / b: mind.0000021684.50925.c9, S2CID 3058065
Groenendijk, J .; Stokhof, M. (1984), Studie o sémantice otázek a pragmatice odpovědí, Disertační práce, Universiteit van Amsterdam
Haenni, R .; Kohlas, J .; Lehmann, N. (2000), „Pravděpodobnostní argumentační systémy“ (PDF), J. Kohlas; S. Moral (eds.), Příručka systémů spravovatelného uvažování a nejistoty, Dordrecht: Svazek 5: Algoritmy pro nejistotu a nepřiměřené uvažování, Kluwer, s. 221–287, archivovány z originál (PDF) 25. ledna 2005
Halmos, Paul R. (2000), „Autobiografie polyadických algeber“, Logický deník IGPL, 8 (4): 383–392, doi:10.1093 / jigpal / 8.4.383, S2CID 36156234
Henkin, L.; Monk, J. D .; Tarski, A. (1971), Válcové algebry, Amsterdam: Severní Holandsko, ISBN 978-0-7204-2043-2
Jaffar, J .; Maher, M. J. (1994), „Constraint logic programming: A survey“, J. Logického programování, 19/20: 503–581, doi:10.1016/0743-1066(94)90033-7
Kohlas, J. (2003), Informační algebry: Generické struktury pro odvozování, Springer-Verlag, ISBN 978-1-85233-689-9
Kohlas, J .; Shenoy, P.P. (2000), „Computation in valuation algebras“, J. Kohlas; S. Moral (eds.), Příručka systémů spravovatelného odůvodňování a nejistoty, svazek 5: Algoritmy pro nejistotu a nepřiměřené zdůvodňování, Dordrecht: Kluwer, s. 5–39
Kohlas, J .; Wilson, N. (2006), Přesný a přibližný lokální výpočet v semiringem indukovaných oceňovacích algebrách (PDF), Technická zpráva 06-06, Katedra informatiky, University of Fribourg, archivováno od originál (PDF) dne 24. září 2006
Larsen, K. G .; Winskel, G. (1984), „Využití informačních systémů k efektivnímu řešení rekurzivních doménových rovnic“, Gilles Kahn; David B. MacQueen; Gordon D. Plotkin (eds.), Sémantika datových typů, mezinárodní sympozium, Sophia-Antipolis, Francie, 27. – 29. Června 1984, sborník, 173 of Lecture Notes in Computer Science, Berlin: Springer, pp. 109–129
Lauritzen, S.L .; Spiegelhalter, D. J. (1988), „Místní výpočty s pravděpodobnostmi grafických struktur a jejich aplikace na expertní systémy“, Journal of the Royal Statistical Society, Series B, 50: 157–224
Pouly, Marc; Kohlas, Jürg (2011), Obecná inference: Sjednocující teorie pro automatické uvažováníJohn Wiley & Sons, ISBN 978-1-118-01086-0
Scott, Dana S. (1970), Nástin matematické teorie výpočtu„Technical Monograph PRG – 2, Oxford University Computing Laboratory, Programming Research Group
Scott, D.S. (1982), „Domains for denotational semantics“, v M. Nielsen; E.M. Schmitt (eds.), Automaty, jazyky a programování, Springer, str. 577–613
Shafer, G. (1991), Axiomatická studie výpočtu ve vysokých stromech, Working Paper 232, School of Business, University of Kansas
Shenoy, P. P .; Shafer, G. (1990). "Axiomy pro pravděpodobnost a funkci víry-funkce". V Ross D. Shachter; Tod S. Levitt; Laveen N. Kanal; John F. Lemmer (eds.). Nejistota v umělé inteligenci 4. Inteligence stroje a rozpoznávání vzorů. 9. Amsterdam: Elsevier. 169–198. doi:10.1016 / B978-0-444-88650-7.50019-6. hdl:1808/144. ISBN 978-0-444-88650-7.
Wilson, Nic; Mengin, Jérôme (1999), „Logická dedukce pomocí lokálního výpočetního rámce“, v Anthony Hunter; Simon Parsons (eds.), Symbolické a kvantitativní přístupy k uvažování a nejistotě, Evropská konference, ECSQARU'99, Londýn, Velká Británie, 5. – 9. Července 1999, sborník, svazek 1638 přednášek v informatice, Springer, str. 386–396, ISBN 978-3-540-66131-3