Netflix Prize: Forum

Forum for discussion about the Netflix Prize and dataset.

You are not logged in.

Announcement

Congratulations to team "BellKor's Pragmatic Chaos" for being awarded the $1M Grand Prize on September 21, 2009. This Forum is now read-only.

#1 2008-05-15 14:38:31

symbol1
Member
Registered: 2008-03-25
Posts: 18

Source code for 0.9046

http://code.google.com/p/nprize/
The only real contribution I made is to add a step to the global base-line removal:
For each user entry, remove correlation with the number of entries that same user made on the same day.
See the README for full information.

Last edited by symbol1 (2008-05-15 14:38:50)

Offline

 

#2 2008-05-16 14:52:07

Newman!
Member
From: BC, Canada
Registered: 2006-12-26
Posts: 168
Website

Re: Source code for 0.9046

symbol1 wrote:

The only real contribution I made is to add a step to the global base-line removal:
For each user entry, remove correlation with the number of entries that same user made on the same day.
See the README for full information.

How much does this improve the RMSE ?
And thanks for posting the code.


When you control the mail, you control... information !

Offline

 

#3 2008-05-16 16:03:45

symbol1
Member
Registered: 2008-03-25
Posts: 18

Re: Source code for 0.9046

I got a RMSE of 0.9569 for my base line.
I failed to mention that I also changed the order in which the BellKor steps are performed. See definition of defaultmethods in ubaseline1.c for details.
My code can also reproduce the BellKor paper by running:
utest0b1 -bl 0 -bl 1 -bl 2 -bl 3 -bl 4 -bl 5 -bl 6 -bl 7 -bl 8 -bl 9 -a -sq data/t.txt
This gave a RMSE of 0.9612
Small but significant improvement.
HTH

Offline

 

#4 2008-05-16 19:51:48

blednotik
Member
Registered: 2007-02-07
Posts: 99

Re: Source code for 0.9046

Thank you for the contribution!  By the way, I got the RMSE of 0.9494 on removal of global effects.

Last edited by blednotik (2008-05-16 19:53:44)

Offline

 

#5 2008-05-16 21:36:52

chef-ele
Member
Registered: 2006-10-31
Posts: 124

Re: Source code for 0.9046

Once again, thanks for sharing that code!

symbol1 wrote:

For each user entry, remove correlation with the number of entries that same user made on the same day.

