2
$\begingroup$

Suppose we have a simple Bayesian network with two rows of nodes: $x_1, x_2, \ldots, x_n$ and $y_1, y_2, \ldots, y_n$. Each node $x_k$ takes a state of either 0 or 1 with equal probability. Each node $y_k$ takes state 1 with probability $p_{k,0}$ if $x_k$ is state 0 and probability $p_{k,1}$ if $x_k$ is state 1.

We would like to find the probability of the joint event $E$ that both (i) all $y_k$ are 1 and (ii) the total assignment of states on the network has a probability above $\epsilon$.

Is exponential time required to compute the probability of $E$, and if so (or not), how do we prove this?


In case it is helpful, let me give a low-$n$ example:

Suppose $n = 3$. If we just want to compute the probability of (i), then this is $$\Pr(\forall k: y_k = 1) = 2^{-3}(p_{1,0}p_{2,0}p_{3,0} + p_{1,0}p_{2,0}p_{3,1} + p_{1,0}p_{2,1}p_{3,0} + p_{1,0}p_{2,1}p_{3,1} + p_{1,1}p_{2,0}p_{3,0} + p_{1,1}p_{2,0}p_{3,1} + p_{1,1}p_{2,1}p_{3,0} + p_{1,1}p_{2,1}p_{3,1}).$$ We can factor the right-hand side so that rather than a sum of $2^3$ terms we just have a product of $3$ factors: $$\Pr(\forall k: y_k = 1) = 2^{-3}(p_{1,0} + p_{1,1})(p_{2,0} + p_{2,1})(p_{3,0} + p_{3,1}).$$ This reduces our computational time from $O(2^n)$ to $O(n)$ (as shown here for arbitrary $n$).

However, now consider the case that the terms $p_{1,0}p_{2,0}p_{3,0}$, $p_{1,0}p_{2,1}p_{3,0}$, and $p_{1,1}p_{2,0}p_{3,1}$ are quite small -- each less than $\epsilon$ -- and we would like our overall probability to 'ignore' such small terms. Then we want to compute: $$\Pr(E) = 2^{-3}(p_{1,0}p_{2,0}p_{3,1} + p_{1,0}p_{2,1}p_{3,1} + p_{1,1}p_{2,0}p_{3,0} + p_{1,1}p_{2,1}p_{3,0} + p_{1,1}p_{2,1}p_{3,1}).$$

Of course, no generalizable factorization seems possible for the right-hand side. This motivates the above question: how can we prove (or disprove) that computing $\Pr(E)$ in the case of arbitrary $n$, $p_{k,0}$, $p_{k,1}$, and $\epsilon$ is indeed $\Omega(2^n)$?

$\endgroup$
  • 1
    $\begingroup$ You may be able to use an adversary argument to show an $\Omega(2^n)$ lower bound. You could try to "hide" one instance of $\prod p_{i,b} < \epsilon$ such that it can only be precisely determined after $\sim 2^n$ queries. You could create a query model such that they submit some amount of $p_{i,b}$'s to you and you return the product or value if there is only 1. $\endgroup$ – ryan Apr 16 '19 at 18:05
2
$\begingroup$

Your problem is equivalent to:

Given: real numbers $a_1,\dots,a_n \in \mathbb{R}$; a real number $t \in \mathbb{R}$
Goal: count the number of binary vectors $(x_1,\dots,x_n) \in \{0,1\}^n$ such that $\sum_i a_i x_i \ge t$.

I think this problem is #P-complete, so you shouldn't expect any polynomial-time algorithm for computing it exactly.

Let me explain why. Let $\ell(x,y)$ denote the likelihood of the states $x,y$, $\ell(x) = \ell(x,1^n)$, and $L(x) = \log \ell(x)$ its log-likelihood. Then $L(x)$ has the form

$$L(x) = -n \log 2 + \sum_i \log p_{i,x_i}.$$

An assignment $x,1^n$ satisfies $E$ iff $L(x) \ge \log \epsilon$. Note that

$$\log p_{i,x_i} = \log p_{i,0} + x_i (\log p_{i,1} - \log p_{i,0}).$$

Letting $a_i = \log p_{i,1} - \log p_{i,0}$, we have

$$\sum_i \log p_{i,x_i} = \sum_i \log p_{i,0} + \sum_i a_i x_i.$$

If we now let $t = \log \epsilon + n \log 2 - \sum_i \log p_{i,0}$, we find that $x$ satisfies $E$ iff $\sum_i a_i x_i \ge t$. So, given $t$, we want to compute the probability that a random chosen $x$ satisfies $\sum_i a_i x_i \ge t$. This is equivalent to counting the number of $x$'s that satisfy $\sum_i a_i x_i \ge t$.

According to https://cstheory.stackexchange.com/q/19758/5038, this problem is #P-complete, so you shouldn't expect to find any polynomial time algorithm to compute the answer exactly.

However, there are techniques for approximating it: for instance, you could use algorithms for estimating the number of lattice points in a convex polytope (see, e.g., https://www.math.ucdavis.edu/~deloera/RECENT_WORK/semesterberichte.pdf) or computing them exactly in super-polynomial time (https://cstheory.stackexchange.com/q/22280/5038, https://cstheory.stackexchange.com/a/6464/5038).

| cite | improve this answer | |
$\endgroup$

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.