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

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

• As it stands this is more suitable as a comment than an answer. Could you give an outline of the algorithm here, please? Commented Oct 9, 2013 at 15:02
• Ok, I did it. Also, fixed an bug on my page. Commented Oct 9, 2013 at 19:15
• I think the code needs a w'[j] = w[i] to go with the a'[j] = a[i]. Commented Oct 16, 2013 at 0:52
• Hi, the link expired
– JoZ
Commented Aug 4 at 20:58
• @JoZ - yes, now the best you can do is web.archive.org/web/20170101113338/http://stat.wikia.com/wiki/… Commented Aug 5 at 21:21