The number of alpha vectors needed to perform PBVI is one for each of your belief sample. Which is a bad idea. Perseus is essentially PBVI, where this idea is explored slightly.

The preamble is the same as PBVI:

we keep track of a bunch of alpha vectors and belief samples (which we get from point selection):

\begin{equation} \Gamma = \{\alpha_{1}, \dots, \alpha_{m}\} \end{equation}

and

\begin{equation} B = \{b_1, \dots, b_{m}\} \end{equation}

To preserve the lower-boundedness of these alpha vectors, one should seed the alpha vectors via something like blind lower bound

a randomized turing machine is a turing machine with functions \(\delta_{0}\), \(\delta_{1}\). During computation, we take either \(\delta_{0}\) or \(\delta_{1}\) each with probability \(\frac{1}{2}\).

See also randomized algorithm.

decision

a randomized TM decides a particular language \(L\) if, \(\forall x \in \Sigma^{*}\), we have that:

\begin{align} &x \in L \implies \text{Pr}\qty [M\text{ accepts } x] \geq \frac{2}{3} \\ &x \not\in L \implies \text{Pr}\qty [M\text{ accepts } x] \leq \frac{1}{3} \end{align}

NOTE! we have to prove this for all \(x\). “most \(x\)” is not good enough.

randomness is a resource which can be used.

Our unit of computation is a randomized turing machine

some questions of randomness

save time/space by using randomness: we used to believe that \(P \subset \text{Randomized } P\), \(L \subset \text{Randomized } L\), etc. But we now think \(P = \text{Randomized } P\) (intuition: if solving SAT requires circuits of exponential size, then \(P\) is equal to Randomized \(P\)).

efficient derandomized: can we reduce usage of randomization—i.e. completely derandomize it while not loosing a lot of efficiency?

The range (image, column space) is the set that some function \(T\) maps to.

constituents

some \(T: V\to W\)

requirements

The range is just the space the map maps to:

\begin{equation} range\ T = \{Tv: v \in V\} \end{equation}

additional information

range is a subspace of the codomain

This result is hopefully not super surprising.

zero

\begin{equation} T0 = 0 \end{equation}

as linear maps take \(0\) to \(0\), so \(0\) is definitely in the range.

Most users are incapable of writing good Boolean Retrieval queries.

feast or famine problem

Boolean Retrieval either returns too few or too many results: AND queries return often too few results \(\min (x,y)\), and OR queries return too many results \(x+y\).

This is not a problem with Ranked Information Retrieval because a large result set doesn’t matter: top results just needs to be good results.

free text query

Instead of using a series of Boolean Retrieval, we instead give free text to the user.