Algebra informacji - Information algebra

Termin „ algebra informacji ” odnosi się do matematycznych technik przetwarzania informacji . Klasyczna teoria informacji sięga Claude'a Shannona . Jest to teoria przekazu informacji, patrząca na komunikację i przechowywanie. Jednak do tej pory nie brano pod uwagę, że informacje pochodzą z różnych źródeł i dlatego są one zwykle łączone. Co więcej, w klasycznej teorii informacji zaniedbano to, że chce się wydobyć z informacji te części, które są istotne dla konkretnych pytań.

Matematyczne sformułowanie tych operacji prowadzi do algebry informacji , opisującej podstawowe sposoby przetwarzania informacji. Taka algebra obejmuje kilka formalizmów informatyki , które z pozoru wydają się różne: relacyjne bazy danych, wiele systemów logiki formalnej czy problemy numeryczne algebry liniowej. Pozwala na opracowanie generycznych procedur przetwarzania informacji, a tym samym ujednolicenie podstawowych metod informatyki, w szczególności rozproszonego przetwarzania informacji .

Informacje odnoszą się do precyzyjnych pytań, pochodzą z różnych źródeł, muszą być zagregowane i mogą koncentrować się na pytaniach będących przedmiotem zainteresowania. Zaczynając od tych rozważań, algebry informacyjne ( Kohlas 2003 ) są dwa posortowane algebry , gdzie jest półgrupa , stanowiących kombinację lub agregacji informacji jest kratownica z domen (powiązane z pytaniami), których częściowy porządek odzwierciedla ziarnistość domeny lub pytanie oraz operację mieszaną reprezentującą skupianie lub wydobywanie informacji. ${\ Displaystyle (\ Phi, D)}$${\ Displaystyle \ Phi}$${\ Displaystyle D}$

Informacja i jej działanie

Dokładniej, w algebrze dwojakiego sortowania zdefiniowane są następujące operacje: ${\ Displaystyle (\ Phi, D)}$

Połączenie ${\ Displaystyle \ otimes: \ Phi \ otimes \ Phi \ rightarrow \ Phi ~ (\phi \ psi) \ mapsto \ phi \ otimes \ psi}$ Skupienie ${\ Displaystyle \ Strzałka w prawo: \ Phi \ otimes D \ Strzałka w prawo \ Phi ~ (\ Phi, x) \ mapsto \ Phi ^ {\ Strzałka w prawo x}}$

Dodatkowo w zwykłych sieciach zdefiniowane są operacje (meet and join). ${\ Displaystyle D}$

Aksjomaty i definicja

Aksjomaty algebry dwuposortowanej , oprócz aksjomatów kraty : ${\ Displaystyle (\ Phi, D)}$${\ Displaystyle D}$

Półgrupa ${\ Displaystyle \ Phi}$ jest przemienną półgrupą w połączeniu z elementem neutralnym (reprezentującym informację próżniową). Dystrybucja skupienia nad kombinacją ${\ Displaystyle (\ phi ^ {\ strzałka w prawo x} \ czasamis \ psi) ^ {\ strzałka w prawo x} = \ phi ^ {\ strzałka w prawo x} \ czasami \ psi ^ {\ strzałka w prawo x}}$ Aby skoncentrować informację na połączeniu z inną informacją w domenie , można równie dobrze najpierw skoncentrować drugą informację na a następnie połączyć. ${\displaystyle x}$${\displaystyle x}$${\displaystyle x}$ Przechodniość skupienia ${\ Displaystyle (\ phi ^ {\ strzałka w prawo x}) ^ {\ strzałka w prawo y} = \ phi ^ {\ strzałka w prawo x \ klin y}}$ Aby skoncentrować informację na i , można ją skoncentrować na . ${\displaystyle x}$${\displaystyle y}$${\displaystyle x\klin y}$ Idempotencja ${\ Displaystyle \ phi \ czasami \ phi ^ {\ strzałka w prawo x} = \ phi}$ Informacja połączona z częścią siebie nie wnosi nic nowego. Wsparcie ${\ Displaystyle \ forall \ phi \ w \ Phi ~ \ istnieje x \ w D}$ takie, że ${\ Displaystyle \ phi = \ phi ^ {\ strzałka w prawo x}}$ Każda informacja dotyczy co najmniej jednej domeny (pytania).

