SUMMATIVE ASSIGNMENT

Programming Assignment 1: Part 1 - Linear Regression

Introduction

In this part of the assignment, you will implement linear regression and get to see it work on data.  To get started, you will need to download the starter code (from DUO) and unzip its contents to the directory where you wish to complete the assignment. If  needed,  use  the  cd  command  in  Matlab/Octave  or  Python  to  change  to  this directory before starting this assignment.

Files included in this assignment

    ex1.m – Matlab/Octave script that will help step you through the assignment

    ex1.py – Python script that will help step you through the assignment

    ex1data1.txt - Dataset for linear regression with one variable

     [⋆] plotData.m - Function to display the dataset

     [⋆] computeCost.m - Function to compute the cost of linear regression

     [⋆] gradientDescent.m - Function to run gradient descent

⋆ indicates files you will need to complete.

Throughout the assignment, you will be using the scripts ex1.m or ex1.py.   These scripts set up the dataset for the problems and make calls to functions that you will write.  You do not need to modify either of them.  You are only required to modify functions in other files, by following the instructions in this assignment.

For this programming assignment, you are required to complete the first part of the assignment to implement linear regression with one variable.  The second part of the assignment, which you must also complete, covers logistic regression.

Linear regression with one variable

In this part of this assignment, you will implement linear regression with one variable to  predict  profits  for  a  food  truck.    Suppose  you  are  the  CEO  of  a  restaurant franchise and are considering different cities for opening a new outlet.   The chain already has trucks in various cities and you have data for profits and populations from the cities.   You would like to use this data to help you select which city to expand to next.

The file ex1data1.txt contains the dataset for our linear regression problem.  The first column is the population of a city and the second column is the profit of a food truck in that city.  A negative value for profit indicates a loss.  The ex1.m and ex1.py script have already been set up to load this data for you.

Plotting the Data

Before starting on any task, it is often useful to understand the data by visualizing it. For this dataset, you can use a scatter plot to visualize the data, since it has only two properties  to  plot  (profit  and  population).    (Many  other  problems  that  you  will encounter in real life are multi-dimensional and can’t be plotted on a 2-d plot.)   In ex1.m, the dataset is loaded from the data file into the variables X and y:

data = load('ex1data1.txt');

X = data(:, 1); y = data(:, 2);

m = length(y);

In ex1.py, the dataset is loaded into the variables X and y as follows:

data = pd.read_csv("ex1data1.txt",names=["X","y"])

x = np.array(data.X)[:,None]

y = np.array(data.y)

m = len(y)

Next, the scripts call the plotData function to create a scatter plot of the data.  If you are using matlab/octave, your job is to complete plotData.m to draw the plot; modify the file and fill in the following code:

plot(x, y, 'rx', 'MarkerSize', 10);

ylabel('Profit in $10,000s');

To do this in python modify the plotData function using the following code:

ax.plot(x,y,'rx',markersize=10)

ax.set_xlabel("Population of City in 10,000s")

ax.set_ylabel("Profit in $10,000s")

Now, when you continue to run ex1.m or ex1.py, with the same red “x” markers and axis labels.

Gradient Descent

In this  part, you will fit the  linear  regression  parameters  θ to  our dataset  using gradient descent.

Update Equations

The objective of linear regression is to minimize the cost function

J (θ)=  1   ¿¿¿

hθ ( x)=θ0 +θ 1 x1+θ2 x2 + ⋯ +θn xn

Here, theθ’s are the parameters, which map the x’s to the y’s. can be written more concisely as follows,

hθ (x)= θixi =θT x

(1)

(2)    Consequently, this

(3)

The value assigned tohθ(x) (the left side the equation) can take any value from -∞ to +∞ . This is a linear regression model.

Recall that the parameters of your model are the θ i values. These are the values you will adjust to minimize cost J(θ). One way to do this is to use the batch gradient descent algorithm. With each step of gradient descent, your parameters θ i come closer to the optimal values that will achieve the lowest cost J(θ).

Implementation

In ex1.m and ex1.py, we have already set up the data for linear regression. In the following  lines,  we  add  another  dimension  to  our  data  to  accommodate  the  θ0 intercept term.   We also initialize the initial parameters to 0 and the learning rate alpha to 0.01.  In ex1.m this is;

X = [ones(m, 1), data(:,1)]; % Add a column of ones to x

theta = zeros(2, 1);

iterations = 1500;

alpha = 0.01;

While in ex1.py the code is as follows;

ones = np.ones_like(x)

X = np.hstack((ones,x)) # Add a column of ones to x

theta = np.zeros(2)

iterations = 1500

alpha = 0.01

Computing the cost J(θ)

As you perform gradient descent to learn minimize the cost function J(θ), it is helpful to monitor the convergence by computing the cost. In this section, you will implement a function to calculate  J(θ) so you can check the convergence of your gradient descent implementation.

