1 00:00:00,120 --> 00:00:04,710 So far except for a few examples, we have learned only about how to do LSH for 2 00:00:04,710 --> 00:00:07,610 declared similarity using minhashing. 3 00:00:07,610 --> 00:00:13,140 There are many other notions of similarity or distance and which one 4 00:00:13,140 --> 00:00:16,989 to use depends on what type of data we have and what our notion of similar is. 5 00:00:18,310 --> 00:00:22,410 We're going to begin by studying distance measures in general, and 6 00:00:22,410 --> 00:00:24,410 see the most useful measures. 7 00:00:24,410 --> 00:00:27,460 Then we'll talk about locality sensitive families of 8 00:00:27,460 --> 00:00:30,520 hash functions as a general idea. 9 00:00:30,520 --> 00:00:34,270 We'll see that it is possible to combine hash functions from a family, 10 00:00:34,270 --> 00:00:38,490 to get the s curve affect that we saw for LSH applied to mid-hash matrices. 11 00:00:39,980 --> 00:00:44,490 In fact, the construction is essentially the same for any LSH family. 12 00:00:44,490 --> 00:00:49,180 And we'll conclude this unit by seeing some particular LSH families, and 13 00:00:49,180 --> 00:00:53,000 how they work for the cosine distance and Euclidean distance. 14 00:00:53,000 --> 00:00:56,250 We'll begin by introducing the distance measures we need. 15 00:00:56,250 --> 00:00:58,699 And we start with the formal notion of a distance measure. 16 00:01:00,210 --> 00:01:05,370 A distance between points in some abstract space is intended to measure closeness and 17 00:01:05,370 --> 00:01:07,140 similarity to points. 18 00:01:07,140 --> 00:01:11,200 The lower the distance, the closer the points, and the more similar they are. 19 00:01:13,510 --> 00:01:17,300 Notice that jaccard similarity is the opposite of what we mean by distance. 20 00:01:17,300 --> 00:01:20,070 Jaccard similarity is higher for similar sets than for 21 00:01:20,070 --> 00:01:25,500 dissimilar sets, while a distance measure would have their distance be lower. 22 00:01:25,500 --> 00:01:30,980 It turns out that 1 minus the Jaccard similarity is a suitable distance measure. 23 00:01:30,980 --> 00:01:33,510 To start, we see two different kinds of distance measures, 24 00:01:33,510 --> 00:01:36,355 Euclidean and non-Euclidean. 25 00:01:36,355 --> 00:01:38,280 Euclidean spaces have dimensions, and 26 00:01:38,280 --> 00:01:41,960 a real number locates each point along each dimension. 27 00:01:41,960 --> 00:01:43,440 The ordinary two or 28 00:01:43,440 --> 00:01:47,160 three dimensional Euclidean spaces are the most common examples. 29 00:01:47,160 --> 00:01:51,290 But Euclidean spaces can have any number of dimensions, for example, 30 00:01:51,290 --> 00:01:56,400 a 1 dimension Euclidean space is a straight line infinite in both directions. 31 00:01:58,560 --> 00:02:02,460 An important property of Euclidean space is that they are dense. 32 00:02:02,460 --> 00:02:04,110 That is, given any two points, 33 00:02:04,110 --> 00:02:07,690 you can find their average and, and it will be a point in the space. 34 00:02:07,690 --> 00:02:10,880 We'll see some examples shortly where there is no reasonable notion 35 00:02:10,880 --> 00:02:13,380 of the average of points in the space. 36 00:02:13,380 --> 00:02:16,670 That can be a problem in certain, cer, situations. 37 00:02:16,670 --> 00:02:20,060 for, for example, if you're trying to cluster points, and 38 00:02:20,060 --> 00:02:23,560 you want to represent the cluster by a single typical point, 39 00:02:23,560 --> 00:02:27,390 it's nice to be able to take the average of the points in the cluster, but 40 00:02:27,390 --> 00:02:30,760 you can't always do that for non-Euclidean spaces. 41 00:02:30,760 --> 00:02:34,520 There are many notions of distance between points in a Euclidean space. 42 00:02:34,520 --> 00:02:40,830 The best known one is often referred to as the Euclidean distance, 43 00:02:40,830 --> 00:02:45,410 where you sum the squares of the distances between the points along each dimension. 44 00:02:45,410 --> 00:02:46,900 And then take the square root of the sum. 45 00:02:49,030 --> 00:02:51,900 However, we shall see that there are many different distance measures that 46 00:02:51,900 --> 00:02:54,740 also work for an Euclidean space. 47 00:02:54,740 --> 00:02:58,610 We shall often refer to any of these as a Euclidean distance. 48 00:03:01,400 --> 00:03:04,060 So what about other spaces and other distance measures? 49 00:03:04,060 --> 00:03:07,590 There are many of these as well, but a non-Euclidean distanced is based on 50 00:03:07,590 --> 00:03:10,060 something other than the location of points in a space. 51 00:03:11,360 --> 00:03:15,160 A distance measure is a function from pairs of points to some space, 52 00:03:15,160 --> 00:03:18,240 in some space to real numbers. 53 00:03:18,240 --> 00:03:21,480 This, this function has to satisfy four important properties. 54 00:03:23,530 --> 00:03:27,414 First, it never has a negative value although the value can be 0. 55 00:03:30,180 --> 00:03:34,510 But the value of a distance measure could be 0 under only one condition, 56 00:03:34,510 --> 00:03:38,340 that the two points to which it is applied are actually, actually the same point. 57 00:03:40,082 --> 00:03:42,874 moreover, whenever applied to the same point, 58 00:03:42,874 --> 00:03:45,335 x as both arguments, the value must be 0. 59 00:03:47,200 --> 00:03:48,399 The distance is symmetric. 60 00:03:49,750 --> 00:03:53,530 That is, the distance from x to y is the same as the distance from y to x. 61 00:03:55,180 --> 00:03:58,790 And most importantly, the function must satisfy the triangle inequality. 62 00:03:59,820 --> 00:04:03,290 That is, the distance from x to y cannot be greater than the sum of 63 00:04:03,290 --> 00:04:06,910 the distance going first from x to some other point z. 64 00:04:06,910 --> 00:04:07,560 And then from z to y. 65 00:04:07,560 --> 00:04:11,600 You often see this idea in the observation that one side of 66 00:04:11,600 --> 00:04:16,450 a triangle cannot be longer than the sum of the lengths of the other two sides. 67 00:04:16,450 --> 00:04:19,650 The most common Euclidean distance is the L2 norm, 68 00:04:19,650 --> 00:04:23,590 which is the square root of the sum of the squares of the distances between the two 69 00:04:23,590 --> 00:04:26,850 points x and y measured in each dimension. 70 00:04:30,220 --> 00:04:31,280 Another common choice for 71 00:04:31,280 --> 00:04:35,180 Euclidean distance is the L1 norm, or Manhattan distance. 72 00:04:35,180 --> 00:04:38,250 If you've ever visited Manhattan in New York 73 00:04:38,250 --> 00:04:40,900 you know that the streets are laid out in a grid. 74 00:04:40,900 --> 00:04:45,500 You can't walk directly between points, you need to first walk in one direction or 75 00:04:45,500 --> 00:04:50,230 dimension, say northsouth, and then in the other direction, say eastwest. 76 00:04:50,230 --> 00:04:53,130 As a result the L1 norm between points x and y, 77 00:04:53,130 --> 00:04:59,290 is the sum of the distances between x and y, along each the, the dimension. 78 00:04:59,290 --> 00:05:04,360 Here's an example of two points a and b in the two dimensional Euclidean space. 79 00:05:05,570 --> 00:05:10,120 A is the point (5,5) and b is (9,8). 80 00:05:10,120 --> 00:05:12,400 The difference between a and b, 81 00:05:12,400 --> 00:05:18,120 in the horizontal dimension is 4, and in the vertical direction it is 3. 82 00:05:21,200 --> 00:05:30,590 Thus the L1 norm and Manhattan distance between a and b is 4 plus 3 which is 7. 83 00:05:30,590 --> 00:05:34,370 On the other hand, the L2 norm is computed as follows. 84 00:05:34,370 --> 00:05:38,430 We take the square of the distances 4 and 3 in each dimension. 85 00:05:38,430 --> 00:05:39,580 Square them and sum them. 86 00:05:39,580 --> 00:05:44,060 It's that. 87 00:05:44,060 --> 00:05:46,120 And finally we take the square root. 88 00:05:46,120 --> 00:05:50,210 Since 4 square is 16, 3 square is 9, the sum is 25. 89 00:05:50,210 --> 00:05:53,000 The square root of that is 5. 90 00:05:53,000 --> 00:05:56,020 Here's another interesting Euclidean distance measure, 91 00:05:56,020 --> 00:05:57,450 called the L infinity norm. 92 00:05:58,450 --> 00:06:01,580 Here are the distance between two points, x and y, is the largest of 93 00:06:01,580 --> 00:06:04,890 the distance between x and y in any of the dimensions of this space. 94 00:06:06,230 --> 00:06:10,620 In fact we can define the L sub r norm for any real number r. 95 00:06:10,620 --> 00:06:14,150 You compute this norm by taking the sum of the rth 96 00:06:14,150 --> 00:06:18,420 powers of the differences of the two points along each of the dimensions. 97 00:06:18,420 --> 00:06:20,330 And then taking the rth root of the sum. 98 00:06:21,370 --> 00:06:25,150 Notice that this definition is consistent with the definitions we gave for 99 00:06:25,150 --> 00:06:27,730 r equals 1 and r equals 2 before. 100 00:06:27,730 --> 00:06:32,320 And it's also consistent with the notion of an L infinity norm, because as r 101 00:06:32,320 --> 00:06:37,060 gets larger and larger, raising numbers to the rth power causes the largest of 102 00:06:37,060 --> 00:06:41,750 them to dominate the sum, and all other rth powers become negligible. 103 00:06:41,750 --> 00:06:43,760 Then, when you take the rth root of the sum, 104 00:06:43,760 --> 00:06:47,980 you essentially are taking the rth root of the rth power of the largest, 105 00:06:47,980 --> 00:06:51,740 which gives you back essentially just the largest of differences. 106 00:06:51,740 --> 00:06:55,360 Now lets introduce the cast of characters for the non-Euclidean distances. 107 00:06:56,990 --> 00:07:02,320 First the Jaccard distance as we mentioned is just 1 minus the Jaccard similarity. 108 00:07:02,320 --> 00:07:05,540 We have to use 1 minus so identical sets have distance 0, 109 00:07:05,540 --> 00:07:08,590 and sets with no intersection have distance 1, 110 00:07:08,590 --> 00:07:11,220 which in this case is the greatest possible distance. 111 00:07:13,640 --> 00:07:16,560 And in this corner, the cosine distance. 112 00:07:16,560 --> 00:07:20,090 This distance requires points to be vectors, if the vectors have 113 00:07:20,090 --> 00:07:24,340 real numbers as components, then they are essentially points in the Euclidean space. 114 00:07:24,340 --> 00:07:25,430 But the vectors could say, 115 00:07:25,430 --> 00:07:28,880 have integer components in which case the space is not Euclidean. 116 00:07:30,750 --> 00:07:34,830 But either way, the cosine distance in between the vectors is called 117 00:07:34,830 --> 00:07:37,060 the cosine distance because as we shall see. 118 00:07:38,700 --> 00:07:42,970 It is generally easiest to compute the cosine of the angle between the vectors, 119 00:07:42,970 --> 00:07:45,340 and then use the cosine to figure out the actual angle. 120 00:07:46,670 --> 00:07:49,140 The edit distance applies to points that are character strings. 121 00:07:51,040 --> 00:07:54,510 The edit distance between two strings is the minimum number of inserts and 122 00:07:54,510 --> 00:07:57,380 deletes needed to transform one of the strings into the other. 123 00:07:57,380 --> 00:08:02,490 There are some other notions of edit distance as well. 124 00:08:02,490 --> 00:08:06,250 For example, sometimes we allow a mutation as one edit. 125 00:08:06,250 --> 00:08:12,845 Where a mutation changes one character to another for 126 00:08:12,845 --> 00:08:18,640 example abc could become adc in one edit. 127 00:08:19,700 --> 00:08:23,420 Without mutations, we would have to make two edits to make this change. 128 00:08:23,420 --> 00:08:28,600 First we would delete the old character b, and then second insert the, 129 00:08:28,600 --> 00:08:29,660 the new character d. 130 00:08:29,660 --> 00:08:34,251 So it would go a to abc to ac, and 131 00:08:34,251 --> 00:08:39,290 then finally to adc in two steps. 132 00:08:39,290 --> 00:08:42,990 By the way we're only going to talk about 133 00:08:42,990 --> 00:08:46,910 the insert delete version of edit distance in, in this course. 134 00:08:48,990 --> 00:08:51,230 Finally, consider the Hamming distance. 135 00:08:51,230 --> 00:08:52,710 It's named after Richard Hamming, 136 00:08:52,710 --> 00:08:55,810 who happens to be the third winner of the Turing award,. 137 00:08:55,810 --> 00:08:59,490 And it applies to points that are bit vectors of the same length. 138 00:08:59,490 --> 00:09:02,230 The Hamming distance between two bit vectors is the number of 139 00:09:02,230 --> 00:09:03,840 positions in which they differ. 140 00:09:06,370 --> 00:09:08,170 Here's an example of Jaccard distance. 141 00:09:09,710 --> 00:09:12,430 Consider these two sets, x and y. 142 00:09:14,550 --> 00:09:17,397 Their intersection has two members, 1 and 3. 143 00:09:20,670 --> 00:09:24,467 And the union has five numbers members the numbers one 144 00:09:24,467 --> 00:09:28,860 through five thus the Jaccard similarity is, is two fifths. 145 00:09:28,860 --> 00:09:33,245 But we don't want Jaccard similarity anymore, now we want Jaccard distance. 146 00:09:33,245 --> 00:09:40,250 That's 1 minus the two-fifths giving us a Jaccard distance of three-fifths. 147 00:09:40,250 --> 00:09:44,120 So let's check the four conditions for a di, a distance measure. 148 00:09:44,120 --> 00:09:46,300 Jaccard distance is never less than 0, 149 00:09:46,300 --> 00:09:49,040 because the Jaccard similarity can't be greater than 1. 150 00:09:49,040 --> 00:09:52,440 The reason for that, is the size of the intersection of 151 00:09:52,440 --> 00:09:55,289 two sets is never greater than the, the size of their union. 152 00:09:57,280 --> 00:10:01,280 Now the distance between a set x and itself is 0. 153 00:10:01,280 --> 00:10:01,840 Why? 154 00:10:01,840 --> 00:10:06,530 Well, x intersect x is the same as x union x, and both are x itself. 155 00:10:06,530 --> 00:10:10,060 So the Jaccard similarity of the set with itself is 1. 156 00:10:10,060 --> 00:10:12,860 Therefore the Jaccard distance is 1 minus 1 is 0. 157 00:10:14,490 --> 00:10:17,480 We also have to check that if x is not equal to y, 158 00:10:17,480 --> 00:10:20,640 then their Jaccard distance is strictly greater than 0. 159 00:10:20,640 --> 00:10:23,410 That is because if x and y are different, then there is at 160 00:10:23,410 --> 00:10:27,090 least one element in their union that's not in their intersection, and 161 00:10:27,090 --> 00:10:30,500 therefore their intersection is strictly smaller than their union. 162 00:10:30,500 --> 00:10:33,340 That means that Jaccard similarity is strictly less than 1, 163 00:10:33,340 --> 00:10:36,440 and that Jaccard distance is strictly greater than 0. 164 00:10:36,440 --> 00:10:40,740 The symmetry condition follows from the fact that the union and 165 00:10:40,740 --> 00:10:42,088 intersection are both symmetric. 166 00:10:42,088 --> 00:10:45,451 That is, x intersect y, equals y intersect x, so 167 00:10:45,451 --> 00:10:48,903 both intersects should surely have the same size. 168 00:10:48,903 --> 00:10:50,920 And, likewise for the unions. 169 00:10:52,370 --> 00:10:54,740 The last thing to prove is the triangle inequality. 170 00:10:56,500 --> 00:10:59,550 That's a bit of work, but we'll show the proof on the next slide. 171 00:11:00,720 --> 00:11:04,480 Here's the inequality that says the Jaccard distance from x to z, 172 00:11:05,610 --> 00:11:09,120 plus the Jaccard distance from z to y is equal to or 173 00:11:09,120 --> 00:11:11,838 greater than the Jaccard distance from x to y. 174 00:11:11,838 --> 00:11:19,480 That is, this is the Jaccard similarity of x and z. 175 00:11:19,480 --> 00:11:23,560 The size of their intersection divided by the size of their union. 176 00:11:23,560 --> 00:11:26,960 So this is the Jaccard distance from x to z. 177 00:11:28,470 --> 00:11:35,254 And similarly this is the Jaccard distance 178 00:11:35,254 --> 00:11:42,200 from y to z, and this is the car distance from x to y. 179 00:11:43,610 --> 00:11:47,190 Remember, we proved that the jaccard similarity between sets a and 180 00:11:47,190 --> 00:11:53,509 b, is the probability that the minhash values of a and b are the same. 181 00:11:55,040 --> 00:11:56,040 Or put another way. 182 00:11:57,270 --> 00:12:05,270 This is the probability that the minhash of a and b are different. 183 00:12:05,270 --> 00:12:08,950 But the probability that minhash of x and y differ, 184 00:12:08,950 --> 00:12:13,050 cannot be greater than the probability that the minhash of x and z differ. 185 00:12:13,050 --> 00:12:16,880 Plus the probability that minhash of y and z differ. 186 00:12:16,880 --> 00:12:18,980 By what we saw on the previous slide, 187 00:12:18,980 --> 00:12:21,880 this claim is equivalent to the triangle inequality. 188 00:12:23,390 --> 00:12:26,730 But the reason is that whenever minhash of x and 189 00:12:26,730 --> 00:12:32,220 y are different, it is impossible for both minhash of x to equal minhash of z. 190 00:12:32,220 --> 00:12:37,950 And for minhash of z to equal minhash of y, because then by transitivity of equals, 191 00:12:37,950 --> 00:12:40,350 minhash of x would be equal to minhash of y. 192 00:12:42,680 --> 00:12:46,370 So, in terms of Venn diagrams, let the plane represent triples of sets x, 193 00:12:46,370 --> 00:12:47,900 y, and z. 194 00:12:47,900 --> 00:12:51,270 Here, those triples where minhash values of x and z differ. 195 00:12:54,000 --> 00:12:57,490 And here are the triples where minhashes of y and z differ. 196 00:12:57,490 --> 00:13:01,350 And contained within their union, must be the set of triples where x and 197 00:13:01,350 --> 00:13:02,950 y have different minhash values. 198 00:13:04,210 --> 00:13:07,420 Another important distance measure is the cosine distance. 199 00:13:07,420 --> 00:13:11,704 Okay, this distance is useful for data that is in the form of a vector. 200 00:13:11,704 --> 00:13:14,614 Often the vector is in very high dimensions. 201 00:13:14,614 --> 00:13:18,110 For example documents are often viewed as the vector of 202 00:13:18,110 --> 00:13:23,437 counts of each of the words appearing in the document, so each word is a dimension. 203 00:13:23,437 --> 00:13:26,657 Now to define the cosine distance think of a data point as 204 00:13:26,657 --> 00:13:30,440 a vector from the origin in some space, to the point in question. 205 00:13:32,250 --> 00:13:36,720 Any two points have an angle from that their origin between their vectors. 206 00:13:36,720 --> 00:13:39,330 So we have something like this. 207 00:13:41,490 --> 00:13:46,080 We can compute the cosine of this angle from the components of the two vectors. 208 00:13:46,080 --> 00:13:49,520 To do so, we take the dot product of the vectors. 209 00:13:51,600 --> 00:13:55,550 The dot product is the sum of the products of the corresponding components. 210 00:13:55,550 --> 00:13:57,650 And then we divide by the lengths of the two vectors. 211 00:13:57,650 --> 00:14:03,610 The length of a vector from the origin is actually the normal Euclidian distance, 212 00:14:03,610 --> 00:14:08,660 what we call the L2 norm, of the point at the head of the vector to the origin. 213 00:14:08,660 --> 00:14:11,420 That is it is the square root of the sum of the squares, 214 00:14:11,420 --> 00:14:12,740 of the component of the vector. 215 00:14:14,230 --> 00:14:17,680 For example, here are two vectors, P1 and P2. 216 00:14:17,680 --> 00:14:23,120 The docked product of the vectors is two. 217 00:14:24,230 --> 00:14:28,710 The products of each of the first three components is 0. 218 00:14:28,710 --> 00:14:35,710 That is 0 times 1 is 0, 0 times 0 is 0, 1 times 0 is also a 0. 219 00:14:35,710 --> 00:14:41,730 But in the last two components each vector is 1 do the dot-product of 220 00:14:41,730 --> 00:14:45,780 the sum of 1 times 1 plus 1 times 1 and the's 2. 221 00:14:45,780 --> 00:14:47,590 For the lengths of the vector. 222 00:14:47,590 --> 00:14:53,250 P1 has three 1s, so we sum three 1s squared, and then take the square root, 223 00:14:53,250 --> 00:14:54,775 giving us the square root of 3. 224 00:14:56,990 --> 00:14:59,742 P2 also has three 1s and two 0s as components, so 225 00:14:59,742 --> 00:15:01,920 its length is the same square root of 3. 226 00:15:03,500 --> 00:15:07,200 Thus the cosine of the angle between P1 and P2 is two. 227 00:15:07,200 --> 00:15:11,850 The dot-product, that is divided by the product of the two vector lanes. 228 00:15:11,850 --> 00:15:14,610 Each of those lengths is the square root of 3, so that product is 3, and 229 00:15:14,610 --> 00:15:16,510 the cosine of the angle is two-thirds. 230 00:15:16,510 --> 00:15:19,980 If you look that up in a table of cosine you'll find that 231 00:15:19,980 --> 00:15:23,580 this angle is about 48 degrees. 232 00:15:23,580 --> 00:15:25,610 So here's a diagram with the two vectors, 233 00:15:25,610 --> 00:15:29,070 P1 to P2 shown on the plane that passes through them. 234 00:15:29,070 --> 00:15:33,620 No matter how many dimensions the vectors have, any two lines that intersect, and 235 00:15:33,620 --> 00:15:37,078 and P1 and P2 do intersect at the origin, they'll follow a plane. 236 00:15:37,078 --> 00:15:42,290 I'm not going to do the math, but if you project P1 onto P2 as we have done here, 237 00:15:42,290 --> 00:15:48,360 the length of the projection is the dot product, divided by the length of P2. 238 00:15:48,360 --> 00:15:53,850 Then the cosine of the angle between them is the ratio of adjacent over hypotenuse. 239 00:15:53,850 --> 00:16:00,800 Which is the dot product divided by P2, that's the adjacent. 240 00:16:02,060 --> 00:16:05,910 And then divided by the length of P1, that's of course the hypotenuse. 241 00:16:07,170 --> 00:16:11,910 Let's see why the cosine distance satisfies the axioms of the distance. 242 00:16:11,910 --> 00:16:16,130 First, remember that vectors here are really directions, not magnitudes. 243 00:16:16,130 --> 00:16:18,050 So two vectors with the same direction and 244 00:16:18,050 --> 00:16:21,030 different magnitudes are really the same vector. 245 00:16:21,030 --> 00:16:21,730 Even to vector and 246 00:16:21,730 --> 00:16:24,990 its negation, the reverse of the vector, ought to be thought of as the same vector. 247 00:16:27,220 --> 00:16:30,700 first, the distance between a vector and itself is 0. 248 00:16:30,700 --> 00:16:34,362 The angle a vector makes with itself is 0 degrees. 249 00:16:34,362 --> 00:16:39,274 moreover, the angle of a vector with any different vector is not 0 degrees. 250 00:16:39,274 --> 00:16:43,260 So, no pair of different vectors have a distance of 0. 251 00:16:43,260 --> 00:16:46,440 Again, remember we think of vectors as direction only, 252 00:16:46,440 --> 00:16:48,560 otherwise you could have say a vector and 253 00:16:48,560 --> 00:16:53,410 twice that vector being quote different, and yet having a 0 angle between them. 254 00:16:55,630 --> 00:16:58,050 To make sure that all distances are non-negative, 255 00:16:58,050 --> 00:17:03,460 we shall interpret all angles as in the range 0 to 100 and 180 degrees. 256 00:17:03,460 --> 00:17:07,430 Notice that any two vectors from the origin will make angle between 0 and 257 00:17:07,430 --> 00:17:09,940 180 degrees in the plane they define. 258 00:17:11,530 --> 00:17:14,060 The rest of the argument is by physical reasoning. 259 00:17:14,060 --> 00:17:18,650 Symmetry simply says that the angle of a vector to x rotating to y, 260 00:17:18,650 --> 00:17:22,760 is the same as the angle from y rotating to x. 261 00:17:22,760 --> 00:17:26,990 And the triangle inequality is merely the observation that if we rotate from x to z, 262 00:17:26,990 --> 00:17:29,530 and then from z to y, 263 00:17:29,530 --> 00:17:35,230 the total rotation can't be less than what we get if we rotate from x to y directly. 264 00:17:35,230 --> 00:17:36,540 Now consider the edit distance. 265 00:17:37,830 --> 00:17:41,170 Recall this distance measure assumes point or character strings, and 266 00:17:41,170 --> 00:17:44,680 the edit distance from x to y, is the minimum number of inserts and 267 00:17:44,680 --> 00:17:46,960 deletes needed to turn x into y. 268 00:17:49,100 --> 00:17:51,790 There is an equivalent formula for edit distance based on 269 00:17:51,790 --> 00:17:55,420 the notion of the longest common subsequence of two strings x and y. 270 00:17:57,280 --> 00:18:01,800 The LCS of x and y is the longest string that is a subsequence of both. 271 00:18:02,800 --> 00:18:06,360 We say one string is a sub-sequence of another if we can get the first by 272 00:18:06,360 --> 00:18:10,270 deleting 0 or more positions from the second. 273 00:18:10,270 --> 00:18:14,400 Note that the positions of the deleted characters did not have to be consecutive. 274 00:18:14,400 --> 00:18:17,450 We'll give an example on the next slide to make these ideas clear. 275 00:18:18,740 --> 00:18:24,030 The formula for the edit distance in terms of the LCS 276 00:18:25,570 --> 00:18:30,250 is this, it's the sum of the lengths of the two strings. 277 00:18:30,250 --> 00:18:36,170 Length of x, length of y minus twice the length of the LCS. 278 00:18:37,310 --> 00:18:41,040 Here's an example where we'll compute the edit distance of these two strings x and 279 00:18:41,040 --> 00:18:42,190 y in two different ways. 280 00:18:43,340 --> 00:18:51,800 First, we can turn x into y by deleting a, 281 00:18:51,800 --> 00:18:58,240 and then inserting u and v, after the d, that uses three edits, 282 00:18:58,240 --> 00:19:02,920 and it's easy to check that there's no way to get from x to y using fewer edits. 283 00:19:02,920 --> 00:19:04,500 Thus the edit distance is three. 284 00:19:06,110 --> 00:19:14,070 Notice that we can get from y to x by doing the same edits in reverse. 285 00:19:14,070 --> 00:19:22,140 That is, we delete u and v, and then we insert a to get x. 286 00:19:22,140 --> 00:19:26,120 In general repair, strings can have several different LCSs of the same length. 287 00:19:27,640 --> 00:19:29,480 In this case, there's only one, BCDE. 288 00:19:29,480 --> 00:19:35,970 It is obtained from x by deleting the first position and obtaining a. 289 00:19:37,010 --> 00:19:39,450 And it is obtained from y by deleting the fourth and 290 00:19:39,450 --> 00:19:42,500 fifth positions containing u and v. 291 00:19:45,480 --> 00:19:49,530 And to verify that the formula relating edit distance to the LCS holds in 292 00:19:49,530 --> 00:19:54,680 this case, the sum of the lengths of the two strings is 5 plus 6 or 11. 293 00:19:54,680 --> 00:19:57,090 And the LCS has a length of 4. 294 00:19:57,090 --> 00:20:01,520 But 11 minus twice 4 is 3, which is indeed the edit distance. 295 00:20:01,520 --> 00:20:04,740 We can check the edit distance also satisfies the requirements to 296 00:20:04,740 --> 00:20:06,940 be considered a distance measure. 297 00:20:06,940 --> 00:20:11,120 First of all, the edit distance from the string x to itself is surely 0 because 0 298 00:20:11,120 --> 00:20:11,990 edits suffice. 299 00:20:13,410 --> 00:20:17,590 Moreover, if x and y are different, at least one edit is required to change one 300 00:20:17,590 --> 00:20:20,920 to the other so that no distances, no other distances, are 0. 301 00:20:20,920 --> 00:20:24,850 And there's no way for there to be a negative number of edits, 302 00:20:24,850 --> 00:20:26,830 so surely there are no negative edit distances. 303 00:20:29,060 --> 00:20:33,720 Symmetry holds because given any sequence of inserts and deletes, say taking string 304 00:20:33,720 --> 00:20:38,170 x to string y, we can reverse that sequence, and replace the deletion of 305 00:20:38,170 --> 00:20:44,430 a character C, by the insertion of C and replace the insertion of C by a deletion. 306 00:20:44,430 --> 00:20:47,310 We saw an example of this transformation on the previous slide. 307 00:20:48,880 --> 00:20:52,270 And the triangle inequality holds for the following reason. 308 00:20:52,270 --> 00:20:56,890 One way to transform x to y, is first to transform x to z and then z to y. 309 00:20:58,200 --> 00:21:01,390 The minimum number of edits needed to make those transformations is 310 00:21:01,390 --> 00:21:04,690 the sum of the edit distances from x to z and from z to y. 311 00:21:05,830 --> 00:21:10,530 But this sequence of edits is one of the possible ways to transform x to y, so 312 00:21:10,530 --> 00:21:14,240 the total number of edits is at least the edit distance from x to y. 313 00:21:14,240 --> 00:21:16,520 And next on our list is the Hamming Distance. 314 00:21:16,520 --> 00:21:19,250 And recall the Hamming distance is the number of positions in 315 00:21:19,250 --> 00:21:22,040 which two bit-vectors of the same length differ. 316 00:21:22,040 --> 00:21:27,173 So for example the Hamming distance between P1 and 317 00:21:27,173 --> 00:21:33,510 P2, is 2 because they differ in the 3rd and 4th positions. 318 00:21:35,270 --> 00:21:35,890 Here there's 1 0. 319 00:21:35,890 --> 00:21:38,210 There there's 0 1. 320 00:21:38,210 --> 00:21:40,990 Other than that they're, they are the same. 321 00:21:40,990 --> 00:21:44,370 The argument about why Hamming distance is also a distance measure quite 322 00:21:44,370 --> 00:21:49,690 the same as before, the Hamming distance between a string and it's self is 0. 323 00:21:49,690 --> 00:21:54,220 Because surely the string differs in 0 positions. 324 00:21:54,220 --> 00:21:57,770 On the other hand Hamming distance between different strains cannot be 0, 325 00:21:57,770 --> 00:21:59,970 because they differ in at least one position. 326 00:22:01,790 --> 00:22:04,570 There can't be a negative Hamming distance because you can't talk about 327 00:22:04,570 --> 00:22:07,050 strings differing in a negative number of positions. 328 00:22:08,210 --> 00:22:11,820 Symmetry of Hamming distance follow from notion that the relationship different 329 00:22:11,820 --> 00:22:13,970 from on bits is symmetric. 330 00:22:13,970 --> 00:22:17,010 That is a is different from b, if and only if b is different from a. 331 00:22:18,210 --> 00:22:22,430 And the triangle in the equality argument is very much like what we saw for, for 332 00:22:22,430 --> 00:22:22,960 edit distance. 333 00:22:24,080 --> 00:22:27,310 One way to change bit string x to y by flipping bits, 334 00:22:27,310 --> 00:22:32,340 is to first to flip bits to turn x to z, and then flip bits to turn z to y. 335 00:22:32,340 --> 00:22:36,307 The sum of these two numbers of flips cannot be less than the number of 336 00:22:36,307 --> 00:22:38,892 bits you have to flip to turn x to y directly.