Algebra z dwoma sortowaniami spełniająca te aksjomaty nazywa się Algebra Informacyjna . ${\ Displaystyle (\ Phi, D)}$

Kolejność informacji

Częściową kolejność informacji można wprowadzić, określając, czy . Oznacza to, że jest to mniej pouczające niż w przypadku, gdy nie dodaje żadnych nowych informacji do . Półgrupa jest półsiecią w stosunku do tego rzędu, tj . . W stosunku do dowolnej dziedziny (pytania) można wprowadzić porządek częściowy poprzez zdefiniowanie czy . Reprezentuje kolejność zawartości informacji i względem domeny (pytanie) . ${\ Displaystyle \ phi \ leq \ psi}$${\ Displaystyle \ phi \ czasami \ psi = \ psi}$${\displaystyle \phi}$${\ Displaystyle \ psi}$${\ Displaystyle \ psi}$${\ Displaystyle \ Phi}$${\ Displaystyle \ phi \ czasami \ psi = \ phi \ vee \ psi}$${\displaystyle x\w d}$${\ Displaystyle \ phi \ leq _ {x} \ psi}$${\ Displaystyle \ phi ^ {\ strzałka w prawo x} \ leq \ psi ^ {\ strzałka w prawo x}}$${\displaystyle \phi}$${\ Displaystyle \ psi}$${\displaystyle x}$

Oznaczona algebra informacji

Pary , gdzie i takie , które tworzą etykietowaną Algebrę Informacyjną . Dokładniej, w algebrze dwojakiego sortowania zdefiniowane są następujące operacje: ${\displaystyle (\phi ,x)\ }$${\ Displaystyle \ phi \ w \ phi}$${\displaystyle x\w d}$${\ Displaystyle \ phi ^ {\ strzałka w prawo x} = \ phi}$${\displaystyle (\Phi,D)\}$

Etykietowanie ${\displaystyle d(\phi,x)=x\}$ Połączenie ${\ Displaystyle (\ phi, x) \ otimes (\ psi , y) = (\ phi \ otimes \ psi , x \ vee y) ~~~~}$ Występ ${\ Displaystyle (\ phi, x) ^ {\ strzałka w dół y} = (\ phi ^ {\ strzałka w prawo y}, y) {\ tekst {dla}} y \ równoważnik x}$

Modele algebr informacyjnych

Oto niepełna lista wystąpień algebr informacyjnych:

• Algebra relacyjna : Redukt algebry relacyjnej z połączeniem naturalnym i zwykłym odwzorowaniem jest etykietowaną algebrą informacji, patrz Przykład .
• Systemy ograniczeń : ograniczenia tworzą algebrę informacji ( Jaffar i Maher 1994 ).
• Algebry o wartościach semiringowych : C-Semiringi indukują algebry informacyjne ( Bistarelli, Montanari i Rossi1997 ); ( Bistarelli i in. 1999 ); ( Kohlas i Wilson 2006 ).
• Logika : Wiele systemów logicznych indukuje algebry informacyjne ( Wilson i Mengin 1999 ). Redukty algebr cylindrycznych ( Henkin, Monk i Tarski 1971 ) lub algebr poliadycznych są algebrami informacyjnymi związanymi z logiką predykatów ( Halmos 2000 ).
• Algebry modułowe : ( Bergstra, Heering i Klint 1990 ); ( de Lavalette 1992 ).
• Układy liniowe : Układy równań liniowych lub nierówności liniowe indukują algebry informacyjne ( Kohlas 2003 ).

Opracowany przykład: algebra relacyjna

Niech będzie zbiorem symboli, zwanych atrybutami (lub nazwami kolumn ). Dla każdego niech będzie niepusty zbiór, zbiór wszystkich możliwych wartości atrybutu . Na przykład, jeśli , to może być zbiorem łańcuchów, podczas gdy i są zbiorem nieujemnych liczb całkowitych. ${\ Displaystyle {\ Mathcal {A}}}$${\ Displaystyle \ alfa \ w {\ mathcal {A}}}$${\ Displaystyle U_ {\ alfa}}$${\ Displaystyle \ alfa}$${\displaystyle {\mathcal {A}}=\{{\texttt {imię}},{\texttt {wiek}},{\texttt {dochód}}\}}$${\displaystyle U_{\texttt {nazwa}}}$${\displaystyle U_{\texttt {wiek}}}$${\displaystyle U_{\texttt {dochód}}}$

