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.
Informacja i jej działanie
Dokładniej, w algebrze dwojakiego sortowania zdefiniowane są następujące operacje:
|
Dodatkowo w zwykłych sieciach zdefiniowane są operacje (meet and join).
Aksjomaty i definicja
Aksjomaty algebry dwuposortowanej , oprócz aksjomatów kraty :
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ć.
Aby skoncentrować informację na i , można ją skoncentrować na .
Informacja połączona z częścią siebie nie wnosi nic nowego.
Każda informacja dotyczy co najmniej jednej domeny (pytania). |
Algebra z dwoma sortowaniami spełniająca te aksjomaty nazywa się Algebra Informacyjna .
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) .
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:
|
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.
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 .
Relacja ponad 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:
Przyłączyć od stosunku nad i związek na jest określona w następujący sposób:
Jako przykład niech i będą następujące relacje:
Wtedy złączeniem i jest:
Relacyjna baza danych z połączeniem naturalnym jako kombinacja i zwykłą projekcją jest algebrą informacyjną. Operacje są dobrze zdefiniowane, ponieważ
- Jeśli , to .
Łatwo zauważyć, że relacyjne bazy danych spełniają aksjomaty etykietowanej algebry informacji:
- półgrupa
- oraz
- przechodniość
- Jeśli , to .
- połączenie
- Jeśli i , to .
- idempotencja
- Jeśli , to .
- Pomoc
- Jeśli , to .
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