That's an interesting effect. I haven't gone through the code closely yet, but I have one  question: Is there one correlation calculated for each user, or one global correlation applied to each user?  (if it's the former, are there any sparsity corrections?) 

To look into the aggregate effect (_not_ per customer), I had once made  this plot. On average, it looks like the more ratings a customer submits in a day, the higher the ratings they give (by up to ~0.15 stars). However, I suppose individual customers might vary from this aggregate pattern.  Anyway, I'll have to go through the code & check this out.

Last edited by chef-ele (2008-05-17 05:48:42)

Offline

 

#6 2008-05-17 05:04:27

symbol1
Member
Registered: 2008-03-25
Posts: 18

Re: Source code for 0.9046

The correlation is computed separately for each user with an alpha of 180 and then applied to that user. (see function timecorr2 in ubaseline1.c)

Offline

 

#7 2008-05-17 06:02:08

sogrwig
Member
Registered: 2007-01-31
Posts: 189

Re: Source code for 0.9046

I'm trying to modify you code (THANKS!) to export the probe results as well, with no luck so far.

I created a probe.bin file by modifying your "qualify2bin.py". The generated file size is 5769084, so I modified netflix.h with this value dived by 4:

Code:

#define NPROBE_SIZE (1442271)

Then, in utest.c, I added a command line parameter:


Code:

    else if(!strcmp(argv[i],"-sp"))
        fname_probe=argv[++i];

and then:


Code:

    if(fname_probe) {
        FILE *fp=fopen(fname_probe,"w");
        char *probe_path="data/probe.bin";
        unsigned int *probe=malloc(NPROBE_SIZE*4);
        load_bin(probe_path,probe,NPROBE_SIZE*4);
        unsigned int *q=probe;
        while (q<(probe+NPROBE_SIZE)) {
            int m=*q++;
            fprintf(fp,"%d:\n",m+1);
            int l=*q++;
            int j;
            for(j=0;j<l;j++) {
                int u=*q++;
                int base2=useridx[u][0]+useridx[u][1]+useridx[u][2];
                int d2=+useridx[u][3];
                int k;
                for(k=0;k<d2;k++) {
                    if((userent[base2+k]&USER_MOVIEMASK) == m)
                        break;
                    //lg("%d\n",userent[base2+k]&USER_MOVIEMASK);
                }
                if(k==d2) error("Bad probe %d %d\n",m,u);
                fprintf(fp,"%.1f\n",8.-err[base2+k]);
            }
        }
        fclose(fp);
    }

What I get is:

-------------------------------------------------------
Sat May 17 16:01:33 2008
utest0b1 -l 0 -le data/7.bin -sp data/my_probe_t.txt
Loading data/user_index.bin
Train=99072112 Probe=1408395 Qualify=2817131
Loading data/user_entry.bin
Loading data/7.bin
Clipping errors
RMSE Train 0.686393 (-245.7%) Probe 0.913855 (-209.4%) Both 0.690099 (-244.9%)
Clipping errors
RMSE Train 0.686393 (0.0%) Probe 0.913855 (0.0%) Both 0.690099 (0.0%)
Loading data/probe.bin
Bad probe 0 15698
---------------------------------------------------------

What am I missing here ?

Offline

 

#8 2008-05-17 13:01:17

symbol1
Member
Registered: 2008-03-25
Posts: 18

Re: Source code for 0.9046

You can get RMSE results (not the t.txt files) for the "probe" without any modification to my original code by removing the "-a" parameter from the command line.

Last edited by symbol1 (2008-05-17 13:01:49)

Offline

 

#9 2008-05-17 13:25:22

symbol1
Member
Registered: 2008-03-25
Posts: 18

Re: Source code for 0.9046

As for the code, try

Code:

d2=useridx[u][2];

instead of

Code:

d2=+useridx[u][3];

Offline

 

#10 2008-05-17 15:14:49

sogrwig
Member
Registered: 2007-01-31
Posts: 189

Re: Source code for 0.9046

symbol1 wrote:

As for the code, try

Code:

d2=useridx[u][2];

instead of

Code:

d2=+useridx[u][3];

It didn't work... Still the "bad file" warning came up.


This worked in generating the file without the warning:

Code:

                int base2=useridx[u][0]+useridx[u][1];//+useridx[u][2];
                int d2=useridx[u][2];

But the probe.txt was full of scores like 9.2, 7.2, etc....
I have no idea what this indexes are... Can you see where the error is now ?

Offline

 

#11 2008-05-17 18:08:53

symbol1
Member
Registered: 2008-03-25
Posts: 18

Re: Source code for 0.9046

useridx[u][0] is the start location for user's "u" in the vector of predictions errors ("err")
and in the vector of inputs ("userent".)
useridx[u][1],[2],[3] are the number of training, probe and qualify  entries for that user respectively.
So you were correct in the way you calculated base2 to point to start of probe.
What is missing is changing

Code:

fprintf(fp,"%.1f\n",8.-err[base2+k]);

which is the way I keep "error" information for qualified entries to

Code:

int r=(userent[base2+k]>>USER_LMOVIEMASK)&7; // the actual ranking, zero based
doble p=r-err[base2+k]; // convert error back to prediction
p+=1.; // convert zero base to 1 base.
fprintf(fp,"%.1f\n",p);

Hope that this time it will work, if not, perhaps you would want to email me directly.

Offline

 

#12 2008-05-18 04:00:51

sogrwig
Member
Registered: 2007-01-31
Posts: 189

Re: Source code for 0.9046

This is it!

Thanks a lot smile

Offline

 

#13 2008-05-19 14:14:34

Aron
Member
Registered: 2006-10-02
Posts: 186

Re: Source code for 0.9046

chef-ele wrote:

To look into the aggregate effect (_not_ per customer), I had once made  this plot.

If you look at NumberOfRatingsOnGivenDay vs. PredictionErrorAfterDoubleCentering.. you get a very mild *downward* slope that is essentially noise when you try to use it for adjusting probe predictions. So essentially the information in your chart above disappears when you do the double centering. This means, more than likely, that people who rate a lot of movies in a given day probably are picking better movies on average though I haven't looked at the exact cause.

At least that's what I found.

Offline

 

#14 2008-05-19 17:41:21

symbol1
Member
Registered: 2008-03-25
Posts: 18

Re: Source code for 0.9046

I found the effect to be strongest when it is performed per user and not globally as chef-ele did. Also I found the effect to work better after double centering. This worked both for probe and qualify results so I guess it is not noise.

To get the best results I've changed the order given by BellKor (see Improved Neighborhood-based Collaborative Filtering). I performed double centering followed by "User×Movie average", followed by "User×Movie support" and only then the above day correlation which was then followed by "Movie×User average" followed by all the other steps given by BellKor.

Last edited by symbol1 (2008-05-19 17:48:11)

Offline

 

#15 2008-05-20 09:15:55

chef-ele
Member
Registered: 2006-10-31
Posts: 124

Re: Source code for 0.9046

symbol1 wrote:

I found the effect to be strongest when it is performed per user and not globally as chef-ele did. Also I found the effect to work better after double centering.

Thanks for the feedback.  You are correct, I didn't double-center the data or remove any global effects before making that graph -- but doing so would have made for a better plot. So I'll have to try that.

Offline

 

#16 2008-05-20 10:08:07

symbol1
Member
Registered: 2008-03-25
Posts: 18

Re: Source code for 0.9046

Also try to do it per user and not globally for all users:
I've computed for each user (u) and movie (i) how many entries user u made on the same day in which she entered movie i. (lets call this Xui) and I then used this variable as described in section 3.1 of "Improved Neighborhood-based Collaborative Filtering" by BellKor with an ALPHA of 180. see function timecorr2 in

Last edited by symbol1 (2008-05-20 10:09:04)

Offline

 

#17 2008-05-21 10:45:07

Aron
Member
Registered: 2006-10-02
Posts: 186

Re: Source code for 0.9046

I can get a drop from the double centering RMSE of .9841 to .9767- 9777 (depending on approach) by adjusting the predictions by the daily average for a user.

There are (at least) three alternate explanations for the effect. One explanation is that the movies selected for a given day are going to vary statistically based on that user's preference. Some days they will select more movies that they have a marginal preference for than others.

A second explanation would be that the user simply had a different mood, or perhaps a different conception of how they wanted to use the rating system. In reality, I'm sure its a combination.

A third explanation might be that the account is shared by different users with wildly different rating styles and this is likely (when it happens which might be rare) to somewhat account for that.

The problem is that the first explanation is likely to get accounted for by a factorization approach. If they rate high on anime titles, then factorization will learn this. On a day where they rate a lot of anime, it is more probable that the probe movie will be anime. The adjustment of the prediction based on a higher daily average simply correlates with the increased probability that the probe movie is also anime. The factorization approach is actually better because if it turns out NOT to be anime than it won't make a needless adjustment.

However, more damaging is that if you reduce the residuals on that day (by subtracting the daily average) you could quite easily be obscuring just how much that user likes anime, to the detriment of the accuracy of that user's features.

So there needs to be some kind of factor analysis to seperate these two factors. Not sure  how to do that precisely but I suspect that blind merging of the results of both models has a similar effect and that's why it works. This same argument likely applies to just about any approach to baselines (you weaken the subsequent factorization by partially subtracting the signal early).

Is there a way to divide these factors more reliably? How about some kind of iterative approach between factorization and these alternate factors?

Last edited by Aron (2008-05-21 10:53:01)

Offline

 

#18 2008-05-27 01:13:59

sogrwig
Member
Registered: 2007-01-31
Posts: 189

Re: Source code for 0.9046

Once again thanks for the excellent code. A few more questions:

a) You only use one decimal point in the qualifying file that is submitted to NF. I increased this to 4 decimal points, but despite the added accuracy the quiz rmse was higher. Any idea why this happens? Did you decide to stick to one decimal point after experimentation or is there some kind of logic behind this?