Niech . -Tuple jest funkcją tak, że i dla każdego Zbiór wszystkich -tuples oznaczamy przez . Dla -krotki i podzbioru ograniczenie jest zdefiniowane jako -krotka, tak aby dla wszystkich . ${\displaystyle x\subseteq {\mathcal {A}}}$${\displaystyle x}$${\displaystyle f}$${\ Displaystyle {\ hbox {dom}} (f) = x}$${\ Displaystyle f (\ alfa ) \ w U_ {\ alfa}}$${\ Displaystyle \ alfa \ w x}$${\displaystyle x}$${\ Displaystyle E_ {x}}$${\displaystyle x}$${\displaystyle f}$${\displaystyle y\subseteq x}$${\displaystyle f[y]}$${\displaystyle y}$${\displaystyle g}$${\displaystyle g(\alfa)=f(\alfa)}$${\ Displaystyle \ alfa \ w Y}$

Relacja ponad${\ Displaystyle R}$${\displaystyle x}$ to zestaw -tuples, czyli podzbiór . Zbiór atrybutów jest nazywany domenę z i oznaczamy przez . Na tym rzucie z na jest określona w następujący sposób: ${\displaystyle x}$${\ Displaystyle E_ {x}}$${\displaystyle x}$${\ Displaystyle R}$${\ Displaystyle d (R)}$${\displaystyle y\subseteq d(R)}$${\ Displaystyle R}$${\displaystyle y}$

${\ Displaystyle \ pi _ {y} (R): = \ {f [y] \ mid f \ w R \}.}$

Przyłączyć od stosunku nad i związek na jest określona w następujący sposób: ${\ Displaystyle R}$${\displaystyle x}$${\displaystyle S}$${\displaystyle y}$

${\ Displaystyle R \ Bowtie S: = \ {f \ mid f \ quad (x \ filiżanka y) {\ hbox {-krotka}}, \ quad f [x] \ w R \; f [y] \ w S\}.}$

Jako przykład niech i będą następujące relacje: ${\ Displaystyle R}$${\displaystyle S}$

${\ Displaystyle R = {\ zacząć {macierz}} {\ texttt {nazwa}} i {\ texttt {wiek}} \ \ {\ texttt {A}} i {\ texttt {34}} \ \ {\ texttt {B }}&{\texttt {47}}\\\end{matrix}}\qquad S={\begin{matrix}{\texttt {nazwa}}&{\texttt {dochód}}\\{\texttt {A }}&{\texttt {20'000}}\\{\texttt {B}}&{\texttt {32'000}}\\\end{macierz}}}$

Wtedy złączeniem i jest: ${\ Displaystyle R}$${\displaystyle S}$

${\ Displaystyle R \ bowtie S = {\ zacząć {macierz} {\ texttt {imię}} i {\ texttt {wiek}} i {\ texttt {dochód}} \ \ {\ texttt {A}} i {\ texttt {34}}&{\texttt {20'000}}\\{\texttt {B}}&{\texttt {47}}&{\texttt {32'000}}\\\end{macierz}}}$

Relacyjna baza danych z połączeniem naturalnym jako kombinacja i zwykłą projekcją jest algebrą informacyjną. Operacje są dobrze zdefiniowane, ponieważ ${\displaystyle \muszka}$${\displaystyle \pi}$

• ${\ Displaystyle d (R \ muszka S) = d (R) \ filiżanka d (S)}$
• Jeśli , to .${\displaystyle x\subseteq d(R)}$${\ Displaystyle d (\ pi _ {x} (R)) = x}$

Łatwo zauważyć, że relacyjne bazy danych spełniają aksjomaty etykietowanej algebry informacji:

półgrupa

${\ Displaystyle (R_ {1} \ muszka R_ {2}) \ muszka R_ {3} = R_ {1} \ muszka (R_ {2} \ muszka R_ {3})}$ oraz ${\ Displaystyle R \ muszka S = S \ muszka R}$

przechodniość

Jeśli , to .${\displaystyle x\subseteq y\subseteq d(R)}$${\ Displaystyle \ pi _ {x} (\ pi _ {y} (R)) = \ pi _ {x} (R)}$

połączenie

Jeśli i , to .${\ Displaystyle d (R) = x}$${\ Displaystyle d (S) = y}$${\ Displaystyle \ pi _ {x} (R \ muszka S) = R \ muszka \ pi _ {x \ czapka y} (S)}$

