I recently started studying bayesian networks and I am now implementing an exact inference algorithm: enumeration. I am aware of the complexity and inefficiency of this method but I want to fully understand it.
As far as I know there are three basic 'steps':
- Use Bayes Rule on query / evidence variables.
- Use summation for hidden variables.
- Calculate joint distribution.
I've tried a recursive approach as suggested in most documentation of the topic, here's the algorithm I'm using (with python):
''' bayesnet is an instance of a class that hold a bayes net queryVars is a list of tuples (varname, boolean) to describe the state of a variable, eg. ('B', True) evidenceVars is a list of tuples (varname, boolean) ''' def enumerate_method(bayesnet, queryVars, evidenceVars = ): #Check evidence vars to apply bayes rule if len(evidenceVars): return enumerate_method(queryVars + evidenceVars) / enumerate_method(evidenceVars) #Check if there are hidden variables left given the query variables if len(bayesnet.hiddenVariables(queryVars)): #For every hidden variable for hiddenvar in bayesnet.hiddenVariables(queryVars): return enumerate_method(bayesnet, queryVars + [(hiddenvar, True)]) + enumerate_method(bayesnet, queryVars + [(hiddenvar, False)]) #Calculate joint distribution of queryVars? return bayesnet.joint(queryVars)
I am still unsure of how to implement the joint distribution calculation. My BayesNet class stores, for each variable, a name, a list of parents and a list of tuples with the probability given its parents. The bayes network is fully described.
I guess I have to use the chain rule, but I have trouble with that as it brings new expressions with evidence variables that I do not have.
Am I moving on the right direction? If so, could you provide a suggestion on how to calculate the joint distribution.