1 00:00:00,000 --> 00:00:04,726 So, today's topic is an important extention on the language of graphical 2 00:00:04,726 --> 00:00:10,110 models. And it's intended to deal with the very, large class of cases, where what 3 00:00:10,110 --> 00:00:15,625 we'd like to do is not just write down one kind of graphical model for a particular 4 00:00:15,625 --> 00:00:20,352 application. But rather, come up with something that is a general purpose, 5 00:00:20,549 --> 00:00:25,670 representation that allows us to solve multiple problems using the same exact 6 00:00:25,670 --> 00:00:31,184 model. So, to understand what that means in a somewhat more concrete setting, let's 7 00:00:31,234 --> 00:00:36,923 go back. Now for genetic inheratince that we have discussed previously it's arguably 8 00:00:36,923 --> 00:00:42,204 the earliest example of Bayesian network reasoning before Bayesian networks were 9 00:00:42,204 --> 00:00:48,138 invented and here we have as input a pedigree. Which is a family tree. And 10 00:00:48,138 --> 00:00:52,526 we're interested in reasoning about a particular trait. And for each pedigree 11 00:00:52,526 --> 00:00:57,198 and each trait we can construct a Bayesian network and the Bayesian network might 12 00:00:57,198 --> 00:01:01,415 look like this. But clearly if you had a somewhat different family tree, so 13 00:01:01,415 --> 00:01:06,201 suddenly you had another three cousins and a great grandfather join the family tree, 14 00:01:06,201 --> 00:01:10,304 or if you had a different family altogether, you would still want to use 15 00:01:10,304 --> 00:01:14,805 the same sort of ideas, the same pieces of what we used in the first network to 16 00:01:14,805 --> 00:01:19,535 construct this other network because there is clearly a lot of commonality between 17 00:01:19,535 --> 00:01:27,936 them. So we have, what you might call, sharing. Between models. But in addition 18 00:01:27,936 --> 00:01:37,116 to that. You also have in this example as a fairly obvious sharing within the model 19 00:01:37,116 --> 00:01:44,926 so for example, this CPD that tells us how Selma's genotype affects Selma's blood 20 00:01:44,926 --> 00:01:51,822 type presumably is the same process by which Marge's genotype affects Marge's 21 00:01:51,822 --> 00:01:58,845 blood type and the same for Maggie and Lisa and Bart and Homer and everybody. So, 22 00:01:59,060 --> 00:02:04,444 so we have this tremendous amount of sharing of both dependency models and 23 00:02:04,444 --> 00:02:10,114 parameters. Similarly, you might argue, you might, looking at this realize that 24 00:02:10,114 --> 00:02:15,569 the genetic inheritance model by which Bart's genotype is determined by the 25 00:02:15,569 --> 00:02:21,440 genotype of his two parents as the same inheritance model that applies to Lisa. To 26 00:02:21,440 --> 00:02:26,584 Maggie, to Marge, to Selma, and so on. So once again we have a lot of parameters 27 00:02:26,584 --> 00:02:31,929 that are shared not just between but also within the model. So we'd like to have 28 00:02:31,929 --> 00:02:37,541 some way of constructing models that have this, large amounts of shared structure 29 00:02:37,541 --> 00:02:42,752 that allows us to both construct large models from sparse parametrization and 30 00:02:42,752 --> 00:02:48,348 also to construct entire family of models from a single concise representation. This 31 00:02:48,348 --> 00:02:53,705 is not the only such application. This is probably the most commonly used type of 32 00:02:53,705 --> 00:02:58,552 graphical models are those that have shared structure and shared parameters. 33 00:02:58,552 --> 00:03:03,463 So, here is another example that we've seen previously, this is for natural 34 00:03:03,463 --> 00:03:09,266 language processing, a sequence model, for in this case trying to identify named 35 00:03:09,266 --> 00:03:16,350 entity recognition, a very common task for which graphical models have been used. 36 00:03:16,350 --> 00:03:22,332 And here, also, we have a sequence model, and we have, again, shared, shared pieces, 37 00:03:22,332 --> 00:03:27,968 for example. The parameters that relate the latent variable, in this case, what 38 00:03:28,018 --> 00:03:34,222 type of, what type of variable, what type of entity it is. 39 00:03:34,272 --> 00:03:40,131 Is it a person, is it a location, and so on. There is a set of parameters here, and 40 00:03:40,131 --> 00:03:45,899 they're going to be independent of the place and the sequence. In which we find 41 00:03:45,899 --> 00:03:50,243 the word because not because it's necessarily an exactly correct model I 42 00:03:50,243 --> 00:03:55,181 mean one could clearly imagine cases where the position in the sequence might make 43 00:03:55,181 --> 00:03:59,643 the difference but because it's often a very useful simplifying assumption, 44 00:03:59,643 --> 00:04:04,581 specifically because it allows us to A use parameters, reuse parameters and B allow 45 00:04:04,581 --> 00:04:09,460 us to apply the same model to sequences of varying length without having to worry 46 00:04:09,460 --> 00:04:14,576 about what is my fifteen word model versus what's my eighth word model and so this is 47 00:04:14,576 --> 00:04:22,923 a, another case where you have We have a tremendous amount of reuse of 48 00:04:22,923 --> 00:04:30,231 parameters. We've already seen similarly the examples in this segmentation clearly 49 00:04:30,231 --> 00:04:36,206 we don't want to have a separate model for every super pixel in the image there's 50 00:04:36,306 --> 00:04:45,517 hundreds of super pixels so we have sharing across superpixels 51 00:04:45,617 --> 00:04:53,209 So for example, the model here that, that relates the class label of the 52 00:04:53,209 --> 00:05:00,718 superpixel to the image features of that superpixel is generally one to be shared 53 00:05:00,718 --> 00:05:07,128 as are the parameters that involve adjacent superpixels. So these edge 54 00:05:07,128 --> 00:05:14,180 potentials are also going to shared across in this case, pairs of superpixels. 55 00:05:15,680 --> 00:05:24,902 And once again we have sharing across models as well because 56 00:05:24,902 --> 00:05:31,038 we are going to have one such model for image A and obviously we don't want to 57 00:05:31,038 --> 00:05:37,640 construct a separate model for every image so once again we have sharing between and within 58 00:05:39,020 --> 00:05:48,914 a model. So let's look at one example a little bit more concretely 59 00:05:48,914 --> 00:05:53,962 because it's an example that we're gonna use in some of the later analysis. So now, 60 00:05:53,962 --> 00:05:58,947 let's return to our university example where we have a student who takes a class 61 00:05:58,947 --> 00:06:03,687 and gets a grade and that the grade depends on the student's difficulty oh I 62 00:06:03,687 --> 00:06:08,486 am sorry difficulty of the course not intelligence of the student. Now this is 63 00:06:08,486 --> 00:06:13,707 all fine if we're interested in using just about an individual student, but now let's 64 00:06:13,707 --> 00:06:18,251 imagine that we want to think about an entire university. So now we have a 65 00:06:18,251 --> 00:06:25,692 difficulty variable. So these are all. Difficulty variables. For different 66 00:06:25,692 --> 00:06:31,258 courses in this case C1 up to CN are different courses that exist in our 67 00:06:31,258 --> 00:06:37,425 university and conversely on the other side we have multiple students and this is 68 00:06:37,425 --> 00:06:44,009 a set of intelligence variables that are indexed by different students so we have 69 00:06:44,009 --> 00:06:48,765 the intelligence of student one up to the intelligence of student m. Now note that 70 00:06:48,765 --> 00:06:53,404 these are different random variables they can and generally will take different 71 00:06:53,404 --> 00:06:58,392 values from each other but they all share a probabilistic model and that's sort of 72 00:06:58,392 --> 00:07:03,747 the kind of sharing that we have in mind. And what we see here, is that the grade of 73 00:07:03,747 --> 00:07:09,134 a student within a course, which are these variables down here, depend on the 74 00:07:09,134 --> 00:07:14,947 difficulty of the relevant course and the intelligence of the relevant student. So 75 00:07:14,947 --> 00:07:20,618 for example, the grade of student one in course one, depends on the difficulty of 76 00:07:20,618 --> 00:07:26,390 course one and on the intelligence. Of student one and once again we have sharing 77 00:07:26,390 --> 00:07:31,264 of the both the structure and the parameters across these different grade 78 00:07:31,264 --> 00:07:36,666 variables so that they all have the same kind of dependency structure in the same 79 00:07:36,666 --> 00:07:44,789 CPD. Another example is that of robot localization and this is another example 80 00:07:44,789 --> 00:07:52,861 of, in this case, the time series where the robot moves through time from one 81 00:07:52,861 --> 00:08:02,840 position to the other. And although the position at time T is different. 82 00:08:04,880 --> 00:08:21,576 Changes over time. We expect that the dynamics of the robot. Are fixed. We'll 83 00:08:21,576 --> 00:08:27,473 talk more about that later. So that gives us a graphical model that again, looks a 84 00:08:27,473 --> 00:08:33,223 little bit, this is one example of such a graphical model where we see that the 85 00:08:33,223 --> 00:08:38,828 position to the robot pose, over here, these X variables depend on for example 86 00:08:38,828 --> 00:08:44,870 the previous pose and on whatever control action the robot took. And we're assuming 87 00:08:48,952 --> 00:08:53,034 that once again we have sharing. Of these parameters for each instantiation of this 88 00:08:53,034 --> 00:08:59,635 variable. So what that gives rise to is a class of models that are represented in 89 00:08:59,635 --> 00:09:04,854 terms of template variables. Where a template variable is something that we end 90 00:09:04,854 --> 00:09:09,808 replicating, in many cases, again and again, within a single model as well as 91 00:09:09,808 --> 00:09:14,828 across models. And so the replication is indexed by the, by the fact that the 92 00:09:14,828 --> 00:09:19,584 variable. You can think of it as a function that takes arguments. And the 93 00:09:19,584 --> 00:09:24,540 arguments, for example, might be time points, as in this example over here. So 94 00:09:24,640 --> 00:09:29,813 here we have a location variable that's indexed by time point or sonar reading 95 00:09:29,863 --> 00:09:35,086 indexed by time point. We have, in this case, a genotype variable and a phenotype 96 00:09:35,086 --> 00:09:40,359 variable that's indexed by a particular person. A class label that's indexed by 97 00:09:40,359 --> 00:09:45,698 pixel. And similarly the difficultly of the intelligence and the grades that are 98 00:09:45,698 --> 00:09:50,638 indexed, in this case, by different combinations of indexees, course student 99 00:09:50,638 --> 00:09:56,973 or course student pairs. And a template model is a language that tells us how 100 00:09:56,973 --> 00:10:03,245 template variables can be the dependency models for template variables and how 101 00:10:03,245 --> 00:10:10,250 concrete instantiations of variables what are called ground variables. Like the ones 102 00:10:10,300 --> 00:10:14,579 that are actually indexed by a particular timepoint or person how they inherit the 103 00:10:14,629 --> 00:10:18,543 dependency molecule [inaudible]. And their's a whole range of such languages 104 00:10:18,543 --> 00:10:22,716 that have been developed in a special purpose way for different applications. So 105 00:10:22,716 --> 00:10:26,732 dynamic Bayesian networks are intended for dealing with temporal processes for 106 00:10:26,832 --> 00:10:32,444 example. Where we have replication over time we have a whole range of [inaudible] 107 00:10:32,494 --> 00:10:38,087 for object relational models both directed models and undirected models where you 108 00:10:38,087 --> 00:10:43,940 have multiple objects such as people or students and courses or pixels so people. 109 00:10:43,940 --> 00:10:49,099 courses, pixels, and lots of other things which can be related to each other in 110 00:10:49,099 --> 00:10:54,593 different ways and how you represent the dependency model over that ensemble in a 111 00:10:54,593 --> 00:10:55,464 coherent way.