only bid if you know Python and algorithms

1

You may choose to use whatever programming language you want. However, you must provide clear instructions on how to compile and/or run your source code. I recommend using a modern language, such as Python, R, or Matlab as learning these languages can help you if you were to enter the machine learning or artificial intelligence field in the future.

All analyses performed and algorithms run must be written from scratch. That is, you may not use a library that can perform coordinate descent, cross validation, elastic net, least squares regression, optimization, etc. to successfully complete this programing assignment (though you may reuse your relevant code from Programming Assignment 1). The goal of this assignment is not to learn how to use particular libraries of a language, but it is to instead understand how key methods in statistical machine learning are implemented. With that stated, I will provide 10% extra credit if you additionally implement the assignment using built-in statistical or machine learning libraries (see Deliverable 6 at end of the document).

Brief overview of assignment

In this assignment you will still be analyzing the same credit card data from 𝑁 = 400 training observations that you examined in Programming Assignment 1. The goal is to fit a model that can predict credit balance based on 𝑝 = 9 features describing an individual, which include an individual’s income, credit limit, credit rating, number of credit cards, age, education level, gender, student status, and marriage status. Specifically, you will perform a penalized (regularized) least squares fit of a linear model using elastic net, with the model parameters obtained by coordinate descent. Elastic net will permit you to provide simultaneous parameter shrinkage (tuning parameter 𝜆 ≥ 0) and feature selection (tuning parameter 𝛼 ∈ [0,1]). The

2

two tuning parameters 𝜆 and 𝛼 will be chosen using five-fold cross validation, and the best-fit model parameters will be inferred on the training dataset conditional on an optimal pair of tuning parameters.

Data

Data for these observations are given in Credit_N400_p9.csv, with individuals labeled on

each row (rows 2 through 401), and input features and response given on the columns (with the first row representing a header for each column). There are six quantitative features, given by columns labeled “Income”, “limit”, “Rating”, “Cards”, “Age”, and “Education”, and three qualitative features with two levels labeled “Gender”, “Student”, and “Married”.

Detailed description of the task

Recall that the task of performing an elastic net fit to training data {(𝑥1,𝑦1),(𝑥2,𝑦2),…,(𝑥𝑁,𝑦𝑁)} is to minimize the cost function

𝐽(𝛽,𝜆,𝛼) = ∑(𝑦𝑖 −∑𝑥𝑖𝑗𝛽𝑗

𝑝

𝑗=1

)

2 𝑁

𝑖=1

+𝜆(𝛼∑𝛽𝑗 2

𝑝

𝑗=1

+(1−𝛼)∑|𝛽𝑗|

𝑝

𝑗=1

)

where 𝑦𝑖 is a centered response and where the input 𝑝 features are standardized (i.e., centered and divided by their standard deviation). Note that we cannot use gradient descent to minimize

this cost function, as the component ∑ |𝛽𝑗| 𝑝 𝑗=1 of the penalty is not differentiable. Instead, we

use coordinate descent, where we update each parameter 𝑘, 𝑘 = 1,2,…,𝑝, in turn, keeping all other parameters constant, and using sub-gradient rather than gradient calculations. To implement this algorithm, depending on whether your chosen language can quickly compute vectorized operations, you may implement coordinate descent using either Algorithm 1 or Algorithm 2 below (choose whichever you are more comfortable implementing). Note that in languages like R, Python, or Matlab, Algorithm 2 (which would be implemented by several nested loops) may be much slower than Algorithm 1. Also note that if you are implementing Algorithm 1 using Python, use numpy arrays instead of Pandas data frames for computational speed. For this assignment, assume that we will reach the minimum of the cost function within a fixed number of steps, with the number of iterations being 1000.

3

Algorithm 1 (vectorized): Step 1. Fix tuning parameters 𝜆 and 𝛼 Step 2. Generate 𝑁-dimensional centered response vector 𝐲 and 𝑁 ×𝑝 standardized

(centered and scaled to have unit standard deviation) design matrix 𝐗 Step 3. Precompute 𝑏𝑘,𝑘 = 1,2,…,𝑝, as

𝑏𝑘 = ∑𝑥𝑖𝑘 2

𝑁

𝑖=1

Step 4. Randomly initialize the parameter vector 𝛽 = [𝛽1,𝛽2,…,𝛽𝑝]

Step 5. For each 𝑘, 𝑘 = 1,2,…,𝑝: compute

𝑎𝑘 = x𝑘 𝑇(𝐲−𝐗𝛽 +x𝑘𝛽𝑘)

and set

𝛽𝑘 =

sign(𝑎𝑘)(|𝑎𝑘|− 𝜆(1−𝛼)

2 ) +

𝑏𝑘 +𝜆𝛼

Step 6. Repeat Step 5 for 1000 iterations or until convergence (vector 𝛽 does not change)

Step 7. Set the last updated parameter vector as �̂� = [�̂�1, �̂�2,…, �̂�𝑝]

4

Algorithm 2 (non-vectorized): Step 1. Fix tuning parameters 𝜆 and 𝛼 Step 2. Generate 𝑁-dimensional centered response vector 𝐲 and 𝑁 ×𝑝 standardized

(centered and scaled to have unit standard deviation) design matrix 𝐗 Step 3. Precompute 𝑏𝑘,𝑘 = 1,2,…,𝑝, as

