2013 Context-aware item-to-item recommendation within the factorization framework

Context-awareitem-to-itemrecommendationwithinthe

factorizationframework

BalázsHidasi?*

balazs.hidasi@gravityrd.com

GravityR&DExporttér5–7.?

*

DomonkosTikk?

domonkos.tikk@gravityrd.com

BudapestUniversityofTechnologyandEconomics

MagyarTudósokkrt.2

1101Hungary

BudapestABSTRACT

Item-to-itemrecommendation–whenthemostsimilaritemssoughttotheactualitem–isanimportantrecommenda-tionscenarioinpracticalrecommendersystems.Onewaytosolvethistaskistousethesimilaritybetweenitemfea-turevectorsoffactorizationmodels.Bydoingso,onemaytransferthewell-knownaccuracyoffactorizationmodelsob-servedatthepersonalizedrecommendationstotheitem-to-itemcase.Thispaperintroducescontext-awarenesstoitemsimilaritiesinthefactorizationframework.Twolevelsofcontext-awaresimilaritiesarede?nedandappliedtotwocontext-awareimplicitfeedbackbasedfactorizationmeth-ods(iTALSandiTALSx).Weinvestigatetheadvantagesanddrawbacksoftheapproachesonfourreallifeimplicitfeedbackdatasetsandwecharacterizetheconditionsfortheirapplication.Theresultssuggestthatitisworthusingcontextualinformationforitem-to-itemrecommendationsinthefactorizationframework,however,oneshouldcarefullyselecttheappropriatemethodtoachievesimilaraccuracygainthaninthecaseofthemoregeneralitem-to-userrec-ommendationscenario.

CategoriesandSubjectDescriptors

I.2.6[[Arti?cialIntelligence]]:Learning-ParameterLearn-ing

GeneralTerms

Algorithms,Experimentation

Keywords

recommendersystems,item-to-itemrecommendation,im-plicitfeedback,factorization,context-awareness

1.INTRODUCTION

Permissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforpro?torcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthe?rstpage.Tocopyotherwise,orrepublish,topostonserversortoredistributetolists,requirespriorspeci?cpermissionand/orafee.

CaRR’13,February5,2013,Rome,Italy.

Copyright2013ACM978-1-4503-1847-1...$15.00.

19

1117Hungary

BudapestItem-to-itemrecommendationisatypicalrecommenda-tionscenarioinreal-worldrecommendersystems.Onecan,forinstance,partiallyovercometheusercold-startprob-lembyprovidingnon-personalizeditem-to-itemrecommen-dationsrelevanttoaselected/vieweditemforanewuser.Itemsthataremostsimilartothegivenitemarethendis-played.Thesimilaritycanbeherede?nedindi?erentways,usingforexamplemetadata(“similaritems”)ortransac-tionaldata(“usersviewedthisitemalsopurchasedthefol-lowings”).Sincetheconceptofitemsimilarityisanintuitivenotion,typicallynotexplicitlyde?nedfortherecommender,thequalityofthesimilaritemsgreatlydependsontheeval-uation(thatisadjustedtobusinessrequirements).

Item-basedcollaborative?lteringapproachesareoccasion-allyalsoreferredtoasitem-to-itemmethods.Thisisbe-causesimilaritybasedapproachescanbeeasilytransformedintopersonalizedones(item-to-user)byrecommendingitemsthataresimilartotheonesintheuser’shistory.Toavoidconfusion,inthispaperweusethetermitem-to-itemrecom-mendationfortheconceptofrecommendingsimilaritemstoagivenitem.Therefore,inourcase,therecommendationlistdoesnotdependonthevisitinguser,butonlyonthevisiteditem.

