Direct Sampling

Direct Sampling is an approximate inference method where we pull samples from the given joint probability distribution.

Example

Suppose we are interested in:

where we dare \(P(B^{1}|D^{1},C^{1})\).

Step 1: sort

We obtain a topological sort of this network:

\begin{equation} B, S, E, D, C \end{equation}

Step 2: sample from \(B,S\)

• We sample \(B\). We sampled that \(B=1\) today.
• We sample \(S\). We sampled that \(S=0\) today.

Step 3: sample from \(E\)

• We sample \(E\) GIVEN what we already sampled, that \(B=1, S=0\), we sampled that that \(E = 1\)

Step 4: sample from \(D, C\)

• We sample \(D\) given that \(E=1\) as we sampled.
• We sample \(C\) given that \(E=1\) as we sampled.

Repeat

Repeat steps 2-4

How do we deal with Markov Decision Process solution with continuous state space?

Let there be a value function parameterized on \(\theta\):

\begin{equation} U_{\theta}(s) \end{equation}

Let us find the value-function policy of this utility:

\begin{equation} \pi(s) = \arg\max_{a} \qty(R(s,a) + \gamma \sum_{s’}^{} T(s’|s,a) U_{\theta}(s’)) \end{equation}

We now create a finite sampling of our state space, which maybe infinitely large (for instance, continuous):

\begin{equation} S \in \mathcal{S} \end{equation}

where, \(S\) is a set of discrete states \(\{s_1, \dots, s_{m}\}\).

Probabilistically Checkable Proofs

Every statement that has a polynomial time checkable proof has such a proof where the verifier only reads \(O(1)\) (constant) bits of the proof such hat…

• perfect completeness: correct statements will be accepted with probability 1
• soundness: false statements will be rejected with probability 0.99 (with epsilon as the reading constant increases)

PCP Theorem

For some constant \(\alpha > 0\), and for ever language \(L \in NP\), there exists a polynomial-time that makes every input \(x\) into a \(f(x)\) such that…

If we take entangled qubits, and separate them real far away, their behavior would be the same even despite it will take longer for light to travel.