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ả.
[INTERPOSING VOICES]
[NHIỀU NGƯỜI NÓI CHEN NHAU]
PROFESSOR
Hi, everyone. Welcome to the 18th lecture of CS188. Two announcements today.
Chào các bạn. Chào mừng đến với bài giảng thứ 18 của CS188. Hôm nay có hai thông báo.
The project [? 2 ?] mini contest results are ready for presentation. I'll present them right after the break in today's lecture.
Kết quả cuộc thi nhỏ của project [? 2 ?] đã sẵn sàng để trình bày. Tôi sẽ trình bày ngay sau giờ giải lao của bài hôm nay.
And you have one thing to work on momentarily, which is homework 8, which, as always, consists of three parts. Self-assessment of the previous one, then a written, and an electronic.
Và trước mắt các bạn có một việc cần làm, đó là bài tập về nhà 8, như mọi khi, gồm ba phần. Tự đánh giá bài trước, rồi phần viết tay, và phần làm trên máy.
And that's due on Monday. Any questions about logistics?
Hạn nộp là thứ Hai. Có câu hỏi nào về các vấn đề hậu cần không?
OK. Today's topic is Hidden Markov Models, possibly the most frequently used Bayes net model.
Được rồi. Chủ đề hôm nay là mô hình Markov ẩn (HMM), có lẽ là mô hình mạng Bayes được dùng thường xuyên nhất.
Before we do the math, let's look at a quick demo.
Trước khi làm phần toán, ta xem nhanh một demo.
So this is what the Pac-Man world in your project 4 will look like. So what we got here, we've got Pac-Man in the top left corner.
Đây là thế giới Pac-Man trong project 4 của các bạn, trông sẽ như thế này. Ở đây ta có Pac-Man ở góc trên bên trái.
We've got what looks like an empty board. But actually, there's ghosts on there. But they're invisible. And Pac-Man is more powerful than you're used to in this project.
Bàn chơi trông như trống không. Nhưng thật ra có các con ma trên đó. Nhưng chúng vô hình. Và trong project này Pac-Man mạnh hơn so với những gì các bạn quen.
Pac-Man can blast a ghost whenever they're on the same square. So Pac-Man wins out.
Pac-Man có thể hạ một con ma bất cứ khi nào chúng ở cùng một ô. Vậy là Pac-Man thắng.
And the goal is to find the ghosts, track him down, and take him out, put him into ghost jail, which is the bottom left. So how to do this.
Mục tiêu là tìm ra các con ma, lần theo dấu, hạ gục và nhốt nó vào nhà tù ma, ở góc dưới bên trái. Vậy làm thế nào?
Well, you could start running around. This is just me playing with a keyboard. And the bottom right, you see four numbers hop up and down. And those are the distances to the different ghosts.
Bạn có thể cứ chạy loanh quanh. Đây chỉ là tôi chơi bằng bàn phím. Ở góc dưới bên phải, bạn thấy bốn con số nhảy lên xuống. Đó là khoảng cách đến từng con ma.
There's four ghosts. And there's different distances to the different ghosts. And these ghosts are actually moving around. So let's see.
Có bốn con ma. Và khoảng cách đến mỗi con là khác nhau. Và những con ma này thực ra đang di chuyển. Ta xem nhé.
Moving closer to blue ghost — maybe, oh. We're very close to blue ghost. Sometimes, 0. But we still didn't eat it somehow.
Đang lại gần con ma xanh dương, có thể là, ồ. Ta rất gần con ma xanh dương. Có lúc là 0. Nhưng không hiểu sao vẫn chưa ăn được nó.
Let's see if we can find another ghost. So it's pretty hard to do to find these ghosts when you can't see them and all you have is distance measurements.
Xem có tìm được con ma khác không. Khá khó để tìm những con ma này khi không nhìn thấy chúng và chỉ có các số đo khoảng cách.
But if you manage to run into one of them, you would actually get points. Oh, we ran into the cyan colored ghost. Actually, they ran into us.
Nhưng nếu bạn tình cờ đụng phải một con, bạn sẽ được điểm. Ồ, ta đụng phải con ma màu lục lam. Thật ra là nó đụng vào ta.
And this gave us a ghost in jail, which gives us points. Let's see if another one wants to run into us.
Và thế là ta có một con ma vào tù, được cộng điểm. Xem con khác có muốn đâm vào ta không.
You should try to help them, of course, with your program — not just sit still. Where is the orange one? Looks like we're getting closer.
Tất nhiên bạn nên giúp chúng bằng chương trình của mình, chứ đừng chỉ ngồi yên. Con màu cam đâu rồi? Có vẻ ta đang lại gần.
It's not that easy a game to play just looking at these numbers. And that's the motivation for today's lecture.
Đây không phải trò dễ chơi nếu chỉ nhìn vào những con số này. Và đó là động lực cho bài hôm nay.
If you have access to these numbers that were shown at the bottom here, can you do a calculation that makes it possible to — another one got themselves eaten.
Nếu bạn có những con số hiển thị ở phía dưới này, bạn có thể tính toán để có thể, à, lại một con nữa tự đâm vào để bị ăn.
These are not the smartest ghosts.
Những con ma này không thông minh lắm.
If you have access to those numbers, can you do something better than this poor play I've been doing here, by maybe somehow extracting information about where the ghosts are most likely, and then move towards that?
Nếu có những con số đó, liệu bạn có làm tốt hơn cách chơi tệ hại này của tôi, bằng cách bằng cách nào đó rút ra thông tin về nơi các con ma có khả năng ở nhất, rồi di chuyển về phía đó không?
And that's what HMM tools will give us. Of course, it's not just for tracking down ghosts. We'll see other applications for HMMs. So this will be all probabilistic reasoning.
Và đó là điều các công cụ HMM sẽ mang lại cho ta. Tất nhiên, nó không chỉ để săn ma. Ta sẽ thấy các ứng dụng khác của HMM. Toàn bộ phần này sẽ là suy luận xác suất.
So quick probability recap. What is Conditional Probability, which will be key here?
Nên ta ôn nhanh về xác suất. Xác suất có điều kiện, khái niệm then chốt ở đây, là gì?
Conditional probability is, in this case, conditional of x given y is the probability of x and y are both taken on the values xy divided by probability of y.
Xác suất có điều kiện, trong trường hợp này, của x cho trước y là xác suất để x và y đồng thời nhận các giá trị x, y, chia cho xác suất của y.
So the fraction of the time, we have small x among the times that we have small y.
Tức là tỉ lệ số lần có x nhỏ trong số các lần có y nhỏ.
Product rule is rearranging this and allows us to compose a joint distribution from a marginal and a conditional. The chain rule is repeated application of this. Essentially, the same thing.
Quy tắc nhân là sắp xếp lại công thức này, cho phép ta tạo phân phối đồng thời từ một phân phối biên và một phân phối có điều kiện. Quy tắc chuỗi là áp dụng lặp lại điều này. Về cơ bản là cùng một thứ.
You can do this is in any order of your choice for n factorial choices of expanding the chain rule.
Bạn có thể làm theo thứ tự bất kỳ với n giai thừa cách khai triển quy tắc chuỗi.
And x and y are independent if and only if, for all values x and y, can take on the probability of x and y is equal to probability of x times the probability of y.
Và x và y độc lập khi và chỉ khi, với mọi giá trị x và y, xác suất của x và y bằng xác suất của x nhân xác suất của y.
And then Conditional Independence is the same idea. But conditional independence, instead of having just x and y, there's also z. And you just condition everywhere on z.
Và độc lập có điều kiện cũng là ý tưởng đó. Nhưng với độc lập có điều kiện, thay vì chỉ có x và y, còn có thêm z. Và bạn chỉ cần đặt điều kiện z ở mọi chỗ.
And that's generally true in these equalities that we have for probabilities. If you have something that's true, in this case for x and y, you can just conditional z everywhere.
Và điều đó nói chung đúng với các đẳng thức mà ta có cho xác suất. Nếu có điều gì đúng, ở đây là cho x và y, bạn có thể đặt điều kiện z ở mọi chỗ.
And it'll still be true. And that's exactly what we did here. x and y are conditionally independent given z if this condition holds true for all values of x, y, and z.
Và nó vẫn đúng. Và đó chính xác là điều ta đã làm ở đây. x và y độc lập có điều kiện cho trước z nếu điều kiện này đúng với mọi giá trị của x, y và z.
And this is our notation for conditional independence. So we covered a lot of that in the context of Bayes nets. And today we're going to see a special kind of Bayes net.
Và đây là ký hiệu của ta cho độc lập có điều kiện. Ta đã học nhiều về điều này trong ngữ cảnh mạng Bayes. Và hôm nay ta sẽ thấy một loại mạng Bayes đặc biệt.
That sees a particularly large amount of use compared to most Bayes nets. OK. Well, what we want to do is reason about sequences of observations. Where might this pop up in the real world?
Loại này được dùng nhiều hơn hẳn so với hầu hết các mạng Bayes. Được rồi. Điều ta muốn làm là suy luận về các chuỗi quan sát. Điều này xuất hiện ở đâu trong thực tế?
Let's say, speech recognition. In speech recognition, you get a sequence of numbers coming in corresponding to the pressure of the air, at that time.
Chẳng hạn, nhận dạng giọng nói. Trong nhận dạng giọng nói, bạn nhận vào một chuỗi các số tương ứng với áp suất không khí tại thời điểm đó.
And you're supposed to decode that into a sentence or something. In Remote Localization, you have a robot going around a building.
Và bạn phải giải mã điều đó thành một câu hay thứ gì đó. Trong định vị robot, bạn có một robot đang di chuyển trong một tòa nhà.
But even though we can see where the robot is, for the robot itself to know where it is, it needs to use some sensory information. That sensory information will not be perfect.
Dù chúng ta thấy robot đang ở đâu, nhưng để chính robot biết nó đang ở đâu, nó cần dùng một số thông tin từ cảm biến. Thông tin cảm biến đó sẽ không hoàn hảo.
It might have sensory information from maybe a camera looking around or from a lidar, which is a laser beam you send out. And then, it bounces back at you, if you're lucky.
Nó có thể có thông tin cảm biến từ một camera quan sát xung quanh hoặc từ lidar, tức là một tia laser bạn phát ra. Rồi nó phản xạ trở lại, nếu bạn may mắn.
And then you measure how long it took before it got back to you. And then, you multiply that with the speed of light.
Sau đó bạn đo xem mất bao lâu thì tia quay lại. Rồi bạn nhân thời gian đó với vận tốc ánh sáng.
And then based on that, you know how far away that obstacle is. You need a really good timer, obviously. Because speed of light is very, very fast. But that's actually used quite often.
Từ đó bạn biết vật cản ở cách bao xa. Rõ ràng là bạn cần một bộ đếm thời gian thật tốt. Vì vận tốc ánh sáng rất, rất nhanh. Nhưng cách này thực tế được dùng khá thường xuyên.
User Attention. As a user's navigating your website, then goes to another website, what do you expect them to do? What might they be caring about on your website?
Sự chú ý của người dùng. Khi một người dùng đang duyệt trang web của bạn, rồi sang trang web khác, bạn đoán họ sẽ làm gì? Họ có thể quan tâm điều gì trên trang của bạn?
Medical Monitoring. Let's say you have a patient in the intensive care unit. You're measuring a lot of signals.
Theo dõi y tế. Giả sử bạn có một bệnh nhân trong phòng chăm sóc đặc biệt. Bạn đang đo rất nhiều tín hiệu.
Can you, from that, infer — from the aggregate of signals you've seen so far — infer if there's any emergency and you should call in a physician, or whether you can just leave them alone and let them rest?
Từ đó bạn có thể suy ra được không — từ tổng hợp các tín hiệu đã thấy cho đến giờ — liệu có tình huống khẩn cấp và cần gọi bác sĩ, hay có thể để họ yên và nghỉ ngơi?
So it's all about aggregating signals from the past into drawing a conclusion about what situation you are in right now. So we'll need to introduce time or space into our models.
Vậy tất cả là tổng hợp các tín hiệu trong quá khứ để rút ra kết luận về tình huống mà bạn đang gặp ngay lúc này. Vì vậy ta cần đưa thời gian hoặc không gian vào mô hình.
So here's a Bayes net in which we have time index variables. So x is the state of a system. xi is the state of a system at time i.
Đây là một mạng Bayes có các biến được đánh chỉ số theo thời gian. x là trạng thái của hệ thống. xi là trạng thái của hệ thống tại thời điểm i.
We've seen this before. In market decision processes, we had a state. We called it s. It's called x, now.
Ta đã thấy điều này trước đây. Trong quá trình quyết định Markov, ta có một trạng thái. Ta gọi nó là s. Bây giờ nó gọi là x.
Essentially, it's the same thing. We have a state of the world. And it can vary over time — be different at every time step. It can also stay the same.
Về bản chất, nó là một thứ. Ta có một trạng thái của thế giới. Và nó có thể thay đổi theo thời gian — khác nhau ở mỗi bước thời gian. Nó cũng có thể giữ nguyên.
What we have here, also, is actually a — this here is a Bayes net, where does a conditional probability distribution for x2 given x1, the distribution for x3 given x2, and so forth.
Ở đây ta cũng có — đây là một mạng Bayes, trong đó có phân phối xác suất có điều kiện của x2 cho x1, phân phối của x3 cho x2, và cứ thế.
And what's special about these models that the parameters we'll use will be tied, meaning that we'll have a generic distribution for xt given xt minus 1 that is the same for every time step.
Điều đặc biệt ở các mô hình này là các tham số ta dùng sẽ được ràng buộc chung, nghĩa là có một phân phối chung của xt cho xt trừ 1, giống nhau ở mọi bước thời gian.
This was actually also true in our MDP models. It was always the same transition model. We're going to make the same assumption here.
Điều này cũng đúng trong các mô hình MDP của ta. Mô hình chuyển luôn là một. Ở đây ta cũng đưa ra giả thiết như vậy.
And so, even though this Bayes net could, in principle, be infinitely long, the number of parameters is bounded. It's actually not that many. There was just two tables.
Nên dù mạng Bayes này về nguyên tắc có thể dài vô hạn, số tham số vẫn bị chặn. Thực ra không nhiều lắm. Chỉ có hai bảng.
One table for the conditional. And one table for the initial distribution. OK. So this parameters here are called transition probabilities — or dynamics — and specify how the state evolves over time.
Một bảng cho phân phối có điều kiện. Và một bảng cho phân phối ban đầu. OK. Các tham số này gọi là xác suất chuyển — hay động lực học — và cho biết trạng thái tiến triển thế nào theo thời gian.
And then these are the initial state probabilities. [? So ?] this narrative assumption is that the transition probabilities stay the same at all times.
Còn đây là các xác suất của trạng thái ban đầu. Giả thiết ở đây là các xác suất chuyển không đổi ở mọi thời điểm.
If somebody says, we have a non-stationary process, then you'll need a different transition model for every time. So, same as MDPs. But what's missing is actions. We're not going to worry about actions.
Nếu ai đó nói ta có một quá trình không dừng, thì bạn cần một mô hình chuyển khác cho mỗi thời điểm. Vậy giống như MDP. Nhưng thiếu các hành động. Ta sẽ không bận tâm đến hành động.
They're not going to be present in this lecture. OK. So what are some conditional independencies implied by this Bayes net? Well, past and the future are independent, given the present.
Chúng sẽ không xuất hiện trong bài giảng này. OK. Vậy mạng Bayes này hàm ý những tính độc lập có điều kiện nào? Tức là quá khứ và tương lai độc lập với nhau, khi biết hiện tại.
When we know this variable — let's call this, the present, time t.
Khi ta biết biến này — ta gọi hiện tại là thời điểm t.
Then once we know that variable, knowing something about the future does not tell us anything about the past and the other way around. We can calculate that with deseparation.
Thì một khi biết biến đó, biết điều gì đó về tương lai sẽ không cho ta biết gì về quá khứ, và ngược lại. Ta có thể tính điều đó bằng d-separation.
Or we can just intuitively re-conclude that. Each time step only depends on the previous.
Hoặc có thể suy ra trực giác. Mỗi bước thời gian chỉ phụ thuộc vào bước trước đó.
To predict what happens at the next time, just knowing the current time is the best thing you can know to predict that. Knowing more things about the past is not going to help you.
Để dự đoán điều xảy ra ở thời điểm kế tiếp, chỉ cần biết thời điểm hiện tại là điều tốt nhất bạn có thể biết để dự đoán. Biết thêm về quá khứ cũng không giúp ích gì.
This is called a First Order Markov property. You might say, well, what if it doesn't apply in my situation?
Đây gọi là tính chất Markov bậc nhất. Bạn có thể hỏi, nếu nó không áp dụng trong tình huống của tôi thì sao?
What if, in my situation, the state of the next time depends on the state of the current time and the state of the previous time?
Nếu trạng thái ở thời điểm kế tiếp phụ thuộc vào trạng thái hiện tại và trạng thái ở thời điểm trước đó thì sao?
Well, to still be able to fit it in this format and to really fit the notion of what actually it means to be a state, you should then combine the state of the current time and the state of the previous time, in one bigger state variable that you now call your state.
Để vẫn đưa được vào dạng này và đúng với ý nghĩa thực sự của một trạng thái, bạn nên gộp trạng thái hiện tại và trạng thái ở bước trước, thành một biến trạng thái lớn hơn mà giờ bạn gọi là trạng thái.
And then you can use this model again. Because now it is bigger state, which includes current state and previous time step state in your original formulation together is enough to predict next state.
Và rồi bạn lại dùng được mô hình này. Vì giờ trạng thái lớn hơn, gồm trạng thái hiện tại và trạng thái bước trước trong cách mô tả ban đầu của bạn, cùng nhau đủ để dự đoán trạng thái kế tiếp.
Predict here could be probabilistic, of course. So really what this is just a Bayes net that you can keep growing.
Dĩ nhiên dự đoán ở đây có thể mang tính xác suất. Vậy thực chất đây chỉ là một mạng Bayes mà bạn có thể tiếp tục mở rộng.
And as time goes by, you keep growing it to keep up with time passing. Or as you traverse space, you keep growing it to keep up with the amount of space you have traversed.
Và khi thời gian trôi, bạn mở rộng nó để theo kịp thời gian trôi qua. Hoặc khi bạn đi qua không gian, bạn mở rộng nó để theo kịp lượng không gian mà bạn đã đi qua.
If we want to do any probabilistic reasoning in this Bayes net, what we can do is we can just say, OK, we'll look at everything up to the current time or up to the time we care about, cap it off, and then we can run our standard Bayes net inference algorithms.
Nếu muốn suy luận xác suất nào đó trong mạng Bayes này, ta có thể nói rằng, OK, ta sẽ xét mọi thứ cho đến thời điểm hiện tại hoặc đến thời điểm ta quan tâm, rồi cắt ngang ở đó, rồi chạy các thuật toán suy luận mạng Bayes chuẩn.
We can do variable elimination. We can do sampling and so forth.
Ta có thể dùng khử biến. Ta có thể dùng lấy mẫu, v.v.
But we'll see in this lecture and next lecture is some variations of this algorithms that are easy to derive from first principles for Markov models and that have equivalence simplifications of the sampling and variable elimination algorithms you've already seen.
Nhưng trong bài này và bài sau, ta sẽ thấy một số biến thể của các thuật toán này, dễ suy ra từ các nguyên lý cơ bản cho mô hình Markov và là các dạng đơn giản hóa tương đương của các thuật toán lấy mẫu và khử biến mà các em đã học.
OK. Let's look at an example Markov chain. Here we have a state space with two possible values the state can take on. It can be rainy or sunny.
Được rồi. Hãy xem một ví dụ chuỗi Markov. Ở đây ta có không gian trạng thái với hai giá trị mà trạng thái có thể nhận. Trời có thể mưa hoặc nắng.
And maybe we observe this on a daily basis. So Monday, sunny. Tuesday, sunny. Wednesday, rainy.
Và giả sử ta quan sát hằng ngày. Thứ Hai, nắng. Thứ Ba, nắng. Thứ Tư, mưa.
Thursday, rainy, and so forth. So our initial distribution is going to say, it's sunny on the first time slice.
Thứ Năm, mưa, và cứ thế. Phân phối ban đầu sẽ cho biết ở bước thời gian đầu tiên trời nắng.
And our conditional probability table — our dynamics model — is given by this table over here saying that when it's sunny, there is a 90% chance of sunny again the next day.
Còn bảng xác suất có điều kiện, tức mô hình động lực học, là bảng ở đây, cho biết khi trời nắng, có 90% khả năng hôm sau vẫn nắng.
When it's rainy, there is a 70% chance it's rainy again the next day and then the complimentary probability of being sunny.
Khi trời mưa, có 70% khả năng hôm sau vẫn mưa, và xác suất bù là trời nắng.
All right. So now we can start doing some calculations with this. But also, let's look at a few other visualizations. So this is one way to look at it.
Được rồi. Giờ ta có thể bắt đầu tính toán. Nhưng hãy xem thêm vài cách biểu diễn khác. Đây là một cách nhìn.
That's rolling out the Markov model. Another way to represent the conditional probability table is to look at it in this format. So this looks like a finite state automaton.
Đó là trải mô hình Markov ra. Một cách khác để biểu diễn bảng xác suất có điều kiện là dùng dạng này. Nó trông như một automat hữu hạn trạng thái.
There is two possible values the state can be. So you have rain or sun and then there [? are ?] transition probabilities associated with each possible transition.
Trạng thái có hai giá trị có thể. Tức là mưa hoặc nắng, và có xác suất chuyển gắn với mỗi phép chuyển có thể.
So that's a pretty valid way to think of a Markov model.
Đó là một cách hợp lý để nghĩ về mô hình Markov.
Another way to represent it and keep time a little more explicit in it is do essentially the same thing, but unroll one step when you draw this thing.
Một cách khác, thể hiện thời gian rõ hơn một chút, về cơ bản cũng như vậy, nhưng trải ra một bước khi vẽ.
Because when you go from sun to rain, it's really at the next time it'll be rainy. And so this model on the right makes that a little more explicit that you progress in time.
Vì khi đi từ nắng sang mưa, thực ra là ở thời điểm kế tiếp trời mưa. Và mô hình bên phải thể hiện rõ hơn việc thời gian tiến lên.
OK. Any questions about the formalism?
Được rồi. Có câu hỏi nào về cách biểu diễn này không?
Then let's do some calculations. So let's say the initial distribution is all probability on sun. What is the distribution after one time step? So let's see.
Vậy ta tính toán thử. Giả sử phân phối ban đầu dồn toàn bộ xác suất vào nắng. Phân phối sau một bước thời gian là gì? Để xem nào.
Let's think about this. We have the initial distribution. We have a dynamics model for next state given current state.
Hãy nghĩ thử. Ta có phân phối ban đầu. Ta có mô hình động lực học cho trạng thái kế tiếp theo trạng thái hiện tại.
So we should be able to combine both of those to get the distribution at the next time step. OK.
Nên ta có thể kết hợp cả hai để có phân phối ở bước thời gian kế tiếp. Được rồi.
Probability of it being sunny at the next time step is the probability of it could initially be sunny or rainy. When it's sunny, then we need to transition from sun to sun.
Xác suất trời nắng ở bước kế tiếp là: ban đầu trời có thể nắng hoặc mưa. Khi nắng, ta cần chuyển từ nắng sang nắng.
When it's rainy, you transition from rain to sun. That's how a generic updated equation could go from a distribution at time 1 to a distribution at time 2.
Khi mưa, ta chuyển từ mưa sang nắng. Đó là cách một phương trình cập nhật tổng quát đi từ phân phối ở thời điểm 1 sang phân phối ở thời điểm 2.
This particular case, initially we put a probability of 1 on sun. So only this first term here will have a non-zero contribution.
Trong trường hợp này, ban đầu ta đặt xác suất 1 cho nắng. Nên chỉ có số hạng đầu tiên ở đây đóng góp khác không.
And it'll be, in this case, the transition model was 90% chance of staying sunny. We knew it was sunny at time 1. So we have 0.9 times 1 gives us 0.9.
Và ở đây, mô hình chuyển cho 90% khả năng giữ nguyên nắng. Ta biết ở thời điểm 1 trời nắng. Vậy 0,9 nhân 1 được 0,9.
OK. So what is the probability for x taking on a certain value on some time t in the further future?
Được rồi. Vậy xác suất để x nhận một giá trị nào đó tại thời điểm t xa hơn trong tương lai là bao nhiêu?
Well, what we just did, we can actually repeat that process quite easily. Because it gave us the distribution of time 2.
Điều vừa làm, ta có thể lặp lại rất dễ dàng. Vì nó cho ta phân phối ở thời điểm 2.
And going from 2 to 3 is the same calculation as going from 1 to 2. So we can just iterate this same calculation over and over to progress over time.
Và đi từ 2 sang 3 là cùng phép tính như đi từ 1 sang 2. Nên ta cứ lặp đi lặp lại phép tính này để tiến theo thời gian.
Writing this out on the slides. We know distribution at time 1.
Viết ra trên slide. Ta biết phân phối ở thời điểm 1.
Then for time t, well, we say, we could compute it recursively based on the distribution of time t minus 1, which is this summation over here — the sum over all possible values we could have time t minus 1 — jointly with xt.
Rồi với thời điểm t, ta tính đệ quy dựa trên phân phối ở thời điểm t trừ 1, là tổng ở đây, tổng trên mọi giá trị có thể có ở thời điểm t trừ 1, đồng thời với xt.
This itself we don't have available. But we have a conditional of xt, given xt minus 1. And we'll recursively assume we have xt minus 1 distribution. So that gives us this expression over here.
Bản thân đại lượng này ta không có sẵn. Nhưng ta có xác suất có điều kiện của xt theo xt trừ 1. Và ta giả sử đệ quy rằng đã có phân phối của xt trừ 1. Từ đó ta có biểu thức này.
And this is an expression we can apply for each time slice to propagate forward to any time we care about.
Biểu thức này áp dụng được cho từng bước thời gian để lan truyền tiến đến bất kỳ thời điểm nào ta quan tâm.
And this here with forward simulation — that's referring to the model that we have available to model how the dynamics works in this world.
Và đây, mô phỏng tiến, là nói đến mô hình ta có để mô hình hóa cách thế giới này vận hành.
OK. So that now means we can run things forward in time.
Được rồi. Vậy giờ ta có thể chạy tiến theo thời gian.
If we have a distribution at the initial time, we can use this update equation here to get the distribution at the next time.
Nếu có phân phối ở thời điểm ban đầu, ta dùng phương trình cập nhật này để có phân phối ở thời điểm kế tiếp.
If you think about it, what is actually going on here — think about the Markov model. You have x1, x2. It's a Bayes net with two variables.
Nghĩ kỹ thì điều thực sự đang diễn ra ở đây là gì? Hãy nghĩ về mô hình Markov. Có x1, x2. Đó là mạng Bayes với hai biến.
You have all the distributions, all the tables. You have instantiated a distribution for the initial time for x1. And now you're running variable elimination to get the distribution for x2.
Ta có mọi phân phối, mọi bảng. Ta đã gán một phân phối cho thời điểm đầu, x1. Và giờ ta chạy khử biến để có phân phối cho x2.
So you're trying to compute p of x2 in this Bayes net. If you do that with variable elimination, you'll get the exact same expression shown here. Will not be any different.
Tức là ta tính p của x2 trong mạng Bayes này. Nếu làm bằng khử biến, ta sẽ được đúng biểu thức hiển thị ở đây. Không khác gì cả.
But this is such a simple situation. It's easier to just rederive it from scratch than to go through the very general framework and then finally arrive here. OK.
Nhưng tình huống này đơn giản đến mức suy ra lại từ đầu còn dễ hơn là đi qua khung tổng quát rồi cuối cùng mới đến được kết quả này. OK.
So let's do this. Let's say, initially, it's sunny. We've observed it. So all probability mass is on sun.
Ta làm thế này. Giả sử ban đầu trời nắng. Ta đã quan sát được điều đó. Vậy toàn bộ khối xác suất nằm ở nắng.
We can propagate forward in our model. We already did that for one time step. It became 0.9, 0.1. What if you propagate forward again?
Ta có thể lan truyền tiến trong mô hình. Ta đã làm điều đó cho một bước thời gian. Nó thành 0.9, 0.1. Nếu lan truyền tiến thêm lần nữa thì sao?
With same calculation, we end up with 0.84, 0.16. We can keep repeating this. And if we keep running this forever, if we had the patience.
Với cùng phép tính, ta được 0.84, 0.16. Ta có thể cứ lặp lại như vậy. Và nếu cứ chạy mãi mãi, nếu ta đủ kiên nhẫn.
But if we run it long enough, we already see the pattern occurring — [? will ?] converge onto 0.75, 0.25. This might remind you of something we've done before, also.
Nhưng nếu chạy đủ lâu, ta đã thấy quy luật xuất hiện: nó sẽ hội tụ về 0.75, 0.25. Điều này có thể gợi bạn nhớ đến một thứ ta đã làm trước đây.
In value iteration, in policy evaluation, we had an updated equation. It was done for the values. Now it's for the distribution over states. And if you repeated the update equation infinitely often.
Trong lặp giá trị, trong đánh giá chính sách, ta có một phương trình cập nhật. Nó được áp dụng cho các giá trị. Giờ nó áp dụng cho phân phối trên các trạng thái.
It would converge to a stationary point. OK. What about if initially we observe it's raining? So we start from 0 and 1.
Và nếu lặp phương trình cập nhật vô hạn lần, nó sẽ hội tụ về một điểm dừng. OK. Còn nếu ban đầu ta quan sát thấy trời mưa thì sao? Ta bắt đầu từ 0 và 1.
We can follow the same update equation. We now get 0.3, 0.7. And we can repeat this process over and over and over and see what happens.
Ta dùng cùng phương trình cập nhật. Giờ ta được 0.3, 0.7. Và ta có thể lặp đi lặp lại quá trình này và xem chuyện gì xảy ra.
We actually end up with the same distribution at time t equals infinity. So just like value attrition policy evaluation, it doesn't matter how you initialize your values.
Ta thực sự có cùng một phân phối tại thời điểm t bằng vô cùng. Giống như lặp giá trị và đánh giá chính sách, cách khởi tạo các giá trị không quan trọng.
There it was because it decays over time because of the discount factor. Here it's a slightly different effect, which we'll discuss in a little bit.
Ở đó là vì nó suy giảm theo thời gian do hệ số chiết khấu. Ở đây hiệu ứng hơi khác một chút, ta sẽ bàn sau.
But intuitively, it's the notion that if there is some randomness in the next day's weather, over time, the information about the weather on the first day will be erased.
Nhưng theo trực giác, nếu thời tiết ngày hôm sau có tính ngẫu nhiên, thì theo thời gian, thông tin về thời tiết ngày đầu tiên sẽ bị xóa mất.
Because it will not affect anymore what you expect to happen. Let's say, I ask you today, what's the weather going to be like in the year — I don't know — 3,000.
Vì nó không còn ảnh hưởng đến điều bạn kỳ vọng sẽ xảy ra. Giả sử hôm nay tôi hỏi bạn, thời tiết vào năm 3.000 sẽ thế nào.
You will not be basing that on exactly what the weather is like today. That will not affect your decision on what the weather will be like in the year 3,000.
Bạn sẽ không dựa vào chính xác thời tiết hôm nay. Điều đó sẽ không ảnh hưởng đến quyết định của bạn về thời tiết năm 3.000.
It's too far out. And the transition model will dominate, not the initial distribution. I can do this with anything. You can have any initial distribution.
Nó quá xa. Và mô hình chuyển sẽ chi phối, chứ không phải phân phối ban đầu. Tôi có thể làm điều này với bất cứ thứ gì. Bạn có thể có phân phối ban đầu bất kỳ.
And if you do the calculation with that transition model, you'll find you converge onto the same distribution. 0.75, 0.25.
Và nếu tính với mô hình chuyển đó, bạn sẽ thấy nó hội tụ về cùng một phân phối. 0.75, 0.25.
Of course, the specific numbers here are specific to the fact that we have the conditional probability tables shown early on here.
Tất nhiên, các con số cụ thể ở đây phụ thuộc vào việc ta có các bảng xác suất có điều kiện đã cho ở đầu.
This conditional probability table is what results in that particular stationary distribution.
Bảng xác suất có điều kiện này là thứ tạo ra phân phối dừng cụ thể đó.
OK. Let's take a look at this in action. I think you've seen this grid in the value of perfect information lecture. So what are these numbers?
OK. Ta xem nó hoạt động thế nào. Tôi nghĩ bạn đã thấy lưới này trong bài giảng về giá trị của thông tin hoàn hảo. Vậy những con số này là gì?
They are the probabilities of the ghost being in that particular spot. There's only one ghost in this case. Let's first find this ghost by doing a few measurements.
Chúng là xác suất con ma ở đúng vị trí đó. Trường hợp này chỉ có một con ma. Trước hết hãy tìm con ma này bằng vài phép đo.
Where is the ghost? Somewhere here it seems. Pretty high probability. OK.
Con ma ở đâu? Có vẻ ở đâu đó quanh đây. Xác suất khá cao. OK.
Now this button here — we're not going to worry about busting the ghost in this lecture — this button here, time plus 1, will make time progress.
Nút này đây, bài giảng này ta sẽ không lo việc diệt con ma, nút time plus 1 này sẽ cho thời gian trôi.
The ghost is moving randomly in this dynamics model. So equal probability of moving to any neighboring square. So if we make time pass, what do we expect to happen?
Con ma di chuyển ngẫu nhiên trong mô hình động này. Nên xác suất di chuyển sang mỗi ô lân cận là như nhau. Vậy nếu cho thời gian trôi, ta kỳ vọng điều gì?
We expect the probability mass to spread out from being all concentrated here to neighboring squares. So let's see if that happens. Indeed. Probability mass is sifting out.
Ta kỳ vọng khối xác suất lan ra từ chỗ tập trung hết ở đây sang các ô lân cận. Xem có đúng vậy không. Đúng thế. Khối xác suất đang tỏa ra.
So the ghost stays in place with a high probability and then sometimes randomly moves off to a neighboring square. So let time pass again, again, again.
Con ma ở yên tại chỗ với xác suất cao và đôi khi ngẫu nhiên di chuyển sang một ô lân cận. Cho thời gian trôi tiếp, lại tiếp.
The probability mass will diffuse more and more and ultimately diffuse back out over the entire board that we have here if we play this long enough. Takes a while, though.
Khối xác suất sẽ khuếch tán ngày càng nhiều và cuối cùng khuếch tán ra toàn bộ bàn cờ nếu ta chạy đủ lâu. Nhưng mất khá nhiều thời gian.
A lot of clicking. If we play this long enough, what we'll see is that we'll hit the stationary distribution where this doesn't change anymore. And it doesn't matter where we started.
Phải bấm rất nhiều. Nếu chạy đủ lâu, ta sẽ thấy đạt tới phân phối dừng, tức là nó không thay đổi nữa. Và không quan trọng ta bắt đầu từ đâu.
The distribution will be the same. What do we expect? It'll go back to the uniform distribution where everything is the same probability. It's starting to get closer.
Phân phối sẽ như nhau. Ta kỳ vọng điều gì? Nó sẽ quay về phân phối đều trong đó mọi ô có xác suất bằng nhau. Nó bắt đầu tiến gần hơn.
But this will require a lot more clicks before it gets all the way out there. Infinity, in this case, is not super close to us.
Nhưng sẽ cần bấm nhiều hơn nữa mới đến được đích. Trường hợp này, vô cùng không gần lắm.
But we're getting there, at least, with most of the probability mass largely spread out and only very little left on the initial square. OK.
Nhưng ít nhất ta đang tiến tới, với phần lớn khối xác suất đã lan rộng và chỉ còn rất ít ở ô ban đầu. OK.
So that's the process of probability mass diffusing as time passes by. Now this becomes more interesting when you have more interesting dynamics.
Đó là quá trình khối lượng xác suất khuếch tán theo thời gian. Giờ nó sẽ thú vị hơn khi có động lực học thú vị hơn.
So here we have circular dynamics, which means the ghosts will be going around in a circle. So what do you expect to happen when I press time plus 1?
Ở đây ta có động lực học vòng tròn, nghĩa là các con ma sẽ đi vòng quanh theo một vòng tròn. Các em nghĩ điều gì sẽ xảy ra khi tôi bấm time plus 1?
I see some No nods. Because, actually, nothing's going to happen. These numbers are going to stay the same.
Tôi thấy có người lắc đầu. Đúng, vì thực ra sẽ không có gì xảy ra cả. Các con số này sẽ giữ nguyên.
Because if the ghost moves around in a circle, well, all that mass will just shift around and fall right back into place. So time plus 1, time plus 1, time plus 1.
Vì nếu con ma đi vòng quanh theo vòng tròn, thì toàn bộ khối lượng đó chỉ dịch chuyển rồi rơi đúng về vị trí cũ. Nên time plus 1, time plus 1, time plus 1.
We're on the stationary distribution already for the circular motion. And so as time passes, nothing changes. We hit the stationary distribution from the beginning.
Ta đã ở phân phối dừng ngay từ đầu với chuyển động tròn. Vì vậy theo thời gian, không có gì thay đổi. Ta đạt phân phối dừng ngay từ đầu.
Now if I go find the ghost to change this distribution a little bit — let's see, somewhere here. OK. We got some pretty high probability here for the ghost.
Giờ nếu tôi đi tìm con ma để thay đổi phân phối này một chút, để xem, đâu đó ở đây. OK. Ta có xác suất khá cao ở đây cho con ma.
If now we let time pass, what do we expect to happen? We expect that high probability to move around in a circle. Actually, for you guys, it'll move around in a circle this way.
Nếu giờ để thời gian trôi, các em nghĩ điều gì xảy ra? Ta kỳ vọng xác suất cao đó di chuyển vòng quanh theo vòng tròn. Thực ra, với các em, nó sẽ di chuyển theo vòng tròn theo hướng này.
Let's see if that indeed happens. So there's the ghost moving around in a circle. That's our estimate of where that ghost is. The ghost doesn't need to be here at the red square.
Xem có đúng vậy không. Đây là con ma di chuyển theo vòng tròn. Đó là ước lượng của ta về vị trí con ma. Con ma không nhất thiết ở ô đỏ này.
We think, 50% chance the ghost is there. And probability mass keeps following along with what we expect to happen.
Ta nghĩ có 50% khả năng con ma ở đó. Và khối lượng xác suất cứ đi theo điều ta kỳ vọng sẽ xảy ra.
But at the same time, diffusing, because there is some probability the ghost moves randomly off to the side instead of following the circular pattern.
Nhưng đồng thời nó khuếch tán, vì có một xác suất con ma di chuyển ngẫu nhiên sang bên cạnh thay vì theo mẫu vòng tròn.
And what do we expect to happen if we keep pushing the time plus 1 button?
Và nếu ta cứ tiếp tục bấm nút time plus 1 thì sao?
As more and more time passes, we'll go back to the stationary distribution where every square has a probability of 0.2. And again, this might require more clicks than we have patience for.
Khi thời gian trôi qua nhiều hơn, ta sẽ quay về phân phối dừng trong đó mỗi ô có xác suất 0,2. Và lại nữa, có thể cần nhiều lần bấm hơn mức ta đủ kiên nhẫn.
But we see it's already getting pretty close just a few rounds into what would be a full circle around. Now right now, we have no idea where the ghost is.
Nhưng ta thấy nó đã khá gần chỉ sau vài vòng trong một vòng tròn đầy đủ. Bây giờ ta không biết con ma ở đâu.
The probability mass is largely diffused over the entire board. What's another example of a distribution or a dynamics model? In this one, it's a whirlpool. So the ghost spins to the center.
Khối lượng xác suất phần lớn đã khuếch tán khắp bàn cờ. Một ví dụ khác về phân phối hay mô hình động lực học là gì? Ở đây là một xoáy nước. Con ma xoay vào tâm.
Wherever you start, you spin around, but towards the center. So what happens if I just do time plus 1 here? This is not the stationary distribution. Because you're inclined to spin to the center.
Bắt đầu ở đâu thì bạn cũng xoay vòng, nhưng hướng về tâm. Vậy nếu tôi bấm time plus 1 ở đây thì sao? Đây không phải phân phối dừng. Vì bạn có xu hướng xoáy vào tâm.
So no matter where you are, a bunch of probability mass is going to shift around that circle and towards the center.
Nên dù ở đâu, một lượng lớn khối lượng xác suất sẽ dịch chuyển quanh vòng đó và về phía tâm.
So as I keep pushing time plus 1, here, actually, without even measuring anything, because the stationary distribution is fairly concentrated to those two squares, we actually find out where the ghost is by just letting time pass and doing the appropriate calculation.
Khi tôi cứ bấm time plus 1, ở đây, thậm chí không cần đo đạc gì, vì phân phối dừng khá tập trung vào hai ô đó, ta thực sự biết con ma ở đâu chỉ bằng cách để thời gian trôi và thực hiện phép tính phù hợp.
So, OK. It looks like the ghost is either here or there. We can go check, measure where the ghost actually is. It doesn't look like the ghost ended up there just yet.
OK. Có vẻ con ma ở đây hoặc ở kia. Ta có thể đo để kiểm tra con ma thực sự ở đâu. Có vẻ con ma chưa đến đó.
But it may be pretty close. So we now have observed the ghost is most likely here. We'll let time pass. What do you expect to happen?
Nhưng có thể khá gần. Giờ ta đã quan sát thấy con ma nhiều khả năng ở đây. Ta để thời gian trôi. Các em nghĩ điều gì xảy ra?
It will go back to — we'll see it circle around, while drifting towards the center. And once it's in the center, it hops back and forth between those two squares.
Nó sẽ quay lại... ta sẽ thấy nó đi vòng quanh, đồng thời trôi về phía tâm. Và khi đã ở tâm, nó nhảy qua lại giữa hai ô đó.
It's just how the whirlpool dynamics work in this world. So we've seen a few different world dynamics here. The first one was just randomly moving into a neighboring square.
Đó chỉ là cách động lực học xoáy nước vận hành trong thế giới này. Vậy ta đã thấy vài động lực học thế giới khác nhau. Cái đầu tiên là di chuyển ngẫu nhiên sang một ô lân cận.
The stationary distribution was uniform over all the squares, as we saw.
Phân phối dừng là đều trên mọi ô, như ta đã thấy.
Then we saw the going around in a circle, where also the stationary distribution was uniform and a little bit of noise was in there. And then this one here, it's drifting to the middle.
Rồi ta thấy chuyển động vòng tròn, trong đó phân phối dừng cũng đều và có thêm một chút nhiễu. Còn cái này thì trôi về giữa.
And the stationary distribution is then putting probability mass mostly in the middle. So usually when time passes, we lose information about where the ghost might be.
Và phân phối dừng khi đó đặt phần lớn khối lượng xác suất ở giữa. Thường thì khi thời gian trôi, ta mất thông tin về vị trí con ma.
But for very specific dynamics, where things converge together automatically, you can just let time pass and learn about where the ghost is.
Nhưng với những động lực học rất đặc biệt, nơi mọi thứ tự hội tụ lại, bạn chỉ cần để thời gian trôi là biết được con ma ở đâu.
Any questions about this?
Có câu hỏi nào về phần này không?
Yes.
Vâng.
STUDENT
[INAUDIBLE] all the probabilities sum up to 1 because there's only one goes to — PROFESSOR: There's only one ghost here. This probability should always sum up to 1.
[KHÔNG NGHE RÕ] tất cả xác suất cộng lại bằng 1 vì chỉ có một cái đi tới — GIÁO SƯ: Ở đây chỉ có một con ma. Xác suất này luôn phải cộng lại bằng 1.
I'm not sure if you were doing all the calculations in your head while these were flashing by.
Không biết em có nhẩm tính trong đầu không khi các số này nhấp nháy qua.
It's possible that they didn't always perfectly sum to 1 because of rounding errors showing only a small number of digits.
Có thể chúng không phải lúc nào cũng cộng đúng bằng 1 do sai số làm tròn khi chỉ hiển thị một vài chữ số.
But under the hood, they will sum to 1 if you show them in full precision.
Nhưng bên dưới, chúng sẽ cộng lại bằng 1 nếu hiển thị đầy đủ độ chính xác.
OK. Let's think a bit more about stationary distributions. For most chains, the influence of the initial distribution gets less and less over time.
OK. Ta hãy nghĩ thêm một chút về phân phối dừng. Với hầu hết các chuỗi, ảnh hưởng của phân phối ban đầu giảm dần theo thời gian.
And so the distribution we end up with is independent of how you started out. There are exceptions to this. You can carefully design exceptions to this.
Và vì vậy phân phối ta nhận được cuối cùng độc lập với cách bạn bắt đầu. Có những ngoại lệ. Bạn có thể cố ý thiết kế ngoại lệ.
But the most common case that you'll encounter — and if you just randomly put some transition model in place by randomly choosing numbers, this is what will happen — the stationary distribution is the distribution you hit at that point.
Nhưng trường hợp phổ biến nhất mà các em sẽ gặp, và nếu bạn chỉ đặt bừa một mô hình chuyển bằng cách chọn số ngẫu nhiên, đây là điều sẽ xảy ra, là như vậy — phân phối dừng chính là phân phối mà bạn đạt tới tại thời điểm đó.
The stationary distribution is one where, if you apply the transition model, nothing changes.
Phân phối dừng là phân phối mà nếu bạn áp dụng mô hình chuyển thì không có gì thay đổi.
So actually, rather than applying the transition model infinitely often to understand what is now the stationary distribution, you can also just set up an equation.
Thực ra, thay vì áp dụng mô hình chuyển vô hạn lần để tìm ra phân phối dừng, bạn cũng có thể chỉ cần lập một phương trình.
You can say, the distribution at time infinity plus 1 has to be equal to the distribution at time infinity. That's what it means to be stationary, [? where ?]
Bạn nói rằng phân phối tại thời điểm vô cùng cộng 1 phải bằng phân phối tại thời điểm vô cùng.
it's the infinite time stationary distribution. This is the update equation. And so we can solve this system of equations here to directly solve for the stationary distribution.
Đó là ý nghĩa của tính dừng, ở đây là phân phối dừng tại thời gian vô hạn. Đây là phương trình cập nhật. Và vì vậy ta có thể giải hệ phương trình này để tìm trực tiếp phân phối dừng.
It's just linear equations. Because the transition model here — transition model — is known as the [? p ?] infinity of x — that's unknown. Those are the unknown variables.
Chỉ là các phương trình tuyến tính. Vì mô hình chuyển ở đây mô hình chuyển đã biết, còn p infinity của x thì chưa biết. Đó là các biến chưa biết.
You might say, isn't 0 a solution? Yeah. So you need to find a solution to this linear system of equations that is not the solution that makes everything 0.
Bạn có thể hỏi: 0 không phải là một nghiệm sao? Đúng vậy. Nên bạn cần tìm nghiệm của hệ phương trình tuyến tính này mà không phải là nghiệm làm mọi thứ bằng 0.
You need to find — there's actually infinitely many solutions to this equation. There will typically be only one solution where all entries sum to 1. And that's the solution you want to find.
Thực ra phương trình này có vô số nghiệm. Thường chỉ có một nghiệm mà tất cả các phần tử có tổng bằng 1. Và đó là nghiệm bạn muốn tìm.
So you want to solve this linear system, in addition to sum over x — p infinity x equals 1.
Vậy bạn muốn giải hệ tuyến tính này, cùng với tổng theo x của p infinity x bằng 1.
If you add this equation to the system of linear equations we already have there, then there will be, most typically, a unique solution, which is your stationary distribution.
Nếu thêm phương trình này vào hệ phương trình tuyến tính ta đã có, thì thông thường sẽ có một nghiệm duy nhất, chính là phân phối dừng của bạn.
This should actually remind you of something we saw when we covered Markov decision processes and we looked at policy evaluation.
Điều này hẳn gợi bạn nhớ tới thứ ta đã thấy khi học quá trình quyết định Markov và xem xét việc đánh giá chính sách.
In policy evaluation, we saw you can iterate the value attrition equations where you removed the max. And you just choose the action based on the policy.
Trong đánh giá chính sách, ta thấy có thể lặp các phương trình lặp giá trị trong đó bạn bỏ max đi. Và bạn chỉ chọn hành động dựa trên chính sách.
And that gives you the value of that policy for each state.
Điều đó cho bạn giá trị của chính sách đó ở mỗi trạng thái.
Or you could realize that once you removed the max, this is just a linear system of equations, and just solve the linear system of equations directly to evaluate the value of a policy at each state.
Hoặc bạn nhận ra rằng khi đã bỏ max, đây chỉ là một hệ phương trình tuyến tính, và chỉ cần giải hệ phương trình tuyến tính đó trực tiếp để đánh giá giá trị của chính sách tại mỗi trạng thái.
Same thing here. We could either iterate, which would be, likely, a lot of work.
Ở đây cũng vậy. Ta có thể lặp, mà nhiều khả năng sẽ mất rất nhiều công.
If we asked you on an exam, find the stationary distribution, if you iterate, you're going to be busy for a long time. And you might not have time to solve some other questions.
Nếu đề thi yêu cầu tìm phân phối dừng, mà bạn lặp thì sẽ bận rộn rất lâu. Và có thể bạn không còn thời gian làm các câu khác.
But if you use this equation and say, I just need to solve those linear system of equations — and if we ask you to do that, it'll probably be a linear system that's very easy to solve.
Nhưng nếu dùng phương trình này và nói: mình chỉ cần giải hệ phương trình tuyến tính đó và nếu chúng tôi yêu cầu, thì có lẽ đó là một hệ rất dễ giải.
Then you could just solve that linear system of equations, have the solution, and be done.
Bạn chỉ việc giải hệ phương trình tuyến tính đó, có nghiệm, và xong.
OK. Let's look at some examples.
OK. Hãy xem vài ví dụ.
And let's use the linear system of equations to find the stationary distribution of the rain, sunny Markov model. OK.
Và hãy dùng hệ phương trình tuyến tính để tìm phân phối dừng của mô hình Markov mưa, nắng. OK.
This is the two equations that say, the distribution at time infinity should be the same after one update.
Đây là hai phương trình nói rằng phân phối tại thời điểm vô cùng phải giữ nguyên sau một lần cập nhật.
The equations — the right hand sides are what happens with one time update. OK. So the unknowns are these guys here.
Các phương trình, vế phải là điều xảy ra sau một lần cập nhật thời gian. OK. Các ẩn số là những đại lượng này.
The lot of them are the same. There's not six separate unknowns. There's only two unknowns here. p infinity of rain. p infinity of sun.
Nhiều cái trong số đó giống nhau. Không có sáu ẩn số riêng biệt. Ở đây chỉ có hai ẩn số. p infinity của mưa, p infinity của nắng.
The other four entries, which I'm drawing lines underneath, those are just numbers that we can take from this table over here. Let's fill them out. Now let's solve this system of equations.
Bốn phần tử còn lại, những cái tôi gạch dưới, chỉ là các con số mà ta có thể lấy từ bảng ở đây. Ta điền vào. Giờ hãy giải hệ phương trình này.
Do a little bit of work. We get this here. Actually, we see that both of those equations tell us the same thing. It's really only one equation.
Biến đổi một chút. Ta được thế này. Thực ra, ta thấy cả hai phương trình cho ta cùng một điều. Thật ra chỉ có một phương trình.
But also, we have that they need to sum to 1. And that gives us the solution summing to 1. And 1 has to be three times the other one.
Nhưng ta còn có điều kiện tổng bằng 1. Và điều đó cho ta nghiệm có tổng bằng 1. Và một giá trị gấp ba lần giá trị kia.
Then it's going to be 0.75 and 0.25, which is our solution. Any questions about how this was done? Yes.
Vậy là 0.75 và 0.25, đó là nghiệm của ta. Có câu hỏi nào về cách làm này không? Mời bạn.
STUDENT
[INAUDIBLE] PROFESSOR: There will always be at least one solution.
[KHÔNG NGHE RÕ] GIÁO SƯ: Luôn có ít nhất một nghiệm.
It is not guaranteed that there is a unique solution. And so, let's think about this. How could we end up with a non-unique solution? Let's think about the iteration case, all right?
Không đảm bảo là nghiệm duy nhất. Hãy nghĩ về điều này. Làm sao ta có thể có nghiệm không duy nhất? Hãy nghĩ về trường hợp lặp nhé.
Let's imagine your initial state could be either in Wheeler or in Soda hall. And let's say your dynamics model is such that when you're in Soda, you cannot leave Soda.
Giả sử trạng thái ban đầu của bạn có thể ở Wheeler hoặc ở Soda hall. Và giả sử mô hình động lực của bạn là khi đang ở Soda, bạn không thể rời Soda.
And when you're in Wheeler, you cannot leave Wheeler. Then all of a sudden, your initial state will determine the stationary distribution you get at the end of doing infinite repetition.
Và khi ở Wheeler, bạn không thể rời Wheeler. Thì đột nhiên, trạng thái ban đầu sẽ quyết định phân phối dừng bạn nhận được sau khi lặp vô hạn lần.
And when you solve the linear system of equations corresponding to this kind of transition model, you will find that it has two solutions instead of one. It could be more.
Và khi giải hệ phương trình tuyến tính tương ứng với kiểu mô hình chuyển này, bạn sẽ thấy nó có hai nghiệm thay vì một. Có thể còn nhiều hơn.
It could be that maybe if you're dropped in Soda Hall, if you're on the fourth floor, you always end up staying on the fourth floor. You can't exit.
Có thể là nếu bạn được thả vào Soda Hall, nếu bạn ở tầng bốn, bạn luôn ở lại tầng bốn. Bạn không thể ra.
And same for 1, 2, 3, 5, 6, and 7.
Và tương tự với các tầng 1, 2, 3, 5, 6 và 7.
And if that were the case, then you'd have seven stationary distributions in Soda Hall, which you hit depending on where you started, and then one for Wheeler.
Và nếu đúng vậy, thì bạn sẽ có bảy phân phối dừng trong Soda Hall, và bạn đạt tới cái nào tùy vào nơi bạn bắt đầu, và một phân phối nữa cho Wheeler.
So if you keep things separated like that — essentially, if there's 0 transition probabilities between certain regions of the state space, you can end up with multiple stationary distributions.
Vậy nếu ta giữ các phần tách biệt như thế này... về cơ bản, nếu xác suất chuyển bằng 0 giữa một số vùng của không gian trạng thái, thì ta có thể có nhiều phân phối dừng.
But once you introduce a non-zero probability of transitioning between any pair of states, then typically we end up with a single solution. There is another funny case.
Nhưng khi ta đưa vào xác suất khác 0 để chuyển giữa bất kỳ cặp trạng thái nào, thì thường ta chỉ có một nghiệm duy nhất. Còn một trường hợp kỳ lạ nữa.
And these things are not too important for one idea.
Những chuyện này không quá quan trọng.
But just because [INAUDIBLE] has another funny cases where let's say, you have a system where maybe you could either be in front of the classroom or you could be sitting in a chair in the classroom.
Nhưng cứ nói thêm, có một trường hợp kỳ lạ khác, giả sử bạn có một hệ thống mà bạn có thể đứng trước lớp hoặc ngồi trên ghế trong lớp.
And your transition model is, at the next time, if you're sitting, you're in front. And if you're in front, you're sitting. They always go back and forth.
Và mô hình chuyển của bạn là, ở thời điểm kế tiếp, nếu đang ngồi thì bạn lên đứng trước lớp. Còn nếu đang đứng trước lớp thì bạn ngồi xuống. Chúng luôn đổi qua đổi lại.
Then you will not hit a stationary distribution, either. Because the dynamics are such that you always swap. So if you start here, you'll end up there. If you start there, you'll end up here.
Thì bạn cũng sẽ không đạt được phân phối dừng. tùy bạn bắt đầu ở đâu. Vì động học là lúc nào cũng đổi chỗ. Nếu bắt đầu ở đây, bạn sẽ kết thúc ở kia. Nếu bắt đầu ở kia, bạn sẽ kết thúc ở đây.
And so you don't get this kind of convergence. And so whenever these special cases happen is because there's a lot of 0's in the transitions between states.
Nên ta không có sự hội tụ kiểu này. Và những trường hợp đặc biệt này xảy ra là do có nhiều số 0 trong các xác suất chuyển giữa các trạng thái.
And so things don't get to naturally diffuse. Once there's some natural diffusion, then you get a single stationary distribution.
Nên mọi thứ không thể khuếch tán tự nhiên. Khi đã có sự khuếch tán tự nhiên, thì ta có một phân phối dừng duy nhất.
Any other questions?
Còn câu hỏi nào khác không?
OK. Let's think about where these Markov models might have already helped you in your life. Who here has used Google before? Who has not used Google before?
Được. Hãy nghĩ xem các mô hình Markov này có thể đã giúp bạn trong cuộc sống như thế nào. Ai ở đây đã từng dùng Google? Ai chưa từng dùng Google?
Anybody? Curious. Everybody has used Google before. OK.
Có ai không? Lạ nhỉ. Ai cũng đã dùng Google rồi. Được.
That's cool. So you guys are so young. You probably don't remember the time — but you were not alive — before Google existed. I was alive before Google existed.
Hay đấy. Các bạn còn trẻ quá. Có lẽ các bạn không nhớ, vì lúc đó các bạn chưa ra đời, cái thời trước khi có Google. Tôi thì đã sống trước khi có Google.
Google came into existence in '98. And before Google existed, it was very hard to find anything on the internet. And people used to bookmark things. Because it was so hard to find something.
Google ra đời năm 1998. Và trước khi có Google, rất khó tìm được thứ gì trên internet. Người ta hay đánh dấu trang. Vì tìm một thứ gì đó quá khó.
And so there were some search engines. But they didn't work all that well. And then you might have to scroll down to the 100th option they returned. And then, definitely, you're bookmarking.
Có một số công cụ tìm kiếm. Nhưng chúng không hoạt động tốt lắm. Bạn có thể phải cuộn xuống đến kết quả thứ 100 mà chúng trả về. Và chắc chắn là bạn sẽ đánh dấu trang.
So you don't want to do that again. Google really changed that. What was the key idea that they came up with at the time? The idea of page rank.
Để khỏi phải làm lại lần nữa. Google đã thay đổi hoàn toàn điều đó. Ý tưởng then chốt họ đưa ra lúc đó là gì? Ý tưởng page rank.
So page rank is a number assigned to each node in the web graph. So for every website, there is a rank number. And so Google came up with a rank number for every website.
Page rank là một con số gán cho mỗi nút trong đồ thị web. Tức là mỗi trang web đều có một số xếp hạng. Google đã nghĩ ra số xếp hạng cho mọi trang web.
And so when you were to search something, in previous search engines, you would search. And it would then either just return websites that have matching words, but not know which websites are more interesting.
Vậy khi bạn tìm kiếm thứ gì đó, ở các công cụ tìm kiếm trước đây, bạn tìm kiếm. Và nó hoặc chỉ trả về các trang có từ khớp, nhưng không biết trang nào thú vị hơn.
Or somebody would manually curate and say, I think this website is more important than this website. So if there's multiple websites with the correct word, let's show this one over that one.
Hoặc có người tự tay chọn lọc và nói, tôi nghĩ trang này quan trọng hơn trang kia. Nên nếu có nhiều trang chứa đúng từ đó, thì hiện trang này trước trang kia.
So we do a manual page rank, which is really hard to do. A lot of work. Very expensive to hire people to do this. They have the constant crawl the internet.
Tức là xếp hạng thủ công, việc này rất khó làm. Tốn rất nhiều công sức. Thuê người làm việc này rất đắt. Họ phải liên tục duyệt khắp internet.
Google came up with a way for a computer to just crawl the internet and assign the page ranks automatically. What they said is, the computer will start anywhere on the internet, at random.
Google nghĩ ra cách để máy tính tự duyệt internet và gán thứ hạng trang một cách tự động. Họ nói rằng máy tính sẽ bắt đầu ở bất kỳ đâu trên internet, một cách ngẫu nhiên.
And then when you're on a page with a bunch of out links, you click one of them at random. You follow that one. And then you repeat this process.
Rồi khi bạn ở một trang có nhiều liên kết đi ra, bạn bấm ngẫu nhiên vào một liên kết. Bạn đi theo liên kết đó. Rồi lặp lại quá trình này.
And as you repeat this, you're actually following a Markov model. There is a distribution over next states, given current state, where state is the page that you're on.
Và khi lặp lại, thực ra bạn đang đi theo một mô hình Markov. Có một phân phối trên trạng thái kế tiếp, cho trước trạng thái hiện tại, với trạng thái là trang bạn đang ở.
And the next state would be one of the states that you can go to from that state.
Và trạng thái kế tiếp sẽ là một trong các trạng thái mà bạn có thể đi tới từ trạng thái đó.
And there's a probability of getting reset, which actually helps with making sure there is a nice stationary distribution so you don't have weird zero probabilities in certain states and so forth.
Và có một xác suất bị đặt lại, điều này giúp đảm bảo có phân phối dừng tốt, để không có các xác suất bằng 0 kỳ quặc ở một số trạng thái, v.v.
So probability of being reset uniformly. But most of the time, we just transition to an outlink page. OK. So let's say you do that.
Tức là xác suất bị đặt lại đồng đều. Nhưng phần lớn thời gian, ta chỉ chuyển sang một trang liên kết đi ra. Được. Giả sử bạn làm như vậy.
And you follow this process. You look at the stationary distribution. Let's say you were to compute that. And that's exactly what Google did.
Và bạn đi theo quá trình này. Bạn xem xét phân phối dừng. Giả sử bạn tính nó. Và đó chính xác là điều Google đã làm.
They compute the stationary distribution. Then which pages will have a high probability to be on at time equals infinity? It's pages to which a lot of other pages link.
Họ tính phân phối dừng. Vậy những trang nào sẽ có xác suất cao được ghé tới ở thời điểm bằng vô cùng? Đó là những trang có nhiều trang khác liên kết tới.
But not just pages through which a lot of other pages link, also if a lot of pages link to a page that, in turn, links to you, that's also good for you.
Nhưng không chỉ vậy, mà còn nếu nhiều trang liên kết tới một trang, và trang đó lại liên kết tới bạn, thì điều đó cũng tốt cho bạn.
Some subtleties there. It might encourage you to not have any outlinks. So the random navigator gets stuck on your page.
Có vài điểm tinh tế ở đây. Nó có thể khuyến khích bạn không để liên kết đi ra nào. Để người duyệt ngẫu nhiên bị kẹt ở trang của bạn.
And there's fixes for that to make sure you never just stay on a page. But that's what they did. They computed a stationary distribution of this random web surfer Markov model.
Và có các cách sửa để đảm bảo không ai cứ ở mãi trên một trang. Nhưng đó là những gì họ đã làm. Họ tính phân phối dừng của mô hình Markov người lướt web ngẫu nhiên này.
And [INAUDIBLE] distribution was then used to rank. So you would search, type in maybe two words. It would retrieve all the pages that have those words on them.
Và phân phối đó sau đó được dùng để xếp hạng. Bạn tìm kiếm, gõ vào có thể là hai từ. Nó sẽ lấy ra tất cả các trang chứa những từ đó.
And among those, they showed them in order of page rank. That's Google 1.0. That was so much better than anything else that everybody switched over to using Google rather than the other ones.
Và trong số đó, nó hiển thị theo thứ tự page rank. Đó là Google 1.0. Nó tốt hơn hẳn mọi thứ khác đến mức ai cũng chuyển sang dùng Google thay vì các công cụ kia.
And then the next thing happened, of course, is everybody uses it. But initially, you still had to click, maybe, on result number five or a result number seven.
Rồi điều tiếp theo xảy ra, tất nhiên, là ai cũng dùng nó. Nhưng ban đầu, bạn vẫn phải bấm vào, chẳng hạn, kết quả thứ năm hoặc kết quả thứ bảy.
They log that click stream data. They machine learn on top of their page rank, whatever else matters for you to select a particular page. And at that point, it's hard to catch up.
Họ ghi lại dữ liệu click stream đó. Họ dùng machine learning bên trên page rank để học xem còn yếu tố nào khác khiến bạn chọn một trang cụ thể. Và đến lúc đó thì rất khó đuổi kịp.
Because if you were to build Google '98, it won't be that great as Google today. And so you won't get the users.
Vì nếu bạn xây một Google '98, nó sẽ không tốt bằng Google ngày nay. Nên bạn sẽ không có người dùng.
And so you wont get the ability to update how it ranks pages based on what users have done. But that was the foundation.
Và bạn sẽ không thể cập nhật cách xếp hạng trang dựa trên những gì người dùng đã làm. Nhưng đó là nền tảng.
And it was a lot better than anything people were able to do before.
Và nó tốt hơn nhiều so với bất cứ thứ gì người ta làm được trước đó.
It might still be the best you can do of starting from scratch and having no user data of what users prefer. Any questions about this?
Có thể đó vẫn là cách tốt nhất khi bắt đầu từ con số không và không có dữ liệu người dùng về sở thích của họ. Có câu hỏi nào về phần này không?
You actually have seen a Markov model in one other place, already, too, in 188, which is Gibbs sampling. The star here means that this is something a little advanced.
Thật ra các em đã thấy một mô hình Markov ở một chỗ khác rồi, trong CS 188, đó là Gibbs sampling. Dấu sao ở đây nghĩa là phần này hơi nâng cao.
And we don't expect you to necessarily fully follow along with what's happening here. But it's good to be aware of. And probably several of you will understand what's happening.
Và chúng tôi không đòi hỏi các em phải theo kịp hoàn toàn những gì đang diễn ra ở đây. Nhưng nên biết đến nó. Và chắc cũng có vài em sẽ hiểu.
So let's say you do Gibbs sampling. What was Gibbs sampling? It's this process where you say, I have a Bayes net.
Giả sử bạn chạy Gibbs sampling. Gibbs sampling là gì? Đó là quá trình mà bạn nói: tôi có một mạng Bayes.
I have a bunch of variables that are evidence variables — e1 through em. I have a bunch of query variables — x1 through xm.
Tôi có một số biến là biến bằng chứng, e1 đến em. Tôi có một số biến truy vấn, x1 đến xm.
And I want to infer distribution over the x variables, given the evidence variables. And let's say your Bayes net is big.
Và tôi muốn suy luận phân phối của các biến x, khi biết các biến bằng chứng. Và giả sử mạng Bayes của bạn lớn.
And variable elimination doesn't work, because you would need to generate a factor that's so big that you can't represent it on your computer. And it would take too long.
Và khử biến không dùng được, vì bạn sẽ phải tạo ra một factor lớn đến mức máy tính không biểu diễn nổi . Và sẽ mất quá nhiều thời gian.
OK. You might run a sampling algorithm. Gibbs sampling is one of the most popular ones.
Được. Bạn có thể chạy một thuật toán lấy mẫu. Gibbs sampling là một trong những thuật toán phổ biến nhất.
In Gibbs sampling, you take a random instantiation of those x variables, then randomly pick one of them and re-sample it conditioned on all the other variables.
Trong Gibbs sampling, bạn lấy một phép gán ngẫu nhiên cho các biến x, rồi chọn ngẫu nhiên một biến và lấy mẫu lại nó với điều kiện là tất cả các biến còn lại.
And sampling one variable in a Bayes net conditioned on all the others is actually a very efficient operation. So you do that operation.
Và lấy mẫu một biến trong mạng Bayes với điều kiện các biến khác thực ra là một thao tác rất hiệu quả. Vậy bạn thực hiện thao tác đó.
And then you randomly pick another variable, re-sample the condition on all the others. Repeat, repeat, repeat.
Rồi chọn ngẫu nhiên một biến khác, lấy mẫu lại với điều kiện tất cả các biến còn lại. Lặp đi lặp lại.
And it turns out, if you keep doing this, the distribution over assignments of variables will converge to a stationary distribution.
Và hóa ra, nếu cứ tiếp tục làm vậy, phân phối trên các phép gán biến sẽ hội tụ về một phân phối dừng.
So just like in the weather Markov model, it was always either sunny or rainy. That was never at stake. It was either one or the other. It was never a combination.
Giống như mô hình Markov thời tiết, luôn là nắng hoặc mưa. Điều đó không bao giờ thay đổi. Hoặc là cái này hoặc là cái kia. Không bao giờ là sự pha trộn.
But the stationary distribution put 75% on sun, 25% on rain. Same thing will happen here. At any step in your process, all these variables have been assigned.
Nhưng phân phối dừng dồn 75% cho nắng, 25% cho mưa. Ở đây cũng vậy. Ở bất kỳ bước nào, tất cả các biến này đều đã được gán giá trị.
Maybe it's plus x1, negative x2, plus x3, plus x4, negative x5, plus x6.
Có thể là cộng x1, trừ x2, cộng x3, cộng x4, trừ x5, cộng x6.
But the distribution of what you end up with ends up being a stationary solution that matches the correct posterior distribution of — oh, not this one — this one here.
Nhưng phân phối của kết quả cuối cùng sẽ là một nghiệm dừng khớp với phân phối hậu nghiệm đúng của... ồ, không phải cái này... cái này đây.
This conditional distribution is the stationary distribution of that process. Now, when you run this by sampling, you only get one sample of that distribution after you run infinitely long.
Phân phối có điều kiện này chính là phân phối dừng của quá trình đó. Giờ, khi chạy bằng lấy mẫu, bạn chỉ được một mẫu của phân phối đó sau khi chạy vô hạn lâu.
Then you repeat the process. You re-initialize everything, run the process again, get a second sample, re-initialize, run it again, get a third sample, and so forth.
Rồi bạn lặp lại quá trình. Khởi tạo lại mọi thứ, chạy lại để được mẫu thứ hai, khởi tạo lại, chạy tiếp, được mẫu thứ ba, và cứ thế.
And then the combination of samples together will reflect a stationary distribution, which you can then use to make some inferences from.
Rồi tập hợp các mẫu lại sẽ phản ánh phân phối dừng, từ đó bạn có thể thực hiện suy luận.
So this star also means that — it's not expected just from this slide that you understand how the proof would work, but just want you to know that this is out there.
Dấu sao này cũng có nghĩa là... chỉ từ slide này, các em chưa cần hiểu chứng minh hoạt động thế nào, chỉ cần biết là có điều này.
Any questions about Markov models?
Có câu hỏi nào về mô hình Markov không?
The thing about Markov models is that in some sense, yes, they have some applications, but they don't really have that many applications. They have a roughly trillion dollar application, which is pretty good.
Vấn đề của mô hình Markov là, theo một nghĩa nào đó, đúng là chúng có vài ứng dụng, nhưng thật ra không có nhiều ứng dụng lắm. Chúng có một ứng dụng trị giá khoảng một nghìn tỷ đô la, như vậy là khá ổn.
But how about more applications? Typically, you need more than just a Markov model. You need something called a hidden Markov model. So let's go back to this situation here.
Nhưng làm sao có thêm ứng dụng? Thường thì bạn cần nhiều hơn một mô hình Markov. Bạn cần một thứ gọi là mô hình Markov ẩn. Vậy hãy quay lại tình huống này.
We watched me play this at the beginning of lecture, and honestly, it was pretty hard to play.
Ở đầu buổi học, chúng ta đã xem tôi chơi trò này, và thành thật mà nói, nó khá khó chơi.
But in principle, we should fuse the information we get from the readings down here to get an estimate of where the ghosts are.
Nhưng về nguyên tắc, ta nên kết hợp thông tin từ các số đo ở dưới này để ước lượng vị trí của các con ma.
The ghosts' location is falling in Markov model, but we're also having measurements, and these measurements we don't have in the Markov model. Once we have a hidden Markov model, we'll also have measurements.
Vị trí của ma tuân theo mô hình Markov, nhưng ta cũng có các phép đo, và các phép đo này không có trong mô hình Markov. Khi có mô hình Markov ẩn, ta cũng sẽ có các phép đo.
So let's take a look at that. So in a hidden Markov model, there's still a sequence of states shown here, and that's not different. We've already covered that.
Vậy hãy xem thử. Trong mô hình Markov ẩn, vẫn có một chuỗi trạng thái như hình, và điều đó không khác. Ta đã học phần đó rồi.
That's the Markov model. But now in addition, we have observation — evidence variables at each time — for example, distance to each of the ghosts.
Đó là mô hình Markov. Nhưng giờ ta có thêm các biến quan sát, tức biến bằng chứng, ở mỗi thời điểm. ví dụ như khoảng cách tới từng con ma.
In a hidden Markov model, we don't get to observe the hidden state — x1, x2, x3, x4.
Trong mô hình Markov ẩn (HMM), chúng ta không quan sát được trạng thái ẩn: x1, x2, x3, x4.
But the hope is that by observing the evidence variables, we can somehow infer a posterior distribution over the hidden states that allows us to do something interesting.
Nhưng hy vọng là nhờ quan sát các biến bằng chứng, ta có thể suy ra phân phối hậu nghiệm trên các trạng thái ẩn, từ đó cho phép ta làm được những điều thú vị.
Again, this is just a Bayes net, right? If you look at this and you say, we only have four time steps so we cut it off right here, this is a Bayes net.
Một lần nữa, đây chỉ là một mạng Bayes, đúng không? Nếu nhìn vào đây và nói, ta chỉ có bốn bước thời gian nên cắt ngay ở đây, thì đây là một mạng Bayes.
You have observed, let's say, e1 through e4, you can now run variable elimination or anything else you'd like to run to infer distribution over x1, x2, x3, x4.
Giả sử bạn đã quan sát e1 đến e4, bạn có thể chạy khử biến hoặc bất kỳ phương pháp nào khác bạn muốn để suy ra phân phối trên x1, x2, x3, x4.
What we're going to look at is something that, over time, keeps track of that distribution that's a little specific to HMMs. But think about it after the fact.
Cái chúng ta sắp xem là một phương pháp theo dõi phân phối đó theo thời gian, và nó hơi đặc thù cho HMM. Nhưng hãy nghĩ lại sau đó.
You'll realize it's just variable elimination run from left to right.
Bạn sẽ nhận ra nó chỉ là khử biến chạy từ trái sang phải.
So here is an other example HMM. This is from the Russell and Norvig book.
Đây là một ví dụ HMM khác. Nó từ cuốn sách của Russell và Norvig.
They call it the weather HMM, but if you hear the story, you would probably call it the sad grad student HMM. The story goes as follows.
Họ gọi nó là HMM thời tiết, nhưng nếu nghe câu chuyện, bạn có lẽ sẽ gọi nó là HMM nghiên cứu sinh buồn. Câu chuyện như sau.
There's a grad student, but as it goes with very diligent grad students, they are just in the basement at all times. They don't come out of that basement.
Có một nghiên cứu sinh, và như các nghiên cứu sinh rất chăm chỉ khác, họ lúc nào cũng ở trong tầng hầm. Họ không ra khỏi tầng hầm đó.
But luck has it, every now and then Professor stops by and says hi to them. And sometimes, Professor has an umbrella, sometimes not.
Nhưng may thay, thỉnh thoảng giáo sư ghé qua chào họ. Và đôi khi giáo sư cầm ô, đôi khi không.
And that, for the grad student, is a way to extract information about whether today might be a sunny day or a rainy day, OK?
Và với nghiên cứu sinh, đó là cách để rút ra thông tin xem hôm nay có thể là ngày nắng hay ngày mưa, được chứ?
[CHUCKLING] I'm not saying this is realistic grad student life, but that's the story in the book. I hope it's not realistic.
[CƯỜI KHẼ] Tôi không nói đây là cuộc sống thực tế của nghiên cứu sinh, nhưng đó là câu chuyện trong sách. Tôi hy vọng nó không thực tế.
So that's what's going on here. Grad student really wants to know about the weather outside. Doesn't get to look at it, but gets to see the professor carrying an umbrella or not.
Vậy đó là những gì đang diễn ra ở đây. Nghiên cứu sinh rất muốn biết thời tiết bên ngoài. Không được nhìn ra ngoài, nhưng thấy giáo sư có cầm ô hay không.
Now, there's multiple distributions involved. There's initial state distribution — initially sunny or rainy. There's a distribution of for next day, like we saw in the Markov model, the transition model here.
Giờ có nhiều phân phối liên quan. Có phân phối trạng thái ban đầu: lúc đầu nắng hay mưa. Có phân phối cho ngày tiếp theo, như ta thấy trong mô hình Markov, đó là mô hình chuyển.
And then there's a distribution for evidence given current state, OK? So let's put some numbers in. The transition model we've already seen before. Actually, it's slightly different here, slightly simplified.
Và có phân phối của bằng chứng cho trước trạng thái hiện tại, được chứ? Giờ ta điền vài con số. Mô hình chuyển thì ta đã thấy trước đây. Thực ra ở đây hơi khác một chút, được đơn giản hóa một chút.
It's made symmetric. Probability of rain the next day given rain on a previous day is 0.7, and same deal the other way around.
Nó được làm đối xứng. Xác suất mưa ngày hôm sau khi hôm trước có mưa là 0.7, và chiều ngược lại cũng vậy.
So it's 70% chance things stay the same and 30% chance things switch up. Then turns out, 90% of the time when it rains, Professor has an umbrella.
Tức là 70% khả năng giữ nguyên và 30% khả năng đổi khác. Rồi, hóa ra 90% số lần trời mưa, giáo sư có cầm ô.
And then, when it doesn't rain, Professor still has an umbrella 20% of the time. So you can't just look at the umbrella or not to know whether it's been raining.
Còn khi trời không mưa, giáo sư vẫn cầm ô 20% số lần. Vậy bạn không thể chỉ nhìn có ô hay không để biết trời có mưa hay không.
You need to do some probabilistic calculus to get a posterior over when it might be raining or not outside.
Bạn cần tính toán xác suất một chút để có phân phối hậu nghiệm về việc bên ngoài có thể đang mưa hay không.
Not sure if it matters to know if you're always in the basement, but it's the calculation we're going to do.
Không chắc có quan trọng không nếu lúc nào cũng ở trong tầng hầm, nhưng đó là phép tính ta sẽ làm.
OK. Here's another example — Ghostbusters. So this is a smaller version of the grid that we looked at — just three by three, uniform distribution initially.
OK. Đây là một ví dụ khác: Ghostbusters. Đây là phiên bản nhỏ hơn của lưới ta đã xem: chỉ 3 x 3, ban đầu là phân phối đều. ngay từ đầu.
We have a transition model where they usually move clockwise in this grid, but might also veer randomly off that.
Ta có mô hình chuyển trong đó chúng thường di chuyển theo chiều kim đồng hồ trong lưới, nhưng cũng có thể lệch ngẫu nhiên khỏi hướng đó.
And then there is an observation model where we have sensors that you also covered in last week's lecture — oh, no, this Tuesdya's lecture on value of perfect information — where the sensor could take on different colors depending on how far away the ghost is from where you made your measurement.
Và có mô hình quan sát với các cảm biến mà bạn cũng đã học ở bài tuần trước, à không, bài thứ Ba này, về giá trị của thông tin hoàn hảo, trong đó cảm biến có thể hiện các màu khác nhau tùy theo con ma cách vị trí bạn đo bao xa.
And that's our observation given state conditional distribution. OK, so let's take a look at the corresponding demo here.
Và đó là phân phối có điều kiện của quan sát cho trước trạng thái. OK, giờ xem bản demo tương ứng.
OK, so we'll let time pass.
OK, ta cho thời gian trôi.
Don't see anything happen because we hit the stationary distribution of the Markov model, but now we're going to consider it as an HMM. So we'll get a measurement this time.
Không thấy gì xảy ra vì ta đã đạt phân phối dừng của mô hình Markov, nhưng giờ ta sẽ xem nó như một HMM. Lần này ta nhận một phép đo.
This will change the distribution. Then time passes again. We'll get another measurement. We'll change distribution.
Nó sẽ làm thay đổi phân phối. Rồi thời gian lại trôi. Ta nhận một phép đo nữa. Ta thay đổi phân phối.
Time passes again. We'll get another measurement, maybe here, get another distribution, and so forth.
Thời gian lại trôi. Ta nhận thêm một phép đo, có thể ở đây, được một phân phối khác, và cứ thế.
So you have an alternation between time passes, which tends to diffuse where the ghost probability mass is, and then a measurement which tends to help us concentrate where the ghosts might be.
Vậy có sự xen kẽ giữa thời gian trôi, làm khối xác suất của con ma có xu hướng lan ra, và phép đo, giúp ta tập trung lại vị trí con ma có thể ở.
And that's the dynamics of an HMM.
Và đó là động lực của một HMM.
There's this alternation between time passing, a measurement, time passing, a measurement, and every step along that process, the distribution gets updated, and hopefully, gives us more and more concentrated information on where the ghost might be.
Có sự xen kẽ giữa thời gian trôi, phép đo, thời gian trôi, phép đo, và ở mỗi bước của quá trình đó, phân phối được cập nhật, và hy vọng sẽ cho ta thông tin ngày càng tập trung hơn về vị trí con ma có thể ở.
OK, so that's the HMM process in action.
OK, đó là quá trình HMM đang hoạt động.
Let's think about the independence assumptions we make in this model.
Giờ hãy nghĩ về các giả định độc lập ta đưa ra trong mô hình này.
So the reason we talked about things like deseparation is that when we look at a graph like this, we can just read off, what is it that we're assuming by choosing this Bayes net graph?
Lý do ta nói về d-separation là khi nhìn vào một đồ thị như thế này, ta có thể đọc ngay ra ta đang giả định điều gì khi chọn đồ thị mạng Bayes này.
So what is it that we're assuming? Well, look at the hidden process. The hidden process up here — x1 through x4. What can we say about that?
Vậy ta đang giả định điều gì? Hãy nhìn vào quá trình ẩn. Quá trình ẩn ở phía trên này, x1 đến x4. Ta có thể nói gì về phần này?
It's actually similar to what we had for the Markov model.
Nó thực ra giống với mô hình Markov mà ta đã có.
It's still the case that if you know the state, let's say, at time three, knowing anything about the past before time three does not tell you anything about the future past time three.
Vẫn đúng là nếu bạn biết trạng thái, giả sử ở thời điểm ba, thì biết bất cứ điều gì về quá khứ trước thời điểm ba cũng không cho bạn biết điều gì về tương lai sau thời điểm ba.
So knowing a state at a given time separates past from future. How about if we have observations?
Vậy biết trạng thái tại một thời điểm tách quá khứ khỏi tương lai. Còn nếu ta có các quan sát thì sao?
What this model is saying is that if we know x3, the evidence we expect to observe, the distribution over evidence, is independent of anything else we could find out once we know x3.
Mô hình này nói rằng nếu ta biết x3, thì bằng chứng mà ta kỳ vọng quan sát được, tức phân phối của bằng chứng, độc lập với mọi thứ khác mà ta có thể biết thêm, một khi đã biết x3.
It's just x3 directly influences our measurement, and nothing else has any influence anymore. How about this question at the bottom here? Does this mean evidence variables are guaranteed to be independent?
Chỉ có x3 ảnh hưởng trực tiếp đến phép đo của ta, và không còn gì khác ảnh hưởng nữa. Còn câu hỏi ở dưới này thì sao? Điều này có nghĩa là các biến bằng chứng chắc chắn độc lập với nhau không?
Who thinks they're guaranteed to be independent? Who thinks they're not guaranteed to be independent? Let's see. Very few hands are going up.
Ai nghĩ chúng chắc chắn độc lập? Ai nghĩ chúng không chắc chắn độc lập? Để xem nào. Rất ít người giơ tay.
This is a question you should be able to answer. So either it's just so simple you feel offended you're even asked, or you need to do a little bit of review of this material.
Đây là câu hỏi các bạn phải trả lời được. Hoặc là nó quá đơn giản đến mức bạn thấy bị xúc phạm khi được hỏi, hoặc là bạn cần ôn lại phần này một chút.
I'm not going to ask you which one it is. I'll just answer the question. So are these evidence variables guaranteed to be independent? What's the question there?
Tôi sẽ không hỏi là trường hợp nào. Tôi sẽ trả lời luôn. Vậy các biến bằng chứng này có chắc chắn độc lập không? Câu hỏi ở đây là gì?
Well, let's look at some evidence variables. For example, e1 and e4 — are they guaranteed to be independent? Let's see. What paths do we have?
Hãy xét một vài biến bằng chứng. Ví dụ e1 và e4, chúng có chắc chắn độc lập không? Để xem. Ta có những đường đi nào?
This is a path, and it's actually the only path. Is that an active path or an inactive path? Well, let's take a look.
Đây là một đường đi, và thực ra là đường duy nhất. Đó là đường hoạt động hay không hoạt động? Ta cùng xem.
The first triple here is active, second triple active, third triple active. All these triples are active because the first one is a common cause, and the next ones are causal chains.
Bộ ba đầu tiên hoạt động, bộ ba thứ hai hoạt động, bộ ba thứ ba hoạt động. Tất cả các bộ ba này đều hoạt động vì bộ đầu tiên là nguyên nhân chung, còn các bộ tiếp theo là chuỗi nhân quả.
And nothing is observed in-between because we said — already independent, but not conditional or anything. Are they just independent? So nothing's observed. So there is influence running, so indeed, we cannot claim this.
Và không có gì được quan sát ở giữa vì ta đã nói là độc lập thôi, chứ không có điều kiện gì cả. Chúng chỉ độc lập thôi à? Vậy là không có gì được quan sát. Nên có ảnh hưởng truyền qua, và do đó ta không thể khẳng định điều này.
So no. Answer is no. It changes, of course, if we were to observe, for example, x2. Then all of a sudden, we have independents here.
Vậy là không. Đáp án là không. Dĩ nhiên điều đó sẽ thay đổi nếu ta quan sát, ví dụ, x2. Thì đột nhiên ta có tính độc lập ở đây.
We have e1 independent of e4 given x2. So those are the assumptions we're making.
Ta có e1 độc lập với e4 khi biết x2. Đó là những giả định mà ta đưa ra.
If you're not happy with those assumptions, you don't think they capture how the world works, well, then you should modify your model because otherwise, the conclusions from the model are not going to be very precise for what you're trying to do.
Nếu bạn không hài lòng với các giả định đó, bạn thấy chúng không phản ánh cách thế giới vận hành, thì bạn nên sửa mô hình, vì nếu không, các kết luận từ mô hình sẽ không chính xác lắm cho việc bạn đang muốn làm.
Let's see.
Được rồi.
Let's take a short break here, and then, let's do mini-contest results and do the remainder of HMMs.
Ta nghỉ giải lao một chút ở đây, rồi xem kết quả mini-contest và làm phần còn lại của HMM.
STUDENT
Do you have office hours next week or is that — PROFESSOR: OK, let's restart.
Tuần sau thầy có giờ làm việc không ạ, hay là — GIÁO SƯ: Được rồi, ta bắt đầu lại.
Let's look at the mini-contest 2 results. How did the game work? It was a game. Each side controls multiple agents.
Hãy xem kết quả mini-contest 2. Trò chơi diễn ra thế nào? Đó là một trò chơi. Mỗi bên điều khiển nhiều tác tử.
Each agent is a ghost in their own territory, which they can then defend, and a Pac-Man on the other side, where it can go collect food pellets, but you only get points when you bring them back.
Mỗi tác tử là một con ma trong lãnh thổ của mình, và có thể phòng thủ, còn ở phía bên kia là một Pac-Man, có thể đi thu thập các viên thức ăn, nhưng bạn chỉ được điểm khi mang chúng về.
If you get attacked by the opponent's ghost and eaten, then the food pellets re-spawn around you. So you win by returning all but two food dots.
Nếu bạn bị ma của đối phương tấn công và ăn mất, thì các viên thức ăn sẽ xuất hiện lại quanh bạn. Bạn thắng khi mang về tất cả trừ hai viên thức ăn.
Well, you can — all but two, or it's fine if you return more and return all of them, but that's the minimum. All but two should be returned to win, or after 1,200 steps.
Bạn có thể mang về nhiều hơn, thậm chí tất cả cũng được, nhưng đó là mức tối thiểu. Chỉ cần mang về tất cả trừ hai viên là thắng. Hoặc sau 1.200 bước.
If nobody has won yet, according to this rule, the game ends, and we just look at who has the most food pellets returned so far — so the running score.
Nếu chưa ai thắng theo luật này, trò chơi kết thúc, và ta xem ai mang về được nhiều viên thức ăn nhất, tức là điểm hiện tại.
Many different layouts — so it's not about solving one particular scenario. The layouts are different in different games. How are the rankings calculated?
Có nhiều bố cục khác nhau, nên không phải chỉ giải một tình huống cụ thể. Mỗi ván có bố cục khác nhau. Bảng xếp hạng được tính thế nào?
For each of the four staff agents on the six different maps, three games per map are played.
Với mỗi tác tử trong bốn tác tử của ban giảng huấn trên sáu bản đồ khác nhau, mỗi bản đồ chơi ba ván.
And for each map, the score of the three games is averaged, and then a total score is the sum of all these average scores.
Với mỗi bản đồ, điểm của ba ván được lấy trung bình, rồi tổng điểm là tổng của tất cả các điểm trung bình này.
There's also some extra credit involved.
Cũng có một số điểm cộng.
On project 2, if you are first place in the ranking, you get two extra credit points; second and third place, 1.5; fourth to 10, 1 point; and 0.5 points for if you win at least 51% of the time against a baseline team we provided [? similarly ?] for the three staff agents.
Ở project 2, nếu bạn xếp hạng nhất, bạn được hai điểm cộng; hạng hai và ba được 1,5; hạng tư đến 10 được 1 điểm; và 0,5 điểm nếu bạn thắng ít nhất 51% số ván trước đội cơ sở mà chúng tôi cung cấp, [? tương tự ?] với ba tác tử của ban giảng huấn.
OK, let's look at what happened. 35 participating teams — many interesting team names, which were always appreciated. Let's see.
Được rồi, hãy xem chuyện gì đã xảy ra. Có 35 đội tham gia, nhiều tên đội rất thú vị, và chúng tôi luôn rất thích điều đó. Để xem nào.
"Team No Bug," "Get Wrecked," "My Stupid Code Just Cannot Work," "Please Don't Eat Me."
"Team No Bug", "Get Wrecked", "My Stupid Code Just Cannot Work", "Please Don't Eat Me".
Then I'm going to read this as — [LAUGHTER] "Please Don't Read Me"?
Còn cái này thì tôi sẽ đọc là — [CƯỜI] "Please Don't Read Me"?
I think it has a meaning. I looked it up yesterday, and I'm pretty sure it was not offensive and it's OK to show in class, but I don't remember what it is.
Tôi nghĩ nó có một ý nghĩa. Hôm qua tôi đã tra, và tôi khá chắc là nó không xúc phạm và chiếu trên lớp được, nhưng tôi không nhớ nó là gì.
And then, actually, three dots isn't indicating there were more team names, but actually, one of the team names was just three dots.
Còn ba dấu chấm này không có nghĩa là còn thêm tên đội khác, mà thực ra có một đội đặt tên chỉ là ba dấu chấm.
Results — in 10th place, we had Wilson Wu, "I Would Prefer Not To," with 25 points. In ninth place, Victor Chang, "War of Greed."
Kết quả: hạng 10 là Wilson Wu, "I Would Prefer Not To", với 25 điểm. Hạng chín, Victor Chang, "War of Greed".
In eighth place, [INAUDIBLE] and [INAUDIBLE] with Ruji. In seventh place, [INAUDIBLE] with "Team No Bug." In sixth place, Chang [INAUDIBLE],, "Find A Way."
Hạng tám, [KHÔNG NGHE RÕ] và [KHÔNG NGHE RÕ] với Ruji. Hạng bảy, [KHÔNG NGHE RÕ] với "Team No Bug". Hạng sáu, Chang [KHÔNG NGHE RÕ], với "Find A Way."
Fifth place, Johannes [INAUDIBLE] with "A Unique Leaderboard Name." Fourth place, Ariel Hirschberg with "Waka x3."
Hạng năm, Johannes [KHÔNG NGHE RÕ] với "A Unique Leaderboard Name." Hạng tư, Ariel Hirschberg với "Waka x3."
Congratulations, everyone in the top 10 listed so far.
Chúc mừng tất cả các bạn trong top 10 vừa được xướng tên.
[APPLAUSE] Then in third place, we have "Don't Forget — Register to Vote."
[VỖ TAY] Rồi, hạng ba là "Don't Forget — Register to Vote."
If you want to get any message across in this class, your team name is your opportunity. The sole team member is Sean Liu. Who is Sean — is Sean here?
Nếu muốn gửi một thông điệp nào đó trong lớp này, thì tên đội chính là cơ hội của các bạn. Thành viên duy nhất của đội là Sean Liu. Sean đâu nhỉ, Sean có ở đây không?
Can you raise your hand if you're here, Sean? Oh, you have two people. Oh. What's your name?
Sean, bạn có ở đây thì giơ tay lên nhé? Ồ, có hai người. Ồ. Bạn tên gì?
STUDENT
Hm.
Hm.
PROFESSOR
Adam?
Adam à?
STUDENT
Hm.
Hm.
PROFESSOR
H-M. Hm. We'll see more Hm in one of the future lectures, actually. Hm and Sean, congratulations. So score of 99 — apologies for no Hm on this slide.
H-M. Hm. Thực ra chúng ta sẽ còn gặp Hm trong một bài giảng sau. Hm và Sean, chúc mừng hai bạn. Điểm là 99 — xin lỗi vì slide này không có tên Hm.
Somehow, clicking on [? great scope ?] did not show your name as a partner, so we might have to do some fixing so you get the extra credit points.
Không hiểu sao khi bấm vào [? great scope ?] thì tên bạn không hiện là đồng đội, nên chúng tôi có thể phải sửa lại để bạn nhận được điểm cộng.
Bot description — [? min/max ?] with the offensive agent looking at score — distance to ghost, distance to home, distance to pellets, number of pellets left, number of power pellets left, when the enemy is two away, encourage to go home.
Mô tả bot: [? min/max ?] với tác tử tấn công xét điểm số, khoảng cách tới ma, khoảng cách về nhà, khoảng cách tới các viên thức ăn, số viên còn lại, số viên năng lượng còn lại; khi kẻ địch cách hai bước, thì khuyến khích quay về nhà.
Otherwise, encourage to collect more food. So you can re-weight those features in different ways, depending on which situation you're in.
Còn không thì khuyến khích ăn thêm thức ăn. Vậy bạn có thể đặt lại trọng số các đặc trưng đó theo nhiều cách, tùy tình huống đang gặp.
The defensive agent is measuring distance to enemy Pac-Man and trying to get as close as possible. Then, the defensive agent plays a trick. It flaunts and dances near the border to lure you in.
Tác tử phòng thủ đo khoảng cách tới Pac-Man của địch và cố đến gần nhất có thể. Rồi tác tử phòng thủ dùng một mánh. Nó khoe mẽ và nhảy múa gần biên giới để dụ bạn vào.
So sometimes at the border, these things get stationary and don't move, but this agent will, well, dance and flaunt, whatever that means exactly, and you will come closer and be eaten.
Đôi khi ở biên giới, các tác tử đứng yên không di chuyển, nhưng tác tử này thì nhảy múa và khoe mẽ, dù chính xác là gì thì không rõ, và bạn sẽ lại gần rồi bị ăn.
This is what it looks like in action. So this is against one of the staff agents.
Đây là cách nó hoạt động thực tế. Đây là trận đấu với một tác tử của ban giảng huấn.
On the left in red is the third-place team, "Don't Forget — Register to Vote," working their way.
Bên trái màu đỏ là đội hạng ba, "Don't Forget — Register to Vote", đang tiến lên.
And on the right is the staff team, also trying to work their way, though maybe one of the ghosts is not working their way down much.
Bên phải là đội của ban giảng huấn, cũng đang cố tiến lên, dù có lẽ một con ma không đi xuống nhiều lắm.
So the score is still 0, even though food pellets have been eaten, because nobody has brought food pallets back yet.
Điểm vẫn là 0, dù đã ăn thức ăn, vì chưa ai mang thức ăn về cả.
So red is up by 2.
Đỏ đang hơn 2 điểm.
[CHUCKLING] So red is still up by 2.
[CƯỜI KHẼ] Đỏ vẫn hơn 2 điểm.
Oh, he didn't — lured in the staff agents and ate them.
Ồ, nó dụ các tác tử của ban giảng huấn vào rồi ăn họ.
[CHUCKLING] Time to go back, bring back a lot of food pellets.
[CƯỜI KHẼ] Đến lúc quay về, mang thật nhiều thức ăn về.
Score is 6 now.
Giờ điểm là 6.
Playing more games.
Chơi thêm vài ván.
Let's fast-forward this a little bit, if we can.
Tua nhanh một chút nhé, nếu được.
So Team Red wins this one. Let's move to the next won. Second place is YZY, [INAUDIBLE] and [INAUDIBLE].. Are [INAUDIBLE] and [INAUDIBLE] here?
Đội Đỏ thắng ván này. Sang đội tiếp theo. Hạng nhì là YZY, [KHÔNG NGHE RÕ] và [KHÔNG NGHE RÕ]. [KHÔNG NGHE RÕ] và [KHÔNG NGHE RÕ] có ở đây không?
Both here. Congratulations. [APPLAUSE] We're on a [? search — ?] I'll play this in parallel to explaining. If the closest ghost is near, alpha/beta is run for two turns.
Cả hai đều có mặt. Chúc mừng. [VỖ TAY] Chúng ta đang [? search — ?] tôi sẽ phát video song song với phần giải thích. Nếu con ma gần nhất ở gần, alpha/beta được chạy trong hai lượt.
If the closest ghost is not near — this is when you're an offensive agent — greedy tree search to just cover as many food pellets as quickly as possible.
Nếu con ma gần nhất không ở gần — đây là khi bạn là tác tử tấn công — thì dùng tìm kiếm cây tham lam để ăn càng nhiều viên thức ăn càng nhanh càng tốt.
Evaluation functions have a lot of sophisticated features, more than I could put on this slide.
Hàm đánh giá có rất nhiều đặc trưng phức tạp, nhiều hơn mức tôi có thể ghi trên slide này.
Also, pay attention to dead ends very specifically because of course, you don't want to get trapped, and then more emphasis on y-coordinate than x because y is often the way you can keep people blocked, whereas x doesn't play as big a role in that.
Ngoài ra, đặc biệt chú ý các ngõ cụt vì tất nhiên, bạn không muốn bị mắc kẹt, và nhấn mạnh tọa độ y hơn x vì y thường là hướng để chặn đối thủ, còn x thì không đóng vai trò lớn như vậy.
So decision and action — also beats staff agent. I'm going to move forward through this one to first place. First place is @_@, Phillip [INAUDIBLE] and [INAUDIBLE]..
Vậy quyết định và hành động — cũng đánh bại tác tử của ban giảng huấn. Tôi sẽ lướt qua đội này để đến hạng nhất. Hạng nhất là @_@, Phillip [KHÔNG NGHE RÕ] và [KHÔNG NGHE RÕ].
Are you here? Philip [INAUDIBLE], over there. Congratulations. [APPLAUSE] So let me play this one while we explain.
Các bạn có ở đây không? Philip [KHÔNG NGHE RÕ], ở đằng kia. Chúc mừng. [VỖ TAY] Tôi sẽ phát video này trong lúc giải thích.
If there are no opponents on their side, both agents are offensive. When opponents enter their side, one of the agents will turn defensive, often the closer agent.
Nếu không có đối thủ ở phía mình, cả hai tác tử đều tấn công. Khi đối thủ vào phía mình, một trong hai tác tử sẽ chuyển sang phòng thủ, thường là tác tử gần hơn.
The defensive agent works similar to the baseline defensive agent.
Tác tử phòng thủ hoạt động tương tự tác tử phòng thủ cơ sở.
During initialization, the dead ends in the map are found and blocks in the dead area assigned a danger coefficient, which is the number of steps required to escape.
Lúc khởi tạo, các ngõ cụt trên bản đồ được tìm ra và các ô trong vùng cụt được gán một hệ số nguy hiểm, là số bước cần để thoát ra.
This danger coefficient plays an important role in the evaluation function, and the offensive agent runs a min/max of depth 1. Let's this in action here.
Hệ số nguy hiểm này đóng vai trò quan trọng trong hàm đánh giá, và tác tử tấn công chạy minimax với độ sâu 1. Hãy xem nó hoạt động thế nào.
[APPLAUSE] Zero food pellets left on the other side.
[VỖ TAY] Không còn viên thức ăn nào ở phía bên kia.
So HMMs — this is the Bayes net model corresponding to it. What are some real HMM examples?
Còn HMM thì đây là mô hình mạng Bayes tương ứng. Một số ví dụ HMM thực tế là gì?
Well, speech recognition — the observed variables are the sequence of numbers corresponding to the pressure that you observe in the air coming at you, and the unobserved variables are the characters or the phonemes or the words, whichever version of transcription you're using.
Nhận dạng giọng nói: các biến quan sát được là chuỗi số tương ứng với áp suất mà bạn đo được trong không khí truyền tới, còn các biến không quan sát được là ký tự, âm vị hoặc từ, tùy cách phiên âm bạn dùng.
Machine translation — the observed evidence is words or characters or symbols in one language. The unobserved is characters, symbols, or words in the other language.
Dịch máy: bằng chứng quan sát được là các từ, ký tự hoặc ký hiệu trong một ngôn ngữ. Biến không quan sát được là các ký tự, ký hiệu, hoặc từ trong ngôn ngữ còn lại.
Robot tracking observations could be sensory readings, like laser rangefinder readings, and the unobserved is the state, the localization of the robot.
Với theo dõi robot, quan sát có thể là các số đo cảm biến, như số đo của máy đo khoảng cách laser, còn biến không quan sát được là trạng thái, tức vị trí định vị của robot.
Filter monitoring is the process of tracking the distribution over state given evidence.
Filter monitoring là quá trình theo dõi phân phối trên trạng thái khi có bằng chứng.
So keeping track of this belief state — that's why it's called belief state over state, which is a conditional of state at a time xt given all evidence up to time t.
Tức là ta theo dõi belief state này, gọi là belief state trên trạng thái, vì nó là phân phối có điều kiện của trạng thái tại thời điểm t, xt, cho trước mọi bằng chứng đến thời điểm t.
We will start with belief state of time. One, usually uniform — and then, as time passes or we get observations, we update the belief.
Ta bắt đầu với belief state ở thời điểm một, thường là phân phối đều, rồi khi thời gian trôi qua hoặc có quan sát mới, ta cập nhật belief.
The common [INAUDIBLE] is an example of an HMM that happens to use continuous variables, which we're not going to do, but was used in the Apollo project and critical to getting to the moon.
Bộ lọc Kalman là một ví dụ của HMM dùng biến liên tục, cái mà ta sẽ không học, nhưng nó được dùng trong dự án Apollo và rất quan trọng để lên được Mặt Trăng.
So what's an example of this in action for robot localization? This robot could be anywhere in this grid, so everything's equally gray.
Vậy ví dụ về định vị robot trong thực tế là gì? Robot này có thể ở bất kỳ đâu trong lưới này, nên mọi ô đều xám như nhau.
The observation model is that it senses to the top, the bottom, left, right. It senses whether there is a wall or not. It makes at most one error.
Mô hình quan sát là nó cảm nhận phía trên, dưới, trái, phải. Nó cảm nhận có tường hay không. Nó sai tối đa một lần.
So when it's there, it could have five different types of readings — the reading where there is no error, or the other four readings where you make one error in your four readings.
Vậy ở một ô, nó có thể có năm loại số đo: số đo không có lỗi, hoặc bốn số đo còn lại có một lỗi trong bốn hướng đo.
That also means that when you read something, you can count on it being an exact match to where you are.
Điều đó cũng có nghĩa là khi bạn đọc được một giá trị, bạn có thể tin nó khớp chính xác với vị trí của bạn.
So at time zero, we have a uniform distribution over wherever the robot could be. Then the robot will move. We know the action of the robot, so we can do a next state calculation.
Tại thời điểm không, ta có phân phối đều trên mọi vị trí robot có thể ở. Sau đó robot sẽ di chuyển. Ta biết hành động của robot, nên có thể tính trạng thái kế tiếp.
Actually, will this robot move? Yeah, it'll move. So we first do a sensor reading. We do a belief update based on the sensor reading.
Mà robot này có di chuyển không nhỉ? Có, nó sẽ di chuyển. Trước tiên ta đọc cảm biến. Ta cập nhật belief dựa trên số đo cảm biến.
We read wall, top, wall, bottom. This is now our posterior. The robot will move to the right. We'll have a transition model for that.
Ta đọc được tường trên, tường dưới. Đây giờ là posterior của ta. Robot sẽ di chuyển sang phải. Ta có mô hình chuyển cho việc đó.
It's not guaranteed to move one to the right, but with high probability, it will. Then we get another sensor reading. We see wall, top, wall, bottom.
Không chắc chắn nó sẽ đi đúng một ô sang phải, nhưng với xác suất cao thì có. Rồi ta có thêm một số đo cảm biến. Ta thấy tường trên, tường dưới.
We're showing it here, and that's because we know it's there because we're kind of looking from above and knowing how the world works. But the HMM itself doesn't know where the robot is.
Ta hiển thị nó ở đây, và đó là vì ta biết nó ở đó do ta đang nhìn từ trên xuống và biết thế giới vận hành ra sao. Nhưng bản thân HMM không biết robot ở đâu.
It has a distribution of where the robot might be. Then moves again, also does a sensory update and keeps repeating this. And then, when it's here, symmetry gets broken.
Nó chỉ có một phân phối về nơi robot có thể ở. Rồi nó lại di chuyển, lại cập nhật cảm biến và cứ lặp lại như vậy. Và khi đến đây, tính đối xứng bị phá vỡ.
It knows it's in the top hallway, not the bottom hallway — not for sure, but very likely — and knows its localization pretty well. OK, so what are the base cases?
Nó biết mình ở hành lang trên, không phải hành lang dưới, không chắc chắn hoàn toàn nhưng rất có khả năng, và định vị khá tốt. Vậy các trường hợp cơ sở là gì?
We either observe evidence, which is we want to then compute the posterior of x1 given the evidence e1. How do we do this? Well, this is the calculation.
Hoặc ta quan sát được bằng chứng, tức là ta muốn tính posterior của x1 cho trước bằng chứng e1. Làm thế nào? Đây là phép tính.
What's happening here? The conditional of x1 given e1 is, by definition, the joint of x1 and e1 divided by the probability of e1.
Chuyện gì đang diễn ra ở đây? Phân phối có điều kiện của x1 cho e1, theo định nghĩa, là phân phối đồng thời của x1 và e1 chia cho xác suất của e1.
Then we use this sign over here saying we're now going to get rid of this thing over here by using this sign.
Rồi ta dùng ký hiệu này ở đây để nói rằng ta sẽ bỏ cái thứ ở đây đi bằng ký hiệu này.
It's kind of weird, but it's just saying we're interested [INAUDIBLE] over x1. So our variable's x1. e1 is not a variable. Only x1 is the variable.
Hơi lạ, nhưng nó chỉ có nghĩa là ta quan tâm đến [KHÔNG NGHE RÕ] trên x1. Biến của ta là x1. e1 không phải là biến. Chỉ x1 là biến.
So anything that does not involve x1, we can just remove if it's just multiplied in. Now, here it's divided, and that's the same as multiply.
Nên bất cứ thứ gì không liên quan đến x1, ta có thể bỏ đi nếu nó chỉ là một thừa số nhân vào. Ở đây nó là phép chia, mà chia cũng như nhân.
We can just remove it say it's proportional to this. And then we can fill in the model and get this thing over here. What would be the result of this calculation?
Ta có thể bỏ nó đi và nói là tỉ lệ với cái này. Rồi ta điền mô hình vào và được biểu thức này. Kết quả của phép tính này sẽ là gì?
We would have a table for values of x1.
Ta sẽ có một bảng các giá trị của x1.
We would then have values that are proportional to x1 given e1, and maybe it would look something like this. x1 could be 0 or 1, and then proportional says 0.2 on this and 0.3 on this.
Rồi các giá trị tỉ lệ với x1 cho trước e1, có thể trông như thế này. x1 có thể là 0 hoặc 1, và tỉ lệ cho ta 0,2 ở giá trị này và 0,3 ở giá trị kia. Nếu muốn biết xác suất thật sự, bạn sẽ nói, à, đó mới chỉ là tỉ lệ.
If you want them to know the actual probabilities, you will say, oh, well, that's only proportional.
I now need to re-normalize, so it will be 0.2 over the sum of those and 0.3 over the sum of those again.
Giờ tôi cần chuẩn hóa lại, nên sẽ là 0,2 chia cho tổng của chúng và 0,3 chia cho tổng của chúng. Đó sẽ là xác suất thật sự.
That will be the actual probability. So that's what's happening over here. We got rid of this thing, which happens to be corresponding to the sum of those.
Vậy đó là điều đang xảy ra ở đây. Ta đã bỏ cái thứ này, vốn tương ứng với tổng của chúng.
This is often done because it's easier to just get rid of things that don't really matter if you know all you need to do at the end is just re-normalize to get the correct probabilities.
Người ta hay làm vậy vì dễ hơn khi bỏ những thứ không thật sự quan trọng, nếu ở cuối ta chỉ cần chuẩn hóa lại để có xác suất đúng. Vậy đó là cách tính phân phối có điều kiện của x1 khi có bằng chứng mới.
OK, so that's computing the conditional of x1 when new evidence comes in.
Không, đi chỗ khác.
No, go away.
Then the other thing that can happen is a transition over time. This is the Markov model update. We've seen this before.
Rồi điều khác có thể xảy ra là sự chuyển trạng thái theo thời gian. Đây là cập nhật của mô hình Markov. Ta đã thấy rồi.
This is just a [INAUDIBLE] x1 and x2 summing out over x1, which is this thing over here, and that's exactly what we've been doing in the first half of lecture.
Đây chỉ là phân phối đồng thời của x1 và x2 lấy tổng theo x1, chính là thứ ở đây, và đó chính xác là điều ta đã làm trong nửa đầu bài giảng. Được rồi, giờ ta làm cho nó rõ ràng hơn một chút.
OK, So let's now make this a little more explicit. These are the base cases. See, they're very simple bases with only two variables.
Đây là các trường hợp cơ sở. Bạn thấy đấy, chúng rất đơn giản, chỉ có hai biến. Giờ ta có thể dùng nó trong HMM, nơi quá trình này lặp đi lặp lại không?
Can we now use this in an HMM, where this process repeats over and over and over? Well, let's see.
Giờ ta có thể dùng nó trong HMM, nơi quá trình này lặp đi lặp lại không? Ta cùng xem.
We want to believe at time t, which is conditional of xt given all past evidence. After one step passes, we now want to transition to xt plus 1, given e1 through t.
Ta muốn có belief tại thời điểm t, tức là phân phối có điều kiện của xt Ta muốn có belief tại thời điểm t, tức là phân phối có điều kiện của xt với toàn bộ bằng chứng trong quá khứ. Sau khi trôi qua một bước, giờ ta muốn chuyển sang xt cộng 1, cho trước e1 đến et.
This notation here means we're conditioning on all evidence variables from e1 all the way through et. It's just a shorthand for many, many evidence variables, all the way from 1 through t.
Ký hiệu này nghĩa là ta đang điều kiện theo tất cả các biến bằng chứng từ e1 cho đến et. Đây chỉ là cách viết tắt cho rất nhiều biến bằng chứng, từ 1 cho đến t.
OK, well, what is it other than sum? We can bring in an extra variable and sum it out. You can always do that with a distribution over one variable.
Vậy ngoài tổng ra thì nó là gì? Ta có thể đưa thêm một biến vào rồi lấy tổng để loại nó đi. Bạn luôn làm được điều đó với phân phối trên một biến.
Bring in another one and just sum it out. The reason we bring in xt is because we assume recursively that we already know the belief for time t.
Đưa thêm một biến nữa vào rồi lấy tổng loại đi. Lý do ta đưa xt vào là vì ta giả định theo đệ quy rằng ta đã biết belief tại thời điểm t.
So by bringing in xt, we might be able to build us something we already have, whereas for xt plus 1, we don't have the answer yet. So we bring in xt.
Nên khi đưa xt vào, ta có thể xây dựng được thứ mà ta đã có, trong khi với xt cộng 1 thì ta chưa có đáp án. Vậy ta đưa xt vào.
We sum over it. We can now use the dynamics model, say that, OK, this joint is the conditional here times the distribution for xt given all evidence.
Ta lấy tổng theo nó. Giờ ta có thể dùng mô hình động học, nói rằng phân phối đồng thời này bằng xác suất có điều kiện này nhân với phân phối của xt cho trước toàn bộ bằng chứng.
This is exactly what a dynamics model looks like, except that everywhere we have additional conditioning on e1 through et. That's the only thing we added in. Otherwise, this is just a dynamics model update.
Đây đúng là dạng của một mô hình động học, chỉ khác là ở mọi chỗ ta có thêm điều kiện theo e1 đến et. Đó là điều duy nhất ta thêm vào. Còn lại, đây chỉ là bước cập nhật theo mô hình động học.
Now, we don't have all of these available. The red one we already have available. The black one we don't. What do we need to do?
Bây giờ, ta không có sẵn tất cả những số hạng này. Số hạng màu đỏ thì ta đã có. Số hạng màu đen thì chưa. Ta cần làm gì?
We need to somehow make an assumption. The hidden Markov model gives us the assumption that this thing here does not depend on these variables.
Ta cần đưa ra một giả định nào đó. Mô hình Markov ẩn cho ta giả định rằng số hạng này không phụ thuộc vào các biến này.
The distribution over xt plus 1 is — given xt doesn't depend on the evidence. So we can get rid of that. Now we have quantities we know.
Phân phối của xt cộng 1, cho trước xt, không phụ thuộc vào bằng chứng. Nên ta có thể bỏ phần đó đi. Giờ ta có các đại lượng đã biết.
This one we know recursively from the previous computation. This one is in our dynamics model, and we have the ability to compute, maybe in compact notation, the belief at the next time.
Số hạng này ta biết theo đệ quy từ phép tính trước. Số hạng này nằm trong mô hình động học, và ta có thể tính được, có lẽ theo ký hiệu gọn, belief ở thời điểm kế tiếp.
So this is exactly the Markov model calculation done again.
Vậy đây đúng là phép tính của mô hình Markov, làm lại một lần nữa.
We're just conditioning on e1 through et everywhere, and the place where our assumption comes in, the one place where we make an assumption in this entire calculation, is when we get rid of this conditioning here.
Ta chỉ điều kiện theo e1 đến et ở mọi chỗ, và chỗ giả định xuất hiện, chỗ duy nhất ta đưa ra giả định trong toàn bộ phép tính này, là khi ta bỏ điều kiện ở đây.
This here is something we can always do. It does not depend on the structure of our Bayes net or HMM.
Phần này thì lúc nào cũng làm được. Nó không phụ thuộc vào cấu trúc của mạng Bayes hay HMM.
But this transition here — getting rid of this — that's using a very specific conditional independence assumption that we have in this model. OK?
Nhưng bước chuyển này, tức là bỏ cái này đi, là dùng một giả định độc lập có điều kiện rất cụ thể mà mô hình này có. OK?
So we see that believes essentially just get pushed through the transition model. Get the beliefs for the next time.
Vậy ta thấy các belief về cơ bản chỉ được đẩy qua mô hình chuyển. Để có belief cho thời điểm kế tiếp.
Often, what it means is that uncertainty will accumulate. We've seen this with the ghost environments.
Thường thì điều này có nghĩa là độ bất định sẽ tích lũy. Ta đã thấy điều này với môi trường có ma.
As we push through the transition model, the ghosts will kind of circle around, but also diffuse their probability, and it will take measurements to concentrate that distribution again.
Khi ta đẩy qua mô hình chuyển, các con ma sẽ đi vòng vòng, nhưng cũng khuếch tán xác suất của chúng, và cần có các phép đo để làm phân phối tập trung lại.
So we've seen this in demo. How about the observation? We want to know the belief after an observation. So we assume we already have the believe before an observation.
Ta đã thấy điều này trong bản demo. Còn quan sát thì sao? Ta muốn biết belief sau một quan sát. Nên ta giả định đã có belief trước quan sát.
So this is — assume we know that recursively from the previous calculation. Can we use this to now get the distribution for xt plus 1, given all evidence up to time t plus 1?
Tức là, giả sử ta biết nó theo đệ quy từ phép tính trước. Ta có thể dùng nó để tìm phân phối của xt cộng 1, cho trước toàn bộ bằng chứng đến thời điểm t cộng 1 không?
This is only up to time t. OK, well, how do we do that? To be able to condition and also evidence of time t plus 1, this is what we need.
Cái này mới chỉ đến thời điểm t. OK, vậy làm thế nào? Để điều kiện thêm cả bằng chứng ở thời điểm t cộng 1, ta cần cái này.
And we somehow need to get this in terms of this expression we already have in our measurement model — the distribution over et plus 1 given xt plus 1, because that's going to tell us how the evidence influences our belief.
Và ta cần biểu diễn nó theo biểu thức ta đã có trong mô hình đo lường, phân phối của et cộng 1 cho trước xt cộng 1, vì nó sẽ cho ta biết bằng chứng ảnh hưởng đến belief của ta như thế nào.
OK, well, we know that we can expand this by definition this way. And notice that, again, e1 through t are just kind of hanging off the back.
OK, ta biết có thể khai triển cái này theo định nghĩa như thế này. Và lưu ý rằng, một lần nữa, e1 đến t chỉ như bám thêm ở phía sau.
If they weren't there, this would look a lot simpler to you. But of course, we need them there to be complete here.
Nếu chúng không có ở đó, trông nó sẽ đơn giản hơn nhiều với bạn. Nhưng dĩ nhiên, ta cần chúng ở đó để cho đầy đủ.
Then we do the proportional thing. What does that mean again? Well, we're interested in distribution over xt plus 1. That's the only variable.
Rồi ta làm phép tỉ lệ. Điều đó nghĩa là gì nhỉ? Ta quan tâm đến phân phối trên xt cộng 1. Đó là biến duy nhất.
This stuff in the back here doesn't have xt plus 1 in it. It's a constant as far as xt plus 1 is concerned, so you can remove it.
Phần phía sau này không chứa xt cộng 1. Với xt cộng 1 thì nó là hằng số, nên bạn có thể bỏ nó đi.
Note that it needs to be a multiplication with a constant. If it's plus some constant, you can't just drop it. But if you multiply with a constant, you can drop it, and later, re-normalize.
Lưu ý nó phải là phép nhân với hằng số. Nếu là cộng thêm hằng số thì không thể bỏ được. Nhưng nếu nhân với hằng số thì bỏ được, rồi chuẩn hóa lại sau.
OK, then we can use — and again, imagine these are not here for a moment. Then this should look very simple to you.
OK, rồi ta có thể dùng và một lần nữa, hãy tưởng tượng những cái này tạm thời không có ở đây. Thì cái này trông sẽ rất đơn giản với bạn.
It's just decomposing the joint over two variables in the marginal plus the conditional. And then just everywhere, we also condition on all those past evidence variables.
Nó chỉ là phân tách phân phối đồng thời của hai biến thành phân phối biên cộng với phân phối có điều kiện. Và ở mọi chỗ, ta cũng điều kiện theo tất cả các biến bằng chứng trong quá khứ.
Then, we apply an assumption.
Sau đó, ta áp dụng một giả định.
Getting rid of this thing over here is saying that the evidence of time t plus 1 not depend on any past evidence if we know the state at time t plus 1.
Bỏ cái này ở đây đi nghĩa là nói rằng bằng chứng tại thời điểm t cộng 1 không phụ thuộc vào bằng chứng quá khứ nào nếu ta biết trạng thái tại thời điểm t cộng 1.
That's an assumption. This here is where our assumption comes in.
Đó là một giả định. Đây là chỗ giả định của ta xuất hiện.
Now we have it expressed in terms of what we already had and something that's in our model, our measurement model, and we can do this calculation. What will be the result of this calculation?
Giờ ta đã biểu diễn nó theo thứ ta đã có và thứ có trong mô hình, mô hình đo lường của ta, và ta có thể thực hiện phép tính này. Kết quả của phép tính này sẽ là gì?
It will be something that's proportional to what we care about. And then we can just re-normalize, which means we'll have a table with a bunch of entries.
Nó sẽ tỉ lệ với thứ mà ta quan tâm. Và rồi ta chỉ cần chuẩn hóa lại, nghĩa là ta sẽ có một bảng gồm nhiều mục.
They won't sum to 1, but we'll sum them up nevertheless. We'll see it's not 1, and then we'll divide every entry by the sum to get it to sum to 1.
Chúng không có tổng bằng 1, nhưng ta cứ cộng chúng lại. Ta thấy tổng không phải 1, rồi ta sẽ chia từng mục cho tổng để tổng bằng 1.
And what we're doing in that process is effectively, we're computing this thing over here, which we kind of decided to forget about.
Và về bản chất, trong quá trình đó ta đang tính đại lượng này ở đây, mà ta đã quyết định bỏ qua.
And by summing all the entries, we get this thing over here, and then we divide by it to get things to sum to 1.
Khi cộng tất cả các mục, ta được đại lượng này ở đây, rồi ta chia cho nó để tổng bằng 1.
OK, far more compactly, we have the belief that the next time is proportional to belief at the previous time multiplied by probability of evidence.
OK, viết gọn hơn nhiều: belief ở thời điểm kế tiếp tỉ lệ với belief ở thời điểm trước nhân với xác suất của bằng chứng.
So if the evidence is very compatible with the next state, then the probability mass will go up for that next state.
Nếu bằng chứng rất phù hợp với trạng thái kế tiếp, thì khối lượng xác suất của trạng thái đó sẽ tăng lên.
If the evidence is very incompatible with the next state, the probability mass will go down for that state. That's the multiplicative effect happening over here.
Nếu bằng chứng rất không phù hợp với trạng thái kế tiếp, khối lượng xác suất của trạng thái đó sẽ giảm xuống. Đó là hiệu ứng nhân đang diễn ra ở đây.
OK. So typically, when an observation happens, beliefs will concentrate, as we see going from left to right here.
OK. Thông thường, khi có một quan sát, các belief sẽ tập trung lại, như ta thấy khi đi từ trái sang phải ở đây.
Let's look at the weather HMM. This slide is working through the math. We start with a uniform distribution over here.
Hãy xem HMM thời tiết. Slide này đi qua phần tính toán. Ta bắt đầu với phân phối đều ở đây.
Then we transition to, again, uniform, because it's just the way the transition model is set up.
Sau đó chuyển sang, lại là phân phối đều, vì mô hình chuyển được thiết lập như vậy.
But then we have an observation, which sees plus r, which then moves more weight onto where we see an umbrella, which is correlated with plus r.
Nhưng rồi ta có một quan sát, thấy +r, nên dồn thêm trọng số vào chỗ ta thấy ô, vốn tương quan với +r.
And so we see more mass shifted on to the plus r, and then this process repeats. These are the numbers corresponding to these tables over there.
Vì vậy ta thấy nhiều khối lượng hơn dồn sang +r, và quá trình này lặp lại. Đây là các con số tương ứng với những bảng ở đằng kia.
If you work through the equations on the previous slide, you then get these numbers here.
Nếu bạn tính qua các phương trình ở slide trước, bạn sẽ ra những con số này.
And this is just a very procedural thing you can just repeat over and over to get the conditional distribution of current state given all past evidence. There's another way to write this.
Đây chỉ là một quy trình thủ tục mà bạn có thể lặp đi lặp lại để có phân phối có điều kiện của trạng thái hiện tại khi biết mọi bằng chứng trong quá khứ. Còn một cách viết khác.
Another way to write this is in one big update. So rather than saying I'm doing a time update and I'm doing an evidence update, I'm going to just do one update.
Một cách khác là viết thành một cập nhật lớn duy nhất. Thay vì nói tôi làm cập nhật thời gian rồi làm cập nhật bằng chứng, tôi sẽ chỉ làm một cập nhật.
So how would that work? Let's say I want this quantity as a function of the quantity at the previous time.
Vậy nó hoạt động thế nào? Giả sử tôi muốn đại lượng này theo hàm của đại lượng ở thời điểm trước.
I'm first going to say, well, really, I should be dividing here by e1 through t.
Đầu tiên tôi nói, thật ra ở đây tôi phải chia cho e1 đến t.
But that doesn't depend on xt, so I'm just using this proportional sign here to get rid of that division, and we can later make things sum to 1, and that will make up for this.
Nhưng nó không phụ thuộc vào xt, nên tôi chỉ dùng dấu tỉ lệ ở đây để bỏ phép chia đó, và sau này ta có thể chuẩn hóa cho tổng bằng 1, và điều đó sẽ bù lại.
Then I can write this out as bringing in xt minus 1. Why? Because we want a recursive update equation as a function of what we had at the previous time.
Rồi tôi có thể viết ra bằng cách đưa xt trừ 1 vào. Tại sao? Vì ta muốn một phương trình cập nhật đệ quy theo hàm của những gì ta có ở thời điểm trước.
So bring in xt minus 1 sum it out. Then we can decompose this into what we already have, [? being ?] for xt minus 1, then the transition model and the evidence.
Nên đưa xt trừ 1 vào rồi lấy tổng theo nó. Sau đó ta phân rã thành những gì ta đã có, belief cho xt trừ 1, rồi mô hình chuyển và bằng chứng.
So we have both things happening at the same time here — transition and evidence.
Vậy cả hai việc xảy ra cùng lúc ở đây: chuyển trạng thái và bằng chứng.
We can reorganize this a little bit, and this would be the kind of single update way of getting both a transition incorporated and evidence.
Ta có thể sắp xếp lại một chút, và đây sẽ là cách cập nhật một lần để đưa vào cả bước chuyển lẫn bằng chứng.
It comes down to the same result as doing it one and then the other, but sometimes this might be convenient to do it this way.
Kết quả giống như làm bước này rồi đến bước kia, nhưng đôi khi làm theo cách này sẽ tiện hơn.
If you look at the details, you'll see that if you do variable elimination and you elimination variable x1, then x2, then x3, then x4, all the way to xt minus 1, I end up with distribution for xt given all past evidence.
Nếu xem kỹ chi tiết, bạn sẽ thấy nếu bạn khử biến và khử biến x1, rồi x2, rồi x3, rồi x4, cho đến xt trừ 1, tôi sẽ có phân phối của xt khi biết mọi bằng chứng quá khứ.
It's exactly the same as this calculation here, as long as you do your variable elimination going from time 1 all the way to the time you're currently at.
Nó hoàn toàn giống phép tính này, miễn là bạn khử biến từ thời điểm 1 cho đến thời điểm hiện tại.
Online belief updates, which is most common, is where you would essentially just do these things. So you would update for time, which we derived as this equation. Then you'd update for evidence and repeat.
Cập nhật belief trực tuyến, là cách phổ biến nhất, về cơ bản là bạn chỉ làm những bước này. Bạn cập nhật theo thời gian, mà ta đã suy ra thành phương trình này. Rồi cập nhật theo bằng chứng và lặp lại.
If you have multiple time of dates without evidence, then you just repeat this one multiple times. And then, once finally some evidence comes in again, you can do an evidence update.
Nếu có nhiều bước thời gian liên tiếp không có bằng chứng, thì bạn chỉ lặp lại bước này nhiều lần. Và cuối cùng, khi có bằng chứng đến lần nữa, bạn có thể làm cập nhật bằng chứng.
Keep in mind, again, this thing here means this is an un-normalized update.
Lưu ý lại, ký hiệu này ở đây nghĩa là đây là cập nhật chưa chuẩn hóa.
It will be an un-normalized distribution, which you need to normalize by summing all the entries and dividing every entry by the sum. OK.
Đó sẽ là phân phối chưa chuẩn hóa, bạn cần chuẩn hóa bằng cách cộng tất cả các mục và chia từng mục cho tổng. OK.
Once we do this, we can reconsider the Pac-Man game that we saw at the very beginning, and we can have an agent play it with beliefs visualized.
Xong việc này, ta có thể xét lại trò Pac-Man mà ta đã thấy ngay từ đầu, và cho một tác tử chơi với các belief được hiển thị.
So it's showing in color distribution over possible locations of each of the ghosts.
Nó hiển thị bằng màu phân phối trên các vị trí có thể có của từng con ma.
And then, of course, you can run a search to try to get as close as possible to the ghost because you're more powerful than the ghost in this game and go put it in its ghost jail slot at the bottom left.
Và tất nhiên, bạn có thể chạy tìm kiếm để đến gần con ma nhất có thể vì trong trò này bạn mạnh hơn con ma và nhốt nó vào ô nhà tù ma ở dưới cùng bên trái.
And if your project 4 is successful, this is pretty much what it should look like when fully up and running.
Và nếu project 4 của bạn thành công, thì khi chạy đầy đủ nó sẽ trông gần như thế này.
Huh? Difficult one. Ghost is escaping, it seems.
Hả? Khó đấy. Có vẻ con ma đang trốn thoát.
Oh, come on, random seed. Give Pac-Man a break.
Ôi thôi nào, random seed. Tha cho Pac-Man đi.
Ah, OK.
À, OK.
That kind of showcases that it's not always the ghosts is where the maximum probability is. It might very well be one of the low probability squares. So let's see.
Điều đó cho thấy không phải lúc nào con ma cũng ở chỗ có xác suất cực đại. Nó rất có thể nằm ở một ô có xác suất thấp. Vậy, xem nào.
What's left for us? Next time, we'll look at particle filtering and more applications of HMMs. What particle filtering will do will be the counterpart of sampling methods that we saw in Bayesian networks.
Còn lại gì cho chúng ta? Lần sau, ta sẽ xem lọc hạt và thêm các ứng dụng của HMM. Lọc hạt sẽ là đối tác của các phương pháp lấy mẫu mà chúng ta đã thấy trong mạng Bayes.
But then sampling methods for HMMs — this is for when your HMM has two large a state space to be able to run the algorithms we saw today.
Tức là các phương pháp lấy mẫu cho HMM, dùng khi HMM của bạn có không gian trạng thái quá lớn để có thể chạy các thuật toán mà hôm nay chúng ta đã học.
All right?
Được chứ?
Đă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.