“Information algebra”的意思、由来-开放百科全书

词条

Information algebra

释义

Information and its operations
Axioms and definition
Order of information
Labeled information algebra
Models of information algebras
Worked-out example: relational algebra
Connections
Historical Roots
References

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 {{Harv|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:

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 {{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 cylindric 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 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

If , then .

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 {{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}}. For a book-length exposition on the topic see {{Harvtxt|Pouly|Kohlas|2011}}.

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

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

{{Citation | first1=J. | last1= Barwise | author1link=Jon Barwise | first2=J. | last2=Seligman | title=Information Flow: The Logic of Distributed Systems | year=1997 | publisher=Number 44 in Cambridge Tracts in Theoretical Computer Science, Cambridge University Press | place=Cambridge U.K. }}
{{Citation | first1=J.A. | last1=Bergstra | first2=J.| last2=Heering | first3=P. | last3=Klint | title=Module algebra | journal=J. Of the Assoc. For Computing Machinery|volume=73|issue=2|pages=335–372 | year=1990| doi=10.1145/77600.77621 }}
{{Citation | first1=S. | last1=Bistarelli | first2=H. | last2=Fargier | first3=U. | last3=Montanari | first4=F. | last4=Rossi | first5=T. |last5=Schiex | first6=G.|last6=Verfaillie| title=Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison | journal=Constraints |volume=4 |issue=3 | pages=199–240 | year=1999 | url=ftp://ftp.irit.fr/pub/IRIT/RPDMP/PapersFargier/valuatedItaliens.ps.gz| doi=10.1023/A:1026441215081 }}
{{Citation | first1=Stefano | last1=Bistarelli | first2=Ugo |last2=Montanari |first3=Francesca | last3=Rossi |title=Semiring-based constraint satisfaction and optimization | journal=Journal of the ACM |volume=44 |issue=2 | pages=201–236 | year=1997 | url=ftp://ftp.di.unipi.it/pub/Papers/rossi/jacm.ps.gz | doi=10.1145/256303.256306| citeseerx=10.1.1.45.5110 }}
{{Citation | first=Gerard R. Renardel | last=de Lavalette | chapter= Logical semantics of modularisation | editor=Egon Börger |editor2=Gerhard Jäger |editor3=Hans Kleine Büning |editor4=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=978-3-540-55789-0 |

chapter-url=http://citeseer.ist.psu.edu/484529.html}}

{{Citation | first=Luciano | last= Floridi | title=Outline of a theory of strongly semantic information | journal=Minds and Machines |volume=14 |issue=2 | pages=197–221 | year=2004 | doi=10.1023/b:mind.0000021684.50925.c9}}
{{Citation | first1=J. | last1=Groenendijk | first2=M. | last2=Stokhof | title=Studies on the Semantics of Questions and the Pragmatics of Answers | publisher=PhD thesis, Universiteit van Amsterdam | year=1984}}
{{Citation|first1=R. |last1=Haenni |first2=J. |last2=Kohlas |first3=N. |last3=Lehmann |chapter=Probabilistic argumentation systems |editor=J. Kohlas |editor2=S. Moral |title=Handbook of Defeasible Reasoning and Uncertainty Management Systems |pages=221–287 |publisher=Volume 5: Algorithms for Uncertainty and Defeasible Reasoning, Kluwer |place=Dordrecht |year=2000 |chapter-url=http://diuf.unifr.ch/tcs/publications/ps/hkl2000.pdf |deadurl=yes |archiveurl=https://web.archive.org/web/20050125040324/http://diuf.unifr.ch/tcs/publications/ps/hkl2000.pdf |archivedate=January 25, 2005 }}
{{Citation | first=Paul R. | last=Halmos | authorlink=Paul R. Halmos | title=An autobiography of polyadic algebras | journal=Logic Journal of the IGPL |volume=8 |issue=4 | pages=383–392 | year=2000 | doi=10.1093/jigpal/8.4.383 }}
{{Citation | first1=L. | last1=Henkin | author1link=Leon Henkin | first2=J. D. | last2=Monk | first3=A. | last3=Tarski | author3link=Alfred Tarski | title=Cylindric Algebras | publisher=North-Holland | place=Amsterdam | year= 1971 | isbn =978-0-7204-2043-2}}
{{Citation | first1=J. | last1=Jaffar | first2= M. J. | last2=Maher | title= Constraint logic programming: A survey | journal= J. Of Logic Programming |volume= 19/20 | pages=503–581 | year= 1994 | doi=10.1016/0743-1066(94)90033-7}}
{{Citation | first=J. | last=Kohlas | title= Information Algebras: Generic Structures for Inference | publisher=Springer-Verlag | year= 2003 | isbn = 978-1-85233-689-9}}
{{Citation | first1=J. | last1=Kohlas | first2= P.P. | last2=Shenoy | chapter=Computation in valuation algebras | editor=J. Kohlas |editor2=S. Moral | title=Handbook of Defeasible Reasoning and Uncertainty Management Systems, Volume 5: Algorithms for Uncertainty and Defeasible Reasoning |pages=5–39|publisher=Kluwer | place=Dordrecht | year= 2000}}
{{Citation|first1=J. |last1=Kohlas |first2=N. |last2=Wilson |title=Exact and approximate local computation in semiring-induced valuation algebras |publisher=Technical Report 06-06, Department of Informatics, University of Fribourg |year=2006 |url=http://diuf.unifr.ch/tcs/publications/ps/kohlaswilson06.pdf |deadurl=yes |archiveurl=https://web.archive.org/web/20060924230816/http://diuf.unifr.ch/tcs/publications/ps/kohlaswilson06.pdf |archivedate=September 24, 2006 }}
{{Citation | first1=K. G. | last1=Larsen | first2=G. |last2=Winskel | chapter=Using information systems to solve recursive domain equations effectively | editor=Gilles Kahn |editor2=David B. MacQueen |editor3=Gordon D. Plotkin | title=Semantics of Data Types, International Symposium, Sophia-Antipolis, France, June 27–29, 1984, Proceedings |volume=173 of Lecture Notes in Computer Science | pages=109–129 | location=Berlin | year= 1984 | publisher=Springer}}
{{Citation | first1=S. L. | last1= Lauritzen |first2=D. J.|last2=Spiegelhalter | title=Local computations with probabilities on graphical structures and their application to expert systems | journal= Journal of the Royal Statistical Society, Series B |volume= 50 | pages=157–224 | year= 1988}}
{{citation|first1=Marc |last1=Pouly | first2=Jürg |last2=Kohlas|title=Generic Inference: A Unifying Theory for Automated Reasoning|year=2011|publisher=John Wiley & Sons|isbn=978-1-118-01086-0}}
{{Citation | first=Dana S. | last= Scott | authorlink=Dana Scott | title= Outline of a mathematical theory of computation | publisher=Technical Monograph PRG–2, Oxford University Computing Laboratory, Programming Research Group | year=1970}}
{{Citation | first=D.S. | last=Scott | chapter=Domains for denotational semantics | editor= M. Nielsen |editor2=E.M. Schmitt | title= Automata, Languages and Programming | pages= 577–613 | publisher= Springer | year= 1982}}
{{Citation | first=G. | last= Shafer | title=An axiomatic study of computation in hypertrees | publisher=Working Paper 232, School of Business, University of Kansas | year= 1991}}
{{Citation | first1=P. P. | last1=Shenoy | first2=G. | last2=Shafer | chapter=Axioms for probability and belief-function proagation | editor=Ross D. Shachter |editor2=Tod S. Levitt |editor3=Laveen N. Kanal |editor4=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= 978-0-444-88650-7| doi=10.1016/B978-0-444-88650-7.50019-6 }}
{{Citation | first1=Nic | last1=Wilson |first2= Jérôme | last2= Mengin | chapter=Logical deduction using the local computation framework | editor=Anthony Hunter |editor2=Simon Parsons | title=Symbolic and Quantitative Approaches to Reasoning and Uncertainty, European Conference, 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 = 978-3-540-66131-3 | chapter-url = http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=1638&spage=0386}}

2 : Information theory|Abstract algebra

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。