Receiving multiple observations

Another extension of Formulation 9.5 is to allow multiple observations, $ y_1$, $ y_2$, $ \ldots $, $ y_n$, before making a decision. Each $ y_i$ is assumed to belong to an observation space, $ Y_i$. A strategy, $ \pi $, now depends on all observations:

$\displaystyle \pi : Y_1 \times Y_2 \times \cdots \times Y_n \rightarrow U .$ (9.29)

Under the nondeterministic model, $ Y_i(\theta)$ is specified for each $ i$ and $ \theta \in \Theta$. The set $ \Theta(y)$ is replaced by

$\displaystyle \Theta(y_1) \cap \Theta(y_2) \cap \cdots \cap \Theta(y_n)$ (9.30)

in (9.24) to obtain the optimal action, $ \pi^*(y_1,\ldots,y_n)$.

Under the probabilistic model, $ P(y_i\vert\theta)$ is specified instead. It is often assumed that the observations are conditionally independent given $ \theta $. This means for any $ y_i$, $ \theta $, and $ y_j$ such that $ i \not = j$, $ P(y_i\vert\theta,y_j) = P(y_i\vert\theta)$. The condition $ P(\theta\vert y)$ in (9.26) is replaced by $ P(\theta\vert y_1,\ldots,y_n)$. Applying Bayes' rule, and using the conditional independence of the $ y_i$'s given $ \theta $, yields

$\displaystyle P(\theta\vert y_1,\ldots,y_n) = {P(y_1\vert\theta) P(y_2\vert\theta) \cdots P(y_n\vert\theta) P(\theta) \over P(y_1,\ldots,y_n) }.$ (9.31)

The denominator can be treated as a constant factor that does not affect the optimization. Therefore, it does not need to be explicitly computed unless the optimal expected cost is needed in addition to the optimal action.

Conditional independence allows a dramatic simplification that avoids the full specification of $ P(y\vert\theta)$. Sometimes the conditional independence assumption is used when it is incorrect, just to exploit this simplification. Therefore, a method that uses conditional independence of observations is often called naive Bayes.

Steven M LaValle 2012-04-20