4 ms·
Aside: bisecting flakes doesn't have to involve repeated runs. You can reformulate bisection as an information probing operation, expanding the scope to support
by Scaevolus 2y ago
Aside: bisecting flakes doesn't have to involve repeated runs. You can reformulate bisection as an information probing operation, expanding the scope to support noisy benchmarks or low-probability flakes. Bayesian inference narrows down the probable range of the failure for each new observation, and you can choose new probes to maximize information gain-- or even run them in parallel to minimize the total time.
You do have to provide flake rate probability to do the probability estimates, but even roughly correct rates work fine. Running bisects assuming a 5% chance of getting a false positive or negative barely adds more steps and greatly improves robustness.
The math is pretty simple too-- my old prototype might still be in Google's monorepo; I should reimplement it for the open source world.
- rsc 2y agoIndeed. Something like this is what I intend to do when I get some time.
- eru 2y agoCould you briefly sketch out the math (or point to a sketch) so that other people can pick it up? I'm quite interested! (I suspect you could get pretty far with a Monte Carlo simulation, and that would let you bypass most of the math anyway.)
- ajb 2y agoHere is a doc explaining a Bayesian search algorithm; not sure if it's precisely what GP has in mind. https://github.com/Ealdwulf/BBChop/blob/master/BBChop/doc/BayesianSearch_Debugging.pdf https://github.com/Ealdwulf/BBChop/blob/master/BBChop/doc/Ba... (Edit- had wrong link originally)
- eru 2y agoThanks!
- dwattttt 2y agoFor Bayesian Inference, the example in the Wikipedia article is good (who doesn't like cookies?): https://en.m.wikipedia.org/wiki/Bayesian_inference#Examples https://en.m.wikipedia.org/wiki/Bayesian_inference#Examples When gathering more evidence, you'd use your new belief about which cookie bowl Fred has as P(H1)=0.6 and P(H2)=0.4
- eru 2y agoThat just explains Bayesian inference in general, which is useful, but not what I'm after. I was specifically interested in the application to binary search / bisection in the presence of flaky tests.
- dwattttt 2y agoYou apply the same process, but your hypotheses are "bug is before/after this bisection point". Your "probability of evidence given hypothesis before/after" are where you incorporate your guess about the tests flakiness. Still works even if you don't have "true" numbers for the tests flakiness, just won't converge as quickly
- efdb 2y ago[flagged]
- efdb 2y agoJ
- efdb 2y agoH
- jhfdbkofdchk 2y agoThe 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 https://ieeexplore.ieee.org/document/1057832 Here's a nice presentation on an analysis of the method, references start on slide 47 https://people.orie.cornell.edu/pfrazier/Presentations/2014.01.Lancaster.bisection.pdf 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/thresholds/bisect.py https://github.com/choderalab/thresholds/blob/master/thresho...
- eru 2y agoThanks!