Efficient learning of smooth probability functions from Bernoulli tests with guarantees

Paul Rolland, Ali Kavis, Adish Singla, Volkan Cevher

TL;DR

This paper introduces a novel algorithm, the Smooth Beta Process (SBP), for efficiently learning smooth probability functions from Bernoulli test outcomes. SBP offers provable convergence guarantees and handles contextual features that influence test results, outperforming existing methods in both efficiency and accuracy, especially in scenarios with limited data or complex dependencies.

What Problem Does This Paper Address?

The core challenge addressed is learning an unknown, smooth probability function, denoted as $\pi(x)$, from a series of point-wise Bernoulli tests. Imagine trying to understand the probability of success for a user clicking an ad based on various features of the ad and user. Each test (e.g., showing an ad) yields a binary outcome (click or no click), and we want to infer the underlying probability $\pi(x)$ for any given input $x$ (representing ad/user features). A major hurdle is the "curse of dimensionality": to get accurate estimates, especially in high-dimensional feature spaces, we often need a vast number of tests. Existing methods, like Logistic Gaussian Processes (LGP), can be computationally expensive (cubic complexity) or lack theoretical guarantees. Furthermore, real-world scenarios often involve "contextual features" that influence the success probability in ways not captured by a simple $\pi(x)$ model, leading to biased results or requiring complex feature engineering. This paper aims to provide a scalable, theoretically sound, and efficient method that can handle these complexities.

Methods

The paper proposes the Smooth Beta Process (SBP), an algorithm that leverages Beta distributions as conjugate priors for Bernoulli outcomes. The key innovations are:

  • Experience Sharing via Kernel: To overcome the curse of dimensionality and ensure convergence across the entire feature space, SBP employs a kernel function $K(x, x_i)$ to share information from an experiment at point $x_i$ to other points $x$. This is crucial for learning smooth functions, as nearby points are expected to have similar probabilities.
  • Provable Convergence Guarantees: Unlike some prior work, SBP comes with theoretical guarantees. The authors prove that the posterior distribution learned by SBP converges to the true probability function $\pi(x)$ in $L_2$-norm, with rates dependent on the function's smoothness (Lipschitz constant) and the number of experiments.
  • Handling Contextual Features: A significant contribution is the extension of SBP to handle "dynamic settings" where Bernoulli tests are influenced by contextual parameters (e.g., patient fatigue in a clinical trial). The paper introduces modified inference engines that explicitly incorporate these features, providing provable convergence even in these more complex scenarios. This is achieved through Bayesian updates that account for these parameters, leading to algorithms like the Contextual Smooth Beta Process (CSBP).
  • Scalable Inference: SBP is designed for efficiency, with inference complexity scaling linearly ($O(t)$) with the number of experiments $t$, making it suitable for large datasets.

Datasets

The paper uses synthetic datasets for evaluating the algorithms in both static and dynamic settings. For the dynamic setting, they specifically reproduce a case study from Goetschalckx et al. (2011) involving synthetic stroke rehabilitation data to demonstrate the handling of bias. No new benchmark datasets are introduced.

Key Insights and Ideas

  • Smoothness is Key for Sharing: The paper emphasizes that learning smooth functions allows for effective "experience sharing" between nearby data points. This sharing is what enables convergence over the entire feature space, not just at observed points.
  • Kernel Design Matters for Guarantees: The choice of kernel function is not arbitrary; it must be carefully designed (and depend on the number of samples) to ensure theoretical convergence. The paper provides a specific kernel construction that achieves this.
  • Contextual Features as First-Class Citizens: The ability to directly incorporate contextual features into the inference engine, rather than just treating them as additional input dimensions, is a major advantage. This allows for more accurate modeling and faster convergence when these features are important.
  • Bayesian Priors for Efficiency: Using Beta distributions as priors for Bernoulli outcomes provides a natural and computationally tractable way to update beliefs as new data arrives.

Key Results

  • Theoretical Guarantees: The paper provides theoretical guarantees for $L_2$-norm convergence of SBP to the true probability function, with rates dependent on the feature space dimension and the number of experiments ($O(t^{-d/2})$ for static, $O(t^{-1/2})$ in 1D, $O(t^{-1})$ in 2D).
  • Efficient Computation: SBP achieves linear time complexity ($O(t)$) for inference, significantly outperforming cubic-time methods like LGP.
  • Superior Performance with Context: In numerical experiments, SBP and its contextual variant (CSBP) demonstrated superior performance over LGP and CCBP, especially in handling contextual features and in low-data regimes. CSBP showed better accuracy and faster convergence in dynamic settings.
  • Convergence in $L_1$ and Bayes Risk: The paper extends the theoretical results to $L_1$ norm convergence and Bayes risk for classification tasks, showing that the learned classifier converges to the optimal Bayes classifier.

Limitations and Future Work

  • Specific Contextual Model: The current framework primarily models contextual influences of the form $A_i \pi(x_i) + B_i$. While generalized to noisy versions, more complex functional relationships between context and probability might require further extensions.
  • Certainty Invariance Assumption: For the dynamic setting, the paper often relies on a "certainty invariance assumption" (or its inverse) for simplifying analysis. While practical workarounds are discussed, it's a simplifying assumption.
  • Future Directions: The authors suggest generalizing the contextual influence model to arbitrary polynomial transformations of $\pi(x)$. They also propose exploring SBP's applicability to other domains like risk tracking, bandit settings, and active learning, indicating a broad potential for this framework.

Summary updated

Abstract

We study the fundamental problem of learning an unknown, smooth probability function via pointwise Bernoulli tests. We provide a scalable algorithm for efficiently solving this problem with rigorous guarantees. In particular, we prove the convergence rate of our posterior update rule to the true probability function in L2-norm. Moreover, we allow the Bernoulli tests to depend on contextual features and provide a modified inference engine with provable guarantees for this novel setting. Numerical results show that the empirical convergence rates match the theory, and illustrate the superiority of our approach in handling contextual features over the state-of-the-art.
BibTeX
@inproceedings{rolland2019efficient,
  author = {Paul Rolland and Ali Kavis 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