1. The sum-product algorithm: algebraic independence and computational aspects
- Creator:
- Malvestuto, Francesco M.
- Format:
- bez média and svazek
- Type:
- model:article and TEXT
- Subject:
- sum-product algorithm, distributive law, acyclic set system, and junction tree
- Language:
- English
- 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.
- Rights:
- http://creativecommons.org/publicdomain/mark/1.0/ and policy:public