Video
Đăng bởi Ban biên tập OpenER ·
Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
PROFESSOR
OK. All right. I'm too quiet this time. All right, everybody.
Được rồi. Nào. Lần này em nói nhỏ quá. Chào cả lớp.
Today, we are going to continue talking about hidden Markov models.
Hôm nay chúng ta sẽ tiếp tục nói về mô hình Markov ẩn (HMM).
And in particular, we're going to extend what you saw last time about inference in hidden Markov models to a sampling based technique called particle filtering. And we'll also see some applications of these methods.
Cụ thể, ta sẽ mở rộng phần suy luận trong mô hình Markov ẩn mà các em đã học lần trước sang một kỹ thuật dựa trên lấy mẫu gọi là lọc hạt. Chúng ta cũng sẽ xem vài ứng dụng của các phương pháp này.
We'll see even more applications towards the end. The overall structure of this course, remember the beginning was about choosing actions. The middle has been about reasoning about uncertainty.
Về cuối khóa sẽ còn nhiều ứng dụng hơn nữa. Về cấu trúc chung của môn học, phần đầu nói về việc chọn hành động. Phần giữa nói về suy luận trong điều kiện bất định.
The last chunk of the course will be about machine learning.
Phần cuối của môn sẽ là học máy.
And then at the very end, there will be a section on applications where we'll see a bunch of different techniques that we've seen throughout the semester show up.
Và ngay cuối cùng sẽ có một phần về ứng dụng, ở đó ta sẽ thấy nhiều kỹ thuật khác nhau đã học trong suốt học kỳ xuất hiện trở lại.
Hidden Markov models will feature prominently, because this basic idea of reasoning about underlying phenomena over time on the basis of noisy observations is a really important one.
Mô hình Markov ẩn sẽ đóng vai trò nổi bật, vì ý tưởng cơ bản là suy luận về các hiện tượng tiềm ẩn theo thời gian dựa trên các quan sát có nhiễu là một ý tưởng rất quan trọng.
And that overall framing backs a lot of modern problems in AI, though the specific techniques that we use do vary.
Khung tổng quát đó nằm sau rất nhiều bài toán AI hiện đại, dù các kỹ thuật cụ thể thì khác nhau.
So today, what we're going to do is we're going to talk about quickly recap hidden Markov models from last time. We're going to talk about particle filtering as an approach to doing inference.
Hôm nay chúng ta sẽ điểm nhanh lại mô hình Markov ẩn từ buổi trước. Sau đó nói về lọc hạt như một cách tiếp cận để suy luận.
Particle filtering partially is something we do — yes?
Lọc hạt một phần là thứ ta làm — em có câu hỏi à?
STUDENT
[INAUDIBLE] PROFESSOR: All right, can people hear me in the back? OK. All right, I think for once, I'm just quieter than expected.
[KHÔNG NGHE RÕ] GIÁO SƯ: Các em ở cuối lớp nghe rõ không? Được. Có lẽ lần này tôi chỉ nói nhỏ hơn dự kiến.
All right, how's that? I also just got louder.
Giờ thế nào? Tôi cũng vừa nói to lên rồi.
All right, so if everyone can hear, let's find that train of thought was particle filtering, we partially do in the real world, because it's efficient.
Nếu mọi người đều nghe được thì quay lại mạch ý: lọc hạt, một phần ta dùng trong thực tế vì nó hiệu quả.
Especially when your event spaces are very large or continuous or infinite, it can be a very powerful technique. But it's also a really useful way of understanding what's happening in the exact case.
Đặc biệt khi không gian sự kiện rất lớn, liên tục hoặc vô hạn, đây có thể là kỹ thuật rất mạnh. Nhưng nó cũng là cách hữu ích để hiểu điều xảy ra trong trường hợp chính xác.
Because sometimes, it's easier to think about tracking a particular particle or a particular sample instead of tracking the exact space in aggregate.
Vì đôi khi dễ hơn khi nghĩ về việc theo dõi một hạt hay một mẫu cụ thể thay vì theo dõi toàn bộ không gian một cách tổng hợp.
We're going to see a bunch of demos to illustrate what goes on in these exact and approximate techniques.
Chúng ta sẽ xem vài bản demo để minh họa điều diễn ra trong các kỹ thuật chính xác và xấp xỉ này.
And if there's time, we'll start talking about most likely explanation queries, which are used for a lot of things like speech recognition where you're interested not only in tracking something over time, but in reconstructing the trajectory it took over time.
Nếu còn thời gian, ta sẽ bắt đầu nói về các truy vấn giải thích khả dĩ nhất, được dùng nhiều như trong nhận dạng giọng nói, khi ta quan tâm không chỉ việc theo dõi một thứ theo thời gian, mà còn dựng lại quỹ đạo mà nó đã đi qua.
We'll see some applications today. Robot localization and mapping are going to feature prominently as well as some ghost busting.
Hôm nay ta sẽ thấy một số ứng dụng. Định vị và lập bản đồ cho robot sẽ xuất hiện nhiều, cùng với việc săn ma.
And later on in the course, we will see a little bit of information about speech recognition.
Và sau này trong khóa, ta sẽ thấy đôi chút về nhận dạng giọng nói.
So to recap, last time, you saw a couple instances of reasoning about how a random variable evolves over time.
Tóm tắt lại: lần trước các em đã thấy vài ví dụ suy luận về cách một biến ngẫu nhiên thay đổi theo thời gian.
The simplest instantiation of a random variable evolving over time is a Markov chain, like what's shown here.
Dạng đơn giản nhất của biến ngẫu nhiên thay đổi theo thời gian là chuỗi Markov, như hình này.
In a Markov model, you have some variable x that replicates at every time step, and you're interested in watching how its value evolves probabilistically over time.
Trong mô hình Markov, có một biến x lặp lại ở mỗi bước thời gian, và ta muốn xem giá trị của nó biến đổi theo xác suất qua thời gian như thế nào.
In order to do this, we need to supply you with a couple pieces of information, so that you can ask questions like, what's the probability of this variable on day three?
Để làm được điều này, ta cần cung cấp một vài thông tin, để các em có thể hỏi như: xác suất của biến này vào ngày thứ ba là bao nhiêu?
And so we need to give you an initial probability distribution, so some initial marginal probability over x at the first time step. And we also need to give you a transition probability matrix.
Vậy ta cần cho một phân phối xác suất ban đầu, tức một xác suất biên ban đầu của x ở bước thời gian đầu tiên. Và ta cũng cần cho một ma trận xác suất chuyển.
These are sometimes referred to as the dynamics of the model, and this represents the probability distribution over this variable x given its value at the time before.
Đôi khi nó được gọi là động lực học của mô hình, và nó biểu diễn phân phối xác suất của biến x khi biết giá trị của nó ở thời điểm trước.
So what this tells you is this tells you probabilistically how this variable evolves.
Vậy nó cho ta biết biến này tiến triển theo xác suất ra sao.
If this variable is a variable that is unchanging, this will be a big diagonal matrix that just says whatever you were before with probability one, you'll be the same thing at the next time step.
Nếu biến này không thay đổi, đây sẽ là một ma trận đường chéo lớn, nghĩa là trước đó là gì thì với xác suất một, ở bước sau vẫn là cái đó.
Usually, something more interesting is happening. So the example you saw last time is over here on the right, and this is a very, very simple Markov model.
Thường thì có điều thú vị hơn xảy ra. Ví dụ lần trước ở bên phải đây, là một mô hình Markov rất đơn giản.
Here, the random variable x takes on the value rain or sun and represents a simplification of weather.
Ở đây biến ngẫu nhiên x nhận giá trị mưa hoặc nắng và là phiên bản đơn giản hóa của thời tiết.
And this thing on the right, if you look at it really quickly you say, that's the strangest Bayes net I've ever seen, because the arrows form cycles, and some of them are even pointing at themselves.
Hình bên phải này, nếu nhìn lướt qua các em sẽ bảo: mạng Bayes gì kỳ lạ nhất mình từng thấy, các mũi tên tạo thành chu trình, có cái còn trỏ vào chính nó.
It's not a Bayes net. So on the left, that's a Bayes net.
Nó không phải mạng Bayes. Còn bên trái mới là mạng Bayes.
So even though we talk about hidden Markov models and Markov models as special cases, because we feed them to you in time slices, and then they unroll over time, this here is a Bayes net.
Dù ta nói mô hình Markov ẩn và mô hình Markov là các trường hợp đặc biệt, vì ta đưa chúng theo từng lát cắt thời gian, rồi chúng được trải ra theo thời gian, thì cái này là một mạng Bayes.
Over here, this is not. This is, in fact, more like a finite automaton. The circles on the right represent the states of this Markov model.
Còn bên này thì không. Thực ra nó giống một automat hữu hạn hơn. Các vòng tròn bên phải biểu diễn các trạng thái của mô hình Markov này.
And in particular, they represent elements in the domain of the random variable x. So here, x can take on the values rain or sun.
Cụ thể, chúng biểu diễn các phần tử trong miền giá trị của biến ngẫu nhiên x. Ở đây x có thể nhận giá trị mưa hoặc nắng.
And the probabilities are represented here by the arrows, which show what state transitions are possible, meaning probability non-zero, and the numbers or weights on those arcs, which represent the probability.
Các xác suất được biểu diễn bằng các mũi tên, cho biết chuyển trạng thái nào khả dĩ, nghĩa là xác suất khác không, còn các con số hay trọng số trên các cung đó biểu diễn xác suất.
So it says, for example, if it's rainy today, 70% chance of rain tomorrow and 30% chance that it will transition to sun.
Chẳng hạn, nếu hôm nay trời mưa, thì ngày mai 70% vẫn mưa và 30% sẽ chuyển sang nắng.
This kind of a network structure is really useful for specifying the structure within the different states and how they can interact.
Kiểu cấu trúc mạng này rất hữu ích để đặc tả cấu trúc giữa các trạng thái khác nhau và cách chúng có thể tương tác.
This is useful for things like speech recognition where not all states can connect up to other states.
Điều này hữu ích cho những việc như nhận dạng giọng nói, nơi không phải trạng thái nào cũng nối được tới trạng thái khác.
When you see these, don't confuse them with Bayes nets or try to run variable elimination on them. They are representations of probability tables. All right, so you have a Markov model.
Khi thấy các sơ đồ này, đừng nhầm chúng với mạng Bayes hay cố chạy khử biến trên chúng. Chúng là cách biểu diễn các bảng xác suất. Được rồi, vậy là ta có một mô hình Markov.
And if I give you a Markov model, shown as a Bayes net on the left, and I give you the specific probabilities that live inside it, shown on the right, what can you do?
Nếu tôi đưa cho bạn một mô hình Markov, biểu diễn dưới dạng mạng Bayes ở bên trái, cùng các xác suất cụ thể nằm bên trong nó, ở bên phải, bạn làm được gì?
There's not a lot you can do. You can do things like say, if yesterday it was sunny, what's the probability of rain? Or what's the probability of rain five days after it was sunny?
Bạn làm được không nhiều. Bạn có thể hỏi, nếu hôm qua trời nắng, thì xác suất mưa là bao nhiêu? Hoặc xác suất trời mưa năm ngày sau một ngày nắng là bao nhiêu?
These are computations you can do on a simple Markov model like this without any evidence or observations, like we'll see in a hidden Markov model.
Đây là các phép tính bạn làm được trên một mô hình Markov đơn giản như thế này, không có bằng chứng hay quan sát nào, khác với mô hình Markov ẩn mà ta sắp thấy.
There are other uses for Markov models that you talked about last time, I think. Like for example, looking at the stationary distribution, that backs some algorithms like page rank where that quantity is important.
Mô hình Markov còn có những ứng dụng khác mà tôi nghĩ buổi trước các bạn đã học. Ví dụ như xét phân phối dừng, thứ làm nền cho một số thuật toán như page rank, nơi đại lượng đó rất quan trọng.
In a hidden Markov model, which is much, much, much more useful, you have not only the random variable x, which tends to be the variable that you're trying to track or reason about, you also have another class of variables that you see at every time step, which are your noisy observations of something that's connected to x.
Trong mô hình Markov ẩn, hữu ích hơn rất, rất nhiều, bạn không chỉ có biến ngẫu nhiên x, thường là biến mà bạn muốn theo dõi hoặc suy luận về nó, mà còn có thêm một lớp biến khác mà bạn thấy ở mỗi bước thời gian, đó là các quan sát có nhiễu về một thứ liên quan đến x.
They may be an observation of x itself. They may be a sensor reading.
Đó có thể là quan sát chính x. Có thể là số đọc của một cảm biến.
But what you have now is in addition to at each time step knowing how the variable x evolves, you also have evidence, and you're armed with a table that shows you for any value of the underlying state x, which you don't observe, what the probability distribution over evidence values is, which in general you do observe.
Nhưng giờ ngoài việc biết ở mỗi bước thời gian biến x tiến triển ra sao, bạn còn có bằng chứng, và bạn có một bảng cho biết với mỗi giá trị của trạng thái ẩn x, thứ bạn không quan sát được, thì phân phối xác suất trên các giá trị bằng chứng là gì, thứ mà nhìn chung bạn quan sát được.
There are other questions you could ask of this Bayes net shown here as a hidden Markov model, but the one you usually ask is, given evidence at every time step, either what is the current distribution, the current posterior distribution over the variable x given all my evidence to date, or I ask the question, what sequence of x values was most likely given the evidence I've seen?
Bạn có thể hỏi những câu khác về mạng Bayes này, ở đây được vẽ như một mô hình Markov ẩn, nhưng câu thường hỏi nhất là: cho bằng chứng ở mỗi bước thời gian, phân phối hiện tại là gì, tức phân phối hậu nghiệm hiện tại của biến x cho toàn bộ bằng chứng đến nay, hoặc câu hỏi: chuỗi giá trị x nào có khả năng nhất, cho bằng chứng tôi đã thấy?
In this case, p of given x says something like, when there's rain, you usually see the umbrella. And when there's sun, you usually don't see the umbrella.
Trong trường hợp này, p của e cho x nói lên điều như khi trời mưa, bạn thường thấy cái ô. Và khi trời nắng, bạn thường không thấy cái ô.
If you remember, this was a case of something like a, I don't know, maybe a security cam robot that doesn't get to see the weather, but sometimes sees you walk in and out with or without your umbrella and has to reconstruct something about its belief over the variable that represents weather.
Nếu còn nhớ, đây là trường hợp như một robot camera an ninh chẳng hạn, không thấy được thời tiết, nhưng thỉnh thoảng thấy bạn đi ra đi vào có hoặc không có ô, và phải suy ra niềm tin của nó về biến biểu diễn thời tiết.
All right, so these are Markov models, which we won't say much more about, and hidden Markov models, which we're going to say a lot about. Let's see an example.
Vậy đó là các mô hình Markov, mà ta sẽ không nói thêm nhiều, và mô hình Markov ẩn, mà ta sẽ nói rất nhiều. Hãy xem một ví dụ.
OK.
OK.
All right, so here is our ghost buster grid. What is this showing? This is going to show at all times our belief distribution over the random variable ghost location.
Đây là lưới săn ma của chúng ta. Nó đang hiển thị gì? Nó luôn hiển thị phân phối niềm tin của ta về biến ngẫu nhiên vị trí con ma.
What's a belief distribution? It's the conditional probability of that variable given all the evidence to date. And right now, there is no evidence to date. So how can I change this?
Phân phối niềm tin là gì? Đó là xác suất có điều kiện của biến đó cho toàn bộ bằng chứng đến nay. Và hiện giờ chưa có bằng chứng nào. Vậy làm sao thay đổi nó?
Well, in a hidden Markov model, you'll notice that there's a very regimented structure, which you'll have to modify to make more flexible in your projects.
Trong mô hình Markov ẩn, bạn sẽ thấy cấu trúc rất cứng nhắc, và bạn sẽ phải sửa để linh hoạt hơn trong các project.
In a hidden Markov model, every time step, you get some sort of evidence, and then time elapses, and then more evidence comes in, and then time elapses.
Trong mô hình Markov ẩn, mỗi bước thời gian, bạn nhận một bằng chứng nào đó, rồi thời gian trôi, rồi thêm bằng chứng đến, rồi thời gian lại trôi.
So if I were going to simulate that here, I could say, I'm going to get some evidence.
Để mô phỏng ở đây, tôi có thể nói: tôi sẽ nhận một bằng chứng.
And what that does is it reshapes my posterior distribution knowing that the ghost is medium far from that point probably.
Việc đó định hình lại phân phối hậu nghiệm của tôi, vì biết con ma có lẽ ở khoảng cách trung bình so với điểm đó.
Now if I let time pass, this ring that represents my belief distribution, what's going to happen? It's going to get moved around through the dynamics of the model.
Giờ nếu tôi cho thời gian trôi, vòng tròn này biểu diễn phân phối niềm tin của tôi, điều gì sẽ xảy ra? Nó sẽ bị dịch chuyển theo động lực học của mô hình.
And you can't see in this visualization what the probability of ghost position is given the previous ghost position. But let's imagine I know that the ghost tend to wander around clockwise in a circle.
Và bạn không thấy được trong hình này xác suất của vị trí con ma cho vị trí trước đó của nó. Nhưng hãy tưởng tượng tôi biết con ma hay đi vòng quanh theo chiều kim đồng hồ.
So you can see that diamond of higher probability has been pushed along that whirlpool there. So in a hidden Markov model then, I will get more evidence.
Bạn thấy hình thoi có xác suất cao hơn đã bị đẩy theo vòng xoáy đó. Trong mô hình Markov ẩn, tôi sẽ nhận thêm bằng chứng.
Notice that when I get this evidence, it tends to sharpen my belief distribution. It's easier to localize the ghost after I get information about its position. That makes sense.
Để ý là khi nhận bằng chứng này, phân phối niềm tin của tôi thường trở nên nhọn hơn. Dễ định vị con ma hơn sau khi có thông tin về vị trí của nó. Điều đó hợp lý.
But then when time elapses, not only does this probability swirl around a little bit, it also flattens. And this makes sense too, because I'm not totally sure where the ghost is.
Nhưng khi thời gian trôi, xác suất này không chỉ xoáy đi một chút mà còn dẹt ra. Điều này cũng hợp lý, vì tôi không hoàn toàn chắc con ma đang ở đâu.
And as time passes, I become even less sure, because its movement isn't deterministic. So in a hidden Markov model, I would get another piece of evidence. Time would elapse.
Và thời gian càng trôi, tôi càng kém chắc chắn, vì chuyển động của nó không tất định. Vậy trong mô hình Markov ẩn, tôi sẽ nhận thêm một bằng chứng. Thời gian trôi.
Get evidence. Time elapses. And you can see that I'm slowly accumulating, in this case, some certainty about the position, but I'm never totally sure. OK, now, I'm pretty sure.
Nhận bằng chứng. Thời gian trôi. Bạn thấy tôi dần tích lũy được, trong trường hợp này, độ chắc chắn về vị trí, nhưng không bao giờ hoàn toàn chắc. OK, giờ thì tôi khá chắc rồi.
And if I stopped collecting evidence and I treated this like a Markov model instead of a hidden Markov model, what's going to happen? Right now, I'm pretty sure where the ghost is.
Và nếu tôi ngừng thu thập bằng chứng và coi nó như một mô hình Markov thay vì mô hình Markov ẩn, điều gì sẽ xảy ra? Lúc này, tôi khá chắc con ma đang ở đâu.
OK. I'm super sure where the ghost is.
OK. Tôi cực kỳ chắc con ma ở đâu.
If I let time pass, my belief distribution gets flatter and flatter, because the possibilities that could unfold drift further away from that most likely position.
Nếu cho thời gian trôi qua, phân phối belief của tôi sẽ ngày càng phẳng hơn, vì các khả năng có thể xảy ra sẽ trôi ngày càng xa khỏi vị trí có khả năng nhất đó.
All right. So that gives you a sense of a little bit of what happens when time passes and what happens when you get evidence.
Được rồi. Vậy là các em đã có chút hình dung về chuyện gì xảy ra khi thời gian trôi qua và khi có thêm bằng chứng.
And those are the two building blocks that we're going to use, both in exact inference and in sample based inference with particle filtering to construct and track our belief distributions over the random variable x.
Đó là hai khối xây dựng mà ta sẽ dùng, cả trong suy luận chính xác lẫn suy luận dựa trên lấy mẫu với lọc hạt, để xây dựng và theo dõi các phân phối belief trên biến ngẫu nhiên x.
So there's basically two pieces we can break that into, and we want to wrap our heads around the math. Because it's basically these two little building blocks that get used over and over.
Về cơ bản ta tách thành hai phần, và ta muốn nắm chắc phần toán. Bởi vì chính hai khối nhỏ này được dùng đi dùng lại.
So the first case is this passage of time. I don't exactly know where the ghost is. I don't exactly in general know what value x1 takes, but I have some distribution.
Trường hợp đầu tiên là thời gian trôi qua. Tôi không biết chính xác con ma ở đâu. Nói chung tôi không biết chính xác x1 nhận giá trị nào, nhưng tôi có một phân phối.
And I'd like to say something about that random variable at the next time step. I'd like to predict forward one layer.
Và tôi muốn nói điều gì đó về biến ngẫu nhiên đó ở bước thời gian kế tiếp. Tôi muốn dự đoán tiến lên một lớp.
Predicting forward involves taking my belief distribution and advancing it through the dynamics of the model. We'll dive into that. That's going to show up over and over.
Dự đoán tiến lên nghĩa là lấy phân phối belief và đẩy nó đi qua động lực học của mô hình. Ta sẽ đi sâu vào phần này. Nó sẽ xuất hiện liên tục.
The second base case is I have some distribution over the random variable x. I think the ghost is about here. Then evidence comes in. That evidence will also reshape my belief distribution.
Trường hợp cơ sở thứ hai là tôi có một phân phối trên biến ngẫu nhiên x. Tôi nghĩ con ma ở khoảng đây. Rồi bằng chứng đến. Bằng chứng đó cũng định hình lại phân phối belief của tôi.
And from these two building blocks, you can do any kind of updates of getting a bunch of evidence or letting time pass for a while without getting evidence.
Và từ hai khối xây dựng này, ta có thể cập nhật cho mọi tình huống: nhận nhiều bằng chứng hoặc để thời gian trôi một lúc mà không có bằng chứng.
You can do it in the exact case, and you can do it in the sampling based case. So let's dive into these two cases.
Ta làm được trong trường hợp chính xác, và làm được trong trường hợp dựa trên lấy mẫu. Vậy ta đi vào hai trường hợp này.
All right, first one, the first one is I'd like to know the distribution over x based on what? Right? So let's say I want to know the distribution over x at time two.
Được rồi, trường hợp đầu tiên là tôi muốn biết phân phối của x dựa trên cái gì? Đúng không? Giả sử tôi muốn biết phân phối của x tại thời điểm hai.
Well, what do I know? In general here, I'm going to know the distribution at the previous time step. So what do I know? I happen to already know P of x1.
Vậy tôi biết gì? Nói chung ở đây tôi sẽ biết phân phối ở bước thời gian trước. Vậy tôi biết gì? Giả sử tôi đã biết P của x1.
Why? Well, it could actually be that I've observed x1. That would be extra easy.
Tại sao? Có thể là tôi đã quan sát được x1. Vậy thì càng dễ.
But maybe I know it because it's given to me on the first time step as a known in the problem, or maybe I've already done inference up to this point.
Hoặc có thể tôi biết vì nó được cho sẵn ở bước thời gian đầu như một dữ kiện của bài toán, hoặc có thể tôi đã suy luận xong đến thời điểm này.
And I know it conditionally on some evidence, which isn't shown here. We'll expand this based case to condition on evidence as well.
Và tôi biết nó có điều kiện theo một số bằng chứng, mà ở đây không ghi ra. Ta sẽ mở rộng trường hợp cơ sở này để có điều kiện theo bằng chứng.
But let's say I'd like to know p of x2, but what I'm given is p of x1. How am I going to do that?
Giả sử tôi muốn biết P của x2, nhưng cái được cho là P của x1. Làm sao đây?
Well, the way I'm going to do that is I'm going to break that into two steps.
Cách làm là tách thành hai bước.
And the first one I say, well, for any given value of x2, p of x2, I can rewrite that as p of x1, x2. Remember x1 is for the first time step.
Bước đầu, với bất kỳ giá trị nào của x2, tôi có thể viết lại P của x2 thành P của x1, x2. Nhớ x1 là của bước thời gian đầu.
X2 is for the second time step summed out over x1.
X2 là của bước thời gian thứ hai, lấy tổng theo x1.
So this rewrite here that says p of x2 equals p of x1, comma, x2, summed over x1, whenever I write something like this, what you should be thinking is, why was this allowed?
Phép viết lại này: P của x2 bằng tổng theo x1 của P của x1, x2. Mỗi khi em viết thứ như vậy, hãy tự hỏi: tại sao được phép viết thế?
Otherwise, you start to get to feel like you can throw in variables and commas and conditioning bars everywhere and sum things out and whatever you write is going to be true.
Nếu không, em sẽ có cảm giác có thể thêm biến, dấu phẩy, dấu điều kiện khắp nơi rồi lấy tổng, và viết gì cũng đúng. Không phải vậy.
That's not true. Almost anything you can write about probabilities will be false. Why is this one true?
Điều đó không đúng. Hầu như mọi thứ em viết về xác suất đều sẽ sai. Vậy sao cái này đúng?
You want to think is that because of something I know about an HMM, or is that just laws of probability? What's this one? This is just laws of probability.
Hãy nghĩ xem đó là do tính chất nào đó của HMM hay chỉ là các luật xác suất? Còn cái này thì sao? Đây chỉ là các luật xác suất.
You can always take any p of a, and say, hey, that's the same as p of a, comma, b if I sum out all the values of b and whatever random variable b belongs to.
Em luôn có thể lấy P của a và nói nó bằng P của a, b lấy tổng trên mọi giá trị của b, với b thuộc biến ngẫu nhiên nào đó. mà b thuộc về.
That's always true. OK, that's introducing a variable and marginalizing out at the same time. All right, well, how does that help you?
Điều đó luôn đúng. Đó là vừa đưa thêm biến vào vừa lấy biên nó ra. Vậy điều này giúp ích gì?
Well, that helps you because p of x1, comma, x2, that is the probability of x1 happening and then x2 happening, is just the probability of x1 happening in the first place, which remember we know something about, and the probability of x2 given x1, which is an element of the transition probability that was given to us when we were handed this hidden Markov model, or in this case, just Markov model.
Nó giúp vì P của x1, x2, tức xác suất x1 xảy ra rồi sau đó x2 xảy ra, chính là xác suất x1 xảy ra ngay từ đầu, mà ta biết một chút về nó, nhân với xác suất của x2 cho trước x1, đó là một phần tử của xác suất chuyển được cho khi ta được đưa mô hình Markov ẩn này, hay ở đây chỉ là mô hình Markov.
OK. So when can I do this? I look at this and I say, is this because of a property of an HMM, or is this because of a law of probability?
OK. Vậy khi nào tôi làm được điều này? Tôi nhìn và hỏi: đây là do tính chất của HMM hay do luật xác suất?
In this case, this is just the law of probability. When we do this in general with evidence, we're going to need to know conditional independence properties from the HMM.
Trường hợp này chỉ là luật xác suất. Khi làm điều này nói chung với bằng chứng, ta sẽ cần biết các tính chất độc lập có điều kiện của HMM.
But right here, I've just written here the chain rule in its simplest form, the product rule. All right, so what does this mean?
Nhưng ở đây tôi chỉ viết quy tắc chuỗi ở dạng đơn giản nhất, quy tắc tích. Vậy điều này có nghĩa là gì?
This means that if I know the probability of and I'd like the probability distribution over x2, for each value of x2, I say, well, you had to come from somewhere.
Nghĩa là nếu tôi biết xác suất của và tôi muốn phân phối xác suất của x2, thì với mỗi giá trị của x2, tôi nói rằng nó phải đến từ đâu đó.
You had to come from some x1. I know how likely each x1 is.
Nó phải đến từ một x1 nào đó. Tôi biết mỗi x1 có khả năng bao nhiêu.
So I write the probability that you started at that particular x1 and then went to our current value of x2 we're considering from there.
Nên tôi viết xác suất để bạn xuất phát từ x1 cụ thể đó, rồi đi đến giá trị x2 hiện tại mà ta đang xét.
So these are all the ways you can end up in x2. You can start at this x1, that x1, that x1, and then transition here. And then you repeat this computation for every x2.
Đây là tất cả các cách để bạn kết thúc ở x2. Bạn có thể xuất phát từ x1 này, x1 kia, x1 nọ, rồi chuyển đến đây. Rồi bạn lặp lại phép tính này cho mọi x2.
OK? So the transition probabilities say, hey, if your ghost was here at x1, here's all the places it could be at x2.
OK? Vậy xác suất chuyển nói rằng, nếu con ma đang ở x1 này, thì đây là mọi chỗ nó có thể ở tại x2.
But this computation says, hey, what's the likelihood that the ghost will be here at x2. And then you consider, well, you could've started here. You could've started here.
Còn phép tính này nói rằng, khả năng con ma ở đây tại x2 là bao nhiêu. Rồi bạn xét, nó có thể đã xuất phát từ đây. Có thể từ đây.
You could've started here. You could've have started here. And you compute all the ways of getting to that x2.
Có thể từ đây. Có thể từ đây. Và bạn tính mọi cách để đến x2 đó.
And for each one, you weight it by the probability of being there at x1 times the transition probability.
Với mỗi cách, bạn nhân trọng số là xác suất ở x1 nhân với xác suất chuyển.
This idea that you think about all the ways to get to a certain state by considering the ways you could have gotten there, that's going to be the backing of the dynamic programs like the forward algorithm, which you saw quickly last lecture.
Ý tưởng xét mọi cách để đến một trạng thái bằng cách xem xét những đường có thể đã dẫn tới đó, chính là nền tảng của các thuật toán quy hoạch động như thuật toán forward, mà bạn đã thoáng thấy ở bài trước.
OK, any questions about that? All right, so that we wrote basically without using the fact that this was a Markov model or a hidden Markov model.
OK, có câu hỏi nào về phần này không? Được rồi, vậy ta đã viết điều đó mà về cơ bản không dùng việc đây là mô hình Markov hay mô hình Markov ẩn.
The hidden part won't show up until we have evidence.
Phần ẩn chỉ xuất hiện khi ta có bằng chứng.
So we're going to have to use somewhere the conditional independence of a Markov model, which says that the past is conditionally independent of the future given the present.
Nên ở đâu đó ta sẽ phải dùng tính độc lập có điều kiện của mô hình Markov, tức là quá khứ độc lập có điều kiện với tương lai khi biết hiện tại.
All right, so let's say we know something other than p of x1. Let's say we have a belief about xt. Say, what's b? OK, this is just shorthand.
Được rồi, giả sử ta biết thứ khác ngoài p của x1. Giả sử ta có một belief về xt. Gọi nó là b. OK, đây chỉ là ký hiệu tắt.
It's actually kind of sloppy shorthand that people use to indicate that this is a belief about variable xt.
Thật ra là cách viết tắt hơi cẩu thả mà người ta dùng để chỉ rằng đây là belief về biến xt.
But with a probability, when I write p, I have to be very, very careful what I condition about. Because p of xt, that's a marginal probability of xt.
Nhưng với xác suất, khi tôi viết p, tôi phải rất cẩn thận về điều kiện. Vì p của xt là xác suất biên của xt.
P of xt given e1 through t, that's a conditional probability condition on the evidence. They are not the same. With belief distributions, when I write b, sometimes I'm sloppy.
P của xt cho e1 đến t là xác suất có điều kiện theo bằng chứng. Hai thứ này không giống nhau. Với phân phối belief, khi tôi viết b, đôi khi tôi viết cẩu thả.
If you're ever confused on homework or exam and it's not clear in the context, please ask.
Nếu bạn bối rối ở bài tập hay kỳ thi và ngữ cảnh không rõ, cứ hỏi nhé.
But here on the slide, imagine we have a belief over xt, which is equal to some already computed conditional probability over xt given the evidence up to time t.
Nhưng trên slide này, hãy tưởng tượng ta có belief về xt, bằng một xác suất có điều kiện đã tính sẵn của xt cho bằng chứng đến thời điểm t.
So I've been tracking the ghost. Here is the probability. All right, then I want to know what should my belief look like after one more time step. Well, what is that?
Tức là tôi đã theo dõi con ma. Đây là xác suất. Được rồi, giờ tôi muốn biết belief nên trông thế nào sau thêm một bước thời gian. Vậy nó là gì?
As a probability, I now want to compute the distribution not over xt, which I already know. So this thing here in the box, that's known.
Về xác suất, giờ tôi muốn tính phân phối không phải của xt, cái đã biết rồi. Cái trong khung này là đã biết.
That's sitting there in a vector in memory ready to be accessed.
Nó nằm sẵn trong một vectơ trong bộ nhớ, sẵn sàng truy cập.
I'd now like to compute given the same evidence, e1 through t, I'd like to compute the probability distribution over x at time t plus one. What does this look like visually?
Giờ tôi muốn tính, với cùng bằng chứng e1 đến t, phân phối xác suất của x tại thời điểm t cộng một. Nhìn trực quan thì nó ra sao?
This looks like I have a hidden Markov model here, so now evidence is coming into it. I have a hidden Markov model. Here is x1. This went all the way up to xt.
Ta có một mô hình Markov ẩn ở đây, và bằng chứng đang đến. Ta có một mô hình Markov ẩn. Đây là x1. Kéo dài đến xt.
There was evidence at each time step. So there's all this evidence. Here's evidence one all the way up to evidence t.
Mỗi bước thời gian đều có bằng chứng. Vậy có toàn bộ bằng chứng này. Đây là bằng chứng một cho đến bằng chứng t.
All the evidence is shaded, so I know all those nodes down there. And I currently have the probability over that node. What is going on with the ghost right now at time t?
Mọi bằng chứng đều được tô bóng, nên tôi biết các nút ở dưới đó. Và hiện tôi có xác suất trên nút đó. Con ma đang ở đâu ngay lúc này, thời điểm t?
And what I'd like to do is I'd like to project that forward time step to xt plus one without observing any new evidence. The evidence will come. So time is going to pass.
Và điều tôi muốn là đẩy nó tiến một bước thời gian tới xt cộng một mà không quan sát thêm bằng chứng mới. Bằng chứng sẽ đến sau. Nên thời gian sẽ trôi.
I'd like to compute this new conditional probability. How am I going to do it?
Tôi muốn tính xác suất có điều kiện mới này. Tôi sẽ làm thế nào?
I'm going to write down a bunch of conditional probability statements that are licensed either by the laws of probability or by something I know about hidden Markov model's conditional independence until I can reduce the thing I'm looking for in blue, which I don't know, to some computation involving known things.
Tôi sẽ viết ra một loạt phát biểu xác suất có điều kiện được phép nhờ các luật xác suất hoặc nhờ điều tôi biết về tính độc lập có điều kiện của mô hình Markov ẩn cho đến khi đưa được cái tôi cần tìm, màu xanh, mà tôi chưa biết, về một phép tính dùng những thứ đã biết.
So the first thing I can do is I can introduce this variable xt. I'm curious about the value at t plus one.
Việc đầu tiên là tôi có thể đưa vào biến xt. Tôi quan tâm giá trị tại t cộng một.
I can throw in the value at xt and sum it out at the same time. This is just introducing a variable. So xt popped in here, and it got summed up.
Tôi có thể thêm giá trị xt vào và đồng thời lấy tổng theo nó. Đây chỉ là đưa thêm một biến. Vậy xt xuất hiện ở đây và được lấy tổng.
The next thing I can do is I can pull out, I can decompose this conditional probability.
Việc tiếp theo là tôi có thể tách xác suất có điều kiện này.
I can say the probability given my evidence one through t of generating xt and then xt plus one is just the probability of generating xt.
Tôi có thể nói xác suất, cho bằng chứng một đến t, của việc sinh ra xt rồi xt cộng một chính là xác suất sinh ra xt.
And then once I've done that, generating xt plus one. This isn't exactly how you usually see the chain rule, but this is also just true from the laws of probability.
Rồi sau đó, sinh ra xt cộng một. Đây không đúng như cách bạn thường thấy quy tắc chuỗi, nhưng nó cũng đúng theo các luật xác suất.
If you write all these conditional probabilities, everything will cancel out. So far, what have I accomplished? I've done some manipulation.
Nếu bạn viết hết các xác suất có điều kiện này, mọi thứ sẽ triệt tiêu. Đến giờ tôi đã đạt được gì? Tôi đã biến đổi một chút.
And this value that I already know, which is the distribution at time t given the evidence up to t, has appeared, and now I can plug those in.
Và giá trị mà tôi đã biết, là phân phối tại thời điểm t cho bằng chứng đến t, đã xuất hiện, và giờ tôi có thể thay vào.
I don't need to simplify that anymore.
Tôi không cần đơn giản hóa nó thêm nữa.
But this part over here, the probability distribution of xt plus one given xt and e of one to t, this still needs to be simplified, because this is not provided by my hidden Markov model.
Nhưng phần ở đây, phân phối xác suất của xt cộng một cho xt và e từ một đến t, phần này vẫn cần được đơn giản hóa, vì mô hình Markov ẩn của ta không cho sẵn nó.
However, what my hidden Markov tells me is that xt is conditionally independent of all evidence before it given xt plus one. And that lets me simplify that expression down to a transition probability.
Tuy nhiên, điều mà mô hình Markov ẩn cho ta biết là xt độc lập có điều kiện với mọi bằng chứng trước đó, khi đã biết xt cộng một. Và điều đó cho phép ta đơn giản biểu thức này thành xác suất chuyển.
So this says something pretty intuitive.
Điều này khá trực quan.
It says, if you want to know how likely it is, given some fixed evidence, of being at sum xt plus one, you just think, what are all the different ways I could have gotten there?
Nó nói rằng, nếu bạn muốn biết khả năng ở một xt cộng một nào đó là bao nhiêu, với bằng chứng cố định cho trước, bạn chỉ cần nghĩ xem có những cách nào để đến được đó?
Well, I had to be somewhere at the previous time step xt. So I'm trying to figure out how likely is it to get to xt plus one.
Ở bước thời gian trước, tôi phải ở đâu đó là xt. Nên tôi đang cố tìm xem khả năng đến xt cộng một là bao nhiêu.
So I think of all the ways I could have gotten there. I could have been at all these different values for xt. Each one has this probability given the evidence.
Tôi nghĩ đến mọi cách mà tôi có thể đến được đó. Tôi có thể đã ở bất kỳ giá trị nào của xt. Mỗi giá trị có một xác suất cho trước bằng chứng.
And then the probability of doing that transition is the transition probability. So I had to start at a certain place. I had to transition to my current xt plus one.
Và xác suất thực hiện bước chuyển đó chính là xác suất chuyển. Tức là tôi phải xuất phát từ một chỗ nào đó. Tôi phải chuyển sang xt cộng một hiện tại.
And then, I'm done. I add those up. All right, so to write that compactly, you'll sometimes see something like this.
Và thế là xong. Tôi cộng tất cả lại. Được rồi, để viết gọn lại, đôi khi bạn sẽ thấy dạng như thế này.
This says, if I have a belief distribution, yes, it's conditioned on the evidence, yes, I didn't write that out, for time t. And I'd like to know the belief at time t plus one.
Nó nói rằng, nếu tôi có một phân phối niềm tin, đúng, nó có điều kiện theo bằng chứng, đúng, tôi không viết ra, tại thời điểm t. Và tôi muốn biết niềm tin tại thời điểm t cộng một.
Without any new evidence, I just take that old belief distribution, and I multiply it by the transition probabilities and add things up appropriately.
Nếu không có bằng chứng mới, tôi lấy phân phối niềm tin cũ nhân với các xác suất chuyển rồi cộng lại một cách thích hợp.
This is sometimes called b of xt through the dynamics. Yep?
Đôi khi người ta gọi đây là b của xt qua động lực học. Vâng?
Why do we have this b prime?
Sao ở đây lại có b phẩy?
Oh, yeah. xt plus one. Yeah. Sloppy PowerPoint.
À, đúng rồi. xt cộng một. Vâng. Slide PowerPoint làm ẩu.
Sorry. xt plus one would be more correct. Thank you. All right, so the basic idea here is you have some belief distribution, and it gets pushed through the transition.
Xin lỗi. xt cộng một mới đúng hơn. Cảm ơn bạn. Được rồi, ý tưởng cơ bản ở đây là bạn có một phân phối niềm tin, và nó được đẩy qua phép chuyển.
If you actually knew where the ghost was, if you knew the value of x at time t, it would be just the transition probability from there.
Nếu bạn thực sự biết con ma ở đâu, tức biết giá trị của x tại thời điểm t, thì chỉ cần xác suất chuyển từ vị trí đó.
But since you don't know, you get a superposition of those transition probabilities weighted by the likelihood. All right, so what happens as time passes in the absence of any observation?
Nhưng vì không biết, bạn có một chồng chập các xác suất chuyển đó, có trọng số theo khả năng xảy ra. Vậy điều gì xảy ra khi thời gian trôi mà không có quan sát nào?
As time passes, uncertainty accumulates.
Thời gian trôi qua, độ bất định tích lũy.
So even if you knew exactly where that ghost was or the exact value of variable xt, if time starts to pass, well, after one time step, even if you know the value of xt, at the next time step, all you know is where it would go.
Dù bạn biết chính xác con ma ở đâu hay giá trị chính xác của biến xt, khi thời gian trôi, sau một bước, dù bạn biết giá trị xt, ở bước kế tiếp bạn chỉ biết nó có thể đi đâu.
And so the sharper your transition probabilities are, the more deterministic they are, the more you're going to know after a time step. But there's a lot of things that could happen.
Và xác suất chuyển càng sắc nét, càng tất định, thì sau một bước bạn càng biết nhiều. Nhưng có rất nhiều điều có thể xảy ra.
Even after one time step, you're starting to be unsure. And if you push things, five, 10, 100 steps into the future, you stop being as certain as you were, because of the simulation.
Ngay sau một bước, bạn đã bắt đầu không chắc chắn. Và nếu đẩy tới năm, 10, 100 bước trong tương lai, bạn không còn chắc chắn như trước, vì phép mô phỏng.
This is a general tendency. Is it possible to be uncertain, and then let time pass and have your certainty increase? It's definitely possible.
Đây là một xu hướng chung. Có thể đang bất định, rồi để thời gian trôi mà độ chắc chắn tăng lên không? Hoàn toàn có thể.
If I had transition probabilities that said that wherever you are, you go towards the lower right corner. And I said, the ghost is somewhere. I don't know where, uniform probability.
Nếu xác suất chuyển nói rằng dù bạn ở đâu, bạn cũng đi về góc dưới bên phải. góc. Và tôi nói, con ma ở đâu đó. Tôi không biết ở đâu, xác suất đều.
Right? It would say 0.2 everywhere or whatever. And then if I advanced time, that probability would slowly push itself into the corner.
Đúng không? Mỗi chỗ là 0.2 hay gì đó. Rồi nếu tôi cho thời gian trôi, xác suất đó sẽ dần dồn vào góc.
And after 1,000 times steps, I would be sure that by now surely the ghost had made it to the corner.
Và sau 1.000 bước, tôi sẽ chắc chắn rằng giờ này con ma hẳn đã đến góc.
So there are transition probabilities for which the stationary distribution, which is basically what this is computing, is actually very peaked even if you don't have a sharp transition, even if you don't have a sharp initial probability distribution.
Vậy có những xác suất chuyển mà phân phối dừng, về cơ bản là thứ đang được tính ở đây, về cơ bản chính là thứ mà phần này đang tính, lại rất nhọn, dù bạn không có phép chuyển sắc nét, dù bạn không có phân phối xác suất ban đầu sắc nét.
Normally, it goes the other way. Normally, you have some knowledge, and it decays over time.
Thông thường thì ngược lại. Thông thường bạn có một ít hiểu biết, và nó phai dần theo thời gian.
And so the picture here is more like you have your robot, and it starts off with some clear sensor reading.
Hình ảnh ở đây giống như bạn có một con robot, ban đầu nó có số đọc cảm biến rõ ràng.
And if some time passes without any more sensor readings, it gets a little confused. And then if enough time happens, it has no idea. We saw that in Ghostbusters as well.
Nếu thời gian trôi mà không có thêm số đọc cảm biến nào, nó bắt đầu hơi bối rối. Và nếu đủ lâu, nó hoàn toàn không biết gì. Chúng ta cũng đã thấy điều đó trong Ghostbusters.
OK, here's the other base case, and then we'll translate these into this new particle filtering algorithm. The other base case is I have some probability.
Được rồi, đây là trường hợp cơ sở còn lại, rồi ta sẽ chuyển những điều này thành thuật toán lọc hạt mới. Trường hợp cơ sở còn lại là tôi có một xác suất nào đó.
So here, we imagine the known is p of x1. I have some distribution over a random variable, like the ghost position. Maybe it's conditioned on a bunch of evidence.
Ở đây, ta hình dung cái đã biết là p của x1. Tôi có một phân phối trên một biến ngẫu nhiên, như vị trí con ma. Có thể nó có điều kiện theo một loạt bằng chứng.
We'll get the evidence here in a couple slides. But I currently have a belief distribution and evidence comes in.
Vài slide nữa ta sẽ có bằng chứng. Nhưng hiện tôi có một phân phối niềm tin và bằng chứng đến.
When time passes, I take my belief distribution and I reshape it through the dynamics, which in a fuzzy way pushes it forward through that transition probability.
Khi thời gian trôi, tôi lấy phân phối niềm tin và định hình lại qua động lực học, theo cách mờ đẩy nó tiến lên qua xác suất chuyển đó.
Here, time isn't passing, but I'm going to get some evidence. So I'm going to go from p of x, which is a known quantity, and try to compute p of x given some evidence.
Ở đây thời gian không trôi, nhưng tôi sẽ nhận được bằng chứng. Vậy tôi đi từ p của x, là đại lượng đã biết, và cố tính p của x cho trước một bằng chứng.
Well, in a way, this is easier. And in a way, it's more complicated. It's easier in that we're still going to work with x1.
Về một mặt, cái này dễ hơn. Về mặt khác, nó phức tạp hơn. Dễ hơn ở chỗ ta vẫn làm việc với x1.
All we have to do is figure out how the evidence reshapes our beliefs, and this should be fairly intuitive.
Ta chỉ cần tìm xem bằng chứng định hình lại niềm tin của ta như thế nào, và điều này khá trực quan.
Because if I'm not sure where in this room my robot is, and it takes a, I don't know, how close am I to the wall reading, and it gets really close, suddenly, I don't think it's in the middle of the room anymore.
Vì nếu tôi không chắc robot của mình đang ở đâu trong căn phòng này, và nó đo, ví dụ, khoảng cách từ tôi đến bức tường, và kết quả là rất gần, thì đột nhiên tôi không còn nghĩ nó ở giữa phòng nữa.
So evidence should reshape my probabilities, and it should do it in an intuitive way. When I get evidence, the underlying states x that are more compatible with that evidence should come to dominate.
Vậy bằng chứng phải định hình lại xác suất của tôi, và phải làm điều đó một cách trực quan. Khi tôi nhận được bằng chứng, các trạng thái x bên dưới mà phù hợp hơn với bằng chứng đó sẽ trở nên chiếm ưu thế.
How exactly does that work is a little more complicated, because there's some renormalization involved.
Chính xác thì việc đó diễn ra thế nào thì phức tạp hơn một chút, vì có liên quan đến việc chuẩn hóa lại.
So again, we're going to use the laws of probability to rewrite x1 given e1 in terms of the things we actually know. In this case, we know p of x1.
Vậy một lần nữa, ta sẽ dùng các quy tắc xác suất để viết lại x1 cho trước e1 theo những đại lượng ta thực sự biết. Trong trường hợp này, ta biết p của x1.
And we know the evidence probability, so we know p of e given x. OK, the HMM gives you that. All right, so let's write that out. OK, that's too much.
Và ta biết xác suất của bằng chứng, tức là biết p của e cho trước x. HMM cho ta những thứ đó. Được rồi, ta viết ra nhé. À, viết thế này nhiều quá.
Probability of some x1 given e1. Well, I can rewrite that as the joint probability of x1 and e1 divided by the total probability of the evidence e1.
Xác suất của x1 nào đó cho trước e1. Ta có thể viết lại thành xác suất đồng thời của x1 và e1 chia cho tổng xác suất của bằng chứng e1.
This step, just the law of probability. This is the definition of conditional probability. All right, well, how does that help us?
Bước này chỉ là quy tắc xác suất. Đây là định nghĩa của xác suất có điều kiện. Vậy điều này giúp ích gì cho ta?
This helps us because to compute p of capital X1, that's going to be a vector. I'm going to get a probability of each and every value x1 could take on given e1.
Nó giúp vì để tính p của X1 viết hoa, đó sẽ là một vectơ. Tôi sẽ có xác suất cho từng giá trị mà x1 có thể nhận, cho trước e1.
And so I'm going to do the same computation for every single x1, which means I can ignore this constant, because this constant is present for each value of x1.
Và tôi sẽ thực hiện cùng một phép tính cho mọi x1, nghĩa là tôi có thể bỏ qua hằng số này, vì hằng số này có mặt ở mọi giá trị của x1.
And I can do the computation being off by that constant and then renormalize at the end.
Tôi có thể tính sai khác hằng số đó rồi chuẩn hóa lại ở cuối.
So what that means is it's actually enough to compute the joint probability of x1 and the evidence, provided I do that for every value of x1 and then renormalize.
Nghĩa là chỉ cần tính xác suất đồng thời của x1 và bằng chứng, với điều kiện làm cho mọi giá trị của x1 rồi chuẩn hóa lại.
And the probability of x1 and the evidence is just the probability of x1, which I already know, that was a given, times the probability of the evidence given x1.
Và xác suất của x1 và bằng chứng chính là xác suất của x1, cái ta đã biết, vì nó được cho sẵn, nhân với xác suất của bằng chứng cho trước x1.
This has a fairly intuitive interpretation as well. This says, for each position x1, each value of x, x1, they get weighted by the probability of the evidence given that underlying state.
Điều này cũng có cách diễn giải khá trực quan. Nó nói rằng, với mỗi vị trí x1, mỗi giá trị của x, x1, đều được đánh trọng số bằng xác suất của bằng chứng cho trước trạng thái bên dưới đó.
So if e1 is likely given x1, this doesn't change very much. If e1 is very unlikely, this p of x1 will then be reduced to a very small number.
Nếu e1 có khả năng cao khi cho trước x1 thì giá trị này không đổi nhiều. Nếu e1 rất khó xảy ra, thì p của x1 này sẽ bị giảm xuống còn rất nhỏ.
Each p of x1 gets reduced. Some get reduced more than others. And then you renormalize. And the ones that were reduced less in proportion will grow.
Mỗi p của x1 đều bị giảm. Có cái giảm nhiều hơn cái khác. Rồi bạn chuẩn hóa lại. Và những giá trị bị giảm ít hơn theo tỉ lệ sẽ tăng lên.
This is why that robot, if I have some distribution that at sums to one over robot positions, let's say it's flat over this whole room, and I get a sensor reading saying the wall is nearby, all of the positions for which wall is nearby is likely would have their joint probabilities be fairly close to just p of x1.
Đó là lý do với robot, nếu tôi có một phân phối có tổng bằng một trên các vị trí của robot, giả sử nó phẳng trên toàn căn phòng này, và tôi nhận được số đo cảm biến nói tường ở gần, thì mọi vị trí mà tường ở gần là có khả năng sẽ có xác suất đồng thời khá gần với p của x1.
All of the positions in the center would have their joint probabilities very close to zero.
Mọi vị trí ở giữa phòng sẽ có xác suất đồng thời rất gần bằng không.
And then when I renormalize, all those probabilities that are towards the walls will then go up, because we divide by sums number that's less than one. All right, so that's the key bit.
Rồi khi tôi chuẩn hóa lại, mọi xác suất ở các vị trí gần tường sẽ tăng lên, vì ta chia cho một tổng nhỏ hơn một. Đó là ý chính.
Now I'll write it out here, but some of these equations are easier to go through on your own mechanically. So here's how observation works. Imagine you have some current belief distribution.
Giờ tôi sẽ viết ra đây, nhưng một số phương trình bạn nên tự mình làm từng bước thì dễ hiểu hơn. Đây là cách cập nhật quan sát hoạt động. Hãy tưởng tượng bạn có một phân phối niềm tin hiện tại.
You have p of x given some previous evidence.
Bạn có p của x cho trước một số bằng chứng trước đó.
So for example, we might have a belief distribution over the value x takes on at time t plus one given all the evidence up to t, but not including t plus one's evidence.
Ví dụ, ta có thể có một phân phối niềm tin trên giá trị x nhận tại thời điểm t cộng một cho trước mọi bằng chứng đến t, nhưng không gồm bằng chứng của t cộng một.
This is actually just the same if you're getting multiple readings of evidence at the same time. You can modify the Bayes net for that as well. You get the same update.
Điều này thực ra y hệt nếu bạn nhận nhiều số đo bằng chứng cùng lúc. Bạn cũng có thể sửa mạng Bayes cho trường hợp đó. Bạn có cùng một phép cập nhật.
And so we have this b prime, which is a belief over xt plus one, but it doesn't take into account the current evidence.
Vậy ta có b phẩy này, là niềm tin về xt cộng một, nhưng nó chưa tính đến bằng chứng hiện tại.
And we're going to update it by feeding it evidence at the current time step. So we're going to feed it e of t plus one. So evidence comes in.
Và ta sẽ cập nhật nó bằng cách đưa vào bằng chứng ở bước thời gian hiện tại. Tức là ta đưa vào e của t cộng một. Vậy bằng chứng đến.
And now, I want to compute what's the probability distribution over t plus one given my old evidence, but also e of t plus one.
Và giờ tôi muốn tính phân phối xác suất trên t cộng một cho trước bằng chứng cũ, và cả e của t cộng một.
So that evidence chain is now longer. So I can write that out.
Vậy chuỗi bằng chứng giờ dài hơn. Tôi có thể viết ra.
I can say, well, what that is is I can shuffle some conditional probabilities here and say, that is up to this constant here, that is the probability given it's proportional to the probability of the old evidence and then xt plus one happening and then
Tôi có thể nói rằng, điều đó là ta xáo trộn một số xác suất có điều kiện ở đây và nói, sai khác hằng số này, đó là xác suất, tỉ lệ thuận với xác suất của bằng chứng cũ rồi xt cộng một xảy ra và sau đó
the new evidence happening. And so if I write that out, I can remove the constant, because it's constant overall values of xt plus one, as long as I renormalize later.
bằng chứng mới xảy ra. Và nếu viết ra, tôi có thể bỏ hằng số, vì nó là hằng số trên mọi giá trị của xt cộng một, miễn là tôi chuẩn hóa lại sau.
And now, I'm computing the probability distribution given the old evidence, the evidence from time one to t, the probability that, first, I transition to x xt plus one and then I observe evidence e of t plus one.
Và giờ tôi đang tính phân phối xác suất cho trước bằng chứng cũ, bằng chứng từ thời điểm một đến t, xác suất rằng trước tiên tôi chuyển sang xt cộng một rồi tôi quan sát bằng chứng e của t cộng một.
OK? What's that? That is the probability given the same evidence that, first, I transition to xt plus one.
Được chứ? Đó là gì? Đó là xác suất, cho trước cùng bằng chứng, rằng trước tiên tôi chuyển sang xt cộng một.
And then given that I've done that, I observe the new evidence. This here is a known. This is here. So I don't have to simplify that any further.
Rồi cho trước việc tôi đã làm vậy, tôi quan sát bằng chứng mới. Cái này ở đây là đã biết. Nó ở đây. Nên tôi không cần đơn giản hóa thêm nữa.
I've said, my new belief distribution is actually just my old belief distribution times this quantity here, that I still have to simplify, and then renormalized. All right, let's re normalize that.
Tôi đã nói, phân phối niềm tin mới của tôi thực ra chỉ là phân phối niềm tin cũ nhân với đại lượng này, mà tôi vẫn phải đơn giản hóa, rồi chuẩn hóa lại. Được rồi, ta chuẩn hóa lại nhé.
Let's simplify that quantity. This is the probability of the new evidence given xt plus one and the old evidence. Well, in the hidden Markov model, the old evidence doesn't matter.
Hãy đơn giản hóa đại lượng đó. Đây là xác suất của bằng chứng mới cho trước xt cộng một và các bằng chứng cũ. Trong mô hình Markov ẩn, bằng chứng cũ không quan trọng.
And so I get the simpler statement, which now has this very intuitive form, which says, if you want to include the new evidence at t plus one, you take your belief distribution not including that evidence, you weight every term in that distribution by the conditional probability of the evidence.
Nên ta có biểu thức đơn giản hơn, và nó có dạng rất trực quan, nói rằng: nếu muốn đưa bằng chứng mới tại thời điểm t cộng một vào, bạn lấy phân phối niềm tin chưa tính bằng chứng đó, rồi gán trọng số cho từng số hạng trong phân phối bằng xác suất có điều kiện của bằng chứng.
Now, it's not going to be a probability distribution anymore.
Lúc này nó sẽ không còn là một phân phối xác suất nữa.
Because where it was a p of xt plus one, now, it is a p of xt plus one and your evidence t plus one given all of your other evidence.
Vì trước đây là p của xt cộng một, giờ nó là p của xt cộng một và bằng chứng t cộng một, cho trước tất cả các bằng chứng còn lại.
But then if you renormalize, that transfers this to the other side of the conditioning bar. And now, you have a belief distribution again.
Nhưng nếu chuẩn hóa lại, thì nó chuyển bằng chứng sang bên kia dấu điều kiện. Và bạn lại có một phân phối niềm tin.
So compactly, you could write this as the new belief distribution — whoops, unexpected — the new belief distribution is the old belief distribution weighted by the evidence and then renormalized.
Viết gọn lại, phân phối niềm tin mới — ối, ngoài ý muốn — phân phối niềm tin mới là phân phối niềm tin cũ nhân trọng số của bằng chứng rồi chuẩn hóa lại.
And that makes sense, because you believe what you used to believe except the evidence shifts things. And then your beliefs still have to sum to one.
Điều này hợp lý, vì bạn vẫn tin những gì đã tin, chỉ là bằng chứng làm dịch chuyển chúng. các thứ. Và niềm tin của bạn vẫn phải có tổng bằng một.
So all that stuff that got deleted because it was incompatible with the evidence, that probability just moves over proportionately to the other events.
Vậy những thứ bị loại bỏ vì không phù hợp với bằng chứng, xác suất của chúng được chuyển sang các sự kiện khác theo tỉ lệ.
OK.
OK.
There's a key piece here, which is unlike — both of these basic operations, which are the building blocks of all these inference procedures, have a simple intuitive interpretation.
Có một điểm mấu chốt ở đây, khác với — cả hai phép toán cơ bản này, là những khối xây dựng của mọi thủ tục suy luận, đều có cách diễn giải trực quan đơn giản.
Passage of time is you take your vector and you move it through the dynamics. Easy. Observation is tricky.
Thời gian trôi qua nghĩa là bạn lấy vectơ của mình và đưa nó qua động học. Dễ. Dễ. Quan sát thì khó hơn.
It makes sense that you should weight all of the different outcomes by the evidence, but then you have to renormalize, and that's the part that's a little less intuitive.
Hợp lý khi bạn gán trọng số cho mọi kết quả khác nhau theo bằng chứng, nhưng sau đó phải chuẩn hóa lại, và phần đó kém trực quan hơn một chút.
And that will also be less intuitive in terms of how it shows up in the algorithm.
Nó cũng sẽ kém trực quan khi xuất hiện trong thuật toán.
It's going to show up as a step either in the forward algorithm or in the particle filtering algorithm where it might be less obvious why you're doing a certain thing.
Nó sẽ xuất hiện như một bước trong thuật toán forward hoặc trong thuật toán lọc hạt, nơi có thể khó thấy vì sao bạn lại làm một việc nào đó.
And we'll see that in a minute here.
Chúng ta sẽ thấy ngay sau đây.
So here's an example. I can pull up the app and do this in the app. You'll see these in your projects as well. As we get observations, what happens?
Đây là một ví dụ. Tôi có thể mở ứng dụng và làm ngay trong đó. Các bạn cũng sẽ thấy cái này trong project. Khi có quan sát thì chuyện gì xảy ra?
Your beliefs get reweighted. And the caricature is, typically, you're sort of a little confused. And then some evidence comes in, and you're a little bit less confused.
Niềm tin của bạn được đánh trọng số lại. Nói một cách biếm họa, thường thì bạn hơi bối rối. Rồi có bằng chứng đến, và bạn bớt bối rối hơn một chút.
So let me see if I can make this happen on the — let's see if I can have it here. So right now, I'm maximally confused.
Để xem tôi có làm nó xảy ra được không — xem có làm được ở đây không. Hiện giờ tôi bối rối tối đa.
If I get some evidence, I'm less confused. I still don't know where the ghost is, but my belief distribution is concentrated on this diamond now.
Nếu có thêm bằng chứng, tôi bớt bối rối. Tôi vẫn chưa biết con ma ở đâu, nhưng phân phối niềm tin giờ tập trung vào ô kim cương này .
Now if I get more evidence, what will typically happen is my posterior distribution will sharpen, and it did. Now my belief is concentrated on these six squares. Let's see if it sharpens again.
Nếu có thêm bằng chứng, thường thì phân phối hậu nghiệm sẽ sắc nét hơn, và đúng vậy. Giờ niềm tin tập trung vào sáu ô này. Xem nó có sắc nét hơn nữa không.
OK, it sharpened. Sharpened. Sharpened. Thank you random number generator.
OK, sắc nét hơn rồi. Sắc nét hơn. Sắc nét hơn. Cảm ơn bộ sinh số ngẫu nhiên.
That's what normally happens.
Đó là điều thường xảy ra.
If you play with this app enough, you can do this in your projects, what you'll see is every now and then, you get some evidence, which is actually inconsistent with your current beliefs.
Nếu chơi với ứng dụng này đủ lâu, các bạn cũng làm được trong project, các bạn sẽ thấy thỉnh thoảng có bằng chứng đến mà thực ra mâu thuẫn với niềm tin hiện tại.
And that actually causes you to become a little more confused. Because some things that you thought were unlikely, now, they seem actually a little bit more likely.
Và điều đó khiến bạn bối rối hơn một chút. Vì những thứ bạn từng nghĩ là khó xảy ra giờ lại có vẻ khả dĩ hơn một chút.
And those things that you were sure of, they don't really match all the evidence anymore. And so it's possible for evidence to come in and for you to get more confused.
Còn những thứ bạn từng chắc chắn, giờ không còn khớp hoàn toàn với bằng chứng. Vì vậy có thể có bằng chứng đến khiến bạn bối rối hơn.
But the typical thing that you will see — I'm going to bust just for fun. Nice. OK. The typical thing that you'll see is that every time you get evidence, your uncertainty decreases.
Nhưng điều thường thấy — Tôi bắt con ma cho vui. Hay. OK. Điều thường thấy là mỗi lần có bằng chứng, độ bất định giảm xuống.
And every time elapses, your uncertainty increases again. Neither is actually saying that's guaranteed to happen.
Và mỗi lần thời gian trôi qua, độ bất định lại tăng lên. Không điều nào trong đó được đảm bảo sẽ xảy ra.
The only thing that's actually guaranteed to happen is that if you elapse time a lot without getting any evidence, that your belief distribution will converge to the stationary distribution of the matrix that's represented by your transition probabilities.
Điều duy nhất được đảm bảo là nếu cho thời gian trôi qua nhiều mà không có bằng chứng nào, phân phối niềm tin sẽ hội tụ về phân phối dừng của ma trận biểu diễn các xác suất chuyển.
Which means, among other things, it'll be independent of what you started out believing assuming everything's connected in a sufficiently probabilistic way.
Nghĩa là, trong số những điều khác, nó sẽ không phụ thuộc vào niềm tin ban đầu của bạn, giả sử mọi thứ được kết nối với nhau một cách đủ xác suất.
All right, let's see a little tiny zoomed in example, and then we'll start getting into particle filtering. So there are these two building blocks.
Giờ xem một ví dụ nhỏ phóng to, rồi ta sẽ bắt đầu vào lọc hạt. Vậy có hai khối xây dựng này.
And in your code, you're actually going to have functions with these names in them. This is not the only way you can represent this stuff.
Và trong code, các bạn sẽ có những hàm mang đúng các tên này. Đây không phải cách duy nhất để biểu diễn chúng.
You're going to have one action, which is to take your belief distribution and let time elapse. And we saw that that is you take your old belief distribution.
Bạn sẽ có một hành động, là lấy phân phối niềm tin của bạn và cho thời gian trôi qua. Ta đã thấy đó là lấy phân phối niềm tin cũ, nhân với các xác suất chuyển, rồi cộng tổng lại theo cách thích hợp.
You multiply it by the transition probabilities. And then you sum things up in the appropriate way. There's also going to be a step where you observe evidence.
Cũng sẽ có một bước quan sát bằng chứng.
In this case, you take your old belief distribution. You weight each term by the evidence. And then you renormalized, so it's a probability again. That's why this one is equal.
Trong trường hợp này, bạn lấy phân phối niềm tin cũ. Bạn gán trọng số cho từng số hạng theo bằng chứng. Rồi bạn chuẩn hóa lại để nó lại là một xác suất. Đó là lý do ở đây có dấu bằng.
Turns out, you don't have to renormalize there, because this is a stochastic matrix here. Here, you do have to renormalize, because you took a bunch of numbers that add up to one.
Hóa ra ở bước này bạn không cần chuẩn hóa lại, vì đây là một ma trận ngẫu nhiên. Còn ở đây thì bạn phải chuẩn hóa lại, vì bạn lấy một loạt số có tổng bằng một.
You multiplied them each by a probability. So they each got either a little smaller or a lot smaller. And so you have to renormalize to get a probability again.
Bạn nhân từng số với một xác suất. Nên mỗi số nhỏ đi một chút hoặc nhỏ đi nhiều. Vì vậy bạn phải chuẩn hóa lại để có một xác suất.
So here's how it would work. You would start off with some belief about, say, the probability of rain versus sun.
Nó hoạt động như thế này. Bạn bắt đầu với một niềm tin về, chẳng hạn, xác suất trời mưa so với trời nắng.
So let's say x here now is rain and sun, and e is umbrella or no umbrella. So you might have some prior on x1 that's given to you as input to the model.
Giả sử x ở đây là mưa và nắng, còn e là có ô hoặc không có ô. Bạn có thể có một phân phối tiên nghiệm cho x1 được đưa cho bạn làm đầu vào của mô hình.
And then some evidence comes in. You see that e1 is umbrella. OK, so I can shade that in here. Now we do some computation.
Rồi có bằng chứng đến. Bạn thấy e1 là có ô. Được, tôi tô đậm nó ở đây. Giờ ta tính toán.
And we see, OK, there's this 0.5 and 0.5. They both get multiplied by probability of umbrella. One of those probabilities is very high. One of them is very small.
Ta thấy có 0.5 và 0.5 này. Cả hai đều được nhân với xác suất có ô. Một trong các xác suất đó rất cao. Một cái thì rất nhỏ.
And when you renormalize, you end up with something like this. So now I think it's rainy. But then I flip to the next day. I let time pass.
Và khi chuẩn hóa lại, bạn sẽ được kết quả giống như thế này. Giờ tôi nghĩ là trời mưa. Nhưng rồi tôi chuyển sang ngày hôm sau. Tôi cho thời gian trôi qua.
I look at the probability of x2 given e1 is umbrella. All I have to do is use this elapsed time update, and things will flatten out.
Tôi xét xác suất của x2 biết e1 là có ô. Tôi chỉ cần dùng bước cập nhật theo thời gian trôi qua này, và phân phối sẽ phẳng ra.
Because if it was rainy, well, maybe it's still rainy. And if it was sunny, well, maybe it's rainy, and things tend to flatten out in this particular little model.
Vì nếu hôm trước mưa, thì có thể hôm nay vẫn mưa. Còn nếu hôm trước nắng, thì có thể hôm nay mưa, và trong mô hình nhỏ này, mọi thứ có xu hướng phẳng ra như vậy.
But then I get new evidence that I see an umbrella again, and then now I'm even more sure than ever that it's raining. OK?
Nhưng rồi tôi có bằng chứng mới là lại thấy một cái ô, và giờ tôi còn chắc hơn bao giờ hết là trời đang mưa. OK?
All right, any questions there before we do that basically again sideways with particles?
Được rồi, có câu hỏi nào không trước khi ta làm lại về cơ bản điều này theo hướng khác với các hạt?
OK.
OK.
So one common application that people use to illustrate HMMs, we've been using ghost tracking. In general, you could think about those tracking position.
Một ứng dụng phổ biến để minh họa HMM mà ta vẫn dùng là theo dõi con ma. Nói chung, bạn có thể nghĩ đến việc theo dõi vị trí.
Certainly not all hidden Markov models have the random variable x being position. We've had one here where it's weather.
Chắc chắn không phải mô hình Markov ẩn nào cũng có biến ngẫu nhiên x là vị trí. Ở đây ta có một ví dụ mà x là thời tiết.
You can imagine in speech recognition, it has something to do with the words that you're saying. For medical diagnosis, you might be tracking some oxygen level.
Bạn có thể hình dung trong nhận dạng giọng nói, nó liên quan đến các từ mà bạn đang nói. Với chẩn đoán y khoa, bạn có thể theo dõi nồng độ oxy nào đó.
In general, we are trying to construct hypotheses with probabilities associated with them over the underlying variable x, which in a localization problem is positions on a map.
Nói chung, ta đang cố xây dựng các giả thuyết kèm xác suất của chúng trên biến ẩn bên dưới x, mà trong bài toán định vị là các vị trí trên bản đồ.
What we've done so far is say, here's the map. And in each square, meaning for each value of x, we're going to write a probability. That's the whole vector of probabilities.
Những gì ta đã làm đến giờ là nói: đây là bản đồ. Và trong mỗi ô, tức là với mỗi giá trị của x, ta sẽ ghi một xác suất. Đó là toàn bộ vectơ xác suất.
The thing we track is a mapping, a vector, from hidden states x to probabilities. That is a distribution of recs. In particle filtering, you flip that around.
Thứ ta theo dõi là một ánh xạ, một vectơ, từ các trạng thái ẩn x đến xác suất. Đó là một phân phối trên các giá trị của x. Trong lọc hạt, bạn đảo ngược điều đó.
You don't necessarily track the entire distribution. You track particles or samples, which are individual hypotheses of what's going on. You might have two samples of the same hypothesis.
Bạn không nhất thiết theo dõi toàn bộ phân phối. Bạn theo dõi các hạt hay các mẫu, mà là những giả thuyết riêng lẻ về chuyện đang xảy ra. Bạn có thể có hai mẫu của cùng một giả thuyết.
Some samples might not have a hypothesis, or sorry, some hypotheses might not have a sample.
Một số mẫu có thể không có giả thuyết, à xin lỗi, một số giả thuyết có thể không có mẫu.
And the data structure you manipulate isn't a map from all the different outcomes of x to probabilities, but rather a list of samples.
Và cấu trúc dữ liệu bạn thao tác không phải là ánh xạ từ mọi kết quả khác nhau của x đến xác suất, mà là một danh sách các mẫu.
So for example, here, you might have a bunch of samples hypothesizing you're here, you're here, you're here, you're here, you're here.
Ví dụ ở đây, bạn có thể có một loạt mẫu giả thuyết rằng bạn ở đây, ở đây, ở đây, ở đây, ở đây.
And then there's other places where you have no samples representing that hypothesis, which means in that empirical distribution probability zero.
Và có những chỗ khác mà bạn không có mẫu nào đại diện cho giả thuyết đó, nghĩa là trong phân phối thực nghiệm, xác suất bằng không.
So you might need a lot of samples for this to work, and there might be a lot of hypotheses which have probability zero. So this is an approximate solution to the filtering problem.
Vậy bạn có thể cần rất nhiều mẫu để cách này hiệu quả, và có thể có rất nhiều giả thuyết có xác suất bằng không. Đây là một lời giải xấp xỉ cho bài toán lọc.
Remember filtering is one name for the problem where I ask given all of my evidence, what is the current hidden variable xt? Where is the robot now?
Nhớ rằng lọc là một tên gọi của bài toán mà tôi hỏi, với toàn bộ bằng chứng của mình, biến ẩn hiện tại xt là gì? Robot đang ở đâu bây giờ?
That's different from the most likely explanation problem where you want to know something about where, basically what was the robot's road trip like that got it here?
Điều đó khác với bài toán giải thích có khả năng nhất, khi bạn muốn biết điều gì đó về việc chuyến đi của robot trông như thế nào để nó đến được đây? Có vài lý do để bạn muốn dùng lọc hạt.
There are a couple reasons why you might want to do particle filtering. One is this event space x of robot positions might be too big to use exact inference.
Một là không gian sự kiện x của các vị trí robot có thể quá lớn để dùng suy luận chính xác.
It might just be really big, and you don't want to store it, or it might be slow to work with, or x might be continuous.
Nó có thể rất lớn, bạn không muốn lưu trữ nó, hoặc xử lý nó chậm, hoặc x có thể liên tục.
If I want to track robot positions in the real world, I can't enumerate all the pairs or triples of real numbers. Right?
Nếu tôi muốn theo dõi vị trí robot trong thế giới thực, tôi không thể liệt kê hết các cặp hay bộ ba số thực. Đúng không?
But I can say, all right, I'm willing to have 600,000 samples, go. And there's one sample that's here and here and here and one over by the wall.
Nhưng tôi có thể nói, được rồi, tôi chấp nhận có 600,000 mẫu, bắt đầu. Có một mẫu ở đây, ở đây, ở đây và một mẫu gần bức tường.
And there, I get to decide how much compute I do and what the trade off is between compute and accuracy even if x is an infinite space like a continuous space.
Ở đó, tôi được quyết định mình dùng bao nhiêu tính toán và đánh đổi giữa tính toán và độ chính xác thế nào, ngay cả khi x là không gian vô hạn như không gian liên tục.
It's also a solution, because we can now do approximate inference, which often has a lot of trade offs, usually speed. So here's how it works. Here's how particle filtering works.
Đây cũng là một giải pháp, vì giờ ta có thể thực hiện suy luận xấp xỉ, thường có nhiều đánh đổi, thường là về tốc độ. Vậy nó hoạt động như sau. Đây là cách lọc hạt hoạt động.
Rather than writing down belief distributions explicitly where for every outcome x, I write a probability, which is a vector of size domain of x, which could be very big.
Thay vì ghi tường minh các phân phối niềm tin mà với mỗi kết quả x, tôi ghi một xác suất, tức là một vectơ có kích thước bằng miền của x, có thể rất lớn. Thay vào đó, tôi sẽ theo dõi các mẫu của x.
Instead, I'm going to track samples of x. Maybe I track a million samples, maybe I track two. I'm going to track samples of x not necessarily all values.
Có thể tôi theo dõi một triệu mẫu, có thể chỉ hai. Tôi sẽ theo dõi các mẫu của x chứ không nhất thiết mọi giá trị. Những mẫu này ở đây được gọi là các hạt.
These samples here are called particles. They're just samples. The amount of time I'm going to spend is linear in the number of samples.
Những mẫu này ở đây được gọi là các hạt. Chúng chỉ là các mẫu thôi. Thời gian tôi tốn tỉ lệ tuyến tính với số lượng mẫu.
Because my basic flow of this algorithm is, here are my samples. They represent my current belief, because, hey, all the samples are over there by the wall. I think the robot's probably over there.
Vì luồng cơ bản của thuật toán này là: đây là các mẫu của tôi. Chúng biểu diễn niềm tin hiện tại của tôi, vì này, tất cả các mẫu đều nằm ở chỗ bức tường kia. Tôi nghĩ robot có lẽ ở đằng đó.
I'm going to do operations on these samples to give me new samples, and I'm going to do it basically by scanning over the old samples. So that's great.
Tôi sẽ thực hiện các phép toán trên những mẫu này để tạo ra các mẫu mới, và tôi sẽ làm việc đó về cơ bản bằng cách duyệt qua các mẫu cũ. Vậy là tốt.
It's linear in the number of samples, but the number of samples you need might be very large.
Nó tuyến tính theo số lượng mẫu, nhưng số mẫu bạn cần có thể rất lớn.
The thing you actually store in memory, and this is really important, because some of the PowerPoint figures will suggest that all the spaces or even the ones with zero are tracked.
Thứ bạn thực sự lưu trong bộ nhớ, và điều này rất quan trọng, vì một số hình trong PowerPoint gợi ý rằng mọi ô, kể cả những ô bằng không, đều được theo dõi.
They're not. In memory, you have a list of samples, a list of particles. There is not a list of all possible states. That's important, or there'd be no point doing this.
Không phải vậy. Trong bộ nhớ, bạn có một danh sách các mẫu, danh sách các hạt. Không có danh sách tất cả các trạng thái có thể. Điều đó quan trọng, nếu không thì làm thế này chẳng có ý nghĩa gì.
In practice, robot localization works this way, because it happens in continuous spaces. A lot of other tracking problems also work this way. And particles are just samples. OK, are we ready?
Trong thực tế, định vị robot hoạt động theo cách này, vì nó diễn ra trong không gian liên tục. Nhiều bài toán theo dõi khác cũng hoạt động như vậy. Và các hạt chỉ là các mẫu. Được rồi, sẵn sàng chưa?
Here is a distribution over this three by three grid, represented in the explicit way. For each state, I have a number. In this case, some of them are zero.
Đây là một phân phối trên lưới ba nhân ba này, biểu diễn theo cách tường minh. Với mỗi trạng thái, tôi có một con số. Ở đây, một số bằng không.
This is the way I'm going to draw a collection of 10 samples. Of those 10 samples, five of them are in the lower right corner. Some states have no samples.
Còn đây là cách tôi vẽ một tập 10 mẫu. Trong 10 mẫu đó, có năm mẫu nằm ở góc dưới bên phải. Một số trạng thái không có mẫu nào.
If I write out the state space, I'll have to write out nine numbers. If I write out the samples, I have to write out some list, oh, OK.
Nếu viết ra không gian trạng thái, tôi phải viết chín con số. Nếu viết ra các mẫu, tôi phải viết một danh sách nào đó, ồ, được.
There's one in two, one. There's one in three, two, whatever. And I have to write them all out. I'll have to write out pin numbers.
Có một mẫu ở (2, 1). Có một mẫu ở (3, 2), v.v. Và tôi phải viết hết ra. Tôi sẽ phải viết ra từng con số.
In this case, it's cheaper to write out the states based representation. In general, it's going to be the other way around. So here's my representation.
Trong trường hợp này, biểu diễn theo trạng thái rẻ hơn. Nhưng nói chung thì sẽ ngược lại. Đây là biểu diễn của tôi.
My representation of my distributions over x, which will in general condition on evidence, they'll be belief distributions, but whenever I have a distribution over x, it's going to be a list of n particles.
Biểu diễn các phân phối của tôi trên x, nói chung sẽ có điều kiện theo bằng chứng, chúng sẽ là các phân phối niềm tin, nhưng bất cứ khi nào tôi có một phân phối trên x, nó sẽ là một danh sách n hạt.
Normally, n is much, much, much smaller than the size of x, except on these slides where it's just going to be a tiny bit bigger.
Thông thường n nhỏ hơn rất, rất nhiều so với kích thước của x, trừ trên những slide này, nơi nó chỉ lớn hơn một chút.
But imagine the grid is huge and the number of samples compared to that is relatively small.
Nhưng hãy tưởng tượng lưới rất lớn và số mẫu so với nó là tương đối nhỏ.
So we're not going to store a map that says in this point, this place we have five samples. We might as well just draw the probability.
Vì vậy ta sẽ không lưu một bản đồ nói rằng tại điểm này, chỗ này có năm mẫu. Khi đó thà vẽ xác suất luôn cho xong.
We're going to store this in memory, list of particles. When we see a green particle here in these slides, that's going to be the particle that I'm going to talk about.
Ta sẽ lưu trong bộ nhớ một danh sách các hạt. Khi thấy một hạt màu xanh lá trong các slide này, đó là hạt mà tôi sẽ nói đến.
We're going to talk about the journey of the green particle and what happens to it. Particles aren't actually distinguished. They're just a list of them.
Ta sẽ nói về hành trình của hạt xanh lá và chuyện gì xảy ra với nó. Thực ra các hạt không được phân biệt. Chúng chỉ là một danh sách.
They each have the same status in the computation so p of x will be approximated by the number of particles that have the value of x.
Mỗi hạt có vai trò như nhau trong tính toán, nên p của x sẽ được xấp xỉ bằng số hạt có giá trị x.
So many, many, many values of x have p of x equals zero in the sampling distribution. If we have more particles, we get more accuracy. Right now, imagine all the particles have equal weight.
Vì thế rất, rất nhiều giá trị của x có p của x bằng không trong phân phối lấy mẫu. Có càng nhiều hạt thì càng chính xác. Bây giờ hãy tưởng tượng mọi hạt có trọng số bằng nhau.
So if I show you this list of particles here, well, I could ask you a question like, hey, what's the probability that the robot is at this location?
Nếu tôi cho bạn xem danh sách các hạt này, tôi có thể hỏi một câu như, xác suất robot ở vị trí này là bao nhiêu?
Which is what is that? Three, two. So I would look through, and I'd say, well, there's a three, two.
Vị trí nào đây? (3, 2). Tôi sẽ duyệt qua và nói, có một hạt ở (3, 2).
And there's a three, two. So two out of 10, that is my approximation. Is that right? It's probably not right.
Và lại có một hạt ở (3, 2). Vậy hai trên 10, đó là xấp xỉ của tôi. Có đúng không? Có lẽ không đúng.
This is like any other sampling method. Unless you have a lot of samples, you're going to have some error due to the sampling noise.
Cũng như mọi phương pháp lấy mẫu khác. Nếu không có nhiều mẫu, bạn sẽ có sai số do nhiễu lấy mẫu.
All right, so I am going to be carrying a list of samples, a list of particles which represent my current hypotheses and in aggregate represent my belief distribution over where the robot is.
Vậy tôi sẽ mang theo một danh sách các mẫu, một danh sách các hạt biểu diễn các giả thuyết hiện tại của tôi và gộp lại biểu diễn phân phối niềm tin của tôi về vị trí của robot.
It could be here. It could be here. And at three, three, I have five samples. That represents I have a higher probability there.
Nó có thể ở đây. Nó có thể ở đây. Và tại (3, 3), tôi có năm mẫu. Điều đó nghĩa là xác suất ở đó cao hơn.
How should I take this list of particles, which represents my probability distribution, and advance time? What happens when time advances? The dynamics come into play.
Làm sao lấy danh sách hạt này, vốn biểu diễn phân phối xác suất của tôi, rồi cho thời gian trôi tiếp? Điều gì xảy ra khi thời gian trôi? Động lực học phát huy tác dụng.
And for every xt, there will be some distribution over xt plus one, which represents what happens next in the dynamics.
Với mỗi xt sẽ có một phân phối trên xt cộng một, biểu diễn điều xảy ra tiếp theo theo động lực học.
And so what I'll do is I'll go to each particle and I'll just move it, like think about moving it around the game board here.
Vì vậy tôi sẽ đến từng hạt và chỉ việc di chuyển nó, hãy nghĩ như di chuyển nó quanh bàn chơi này.
And for each sample x, that I have right now, I'm going to take a sample of its future.
Với mỗi mẫu x mà tôi đang có, tôi sẽ lấy một mẫu về tương lai của nó.
Well, if it's at value little x, I'm going to look up the transition probability and say, oh, here the probability of the various x primes. And then I'm going to sample.
Nếu nó đang ở giá trị x nhỏ, tôi sẽ tra xác suất chuyển và thấy, ồ, đây là xác suất của các x phẩy khác nhau. Rồi tôi sẽ lấy mẫu. Tôi dùng cách lấy mẫu đa thức mà ta đã học trước đó.
I'm going to use my multinomial sampling that we had before. I'm going to take a uniform distribution from zero to one.
Tôi lấy một phân phối đều từ không đến một. Ánh xạ nó lên các kết quả khác nhau, và giả sử nó đi xuống ô bên dưới.
I'll map it onto the various outcomes, and let's say it'll go to the square below. That is my new value x prime.
Đó là giá trị mới x phẩy của tôi.
So for example this green, let's go green, this green particle here is at three, three. I will look up and I will say, in my HMM, where do things go from three, three?
Ví dụ hạt xanh lá này, chọn màu xanh lá nhé, hạt xanh lá này đang ở (3, 3). hạt màu xanh lá này đang ở vị trí (3, 3). Tôi sẽ tra cứu và hỏi, trong HMM của mình, từ ô (3, 3) thì mọi thứ sẽ đi đâu?
And it'll say, well, 60% of the time, they go to the square below, and 20% of time, they go to the square below and to the left or whatever it is.
Và nó sẽ nói, 60% số lần chúng đi xuống ô bên dưới, còn 20% đi xuống ô phía dưới bên trái, hoặc ô nào đó.
And then I'll flip a coin, and maybe it goes to the square. That particle will be replaced by a new particle at this newly sampled position.
Rồi tôi tung đồng xu, và có thể nó đi vào ô đó. Hạt đó sẽ được thay bằng một hạt mới tại vị trí vừa được lấy mẫu này.
So each particle before turns into a particle after, and each one takes its own journey.
Vậy mỗi hạt ở bước trước biến thành một hạt ở bước sau, và mỗi hạt có hành trình riêng của nó.
So if I have five different particles that all happen to be at three, three, for each one, I'm going to pick it up and say, hey, you, where do you want to go?
Giả sử tôi có năm hạt khác nhau đều đang ở (3, 3), với từng hạt một, tôi sẽ nhấc nó lên và hỏi, này bạn, bạn muốn đi đâu?
I want to go down. OK, great. Where do you want to go? I want to go down.
Tôi muốn đi xuống. Được, tốt. Còn bạn muốn đi đâu? Tôi muốn đi xuống.
Great. Where do you want to go? I want to go to the left. And so they will in general scatter a little bit.
Tốt. Còn bạn muốn đi đâu? Tôi muốn sang trái. Vậy nói chung chúng sẽ phân tán ra một chút.
But each one is independently picked up. You go through this list, pick up each particle, and sample a future for it.
Nhưng mỗi hạt được nhấc lên một cách độc lập. Bạn đi qua danh sách này, nhấc từng hạt lên, và lấy mẫu một tương lai cho nó.
Even if two particles are the same, they will in general not have the same future.
Ngay cả khi hai hạt giống nhau, nói chung chúng sẽ không có cùng một tương lai.
And you can have two particles that are different that end up having the same future, because there are multiple ways to get to a certain square. This should remind you of prior sampling.
Và có thể có hai hạt khác nhau nhưng lại có cùng một tương lai, vì có nhiều cách để đến cùng một ô. Điều này nên làm bạn nhớ đến prior sampling.
Things that are more likely in my distribution, that increased likelihood is reflected in the increased count of samples. So the sample frequencies here are going to reflect the probabilities.
Những thứ có khả năng cao hơn trong phân phối của tôi thì khả năng cao đó được phản ánh qua số mẫu nhiều hơn. Vậy tần suất mẫu ở đây sẽ phản ánh các xác suất.
And then each variable, I'm just going to sample a future for, just like prior sampling. Oh, you chose sprinkler on. Let's sample for wet grass.
Và với mỗi biến, tôi chỉ việc lấy mẫu một tương lai cho nó, giống như prior sampling. À, bạn chọn sprinkler bật. Giờ lấy mẫu cho wet grass.
And so for each of these samples, I'm going to be, oh, you're in three, three. Let's sample a future for you.
Và với mỗi mẫu này, tôi sẽ nói, à, bạn đang ở (3, 3). Để lấy mẫu một tương lai cho bạn.
So each particle before becomes a particle after in general evolved according to the dynamics, and this is going to capture the passage of time.
Vậy mỗi hạt trước đó trở thành một hạt sau đó, nói chung tiến triển theo động lực học của hệ, và điều này nắm bắt sự trôi qua của thời gian.
If you have enough samples, these will look pretty much like the exact values before and after. If you only have a couple samples, it'll be super noisy. OK?
Nếu có đủ mẫu, những hạt này sẽ trông gần giống các giá trị chính xác trước và sau. Nếu chỉ có vài mẫu thì sẽ rất nhiễu. Được chứ?
Any questions? So this is actually a lot easier, I think this is a lot easier to get intuitively than the actual exact inference, because I don't have to think about marginalizing probabilities or anything.
Có câu hỏi nào không? Thật ra cách này dễ hơn nhiều, tôi nghĩ nó dễ nắm bắt bằng trực giác hơn nhiều so với suy luận chính xác, vì tôi không phải nghĩ về việc lấy biên các xác suất hay gì cả.
I just have to think, all right, here's a hypothesis. Maybe it's at three, three. If it were, where would it go? I'll flip a coin.
Tôi chỉ cần nghĩ, được rồi, đây là một giả thuyết. Có thể nó ở (3, 3). Nếu đúng vậy, nó sẽ đi đâu? Tôi tung đồng xu.
The fact that there are now a bunch of particles here, well, how did they get here? Well, they all started at a different location.
Việc bây giờ có một loạt hạt ở đây, vậy chúng đến đây bằng cách nào? Chúng đều xuất phát từ những vị trí khác nhau.
They all flipped a coin about their future, and then they transitioned here.
Chúng đều tung đồng xu cho tương lai của mình, rồi chuyển đến đây.
That is just the summation weighted by the transitions of all the previous probabilities, but it's done in a more sample based way. OK, here's the trickier step.
Đó chính là tổng có trọng số theo các xác suất chuyển của mọi xác suất trước đó, nhưng được làm theo cách dựa trên mẫu. Được rồi, đây là bước khó hơn.
Then we'll look at some examples and take a break. The trickier step is observation. So I've got a list of particles. So here they are.
Sau đó ta sẽ xem vài ví dụ rồi nghỉ giải lao. Bước khó hơn là quan sát. Tôi có một danh sách các hạt. Đây là chúng.
This is what is actually in memory. This is what I put in PowerPoint so we can visualize it. OK? So you've got this list of particles.
Đây là thứ thực sự nằm trong bộ nhớ. Đây là thứ tôi đưa vào PowerPoint để ta hình dung. Được chứ? Vậy bạn có danh sách các hạt này.
And I could look at this list of particles, and I could ask questions like, how likely is it that you're at two, comma, two? Well, I've got one particle there out of 10.
Tôi có thể nhìn danh sách này, và hỏi những câu như, khả năng bạn ở ô (2, 2) là bao nhiêu? Có một hạt ở đó trong 10 hạt.
Looks like 10%. I could ask questions like, what's the most likely location of the robot? And according to these particles, it's three, comma, two. I can also use these particles to incorporate evidence.
Có vẻ là 10%. Tôi cũng có thể hỏi, vị trí có khả năng nhất của robot là đâu? Và theo các hạt này, đó là (3, 2). Tôi cũng có thể dùng các hạt này để đưa bằng chứng vào.
So let's say I get evidence that this square here measured a reading of red, meaning ghost very close.
Giả sử tôi nhận được bằng chứng rằng ô này đo được kết quả màu đỏ, nghĩa là ma ở rất gần.
Well, if this were prior sampling, or more to the point here, rejection sampling, what I would do is I would pick up three, comma, two, and say, all right, time to sample a future for you.
Nếu đây là prior sampling, hay chính xác hơn ở đây là rejection sampling, thì tôi sẽ nhấc hạt (3, 2) lên và nói, được rồi, đến lúc lấy mẫu một tương lai cho bạn.
What reading do you think should happen? And I'll be like, oh, I think orange. Dead. You pick up the next one.
Bạn nghĩ sẽ có kết quả đo nào? Và nó nói, ồ, tôi nghĩ là màu cam. Chết. Bạn nhấc hạt tiếp theo lên.
What do you think should happen? Yellow. Dead. And you reject all of these samples by asking them what evidence they would like.
Bạn nghĩ sẽ có kết quả nào? Màu vàng. Chết. Bạn loại bỏ tất cả các mẫu này bằng cách hỏi chúng muốn bằng chứng nào.
And then when it doesn't happen to match the evidence you have, which is red, they're out. This is a way to reject all your samples. OK, so we don't do this.
Và khi nó không khớp với bằng chứng bạn có, tức là màu đỏ, thì chúng bị loại. Đây là cách loại bỏ hết các mẫu của bạn. Được, nên ta không làm vậy.
Instead, we do something that's like likelihood weighting. I pick up each particle and say, hi, particle. I'm here to inform you that there is this evidence red at this square.
Thay vào đó, ta làm điều giống như likelihood weighting. Tôi nhấc từng hạt lên và nói, chào hạt. Tôi đến để báo rằng có bằng chứng màu đỏ tại ô này.
And the particle might say, great. That's probably what would have happened anyway. So this particle maybe says that. There are going to be other particles that say, I think that's extremely unlikely.
Và hạt có thể nói, tuyệt. Dù sao đó cũng có thể là điều sẽ xảy ra. Hạt này có thể nói như vậy. Sẽ có những hạt khác nói, tôi nghĩ điều đó cực kỳ khó xảy ra.
And so each particle will stay there in your list, but it will pick up a weight, because we're now doing likelihood weighting. We're not giving them the option of being rejected.
Và mỗi hạt vẫn nằm lại trong danh sách của bạn, nhưng sẽ nhận một trọng số, vì bây giờ ta đang dùng likelihood weighting. Ta không cho chúng lựa chọn bị loại bỏ.
We're forcing them to stay around. And so they can only stay around fractionally. They can stay around with a fraction that represents how likely it would have been to generate the evidence in question.
Ta buộc chúng phải ở lại. Và vì vậy chúng chỉ có thể tồn tại ở một phần nhỏ. Chúng tồn tại với một phần biểu thị khả năng chúng sẽ sinh ra bằng chứng đang xét.
So now suddenly, we have the same particles, but weighted. You can think about that as some particles stay size one, but most particles shrink. Some particles shrink a lot.
Vậy là đột nhiên ta có cùng các hạt đó, nhưng có trọng số. Bạn có thể hình dung là một số hạt giữ kích thước một, nhưng phần lớn các hạt co lại. Một số hạt co lại rất nhiều.
Maybe some particles will shrink down to zero. So suddenly, instead of 10 particles, I've got three fractional particles. But I do still have 10 things in my list.
Có thể một số hạt co về không. Vậy là đột nhiên, thay vì 10 hạt, tôi có ba hạt phân số. Nhưng tôi vẫn có 10 phần tử trong danh sách.
What does this correspond to? This corresponds to taking my belief distribution, my old belief distribution, and weighting everything by the evidence. Except remember when I weight everything by the evidence, I have to renormalize.
Điều này tương ứng với gì? Điều này tương ứng với việc lấy phân phối belief, phân phối belief cũ của tôi, và nhân trọng số mọi thứ theo bằng chứng. Trừ việc nhớ rằng khi nhân trọng số mọi thứ theo bằng chứng, tôi phải chuẩn hóa lại.
Why do I renormalize? I renormalize because I don't have probability distribution. Here, I have samples, but a lot of them are sitting there with tiny, tiny weight, maybe even zero weight.
Tại sao phải chuẩn hóa lại? Vì tôi không có một phân phối xác suất. Ở đây, tôi có các mẫu, nhưng rất nhiều mẫu đang nằm đó với trọng số cực nhỏ, thậm chí có thể bằng không.
So I need new samples.
Nên tôi cần mẫu mới.
And so there is another step that we add after we've down weighted all of the samples by the evidence probability, where we get new samples weighted from the old samples.
Và vì thế có thêm một bước nữa sau khi ta đã giảm trọng số tất cả các mẫu theo xác suất của bằng chứng, trong đó ta lấy các mẫu mới có trọng số từ các mẫu cũ.
OK?
OK?
So what we're going to do is we're going to take these weighted samples, which are the old samples we had, and some have shrunk a lot and some have not shrunk, and I'm going to say, these samples are no good to me, because their weights are starting to shrink.
Vậy ta sẽ làm như sau: lấy các mẫu có trọng số này, là các mẫu cũ, trong đó có mẫu co lại nhiều và có mẫu không co, và tôi sẽ nói: những mẫu này vô dụng với tôi, vì trọng số của chúng đang bắt đầu co lại.
And if I do this for too long, their weights will all go to zero. And so what I'll do is I'll create new particles.
Và nếu làm thế quá lâu, trọng số của chúng sẽ về không hết. Nên tôi sẽ tạo các hạt mới.
The new particles, I sample with replacement here from the old weighted samples. So I say, all right, what particle should I have for the first thing on my list?
Với các hạt mới, tôi lấy mẫu có hoàn lại từ các mẫu có trọng số cũ. Tôi tự hỏi, hạt nào nên nằm ở vị trí đầu tiên trong danh sách?
Well, I come back up here and I pick one of my old particles in proportion to its weight.
Tôi quay lại đây và chọn một hạt cũ tỉ lệ với trọng số của nó.
So this one here at three, two, which has weight 0.9, it's going to get picked more often than this one at one, comma, three, whose weight's approaching zero.
Hạt ở (3, 2) này, có trọng số 0.9, sẽ được chọn thường xuyên hơn hạt này ở (1, 3), có trọng số gần bằng không.
And so you might find that particle at three, two, which was one highly weighted particle, it might show up now as multiple unweighted particles.
Và bạn có thể thấy hạt ở (3, 2), vốn là một hạt có trọng số cao, giờ có thể xuất hiện thành nhiều hạt không trọng số.
And so we, by resampling, shifted the information about their relative probabilities from their weights over to their multiplicity. So how's that work?
Như vậy, nhờ lấy mẫu lại, ta chuyển thông tin về xác suất tương đối của chúng từ trọng số sang số lần xuất hiện. Vậy nó hoạt động thế nào?
We had n particles. We're going to choose n different particles from our old particles with replacement. And in the process, we'll ditch the weights.
Ta có n hạt. Ta sẽ chọn n hạt từ các hạt cũ, có hoàn lại. Và trong quá trình đó, ta bỏ trọng số.
The weights were necessary to reflect the fact that, say, this one here was present, but basically shouldn't contribute very much to the belief.
Trọng số cần thiết để phản ánh việc, chẳng hạn, hạt này có mặt, nhưng về cơ bản không nên đóng góp nhiều vào belief.
That same situation is reflected in the fact that with high probability, it won't be selected.
Tình huống đó giờ được phản ánh ở chỗ nó có xác suất cao là không được chọn.
And now your update's complete. So when you observe evidence, you take your particles. You weight them by the evidence. And then you resample them.
Và vậy là bước cập nhật hoàn tất. Khi quan sát bằng chứng, bạn lấy các hạt. Bạn nhân trọng số theo bằng chứng. Rồi bạn lấy mẫu lại.
And now, you have another set of 10 particles, which are composed of your old particles, some of them more than once, and some of them have dropped off.
Và giờ bạn có một tập 10 hạt khác, gồm các hạt cũ của bạn, một số xuất hiện nhiều lần, và một số đã bị loại.
Then time will pass, and those particles that are cloned from each other will start to diverge and so on. So let's do a recap. We'll see some demos.
Rồi thời gian trôi, và những hạt được nhân bản từ nhau sẽ bắt đầu tách ra và cứ thế tiếp tục. Ta tóm tắt lại. Ta sẽ xem vài demo.
We'll take a break.
Rồi nghỉ giải lao.
All right, particles track samples of states or hypotheses of unobserved variables rather than a distribution. So instead of tracking a distribution, I track this list of particles.
Được rồi, các hạt theo dõi các mẫu của trạng thái hay giả thuyết về các biến không quan sát được thay vì một phân phối. Nên thay vì theo dõi một phân phối, tôi theo dõi danh sách các hạt này.
When time elapses, I move my particles around the game board probabilistically by picking each one up and picking a future. I don't have to renormalize. I don't have to resample.
Khi thời gian trôi, tôi di chuyển các hạt quanh bàn chơi theo xác suất, bằng cách nhấc từng hạt lên và chọn một tương lai. Tôi không phải chuẩn hóa lại. Tôi không phải lấy mẫu lại.
It's just each particle moves. Multiple particles that had been in the same place can diverge. Multiple particles that had been diverged can come back together. It's whatever you sample.
Chỉ là mỗi hạt di chuyển. Nhiều hạt từng ở cùng một chỗ có thể tách ra. Nhiều hạt đã tách ra có thể quay lại gặp nhau. Tùy vào kết quả lấy mẫu.
When you get evidence, you weight the particles. Some of the particles maintain high weight, because they're compatible with the evidence. Some of the particles are starting to shrink.
Khi có bằng chứng, bạn nhân trọng số cho các hạt. Một số hạt giữ trọng số cao, vì chúng phù hợp với bằng chứng. Một số hạt bắt đầu co lại.
They're almost gone. You don't want to keep around particles that are basically not contributing, because they don't represent very much mass of your belief distribution.
Chúng gần như biến mất. Bạn không muốn giữ lại những hạt về cơ bản không đóng góp gì, vì chúng không đại diện cho nhiều khối lượng của phân phối belief.
And so you take those weighted particles and resample, which gives you a new set of particles, once again unweighted. There's some multiplicity, and they represent your new distribution.
Vì vậy bạn lấy các hạt có trọng số đó và lấy mẫu lại, cho ra một tập hạt mới, lại không có trọng số. Có một số hạt lặp lại, và chúng biểu diễn phân phối mới của bạn.
Elapsed time, this represents what happens to your distribution if time passes. Weighting and resampling together represent what happens to your distribution when you observe evidence. OK, let's see some examples.
Bước thời gian trôi biểu diễn điều xảy ra với phân phối khi thời gian trôi qua. Gán trọng số và lấy mẫu lại cùng nhau biểu diễn điều xảy ra với phân phối của bạn khi bạn quan sát bằng chứng. OK, xem vài ví dụ.
We'll take a break.
Ta sẽ nghỉ giải lao.
All right, so ghost busters.
Được rồi, trò săn ma.
We will run the same ghost busters app where we can elapse time or take observations or bust the ghosts, except this time instead of exact inference, we will be doing it with particles.
Ta sẽ chạy cùng ứng dụng săn ma đó, nơi ta có thể cho thời gian trôi, quan sát hoặc bắt các con ma, nhưng lần này thay vì suy luận chính xác, ta sẽ làm bằng các hạt.
Each particle will represent a hypothesis of where the ghost is. So in memory somewhere is some list of 30 positions where the ghost might be. What's being visualized?
Mỗi hạt sẽ biểu diễn một giả thuyết về vị trí của con ma. Trong bộ nhớ có một danh sách gồm 30 vị trí mà con ma có thể đang ở. Hình này đang minh họa điều gì?
What's being visualized is according to those samples, what is the probability implied over the space? Luckily, the space is small enough I can do that computation. In general, I would just have my particles.
Nó cho thấy, dựa trên các mẫu đó, xác suất suy ra trên toàn không gian là bao nhiêu. May là không gian đủ nhỏ nên tôi tính được điều đó. Nói chung, tôi chỉ có các hạt của mình thôi.
You'll notice that some of the positions have probability zero, because there's no particles that live there.
Các bạn sẽ thấy một số vị trí có xác suất bằng không, vì không có hạt nào nằm ở đó.
And others have probability greater than 0.02, and that's because instead of sampling everything uniformly, the samples fell where they fell, and there's noise in that process.
Còn những vị trí khác có xác suất lớn hơn 0.02, đó là vì thay vì lấy mẫu đều mọi nơi, các mẫu rơi đâu thì nằm đó, và quá trình này có nhiễu.
So here is what with a moderate number of samples a uniform distribution looks like. It's not all that uniform, right? What happens when I elapse time?
Đây là dạng của một phân phối đều với số mẫu vừa phải. Nó không đều lắm, đúng không? Điều gì xảy ra khi tôi cho thời gian trôi?
Well, all these particles will swim around in a circle in a stochastic way here. So there they go. If I do it fast enough, you can actually see the circular motion there.
Tất cả các hạt này sẽ bơi quanh theo vòng tròn một cách ngẫu nhiên. Đấy, chúng đang di chuyển. Nếu chạy đủ nhanh, bạn thực sự thấy được chuyển động tròn đó.
I can gather some evidence. Like, oh, this one looks reasonably like — let's sense here. All right, so you can see what happened when I gathered evidence?
Tôi có thể thu thập một ít bằng chứng. Ví dụ, cái này trông khá hợp lý, ta cảm biến ở đây. Các bạn thấy điều gì xảy ra khi tôi thu thập bằng chứng chứ?
A whole bunch of particles were wiped out, because they didn't match that evidence. And then a bunch of new particles were sampled from those weighted particles.
Cả loạt hạt bị loại bỏ, vì chúng không khớp với bằng chứng đó. Rồi một loạt hạt mới được lấy mẫu từ các hạt có trọng số đó.
A disproportionate number of them happened to be right here. Maybe I'll sample here.
Một số lượng không cân xứng trong đó lại rơi đúng chỗ này. Có thể tôi sẽ lấy mẫu ở đây.
All right, so a bunch of particles that were all piled up there that are now inconsistent with that evidence just basically got deleted. They got small weights, and then they didn't get resampled.
Vậy là nhiều hạt từng chất đống ở đó mà giờ không còn phù hợp với bằng chứng thì về cơ bản bị xóa. Chúng có trọng số nhỏ nên không được lấy mẫu lại.
So where did my mass go? It went to wherever there were particles that were still reasonably likely to have survived the previous round.
Vậy khối lượng xác suất của tôi đi đâu? Nó đi đến nơi nào có các hạt vẫn còn khả năng sống sót qua vòng trước.
So at this point, the particles are starting to clump together, but they're not probably in the right place.
Lúc này các hạt bắt đầu tụ lại với nhau, nhưng có lẽ chưa đúng chỗ.
This is why it's dangerous to have a small number of particles, and it's always dangerous to have a small number of samples, because you're going to get noise from that.
Đó là lý do việc dùng ít hạt là nguy hiểm, mà dùng ít mẫu thì lúc nào cũng nguy hiểm, mà dùng ít mẫu thì lúc nào cũng nguy hiểm, vì bạn sẽ bị nhiễu từ đó.
But in particle filtering, there's this extra tendency of particles to accumulate in weird places and get overly peaked in their distribution. All right, let's do that exact same thing, but with one particle.
Nhưng trong lọc hạt, còn có xu hướng các hạt dồn vào những chỗ kỳ lạ và làm phân phối quá nhọn. Giờ ta làm lại y hệt, nhưng chỉ với một hạt.
So what do I do? I'm going to have my initial list of particles, which will represent a uniform distribution over the space. There it is. That's as uniform as you get with one particle.
Tôi làm gì đây? Tôi có danh sách hạt ban đầu, biểu diễn một phân phối đều trên không gian. Đây rồi. Với một hạt thì đó là đều hết mức có thể.
All right, I can elapse time. What's going to happen? Well, the particle is going to sort of swim around in a circle. I can take a measurement.
Tôi cho thời gian trôi. Chuyện gì sẽ xảy ra? Hạt sẽ bơi quanh theo vòng tròn. Tôi đo một lần.
What will happen? Let's measure over here. All right, where's my particle go? It stays right there.
Điều gì sẽ xảy ra? Ta đo ở đây. Hạt của tôi đi đâu? Nó vẫn ở nguyên đó.
There's nowhere for it to go. It gets down weighted, and then you sample a new one. And guess what? You've only got one choice, and your particle's back.
Nó không còn chỗ nào để đi. Nó bị giảm trọng số, rồi bạn lấy mẫu một hạt mới. Và đoán xem? Bạn chỉ có một lựa chọn, và hạt của bạn quay lại.
And you can't shake this one particle. It's never going to split and become two particles. Each particle just does its thing.
Bạn không thể thoát khỏi hạt duy nhất này. Nó sẽ không bao giờ tách ra thành hai hạt. Mỗi hạt cứ làm việc của nó.
Only when you have multiple particles can you have one get resampled a few times and another one get lost in the resampling step, and this causes your distribution to refocus.
Chỉ khi có nhiều hạt thì một hạt mới được lấy mẫu lại vài lần còn hạt khác bị mất ở bước lấy mẫu lại, và điều này làm phân phối tập trung lại.
All right, let's do it again, but with a ton of particles. OK. Now, there's a lot of particles here. And now you can there's some noise.
Ta làm lại, nhưng với rất nhiều hạt. Được. Giờ có rất nhiều hạt ở đây. Và các bạn thấy vẫn còn chút nhiễu.
Right? In fact, there's a 0.01 here where it really should be 0.02. But this is a lot closer to the actual distribution, because the number of samples is higher.
Đúng không? Thực tế, chỗ này là 0.01 trong khi lẽ ra phải là 0.02. Nhưng nó gần phân phối thật hơn nhiều, vì số mẫu lớn hơn.
So lets grab some evidence. All right. Now, if I let time pass, all of those particles will start to diverge. And now, they're smeared all over the place.
Giờ ta thu thập bằng chứng. Được rồi. Giờ nếu cho thời gian trôi, tất cả các hạt đó sẽ bắt đầu tản ra. Và giờ chúng bị dàn trải khắp nơi.
Now if I take some samples, almost all the particles are living here. But if time passes, those particles start spreading out.
Giờ nếu tôi lấy mẫu, hầu hết các hạt nằm ở đây. Nhưng khi thời gian trôi, các hạt đó bắt đầu lan ra.
And all those things that happen to particles, the same thing happens to the probabilistic distribution. OK. We'll bust. OK.
Và mọi chuyện xảy ra với các hạt thì cũng xảy ra với phân phối xác suất. Được. Ta sẽ thoát. Được.
It's approximate. OK, so let's now take a break. And then we'll see some demos of what these techniques can do.
Nó chỉ là xấp xỉ. Giờ ta nghỉ giải lao nhé. Sau đó ta sẽ xem vài demo về những gì các kỹ thuật này làm được.
Two minute break.
Nghỉ hai phút.
OK, let's start again and see some demos of what this looks like in practice. So most of the demos we're going to see now are robot localization demos in one way or another.
Được rồi, ta bắt đầu lại và xem vài demo về việc này trông thế nào trong thực tế. Hầu hết các demo ta sắp xem đều là định vị robot theo cách này hay cách khác.
Sometimes, the robot will be a ghost in Pac-Man. In robot localization, you imagine you know the map, but you don't know the robot's position. So think, what is a hypothesis in this case?
Đôi khi robot sẽ là một con ma trong Pac-Man. Trong định vị robot, giả sử bạn biết bản đồ nhưng không biết vị trí của robot. Hãy nghĩ xem giả thuyết trong trường hợp này là gì?
That will usually tell you what the underlying variable x is that you're trying to track. If the hypothesis, I think the robot is here, in a known map, that's robot localization.
Điều đó thường cho bạn biết biến x cơ sở mà bạn đang cố theo dõi là gì. Nếu giả thuyết là, tôi nghĩ robot ở đây, trên một bản đồ đã biết, thì đó là định vị robot.
So x here, the underlying variable that you'd like to reason about, is the robot's location on the map, e, the evidence, observations might be something like range finder readings.
Vậy x ở đây, biến cơ sở mà bạn muốn suy luận, là vị trí của robot trên bản đồ, còn e, bằng chứng, quan sát, có thể là các số đọc của cảm biến đo khoảng cách.
So in a lot of these cases, as shown here, you have some robot.
Trong nhiều trường hợp như vậy, như hình này, có một con robot.
You're not really sure where it is, and the evidence you get is you have a 360 range finder that says, far from an obstacle, far from an obstacle, close, close, close close.
Bạn không chắc nó đang ở đâu, và bằng chứng bạn nhận được là một thiết bị đo khoảng cách 360 độ báo: xa vật cản, xa vật cản, gần, gần, gần, gần.
That tells you there's a wall behind you and to the right.
Điều đó cho biết có một bức tường ở phía sau và bên phải bạn.
In these cases with real robot localizations, the state space in the readings are typically continuous. There's some range finder reading, which is a real number.
Trong các trường hợp định vị robot thực tế, không gian trạng thái và các số đo thường là liên tục. Có một số đo từ thiết bị đo khoảng cách, là một số thực.
And your state space is some map with maybe polygonal objects or something, depending on how that's specified for you. And you're somewhere in there. The robot can be at any real location.
Còn không gian trạng thái là một bản đồ, có thể gồm các vật thể đa giác hay gì đó, tùy cách người ta mô tả nó. Và bạn đang ở đâu đó trong đó. Robot có thể ở bất kỳ vị trí thực nào.
So what's really appealing to you is particle filtering. But of course, your particles can't be everywhere in a real space. So it might look something like what's shown here.
Vậy thứ thật sự hấp dẫn ở đây là lọc hạt. Nhưng tất nhiên, các hạt không thể phủ khắp một không gian thực. Nên nó sẽ trông giống như hình này.
There's a map. The gray areas are obstacles, walls, furniture, and so on. And all the little red dots are places the robot might be.
Có một bản đồ. Vùng màu xám là vật cản, tường, đồ đạc, v.v. Và những chấm đỏ nhỏ là các vị trí robot có thể đang ở.
This is a case where the particles are smeared all over the map.
Đây là trường hợp các hạt rải khắp bản đồ.
And if you stare really hard and the resolution is high enough, you can see there's a lot of places that don't have any particles. And what if the robot's there?
Nếu bạn nhìn kỹ và độ phân giải đủ cao, bạn sẽ thấy có nhiều chỗ không có hạt nào. Vậy nếu robot ở đúng chỗ đó thì sao?
Well, in general, in particle filtering applications, you're going to have a cloud of these things. And you're going to ask questions like, well, what's the average location?
Nhìn chung, trong các ứng dụng lọc hạt, bạn sẽ có một đám mây các hạt này. Và bạn sẽ hỏi những câu như, vị trí trung bình là gì?
So even if there's no particle in the exact correct hypothesis, it's still very useful, because you're working with a whole cloud of them. So particle filtering is a main technique.
Nên dù không có hạt nào nằm đúng giả thuyết chính xác, nó vẫn rất hữu ích, vì bạn đang làm việc với cả đám mây hạt. Vậy lọc hạt là một kỹ thuật chủ chốt.
Let me show you a couple examples. This is an example from University of Washington where you're going to see a robot. So there's actually a robot in this map that's shown.
Tôi sẽ cho các bạn xem vài ví dụ. Đây là một ví dụ từ Đại học Washington nơi bạn sẽ thấy một con robot. Thực sự có một con robot trong bản đồ này.
You don't know where it is, so there's particles everywhere to begin with and a whole bunch of them.
Bạn không biết nó ở đâu, nên ban đầu có hạt ở khắp nơi, rất nhiều hạt.
And the robot is going to get readings that say there's an obstacle in front of you, but nothing to your right or left.
Robot sẽ nhận các số đo cho biết có vật cản ở phía trước, nhưng không có gì bên phải hay bên trái.
And so it's going to get these distances, which are shown here as blue lines. And of course, not only don't you know where the robot is, you also don't know which direction it's pointed.
Và nó nhận các khoảng cách này, được vẽ ở đây bằng các đường xanh. Và tất nhiên, không chỉ không biết robot ở đâu, bạn còn không biết nó đang quay về hướng nào.
So your hypothesis is not just a dot. It's sort of a dot with an arrow. And as the robot moves around, new readings come streaming in.
Nên giả thuyết của bạn không chỉ là một chấm. Mà là một chấm có mũi tên. Khi robot di chuyển, các số đo mới liên tục đến.
So if I say, oh, hey, I'm pretty sure there's a wall behind me. Well, I could be here. I could be there. I could be there.
Giả sử tôi nói: tôi khá chắc có một bức tường sau lưng. Vậy tôi có thể ở đây. Tôi có thể ở đó. Hoặc ở đó.
I could be there. And then as I move around, I start to see, hey, wait a minute. There's not a stage here that I expected, and so I know I wasn't at that wall.
Hoặc ở đó nữa. Rồi khi tôi di chuyển, tôi bắt đầu thấy: khoan đã. Ở đây không có cái bục mà tôi dự đoán, nên tôi biết mình không ở bức tường đó.
And so I'm going to run this, and you can watch the particles. And each particle, think of like a hypothesis. Robot might be here.
Giờ tôi sẽ chạy nó, và các bạn có thể quan sát các hạt. Mỗi hạt hãy coi như một giả thuyết. Robot có thể ở đây.
And as you move around and you start to get evidence that's not consistent with all of those hypotheses, a lot of the samples are going to die out.
Và khi bạn di chuyển và bắt đầu nhận bằng chứng không nhất quán với tất cả các giả thuyết đó, nhiều mẫu sẽ biến mất.
They're going to die out by getting down weighted. And then during resampling, in general, they're going to not get reselected. OK, so let's go. Right now, it has no idea where the robot is.
Chúng biến mất do bị giảm trọng số. Rồi khi lấy mẫu lại, nhìn chung chúng sẽ không được chọn lại. Được, bắt đầu nào. Hiện giờ nó chưa biết robot ở đâu.
There's some most likely hypothesis, but it has no idea.
Có vài giả thuyết khả dĩ nhất, nhưng nó chưa biết gì cả.
The robot's actually going down the corridor, and it's getting all these readings that say, wall to my side, wall to my side, wall to my side, so you'll notice that already it's gotten a whole bunch of readings of wall to my side as it's been moving forward.
Thực ra robot đang đi dọc hành lang, và nhận được hàng loạt số đo báo: tường bên cạnh, tường bên cạnh, tường bên cạnh, nên bạn sẽ thấy là nó đã nhận rất nhiều số đo tường bên cạnh khi nó tiến về phía trước.
So what does it know? It knows that there's a wall next to it, and that it was able to move forward along the wall for a while.
Vậy nó biết gì? Nó biết có một bức tường bên cạnh, và nó đã đi tới được dọc theo bức tường một đoạn.
And all these red dots that have survived are ones that are in locations where you would have moved past a wall for a while.
Và những chấm đỏ còn sống sót là những chấm ở các vị trí mà bạn có thể đã đi dọc một bức tường một đoạn.
So all the little rooms that aren't big enough to support that reading of a wall as you move forward, they don't have very many particles in them.
Còn các phòng nhỏ không đủ lớn để có số đo tường như vậy khi bạn đi tới, thì không có nhiều hạt trong đó.
And you'll see this distribution is going to start to collapse as you get more and more evidence as to where you are.
Và bạn sẽ thấy phân phối này bắt đầu co lại khi có ngày càng nhiều bằng chứng về vị trí của bạn.
So once you've seen a wall for a very, very long time off to your side, you know you're not in the square off to the left.
Một khi bạn đã thấy tường suốt rất, rất lâu ở bên cạnh, bạn biết mình không ở ô vuông phía bên trái.
So now, it's getting to the point where it knows it's along a long corridor. But it's not really sure whether it's on the left end or the right end.
Giờ thì nó đã đến mức biết mình ở dọc một hành lang dài. Nhưng nó chưa chắc mình ở đầu bên trái hay đầu bên phải.
And then watch what happens here. OK, now, he knows where he is. Let me back him up. OK.
Và hãy xem chuyện gì xảy ra. Được rồi, giờ nó biết mình ở đâu. Để tôi lùi lại một chút. Được.
Right here. Can I stop it? OK. Right here, if you had to guess you would say, well, the densest cluster maybe of points is over there on the right.
Ngay đây. Dừng lại được không? Được. Ngay đây, nếu phải đoán thì bạn sẽ nói, cụm điểm dày đặc nhất có lẽ nằm ở bên phải.
And you can see that's where the visualization has guessed the robot position is. The robot's continuing to go forward. One of two things will happen very soon.
Và bạn thấy đó là chỗ phần hiển thị đoán là vị trí của robot. Robot vẫn tiếp tục đi tới. Sắp tới sẽ xảy ra một trong hai điều.
Either it will get a range finder reading that says, there's a wall in front of me.
Hoặc nó nhận số đo báo rằng có một bức tường ngay trước mặt.
At which point, a whole bunch of dots to the left are going to disappear, because they're not consistent with that evidence. Or it's going to see more corridor.
Khi đó, cả loạt chấm bên trái sẽ biến mất, vì chúng không nhất quán với bằng chứng đó. Hoặc là nó sẽ thấy thêm hành lang.
And then a whole bunch of dots to the right are going to disappear, because they're not consistent with that evidence. And as soon as that happens, it's going to be pretty much localized.
Và khi đó rất nhiều chấm bên phải sẽ biến mất, vì chúng không nhất quán với bằng chứng đó. Và ngay khi điều đó xảy ra, nó gần như đã được định vị xong.
And it turns out, no wall appeared. Now, it knows where it is, and it can wander around. And there's this cloud around it.
Và hóa ra là không có bức tường nào xuất hiện. Giờ nó biết mình ở đâu, và nó có thể đi loanh quanh. Và có một đám mây quanh nó.
You'll notice anytime it turns, there's a bloom of uncertainty around its position. But now, we're basically tracking it. So that first phase was really localization. Where am I in this map?
Các em sẽ thấy mỗi khi nó rẽ, lại có một vùng bất định nở ra quanh vị trí của nó. Nhưng bây giờ, về cơ bản ta đang theo dõi nó. Vậy giai đoạn đầu thực sự là định vị. Tôi đang ở đâu trong bản đồ này?
And then once we were localized, monitoring our location once it had collapsed down from enough evidence is an ongoing thing that's more like robot tracking.
Và khi đã định vị xong, việc giám sát vị trí của mình sau khi phân bố đã co lại nhờ đủ bằng chứng là việc diễn ra liên tục, giống theo dõi robot hơn.
First, you're figuring out where you are. Then, you're tracking where you are as you go. But mathematically, it's all the same thing. All right, here's a laser range finder of this.
Đầu tiên, bạn xác định mình đang ở đâu. Sau đó, bạn theo dõi vị trí của mình khi di chuyển. Nhưng về mặt toán học, tất cả đều giống nhau. Được rồi, đây là máy đo khoảng cách laser của nó.
It goes by pretty quickly. But imagine each of these hypotheses is consistent with the evidence. And the robot knows by now, based on its movement pattern, that it's somewhere in the hallway.
Nó chạy khá nhanh. Nhưng hãy tưởng tượng mỗi giả thuyết này đều nhất quán với bằng chứng. Và đến giờ robot biết, dựa trên kiểu di chuyển của nó, rằng nó đang ở đâu đó trong hành lang.
And it knows it's about to turn into one of these two symmetric rooms. This is how I feel whenever I get off the soda elevator.
Và nó biết sắp rẽ vào một trong hai căn phòng đối xứng này. Tôi cũng cảm thấy y như vậy mỗi khi ra khỏi thang máy Soda.
And then it's either going to see a piece of furniture or not. If it sees a piece of furniture, it's going to be in the upper room.
Rồi nó sẽ thấy một món đồ nội thất hoặc không. Nếu thấy đồ nội thất, nó đang ở phòng phía trên.
And if not, it'll be in the lower room. And wipe out on the lower particles, because it saw the furniture. So this is sort of the way this goes.
Còn nếu không, nó ở phòng phía dưới. Và loại bỏ các hạt ở phòng dưới, vì nó đã thấy đồ nội thất. Vậy quá trình diễn ra đại khái như thế.
You have a bunch of particles. They represent, in this case, two primary groups of hypotheses. And then evidence comes in that deletes a whole bunch of those particles.
Bạn có một loạt hạt. Trong trường hợp này chúng biểu diễn hai nhóm chính của các giả thuyết. Rồi bằng chứng đến và xóa đi rất nhiều hạt trong số đó.
OK, any questions on that before I talk about — Yep?
Được rồi, có câu hỏi nào không trước khi tôi nói về — Em nào?
STUDENT
[INAUDIBLE] PROFESSOR: That's a great question. What if you know where the robot starts? You still want to do this, because you won't know where it is for long.
[KHÔNG NGHE RÕ] GIÁO SƯ: Câu hỏi rất hay. Nếu biết robot xuất phát từ đâu thì sao? Bạn vẫn muốn làm thế này, vì bạn sẽ không biết nó ở đâu được lâu.
Imagine it's basically like how we localize. I know exactly where I am.
Hãy tưởng tượng nó giống cách chúng ta định vị. Tôi biết chính xác mình đang ở đâu.
If I close my eyes and I just start walking, I will have a reasonable sense for a while, and then I'll probably hurt myself.
Nếu tôi nhắm mắt và cứ thế bước đi, tôi sẽ còn có cảm giác khá đúng một lúc, rồi có lẽ tôi sẽ tự làm mình đau.
And what happens is the robot, you give it a command like, go forward a foot. And it goes forward 11.3 inches. And then you have it turn, and it turns almost what expected.
Và điều xảy ra với robot là, bạn ra lệnh như là, tiến lên một foot. Và nó tiến lên 11,3 inch. Rồi bạn bảo nó quay, và nó quay gần đúng như mong đợi.
And these little errors start to accumulate. This is equivalent to a lapse in time. Over time, your uncertainty is going to bloom. And that distribution is going to flatten.
Và những sai số nhỏ này bắt đầu tích lũy. Điều này tương đương với thời gian trôi qua. Theo thời gian, độ bất định sẽ nở ra. Và phân phối đó sẽ dẹt đi.
Because your transition probability says wherever you are, if you move forward, you're going to be a unit forward with some noise. And that with some noise is going to add and add and add.
Vì xác suất chuyển của bạn nói rằng dù bạn ở đâu, nếu tiến lên, bạn sẽ ở cách một đơn vị phía trước, cộng thêm nhiễu. Và phần nhiễu đó cứ cộng dồn, cộng dồn mãi.
What you want to do is you still want to use something like particle filtering to track how that uncertainty grows and is then mitigated and reduced by the readings you get.
Điều bạn muốn làm là vẫn dùng một thứ như lọc hạt để theo dõi độ bất định tăng thế nào rồi được giảm nhẹ và thu hẹp lại nhờ các số đo bạn nhận được.
And so you could think, well, if I really know where I am, maybe I should use another technique.
Và bạn có thể nghĩ, nếu thật sự biết mình ở đâu, có lẽ nên dùng kỹ thuật khác.
But in fact, the value of particle filtering is especially high when you know where you are. And you'll notice in this here, the number of particles they use is adaptive.
Nhưng thực ra giá trị của lọc hạt đặc biệt cao khi bạn biết mình ở đâu. Và các em sẽ thấy ở đây, số hạt họ dùng là thích nghi.
And so you start with a bunch of particles, or relatively speaking, a bunch of particles here. You start with a bunch of particles, because you have to cover all these hypotheses.
Bạn bắt đầu với nhiều hạt, hoặc tương đối mà nói, nhiều hạt ở đây. Bạn bắt đầu với nhiều hạt, vì phải bao phủ tất cả các giả thuyết này.
You might as well actually have enumerated a grid of probabilities.
Thậm chí bạn có thể liệt kê hết một lưới xác suất.
But once you basically know where you are, you can just keep a cloud of hypotheses around you, which is basically like, I'm still there. I've drifted left. I've drifted right.
Nhưng khi về cơ bản đã biết mình ở đâu, bạn chỉ cần giữ một đám mây giả thuyết quanh mình, nghĩa là tôi vẫn ở đó. Tôi trôi sang trái. Tôi trôi sang phải.
Except instead of enumerating the hypotheses, you just blanket your nearby area with random samples. And that's really good, because it means you don't have to think about the local geometry or anything.
Chỉ có điều thay vì liệt kê các giả thuyết, bạn rải các mẫu ngẫu nhiên phủ kín vùng lân cận. Và điều đó rất tốt, vì bạn không cần nghĩ đến hình học cục bộ hay gì cả.
You just blast samples everywhere.
Bạn cứ rải mẫu khắp nơi.
OK, you'll notice the particles now, if I can make this go away, the particles now are starting to drop, because the more peaked your distribution, the fewer particles you need.
Các em sẽ thấy các hạt bây giờ, để tôi tắt cái này đi, các hạt đang bắt đầu giảm, vì phân phối của bạn càng nhọn thì càng cần ít hạt.
But you got to be really careful, because at some point, the math is going to tell you you are completely, completely sure you're at this particle. And remember that lone particle?
Nhưng phải thật cẩn thận, vì đến một lúc nào đó, phép toán sẽ bảo bạn rằng bạn hoàn toàn chắc chắn mình ở hạt này. Còn nhớ hạt đơn độc đó không?
It's bad when you have a lone particle. So you need to generally maintain a cloud of hypotheses to catch that uncertainty as it blooms. Any other questions? That was a great question.
Có một hạt đơn độc là điều tệ. Nên nói chung bạn cần duy trì một đám mây giả thuyết để bắt được độ bất định khi nó nở ra. Còn câu hỏi nào khác không? Đó là một câu hỏi rất hay.
Yep?
Em nào?
How do you determine the number of particles? That's a really hard question. There's no hard and fast rule.
Làm sao xác định số lượng hạt? Đó là câu hỏi rất khó. Không có quy tắc cứng nhắc nào.
Often in these environments where you're repeating these things, you can figure out what the right number of things is to track. It's going to depend on the complexity and the level of uncertainty.
Thường trong những môi trường mà bạn lặp lại các việc này, bạn có thể tìm ra số lượng phù hợp cần theo dõi. Nó sẽ phụ thuộc vào độ phức tạp và mức độ bất định.
And there's no hard and fast rule. There's some signs you don't have enough, like distributions collapsing.
Và không có quy tắc cứng nhắc nào. Có một số dấu hiệu cho thấy bạn chưa đủ, như phân phối bị sụp đổ.
And there's signs that you have too many, like particles are all lining up on top of each other.
Và có dấu hiệu cho thấy bạn dùng quá nhiều, như các hạt chồng hết lên nhau.
But there's no — I mean, there are some things that can be said about required number of samples. But in practice, it's hard to know. Yep?
Nhưng không có... Ý tôi là, có một vài điều có thể nói về số mẫu cần thiết. Nhưng trong thực tế thì khó biết. Bạn hỏi đi?
Great question. How does the robot move? In all of these things I've shown you, the robot's intended motion, meaning, the dynamics is known. Somebody is saying, move forward, or turn now, or whatever.
Câu hỏi hay. Robot di chuyển như thế nào? Trong tất cả những ví dụ tôi cho các bạn xem, chuyển động dự định của robot, tức là động lực học, đã được biết. Có ai đó bảo: tiến lên, hoặc rẽ đi, hay gì đó.
So there's no action selection. It is simply tracking what's going on. In actual robot planning, you would have to make the decision based on some other goals.
Nên không có việc chọn hành động. Nó chỉ đơn giản là theo dõi những gì đang xảy ra. Trong lập kế hoạch robot thực tế, bạn sẽ phải ra quyết định dựa trên một số mục tiêu khác.
Maybe you're trying to move a package from here to there. For this tracking, you know where the robot is trying to go in the form of the expected behavior under that transition probably.
Có thể bạn muốn chuyển một gói hàng từ đây đến đó. Với việc theo dõi này, bạn biết robot đang muốn đi đâu qua hành vi kỳ vọng theo xác suất chuyển trạng thái đó.
If the robot's trying to stand still, you're not going to get any new evidence, and you're never going to figure out where you are.
Nếu robot cố đứng yên, bạn sẽ không nhận được bằng chứng mới nào, và bạn sẽ không bao giờ biết mình đang ở đâu.
On the other hand, you won't actually accumulate any true uncertainty. OK, let me show you something else, which is pretty cool. It's called SLAM. It stands for simultaneous localization and mapping.
Mặt khác, thực ra bạn cũng sẽ không tích lũy thêm độ bất định thật sự nào. Giờ tôi cho các bạn xem một thứ khác khá hay. Nó gọi là SLAM. Viết tắt của simultaneous localization and mapping, tức định vị và lập bản đồ đồng thời.
This is where your hypothesis is not, I'm here on a known map, but, I'm here and I think the map looks like this. So you don't know the map.
Ở đây giả thuyết của bạn không phải là: tôi đang ở trên một bản đồ đã biết, mà là: tôi ở đây và tôi nghĩ bản đồ trông như thế này. Tức là bạn không biết bản đồ.
That means each particle is a map that you are drawing with a dot on it. OK? Instead of a grid of these things, there's some high dimensional space of maps and dots on them.
Nghĩa là mỗi hạt là một bản đồ mà bạn đang vẽ, với một chấm trên đó. Rõ chưa? Thay vì một lưới các thứ này, ta có một không gian nhiều chiều gồm các bản đồ và chấm trên đó.
So let's take a look. In this case, how do I visualize it?
Ta cùng xem nhé. Trường hợp này, trực quan hóa thế nào?
Well, I can't have each dot be a map anymore, but I can take all the hypotheses, each of which is a map with a red dot in it, and I can superimpose them according to a visualization.
Ta không thể để mỗi chấm là một bản đồ nữa, nhưng ta có thể lấy tất cả các giả thuyết, mỗi giả thuyết là một bản đồ có chấm đỏ, và chồng chúng lên nhau theo một cách hiển thị.
And so what you'll see is in addition to the ballooning out of where I am on the red dots, the map is also going to be blurry when I'm not really sure exactly where that wall was or which direction it went.
Và bạn sẽ thấy, ngoài việc các chấm đỏ loang rộng ra về vị trí của tôi, bản đồ cũng sẽ bị mờ khi tôi không chắc bức tường đó chính xác ở đâu hay đi theo hướng nào.
And so as you go, you're mapping, but you're not totally sure how long this corridor is. And notice that flash was you had a whole bunch of particles that diverged.
Khi đi tiếp, bạn đang lập bản đồ, nhưng không chắc hành lang này dài bao nhiêu. Và chú ý cú nháy đó là lúc có cả loạt hạt phân kỳ.
So you can see here, your space, your estimated position is in red, but you're not really sure where you are.
Bạn thấy đây, vị trí ước lượng của bạn màu đỏ, nhưng bạn không thật sự chắc mình đang ở đâu.
And that's leading to not really being sure how far this wall in front of you is, because you don't know where it is with respect to the rest of the map.
Điều đó dẫn đến việc không chắc bức tường trước mặt cách bao xa, vì bạn không biết nó nằm ở đâu so với phần còn lại của bản đồ.
And as you start going around this loop, what's going to happen? Right? Right now, you've gone around in a circle.
Và khi bạn bắt đầu đi vòng quanh vòng lặp này, chuyện gì sẽ xảy ra? Đúng không? Giờ bạn đã đi một vòng tròn.
And as soon as you see your starting point, a whole bunch of hypotheses that perhaps this is a big spiral are going to vanish, and everything's going to snap tight right about now.
Và ngay khi bạn thấy lại điểm xuất phát, cả loạt giả thuyết cho rằng đây có thể là một hình xoắn ốc lớn sẽ biến mất, và mọi thứ sẽ khớp chặt lại ngay lúc này.
So this is a case of maintaining a whole bunch of different kinds of uncertainty over multiple variables and using them to disambiguate. Let me show you another vehicle of this, another video.
Đây là trường hợp duy trì nhiều loại bất định khác nhau trên nhiều biến và dùng chúng để khử mơ hồ. Tôi cho các bạn xem một phương tiện khác, một video khác.
So you can see here, again, this is showing its trajectory. It's on one of these trajectories.
Bạn thấy đây, nó cũng đang hiển thị quỹ đạo của mình. Nó đang ở trên một trong các quỹ đạo này.
But as it goes around, it gets less and less sure exactly where it is, until it sees its starting position.
Nhưng khi đi vòng, nó càng lúc càng kém chắc về vị trí chính xác, cho đến khi thấy lại vị trí xuất phát.
And suddenly, everything goes rectilinear here, and a lot of those hypotheses, which correspond to having drifted when in fact you didn't or whatever it is, go away.
Và đột nhiên mọi thứ thẳng hàng vuông góc ở đây, và nhiều giả thuyết, vốn tương ứng với việc bị trôi trong khi thực tế không trôi, hay gì đó, biến mất.
And you can see there's a bunch of snapping to rectilinear shape that happens when you see reference points. Localization and mapping, it's super cool.
Và bạn thấy có nhiều chỗ bị kéo về dạng thẳng góc khi nhìn thấy các điểm tham chiếu. Định vị và lập bản đồ, thật sự rất tuyệt.
Any questions on the localization and mapping? And then I'm going to leave you with one thought on how this is going to apply to your projects where you'll have more than one variable.
Có câu hỏi nào về định vị và lập bản đồ không? Rồi tôi sẽ để lại cho các bạn một ý nghĩ về việc điều này áp dụng vào các project của các bạn thế nào khi bạn có nhiều hơn một biến.
Let's quickly take a look at projects here. The general case of a hidden Markov model, so what is a hidden Markov model?
Ta xem nhanh các project ở đây. Trường hợp tổng quát của mô hình Markov ẩn, vậy mô hình Markov ẩn là gì?
It's a super simple Bayes net where you have x and evidence, but it's interesting because it's replicated across time.
Đó là một mạng Bayes rất đơn giản gồm x và bằng chứng, nhưng thú vị ở chỗ nó được lặp lại qua thời gian.
You can also take more interesting Bayes nets, which have a bunch of variables with dependencies, and replicate them across time.
Bạn cũng có thể lấy những mạng Bayes thú vị hơn, có nhiều biến với các phụ thuộc, và lặp lại chúng qua thời gian.
This is popular for things like medical diagnosis, where there's a bunch of different underlying things. They have connections between them. They all evolve over time, oxygen levels, heart levels, whatever.
Cách này phổ biến cho những việc như chẩn đoán y khoa, nơi có nhiều yếu tố nền khác nhau. Chúng có liên kết với nhau. Tất cả đều biến đổi theo thời gian: nồng độ oxy, nhịp tim, v.v.
For DBNs, dynamic Bayes nets, you want to track multiple variables over time, which have correlations amongst them, using multiple sources of evidence.
Với DBN, tức mạng Bayes động, bạn muốn theo dõi nhiều biến theo thời gian, có tương quan với nhau, bằng cách dùng nhiều nguồn bằng chứng.
The idea here is you're going to take instead of this tiny little Bayes net and replicate it, you're going to take whatever fixed Bayes net you have and replicate that at each time step.
Ý tưởng ở đây là thay vì lấy mạng Bayes nhỏ xíu này rồi lặp lại, bạn lấy bất kỳ mạng Bayes cố định nào bạn có và lặp lại nó ở mỗi bước thời gian.
And you're going to specify not only how things interact within time, but across time. So here's an example of that.
Và bạn sẽ chỉ rõ không chỉ các thành phần tương tác thế nào trong cùng thời điểm, mà cả giữa các thời điểm. Đây là một ví dụ.
Let's say you had two ghosts instead of one, and you have sonar reading that said, I am very far from the red ghost sound, but it seems like I'm really close to the blue ghost sound.
Giả sử bạn có hai con ma thay vì một, và có số đo sonar cho biết: tôi ở rất xa âm thanh của ma đỏ, nhưng có vẻ tôi ở rất gần âm thanh của ma xanh.
Well, you could have ghost a and ghost b, which are two different random variables. Each of which has an observation. And this could replicate across time. So here's time one, which has the variables.
Bạn có thể có ma a và ma b, là hai biến ngẫu nhiên khác nhau. Mỗi biến đều có một quan sát. Và điều này có thể lặp lại qua thời gian. Đây là thời điểm một, có các biến.
And then at time two, those variables repeat. And you can unroll this network as far as you want.
Rồi ở thời điểm hai, các biến đó lặp lại. Và bạn có thể trải mạng này ra bao xa tùy ý.
This is what you're going to have in your projects where the thing you're going to reason over is where are multiple ghosts on the evidence of multiple sonar readings?
Đây là thứ bạn sẽ có trong các project của mình. nơi bạn sẽ suy luận về vị trí của nhiều con ma dựa trên bằng chứng từ nhiều số đọc sonar?
So I'm going to show you what this looks like in two demos, and then we'll wrap up for today.
Em sẽ cho các bạn xem nó trông thế nào qua hai demo, rồi chúng ta sẽ kết thúc buổi hôm nay.
All right, so here is Pac-Man. I'm going to control it. And what you're going to see is sonar readings.
Được rồi, đây là Pac-Man. Em sẽ tự điều khiển nó. Và các bạn sẽ thấy các số đọc sonar.
These are down in the lower right. Actually, this is super hard to play. Those numbers in the lower right show you for each ghost color how far you are.
Chúng nằm ở góc dưới bên phải. Thật ra chơi cái này khó kinh khủng. Các con số ở góc dưới bên phải cho biết với mỗi màu ma thì mình đang cách bao xa.
It's a noisy signal. So I'm going to try to hunt down the blue ghost. OK, that's the wrong way. That's the wrong way.
Tín hiệu này có nhiễu. Em sẽ thử săn con ma xanh dương. Ồ, sai hướng rồi. Sai hướng rồi.
That's really the wrong way. This is super hard. OK, he's here somewhere. Got him.
Thật sự sai hướng rồi. Khó kinh khủng. Được rồi, nó ở đâu đó quanh đây. Bắt được rồi.
OK. Now I'm going to go try to track down another ghost. Anyway. It's very hard to know where the ghosts are given these readings.
OK. Giờ em sẽ thử lần theo một con ma khác. Dù sao thì. Rất khó biết các con ma ở đâu chỉ từ những số đọc này.
The best I can do is, it looks like I'm getting close. It looks like I'm getting far. I can play hot cold with these ghosts.
Em chỉ làm được là: có vẻ mình đang tới gần. Có vẻ mình đang xa dần. Em có thể chơi trò nóng lạnh với mấy con ma này.
But you can take these readings and a model of the ghost behavior and synthesize them into a localization of the ghost. And that's going to look something like this.
Nhưng bạn có thể lấy các số đọc này cùng mô hình hành vi của ma rồi tổng hợp chúng thành một định vị cho con ma. Và nó sẽ trông như thế này.
All right. As you can see here, these are clouds that represent your beliefs over the ghost location. And you might think, well, that's great. You're running four HMMs.
Được rồi. Như các bạn thấy, đây là những đám mây biểu diễn niềm tin của bạn về vị trí con ma. Có thể bạn nghĩ: vậy là tuyệt rồi. Bạn đang chạy bốn HMM.
OK, it's still super annoying. You're running four HMMs.
OK, vẫn rất phiền. Bạn đang chạy bốn HMM.
In fact, the ghost dynamics in the project will be such that they sometimes do things like go towards each other or disperse and go away from each other.
Thực ra, động lực của ma trong project sẽ khiến đôi khi chúng tiến lại gần nhau hoặc tản ra và đi xa nhau.
So the hypotheses you are tracking are multiple ghost locations simultaneously. Each hypothesis is this ghost is here. This ghost is here. This goes is here.
Vì vậy các giả thuyết bạn đang theo dõi là vị trí của nhiều con ma cùng lúc. Mỗi giả thuyết là: con ma này ở đây. Con ma này ở đây. Con ma này ở đây.
So the event space is very big, but a particle is very simple. Here's what I think is going on. Also, here's what I think is going. Also, here's what I think is going on.
Không gian sự kiện rất lớn, nhưng một hạt thì rất đơn giản. Đây là điều tôi nghĩ đang xảy ra. Và đây cũng là điều tôi nghĩ đang xảy ra. Và đây cũng vậy.
And you have 1,000 of those hypotheses.
Bạn có 1.000 giả thuyết như thế.
And even though it's a high dimensional space, they cover a lot of different ghost positions and let you compute these marginals that you can use to chase the ghost down.
Và dù là không gian nhiều chiều, chúng bao phủ rất nhiều vị trí khác nhau của ma và cho phép bạn tính các phân phối biên để dùng đuổi theo con ma.
All right, that's your project. We'll see you next time for starting our unit on machine learning.
Được rồi, đó là project của các bạn. Hẹn gặp lại các bạn buổi sau để bắt đầu phần học máy.
Đă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.