Collaborative?ltering(CF)recommenderalgorithmsuseonlytransactionaldata,yetconsideredasthestate-of-the-artmethodologyforpersonalizedrecommendation.Factor-izationbasedmethodscomputealowrankvector(featurevector)foreachuserandeachitem,andpreferencesofauseronanitemisapproximatedbythescalarproductoftheappropriatevectors.Inthegeneralitem-to-usersce-nario–whereitemsthatsatisfytheneedsoftheuserthemostarerecommended–factorizationbasedmodelsprovedtobeascalableandaccuratewaytotackletherecommen-dationproblem.Therefore,weinvestigateinthispaperhowtoapplythesameframeworkforitem-to-itemrecommenda-tionsusingsimilaritybetweentheitemfeaturevectors.CFmethodsworkontransactionaldata.Transactionaldataisoftenclassi?edintoexplicitorimplicitfeedbacktypes.Themaindi?erencesarethatexplicitfeedbacksdirectlyde-scribethepreferencesoftheuseronitems(e.g.intheformofratings),andbothpositiveandnegativepreferencedataareprovidedbyusers.Ontheotherhand,implicitfeedbackdataareindirectcluesforuserpreferences;thatcanonlybeinferredfromuser’snavigationalandpurchasehistory(itselementstermedasevents).Forimplicitfeedback,webshopusageisatypicalexample.Thepresenceofaneventdoesnotalwaysmeanpositivefeedback(e.g.whethertheproductis

satisfactoryonlyturnsoutafterthepurchase)thereforethepositivefeedbackisnoisy.Butmoreimportantly,theab-senceofaneventhardlymeansnegativepreference,becausetheuserisusuallynotawareofthemajorityoftheavail-ableproducts/content.Thus,withimplicitfeedbackdata,informationonnegativepreferencesisnotavailable.Thispropertymakespreferencereasoningmoredi?cultbothintermofpredictionaccuracyandscalability.Nevertheless,thepracticalusefulnessoftheimplicitfeedbackbasedrec-ommendersjusti?estheirnecessity.

Context-awarerecommendersystemsintegratecontextualinformationintorecommendationapproach.Inthispapercontextisusedas“event-context”,thatis,contextisconsid-eredasapropertyofauser–iteminteraction(e.g.timeoftheevent,actualmoodoftheuserwhenrecommendationisre-quested,etc.)incontrasttostaticpropertiesspeci?ctousers(usermetadata)oritems(itemmetadata).Context-awareapproacheshavesubstantialadvantagesoverothercollabo-rative?lteringmethodsastheytendtobemoreaccurateandabletoadapttotemporalcircumstances(likethemoodoftheuser).

Thispaperdealswiththeintersectionoftheabovefourar-eas:item-to-itemrecommendations,context-awareness,im-plicitfeedbackdataandfactorizationmodels.Weinvesti-gateourrecentcontext-awaretensorfactorizationmethods(iTALSandiTALSx)fromthepointofviewofitem-to-itemrecommendations,andweproposehowcontextualinforma-tioncanbeintegratedintothesimilaritycomputation.

Thepaperisstructuredasfollows.Section2brie?yre-viewsthemainadvancesinitem-to-itemrecommendationsandincontext-awareness.Themainideaofthepaper(i.e.theincorporationofthecontextinformationintosimilari-ties)ispresentedinsection3.Inthe?rstpartwedescribethemodelsweuse;thesecondpartdealswiththeproposedapproachforeachmodel.Wereportonourexperimentsandresultsinsection4,wherethestrengthsandweaknessesofthedi?erentapproachesarealsodiscussed.Finally,section5concludesthepaper.

2.RELATEDWORK

Item-to-itemrecommendation—justlikeitem-to-userrec-ommendations—canbeclassi?edascontentbased?ltering(CBF)orcollaborative?lteringmethods(CF).Item-to-itemCFmethodsareusuallyneighborbased[17],meaningthatthesimilaritiesbetweenitemsarede?nedasthesimilari-tiesbetweenthesetsoftransactionsoftheitems.Anotherapproachistoextractassociationrules[3]fromthedata.Theserulesthencanbeusedtorecommenditemstotheactualitem(e.g.“whoviewedthisitem,alsoviewedthoseitems”).Thismethodcanperformwellincertainapplicationareas[9].

Context-awarerecommendersystems(CARS)[1]emergedasanimportantresearchtopicinthelastyears.Recently,entireworkshopsweredevotedtothistopiconmajorconfer-ences.Theapplication?eldsofcontext-awarerecommendersincludeamongothermovie[6]andmusicrecommendation[5],point-of-interestrecommendation(POI)[4],citationrec-ommendation[11].Context-awarerecommenderapproachescanbeclassi?edintothreemaingroups:pre-?ltering,post-?lteringandcontextualmodeling[2].BaltrunasandAm-atriain[5]proposedapre-?lteringapproachbypartitioneduserpro?lesintomicro-pro?lesbasedonthetimesplitofusereventfalls,andexperimentedwithdi?erenttimeparti-

