1D weighted Isotonic Regression (PAV): a simple description of the algorithm

Question

I have to use IsotonicRegression class from scikit-learn with non-uniform point weights: in method IsotonicRegression.fit parameter sample_weight!=None.

I roughly know how the weighted PAV algorithm works, but I don't want to insert the rough description into my article. I just want to give some reference. But I could not find any suitable description of weighted PAV simple enough to be understandable by non-mathematicians, best of all — in the form of some pseudocode.

Can someone help me?

Answer 1

A couple of years ago I wrote an article about isotonic regression. Below is the link to the description of PAVA.

http://stat.wikia.com/wiki/Isotonic_regression#Pool_Adjacent_Violators_Algorithm

If $a$ is vector of input values, $w$ is vector of weights, $y$ is vector of output values minimizing $\sum_i w_i (y_i-a_i)^2$ subject to $y_1\leq ...\leq y_n$, the algorithm is:

Set a'[1]=a[1], w'[1]=w[1], j=1, S[0]=0, S[1]=1
For i=2 to n do:
    j++
    a'[j] = a[i]
    w'[j] = w[i]
    while j>1 and a'[j] < a'[j-1] do
        a'[j-1] = (w'[j]*a'[j] + w'[j-1]*a'[j-1]) / (w'[j] + w'[j-1])
        w'[j-1] += w'[j]
        j--
    S[j] = i
for k=1 to j do
    for l=S[k-1]+1 to S[k] do
        y[l] = a'[k]

Here S defines to which old points each new point corresponds.

PS: now (7 Aug 2024) when the link above is expired, the correct link is https://en.wikibooks.org/wiki/Isotonic_regression#Pool_Adjacent_Violators_Algorithm