2
$\begingroup$

The joint distribution of a undirected graph can be factorized as a product of potential functions over the maximal cliques of an undirected graph.

$$ p(\mathsf{x} \mid \theta) = \frac {1} {Z(\theta)} \prod_C \psi_C (\mathsf{x_C} \mid \theta_C) $$

  • $\mathsf{x_C}$ is a set of variables in the clique $C$
  • $Z$ normalizes the distribution and is called the partition function given by,

$$ Z(\theta) \triangleq \sum_\mathsf{x} \prod_C \psi_C (\mathsf{x_C} \mid \theta_C) $$

Why exactly is calculating $Z(\theta)$ expensive and how is this situation resolved? I'm a little confused about this.

$\endgroup$
1
  • 5
    $\begingroup$ That $\sum\limits_\mathsf{x}$ suggests this could be a big calculation if there are many possible values of $\mathsf{x}$ $\endgroup$
    – Henry
    Dec 14, 2022 at 10:03

1 Answer 1

7
$\begingroup$

A probability distribution needs to integrate to one.

$$1 = \int_{x_1 \in \omega_1} \int_{x_2 \in \omega_2} \dots \int_{x_N \in \omega_N} \frac {1} {Z(\theta)} \underbrace{\prod_C \psi_C (\mathsf{x_C} \mid \theta_C) }_{\text{this part is often known}}\,\text{d} x_1 \text{d} x_2 \dots \text{d} x_N $$

And often you know the expression $\prod_C \psi_C (\mathsf{x_C} \mid \theta_C) $ based on some theoretical grounds, but the normalisation constant $Z(\theta)$ is missing. We can multiply both sides of the equation above with $Z(\theta)$ giving

$$\begin{array}{} Z(\theta) &=& Z(\theta)\iiint_{{\bf x} \in \boldsymbol{\omega}} \frac {1} {Z(\theta)} \prod_C \psi_C (\mathsf{x_C} \mid \theta_C) \,\text{d} {\bf x} \\ &=&\iiint_{{\bf x} \in \boldsymbol{\omega}} \prod_C \psi_C (\mathsf{x_C} \mid \theta_C) \,\text{d} {\bf x}\end{array}$$

and that integral is not so easy.


Luckily you don't always need to know $Z(\theta)$. For instance when we compute a probability (density) ratio for two different values $\mathsf{x}$ and $\mathsf{x}^\prime$

$$\frac{p(\mathsf{x} \mid \theta)}{p(\mathsf{x}^\prime \mid \theta)} = \frac{\frac {1} {Z(\theta)} \prod_C \psi_C (\mathsf{x_C} \mid \theta_C)}{\frac {1} {Z(\theta)} \prod_C \psi_C (\mathsf{x_C}^\prime \mid \theta_C)} = \frac{ \prod_C \psi_C (\mathsf{x_C} \mid \theta_C)}{ \prod_C \psi_C (\mathsf{x_C}^\prime \mid \theta_C)}$$

This is used for instance in Markov chain monte carlo sampling methods.

$\endgroup$

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.