# New course! Ensemble Machine Learning in Python: Random Forest and AdaBoost

December 25, 2016

This course is all about ensemble methods.

We’ve already learned some classic machine learning models like k-nearest neighbor and decision tree. We’ve studied their limitations and drawbacks.

But what if we could combine these models to eliminate those limitations and produce a much more powerful classifier or regressor?

In this course you’ll study ways to combine models like decision trees and logistic regression to build models that can reach much higher accuracies than the base models they are made of.

In particular, we will study the Random Forest and AdaBoost algorithms in detail.

To motivate our discussion, we will learn about an important topic in statistical learning, the bias-variance trade-off. We will then study the bootstrap technique and bagging as methods for reducing both bias and variance simultaneously.

We’ll do plenty of experiments and use these algorithms on real datasets so you can see first-hand how powerful they are.

Since deep learning is so popular these days, we will study some interesting commonalities between random forests, AdaBoost, and deep learning neural networks.

# New course! Bayesian Machine Learning in Python: A/B Testing

November 17, 2016

[If you already know you want to sign up for my Bayesian machine learning course, just scroll to the bottom to get your $10 coupon!] Boy, do I have some exciting news today! You guys have already been keeping up with my deep learning series. Hopefully, you’ve noticed that I’ve been releasing non-deep learning machine learning courses as well, in parallel (and they often tie into the deep learning series quite nicely). Well today, I am announcing the start of a BRAND NEW series on Bayesian machine learning. Bayesian methods require an entirely new way of thinking – a paradigm shift. But don’t worry, it’s not just all theory. In fact, the first course I’m releasing in the series is VERY practical – it’s on A/B testing. Every online advertiser, e-commerce store, marketing team, etc etc etc. does A/B testing. But did you know that traditional A/B testing is both horribly confusing and inefficient? Did you know that there are cool, new adaptive methods inspired by reinforcement learning that improve on those old crusty tests? (Those old methods, and the way they are traditionally taught, are probably the reason you cringe when you hear the word “statistics”) Well, Bayesian methods not only represent a state-of-the-art solution to many A/B testing challenges, they are also surprisingly theoretically simpler! You’ll end the course by doing your own simulation – comparing and contrasting the various adaptive A/B testing algorithms (including the final Bayesian method). This is VERY practical stuff and any digital media, newsfeed, or advertising startup will be EXTREMELY IMPRESSED if you know this stuff. This WILL advance your career, and any company would be lucky to have someone that knows this stuff on their team. Awesome coincidence #1: As I mentioned above, a lot of these techniques cross-over with reinforcement learning, so if you are itching for a preview of my upcoming deep reinforcement learning course, this will be very interesting for you. Awesome coincidence #2: Bayesian learning also crosses over with deep learning, one example being the variational autoencoder, which I may incorporate into a more advanced deep learning course in the future. They heavily rely on concepts from both Bayesian learning AND deep learning, and are very powerful state-of-the-art algorithms. Due to all the black Friday madness going on, I am going to do a ONE-TIME ONLY$10 special for this course. With my coupons, the price will remain at $10, even if Udemy’s site-wide sale price goes up (which it will). See you in class! As promised, here is the coupon: https://www.udemy.com/bayesian-machine-learning-in-python-ab-testing/?couponCode=EARLYBIRDSITE2 UPDATE: The Black Friday sale is over, but the early bird coupon is still up for grabs: https://www.udemy.com/bayesian-machine-learning-in-python-ab-testing/?couponCode=EARLYBIRDSITE LAST THING: Udemy is currently having an awesome Black Friday sale.$10 for ANY course starting Nov 15, but the price goes up by $1 every 2 days, so you need to ACT FAST. I was going to tell you earlier but I was hard at work on my course. =) Just click this link to get ANY course on Udemy for$10 (+\$1 every 2 days): http://bit.ly/2fY3y5M

#bayesian #data science #machine learning #statistics

# Announcing Data Science: Supervised Machine Learning in Python (Less Math, More Action!)

September 16, 2016

In recent years, we’ve seen a resurgence in AI, or artificial intelligence, and machine learning.

Machine learning has led to some amazing results, like being able to analyze medical images and predict diseases on-par with human experts.

Google’s AlphaGo program was able to beat a world champion in the strategy game go using deep reinforcement learning.

