Linear Interpolation - No external libraries except Numpy

user_9242747 0
Viewed 259

I'm working through a quiz where you have to implement some machine learning concepts from scratch. One question asks to implement linear interpolation in python without any external libraries besides numpy. The question states:

Q: Given the input data of points [(1, 2), (3, 4), (5, 6), (8, 8), (7, -1)], fit a line of the form Y = A * X + B using gradient descent. Provide the implementation of your algorithm in the function provided using no external libraries, except for numpy. The evaluate linear regression fit on the provided point.

def linear_interpolate_point(data, x):
    """
    Fit a line to the provided data and then evaluate on the provided test point.
    :param data: Collection of points to fit provided as a list of tuples
    :param x: Point to interpolate using your fit line
    :return: The output of your point on the interpolated line
    """
    # fill in function below

I've tried a few different concepts but seem to be stumped on what the question is asking.

Any help is much appreciated.

numpy python
1 Answers

A linear regression can be formalized as follows: f(x) = x*m + b, where b is a bias weigth and m is a weigth that is multiplied with the input. What gradient descent does is to optimize the m and b based on your data. So let's set up an initial model based on your data.

import numpy as np

data = np.array([(1, 2), (3, 4), (5, 6), (8, 8), (7, -1)])
x = data[:, 0]
y = data[:, 0]
m = 0
b = 0

With the initial model we can run a several optimization steps with gradient descent to optimize the weights. Gradient descent basically just computes in which direction to change the weights b and m. We further specify how much iterations we allow for optimization (max_iterations) and how much we move in the direction of the gradient (eta).

def gradient_descent(x, y, m, b, eta, max_iterations):
    n = x.shape[0]
    for iteration in range(max_iterations):
        y_hat = x * m + b
        error = y - y_hat
        # Compute gradient for m and b
        gradient_m = (-2/n) * x.dot(error)
        gradient_b = (-2/n) * sum(error)
        # Update weights
        m = m - eta*gradient_m
        b = b - eta*gradient_b
    
    return m, b

m, b = gradient_descent(x, y, m, b, 1e-2, 1000)

Now plotting the data and the model with optimized weights.

plt.scatter(x, y)
plt.plot(np.linspace(1, 8, 100), np.linspace(1, 8, 100) * m + b )
plt.show()

enter image description here

For a complete explanation how gradient descent works probably some blog posts are better than stackoverflow, e.g. Gradient Descent.

user_60878110
Related