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