Value of Information in Probabilistic Logic Programs
  In medical decision making, we have to choose among several expensive
diagnostic tests such that the certainty about a patient's health is maximized
while remaining within the bounds of resources like time and money. The
expected increase in certainty in the patient's condition due to performing a
test is called the value of information (VoI) for that test. In general, VoI
relates to acquiring additional information to improve decision-making based on
probabilistic reasoning in an uncertain system. This paper presents a framework
for acquiring information based on VoI in uncertain systems modeled as
Probabilistic Logic Programs (PLPs). Optimal decision-making in uncertain
systems modeled as PLPs have already been studied before. But, acquiring
additional information to further improve the results of making the optimal
decision has remained open in this context.
  We model decision-making in an uncertain system with a PLP and a set of
top-level queries, with a set of utility measures over the distributions of
these queries. The PLP is annotated with a set of atoms labeled as
"observable"; in the medical diagnosis example, the observable atoms will be
results of diagnostic tests. Each observable atom has an associated cost. This
setting of optimally selecting observations based on VoI is more general than
that considered by any prior work. Given a limited budget, optimally choosing
observable atoms based on VoI is intractable in general. We give a greedy
algorithm for constructing a "conditional plan" of observations: a schedule
where the selection of what atom to observe next depends on earlier
observations. We show that, preempting the algorithm anytime before completion
provides a usable result, the result improves over time, and, in the absence of
a well-defined budget, converges to the optimal solution.
