## Import packages, Environment Setting


```python
import numpy as np
import tensorflow as tf

from tensorflow.keras import activations

physical_devices = tf.config.list_physical_devices('GPU') 
tf.config.experimental.set_memory_growth(physical_devices[0], True)
```

## Gradient descent (1 dimensional)

Suppose we have a one variable nonlinear function of a single feature: $\mathbf{y}=\frac{1}{1000}(10\mathbf{x})^3 + \frac{1}{20}(10\mathbf{x})^2 + \frac{1}{100}(10\mathbf{x})$. Now we would like to construct a model to fit the above-mentioned function: $\frac{1}{1000}(w\mathbf{x})^3 + \frac{1}{20}(w\mathbf{x})^2 + \frac{1}{100}(w\mathbf{x})$. It is trivial to see that $w=10$ gives us the exact function of $\mathbf{y}$. Here, we will use a __gradient descent__ algorithm to approximate the solution.



To do so, we need to first define the __objective function__ between $\mathbf{y}$ and $\mathbf{\hat{y}}$, we use mean square error here:
$$
\begin{align}
L(\mathbf{y}, \mathbf{\hat{y}})&=\sum\limits_{i=1}^{m}(y_i - \hat{y}_i)^2\\
&=\sum\limits_{i=1}^{m}[y_i - (\frac{w^3x_{i}^3}{1000} + \frac{w^2x_{i}^2}{20} + \frac{wx_{i}}{100})]^2
\end{align}
$$
We can then compute the gradient of $L$ with respect to $w$:
$$
\nabla_{\mathbf{w}}L=2(\frac{3w^2\mathbf{x}^3}{1000} + \frac{w\mathbf{x}^2}{10} + \frac{\mathbf{x}}{100})^T(\mathbf{\hat{y}} - \mathbf{y})
$$
The derived gradient will always point towards the opposite direction from the weight that yield local minimum of the loss surface. Therefore, we can use this property to update the weight to make sure it is closer to the local minimum:
$$
\mathbf{w}^{(t+1)}=\mathbf{w}^{(t)} - \eta\nabla_{\mathbf{w}}L(\mathbf{\hat{y}})
$$
where $\eta$ is a hyperparameter called __learning rate__, which is used to control the magnitude of each updates.


```python
num_samples = 10
tf.random.set_seed(0)
x = tf.random.normal((num_samples, 1), mean=0, stddev=1)
y = x ** 3 + 5 * x ** 2 + 0.1 * x
w = tf.Variable(0.5)

mse = tf.keras.losses.MeanSquaredError()

eta = 0.5
for i in range(0, 10):
    with tf.GradientTape() as g:
        g.watch(w)
        y_hat = ((w * x) ** 3 + 50 * (w * x) ** 2 + 10 * w * x) / 1000
        loss = mse(y, y_hat)
    gradient = g.gradient(loss, w)
    w = w.assign(w - eta * gradient) 
    print(f'iteration:{i+1:>3}{"":>4}weight:{w.numpy():>7.3f}{"":>4}loss:{loss.numpy():>7.3f}')
```

    iteration:  1    weight:  0.838    loss: 36.317
    iteration:  2    weight:  1.390    loss: 36.016
    iteration:  3    weight:  2.291    loss: 35.213
    iteration:  4    weight:  3.746    loss: 33.086
    iteration:  5    weight:  5.979    loss: 27.677
    iteration:  6    weight:  8.818    loss: 15.992
    iteration:  7    weight: 10.401    loss:  2.022
    iteration:  8    weight:  9.678    loss:  0.284
    iteration:  9    weight: 10.187    loss:  0.168
    iteration: 10    weight:  9.862    loss:  0.060


