maths

Today I have been trawling through the paper "The Generalized Distributive Law" to understand the maths behind the Max-Sum algorithm. The GDL is based on the "humble" distributive law [i.e ab + ac = a(b + c)] but generalised to other things, such as trees. The idea is that you decompose a problem into a set of smaller problems such that the complexity to solve the smaller problems is less than the complexity to solve the original function. Example f(x1, x2, x3), the complexity to solve this is dependant on all the variables, whereas if f(x1, x2, x3) = f(x1, x2) + f(x2, x3) the complexity is dependant on the maximum number of variables in the functions (in this case 2) therefore reducing the number of operations required to solve the problem. Ruben helped me to understand the basic concept of the GDL algorithm. The paper did contain some difficult maths which I got the general gist of, however I will need to go over this in more detail. TODO (tomorrow) : Read the second paper that Max-Sum is based on "Factor Graphs and the Sum-Product Algorithm"