# Tractable Computation of Expected Kernels

arXiv: https://arxiv.org/abs/2102.10562 · HTML: https://mlsanity.com/paper/2102.10562/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 68 references that are in the map.
- First posted on arXiv 21 Feb 2021.

## Builds on (most cited first, 20 of 20)

- [Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithm](https://mlsanity.com/paper/1608.04471/) (2016)
- [A Kernelized Stein Discrepancy for Goodness-of-fit Tests and Model Evaluation](https://mlsanity.com/paper/1602.03253/) (2016)
- [Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2004.06231/) (2020)
- [A Differential Approach to Inference in Bayesian Networks](https://mlsanity.com/paper/1301.3847/) (2013)
- [Structure Discovery in Nonparametric Regression through Compositional Kernel Search](https://mlsanity.com/paper/1302.4922/) (2013)
- [Control functionals for Monte Carlo integration](https://mlsanity.com/paper/1410.2392/) (2014)
- [Bayesian Probabilistic Numerical Methods](https://mlsanity.com/paper/1702.03673/) (2017)
- [A Linear-Time Kernel Goodness-of-Fit Test](https://mlsanity.com/paper/1705.07673/) (2017)
- [Automatic Construction and Natural-Language Description of Nonparametric Regression Models](https://mlsanity.com/paper/1402.4304/) (2014)
- [Stein Variational Gradient Descent With Matrix-Valued Kernels](https://mlsanity.com/paper/1910.12794/) (2019)
- [Strudel: Learning Structured-Decomposable Probabilistic Circuits](https://mlsanity.com/paper/2007.09331/) (2020)
- [Probabilistic Circuits for Variational Inference in Discrete Graphical Models](https://mlsanity.com/paper/2010.11446/) (2020)
- [On Tractable Computation of Expected Predictions](https://mlsanity.com/paper/1910.02182/) (2019)
- [Black-box Importance Sampling](https://mlsanity.com/paper/1610.05247/) (2016)
- [One-Class Support Measure Machines for Group Anomaly Detection](https://mlsanity.com/paper/1303.0309/) (2013)
- [What to Expect of Classifiers? Reasoning about Logistic Regression with Missing Features](https://mlsanity.com/paper/1903.01620/) (2019)
- [The Sum-Product Theorem: A Foundation for Learning Tractable Models](https://mlsanity.com/paper/1611.03553/) (2016)
- [Approximate Knowledge Compilation by Online Collapsed Importance Sampling](https://mlsanity.com/paper/1805.12565/) (2018)
- [A Compositional Atlas of Tractable Circuit Operations: From Simple Transformations to Complex Information-Theoretic Queries](https://mlsanity.com/paper/2102.06137/) (2021)
- [Kernelized Complete Conditional Stein Discrepancy](https://mlsanity.com/paper/1904.04478/) (2019)

## Built on by (most cited first, 1 of 1)

- [Solving Marginal MAP Exactly by Probabilistic Circuit Transformations](https://mlsanity.com/paper/2111.04833/) (2021)

## Abstract (arXiv)

Computing the expectation of kernel functions is a ubiquitous task in machine learning, with applications from classical support vector machines to exploiting kernel embeddings of distributions in probabilistic modeling, statistical inference, causal discovery, and deep learning. In all these scenarios, we tend to resort to Monte Carlo estimates as expectations of kernels are intractable in general. In this work, we characterize the conditions under which we can compute expected kernels exactly and efficiently, by leveraging recent advances in probabilistic circuit representations. We first construct a circuit representation for kernels and propose an approach to such tractable computation. We then demonstrate possible advancements for kernel embedding frameworks by exploiting tractable expected kernels to derive new algorithms for two challenging scenarios: 1) reasoning under missing data with kernel support vector regressors; 2) devising a collapsed black-box importance sampling scheme. Finally, we empirically evaluate both algorithms and show that they outperform standard baselines on a variety of datasets.