Tractable Computation of Expected Kernels
This work addresses a fundamental computational bottleneck in machine learning for applications like support vector machines and probabilistic modeling, offering incremental improvements through tractable methods.
The paper tackles the problem of computing expected kernel functions, which are typically intractable and estimated via Monte Carlo methods, by characterizing conditions for exact and efficient computation using probabilistic circuits. It demonstrates advancements in kernel embedding frameworks, with new algorithms for missing data reasoning and importance sampling that outperform baselines on various datasets.
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.