# Formula for number of parameters in an undirected graphical (probability) model

I have googled endlessly, and I cannot find it. Can anyone point me to a reference that gives a way to calculate the number of parameters in an undirected Graphical Model?

Adapting from the similar formula for Bayes nets, this is my guess: if we have variables $1 \ldots k$ where variable $i$ has $d_i$ possible values, and $n(i)$ is the set of vertices adjacent to $i$ in the independence graph, then the number of parameters would be

$\Sigma_{i=1}^{k}(d_i - 1) \Pi_{j \in n(i)}d_j$.

Can anyone verify this, and if it's wrong, point me to a correct solution?

I'm trying to calculate the AIC and BIC scores for graphical models, but to do that, I need the number of parameters each has.

EDIT: To clarify, for graphical model I'm talking about the sub-class of log-linear discrete probability distributions. They're also called Markov Networks. See the Wikipedia article.

The idea is, you have $n$ discrete variables $v_1, \ldots, v_k$, where $p(v_1 = x_1, \ldots, v_k = x_k) = u_{1}(x_1) \cdot \ldots \cdot u_{1,2,\ldots,k}(x_1, x_2, \ldots, x_k)$ i.e. there is a term for each combination of variables, and the probability is just the product of those terms.

Some of those terms will be $0$, depending on which variables are independent. The model is heirchical if it's , meaning that if a set of variables has non-zero $u$-term, then all of its subsets have non-zero u-terms. The model is graphical if it's heirarchical, and it's specified entirely by the independence graph (where $v_i$ and $v_j$ have an edge iff they are not conditionally independent given the other nodes.)

The number of the parameters is the number of non-zero $u$-terms. It's easy for the binary case, where each $u$ can just be a number, but when there are more than 2 possible values for each variable, it's more complicated, since you need a parameter for each value combination.

• What do you mean by "the number of parameters"? What is a "graphical model" for you? – Yuval Filmus Dec 10 '14 at 16:39
• Edited to clarify, hopefully. – jmite Dec 10 '14 at 16:54
• Perhaps I'm just confused (which is likely the case), but why would the number of parameters be dependent on the range of values per variable? Does $d_i$ indicate the number of parameters associated with $x_i$ or does $d_i = |X_i|$ where $x_i \in X_i$? – Nicholas Mancuso Dec 10 '14 at 18:59
• So, the number of U functions doesn't change, but the number of values we need to fit does. If $v_i$ is binary, then we can make $u_i$ a single value, corresponding to $v_i=1$, since the value for $v_i=0$ is determined to make the rules of probability work. But if we have $3$ values for $v_i$, then we need a case for $1$ and a case for $2$, etc. The last value is always restricted based on the others, but there's more degrees of freedom when there's more possible values. – jmite Dec 10 '14 at 20:46