The generalized distributive law (GDL) is a generalization of the distributive property which gives rise to a general message passing algorithm. It is a synthesis of the work of many authors in the information theory, digital communications, signal processing, statistics, and artificial intelligence communities. The law and algorithm were introduced in a semi-tutorial by Srinivas M. Aji and Robert J. McEliece with the same title.
Introduction "The distributive law in mathematics is the law relating the operations of multiplication and addition, stated symbolically, a ∗ ( b + c ) = a ∗ b + a ∗ c {\displaystyle a*(b+c)=a*b+a*c} ; that is, the monomial factor a {\displaystyle a} is distributed, or separately applied, to each term of the binomial factor b + c {\displaystyle b+c} , resulting in the product a ∗ b + a ∗ c {\displaystyle a*b+a*c} " – Britannica. As it can be observed from the definition, application of distributive law to an arithmetic expression reduces the number of operations in it. In the previous example the total number of operations reduced from three (two multiplications and an addition in a ∗ b + a ∗ c {\displaystyle a*b+a*c} ) to two (one multiplication and one addition in a ∗ ( b + c ) {\displaystyle a*(b+c)} ). Generalization of distributive law leads to a large family of fast algorithms. This includes the FFT and Viterbi algorithm. This is explained in a more formal way in the example below:
α ( a , b ) = d e f ∑ c , d , e ∈ A f ( a , c , b ) g ( a , d , e ) {\displaystyle \alpha (a,\,b){\stackrel {\mathrm {def} }{=}}\displaystyle \sum \limits _{c,d,e\in A}f(a,\,c,\,b)\,g(a,\,d,\,e)} where f ( ⋅ ) {\displaystyle f(\cdot )} and g ( ⋅ ) {\displaystyle g(\cdot )} are real-valued functions, a , b , c , d , e ∈ A {\displaystyle a,b,c,d,e\in A} and | A | = q {\displaystyle |A|=q} (say) Here we are "marginalizing out" the independent variables ( c {\displaystyle c} , d {\displaystyle d} , and e {\displaystyle e} ) to obtain the result. When we are calculating the computational complexity, we can see that for each q 2 {\displaystyle q^{2}} pairs of ( a , b ) {\displaystyle (a,b)} , there are q 3 {\displaystyle q^{3}} terms due to the triplet ( c , d , e ) {\displaystyle (c,d,e)} which needs to take part in the evaluation of α ( a , b ) {\displaystyle \alpha (a,\,b)} with each step having one addition and one multiplication. Therefore, the total number of computations needed is 2 ⋅ q 2 ⋅ q 3 = 2 q 5 {\displaystyle 2\cdot q^{2}\cdot q^{3}=2q^{5}} . Hence the asymptotic complexity of the above function is O ( n 5 ) {\displaystyle O(n^{5})} . If we apply the distributive law to the RHS of the equation, we get the following:
α ( a , b ) = d e f ∑ c ∈ A f ( a , c , b ) ⋅ ∑ d , e ∈ A g ( a , d , e ) {\displaystyle \alpha (a,\,b){\stackrel {\mathrm {def} }{=}}\displaystyle \sum \limits _{c\in A}f(a,\,c,\,b)\cdot \sum _{d,\,e\in A}g(a,\,d,\,e)}
This implies that α ( a , b ) {\displaystyle \alpha (a,\,b)} can be described as a product α 1 ( a , b ) ⋅ α 2 ( a ) {\displaystyle \alpha _{1}(a,\,b)\cdot \alpha _{2}(a)} where α 1 ( a , b ) = d e f ∑ c ∈ A f ( a , c , b ) {\displaystyle \alpha _{1}(a,b){\stackrel {\mathrm {def} }{=}}\displaystyle \sum \limits _{c\in A}f(a,\,c,\,b)} and α 2 ( a ) = d e f ∑ d , e ∈ A g ( a , d , e ) {\displaystyle \alpha _{2}(a){\stackrel {\mathrm {def} }{=}}\displaystyle \sum \limits _{d,\,e\in A}g(a,\,d,\,e)}
Now, when we are calculating the computational complexity, we can see that there are q 3 {\displaystyle q^{3}} additions in α 1 ( a , b ) {\displaystyle \alpha _{1}(a,\,b)} and α 2 ( a ) {\displaystyle \alpha _{2}(a)} each and there are q 2 {\displaystyle q^{2}} multiplications when we are using the product α 1 ( a , b ) ⋅ α 2 ( a ) {\displaystyle \alpha _{1}(a,\,b)\cdot \alpha _{2}(a)} to evaluate α ( a , b ) {\displaystyle \alpha (a,\,b)} . Therefore, the total number of computations needed is q 3 + q 3 + q 2 = 2 q 3 + q 2 {\displaystyle q^{3}+q^{3}+q^{2}=2q^{3}+q^{2}} . Hence the asymptotic complexity of calculating α ( a , b ) {\displaystyle \alpha (a,b)} reduces to O ( n 3 ) {\displaystyle O(n^{3})} from O ( n 5 ) {\displaystyle O(n^{5})} . This shows by an example that applying distributive law reduces the computational complexity which is one of the good features of a "fast algorithm".
History
Some of the problems that used distributive law to solve can be grouped as follows:
Decoding algorithms: A GDL like algorithm was used by Gallager's for decoding low density parity-check codes. Based on Gallager's work Tanner introduced the Tanner graph and expressed Gallagers work in message passing form. The tanners graph also helped explain the Viterbi algorithm. It is observed by Forney that Viterbi's maximum likelihood decoding of convolutional codes also used algorithms of GDL-like generality. Forward–backward algorithm: The forward backward algorithm helped as an algorithm for tracking the states in the Markov chain. And this also was used the algorithm of GDL like generality Artificial intelligence: The notion of junction trees has been used to solve many problems in AI. Also the concept of bucket elimination used many of the concepts.
The MPF problem MPF or marginalize a product function is a general computational problem which as special case includes many classical problems such as computation of discrete Hadamard transform, maximum likelihood decoding of a linear code over a memory-less channel, and matrix chain multiplication. The power of the GDL lies in the fact that it applies to situations in which additions and multiplications are generalized. A commutative semiring is a good framework for explaining this behavior. It is defined over a set K {\displaystyle K} with operators " + {\displaystyle +} " and " . {\displaystyle .} " where ( K , + ) {\displaystyle (K,\,+)} and ( K , . ) {\displaystyle (K,\,.)} are a commutative monoids and the distributive law holds. Let p 1 , … , p n {\displaystyle p_{1},\ldots ,p_{n}} be variables such that p 1 ∈ A 1 , … , p n ∈ A n {\displaystyle p_{1}\in A_{1},\ldots ,p_{n}\in A_{n}} where A {\displaystyle A} is a finite set and | A i | = q i {\displaystyle |A_{i}|=q_{i}} . Here i = 1 , … , n {\displaystyle i=1,\ldots ,n} . If S = { i 1 , … , i r } {\displaystyle S=\{i_{1},\ldots ,i_{r}\}} and S ⊂ { 1 , … , n } {\displaystyle S\,\subset \{1,\ldots ,n\}} , let
A S = A i 1 × ⋯ × A i r {\displaystyle A_{S}=A_{i_{1}}\times \cdots \times A_{i_{r}}} , p S = ( p i 1 , … , p i r ) {\displaystyle p_{S}=(p_{i_{1}},\ldots ,p_{i_{r}})} ,
q S = | A S | {\displaystyle q_{S}=|A_{S}|} , A = A 1 × ⋯ × A n {\displaystyle \mathbf {A} =A_{1}\times \cdots \times A_{n}} , and
p = { p 1 , … , p n } {\displaystyle \mathbf {p} =\{p_{1},\ldots ,p_{n}\}}
Let S = { S j } j = 1 M {\displaystyle S=\{S_{j}\}_{j=1}^{M}} where S j ⊂ { 1 , . . . , n } {\displaystyle S_{j}\subset \{1,...\,,n\}} . Suppose a function is defined as α i : A S i → R {\displaystyle \alpha _{i}:A_{S_{i}}\rightarrow R} , where R {\displaystyle R} is a commutative semiring. Also, p S i {\displaystyle p_{S_{i}}} are named the local domains and α i {\displaystyle \alpha _{i}} as the local kernels. Now the global kernel β : A → R {\displaystyle \beta :\mathbf {A} \rightarrow R} is defined as: β ( p 1 , . . . , p n ) = ∏ i = 1 M α ( p S i ) {\displaystyle \beta (p_{1},...\,,p_{n})=\prod _{i=1}^{M}\alpha (p_{S_{i}})}
Definition of MPF problem: For one or more indices i = 1 , . . . , M {\displaystyle i=1,...\,,M} , compute a table of the values of S i {\displaystyle S_{i}} -marginalization of the global kernel β {\displaystyle \beta } , which is the function β i : A S i → R {\displaystyle \beta _{i}:A_{S_{i}}\rightarrow R} defined as β i ( p S i ) = ∑ p S i c ∈ A S i c β ( p ) {\displaystyle \beta _{i}(p_{S_{i}})\,=\displaystyle \sum \limits _{p_{S_{i}^{c}}\in A_{S_{i}^{c}}}\beta (p)}
Here S i c {\displaystyle S_{i}^{c}} is the complement of S i {\displaystyle S_{i}} with respect to { 1 , . . . , n } {\displaystyle \mathbf {\{} 1,...\,,n\}} and the β i ( p S i ) {\displaystyle \beta _{i}(p_{S_{i}})} is called the i t h {\displaystyle i^{th}} objective function, or the objective function at S i {\displaystyle S_{i}} . It can observed that the computation of the i t h {\displaystyle i^{th}} objective function in the obvious way needs M q 1 q 2 q 3 ⋯ q n {\displaystyle Mq_{1}q_{2}q_{3}\cdots q_{n}} operations. This is because there are q 1 q 2 ⋯ q n {\displaystyle q_{1}q_{2}\cdots q_{n}} additions and ( M − 1 ) q 1 q 2 . . . q n {\displaystyle (M-1)q_{1}q_{2}...q_{n}} multiplications needed in the computation of the i th {\displaystyle i^{\text{th}}} objective function. The GDL algorithm which is explained in the next section can reduce this computational complexity. The following is an example of the MPF problem. Let p 1 , p 2 , p 3 , p 4 , {\displaystyle p_{1},\,p_{2},\,p_{3},\,p_{4},} and p 5 {\displaystyle p_{5}} be variables such that p 1 ∈ A 1 , p 2 ∈ A 2 , p 3 ∈ A 3 , p 4 ∈ A 4 , {\displaystyle p_{1}\in A_{1},p_{2}\in A_{2},p_{3}\in A_{3},p_{4}\in A_{4},} and p 5 ∈ A 5 {\displaystyle p_{5}\in A_{5}} . Here M = 4 {\displaystyle M=4} and S = { { 1 , 2 , 5 } , { 2 , 4 } , { 1 , 4 } , { 2 } } {\displaystyle S=\{\{1,2,5\},\{2,4\},\{1,4\},\{2\}\}} . The given functions using these variables are f ( p 1 , p 2 , p 5 ) {\displaystyle f(p_{1},p_{2},p_{5})} and g ( p 2 , p 4 ) {\displaystyle g(p_{2},p_{4})} and we need to calculate α ( p 1 , p 4 ) {\displaystyle \alpha (p_{1},\,p_{4})} and β ( p 2 ) {\displaystyle \beta (p_{2})} defined as:
α ( p 1 , p 4 ) = ∑ p 2 ∈ A 2 , p 3 ∈ A 3 , p 5 ∈ A 5 f ( p 1 , p 2 , p 5 ) ⋅ g ( p 2 , p 4 ) {\displaystyle \alpha (p_{1},\,p_{4})=\displaystyle \sum \limits _{p_{2}\in A_{2},\,p_{3}\in A_{3},\,p_{5}\in A_{5}}f(p_{1},\,p_{2},\,p_{5})\cdot g(p_{2},\,p_{4})}
β ( p 2 ) = ∑ p 1 ∈ A 1 , p 3 ∈ A 3 , p 4 ∈ A 4 , p 5 ∈ A 5 f ( p 1 , p 2 , p 5 ) ⋅ g ( p 2 , p 4 ) {\displaystyle \beta (p_{2})=\sum \limits _{p_{1}\in A_{1},\,p_{3}\in A_{3},\,p_{4}\in A_{4},\,p_{5}\in A_{5}}f(p_{1},\,p_{2},\,p_{5})\cdot g(p_{2},\,p_{4})}
Here local domains and local kernels are defined as follows:
where α ( p 1 , p 4 ) {\displaystyle \alpha (p_{1},p_{4})} is the 3 r d {\displaystyle 3^{rd}} objective function and β ( p 2 ) {\displaystyle \beta (p_{2})} is the 4 t h {\displaystyle 4^{th}} objective function. Consider another example where p 1 , p 2 , p 3 , p 4 , r 1 , r 2 , r 3 , r 4 ∈ { 0 , 1 } {\displaystyle p_{1},p_{2},p_{3},p_{4},r_{1},r_{2},r_{3},r_{4}\in \{0,1\}} and f ( r 1 , r 2 , r 3 , r 4 ) {\displaystyle f(r_{1},r_{2},r_{3},r_{4})} is a real valued function. Now, we shall consider the MPF problem where the commutative semiring is defined as the set of real numbers with ordinary addition and multiplication and the local domains and local kernels are defined as follows:
Now since the global kernel is defined as the product of the local kernels, it is
F ( p 1 , p 2 , p 3 , p 4 , r 1 , r 2 , r 3 , r 4 ) = f ( p 1 , p 2 , p 3 , p 4 ) ⋅ ( − 1 ) p 1 r 1 + p 2 r 2 + p 3 r 3 + p 4 r 4 {\displaystyle F(p_{1},p_{2},p_{3},p_{4},r_{1},r_{2},r_{3},r_{4})=f(p_{1},p_{2},p_{3},p_{4})\cdot (-1)^{p_{1}r_{1}+p_{2}r_{2}+p_{3}r_{3}+p_{4}r_{4}}}
and the objective function at the local domain p 1 , p 2 , p 3 , p 4 {\displaystyle p_{1},p_{2},p_{3},p_{4}} is
F ( p 1 , p 2 , p 3 , p 4 ) = ∑ r 1 , r 2 , r 3 , r 4 f ( r 1 , r 2 , r 3 , r 4 ) ⋅ ( − 1 ) p 1 r 1 + p 2 r 2 + p 3 r 3 + p 4 r 4 . {\displaystyle F(p_{1},p_{2},p_{3},p_{4})=\displaystyle \sum \limits _{r_{1},r_{2},r_{3},r_{4}}f(r_{1},r_{2},r_{3},r_{4})\cdot (-1)^{p_{1}r_{1}+p_{2}r_{2}+p_{3}r_{3}+p_{4}r_{4}}.}
This is the Hadamard transform of the function f ( ⋅ ) {\displaystyle f(\cdot )} . Hence we can see that the computation of Hadamard transform is a special case of the MPF problem. More examples can be demonstrated to prove that the MPF problem forms special cases of many classical problem as explained above whose details can be found at
GDL: an algorithm for solving the MPF problem If one can find a relationship among the elements of a given set S {\displaystyle S} , then one can solve the MPF problem basing on the notion of belief propagation which is a special use of "message passing" technique. The required relationship is that the given set of local domains can be organised into a junction tree. In other words, we create a graph theoretic tree with the elements of S {\displaystyle S} as the vertices of the tree T {\displaystyle T} , such that for any two arbitrary vertices say v i {\displaystyle v_{i}} and v j {\displaystyle v_{j}} where i ≠ j {\displaystyle i\neq j} and there exists an edge between these two vertices, then the intersection of corresponding labels, viz S i ∩ S j {\displaystyle S_{i}\cap S_{j}} , is a subset of the label on each vertex on the unique path from v i {\displaystyle v_{i}} to v j {\displaystyle v_{j}} . For example, Example 1: Consider the following nine local domains:
{ p 2 } {\displaystyle \{p_{2}\}}
{ p 3 , p 2 } {\displaystyle \{p_{3},p_{2}\}}
{ p 2 , p 1 } {\displaystyle \{p_{2},p_{1}\}}
{ p 3 , p 4 } {\displaystyle \{p_{3},p_{4}\}}
{ p 3 } {\displaystyle \{p_{3}\}}
{ p 1