Source-linked AI summary
Lifted Model Construction under Approximate Commutativity
Malte Luttermann, Jan Speller, Tanya Braun, Marcel Gehrke, Ralf Möller
TL;DR
Lifted inference relies on exact commutative factors, yet data-estimated potentials may differ slightly despite underlying indistinguishability. The paper introduces ε-commutativity and representative-based compression, proving strict query-error bounds and finding substantially lower runtime with highly accurate results.
Problem
Lifted representation construction requires exact commutative factors, but estimation errors can break potential equality even when underlying symmetries remain.
Method
The paper defines ε-commutativity, compresses approximately symmetric factors using representative potentials, and integrates this compression into ACP.
Results
The paper proves strict approximation-error bounds and empirically finds substantially reduced runtime with query results extremely close to exact ACP.
Takeaways & Limitations
ε-commutative compression supports lifted inference with highly accurate query results despite small deviations from exact symmetry.
Takeaways & Limitations
Using a counting random variable currently restricts the approach to discrete factor graphs, while continuous models require a continuous counterpart.
Abstract
from arXiv · showhide
Lifted inference algorithms enable scalable probabilistic inference even for large object domains by leveraging the indistinguishability of objects in a probability distribution. An essential prerequisite for constructing a lifted representation is to identify commutative factors, i.e., functions whose output values are invariant under permutations of a subset of their input values, in a potential-based factorisation. In practice, however, parameters learned from data inevitably deviate even if associated objects are indistinguishable, causing their corresponding factors to be only approximately commutative instead of being exactly commutative. We address this problem by introducing the concept of ε-commutativity, a relaxation of commutativity where output values are only approximately invariant under permutations of input values. Specifically, we show how ε-commutativity can be exploited for lifted model construction, downstream probabilistic inference, and prove strict bounds on the induced approximation error, thereby ensuring the practical applicability of lifted model construction while maintaining highly accurate query results. These theoretical guarantees are confirmed empirically, demonstrating comparable query accuracy at lower runtime.
1 Introduction
Lifted inference exploits indistinguishable objects to make probabilistic inference tractable, but constructing lifted representations requires identifying exactly commutative factors. This paper introduces ε-commutativity to handle estimation-induced deviations while preserving accurate inference and reducing runtime.
- Motivation: Lifted inference groups indistinguishable objects to achieve inference whose complexity grows polynomially with domain size.General probabilistic inference is otherwise intractable because computational cost grows exponentially with the number of random variables.
- Motivation: Commutative factors are required for lifted representation construction because their outputs remain invariant under permutations of selected inputs.Identifying such factors enables symmetric objects to be grouped together.
- Problem: Exact commutativity can be broken by small parameter-estimation errors even when the underlying object symmetry remains present.This motivates relaxing exact equality of factor potentials.
- Approach: ε-commutativity permits bounded output deviations under permutations and supports compression by replacing groups of similar potential values with representatives.The compressed representation assigns events in a symmetry set the same value.
- Results: The paper proves a strict approximation-error bound and reports that empirical errors remain below the theoretical bound while runtime is substantially reduced.The compression is integrated into the ACP algorithm and evaluated across multiple parameter settings.
2 Background
Factor graphs represent joint distributions as products of non-negative local factors, and commutativity identifies factors whose outputs are unchanged by permitted argument permutations. The background example shows that this property can depend on counts rather than object identities, while estimation errors motivate approximate commutativity.
- Factor Graphs: A factor graph represents a joint distribution by decomposing it into products of local non-negative functions called factors.Each factor maps assignments of its argument randvars to non-negative potential values.
- Example: In the employee example, the factor output depends on the number of highly competent employees rather than their identities.Swapping Alice's and Bob's competence values leaves the corresponding revenue potential unchanged.
- Commutative Factors: A factor is commutative with respect to a subset of arguments when every permitted permutation leaves its output unchanged.Only arguments with identical ranges can be permuted.
- Motivation: Exact commutativity is fragile because small estimation errors can destroy potential equality despite preserved underlying symmetry.The paper therefore introduces approximate commutativity in the next section.
3 Approximate Commutativity
ε-commutativity relaxes exact commutativity by allowing multiplicative deviations between potentials related by permutations, enabling approximate factor compression with bounded error. The paper establishes structural properties, a representative-factor construction, and limits on detecting ε-commutative argument sets.
- Definition: ε-commutativity allows permuted potentials to differ multiplicatively within factors of (1 − ε) and (1 + ε), reducing to strict commutativity when ε = 0.The definition requires both directions of the ε-equivalence relation for every relevant permutation.
- Compression: Commutative arguments can be grouped into a counting random variable, replacing individual assignments with aggregated representative potentials.The compressed representation gives symmetry-equivalent assignments the same value.
- Structural properties: ε-commutativity is preserved for subsets of arguments, but it is not closed under unions of ε-commutative sets.Therefore, identifying larger ε-commutative argument sets requires more sophisticated procedures than exact commutativity detection.
- Structural properties: Theorem 1 prevents direct transfer of an exact-commutativity algorithm for maximum subsets to ε-commutative arguments.The failure of union closure is the relevant structural obstruction.
- Compression: A symmetrised representative factor is ε-equivalent to the original factor, and averaging potentials within each symmetry set provides such a representative.Potentials within one symmetry set are pairwise ε-equivalent, supporting the averaging construction.
- Error guarantees: The paper derives a strict, optimal approximation bound for distributions induced by compressing ε-commutative factors.The bound is sharp in the general non-trivial case.
- Error guarantees: Multiplicative relaxation makes the distributional bound attainable because the discrepancy measure depends on potential quotients; additive relaxation could yield arbitrarily large deviations.This scope condition explains why the paper uses multiplicative ε-equivalence.
4 Experiments
The experiments evaluate the trade-off between compressing ε-commutative factors, downstream inference runtime, and query accuracy. Compression substantially accelerates inference while marginal probabilities remain close to those from exact ACP.
- 4 Experiments: The evaluation compares runtime and query accuracy when compressing ε-commutative factors in lifted model construction.It compares LVE on models returned by exact ACP and its ε-commutative extension.
- 4 Experiments: Compression of ε-commutative factors substantially accelerates downstream probabilistic inference, with speedup increasing exponentially with domain size.
- 4 Experiments: The per-query quotient p′ / p concentrates tightly around one across evaluated configurations, apart from a few outliers.This indicates that marginal probabilities remain extremely close to those obtained with exact ACP.
- 4 Experiments: ACP ±ε unlocks lifted-inference speedups at almost no loss of query accuracy.
5 Conclusion
The paper concludes that ε-commutativity supports representative-based compression, theoretically controlled query error, and substantial practical speedups. The current treatment is restricted to discrete variables, leaving continuous-variable extensions for future work.
- 5 Conclusion: ε-commutativity tolerates small numerical deviations in factor potentials and supports representative-based compression integrated into ACP.The scheme collapses ε-equivalent potentials into shared values.
- 5 Conclusion: The paper proves a sharp optimal bound on approximation error while empirical results show substantial speedups and query deviations within the theoretical guarantee.
- 5 Conclusion: The concepts also apply to detecting and compactly storing approximately symmetric non-negative functions beyond factor graphs.
- 5 Conclusion: The present work is restricted to discrete variables because continuous-variable models require a continuous counterpart of a CRV.
A Detailed Proofs
The detailed proofs establish multiplicative relationships among permuted potentials and derive tight approximation-error bounds for symmetrising ε-commutative factors. The bounds are attained by explicit constructions, proving optimality.
- A Detailed Proofs: ε-commutativity bounds every permuted potential within multiplicative factors 1/(1+ε) and 1+ε of the original value.
- A Detailed Proofs: Within each equivalence class, potentials lie between class minima and maxima whose ratio is at most 1+ε.
- A Detailed Proofs: The proof handles extrema from different or identical equivalence classes and establishes the bound in all cases.
- A Detailed Proofs: The sharpest bound uses the two largest equivalence classes, with equal maximal sizes when several classes tie.
- A Detailed Proofs: Theorem 5 proves that the bound from Theorem 4 is optimal.
- A Detailed Proofs: An explicit factor-graph construction attains the bound, while disjoint argument sets allow extrema to be chosen independently across factors.
A.1 Additional Result Symmetry Set
The symmetry-set cardinality is determined by the number of commutative argument permutations after accounting for repeated values. It ranges from one to |Cϕ|!, attaining the maximum exactly when all values are pairwise non-ε-equivalent.
- A.1 Additional Result Symmetry Set: For a fixed assignment, the symmetry set is generated by permuting positions corresponding to ε-commutative arguments.
- A.1 Additional Result Symmetry Set: The symmetry-set cardinality satisfies 1 ≤ |Sϕ(r)| ≤ |Cϕ|!, with the upper bound attained exactly when commutative-argument values are pairwise non-ε-equivalent.
- A.1 Additional Result Symmetry Set: Repeated values reduce the number of distinct tuples because permutations among equal-valued positions produce identical results.
B Additional Experimental Results
Additional experiments show that ε-relaxed ACP preserves accurate inference while improving online speed and structural compression across tested factor counts and tolerances. The relaxation adds no offline overhead and can reduce it, while exact ACP may fail to compress some instance classes.
- LVE runtime on ε-relaxed models remains almost constant with domain size, unlike exact ACP, whose runtime grows as the domain expands.
- The per-query quotient p′ / p stays concentrated near one across all tested configurations, with slightly wider spread for larger ε and more outliers as k increases.Even at k = 7 and ε = 0.1, the quotient remains within the theoretical guarantee.
- Online inference speedup grows exponentially with domain size and exceeds 30× at d = 20 when averaged across k and ε.
- ε-relaxed ACP does not increase offline runtime and can slightly reduce it by finding ε-commutative factors with fewer search iterations.Exact ACP checks more argument subsets before concluding that no strictly commutative subset exists.
- ε-relaxed ACP achieves substantially smaller compression ratios than exact ACP, and both ratios decrease as domain size grows.The relaxed variant can compress ε-commutative factors that exact ACP cannot.
- Exact ACP compresses employee instances but achieves no compression for epidemic instances, showing that its success depends on factor-graph structure.This failure can occur even when a graph contains one ε-commutative factor, because information propagates through ACP’s colour-passing procedure.