I am implementing a learner to learn a DAG model $G=\langle V,E\rangle$ where $V$ and $E$ represent both variables and dependencies respectively ( similar to Bayesian networks). Each variable $v\in V$ is associated with possible values (domain) $D_v$ and a function $\theta_v$.

I assume the learner knows the number of variables $n$ (i.e. vertices) and their possible values (domain). The goal is to find $E$ (dependencies) and $\theta_v$ for every variable $v$. I also assume there is a target function $c$ exist (the realizable case).

The hypothesis class is defined as the set of consistent hypotheses i.e. $H=\{h|\ h(x)=c(x)\} \forall x\in S$ where $S$ is set of examples seen so far.

I am trying to find a way to represent my hypotheses class. Initially, before receiving any example, it contains:

  1. all possible DAGs over $V$.
  2. all different combinations of $E$ as long as its acyclic.
  3. For every Graph $G$ generated from (1) and (2),all different function values over $G$.

Beside my naive representation, I do not know how to compute (1) precisely. To put my question in another way, how to represent the hypotheses class over Bayesian networks?

  • $\begingroup$ The number of DAGs with $n$ vertices is given in the DAG article on Wikipedia. $\endgroup$
    – alto
    Commented Nov 22, 2013 at 17:21
  • $\begingroup$ @alto thanks. I missed this when I was reading it.. definitely not going to enumerate this huge number $\endgroup$
    – seteropere
    Commented Nov 22, 2013 at 17:36

1 Answer 1


OK here is what I did:

I read about the most specific $ms$ and most general $mg$ hypotheses here. Intuitively, the hypotheses class is defined as these two hypotheses and anything in between. That is, for a hypothesis $h$ with DAG $G_h$, in order for $h$ to be in the hypotheses class $H$, it must be the case $G_{ms}\subseteq G_h \subseteq G_{mg}$.

For now, I used only $ms$ since my problem transformed to learning only one labelling $\{+\}$. Initially $G_{ms}=\emptyset$. Every example $x$ consist of pair of vertices $(x[a],x[b])$. if $\zeta(x)=\{+\}$ then there is an edge from $x[a]$ to $x[b]$ in $G_{ms}$ where $\zeta(x)$ is the labelling of $x$ according to the target function $h^*$.

After seeing $i$ examples $G_{ms}$ has $i$ edges. Any hypothesis $h$ with $G_{ms}\subset G_h$ is included in my hypotheses class $H$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.