<p>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? </p>

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

<hr>

<ul>
<li><p>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.  </p></li>
<li><p>I would be equally well helped to know if there are such results known with Marokov Random Fields or Factor Graphs.  </p></li>
</ul>

CC BY-SA 3.0
2016-04-08T23:36:26.023Z
It is NP-hard to compute marginals of nodes in graphical models.
Kaveh
CC BY-SA 3.0
2016-04-09T07:11:08.437Z
@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.)
Student
CC BY-SA 3.0
2016-04-09T07:50:33.110Z
@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, https://arxiv.org/ftp/arxiv/papers/1206/1206.3240.pdf ?) But isn't this question wholly different from what I am asking?
Student
<graph-theory><graph-algorithms><np-hardness><approximation-hardness><graph-colouring>
About complexity of recovering or learning Bayesian networks
Student
# About complexity of recovering or learning Bayesian networks

(Asked by: username_0 on 2016-04-08)

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.

**Tags:** graph-theory, graph-algorithms, np-hardness, approximation-hardness, graph-colouring
> **Comments:**
> **username_1**: It is NP-hard to compute marginals of nodes in graphical models.  
> **username_0**: @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.)  
> **username_0**: @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, https://arxiv.org/ftp/arxiv/papers/1206/1206.3240.pdf ?) But isn't this question wholly different from what I am asking?  

---

## 0 answers

