《stanford大学-大数据挖掘-advertising-19》由会员分享，可在线阅读，更多相关《stanford大学-大数据挖掘-advertising-19（36页珍藏版）》请在金锄头文库上搜索。
1、CS 345Data Mining,Online algorithmsSearch advertising,Online algorithms,Classic model of algorithmsYou get to see the entire input, then compute some function of itIn this context, “offline algorithm”Online algorithmYou get to see the input one piece at a time, and need to make irrevocable decisions
2、 along the waySimilar to data stream models,Example: Bipartite matching,1,2,3,4,a,b,c,d,Girls,Boys,Example: Bipartite matching,1,2,3,4,a,b,c,d,M = (1,a),(2,b),(3,d) is a matchingCardinality of matching = |M| = 3,Girls,Boys,Example: Bipartite matching,1,2,3,4,a,b,c,d,Girls,Boys,M = (1,c),(2,b),(3,d),
3、(4,a) is a perfect matching,Matching Algorithm,Problem: Find a maximum-cardinality matching for a given bipartite graphA perfect one if it existsThere is a polynomial-time offline algorithm (Hopcroft and Karp 1973)But what if we dont have the entire graph upfront?,Online problem,Initially, we are gi
4、ven the set BoysIn each round, one girls choices are revealedAt that time, we have to decide to either:Pair the girl with a boyDont pair the girl with any boyExample of application: assigning tasks to servers,Online problem,1,2,3,4,(1,a),(2,b),(3,d),Greedy algorithm,Pair the new girl with any eligib
5、le boyIf there is none, dont pair girlHow good is the algorithm?,Competitive Ratio,For input I, suppose greedy produces matching Mgreedy while an optimal matching is MoptCompetitive ratio = minall possible inputs I (|Mgreedy|/|Mopt|),Analyzing the greedy algorithm,Consider the set G of girls matched
6、 in Mopt but not in MgreedyThen it must be the case that every boy adjacent to girls in G is already matched in MgreedyThere must be at least |G| such boysOtherwise the optimal algorithm could not have matched all the G girlsTherefore |Mgreedy| |G| = |Mopt - Mgreedy|Mgreedy|/|Mopt| 1/2,Worst-case sc
7、enario,1,2,3,4,(1,a),(2,b),History of web advertising,Banner ads (1995-2001)Initial form of web advertisingPopular websites charged X$ for every 1000 “impressions” of adCalled “CPM” rateModeled similar to TV, magazine adsUntargeted to demographically tagetedLow clickthrough rateslow ROI for advertis
8、ers,Performance-based advertising,Introduced by Overture around 2000Advertisers “bid” on search keywordsWhen someone searches for that keyword, the highest bidders ad is shownAdvertiser is charged only if the ad is clicked onSimilar model adopted by Google with some changes around 2002Called “Adword
9、s”,Ads vs. search results,Web 2.0,Performance-based advertising works!Multi-billion-dollar industryInteresting problemsWhat ads to show for a search?If Im an advertiser, which search terms should I bid on and how much to bid?,Adwords problem,A stream of queries arrives at the search engineq1, q2,Sev
10、eral advertisers bid on each queryWhen query qi arrives, search engine must pick a subset of advertisers whose ads are shownGoal: maximize search engines revenuesClearly we need an online algorithm!,Greedy algorithm,Simplest algorithm is greedyIts easy to see that the greedy algorithm is actually op
11、timal!,Complications (1),Each ad has a different likelihood of being clickedAdvertiser 1 bids $2, click probability = 0.1Advertiser 2 bids $1, click probability = 0.5Clickthrough rate measured historicallySimple solutionInstead of raw bids, use the “expected revenue per click”,The Adwords Innovation
12、,Advertiser,Bid,CTR,Bid * CTR,A,B,C,$1.00,$0.75,$0.50,1%,2%,2.5%,1 cent,1.5 cents,1.125 cents,The Adwords Innovation,Advertiser,Bid,CTR,Bid * CTR,A,B,C,$1.00,$0.75,$0.50,1%,2%,2.5%,1 cent,1.5 cents,1.125 cents,Complications (2),Each advertiser has a limited budgetSearch engine guarantees that the ad
13、vertiser will not be charged more than their daily budget,Simplified model (for now),Assume all bids are 0 or 1Each advertiser has the same budget BOne advertiser per queryLets try the greedy algorithmArbitrarily pick an eligible advertiser for each keyword,Bad scenario for greedy,Two advertisers A
14、and BA bids on query x, B bids on x and yBoth have budgets of $4Query stream: xxxxyyyyWorst case greedy choice: BBBB_Optimal: AAAABBBBCompetitive ratio = Simple analysis shows this is the worst case,BALANCE algorithm MSVV,Mehta, Saberi, Vazirani, and VaziraniFor each query, pick the advertiser with
15、the largest unspent budgetBreak ties arbitrarily,Example: BALANCE,Two advertisers A and BA bids on query x, B bids on x and yBoth have budgets of $4Query stream: xxxxyyyyBALANCE choice: ABABBB_Optimal: AAAABBBBCompetitive ratio = ,Analyzing BALANCE,Consider simple case: two advertisers, A1 and A2, e
16、ach with budget B (assume B 1)Assume optimal solution exhausts both advertisers budgetsBALANCE must exhaust at least one advertisers budgetIf not, we can allocate more queriesAssume BALANCE exhausts A2s budget,Analyzing Balance,Opt revenue = 2BBalance revenue = 2B-x = B+y,We have y xBalance revenue is minimum for x=y=B/2Minimum Balance revenue = 3B/2Competitive Ratio = 3/4,
