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ả.
[SIDE CONVERSATION] PROFESSOR: OK, let's get started.
[TRÒ CHUYỆN RIÊNG] GIÁO SƯ: Được rồi, chúng ta bắt đầu nhé.
So we've been talking about Bayes nets, which are representations of probabilistic models over a domain of variables.
Chúng ta đã học về mạng Bayes, là cách biểu diễn các mô hình xác suất trên một miền các biến.
And in particular, we've been talking about how to answer questions about various quantities, queries, given evidence, and how to do that in as efficient way as possible.
Cụ thể, chúng ta đã nói về cách trả lời các câu hỏi về nhiều đại lượng khác nhau, tức các truy vấn, khi có bằng chứng, và làm sao để làm việc đó hiệu quả nhất có thể.
Today, we're going to talk about an entirely new kind of approach for doing inference in Bayes nets, which involves sampling.
Hôm nay, chúng ta sẽ nói về một cách tiếp cận hoàn toàn mới để suy luận trong mạng Bayes, đó là lấy mẫu.
So mostly, we're going to take a huge step back, forget everything we know about variable elimination, everything we know about actually constructing joint distributions, and instead, talk about a completely different way to do inference in the distribution represented by a Bayes net.
Về cơ bản, chúng ta sẽ lùi lại một bước lớn, quên mọi thứ đã biết về khử biến, mọi thứ về việc thực sự xây dựng phân phối đồng thời, và thay vào đó, nói về một cách hoàn toàn khác để suy luận trên phân phối được biểu diễn bởi một mạng Bayes.
So let's remember what a Bayes net actually represents. So it's a representation of a probabilistic model over some domain of variables. You have a directed acyclic graph.
Trước hết hãy nhớ lại mạng Bayes thực sự biểu diễn gì. Nó là biểu diễn của một mô hình xác suất trên một miền các biến. Ta có một đồ thị có hướng không chu trình.
You have one node per random variable, and living inside each node is a conditional probability that specifies the probability of all the outcomes of that node, given an assignment to the parents.
Mỗi biến ngẫu nhiên ứng với một nút, và bên trong mỗi nút là một xác suất có điều kiện cho biết xác suất của mọi kết quả của nút đó, với một phép gán cho các nút cha.
This encodes a joint distribution. And we've seen this before a bunch of times in recent lectures.
Nó mã hóa một phân phối đồng thời. Ta đã thấy điều này nhiều lần trong các bài gần đây.
But today, we're really going to need to remember what things you have to multiply together to actually get the probability of an event in this joint distribution.
Nhưng hôm nay, ta thật sự cần nhớ phải nhân những gì với nhau để có được xác suất của một sự kiện trong phân phối đồng thời này.
So a Bayes net implicitly — explicitly, it's a bunch of little local conditional probabilities. And implicitly, it encodes a joint distribution over all those variables that's given by the following formula.
Vậy mạng Bayes ngầm định — tường minh thì nó là một loạt xác suất có điều kiện cục bộ nhỏ. Và ngầm định, nó mã hóa một phân phối đồng thời trên tất cả các biến đó, cho bởi công thức sau.
So if you give me a complete assignment to all the variables x1 through xn, the probability under the Bayes net is the product of all the conditional probabilities for each of those x sub i given the parents.
Nếu bạn cho tôi một phép gán đầy đủ cho mọi biến x1 đến xn, xác suất theo mạng Bayes là tích của các xác suất có điều kiện của từng x_i cho trước các nút cha.
Now, where do these all come from? Each node of the Bayes net representing a variable has those tables buried in it, OK?
Vậy những giá trị này đến từ đâu? Mỗi nút của mạng Bayes, đại diện cho một biến, chứa sẵn các bảng đó, đúng không?
What we wanted to do with Bayes nets was answer questions, like, hey, what's the probability of this variable given some piece of evidence we observe? What's the probability of this disease given these tests?
Với mạng Bayes, ta muốn trả lời các câu hỏi, ví dụ, xác suất của biến này là bao nhiêu khi ta quan sát được một bằng chứng nào đó? Xác suất mắc bệnh này là bao nhiêu với các kết quả xét nghiệm này?
What's the probability that my battery is dead given that this light is blinking in my car? What's the probability of this insurance parameter, or whatever it is, given the known quantities?
Xác suất ắc quy hết điện là bao nhiêu khi đèn trên xe tôi đang nhấp nháy? Xác suất của tham số bảo hiểm này, hay gì đó, là bao nhiêu khi biết các đại lượng đã cho?
And for large Bayes nets, it wasn't practical to construct the whole joint distribution because it's exponentially large.
Với các mạng Bayes lớn, việc xây dựng toàn bộ phân phối đồng thời là không thực tế vì nó lớn theo cấp số mũ.
And even if you had it sitting there in memory, it wouldn't be practical to answer queries because most queries involve a small number of variables, which means you would have to sum out over all the various combinations of settings of the other variables, and that would take exponential time.
Và dù nó có nằm sẵn trong bộ nhớ, trả lời truy vấn vẫn không thực tế vì hầu hết truy vấn chỉ liên quan ít biến, nghĩa là bạn phải lấy tổng trên mọi tổ hợp giá trị của các biến còn lại, và việc đó tốn thời gian theo cấp số mũ.
So we have this algorithm variable elimination, which involved alternating between inflating little bits of the Bayes net and summing out variables you don't want, where we sum things out aggressively before the factors that we build have a chance to get exponentially large.
Vì vậy ta có thuật toán khử biến, luân phiên giữa việc kết hợp các phần nhỏ của mạng Bayes và lấy tổng bỏ các biến không cần, trong đó ta lấy tổng sớm trước khi các nhân tử ta xây dựng kịp lớn lên theo cấp số mũ.
How big do they get? Well, in general, if there are d elements in the domain, and there are k variables in a factor, you're going to have factors of size d to the k.
Chúng lớn đến mức nào? Nói chung, nếu miền có d phần tử và một nhân tử có k biến, thì nhân tử có kích thước d mũ k.
That means k can't get too big. What happens in an arbitrary Bayes net? Sometimes there aren't any orderings that are going to give you only small factors. And it can still be very expensive.
Nghĩa là k không được quá lớn. Điều gì xảy ra với một mạng Bayes bất kỳ? Đôi khi không có thứ tự nào cho ra các nhân tử nhỏ. Và chi phí vẫn có thể rất lớn.
The ordering can matter a lot. We saw cases where there were networks that had good orderings and bad orderings. There's also networks that only have good orderings.
Thứ tự có thể rất quan trọng. Ta đã thấy có những mạng có thứ tự tốt và thứ tự xấu. Cũng có mạng chỉ có thứ tự tốt.
And there's also networks that have no good orderings. Sometimes, there's a good ordering and a bad ordering, but it's really hard to find the good ones.
Và cũng có mạng không có thứ tự tốt nào. Đôi khi có cả thứ tự tốt lẫn xấu, nhưng rất khó tìm ra thứ tự tốt.
But in general, variable elimination was better than inference by enumeration, even though in worst case, everything was exponential in the size of the Bayes net.
Nhưng nhìn chung, khử biến tốt hơn suy luận bằng liệt kê, dù trong trường hợp xấu nhất, mọi thứ đều là hàm mũ theo kích thước mạng Bayes.
And we saw why that has to be because Bayes nets can compactly encode satisfiability instances.
Và ta đã thấy vì sao phải thế: mạng Bayes có thể mã hóa gọn các bài toán thỏa mãn mệnh đề (satisfiability).
So we have this algorithm variable elimination, which, basically, is going to add a ton of entries of the joint distribution together in a, hopefully, efficient way by moving some of the sums in the expression.
Vậy ta có thuật toán khử biến, về cơ bản sẽ cộng một lượng lớn các giá trị của phân phối đồng thời lại, hy vọng là hiệu quả, bằng cách dời một số phép tổng trong biểu thức.
But it might still be slow. Today, we're going to do something entirely different. Today, we're going to do an algorithm that's really, really fast. But the answer might be totally wrong.
Nhưng nó vẫn có thể chậm. Hôm nay ta sẽ làm một thứ hoàn toàn khác. Hôm nay ta sẽ học một thuật toán cực kỳ nhanh. Nhưng đáp án có thể sai hoàn toàn.
And this is different than how we normally approach problems in this class. Normally, we have an exact answer. And we're going to find it.
Điều này khác với cách ta thường tiếp cận các bài toán trong môn này. Thông thường, ta có một đáp án chính xác. Và ta sẽ tìm ra nó.
And we're going to try to make it as efficient as possible, either in a way that we can show the worst case computational complexity isn't too bad, or maybe the worst case complexity is bad, but it's still, in practice, feasible for lots of problems.
Và ta cố làm cho nó hiệu quả nhất có thể, hoặc theo cách mà ta chứng minh được độ phức tạp trường hợp xấu nhất không quá tệ, hoặc có thể độ phức tạp xấu nhất là tệ, nhưng trong thực tế vẫn khả thi với nhiều bài toán.
Today, we're going to talk about sampling-based methods, which you can run them as quickly as you want. But if you don't run them long enough, your answer may not be very accurate.
Hôm nay ta nói về các phương pháp dựa trên lấy mẫu, mà bạn có thể chạy nhanh tùy ý. Nhưng nếu không chạy đủ lâu, đáp án có thể không chính xác lắm.
And so here there's a trade-off between compute and accuracy, and that's not the normal trade-off we have. So what is sampling? There's actually two entirely different reasons you might sample.
Vậy ở đây có sự đánh đổi giữa tính toán và độ chính xác, và đó không phải sự đánh đổi thường gặp. Vậy lấy mẫu là gì? Thật ra có hai lý do hoàn toàn khác nhau để bạn lấy mẫu.
So sample is a lot like doing repeated simulation. In fact, we've already done some sampling in this class.
Lấy mẫu rất giống việc mô phỏng lặp lại. Thực ra, ta đã làm một ít lấy mẫu trong môn này rồi.
We did sampling when we did reinforcement learning, where we were like, hey, what's the value of this state? Or what does this action do? And so we'd try it, and then we tried again.
Chúng ta đã lấy mẫu khi học tăng cường, khi đó chúng ta hỏi: giá trị của trạng thái này là bao nhiêu? Hoặc hành động này làm gì? Thế là ta thử, rồi thử lại.
And we tried again, and again, and again, and again. And if we tried it enough times, those probabilities would start to converge to the right values. That use of sampling is learning.
Và thử đi thử lại, hết lần này đến lần khác. Nếu thử đủ nhiều lần, các xác suất đó sẽ bắt đầu hội tụ về giá trị đúng. Cách dùng lấy mẫu đó là để học.
So in that case, you don't actually know the distribution. Like, we didn't know the distribution of the slot machine.
Trong trường hợp đó, thực ra bạn không biết phân phối. Như lúc ta không biết phân phối của máy đánh bạc.
And we had to keep playing the slot machine, so that we could learn how often it pays off. So that's a case of learning. You don't know the various probabilities.
Và ta phải tiếp tục chơi máy đánh bạc, để học xem nó trúng thưởng thường xuyên đến mức nào. Đó là trường hợp học. Bạn không biết các xác suất.
But you're going to interact with a real world to discover them. That's learning. We're going to use sampling today for a very different purpose, which in a lot of ways is a little counterintuitive.
Nhưng bạn tương tác với thế giới thực để khám phá ra chúng. Đó là học. Hôm nay ta dùng lấy mẫu cho một mục đích rất khác, và theo nhiều cách thì hơi phản trực giác.
Today, we're going to use it for inference. And that means, we're going to go to our Bayes net, in which we know all of the probabilities. How do we get them?
Hôm nay ta dùng nó để suy luận. Nghĩa là ta sẽ làm việc với mạng Bayes mà ta biết hết mọi xác suất. Ta có chúng bằng cách nào?
Maybe, they were handed to us. Maybe, we actually got them from learning. But right now, there's a Bayes net right in front of us.
Có thể ai đó đưa cho ta. Có thể ta học được chúng. Nhưng bây giờ, mạng Bayes nằm ngay trước mặt ta.
And it tells us that the probability of this variable, given the settings of these other variables is 0.37. OK, so we actually know all the probabilities, but we're going to sample anyway.
Và nó cho biết xác suất của biến này, với giá trị đã cho của các biến khác, là 0.37. Vậy là ta biết hết các xác suất, nhưng ta vẫn lấy mẫu.
When you sample in a network that you already know, it looks like simulation. You walk along the network, and you say, hmm, well, if this happened, let's see what would happen at this variable.
Khi lấy mẫu trong một mạng mà bạn đã biết, nó giống như mô phỏng. Bạn đi dọc theo mạng và nói, ừm, nếu điều này xảy ra thì ở biến này sẽ xảy ra gì.
And you flip some coins. And you get a sample out that is a sort of probabilistic simulation.
Và bạn tung vài đồng xu. Rồi bạn thu được một mẫu, đó là một dạng mô phỏng xác suất.
And in this case, the reason you're getting a sample is not because you don't actually know or are not able to compute the underlying probabilities.
Và ở đây, lý do bạn lấy mẫu không phải vì bạn không biết hoặc không tính được các xác suất bên dưới.
It's because sampling turns out to be faster than computing the right answer through brute force.
Mà vì lấy mẫu hóa ra nhanh hơn việc tính đáp án đúng bằng vét cạn.
So here's the basic idea in sampling, regardless of whether you're doing it for learning purposes or for speed purposes.
Vậy ý tưởng cơ bản của lấy mẫu, dù bạn làm để học hay để tăng tốc, là thế này.
The basic idea is we're going to draw n samples, where n might be very large, from some sampling distribution s. And we get to define the sampling distribution.
Ta rút n mẫu, trong đó n có thể rất lớn, từ một phân phối lấy mẫu s nào đó. Và ta được tự định nghĩa phân phối lấy mẫu.
We'll see several different examples today of different sampling distributions that are given by the different algorithms we're going to cover for sampling. But there's some sampling distribution that hopefully we can characterize.
Hôm nay ta sẽ thấy vài ví dụ khác nhau về các phân phối lấy mẫu do các thuật toán lấy mẫu khác nhau mà ta sẽ học tạo ra. Nhưng luôn có một phân phối lấy mẫu mà hy vọng ta mô tả được. Bạn rút n mẫu từ đó.
You're going to draw n samples from that. Inside those samples, which are all events that look like outcomes of s, and you're going to compute an approximate posterior probability.
Trong các mẫu đó, vốn đều là các sự kiện trông như kết quả của s, bạn sẽ tính một xác suất hậu nghiệm xấp xỉ. Bất cứ truy vấn nào bạn muốn trả lời, bạn tính nó trên các mẫu.
Whatever query you're trying to answer, you'll compute it over your samples. And that's efficient because it scales in terms of time with the number of samples you take.
Cách này hiệu quả vì thời gian tăng theo số mẫu bạn lấy. Muốn chính xác hơn thì lấy thêm mẫu.
If you want it to be more accurate, you take more samples. And now, you might think, there can't be really a free lunch there. There's got to be some trade-off between accuracy and time.
Có thể bạn nghĩ không có bữa trưa miễn phí ở đây. Chắc chắn phải có đánh đổi giữa độ chính xác và thời gian. Và nếu phân phối rất khó, có thể một số truy vấn cần rất nhiều mẫu mới chính xác.
And if I have a really tricky distribution, maybe some queries need a lot of samples in order to get accurate. There are going to be trade-offs like that.
Sẽ có những đánh đổi như vậy. Nhưng bạn luôn có thể dừng lại và nhận đáp án sai.
But you can always stop it and get the wrong answer.
Điều ta muốn chứng minh là khi n tăng, khi n tiến đến vô cùng, thủ tục này hội tụ về xác suất thật mà ta muốn tính.
What you want to show is you want to show that as n grows, as n goes to infinity, this procedure is going to converge to the true probability you actually want it to compute.
Vì vậy mỗi khi giới thiệu một thuật toán lấy mẫu, ta cần lập luận rằng nếu rút nhiều mẫu từ đó, ta sẽ thực sự được đáp án đúng.
And so every time we introduce a sampling algorithm, we need to argue that, if I draw a bunch of samples from this, I'll actually get the right answer.
Dù tất nhiên, nếu chỉ rút ít mẫu thì là phụ thuộc vào may rủi. Được rồi.
Even though, of course, if I draw a small number of samples, it's the luck of the draw. All right. So we're going to have an atomic building block when we do sampling.
Khi lấy mẫu, ta sẽ có một khối cơ bản. Đó là ta cần lấy mẫu được từ các phân phối lớn và mạng Bayes. Sẽ có các thuật toán cho việc đó, trong đó bạn đi dọc mạng, từng biến một theo thứ tự phù hợp.
And that is, we need to be able to sample from big distributions and Bayes nets.
And there's going to be algorithms for that where you walk along the network going variable by variable in an appropriate way.
Nhưng trước khi làm vậy, ta cần hiểu cách lấy mẫu từ một phân phối đa thức đơn lẻ. Ví dụ, ta có phân phối này.
But before we can do that, we need to understand how to sample from a single multinomial distribution. So let's say, for example, we have this distribution here. There's a random variable c.
Có một biến ngẫu nhiên c. Nó là màu. Đỏ, xanh lá hoặc xanh dương. Và các xác suất nằm ngay trước mặt tôi. Nhớ là tôi không làm việc học.
It's a color. It's red, green, or blue. And I have right in front of me the probabilities. Now, remember, I'm not doing learning.
Tôi biết các xác suất. Tôi biết đỏ xuất hiện 60% số lần. Nhưng tôi sẽ rút một mẫu từ phân phối này. Nên tôi sẽ tung một loại đồng xu nào đó.
I know the probabilities. I know that red happens 60% of the time. But I'm going to draw a sample from this distribution. So I'm going to flip some kind of coin.
Về mặt khái niệm, tôi tung một đồng xu ba mặt đỏ, xanh lá và xanh dương, trong đó mặt đỏ xuất hiện 60% số lần, mặt xanh lá 10% số lần, và cứ thế.
And I'm going to basically flip — conceptually, I'm going to flip a three-sided coin that says, red, green, and blue, where the red side comes up 60% of the time, and the green side comes up 10% of the time, and so on.
Nhưng làm sao có được đồng xu này? Làm sao thực sự lấy được một mẫu đơn này? Tôi sẽ tạo ra một mẫu theo phân phối này từ một phân phối lấy mẫu nguyên thủy, chẳng hạn trên khoảng số thực từ 0 đến 1.
But how am I going to get this coin? How am I going to actually get this single sample?
Ví dụ, nếu bạn gọi hàm random, bạn sẽ được một số phân phối đều trong khoảng từ 0 đến 1.
Well, what I'm going to do is I'm going to manufacture a sample over this distribution from a primitive sampling distribution over, say, the real interval from 0 to 1.
Rồi bước hai là lấy mẫu trên khoảng 0, 1 đó từ một phân phối lấy mẫu nguyên thủy trên, chẳng hạn, khoảng số thực từ 0 đến 1.
So for example, if you call random, you'll get a uniformly distributed number between 0 and 1.
Ví dụ, nếu bạn gọi hàm random, bạn sẽ nhận được một số phân bố đều trong khoảng từ 0 đến 1.
And then step two is to take that sample over the 0, 1 interval and convert it into a sample over the event space for c. How do we do that?
Rồi bước hai là lấy mẫu đó trên khoảng 0, 1 rồi chuyển nó thành một mẫu trên không gian sự kiện của c. Làm thế nào?
We divide up that real line into subintervals where the size of each subinterval is equal to the probability of the outcome.
Ta chia đoạn thẳng thực đó thành các khoảng con, sao cho độ dài của mỗi khoảng con bằng xác suất của kết quả tương ứng.
So for example, I might grab my number between 0 and 1 and say, well, if it's between 0 and 0.6, I'll call that an instance of red.
Ví dụ, tôi lấy một số trong khoảng từ 0 đến 1 và nói: nếu nó nằm giữa 0 và 0.6, thì tôi coi đó là một mẫu màu đỏ.
And if it's between 0.6 and 0.7, I'll call that an instance of green. And if it's between 0.7 and 0.1, I'll call that an instance of blue. OK, so I could do that.
Nếu nó nằm giữa 0.6 và 0.7, thì tôi coi đó là một mẫu màu xanh lá. Và nếu nó nằm giữa 0.7 và 0.1, thì tôi coi đó là một mẫu màu xanh dương. Vậy là ta làm được rồi.
Let's say, my random my call to random returns 0.83. I would look, and I would say, well, that's not in the first bucket. That's not in the second bucket.
Giả sử lời gọi random trả về 0.83. Tôi sẽ xem xét và nói: nó không nằm trong khoảng đầu tiên. Cũng không nằm trong khoảng thứ hai.
That's in the third bucket. So I'm going to say, I just sampled the value blue. Now, why would I ever want to do that? I could draw a bunch of samples.
Nó nằm trong khoảng thứ ba. Vậy tôi vừa lấy mẫu được giá trị xanh dương. Vậy tại sao ta lại muốn làm vậy? Tôi có thể lấy một loạt mẫu.
If I sampled eight times, I might get five reds, two blues, and one green. Do those seem plausible given these probabilities? They're plausible. Why would I ever want to do this?
Nếu lấy tám lần, tôi có thể được năm đỏ, hai xanh dương và một xanh lá. Kết quả này có hợp lý với các xác suất đó không? Có thể xảy ra. Vậy tại sao ta lại muốn làm thế này?
Well, I basically wouldn't, right? I already know the probability of red. Drawing 10 samples, and this time I got seven, instead of six. That's really just introducing variance into the process.
Thực ra thì về cơ bản là không cần, đúng không? Tôi đã biết xác suất của màu đỏ rồi. Lấy 10 mẫu, và lần này tôi được bảy chứ không phải sáu. Điều đó chỉ đưa thêm phương sai vào quá trình.
So for this one dimensional single variable, I wouldn't actually have much use for sampling from this known distribution.
Vì vậy với một biến đơn, một chiều như thế này, tôi thực sự không có nhiều lý do để lấy mẫu từ một phân phối đã biết.
However, in a Bayes net, there is a use for sampling from the entire network because listing all the outcomes is too expensive, even if I can create them given infinite time.
Tuy nhiên, trong một mạng Bayes, việc lấy mẫu từ toàn bộ mạng là hữu ích vì liệt kê mọi kết quả thì quá tốn kém, dù là tôi có thể tạo ra chúng nếu có thời gian vô hạn.
All right. So here's what we're going to do today now that we have this building block of being able to sample from any given single multinomial distribution.
Được rồi. Hôm nay ta sẽ làm như sau, khi đã có khối xây dựng này: lấy mẫu từ bất kỳ phân phối đa thức đơn nào.
So we'll think of that as a primitive now. We're going to look at four different algorithms for drawing samples, and think about what they do, and what we can understand about them.
Giờ ta coi đó là một thao tác nguyên thủy. Ta sẽ xem xét bốn thuật toán khác nhau để lấy mẫu, xem chúng làm gì, và hiểu được gì về chúng.
Yes. Questions before we start.
Vâng. Có câu hỏi nào trước khi bắt đầu không?
STUDENT
[INAUDIBLE] PROFESSOR: Wow, that's the first time I've ever been asked to turn my mic up. How's that? All right.
[KHÔNG NGHE RÕ] GIÁO SƯ: Chà, lần đầu tiên có người yêu cầu tôi tăng âm lượng mic. Thế này được chưa? Được rồi.
Any other questions? Any other volume requests? OK, so we're going to do some prior sampling.
Còn câu hỏi nào khác không? Còn yêu cầu nào về âm lượng không? Vậy ta bắt đầu với prior sampling.
So I like to think of samples as snapshots, assignments to random variables that come along — come across a conveyor belt. And in the prior sampling algorithm, we're just going to draw samples from the distribution of interest.
Tôi hay hình dung các mẫu như những ảnh chụp nhanh, là các phép gán cho các biến ngẫu nhiên chạy qua một băng chuyền. Trong thuật toán prior sampling, ta chỉ việc lấy các mẫu từ phân phối mà ta quan tâm.
So this is the basic building block. Here's a little Bayes net. This is a Bayes net that says, half the time the sky is cloudy, that's P of c.
Đây là khối xây dựng cơ bản. Đây là một mạng Bayes nhỏ. Mạng này nói rằng một nửa thời gian trời có mây, đó là P của c.
And then there's a sprinkler on my lawn, and there's a dependence between the cloudy and the sprinkler. So what does this look like? If it's cloudy, the sprinkler is usually off.
Rồi có một vòi phun nước trên bãi cỏ của tôi, và có sự phụ thuộc giữa mây và vòi phun. Nó trông thế nào? Nếu trời có mây, vòi phun thường tắt.
If it's not cloudy, half the time the sprinkler is on. There's also a dependence between cloudy and rain. So when it's cloudy, it usually rains. And when it's not cloudy, it usually doesn't.
Nếu trời không mây, một nửa thời gian vòi phun bật. Cũng có sự phụ thuộc giữa mây và mưa. Khi trời có mây, thường là có mưa. Và khi không có mây, thường là không mưa.
And then in addition to sometimes it's cloudy, sometimes there's a sprinkler on, and sometimes there's a rain, sometimes my grass is wet, OK? So how does that work?
Và ngoài ra, khi thì trời có mây, khi thì vòi phun bật, khi thì có mưa, và khi thì cỏ của tôi bị ướt, được chứ? Vậy nó hoạt động thế nào?
Basically, the sprinkler can make my grass wet, and so can the rain.
Vòi phun có thể làm cỏ ướt, mưa cũng vậy.
And so there is a conditional probability table here that describes how w responds to s and r that basically says, if it's either s or r, then it's probably wet grass.
Ở đây có một bảng xác suất có điều kiện mô tả cách w phụ thuộc vào s và r: về cơ bản, nếu có s hoặc r, thì nhiều khả năng cỏ ướt.
But if there is neither rain nor sprinkler, there's probably not wet grass. OK, so everybody get that Bayes net in your head because we're going to use this Bayes net over and over again.
Nhưng nếu không có mưa cũng không có vòi phun, thì nhiều khả năng cỏ không ướt. Mọi người hãy nhớ kỹ mạng Bayes này vì ta sẽ dùng nó đi dùng lại.
It's an interesting Bayes net because the variables separate. But then they come back together at the bottom. So if I look at this, what can I do?
Đây là một mạng Bayes thú vị vì các biến tách ra, rồi lại gặp nhau ở phía dưới. Vậy với mạng này ta làm được gì?
What do I know how to do with this Bayes net? Given time, I know how to create the whole joint distribution. So I could do that right now.
Ta biết làm gì với mạng Bayes này? Có thời gian thì ta biết tạo ra toàn bộ phân phối đồng thời. Tôi có thể làm ngay bây giờ.
I could ask you, hey, what's the probability that it's cloudy, there's a sprinkler, it's rainy, but the grass is dry? We could compute that right now by multiplying a bunch of conditional probabilities together.
Tôi có thể hỏi: xác suất để trời có mây, có vòi phun, có mưa, nhưng cỏ khô là bao nhiêu? Ta tính được ngay bằng cách nhân một loạt xác suất có điều kiện với nhau.
We're going to do something similar to that. Instead of computing an entry of the joint distribution, we are going to create an event which is an assignment to these four variables.
Ta sẽ làm một việc tương tự. Thay vì tính một phần tử của phân phối đồng thời, ta sẽ tạo ra một sự kiện, là một phép gán cho bốn biến này.
But we're going to create it by walking along the Bayes net. So we'll go to cloudy. And we'll say, well, sometimes it's cloudy, and sometimes it's not. My samples will come out both ways.
Nhưng ta sẽ tạo nó bằng cách đi dọc theo mạng Bayes. Ta đến nút cloudy. Và nói rằng khi thì trời có mây, khi thì không. Các mẫu của tôi sẽ ra cả hai trường hợp.
Right now, it's time to pick a single sample. So I'm going to flip a coin. And here, it's going to be a 50/50 coin. And maybe it turns out it's plus cloudy.
Bây giờ là lúc chọn một mẫu đơn. Vậy tôi tung một đồng xu. Và ở đây, nó là đồng xu 50/50. Có thể kết quả là có mây.
So green here will be plus, and red will be minus. All right. Time to go to the next variable because I don't have a complete assignment yet. So I'll go to the sprinkler.
Vậy màu xanh lá ở đây là cộng, còn màu đỏ là trừ. Được rồi. Đến lúc sang biến tiếp theo vì tôi chưa có một phép gán hoàn chỉnh. Vậy tôi đến vòi phun.
I've already picked plus c. So now, I'm going to pick a value for s. It's probably going to be minus s.
Tôi đã chọn +c rồi. Giờ tôi sẽ chọn một giá trị cho s. Nhiều khả năng sẽ là -s.
But there's a 10% chance that when I flip this 90:10 coin, it'll come out plus s. So let's flip the coin. OK, it came out minus. I go to the next variable, rain.
Nhưng có 10% khả năng là khi tôi tung đồng xu 90:10 này, thì nó ra plus s. Giờ ta tung đồng xu nhé. OK, ra minus. Tôi chuyển sang biến tiếp theo, rain.
And it looks like I have an 80% chance of getting a sample of plus r, and a 20% chance of minus r. It comes out plus r.
Ở đây tôi có 80% khả năng lấy được mẫu plus r, và 20% là minus r. Nó ra plus r.
And then I go down here to the wet grass. There's no sprinkler, but there is a rain. And so the probability of wet grass is 90%.
Rồi tôi đi xuống wet grass ở đây. Không có sprinkler, nhưng có rain. Nên xác suất cỏ ướt là 90%.
I flip another 90% coin, and I get plus wet grass. So I walked along this network.
Tôi tung thêm một đồng xu 90%, và được plus wet grass. Vậy là tôi đã đi dọc theo mạng này.
If I did this again, and I flipped those coins again at each node, next time, I'm presumably going to get a different sample, and then a different sample, and then a different sample.
Nếu làm lại và tung lại các đồng xu đó tại mỗi nút, lần sau chắc chắn tôi sẽ được một mẫu khác, rồi một mẫu khác nữa, và một mẫu khác nữa.
Each time I get a sample, I write it down, OK? So my first sample was plus c, minus s, plus r, plus w. And I can do that again, and again, and again.
Mỗi lần lấy được một mẫu, tôi ghi nó xuống, OK? Mẫu đầu tiên của tôi là plus c, minus s, plus r, plus w. Và tôi có thể làm lại, lặp đi lặp lại.
I can draw as many samples as I want. We could ask some questions like, OK, that first sample, how often is that going to happen?
Tôi có thể lấy bao nhiêu mẫu tùy ý. Ta có thể hỏi, OK, mẫu đầu tiên đó, nó sẽ xảy ra thường xuyên đến mức nào?
I mean, will it always come out that way? Certainly not. What's the probability that I will get the sample plus c, minus s, plus r, plus w?
Ý tôi là, lúc nào nó cũng ra như vậy sao? Chắc chắn là không. Xác suất để tôi được mẫu plus c, minus s, plus r, plus w là bao nhiêu?
Well, the probability that I'm going to get the plus c part, that's going to be true of half the samples.
Xác suất để tôi được phần plus c đúng với một nửa số mẫu.
And then of those samples where I got a plus c, the probability that I'm going to get a minus s, that's going to be true of 90% of those samples.
Rồi trong những mẫu mà tôi được plus c, xác suất để được minus s đúng với 90% số mẫu đó.
And then when I go to plus r, it's going to be 80% of the samples, and then 90% of the samples.
Rồi khi sang plus r, là 80% số mẫu, và sau đó là 90% số mẫu.
And if I multiply those together, I can determine the probability of the sample, which is just the probability of this event in the distribution described by the Bayes net.
Và nếu nhân các số đó với nhau, tôi xác định được xác suất của mẫu, chính là xác suất của sự kiện này trong phân phối được mô tả bởi mạng Bayes.
So when I draw samples according to this procedure of walking node by node, and just flipping the coin the way it says in that node, I end up with samples coming out in a way that exactly matches the probabilities in the joint distribution, OK?
Vậy khi tôi lấy mẫu theo thủ tục này, đi từng nút một, và tung đồng xu theo đúng những gì ghi ở nút đó, các mẫu tạo ra sẽ khớp chính xác với các xác suất trong phân phối đồng thời, OK?
Does that make sense? You might wonder, why the heck would I do this, right? Because I can compute those probabilities. But that is the probability of each sample type.
Mọi người hiểu chứ? Bạn có thể thắc mắc, sao lại phải làm vậy, đúng không? Vì tôi có thể tính các xác suất đó. Nhưng đó là xác suất của từng loại mẫu.
So here's the prior sampling algorithm. If you're going to draw n samples — sorry. You can draw as many samples as you want. For each sample, you do the following.
Đây là thuật toán prior sampling. Nếu bạn định lấy n mẫu — xin lỗi. Bạn có thể lấy bao nhiêu mẫu tùy ý. Với mỗi mẫu, bạn làm như sau.
You visit each node, sampling a value for that node given the parents. And so you say, what happens if I visit a node before a parent? You can't do that, right?
Bạn duyệt từng nút, lấy mẫu một giá trị cho nút đó với điều kiện các nút cha. Vậy nếu duyệt một nút trước nút cha của nó thì sao? Không làm được, đúng không?
So you have to do this in a topological ordering of this, where you don't sample something until all it's parents are sampled. How do I know there's such an order?
Nên bạn phải làm theo thứ tự tô-pô, tức là không lấy mẫu một nút cho đến khi tất cả các nút cha của nó đã được lấy mẫu. Làm sao biết có thứ tự như vậy?
It's an acyclic graph, OK?
Vì đồ thị này là phi chu trình, OK?
After you sample all the nodes, you return it. That's your sample. How many samples do you want to draw? That's up to you.
Sau khi lấy mẫu tất cả các nút, bạn trả về kết quả. Đó là mẫu của bạn. Bạn muốn lấy bao nhiêu mẫu? Tùy bạn.
So we already talked about this process generating samples with a certain probability. So let's parse this expression. This is a sampling distribution. S is a sampling distribution.
Ta đã nói về quá trình này, nó sinh ra các mẫu với một xác suất nhất định. Giờ ta phân tích biểu thức này. Đây là một phân phối lấy mẫu. S là một phân phối lấy mẫu.
It's like P, except when I write it down, I might or not actually be a probability. But here S is a sampling distribution. PS is prior sampling.
Nó giống P, trừ việc khi tôi viết ra, nó có thể không thực sự là xác suất. Nhưng ở đây S là phân phối lấy mẫu. PS là prior sampling.
And the probability that I'll get the sequence x1 through xn as the assignment from the sample, the probability I'll get that snapshot, is the product of the probability of each piece given its parents.
Và xác suất để tôi được dãy x1 đến xn làm phép gán của mẫu, xác suất để tôi được bức ảnh chụp đó, là tích của xác suất từng phần với điều kiện các nút cha của nó.
And that, as we said, is just the probability of that same exact event under the joint distribution.
Và như ta đã nói, đó chính là xác suất của đúng sự kiện đó trong phân phối đồng thời.
So we found a way of drawing events from the full joint distribution with probability P. That's not too hard.
Vậy ta đã tìm ra cách lấy các sự kiện từ phân phối đồng thời đầy đủ với xác suất P. Không khó lắm.
So what do we know? Let's say, we take some event, like x1 through n, and we draw some samples. We might not get any samples of that event.
Vậy ta biết gì? Giả sử ta lấy một sự kiện nào đó, như x1 đến n, và ta lấy một số mẫu. Ta có thể không được mẫu nào của sự kiện đó.
We might get a lot. Let n be the number of samples you get of a certain event.
Hoặc có thể được rất nhiều. Gọi n là số mẫu bạn có được của một sự kiện nào đó.
One thing that should seem very plausible is that as n goes to infinity, the fraction of samples that come out as that event, compared to the number of samples you take, that's the sampling probability, which we know from the form of the sampling process is going to be the probability in the network.
Một điều nghe rất hợp lý là khi n tiến tới vô cùng, tỉ lệ các mẫu ra đúng sự kiện đó, so với số mẫu bạn lấy, đó là xác suất lấy mẫu, mà ta biết từ dạng của quá trình lấy mẫu sẽ bằng xác suất trong mạng.
What this means is this means the sampling procedure is called consistent. You may have noticed that in every unit, we use the word consistent. And it always means something different.
Điều này có nghĩa là thủ tục lấy mẫu được gọi là nhất quán. Có thể bạn đã để ý là ở mỗi phần, ta đều dùng từ nhất quán. Và lần nào nó cũng mang một nghĩa khác.
This is what consistency means here, OK? So we say a sampling procedure is consistent if the ratio of the samples in the limit goes towards the actual distribution that we're trying to sample from.
Đây là nghĩa của tính nhất quán ở đây, OK? Ta nói một thủ tục lấy mẫu là nhất quán nếu tỉ lệ các mẫu khi đi đến giới hạn tiến về phân phối thật mà ta đang cố lấy mẫu.
You might look at this and be like, well, how could it be inconsistent? Well, here's an inconsistent sampling procedure. What if I just went, and I picked each node 50:50 independently.
Bạn có thể nhìn vào và nghĩ, vậy làm sao nó có thể không nhất quán? Đây là một thủ tục lấy mẫu không nhất quán. Nếu tôi chọn từng nút theo tỉ lệ 50:50 một cách độc lập thì sao?
I would still get samples. They just wouldn't come out according to a distribution that had anything to do with the one I'm trying to model. All right. Let's do some prior sampling.
Tôi vẫn có các mẫu. Chỉ là chúng sẽ không ra theo một phân phối nào có liên quan đến phân phối mà tôi đang cố mô hình hóa. Được rồi. Ta làm thử prior sampling.
So here's this little network. We run that procedure where we visit each node and out pops sample 1, and then out pops sample 2, and sample 3, and sample 4, and sample 5.
Đây là mạng nhỏ này. Ta chạy thủ tục đó, duyệt từng nút và ra mẫu 1, rồi ra mẫu 2, mẫu 3, mẫu 4, và mẫu 5.
We've got five samples. Now, normally, we would have, maybe, millions of samples. We've got five. What can we do with these samples?
Chúng ta có năm mẫu. Bình thường thì ta sẽ có cả triệu mẫu. Ở đây chỉ có năm. Ta làm được gì với những mẫu này?
Well, with these samples, these samples represent a distribution. And we can do anything we would do with an actual distribution, we can do with these samples using counts instead of probabilities.
Những mẫu này biểu diễn một phân phối. Và bất cứ điều gì ta làm được với một phân phối thực sự, ta đều làm được với các mẫu này bằng cách dùng số đếm thay cho xác suất.
So let's say, I would like to know in this Bayes net — which remember, deep down this represents a joint distribution of our c, s, r, and w.
Giả sử tôi muốn biết, trong mạng Bayes này, mà hãy nhớ về bản chất nó biểu diễn một phân phối đồng thời của c, s, r và w.
And I could do things, like, I could compute in this network. I could compute the probability of w. How would I do that? Variable elimination.
Và tôi có thể tính một số thứ trong mạng này. Tôi có thể tính xác suất của w. Làm bằng cách nào? Khử biến.
So you say, I hate variable elimination. I haven't reviewed those lecture slides yet. I'm not going to do that. How else could I do it?
Nhưng bạn nói: tôi ghét khử biến. Tôi còn chưa xem lại slide bài đó. Tôi không làm đâu. Vậy còn cách nào khác?
Well, I could look in these samples. And I could say, well, in these samples, sometimes w comes out plus, and sometimes it comes out minus.
Ta có thể nhìn vào các mẫu này. Và nói rằng, trong các mẫu này, đôi khi w ra dương, đôi khi ra âm.
And in these samples, what's the probability of plus w? It's 4/5 or 80%.
Vậy trong các mẫu này, xác suất của +w là bao nhiêu? Là 4/5 hay 80%.
So I could write — in these samples, I could write the probability that plus w is 0.8. Great. Do you think that's actually the probability in the network?
Vậy tôi có thể viết, trong các mẫu này, xác suất của +w là 0,8. Tuyệt. Bạn nghĩ đó có thật là xác suất trong mạng không?
I mean, I have no idea, but probably not, right?
Tôi cũng không biết, nhưng có lẽ là không, đúng không?
This is just an empirical probability of this quantity of interest, not computed in the network, but computed over samples which were drawn consistently with the network.
Đây chỉ là xác suất thực nghiệm của đại lượng ta quan tâm, không tính trong mạng, mà tính trên các mẫu được lấy nhất quán với mạng.
So if instead of five samples, I had five billion, this 0.8 would be about right. As it is, hey, it's a number, OK?
Nếu thay vì năm mẫu, ta có năm tỉ mẫu, thì con số 0,8 này sẽ xấp xỉ đúng. Còn bây giờ thì, nó cũng là một con số, được chứ?
So we get counts, and we can normalize any events over those counts to get the probability of that event under our samples. This approach is the true distribution if we have more samples.
Vậy ta có các số đếm, và ta có thể chuẩn hóa bất kỳ sự kiện nào trên các số đếm đó để có xác suất của sự kiện đó trên tập mẫu của ta. Cách này tiến tới phân phối thực khi ta có nhiều mẫu hơn.
And we can estimate anything else that we like. So let's do some practice. Can we compute the conditional probability over the variable c, given that the grass is wet?
Và ta có thể ước lượng bất cứ thứ gì khác ta muốn. Ta luyện tập một chút. Ta có tính được xác suất có điều kiện của biến c, biết cỏ ướt không?
So how likely is it to be cloudy, given that the grass is wet? Let's do it.
Tức là khả năng trời nhiều mây là bao nhiêu, biết rằng cỏ ướt? Làm thôi.
All right. Well, when I look at these samples, I say, I care about the case where the grass is wet.
Được rồi. Khi nhìn vào các mẫu này, tôi quan tâm đến trường hợp cỏ ướt.
So this sample here, this sample doesn't do much for me because the grass is not wet there. So I look at the other four samples. And I say, how often is c true?
Mẫu này không giúp ích gì cho tôi vì ở đó cỏ không ướt. Nên tôi xét bốn mẫu còn lại. Và hỏi c đúng bao nhiêu lần?
Looks like three out of four. So there's my answer 3/4. Is it right? Probably not.
Có vẻ là ba trên bốn. Vậy đáp án của tôi là 3/4. Có đúng không? Có lẽ là không.
All right. Probability of cloudy, given rainy and wet grass. Man. OK, probability of cloudy, given rainy and wet grass.
Được rồi. Xác suất trời nhiều mây, biết trời mưa và cỏ ướt. Trời. Ok, xác suất trời nhiều mây, biết trời mưa và cỏ ướt.
All right. That one's not rainy and wet grass. That one's not rainy and wet grass. So of the rainy, wet grass samples, of which there are three, how often is it cloudy?
Được rồi. Mẫu đó không phải mưa và cỏ ướt. Mẫu đó cũng không phải mưa và cỏ ướt. Vậy trong các mẫu mưa và cỏ ướt, mà có ba mẫu, trời nhiều mây bao nhiêu lần?
All the time. In all of those samples, it was cloudy. Now, in this network, is the probability of cloudy, given plus r plus w, 1? Probably not.
Lần nào cũng vậy. Trong tất cả các mẫu đó, trời đều nhiều mây. Vậy trong mạng này, xác suất trời nhiều mây, biết +r +w, có bằng 1 không? Có lẽ là không.
But if I drew enough samples, this would start to approach the correct probability. Here's an interesting case. What's the probability of cloudy, given minus r and minus w?
Nhưng nếu tôi lấy đủ nhiều mẫu thì giá trị này sẽ tiến dần đến xác suất đúng. Đây là một trường hợp thú vị. Xác suất trời nhiều mây, biết -r và -w là bao nhiêu?
So I look through my samples. And I say, how many samples do I have for this condition minus r minus w? Uh-oh. I have no samples for that.
Tôi xem qua các mẫu. Và hỏi có bao nhiêu mẫu thỏa điều kiện -r -w này? Ôi. Tôi không có mẫu nào cả.
So I can't even answer this question yet. And this is a real problem because, in prior sampling, I just pull samples off according to the distribution. Sometimes they match my evidence.
Nên tôi còn chưa trả lời được câu hỏi này. Và đây là vấn đề thật sự vì trong prior sampling, tôi chỉ lấy mẫu ra theo phân phối. Đôi khi chúng khớp với bằng chứng của tôi.
Sometimes they don't.
Đôi khi thì không.
And if I have a question about some variable like c, conditioned on some rare evidence, I just got to keep pulling samples off the conveyor belt until I get some that match my evidence.
Và nếu tôi có câu hỏi về một biến như c, với điều kiện là một bằng chứng hiếm, thì tôi cứ phải lấy mẫu từ băng chuyền ra cho đến khi có mẫu khớp với bằng chứng.
I might never get any that match the evidence if it's rare enough. So that's a real problem with the sampling method, OK? But we can — it's fast.
Tôi có thể không bao giờ có mẫu nào khớp nếu bằng chứng đủ hiếm. Đó là vấn đề thật sự của phương pháp lấy mẫu, được chứ? Nhưng nó nhanh.
We can stop at any time. And, of course, the drawback is that it may be very inaccurate, OK? Any questions on prior sampling? Yep.
Ta có thể dừng bất cứ lúc nào. Và dĩ nhiên, nhược điểm là nó có thể rất thiếu chính xác, ok? Có câu hỏi nào về prior sampling không? Mời bạn.
STUDENT
So if we never get the evidence, what do we do?
Nếu ta không bao giờ có bằng chứng thì sao ạ?
PROFESSOR
What do you do if you never get the evidence? So in general, you want to set up your sampling procedures so that you're seeing the conditioning environment. You're seeing the evidence.
Bạn làm gì nếu không bao giờ có bằng chứng? Nhìn chung, bạn nên thiết lập quy trình lấy mẫu sao cho nó thấy được môi trường điều kiện. Tức là thấy được bằng chứng.
And if your evidence is very rare, prior sampling or, actually, in this case, rejection sampling — it's going to turn out as what we were doing there — is a very poor algorithm.
Và nếu bằng chứng rất hiếm, prior sampling, hay đúng hơn ở đây là rejection sampling, hóa ra đó là cái ta vừa làm, là một thuật toán rất tệ.
So you've got two choices. You can run for a long time, or you can have a better sampling algorithm.
Vậy bạn có hai lựa chọn. Chạy thật lâu, hoặc dùng thuật toán lấy mẫu tốt hơn.
I mean, you could make a decision about in your code, if there is ever a zero in the denominator, you have to do something reasonable.
Bạn cũng có thể quyết định trong code, nếu mẫu số bằng không thì phải xử lý hợp lý. Nhưng tóm lại, bất kỳ lựa chọn nào bạn đưa ra cũng chỉ là cách sửa ở mức kỹ thuật.
But the bottom line is any choice you make is going to be an engineering level fix. Mathematically, you just don't know very much, OK?
Về mặt toán học, bạn đơn giản là biết rất ít, được chứ? Về mặt toán học, bạn đơn giản là biết rất ít, được chứ?
So let's talk about rejection sampling. So the metaphor of prior sampling is events are coming off the conveyor belt distributed according to the joint probability that we have in our domain.
Bây giờ ta nói về rejection sampling. Phép ẩn dụ của prior sampling là các sự kiện lần lượt chạy ra từ băng chuyền, phân phối theo xác suất đồng thời của miền bài toán mà ta có.
And as they come off, we tally things up. In rejection sampling, we go into the sampling procedure with some condition that we care about, like, plus r, plus s, or something like that.
Và khi chúng chạy ra, ta ghi nhận đếm. Trong rejection sampling, ta bắt đầu quá trình lấy mẫu với một điều kiện mà ta quan tâm, chẳng hạn như plus r, plus s hay đại loại thế.
And so as the samples come off our conveyor belt, we take a look at them. And if they're samples we can use, meaning they match our evidence, we keep them.
Và khi các mẫu chạy ra khỏi băng chuyền, ta xem xét chúng. Nếu là mẫu dùng được, nghĩa là khớp với bằng chứng của ta, thì ta giữ lại.
And if they're samples, we can't use, we reject them.
Nếu là mẫu không dùng được, ta loại bỏ.
We actually sort of already did that when we computed some of those queries on the last slide, where we are crossing things out saying these samples don't represent my data condition.
Thực ra ta đã làm điều đó rồi khi tính một số truy vấn đó ở slide trước, khi ta gạch bỏ và nói các mẫu này không thỏa điều kiện dữ liệu của tôi.
So they don't actually — they're not relevant to this query. So in rejection sampling, samples come off, and you reject them if they don't match the evidence.
Nên chúng không liên quan đến truy vấn này. Vậy trong rejection sampling, các mẫu chạy ra, và ta loại chúng nếu không khớp với bằng chứng.
So let's look at the difference. If we'd like to know, say, in this network here, we'd like to know the marginal probability of c. In fact, it's sitting there in the network.
Ta hãy xem sự khác biệt. Giả sử trong mạng này, ta muốn biết xác suất biên của c. Thật ra nó nằm sẵn trong mạng.
So we wouldn't have to compute anything at all. But let's just say, we did it with sampling. OK, we could do prior sampling. We would get samples like this.
Nên ta chẳng cần tính gì cả. Nhưng cứ giả sử ta làm bằng lấy mẫu. Được, ta có thể dùng prior sampling. Ta sẽ có các mẫu như thế này.
We don't actually have to keep the samples around. We could tally for each sample as we draw it. We could be like, oh, you're a plus c sample.
Thực ra ta không cần giữ các mẫu lại. Ta có thể đếm ngay khi lấy từng mẫu. Kiểu như, à, bạn là một mẫu plus c.
You're another plus c sample. You're a minus c sample. You're a plus c sample. And we could keep tallies of the event we care about as the samples stream by.
Bạn là một mẫu plus c nữa. Bạn là mẫu minus c. Bạn là mẫu plus c. Và ta có thể giữ số đếm của sự kiện mà ta quan tâm khi các mẫu chạy qua.
In the end, we would normalize to get a probability. We could then discard the samples. They're gone. We don't need them anymore.
Cuối cùng, ta chuẩn hóa để ra xác suất. Rồi ta có thể bỏ các mẫu đi. Chúng biến mất. Ta không cần chúng nữa.
Whoops. If we want to know what's the probability of cloudy, given that there is a sprinkler out, you can do the same thing.
Rất tiếc. Nếu muốn biết xác suất trời nhiều mây, biết rằng có vòi phun nước, ta làm tương tự.
These samples come by, and you tally how many come up plus c versus minus c because that's your query variable of interest.
Các mẫu này chạy qua, và ta đếm bao nhiêu mẫu ra plus c so với minus c vì đó là biến truy vấn mà ta quan tâm.
The difference is everything that comes off the conveyor belt that doesn't match plus s, you just throw it in the bin. You don't tally anything because that's not relevant to your data condition.
Điểm khác là mọi thứ chạy ra từ băng chuyền mà không khớp plus s, ta cứ quăng vào thùng rác. Ta không đếm gì cả vì điều đó không liên quan đến điều kiện dữ liệu của ta.
This is called rejection sampling. And this is consistent for conditional probabilities. It's the exact same argument as why prior sampling is consistent with the entire distribution, OK?
Cái này gọi là rejection sampling. Và nó nhất quán đối với xác suất có điều kiện. Lập luận hoàn toàn giống như lý do prior sampling nhất quán với toàn bộ phân phối, được chứ?
So from, again, from these samples, we can answer any question. We could say, what's the probability of plus s, given plus c?
Vậy từ các mẫu này, ta có thể trả lời mọi câu hỏi. Ta có thể hỏi xác suất của plus s biết plus c là bao nhiêu?
And we'd be like, OK, that's this sample, this sample, and this sample are plus c. I would discard the rest as they pass.
Và ta sẽ thấy, được, mẫu này, mẫu này, và mẫu này là plus c. Tôi bỏ phần còn lại khi chúng chạy qua.
And as I go, I would say, OK, there's a vote for minus s, a vote for plus s, and a vote for minus s. And I would say, minus s, 2/3; plus s, 1/3.
Và khi đếm, tôi có một phiếu cho minus s, một phiếu cho plus s, và một phiếu cho minus s. Vậy minus s là 2/3; plus s là 1/3.
OK, that's rejection sampling, OK? Here's the algorithm, though we've now done it twice. Your input to this algorithm is the evidence that you have instantiated.
Đó là rejection sampling, được chứ? Đây là thuật toán, dù ta đã làm hai lần rồi. Đầu vào của thuật toán này là bằng chứng mà bạn đã gán giá trị.
So I know the values of this test and this test. Or this light in my car is blinking. So I know the evidence. Then I go through the network variable by variable.
Ví dụ tôi biết kết quả của xét nghiệm này và xét nghiệm kia. Hoặc đèn này trong xe tôi đang nhấp nháy. Vậy tôi biết bằng chứng. Rồi tôi đi qua mạng, từng biến một.
And I sample values for that variable. If they happen to come up in a way that matches my evidence, great, I return the sample. And if they don't, I just reject the sample.
Và lấy mẫu giá trị cho biến đó. Nếu kết quả tình cờ khớp với bằng chứng của tôi, tốt, tôi trả về mẫu đó. Nếu không, tôi loại mẫu đó.
And I start on a new sample. OK, so let's think about what that means. That means we're walking through the network. We get to the evidence variable.
Và bắt đầu một mẫu mới. Giờ ta hãy nghĩ xem điều đó có nghĩa gì. Nghĩa là ta đi qua mạng. Ta đến biến bằng chứng.
And there's this moment. There's this moment where I'm wondering, is it going to come up in a way that matches my evidence or not?
Và có một khoảnh khắc. Khoảnh khắc mà tôi tự hỏi, liệu nó có ra giá trị khớp với bằng chứng của tôi hay không?
And that moment determines whether or not we throw out the sample or keep it, OK? Remember, the problem is we might end up throwing out a lot of evidence.
Và khoảnh khắc đó quyết định việc ta vứt mẫu đi hay giữ lại. Hãy nhớ, vấn đề là ta có thể phải vứt đi rất nhiều mẫu.
So we're going to go back to that moment when we weren't sure whether or not the random variable that matches the evidence would come up in a way that matched the evidence.
Vì vậy ta sẽ quay lại khoảnh khắc đó, khi ta không chắc biến ngẫu nhiên khớp với bằng chứng có ra giá trị khớp với bằng chứng hay không.
We're going to fix that. We're going to fix that by doing something called likelihood weighting.
Ta sẽ sửa điều đó. Ta sẽ sửa bằng cách làm một thứ gọi là likelihood weighting.
So if we look at the caricature here, if you imagine that your evidence is — you know that the shape coming off the conveyor belt is blue.
Nhìn vào hình minh họa này, hãy tưởng tượng bằng chứng của bạn là hình chạy ra từ băng chuyền có màu xanh.
And you want to know what's the distribution over shape, given color blue. We're, basically — we're going to take every blue thing that comes off and throw it into one of the shape bins.
Và bạn muốn biết phân phối của hình dạng biết màu xanh. Về cơ bản, ta sẽ lấy mọi vật màu xanh chạy ra và ném vào một trong các thùng hình dạng.
And that's going to be our distribution. So let me just write that down. Whoops. Let me just write that down.
Và đó sẽ là phân phối của ta. Để tôi viết ra. Rất tiếc. Để tôi viết ra.
So we're trying to compute probability, the probability distribution of our shape. OK, I just changed models here. We're not in the sprinkler anymore. Probability distribution over shape, given that c equals blue.
Ta đang cố tính xác suất, phân phối xác suất của hình dạng. Tôi vừa đổi mô hình ở đây. Ta không còn ở bài vòi phun nước nữa. Phân phối xác suất của hình dạng, biết c bằng xanh.
So what do we do? Colored shapes come off the conveyor belt, and if it's blue we throw it into one of the shape bins. This one's going in this bin.
Vậy ta làm gì? Các hình màu chạy ra từ băng chuyền, và nếu nó màu xanh ta ném vào một trong các thùng hình dạng. Cái này vào thùng này.
They go into the bins. In the end, I'm going to count up how many things fell into each bin.
Chúng rơi vào các thùng. Cuối cùng, tôi sẽ đếm xem có bao nhiêu thứ rơi vào mỗi thùng.
When I get something that's red, it doesn't match my evidence of blueness, so I throw it out.
Khi tôi gặp một thứ màu đỏ, nó không khớp với bằng chứng là màu xanh, nên tôi loại bỏ nó.
In likelihood weighting, we don't have the problem of throwing out samples because we make them all blue.
Với likelihood weighting, ta không gặp vấn đề phải vứt bỏ các mẫu vì ta làm cho tất cả đều màu xanh.
That is, when we're drawing samples from the network, we don't risk the sample not matching the evidence at the evidence nodes. We fix it to equal the evidence at the evidence nodes.
Tức là, khi lấy mẫu từ mạng, ta không có nguy cơ mẫu không khớp với bằng chứng tại các nút bằng chứng. Ta cố định giá trị bằng đúng bằng chứng tại các nút bằng chứng.
So there's a big plus. We don't have to throw out any samples. Every shape comes out blue. But there's a problem.
Vậy là có một ưu điểm lớn. Ta không phải vứt bỏ mẫu nào cả. Hình nào ra cũng màu xanh. Nhưng có một vấn đề.
What's the problem? Let's go see if we can see the problem. OK, so the problem with rejection sampling, if your evidence is unlikely, you reject lots of samples.
Vấn đề là gì? Hãy xem ta có thấy được vấn đề không. Được rồi, vấn đề của rejection sampling là nếu bằng chứng ít xảy ra, bạn sẽ loại bỏ rất nhiều mẫu.
Actually, how many do you reject? So let's say, we're trying to compute some query, P of Q, given some evidence, variables e. So you have a bunch of evidence, variables e.
Thực ra là loại bỏ bao nhiêu? Giả sử ta đang tính một truy vấn P của Q, cho trước một số bằng chứng, các biến e. Vậy bạn có một loạt biến bằng chứng e.
So I'm getting samples out of my Bayes net using prior sampling, rejection sampling. Each sample pops off, and I look at it, and I say, do you match my evidence e?
Tôi lấy mẫu từ mạng Bayes bằng prior sampling, tức rejection sampling. Mỗi mẫu bật ra, tôi xem xét nó và hỏi: bạn có khớp với bằng chứng e của tôi không?
No, I throw it out. Do you match my evidence e? Nope, I throw it out. Do you match?
Không, tôi loại bỏ. Bạn có khớp với bằng chứng e không? Không, tôi loại bỏ. Bạn có khớp không?
Yes, I'll keep this sample. What if your evidence is, like, this test result, and this test result, and this test result, and this test result? How many samples am I going to keep?
Có, tôi sẽ giữ mẫu này. Nếu bằng chứng của bạn là kết quả xét nghiệm này, và kết quả này, và kết quả này, và kết quả này thì sao? Tôi sẽ giữ lại bao nhiêu mẫu?
I'm only going to keep the ones that pop off the conveyor belt miraculously matching all my evidence variables. What fraction of samples from the full distribution match my evidence?
Tôi chỉ giữ những mẫu mà từ băng chuyền bật ra khớp một cách kỳ diệu với tất cả các biến bằng chứng. Tỉ lệ mẫu từ phân phối đầy đủ khớp với bằng chứng là bao nhiêu?
Well, P of e, right? That evidence has some probability. And I'm drawing things from the network according to the distribution of the full joint.
Là P của e, đúng không? Bằng chứng đó có một xác suất nào đó. Và tôi lấy mẫu từ mạng theo phân phối đồng thời đầy đủ.
And so things come out matching my evidence with P of e. Well, if my evidence probability is 0.3, that means I keep 30% of my samples.
Nên các mẫu khớp với bằng chứng của tôi với xác suất P của e. Nếu xác suất bằng chứng là 0,3, nghĩa là tôi giữ 30% số mẫu.
If my evidence probability is one in a billion, it means I only keep one in a billion of the samples. And that's super inefficient because I spend all my time rejecting everything.
Nếu xác suất bằng chứng là một phần tỉ, nghĩa là tôi chỉ giữ một trên một tỉ mẫu. Và như vậy cực kỳ kém hiệu quả vì tôi mất toàn bộ thời gian để loại bỏ mọi thứ.
And that's what's going to happen because your evidence is, like, some weird things you've observed. Next time you do it, you're going to observe some other weird things.
Và điều đó sẽ xảy ra vì bằng chứng của bạn là những điều kỳ lạ nào đó mà bạn đã quan sát được. Lần sau bạn làm lại, bạn sẽ quan sát những điều kỳ lạ khác.
So the marginal probability of your evidence is almost always pretty small. And that means with rejection sampling, you're almost always rejecting almost everything, so that's not great.
Vì vậy xác suất biên của bằng chứng hầu như luôn khá nhỏ. Và điều đó có nghĩa là với rejection sampling, bạn hầu như luôn loại bỏ gần hết mọi thứ, nên không hay lắm.
And in particular, as you sample, you're not exploiting the fact that you know the evidence. You draw your sample, and then you're like, oh, man, it didn't come up like the evidence.
Đặc biệt, khi lấy mẫu, bạn không tận dụng việc mình đã biết bằng chứng. Bạn lấy mẫu, rồi bạn nghĩ: trời ơi, nó không ra giống bằng chứng.
Oh, it didn't come up like the evidence again. It's like, well, you actually know the evidence. Maybe we should work this into the process. OK, so we do.
Lại không ra giống bằng chứng nữa. Thì bạn thực ra biết bằng chứng mà. Có lẽ ta nên đưa nó vào quy trình. Được, vậy ta làm thế.
We already did this, but here's an illustration.
Ta đã làm rồi, nhưng đây là một minh họa.
If I want to know the probability of a shape, given blue, and I draw all of these samples off the conveyor belt, I throw out everything except that one blue sphere.
Nếu tôi muốn biết xác suất của một hình, cho trước màu xanh, và tôi lấy hết các mẫu này từ băng chuyền, tôi vứt hết, trừ quả cầu xanh đó.
Because it didn't happen to come across blue. So here's the idea. We're going to rig the system. We're going to fix all the evidence variables as we walk through the network.
Vì chúng tình cờ không ra màu xanh. Vậy đây là ý tưởng. Ta sẽ "gian lận" hệ thống. Ta sẽ cố định tất cả các biến bằng chứng khi đi qua mạng.
And we're not going to sample their values. We're just going to fix them to the evidence. And that means that the sample distribution can't be consistent anymore because suddenly everything is coming off blue.
Và ta sẽ không lấy mẫu giá trị của chúng. Ta chỉ cố định chúng bằng bằng chứng. Và điều đó có nghĩa là phân phối mẫu không còn nhất quán nữa vì đột nhiên mọi thứ đều ra màu xanh.
And if everything comes off the conveyor belt matching our evidence, it's not the same distribution. I mean, if nothing else, the probability evidence used to be P of e, and now, it's what?
Và nếu mọi thứ ra khỏi băng chuyền đều khớp với bằng chứng, thì đó không còn là cùng phân phối. Ít nhất là xác suất của bằng chứng trước đây là P của e, còn bây giờ thì là bao nhiêu?
Now, it's 1. Everything matches the evidence, so we've broken something. Let's go dig into the algorithm, and see where we can fix what were broken.
Bây giờ là 1. Mọi thứ đều khớp bằng chứng, nên ta đã làm hỏng một điều gì đó. Hãy đi sâu vào thuật toán, xem ta có thể sửa chỗ hỏng ở đâu.
But it does give me a solution, which is to say that each of these samples that comes off is going to have a weight. And we'll figure out what that weight is.
Nhưng nó cho tôi một giải pháp, đó là mỗi mẫu ra khỏi băng chuyền sẽ có một trọng số. Và ta sẽ tìm xem trọng số đó là gì.
It's going to correspond to the probability of the evidence. And what that means is we're now going to go through, and we're going to pull things off the conveyor belt.
Nó sẽ tương ứng với xác suất của bằng chứng. Và điều đó có nghĩa là bây giờ ta sẽ đi qua, và lấy từng thứ ra khỏi băng chuyền.
And they're all going to be blue. And so everything comes off blue. But they're not all going to come off with the same weight.
Và tất cả đều màu xanh. Vậy mọi thứ đều ra màu xanh. Nhưng không phải tất cả đều có cùng trọng số.
And in particular, samples where it probably wouldn't have matched the evidence are going to come off with a very small weight.
Cụ thể, những mẫu mà nhiều khả năng đã không khớp với bằng chứng sẽ có trọng số rất nhỏ.
And samples where, actually, plausibly, it could have matched the evidence, they're going to come off with a little larger weight. OK, so let's do an instance of likelihood weighting, OK?
Còn những mẫu mà thực tế có khả năng khớp với bằng chứng sẽ có trọng số lớn hơn một chút. Được rồi, hãy làm một ví dụ về likelihood weighting.
So here's my network. What I did before is I started at the top, and I sampled each node. And sometimes things came off as plus sprinkler, plus wet grass, and sometimes they didn't.
Đây là mạng của tôi. Trước đây tôi bắt đầu từ trên cùng, và lấy mẫu từng nút. Và đôi khi ra plus sprinkler, plus wet grass, và đôi khi không.
But now, everyday is a sprinkler wet grass day. So let's draw a sample. I go to node c and with probability of 0.5, I'm going to get plus cloudy.
Nhưng bây giờ, ngày nào cũng là ngày có sprinkler và cỏ ướt. Hãy lấy một mẫu. Tôi đến nút c và với xác suất 0,5, tôi sẽ được plus cloudy.
I get plus cloudy. OK, now, I go to r. And with probability, let's see, it's plus cloudy.
Tôi được plus cloudy. Được rồi, giờ tôi đến r. Và với xác suất, để xem nào, nó là plus cloudy.
So with probability of 0.8, I'm going to get plus r here, and with the probability of 0.2, I'm going to get minus r. Nope, we're not doing that one yet.
Với xác suất 0.8, ta sẽ được plus r ở đây, và với xác suất 0.2, ta sẽ được minus r. Không, ta chưa làm cái đó vội.
OK, so we have plus c. We're going to go to the sprinkler.
Được rồi, ta có plus c. Giờ ta đi tới sprinkler.
Now, given that this sample has cloudy, what I would normally do is flip a coin at sprinkler, and it would come up as plus s 10% of the time.
Với mẫu này đã có cloudy, bình thường ta sẽ tung đồng xu tại sprinkler, và nó sẽ ra plus s trong 10% số lần.
And it would come out red, minus s, 90% of the time. So right here, imagine I haven't actually flip the coin yet. Chances are, I'm going to get minus s.
Còn 90% số lần sẽ ra minus s. Ngay tại đây, hãy tưởng tượng ta chưa tung đồng xu. Nhiều khả năng ta sẽ được minus s.
I'm going to get a red node here. But my evidence says, green. OK, so what happens? I'm going to stop.
Ta sẽ có một nút màu đỏ ở đây. Nhưng bằng chứng của ta lại là màu xanh. Vậy chuyện gì xảy ra? Ta sẽ dừng lại.
There's this moment where I don't know what's going to happen in prior sampling or rejection sampling. And I don't know what's going to happen.
Có một khoảnh khắc ta không biết điều gì sẽ xảy ra trong lấy mẫu tiên nghiệm hay lấy mẫu loại bỏ . Ta không biết điều gì sẽ xảy ra.
But I know that if I got to this point again, and again, and again, how likely would I be to get the evidence of plus s?
Nhưng ta biết rằng nếu đến điểm này hết lần này đến lần khác, khả năng ta được bằng chứng plus s là bao nhiêu?
Well, basically 10% of the time that I get to this point, the next node that I sample, when I sample sprinkler, it will come out matching the evidence.
Về cơ bản, cứ 10% số lần ta đến điểm này, nút tiếp theo ta lấy mẫu, khi lấy mẫu sprinkler, sẽ khớp với bằng chứng.
So for every 10 samples they get here, 9 of them are going to get rejected, but 1 will survive.
Nên cứ 10 mẫu đến đây thì 9 mẫu bị loại, nhưng 1 mẫu sống sót.
And that means, if you imagine we split into some multiverse of parallel execution here, instead of flipping the coin, and risking a 90% chance of getting minus sprinkler, I'm going to take the universes where I actually get plus s.
Nghĩa là, hãy tưởng tượng ta tách ra thành nhiều vũ trụ song song thay vì tung đồng xu và chịu 90% rủi ro ra minus sprinkler, ta chọn những vũ trụ mà ta thật sự được plus s.
And I'm going to pretend I'm going into those universes, which means this sample only really represents 10% of the samples that make it to this point.
Và ta giả vờ rằng ta đi vào những vũ trụ đó, nghĩa là mẫu này chỉ thực sự đại diện cho 10% số mẫu đi tới điểm này.
So when I go through, I'm going to multiply in — I'm going to rig this node.
Nên khi đi qua, ta sẽ nhân vào... Ta sẽ làm gian nút này.
And every time I rig a node, I'm going to multiply the weight of a sample that begins at 1 by the probability that the thing that I rigged would have actually happened.
Và mỗi lần làm gian một nút, ta sẽ nhân trọng số của mẫu, bắt đầu từ 1, với xác suất để điều ta làm gian thực sự xảy ra.
All right. So now, I go over to rain, and I say, well, this isn't evidence. So I'm just going to flip a coin and see where it falls.
Được rồi. Giờ sang rain, và đây không phải bằng chứng. Nên ta cứ tung đồng xu xem nó ra gì.
Maybe it will be plus r. Maybe it will be minus r. It's plus r, OK? Now, I get to wet grass again.
Có thể là plus r. Có thể là minus r. Là plus r, OK? Giờ ta tới wet grass.
And when I get to wet grass, I look here, and I say, I could flip a coin and see whether I get plus or minus w.
Khi tới wet grass, ta nhìn đây và nói, ta có thể tung đồng xu xem được plus hay minus w.
But instead, I'm just going to fix it to plus w because I'm imagining that's my evidence. But not every single time I get to this point, would it come up my way.
Nhưng thay vào đó, ta cố định nó là plus w vì ta coi đó là bằng chứng của mình. Nhưng không phải lần nào đến điểm này nó cũng ra theo ý ta.
But it would 99% of the time. And so this sample is going to get another weight of 0.99.
Mà chỉ 99% số lần. Nên mẫu này được thêm trọng số 0.99.
And so what's going to pop off here is that you'll get samples, and they'll have weights on them.
Và kết quả là ta sẽ có các mẫu kèm theo trọng số.
Now, why do these samples have weights?
Vậy tại sao các mẫu này có trọng số?
These samples have weights because — these samples have weights because the nodes that I rigged only had a small probability of actually having the chips fall the way I needed them to.
Các mẫu này có trọng số vì... các mẫu này có trọng số vì những nút ta làm gian chỉ có xác suất nhỏ để mọi thứ thật sự rơi đúng như ta cần.
And that probability needs to be captured somewhere. And that's captured in the weight of the sample. So here's the algorithm for likelihood weighting. And then we'll look at its properties.
Và xác suất đó cần được ghi lại ở đâu đó. Nó được ghi lại trong trọng số của mẫu. Đây là thuật toán likelihood weighting. Rồi ta sẽ xem các tính chất của nó.
The input again, just like rejection sampling, is the instantiation of your evidence.
Đầu vào, giống lấy mẫu loại bỏ, là phép gán bằng chứng của bạn.
But now, instead of rejecting samples that don't match the evidence, instead, what I'm going to do now is I'm going to rig every sample to match my evidence.
Nhưng giờ, thay vì loại bỏ các mẫu không khớp bằng chứng, ta sẽ làm gian mọi mẫu để khớp với bằng chứng.
So I'm going to go along node to node, and if it's not an evidence node, I'm going to flip a coin according to the probabilities based on the parents.
Ta đi từ nút này sang nút khác, nếu không phải nút bằng chứng, ta tung đồng xu theo xác suất dựa trên các nút cha.
And I'm going to take whatever comes out. But when I get to an evidence variable — so that's the normal thing.
Và lấy bất kỳ kết quả nào ra. Nhưng khi tới một biến bằng chứng... đó là trường hợp thông thường.
When I get to an evidence variable, I am going to assign the value in my evidence to that node.
Khi tới một biến bằng chứng, ta gán giá trị trong bằng chứng cho nút đó.
And I'm going to multiply the probability of that actually having happened in an organic way into the weight of the sample, OK?
Và ta nhân xác suất để điều đó thực sự xảy ra một cách tự nhiên vào trọng số của mẫu, OK?
What comes off now is a sample that has a weight attached to it.
Thứ ra khỏi quy trình giờ là một mẫu có gắn kèm một trọng số.
And so you can imagine, I pull this red ball, or sorry, I pull a blue pyramid off of the conveyor belt, except it's now got the number of 0.7 attached to it.
Bạn có thể hình dung, tôi lấy quả bóng đỏ này, à nhầm, một hình chóp xanh từ băng chuyền, nhưng giờ nó có gắn con số 0.7.
And not every sample is going to have the same weight.
Và không phải mẫu nào cũng có cùng trọng số.
Indeed, samples often have very, very low weight because you forced a lot of evidence nodes to be something that they probably wouldn't have been.
Thực tế, các mẫu thường có trọng số rất rất thấp vì bạn ép nhiều nút bằng chứng thành giá trị mà lẽ ra chúng khó có được.
And the weights on the evidence are, in general, very small. OK, so that's likelihood weighting. Likelihood weighting, we take our network. We start at the top.
Và trọng số của bằng chứng nhìn chung rất nhỏ. Đó là likelihood weighting. Với likelihood weighting, ta lấy mạng của mình. Bắt đầu từ trên cùng.
We flip a coin for non-evidence variables. And we see, it lands however it is.
Tung đồng xu cho các biến không phải bằng chứng. Và xem nó rơi ra sao.
As a result, if I draw a sample from a Bayes net in which some nodes were actually sampled, and they took on whatever value the random number came up, and other nodes are rigged, what's the probability that I'm going to get, whatever, plus c, plus s, plus r, plus w?
Do đó, nếu tôi lấy một mẫu từ mạng Bayes trong đó một số nút được lấy mẫu thật, và nhận giá trị mà số ngẫu nhiên cho ra, còn các nút khác bị làm gian, xác suất để tôi được, chẳng hạn, plus c, plus s, plus r, plus w là bao nhiêu?
What's the probability that's going to happen? Well, the probability that I'm going to get plus c is P of plus c. The probability that I'm going to get, whatever, r is r, given c.
Xác suất điều đó xảy ra là bao nhiêu? Xác suất tôi được plus c là P của plus c. Xác suất tôi được, chẳng hạn, r bằng r, cho trước c.
And so the sampling probability — the probability that we're going to get the sample which includes my evidence every time — is going to be a product of the probability of the nodes that I actually did sample.
Và xác suất lấy mẫu, tức xác suất ta được mẫu chứa bằng chứng của mình mỗi lần, là tích xác suất của các nút mà ta thực sự đã lấy mẫu.
But unlike before, there are not terms in this product for the nodes that I didn't sample.
Nhưng khác với trước, trong tích này không có các số hạng cho những nút ta không lấy mẫu.
The nodes that I just rigged values to match the evidence — those conditional probabilities are not part of this product.
Những nút ta chỉ gán giá trị cho khớp với bằng chứng, các xác suất có điều kiện đó không nằm trong tích này.
And if I want probabilities to match my joint distribution, I have to have every single term, one for each variable. However, samples have weights.
Và nếu muốn xác suất khớp với phân phối đồng thời, thì phải có đủ từng số hạng, mỗi biến một số hạng. Tuy nhiên, các mẫu có trọng số.
And the weight on a sample for z, sampled variables, and e, fixed evidence variables — the weight on a sample is all the other terms of the joint probability.
Và trọng số của một mẫu với z là các biến được lấy mẫu, và e là các biến bằng chứng cố định — trọng số của mẫu là tất cả các số hạng còn lại của xác suất đồng thời.
It's the probability of each evidence value that I fixed, given its parents. And so either in the sampling distribution or in the weights, every term appears exactly once.
Đó là xác suất của từng giá trị bằng chứng mà tôi đã cố định, cho trước các nút cha của nó. Vậy nên hoặc trong phân phối lấy mẫu hoặc trong các trọng số, mỗi số hạng xuất hiện đúng một lần.
And that means that if I take a weighted sampling distribution here, I get all of those terms in the Bayes net appearing on one side or the other.
Điều đó có nghĩa là nếu lấy phân phối lấy mẫu có trọng số ở đây, ta có mọi số hạng của mạng Bayes xuất hiện ở bên này hoặc bên kia.
So what does that mean? It means we have a bunch of samples with weights. And when I tally things up, each sample counts in proportion to it's weight, OK?
Vậy điều đó nghĩa là gì? Nghĩa là ta có một loạt mẫu kèm trọng số. Và khi tổng hợp lại, mỗi mẫu được tính tỉ lệ với trọng số của nó, được chứ?
All right. Any questions about that? We'll do an overview. And then we'll look at something a little bit different.
Được rồi. Có câu hỏi nào về phần này không? Ta sẽ điểm lại tổng quan. Rồi sau đó xem một thứ hơi khác một chút.
OK, so let's think about likelihood weighting. What was the idea in likelihood weighting?
Nào, hãy nghĩ về likelihood weighting. Ý tưởng của likelihood weighting là gì?
The idea in likelihood weighting is if I have certain evidence values, I have certain variables whose value I know for my query. Like, I know this test came out negative, or something like that.
Ý tưởng là nếu tôi có một số giá trị bằng chứng, có một số biến mà tôi đã biết giá trị cho truy vấn của mình. Ví dụ, tôi biết xét nghiệm này ra âm tính, hay đại loại như thế.
Or I know this light is on in the car. It seems silly to generate samples that don't match my evidence because you're just going to reject them.
Hoặc tôi biết đèn này trong xe đang sáng. Thật ngớ ngẩn khi tạo ra những mẫu không khớp với bằng chứng, vì rồi bạn cũng sẽ loại chúng đi.
So think about a big network which has a bunch of variables. And let's say, the one you know — and there's a bunch of connections between these variables in this network, OK?
Hãy nghĩ về một mạng lớn có nhiều biến. Và giả sử, cái bạn biết — và có nhiều kết nối giữa các biến trong mạng này, được chứ?
And let's say, we've got some evidence. We'll make it blue. Let's say, this node and this node, we happen to know their values.
Và giả sử ta có một ít bằng chứng. Ta tô màu xanh. Giả sử nút này và nút này, ta tình cờ biết giá trị của chúng.
It seems a little crazy — if we know that, say, this one takes on value plus and this one takes on value minus.
Sẽ hơi điên rồ — nếu ta biết, chẳng hạn, nút này nhận giá trị cộng và nút này nhận giá trị trừ.
It seems a little crazy to generate samples that don't match that evidence. Why would we do that? We're just going to throw them out? So in likelihood weighting, we would fix these values.
Sẽ hơi điên rồ khi tạo ra những mẫu không khớp với bằng chứng đó. Sao lại làm thế? Rồi lại vứt chúng đi? Nên trong likelihood weighting, ta cố định các giá trị này.
And then as we go down the network, the whole rest of the sample would play out in a way that's consistent with the evidence. This is sort of like hypothetical simulation.
Rồi khi đi xuống phía dưới mạng, phần còn lại của mẫu sẽ diễn ra theo cách nhất quán với bằng chứng. Giống như một dạng mô phỏng giả định.
Hey, imagine — what network? Imagine there was a burglary, but not an earthquake. What would happen? Let's simulate.
Này, hãy tưởng tượng — mạng nào nhỉ? Tưởng tượng có trộm nhưng không có động đất. Điều gì sẽ xảy ra? Hãy mô phỏng.
So I fix burglary. I fix earthquake because why not? We only care about those samples. And then I let the network play out according to its probabilities.
Vậy tôi cố định biến trộm. Tôi cố định biến động đất vì sao lại không? Ta chỉ quan tâm đến những mẫu đó. Rồi tôi để mạng tự chạy tiếp theo các xác suất của nó.
That's just simulation. And likelihood works really well when your evidence is at the top because then everything else that falls out of the network after that, conditions on that evidence naturally.
Đó chỉ là mô phỏng. Và likelihood weighting hoạt động rất tốt khi bằng chứng nằm ở trên cùng, vì khi đó mọi thứ còn lại rơi ra từ mạng phía sau đều có điều kiện theo bằng chứng đó một cách tự nhiên.
However, let's say, we have a similar network. And we had a bunch of variables. And there's errors between them. So imagine that's the same network.
Tuy nhiên, giả sử ta có một mạng tương tự. Và ta có một loạt biến. Và có các cung nối giữa chúng. Hãy tưởng tượng đó là cùng một mạng.
And now, let's say, all our evidence is at the bottom. So we know John called and Mary called. And I'd like to know what's the probability of an earthquake.
Và giờ giả sử toàn bộ bằng chứng nằm ở dưới cùng. Tức ta biết John gọi và Mary gọi. Và tôi muốn biết xác suất có động đất là bao nhiêu.
Well, now, this isn't quite so good because we start simulating, and we're like, hmm, no burglary and no earthquake, no alarm. Oh, John called. Mary called.
Giờ thì không còn tốt lắm, vì ta bắt đầu mô phỏng và thấy: không trộm và không động đất, không báo động. Ồ, John gọi. Mary gọi.
That sample, is that going to have high weight or low weight? Right, it's pretty typical up top because there's usually not a burglary. There's usually not an earthquake.
Mẫu đó sẽ có trọng số cao hay thấp? Đúng, phần trên rất điển hình vì thường là không có trộm. Thường là không có động đất.
The alarm usually doesn't go off. But then, instead of nobody calling me, which would be the typical way that simulation would unfold. I'm like, no, pretend they called.
Chuông báo động thường không kêu. Nhưng rồi, thay vì không ai gọi cho tôi, vốn là diễn biến điển hình của mô phỏng. Tôi lại bảo: không, cứ giả sử họ đã gọi.
The sample will come off as negative, negative, negative, but they both called.
Mẫu sẽ ra là âm, âm, âm, nhưng cả hai đều gọi.
It will come off with a very small weight because that's probably not what would have happened if there had been no alarm.
Nó sẽ có trọng số rất nhỏ vì đó có lẽ không phải điều sẽ xảy ra nếu không có báo động.
And then you're going to have lots of samples rolling off the conveyor belt that represent no burglary, no earthquake, no burglary, no earthquake, no burglary, no earthquake.
Và bạn sẽ có rất nhiều mẫu lăn ra khỏi băng chuyền đại diện cho không trộm, không động đất, không trộm, không động đất, không trộm, không động đất.
They're all John and Mary calling because that's how the procedure works. But they all have a very small weight because that's probably not what would have happened.
Tất cả đều có John và Mary gọi vì đó là cách thủ tục này hoạt động. Nhưng tất cả đều có trọng số rất nhỏ vì đó có lẽ không phải điều sẽ xảy ra.
And so as a result, everything upstream of your evidence doesn't take on values which are typical of scenarios where that evidence has that value.
Kết quả là mọi thứ ở phía trên bằng chứng không nhận các giá trị điển hình của những kịch bản mà bằng chứng đó có giá trị như vậy.
So in likelihood weighting everything's sort of downstream. You simulate the consequences of the evidence. But likelihood weighting doesn't do a very good job of simulating the causes of the evidence.
Vậy trong likelihood weighting mọi thứ đều thuộc về phía hạ nguồn. Bạn mô phỏng hệ quả của bằng chứng. Nhưng likelihood weighting không làm tốt việc mô phỏng nguyên nhân của bằng chứng.
You're just sort of going along simulating a normal day, and then, boom, there's your evidence. It's probably pretty inconsistent with what actually has been sampled.
Bạn cứ đi tiếp mô phỏng một ngày bình thường, rồi bùm, bằng chứng xuất hiện. Nó có lẽ khá mâu thuẫn với những gì thực sự đã được lấy mẫu.
And so your samples roll off with a very small weight. So likelihood weighting is good. We take the evidence into account, at least to a certain degree.
Và vì vậy các mẫu của bạn ra với trọng số rất nhỏ. Vậy likelihood weighting là tốt. Ta có tính đến bằng chứng, ít nhất ở một mức độ nào đó.
If nothing else, all the samples do match the evidence, so we don't completely reject anything. And that means more of the samples will reflect the state of the world.
Ít nhất thì mọi mẫu đều khớp với bằng chứng, nên ta không loại bỏ hoàn toàn mẫu nào. Và điều đó nghĩa là nhiều mẫu hơn sẽ phản ánh trạng thái của thế giới.
But as we just talked about, likelihood weighting doesn't solve all our problems because the evidence influences the choice of things that are downstream, but not upstream.
Nhưng như ta vừa nói, likelihood weighting không giải quyết được mọi vấn đề, vì bằng chứng chỉ ảnh hưởng đến việc chọn các biến ở phía dưới, chứ không ảnh hưởng đến các biến ở phía trên.
What we'd really like to do is we'd like to be able to say, I know this variable, and I know this variable.
Điều ta thực sự muốn là có thể nói: tôi biết biến này, và tôi biết biến này.
So somehow fill out the rest of the network for me in a way that kind of takes that into account.
Vậy hãy điền phần còn lại của mạng sao cho có tính đến điều đó.
Like, John and Mary are calling, so set that earthquake in a way that is typical, given that evidence. How do we do that? We don't have a method for that right now.
Ví dụ, John và Mary đang gọi, vậy hãy đặt biến động đất theo cách điển hình, với bằng chứng đó. Làm thế nào để làm được điều đó? Hiện giờ ta chưa có phương pháp nào cho việc này.
We only know how to sample downward, and usually there won't be an earthquake or a burglary if we do that. So we're going to take a couple minute break.
Ta chỉ biết lấy mẫu theo chiều đi xuống, và thường sẽ không có động đất hay trộm nếu làm như vậy. Giờ ta nghỉ giải lao vài phút.
And then we're going to talk about another technique called Gibbs sampling, which has its own issues, which we'll get into, but fixes this problem of wanting your samples to take into account the evidence, regardless of where the evidence is placed in the network, OK?
Sau đó ta sẽ nói về một kỹ thuật khác gọi là lấy mẫu Gibbs, kỹ thuật này cũng có vấn đề riêng, sẽ nói sau, nhưng nó khắc phục được việc ta muốn các mẫu có tính đến bằng chứng, bất kể bằng chứng nằm ở đâu trong mạng, được chứ?
So a couple minute break, and then we'll take over with Gibbs sampling.
Nghỉ vài phút, rồi ta sẽ tiếp tục với lấy mẫu Gibbs.
[SIDE CONVERSATION] That's weird.
[TRÒ CHUYỆN RIÊNG] Lạ thật.
[WHISPERING] OK, I changed my mind.
[THÌ THẦM] Được rồi, tôi đổi ý.
We're not going to Gibbs sampling yet. We're going to do some examples. All right.
Ta chưa học lấy mẫu Gibbs vội. Ta sẽ làm vài ví dụ. Được rồi.
OK, so first example, we're going to bring back the rain and traffic network. So rain, traffic, we need some probabilities.
Ví dụ đầu tiên, ta quay lại mạng mưa và kẹt xe. Mưa, kẹt xe, ta cần các xác suất.
Something has to live under rain, so we'll say, P of R. Oh, let's say, P of R, OK.
Dưới nút mưa phải có một bảng, nên ta viết P của R. À, P của R, được rồi.
So let's say, plus R, minus R. What's the probability of rain going to be? Well, let's make probability of rain 0.3, probability of no rain 0.7.
Vậy là +r, -r. Xác suất mưa là bao nhiêu? Cho xác suất mưa là 0,3, xác suất không mưa là 0,7.
We'll pretend we're not in our perpetual drought, OK? Let's make the conditional probability, what lives under T?
Ta giả vờ là không phải đang hạn hán triền miên nhé. Bây giờ là xác suất có điều kiện, dưới T có gì?
T is dreaming about the conditional probability of traffic, given rain. And so that is — well, there's two probabilities.
T đang mơ về xác suất có điều kiện của kẹt xe, biết mưa. Và nó là... có hai xác suất.
There's plus traffic, minus traffic, when there is rain. And then also, when there is not rain, there is plus traffic, minus traffic.
Có kẹt xe, không kẹt xe, khi có mưa. Và cả khi không có mưa cũng có kẹt xe, không kẹt xe.
So let's think of some numbers. When it's raining, let's say, there is 90% traffic, 10% no traffic. And then when there's no rain, let's say, it's reversed. Well, let's say it's 50:50.
Ta nghĩ vài con số. Khi trời mưa, giả sử 90% kẹt xe, 10% không kẹt xe. Còn khi không mưa, giả sử ngược lại. À, giả sử là 50:50.
All right, so we have a Bayes net. What can I do in this Bayes net? I can compute elements of the joint distribution. So probability of rain and traffic 0.3.
Vậy ta có một mạng Bayes. Tôi làm được gì với mạng này? Tôi tính được các phần tử của phân phối đồng thời. Xác suất mưa và kẹt xe là 0,3.
That's the probability of rain. And when there's rain, the probability of traffic's 0.9. So it's 0.3 times 0.9. OK, that's a thing I can do.
Đó là xác suất mưa. Và khi có mưa, xác suất kẹt xe là 0,9. Nên là 0,3 nhân 0,9. Được, đó là một việc tôi làm được.
I could run variable elimination or inference by enumeration. And I could answer questions. Like, I could answer, what's the probability of T? Well, we know what the answer looks like.
Tôi có thể chạy khử biến hoặc suy luận bằng liệt kê. Và trả lời các câu hỏi. Ví dụ, xác suất của T là bao nhiêu? Ta biết đáp án trông thế nào.
There's some chance of plus T, and there's some chance of minus T. And then there's some numbers, but I don't know what they are. But I could do some compute, OK?
Có một xác suất cho +t, và có một xác suất cho -t. Rồi có vài con số, nhưng tôi chưa biết chúng là gì. Nhưng tôi có thể tính toán chút, được chứ?
We're not going to do that. Today is sampling day. Instead, what I could do is I could draw some samples from this network, and use these samples to compute some quantities.
Ta sẽ không làm vậy. Hôm nay là ngày của lấy mẫu. Thay vào đó, tôi có thể rút vài mẫu từ mạng này, rồi dùng các mẫu để tính một số đại lượng.
So let's compute a probability of plus T in this network according to samples.
Ta tính xác suất của +t trong mạng này dựa trên các mẫu.
Well, I sort of need to be able to call Python's random in order to get fair samples, so I'm just going to make stuff up. So what's my first sample going to be?
Lẽ ra tôi cần gọi hàm random của Python để có các mẫu công bằng, nhưng tôi sẽ tự bịa ra. Mẫu đầu tiên của tôi sẽ là gì?
Well, what's the most likely sample? The most likely sample, which might not happen first, but the most likely sample would be that there is no rain, OK?
Mẫu nào có khả năng nhất? Mẫu có khả năng nhất, dù có thể không xuất hiện đầu tiên, sẽ là không có mưa, được chứ?
So I flip a coin, and 70% of the time it comes up no rain. So my first sample, let's pretend it's no rain.
Tôi tung đồng xu, và 70% số lần ra không mưa. Vậy mẫu đầu tiên, giả sử là không mưa.
And then at T, I need to pick a value for traffic. So in the no rain case, it's 50:50 whether it will be plus or minus. What would you like?
Rồi ở T, tôi cần chọn giá trị cho kẹt xe. Trong trường hợp không mưa, khả năng 50:50 là có hoặc không kẹt xe. Em muốn chọn gì?
CS188 dot random, go.
CS188 chấm random, bắt đầu.
STUDENT
Plus traffic.
Có kẹt xe.
PROFESSOR
Plus traffic. You want traffic. All right. Well, good thing you're in the Bay Area, OK?
Có kẹt xe. Em muốn kẹt xe à. Được rồi. May là em đang ở Bay Area đấy.
All right. So then we draw another one. All right. Another one minus r.
Được rồi. Rồi ta rút một mẫu khác. Được rồi. Một mẫu nữa, -r.
This one maybe comes out minus traffic. OK, this one, now, there's rain. And now, there is traffic. And now, there's rain again.
Mẫu này có thể ra không kẹt xe. Mẫu này thì có mưa. Và có kẹt xe. Rồi lại có mưa.
And now, there's traffic, OK. And I could keep doing this, all right? So of these four samples that I've just drawn, what is the probability of traffic in these samples?
Và có kẹt xe. Tôi có thể cứ tiếp tục như vậy. Trong bốn mẫu vừa rút này, xác suất kẹt xe là bao nhiêu?
STUDENT
3/4.
3/4.
PROFESSOR
3/4. Is that the probability in the actual underlying distribution? Probably not. But if instead of 4, it were 4,000, or 4 million, I'd probably get pretty close.
3/4. Đó có phải là xác suất trong phân phối gốc thật sự không? Có lẽ không. Nhưng nếu thay vì 4, ta có 4.000 hay 4 triệu mẫu, tôi sẽ có kết quả khá gần.
That's prior sampling. Prior sampling, I sample each node in the network until I have a complete outcome. I write it down. I write the next one.
Đó là lấy mẫu tiên nghiệm. Với lấy mẫu tiên nghiệm, tôi lấy mẫu từng nút trong mạng cho đến khi có một kết quả hoàn chỉnh. Tôi ghi nó xuống. Tôi ghi mẫu tiếp theo.
I write the next one down. And then I answer questions in those samples. Questions about marginals, like, what's the probability of T that have no evidence? That's prior sampling.
Rồi ghi mẫu kế tiếp nữa. Sau đó tôi trả lời các câu hỏi dựa trên những mẫu đó. Các câu hỏi về phân phối biên, ví dụ xác suất của T khi không có bằng chứng? Đó là lấy mẫu tiên nghiệm (prior sampling).
However, if I want to know what's the probability of rain, given traffic, only three of these samples matter. This one matters, this one matters, and this one matters.
Tuy nhiên, nếu tôi muốn biết xác suất có mưa, biết là có kẹt xe, thì chỉ có ba mẫu này là quan trọng. Mẫu này, mẫu này và mẫu này.
But that second sample represents the strange world where there's no traffic. And if I wanted a probability of rain, given traffic, those outcomes don't matter to me.
Nhưng mẫu thứ hai thể hiện một thế giới kỳ lạ nơi không có kẹt xe. Và nếu tôi muốn xác suất có mưa, biết có kẹt xe, thì những kết quả đó không có ý nghĩa với tôi.
So to do rejection sampling — so I just answered probability of distribution over T using prior sampling. And I got plus T, minus T, what was it?
Vậy để làm rejection sampling, tức là lấy mẫu loại bỏ, thì tôi vừa trả lời phân phối xác suất của T bằng prior sampling. Và tôi được plus T, minus T, là bao nhiêu nhỉ?
3/4, 1/4. OK, that was with prior sampling.
3/4, 1/4. Đó là với prior sampling.
Now I'm going to use rejection sampling to answer distribution over — what did I say it was going to be — R given, plus T. All right.
Giờ tôi sẽ dùng rejection sampling để trả lời phân phối của — lúc nãy tôi nói là gì nhỉ — R biết plus T. Được rồi.
I've got three samples that are relevant because one was rejected. That's not bad. I only rejected one. That's because my evidence is plus T, which is pretty common in the samples.
Tôi có ba mẫu liên quan vì có một mẫu bị loại. Vậy cũng không tệ. Tôi chỉ loại một mẫu. Đó là vì bằng chứng của tôi là plus T, khá phổ biến trong các mẫu.
And it's pretty common in the samples because it's pretty common in the underlying model, OK? So rejection sampling — reject, OK? Now, in the remaining samples, what do I get?
Và nó phổ biến trong các mẫu vì nó khá phổ biến trong mô hình nền, được chứ? Vậy rejection sampling là loại bỏ mẫu, nhé? Giờ, trong các mẫu còn lại, tôi được gì?
Probability of R, plus R, or minus R. Plus R is 2/3, and minus R is 1/3 because that's the proportion in the samples that survived the rejection process, meaning the samples that matched my evidence.
Xác suất của R, plus R hoặc minus R. Plus R là 2/3, còn minus R là 1/3, vì đó là tỉ lệ trong các mẫu còn sót lại sau quá trình loại bỏ, nghĩa là các mẫu khớp với bằng chứng của tôi.
Now, normally it doesn't work that well. Was everybody clear on how I draw the samples? We didn't do likelihood weighting, right?
Thông thường thì cách này không hiệu quả lắm. Mọi người đã rõ cách tôi lấy mẫu chưa? Ta chưa làm likelihood weighting, đúng không?
I just drew samples, and then reject the ones that don't match my evidence, and I compute quantities on the ones that are left.
Tôi chỉ lấy mẫu, rồi loại bỏ những mẫu không khớp với bằng chứng, và tính các đại lượng trên những mẫu còn lại.
Draw a lot of samples, you'll get something like the right answer. OK, any questions on that? OK. What about likelihood weighting?
Lấy thật nhiều mẫu, bạn sẽ được một kết quả gần đúng. Có câu hỏi nào về phần này không? Được rồi. Còn likelihood weighting thì sao?
Let's do that again. Oh, I guess if it's gone, we can just do it on the same slide. All right. Let's do this again, except now the network is fire causes alarm.
Ta làm lại nhé. À, nó bị xóa rồi, ta cứ làm trên cùng slide này. Được rồi. Ta làm lại, nhưng giờ mạng là cháy gây ra báo động.
And up here, I need the probability of a fire. And it's either going to be yes fire or no fire. What's the probability of fire?
Và ở trên này, tôi cần xác suất có cháy. Nó sẽ là có cháy hoặc không cháy. Xác suất cháy là bao nhiêu?
Let's call it 0.01, probability of no fire 0.99. All right. Now, we need to know the probability of alarm.
Cứ cho là 0.01, xác suất không cháy là 0.99. Được rồi. Giờ ta cần xác suất của báo động.
Hmm. I still want my other example. I'm sorry I deleted it.
Hmm. Tôi vẫn muốn ví dụ kia. Tiếc là tôi đã xóa mất.
We're going to compare and contrast. There's rain causes traffic. And remember, we decided that probability of rain was — I don't remember what we said.
Ta sẽ so sánh đối chiếu. Có mưa gây ra kẹt xe. Và nhớ là ta đã chọn xác suất mưa là — tôi không nhớ ta đã nói bao nhiêu.
Plus rain, minus rain, 0.3, 0.7. Now, way over here, we have probability of traffic, given rain. There's the plus R case.
Plus rain, minus rain, 0.3, 0.7. Còn bên đây, ta có xác suất kẹt xe, biết mưa. Đây là trường hợp plus R.
There's the minus R case — plus T, minus T, plus T, minus T.
Đây là trường hợp minus R — plus T, minus T, plus T, minus T.
Here this was traffic is 50:50 without rain, but it's 90:10 with rain. OK, so there's our rain and traffic case. So we didn't do likelihood weighting there, but maybe we should.
Ở đây, không mưa thì kẹt xe 50:50, còn có mưa thì 90:10. Vậy đó là ví dụ mưa và kẹt xe. Ở đó ta chưa làm likelihood weighting, nhưng có lẽ nên làm.
Let's do likelihood weighting. So remember, we were computing — we have to have a query.
Ta làm likelihood weighting. Nhớ là ta đang tính — ta phải có một truy vấn.
So let's say, we want to compute the probability of rain, given plus traffic. All right.
Giả sử ta muốn tính xác suất có mưa, biết plus traffic. Được rồi.
So let's compute it. Now, we need to draw some samples. And in this box, I'm going to draw some samples.
Ta tính thử. Giờ ta cần lấy vài mẫu. Và trong khung này, tôi sẽ vẽ vài mẫu.
So what we did before is we drew something like, oh, plus rain, plus T; minus rain, plus T; minus rain, minus T; minus rain, plus T. And then we said, OK, well, that's fine because this one gets crossed out because it doesn't match my evidence.
Lúc trước ta lấy các mẫu như plus rain, plus T; minus rain, plus T; minus rain, minus T; minus rain, plus T. Rồi ta nói, được thôi, không sao vì mẫu này bị gạch bỏ do không khớp với bằng chứng.
Then I compute probability of R over the remaining samples. And in this case, I would get 1/3 probability of rain given traffic, OK? That's what we did before.
Rồi tôi tính xác suất của R trên các mẫu còn lại. Và trong trường hợp này, tôi được xác suất mưa biết kẹt xe là 1/3, nhé? Đó là những gì ta đã làm trước đó.
Let's do that again. Let's do that again, but with likelihood weighting. Why do we do this with likelihood weighting?
Ta làm lại. Làm lại, nhưng với likelihood weighting. Tại sao ta làm với likelihood weighting?
We do it with likelihood weighting because we don't like throwing out samples, especially if we're throwing out 99% of our samples. So let's do some likelihood weighting, all right?
Ta làm vậy vì ta không thích vứt bỏ mẫu, nhất là khi phải vứt tới 99% số mẫu. Vậy ta làm likelihood weighting nhé?
In likelihood weighting, we say, all right, well, we're going to flip a coin. So we know that T is supposed to take on this value plus, OK?
Trong likelihood weighting, ta nói rằng ta sẽ tung đồng xu. Ta biết T phải nhận giá trị plus, đúng không?
So we're going to flip a coin at R and see what we get.
Nên ta sẽ tung đồng xu ở R và xem được gì.
So let's say, we get plus R. Now, normally, we'd flip a coin, and we'd say, T is going to come up plus 90% of the time.
Giả sử ta được plus R. Bình thường ta sẽ tung đồng xu, và T sẽ ra plus 90% số lần.
We're not going to flip the coin. We're just going to take plus, plus T. And we write down the weight.
Ta sẽ không tung đồng xu. Ta cứ lấy plus, plus T. Và ta ghi lại trọng số.
That thing I did, this whole multiverse of samples, 10% of them just got shaved off because they didn't match what actually happened. So let's do another one.
Những gì tôi vừa làm, cả đa vũ trụ các mẫu này, thì 10% trong đó bị loại bỏ vì không khớp với những gì thực sự xảy ra. Ta làm mẫu nữa.
Minus R, let's say that's the sample at R. Now, normally, I would flip a coin at T. And that coin would come up plus or minus 50:50. But you know what?
Minus R, giả sử đó là mẫu tại R. Bình thường tôi sẽ tung đồng xu ở T. Và đồng xu đó ra plus hoặc minus với tỉ lệ 50:50. Nhưng bạn biết không?
I don't want to waste time rejecting the sample. So I'm going to force the sample to be plus T. And you say, wait a minute.
Tôi không muốn tốn thời gian loại bỏ mẫu. Nên tôi sẽ ép mẫu này thành plus T. Và bạn sẽ nói: khoan đã.
It had a 50% chance of not being plus T.
Nó có 50% khả năng không phải là plus T.
And so that beautiful whole sample that I had, half of it is gone because half of it happened in the parallel reality where it came up the wrong way.
Vậy là cả mẫu đẹp đẽ của tôi, một nửa đã mất đi, vì một nửa đó xảy ra trong thực tại song song nơi nó ra theo hướng sai.
So this sample has less weight. So now, I go to do this. Well, let's do another one.
Nên mẫu này có trọng số nhỏ hơn. Giờ tôi làm tiếp bước này. Thôi, làm thêm một mẫu nữa.
Let's do another — let's say, the next sample's plus R, plus T. That will come out with 0.9. So now, when I look at these three samples, nothing's been rejected.
Giả sử mẫu tiếp theo là plus R, plus T. Cái đó sẽ có trọng số 0,9. Giờ nhìn ba mẫu này, không mẫu nào bị loại.
But one of them didn't make it through quite so well as the others because it doesn't match the evidence very well. So it has a smaller weight.
Nhưng có một mẫu không vượt qua tốt bằng những mẫu khác, vì nó không khớp bằng chứng lắm. Nên nó có trọng số nhỏ hơn.
So now what I do, when I ask you the distribution over R, given T, all the samples are now relevant. But they don't all have the same weight.
Giờ khi tôi hỏi phân phối của R, cho trước T, thì mọi mẫu đều có liên quan. Nhưng chúng không có cùng trọng số.
So what is the mass on plus R? So for plus R — that's this one and this one for a total of 1.8.
Vậy khối lượng xác suất của plus R là bao nhiêu? Với plus R, là mẫu này và mẫu này, tổng cộng 1,8.
So here for plus R, I have 1.8. And then for minus R, I just have this one sample, and it doesn't even have as high weight, so 0.5.
Vậy plus R có 1,8. Còn minus R chỉ có mẫu này, mà trọng số cũng không cao, là 0,5.
So as unweighted samples, 2/3 of them are plus R.
Nếu không tính trọng số, 2/3 số mẫu là plus R.
But the actual weighted distribution here, under likelihood weighting, is probability of plus R is 1.8 divided by 2.3.
Nhưng phân phối có trọng số thực sự ở đây, theo likelihood weighting, xác suất của plus R là 1,8 chia 2,3.
Let's call that 0.9, OK? So you get a different answer because the weights affect how much each sample contributes.
Cứ coi là 0,9 nhé? Vậy bạn được đáp án khác vì trọng số ảnh hưởng đến mức đóng góp của mỗi mẫu.
And samples that came off the assembly line matching the evidence really well — like, plus R, probably you were going to get traffic anyway — they have high weights.
Những mẫu ra khỏi dây chuyền mà khớp bằng chứng rất tốt, như plus R, vốn dĩ có lẽ bạn cũng sẽ gặp kẹt xe, thì có trọng số cao.
And the ones that came off the assembly line not really looking like your evidence, but what the heck, let's assign the evidence anyway, they're going to have smaller weight because they represent a much smaller chance that you would have gotten the evidence had you let the sampling occur naturally, OK?
Còn những mẫu ra khỏi dây chuyền trông không giống bằng chứng của bạn lắm, nhưng kệ, cứ gán bằng chứng vào, thì sẽ có trọng số nhỏ hơn vì chúng đại diện cho khả năng thấp hơn nhiều là bạn có được bằng chứng đó nếu để việc lấy mẫu diễn ra tự nhiên, nhé?
Questions on that side before we compare and contrast with fire and alarm? Yep.
Có câu hỏi nào về phần này không, trước khi so sánh với ví dụ cháy và chuông báo? Mời bạn.
STUDENT
All right, so the thing we calculated is the marginal probability of R?
Vậy cái chúng ta vừa tính là xác suất biên của R phải không?
GIÁO SƯ
Or is it — PROFESSOR: Down here?
Hay là... Ở dưới này à?
STUDENT
Yeah.
Vâng.
PROFESSOR
Here, in likelihood weighting, you are always computing the conditional probability of an event, given the evidence that you have fixed because every sample looks like your evidence.
Ở đây, với likelihood weighting, bạn luôn tính xác suất có điều kiện của một sự kiện, cho trước bằng chứng mà bạn đã cố định, vì mọi mẫu đều giống bằng chứng của bạn.
STUDENT
We never calculated marginal probability?
Vậy ta không bao giờ tính xác suất biên ạ?
PROFESSOR
Yeah, actually, you can't calculate the marginal probability of R from this because you've messed with your samples. They're all evidence matching samples.
Đúng, thực ra bạn không thể tính xác suất biên của R từ đây, vì bạn đã can thiệp vào các mẫu. Tất cả đều là mẫu khớp bằng chứng.
Now, I could run likelihood weighting with no evidence, but then it reduces to prior sampling, OK? All right.
Tôi có thể chạy likelihood weighting không có bằng chứng, nhưng khi đó nó thành lấy mẫu tiên nghiệm, nhé? Được rồi.
So that's the basic idea is you go through, and instead of just throwing out samples that don't match your evidence, instead what you're going to do is you're going to make them match your evidence.
Vậy ý tưởng cơ bản là bạn đi qua từng biến, và thay vì chỉ vứt bỏ các mẫu không khớp bằng chứng, thì bạn sẽ ép chúng khớp với bằng chứng.
And some will escape with reasonably high weights, and others will just get their weights reduced because they don't match the evidence very well.
Một số mẫu thoát với trọng số khá cao, số khác thì bị giảm trọng số vì không khớp bằng chứng lắm.
So instead of being rejected when you don't match the evidence, instead you get a smaller weight. And so you have a little bit more signal coming through than if you had just rejected them.
Vậy thay vì bị loại khi không khớp bằng chứng, chúng chỉ nhận trọng số nhỏ hơn. Nhờ đó ta có thêm một chút tín hiệu so với việc loại bỏ chúng.
That's sort of the success case for likelihood weighting. Before we do Gibbs sampling, I want to motivate why we're doing Gibbs sampling. We're doing Gibbs sampling because of the failure case of likelihood weighting.
Đó là trường hợp thành công của likelihood weighting. Trước khi sang Gibbs sampling, tôi muốn giải thích động cơ của Gibbs sampling. Ta dùng Gibbs sampling vì trường hợp thất bại của likelihood weighting.
So the failure case of likelihood weighting is like fire causes alarm. Fire happens only 1% of the time. And what does the alarm do?
Trường hợp thất bại của likelihood weighting là kiểu cháy gây ra chuông báo. Cháy chỉ xảy ra 1% thời gian. Còn chuông báo thì sao?
Well, let's say, we have to say what the alarm does in the fire cases and in the no fire cases.
Giả sử ta phải nói chuông làm gì trong trường hợp có cháy và không cháy.
Maybe in the fire cases, I need to say the alarm can go off, or it can fail to go off.
Có thể khi cháy, chuông có thể kêu, hoặc không kêu.
Let's say 90% of the time it goes off, and 10% of the time it doesn't work. And when there's no fire, sometimes the alarm goes off anyway, and sometimes it doesn't.
Giả sử 90% thời gian nó kêu, và 10% thời gian nó hỏng. Còn khi không cháy, đôi khi chuông vẫn kêu, đôi khi không.
Let's say, 99% of the time it doesn't go off, and 1% of the time you get a false alarm. So here's a domain. This domain seems fine. Let's compute some samples.
Giả sử 99% thời gian nó không kêu, và 1% thời gian là báo động giả. Đây là một miền bài toán. Miền này có vẻ ổn. Hãy tính vài mẫu.
First, what would happen if we did rejection sampling? So first we need a query. So we need a query.
Trước tiên, nếu dùng rejection sampling thì sao? Trước hết cần một truy vấn. Vậy cần một truy vấn.
How about, let's compute the probability of fire, or the distribution over fire, given that my alarm went off. How am I going to compute this?
Ví dụ, tính xác suất của cháy, hay phân phối của F, cho trước chuông báo đã kêu. Tính thế nào đây?
Well, I need samples that say, plus A. So I could do rejection sampling. Let's do some rejection sampling. OK, CS188 dot random, what's the value for F? Remember, it's minus 99% of the time.
Ta cần các mẫu có plus A. Vậy tôi có thể dùng rejection sampling. Làm thử rejection sampling. Nào, CS188 dot random, giá trị của F là gì? Nhớ là 99% thời gian nó là minus.
Minus, all right.
Minus, được rồi.
Now, given that it's minus, we need to pick a probability for A. This is rejection sampling, so I'm not going to rig A. I'm just going to cross my fingers and hope I get the right thing.
Giờ cho F là minus, ta cần chọn xác suất cho A. Đây là rejection sampling, nên tôi không ép A. Tôi chỉ cầu may và hy vọng ra đúng giá trị.
What am I probably going to get? I'm probably going to get that the alarm did not go off. OK, well, this sample's getting rejected because the alarm didn't go off.
Nhiều khả năng tôi sẽ được gì? Nhiều khả năng là chuông báo không kêu. Vậy mẫu này bị loại vì chuông báo không kêu.
Let's try another one. What's going to happen at F? Minus. What's going to happen at A?
Thử mẫu khác. F sẽ ra gì? Minus. A sẽ ra gì?
Minus. OK, reject. Minus, minus A, reject. Minus, minus A, reject.
Minus. OK, loại. Trừ, trừ A, loại. Trừ, trừ A, loại.
OK, there's a fire, and the alarm doesn't go off, reject. OK, so we're going to create a whole lot of samples that get rejected. Well, that's no fun.
OK, có cháy mà chuông báo không kêu, loại. OK, vậy là ta tạo ra cả đống mẫu rồi bị loại hết. Chán thật.
So rejection sampling seems super annoying in this case. Why? Because remember, we reject things unless they happen to match the evidence.
Vậy lấy mẫu loại bỏ (rejection sampling) trong trường hợp này rất phiền. Tại sao? Vì hãy nhớ, ta loại bỏ mọi mẫu trừ khi nó tình cờ khớp với bằng chứng.
And the evidence here is rare because the thing that causes it is rare, OK? So let's erase all these samples because they are not helpful.
Mà bằng chứng ở đây hiếm, vì nguyên nhân gây ra nó cũng hiếm, OK? Vậy xóa hết các mẫu này đi vì chúng không có ích.
Let's do it again because we thought we had the solution. We thought maybe it's a solution to just rig the alarm. Like, the alarm's going off, plus A, OK?
Làm lại, vì ta tưởng mình đã có lời giải. Ta nghĩ có lẽ cách giải quyết là ép cố định chuông báo. Kiểu như chuông đang kêu, cộng A, OK?
Now, we don't know have to — we're not going to do rejection sampling. We're going to do likelihood weighting. I promise every sample will come off with the alarm going off.
Giờ, ta không cần — ta sẽ không dùng lấy mẫu loại bỏ. Ta sẽ dùng likelihood weighting. Tôi đảm bảo mẫu nào cũng có chuông báo kêu.
So let's do it. We're going to flip a coin at F, and we're going to get minus because you always get minus, right? 99% of the time you get minus, but, hey, plus A.
Làm thôi. Ta tung đồng xu tại F, và ta sẽ được trừ, vì lúc nào cũng ra trừ, đúng không? 99% ra trừ, nhưng này, cộng A.
But there's a weight because if I had picked minus F, what's the chance that I actually would have for reals gotten plus A?
Nhưng có một trọng số, vì nếu chọn trừ F, thì xác suất thật sự ra cộng A là bao nhiêu?
90% — sorry. If you say, minus F, the chance that for reals, you would get plus A is only 0.01. So this one only has weight 0.01.
90%... xin lỗi. Nếu là trừ F, xác suất thật sự ra cộng A chỉ là 0.01. Nên mẫu này chỉ có trọng số 0.01.
Like, it's there, but by its weight, it's basically already a dead sample. OK, so what's the next one?
Nó có đó, nhưng xét theo trọng số, về cơ bản nó đã là mẫu chết. OK, mẫu tiếp theo là gì?
Minus F. Well, let's rig plus A. You do that for a long time, and you get a whole bunch of samples that look just like that.
Trừ F. Ép cộng A. Làm vậy một lúc lâu, ta được cả loạt mẫu trông y như thế.
And you say, all right, well, on the plus side, these are coming out matching my evidence.
Và bạn nói, được, mặt tích cực là các mẫu này khớp với bằng chứng của tôi.
On the minus side, all those variables upstream — the samples that I really need are the ones that say plus F because those are the samples that are going to come through with high weight.
Mặt tiêu cực là mọi biến ở phía trên... những mẫu tôi thật sự cần là những mẫu có cộng F, vì đó là những mẫu sẽ có trọng số cao.
And that makes sense because when the alarm goes off, there's probably a fire. OK, maybe someday, a plus F sample will pop off.
Điều đó hợp lý vì khi chuông báo kêu, khả năng cao là có cháy. OK, biết đâu một ngày nào đó, một mẫu cộng F sẽ xuất hiện.
And of course, it will be a plus A sample as well because I'm rigging A. Now, what's the weight on this?
Và tất nhiên nó cũng sẽ là mẫu cộng A, vì tôi ép A. Vậy trọng số của nó là bao nhiêu?
Well, this plus F won't happen very often because P of plus F is small. But given that it does happen, the probability of plus A is 90%.
Cộng F này sẽ không xuất hiện thường xuyên vì P của cộng F nhỏ. Nhưng khi nó đã xảy ra, xác suất của cộng A là 90%.
And so this sample will have weight 0.9. And so even if I have 20 of these, and 1 of these — let's say that.
Nên mẫu này sẽ có trọng số 0.9. Và dù tôi có 20 mẫu loại này, và 1 mẫu loại này — giả sử vậy.
We've got 20 of these, and 1 of these, and then we've got to compute our probability distribution over F, given plus A. Well, there's the plus F samples.
Ta có 20 mẫu loại này, và 1 mẫu loại này, rồi ta phải tính phân phối xác suất của F, cho cộng A. Đây là các mẫu cộng F.
There's the minus F samples. How many plus F samples do I have? 20. But when you weight them, it's just 0.2.
Đây là các mẫu trừ F. Tôi có bao nhiêu mẫu cộng F? 20. Nhưng khi tính trọng số, chỉ là 0.2.
And how about minus F? We've only got one sample, but it has weight 0.9. And then, of course, I have to divide these both by 1.1 to make them normalize, OK?
Còn trừ F thì sao? Ta chỉ có một mẫu, nhưng nó có trọng số 0.9. Rồi tất nhiên tôi phải chia cả hai cho 1.1 để chuẩn hóa, OK?
No, I messed that up.
Không, tôi nói nhầm.
I'm just going to say it again, but right, instead of just swapping them. Let's try that again, but right.
Tôi sẽ nói lại, cho đúng, thay vì chỉ đổi chỗ chúng. Thử lại, lần này cho đúng.
Minus F. There are 20 minus F, plus A samples, but in aggregate they only have weight 0.2. Plus F, plus A, there's only one sample of that, but in aggregate it has weight 0.9.
Trừ F. Có 20 mẫu trừ F, cộng A, nhưng tổng cộng chúng chỉ có trọng số 0.2. Cộng F, cộng A, chỉ có một mẫu như vậy, nhưng tổng cộng nó có trọng số 0.9.
That's not a probability distribution. I have to normalize by the total weight.
Đó chưa phải phân phối xác suất. Tôi phải chuẩn hóa theo tổng trọng số.
But when I do that, I do actually end up with a probability of fire being high, given alarm, even though it took a while for me to actually get a sample that looked like that because my evidence was rare.
Nhưng khi làm vậy, tôi thật sự có xác suất cháy cao, khi biết chuông báo, dù mất một lúc mới có được một mẫu như vậy, vì bằng chứng của tôi hiếm.
So likelihood weighting will do the right thing in the end. But, let's say, I do this again, except fire is now 0.000001, OK?
Vậy likelihood weighting cuối cùng vẫn cho kết quả đúng. Nhưng giả sử tôi làm lại, trừ việc xác suất cháy giờ là 0.000001, OK?
It'll still work, except now, I'm going to get 2 million of the minus F's.
Nó vẫn chạy, nhưng giờ tôi sẽ có 2 triệu mẫu trừ F.
And then finally, finally, finally, maybe, I'll get a sample that actually looks like what really happens with a plus A. And when that appears it will have such high weight that it'll proportionally do the right thing.
Rồi cuối cùng, cuối cùng, có thể tôi sẽ có một mẫu giống với điều thật sự xảy ra khi cộng A. Và khi nó xuất hiện nó sẽ có trọng số cao đến mức theo tỉ lệ nó cho kết quả đúng.
But I'm going to waste a lot of time generating stuff upstream of the rare evidence that isn't typical for that evidence, OK? This is why we need something like Gibbs sampling, all right?
Nhưng tôi sẽ phí rất nhiều thời gian tạo ra những thứ ở phía trên của bằng chứng hiếm mà không điển hình cho bằng chứng đó, OK? Đó là lý do ta cần thứ như Gibbs sampling, được chứ?
Does that make sense? So let's do Gibbs sampling really quickly.
Có hiểu không? Vậy ta làm Gibbs sampling thật nhanh.
In Gibbs sampling, we don't walk through the network — we don't walk through the network from top to bottom, get a sample, and reset.
Trong Gibbs sampling, ta không đi qua mạng từ trên xuống dưới, lấy một mẫu rồi đặt lại.
Instead, we're going to — it's sort of like iterative improvement for [? CSVs. ?] We're going to start with a complete assignment. And we're going to tweak it a little bit.
Thay vào đó, nó hơi giống cải thiện lặp cho CSP. Ta bắt đầu với một phép gán đầy đủ. Và ta chỉnh nó một chút.
The end result is going to be that we take into account evidence upstream and downstream, but there's going to be a price, OK? So here's the procedure. I'll say it in words first.
Kết quả cuối cùng là ta tính đến bằng chứng ở cả phía trên lẫn phía dưới, nhưng sẽ có một cái giá, OK? Đây là quy trình. Trước hết tôi nói bằng lời.
We're going to start with a complete full instantiation. That's an assignment to all variables. For example, random, or draw a prior sample, whatever you want, doesn't matter.
Ta bắt đầu với một phép khởi tạo đầy đủ. Tức là một phép gán cho mọi biến. Ví dụ ngẫu nhiên, hoặc lấy một mẫu tiên nghiệm, tùy bạn, không quan trọng.
OK, you start with a full instantiation that is consistent with your evidence. You're then going to walk to the variables one at a time, round robin, and leave the evidence fixed.
OK, bạn bắt đầu với một phép khởi tạo đầy đủ phù hợp với bằng chứng của bạn. Sau đó bạn đi qua từng biến một, theo vòng tròn, và giữ nguyên bằng chứng.
But for every non-evidence variable, you will resample just that variable, conditioned on all the rest staying fixed. OK, we'll walk through an example of that, but you do this for a long time.
Nhưng với mỗi biến không phải bằng chứng, bạn lấy mẫu lại riêng biến đó, có điều kiện là tất cả các biến còn lại giữ nguyên. OK, ta sẽ đi qua một ví dụ về điều đó, nhưng bạn làm việc này trong một thời gian dài.
And so you change this variable, and this variable, and this variable, and this variable. And you do this. And you get this sequence of assignments.
Bạn đổi biến này, rồi biến này, rồi biến này, rồi biến này. Và bạn cứ làm như vậy. Và bạn thu được một chuỗi các phép gán.
If you repeat this, infinitely many times, the samples that come off are going to come from the correct distribution, where what that is is the probability distribution over all of the non-evidence variables, conditioned on the evidence variables.
Nếu lặp lại vô hạn lần, các mẫu thu được sẽ đến từ đúng phân phối, mà đó là phân phối xác suất trên tất cả các biến không phải bằng chứng, có điều kiện theo các biến bằng chứng.
It's sort of an amazing property. And the basic idea here is that you're resampling everything, but you're leaving the evidence.
Đây là một tính chất khá tuyệt vời. Ý tưởng cơ bản là bạn lấy mẫu lại mọi thứ, nhưng giữ nguyên bằng chứng.
And as you resample things, the evidence can influence the things you're resampling through the other variables in all directions, OK? So let's do an example. All right.
Và khi bạn lấy mẫu lại, bằng chứng có thể ảnh hưởng đến những biến bạn đang lấy mẫu lại thông qua các biến khác, theo mọi hướng, được chứ? Ta làm một ví dụ. Được rồi.
So remember, this is going to be in the cloudy causes sprinkler and rain, both of which cause wet grass. And I'd like to know, what's the probability of sprinkler given rain?
Hãy nhớ, ở đây cloudy gây ra sprinkler và rain, cả hai đều gây ra wet grass. Và tôi muốn biết xác suất của sprinkler khi biết rain là bao nhiêu?
So what I will do is I will fix my evidence. So r has been locked to plus r, just like in likelihood weighting. So here's my Bayes net.
Vậy tôi sẽ cố định bằng chứng của mình. r đã bị khóa ở +r, giống như trong likelihood weighting. Đây là mạng Bayes của tôi.
r has been locked because it's evidence. And what would I do in likelihood weighting?
r bị khóa vì nó là bằng chứng. Trong likelihood weighting thì tôi làm gì?
I'd walk along the other three variables, flipping coins, assigning each variable, given its parents, according to my coin flips, except for plus r which I'd just rig.
Tôi đi qua ba biến còn lại, tung đồng xu, gán giá trị cho từng biến theo các biến cha của nó, dựa trên kết quả tung đồng xu, trừ +r thì tôi gán cứng.
And I'd get a weight out of that. Here, we do something different. We initialize the other variables. Call it random, whatever.
Và từ đó tôi có một trọng số. Ở đây, ta làm khác đi. Ta khởi tạo các biến còn lại. Cứ gọi là ngẫu nhiên, sao cũng được.
And then we're going to repeat the following process. We've got a full assignment. We're going to choose a non-evidence variable. So let's say, we choose s.
Rồi ta lặp lại quá trình sau. Ta có một phép gán đầy đủ. Ta chọn một biến không phải bằng chứng. Giả sử ta chọn s.
I keep the whole rest of my assignment, and I only resample this one variable. Well, I know how to sample a variable, given its parent.
Tôi giữ nguyên toàn bộ phần còn lại của phép gán, và chỉ lấy mẫu lại đúng biến này. Tôi biết cách lấy mẫu một biến khi biết biến cha của nó.
But here, I'm sampling a variable given its parent and its child. And in fact, I'm sampling it given everything else in the network.
Nhưng ở đây, tôi lấy mẫu một biến khi biết cả biến cha và biến con. Thực ra là khi biết mọi thứ còn lại trong mạng.
So we're going to have to think through the math on that. So we're going to resample x from P of x, given all other variables. You say, that's in my Bayes net.
Nên ta sẽ phải suy nghĩ về phần toán ở đây. Vậy ta sẽ lấy mẫu lại x từ P của x, khi biết tất cả các biến khác. Bạn sẽ nói, cái đó có trong mạng Bayes của tôi mà.
That is not in your Bayes net. Your Bayes net has P of x, given its parents. This is P of x, given everything, so we're going to have to compute that.
Không, nó không có trong mạng Bayes của bạn. Mạng Bayes của bạn có P của x khi biết các biến cha. Đây là P của x khi biết mọi thứ, nên ta sẽ phải tính nó.
So we're going to compute — we're going to draw a sample from P of s, given plus c, minus w, plus r — the whole rest of the network.
Vậy ta sẽ tính — ta sẽ rút một mẫu từ P của s, khi biết +c, -w, +r — toàn bộ phần còn lại của mạng.
And so what do we get? We get plus s, great. We're going to pick the next variable. Maybe, that'll be c.
Và ta được gì? Ta được +s, tốt. Ta chọn biến tiếp theo. Có thể là c.
We're going to sample a new value of c, given all of the other assigned variables. Maybe we get plus c, great.
Ta lấy mẫu một giá trị mới của c, khi biết tất cả các biến đã được gán còn lại. Có thể ta được +c, tốt.
Then we go to w, and we resample w, given all of its neighbors. And maybe, we get minus w. And we keep doing this. And we get this chain here of samples.
Rồi ta qua w, và lấy mẫu lại w, khi biết tất cả các biến lân cận của nó. Và có thể ta được -w. Và ta cứ tiếp tục như vậy. Và ta có chuỗi các mẫu này.
First question, when I did prior sampling, each sample walks through the network, and then resets, walk through the network again. So I take sample one, and I take sample two.
Câu hỏi đầu tiên: khi tôi làm prior sampling, mỗi mẫu đi qua mạng, rồi đặt lại, rồi lại đi qua mạng lần nữa. Tôi lấy mẫu một và mẫu hai.
Are sample one and sample two going to — are there going to be correlations between them, given the network? No, they're just totally independent walks through the network, right?
Mẫu một và mẫu hai có — có tương quan với nhau không, khi biết mạng? Không, chúng là những lượt đi qua mạng hoàn toàn độc lập, đúng không?
How about here? Think about this sample and this sample. Are they going to be correlated? Think you have a big network.
Còn ở đây thì sao? Hãy nghĩ về mẫu này và mẫu này. Chúng có tương quan không? Hãy tưởng tượng bạn có một mạng lớn.
You have a huge network. Everything's assigned. You pick variable 712, and you flip a coin. And in the end, what does the network look like compared to before you flipped that variable?
Một mạng khổng lồ. Mọi thứ đều đã được gán. Bạn chọn biến 712 và tung đồng xu. Rốt cuộc, mạng trông như thế nào so với trước khi bạn lật biến đó?
It looks exactly the same, except maybe in one place, OK? So you are no longer drawing independent samples, all right? So the samples are now highly correlated.
Nó trông y hệt, có thể chỉ khác ở một chỗ, được chứ? Vậy là bạn không còn rút các mẫu độc lập nữa. Các mẫu giờ có tương quan rất cao.
We're going to have to deal with that, OK? But you've got these sequence of samples. Each one is a slight variation on the sample that came before it.
Ta sẽ phải xử lý chuyện đó, được chứ? Nhưng bạn có chuỗi các mẫu này. Mỗi mẫu là một biến thể nhỏ của mẫu đứng trước nó.
And if we grab a sample, and then we do this thing for a long time, and we grab another sample, and then we rotate around robin for a while, and we grab another sample, if we wait long enough between samples, then the correlations reduce.
Và nếu ta lấy một mẫu, rồi chạy quá trình này một thời gian dài, rồi lấy một mẫu khác, rồi quay vòng một lúc, rồi lấy thêm một mẫu, nếu ta chờ đủ lâu giữa các mẫu, thì tương quan sẽ giảm.
And now, we're grabbing samples from the joint distribution over all non-evidence variables, conditioned on the evidence variables, OK? So that's great.
Và lúc này, ta đang lấy mẫu từ phân phối đồng thời trên tất cả các biến không phải bằng chứng, có điều kiện theo các biến bằng chứng, được chứ? Vậy là tốt.
We now have this Markov chain we run. And we get sample, sample, sample, sample, sample. And if we draw them too close, they just look exactly like each other.
Giờ ta có chuỗi Markov này để chạy. Và ta được mẫu, mẫu, mẫu, mẫu, mẫu. Nếu ta lấy chúng quá gần nhau, chúng sẽ giống hệt nhau.
But that's actually OK, as long as you run it long enough. That's great. That will give us the ability to draw samples that condition upstream and downstream on our evidence.
Nhưng thực ra cũng không sao, miễn là bạn chạy đủ lâu. Tuyệt. Cách này cho ta khả năng rút các mẫu có điều kiện theo bằng chứng cả ở phía trên lẫn phía dưới.
But we need to do computation to get from one state in the chain to the next.
Nhưng ta cần tính toán để đi từ một trạng thái trong chuỗi sang trạng thái kế tiếp.
And in particular, we need to be able to compute what is the probability of the currently flipping variable, given the whole rest of the network. Well, that sounds bad, right?
Cụ thể, ta cần tính được xác suất của biến đang được lật khi biết toàn bộ phần còn lại của mạng. Nghe có vẻ tệ, đúng không?
Isn't this what got us into trouble, was trying to compute conditional probabilities of things, given other things? It's not so bad. And the reason it's not — so wow, that's a lot of math.
Chẳng phải chính điều này đã gây rắc rối cho ta sao, là cố tính các xác suất có điều kiện của việc này khi biết việc khác sao? Thực ra không tệ đến thế. Lý do là... chà, nhiều toán quá.
OK, let's walk through it. The reason it's not so bad is because the probability distribution over s, conditioned on some assignment to the rest — it will look this way for any network, OK?
Ta cùng đi qua từng bước. Lý do nó không tệ là vì phân phối xác suất của s, có điều kiện là một phép gán nào đó cho phần còn lại sẽ có dạng này với mọi mạng, được chứ?
It's a variable conditioned on an assignment to everything else. Well, that's going to be a ratio.
Đó là một biến có điều kiện là phép gán cho tất cả các biến còn lại. Đó sẽ là một tỉ số.
And then the numerator is just an entry of my Bayes net — a probability of all the variables all together.
Tử số chỉ là một mục của mạng Bayes, tức xác suất của tất cả các biến cùng nhau.
And the denominator is the exact same thing, but summed over, in this case, s. So I can rewrite that like this.
Còn mẫu số y hệt, nhưng được lấy tổng theo s, trong trường hợp này. Nên tôi viết lại như thế này.
That's a probability of one entry of the joint distribution divided by the sum of a bunch of similar entries in the joint distribution that only differ on the value of s.
Đó là xác suất của một mục trong phân phối đồng thời chia cho tổng của nhiều mục tương tự trong phân phối đồng thời, chỉ khác nhau ở giá trị của s.
So if you expand that out, so from here to here, this is P of scrw is a product of local conditional probabilities because that's the definition of a joint probability in a Bayes net.
Nếu khai triển ra, từ chỗ này sang chỗ này, P của scrw là tích của các xác suất có điều kiện cục bộ, vì đó là định nghĩa của xác suất đồng thời trong mạng Bayes.
But then I look at this, and I'm like, huh, this numerator came from the Bayes net formula. The denominator came from the Bayes net formula.
Nhưng nhìn vào đây, tôi thấy, tử số này đến từ công thức mạng Bayes. Mẫu số cũng đến từ công thức mạng Bayes.
And if we look, we see that actually quite a lot of those terms have nothing to do with s. Like, P of plus c is in the numerator and the denominator, right?
Và nếu để ý, ta thấy khá nhiều số hạng chẳng liên quan gì đến s. Chẳng hạn, P của plus c có ở cả tử và mẫu, đúng không?
And P of whatever this is, plus r plus c is in the numerator and the denominator.
Và P của cái này, plus r plus c, cũng có ở cả tử và mẫu.
And in general, almost everything in the network is in the numerator and the denominator in the exact same way because it doesn't mention this one variable that's changing.
Nói chung, hầu như mọi thứ trong mạng đều có ở cả tử và mẫu theo cùng một cách, vì chúng không nhắc đến biến đang thay đổi này.
And so everything cancels out. And you're left with something really simple. You're left with the following algorithm, which is you want to resample this network.
Nên mọi thứ triệt tiêu. Và còn lại một thứ rất đơn giản. Ta còn lại thuật toán sau, đó là bạn muốn lấy mẫu lại mạng này.
You look at all the terms in the network which mention that variable. These are exactly the things you would join together in variable elimination. You take all the terms that mention that.
Bạn xem tất cả các số hạng trong mạng có nhắc đến biến đó. Đây đúng là những thứ bạn sẽ nối với nhau trong khử biến. Bạn lấy mọi số hạng nhắc đến nó.
You assign them. And then you normalize over all the different values of s, and that's it.
Bạn gán giá trị cho chúng. Rồi chuẩn hóa trên tất cả các giá trị khác nhau của s, vậy là xong.
And the whole rest of the network doesn't matter because it's going to cancel out, because it's contribution to the likelihood function is the same regardless of what you set s to, all right?
Phần còn lại của mạng không quan trọng vì nó sẽ triệt tiêu, vì đóng góp của nó vào hàm khả năng là như nhau dù bạn đặt s bằng giá trị nào, được chứ?
So almost everything cancels out. You're left with only conditional probabilities with s. And in general, only the ones with the resampled variables need to be considered.
Vậy hầu như mọi thứ đều triệt tiêu. Chỉ còn lại các xác suất có điều kiện chứa s. Nói chung, chỉ cần xét những số hạng chứa biến được lấy mẫu lại.
And so it's efficient to resample a single variable. It's not trivial. It's not sitting in the Bayes net, like it was for prior or rejection sampling. But it's efficient.
Nên lấy mẫu lại một biến đơn lẻ là hiệu quả. Nó không tầm thường. Nó không có sẵn trong mạng Bayes như với lấy mẫu tiên nghiệm hay lấy mẫu loại bỏ. Nhưng nó hiệu quả.
And you get this nice algorithm that lets you take into account evidence in both directions. There's a couple things I didn't specify yet.
Và bạn có một thuật toán hay cho phép tính đến bằng chứng ở cả hai hướng. Có vài điều tôi chưa nói rõ.
Didn't talk about how many samples you need, so that your [? error bars ?] get small. That's the thing you would see in a statistics class.
Chưa nói cần bao nhiêu mẫu để sai số nhỏ đi. Đó là thứ bạn sẽ thấy trong lớp thống kê.
I didn't talk about how far you have to run this Markov chain and Gibbs sampling in order to escape your initial conditions. We didn't talk about that.
Tôi chưa nói phải chạy chuỗi Markov này và Gibbs sampling bao lâu để thoát khỏi điều kiện ban đầu. Ta chưa bàn đến điều đó.
And we didn't talk about some of — we didn't talk about why it is yet, that if you run Gibbs sampling somehow upstream and downstream evidence is both conditioned.
Và ta cũng chưa bàn về vì sao khi chạy Gibbs sampling thì bằng chứng thượng nguồn và hạ nguồn đều được điều kiện hóa.
But it should feel plausible because you lockdown your evidence, and then you're sampling a bunch of things.
Nhưng điều này nghe có vẻ hợp lý, vì bạn cố định bằng chứng, rồi bạn lấy mẫu một loạt thứ.
And each time you sample a node, you push a little bit of information up, and down, and around the network. So it should make sense that that all gets smeared around the network.
Và mỗi lần lấy mẫu một nút, bạn đẩy một chút thông tin lên trên, xuống dưới và khắp mạng. Nên hợp lý là tất cả sẽ được lan tỏa khắp mạng.
But we haven't proven anything about it. OK, so in summary, we have the following algorithms. We have prior sampling.
Nhưng ta chưa chứng minh gì về điều đó. Tóm lại, ta có các thuật toán sau. Ta có lấy mẫu tiên nghiệm.
This is where you walk down the Bayes net from the top, so that you can use the conditional probabilities of nodes, given just their parents, because that's easy.
Đó là khi bạn đi xuống mạng Bayes từ trên đỉnh, để dùng được các xác suất có điều kiện của nút khi chỉ biết cha của nó, vì việc đó dễ.
You walk down the network, and you draw a sample. That's great for computing P of a query without evidence. If you have evidence, you do the exact same thing.
Bạn đi xuống mạng và lấy một mẫu. Cách này tốt để tính P của truy vấn khi không có bằng chứng. Nếu có bằng chứng, bạn làm y hệt.
You walk down the network, but you throw out all of the samples that don't end up matching your evidence. It's a very simple algorithm.
Bạn đi xuống mạng, nhưng loại bỏ mọi mẫu cuối cùng không khớp với bằng chứng. Đó là thuật toán rất đơn giản.
But it might be very slow because you're going to reject almost everything. You're going to reject 1 minus the probability of your evidence stuff.
Nhưng có thể rất chậm vì bạn sẽ loại bỏ gần hết mọi thứ. Bạn sẽ loại bỏ 1 trừ xác suất của bằng chứng.
We had likelihood weighting, which is also to answer P of Q, given some evidence. Here, every sample is relevant, but sometimes, they all have so low weight that you didn't really gain much.
Ta có likelihood weighting, cũng để trả lời P của Q khi biết bằng chứng nào đó. Ở đây mọi mẫu đều liên quan, nhưng đôi khi tất cả đều có trọng số quá thấp nên chẳng được lợi bao nhiêu.
But sometimes, if the evidence is high enough in the network, your samples actually are all much better. And this can be much faster to converge than rejection sampling.
Nhưng đôi khi, nếu bằng chứng ở đủ cao trong mạng, các mẫu của bạn thực sự tốt hơn nhiều. Và cách này có thể hội tụ nhanh hơn nhiều so với lấy mẫu loại bỏ.
And finally, we have Gibbs sampling, which is a very different style of sampling, where you compute a sequence of samples.
Và cuối cùng là Gibbs sampling, một kiểu lấy mẫu rất khác, trong đó bạn tính một chuỗi các mẫu.
These have the property that you take into account evidence upstream and downstream in a naturally unified way.
Chúng có tính chất là tính đến bằng chứng thượng nguồn và hạ nguồn một cách thống nhất tự nhiên.
But there were a lot more questions about non-independence of samples and about the actual math you have to do in order to resample a single variable, conditioned on the rest of the network.
Nhưng có nhiều câu hỏi hơn về việc các mẫu không độc lập và về phép toán thực tế bạn phải làm để lấy mẫu lại một biến đơn lẻ, có điều kiện là phần còn lại của mạng.
There's a lot more that we're not going to cover.
Còn nhiều điều nữa mà ta sẽ không đề cập.
There's actually not a ton more to say about rejection sampling, and likelihood weighting, and what little there is to say, we'll say it when we see particle filtering with hidden Markov models.
Thực ra cũng không còn nhiều để nói thêm về rejection sampling và likelihood weighting, và chút ít cần nói thì chúng ta sẽ nói khi học lọc hạt với mô hình Markov ẩn (HMM).
But on Gibbs sampling, there's a lot more that we're not going to talk about here. So it does produce samples from probability of query, given evidence.
Nhưng về Gibbs sampling thì còn rất nhiều điều chúng ta sẽ không đề cập ở đây. Nó thật sự tạo ra các mẫu từ xác suất của truy vấn, cho trước bằng chứng.
But again, only under certain conditions of how long you run it, and how often you — how you space your samples, and so on, depending on what you're doing.
Nhưng một lần nữa, chỉ trong một số điều kiện nhất định về việc chạy bao lâu, và bao lâu thì lấy một mẫu — tức là cách bạn giãn cách các mẫu, v.v., tùy vào việc bạn đang làm.
Gibbs sampling has a special case of something you might have heard of, called Markov chain Monte Carlo. There's a more general category called Metropolis-Hastings samplers, which you may have heard about.
Gibbs sampling là một trường hợp đặc biệt của thứ mà có thể các bạn đã nghe, gọi là Markov chain Monte Carlo. Có một nhóm tổng quát hơn gọi là các bộ lấy mẫu Metropolis-Hastings, có thể bạn đã nghe nói.
They're very famous. Gibbs sampling is a special case of that. But it has its own flaws that are addressed by Metropolis-Hastings. And you can read about these things.
Chúng rất nổi tiếng. Gibbs sampling là một trường hợp đặc biệt của nó. Nhưng nó có những điểm yếu riêng mà Metropolis-Hastings khắc phục được. Các bạn có thể tự đọc về những thứ này.
In fact, any time you see the word Monte Carlo, that usually means sampling. So you could take a look at that stuff. We're not going to cover that here.
Thật ra, bất cứ khi nào bạn thấy từ Monte Carlo, thường nó có nghĩa là lấy mẫu. Nên các bạn có thể xem qua. Chúng ta sẽ không học phần đó ở đây.
OK, that's it for today. We will see you next time.
Được rồi, hôm nay đến đây thôi. Hẹn gặp lại các bạn lần sau.
We will talk about taking everything we've done with the Bayes nets, merging it with what we were doing with action selection earlier, and start thinking about associating utilities with knowledge and value of information.
Chúng ta sẽ lấy tất cả những gì đã làm với mạng Bayes, kết hợp với phần chọn hành động đã học trước đó, và bắt đầu nghĩ đến việc gắn độ hữu dụng với tri thức và giá trị của thông tin.
[SIDE CONVERSATION] Yeah, of course.
[HỘI THOẠI RIÊNG] Vâng, tất nhiên rồi.
Đă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.