So what I'd like to do today is continue our discussion of unsupervised learning algorithms, and in particular, we'll talk about PCA, principal components analysis. Really one of the old, classic learning algorithms that I still use every now and then. There's one application I'm using that uses it, so I do use this. And then also ICA, independent components analysis. One of the most interesting things about PCA is that while it's useful in some contexts, I see a lot of people use it when they really should not be applying PCA. So today I also try to give some suggestions and some advice on when to use it, but also when to not bother using PCA.
So last week on Wednesday you saw the factor analysis algorithm, which is a way to take very high-dimensional data that maybe lies on a lower-dimensional subspace and tries to model that as a very high-dimensional Gaussian that spans a low-dimensional subspace of a very high-dimensional space. And that was a probabilistic method, right? So for factor analysis you wind up building a model P of X for the density of X in this very high-dimensional space. And we had the example of maybe 100-dimensional data with 30 examples. Now what you see today, principal components analysis, is an algorithm that is not probabilistic. It does not model P of X. But that allows you to nonetheless figure out if your data lives in a low-dimensional subspace, what is that subspace and how to reduce the dimension of the data.
So let's start with a specific example. And actually, I'm still trying to figure out what is this better? Then when I go to the PowerPoint I'll switch lighting. Okay, so let's start with an example. We're still using unsupervised learning. And so as usual, you have an unlabeled data set like this. And what we'd like to do is reduce the dimension from n dimensions to maybe k dimensions, where k is maybe much less than n, right? And so for example, let's say that you have a data set, let's say that you run a school and in the same month for whatever reason the school for young children wound up measuring the children's height in centimeters and also their height in inches, right? And so you may have a data set that looks like this. And because of rounding to the nearest centimeter or rounding to the nearest inch, you know, the data is almost perfectly correlated but not completely perfect, not completely correlated. But this data set, even though you have two-dimensional data, so in this case n equals 2, you know, this is really kind of 1D data but living in 2D, right? Because these are both measurements of the height of these school children in your school. And so what we will do is come up with an algorithm, PCA, that will figure out that that diagonal arrow is really the dimension on which the data varies. It will be the principal axis of variation of the data, which is really, you know, children can be tall or short whether it's measured in inches or centimeters. And that there's just a little bit of noise in the orthogonal dimension, in the 90-degree dimension. Orthogonal means at 90 degrees, right? So the orthogonal dimension to this principal axis of variation. And what you can do is take the data and project it onto the principal axis of variation. So you can turn your 2D data into one-dimensional data, and that one-dimensional is a cleaned-up, less noisy version of what is the height of these school children.
Okay. Now this example is a little bit contrived or a little bit far because, you know, inches and centimeters is basically the same thing, right? It's really the length. A slightly different example would be if you have some variables. Let's say that you're running a factory and you have two vibration sensors on maybe two different parts of the machine. So you can have a vibration sensor one and a different sensor two on a big, you know, big factory machinery that's shaking, right? And you could have two sensors maybe made by two different manufacturers on two different parts of the machine. And again, the noise may be bigger, but maybe you think, well, both of these sensors are just measuring how much is this machine shaking, because you want to do preventive maintenance. If it actually turns out that before your washing machine at home breaks, right, before it faults, often the pattern of how it shakes will change. And so having vibration sensors can help you to prevent the maintenance. But having two different sensors might let you, again, you might want to reduce the data from two dimensions down to one dimension, right? And maybe just one last example. For quite some time I was working with helicopter pilots here at Stanford, right? So we're flying autonomous helicopters. And if you think that on the x-axis, let's say you measure pilot skill, you'll have some tests on how skilled are the pilots. And on the vertical axis you measure, you know, pilot enjoyment, how much they enjoy flying the helicopters, right? So these are two different things, but you might hypothesize that what really matters is some measure of the pilot aptitude. You know, how good an RC pilot are they, and good pilots maybe enjoy flying more and have more skills, and intrinsically what is their aptitude or something, right? Then PCA is a way to take your two-dimensional data and try to project it down to one dimension, okay? And end up with a one-dimensional data set instead. Okay. All of these examples are really low-dimensional. In practice, you very rarely use PCA to reduce a two-dimensional data set to one dimension. The typical numbers may be more like that. You know, if a 10,000-dimensional data set, you might reduce it to 100 dimensions or a thousand dimensions. But going from two to one is just really, you know, small. People don't do this in practice, but because of the constraints of a two-dimensional whiteboard, I'm going to use this. But in practice the numbers look more like this. Right?
So let's talk about how you would actually implement something to reduce the dimension of the data before running PCA. A common pre-processing is to zero out the mean and standard deviation. Right. All right. Okay. So before running PCA, actually before running many supervised learning algorithms, I guess you do this, it makes gradient descent behave better. But so you compute the mean, subtract out the mean from every example, and then compute the variance of each feature j and divide by the square root of the variance, or divide by the standard deviation, or if you want, the square root of the variance. Right? So now each of your features has mean zero and variance one. So standardize the variance to one.
Okay. Now let's see how we would implement PCA. All right. So with two features X1 and X2, right? And it looks like the principal axis of variation, you know, looks a bit like the 45-degree line, right? And the mean and variance of these, you know, maybe close enough, right? Roughly zero, right? Okay. So let's take a look at what it means to define the principal axis of variation of this data. It looks like that is a pretty good candidate for a one-dimensional subspace onto which to project this two-dimensional data. Right? You want to reduce the data from 2D to 1D. Looks like that green line is a pretty good direction onto which to project the data. And one way that this is a... now in contrast, you know, it looks like this red line is like a really bad way, really bad dimension onto which to project the data, right? The red line is like almost the worst possible choice for what you think is the principal axis of variation. So what is the difference between the red line and the green line? Here's one difference, which is that if you look at, if you take each cross and you project it using an orthogonal projection. So orthogonal projection means that this little green line segment and that long green line are at 90 degrees, right? So projected the shortest distance to the green line. Right? If you look at all of these projection distances, all of these distances between the point and this long green line, their sum of square distances is quite small, right? So the sum of square distances between the blue crosses and the green dots is quite small. But in contrast, if you were to project this onto any other line such as a red line, then the sum of square distances between the blue crosses and the red dots is really large, right? So for PCA, what we'd like to do is to find the direction of that green line. So that when you project your training examples, the blue crosses, when you project these blue crosses onto this green line, that you minimize the sum of squares of the projection distances. That would be one possible way to define PCA. It turns out that there are multiple ways to derive PCA, and what I want to do today is actually use a slightly different but equivalent definition of PCA. And the equivalence you actually get to work out and prove yourself in the homework, which is there's another way to look at PCA. I'll go through this in a second, which is if you look at the green dots, it looks like the green dots are spread apart very far from each other, right? But if you look at the red dots, it looks like the red dots are really clustered together. So if you'd like to preserve as much of the variability of the data as possible, a second possible intuition behind PCA is you want to find a line onto which to project your data so that the data still remains as spread apart as far as possible.
Okay. So what I want to do, it turns out both of these intuitions I just described are actually mathematically equivalent. I'm going to use the second one today to derive PCA in lecture, and then you can actually use the first one in the homework to show that these two are actually equivalent. Okay. So let's see, what we'd like to do is find the direction of the green line, and in particular we'd like to find a unit vector u that points in that direction. Right? So to specify the green line you need to specify a unit vector specifying the direction of the green line. And so what we'd like to do is find a direction of u in order to specify that direction onto which you want to project the data. Okay. So if the length of a vector, this L2 norm, right, so if the L2 norm of a vector is equal to one, then the length of the projection of X_i onto u is u transpose x_i. Okay. So from what we saw, right? If this is u and this is x, then this length here is u transpose x_i, right? So in PCA we're going to choose a vector u to maximize. So what we're going to do is maximize the spread of the green dots. And so we're going to maximize the sum over your m training examples of x_i transpose u squared. Right? Let me just put a one over m there. And you're going to maximize this over all the choices of u where the length of u is equal to one. Okay. So this notation, maximize over all vectors u such that the length of u is equal to one, of 1/m sum of the square of the magnitude of the projections. Right? So in other words, another way to describe this is you want to maximize the sum of this length squared plus the sum of this length squared plus sum of this length squared and so on, summed over your five training examples. Okay. Um, so let's expand this out. This term you're maximizing over is equal to that u transpose x_i times x_i transpose u. And I guess by linearity you could pull out u transpose and u, so this is u transpose 1/m... Okay. So, let me just take this matrix and call this matrix sigma. Right? And one of the unfortunate things about this notation is that sigma, the covariance matrix, is that symbol is the same as the summation symbol, but hopefully it'll be clear from context. Right. And so what we would like to do is maximize over u, norm of u = 1, u transpose sigma u. Okay. And it turns out that the way to solve for the value of u that maximizes this is that u is the principal eigenvector of the matrix sigma. Right? And sigma here, the way we've defined it, it is the covariance matrix of the data after you set mean to zero and standardize it. This matrix sigma is the covariance matrix of the data. And so this means that the first principal component, the principal axis of variation, is the principal eigenvector of sigma. Oh, let me just check, how many of you have seen eigenvectors and eigenvalues before? Wow, cool. Okay, great. Most of you. All right, good. All right, I won't spend too much time on this then. But maybe, yeah, let me just give a real quick explanation for why this is the eigenvector. Right, and so just recall, if Au equals lambda u, then u is an eigenvector of A, right? And lambda is the eigenvalue. And the way you show that this corresponds... actually, how many are familiar with the method of Lagrange multipliers? Okay, less of you. All right, so if you're familiar with the method of Lagrange multipliers, which you don't have to be, one way to go from this problem is that if you want to maximize u transpose sigma u subject to norm of u = 1, then to solve a constrained optimization problem like that you form a Lagrangian, right? Which is how you solve constrained optimization problems. So this constraint is u transpose u equals 1. And then take derivatives with respect to u of the Lagrangian, which is sigma u minus lambda u, which you set to zero, which is why you get that sigma u equals lambda u, and thus u must be an eigenvector of the covariance matrix sigma. Okay, if you didn't get that, don't worry about it. But this is just if you're familiar with the method of Lagrange multipliers for constructing Lagrangians to solve constrained optimization problems where you want to maximize this subject to this constraint, then this is how you show that this is equivalent to that. But if you didn't understand the details, it's okay.
All right. So to summarize, what we found here is that if you want to choose a one-dimensional subspace with which to approximate your data x, choose the dimension of that one-dimensional subspace to be given by the principal eigenvector of the covariance matrix sigma of the data. Okay. Oh, and let's see, so the intuition about why the two... let's see, I gave two intuitions. One is maximize the spread of the green dots, that's what we just worked through. The other is minimize the square distances between the blue crosses and the green dots. And it turns out these are equivalent sort of by Pythagoras' theorem, right? Where if you look at this triangle, right? But again, the full details, don't worry about it, you see the full details in the lecture notes, excuse me, in the homework, you can prove for yourself why these two ways of deriving PCA give you the same answer, right? And I think actually many years ago there was a paper that proved that there are something like 11 equivalent ways to derive PCA, and these are two of them, right? All right. So in a more general case, if you wish to project the data to K dimensions, then set U1, U2, U3 to be the top k eigenvectors of the covariance matrix sigma. Okay. And you know, with lambda 1, lambda 2 and so on up to lambda k as the corresponding eigenvalues. Okay. So in other words, let's say you have... okay, let's use the new board. All right. Okay, so let's say you have very high-dimensional data, right? Say 1,000... well, 1,000 is not that high these days, but let's say you have a 10,000-dimensional data. And you want to reduce the dimension from 1,000 to 10, then you would compute U1 up to UK, say k equals 10, and then you would have a new representation of the data where instead of x_i you can now represent it using 10 numbers which are given by u1 transpose x_i, u2 transpose x_i, up to u10 transpose x_i. And so now instead of using a thousand numbers to represent the training example, you're now using, you know, 10 numbers to represent a training example. And in the example we had earlier about, you know, children's height in centimeters and inches, you'd be reducing it from two dimensions to one dimension. And so now for each child in your data set, you would have just one number that is a slightly cleaned-up estimate, right, of the height of the child. Okay. And if you want to... and let me just call this yi, right, as a new representation. It turns out that if you ever want to go back from y to x, it turns out that x_i is approximately yi1 * u1 + yi2 * u2 + dot dot dot plus yik * uk. Okay, so you've taken your thousand numbers, your thousand-dimensional data, and compressed it to a 10-dimensional representation. If you ever want to uncompress your data and go back from this low-dimensional y representation up to this thousand-dimensional representation, this is how you map from your 10 numbers y1, y2 up to yk back up to a thousand-dimensional subspace, right? And what this formula does is it actually tells you the position of these projections, right? All of these decompressed representations would live in a 10-dimensional subspace, but these are, you know, 10-dimensional points in a thousand-dimensional space. They're all... but these are 10,000-dimensional vectors, right? So these would be in R^N. Okay, cool. So this is how you implement PCA. I'm going to go into some practicalities and some applications a little bit before I take questions.
>> How do you know what's... it just by? >> Uh oh. Say how do you choose K? >> So you said you pick the top. >> Oh, I see. Yeah. >> I see. >> All right. So each eigenvector ui is paired with an eigenvalue lambda i. So you pick the eigenvectors corresponding to the biggest eigenvalues. And then the other question is how do you decide how many eigenvectors to keep? Let me come back to that in a second. If you use a, you know, like off-the-shelf PCA software or off-the-shelf eigenvector solver, right, in numpy or something, most implementations will return the eigenvectors sorted in decreasing value corresponding to their eigenvalues as well. So you just take the top k. Any questions?
>> Yeah. Why do you do pre-processing? >> Uh oh. Why do you do pre-processing? Oh, thank you. Yeah. So, it turns out that... so it turns out that this is what goes wrong if you don't subtract the mean and standardize the variance. It turns out that if your data kind of lives out here, right? And you don't subtract off the mean, it turns out that actually, let's say your data look like that, right? If your data lives out there, then it turns out that PCA would choose that as a principal axis of variation. Whereas you subtract off the mean, then your data is lined up like that and it would choose that as a much better choice. So that's why you subtract out the mean and why you standardize the variance, is because if your axes are very different, you know, maybe this is now centimeters and this is now kilometers, right, then your data will kind of look like that and PCA will just choose that direction. So that's why it's a pre-processing step, right? Okay, cool, yeah.
>> Say again? Um, let's see. So let's use the children's height example. So in that case x_i is in R^2 and y is in R, right? So you've now compressed each child's height, which was previously represented with two numbers, into a single number. And oh, and if your goal is to run a learning algorithm, right, to predict something about children, you know, whatever, how good are they at basketball as a function of the height, you can then use this as the input feature, you know, to predict what's the chance of their basketball skill or something. And the mapping in the reverse direction is now that you have a... right, if you want to map your data back to the space of X1 and X2, that formula helps you map back from R^1 to R^2. But it turns out that if you take the different children's height and map them back, they'll all lie on a straight line like that. So... um, so y_i is u1 transpose x_i, right? And so if this is the vector... let me think, yes, actually basically yes, in 1D, if this is your original, if you had an example like that, and if this is the vector u, then this length is y_i, I guess, yes, it's the magnitude of the projection of x onto each of the vectors, right? Okay. All right. Cool.
So, some applications of PCA, and I'm going to talk about both good applications and bad applications. So one, you know what? I think I want to use the display. All right. So one good application of PCA is visualization. And so in particular, if you have very high-dimensional data, then you can use PCA to project your data from, you know, n-dimensional to 2D or 3D, right? And maybe you have some ways to visualize 4D data if you have time and animation or something. But so one of the... let me see. All right, cool. So one of the most interesting applications of PCA that I've seen here at Stanford was there was a Stanford student, still is, Ashesh, who was working on sticking electrodes into monkeys' brains and modeling how the state of the monkey's brain evolves when the monkey is planning a task to use his hand to reach out to touch a target. Right? So in his lab he has, I guess I don't know, a batch of monkeys or flock of monkeys, I'm not sure how you call monkeys, with electrodes stuck on their brain measuring little impulses of electricity. And what he did was... All right, cool. And what he did was train the monkeys to carry out reaching tasks where there'd be a square that appears on a touchscreen and it would be the monkey's job to reach out and tap his finger on the location of this little square on basically a touchscreen. And if it successfully taps a square then it gets a reward, right, gets a squirt of juice into his mouth. And so what they did, what his lab did, was measure a lot of electric impulses in the monkey's brain. But if you have 50 electrodes then you get this 50-dimensional time series, right? So you measure the amount of electricity in, let's say simplifying a little bit, let's say in 50 different points on the monkey's brain, and you now have this 50-dimensional data which is very hard to visualize because you can't plot data in 50D. So one of Krishna's students actually took CS229 several years back, quite a few years ago, and learned about PCA from this class and wound up using PCA to reduce the dimension of the data from 50 to three. And the fascinating result was that they could now visualize how the monkey is thinking and planning as it readies its brain and its arm for the task of reaching out to tap a target on a screen. And so this wound up being a breakthrough result in neuroscience because you can now really visualize how a monkey readies his brain, readies his arm, thinks through, all right, how to reach his arm, and then when the monkey sends the go signal, right, all right, go monkey, then you can actually see the state of the monkey's brain change as it's reaching out to tap the target to get this juice reward, right? I thought this is a cool example because it's a Stanford example. But whenever you have very high-dimensional... So, oh, so you could actually see in a 2D or 3D space, the monkey's brain is there. It's just waiting, waiting, waiting. You show the target, then it goes, all right, it's planning, then just waiting, waiting. You say go and then the monkey's brain moves, right? So you can actually plot, this would be Y1 and Y2, I guess, the trajectory of how the state of this 50-dimensional state of the monkey's brain evolves. You can actually see the brain transition through different states as it goes through this task, right? So whenever you have very high-dimensional data, higher than 2D or 3D, PCA can help you with visualizing the data.
Some other applications of PCA... excuse me... is compression for learning algorithms efficiency. Right? So let's see, it turns out that most of your high-dimensional data lies on a low-dimensional subspace. It's just a fact of life. You know, if you have a 10,000-dimensional data set, there's a pretty good chance that your 10,000-dimensional data set actually is quite well approximated by a much lower-dimensional subspace. You know, maybe a 10-dimensional or a 100-dimensional subspace or something. And it turns out that if you feed X, say 10,000 dimensions, to a learning algorithm like a support vector machine, then you're carrying around these 10,000-dimensional examples throughout your whole training process. But if you can compress your data to this y_i representation which is just 100-dimensional, then your memory bandwidth, your network bandwidth, your computational speed, right, you can run your learning algorithm on a much lower-dimensional set of data and it may be much more efficient. And so one other pretty good application of PCA is if for computational efficiency you want to lower the dimension of your data before you feed it into some expensive learning algorithms. So I've done this a few times. Right? Now let me mention some slightly more questionable applications of PCA. And people still do this a bit, but again, well, I'll just mention them. Questionable doesn't mean bad, it's just that, you know, it's questionable, right? One way is to reduce overfitting, right? So one thing you might think is PCA is a way to reduce my data from 10,000 dimensions to a thousand dimensions. So if you're using say logistic regression, maybe logistic regression on a thousand D is less likely to overfit than logistic regression on a 10,000D. This is one of those things where if you try it, I think it works half the time, it fails half the time. But what happened over the years was enough people tried it and because it worked half the time, that half of the time people publish papers and then the other half of the time that it fails, you know, there's nothing to publish. And so I think over some number of years there wound up being some number of papers where people use this to reduce overfitting and it kind of works. But this is one of those techniques I think works as often as it fails, just in my experience. And so I tend not to use PCA to reduce the number of features for the purpose of reducing overfitting. Instead I would, you know, use regularization instead, right? That's what I would do. And then there's actually one other slightly questionable... again, this one is another one of those techniques. They use PCA, it sometimes works, sometimes...
I don't think it works more often than it fails. But because it sometimes works, people will publish papers on this. But so I just don't recommend this as outlier detection.
Right. And actually let me just talk about matching. So there was one theory actually. In the very early days of face recognition, how do you look at two pictures and see if two pictures are of the same person? Now we have laptops and smartphones that unlock using your face. In the early days of face recognition, how do you tell if two pictures are of the same face? So there was this theory that given two pictures of two faces, you could measure the Euclidean distance in the pixel space. The original data is just the pixel values of the two pictures. So one thing you do is measure these pixel value differences. But there was a theory that if you reduce the dimension of the data and measure the distance in this reduced dimension subspace, maybe you're cleaning up some of the noise. So to tell if I and J are the same person, just look at the sum of squares pixel distances to see how different these two pictures are. But maybe if you go from a 10,000 dimensional space, and if your picture is 100 by 100 pixels, then that is 10,000 grayscale values. So it's a 10,000 dimensional vector. If you use PCA to reduce it to say 1,000 dimensions, maybe that will reduce the dimension of your subspace. You can now measure distance in this slightly cleaned up data. So unfortunately this is one of those results that, again, I personally would not do this, but sometimes if you do this you get lucky and it works a little bit better. But this is not a reliable result. So hardly anyone does this anymore, but you sometimes still see people use this method and sometimes they get lucky and it kind of helps a bit. But this is not how I would tend to use PCA.
So there were actually early face detection systems. There's actually a well-known result called eigenfaces in which you run PCA on this face data set and then you plot the eigenvectors as an image. So the eigenvector u is a 10,000 dimensional vector. So if it's 100 by 100 pixels, then the dimension of x as well as the dimension of u is 10,000 dimensions. And you can plot the eigenvectors and you get pictures like this. And yeah, we used to tell ourselves stories like that. Gee, it looks like this picture on the upper left is whether the face is illuminated on the left or the right, and this is how much does this person have a beard. And we used to tell ourselves stories like that, but I think we learned that these results are at least as much a product of the researchers' imagination as an actual phenomenon. So I would just discourage it. It turns out that individual eigenvectors are very noisy. So whenever I run PCA, I tend not to look at any single eigenvector, because it turns out that individual eigenvectors are very noisy and human interpretations that oh yeah, it looks like eigenvector 5 is does this person wear glasses? Those are often more the researchers' imaginations rather than a reliable result that you see in the data.
And so there are things like this that you input this face and these are the most similar faces and sometimes this works better if you use eigenfaces, but this is not a good method. I tend not to use this method anymore.
Okay, so PCA is a useful technique. I am using it for one project right now at Landing AI, but don't always use it. And let me just give you one rule of thumb: before using PCA, consider just using the original data XI. So what I've seen in past years in some CS229 project proposals as well is students would say I want to build a system and as part of the system I'm going to take the Xi and reduce it to some lower dimensional yi and it will do something with yi. And when it's visualization, that's great, because you can't visualize higher than two or three or maybe four dimensional data. But before having a component in your learning algorithm that reduces the dimension of your data from say 10,000 to 1,000 dimensions, just see if you could just use your original data XI and see how well that does. And unless you need to speed it up or reduce the memory footprint or something, consider, so before you submit a class project report that uses PCA as part of your project, just ask yourself how would the algorithm do if you were to not even use PCA and make sure that you're not adding in a PCA as part of your algorithm unnecessarily. And this is a little bit like we talked about premature statistical optimization where sometimes people build a system with a lot of complicated modules. So just consider not doing this. But I think the good reasons to use PCA are visualization or if you need to compress your data in order to drive more efficiency.
Did you say there's a minimum amount of dimensions before you should consider? Oh, is there a minimum number of dimensions before you should consider PCA? Not really. I could see even if you have, two to one is really extreme. But if you have an application where you have 2D data, but you really need to half your memory requirements, because you get a very large volume of data per second, maybe you could do it.
Yeah. At the back. A factor analysis. Great question. When would you use PCA? When would you use factor analysis? Let me get to that in a second.
Anything else? All right. Oh, yeah.
Oh, sure. So, train and test, right? Would you find the vector on the test data? The answer's actually no. So what you do is if you have a training set, let's say you want to use PCA to compress your data, what you would do is take your training set, run PCA on your training set and then your eigenvectors are fixed forever. You would not find a different set of eigenvectors on your test set. You just always use the same UIs that you found in your training set and use that same set of eigenvectors computed on the training set to map your test data to a low dimensional space. And but it turns out for those of you familiar with linear algebra, it turns out that the vectors UI, let's say U1 up to U10, these are 1,000 dimensional vectors. In the case we reduce from 10,000 to 100, it turns out that these 10, I'm going to switch into linear algebra terminology. So if you don't understand what I say, it's okay. But it turns out that these 10 vectors form a basis for a 10-dimensional subspace in this 10,000 dimensional space. And what you're doing is projecting the data onto a 10 dimensional subspace, a 10D subspace that is spanned by this orthogonal basis. And then you're using 10 numbers to represent your thousand dimensional data in terms of their projections onto this 10 dimensional subspace. And it turns out that vectors are orthogonal to each other because sigma is symmetric. Symmetric matrices have orthogonal eigenvectors. Sigma is symmetric positive definite. So sigma has orthogonal eigenvectors meaning all these u are at 90 degrees to each other. Which is why this is actually an orthogonal basis. And there's one degeneracy case in case of repeat values, but you should choose UI to be orthogonal which most linear algebra solvers do as well. All right, if you don't understand what I just said last 60 seconds, it's okay. Actually how many of you understood what I just said? Wow, okay, wow, okay, that's great. I love you guys.
Okay, so question: when do you use PCA and when do you use factor analysis? So what I'd like to do is take the four unsupervised learning algorithms we talked about and put them into this framework. And so some of the algorithms we talked about would model P of X, model what's the density of X. And one reason you might want to do that is anomaly detection. So some of the algorithms talked about were density estimation algorithms. And some of the algorithms we talked about were non-probabilistic. And then some of the algorithms we talked about assume that the data lives on a low dimensional subspace of a very high dimensional space. And some of the algorithms we talked about assume the data lives in clusters or maybe clumps. Clumps is not a formal term in machine learning. And so PCA falls in that category. It's not a probabilistic algorithm. There's no reference to P of X and it models the data as living approximately on a low dimensional subspace of a high dimensional space.
Actually anyone, what should go in here? What do you think here? Probably. So if you think your data lives in a low dimensional subspace and you want to model P of X, what's your call? Awesome. Cool. How about here, non-probabilistic, your data lives in clusters? It's awesome. And then here? Yeah, I'll say mixtures of Gaussians. Although this one, this is not a perfect answer because mixtures of Gaussians works in lots of scenarios where your data isn't quite in clusters as well. Oh and EM is a technique for density estimation. So EM works whenever you have a model of P of XZ where Z is latent or unobserved and you want to model P of X. So that's the category of problems that EM applies to which is why we use EM for everything in this first column for both factor analysis and for the mixture of Gaussians model.
Can Z be? Oh, can Z be continuous? Yes, Z can be. In fact in factor analysis Z is Gaussian and in mixture of Gaussians Z was discrete. And so the other way to think about these algorithms is the non-probabilistic algorithms, some of the applications include compression and sometimes visualization and sort of human understanding of data. So we talked about PCA as a visualization to reduce your data to 2D or 3D to visualize. You may remember we talked about K-means as a mechanism for market segmentation. You have a database of customers, you want to group your customers into four groups to develop different marketing campaigns for different four market segments. So that's a way for you to reduce the data into four clusters so that maybe your marketing team can look at the four market segments and do something about them. Or I've also seen people take genomic data and use that to cluster genes into a few different discrete clusters to try to understand if there are a few different types of genes. So clustering algorithms like K-means help us take the world and sort it into a small number of categories to help us better understand them. Or you can take a, yeah right, in fact I think the whole phylogenetic tree, all of life I guess clusters into animal kingdom, plant kingdom and so on, that's an attempt to cluster all of life onto a number of discrete categories as well.
Oh, why do you consider the cluster K-means interpretable but not the PCA components? Well so if you have a relatively small number of K-means clusters you can just look at them and say oh look this looks like the animal kingdom of living things, that looks like plant kingdom, that looks like whatever. It turns out that the position of individual eigenvectors are numerically unstable. Actually maybe here's an example. Let's say you have a 3D data but it lives roughly on a 2D plane. So this is actually 3D data with a little bit of fuzz off the surface of the whiteboard. It turns out that maybe you get that as U1 U2, and U3 points out of the board. But with very small perturbations to the numerical precision, very small perturbation of data you might easily get a different orthogonal basis which is why from a statistical point of view the exact orientation of the eigenvectors is very unstable, it's very noisy. Just change one training example, change something in the fifth decimal place and the eigenvectors can change significantly. So that's why I think if you look at individual eigenvectors and try to interpret them, they're often the hallucinations or often the imaginations of the researcher. What turns out to be stable is a subspace spanned by the first k eigenvectors. It turns out that if you look at the subspace spanned by the first k eigenvectors, the subspace is quite stable but the individual eigenvectors are not.
So yeah, how am I doing on time? All right go ahead. Also give a probabilistic interpretation to PCA in terms of delivery. Yes. Is it possible of PCA that kind of does that? But yeah. All right. One last question. No. Okay. Cool. Oh, right. All right. Just last two questions. Yeah.
PCA overfit? Oh, that's interesting. Can PCA overfit? Rarely. I guess one way for PCA to overfit would be if you have a 10,000 dimensional subspace, excuse me, 10,000 examples with a thousand dimensional subspace but only a thousand examples. So it would be a bit strange. So what PCA is trying to do is find a K dimensional subspace that captures the variations of the data. So I guess if K and your number of training examples M was too similar, it wouldn't do a very good job. Yeah. That's one question.
Um, so hang on. So I think of orthogonal rotations in such space. So first, you should pretty much always, I would never use non-orthogonal bases for the vectors U. Just make sure the U's are all orthogonal. It'd be very unusual to have the U's not be orthogonal to each other. So the vectors should always be an orthogonal basis for your subspace you're mapping to. And what happens in practice is by this example I did not mean that you would do this rotation on purpose. You wouldn't do that. What I meant was if two different people collect slightly different data on slightly different days just by chance the basis could rotate significantly. But you wouldn't actually do this manually. What you do is run PCA once and then you just get some basis and then you would just use that. And this was meant to an illustration that just by chance or just by luck, if your labmate had a data set that was very very slightly different they might get a totally different basis but you wouldn't make this rotation by hand on purpose.
Okay. All right cool. So there's one last question just now that I promised to answer and I'll answer this only briefly which is how many principal components do you keep, right? So what is the value of K? So one standard, if you, so it turns out that there's a metric you can compute which is compute the eigenvectors lambda 1 up through lambda k divided by the sum of all of the lambdas. And so it turns out that if this is, let's say, 0.9, then sometimes you see people say that this retained 90% of the variance of the data. So if you've ever seen someone write a paper that uses PCA and they say we use PCA to reduce the dimension from 10,000 to 1,000 dimensions and this 1,000 dimensional subspace retains 90% of the variance of the data, then that's what this means. And it's sort of, I don't want to go deeply into exactly what this means but this is just if you look at, let's see, so a data set with no variance is a data set where every example is equal to zero. Right? So variance in the data means how much does the data vary compared to if every example was exactly the zero vector. And it turns out that remember we start off deriving PCA in terms of maximizing the variance, project the data on the subspace you maximize the variance in the projections. So this is roughly how much of the signal did you keep and how much did you throw away. And so often you see people, the numbers you often see, well you see people use PCA to retain 90 or 95% maybe 98 or 99% of the variance of the data. You see this range of numbers quite common and it's not at all unusual if you're very high dimensional data set to compress your data set maybe 10x and still retain 95% of the variance of the data, basically keep 95% of the signal in your training set while having like maybe a 10x reduction in your data set size.
Actually debating how far to go into ICA. All right. Actually, let's do this. The second thing I want to do, we scheduled this for today and Wednesday, but I think I'll just make a start on setting up the ICA problem. But then we'll end up doing most of it on Wednesday instead of today. So, PCA finds the principal components of the data. ICA finds the independent axes of variations of the data. And so let's see. All right, this thing's warming up. In order to motivate what you actually get to do in one of the homework problems is implement an algorithm that solves the cocktail party problem. So here's a cocktail party problem which is if you go to a party and there are a lot of people standing around talking, we've been to those parties where there's so many people talking you can barely hear your own voice. So these three people talking and what we're going to do in this cocktail party is put a couple microphones here. And so speaker one's voice will go to both microphones. Both microphones will pick up speaker one and speaker two's voice will also be carried to both microphones. But what you find is that each microphone captures an overlapping combination of the two speakers' voices. And so what ICA will do is remember in unsupervised learning you have some data you're going to give the data to the algorithm and say hey algorithm figure out what's in this data for me. And so what you will be able to implement with ICA is to take the audio recordings from both microphones and feed your two microphone recordings to the algorithm and say hey ICA algorithm here's some unlabeled data figure out some stuff for me. And what ICA will do is figure out that this audio data is best explained in terms of there being two different speakers and separate out the voices of the two speakers. So let me do a demo. And in fact in the homework problem I'm going to do a demo with two speakers. In the homework problem, we'll ask you to implement ICA for five speakers and five overlapping voices. But so someone should play this audio.
All right, that was microphone one. Not the most interesting cocktail party. All right. And so when you feed this data to ICA, it will recognize that the underlying structure behind this data is not subspaces, is not clusters, but is that the two audio recordings were generated by two independent speakers that were speaking independently of each other. And it'll separate out the sources into the following. One, two, three, four, five, six, seven, eight, nine, 10. Right, that's the first source that ICA extracts. And the second one. So that was one example. Let's, and let me just play for you audio from another example. 1 2 3 4 5 6 7 8 9 10. All right. So, the poor guy's gone home from the cocktail party. Now he's sitting in the room talking to his radio. Oh, that's the second source. 1 2 3 4 5 6 7 8 9 10. And when you run this through ICA, this is what it gets. These are real examples, real audio recorded in a physical room. And so the results aren't perfect, but this gives you a sense of what ICA can do. 1 2 3 4 5 6 7 8 9 10. Right? Got rid of most of the music so you can hear the counting much more clearly than each of the original clips. And then the second one. Right? And so what you will see a little bit today and then more on Wednesday is how you can implement an algorithm in order to do that.
So, oh, and in the homework problem, we'll give you data with five overlapping voices and ask you to separate out not two, but five overlapping voices. So in ICA we're going to assume that the data was generated through some set of sources S in Rn where you have n speakers. So you have two speakers S is in R2, you have five speakers S is in R5. And so Sij is equal to the signal from speaker J at time I. And you know how does sound work? If you look at oscilloscope recordings of sound or some laptop applications can plot sound. This is what sound looks like. Let's say this is speaker one. Then sound looks like these periodic functions like these. Sorry, not really periodic but this is time. And what a microphone does is records very minute variations in air pressure and those are the numbers stored in your computer when you have an audio recording. So over time sound is captured by a microphone by capturing tiny increases and decreases in air pressure. And that's how your ear works as well. The way you're hearing my voice is my voice or the microphones or the audio system is creating very rapid changes in air pressure and those air pressures are transmitted to your ear through the air and then your ear measures these very rapid changes in air pressure and your brain then interprets as a sound. So at time t this height is st1 if that's speaker one. And I don't know if speaker two looks like this. Then at the same time t the height of this is st subscript 2. Oh, and a perfect sine wave like this, this is what a tuning fork sounds like, it's like a pure tone, ding. If you have a tuning fork, that's just so I guess speaker 2 is not a very interesting speaker either. Yeah. Question.
Do you require the recordings to be aligned? Do you require the recordings to be aligned? Yes, we do require that microphone one and microphone 2 be timestamped consistently. Yeah.
And so we observe xi equals A of si. Great. Okay. So, if you have two speakers and two microphones, then what you observe is each microphone captures a linear combination of the speaker sources. You have two people talking and sound adds. And so each microphone records a linear combination captured by this mixing matrix A of the speaker sources. And so Xij is the recording of microphone J at time I. And so J will range from 1 through n. Okay. So to take this equation and just write it out an equivalent way. This is that xij is equal to sum over k ajk sik. Right? So at time I microphone J gets this linear combination of the K speakers. And the goal is to find the matrix W defined as A inverse so that you can recover the sources from W XI. And what the ICA algorithms do is given just the data X to find the matrix W that lets you go back to recover the original sources S.
And the notation is that the matrix W I'm going to write as follows. Right I'm going to write the rows of W using this lower case. And so the original source I is equal to wi transpose X. I guess but every time I write it right, just you can take X multiply by the columns of this right and multiply by the rows of the matrix W which is why the rows of W allow you to recover the original sources.
So, all right. One last quick thing on PowerPoint and then we'll break. So, why is ICA even possible? Why do we think given this overlapping set of voices, why is it even possible to recover the original data? So, here's a visualization for why ICA might be possible. See, I'm realizing I need to plan one minute ahead or something because that's how long this thing takes to warm up. So it turns out that this is one figure to show why ICA may be possible which is let's say that the speaker sources, at each instant in time each speaker is emitting a random number between minus one and plus one. So if we were to plot the sources, notice the axes here are s1 and s2, the histogram of the speakers' voices would look like this if only you had access to the sources, which you don't. We only observe the X's, not the S's. And what the X's are is taking this data set and mapping it through a linear combination by that mixing matrix A. And so the data you will get looks like this, distribution of X1 and X2. And your job is to find an unmixing matrix W that lets you go back from this parallelogram shape to something like this where S1 and S2 are independent. Now there are two sources of ambiguity here. First is you don't know which one is S1 and which one is S2. If speaker one was a person and speaker two was a radio, there's no way that ICA could have known that one was a human and two was a radio rather than the other way around. One was a radio, two was a person. So there's one source of ambiguity for ICA is the axis ambiguity. You don't know which is S1, which is S2, which is S3. But that's okay, you can still recover the sources just maybe in some random sorted order. The second source of ambiguity is sign ambiguity. You don't know which is plus S1 and minus S1. So if you were to take this rectangle and flip it horizontally or flip it vertically, it still looks like the same rectangle. So at least at this level of abstraction, you may end up recovering negative of S rather than positive of S. And so but fortunately it turns out that when you run, if you take an audio clip and you take the negative of it and you play that through a speaker, it sounds pretty much the same. And so it turns out that for audio, even if you end up recovering negative of the sound source, if you play that through the speaker, it'll sound the same to your ear. And technically sound can only add. So technically there are versions of ICA because sound doesn't actually subtract, there's no, and so you can actually there's some versions of ICA that put some additional sign constraints on A and W because sound doesn't subtract, but in practice it doesn't matter. So in practice, whether you play the sound X or the sound S or the negative of that, it'll sound the same. So in most applications, we're quite happy recovering either the positive or the negative. It's not a big deal.
Oh. What's the subscript on S? Oh, I see. Sorry. Yes. This should be a J, I think. Yes. Oh. That was this is W. And then when I was saying W * X, I would add W * X. Yeah. Thanks.
Sure. Yeah. So is it necessary the number of speakers equal the number of microphones? For now for the initial development of the algorithm, let's just say yes and we'll come back and address this at the end of Wednesday. All right. I think we're running a little bit late. I think we can take more questions, but I'm just going to break on time. So let's break and then this is the ICA problem setup and on Wednesday we'll go through how you actually do this.
