Colour Passing Revisited: Lifted Model Construction with Commutative Factors

• URL: http://arxiv.org/abs/2309.11236v2
• Date: Fri, 15 Dec 2023 15:28:09 GMT
• Title: Colour Passing Revisited: Lifted Model Construction with Commutative Factors
• Authors: Malte Luttermann, Tanya Braun, Ralf M\"oller, Marcel Gehrke
• Abstract summary: 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.
• Score: 3.1045268505532566
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Lifted probabilistic inference exploits symmetries in a probabilistic model to allow for tractable probabilistic inference with respect to domain sizes. To apply lifted inference, a lifted representation has to be obtained, and to do so, the so-called colour passing algorithm is the state of the art. The colour passing algorithm, however, is bound to a specific inference algorithm and we found that it ignores commutativity of factors while constructing a lifted representation. We contribute a modified version of the colour passing algorithm that uses logical variables to construct a lifted representation independent of a specific inference algorithm while at the same time exploiting commutativity of factors during an offline-step. Our proposed algorithm efficiently detects more symmetries than the state of the art and thereby drastically increases compression, yielding significantly faster online query times for probabilistic inference when the resulting model is applied.

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)
• Efficient Fairness-Performance Pareto Front Computation [51.558848491038916]
  We show that optimal fair representations possess several useful structural properties. We then show that these approxing problems can be solved efficiently via concave programming methods.
  arXiv  Detail & Related papers  (2024-09-26T08:46:48Z)
• Efficient Detection of Commutative Factors in Factor Graphs [1.1323769002489257]
  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.
  arXiv  Detail & Related papers  (2024-07-23T08:31:24Z)
• Lifted Causal Inference in Relational Domains [5.170468311431656]
  We show how lifting can be applied to efficiently compute causal effects in relational domains. We present the lifted causal inference algorithm to compute causal effects on a lifted level.
  arXiv  Detail & Related papers  (2024-03-15T10:44:27Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  We discuss the problem of bounding partially identifiable queries, such as counterfactuals, in Pearlian structural causal models. A recently proposed iterated EM scheme yields an inner approximation of those bounds by sampling the initialisation parameters. We show how a single symbolic knowledge compilation allows us to obtain the circuit structure with symbolic parameters to be replaced by their actual values.
  arXiv  Detail & Related papers  (2023-10-05T07:10:40Z)
• Object Representations as Fixed Points: Training Iterative Refinement Algorithms with Implicit Differentiation [88.14365009076907]
  Iterative refinement is a useful paradigm for representation learning. We develop an implicit differentiation approach that improves the stability and tractability of training.
  arXiv  Detail & Related papers  (2022-07-02T10:00:35Z)
• Distributional Gradient Boosting Machines [77.34726150561087]
  Our framework is based on XGBoost and LightGBM. We show that our framework achieves state-of-the-art forecast accuracy.
  arXiv  Detail & Related papers  (2022-04-02T06:32:19Z)
• Mitigating Performance Saturation in Neural Marked Point Processes: Architectures and Loss Functions [50.674773358075015]
  We propose a simple graph-based network structure called GCHP, which utilizes only graph convolutional layers. We show that GCHP can significantly reduce training time and the likelihood ratio loss with interarrival time probability assumptions can greatly improve the model performance.
  arXiv  Detail & Related papers  (2021-07-07T16:59:14Z)
• Learning Disentangled Representations with Latent Variation Predictability [102.4163768995288]
  This paper defines the variation predictability of latent disentangled representations. Within an adversarial generation process, we encourage variation predictability by maximizing the mutual information between latent variations and corresponding image pairs. We develop an evaluation metric that does not rely on the ground-truth generative factors to measure the disentanglement of latent representations.
  arXiv  Detail & Related papers  (2020-07-25T08:54:26Z)
• Distributed Value Function Approximation for Collaborative Multi-Agent Reinforcement Learning [2.7071541526963805]
  We propose several novel distributed gradient-based temporal difference algorithms for multi-agent off-policy learning. The proposed algorithms differ by their form, definition of eligibility traces, selection of time scales and the way of incorporating consensus iterations. It is demonstrated how the adopted methodology can be applied to temporal-difference algorithms under weaker information structure constraints.
  arXiv  Detail & Related papers  (2020-06-18T11:46:09Z)

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.