Representing Graphical Model Factors in Numpy
I've been working a bit with graphical models lately for my research. For a while I was using a library called pgmpy for their implementations of factor arithmetic and inference algorithms. However, as my research is progressing I am needing more control than what pgmpy offers, so I decided to re-implement and extend the algorithms that I needed. If you are in a similar situation and are finding yourself implementing your own graphical models algorithms, this post is for you.
In the setting I am working in, I have a Markov random field model where there are only a small number of variables (no more than a few dozen, often much less). However, each variable can take on a possibly large number of categorical values and the graph may contain relatively large cliques that make exact inference computationally challenging (although still possible).
Suppose the model has $d$ variables and variable $i$ can take on $n_i$ possible values. Usually a factor defined over $k$ variables can be represented as a $k$ dimensional array. However, if we instead represent the factor as a $d$ dimensional array, we can exploit built-in functionality of numpy array arithmetic to simplify the factor math. The new factor representation has the size of each dimension being $1$ (if it is not in the factor) or $n_i$ (if it is in the factor).
When we want to multiply two factors, say, $AB$ and $AC$ we can just write $ABC = AB * AC$ and numpy will automatically broadcast these arrays to the desired compatible shape. If the factors are in log space, we can just write $ ABC = AB+AC $ and the same thing happens with addition. The marginalize a factor, we can just call the function
By using this idea I was able to avoid solving the annoying problem of aligning factors before adding or multiplying them. Thus, the code is cleaner and there is no overhead for aligning so the code is more efficient.
In the setting I am working in, I have a Markov random field model where there are only a small number of variables (no more than a few dozen, often much less). However, each variable can take on a possibly large number of categorical values and the graph may contain relatively large cliques that make exact inference computationally challenging (although still possible).
Suppose the model has $d$ variables and variable $i$ can take on $n_i$ possible values. Usually a factor defined over $k$ variables can be represented as a $k$ dimensional array. However, if we instead represent the factor as a $d$ dimensional array, we can exploit built-in functionality of numpy array arithmetic to simplify the factor math. The new factor representation has the size of each dimension being $1$ (if it is not in the factor) or $n_i$ (if it is in the factor).
When we want to multiply two factors, say, $AB$ and $AC$ we can just write $ABC = AB * AC$ and numpy will automatically broadcast these arrays to the desired compatible shape. If the factors are in log space, we can just write $ ABC = AB+AC $ and the same thing happens with addition. The marginalize a factor, we can just call the function
np.sum(ABC, axis=ax, keepdims=True)
and this will keep the dimensionality of the factor, so that it can be used for downstream factor computations. We can replace np.sum
with scipy.misc.logsumexp
if we are working in log space. By using this idea I was able to avoid solving the annoying problem of aligning factors before adding or multiplying them. Thus, the code is cleaner and there is no overhead for aligning so the code is more efficient.
Final Four 2018
ReplyDeleteFinal Four
NCAA Final Four 2018
NCAA Final Four
NCAA Tournament 2018 Final Four
NCAA Tournament Final Four 2018
March Madness 2018 Final Four
March Madness Final Four 2018
Final Four 2018 Live
Final Four 2018 Live Stream
Final Four Live
Final Four Live Stream
NCAA Final Four Live
Men's Final Four Championship
Men's Final Four Championship 2018
Men's Final Four 2018
NCAA Men's Final Four 2018
Basketball Men's Final Four 2018
Basketball Men's Final Four
NCAA Final Four Live Stream
NCAA Final Four 2018 Live
NCAA Final Four 2018 Live Stream
https://finalfour2018.co/
https://finalfour2018.co/
Watch Final Four Online
Watch Final Four Live
Watch Final Four 2018 Online
Watch Final Four 2018 Live
Watch Final Four Live Stream
Final Four 2018
Final Four
NCAA Final Four 2018
NCAA Final Four
Final Four 2018 Live
Final Four 2018 Live Stream
Final Four Live
Final Four Live Stream
NCAA Final Four Live
Men's Final Four Championship
Men's Final Four Championship 2018
Men's Final Four 2018
NCAA Men's Final Four 2018
Basketball Men's Final Four 2018
Basketball Men's Final Four
https://four-final.ca/
https://four-final.ca/