Information algebra

The term "information algebra" refers to mathematical techniques of information processing. 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 involves several 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 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 , where is a semigroup, representing combination or aggregation of information, 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 , the following operations are defined

Combination 
Focusing 
            

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

Axioms and definition

The axioms of the two-sorted algebra , in addition to the axioms of the lattice :

Semigroup 
is a commutative semigroup under combination with a neutral element (representing vacuous information).
Distributivity of Focusing over Combination 

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

Transitivity of Focusing 

To focus an information on and , one may focus it to .

Idempotency 

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

Support 
such that

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

            

A two-sorted algebra satisfying these axioms is called an Information Algebra.

Order of information

A partial order of information can be introduced by defining if . This means that is less informative than if it adds no new information to . The semigroup is a semilattice relative to this order, i.e. . Relative to any domain (question) a partial order can be introduced by defining if . It represents the order of information content of and relative to the domain (question) .

Labeled information algebra

The pairs , where and such that form a labeled Information Algebra. More precisely, in the two-sorted algebra , the following operations are defined

Labeling 
Combination 
Projection 
            

Models of information algebras

Here follows an incomplete list of instances of information algebras:

Worked-out example: relational algebra

Let be a set of symbols, called attributes (or column names). For each let be a non-empty set, the set of all possible values of the attribute . For example, if , then could be the set of strings, whereas and are both the set of non-negative integers.

Let . An -tuple is a function so that and for each The set of all -tuples is denoted by . For an -tuple and a subset the restriction is defined to be the -tuple so that for all .

A relation over is a set of -tuples, i.e. a subset of . The set of attributes is called the domain of and denoted by . For the projection of onto is defined as follows:

The join of a relation over and a relation over is defined as follows:

As an example, let and be the following relations:

Then the join of and is:

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

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

semigroup 
and
transitivity 
If , then .
combination 
If and , then .
idempotency 
If , then .
support 
If , then .

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). For a book-length exposition on the topic see Pouly & Kohlas (2011).
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 
...
Compositional models
Such models may be defined within the framework of information algebras: https://arxiv.org/abs/1612.02587
Extended axiomatic foundations of information and valuation algebras
The concept of conditional independence is basic for information algebras and a new axiomatic foundation of information algebras, based on conditional independence, extending the old one (see above) is available: https://arxiv.org/abs/1701.02658

Historical Roots

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

References

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.