Efficient Detection of Commutative Factors in Factor Graphs

• URL: http://arxiv.org/abs/2407.16280v1
• Date: Tue, 23 Jul 2024 08:31:24 GMT
• Title: Efficient Detection of Commutative Factors in Factor Graphs
• Authors: Malte Luttermann, Johann Machemer, Marcel Gehrke,
• Abstract summary: We introduce the detection of commutative factors (DECOR) algorithm, which allows us to drastically reduce the computational effort for checking whether a factor is commutative in practice. We prove that DECOR efficiently identifies restrictions to drastically reduce the number of required iterations and validate the efficiency of DECOR in our empirical evaluation.
• Score: 1.1323769002489257
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Lifted probabilistic inference exploits symmetries in probabilistic graphical models to allow for tractable probabilistic inference with respect to domain sizes. To exploit symmetries in, e.g., factor graphs, it is crucial to identify commutative factors, i.e., factors having symmetries within themselves due to their arguments being exchangeable. The current state of the art to check whether a factor is commutative with respect to a subset of its arguments iterates over all possible subsets of the factor's arguments, i.e., $O(2^n)$ iterations for a factor with $n$ arguments in the worst case. In this paper, we efficiently solve the problem of detecting commutative factors in a factor graph. In particular, we introduce the detection of commutative factors (DECOR) algorithm, which allows us to drastically reduce the computational effort for checking whether a factor is commutative in practice. We prove that DECOR efficiently identifies restrictions to drastically reduce the number of required iterations and validate the efficiency of DECOR in our empirical evaluation.

Related papers

• Lifted Model Construction without Normalisation: A Vectorised Approach to Exploit Symmetries in Factor Graphs [3.1045268505532566]
  We find that the current state-of-the-art algorithm to construct a lifted representation in form of a parametric factor graph misses symmetries between factors that are exchangeable but scaled differently. We propose a generalisation of the advanced colour passing (ACP) algorithm, which is the state of the art to construct a parametric factor graph. Our proposed algorithm allows for potentials of factors to be scaled arbitrarily and efficiently detects more symmetries than the original ACP algorithm.
  arXiv  Detail & Related papers  (2024-11-18T16:59:44Z)
• Contrastive Factor Analysis [70.02770079785559]
  This paper introduces a novel Contrastive Factor Analysis framework. It aims to leverage factor analysis's advantageous properties within the realm of contrastive learning. To further leverage the interpretability properties of non-negative factor analysis, it is extended to a non-negative version.
  arXiv  Detail & Related papers  (2024-07-31T16:52:00Z)
• Knowledge Composition using Task Vectors with Learned Anisotropic Scaling [51.4661186662329]
  We introduce aTLAS, an algorithm that linearly combines parameter blocks with different learned coefficients, resulting in anisotropic scaling at the task vector level. We show that such linear combinations explicitly exploit the low intrinsicity of pre-trained models, with only a few coefficients being the learnable parameters. We demonstrate the effectiveness of our method in task arithmetic, few-shot recognition and test-time adaptation, with supervised or unsupervised objectives.
  arXiv  Detail & Related papers  (2024-07-03T07:54:08Z)
• Efficient Detection of Exchangeable Factors in Factor Graphs [1.1323769002489257]
  We introduce the detection of exchangeable factors (DEFT) algorithm, which allows us to drastically reduce the computational effort for checking whether two factors are exchangeable in practice. We prove that DEFT efficiently identifies restrictions to drastically reduce the number of permutations and validate the efficiency of DEFT in our empirical evaluation.
  arXiv  Detail & Related papers  (2024-03-15T10:20:56Z)
• Nonparametric Partial Disentanglement via Mechanism Sparsity: Sparse Actions, Interventions and Sparse Temporal Dependencies [58.179981892921056]
  This work introduces a novel principle for disentanglement we call mechanism sparsity regularization. We propose a representation learning method that induces disentanglement by simultaneously learning the latent factors. We show that the latent factors can be recovered by regularizing the learned causal graph to be sparse.
  arXiv  Detail & Related papers  (2024-01-10T02:38:21Z)
• Colour Passing Revisited: Lifted Model Construction with Commutative Factors [3.1045268505532566]
  We present a modified version of the colour passing algorithm that uses logical variables to construct a lifted representation independent of a specific inference algorithm. Our proposed algorithm efficiently detects more symmetries than the state of the art and thereby drastically increases compression, yielding significantly faster online query times.
  arXiv  Detail & Related papers  (2023-09-20T11:57:19Z)
• Enriching Disentanglement: From Logical Definitions to Quantitative Metrics [59.12308034729482]
  Disentangling the explanatory factors in complex data is a promising approach for data-efficient representation learning. We establish relationships between logical definitions and quantitative metrics to derive theoretically grounded disentanglement metrics. We empirically demonstrate the effectiveness of the proposed metrics by isolating different aspects of disentangled representations.
  arXiv  Detail & Related papers  (2023-05-19T08:22:23Z)
• Identifying Weight-Variant Latent Causal Models [82.14087963690561]
  We find that transitivity acts as a key role in impeding the identifiability of latent causal representations. Under some mild assumptions, we can show that the latent causal representations can be identified up to trivial permutation and scaling. We propose a novel method, termed Structural caUsAl Variational autoEncoder, which directly learns latent causal representations and causal relationships among them.
  arXiv  Detail & Related papers  (2022-08-30T11:12:59Z)
• Data-Driven Influence Functions for Optimization-Based Causal Inference [105.5385525290466]
  We study a constructive algorithm that approximates Gateaux derivatives for statistical functionals by finite differencing. We study the case where probability distributions are not known a priori but need to be estimated from data.
  arXiv  Detail & Related papers  (2022-08-29T16:16:22Z)
• Integer Factorization with Compositional Distributed Representations [5.119801391862319]
  We present an approach to integer factorization using distributed representations formed with Vector Symbolic Architectures. The approach formulates integer factorization in a manner such that it can be solved using neural networks and potentially implemented on parallel neuromorphic hardware.
  arXiv  Detail & Related papers  (2022-03-02T08:09:17Z)
• Ghost factors in Gauss-sum factorization with transmon qubits [44.62475518267084]
  We investigate Type II ghost factors, which are the class of ghost factors that cannot be suppressed. The presence of Type II ghost factors and the coherence time of the qubit set an upper limit for the total experiment time. We introduce preprocessing as a strategy to increase the discernability of a system, and demonstrate the technique with a transmon qubit.
  arXiv  Detail & Related papers  (2021-04-23T01:31:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.