## Gradient descent (2 dimensional)
Now let's look into multiple variables regression. Given a nonlinear transformatin of $\mathbf{X}$: $\mathbf{y}=ReLU(5.0\mathbf{x}_1 + 5.0\mathbf{x}_2)$, we would like to find $\hat{y}=ReLU(w_1\mathbf{x}_1+w_2\mathbf{x}_2)$:
$$
\mathbf{\hat{y}} = ReLU(\mathbf{X}\mathbf{w}) = ReLU(
\begin{bmatrix}
    x_{1,1} & x_{1,2}\\
    x_{2,1} & x_{2,2}\\
    \vdots  & \vdots \\
    x_{m,1} & x_{m,2}\\
\end{bmatrix}\begin{bmatrix}
    w_{1}   \\
    w_{2}   \\
\end{bmatrix}
)
$$
that approximate this function. The square loss function then become:
$$
\begin{align}
L&=\sum\limits_{i=1}^{m}(y_i - \hat{y}_i)^2\\
 &=\sum\limits_{i=1}^{m}[y_i - ReLU(\sum\limits_{j=1}^{2}w_jx_{ij})]^2
\end{align}
$$
The gradient of $L$ with respect to $\mathbf{w}$ is:
$$
\nabla_{\mathbf{w}}L(\mathbf{\hat{y}})=2\frac{\partial(\text{ReLU}(\mathbf{X}))}{\partial\mathbf{w}}(\mathbf{\hat{y}}-\mathbf{y})
$$



Although we only show the example of two dimensional feature matrix. The algorithm can be easily generalized to higher dimension.


```python
eta = 1
num_samples = 10

tf.random.set_seed(0)
x = tf.random.normal((num_samples, 2), mean=0, stddev=1)
w = tf.Variable([[8.], [10.]])
y = activations.relu(tf.matmul(x, w))

w = tf.Variable([[-15.], [-15.]])

for i in range(0, 10):
    with tf.GradientTape() as g:
        g.watch(w)
        y_hat = activations.relu(tf.matmul(x, w))
        loss = tf.reduce_mean(tf.pow(y - y_hat, 2))
    gradient = g.gradient(loss, w)
    w = w.assign(w - eta * gradient)
    message = ''.join((
        f'iteration:{i+1:>3}{"":>4}weight 1:{w.numpy()[0, 0]:>7.3f}{"":>4}', 
        f'weight 2:{w.numpy()[1, 0]:>7.3f}{"":>4}loss:{loss.numpy():>7.3f}'
    ))
    print(message)
```

    iteration:  1    weight 1: -1.922    weight 2: -4.658    loss:233.694
    iteration:  2    weight 1:  0.084    weight 2: -1.810    loss: 66.604
    iteration:  3    weight 1:  0.454    weight 2: -0.885    loss: 58.866
    iteration:  4    weight 1:  5.278    weight 2:  0.828    loss: 57.196
    iteration:  5    weight 1:  8.291    weight 2:  6.033    loss: 27.748
    iteration:  6    weight 1:  8.661    weight 2:  8.062    loss:  3.822
    iteration:  7    weight 1:  8.543    weight 2:  8.947    loss:  0.819
    iteration:  8    weight 1:  8.401    weight 2:  9.367    loss:  0.226
    iteration:  9    weight 1:  8.305    weight 2:  9.575    loss:  0.077
    iteration: 10    weight 1:  8.235    weight 2:  9.695    loss:  0.036


## Epoch and Batch
When we compute the loss, we can either consider every sample or a subset of samples at a time. We call the iteration that every sample in the dataset has been used to update the parameters an __epoch__. In each epoch, we can split the samples into different __batches__. 
* __Mini-batch gradient descent__: updates the parameters consider a batch of samples at a time. 
* __Stochastic gradient descent (SGD)__: update the parameters consider one sample at a time).




