Lecture 6: Stochastic computations
Two main questions:
- How to compute probabilities with limited resources
- How to do probabilistic / stochastic computations?
Approach: study complexity classes based on Probabilistic Turing Machines.
- Motivation: what's the benefit of using uncertainty / or when can we be uncertain?
- Examples: primality testing and majority SAT.
-
The classes PP (Majsat) and BPP (Primes).
-
BPP: bounded probabilistic polynomial time (akin to P)
- PP: (includes inherently intractable problems) (akin to NP)
MARGINAL PROBABILITY is PP-hard. If we can show that MARGINAL PROBABILITY is in BPP, then we have shown that BPP=PP.
The main insight here is that in certain conditions, stochastic algorithms can provide good enough approximations way more efficiently that deterministic algorithms.
Problem statement
We have discussed so far:
- axioms of probability theory
- updating probabilities in light of new evidence
- fundamental problems of "Bayesianism"
One important problem of the Bayesian confirmation theory was logical omniscience, meaning: an agent ought to believe everything that can be inferred (from the agent's subjective perspective) from the agent's knowledge base.
Expression in epistemic knowledge: $K \phi, K(\phi \rightarrow \psi) \rightarrow K \phi$.
If agent knows phi, and if the agent knows that phi entails psi, then the agent ought to know psi.
In this case, the conclusion phi follows logically from the assumptions. But in case of uncertainty, i.e. reasoning with uncertainty, this step requires computation.
We can express a variant with uncertainty:
If the agent's degrees of belief are P(A) and P(B|A), then the agent ought to also have a degree of belief P(B).
The required computation is in this case P(B)=P(B|A)xP(A) (i.e. for all possible values of A). Given that we only have A and A is simple, this is trivial. But in the general case, computing marginals like that cannot be computed with "bounded" resources.
How can we do computations involving uncertainty when we have bounded resources?
Computations in the brain
- Synapses are extremely unreliable
- Spikes often fail to cause neurotransmitter release
- Neurotransmitters are often released without spikes
-
Evolution likely could have produced more accurate spikes
-
Conclusion/hypothesis, the stochastic firing of neurons is actually useful to reach good results with limited resources:
Similar considerations go for stochastic opening and closing of membrane channels, so there are many reasons to suspect that this stochastic nature actually is useful for computations and information processing in the brain. (Lecture Notes Kwisthout, 31)
Example: Primality testing with sampling
So, in what way is (random/stochastic) noise useful?
In some cases you may arrive at sufficiently accurate answers based on sampling noisy data, using properties of prime numbers.
"Fermat's little theorem" states a condition (a^(p-1) === 1(mod p)) that holds for all 0 < a < p if p is a prime.
Two approaches:
- Deterministic: compute for all a
- How many bits required to represent all numbers?
- N.B. only know for 14 years that there is a polynomial deterministic solution; but it is still quite bad and uses huge constants.
- Sample k times and if the condition holds for all sampled values, then p is probably a prime.
- Polynomial if k <= log(n). Review: why?
- Disclaimer: there are some numbers 'a' that will always pass this test (Carmigle numbers? I don't know how to write this name), so they are not evidence. So with sampling you can be a bit unlucky when sampling.
- Sophisticated variant with stronger prime properties: Miller-Rabin primality test with error bound $4^{-k}$, so that's amazing.
Of course, your confidence increases with more samples.
If you use k=100, then probability of answering incorrectly is 1/4^100. The chance of a random bit flip due to cosmic rays is larger! (IBM numbers in 1996) So this stochastic algorithm is more accurate than a deterministic algorithm for primality testing! So in practice, this algorithm is used for primality testing instead of a deterministic one, even if in theory the deterministic one is guaranteed to have a good result (assuming the hardware is not erroneous, which it may be due to the cosmic flip above).
Example: Majority Satisfiability and Marginal Probability
The well-known CNF-Sat problem (does there exist a truth assignment such that a boolean formula in CNF form holds?) has another variant: MajSat. Recall: this is a "yes/no" question.
MajSat: does the majority of truth assignments satisfy the formula? Or another formulation: does a random truth assignment satisfy the formula?
Deterministic variant:
Naive approach: trying all assignments and count "yes" and "no" answers for the assignments to estimate the probability of the "yes" answer. I guess that if p('yes')>-0.5, you decide "yes" on MajSat.
This approach has a lower bound of 2^(n-1) + 1 tests, and upper bound 2^n.
Each literal can take two values. The question then is: when can you know for sure the majority will be "yes"?
At what point can you say, in the best case, that the majority satisfies? If the first x are consistently "yes" or "no", at some point you already know a majority has been reached because there are not enough tests left to reach a majority. Specifically, after you've seen half of all truth assignments + 1 (where they are all either yes or no).
Best case: even if all truth assignments will satisfy, we will not be certain that will do unless we have seen half of all assignment + 1.
Why is half 2^(n-1)?
Example. Take n=4, then we have 2^4=16 possible truth assignments. Note that half is not 2^(n/2) which would be 4, but that half is 2^3 = 8. So for majority in the best case, we need 2^(n-1).
Stochastic approach:
Alternative: have a stochastic approach! Randomly pick a truth assignment and evaluate that. Then the question is: how many assignments/samples do we need to do before being sure enough?
- If the running frequency is very close to 0 or 1, we can be sure relatively quickly on a majority decision
- If instead the running frequency is close to 0.5, we are really not sure and need more samples to come to a decision with reasonable confidence.
Answer: we can use using Hoeffding's inequality
- q: fraction of satisfying truth assignments
- delta: upper bound on the desired degree of error
$$\frac{1}{(q-1/2)^2} ln \frac{1}{\sqrt{\delta}}$$
If q is close to 1/2, you need much more random samples than when you would just iterate over all assignments deterministically.
Takeaway: whether a stochastic approach will be successful heavily depends on the input type, i.e. the type of problem.
The trick then is: what type of problem has efficient randomized algorithms?
In this case, do we know in advance (based on some promise or problem property) that q will be far away from 0.5 (either lower or higher)? If yes, then the randomized approach is fruitful.
The answer is cast in terms of relations between complexity classes.
BPP and PP "can be seen as the randomized analog of P and NP". Similarly, BPP is a subset (not a true one) of PP. NP is also a subset of PP.
Assuming BPP != PP, MajSat $\in$ PP and is PP-complete.
So, if a problem is shown to be in PP, we cannot expect that a randomized algorithm will guarantee an efficient solution.
Details in the appendix.
For now:
- "BPP is the class of problems that can be efficiently (= in polynomial time) solved by a randomized algorithm with a neglictable probability of error"
- and "PP-complete problems would require an exponential number of samples to be solved in general by such a randomized algorithm, and in general cannot be solved by a deterministic algorithm either."
Probabilistic inference is PP-complete.
PP and BPP
PP:
- yes-instances in PP are accepted with probability 1/2 + e, but e may depend exponentially on the input size, i.e. e = 1/c^n for constant c>1.
- This means that it may approach 1/2 infinitesimally which means that a randomized algorithm will be ineffective.
BPP:
- Instead, in BPP the probability is polynomially bounded away from 1/2 (i.e. e = 1/(n^c))
Note that the difference between c^n (exponential) and n^c (polynomial).
Review p. 13, w.r.t. PP: majority of t ruth asssignments psi satisfy the formula if and only if phi is satisfiable. Why?
It is conjectured that BPP=P, meaning that for these stochastic solutions there is also expected to be a deterministic solution!
It is shown that NP is a subset of PP (but note, not proven that it's a strict subset!)
- Take formula phi with n variables
- Construct psi such that psi = phi or Xn+1 (so a disjunction with yet another variable)
To reach a majority for psi, it is required that it is possible to find at least one satisfying assignment.
Why do we add Xn+1? Not entirely clear to me. In any case, in the minimal case where psi is only one variable long, it is still clear you need it to be satisfiable to every reach a majority (i.e. 3 truth assignments).
Computational Complexity of marginal and posterior probabilities
Posterior:
To be shown/proven is that computing Pr(H=h) can be phrased as a PP-complete decision problem, namely: Is Pr(h|e) > q, where h are variables with a joint value assignment, e are evidence variables, and q is a rational number i.e. can be interpreted as a probability.
Marginal:
Is Pr(h) > q? This question is a subproblem of Pr(h|e) > q, because you can replace e with some unconnected binary variable X. Because this unconnected variable is independent of h, we have Pr(h|X=true)=Pr(h).
Types of approximations
Absolute approximation: let approximation q(h) be not more than e (some error measure) lower or higher than Pr(h).
Relative approximation:
$$\frac{Pr(h)}{1+\eta} \leq q(h) \leq Pr(h) x (1+\eta)$$
i.e. for $\eta = 0.2$ the approximation can be 20% off.
Claims
- Computing marginal probability and posterior probability are both PP-complete
- We focus on marginal probability, but already showed that this is a specific case of posterior probability
- Marginal probability cannot be decided by a randomized algorithm unless BPP=PP.
- Marginal probability cannot be approximated, either absolutely or relatively, for any given error measure e, unless P=NP.
- Marginal probability can be absolutely approximated in polynomial time using a randomized algorithm for an error measure $\eta \geq 1/n^c$.
- Using forward sampling
Marginal probability is PP-complete
See appendix C: probabilistic Turing machine can solve the Marginal Probability problem.
To show that Marginal Probabilty.
- MajSat is shown to be PP-hard (it is PP-complete, so both in PP and PP-hard).
- Reduce MajSat to Marginal Probability
- meaning: MajSat can be constructed as a case of Marginal Probability, which therefore is at least as hard but may be a harder problem (i.e. MajSat may be a simpler instance of the problem).
- notation: MajSat <= Marginal Probability
- Translate every instance of MajSet to an instance of Marginal Probability.
- Meaning: Marginal Probability is at least as hard as MajSat.
- So Marginal Probability is also PP-hard.
Implications of reduction:
- If we can solve MajSat, we can also solve Marginal Probability
- If we cannot solve Marginal Probability, we also cannot solve MajSat.
Reduction procedure: construct a Bayesian network from a given Boolean formula $\phi$ with n variables.
- For each variable in the Boolean formula $\phi$, add a binary stochastic variable to a Bayesian network.
- Possible values are "true" and "false"
- Have a uniform probability distribution over these values
- For each logical operator in $\phi$, add a binary variable to the Bayesian network.
- The parents of this variable are the inputs of the logical operator
- The conditional probability table of the binary variable corresponds to the truth table of the logical operator
- The top level operator is indicated with $V_{\phi}$.
- Now, any truth assignment that satisfies the original boolean formula $\phi$ will result in $V_{\phi}$ being 1 if that assignment satisfies $\phi$ and 0 otherwise.
- This reduction can be done in polynomial time: each element in the boolean formula (literal or operator) corresponds to a single variable in the Bayesian network, so the conversion has linear complexity.
Observation: without any joint value assignment the prior probability of the top level variable $V_{\phi}$ being true is $\frac{#\phi}{2^n}$. $#\phi$ is the number of satisfying truth assignments.
Why? I think this is quite trivial: simply the relative frequency of satisfying assignments over all possible assignments, given that you have no further evidence embedded in the network.
Proof. We reduce MajSat to Marginal Probability with the procedure above. Then we have Pr($V_{\phi}$ = True) > 1/2 iff $\frac{#\phi}{2^n}$ > 1/2, i.e. if the majority of truth assignments satisfy $\phi$. So Marginal Probability is PP-hard. Because it is also in PP, it is PP-complete (QED claim 1).
Reasoning (because I always break my head over the logic of reduction): The MajSat problem is construed as one case of the Marginal Probability problem, so a solution to Marginal Probability is also a solution to MajSat. Furthermore, the Marginal Probability problem is at least as hard as the MajSat problem (but in theory it could be harder; therefore solving MajSat does not necessarily solve Marginal Probability) We know MajSat is PP-hard, so Marginal Probability must also be PP-hard.
Theorem (see claim 2): because Marginal Probability is PP-hard it cannot be decided by a randomized algorithms, unless BPP = PP (cf. P=NP).
Intuition: randomized algorithms are incredibly ineffective when the majority is miniscule (1/2 + (1/2)^2), so they cannot be guaranteed to work in polynomial time.
Approximation results
Proof by contradiction for claim 3.
- Assume there is an algorithm A for approximating Marginal Probability in polynomial time.
- Transform some satisfiability instance $\phi$ to a Bayesian network.
- If $\phi$ is satisfiable, we have Pr($V_{\phi} = true) > \frac{1}{2^n}$ (because in the minimal case, only one assignment satisfies $\phi$). Otherwise, it is 0.
- Take the formula of relative approximation. Because the true $Pr(V_{\phi})$ is 0, you get 0 <= q(h) <= 0, so q(h) must be 0 when the formula $\phi$ is not satisfiable.
- Because of this strict conclusion, the output of approximation A helps us decide on the satisfiability of $\phi$! (i.e. if it's non-zero we know the original formula is satisfiable, otherwise not).
- This implies P=NP, because we have an efficient algorithm for deciding its satisfiability. Given that it's NP-hard (or PP-hard?) i.e. all other NP problems can be reduced to it, we now have an algorithm for all NP problems.
This leads to a contradiction when we would have P!=NP. So such an algorithm A cannot exist unless we also assume P=NP.
The argument can be repeated for the formula of absolute approximation.
From syllabus:
By a similar argument, we can show that Marginal Probability cannot be absolute approximated in polynomial time for $\eta$ < 1/2n+1 unless P = NP: just round A’s answer to the nearest k/2n; if and only if k > 0 then $\phi$ was satisfiable.
And claim 4:
We also claimed that Marginal Probability can be absolute approximated in polynomial time by a randomized algorithm for $\eta \geq 1/n^{c}$. This in fact follows from the Chernoff bound. If we do sampling by a simple forward sampling algorithm (pick random values for each variables, starting with the leafs, based on its conditional probability distribution and thus sample a joint value assignment), then the number of samples N we need to approximate q(h) with error $\eta$ and with a probability lower than $\delta$ that we answer incorrectly, is $\frac{1}{(\eta)^2} ln \frac{1}{\sqrt{\delta}}$. If $\eta \geq 1/n^{c}$, then this number is polynomially bounded in the size of the network for any $\delta$.