Stanford Machine Learning Week 10 review

What is the problem with learning with large dataset?

When training the parameters with a large dataset, such as 100 million training examples or even more, we may not be able to fit all training example into memory. However, we do need all the training examples to calculate partial derivatives for all the parameters. That means, for each step of gradient descent, we have to calculate the next θ value by accumulating the h(θ) - y of all the training examples. How can we deal with that if the training example is too large to fit into memory?

Three solutions

• Stochastic Gradient Descent
• Mini-Batch Gradient Descent (may be more efficient)
• Map Reduce (multiple machines)

Stochastic Gradient Descent

Each update of θ is calculated by only one training example. Stochastic gradient descent is much faster than Batch gradient descent. Each baby step -update θ values - of Batch gradient descent uses all training examples, whereas each baby step of Stochastic gradient descent uses only one training example. But one caveat here is that even though the baby steps of Stochastic gradient descent will generally move the parameters in the direction of the global minimum, but not always. In fact as you run Stochastic gradient descent it doesn't actually converge in the same sense as Batch gradient descent does, and what it ends up doing is wandering around continuously in some region that's close to the global minimum, but it doesn't just get to the global minimum and stay there. In practise, it isn't a problem though since it will be a pretty good hypothesis.

Stochastic gradient descent convergence

We can plot a learning curve to check if the our stochastic gradient descent is converging when more and more iterations. The x-axis is the number of iterations, and the y-axis is the cost function. As we can see in the top-left figure, we get a slightly better result when we use a smaller learning rate. The top-right figure shows we get a more smoothy curve when calculating the cost function every 5000 iterations instead of every 1000 iterations. The bottom-right figure shows if the learning rate is too large, the learning curve might end up diverging.

Mini-Batch Gradient Descent

It's just another variation of stochastic gradient descent. Instead of calculating one training example at a time, it calculates multiple (mini batch) training examples. Mini-batch gradient descent is likely to outperform Stochastic gradient descent only if you have a good vectorised implementation, paralleling your computation. 

Map Reduce

All learning algorithms that can be expressed as a summation over the training set can apply Map Reduce in order to speed up the computation. By paralleling the computation over different computers. So whether it's Linear Regression, Logistic Regression, or Neural Network, they can all apply map reduce. For example, if we have 400 million training examples, we can partition them into 4 computers and each computer calculates one fourth of the training examples, before another machine combines the 4 results together to calculate the partial derivative.

What is Online Learning?

When you can continuously have streams of new training examples and you don't want to save all the previous training examples because you constantly have new data. Then you can use Online learning. It continuously (forever) calculate the stochastic gradient descent.

Continue reading →

Stanford Machine Learning Week 9 review

What is Anomaly Detection?

Given a bunch of x's (where each x is a vector - a training example), detect whether for a new example x (a new vector), possibility p(x) < ε (epsilon). If yes, it is considered an anomaly; otherwise, it is considered normal.

What is Gaussian (Normal) distribution?

Gaussian distribution is defined as X ~ N(μ, σ^2), where μ (pronounced mu) is the mean of x; σ (pronounced sigma) is the standard deviation; σ^2 is the variance.

Anomaly Detection Algorithm

p(x;μ,σ^2) uses Gaussian distribution to plot the function of x for given a fixed value of mu and of sigma squared.

 

Recommender Systems: Collaborative Filtering Algorithm

Collaborative Filtering Algorithm is based on linear regression. We can think of each movie has its features: x1, x2, ..., xn. x1 may represent how romance the movie is, x2 may represent how action the movie is, etc. Then if the user has rated enough movies ( 1<= the rating y <= 5), we can use linear regression to predict hθ(x), given the features of a movie.

Learning features

Not only we can learn the thetas of each user, we can even learn the value of features of each movie automatically by using Collaborative Filtering Algorithm.

Given a dataset that consists of a set of ratings produced by some users on some movies, you wish to learn the parameter vectors x(1),...,x(nm),θ(1),...,θ(nu) that produce the best fit (minimizes the squared error).

Continue reading →

Stanford Machine Learning Week 8 review

What is Unsupervised Learning?

Supervised Learning is to learn the weights from training examples with answers.Unsupervised Learning does not have such answers in the training examples.

What is K-Means Algorithm?

