Video
Đăng bởi Ban biên tập OpenER ·
Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
PROFESSOR
OK. That's low.
Được rồi. Nhỏ quá.
All right.
Được rồi.
I can't seem to change the volume down here, so I either have to talk really quietly or hope they can fix that in the back.
Có vẻ tôi không chỉnh được âm lượng ở dưới này, nên hoặc là tôi phải nói thật khẽ, hoặc là hy vọng phía sau chỉnh được.
If I get carried away and you all get like blasted into the back of your seats, I apologize in advance. It's easy to get carried away because we're talking out Bayes' Nets again today.
Nếu tôi hăng quá và các bạn bị âm thanh đập ngửa ra ghế, tôi xin lỗi trước. Rất dễ hăng lên vì hôm nay chúng ta lại nói về mạng Bayes.
OK. All right.
Được. Rồi.
So today we're going to talk about inference in Bayes' Nets, which is the process of taking your lovely Bayes' Net that describes your domain and your variables, and the probabilistic interactions between those variables locally, and answering global questions, like, what does this variable over here do if I observe something clear on the other side
Hôm nay ta sẽ nói về suy luận trong mạng Bayes, tức là quá trình lấy mạng Bayes đáng yêu của bạn, mô tả miền bài toán và các biến của bạn, cùng các tương tác xác suất cục bộ giữa các biến đó, rồi trả lời các câu hỏi toàn cục, chẳng hạn, biến ở đây sẽ ra sao nếu tôi quan sát được điều gì đó ở tận phía bên kia
of the network?
của mạng?
So let's first remember what Bayes' Nets actually are, because we're going to be using this semantic definition formula over and over again today and in the next lecture.
Trước hết hãy nhớ lại mạng Bayes thực sự là gì, vì ta sẽ dùng đi dùng lại công thức định nghĩa ngữ nghĩa này trong hôm nay và bài giảng tới.
So a Bayes' Net is — they're also called graphical models. They're a model of your domain.
Mạng Bayes còn được gọi là mô hình đồ thị. Nó là một mô hình của miền bài toán của bạn.
The nodes in the Bayes' Net represent variables that you care about in your domain, and those variables have values, which are the domains of those variables.
Các nút trong mạng Bayes biểu diễn những biến mà bạn quan tâm trong miền đó, và các biến đó có giá trị, chính là miền giá trị của chúng.
The network is also a directed acyclic graph over those variables where the arrows encode something about direct influence between variables.
Mạng cũng là một đồ thị có hướng không chu trình trên các biến, trong đó các mũi tên mã hóa ảnh hưởng trực tiếp giữa các biến.
And, in particular, underneath each variable in the network, lives a conditional probability table that specifies what that variable does — meaning what is its conditional distribution over all of its values in its domain — given the various settings of the parent.
Đặc biệt, bên dưới mỗi biến trong mạng có một bảng xác suất có điều kiện cho biết biến đó hoạt động thế nào, nghĩa là phân phối có điều kiện của nó trên tất cả các giá trị trong miền của nó, với từng cách gán giá trị của các nút cha.
And that's where we get to say — actually, let's just pull up an example. OK. So from a couple of lectures ago, we had built this tiny little Bayes' Net and it's still there.
Và đó là chỗ ta được nói rằng thôi, ta mở một ví dụ lên. Được. Từ vài bài giảng trước, ta đã xây mạng Bayes nhỏ xíu này và nó vẫn còn đây.
And in this Bayes' Net, each node represents a variable like low pressure causes rain, rain causes the drip in my roof, and it also causes traffic.
Trong mạng này, mỗi nút biểu diễn một biến: áp suất thấp gây ra mưa, mưa gây ra nước nhỏ giọt trên mái nhà tôi, và cũng gây ra kẹt xe.
There's no arc between drip and traffic, because there's no direct influence between them in a way that we mostly made precise in the last lecture when we talked about conditional independence.
Không có cung giữa nhỏ giọt và kẹt xe, vì giữa chúng không có ảnh hưởng trực tiếp theo cách mà ta đã làm khá chính xác ở bài trước khi nói về tính độc lập có điều kiện.
But if we take a look inside here, inside each of these — so underneath low pressure, it doesn't have any parents.
Nhưng nếu ta nhìn vào bên trong từng nút này, ví dụ bên dưới áp suất thấp, nó không có nút cha.
There's just a little probability over that variable that says, oh, there's low pressure 10% of the time.
Chỉ có một xác suất nhỏ trên biến đó, cho biết áp suất thấp xảy ra 10% thời gian.
But if I go to a more interesting node, like traffic, there is a description of how likely traffic is under all its conditions.
Nhưng với nút thú vị hơn như kẹt xe, có mô tả khả năng kẹt xe trong mọi điều kiện của nó.
So here it says when there is rain, 80% chance of traffic. When there's no rain, 30% chance of traffic.
Ở đây ghi: khi có mưa, 80% là kẹt xe. Khi không mưa, 30% là kẹt xe.
And, in general, the more parents you have, the more different behaviors can exist at that node, because you get to specify a conditional probability for each setting of the parents.
Nói chung, càng nhiều nút cha, nút đó càng có nhiều hành vi khác nhau, vì bạn phải chỉ định một xác suất có điều kiện cho mỗi cách gán giá trị của các nút cha.
So maybe we'll actually go look that. Let's say we want traffic to also depend on — I guess before we had a ball game.
Vậy ta thử xem sao. Giả sử ta muốn kẹt xe còn phụ thuộc vào trước đó ta có một trận bóng.
So there can be a ball game or not. And I'm going to make an arc between ball game and traffic.
Vậy có thể có trận bóng hoặc không. Tôi sẽ vẽ một cung giữa trận bóng và kẹt xe.
And now what I have to do is, suddenly, this sort of becomes a pain, because I need to specify how likely traffic is for each combination of the parent.
Và giờ đột nhiên việc này hơi phiền, vì tôi cần chỉ định khả năng kẹt xe cho từng tổ hợp của các nút cha.
So maybe if there's rain and ballgame, almost guaranteed traffic. If there's rain but no ball game, 80%. Ball game but no rain, maybe that's 50%. And neither rain nor ball game, maybe that's 20%.
Có thể nếu có mưa và có trận bóng, gần như chắc chắn kẹt xe. Có mưa nhưng không có trận bóng thì 80%. Có trận bóng nhưng không mưa, có thể là 50%. Còn không mưa cũng không có trận bóng, có thể là 20%.
And so the more parents you have, the more action there is inside that node, because you've got to specify what it does for each combination of the parents.
Vậy càng nhiều nút cha, bên trong nút đó càng có nhiều thứ xảy ra, vì bạn phải chỉ định nó làm gì với từng tổ hợp của các nút cha.
So that's written here.
Điều này được viết ở đây.
Underneath each node x is the following conditional probability family. It's a distribution over x, but it's not one distribution over x, it's distribution over x for each combination of values of the parents.
Bên dưới mỗi nút x là họ xác suất có điều kiện sau. Đó là một phân phối trên x, nhưng không phải một phân phối trên x, mà là phân phối trên x cho mỗi tổ hợp giá trị của các nút cha.
A Bayes' Net, which is this graphical structure along with a conditional probability family for each node, encodes a joint distribution as a product of local distributions.
Một mạng Bayes, gồm cấu trúc đồ thị này cùng một họ xác suất có điều kiện cho mỗi nút, mã hóa một phân phối đồng thời dưới dạng tích của các phân phối cục bộ.
So if your nodes in your network are x1 through xn, here is the definition of the joint probability your Bayes' Net encodes.
Nếu các nút trong mạng là x1 đến xn, thì đây là định nghĩa xác suất đồng thời mà mạng Bayes của bạn mã hóa.
The joint probability of some complete assignment, x1 through xn, is the product of each Xi, given the parents in the network. If you have no parents, that's a bunch of independent probabilities.
Xác suất đồng thời của một phép gán đầy đủ nào đó, x1 đến xn, là tích của từng Xi cho trước các nút cha trong mạng. Nếu không có nút cha, đó chỉ là một loạt xác suất độc lập.
That would be a very simple network.
Đó sẽ là một mạng rất đơn giản.
If nodes have all kinds of parents, then this starts to become a complex expression, and in the limit, this will look like the chain rule, and it will represent an arbitrary class of probability distributions.
Nếu các nút có đủ loại nút cha, thì biểu thức này bắt đầu trở nên phức tạp, và ở giới hạn, nó sẽ giống quy tắc chuỗi, và biểu diễn được một lớp tùy ý các phân phối xác suất.
In general, you want to build a network that has all of your variables connected up, but with a small number of parents for each, so that each of these terms is relatively simple, even though the whole network it defines may be an — encoding all kinds of interesting interactions.
Nói chung, bạn muốn xây một mạng nối tất cả các biến lại, nhưng mỗi biến có ít nút cha, để mỗi số hạng này tương đối đơn giản, dù cả mạng mà nó định nghĩa có thể mã hóa đủ loại tương tác thú vị.
All right.
Được rồi.
So this is the definition of the probability of an entry in the joint probability table defined by a Bayes' Net, and you just multiply it together, all of the appropriate conditional probabilities that match on those values.
Đây là định nghĩa xác suất của một mục trong bảng xác suất đồng thời được định nghĩa bởi một mạng Bayes, và bạn chỉ việc nhân với nhau tất cả các xác suất có điều kiện thích hợp mà khớp với những giá trị đó.
Sometimes I'll call this the Bayes' Net reconstitution formula, because it lets you take these little conditional probabilities and inflate them into a giant network — or sorry — inflate them into a giant joint distribution where each and every entry in that high dimensional table gets filled in according to this recipe.
Đôi khi tôi gọi đây là công thức tái dựng mạng Bayes, vì nó cho phép ta lấy những xác suất có điều kiện nhỏ này và phồng chúng thành một mạng khổng lồ — à nhầm, phồng chúng thành một phân phối đồng thời khổng lồ, trong đó từng mục của bảng nhiều chiều đó được điền theo công thức này.
Sort of a wasteful thing to do, but we — we're going to have to do it for a while until we have a better algorithm, which we'll get today.
Làm vậy hơi lãng phí, nhưng ta sẽ phải làm như thế một thời gian cho đến khi có thuật toán tốt hơn, mà hôm nay ta sẽ học.
OK. Here's an example of a Bayes' Net. Hopefully, this network is not only familiar, you're getting mildly sick of it. This is the alarm network.
OK. Đây là một ví dụ về mạng Bayes. Hy vọng mạng này không chỉ quen thuộc, mà các em còn hơi phát chán rồi. Đây là mạng báo động.
It's a classic. This one says, burglaries happen but rarely. It's up here. There's no parents to burglary, so it's just a little marginal distribution over that.
Một ví dụ kinh điển. Mạng này nói rằng trộm có xảy ra nhưng hiếm. Nó ở trên này. Trộm không có nút cha, nên nó chỉ là một phân phối biên nhỏ.
Earthquakes happen, but rarely.
Động đất có xảy ra, nhưng hiếm.
That also doesn't have any parents, so just a marginal distribution.
Nó cũng không có nút cha, nên chỉ là một phân phối biên.
The heart of this network lives under the alarm node, which specifies how likely it is that alarm's going to go off when there's a burglary, and an earthquake when there's a burglary, but not an earthquake, and so on.
Phần cốt lõi của mạng nằm ở nút báo động, nó cho biết khả năng chuông báo động kêu khi có trộm và động đất, khi có trộm nhưng không có động đất, v.v.
And so, for example, if there's a burglary and an earthquake, the alarm goes off 90% — 95% of the time. OK.
Ví dụ, nếu có trộm và động đất, chuông kêu 90% — 95% số lần. OK.
Similarly, Judd — John has a node and Mary has a node that specify how often they call, with and without the alarm.
Tương tự, Judd — John có một nút và Mary có một nút cho biết họ gọi thường xuyên thế nào, khi có và không có báo động.
If I started adding parents to these things, like I, you know — maybe John alway — Mary always calls me when there — when there's an earthquake.
Nếu tôi thêm nút cha cho những nút này, chẳng hạn, giả sử John luôn — Mary luôn gọi cho tôi khi — khi có động đất.
Then suddenly Mary's distribution family is going to be more complicated, because now I have to specify what she does with and without earthquake, with and without alarm, and all the different combinations.
Thì phân phối của Mary sẽ phức tạp hơn, vì giờ tôi phải chỉ rõ cô ấy làm gì khi có và không có động đất, có và không có báo động, và mọi tổ hợp khác.
OK. So this is what's in the Bayes' Net, and it defines any entry in the joint distribution over these variables b, e, a, j, and m.
OK. Vậy đây là nội dung của mạng Bayes, và nó xác định mọi mục của phân phối đồng thời trên các biến b, e, a, j và m.
So, for example, if I come up to you and I say, all right, you've got this Bayes' Net, which is a bunch of little local pieces, but I'm intensely curious how likely it is that there is a burglary, but not an earthquake.
Ví dụ, giả sử tôi đến hỏi các em, này, các em có mạng Bayes này, gồm nhiều mảnh cục bộ nhỏ, nhưng tôi rất tò mò khả năng có trộm mà không có động đất.
The alarm goes off. John does not call, but Mary does. That's this event here. And, now, you're thinking, that's an awfully specific event.
Chuông báo động kêu. John không gọi, nhưng Mary gọi. Đó là sự kiện này đây. Giờ các em nghĩ, sự kiện này cụ thể quá đi.
But, remember, all the things we actually care about, like how likely is it that there's an earthquake if Mary calls me, are derived by summing together and dividing lots of these elementary events.
Nhưng nhớ rằng, mọi thứ ta thực sự quan tâm, như khả năng có động đất nếu Mary gọi, đều suy ra bằng cách cộng rồi chia nhiều sự kiện cơ bản như vậy.
OK.
OK.
So if I really am intensely curious about this, I look and I look around and I see, you know what, my Bayes' Net doesn't actually list an entry for that element of the joint distribution, but it gives me a recipe to reconstitute it.
Nếu tôi thật sự tò mò về nó, tôi tìm khắp nơi và thấy rằng mạng Bayes không liệt kê mục nào cho phần tử đó của phân phối đồng thời, nhưng nó cho tôi công thức để tái dựng.
So I can multiply together the relevant pieces. Let's see, so we need the probability of a burglary. All right. Minus e, an earthquake.
Nên tôi nhân các mảnh liên quan lại với nhau. Xem nào, ta cần xác suất có trộm. Được. Trừ e, tức là động đất.
And, now, I need to know the alarm is plus a. Well — but it's plus a in an environment where it's plus b and minus e. So I go find that here.
Và giờ tôi cần biết báo động là cộng a. Nhưng nó là cộng a trong môi trường mà có cộng b và trừ e. Nên tôi tìm nó ở đây.
So that's plus b minus e plus a. That's here. OK. And I look up all the relevant things.
Tức là cộng b, trừ e, cộng a. Nó ở đây. OK. Và tôi tra tất cả các giá trị liên quan.
So John does not call, despite the alarm, 10% of the time. Mary does call when there's an alarm 70% of the time.
John không gọi dù có báo động, 10% số lần. Mary gọi khi có báo động 70% số lần.
And I can multiply these little pieces together, and I'll get some number. I don't know what that is. It's some small number that represents that exact event.
Tôi nhân các mảnh nhỏ này lại với nhau, và sẽ ra một con số. Tôi không biết nó là bao nhiêu. Một số nhỏ biểu diễn đúng sự kiện đó.
And if you say, well, actually, I just want to know how likely it is Mary calls. Well, how do you find that?
Và nếu các em nói, thực ra tôi chỉ muốn biết khả năng Mary gọi. Vậy tìm nó thế nào?
You take this event, and a whole bunch of other events where Mary calls, and you add them up. Which events?
Lấy sự kiện này cùng hàng loạt sự kiện khác mà Mary gọi, rồi cộng lại. Những sự kiện nào?
All the events that are plus m, and then you sum together everything on all the other axes and all combinations. And that gives you the total marginal probability of Mary calling.
Tất cả sự kiện có cộng m, rồi cộng mọi thứ trên tất cả các trục còn lại và mọi tổ hợp. Và nó cho ta tổng xác suất biên của việc Mary gọi.
And in this Bayes' Net, you can answer questions of the whole distribution by assembling it as you go from the Bayes' Net definition.
Với mạng Bayes này, ta có thể trả lời các câu hỏi về toàn bộ phân phối bằng cách lắp ráp nó dần dần từ định nghĩa của mạng Bayes.
So if I told you I am now — I've changed my mind, I'm intensely curious about no burglary, no earthquake, the alarm goes off anyway but nobody calls me.
Nếu tôi nói bây giờ tôi — tôi đổi ý rồi, tôi rất tò mò về trường hợp không trộm, không động đất, chuông vẫn kêu nhưng không ai gọi tôi.
You could go and you'd be like, all right, I'll circle different entries and I'll multiply them together, and I can get you that probability, too.
Các em sẽ nói, được thôi, tôi khoanh các mục khác nhau rồi nhân chúng lại, và tôi cũng tính được xác suất đó. nữa.
And whatever probability asked for you can fetch it on demand. Even though you're taking entries, you're fetching probabilities from a high dimensional table of exponential size.
Xác suất nào được hỏi, các em đều lấy ra theo yêu cầu. Dù các em đang lấy các mục, lấy xác suất từ một bảng nhiều chiều có kích thước mũ.
But you're building it out of local little pieces of, basically, linear size, assuming all of the conditional probabilities are of constant size. OK.
Nhưng các em dựng nó từ những mảnh cục bộ nhỏ có kích thước về cơ bản là tuyến tính, giả sử tất cả các xác suất có điều kiện có kích thước không đổi. OK.
All right. So what do we have with Bayes' Net so far? We've seen representation, which is what probability distribution does a Bayes' Net represent? We've talked about conditional independence.
Được rồi. Vậy đến giờ ta có gì về mạng Bayes? Ta đã thấy biểu diễn, tức là mạng Bayes biểu diễn phân phối xác suất nào? Chúng ta đã nói về tính độc lập có điều kiện.
What conditional independences hold for sure in a network based on the structure?
Những tính độc lập có điều kiện nào chắc chắn đúng trong một mạng, dựa trên cấu trúc của nó?
And you saw last time how we can do a kind of a search operation and look at various kinds of paths in the network to detect independence.
Và lần trước các em đã thấy ta có thể làm một dạng phép tìm kiếm và xem xét nhiều loại đường đi trong mạng để phát hiện tính độc lập.
Today what we're going to talk about is probabilistic inference, and we actually already spoiled this lecture a little bit two lectures ago when we talked about inference by enumeration.
Hôm nay điều chúng ta sẽ nói là suy luận xác suất, và thật ra chúng ta đã lỡ tiết lộ trước bài này một chút từ hai buổi trước khi nói về suy luận bằng liệt kê.
Unfortunately, that's usually intractable, so we're going to replace it with a much better algorithm today, which is also intractable, because this is an AI class, and everything we do is NP-hard.
Đáng tiếc là cách đó thường không khả thi về mặt tính toán, nên ta sẽ thay bằng một thuật toán tốt hơn nhiều hôm nay, thuật toán này cũng không khả thi, vì đây là môn AI, và mọi thứ ta làm đều là NP-hard.
But it's usually better. All right. So we're going to talk about inference by enumeration again.
Nhưng nó thường tốt hơn. Được rồi. Vậy ta sẽ nói lại về suy luận bằng liệt kê.
We're going to talk about variable enumeration, which is, usually, much better, even on the worst case, it's just as bad.
Ta sẽ nói về khử biến, mà thường tốt hơn nhiều, dù trong trường hợp xấu nhất nó cũng tệ như vậy.
We're going to talk about why these things are so hard and, in particular, why is inference in a Bayes' Net NP-hard. And then we'll talk about sampling, but not today.
Ta sẽ nói vì sao những việc này lại khó đến thế, và cụ thể là vì sao suy luận trong mạng Bayes là NP-hard. Sau đó là lấy mẫu, nhưng không phải hôm nay.
And then, finally, learning these networks from data will come later.
Và cuối cùng, học các mạng này từ dữ liệu sẽ để sau.
All right. Any questions before we start in on inference? OK. Let's do it.
Được rồi. Có câu hỏi nào trước khi ta vào phần suy luận không? OK. Bắt đầu nào.
So what is inference? Inference means a lot of different things to a lot of different people. Here in this class, it means calculating some quantity from a joint probability distribution.
Vậy suy luận là gì? Suy luận mang nhiều nghĩa khác nhau với nhiều người khác nhau. Trong lớp này, nó có nghĩa là tính một đại lượng nào đó từ một phân phối xác suất đồng thời.
So you imagine the given is some collection of probabilities. Maybe it's the whole joint probability table in all its exponential size glory.
Các em hình dung cái cho trước là một tập các xác suất. Có thể là toàn bộ bảng xác suất đồng thời với kích thước hàm mũ hoành tráng của nó.
More often, it's a bunch of conditional probabilities that define a Bayes' Net. OK. Some examples of things you might calculate from those givens are the canonical thing is a posterior probability.
Thường hơn, đó là một loạt xác suất có điều kiện định nghĩa một mạng Bayes. OK. Một vài ví dụ về những thứ các em có thể tính từ những dữ kiện đó, thứ tiêu biểu nhất là xác suất hậu nghiệm.
I care about variable Q. There's a bunch of evidence variables whose values I know and, unfortunately, there's going to be a bunch of other variables called hidden variables that I don't care about, and I also don't observe.
Tôi quan tâm biến Q. Có một loạt biến bằng chứng mà tôi biết giá trị, và đáng tiếc là có một loạt biến khác gọi là biến ẩn mà tôi không quan tâm, và cũng không quan sát được.
And we're going to have to sum them out, and that creates a lot of time complexity. So posterior probability is give me a distribution over Q given the evidence I have.
Ta sẽ phải lấy tổng loại chúng đi, và điều đó tạo ra độ phức tạp thời gian lớn. Xác suất hậu nghiệm tức là cho tôi một phân phối trên Q với bằng chứng tôi có.
Another classic canonical query you might do is a most likely explanation query, where you say, I have some evidence.
Một truy vấn tiêu biểu khác là truy vấn giải thích có khả năng nhất, tức là bạn nói, tôi có một số bằng chứng.
I would like to know the most likely value of a one or more variables given that evidence. We're only going to talk about the top kinds of queries today.
Tôi muốn biết giá trị có khả năng nhất của một hay nhiều biến khi có bằng chứng đó. Hôm nay ta chỉ nói loại truy vấn ở trên.
But the bottom ones are solved in, basically, the same way. In most cases, the changes are limited to sums turning into maxes.
Nhưng loại bên dưới được giải về cơ bản theo cùng cách. Trong hầu hết trường hợp, thay đổi chỉ là tổng biến thành max.
All right. So let's figure out how to answer. Mainly, let's get back on track. Let's wait — all right.
Được rồi. Giờ ta tìm cách trả lời. Nói chính xác hơn, quay lại đúng hướng nào. Khoan, được rồi.
So posterior probability queries. We have this algorithm called inference by enumeration. It barely fits on the slides. Let's go through it again.
Vậy là các truy vấn xác suất hậu nghiệm. Ta có thuật toán gọi là suy luận bằng liệt kê. Nó vừa khít trên slide. Ta xem lại một lượt.
But, in fact, it's really simple. It's just really, really excruciatingly slow in practice. So the general case is we have a Bayes' Net. So what's our Bayes' Net look like?
Nhưng thật ra nó rất đơn giản. Chỉ là trong thực tế nó cực kỳ, cực kỳ chậm. . Trường hợp tổng quát là ta có một mạng Bayes. Vậy mạng Bayes của ta trông thế nào?
It's got a bunch of circles, and those all represent some variables. And there's one that we care about. Let's call it Q, right there. You care about that variable.
Nó có một loạt hình tròn, và chúng biểu diễn các biến. Và có một biến ta quan tâm. Gọi nó là Q, ngay đây. Các em quan tâm biến đó.
Actually, often the variable you care about's the top.
Thật ra thường biến ta quan tâm nằm ở trên cùng.
Then there's some things we know, like, maybe we know — maybe we know the value of this variable, and the value of this variable, and the value of the variable, and the value of this variable.
Rồi có vài thứ ta biết, chẳng hạn, có thể ta biết giá trị của biến này, và giá trị của biến này, và giá trị của biến này, và giá trị của biến này. .
And, of course, the whole reason that this is interesting is because we've also got all kinds of arrows going between these variables in various patterns. OK. So there's your Bayes' Net.
Và dĩ nhiên, lý do toàn bộ chuyện này thú vị là vì còn có đủ loại mũi tên nối giữa các biến này theo nhiều kiểu. OK. Đây là mạng Bayes của các em.
You have a query variable that you care about. That's your query variable.
Có một biến truy vấn mà các em quan tâm. Đó là biến truy vấn.
We have evidence variables, which are — oh, you know, I know that variable takes on the value 7. And then there is the bane of your existence, there are the hidden variables.
Ta có các biến bằng chứng, ví dụ tôi biết biến đó nhận giá trị 7. Và rồi còn có nỗi ám ảnh của các em, đó là các biến ẩn.
There're these variables, and these variables, and these variables. There're all those variables in your network that at the moment you don't observe, and you also don't care about their values.
Có những biến này, và những biến này, và những biến này. Đó là tất cả các biến trong mạng mà hiện tại ta không quan sát, và cũng không quan tâm giá trị của chúng.
So if I give you a joint distribution, I say, hey, here's the probability distribution over x and y. I'd like to know the probability that x takes on the value big.
Nếu tôi cho các em một phân phối đồng thời, nói rằng, đây là phân phối xác suất trên x và y. Tôi muốn biết xác suất x nhận giá trị big.
What do you do? You say, well, that's not in my network. That's not in my joint distribution.
Các em làm gì? Các em nói, cái đó không có trong mạng của tôi. Nó không có trong phân phối đồng thời của tôi.
But I'll find all the entries that say big, and I'll add them up, and that will give you your marginal. OK. So we talked about that. We've had that for a while.
Nhưng tôi sẽ tìm mọi mục có big, rồi cộng lại, và đó sẽ là phân phối biên của các em. OK. Ta đã nói về chuyện đó. Ta có nó được một thời gian rồi.
In this case, x is the query variable. y is the hidden variable. Because we have to get rid of it by adding it up, by summing it out.
Trong trường hợp này, x là biến truy vấn. y là biến ẩn. Vì ta phải loại bỏ nó bằng cách cộng lại, tức là lấy tổng loại nó.
And there are no, in that case, evidence variables. OK. So if evidence query and hidden, that's all your variables.
Và trong trường hợp đó không có biến bằng chứng. OK. Vậy bằng chứng, truy vấn và ẩn, đó là tất cả các biến của các em.
And we'd like to have the probability of Q, the query variable, given all the evidence variables. So what do we do? Let me make it go away.
Và ta muốn tính xác suất của Q, biến truy vấn, khi biết tất cả các biến bằng chứng. Vậy ta làm gì? Để tôi xóa cái này đi.
If I give you the whole big joint distribution in all of its exponential sized glory, step one is you take the entries consistent with the evidence.
Nếu tôi đưa cho bạn toàn bộ phân phối đồng thời lớn với kích thước mũ hoành tráng của nó, bước một là lấy các dòng phù hợp với bằng chứng.
So everything that doesn't match your evidence, you just delete it from your table, and your table shrinks. Right. So all those entries that don't match the evidence, they're gone.
Tức là mọi thứ không khớp với bằng chứng, bạn xóa khỏi bảng, và bảng nhỏ lại. Đúng không. Tất cả những dòng không khớp với bằng chứng đều biến mất.
You have a smaller table. Your table is a big joint distribution. So it used to out up to 1. Right.
Bạn có một bảng nhỏ hơn. Bảng của bạn là một phân phối đồng thời lớn. Trước đó nó cộng lại bằng 1. Đúng không.
Because it's a happy well-formed distribution. As soon as I knock out all the rows that don't match the evidence, it doesn't sum up to 1 any more. What does it sum up to?
Vì nó là một phân phối hợp lệ. Ngay khi tôi loại hết các dòng không khớp bằng chứng, tổng không còn bằng 1 nữa. Vậy tổng bằng bao nhiêu?
So if I was like, stop, stop doing inference. Add everything up. Let's say that my evidence was e. What does this add up to?
Giả sử tôi bảo: dừng lại, đừng suy luận nữa. Cộng hết lại. Giả sử bằng chứng của tôi là e. Tổng này bằng bao nhiêu?
Any guesses? It's not 1 any more, it's smaller, because I knocked out all the rows that said something other than e.
Có ai đoán không? Không còn là 1 nữa, nó nhỏ hơn, vì tôi đã loại hết các dòng nói điều gì khác e.
Like this was maybe like, I know it's sunny, knock out all the rainy rows, not — knock out all the windy rows, or whatever else is in there.
Ví dụ như, tôi biết trời nắng, loại hết các dòng mưa, loại hết các dòng có gió, hay bất cứ thứ gì khác ở đó.
OK. What's left is all the rows that say sunny. And when you add them up, you get the probability of sunny. So this thing is going to be the probability of your evidence.
OK. Còn lại là các dòng nói trời nắng. Cộng chúng lại, bạn được xác suất trời nắng. Vậy đại lượng này là xác suất của bằng chứng.
It's like this magic space I can't actually draw any in. OK. So that's the probability of your evidence. But we're not going to do that.
Nó như một chỗ kỳ diệu mà tôi không vẽ vào được. OK. Đó là xác suất của bằng chứng. Nhưng ta sẽ không làm vậy.
That's not why we're here. We didn't come for the probability of the evidence.
Đó không phải mục đích của ta. Ta không đến đây để tìm xác suất của bằng chứng.
So we're going to knock out the rows consistent with the evidence, and then we're going to sum out all of the variables we don't care about.
Vậy ta sẽ loại các dòng phù hợp bằng chứng, rồi ta sẽ lấy tổng để loại mọi biến ta không quan tâm.
That means take this still large dimensional table and get rid of dimensions of that array that correspond to variables that we don't currently want.
Nghĩa là lấy bảng nhiều chiều này và bỏ các chiều của mảng ứng với những biến ta hiện không cần.
And what we'll end up with is a tiny little — so, in mathematics, that's this. So we have — we have the whole distribution here.
Và cuối cùng ta được một mảng rất nhỏ... Trong toán học thì nó là thế này. Ta có toàn bộ phân phối ở đây.
We're going to sum out the hidden variables. And so all those rows that differ only in their value of the hidden variables are going to collide and get summed together into the smaller array.
Ta sẽ lấy tổng loại các biến ẩn. Và những dòng chỉ khác nhau ở giá trị của biến ẩn sẽ gộp lại và được cộng chung thành mảng nhỏ hơn.
And the smaller array represents the probability of Q and the evidence. And for each value of Q, you're going to have a separate entry. So what's this thing look like?
Mảng nhỏ này biểu diễn xác suất của Q và bằng chứng. Với mỗi giá trị của Q, bạn có một mục riêng. Vậy nó trông thế nào?
It's now a one-dimensional array, and the difference between each entry in that array is they have different values of Q. Do they add up? Is it a distribution over Q?
Giờ nó là một mảng một chiều, và điểm khác nhau giữa các mục trong mảng là chúng có giá trị Q khác nhau. Chúng có cộng lại bằng 1 không? Đây có phải phân phối trên Q không?
It's not. They still add up to p of e.
Không. Chúng vẫn cộng lại bằng p của e.
But if you normalize it, which is the last step, meaning, you add up all the entries and then you multiply them all by 1 over that number so that they are proportional to their values, but now sum to 1, you're going to now get, if you take this and normalize, you end up with p of Q, comma, all the e's, and you divide
Nhưng nếu bạn chuẩn hóa, là bước cuối, nghĩa là cộng tất cả các mục rồi nhân tất cả với 1 chia cho tổng đó để chúng vẫn tỉ lệ với giá trị cũ, nhưng giờ có tổng bằng 1, thì khi chuẩn hóa cái này bạn có p của Q, phẩy, tất cả các e, và chia
that by what we know to be p of e, you'll end up with p of Q, given all your evidence. And that was the query you wanted. So that is inference by enumeration.
cho p của e mà ta đã biết, bạn sẽ được p của Q khi biết toàn bộ bằng chứng. Và đó chính là truy vấn bạn muốn. Đó là suy luận bằng liệt kê.
You take your whole table, you select the evidence matching rows, you sum up the variables you don't want — we'll see that more in a second — you normalize, and you're done.
Bạn lấy cả bảng, chọn các dòng khớp bằng chứng, lấy tổng loại các biến không cần, lát nữa ta sẽ thấy rõ hơn, chuẩn hóa, là xong.
OK. Problems with that algorithm, aside from the fact that it barely fits on the slide, one, we don't have the giant joint distribution, we've got a Bayes' Net.
OK. Vấn đề của thuật toán này, ngoài việc nó vừa khít trang chiếu, thứ nhất, là ta không có phân phối đồng thời khổng lồ, ta chỉ có một mạng Bayes.
And while we could, in principle, build the giant joint distribution, that would be a waste of space and time. So that's basically enough problems. We'll stop there. OK.
Và dù về nguyên tắc ta có thể dựng phân phối đồng thời khổng lồ đó, thì thế là phí không gian và thời gian. Vậy là đủ vấn đề rồi. Ta dừng ở đây. OK.
Let's get some more intuition about why this is a bad idea so that we can come up with an idea that — algorithm that's a better idea.
Ta hãy tìm hiểu trực giác vì sao đây là ý tồi để nghĩ ra một thuật toán tốt hơn.
So, if you have unlimited time and unlimited space, inference and Bayes' Nets is easy. You take your Bayes' Net and you get your query.
Nếu có thời gian và không gian vô hạn, suy luận trong mạng Bayes rất dễ. Bạn lấy mạng Bayes và truy vấn của bạn.
And so maybe somebody comes along and says something a lot more reasonable, which is, I'd like to know how likely it is there's a burglary given that John and Mary have called me.
Có thể ai đó đến và hỏi một câu hợp lý hơn nhiều, đó là: tôi muốn biết khả năng có trộm khi John và Mary đều đã gọi cho tôi. OK.
OK. This is a reasonable query. It's not in your Bayes' Net. Your Bayes' Net tells you things like probability that Mary calls given the alarm.
Đây là truy vấn hợp lý. Nó không có sẵn trong mạng Bayes. Mạng Bayes cho bạn những thứ như xác suất Mary gọi khi biết có báo động.
This is a case, by the way, side comment, of we've observed variables at the bottom, which is very common, right.
Nhân tiện, nói thêm một chút, đây là trường hợp ta quan sát các biến ở dưới cùng, điều này rất phổ biến.
This sort of — these — to the extent these Bayes' Nets represent causal domains, the stuff at the top sort of causes the stuff in the middle, that causes the stuff in the bottom, you tend to observe the effects at the bottom and try to reason about the causes.
Trong chừng mực các mạng Bayes này biểu diễn miền nhân quả, thứ ở trên gây ra thứ ở giữa, rồi gây ra thứ ở dưới, bạn thường quan sát các kết quả ở dưới và suy luận về nguyên nhân. Đó không phải điều duy nhất làm được với mạng Bayes, nhưng là việc khá phổ biến.
It's not the only thing you can do with a Bayes' Net, but it's a pretty common thing that people do. We shade nodes to indicate that they're observed.
Ta tô đậm các nút để chỉ rằng chúng đã được quan sát. Ta tô đậm các nút để chỉ rằng chúng đã được quan sát. Ta tô đậm các nút để chỉ rằng chúng đã được quan sát.
So, in this case, I've observed the values for J and M. They're both positive. And I'd like to know the value or, in this case, the distribution over b.
Vậy trong trường hợp này, tôi đã quan sát được giá trị của J và M. Cả hai đều dương. Và tôi muốn biết giá trị, hay đúng hơn là phân phối của b.
What about e and a? I wish they weren't in my network. What can I do about it? Nothing.
Còn e và a thì sao? Ước gì chúng không có trong mạng của tôi. Tôi làm gì được đây? Không làm gì được.
I got to work around it. Say, why didn't you give me a network that doesn't have e and a? Two reasons.
Tôi phải tìm cách xử lý chúng. Bạn có thể hỏi: sao không cho tôi một mạng không có e và a? Có hai lý do.
One, maybe next time you're going to want e and not b, and you want this network to be a sort of multipurpose.
Một, lần sau có thể bạn muốn e chứ không phải b, và bạn muốn mạng này dùng được cho nhiều mục đích.
And the second thing is if you start deleting nodes from your network, the nodes that are left, end up all pointing to each other in all kinds of crazy ways.
Hai, nếu bạn bắt đầu xóa các nút khỏi mạng, thì những nút còn lại sẽ trỏ vào nhau theo đủ kiểu rối rắm.
Because simple interactions that were mediated by those hidden variables are now just sort of like a free-for-all of direct interactions between the remaining ones.
Vì những tương tác đơn giản vốn được trung gian bởi các biến ẩn đó giờ thành một mớ hỗn độn các tương tác trực tiếp giữa những biến còn lại.
So, usually, you're going to have some hidden variables, for one reason or another. So you're in this situation. I'd like to know the probability of b, the distribution over b.
Nên thường thì bạn sẽ có một số biến ẩn, vì lý do này hay lý do khác. Vậy ta đang ở tình huống này. Tôi muốn biết xác suất của b, phân phối của b.
So it's going to be two values. One for plus and one for minus. Given J and M are both true, let's figure it out. We've got laws of probability.
Nên sẽ có hai giá trị. Một cho cộng và một cho trừ. Cho trước J và M đều đúng, ta hãy tính. Ta có các luật xác suất.
First law of probability says that that conditional distribution over b is proportional to the values where we have joint distributions instead of conditional.
Luật xác suất đầu tiên nói rằng phân phối có điều kiện của b tỉ lệ với các giá trị mà ta dùng phân phối đồng thời thay cho có điều kiện.
So let's stop and figure out what this little fish shaped with a b means. This in — this proportionality with respect to b. So this says these two things are almost equal.
Hãy dừng lại xem ký hiệu hình con cá nhỏ với chữ b này nghĩa là gì. Đây là tính tỉ lệ theo b. Tức là hai thứ này gần bằng nhau.
They're not actually equal. But they'd be equal if we summed up the values over b, and multiply by the inverse. So that means they're proportional.
Chúng không thật sự bằng nhau. Nhưng sẽ bằng nếu ta lấy tổng các giá trị theo b rồi nhân với nghịch đảo. Nghĩa là chúng tỉ lệ với nhau.
OK. And so what this says is if you want a conditional probability, you compute the equivalent joint probability, and then normalize. All right. We know how to normalize.
OK. Vậy điều này nói rằng nếu muốn có xác suất có điều kiện, bạn tính xác suất đồng thời tương ứng, rồi chuẩn hóa. Được rồi. Ta biết cách chuẩn hóa.
If I gave you this — so what is this? Like what is this?
Nếu tôi cho bạn cái này, vậy nó là gì? Nó là gì nhỉ?
I don't know, but it's like — it's something that says — b says plus minus 0.2, 0.1, and when you normalize, you get one-third and 2/3. So let's compute this.
Tôi không biết, nhưng giả sử nó cho biết b cộng trừ là 0,2 và 0,1, và khi chuẩn hóa, bạn được một phần ba và hai phần ba. Giờ ta hãy tính cái này.
Let's compute this joint — this joint value here. So what is that? That is for each value of b. I don't actually know that joint distribution — those joint probabilities, either.
Ta tính giá trị đồng thời ở đây. Nó là gì? Là với mỗi giá trị của b. Thật ra tôi cũng không biết phân phối đồng thời đó, tức các xác suất đồng thời đó.
But if I introduce e and a with specific values, suddenly, the network tells me how to get these. So I want those joint probability entries.
Nhưng nếu tôi đưa e và a vào với giá trị cụ thể, thì đột nhiên mạng cho tôi biết cách tính chúng. Tôi muốn các mục xác suất đồng thời đó.
I now have to look for the probability of b, and e, and a, and plus j, and plus m. We're going to do it for each value of e and a.
Giờ tôi phải tìm xác suất của b, e, a, cộng j và cộng m. Ta sẽ làm vậy với mỗi giá trị của e và a.
And we're going to have to sum them. OK. Because those are variables we introduced. That's how marginalization works.
Và phải lấy tổng chúng. OK. Vì đó là các biến ta đã đưa vào. Marginalization hoạt động như vậy.
And this capital letter means we're going to keep a vector around. That means we're going to be doing sort of vector math.
Còn chữ in hoa này nghĩa là ta giữ nguyên cả một vectơ. Tức là ta sẽ làm toán trên vectơ.
We're going to be doing this exact same computation once for plus b, and once for minus b. In general, we're going to be doing the exact same computation for every value in the domain.
Ta sẽ thực hiện đúng một phép tính đó một lần cho cộng b, và một lần cho trừ b. Nói chung, ta sẽ thực hiện đúng một phép tính cho mọi giá trị trong miền giá trị.
So when you see capital letters involved in these, it means vector math. Means that same operation's happening for each value in the domain. All right. So conditional quantity I wanted.
Nên khi bạn thấy chữ in hoa trong các biểu thức này, nghĩa là toán vectơ. Nghĩa là cùng một phép toán được thực hiện cho mỗi giá trị trong miền giá trị. Được rồi. Đây là đại lượng có điều kiện tôi muốn.
Joint quantity I wanted. This is a full entry from the joint distribution which, in principle, the Bayes' Net gives me. This is the rewriting of that according to the Bayes' Net reconstitution formula.
Đây là đại lượng đồng thời tôi muốn. Đây là một mục đầy đủ của phân phối đồng thời, mà về nguyên tắc, mạng Bayes cho tôi. Đây là cách viết lại nó theo công thức tái tạo của mạng Bayes.
This is the chain rule as it applies to this Bayes' Net. So it's not the full chain rule, it's just the multiplying together of the conditional probabilities of this Bayes' Net.
Đây là quy tắc chuỗi áp dụng cho mạng Bayes này. Không phải quy tắc chuỗi đầy đủ, mà chỉ là nhân các xác suất có điều kiện với nhau của mạng Bayes này.
All right. What's that? That bottoms out in taking a whole bunch of individual probabilities and multiplying them together in a bunch ways and adding them.
Được rồi. Vậy nó là gì? Rốt cuộc là lấy cả một loạt xác suất riêng lẻ rồi nhân chúng với nhau theo nhiều cách và cộng lại.
Don't stare at that too hard or your eyes will roll out of your head. OK. Get the idea?
Đừng nhìn chằm chằm quá, kẻo mắt lọt ra ngoài đấy. OK. Hiểu ý chưa?
All right. Great. So we have our algorithm. Here's why we don't use that algorithm.
Được rồi. Tuyệt. Vậy ta đã có thuật toán. Và đây là lý do ta không dùng nó.
Here's a, you know, by modern standards, what's the technical term? Extremely tiny network.
Đây là một, theo chuẩn hiện đại, thuật ngữ kỹ thuật là gì nhỉ? Một mạng cực kỳ nhỏ.
But even in this network, if I wanted to know something like, hey, what is the probability that you have — I don't know — an extra car given — here is your driving history and your age.
Nhưng ngay cả với mạng này, nếu tôi muốn biết, ví dụ, xác suất bạn có thêm một chiếc xe là bao nhiêu, cho trước lịch sử lái xe và độ tuổi của bạn.
OK. I observed two variables. Great. I'm interested in one variable.
OK. Tôi quan sát hai biến. Tốt. Tôi quan tâm đến một biến.
Great. And the other 24, or whatever, are hidden variables.
Tốt. Và 24 biến còn lại, hay bao nhiêu đó, là biến ẩn.
So when I do that same formula — formula, I'll be like, oh, I'm computing probabilities of, what is it, extra car given, you know, some particular value of the age, and some particular value of the driving history.
Vậy khi áp dụng cùng công thức đó, tôi sẽ phải tính các xác suất của, gì nhỉ, extra car, khi cho trước một giá trị cụ thể nào đó của tuổi, và một giá trị cụ thể nào đó của lịch sử lái xe.
And I don't know that, so I'm going to get the joint probability instead of e and h and a. But I don't know that. But I know how to do that.
Mà tôi không biết các giá trị đó, nên tôi sẽ tính xác suất đồng thời của e, h và a. Nhưng tôi cũng không biết cái đó. Nhưng tôi biết cách tính nó.
It's going to be a sum over, like, the whole rest of the network, p of e, h, a, lots of things.
Đó sẽ là một tổng trên toàn bộ phần còn lại của mạng, p của e, h, a, và nhiều thứ khác.
And so because we're summing over lots of things, this is going to be an exponential time thing and we can just go get lunch while it runs. OK.
Và vì ta lấy tổng trên rất nhiều thứ, việc này sẽ tốn thời gian theo hàm mũ, nên ta cứ đi ăn trưa trong lúc nó chạy. OK.
So already in this tiny, tiny network, it's bad news to do this in an exhaustive way. All right. So why is this so slow?
Vậy là ngay trong một mạng rất rất nhỏ, làm theo kiểu vét cạn thế này là tin xấu. Được rồi. Vậy tại sao nó chậm thế?
The reason it's so slow is somebody was nice enough to give you this conceptually giant network in tiny little pieces. Right. So these tiny little pieces multiplied together to find this exponentially large thing.
Lý do là có người tốt bụng đưa cho bạn một mạng khổng lồ về mặt khái niệm dưới dạng những mảnh nhỏ xíu. Đúng không. Những mảnh nhỏ xíu này được nhân với nhau để ra một thứ lớn theo hàm mũ.
And they have this warning on them, which is like, do not multiply us together to form the exponentially large thing. So what did we do?
Và chúng như có lời cảnh báo kiểu, đừng nhân chúng lại với nhau để tạo ra một thứ lớn theo hàm mũ. Vậy ta đã làm gì?
Step one, multiply them together to form the exponentially large thing. And then once we get the whole thing, what's the first thing we do?
Bước một, nhân chúng lại để tạo ra thứ lớn theo hàm mũ đó. Rồi khi có cả cục đó rồi, việc đầu tiên ta làm là gì?
We collapse out all of those dimensions we don't care about so they'll get small again. Maybe we should not inflate the whole thing before we start deflating it.
Ta thu gọn tất cả những chiều mà ta không quan tâm để nó nhỏ lại. Có lẽ ta không nên thổi phồng cả cục trước khi xả hơi nó.
And so a variable elimination is going to be is instead of joining up the whole joint distribution and then summing things out, we're just going to interleave those things.
Và khử biến sẽ là thay vì ghép toàn bộ phân phối đồng thời rồi mới lấy tổng, ta sẽ xen kẽ các bước đó.
So we're going to join some variable, and then immediately sum it out, and then join the next variable and sum that out. And so we control that growth.
Ta ghép một biến, rồi lấy tổng loại nó ngay, rồi ghép biến kế tiếp và lấy tổng loại nó. Nhờ vậy ta kiểm soát được sự phình to.
And you say, why does that really matter if you're going to do 10 joins, and then 10 sums, why is it worked to interleave them?
Bạn sẽ hỏi, điều đó có quan trọng gì nếu ta làm 10 phép ghép rồi 10 phép tổng, sao xen kẽ lại hiệu quả hơn?
The reason it's good to interleave them is because when we let that network grow, it grows exponentially. So if you join 10 times, things are growing sort of exponentially.
Lý do xen kẽ là tốt là vì khi ta để mạng phình ra, nó phình theo hàm mũ. Nên nếu ghép 10 lần, mọi thứ lớn lên gần như theo hàm mũ.
And then by the time you sum them out, it's sort of too late.
Đến lúc ta lấy tổng loại bớt thì đã quá muộn.
Whereas, if we catch those joints early, and sum out hidden variables as soon as we legally can according to the laws of probability and the conditional independence assumptions we have available, then we can avoid that exponential blowout.
Còn nếu ta bắt các phép ghép sớm, và lấy tổng loại các biến ẩn ngay khi có thể một cách hợp lệ theo các quy luật xác suất và các giả định độc lập có điều kiện mà ta có, thì ta tránh được sự bùng nổ theo hàm mũ.
OK. So we're going to interleave joining and marginalizing things. This is called variable elimination. It's still NP-hard, but it's usually much, much faster.
OK. Vậy ta sẽ xen kẽ việc ghép và lấy biên các thứ. Đây gọi là khử biến. Nó vẫn là NP-hard, nhưng thường nhanh hơn rất nhiều.
And for certain kinds of graft structures, it's in fact efficient, and sometimes even polynomial. All right. So he need some notation — some notation.
Và với một số loại cấu trúc đồ thị, nó thực sự hiệu quả, thậm chí đôi khi là đa thức. Được rồi. Vậy ta cần một ít ký hiệu.
The notation we're about to get is what are called factors. You already seen the basic types, but there's sort of a whole zoo. There's like a menagerie.
Ký hiệu sắp tới là cái gọi là các factor. Các bạn đã thấy những loại cơ bản, nhưng thực ra có cả một sở thú. Như một bầy muông thú đủ loại.
There's simple factors, like joint probabilities and conditional probabilities. And then there's the weird stuff. I'm not even going to show you all the weird stuff.
Có những factor đơn giản, như xác suất đồng thời và xác suất có điều kiện. Và rồi có những thứ kỳ quặc. Tôi thậm chí sẽ không cho bạn xem hết những thứ kỳ quặc.
When this algorithm runs, it's taking little pieces of network and multiplying them together and summing out variables.
Khi thuật toán này chạy, nó lấy các mảnh nhỏ của mạng nhân chúng với nhau và lấy tổng loại các biến.
And what you're left with is often something like weird hybrid of a joint probability and a conditional probability. Let's take a look at what you can get, and build up some intuition.
Và thứ còn lại thường là một dạng lai kỳ lạ giữa xác suất đồng thời và xác suất có điều kiện. Hãy xem ta có thể gặp những gì, và xây dựng chút trực giác.
But just know that if you do this on a big network, the intermediate stages can be hard to think about. All right. So the factor zoo. Let's see what's in our factor zoo.
Nhưng hãy biết rằng nếu làm trên mạng lớn, các giai đoạn trung gian có thể khó hình dung. Được rồi. Vậy là sở thú factor. Xem sở thú factor của ta có gì.
There's the relatively innocuous stuff, like, you know what a joint distribution is. What is p of x and y? Well, it looks like this.
Có những thứ tương đối vô hại, như phân phối đồng thời, bạn biết nó là gì rồi. p của x và y là gì? Nó trông như thế này.
It contains a probability for each value of x and y. When you sum it up, it sums to 1, because it is a joint distribution over those two variables.
Nó chứa một xác suất cho mỗi giá trị của x và y. Cộng lại thì bằng 1, vì nó là phân phối đồng thời trên hai biến đó.
And it's just a sort of enumeration of all of the cross product of their domains. OK. So in this case, what's the probability of hot and sun? It's 0.4.
Và nó chỉ là sự liệt kê toàn bộ tích Descartes của các miền giá trị. OK. Ở đây, xác suất của hot và sun là bao nhiêu? Là 0.4.
Great. We know about joint distributions.
Tốt. Ta đã biết về phân phối đồng thời.
Often, we are selecting rows of a joint distribution. Like, for example, somebody tells you, oh, hey, it's sunny.
Thường ta chọn ra một số hàng của phân phối đồng thời. Ví dụ, có người nói với bạn, này, trời nắng.
And so I might say, all right, it's sunny, let's knock out all the rows that do not correspond to sunny.
Thế là tôi nói, được rồi, trời nắng, hãy loại bỏ mọi hàng không ứng với trời nắng.
Once I've knocked out rows, I structurally still kind of — I semantically have the same thing. I still have entries of a joint distribution.
Sau khi loại hàng, về cấu trúc thì ta vẫn, về ngữ nghĩa thì vẫn là cùng một thứ. Vẫn là các phần tử của một phân phối đồng thời.
They didn't like become a conditional probability or anything, but the dimensionality got reduced. Right. Because on that one axis, in this case, that axis of sun, it's no longer all values.
Chúng không biến thành xác suất có điều kiện hay gì cả, nhưng số chiều đã giảm đi. Đúng không. Vì trên trục đó, ở đây là trục sun, nó không còn là mọi giá trị nữa.
It's just the one. OK. This is called a selected joint. You can think of it as a slice of a joint distribution.
Mà chỉ còn một giá trị. OK. Cái này gọi là selected joint. Bạn có thể xem nó như một lát cắt của phân phối đồng thời.
There are still probabilities of x, y. But now x is fixed and y still ranges. This doesn't sum to 1.
Chúng vẫn là các xác suất của x, y. Nhưng bây giờ x đã cố định còn y vẫn chạy qua mọi giá trị. Cái này không có tổng bằng 1.
So if I look over here and I sum these things together, it's going to sum to probability of sun. OK. So it's going to sum to the probability of what you selected.
Nếu tôi nhìn ở đây và cộng các giá trị này lại, tổng sẽ bằng xác suất của sun. OK. Tức là tổng sẽ bằng xác suất của cái mà bạn đã chọn.
So there's a probability of cold, comma, w. You knock out everything that doesn't correspond to cold, and you're left with a slice of the joint distribution. OK.
Vậy có xác suất của cold, w. Bạn loại bỏ mọi thứ không ứng với cold, và còn lại một lát cắt của phân phối đồng thời. OK.
This is actually an important point to stop and think about the difference between what the numbers mean. Right.
Đây là điểm quan trọng, đáng dừng lại suy nghĩ về sự khác nhau giữa ý nghĩa của các con số. Đúng không.
These are still joint probabilities over T and W. 0.2 is still the joint probability of cold and sun.
Đây vẫn là các xác suất đồng thời trên T và W. 0.2 vẫn là xác suất đồng thời của cold và sun.
But as a data structure, it went from being a two-dimensional array to a one-dimensional array, because I picked a value for one of those dimensions.
Nhưng xét như một cấu trúc dữ liệu, nó đã chuyển từ mảng hai chiều thành mảng một chiều, vì tôi đã chọn một giá trị cho một trong các chiều đó.
How do I know what this is as an array, as a data structure? Capital letters indicate dimensions of the array. So T, comma, W, in caps is a two-dimensional object, like what's shown here.
Làm sao biết nó là mảng nào, cấu trúc dữ liệu nào? Chữ in hoa cho biết các chiều của mảng. Vậy T, W viết hoa là đối tượng hai chiều, như cái đang hiển thị ở đây.
Cold, comma, W. Well, there's only one capital random variable whose value has not been fixed. That's now a one-dimensional object.
Cold, W. Chỉ có một biến ngẫu nhiên viết hoa mà giá trị chưa được cố định. Giờ nó là đối tượng một chiều.
And if I go to cold, comma, sun, it's still a joint probability, but now it's a one-dimensional object as a scalar. OK. That's important.
Còn cold, sun thì vẫn là xác suất đồng thời, nhưng giờ là đối tượng không chiều, một số vô hướng. OK. Điều này quan trọng.
We can reduce the size of the data structure without changing the semantics of what's in it. OK.
Ta có thể giảm kích thước của cấu trúc dữ liệu mà không đổi ngữ nghĩa của những gì bên trong. OK.
You want to know what changes the semantics of what's in it from a conditional probability to a joint probability? That's the laws of probability.
Vậy cái gì làm đổi ngữ nghĩa của nó từ xác suất có điều kiện sang xác suất đồng thời? Đó là các luật xác suất.
You multiply things together and you cross things off according to the product rule or the chain rule. All right. Number of capitals is dimensionality of the table. All right.
Bạn nhân các thứ với nhau và gạch bỏ bớt theo quy tắc nhân hay quy tắc chuỗi. Được rồi. Số chữ in hoa là số chiều của bảng. Được rồi.
Here is a relatively harmless thing from our zoo that you've seen before. This is a conditional probability.
Đây là một thứ tương đối vô hại trong vườn thú của ta mà các bạn đã thấy. Đây là một xác suất có điều kiện.
This is the conditional probability distribution over Y. See, Y is a capital, so as a data structure, this is a vector over all the values of Y.
Đây là phân phối có điều kiện trên Y. Y viết hoa, nên xét như cấu trúc dữ liệu, đây là một vectơ trên mọi giá trị của Y.
This is the probability of Y taking on its various values, given the evidence x. Each entry in this is a conditional probability of Y given x.
Đây là xác suất Y nhận các giá trị khác nhau, khi biết bằng chứng x. Mỗi phần tử ở đây là một xác suất có điều kiện của Y khi biết x.
They all have the same x, but they have different Y. If I sum this up, what am I going to get?
Chúng có cùng x nhưng khác Y. Nếu tôi cộng lại, sẽ được bao nhiêu?
Well, it's a distribution over Y. If I sum up all the values, it's going to sum to 1. It is a probability distribution over Y, for the condition x takes on some particular value.
Đây là phân phối trên Y. Cộng mọi giá trị lại thì được 1. Nó là phân phối xác suất trên Y, với điều kiện x nhận một giá trị cụ thể nào đó.
All right. That's great. We know about conditional distributions. They look something like this.
Được rồi. Tuyệt. Ta đã biết về các phân phối có điều kiện. Chúng trông như thế này.
This is the distribution over w given T is cold. And so there's a value for each element in the domain of w here, and these things sum to 1.
Đây là phân phối của w khi biết T là cold. Có một giá trị cho mỗi phần tử trong miền của w ở đây, và chúng có tổng bằng 1.
All right. You can also get a family of conditionals. This isn't too weird, but it's a little weird. This is distributions over Y, but it's one for every value of x.
Được rồi. Bạn cũng có thể có một họ các phân phối có điều kiện. Cái này không quá lạ, nhưng hơi lạ. Đây là các phân phối trên Y, nhưng mỗi giá trị của x có một phân phối.
So it's like you've taken p of Y given this x, and p of Y given x, and you've glued them together. It's a two-dimensional data structure.
Giống như bạn lấy p của Y khi biết x này, và p của Y khi biết x kia, rồi ghép chúng lại. Đó là cấu trúc dữ liệu hai chiều.
It's got a value for every value of x and every value for Y.
Nó có một giá trị cho mỗi giá trị của x và mỗi giá trị của Y.
And everything in there is p of Y given x for some x and some Y. If you add them up, each little distribution over Y adds — adds up to 1, and there are x many of them, so this whole thing together now sums to more than 1.
Và mọi thứ trong đó là p của Y khi biết x, với một x nào đó và một Y nào đó. Nếu cộng lại, mỗi phân phối nhỏ trên Y có tổng bằng 1, và có nhiều phân phối như thế bằng số giá trị x, nên toàn bộ cái này cộng lại lớn hơn 1.
That's weird. OK. So we'll look at them through the glass. This is getting a little weird.
Lạ nhỉ. OK. Ta sẽ xem chúng qua một tấm kính. Càng lúc càng hơi lạ.
Here's what it looks like when you see a probability of say, w given T. You look at it, it looks two-dimensional just like w comma T, but if you peek a little closer, you'll see that for each fixed value of T, like these ones, we get a distribution over w.
Đây là hình dạng khi bạn thấy xác suất của, chẳng hạn, w khi biết T. Nhìn vào thì nó có vẻ hai chiều giống hệt w, T, nhưng nếu nhìn kỹ hơn, bạn sẽ thấy với mỗi giá trị cố định của T, như những dòng này, ta có một phân phối trên w.
Here's another distribution over w. They've just bolted together. It's a two-dimensional object. It's got variables for w and T.
Đây là một phân phối khác trên w. Chúng chỉ được ghép lại với nhau. Đó là đối tượng hai chiều. Nó có các biến w và T.
All right. Now, we get to the weird stuff. OK. You'll end up things like specified families.
Được rồi. Giờ ta đến phần lạ. OK. Bạn sẽ gặp những thứ như các họ được chỉ định.
What does it mean when I hand you something and I say, oh, what's in here is the probability of a fixed value of lower case y, like the probability of rain.
Khi tôi đưa bạn một thứ và nói, trong này là xác suất của một giá trị y viết thường cố định, như xác suất mưa.
And then it's giving capital X. That means there's going to be an entry for every value of capital X. So this is a whole bunch of probability of rains, for example.
Và nó cho khi biết X viết hoa. Nghĩa là sẽ có một phần tử cho mỗi giá trị của X viết hoa. Vậy đây là cả loạt xác suất mưa chẳng hạn. .
So here's an example. This is a probability of rain. When it's hot, there's a probability of rain. When it's cold, what happens when you sum them up?
Đây là một ví dụ. Đây là xác suất mưa. Khi trời nóng, có một xác suất mưa. Khi trời lạnh, cộng lại thì sao?
It's not a distribution over rain and sun, it's a bunch of probabilities of rains. And so when you add them up, you get to — no one knows.
Nó không phải phân phối trên rain và sun, mà là một loạt xác suất mưa. Nên khi cộng lại, bạn được không ai biết.
They could be all zero, they could be all 1, just depends on what those conditional probabilities are. This is no longer a distribution. It's no longer a family of distributions.
Có thể toàn bằng 0, có thể toàn bằng 1, tùy vào các xác suất có điều kiện đó là gì. Đây không còn là một phân phối. Cũng không còn là một họ các phân phối.
It is a one-dimensional array, because there's an entry for every value of x. But each of those entries is the conditional probability of some particular value of Y, which is usually an evidence value.
Nó là mảng một chiều, vì có một phần tử cho mỗi giá trị của x. Nhưng mỗi phần tử đó là xác suất có điều kiện của một giá trị cụ thể nào đó của Y, mà thường là một giá trị bằng chứng.
OK. So that's weird. You'll see those two. OK.
OK. Nghe hơi lạ nhỉ. Các em sẽ gặp cả hai loại này. OK.
How do we get these things? We get these things because somebody hands us little pieces of Bayes' Net.
Làm sao để có được những thứ này? Ta có chúng vì có người đưa cho ta những mảnh nhỏ của mạng Bayes.
We're going to be selecting the value of the evidence, wherever it is on the conditioning bar, could be on the left or the right. And then we're going to start multiplying things together.
Ta sẽ chọn giá trị của bằng chứng, dù nó nằm ở đâu quanh dấu điều kiện, bên trái hay bên phải đều được. Rồi ta bắt đầu nhân chúng lại với nhau.
So we're going to get all kinds of stuff.
Nên ta sẽ có đủ loại thứ.
Any questions?
Có câu hỏi nào không?
All right. So, in general, we're going to be writing things that look like this. We're going to be writing conditional probabilities of some number of variables, possibly zero.
Được rồi. Vậy nhìn chung, ta sẽ viết những thứ có dạng thế này. Ta sẽ viết các xác suất có điều kiện của một số biến nào đó, có thể là không biến nào.
It's not going to happen today. Don't let it freak you out. Given some number of other variables, possibly zero, that happens all the time, those are marginal probabilities.
Hôm nay thì không xảy ra đâu. Đừng để nó làm các em hoảng. Cho một số biến khác, cũng có thể là không biến nào, trường hợp này xảy ra suốt, đó là các xác suất biên.
This is what's called a factor.
Cái này gọi là một factor.
It's always going to be data structure wise a multidimensional array where every capital letter is going to indicate a dimension of the array, and we're going to have the whole cross product of all of those entries.
Về mặt cấu trúc dữ liệu, nó luôn là một mảng nhiều chiều, mỗi chữ cái viết hoa cho biết một chiều của mảng, và ta có toàn bộ tích Descartes của các mục đó.
The values in this factor are always going to be specific values of probabilities of the stuff to the left of the conditioning bar, given the evidence to the right.
Các giá trị trong factor này luôn là các giá trị xác suất cụ thể của những gì bên trái dấu điều kiện, cho bằng chứng bên phải.
Anything that's assigned, meaning we write it with lowercase, is a dimension that's missing, or selected, from this array.
Cái gì đã được gán, tức là ta viết bằng chữ thường, thì là một chiều bị bỏ đi, hay được chọn, khỏi mảng này.
So we're going to have all kinds of factors, and we're going to generate them sort of algebraically as we go.
Vậy ta sẽ có đủ loại factor, và ta sẽ tạo ra chúng bằng đại số khi đi tiếp.
All right. Let's do a specific example now that we have our factor zoo. So this is a tiny example.
Được rồi. Giờ có bộ sưu tập factor rồi, ta làm một ví dụ cụ thể. Đây là một ví dụ nhỏ.
This example is so small that it's actually fine to just build out the full joint distribution or resist. So the random variables are, is it raining or not?
Nhỏ đến mức ta có thể dựng cả phân phối đồng thời cũng không sao. Các biến ngẫu nhiên: trời có mưa hay không?
Boolean random variable. T, is there traffic or not? Boolean random variable. L, am I late for class or not, which I nearly was today.
Biến ngẫu nhiên Boolean. T, có kẹt xe hay không? Biến ngẫu nhiên Boolean. L, tôi có trễ học không, mà hôm nay suýt trễ thật.
Boolean variable. OK. What's living in my Bayes' Net? Well, I have p of r, because it doesn't have any parents.
Biến Boolean. OK. Mạng Bayes của tôi có gì? Có p của r, vì nó không có nút cha.
And, it says, 10% of the time it rains. OK. What's under t? This encodes the probability of traffic given yes rain, and given no rain.
Nó nói 10% thời gian trời mưa. OK. Dưới t có gì? Nó mã hóa xác suất kẹt xe khi có mưa và khi không mưa.
So in fact, this is a family of conditional distributions. I eyeball it.
Thực ra đây là một họ các phân phối có điều kiện. Nhìn qua là thấy.
I see it adds up to 2, because there are, in fact, two distributions over t, one for plus r, one for minus r. You can see it's a two-dimensional data structure.
Tổng bằng 2, vì thực tế có hai phân phối trên t, một cho cộng r, một cho trừ r. Các em thấy đây là cấu trúc dữ liệu hai chiều.
They're all conditional probabilities of t given r. Same thing under l. There's a bunch of conditional probabilities given the parents. OK.
Tất cả đều là xác suất có điều kiện của t cho r. Dưới l cũng vậy. Có một loạt xác suất có điều kiện cho các nút cha. OK.
Here's distribution over l given plus t, given minus 2. OK. Let's say somebody comes to me and said, I'm intensely interested in the probability distribution over l.
Đây là phân phối trên l cho cộng t, cho trừ t. OK. Giả sử có người đến hỏi tôi, tôi rất quan tâm đến phân phối xác suất trên l.
That is, forget this raining and stuff, how often are you late for class?
Tức là bỏ chuyện mưa gió đi, thầy trễ học thường xuyên không?
And I say, well, that's annoying, because if you had asked me how often it rains, I have that answer at my fingertips.
Và tôi nói, phiền thật, vì nếu em hỏi trời mưa thường xuyên không, tôi có sẵn câu trả lời ngay.
This answer of p of l I need to compute from what I know. It's not just sitting in there. I can tell you probability I'm late when there's traffic.
Còn p của l thì tôi phải tính từ những gì đã biết. Nó không nằm sẵn đó. Tôi nói được xác suất trễ khi có kẹt xe.
But in order to tell you the overall probability, I sort of need to know how often traffic is, but I don't have that, either, so I need to sort of combine that with rain.
Nhưng để nói xác suất tổng thể, tôi cần biết kẹt xe thường xuyên cỡ nào, mà cái đó cũng không có, nên phải kết hợp với mưa.
And that's what the Bayes' Net mathematics lets you do.
Và đó là điều toán học của mạng Bayes cho phép làm.
So I could look at this and I could be like, well, because this is just a distribution over these variables, I can always write this. This is introducing a variable and summing it out.
Tôi có thể nhìn và nghĩ, vì đây chỉ là phân phối trên các biến này, nên tôi luôn viết được thế này. Đây là đưa thêm một biến vào rồi lấy tổng để loại nó.
The probability distribution over l is just the sum over all the values of r and t of the probability distribution over RT and l. OK.
Phân phối xác suất trên l chính là tổng trên mọi giá trị của r và t của phân phối xác suất trên R, T và l. OK.
I just introduced some variables, but I'm collapsing them out. So that's law of marginalization here. Now, I don't actually know that, either. That's an entry of the joint.
Tôi vừa đưa vào vài biến, nhưng rồi gộp chúng lại. Đó là luật biên hóa ở đây. Nhưng cái này tôi cũng chưa biết. Đó là một mục của phân phối đồng thời.
But because it's a Bayes' Net, I can break that down into a product of things I do know. I do know p of r, because it's sitting there under r.
Nhưng vì là mạng Bayes, tôi có thể tách nó thành tích của những thứ tôi đã biết. Tôi biết p của r, vì nó nằm sẵn dưới r.
And I do know t of — t given r. It's sitting there under t. And I do know l given t. OK.
Và tôi biết t của — t cho r. Nó nằm sẵn dưới t. Và tôi biết l cho t. OK.
All right. So inference by enumeration, which you already know. We're going to see it again through the lens of factors, which will let us get to variable elimination.
Được rồi. Đây là suy luận bằng liệt kê, các em đã biết. Ta sẽ xem lại nó qua lăng kính factor, từ đó dẫn đến khử biến.
All right. We're going to track these factors from our zoo. The initial factors, the givens, are going to be conditional probability tables. OK.
Được rồi. Ta sẽ theo dõi các factor từ bộ sưu tập này. Các factor ban đầu, tức dữ kiện cho trước, là các bảng xác suất có điều kiện. OK.
You get one per node.
Mỗi nút có một bảng.
And if I have some node sitting here in my network that's called a and it's got a parent called b, and another parent called c, my initial factors are going to look like P of A given B and C.
Và nếu trong mạng có một nút tên là a với một nút cha là b, và một nút cha khác là c, các factor ban đầu của tôi là sẽ có dạng P của A given B và C.
OK. So the network structure gives me my initial factors. And so for the computation of p of l in that little lateness network, these are my initial factors.
OK. Vậy cấu trúc mạng cho ta các factor ban đầu. Và để tính p của L trong mạng đi trễ nhỏ này, đây là các factor ban đầu của chúng ta.
You see, that's just the Bayes' Net. That is just the Bayes' Net. OK. All right.
Các em thấy đấy, đó chính là mạng Bayes. Chính là mạng Bayes. OK. Được rồi.
Step one. Just like our original inference by enumeration, we have to select values that match the evidence.
Bước một. Giống như suy luận bằng liệt kê ban đầu, ta phải chọn các giá trị khớp với bằng chứng.
So let's say we're going to do a query, and I'm going to say something like, maybe, what's the probability that it's raining given that I am late?
Giả sử ta thực hiện một truy vấn, và tôi nói kiểu như, xác suất trời đang mưa là bao nhiêu, biết rằng tôi bị trễ?
Well, if we know l is plus l, then the initial factors are going to be smaller. p of r doesn't change, because it's all sort of valid for plus l and minus l.
Nếu ta biết l là +l thì các factor ban đầu sẽ nhỏ đi. p của r không đổi, vì nó hợp lệ cho cả +l và -l.
But all the entries that actually mention l in them get paired down to just the amount that is consistent. Now, conceptually, I had this whole giant joint distribution.
Nhưng mọi mục có nhắc đến l được thu gọn chỉ còn phần phù hợp. Về mặt khái niệm, ta có phân phối đồng thời khổng lồ này.
And, conceptually, I just knocked out half the rows. I knocked out all of the minus l rows. But to my Bayes' Net, I sort of knocked them out locally.
Và về mặt khái niệm, ta vừa loại bỏ một nửa số hàng. Ta loại bỏ tất cả các hàng -l. Nhưng với mạng Bayes, ta loại bỏ chúng một cách cục bộ.
But the consequence is if I inflated the whole thing, half of the network would be gone now. OK. All right. So inference by enumeration.
Hệ quả là nếu ta khai triển toàn bộ ra, một nửa mạng đã biến mất. OK. Được rồi. Vậy suy luận bằng liệt kê.
Initial factors are local conditional probability tables, one per node. Any known values are selected. That's your evidence. Join all your factors, whatever that means.
Các factor ban đầu là các bảng xác suất có điều kiện cục bộ, mỗi nút một bảng. Các giá trị đã biết được chọn ra. Đó là bằng chứng của các em. Join tất cả các factor, dù điều đó nghĩa là gì.
Eliminate all your hidden variables. We know what that means, it means sum them out, and then normalize what's left over. So operation one. What does it mean to join factors?
Khử tất cả các biến ẩn. Ta biết nghĩa là gì, là lấy tổng loại chúng đi, rồi chuẩn hóa phần còn lại. Vậy phép toán một. Join các factor nghĩa là gì?
I've got all these little pieces. So I got factors, and I need to merge them together. But I don't just want to like multiply everything together. That would give me the whole Bayes' Net.
Ta có nhiều mảnh nhỏ này. Ta có các factor và cần gộp chúng lại. Nhưng ta không muốn cứ nhân hết mọi thứ với nhau. Làm vậy sẽ ra cả mạng Bayes.
So we need an operation for joining a selected set of factors. It's sort of just like a database join. OK.
Nên ta cần một phép toán để join một tập factor được chọn. Nó khá giống phép join trong cơ sở dữ liệu. OK.
So in a database join, you've got some table, and it sort of talks about A and B. And then you got some other table that talks about A and C.
Trong phép join cơ sở dữ liệu, ta có một bảng, nói về A và B. Rồi một bảng khác nói về A và C.
And you join them together. And what do you have now? You've got this big table that talks about A and B and C, except now it's big.
Và ta join chúng lại. Giờ ta có gì? Một bảng lớn nói về A, B và C, chỉ là giờ nó lớn hơn.
I guess it depends what join you do. OK. So this is like a database join. We're going to — and what happens when we join, we talk about joining factors.
Tôi đoán còn tùy loại join nào. OK. Vậy nó giống một phép join cơ sở dữ liệu. Ta sẽ... và điều gì xảy ra khi join, ta nói về việc join các factor.
In particular, we talked about — we talk about joining on a variable. So maybe we'll join on a variable x. We get all the factors that mention that variable.
Cụ thể, ta nói về join theo một biến. Giả sử join theo biến x. Ta lấy tất cả factor nhắc đến biến đó.
If you leave one out, weird things will happen. Don't do it. So if somebody says join the factors on x, I sum unto me all of the factors that mention x.
Nếu bỏ sót một cái, những chuyện kỳ quặc sẽ xảy ra. Đừng làm vậy. Nên nếu ai đó bảo join các factor theo x, tôi triệu hồi tất cả factor có nhắc đến x.
Some will mention it on the condition side of the bar, and exactly one will mention it on the left-hand side of the bar. And that's whatever was living under x to begin with.
Một số nhắc đến nó ở phía điều kiện của dấu gạch, và đúng một factor nhắc đến nó ở vế trái của dấu gạch. Đó là cái vốn nằm dưới x ngay từ đầu.
So we summon all the factors that mention our magic variable. We build a new factor over the union of the variables involved. So let's do an example of that.
Vậy ta triệu hồi tất cả factor nhắc đến biến thần kỳ của ta. Ta xây một factor mới trên hợp của các biến liên quan. Hãy làm một ví dụ.
Let's say I would like to take my little r, t and l Bayes' Net over raining, traffic and lateness, and I want to join on the variable r.
Giả sử tôi muốn lấy mạng Bayes nhỏ r, t và l về mưa, kẹt xe và đi trễ, và tôi muốn join theo biến r.
Step one, I gather all of the variables that mention r. What mentions r? p of r. Great. And p of t given r.
Bước một, gom tất cả factor nhắc đến r. Cái gì nhắc đến r? p của r. Tốt. Và p của t given r.
And if r had other children, they would mention r, too, and we'd join — we'd summon them, too. But at the moment we just get these two. What does it mean to join?
Nếu r có các con khác, chúng cũng nhắc đến r, và ta cũng triệu hồi chúng. Nhưng lúc này ta chỉ có hai cái này. Join nghĩa là gì?
It means we create a new — we create a new array that's going to represent the product of these things, whose dimensionality is the union of all these variables.
Nghĩa là ta tạo một mảng mới biểu diễn tích của những thứ này, với số chiều là hợp của tất cả các biến này. có số chiều là hợp của tất cả các biến này.
So in this case, the union isn't actually any bigger. And we'll end up with r, a, and t.
Trong trường hợp này, hợp không lớn hơn thực sự. Và ta có r và t.
And because we multiplied of p — t given r, or with a p of r, I know from the product rule that's going to be p of r comma t.
Và vì ta nhân p của t given r với p của r, từ quy tắc tích tôi biết nó sẽ là p của r phẩy t.
I don't have to know that to join variables. This is a mechanical operation.
Tôi không cần biết điều đó để join các biến. Đây là một phép toán cơ học.
But because I'm tracking what these things mean, and I know the laws of probability, I can infer that what's actually going to live here is going to be p of r comma t.
Nhưng vì tôi theo dõi ý nghĩa của chúng, và biết các luật xác suất, tôi có thể suy ra thứ thực sự nằm ở đây sẽ là p của r phẩy t.
But I can do the algorithm anyway without giving it a name. So what do I do?
Nhưng tôi vẫn chạy được thuật toán mà không cần đặt tên cho nó. Vậy ta làm gì?
For each entry of this new thing, which is still a two-dimensional array, it looks just like this one. Only the numbers are going to be different.
Với mỗi mục của cái mới này, vẫn là một mảng hai chiều, trông giống hệt cái này. Chỉ có các con số là khác.
For each element, I'm going to do a pointwise product. So, for example, in order to get the entry for minus r plus t, I'm going to get minus r — minus r plus t.
Với mỗi phần tử, ta lấy tích từng điểm. Ví dụ, để có mục cho -r +t, tôi lấy -r, -r +t.
I select everything that's relevant and I multiply them together. And I do that for every entry. It's a pointwise product. All right.
Tôi chọn mọi thứ liên quan và nhân chúng với nhau. Và làm vậy cho mọi mục. Đó là tích từng điểm. Được rồi.
That's what joining on a variable means.
Đó là ý nghĩa của join theo một biến.
We grab all of the factors that mention the variable, I create a possibly higher dimensional array to hold all of those variables, one per access, and then I do a pointwise product of everything relevant.
Ta lấy tất cả các factor có nhắc đến biến đó, tạo một mảng có thể có số chiều cao hơn để chứa tất cả các biến đó, mỗi biến một trục, rồi lấy tích từng điểm của mọi thứ liên quan.
Once I've done that, I sort of don't have a Bayes' Net with an r pointing to a t. I've sort of merged them together into one mega variable called r comma t.
Làm xong, ta coi như không còn một mạng Bayes với r trỏ tới t nữa. Ta đã gộp chúng lại với nhau thành một biến khổng lồ gọi là r phẩy t.
We've never seen that in our network, and we actually won't, except in this lecture, I'll draw that to evoke the fact that r and t have sort of been conflated by this joining process.
Ta chưa từng thấy điều đó trong mạng của mình, và thực ra sẽ không thấy, trừ bài giảng này, tôi vẽ ra để gợi ý rằng r và t đã bị nhập lại do quá trình join này.
All right. Let's do an example of multiple joins where we take all these little pieces and we stick them together and get something higher dimensional. All right.
Được rồi. Ta làm một ví dụ về nhiều phép join, nơi ta lấy các mảnh nhỏ này và ghép chúng lại để có một thứ nhiều chiều hơn. Được rồi.
So here is that network p of r. Raining causes traffic, traffic causes lateness. Here are the local probabilities involved. Let's go crazy joining things up.
Đây là mạng với p của r. Mưa gây ra kẹt xe, kẹt xe gây ra đi trễ. Đây là các xác suất cục bộ liên quan. Ta cứ thoải mái join các thứ lại.
So I can join on r. What's going to happen? I'm going to gather everything that mentions r. That's p of r and p of t given r.
Tôi join trên r. Chuyện gì sẽ xảy ra? Tôi gom mọi thứ có nhắc đến r. Đó là p của r và p của t với điều kiện r.
I'm going to get something that multiplies them together. So it's going to be p of — it's going to be something with t and r, because that's the union of the variables.
Tôi nhân chúng với nhau. Vậy nó sẽ là p của — một thứ có t và r, vì đó là hợp của các biến.
And we know it's going to be t comma r, because if you multiply a conditional by a marginal, the product rule here says you're going to get a joint probability.
Và ta biết nó sẽ là t phẩy r, vì nếu nhân một phân phối có điều kiện với một phân phối biên, thì quy tắc nhân cho thấy ta sẽ có một xác suất đồng thời.
So we already did that. We're still going to have this other factor. It is unchanged.
Cái này ta đã làm rồi. Ta vẫn còn factor kia. Nó không thay đổi.
It is not harmed in the joining of r, but there's this new factor r comma t that we saw before that we got on the last slide.
Nó không bị ảnh hưởng khi join trên r, nhưng có factor mới r phẩy t mà ta đã thấy ở slide trước.
I've taken one step away from the Bayes' Net and towards the joint distribution by collapsing together r and t. Let's go crazy. Let's join on t now. All right.
Tôi đã đi một bước rời khỏi mạng Bayes và tiến tới phân phối đồng thời bằng cách gộp r và t lại. Cứ tiếp tục nào. Giờ join trên t. Được rồi.
So if I join on t, I gather everything that mentions t. And, look, everything mentions t. When I do this, I'm going to get a new factor.
Join trên t thì tôi gom mọi thứ có nhắc đến t. Và này, cái nào cũng nhắc đến t. Làm vậy ta sẽ có một factor mới.
It's going to be a probability of something. It's going to have dimensions for r and t and l.
Nó là xác suất của một thứ gì đó. Nó có các chiều cho r, t và l.
And I know by sort of the chain rule here and what I'm multiplying together that, in fact, what I'm going to end up with is the probability of r and t and l.
Và nhờ quy tắc chuỗi và những gì đang nhân với nhau, ta biết kết quả sẽ là xác suất của r, t và l.
All right. What's it going to look like? It's going to be a three-dimensional array here, one for every value of r, every value of t, and every value of l.
Được rồi. Nó sẽ trông thế nào? Nó là một mảng ba chiều, mỗi giá trị của r, mỗi giá trị của t, và mỗi giá trị của l.
And for each element here, like, if I want plus r plus t minus l, I grab plus r plus t from here, and plus t minus l from here, and I multiply them together.
Với mỗi phần tử, chẳng hạn muốn +r +t -l, tôi lấy +r +t từ đây, và +t -l từ đây, rồi nhân chúng với nhau.
So, again, it's a pointwise product, and now we've made something bigger. In general, if you go crazy jointing stuff together, these tables get higher dimensional. And as you add dimensions, things grow exponentially fast.
Vậy lại là tích từng điểm, và giờ ta đã tạo ra thứ lớn hơn. Nói chung, nếu cứ join bừa các thứ lại, các bảng sẽ có số chiều ngày càng cao. Và khi thêm chiều, kích thước tăng theo hàm mũ rất nhanh.
OK. Which hopefully I've said enough times is not what we want.
OK. Hy vọng tôi đã nói đủ nhiều lần là ta không muốn vậy.
All right. So it's multiple joins.
Được rồi. Đó là nhiều phép join.
If you just go crazy and start joining on variables and pressing the join button like a — like a maniac, you're going to end up with the full joint distribution, and it's going to be big.
Nếu cứ join các biến một cách điên cuồng và bấm nút join như người cuồng loạn, bạn sẽ ra phân phối đồng thời đầy đủ, và nó sẽ rất lớn.
So how do we control this growth? We have something that basically doubles the size of things by joining them, or perhaps much worse.
Vậy làm sao kiểm soát sự phình to này? Join làm kích thước các thứ tăng gấp đôi, hoặc có khi tệ hơn nhiều.
We, also, have an operation which halves the size of things by eliminating a variable.
Ta cũng có một phép toán làm kích thước giảm một nửa bằng cách khử một biến.
This takes a larger dimensional object, and deletes one of the axes by collapsing everything on that axis and summing them together. So this is called marginalization. It's just like marginalizing from before.
Nó lấy một đối tượng nhiều chiều và xóa đi một trục bằng cách gộp mọi thứ trên trục đó và cộng chúng lại. Phép này gọi là lấy biên (marginalization). Giống như lấy biên trước đây.
It takes a factor and sums out a variable. So a factor becomes a smaller factor. This is a projection operation.
Nó lấy một factor và lấy tổng theo một biến. Vậy factor trở thành factor nhỏ hơn. Đây là một phép chiếu.
So, for example, if I have my factor over r and t — this is also just a joint distribution over r and t — and I want to get rid of a factor, I say, you know what?
Ví dụ, tôi có factor trên r và t — nó cũng chỉ là phân phối đồng thời trên r và t — và muốn bỏ một biến, tôi nói: thôi, tôi không quan tâm r.
I don't care about r. I just want to know the probability of traffic. And, I say, unfortunately, my network mentions it.
Tôi chỉ muốn biết xác suất kẹt xe. Tiếc là mạng của tôi lại nhắc đến nó.
I'd like my network to not mention it, so I sort of like — I can't just scribble it out, right, because there's going to be a bunch of Ts that collapse, and a bunch of Rs that collapse.
Tôi muốn mạng không nhắc đến nó, nên kiểu như — tôi không thể chỉ gạch bỏ nó, đúng không, vì sẽ có nhiều giá trị T bị gộp lại, và nhiều giá trị R bị gộp lại.
But if I scribbled it out, I would say, huh, I guess I got to put together those two plus Ts.
Nhưng nếu gạch bỏ, tôi sẽ nói, ừm, chắc phải gộp hai dòng +t lại.
And I guess I got to put together the two minus Ts that have now collapsed. And if you do that, you'll end up with a distribution over t, and it'll look like that.
Và chắc phải gộp hai dòng -t giờ đã trùng nhau. Làm vậy bạn sẽ có phân phối trên t, và nó trông như thế này.
So this two-dimensional thing became a one-dimensional thing. And where there was collapsing, I added things together. That's marginalization. And this is the thing that reduces the size of the objects that we're constructing.
Vậy thứ hai chiều này thành thứ một chiều. Chỗ nào bị gộp, tôi cộng các giá trị lại. Đó là lấy biên. Và đây là thứ làm giảm kích thước các đối tượng mà ta đang xây dựng.
So, in general, we're going to join, and then as soon as possible, we're going to marginalize everything we don't need that's legal to marginalize so that we can keep things small and controlled.
Nói chung, ta sẽ join, rồi càng sớm càng tốt, ta sẽ lấy biên mọi thứ không cần thiết mà được phép lấy biên, để giữ mọi thứ nhỏ gọn và dễ kiểm soát.
OK. So here's an example of multiple elimination. Here's a joint distribution over r, t and l. It's a three-dimensional object.
OK. Đây là ví dụ về khử nhiều biến. Đây là phân phối đồng thời trên r, t và l. Nó là một đối tượng ba chiều.
It's a joint distribution over three variables. Where'd it come from? We reconstituted it from a Bayes' Net from — but for the present purposes, it doesn't matter where it came from.
Nó là phân phối đồng thời trên ba biến. Nó từ đâu ra? Chúng ta dựng lại nó từ một mạng Bayes từ... nhưng với mục đích hiện tại, nó từ đâu ra không quan trọng.
OK. What can I do to this thing? Well, I can answer questions like, hey, what's plus r plus t plus l? OK.
OK. Ta có thể làm gì với nó? Ta có thể trả lời những câu hỏi như: xác suất của plus r plus t plus l là bao nhiêu? OK.
It's 0.024. Great. I can, also, start projecting things out. So I could sum out r.
Là 0.024. Tốt. Ta cũng có thể bắt đầu chiếu bớt các biến đi. Ví dụ ta lấy tổng theo r.
That basically means I get rid of this axis, and all the plus t plus l's that collapse get added together. And now I have something that's just two-dimensional, t and l.
Nghĩa là ta bỏ trục này đi, và các dòng plus t plus l bị gộp lại sẽ được cộng với nhau. Giờ ta có một thứ chỉ còn hai chiều, t và l.
Each one of these entries is backed by a whole bunch of things that also say plus t plus l, but used to vary over r and have now been collapsed.
Mỗi mục trong này được tạo thành từ cả loạt mục cũng có plus t plus l, nhưng trước đây thay đổi theo r và giờ đã bị gộp lại.
All right. That was summing out r. OK. We're going to pare it down.
Được rồi. Đó là lấy tổng theo r. OK. Giờ ta sẽ rút gọn thêm.
It's going to be brutal. We're going to sum out over t. What's left? Just going to have p of l left.
Sẽ khá tàn nhẫn đấy. Ta lấy tổng theo t. Còn lại gì? Chỉ còn p của l.
That's just a plus l and a minus l. And there you have it. My probability of lateness is 13.4% in this model. Hopefully, real statistics do not bear that out.
Chỉ có plus l và minus l. Và đây là kết quả. Xác suất bị trễ là 13.4% trong mô hình này. Hy vọng số liệu thực tế không như vậy.
OK. So we can join a bunch of things. We'll get the — in the limit we'll get the whole joint distribution.
OK. Vậy ta có thể kết hợp (join) nhiều thứ. Đến cùng ta sẽ có toàn bộ phân phối đồng thời.
We can sum out things from the joint distribution limit, we'll end up with just like one variable left. And it turns out that that's all you need to do inference by enumeration.
Ta có thể lấy tổng bỏ các biến khỏi phân phối đồng thời đó, cuối cùng chỉ còn lại một biến. Và hóa ra chỉ cần vậy là làm được suy luận bằng liệt kê.
Somebody gives you your conditional probabilities and your Bayes' Net, you select your evidence, you join, join, join, join, join, until you can join no more.
Ai đó đưa cho bạn các xác suất có điều kiện và mạng Bayes, bạn chọn bằng chứng, rồi join, join, join, join, join, đến khi không join được nữa.
And then you eliminate everything you don't care about, and then you normalize. That's it. And all variable elimination is going to do is interleave those op — those operations.
Sau đó loại bỏ mọi thứ bạn không quan tâm, rồi chuẩn hóa. Vậy thôi. Khử biến chỉ làm một việc là đan xen các phép toán đó.
OK. So variable elimination, and then we'll take our break for today. Variable elimination is simply marginalizing early and you say, I have a really good idea.
OK. Vậy là khử biến, rồi ta sẽ nghỉ giải lao. Khử biến đơn giản là lấy biên sớm và bạn nghĩ: mình có ý hay lắm.
I'm going to marginalize everything at the beginning just like project it all out. The problem is when — you can't actually marginalize things until there is only one factor that mentions them.
Mình sẽ lấy biên mọi thứ ngay từ đầu, chiếu bỏ hết. Vấn đề là bạn không thể lấy biên một biến cho đến khi chỉ còn một factor nhắc đến nó.
So if you sit down to your Bayes' Net and you see, oh, I've got like a p of a, and then I've got a p of b given a, and you're like, I'm going to marginalize out a.
Nếu bạn ngồi nhìn mạng Bayes và thấy có p của a, rồi p của b cho trước a, và bạn định lấy biên bỏ a.
OK. Like don't get too excited, you can't marginalize that out yet, because you haven't yet done the joining that's necessary to connect everything that a mediates. So here a influences b.
OK. Đừng vội, bạn chưa thể lấy biên bỏ a được, vì bạn chưa join để nối mọi thứ mà a liên quan. Ở đây a ảnh hưởng b.
You would have to join these together before you could marginalize it.
Bạn phải join chúng lại rồi mới lấy biên được.
If you had p of c given — well, given b and a, let's say, as well, you would have to join all of these on a before you could marginalize on a.
Nếu bạn còn p của c cho trước b và a chẳng hạn, bạn phải join tất cả theo a trước khi lấy biên theo a.
And so the rule is you can't actually marginalize something unless you only have one factor that has it that represents the distribution over that variable, perhaps jointly with other things, and under some condition.
Vậy quy tắc là bạn không thể lấy biên một biến trừ khi chỉ còn một factor chứa nó, biểu diễn phân phối trên biến đó, có thể là đồng thời với các biến khác, và với một số điều kiện.
So the basic recipe is going to be simple. You can't marginalize it until you've joined all the factors that have it.
Công thức cơ bản sẽ đơn giản. Bạn không thể lấy biên cho đến khi đã join mọi factor chứa biến đó.
So you're going to pick a variable, you're going to join on that variable, and you're going to immediately marginalize on it. You say what about my query variable?
Vậy bạn chọn một biến, join theo biến đó, và lấy biên ngay lập tức. Bạn hỏi còn biến truy vấn thì sao?
I don't want to marginalize over that. OK. Don't pick that one. Leave that one for last.
Tôi không muốn lấy biên theo nó. OK. Đừng chọn biến đó. Để nó lại cuối cùng.
And what about my evidence variables? I don't want to marginalize over them. Well, the first thing you do is select them, so they're basically gone in a data structure sense.
Còn các biến bằng chứng thì sao? Tôi không muốn lấy biên theo chúng. Việc đầu tiên bạn làm là chọn chúng, nên về mặt cấu trúc dữ liệu chúng coi như biến mất.
So let's take a look in the traffic domain and see what this is going to look like.
Hãy xem trong miền giao thông thì việc này trông ra sao.
p of l. OK. We're not — we're not going to actually go through p of l again, and we've already done a couple times.
p của l. OK. Ta sẽ không giải lại p của l nữa, ta đã làm vài lần rồi.
But just sort of eyeball another — just another look of sort of what variable elimination is. Eyeball the inference by enumeration. It says, oh, you want p of l?
Chỉ nhìn lại một lần nữa xem khử biến là gì. Hãy xem suy luận bằng liệt kê. Nó nói: bạn muốn p của l à?
Well, too bad. We don't have that. Instead we have p of sort of l comma t comma r, which decomposes into this product, because it's a Bayes' Net.
Tiếc quá. Ta không có cái đó. Thay vào đó ta có p của l, t, r, phân rã thành tích này, vì đây là mạng Bayes.
So we're going to write that product and then we're going to do lots of summing.
Ta viết tích đó ra rồi lấy tổng rất nhiều lần.
The summing is all out here, and this represents joining those factors on r, joining the factors that remain on t, then eliminating r, then eliminating t.
Các tổng nằm hết ở ngoài này, và nó biểu diễn việc join các factor theo r, join các factor còn lại theo t, rồi khử r, rồi khử t.
All variable elimination is going to do is move the sum in. So you're going to join on r, but then immediately eliminate it.
Khử biến chỉ làm một việc là đưa tổng vào trong. Bạn join theo r, nhưng khử nó ngay lập tức.
And what's going to be sitting there after you do that is a little p of t factor. And now you can join on t and eliminate that.
Và sau đó thứ còn lại là một factor p của t nhỏ. Giờ bạn có thể join theo t và khử nó.
And so you didn't sort of grow it completely before you projected it down. OK. So you could say, why did you teach us about factors? Why was there a factor zoo?
Như vậy bạn không để nó phình to hoàn toàn rồi mới chiếu xuống. OK. Có thể các em sẽ hỏi: sao thầy lại dạy về các factor? Sao lại có cả một "vườn thú factor"?
Why are there database joins? Why don't we just write algebraic expressions like this, and move the summation around according to the laws of algebra and probability? You can do that if you want.
Sao lại có phép join kiểu cơ sở dữ liệu? Sao không viết thẳng các biểu thức đại số như thế này, rồi di chuyển dấu tổng theo các quy tắc của đại số và xác suất? Nếu muốn thì các em cứ làm vậy.
In fact, some people teach it that way. Enough said. OK. So let's do marginalizing early.
Thực ra, có người dạy theo cách đó. Nói vậy là đủ. OK. Giờ ta hãy lấy biên sớm.
OK. At this point, like don't even track the individual numbers, though feel free to go back and actually like go through these slides your own.
OK. Đến đây, đừng theo dõi từng con số nữa, nhưng các em cứ tự quay lại và xem kỹ các slide này.
We're now — instead of going to join, join, join r t, l, marginalize, marginalize, marginalize. Let's just sort of like marginalize aggressively. OK. So we're going to join on r.
Thay vì join, join, join r t, l, rồi lấy biên, lấy biên, lấy biên, ta sẽ lấy biên một cách quyết liệt. OK. Ta join trên r.
Boom. The r and t nodes become one big factor r comma t. OK. So these two factors get consumed to produce their join.
Xong. Hai nút r và t thành một factor lớn r phẩy t. OK. Hai factor này bị dùng hết để tạo ra phép join của chúng.
But now we can sum out r, because we don't care about it, and it only appears in one factor. See, this was too early here to marginalize it.
Nhưng giờ ta có thể lấy tổng theo r, vì ta không quan tâm đến nó, và nó chỉ xuất hiện trong một factor. Thấy chưa, lúc trước lấy biên nó thì còn quá sớm.
OK. So we sum out r. Boom. r comma t is just t, and this factor just got exponentially smaller.
OK. Vậy ta lấy tổng theo r. Xong. r phẩy t chỉ còn là t, và factor này nhỏ đi theo cấp số nhân.
OK. Got half as — half as big. OK. All right.
OK. Chỉ còn một nửa kích thước. OK. Được rồi.
Now we can join on t. We get something two-dimensional over t and l, but then we sum out t and it's back down to l. Is this better?
Giờ ta join trên t. Ta được một thứ hai chiều theo t và l, nhưng rồi lấy tổng theo t và nó lại còn l. Cách này có tốt hơn không?
Yeah, it is actually better, because when we did join, join, we got the big three-dimensional thing, and here it never got that out of hand.
Có, thực sự tốt hơn, vì khi join, join, ta có một thứ ba chiều rất lớn, còn ở đây nó không bao giờ phình to như vậy.
We never got anything bigger than two-dimensional in this order of variable elimination.
Ta không có thứ gì lớn hơn hai chiều với thứ tự khử biến này.
OK. So let's take a break, and then we'll present kind of how that works with evidence. We'll do some examples.
OK. Giờ nghỉ giải lao, rồi ta sẽ xem cách nó hoạt động với bằng chứng. Ta sẽ làm vài ví dụ.
We'll talk about why all the stuff is NP-hard anyway, and the difference between good and bad variable orderings. OK. All right. Two minutes.
Ta sẽ bàn vì sao những thứ này vốn là NP-hard, và sự khác nhau giữa thứ tự biến tốt và xấu. OK. Được rồi. Hai phút.
All right.
Được rồi.
OK. Let's get started again.
OK. Ta bắt đầu lại nhé.
So what about evidence? What are we doing here? We're looking at the variable elimination algorithm, which is an algorithm for computing queries in a Bayes' Net.
Vậy còn bằng chứng thì sao? Ta đang làm gì ở đây? Ta đang xem thuật toán khử biến, một thuật toán để tính các truy vấn trong mạng Bayes.
And so far, we sort of have some pieces, but we don't quite have an algorithm, like, we haven't really said what the inputs and outputs are. We've just said what the building blocks are.
Đến giờ ta mới có vài mảnh ghép, chứ chưa có một thuật toán hoàn chỉnh, tức là ta chưa nói rõ đầu vào và đầu ra là gì. Ta mới nói các khối xây dựng là gì.
The building blocks are joining where you gather all your factors that share a specific variable. And then after you join them, that variable will appear once in one factor.
Khối xây dựng là phép join, trong đó ta gom mọi factor có chung một biến cụ thể. Sau khi join, biến đó chỉ xuất hiện một lần trong một factor.
And it turns out it'll appear on the left side of the conditioning bar, and so you can marginalize it out.
Và nó sẽ nằm bên trái dấu điều kiện, nên ta có thể lấy biên để loại nó đi.
So in order to actually have the full algorithm, we need to talk about what happens with evidence, what happens with your query, what are the inputs, what are the sequences, what are the choice points.
Vậy để có thuật toán đầy đủ, ta cần nói về bằng chứng, về truy vấn, đầu vào là gì, các bước là gì, các điểm lựa chọn là gì.
So we're going to do that now. So your inputs are — you have a bunch of local factors there. The conditional probability is to come with your Bayes' Net.
Giờ ta sẽ làm điều đó. Đầu vào của ta là một loạt factor cục bộ. Các xác suất có điều kiện đi kèm mạng Bayes.
There's no evidence yet, but you know which variables have specific values, because they've been observed. Like maybe you've observed that the patient has this temperature. So now that random variable is evidence.
Chưa có bằng chứng, nhưng ta biết biến nào có giá trị cụ thể, vì chúng đã được quan sát. Ví dụ ta đã quan sát thấy bệnh nhân có nhiệt độ này. Khi đó biến ngẫu nhiên ấy là bằng chứng.
So what do you do? So you start with your factors.
Vậy ta làm gì? Ta bắt đầu với các factor.
So if you have no evidence in this exam — running example of p of r, p of t given r, and p of l given t, these are the conditional probabilities that come with your Bayes' Net, no observations.
Nếu không có bằng chứng, trong ví dụ đang chạy này gồm p của r, p của t cho r, và p của l cho t, đây là các xác suất có điều kiện đi kèm mạng Bayes, không có quan sát.
But if I'd like to compute what's the probability that I'm late given that it's raining, my initial factors change. p of r changes, because the minus r part is gone.
Nhưng nếu ta muốn tính xác suất mình bị muộn khi trời mưa, các factor ban đầu sẽ đổi. p của r đổi, vì phần trừ r bị bỏ đi.
You say that's a — I only saved one line. But, remember, you've conceptually just knocked out half your joint distribution. So that's great. You've just knocked it out locally.
Các em bảo là... mới tiết kiệm được có một dòng. Nhưng hãy nhớ, về mặt khái niệm ta vừa loại bỏ một nửa phân phối đồng thời. Vậy là rất tốt. Ta vừa loại nó ngay tại chỗ.
And then t given r becomes t given plus r. So it's still probabilities of t given r, except now instead of being a two-dimensional object, it's a one-dimensional object.
Rồi t cho r thành t cho cộng r. Nó vẫn là xác suất của t cho r, nhưng thay vì là vật hai chiều, giờ nó là vật một chiều.
And p of l given t doesn't change, because it doesn't mention r, which is our evidence.
Còn p của l cho t không đổi, vì nó không nhắc đến r, tức bằng chứng của ta.
So you start with the same factors as before, but everywhere your evidence appears, you delete all of the rows that correspond to the values other than the observed evidence.
Vậy ta bắt đầu với các factor giống như trước, nhưng ở mọi chỗ bằng chứng xuất hiện, ta xóa mọi dòng ứng với các giá trị khác với bằng chứng đã quan sát.
All right. So you eliminate — and now what you do is you eliminate all variables, you're not going to eliminate the evidence we already took into account. We're happy.
Được rồi. Rồi ta khử biến, và giờ ta khử mọi biến, trừ bằng chứng vì ta đã tính đến nó rồi. . Ta ổn rồi.
The evidence is happy. We don't need to eliminate it. We don't need to join it. OK.
Bằng chứng cũng ổn. Ta không cần khử nó. Ta cũng không cần join nó. OK.
And we're not going to eliminate or join our query just yet, because that's what we want to have left in the end.
Và ta cũng chưa khử hay join biến truy vấn, vì đó là thứ ta muốn giữ lại ở cuối.
So what we're going to do is we're going to go to every other variable that isn't our evidence. Here our evidence is r, and here our query is l.
Vậy việc ta sẽ làm là đi tới mọi biến khác không phải là bằng chứng. Ở đây bằng chứng là r, và truy vấn là l.
So we're going to go to all the others, which is just t, and we're going to eliminate them. What does eliminate mean? Join and marginalize. OK.
Vậy ta đi tới tất cả các biến còn lại, ở đây chỉ có t, và ta sẽ khử chúng. Khử nghĩa là gì? Join rồi marginalize. OK.
So if we do that — and we'll do an example in a sec — in a second — what you'll end up with is you will end up, if you do probability of late given r, meaning you select all of the plus r rows, and then you find everything like t that isn't mentioned in your evidence and query, and you join and marginalize, you'll end up with one factor at the end.
Nếu làm vậy, và lát nữa ta sẽ có ví dụ, ngay sau đây, thì kết quả sẽ là, nếu tính xác suất của late cho trước r, nghĩa là chọn tất cả các hàng có plus r, rồi tìm mọi biến như t không nằm trong bằng chứng và truy vấn, rồi join và marginalize, bạn sẽ còn lại một nhân tử ở cuối.
So there'll be a join at the end. And the join at the end, you'll end up with one factor that looks like this. It'll be a selected joint of the evidence in the query.
Tức là có một phép join ở cuối. Và sau phép join cuối đó, bạn có một nhân tử trông như thế này. Đó là phân phối đồng thời được chọn của bằng chứng và truy vấn.
So the evidence has one value, and the query has all its values. So it has plus l and minus l, but just plus r because that's your evidence.
Bằng chứng chỉ có một giá trị, còn truy vấn có mọi giá trị. Tức là có plus l và minus l, nhưng chỉ có plus r vì đó là bằng chứng của bạn.
As a data structure, that's a one-dimensional object. As a semantic object, is it — those are all joint probabilities of r and l.
Về cấu trúc dữ liệu, đó là đối tượng một chiều. Về ý nghĩa, đó đều là các xác suất đồng thời của r và l.
So if I normalize that, meaning divide it by its sum, I'll end up with a probability distribution over l.
Nếu chuẩn hóa, tức là chia cho tổng, ta được một phân phối xác suất trên l.
There's an entry for every value of l and it sums to 1, so it's a probability distribution. Moreover, it'll be the conditional probability of the query variable given the evidence.
Có một mục cho mỗi giá trị của l và tổng bằng 1, nên đó là một phân phối xác suất. Hơn nữa, đó là xác suất có điều kiện của biến truy vấn cho trước bằng chứng.
OK. So let's do some examples. That's it. We're going to do the general again — say what it is in general, and then we're going to do some examples.
OK. Giờ ta làm vài ví dụ. Vậy thôi. Ta sẽ nói lại dạng tổng quát, nó là gì nói chung, rồi ta làm vài ví dụ.
Your query, it has a query variable. You can actually have multiple query variables, but for now we'll pretend there's just one. There's evidence. OK.
Truy vấn của bạn có một biến truy vấn. Thực ra có thể có nhiều biến truy vấn, nhưng tạm thời ta giả sử chỉ có một. Có bằng chứng. OK.
You can have anywhere from 0 to everything else in the network as evidence. Your initial states is the local conditional probabilities instantiated by the evidence.
Bằng chứng có thể là từ 0 đến tất cả các biến còn lại trong mạng. . Trạng thái ban đầu là các xác suất có điều kiện cục bộ được gán theo bằng chứng.
While there are variables, which are neither e variables nor q, pick a hidden variable, join everything mentioning h, and then sum out h. So you join on h, you sum on h.
Chừng nào còn biến không phải biến bằng chứng cũng không phải q, chọn một biến ẩn, join mọi thứ có chứa h, rồi lấy tổng theo h. Tức là join theo h, rồi lấy tổng theo h.
Once that's done and you can find it no more hidden variables, what's left in your factors? All the hidden variables are gone.
Khi xong và không còn biến ẩn nào nữa, các nhân tử còn lại gì? Mọi biến ẩn đã mất.
What's going to be left is q, which will appear as a vector. And a bunch of evidence values, which will — which will not appear sort of as axes.
Còn lại q, xuất hiện dưới dạng vectơ. Và một loạt giá trị bằng chứng, không xuất hiện như các trục.
Countdown to goodness. I think we can wait an hour for the goodness. OK. All right.
Đếm ngược tới điều tuyệt vời. Chắc ta chờ được một tiếng cho điều tuyệt vời đó. OK. Được rồi.
So the last thing you're going to do is you're going to join all your remaining factors in — and normalize. So you select your evidence.
Bước cuối cùng là join tất cả nhân tử còn lại và chuẩn hóa. Vậy bạn chọn bằng chứng.
You hunt down the hidden variables in order of your choosing, and then at the end you join and normalize.
Bạn xử lý các biến ẩn theo thứ tự tùy chọn, và cuối cùng join rồi chuẩn hóa.
Here's an example. All right. There's going to be a lot of little conditional probabilities with conditioning bars and some capitals and some lower case.
Đây là một ví dụ. Được rồi. Sẽ có rất nhiều xác suất có điều kiện nhỏ với dấu gạch điều kiện cùng chữ hoa và chữ thường. Hãy cố theo dõi dòng chảy của việc các đối tượng này thay đổi về mặt đại số.
Just try to track the flow of how these objects are sort of changing algebraically. So at the beginning, here's my alarm network.
Đầu tiên, đây là mạng báo động của tôi.
So that's — so forget variable elimination for my — forgot my query. There is my network. If that means we're going to have a model here over a, b, e, j and m.
Tạm quên khử biến, quên truy vấn đi. Đây là mạng của tôi. Nghĩa là ta có một mô hình trên a, b, e, j và m.
OK. Great. And that means in principle, there is a joint probability over a, b, e, j, and m. But we're going to try our very best to not actually assemble that five-dimensional object.
OK. Tuyệt. Và về nguyên tắc, điều đó nghĩa là có một phân phối đồng thời trên a, b, e, j và m. Nhưng ta sẽ cố hết sức để không phải dựng đối tượng năm chiều đó.
Somebody comes along and says, hey, I want the probability of burglary given that John and Mary are both calling, let's say. So let's pretend those are plus j and plus m.
Có người đến và nói, tôi muốn xác suất có trộm khi cả John và Mary đều gọi, chẳng hạn. Giả sử đó là plus j và plus m.
OK. They're just written as j and m. Pretend they're plus. All right.
OK. Chúng chỉ được viết là j và m. Cứ coi như là plus. Được rồi.
So I say, all right, let's do it. Well, what I'm really going to do is calculate this joint probability instead. It's the same thing but unnormalized. And then I'll normalize as a last step.
Tôi nói, được, làm thôi. Thực ra tôi sẽ tính xác suất đồng thời này thay vào đó. Nó giống nhau nhưng chưa chuẩn hóa. Rồi bước cuối tôi sẽ chuẩn hóa.
So let's calculate it. Well, rather than actually going through and introducing variables and summing and trying to do this sort of arithmetically, we're going to do variable elimination.
Ta tính thôi. Thay vì thật sự đi đưa biến vào rồi lấy tổng và tính theo kiểu số học, ta sẽ dùng khử biến.
So here we are with our five factors. Each one corresponds to a node.
Đây là năm nhân tử của ta. Mỗi nhân tử ứng với một nút.
So, for example, this j node has probability of j given a, and it's been instantiated to select to match the evidence. So I start with five.
Ví dụ nút j này có xác suất của j cho trước a, và nó đã được gán để khớp với bằng chứng. Vậy tôi bắt đầu với năm nhân tử.
P of b, p of e — those are the two top nodes — p of a given b comma e, that's the big node in the middle.
P của b, p của e, đó là hai nút trên cùng, p của a cho trước b, e, đó là nút lớn ở giữa.
It's already a three-dimensional object, so that one might be trouble. And then I've got j given a, but it's already been selected to the value of j plus that I have.
Nó đã là đối tượng ba chiều rồi, nên cái đó có thể gây rắc rối. Rồi tôi có j cho trước a, nhưng nó đã được chọn theo giá trị của j cộng mà tôi có.
And m given a has also been selected. These are — remember, we talked about them, they are selected families. They are not probability distributions over a.
Và m cho trước a cũng đã được chọn. Những cái này, nhớ là chúng ta đã nói rồi, chúng là các họ đã được chọn. Chúng không phải phân phối xác suất theo a.
They're conditional probabilities over plus j, one for every value of a. What do they sum to? Who knows. OK.
Chúng là các xác suất có điều kiện theo cộng j, một cái cho mỗi giá trị của a. Chúng có tổng bằng bao nhiêu? Ai biết đâu. Được rồi.
All right. So here are my five factors, which are my original conditional probabilities from the Bayes' Net instantiated by the evidence. So I pick variables in some order.
Được rồi. Đây là năm factor của tôi, chính là các xác suất có điều kiện ban đầu từ mạng Bayes, đã được gán bằng bằng chứng. Tôi chọn các biến theo một thứ tự nào đó.
Let's pick a. So I choose a. I summon together all the factors that mention a, of which there are three. All right.
Chọn a. Vậy tôi chọn a. Tôi gom tất cả các factor có chứa a, có ba cái. Được rồi.
So I got to join all these factors together. What am I going to end up with? Well, whatever I end up with, it's going to involve a and b and e.
Giờ tôi phải kết hợp (join) các factor này lại. Tôi sẽ thu được gì? Dù là gì đi nữa, nó sẽ liên quan đến a, b và e.
And, actually, also j and m, in terms of what it means, but they're not as a data structure. They're not axes here. These are going to be three-dimensional objects.
Thực ra cũng có j và m về mặt ý nghĩa, nhưng chúng không có trong cấu trúc dữ liệu. Chúng không phải là các trục ở đây. Đây sẽ là các đối tượng ba chiều.
So I'm going to have something that's going to be a factor over a, b, and e.
Vậy tôi sẽ có một thứ là factor theo a, b và e.
And what it's going to correspond to is a bunch of products of p of a given b e values, times p of j given a values, times p of m given a values.
Và nó sẽ tương ứng với một loạt tích của p của a cho trước b, e, nhân p của j cho trước a, nhân p của m cho trước a.
What's that? That's going to be the probability of a and j and m given b of e. So if I put all those things together, you say, how did I know that?
Đó là gì? Đó sẽ là xác suất của a và j và m cho trước b, e. Nếu gộp tất cả lại, các bạn hỏi, sao tôi biết vậy?
Well, that's the only thing they could be.
Vì nó chỉ có thể là như thế.
You sort of union up over — union up everything that's on the left of the conditioning bars, and then whatever is left is on the right of the conditioning bar.
Bạn hợp tất cả những gì ở bên trái dấu điều kiện lại, và phần còn lại nằm bên phải dấu điều kiện.
OK. All right. So I'm going to join them up, and then I'm going to sum out a. I joined on a, and now I'm going to sum it out.
Được rồi. Được rồi. Vậy tôi kết hợp chúng, rồi lấy tổng loại a. Tôi đã join theo a, giờ tôi tính tổng để loại nó.
And I'm going to end up with a table that represents joint probabilities of j and m given b and e.
Và tôi sẽ có một bảng biểu diễn xác suất đồng thời của j và m cho trước b và e.
Except j and m have single values, which means how big a data structure is this? Dimension one, dimension two. OK.
Chỉ là j và m đã có giá trị cố định, vậy cấu trúc dữ liệu này lớn cỡ nào? Chiều một, chiều hai. Được rồi.
This is going to be a two-dimensional array for values of b and for values of e, and for every entry for a b and an e, it'll give you the probability of j and m, given that b and d.
Đây sẽ là một mảng hai chiều theo các giá trị của b và của e, và với mỗi ô ứng với một b và một e, nó cho xác suất của j và m, cho trước b và e đó.
Well, here we are. We got factors again. I dispose of these. They will confuse me, so I throw them out.
Vậy là xong. Ta lại có các factor. Tôi bỏ những cái này đi. Chúng sẽ làm tôi rối, nên tôi vứt chúng.
Besides, I don't need them anymore. I already have their replacement. So now I've got p of b because it was not harmed in that joining.
Hơn nữa tôi không cần chúng nữa. Tôi đã có cái thay thế rồi. Giờ tôi còn p của b vì nó không bị ảnh hưởng trong phép join đó.
We've got p of e, it was not harmed in that joining. And these three here have been replaced by this one. OK. Almost done.
Còn p của e, cũng không bị ảnh hưởng. Và ba cái này đã được thay bằng cái này. Được rồi. Gần xong rồi.
I want p of be given j and m. There's one more hidden variable, which is e. So I'm going to join and eliminate.
Tôi muốn p của b, e cho trước j và m. Còn một biến ẩn nữa, là e. Vậy tôi sẽ join rồi loại.
So I say — I say, I will pick e. When I picked, there are two variables that mention — there are two factors that mention e.
Tôi chọn e. Khi chọn, có hai biến à không, có hai factor chứa e.
The original p of e, and this new thing that I just made that has e as one of the conditioning properties. When I join these things together, I'm going to get another two-dimensional object.
p của e ban đầu, và cái mới vừa tạo có e là một trong các biến điều kiện. Khi join chúng lại, tôi sẽ có một đối tượng hai chiều khác.
You'll see e has moved from one side to the other, because I multiplied by p of e.
Các bạn thấy e chuyển từ bên này sang bên kia, vì tôi đã nhân với p của e.
And then no sooner does it move than I eliminate it, and I end up with the probability of plus j plus m given b.
Và vừa chuyển xong là tôi loại nó ngay, và được xác suất của cộng j cộng m cho trước b.
So there's going to be a value for plus b, and a value for minus b. Now, I've got two factors left.
Sẽ có một giá trị cho cộng b, và một giá trị cho trừ b. Giờ tôi còn hai factor.
I got the original p of b, and I've got this new p of j comma m given b. All right. I'm all out of hidden variables.
Có p của b ban đầu, và p mới của j, m cho trước b. Được rồi. Tôi hết biến ẩn rồi.
My evidence variables were taken into account when I instantiated them. All that's left is my query variable.
Các biến bằng chứng đã được tính đến khi tôi gán giá trị cho chúng. Chỉ còn biến truy vấn.
I could join and eliminate one more time, but that would be silly because, actually, I don't want to eliminate b. So what I'll do is join but not eliminate.
Tôi có thể join và loại thêm một lần nữa, nhưng thế thì ngớ ngẩn vì thực ra tôi không muốn loại b. Nên tôi sẽ join mà không loại.
So the last thing I do is a big join. I join everything that's left.
Bước cuối là một phép join lớn. Tôi join mọi thứ còn lại.
And I will end up with the probability of my evidence jointly with my query variable, because this is a vector. There's one value of this for plus b, and one value for minus b.
Và tôi sẽ được xác suất của bằng chứng đồng thời với biến truy vấn, vì đây là một vectơ. Có một giá trị cho cộng b, và một giá trị cho trừ b.
And if I normalize that, I will get the conditional probability of b given that evidence, and I'm done. OK. So that's how the variable elimination flows.
Nếu chuẩn hóa nó, tôi sẽ có xác suất có điều kiện của b cho trước bằng chứng đó, và xong. Được rồi. Đó là cách khử biến diễn ra.
You start with a bunch of little factors, you join. And when you join, you might grab seven things and build some mega factor, and then you eliminate one thing.
Bạn bắt đầu với một loạt factor nhỏ, rồi join. Khi join, bạn có thể lấy bảy cái và tạo ra một factor khổng lồ, rồi mới loại một biến.
And so you have to choose wisely about what you join, because for bad orders, you might build things faster than you're shrinking them. OK. All right. Do not process the slide.
Nên bạn phải chọn khôn ngoan thứ cần join, vì với thứ tự tệ, bạn có thể tạo ra factor nhanh hơn tốc độ bạn thu nhỏ chúng. Được rồi. Được rồi. Đừng xử lý slide.
Don't do it. This slide is simply saying that instead of working with these factors, I could have worked all that out using products, and sums, and laws of distribution, and all of that.
Đừng làm thế. Slide này chỉ muốn nói rằng thay vì làm việc với các factor này, tôi có thể tính ra tất cả bằng các phép nhân, phép tổng, và luật phân phối, v.v.
OK. Variable elimination is — is a mechanical way of figuring out how this is going to work in a way that's much easier to reason about than these sort of algebraic arithmetic expressions.
OK. Khử biến là một cách máy móc để tìm ra việc này diễn ra thế nào, theo cách dễ suy luận hơn nhiều so với những biểu thức đại số số học này.
OK. But feel free to like eyeball this later and see how it's doing the same thing. But don't eyeball it now. I'm going to make it go away.
OK. Nhưng lát nữa các em cứ thoải mái nhìn kỹ để thấy nó làm cùng một việc. Nhưng bây giờ thì đừng nhìn. Tôi sẽ cho nó biến mất.
It's gone. Oh, man. OK.
Mất rồi. Trời ơi. OK.
All right. So variable elimination. Somebody hands you a network, and in that network, there is a whole bunch of variables that are maybe observed.
Được rồi. Vậy là khử biến. Ai đó đưa cho bạn một mạng, và trong mạng đó có cả loạt biến có thể đã được quan sát.
So observe, observe, observe, observe, sort of observe, maybe observe all the Y's. This is pretty common, right?
Quan sát, quan sát, quan sát, quan sát, kiểu như quan sát, có thể quan sát tất cả các Y. Chuyện này khá phổ biến, đúng không?
You've got some underlying cause you'd like to infer something about, and you see a bunch of distal facts, and you want to do a — do a diagnostic inference here.
Bạn có một nguyên nhân tiềm ẩn mà bạn muốn suy ra điều gì đó, và bạn thấy một loạt dữ kiện xa, và bạn muốn thực hiện suy luận chẩn đoán ở đây.
And so I'd like to know what's the probability of something given the rest. Maybe I want to know what's the probability of xn given all those Y's. OK.
Và tôi muốn biết xác suất của một thứ nào đó khi biết phần còn lại. Có thể tôi muốn biết xác suất của xn khi biết tất cả các Y đó. OK.
Now — well, first of all, let's just figure out what's going on. These guys, these are the evidence. OK. So those are the evidence variables e.
Bây giờ, trước hết, hãy xem chuyện gì đang diễn ra. Những biến này là bằng chứng. OK. Đó là các biến bằng chứng e.
The Y's are the e's. The query variable is x sub n. Everything else z, x1, x7, all that stuff, that's all hidden variables.
Các Y chính là các e. Biến truy vấn là x chỉ số n. Mọi thứ còn lại: z, x1, x7, v.v. đều là biến ẩn.
So the evidence I'm going to instantiate that. Fine. We're not going to eliminate the Y's. The last thing left standing is going to be xn.
Còn bằng chứng thì tôi sẽ gán giá trị cụ thể. Tốt. Chúng ta sẽ không khử các Y. Thứ cuối cùng còn lại sẽ là xn.
And we'll join and normalize in that in the end. And in between all this other stuff — put a green box. All the stuff in the green box is hidden variables.
Và cuối cùng ta sẽ kết hợp (join) và chuẩn hóa nó. Còn ở giữa, tất cả những thứ khác, tôi vẽ một khung xanh. Mọi thứ trong khung xanh là biến ẩn.
These are the H's. And these need to get eliminated. So we have an algorithm.
Đây là các H. Và những biến này cần được khử. Vậy ta có một thuật toán.
We're going to point to one, we're going to summon its factors, and then we're going to multiply them together, and then marginalize out over that axis. So let's actually try something.
Ta chỉ vào một biến, triệu tập các factor của nó, rồi nhân chúng lại với nhau, sau đó lấy biên theo trục đó. Giờ ta thử một chút nhé.
Let's try two possible worlds here. One is where we eliminate X1. Let's just do it real quick. So we're going to summon all the factors that involve X1.
Thử hai kịch bản có thể xảy ra ở đây. Một là khử X1. Ta làm thật nhanh. Ta triệu tập mọi factor có chứa X1.
Well, there's this p of y1. That's evidence, so it's going to be a lower case y1 given capital X1. OK. That's cool.
Có p của y1. Đó là bằng chứng, nên nó sẽ là y1 viết thường khi biết X1 viết hoa. OK. Được rồi.
What else mentions X1? What other factors in this network have an X1 in them? It was only one more. There's the one living under p of X1.
Còn gì nhắc đến X1 nữa? Những factor nào khác trong mạng này có X1? Chỉ còn một cái nữa thôi. Cái nằm dưới p của X1.
So it's p of X1 given — given z, given its parent. OK. So we're going to join them. So let's do it.
Tức là p của X1 khi biết z, nút cha của nó. OK. Vậy ta sẽ join chúng. Làm thôi.
We're going to do a join on these things. We're going to end up with some new data structure. It's going to contain probability of little y1 and big X1.
Ta thực hiện phép join trên các thứ này. Ta sẽ có một cấu trúc dữ liệu mới. Nó sẽ chứa xác suất của y1 viết thường và X1 viết hoa.
So it's going to be a given z. It's going to be, as a data structure, two-dimensional. There's a dimension for x and a dimension for z.
Nên nó sẽ có điều kiện theo z. Về mặt cấu trúc dữ liệu, nó là hai chiều. Có một chiều cho x và một chiều cho z.
And every entry is a probability of y1 given X1 — sorry, y1 and X1 given z. Now — so that's the join.
Và mỗi ô là xác suất của y1 khi biết X1, xin lỗi, của y1 và X1 khi biết z. Đó là phép join.
And now we're going to marginalize out over X1, and we're going to end up with probability of y1 given z. That's OK. No harm done.
Và giờ ta lấy biên theo X1, và sẽ được xác suất của y1 khi biết z. Ổn thôi. Không sao cả.
And then I'll do it for X2 and for X3. That'll be OK, right?
Rồi tôi làm tương tự cho X2 và X3. Vậy là ổn, đúng không?
Let's think about another path we could take. So this is where we pick X1 as our first variable to eliminate. So, now, let's eliminate z. Eliminated z.
Giờ hãy xét một hướng đi khác. Đây là trường hợp ta chọn X1 làm biến đầu tiên để khử. Còn bây giờ, ta khử z. Khử z.
OK. Let's see what happens. Step one, we're going to summon every factor that mentions z. Let's figure out what faction's met — factors mention z.
OK. Xem chuyện gì xảy ra. Bước một, triệu tập mọi factor có chứa z. Xem factor nào có chứa z.
Well, there's p of z, that mentions z. That lives in here. All right. What other factors mention z in this Bayes' Net?
Có p của z, cái đó chứa z. Nó nằm ở đây. Được rồi. Những factor nào khác trong mạng Bayes này chứa z?
So think about which nodes, either rz, we got that one, or have a parent that is z. Well, p of X1 given z, that's one of them. What else?
Hãy nghĩ xem nút nào là z, cái đó ta có rồi, hoặc có nút cha là z. Có p của X1 khi biết z, đó là một cái. Còn gì nữa?
p of X2 given z. p of X3 given z. p of xn minus 1 given z. All right.
p của X2 khi biết z. p của X3 khi biết z. p của xn trừ 1 khi biết z. Được rồi.
Do you have a bad feeling? I have a bad feeling. So we're going to take all these things and we're going to join them together. What do we get?
Các em có linh cảm xấu không? Tôi có linh cảm xấu. Ta sẽ lấy tất cả những thứ này và join chúng lại với nhau. Ta được gì?
We're going to get a monster array, right?
Ta sẽ có một mảng khổng lồ, đúng không?
This is going to be some thing which is going to be probably — it's going to be some factor over X1 all the way through xn minus 1.
Đây sẽ là một thứ có lẽ là — một nhân tử trên X1 cho đến xn trừ 1.
Actually, it's going to be all those product together. p of z. Then we're going to eliminate z.
Thật ra, nó sẽ là tích của tất cả những thứ đó. p của z. Sau đó ta sẽ khử z.
Let me just — Let's do it this way. OK. So we're going to form this joint probability, and then we're going to eliminate z.
Để tôi — Làm thế này nhé. OK. Ta tạo ra phân phối xác suất đồng thời này, rồi khử z.
All right. What are we left with when we eliminate z? We're left with a giant factor over all of its children.
Được rồi. Khi khử z, ta còn lại gì? Ta còn lại một nhân tử khổng lồ trên tất cả các nút con của nó.
That's kind of bad, right? We just built something exponential. Sorry. OK.
Tệ nhỉ? Ta vừa tạo ra thứ có kích thước mũ. Xin lỗi. OK.
That was a bad choice. We should not eliminate z. Why? Intuitively, what's going on here?
Đó là lựa chọn tồi. Ta không nên khử z. Tại sao? Về trực giác, chuyện gì đang xảy ra ở đây?
In this network, you've got z, which is a cause. And there's a whole bunch of things which are independent given z. Well, what happens if we eliminate z?
Trong mạng này, z là một nguyên nhân. Và có cả loạt biến độc lập với nhau khi biết z. Vậy nếu khử z thì sao?
They're not independent anymore. Suddenly, they all kind of rise and fall together. But it's not mediated by z anymore because we just nuked z.
Chúng không còn độc lập nữa. Đột nhiên chúng cùng tăng cùng giảm với nhau. Nhưng không còn thông qua z nữa vì ta vừa xóa sạch z.
So what's left is a big joint factor over everything that's left that has now been coupled.
Thế là còn lại một nhân tử đồng thời lớn trên mọi biến còn lại, giờ đã bị gắn kết với nhau.
So we have to be very careful when we do variable elimination that we don't pick variables early on that cause everything left to couple.
Vì vậy khi khử biến, ta phải rất cẩn thận đừng chọn sớm những biến khiến mọi biến còn lại bị gắn kết.
Because that's going to end up with exponentially large things right away. So there are good variable orderings and there's bad variable orderings. Is there always a good ordering?
Vì như vậy sẽ tạo ra những thứ lớn theo hàm mũ ngay lập tức. Vậy có thứ tự biến tốt và có thứ tự biến xấu. Có phải lúc nào cũng có thứ tự tốt không?
No. This is NP-hard. How hard is it to find the best ordering? NP-hard.
Không. Bài toán này là NP-hard. Tìm thứ tự tốt nhất khó đến mức nào? NP-hard.
Right. So, however, you know, good luck. Good luck finding a good ordering. OK.
Đúng. Nên là, chúc may mắn nhé. Chúc may mắn tìm được thứ tự tốt. OK.
So this can be exponentially better if you pick a good ordering. Can't always find a good ordering, but you can try. OK. So the ordering affects efficiency.
Nếu chọn thứ tự tốt thì có thể nhanh hơn theo hàm mũ. Nếu chọn thứ tự tốt thì có thể nhanh hơn theo hàm mũ. Không phải lúc nào cũng tìm được thứ tự tốt, nhưng ta có thể thử. OK. Vậy thứ tự ảnh hưởng đến hiệu quả.
OK.
OK.
We have an algorithm, variable elimination. You join things and eliminate immediately. Some orders are better than others. Finding the best ordering can be hard.
Ta có một thuật toán, khử biến. Bạn kết hợp rồi khử ngay. Có thứ tự tốt hơn thứ tự khác. Tìm thứ tự tốt nhất có thể rất khó.
The computational and space complexity of this algorithm is going to be determined by how big these things that you build are.
Độ phức tạp tính toán và bộ nhớ của thuật toán này được quyết định bởi các nhân tử bạn tạo ra lớn đến đâu.
If you just build up the whole joint probability, it's going to be bad news. So it's going to be determined by how quickly you let those factors grow.
Nếu bạn dựng cả phân phối đồng thời, thì sẽ rất tệ. Nên nó được quyết định bởi việc bạn để các nhân tử lớn nhanh đến đâu.
The elimination ordering can be very — they can vary greatly how big that factor is going to end up being and, therefore, how expensive this is going to be.
Thứ tự khử có thể rất — kích thước nhân tử cuối cùng có thể chênh lệch rất nhiều và do đó chi phí cũng vậy.
So in the previous slide, there was an exponential difference. All right. So we already knew this. Is there an — always an ordering that results in only small factors?
Ở slide trước, có sự chênh lệch theo hàm mũ. Được rồi. Vậy ta đã biết điều này. Có phải luôn có một thứ tự chỉ tạo ra nhân tử nhỏ không? Có phải luôn có một thứ tự chỉ tạo ra nhân tử nhỏ không?
No. Can you find the best ordering? No. Any questions on that before I show you why?
Không. Bạn có tìm được thứ tự tốt nhất không? Không. Có câu hỏi nào trước khi tôi cho thấy lý do không?
OK. In practice, often there are reasonably good orderings that are reasonably easy to find, and everything ends up being quite efficient. But as always in AI, the worst case is very, very bad news.
OK. Trong thực tế, thường có những thứ tự khá tốt mà khá dễ tìm, và mọi thứ chạy khá hiệu quả. Nhưng như mọi khi trong AI, trường hợp xấu nhất rất tệ.
The reason the worst case here, if you think about it, we can actually go directly to thinking about a CSP and, in particular, a satisfiability problem.
Về lý do của trường hợp xấu nhất, nếu nghĩ kỹ, ta có thể đi thẳng sang việc xét một CSP, cụ thể là bài toán thỏa mãn (satisfiability).
So how could I use a Bayes' Net to solve a satisfiability problem?
Vậy làm sao dùng mạng Bayes để giải một bài toán satisfiability?
If a Bayes' Net can knock out the solution to any satisfiability problem efficiently, then we just found a way to solve [? SAT ?] efficiently.
Nếu mạng Bayes giải hiệu quả được mọi bài toán satisfiability, thì ta đã tìm ra cách giải SAT hiệu quả.
We don't think that's possible and so, therefore, we know that we've got sort of bad news with these Bayes' Net problems in general.
Ta không nghĩ điều đó khả thi, và vì vậy ta biết là có tin xấu với các bài toán mạng Bayes nói chung.
Because even though they might not encode satisfiability, they might, or something else equally bad. So here's how you could, given a satisfiability problem, build a Bayes' Net. Somebody drops on you a satisfiability problem.
Vì dù chúng có thể không mã hóa satisfiability, chúng có thể mã hóa nó, hoặc thứ gì tệ tương đương. Đây là cách, với một bài toán satisfiability, bạn dựng một mạng Bayes. Có người đưa bạn một bài toán satisfiability.
What do those look like? They are a bunch of variables, and then you have a bunch of disjunctions, ors, of those variables so there are negations.
Chúng trông thế nào? Có một loạt biến, rồi có một loạt phép tuyển, tức là phép or, của các biến đó, có cả phủ định.
And then those little clauses are all ended together. How could I write that as a Bayes' Net? Well, variables X1. It's either true or false.
Rồi các mệnh đề nhỏ đó được and với nhau. Làm sao viết nó thành mạng Bayes? Có biến X1. Nó đúng hoặc sai.
And I could stick that in my network, maybe with a distribution says 50-50, true or false. And here's X2, 50-50, true or false.
Tôi có thể đặt nó vào mạng, có thể với phân phối 50-50, đúng hoặc sai. Và đây là X2, 50-50, đúng hoặc sai.
And then each of these clauses is going to say, well, what's y1? Well, guess what? This is y1. y1.
Rồi mỗi mệnh đề này sẽ cho biết y1 là gì? Đoán xem? Đây là y1. y1.
OK. What is y1? y1 is true if X1 is true, or X2 is true, or not X3 is true. How do I encode that?
OK. y1 là gì? y1 đúng nếu X1 đúng, hoặc X2 đúng, hoặc not X3 đúng. Làm sao mã hóa điều đó?
Well, remember, hidden inside this Bayes' Net for y1 is the probability of y1 given various assignments.
Hãy nhớ rằng, ẩn bên trong mạng Bayes cho y1 này là xác suất của y1 với các phép gán khác nhau.
And so you just set it up so that y1 is false if I have a bad configuration of X1, X2, and X3, and y is — y1 is true otherwise.
Và thế là bạn chỉ cần thiết lập sao cho y1 là sai nếu tôi có một cấu hình xấu của X1, X2 và X3, còn y1 là đúng trong các trường hợp khác.
So I can do that for y2 and y3, and then each of the variables. These are the variables. This row is the clauses. What's this structure?
Tôi có thể làm tương tự cho y2 và y3, rồi cho từng biến. Đây là các biến. Hàng này là các mệnh đề. Còn cấu trúc này là gì?
This structure is going to be the ands. This is the thing that's going to say all of those Y's have to be true.
Cấu trúc này sẽ là các phép and. Nó sẽ nói rằng tất cả các Y đó đều phải đúng.
OK. And you similarly fill in their probabilities so that they enforce — they're true only if both of their parents are true. Then you go and you say, hey, what's the probability of z?
OK. Và tương tự, bạn điền các xác suất của chúng sao cho chúng ép buộc rằng chúng chỉ đúng khi cả hai nút cha đều đúng. Rồi bạn hỏi: xác suất của z là bao nhiêu?
Well, if there's some way to assign those X1s so that everything percolates down to true, then the probability of z won't be 0. And if there isn't, it will be 0.
Nếu có một cách gán các X1 nào đó để mọi thứ lan xuống thành đúng, thì xác suất của z sẽ khác 0. Còn nếu không có cách nào, nó sẽ bằng 0.
And so by looking at this marginal probability, you can answer whether or not this thing is satisfiable. And so you say that's a weird sort of construction. Why is there this tree-shaped object?
Vậy bằng cách nhìn vào xác suất biên này, bạn có thể trả lời công thức này có thỏa mãn được hay không. Bạn sẽ nói đây là một cách xây dựng hơi lạ. Sao lại có cấu trúc hình cây này?
Why don't we have variables, disjuncts, conjuncts? OK. Let's do it. So let's say instead all those y1 through yn went straight to a z.
Sao không dùng thẳng các biến, tuyển, hội? OK. Thử xem. Giả sử thay vào đó, tất cả y1 đến yn đều đi thẳng tới z.
Well, they have to all be parents of the z, like this. And if z has a ton of parents, what's living in there?
Thì chúng đều phải là nút cha của z, như thế này. Nếu z có rất nhiều nút cha, thì bên trong nó có gì?
Well, it's something that says all the parents have to be true. And like exponentially many other things, because you don't want to have a lot of parents.
Nó là thứ nói rằng tất cả các nút cha đều phải đúng. Và có số lượng mũ các thứ khác nữa, vì bạn không muốn có quá nhiều nút cha.
So this is a construction that's designed to stay compact while specifying that conjunction.
Đây là cách xây dựng được thiết kế để giữ gọn mà vẫn biểu diễn được phép hội đó.
If you made everything a parent of z, it wouldn't be compact, and so it's not actually — it's not actually that bad that it takes a long time to solve because it's a big thing.
Nếu cho tất cả làm cha của z, nó sẽ không còn gọn, và như vậy thì thật ra việc mất nhiều thời gian để giải cũng không tệ lắm vì bài toán quá lớn.
So, in general, for these reductions, you need to have something small that is hard. This keeps it small. All right. All right.
Nên nói chung, với các phép quy dẫn này, bạn cần một thứ nhỏ mà khó. Cách này giữ cho nó nhỏ. Được rồi. Được rồi.
We now know a Bayes' Net inference is NP-hard.
Giờ ta biết suy luận trên mạng Bayes là NP-hard.
There's no way around that. But in practice, often things are not that bad.
Không có cách nào tránh được. Nhưng trong thực tế, thường mọi thứ không tệ đến vậy.
So let me give you some examples of things that aren't that bad that maybe will remind you of things you've seen in CSPs.
Tôi sẽ đưa vài ví dụ không tệ lắm, có thể gợi bạn nhớ đến những gì đã thấy trong CSP.
So one thing that's not that bad is — well, before we talk about polytrees, one thing that's not that bad is a Bayes' Net that's a chain like this.
Một trường hợp không tệ là trước khi nói về polytree, một mạng Bayes dạng chuỗi như thế này.
OK. Why is that not so bad?
OK. Tại sao nó không tệ?
Well, if I have to do variable elimination on this, it turns out that if I sort of eliminate them from left to right, nothing will really explode in size.
Nếu tôi phải khử biến trên mạng này, thì hóa ra nếu tôi khử chúng từ trái sang phải, sẽ không có gì phình to về kích thước.
OK. Really, the thing that's bad news is when you have lots of things that get coupled together.
OK. Thứ thực sự xấu là khi có nhiều thứ bị ghép cặp với nhau.
So a parent with a lot of children, and you eliminate that here, there are things — don't have that many parents, don't have that many children.
Ví dụ một nút cha có nhiều nút con, và bạn khử nó ở đây, còn ở đây các nút không có nhiều nút cha, cũng không có nhiều nút con.
In general, a polytree is something that is a directed graph that does not have undirected cycles. You can think about it, basically, as a tree.
Nói chung, polytree là một đồ thị có hướng không có chu trình vô hướng. Về cơ bản bạn có thể xem nó như một cây.
But there are some other cases, like, two parents pointing at the same node. For polytrees, you can always find an efficient ordering.
Nhưng có thêm vài trường hợp khác, như hai nút cha cùng trỏ vào một nút. Với polytree, bạn luôn tìm được một thứ tự hiệu quả.
And, in fact, that example we saw with the z's and the y's and the X's — not the satisfiability one, but the one z on the top. That's an example of a polytree.
Thực ra, ví dụ ta thấy với các z, y và X không phải ví dụ thỏa mãn được, mà là ví dụ có z ở trên cùng. Đó là một ví dụ về polytree.
And for polytrees, there can be bad orderings, but there's always a good one. So what does that remind us like from CSPs?
Với polytree, có thể có thứ tự xấu, nhưng luôn có một thứ tự tốt. Điều này gợi ta nhớ đến gì trong CSP?
Remember, CSPs, if you try to do your backtracking search, that might be expensive.
Nhớ lại, trong CSP, nếu bạn dùng tìm kiếm quay lui, nó có thể tốn kém.
But if you arrange things just right, then you can be greedy if you did this sort of message passing algorithm for constraint satisfaction — for enforcing our consistency.
Nhưng nếu sắp xếp mọi thứ đúng cách, thì bạn có thể dùng tham lam, nếu bạn dùng thuật toán truyền thông điệp này cho việc thỏa mãn ràng buộc, để đảm bảo tính nhất quán cung.
This is a very similar thing. They're very deeply related, in fact. And there's also notions like cutset conditioning.
Điều này rất giống. Thực ra chúng liên hệ rất sâu sắc với nhau. Cũng có khái niệm như cutset conditioning.
So just like in a CSP, if you don't have a polytree, but if a couple nodes would go away, you would. You can do the same thing here.
Giống như trong CSP, nếu bạn không có polytree, nhưng bỏ vài nút đi thì sẽ có. Bạn có thể làm điều tương tự ở đây.
You can sort of instantiate the problematic nodes in all the different ways, which creates a number of subproblems that's exponential in the size of the cutset.
Bạn có thể gán giá trị cho các nút gây vấn đề theo mọi cách khác nhau, việc này tạo ra một số bài toán con là hàm mũ theo kích thước của cutset.
But if what's left is a polytree, then you have an efficient algorithm over what's left. So you can see this sort of same idea from before.
Nhưng nếu phần còn lại là một polytree, thì bạn có thuật toán hiệu quả cho phần còn lại. Vậy bạn thấy cùng ý tưởng như trước.
Take a CSP, find a cutset that leaves a tree-shaped residual, and now everything's efficient. You can do the same thing here.
Lấy một CSP, tìm cutset để phần dư có dạng cây, và giờ mọi thứ đều hiệu quả. Bạn có thể làm điều tương tự ở đây.
Take a Bayes' Net, find a relatively small set of things that leave a polytree residual. You have to work out what residual means here. And then you do something efficient on what's left.
Lấy một mạng Bayes, tìm một tập tương đối nhỏ các nút để phần dư là một polytree. Bạn phải tự làm rõ phần dư ở đây nghĩa là gì. Rồi bạn làm một việc hiệu quả trên phần còn lại.
OK. So you can think about the specifics there. All right. What do we have?
OK. Bạn có thể tự nghĩ về các chi tiết cụ thể. Được rồi. Ta đã có những gì?
We talked about representation. What is a Bayes' Net? What joint probability model does it represent? We talked about conditional independence.
Ta đã nói về biểu diễn. Mạng Bayes là gì? Nó biểu diễn mô hình xác suất đồng thời nào? Ta đã nói về tính độc lập có điều kiện.
What can you conclude about which variables do and do not influence each other given other evidence? We talked about various things and probabilistic inference.
Bạn có thể kết luận gì về việc biến nào có và không ảnh hưởng lẫn nhau khi đã biết các bằng chứng khác? Chúng ta đã nói về nhiều vấn đề và về suy luận xác suất.
How to do it exactly in exponential time by enumeration, how to do it exactly in exponential time, but often faster with variable elimination. We talked about why this thing is NP-hard.
Cách thực hiện chính xác trong thời gian hàm mũ bằng phép liệt kê, tức là làm chính xác trong thời gian hàm mũ, nhưng thường nhanh hơn với khử biến. Chúng ta cũng đã nói vì sao bài toán này là NP-hard.
Next time, we're going to talk about sampling, which is a way of doing inference really, really fast. And maybe getting the wrong answer, which is another way of attacking these problems.
Lần tới, chúng ta sẽ nói về lấy mẫu, là một cách suy luận cực kỳ nhanh. Và có thể cho ra đáp án sai, đó là một cách khác để giải quyết các bài toán này.
So we'll talk about sampling next time, and then get to learning later in the course. All right. We'll stop there. Thank you.
Vậy lần tới chúng ta sẽ nói về lấy mẫu, rồi sau đó sẽ chuyển sang phần học máy trong khóa. Được rồi. Chúng ta dừng ở đây. Cảm ơn các bạn.
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.