20

tioning.Post-?lteringignoresthecontextualdataatrecom-mendationgeneration,butdisregardsirrelevantitems(inagivencontext)oradjustrecommendationscore(accordingtothecontext)whentherecommendationlistisprepared;seeacomparisonin[18].Tensorfactorization—fallingintothecontextualmodelingcategory—wasproposedasasolu-tionforcontext-awarenessinthefactorizationframework.Therearedi?erentapproachesforexplicit[16,19]andim-plicitfeedbackdata[21,14,13].

3.CONCEPT

Wepresentinthissectionhowitem-to-itemrecommen-dationcanbeperformedusingcontext-awarefactorizationmodels.

3.1Context-awarefactorizationmodels

Beforeintroducingthemainideaofthispaper,thebasemethodsaretobeintroduced.Sinceweconcentrateontheimplicitfeedbackcase,wereviewiALS,iTALSandiTALSxmethods.

IALS[15]istheseminalmethodforhandlingimplicitfeed-backinthefactorizationframework.Itfactorizesafullbi-narymatrix—describingtheuser–iteminteractions—op-timizingforweightedrootmeansquarederror(wRMSE)us-ingalternatingleastsquares(ALS).Acellofthematrixis1onlyifthereisatleastonetransactionbetweentheuserandtheitem.Thereforethenumberofzeroesisdominantoverthenumberofonesinthismatrix.Theweightcorrespond-ingtoacellwithzerois1and??1otherwise.Theactualweightmayalsodependonthenumberoftransactionsbe-tweenthegivenuseranditem.Themethodresultsintwolowrank(feature)matrices:onefortheusersandonefortheitems.Eachcelloftheoriginalmatrixisapproximatedbythescalarproductoftheappropriateuseranditemfea-turevector.IALScomputesthefeaturevectorse?cientlybydecomposingthederivativesattheminimizingstepintouser-dependentanduser-independentparts(seedetailsin[15]),thusthemethodscaleslinearlywiththenumberofnon-zeroesintheoriginalmatrix.

ITALS[14]isthegeneralizationofIALSfortensors,andthusprovidesasolutionforcontext-awarerecommendationsintheimplicitcase.Anadditionalcontextdimensionisaddedtotheuser–itemsettingthusextendingthematrixoftransactionstoatensor1andafeaturematrixforeachdimension(user,item,context(s))areprovidedasoutput.ITALSusesthesameapproximationframeworkasIALS(bi-naryinput,weightedRMSEasobjectivefunction,andALSasoptimizer),butapproximatesthecellsbythesumofel-ementsintheHadamardorelementwiseproductofthreevectorsforthegivenuser,itemandcontext-state.Sincethederivativesinvolvemorefactors,thedecompositionthatallowsfore?cientcalculationtimeissomewhatmorecom-plicatedasforIALS.Itisshownin[14]thatthecomplexityofthisalgorithmcantheoreticallybethesameasthatoftheiALS.

ITALSx[13]appliesthebinarytensorapproachwithadi?erentapproximationmodel.Thecellsareapproximatedbythesumofthreescalarproducts:betweentheuser–item,user–contextanditem-contextfeaturevectors(seealsoTa-1

isMorethanonecontextdimensionsmightbeaddedbutitbecomesnotadvisedextremelytousesparse.

toomanyofthemsincethenthetensorTable1:MainpropertiesofusedalgorithmsMethodModeliALSiTALSiTALSxMethodiALSiTALSiTALSx

r?u,i=(Pu)TQi

r?u,i,c=1T(Pu?Qi?Cc)

=(Pu)TQi+(Pu)TCc+(Qi)TCc

Context?

NoYesYes

Commonpropertiesmodeling:binarytensorlearning:ALS

optimizing:wRMSE

r?u,i,c

Implicit?

YesYesYes

ble1).Itisshownin[13]thatthemodelhasthesamecomplexityasITALS,thatis,itscaleslinearlywiththenumberofnon-zeroinputsinthetensor.Themaindif-ferenceinanglelieswithinthatiTALSusescontext-statebasedreweightingoftheuser–itemrelations,whileiTALSxconsidersthee?ectofcontextseparatelyfortheuserandtheitemdimensions(byprojectingtherelationintotwodi-mensionalsubspaces),butmeanwhilethesingularcontextfeaturevector(percontext-state)stillensuresthatcontextfeaturesarein?uencedbybothusersanditems.

