2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
3
  • $\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 '13 at 15:02
  • $\begingroup$ Ok, I did it. Also, fixed an bug on my page. $\endgroup$ – user31264 Oct 9 '13 at 19:15
  • $\begingroup$ I think the code needs a w'[j] = w[i] to go with the a'[j] = a[i]. $\endgroup$ – Ray Koopman Oct 16 '13 at 0:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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