Information algebra

From Wikipedia, the free encyclopedia

Classical information theory goes back to Claude Shannon. It is a theory of information transmission, looking at communication and storage. However, it has not been considered so far that information comes from different sources and that it is therefore usually combined. It has furthermore been neglected in classical information theory that one wants to extract those parts out of a piece of information that are relevant to specific questions.

A mathematical phrasing of these operations leads to an algebra of information, describing basic modes of information processing. Such an algebra grasps a lot of formalisms of computer science, which seem to be different on the surface: relational databases, multiple systems of formal logic or numerical problems of linear algebra. It allows the development of generic procedures of information processing and thus a unification of basic methods of computer science, in particular of distributed information processing.

1 Information algebra
2 Information and its operations
3 Axioms and definition
4 Order of information
5 Labeled information algebra
6 Models of information algebras
- 6.1 Worked-out Example: Relational Algebra
7 Connections
8 Historical Roots
9 References

[edit] Information algebra

Information relates to precise questions, comes from different sources, must be aggregated and can be focused on questions of interest. Starting from these considerations, information algebras (Kohlas 2003) are two sorted algebras $(\Phi,D)\,$ , where $\Phi\,$ is a semigroup, representing combination or aggregation of information, $D\,$ is a lattice of domains (related to questions) whose partial order reflects the granularity of the domain or the question, and a mixed operation representing focusing or extraction of information.

[edit] Information and its operations

More precisely, in the two-sorted algebra $(\Phi,D)\,$ , the following operations are defined

Combination: $\otimes: \Phi \otimes \Phi \rightarrow \Phi,~ (\phi,\psi) \mapsto \phi \otimes \psi\,$
Focussing: $\Rightarrow: \Phi \otimes D \rightarrow \Phi,~ (\phi,x) \mapsto \phi^{\Rightarrow x}\,$

Additionally, in $D\,$ the usual lattice operations (meet and join) are defined.

[edit] Axioms and definition

The axioms of the two-sorted algebra $(\Phi,D)\,$ , in addition to the axioms of the lattice $D\,$ :

Semigroup: $\Phi\,$ is a commutative semigroup under combination with a neutral element (representing vacuous information).
Distributivity of Focusing over Combination: $(\phi^{\Rightarrow x} \otimes \psi)^{\Rightarrow x} = \phi^{\Rightarrow x} \otimes \psi^{\Rightarrow x}\,$

To focus an information on $x\,$ combined with another information to domain $x\,$ , one may as well first focus the second information to $x\,$ and combine then.

Transitivity of Focusing: $(\phi^{\Rightarrow x})^{\Rightarrow y} = \phi^{\Rightarrow x \wedge y}\,$

To focus an information on $x\,$ and $y\,$ , one may focus it to $x \wedge y\,$ .

Idempotency: $\phi \otimes \phi^{\Rightarrow x} = \phi\,$

An information combined with a part of itself gives nothing new.

Support: $\forall \phi \in \Phi,~ \exists x \in D\,$ such that $\phi = \phi^{\Rightarrow x}\,$

Each information refers to at least one domain (question).

A two-sorted algebra $(\Phi,D)\,$ satisfying these axioms is called an Information Algebra.

[edit] Order of information

A partial order of information can be introduced by defining $\phi \leq \psi\,$ if $\phi \otimes \psi = \psi\,$ . This means that $\phi\,$ is less informative than $\psi\,$ if it adds no new information to $\psi\,$ . The semigroup $\Phi\,$ is a semilattice relative to this order, i.e. $\phi \otimes \psi = \phi \vee \psi\,$ . Relative to any domain (question) $x \in D\,$ a partial order can be introduced by defining $\phi \leq_{x} \psi\,$ if $\phi^{\Rightarrow x} \leq \psi^{\Rightarrow x}\,$ . It represents the order of information content of $\phi\,$ and $\psi\,$ relative to the domain (question) $x\,$ .

[edit] Labeled information algebra

The pairs $(\phi,x) \ \,$ , where $\phi \in \Phi\,$ and $x \in D\,$ such that $\phi^{\Rightarrow x} = \phi\,$ form a labeled Information Algebra. More precisely, in the two-sorted algebra $(\Phi,D) \ \,$ , the following operations are defined

Labeling: $d(\phi,x) = x \ \,$
Combination: $(\phi,x) \otimes (\psi,y) = (\phi \otimes \psi,x \vee y)~~~~\,$
Projection: $(\phi,x)^{\downarrow y} = (\phi^{\Rightarrow y},y)\,$ for $y \leq x\,$

[edit] Models of information algebras

Here follows an incomplete list of instances of information algebras:

Relational algebra: The reduct of a relational algebra with natural join as combination and the usual projection is a labeled information algebra, see Example.
Constraint systems: Constraints form an information algebra (Jaffar & Maher 1994).
Semiring valued algebras: C-Semirings induce information algebras (Bistarelli & Montanari Rossi1997);(Bistarelli et al. Schiex);(Kohlas & Wilson 2006).
Logic: Many logic systems induce information algebras (Wilson & Mengin 1999). Reducts of cylindrical algebras (Henkin, Monk & Tarski 1971) or polyadic algebras are information algebras related to predicate logic (Halmos 2000).
Module algebras: (Bergstra, Heering & Klint 1990);(de Lavalette 1992).
Linear systems: Systems of linear equations or linear inequalities induce information algebras (Kohlas 2003).

