Better results for tree-like graph solved with approximation algorithm than with exact algorithms

[Jaro Richter]

Hi there,

I've chosen a graphical model with a tree-like structure, so that exact inference should be possible. I've tested the inference with 3 different algorithms: LazyFlipper, DynamicProgramming and BeliefPropagation. In my understanding, the LazyFlipper algorithm should only be able to approximate the global optimum, which might result in the actual global optimum, but is not guaranteed. On the other hand, for DynamicProgramming and BeliefPropagation it is guaranteed to achieve the global optimum.

The results for DynamicProgramming and BeliefPropagation are exactly the same in this configuration. But it was extremely confusing to see that the inference with LazyFlipper as solving algorithm produced better results as those algorithms that guarantee the global optimum. Can anyone tell me how this could have happened?

Best regards,
Jaro

[Jörg Kappes]

Hi Jaro,
could You share your code or model in hdf5-Formal with us?

Most likely its a wrong usage of opengm.

best
Joerg

[Jaro Richter]

Hi Joerg,

thank you for your immediate answer.
While preparing the data for the hdf5-export, we (our working group) noticed that this was a misinterpretation of our results. We implemented a problem related detection accuracy for the graphical models. In our case, the detection accuracy was higher for solving the tree-like graphical model with LazyFlipper than with DynamicProgramming or BeliefPropagation. Nevertheless, the energy was minimized by DynamicProgramming and BeliefPropagation, while LazyFlipper produced results with minimal higher energy. So, everything worked as it should, but while focussing on the detection accuracy, we missed the fact that a lower detection accuracy is not always related to a lower energy of the graphical model.

Best regards,
jaro