CS 378 Introduction to Data Mining Spring 2009Homework 4Instructor: Inderjit Dhillon Date Due: April 2, 2009Keywords: Linear Regression1. (5 points) Based on the lecture notes on linear regression (available on the course website), let us considerthe linear regr ession problem for the case when dimensionality of the data d = 1. Suppose we are given atraining data {(xi, yi), i = 1, . . . , N } with N observations, xi∈ R is the data point and yi∈ R is the targetvalue associated with xi. We use a linear function of the form f (x) = w0+ w1x to fit the data. Show thatw0= ¯y − w1¯x and w1=σxyσxx,where ¯x =1NPNi=1xi, ¯y =1NPNi=1yi, σxy=1NPNi(xi− ¯x)(yi− ¯y), and σxx=1NPNi=1(xi− ¯x)2.2. (4 points) In this problem, we are going to investigate the time complexity of solving a least squares problemby normal equation with different number of data points N and dimensionality d. Suppose th e data pointsare organized as a matrix X ∈ RN×(d+1), where each row of X corr esponds to a data point, and theassociated target values are organized as column vector y ∈ RN. The normal equation to solve for the(d + 1)-dimensional parameter vector w can be written as XTXw = XTy, which can be solved in Matlabusing “\” operator. (Ax = b can be solved in Matlab by x = A\b.) To measure the elapsed time, you canuse the Matlab commands “tic” and “toc”.(a) (2 points) Use the provided Matlab code genRegression.m to generate synthetic data for linear regression,where the number of data points is varied from 1, 000 to 10, 000 with a step size of 100 and d is fi xed to100. Solve normal equation (by using “\”) for each generated data set and report a plot showing theelapsed time (in seconds) for solving the problem vs the number of data points. (Your results shouldbe averaged over 10 different runs.) DO NOT COMPUTE AN INVERSE.(b) (2 points) Repeat the above procedure while the number of data points is fixed to N = 5000 and d isvaried from 100 to 1000 with a step size of 50.3. (6 points) You are given the Iris dataset (http://www.cs.utexas.edu/~wtang/cs378/iris_reg.tar.gz)for the linear regression problem, where the dataset has been split into training and test set. Let’s considerthe problem of predicting the petal width using a linear combination of sepal length, sepal width, and petallength. In another word, we use the linear function f(x1, x2, x3) =P3i=1wixito fit the training data, wherex1, x2, x3represent sepal length, sepal width and petal length, respectively, and we assume w0= 0.(a) (2 points) Use normal equation to solve this least squares problem. What is the solution w you obtained?What is the RMSE on training set? What is the RMSE on test set?(b) (4 points) Now let us consider using gradient d escent algorithm to solve this problem. The objectiveJ =12ky − Xwk22,where X ∈ RN×3, y ∈ RN, w ∈ R3, and N is th e number of d ata points in the training set.12 CS 378: Introduction to Data MiningThe gradient of J with respect to w is∂J∂w= XT(Xw − y).We can use the following updating rule to reach the optimal value of w:w(t+1)← w(t)− ηXT(Xw(t)− y),where t is the current number of iterations and η is th e learning rate which is set heuristically basedon the application. When using the gradient descent algorithm, we need an initial point w(0)as well.For this problem, let w(0)= [1, 1, 1]Tand η = 10−4. Update w using the above updating rule untilthe criteria kw(t+1)− w(t)k2/kw(t)k2≤ ǫ is satisfied, where the tolerance ǫ is s et to be 10−6for th isproblem.What is the solution w using the above gradient descent algorithm? Is it the same as in
View Full Document
Unlocking...