Your next task is to complete the code in the file computeCost.m or the function computeCost  in ex1.py. These functions computes  J(θ).   As you are doing this, remember that the variables X and y are not scalar values, but matrices whose rows represent  the  examples  from  the  training  set.    Once  you  have  completed  the function,  the  next  step  in  ex1.m  or  ex1.py  will  run  computeCost  once  using  θ initialized to zeros, and you will see the cost printed to the screen. You should expect to see a cost of 32.07.

Gradient descent

Next, you will implement gradient descent in the file gradientDescent.m if you are using matlab/octave or the gradientDescent function in ex1.py if python.  The loop structure has been written for you, and you only need to supply the updates to θ within each iteration.

As you program, make sure you understand what you are trying to optimize and what is being updated.   Keep in mind that the cost J(θ) is parameterized by the vector θ, not X and y.  That is, we minimize the value of J(θ) by changing the values of the vector θ, not by changing X or y.  Refer to the equations in this handout and to the lecture notes if you are uncertain.

A good way to verify that gradient descent is working correctly is to look at the value of  J(θ)  and  check  that  it  is  decreasing  with  each  step.    Assuming  you  have implemented gradient descent and computeCost correctly, your value of J(θ) should never increase, and should converge to a steady value by the end of the algorithm.

After you are finished, the code will use your final parameters to plot the linear fit.

Your final values for θ will also be used to make predictions on profits in areas of 35,000 and 70,000 people.   Note the way that the following lines in ex1.m uses matrix  multiplication,  rather  than  explicit  summation  or  looping,  to  calculate  the predictions. This is an example of code vectorization.

predict1 = [1, 3.5] * theta;

predict2 = [1, 7] * theta;

These lines in ex1.py are;

predict1 = np.dot([1, 3.5],theta)

predict2 = np.dot([1, 7],theta)

Visualizing J(θ)

To understand the cost function J(θ) better, you will now plot the cost over a 2- dimensional grid of θ0 and θ1 values. You will not need to code anything new for this part, but you should understand how the code you have written already is creating these images.

In the next step of ex1.m, there is code set up to calculate J(θ) over a grid of values using the computeCost function that you wrote.

J_vals = zeros(length(theta0_vals), length(theta1_vals));

for i = 1:length(theta0_vals)

for j = 1:length(theta1_vals)

t = [theta0_vals(i); theta1_vals(j)];

J_vals(i,j) = computeCost(x, y, t);

end

end

In the python script the code set up to calculate J(θ) over a grid of values using the computeCost function that you wrote is;

J_vals = np.zeros((len(theta0_vals),len(theta1_vals)))

for i in range(len(theta0_vals)):

for j in range(len(theta1_vals)):

t = np.array([theta0_vals[i],theta1_vals[j]])

J_vals[i][j] = computeCost(X,y,t)

After these lines are executed, you will have a 2-D array of J(θ) values. The code will then use these values to produce surface and contour plots of J(θ) using the surf and contour commands.

The purpose of these graphs is to show you that how J(θ) varies with changes in θ0 and θ1. The cost function J(θ) is bowl-shaped and has a global minimum. (This is easier to see in the contour plot than in the 3D surface plot). This minimum is the optimal point for θ0 and θ1, and each step of gradient descent.

Required:

a)   Using  your  own  words,   briefly   define  the  functions   computeCost   and gradientDescent.

b)  Create flowchart solutions for computeCost and gradientDescent.

c)  As CEO, your goal is to gain strategic advantage over its rival firms.  How can the food truck business use data analytics analytics and exploit social media

to accomplish this goal?

d)

Programming Assignment 1: Part 2 - Logistic Regression

Introduction

In this exercise, you will implement logistic regression and apply it to two different datasets.

To get started with this part of the exercise, you will need to download the starter code (from DUO) and unzip its contents to the directory where you wish to complete the exercise.  If needed, use the cd command in Octave/Matlab or Python to change to this directory before starting this exercise.

Files included in this programming assignment

    ex2.m – Octave/Matlab script that will help step you through the exercise

    ex2.py - Python script that will help step you through the exercise

    ex2data1.txt - Training set for the first half of the exercise

     plotDecisionBounday.m - Function to plot classifier’s decision boundary

     [⋆] plotData.m - Function to plot 2D classification data

     [⋆] sigmoid.m - Sigmoid Function

     [⋆] costFunction.m - Logistic Regression Cost Function

     [⋆] predict.m - Logistic Regression Prediction Function

⋆ indicates files you will need to complete.

Throughout the exercise, you will be using the scripts ex2.m and/ or ex2.py.  These scripts set up the dataset for the problems and make calls to functions that you will write.  You are only required to modify functions by following the instructions in this assignment.

Logistic Regression

In this  part of the  exercise, you will  build a  logistic  regression  model to  predict whether a student gets admitted into a university.