Machine learning is even being used to program self driving cars, which is going to change the automotive industry forever. Imagine a world with drastically reduced car accidents, simply by removing the element of human error.

Google famously announced that they are now “machine learning first”, meaning that machine learning is going to get a lot more attention now, and this is what’s going to drive innovation in the coming years.

Machine learning is used in many industries, like finance, online advertising, medicine, and robotics.

It is a widely applicable tool that will benefit you no matter what industry you’re in, and it will also open up a ton of career opportunities once you get good.

Machine learning also raises some philosophical questions. Are we building a machine that can think? What does it mean to be conscious? Will computers one day take over the world?

The best part about this course is that it requires WAY less math than my usual courses; just some basic probability and geometry, no calculus!

In this course, we are first going to discuss the K-Nearest Neighbor algorithm. It’s extremely simple and intuitive, and it’s a great first classification algorithm to learn. After we discuss the concepts and implement it in code, we’ll look at some ways in which KNN can fail.

It’s important to know both the advantages and disadvantages of each algorithm we look at.

Next we’ll look at the Naive Bayes Classifier and the General Bayes Classifier. This is a very interesting algorithm to look at because it is grounded in probability.

We’ll see how we can transform the Bayes Classifier into a linear and quadratic classifier to speed up our calculations.

Next we’ll look at the famous Decision Tree algorithm. This is the most complex of the algorithms we’ll study, and most courses you’ll look at won’t implement them. We will, since I believe implementation is good practice.

The last algorithm we’ll look at is the Perceptron algorithm. Perceptrons are the ancestor of neural networks and deep learning, so they are important to study in the context of machine learning.

One we’ve studied these algorithms, we’ll move to more practical machine learning topics. Hyperparameters, cross-validation, feature extraction, feature selection, and multiclass classification.

We’ll do a comparison with deep learning so you understand the pros and cons of each approach.

We’ll discuss the Sci-Kit Learn library, because even though implementing your own algorithms is fun and educational, you should use optimized and well-tested code in your actual work.

We’ll cap things off with a very practical, real-world example by writing a web service that runs a machine learning model and makes predictions. This is something that real companies do and make money from.

All the materials for this course are FREE. You can download and install Python, Numpy, and Scipy with simple commands on Windows, Linux, or Mac.

https://www.udemy.com/data-science-supervised-machine-learning-in-python/?couponCode=EARLYBIRDSITE

UPDATE: New coupon if the above is sold out:

https://www.udemy.com/data-science-supervised-machine-learning-in-python/?couponCode=SLOWBIRD_SITE

#data science #machine learning #matplotlib #numpy #pandas #python

# New machine learning course! Cluster Analysis and Unsupervised Machine Learning in Python

April 20, 2016

[Scroll to the bottom if you want to jump straight to the coupon]

Cluster analysis is a staple of unsupervised machine learning and data science.

It is very useful for data mining and big data because it automatically finds patterns in the data, without the need for labels, unlike supervised machine learning.

In a real-world environment, you can imagine that a robot or an artificial intelligence won’t always have access to the optimal answer, or maybe there isn’t an optimal correct answer. You’d want that robot to be able to explore the world on its own, and learn things just by looking for patterns.

Do you ever wonder how we get the data that we use in our supervised machine learning algorithms?

We always seem to have a nice CSV or a table, complete with Xs and corresponding Ys.

If you haven’t been involved in acquiring data yourself, you might not have thought about this, but someone has to make this data!

Those “Y”s have to come from somewhere, and a lot of the time that involves manual labor.

Sometimes, you don’t have access to this kind of information or it is infeasible or costly to acquire.

But you still want to have some idea of the structure of the data. If you’re doing data analytics automating pattern recognition in your data would be invaluable.

This is where unsupervised machine learning comes into play.

In this course we are first going to talk about clustering. This is where instead of training on labels, we try to create our own labels! We’ll do this by grouping together data that looks alike.

There are 2 methods of clustering we’ll talk about: k-means clustering and hierarchical clustering.

Next, because in machine learning we like to talk about probability distributions, we’ll go into Gaussian mixture models and kernel density estimation, where we talk about how to “learn” the probability distribution of a set of data.

