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

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?

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

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