Multivariate Gradient Descent in Python

mv_grad_desc.py

def multivariate_gradient_descent(training_examples, alpha=0.01):
    """
    Apply gradient descent on the training examples to learn a line that fits through the examples
    :param examples: set of all examples in (x,y) format
    :param alpha = learning rate
    :return:
    """
    # initialize the weight and x_vectors
    W = [0 for index in range(0, len(training_examples[0][0]))]

    # W_0 is a constant
    W_0 = 0

    # repeat until "convergence", meaning that w0 and w1 aren't changing very much
    # --> need to define what 'not very much' means, and that may depend on problem domain
    convergence = False
    while not convergence:

        # initialize temporary variables, and set them to 0
        deltaW_0 = 0
        deltaW_n = [0 for x in range(0,len(training_examples[0][0]))]

        for pair in training_examples:
            # grab our data points from the example
            x_i = pair[0]
            y_i = pair[1]

            # calculate a prediction, and find the error
            # needs to be an element-wise plus
            deltaW_0 += multivariate_prediction_error(W_0, y_i, W, x_i)
            deltaW_n = numpy.multiply(numpy.add(deltaW_n, multivariate_prediction_error(W_0, y_i, W, x_i)), x_i)

        #print "DELTA_WN = " + str(deltaW_n)
        # store previous weighting values
        prev_w0 = W_0
        prev_Wn = W

        # get new weighting values
        W_0 = W_0 + alpha*deltaW_0
        W = numpy.add(W,numpy.multiply(alpha,deltaW_n))
        alpha -= 0.001

        # every few iterations print out current model
        #     1.  -->  (w0 + w1x1 + w2x2 + ... + wnxn)
        variables = [( str(W[i]) + "*x" + str(i+1) + " + ") for i in range(0,len(W))]
        var_string = ''.join(variables)
        var_string = var_string[:-3]
        print "Current model is: " + str(W_0)+" + "+var_string
        #     2.  -->  averaged squared error over training set, using the current line
        summed_error = sum_of_squared_error_over_entire_dataset(W_0, W, training_examples)
        avg_error = summed_error/len(training_examples)
        print "Average Squared Error="+str(sum(avg_error))
        print ""

        # check if we have converged
        if abs(prev_w0 - W_0) < 0.00001 and abs(numpy.subtract(prev_Wn, W)).all() < 0.00001:
            convergence = True

    # after convergence, print out the parameters of the trained model (w0, ... wn)
    variables = [( "w"+str(i+1)+"="+str(W[i])+", ") for i in range(0,len(W))]
    var_string = ''.join(variables)
    var_string = var_string[:-2]
    print "RESULTS: "
    print "\tParameters of trained model are: w0="+str(W_0)+", "+var_string
    return W_0, W


################################
##### MULTIVARIATE HELPERS #####
################################
# generalize these to just take a w0, a vector of weights, and a vector x-values
def multivariate_model_prediction(w0, weights, xs):
    return w0 + numpy.dot(weights, xs)

# again, this needs to take just a w0, vector of weights, and a vector of x-values
def multivariate_prediction_error(w0, y_i, weights, xs):
    # basically, we just take the true value (y_i)
    # and we subtract the predicted value from it
    # this gives us an error, or J(w0,w1) value
    return y_i - multivariate_model_prediction(w0, weights, xs)

# should be the same, but use the generalize functions above, and update the weights inside the vector titself
# also need to have a vector fo delta_Wn values to simplify
def multivariate_sum_of_squared_error_over_entire_dataset(w0, weights, training_examples):
    # find the squared error over the whole training set
    sum = 0
    for pair in training_examples:

        x_i = pair[0]
        y_i = pair[1]

        # cast back to values in range [1 --> 20]
        prediction = multivariate_model_prediction(w0,weights,x_i) / (1/20.0)
        actual = y_i / (1/20.0)
        error = abs(actual - prediction)
        error_sq = error ** 2

        sum += error_sq

    return sum