AProactive,Personal,PrivateShoppingAssistant
FilippoMenczer
filippo-menczer@uiowa.edu
W.NickStreet
nick-street@uiowa.edu
DepartmentofManagementSciences
TheUniversityofIowaIowaCity,IA52242
NarayanVishwakarma
nvishwakarma@yahoo.com
DepartmentAlvaroE.Monge
ofCECSCal.StateUniv.LongBeachLongBeach,CA90840monge@cecs.csulb.edu
ABSTRACT
TheIntelliShopperisashoppingassistantdesignedtoem-powerconsumers.Itisapersonalassistantinthatitob-servestheuserswhileshoppingandlearnstheirpreferenceswithrespecttovariousfeaturesthatcharacterizeshoppingitems.Itisproactiveinthatitrememberstheusers’requestsandautonomouslymonitorsvendorsitesfornewitemsthatmightmatchtheusers’needsandpreferences.Finally,itprotectsusers’privacybymeansofpseudonymity,IPanony-mizing,andtrustedfiltering.Pseudonymityisachievedthroughtheuseofpersonae;weshowthatthisapproachalsobehoovessuccessfulclassification.IPanonymizingcanbeperformedinatleasttwomanners,whichwediscussandcompareinthecontextofourapplication.Trustedfiltering—asopposedtomerchant-basedfiltering—improvespri-vacybyallowinguserstoselecttheirpreferredprivacyrepre-sentative.ThispaperintroducestheIntelliShoppersystem,discussesitsarchitectureandcomponents,describesaproto-typeimplementation,andoutlinespreliminaryevaluationsofitsperformance.
CategoriesandSubjectDescriptors
K.4.4[ComputersandSociety]:ElectronicCommerce;I.2.11[ArtificialIntelligence]:DistributedArtificialIn-telligence—Intelligentagents,Multiagentsystems;H.3.4[In-formationStorageandRetrieval]:SystemsandSoft-ware—Userprofilesandalertservices;H.3.3[InformationStorageandRetrieval]:InformationSearchandRetriev-al—Informationfiltering,Relevancefeedback;E.3[DataEn-cryption]:Publickeycryptosystems
Permissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthefirstpage.Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspecificpermissionand/orafee.
AAMAS2002,July15-19,2002,Bologna,Italy.
Copyright2002ACMX-XXXXX-XX-X/XX/XX...$5.00.
MarkusRSALaboratoriesJakobsson
20CrosbyDriveBedford,MA01730
mjakobsson@rsasecurity.com
Keywords
Shopping,Pro-activity,Monitoring,Personalization,Learn-ing,Privacy
1.INTRODUCTION
E-commercehaschangedthewaycompaniesdistributetheirproductsandservicestoconsumers.Traditionalbrick-and-mortarcompaniescontinuegrowingthissegmentoftheeconomybycreatingtheirowne-commercepresence.Somecompanieshavecreated(orreshaped)theirimagebyhavingtheirentireoperationsbasedstrictlyone-commerce.Ane-commercestrategyhasmanybenefitsforthecompanyaswellastheconsumer.Intheresearchpresentedhere,weaimatimprovingtheaccessibilityandexpandingthebenefitsofe-commerceshoppingtoconsumersandataidingthemovetoapersonalized(andthusmoreefficient)marketplace.Thesuccessofe-commercehasresultedinproblemsanal-ogoustothoseearliercreatedbythegrowthandpopularityoftheInternet.Searchengineswereanearlysolutiontotheproblemoffindinginformationspreadoutovermanydiffer-entWebsites.Similarlynow,ashoppermustsiftthroughtheinformationprovidedbyinnumerablee-commercesites.Thistaskisadifficultoneasthetype,amount,andorga-nizationoftheinformationprovidedone-commercesitesdiffersfromcompanytocompany.Complicatingmatters,acustomergoesunawareofchangesinpricing,availability,etc.unlesssherevisitsthesitesveryfrequently.
Currentlythereareanumberofapproachesthatshop-perscantakewhenseekingtofindaproduct.Thefirstandmoststraightforwardapproachisfortheshoppertomanuallyvisitvariouse-commercesites;foreachsite,theshopperbrowsesand/orsearchesfortheparticularproductofinterest.Thissimpleapproachhasseveraldrawbacks.Foronething,thereisnosinglesitethatcaterstoallshop-pingneeds,whichincreasesthe(user)searchtimeforeachnewproductcategory.Also,itinvolvesgettingacquaintedtonewinterfaces,slowingdowntheuserbrowsingandhin-deringimpulseshopping.Finally,itisanapproachlikelytofavoronlythelargestvendors(duetoname-branding),
whichinturnreducestheeffectivenessofthemarket.
Asecondapproachincreasesthedegreeofautomatizationbysite-providedalertservices.Severalservicesallowshop-perstosignuptoreceivepricealertsthatnotifyashopperwhenthepriceofaproductchangesorfallsbelowaspec-ifiedamount.Someoftheservicesrequirelengthysurveystobefilledout,whileatthesametimemostprovidelittletonopersonalization.Afurtherdrawbackofthisapproachistheweakeningofuserprivacythatitimplies.
Athirdproposedapproachinvolvesvoluntaryratingsandreviewsofvendorsandproductsbyusers,andthecompila-tionofsuchinformation[9].Asinthepreviousapproach,suchrecommendationsystemsarelikelytoreducethesizeofthemarketplaceandtointroducebias,asitisdifficulttoobtainasufficientnumberofratingsforeveryexistingvendor,andtocontrolthereliabilityofthesources.
Finally,afourthgeneralapproachistofurtherautomateandgeneralizethesearchprocess[11,7].Asearlyas1995,shoppingagents(alsoreferredtoascomparisonshoppingagents)wereproposedasasolutiontofindaproductunderthebestterms(wherepricewasthemostimportantfea-tureearlyon)amongdifferente-commercesites.Ashop-pingagentqueriesmultiplesitesonbehalfofashoppertogatherpricingandotherinformationonproductsandservices.Mostofthesecomparisonshoppingagentshow-everpresentamarketplacethatisbiasedinfavorofthee-commercesitesthatcollaboratewiththeshoppingagent.Inadditiontothebiasedmarketplace,ashopperhasonlyalimitednumberofe-commercesitestochoosefromandoftentheparticipatingsitesdonotofferthebestprices.Weproposeanewtypeofshoppingagent,calledIntel-liShopper,thatextendstheaboveapproachesbyprovidingtheuserwithautonomy,personalization,andprivacy.
Autonomyreferstotheideathatashoppingagentcanprovidethebestpossibleservicebyremainingasindepen-dentaspossiblefrombothcustomersandvendors.Au-tonomyfromvendorsimpliesthattheserviceistoremainunbiasedbyperformingwidesearches(asopposedtoonlysearchingthedatabasesofafew“preferred”vendors).Thiscanbeachievedbyprogressinmakinginterfacesmoreuni-form,andbyimprovedmethodsforinterpretingpotentialhits.Autonomyfromthecustomermeansthatuserscanberelievedfromthetedioustaskofsearchingforinformationandofneedingtoadjusttodifferente-commercesites.Fur-thermore,ourshoppingagentproactivelymonitorsvendorsitesonbehalfoftheuser,notifyinghimofnewproductsofpotentialinterest.
Personalizationmeansthattheshoppingassistantstrivestolearntheuserbehaviorsandpreferencesbyobservinghisactionswhileshopping.Whenauserconsiderstheitemsavailableate-commercesites,heindirectlyprovidesfeed-backbyclickingonitems.Theagentcaninternalizethisfeedbacktoinferuserpreferencesandapplysuchlearnedknowledgeintakinginitiativeaboutfuturesearches,aswellasinpredictingwhenausermightbeinterestedinanitem,sothattheusercanbenotified.
Finally,ourresearchaddressestheprivacyoftheshopperbyconcealingtheidentityandbehavioroftheuserinava-rietyofways.However,wenotethattheprivacyprovidedisconditional,andshouldbeselectivelyrevokedifabuseissuspected.Thepersonalizationandprivacyaspectsofourproposedagentprovideforanunbiasedpersonalizedmar-ketplacewheretheuserbenefitsinmanyrespects.
2.BACKGROUND
ResearchintheareaofshoppingagentsdatesbacktotheearlyyearsoftheWeb.In1995,AndersenConsultingdevel-opedBargainFinder,thefirstoftheshoppingagents.Ital-loweduserstocomparepricesofmusicCDsfromstoressell-ingovertheInternet.Atthetimehowever,someofthere-tailersblockedaccessbecausetheydidnotwanttocompeteonprice,andBargainFinderceasedoperation.Sincethen,therehavebeenadditionalshoppingagentsthatstartedpro-vidingunbiasedcomparisonofproductsfromdifferentshop-pingsites.InPersonaLogic,userscreatedpreferenceprofilestodescribetheirtastes.Theapproachallowedfortheiden-tificationofproductswithfeaturesimportanttotheusers,butthevendorshadtoprovideaninterfacethatexplicitlydisclosedthefeaturesoftheproductsinawaythatcouldbematchedwithuserprofiles.PersonaLogicwasacquiredbyAOLin1998andthetechnologydisappeared.
Ringowasanagentthatrecommendedentertainmentprod-ucts(music,movies)basedoncollaborativefiltering,i.e.,onopinionsoflike-mindedusers[3].Thiswasoneoftheearli-estsoftwareagenttechnologiestobecommercialized,whenitwasincorporatedintoacompanynamedFireFly.FireFlyalsoaddressedtheissueofprivacybyinitiatingandpromot-ingtheP3Pstandard.FireFlywasacquiredbyMicrosoftin1998andtheFireFlyagentceasedoperationshortlythere-after.Howevertheconceptofcollaborativefilteringhasbe-comewidelyused,including—insimplifiedways—bylargecommercialvendorssuchasAmazon.
TheShopBotwasanagentthatcouldlearnhowtosub-mitqueriestoe-commercesitesandinterprettheresultinghitstoidentifylowest-priceditems[4].ShopBotautomatedtheprocessofbuilding“wrappers”toparsesemistructured(HTML)documentsandextractfeaturessuchasproductde-scriptionsandprices.Ourgoalsaresimilarbutwefocusonlearningtheuserpreferences(withrespecttomanyfeatures)andweuseadifferentapproachforextractingthosefeaturesfromvendorsites.TheShopBottechnologyhadasimilarfatetothoseofPersonaLogicandFireFly;itwasacquiredandcommercializedbyExcite(underthenameJango),andsoonreplacedwithabiasedvendor-drivenagent.
Tete@Tetewasanagentthatintegratedproductbroker-ing,merchantbrokering,andnegotiation[15].Astart-upcalledFrictionlessCommerceisapplyingthetechnologytoB2Bmarkets(e-sourcing)ratherthantoB2Cmarkets.Theonlycomparisonshoppingagentsavailabletoconsumersthataresurvivinginthecommercialrealmarebiased,pre-sentingresultsonlyfromcompanieswithwhomtheycollab-orate.ExamplesincludeMySimon,DealTime,PriceScan,RoboShopper,andmanyothers.
Learninguserbehaviorsandpreferencesby“lookingovertheuser’sshoulders”isanexampleofaninterfaceagent.ThesehavebeenwidelyemployedininformationfilteringandInternetrecommendationsystems[14].Twouserinter-faceagentsthatlearnedfromtheactionstakenbyauserareLetizia[12]andWebWatcher[10].Similarlytotheseagents,IntelliShopperpresentsinformationtotheuserinawaythatallowsherinteractiontobeeasilyincorporatedintothelearningprocess.
IntheareaofWebqueryingandmonitoring,themostrelevantworkisWebCQ[13].InWebCQ,specificpagescanbemonitoredforchangestotheircontent.Thesystemcantrackchangesonarbitrarypagesbycomputingthediffer-encebetweenthepageatsomegiventimeandthesame
pageatalatertime.MorerecentlyresearchhasbegunonthemonitoringofXMLdata[17].Here,thestructuringofdocumentsallowsfordatabase-precisionqueries.Inthisparticularwork,thefocusisonthearchitectureofascalablesystemthatsupportsthemonitoringofmillionsofpagesperdayservingmillionsofsubscriberstothemonitoringservice.Avarietyofwell-knowncryptographictechniquesareap-plicabletopreservetheprivacyofonlineshoppers.Topro-tecttheidentityofusers,atypeofpseudonymcalledapersonacanbeused(see[1]foradiscussionofthetypeanddegreeofprivacyobtainedwiththistechnique).Ananonymizer1(a.k.a.mixnetworkoronionrouter)canbeusedtoobtaincommunicationprivacy,i.e.,tohidetheIPaddressfromwhichrequestsemanateandtowhichresponsesaredirected.Ananonymizerconsistsofoneormoreserverslocatedbetweentheuserandthemerchants;theseserversforwardrequestsandresponses,andanonymizebymeansofpermutation,strippingofIPaddresses,andencryption/de-cryption.Wereferto[9]foradetaileddescriptionofhowtointegratethesetoolsinanarchitecturesuchasours.
Analternativetoanonymizersisthe“Crowds”approach,whichcanbethoughtofasa“buyersclub”forprivacy[18].Inpractice,thisisimplementedbyoneormoreuserspassingeachother’srequestsbackandforthtohidetheiroriginfromarecipient/merchant.Suchanapproachisslightlylesspalpablethananonymizersinanarchitectureliketheoneproposedinthispaper,butisstillpossibletouse.
Analternativetohidingtheidentityandthewhereabouts(IPaddress)oftheusersistohidewhattheyrequest.Inparticular,itispossibletodesignasysteminwhichuserscanaccesselementsofadatabaseinamannerthatmakesitimpossibletodeterminewhatelementswereaccessed[6].However,suchanapproach(naturally)prohibitsthecentralcollectionofstatistics,forcingallthefilteringtobeper-formedbytheuser.Furthermore,thisapproachmakesusermobilitydifficultandcollaborativefilteringimpossible.Wethereforedonotconsidertechniquesofthistype.
3.SYSTEMARCHITECTURE
Figure1illustratesthehigh-levelarchitectureoftheIntel-liShoppersystem.Theprivacyagentallowstheusertotakeonashoppingpersonaandhidesallidentifyinginformationabouttheuser(e.g.,IPaddress,username,andemail)fromtherestofthesystem.Theprivacyagentresidesononeormorecollaboratingservers,locatedbetweentheuserandtheIntelliShopperserver.Itispossibleforseveralprivacyagentstoco-exist,allowingeachusertoselecttheoneinwhichhehasthemostconfidence.Itisalsopossiblefortheusertoemploydifferentprivacyagentsfordifferentfunctions,per-sonaeorrequests.Thisselectioncanbemadelocally,ontheuser’sclient,orbyafirstprivacyagentserverwhosemainfunctionistokeepandmaintaintheselectionpolicies.
InthismodelitisassumedthatthecustomerwillnotconductpurchasingtransactionsviatheIntelliShopper;iftheuser’sprivacyistobeprotectedthroughoutthebuy-ingprocessaswellaswhileshopping,thenaprivacyagent(acceptabletothemerchants)wouldhavetoresidebetweentheuser(ortheuser’spurchasingagent)andthemerchants.Wedonotfurtherdiscussthisissueinthepresentpaper.Ashoppingpersonaisauniqueidentityreflectingthe1
anonymizer.
Seewww.anonymizer.comforacommerciallyproposedprivacymonitoragentMySQLagentShoppingvendorvendorPersonalearningagentmodulesWeb sitesanonymizing serverIntelliShopper serverFigure1:ArchitectureoftheIntelliShoppersystem.LightgrayarrowsrepresentWebinteractionsbasedontheHTTPprotocol.DarkgrayarrowsrepresentSQL-basedinteractions.
modeofuseofaparticularuser.Itspublicdescriptorsarein-dependentoftheowner’sidentity,location,etc.Thepersonabecomesthe“publicuser”seenbytheothercomponentsofthesystem,andcouldevenbedisclosedtomerchantswith-outcompromisingtheuser’sidentity.TheIntelliShoppercanbuilditshistory-basedpreferencedatabasesindexedbythepersonadescriptors,ratherthanbyusernames,IPad-dresses,orbyusingcookiesasiscurrentlydonebycommer-cialnotificationandbrokeringsystems.Thepersonahastwoexplicitpurposes:(i)theprivacyoftheuserisguaran-teed,assumingtheusertruststheanonymizingserver,be-causenoidentifyingpersonalinformationabouttheuseriseverstoredintheIntelliShopperdatabase;and(ii)theusercantakedifferentpersonaefordifferentshoppingneeds,e.g.,“gadgetgeek”vs.“lovingspouse,”andIntelliShoppercanlearnadifferentshoppingprofileforeachpersona.
TheremainingmodulesofthesystemarehostedonthemainIntelliShopperserver.Theyinteractwithusersonlyviashoppingpersonae.Thelearningagenttakesuserre-quests,savesthemonthedatabase,forwardsthemtoonlinevendors,retrievestheresultinghitsfromthelocaldatabase,anddisplaystheresults(rankedaccordingtothepersonaprofile)backtotheuser.Thelearningagentalsoobservestheactionsoftheuser—removing,viewing,and/orbuyingitems—andadjuststheprofileaccordingly.
LogicaboutindividualWeb-basede-commerceandauc-tionsitesisstoredinthevendormodules.Thesespecifyhowtoqueryvendorsandhowtointerprettheresultsandex-tractstructuredinformation,suchasproductdescriptionsandprices,fromtheHTMLpagesreturnedbythevendorsites.Thehitsreturnedbythevendorsareparsed,recordedinthedatabase,andmadeavailabletothelearningagent.Themonitoragentperiodicallyqueriesthedatabasetoretrieveoutstandingqueries,i.e.,shoppingrequestsinwhichtheuserisstillinterested.Atintervalsspecifiedbytheuser,themonitoragentqueriesvendors(viathevendormodules)toseeifnewitemshaveappearedthatmightmatchthepersonaprofile.Thenewhitsarerecordedinthedatabasesothattheusercanbenotified.
Thefollowingsubsectionsillustratethemodelsbehindthelearning,monitor,andprivacyagentsingreaterdetail.Im-plementationissuesarediscussedinSection4.
3.1LearningAgent
IntelliShopperadaptstouserpreferencestobetterrankhitswithcontinueduse.Ourapproachisbasedongath-
Before user clickAfter user clickFeature low avg highFeature low avg highPrice 3.25 1.25 2:75Price 3.25 1.00 3.00Bids ... ... ...Bids ... ... ...Time ... ... ...Time ... ... .........Lavazza Oro 500g vacuum-packed $ 9.05 4 bids 2 days Buy|RemoveIlly Caffe' - imported from Italy $19.95 9 bids 5 min Buy|RemoveFolgers American Coffee $ 6.50 6 bids 8 hrs Buy|Remove...Figure2:Illustrationofhowthelearningagentchangesaprofilefollowingauseraction.Inthiscase,focusingonthepricefeature,theuserclicksonthesecondhit,fromwhichthelearningagentin-fersamildinterestforhigh-priceditemsandamilddisinterestforaverage-priceditems(sincethefirsthitwasskippedover).Thetemperaturesofthecor-respondingpricerangesareupdatedaccordingly.eringthemaximumamountofinformationwhilerequiringaminimumofextrafeedbackfromtheuser.Thesystemlearnstoincreasetherankingsofhitsthataresimilartothosethathaveinterestedtheuserinthepast,andreducetherankingsofthosesimilartoitemsthattheuserhasei-therignoredoractivelydisliked.TheprocessisillustratedinFigure2.
Asistypicalininductivemachinelearning,ouradaptationschemeisbasedonacollectionoffeaturesextractedfromthehits.Featuresarechosensuchthattheymightberelevanttotheuser’sevaluationoftheitem.Featurescanbeeithercontinuousordiscrete,althoughallfeaturescurrentlyusedarecontinuous.Consideringauctionsitesforexample,thefollowingfeaturesareusedinthecurrentmodel:•priceoftheitem,
•numberofbidsthathavebeenplacedontheitem,•timeremainingintheauction,and
•similarityThisiscomputedbetweenusingthequerythestandardandthecosineitemdescription.similarity:
sim(q,d)=k∈q∩dfkqfkd
k∈dfkd2k∈qfkq
2
whereqisthequery,distheitemdescription,andfki
isthefrequencyoftermkini.
Foreachfeaturex,wemaintainadistributionoftempera-turesacrosstherangeofpossiblevalues.Thetemperatureofagivenfeature/valuepairshouldcorrespondwiththeuser’sdesireforanitemwiththatcharacteristic;hightemperaturesignifiesadesirablevalue,lowtemperatureanundesirableone.Temperaturesaremaintainedforeachpossiblevalueofdiscretefeatures,e.g.,a“color”featuremighthavealowtemperatureforthevalue“pink.”Continuousvariablesarediscretized,e.g.,the“price”featurecouldhaveahightem-peratureforthevalue“low.”Cutpointsforthediscretiza-tionarebasedonthemeanµandstandarddeviationσoffeaturevaluesobservedamonghits,asfollows:
•Verylow:x<µ−2σ•Low:µ−2σ≤x<µ−σ2•Average:µ−σ2≤x<µ+
σ2•High:µ+
σ2≤x<µ+2σ
•Veryhigh:µ+2σ≤x
NotethatFigure2denotesonlythreepossiblevaluesfor
discretizedcontinuousfeatures.
Temperaturesareupdatedonanyuseraction(orinaction)relatedtoagivenhit.InFigure2,theuserclicksontheseconditem,whichishigh-priced.Thiscausesariseinthetemperatureforhighprice,i.e.,thesystemconsidersthisevidencethattheuserisinterestedinexpensivecoffee.Thetemperatureassociatedwitheachfeaturevaluefollowsasimpleupdaterule:
T(t+1)=α1T(t)+α2∆T
(1)
whereα1,α2determinehowquicklyaprofileforgetsoldpref-erencesandtracksnewones.2Therearefourpossiblereac-tionstoanygivenhit,eachwithitsowneffecton∆Tforthecorrespondingfeaturevalues:
•Buy:positiveClickingfeedback;ontheit“Buy”resultsoptioninatemperatureisconsideredincreasestrong∆T=+0.5forallthefeaturevaluesofthatitem.•Browse:tivefeedback;Clickingtheontemperaturetheitemdescriptionincreaseis∆isTweak=+0posi-.25.•Ignore:clickingIfonaoneuserfartherbypassesdownantheitem,listasofindicatedhits,thisbyisconsideredweaknegativefeedback:∆T=−0.25.TheLavazzaOroiteminFigure2isonesuchexample.•Remove:feedback:Actively∆T=−deleting0.5.anitemisstrongnegativeHitsthatappearonthelistbelowthelastonewithwhichtheuserinteracteddonotcauseanytemperatureupdates.Hitsaregivenatemperaturebasedonasimplesumofthetemperaturesforthevaluesoftheirfeatures.Thehitsarethenrankedaccordingtotheirtemperatures,fromhightolow.Userinteractionsduringaquerysessioncauseare-rankingofthehitsbasedonupdatedtemperatures.
3.2MonitorAgent
ThemonitoragentmakestheIntelliShopperautonomousinthatitproactivelyshopsonbehalfofusers(or,moreac-curately,onbehalfofpersonae).Thisagentisabackgroundprocessthatwakesupperiodicallyandqueriesthedatabasesforanyrequestsnotyetexpiredorremovedbytheusers.Theusercanspecifythedurationandfrequencyofshop-pingrequests.Foranyoutstandingrequest,theagentchecksthefrequencyatwhichtheuserhasrequestedtomonitorvendors.Ifthetimeelapsedsincethelastcheckislongerthantheonecorrespondingtothemonitoringfrequency,theagentqueriesthevendorsagainandupdatesthedatabasewiththenewhits.Newhitsmightincludepreviouslyseenitemswhosecharacteristicfeaturevalues(say,price)havechanged.Theuser(possiblynotifiedviaemail)willfindthe
2
Wesetα1=α2=1inthecurrentprototype.
newresultswaitingthenexttimeshelogsintotheIntelliSh-opper.Theresultswillberankedbasedontheprofileoftheshoppingpersonausedtomaketherequest.Astheuserlooksatthenewhits,thelearningagentcangetadditionalfeedbackandfurtheradjustthepersonaprofile.
3.3PrivacyAgent
Amultitudeofapproachesmustbetakentoimplementprivacyinoursystem.Privacycouldmeaneitherinfor-mationaboutwhoisperformingasearch,orwhatisbe-ingsearchedfor.Inordertouncoupletherequestfromtherequester,itisnecessarytohidebothhisidentityandwhereabouts.(Wedonotconsidertheissueofhidingthegeographicallocationoftheuser.)
Thewhereaboutoftheuser—mosttypicallytheIPad-dress—isbesthiddenbypassingallrequeststhroughananonymizer,whichhidestheoriginoftherequestfromtheIntelliShopperagent,andthecontentsoftherequestfromtheanonymizer’sservers.
Anonymizersaretypicallyimplementedviadistributedcontrol.Therequestmaybeamultiplyencryptedmessage.Foreachanonymizerserver,thisgetspartiallydecrypted,andpassedalongtothenextserver,accompaniedbyasetofothersuchrequests.Eachservertakesalistofinputsandpermutesandoperatesontheseusingdecryption,re-encryption,orsimilarcryptographicoperations[2,8].Afterthelastsuchserverhasoperatedonthelist,thecorrespond-ingoutputsareforwardedtotheIntelliShopperserver.Thelatterrepliesbypassingamessagebacktotheuser,employ-ingsomeuser-createdtemporaryaliastoaddressthereplyasitispassedbackthroughtheprivacyagent.
Theprivacyofanonymizersrelyonatleastoneoftheserversperformingthistaskcorrectly,andwithoutrevealingitssecretdecryptionandpermutationinformation.Infact,forthesakeofefficiency,wewilluseonlyoneanonymizingserver,aswasperformedinearlyre-mailersandinatleastonecommerciallytestedWebaccessanonymizingsystem[5].Theone-serveranonymizerisadegeneratecaseinwhichtheserveritselfistheprivacyagent.Thisservermustbetrustedbytheusers;itshouldnothaveanycommercialrelationtomerchantsandotherpartieswishingtodeterminetheidentityofshoppers.
Mostanonymizersrequireserverstohaveknowledgeofsomesecretkeyfordecryptioncorrespondingtothepub-lickeyusedtoencrypttherequest[2,19];othersrequireknowledgeofthepublickeyalone[8,16].Thismakesthelattertypeusefulforad-hocanonymizers,wherekeysarenotpre-assignedtoserversandanybodymayactasaserver.Usersmayusedifferentpseudonymsorpersonaeinordertohidetheiridentityfromtheagent(andotherparties).Here,weletapersonarefertoapseudonymthatauseremploysforaparticulartypeofactivitythatshewishestoseparate(de-correlate)fromotheractivities.However,usingthecaseofsocialsecuritynumbersassupportingevidence,itisclearthatifaparticularpseudonymorpersonaisusedforalongtime,thenthisbecomespartoftheuseridentity.Infact,thepossibilitytolinkapseudonymtotherealidentityonlyonce(withsomereasonableprobability)issufficientinorderfortheassociationtoremain.Therefore,itisim-portantforuserstomigratebetweenpseudonymsovertime,wherethemigrationfrequencydependsonthedegreeofpri-vacydesired.Note,however,thattheprecisionofthesearchdependsontheuseof(somewhatcontinuous)usernaming.
Inordertobalancetheserequirementsagainsteachother,usersmayobtaindescriptorsthatlabeltheirsearchbehav-ior,allowingthemtosubmitthesealongwithnewpersonae.Notethatthedescriptorsmustnotbedetailedenoughtoal-lowstrong“cross-pseudonym”correlations.Notealsothatsuchpseudonymupdatesshouldbeperformedinlargenum-bersatthesametime,andpreferablybyalargefractionoftheuserpopulationeachtime.Wereferto[1]foradiscus-sionofhowtoestablishandmanagepersonae.
4.INTELLISHOPPERPROTOTYPE
ApartialprototypeoftheIntelliShopperhasbeenim-plementedtotesttheideasdiscussedabove.3Thecurrentsystemresidesonasingleserveranddoesnotyetincludetheprivacyagent,whichwillbedeployedonadifferentserver.Thereforeinthecurrentprototypeeachuserhasasingleshoppingpersona.Althoughprivacyprotectionisnotcur-rentlysupportedinthecurrentprototype,wenotethatthisisbuiltaccordingtothearchitecturerequiredtolateraddtheprivacyprotectionmechanisms.Emailnotificationisalsonotyetimplementedinourprototype.
Inthedevelopmentanddeploymentoftheprototypewehaveusedfreeopensourcetoolsexclusively.TheprototypeisimplementedinPerl,usingLWPandDBImodulesforitsWebanddatabaseinterfaces,respectively.ThedatabaseisimplementedusingMySQL.TheIntelliShopperisdeployedonaDarwin-basedPowerMacwithanApacheHTTPserver.
4.1UserInterface
Figure3showssomescreenshotsoftheIntelliShopperuserinterface,illustratinghowauserinteractswiththesystem.Whenauserlogsin,IntelliShopperdisplaystheprofilein-ferredbythelearningagentbasedonthepreviousshoppingactivityofthecurrentpersona(user).Thehistoryoftheshopperisalsodisplayed,withlivelinkstooutstandingre-questsandaflagforqueriesforwhichthemonitoragenthasfoundnewhits.Theusercanclicktoexamineneworoldhits,orremoverequestshenolongerwantstomonitor.Alternatively,theusercansubmitanewshoppingrequestviathequeryinterface.Heretheusercanspecifyaquerystring(tobeforwardedtovendors)andthetypeofrequest,i.e.,whethertheuserisinterestedinshoppingatonlinestoresorauctionssites.Eachoftheseoptionscorrespondstoasetofvendormodules.Inthefutureuserswillalsobeabletoupdatetheirprofile,includingpreferencesamongvendors.Furthermore,theusercanspecifyforhowlong,andhowfrequently,themonitoragentshouldlookoutfornewavailableitemsmatchingthequery.
Oncetheresultshavebeenreceivedfromthevariousven-dors,collated,parsedandstoredinthedatabase,thelearn-ingagentpresentsthemtotheuser,rankedaccordingtothepersona(user)profile.AsFigure3demonstrates,vendorshavedifferentformatsforthedisplayedfeatures.Forexam-pleoneauctionsitesmightreporttheabsenceofbidsas“0”andanotheras“–”.Manydifferentformatsarealsousedtodisplaythetimeremaininginanauction,evenbyasinglevendor.Anauctionsitemightdisplay“at6:30PM”atonetimeand“in10minutes”atalatertime,forthesameitem.Alltheseformatsareconvertedtocommondatadomainsbeforethevalueofeachfeatureisstoredinthedatabase.3
myspiders.biz.uiowa.edu/~nvish/IntelliShopper
TheprototypecanbeaccessedontheWebat
Figure3:Top:TheinformationdisplayedbyIn-telliShopperuponlogin.Middle:Queryinterface.Bottom:Resultsofasearch.
4.2VendorModules
ThevendormodulesallowIntelliShoppertointerfacewiththevariousonlinestore/auctionsites.TherearetwoaspectstoavendorlogicfromtheIntelliShopper’sperspective:(i)submittingqueries,and(ii)parsingresults.Task(i)issim-pler;itconsistsofidentifyinganappropriateform,submis-sionprotocol,andinputsyntaxoneachvendorsite.Task(ii)ismoredifficult;itconsistsofidentifyingitemsandex-tractingfeaturevaluesforalldesiredfeatures(e.g.,productdescription,price,etc.).Whilevendorscouldreadilysim-plifythistask,saybyusingXML-basedoutput,theoppo-sitetrendseemstobetakingplace;manyvendorsarenotinterestedincompetingonpricealone,andthereforeusecomplexandchangingHTMLmarkuptomakeitdifficultforshoppingbotstoextractinformationfromtheirsites.Thereismuchactiveresearchinthedevelopmentofin-telligentwrappersthatcouldautomatetheabovetasks.Infact,thereisasortofarmsracebetweentheintelligent
action=\"http://search.ebay.com/search/search.dll\"method=\"GET\"> key=’ Figure4:Simplifiedexampleofavendormodule.Themodulehaslogictosubmitqueriestoavendorsiteandtointerprettheresults. wrappersemployedbyshoppingbotsandthegrowingcom-plexityofHTMLinterfaces.EarlyshoppingagentssuchastheShopBot[4]demonstratedtheinterestinglearningchallengesstemmingfromthiscompetition.HowevertheIntelliShopperdescribedheredoesnotfocusonthisgoal,thereforewefollowedadifferentrouteinourimplementa-tion.Ratherthantryingtobuildautomaticwrappers,wesimplifiedthetaskofhand-codingwrappersbydesigningalanguageforthespecificationofvendor-dependentlogic.Thiswaynewvendormodulescanbewritteninminutes.AfulldescriptionofIntelliShopper’svendordescriptionlanguageisoutsidethescopeofthispaper,howeverFig-ure4illustratestheideawithanexample.ThelanguageisbasedonXMLandisinspiredbytheplug-insemployedinApple’sSherlockmeta-searchengine.Amodulecontainstwoparts:queryingandparsing.Forquerying,therearetagswithfieldsspecifyingtheURLoftheform,thesub-missionprotocol(GET/POST),andthevariousnecessaryinputparameters.Forparsing,thereisatagwithfieldsspecifyingfieldnamesandPerlregularexpressionsthatex-tractthecorrespondingfeaturevalues.Thisflexiblerepre-sentationpermitseasyupdatesforvendorsitesthatarenotparticularlyhostiletoshoppingagents. AllthatisneededtoallowIntelliShoppertointegrateanewvendoristodropitsvendormoduleintotheappropri-atedirectory.ThecurrentprototypehasmodulesforeBay,Yahoo,andAmazonauctions.Itshouldbenotedthatwhiletheuseofregularexpressionsmakesiteasytomodifywrap-persasnecessary,italsoyieldswrappersthatarenotveryrobustinthefaceofchangingvendorsitedesign. 4.3DatabaseDesign IntelliShoppermuststoremuchdataaboutitsshopperpersonae,theirprofiles,queries,producthits,andtheirfea-tures.Theprototypestoresallthisinformationinarela-tionaldatabase.Figure5isanentity-relationshipdiagramoutliningtheIntelliShopperdatabasedesign. Thediagramisquiteself-explanatory.Thepreferencestablestorestheprofileofeachpersona;foreachfeature(e.g.,price)thelearningagentassignsatemperaturetoeachofthevaluerangestakenbythefeature,basedonuserfeed-back(cf.Section3.1).Foreachhitintheitemtable,the PersonalikesVendorhassubmitssellsPreferenceQueryhitsItemhasFeatureFigure5:DatamodelofthedatabasesupportingtheIntelliShopper.Single-lineconnectionstoentitiesrepresentrelationshipsofcardinality1,andtridentconnectionsrepresentcardinalityN. featuretablestoresthevalueofeachfeatureandthecorre-spondingrange.Thelearningagentusesthisrangetolookupthecorrespondingtemperatureinthepreferencetable,forthepersonawhosubmittedthequerythatyieldedthishit.Theresultingtemperaturesforallfeaturevaluesofanitemarethencombinedtocomputetheitemtemperatureandultimatelyrankthehits. 5.EVALUATION EvaluationofanagentlikeIntelliShopperisdifficultbe-causemeasuresofsuccessand/orperformancearesubjec-tive.IdeallyoneshouldcompareusersatisfactionbetweenshoppersusingIntelliShopperandshoppersusingothershop-pingagents.Thisisproblematicforanumberofobviousreasons,thereforewehavefocusedontheperformanceofthelearningagent. Thegoalisanevaluationmeasurethatisbothquanti-tativeandobjective,whilebasedondatafromrealusers.Wethusrecruited51distinctvolunteersubjectswhousedIntelliShopperduringactualshoppingsessions.Thesub-jectswereaskedtositthroughtwoormoresessionsovertheweekendof27-28October2001,shoppingforanynum-berofitemsoftheirchoice.Thesubjectssubmittedatotalof97distinctqueries(1.9queriesperuseronaverage)andsatthroughatotalof127shoppingsessions(2.5sessionsperuseronaverage).Theentireexperimentinvolvedato-talof3,425distincthits,or27hitspersessiononaverage(atmost10hitsperquerywereretrievedfromeachofthethreeauctionsites). Duringeachshoppingsessionasubjectcouldsubmitre-quests,lookatnewhitsforpreviousrequests,andprovideindirectfeedbacktothelearningagentthroughtheIntelliSh-opperuserinterface.Alltheuserrequests,hitsandfeedbackwererecordedalongwithtworankingsofallthehitsineachsession.Thefirstrankingwastheoneusedbythesystemtodisplayhits,basedonthelearneduserprofiles.Thesecondrankingwascomputedbasedonthefeedbackinferredfromuseractionsduringeachsession.Forthehitsetcorrespond-ingtoeach(user,session,query)tuple,wemeasuredtheSpearman’srankcorrelationcoefficientbetweenthesetworankings: ρ=1−6 n(rankIntelliShopper(i)−rankuser(i))2 i=1n(n2−1)wherenisthenumberofhitsrankedineachsession. Theideaisthatifthelearningagentiseffective,thecor-relationbetweentherankslearnedbythesystemandtheranksinferredfromuserfeedbackshouldincreaseoverses-sions.Figure6plotsthemeanSpearman’srankcorrela- Figure6:Spearman’scorrelationbetweenIntelliSh-opper’srankingandranksinferredfromuserfeed-back.Acorrelationcoefficientiscomputedforeveryuser/session/query,thentheseareaveragedacrossusersandqueriesineachsessionnumber.Errorbarscorrespondto±1standarderror. tioncoefficientagainstthenumberofshoppingsessions.Af-terthefirstthreeshoppingsessionweobserveasignificantimprovementinperformance,indicatingthatthelearningagentiseffectivelypredictinguserpreferences. 6.CONCLUSION ThispaperintroducedIntelliShopper,ashoppingassis-tantdesignedtoempowerconsumersbyadaptingtotheirpersonalpreferences,searchingproactivelyontheirbehalf,andprotectingtheirprivacy.IntelliShoppercanlearnauserprofilewithoutrequiringexplicitfeedbackfromusers,butratherobservingtheiractionsinanunobtrusivefash-ion.Thefeasibilityoftheapproachhasbeendemonstratedthroughanimplemented,publiclyavailableprototype.ThisprototypehasalsoallowedustoevaluatetheperformanceofIntelliShopper’slearningagent,showingthatthesystemcanquicklybuilduserprofilesthatcanrankitemsaccordingtouserpreferences. Severalextensionsandimprovementsofthecurrentpro-totypeareunderway.First,wewillimplementthepri-vacyagenttodemonstratethefeasibilityoftheproposedanonymityandpseudonymityprotocolsforguaranteeingtheprivacyoftheusers.Theprivacyagentwillalsoenableamorestraightforwardimplementationofmultipleshoppingpersonaeforeachuser,allowingthelearningagenttobet-teradapttotheheterogeneousshoppingneedsofrealusers.Otherimmediateadditionstotheprototypewillincludenewvendormodulesforonlinestoresandanoptiontoallowuserstospecifypreferencesamongvendors. FutureversionsofIntelliShopperwillincludeseveralup-datestothelearningagent,improvingthesystem’sabilitytoadapttouserpreferences.Moresimplefeatures(suchasbrandname)willbeadded,subjecttoourabilitytoconsis-tentlyextractthemfromtheitempage.Wewillalsoaddamoresophisticatedsimilaritymechanismthatcompareshitstootheritemsthathavebeenjudgedbytheuser.Thetem-peraturecombinationschemewillbemadeadaptive,sothat, forinstance,ifaparticularuseroftenmakesdecisionsbasedonprice,thepricefeaturewillbemorehighlyweightedinrankinghits.Theα1,α2parametersinEquation1canalsobetunedadaptivelytoefficientlytrackdynamicprofiles.Wewillexploretheuseoftemperaturesettingsfromprevi-ously-learnedprofilestobootstraptheprofilesofnewper-sonae.Itisreasonabletoassumethatsomeinformationfromauser’sexistingpersonaewouldbeusefulwhenrankinghitsforanewpersona’squeries;forexample,ausermightoftenpreferlow-priceditems.However,thismightcompro-misetheidentityoftheuser.Inordertoavoidthecompletelossoflearnedprofilesduringthecreationofanewpersona,afewfeaturesoftheprofilemaybetransferredtoanewper-sonabytheuser.Thereareafewwaystoimproveprivacyatthisstage:(i)performthetasksimultaneouslywithmanyusers;(ii)staggertheintroductionofanewpersonawiththecessationofapreviousone;(iii)shedpersonaefrequently;or(iv)useveryconciseprofiletemplateswhenstartinganewpersona.Solution(i)islogisticallydifficult;allothersolu-tions,ontheotherhand,hinderefficientlearning.Thereforetheprivacyandlearningaspectsoftheshoppingagentneedtobebalancedagainsteachother.Thismaybedonebytheuser—onaperpersonabasis—byselectinganappropriatetrade-offbetweenprivacyandpersonalization. Theuserinterfacecanbeimprovedtoallowforbetterlearningbasedonuseractionsandmoreefficientdatabasetransactions.Forexample,weplantoallowuserstochoosemultipleitemstoberemovedsimultaneouslyfromthepre-sentedlistofhits.Suchanactionwillreducethenumberofdatabasetransactionsandwillrenderfeedbacktothelearn-ingagentmoreconsistent.Furthermore,theinterfaceshouldcommunicatebetterthelearningthatistakingshapetotheuser,byemphasizingandde-emphasizingitemsbasedonthelearnedknowledge. Adirectionforfutureresearchistostudytheopportu-nitiesforcollaborativefilteringthatstemfromcentralizedshoppingassistantssuchasIntelliShopper.Theeffectivenessofcollaborativefilteringiswellestablished.Itwouldnotbedifficult,attheusers’option,toclusterpersonaebasedontheirprofiles,andthenextendarequest’shitsetwithitemspreviouslylocatedonbehalfofotherpersonaewithsimi-larprofiles.Thiscouldbedoneirrespectiveofqueries,orsubjecttosomeminimalsimilaritybetweenqueries. Wementionedtheneedformorerobustand/oradap-tivewrapperstointerfacewithvendorsites.Alternatively,vendorsmayfinditeconomicallyadvantageoustobecome“friendly”toshoppingagentssuchasIntelliShopper,thatputthecustomeratthecenterofthebusinessrelationship,notonlybasedonpricecompetitionbutonanumberofotherfactors.Weviewthisasabetterbusinessmodelthaneitherprice-onlybotsor,worse,comparisonshoppingagentsthatarebiasedbyhiddenfeesfromvendors.Thefirstgen-erationonuser-centeredshoppingbotsdidnotsurvivethetransitiontothecommercialrealm;botssuchasPerson-aLogic,FireflyandJangowerequicklyreplacedbythecur-rentvendor-biasedagents.Theultimatefateofthenewgenerationofshoppingassistantsproposedherewillbelike-wisedecidedbythemarketplace. 7.ACKNOWLEDGMENTS ThankstothemembersoftheAdaptiveAgentsandDataMiningresearchgroupsatU.Iowafortheirsuggestions,andtothevolunteerswhohelpedevaluateIntelliShopper. 8.REFERENCES [1]R.Arlein,B.Jai,M.Jakobsson,F.Monrose,and M.Reiter.Privacy-preservingglobalcustomization.InACME-Commerce’00,2000. [2]D.Chaum.Untraceableelectronicmail,return addresses,anddigitalpseudonyms.Comm.oftheACM,24(2):84–88,1981. [3]U.DooandP.Maes.Socialinformationfiltering: Algorithmsforautomating“wordofmouth”.InProc.ACMConferenceonHumanFactorsinComputingSystems,pages210–217,1995. [4]R.Doorenbos,O.Etzioni,andD.Weld.Ascalable comparison-shoppingagentfortheWorld-WideWeb.InProceedingsoftheFirstInternationalConferenceonAutonomousAgents,pages39–48,1997. [5]E.Gabber,P.Gibbons,Y.Matias,andA.Mayer. HowtomakepersonalizedWebbrowsingsimple,secure,andanonymous.InR.Hirschfeld,editor,FinancialCryptography’97,pages17–31,1997. [6]Y.Gertner,Y.Ishai,E.Kushilevitz,andT.Malkin. Protectingdataprivacyinprivateinformationretrieval.InSTOC’98,1998. [7]A.R.GreenwaldandJ.O.Kephart.Shopbotsand pricebots.InProc.16thIntl.JointConferenceonArtificialIntelligence,pages506–511,1999. [8]M.Jakobsson.Flashmixing.InPODC’99,pages 83–89.ACM,1999. [9]M.JakobssonandM.Yung.Onassurancestructures forWWWcommerce.InFinancialCryptography’98,1998. [10]T.Joachims,D.Freitag,andT.Mitchell. WebWatcher:Atourguidefortheworldwideweb.InProc.Intl.JointConf.onArtificialIntelligence,1997.[11]J.O.KephartandA.R.Greenwald.Shopbot economics.AutonomousAgentsandMulti-AgentSystems.forthcoming. [12]H.Lieberman.Autonomousinterfaceagents.InProc. ACMConferenceonComputersandHumanInterface,Atlanta,GA,1997. [13]L.Liu,C.Pu,,andW.Tang.WebCQ:Detectingand deliveringinformationchangesontheWeb.InProc.Int.Conf.onInformationandKnowledgeManagement(CIKM),2000. [14]P.Maes.Agentsthatreduceworkandinformation overload.Comm.oftheACM,37(7):31–40,1994.[15]P.Maes,R.Guttman,andA.Moukas.Agentsthat buyandsell.Comm.oftheACM,42(3):81–91,1999.[16]M.MitomoandK.Kurosawa.Attackforflashmix.In T.Okamoto,editor,ASIACRYPT’00,pages192–204,2000.LNCSNo.1976. [17]B.Nguyen,S.Abiteboul,G.Cobena,andM.Preda. MonitoringXMLdataontheWeb.ACMSIGMODRecord,30(2):437–448,2001. [18]M.K.ReiterandA.D.Rubin.Anonymityloves company:AnonymousWebtransactionswithCrowds.Comm.oftheACM,42(2):32–38,1999. [19]P.Syverson,D.Goldschlag,andM.Reed.Anonymous connectionsandonionrouting.InProc.of18th AnnualSymposiumonSecurityandPrivacy,pages44–54.IEEEPress,1997. 因篇幅问题不能全部显示，请点此查看更多更全内容