Updating with incomplete observations
  Currently, there is renewed interest in the problem, raised by Shafer in
1985, of updating probabilities when observations are incomplete (or
set-valued). This is a fundamental problem, and of particular interest for
Bayesian networks. Recently, Grunwald and Halpern have shown that commonly used
updating strategies fail here, except under very special assumptions. We
propose a new rule for updating probabilities with incomplete observations. Our
approach is deliberately conservative: we make no or weak assumptions about the
so-called incompleteness mechanism that produces incomplete observations. We
model our ignorance about this mechanism by a vacuous lower prevision, a tool
from the theory of imprecise probabilities, and we derive a new updating rule
using coherence arguments. In general, our rule produces lower posterior
probabilities, as well as partially determinate decisions. This is a logical
consequence of the ignorance about the incompleteness mechanism. We show how
the new rule can properly address the apparent paradox in the 'Monty Hall'
puzzle. In addition, we apply it to the classification of new evidence in
Bayesian networks constructed using expert knowledge. We provide an exact
algorithm for this task with linear-time complexity, also for multiply
connected nets.
