2
$\begingroup$

In Daphne Kollers book on Probabilistic graphical models exercise 9.3 asks the following

Ex 9.3 Consider a modified variable elimination algorithm that is allowed to multiply all of the entries in a single factor by some arbitrary constant. (For example, it may choose to renormalize a factor to sum to 1.) If we run this algorithm on the factors resulting from a Bayesian network with evidence, which types of queries can we still obtain the right answer to, and which not?

The reason i'm interested to a solution to this problem is for implementation. I'm interested in implementing the algorithm to prevent underflow issues. I can't seem to find a lot online about dealing with this especially for the sum product algorithm i've seen some stuff for max product. In particular this exercise is highlighted in chapter 10

enter image description here

Does anyone have a solution to this problem?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ How old is this book? The overhead of taking logarithms and exponentials ceased to be a concern some 30 years ago. $\endgroup$
    – whuber ♦
    Jul 22, 2021 at 14:11
  • $\begingroup$ It was published in 2009 $\endgroup$
    – Pavan Sangha
    Jul 22, 2021 at 14:17
  • $\begingroup$ Maybe, then, it's not the best resource for dealing with numerical issues. There's a lot of good information out there, especially in numerical analysis textbooks. $\endgroup$
    – whuber ♦
    Jul 22, 2021 at 15:05
  • $\begingroup$ cool, would you know the answer to the VE algorithm question specifically? What queries work if we scale factors? $\endgroup$
    – Pavan Sangha
    Jul 22, 2021 at 15:56
  • 1
    $\begingroup$ @whuber. Variable elimination is a standard technique for efficient exact inference in probabilistic graphical models. The modification is stated in the exercise. $\endgroup$
    – microhaus
    Jul 23, 2021 at 18:12

1 Answer 1

Reset to default
1
$\begingroup$

I believe that the answer is that you can answer queries of the form $P(A|B=b)$ but not of the form $P(A,B=b)$.

To see this, suppose that $F(A,B=b)$ is the outcome of the query. If we have multiplied factors $f_1,\ldots,f_k$ by scalers $c_1,\ldots,c_k$ then we get $$F(A,B=b) = \left(\prod_{i=1}^k c_i \right) P(A,B=b).$$ Then we can obtain the factor $$F'(B) = \sum_{B} F(A,B=b) = \left(\prod_{i=1}^k c_i \right) \sum_{B} P(A,B=b) = \prod_{i=1}^k c_i P(B=b).$$ Finally we get that $$\frac{F(A,B=b)}{F'(B=b)} = P(A|B=b)$$ as required.

To calculate $P(A,B=b)$ we would have to normalise at the end, which may not be part of the algorithm but is easy enough to implement.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I am not following your reasoning in here, you can normally reduce the factor to given evidence and continue with the inference ? $\endgroup$
    – Kaan E.
    Aug 1, 2021 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.