How to represent/implement the hypotheses class for a DAG learner

Question

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?

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$.