Table1summarizesthepropertiesofthethreeapproaches.P,Q,andCaretheuser,item,andcontextfeaturematrices,eachcolumnofamatrixisafeaturevector.Users,itemsandcontext-statesareindexedbyu,iandcrespectively,whilethePu,QiandCcdenotetheappropriatecolumnofthema-trix.Ther?u,ivalueisthepredictedpreferenceoftheuserontheitem(giventhecurrentcontextforcontext-awaremethods).

3.2Tworecommendations

levelsofcontext-awareitem-to-item

Similaritybetweenitemsmustbede?nedinordertopro-videitem-to-itemrecommendations.Inthefactorizationframeworkitisthesimilaritybetweenitemfeaturevec-tors.Hereweinvestigatetwoalternativesforsimilarity:cosinesimilarityandscalarproduct.Themaindi?erencebetweenthemisthatscalarproductfavorsfeaturevectorswithhighernorm.Usuallythenormofthefeaturevectorishigherformorepopularitems,thereforethosearemoreoftensimilartootheritems.Thismightincreaseaccuracy(asamanyuserslikespopularitems),butmightalsoreducethediversityandthecoverageofrecommendations.

Itisinterestingtonotethatsimilaritybetweenitemfea-turevectorsisused,butthemodelsareoptimizedforpre-dictingtheuser–itemrelations.Thisisbecausethedesiredsimilaritybetweenitemsisnotsuppliedforthesystem.Alsoitisassumedthatagoodfactorizationmethodproducessimilarfeaturevectorstosimilaritems.

Context-awaremethodsareabletoachievebetterresultscomparedtocontext-unawareones.Thisismainlybecause(1)goodcontextseparatesitemsand/orusersthatbehavedi?erently,thusmakesiteasiertolearntheuser–itemre-lationsmoree?ciently;(2)di?erentrecommendationscanbeprovidedindi?erentsituationsgiventhatcontext-statesdi?er.Basedontheseobservations,twolevelsofcontext-awarenesscanbeincorporatedintofactorizationbasedsim-

21

ilarities.The?rstlevelistousethestandardsimilarity

S(L1)(Pi)TPj

i,j

=??(1)

(Pi)TPi(Pj)TPj

i.e.cosinesimilaritybetweenitemfeatures,whilelearningacontext-awaremethod.Iftheexpressivepowerofcontextin-formationislargethecontext-awaremethodwilllearnmoreaccurateitemmodelsthanthecontext-unawarefactoriza-tion.Thereforethesimilaritiesbetweentheitemswillbemoreprecise.Thisapproachisonlybasedon(1)andwhilealegitimatestrategy,itdoesnotexploitthefullpotentialofcontextinformation.Forexampleitem-2-itemrecommen-dationlistscreatedinthiswaywillbestatic,thatis,hesamesetofitemsisrecommendedtoagivenitemineverycontext-state.

Thesecondlevelofcontext-awarenessofitemsimilari-tiesleveragesthecontextinformationthroughthefeaturevectorofthecontext-state.Theactualsimilarityvalueiscalculateddi?erentlyfordi?erentmodels2.Equation2andequation3de?nesthesecondlevelcontext-aware3similarityforiTALSandiTALSxrespectively.Bothsimilaritiesarecontextdependentthereforeshouldbeindexedwiththese-lectedcontext-stateaswell(inadditiontotheindicesofthetwocompareditems).

S(L2,iTALS)=??1T(Pi?Cc?Pj)i,j,c

(Pi)TPi(Pj)T(2)

Pj

S(L2,iTALSx)=??(Pi)TPj

