Optimization Algorithms

Gradient descent is a way of minimizing an objective function J(θ) by updating the model's parameters in the opposite direction of the gradient of the objective function.

Batch Gradient Descent: Batch gradient descent computes the gradient of the cost function for the entire training set in just one update which makes it very slow and intractable for very large datasts. The parameters are updated as follows: 
θ = θ - η ∇ J(θ)
Batch gradient descent is guaranteed to converge to the global minimum for convex problems.

Stochastic Gradient Descent: SGD performs parameter update for each training example. It is much faster and can be used to learn online but due to single point updates it can be very noisy and cause the objective function to oscillate. It can continuously keep oscillating and is not guaranteed to converge. However, upon using a decreasing learning rate it is known to converge almost certainly.

Mini-batch gradient descent: This is in between the above two algorithms and operates on a mini batch of n training examples in every iteration. Typically mini batch sizes can be between 64 to 512. It thus reduces the variance of the parameter updates and leads to stable convergence and can make use of vectorization from the state of the art libraries. One of the biggest challenge of using mini-batch gradient descent is the choice of the learning rate parameter. Another problem is that same learning rate applies to all the features but if the features have different frequencies and are sparse this needs to be taken care of. (Note: Other optimization algorithms such as Newton's method are infeasible to compute for high dimensional datasets.)

Momentum : The basic idea is to compute an exponentially weighted average of the gradients and then use that to update the gradients itself. The update is as follows: 
Compute the moving average gradient vector
Vt = βVt-1 + (1 - β)∇J(θ)
Update the weights instead of updating with the derivatives
θ = θ - αVt
This smoothes out the step of gradient descent as it averages out the gradients. As a result it results in much smaller oscillations and faster convergence. There are 2 parameters α the learning rate parameter and β which controls the exponentially weighted average. In practice, β = 0.9 works very well. (Note: In many literature the term (1 - β) is ignored.)

RMSprop : Root mean squared prop is an unpublished method by Geoff Hinton. It proceeds as follows: On iteration t, Compute the derivative on current mini-batch and maintain a moving average of the square of the gradient. Note that the square is computed as an element wise square. 
St = βSt-1 + (1 - β) ∇J(θ)^2
θt = θt-1 - α ∇J(θ)/√ St
It helps damp out the oscillations and hence can use a larger learning rate and faster learning.

Adagrad : Adagrad adapts the learning rate for the parameters performing larger updates for infrequent and smaller updates for frequent parameters. For this reason it is particularly useful for sparse datasets. Adagrad modifies the learning rate η based upon the past gradient of the parameter as follows: 
gt,i = ∇ J(θt,i)
θt,i = θt-1, i - η gt,i/√ Gt,ii
Adam : Adaptive Moment Estimation (Adam) computes the adaptive learning rates for each parameters. It combines ideas from RMSprop and Momentum to come up with updates as follows: 
On iteration t:
Compute gradient using mini batch dw
Vt = β1 Vt-1 + (1 - β1) dw
St = β2 St-1 + (1 - β2) dw^2
You can also correct for bias as the moving averages in the initial iterations are off.
Vt_corrected = Vt / ( 1 - β1^t)
St_corrected = St / ( 1 - β2^t)
Finally the updates are:
θt = θt-1 - αVt_corrected / √ St_corrected
Totally awesome blog post on Overview of Optimization Algorithms for Gradient Descent Corresponding paper of the blog post

Comments

Post a Comment

Popular posts from this blog

MinHash, Bloom Filters and LSH

Lets talk about some large scale algorithms widely used in the document world. MinHash: Minhash is a really cute algorithm to determine how does a document compare to another. One simple way to compute document similarity is to compute the jaccard similarity between them. The jaccard similarity between the documents is computed as follows: def jaccard_similarity(set1: set, set2: set): if len(set1) == 0 or len(set2) == 0: return 0.0 common = len(set1.intersection(set2)) if common == 0: return 0.0 union = len(set1.union(set2)) return common / union One problem with Jaccard similarity is that it can take a lot of time to compute especially for large scale documents. The idea behind minhashing is to first operate on the space of document shingles. Shingles are basically any combination of k consecutive words of the document. For example, for the sentence "hi i am jaya" the possible 3 shingles are "hi i am" and "i am jaya...
Read more

Perceptron Algorithm

Image
The perceptron algorithm is a linear classifier using a linear function (w'x + b) to classify the points into two classes. The loss function for the perceptron algorithm just counts the points misclassified and then incrementally adjusts the weight vector and thus the decision boundary to appropriately classify the two classes. Perhaps this is the simplest algorithm one can think of to update the weight vector and is shown as follows: w(k+1) = w(k) + yt*xt if yt ≠ f(xt; w) i.e. we cycle through the training points and adjust the weight vector only if the points are misclassified. Note that our class labels are -1 and 1 and hence if the points are misclassified then y_t* f(xt; w) will be negative. In order to understand why the seemingly simple update rule works and leads to a convergence, lets closely examine it. One of the underlying assumption in the perceptron model is that the points are linearly separated hence there exists an w* such that y_t * f(xt; w*) ≥ γ for all...
Read more

Logistic Regression

The logistic regression method even though called regression has a unique ability to give posterior probability values for a data point to belong to a particular class and hence serve as a discriminative function useful for classification. The idea is simple, to use the logistic sigmoid function on the linear function of feature vector. p(y = 1| x) = σ(w'x +b) The likelihood function can be written as p(t|w) = Π y_i^t_i*(1 - y_i)^(1 - t_i) ln p(t|w) = Σ t_i*ln(y_i) + (1 - t_i)*ln(1 - y_i) The error function is computed by taking the negative of the log likelihood function and is computed as follows: E(w) = -ln p(t|w) Now, ∇E(w) is computed as follows: y = 1 / (1 + exp(-w'x) Taking derivative of both sides, ∇y/∇w = exp(-w'x)(x)/(1 + exp(-w'x))^2 ∇y/∇w = xy(1-y) Substituting the value in ∇E(w), we get ∇ E(w) = Σ (y_i - t_i)*x_i The derivative of the error function is similar to the least squares problem, although w...
Read more