# Bayesian Binary Search
## 2 Methodology
### Probabilistic Bisection Step
By integrating these spectral properties, machine learning models can effectively recognize and utilize global characteristics, enhancing performance in tasks like node classification and community detection. #### 3.3.5 Concatenated Prediction ML Model

Our model predicts \(p_{(u,v)}\) as a function of the concatenation of the features of the source and destination nodes as well as edge features:

\[\hat{p}_{(u,v)}=\text{RF}(x_{u}||x_{v}||e_{(u,v)})\]

#### 3.3.6 Model Training Details and Performance

We set aside 10% of the observed \(y_{(u,v)}\) as our test set and 10% as our validation set. The RF model trained for balance prediction has an MAE of 1.08, an R of 0.612, and \(R^{2}\) of 0.365. For the BBS experiments, we use the predictions on the validation set (89 channels). For validation set channels, we feed the predictions of each tree in the ensemble (100) into a Kernel Density Estimation (KDE) process to construct the search space PDF. Using these constructed PDFs, we compare BBS with basic binary search in measuring how many probes it would take to ascertain the balance of a given channel. ## 4 Discussion

Our experimental results demonstrate the potential of Bayesian Binary Search (BBS) as a promising alternative to classical binary search/bisection, particularly in scenarios where the search space exhibits non-uniform distributions and is costly to access. The performance improvements observed in both simulated environments and real-world applications, such as probing payment channels in the Bitcoin Lightning Network, highlight the promise of BBS (Figures 1 and 2, Tables 1 and 2). However, it is important to consider these findings in a broader context and acknowledge the limitations and implications of our work. The results observed here are also consistent with some theoretical analysis from [24, 25], and the BBS framework provides a novel perspective on how probabilistic machine learning techniques can be used to achieved these efficiencies. ### Theoretical Alignment and Performance Gains

The superior performance of BBS over classical binary search in non-uniform distributions aligns with our theoretical expectations. By leveraging probabilistic information about the search space, BBS can make more informed decisions at each step, leading to faster convergence on average. This is particularly evident in our simulated experiments with skewed distributions, where BBS consistently required fewer steps to locate the target. The ability of BBS to adapt to the underlying distribution of the search space represents an advance in the design of search algorithms, and a fusion of search theory and probabilistic machine learning/statistical learning. ### Real-World Application and Implications

In the context of the Bitcoin Lightning Network, the improvement in probing efficiency could have significant practical implications. Faster and more accurate channel capacity discovery can enhance routing algorithms, potentially leading to improved transaction success rates. Crucially, probes in the Lightning Network consume network-wide computational resources, as each probe requires processing by multiple nodes along potential payment routes. By using BBS to enhance probe efficiency, we effectively reduce unnecessary network load, akin to removing spam from the system. This reduction in network overhead could lead to improved overall network performance and scalability. ### Limitations and Challenges

Despite the promising results, several limitations of our study should be acknowledged:

1. **Computational Overhead:** The improved search efficiency of BBS comes at the cost of increased computational complexity, particularly in the PDF estimation step. This overhead may offset the reduction in search steps for certain applications, especially those dealing with small search spaces or requiring extremely fast operation. 2. **PDF Estimation Accuracy:** The performance of BBS is heavily dependent on the accuracy of the PDF estimation.