1 00:00:01,220 --> 00:00:06,812 One very important variance of Markov networks that is probably at this point 2 00:00:06,812 --> 00:00:12,762 more commonly used than other kinds than anything that's not this type is called a 3 00:00:12,762 --> 00:00:18,355 conditional random field. So conditional random field you can think of it as a 4 00:00:18,355 --> 00:00:23,517 something that looks very much like a Markov network but for a somewhat 5 00:00:23,517 --> 00:00:29,467 different purpose. So let's think about what you're trying to do here. This class 6 00:00:29,467 --> 00:00:35,319 of model is intended to deal with what we call task specific prediction. That is, 7 00:00:35,319 --> 00:00:42,932 where we have a set of input variables. Or observed variables, X. And we have a set 8 00:00:42,932 --> 00:00:51,337 of target variables. That we're trying to predict Y. And the classic model is 9 00:00:51,337 --> 00:00:58,134 intended to, is designed for those cases where we always have the same types of 10 00:00:58,134 --> 00:01:03,238 variables as the input variables and the same types of variables as the targets. 11 00:01:03,238 --> 00:01:08,533 And we're always trying to solve what is essentially the exact same problem. Or the 12 00:01:08,533 --> 00:01:13,510 exact same type of problem. So let's think about that as, let's think about two 13 00:01:13,510 --> 00:01:18,742 examples along these lines. So now going back to the example of image segmentation, 14 00:01:18,933 --> 00:01:25,477 here we have the input is always a set of pixels. With their values, pixel values, 15 00:01:25,477 --> 00:01:31,552 which we can process to produce more expressive features, like histograms of 16 00:01:31,552 --> 00:01:38,105 colors and textures but this is sort of not relevant at this point, but it will be 17 00:01:38,105 --> 00:01:48,392 in a minute. So my input X is pixel values and a processed features [inaudible] And 18 00:01:48,392 --> 00:01:57,788 my target variable's Y is a class. For every pixel. So for example, where by 19 00:01:57,788 --> 00:02:05,480 class I mean, you know, grass, sky, cow, water, and so on. And we're always trying 20 00:02:05,480 --> 00:02:13,475 to, we design the model so as to solve this problem of going from X to Y. And we 21 00:02:13,475 --> 00:02:21,572 want to solve that problem. In some of the text processing and NLT problems that 22 00:02:21,572 --> 00:02:31,664 we've discussed, the, the pixel, the input X are the words in a sentence. And the 23 00:02:31,664 --> 00:02:39,347 output that we're trying to derive is, for example, the labels. Of the words, where 24 00:02:39,347 --> 00:02:47,631 again, the labels might be in this case things like person, location, organization 25 00:02:47,631 --> 00:02:55,916 and so on. And once again, this is always their input, the words and the output is 26 00:02:55,916 --> 00:03:03,663 always the labels. So Why, what is the problem? So fine, so we want to solve 27 00:03:03,663 --> 00:03:09,526 this, this kind of a prediction problem. Why not use just a regular old graphical 28 00:03:09,526 --> 00:03:15,035 model in the same way we've done so far. So let's think about what some of the 29 00:03:15,035 --> 00:03:21,110 issues might be with that. So imagine that we are trying to predict, in this case CI, 30 00:03:21,110 --> 00:03:26,328 which is the label of a particular super-pixel in this case, I. And we're 31 00:03:26,328 --> 00:03:33,454 going to go ahead and process our features of that super pixel to provide a range of 32 00:03:33,454 --> 00:03:40,580 different color and texture histograms that represent different ways of measuring 33 00:03:40,580 --> 00:03:47,035 the appearance of the super pixel. So, in this case that's my Y, just as in the 34 00:03:47,035 --> 00:03:53,658 location of previous slide, this is my target Y and these guys down here are my 35 00:03:53,658 --> 00:04:00,229 Xs. So what's the problem with this? The problem with this is that these features 36 00:04:00,229 --> 00:04:06,723 that are often much more informative about, about these about the classes of 37 00:04:06,723 --> 00:04:13,217 pixel are very correlated with each other. So, for example, the, the texture 38 00:04:13,217 --> 00:04:19,053 histograms which tell us sort of the directions in which lines go in a 39 00:04:19,053 --> 00:04:24,889 particular super pixel, they're very redundant in terms of the kinds of 40 00:04:24,889 --> 00:04:31,776 structure, the kinds of textures that they measure. And so if you have features here 41 00:04:31,776 --> 00:04:37,827 that are very correlated with each other, so where two variables or two features 42 00:04:37,827 --> 00:04:44,105 have a lot of redundant information. If we represent this in a [inaudible] model, as 43 00:04:44,105 --> 00:04:57,848 I drew here, where the features are independent. Given the label. Then, I'm 44 00:04:57,848 --> 00:05:03,422 effectively ignoring that correlation structure. Now why is that bad? It's bad 45 00:05:03,422 --> 00:05:08,180 because it allows me to count the same feature again and again and again and 46 00:05:08,180 --> 00:05:12,444 again and again. So it's I have five copies of a feature or five very 47 00:05:12,444 --> 00:05:16,770 correlated, related features that effectively measure the same thing. I 48 00:05:16,770 --> 00:05:21,405 count it five times which means I get really confident because of this one 49 00:05:21,405 --> 00:05:27,359 feature. If I have a hundred copies of that feature I count that a hundred times 50 00:05:27,359 --> 00:05:33,426 so it, and again it pushes me towards very skewed probability distributions that 51 00:05:33,426 --> 00:05:39,977 don't really, that are not really good reflections of, of my true beliefs because 52 00:05:39,977 --> 00:05:46,035 they make incorrect independence assumptions. Well, fine, so let's make 53 00:05:46,035 --> 00:05:55,757 correct, independent assumptions. Let's add a bunch of edges To capture the 54 00:05:55,757 --> 00:06:03,344 correlations. Well, that turns out to be really hard, because once you start doing 55 00:06:03,344 --> 00:06:08,913 things that are not trivial features, figuring out how they're correlated, and 56 00:06:08,913 --> 00:06:14,621 furthermore even trying to put in these correlations gives rise to ... So first of 57 00:06:14,621 --> 00:06:22,496 all this is hard to figure out. And it gives rise to densely connected models. If 58 00:06:22,496 --> 00:06:31,187 I start putting in all these edges between these features. So a completely different 59 00:06:31,187 --> 00:06:37,034 solution to this problem, basically says, well, I don't care about the image 60 00:06:37,034 --> 00:06:42,812 features. I don't want to predict the probability distributions over pixels. I 61 00:06:42,812 --> 00:06:47,532 want, I don't care to predict, you know I'm not trying to do image synthesis. I 62 00:06:47,532 --> 00:06:52,130 don't care about the probability of having, you know, green pixel next to 63 00:06:52,130 --> 00:06:57,218 another green pixel next to a brown pixel. I'm trying to use a [inaudible] given to 64 00:06:57,218 --> 00:07:02,122 me, something that is already given which is the features X and the only thing I 65 00:07:02,122 --> 00:07:06,719 really care about is to model the distribution over Y. So I've reformulated 66 00:07:06,719 --> 00:07:14,920 my problem, instead of modeling. The joined distribution of X and Y together. 67 00:07:18,100 --> 00:07:25,917 So instead of doing this, I'm going to model a conditional distribution of Y 68 00:07:25,917 --> 00:07:36,269 given X. Where I'm not trying to capture the distribution over X. Now if I'm not 69 00:07:36,269 --> 00:07:41,453 trying to capture the distribution over X, then I don't really care about the 70 00:07:41,453 --> 00:07:46,771 correlations between them, and we'll see that a little bit more clearly when we 71 00:07:46,771 --> 00:07:51,753 look at an example in a little bit. But before we do that, let's first give 72 00:07:51,753 --> 00:07:57,071 ourselves the formal definition of this thing which is called a, a CRF which 73 00:07:57,071 --> 00:08:08,729 stands for Conditional Random. Field. And a conditional random field at first glance 74 00:08:08,729 --> 00:08:17,108 looks just like a Gibbs distribution. So just like a Gibbs Distribution, we have a 75 00:08:17,108 --> 00:08:29,333 set of factors. Each with their scope. And just like the [inaudible] distribution I 76 00:08:29,333 --> 00:08:45,290 multiply The factors I get an unnormalized measure. And In order, and now, so far 77 00:08:45,290 --> 00:08:50,316 it's exactly the same except that I have an X and Y on, in the, as the arguments of 78 00:08:50,316 --> 00:08:55,342 a normalized measure rather than just a set of random variables. This is where the 79 00:08:55,342 --> 00:09:00,429 difference comes in, if I want to model a conditional distribution of Y given X, I'm 80 00:09:00,429 --> 00:09:05,454 going to have to put X on the right-hand side of the conditioning bar, which means 81 00:09:05,454 --> 00:09:10,541 I'm going to have a separate normalization constant, a partition function, that is a 82 00:09:10,541 --> 00:09:20,067 function of X. [inaudible] and so what does that mean? It means that for any 83 00:09:20,067 --> 00:09:28,529 given X, I sum over Y The change that's for any given X I'm going to have the sum 84 00:09:28,529 --> 00:09:34,748 of all the Y's that correspond to that X, and then I'm going to construct the 85 00:09:34,748 --> 00:09:42,395 conditional distribution by normalizing by I'm going to start a visual distribution 86 00:09:42,395 --> 00:09:49,724 for Y over Y for any given X. This shouldn't have a tilda. By dividing by 87 00:09:49,724 --> 00:09:56,959 this X specific partition function. So to be a little bit more concrete, let's 88 00:09:56,959 --> 00:10:06,125 imagine I have a table here And I'm going to make life simple for our selves, for my 89 00:10:06,125 --> 00:10:15,811 self and this is my [inaudible] for X1 Y X0Y0 X0Y1 X1Y0 and X1Y1 and for any given 90 00:10:15,811 --> 00:10:24,806 X in this case this for example these two entries here I'm going to sum them up. 91 00:10:24,806 --> 00:10:32,199 That's going to give me the normalizing constant for these two entries together, 92 00:10:32,199 --> 00:10:39,886 and I'm going to divide by that zed of X0. And that guarantees that these two entries 93 00:10:39,886 --> 00:10:45,838 now sum to one because I've just basically divided by their appropriate normalizing 94 00:10:45,838 --> 00:10:51,577 constant. And similarly, [cough] I'm going to add these over here, and I'm going to 95 00:10:51,577 --> 00:10:56,891 divide this entry by [inaudible]. And so now define a family of conditional 96 00:10:56,891 --> 00:11:13,440 distributions. So this is a family Of conditional distributions. Which varies by 97 00:11:13,440 --> 00:11:21,306 X. Now it turns out that CRF's are highly related to a model that we have previously 98 00:11:21,306 --> 00:11:27,563 seen, in, in many machine learning classes and also comes up as a CPD representation 99 00:11:27,563 --> 00:11:33,310 in, in Bayesian Network which is the logistic function, or the logistic model. 100 00:11:33,310 --> 00:11:39,349 So in order to, understand that connection let's look at a very, very simple case 101 00:11:39,349 --> 00:11:45,534 where we have both X's and Y's are binary random variables so they take on values in 102 00:11:45,534 --> 00:11:52,820 the space 01. And we're going to use in out log linear model a simple 103 00:11:52,820 --> 00:12:04,014 representation of my log linear features which is just the indicator function. So 104 00:12:04,014 --> 00:12:09,937 we have one, my indicator function is one when both XI and Y, when XI and Y are both 105 00:12:09,937 --> 00:12:15,789 one. And zero otherwise. And that's going to have a parameter YI. Now let's actually 106 00:12:15,789 --> 00:12:22,235 plug that into the CRF representation and see what happens. So let's look at 107 00:12:22,495 --> 00:12:29,264 [inaudible] of XI and Y equals one. Well, if you look at that in this case Y is 108 00:12:29,264 --> 00:12:35,599 always one and now we have two choices. Either XI is one, in this case the 109 00:12:35,599 --> 00:12:42,975 indicator function is one or XI is zero in which case the indicator function is zero. 110 00:12:42,975 --> 00:12:54,814 So you can rewrite this as WI times XI X, sorry, X. Wixi. Right? Because if XI's 111 00:12:54,814 --> 00:13:06,094 zero, then you get X of WI times zero and if XI's one you get X of WI. Hmm. On the 112 00:13:06,094 --> 00:13:13,459 other hand, if I make Y equal zero, then my indicator function is zero, because if 113 00:13:13,459 --> 00:13:19,625 Y is zero than the indicator function is zero and at that point I get exponential 114 00:13:19,625 --> 00:13:25,716 zero which is equal to one. So these are my two cases. I have what is the value of 115 00:13:25,716 --> 00:13:31,581 this factor for Y=1 and what is the value of this factor for Y=0. And now I can go 116 00:13:31,581 --> 00:13:39,771 ahead and compute my unnormalized density. And my un-normalized density has the 117 00:13:39,771 --> 00:13:45,596 following again I'm going to do two different cases. There is the case where Y 118 00:13:45,596 --> 00:13:51,349 equals zero and the case where y equals one and my un-normalized density in the 119 00:13:51,349 --> 00:13:57,318 case Y equals one is just multiplying all of these guys up here. So multiplying all 120 00:13:57,318 --> 00:14:02,928 of these guys which gives rise to this exponential over here just because the 121 00:14:02,928 --> 00:14:10,517 product of the [inaudible] 'Kay? So, that is in this case and here clearly the 122 00:14:10,517 --> 00:14:16,630 product of a bunch of ones is one, so that's pretty straightforward. And, so 123 00:14:16,630 --> 00:14:23,403 now, putting this all together to produce a normalized density, remember? My goal is 124 00:14:23,403 --> 00:14:30,012 to produce a normalized density which is the P of Y, my binary value Y, given all 125 00:14:30,012 --> 00:14:36,290 of the features X. And if you just stick this together this is, when you just 126 00:14:36,290 --> 00:14:45,703 rewrite this, this is the probability of Y. Equals one, X. And this is divided by 127 00:14:45,703 --> 00:14:53,460 the probability of Y=1, X. Plus the probability of Y=0, X, which is my 128 00:14:53,460 --> 00:15:02,428 normalizing constant. [inaudible] This is a very familiar shape. It's the sigma 129 00:15:02,428 --> 00:15:11,885 function it's E to the power of Z if we call this Z So it's E to the Z divided by 130 00:15:11,885 --> 00:15:17,750 one plus E to the Z, which is exactly [inaudible] similar function. So what we 131 00:15:17,750 --> 00:15:24,463 have, eh, concluded from this, is that the logistic model Is a very simple 132 00:15:24,463 --> 00:15:38,390 [inaudible] So, broadening from this, from this, particular mathematical derivation. 133 00:15:38,390 --> 00:15:43,661 What we have here is that if we were to think about the model where we had a joint 134 00:15:43,661 --> 00:15:48,806 density of Y and X together as a kind of a naive base model because we only have 135 00:15:48,806 --> 00:15:53,697 [inaudible] terms that relayed the Y and the X size. You can think of it as a 136 00:15:53,697 --> 00:15:58,778 bunch, if we , if we weren't doing this conditional normalization we would have a 137 00:15:58,778 --> 00:16:03,605 model that looks like this. We would have, you know, the Y and we would have a 138 00:16:03,605 --> 00:16:14,588 [inaudible] feature that relates Y to X1. Y2x2 Up to Y2XM And that would be 139 00:16:14,588 --> 00:16:19,580 effectively like a [inaudible] model because we don't have any features, 140 00:16:19,580 --> 00:16:25,266 paralyze features that connect the XI's to each other we would effectively have a 141 00:16:25,266 --> 00:16:30,883 model where the XI's are independent given Y. So if I weren't doing a conditional 142 00:16:30,883 --> 00:16:37,335 model, if I were to just use this set of potentials Represent the joint 143 00:16:37,335 --> 00:16:42,166 distribution of X and Y it would be effectively like a [inaudible] model and 144 00:16:42,166 --> 00:16:47,249 it would make very strong independence assumptions. But because I'm modeling this 145 00:16:47,249 --> 00:16:53,279 as a conditional distribution like this. This is a conditional distribution. I've 146 00:16:53,279 --> 00:16:58,866 effectively removed from this analysis any notion of the correlations between the X's 147 00:16:58,866 --> 00:17:04,000 and I'm just modeling how the X's come together to affect the probability of Y. 148 00:17:04,420 --> 00:17:09,940 And so that's really the difference between a [inaudible] model and a logistic 149 00:17:09,940 --> 00:17:15,669 regression model, and that same intuition extends to much richer classes of models 150 00:17:15,669 --> 00:17:21,399 where I don't just have binary variables in a single Y, but rather a very rich set 151 00:17:21,399 --> 00:17:26,989 of Y's and X's and nevertheless this ability to sort of ignore the distribution 152 00:17:26,989 --> 00:17:32,670 over the features and focus only on the target variables allows me to, exploit, 153 00:17:32,670 --> 00:17:38,694 allows me to sort of ignore correlations between rich features and not worry about 154 00:17:38,694 --> 00:17:44,638 whether they're independent of each other or not. So for example going back to our 155 00:17:44,638 --> 00:17:50,138 notion of [inaudible] for image segmentation here we typically have very 156 00:17:50,138 --> 00:17:55,566 rich features of the variables so for example we think about individual 157 00:17:55,566 --> 00:18:01,354 [inaudible] potentials that relate the features XI to the class label YI, we 158 00:18:01,354 --> 00:18:05,616 don't worry about how correlated the features are. We can have color 159 00:18:05,616 --> 00:18:10,692 histograms, texture features, you can have discriminative patches like looking for 160 00:18:10,692 --> 00:18:15,831 the eye of the cow, for example. And all of these are going to be really correlated 161 00:18:15,831 --> 00:18:21,195 with each other, but I don't care. You can even look at features that are outside of 162 00:18:21,195 --> 00:18:25,119 the super pixels. You could say oh well if it's you know green underneath in a 163 00:18:25,119 --> 00:18:29,143 completely different super pixel. Maybe it's more like we could be a cow or a 164 00:18:29,143 --> 00:18:33,117 sheep, because they tend to be on grass that's [inaudible]. These are definitely 165 00:18:33,117 --> 00:18:37,393 correlated because your counting the same feature from my super pixel as well as for 166 00:18:37,393 --> 00:18:41,367 a different super pixel that's fine I don't care because I'm not worried about 167 00:18:41,367 --> 00:18:46,724 the correlation because of super pixels So the correlations don't matter. You can 168 00:18:46,724 --> 00:18:52,515 even, and this is very commonly done, train your favorite discriminative 169 00:18:52,515 --> 00:18:58,877 classifier - a support vector machine, boosting, random force - anything that you 170 00:18:58,877 --> 00:19:05,240 like. To predict the probability of YI given a whole bunch of image features X. 171 00:19:05,540 --> 00:19:11,829 And that's fine too. And in fact, that is how one achieves high performance on most 172 00:19:11,829 --> 00:19:18,118 of these tasks. By training very strong classifiers for, in most cases your node 173 00:19:18,118 --> 00:19:24,100 potentials, that is the predictors for individual variables. And then, adding on 174 00:19:24,100 --> 00:19:30,160 top of that, [inaudible] features or, or not just [inaudible] but a higher order. 175 00:19:31,960 --> 00:19:46,879 Features. Between, between the Y's. It's im-, heh one important point here that is 176 00:19:46,879 --> 00:19:53,238 useful to make is that the word features is overloaded in this framework. And that 177 00:19:53,238 --> 00:19:59,674 might be confusing and rightfully so. There are features in the context of image 178 00:19:59,674 --> 00:20:05,722 features, for example, like these guys over here. And that's one use of the word 179 00:20:05,722 --> 00:20:11,925 features. And the other use of the word features, which is this usage, is in terms 180 00:20:11,925 --> 00:20:19,017 of features in my log-linear model. And these [inaudible] that we use to define 181 00:20:19,017 --> 00:20:23,624 the log linear model and features are actually used for both which is an 182 00:20:23,624 --> 00:20:28,800 unfortunate thing but there it is. So, hopefully this will be clear from context. 183 00:20:29,349 --> 00:20:35,080 The same kind of idea applies when we do CRF's for language. Again, we usually have 184 00:20:35,080 --> 00:20:39,902 here features that are very highly correlated with each other. So, for 185 00:20:39,902 --> 00:20:45,632 example, whether the word is capitalized is correlated with whether the word is in 186 00:20:45,632 --> 00:20:50,804 some atlas or name list. Definitely correlated features. Correlated with 187 00:20:50,804 --> 00:20:56,384 whether the previous word is Mrs. Or Mr. All sorts of other features that are often 188 00:20:56,384 --> 00:21:01,760 very correlated with each other you can even see that the same, that this word is 189 00:21:01,760 --> 00:21:07,523 used as a feature for more than one word, that's fine it's not a problem because we 190 00:21:07,523 --> 00:21:13,055 don't try and model this distribution over the words in a sentence but rather the 191 00:21:13,055 --> 00:21:20,015 probability of the labels. Given the words. So to summarize, a CRF is 192 00:21:20,015 --> 00:21:26,157 deceptively like any other Gibbs Distribution. But a critical, a subtle but 193 00:21:26,157 --> 00:21:32,382 critical difference is that it's normalized differently. It's normalized so 194 00:21:32,382 --> 00:21:40,026 that you're, it's creating a conditional distribution on Y given X. And we've seen 195 00:21:40,026 --> 00:21:45,745 that as a special case it subsumes your standard logistic regression model, but 196 00:21:45,745 --> 00:21:52,233 has a lot of other, but has much richer expressive power. A key feature of it is 197 00:21:52,233 --> 00:21:57,491 that we can, we don't need to model the distribution over variables that we don't 198 00:21:57,491 --> 00:22:02,944 care about, only the ones that we actually care about predicting and that a critical 199 00:22:02,944 --> 00:22:08,202 utility of this is that you can design really, really expressive predictors of, 200 00:22:08,202 --> 00:22:13,720 of pieces of the model without worrying about incorrect between, between different 201 00:22:13,720 --> 00:22:19,238 variables which would be inevitable if you actually tried to model this distribution, 202 00:22:19,238 --> 00:22:22,484 joint distribution over these expressive features.