The sum-product algorithm: algebraic independence and computational aspects

Title:

The sum-product algorithm: algebraic independence and computational aspects

Creator:

Malvestuto, Francesco M.

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:10094798-8b54-4431-8fa0-b9f972e675b0
uuid:10094798-8b54-4431-8fa0-b9f972e675b0

Subject:

sum-product algorithm, distributive law, acyclic set system, and junction tree

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

The sum-product algorithm is a well-known procedure for marginalizing an "acyclic'' product function whose range is the ground set of a commutative semiring. The algorithm is general enough to include as special cases several classical algorithms developed in information theory and probability theory. We present four results. First, using the sum-product algorithm we show that the variable sets involved in an acyclic factorization satisfy a relation that is a natural generalization of probability-theoretic independence. Second, we show that for the Boolean semiring the sum-product algorithm reduces to a classical algorithm of database theory. Third, we present some methods to reduce the amount of computation required by the sum-product algorithm. Fourth, we show that with a slight modification the sum-product algorithm can be used to evaluate a general sum-product expression.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

[4]-22

Source:

Kybernetika | 2013 Volume:49 | Number:1

Harvested from:

CDK

Metadata only:

false