One interesting fact is that under certain conditions, Gaussian mixture models and k-means clustering are exactly the same! You can think of GMMs as a “souped up” version of k-means. We’ll prove how this is the case.

All the algorithms we’ll talk about in this course are staples in machine learning and data science, so if you want to know how to automatically find patterns in your data with data mining and pattern extraction, without needing someone to put in manual work to label that data, then this course is for you.

All the materials for this course are FREE. You can download and install Python, Numpy, and Scipy with simple commands on Windows, Linux, or Mac.

#agglomerative clustering #cluster analysis #data mining #data science #expectation-maximization #gaussian mixture model #hierarchical clustering #k-means clustering #kernel density estimation #pattern recognition #udemy #unsupervised machine learning

# Covariance Matrix: Divide by N or N-1?

February 14, 2016

This is a statistics post. It’s probably very boring. I am posting it for my own reference, because I seem to forget how this is derived every time I need it.

Sometimes you see the sample variance defined as:

$$\hat{\sigma}^2 = \frac{1}{N} \sum_{n=1}^{N} (X_n – \mu)^2$$

But you might also see it defined as:

$$\hat{\sigma}^2 = \frac{1}{N-1} \sum_{n=1}^{N} (X_n – \hat{\mu})^2$$

Where as usual the “hat” symbol means that is our prediction.

Why do statisticians sometimes divide by N, and sometimes divide by N-1?

The same question arises for the calculation of the sample covariance matrix, and this is what we will work with in this post.

This has to do with whether you want your estimate to be a biased estimate or an unbiased estimate.

For any parameter $$\theta$$, our estimate $$\hat{ \theta }$$ is unbiased if:

$$E\{ \hat{ \theta } \} = 0$$

In this tutorial we will calculate the bias of the sample covariance on the multivariate Gaussian, which is defined as:

$$p(x | \mu, \sigma) = \frac{1}{\sqrt{(2\pi)^D |\Sigma|}} exp( -\frac{1}{2} (x – \mu)^T \Sigma^{-1} (x – \mu) )$$

The maximum likelihood estimates of $$\mu$$ and $$\Sigma$$ can be found by taking the derivative of the log-likelihood and setting it to 0.

The likelihood is:

$$p(X | \mu, \Sigma) = \prod_{n=1}^{N} p(x_n | \mu, \Sigma)$$

So the log-likelihood (expanded) is:

$$L(X | \mu, \Sigma) = -\frac{ND}{2} log(2\pi) -\frac{N}{2} log(|\Sigma|) -\sum_{n=1}^{N} \frac{1}{2}(x_n – \mu)^T \Sigma^{-1} (x_n – \mu)$$

To take “vector derivatives” and “matrix derivatives” you’ll want to consult the Matrix Cookbook.

If you made it this far it is almost trivial to calculate $$\frac{ \partial L }{ \partial \mu } = 0$$ to get the usual result:

$$\hat{ \mu } = \frac{1}{N} \sum_{n=1}^{N} x_n$$

To get the sample covariance, we calculate:

$$\frac{ \partial L }{ \partial \Sigma } = -\frac{N}{2} (\Sigma^{-1})^T – \frac{1}{2} \sum_{n=1}^{N} – \Sigma^{-T} (x_n – \mu) (x_n – \mu)^T \Sigma^{-T}$$

Set that t0 0 and solve for $$\Sigma$$ to get:

$$\hat{ \Sigma } = \frac{1}{N} \sum_{n=1}^{N} (x_n – \hat{\mu}) (x_n – \hat{\mu})^T$$

Note that we are assuming we don’t have the “true mean”, so we are estimating the mean using the maximum likelihood estimate before calculating the maximum likelihood estimate for the covariance.

Now we will show that $$E\{ \hat{ \Sigma } \} \neq 0$$. By definition:

$$E\{ \hat{ \Sigma } \} = \frac{1}{N} E\{ \sum_{n} (x_n – \hat{\mu})(x_n – \hat{\mu})^T \}$$

Expand:

$$E\{ \hat{ \Sigma } \} = \frac{1}{N} E\{ \sum_{n} ((x_n – \mu) – (\hat{\mu} – \mu))((x_n – \mu) – (\hat{\mu} – \mu)))^T \}$$

Expand that:

