102.102. Backpropagation Algorithm

Backpropagation Algorithm

Implement the Backpropagation Algorithm to train a simple neural network. Backpropagation is the core algorithm behind training neural networks. It works by computing the gradient of the loss function with respect to each weight using the chain rule, then updating the weights in the direction that minimizes the loss.

The algorithm follows these steps:

1. Forward Pass: output = X @ W

2. Loss Computation: loss = mean((target - output)^2)

3. Gradient Computation: dW = -2/n * X.T @ (target - output)

4. Weight Update: W_new = W - learning_rate * dW

Your function backpropagation(X, weights, target) should perform one step of gradient descent using a learning rate of 0.1 and return the updated weights.

Example:

Input: X = [[1, 2], [3, 4]], weights = [[0.1, 0.2], [0.3, 0.4]], target = [[0.5, 0.6], [0.7, 0.8]]

Forward: output = X @ weights

Error: error = target - output

Gradient: gradient = -2 * X.T @ error

Updated weights: weights - 0.1 * gradient

Output: [[0.09, 0.18], [0.27, 0.36]]

The chain rule allows us to decompose the gradient of a composite function into a product of simpler gradients. This enables efficient computation of how each weight contributes to the overall loss, even in networks with many layers.

Constraints: