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ả.
ALICE
Okay. Hi, everyone. Can you hear me? Okay, so welcome to, I guess, 16A review session for module 1 and module 3.
Được rồi. Xin chào mọi người. Mọi người nghe rõ không? Chào mừng các bạn đến buổi ôn tập EECS 16A cho module 1 và module 3.
My name is Alice. This is Sarika and Norman. And so we'll be helping to go over some questions today.
Mình tên là Alice. Đây là Sarika và Norman. Hôm nay bọn mình sẽ cùng làm một số câu hỏi.
We don't have review slides, so if you have any questions about how we kind of arrived at an answer or any conceptual questions, feel free to stop us at any point and ask questions.
Bọn mình không có slide ôn tập, nên nếu các bạn có thắc mắc về cách bọn mình ra đáp án hay câu hỏi về khái niệm nào, cứ ngắt lời và hỏi bất cứ lúc nào nhé.
So the first question that we're going to do is this question. It's called APS Lab by Hand. It's from a Spring '18 exam question number 8.
Câu đầu tiên mình sẽ làm là câu này. Tên là APS Lab by Hand. Đây là câu số 8 của đề thi mùa xuân 2018.
So if any of you wanted to bring up the question and follow along on your computers, you're welcome to as well. And this one covers a bit of correlation and also trilateration.
Bạn nào muốn thì có thể mở đề bài và theo dõi trên máy tính. Cứ tự nhiên nhé. Câu này có liên quan đến tương quan và định vị ba điểm (trilateration).
So I guess I'll give everyone a couple of minutes to take a look at the question and then think about how they might go about answering it. And then we can discuss together.
Mình sẽ cho mọi người vài phút đọc đề và nghĩ xem sẽ làm thế nào. có thể trả lời câu hỏi này như thế nào. Sau đó mình cùng thảo luận.
Oh, sorry.
À, xin lỗi.
Okay, let's talk over the question together. Oh, sorry. I'm having some technical difficulties. So this question says that we have a couple beacon signals.
Được rồi, cùng nói về câu hỏi nhé. À, xin lỗi. Mình đang gặp chút trục trặc kỹ thuật. Đề bài nói có một vài tín hiệu từ beacon.
And you can treat these as elements that are traveling at a velocity of 1 meter per second.
Các bạn có thể coi chúng là những phần tử di chuyển với vận tốc 1 mét trên giây.
And then your beacons are located some distance d away from the microphone. And this is in units of meters.
Các beacon nằm cách micro một khoảng d từ micrô. tính theo đơn vị mét.
So we're first going to consider the 1d case where we have two beacons, and then we're trying to detect the position of something along a line.
Trước hết xét trường hợp 1 chiều với hai beacon, và ta cần xác định vị trí của một vật trên một đường thẳng.
And so we have two different signals coming between each beacon. So first beacon, beacon A, is transmitting this signal here. And then beacon B is transmitting this signal here.
Có hai tín hiệu khác nhau đến từ mỗi beacon. Beacon đầu tiên, beacon A, phát tín hiệu này. Còn beacon B phát tín hiệu này.
And so the whole system looks something like this here. So the first part is, let's suppose that we have a microphone located at x equals 0. So we put our microphone right here.
Cả hệ thống trông như thế này. Phần đầu: giả sử micro đặt tại x bằng 0. Ta đặt micro ngay đây.
What is the signal that the microphone is going to receive from the two beacons? So does anyone have any suggestions on how we might go about approaching this?
Tín hiệu micro nhận được từ hai beacon là gì? Có bạn nào có gợi ý về cách tiếp cận không?
Okay, so let's first think about what will happen from the signal going from A as it transmits to the microphone located at xm.
Được rồi, trước hết xét điều gì xảy ra với tín hiệu đi từ A đến micro đặt tại xm.
So we know that the signal is moving at 1 meter per second, right? So let's say that signal A first transmits a 1 from beacon A.
Ta biết tín hiệu đi với tốc độ 1 mét trên giây, đúng không? đúng không? Giả sử tín hiệu A đầu tiên phát ra một số 1 từ beacon A.
And then that 1 is going to be transmitting at a speed of 1 meter per second to xm.
Số 1 đó sẽ truyền đi với tốc độ 1 mét trên giây tới xm.
So how many seconds is it going to take until it reaches xm, which is a distance of 10 meters away? 10 seconds, right?
Vậy mất bao nhiêu giây để nó tới xm, cách đó 10 mét? 10 giây, đúng không?
Okay, so the first signal in A is going to take 10 seconds to get to the microphone. Now what about B? What's going to happen here?
Vậy tín hiệu đầu tiên của A mất 10 giây để tới micro. Còn B thì sao? Chuyện gì xảy ra ở đây?
How long will it take for the first signal of B to transmit to the microphone?
Tín hiệu đầu tiên của B mất bao lâu để tới micro?
Also 10 seconds, right? So that means that between the delay from the beacon to the microphone for A and B are the same. Each of them has the same delay.
Cũng 10 giây, đúng không? Nghĩa là độ trễ từ beacon tới micro của A và B là như nhau. Cả hai có cùng độ trễ.
So then microphone is going to start receiving signal A and B at the same time. And then when it receives those signals, the signals get added to each other, right?
Nên micro sẽ bắt đầu nhận tín hiệu A và B cùng lúc. Và khi nhận được các tín hiệu đó, chúng được cộng với nhau, đúng không?
So in this case, our raw signal is just going to be the sum of A and B with some 10 second delay.
Trong trường hợp này, tín hiệu thô chính là tổng của A và B với độ trễ 10 giây.
So if we add those two signals together, then we'll just get 1 plus 1, which equals 2, 0, the 1 from A, 1 from B, and then some more 0's.
Nếu cộng hai tín hiệu lại, ta được 1 cộng 1 bằng 2, rồi 0, số 1 từ A, số 1 từ B, rồi thêm các số 0.
Sounds good? Okay, so now let's try to move on to the next question.
Ổn chứ? Được rồi, giờ qua câu tiếp theo.
So now let's say that we received different raw signals. So before we had this raw signal, assuming that the position was in the middle. But now we have something different, right?
Giờ giả sử ta nhận được các tín hiệu thô khác. Lúc trước ta có tín hiệu thô này, giả sử vị trí nằm ở giữa. Nhưng bây giờ khác rồi, đúng không?
So if you take a look at the 1's over here, they're at a different location from before. And so the question here is, what is the smallest time delay between when the signals arrive?
Nếu nhìn các số 1 ở đây, chúng ở vị trí khác so với trước. Câu hỏi ở đây là: độ trễ nhỏ nhất giữa lúc các tín hiệu đến là bao nhiêu?
And so I guess the question is, we want to figure out what the difference between when signal A is arriving versus when signal B is arriving.
Tức là ta muốn tìm hiệu giữa thời điểm tín hiệu A đến và thời điểm tín hiệu B đến.
So I'll let everyone think about it a bit again.
Mình lại để mọi người nghĩ một chút.
Yeah.
Vâng.
STUDENT
Do you have the first one?
Chị có cái đầu tiên không ạ?
ALICE
Oh yeah, sorry. Let me see if I can copy them down. So A is 1 0 1 0 0 0 0.
À vâng, xin lỗi. Để mình xem chép lại được không. A là 1 0 1 0 0 0 0.
And then B is 1 0 0 — okay.
Còn B là 1 0 0 — được rồi.
Okay, so taking a look at this question, since we're asked for the delay between when the signal's arriving, is there a technique that we've learned to figure out what the delay is of a signal?
Nhìn vào câu này, vì đề hỏi độ trễ giữa lúc các tín hiệu đến, ta đã học kỹ thuật nào để tìm độ trễ của một tín hiệu? mà ta đã học để tìm ra độ trễ của một tín hiệu?
Yeah. Yeah, we can do cross-correlation, right? So we can go ahead and try to cross correlate signals A and B with the raw signal and see where the peak of the correlation is.
Vâng. Đúng rồi, ta có thể dùng tương quan chéo. Ta tính tương quan chéo của tín hiệu A và B với tín hiệu thô rồi xem đỉnh của tương quan nằm ở đâu.
And that will give us an indication of what the delay is.
Điều đó cho ta biết độ trễ là bao nhiêu.
And so we remember the equation of cross correlation, which is the correlation onto some signal of, let's say, A or B in this case is equal to the sum of the product of the received signal
Hãy nhớ công thức tương quan chéo, tức là tương quan với một tín hiệu nào đó, chẳng hạn A hoặc B trong trường hợp này, bằng tổng của tích giữa tín hiệu nhận được
and then the shifted beacon signal for i equals negative infinity to infinity.
và tín hiệu beacon đã dịch, với i chạy từ âm vô cực đến vô cực.
And so one key thing to note about this question is that the signals are periodic, meaning that they're sort of repeating themselves in both positive infinity and negative infinity of time.
Một điểm quan trọng cần lưu ý ở câu này là các tín hiệu tuần hoàn, nghĩa là chúng tự lặp lại ở cả hướng thời gian dương vô cùng lẫn âm vô cùng.
So let's go ahead and try to take the cross correlation. So maybe we'll first try out a correlation between signal A and the raw signal.
Nào, ta thử tính tương quan chéo nhé. Trước tiên ta thử tính tương quan giữa tín hiệu A và tín hiệu thô.
So I'm going to use the table method to calculate the correlation. You may have also tried other methods.
Mình sẽ dùng phương pháp bảng để tính tương quan. Có thể các em đã thử cách khác.
So if we put the raw signal here — so we have 2 0 0 1 0 1 0. And then I'll first take with A with a shift of 0.
Nếu ta đặt tín hiệu thô ở đây — ta có 2 0 0 1 0 1 0. Rồi trước hết lấy A với độ dịch bằng 0.
And A is going to just be 1 0 1 0 0 0 0. Okay.
A chính là 1 0 1 0 0 0 0. Được rồi.
And so all you have to do is multiply all of the columns and then sum up all of the multiplied numbers. So I'll multiply 2 times 1 to get 2.
Việc cần làm là nhân từng cột với nhau rồi cộng tất cả các tích lại. Mình nhân 2 với 1 được 2.
And then this is 0 0 0 0 0 0. Okay. And then if we sum all these numbers together, then we get 2.
Còn lại là 0 0 0 0 0 0. Được rồi. Cộng tất cả các số này lại, ta được 2.
So this is going to be my correlation of Sa onto r at 0.
Vậy đây là tương quan của Sa lên r tại 0.
Everyone with me so far? Yeah? Okay. Yeah, basically we can repeat this for the next step.
Đến đây mọi người theo kịp chứ? Ừ? Được. Về cơ bản ta lặp lại cho bước tiếp theo.
So we can go ahead and shift Sa by 1.
Ta dịch Sa đi 1.
So 2 0 0 1 0 1 0. And then everything gets moved over by 1. And because this is a periodic signal, the last number becomes the first number in my shifted signal.
Tức là 2 0 0 1 0 1 0. Rồi mọi thứ dịch sang một vị trí. Và vì đây là tín hiệu tuần hoàn, số cuối cùng trở thành số đầu tiên trong tín hiệu đã dịch.
So I have 0 first, then 1 0 1 0 0 0. So we can go ahead and calculate this one. Everything is 0 except the 1 here.
Vậy ta có 0 trước, rồi 1 0 1 0 0 0. Giờ ta tính bước này. Mọi thứ đều bằng 0 trừ số 1 ở đây.
So if we sum up the 1 and all the 0's, we get 1. Okay. So that's the idea of correlation. I don't want to make everyone sit through the rest of the calculations.
Cộng số 1 với các số 0, ta được 1. Được rồi. Đó là ý tưởng của tương quan. Mình không muốn mọi người phải ngồi xem hết các phép tính còn lại.
I'll just write out the solution. So after kind of doing all of this, then we'll find that the correlation of Sa with r is 2 1 0 2 0 3 0.
Mình sẽ viết luôn kết quả. Sau khi làm hết như vậy, ta sẽ thấy tương quan của Sa với r là 2 1 0 2 0 3 0.
And then the correlation with Sb is going to be 3 0 1 2 1 1 0.
Còn tương quan với Sb là 3 0 1 2 1 1 0.
So now that we've found the correlations, how can we get the delay from this?
Giờ đã có các tương quan, làm sao suy ra độ trễ từ đây?
Yep.
Mời em.
STUDENT
[INDISCERNIBLE] ALICE: Right. So first we want to find the peak of where the correlation is. So we have one here and then we have one here.
[KHÔNG NGHE RÕ] ALICE: Đúng rồi. Trước hết ta tìm đỉnh của tương quan. Ta có một đỉnh ở đây và một đỉnh ở đây.
And then you're saying to subtract the two from each other. So in this case, Sa has from 0 a delay of 5. And then Sb has a delay of 0.
Rồi em nói là lấy hiệu của hai đỉnh. Ở đây, Sa tính từ 0 có độ trễ là 5. Còn Sb có độ trễ là 0.
And so first idea is like, okay, so maybe we can just take Sa minus Sb's delay and get a delay of 5.
Ý đầu tiên là, có lẽ ta lấy độ trễ của Sa trừ Sb và được độ trễ 5.
So the other thing we also want to think about is that maybe, since it's a periodic signal, this correlation is actually repeating.
Nhưng ta cũng cần nghĩ rằng vì là tín hiệu tuần hoàn, tương quan này thực ra cũng lặp lại.
So if I try to extend Sa into the negative direction, the correlation will continue — oops.
Nếu mở rộng Sa về phía âm, tương quan sẽ tiếp tục — ối.
0, 3, Going this way as well, right? This is also another peak.
0, 3, về phía này cũng vậy, đúng không? Đây cũng là một đỉnh khác.
And so in this case, the other thing you could observe is that the delay between A to B could be that Sa is actually two steps in front of Sb as well.
Vì vậy, điều khác ta có thể quan sát là độ trễ từ A đến B có thể là Sa đi trước Sb hai bước.
Both of these options are valid.
Cả hai khả năng đều hợp lệ.
And so since we're looking for the minimum time delay or the smallest one, in this case I would say it's actually that Sb is delayed two steps after Sa.
Và vì ta tìm độ trễ thời gian nhỏ nhất, tức là cái nhỏ nhất, trong trường hợp này mình sẽ nói rằng Sb trễ hai bước sau Sa.
So smallest time delay is two steps down Sa before Sb.
Vậy độ trễ nhỏ nhất là Sa đi trước Sb hai bước.
Any questions so far? Yep.
Đến đây có câu hỏi nào không? Mời em.
STUDENT
Can you share how you got to two steps?
Cô có thể giải thích sao ra hai bước không?
ALICE
How do I go out to two steps? Oh, okay. Yeah, that's a good question.
Làm sao ra hai bước à? À, được. Câu hỏi hay đấy.
So we know that for periodic correlation, the correlation signal is also going to be periodic.
Ta biết với tương quan tuần hoàn, tín hiệu tương quan cũng sẽ tuần hoàn.
So it will be a pattern and it will repeat itself with the same period as the signal. And so signal Sa has a period of seven numbers.
Nó là một mẫu và sẽ lặp lại với cùng chu kỳ như tín hiệu. Tín hiệu Sa có chu kỳ bảy số.
And it's going to keep on repeating itself.
Và nó sẽ cứ lặp lại mãi.
So that means that if we take a look at just the calculated correlation for one period, that will tell us the difference between Sa and Sb in one direction.
Nghĩa là nếu ta chỉ xét tương quan đã tính cho một chu kỳ, nó cho ta biết chênh lệch giữa Sa và Sb theo một hướng.
But actually, since it's periodic, the correlation will also extend into the negative case.
Nhưng vì tuần hoàn, tương quan cũng kéo dài sang phía âm.
And if you consider the repeated signal, then you can see that Sb actually has a delay of 2 after Sa.
Và nếu xét tín hiệu lặp lại, ta thấy Sb thực ra trễ 2 sau Sa.
Does that answer your question? Okay. Any other questions?
Vậy đã trả lời câu hỏi của em chưa? Được. Còn câu hỏi nào khác không?
Okay. So let's go ahead and try out the next part then.
Được rồi. Giờ ta thử làm phần tiếp theo.
So based on this answer of using the smallest time step of two steps, how can we figure out where the microphone is located?
Dựa trên đáp án dùng bước thời gian nhỏ nhất là hai bước, làm sao tìm ra vị trí của micro?
Yeah.
Mời em.
STUDENT
[INDISCERNIBLE] ALICE: So what would you say — so let's first think about it.
[KHÔNG NGHE RÕ] ALICE: Em sẽ nói sao — ta cùng nghĩ trước đã.
So let's go ahead and try and see what happens if we shift it two steps towards A. So then the delay from A to this location will be 8, right?
Ta thử xem điều gì xảy ra nếu dịch hai bước về phía A. Khi đó độ trễ từ A đến vị trí này sẽ là 8, đúng không?
STUDENT
So then B is also increased [INDISCERNIBLE] as well. [INDISCERNIBLE] ALICE: Yeah, exactly.
Vậy thì B cũng tăng [KHÔNG NGHE RÕ] luôn. [KHÔNG NGHE RÕ] ALICE: Đúng, chính xác.
So let me go ahead and erase this. So that's correct.
Để mình xóa cái này đi. Đúng rồi.
So if we go ahead and place the mic at negative 1, then you'll see that the delay from A to the mic is 9 and the delay from B to the mic is 11.
Nếu ta đặt micro ở âm 1, thì độ trễ từ A đến micro là 9 và độ trễ từ B đến micro là 11.
So then 11 minus 9 will give you 2. Okay, great. Okay.
Vậy 11 trừ 9 được 2. Tốt lắm. Okay.
So I think in the interest of time I'll skip part D for now, but I suggest to take a look at it on your own time.
Vì thời gian có hạn nên tôi tạm bỏ qua phần D, nhưng các bạn nên tự xem lại khi rảnh.
And let's go ahead and try out part E next. So it turns out that our 1D microphone setup is not so accurate. And we'd like to actually consider things in two dimensions.
Giờ ta thử làm phần E nhé. Hóa ra hệ micro 1D của ta không chính xác lắm. Nên ta muốn xét bài toán trong không gian hai chiều.
So now let's say that we have the same setup, so the same raw signal.
Giả sử ta có cùng thiết lập như trước, cùng tín hiệu thô.
But then we want to solve for all the different possible solutions in two dimensions. And so we have some hints here.
Nhưng giờ ta muốn tìm tất cả các nghiệm có thể trong hai chiều. Ở đây có một vài gợi ý.
So the delay is going to be the same. And then it should still give the same answer to us as when we solve the 1D case.
Độ trễ vẫn như cũ. Và kết quả vẫn phải trùng với khi ta giải trường hợp 1D.
But now we're just considering two dimensions. So I'd like everyone to maybe think about it for a few seconds, and then we'll try to discuss together again.
Chỉ là giờ ta xét hai chiều. Mời mọi người suy nghĩ vài giây, rồi ta sẽ cùng thảo luận.
Okay. Does anyone have any ideas of something that we've learned before that might be kind of helpful?
Okay. Có ai nghĩ ra điều gì ta đã học mà có thể giúp ích ở đây không?
No? Maybe I can draw a picture. So let's say that we have our beacon A and beacon B.
Không ai à? Có lẽ tôi vẽ hình nhé. Giả sử ta có beacon A và beacon B.
And so in the two-dimensional case, we're saying that — let's say we put the mic over here.
Trong trường hợp hai chiều, giả sử ta đặt micro ở đây.
And we want to try to figure out where the position of the mic is.
Ta muốn tìm vị trí của micro .
And then the mic will — using correlation, we can figure out what the distance is from the mic to each of the beacons.
Và micro sẽ... dùng tương quan, ta tìm được khoảng cách từ micro đến từng beacon.
And so that's this problem, where we'll know the distance of the mic from one of them, but it could be anywhere within a radius around each beacon.
Vậy là ta biết khoảng cách của micro tới từng beacon, nhưng micro có thể ở bất kỳ đâu trên đường tròn quanh mỗi beacon.
So this looks really similar to our trilateration problems, right? So we can think back to how we went about solving those.
Bài này trông rất giống bài định vị ba điểm (trilateration), đúng không? Ta nhớ lại cách đã giải những bài đó.
And we know that we can solve this just by setting up the equations for the circle around the beacon.
Ta biết có thể giải bằng cách viết phương trình đường tròn quanh beacon.
So in this case, if we were to consider the distance of the microphone from beacon A, we know that dA squared equals the x distance squared and then the y distance squared.
Ở đây, xét khoảng cách từ micro đến beacon A, ta có dA bình phương bằng bình phương khoảng cách theo x cộng bình phương khoảng cách theo y.
So that will just be x mic minus xA squared plus y mic minus yA squared.
Tức là (x mic trừ xA) bình phương cộng (y mic trừ yA) bình phương.
And then we can go ahead and do the same thing for B. So dB squared equals x minus xB squared plus y minus yB squared.
Rồi ta làm tương tự cho B. dB bình phương bằng (x trừ xB) bình phương cộng (y trừ yB) bình phương.
And so then since we want to find an expression for all the possible solutions, we'd like to try to simplify this equation a little bit.
Vì ta muốn tìm biểu thức cho tất cả các nghiệm có thể, ta muốn đơn giản hóa phương trình này một chút.
So one way that we can do this is that we can try to subtract or eliminate some of the equations. So I'll subtract the first equation from the second equation.
Một cách là trừ các phương trình cho nhau để khử bớt. Tôi lấy phương trình thứ hai trừ phương trình thứ nhất.
And then we'll get dA squared minus dB squared equals xm minus xA squared minus xm minus xB squared plus ym minus yA squared minus ym minus yB squared.
Ta được dA bình phương trừ dB bình phương bằng (xm trừ xA) bình phương trừ (xm trừ xB) bình phương cộng (ym trừ yA) bình phương trừ (ym trừ yB) bình phương.
Okay. And then we're given some parameters that we already know. So xA is going to be minus 10 and yA is 0. xB is 10 and yB is 0.
Okay. Đề đã cho một số tham số ta biết. xA bằng -10 và yA bằng 0. xB bằng 10 và yB bằng 0.
So we can go ahead and substitute these things in.
Ta thay những giá trị này vào.
Oh, and then the distance of the microphone from the beacons — we also know that the difference between the distances is going to be a delay of 2.
À, và về khoảng cách từ micro đến các beacon, ta cũng biết hiệu hai khoảng cách ứng với độ trễ là 2.
So let's go ahead and write this out. xA equals minus 10. yA equals 0.
Ta viết ra nhé. xA bằng -10. yA bằng 0.
xB equals 10 and yB equals 0. Then we know that dB equals dA plus 2 from earlier.
xB bằng 10 và yB bằng 0. Và từ trước, ta biết dB bằng dA cộng 2.
Okay, so substituting everything in now, we'll just get that dA squared minus dA plus 2 squared equals xm minus negative 10 squared minus xm minus xB, which
Okay, thay hết vào, ta được dA bình phương trừ (dA cộng 2) bình phương bằng (xm trừ (-10)) bình phương trừ (xm trừ xB), tức là
is 10 squared, plus ym minus yA squared minus ym minus yB, which is also 0 squared.
10, bình phương, cộng (ym trừ yA) bình phương trừ (ym trừ yB), cũng là 0, bình phương.
And so we'll notice a couple of things. So one is that the ym's will cancel each other out.
Ta để ý vài điều. Một là các số hạng ym sẽ triệt tiêu nhau.
And then.
Và rồi.
Last step is to basically just check and make sure that this still works for our previous situation.
Bước cuối là kiểm tra lại xem nó còn đúng với tình huống trước không.
So if we were to solve for what dA is, from the question before, we know that dA should equal 9. And then we position the microphone at location negative 1.
Nếu ta giải tìm dA, từ câu trước ta biết dA phải bằng 9. Và ta đặt micro tại vị trí -1.
So as a reminder, take a look at this question over here.
Xin nhắc lại, các bạn xem câu hỏi ở đằng kia.
So if we substitute xm equals minus 1, then we'll get — so it's dA squared minus dA squared plus 4dA plus 4 equals
Thay xm bằng -1, ta được... dA bình phương trừ dA bình phương cộng 4dA cộng 4 bằng xm.
xm.
Oh, sorry.
Ôi, xin lỗi.
So xm equals minus 1 plus 10 squared minus minus 1 minus 10 squared.
xm bằng -1, cộng 10, bình phương, trừ (-1 trừ 10) bình phương.
So these two numbers will cancel.
Hai số này sẽ triệt tiêu.
Then we'll get 4dA plus 4 equals 9 squared minus 121.
Rồi ta được 4dA cộng 4 bằng 9 bình phương trừ 121.
So in the end, I think this should work out that dA equals 9.
Cuối cùng, tôi nghĩ kết quả sẽ ra dA bằng 9.
So you can see that even though we're substituting everything into the trilateration equation, it still gives us the same solution as the 1D case.
Vậy dù ta thay mọi thứ vào phương trình định vị ba điểm, ta vẫn ra cùng nghiệm như trường hợp 1D.
Cool. Any questions about this part?
Hay quá. Phần này có câu hỏi nào không?
If not, then I'll pass the microphone to Sarika.
Nếu không, tôi sẽ chuyển micro cho Sarika.
Oh yeah, sure.
À vâng, mời bạn.
STUDENT
So where did the B equals dA come from?
Vậy B bằng dA từ đâu ra ạ?
ALICE
Oh, so in part B, we calculated the correlations of both of the signals.
À, ở phần B, ta đã tính tương quan của cả hai tín hiệu.
And then we found that the peak of the correlation for signal A was sort of like the delay of five time step. And then the peak signal B is delay of two time step.
Và thấy đỉnh tương quan của tín hiệu A ứng với độ trễ năm bước thời gian. Còn đỉnh của tín hiệu B là độ trễ hai bước thời gian.
So we mention that because the signals are periodic, that five time step delay could also mean that signal A is coming Two time steps before signal B.
Ta đã nói rằng vì các tín hiệu tuần hoàn, nên độ trễ năm bước đó cũng có thể nghĩa là tín hiệu A đến trước tín hiệu B hai bước.
And so then we decided the smallest time delay is two steps. All right. SARIKA: All right.
Nên ta chọn độ trễ nhỏ nhất là hai bước. Được rồi. SARIKA: Được rồi.
Can everyone hear me? Okay, great. So now we're going to be going through Spring '19, the final exam.
Mọi người nghe rõ tôi không? Okay, tốt. Bây giờ chúng ta sẽ làm đề thi cuối kỳ mùa xuân 2019.
And this will be question number 3, which is an application of least squares. So the idea here is we have a sensor.
Đây là câu số 3, một ứng dụng của bình phương tối thiểu. Ý tưởng là ta có một cảm biến, và nó cố gắng đo khoảng cách giữa cảm biến và một vật.
And it's trying to measure the distance between the sensor and an object. Okay.
Được rồi.
So take a few minutes to just look at the problem and familiarize yourself with it, and then we'll go through it together.
Các bạn dành vài phút đọc bài toán để làm quen với nó, rồi chúng ta sẽ cùng làm.
Does anyone need some more time? Raise your hand if you'd a minute or two more. Okay, great.
Có ai cần thêm thời gian không? Giơ tay nếu bạn cần thêm một, hai phút. Được rồi.
So in this problem, we have this sensor here that tries to detect this distance s of the position of the objects on this line.
Trong bài này, ta có cảm biến này dùng để đo khoảng cách s, là vị trí của các vật trên đường thẳng này.
And it outputs some voltage v, which is going to be some function of this distance s. So we're given this table here, which has basically a list of positions versus voltage measurements.
Nó xuất ra một điện áp v, là một hàm nào đó của khoảng cách s. Ta được cho bảng này, về cơ bản là danh sách vị trí và các giá trị điện áp đo được.
And so the idea is we want to figure out what exactly this function is between our sensor output and our voltage — or sorry, and our distance of the object.
Mục tiêu là tìm ra hàm đó chính xác là gì, giữa đầu ra của cảm biến là điện áp... à xin lỗi, và khoảng cách của vật.
So in part a here, we start by assuming that our position is approximated by scaled voltage.
Ở phần a, ta bắt đầu bằng giả sử vị trí xấp xỉ bằng điện áp nhân một hệ số.
So basically, our position s is equal to some constant k times v. But we don't know what this constant k is, so we're trying to figure out the k that minimizes our squared error s minus kv norm squared.
Tức là vị trí s bằng một hằng số k nhân v. Nhưng ta chưa biết k là bao nhiêu, nên ta tìm k làm cực tiểu sai số bình phương, chuẩn bình phương của s trừ kv.
So can someone tell me how we might start approaching this?
Ai cho mình biết ta có thể bắt đầu thế nào?
Any ideas? What have we learned that minimizes this function?
Bạn nào có ý kiến không? Ta đã học cách nào để cực tiểu hàm này?
Least squares, exactly.
Bình phương tối thiểu, đúng rồi.
So we can just go ahead and apply our least squares solution, assuming that our solution looks something like this, s is equal to k times v. So first of all recall that our least squares solution is x hat is equal to A transpose A inverse times A transpose times b for a system A times x is equal to b.
Vậy ta cứ áp dụng nghiệm bình phương tối thiểu, với giả sử nghiệm có dạng s bằng k nhân v. Trước hết nhớ lại nghiệm bình phương tối thiểu là x mũ bằng A chuyển vị nhân A, nghịch đảo, nhân A chuyển vị nhân b, cho hệ A nhân x bằng b.
So in this case, how does this translate to this problem? So what is our A matrix?
Vậy trong bài này nó tương ứng thế nào? Ma trận A của ta là gì?
Our A matrix is going to be our voltage measurements v. So that's going to be 4, 10, 15.
Ma trận A là các giá trị điện áp đo v. Tức là 4, 10, 15.
Our x here, this is going to be our unknown, which in this case is k — this scalar k.
x là ẩn số của ta, trong trường hợp này là k, một số vô hướng k.
And then b is going to be S, so our position — so the object's position — which is 1, 2, 3.
Còn b là S, tức vị trí của vật, là 1, 2, 3.
Okay, so this is our setup, so we can go ahead and just apply our least squares solution. So k hat is equal to A transpose A inverse.
Được rồi, đây là cách thiết lập, giờ ta cứ áp dụng nghiệm bình phương tối thiểu. k mũ bằng A chuyển vị nhân A, nghịch đảo.
So A transpose is 4, 10, 15 times regular 4, 10, 15.
A chuyển vị là 4, 10, 15 nhân với 4, 10, 15 ban đầu.
This whole thing inverse times A transpose, which is 4, 10, 15, times b, which is 1, 2, 3. And we can go ahead and solve.
Cả cụm này lấy nghịch đảo, nhân A chuyển vị, là 4, 10, 15, nhân b, là 1, 2, 3. Rồi ta tính.
Well, let's work out the math for this problem, since we don't actually have to for the rest of the parts.
Ta tính thử bài này, vì các phần sau ta không cần tính.
So this should end up being 1 over 16 plus 100 plus 225 times this product here, which is 4 plus 20 plus 45.
Kết quả là 1 trên 16 cộng 100 cộng 225, nhân tích này, là 4 cộng 20 cộng 45.
And that gives us our final answer, which is just 69/341. And that's what we've approximated for k.
Và ta ra đáp án cuối cùng là 69/341. Đó là giá trị xấp xỉ của k.
Are there any questions about this part? No? Okay. Sounds good.
Phần này có câu hỏi nào không? Không ạ? Được rồi. Tốt.
All right. So once you finish kind of looking at that, this time we measure the output voltage to be negative 3 at position s is equal to 0.
Nào. Sau khi xem xong phần đó, lần này ta đo được điện áp đầu ra là âm 3 tại vị trí s bằng 0.
So we think that there might be a bias in the sensor.
Nên ta nghĩ cảm biến có thể bị lệch (bias).
So it's not just going to be s is equal to k times v. Is going to be k times v plus some constant b, right?
Vậy s không chỉ bằng k nhân v, mà là k nhân v cộng một hằng số b, đúng không?
So it'll be an affine transformation instead of a linear one. So in this case, we want to set up our least squares solution using this new model, s is equal to kv plus b.
Tức là một phép biến đổi affine chứ không phải tuyến tính. Vậy ta muốn thiết lập bình phương tối thiểu với mô hình mới này, s bằng kv cộng b.
So take a minute or two to do that. Remember, you don't actually have to solve, but just get the setup.
Các bạn dành một, hai phút làm đi. Nhớ là không cần giải, chỉ cần thiết lập.
Okay, so for this part, what is our A matrix and our X matrix and everything? What is it going to look like? What are our unknowns in this problem?
Ở phần này, ma trận A và ma trận X và các thứ khác là gì? Chúng trông như thế nào? Ẩn số trong bài này là gì?
Anyone?
Ai trả lời được?
Yeah, so they're k and b. So our unknowns, our x vector is going to be k and b, because we're trying to fit this affine model to our measurements.
Đúng, là k và b. Vậy ẩn số, vectơ x của ta, là k và b, vì ta đang khớp mô hình affine này với các số đo.
So to set up this matrix, we know that k is going to be times x — or it's going to be times v in this case.
Để lập ma trận, ta biết k được nhân với x, à không, được nhân với v trong trường hợp này.
So v is going to be negative 3, 4, 10, 15. And this is all times k, b. What goes in this second column here?
Vậy v là âm 3, 4, 10, 15. Và tất cả nhân với k, b. Cột thứ hai này sẽ chứa gì?
STUDENT
[INDISCERNIBLE] SARIKA: Exactly. So it's going to be a column of 1's because we know that b is just multiplied by 1 in this model here.
[KHÔNG NGHE RÕ] SARIKA: Đúng vậy. Là một cột toàn số 1, vì ta biết b chỉ được nhân với 1 trong mô hình này.
And this whole thing is going to equal s, so our object's position, which is 0, 1, 2, 3 like that. Okay, so this is going to be our setup, Ax is equal to b.
Và tất cả bằng s, tức vị trí của vật, là 0, 1, 2, 3 như vậy. Được rồi, đây là cách thiết lập, Ax bằng b.
And like before, we're trying to minimize the squared error. So we can just apply the least squares formula.
Và như trước, ta muốn cực tiểu sai số bình phương. Nên ta cứ áp dụng công thức bình phương tối thiểu.
So to set this up, we have that x hat is equal to A transpose, which is negative 3, 4, 10, 15 and 1, 1, 1, 1 times A.
Ta có x mũ bằng A chuyển vị, là âm 3, 4, 10, 15 và 1, 1, 1, 1, nhân A.
That whole thing inverse times A transpose again. I'll just put this on the next line.
Cả cụm nghịch đảo, nhân A chuyển vị lần nữa. Mình viết xuống dòng tiếp theo.
So times A transpose times b, which is again 0, 1, 2, 3.
Nhân A chuyển vị nhân b, lại là 0, 1, 2, 3.
And this is how we get our approximates for k and b. Are there any questions about this part?
Và đó là cách ta có giá trị xấp xỉ của k và b. Phần này có câu hỏi nào không?
Okay. Great. So moving on to the next part, so here we have a different sensor and we take more data points. And these data points don't exactly follow our model from b very well.
Được rồi. Tốt. Chuyển sang phần tiếp theo, ở đây ta có một cảm biến khác và đo thêm nhiều điểm dữ liệu. Những điểm dữ liệu này không khớp hoàn toàn với mô hình của ta từ b một cách chính xác lắm.
So it's no longer going to be an affine transformation. So by inspection, we decide either a quadratic or a logarithmic fit is going to work, so something like this.
Nên nó sẽ không còn là một phép biến đổi affine nữa. Quan sát thì ta thấy một mô hình bậc hai hoặc mô hình logarit sẽ khớp, đại loại như thế này.
So we have these two models here rather than our previous linear and affine models.
Vậy ta có hai mô hình này thay cho các mô hình tuyến tính và affine trước đó.
So now we want to set up the least squares problems for these two models using the data in this table here so similar to before.
Bây giờ ta cần thiết lập bài toán bình phương tối thiểu cho hai mô hình này, dùng dữ liệu trong bảng này, tương tự như lúc trước.
Yeah, so take a few moments to try and work this out. Remember, don't actually solve, just set up the least squares formula.
Các bạn dành vài phút thử làm nhé. Nhớ là không cần giải, chỉ cần thiết lập công thức bình phương tối thiểu.
Does anyone want a few more minutes? So let's start going over the quadratic setup for a quadratic model. So in this case, we know our unknowns. So Ax is equal to b.
Có ai cần thêm vài phút không? Ta bắt đầu xem phần thiết lập cho mô hình bậc hai. Mô hình bậc hai. Ở đây ta biết các ẩn số. Vậy Ax bằng b.
Our unknowns are going to be a2, a1, and 0, right? Oh sorry, a0, because we're trying to find the best fit for those parameters.
Các ẩn số là a2, a1 và 0, đúng không? Xin lỗi, là a0, vì ta đang tìm giá trị khớp nhất cho các tham số đó.
Okay. And so what is our A matrix going to look like?
Được rồi. Vậy ma trận A sẽ trông như thế nào?
Any ideas? Yeah.
Bạn nào có ý kiến không? Mời bạn.
STUDENT
[INDISCERNIBLE] SARIKA: Exactly. So it's going to be a column of v squared. Because recall that our model looks like this. It's a2 times v squared plus a1 times v plus A0.
[KHÔNG NGHE RÕ] SARIKA: Chính xác. Đó sẽ là một cột các giá trị v bình phương. Vì nhớ rằng mô hình của ta có dạng này. Là a2 nhân v bình phương cộng a1 nhân v cộng a0.
So the first column is just going to be all our values v squared. So that's going to be 20 squared, 45 squared, 98 squared, and 214 squared.
Vậy cột đầu tiên là tất cả các giá trị v bình phương. Tức là 20 bình phương, 45 bình phương, 98 bình phương và 214 bình phương.
Our second column is going to be just a column of v's. So it's going to be 20, 45, 98, and 214.
Cột thứ hai chỉ là cột các giá trị v. Tức là 20, 45, 98 và 214.
And then our final one is just going to be a row of 1's, because we know that a0 is multiplied just by 1. Okay, so that's our A matrix.
Còn cột cuối cùng chỉ toàn số 1, vì ta biết a0 chỉ được nhân với 1. Đó là ma trận A của ta.
And then our b matrix is the same as before. So it's just going to be our s values, so 4, 5, 6, and 7. Okay.
Còn vectơ b thì giống như trước. Chỉ là các giá trị s của ta, tức 4, 5, 6 và 7. Được rồi.
And from here, we just plug in our A and our b into the formula. x hat equals A transpose A inverse A transpose b. Yeah. Any questions about that part?
Từ đây, ta chỉ cần thay A và b vào công thức. x mũ bằng nghịch đảo của A chuyển vị A, nhân A chuyển vị, nhân b. Vâng. Có câu hỏi nào về phần này không?
Okay, cool. So now for our logarithmic setup, recall our equation is s is equal to b1 times ln of v plus b0.
Tốt. Giờ đến phần thiết lập cho mô hình logarit, nhớ rằng phương trình là s bằng b1 nhân ln của v cộng b0.
So in this case, we know that our x vector is going to be b1, b0 because these are our unknowns. What is our A matrix going to look like?
Vậy ở đây vectơ x của ta là b1, b0 vì đây là các ẩn số. Ma trận A sẽ trông như thế nào?
The first column is just going to be all ln of v, right? So ln of each of the v's in the table.
Cột đầu tiên toàn là ln của v, đúng không? Tức là ln của từng giá trị v trong bảng.
So ln 20, ln 45, ln 98, and ln 214.
Vậy là ln 20, ln 45, ln 98 và ln 214.
And our second column is just going to be all 1's, because again, b0 is just multiplied by the constant 1. Okay. Great. And again, we want to apply this least squares formula here.
Còn cột thứ hai toàn số 1, vì b0 cũng chỉ được nhân với hằng số 1. Được rồi. Tốt. Và ta lại áp dụng công thức bình phương tối thiểu này.
Okay, are there any questions about any of these parts so far?
Có câu hỏi nào về các phần vừa rồi không?
Okay, great. So moving on to our last part, which is part d, we're given these errors, right?
Tốt. Chuyển sang phần cuối, là phần d, ta được cho các sai số này, đúng không?
So we're given this table of errors where e is equal to s approximate minus actual s, s measured, for the sets of data in that part.
Ta được cho bảng sai số trong đó e bằng s xấp xỉ trừ s thực tế, tức s đo được, cho các bộ dữ liệu trong phần đó.
So our question is in the context of least squares, which is the better fit? And justify your answer mathematically.
Câu hỏi là trong ngữ cảnh bình phương tối thiểu, mô hình nào khớp hơn? Và hãy chứng minh câu trả lời bằng toán học.
Just take a minute or two to think about that and then we'll talk about it together.
Các bạn nghĩ một hai phút rồi ta sẽ cùng thảo luận.
Would anyone some more time to think about this? Raise your hand. Okay, just a minute more then.
Có ai cần thêm thời gian suy nghĩ không? Giơ tay nhé. Được, vậy thêm một phút nữa.
So let's start talking about this part. So again, what we're trying to do is find which of these models is the better fit in the context of least squares.
Giờ ta bắt đầu bàn về phần này. Một lần nữa, ta cần tìm xem mô hình nào khớp hơn trong ngữ cảnh bình phương tối thiểu.
So my first question is, what is the cost function that we're trying to minimize in least squares?
Câu hỏi đầu tiên: hàm chi phí mà ta cần cực tiểu hóa trong bình phương tối thiểu là gì?
It's the norm of Ax hat minus b squared, right? Where Ax hat is our estimate and this b is our actual.
Đó là chuẩn của Ax mũ trừ b, bình phương, đúng không? Trong đó Ax mũ là ước lượng và b là giá trị thực.
So this is our actual measurement, whereas Ax hat is given the model that we're trying to look at, what is our estimated position for a given voltage?
Đây là số đo thực tế của ta, còn Ax mũ là, với mô hình mà ta đang xét, vị trí ước lượng ứng với một điện áp cho trước.
So using this formula, we can figure out which of the overall costs is going to be lower given the two different models.
Dùng công thức này, ta có thể xác định chi phí tổng thể nào thấp hơn giữa hai mô hình.
So our cost for the quadratic case — so we're already given here our errors.
Chi phí cho trường hợp bậc hai: ở đây ta đã có sẵn các sai số.
So we can just square them and add them together just by this cost function equation.
Nên ta chỉ cần bình phương rồi cộng lại theo phương trình hàm chi phí này.
So the cost for the quadratic is going to be 1 squared plus negative 1.5 squared plus 0.5 squared plus 0 squared. And that ends up being 3.5.
Vậy chi phí của mô hình bậc hai sẽ là 1 bình phương cộng âm 1,5 bình phương cộng 0,5 bình phương cộng 0 bình phương. Kết quả là 3,5.
And so the cost now for logarithmic, you do the exact same thing. We just square all of our errors and add them together.
Còn chi phí của mô hình logarit thì ta làm y hệt. Bình phương tất cả sai số rồi cộng lại.
And that gives us negative 0.9 squared plus 0 squared plus negative 1 squared plus 1.1 squared, which is 3.02.
Ta được âm 0,9 bình phương cộng 0 bình phương cộng âm 1 bình phương cộng 1,1 bình phương, bằng 3,02.
Okay, so given these two costs, which one is the better fit?
Với hai chi phí này, mô hình nào khớp hơn?
It's going to be the logarithmic, right? So logarithmic is better fit because the overall cost when we use our logarithmic model is lower.
Là mô hình logarit, đúng không? Logarit khớp hơn vì chi phí tổng thể khi dùng mô hình logarit thấp hơn.
And our goal in least squares is to minimize the cost as much as we can. Okay. Are there any questions about this problem or least squares in general?
Và mục tiêu của bình phương tối thiểu là cực tiểu hóa chi phí hết mức có thể. Được rồi. Có câu hỏi nào về bài này hoặc về bình phương tối thiểu nói chung không?
Yeah.
Mời bạn.
STUDENT
How do we [INDISCERNIBLE] SARIKA: Oh, yeah. So we don't actually use it, because we just use it in the setup for each of these problems.
Làm sao ta [KHÔNG NGHE RÕ] SARIKA: À, vâng. Thật ra ta không dùng nó, vì ta chỉ dùng nó trong phần thiết lập cho mỗi bài này.
Though theoretically, if you had actually solved these out, that would give you your estimates, which you can use to subtract the actual position in order to get these errors here.
Dù về mặt lý thuyết, nếu các em giải ra hết các bài này, thì sẽ có được các ước lượng, rồi đem trừ đi vị trí thực để tính ra các sai số ở đây.
Yeah. Any other questions? If there are no other questions, I'm going to pass the mic to Norman.
Vâng. Còn câu hỏi nào khác không? Nếu không còn câu hỏi nào, mình sẽ đưa micro cho Norman.
NORMAN
Hello? Can people hear me? All right, cool.
Xin chào? Mọi người nghe được không? Được rồi, tốt.
So the problem I'm going to be going over is this constraint least squares problem.
Bài mình sẽ làm là bài toán bình phương tối thiểu có ràng buộc.
So the basic idea is we're trying to find — we're trying to minimize — we're considering a matrix A of full column rank where M is greater than N. We're trying to determine a unit vector x that minimizes the norm of Ax.
Ý tưởng cơ bản là ta đang tìm — ta đang cực tiểu hóa — ta xét một ma trận A có hạng cột đầy đủ với M lớn hơn N. Ta cần tìm một vectơ đơn vị x làm cực tiểu chuẩn của Ax.
So it's equivalent. And in particular, we have this constraint where the norm of x is 1.
Tức là tương đương. Và cụ thể, ta có ràng buộc là chuẩn của x bằng 1.
So this argument kind of looks like a least squares kind of thing.
Bài này trông khá giống dạng bình phương tối thiểu quen thuộc.
So in least squares, we're trying to minimize x for Ax minus b.
Với bình phương tối thiểu, ta cực tiểu hóa theo x của Ax trừ b.
So in this case, B equals 0, right?
Ở đây b bằng 0, đúng không?
So x hat would be like if that's A transpose A inverse A transpose b, that would give us 0. But the x hat can't actually be 0, right?
Thì x hat sẽ là A transpose A nghịch đảo nhân A transpose b, và kết quả là 0. Nhưng x hat không thể bằng 0, đúng không?
Because we have a constraint where the norm of x is equal to 1. So in this problem, so we can't use the regular least squares approach.
Vì ta có ràng buộc chuẩn của x bằng 1. Nên ở bài này ta không dùng được cách bình phương tối thiểu thông thường.
So we have to do this modified constrained least squares optimization. And this problem helps guide us through it. So it's a bunch of inner product proofs that I think would be good practice.
Ta phải làm bài tối ưu bình phương tối thiểu có ràng buộc đã chỉnh sửa này. Và bài này hướng dẫn ta từng bước. Đó là một loạt chứng minh về tích vô hướng mà mình nghĩ là bài luyện tập tốt.
So in the first part, in the setup we have these eigenvalue eigenvector pairs for A transpose A. And we're assuming that all the eigenvalues are real and are indexed in ascending order.
Ở phần đầu, trong phần thiết lập ta có các cặp giá trị riêng và vectơ riêng của A transpose A. Và ta giả sử mọi giá trị riêng đều thực và được đánh chỉ số theo thứ tự tăng dần.
So the first part is just trying to show that the smallest eigenvalue is greater than 0. So let's spend a few minutes thinking about that.
Phần đầu chỉ là chứng minh giá trị riêng nhỏ nhất lớn hơn 0. Ta dành vài phút nghĩ về việc này.
Oh yeah, this is from spring 2017, if you want to follow along. Question 6. Yeah.
À, đây là đề mùa xuân 2017, nếu các em muốn theo dõi. Câu 6. Vâng.
STUDENT
What happens when that box [INDISCERNIBLE]?
Điều gì xảy ra khi cái ô đó [KHÔNG NGHE RÕ]?
NORMAN
Oh yeah. During this final exam, the professors decided to have this wave thing. So if you didn't know how to do it, you could just get 10% of the credit.
À vâng. Trong kỳ thi cuối kỳ này, các giáo sư quyết định có phần miễn này. Nếu không biết làm, các em vẫn nhận được 10% số điểm.
It depends on the professors each semester if they do it. So I can't say if it will happen this semester or not.
Mỗi học kỳ tùy các giáo sư có làm vậy hay không. Nên mình không nói được học kỳ này có hay không.
So do people have any thoughts, like how to start?
Mọi người có ý tưởng gì để bắt đầu không?
So the way I would start this problem is that we're interested in lambda 1, right? So we know that lambda 1 is an eigenvalue of A transpose A.
Cách mình bắt đầu bài này là ta quan tâm đến lambda 1, đúng không? Ta biết lambda 1 là một giá trị riêng của A transpose A.
So in particular, we have that A transpose A times some v1 equals lambda 1 v1, right?
Cụ thể, A transpose A nhân với v1 nào đó bằng lambda 1 nhân v1, đúng không?
So if I were taking this exam, what I would see, this A transpose A shows up here in particular.
Nếu mình đang thi, mình sẽ thấy A transpose A xuất hiện ở đây.
So that would motivate me to — let's consider the quantity Av1.
Điều đó gợi ý mình xét đại lượng Av1.
Because that will give us v1 transpose times A1 transpose A times v1. And then we have that v1 is an eigenvector of A transpose A.
Vì nó cho ta v1 transpose nhân A transpose A nhân v1. Mà v1 là vectơ riêng của A transpose A.
So that lets us substitute this expression.
Nên ta thay biểu thức này vào.
So we get v1 transpose times lambda 1 times v1, which gives us this.
Ta được v1 transpose nhân lambda 1 nhân v1, bằng cái này.
So that will give us lambda 1 times the norm of v1 squared. So we can solve for lambda 1 now.
Tức là lambda 1 nhân bình phương chuẩn của v1. Giờ ta có thể giải ra lambda 1.
So you get lambda 1 is the norm of Av1 divided by the norm of v1.
Lambda 1 bằng chuẩn của Av1 chia cho chuẩn của v1.
These should be squares.
Chỗ này phải là bình phương.
So how does this help us? So we have an expression for lambda 1. How does this help us show that lambda 1 is greater than 0? Yeah.
Vậy điều này giúp gì cho ta? Ta đã có biểu thức của lambda 1. Nó giúp chứng minh lambda 1 lớn hơn 0 như thế nào? Vâng.
STUDENT
[INDISCERNIBLE] NORMAN: Yeah.
[KHÔNG NGHE RÕ] NORMAN: Đúng.
So we have that these are norm squares. So these are at least positive semi-definite numbers. They're non-negative.
Đây là các bình phương của chuẩn. Nên chúng ít nhất là các số nửa xác định dương. Chúng không âm.
So at the very least, we can say that lambda 1 is greater than or equal to 0.
Vậy ít nhất ta nói được lambda 1 lớn hơn hoặc bằng 0.
So now we have to show why can't lambda 1 be 0. So if lambda 1 were equal to 0, that would mean that A times v1 would equal to 0, right?
Giờ ta phải chứng minh vì sao lambda 1 không thể bằng 0. Nếu lambda 1 bằng 0 thì A nhân v1 sẽ bằng 0, đúng không?
So obviously v1 is not equal to 0. So the only way this would be true is if v1 was in the null space of A, right?
Rõ ràng v1 không bằng 0. Vậy điều này chỉ đúng nếu v1 nằm trong null space của A, đúng không?
But if you go back to the beginning of the problem, it says that the matrix A is a full column rank. So there's no null space.
Nhưng nếu quay lại đầu bài, đề nói ma trận A có hạng cột đầy đủ. Nên không có null space.
So therefore, lambda 1 cannot be equal to 0 as well.
Do đó lambda 1 cũng không thể bằng 0.
So the way I would structure the proof is I would first show that lambda 1 is at least greater than or equal to 0.
Cách mình cấu trúc phép chứng minh là trước hết chứng minh lambda 1 ít nhất lớn hơn hoặc bằng 0.
And then you have to show the subcase why lambda 1 can't be equal to 0. Cool.
Rồi xét trường hợp con, vì sao lambda 1 không thể bằng 0. Tốt.
So the second part of the problem is we're considering these two eigenpairs corresponding to lambda k and l, which are distinct eigenvalues of A transpose A. So now we want to prove that the eigenvectors of different eigenvalues are orthogonal.
Phần hai của bài xét hai cặp riêng ứng với lambda k và l, là các giá trị riêng phân biệt của A transpose A. Giờ ta muốn chứng minh các vectơ riêng ứng với giá trị riêng khác nhau thì trực giao.
So they gave us a few hints. So I'll give you a few minutes to think about it.
Đề cho vài gợi ý. Mình cho các em vài phút để nghĩ.
How many people would some more time?
Ai cần thêm thời gian không?
All right. So let's follow the hint. So the first thing says premultiply the first equation by wl transpose.
Được rồi. Ta làm theo gợi ý. Điều đầu tiên nói là nhân trái phương trình thứ nhất với wl transpose.
So that will give us wl transpose A transpose A times vk. And then doing the same thing on the other side, we get this.
Ta sẽ được wl transpose A transpose A nhân vk. Rồi làm tương tự ở vế bên kia, ta được cái này.
And then the second one says first multiply the second equation by vk.
Sau đó ý thứ hai bảo trước hết nhân phương trình thứ hai với vk.
So we get vl transpose A transpose Avk equals lambda l vL transpose vk.
Vậy ta có vl transpose A transpose Avk bằng lambda l vL transpose vk.
So what we notice is that the left-hand sides of both of these equations are the same, right? So that means we can set the right-hand sides equal to each other.
Ta nhận thấy vế trái của cả hai phương trình này giống nhau, đúng không? Nghĩa là ta có thể cho hai vế phải bằng nhau.
Or another way you can do that is just we can subtract the two equations. So the left-hand side of the subtraction will give us 0.
Hoặc cách khác là ta trừ hai phương trình cho nhau. Vế trái của phép trừ sẽ cho ta 0.
And then we can get lambda k times vl transpose times vk minus lambda l vl transpose vk.
Còn lại lambda k nhân vl transpose nhân vk trừ lambda l vl transpose vk.
So that gives us lambda k minus lambda l times the inner product of vl and vk.
Tức là lambda k trừ lambda l nhân tích vô hướng của vl và vk.
So how does this help us show that the two eigenvectors are orthogonal? Yeah.
Vậy điều này giúp ta chứng minh hai vectơ riêng trực giao như thế nào? Mời em.
STUDENT
[INDISCERNIBLE] NORMAN: Right.
[KHÔNG NGHE RÕ] NORMAN: Đúng.
So since this is a product of two you scalars, at least one of the scalars better be 0, right?
Vì đây là tích của hai số vô hướng, nên ít nhất một trong hai số đó phải bằng 0, đúng không?
But in the beginning of the problem, we say that lambda k cannot be equal to lambda l. So since lambda k does not equal to lambda l, this scalar cannot be equal to 0.
Nhưng ngay đầu bài ta đã có lambda k không bằng lambda l. Vì lambda k khác lambda l, số vô hướng này không thể bằng 0.
So that means the inner product better be 0.
Vậy tích vô hướng phải bằng 0.
So that means that the eigenvectors are orthogonal to each other.
Nghĩa là các vectơ riêng trực giao với nhau.
All right. All right. So the next part says okay, so now we know that they're mutually orthogonal and each of them has unit length. So they can form an orthonormal basis for RN.
Được rồi. Tiếp theo. Phần tiếp theo nói: bây giờ ta biết chúng trực giao đôi một và mỗi vectơ có độ dài bằng 1. Nên chúng tạo thành cơ sở trực chuẩn của RN.
So that means we can express an arbitrary vector x in RN as a linear combination as follows. So this is expressing as a linear combination.
Vậy ta có thể biểu diễn một vectơ x bất kỳ trong RN dưới dạng tổ hợp tuyến tính như sau. Đây là biểu diễn dưới dạng tổ hợp tuyến tính.
So now the first part is just saying, what is the n-th coefficient alpha n in the linear combination?
Phần đầu hỏi hệ số thứ n, alpha n, trong tổ hợp tuyến tính là gì?
All right, so in this part — so we know that they're each orthogonal to each other. And we're interested in particular alpha n.
Ở phần này, ta biết các vectơ trực giao với nhau. Và ta quan tâm đến alpha n.
So we want to somehow solve for alpha n in this problem.
Nên ta muốn tìm alpha n.
So one way we can do this, since we know that they're orthogonal, we would be motivated to take the inner product of x with vn. So let's do that.
Vì chúng trực giao, một cách làm là lấy tích vô hướng của x với vn. Ta làm thử.
So on the other side, we would have the sum from i equals 1 to N of alpha n times the inner product of v. Oh, okay.
Ở vế kia, ta có tổng từ i bằng 1 đến N của alpha n nhân tích vô hướng của v... À, khoan.
I changed the index to i, but vn and vi. So all the terms — okay, wait.
Tôi đổi chỉ số thành i, nhưng vn và vi. Vậy tất cả các số hạng... khoan đã.
Okay.
Được rồi.
All right, let's be consistent.
Cho nhất quán nhé.
So I'm going to change the index to i.
Tôi đổi chỉ số thành i.
So that will be alpha i times vn inner product with vi. So the only term that will survive is the case where i equals to n.
Vậy là alpha i nhân tích vô hướng của vn với vi. Số hạng duy nhất còn lại là khi i bằng n.
So that will give us alpha n times vn, vn. And since each of the eigenvectors have unit length, this just equals alpha n.
Ta được alpha n nhân vn, vn. Và vì mỗi vectơ riêng có độ dài bằng 1, nên cái này bằng alpha n.
So that means that alpha n is just simply equal to the inner product of vn and x for this part.
Vậy alpha n đơn giản bằng tích vô hướng của vn và x ở phần này.
And you could have immediately written this without doing this inner product argument by simply knowing that we just need to project onto vn because they're orthogonal to each other.
Thực ra có thể viết ngay ra mà không cần lập luận tích vô hướng, chỉ cần biết ta chiếu lên vn vì các vectơ trực giao với nhau.
All right, so then part 2 is like, suppose x is a unit length vector. Now we want to show that all the sum of the squares of the weights equals 1.
Rồi, phần 2 nói rằng giả sử x là vectơ có độ dài bằng 1. Ta cần chứng minh tổng bình phương các hệ số bằng 1.
So spend a few minutes thinking about that.
Các em suy nghĩ vài phút nhé.
All right. So we're given that x is a unit length vector. So that means even the norm squared is equal to 1. So the inner product of x with itself would just be 1.
Được rồi. Đề cho x là vectơ có độ dài bằng 1. Tức là chuẩn bình phương bằng 1. Nên tích vô hướng của x với chính nó bằng 1.
So we can just substitute — so we have an expression for x. So we can just substitute that down here.
Ta thay vào thôi, vì ta đã có biểu thức của x. Ta thay xuống đây.
So this is going to be x transpose x, which is just going to be the sum from i equals 1 to N of alpha i vi transpose.
Đây là x transpose x, bằng tổng từ i bằng 1 đến N của alpha i vi transpose. Và cái còn lại là tổng từ j bằng 1 đến N của alpha j vj.
And the other one will be from j equals 1 to N of alpha j vj.
So we can just bring the sums over.
Ta đưa các tổng ra ngoài.
So that will give us this j times the inner product of vi and vj.
Ta được alpha i alpha j nhân tích vô hướng của vi và vj.
All right. So now in this sum, what terms will contribute? Which ones will not be 0?
Được rồi. Trong tổng này, số hạng nào còn lại? Số hạng nào khác 0?
So we know that the eigenvectors are mutually orthogonal to each other. So the only terms that will be 1 is if i equals to j.
Ta biết các vectơ riêng trực giao đôi một. Nên chỉ các số hạng có i bằng j mới bằng 1.
So that means we can write this as — so we can write this as from i equals 1 to N of alpha i squared.
Vậy ta có thể viết lại thành tổng từ i bằng 1 đến N của alpha i bình phương.
And then the inner product is always 1. So since the original inner product equals 1, the sum of the weights better be one.
Còn tích vô hướng luôn bằng 1. Vì tích vô hướng ban đầu bằng 1, nên tổng các hệ số bình phương phải bằng 1.
So this was equal to 1, so I just brought that over. Yeah, that proves that.
Cái này bằng 1 nên tôi chuyển sang đây. Vậy là chứng minh xong.
Any questions about this part?
Phần này có câu hỏi nào không?
All right. All right. So now part d is like, we're trying to solve the original problem. How do we minimize the norm of Ax with x being a unit vector?
Được rồi. Tiếp tục. Phần d, ta cần giải bài toán ban đầu. Làm sao cực tiểu hóa chuẩn của Ax khi x là vectơ đơn vị?
So we basically want to use the previous parts. We have a lot of information now. How can we use that information to find the minimum?
Ta sẽ dùng các phần trước. Giờ ta có nhiều thông tin rồi. Làm sao dùng chúng để tìm giá trị nhỏ nhất?
All right, so let's start going over it. So we're interested in the quantity the norm of Ax. So that gives us x transpose A transpose A times x.
Ta bắt đầu nhé. Ta quan tâm đến chuẩn của Ax. Nó bằng x transpose A transpose A nhân x.
So the previous part was hinting that we should probably use a similar expansion to this.
Phần trước gợi ý rằng ta nên dùng một khai triển tương tự thế này.
So substituting that in, we'll get equals 1 to N of alpha i vi transpose times A transpose A times another sum.
Thay vào, ta được bằng 1 đến N của alpha i vi transpose nhân A transpose A nhân với một tổng khác.
And we know that these v's are eigenvectors of A transpose A. So we can bring that over and simplify this as follows.
Và ta biết các vi này là vectơ riêng của A transpose A. Nên ta có thể đưa nó sang và rút gọn như sau.
And then we can use a similar argument here. So we can combine the sums and then we'll get a bunch of inner products with vi and vj.
Rồi ta dùng một lập luận tương tự ở đây. Ta gộp các tổng lại, và sẽ có một loạt tích vô hướng giữa vi và vj.
So the only terms that will contribute is when i equals to j. So then we can simplify this to be as follows.
Vậy những số hạng duy nhất còn lại là khi i bằng j. Rồi ta rút gọn thành như sau.
And then the inner product of vi with itself will be 1. So Ax squared will equal something like this. So now the question is, okay, how do I minimize this?
Và tích vô hướng của vi với chính nó bằng 1. Vậy Ax bình phương sẽ bằng cỡ như thế này. Giờ câu hỏi là, làm sao cực tiểu hóa biểu thức này?
What should I pick x to be equal to?
Ta nên chọn x bằng gì?
I want this to be small, right? So this will be like alpha 1 squared times lambda 1 plus alpha 2 squared times lambda 2, and so on. So how do I minimize that?
Ta muốn nó nhỏ, đúng không? Nó sẽ là alpha 1 bình phương nhân lambda 1 cộng alpha 2 bình phương nhân lambda 2, và cứ thế. Vậy làm sao cực tiểu hóa nó?
Yeah.
Bạn nói đi.
STUDENT
[INDISCERNIBLE] the lambdas.
[KHÔNG NGHE RÕ] các lambda.
NORMAN
Right. So since the lambdas are in ascending order, we want to pick the smallest lambda possible.
Đúng. Vì các lambda được sắp theo thứ tự tăng dần, ta muốn chọn lambda nhỏ nhất có thể.
So in particular, we want all the weights to be to the smallest eigenvector — I mean to the smallest eigenvalue. So what vector x would accomplish that?
Cụ thể, ta muốn mọi trọng số dồn vào vectơ riêng nhỏ nhất — ý tôi là giá trị riêng nhỏ nhất. Vậy vectơ x nào làm được điều đó?
So it'd be v1, right? Because that will make sure that the only alpha that will contribute is alpha 1. So we should pick x equals to lambda 1 — or not lambda 1, v1.
Là v1, đúng không? Vì như thế đảm bảo alpha duy nhất đóng góp là alpha 1. Vậy ta chọn x bằng lambda 1 — à không, v1.
And then the norm of Ax will equal lambda 1.
Và khi đó chuẩn của Ax sẽ bằng lambda 1.
And the reason we had you show the part 1 was that lambda 1 is positive is because it's just to verify like the norm can't be negative.
Lý do ta cho các em chứng minh phần 1, rằng lambda 1 dương, là để kiểm tra rằng chuẩn không thể âm.
That would be not right. So that's what the first part was trying to accomplish. Are there any questions about the proof? Yeah.
Như vậy là sai. Đó là mục đích của phần đầu. Có câu hỏi nào về phép chứng minh không? Bạn nói đi.
STUDENT
[INDISCERNIBLE] NORMAN: Yeah. So we know that vj's are eigenvectors of A transpose A. So we can just bring this in.
[KHÔNG NGHE RÕ] NORMAN: Vâng. Ta biết các vj là vectơ riêng của A transpose A. Nên ta có thể đưa nó vào đây.
So A transpose A times vj will just equal lambda j times vj because it's an eigenvector. Yeah.
A transpose A nhân vj sẽ bằng lambda j nhân vj vì nó là vectơ riêng. Vâng.
STUDENT
[INDISCERNIBLE] NORMAN: Yeah. Okay. Yeah. Yeah.
[KHÔNG NGHE RÕ] NORMAN: Vâng. Được rồi. Vâng. Vâng.
STUDENT
Can you repeat the last question, why you chose x [INDISCERNIBLE]?
Thầy nhắc lại câu hỏi vừa rồi được không, tại sao thầy chọn x [KHÔNG NGHE RÕ]?
NORMAN
Oh yeah. So we want this to be as small as possible, right? So we basically want to pick the smallest eigenvalue.
À vâng. Ta muốn cái này nhỏ nhất có thể, đúng không? Nên về cơ bản ta chọn giá trị riêng nhỏ nhất.
Because if we pick a bigger one, like if there's a component with a larger eigenvalue, that will increase their sum. So we want to minimize this.
Vì nếu chọn giá trị lớn hơn, tức là nếu có thành phần ứng với giá trị riêng lớn hơn, nó sẽ làm tổng tăng lên. Mà ta muốn cực tiểu hóa nó.
So we just pick all the alphas to contribute to alpha 1 — I mean to lambda 1. Yeah. So therefore, x is just equal to v1. Yeah.
Nên ta chọn mọi alpha đều đóng góp vào alpha 1 — ý tôi là vào lambda 1. Vâng. Vì vậy x chính là v1. Vâng.
Other questions?
Còn câu hỏi nào khác không?
So I think we're basically out of time, right? All right. If you want to start on — yeah, yeah.
Tôi nghĩ chúng ta gần hết giờ rồi nhỉ. Được rồi. Nếu các em muốn bắt đầu làm — vâng, vâng.
So for the rest of the five minutes, we can just have general questions about the exam or anything about module 3. So if you have any questions, feel free to ask them.
Năm phút còn lại, ta có thể hỏi bất kỳ câu hỏi chung nào về kỳ thi hoặc về module 3. Nếu có câu hỏi, các em cứ hỏi nhé.
Otherwise, that's like the end of the review session. Yeah, thanks. [APPLAUSE]
Nếu không thì buổi ôn tập đến đây là kết thúc. Cảm ơn các em. [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.