1 00:00:00,250 --> 00:00:02,240 Welcome back to Mining of Massive Datasets. 2 00:00:02,240 --> 00:00:04,930 We continue our discussion of online algorithms. 3 00:00:04,930 --> 00:00:08,450 Now, we just warmed up by looking at an online algorithm called 4 00:00:08,450 --> 00:00:11,810 a greedy algorithm for the bipartite graph matching problem. 5 00:00:11,810 --> 00:00:14,900 We're going to look now at an application of online algorithms, 6 00:00:14,900 --> 00:00:17,490 which is performance based advertising and in particular, 7 00:00:17,490 --> 00:00:19,990 we're going to look at a problem called the AdWords problem. 8 00:00:22,020 --> 00:00:25,820 Let's a start with a short history of advertising on the web. 9 00:00:25,820 --> 00:00:30,800 Now, from you know, web advertising started almost simultaneously with 10 00:00:30,800 --> 00:00:32,370 the World Wide Web itself. 11 00:00:32,370 --> 00:00:33,610 In the early days of the web, 12 00:00:33,610 --> 00:00:36,214 the only kind of ads that you see online were banner ads. 13 00:00:37,300 --> 00:00:42,100 And these reigned supreme from til about 2001. 14 00:00:42,100 --> 00:00:44,340 And banner ads were very, very simple. 15 00:00:44,340 --> 00:00:48,030 They were graphical units that, that you saw on webpages. 16 00:00:48,030 --> 00:00:52,590 And popular websites charged certain number of dollars for 17 00:00:52,590 --> 00:00:54,920 every 1,000 impressions of the ad. 18 00:00:54,920 --> 00:00:59,740 This is called the, the CPM rate, or the cost per thousand impressions, where M is 19 00:00:59,740 --> 00:01:05,390 the Roman numeral for, for a thousand, and that's why it's called a CPM rate. 20 00:01:05,390 --> 00:01:09,620 And this, this model comes to us from TV or magazine ads, 21 00:01:09,620 --> 00:01:13,840 which are priced similarly based on the circulation of the magazine or the, or 22 00:01:13,840 --> 00:01:16,752 the number of viewers of the, of the TV show. 23 00:01:16,752 --> 00:01:21,207 And this was a good initial model to, to start off with but 24 00:01:21,207 --> 00:01:27,378 it doesn't really you know, exploit a lot of information that we have available 25 00:01:27,378 --> 00:01:33,090 on the web that we don't have available, you know, on TV or in a magazine ad. 26 00:01:33,090 --> 00:01:37,512 In particular, these ads are very, very untargeted so the same ad is shown to 27 00:01:37,512 --> 00:01:42,410 everyone who comes to a website or, or sees a particular page on a website. 28 00:01:42,410 --> 00:01:47,090 And so these ads, not surprisingly, performed really, really poorly. 29 00:01:47,090 --> 00:01:48,930 Now, how do you measure performance? 30 00:01:48,930 --> 00:01:52,350 Typically, advertisers measure performance of ads by looking at 31 00:01:52,350 --> 00:01:55,200 how many people click on, on the ad. 32 00:01:55,200 --> 00:01:58,040 What they look at is what's called the click through rate which is the ratio of 33 00:01:58,040 --> 00:02:01,800 the number of clicks the ad receives divided by the number of 34 00:02:01,800 --> 00:02:03,890 impressions of that ad. 35 00:02:03,890 --> 00:02:07,100 Remember, impressions are what the advertiser is paying for 36 00:02:07,100 --> 00:02:10,860 in the CPM rate,and the clicks are what they want uh,and so 37 00:02:10,860 --> 00:02:14,350 they measure the return on advertise, the return on investment. 38 00:02:14,350 --> 00:02:19,580 RO or ROI by looking at the ratio of clicks to impressions. 39 00:02:20,730 --> 00:02:24,600 Not surprisingly, the early banner ads, which are completely untargeted, 40 00:02:24,600 --> 00:02:29,090 have very low click-through rates and very low ROI for advertisers. 41 00:02:29,090 --> 00:02:34,270 And this sort of prompted a move of banner advertising that went 42 00:02:34,270 --> 00:02:38,286 from untargeted and then it's going to move to demographically targeted. 43 00:02:38,286 --> 00:02:41,350 You can sort of give demographic information, 44 00:02:41,350 --> 00:02:44,390 broad demographic information about the kinds of people who are likely to 45 00:02:44,390 --> 00:02:48,350 see a given webpage, and target, ads to those people. 46 00:02:48,350 --> 00:02:50,355 For example, you can place, 47 00:02:50,355 --> 00:02:55,310 automobile ads, on, on a site about car repair for instance, right? 48 00:02:55,310 --> 00:03:01,642 So, you can sort of broadly, demographically target ads to specific, 49 00:03:01,642 --> 00:03:04,601 to specific websites, but in general these ads 50 00:03:04,601 --> 00:03:08,860 still don't perform really well because they are very broadly targeted. 51 00:03:08,860 --> 00:03:13,310 Now all this changed with with the advent of 52 00:03:13,310 --> 00:03:17,590 next new form of advertising called performance based advertising. 53 00:03:17,590 --> 00:03:21,150 And, performance based advertising was first introduced by 54 00:03:21,150 --> 00:03:22,860 a company called Robiture. 55 00:03:22,860 --> 00:03:23,930 Around the year, 2000. 56 00:03:23,930 --> 00:03:28,200 Now, a lot of you may not remember Overture, but, 57 00:03:28,200 --> 00:03:33,690 it was another search engine, you know, that, existed, around the year 2000. 58 00:03:33,690 --> 00:03:38,840 and, their innovation, i, it at Overture, 59 00:03:38,840 --> 00:03:42,880 was that they, allowed advertisers to bid on search keywords. 60 00:03:42,880 --> 00:03:47,050 So people searched on Overture, much as they search on search engines like Google 61 00:03:47,050 --> 00:03:52,490 and Bing today and advertisers bid to appear you know, 62 00:03:52,490 --> 00:03:56,890 on those search results by bidding on specific search keywords. 63 00:03:56,890 --> 00:03:58,590 And when somebody searches for 64 00:03:58,590 --> 00:04:03,710 that keyword, then Overture used to show the ad of the highest bidder. 65 00:04:03,710 --> 00:04:07,170 Followed by the actual search results. 66 00:04:07,170 --> 00:04:10,110 But the key innovation that Overture made was 67 00:04:10,110 --> 00:04:14,000 that the advertisers was charged only if the ad was actually clicked on. 68 00:04:14,000 --> 00:04:16,320 Right? The advertiser did not charge you know, 69 00:04:16,320 --> 00:04:18,060 did not pay for the impression. 70 00:04:18,060 --> 00:04:20,430 But they pay only for the click. 71 00:04:20,430 --> 00:04:22,820 And so this is called performance-based ad, 72 00:04:22,820 --> 00:04:27,930 advertising, or cost per click advertising to distinguish it from the, the, 73 00:04:27,930 --> 00:04:32,190 the, the impression based or CTM advertising that preceded it. 74 00:04:33,830 --> 00:04:38,370 Now it turns out that advertisers really like performance-based advertising, or 75 00:04:38,370 --> 00:04:39,830 CPC advertising. 76 00:04:39,830 --> 00:04:45,905 And and Overture did really well and ended up being acquired by, by Yahoo. 77 00:04:45,905 --> 00:04:51,950 Um,much later on, however Google, which was another site and 78 00:04:51,950 --> 00:04:55,460 it was just getting started at roughly the same time you know, 79 00:04:55,460 --> 00:05:00,670 adopted a very similar model to around 2002 and they call it AdWords. 80 00:05:00,670 --> 00:05:04,260 Now we're all familiar with AdWords when we search on Google today, 81 00:05:04,260 --> 00:05:06,730 when we see these, see these ads. 82 00:05:06,730 --> 00:05:12,920 On Google, which are ads that are targeted to the searches that we do and 83 00:05:12,920 --> 00:05:17,170 the, the idea originally came from, from Overture and then was adopted by Google. 84 00:05:17,170 --> 00:05:22,010 And as we will see, Google made some 85 00:05:23,460 --> 00:05:29,040 important changes to the Overture model in terms of how advertisers bid. 86 00:05:29,040 --> 00:05:30,800 And what ads gets shown. 87 00:05:32,910 --> 00:05:36,850 Now it turns out that performance-based advertising actually works. 88 00:05:36,850 --> 00:05:41,560 Advertisers they like to pay on pay per click as opposed to impressions. 89 00:05:41,560 --> 00:05:45,060 And so, it is a multi-billion dollar industry primarily 90 00:05:45,060 --> 00:05:47,320 around search marketing. 91 00:05:47,320 --> 00:05:48,430 And there are a number of 92 00:05:48,430 --> 00:05:51,820 algorithmic challenges around performance-based advertising. 93 00:05:53,000 --> 00:05:56,350 There are, you know, they, they roughly fall in to two buckets. 94 00:05:56,350 --> 00:06:00,310 The first bucket is, from the point of view of a search engine, 95 00:06:00,310 --> 00:06:04,050 which is what ads do I show for a given query? 96 00:06:04,050 --> 00:06:06,530 And that's the topic of today's lecture. 97 00:06:06,530 --> 00:06:10,200 And the second set of challenges come from an advertiser point of view. 98 00:06:10,200 --> 00:06:12,380 And the problem here is, if I'm an advertiser, 99 00:06:12,380 --> 00:06:17,060 which search term should I bid on, and how much should I bid for the search term? 100 00:06:17,060 --> 00:06:19,600 Now this is not the focus of today's lecture, but 101 00:06:19,600 --> 00:06:20,990 it's in fact a very important problem. 102 00:06:20,990 --> 00:06:25,920 And there's an entire industry segment that focuses around this problem as well. 103 00:06:27,230 --> 00:06:32,870 So we formalize, the, the problem, of, from the search engine's point of view. 104 00:06:33,930 --> 00:06:35,900 We call it the AdWords problem, 105 00:06:35,900 --> 00:06:41,240 because formulated in the context of Google's, AdWords. 106 00:06:41,240 --> 00:06:45,750 And in the AdWords problem, a stream of queries arrives at the search engine and 107 00:06:45,750 --> 00:06:48,910 let's, let's say it's q1, q2, q3, and so on. 108 00:06:48,910 --> 00:06:52,610 And, in general, a search engine knows the query that it has seen so 109 00:06:52,610 --> 00:06:55,420 far, but it cannot predict the queries it's going to see next. 110 00:06:58,170 --> 00:07:01,053 Now, several advertisers have bid on each search query. 111 00:07:03,711 --> 00:07:07,829 When a query qi arrives the search engine must pick a subset of 112 00:07:07,829 --> 00:07:10,930 advertisers whose ads are shown. 113 00:07:10,930 --> 00:07:11,680 Right? 114 00:07:11,680 --> 00:07:17,620 When you search, there's a number of, advertisers who bid for that, keyword. 115 00:07:17,620 --> 00:07:20,930 Now there's usually a larger set of advertisers that have bid for a keyword. 116 00:07:20,930 --> 00:07:22,960 Than the search engine can show. 117 00:07:22,960 --> 00:07:27,050 Most search engines have a policy that, that said they will show, at most, one ad. 118 00:07:27,050 --> 00:07:29,818 Or two ads, or three ads for each search query. 119 00:07:29,818 --> 00:07:32,940 Then there may be tens of hundreds of bidders for each search query. 120 00:07:32,940 --> 00:07:38,230 So the search engine must decide which subset of advertisers it'll pick and 121 00:07:38,230 --> 00:07:40,530 show their ads for that search query. 122 00:07:40,530 --> 00:07:45,970 And remember, this looks very very similar to the model for 123 00:07:45,970 --> 00:07:48,430 bipartite graph matching, and it's no coincidence. 124 00:07:51,100 --> 00:07:53,780 The goal is to maximize a search engine's, 125 00:07:53,780 --> 00:07:58,770 revenues by showing the, the appropriate set of ads. 126 00:07:58,770 --> 00:08:02,800 And, clearly we need an online algorithm in this case because the, 127 00:08:02,800 --> 00:08:05,990 the search engine can only see one query at a time. 128 00:08:05,990 --> 00:08:10,600 And it must make an irrevocable decision of, of deciding which ads to show, but 129 00:08:10,600 --> 00:08:14,800 it cannot go back and change, the ad that showed in the past, nor 130 00:08:14,800 --> 00:08:17,580 does it know what queries are going to come in the future. 131 00:08:17,580 --> 00:08:21,000 So, we need, an online algorithm, for this problem, 132 00:08:21,000 --> 00:08:24,761 very similar to the algorithm that we had for the bipartite graph matching problem. 133 00:08:26,200 --> 00:08:31,090 Now, it turns out that there is a very simple heuristic that you can use to 134 00:08:31,090 --> 00:08:33,368 create an online algorithm for the AdWords problem. 135 00:08:33,368 --> 00:08:36,680 And that heuristic is called expected revenue. 136 00:08:36,680 --> 00:08:39,130 Let's first look at a very simple example. 137 00:08:39,130 --> 00:08:43,530 Let's say we have a particular query, Q, and we have three advertisers, A, B, and 138 00:08:43,530 --> 00:08:46,660 C, who have each bid on query Q. 139 00:08:46,660 --> 00:08:49,710 And their bids are shown in this table here. 140 00:08:49,710 --> 00:08:52,990 Advertiser A has bid $1 for each click. 141 00:08:52,990 --> 00:08:56,090 Advertiser B has bid $0.75 for each click. 142 00:08:56,090 --> 00:08:59,180 And Advertiser C has bid $0.50 per click. 143 00:08:59,180 --> 00:09:01,680 Remember now, these are bids per click. 144 00:09:01,680 --> 00:09:06,310 So, if the search engines decides to show Advertiser As ad, 145 00:09:06,310 --> 00:09:11,490 then Advertiser A pays if' there is a click at that time. 146 00:09:11,490 --> 00:09:15,380 The advertiser A doesn't pay anything if the user doesn't click on the ad but 147 00:09:15,380 --> 00:09:17,460 the ad just gets shown, right? 148 00:09:17,460 --> 00:09:20,210 Now, the search engine doesn't know apriori whether the ad is going to get 149 00:09:20,210 --> 00:09:21,880 clicked or not. 150 00:09:21,880 --> 00:09:23,370 so. 151 00:09:23,370 --> 00:09:27,230 The simple, heuristic that Overture used when they first, 152 00:09:27,230 --> 00:09:33,000 introduced, you know, performance based advertising was to just show the, 153 00:09:33,000 --> 00:09:35,040 the ad from the highest paying advertiser. 154 00:09:35,040 --> 00:09:39,500 They used to, sort advertisers by bid as shown here. 155 00:09:40,880 --> 00:09:45,180 and, you know, from top to bottom. 156 00:09:45,180 --> 00:09:47,510 So, Advertiser A, A has the highest bid. 157 00:09:47,510 --> 00:09:49,290 Advertiser B has the second highest bid, and 158 00:09:49,290 --> 00:09:51,140 Advertiser C has the third highest bid. 159 00:09:51,140 --> 00:09:54,560 So, if I'm going to show only one ad, I might as well show Advertisers A's ad, 160 00:09:54,560 --> 00:09:58,589 because adver, Advertiser A is willing to pay the most for a, per click. 161 00:09:59,650 --> 00:10:04,030 You know, if I'm going to show two ads I should just show advertiser A's and 162 00:10:04,030 --> 00:10:05,880 B's ads but not C's. 163 00:10:05,880 --> 00:10:10,215 Because A and B are both willing to pay more than C for each click. 164 00:10:11,540 --> 00:10:16,390 So this is a simple heuristic that, which are used.ah, for 165 00:10:16,390 --> 00:10:19,950 a you know, for, for, for deciding which ads to show. 166 00:10:19,950 --> 00:10:24,540 Now, it turns out that this is not the optimal, algorithm for this, for 167 00:10:24,540 --> 00:10:26,020 this scenario. 168 00:10:26,020 --> 00:10:31,180 and, the, the, the important reason is that ads behave very 169 00:10:31,180 --> 00:10:33,290 differently in terms of how they get clicked. 170 00:10:34,730 --> 00:10:35,230 So. 171 00:10:36,490 --> 00:10:39,670 What we should instead measure is something called the click through rate of 172 00:10:39,670 --> 00:10:40,690 each ad. 173 00:10:40,690 --> 00:10:44,560 Now suppose advertisers A's ads on average let's say we show, 174 00:10:44,560 --> 00:10:48,480 show all these ads many, many times and measure how often they are clicked. 175 00:10:48,480 --> 00:10:52,260 Let's say advertiser A's ads are clicked 1% of the time, 176 00:10:52,260 --> 00:10:57,340 B's ads are clicked 2% of the time and C's ads are clicked 2.5% of the time. 177 00:10:57,340 --> 00:10:58,420 All right. 178 00:10:58,420 --> 00:11:05,380 Now, if I show advertiser A's ad and it's just clicked 1% of the time. 179 00:11:05,380 --> 00:11:10,120 Then each time I show advertiser A's ad there's a 1% chance that's it's 180 00:11:10,120 --> 00:11:10,800 going to be clicked. 181 00:11:10,800 --> 00:11:16,660 And if it does get clicked I get paid $1 and so my expected revenue from showing 182 00:11:16,660 --> 00:11:23,530 advertiser's A's ad is $1 times 1%, which is a penny, right? 183 00:11:23,530 --> 00:11:26,660 And similarly, my expected revenue 184 00:11:26,660 --> 00:11:32,160 from showing advertiser's B's ad once is $0.75 times 2%. 185 00:11:32,160 --> 00:11:37,930 And, and similarly for C, my expected revenue is $0.50 times 2.5%. 186 00:11:37,930 --> 00:11:42,050 And so we can go ahead and compute the expected revenue for 187 00:11:42,050 --> 00:11:47,600 each advertiser by multiplying their bid and the CTR and in this case, 188 00:11:47,600 --> 00:11:51,960 we find out that expected revenue for Advertiser A is $0.01. 189 00:11:51,960 --> 00:11:56,220 The expected for Advertiser B is $0.015, and the expected revenue for 190 00:11:56,220 --> 00:11:58,275 Advertiser C is $0.01125. 191 00:11:59,740 --> 00:12:00,300 Right? 192 00:12:00,300 --> 00:12:04,840 Now, the important innovation that Google did, that over, you know, beyond the model 193 00:12:04,840 --> 00:12:09,860 that Overture had introduced, was to observe this, and notice that it's much 194 00:12:09,860 --> 00:12:15,040 better to sort advertisers by expected revenue than it is to sort them by bid. 195 00:12:16,580 --> 00:12:19,410 Right? So, when you sort by bid, 196 00:12:19,410 --> 00:12:22,250 you place advertiser A first,. 197 00:12:22,250 --> 00:12:26,930 Whereas when you saw by expected revenue, you observe that advertiser B 198 00:12:26,930 --> 00:12:31,580 is actually a much better advertiser, advertiser's ad to show. 199 00:12:31,580 --> 00:12:33,420 So we just had to show one ad. 200 00:12:33,420 --> 00:12:39,230 You'd much rather show advertisers B's ad because expected revenue is $0.015. 201 00:12:39,230 --> 00:12:44,580 As opposed to showing advertiser A's ad, where the expected revenue is just $0.01. 202 00:12:44,580 --> 00:12:51,560 So, so in fact if you sort by by expected revenue rather than actual bid amount 203 00:12:51,560 --> 00:12:57,360 you get a different sort order with B, C, A instead of A, B, C. 204 00:12:57,360 --> 00:13:01,790 And this is in fact the AdWords innovation that Google introduced. 205 00:13:01,790 --> 00:13:06,800 It turns out that sorting by expected revenue is a very, very good heuristic. 206 00:13:06,800 --> 00:13:10,810 And it it works well for the AdWords problem. 207 00:13:15,750 --> 00:13:18,704 Now it turns out though that there are a few more constraints in 208 00:13:18,704 --> 00:13:24,120 the AdWords problem that the, just the sorting by expected revenue doesn't solve. 209 00:13:24,120 --> 00:13:26,720 Let's look at some of those, those constraints. 210 00:13:26,720 --> 00:13:29,620 So let's, formally state, the AdWords problem. 211 00:13:29,620 --> 00:13:34,030 We are given a set of bids by advertisers for search queries. 212 00:13:34,030 --> 00:13:37,300 Now, we just looked at one search query but in general remember there are many, 213 00:13:37,300 --> 00:13:38,840 many search queries. 214 00:13:38,840 --> 00:13:42,830 and, there are many, many advertisers and each advertiser bids for 215 00:13:42,830 --> 00:13:43,980 some set of search queries. 216 00:13:43,980 --> 00:13:46,550 So, so there's a set of bids. 217 00:13:46,550 --> 00:13:48,950 By advertiser for surf, advertisers for search queries. 218 00:13:48,950 --> 00:13:53,170 You can think of this as a bipartite graph with advertisers on one side and 219 00:13:53,170 --> 00:13:54,450 search queries on the other. 220 00:13:54,450 --> 00:13:56,690 And the ranges between advertisers and search queries. 221 00:13:58,180 --> 00:14:01,550 We are also given a click-through rate for 222 00:14:01,550 --> 00:14:04,290 each advertiser-query pair that, that has been estimated. 223 00:14:07,190 --> 00:14:12,620 Now, the new thing that we haven't seen so far is that each advertiser has a budget. 224 00:14:12,620 --> 00:14:13,130 Right? 225 00:14:13,130 --> 00:14:17,060 Now, advertisers don't have infinite advertising budget. 226 00:14:17,060 --> 00:14:21,218 An advertiser might say, look, I'm willing to spend at most $1,000 a day, or 227 00:14:21,218 --> 00:14:23,920 at most maybe spend $100,000 a month. 228 00:14:23,920 --> 00:14:25,450 Or a million dollars a month. 229 00:14:25,450 --> 00:14:28,460 But there's always a limit to how much an advertiser can spend. 230 00:14:29,750 --> 00:14:32,560 Which is defined by their advertising budget. 231 00:14:32,560 --> 00:14:36,460 So each advertiser has a budget which they which they tell the search engine. 232 00:14:38,890 --> 00:14:42,010 Now the search engine also has a limit on the number of ads we display with 233 00:14:42,010 --> 00:14:43,190 each such query. 234 00:14:43,190 --> 00:14:44,230 Right? 235 00:14:44,230 --> 00:14:46,210 For example a search engine may say look, I'm going to show, 236 00:14:46,210 --> 00:14:49,790 at most, one ad for each search query, or two or three. 237 00:14:49,790 --> 00:14:52,240 Now in, some modern search engines the number ads actually, 238 00:14:52,240 --> 00:14:54,930 depends on the kind of query as well. 239 00:14:54,930 --> 00:14:59,680 But in a simple scenario, let's imagine that, there is a fixed limit 240 00:14:59,680 --> 00:15:02,120 on the number of ads to be displayed with each search query. 241 00:15:04,770 --> 00:15:05,930 Now the AdWords problem is, 242 00:15:05,930 --> 00:15:10,320 then given all these, to respond to each search query with a set of ads. 243 00:15:11,830 --> 00:15:16,150 And we have defined the set of ads so that the size of the set is no, 244 00:15:16,150 --> 00:15:18,910 no larger than the limit of the number of ads per query. 245 00:15:18,910 --> 00:15:20,130 Right? 246 00:15:20,130 --> 00:15:25,100 And we also have to make sure that we only show advertisers who actually bid for 247 00:15:25,100 --> 00:15:25,860 the search query. 248 00:15:25,860 --> 00:15:27,090 Otherwise we aren't going to get paid. 249 00:15:29,400 --> 00:15:31,282 And finally, and most critically, 250 00:15:31,282 --> 00:15:35,940 we have to make sure that not only has, have the advertiser bid on the query. 251 00:15:35,940 --> 00:15:38,340 But the advertiser has budget left over to pay for 252 00:15:38,340 --> 00:15:40,280 the ad if it is actually clicked upon. 253 00:15:40,280 --> 00:15:43,910 All right, if you show an ad from an advertiser whose budget has been 254 00:15:43,910 --> 00:15:48,940 exhausted because lots of ads have been clicked on from that advertiser then if 255 00:15:48,940 --> 00:15:52,610 somebody clicks on the ad, then the advertiser doesn't have enough budget 256 00:15:52,610 --> 00:15:56,020 left over to pay for the AdWord's click and the search engine doesn't get paid. 257 00:15:56,020 --> 00:15:58,480 So there's no point showing that advertiser's ad. 258 00:15:58,480 --> 00:16:03,900 So once a, the budget of an advertiser has been exhausted, we can, 259 00:16:03,900 --> 00:16:06,970 effectively assume that the advertiser's out of the game, 260 00:16:06,970 --> 00:16:10,770 and it's no longer bidding on, on any, any search queries. 261 00:16:13,058 --> 00:16:16,650 So the AdWords problem is, therefore, to find a set of ads for 262 00:16:16,650 --> 00:16:20,250 each search query that satisfy this this criteria. 263 00:16:20,250 --> 00:16:23,980 So here's a simple algorithm that you've seen, which is sort by expected revenue. 264 00:16:23,980 --> 00:16:25,590 Which is bid times CTR. 265 00:16:25,590 --> 00:16:29,870 And it turns out that if the CTR of each ad is known, and 266 00:16:29,870 --> 00:16:35,600 if advertisers have unlimited budgets then the simple algorithm. 267 00:16:35,600 --> 00:16:38,710 Which is to sort by expected revenue is actually optimal. 268 00:16:38,710 --> 00:16:42,580 However, advertisers don't have unlimited budgets in practice. 269 00:16:42,580 --> 00:16:45,230 And the CTR of an ad is unknown. 270 00:16:45,230 --> 00:16:48,720 And so we have to do something different. 271 00:16:48,720 --> 00:16:53,876 Let's start with problem one, which is to estimate the click through rate of an ad. 272 00:16:53,876 --> 00:16:58,303 And in the next lecture we'll look at an algorithm called balance which deals with 273 00:16:58,303 --> 00:17:01,012 the fact that advertisers have limited budgets. 274 00:17:04,357 --> 00:17:08,260 To look at the problem of estimating the click through rate of an ad. 275 00:17:08,260 --> 00:17:10,390 Now this looks like a very simple problem. 276 00:17:10,390 --> 00:17:13,020 All we have to do is to measure the clickthrough rate of 277 00:17:13,020 --> 00:17:14,523 a query-ad pair historically. 278 00:17:14,523 --> 00:17:19,510 Which has, we just have to show an ad a large number of times right? 279 00:17:19,510 --> 00:17:24,020 Let's say a thousand or 10,000 and you're to measure the number of clicks for 280 00:17:24,020 --> 00:17:29,411 that ad, query-ad pair and then we have the CTR for that query-ad query-ad pair. 281 00:17:30,620 --> 00:17:31,630 And so far so good. 282 00:17:31,630 --> 00:17:33,680 This is, in fact, the right way to do it. 283 00:17:33,680 --> 00:17:36,380 But there are a couple of challenges. 284 00:17:38,030 --> 00:17:41,100 Which we actually won't have time to cover in this lecture. 285 00:17:41,100 --> 00:17:44,790 The first is that the click through rate is actually position dependent. 286 00:17:44,790 --> 00:17:49,710 So remember a search engine may show more than one ad for a given query. 287 00:17:49,710 --> 00:17:52,730 So an ad that's shown in position one generally gets 288 00:17:52,730 --> 00:17:56,200 more clicks than an ad that's shown in position number two. 289 00:17:56,200 --> 00:17:57,390 Right? So, so 290 00:17:57,390 --> 00:18:00,650 therefore we actually have to measure the click-through rate for 291 00:18:00,650 --> 00:18:05,440 a query-ad pair for each position, not just for a query-ad pair. 292 00:18:05,440 --> 00:18:07,380 Because the click query-ad is position dependent. 293 00:18:08,390 --> 00:18:11,120 And the second problem that we have is something called ex, 294 00:18:11,120 --> 00:18:12,444 explore v exploit trade-off. 295 00:18:13,500 --> 00:18:17,140 Now, imagine that we have a lot of ads for a given query. 296 00:18:17,140 --> 00:18:20,540 And we, we show, we've shown them a lot, and we know their CTR. 297 00:18:20,540 --> 00:18:24,250 And now a new advertiser comes in, and also bids on the query. 298 00:18:26,140 --> 00:18:29,630 Now, we don't know the CTR of the new ad. 299 00:18:29,630 --> 00:18:31,659 However, ne, be, we know the CTR of the old ads. 300 00:18:33,490 --> 00:18:35,862 Now should we show the new ad at all? 301 00:18:35,862 --> 00:18:40,030 And take the risk that it doesn't get clicked on much and we lose some revenue. 302 00:18:40,030 --> 00:18:43,950 Or should we just ignore the new ad, just go with the ads that we 303 00:18:43,950 --> 00:18:47,580 already know their CTR and keep showing them to optimize revenue. 304 00:18:47,580 --> 00:18:51,890 All right, so we just exploit the known information, the known CTRs, 305 00:18:51,890 --> 00:18:54,770 the known ads or should we explore one of the new ad does, 306 00:18:54,770 --> 00:18:58,390 perhaps the new ad is really good and has a high CTR but we don't know. 307 00:18:58,390 --> 00:19:00,850 Perhaps it's actually bad and has a low CTR. 308 00:19:00,850 --> 00:19:05,730 So this problem is called explore the exploit trade-off and there's, it's, 309 00:19:05,730 --> 00:19:10,260 it's a very richly studied branch of you know, research. 310 00:19:10,260 --> 00:19:13,160 Which again we won't have time to cover in this lecture. 311 00:19:13,160 --> 00:19:16,330 We'll just assume that we know the click-through rate for 312 00:19:16,330 --> 00:19:18,810 each query-ad pair because it's been giving to us.