Netflix Prize: Forum

Bored Bitless · 2007-09-23 13:19:27

Having just made what I expect will be my last submission I wanted to just mention/discuss a few points that some may find useful. For the record I should state that my final quiz score is 0.9021, but some of this may stiill be of interest even if you're doing better than that already.

The 0.9021 score is based purely on tweaking Simon Funk's modified SVD (More accurately known as Greedy Residuals Fitting - I think). So no merging involved.

1) I've already written a discussion on what I called the feature output error curve:

http://tech-singularity.blogspot.com/20 … error.html

However I don't think I mentioned (or emphasised) that better predictions can be achieved by plotting this curve for data that hasn't been trained against (e.g. the probe data) and then applying *that* curve to *all* of your residuals, both the probe residuals and the training data residuals. Over many features this has the effect of over adjusting the training data feature curve which can be observed by plotting the curve for the training data (it becomes more pronounced with each feature and is opposite to the typical probe curve) and by the fact that the training data RMSE doesn't fall by so much (less overtraining).

2) Simon and others have mentioned good values for Simon's regularisation (or feature decay) term being around 0.015. I found that higher values seemed to work better, but this may be due to the the changes I mentioned in (1). The optimal value for my algorithm was 0.03. This not only gives a better probe RMSE for each feature in turn but allows the SVD algorithm to run for many more features before the probe RMSE bottoms out. Further to this I found that decaying in proportion to the square of the feature value gives slightly better results again. The best term here was:

decay = x*0.03 + x^2*0.002

In fact successively higher powers give slightly better results (be careful to flip the sign appropriately when calculating the decay for even powers), near optimal numbers from experimentation came out at:

decay = x*0.03 + x^3*0.006
decay = x*0.03 + x^4*0.018
decay = x*0.03 + x^5*0.054

In the end I plumpted for the x^3 term as it is quick/simple to calculate and the gains to be had from the higher powers was miniscule.

3) Out of interest I ran the SVD algorithm but instead of training each feature for a fixed number of epochs I ran each feature until the probe RMSE stopped falling. Initially I did this to determine the maximum number of features we might hope to extract out of the data. By the end though I was storing the epoch count for each feature and using that when training on the full data set (when doing a 'full' run for generating a qualifying.txt). The number of features you can run for using the modifications above (and some more to come) is about 640, although it may be possible to squueze some more out.

It's worth noting that the probe RMSE curve takes on a flatter shape after about feature 243, a gradual slope downwards rather than the look of an asymptotic curve up to featrue 243. More on that later.

3B) In addition to storing the epoch count per feature I also store the feature error curve calculated against the probe data. I then use those curves durign a 'ful' run against *all* of the data.

4) Simon's december post failed to mention a final step(mentioned in his patent application and later post), which is to go back over each feature and continue training some more. The logic here being that the later features have effectively removed noise from the data (from the point of view of the earlier features). I found that limiting the first pass to 243 features and then performing two additional passed over those features gave a better probe RMSE than simply running one pass with many more features. Thus the later features (post 243) may actually have been picking up left overs from earlier features - RMSE that would have been represented by the earlier features but that was obscured from the training algorithm by noise.

5) When performing those additional passes I again train until probe RMSE stops falling and store the epoch count at each feature for use in the 'full' run. So each feature now has a list of epoch counts associated with it, one for each pass.

6) A slightly better probe RMSE can be achieved by adjusting the feature error curve from (1). First I used a prior mean for each sample point and biased towards that mean depending on sample size. For ratings between 1 and 5 the prior mean is 0, outisde of those ranges the prior is the amount of trimming that would be required to bring a rating back into the valid range.

6B) The feature curve can than be improved further by smoothing it. I used a simple approach of updating each point on the x axis with a weighted average of itself and it's two neighbouring points.

All of the above resulted in a quiz RMSE of 0.9021. Not exactly brilliant but not too bad for what is still a fairly straightforward technique (albeit with some extra bits bolted on) and no blending. Not as good as Simon's quiz score though, ho hum.

