Bayesian Binary Search
We present Bayesian Binary Search (BBS), a novel probabilistic variant of the classical binary search/bisection algorithm. BBS leverages machine learning/statistical techniques to estimate the probability density of the search space and modifies the bisection step to split based on probability density rather than the traditional midpoint, allowing for the learned distribution of the search space to guide the search algorithm. Search space density estimation can flexibly be performed using supervised probabilistic machine learning techniques (e.g., Gaussian process regression, Bayesian neural networks, quantile regression) or unsupervised learning algorithms (e.g., Gaussian mixture models, kernel density estimation (KDE), maximum likelihood estimation (MLE)). We demonstrate significant efficiency gains of using BBS on both simulated data across a variety of distributions and in a real-world binary search use case of probing channel balances in the Bitcoin Lightning Network, for which we have deployed the BBS algorithm in a production setting.
Code (0)
등록된 구현이 없습니다.
Tasks
Density Estimationquantile regressionregressionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Efficient computation of predictive probabilities in probit models via expectation propagation
Binary regression models represent a popular model-based approach for binary classification. In the Bayesian framework, computational challenges in the form of the posterior distribution motivate still-ongoing fruitful r…
Binary ClassificationFormregressionBCTH: A Novel Text Hashing Approach via Bayesian Clustering
Similarity search is to find the most similar items for a certain target item. The ability of similarity search at large scale plays a significant role in many information retrieval applications, and thus has received mu…
ClusteringInformation RetrievalRetrievalDichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networks
We present a comprehensive study of multilayer neural networks with binary activation, relying on the PAC-Bayesian theory. Our contributions are twofold: (i) we develop an end-to-end framework to train a binary activated…
Generalization BoundsA Bayesian non-parametric method for clustering high-dimensional binary data
In many real life problems, objects are described by large number of binary features. For instance, documents are characterized by presence or absence of certain keywords; cancer patients are characterized by presence or…
ClusteringSpecificityVocal Bursts Intensity PredictionBayesian Optimization with Binary Auxiliary Information
This paper presents novel mixed-type Bayesian optimization (BO) algorithms to accelerate the optimization of a target objective function by exploiting correlated auxiliary information of binary type that can be more chea…
Bayesian OptimizationReinforcement LearningVocal Bursts Type Prediction