(Pi)TCc(Pj)TCc

i,j,c

(Pi)T+P??+(P??i(Pj)TPji)TPi(Pj)TPj

(3)

Letusinvestigate,iTALS)thedi?erencesbetweenthetwoapproachesindetail.InS(L2thecontextfeaturevectorre-weightsthescalarproductofthetwoitemfeaturevectors.Theim-portanceofafeaturedependsontheselectedcontext-state.Someitemsthataresimilarinonecontext-statemaybedif-ferentinanother.Consequently,theapproachisverysen-sibleforthepropercontextselection:whilecontextdimen-sionsofcontext-statesthatsuittheproblemwellmayresultinamuchincreasedaccuracy(asthemodelisfullycontext-aware),ifthecontext-statesarenotappropriatelyselected

2

lossThe3

function,calculationnorofonsimilaritythelearningvaluesmethod.doesnotdependontheity.TheoftheForequationsitemscalarpresentthecalculationsusingcosinesimilar-featuresproduct,shouldthebenormalizationomitted.

withthelengthfortheproblemorthecontextfeaturesarenotlearnedwell,thesimilaritieswillbecompletelyuncorrect.

Asshowninourongoingresearch[13],thepersonalizedrecommendationsgeneratedbyiTALSmayalsosu?erfromthesensitivitytothepropercontextselectionbutthee?ectismuchsmallerthere,becausethefeaturevectorsareop-timizedusingthesamemodelaswiththepredictionsaremade.

Ontheotherhand,S(L2,iTALSx)isamorestablesimilarityfunctionapproachthatdependsonthecontextfeatureinlessextent.Thesimilaritymodelhasthreeterms:the?rstcontext-independenttermisborrowedfromEq.(1),whiletheothertwotermsarecontext-dependentcapturinghowthegivencontext-statefavorstheithandjthitems.UnliketheS(L2,iTALS)similarity,thecontextfeaturehasnoe?ectoneverytermofthesimilarityprediction,thereforeS(L1)actsasaregularizationterm,evenifthecontextdependentpromotions/demotionsgoastray.

Weoptfornotnormalizingthecontextfeaturesinequa-tions(2),sincefortheiTALSmodel,thelengthofthecon-textfeaturehasnoe?ectontheitemrankinginagivencontext-state.OntheotherhandthenormalizationofthecontextvectorattheiTALSxmodelyieldsadi?erentmodel,coinedasiTALSxN.Themaindi?erencebetweenthesemod-elsisthatthee?ectoftheitemdemotionsandpromotionsarestrongerwiththenon-normalizedversion.

4.EXPERIMENTS

Weusedfourgenuineimplicitfeedbackdatasets(LastFM1K[7],TV1,TV2[8]andGrocery)toevaluateouralgo-rithm.ThepropertiesofthedatasetsaresummarizedinTable2.Thecolumn“Multi”showstheaveragemultiplic-ityofuser–itempairsinthetrainingevents.4Chronologicaltrain–testsplitswerecreated.Thelengthofthetestperiodwasselectedtobeatleastonedaydependingalsoonthedomainandthefrequencyofevents.WeusedtheartistsasitemsinLastFM.

Ourprimaryevaluationmetricisrecall@20.Recallisde-?nedastheratioofrelevantrecommendeditemsandrele-vantitems.Anitemisconsideredrelevantforauserifthereisaneventinthetestsetwiththegivenuseranditem.Re-calldoesnottakeintoaccountthepositionofanitemontherecommendationlist.Wechoosecuto?20forseveralreasons.First,thelengthoftherecommendationlistislim-itedasusersareexposedtoafewrecommendeditemsatatime,andtheirdependsontheuserinterface.However,dur-ingausersession,severalrecommendationwidgetscanbeshown,sousermaysee20recommendationsduringavisit.MeanAveragePrecision(MAP)wasusedasasecondaryevaluationmetric.MAPconsiderstheorderoftherecom-mendeditemsthuspreferringmethodsthatputtherelevantitemsatthebeginningoftherecommendationlist.Wealsousedacuto?valueof20forMAP(denotedasMAP@20).Wealsocalculatedcoverage,ametricthatquanti?estheabilityoftherecommendersystemtoexploretheentireitemcatalog[12].Weadoptedaversionofcatalogcoverage[10,20],thatwecallperceivedcatalogcoverage,theratioofactuallyrecommendeditemscomparedtothenumberofitemsmeasuredovertheentiretestperiod.Largercover-agemeansthatusersgetmorediverserecommendationsin4

mightThisvaluehavebeenis1.0?lteredattwofordataduplicatesetsasevents.

TV1andTV2data22

general,thatisusuallyconsideredasadesiredpropertyoftherecommendersystem[20].Usuallymoreaccuraterecom-menderalgorithmstendtohavelowercoverage[22],since—bythenatureoftheconcept—manyuserspreferpopularitems,thereforemodelsbeingbiasedtowardspopularitemsachievehigheraccuracybutlowercoverage.

Seasonalitywasusedascontextinformation,becauseitreliessolelyontimestampoftheeventsthatisavailableinallofthedatasets.Onseasonalitywemeanthatwede?neaperiodicityanddivideitintosmallertimeintervalscalledtimebands.Forexample,hoursofadaycanbetimebandsofaday,ortheweekdaysandtheweekendcanbetimebandsofaweek.Thecontextofaneventisthetimebandinwhichithappened.Theperiodicity(orseason)wasaweekfortheGrocerydatasetandonedayfortheothers,becauseuserstendtodoshoppingonceortwiceaweek,whileactivitiesrelatedtomusiclisteningormovieswatchingshowdailyperiodicity.ThetimebandswerethedaysoftheweekforGroceryandfourhourlongtimewindowsfortheotherdatabases.

4.1Initialresults

The?rstexperimentrevolvesaroundtheusefulnessofthecontext-awaresimilarities.TheresultsareshowcasedinTa-ble3.Sincenoitem-2-itemsimilaritiesaregiven,weperformtheevaluationschemaasdescribednext.Weassumethatifauserinteractswithtwosubsequentitemsthenthesecondonecanbeconsideredasameaningfulrecommendationtothe?rstone,ifthetimedi?erencebetweenthetwoeventsisnotverylarge.ThusrecallandMAPvaluesweremeasuredasfollows:theeventsinthetestsetwereorderedbytheirtimestamps.Aprecedingeventofaneventisde?nedastheclosesteventwithin24hours.Iftherewasnoprecedingeventthannorecommendationscanbegeneratedandthealgorithmscannotscoreongiventestevent,butitisstillconsideredinthemeasurements.Incasetheanexistingprecedingevent,anitem-to-itemrecommendationlistwasgeneratedtotheitemoftheprecedingevent.

Generalobservations:Asitwasexpected,scalarprod-uctsimilaritiesgenerallyachievehigherrecall(andMAP)andlowercoverage,becausetheyprefermorepopularitems.TheiTALSx-basedmodelactsmoresimilarlytothecontext-unawaresimilaritythantheiTALS-basedmodel.Itisespe-ciallytruewhenL2similaritiesareused.TheiTALS-modelswithL2context-awaresimilaritiesseemtobeverysensitivetothequalityofthecontextdimension(e.g.performanceonTV2withseasonandonGrocerywithseq.isverypoor).Grocerydataset:Recallissimilarforthecontext-unawareandcontext-awaresimilaritiesusingcosinesimilarity(bothlevel1and2).Thisimpliesthattheaveragenumberofrele-vantitemsrecommendedaresimilarforeachmethod.How-evertheL2similaritywiththeiTALS-basedmodelachieveshigherMAP.Thismeansthattherankingofthoseitemsisbetter.Thecoverageoftherecommendationsismuchhigherforthecontext-awaremethodsusingcosinesimilarity.Withscalarproductsimilaritythecoveragealsoincreasesinmostcases,theaccuracy(recallandMAPvalues)ofthealgorithmisalsosigni?cantlybetter,especiallyifiTALS-basedmodelsareused.

TV1dataset:Theresultsaresimilarwithbothcosineandscalarproductsimilarity.TheiTALS-basedmodelsperformsimilarlytothecontext-unawaremethod,whiletheiTALSx-basedmodelperformsslightlybetter.Theonlyoutstanding