𝑏𝑘 = ∑𝑥𝑖𝑘 2

𝑁

𝑖=1

Step 4. Randomly initialize the parameter vector 𝛽 = [𝛽1,𝛽2,…,𝛽𝑝]

Step 5. For each 𝑘, 𝑘 = 1,2,…,𝑝: compute

𝑎𝑘 = ∑𝑥𝑖𝑘

(

𝑦𝑖 −∑𝑥𝑖𝑗𝛽𝑗

𝑝

𝑗=1 𝑗≠𝑘 )

𝑁

𝑖=1

and set

𝛽𝑘 =

sign(𝑎𝑘)(|𝑎𝑘|− 𝜆(1−𝛼)

2 ) +

𝑏𝑘 +𝜆𝛼

Step 6. Repeat Step 5 for 1000 iterations or until convergence (vector 𝛽 does not change)

Step 7. Set the last updated parameter vector as �̂� = [�̂�1, �̂�2,…, �̂�𝑝]

Note that we define

sign(𝑥) = { −1 if 𝑥 < 0 1 if 𝑥 ≥ 0

𝑥+ = { 0 if 𝑥 < 0 𝑥 if 𝑥 ≥ 0

and we use the notation x𝑘 as the 𝑘th column of the design matrix 𝐗 (the 𝑘th feature vector). This vector by definition is an 𝑁-dimensional column vector.

When randomly initializing the parameter vector, I would make sure that the parameters start at small values. A good strategy here may be to randomly initialize each of the 𝛽𝑗, 𝑗 = 1,2,…,𝑝,

parameters from a uniform distribution between −1 and 1.

Effect of tuning parameter on inferred regression coefficients

You will consider a discrete grid of nine tuning parameter values 𝜆 ∈ {10−2,10−1,100,101,102,103,104,105,106} where the tuning parameter is evaluated across

a wide range of values on a log scale, as well as six tuning parameter values 𝛼 ∈ {0, 1

5 , 2

5 , 3

5 , 4

5 ,1}.

For each tuning parameter value pair, you will use coordinate descent to infer the best-fit model. Note that when 𝛼 = 0, we obtain the lasso estimate, and when 𝛼 = 1, we obtain the ridge regression estimate.

5

Deliverable 1: Illustrate the effect of the tuning parameter on the inferred elastic net regression coefficients by generating six plots (one for each 𝛼 value) of nine lines (one for

each of the 𝑝 = 9 features), with the 𝑦-axis as �̂�𝑗, 𝑗 = 1,2,…,9, and the 𝑥-axis the

corresponding log-scaled tuning parameter value log10(𝜆) that generated the particular �̂�𝑗.

Label both axes in all six plots. Without the log scaling of the tuning parameter 𝜆, the plots will look distorted.

Choosing the best tuning parameter

You will consider a discrete grid of nine tuning parameter values 𝜆 ∈ {10−2,10−1,100,101,102,103,104,105,106} where the tuning parameter is evaluated across

a wide range of values on a log scale, as well as six tuning parameter values 𝛼 ∈ {0, 1

5 , 2

5 , 3

5 , 4

5 ,1}.

For each tuning parameter value pair, perform five-fold cross validation and choose the pair of 𝜆 and 𝛼 values that give the smallest

CV(5) = 1

5 ∑MSE𝑖

5

𝑖=1

where MSE𝑖 is the mean squared error on the validation set of the 𝑖th-fold.

Note that during the five-fold cross validation, you will hold out one of the five sets (here 80 observations) as the Validation Set and the remaining four sets (the other 320 observations) will be used as the Training Set. On this Training Set, you will need to center the output and standardize (center and divided by the standard deviation across samples) each feature. These identical values used for centering the output and standardizing the input will need to be applied to the corresponding Validation Set, so that the Validation set is on the same scale. Because the Training Set changes based on which set is held out for validation, each of the five pairs of Training and Validation Sets will have different centering and standardization parameters.

Deliverable 2: Illustrate the effect of the tuning parameters on the cross validation error by generating a plot of six lines (one for each 𝛼 value) with the 𝑦-axis as CV(5) error, and the 𝑥-

axis the corresponding log-scaled tuning parameter value log10(𝜆) that generated the particular CV(5) error. Label both axes in the plot. Without the log scaling of the tuning

parameter 𝜆, the plots will look distorted.

Deliverable 3: Indicate the pair of values 𝜆 and 𝛼 that generated the smallest CV(5) error.

Deliverable 4: Given the optimal 𝜆 and 𝛼 pair, retrain your model on the entire dataset of 𝑁 = 400 observations and provide the estimates of the 𝑝 = 9 best-fit model parameters. How do these estimates compare to the estimates obtained from ridge regression (𝛼 = 1 under optimal 𝜆 for 𝛼 = 1) and lasso (𝛼 = 0 under optimal 𝜆 for 𝛼 = 0) on the entire dataset of 𝑁 = 400 observations?

6

Deliverable 5: Provide all your source code that you wrote from scratch to perform all analyses (aside from plotting scripts, which you do not need to turn in) in this assignment, along with instructions on how to compile and run your code. Deliverable 6 (extra credit): Implement the assignment using statistical or machine learning libraries in a language of your choice. Compare the results with those obtained above, and provide a discussion as to why you believe your results are different if you found them to be different. This is worth up to 10% additional credit, which would allow you to get up to 110% out of 100 for this assignment.