K-Means Algorithm is one of the supervised learning algorithm, to automatically find K clusters from the training points. It repeats the two steps iteratively until arrives at the optimal situation.

1. Clustering assignment : assign each point (each training example) to a cluster centroid
2. Move centroid : move centroid to the average position of all points belonging to it

A few things to pay attention to when implementing K-Means Algorithm

• Always normalise the features (zero-mean, better scaling)
• Local optimal is possible, depending on the initial K centroids used. Therefore, we should randomly initialise the K centroids many times and choose the one with the minimum cost function
• Choosing the K number: Elbow Method is not always good. It is better to choose the K number that best serves the downstream purpose.

Dimension Reduction Motivation

By working with lower dimensional data, we have the following advantages:

• Our learning algorithms can often run much much faster
• Use less memory or disk space
• Visualise data in a 2D plot if k = 2, or in a 3D plot if k = 3

 

PCA (Principle Component Analysis) algorithm

PCA finds a low dimensional "surface" onto which to project the training examples so that the sum of the projection errors is minimised.

Projection error means the projection distance which is the distance between points (All training examples X) and the projections.
Think about each training example x as a point in a 3D space, and the "surface" as a 2D plane in the 3D space, the distance of the projection from the point x onto the 2D plane is the projection error (projection distance).

Let's say we have an n-dimensional training example, and we want to reduce it to a k-dimensional training example.
The PCA will find k vectors - u(1), u(2), ..., u(k), which will define the "surface".
u(1) .. u(k) are called eigenvectors or principal components.

How to reduce a training example from n dimension to k dimension?

X the training set, is an n*m matrix

1. Sigma = (1/m)*X'*X, the covariance matrix
2. [U,S,V] = svd(Sigma), take the U, n*n matrix, which are the eigenvectors (the principle components)
3. Ureduce = U(:, 1:k), meaning take the first k columns of U, name it Ureduce, a n*k matrix
4. z = Ureduce'*x transform each training example x into a k dimensional vector

Reconstruction from Compressed Representation

One can easily reconstruct each training example x (n-dimensional) from the compressed representation (k-dimensional) using xapprox = Ureduce*z

How to choose k (number of principal components)?

Choose a (smallest value of) k so that "99% of variance is retained". Yes, we should try to retain as much variance as possible.

Is it possible to apply the mapping x -> z to cross validation and test set?

Yes, you should apply the same mapping x -> z you get from running PCA on the training set.

Caveat

Do not do PCA systematically in your ML system design, only apply PCA when your learning algorithm runs too slow. 

Dimension Reduction showcase

On the left side of the following figure is the original features, each training example (face) is represented by 1024 pixels. When choosing only 100 principal components (reduction of factor of 10), we reduce the dimension of each training example from 1024 to 100. On the right side of the figure is the reconstructed features. Even some informations are lost by dimension reduction, the faces are still recognisable and we 10 times less features to compute.

The eigenvectors

Each of the following faces represents an eigenvector. Each eigenvector transforms one original 1024 dimensional (pixel) training example to 1 pixel of the 100 dimensional (pixel) reduced training example. The figure shows only the first 36 principle components:

Continue reading →

Stanford Machine Learning Week 7 review

What is SVM (Support Vector Machine)?

SVM is like logistical regression. It has the same way to solve z, which is ϴ'*X.

The difference is the cost function. SVM's cost function is two simple straight lines for y == 1; and symmetrically, two other straight lines for y == 0.

This is computationally more efficient. It also makes effort to make θ'*x ≥ 1 when y = 1 (not merely making θ'*x ≥ 0 ), and make tθ'*x ≤ -1 when y = 0 (not merely making θ'*x ≤ 0).

By solving the minimization of (this modified version of) cost function SVM, thanks toLarge Margin Technique, we can draw a linear line (if features are not polynomial), we will get the final ϴ, separating the positives (h=1) and negatives(h=0) for classification problem.

What is Large Margin?

With Large Margin, we can draw a line that separates the positive points from the negative points. Large Margin guaranties to have a large minimum length of projection from each point to that boundary line. 

What is Vector Inner Product?

If we have two vectors: u = [u1 u2] v = [v1 v2]. One way to calculate the inner product is u'*v, which is u1*v1 + u2*v2.