```python
def mini_batch_gradient_descent(x, y, w, num_epochs, batch_size, eta=0.03):
    num_samples = x.shape[0]

    for i in range(0, num_epochs):
        indices = tf.range(start=0, limit=num_samples, dtype=tf.int32)
        tf.random.set_seed(i)
        shuffled_indices = tf.random.shuffle(indices)

        shuffled_x = tf.gather(x, shuffled_indices)
        shuffled_y = tf.gather(y, shuffled_indices)

        batches = [batch_size] * (num_samples // batch_size)
        if num_samples % batch_size != 0:
            batches.extend([num_samples % batch_size])
            
        batches_x = tf.split(shuffled_x, batches, axis=0)
        batches_y = tf.split(shuffled_y, batches, axis=0)

        for j, (batch_x, batch_y) in enumerate(zip(batches_x, batches_y)):
            with tf.GradientTape() as g:
                g.watch(w)
                y_hat = activations.relu(tf.matmul(batch_x, w))
                loss = tf.reduce_mean(tf.pow(batch_y - y_hat, 2))
            gradient = g.gradient(loss, w)
            w = w.assign(w - eta * gradient) 
            message = ''.join((
                f'epoch:{i+1:>3}{"":>4}batch:{j+1:>3}{"":>4}weight 1:{w.numpy()[0, 0]:>7.3f}',
                f'{"":>4}weight 2:{w.numpy()[1, 0]:>7.3f}{"":>4}loss:{loss.numpy():>8.3f}'
            ))
            print(message)
                  
    return
```


```python
eta = 0.5
batch_size = 5
num_epochs = 5
num_samples = 20

tf.random.set_seed(0)
x = tf.random.normal((num_samples, 2), mean=0, stddev=1)
w = tf.Variable([[8.], [10.]])
y = activations.relu(tf.matmul(x, w))

w = tf.Variable([[-12.90], [-10.10]])

mini_batch_gradient_descent(x, y, w, num_epochs, batch_size, eta) 
```

    epoch:  1    batch:  1    weight 1: -8.620    weight 2:-11.302    loss: 104.110
    epoch:  1    batch:  2    weight 1:  2.346    weight 2: -9.223    loss: 176.833
    epoch:  1    batch:  3    weight 1:  2.168    weight 2: -7.583    loss: 161.436
    epoch:  1    batch:  4    weight 1:  1.886    weight 2: -5.014    loss:  43.494
    epoch:  2    batch:  1    weight 1:  1.244    weight 2: -4.225    loss:  16.860
    epoch:  2    batch:  2    weight 1:  6.825    weight 2: -2.493    loss:  78.891
    epoch:  2    batch:  3    weight 1:  9.963    weight 2:  1.797    loss: 102.498
    epoch:  2    batch:  4    weight 1: 10.698    weight 2:  6.697    loss:  38.748
    epoch:  3    batch:  1    weight 1: 10.968    weight 2:  8.526    loss:   5.312
    epoch:  3    batch:  2    weight 1:  7.207    weight 2:  9.451    loss:  12.181
    epoch:  3    batch:  3    weight 1:  7.223    weight 2:  9.569    loss:   0.077
    epoch:  3    batch:  4    weight 1:  7.456    weight 2: 10.010    loss:   0.371
    epoch:  4    batch:  1    weight 1:  7.586    weight 2: 10.173    loss:   0.069
    epoch:  4    batch:  2    weight 1:  7.876    weight 2:  9.987    loss:   0.152
    epoch:  4    batch:  3    weight 1:  7.937    weight 2: 10.011    loss:   0.008
    epoch:  4    batch:  4    weight 1:  7.937    weight 2: 10.007    loss:   0.000
    epoch:  5    batch:  1    weight 1:  7.965    weight 2: 10.015    loss:   0.002
    epoch:  5    batch:  2    weight 1:  7.967    weight 2: 10.013    loss:   0.000
    epoch:  5    batch:  3    weight 1:  7.969    weight 2: 10.007    loss:   0.000
    epoch:  5    batch:  4    weight 1:  7.990    weight 2:  9.999    loss:   0.001


