Crate probabilistic_bisector 

This crate implements linear bisection for finding the root of a one-dimensional stochastic function.

Root finding is a fairly simple problem when the function we are looking for the root of is deterministic. We can just use a linear bisection algorithm, or something more sophisticated like Brent’s method.

In a general stochastic root finding method our goal is still the same: we want to locate a point x such that the optimisation function g(x) = 0 when the optimisation function can only be observed in the presence of noise.

This module achieves this by implementing the probabilistic bisection algorithm. This queries the function g as to whether the root lies to the left or right of a prescribed point t. As a consequence of observational noise each query has probability 1 - p(t) of being incorrect. To account for this the algorithm updates a probability distribution which attempts to represent knowledge of the true root x. A full description is available in the PhD thesis of R. Waeber.

use probabilistic_bisector::{Bisectable, ProbabilisticBisector, GenerateBuilder, Confidence,
ConfidenceLevel};

struct Linear {
    gradient: f64,
    intercept: f64,
}

impl Bisectable<f64> for Linear {
    // This function can be noisy!
    fn evaluate(&self, x: f64) -> f64 {
        self.gradient * x + self.intercept
    }
}

let problem = Linear { gradient: 1.0, intercept: 0.0 };

let domain = -1.0..1.0;
let bisector = ProbabilisticBisector::new(domain, ConfidenceLevel::ninety_nine_percent());

let runner = bisector
    .build_for(problem)
    .configure(|state| state.max_iters(1000).relative_tolerance(1e-3))
    .finalise()
    .unwrap();

let result = runner.run().unwrap().result;

assert!(result.interval.contains(0.0));

Structs

BisectorState

CombinedConfidenceInterval

ConfidenceLevel

The degree of confidence associated with a value to be computed.

ProbabilisticBisector

Enums

Error

Sign

Traits

Bisectable

Confidence

GenerateBuilder