Another way to calculate the inner product is based on geometry:
The normal or (euclidean) length of vector u, ||u|| is sqrt(u1^2 + u2^2). It's like when we project u1, u2 into axis x (x = u1), and axis y (y = u2), then calculate the Pythagoras theorem. Draw vector v in the axis x and axis y, do a orthogonal projection from v to u and get the length of p (from the origin (0,0) to the orthogonal point), p is signed and could be negative, finally the inner production = p*||u||.

Apply Vector Inner Product to minimise the cost function, to get the Large Margin Decision Boundary

We can rewrite the cost function of SVM in a way that uses Vector Inner Product. In order to minimise the cost function, Vector Inner Product chooses a decision boundary that has the largest margin.

What are Kernels?

We use a kernel in order to develop complex nonlinear classifiers. Without a kernel (sometimes we call it a linear kernel), we can only develop linear classifiers. SVM is about the cost function, whereas Kernel is about the hypothesis function.

How to use Kernels in a hypothesis function?

Without kernel, we would write a polynomial hypothesis function. We can replace the polynomial hypothesis function x's by f's. The f's are the result of kernel. Gaussian Kernel is the most popular kernel that calculates the similarity of two vectors; it returns 1 when two vectors are very similar, and returns 0 when two vectors are very different. Each training example is a n-dimensional vector. We have m vectors in the training set. We can learn parameters θ so that when a vector is similar to certain other vectors, the hypothesis function > 0.

SVM, Logistic Regression, or Neural Network?

It's not alway obvious to make a choice of the learning algorithm when solving classification problem. Here's a recommended best practice guide:

Questions

Does it change the hypothesis function of SVM compared to the hypothesis function of Logistic Regression? Why?

It seems - to be verified - that the hypothesis function of SVM becomes:
h = 1, when theta-transpose*x ≥ 0
h = 0, when theta-transpose*x ≤ 0

Continue reading →

Stanford Machine Learning Week 6 review

How to choose the number of layers in neural network?

The best default strategy is to choose to use one hidden layer. The more hidden layers you have, the more prone you'll have high variance problems. But having too few layers makes the neural network prone to high bias problem. A practical strategy is to increment the number of layers - it's like adding polynomial features or decreasing lambda λ in normal cost function to fix high bias problem - and get the Θ for the neural network. Then use the Θ to calculate the cost function of cross validation. Choose the Θ ( also number of layers) that has the minimum cost function of cross validation.

What's Learning Curve?

Learning Curve shows whether you have a high variance or high bias problem. The horizontal axis represents m : the training set size; the vertical axis represents the errors (training error and cross validation error).

High Bias

When m increases, training error and cross validation error converge and keeps high.

High Variance

When m increases, training error and cross validation error also converge, but there's a gap between training error and cross validation error and adding new training data helps.

Good practice when plotting learning curves with small training sets: It's often helpful to average across multiple sets of randomly selected examples to determine the training error and cross validation error. For example, for m = 10, randomly choose 10 examples from training set and 10 examples from cross validation set, the calculate the training error and cross validation error. Do this for 50 times to get the average training error and cross validation error for m = 10.

What's Training Set, Cross Validation Set, and Test Set?

A good (supervised learning) practice is to divide the data into 3 groups:

• Training Set : Learn the model parameters θ
• Cross Validation Set : Select the regularzation λ parameters to find tradeoff between high bias and high variance
• Test Set : Evaluate the "final" model

Recommended approach to develop a learning algorithm

1. Start with a very simple, quick-and-dirty algorithm that you can implement quickly. Implement it and test it against your cross validation data.
2. Plot learning curves to decide if more data, more features are likely to help.
3. Error analysis: Manually examine the examples (in cross validation data) that your algorithm made errors on. See if you can spot any systematic trend in what types of examples it is making errors on. For example, for a mail spam classification problem, you could manually examine (1) What type of email it is - Pharma, Replica, Stealing Password? If most of the cross validation error is related to emails of Stealing Password, then it's worth spending some time to see if you can come up with better features to categorise Stealing Password spam more correctly. (2) What features you think would have helped the algorithm classify them correctly. Finally, ALWAYS TEST your assumption again cross validation data. 

What are Precision and Recall, and when are they useful?

