Backpropagation

Backpropagation (BP), short for Error Backward Propagation, is a fundamental algorithm used to train neural network models for graph embeddings.

The BP algorithm encompasses two main stages:

• Forward Propagation: Input data is fed into the input layer of the neural network or model. It then moves forward through one or more hidden layers before generating an output at the output layer.
• Backpropagation: The generated output is compared with the actual or expected value. Subsequently, the error is conveyed from the output layer through the hidden layers and back to the input layer. During this process, the weights of the model are adjusted using the gradient descent technique.

The iterative adjustment of weights forms the core of the training process of a neural network. We will illustrate this with a concrete example.

Preparations

Neural Network

A neural network typically consists of several key components: an input layer, one or more hidden layers, and an output layer. Below is a simple example of a neural network architecture:

In this example, $x$ is the input vector with 3 features, and $y$ is the output. The hidden layer contains two neurons $h_1$ and $h_2$, and the sigmoid activation function is applied at the output layer.

Furthermore, the connections between layers are characterized by weights: $v_{11}$ ~ $v_{32}$ connect the input layer to the hidden layer, while $w_1$ and $w_2$ connect the hidden layer to the output layer. These weights are pivotal in the computations performed within the neural network.

Activation Function

Activation functions enable neural networks to model non-linear relationships. Without them, the network can only represent linear mappings, which greatly limits its expressiveness. There are various activation functions available, each with its specific role. In this context, the sigmoid function is used, defined by the following formula and illustrated in the graph below:

Initial Weights

The weights are initialized with random values. For illustration, let's assume the following initial weights:

Training Samples

Let's consider three sets of training samples, as shown below. The superscript indicates the order of the sample in the sequence:

• Inputs: $x^{(1)}=(2\mathrm{, }3\mathrm{, }1)$, $x^{(2)}=(1\mathrm{, }0\mathrm{, }2)$, $x^{(3)}=(3\mathrm{, }1\mathrm{, }1)$
• Outputs: $t^{(1)}=0.64$, $t^{(2)}=0.52$, $t^{(3)}=0.36$

The primary goal of the training process is to adjust the model's parameters (weights) so that the predicted/computed output ($y$) closely matches the actual output ($t$) when the input ($x$) is provided.

Forward Propagation

Input Layer → Hidden Layer

Neurons $h_1$ and $h_2$ are calculated by:

Hidden Layer → Output Layer

The output $y$ is calculated by:

Below is the calculation of the 3 samples:

Apparently, the three computed outputs ($y$) are very different from the expected ($t$).

Backpropagation

Loss Function

A loss function is used to quantify the error or discrepancy between the model's predicted outputs and the expected outputs. It is also commonly referred to as the objective function or cost function. In this case, we'll use the mean squared error (MSE) as the loss function $E$:

where $m$ is the number of samples. Calculate the error of this round of forward propagation as:

$\frac{{(0.64-0.907)}^2+{(0.52-0.698)}^2+{(0.36-0.796)}^2}{2\times 3}=0.234$

A smaller value of the loss function corresponds to higher model accuracy. The fundamental goal of model training is to minimize the value as much as possible.

By treating the inputs and outputs as constants and the weights as variables within the loss function, the goal becomes finding the weights that minimize the loss. This is precisely where the gradient descent technique comes into play.

In this example, batch gradient descent (BGD) is used, meaning all training samples are involved in the gradient calculation. The learning rate is set to $\eta =0.5$.

Output Layer → Hidden Layer

Adjust the weights $w_1$ and $w_2$ respectively.

Calculate the partial derivative of $E$ with respect to $w_1$ with the chain rule:

where,

Calculate with values:

$\frac{\partial E}{\partial y}=\frac{(0.907-0.64)+(0.698-0.52)+(0.796-0.36)}{3}=0.294$

$\frac{\partial y}{\partial s}=\frac{0.907\times (1-0.907)+0.698\times (1-0.698)+0.796\times (1-0.796)}{3}=0.152$

$\frac{\partial s}{\partial w_1}=\frac{2.4+0.75+1.35}{3}=1.5$

Then, $\frac{\partial E}{\partial w_1}=0.294\times 0.152\times 1.5=0.067$

NOTE

Since all samples are involved in computing the partial derivative, we calculate $\frac{\partial y}{\partial s}$ and $\frac{\partial s}{\partial w_1}$ by summing the derivatives across all samples and then taking the average.

Therefore, $w_1$ is updated to $w_1=w_1-\eta \frac{\partial E}{\partial w_1}=0.8-0.5\times 0.067=0.766$.

The weight $w_2$ can be updated in a similar way by calculating the partial derivative of $E$ with respect to $w_2$. In this round, $w_2$ is updated from $0.2$ to $0.167$.

Hidden Layer → Input Layer

Adjust the weights $v_{11}$ ~ $v_{32}$ respectively.

Calculate the partial derivative of $E$ with respect to $v_{11}$ with the chain rule:

We already computed $\frac{\partial E}{\partial y}$ and $\frac{\partial y}{\partial s}$, below are the latter two:

Calculate with values:

$\frac{\partial E}{\partial y}=0.294$

$\frac{\partial y}{\partial s}=0.152$

$\frac{\partial s}{\partial h_1}=0.8$

$\frac{\partial h_1}{\partial v_{11}}=\frac{2+1+3}{3}=2$

Then, $\frac{\partial E}{\partial v_{11}}=0.294\times 0.152\times 0.8\times 2=0.072$.

Therefore, $v_{11}$ is updated to $v_{11}=v_{11}-\eta \frac{\partial E}{\partial v_{11}}=0.15-0.5\times 0.072=0.114$.

The remaining weights can be updated in a similar way by calculating the partial derivative of $E$ with respect to each weight. In this round, their values are updated as follows:

• $v_{12}$ is updated from $0.2$ to $0.191$
• $v_{21}$ is updated from $0.6$ to $0.576$
• $v_{22}$ is updated from $0.3$ to $0.294$
• $v_{31}$ is updated from $0.3$ to $0.282$
• $v_{32}$ is updated from $0.5$ to $0.496$

Training Iterations

Apply the updated weights to the model and perform forward propagation again using the same three samples. In this iteration, the resulting error $E$ decreases to $0.192$.

The backpropagation algorithm continues this cycle of forward and backward propagation iteratively to train the model. This process repeats until one of the following conditions is met: a predefined number of training iterations is completed, a time limit is reached, or the error falls below a specific threshold.