When Some Factors Go Missing, LIFAGU Finds the Symmetries

Table of Links

Abstract and 1. Introduction

1. Preliminaries and 2.1 Factor Graphs and Parameterised Factor Graphs

   2.2 The Colour Passing Algorithm

2. The LIFAGU Algorithm

3. Empirical Evaluation

4. Conclusion, Acknowledgements, and References

3 The LIFAGU Algorithm

As our goal is to perform lifted inference, we have to obtain a PFG where all potentials are known. To transform an FG containing unknown factors into a PFG without unknown factors, we transfer potentials from known factors to unknown factors. For example, consider again the FG depicted in Fig. 1 and assume that another individual, say eve, is added to the model. Like alice and bob, eve can travel, be sick, and be treated and hence, four new randvars with three new corresponding factors are attached to the model. However, as we might have limited data, we might not always know the exact potentials for the newly introduced factors when a new individual is added to the model and thus, we end up with a model containing unknown factors. In this example, we can transfer the potentials of the known factors f1 and f2 to the newly introduced unknown factors, as it is reasonable to assume that eve behaves the same as alice and bob as long as no evidence suggesting the contrary is available.

\ In an FG containing unknown factors, the only information available to measure the similarity of factors is the neighbouring graph structure of the factors. For the upcoming definitions, let NeG(v) denote the set of neighbours of a node v (variable node or factor node) in G, i.e., NeG(f) contains all randvars connected to a factor f in G and NeG(R) contains all factors connected to a randvar R in G. If the context is clear, we omit the subscript from NeG(v) and write Ne(v) for simplification. We start by defining the 2-step neighbourhood of a factor f as the set containing all randvars that are connected to f as well as all factors connected to a randvar that is connected to f. The concept of taking into account all nodes with a maximal distance of two is based on the idea of a single iteration of the colour passing procedure.

\

\

\

\ The second condition serves to ensure consistency as two factors with different potentials can obviously not be identical. Applying the definition of possibly identical factors to ϕ1 and ϕ2 from Fig. 3, we can verify that ϕ1 and ϕ2 are indeed possibly identical because they have symmetric 2-step neighbourhoods and identical potentials. Next, we describe the entire LIFAGU algorithm, which is illustrated in Algorithm 1.

\

\ Corollary 1. Given that for every unknown factor fi there is at least one known factor that is possibly identical to fi in an FG G, LIFAGU is able to replace all unknown potentials in G by known potentials.

\ It is easy to see that LIFAGU is a generalisation of CP, meaning that both algorithms compute the same result for input FGs containing only known factors (if an input FG G contains no unknown factors, only the first line and the last line of Algorithm 1 are executed—which is equivalent to calling CP on G).

\ Corollary 2. Given an FG that contains only known factors, CP and LIFAGU output identical groupings of randvars and factors, respectively.

\ Next, we investigate the practical performance of LIFAGU in our evaluation.

\

:::info Authors:

(1) Malte Luttermann[0009 −0005 −8591 −6839], Institute of Information Systems, University of Lubeck, Germany and German Research Center for Artificial Intelligence (DFKI), Lubeck, Germany (luttermann@ifis.uni-luebeck.de);

(2) Ralf Moller[0000 −0002 −1174 −3323], Institute of Information Systems, University of Lubeck, Germany and German Research Center for Artificial Intelligence (DFKI), Lubeck, Germany (moeller@ifis.uni-luebeck.de);

(3) Marcel Gehrke[0000 −0001 −9056 −7673], Institute of Information Systems, University of Lubeck, Germany (gehrke@ifis.uni-luebeck.de).

:::

:::info This paper is available on arxiv under ATTRIBUTION-SHAREALIKE 4.0 INTERNATIONAL license.

:::

\