# What is the number of free parameters for a directed acyclic graph?

I am trying to use Maximum Likelihood Estimation to learn the structure of a DAG, G.

How is the number of free parameters of G calculated to compare the complexity of different graphical models?

Is it based on one of the following, or something else?

• Number of edges in the graph
• Maximum number of possible edges in the graph
• Maximum number of parents (children)
• What do you mean by "number of free parameters of G"? Do you mean the number of parameters in the sampling distribution of the data for a particular G? Apr 21, 2011 at 12:54
• I feel obligated to tell you that learning the optimal structure of a Bayesian Network (which is a DAG) is in NP (en.wikipedia.org/wiki/NP_%28complexity%29) and hence not feasible. Does this question has any statistical background / aim or it is "just" a exercise in Combinatorics ? Apr 21, 2011 at 13:10
• @steffen: It is certainly feasible if the number of vertices p is relatively small (p<6 can be done by simple enumeration, and I think some of the more recent optimisation algorithms work for p<50). With a few restrictions on the type of graphs (say, limiting the number of parents of any vertex), you can easily step it up to even larger graphs. Apr 21, 2011 at 13:21
• @Simon With the introduction of restrictions, how can you be sure that the OPTIMAL structure will be found ? Nevertheless, I am interested in such optimisation algorithms ;) ... can you provide a link ? Apr 21, 2011 at 13:27
• @steffen: Well, it would be would be optimal from the class you consider. How do you know that any DAG is an appropriate model? (all models being wrong etc.) As far as algorithms go, the PC algorithm and its variants seems to be what all the cool kids are using these days. Apr 21, 2011 at 13:41

The answer depends on your likelihood for the data $X$

1) Joint Gaussian

You can fit the model by sequentially fitting the conditional distribution of each node $v$ given its parents $\mathrm{pa}(v)$, in this case:

$X_v | X_{\mathrm{pa}(v)} \sim N\big(\mu_v + \beta_v^\top [X_{\mathrm{pa}(v)} - \mu_{\mathrm{pa}(v)}], \sigma_v^2 \big)$

Then for each node you need 1 parameter $\mu_v$ for the mean, 1 parameter $\sigma_v^2$ for the conditional variance and a vector $\beta_v$ of length $|\mathrm{pa}(v)|$.

So the total number of parameters needed for a graph $G=(V,E)$ is $2|V| + |E|$.

2) Discrete

Suppose the variable $X_v$ for each node $v$ is discrete with $n_v$ possible outcomes. Then for each possible outcome in the parent space, you require $n_v-1$ parameters. So for each node, you will need:

$(n_v-1) \prod_{u \in \mathrm{pa}(v)} n_u$

parameters. If each node has 2 possible outcomes, you will need:

$\sum_{v} 2^{|\mathrm{pa}(v)|}$

total parameters, unless you make some simplifying assumptions, such as proportional-odds (i.e. logistic regression).

• In the discrete case, how do you treat the top node with no parents? Jun 5, 2018 at 19:26
• The product over the empty set is 1, so you would need n_v - 1 parameters (i.e. an n_v simplex) Jun 6, 2018 at 4:06