Suppose that you are the administrator of a university department and you want to determine  each  applicant’s  chance  of  admission  based  on  their  results  on  two exams. You have historical data from previous applicants that you can use as a training  set  for  logistic  regression.    For  each  training  example,  you  have  the applicant’s scores on two exams and the admissions decision.

Your task is to build a classification model that estimates an applicant’s probability of admission based the scores from those two exams.  This outline and the framework code in ex2.m and ex2.py will guide you through the exercise.

Visualizing the data

Before starting to implement any learning algorithm, it is always good to visualize the data if possible.  In the first part of ex2.m, the code will load the data and display it on a 2-dimensional plot by calling the function plotData.

You will now complete the code in plotData so that it displays a figure like Figure 1, where the axes are the two exam scores, and the positive and negative examples are shown with different markers.

% Find Indices of Positive and Negative Examples

pos = find(y==1); neg = find(y == 0);

% Plot Examples

plot(X(pos, 1), X(pos, 2), 'k+','LineWidth', 2, 'MarkerSize', 7);

plot(X(neg, 1), X(neg, 2), 'ko', 'MarkerFaceColor', 'y', 'MarkerSize', 7);

In the ex2.py script the following code should be added to the plotData function to display the data on a 2-dimensional plot:

pos = X[np.where(y==1)]

neg = X[np.where(y==0)]

fig, ax = plt.subplots()

ax.plot(pos[:,0],pos[:,1],"k+",neg[:,0],neg[:,1],"yo")

Sigmoid function

Before you  start with  the  actual  cost function,  recall that the  logistic  regression hypothesis is defined as:

hθ ( x)=g(θT x) =                                              (3)

where function g is the sigmoid function. The sigmoid function is defined as:

g( z)=    1                                                          (4)

Your first step is to implement this function in the sigmoid.m script if you are using octave/ matlab or the sigmoid function in the ex2.py script if you are using python. When you are finished, try testing a few values by calling sigmoid(x) at the command line.  For large positive values of x, the sigmoid should be close to 1, while for large negative values, the sigmoid should be close to 0. Evaluating sigmoid(0) should give you exactly 0.5.   Your code should also work with vectors and matrices.   For a matrix, your function should perform the sigmoid function on every element.

Cost function and gradient

Now you will implement the cost function and gradient for logistic regression.   In octave/matlab, complete the code in costFunction.m to return the cost and gradient. In python this is the costFunction function in the ex2.py script.  Once you are done, ex2.m and ex2.py will call your costFunction using the initial parameters of θ.  You should see that the cost is about 0.693.

Learning parameters

In the previous assignment, you found the optimal parameters of a linear regression model by implementing gradient descent.  You wrote a cost function and calculated its gradient, then took a gradient descent step accordingly.   This time, instead of taking gradient descent steps will use the built in fminunc and minimize functions in octave/matlab and python respectively.  These two functions are optimization solver that find the minimum of an unconstrained function.  For logistic regression, you want to optimize the cost function J(θ) with parameters θ.

Concretely, you are going to use these functions to find the best parameters θ for the logistic regression cost function, given a fixed dataset (of X and y values).  You will pass following inputs:

    The initial values of the parameters we are trying to optimize.

    A function that, when given the training set and a particular θ, computes the

logistic regression cost and gradient with respect to θ for the dataset (X, y)

In ex2.m and ex2.py, we already have code written to call the optimization functions with  the  correct  arguments.    If you  have  completed  the  costFunction  correctly, optimization functions will converge on the right optimization parameters and return the final values of the cost and θ.   Notice that by using the built in optimization functions, you did not have to write any loops yourself, or set a learning rate like you did for gradient descent. This is all done by built in optimization functions you only needed to provide a function calculating the cost and the gradient.

Once  the  optimization  functions  have  complete,  ex2.m  or  ex2.py  will  call  your costFunction function using the optimal parameters of θ.  You should see that the cost is about 0.203.

Evaluating logistic regression

After learning the parameters, you can use the model to predict whether a particular student will be admitted.  For a student with an Exam 1 score of 45 and an Exam 2 score of 85, you should expect to see an admission probability of 0.774.

Another way to evaluate the quality of the parameters we have found is to see how well the learned model predicts on our training set.   In this part, your task is to complete the code in predict.m in octave/matlab or the predict function in ex1.py. The predict function will produce “1” or “0” predictions given a dataset and a learned parameter vector θ.

After you have completed the code the ex2.m and ex2.py scripts will proceed to report  the  training  accuracy  of  your  classifier  by  computing  the  percentage  of examples it got correct.

Required:

a)   Using your own words, briefly define the functions sigmoid, costFunction and predict.

b)   Create flowchart solutions for sigmoid, costFunction and predict .

c)   Suppose after training the logistic regression classifier with gradient descent, you find that it has overfit the training set and does not achieve the desired performance  on  the  training  or  cross  validation  sets.  Briefly  discuss  the

problem of overfitting and identify and discuss two alternative approaches that could be taken to improve the performance of the logistic regression classifier.

d)