When solving classification problems, such as Cancer classification, we might be proud to see that we got 1% error on test set (99% correct diagnoses). But wait, only 0.50& of patients have cancer. If we had a "cheat" version of hypothesis predicting all patients don't have cancer, we would have 99.5% correct diagnoses. But by using "cheat" version, we are not actually improving our predicting algorithm, even though we have a better accuracy. This situation happens when we have skewed classes. 

Precision and Recall come to rescue

Precision : Of all patients where we predicted True (having cancer), what fraction actually has cancer. In the figure below, the denominator is the first row (all predicted True).

Recall : Of all patients having cancer, what fraction did we correctly predict as having cancer? In the figure below, the denominator is the first column (all actual True).

The "cheat" version would have 0 as recall, as it predicts all patients not having cancer: recall = zero/non-zero = 0. So we would find out the "cheat" version is not improving our algorithm.

Trading off precision and recall

When using logistic regression, we set a threshold for hθ(x). If threshold is 0.5, we predict 1 if hθ(x) > 0.5, and we predict 0 if hθ(x) < 0.5.

Suppose we want to predict y = 1 (cancer) only if very confident, we do not want to scare patients. We would set the threshold high, which results in higher precision and lower recall.

But if we want to be more preservative and avoid missing too many cases of cancer, we would set the threshold low, which results in higher recall and lower precision.

When does using a large training set makes sense?

It only makes sense when we have a low bias algorithm - algorithm with (1) many useful features and (2) many parameters θ. In this case, increasing training set size will help fix overfitting problem and training error will be closer to cross validation error. If features x do not contain enough information to predict y accurately (such as predicting a house's price from only its size), even if we are using a neural network with a large number of hidden units, it won't work. We can ask ourself whether features x contain enough information by imagining if we have a human expert look at the features x, can he/she confidently predict the value of y. Simply looking at a house's size, even a realtor cannot confidently predict the price. He/She has to have more informations: number of rooms, which part of city, etc.

Questions?

When features (e.p. polynomial of degree 8: x=40, x8 = too big) are badly scaled, we need to normalise the features. How do we do feature normalisation? What is mu, sigma? Do some further readings and earlier lectures reviews.

Continue reading →

Stanford Machine Learning Week 5 review

I just finished the 5th week of Stanford Machine Learning course:Neural Networks: Learning. Since this week's course is a little bit difficult. I thought I might as well write something as a reminder, so that I could look back in the future.

I do feel that it is a powerful way to predict the outcome when there's enough training data, hidden layers and intermediate neurons. A simple and practical neural network would consist of three layers: input layer, hidden layer, and output layer. Actually, one of the first versions of self-driving car was built on a three-layer neural network.

The forward propagation is straightforward and intuitive. On the other hand, it's a bit difficult for me to grasp the concept of back propagation. The good news is that I somehow managed to understand the implementation.

The Neural Network Learning Algorithm on a high level

• Calculate the cost function, given multiple matrices of thetas* (one matrice per layer). In the end, we should have a cost given thetas. The cost represents how "far" our prediction is from the "reality".
• Calculate the gradient (a.k.a. partial derivative) for each given theta. In the end, we should have a concrete numerical gradient value for each given theta. The back propagation take place on this step.
• With the ability to calculate the cost, and gradient for each theta, we can use one of the optimised functions such as fminunc (or gradient descent) to do the following iteration: random initial thetas --> calculate cost and gradients --> update thetas --> less cost and new gradients --> update thetas --> less cost and new gradients --> ... ---> until we get the minimum cost. This is a glorious moment when we get the optimised thetas, which allows the neural network to do the most accurate prediction.

*theta is the weight of X, whereas X is the feature vector used to predict outcome.

 

Questions

Though I finished the assignment of this week, there are still some parts that I need to do more research on to understand better:

• What exactly does δ (delta) represent in back propagation?
• Why do we use derivative sigmoid function g'(z) to calculate the δ (delta) from last layer back to the hidden layers?
• Why δ(l+1)*(a(l))T is the gradient (a.k.a. partial derivative) matrice at l layer?

Accomplishment

• Built a neural network that recognises 1 - 9 digital number imagines with 96% accuracy.
• Visualized hidden layer images, each of which represents a row of theta in the input layer, who calculates one neuron in the hidden layer. There are 25 neurons in the hidden layer.
• 100% code score passed.

Continue reading →