stanford大學(xué)-大數(shù)據(jù)挖掘-advertising-192025/10/16stanford大學(xué)大數(shù)據(jù)挖掘advertising19OnlinealgorithmsClassicmodelofalgorithmsYougettoseetheentireinput,thencomputesomefunctionofitInthiscontext,“offlinealgorithm”O(jiān)nlinealgorithmYougettoseetheinputonepieceatatime,andneedtomakeirrevocabledecisionsalongthewaySimilartodatastreammodelsstanford大學(xué)大數(shù)據(jù)挖掘advertising19Example:Bipartitematching1234abcdGirlsBoysstanford大學(xué)大數(shù)據(jù)挖掘advertising19Example:Bipartitematching1234abcdM={(1,a),(2,b),(3,d)}isamatchingCardinalityofmatching=|M|=3GirlsBoysstanford大學(xué)大數(shù)據(jù)挖掘advertising19Example:Bipartitematching1234abcdGirlsBoysM={(1,c),(2,b),(3,d),(4,a)}isaperfectmatchingstanford大學(xué)大數(shù)據(jù)挖掘advertising19MatchingAlgorithmProblem:Findamaximum-cardinalitymatchingforagivenbipartitegraphAperfectoneifitexistsThereisapolynomial-timeofflinealgorithm(HopcroftandKarp1973)Butwhatifwedon’thavetheentiregraphupfront?stanford大學(xué)大數(shù)據(jù)挖掘advertising19OnlineproblemInitially,wearegiventhesetBoysIneachround,onegirl’schoicesarerevealedAtthattime,wehavetodecidetoeither:PairthegirlwithaboyDon’tpairthegirlwithanyboyExampleofapplication:assigningtaskstoserversstanford大學(xué)大數(shù)據(jù)挖掘advertising19Onlineproblem1234abcd(1,a)(2,b)(3,d)stanford大學(xué)大數(shù)據(jù)挖掘advertising19GreedyalgorithmPairthenewgirlwithanyeligibleboyIfthereisnone,don’tpairgirlHowgoodisthealgorithm?stanford大學(xué)大數(shù)據(jù)挖掘advertising19CompetitiveRatioForinputI,supposegreedyproducesmatchingMgreedywhileanoptimalmatchingisMoptCompetitiveratio= minallpossibleinputsI(|Mgreedy|/|Mopt|)stanford大學(xué)大數(shù)據(jù)挖掘advertising19AnalyzingthegreedyalgorithmConsiderthesetGofgirlsmatchedinMoptbutnotinMgreedyThenitmustbethecasethateveryboyadjacenttogirlsinGisalreadymatchedinMgreedyTheremustbeatleast|G|suchboysOtherwisetheoptimalalgorithmcouldnothavematchedalltheGgirlsTherefore|Mgreedy|?|G|=|Mopt-Mgreedy||Mgreedy|/|Mopt|?1/2stanford大學(xué)大數(shù)據(jù)挖掘advertising19Worst-casescenario1234abc(1,a)(2,b)dstanford大學(xué)大數(shù)據(jù)挖掘advertising19HistoryofwebadvertisingBannerads(1995-2001)InitialformofwebadvertisingPopularwebsiteschargedX$forevery1000“impressions”ofadCalled“CPM”rateModeledsimilartoTV,magazineadsUntargetedtodemographicallytagetedLowclickthroughrateslowROIforadvertisersstanford大學(xué)大數(shù)據(jù)挖掘advertising19Performance-basedadvertisingIntroducedbyOverturearound2000Advertisers“bid”onsearchkeywordsWhensomeonesearchesforthatkeyword,thehighestbidder’sadisshownAdvertiserischargedonlyiftheadisclickedonSimilarmodeladoptedbyGooglewithsomechangesaround2002Called“Adwords”stanford大學(xué)大數(shù)據(jù)挖掘advertising19Adsvs.searchresultsstanford大學(xué)大數(shù)據(jù)挖掘advertising19Web2.0Performance-basedadvertisingworks!Multi-billion-dollarindustryInterestingproblemsWhatadstoshowforasearch?IfI’manadvertiser,whichsearchtermsshouldIbidonandhowmuchtobid?stanford大學(xué)大數(shù)據(jù)挖掘advertising19AdwordsproblemAstreamofqueriesarrivesatthesearchengineq1,q2,…SeveraladvertisersbidoneachqueryWhenqueryqiarrives,searchenginemustpickasubsetofadvertiserswhoseadsareshownGoal:maximizesearchengine’srevenuesClearlyweneedanonlinealgorithm!stanford大學(xué)大數(shù)據(jù)挖掘advertising19GreedyalgorithmSimplestalgorithmisgreedyIt’seasytoseethatthegreedyalgorithmisactuallyoptimal!stanford大學(xué)大數(shù)據(jù)挖掘advertising19Complications(1)EachadhasadifferentlikelihoodofbeingclickedAdvertiser1bids$2,clickprobability=0.1Advertiser2bids$1,clickprobability=0.5ClickthroughratemeasuredhistoricallySimplesolutionInsteadofrawbids,usethe“expectedrevenueperclick”stanford大學(xué)大數(shù)據(jù)挖掘advertising19TheAdwordsInnovationAdvertiserBidCTRBid*CTRABC$1.00$0.75$0.501%2%2.5%1cent1.5cents1.125centsstanford大學(xué)大數(shù)據(jù)挖掘advertising19TheAdwordsInnovationAdvertiserBidCTRBid*CTRABC$1.00$0.75$0.501%2%2.5%1cent1.5cents1.125centsstanford大學(xué)大數(shù)據(jù)挖掘advertising19Complications(2)EachadvertiserhasalimitedbudgetSearchengineguaranteesthattheadvertiserwillnotbechargedmorethantheirdailybudgetstanford大學(xué)大數(shù)據(jù)挖掘advertising19Simplifiedmodel(fornow)Assumeallbidsare0or1EachadvertiserhasthesamebudgetBOneadvertiserperqueryLet’strythegreedyalgorithmArbitrarilypickaneligibleadvertiserforeachkeywordstanford大學(xué)大數(shù)據(jù)挖掘advertising19BadscenarioforgreedyTwoadvertisersAandBAbidsonqueryx,BbidsonxandyBothhavebudgetsof$4Querystream:xxxxyyyyWorstcasegreedychoice:BBBB____Optimal:AAAABBBBCompetitiveratio=?Simpleanalysisshowsthisistheworstcasestanford大學(xué)大數(shù)據(jù)挖掘advertising19BALANCEalgorithm[MSVV][Mehta,Saberi,Vazirani,andVazirani]Foreachquery,picktheadvertiserwiththelargestunspentbudgetBreaktiesarbitrarilystanford大學(xué)大數(shù)據(jù)挖掘advertising19Example:BALANCETwoadvertisersAandBAbidsonqueryx,BbidsonxandyBothhavebudgetsof$4Querystream:xxxxyyyyBALANCEchoice:ABABBB__Optimal:AAAABBBBCompetitiveratio=?stanford大學(xué)大數(shù)據(jù)挖掘advertising19AnalyzingBALANCEConsidersimplecase:twoadvertisers,A1andA2,eachwithbudgetB(assumeBà1)Assumeoptimalsolutionexhaustsbothadvertisers’budgetsBALANCEmustexhaustatleastoneadvertiser’sbudgetIfnot,wecanallocatemorequeriesAssumeBALANCEexhaustsA2’sbudgetstanford大學(xué)大數(shù)據(jù)挖掘advertising19AnalyzingBalanceA1A2BxyBA1A2xOptrevenue=2BBalancerevenue=2B-x=B+yWehavey?xBalancerevenueisminimumforx=y=B/2MinimumBalancerevenue=3B/2CompetitiveRatio=3/4QueriesallocatedtoA1inoptimalsolutionQueriesallocatedtoA2inoptimalsolutionstanford大學(xué)大數(shù)據(jù)挖掘advertising19GeneralResultInthegeneralcase,worstcompetitiveratioofBALANCEis1–1/e=approx.0.63Interestingly,noonlinealgorithmhasabettercompetitiveratioWon’tgothroughthedetailshere,butlet’sseetheworstcasethatgivesthisratiostanford大學(xué)大數(shù)據(jù)挖掘advertising19WorstcaseforBALANCENadvertisers,eachwithbudgetBàNà1NBqueriesappearinNroundsofBquerieseachRound1queries:biddersA1,A2,…,ANRound2queries:biddersA2,A3,…,ANRoundiqueries:biddersAi,…,ANOptimumallocation:allocateroundiqueriestoAiOptimumrevenueNBstanford大學(xué)大數(shù)據(jù)挖掘advertising19BALANCEallocation…A1A2A3AN-1ANB/NB/(N-1)B/(N-2)Afterkrounds,sumofallocationstoeachofbinsAk,…,ANisSk=Sk+1=…=SN=

1·1·kB/(N-i+1)IfwefindthesmallestksuchthatSk

?B,thenafterkroundswecannotallocateanyqueriestoanyadvertiserstanford大學(xué)大數(shù)據(jù)挖掘advertising19BALANCEanalysisB/1B/2B/3…B/(N-k+1)…B/(N-1)B/NS1S2Sk=B

1/11/2