idempotencja

Jeśli , to .${\displaystyle x\subseteq d(R)}$${\ Displaystyle R \ muszka \ pi _ {x} (R) = R}$

Pomoc

Jeśli , to .${\ Displaystyle x = d (R)}$${\ Displaystyle \ pi _ {x} (R) = R}$

Znajomości

Algebry wyceny

Porzucenie aksjomatu idempotentności prowadzi do algebr wartościowania . Aksjomaty te zostały wprowadzone przez ( Shenoy i Shafer 1990 ) w celu uogólnienia lokalnych schematów obliczeniowych ( Lauritzen i Spiegelhalter 1988 ) z sieci bayesowskich do bardziej ogólnych formalizmów, w tym funkcji przekonań, potencjałów możliwości itp. ( Khollas i Shenoy 2000 ). Ekspozycja o objętości książki na ten temat znajduje się w Pouly & Kohlas (2011) .

Domeny i systemy informacyjne

Kompaktowe algebry informacyjne ( Kohlas 2003 ) są związane z domenami Scotta i systemami informacyjnymi Scotta ( Scott 1970 ); ( Scott 1982 ); ( Larsen & Winskel 1984 ).

Niepewne informacje

Zmienne losowe z wartościami w algebrach informacyjnych reprezentują probabilistyczne systemy argumentacji ( Haenni, Kohlas & Lehmann 2000 ).

Informacje semantyczne

Algebry informacyjne wprowadzają semantykę poprzez powiązanie informacji z pytaniami poprzez skupienie i kombinację ( Groenendijk & Stokhof 1984 ); ( Floridi 2004 ).

Przepływ informacji

Algebry informacyjne są związane z przepływem informacji, w szczególności klasyfikacjami ( Barwise i Seligman 1997 ).

Rozkład drzewa

...

Teoria półgrup

...

Modele kompozycyjne

Takie modele można zdefiniować w ramach algebr informacyjnych: https://arxiv.org/abs/1612.02587

Rozszerzone podstawy aksjomatyczne algebr informacyjnych i wartościujących

Pojęcie warunkowej niezależności jest podstawą algebr informacyjnych, a nowa podstawa aksjomatyczna algebr informacyjnych, oparta na warunkowej niezależności, rozszerzająca starą (patrz wyżej) jest dostępna: https://arxiv.org/abs/1701.02658

Korzenie historyczne

Aksjomaty algebr informacyjnych wywodzą się z systemu aksjomatów zaproponowanego w (Shenoy i Shafer, 1990), patrz także (Shafer, 1991).

Bibliografia

