Information algebra


Information algebra

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.

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 Harv|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.

Information and its operations

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

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 .
*Constraint systems: Constraints form an information algebra Harv|Jaffar|Maher|1994.
*Semiring valued algebras: C-Semirings induce information algebras Harv|Bistarelli|Montanari|Rossi1997;Harv|Bistarelli|Fargier|Montanari|Rossi|Schiex|Verfaillie|1999;Harv|Kohlas|Wilson|2006.
*Logic: Many logic systems induce information algebras Harv|Wilson|Mengin|1999. Reducts of cylindrical algebras Harv|Henkin|Monk|Tarski|1971 or polyadic algebras are information algebras related to predicate logic Harv|Halmos|2000.
*Module algebras: Harv|Bergstra|Heering|Klint|1990;Harv|de Lavalette|1992.
*Linear systems: Systems of linear equations or linear inequalities induce information algebras Harv|Kohlas|2003.

Worked-out Example: Relational Algebra

Let {mathcal A}, be a set of symbols, called attributes (or columnnames). For each alphain{mathcal A}, let U_alpha, be a non-empty set, theset of all possible values of the attribute alpha,. For example, if {mathcal A}= { exttt{name}, exttt{age}, exttt{income}},, then U_{ exttt{name, couldbe the set of strings, whereas U_{ exttt{age, and U_{ exttt{income, are boththe set of non-negative integers.

Let xsubseteq{mathcal A},. An x,-tuple is a function f, so thathbox{dom}(f)=x, and f(alpha)in U_alpha, for each alphain x, The setof all x,-tuples is denoted by E_x,. For an x,-tuple f, and a subsetysubseteq x, the restriction f [y] , is defined to be they,-tuple g, so that g(alpha)=f(alpha), for all alphain 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 byd(R),. For ysubseteq d(R), the projection of R, onto y, is definedas follows::pi_y(R):={f [y] mid fin R}.,The join of a relation R, over x, and a relation S, over y, isdefined as follows::Rowtie S:={fmid f quad (xcup y)hbox{-tuple},quad f [x] in R, ;f [y] in S}.,As an example, let R, and S, be the following relations::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},Then the join of R, and S, is::Rowtie S= egin{matrix} exttt{name} & exttt{age} & exttt{income} \ exttt{A} & exttt{34} & exttt{20'000} \ exttt{B} & exttt{47} & exttt{32'000} \ end{matrix},A relational database with natural join owtie, as combination and the usual projection pi, is an information algebra.The operations are well defined since

  • d(Rowtie S)=d(R)cup d(S),
  • If xsubseteq d(R),, then d(pi_x(R))=x,.
It is easy to see that relational databases satisfy the axioms of a labeledinformation algebra:; semigroup : (R_1owtie R_2)owtie R_3=R_1owtie(R_2owtie R_3), and Rowtie S=Sowtie R,; transitivity : If xsubseteq ysubseteq d(R),, then pi_x(pi_y(R))=pi_x(R),.; combination : If d(R)=x, and d(S)=y,, then pi_x(Rowtie S)=Rowtiepi_{xcap y}(S),.; idempotency : If xsubseteq d(R),, then Rowtiepi_x(R)=R,.; support : If x = d(R),, then pi_x(R)=R,.

Connections

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

Historical Roots

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

References

Harvard reference | Given=Gerard R. Renardel | Surname=de Lavalette | Chapter= Logical semantics of modularisation | Editor=Egon Börger, Gerhard Jäger, Hans Kleine Büning, and Michael M. Richter | Title=CSL: 5th Workshop on Computer Science Logic | Pages=306–315 | Publisher=Volume 626 of Lecture Notes in Computer Science, Springer | Year=1992 | ISBN=3-540-55789-X
URL=http://citeseer.ist.psu.edu/484529.html

Harvard reference | Given1=K. G. | Surname1=Larsen | Given2=G. |Surname2=Winskel | Chapter=Using information systems to solve recursive domain equations effectively | Editor=Gilles Kahn, David B. MacQueen, and Gordon D. Plotkin | Title=Semantics of Data Types, International Symposium, Sophia-Antipolis, France, June 27-29, 1984, Proceedings | Volume=173 of Lec- ture Notes in Computer Science | Pages=109–129 | Location=Berlin | Year= 1984 | Publisher=Springer

Harvard reference | Given1=S. L. | Surname1= Lauritzen |Given2=D. J.|Surname2=Spiegelhalter | Title=Local computations with probabilities on graphical structures and their application to expert systems | Journal= J. Royal Statis. Soc. B |Volume= 50 | Pages=157–224 | Year= 1988

Harvard reference | Given=Dana S. | Surname= Scott | Title= Outline of a mathematical theory of computation | Publisher=Technical Monograph PRG–2, Oxford University Computing Laboratory, Programming Research Group | Year=1970

Harvard reference | Given1=P. P. | Surname1=Shenoy | Given2=G. | Surname2=Shafer | Chapter=Axioms for probability and belief-function proagation | Editor=Ross D. Shachter, Tod S. Levitt, Laveen N. Kanal, and John F. Lemmer | Title= Uncertainty in Artificial Intelligence 4 | Volume= 9 | Journal= Machine intelligence and pattern recognition |Pages = 169–198 | Place=Amsterdam | Year= 1990 | Publisher=Elsevier | ISBN= 0-444-88650-8

Harvard reference | Given1=Nic | Surname1=Wilson |Given2= Jérôme | Surname2= Mengin | Chapter=Logical deduction using the local computation framework | Editor=Anthony Hunter and Simon Parsons, | Title=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 | Pages= 386–396 | Publisher= Springer | Year= 1999 | ISBN = 3-540-66131-X | URL = http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=1638&spage=0386


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Information theory — Not to be confused with Information science. Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental… …   Wikipedia

  • Information Integration Theory — was proposed by Norman H. Anderson to describe and model how a person integrates information from a number of sources in to make an overall judgment. The theory proposes three functions. [1] The valuation function V(S) is an empirically derived… …   Wikipedia

  • algebra — /al jeuh breuh/, n. 1. the branch of mathematics that deals with general statements of relations, utilizing letters and other symbols to represent specific sets of numbers, values, vectors, etc., in the description of such relations. 2. any of… …   Universalium

  • Algebra — This article is about the branch of mathematics. For other uses, see Algebra (disambiguation). Algebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from… …   Wikipedia

  • Information theory and measure theory — Measures in information theory = Many of the formulas in information theory have separate versions for continuous and discrete cases, i.e. integrals for the continuous case and sums for the discrete case. These versions can often be generalized… …   Wikipedia

  • Information science — Not to be confused with Information theory. Contents 1 Introduction 2 A multitude of information sciences? 3 Definitions of information science 4 History …   Wikipedia

  • information theory — the mathematical theory concerned with the content, transmission, storage, and retrieval of information, usually in the form of messages or data, and esp. by means of computers. [1945 50] * * * ▪ mathematics Introduction       a mathematical… …   Universalium

  • information processing — Acquisition, recording, organization, retrieval, display, and dissemination of information. Today the term usually refers to computer based operations. Information processing consists of locating and capturing information, using software to… …   Universalium

  • Homological algebra — is the branch of mathematics which studies homology in a general algebraic setting. It is a relatively young discipline, whose origins can be traced to investigations in combinatorial topology (a precursor to algebraic topology) and abstract… …   Wikipedia

  • History of algebra — Elementary algebra is the branch of mathematics that deals with solving for the operands of arithmetic equations. Modern or abstract algebra has its origins as an abstraction of elementary algebra. Historians know that the earliest mathematical… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.