Re:Hash-Based Bisect Debugging in Compilers and Runtimes
by jhfdbkofdchk on Friday July 19, 2024 @07:02AM
(#41004888)
The Probabilistic Bisection Algorithm by Horstein, original paper is "Sequential transmission using noiseless feedback," IEEE Trans. Inform. Theory, 9(3):136–143. https://ieeexplore.ieee.org/document/1057832
Here's a nice presentation on an analysis of the method, references start on slide 47
Paraphrasing the theorem from Jedynak, Frazier, Sznitman (2011):
Suppose [flake probability] is constant, known, and bounded away from 1/2, and we use the entropy loss function. ... The policy that chooses [next test point] at the median of [current posterior distribution] is optimal.
And some python code that implements a version of the analysis
Here's a nice presentation on an analysis of the method, references start on slide 47
https://people.orie.cornell.edu/pfrazier/Presentations/2014....
Paraphrasing the theorem from Jedynak, Frazier, Sznitman (2011):
Suppose [flake probability] is constant, known, and bounded away from 1/2, and we use the entropy loss function. ... The policy that chooses [next test point] at the median of [current posterior distribution] is optimal.
And some python code that implements a version of the analysis
https://github.com/choderalab/thresholds/blob/master/thresho...