Belief propagation generalizes backpropagation

• URL: http://arxiv.org/abs/2210.00610v1
• Date: Sun, 2 Oct 2022 20:02:41 GMT
• Title: Belief propagation generalizes backpropagation
• Authors: Frederik Eaton
• Abstract summary: In spite of their importance, the connection between backpropagation and belief propagation is poorly characterized. We show that when an input to backpropagation is converted into an input to belief propagation so that (loopy) belief propagation can be run on it, then the result of belief propagation encodes the result of backpropagation. In other words, we prove for apparently the first time that belief propagation generalizes backpropagation.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: The two most important algorithms in artificial intelligence are backpropagation and belief propagation. In spite of their importance, the connection between them is poorly characterized. We show that when an input to backpropagation is converted into an input to belief propagation so that (loopy) belief propagation can be run on it, then the result of belief propagation encodes the result of backpropagation; thus backpropagation is recovered as a special case of belief propagation. In other words, we prove for apparently the first time that belief propagation generalizes backpropagation. Our analysis is a theoretical contribution, which we motivate with the expectation that it might reconcile our understandings of each of these algorithms, and serve as a guide to engineering researchers seeking to improve the behavior of systems that use one or the other.

Related papers

• Beyond Progress Measures: Theoretical Insights into the Mechanism of Grokking [50.465604300990904]
  Grokking refers to the abrupt improvement in test accuracy after extended overfitting. In this work, we investigate the grokking mechanism underlying the Transformer in the task of prime number operations.
  arXiv  Detail & Related papers  (2025-04-04T04:42:38Z)
• Uncommon Belief in Rationality [23.98373492872004]
  This paper proposes a graph-based language for capturing higher-order beliefs that agents might have about the rationality of the other agents. The two main contributions are a solution concept that captures the reasoning process based on a given belief structure and an efficient algorithm for compressing any belief structure into a unique minimal form.
  arXiv  Detail & Related papers  (2024-12-12T16:12:40Z)
• Isopignistic Canonical Decomposition via Belief Evolution Network [12.459136964317942]
  We propose an isopignistic transformation based on the belief evolution network. This decomposition offers a reverse path between the possibility distribution and its isopignistic mass functions. This paper establishes a theoretical basis for building general models of artificial intelligence based on probability theory, Dempster-Shafer theory, and possibility theory.
  arXiv  Detail & Related papers  (2024-05-04T12:39:15Z)
• Why do Random Forests Work? Understanding Tree Ensembles as Self-Regularizing Adaptive Smoothers [68.76846801719095]
  We argue that the current high-level dichotomy into bias- and variance-reduction prevalent in statistics is insufficient to understand tree ensembles. We show that forests can improve upon trees by three distinct mechanisms that are usually implicitly entangled.
  arXiv  Detail & Related papers  (2024-02-02T15:36:43Z)
• Leveraging Contextual Counterfactuals Toward Belief Calibration [1.418033127602866]
  meta-alignment problem is that human beliefs are diverse and not aligned across populations. In high regret situations, we observe that contextual counterfactuals and recourse costs are important in updating a decision maker's beliefs and the strengths to which such beliefs are held. We introduce the belief calibration cycle' framework to more holistically calibrate this diversity of beliefs with context-driven counterfactual reasoning.
  arXiv  Detail & Related papers  (2023-07-13T01:22:18Z)
• A Belief Model for Conflicting and Uncertain Evidence -- Connecting Dempster-Shafer Theory and the Topology of Evidence [8.295493796476766]
  We propose a new model for measuring degrees of beliefs based on possibly inconsistent, incomplete, and uncertain evidence. We show that computing degrees of belief with this model is #P-complete in general.
  arXiv  Detail & Related papers  (2023-06-06T09:30:48Z)
• Hybrid Predictive Coding: Inferring, Fast and Slow [62.997667081978825]
  We propose a hybrid predictive coding network that combines both iterative and amortized inference in a principled manner. We demonstrate that our model is inherently sensitive to its uncertainty and adaptively balances balances to obtain accurate beliefs using minimum computational expense.
  arXiv  Detail & Related papers  (2022-04-05T12:52:45Z)
• Iterated Belief Change, Computationally [3.42658286826597]
  Iterated Belief Change is the research area that investigates principles for the dynamics of beliefs over (possibly unlimited) many subsequent belief changes. In particular, we show that iterative belief revision is Turing complete, even under the condition that broadly accepted principles like the Darwiche-Pearl postulates for iterated revision hold.
  arXiv  Detail & Related papers  (2022-02-17T19:01:20Z)
• Convergence of Generalized Belief Propagation Algorithm on Graphs with Motifs [0.15229257192293197]
  Belief propagation is a fundamental message-passing algorithm for numerous applications in machine learning. In this paper, we study the convergence behavior of generalized belief propagation algorithm on graphs with motifs.
  arXiv  Detail & Related papers  (2021-12-11T22:46:50Z)
• Learning to Predict Trustworthiness with Steep Slope Loss [69.40817968905495]
  We study the problem of predicting trustworthiness on real-world large-scale datasets. We observe that the trustworthiness predictors trained with prior-art loss functions are prone to view both correct predictions and incorrect predictions to be trustworthy. We propose a novel steep slope loss to separate the features w.r.t. correct predictions from the ones w.r.t. incorrect predictions by two slide-like curves that oppose each other.
  arXiv  Detail & Related papers  (2021-09-30T19:19:09Z)
• Nested Counterfactual Identification from Arbitrary Surrogate Experiments [95.48089725859298]
  We study the identification of nested counterfactuals from an arbitrary combination of observations and experiments. Specifically, we prove the counterfactual unnesting theorem (CUT), which allows one to map arbitrary nested counterfactuals to unnested ones.
  arXiv  Detail & Related papers  (2021-07-07T12:51:04Z)
• A Weaker Faithfulness Assumption based on Triple Interactions [89.59955143854556]
  We propose a weaker assumption that we call $2$-adjacency faithfulness. We propose a sound orientation rule for causal discovery that applies under weaker assumptions.
  arXiv  Detail & Related papers  (2020-10-27T13:04:08Z)
• Neural Enhanced Belief Propagation on Factor Graphs [85.61562052281688]
  A graphical model is a structured representation of locally dependent random variables. We first extend graph neural networks to factor graphs (FG-GNN) We then propose a new hybrid model that runs conjointly a FG-GNN with belief propagation.
  arXiv  Detail & Related papers  (2020-03-04T11:03:07Z)

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.