maths

Over the past few days I have been reading two papers that contain quite a bit of maths. I have been going over both papers trying to understand what is going on. It is slow progress for me. The second of the two papers "factor graphs and the sum-product algorithm" is easier to understand and get a grasp of. So far essentially what the algorithm does is to construct a factor graph from a particular problem (which contains functions and variables) and then compute each variable as a product of all the factors. This is essentially computing a functions as a product of local functions (which take less operations to compute). This is what I understand is going on. Other then this, I have been working through a number of power analysis problems consisting of load factors, peak power, cost for generation etc.

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"