Efficient learning of smooth probability functions from Bernoulli tests with guarantees

Paul Rolland, Ali Kavis, Alexander Immer, Adish Singla, Volkan Cevher

Overview

Estimating a continuous probability function from binary "pass/fail" observations is a fundamental challenge in fields ranging from clinical trials to recommendation systems. This paper introduces the Smooth Beta Process (SBP), a highly efficient algorithm designed to learn these smooth probability functions from Bernoulli test data. Unlike traditional methods that struggle to scale, SBP offers linear-time complexity and rigorous theoretical convergence guarantees, even when outcomes are influenced by external contextual factors.

The Problem with Existing Standards

Traditionally, the Logistic Gaussian Process (LGP) has served as the gold standard for this type of inference. However, LGP suffers from two critical limitations:

  1. Prohibitive Computational Cost: LGP's complexity grows cubically ($\mathcal{O}(t^3)$) with the number of tests $t$. This makes it practically unusable for large-scale, modern datasets.
  2. Lack of Theoretical Guarantees: There are no formal proofs guaranteeing that the LGP-estimated function will actually converge to the true underlying probability function as more data is collected.

While faster alternatives exist, they frequently lack theoretical foundations or plateau in accuracy after a certain amount of data. Furthermore, real-world data is often "dynamic"—meaning the probability of success might be biased by known external factors (context), such as a patient's fatigue level during a medical test. Standard methods struggle to incorporate this context without falling victim to the curse of dimensionality.

The Smooth Beta Process (SBP)

To overcome these hurdles, the authors propose the Smooth Beta Process (SBP) and its contextual extension, CSBP. The methodology relies on three core pillars:

  • Experience Sharing: SBP utilizes a Beta distribution as a prior. To capitalize on the assumption that the target function is "smooth" (Lipschitz continuous), it employs a kernel-based update rule. This allows a single test at a specific point to inform the model's knowledge of the probability at nearby points.
  • Dynamic Kernel Scaling: A major theoretical contribution of the paper is proving that for the algorithm to converge, the kernel width ($\Delta$) must shrink at a specific, mathematically defined rate as the number of samples increases.
  • Contextual Inference: In dynamic settings, the probability of success is modeled as $P(s_i = 1) = A_i\pi(x_i) + B_i$, where $A_i$ and $B_i$ are known contextual parameters. Instead of adding these as new dimensions to the feature space (which exponentially increases complexity), CSBP incorporates them directly into the posterior update rule.

Key Insights and Results

The researchers evaluated SBP and CSBP using both synthetic 1D/2D data and a simulated stroke rehabilitation case study (where "fatigue" acted as a biasing contextual feature). The results highlight several major advantages:

1. Linear Scaling and Massive Speedups The authors prove that cubic complexity is not required to achieve rigorous guarantees. SBP achieves $\mathcal{O}(t)$ complexity, scaling linearly with the number of tests. For 10,000 iterations, SBP executes in a fraction of a second, whereas LGP's execution time becomes unmanageable.

2. The "Goldilocks" Kernel Kernel width is a delicate balancing act. A kernel that is too wide "overshares" and creates an overly smoothed function, while one that is too narrow fails to share enough information, resulting in a noisy estimate. SBP's dynamic scaling perfectly balances this tradeoff.

SBP performance in a 1D static setting. The middle panel shows how different kernel widths affect the smoothness of the posterior estimate. The right panel highlights the massive speed advantage of SBP over LGP.

3. Superiority in Contextual Settings Empirical results perfectly match the predicted $L_2$ convergence rates ($\mathcal{O}(t^{-2/(d+2)})$). More importantly, in dynamic settings, CSBP significantly outperforms LGP. Because LGP treats context as an extra dimension, its error decays much more slowly than CSBP, which treats context as part of the inference engine.

L2 error comparison. In the dynamic setting (right), CSBP converges much faster than LGP because it handles contextual features more efficiently without adding dimensions.

Limitations and Future Work

Currently, the CSBP framework is specifically designed for linear contextual influences ($A\pi + B$). While this covers many practical use cases like bias and scaling, it does not account for more complex, non-linear relationships.

Future work could generalize these results to polynomial transformations of the success probability. Additionally, there is strong potential for applying SBP to active learning and "bandit" problems, where an algorithm must strategically decide which points to test next to learn the function as efficiently as possible.

Summary updated

Abstract

We study the fundamental problem of learning an unknown, smooth probability function via point-wise Bernoulli tests. We provide a scalable algorithm for efficiently solving this problem with rigoro...
BibTeX
@inproceedings{rolland2019efficient,
  author = {Paul Rolland and Ali Kavis and Alexander Immer and Adish Singla and Volkan Cevher},
  title = {{Efficient learning of smooth probability functions from Bernoulli tests with guarantees}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=LgwLX_-Y67i},
}
Figure