Are there complexity theoretic results about recoverability or learnability of the marginals (of the source vertices) and the conditionals (along each of the edges) of a Bayesian network from having access to some subset of the vertices?

Are there at least known conditions when this is provably impossible or when some hardness result has been proven?

  • I am typically assuming that the random variables (one at each vertex) are mapping the same sample space into some finite space which could be different for each random variable/vertex. I would equally well want to know if there are results with continuous distributions.

  • I would be equally well helped to know if there are such results known with Marokov Random Fields or Factor Graphs.

  • $\begingroup$ It is NP-hard to compute marginals of nodes in graphical models. $\endgroup$ – Kaveh Apr 8 '16 at 23:36
  • $\begingroup$ @Kaveh Thanks! Any reference to this result? (I do know of various special classes of Bayesian networks where we can do this computation in polynomial time. If as you say the general question is NP-hard, I wonder if there is a classification statement about when we can do this and when it is impossible.) $\endgroup$ – Anirbit Apr 9 '16 at 7:11
  • $\begingroup$ @Kaveh Just wondering, aren't you referring to the NP-hardness of "inference" that is the question of finding the marginal of some vertex given the joint distribution? (like say what is discussed here, arxiv.org/ftp/arxiv/papers/1206/1206.3240.pdf ?) But isn't this question wholly different from what I am asking? $\endgroup$ – Anirbit Apr 9 '16 at 7:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.