赢得netflix推荐系统大奖的算法

1

TheBellKorSolutiontotheNet ixGrandPrize

YehudaKorenAugust2009

I.INTRODUCTION

Thisarticledescribespartofourcontributiontothe“Bell-Kor’sPragmaticChaos” nalsolution,whichwontheNet ixGrandPrize.TheotherportionofthecontributionwascreatedwhileworkingatAT&TwithRobertBellandChrisVolinsky,asreportedinour2008ProgressPrizereport[3].The nalsolutionincludesallthepredictorsdescribedthere.Inthisarticlewedescribeonlythenewerpredictors.

Sowhatisnewoverlastyear’ssolution?Firstwefurtherim-provedthebaselinepredictors(Sec.III).Thisinturnimprovesourothermodels,whichincorporatethosepredictors,likethematrixfactorizationmodel(Sec.IV).Inaddition,anextensionoftheneighborhoodmodelthataddressestemporaldynamicswasintroduced(Sec.V).OntheRestrictedBoltzmannMa-chines(RBM)front,weuseanewRBMmodelwithsuperioraccuracybyconditioningthevisibleunits(Sec.VI).The naladditionistheintroductionofanewblendingalgorithm,whichisbasedongradientboosteddecisiontrees(GBDT)(Sec.VII).

II.PRELIMINARIES

TheNet ixdatasetcontainsmorethan100milliondate-stampedmovieratingsperformedbyanonymousNet ixcus-tomersbetweenDec31,1999andDec31,2005[4].Thisdatasetgivesratingsaboutm=480,189usersandn=17,770movies(aka,items).

Thecontestwasdesignedinatraining-testsetformat.AHold-outsetofabout4.2millionratingswascreatedconsistingofthelastninemoviesratedbyeachuser(orfewerifauserhadnotratedatleast18moviesovertheentireperiod).Theremainingdatamadeupthetrainingset.TheHold-outsetwasrandomlysplitthreeways,intosubsetscalledProbe,Quiz,andTest.TheProbesetwasattachedtothetrainingset,andlabels(theratingthattheusergavethemovie)wereattached.TheQuizandTestsetsmadeupanevaluationset,whichisknownastheQualifyingset,thatcompetitorswererequiredtopredictratingsfor.Onceacompetitorsubmitspre-dictions,theprizemasterreturnstherootmeansquarederror(RMSE)achievedontheQuizset,whichispostedonapublicleaderboard(/leaderboard).RMSEvaluesmentionedinthisarticlecorrespondtotheQuizset.Ultimately,thewinneroftheprizeistheonethatscoresbestontheTestset,andthosescoreswereneverdisclosedbyNet ix.Thisprecludescleversystemswhichmight“game”thecompetitionbylearningabouttheQuizsetthroughrepeatedsubmissions.

Comparedwiththetrainingdata,theHold-outsetcontainsmanymoreratingsbyusersthatdonotratemuchandare

Y.KoreniswithYahoo!Research,

Haifa,

ISRAEL.

Email:yehuda@

thereforehardertopredict.Inaway,thisrepresentsrealrequirementsforacollaborative ltering(CF)system,whichneedstopredictnewratingsfromolderones,andtoequallyaddressallusers,notjusttheheavyraters.

Wereservespecialindexingletterstodistinguishusersfrommovies:forusersu,v,andformoviesi,j.Aratingruiindicatesthepreferencebyuseruofmoviei.Valuesarerangingfrom1(star)indicatingnointerestto5(stars)indicatingastronginterest.Wedistinguishpredictedratingsfromknownones,byusingthenotationr uiforthepredictedvalueofrui.

Thescalartuidenotesthetimeofratingrui.Here,timeismeasuredindays,sotuicountsthenumberofdayselapsedsincesomeearlytimepoint.About99%ofthepossibleratingsaremissing,becauseausertypicallyratesonlyasmallportionofthemovies.The(u,i)pairsforwhichruiisknownarestoredinthetrainingsetK={(u,i)|ruiisknown}.NoticethatKincludesalsotheProbeset.EachuseruisassociatedwithasetofitemsdenotedbyR(u),whichcontainsalltheitemsforwhichratingsbyuareavailable.Likewise,R(i)denotesthesetofuserswhorateditemi.Sometimes,wealsouseasetdenotedbyN(u),whichcontainsallitemsforwhichuprovidedarating,eveniftheratingvalueisunknown.Thus,N(u)extendsR(u)byalsoconsideringtheratingsintheQualifyingset.

Modelsfortheratingdataarelearnedby ttingthepre-viouslyobservedratings(trainingset).However,ourgoalistogeneralizethoseinawaythatallowsustopredictfuture,unknownratings(Qualifyingset).Thus,cautionshouldbeex-ercisedtoavoidover ttingtheobserveddata.Weachievethisbyregularizingthelearnedparameters,whosemagnitudesarepenalized.Theextentofregularizationiscontrolledbytunableconstants.Unlessotherwisestated,weuseL2regularization.Thisisagoodplacetoaddsomewordsontheconstantscontrollingouralgorithms(includingstepsizes,regularization,andnumberofiterations).ExactvaluesoftheseconstantsaredeterminedbyvalidationontheProbeset.Inallcasesbutone(tobementionedbelow),suchvalidationisdoneinamanualgreedymanner.Thatis,whenanewlyintroducedconstantneedstogettuned,weexecutemultiplerunsofthealgorithmsandpickthevaluethatyieldsthebestRMSEontheNet ixProbeset[4].Thisschemedoesnotresultinoptimalsettingsforseveralreasons.First,onceaconstantissetwedonotrevisititsvalue,eventhoughfutureintroductionofotherconstantsmayrequiremodifyingearliersettings.Second,weusethesameconstantsundermultiplevariantsofthesamealgorithm(e.g.,multipledimensionalitiesofafactorizationmodel),whereasamoredelicatetuningwouldrequireadifferentsettingforeachvariant.Wechosethisconvenient,butlessaccuratemethod,becauseourexperienceshowedthatovertuningtheaccuracyofasinglepredictordoes