[edit] Worked-out Example: Relational Algebra

Let ${\mathcal A}\,$ be a set of symbols, called attributes (or column names). For each $\alpha\in{\mathcal A}\,$ let $U_\alpha\,$ be a non-empty set, the set of all possible values of the attribute $\alpha\,$ . For example, if ${\mathcal A}= \{\texttt{name},\texttt{age},\texttt{income}\}\,$ , then $U_{\texttt{name}}\,$ could be the set of strings, whereas $U_{\texttt{age}}\,$ and $U_{\texttt{income}}\,$ are both the set of non-negative integers.

Let $x\subseteq{\mathcal A}\,$ . An $x\,$ -tuple is a function $f\,$ so that $\hbox{dom}(f)=x\,$ and $f(\alpha)\in U_\alpha\,$ for each $\alpha\in x\,$ The set of all $x\,$ -tuples is denoted by $E_x\,$ . For an $x\,$ -tuple $f\,$ and a subset $y\subseteq x\,$ the restriction $f[y]\,$ is defined to be the $y\,$ -tuple $g\,$ so that $g(\alpha)=f(\alpha)\,$ for all $\alpha\in y\,$ .

A relation $R\,$ over $x\,$ is a set of $x\,$ -tuples, i.e. a subset of $E_x\,$ . The set of attributes $x\,$ is called the domain of $R\,$ and denoted by $d(R)\,$ . For $y\subseteq d(R)\,$ the projection of $R\,$ onto $y\,$ is defined as follows:

$\pi_y(R):=\{f[y]\mid f\in R\}.\,$

The join of a relation $R\,$ over $x\,$ and a relation $S\,$ over $y\,$ is defined as follows:

$R\bowtie S:=\{f\mid f \quad (x\cup y)\hbox{-tuple},\quad f[x]\in R, \;f[y]\in S\}.\,$

As an example, let $R\,$ and $S\,$ be the following relations:

$R= \begin{matrix} \texttt{name} & \texttt{age} \\ \texttt{A} & \texttt{34} \\ \texttt{B} & \texttt{47} \\ \end{matrix}\qquad S= \begin{matrix} \texttt{name} & \texttt{income} \\ \texttt{A} & \texttt{20'000} \\ \texttt{B} & \texttt{32'000} \\ \end{matrix}\,$

Then the join of $R\,$ and $S\,$ is:

$R\bowtie S= \begin{matrix} \texttt{name} & \texttt{age} & \texttt{income} \\ \texttt{A} & \texttt{34} & \texttt{20'000} \\ \texttt{B} & \texttt{47} & \texttt{32'000} \\ \end{matrix}\,$

A relational database with natural join $\bowtie\,$ as combination and the usual projection $\pi\,$ is an information algebra. The operations are well defined since

$d(R\bowtie S)=d(R)\cup d(S)\,$
If $x\subseteq d(R)\,$ , then $d(\pi_x(R))=x\,$ .

It is easy to see that relational databases satisfy the axioms of a labeled information algebra:

semigroup: $(R_1\bowtie R_2)\bowtie R_3=R_1\bowtie(R_2\bowtie R_3)\,$ and $R\bowtie S=S\bowtie R\,$
transitivity: If $x\subseteq y\subseteq d(R)\,$ , then $\pi_x(\pi_y(R))=\pi_x(R)\,$ .
combination: If $d(R)=x\,$ and $d(S)=y\,$ , then $\pi_x(R\bowtie S)=R\bowtie\pi_{x\cap y}(S)\,$ .
idempotency: If $x\subseteq d(R)\,$ , then $R\bowtie\pi_x(R)=R\,$ .
support: If $x = d(R)\,$ , then $\pi_x(R)=R\,$ .

[edit] Connections

Valuation Algebras: Dropping the idempotency axiom leads to Valuation Algebras. These axioms have been introduced by (Shenoy & Shafer 1990) to generalize local computation schemes (Lauritzen & Spiegelhalter 1988) from Bayesian networks to more general formalisms (including belief function, possibility potentials, etc.) (Kohlas & Shenoy 2000).
Domains and Information Systems: Compact Information Algebras (Kohlas 2003) are related to Scott domains and Scott information systems (Scott 1970);(Scott 1982);(Larsen & Winskel 1984).
Uncertain Information: Random variables with values in information algebras represent probabilistic argumentation systems (Haenni, Kohlas & Lehmann 2000).
Semantic Information: Information algebras introduce semantics by relating information to questions through focusing and combination (Groenendijk & Stokhof 1984);(Floridi 2004).
Information Flow: Information algebras are related to information flow, in particular classifications (Barwise & Seligman 1997).
Tree decomposition: ...
Semigroup theory: ...

[edit] Historical Roots

