Video
Đăng bởi Ban biên tập OpenER ·
Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
[INTERPOSING VOICES] GIREEJA RANADE: OK. Let's get started.
[NHIỀU NGƯỜI NÓI CHEN NHAU] GIREEJA RANADE: Được rồi. Bắt đầu thôi.
So it's the last lecture for 16A. Congratulations! You all made it. You survived, good job.
Đây là buổi học cuối cùng của 16A. Chúc mừng các bạn! Các bạn đã làm được rồi. Các bạn đã vượt qua, giỏi lắm.
[APPLAUSE] It's been a good semester. Thank you, everyone.
[VỖ TAY] Đó là một học kỳ tốt. Cảm ơn tất cả mọi người.
And a big, big thanks to all of the TAs and ASEs because, you know, this would not be possible without the tremendous amount of work that every single person on the TA staff, every single ASE, every single lab assistant, every single person who helped in office hours, every single person in the EEG's department's staff who painstakingly printed
Và xin cảm ơn thật nhiều các TA và ASE vì khóa học này sẽ không thể diễn ra nếu thiếu khối lượng công việc khổng lồ của từng người trong đội TA, từng ASE, từng trợ giảng lab, từng người đã giúp trong giờ office hours, từng nhân viên của khoa EE đã tỉ mỉ in
out 1,100 exams so every one of you could take the exam. The fabulous people at ETS who make sure that the webcasts are up and running for us.
1.100 bài thi để mỗi bạn đều có bài để thi. Cả những người tuyệt vời ở ETS đảm bảo webcast luôn hoạt động cho chúng ta.
They've all been working super hard, and this would not work at this scale without any of them. Of course, it hasn't been perfect. There's been ups and downs.
Mọi người đều đã làm việc rất chăm chỉ, và khóa học quy mô này sẽ không chạy được nếu thiếu ai trong số họ. Tất nhiên, mọi thứ không hoàn hảo. Có lúc lên lúc xuống.
Stuff has gone wrong in places. But thanks to everyone and thanks for everything that you've been doing to make this good.
Có những chỗ đã trục trặc. Nhưng cảm ơn mọi người, và cảm ơn tất cả những gì các bạn đã làm để khóa học tốt hơn.
And thanks to all of the TAs and all of the ASEs and all of the staff who've been working really hard also to make this a possibility.
Cảm ơn tất cả các TA, các ASE và toàn bộ nhân viên đã làm việc rất vất vả để khóa học này có thể diễn ra.
So with that, we're going to try and wrap up the entire semester today.
Vậy nên hôm nay chúng ta sẽ cố gắng tổng kết cả học kỳ trong một buổi.
And today's class is going to be basically going back to the very beginning of class and talking about what we talked about in Module 1 again.
Buổi hôm nay về cơ bản là quay lại ngay đầu môn học và nói lại về những gì chúng ta đã học ở Module 1.
But also pointing a little bit towards the future and giving you a hint of what is to come in the rest of your classes that you will be taking in the department.
Nhưng cũng hướng một chút về tương lai và gợi ý cho các bạn những gì sắp tới trong các môn còn lại mà các bạn sẽ học trong khoa.
So this meme is actually a meme that was made by one of the previous semesters. And I think it's just a great reminder of Module 1. I think it's actually quite funny.
Meme này thực ra do một học kỳ trước làm ra. Tôi nghĩ nó nhắc lại Module 1 rất hay. Tôi thấy nó khá buồn cười.
It takes a minute — took a minute for me to get it when I first saw it. But it's one of the ones that I really like.
Phải mất một lúc — lần đầu thấy tôi cũng mất một lúc mới hiểu. Nhưng đó là một trong những cái tôi thích nhất.
So I thought it would be fun to share. Especially because what I really want to start off talking about in today's lecture is ONP for imaging.
Nên tôi nghĩ chia sẻ sẽ vui. Nhất là vì điều tôi muốn mở đầu bài giảng hôm nay là ONP cho bài toán ảnh.
So could I switch to the dot cams, please? Thank you.
Cho tôi chuyển sang dot cam nhé. Cảm ơn.
So last time, we've talked about this ONP algorithm. And what this ONP algorithm is talking about is it's saying, well, you have a received signal. There's a bunch of candidate signals that are transmitting.
Lần trước chúng ta đã nói về thuật toán ONP này. Thuật toán ONP nói rằng, bạn có một tín hiệu thu được. Có nhiều tín hiệu ứng viên đang phát.
And you don't know which of them are transmitting and which ones aren't. There's millions of candidate signals. But only a handful, say, five or 10 of them are actually transmitting.
Và bạn không biết cái nào đang phát và cái nào không. Có hàng triệu tín hiệu ứng viên. Nhưng chỉ một số ít, chẳng hạn năm hoặc 10, thực sự đang phát.
And you want to figure out how to identify which devices are transmitting, even though you have far more unknowns than you actually have equations. That's the ONP setup that we actually talked about.
Và bạn muốn tìm cách xác định thiết bị nào đang phát, dù số ẩn số nhiều hơn rất nhiều so với số phương trình. Đó là bài toán ONP mà chúng ta đã nói.
And what is the ONP algorithm? Let me — can people read this?
Vậy thuật toán ONP là gì? Để tôi — mọi người đọc được không?
Yes? No? Bigger?
Được? Không? Phóng to hơn nhé?
Okay.
Được rồi.
So what are we saying? The ONP algorithm says, well, first, what is our list of signals that we know are present? It's empty.
Vậy chúng ta đang nói gì? Thuật toán ONP nói rằng, trước hết, danh sách các tín hiệu mà ta biết chắc là có mặt là gì? Nó rỗng.
x represents the signal. Let's list the signals that we know are present. This is empty because when we start, we don't know who is present, who isn't.
x biểu diễn tín hiệu. Hãy liệt kê các tín hiệu mà ta biết là có mặt. Danh sách này rỗng vì lúc bắt đầu, ta không biết ai có mặt, ai không.
And what is the unexplained part of our signal? The unexplained part of our signal is basically the entire signal. Because we haven't identified any signatures that we know are present for sure.
Còn phần chưa được giải thích của tín hiệu là gì? Phần chưa được giải thích của tín hiệu về cơ bản là toàn bộ tín hiệu. Vì ta chưa xác định được dấu hiệu nào mà ta biết chắc là có mặt.
So our unexplained part, or this error vector E, is the entire received signal. And the list of signatures that are present is basically the empty matrix. Then what do you do?
Nên phần chưa giải thích, hay vectơ sai số E, là toàn bộ tín hiệu thu được. Còn danh sách các signature có mặt về cơ bản là ma trận rỗng. Rồi làm gì tiếp?
You say, well, let me take the unexplained part. In the first iteration, the unexplained part is basically the entire received signal.
Bạn nói, hãy lấy phần chưa được giải thích. Ở lần lặp đầu tiên, phần chưa được giải thích về cơ bản là toàn bộ tín hiệu thu được.
And look at the inner products, or the cross correlations. Remember, it's important to note that inner products and cross correlations are not different things, really.
Rồi xét các tích vô hướng, hay các tương quan chéo. Hãy nhớ, quan trọng là tích vô hướng và tương quan chéo thực ra không phải là hai thứ khác nhau.
Cross correlations are just a series of shifted inner products. So I got some questions about why cross correlation? Why inner product?
Tương quan chéo chỉ là một chuỗi các tích vô hướng với tín hiệu dịch. Tôi nhận được vài câu hỏi: tại sao tương quan chéo? Tại sao tích vô hướng?
The reason we use these terminologies interchangeably is that cross correlation is just inner products have shifted signals. So this terminology basically means the same thing. Don't worry about using either one.
Lý do ta dùng hai thuật ngữ này thay thế nhau là vì tương quan chéo chỉ là tích vô hướng với các tín hiệu đã dịch. Nên về cơ bản hai thuật ngữ có cùng nghĩa. Đừng lo dùng cái nào.
Inner product means that you have no shift between them. Cross correlation means that your signals are potentially shifting.
Tích vô hướng nghĩa là không có độ dịch giữa chúng. Tương quan chéo nghĩa là các tín hiệu có thể bị dịch.
So here, in this case, when we don't really have to worry about any time delays, what we're going to do is we're going to say, let's take an inner product with every single candidate signature.
Ở đây, trong trường hợp này, khi ta không thật sự phải lo về độ trễ thời gian, việc ta sẽ làm là lấy tích vô hướng với từng signature ứng viên.
And I find that signature that produces the largest inner product. This word arg max is short form for the maximizing argument. Argument is here is basically these Si's.
Và tìm signature cho tích vô hướng lớn nhất. Từ arg max là viết tắt của đối số làm cực đại. Đối số ở đây về cơ bản là các Si này.
These Si's are changing. So what this notation means is it says find that signature that maximizes this inner product. Let's call that S max.
Các Si này thay đổi. Nên ký hiệu này có nghĩa là hãy tìm signature làm cực đại tích vô hướng này. Ta gọi nó là S max.
After this, you say, well, we declare that S max is present. So we add this S max to our list of potential devices.
Sau đó, ta tuyên bố rằng S max có mặt. Vậy ta thêm S max này vào danh sách các thiết bị tiềm năng.
We say that S max is now a device that is present, and we basically update our list. The first time we're doing this, this matrix is just going to be a column.
Ta nói S max giờ là một thiết bị đang có mặt, và về cơ bản ta cập nhật danh sách của mình. Lần đầu tiên làm việc này, ma trận này chỉ là một cột.
Because it was initially empty. There was no signature. So the first signature's a column. The second iteration you will have a matrix with two columns.
Vì ban đầu nó rỗng. Chưa có signature nào. Nên signature đầu tiên là một cột. Ở lần lặp thứ hai, bạn sẽ có ma trận hai cột.
The third iteration you will have a matrix with three columns, so on, and so forth.
Ở lần lặp thứ ba, bạn sẽ có ma trận ba cột, và cứ thế tiếp tục.
Once you have this matrix, then you say, well, how do these signatures together — if it's the first iteration, you just have one signature. If it's the second iteration, you have two signatures.
Khi có ma trận này rồi, bạn hỏi: các signature này kết hợp lại thì sao — nếu là lần lặp đầu thì chỉ có một signature. Nếu là lần lặp thứ hai thì có hai signature.
How do these collectively explain what the unexplained signal is doing? How does it collectively explain the received signal?
Chúng cùng nhau giải thích được phần tín hiệu chưa được giải thích đến đâu? Chúng cùng nhau giải thích tín hiệu nhận được đến đâu?
So you say project R on to the columns of S. Right? Notice we're not saying Project E.
Vậy ta chiếu R lên các cột của S. Đúng không? Để ý là ta không nói chiếu E.
We're saying project R, which is the entire received signal, onto the columns of S. Because basically, this is saying, using the linear combinations of the columns of S, how close can you get to R?
Ta nói chiếu R, tức toàn bộ tín hiệu nhận được, lên các cột của S. Vì về cơ bản, điều này nói rằng, dùng các tổ hợp tuyến tính của các cột của S, bạn có thể tiến gần R đến mức nào?
So you do that. And then you say, well, let me get that projection. Let me remove it from R. And that gives me my remaining unexplained portion.
Vậy ta làm vậy. Rồi ta nói, lấy phép chiếu đó, trừ nó khỏi R. Và nó cho ta phần còn lại chưa được giải thích.
Once you have this, you've done the best you can do explaining with the signals you've picked out so far. Go back and pick out the next loudest signal.
Khi có được nó, bạn đã làm hết sức có thể để giải thích bằng các tín hiệu mà bạn đã chọn cho đến giờ. Quay lại và chọn tín hiệu lớn nhất kế tiếp.
OK? And you asked many good questions about how and when to stop. And we had some answers for this.
OK? Và các bạn đã hỏi nhiều câu hay về cách thức và lúc nào thì dừng. Và ta đã có vài câu trả lời.
We said, well, you can say that if I know the number of devices that are going to be talking, I know that there's 10 devices that are talking.
Ta nói, nếu biết số thiết bị đang truyền, giả sử biết có 10 thiết bị đang truyền.
After I do this 10 times, I stop. Or I can look at the magnitude of this error vector E.
Sau khi làm 10 lần, tôi dừng. Hoặc tôi có thể xem độ lớn của vectơ sai số E này.
And after that magnitude gets super small, it's so small that it could only really be some kind of interference or noise. Then I say, OK, I'm going to stop.
Khi độ lớn đó trở nên rất nhỏ, nhỏ đến mức chỉ có thể là nhiễu hay can nhiễu nào đó. Thì tôi nói, OK, tôi sẽ dừng.
At the end of lecture today, we're going to talk about validation. And this will give you another way of trying to figure out how to potentially stop this ONP algorithm.
Cuối buổi học hôm nay, ta sẽ nói về validation. Và nó sẽ cho bạn một cách khác để tìm cách dừng thuật toán OMP này.
So today, we are going to get to ONP for imaging and validation.
Vậy hôm nay, ta sẽ đến với OMP cho ảnh và validation.
These are the two ideas that I want to get across. So going back to Module 1, where we talked a lot about imaging, you did imaging of fairly large images.
Đây là hai ý tưởng tôi muốn truyền đạt. Quay lại Module 1, nơi ta nói nhiều về chụp ảnh, các bạn đã chụp những ảnh khá lớn.
Right? So let's say you are trying to image a very large image.
Đúng không? Giả sử bạn muốn chụp một ảnh rất lớn.
Say you had an image that is 100 by 100 pixels.
Giả sử ảnh có kích thước 100 x 100 pixel.
OK?
OK?
In Module 1, to be able to image a 100 by 100 image, to be able to take a picture of it, to be able to recreate it, how many measurements did you need to take?
Ở Module 1, để chụp một ảnh 100 x 100, để chụp được nó và dựng lại nó, bạn cần thực hiện bao nhiêu phép đo?
Anyone remembers?
Có ai nhớ không?
If you had 10 to the 4 pixels in your image, how many measurements were needed? 10 to the 4, right? That's what you did in the first lab of the class.
Nếu ảnh có 10^4 pixel, thì cần bao nhiêu phép đo? 10^4, đúng không? Đó là những gì các bạn làm ở bài lab đầu tiên của môn.
Now that we have more advanced techniques at our disposal, can there possibly be a way that we could do it in fewer measurements?
Giờ ta có các kỹ thuật tiên tiến hơn, liệu có cách nào để làm việc đó với ít phép đo hơn không?
And be able to reconstruct the image, even though we have, let's say, less data. So in Module 1, this required 10 to the 4 measurements.
Và vẫn dựng lại được ảnh, dù ta có ít dữ liệu hơn. Ở Module 1, việc này cần 10^4 phép đo.
Can we do with less? That's what we really want to try and figure out.
Ta có thể làm với ít hơn không? Đó là điều ta thực sự muốn tìm hiểu.
And, at some level, if we wanted to recover every single pixel exactly with absolutely no noise, is it possible to do it with less than 10 to the 4 measurements?
Và ở một mức nào đó, nếu muốn khôi phục từng pixel chính xác hoàn toàn, không có nhiễu, thì có thể làm với ít hơn 10 mũ 4 phép đo không?
No. For a general image, there's actually nothing we can do. But what if we had some side information?
Không. Với một ảnh bất kỳ, thực ra ta không làm gì được. Nhưng nếu ta có thêm thông tin phụ thì sao?
What if we knew our image is sparse?
Nếu ta biết ảnh của mình là thưa (sparse) thì sao?
What do I mean again by sparse? I mean that most of the pixels are black.
Nhắc lại, thưa nghĩa là gì? Nghĩa là hầu hết các pixel đều đen.
When you represent that numerically, it means that the pixel is basically — the pixel number is a zero. And there's some smaller number of non-zero pixels.
Khi biểu diễn bằng số, điều đó có nghĩa là pixel — giá trị pixel bằng không. Và có một số ít pixel khác không.
If you have this structure, then suddenly we're in a setup which seems a lot like the ONP set up, where we had one received signal. There's few things that are transmitting.
Nếu có cấu trúc này, thì bỗng nhiên ta ở trong một bài toán rất giống bài OMP, nơi ta có một tín hiệu nhận được. Có vài thiết bị đang truyền.
And the other ones are really quiet. So most of the alpha, there's zero in this case, here. Most of the alpha, they're zero. Some of them are non-zero.
Còn những thiết bị khác thì rất im lặng. Nên hầu hết các alpha ở đây đều bằng không. Hầu hết các alpha đều bằng không. Một số thì khác không.
And the number that is non-zero is far smaller than the number that is actually zero. So let's try and see how we can replicate this in this imaging setup.
Và số lượng khác không ít hơn nhiều so với số lượng bằng không. Vậy hãy xem ta có thể lặp lại điều này thế nào trong bài toán chụp ảnh này.
So let me represent our image as a vector just like you did in the Module 1 labs.
Tôi biểu diễn ảnh của ta như một vectơ giống như các bạn đã làm trong lab Module 1.
Let's say there is x10,000, some large number of pixels.
Giả sử có x10,000, một số lượng pixel lớn.
And now, we want to see what we can do with, say, a smaller number of measurements. So I don't really want to do out an example that has 10,000 variables.
Và giờ ta muốn xem có thể làm gì với số phép đo ít hơn. Tôi không muốn làm ví dụ có 10,000 biến.
Because then the entire electoral will go away in just writing it out. So I'm going to do a smaller example, but hopefully you'll get the gist of what I'm trying to say.
Vì khi đó cả cái bảng sẽ hết chỗ chỉ để viết nó ra. Nên tôi sẽ làm một ví dụ nhỏ hơn, nhưng hy vọng các bạn sẽ hiểu ý tôi.
So let's say we have the following setup where I have x1, x2, x3, x4, x5, x6, x7, x8, x9, x10.
Giả sử ta có thiết lập sau, trong đó tôi có x1, x2, x3, x4, x5, x6, x7, x8, x9, x10.
This is my image. And I want to take some number of measurements of it. Let's say I want to take four measurements.
Đây là ảnh của tôi. Và tôi muốn thực hiện một số phép đo nó. Giả sử tôi muốn đo bốn lần.
So I'm going to write this as 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 0 0 1 and 0 1 1 0.
Vậy tôi sẽ viết nó thành 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 0 0 1 và 0 1 1 0.
OK? So there's a structure to these measurements, if you can see. These first four columns only have 1 1 in them. And then the remaining six all have two ones in them.
OK? Các phép đo này có một cấu trúc, các em có thể thấy. Bốn cột đầu tiên chỉ có một số 1 trong mỗi cột. Còn sáu cột còn lại đều có hai số 1.
Right? But how many measurements does this matrix imply? How many measurements am I taking? How many columns are there?
Đúng không? Nhưng ma trận này cho biết có bao nhiêu phép đo? Tôi đang thực hiện bao nhiêu phép đo? Có bao nhiêu cột?
And how many rows are there?
Và có bao nhiêu hàng?
There's four rows and 10 columns, right? So there's 10 unknowns. That's why there's 10 columns. So I have columns C1, C2, C10.
Có bốn hàng và 10 cột, đúng không? Vậy có 10 ẩn số. Đó là lý do có 10 cột. Vậy tôi có các cột C1, C2, đến C10.
And I have four rows. So I have four measurements.
Và tôi có bốn hàng. Vậy tôi có bốn phép đo.
And let's say I take this mask, and just like you did in Module 1, I shine this mask onto this image and I get back a received vector.
Giả sử tôi lấy mặt nạ này, và giống như các em đã làm ở Module 1, tôi chiếu mặt nạ này lên bức ảnh và nhận lại một vectơ thu được.
And I get back this vector, let's say 1 2 0 1. So now I have four equations and 10 unknowns.
Giả sử tôi nhận lại vectơ này: 1 2 0 1. Vậy giờ tôi có bốn phương trình và 10 ẩn số.
This is not going to be solvable using our typical Module 1 solutions.
Hệ này không giải được bằng các cách giải thông thường của Module 1.
But what if I told you only two of the 10 pixels are non-zero?
Nhưng nếu tôi nói chỉ có hai trong 10 pixel khác không thì sao?
Most of them are actually going to be zero. Only two of them are non-zero.
Hầu hết chúng thực ra sẽ bằng không. Chỉ có hai pixel khác không.
How can we go about trying to understand this, solve this? Can we somehow use the ONP algorithm to follow the same strategy?
Làm sao để hiểu và giải bài toán này? Liệu ta có thể dùng thuật toán OMP theo cùng chiến lược không?
Every pixel is now playing the role of a device. And every column is basically corresponding to the contribution of a pixel in the received vector.
Giờ mỗi pixel đóng vai trò của một thiết bị. Và mỗi cột về cơ bản tương ứng với phần đóng góp của một pixel vào vectơ thu được.
Right? So take a minute. Think about it. Think about how this might be connected to ONP.
Đúng không? Các em dành một phút. Hãy suy nghĩ. Nghĩ xem điều này có thể liên hệ thế nào với OMP.
And see if there is a parallel here that you think is worth exploring. Feel free to talk to your neighbors. Just try and understand the set up here.
Và xem có điểm tương đồng nào mà các em thấy đáng khám phá không. Cứ trao đổi với bạn bên cạnh. Chỉ cần cố hiểu cách thiết lập ở đây.
[INTERPOSING VOICES] GIREEJA RANADE: OK.
[NHIỀU NGƯỜI NÓI CÙNG LÚC] GIREEJA RANADE: OK.
So does everyone see how this is parallel?
Mọi người có thấy điểm tương đồng này không?
Are there any questions about how this might actually parallel the ONP setup with the few devices transmitting in our received signal? Yes?
Có câu hỏi nào về việc nó tương đồng thế nào với bài toán OMP, khi chỉ có vài thiết bị phát trong tín hiệu thu được không? Em nói đi?
STUDENT
So in the ONP algorithm, we had a matrix full of gold codes. And we knew what the gold codes were. They were present in our relief signal.
Trong thuật toán OMP, ta có một ma trận gồm các gold code. Và ta biết các gold code đó là gì. Chúng có mặt trong tín hiệu thu được.
But — GIREEJA RANADE: We didn't know which gold codes were present. Right? We didn't know which devices were transmitting.
Nhưng — GIREEJA RANADE: Ta không biết gold code nào có mặt. Đúng không? Ta không biết thiết bị nào đang phát.
STUDENT
But we knew the gold codes for each device.
Nhưng ta biết gold code của từng thiết bị.
GIREEJA RANADE
We knew the gold codes for each device.
Ta biết gold code của từng thiết bị.
STUDENT
But in this case, when we're doing imaging, we don't necessarily know what the pixels [INAUDIBLE]..
Nhưng ở đây, khi chụp ảnh, ta không nhất thiết biết các pixel [KHÔNG NGHE RÕ].
GIREEJA RANADE
Yeah. The great point is you don't know what each pixel — the pixels aren't transmitting anything, right? It's not like there's a code associated with every pixel.
Vâng. Ý rất hay là em không biết mỗi pixel — các pixel đâu có phát gì cả, đúng không? Không có mã nào gắn với mỗi pixel.
So it's a slightly different setup in that sense. You're exactly right. So can we somehow parallel it, nonetheless? Excellent observation.
Nên theo nghĩa đó cách thiết lập hơi khác. Em nói hoàn toàn đúng. Vậy dù thế, ta có thể đối chiếu chúng không? Nhận xét rất tốt.
Yep?
Em nói đi?
STUDENT
I have a question about R1 vector. So when you do the error vector, do we R minus 1 or do we do R minus S times R1?
Em có câu hỏi về vectơ R1. Khi tính vectơ sai số, ta lấy R trừ 1 hay lấy R trừ S nhân R1 ạ?
GIREEJA RANADE
You're right. We actually do R minus S times R1.
Em nói đúng. Thực ra ta lấy R trừ S nhân R1.
You're right. Thank you.
Em đúng rồi. Cảm ơn em.
Typo on my part. Yes? Question?
Cô viết nhầm. Còn ai nữa? Câu hỏi?
STUDENT
Is the [INAUDIBLE] on the [INAUDIBLE] right? So that [INAUDIBLE]?
[KHÔNG NGHE RÕ] trên [KHÔNG NGHE RÕ] đúng không ạ? Vậy [KHÔNG NGHE RÕ]?
GIREEJA RANADE
Yes. The question is how is the math, basically like the gold codes have this property of being orthogonal to each other. They have all these nice structures. And where is this structure here?
Vâng. Câu hỏi là phần toán ở đây thế nào, tức là các gold code có tính chất trực giao với nhau. Chúng có nhiều cấu trúc đẹp. Vậy cấu trúc đó ở đâu trong bài này?
So all these are great questions. And it's right. It's not exactly a parallel. However, let's try and look at this, right?
Đây đều là những câu hỏi rất hay. Và em nói đúng. Nó không hoàn toàn song song. Tuy nhiên, ta thử xem nhé.
So when I have a matrix times a vector, I know this matrix times this vector is equal to this other vector, which is very similar to the setup here.
Khi tôi có một ma trận nhân với một vectơ, tôi biết ma trận này nhân vectơ này bằng một vectơ khác, rất giống cách thiết lập ở đây.
Right? So here, every column represents a signature.
Đúng không? Ở đây, mỗi cột là một đặc trưng riêng.
Instead of having every column here be a gold code, what we have here is every column basically represents this pixel's contribution to this received vector.
Thay vì mỗi cột ở đây là một gold code, thì ở đây mỗi cột về cơ bản biểu diễn phần đóng góp của pixel đó vào vectơ thu được.
Right? Because when I write this entire thing out, what is this matrix vector multiplication?
Đúng không? Vì khi tôi viết toàn bộ ra, phép nhân ma trận với vectơ này là gì?
This is C1 times X1 plus C2 times X2 plus C3 times X3 is equal to this received vector Y. Or let's call this received vector R.
Là C1 nhân X1 cộng C2 nhân X2 cộng C3 nhân X3 bằng vectơ thu được Y. Hay ta gọi vectơ thu được này là R.
And I have basically — so C1X1 plus C2X2 plus C3X3 plus C10X10 is equal to R.
Và về cơ bản ta có — C1X1 cộng C2X2 cộng C3X3 cộng C10X10 bằng R.
So here, if you compare these two, the X's are exactly like the alphas. And the C's are exactly like the S's. Does everyone see this?
Nếu so sánh hai bài này, các X giống hệt các alpha. Và các C giống hệt các S. Mọi người có thấy không?
So you can think about every column here as basically the signature of that pixel. If that pixel was on, then this signature would be present in your received signal.
Vậy ta có thể xem mỗi cột ở đây là đặc trưng riêng của pixel đó. Nếu pixel đó bật, thì đặc trưng này sẽ có mặt trong tín hiệu thu được.
If that pixel is off, if that's a zero, then this signature is not going to be present in your received signal. Does everyone see how the two problems are essentially equivalent?
Nếu pixel đó tắt, tức là bằng không, thì đặc trưng này sẽ không có mặt trong tín hiệu thu được. Mọi người có thấy hai bài toán về bản chất tương đương nhau không?
Of course, you don't want to set up a matrix where basically all of these columns are linearly dependent or exactly the same.
Tất nhiên, ta không muốn thiết lập một ma trận mà về cơ bản tất cả các cột này đều phụ thuộc tuyến tính hoặc giống hệt nhau.
Because then, you're not going to be able to identify the different columns through our inner product strategy. So there is some level of structure that you want to take in the measurement.
Vì khi đó, ta sẽ không thể phân biệt được các cột khác nhau bằng cách dùng tích vô hướng. Vì vậy cần có một mức độ cấu trúc nhất định trong phép đo mà bạn thực hiện.
However, we can actually go ahead and run the ONP algorithm even though there's far less than 10 measurements that are being taken here. Does everyone see the parallel?
Tuy nhiên, ta vẫn có thể chạy thuật toán OMP dù số phép đo ở đây ít hơn 10 rất nhiều. dù số phép đo ở đây ít hơn 10 rất nhiều. Mọi người thấy sự tương đồng chứ?
OK. So let's actually try and follow through with this. So why don't you start taking inner products of every single column with this received vector R.
OK. Giờ hãy thử làm theo từng bước nhé. Các bạn hãy bắt đầu tính tích vô hướng của từng cột với vectơ nhận được R.
So we'll follow our first step of the algorithm — is take inner products.
Đó là bước đầu tiên của thuật toán, tức là tính các tích vô hướng.
And we can do it quickly together, because these columns are so easy. If you take the inner part of the first column with this R, you're just going to get 1.
Ta có thể làm nhanh cùng nhau, vì các cột này rất đơn giản. Lấy tích vô hướng của cột đầu tiên với R, bạn chỉ được 1.
The second column — and this is just going to give you 2. The third column is going to give you 0. The fourth column is going to give you 1.
Cột thứ hai cho bạn 2. Cột thứ ba cho bạn 0. Cột thứ tư cho bạn 1.
Fifth column gives you 3. Sixth column gives you 1. The seventh column gives you 3.
Cột thứ năm cho bạn 3. Cột thứ sáu cho bạn 1. Cột thứ bảy cho bạn 3.
Eighth column gives you 1. This gives you 2. And this gives you 2. Right?
Cột thứ tám cho bạn 1. Cột này cho bạn 2. Và cột này cho bạn 2. Đúng không?
So what we saw was that inner product of R and C5 C3, C4, C5, C6, C7, C8, C9.
Vậy ta thấy tích vô hướng của R với C5 là 3 (C3, C4, C5, C6, C7, C8, C9 cũng đã tính).
This is equal to 3. And inner product of R and C7 is also equal to 3.
Nó bằng 3. Và tích vô hướng của R với C7 cũng bằng 3.
And these are the two largest inner products. I don't want to spend time doing out every single inner product. But if you couldn't follow along my quick inner product calculations, go and practice this.
Đây là hai tích vô hướng lớn nhất. Tôi không muốn mất thời gian tính từng tích vô hướng. Nhưng nếu bạn không theo kịp phép tính nhanh của tôi, hãy về luyện tập thêm.
It's good practice to have fluency with inner products. But now we have two different signatures. The columns are just like the signatures. We have two signatures that have the exact same impact.
Thành thạo tích vô hướng là một việc luyện tập tốt. Nhưng giờ ta có hai signature khác nhau. Các cột giống như các signature. Hai signature có tác động hoàn toàn giống nhau.
What do we do? We can just choose anyone. If they're exactly the same, this will never happen in a real scenario. This is just because I'm rigging this to make an easy class demo.
Ta làm gì đây? Ta cứ chọn đại một cái. Nếu chúng giống hệt nhau thì điều này sẽ không bao giờ xảy ra trong thực tế. Chỉ là tôi sắp đặt để có một ví dụ dễ cho buổi học này thôi.
But it doesn't matter. Just pick either one and continue on. So let's say C5 is present.
Nhưng không sao. Cứ chọn một cái rồi làm tiếp. Giả sử C5 có mặt.
So saying C5 is present is essentially saying that X5 is non-zero. Right? Because you have a C5X5 that is giving me my received vector R.
Nói C5 có mặt về cơ bản là nói X5 khác không. Đúng không? Vì C5X5 là thành phần tạo ra vectơ nhận được R.
So now I'm going to project R onto C5.
Giờ tôi sẽ chiếu R lên C5.
And I'm going to get my X5 hat to be basically C5 transpose C5 inverse C5 transpose times R. Right?
Và X5 hat của tôi sẽ bằng C5 transpose C5 nghịch đảo, nhân C5 transpose nhân R. Đúng không?
What are we doing? We're saying C5 is present. Let us use C5 to explain R. All I'm doing is this projection step of our algorithm, this step right here.
Ta đang làm gì? Ta nói C5 có mặt. Hãy dùng C5 để giải thích R. Tôi chỉ đang làm bước chiếu của thuật toán, chính là bước này đây.
OK?
OK?
So now, we have this is equal to 1 1 0 0 1 1 0 0 inverse 1 1 0 0 1 2 0 1.
Vậy ta có biểu thức này bằng 1 1 0 0 1 1 0 0 nghịch đảo 1 1 0 0 1 2 0 1.
Right? Because C5 is just equal to 1 1 0 0.
Đúng không? Vì C5 chỉ bằng 1 1 0 0.
What is C5 transpose times C5?
C5 transpose nhân C5 bằng bao nhiêu?
Or just take a minute to solve this out. Tell me what you get.
Hãy dành một phút tính thử. Cho tôi biết kết quả.
[INTERPOSING VOICES] GIREEJA RANADE: Yes?
[NHIỀU NGƯỜI NÓI CÙNG LÚC] GIREEJA RANADE: Vâng?
Question at the back?
Câu hỏi ở phía sau?
STUDENT
[INAUDIBLE].
[KHÔNG NGHE RÕ].
GIREEJA RANADE
You ought to speak up.
Bạn nói to lên nhé.
STUDENT
We have to include the multiplication by C5 [INAUDIBLE]?
Ta có phải nhân thêm với C5 [KHÔNG NGHE RÕ] không ạ?
GIREEJA RANADE
This is just the coefficient. So we're going to subtract X5 hat times C5 from the received signal. This is just the coefficient.
Đây chỉ là hệ số thôi. Ta sẽ trừ X5 hat nhân C5 khỏi tín hiệu nhận được. Đây chỉ là hệ số.
Yes?
Vâng?
STUDENT
[INAUDIBLE]?
[KHÔNG NGHE RÕ]?
GIREEJA RANADE
No. That would not be a good idea.
Không. Đó không phải ý hay.
Yes?
Vâng?
STUDENT
Why is the length of the vector [INAUDIBLE] GIREEJA RANADE: Why is the length of the vector 4? Because we took four measurements. We just decided to take four measurements.
Tại sao độ dài của vectơ [KHÔNG NGHE RÕ] GIREEJA RANADE: Tại sao độ dài của vectơ là 4? Vì ta đã thực hiện bốn phép đo. Ta chỉ đơn giản quyết định đo bốn lần.
We wanted to see if we could do it in four measurements. If we took five measurements, it would be five. If we took three measurements, it would be three.
Ta muốn xem có làm được với bốn phép đo không. Nếu đo năm lần thì sẽ là năm. Nếu đo ba lần thì sẽ là ba.
STUDENT
For the first iteration, do we just use a projection formula?
Ở lần lặp đầu tiên, ta chỉ cần dùng công thức chiếu phải không ạ?
GIREEJA RANADE
For the first iteration, can we just use a projection formula? Absolutely. This is exactly equal to the projection formula. Question in the back?
Ở lần lặp đầu tiên, có thể chỉ dùng công thức chiếu không? Hoàn toàn được. Nó chính xác bằng công thức chiếu. Câu hỏi ở phía sau?
STUDENT
What does a single measurement look like? Is it measuring the [INAUDIBLE]?
Một phép đo trông như thế nào ạ? Có phải nó đo [KHÔNG NGHE RÕ] không ạ?
What does a single measurement [INAUDIBLE] GIREEJA RANADE: A single measurement is just exactly what you did in the first lab. Right? This row times this column gives me 1.
Một phép đo [KHÔNG NGHE RÕ] GIREEJA RANADE: Một phép đo chính là điều các bạn đã làm trong bài lab đầu tiên. Đúng không? Hàng này nhân cột này cho tôi 1.
So this is basically all of the pixels in the image. This is the light.
Vậy đây về cơ bản là tất cả các pixel trong ảnh. Đây là ánh sáng.
Basically, remember when you did Module 1 imaging, you basically had these masks, where there was darks some places and ones some places. So this is exactly this.
Nhớ lại khi làm Module 1 về chụp ảnh, các bạn có những mặt nạ, chỗ thì tối chỗ thì sáng, là các số 0 và 1. Cái này chính xác là như vậy.
So this is basically saying that I'm going to take a measurement that shines light on pixel 1, 5, 8, and 9. Right? And everywhere else I'm going to put black.
Vậy ở đây tôi nói rằng tôi sẽ thực hiện một phép đo chiếu sáng vào pixel 1, 5, 8 và 9. Đúng không? Còn mọi chỗ khác tôi để tối.
That's the first mask. The second mask has pixel 2 and pixel 5, and so on. Does that make sense? Yes?
Đó là mặt nạ (mask) thứ nhất. Mặt nạ thứ hai có pixel 2 và pixel 5, và cứ thế tiếp tục. Mọi người hiểu chưa? Em hỏi à?
STUDENT
[INAUDIBLE].
[KHÔNG NGHE RÕ].
GIREEJA RANADE
Why did I choose C5? Because it had the largest inner product with R.
Tại sao tôi chọn C5? Vì nó có tích vô hướng lớn nhất với R.
STUDENT
[INAUDIBLE]?
[KHÔNG NGHE RÕ]?
GIREEJA RANADE
Because you can choose arbitrarily. It doesn't matter. If you have two equal things, it doesn't matter.
Vì em có thể chọn tùy ý. Không quan trọng. Nếu có hai giá trị bằng nhau thì chọn cái nào cũng được.
STUDENT
Is the projection of R onto C5 equal to X5 or C5X5? What's the difference between the two?
Hình chiếu của R lên C5 bằng X5 hay C5X5? Hai cái đó khác nhau thế nào ạ?
GIREEJA RANADE
The projection — this is equal to X5 hat. This formula is basically the coefficient that gives you X5 hat.
Hình chiếu... cái này bằng X5 hat. Công thức này về cơ bản là hệ số cho ra X5 hat.
If you now wanted to figure out this projection onto C5, you would have to multiply it by a C5.
Nếu giờ em muốn tìm hình chiếu lên C5, thì phải nhân nó với C5.
Yes. OK. So this is 1.5. What we get out from this is a scalar.
Đúng vậy. OK. Vậy đây là 1.5. Kết quả ta nhận được là một số vô hướng.
Right? This cannot be a vector? The dimensions don't allow it to be a vector.
Đúng không? Nó không thể là vectơ đúng không? Số chiều không cho phép nó là vectơ.
So to get a vector out of this, I cannot subtract just X5 from R. I have to subtract, basically, X5 times C5. Because X5 is a component of C5 that is present in R.
Vậy để có một vectơ, tôi không thể chỉ trừ X5 khỏi R. Tôi phải trừ X5 nhân C5. Vì X5 là thành phần của C5 có mặt trong R.
Does that make sense? OK. OK. Everyone with me here?
Mọi người hiểu chưa? OK. OK. Mọi người theo kịp chưa?
Good? OK. Good. Now we're going to remove 1.5 times C5 from R.
Ổn chứ? OK. Tốt. Giờ ta trừ 1.5 lần C5 khỏi R.
So R1 is equal to R minus 1.5 times 1 1 0 0.
Vậy R1 bằng R trừ 1.5 nhân 1 1 0 0.
What is R?
R là gì?
1 2 0 1 minus 1.5 1.5 0 0, which gives me, basically, minus 0.5 0.50 0 1.
1 2 0 1 trừ 1.5 1.5 0 0, ta được -0.5 0.5 0 1.
OK?
OK?
OK. So now we have this.
OK. Vậy giờ ta có cái này.
So now we're going to say, let's consider the next step, inner product of R1 with C1, inner product of R1 with C2,
Giờ ta xét bước tiếp theo, tích vô hướng của R1 với C1, của R1 với C2,
so on and so forth — R1 with C10. Right? We're going to do this inner product. So here, I guess I changed my notation a little bit.
và cứ thế... R1 với C10. Đúng không? Ta sẽ tính các tích vô hướng này. Ở đây tôi đã đổi ký hiệu một chút.
This is exactly equal to E. Sorry. This notation is a little bit different from what I'm using here.
Cái này đúng bằng E. Xin lỗi. Ký hiệu này hơi khác so với cái tôi đang dùng ở đây.
Let's call this, maybe — let me call this alpha hat.
Ta gọi cái này là... tôi gọi nó là alpha hat.
OK. Sorry. I'm not going to try and fix this notation. I will fix this and post a corrected notation one on the website.
OK. Xin lỗi. Tôi sẽ không sửa ký hiệu này ngay bây giờ. Tôi sẽ sửa và đăng bản đã sửa ký hiệu lên website.
Don't worry about this notation. Just follow what I'm doing right here. So what did we do? We have this R. We have this received vector.
Đừng lo về ký hiệu này. Cứ theo dõi những gì tôi làm ở đây. Vậy ta đã làm gì? Ta có R này, vectơ nhận được này.
We say that C5 is a component, right? C5 is a component. And so now, I'm going to subtract from R the part of R that can be explained by C5.
Ta nói C5 là một thành phần, đúng không? C5 là một thành phần. Và giờ tôi trừ khỏi R phần của R có thể giải thích bằng C5.
OK. Does everyone understand what we've done here so far? OK. Now whatever this remainder is, which I'm going to call R1 or E, I'm going to consider all these inner products.
OK. Mọi người hiểu những gì ta đã làm tới giờ chưa? OK. Phần còn lại này, tôi gọi nó là R1 hay E, tôi sẽ xét tất cả các tích vô hướng này.
OK? Once we have all of these inner products, which one is the maximum if I take minus 0.5 0.5 0 1 and I inner product it with every single one of these?
OK? Khi có tất cả các tích vô hướng này, cái nào lớn nhất nếu tôi lấy -0.5 0.5 0 1 và tính tích vô hướng với từng cái trong số này?
C7 is the maximum inner product. Right? It so turned out that earlier, also, we had C7. But that doesn't matter.
C7 có tích vô hướng lớn nhất. Đúng không? Tình cờ là lúc trước cũng là C7. Nhưng điều đó không quan trọng.
That was just luck. What matters is that now, again, C7 has the maximum inner product.
Đó chỉ là may mắn. Điều quan trọng là giờ C7 lại có tích vô hướng lớn nhất.
OK. So now that we know that C7 has the maximum inner product, what are we going to do to our S matrix? Our S matrix, initially, here, we just had this C5.
OK. Vì C7 có tích vô hướng lớn nhất, ta sẽ làm gì với ma trận S? Ban đầu ma trận S chỉ có C5.
So it was just C5. Now our S matrix is basically C5C7.
Tức là chỉ có C5. Giờ ma trận S là C5C7.
Because we now have both of these as identified. Right? So what does this mean? If I have C5 and C7, that means I have pixel X5 and X7 turned on.
Vì giờ ta đã xác định được cả hai. Đúng không? Vậy điều này nghĩa là gì? Nếu có C5 và C7, nghĩa là pixel X5 và X7 được bật.
Right? So I'm saying, to explain my observations when I took this measurement, I'm going to say, well, X5 and X7 were non-zero. Everything else was zero.
Đúng không? Tức là để giải thích các quan sát khi ta đo, ta nói rằng X5 và X7 khác không. Mọi thứ khác bằng không.
Now what do I do next?
Giờ ta làm gì tiếp?
Now I say, well, explain R using both C5 and C7.
Giờ ta giải thích R bằng cả C5 và C7.
OK?
OK?
So now, S is equal to C5C7 is equal to 1 1 0 0 0 1 0 1.
Vậy S bằng C5C7 bằng 1 1 0 0 0 1 0 1.
Now I want to project my received vector R onto S. OK?
Giờ tôi muốn chiếu vectơ nhận được R lên S. OK?
And how am I going to do this? I'm going to use, basically, the B squares formula.
Làm bằng cách nào? Tôi sẽ dùng công thức bình phương tối thiểu.
And so I'm going to get my X5X7 is equal to S transpose S inverse S transpose times R. Right?
Và ta sẽ được X5X7 bằng S transpose S nghịch đảo nhân S transpose nhân R. Đúng không?
These are the two things that I'm projecting onto. This is my received vector R. So what is this equal to?
Đây là hai vectơ mà tôi chiếu lên. Đây là vectơ nhận được R. Vậy cái này bằng gì?
This is now equal to 1 1 0 0 0 1 0 1. This is S transpose.
Giờ nó bằng 1 1 0 0 0 1 0 1. Đây là S transpose.
S is equal to 1 1 0 0 0 1 0 1, all of this inverse times 1 1 0 0 0 1 0 1 times my received vector, which is 1 2 0 1.
S bằng 1 1 0 0 0 1 0 1, toàn bộ phần này lấy nghịch đảo nhân 1 1 0 0 0 1 0 1 nhân vectơ nhận được của tôi, là 1 2 0 1.
OK?
OK?
Is everyone following me up to this point?
Mọi người theo kịp tới đây chưa?
Yes? Question?
Rồi chứ? Có câu hỏi không?
STUDENT
[INAUDIBLE]?
[KHÔNG NGHE RÕ]?
GIREEJA RANADE
This is — OK. So everyone please pay attention. I've had this question twice now. It's a good question.
Cái này — Được rồi. Mọi người chú ý nhé. Em đã gặp câu hỏi này hai lần rồi. Đây là câu hỏi hay.
But make sure — it doesn't. It's a cooked up example. It just happens that these are equal. If you have two things that are equal, it doesn't matter.
Nhưng hãy nhớ: nó không phải vậy. Đây là ví dụ được dựng sẵn. Chỉ là tình cờ hai giá trị này bằng nhau. Nếu có hai thứ bằng nhau thì không quan trọng.
You can choose any one of them randomly. So if you have two inner products that are equal, you don't necessarily know that both of them are present. They might be phantoms.
Ta có thể chọn ngẫu nhiên một trong hai. Nếu có hai tích vô hướng bằng nhau, ta không chắc là cả hai đều thực sự có mặt. Chúng có thể chỉ là bóng ma.
You have no way of knowing. So you want to make sure that it shows up in the second round. You could have also done just C — so you would have started with C7.
Ta không có cách nào biết được. Nên ta phải chắc là nó xuất hiện ở vòng thứ hai. Ta cũng có thể chỉ làm C — tức là bắt đầu với C7.
Because of the cooked up example, you would have gotten C5 as the next one. And in this specific corner case, it would have worked. But in general, it will not.
Vì ví dụ được dựng sẵn, bước tiếp theo ta sẽ được C5. Và trong trường hợp đặc biệt này, cách đó vẫn đúng. Nhưng nói chung thì không.
This is because this is a classroom example with 10 pixels and four measurements, which is never a real world situation that you're actually going to end up in.
Vì đây là ví dụ trên lớp với 10 pixel và bốn phép đo, không bao giờ là tình huống thực tế mà các em sẽ gặp.
So don't worry about the fact that these inner products are exactly equal. OK?
Nên đừng bận tâm chuyện các tích vô hướng này bằng nhau chính xác. Được chứ?
So we have, basically, these two. It doesn't matter that these happen to be equal. This is just pure fluke.
Vậy về cơ bản ta có hai cái này. Chúng tình cờ bằng nhau cũng không sao. Đây hoàn toàn chỉ là ngẫu nhiên.
Does that answer the question? Yeah? OK. Great.
Vậy đã trả lời câu hỏi chưa? Rồi chứ? Được. Tốt.
Yes?
Em nào hỏi?
STUDENT
Why does the signal [INAUDIBLE] image need to be sparse?
Tại sao ảnh tín hiệu [KHÔNG NGHE RÕ] cần phải thưa?
GIREEJA RANADE
Why does the signal image need to be sparse?
Tại sao ảnh tín hiệu cần phải thưa?
Hold on to that. We'll get to that. But basically, the thing is that if the signal image isn't sparse, then I cannot make this assumption that most of my pixels are zeros.
Em cứ giữ câu hỏi đó. Lát nữa ta sẽ nói tới. Nhưng về cơ bản, nếu ảnh tín hiệu không thưa thì ta không thể giả định rằng hầu hết các pixel bằng không.
The only reason this works is that I want to explain my R by turning on as few pixels as possible.
Cách này chạy được chỉ vì ta muốn giải thích R bằng cách bật càng ít pixel càng tốt.
Basically, at some point, my process will entirely break down if my signal isn't sparse. I will start to read values that are not actually there.
Nếu tín hiệu không thưa, quá trình của ta sẽ sụp đổ hoàn toàn ở một lúc nào đó. Ta sẽ đọc ra những giá trị không thực sự có.
If my signal isn't sparse, I cannot get away from needing 10,000 measurements for 10,000 pixels.
Nếu tín hiệu không thưa, ta không thể tránh việc cần 10.000 phép đo cho 10.000 pixel.
The structure that is in there that says that most of the things are zeros is what allows me to do this. Does that make sense? Yes?
Chính cấu trúc bên trong, là hầu hết các giá trị bằng không, cho phép ta làm được điều này. Em hiểu chưa? Em nào hỏi?
STUDENT
When we did this process with our satellites, [INAUDIBLE], if you [INAUDIBLE]?
Khi làm quy trình này với các vệ tinh, [KHÔNG NGHE RÕ], nếu [KHÔNG NGHE RÕ]?
GIREEJA RANADE
If these are — good question. Like, basically, you are saying that does there need to be some structure on these columns? And you basically do want to choose these columns to be near orthogonal.
Nếu những cái này — câu hỏi hay. Ý em là các cột này có cần một cấu trúc nào đó không? Đúng vậy, ta muốn chọn các cột này gần trực giao.
ONP will still work. It's an algorithm. You can still execute it. But it will work better and you will basically know that you get the right answer if you have some kind of structure.
OMP vẫn chạy được. Nó là một thuật toán. Ta vẫn có thể thực thi nó. Nhưng nó sẽ chạy tốt hơn và ta sẽ biết chắc là có đáp án đúng nếu có một cấu trúc nào đó.
So you don't want to have a bunch of columns that are linearly dependent here. That would make this fail. This would not work for any arbitrary columns. There's a structure to these columns.
Nên ta không muốn có nhiều cột phụ thuộc tuyến tính ở đây. Như vậy sẽ làm nó thất bại. Nó sẽ không chạy với các cột tùy ý. Các cột này có cấu trúc.
And there's that structure for a reason.
Và cấu trúc đó có lý do.
OK. So I'm not going to do this algebra. You can do it when you get home. But this basically turns out to be equal to exactly 1 1, right?
Được rồi. Em sẽ không làm phần đại số này. Các em có thể làm khi về nhà. Nhưng kết quả chính xác bằng 1 1, đúng không?
You can verify it if you want.
Muốn thì các em có thể kiểm tra.
And now, when you look at this received [INAUDIBLE] vector, 1 2 0 1, and you look at C5 and C7, what is R?
Giờ nhìn vectơ nhận được [KHÔNG NGHE RÕ] 1 2 0 1, và nhìn C5 và C7, R là gì?
It's just C5 plus C7, right?
Nó chỉ là C5 cộng C7, đúng không?
And so here, what this is saying is what was the estimate that you got for X5 when you just projected onto C5? You got 1.5, right?
Và ở đây, điều này cho biết ước lượng của X5 khi ta chỉ chiếu lên C5 là bao nhiêu? Ta được 1,5, đúng không?
But when you see now this better estimate using both the columns, you're actually doing a better job than if you had just used this estimate and not updated using the new information that you had gotten.
Nhưng khi có ước lượng tốt hơn dùng cả hai cột, ta thực sự làm tốt hơn so với việc chỉ dùng ước lượng cũ mà không cập nhật bằng thông tin mới vừa có được.
Right? This is why you want to keep updating your estimates for the unknowns every time you discover a new device. Basically, if you keep the old estimates, that's old estimates with less information.
Đúng không? Đó là lý do ta phải liên tục cập nhật ước lượng cho các ẩn số mỗi lần phát hiện thêm một thiết bị. Nếu giữ ước lượng cũ, đó là ước lượng cũ với ít thông tin hơn.
The fact that you can now make a better estimate using all of the information you have will lead to better answers. That's why you want to keep doing this.
Việc ta có thể ước lượng tốt hơn bằng toàn bộ thông tin đang có sẽ cho đáp án tốt hơn. Vì vậy ta phải tiếp tục làm thế.
And you don't want to just say that, OK, well, let me keep my estimate here, and let me now just estimate X7 instead of trying to estimate both of them together.
Và đừng nói rằng, thôi, cứ giữ ước lượng ở đây rồi giờ chỉ ước lượng X7 thay vì ước lượng cả hai cùng lúc.
We're going to do an example in discussion tomorrow that's going to talk more about exactly this point.
Ngày mai buổi thảo luận sẽ có một ví dụ nói kỹ hơn đúng về điểm này.
So if you still have some questions about this, please make sure you attend discussion — sorry, not tomorrow, but Monday's discussion. OK?
Nếu các em vẫn còn thắc mắc, hãy đi buổi thảo luận, xin lỗi, không phải ngày mai mà là buổi thảo luận thứ Hai. Được chứ?
So now that you've seen this ONP procedure out in an example, is everyone clear on what these steps are and what we're doing by saying, OK, well, let's explain it by the signatures we have and then remove them one by one?
Giờ các em đã thấy quy trình OMP qua ví dụ, mọi người đã rõ các bước này chưa, và việc ta đang làm là giải thích tín hiệu bằng các signature đang có rồi loại bỏ chúng từng cái một?
Question?
Có câu hỏi không?
STUDENT
[INAUDIBLE]?
[KHÔNG NGHE RÕ]?
GIREEJA RANADE
The question was if we had another pixel and we wanted to do this again, then S would indeed have a third column. And then you would get a 4 by 3 matrix.
Câu hỏi là nếu có thêm một pixel nữa và ta muốn làm lại thì S sẽ có thêm cột thứ ba. Và khi đó ta có ma trận 4 nhân 3.
Exactly. So here, S was just a column. Here it's two columns. Then it will be three columns, and so on, and so forth.
Đúng vậy. Ở đây S chỉ có một cột. Ở đây là hai cột. Rồi sẽ là ba cột, và cứ thế tiếp tục.
And you can see that basically, right now, the error vector or the [INAUDIBLE] you have when you put X5 and X7 is exactly zero. Right? Because what do you have?
Và các em thấy là ngay lúc này, vectơ sai số hay [KHÔNG NGHE RÕ] mà ta có khi chọn X5 và X7 bằng đúng 0. Đúng không? Vì ta có gì?
X5 — so this is X5 hat, X7 hat, X5 hat times C5 plus X7 hat times C7 is exactly equal to 1 2 0 1.
X5 — đây là X5 mũ, X7 mũ, X5 mũ nhân C5 cộng X7 mũ nhân C7 bằng đúng 1 2 0 1.
Right? This is exactly equal to R. Because this is 1 times 1 1 0 0 plus 1 times 0 1 0 1.
Đúng không? Cái này bằng đúng R. Vì đây là 1 nhân 1 1 0 0 cộng 1 nhân 0 1 0 1.
Right? So here we've explained everything. The unexplained part is exactly zero.
Đúng không? Vậy là ta đã giải thích hết. Phần chưa giải thích được bằng đúng 0.
R minus this R1 is equal to 0. So in this case, we've actually explained all of R, now that we've found these two things.
R trừ R1 này bằng 0. Vậy ở trường hợp này ta đã giải thích toàn bộ R, khi đã tìm được hai thứ này.
Other questions? Yes?
Còn câu hỏi nào không? Mời em?
STUDENT
What happens if our matrix [INAUDIBLE] sparse [INAUDIBLE]?
Điều gì xảy ra nếu ma trận của ta [KHÔNG NGHE RÕ] thưa [KHÔNG NGHE RÕ]?
GIREEJA RANADE
What happens if our image isn't sparse? Basically, this will not work. This only works when you have sparse images. But let's try and do this now in an actual set up.
Điều gì xảy ra nếu ảnh không thưa? Về cơ bản là sẽ không hiệu quả. Cách này chỉ hiệu quả với ảnh thưa. Giờ ta thử làm trong một thiết lập thực tế.
So can I have one of the cameras connect to my laptop? Perfect. Thank you.
Cho cô một camera kết nối với laptop nhé? Tuyệt. Cảm ơn em.
So what we have here is basically 100 by 100 image. And instead of taking 10 to the 4 measurements, we want to take only 7,000.
Ở đây ta có ảnh 100 nhân 100. Và thay vì đo 10 mũ 4 lần, ta chỉ muốn đo 7.000 lần.
And we know the sparsity of the image. We know that the sparsity of the image is basically 960. And we're taking these measurements. So we have measurements.
Và ta biết độ thưa của ảnh. Ta biết độ thưa của ảnh là 960. Và ta đang thực hiện các phép đo này. Vậy ta có các phép đo.
And the number of measurements we have is basically 7,000. So the column that we have is something like this. So all we're given is this.
Và số phép đo là 7.000. Cột mà ta có trông như thế này. Vậy tất cả những gì ta có là cái này.
This basically parallels this received vector here, the measurements vector that I'm pointing to on the iPad notebook is the same as this R. And I also know this measurement matrix, right?
Nó tương ứng với vectơ nhận được ở đây, vectơ các phép đo mà cô đang chỉ trên iPad cũng chính là R này. Và cô cũng biết ma trận đo này, đúng không?
So I've generated this measurement matrix. I know this received vector. And what I'm going to do is now basically run ONP on this.
Cô đã tạo ra ma trận đo này. Cô biết vectơ nhận được này. Và giờ cô sẽ chạy ONP trên đó.
And let's see what actually happens. So the things to note from this — you don't have to read all of the code. What I want you to see is that this has 10,000 pixels.
Và xem chuyện gì xảy ra. Những điều cần chú ý ở đây: các em không cần đọc hết đoạn code. Cô muốn các em thấy là ảnh này có 10.000 pixel.
We are taking 7,000 measurements. Right? All we're given is basically this vector. And we have this mask.
Ta đo 7.000 lần. Đúng không? Tất cả những gì ta có là vectơ này. Và ta có mặt nạ này.
This mask is known to us. This mask is basically generating by randomly putting zeros and ones. Random generated masks often give you columns that are very close to orthogonal, which is why they work.
Mặt nạ này ta biết trước. Mặt nạ này được tạo bằng cách đặt ngẫu nhiên các số không và một. Mặt nạ tạo ngẫu nhiên thường cho ra các cột gần như trực giao, và đó là lý do chúng hiệu quả.
So we have this mask. We have these measurements. And now we're going to use ONP to actually recover this.
Vậy ta có mặt nạ này. Ta có các phép đo này. Giờ ta dùng ONP để khôi phục ảnh.
So what this is saying is that the bottom is the iteration number of the ONP. So it's keep going. And every time, it's choosing one pixel to light up.
Phía dưới này là số lần lặp của ONP. Nó cứ chạy tiếp. Và mỗi lần nó chọn một pixel để sáng lên.
So as you can see, every new number, it's one extra pixel goes from black to white. Everything there is black right now. Because we're assuming that most of the pixels are zero.
Các em thấy mỗi số mới, có thêm một pixel chuyển từ đen sang trắng. Lúc này mọi thứ đều đen. Vì ta giả sử hầu hết các pixel bằng không.
OK? And as you'll see, it will take quite a bit of time. While this is running, I'll take another question, if there is one. Yes?
Được chứ? Và các em sẽ thấy nó mất khá nhiều thời gian. Trong lúc nó chạy, cô nhận thêm một câu hỏi, nếu có. Mời em?
STUDENT
Are we under the assumption that the value of X are between 0 and 1?
Ta có giả sử các giá trị của X nằm giữa 0 và 1 không ạ?
GIREEJA RANADE
Are we under the assumption that the values of X are between 0 and 1? We don't have to make that explicit assumption in ONP.
Ta có giả sử các giá trị của X nằm giữa 0 và 1 không? Ta không cần đưa ra giả sử tường minh đó trong ONP.
STUDENT
[INAUDIBLE].
[KHÔNG NGHE RÕ].
GIREEJA RANADE
Because this is working without that assumption. But because the values are between 0 and 1, the values that are being returned are also between 0 and 1.
Vì nó vẫn chạy được mà không cần giả sử đó. Nhưng vì các giá trị nằm giữa 0 và 1, nên các giá trị được trả về cũng nằm giữa 0 và 1.
Because it's actually picking up fairly correct values.
Vì nó thực sự tìm ra các giá trị khá chính xác.
Other questions? Yes?
Còn câu hỏi nào không? Mời em?
STUDENT
So these [INAUDIBLE] devices, [INAUDIBLE] gold codes, is there any significance to the columns in this example?
Với những thiết bị này, [KHÔNG NGHE RÕ] gold code, các cột trong ví dụ này có ý nghĩa gì đặc biệt không ạ? Câu hỏi là các cột có ý nghĩa gì.
GIREEJA RANADE
So the question was what is the significance of the columns. In this example? Each column basically says that, in the received vector that I have, what is the contribution of this particular pixel?
Trong ví dụ này à? Mỗi cột cho biết, trong vectơ nhận được của ta, pixel cụ thể này đóng góp bao nhiêu.
So just like in the gold code setting, we get to create the signatures. We create the gold codes. Here we create the columns. So there's not any significant, per se.
Giống như trong bài gold code, ta được tự tạo các chữ ký. Ta tạo ra các gold code. Ở đây ta tạo ra các cột. Nên không có ý nghĩa đặc biệt gì. Chúng không phải chữ ký theo nghĩa đó.
They're not signatures in that sense. But you can think of them as signatures of the pixels.
Nhưng các em có thể xem chúng như chữ ký của các pixel. [SINH VIÊN CÙNG THỐT LÊN] SINH VIÊN: Ồ!
GIREEJA RANADE
[STUDENTS EXCLAIMING TOGETHER] STUDENTS: Whoa!
Ồ!
GIREEJA RANADE
Whoa! [INTERPOSING VOICES] GIREEJA RANADE: OK.
[NHIỀU NGƯỜI NÓI CHEN NHAU] GIREEJA RANADE: Được rồi.
GIREEJA RANADE
[INTERPOSING VOICES] GIREEJA RANADE: What do you see happening as time is going on?
[NHIỀU NGƯỜI NÓI CHEN NHAU] GIREEJA RANADE: Các em thấy gì đang xảy ra theo thời gian? Các em thấy gì đang xảy ra theo thời gian?
It's taking more and more time to do one iteration, right? Why is that happening?
Mỗi vòng lặp mất càng lúc càng nhiều thời gian, đúng không? Tại sao lại như vậy?
STUDENT
Our S multiplication.
Do phép nhân với S.
GIREEJA RANADE
Our S matrix keeps getting bigger and bigger, right? So you have to do bigger and bigger matrix inversions every time to figure it out.
Ma trận S của chúng ta cứ lớn dần lên, đúng không? Nên em phải tính nghịch đảo ma trận ngày càng lớn ở mỗi lần để tìm ra kết quả.
Like, if you were to do this with 10,000 measurements, you would have to invert a 10,000 by 10,000 matrix. Right?
Ví dụ, nếu làm việc này với 10,000 phép đo, em sẽ phải nghịch đảo một ma trận 10,000 x 10,000. Đúng không?
Which would be a pretty big matrix to invert, you typically don't want to be in a situation where you're inverting that.
Đó là một ma trận khá lớn để lấy nghịch đảo, và thường em không muốn rơi vào tình huống phải nghịch đảo nó.
Almost there — it's going to take some time.
Gần xong rồi, sẽ mất chút thời gian.
So it turns out that as you can see, ONP is a pretty slow algorithm because it has these matrix inversions that are embedded into it.
Như các em thấy, ONP là một thuật toán khá chậm vì nó có các phép nghịch đảo ma trận nằm bên trong.
There are actually ways to speed up ONP using a procedure called Gram-Schmidt, which basically analyzes your component, your signatures explicitly.
Thực ra có cách tăng tốc ONP bằng một thủ tục gọi là Gram-Schmidt, về cơ bản là phân tích tường minh các thành phần, tức các signature của em.
Right now, we have almost orthogonal signatures. What it does is it explicitly orthogonalizes them. And therefore, you can actually speed up your computation a lot.
Hiện giờ, ta có các signature gần như trực giao. Nó sẽ trực giao hóa chúng một cách tường minh. Nhờ đó, em có thể tăng tốc tính toán lên rất nhiều.
Again, we will not be covering Gram-Schmidt in this class right now. But you will learn it in 16B. So for those who want the extra penny, you can collect it.
Một lần nữa, lớp này sẽ không học Gram-Schmidt ngay lúc này. Nhưng các em sẽ học nó trong 16B. Ai muốn lấy thêm điểm cộng thì cứ lấy.
Collect it for that now. We're almost there, almost there. So what is the sparsity level? Do we know how many iterations do we expect it to go for?
Hãy lấy ngay bây giờ. Sắp xong rồi, sắp xong rồi. Vậy mức độ thưa (sparsity) là bao nhiêu? Ta có biết nó sẽ chạy bao nhiêu vòng lặp không?
We know that the sparsity is 960. So it's going to keep going until it gets 960 pixels. We can start to see what the image really is. Right?
Ta biết độ thưa là 960. Nên nó sẽ chạy tiếp đến khi có 960 điểm ảnh. Ta bắt đầu thấy ảnh thật sự là gì. Đúng không?
OK. So we'll let that keep going in the background.
OK. Cứ để nó chạy nền.
And I'm going to move to the next part of the lecture, which is validation.
Còn thầy/cô sẽ chuyển sang phần tiếp theo của bài giảng, là validation (kiểm chứng).
Which is finally coming to the question that you have all been asking me throughout the three lectures that we've been talking about ONP.
Cuối cùng ta quay lại câu hỏi mà các em đã hỏi suốt ba buổi học khi nói về ONP.
You've been saying, well, but how do I decide when to stop? How do I decide when to stop? Here you're telling me that you know the sparsity level.
Các em hỏi: nhưng làm sao quyết định khi nào dừng? Làm sao quyết định khi nào dừng? Ở đây thì biết trước mức độ thưa.
But maybe I don't know the sparsity level. Maybe I don't know how many pixels there are. Maybe I don't know how many devices are transmitting.
Nhưng có thể em không biết mức độ thưa. Có thể em không biết có bao nhiêu điểm ảnh. Có thể em không biết có bao nhiêu thiết bị đang phát.
And to understand this, I want to introduce this concept of validation, which is basically one of the most fundamental concepts that's used many, many times over in development of every single machine learning algorithm that is used.
Để hiểu điều này, thầy/cô muốn giới thiệu khái niệm validation, về cơ bản là một trong những khái niệm nền tảng nhất, được dùng rất nhiều lần trong quá trình phát triển mọi thuật toán machine learning đang được sử dụng.
We're definitely not going to go into a full development of validation in the class this time. Because there's multiple levels that we can go into.
Lần này ta chắc chắn không đi sâu đầy đủ về validation trong lớp. Vì có nhiều mức độ mà ta có thể đi vào.
But I want to really just introduce you to the topic so that when you go into operative vision classes, you'll have a sense for what this is.
Nhưng thầy/cô chỉ muốn giới thiệu chủ đề này để khi các em học các lớp về thị giác máy tính, các em có khái niệm về nó.
And for this I want to go back to the devices example.
Và để làm vậy, ta quay lại ví dụ về các thiết bị.
OK. So we have these different devices that are transmitting. And we're saying that, well, I picked out one device. I picked out a second device.
OK. Ta có các thiết bị khác nhau đang phát tín hiệu. Và ta nói: em chọn ra một thiết bị. Chọn ra thiết bị thứ hai.
I picked out a third device. How do I know when to stop? Right?
Chọn ra thiết bị thứ ba. Làm sao biết khi nào dừng? Đúng không?
And so let's think about one way of doing this.
Hãy nghĩ về một cách làm.
Let's say I have my signatures that I've made, my gold codes, SA, SB, SC, so on and so forth.
Giả sử em có các signature đã tạo, các mã Gold, SA, SB, SC, v.v.
These correspond to my devices that I know. But what I can do is, in addition, I can make a set of ghost signatures.
Chúng tương ứng với các thiết bị mà em biết. Nhưng ngoài ra, em có thể tạo một tập các signature ma (ghost).
Maybe I'll call them GA, GB, GC, and so on.
Có thể gọi chúng là GA, GB, GC, v.v.
These are the different ghost signatures that you have. Is this still running? OK. You know the different ghost signatures that you have.
Đây là các signature ma khác nhau mà em có. Cái này vẫn đang chạy chứ? OK. Em biết các signature ma mà em có.
And you can say, well, I'm not going to use every single gold code that I have for a device. I'm going to keep some of my gold codes in reserve.
Và em có thể nói: em sẽ không dùng hết mọi mã Gold cho các thiết bị. Em giữ lại một số mã Gold để dự phòng.
And I'm never going to assign them to any device. So I know that these are gold codes that are valid gold codes. But they're not ever assigned to any device.
Và không bao giờ gán chúng cho thiết bị nào. Vậy em biết đây là các mã Gold hợp lệ. Nhưng chúng không bao giờ được gán cho thiết bị nào.
So then, what I could do potentially is I can say, well, let me keep picking off one device at a time, one signature at a time.
Vậy thì em có thể làm như sau: cứ chọn ra từng thiết bị một, từng signature một.
As soon as I encounter a device, a signature, that belongs to my gold set, my fake signature set that I have created, then I know that, hey, actually, this cannot be.
Ngay khi gặp một thiết bị, một signature, thuộc tập Gold giả mà em đã tạo, thì em biết là điều này không thể đúng.
This has to be some artifact of the noise. This cannot actually be because of a real device. Right?
Đây hẳn là một hiện tượng do nhiễu. Nó không thể do một thiết bị thật gây ra. Đúng không?
So how do I know when to stop as soon as I pick out a device from my fake ghost set?
Vậy làm sao biết khi nào dừng? Ngay khi chọn ra một thiết bị từ tập ma giả.
Right? This is something that we could do. And then we would know that, basically, the big thing, the reason that we're seeing this, has to be some artifact of the noise.
Đúng không? Đây là điều ta có thể làm. Và khi đó ta biết rằng nguyên nhân khiến ta thấy tín hiệu lớn này hẳn là do nhiễu.
Right? I got a lot of questions in office hours of saying, well, how do you know if your ONP is actually working or not? Right? You run this procedure.
Đúng không? Thầy/cô nhận được nhiều câu hỏi trong giờ hỗ trợ kiểu như: làm sao biết ONP của em có thật sự hoạt động hay không? Đúng không? Em chạy thủ tục này.
You get something out. How do you have any idea what you are getting is any good? Maybe you just got complete and utter and total garbage.
Em nhận được một kết quả. Làm sao em biết kết quả đó có tốt không? Có thể em chỉ nhận được toàn rác hoàn toàn.
How do you know whether this is at all valid?
Làm sao biết nó có hợp lệ hay không?
And this is one way that you can engineer into the system a level of redundancy that says, well, if you're picking out these ghost signals, you must just be picking out the noise.
Và đây là một cách để thiết kế vào hệ thống một mức dự phòng, nghĩa là nếu em chọn ra các tín hiệu ma này, thì em chỉ đang chọn ra nhiễu.
Because I know that no such device is actually transmitted. Right? That's great.
Vì em biết không có thiết bị nào như vậy thực sự phát. Đúng không? Tuyệt.
But then, what if we have some enterprising Berkeley student who decides to build a device and looks at the list of signatures that are taken.
Nhưng nếu có một sinh viên Berkeley đầy sáng tạo quyết định chế tạo một thiết bị và danh sách các signature đã được dùng.
They don't want to accidentally impinge on some kind of IP or take a signature that is already taken. So they pick a ghost device. And they actually build their device.
Họ không muốn vô tình vi phạm quyền sở hữu trí tuệ nào đó hay lấy một signature đã có người dùng. Nên họ chọn một thiết bị ma. Và họ thật sự chế tạo thiết bị đó.
And this device starts transmitting. Maybe the ghost device that you're seeing is because someone decided to build that device.
Và thiết bị này bắt đầu phát tín hiệu. Có thể thiết bị ma mà các em đang thấy là do có người quyết định chế tạo thiết bị đó.
And it's actually there. How would you know if the ghost signature that you're detecting is actually a ghost signature and it's actually present? You just made a mistake or you're just detecting the noise?
Và nó thật sự có mặt. Làm sao biết signature ma mà các em phát hiện là signature ma thật và nó thật sự có mặt? Hay các em chỉ nhầm lẫn, hoặc chỉ đang phát hiện nhiễu?
How could you potentially try and get around that kind of situation? Any ideas? Any thoughts? Yeah?
Làm thế nào để có thể xử lý tình huống như vậy? Có ý kiến nào không? Em nào nghĩ ra không? Em nào?
STUDENT
Have the FCC reserve [INAUDIBLE]..
Để FCC dành riêng [KHÔNG NGHE RÕ].
GIREEJA RANADE
Have the FCC reserve three gold codes — absolutely a great idea, which is usually done. But people sometimes make illegal devices.
Để FCC dành riêng ba mã Gold — đúng là ý hay, và thường người ta làm vậy. Nhưng đôi khi người ta chế tạo thiết bị trái phép.
And if you want to test your algorithm, we want to really try and do this. But in many cases, that will exactly work. Sometimes you don't have that much control.
Và nếu muốn kiểm tra thuật toán của mình, chúng ta muốn thử làm điều đó thật sự. Nhiều trường hợp cách đó sẽ hiệu quả. Đôi khi mình không kiểm soát được nhiều như vậy.
But other ideas, potentially, on what we could do? Yeah?
Còn ý tưởng nào khác chúng ta có thể làm không? Em nào?
STUDENT
Validate each code using modulations, like, [INAUDIBLE]?
Kiểm chứng từng mã bằng điều chế, kiểu như [KHÔNG NGHE RÕ]?
GIREEJA RANADE
Yeah. Can you somehow validate what you're seeing? The idea is saying, can you somehow validate what you're actually getting, right?
Đúng. Có cách nào kiểm chứng những gì mình thấy không? Ý là, liệu mình có thể kiểm chứng những gì mình thực sự nhận được không?
You're saying, well, if I am getting this signature, is it actually that some student made some device? Or is it that I'm just detecting the noise?
Tức là, nếu tôi nhận được signature này, thì có phải một sinh viên nào đó đã chế tạo thiết bị? Hay tôi chỉ đang phát hiện nhiễu?
So what one would want to do, what a good engineer would do is you would collect a validation set.
Vậy điều cần làm, điều một kỹ sư giỏi sẽ làm, là thu thập một validation set (tập kiểm chứng).
You would say I have my received signal R. And maybe my received signal R is coming from microphone one, or it's coming from my device, like my first home box.
Giả sử tôi có tín hiệu nhận được R. Và có thể tín hiệu R này đến từ microphone một, hoặc đến từ thiết bị của tôi, như home box đầu tiên.
Right? But if I have, say, a second microphone, a second receiver, where I can collect, basically, an independent measurement of the same devices — so these are two devices now.
Đúng không? Nhưng nếu tôi có microphone thứ hai, một bộ thu thứ hai, để thu một phép đo độc lập của cùng các thiết bị đó, tức là giờ có hai thiết bị.
They're both placed in the same room, but maybe at slightly different locations.
Cả hai đặt trong cùng một phòng, nhưng ở vị trí hơi khác nhau.
So the second device, the noise that is coming into this device is different from the noise that is coming into this device.
Vậy nhiễu đi vào thiết bị thứ hai khác với nhiễu đi vào thiết bị này.
So if there's truly a device that is present, both of them should pick it up.
Nếu thật sự có một thiết bị, cả hai đều phải bắt được nó.
But if I see a ghost device that's present only in one signal and not in the second signal, then I can say, well, you must actually be noise.
Nhưng nếu tôi thấy một thiết bị ma chỉ có trong một tín hiệu mà không có trong tín hiệu kia, thì tôi có thể nói nó thực chất là nhiễu.
Right? This ghost device is just an artifact of noise. So I have basically an R1 or R primary and R validation.
Đúng không? Thiết bị ma này chỉ là sản phẩm của nhiễu. Vậy tôi có R1 hay R chính, và R validation.
And I say basically the strongest signals — the strongest signals plus devices will be present in both.
Và những tín hiệu mạnh nhất, tức các thiết bị mạnh nhất, sẽ có mặt ở cả hai.
And as soon as you end up in a situation where the ONP running on the two different signals start giving you different devices that are present, you can say, hey, come on, guys.
Và ngay khi gặp tình huống mà OMP chạy trên hai tín hiệu khác nhau cho ra các thiết bị có mặt khác nhau, thì các em có thể nói: này, thôi nào. Các em ở cùng một phòng, về cơ bản cùng một vị trí.
You're in the same room at essentially the same location. You're just making up stuff by activating the noise. Right? That's basically your way of saying that, OK, there's something going wrong here.
Các em đang tự bịa ra thứ không có bằng cách kích hoạt nhiễu. Đúng không? Đó là cách nói rằng có điều gì đó đang sai ở đây. Đây là ý tưởng của validation trong machine learning.
This is the idea of validation in machine learning. And this is an idea that you have to grapple with a lot in machine learning. Can I get back both the document cameras?
Và đây là ý tưởng mà các em sẽ phải vật lộn rất nhiều trong machine learning. Cho tôi lấy lại cả hai document camera nhé?
So in general in machine learning, you will always have to ask the question, how do I know if my model is any good?
Nói chung trong machine learning, các em luôn phải đặt câu hỏi: làm sao biết mô hình của mình có tốt không? Tôi có thể xây một mô hình.
I can make a model. I can make a model, for example, to predict the stock prices. Right? And I can make whatever model I wanted.
Chẳng hạn một mô hình dự đoán giá cổ phiếu. Đúng không? Và tôi có thể xây bất kỳ mô hình nào tôi muốn. Nhưng làm sao biết tôi có nên dùng nó hay không?
But how do I know that I actually want to use it? Right? I could make a model to predict whether people are going to like a certain shirt or like a certain design.
Đúng không? Tôi có thể xây mô hình dự đoán liệu mọi người có thích một chiếc áo hay một thiết kế nào đó. Tôi nghĩ có bạn đã đăng bài extra credit lên Piazza về chuyện này.
I think someone posted an extra credit submission on Piazza about this. How do I actually know whether my model is any good. Let's say I'm modeling — not the stock.
Làm sao biết thật sự mô hình của mình có tốt không? Giả sử tôi đang mô hình hóa không phải cổ phiếu, mà tôi đang xây một mạch. Tôi đang cố hiểu một linh kiện nào đó hoạt động ra sao.
But I'm building a circuit. I'm trying to understand how a certain component is behaving. I'm trying to just fit a polynomial to some data.
Tôi đang cố khớp một đa thức với dữ liệu. Làm sao biết việc mình làm có tốt không? Giả sử tôi có dữ liệu.
How do I know if what I am doing is any good? Say I have some data, right? I can fit a polynomial to it. I can say that this is my y.
Tôi có thể khớp một đa thức vào đó. Đây là y của tôi. Đây là x của tôi. Tôi có thể viết y bằng alpha 1x cộng alpha naught.
This is my x. I can say y is equal to alpha 1x plus alpha naught. This is one model, Model 1.
Đây là một mô hình, Model 1. Model 2 là y bằng alpha 2x bình phương cộng alpha 1x cộng alpha naught.
Model 2 is y is equal to alpha 2x squared plus alpha 1x plus alpha naught.
Model 3 là y bằng alpha 3x lập phương cộng alpha 2x bình phương cộng alpha 1x cộng alpha naught.
Model 3 is y is equal to alpha 3x cubed plus alpha 2x squared plus alpha 1x plus alpha naught. Right? I can make as many models as I want.
Đúng không? Tôi có thể tạo bao nhiêu mô hình tùy thích. Và tôi có thể lấy mô hình nào tôi muốn rồi khớp nó với bất kỳ dữ liệu nào.
And I can take whatever model I want and I could fit it to whatever data I want. But I need to know that I'm not just making up nonsense.
Nhưng tôi cần biết mình không chỉ đang bịa ra thứ vô nghĩa. Đúng không? Và đó chính là ý tưởng của validation.
Right? And this is basically the idea of validation. So if I could go back to my computer for a minute?
Cho tôi quay lại máy tính một phút nhé? Tốt rồi. Đây là đoạn code mà có thể các em đã quen, với những bạn đã bắt đầu làm bài tập về nhà.
Perfect. So this is some code that might be familiar to you, for those of you have who have already started the homework. But let's say you are given, actually, a device.
Nhưng giả sử các em được cho một thiết bị. Đúng không? Giả sử các em đang cố hiểu đường đặc tuyến IV của một thiết bị nào đó.
Right? Let's say you're trying to understand the IV curve for a certain device. Or you're trying to understand the relationship between x and y variables. And you're given this data.
Hoặc đang cố hiểu mối quan hệ giữa x đường cong cho một thiết bị nào đó. Hoặc bạn đang cố tìm hiểu mối quan hệ giữa x và y. Và bạn được cho dữ liệu này.
It looks awfully line-like. But how do I know what I can fit it with?
Trông nó rất giống một đường thẳng. Nhưng làm sao biết nên khớp nó bằng loại hàm nào?
So here I have some code that I can basically input the degree of a polynomial that I want to fit. And it'll fit it for me.
Ở đây tôi có một đoạn code, cho phép nhập bậc của đa thức mà tôi muốn khớp. Và nó sẽ khớp giúp tôi.
So I can fit a polynomial of degree 1. And you can see that it's plotting a line. I could try and fit a polynomial of degree 2.
Tôi có thể khớp đa thức bậc 1. Và bạn thấy nó vẽ ra một đường thẳng. Tôi có thể thử khớp đa thức bậc 2.
I can try and fit a polynomial of degree 3. And pay attention to this number that is the error magnitude here. Right? This is basically capturing how many points are not on the line.
Tôi có thể thử đa thức bậc 3. Và hãy chú ý con số này, đây là độ lớn của sai số. Đúng không? Về cơ bản nó cho biết có bao nhiêu điểm không nằm trên đường.
So I can pick degree 4. So it's 60.8. I can pick degree 5. My error decreased a little bit.
Tôi chọn bậc 4. Sai số là 60,8. Tôi chọn bậc 5. Sai số giảm đi một chút.
I can pick degree 6. My error decreased, even, a little bit more. As I keep increasing the degree of this polynomial, my error keeps going more and more — it keeps going down, right?
Tôi chọn bậc 6. Sai số lại giảm thêm một chút nữa. Khi tôi cứ tăng bậc của đa thức này, sai số cứ ngày càng... cứ giảm dần, đúng không?
I'm increasing the complexity of my polynomial and increasing the complexity of my model. And basically, then, saying that, well, I can improve things. But how do I know I'm not just fitting the noise?
Tôi đang tăng độ phức tạp của đa thức và tăng độ phức tạp của mô hình. Và như vậy nghĩa là tôi có thể cải thiện kết quả. Nhưng làm sao biết tôi không chỉ đang khớp với nhiễu?
Right? How do I know that this is not just coming from something made up?
Đúng không? Làm sao biết đây không phải là thứ tự bịa ra?
So for this, what you can do is basically — what you do is you take the data that you have, and you divide it up into two sets.
Vậy ở đây, cách làm là... bạn lấy dữ liệu đang có và chia thành hai tập.
You divide it up into a training data set, and you divide it up into a validation data set.
Một tập dữ liệu huấn luyện (training), và một tập dữ liệu kiểm định (validation).
And you say, well, I'm going to see and fit a model to the half of the data points, or some third of the data points, that is basically what are the data points that I have.
Bạn nói: tôi sẽ khớp một mô hình với một nửa, hoặc một phần ba số điểm dữ liệu, tức là một phần các điểm dữ liệu mà tôi có.
And then I take some remaining part of the data points that I don't use for this training purpose. I don't use them to fit my least squares coefficients.
Rồi tôi lấy phần còn lại của dữ liệu mà tôi không dùng để huấn luyện. Tôi không dùng chúng để khớp các hệ số bình phương tối thiểu.
And I evaluate the performance on these other data points. Do you see that I basically split my data into these two parts?
Và tôi đánh giá hiệu năng trên những điểm dữ liệu còn lại này. Bạn thấy chứ, tôi chia dữ liệu thành hai phần như vậy.
So what this plot here is showing is that I can start at a degree 1 polynomial. I can end at a degree 15 polynomial.
Đồ thị này cho thấy tôi có thể bắt đầu từ đa thức bậc 1. Và kết thúc ở đa thức bậc 15.
And as I keep increasing the degree, I keep, somehow, fitting all the noise points.
Và khi tôi cứ tăng bậc, bằng cách nào đó tôi khớp cả các điểm nhiễu.
And this error, which is just saying that, well, how far away are each of my points from the line, just keeps getting better and better.
Và sai số này, tức là mỗi điểm cách đường bao xa, cứ tốt hơn và tốt hơn.
Because the line, the more degree I have, it keeps wriggling, wiggling to fit more and more points. But we know that that's somehow not a good thing.
Vì bậc càng cao thì đường càng uốn éo, ngoằn ngoèo để khớp ngày càng nhiều điểm. Nhưng ta biết đó không phải là điều tốt.
So what we're going to do is, instead, we're going to fit the polynomial on these training points.
Nên thay vào đó, ta sẽ khớp đa thức trên các điểm huấn luyện.
And we're going to compute the error, we're going to compute the cost on these validation data points.
Và ta sẽ tính sai số, tính chi phí trên các điểm dữ liệu kiểm định này.
And so what this validation cost is saying is saying, you've trained on these guys, this training data. But now, I'm going to test you on this validation data.
Chi phí kiểm định này nói rằng: bạn đã học trên dữ liệu huấn luyện này. Nhưng giờ tôi sẽ kiểm tra bạn trên dữ liệu kiểm định.
And now, if I look at my cost, well, it keeps starting to go up, basically. I can say that, well, the particular noise that was in your training data, you fit.
Và giờ nếu nhìn vào chi phí, ta thấy nó bắt đầu tăng lên. Tức là phần nhiễu cụ thể trong dữ liệu huấn luyện thì bạn đã khớp.
And you decreased your costs there. But in a more general case, you're actually going to do quite poorly. So that's just a one degree example.
Và bạn đã giảm chi phí ở đó. Nhưng trong trường hợp tổng quát hơn, bạn thực ra sẽ làm khá tệ. Đó mới chỉ là một ví dụ về bậc.
But you can also think about — let's say you have this. Right? Here this is the data that you're given. You want to try and fit a polynomial and understand what's going on.
Nhưng bạn cũng có thể nghĩ đến... giả sử bạn có cái này. Đúng không? Đây là dữ liệu bạn được cho. Bạn muốn thử khớp một đa thức và hiểu chuyện gì đang xảy ra.
So let's say I can choose by starting to fit a degree 1. Right? Doesn't look too good. I can fit degree 2.
Giả sử tôi bắt đầu bằng cách khớp bậc 1. Đúng không? Trông không tốt lắm. Tôi khớp bậc 2.
Doesn't look too good.
Cũng không tốt lắm.
Degree 3, ah, making progress — degree 4, oh, better — degree 5, how do I know when to stop?
Bậc 3, à, có tiến triển... bậc 4, ồ, tốt hơn... bậc 5, làm sao biết khi nào dừng?
I can do degree 10. Whoa! They're all good, right? Which one do I pick?
Tôi có thể thử bậc 10. Chà! Cái nào cũng tốt hết, đúng không? Vậy chọn cái nào?
This is where I basically need to now look at this validation cost. I take this data, and I say, well, I'm actually going to split it.
Đây là lúc ta cần nhìn vào chi phí kiểm định. Tôi lấy dữ liệu này và nói: tôi sẽ chia nó ra.
I'm going to say some of it is training data, where I can use to choose my model. The rest is validation data.
Một phần là dữ liệu huấn luyện, dùng để chọn mô hình. Phần còn lại là dữ liệu kiểm định.
And now, I see a massive cost of degree 1, massive cost of degree 2. At degree 3, suddenly, the cost drops. And it looks like it's flatlining here.
Và giờ tôi thấy chi phí rất lớn ở bậc 1, chi phí rất lớn ở bậc 2. Đến bậc 3, chi phí đột nhiên giảm. Và trông như nó đi ngang ở đây.
But actually, that's just because this axis is skewed. So if I actually started degree 3, you can see that degree 4, degree 5, degree 6, actually, the cost is increasing.
Nhưng thật ra đó chỉ là do trục này bị méo tỉ lệ. Nếu tôi bắt đầu từ bậc 3, bạn sẽ thấy ở bậc 4, bậc 5, bậc 6, chi phí thực ra đang tăng.
So what I want to just communicate to you is that whenever you're doing this engineering job, you're saying, well, let me model the world as x. Let me model the world as y.
Điều tôi muốn nhắn gửi các bạn là mỗi khi làm công việc kỹ thuật này, bạn nói: hãy mô hình hóa thế giới là x. Hãy mô hình hóa thế giới là y.
Let me have this set up. Make sure you actually validate your models. Divide your data up into training data and validation data. It's easy to make a model that works.
Hãy thiết lập như thế này. Nhớ kiểm định mô hình của bạn. Hãy chia dữ liệu thành dữ liệu huấn luyện và dữ liệu kiểm định. Tạo ra một mô hình chạy được thì dễ.
But you have no way of knowing whether it's good or not. You can run ONP on anything. But you might violate the sparsity assumptions, right?
Nhưng bạn không có cách nào biết nó tốt hay không. Bạn có thể chạy OMP trên bất cứ thứ gì. Nhưng bạn có thể vi phạm các giả thiết về tính thưa, đúng không?
How do you know that you're not just picking out noise? This is where validation comes in.
Làm sao biết mình không chỉ đang chọn ra nhiễu? Đây là lúc cần đến validation (kiểm định).
And it's an important tool of any engineer and anyone who wants to do any kind of data processing going forward. So I'm going to basically end the lecture here.
Và đó là một công cụ quan trọng của mọi kỹ sư và của bất kỳ ai muốn xử lý dữ liệu dưới bất kỳ hình thức nào sau này. Nên về cơ bản tôi sẽ kết thúc bài giảng ở đây.
Don't have too much time, because there's [INAUDIBLE] people who want to go and talk about surveys. But just to remind all of you of where you've come so far, right?
Không còn nhiều thời gian, vì có [KHÔNG NGHE RÕ] những bạn muốn lên nói về các khảo sát. Nhưng xin nhắc lại để các bạn thấy mình đã đi được đến đâu, nhỉ?
You have just been introduced to validation, which is a key concept that basically everyone in machine learning and any kind of engineer uses all the time.
Các bạn vừa được giới thiệu về validation, một khái niệm then chốt mà gần như mọi người làm machine learning và mọi kỹ sư đều dùng thường xuyên.
But if you think about where you've come so far, where did you start off at the beginning of the semester? You started off with just deciding how to learn to model.
Nhưng nghĩ lại xem các bạn đã đi được bao xa, đầu học kỳ các bạn bắt đầu từ đâu? Các bạn bắt đầu từ việc quyết định cách học một mô hình.
And what you have is, well, you've built your own camera. You've built two different types of touchscreens, and you've built your own GPS.
Và giờ thì các bạn đã tự xây dựng một chiếc máy ảnh. Các bạn đã xây hai loại màn hình cảm ứng, và tự xây một hệ thống GPS.
If you think about it, that's a pretty impressive accomplishment for about three months of time. So make sure you don't forget that. And make sure you're proud of how far you've come this semester.
Nghĩ mà xem, đó là một thành tựu khá ấn tượng trong khoảng ba tháng. Nên đừng quên điều đó. Và hãy tự hào về việc các bạn đã tiến xa thế nào trong học kỳ này.
And this wasn't the only class you were taking. You did this while taking a series of other classes. And for many of you, navigating your first semester at Berkeley.
Đây cũng không phải môn duy nhất các bạn học. Các bạn làm được điều này khi còn học nhiều môn khác. Và với nhiều bạn, đó còn là học kỳ đầu tiên ở Berkeley.
So make sure that you remember that. Enjoy it. And there's a lot of other courses that you can go forward to take.
Nên hãy nhớ điều đó. Hãy tận hưởng nó. Và còn rất nhiều môn khác mà các bạn có thể học tiếp.
So hopefully, this will inspire you to explore a large variety of classes.
Hy vọng điều này sẽ truyền cảm hứng để các bạn khám phá nhiều môn học đa dạng.
And if any of you have any questions about any of these classes, Professor Boser and I are always very, very happy to talk about it.
Và nếu bạn nào có câu hỏi về các môn này, Giáo sư Boser và tôi luôn rất sẵn lòng trao đổi.
So look forward to seeing some of you on course staff next semester. And I will pass on to [INAUDIBLE].. I'll be outside at the end of class, if anyone has any questions.
Mong được gặp một số bạn trong đội ngũ trợ giảng học kỳ sau. Và tôi xin chuyển cho [KHÔNG NGHE RÕ]. Tôi sẽ ở ngoài cửa khi hết giờ, nếu ai có câu hỏi.
But for H10, I'm required to leave the room. Thank you.
Nhưng đến tiết H10, tôi phải rời phòng. Cảm ơn các bạn.
[APPLAUSE] I'll get out.
[VỖ TAY] Tôi ra ngoài đây.
[INTERPOSING VOICES] [TAPS MICROPHONE] GIREEJA RANADE: That works better. Yeah.
[NHIỀU GIỌNG NÓI XEN KẼ] [GÕ VÀO MICRO] GIREEJA RANADE: Thế này tốt hơn. Vâng.
STUDENT
[INAUDIBLE].
[KHÔNG NGHE RÕ].
GIREEJA RANADE
Oh. You want to use the [INAUDIBLE].
Ồ. Bạn muốn dùng [KHÔNG NGHE RÕ].
STUDENT
[INAUDIBLE].
[KHÔNG NGHE RÕ].
GIREEJA RANADE
If you have a minute, we would really appreciate if you could stay for the [INAUDIBLE] reviews.
Nếu các bạn có chút thời gian, chúng tôi rất mong các bạn ở lại cho phần [KHÔNG NGHE RÕ] đánh giá.
This is really important for us, as course staff, to understand how things went over the course of the semester. It's just five minutes. But these are your fellow students.
Điều này rất quan trọng với chúng tôi, đội ngũ giảng dạy, để hiểu mọi việc diễn ra thế nào trong suốt học kỳ. Chỉ năm phút thôi. Đây là những bạn sinh viên cùng khoa.
They're putting in time to be here and do this service for the department. It would be really nice if you could just wait for five more minutes. Thank you so much.
Các bạn ấy dành thời gian đến đây làm việc này cho khoa. Sẽ thật tuyệt nếu các bạn có thể đợi thêm năm phút. Cảm ơn các bạn rất nhiều.
STUDENT
Thank you. Yeah. Hi, everyone. So we're from [INAUDIBLE],, as Professor Ranade said.
Cảm ơn ạ. Vâng. Chào mọi người. Bọn mình đến từ [KHÔNG NGHE RÕ], như Giáo sư Ranade đã nói.
We're just here to encourage you all to do the course evaluations. They're super important for the professors and all the TAs to understand how they did.
Bọn mình đến để khuyến khích các bạn làm đánh giá môn học. Chúng rất quan trọng để các giáo sư và tất cả trợ giảng biết mình đã làm được đến đâu.
And your feedback will be read by them and will be taken into account for future iterations of the class. So basically, here's the link. It's just course-evaluations.Berkeley.edu.
Phản hồi của các bạn sẽ được họ đọc và được cân nhắc cho những lần mở lớp sau của môn học. Đây là đường dẫn. Chỉ là course-evaluations.Berkeley.edu.
And then, these are also good practices for when you're doing it. You also probably got emails about doing course evaluations. So hopefully a lot of you will have done it already.
Và đây cũng là những cách làm tốt khi các bạn điền đánh giá. Chắc các bạn cũng đã nhận email về việc đánh giá môn học. Hy vọng nhiều bạn đã làm rồi.
But in case you haven't, here's five or six minutes to do it right now. Thank you.
Nhưng nếu chưa, đây là năm sáu phút để làm ngay bây giờ. Cảm ơn các bạn.
STUDENT
Yeah. So these course evaluations are really, really important.
Vâng. Những đánh giá môn học này thực sự rất quan trọng.
The only reason why the class is how it is right now is because all the previous years, every single year, the students have done these course evaluations.
Lý do duy nhất khiến môn học được như hiện nay là vì tất cả các năm trước, năm nào sinh viên cũng làm các đánh giá này.
So if you really enjoy this class, it'd be a good time to sort of voice your opinion and say, like, oh, what you liked about it so it can continue staying good.
Nếu các bạn thật sự thích môn này, đây là lúc tốt để nêu ý kiến và nói các bạn thích điều gì để môn học tiếp tục tốt.
And if you didn't like it so much, then it's a perfect opportunity for you to say what part of the class, you thought did not go as well so it can be changed and improved for all the future years of people doing this.
Còn nếu các bạn không thích lắm, thì đây là cơ hội hoàn hảo để nói phần nào của môn học chưa tốt để có thể được thay đổi và cải thiện cho tất cả các khóa sau này.
So please, again, if you haven't done your course evaluations, please go up to course-evaluations.Berkeley.edu right now. We're giving you time right now in class to do it.
Vì vậy, một lần nữa, nếu chưa làm đánh giá môn học, hãy vào course-evaluations.Berkeley.edu ngay bây giờ. Chúng tôi dành thời gian ngay trong lớp để các bạn làm.
It will take just a few, like, five to 10 minutes. And that would really help out. Thank you.
Chỉ mất khoảng năm đến 10 phút. Điều đó sẽ giúp ích rất nhiều. Cảm ơn các bạn.
[INTERPOSING VOICES] [APPLAUSE] STUDENT: OK.
[NHIỀU GIỌNG NÓI XEN KẼ] [VỖ TAY] SINH VIÊN: Được rồi.
It's 2:00. So yeah, you all are good to go.
2 giờ rồi. Vậy là các bạn có thể ra về.
STUDENT
If you have any questions — STUDENT: Yeah. If you have any questions, I guess we'll hang out for a bit. But you don't have to stay anymore.
Nếu có câu hỏi nào — SINH VIÊN: Vâng. Nếu có câu hỏi nào, bọn mình sẽ ở lại một lúc. Nhưng các bạn không cần ở lại nữa.
If you're still doing your course eval, that'd be great. But thanks. Oh, what's up, Michael?
Nếu còn đang làm đánh giá thì tốt quá. Nhưng cảm ơn các bạn. Ồ, có chuyện gì thế, Michael?
STUDENT
[INAUDIBLE]?
[KHÔNG NGHE RÕ]?
STUDENT
It's just 16A.
Chỉ là 16A thôi.
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.