b) In usvdbkw1.c you mention:

  /* Facorization based estimation as described in section 4.3 of cf.pdf
   * With time based weights
   */

but in bellkor's paper in 4.3 they describe their method without the use of any weighting. Then in section 4.4 they extend this method with weighting, where they say that

We use here an inverse power of the Euclidean distance, but other similarity measures can be applied as well.

Have you improved on the 4.3 method by adding weighting or is it really 4.4 that you have implemented and why did you choose time based weights?

Offline

 

#19 2008-05-27 05:55:43

symbol1
Member
Registered: 2008-03-25
Posts: 18

Re: Source code for 0.9046

a) Interesting finding, I rounded to one digit just because that is how the example from Netflix looked like. My guess is that the result is biased and by truncating it I accidentally lowered the average and removed some of the bias. You can test this by removing the global average of your result with:

Code:

utest0b1 -l 11 -a -le data/biased.bin -se data/unbiased.bin

b) My time weight averaging is an addition to 4.3 (of "Modeling Relationships at Multiple Scales to Improve Accuracy of Large Recommender Systems") which is not covered anywhere. However, the usage of time weights was discussed many times so I can't claim this. I tried several time weights and what I have in the code is the only one that worked for me.

In general my code is not always identical to the papers but is based on them. I had problems making 4.4 work, and in general I didn't publish any code that did not gave results. If you want I can publish the non working code I have, and hopefully someone will be nice enough to publish back her/his corrections (and perhaps even merge it into the same open code repository.)

