1 00:00:03,560 --> 00:00:06,820 We’ve see when use of locality sensitive hashing, where the underlying 2 00:00:06,820 --> 00:00:11,630 data is a collection of sets and similarity means Jaccard similarity. 3 00:00:11,630 --> 00:00:14,910 But there are other approaches that share the same goal of focusing our search on 4 00:00:14,910 --> 00:00:17,460 the pairs that are likely to be similar. 5 00:00:17,460 --> 00:00:20,300 We’re now going to see some of these variations. 6 00:00:20,300 --> 00:00:22,120 Later, we'll examine general techniques and 7 00:00:22,120 --> 00:00:24,840 definitions of similarity other than Jaccard similarity. 8 00:00:24,840 --> 00:00:29,340 And we'll see that LSH is really an approach to problems rather than, 9 00:00:29,340 --> 00:00:31,670 than a particular algorithm. 10 00:00:31,670 --> 00:00:36,290 Our first example of using LSH concerns a problem called entity resolution. 11 00:00:36,290 --> 00:00:39,620 In this kind of problem, we're given a collection of records. 12 00:00:39,620 --> 00:00:42,930 Each record provides some information about an entity 13 00:00:42,930 --> 00:00:44,560 typically entities are people but 14 00:00:44,560 --> 00:00:48,330 they could be companies, physical locations, events or any number of things. 15 00:00:49,370 --> 00:00:52,270 The entity resolution problem is to determine which sets of 16 00:00:52,270 --> 00:00:54,710 records refer to the same person and 17 00:00:54,710 --> 00:00:58,290 to merge these records into one record that tells everything about that entity. 18 00:00:59,810 --> 00:01:02,770 The problem is way more complicated than it looks. 19 00:01:02,770 --> 00:01:06,440 for, for example, it is typical that records about people include the name of 20 00:01:06,440 --> 00:01:09,290 the person, so it looks like it should be no problem at all 21 00:01:09,290 --> 00:01:12,900 to group them into sets that represent the same individual. 22 00:01:12,900 --> 00:01:16,190 But in a large collection of records, there will be people with the same name, 23 00:01:17,240 --> 00:01:21,390 so grouping by name will merge records for different people and worse, the same 24 00:01:21,390 --> 00:01:25,550 person may have their name written in different ways in different records. 25 00:01:25,550 --> 00:01:29,410 Some records will have their middle initials and others not. 26 00:01:29,410 --> 00:01:32,270 A person's nickname may appear in one place and 27 00:01:32,270 --> 00:01:34,550 their formal name in another, like Sue and Susan. 28 00:01:35,950 --> 00:01:39,700 And, of course misspellings occur which makes names look different even if they 29 00:01:39,700 --> 00:01:41,040 are intended to be identical. 30 00:01:42,100 --> 00:01:43,740 And we often can compensate for 31 00:01:43,740 --> 00:01:47,770 these discrepancies by using other information in the records. 32 00:01:47,770 --> 00:01:51,730 For example, two records may have similar names, but identical phone numbers or 33 00:01:51,730 --> 00:01:53,510 identical addresses. 34 00:01:53,510 --> 00:01:57,150 That's when the problem becomes really interesting. 35 00:01:57,150 --> 00:02:02,100 I'm going to tell you a real story of how I use LSH to get a big consulting fee. 36 00:02:03,530 --> 00:02:07,270 After I retired from Stanford I took a job consulting for some lawyers. 37 00:02:09,080 --> 00:02:12,770 They were dealing with a lawsuit involving two companies that I will call A and B. 38 00:02:13,790 --> 00:02:15,560 Okay. Company B had a service and 39 00:02:15,560 --> 00:02:20,060 Company A agreed to use its customer base to find customers for Company B. 40 00:02:22,570 --> 00:02:26,290 But the companies took to squabbling and the deal was eventually cancelled. 41 00:02:27,450 --> 00:02:32,400 Since B was serving many of the customers that A had sent them, A was owed fees for 42 00:02:32,400 --> 00:02:34,720 these customers and sued to get those fees. 43 00:02:36,940 --> 00:02:40,870 Unfortunately, neither company had bothered to modify their records to 44 00:02:40,870 --> 00:02:43,940 indicate whether a customer had been part of this deal. 45 00:02:43,940 --> 00:02:48,250 They could have created a record, we sent this guy to B, and B could have 46 00:02:48,250 --> 00:02:53,210 added a bit to their record saying, this guy came from A but neither did. 47 00:02:53,210 --> 00:02:56,870 So they had to pay me to figure out how many customers appeared in 48 00:02:56,870 --> 00:02:58,349 the databases of both companies. 49 00:03:00,030 --> 00:03:04,120 To set the scale of the problem each company had about a million records that 50 00:03:04,120 --> 00:03:07,610 might represent the customer that A had provided to B. 51 00:03:07,610 --> 00:03:11,110 That's a tiny database by todays standards, but 52 00:03:11,110 --> 00:03:15,010 notice that there are a trillion pairs of records, one from A and one from B, 53 00:03:15,010 --> 00:03:17,630 that might be the same person. 54 00:03:17,630 --> 00:03:22,060 It is way too expensive to examine and evaluate a trillion pairs of records. 55 00:03:24,380 --> 00:03:27,290 Each record from either company, had a name, address, and 56 00:03:27,290 --> 00:03:30,570 phone number but often these were different, even for the same person. 57 00:03:32,030 --> 00:03:34,820 in, in addition to typos and the sorts of variation in 58 00:03:34,820 --> 00:03:39,060 name we discussed earlier there were many other sources of difference. 59 00:03:39,060 --> 00:03:42,670 People would move and tell one company their new address but not the other. 60 00:03:44,080 --> 00:03:47,160 Area codes would change even though the rest of your phone number remained 61 00:03:47,160 --> 00:03:48,660 the same. 62 00:03:48,660 --> 00:03:51,700 People would get married and change their name. 63 00:03:51,700 --> 00:03:54,750 In all these cases one company might track the change and the other not. 64 00:03:57,080 --> 00:03:59,200 So our, our first step wa, 65 00:03:59,200 --> 00:04:03,060 wa, was to devise a measure of how similar records were. 66 00:04:03,060 --> 00:04:05,840 We gave 100 points each for identical names, addresses, and 67 00:04:05,840 --> 00:04:08,148 phone numbers, so 300 was the top score. 68 00:04:08,148 --> 00:04:13,470 Interestingly only 7,000 pairs of records received this top score, although 69 00:04:13,470 --> 00:04:18,500 we identified over 180 thousand pairs that were very likely the same person. 70 00:04:21,160 --> 00:04:24,510 Then we penalize differences in these three fields. 71 00:04:24,510 --> 00:04:26,280 Completely different names addresses or 72 00:04:26,280 --> 00:04:30,400 phones got zero score but small changes gave scores close to 100. 73 00:04:30,400 --> 00:04:33,380 For example if the last names were the same but 74 00:04:33,380 --> 00:04:36,119 there was a small spelling difference in the first names. 75 00:04:37,508 --> 00:04:38,463 like, like this. 76 00:04:43,559 --> 00:04:46,330 Then the score for the name would be 90. 77 00:04:46,330 --> 00:04:47,910 If the last names were the same but 78 00:04:47,910 --> 00:04:52,440 the first name's completely different the score for the names would be 50. 79 00:04:52,440 --> 00:04:55,440 We scored all candidate pairs of records and 80 00:04:55,440 --> 00:04:58,879 reported those pairs that were above a certain threshold as matches. 81 00:05:00,040 --> 00:05:03,810 One of the subtle points is how we set the threshold without knowing ground truth. 82 00:05:03,810 --> 00:05:08,840 That is, which pairs of records really were created by the same individuals. 83 00:05:08,840 --> 00:05:12,150 Notice that this is not a job you can do with machine learning, because there's no 84 00:05:12,150 --> 00:05:16,600 training set available and, we'll, we'll talk about how we did this soon. 85 00:05:18,560 --> 00:05:23,220 'Kay so as I mentioned we can't afford to score all trillion pairs of records. 86 00:05:24,290 --> 00:05:29,310 Okay, so I devised a really simple form of locality sensitive hashing to 87 00:05:29,310 --> 00:05:31,050 focus on the likely matches. 88 00:05:32,230 --> 00:05:35,320 Here we used exactly three hash functions. 89 00:05:35,320 --> 00:05:37,480 One had a bucket for each possible name. 90 00:05:37,480 --> 00:05:40,760 The second had a bucket for each possible address. 91 00:05:40,760 --> 00:05:43,200 And the third had a bucket for each possible phone number. 92 00:05:45,620 --> 00:05:50,440 Now, the candidate pairs were those placed in the same bucket by 93 00:05:50,440 --> 00:05:52,580 at least one of these hash functions. 94 00:05:52,580 --> 00:05:55,310 That is a pair of records was a candidate pair if and 95 00:05:55,310 --> 00:05:58,430 only if they agreed exactly in at least one of the three fields. 96 00:06:00,240 --> 00:06:02,306 Did we lose some pairs? 97 00:06:02,306 --> 00:06:03,520 Surely we did. 98 00:06:03,520 --> 00:06:06,900 Because there would be some pairs of records that had small differences in 99 00:06:06,900 --> 00:06:11,370 each of the three fields and these would never become candidates for scoring. 100 00:06:11,370 --> 00:06:13,610 We actually did a hand sampling of records and 101 00:06:13,610 --> 00:06:19,540 estimate that there were, about 2,500 pairs of records that we missed. 102 00:06:19,540 --> 00:06:23,430 But that's not bad compared with 180,000 that we found. 103 00:06:23,430 --> 00:06:26,810 And finding those extra 2,500 would probably have cost more than 104 00:06:26,810 --> 00:06:28,950 they were worth to either company. 105 00:06:32,120 --> 00:06:35,590 You may have been puzzled by my remark that we hash to one bucket for each 106 00:06:35,590 --> 00:06:41,020 possible name since there are in principle an infinite number of possible names. 107 00:06:41,020 --> 00:06:45,620 But we didn't really hash to buckets, rather we sorted the records by name 108 00:06:47,700 --> 00:06:49,739 and then the records with identical names. 109 00:06:51,710 --> 00:06:56,050 Appear consecutively in the list and we can score each pair with identical names. 110 00:06:57,200 --> 00:06:59,730 After that we resorted by address and 111 00:06:59,730 --> 00:07:02,970 did the same thing with records that had identical addresses. 112 00:07:02,970 --> 00:07:07,470 And then finally we repeated the process by sorting, by, by phone number. 113 00:07:09,330 --> 00:07:12,030 We should, we should observe that another approach was to 114 00:07:12,030 --> 00:07:16,930 follow the strategy we used when we did LSH for signatures we could hash to 115 00:07:16,930 --> 00:07:22,990 say several million buckets and compare all pairs of records within one bucket. 116 00:07:22,990 --> 00:07:26,890 That would sometimes cause us to look at pairs of records with different names that 117 00:07:26,890 --> 00:07:30,050 happened to hash to the same bucket but if the number of buckets is 118 00:07:30,050 --> 00:07:34,070 much larger than the number of different names that actually appeared in the data 119 00:07:34,070 --> 00:07:38,260 then the probability of collisions like this is very low. 120 00:07:38,260 --> 00:07:41,540 Now remember that we scored each candidate pair of records but 121 00:07:41,540 --> 00:07:46,290 suppose a pair gets a score like 200 out of 300 indicating a good deal of 122 00:07:46,290 --> 00:07:48,320 similarity but not perfect similarity. 123 00:07:49,610 --> 00:07:51,850 Do these records represent the same person? 124 00:07:53,050 --> 00:07:56,010 Well turns out a score of 200 made it very likely that 125 00:07:56,010 --> 00:07:58,340 the records represented the same person. 126 00:07:58,340 --> 00:07:59,680 But how could we tell for sure? 127 00:08:00,930 --> 00:08:04,570 We devised a way to calculate the probability that records 128 00:08:04,570 --> 00:08:07,150 with a score x represented the same person. 129 00:08:07,150 --> 00:08:09,890 And it's worth telling about because it can be used in 130 00:08:09,890 --> 00:08:11,760 other circumstances as well. 131 00:08:11,760 --> 00:08:15,370 Even though the data we used was very specific to the, the problem at hand. 132 00:08:18,460 --> 00:08:20,717 First, remember that there's a gold standard. 133 00:08:20,717 --> 00:08:25,050 7,000 pairs of identical records that we could assume represented the same person. 134 00:08:26,800 --> 00:08:32,530 For these pairs, we looked at the creation dates at companies A and B. 135 00:08:32,530 --> 00:08:37,220 It turns out that there was a 10 day lag on average between the time the record was 136 00:08:37,220 --> 00:08:42,410 created by company A and the time that the same person went to company B to be, 137 00:08:42,410 --> 00:08:44,190 to begin their service. 138 00:08:44,190 --> 00:08:48,100 On the other hand, in order to reduce further the pairs of records we needed to 139 00:08:48,100 --> 00:08:52,540 score we only looked at pairs of records where the A record was created between, 140 00:08:52,540 --> 00:08:55,090 between zero and 90 days before the B record. 141 00:08:55,090 --> 00:08:59,062 Now if you take a random A record and a random B record, 142 00:08:59,062 --> 00:09:02,040 when the A record happens to have been created between zero and 143 00:09:02,040 --> 00:09:05,910 90 days before the B record, you'll get an average delay of 45 days. 144 00:09:07,180 --> 00:09:10,500 These records are almost certain to represent different people because they 145 00:09:10,500 --> 00:09:11,590 were chosen at random. 146 00:09:14,140 --> 00:09:17,910 So let's look at a pool of matches, say those with score 200. 147 00:09:17,910 --> 00:09:20,180 Some will be valid matches and 148 00:09:20,180 --> 00:09:22,455 their average difference in creation dates will be ten. 149 00:09:23,580 --> 00:09:25,290 Others will be false matches and 150 00:09:25,290 --> 00:09:28,734 they will have an average difference in creation dates of 45. 151 00:09:29,870 --> 00:09:33,760 Suppose that within this pool, the average difference is X. 152 00:09:33,760 --> 00:09:37,720 A little math tells you that the fraction of matches that 153 00:09:37,720 --> 00:09:42,870 are valid are 45 minus X, all divided by 35. 154 00:09:42,870 --> 00:09:47,640 So for example, if X equals ten then this fraction is one, which makes sense as 155 00:09:47,640 --> 00:09:51,800 a ten is the difference that the gold standard provides. 156 00:09:51,800 --> 00:09:58,310 If x equals 20 then we would expect that five-sevenths of the matches are valid. 157 00:09:58,310 --> 00:10:02,896 That makes sense five-sevenths of the matches will have an average difference of 158 00:10:02,896 --> 00:10:07,300 ten and two-sevenths of them will have an average difference of 45. 159 00:10:07,300 --> 00:10:12,050 So the weighted average of the averages is, is 20. 160 00:10:12,050 --> 00:10:16,960 So we tried to convince the lawyers that they should go into court with a claim of 161 00:10:16,960 --> 00:10:21,500 a fraction of each of the pools that had average delays less than 45. 162 00:10:21,500 --> 00:10:25,070 Even though we couldn't tell which pairs in each pool were valid and 163 00:10:25,070 --> 00:10:26,510 which were not. 164 00:10:26,510 --> 00:10:29,710 But the lawyers told us not to even try because no judge or 165 00:10:29,710 --> 00:10:33,830 jury would understand the argument, but you understand it, don't you? 166 00:10:35,450 --> 00:10:39,800 Well, while we use the creation date field in records, the idea generalizes to 167 00:10:39,800 --> 00:10:43,820 use any field that was not involved in the locality-sensitive hashing. 168 00:10:43,820 --> 00:10:47,290 All we need to know is that the value in this field will be closer when 169 00:10:47,290 --> 00:10:51,990 the records represent the same entity than when they represent different entities. 170 00:10:51,990 --> 00:10:53,800 That should be the case almost always. 171 00:10:55,370 --> 00:10:59,110 okay, for a concrete example, suppose records represent individuals and 172 00:10:59,110 --> 00:11:00,890 they have a height field. 173 00:11:00,890 --> 00:11:03,970 We can assume that if the records represent the same person 174 00:11:03,970 --> 00:11:08,200 the average difference in heights will be zero or, or perhaps more precisely, 175 00:11:08,200 --> 00:11:11,520 the difference will be the average measurement error which we can determine 176 00:11:11,520 --> 00:11:15,630 if we have some gold standard of records that we know represent the same person. 177 00:11:16,960 --> 00:11:20,090 This difference substitutes for the difference ten days in our example. 178 00:11:21,920 --> 00:11:24,600 But if two records represent different people then 179 00:11:24,600 --> 00:11:28,520 the average height difference will be the average difference for random people. 180 00:11:28,520 --> 00:11:31,590 We can determine this difference by picking a relatively small number of 181 00:11:31,590 --> 00:11:33,580 pairs of records at random and 182 00:11:33,580 --> 00:11:36,440 determining the difference in heights of those two records. 183 00:11:36,440 --> 00:11:39,260 This difference plays the role of 45 in our example.