Recursive Estimation of Quantiles

Quantiles are fundamental in statistics and machine learning. In this project we will explore new algorithms that are able to estimate quantiles in real-time.
Master

The traditional approach to estimate the quantile associated with some probability q, is to find the data point (or an average of two) such that the portion of points with a value less than the selected points is close to q. A substantial disadvantage with this approach is that it cannot recursively update the quantile estimate. For example if we receive more data.

Incremental quantile estimators are an interesting group of methods that are able to recursively estimate quantiles. The methods are based on making small updates of a quantile estimate every time a new data point is received. The methods are quite intuitive. If the value of the received data point is above (below) the current quantile estimate, the estimate will be increased (decreased). The step sizes are adjusted to ensure that the quantile estimate will converge to the true quantile.

In this project we will explore some new ideas on how to develop incremental quantile estimates. We will analyze the properties of the suggested estimators using computer simulations.

Goal

Develop new incremental quantile estimators, and evaluate their efficiency using computer simulations.

Learning outcome

Quantile estimation
Statistics

Qualifications

Hard working and motivated. Interested in learning (the rest can be learned during the thesis work)

Supervisors

  • Michael Riegler
  • Hugo Hammer
  • Anis Yazidi - OsloMet

References

Yazidi, A., & Hammer, H. (2017). Multiplicative update methods for incremental quantile estimation. IEEE transactions on cybernetics, 49(3), 746-756.

Contact person