2
$\begingroup$

This question is related somewhat to Bayesian networks. In a BN, you have a DAG (directed acyclic graph). By supplying the root nodes with a sample, you can then follow the directed arcs to sample each of their children, and children's children, etc. until you have sampled the whole graph.

But what about a scenario where I have a complete, undirected (and thus cyclic) graph? For example, if I have 4 discrete variables $a, b, c, d$, and I have the complete set of empirical non-parametric partial conditional distributions $C = \{ p(a|b), p(a|c), p(a|d), p(b|a), p(b|c), ... \}$, how could I best sample a random vector $V_n = \{a_n, b_n, c_n, d_n\}$ satisfying all partial conditional distributions $C$? Since there is no notion of a set of "starting nodes", the cycles become an issue.

Here are two ideas I have so far:

  1. Generate a vast number of random $V_n = \{ p(a), p(b), p(c), p(d) \}$ and compute some approximation of likelihood for each like $\sim MLE(V_n) = \prod_{p(x|y)\in C, (x,y)\in V_n}{p(y)p(x|y)}$, and then stochastically select a winner by sampling over $\sim MLE(V_n)$. This seems very inefficient and unlikely to generalize well if the variable count and/or number of factors begins to increase substantially.
  2. A more complex stochastic method where you start with sample $V_{n_0} = \{ p(a), p(b), p(c), p(d) \}$, and iteratively attempt to converge toward the actual joint distribution by randomly selecting and replacing one of the variables, lets say for example $c$, using only the conditionals $p(c|\ast)$ in $C$ to sample a new $c_1$, and thus creating a new sample vector $V_{n_1} = \{ a_0, b_0, c_1, d_0 \}$. Then we could compare the likelihood estimates $\sim MLE(V_{n_0})$ and $\sim MLE(V_{n_1})$ and choose the more likely (deterministic or stochastic choice?) as the starting point for our next iteration. Hopefully this would converge after some reasonable number of iterations (even if the variable count and/or number of factors was high). However, how many iterations to take (or when to conditionally stop) is unclear to me.

Would either of my two ideas work at all? What better ways are there to efficiently generate quality samples approximating a non-parametric joint distribution given the complete set of partial conditional distributions? Maybe some other types of acceptance/rejection methods?

$\endgroup$
  • $\begingroup$ Your second idea seems similar to methods for multiple imputation of missing data via conditional distributions, see stefvanbuuren.name/fimd/sec-FCS.html, essentially a form of Gibbs sampling if the conditional distributions are compatible. $\endgroup$ – Jarle Tufto Mar 9 at 22:19
  • 1
    $\begingroup$ Do you know $p(a\& b|c)$ or $p(b|c\& d)$? $\endgroup$ – Matt F. Mar 10 at 1:28
  • $\begingroup$ @MattF. Yes, I could get any level of joint conditional distributions if needed, but this exponentially increases the time and storage/RAM requirements. So I was hoping to use just the first-order partial conditional distributions. $\endgroup$ – Special Sauce Mar 11 at 17:55
1
+50
$\begingroup$

The approximate joint distribution

If I understand the question correctly, the set of conditional distributions you have isn't enough to uniquely specify the full joint distribution. Instead, you want a way to sample from an approximate joint distribution that's consistent with the given conditional distributions. So, the first question is: what should this approximate joint distribution be? There are uncountably many valid possibilities, but the principle of maximum entropy (MaxEnt) argues for a particular choice: the distribution with maximum entropy that satisfies the constraints. This choice is consistent with all known information while otherwise imposing the minimum possible structure (i.e. it doesn't assume any information we don't actually have).

The MaxEnt distribution

Here's how to find the MaxEnt distribution consistent with the given conditional and marginal distributions. First, define the pairwise distributions $p(a,b), p(a,c), p(a,d), p(b,c), p(b,d), p(c,d)$. For example, $p(a,b) = p(a \mid b) p(b)$. These pairwise distributions completely capture the given marginal and conditional distributions.

The goal is then to find the joint distribution with maximum entropy, among those that are consistent with the pairwise distributions above. This is an optimization problem with linear constraints, and can be expressed as follows. There are 4 discrete variables, so the joint distribution can be expressed as a 4-dimensional table/array. Vectorize this table to represent the joint distribution as a vector $\hat{p}$. The optimization problem is then:

$$\max_\hat{p} \ -\sum_i \hat{p}_i \log \hat{p}_i \quad \text{subject to:}$$

$$\hat{p}_i \ge 0 \quad \vec{1}^T \hat{p} = 1 \quad W \hat{p} = v$$

The objective function is the Shannon entropy (which assumes the definition $0 \log 0 = 0$). The first two constraints require that $\hat{p}$ is a valid probability distribution (i.e. it's non-negative and sums to one; $\vec{1}$ denotes a vector of ones). The last set of constraints enforce consistency with the pairwise distributions--marginalizing out each pair of variables from the joint distribution must yield the corresponding pairwise distribution. Each row of matrix $W$ contains a pattern of zeros and ones that specify how to sum over $\hat{p}$, and the corresponding entry of vector $v$ specifies the value this sum must take. For example, if $A$ and $B$ can take particular values $a'$ and $b'$, then $v$ must contain the element $p(a',b')$ and the corresponding row of $W$ must be set to sum $\hat{p}$ over all values where $A=a', B=b'$. This enforces the constraint $\sum_{c,d} \hat{p}(a',b',c,d) = p(a',b')$. There will be one constraint for every possible pair of values that each pair of variables can take.

This problem can be solved numerically using a standard constrained optimization solver. Then, the vector $\hat{p}$ can be reshaped back to a 4-dimensional probability table. Note that this approach won't scale well with the number of variables, as the size of $\hat{p}$ will increase multiplicatively.

Sampling from the MaxEnt distribution

Given a probability table representing the full joint distribution, sampling from it is trivial (e.g. using the inverse transform method).

$\endgroup$
  • $\begingroup$ This sounds like a good choice for an analytic solution when the number of variables is small and the number of factors (number of unique values a given variable can take) is small. I was hoping for something that could scale well given a substantial increase in either of those two properties. I wasn't as explicit as I should have been in the question. I guess I'm probably left with Gibbs sampling as my best option. If no one else produces a more informative answer within a few days, I will award you the bounty. Thanks for your time and answer. $\endgroup$ – Special Sauce Mar 12 at 6:23
  • $\begingroup$ @SpecialSauce Yes, this answer was meant for small scale problems, since the question mentioned 4 variables. Hope you find what you're looking for. $\endgroup$ – user20160 Mar 12 at 11:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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