1 00:00:00,110 --> 00:00:02,612 Okay, so I guess this slide is this I guess 2 00:00:02,612 --> 00:00:05,127 you can say this slide but I guess this is true. 3 00:00:05,127 --> 00:00:09,830 That no all this models on the left side right there are a multiple of those right. 4 00:00:09,830 --> 00:00:12,063 So many of those are in fact special cases of 5 00:00:12,063 --> 00:00:15,363 Markov logic in the sense that you can represent them, right. 6 00:00:15,363 --> 00:00:17,988 Markov networks, Markov random fields, when I say Bayesian 7 00:00:17,988 --> 00:00:20,059 networks what I mean is that essentially it's as 8 00:00:20,059 --> 00:00:22,181 good as converting it into a Bayesian network with 9 00:00:22,181 --> 00:00:25,480 a Markov network and then representing as Markov logic network. 10 00:00:25,480 --> 00:00:28,130 Of course, you lose some independences. 11 00:00:28,130 --> 00:00:28,910 >> You lose some? 12 00:00:28,910 --> 00:00:29,280 >> Yeah, yeah. 13 00:00:29,280 --> 00:00:32,425 So it is, in the sense that, any distribution 14 00:00:32,425 --> 00:00:35,823 which is in the network, you could present here. 15 00:00:35,823 --> 00:00:36,687 But you lose, yes. 16 00:00:36,687 --> 00:00:37,397 [CROSSTALK]. 17 00:00:37,397 --> 00:00:38,179 >> You will produce things which. 18 00:00:38,179 --> 00:00:40,489 >> Yes, yes. 19 00:00:40,489 --> 00:00:43,100 >> Not necessarily [INAUDIBLE]. 20 00:00:43,100 --> 00:00:43,720 >> Dependent, right, yes. 21 00:00:43,720 --> 00:00:47,800 So you will lose some independencies, that is true, right. 22 00:00:47,800 --> 00:00:49,595 So, but [UNKNOWN], right? 23 00:00:49,595 --> 00:00:52,272 So which essentially a special case in that restricted 24 00:00:52,272 --> 00:00:54,725 sense, at least in the case of Bayesian network. 25 00:00:54,725 --> 00:00:57,785 But Markov network it is obviously true that, you can 26 00:00:57,785 --> 00:01:02,762 just have propositional sort of right, [UNKNOWN] Markov network, yeah, right. 27 00:01:02,762 --> 00:01:06,680 So, right, and in principle what happens that if you make [UNKNOWN] which 28 00:01:06,680 --> 00:01:08,673 means you don't have variables then 29 00:01:08,673 --> 00:01:12,665 this propositional model becomes essentially enigmatic, right. 30 00:01:12,665 --> 00:01:16,091 But what is more interesting is that you have this explicit notion 31 00:01:16,091 --> 00:01:18,893 of interdependence and [UNKNOWN] structure, which, 32 00:01:18,893 --> 00:01:21,330 which many of these models [UNKNOWN] right. 33 00:01:21,330 --> 00:01:23,920 So, that is, that is what you have, What 34 00:01:23,920 --> 00:01:26,180 is even more interesting is contradiction to first-order logic. 35 00:01:26,180 --> 00:01:27,470 When it's a first-order logic, at least 36 00:01:27,470 --> 00:01:29,860 here, when, an infinite weight first-order logic. 37 00:01:29,860 --> 00:01:30,250 Right? 38 00:01:30,250 --> 00:01:33,010 So, in the limit of all the weights sending to infinity. 39 00:01:33,010 --> 00:01:34,580 In the same limit, right? 40 00:01:34,580 --> 00:01:36,416 So, meaning if your Markov works, if all of 41 00:01:36,416 --> 00:01:39,000 them together turn to infinity, then you can show that. 42 00:01:39,000 --> 00:01:40,790 This exactly becomes first-order logic. 43 00:01:40,790 --> 00:01:42,179 Right, so all the weights which are 44 00:01:42,179 --> 00:01:45,060 satisfied, will get the probability of non-zero probability. 45 00:01:45,060 --> 00:01:48,835 And all the weights that are not satisfied will get the zero probability. 46 00:01:48,835 --> 00:01:52,258 >> When you say [INAUDIBLE] does it mean 47 00:01:52,258 --> 00:01:57,460 that you can replace logical and pyramid with that? 48 00:01:57,460 --> 00:02:00,429 >> Logical entailment with infinite case. 49 00:02:01,740 --> 00:02:06,070 And when you take the limit of the [UNKNOWN] probability, yes. 50 00:02:06,070 --> 00:02:08,660 >> A implies B which implies C. 51 00:02:08,660 --> 00:02:09,430 >> Yes. 52 00:02:09,430 --> 00:02:11,620 >> That follows from [UNKNOWN]. 53 00:02:11,620 --> 00:02:16,073 >> That follows from nine friends, if you take the limit of [UNKNOWN] yes. 54 00:02:16,073 --> 00:02:17,216 In the finite case. 55 00:02:17,216 --> 00:02:17,638 >> [INAUDIBLE] 56 00:02:17,638 --> 00:02:20,660 >> Meaning your network should be finite, finite number of constants. 57 00:02:20,660 --> 00:02:23,740 Yes, yes, yes, yes, but that should not be too difficult to see. 58 00:02:23,740 --> 00:02:25,600 >> That's, that's very straight forward. 59 00:02:25,600 --> 00:02:26,790 >> Yes, that's fairly straight forward. 60 00:02:26,790 --> 00:02:27,150 Yeah, yeah. 61 00:02:27,150 --> 00:02:29,551 So, all of them, all the decided weights will get the same 62 00:02:29,551 --> 00:02:32,900 probability, so their key assignments, each one will get one byte key. 63 00:02:32,900 --> 00:02:34,855 And others you'll get zero, it is for W 64 00:02:34,855 --> 00:02:37,401 will give you, right, because even if there is one 65 00:02:37,401 --> 00:02:40,364 difference, one formula which is not satisfied, then the 66 00:02:40,364 --> 00:02:43,704 denominator will really overpower the numerator and get to zero. 67 00:02:44,810 --> 00:02:46,920 Right, but what is more interesting is that if you 68 00:02:46,920 --> 00:02:50,780 are satisfied, if you have a satisfiable knowledge base, right. 69 00:02:50,780 --> 00:02:54,482 So your knowledge base is something which can be satisfied and if positive 70 00:02:54,482 --> 00:02:57,227 weights, then those assignments, which satisfy all 71 00:02:57,227 --> 00:03:00,360 the formulas are the modes of distribution. 72 00:03:00,360 --> 00:03:00,520 Right. 73 00:03:00,520 --> 00:03:03,930 So remember I talked about this sort of [UNKNOWN] probability. 74 00:03:03,930 --> 00:03:06,078 What you're saying is that, if your knowledge 75 00:03:06,078 --> 00:03:07,851 base in fact has an assignment which can 76 00:03:07,851 --> 00:03:10,268 satisfy all the formulas, those are the assignments 77 00:03:10,268 --> 00:03:13,130 which will get the maximum probability during distribution. 78 00:03:13,130 --> 00:03:15,947 So which is very, very good, right which is a very nice probability. 79 00:03:15,947 --> 00:03:18,815 In particular Markov logic allows contradictions between formulas, 80 00:03:18,815 --> 00:03:20,890 which is not the case for pure first-order logic. 81 00:03:20,890 --> 00:03:24,593 That's what we're looking for, okay. 82 00:03:24,593 --> 00:03:28,381 >> [INAUDIBLE]. 83 00:03:28,381 --> 00:03:29,578 >> Mm-hm. 84 00:03:29,578 --> 00:03:33,366 >> [INAUDIBLE] >> Mm-hm. 85 00:03:33,366 --> 00:03:37,154 >> [INAUDIBLE] >> Mm-hm. 86 00:03:37,154 --> 00:03:39,743 >> [INAUDIBLE]. 87 00:03:41,820 --> 00:03:42,310 >> no. 88 00:03:42,310 --> 00:03:45,008 >> Because like, smoking implies cancer. 89 00:03:45,008 --> 00:03:46,070 >> Uh-huh. 90 00:03:46,070 --> 00:03:50,498 >> But they're not talking anything about cancer implies smoking. 91 00:03:50,498 --> 00:03:51,029 So this [CROSSTALK]. 92 00:03:51,029 --> 00:03:53,761 >> So what you're saying not cancer implies not smoking? 93 00:03:53,761 --> 00:03:57,071 >> Right, so actually, so you're saying that [UNKNOWN] 94 00:03:57,071 --> 00:04:02,450 right, so first-order logic doesn't have any emotional directionality, right? 95 00:04:02,450 --> 00:04:05,872 I mean, I mean it is, it is [INAUDIBLE] or cancer, right, yeah. 96 00:04:05,872 --> 00:04:05,922 >> [CROSSTALK]. 97 00:04:05,922 --> 00:04:10,174 >> Yeah, yeah, yeah, so you saw, in this case it is little bit misleading 98 00:04:10,174 --> 00:04:12,266 the example that I gave that was more 99 00:04:12,266 --> 00:04:15,730 for orientation, but they are purely logical formulas. 100 00:04:15,730 --> 00:04:17,820 We are not talking about causality yet, right. 101 00:04:17,820 --> 00:04:19,880 So there is no causal semantics right. 102 00:04:19,880 --> 00:04:22,405 Although that intuition may help sometimes in terms of the 103 00:04:22,405 --> 00:04:25,457 weights that we get, but the mathematically its not causing, okay. 104 00:04:25,457 --> 00:04:27,350 Okay. 105 00:04:27,350 --> 00:04:28,820 So, how are we doing on time? 106 00:04:28,820 --> 00:04:29,740 How much I mean? 107 00:04:29,740 --> 00:04:30,050 >> 15 minutes. 108 00:04:30,050 --> 00:04:31,835 >> 15 minutes, okay. 109 00:04:31,835 --> 00:04:34,810 >> May be skip it [UNKNOWN]. 110 00:04:34,810 --> 00:04:34,950 >> Okay. 111 00:04:34,950 --> 00:04:36,880 >> And go to an example. 112 00:04:36,880 --> 00:04:38,680 >> Example, sure, yeah. 113 00:04:38,680 --> 00:04:40,488 So let me just, what we, what I will do 114 00:04:40,488 --> 00:04:43,280 is that I will define the Inference and Learning tasks. 115 00:04:43,280 --> 00:04:44,714 I will not go in detail of that, there is 116 00:04:44,714 --> 00:04:46,500 some interest in that then we can talk off later. 117 00:04:46,500 --> 00:04:49,470 And then I will give you some example that will help I think. 118 00:04:49,470 --> 00:04:49,870 Right. 119 00:04:49,870 --> 00:04:52,940 So just couple of slides. 120 00:04:52,940 --> 00:04:55,430 [COUGH] So the Inference problem is, I think we talked about that right? 121 00:04:55,430 --> 00:04:56,760 Given some nodes in the network right? 122 00:04:56,760 --> 00:04:59,100 So green nodes are given, and lets say you know the weights. 123 00:04:59,100 --> 00:05:01,750 So then you find the margin of probability of the nodes on the 124 00:05:01,750 --> 00:05:04,720 network, or what is the most likely set up of the network, right. 125 00:05:04,720 --> 00:05:07,282 So in this case the green nodes are given and you're saying, 126 00:05:07,282 --> 00:05:10,600 what is the probability Ana smokes, or Bob smokes, or Bob has cancer. 127 00:05:10,600 --> 00:05:13,214 Right, so that is the inference problem, and, right. 128 00:05:13,214 --> 00:05:15,838 So, this is called marginal interference results, 129 00:05:15,838 --> 00:05:19,200 or something called MPE: Most Probable Explanation, right. 130 00:05:19,200 --> 00:05:21,701 So, that, deals with the question of, what is 131 00:05:21,701 --> 00:05:24,650 the most likely state of the, the nodes together? 132 00:05:24,650 --> 00:05:27,990 And, that can be different from the marginals, maximum marginal state, okay. 133 00:05:27,990 --> 00:05:30,940 So, that, is a different interference problem. 134 00:05:30,940 --> 00:05:35,660 And, right, so I think we talked about that, that. 135 00:05:37,010 --> 00:05:37,620 Okay this is fine. 136 00:05:37,620 --> 00:05:40,024 So let me just play one or two more slides. 137 00:05:40,024 --> 00:05:44,111 Marginal inference, what you do is just put the, put the 138 00:05:44,111 --> 00:05:49,230 formula the, state into the equation of the, of the problem distribution. 139 00:05:49,230 --> 00:05:53,090 One little thing is that, typically you're given some evidence, right? 140 00:05:53,090 --> 00:05:56,466 So, given that evidence, you fix those nodes to evidence, and then 141 00:05:56,466 --> 00:06:00,210 marginal inference is find the probability of Y which are your query right? 142 00:06:00,210 --> 00:06:01,140 So then z depends on x. 143 00:06:01,140 --> 00:06:04,050 Because you fixed those evidence. 144 00:06:04,050 --> 00:06:06,505 And rest of the things remain the same, and this is 145 00:06:06,505 --> 00:06:10,650 the distribution then you can find the probability of y in principle. 146 00:06:10,650 --> 00:06:13,543 And doing this exactly is exponential in number 147 00:06:13,543 --> 00:06:16,183 of states of y, right, number of variables y. 148 00:06:16,183 --> 00:06:20,130 So typically you have to resort to other approximate sometimes. 149 00:06:20,130 --> 00:06:22,535 And I'll skip that page, so I'll skip that, 150 00:06:22,535 --> 00:06:25,620 that slides are propagation and there are some interesting 151 00:06:25,620 --> 00:06:27,902 work here where we can find clusters of nodes 152 00:06:27,902 --> 00:06:30,694 which we have similarly, but, but let me skip that. 153 00:06:31,820 --> 00:06:33,142 So this is timing. 154 00:06:33,142 --> 00:06:33,623 Okay. 155 00:06:33,623 --> 00:06:36,117 [BLANK_AUDIO] 156 00:06:36,117 --> 00:06:38,050 Right, so now, learning parameters. 157 00:06:38,050 --> 00:06:40,980 So learning parameters is, that given this formulas, right. 158 00:06:40,980 --> 00:06:44,410 So the formulas typically some domain expert can give you, right. 159 00:06:44,410 --> 00:06:47,770 So given the formulas, what are the rates that you would like to learn. 160 00:06:47,770 --> 00:06:47,950 Right. 161 00:06:47,950 --> 00:06:51,510 So let's say you, we assume that you have the data. 162 00:06:51,510 --> 00:06:52,000 Right. 163 00:06:52,000 --> 00:06:53,806 Let's assume full observability. 164 00:06:53,806 --> 00:06:55,430 So example, there are three constraints. 165 00:06:55,430 --> 00:06:57,720 So the data is in the form of an additional database, right? 166 00:06:57,720 --> 00:07:01,010 So you'll say that in my domain Ana smokes, Bob smokes, 167 00:07:01,010 --> 00:07:04,610 Ana has cancer, Bob has cancer, and the other friends relationship. 168 00:07:04,610 --> 00:07:06,410 So, given this, and you assume that the, 169 00:07:06,410 --> 00:07:08,610 it's a closed world assumption, that anything not 170 00:07:08,610 --> 00:07:10,410 in the database is false, then from that, 171 00:07:10,410 --> 00:07:13,470 essentially you use the principle of maximum likelihood, right. 172 00:07:13,470 --> 00:07:16,243 So, you know what is probability of this particular 173 00:07:16,243 --> 00:07:19,850 assignment of things with the variables in your network. 174 00:07:19,850 --> 00:07:22,300 So find the weights which maximizes getting this weight. 175 00:07:22,300 --> 00:07:22,670 Right? 176 00:07:22,670 --> 00:07:25,060 And that is the maximum like-node principle, and you can 177 00:07:25,060 --> 00:07:28,150 follow the standard application [UNKNOWN] and get, get the rates, right. 178 00:07:28,150 --> 00:07:28,443 So that is [UNKNOWN]. 179 00:07:28,443 --> 00:07:30,821 >> [INAUDIBLE]. 180 00:07:30,821 --> 00:07:34,400 >> Is there any [UNKNOWN] here? 181 00:07:34,400 --> 00:07:34,670 Right? 182 00:07:34,670 --> 00:07:36,719 So, what you can do is that you can start 183 00:07:36,719 --> 00:07:40,190 with some prior, and that will give you some regular addition. 184 00:07:40,190 --> 00:07:40,340 Right? 185 00:07:40,340 --> 00:07:43,520 So you can start with some prior [UNKNOWN], yeah. 186 00:07:43,520 --> 00:07:45,910 And, in fact, there is some work there, if you're, do, 187 00:07:45,910 --> 00:07:48,900 learn regular [INAUDIBLE] that was the [INAUDIBLE] actually go towards here. 188 00:07:48,900 --> 00:07:49,400 Yeah. 189 00:07:50,580 --> 00:07:50,990 Right. 190 00:07:50,990 --> 00:07:54,020 So the, the, so, Daniel Lowd and Pedro Domingos had a 191 00:07:54,020 --> 00:07:57,580 paper at ECML, and I think that compares many, methods for learning. 192 00:07:57,580 --> 00:08:00,830 Second order methods also, so you can get that, if you're interested. 193 00:08:00,830 --> 00:08:03,660 So the learning structure corresponds to learning the formulas, right. 194 00:08:03,660 --> 00:08:07,549 So, let's say, if the formulas are not given to you, then how do you learn those? 195 00:08:07,549 --> 00:08:10,300 And standard ILP based techniques can best be used, right. 196 00:08:10,300 --> 00:08:13,475 Now it's problematic so we have to relate your likelihood to see how good those 197 00:08:13,475 --> 00:08:15,448 are, and there are many different techniques, 198 00:08:15,448 --> 00:08:17,824 many more advances techniques which have been proposed. 199 00:08:17,824 --> 00:08:19,740 I will not go in details of that. 200 00:08:19,740 --> 00:08:23,860 And [UNKNOWN] has done lot of work on that. 201 00:08:23,860 --> 00:08:26,568 Right so he has a couple of three or four papers at 202 00:08:26,568 --> 00:08:28,601 ICML, a succession of papers which 203 00:08:28,601 --> 00:08:33,110 really improves those, those learning structure techniques. 204 00:08:33,110 --> 00:08:35,358 But, but let me just give you one, one thing. 205 00:08:35,358 --> 00:08:38,320 One idea that, you can either learn the network from 206 00:08:38,320 --> 00:08:41,820 the outside or [UNKNOWN] says that I have this formulas. 207 00:08:41,820 --> 00:08:44,833 And then are there more formulas that can be learned? 208 00:08:44,833 --> 00:08:47,216 Right, for example, given this formula as you 209 00:08:47,216 --> 00:08:49,540 can see the other formula that can be learned, 210 00:08:49,540 --> 00:08:51,564 and which is friends x, y and friends y, 211 00:08:51,564 --> 00:08:54,440 x they are essentially, this is a similar calculation. 212 00:08:54,440 --> 00:08:57,750 Right, so from the data you can potentially learn this formula. 213 00:08:57,750 --> 00:08:59,499 So what do you typically do for your real problem 214 00:08:59,499 --> 00:09:01,161 is that maybe you can start with a formula that 215 00:09:01,161 --> 00:09:03,392 a domain expert gives, and then you refine those formulas, 216 00:09:03,392 --> 00:09:05,471 based on the data, right so that's a typical setting. 217 00:09:05,471 --> 00:09:07,154 If you are very confident that you know 218 00:09:07,154 --> 00:09:09,529 the formulas, then you can directly [UNKNOWN] right. 219 00:09:09,529 --> 00:09:10,500 So that is the system. 220 00:09:12,320 --> 00:09:14,513 Okay, right, so I should mention that one of 221 00:09:14,513 --> 00:09:16,650 the reasons that it has become so popular and 222 00:09:16,650 --> 00:09:19,019 so many people have really adopted this for their 223 00:09:19,019 --> 00:09:22,020 own problems, is that there is software called Alchemy. 224 00:09:22,020 --> 00:09:23,260 And in fact there are at least four 225 00:09:23,260 --> 00:09:25,840 or five different implementations which have come about. 226 00:09:25,840 --> 00:09:28,955 All of them, I think, are freely available online. 227 00:09:28,955 --> 00:09:32,580 [INAUDIBLE] implement Markov logic, and they give various 228 00:09:32,580 --> 00:09:36,390 inference algorithms, various learning algorithms, and many different features. 229 00:09:36,390 --> 00:09:38,810 So you can just, after this talk, if you're interested, you can just 230 00:09:38,810 --> 00:09:42,600 go back and download that, and it should work, you know, as, just fine. 231 00:09:42,600 --> 00:09:44,383 And, of course, when you really want to make it 232 00:09:44,383 --> 00:09:46,537 work for your own problem, there may be issues, right. 233 00:09:46,537 --> 00:09:50,120 Because it's just like any other, any other subsystem. 234 00:09:50,120 --> 00:09:52,024 And one key issue that I should mention is 235 00:09:52,024 --> 00:09:54,610 that, it is very easy to blow up your network. 236 00:09:54,610 --> 00:09:57,381 Right, because you can write two or three formulas and if it is 237 00:09:57,381 --> 00:10:00,325 very high then you can sort of [INAUDIBLE] which is very, very big. 238 00:10:00,325 --> 00:10:02,235 So that is something that you do very careful when 239 00:10:02,235 --> 00:10:04,570 you write the formulas, not to blow up your network. 240 00:10:04,570 --> 00:10:06,485 And there are techniques that deal with 241 00:10:06,485 --> 00:10:09,098 that explicitly, in terms of inference engine, but 242 00:10:09,098 --> 00:10:13,219 it is good to be, you know, pragmatic and doubt such right formulas, which clearly 243 00:10:13,219 --> 00:10:17,106 do not lead to not very big network, right, very, yeah, so that maybe a, 244 00:10:17,106 --> 00:10:21,090 one challenge that, or something that is sort of an odd, as you use this system.