The axioms for information algebras are derived from the axiom system proposed in (Shenoy and Shafer, 1990), see also (Shafer, 1991).

[edit] References

Barwise, J. & J. Seligman (1997), written at Cambridge U.K., Information Flow: The Logic of Distributed Systems, Number 44 in Cambridge Tracts in Theoretical Computer Science, Cambridge University Press

Bergstra, J.A.; J. Heering & P. Klint (1990), "Module algebra", J. of the assoc. for Computing Machinery 73 (2): 335–372

Bistarelli, S.; H. Fargier & U. Montanari et al. (1999), "Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison", Constraints 4 (3): 199-240, <ftp://ftp.irit.fr/pub/IRIT/RPDMP/PapersFargier/valuatedItaliens.ps.gz>

Bistarelli, Stefano; Ugo Montanari & Francesca Rossi (1997), "Semiring-based constraint satisfaction and optimization", Journal of the ACM 44 (2): 201–236, <ftp://ftp.di.unipi.it/pub/Papers/rossi/jacm.ps.gz>

de Lavalette, Gerard R. Renardel (1992), "Logical semantics of modularisation", in Egon Börger, Gerhard Jäger, Hans Kleine Büning, and Michael M. Richter, CSL: 5th Workshop on Computer Science Logic, Volume 626 of Lecture Notes in Computer Science, Springer, 306–315, ISBN 3-540-55789-X, <http://citeseer.ist.psu.edu/484529.html>

Floridi, Luciano (2004), "Outline of a theory of strongly semantic information", Minds and Machines 14 (2): 197–221

Groenendijk, J. & M. Stokhof (1984), Studies on the Semantics of Questions and the Pragmatics of Answers, PhD thesis, Universiteit van Amsterdam

Haenni, R.; J. Kohlas & N. Lehmann (2000), "Probabilistic argumentation systems", written at Dordrecht, in J. Kohlas and S. Moral, Handbook of Defeasible Reasoning and Uncertainty Management Systems, Volume 5: Algorithms for Uncertainty and Defeasible Reasoning, Kluwer, 221–287, <http://diuf.unifr.ch/tcs/publications/ps/hkl2000.pdf>

Halmos, Paul R. (2000), "An autobiography of polyadic algebras", Logic Journal of the IGPL 8 (4)

Henkin, L.; J. D. Monk & A. Tarski (1971), written at Amsterdam, Cylindric Algebras, North-Holland, ISBN 0-7204-2043-1

Jaffar, J. & M. J. Maher (1994), "Constraint logic programming: A survey", J. of Logic Programming 19/20: 503–581

Kohlas, J. (2003), Information Algebras: Generic Structures for Inference, Springer-Verlag, ISBN 1852336897

Kohlas, J. & P.P. Shenoy (2000), "Computation in valuation algebras", written at Dordrecht, in J. Kohlas and S. Moral, Handbook of Defeasible Reasoning and Uncertainty Management Systems, Volume 5: Algorithms for Uncertainty and Defeasible Reasoning, Kluwer, 5–39

Kohlas, J. & N. Wilson (2006), Exact and approximate local computation in semiring-induced valuation algebras, Technical Report 06-06, Department of Informatics, University of Fribourg, <http://diuf.unifr.ch/tcs/publications/ps/kohlaswilson06.pdf>

Larsen, K. G. & G. Winskel (1984), "Using information systems to solve recursive domain equations effectively", in Gilles Kahn, David B. MacQueen, and Gordon D. Plotkin, Semantics of Data Types, International Symposium, Sophia-Antipolis, France, June 27-29, 1984, Proceedings, vol. 173 of Lec- ture Notes in Computer Science, Springer, 109–129

Lauritzen, S. L. & D. J. Spiegelhalter (1988), "Local computations with probabilities on graphical structures and their application to expert systems", J. Royal Statis. Soc. B 50: 157–224

Scott, Dana S. (1970), Outline of a mathematical theory of computation, Technical Monograph PRG–2, Oxford University Computing Laboratory, Programming Research Group

Scott, D.S. (1982), "Domains for denotational semantics", in M. Nielsen and E.M. Schmitt, Automata, Languages and Programming, Springer, 577–613

Shafer, G. (1991), An axiomatic study of computation in hypertrees, Working Paper 232, School of Business, University of Kansas

Shenoy, P. P. & G. Shafer (1990), Axioms for probability and belief-function proagation, written at Amsterdam, in Ross D. Shachter, Tod S. Levitt, Laveen N. Kanal, and John F. Lemmer, "Uncertainty in Artificial Intelligence 4", Machine intelligence and pattern recognition (Elsevier) 9: 169–198, ISBN 0-444-88650-8

Wilson, Nic & Jérôme Mengin (1999), "Logical deduction using the local computation framework", in Anthony Hunter and Simon Parsons,, Symbolic and Quantitative Approaches to Reasoning and Uncertainty, European Confer- ence, ECSQARU’99, London, UK, July 5-9, 1999, Proceedings, volume 1638 of Lecture Notes in Computer Science, Springer, 386–396, ISBN 3-540-66131-X, <http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=1638&spage=0386>

Categories: Algebraic information theory