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ả.
[MUTED] [INTERPOSING VOICES]
[TẮT TIẾNG] [NHIỀU NGƯỜI NÓI CHEN NHAU]
GIREEJA RANADE
Okay, welcome to Lecture 3 of Module 3.
Được rồi, chào mừng các em đến với Bài giảng 3 của Mô-đun 3.
Before we get started, I wanted to share this really cool project that some of your fellow students in the department are doing.
Trước khi bắt đầu, cô muốn chia sẻ một dự án thật thú vị mà một số bạn sinh viên cùng khoa với các em đang thực hiện.
So this is a project that is being done by EE84, which is a class, hands-on ham radio taught by Miki Lustig.
Đây là dự án do lớp EE84 thực hiện, một lớp thực hành về radio nghiệp dư (ham radio) do thầy Miki Lustig dạy.
And what they did was released a balloon from the top of Cory Hall. These are all EEG students.
Các bạn ấy đã thả một quả bóng bay từ trên nóc tòa nhà Cory Hall. Tất cả đều là sinh viên EEG.
And this balloon was equipped with the following.
Quả bóng này được gắn các thiết bị sau.
What this is a solar cell right here, this horizontal thing.
Đây là một tấm pin mặt trời, cái nằm ngang này.
This is an antenna plus a GPS chip, as well as there's a small Arduino on it and a radio antenna. And these are two super capacitors.
Đây là một ăng-ten cộng với chip GPS, ngoài ra còn có một bo Arduino nhỏ và một ăng-ten radio. Còn đây là hai siêu tụ điện.
So this was the entire payload off that balloon. And if you want to look a little bit more closely — ah, this thing.
Đó là toàn bộ tải trọng của quả bóng. Nếu muốn nhìn kỹ hơn một chút... à, cái này.
Maybe this is a better way to do it. So this is the thing that's hanging off of it. This is the GPS antenna, the GPS chip. There's a little Arduino microcontroller here.
Có lẽ cách này tốt hơn. Đây là phần treo bên dưới quả bóng. Đây là ăng-ten GPS, chip GPS. Đây là một vi điều khiển Arduino nhỏ.
So there's at least three things on here that should look vaguely familiar to 16A students.
Vậy là có ít nhất ba thứ ở đây mà sinh viên 16A sẽ thấy hơi quen.
And what they did was they said, well, we're going to release this balloon from the top of Cory Hall. And we're going to actually use GPS to track where it's going.
Các bạn ấy nghĩ rằng, mình sẽ thả quả bóng này từ nóc Cory Hall. Và dùng GPS để theo dõi xem nó đi đâu.
So what this shows is here it's being released in Berkeley.
Hình này cho thấy nó được thả ở Berkeley.
Then it crossed into Nevada, went over into Idaho, Wyoming, into Kansas, Missouri, Tennessee, South Carolina.
Rồi nó bay qua Nevada, sang Idaho, Wyoming, đến Kansas, Missouri, Tennessee, South Carolina.
And it is now left the continental United States. And how does this work? Right?
Và giờ nó đã rời khỏi lục địa Hoa Kỳ. Vậy nó hoạt động thế nào? Đúng không?
Basically, this antenna here receives the signals, exactly the same signature that we've been talking about in class, from these 24 GPS satellites. And it figures out exactly what the propagation delays.
Về cơ bản, ăng-ten này nhận tín hiệu, hoàn toàn giống các tín hiệu đặc trưng mà ta đã học trên lớp, từ 24 vệ tinh GPS này. Và nó tính chính xác các độ trễ lan truyền.
That's what this GPS chip does. This GPS chip then performs essentially the trilateration algorithm, which is what we're going to talk about today.
Đó là việc của chip GPS này. Sau đó chip GPS thực hiện thuật toán định vị ba điểm (trilateration), chính là điều ta sẽ nói hôm nay.
Hopefully, all of you figured it out between last lecture and now.
Hy vọng các em đã tự tìm ra từ bài giảng trước đến giờ.
And then the radio antenna basically transmits this to one of these several receiving stations over here.
Sau đó ăng-ten radio truyền dữ liệu này đến một trong số các trạm thu ở đằng kia.
The protocol that they use is this protocol called Automatic Packet Reporting System, APRS.
Giao thức họ dùng là Automatic Packet Reporting System, APRS.
And once a particular tower receives it, they either rebroadcast or relay it or upload it to the internet. And that is how this map is exactly generated.
Khi một trạm thu nhận được, họ phát lại, chuyển tiếp hoặc tải lên internet. Đó chính là cách bản đồ này được tạo ra.
So there is a balloon that was released from the top of Cory Hall five days ago. It is somewhere now over the Atlantic Ocean. We don't exactly know where, but it is being tracked.
Vậy là có một quả bóng đã được thả từ nóc Cory Hall cách đây năm ngày. Giờ nó đang ở đâu đó trên Đại Tây Dương. Ta không biết chính xác ở đâu, nhưng nó vẫn đang được theo dõi.
And it was made by students from this department using ideas that you are learning about in this class now.
Nó do sinh viên của khoa làm ra, dùng những ý tưởng mà các em đang học trong lớp này.
We haven't talked about every single detail about how to make this GPS chip and we haven't talked about every single software implementation of the GPS algorithm.
Ta chưa nói về mọi chi tiết của việc chế tạo chip GPS này, và cũng chưa nói về mọi cách cài đặt phần mềm của thuật toán GPS.
However, I'm hoping you can put all of these things together to see where you can go.
Tuy nhiên, cô hy vọng các em có thể ghép những thứ này lại để thấy mình có thể đi đến đâu.
So if you're interested in this kind of stuff, you can go ahead and take a series of classes, right, 120, 123, and then the ham radio class as well to kind of build on these things.
Nếu các em thích những thứ này, có thể học một loạt môn như 120, 123, và cả lớp ham radio nữa để phát triển thêm.
And as you can see, it's not really just one piece, like it's not one class that is being used to make this happen, right.
Và như các em thấy, đây không chỉ là một mảnh ghép, không phải chỉ một môn học được dùng để làm ra nó, đúng không.
There is stuff from multiple upper division level classes that are being put together to be able to realize this super cool project.
Có kiến thức từ nhiều môn chuyên ngành năm trên được kết hợp lại để hiện thực hóa dự án siêu thú vị này.
So when you're going through your career here, when you're going through classes, try to keep this hat on of interconnections between things and realizing that true engineering always requires you to synthesize different parts of things and different parts of the material and bring them together.
Vì vậy, trong suốt quá trình học ở đây, khi học các môn, hãy luôn nghĩ đến sự liên kết giữa các thứ, và nhận ra rằng kỹ thuật thực thụ luôn đòi hỏi các em tổng hợp nhiều phần khác nhau của nhiều mảng kiến thức và kết hợp chúng lại.
So remember to think about connections across classes. Don't necessarily say, oh, well, this is type A class, type B class, type C class. They all really come together.
Nên hãy nhớ nghĩ đến mối liên hệ giữa các môn. Đừng vội nói, ồ, đây là môn loại A, môn loại B, môn loại C. Tất cả đều gắn kết với nhau.
And you really need different types of techniques to make a complex system like this work. So I just thought that this was super cool, especially given that we are studying GPS now.
Và các em thực sự cần nhiều loại kỹ thuật khác nhau để một hệ thống phức tạp như thế này hoạt động. Cô thấy dự án này siêu thú vị, nhất là khi ta đang học về GPS.
And I wanted to show it off to you. So if you have any friends in this class, make sure to ask them for more details about how they actually made this.
Nên cô muốn khoe với các em. Nếu các em có bạn trong lớp đó, hãy hỏi họ thêm chi tiết về cách các bạn ấy làm ra nó.
Okay, so with that, I will move to actually talking about the lecture.
Được rồi, bây giờ cô sẽ chuyển sang nội dung của bài giảng.
So we are Module 3, Lecture 3. And there's two announcements before we begin.
Ta đang ở Mô-đun 3, Bài giảng 3. Có hai thông báo trước khi bắt đầu.
First, you should have seen a Piazza post about the optional lab that is going to be happening.
Thứ nhất, các em hẳn đã thấy bài đăng trên Piazza về bài thí nghiệm (lab) tùy chọn sắp diễn ra.
So this is the chance for you to try out a lab that we are considering offering in future iterations of 16A. But it is completely optional.
Đây là cơ hội để các em thử một bài lab mà chúng tôi đang cân nhắc đưa vào các khóa 16A sau này. Nhưng hoàn toàn không bắt buộc.
The only reason to do it is if you're really curious. And what this lab is talking about is talking about how to basically transmit an image using an audio signal.
Lý do duy nhất để làm là nếu các em thật sự tò mò. Bài lab này nói về cách truyền một hình ảnh bằng tín hiệu âm thanh.
So there's details on the Piazza website. It will talk also about ideas of correlation and encoding, decoding wireless communication. So all of these ideas, we'll be talking about in this lab.
Chi tiết có trên trang Piazza. Bài này cũng nói về các ý tưởng như tương quan và mã hóa, giải mã, truyền thông không dây. Tất cả những ý tưởng này sẽ được bàn trong bài lab.
If you're interested, please check out the Piazza post and sign up.
Nếu quan tâm, hãy xem bài đăng trên Piazza và đăng ký.
The second thing is that next week is going to be Thanksgiving week. So hopefully, you will all get a nice break. We will have lecture on Tuesday.
Thứ hai là tuần sau là tuần Lễ Tạ ơn. Hy vọng các em sẽ có một kỳ nghỉ thoải mái. Ta vẫn có buổi học vào thứ Ba.
And so that there is no homework that will be due the Friday of Thanksgiving, that homework is going to be due on Monday.
Và vì sẽ không có bài tập nào đến hạn vào thứ Sáu của tuần Lễ Tạ ơn, bài tập đó sẽ đến hạn vào thứ Hai.
So you don't have to turn in the homework the Friday after Thanksgiving. Instead, you'll just be turning it on Monday. So make sure you look into this.
Vậy các bạn không phải nộp bài tập vào thứ Sáu sau Lễ Tạ ơn. Thay vào đó, các bạn nộp vào thứ Hai. Nên hãy nhớ xem kỹ điều này.
These dates are all on the website and were announced at the beginning of class. But just make sure that you're aware of this, so that you don't forget to submit the homework.
Các ngày này đều có trên trang web và đã được thông báo đầu buổi học. Nhưng các bạn cứ lưu ý điều này để không quên nộp bài tập.
So what have we been doing over the past couple of lectures, right? We've been really thinking about how to make this GPS system work.
Vậy mấy buổi học vừa qua chúng ta đã làm gì nhỉ? Đúng không? Chúng ta đã suy nghĩ xem làm sao để hệ thống GPS này hoạt động.
And in the very first lecture, we focused on which satellite is transmitting.
Ở bài giảng đầu tiên, chúng ta tập trung vào việc vệ tinh nào đang phát tín hiệu.
And we used inner products to figure this out.
Và ta dùng tích vô hướng để tìm ra điều đó.
The second lecture, we focused on, well, you know, now I know which satellite is talking to me, but how do I figure out how far away that satellite is?
Ở bài thứ hai, ta tập trung vào việc: được rồi, giờ tôi biết vệ tinh nào đang nói chuyện với mình, nhưng làm sao biết vệ tinh đó cách bao xa?
So what was the distance and the propagation delay?
Tức là khoảng cách và độ trễ lan truyền là bao nhiêu?
And the technical tool that we talked about for this was correlation, which is essentially, as you've probably seen from discussion now, is just a sliding inner product.
Và công cụ kỹ thuật mà ta đã dùng cho việc này là tương quan, về bản chất, như các bạn có lẽ đã thấy trong buổi thảo luận, chỉ là một tích vô hướng trượt.
It's just inner product, but like one signal's moving along the other. And when the inner product, that shift at which the inner product is maximized, is basically the shift that you're interested in.
Nó vẫn là tích vô hướng, nhưng một tín hiệu được dịch chuyển dọc theo tín hiệu kia. Và độ dịch mà tại đó tích vô hướng đạt cực đại chính là độ dịch mà ta quan tâm.
So this is just a moving inner product.
Vậy đây chỉ là một tích vô hướng chuyển động.
So now that we have all of these distances of these different satellites from our position of interest, what remains to be done is how do we combine all of these signals to actually compute the location of our receiver?
Giờ ta đã có tất cả các khoảng cách đến các vệ tinh khác nhau từ vị trí mình quan tâm, việc còn lại là làm sao kết hợp tất cả các tín hiệu này để thực sự tính ra vị trí của bộ thu của chúng ta?
So how do we go from distances to location?
Vậy làm sao đi từ khoảng cách đến vị trí?
And this is the trilateration algorithm that we talked about briefly last time. And what did we see in this trilateration algorithm?
Và đây là thuật toán định vị ba điểm (trilateration) mà ta đã nói sơ qua hồi trước. Vậy trong thuật toán định vị ba điểm này ta đã thấy gì?
What did we see when we set this up last time? This is where we ended in last class.
Lần trước khi thiết lập bài toán, ta đã thấy gì? Đây là chỗ ta dừng lại ở buổi trước.
What did you notice?
Các bạn đã nhận thấy điều gì?
What kind of equations did we get when we started trying to figure out, well, let's say I have one landmark here or a beacon or a satellite or whatever you want to call it, another landmark, another landmark, and I know distances from these three landmarks?
Ta nhận được loại phương trình nào khi bắt đầu tìm cách xác định, giả sử tôi có một mốc ở đây, hay một trạm phát hay một vệ tinh, gọi sao cũng được, rồi một mốc nữa, một mốc nữa, và tôi biết khoảng cách đến ba mốc này?
What kind of equation — how do I write that equation out? Well, if my position, let's say, is the unknown vector x, I have some origin here.
Loại phương trình nào, tôi viết phương trình đó ra sao? Giả sử vị trí của tôi là vectơ chưa biết x, tôi có một gốc tọa độ ở đây.
I'm interested in my position relative to the origin. And let's say I know that each of my landmarks are at positions vector A, vector B, and vector C.
Tôi quan tâm đến vị trí của mình so với gốc. Và giả sử tôi biết các mốc nằm ở các vị trí vectơ A, vectơ B và vectơ C.
And I know my distances from each of these landmarks.
Và tôi biết khoảng cách từ mình đến từng mốc.
What kind of equation do I get when I write out these distances? A quadratic, right. It's a second degree equation. And what do we do with second degree equations?
Khi viết các khoảng cách này ra, tôi nhận được loại phương trình nào? Bậc hai, đúng rồi. Đó là phương trình bậc hai. Vậy ta làm gì với phương trình bậc hai?
Have we developed some months full of machinery to solve quadratic equations? Not in this class. There's definitely ways of solving quadratic equations and systems of quadratic equations.
Ta đã xây dựng cả một bộ công cụ đồ sộ để giải phương trình bậc hai chưa? Chưa, trong môn này thì chưa. Chắc chắn có cách giải phương trình bậc hai và hệ phương trình bậc hai.
But here, we're focusing entirely on linear equations. So the question is, how do we go from these quadratic equations to talking about a linear equation? And that's what we want to talk about next.
Nhưng ở đây, ta chỉ tập trung vào phương trình tuyến tính. Vậy câu hỏi là làm sao đi từ các phương trình bậc hai này sang phương trình tuyến tính? Và đó là điều ta muốn nói tiếp theo.
And that is what the trilateration algorithm is. So now, what are exactly the equations that we have? Okay, I'll just move this here for now.
Và đó chính là thuật toán định vị ba điểm. Vậy chính xác thì ta có những phương trình nào? Được rồi, tôi tạm dời cái này sang đây.
So we have three equations. Let's say I have x minus a. This is equal to d1 squared.
Ta có ba phương trình. Giả sử tôi có x trừ a. Cái này bằng d1 bình phương.
I have x minus b is equal to d2 squared. And x minus c is equal to d3 squared.
Tôi có x trừ b bằng d2 bình phương. Và x trừ c bằng d3 bình phương.
Where do we go from here? We ended at this point in the last lecture. Any ideas on what we should be doing?
Từ đây ta đi tiếp thế nào? Ta đã dừng ở điểm này trong bài giảng trước. Các bạn có ý tưởng gì ta nên làm không?
When you see something complex and you're kind of trying to figure out what the next step to take is, what's a good standard way of progressing? Yeah.
Khi gặp một thứ phức tạp và đang loay hoay không biết bước tiếp theo là gì, cách tiến hành chuẩn và hay là gì? Vâng, bạn.
STUDENT
A simple example.
Thử một ví dụ đơn giản.
GIREEJA RANADE
Try a simple example. That's an excellent idea. So we can try a simple example. And we kind of started with this 2D scenario.
Thử một ví dụ đơn giản. Ý tưởng rất hay. Vậy ta có thể thử một ví dụ đơn giản. Và ta cũng đã bắt đầu với trường hợp 2D này.
So we could go back to that, and I think that would be a perfectly great way of doing it.
Nên ta có thể quay lại đó, và tôi nghĩ đó sẽ là một cách làm hoàn toàn tốt.
Today, I'm not going to do a simple example, simply because we don't have enough time to do that in class. But on an exam, if you're in the situation, 100% I support doing that.
Hôm nay tôi sẽ không làm ví dụ đơn giản, đơn giản vì ta không đủ thời gian để làm trong lớp. Nhưng trong kỳ thi, nếu gặp tình huống này, tôi hoàn toàn ủng hộ việc làm như vậy.
Did someone else have a hand? Okay. Another thing that you can do when you see some kind of expressions that are somewhat complicated is see if you can express them in simpler terms.
Có bạn nào khác giơ tay không? Được rồi. Một việc khác bạn có thể làm khi thấy những biểu thức khá phức tạp là xem có thể biểu diễn chúng đơn giản hơn không.
That can also often help. So I want to just manipulate this equation. I have this equation 1. And I want to pull out the quadratic-ness of this.
Cách này cũng thường giúp ích. Vậy tôi muốn biến đổi phương trình này. Tôi có phương trình 1 này. Và tôi muốn tách phần bậc hai ra khỏi nó.
So how can I write this norm in another way?
Vậy làm sao viết chuẩn này theo cách khác?
I can write this as x minus a transpose times x minus a equal to d1 squared.
Tôi có thể viết là x trừ a, chuyển vị, nhân x trừ a, bằng d1 bình phương.
And can I somehow rearrange terms to separate out the quadratic part and the linear part of this equation? So here, this is basically x transpose minus a transpose.
Và liệu tôi có thể sắp xếp lại các số hạng để tách phần bậc hai và phần tuyến tính của phương trình này không? Ở đây, cái này về cơ bản là x chuyển vị trừ a chuyển vị.
And then I have x minus a.
Rồi tôi có x trừ a.
So when I expand this, what do I get? x transpose times x.
Khi khai triển, ta được gì? x chuyển vị nhân x.
I get basically the norm squared of x when I multiply this out. What about a transpose times a?
Khi nhân ra, về cơ bản ta được chuẩn bình phương của x. Còn a chuyển vị nhân a thì sao?
This gives me the norm squared of a.
Cái này cho ta chuẩn bình phương của a.
And then I have minus x transpose a minus a transpose x.
Rồi ta có trừ x chuyển vị nhân a trừ a chuyển vị nhân x.
This is equal to d1 squared.
Cái này bằng d1 bình phương.
Okay, these two terms, are these two different terms here at the end? Not really, right, because the order of an inner product doesn't actually matter.
Được rồi, hai số hạng này, có phải là hai số hạng khác nhau không, hai số hạng ở cuối đây? Thật ra không, vì thứ tự của một tích vô hướng không quan trọng.
So I can just write this as x norm of x squared plus norm of a squared minus 2 inner product x a.
Nên tôi có thể viết lại thành chuẩn của x bình phương cộng chuẩn của a bình phương trừ 2 lần tích vô hướng của x và a.
Okay? So what is the annoying term here? The annoying term here is this quadratic term. I don't like this quadratic term.
Được chứ? Vậy số hạng phiền phức ở đây là gì? Số hạng phiền phức ở đây là số hạng bậc hai này. Tôi không thích số hạng bậc hai này.
How can I get rid of this quadratic term? What I'm going to do is now I'm going to basically use a little trick. I can do this computation for the first equation.
Làm sao để loại bỏ số hạng bậc hai này? Bây giờ tôi sẽ dùng một mẹo nhỏ. Tôi có thể tính như vậy cho phương trình đầu tiên.
I can also similarly get the second equation in the following form.
Tương tự, tôi cũng có thể viết phương trình thứ hai theo dạng sau.
I can write it as norm of x squared plus norm of b squared minus 2 inner product between x and b is equal to d2 squared.
Tôi viết nó là chuẩn của x bình phương cộng chuẩn của b bình phương trừ 2 lần tích vô hướng của x và b bằng d2 bình phương.
And the third equation gives me norm of x squared plus norm of c squared minus 2 inner product x and c gives me d3 squared.
Còn phương trình thứ ba cho tôi chuẩn của x bình phương cộng chuẩn của c bình phương trừ 2 lần tích vô hướng của x và c bằng d3 bình phương.
So let's call this equation 4. Let's call this equation 5. And let's call this equation 6.
Ta gọi đây là phương trình 4. Đây là phương trình 5. Và đây là phương trình 6.
So what happens now if I, let's say, take equation 4 minus equation 5?
Vậy chuyện gì xảy ra nếu, chẳng hạn, ta lấy phương trình 4 trừ phương trình 5?
What do I get? 4 minus 5, what happens to these x squareds? They cancel out.
Ta được gì? 4 trừ 5, các số hạng x bình phương thì sao? Chúng triệt tiêu nhau.
So I have norm of a squared minus norm of b squared minus 2 inner product xa plus 2 inner product xb is equal to d1 squared minus d2 squared.
Nên ta có chuẩn của a bình phương trừ chuẩn của b bình phương trừ 2 lần tích vô hướng xa cộng 2 lần tích vô hướng xb bằng d1 bình phương trừ d2 bình phương.
And now if I take 4 minus 6, can I write a similar equation? Why don't you just write it out to make sure that the algebra is correct.
Và nếu lấy 4 trừ 6, ta có thể viết một phương trình tương tự không? Các bạn cứ viết ra đi để chắc là phần đại số đúng.
What's the most important property of the equation that we now have here?
Tính chất quan trọng nhất của phương trình mà ta có bây giờ là gì?
Is this now a quadratic equation anymore?
Đây còn là phương trình bậc hai nữa không?
We have used basically the fact that we had three equations to turn them into two linear equations, because these two terms are both linear in x.
Ta đã tận dụng việc có ba phương trình để biến chúng thành hai phương trình tuyến tính, vì hai số hạng này đều tuyến tính theo x.
I can just rewrite this.
Tôi có thể viết lại.
So let's take this equation and rewrite it as this is basically — minus 2x transpose times a.
Ta lấy phương trình này và viết lại nó về cơ bản là — trừ 2 x chuyển vị nhân a.
Or let me actually write this as 2 a transpose times x and plus 2 b transpose times x equal to d1 squared minus d2 squared.
Hoặc để tôi viết là 2 a chuyển vị nhân x cộng 2 b chuyển vị nhân x bằng d1 bình phương trừ d2 bình phương.
It doesn't matter which one I take the transpose of. I can write these in either order. So now, you have a linear equation in x. How many variables are there in x?
Lấy chuyển vị của cái nào cũng không sao. Tôi có thể viết theo thứ tự nào cũng được. Vậy bây giờ ta có một phương trình tuyến tính theo x. x có bao nhiêu biến?
x is a vector with two components. So I get one equation. I get two equations. So can I now solve for x?
x là một vectơ có hai thành phần. Vậy tôi có một phương trình. Tôi có hai phương trình. Vậy giờ ta giải được x chưa?
So I've used basically the fact that I had these three beacons, I had three satellites, even though they gave me quadratic equations, because of the form of the quadratic equations, I was basically able to manipulate them to becoming linear equations.
Ta đã tận dụng việc có ba trạm phát tín hiệu, ba vệ tinh, dù chúng cho tôi các phương trình bậc hai, nhưng nhờ dạng của các phương trình bậc hai đó, ta đã biến đổi được chúng thành các phương trình tuyến tính.
Now, can you set up a matrix equation that basically you can use Gaussian elimination on for this? That's just a question of algebra manipulation.
Bây giờ, các bạn có thể thiết lập một phương trình ma trận để dùng phép khử Gauss cho bài này không? Đó chỉ là biến đổi đại số thôi.
Everyone with me here? Questions?
Mọi người theo kịp chứ? Có câu hỏi nào không?
Take a minute. Think about it. Talk to your neighbor. Make sure from this point on, you actually know how to solve this.
Dành một phút. Hãy suy nghĩ. Trao đổi với bạn bên cạnh. Hãy chắc rằng từ đây trở đi, các bạn thực sự biết cách giải bài này.
[INTERPOSING VOICES] GIREEJA RANADE: Any questions?
[NHIỀU GIỌNG NÓI CHEN NHAU] GIREEJA RANADE: Có câu hỏi nào không?
Is everyone with me?
Mọi người theo kịp chứ?
STUDENT
There is a question.
Em có một câu hỏi.
GIREEJA RANADE
Oh, here. Thank you.
À, ở đây. Cảm ơn em. Cảm ơn em.
STUDENT
You mentioned that x is an annoying variable. I don't understand, because you still have 2 squared variables and x was just a square. So what's the difference between ab and x?
Thầy nói x là biến phiền phức. Em không hiểu, vì vẫn còn 2 biến bình phương mà x cũng chỉ là một bình phương. Vậy ab khác x ở chỗ nào ạ?
GIREEJA RANADE
So a and b — the question is, how many unknowns are there in x? x here is a 2D variable. So this is the x1 axis, x2 axis.
Vậy a và b — câu hỏi là x có bao nhiêu ẩn? x có bao nhiêu ẩn? x ở đây là biến 2D. Đây là trục x1, trục x2.
So x is equal to x1, x2. So there are two scalars that are unknown. So if I have two scalar unknowns, I need two equations to solve them.
Vậy x bằng x1, x2. Có hai ẩn vô hướng chưa biết. Nếu có hai ẩn vô hướng, tôi cần hai phương trình để giải.
Whereas I'm saying what is my position relative to the Campanile. And we're assuming that everyone knows where the Campanile is. This is my position relative to Doe Library, which is given by b.
Còn ở đây, tôi hỏi vị trí của tôi so với tháp Campanile là gì. Và ta giả sử mọi người đều biết Campanile ở đâu. Đây là vị trí của tôi so với thư viện Doe, được cho bởi b.
And we're assuming that everyone knows where Doe Library is. So a, b, c are known.
Và ta giả sử mọi người biết thư viện Doe ở đâu. Vậy a, b, c đã biết.
So when I have a norm of a squared here, it's just a number. Whereas the norm of x squared is x1 squared plus x2 squared. Does that answer the question?
Nên khi có chuẩn của a bình phương ở đây, nó chỉ là một con số. Còn chuẩn của x bình phương là x1 bình phương cộng x2 bình phương. Vậy đã trả lời câu hỏi của em chưa?
STUDENT
Yep, got it.
Dạ, em hiểu rồi.
GIREEJA RANADE
Got it. Other questions? That's an excellent question. Everyone get that?
Tốt. Còn câu hỏi nào khác không? Đó là một câu hỏi rất hay. Mọi người hiểu chưa?
STUDENT
Should it be minus norm of a squared?
Chỗ đó có nên là trừ chuẩn của a bình phương không ạ?
GIREEJA RANADE
Should it be minus norm of a squared? I don't think so. But you can check the algebra. It's just algebra.
Có nên là trừ chuẩn của a bình phương không? Tôi nghĩ là không. Nhưng em cứ kiểm tra lại phần đại số. Chỉ là đại số thôi mà.
Other questions? Yes.
Còn câu hỏi nào khác không? Vâng, mời em.
STUDENT
When you move the norm of a squared, b squared to the outside, would you make it like all of b squared minus a squared?
Khi thầy chuyển chuẩn của a bình phương, b bình phương ra ngoài, thì có phải sẽ thành cả b bình phương trừ a bình phương không ạ?
GIREEJA RANADE
Yes, it might be a minus sign error. That's exactly the question that he just asked. Other questions? Over there?
Đúng, có thể là lỗi dấu trừ. Đó chính xác là câu hỏi bạn ấy vừa hỏi. Còn câu hỏi nào khác không? Bạn ở đằng kia?
No.
Không.
Yeah, I didn't do this algebra right now. We can check. This might be a minus sign. Yes, this will be a minus sign.
Ừ, lúc nãy tôi chưa biến đổi đại số này cho đúng. Ta kiểm tra nhé. Chỗ này có thể là dấu trừ. Đúng, đây sẽ là dấu trừ.
Okay.
Được rồi.
I don't really care about the algebraic manipulations. All I care about is that you see that this is a linear equation.
Tôi không quan tâm lắm đến các phép biến đổi đại số. Điều tôi quan tâm là các em thấy đây là một phương trình tuyến tính.
And if you have two linear equations and two unknowns, then you can solve. That's the point. Question?
Và nếu có hai phương trình tuyến tính và hai ẩn, thì ta giải được. Đó là điểm mấu chốt. Câu hỏi?
STUDENT
So since we did this right now in a 2D space, if we do it in 3D space, would we have to add another satellite?
Vì bây giờ ta làm trong không gian 2D, nếu làm trong không gian 3D thì có phải thêm một vệ tinh nữa không ạ?
GIREEJA RANADE
Excellent question. The question was we did this in a 2D space, and we had three satellites.
Câu hỏi rất hay. Câu hỏi là: ta làm trong không gian 2D và có ba vệ tinh.
So now we wanted to do this in 3D space, exactly, we would need to add a fourth satellite. Just like in the 1D space, we could do it with two landmarks.
Giờ muốn làm trong không gian 3D, đúng vậy, ta cần thêm vệ tinh thứ tư. Cũng như trong không gian 1D, ta làm được với hai mốc.
In a 2D space, we needed three landmarks. In a 3D space, we will need four landmarks. So exactly. Yes, question?
Trong không gian 2D, ta cần ba mốc. Trong không gian 3D, ta sẽ cần bốn mốc. Chính xác. Vâng, câu hỏi?
STUDENT
Is the pattern because we're trying to get rid of the quadratic term.
Quy luật đó có phải vì ta đang cố triệt tiêu số hạng bậc hai không ạ?
GIREEJA RANADE
The question was, is the pattern because you're trying to get rid of the quadratic term?
Câu hỏi là: quy luật đó có phải vì ta đang cố triệt tiêu số hạng bậc hai không?
Essentially, yes, because you can think about it in 2D when you have basically two quadratic equations or two circle will intersect in two points.
Về cơ bản là đúng, vì trong 2D, hai phương trình bậc hai, tức hai đường tròn, sẽ cắt nhau tại hai điểm.
You need a way of disambiguating which of those points it is.
Ta cần cách phân biệt xem đó là điểm nào.
Other questions? Okay, so we're all on the same page about trilateration? Everyone gets it? So this is the computation that is being performed by the GPS chip, right.
Còn câu hỏi nào khác không? Vậy cả lớp đã hiểu trilateration chưa? Ai cũng hiểu chứ? Đây là phép tính mà chip GPS thực hiện. Đúng không?
Except there's a little bit of a problem, right?
Nhưng có một vấn đề nhỏ, đúng không?
What happens if — this is a small little chip. It's doing some computation. There's lots of other interference going around.
Chuyện gì xảy ra nếu... đây là con chip nhỏ xíu. Nó đang thực hiện một số phép tính. Xung quanh có rất nhiều nhiễu khác.
What if there is some noise in the system that makes it feel like your GPS or your satellite is at a slightly different distance than you thought it was?
Nếu có nhiễu trong hệ thống khiến GPS của bạn có cảm giác vệ tinh ở xa hơn hoặc gần hơn một chút so với thực tế thì sao?
You get a reflected measurement of the GPS signal. You have some tiny little errors. What happens in the trilateration algorithm?
Bạn đo được tín hiệu GPS bị phản xạ. Bạn có những sai số rất nhỏ. Điều gì xảy ra với thuật toán trilateration?
Let's say I have these three circles.
Giả sử tôi có ba đường tròn này.
But what if — actually, maybe I can draw here — what if instead of getting three circles that intersect at a point, I get the following?
Nhưng nếu... có lẽ tôi vẽ ở đây được... nếu thay vì ba đường tròn cắt nhau tại một điểm, ta có hình như sau thì sao?
Where now is my location? I get these equations. But are these going to be consistent? Am I going to be able to solve them?
Vậy vị trí của tôi bây giờ ở đâu? Ta có các phương trình này. Nhưng chúng có nhất quán không? Liệu ta có giải được không?
Is there going to be a unique solution?
Liệu có nghiệm duy nhất không?
STUDENT
No.
Không.
GIREEJA RANADE
No, right, we know that even when you have n questions and n unknowns, it's possible that you might not have a unique solution.
Không, đúng rồi, ta biết rằng ngay cả khi có n phương trình và n ẩn, vẫn có thể không có nghiệm duy nhất.
So this is basically what we want to deal with in the rest of the class, which is we're going to get to part 4 of the problem, which is dealing with noise.
Đây chính là điều ta muốn xử lý trong phần còn lại của buổi học, tức là ta sẽ đến phần 4 của bài toán, là xử lý nhiễu.
And this is going to take us to the least squares algorithm and projections.
Và nó sẽ đưa ta đến thuật toán bình phương tối thiểu và phép chiếu.
And that's the technical tool we're going to use. So that's the agenda for the rest of our lecture today.
Đó là công cụ kỹ thuật ta sẽ dùng. Đó là nội dung cho phần còn lại của buổi học hôm nay.
So which paper do you want, the equations or the summary?
Vậy bạn muốn tờ nào, phương trình hay tóm tắt?
STUDENT
Summary.
Tóm tắt.
GIREEJA RANADE
Summary. No?
Tóm tắt. Không?
STUDENT
Yes.
Có.
GIREEJA RANADE
Okay.
Được rồi.
So typically, we have systems of equations.
Thông thường, ta có các hệ phương trình.
When we write a system of equations, we think of a system of equations as ax equal to b.
Khi viết một hệ phương trình, ta nghĩ nó là ax bằng b.
What we want to think about now is how to solve a system of linear equations when we don't have ax equal to b.
Giờ ta muốn nghĩ về việc giải hệ phương trình tuyến tính khi không có ax bằng b.
We have ax is approximately — how do I spell approximate?
Ta có ax xấp xỉ... xấp xỉ viết thế nào nhỉ?
M-a-t-e — approximately b.
x-ấ-p x-ỉ... xấp xỉ b.
What does this mean? This could be even just the imaging lab. You have all actually already experienced noisy measurements.
Điều này nghĩa là gì? Ví dụ ngay trong bài lab chụp ảnh. Thực ra các em đều đã gặp các phép đo có nhiễu rồi.
When you're taking your measurements during the imaging lab, what you collect back using your photodiode, you can see that there is noise in there. Your image that you get out isn't perfect.
Khi đo trong bài lab chụp ảnh, dữ liệu các em thu về bằng photodiode có thể thấy là có nhiễu. Ảnh các em thu được không hoàn hảo.
And that's because sometimes you collect light that comes in from somewhere else. It's not just the reflected light that you get. You get slight reflections from other places.
Đó là vì đôi khi các em thu cả ánh sáng đến từ nơi khác. Không chỉ là ánh sáng phản xạ mà các em muốn đo. Các em nhận thêm phản xạ nhẹ từ những chỗ khác.
And there is all these kinds of issues that show up. And so you tried improving on it by thinking about the eigenvalues and designing a clever measurement matrix.
Và có đủ loại vấn đề như vậy xuất hiện. Các em đã thử cải thiện bằng cách nghĩ về giá trị riêng và thiết kế một ma trận đo thật khéo.
But we're going to talk now about another technique that uses more measurements to actually get rid of this noise.
Nhưng giờ ta sẽ nói về một kỹ thuật khác, dùng nhiều phép đo hơn để loại bỏ nhiễu này.
And what we're going to think about it now how do we solve these systems when ax is only approximately b?
Và điều ta sẽ xét bây giờ là làm sao giải các hệ này khi ax chỉ xấp xỉ b?
So what I want to do is I want to find an x such that x is as close to b as possible.
Vậy tôi muốn tìm một x sao cho ax gần b nhất có thể.
So when I look at my options in terms of these ax's, what is the dimension of ax? ax is a vector. a is a matrix. x is a vector.
Khi nhìn các lựa chọn là những vectơ ax này, ax có số chiều là bao nhiêu? ax là một vectơ. a là một ma trận. x là một vectơ.
But a times x is just a vector. Everyone remember that? b is a vector. So let's say I have some vector b in my space.
Nhưng a nhân x chỉ là một vectơ. Mọi người còn nhớ chứ? b là một vectơ. Giả sử tôi có một vectơ b nào đó trong không gian của mình.
This is my vector b.
Đây là vectơ b của tôi.
What are the possible values that ax can take?
Ax có thể nhận những giá trị nào?
ax represents all of the vectors that are in the column space of a.
ax biểu diễn tất cả các vectơ nằm trong không gian cột của a.
ax always belongs to the column space of a.
ax luôn thuộc không gian cột của a.
So if I want to think about and just draw a picture of this, or a cartoon picture, I can think of, well, maybe this is the column space of a.
Nếu muốn hình dung và vẽ một hình minh họa đơn giản, thì có thể coi đây là không gian cột của a.
And this is my origin. This is 0. And I can choose any ax in this plane, if this was the column space.
Và đây là gốc tọa độ. Đây là 0. Tôi có thể chọn bất kỳ ax nào trong mặt phẳng này, nếu đây là không gian cột.
Any of these are valid values for ax.
Điểm nào ở đây cũng là giá trị hợp lệ của ax.
And I want to say, well, where can I go in the column space of a, such that I'm closest to b?
Và ta muốn hỏi: trong không gian cột của a, đi đến đâu thì gần b nhất?
Does everyone see what we're trying to do here? Yes, question.
Mọi người thấy ta đang định làm gì chưa? Vâng, mời em hỏi.
STUDENT
So are you saying that b is not in the column space so we need the best approximation to it?
Vậy ý cô là b không nằm trong không gian cột, nên ta cần xấp xỉ tốt nhất cho nó ạ?
GIREEJA RANADE
Great question. Are we saying that b is not in the column space? And the answer is essentially yes.
Câu hỏi hay. Có phải b không nằm trong không gian cột không? Về cơ bản là đúng vậy.
If b was in the column space, we could say that we can exactly solve this equation.
Nếu b nằm trong không gian cột, ta có thể giải chính xác phương trình này.
But sometimes you will end up with noisy observations that will lead to b not being in this column space.
Nhưng đôi khi các quan sát bị nhiễu, khiến b không nằm trong không gian cột này.
If b was exactly in the column space, then a inverse b would give you exactly the solution you wanted.
Nếu b nằm đúng trong không gian cột, thì a nghịch đảo nhân b sẽ cho đúng nghiệm mà ta muốn.
But now we want to start thinking about cases where a inverse b either doesn't give you the solution, or we cannot compute a inverse, because a is not square.
Nhưng giờ ta muốn xét các trường hợp mà a nghịch đảo nhân b không cho ra nghiệm, hoặc ta không tính được a nghịch đảo vì a không vuông.
So this is what we're going to move towards. There was another question over here somewhere?
Đó là hướng ta sẽ đi tới. Còn câu hỏi nào ở đâu đó bên này không?
STUDENT
It was the same one GIREEJA RANADE: Same one, okay.
Em cũng hỏi câu đó ạ. Cùng câu đó, được rồi.
So we want to think about cases, the interesting cases here.
Vậy ta muốn xét các trường hợp thú vị ở đây.
a is not square.
a không vuông.
In fact, we want to think of a is an m by n matrix.
Cụ thể, ta xét a là ma trận m nhân n.
And we want to think in particular about cases where we have more equations than unknowns.
Và đặc biệt ta quan tâm đến các trường hợp có nhiều phương trình hơn ẩn số.
Why do we want to think about this case where we have more equations than unknowns?
Tại sao ta muốn xét trường hợp nhiều phương trình hơn ẩn số?
Because this is something, if, let's say, I know that my observations are noisy, what do I want to be able to do?
Vì giả sử tôi biết các quan sát của mình bị nhiễu, thì tôi muốn làm gì?
I want to be able to just basically be able to take multiple measurements to somehow average away the effect of the noise.
Tôi muốn có thể đo nhiều lần để bằng cách nào đó lấy trung bình, triệt tiêu ảnh hưởng của nhiễu.
Like for example, if we're looking at scores of students on 16A homework, we know that sometimes there is a little bit of noise that creeps into the system.
Ví dụ, khi xét điểm bài tập về nhà 16A của sinh viên, ta biết đôi khi có chút nhiễu lọt vào hệ thống.
You don't do as well or as well as you potentially could have. So we take averages across all of the different scores to get a good sense, because there is noise in measurement.
Bạn làm không tốt bằng mức có thể đạt được. Nên ta lấy trung bình các điểm khác nhau để có cái nhìn đúng hơn, vì phép đo có nhiễu.
Because every single time you submit a homework, it's not exactly the same level of performance.
Vì mỗi lần nộp bài tập về nhà, mức độ làm bài không hoàn toàn giống nhau.
Similarly, when you're taking measurements of any real system, if you have noise, what you want to do is you want to be able to take these multiple measurements to basically get rid of the impact of noise.
Tương tự, khi đo đạc một hệ thống thực nào có nhiễu, ta muốn đo nhiều lần để loại bỏ tác động của nhiễu.
And so that's what we're going to be thinking about here.
Đó là điều ta sẽ xét ở đây.
So to be able to solve this problem and to be able to really understand how to go from here, I want to now come back to the suggestion that was made at the beginning and start with a very simple example.
Để giải bài toán này và hiểu rõ cách đi tiếp từ đây, giờ tôi quay lại gợi ý đã được nêu lúc đầu và bắt đầu với một ví dụ rất đơn giản.
So let us think about this very simple case where a is just essentially a vector.
Hãy xét trường hợp rất đơn giản này, trong đó a về cơ bản chỉ là một vectơ.
And b is also a vector.
Và b cũng là một vectơ.
So a I'm thinking about as a 2 by 1 matrix. b as a 2 by 1 vector. Essentially, a here is also a vector.
Tôi coi a là ma trận 2 nhân 1. b là vectơ 2 nhân 1. Về cơ bản, a ở đây cũng là một vectơ.
And I want to say, well, let me think about this a.
Hãy xem xét a này.
I can also call this just this a vector, because in this special simple case that we're thinking about, we're thinking about the case where this matrix is essentially a vector.
Tôi cũng có thể gọi nó là vectơ a, vì trong trường hợp đặc biệt đơn giản đang xét, ma trận này về cơ bản là một vectơ.
And I have some b.
Và tôi có một b nào đó.
Do you see how this is basically a simple version of this?
Mọi người thấy đây là phiên bản đơn giản của bài toán kia chứ?
Now, we're allowed to move in the span of vector a.
Giờ ta được di chuyển trong không gian sinh (span) của vectơ a.
We're allowed to move anywhere that's basically some scalar multiple of the vector a. And we want to see, what is the point along this vector?
Ta được đi đến bất kỳ đâu là bội số vô hướng nào đó của vectơ a. Và ta muốn tìm điểm nào dọc theo vectơ này gần đầu mút của vectơ b nhất, nhớ là có thể đi bước âm.
And remember, we can take negative steps that is closest to the tip of this vector b. That's what we want to find.
gần đầu mút của vectơ b nhất. Đó là điều ta muốn tìm.
So maybe from geometry that you've looked at before, do you have an intuition of what that's going to be? Yeah, at the back.
Từ hình học đã học, có lẽ các em đoán được đó sẽ là điểm nào chứ? Vâng, em ở cuối lớp.
STUDENT
It's a right triangle.
Đó là một tam giác vuông ạ.
GIREEJA RANADE
Right triangle. Create a right triangle. What do we know?
Tam giác vuông. Tạo một tam giác vuông. Ta biết gì?
We have a theorem from geometry that says that the shortest distance between a point and a line is given by the perpendicular from the point to the line.
Hình học có một định lý nói rằng khoảng cách ngắn nhất từ một điểm đến một đường thẳng là đoạn vuông góc hạ từ điểm đó xuống đường thẳng.
So what this is saying is saying, well, from here, let's call this point p. From p, draw this perpendicular to the line.
Nghĩa là, từ đây, gọi điểm này là p. Từ p, hạ đường vuông góc xuống đường thẳng.
This point Q is the point along a that is closest to the point b.
Điểm Q này là điểm trên a gần điểm b nhất.
So now, since we've done this in geometry before, but we want to do this proof using vector ideas, let's think about this vector here as being the vector z.
Ta đã làm điều này trong hình học rồi, nhưng ta muốn chứng minh bằng các ý tưởng về vectơ, nên gọi vectơ này là vectơ z.
So if I call this the origin O, this segment OQ is basically represented by the vector z. And we have this distance PQ.
Nếu gọi gốc là O, đoạn OQ này về cơ bản được biểu diễn bởi vectơ z. Và ta có khoảng cách PQ.
So what do we know about z?
Vậy ta biết gì về z?
z is basically — we know z must be some alpha times a, where alpha is a scalar, because z belongs to the span of this vector a.
z phải bằng alpha nhân a, với alpha là một số vô hướng, vì z thuộc không gian sinh (span) của vectơ a.
How would you now use basically your intuition from geometry to try and show that the closest point along a is actually just this point in here, Q?
Giờ làm sao dùng trực giác hình học để chứng minh rằng điểm gần nhất dọc theo a thật sự là điểm Q này?
We can say that, well, let's suppose, let's consider, let's say hypothetically, there was some other point that was actually closer.
Ta có thể nói: giả sử, giả định rằng có một điểm khác gần hơn.
Let's say that there was some point here. Let's call this, let's say, R. That R is actually closer to P than Q is. Then I can consider this triangle PQR.
Giả sử có một điểm ở đây. Gọi nó là R. Giả sử R thật sự gần P hơn so với Q. Khi đó ta có thể xét tam giác PQR.
Say R is closer to P than Q is.
Giả sử R gần P hơn Q.
So what this is saying is that, well, PR is smaller somehow than PQ. The length of PR is smaller than PQ if R was closer.
Điều này nghĩa là PR phải nhỏ hơn PQ. Độ dài PR nhỏ hơn PQ nếu R gần hơn.
But as was pointed out, what do we have here? What does this make you think of? How do you want to proceed from here?
Nhưng như đã có bạn chỉ ra, ở đây ta có gì? Hình này gợi cho các em nhớ đến điều gì? Các em muốn tiếp tục như thế nào?
Someone who hasn't spoken yet.
Một bạn chưa phát biểu nhé.
Yeah.
Mời bạn.
STUDENT
You could write out Pythagorean theorem.
Ta có thể viết định lý Pythagoras.
GIREEJA RANADE
You could write out the Pythagorean theorem. Do you have to even write out the Pythagorean theorem? What does the Pythagorean theorem say?
Ta có thể viết định lý Pythagoras. Mà có cần phải viết ra định lý Pythagoras không? Định lý Pythagoras nói gì?
It says that the length of PQ square — Pythagoras says that PQ squared plus QR squared is equal to PR squared, right?
Nó nói rằng bình phương độ dài PQ — Pythagoras nói PQ bình phương cộng QR bình phương bằng PR bình phương, đúng không?
So what does that mean?
Vậy điều đó có nghĩa là gì?
This means that length of PR must be larger than the length of PQ, because you take the length of PQ and you add something, which gives you PR.
Nghĩa là độ dài PR phải lớn hơn độ dài PQ, vì ta lấy độ dài PQ rồi cộng thêm một đại lượng thì được PR.
The hypotenuse — this is the hypotenuse of the right angle triangle — is always the longest side of a right angled triangle.
Cạnh huyền, tức cạnh huyền của tam giác vuông, luôn là cạnh dài nhất của một tam giác vuông.
So what this means is that whichever point it is that makes this right angle triangle is actually the closest point to the point p.
Vậy điều này có nghĩa là điểm nào tạo ra tam giác vuông này thì chính là điểm gần điểm P nhất.
So the hypotenuse is the longest side.
Cạnh huyền là cạnh dài nhất.
And this says, therefore, this vector z is basically the closest point.
Do đó, vectơ z này về cơ bản là điểm gần nhất.
If we want it to represent the segment PQ using a vector notation, how could we write it?
Nếu muốn biểu diễn đoạn PQ bằng ký hiệu vectơ, ta viết thế nào?
We could write it basically as this vector b minus this vector z, because z plus this vector going here gives me b.
Ta viết nó là vectơ b trừ vectơ z, vì z cộng vectơ đi tới đây thì ra b.
This vector plus this vector gives me b. So this vector must be b minus z.
Vectơ này cộng vectơ này bằng b. Nên vectơ này phải là b trừ z.
So I can write b minus z is therefore smaller than b minus u, if let's say I called this other vector u, any other vector, u.
Vậy ta viết được b trừ z nhỏ hơn b trừ u, nếu gọi vectơ khác này là u, một vectơ bất kỳ khác, u.
This z is called the projection of b onto a.
z này gọi là hình chiếu của b lên a.
So a projection of one vector onto another vector is basically if the projection of b onto a is that vector z, that is in the span of a, it's basically along this line, but it's as close as it can be to b, to this vector b, to this point P.
Hình chiếu của một vectơ lên một vectơ khác nghĩa là, nếu hình chiếu của b lên a là vectơ z, thì nó nằm trong không gian sinh (span) của a, tức là nằm trên đường thẳng này, nhưng gần b nhất có thể, gần vectơ b này, điểm P này.
And you can see that this basically makes sense. You don't want to go all the way far out over here. You don't want to go all the way far out over here.
Và điều này khá hợp lý. Ta không muốn đi ra thật xa ở đây. Cũng không muốn đi ra thật xa ở đây.
You're going to basically try and choose this point that is as close as possible. Yes, question.
Ta sẽ chọn điểm nào gần nhất có thể. Mời em hỏi.
STUDENT
Does it have to be b minus squared is [INAUDIBLE] GIREEJA RANADE: Oh, basically b minus z squared is PQ squared.
Có phải b trừ bình phương là [KHÔNG NGHE RÕ] GIREEJA RANADE: À, b trừ z bình phương chính là PQ bình phương.
And b minus u squared is PR squared.
Còn b trừ u bình phương là PR bình phương.
This is PR squared.
Đây là PR bình phương.
And this is PQ squared.
Còn đây là PQ bình phương.
Everyone with me here? Any questions?
Mọi người theo kịp chưa? Có câu hỏi nào không?
This is basically — what you have just done is you have just done least squares for a simple system where everything is two-dimensional.
Về cơ bản, những gì các em vừa làm là bình phương tối thiểu cho một hệ đơn giản mà mọi thứ đều nằm trong hai chiều.
This is the least squares algorithm, all of this, that's it. Nothing more complicated. Yes.
Đây chính là thuật toán bình phương tối thiểu, toàn bộ chỗ này, vậy thôi. Không có gì phức tạp hơn. Mời em.
STUDENT
Can you do a projection of a vector onto a [INAUDIBLE] GIREEJA RANADE: Yes, that is exactly what we're going to do next. Question.
Có thể chiếu một vectơ lên một [KHÔNG NGHE RÕ] GIREEJA RANADE: Có, đó chính xác là điều chúng ta sẽ làm tiếp theo. Câu hỏi nào.
STUDENT
Should there be a square next to the b minus?
Cạnh b trừ có cần dấu bình phương không ạ?
GIREEJA RANADE
Should there be a square next to — yes, there should be a square here.
Có cần bình phương cạnh — đúng rồi, ở đây phải có bình phương.
Thank you. Other questions? At the back. No?
Cảm ơn em. Còn câu hỏi nào khác không? Ở cuối lớp. Không à?
Yes.
Mời em.
STUDENT
So does a represent our column space in this problem?
Vậy a có biểu diễn không gian cột trong bài này không ạ?
GIREEJA RANADE
Does a represent our column space in the problem? Yes, in this case because the matrix a is just a column vector. The column space of that matrix is the span of that vector.
GIREEJA RANADE: a có biểu diễn không gian cột trong bài này không? Có, trong trường hợp này vì ma trận a chỉ là một vectơ cột. Không gian cột của ma trận đó là không gian sinh (span) của vectơ đó.
So the span of a represents the column space. Yep, great question. Yes, question.
Vậy span của a chính là không gian cột. Câu hỏi hay đấy. Mời em.
STUDENT
Is there a reason the column space is a plane?
Tại sao không gian cột lại là một mặt phẳng ạ?
GIREEJA RANADE
How do I know the column space is a plane? We haven't gotten there yet. So in general the column space will not just be a plane. It it'll be a hyperplane.
Làm sao biết không gian cột là một mặt phẳng? Chúng ta chưa tới đó. Nói chung không gian cột không chỉ là một mặt phẳng. Nó sẽ là một siêu phẳng (hyperplane).
But we can draw those. So I drew a plane.
Nhưng ta có thể vẽ những cái này. Nên tôi vẽ một mặt phẳng.
Good questions. Any other questions? Also, the word hyperplane — plane is something that is two-dimensional.
Câu hỏi hay. Còn câu hỏi nào khác không? Nhân tiện, từ hyperplane — mặt phẳng là thứ có hai chiều.
Hyperplane is just the generalization of that concept to higher dimensions, except we don't know how to draw or visualize these things. So we don't.
Siêu phẳng chỉ là sự tổng quát hóa khái niệm đó lên các chiều cao hơn, chỉ là ta không biết vẽ hay hình dung những thứ này. Nên ta không vẽ.
STUDENT
How would we get the value of alpha?
Làm sao tìm được giá trị của alpha ạ?
GIREEJA RANADE
How would we get the value of alpha? Thank you. I was going to ask that question. But you asked it for me instead.
Làm sao tìm giá trị của alpha? Cảm ơn em. Tôi định hỏi câu đó. Nhưng em đã hỏi giúp tôi rồi.
So let's get the value of alpha. We have this z. And we have computed it by basically — we said, well, you can drop this — you can draw is perpendicular.
Vậy ta hãy tìm giá trị của alpha. Ta có z này. Và ta đã tính nó bằng cách — ta nói rằng, bạn có thể thả — bạn có thể vẽ đường vuông góc.
But a computer who wants to, let's say, solve this system or compute this projection cannot really draw a picture and then draw an angle and then measure. That doesn't work.
Nhưng một máy tính muốn, chẳng hạn, giải hệ này hoặc tính hình chiếu này thì không thể vẽ hình rồi vẽ góc rồi đo được. Cách đó không được.
How can you algebraically compute the value of this alpha? So let's do that next.
Vậy làm sao tính bằng đại số giá trị của alpha này? Ta cùng làm điều đó tiếp theo.
How do we find alpha?
Làm sao tìm alpha?
So why don't you take a minute to think about it? Like discuss with your neighbors. You know, spend some time. Basically, I'll give you a big hint.
Vậy các em dành một phút suy nghĩ nhé? Trao đổi với bạn bên cạnh. Cứ dành chút thời gian. Thầy/cô gợi ý lớn nhé.
We just discussed something in the last few lectures that connect vectors to the angle between vectors. And here, we care about the angles between vectors. So maybe that'll be helpful.
Mấy bài giảng gần đây mình vừa học một thứ nối vectơ với góc giữa các vectơ. Và ở đây ta quan tâm đến góc giữa các vectơ. Nên có thể nó sẽ hữu ích.
So take a minute to think. Question or an answer?
Các em nghĩ một phút nhé. Em hỏi hay trả lời?
STUDENT
An answer.
Trả lời ạ.
GIREEJA RANADE
Okay, then hold on.
Được, khoan đã.
[INTERPOSING VOICES] GIREEJA RANADE: So how many people
[NHIỀU NGƯỜI NÓI CÙNG LÚC] GIREEJA RANADE: Có bao nhiêu bạn
think they have an idea for how maybe you can kind of proceed? Okay, a few people. How many people want another minute to think? Everyone wants to proceed together?
nghĩ mình có ý tưởng để tiến hành? Được, một vài bạn. Bao nhiêu bạn muốn nghĩ thêm một phút? Cả lớp muốn cùng làm tiếp nhé?
Okay, let's do that. So, yeah, there was a suggestion at the back?
Được, làm thế nhé. Ở cuối lớp có bạn đề xuất đúng không?
Yeah, do you have a suggestion?
Em có gợi ý gì không?
STUDENT
Yeah, wouldn't alpha be b plus z?
Dạ, alpha có phải là b cộng z không ạ?
GIREEJA RANADE
Wouldn't alpha be b plus z? Oh, this is not focused.
GIREEJA RANADE: alpha là b cộng z à? Ồ, cái này chưa rõ ý.
STUDENT
Yeah, like keep the vector and [INAUDIBLE] down to a.
Dạ, giữ vectơ và [KHÔNG NGHE RÕ] xuống a.
GIREEJA RANADE
So, yeah, good point. So let me just draw this out again. So we have this vector z here. We have this vector b here.
Ừ, ý hay đấy. Để thầy/cô vẽ lại. Ta có vectơ z ở đây. Có vectơ b ở đây.
This b should go a little higher. This is b. Okay, these are the two vectors we have. And we have this third vector here.
b này nên cao hơn một chút. Đây là b. Được, đây là hai vectơ ta có. Và ta có vectơ thứ ba ở đây.
And let me call this vector y. So I have now vector z plus vector y equal to vector b. b is equal to z plus y.
Gọi vectơ này là y. Vậy giờ vectơ z cộng vectơ y bằng vectơ b. b bằng z cộng y.
And so if I wanted to write y in terms of b and z, I could write y is equal to b minus z.
Nếu muốn viết y theo b và z, ta viết y bằng b trừ z.
So that's just the name of — like you can think of this vector — that's where this b minus z came from.
Đó chỉ là tên của — các em có thể xem vectơ này — b trừ z xuất phát từ đây.
I'm just basically saying that I can write this vector as b minus z.
Thầy/cô chỉ nói rằng có thể viết vectơ này là b trừ z.
But what we want to find out, we know that z is equal to some alpha times a, and the question is, how do we find this alpha?
Nhưng điều cần tìm, ta biết z bằng alpha nhân a, và câu hỏi là làm sao tìm alpha này?
Other person, yeah. Exactly, you.
Bạn khác nào, mời. Đúng, em đó.
STUDENT
I just had a suggestion real quick.
Em có một gợi ý nhanh ạ.
GIREEJA RANADE
Yeah, a suggestion.
Ừ, em nói đi.
STUDENT
[INAUDIBLE] at the angle [INAUDIBLE] And the other thing, [INAUDIBLE] GIREEJA RANADE: So there's a suggestion that's saying let's look at inner products.
[KHÔNG NGHE RÕ] ở góc [KHÔNG NGHE RÕ] Và điều còn lại, [KHÔNG NGHE RÕ] GIREEJA RANADE: Có một gợi ý là hãy xét tích vô hướng.
The suggestion is saying what is the one technique that we have that connects vectors to angles? And that's inner products.
Gợi ý này hỏi: công cụ nào nối vectơ với góc? Đó là tích vô hướng.
And we can look at basically the inner product between this vector b and the vector a.
Ta có thể xét tích vô hướng giữa vectơ b và vectơ a.
And if we have some theta here, that inner product will tell us something about the angle between vector b and vector a. So it's possible to try and compute going forward from that.
Nếu có góc theta ở đây, tích vô hướng đó cho ta biết về góc giữa vectơ b và vectơ a. Nên ta có thể thử tính tiếp từ đó.
But there is actually an even simpler way. And part of this comes from the fact that what is the case where the inner product becomes zero?
Nhưng thật ra còn một cách đơn giản hơn. Một phần xuất phát từ việc khi nào tích vô hướng bằng không?
STUDENT
When they're perpendicular.
Khi chúng vuông góc.
GIREEJA RANADE
When things are perpendicular. And zeros are so much easier to deal with than any other numbers.
Khi chúng vuông góc. Và số không dễ xử lý hơn nhiều so với các số khác.
So can we write an equation that concerns angles in these vectors but equates to zero? So I know that this vector — this is vector a over here.
Vậy ta có thể viết một phương trình về góc giữa các vectơ mà bằng không không? Ta biết vectơ này — đây là vectơ a.
What is the angle between this vector a and this vector y?
Góc giữa vectơ a này và vectơ y này là bao nhiêu?
STUDENT
90 degrees.
90 độ.
GIREEJA RANADE
90 degrees. So if I take the inner product between this vector a, building on the idea that was just suggested, between this vector a and this vector y, what do I want to get?
90 độ. Nếu lấy tích vô hướng giữa vectơ a này, dựa trên ý vừa được đề xuất, giữa a và y này, ta muốn được gì?
STUDENT
Zero.
Bằng không.
GIREEJA RANADE
Zero. So if I write a inner product y, this is equal to 0. But this is just a inner product of b minus z equal to 0.
Bằng không. Vậy viết tích vô hướng của a và y, bằng 0. Tức là tích vô hướng của a với b trừ z bằng 0.
I can further write this as now a transpose b minus z equal to 0. But what is z? z is just alpha times a. What do we want to find out?
Ta viết tiếp thành a chuyển vị nhân b trừ z bằng 0. Nhưng z là gì? z chính là alpha nhân a. Ta muốn tìm gì?
Alpha, right. So let's substitute that in. So now I have a transpose b minus a transpose times alpha times a equal to 0.
Alpha, đúng rồi. Vậy thế vào. Giờ ta có a chuyển vị nhân b trừ a chuyển vị nhân alpha nhân a bằng 0.
So I know a. I know a. I know a transpose. I know a.
Ta biết a. Ta biết a. Ta biết a chuyển vị. Ta biết a.
So the only unknown here is now alpha.
Nên ẩn duy nhất ở đây là alpha.
So I can write basically this gives me — I can write this as the inner product of a and b minus alpha times the norm squared of a.
Vậy ta có thể viết điều này — viết thành tích vô hướng của a và b trừ alpha nhân bình phương chuẩn của a.
Go to 0.
Bằng 0.
Therefore, alpha is equal to inner product of ab divided by the norm squared of a.
Do đó alpha bằng tích vô hướng của a và b chia cho bình phương chuẩn của a.
Here's the formula. Here's the least squares algorithm.
Đây là công thức. Đây là thuật toán bình phương tối thiểu.
This answers the question that was just asked, which is, well, how do you compute this value of alpha?
Nó trả lời câu hỏi vừa nêu, tức là làm sao tính giá trị alpha này?
And what we did was we used the fact that we had just learned something about inner products that tells us, that connects basically geometry to algebra.
Ta đã dùng điều vừa học về tích vô hướng, thứ nối hình học với đại số.
It used the geometry that says that, okay, these must be orthogonal, these must be perpendicular, to then allow us to actually compute the value of that vector.
Ta dùng tính chất hình học rằng chúng phải trực giao, phải vuông góc, để từ đó tính được giá trị của vectơ đó.
In discussion, you're going to see actually two alternate ways of proving exactly this, this idea about projections, or this least squares algorithm, in the simple two-dimensional case.
Trong buổi thảo luận, các em sẽ thấy hai cách khác để chứng minh chính xác ý tưởng về phép chiếu này, hay thuật toán bình phương tối thiểu này, trong trường hợp hai chiều đơn giản.
We've done one way of proving it. We've done one derivation.
Ta đã chứng minh theo một cách. Ta đã có một cách suy ra.
You're going to see two different ways, because it's just such a fundamental idea that we want to make sure that you see as many different ways of thinking about it as you possibly can.
Các em sẽ thấy thêm hai cách khác, vì đây là một ý tưởng rất nền tảng nên thầy muốn bảo đảm các em thấy càng nhiều cách suy nghĩ về nó càng tốt.
So let's think about this a little bit. Let's play with this a little bit more.
Vậy ta hãy suy nghĩ về điều này một chút. Ta thử thêm một chút nữa.
What if I told you that I want you to project a — or let's say project b onto a.
Nếu tôi bảo các em chiếu a — hay giả sử chiếu b lên a.
And b is already at 90 degrees.
Và b đã vuông góc 90 độ.
You have the following situation. This is your a. This is your b. And you want to project b onto a.
Ta có tình huống sau. Đây là a. Đây là b. Và ta muốn chiếu b lên a.
What is the projection of b onto a?
Hình chiếu của b lên a là gì?
STUDENT
Zero.
Bằng không.
GIREEJA RANADE
Zero, right, because this inner product is going to give you exactly a zero.
Bằng không, đúng, vì tích vô hướng này sẽ cho đúng bằng không.
What if instead the b vector was like this, if this was the b vector, it was aligned with a, but in the different in the opposite direction?
Còn nếu vectơ b nằm như thế này, cùng phương với a, nhưng ngược hướng thì sao?
What would you get? You would get basically — what if b was equal to minus a? You would get alpha equal to a minus a over norm a squared.
Các em sẽ được gì? Nếu b bằng -a thì sao? Ta được alpha bằng a trừ a trên chuẩn của a bình phương.
But this just would be minus norm a squared over nor a squared, which is equal to minus 1.
Nhưng đây chính là trừ chuẩn a bình phương trên chuẩn a bình phương, bằng -1.
What if b was equal to a?
Nếu b bằng a thì sao?
Project something along itself, well, you just get the vector.
Chiếu một thứ lên chính nó thì ta được chính vectơ đó.
So intuitively, you can see that these cases where we intuitively know the answer, things match up perfectly.
Vậy bằng trực giác, các em thấy ở những trường hợp ta biết trước đáp án, mọi thứ khớp hoàn hảo.
Now, we can really come and build to basically, not just this 2D case, but build out to the general case.
Giờ ta có thể xây dựng tiếp không chỉ cho trường hợp 2D này, mà cho trường hợp tổng quát.
What happens when a is not just a column vector, but the columns of a actually have a column space that is, you know, arbitrary?
Điều gì xảy ra khi a không chỉ là một vectơ cột, mà các cột của a tạo nên một không gian cột bất kỳ?
That's really the general case that we want to start thinking about. Always we've done in that case, we've said, well, let's take the inverse of a.
Đó mới là trường hợp tổng quát ta muốn bắt đầu nghĩ tới. Trước giờ trong trường hợp đó, ta đều nói: hãy lấy nghịch đảo của a.
But we've always assumed that b belongs to the column space of a. The question is, well, what if we can't do this. What if that solution doesn't work?
Nhưng ta luôn giả sử b thuộc không gian cột của a. Câu hỏi là, nếu ta không làm được vậy thì sao? Nếu nghiệm đó không dùng được thì sao?
So now moving beyond 2D, projections generalize.
Vậy vượt ra ngoài 2D, phép chiếu được tổng quát hóa.
So before we really just build this out, I want to explore now orthogonality in the context of not just two-dimensional systems, but more general cases — so orthogonality beyond 2D.
Trước khi xây dựng tiếp, thầy muốn xét tính trực giao trong bối cảnh không chỉ các hệ hai chiều, mà cả các trường hợp tổng quát hơn — tức là tính trực giao ngoài 2D.
As we can see, these 90 degree angles and these projections are playing really important roles in finding these best fit — or these best solutions, even in the presence of noise.
Như ta thấy, các góc 90 độ và các phép chiếu này đóng vai trò rất quan trọng trong việc tìm nghiệm khớp nhất — hay nghiệm tốt nhất, ngay cả khi có nhiễu.
So for this, I want to propose the following theorem that I want to think about. We're going to do this, and then we're going to connect back to the more general case.
Vì vậy thầy muốn đề xuất định lý sau để các em suy nghĩ. Ta sẽ làm điều này, rồi sau đó nối lại với trường hợp tổng quát hơn.
So now consider a matrix A. And let y belong to the column space of a.
Xét một ma trận A. Và cho y thuộc không gian cột của A.
Let A be a1, a2, a n. So these are the columns of a, a1 a2, a n.
Cho A là a1, a2, a n. Đây là các cột của A, a1, a2, a n.
Let z be a vector such that z is orthogonal to a1, z is orthogonal to a2, and z is orthogonal to a n.
Cho z là một vectơ sao cho z trực giao với a1, z trực giao với a2, và z trực giao với a n.
So I have the columns of A. And I have a vector that is orthogonal to every single one of those columns.
Vậy ta có các cột của A. Và ta có một vectơ trực giao với từng cột trong số đó.
Then what is the relationship between z and y?
Vậy quan hệ giữa z và y là gì?
If z is orthogonal to every single one of the columns of A, what happens to z and y. Let's draw a picture.
Nếu z trực giao với từng cột của A, thì z và y thế nào? Ta vẽ hình.
Again, I'm drawing a plane because that's the only thing I can draw. But let's say this plane represented the column space of A.
Một lần nữa, thầy vẽ một mặt phẳng vì đó là thứ duy nhất thầy vẽ được. Giả sử mặt phẳng này biểu diễn không gian cột của A.
Or actually, let's say the table represented the column space of A. And I have all these vectors that are lying in this column space. And I have this vector z.
Hay đúng hơn, giả sử mặt bàn biểu diễn không gian cột của A. Và có tất cả các vectơ này nằm trong không gian cột đó. Và ta có vectơ z này.
It's pointing like this. And it's orthogonal to this vector in the column spaces. It's orthogonal to this vector in the column space.
Nó chỉ lên như thế này. Và nó trực giao với vectơ này trong không gian cột. Nó trực giao với vectơ này trong không gian cột.
It's orthogonal to all of these vectors that make up the columns of A.
Nó trực giao với tất cả các vectơ tạo nên các cột của A.
If it's orthogonal to all of the columns, it must be actually orthogonal to every single vector in the column space, because this vector is always going to make a 90-degree angle with any vector in the plane.
Nếu nó trực giao với tất cả các cột, thì nó phải trực giao với mọi vectơ trong không gian cột, vì vectơ này luôn tạo góc 90 độ với bất kỳ vectơ nào trong mặt phẳng.
That's what we want to proof. So we want to say, then we have that the inner product between z and y is also 0.
Đó là điều ta muốn chứng minh. Tức là ta muốn nói rằng tích vô hướng giữa z và y cũng bằng 0.
So z must be orthogonal to any y in the column space if z is orthogonal to all the columns of A.
Vậy z phải trực giao với mọi y trong không gian cột nếu z trực giao với tất cả các cột của A.
Does everyone understand what we're trying to show? Why do we want to show this?
Mọi người hiểu ta đang muốn chứng minh gì chưa? Tại sao ta muốn chứng minh điều này?
We want to show this, because then it allows us to focus just on the columns of A when we want to say something more generally about the column space.
Ta muốn chứng minh vì khi đó ta chỉ cần tập trung vào các cột của A khi muốn nói điều gì đó tổng quát hơn về không gian cột.
Okay? So how can we go about doing this. So how do we prove this theorem?
Được chứ? Vậy ta làm điều này bằng cách nào? Vậy ta chứng minh định lý này thế nào?
Why don't you take a minute to think about it on your own.
Các em hãy dành một phút tự suy nghĩ.
In the meanwhile, are there any questions?
Trong lúc đó, có câu hỏi nào không?
Yes.
Mời em.
STUDENT
So which is the information in the theorem that [INAUDIBLE] GIREEJA RANADE: Great question. We're given that y belongs to the column space of A. We're given that A is made of these columns.
Vậy thông tin nào trong định lý là [KHÔNG NGHE RÕ] GIREEJA RANADE: Câu hỏi hay. Ta được cho y thuộc không gian cột của A. Ta được cho A gồm các cột này.
We're given that z is a vector such that it is orthogonal to each of the columns.
Ta được cho z là một vectơ sao cho nó trực giao với từng cột.
And we're trying to prove what comes after that then, which is that z times y is equal 0 — or inner product of z and y is 0.
Và ta cần chứng minh điều theo sau đó, tức là z nhân y bằng 0 — hay tích vô hướng của z và y bằng 0.
Okay, so how do we go about proving this? Any suggestions?
Vậy ta chứng minh điều này như thế nào? Em nào có gợi ý không?
Someone who hasn't spoken yet. Yes.
Một bạn chưa phát biểu nhé. Mời em.
STUDENT
Well, we know that y must a linear combination of columns [INAUDIBLE] GIREEJA RANADE: Great suggestion. We know that y belongs to the column space of A.
Dạ, ta biết y phải là một tổ hợp tuyến tính của các cột [KHÔNG NGHE RÕ] GIREEJA RANADE: Gợi ý rất hay. Ta biết y thuộc không gian cột của A.
So y is a linear combination of a1 all the way up to a n.
Vậy y là tổ hợp tuyến tính của a1 cho đến a n.
So I can write y as, let's say, some c1 times a1 plus c2 times a2 plus cn times a n. Right?
Nên ta viết y bằng, giả sử, c1 nhân a1 cộng c2 nhân a2 cộng cn nhân a n. Đúng không?
Okay, I know that y belongs to the column space.
Ta biết y thuộc không gian cột.
Now, what do I want to do? I want to explore this quantity, this inner product of z and y.
Giờ ta muốn làm gì? Ta muốn khảo sát đại lượng này, tích vô hướng của z và y.
I can write this as the inner product of z. And I can just substitute what I know about y, c1, a1 plus cn and a n.
Ta viết nó là tích vô hướng của z với y, và thay y bằng c1, a1 cộng cho đến cn, a n.
But what do I know about inner products? Inner products are linear. So I can separate this out.
Ta biết gì về tích vô hướng? Tích vô hướng có tính tuyến tính. Nên ta tách ra được.
So I can think about this as z inner product with the first term, z inner product of the second term, z inner product with the last term.
Tức là z nhân vô hướng với số hạng đầu, z nhân vô hướng với số hạng thứ hai, rồi z nhân vô hướng với số hạng cuối.
So this is z c1, a1 plus z inner product c2, a2 plus z inner product cn, a n.
Vậy là z với c1, a1 cộng z nhân vô hướng c2, a2 cộng z nhân vô hướng cn, a n.
Does the constant matter here?
Hằng số có quan trọng ở đây không?
This is basically just as constant comes out is z inner product a1 plus z inner product a n, cn.
Hằng số được đưa ra ngoài, ta có z nhân vô hướng a1 cộng z nhân vô hướng a n, nhân cn.
There's no c.
Không còn c nữa.
But what are each of these terms? Zero, right? QED.
Vậy mỗi số hạng này bằng bao nhiêu? Bằng không, đúng không? Chứng minh xong.
[APPLAUSE] It was that easy.
[VỖ TAY] Dễ vậy đó.
But I didn't do it. I just followed the suggestion that came from you folks. So good job.
Nhưng không phải tôi làm. Tôi chỉ làm theo gợi ý của các em. Làm tốt lắm.
So what have we shown here? We have shown therefore that if this z is perpendicular to the columns of A, that it must be perpendicular to all of the vectors in the column space.
Vậy ta đã chứng minh được gì? Ta đã chứng minh rằng nếu z này vuông góc với các cột của A, thì nó phải vuông góc với mọi vectơ trong không gian cột.
Everyone with me here? Any questions about this? Because this is important. Like this will build.
Mọi người theo kịp chứ? Có câu hỏi nào không? Vì điều này quan trọng. Phần sau sẽ dựa vào đây.
Okay, good. So now, let's go back to our least squares problem.
Tốt. Giờ quay lại bài toán bình phương tối thiểu.
I have now Ax is kind of like b.
Ta có Ax xấp xỉ b.
These squiggly equal tos means approximately equal to. And let's say A is now an m by n matrix.
Dấu lượn sóng này nghĩa là xấp xỉ bằng. Và giả sử A là ma trận m nhân n.
There's m equations and n unknowns. And there are more equations than there are unknowns.
Có m phương trình và n ẩn. Số phương trình nhiều hơn số ẩn.
Furthermore, we know that these are noisy equations. We know that when we're taking measurements in our imaging lab that maybe some external light crept in.
Hơn nữa, các phương trình này có nhiễu. Khi đo đạc trong lab chụp ảnh, có thể có ánh sáng bên ngoài lọt vào.
We know that when our satellite is transmitting, maybe there was a slight issue with the transmission or there was some interference that made us miscalculate the propagation delays.
Khi vệ tinh truyền tín hiệu, có thể truyền bị trục trặc nhẹ hoặc có nhiễu khiến ta tính sai độ trễ lan truyền.
Something happened. There's some little bit of noise somewhere. So these equations aren't perfect.
Có điều gì đó xảy ra. Đâu đó có một chút nhiễu. Nên các phương trình không hoàn hảo.
What is our goal?
Mục tiêu của ta là gì?
Our goal is to find x such that Ax is close to b, which in particular if we think of this as an error vector, we can think about we want to minimize
Tìm x sao cho Ax gần b. Cụ thể, nếu coi đây là vectơ sai số, ta muốn cực tiểu hóa
the length of an error vector, where we define this error vector as Ax minus b.
độ dài của vectơ sai số, với vectơ sai số được định nghĩa là Ax trừ b.
In our 2D case, this PQ was our error vector.
Trong trường hợp 2D, PQ là vectơ sai số.
z was basically our Ax. This was b. So the length of PQ was the length of our error vector. Everyone see that?
z chính là Ax của ta. Đây là b. Vậy độ dài PQ là độ dài vectơ sai số. Mọi người thấy chưa?
This is important. Everyone see how this PQ is the same thing here? Okay, good.
Điều này quan trọng. Mọi người thấy PQ ở đây chính là cái này chứ? Tốt.
And let's think of A again as these columns, a1 all the way up to an.
Và lại coi A gồm các cột a1 cho đến an.
Now I'll go back to my picture here.
Giờ tôi quay lại hình này.
Everyone see this picture? So now, let this plane represent the column space of A. And let this b the vector that we're trying to match.
Mọi người thấy hình chứ? Giả sử mặt phẳng này là không gian cột của A. Và b là vectơ ta cần khớp.
What do we now want — if we want to find a point in this plane that is closest to b, which point do I want to find?
Ta muốn làm gì? Nếu muốn tìm điểm trong mặt phẳng này gần b nhất, ta cần tìm điểm nào?
What do we want to do? We did it in the two-dimensional case. What do you want to do here? I have a plane.
Ta làm gì? Ta đã làm trong trường hợp hai chiều. Ở đây làm gì? Có một mặt phẳng.
I have a vector.
Có một vectơ.
STUDENT
You want to find the projection.
Tìm hình chiếu ạ.
GIREEJA RANADE
You want to find the projection. You want to find basically where does the perpendicular from b hit my plane?
Đúng, tìm hình chiếu. Tức là đường vuông góc từ b chạm mặt phẳng ở đâu.
We can make sense of this in 2D. We can make sense of this in 3D. In 4D, we cannot visualize it. But how can we write it algebraically?
Ta hình dung được trong 2D. Hình dung được trong 3D. Trong 4D thì không thể hình dung. Nhưng viết bằng đại số thì sao?
What does it mean for something to be perpendicular to an entire subspace or vector space or column space? Well, we just proved a theorem about this.
Vuông góc với cả một không gian con, không gian vectơ hay không gian cột nghĩa là gì? Ta vừa chứng minh một định lý về điều này. Ta vừa chứng minh một định lý về điều này.
So we basically want to find the orthogonal projection of b onto the column space of A.
Vậy ta muốn tìm hình chiếu trực giao của b lên không gian cột của A.
So I want to now find that z in the column space.
Tức là tìm z trong không gian cột.
This is the column space of A. So this is z.
Đây là không gian cột của A. Đây là z.
This is b minus z. I want to find that z, such that b minus z is orthogonal to the column space.
Đây là b trừ z. Tìm z sao cho b trừ z trực giao với không gian cột.
So I want b minus z. Let us call this z.
Tức là ta muốn b trừ z. Ta gọi nó là z.
I want b minus z times this inner product with a1 to be equal to 0.
Ta muốn tích vô hướng của b trừ z với a1 bằng 0.
I also want b minus z inner product with a2 to be equal to 0.
Ta cũng muốn tích vô hướng của b trừ z với a2 bằng 0.
And I want b minus z inner product with a n to be equal to 0.
Và tích vô hướng của b trừ z với a n bằng 0.
Because what we just said was that in order to be orthogonal to an entire column space, I want to make sure that my vector of interest is orthogonal to every single one of the columns.
Vì điều ta vừa nói là để trực giao với cả không gian cột, ta cần đảm bảo vectơ đang xét trực giao với từng cột một.
Is everyone following me here? Any questions? Yes.
Mọi người theo kịp chưa? Có câu hỏi nào không? Mời em.
STUDENT
Why does [INAUDIBLE] GIREEJA RANADE: So I'm just saying that this A times x — last time we were thinking about, remember, z was alpha times A. So now we're going to say A times x is equal to some z.
Tại sao [KHÔNG NGHE RÕ] GIREEJA RANADE: Ý cô là A nhân x này — lần trước ta đã xét, nhớ không, z là alpha nhân A. Giờ ta nói A nhân x bằng một z nào đó.
So z — This is Ax equal to z. I want to find x. So x in this multi-dimensional case is the same as the alpha in the two-dimensional case.
Vậy z — đây là Ax bằng z. Cần tìm x. Vậy x trong trường hợp nhiều chiều này giống như alpha trong trường hợp hai chiều.
So the error now is basically the difference between z and b, which is the length of this vector. But that's given exactly by this. Yeah? Good question.
Sai số bây giờ chính là hiệu giữa z và b, tức là độ dài của vectơ này. Và nó được cho chính xác bởi biểu thức này. Được chưa? Câu hỏi hay.
Yes, question.
Em hỏi đi.
STUDENT
So does the order not matter? Like Ax minus b?
Vậy thứ tự không quan trọng ạ? Ví dụ Ax trừ b?
GIREEJA RANADE
Great question. Does it matter whether we write Ax minus b or bx minus A? It doesn't because all we care about is the length of that vector. The orientation of the vector would care.
Câu hỏi rất hay. Viết Ax trừ b hay b trừ Ax có khác nhau không? Không khác, vì ta chỉ quan tâm đến độ dài của vectơ đó. Hướng của vectơ thì mới bị ảnh hưởng.
But because we're only minimizing the magnitude, the order doesn't matter. Good question.
Nhưng vì ta chỉ cực tiểu hóa độ lớn, nên thứ tự không quan trọng. Câu hỏi hay.
Other questions? Okay.
Còn câu hỏi nào nữa không? Được rồi.
So we now know what it means to be orthogonal to the column space. And we just wrote out the conditions for that orthogonality to that column space.
Vậy ta đã biết trực giao với không gian cột nghĩa là gì. Và ta vừa viết ra các điều kiện để trực giao với không gian cột đó.
So I can now write these out a little bit more explicitly.
Giờ ta có thể viết rõ hơn một chút.
I can say a1 transpose times b minus z is equal to 0 all the way up to a n transpose times b minus z is equal to 0.
Ta có a1 chuyển vị nhân b trừ z bằng 0, cho đến a n chuyển vị nhân b trừ z bằng 0.
Right?
Đúng không?
What I want to do — so what are these a's? These are now a1 transpose, a2 transpose. These are row vectors, right?
Những a này là gì? Là a1 chuyển vị, a2 chuyển vị. Đây là các vectơ hàng, đúng không?
So I can write a transpose is equal to this row a1 transpose all the way up to a n transpose. This is just the transpose version of a.
Vậy A chuyển vị là hàng a1 chuyển vị cho đến a n chuyển vị. Đây chính là phiên bản chuyển vị của A.
All of the column vectors became row vectors. I want to take this and write it as a stacked set of equations.
Mọi vectơ cột đều thành vectơ hàng. Ta muốn viết chúng thành một hệ phương trình xếp chồng.
So I'm going to stack all of these and I'm going to write this as A transpose times b minus z is equal to 0.
Vậy ta xếp chồng tất cả chúng lại và viết thành A chuyển vị nhân b trừ z bằng 0.
This is a row vector times a column vector. This is a row vector times a column vector. So these equations are of this shape. This is a row vector times a column vector.
Đây là vectơ hàng nhân vectơ cột. Đây cũng là vectơ hàng nhân vectơ cột. Các phương trình có dạng như vậy. Đây là vectơ hàng nhân vectơ cột.
This is a row of vector times a column vector. But the column vectors are the same in every case.
Đây cũng là vectơ hàng nhân vectơ cột. Nhưng vectơ cột ở mọi trường hợp đều giống nhau.
So what I'm doing is under stacking up all of these rows to get me this A transpose here. Does everyone see that? Okay, good. I'm going to manipulate this further.
Vậy ta đang xếp chồng tất cả các hàng này để được A chuyển vị ở đây. Mọi người thấy chưa? Tốt. Ta biến đổi tiếp.
This is very similar to the calculation that we did in the 2D case. z is now Ax.
Việc này rất giống phép tính ta đã làm ở trường hợp 2D. z bây giờ là Ax.
This is equal to 0. I can build this out further. A transpose b minus A transpose times A times x is equal to 0.
Cái này bằng 0. Ta khai triển tiếp. A chuyển vị nhân b trừ A chuyển vị nhân A nhân x bằng 0.
What do I want to find? I want to now write this — I want to be able to write this in the way to figure out what my x is.
Ta muốn tìm gì? Giờ ta muốn viết cái này — ta muốn viết nó theo cách để tìm ra x.
So I can write now A transpose Ax is equal to A transpose b.
Vậy ta viết A chuyển vị nhân Ax bằng A chuyển vị nhân b.
Now, what is the dimensions of A transpose A? A, remember, is an m by n matrix. What are the dimensions of A transpose A?
Vậy kích thước của A chuyển vị nhân A là gì? Nhớ rằng A là ma trận m nhân n. Kích thước của A chuyển vị A là gì?
n by n, right. Is this a square matrix?
n nhân n, đúng rồi. Đây có phải ma trận vuông không?
Can I invert this? So I can write x as A transpose A inverse A transpose b.
Ta có thể nghịch đảo nó không? Vậy x bằng nghịch đảo của A chuyển vị A, nhân A chuyển vị, nhân b.
This is the general least squares algorithm.
Đây là thuật toán bình phương tối thiểu tổng quát.
This is also called a projection of b onto the column space of a.
Nó cũng gọi là phép chiếu của b lên không gian cột của A.
There's a question, of course, to be asked here. Is A transpose A always invertible? Are square matrices always invertible? No.
Tất nhiên ở đây có một câu hỏi cần đặt ra. A chuyển vị A có luôn khả nghịch không? Ma trận vuông có luôn khả nghịch không? Không.
So this is something we have to worry about. But we're not going to worry about it today. We're going to worry about it in the next lecture.
Vậy đây là điều ta phải lưu ý. Nhưng hôm nay ta chưa bàn đến. Ta sẽ bàn ở bài giảng sau.
But what I want you to see here is basically how what you did in the general case is exactly what you did in the two-dimensional case.
Điều cô muốn các em thấy ở đây là việc làm ở trường hợp tổng quát y hệt việc ta đã làm ở trường hợp hai chiều.
You have now derived the full least squares algorithm. You know how to deal with noise in the case of GPS systems. We'll pick up on Thursday.
Vậy là các em đã suy ra toàn bộ thuật toán bình phương tối thiểu. Các em biết cách xử lý nhiễu trong hệ thống GPS. Chúng ta sẽ tiếp tục vào thứ Năm.
[APPLAUSE]
[VỖ TAY]
Đă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.