CSE514- Programming: Assignment 1 Solved

This assignment is to enhance your understanding of objective functions, regression models, and the gradient descent algorithm for optimization. It consists of a programming assignment (with optional extensions for bonus points) and a report. This project is individual work, no code sharing please, but you may post bug questions to Piazza for help.

Topic 

Design and implement a (stochastic) gradient descent algorithm or algorithms for regression.

Programming work
A) Uni-variate linear regression
In the lecture, we discussed uni-variate linear regression y = f(x) = mx+b, where there is only a single independent variable x. 

Your program must specify the objective function of mean squared error and be able to apply the gradient descent algorithm for optimizing a uni-variate linear regression model.

B) Multi-variate linear regression
In practice, we typically have multi-dimensional (or multi-variate) data, i.e., the input x is a vector of features with length p. Assigning a parameter to each of these features, plus the b parameter, results in p+1 model parameters. Multi-variate linear models can be succinctly represented as: 

                                y = f(x) = (m · x)                     (i.e., dot product between m and x), 

where m = (m0, m1, …, mp)T and x = (1, x1, …, xp)T, with m0 in place of b in the model. 

Your program must be able to apply the gradient descent algorithm for optimizing a multi-variate linear regression model using the mean squared error objective function.

C) Optional extension 1 – Multi-variate polynomial regression
For bonus points, extend to a multi-variate quadratic regression model. This model should have 36 quadratic terms and 8 linear terms, for a total of 45 (44 + the constant term) parameters that you'll need to fit.

D) Optional extension 2 – Data pre-processing
For bonus points, get results after pre-processing the data by normalizing or standardizing each variable. This should be in addition to the results from not pre-processing, so you can analyse the effect that pre-processing the data has on the results.

IMPORTANT: Regression is basic, so there are many implementations available. But you MUST implement your method yourself. This means that you cannot use a software package and call an embedded function for regression or gradient descent within the package. You may use other basic functions like matrix math, but the gradient descent and regression algorithm must be implemented by yourself.

Data to be used
We will use the Concrete Compressive Strength dataset in the UCI repository at

            UCI Machine Learning Repository: Concrete Compressive Strength Data Set

(https://archive.ics.uci.edu/ml/datasets/Concrete+Compressive+Strength)

Note that the last column of the dataset is the response variable (i.e., y).

There are 1030 instances in this dataset.  

Use the first 900 instances for training and the last 130 instances for testing. This means that you should learn parameter values for your regression models using the training data, and then use the trained models to predict the testing data’s response values without ever training on the testing dataset.