用概率模型优化二分搜索，让搜索更高效。
Bayesian Binary Search
- 基于概率密度划分搜索区间，而非传统中点
- 在模拟和比特币闪电网络实测中效率显著提升
- 支持多种机器学习方法，适合高维或复杂分布场景
我们提出贝叶斯二分搜索（BBS），一种新型的、基于概率的二分搜索变体。BBS 利用机器学习/统计技术估计搜索空间的概率密度，并将传统的中点分割改为依据概率密度进行划分，使搜索过程受学习到的分布引导。密度估计可灵活采用监督式概率模型（如高斯过程回归、贝叶斯神经网络、分位数回归）或无监督算法（如高斯混合模型、核密度估计（KDE）、最大似然估计（MLE））。我们在多种分布的模拟数据上验证了BBS的显著效率提升，并在真实场景——比特币闪电网络通道余额探测中成功部署，实现生产级应用。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。