The BigChaos Solution to the Netflix Grand Prize

TheBigChaosSolutiontotheNetixGrandPrizeAndreasToscherandMichaelJahrercommendoresearch&consultingNeuerWeg23,A-8580Koach,Austriafandreas.toescher,[e-mail]AT&TLabs-ResearchFlorhamPark,NJSeptember5,20091IntroductionTheteamBellKor'sPragmaticChaosisacombinedteamofBellKor,PragmaticTheoryandBigChaos.BellKorconsistsofRobertBell,YehudaKorenandChrisVolinsky.ThemembersofPragmaticTheoryareMartinPiotteandMartinChabbert.AndreasToscherandMichaelJahrerformtheteamBigChaos.BellKorwontheProgressPrize2007[4].TheProgressPrize2008waswonbythecombinedeortsofBellKorandBigChaos[5][17].ThedocumentationoftheNetixGrandPrizeconsistsofthreeparts.InthisdocumentwefocusonthecontributionofBigChaostothecombinedGrandPrizeSolution.Thedocumentisorganizedasfollows:InSection2wedescribetheNetixdatasetandimportantstatisticalproperties,followedbyadetailedexplanationofthetrainingprocedureofourpredictorsinSection3.Section4denesthenotation,whichweusethroughoutthisdocument.ThealgorithmicdetailscanbefoundinSection5.InordertocombinethepredictorsofBigChaosandthewholeteamtoformanalprediction,weusedacombinationofnonlinearprobeblendingandlinearquizblending.ThenonlinearprobeblendingtechniquesaredescribedinSection6,thelinearquizblendisdescribedinSection7.InAppendixAadetailedlistofallusedpredictorsisattached.2TheNetixPrizeDatasetThedatasetconsistsof5-starratingson17770moviesand480189anonymoususers.ItwascollectedbyNetixinaperiodofapproximately7years.Intotal,thenumberofratingsis100480507;theprobesetofsize1408395isasubsetofthem.Thegoalofthecontestistopredictthequalifyingset(size:2817131samples)andachieveaRMSEscoreofatleast0.8563onthequizsubset,togetqualiedfortheGrandPrize.Thequizsetisanunknown50%randomsubsetofthequalifyingset.ThejudgingcriteriaforwinningtheNetixGrandPrizeisthefourdigitsroundedRMSEscoreonthetestset(remaining50%).Inthecaseofatietheearliestsubmissionwins.Theprobesethasequalstatisticalpropertiesasthequalifyingset.Furthermoreitisusedasahold-outsetduringthecompetition.Fulldescriptionoftherulescanbefoundunder[1].TheauthorcontributedSection71TrainingsetQualifyingsetProbesetQuizTestcnt=100,480,507cnt=1408395cnt=281713150%50%LeaderboardfeedbackFigure1:TheNetixPrizedatasetindetail.Ratingsareavailableforthetrainingset.Netixacceptspredictionsforthequalifyingset,thefeedback(4digitprecision)iscalculatedona50%randomsubsetofthequalifyingset,thequizset.100101102103104020004000log(support)usercount05001000150020000123x105days(from1998to2005)ratingcount1001011020510x106log(frequency)numberofuser−daysFigure2:Eectsintheratingdataset.Firstrow:Usersupportisthenumberofvotesgivenfromauser.Themodeoftheusersupportison19votes,wheretheaveragenumberofvotesis200.Secondrow:Moreratingsattheendofthetimeline.Thirdrow:Frequencyisthenumberofvotesperdayperuser.Mostusersgaveoneortwovotesperday.TheideatoexplorethefrequencyeectwasintroducedbyourcolleaguesfromPragmaticTheory.3Frameworks3.1OptimizethePredictorsIndividuallyontheProbeSetThesolutionsoftheNetixProgressPrizesof2007and2008hadafocusontheaccuracyoftheindividualcollaborativelteringalgorithms.Blendingtechniqueswereusedtocombinetheindependentlytrainedpredictors.ThepredictorsweretrainedtominimizetheRMSEontheprobeset.First,theprobesetisexcludedfromthetrainingdata.Themodelgetstrainedtominimizetheprobeset.ForgradientdescentmethodsthismeansthatthetraininghastostopwhentheRMSEontheprobesetisminimal.Thenpredictionsarestoredfortheprobeset.Afterwards,theprobesetgetsincludedintothetrainingdataandthetrainingstartsagain,withexactlythesameparametersandinitialconditions.Afterthe2secondtrainingstage,wegeneratepredictionsforthequalifyingset.Thesepredictionsachievea0.0030to0.0090betterquizRMSE,comparedtotheirprobeRMSE,thankstoexpandingthetrainingset.Foreveryalgorithmrun,theoutcomeisapredictorfortheprobeandqualifyingset,whichcanbeusedinprobeblending,seeSection6.TheindividualpredictorisoptimizedtoachievethelowestpossibleprobeRMSE.Somealgorithmsarebasedontheresidualsofothers.TocalculatetheresidualerrorweusethetrainingsetpredictionsofthetrainedpredictorasshowninFigure3.3.2OptimizetheBlendAkeyobservationwithensemblemethodsisthatitisnotoptimaltominimizetheRMSEoftheindividualpredictors.OnlytheRMSEoftheensemblecounts.Thusthepredictorswhichachievethebestblendingresultsaretheones,whichhavetherightbalancebetweenbeinguncorrelatedtotherestoftheensembleandachievingalowRMSEindividually.Anidealsolutionwouldbetotrainallmodelsinparallelandtreattheensembleasonebigmodel.Thebigproblemisthattraining100+modelsinparallelandtuningallparameterssimultaneouslyiscomputationallynotfeasible.Weapproximatethisidealsolutionbytrainingthemodelsoneafteranother,whereeachmodeltriestoachievebestresultswhenblendedwithallprecedingmodels.SothefocusshiftsfromlookingattheRMSEofanindividualpredictortotheRMSEofablendedensemble.Inthefollowing,werefertotheprobeRMSEofalinearblendwithallprecedingpredictorsas\blendRMSE.Eachpredictortriestoachievebestresultswhenitisblendedwithallprecedingones.Thereforeweneitherreformulatetheerrorfunction,norchangeanylearningrules.W