Description
Programming Assignment 1
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
o 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
• (20 pts total + 7 bonus points) Your program (in a language you choose) including:
o (15 pts) The code itself
o (5 pts) Brief instructions on how to run your program (input/output plus execution
environment and compilation if needed) – in a separate file
o (+2 bonus points) if you include code for normalizing or standardizing the data
o (+5 bonus points) if you include code for the quadratic model.
o 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.
Due date
Wednesday, February 23 (midnight, STL time). Submission to Gradescope via course Canvas.
A one week late extension is available in exchange for a 20% penalty on your final score.
About the extra credit:
TheCSE 514 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.
