Variable Elimination in Hybrid Factor Graphs for Discrete-Continuous Inference & Estimation
Pith reviewed 2026-05-16 18:45 UTC · model grok-4.3
The pith
Hybrid variable elimination in factor graphs produces exact posteriors as hybrid Bayes networks for discrete-continuous problems.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
A novel hybrid Gaussian factor and hybrid conditional allow derivation of hybrid variable elimination under the conditional linear Gaussian scheme, yielding exact posteriors represented as a hybrid Bayes network that supports MAP estimation and marginalization over both discrete and continuous variables.
What carries the argument
The hybrid Gaussian factor (connecting discrete and continuous variables) and hybrid conditional (encoding multiple continuous hypotheses per discrete choice), which together enable exact hybrid variable elimination to produce a hybrid Bayes network.
Load-bearing premise
The hybrid Gaussian factor and conditional capture all discrete-continuous interactions without loss of information, and the tree pruning with probabilistic assignment preserves the true MAP solution.
What would settle it
On a small synthetic hybrid problem whose exact posterior can be enumerated by exhaustive summation, compare the hybrid Bayes network output to the enumerated result and check for exact numerical match.
Figures
read the original abstract
Many problems in robotics involve both continuous and discrete components, and modeling them together for estimation tasks has been a long standing and difficult problem. Hybrid Factor Graphs give us a mathematical framework to model these types of problems, however existing approaches for solving them are based on approximations. In this work, we propose a new framework for hybrid factor graphs along with a novel variable elimination algorithm to produce a hybrid Bayes network, which can be used for exact Maximum A Posteriori estimation and marginalization over both sets of variables. Our approach first develops a novel hybrid Gaussian factor which can connect to both discrete and continuous variables, and a hybrid conditional which can represent multiple continuous hypotheses conditioned on the discrete variables. Using these representations, we derive the process of hybrid variable elimination under the Conditional Linear Gaussian scheme, giving us exact posteriors as a hybrid Bayes network. To bound the number of discrete hypotheses, we use a tree-structured representation of the factors coupled with a simple pruning and probabilistic assignment scheme, which allows for tractable inference. We demonstrate the applicability of our framework on a large scale SLAM dataset and a real world pose graph optimization problem, both with ambiguous measurements which require discrete choices to be made for the most likely measurements. Our demonstrated results showcase the accuracy, generality, and simplicity of our hybrid factor graph framework.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proposes a framework for hybrid factor graphs to jointly model discrete and continuous variables in robotics estimation problems. It introduces a hybrid Gaussian factor and hybrid conditional representation, then derives a variable elimination algorithm under the Conditional Linear Gaussian scheme that produces a hybrid Bayes network for exact MAP estimation and marginalization. For tractability with ambiguous measurements, the method employs a tree-structured factor representation together with pruning and probabilistic assignment to bound the discrete hypothesis space. The approach is demonstrated on a large-scale SLAM dataset and a real-world pose-graph optimization task.
Significance. If the pruning operator can be shown to preserve the exact MAP without unquantified loss, the work would offer a principled advance over existing approximate methods for hybrid inference, providing both exact posteriors in the unpruned case and a practical scheme for robotics applications. The derivation of hybrid elimination steps and the hybrid factor representations constitute the primary technical contribution.
major comments (2)
- [Abstract] Abstract and the variable-elimination derivation: the claim of 'exact posteriors as a hybrid Bayes network' is valid only in the unpruned case; the subsequent tree-structured pruning plus probabilistic assignment step is load-bearing for tractability yet lacks any proof that the operator commutes with elimination or that the true argmax over the joint hybrid posterior is guaranteed to be retained.
- [Pruning and probabilistic assignment section] Pruning scheme description: no dominance bound, error analysis, or recovery guarantee is supplied showing that discarded discrete hypotheses cannot contain the MAP solution, which directly affects the central claim of exact MAP estimation on problems with ambiguous measurements.
minor comments (2)
- [Hybrid representations] Notation for the hybrid conditional could be clarified with an explicit definition of how multiple continuous hypotheses are indexed by the discrete variables.
- [Experiments] The experimental section would benefit from an explicit statement of the pruning threshold value used and its sensitivity analysis.
Simulated Author's Rebuttal
We thank the referee for their careful reading and constructive feedback on our manuscript. The comments correctly identify the need to distinguish the exact inference results from the practical approximations used for tractability. We address each major comment below and will make targeted revisions to the abstract, introduction, and pruning section to clarify these distinctions without overstating the guarantees.
read point-by-point responses
-
Referee: [Abstract] Abstract and the variable-elimination derivation: the claim of 'exact posteriors as a hybrid Bayes network' is valid only in the unpruned case; the subsequent tree-structured pruning plus probabilistic assignment step is load-bearing for tractability yet lacks any proof that the operator commutes with elimination or that the true argmax over the joint hybrid posterior is guaranteed to be retained.
Authors: We agree that the hybrid variable elimination algorithm yields an exact hybrid Bayes network only when no pruning is applied. The tree-structured pruning and probabilistic assignment are introduced solely to bound the discrete hypothesis space for problems with ambiguous measurements. We will revise the abstract and the variable-elimination section to state explicitly that exact posteriors and MAP estimation hold in the unpruned case, while the pruning scheme is a heuristic approximation. We do not claim that the pruning operator commutes with elimination or guarantees retention of the global argmax; it prioritizes high-probability branches based on local scores. The experiments demonstrate practical accuracy, but we will add a clarifying sentence on the approximate nature of the pruned results. revision: partial
-
Referee: [Pruning and probabilistic assignment section] Pruning scheme description: no dominance bound, error analysis, or recovery guarantee is supplied showing that discarded discrete hypotheses cannot contain the MAP solution, which directly affects the central claim of exact MAP estimation on problems with ambiguous measurements.
Authors: The pruning scheme is presented as a practical mechanism to achieve tractability rather than as an exact procedure. No dominance bound, error analysis, or recovery guarantee is provided because the method is heuristic: it discards low-probability hypotheses according to a simple threshold on the tree-structured factors. We will revise the pruning section to describe the scheme explicitly as an approximation that may, in principle, eliminate the true MAP hypothesis, while noting that the unpruned elimination remains exact. The manuscript's central claim of exact MAP estimation applies to the hybrid Bayes network before pruning; we will ensure this scope is stated clearly in the text and experiments. revision: partial
Circularity Check
No significant circularity; hybrid elimination derivation is self-contained
full rationale
The paper introduces novel hybrid Gaussian factors and hybrid conditionals, then derives variable elimination under the Conditional Linear Gaussian scheme to obtain an exact hybrid Bayes network. This chain is algorithmic and does not reduce any prediction or posterior to a fitted parameter, self-citation, or renamed input by construction. The subsequent tree-structured pruning and probabilistic assignment is explicitly separated as a tractability heuristic and does not participate in the exactness claim. No load-bearing step matches any enumerated circularity pattern.
Axiom & Free-Parameter Ledger
free parameters (1)
- pruning threshold
axioms (1)
- domain assumption Conditional Linear Gaussian scheme
invented entities (2)
-
hybrid Gaussian factor
no independent evidence
-
hybrid conditional
no independent evidence
Reference graph
Works this paper leans on
-
[1]
Bayesian fault detection and diagnosis in dynamic systems,
U. Lerner, R. Parr, D. Koller, and G. Biswas, “Bayesian fault detection and diagnosis in dynamic systems,” inProceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence. AAAI Press, 2000, p. 531–537
work page 2000
-
[2]
Mh-isam2: Multi-hypothesis isam using bayes tree and hypo-tree,
M. Hsiao and M. Kaess, “Mh-isam2: Multi-hypothesis isam using bayes tree and hypo-tree,” in2019 International Conference on Robotics and Automation (ICRA), 2019, pp. 1274–1280
work page 2019
-
[3]
Discrete-continuous smoothing and mapping,
K. J. Doherty, Z. Lu, K. Singh, and J. J. Leonard, “Discrete-continuous smoothing and mapping,”IEEE Robotics and Automation Letters, vol. 7, no. 4, pp. 12 395–12 402, 2022
work page 2022
-
[4]
J. Mahler, J. Liang, S. Niyaz, M. Laskey, R. Doan, X. Liu, J. A. Ojea, and K. Goldberg, “Dex-net 2.0: Deep learning to plan robust grasps with synthetic point clouds and analytic grasp metrics,” inRobotics: Science and Systems XIII, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA, July 12-16, 2017, N. M. Amato, S. S. Srinivasa, N. Aya...
work page 2017
-
[5]
Dense object nets: Learn- ing dense visual object descriptors by and for robotic manipulation,
P. R. Florence, L. Manuelli, and R. Tedrake, “Dense object nets: Learn- ing dense visual object descriptors by and for robotic manipulation,” 2018
work page 2018
-
[6]
Neuralfeels with neural fields: Visuotactile perception for in-hand manipulation,
S. Suresh, H. Qi, T. Wu, T. Fan, L. Pineda, M. Lambeta, J. Malik, M. Kalakrishnan, R. Calandra, M. Kaess, J. Ortiz, and M. Mukadam, “Neuralfeels with neural fields: Visuotactile perception for in-hand manipulation,”Science Robotics, vol. 9, no. 96, p. eadl0628, 2024
work page 2024
-
[7]
Pronto: A multi-sensor state estimator for legged robots in real-world scenarios,
M. Camurri, M. Ramezani, S. Nobili, and M. Fallon, “Pronto: A multi-sensor state estimator for legged robots in real-world scenarios,” Frontiers in Robotics and AI, vol. 7, 2020
work page 2020
-
[8]
Slam with object discovery, modeling and mapping,
S. Choudhary, A. J. B. Trevor, H. I. Christensen, and F. Dellaert, “Slam with object discovery, modeling and mapping,” in2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2014, pp. 1018–1025
work page 2014
-
[9]
Incremental task and motion planning: A constraint-based approach,
N. T. Dantam, Z. K. Kingston, S. Chaudhuri, and L. E. Kavraki, “Incremental task and motion planning: A constraint-based approach,” inRobotics: Science and Systems, 2016
work page 2016
-
[10]
Grasp pose detection in point clouds,
A. ten Pas, M. Gualtieri, K. Saenko, and R. Platt, “Grasp pose detection in point clouds,”The International Journal of Robotics Research, vol. 36, no. 13-14, pp. 1455–1473, 2017
work page 2017
-
[11]
Probabilistic contact state estimation for legged robots using inertial information,
M. Maravgakis, D.-E. Argiropoulos, S. Piperakis, and P. Trahanias, “Probabilistic contact state estimation for legged robots using inertial information,” in2023 IEEE International Conference on Robotics and Automation (ICRA), 2023, pp. 12 163–12 169
work page 2023
-
[12]
Data-Driven MCMC for Learning and Inference in Switching Linear Dynamic Systems,
S. M. Oh, J. M. Rehg, T. Balch, and F. Dellaert, “Data-Driven MCMC for Learning and Inference in Switching Linear Dynamic Systems,” in Proc.22 nd AAAI National Conference on AI, Pittsburgh, PA, 2005, pp. 944–949
work page 2005
-
[13]
A new hybrid state estimator for systems with limited mode changes,
K. Roy and C. J. Tomlin, “A new hybrid state estimator for systems with limited mode changes,” inHybrid Systems: Computation and Control, A. Bemporad, A. Bicchi, and G. Buttazzo, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007, pp. 487–500
work page 2007
-
[14]
Collapsed amortized variational inference for switching nonlinear dynamical systems,
Z. Dong, B. Seybold, K. Murphy, and H. Bui, “Collapsed amortized variational inference for switching nonlinear dynamical systems,” inProceedings of the 37th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, H. D. III and A. Singh, Eds., vol. 119. PMLR, 13–18 Jul 2020, pp. 2638–2647
work page 2020
-
[15]
An elementary introduction to kalman filtering,
Y . Pei, S. Biswas, D. S. Fussell, and K. Pingali, “An elementary introduction to kalman filtering,” 2019
work page 2019
-
[16]
D. Koller and N. Friedman,Probabilistic Graphical Models: Princi- ples and Techniques. The MIT Press, 2009
work page 2009
-
[17]
Factor graphs: Exploiting structure in robotics,
F. Dellaert, “Factor graphs: Exploiting structure in robotics,”Annual Review of Control, Robotics, and Autonomous Systems, vol. 4, no. V olume 4, 2021, pp. 141–166, 2021
work page 2021
-
[18]
imhs: An incremental multi-hypothesis smoother,
F. Jiang, V . Agrawal, R. Buchanan, M. Fallon, and F. Dellaert, “imhs: An incremental multi-hypothesis smoother,” 2021
work page 2021
-
[19]
Dynamic bayesian networks: Representation, inference and learning,
K. P. Murphy, “Dynamic bayesian networks: Representation, inference and learning,” Ph.D. dissertation, University of California, Berkeley, 2002
work page 2002
-
[20]
B. K. Kannan and S. N. Kramer, “An augmented lagrange multiplier based method for mixed integer discrete continuous optimization and its applications to mechanical design,”Journal of Mechanical Design, vol. 116, no. 2, pp. 405–411, 06 1994
work page 1994
-
[21]
I. E. Grossmann and F. Trespalacios, “Systematic modeling of discrete- continuous optimization models through generalized disjunctive pro- gramming,”AIChE Journal, vol. 59, no. 9, pp. 3276–3295, 2013
work page 2013
-
[22]
A. Vecchietti, S. Lee, and I. E. Grossmann, “Modeling of dis- crete/continuous optimization problems: characterization and formu- lation of disjunctions and their relaxations,”Computers & Chemical Engineering, vol. 27, no. 3, pp. 433–448, 2003
work page 2003
-
[23]
Continuous reformulations of discrete–continuous optimization problems,
O. Stein, J. Oldenburg, and W. Marquardt, “Continuous reformulations of discrete–continuous optimization problems,”Computers & Chemi- cal Engineering, vol. 28, no. 10, pp. 1951–1966, 2004, special Issue for Professor Arthur W. Westerberg
work page 1951
-
[24]
An improved genetic algorithm for continuous and mixed discrete-continuous optimization,
J. G. Ndititu and T. M. Daniell, “An improved genetic algorithm for continuous and mixed discrete-continuous optimization,”Engineering Optimization, vol. 31, no. 5, pp. 589–614, 1999
work page 1999
-
[25]
Mixed integer-discrete-continuous opti- mization by differential evolution,
J. Lampinen and I. Zelinka, “Mixed integer-discrete-continuous opti- mization by differential evolution,” inProceedings of the 5th interna- tional conference on soft computing, vol. 71. Citeseer Princeton, NJ, USA, 1999, p. 76
work page 1999
-
[26]
Propagation of probabilities, means and variances in mixed graphical association models,
S. Lauritzen, “Propagation of probabilities, means and variances in mixed graphical association models,”Journal of the American Statis- tical Association, vol. 87, 02 1995
work page 1995
-
[27]
Exact inference in networks with discrete children of continuous parents,
U. Lerner, E. Segal, and D. Koller, “Exact inference in networks with discrete children of continuous parents,” inProceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence, ser. UAI’01. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2001, p. 319–328
work page 2001
-
[28]
Inference in hybrid bayesian networks with large discrete and continuous domains,
J. Mori and V . Mahalec, “Inference in hybrid bayesian networks with large discrete and continuous domains,”Expert Systems with Applications, vol. 49, pp. 1–19, 2016
work page 2016
-
[29]
K. P. Murphy, “Switching kalman filters,” UC Berkeley, Tech. Rep., 1998
work page 1998
-
[30]
Linear-time inference in Hierarchical HMMs,
K. Murphy and M. A. Paskin, “Linear-time inference in Hierarchical HMMs,” inAdvances in Neural Information Processing Systems (NIPS), 2001
work page 2001
-
[31]
A hybrid factor graph model for biomedical activity detection,
M. Stender, J. Graßhoff, T. Braun, R. M ¨oller, and P. Rostalski, “A hybrid factor graph model for biomedical activity detection,” in2021 IEEE EMBS International Conference on Biomedical and Health Informatics (BHI), 2021, pp. 1–4
work page 2021
-
[32]
Factor graphs for robot perception,
F. Dellaert, M. Kaess,et al., “Factor graphs for robot perception,” Foundations and Trends in Robotics, vol. 6, no. 1-2, pp. 1–139, 2017. [Online]. Available: https://www.nowpublishers.com/article/Details/ ROB-043
work page 2017
-
[33]
iSAM2: Incremental smoothing and mapping using the Bayes tree,
M. Kaess, H. Johannsson, R. Roberts, V . Ila, J. Leonard, and F. Dellaert, “iSAM2: Incremental smoothing and mapping using the Bayes tree,”Intl. J. of Robotics Research, vol. 31, pp. 217–236, Feb 2012. [Online]. Available: https://journals.sagepub.com/doi/abs/ 10.1177/0278364911430419
-
[34]
The interacting multiple model al- gorithm for systems with markovian switching coefficients,
H. Blom and Y . Bar-Shalom, “The interacting multiple model al- gorithm for systems with markovian switching coefficients,”IEEE Transactions on Automatic Control, vol. 33, no. 8, pp. 780–783, 1988
work page 1988
-
[35]
I. Cox and S. Hingorani, “An efficient implementation of reid’s multiple hypothesis tracking algorithm and its evaluation for the purpose of visual tracking,”IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 18, no. 2, pp. 138–150, 1996
work page 1996
-
[36]
State estimation for hybrid systems: applications to aircraft tracking,
I. Hwang, H. Balakrishnan, and C. Tomlin, “State estimation for hybrid systems: applications to aircraft tracking,”IEE Proceedings - Control Theory and Applications, vol. 153, pp. 556–566, 2006
work page 2006
-
[37]
Discrete-continuous depth estima- tion from a single image,
M. Liu, M. Salzmann, and X. He, “Discrete-continuous depth estima- tion from a single image,” inProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2014
work page 2014
-
[38]
Solving dense image matching in real-time using discrete-continuous optimiza- tion,
A. Shekhovtsov, C. Reinbacher, G. Graber, and T. Pock, “Solving dense image matching in real-time using discrete-continuous optimiza- tion,” 2016
work page 2016
-
[39]
SfM with MRFs: Discrete-continuous optimization for large-scale structure from motion,
D. Crandall, A. Owens, N. Snavely, and D. Huttenlocher, “SfM with MRFs: Discrete-continuous optimization for large-scale structure from motion,”IEEE Trans. Pattern Anal. Machine Intell., 2012
work page 2012
-
[40]
Discrete-continuous opti- mization for optical flow estimation,
S. Roth, V . Lempitsky, and C. Rother, “Discrete-continuous opti- mization for optical flow estimation,” inStatistical and Geometrical Approaches to Visual Motion Analysis, D. Cremers, B. Rosenhahn, A. L. Yuille, and F. R. Schmidt, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009, pp. 1–22
work page 2009
-
[41]
Discrete-continuous optimization for multi-target tracking,
A. Andriyenko, K. Schindler, and S. Roth, “Discrete-continuous optimization for multi-target tracking,” in2012 IEEE Conference on Computer Vision and Pattern Recognition, 2012, pp. 1926–1933
work page 2012
-
[42]
Y . Wu, S. Srivastava, N. Hay, S. Du, and S. Russell, “Discrete- continuous mixtures in probabilistic programming: Generalized se- mantics and inference algorithms,” inProceedings of the 35th Interna- tional Conference on Machine Learning, ser. Proceedings of Machine Learning Research, J. Dy and A. Krause, Eds., vol. 80. PMLR, 10–15 Jul 2018, pp. 5343–5352
work page 2018
-
[43]
Square Root SAM: Simultaneous location and mapping via square root information smoothing,
F. Dellaert, “Square Root SAM: Simultaneous location and mapping via square root information smoothing,” inRobotics: Science and Systems (RSS), 2005
work page 2005
-
[44]
Proprioceptive state estimation of legged robots with kinematic chain modeling,
V . Agrawal, S. Bertrand, R. Griffin, and F. Dellaert, “Proprioceptive state estimation of legged robots with kinematic chain modeling,” in 2022 IEEE-RAS 21st International Conference on Humanoid Robots (Humanoids), 2022, pp. 178–185
work page 2022
-
[45]
On the robustness of most probable explanations,
H. Chan and A. Darwiche, “On the robustness of most probable explanations,” inProceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence, ser. UAI’06. Arlington, Virginia, USA: AUAI Press, 2006, p. 63–71
work page 2006
-
[46]
Darwiche,Modeling and Reasoning with Bayesian Networks
A. Darwiche,Modeling and Reasoning with Bayesian Networks. Cambridge University Press, 2009. APPENDIXI HYBRIDBAYESNETWORK TO AHYBRIDFACTORGRAPH A. Hybrid Bayes Network Decomposition A Hybrid Bayes Network (HBN) represents the joint probability distribution over continuous statesX, discrete modesMand measurements over bothZas P(X, M, Z) We can use the prob...
work page 2009
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.