stanford大学-大数据挖掘-advertising.ppt

CS345DataMining,OnlinealgorithmsSearchadvertising,Onlinealgorithms,ClassicmodelofalgorithmsYougettoseetheentireinput,thencomputesomefunctionofitInthiscontext,“offlinealgorithm”OnlinealgorithmYougettoseetheinputonepieceatatime,andneedtomakeirrevocabledecisionsalongthewaySimilartodatastreammodels,Example:Bipartitematching,1,2,3,4,a,b,c,d,Girls,Boys,Example:Bipartitematching,1,2,3,4,a,b,c,d,M=(1,a),(2,b),(3,d)isamatchingCardinalityofmatching=|M|=3,Girls,Boys,Example:Bipartitematching,1,2,3,4,a,b,c,d,Girls,Boys,M=(1,c),(2,b),(3,d),(4,a)isaperfectmatching,MatchingAlgorithm,Problem:Findamaximum-cardinalitymatchingforagivenbipartitegraphAperfectoneifitexistsThereisapolynomial-timeofflinealgorithm(HopcroftandKarp1973)Butwhatifwedonthavetheentiregraphupfront?,Onlineproblem,Initially,wearegiventhesetBoysIneachround,onegirlschoicesarerevealedAtthattime,wehavetodecidetoeither:PairthegirlwithaboyDontpairthegirlwithanyboyExampleofapplication:assigningtaskstoservers,Onlineproblem,1,2,3,4,(1,a),(2,b),(3,d),Greedyalgorithm,PairthenewgirlwithanyeligibleboyIfthereisnone,dontpairgirlHowgoodisthealgorithm?,CompetitiveRatio,ForinputI,supposegreedyproducesmatchingMgreedywhileanoptimalmatchingisMoptCompetitiveratio=minallpossibleinputsI(|Mgreedy|/|Mopt|),Analyzingthegreedyalgorithm,ConsiderthesetGofgirlsmatchedinMoptbutnotinMgreedyThenitmustbethecasethateveryboyadjacenttogirlsinGisalreadymatchedinMgreedyTheremustbeatleast|G|suchboysOtherwisetheoptimalalgorithmcouldnothavematchedalltheGgirlsTherefore|Mgreedy|G|=|Mopt-Mgreedy|Mgreedy|/|Mopt|1/2,Worst-casescenario,1,2,3,4,(1,a),(2,b),Historyofwebadvertising,Bannerads(1995-2001)InitialformofwebadvertisingPopularwebsiteschargedX$forevery1000“impressions”ofadCalled“CPM”rateModeledsimilartoTV,magazineadsUntargetedtodemographicallytagetedLowclickthroughrateslowROIforadvertisers,Performance-basedadvertising,IntroducedbyOverturearound2000Advertisers“bid”onsearchkeywordsWhensomeonesearchesforthatkeyword,thehighestbiddersadisshownAdvertiserischargedonlyiftheadisclickedonSimilarmodeladoptedbyGooglewithsomechangesaround2002Called“Adwords”,Adsvs.searchresults,Web2.0,Performance-basedadvertisingworks!Multi-billion-dollarindustryInterestingproblemsWhatadstoshowforasearch?IfImanadvertiser,whichsearchtermsshouldIbidonandhowmuchtobid?,Adwordsproblem,Astreamofqueriesarrivesatthesearchengineq1,q2,SeveraladvertisersbidoneachqueryWhenqueryqiarrives,searchenginemustpickasubsetofadvertiserswhoseadsareshownGoal:maximizesearchenginesrevenuesClearlyweneedanonlinealgorithm!,Greedyalgorithm,SimplestalgorithmisgreedyItseasytoseethatthegreedyalgorithmisactuallyoptimal!,Complications(1),EachadhasadifferentlikelihoodofbeingclickedAdvertiser1bids$2,clickprobability=0.1Advertiser2bids$1,clickprobability=0.5ClickthroughratemeasuredhistoricallySimplesolutionInsteadofrawbids,usethe“expectedrevenueperclick”,TheAdwordsInnovation,Advertiser,Bid,CTR,Bid*CTR,A,B,C,$1.00,$0.75,$0.50,1%,2%,2.5%,1cent,1.5cents,1.125cents,TheAdwordsInnovation,Advertiser,Bid,CTR,Bid*CTR,A,B,C,$1.00,$0.75,$0.50,1%,2%,2.5%,1cent,1.5cents,1.125cents,Complications(2),EachadvertiserhasalimitedbudgetSearchengineguaranteesthattheadvertiserwillnotbechargedmorethantheirdailybudget,Simplifiedmodel(fornow),Assumeallbidsare0or1EachadvertiserhasthesamebudgetBOneadvertiserperqueryLetstrythegreedyalgorithmArbitrarilypickaneligibleadvertiserforeachkeyword,Badscenarioforgreedy,TwoadvertisersAandBAbidsonqueryx,BbidsonxandyBothhavebudgetsof$4Querystream:xxxxyyyyWorstcasegreedychoice:BBBB_Optimal:AAAABBBBCompetitiveratio=Simpleanalysisshowsthisistheworstcase,BALANCEalgorithmMSVV,Mehta,Saberi,Vazirani,andVaziraniForeachquery,picktheadvertiserwiththelargestunspentbudgetBreaktiesarbitrarily,Example:BALANCE,TwoadvertisersAandBAbidsonqueryx,BbidsonxandyBothhavebudgetsof$4Querystream:xxxxyyyyBALANCEchoice:ABABBB_Optimal:AAAABBBBCompetitiveratio=,AnalyzingBALANCE,Considersimplecase:twoadvertisers,A1andA2,eachwithbudgetB(assumeB1)AssumeoptimalsolutionexhaustsbothadvertisersbudgetsBALANCEmustexhaustatleastoneadvertisersbudgetIfnot,wecanallocatemorequeriesAssumeBALANCEexhaustsA2sbudget,AnalyzingBalance,Optrevenue=2BBalancerevenue=2B-x=B+y,WehaveyxBalancerevenueisminimumforx=y=B/2MinimumBalancerevenue=3B/2CompetitiveRatio=3/4,QueriesallocatedtoA1inoptimalsolution,QueriesallocatedtoA2inoptimalsolution,GeneralResult,Inthegeneralcase,worstcompetitiveratioofBALANCEis11/e=approx.0.63Interestingly,noonlinealgorithmhasabettercompetitiveratioWontgothroughthedetailshere,butletsseetheworstcasethatgivesthisratio,WorstcaseforBALANCE,Nadvertisers,eachwithbudgetBN1NBqueriesappearinNroundsofBquerieseachRound1queries:biddersA1,A2,ANRound2queries:biddersA2,A3,ANRoundiqueries:biddersAi,ANOptimumallocation:allocateroundiqueriestoAiOptimumrevenueNB,BALANCEallocation,A1,A2,A3,AN-1,AN,Afterkrounds,sumofallocationstoeachofbinsAk,ANisSk=Sk+1=SN=11kB/(N-i+1),IfwefindthesmallestksuchthatSkB,thenafterkroundswecannotallocateanyqueriestoanyadvertiser,BALANCEanalysis,B/1B/2B/3B/(N-k+1)B/(N-1)B/N,S1,S2,Sk=B,BALANCEanalysis,Fact:Hn=1in1/i=approx.log(n)forlargenResultduetoEuler,1/11/21/31/(N-k+1)1/(N-1)1/N,log(N),Sk=1impliesHN-k=log(N)-1=log(N/e)N-k=N/ek=N(1-1/e),BALANCEanalysis,SoafterthefirstN(1-1/e)rounds,wecannotallocateaquerytoanyadvertiserRevenue=BN(1-1/e)Competitiveratio=1-1/e,Generalversionofproblem,Arbitrarybids,budgetsConsiderqueryq,advertiseriBid=xiBudget=biBALANCEcanbet