1 00:00:00,780 --> 00:00:04,710 We shall now take up the essence of what locality and sensitive hashing is 2 00:00:04,710 --> 00:00:08,450 all about, by defining an abstract notion of an LSH families of hash functions. 3 00:00:10,200 --> 00:00:14,810 Using this abstract definition we show how to build new families out of old families, 4 00:00:14,810 --> 00:00:19,480 in such a way that the new family has a steeper S-curve than the original family. 5 00:00:19,480 --> 00:00:23,980 The construction we use are quite analogous to the way we 6 00:00:23,980 --> 00:00:29,100 work with minhash functions, which are an example of an LSH family, and 7 00:00:29,100 --> 00:00:34,570 use the combination into bands to steepen the S-curve. 8 00:00:34,570 --> 00:00:38,360 Before proceeding we need to explain something about what a hash function in 9 00:00:38,360 --> 00:00:40,314 the sense of an LSH family really is. 10 00:00:42,910 --> 00:00:47,090 Technically a hash function h in this sense takes two arguments x and 11 00:00:47,090 --> 00:00:50,730 y, which are elements of similarity or distance we are interested in, 12 00:00:50,730 --> 00:00:54,550 and the hash function returns a decision about this pair. 13 00:00:54,550 --> 00:00:59,290 Yes means that they are a candidate pair and we need to calculate their similarity. 14 00:00:59,290 --> 00:01:01,010 We can think of yes as saying x and 15 00:01:01,010 --> 00:01:04,900 y belong to the same bucket, when hash function h is used. 16 00:01:05,920 --> 00:01:07,690 But the answer no means that x and 17 00:01:07,690 --> 00:01:10,410 y is not a candidate pair according to this hash function. 18 00:01:12,180 --> 00:01:16,250 For example, a minhash function can be viewed as taking two sets x and y. 19 00:01:16,250 --> 00:01:19,640 Computing the minhash values according to some per 20 00:01:19,640 --> 00:01:23,340 permutation associated with that has function. 21 00:01:23,340 --> 00:01:26,260 And saying yes, if and only if the minhash values are the same. 22 00:01:27,260 --> 00:01:31,220 In many cases, there will be a calculation of values behind the scenes, and 23 00:01:31,220 --> 00:01:34,240 the yes answers are made when the values are the same. 24 00:01:34,240 --> 00:01:37,190 However, the view we are taking now is more general, 25 00:01:37,190 --> 00:01:41,570 since there need not be a computation of values that are then compared. 26 00:01:41,570 --> 00:01:44,980 And as we shall see, we really need this generality. 27 00:01:44,980 --> 00:01:48,886 For example, we should look at LSH families that render their decisions, 28 00:01:48,886 --> 00:01:52,858 by looking at many values and saying yes, if there is at least one equality. 29 00:01:55,231 --> 00:01:59,638 However, to make things look more normal, we shall often use 30 00:01:59,638 --> 00:02:05,220 the expression h(x) equals h(y), to mean that h of x and y is yes. 31 00:02:05,220 --> 00:02:08,089 Okay, so here's the definition of an LSH family of hash function. 32 00:02:09,660 --> 00:02:14,480 First these families of hash functions, each assume that it consists of a space of 33 00:02:14,480 --> 00:02:17,450 points with a distance measure for that space. 34 00:02:17,450 --> 00:02:20,830 For example, the family of minhash functions assumes the space of 35 00:02:20,830 --> 00:02:23,930 points as sets, and the distance is the Jaccard distance. 36 00:02:26,460 --> 00:02:30,480 There is no notion of a family of hash functions being sensitive in 37 00:02:30,480 --> 00:02:35,410 some absolute sense,uh, but rather we can make statements about a family H of 38 00:02:35,410 --> 00:02:38,970 hash functions, in terms of four parameters. 39 00:02:39,970 --> 00:02:42,610 There are two distances, d1 and d2. 40 00:02:44,800 --> 00:02:48,639 And there are two probabilities, p1 and p2. 41 00:02:51,776 --> 00:02:55,609 Of the two distance, one is a small distance that's d1. 42 00:02:55,609 --> 00:02:58,579 And the other is a large distance. 43 00:02:58,579 --> 00:03:03,816 The probability p1 is associated with the small distance, and it is a lower bound on 44 00:03:03,816 --> 00:03:08,630 the probability of agreement, for points at distance d1 or less. 45 00:03:08,630 --> 00:03:13,840 The second probability, p2, is associated with a large distance, and 46 00:03:13,840 --> 00:03:17,080 it is an upper-bound, on the probability of agreement for 47 00:03:17,080 --> 00:03:18,650 points at distance d2 or more. 48 00:03:18,650 --> 00:03:23,271 We expect p1 to be large and p2 to be small. 49 00:03:26,242 --> 00:03:31,477 'Kay, more formally, for any two points x and y at distance up to d1, 50 00:03:31,477 --> 00:03:35,934 the probability considering all hash functions little h and 51 00:03:35,934 --> 00:03:41,290 the family capital H, that little h says yes about x and y is at least p1. 52 00:03:43,690 --> 00:03:46,240 And if the distance between x and y is at least d2, 53 00:03:46,240 --> 00:03:52,470 then the probability that the little h says yes for x and y, is at most p2. 54 00:03:52,470 --> 00:03:58,221 Here's a picture of what we know about the probability of h(x) equaling h(y). 55 00:03:59,950 --> 00:04:05,050 For distances d1 and below, we know the probability is at least p1. 56 00:04:05,050 --> 00:04:08,640 And for distance is d2 and above, we know the probability is at most p2. 57 00:04:09,900 --> 00:04:10,919 Between d1 and 58 00:04:10,919 --> 00:04:16,323 d2 we know nothing however we shall try to make the difference between d1 and 59 00:04:16,323 --> 00:04:21,037 d2 very small, and the distance between p1 and p2 as large as we can. 60 00:04:21,037 --> 00:04:24,121 'Kay,that will give us the S-curve we want, although, 61 00:04:24,121 --> 00:04:28,562 since we're now talking about distances rather than similarities, the S-curve is 62 00:04:28,562 --> 00:04:32,385 backwards, it drops down precipitously, between the distances d1 and 63 00:04:32,385 --> 00:04:36,230 d2, rather than rising precipitously so it looks something like this. 64 00:04:39,290 --> 00:04:41,760 Let's take as our example the only example we know, 65 00:04:41,760 --> 00:04:46,850 the underlying space consists of sets, all sub-sets of some universal set. 66 00:04:46,850 --> 00:04:48,980 And the distance measure is Jaccard distance. 67 00:04:50,170 --> 00:04:54,180 The LSH family is the family of minhash functions, each based on one 68 00:04:54,180 --> 00:04:58,019 of the possible permutations of the members of the universal set of elements. 69 00:05:00,180 --> 00:05:03,600 We claim the probability that a given minhash function h gives the same 70 00:05:03,600 --> 00:05:09,290 value for sets x and y, is 1 minus the Jaccard distance from x to y. 71 00:05:09,290 --> 00:05:13,380 That's just a restatement of the theorem, about how the Jaccard similarity is 72 00:05:13,380 --> 00:05:17,988 the probability that two sets agree in a random minhash function. 73 00:05:17,988 --> 00:05:20,910 Notice that 1 minus the Jaccard distance is the Jaccard similarity. 74 00:05:24,140 --> 00:05:27,272 We claim that the family of minhash functions is a one-third, 75 00:05:27,272 --> 00:05:30,340 two-thirds, two-thirds, one-third sensitive family, for 76 00:05:30,340 --> 00:05:33,750 the space S of sets and the Jaccard distance d. 77 00:05:36,150 --> 00:05:39,560 For example the first and third parameters say that if the distance is at 78 00:05:39,560 --> 00:05:44,770 most one-third, than the probability of agreement is at least two-thirds. 79 00:05:44,770 --> 00:05:47,640 But that makes sense, because if the distance is at 80 00:05:47,640 --> 00:05:53,380 most one-third than the Jaccard similarity is at least two-thirds. 81 00:05:53,380 --> 00:05:56,650 And we know that the probability of agreement equals the similarity. 82 00:05:56,650 --> 00:05:57,150 Okay? 83 00:05:58,300 --> 00:06:02,220 Likewise, the second and fourth parameters say that whenever the Jaccard distance is 84 00:06:02,220 --> 00:06:05,220 at least two-thirds, that the similarities is at most one-third. 85 00:06:05,220 --> 00:06:08,165 The probability of agreement is at most one-third. 86 00:06:11,570 --> 00:06:16,150 We can make many statements like this about the family of minhash functions. 87 00:06:16,150 --> 00:06:18,590 There's nothing special about one-third or two-thirds. 88 00:06:18,590 --> 00:06:24,490 In fact, any distances d1 and d2, as long as d1 is less than d2, the minhash 89 00:06:24,490 --> 00:06:30,200 functions form a family with sensitivity, d1, d2, 1 minus d1, 1 minus d2. 90 00:06:34,470 --> 00:06:38,900 When we start with a simple LSH-family such as the set of minhash functions, 91 00:06:38,900 --> 00:06:40,330 we don't get the S-curve effect. 92 00:06:41,530 --> 00:06:45,230 However, we're going to see that it is possible to amplify the steepness of 93 00:06:45,230 --> 00:06:46,550 the S-curve. 94 00:06:46,550 --> 00:06:51,450 Using two constructions that produce a new LSH family from a given LSH family. 95 00:06:51,450 --> 00:06:54,240 These constructions are like, are like what we've already seen for 96 00:06:54,240 --> 00:06:55,327 the minhash functions. 97 00:06:56,590 --> 00:06:59,560 In particular what we call the AND construction, 98 00:06:59,560 --> 00:07:02,830 is essentially the combination of the effect of several rows in one band. 99 00:07:04,360 --> 00:07:07,050 And the OR construction is the combination of several bands. 100 00:07:08,410 --> 00:07:10,208 So here is the AND construction. 101 00:07:13,267 --> 00:07:19,230 We're given an LSH family H and we want to construct from it a new family H prime, 102 00:07:19,230 --> 00:07:24,046 each hash function from H prime, is built from R functions from H. 103 00:07:26,682 --> 00:07:30,171 A hash function little h in the family h prime, 104 00:07:30,171 --> 00:07:36,090 is constructed from a set of r hash functions from family h, so h1 through hr. 105 00:07:37,520 --> 00:07:40,850 Little h renders its decision about a pair of elements x and 106 00:07:40,850 --> 00:07:45,500 y by checking that each hash function in the set, renders the decision yes. 107 00:07:47,480 --> 00:07:52,290 Using our convention that h(x) equals h(y) means that the answer for x and 108 00:07:52,290 --> 00:07:57,040 y is yes, we can write the rule for H as shown. 109 00:07:59,110 --> 00:08:03,893 That is h(x) equals h(y) if, and only if, 110 00:08:03,893 --> 00:08:10,650 hi(x) equals hi(y) for all i, where i ranges now from 1 to r. 111 00:08:15,510 --> 00:08:20,860 The family H prime amplifies the effect of H, according to the rule given here. 112 00:08:20,860 --> 00:08:24,460 The lower and upper distance d1 and d2 don't change. 113 00:08:24,460 --> 00:08:28,430 However, the two probabilities are each raised to the rth power. 114 00:08:28,430 --> 00:08:31,340 That is, in order to get a yes from hash function H, 115 00:08:31,340 --> 00:08:34,580 we have to get yes from each of the Hi's. 116 00:08:34,580 --> 00:08:39,181 The family H prime consists of all possible sets of r members of family H, so 117 00:08:39,181 --> 00:08:44,059 the Hi's for a given H can be viewed as randomly chosen and thus independent. 118 00:08:45,080 --> 00:08:48,410 Remember that the rule for the probability of independent events occurring 119 00:08:48,410 --> 00:08:53,490 simultaneously, is the product of the probabilities of the individual events. 120 00:08:54,670 --> 00:08:57,700 The AND construction corresponds to combining roles in the band. 121 00:08:59,600 --> 00:09:02,605 We also have an OR construction that corresponds to combining bands. 122 00:09:03,990 --> 00:09:06,440 Again, we'll start with an LSH family H and 123 00:09:06,440 --> 00:09:08,760 constru, and construct a new family H prime. 124 00:09:10,620 --> 00:09:15,425 Each member of H prime will be constructed from a set of b functions for H. 125 00:09:15,425 --> 00:09:20,594 That little h be a typical member of the family H prime, and that x and 126 00:09:20,594 --> 00:09:24,237 y be elements to which we want to apply little h. 127 00:09:24,237 --> 00:09:30,376 And we say h(x) equals h(y) if and only if hi(x) equals hi(y) for 128 00:09:30,376 --> 00:09:34,380 at least one value of i and the range of one to b. 129 00:09:37,481 --> 00:09:43,157 Notice that the expression h(x) equals h(y) really is shorthand for the way H 130 00:09:43,157 --> 00:09:49,430 looks at both x and y and decides whether, or not to make them a candidate pair. 131 00:09:49,430 --> 00:09:54,013 We cannot explain what is going on by supposing that H computes a value from x 132 00:09:54,013 --> 00:09:57,303 and a value from y, and simply asks if they are equal. 133 00:10:00,801 --> 00:10:02,370 So here's the rule, for 134 00:10:02,370 --> 00:10:07,310 the sensitivity of family H prime in terms of the sensitivity of H. 135 00:10:07,310 --> 00:10:11,750 As for the And Construction, the distance components d1 and d2 do not change. 136 00:10:12,960 --> 00:10:15,340 But the probabilities are altered according to the rule, for 137 00:10:15,340 --> 00:10:17,940 the probability of the or of independent events. 138 00:10:19,600 --> 00:10:23,670 To see how this combination works, think of at least one of these events 139 00:10:23,670 --> 00:10:28,150 occurs in its equivalent form, it is not true that none of these events occurs. 140 00:10:29,350 --> 00:10:33,318 If each event occurs with probability of p1, 141 00:10:33,318 --> 00:10:38,112 then the probability it doesn't occur is 1 minus p1. 142 00:10:38,112 --> 00:10:42,554 The probability that none of b events occurs is that, raised to the bth power. 143 00:10:47,022 --> 00:10:54,710 And 1 minus that, is the probability that none of them occur it's false. 144 00:10:54,710 --> 00:10:58,000 That is, at least one of the b events occurs. 145 00:10:58,000 --> 00:11:00,900 The same transformation applies to the other, 146 00:11:00,900 --> 00:11:03,400 the other probability p2, of course. 147 00:11:04,520 --> 00:11:08,400 So here’s a summary of what happens when we apply the AND and OR constructions. 148 00:11:12,100 --> 00:11:15,620 AND makes both the high and low probabilities shrink, because we’re 149 00:11:15,620 --> 00:11:20,910 taking two probabilities which are less than 1 and raising them to the rth power. 150 00:11:22,560 --> 00:11:24,710 What we need to do is pick r big enough, so 151 00:11:24,710 --> 00:11:27,500 that the low probability becomes close to 0. 152 00:11:27,500 --> 00:11:31,660 Yet pick r small enough, that the high probability stays significantly above 0. 153 00:11:31,660 --> 00:11:36,020 It's a balancing act, but we'll see in a moment, how it works in practice. 154 00:11:37,790 --> 00:11:41,130 The analogous story implies to the OR construction. 155 00:11:41,130 --> 00:11:45,360 Both probabilities grow, but we contrive the selective value of b 156 00:11:45,360 --> 00:11:47,870 that makes the high probably get very close to one, 157 00:11:47,870 --> 00:11:51,910 while still keeping the low probability significantly away from one. 158 00:11:55,660 --> 00:11:59,280 Now we need to see how to compose the AND and OR constructions in order to 159 00:11:59,280 --> 00:12:04,290 wind up with an LSH family where the low probability is essentially 0, and the high 160 00:12:04,290 --> 00:12:09,540 probability is essentially one, that's the ideal for the S-curve, remember. 161 00:12:09,540 --> 00:12:13,730 In the case of signature matrices and the AND construction, we did the AND 162 00:12:13,730 --> 00:12:17,700 construction, combining rows in the band, followed by the OR 163 00:12:17,700 --> 00:12:19,790 construction combining bands. 164 00:12:19,790 --> 00:12:22,600 But we could have actually done these in the reverse order. 165 00:12:22,600 --> 00:12:26,200 And it is also possible to use a sequence of more than two of the AND and OR 166 00:12:26,200 --> 00:12:29,980 constructions alternating, and we'll see how to do, how that works in a moment. 167 00:12:33,170 --> 00:12:37,790 Suppose we do the r way AND construction followed by the b way OR construction. 168 00:12:39,560 --> 00:12:44,030 The AND construction turns a probability p, into p to the r. 169 00:12:47,580 --> 00:12:51,369 Then, the OR construction turns p to the r into this function. 170 00:12:53,950 --> 00:12:58,949 Notice that what we have is exactly the S, S-curve that we constructed when we 171 00:12:58,949 --> 00:13:02,224 originally discussed LSH and minhash functions. 172 00:13:06,322 --> 00:13:10,197 We're going to do an example on the next slide, where r and b are both 4. 173 00:13:10,197 --> 00:13:12,737 That is, starting with some LSH family H, 174 00:13:12,737 --> 00:13:16,210 we do a four-way AND construction to get a family H prime. 175 00:13:17,880 --> 00:13:21,760 And then use H prime to do a four-way, OR 176 00:13:21,760 --> 00:13:24,090 construction to get a new family H double prime. 177 00:13:26,920 --> 00:13:29,550 So here's a table of what happens to the probability p, 178 00:13:29,550 --> 00:13:32,280 when you apply the four-way AND followed by the four-way OR. 179 00:13:32,280 --> 00:13:38,170 We could could pick the lower and upper distances d1 and d2 as we like. 180 00:13:41,270 --> 00:13:47,404 For example, here's what happens, if we choose the lower distance d1 to be 0.2. 181 00:13:47,404 --> 00:13:50,794 And the upper distance d2 to be 0.8, and 182 00:13:50,794 --> 00:13:55,013 the underlining LSH family is the midhash functions. 183 00:13:55,013 --> 00:14:00,218 We start with a 0.2, 0.8, 0.8, 0.2 family. 184 00:14:00,218 --> 00:14:08,084 The constructed family has the same distances, 0.2 and 0.8. 185 00:14:08,084 --> 00:14:12,233 But if you substitute p equals 0.8 in this formula. 186 00:14:15,198 --> 00:14:17,526 Well, you get this. 187 00:14:17,526 --> 00:14:23,402 You get 0.8785, so, the upper probability is raised that's good. 188 00:14:23,402 --> 00:14:32,707 And if you substitute p equals 0.2, in the same formula, you get 0.0064. 189 00:14:32,707 --> 00:14:35,830 So the lower probability is lowered, that's also good. 190 00:14:37,420 --> 00:14:39,791 We also have the option of starting with a b way, OR 191 00:14:39,791 --> 00:14:42,520 construction and then doing an r way AND construction. 192 00:14:42,520 --> 00:14:49,250 The OR construction turns any probability p, into this expression. 193 00:14:49,250 --> 00:14:50,034 And then the AND 194 00:14:50,034 --> 00:14:54,262 construction raises those probabilities to the rth power, giving this formula. 195 00:14:59,400 --> 00:15:03,589 The S-curve you get from this sequence of constructions is related to what you get, 196 00:15:03,589 --> 00:15:06,800 if you start with the r way AND and then do the b way OR. 197 00:15:06,800 --> 00:15:09,640 Starting with that curve, you'd mirror it vertically and 198 00:15:09,640 --> 00:15:13,970 then mirror it horizontally, or mirror it first horizontally, then vertically it, 199 00:15:13,970 --> 00:15:15,330 it doesn't matter. 200 00:15:15,330 --> 00:15:18,910 The result will be the curve for this expression. 201 00:15:21,190 --> 00:15:24,032 We'll again do an example on the next slide, it is a four-way OR 202 00:15:24,032 --> 00:15:25,360 followed by a four-way AND. 203 00:15:27,460 --> 00:15:29,874 So here's the table for 204 00:15:29,874 --> 00:15:36,420 the OR-AND construction each using four from the previous LSH family. 205 00:15:39,900 --> 00:15:43,396 Let's see what you get when you start with the minhash functions, 206 00:15:43,396 --> 00:15:47,970 thought of as a (0.2, 0.8, 0.8, 0.2) sensitive family. 207 00:15:47,970 --> 00:15:52,569 Looking up the values for probabilities 0.8 and 0.2 in the table, you see you get 208 00:15:52,569 --> 00:15:56,794 a much higher probability for the low the low distance pairs that's this. 209 00:16:02,641 --> 00:16:07,259 And you also get a somewhat lower probability, for the distant pairs. 210 00:16:08,370 --> 00:16:10,160 And so again, both have been improved. 211 00:16:11,720 --> 00:16:15,110 We are free to apply construction after construction. 212 00:16:15,110 --> 00:16:18,340 And if we pick the right values of r and b, we'll keep improving both 213 00:16:18,340 --> 00:16:21,930 probabilities, driving the low one toward zero and the high one toward one. 214 00:16:23,240 --> 00:16:25,380 For example, we could apply the OR 215 00:16:25,380 --> 00:16:28,200 followed by AND construction we just discussed. 216 00:16:28,200 --> 00:16:31,890 And then apply the AND followed by OR construction, discussed earlier. 217 00:16:31,890 --> 00:16:35,890 That by the way would be the same as applying a four-way OR then a 16-way, 218 00:16:35,890 --> 00:16:37,854 AND and Finally another four-way OR. 219 00:16:40,230 --> 00:16:44,110 Notice that each construction uses 16 of the original functions. 220 00:16:44,110 --> 00:16:50,256 So by cascading these two constructions, we use 256 minhash functions. 221 00:16:50,256 --> 00:16:55,395 If you do the math, you'll find that it transforms the minhash functions, 222 00:16:55,395 --> 00:17:01,034 thought of as a 0.2, 0.8, 0.8, 0.2, a sensitive family into this. 223 00:17:04,038 --> 00:17:10,053 The probability of saying yes for sets at Jaccard distance 0.2 or 224 00:17:10,053 --> 00:17:14,100 less is this, which is almost precisely 1. 225 00:17:14,100 --> 00:17:17,400 That is there are very, very few false negatives. 226 00:17:17,400 --> 00:17:21,467 But the probability of saying yes for sets of Jaccard distance 0.8 or 227 00:17:21,467 --> 00:17:23,790 more, is this very small probability. 228 00:17:25,934 --> 00:17:29,362 thus, at least among pairs that are really far apart, 229 00:17:29,362 --> 00:17:32,086 the number of false positives is tiny. 230 00:17:32,086 --> 00:17:34,806 You might look at this analysis and observe that we 231 00:17:34,806 --> 00:17:39,731 don't know anything about what happens between the similarities between 0.2 and 232 00:17:39,731 --> 00:17:41,500 0.8 and that's a big range. 233 00:17:43,610 --> 00:17:45,900 However, suppose our application is shingled web documents. 234 00:17:47,170 --> 00:17:48,906 If we take two random web pages and 235 00:17:48,906 --> 00:17:52,770 we have used a large enough shingle length, say nine or 10. 236 00:17:52,770 --> 00:17:56,120 The two random documents will have very small Jaccard similarity. 237 00:17:57,240 --> 00:17:59,970 And this is Jaccard distance above 0.8. 238 00:17:59,970 --> 00:18:04,140 Only if there is some special cause for similarity, say a mirror page or 239 00:18:04,140 --> 00:18:07,450 plagiarism, will the Jaccard distance be low. 240 00:18:07,450 --> 00:18:11,460 In those cases we expect it to be very low, probably under 0.2. 241 00:18:11,460 --> 00:18:15,704 That is to say there simply aren't many pairs, at distance between 0.2 and 242 00:18:15,704 --> 00:18:16,890 0.8 in this application. 243 00:18:18,490 --> 00:18:20,737 The conclusion is that for the particular, 244 00:18:20,737 --> 00:18:25,810 this particular application, we might be happy with distances 0.2 and 0.8. 245 00:18:25,810 --> 00:18:28,910 But we are free to make the distances be whatever we want, 246 00:18:28,910 --> 00:18:31,420 as long as the first is less than the second. 247 00:18:31,420 --> 00:18:38,038 For example, we could start with a 0.49, 0.51, 248 00:18:38,038 --> 00:18:43,320 0.51, 0.49 sensitive family. 249 00:18:43,320 --> 00:18:49,349 And do constructions that would drive the probabilities initially 0.51 and 250 00:18:49,349 --> 00:18:52,790 0.49, close to one and zero respectively. 251 00:18:53,870 --> 00:18:58,010 course, of course we would need many more than 256 of the base functions to 252 00:18:58,010 --> 00:19:00,087 get such a steep S-curve. 253 00:19:01,570 --> 00:19:05,980 What I'd like to do now is explain how to select the values of r and b, for AND and 254 00:19:05,980 --> 00:19:06,600 OR constructions. 255 00:19:08,910 --> 00:19:16,570 Let's look at the function that we've called the S-curve, that's this. 256 00:19:18,380 --> 00:19:24,304 This is a function of the probability p, and it has two parameters r and b. 257 00:19:24,304 --> 00:19:27,013 An interesting observation is that this curve. 258 00:19:29,382 --> 00:19:30,047 Okay, let's. 259 00:19:34,453 --> 00:19:38,781 Draw something like that here it has a fixed point t, 260 00:19:38,781 --> 00:19:45,310 such that if p equals t then the result of applying the function to t is t itself. 261 00:19:45,310 --> 00:19:50,627 To see the t exists, look at where the curve intersects the line with slope 1. 262 00:19:52,838 --> 00:19:54,630 So that would be the value of t. 263 00:19:56,320 --> 00:20:01,550 Above probability t, applying the S-curve function increases the probability, 264 00:20:01,550 --> 00:20:03,799 while below t, the probability decreases. 265 00:20:05,430 --> 00:20:10,240 We can conclude that as long the two probabilities are on opposite sides of t, 266 00:20:10,240 --> 00:20:14,660 the construction where you do an r way and followed by a b way OR, 267 00:20:14,660 --> 00:20:17,690 will move both probabilities, in the direction we want them to go. 268 00:20:18,800 --> 00:20:22,130 We can then iterate this construction as many times as we like, and 269 00:20:22,130 --> 00:20:23,950 both probabilities will keep improving. 270 00:20:25,340 --> 00:20:28,730 There is an analogous observation about a construction where we do an, OR 271 00:20:28,730 --> 00:20:29,390 followed by an AND. 272 00:20:30,396 --> 00:20:34,230 The S-curve formula is a little different, but the ideas are quite the same. 273 00:20:38,140 --> 00:20:40,200 Here is a picture suggesting what happens for 274 00:20:40,200 --> 00:20:44,356 the S-curves that we get for both the AND and OR, or OR-AND constructions. 275 00:20:45,930 --> 00:20:49,038 The threshold is defined by the place where the S-curve, and 276 00:20:49,038 --> 00:20:50,363 the straight line cross. 277 00:20:53,331 --> 00:20:55,738 'Kay, for probabilities p below t, 278 00:20:55,738 --> 00:20:59,433 applying the S-curve function lowers the probability. 279 00:21:04,471 --> 00:21:10,752 While for probabilities above t, the S-curve sends p to a higher probability.