$$E\{ \hat{ \Sigma } \} = \Sigma + \frac{1}{N} E\{ \sum_{n} (\hat{\mu} – \mu)) (\hat{\mu} – \mu))^T – (x_n – \mu)(\hat{\mu} – \mu))^T – (\hat{\mu} – \mu))(x_n – \mu)^T \}$$

Multiply out the terms:

$$E\{ \hat{ \Sigma } \} = \Sigma + E\{ \hat{\mu}\hat{\mu}^T \} – \frac{1}{N} \sum_{n} E\{ x_n\hat{\mu}^T \} – \frac{1}{N} \sum_{n} E\{ \hat{\mu} x_n^T \} + \mu\mu^T$$

We can combine the expected values to get:

$$E\{ \hat{ \Sigma } \} = \Sigma + \mu\mu^T – E\{ \hat{\mu}\hat{\mu}^T \}$$

Now the exercise becomes finding the expected value.

We need some identities.

First, for $$m \neq n$$:

$$E\{ x_m x_n^T \} = E\{ x_m \} E\{ x_n^T \} = \mu\mu^T$$

Because each sample is IID: independent and identically distributed.

Next, the definition of covariance:

$$\Sigma = E\{ (x – \mu)(x – \mu)^T \} = E\{ xx^T \} – \mu\mu^T$$

We can rearrange this to get:

$$E\{ xx^T \} = \Sigma + \mu\mu^T$$

The term $$E\{\hat{\mu}\hat{\mu}^T \}$$ can be expanded as:

$$E\{\hat{\mu}\hat{\mu}^T \} = \frac{1}{N^2} E\{ (x_1 + x_2 + … + x_N)(x_1 + x_2 + … + x_N)^T \}$$

When expanding the multiplication, there are $$N$$ terms that are the same, so that would be a $$N E\{ x_n x_n^T \}$$ contribution. There are $$N(N-1)$$ terms that are different, and since different terms are independent that is a $$N(N-1)\mu\mu^T$$ contribution.

So in total:

$$E\{\hat{\mu}\hat{\mu}^T \} =\frac{1}{N^2}(N(\Sigma + \mu\mu^T) + N(N-1)\mu\mu^T)$$

Or:

$$E\{\hat{\mu}\hat{\mu}^T \} = \frac{1}{N}\Sigma + \mu\mu^T$$

Plugging this back into the expression for the bias:

$$E\{ \hat{ \Sigma } \} = \Sigma + \mu\mu^T – \frac{1}{N}\Sigma – \mu\mu^T$$

Or:

$$E\{ \hat{ \Sigma } \} = \frac{N-1}{N} \Sigma \neq \Sigma$$

So, if you want the unbiased estimator, you can multiply the biased maximum likelihood estimator by $$\frac{N}{N-1}$$, which gives the expected unbiased formula.

#covariance #maximum likelihood #MLE #multivariate Gaussian #multivariate normal #sample variance #statistics #unbiased estimator

# What the hell is a “z-score”?

December 4, 2015

Was having this conversation recently about what a z-score is.

What is a z-score? Why is it mentioned so often in statistics? You’ve probably heard of it in the context of the Student t-test.

If you are a machine learning guy more than a statistics guy, like me, you’ve probably heard you should “standardize” or “normalize” your variables before putting them into a machine learning model.

For example, if you’re doing linear regression and $$X_1$$ varies from $$0..1$$ and $$X_2$$ varies from $$0..1000$$, the weights $$\beta_1$$ and $$\beta_2$$ will give an inaccurate picture as to their importance.

Well, the z-score actually is the standardized variable.

I would avoid this terminology if possible, because in machine learning we usually think of a “score” as the output of a model, i.e. I’m getting the “score” of a set of links because I want to know in what order to rank them.

$$z = \frac{x – \mu}{\sigma}$$

So instead of thinking of “z-scores”, think of “I need to standardize my variables before using them in my machine learning model so that the effect of any one variable is on the same scale as the others”.

Do you find statistics terminology confusing? “Z score”? “F statistic”? Share your thoughts in the comments!

#frequentist statistics #machine learning #statistics #z score

# Tutorial: Principal Components Analysis (PCA)

November 20, 2015

I remember learning about principal components analysis for the very first time. I remember thinking it was very confusing, and that I didn’t know what it had to do with eigenvalues and eigenvectors (I’m not even sure I remembered what eigenvalues and eigenvectors were at the time).