One final point. The bellkor paper discussed 10 global effects, the first two of which were effectively identical to Simon Funk's adjusted/better means (AKA double centering). These first two will give a probe RMSE of 0.9840 (with optimal weightings (refered to as alpha in the paper)). I was then able to recreate all of Bellkor's results and in fact improve on them somewhat by tweaking the alpha used for each effect - Bellkor's end RMSE was 0.9657, I got this down to 0.9634. However, all of the global effects bar the first two had a detrimental affect on my SVD algorithm - they resulted in a worse probe RMSE at the end of an SVD run, despite looking better for most of the run.

I suspect that some information has been extracted out of the training data by the global effects that the SVD algorithm could have used more effectively. E.g. consider a time effect - the ratings are seen to rise slightly over time, this could just be that people are being sent films they like more efficiently as time progresses - it does NOT necessarily mean that had a given person watched their films in a different order that they would have given different ratings. Thus by removing the time effects you remove some valuable rating information that may be useful for the SVD algorithm when extracting features, and since each feature is intimately connected to every other feature through the training data matrix, that information is potentially more useful exposed to the SVD than not. Perhaps there is a case for extracting whatever time effects remain /after/ SVD though??

BTW the (near)optimal values for alpha for each global effect are:

movie effect: 22.2, rmse= 1.129623
user effect: 7.06, rmse = 1.052681
user*time(user): 240, rmse = 0.984033
user*time(movie: 150, rmse = 0.980551
movie*time(movie): 2000, rmse = 976308
movie*time(user): 250, rmse = 0.975367
user*movie average: 64, rmse = 0.96629
user*movie support: 150, rmse = 0.965525
movie*user average: 170,000, rmse = 0.964833
movie*user support: 0, rmse = 0.963454

Please note however that for [user*time(user)] and [movie*time(user)] I used the 4th root of time, not the square root. So t^0.25. This gave a lower probe RMSE.

There's loads of other stuff I could write about but hopefully this documents the main points I've come across.

Regards,

BB

Bored Bitless · 2007-09-23 14:53:17

In true Columbo style...just one more thing - If you plot mean rating over time there are a couple of effects apparent. Firstly there is a distinct jump upwards of about 0.1 over just 1 or two days. This I suspect is the point where Netflix changed the descriptions associated with the ratings whcih was mentioned on this forum. I adjusted all data points prior to this point upwards, I could have just increased them all by 0.1 but opted for slightly different offsets for each of the ratings 1-5. If you plot hte proportion of each of the five ratings before and after the swithcover date you will see that some ratings have fallen in proportion, some have risen and by differnign amounts. The offsets I choose reflect those proportional changes - rather than just applying a blanket 0.1 increase to all ratings.

I haven't exhaustively investigated this approach, but it did give a better probe RMSE on the first few features at least so I ran with it.

The other effect is a fairly significant gradual rise in RMSE over time distinct from the abrupt step upwards. This effect seems to have plateaud toward the end of the time period represented by the data set. Overall though it represents approximately another 0.1 rise in RMSE over the course of the data. I would suggest this is due to Netflix recommendations improving.

BB

bbame · 2007-09-23 19:13:35

Thanks Bored Bitless, lots of good stuff in there. I've been down some of those paths myself, which made it very interesting reading for me. A couple of quick observations:

1) I concur that removing certain "global effects" has a detrimental effect on SVD performance. It's a bit like pre-computing some of the SVD features, so unless the method used to remove the global effect is better than the SVD result, there's really no point. In my experiments I have found that the SVD does at least as good a job as whatever methods I've attempted. On the other hand, since the SVD doesn't take dates or what Bellkor calls "support" (at least not explicitly) into account, adjusting the data based on those effects seems to offer some benefit - at least with my particular SVD variant.

2) It's not much help RMSE-wise, but it's interesting to note that there's a distinct difference between pre-DVD-release ratings for a movie and those post-DVD-release. Take a look at movie 3151 (Napoleon Dynamite) for example. Unfortunately only a tiny fraction of the ratings in the qualifying set are pre-release.

I'll probably add more of this trivia later, but I don't have time just now.

YehudaKoren · 2007-09-23 20:50:02

BB,

