Mixtures of truncated basis functions

Helge Langseth, Thomas D. Nielsen, Rafael Rumí, Antonio SalmerónInt. J. Approx. Reason 2012 · DOI · OpenReview

Abstract

Reasoning in hybrid domains—environments containing both discrete and continuous variables—poses a significant challenge for Bayesian Networks (BNs). The primary difficulty lies in maintaining "closure" during inference operations such as combination and marginalization. This paper introduces Mixtures of Truncated Basis Functions (MoTBFs), a unified mathematical framework that generalizes existing methods like Mixtures of Truncated Exponentials (MTEs) and Mixtures of Polynomials (MoPs). By employing generalized Fourier series and convex optimization, the proposed approach offers an anytime algorithm capable of approximating any probability distribution with arbitrary precision while guaranteeing valid, non-negative density functions.

Introduction

Bayesian Networks are powerful tools for uncertainty management, yet their application in hybrid domains is often hindered by the complexity of continuous variables. For efficient inference, the functions representing these variables must belong to a family that is closed under multiplication and integration. While discrete tables and Gaussian distributions are well-behaved in isolation, their combination often results in integrals that lack analytical solutions.

Existing solutions, such as MTEs and MoPs, have addressed these issues with varying degrees of success. However, MoPs are not closed under division, and MTEs often require extensive, manually curated libraries of approximations that do not scale well to complex or custom distributions. MoTBFs address these limitations by providing a flexible, automated, and theoretically grounded framework for density approximation.

Methodology

The MoTBF framework is built upon several key innovations:

1. Flexible Basis Functions

MoTBFs are defined as a superset of MTEs and MoPs, allowing for a diverse set of "legal" basis functions. This flexibility ensures that the mathematical operations required for inference remain consistent regardless of the specific function type used for approximation.

2. Global Approximation via Generalized Fourier Series

Unlike Taylor series expansions, which provide local approximations that may fail far from the expansion point, MoTBFs utilize a generalized Fourier series approach. This ensures a global approximation of the density function, meeting error bounds across the entire domain of the variable.

3. Density Enforcement through Convex Optimization

A critical challenge in function approximation is ensuring that the resulting "probability" function remains non-negative and integrates to unity. The authors formulate this as a convex optimization problem, specifically semi-definite programming, to guarantee that the MoTBF result is a valid probability density.

4. Greedy Anytime Algorithm

To balance computational cost and accuracy, the authors propose an iterative "anytime" algorithm. Starting with a simple approximation, the algorithm greedily refines the model by either adding a new basis function or splitting the variable's domain into smaller partitions. These decisions are guided by the reduction in Kullback-Leibler (KL) divergence, allowing the process to be halted once a desired quality threshold is reached.

Evaluation and Results

The MoTBF framework was evaluated by approximating several standard univariate probability distributions, including Normal (Gaussian), Gamma, Beta, and LogNormal distributions. The performance was compared against the state-of-the-art MTE library.

The results demonstrate superior accuracy for MoTBFs. For a standard Normal distribution $N(0,1)$, MoTBFs achieved a KL-divergence of $2.68 \cdot 10^{-9}$, a significant improvement over the $3.46 \cdot 10^{-4}$ achieved by the MTE library. Furthermore, the MoTBF method automatically handled distributions like Beta and LogNormal, which typically require manual intervention in previous frameworks. The algorithm effectively allocates resources, placing more split points and basis functions in regions of high probability mass while maintaining simplicity in the tails.

Conclusion and Future Work

MoTBFs represent a significant advancement in the field of hybrid Bayesian Networks, providing a unified and automated approach to density approximation. While the current implementation shows great promise, the authors identify areas for future improvement, including addressing numerical instabilities associated with high-order basis functions. Future research will also explore "dynamic translation"—refining approximations based on observed evidence—and learning MoTBF parameters directly from raw data.

Summary updated

BibTeX
@article{langseth2012mixtures,
  author = {Helge Langseth and Thomas D. Nielsen and Rafael Rumí and Antonio Salmerón},
  title = {{Mixtures of truncated basis functions}},
  journal = {Int. J. Approx. Reason.},
  year = {2012},
  doi = {10.1016/j.ijar.2011.10.004},
}
Figure