I assure you that in hindsight, understanding PCA, despite its very scientific-sounding name, is not that difficult to understand at all. There are two “categories” I think it makes sense to split the discussion of PCA into.

1) What does it do? A written and visual description of how PCA is used.

2) The math behind PCA. A few equations showing that the things mentioned in (1) are true.

### What does PCA do?

Linear transformation

PCA finds a matrix $$Q$$ that, when multiplied by your original data matrix $$X$$, gives you a linearly transformed data matrix $$Z$$, where:

$$Z = XQ$$

In other words, for a single sample vector $$x$$, we can obtain its transformation $$z = Qx$$.

The $$Q$$ and $$x$$ appear in a different order here because when we load a data matrix, it’s usually $$N \times D$$, so each sample vector is $$1 \times D$$, but when we talk about vectors by themselves we usually think of them as $$D \times 1$$.

The interesting thing about PCA is how it chooses $$Q$$.

Dimensionality reduction

When we think of machine learning models we often study them in the context of 1-3 dimensions. But if you take a dataset like MNIST, where each image is 28×28 pixels, then each input is 784 dimensions. 28×28 is a tiny image. The new iPhone 6 has a resolution of 1080 × 1920 pixels. Each image would thus have 2073600 $$\approx$$ 2 million dimensions.

PCA reduces dimensionality by moving as much “information” as possible into as few dimensions as possible. We measure information via unpredictability, i.e. variance. The end result is that our transformed matrix $$Z$$ has most of its variance in the first column, less variance in the second column, even less variance in the third column, etc.

You will see later how our choice of $$Q$$ accomplishes this.

De-correlation

$$D \approx 2000000$$ is a much bigger problem than the ones you learn about in the classroom. But often there are correlations in the data that make many of the dimensions redundant. This is related to the problem of linear regression – if we can accurately predict one dimension of the inputs, let’s say, $$x_3$$, in terms of another, $$x_5$$, then one of those dimensions is redundant.

The final result of removing these correlations is that every dimension of $$Z$$ is uncorrelated with the other.

The image above shows a scatterplot of the original data on the original x-y axis. The arrows on the plot itself show that the new v1-v2 axis is a) rotated (matrix multiplication rotates a vector) b) still perpendicular, and c) the data relative to the new axis is normally distributed and the distributions on each dimension are independent and uncorrelated.

Visualization

Once we’ve transformed $$X$$ into $$Z$$, noting that most of the “information” from $$X$$ is in the first few dimensions of $$Z$$ – let’s say… 90% of the variance is in the first 2 dimensions – we can do a 2-D scatterplot of Z to see the structure of our data. Humans have a hard time visualization anything greater than 2 dimensions.

We can consider the first 2 dimensions to represent the real underlying trend in the data, and the other dimensions just small perturbations or noise.

Pre-processing

You may have heard that too many parameters in your model can lead to overfitting. So if you are planning to use a logistic regression model, and the dimensionality of each input is 2 million, then the number of weights in your model will also be 2 million. This is not good news if you have only a few thousand samples. One rule of thumb is we would like to have 10x the number of samples compared to the number of parameters in our model.

So instead of going out and finding 20 million samples, we can use PCA to reduce the dimensionality of our data to say, 20, and then we only need 200 samples for our model.

You can also use PCA to pre-process data before using an unsupervised learning algorithm, like k-means clustering. PCA, by the way, is also an unsupervised algorithm.

### The math behind PCA

Everybody’s favorite part!

Ok, so this requires both (a) some statistics knowledge (knowing how to find the covariance matrix), and (b) some linear algebra knowledge (knowing what eigenvalues and eigenvectors are, and basic matrix manipulation).

Covariance

I stated above that in the rotated v1-v2 coordinate system, the data on the v1 axis was not correlated with the data on the v2 axis.

Intuitively, when you have a 2-D Gaussian distribution, the data looks like an ellipse. If that ellipse is perpendicular to the x-y grid, then the x and y components are independent and uncorrelated.

The image below shows what happens with different values of the correlation between $$X_i$$ and $$X_j$$ (called ‘c’ in the image):

(If you really know your statistics, then you will recall that independence implies 0 correlation, but 0 correlation does not imply independence, unless the distribution is a joint Gaussian.)