Offline

 

#20 2008-05-27 06:30:58

sogrwig
Member
Registered: 2007-01-31
Posts: 189

Re: Source code for 0.9046

symbol1 wrote:

In general my code is not always identical to the papers but is based on them. I had problems making 4.4 work, and in general I didn't publish any code that did not gave results. If you want I can publish the non working code I have, and hopefully someone will be nice enough to publish back her/his corrections (and perhaps even merge it into the same open code repository.)

I think this is not a bad idea. One more file in the repository with a big warning (even in the filename) would not be a bad idea, because it might be something really trivial for someone to work out.

Offline

 

#21 2008-05-27 08:00:25

symbol1
Member
Registered: 2008-03-25
Posts: 18

Re: Source code for 0.9046

I made a mistake. The command line should be

Code:

utest0b1 -lb 11 -l 1 -a -le data/biased.bin -se data/unbiased.bin

Offline

 

#22 2008-05-27 08:06:53

sogrwig
Member
Registered: 2007-01-31
Posts: 189

Re: Source code for 0.9046

symbol1 wrote:

I made a mistake. The command line should be

Code:

utest0b1 -lb 11 -l 1 -a -le data/biased.bin -se data/unbiased.bin

lb 11 = ???

Are you sure about it? I don't have you code in front of me right now to test but this seems like an unknown parameter.

Offline

 

#23 2008-05-27 08:22:16

symbol1
Member
Registered: 2008-03-25
Posts: 18

Re: Source code for 0.9046

Sorry, my mistake again! It should be -bl 11 not -lb 11.
The code for it is at the end of ubaseline1.c

Offline

 

#24 2008-05-28 02:29:24

sogrwig
Member
Registered: 2007-01-31
Posts: 189

Re: Source code for 0.9046

A couple more questions (thanks again for been so helpful, I on the other hand apologize for asking so many questions smile I admit I have not studied the code as I should)


a) about paterek NSVD. You have implemented NSVD1 but not NSVD2. I have not idea if nsvd2 is just a simple variation of 1, OR requires coding from scratch? Did you try it and failed for some reason or you have not tried it at all?

b) Do you think it would be possible to modify your code and have batch training of all the features? (the reason why I'm asking is because some have mentioned that in some cases it helps to lower the rmse and I'm not sure how I can do it on your code because I don't really understand all these indexes you have - yet)

Offline

 

#25 2008-05-28 04:34:23

symbol1
Member
Registered: 2008-03-25
Posts: 18

Re: Source code for 0.9046

I tried NSVD2, but for some reason I didn't got good results. The indexing are not that hard so the main problem is solving the numeric optimization problems

Offline

 

Board footer

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson