Lifting Factor Graphs with Some Unknown Factors: Conclusion, Acknowledgements, and References

Table of Links

Abstract and 1. Introduction

2. Preliminaries and 2.1 Factor Graphs and Parameterised Factor Graphs

   2.2 The Colour Passing Algorithm

3. The LIFAGU Algorithm

4. Empirical Evaluation

5. Conclusion, Acknowledgements, and References

5 Conclusion

In this paper, we introduce the LIFAGU algorithm to construct a lifted representation for an FG that possibly contains unknown factors. LIFAGU is a generalisation of the widespread CP algorithm and allows to transfer potentials from known factors to unknown factors by identifying symmetric subgraphs. Under the assumption that for every unknown factor there exists at least one known factor having a symmetric surrounding graph structure to it, LIFAGU is able to replace all unknown potentials in an FG by known potentials.

Acknowledgements

This work was partially supported by the BMBF project AnoMed. The research of Malte Luttermann was also partially supported by the Medical Cause and Effects Analysis (MCEA) project. This preprint has not undergone peer review or any post-submission improvements or corrections. The Version of Record of this contribution is published in Lecture Notes in Computer Science, Volume 14294, and is available online at https://doi.org/10.1007/978-3-031-45608-4 25.

References

1. Ahmadi, B., Kersting, K., Mladenov, M., Natarajan, S.: Exploiting Symmetries for Scaling Loopy Belief Propagation and Relational Training. Machine Learning 92, 91–132 (2013)

   
   

2. Braun, T., Moller, R.: Lifted Junction Tree Algorithm. In: Proceedings of KI 2016: Advances in Artificial Intelligence (KI-16). pp. 30–42. Springer (2016)

   
   

3. De Salvo Braz, R., Amir, E., Roth, D.: Lifted First-Order Probabilistic Inference. In: Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI-05). pp. 1319–1325. Morgan Kaufmann Publishers Inc. (2005)

   
   

4. De Salvo Braz, R., Amir, E., Roth, D.: MPE and Partial Inversion in Lifted Probabilistic Variable Elimination. In: Proceedings of the Twenty-First National Conference on Artificial Intelligence (AAAI-06). pp. 1123–1130. AAAI Press (2006)

   
   

5. Gehrke, M., M¨oller, R., Braun, T.: Taming Reasoning in Temporal Probabilistic Relational Models. In: Proceedings of the Twenty-Fourth European Conference on Artificial Intelligence (ECAI-20). pp. 2592–2599. IOS Press (2020)

   
   

6. Hoffmann, M., Braun, T., M¨oller: Lifted Division for Lifted Hugin Belief Propagation. In: Proceedings of the Twenty-Fifth International Conference on Artificial Intelligence and Statistics (AISTATS-22). pp. 6501–6510. PMLR (2022)

   
   

7. Kersting, K., Ahmadi, B., Natarajan, S.: Counting Belief Propagation. In: Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence (UAI-09). pp. 277–284. AUAI Press (2009)

   
   

8. Kisy´nski, J., Poole, D.: Constraint Processing in Lifted Probabilistic Inference. In: Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence (UAI-09). pp. 293–302. AUAI Press (2009)

   
   

9. Kschischang, F.R., Frey, B.J., Loeliger, H.A.: Factor Graphs and the Sum-Product Algorithm. IEEE Transactions on Information Theory 47, 498–519 (2001)

   
   

10. Kullback, S., Leibler, R.A.: On Information and Sufficiency. The Annals of Mathematical Statistics 22, 79–86 (1951)

    
    

11. Milch, B., Zettlemoyer, L.S., Kersting, K., Haimes, M., Kaelbling, L.P.: Lifted Probabilistic Inference with Counting Formulas. In: Proceedings of the TwentyThird AAAI Conference on Artificial Intelligence (AAAI-08). pp. 1062–1068. AAAI Press (2008)

    
    

12. Niepert, M., Van den Broeck, G.: Tractability through Exchangeability: A New Perspective on Efficient Probabilistic Inference. In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence (AAAI-14). pp. 2467–2475. AAAI Press (2014)

    
    

13. Poole, D.: First-Order Probabilistic Inference. In: Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI-03). pp. 985–991. Morgan Kaufmann Publishers Inc. (2003)

    
    

14. Taghipour, N., Fierens, D., Davis, J., Blockeel, H.: Lifted Variable Elimination: Decoupling the Operators from the Constraint Language. Journal of Artificial Intelligence Research 47, 393–439 (2013)

    
    

15. Weisfeiler, B., Leman, A.A.: The Reduction of a Graph to Canonical Form and the Algebra which Appears Therein. NTI, Series 2, 12–16 (1968), English translation by Grigory Ryabov available at https://www.iti.zcu.cz/wl2018/pdf/ wl paper translation.pdf