So, in the first image, since the ellipse is not perpendicular to the x-y axis, the distributions p(x) and p(y) are not independent. But in the rotated v1-v2 axis, the distributions p(v1) and p(v2) are independent and uncorrelated.

If this all sounds crazy, just remember this one fact: if 2 variables $$X_i$$ and $$X_j$$ are uncorrelated, their corresponding element in the covariance matrix, $$\Sigma_{ij} = 0$$. And since the covariance matrix is symmetric (for our purposes), $$\Sigma_{ji} = 0$$ also.

For every variable to be uncorrelated to every other variable, all the elements of $$\Sigma$$ will be 0, except those along the diagonal, $$\Sigma_{ii} = \sigma_i^2$$, which is just the regular variance for each dimension.

How do we calculate the covariance matrix from the data? Simple!

$$\Sigma_X = \frac{1}{N} (X – \mu_X)^T(X – \mu_X) \tag{1}$$

In non-matrix form this is:

$$\Sigma_{ij} = \frac{1}{N} \sum_{n=1}^{N} (x(n)_i – \mu_i)(x(n)_j – \mu_j)$$

I’ve labeled the equation because we’re going to return to it. You can verify that $$\Sigma$$ is $$D \times D$$ since those are the outer dimensions of the matrix multiply.

Note the mathematical sleight of hand I used above. $$X$$ is $$N \times D$$ and the mean $$\mu_X$$ is $$1 \times D$$, so technically you can’t subtract them under the rules of matrix algebra, but let’s assume that the above notation means each row of $$X$$ has $$\mu_X$$ subtracted from it.

Eigenvalues and Eigenvectors

This is where the real magic of PCA happens.

For no particular reason at all, suppose we compute the eigenvalues and eigenvectors of $$\Sigma_X$$.

If you don’t know what eigenvalues/eigenvectors are: remember that usually, when we multiply a vector by a matrix, it changes the direction of the vector.

So for example, the vector $$(1,2)$$ is pointing in the same direction as $$(2,4) = 2(1,2)$$. But if we were to multiply $$(1,2)$$ by a matrix:

$$\begin{pmatrix} 5 \\ 11 \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} \begin{pmatrix} 1 \\ 2 \end{pmatrix}$$

The result is a vector in a different direction. Eigenvalues $$\lambda$$ and eigenvectors $$v$$ have the property that, if you multiply $$\Sigma_Xv$$, this is the same by multiplying the eigenvector by a constant – the eigenvalue, i.e. the eigenvector does not change direction, it only gets shorter or longer by a factor of $$\lambda$$. In other words:

$$\Sigma_Xv = \lambda v$$

How many pairs of these eigenvectors and eigenvalues can we find? It just so happens that there are $$D$$ such pairs. We’ll say, each eigenvalue $$\lambda_i$$ has a corresponding eigenvector $$v_i$$.

Now again, for no particular reason at all, we are going to combine all the $$v_i$$ into a matrix, let’s call it $$V$$.

We could line up the $$v_i$$ in any random order, but instead we are going to choose a very particular order – we are going to line them up such that the corresponding eigenvalues $$\lambda_i$$ are in descending order. In other words:

$$\lambda_1 > \lambda_2 > \lambda_3 > … > \lambda_D$$

So:

$$V = \begin{pmatrix} | & | & | & … & | \\ v_1 & v_2 & v_3 & … & v_D \\ | & | & | & … & | \end{pmatrix}$$

We are also going to combine the eigenvalues into a diagonal matrix like this:

$$\Lambda = \begin{pmatrix} \lambda_1 & 0 & … & 0 \\ 0 & \lambda_2 & … & 0 \\ … & … & … & … \\ 0 & 0 & … & \lambda_D \end{pmatrix}$$

As a sidenote, don’t worry about how we find the eigenvalues and eigenvectors. That is a huge problem in and of itself. The method you used in high school – solving a polynomial to get the eigenvalues, plugging the eigenvalues into the eigenvalue equation to get the eigenvectors, etc. doesn’t really translate to computer code. There exist some very involved algorithms to solve this problem, but we’ll just use numpy.

In any case, it is easy to prove to yourself, with a simple 2-D example, that:

