Why is the cost increasing in the linear regression method?

Question

I am implementing the linear regression model from scratch.

#!/usr/bin/env python2
# -*- coding: utf-8 -*-
"""
Created on Thu Nov 16 14:40:53 2017

@author: user
"""

import os
import random
os.chdir('/home/user/Desktop/andrewng/machine-learning-ex1/ex1')

import pandas as pd
data = pd.read_csv('/home/user/Desktop/andrewng/machine-learning-ex1/ex1/ex1data1.txt',header=None)

theta_0 = random.random() 
theta_1 = random.random() 
alpha = 0.001

print(len(data))


hist = -90
cost = 0
print('theta_0    + theta_1    ')
while(cost-hist>0.001):
    hist = cost
    cost = 0
    a = 0
    b = 0
    for i in range(len(data)):
        k = data.iloc[i]
        a = a +  theta_0 + theta_1*k[0] - k[1]
        b = b + (theta_0 + theta_1*k[0] - k[1])*k[0]
    theta_0 = theta_0 - alpha*a/len(data)
    theta_1 = theta_1 - alpha*b/len(data)
    #print(str(theta_0)+'    '+str(theta_1))
    for j in range(len(data)):
        k = data.iloc[i]
        cost  = cost + (theta_0 + theta_1*k[0] - k[1])**2
    cost = cost/(2*len(data))
    print(cost)
    #if(cost>hist):
    #    print(str(theta_0)+'    '+str(theta_1))
    #    break
print(str(theta_0)+'    '+str(theta_1))

According to the theory the cost should decrease at each iteration but for me the cost keeps increasing.

(DATA)

Answer 1

The reason is your learning rate alpha is too large for this optimization problem. Start with a really small value (< 0.000001) and you will observe a decrease in your cost function.

Keep in mind that when the learning rate is too large, the gradient descent algorithm will miss the global minimum (global because MSE cost function is convex) and will diverge. This is why you have observed still increasing cost function values with alpha = 0.001.

Answer 2

You are using single variable linear regression with MSE, theory says the truth, cost should decrease.

The reason isn't learning rate, it is a bug:

for j in range(len(data)):
    k = data.iloc[i]

i must be replaced with j.

I also recommend to replace while with a for loop:

for i in range(10):