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

CS345DataMiningOnlinealgorithmsSearchadvertisingOnlinealgorithmsClassicmodelofalgorithmsYougettoseetheentireinput,thencomputesomefunctionofitInthiscontext,“offlinealgorithm”OnlinealgorithmYougettoseetheinputonepieceatatime,andneedtomakeirrevocabledecisionsalongthewaySimilartodatastreammodelsExample:Bipartitematching1234abcdGirlsBoysExample:Bipartitematching1234abcdM={(1,a),(2,b),(3,d)}isamatchingCardinalityofmatching=|M|=3GirlsBoysExample:Bipartitematching1234abcdGirlsBoysM={(1,c),(2,b),(3,d),(4,a)}isaperfectmatchingMatchingAlgorithmProblem:Findamaximum-cardinalitymatchingforagivenbipartitegraphAperfectoneifitexistsThereisapolynomial-timeofflinealgorithm(HopcroftandKarp1973)Butwhatifwedon’thavetheentiregraphupfront?OnlineproblemInitially,wearegiventhesetBoysIneachround,onegirl’schoicesarerevealedAtthattime,wehavetodecidetoeither:PairthegirlwithaboyDon’tpairthegirlwithanyboyExampleofapplication:assigningtaskstoserversOnlineproblem1234abcd(1,a)(2,b)(3,d)GreedyalgorithmPairthenewgirlwithanyeligibleboyIfthereisnone,don’tpairgirlHowgoodisthealgorithm?CompetitiveRatioForinputI,supposegreedyproducesmatchingMgreedywhileanoptimalmatchingisMoptCompetitiveratio=minallpossibleinputsI(|Mgreedy|/|Mopt|)AnalyzingthegreedyalgorithmConsiderthesetGofgirlsmatchedinMoptbutnotinMgreedyThenitmustbethecasethateveryboyadjacenttogirlsinGisalreadymatchedinMgreedyTheremustbeatleast|G|suchboysOtherwisetheoptimalalgorithmcouldnothavematchedalltheGgirlsTherefore|Mgreedy|¸|G|=|Mopt-Mgreedy||Mgreedy|/|Mopt|¸1/2Worst-casescenario1234abc(1,a)(2,b)dHistoryofwebadvertisingBannerads(1995-2001)InitialformofwebadvertisingPopularwebsiteschargedX$forevery1000“impressions”ofadCalled“CPM”rateModeledsimilartoTV,magazineadsUntargetedtodemographicallytagetedLowclickthroughrateslowROIforadvertisersPerformance-basedadvertisingIntroducedbyOverturearound2000Advertisers“bid”onsearchkeywordsWhensomeonesearchesforthatkeyword,thehighestbidder’sadisshownAdvertiserischargedonlyiftheadisclickedonSimilarmodeladoptedbyGooglewithsomechangesaround2002Called“Adwords”Adsvs.searchresultsWeb2.0Performance-basedadvertisingworks!Multi-billion-dollarindustryInterestingproblemsWhatadstoshowforasearch?IfI’manadvertiser,whichsearchtermsshouldIbidonandhowmuchtobid?AdwordsproblemAstreamofqueriesarrivesatthesearchengineq1,q2,…SeveraladvertisersbidoneachqueryWhenqueryqiarrives,searchenginemustpickasubsetofadvertiserswhoseadsareshownGoal:maximizesearchengine’srevenuesClearlyweneedanonlinealgorithm!GreedyalgorithmSimplestalgorithmisgreedyIt’seasytoseethatthegreedyalgorithmisactuallyoptimal!Complications(1)EachadhasadifferentlikelihoodofbeingclickedAdvertiser1bids$2,clickprobability=0.1Advertiser2bids$1,clickprobability=0.5ClickthroughratemeasuredhistoricallySimplesolutionInsteadofrawbids,usethe“expectedrevenueperclick”TheAdwordsInnovationAdvertiserBidCTRBid*CTRABC$1.00$0.75$0.501%2%2.5%1cent1.5cents1.125centsTheAdwordsInnovationAdvertiserBidCTRBid*CTRABC$1.00$0.75$0.501%2%2.5%1cent1.5cents1.125centsComplications(2)EachadvertiserhasalimitedbudgetSearchengineguaranteesthattheadvertiserwillnotbechargedmorethantheirdailybudgetSimplifiedmodel(fornow)Assumeallbidsare0or1EachadvertiserhasthesamebudgetBOneadvertiserperqueryLet’strythegreedyalgorithmArbitrarilypickaneligibleadvertiserforeachkeywordBadscenarioforgreedyTwoadvertisersAandBAbidsonqueryx,BbidsonxandyBothhavebudgetsof$4Querystream:xxxxyyyyWorstcasegreedychoice:BBBB____Optimal:AAAABBBBCompetitiveratio=½SimpleanalysisshowsthisistheworstcaseBALANCEalgorithm[MSVV][Mehta,Saberi,Vazirani,andVazirani]Foreachquery,picktheadvertiserwiththelargestunspentbudgetBreaktiesarbitrarilyExample:BALANCETwoadvertisersAandBAbidsonqueryx,BbidsonxandyBothhavebudgetsof$4Querystream:xxxxyyyyBALANCEchoice:ABABBB__Optimal:AAAABBBBCompetitiveratio=¾AnalyzingBALANCEConsidersimplecase:twoadvertisers,A1andA2,eachwithbudgetB(assumeBÀ1)Assumeoptimalsolutionexhaustsbothadvertisers’budgetsBALANCEmustexhaustatleastoneadvertiser’sbudgetIfnot,wecanallocatemorequeriesAssumeBALANCEexhaustsA2’sbudgetAnalyzingBalanceA1A2BxyBA1A2xOptrevenue=2BBalancerevenue=2B-x=B+yWehavey¸xBalancerevenueisminimumforx=y=B/2MinimumBalancerevenue=3B/2CompetitiveRatio=3/4QueriesallocatedtoA1inoptimalsolutionQueriesallocatedtoA2inoptimalsolutionGeneralResultInthegeneralcase,worstcompetitiveratioofBALANCEis1–1/e=approx.0.63Interestingly,noonlinealgorithmhasabettercompetitiveratioWon’tgothroughthedetailshere,butlet’sseetheworstcasethatgivesthisratioWorstcaseforBALANCENadvertisers,eachwithbudgetBÀNÀ1NBqueriesappearinNroundsofBquerieseachRound1queries:biddersA1,A2,…,ANRound2queries:biddersA2,A3,…,ANRoundiqueries:biddersAi,…,ANOptimumallocation:allocateroundiqueriestoAiOptimumrevenueNBBALANCEallocation…A1A2A3AN-1ANB/NB/(N-1)B/(N-2)Afterkrounds,sumofallocationstoeachofbinsAk,…,ANisSk=Sk+1=…=SN=1·1·kB/(N-i+1)IfwefindthesmallestksuchthatSk¸B,thenafterkroundswecannotallocateanyqueriestoanyadvertiserBALANC