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?


1 Answer 1


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


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:
    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]
    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.

  • $\begingroup$ As it stands this is more suitable as a comment than an answer. Could you give an outline of the algorithm here, please? $\endgroup$
    – Glen_b
    Oct 9, 2013 at 15:02
  • $\begingroup$ Ok, I did it. Also, fixed an bug on my page. $\endgroup$
    – user31264
    Oct 9, 2013 at 19:15
  • $\begingroup$ I think the code needs a w'[j] = w[i] to go with the a'[j] = a[i]. $\endgroup$ Oct 16, 2013 at 0:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.