Gradient Descent Algorithm in Python

Question

I am trying to write a gradient descent function in python as part of a multivariate linear regression exercise. It runs, but does not compute the correct answer. My code is below. I've been trying for weeks to finish this problem but have made zero progress.

I believe that I understand the concept of gradient descent to optimize a multivariate linear regression function and also that the 'math' is correct. I believe that the error is in my code, but I am still learning python. Your help is very much appreciated.

def regression_gradient_descent(feature_matrix,output,initial_weights,step_size,tolerance):
    from math import sqrt
    converged = False
    weights = np.array(initial_weights)
    while not converged:
        predictions = np.dot(feature_matrix,weights)
        errors = predictions - output
        gradient_sum_squares = 0
        for i in range(len(weights)):
            derivative = -2 * np.dot(errors[i],feature_matrix[i])
            gradient_sum_squares = gradient_sum_squares + np.dot(derivative, derivative)
            weights[i] = weights[i] - step_size * derivative[i]
        gradient_magnitude = sqrt(gradient_sum_squares)
        print gradient_magnitude
        if gradient_magnitude < tolerance:
            converged = True
    return(weights)

Feature matrix is:

sales = gl.SFrame.read_csv('kc_house_data.csv',column_type_hints = {'bathrooms':float, 'waterfront':int, 'sqft_above':int, 'sqft_living15':float,'grade':int, 'yr_renovated':int, 'price':float, 'bedrooms':float, 'zipcode':str,'long':float, 'sqft_lot15':float, 'sqft_living':float, 'floors':str, 'condition':int,'lat':float, 'date':str, 'sqft_basement':int, 'yr_built':int, 'id':str, 'sqft_lot':int,'view':int})

I'm calling the function as:

train_data,test_data = sales.random_split(.8,seed=0)
simple_features = ['sqft_living']
my_output= 'price'
(simple_feature_matrix, output) = get_numpy_data(train_data, simple_features, my_output)
initial_weights = np.array([-47000., 1.])
step_size = 7e-12
tolerance = 2.5e7    
simple_weights = regression_gradient_descent(simple_feature_matrix, output,initial_weights,step_size,tolerance)

**get_numpy_data is just a function to convert everything into arrays and works as intended

Update: I fixed the formula to:

derivative = 2 * np.dot(errors,feature_matrix)

and it seems to have worked. The derivation of this formula in my online course used

-2 * np.dot(errors,feature_matrix)

and I'm not sure why this formula did not provide the correct answer.

Can you give a usage example including actual vs. expected output? — mkrieger1
Also if you could maybe supply some inputs like what your feature matrix looks like, that would be really helpful. — jlarks32
Thanks for the responses: I am not sure of the correct output. The feature matrix is housing sales data. There are several thousand houses in rows and features/inputs in columns (sq ft, # bathrooms, etc.) I edited the original question with more information. — LfB
which reference do you use to determine that derivative = -2 * np.dot(errors[i],feature_matrix[i]) should be use to update the weights? as far as I know we usually use the error to update the weights/coefficients as shown in this tutorial — Yohanes Gultom

Giorgos Altanis Giorgos Altanis · Accepted Answer · 2017-02-27T08:34:18

The step size seems too small, and the tolerance unusually big. Perhaps you meant to use them the other way around?

In general, the step size is determined by a trial-and-error procedure: the "natural" step size α=1 might lead to divergence, so one could try to lower the value (e.g. taking α=1/2, α=1/4, etc until convergence is achieved. Don't start with a very small step size.

Gradient Descent Algorithm in Python

1 Answers