• Barwise, J .; Seligman, J. (1997), Przepływ informacji: Logika systemów rozproszonych , Cambridge UK: Numer 44 w Cambridge Tracts in Theoretical Computer Science, Cambridge University Press
• Bergstra, JA; Heering, J.; Klint, P. (1990), "Algebra modułów", Journal of the 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), "CSP oparte na semiringu i cenione CSP: ramy, właściwości i porównanie" , Ograniczenia , 4 (3): 199-240, doi : 10.1023/A:1026441215081 , S2CID  17232456
• Bistarelli, Stefano; Montanari, Ugo; Rossi, Francesca (1997), "Semiring oparte na spełnianiu ograniczeń i optymalizacji", Journal of the ACM , 44 (2): 201-236, CiteSeerX  10.1.1.45.5110 , doi : 10.1145/256303.256306 , S2CID  4003767
• de Lavalette, Gerard R. Renardel (1992), „Logiczna semantyka modularyzacji” , w Egon Börger; Gerharda Jägera; Hansa Kleine Buninga; Michael M. Richter (red.), CSL: 5. Warsztaty na temat logiki komputerowej , tom 626 notatek z wykładów z informatyki, Springer, s. 306-315, ISBN 978-3-540-55789-0
• Floridi, Luciano (2004), „Zarys teorii informacji silnie semantycznej” (PDF) , Minds and Machines , 14 (2): 197-221, doi : 10.1023/b:mind.0000021684.50925.c9 , S2CID  3058065
• Groenendijk, J.; Stokhof, M. (1984), Studies on the Semantics of Questions and the Pragmatics of Answers , praca doktorska, Universiteit van Amsterdam
• Haenni, R.; Kohlas, J.; Lehmann, N. (2000), "Probabilistyczne systemy argumentacji" (PDF) , w J. Kohlas; S. Moral (red.), Handbook of Defeasible Reasoning and Uncertainty Management Systems , Dordrecht: Tom 5: Algorithms for Uncertainty and Defeasible Reasoning, Kluwer, s. 221–287, zarchiwizowane z oryginału (PDF) 25 stycznia 2005 r.
• Halmos, Paul R. (2000), "Autobiografia algebr poliadycznych" , Logic Journal of the IGPL , 8 (4): 383-392, doi : 10.1093/jigpal/8.4.383 , S2CID  36156234
• Henkin, L .; mnich, JD; Tarski, A. (1971), Cylindric Algebras , Amsterdam: Północna Holandia, ISBN 978-0-7204-2043-2
• Jaffar, J.; Maher, MJ (1994), "Programowanie w logice z ograniczeniami: ankieta", Journal of Logic Programming , 19/20: 503-581, doi : 10.1016/0743-1066(94)90033-7
• Kohlas, J. (2003), Algebry informacyjne: struktury ogólne do wnioskowania , Springer-Verlag, ISBN 978-1-85233-689-9
• Kohlas, J.; Shenoy PP (2000), "Obliczenia w algebrach wyceny", w J. Kohlas; S. Moral (red.), Handbook of Defeasible Reasoning and Uncertainty Management Systems, tom 5: Algorytmy dla niepewności i defeasible Reasoning , Dordrecht: Kluwer, s. 5-39
• Kohlas, J.; Wilson, N. (2006), Dokładne i przybliżone obliczenia lokalne w algebrach wyceny indukowanej półpierścieniem (PDF) , Raport techniczny 06-06, Wydział Informatyki, Uniwersytet we Fryburgu, zarchiwizowane z oryginału (PDF) w dniu 24 września 2006 r.
• Larsen, KG; Winskel, G. (1984), „Wykorzystywanie systemów informatycznych do efektywnego rozwiązywania równań domeny rekurencyjnej”, w Gilles Kahn; Davida B. MacQueena; Gordon D. Plotkin (red.), Semantics of Data Types, International Symposium, Sophia-Antipolis, Francja, 27-29 czerwca 1984, Proceedings , 173 of Lecture Notes in Computer Science, Berlin: Springer, s. 109-129
• Lauritzen, SL; Spiegelhalter, DJ (1988), „Lokalne obliczenia z prawdopodobieństwami na strukturach graficznych i ich zastosowanie do systemów ekspertowych”, Journal of the Royal Statistical Society, Seria B , 50 : 157-224
• Pouly, Marc; Kohlas, Jürg (2011), Ogólne wnioskowanie: teoria ujednolicająca zautomatyzowane wnioskowanie , John Wiley & Sons, ISBN 978-1-118-01086-0
• Scott, Dana S. (1970), Zarys matematycznej teorii obliczeń , Monografia techniczna PRG-2, Oxford University Computing Laboratory, Programming Research Group
• Scott, DS (1982), "Domeny dla semantyki denotacyjnej", w M. Nielsen; EM Schmitt (red.), Automaty, języki i programowanie , Springer, s. 577–613
• Shafer, G. (1991), An aksjomatyczne studium obliczeń w hiperdrzewach , dokument roboczy 232, School of Business, University of Kansas
• Shenoy, PP; Shafer, G. (1990). „Aksjomaty propagacji prawdopodobieństwa i funkcji przekonań”. W Rossie D. Shachterze; Tod S. Levitt; Laveena N. Kanala; John F. Lemmer (red.). Niepewność w sztucznej inteligencji 4 . Inteligencja maszynowa i rozpoznawanie wzorców . 9 . Amsterdam: Elsevier. s. 169-198. doi : 10.1016/B978-0-444-88650-7.50019-6 . hdl : 1808/144 . Numer ISBN 978-0-444-88650-7.
• Wilsona, Nica; Mengin, Jérôme (1999), „ Dedukcja logiczna przy użyciu lokalnej struktury obliczeniowej” , w Anthony Hunter; Simon Parsons (red.), Symbolic and Quantitative Approaches to Reasoning and Uncertainty, European Conference, ECSQARU'99, Londyn, Wielka Brytania, 5-9 lipca 1999, Proceedings, tom 1638 Lecture Notes in Computer Science , Springer, s. 386 –396, ISBN 978-3-540-66131-3