Semiring induced valuation algebras: Exact and approximate local computation algorithms

J. Kohlas, N. Wilson

Research output: Contribution to journalArticle

26 Citations (Scopus)

Abstract

Local computation in join trees or acyclic hypertrees has been shown to be linked to a particular algebraic structure, called valuation algebra.There are many models of this algebraic structure ranging from probability theory to numerical analysis, relational databases and various classical and non-classical logics. It turns out that many interesting models of valuation algebras may be derived from semiring valued mappings. In this paper we study how valuation algebras are induced by semirings and how the structure of the valuation algebra is related to the algebraic structure of the semiring. In particular, c-semirings with idempotent multiplication induce idempotent valuation algebras and therefore permit particularly efficient architectures for local computation. Also important are semirings whose multiplicative semigroup is embedded in a union of groups. They induce valuation algebras with a partially defined division. For these valuation algebras, the well-known architectures for Bayesian networks apply. We also extend the general computational framework to allow derivation of bounds and approximations, for when exact computation is not feasible.
Original languageEnglish
Pages (from-to)1360-1399
Number of pages40
JournalArtificial Intelligence
Volume172
Issue number11
DOIs
Publication statusPublished - Jul 2008

Fingerprint

Algebra
logic
Trees (mathematics)
Bayesian networks
Numerical analysis
Group

Cite this

@article{797e6524e6684d259f114ace3c28418f,
title = "Semiring induced valuation algebras: Exact and approximate local computation algorithms",
abstract = "Local computation in join trees or acyclic hypertrees has been shown to be linked to a particular algebraic structure, called valuation algebra.There are many models of this algebraic structure ranging from probability theory to numerical analysis, relational databases and various classical and non-classical logics. It turns out that many interesting models of valuation algebras may be derived from semiring valued mappings. In this paper we study how valuation algebras are induced by semirings and how the structure of the valuation algebra is related to the algebraic structure of the semiring. In particular, c-semirings with idempotent multiplication induce idempotent valuation algebras and therefore permit particularly efficient architectures for local computation. Also important are semirings whose multiplicative semigroup is embedded in a union of groups. They induce valuation algebras with a partially defined division. For these valuation algebras, the well-known architectures for Bayesian networks apply. We also extend the general computational framework to allow derivation of bounds and approximations, for when exact computation is not feasible.",
author = "J. Kohlas and N. Wilson",
year = "2008",
month = "7",
doi = "10.1016/j.artint.2008.03.003",
language = "English",
volume = "172",
pages = "1360--1399",
journal = "Artificial Intelligence",
issn = "0004-3702",
publisher = "Elsevier",
number = "11",

}

Semiring induced valuation algebras: Exact and approximate local computation algorithms. / Kohlas, J.; Wilson, N.

In: Artificial Intelligence, Vol. 172, No. 11, 07.2008, p. 1360-1399.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Semiring induced valuation algebras: Exact and approximate local computation algorithms

AU - Kohlas, J.

AU - Wilson, N.

PY - 2008/7

Y1 - 2008/7

N2 - Local computation in join trees or acyclic hypertrees has been shown to be linked to a particular algebraic structure, called valuation algebra.There are many models of this algebraic structure ranging from probability theory to numerical analysis, relational databases and various classical and non-classical logics. It turns out that many interesting models of valuation algebras may be derived from semiring valued mappings. In this paper we study how valuation algebras are induced by semirings and how the structure of the valuation algebra is related to the algebraic structure of the semiring. In particular, c-semirings with idempotent multiplication induce idempotent valuation algebras and therefore permit particularly efficient architectures for local computation. Also important are semirings whose multiplicative semigroup is embedded in a union of groups. They induce valuation algebras with a partially defined division. For these valuation algebras, the well-known architectures for Bayesian networks apply. We also extend the general computational framework to allow derivation of bounds and approximations, for when exact computation is not feasible.

AB - Local computation in join trees or acyclic hypertrees has been shown to be linked to a particular algebraic structure, called valuation algebra.There are many models of this algebraic structure ranging from probability theory to numerical analysis, relational databases and various classical and non-classical logics. It turns out that many interesting models of valuation algebras may be derived from semiring valued mappings. In this paper we study how valuation algebras are induced by semirings and how the structure of the valuation algebra is related to the algebraic structure of the semiring. In particular, c-semirings with idempotent multiplication induce idempotent valuation algebras and therefore permit particularly efficient architectures for local computation. Also important are semirings whose multiplicative semigroup is embedded in a union of groups. They induce valuation algebras with a partially defined division. For these valuation algebras, the well-known architectures for Bayesian networks apply. We also extend the general computational framework to allow derivation of bounds and approximations, for when exact computation is not feasible.

U2 - 10.1016/j.artint.2008.03.003

DO - 10.1016/j.artint.2008.03.003

M3 - Article

VL - 172

SP - 1360

EP - 1399

JO - Artificial Intelligence

JF - Artificial Intelligence

SN - 0004-3702

IS - 11

ER -