$$\Sigma_X V = V \Lambda \tag{2}$$

Just one more ingredient. We want to show that $$V$$ is orthonormal. In terms of the individual eigenvectors this means that $${v_i}^T v_j = 0$$ if $$i \ne j$$, and $${v_i}^T v_i = 1$$. In matrix form this means $$V^T V = I$$, or in other words, $$V^T = V^{-1}$$.

Proof of orthogonality: Consider $$\lambda_j {v_i}^T v_j$$ for $$i \ne j$$. $$\lambda_j {v_i}^T v_j = {v_i}^T (\lambda_j v_j) = {v_i}^T \Sigma_X v_j = (\Sigma_X^T v_i)^T v_j$$. But we know that $$\Sigma_X$$ is symmetric so this is $$(\Sigma_X v_i)^T v_j = (\lambda_i v_i)^T v_j = \lambda_i {v_i}^T v_j$$. Since $$\lambda_i \ne \lambda_j$$, this can only be true if $${v_i}^T v_j = 0$$.

Normalizing eigenvectors is easy since they are not unique – just choose values so that their length is 1.

Finally, using $$(1)$$, consider the covariance of the transformed data, $$Z$$.

\begin{align*} \Sigma_Z &= \frac{1}{N} (Z – \mu_Z)^T (Z – \mu_Z) \\ &= \frac{1}{N} (XQ – \mu_XQ)^T (XQ – \mu_XQ) \\ &= \frac{1}{N} Q^T(X – \mu_X)^T (X – \mu_X)Q \\ &= Q^T \Sigma_X Q \end{align*}

Now, suppose we choose $$Q = V$$. Then, by plugging in $$(2)$$, we get:

\begin{align*} \Sigma_Z &= V^T \Sigma_X V \\ &= V^T V \Lambda \\ &= \Lambda \end{align*}

So what does this tell us? Since $$\Lambda$$ is a diagonal matrix, there are no correlations in the transformed data. The variance of each dimension of $$Z$$ is equal to the eigenvalues. In addition, because we sorted the eigenvalues in descending order, the first dimension of $$Z$$ has the most variance, the second dimension has the second-most variance, etc. So most of the information is kept in the leading columns, as promised.

You can verify this in Python:

import numpy as np
from sklearn.decomposition import PCA
import matplotlib.pyplot as plt

pca = PCA()
X = np.random.random((100,10)) # generate an N = 100, D = 10 random data matrix
Z = pca.fit_transform(X)

# visualize the covariance of Z
plt.imshow(np.cov(Z.T))
plt.show()


Observe that the off-diagonals are 0 and that the variances are in decreasing order.

You can also confirm that $$Q^T Q = I$$.

QTQ = pca.components_.T.dot(pca.components_)
plt.imshow(QTQ)
plt.show()

print np.around(QTQ, decimals=2)


Remember to leave a comment below if you have any questions on the above material. If you want to go more in depth on this and other data science topics (both with the math and the code), check out some of my data science video courses online.

#anomaly detection #covariance #dimensionality reduction #eigenvalues #eigenvectors #linear algebra #machine learning #pca #principal components analysis #statistics

# Linear regression video course in Python

November 11, 2015

Hi all!

Do you ever get tired of reading walls of text, and just want a nice video or 10 to explain to you the magic of linear regression and how to program it with Python and numpy?

Look no further, that video course is here.

#linear regression #numpy #python #statistics

# Tutorial: K-Nearest Neighbor classifier for MNIST

March 20, 2015

Previously we looked at the Bayes classifier for MNIST data, using a multivariate Gaussian to model each class.

We use the same dimensionality reduced dataset here.

The K-Nearest Neighbor (KNN) classifier is also often used as a “simple baseline” classifier, but there are a couple distinctions from the Bayes classifier that are interesting.

1) KNN does not use probability distributions to model data. In fact, many powerful classifiers do not assume any probability distribution on the data.

2) KNN is a “lazy” classifier. No work is actually done to train the model. It just saves the input points X and all the labels Y.

At classification time, the predicted class/label is chosen by looking at the “k nearest neighbors” of the input test point.

We choose “k” beforehand.

Here is a visual example for k = 3:

So for 3-NN, we go through all the training points, find the 3 closest ones, and choose the label that shows up the most.

