Elias, I am not aware of a comprehensive survey of the complexity results for Bayesian network inference. For the general problem, Roth's paper ( http://citeseer.nj.nec.com/roth96hardnes.html ) provides the primary result both for exact and approximate inference ( It is #P complete, and approximating it within subexponential relative error is NP-hard ).
From there, the problem becomes finding classes of networks which are or are not tractable for exact or approximate inference. For variable elimination style algorithms (including shenoy's framework) the primary parameter of interest is the treewidth of the network. They have time complexity that is linear in the size of the variables, and exponential in the treewidth. I am not sure the origin of this analysis, as it has been used in a variety of situations. Here is a paper by Dechter and Fattah that gives the standard complexity overview, and addresses both the time and space aspects of the algorithms ( http://citeseer.nj.nec.com/dechter00topological.html). There are other algorithms that are capable for other classes defined by parameterizations that are incomparable with treewidth. The other examples I am aware of: Cutset conditioning is exponential only in the cutset size( see Pearl's book). A randomized polynomial time algorithm exists for arbitrarily accurate approximate inference on the class of networks with parameters bounded away from 0 regardless of the network topology ( http://citeseer.nj.nec.com/dagum97optimal.html). If you are looking for general (i.e. not parameterized by treewidth) lower bounds for variable elimination type algorithms, I am not aware of any published versions, but the proof of an exponential lower bound is fairly straight forward since graphs with constant degree and BigTheta(n) treewidth exist. Hope that helps, J.D. Park On Wednesday, July 31, 2002, at 07:48 AM, Elias Biris wrote: > > Hello, > > I am looking for a comprehensive study of the complexity issues > regarding propagation of evidence and probabilities updating in Bayesian > networks. I am also interested in material that provides any results of > a complexity study of the fusion/propagation involved in valuation-based > networks (i.e. using Shenoy's framework) > > Your help will be very much appreciated. > > Kind regards, > > Elias Biris >
