Least Squares, Regularization -LASSO and more

Lets now start with another widely used tool - regression. The main goal of regression analysis is to find a function f(x) that fits the data well and predicts y from x. Also, we want to minimize the risk associated with choosing the hypothesis function. As it is difficult to measure the actual risk and minimize it, we use the empirical measure of risk and try to minimize it. 
Remp = 1/N ∑ Loss(y_i, f(x_i))
Least squares regression has a loss function which is basically the squared error of the target variable y_i from the predicted value f(x_i) and is defined as follows. 
Loss(y_i, f(x_i)) = 1/2 (y_i - f(x_i))^2
Using the above two equations and a vector representation for the input and target variable, we want to minimize the following Remp and we solve it as follows. 
Remp  = 1/2 |y - w'X|^2
      = 1/2 (y - w'X)'(y - w'X)
Taking the first derivative w.r.t. w,
dR/dw = d/dw 1/2 (y'y - X'wy -y'w'X +X'ww'X)
      = 1/2(-2X'y + 2X'Xw)
=> w  = inv(X'X)X'y
The least squares formulation thus has a closed form solution for the weight vector w and can be implemented in matlab using a single command to compute the Moore-Penrose pseudo-inverse. 
w = pinv(x)*y; 
OR
w = x\y;
Big Data and Least Squares:
If the dataset is sufficiently large or available in the form of real time updates, then there will be problems computing X'X. The least squares problem can be solved in such cases using the technique of steepest descent or gradient descent and online algorithm (considering one data point at a time) also known as stochastic gradient descent or the least mean squares algorithm. The idea behind gradient descent algorithm is based upon the principle that if f(x) is defined and differentiable then it decreases the fastest in the direction of the negative of the gradient. The gradient descent algorithm has the problem of getting stuck in a local minima and for certain choices of f(x), the convergence of f(x) is guaranteed. If f(x) is convex, then the local minima is also a global minima (which is true in the case of least squares). The weight update rule in the stochastic gradient descent is defined as follows: (Note that the stochastic gradient descent update leads to an update rule like the perceptron algorithm.) 
w(k+1) = w(k) - η∇E(w) 
Recall that,
E(w) = 1/2 |y_i - w'x_i|^2
∇E(w) = -|y_i - w'x_i|x_i
Hence,
w(k+1) = w(k) + η(y(i) - w(k)'x(i))x(i)
The matlab code for the algorithm is as follows: 
repeat
    for i=1:n
        w = w + eta*(y(i) - x(i,:)*w)*x(i,:)';
    end
until convergence==true
The following figure shows the convergence on the iris dataset.

Regularization and Least Squares:
In order to avoid overfitting, a regularization term can be added to the error function to control the weight vector. Regularization also helps in the cases when the matrix X'X is singular which is the case when two or more column vectors of X are correlated with each other. One simplest form of regularizer is to add a the square of the weight vector and is also known as the weight decay or parameter shrinkage method. The advantage of using this error function is that the function is still differentiable and a closed form solution exists for it. This is also known in literature as the ridge regression. The error function is as follows: 
E(w) = 1/2|y -w'X|^2 + λ w'w/2
∇E(w) = 1/2(y - w'X)'(y - w'X) + λ w'w/2
     = 1/2 (y'y - X'wy -y'w'X +X'ww'X) + λ w'w/2
     = 1/2 (-2X'y + 2X'Xw') + λ w'
  w' = inv(X'X + λI)X'y
The parameter λ ≥ 0 controls the amount of shrinkage. Other regularization technique popularly used is the LASSO regularization which uses the L1 norm of the weight vector instead of the L2-norm as used by ridge regression to control the model parameters. The error function is defined as follows: 
E(w) = 1/2|y -w'X|^2 + λ |w|
Note that the resulting error function is not differentiable but can be solved using quadratic programming or convex optimization methods. One of the main advantages of using this regularizer is that it induces sparsity in the feature space and thus aids in dimensionality reduction. Given the importance of this regularizer in ML today, perhaps we should have another detailed discussion on it later.
Helpful Links:

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&quo
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 t=1, 2
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 we cannot obtain a closed form solution for it
Read more