i.e. If we get 2 whites and 1 black, we choose white. This is called “voting”.

Here is another example, where we might get a different answer depending on whether k = 3 or k = 5.

The idea is, our data should be clustered in “space”. Points from the same class should be near each other. In fact, this is an idea that prevails for pretty much all machine learning algorithms, so you should understand it well.

If data points that are near each other are from the same class, then it follows that a test point can be classified by looking at its neighbors’ classes.

In pseudocode, it might look like this:

function predict(x’):
Q = [] // we’ll use this to store the k-nearest neighbors
for x,y in training data:
if Q.length < k or dist(x,x’) < max distance in Q:
add dist(x,x’) and y to Q
if Q.length > k: remove max distance in Q
return the y that shows up most in Q

A naive implementation might look through every training point, which is O(N), and then to find the max in Q it would be O(k), for a total of O(kN).

You could use a sorted data structure for Q making the search and insert O(logk).

Here is the pseudocode that does this:

https://github.com/lazyprogrammer/machine_learning_examples/blob/master/knn.py

k = 1 achieves a test classification rate of 94.8%!

#bigdata #data science #k-nearest neighbors #knn #machine learning

# Bayes classifier and Naive Bayes tutorial (using the MNIST dataset)

March 19, 2015

The Naive Bayes classifier is a simple classifier that is often used as a baseline for comparison with more complex classifiers.

It is also conceptually very simple.

We will use the famous MNIST data set (pre-processed via PCA and normalized [TODO]) for this tutorial, so our class labels are {0, 1, …, 9}.

Recall Bayes rule:

P(C|X) = P(X|C)*P(C) / P(X)

If you’re like me, you may have found this notation a little confusing at first.

We can read the left side P(C|X) as “the probability that the class is C given the data X”. (this is called the “posterior”)

We can read the right side P(X|C) as “the probability that the data X belongs to the class C”. (this is called the “likelihood”)

Some housekeeping can be done to make our analysis simpler:

1. We have an equal number of samples for each class, so P(C) = 1/10 always.

2. P(X) is constant for every class C, so we can leave that out also.

Now we get this simpler equation:

And we can compute the probability that the class = 0 given the data, probability that the class = 1 given the data, etc. just by computing the probability of the data for each class (how well the data fits a model of each class).

The class chosen is simply the one that yields the highest probability for that data:

This makes a lot of sense. Once we’ve created a model for each class, and we want to predict the class for a test point, we just choose the class that the test point best fits.

The challenge is choosing a model that accurately fits the data.

Great assumptions are made in order to make the problem tractable and easily computable.

For this problem (MNIST images) we will assume the data is multivariate Gaussian.

Note that because the data are continuous, we are not actually calculating probabilities, but probability densities, on the right for P(X|C).

Another thing to note is that because probabilities are very small when dimensionality is high, we’ll work with log-likelihood instead of likelihood. Then instead of getting numbers very close to 0, which is inaccurate when using a computer to represent them, we’ll just get negative numbers.

The log-likelihood can be represented as:

Which you should try to derive yourself. (k is the dimensionality)

Now this problem is tractable.

Training the classifier would work as follows:

For each class = 0..9
get all x’s for the class
save the mean and covariance of those x’s with the class

Prediction using the classifier would work as follows:

Given a test point x
Calculate the probability that x is in each class C
Return the class that yields the highest probability

What makes a Bayes classifier a Naive Bayes classifier?

So far we have only discussed general Bayes classifiers.

A Naive Bayes classifier is one that assumes all dimensions are independent.

So if the vector x = (x1, x2, …, x20)

x1 is independent of x2, and x3, and so on…

This means the covariance matrix only has non-zero elements along the diagonal, which are just the variances at each dimension.

For this particular example (Gaussian) it means we can compute the matrix determinant (just take the sum) and the matrix inverse more easily.

Visually, we can “see” each model by plotting the mean (the most likely value).

If we reconstruct the images by reversing the PCA transform, here are the plots you’d get:

The code for this tutorial can be found here:

https://github.com/lazyprogrammer/machine_learning_examples/blob/master/bayes.py

To reproduce the visualizations run:

python bayes.py reconstruct

We get 93.6% accuracy on the test set, which is pretty good!

#bayes #big data #data science #machine learning #naivebayes