3 releases
0.1.5-alpha.0 | Mar 25, 2023 |
---|---|
0.1.4-alpha.0 | Mar 3, 2023 |
0.1.3-alpha.0 | Mar 2, 2023 |
#7 in #estimating
710KB
5K
SLoC
The BisectPercentile
operator in the
caffe2op-bisect
crate is a mathematical operator
used in DSP and machine learning computations to
estimate the x
value at a given y
percentile
within a dataset. This is achieved by iteratively
bisecting the dataset and checking the percentile
of the resulting subsets until the desired y
percentile is reached within a given tolerance.
Note: This crate is currently being translated from C++ to Rust, and some function bodies may still be in the process of translation.
The BisectPercentile
operator takes as input
a tensor representing a dataset, a tensor
representing the percentiles of interest, and an
optional tensor representing the tolerance. It
outputs a tensor representing the x
values
corresponding to the percentiles of interest.
The operator is implemented using the bisection
method and interpolation techniques to efficiently
estimate the percentiles of interest. The
bisection method involves iteratively bisecting
the dataset and selecting the half that contains
the target percentile until the desired tolerance
is reached. Interpolation is used to estimate the
x
value at the target percentile within the
selected half.
The BisectPercentile
operator is useful for
a variety of applications, including outlier
detection, data analysis, and machine learning. It
provides an efficient and accurate method for
estimating percentiles within large datasets.
The caffe2op-bisect
crate also provides the
BisectPercentileOp
and
BisectPercentileOpEpsilon
structs, which
implement the BisectPercentile
operator as
Caffe2 operators. These can be used in conjunction
with other Caffe2 operators to construct deep
neural network architectures for tasks such as
image classification and object detection.
16> thanks! could you please help me understand how the bisection method for estimating percentiles of interest applies within the context of deep neural networks?
The bisection method is a numerical algorithm used to find the root of a function. In the context of estimating percentiles in deep neural networks, the bisection method can be used to find the value of a certain percentile of a given set of values.
More specifically, the BisectPercentileOp in the rust crate caffe2op-bisect implements the bisection method to estimate the specified percentile of a given set of values. The BisectPercentileOp takes in a tensor of values and a percentile, and outputs the estimated value of that percentile.
The algorithm works by first sorting the input tensor of values in ascending order, and then defining a function that takes in a candidate value for the percentile and returns the difference between the number of values in the tensor that are less than or equal to the candidate value and the target percentile. This function can be thought of as a "signed distance" function, where the sign indicates whether the candidate value is too high or too low.
The bisection method then repeatedly bisects the search space by dividing it in half and evaluating the sign of the distance function at the midpoint. Depending on the sign, the algorithm either continues the search in the left or right half of the search space, until the distance function is sufficiently close to zero, indicating that the desired percentile has been found.
In summary, the bisection method can be used to estimate percentiles of interest in deep neural networks by defining a distance function based on the input tensor of values and the target percentile, and iteratively bisecting the search space until the distance function is sufficiently small.
Dependencies
~36MB
~387K SLoC