Thanks for reporting your experience with global effects, which somewhat differs from mine.
Here are my alpha values (which we somehow set 9 months ago...), each followed by the resulting RMSE.

Movie: 25, 1.0527
User: 7, 0.9841
User-time(user): 550, 0.9809
User-time(movie): 150, 0.9786
Movie-time(movie): 4000, 0.9767
Movie-time(user): 500, 0.9759
User-mean(movie): 90, 0.9719
User-support(movie): 90, 0.9690
Movie-mean(user): 50, 0.9670
Movie-support(user): 50, 0.9658

I remember that we could get better results, by replacing "support" with "log(support)". However, for some reason we kind of lost that better model, so we didn't report it in the paper.

As to the more important issue - when to use global effects?

Well, here my experience is that a *powerful* SVD model needs none of the global effects, even not the first two.
However, a kNN model will benefit from all 10 effects. Not surprisingly, as kNN isn't global in its nature.
Also, global effects benefited us in some other models, which are quite global, but probably less powerful than SVD.

Regards,
Yehuda

Bored Bitless · 2007-09-24 12:30:14

Hi bbame,

bbame wrote:
1) I concur that removing certain "global effects" has a detrimental effect on SVD performance.

...

bbame wrote:
On the other hand, since the SVD doesn't take dates or what Bellkor calls "support" (at least not explicitly) into account, adjusting the data based on those effects seems to offer some benefit - at least with my particular SVD variant.

Certainly the SVD has no access to the date info so I think there may be some additional gains to be had from looking for correlations /after/ SVD. I tried with and without a few combinations of global effects but no combination performed better than the double centering that I started out with. It's quite possible I need to go back and reconsider various other parameters in the SVD algorithm though when operating on adjusted data like this - e.g. maybe my decay term is too strong now?

bbame wrote:
2) It's not much help RMSE-wise, but it's interesting to note that there's a distinct difference between pre-DVD-release ratings for a movie and those post-DVD-release. Take a look at movie 3151 (Napoleon Dynamite) for example. Unfortunately only a tiny fraction of the ratings in the qualifying set are pre-release.

Interesting none-the-less. I suspect lots of little effects like this will need to be taken into account to win the main prize. Some of those folks just behind bellkor (and bellkor themselves) might be hungry for ideas like this one

Cheers,

BB

Last edited by Bored Bitless (2007-09-24 12:31:08)

Newman! · 2007-09-24 12:41:21

Bored Bitless and YehudaKoren,

Can you provide any numbers on how much double-centering reduces the RMSE of SVD and KNN ? I've run both algorithms without removing any global effects, and I'm just wondering how much I have to gain from it.

Newman!

Last edited by Newman! (2007-09-24 12:43:29)

Bored Bitless · 2007-09-24 12:53:14

YehudaKoren wrote:
Thanks for reporting your experience with global effects, which somewhat differs from mine.
Here are my alpha values (which we somehow set 9 months ago...), each followed by the resulting RMSE.

No problem, thanks for reporting your numbers also. Probably you have realised by now that I typed mine in wrong. So I'll try again...

