  Computing the expectation of some kernel function is ubiquitous in machine
learning, from the classical theory of support vector machines, to exploiting
kernel embeddings of distributions in applications ranging from probabilistic
modeling, statistical inference, casual 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.
