stanford大学-大数据挖掘-advertising-19

1、CS 345Data MiningOnline algorithmsSearch advertisingOnlinealgorithmsClassic model of algorithmsYouget to seetheentire input,then computesomefunctionofitInthis context, “offline algorithm”OnlinealgorithmYouget to seetheinputone piece at atime,and needtomakeirrevocabledecisionsalongthe waySimilar to d

2、atastream modelsExample:Bipartitematching1234abcdGirlsBoysExample:Bipartitematching1234abcdM =(1,a),(2,b),(3,d)isamatchingCardinalityofmatching= |M|= 3GirlsBoysExample:Bipartitematching1234abcdGirlsBoysM =(1,c),(2,b),(3,d),(4,a)isaperfect matchingMatchingAlgorithmProblem:Find amaximum-cardinalitymat

3、chingforagivenbipartitegraphA perfectone if it existsThereisa polynomial-timeoffline algorithm(Hopcroftand Karp1973)Butwhatifwedonthave theentiregraphupfront?OnlineproblemInitially, we aregiventheset BoysIneach round,onegirls choicesare revealedAtthat time, we havetodecide to either:Pair thegirl wit

4、haboyDontpair thegirl withany boyExample of application:assigningtaskstoserversOnlineproblem1234abcd(1,a)(2,b)(3,d)GreedyalgorithmPair thenewgirlwith anyeligibleboyIfthereisnone,dontpair girlHowgoodisthealgorithm?CompetitiveRatioForinputI,supposegreedyproducesmatchingMgreedywhileanoptimal matching i

5、s MoptCompetitiveratio=minallpossibleinputs I(|Mgreedy|/|Mopt|)Analyzingthe greedyalgorithmConsidertheset GofgirlsmatchedinMoptbutnot in MgreedyThen it mustbethe casethateveryboyadjacenttogirlsinGisalready matchedinMgreedyTheremust be at least |G|such boysOtherwisethe optimalalgorithm could nothave

6、matchedall theG girlsTherefore|Mgreedy|G|=|Mopt- Mgreedy|Mgreedy|/|Mopt|1/2Worst-case scenario1234abc(1,a)(2,b)dHistory of webadvertisingBannerads (1995-2001)Initial formofweb advertisingPopular websites chargedX$for every 1000“impressions”ofadCalled“CPM”rateModeled similartoTV, magazine adsUntarget

7、ed to demographicallytagetedLowclickthrough rateslowROI foradvertisersPerformance-basedadvertisingIntroduced by Overture around2000Advertisers“bid”onsearchkeywordsWhen someonesearchesfor thatkeyword,the highestbiddersadisshownAdvertiser is chargedonlyiftheadisclickedonSimilar model adoptedbyGoogle w

8、ithsomechanges around2002Called“Adwords”Adsvs. searchresultsWeb2.0Performance-basedadvertisingworks!Multi-billion-dollarindustryInterestingproblemsWhat adstoshow fora search?IfImanadvertiser,whichsearch terms shouldI bidonandhow muchtobid?Adwords problemA streamofqueries arrivesatthe searchengineq1,

9、q2,Several advertisers bidoneach queryWhen query qiarrives,searchengine mustpicka subsetofadvertiserswhoseadsare shownGoal:maximizesearchenginesrevenuesClearly we needanonline algorithm!GreedyalgorithmSimplestalgorithmisgreedyIts easytosee thatthe greedyalgorithmisactuallyoptimal!Complications (1)Ea

10、ch ad hasa differentlikelihood of being clickedAdvertiser 1bids$2,clickprobability=0.1Advertiser 2bids$1,clickprobability=0.5ClickthroughratemeasuredhistoricallySimplesolutionInstead of rawbids,usethe “expectedrevenue perclick”TheAdwordsInnovationAdvertiserBidCTRBid*CTRABC$1.00$0.75$0.501%2%2.5%1 ce

11、nt1.5cents1.125centsTheAdwordsInnovationAdvertiserBidCTRBid*CTRABC$1.00$0.75$0.501%2%2.5%1 cent1.5cents1.125centsComplications (2)Each advertiserhas alimitedbudgetSearchengine guaranteesthattheadvertiserwill notbecharged morethantheirdailybudgetSimplified model (fornow)Assumeall bidsare 0or1Each adv

12、ertiserhas thesame budgetBOneadvertiserperqueryLetstrythe greedyalgorithmArbitrarilypick an eligible advertiserfor eachkeywordBadscenariofor greedyTwoadvertisersAandBA bidsonqueryx,Bbids on xand yBoth havebudgetsof$4Querystream: xxxxyyyyWorstcase greedychoice: BBBB_Optimal:AAAABBBBCompetitiveratio=

13、SimpleanalysisshowsthisistheworstcaseBALANCE algorithmMSVVMehta, Saberi,Vazirani, andVaziraniForeachquery,picktheadvertiserwith thelargest unspentbudgetBreakties arbitrarilyExample:BALANCETwoadvertisersAandBA bidsonqueryx,Bbids on xand yBoth havebudgetsof$4Querystream: xxxxyyyyBALANCE choice:ABABBB_

14、Optimal:AAAABBBBCompetitiveratio= AnalyzingBALANCEConsidersimplecase:two advertisers,A1andA2, eachwithbudgetB(assume B1)Assumeoptimalsolutionexhaustsboth advertisersbudgetsBALANCE mustexhaustatleastoneadvertisers budgetIfnot, we canallocatemore queriesAssumeBALANCEexhaustsA2sbudgetAnalyzingBalanceA1

15、A2BxyBA1A2xOptrevenue= 2BBalance revenue=2B-x =B+yWehave yxBalance revenueisminimumforx=y=B/2Minimum Balancerevenue= 3B/2CompetitiveRatio= 3/4Queries allocatedtoA1inoptimal solutionQueries allocatedtoA2inoptimal solutionGeneral ResultInthegeneralcase,worstcompetitiveratioofBALANCE is11/e= approx.0.6

16、3Interestingly,noonlinealgorithm hasa bettercompetitiveratioWontgothrough thedetails here, butletsseethe worst casethatgivesthis ratioWorstcase forBALANCEN advertisers,each withbudget BN1NBqueries appearinN roundsofB querieseachRound1 queries: biddersA1, A2, , ANRound2 queries: biddersA2, A3, , ANRo

17、undi queries: biddersAi, , ANOptimum allocation: allocate round iqueriestoAiOptimum revenueNBBALANCE allocationA1A2A3AN-1ANB/NB/(N-1)B/(N-2)Afterk rounds,sum of allocations to eachofbinsAk,ANisSk= Sk+1= =SN=11kB/(N-i+1)Ifwefind thesmallestk suchthatSkB,then after kroundswecannotallocateany queriesto

18、any advertiserBALANCE analysisB/1B/2B/3B/(N-k+1) B/(N-1)B/NS1S2Sk= B1/1 1/2 1/3 1/(N-k+1) 1/(N-1) 1/NS1S2Sk = 1 BALANCE analysisFact:Hn=1in1/i=approx. log(n)forlargenResultdue to Euler1/11/21/31/(N-k+1) 1/(N-1)1/NSk = 1 log(N)log(N)-1Sk= 1impliesHN-k= log(N)-1 =log(N/e)N-k=N/ek =N(1-1/e)BALANCE analysisSoafterthefirstN(1-1/e)rounds,wecannotallocateaquerytoanyadvertiserRevenue =BN(1-1/e)Competitiveratio= 1-1/eGeneral versionofproblemArbitrarybids,budgetsConsiderqueryq,advertiser iBid=xiBudget=biBALANCE canbeter