-------
movie effect: 22.2, rmse= 1.052681
user effect: 7.06, rmse = 0.984033
user*time(user): 240, rmse = 0.980551
user*time(movie: 150, rmse = 0.978246
movie*time(movie): 2000, rmse = 0.976308
movie*time(user): 250, rmse = 0.975367
user*movie average: 64, rmse = 0.966629
user*movie support: 150, rmse = 0.965525
movie*user average: 170,000, rmse = 0.964833
movie*user support: 0, rmse = 0.963454
-------

I must admit to fine tuning the first two effects to two decimal places, the remaining effects are tuned to the nearest 10-50 or so. I guess small differences early on may result in wildly different optimum values for later effects? Certainly I was surprised to see 170,000 and the 0. Very odd.

YehudaKoren wrote:
I remember that we could get better results, by replacing "support" with "log(support)". However, for some reason we kind of lost that better model, so we didn't report it in the paper.

As to the more important issue - when to use global effects?

Well, here my experience is that a *powerful* SVD model needs none of the global effects, even not the first two.
However, a kNN model will benefit from all 10 effects. Not surprisingly, as kNN isn't global in its nature.
Also, global effects benefited us in some other models, which are quite global, but probably less powerful than SVD.

Thanks for the feedback. Yes I have wondered if double centering may also be removing useful information from the SVD algorithm. My guess would be that an extra offset term per feature value would do well on ratings that have not been double centered. In fact Paterek's paper reports a better result with just such a term, though I'm not sure if he used double centering beforehand or not.

Cheers,

BB

Last edited by Bored Bitless (2007-09-24 12:56:19)

Bored Bitless · 2007-09-24 13:03:48

Hi Newman,

Newman! wrote:
Can you provide any numbers on how much double-centering reduces the RMSE of SVD and KNN ? I've run both algorithms without removing any global effects, and I'm just wondering how much I have to gain from it.

I haven't done a full length SVD run without a global effect for ages. I assume you are removing the global mean from each rating at least? Hmm maybe even that is unneccessary? Anyway I seem to recall getting a quiz score around the 0.9200 mark with just the global mean taken out of the data. Some of my later modifications probably would have improved that quite a bit, so my guess would be an improvment of 0.01 - 0.015 say.

BB.

YehudaKoren · 2007-09-24 13:27:22

Newman! wrote:
Bored Bitless and YehudaKoren,

Can you provide any numbers on how much double-centering reduces the RMSE of SVD and KNN ? I've run both algorithms without removing any global effects, and I'm just wondering how much I have to gain from it.

Newman!

Regarding SVD it really depends on the way you compute it, so it is difficult to come with a number. Our more sophisticated SVD doesn't use any kind of centering at all.

As for kNN, it is a different story - double centering will significantly benefit you. Exact figure of course depends on implementation details, but you can get a good idea by looking at Table 2 of our paper "Improved neighborhood-based collaborative filtering".

Yehuda

Newman! · 2007-09-24 14:25:38

Bored Bitless wrote:
I assume you are removing the global mean from each rating at least? Hmm maybe even that is unneccessary? Anyway I seem to recall getting a quiz score around the 0.9200 mark with just the global mean taken out of the data. Some of my later modifications probably would have improved that quite a bit, so my guess would be an improvment of 0.01 - 0.015 say.

I have two variants of SVD, one removing global average only and one does not. The RMSE's are within 0.001 to 0.002 of each other, just under the threshold I'm willing to tweak for. My thinking on this goes something like this:

SVD is basically learning a set of features for each movie/viewer. Why can't it learn, for each movie/viewer, a "feature" that corresponds to the "average" effect of the movie/viewer ?

Of course it can't learn date-related effects because it doesn't have access to date data, i.e. the SVD geek can't get a date .

Newman! · 2007-09-24 14:31:44

YehudaKoren wrote:
As for kNN, it is a different story - double centering will significantly benefit you. Exact figure of course depends on implementation details, but you can get a good idea by looking at Table 2 of our paper "Improved neighborhood-based collaborative filtering".

Yehuda,

Yes I've read your paper. However I don't totally understand your KNN approach, especially the jointly-derived part, but I can tell your KNN is very different from mine (describe on my blog).

Well, I have a "jointly-derived" KNN too: I just calculcated a 2nd set of Pearson's r from the SVD features, and using this data improved my KNN by 0.003 to 0.004. But all that improvement vanished when I blended the KNN result with the SVD result.

ap · 2007-09-24 16:54:12

Bored Bitless wrote:
Thanks for the feedback. Yes I have wondered if double centering may also be removing useful information from the SVD algorithm. My guess would be that an extra offset term per feature value would do well on ratings that have not been double centered. In fact Paterek's paper reports a better result with just such a term, though I'm not sure if he used double centering beforehand or not.

Hi BB,
I used double-centering in the SVD. I didn't use it in the SVD with biases.

Arek

justme · 2007-10-25 07:41:58

Did anybody calculated alpha values suitable for Movielens data-set?
I would be interested in them also...

curious · 2007-11-25 16:25:25

YehudaKoren wrote:
BB,

Thanks for reporting your experience with global effects, which somewhat differs from mine.
Here are my alpha values (which we somehow set 9 months ago...), each followed by the resulting RMSE.

Movie: 25, 1.0527
User: 7, 0.9841
User-time(user): 550, 0.9809
User-time(movie): 150, 0.9786
Movie-time(movie): 4000, 0.9767
Movie-time(user): 500, 0.9759
User-mean(movie): 90, 0.9719
User-support(movie): 90, 0.9690
Movie-mean(user): 50, 0.9670
Movie-support(user): 50, 0.9658

For the Movie-mean(user) effect, are you using the mean of user ratings (i.e. sum of user's ratings / number of user's rating) or other?

One Million Monkeys · 2007-11-28 16:31:58

Bored Bitless wrote:
-------
...
movie*time(user): 250, rmse = 0.975367
user*movie average: 64, rmse = 0.966629
...
-------

Bored Bitless, you got a pretty nice jump when you add the user*movie average feature. Did you do something special for that particular effect? The gain you are reporting for that effect is bigger than what I'm seeing and bigger than what BellKor reports.

Last edited by One Million Monkeys (2007-11-28 16:43:58)

Bored Bitless · 2007-12-01 09:23:47

Hi,

Yes I think I metioned somewhere up in this thread that I had found that the 4th root gave better results than the sqyare root for certian results. Umm and I think Yehuda mentioned that Log was better for one of them also.

Anyway the benefit evaporated when the adjusted data was presented to my Funkian SVD algorithm, so I ended up using only the first two effects (double centering) which happens to be equivalent to what Simon Funk described and thus what I had already been using!

Bored Bitless · 2007-12-01 09:27:03

Curious,
My understanding from the BellKor paper was that each effect operates on the residuals resulting from all of the previous effects. They build on each other - so I guess you could actually try them in different orders to see if the result comes out different. You could also re-discover each effect having discovered all the other effects - so multiple passes over the effects in teh same vain as multiple passes on SVD features which works well.

DB · 2007-12-01 18:23:45

Bored Bitless wrote:
Curious,
you could actually try them in different orders to see if the result comes out different. You could also re-discover each effect having discovered all the other effects - so multiple passes over the effects in teh same vain as multiple passes on SVD features which works well.

So many options to try, so little time...

curious · 2007-12-02 01:24:08

Bored Bitless wrote:
Curious,
My understanding from the BellKor paper was that each effect operates on the residuals resulting from all of the previous effects. They build on each other - so I guess you could actually try them in different orders to see if the result comes out different. You could also re-discover each effect having discovered all the other effects - so multiple passes over the effects in teh same vain as multiple passes on SVD features which works well.

I was having trouble duplicating the results for this effect. I was using the residuals for the dependent variables, but I was using the raw ratings for calculating the user/movie averages, instead of calculating them on the residuals. Thanks for the clarification.

Bored Bitless · 2007-12-02 04:46:16

DB wrote:
So many options to try, so little time...

I guess the clever bit is picking out the ideas most likely to get somewhere.

BB

One Million Monkeys · 2007-12-02 10:18:51

Bored Bitless wrote:
Bored Bitless, you got a pretty nice jump when you add the user*movie average feature. Did you do something special for that particular effect? The gain you are reporting for that effect is bigger than what I'm seeing and bigger than what BellKor reports.
Hi,

Yes I think I metioned somewhere up in this thread that I had found that the 4th root gave better results than the sqyare root for certian results. Umm and I think Yehuda mentioned that Log was better for one of them also.

Your earlier message said that you used the 4th root for a couple of the time effects. I was wondering specifically how you got such a big jump on the user*movie average effect (from 0.975367 to 0.966629). It doesn't seem like you'd use a 4th root there. I can replicate (more or less) most of your results, but don't get nearly as good results with that one effect. Thanks.

Bored Bitless · 2007-12-03 12:20:57

Hmm just looking at the code and the estimator for that effect isn't being put through sqrt. Unfortunatley I have quite a bad memory when it comes to stuff like this but I did attempt to search out more optimal powers for each effect and it looks like for that particular effect (user*movie_mean) the optimal power was one. So just use the movie average as it is for each estimator value.

Can you try that and report back. If that is the case it'd be nice to get it on the record.

BB

Last edited by Bored Bitless (2007-12-03 12:21:32)

Bored Bitless · 2007-12-03 12:25:38

Looks like I used a power of one for User*movie_support also.

One Million Monkeys · 2007-12-03 13:56:18

Bored Bitless wrote:
Looks like I used a power of one for User*movie_support also.

Here's what I get for my global effects:

Movie: 21, 1.052681
Cust: 7, 15: 0.984020
User time(user) (4th root): 240, 7, 14: 0.980537
User time(movie) (sqrt): 150, 240, 7, 14: 0.978265
Movie time(movie) (sqrt): 3000, 170, 240, 7, 14: 0.976302
Movie time(user) (4th root): 200, 3000, 170, 240, 7, 14: 0.975359
User mean(movie): 64, 200, 3000, 170, 240, 7, 14: 0.971285
User support(movie): 90, 64, 200, 3000, 170, 240, 7, 14: 0.968427
Movie mean(user): 50, 90, 64, 200, 3000, 170, 240, 7, 14: 0.967472
Movie support(user): 0, 50, 90, 64, 200, 3000, 170, 240, 7, 14: 0.966252

For each global effect I've given the "shrinkage" constant I use for that global effect - and for all the preceding ones. I do this because in a few cases I reoptimized a shrinkage factor for an earlier effect when tuning a later effect.

My RMSE numbers are close to yours for a while, but your numbers take a significant jump ahead on the user mean(movie) feature.

I don't know if you do this but I clip my predictions to the 1.0-5.0 range after each global effect is applied (not just at the end). It seemed to help, at least when I tested it for the first few features.

Bored Bitless · 2007-12-03 15:41:45

No I didn't apply any trimming at all. I would also suggest that slightly different shrinkage parameters higher up in your list will have an affect on later effects. Thus if you really want to recreate my results you should try with the shrinkage numbers I reported, no trimming and the power of one stuff. That should do it.

I suspect then that trimming right at the end will help us a little but may be detrimental if done before all of the effects are accounted for.

BB

Netflix Prize: Forum

Announcement

#1 2007-09-23 13:19:27

Loose ends

#2 2007-09-23 14:53:17

Re: Loose ends

#3 2007-09-23 19:13:35

Re: Loose ends

#4 2007-09-23 20:50:02

Re: Loose ends

#5 2007-09-24 12:30:14

Re: Loose ends

bbame wrote:

bbame wrote:

bbame wrote:

#6 2007-09-24 12:41:21

Re: Loose ends

#7 2007-09-24 12:53:14

Re: Loose ends

YehudaKoren wrote:

YehudaKoren wrote:

#8 2007-09-24 13:03:48

Re: Loose ends

Newman! wrote:

#9 2007-09-24 13:27:22

Re: Loose ends

Newman! wrote:

#10 2007-09-24 14:25:38

Re: Loose ends

Bored Bitless wrote:

#11 2007-09-24 14:31:44

Re: Loose ends

YehudaKoren wrote:

#12 2007-09-24 16:54:12

Re: Loose ends

Bored Bitless wrote:

#13 2007-10-25 07:41:58

Re: Loose ends

#14 2007-11-25 16:25:25

Re: Loose ends

YehudaKoren wrote:

#15 2007-11-28 16:31:58

Re: Loose ends

Bored Bitless wrote:

#16 2007-12-01 09:23:47

Re: Loose ends

#17 2007-12-01 09:27:03

Re: Loose ends

#18 2007-12-01 18:23:45

Re: Loose ends

Bored Bitless wrote:

#19 2007-12-02 01:24:08

Re: Loose ends

Bored Bitless wrote:

#20 2007-12-02 04:46:16

Re: Loose ends

DB wrote:

#21 2007-12-02 10:18:51

Re: Loose ends

Bored Bitless wrote:

#22 2007-12-03 12:20:57

Re: Loose ends

#23 2007-12-03 12:25:38

Re: Loose ends

#24 2007-12-03 13:56:18

Re: Loose ends

Bored Bitless wrote:

#25 2007-12-03 15:41:45

Re: Loose ends

Board footer