## Instability
The gradient descent algorithm might not be able to find the optimal parameters that globally minimize the loss function for many reasons. For instance, if the learning rate is set to be too large, the loss function will be unstable and might lead to non-optimal approximation. This problem can be identified by inspecting the training loss in each epoch:




```python
eta = 1.5
num_samples = 10
tf.random.set_seed(0)
x = tf.random.normal((num_samples, 1), mean=0, stddev=1)
y = x ** 3 + 5 * x ** 2 + 0.1 * x

w = tf.Variable(0.5)

for i in range(0, 10):
    with tf.GradientTape() as g:
        g.watch(w)
        y_hat = ((w * x) ** 3 + 50 * (w * x) ** 2 + 10 * w * x) / 1000
        loss = tf.reduce_mean(tf.pow(y - y_hat, 2))
    gradient = g.gradient(loss, w)
    w = w.assign(w - eta * gradient) 
    print(f'iteration:{i+1:>3}{"":>4}weight:{w.numpy():>7.3f}{"":>4}loss:{loss.numpy():>7.3f}')
```

    iteration:  1    weight:  1.515    loss: 36.317
    iteration:  2    weight:  4.452    loss: 34.980
    iteration:  3    weight: 12.023    loss: 24.310
    iteration:  4    weight: -2.383    loss:  8.710
    iteration:  5    weight: -6.264    loss: 33.324
    iteration:  6    weight:-12.476    loss: 18.812
    iteration:  7    weight: -2.094    loss: 16.372
    iteration:  8    weight: -5.565    loss: 34.031
    iteration:  9    weight:-11.888    loss: 21.742
    iteration: 10    weight: -4.579    loss: 12.917


However, if the learning rate is set to be too small. The algorithm might stuck in local minimum. We usually solve this by proper weight initialization or applying the optimizers, which we will explain in more details in other exercise:




```python
num_samples = 10
tf.random.set_seed(0)
x = tf.random.normal((num_samples, 1), mean=0, stddev=1)
y = x ** 3 + 5 * x ** 2 + 0.1 * x

w = tf.Variable(-5.)

eta = 0.2
for i in range(0, 10):
    with tf.GradientTape() as g:
        g.watch(w)
        y_hat = ((w * x) ** 3 + 50 * (w * x) ** 2 + 10 * w * x) / 1000
        loss = tf.reduce_mean(tf.pow(y - y_hat, 2))
    gradient = g.gradient(loss, w)
    w = w.assign(w - eta * gradient) 
    print(f'iteration:{i+1:>3}{"":>4}weight:{w.numpy():>7.3f}{"":>4}loss:{loss.numpy():>7.3f}')
```

    iteration:  1    weight: -5.829    loss: 24.109
    iteration:  2    weight: -6.671    loss: 20.628
    iteration:  3    weight: -7.473    loss: 17.149
    iteration:  4    weight: -8.184    loss: 14.095
    iteration:  5    weight: -8.766    loss: 11.784
    iteration:  6    weight: -9.206    loss: 10.289
    iteration:  7    weight: -9.516    loss:  9.460
    iteration:  8    weight: -9.721    loss:  9.060
    iteration:  9    weight: -9.852    loss:  8.887
    iteration: 10    weight: -9.932    loss:  8.818



```python

```

5b4d1f4d044ea0a62396b76c55cd5812384f3bdc
ipynb
Jupyter Notebook
notebooks/gradient_descent.ipynb
dn070017/Neural-Networks-Tensorflow
2a98f14a05f98ea8019dbae9bb0f556745e944f6
MIT
notebooks/gradient_descent.ipynb
dn070017/Neural-Networks-Tensorflow
2a98f14a05f98ea8019dbae9bb0f556745e944f6
MIT
notebooks/gradient_descent.ipynb
dn070017/Neural-Networks-Tensorflow
2a98f14a05f98ea8019dbae9bb0f556745e944f6
MIT
Qwen/Qwen-72B
1. YES
2. YES