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.
What to submit – follow the instructions here to earn full points
• (80 pts total + 18 bonus points) The report
o Introduction (15 pts + 6 bonus points)
- § (5 pts) Your description/formulation of the problem (what’s the data and what’s your goal for working with it, beyond just “this is my homework” or “I want to optimize this equation”),
- § (5 pts) the details of your algorithm (e.g., stopping criterion, is this stochastic gradient descent or not, how you chose your learning rate, etc),
- § (5 pts) pseudo-code of your algorithm (see Canvas for an example)
- § (+2 bonus pts) if you include a description of your quadratic model
- § (+4 bonus pts) if you describe how you normalized or standardardized your data.
Include some histograms that illustrate how the distribution of a feature variable’s
values changed as a result of your pre-processing. o Results (52 pts + 8 bonus points)
- § To report the performance of your models, I would like you to calculate the variance explained for the response variable, which is:
1− 𝑀𝑆𝐸
𝑉𝑎𝑟𝑖𝑎𝑛𝑐𝑒(𝑜𝑏𝑠𝑒𝑟𝑣𝑒𝑑)
- § (18 pts) Variance explained of your models on the training dataset when using only one of the predictor variables (uni-variate regression) and when using all eight (multi-variate regression). You should have a total of nine values.
- § (18 pts) Variance explained of your models on the testing data points. Again, you should have a total of nine values.
- § (16 pts) Plots of your trained uni-variate models on top of scatterplots of the training data used (please plot the data using the x-axis for the predictor variable and the y-axis for the response variable).
- § (+4 bonus points) if you include results from your quadratic model
- § (+4 bonus points) if you include results from using normalized or standardized
feature values as input
Discussion (13 pts + 4 bonus points)
- § (5 pts) Describe how the different models compared in performance on the
training data. Did the same models that performed well on the training data do
well on the testing data?
- § (5 pts) Describe how the coefficients of the uni-variate models predicted or failed
to predict the coefficients in the multi-variate model(s).
- § (3 pts) Draw some conclusions about what factors predict concrete compressive
strength. What would you recommend to make the hardest possible concrete?
- § (+2 bonus points) if you include comparisons to the results from normalized or
standardized data
- § (+2 bonus points) if you include comparisons to the results from your quadratic
model
total + 7 bonus points) Your program (in a language you choose) including:
(15 pts) The code itself
(5 pts) Brief instructions on how to run your program (input/output plus execution environment and compilation if needed) – in a separate file
(+2 bonus points) if you include code for normalizing or standardizing the data
(+5 bonus points) if you include code for the quadratic model.
Note: We won’t grade your program’s code for good coding practices or documentation. However, if we find your code difficult to understand or run, we may ask you to run your program to show it works on a new dataset.About the extra credit:
The bonus point values listed are the upper limit of extra credit you can earn for each extension. How many points you get will depend on how well you completed each task. Feel free to include partially completed extensions for partial extra credit!
In total, you can earn up to 25 bonus points on this assignment, which means you can actually get a 125% as your score if you submit it on time, or you can submit this assignment late with the 20% penalty and still get a 100% as your score. It’s up to you how you would prefer to manage your time and effort.
