# Gradient Descent Derivation

We will derive the optimization algorithm from scratch

### Computing $\frac{\partial}{\partial w_0} L(w)$

\begin{align}
\frac{\partial}{\partial w_0} L(w) 
&= \frac{\partial}{\partial w_0} \frac{1}{n} \sum_{i=1}^n\left(y_i - \sin\left(w_0 x_i + w_1 \right)\right)^2 \\
&= \frac{1}{n} \sum_{i=1}^n \frac{\partial}{\partial w_0} \left(y_i - \sin\left(w_0 x_i + w_1 \right)\right)^2 \quad  \\
&= \frac{1}{n} \sum_{i=1}^n  2 \left(y_i - \sin\left(w_0 x_i + w_1 \right)\right) 
    \frac{\partial}{\partial w_0} \left(y_i - \sin\left(w_0 x_i + w_1 \right)\right) \quad\textit{# Chain Rule}\\
&= \frac{1}{n} \sum_{i=1}^n  2 \left(y_i - \sin\left(w_0 x_i + w_1 \right)\right)  
    \left(0 - \frac{\partial}{\partial w_0}\sin\left(w_0 x_i + w_1 \right)\right) \\
&= \frac{1}{n} \sum_{i=1}^n  2 \left(y_i - \sin\left(w_0 x_i + w_1 \right)\right)  
    \left(0 - \cos\left(w_0 x_i + w_1 \right) \frac{\partial}{\partial w_0}\left(w_0 x_i + w_1 \right) \right)  \quad\textit{# Chain Rule}\\
&= \frac{1}{n} \sum_{i=1}^n  2 \left(y_i - \sin\left(w_0 x_i + w_1 \right)\right)  
    \left(0 - \cos\left(w_0 x_i + w_1 \right) \left(x_i + 0 \right) \right) \\
&= -\frac{1}{n} \sum_{i=1}^n  2 \left(y_i - \sin\left(w_0 x_i + w_1 \right)\right)  
    \cos\left(w_0 x_i + w_1 \right) x_i \quad\textit{# Simplified}
\end{align}


### Computing $\frac{\partial}{\partial w_1} L(w)$

\begin{align}
\frac{\partial}{\partial w_1} L(w) 
&= \frac{\partial}{\partial w_1} \frac{1}{n} \sum_{i=1}^n\left(y_i - \sin\left(w_0 x_i + w_1 \right)\right)^2 \\
&= \frac{1}{n} \sum_{i=1}^n \frac{\partial}{\partial w_1} \left(y_i - \sin\left(w_0 x_i + w_1 \right)\right)^2 \\
&= \frac{1}{n} \sum_{i=1}^n  2 \left(y_i - \sin\left(w_0 x_i + w_1 \right)\right) 
    \frac{\partial}{\partial w_1} \left(y_i - \sin\left(w_0 x_i + w_1 \right)\right) \quad\textit{# Chain Rule}\\
&= \frac{1}{n} \sum_{i=1}^n  2 \left(y_i - \sin\left(w_0 x_i + w_1 \right)\right)  
    \left(0 - \frac{\partial}{\partial w_1}\sin\left(w_0 x_i + w_1 \right)\right) \\
&= \frac{1}{n} \sum_{i=1}^n  2 \left(y_i - \sin\left(w_0 x_i + w_1 \right)\right)  
    \left(0 - \cos\left(w_0 x_i + w_1 \right) \frac{\partial}{\partial w_1}\left(w_0 x_i + w_1 \right) \right)  \quad\textit{# Chain Rule}\\
&= \frac{1}{n} \sum_{i=1}^n  2 \left(y_i - \sin\left(w_0 x_i + w_1 \right)\right)  
    \left(0 - \cos\left(w_0 x_i + w_1 \right) \left(0 + 1\right) \right) \\
&= -\frac{1}{n} \sum_{i=1}^n  2 \left(y_i - \sin\left(w_0 x_i + w_1 \right)\right)  
    \cos\left(w_0 x_i + w_1 \right) \quad\textit{# Simplified}
\end{align}


Finally, we get
$$
L(w) = \frac{1}{n} \sum_{i=1}^n\left(y_i - \sin\left(w_0 x_i + w_1 \right)\right)^2
$$


$$
\nabla_w L(w) = \left[ \frac{\partial}{\partial w_1} L(w), \frac{\partial}{\partial w_2} L(w) \right]
$$


```
import plotly.offline as py
import plotly.graph_objects as go
import plotly.express as px
import plotly.figure_factory as ff
import numpy as np
import pandas as pd
```









```
def load_data():
  np.random.seed(42)
  n = 50
  x = np.sort(np.random.rand(n)*2.5 * np.pi)
  x = x - x.mean()/x.std()
  y = np.sin(2.2 * x + 1.8) + 0.2 * np.random.randn(n)
  return (x, y)
```









```
(x, y) = load_data()
print("Number of data points: ", x.shape[0])
```








    Number of data points:  50



```
fig = go.Figure()
fig.add_trace(go.Scatter(x=x, y=y, mode='markers', name='markers'))
fig.update_layout(title='Scatter')
html = plotly.offline.plot(fig, filename='3d-scatter-plotly.html',include_plotlyjs='cdn')
from IPython.core.display import HTML
HTML(html)
```











<html>
<head><meta charset="utf-8" /></head>
<body>
    <div>

                
            
            <div id="5a3f61ad-f583-43b8-bf2c-bdc1126d0acc" class="plotly-graph-div" style="height:100%; width:100%;"></div>
            
        </div>
</body>
</html>



The data is scattered randomly and has high variance, resembling a sine function


```
def model(w, x):
  return np.sin(w[0] * x + w[1])
```









```
xtest = np.linspace(x.min()-0.1, x.max()+0.1, 100)

yhat1 = model([1, 1], xtest)
yhat2 = model([2, 1], xtest)
yhat3 = model([1, 2], xtest)
```









```
fig = px.scatter(x=x, y=y)
fig.add_trace(go.Scatter(x=xtest, y=yhat1, name="$f_{[1,1]}(x) = \sin(x+1)$"))
fig.add_trace(go.Scatter(x=xtest, y=yhat2, name="$f+{[2,1]}(x) = \sin(2x + 1)$"))
fig.add_trace(go.Scatter(x=xtest, y=yhat3, name="$f_{[1,2]}(x) = \sin(x+2)$"))
fig.update_layout(title='Scatter Sine Plot')
html = plotly.offline.plot(fig, filename='3d-scattersine-plotly.html',include_plotlyjs='cdn')
from IPython.core.display import HTML
HTML(html)
```











<html>
<head><meta charset="utf-8" /></head>
<body>
    <div>

                
            
            <div id="44274352-b31c-4521-ab35-f5c4a2870506" class="plotly-graph-div" style="height:100%; width:100%;"></div>
            
        </div>
</body>
</html>



The sin function does not fit at all on the data. We need to find a parameter that is closer to the data, we need a loss function. So, we make use of average squared loss.

$$
L(w) = L\left(f_w, \mathcal{D} = \left\{(x_i, y_i \right\}_{i=1}^n\right) = \frac{1}{n} \sum_{i=1}^n\left(y_i - f_w\left(x_i\right)\right)^2
= \frac{1}{n} \sum_{i=1}^n\left(y_i - \sin\left(w_0 x_i + w_1 \right)\right)^2
$$



```
def avg_sq_loss(w):
  return np.mean((y - model(w, x))**2)
print(avg_sqloss([1,1]))
```








    0.8519315245287105



```
fig = px.bar(x=["$w=[1,1]$", "$w=[2,1]$", "$w=[1,2]$"],
       y=[avg_sq_loss([1,1]), avg_sq_loss([2,1]), avg_sq_loss([1,2])])
fig.update_yaxes(title="Average Squared Loss")
html = plotly.offline.plot(fig, filename='3d-scatter-avgsqloss-plotly.html',include_plotlyjs='cdn')
from IPython.core.display import HTML
HTML(html)
```











<html>
<head><meta charset="utf-8" /></head>
<body>
    <div>

                
            
            <div id="98e7e708-fa1b-4700-80a8-262ecddc5154" class="plotly-graph-div" style="height:100%; width:100%;"></div>
            
        </div>
</body>
</html>




```
loss_trials = []
w0values = np.linspace(0, 3, 30)
w1values = np.linspace(0, 3, 30)
for w0 in w0values:
    for w1 in w1values:
        loss_trials.append([w0, w1, avg_sq_loss([w0, w1])])
```









```
loss_df = pd.DataFrame(loss_trials, columns=["w0", "w1", "loss"])
loss_df
```











<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>w0</th>
      <th>w1</th>
      <th>loss</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>0</th>
      <td>0.0</td>
      <td>0.000000</td>
      <td>0.593748</td>
    </tr>
    <tr>
      <th>1</th>
      <td>0.0</td>
      <td>0.103448</td>
      <td>0.568623</td>
    </tr>
    <tr>
      <th>2</th>
      <td>0.0</td>
      <td>0.206897</td>
      <td>0.564753</td>
    </tr>
    <tr>
      <th>3</th>
      <td>0.0</td>
      <td>0.310345</td>
      <td>0.581171</td>
    </tr>
    <tr>
      <th>4</th>
      <td>0.0</td>
      <td>0.413793</td>
      <td>0.616070</td>
    </tr>
    <tr>
      <th>...</th>
      <td>...</td>
      <td>...</td>
      <td>...</td>
    </tr>
    <tr>
      <th>895</th>
      <td>3.0</td>
      <td>2.586207</td>
      <td>0.943073</td>
    </tr>
    <tr>
      <th>896</th>
      <td>3.0</td>
      <td>2.689655</td>
      <td>0.949557</td>
    </tr>
    <tr>
      <th>897</th>
      <td>3.0</td>
      <td>2.793103</td>
      <td>0.955011</td>
    </tr>
    <tr>
      <th>898</th>
      <td>3.0</td>
      <td>2.896552</td>
      <td>0.960128</td>
    </tr>
    <tr>
      <th>899</th>
      <td>3.0</td>
      <td>3.000000</td>
      <td>0.965686</td>
    </tr>
  </tbody>
</table>
<p>900 rows × 3 columns</p>
</div>




```
loss_df.sort_values("loss").head()
```











<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>w0</th>
      <th>w1</th>
      <th>loss</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>648</th>
      <td>2.172414</td>
      <td>1.862069</td>
      <td>0.036495</td>
    </tr>
    <tr>
      <th>649</th>
      <td>2.172414</td>
      <td>1.965517</td>
      <td>0.041426</td>
    </tr>
    <tr>
      <th>647</th>
      <td>2.172414</td>
      <td>1.758621</td>
      <td>0.042194</td>
    </tr>
    <tr>
      <th>676</th>
      <td>2.275862</td>
      <td>1.655172</td>
      <td>0.042869</td>
    </tr>
    <tr>
      <th>675</th>
      <td>2.275862</td>
      <td>1.551724</td>
      <td>0.046697</td>
    </tr>
  </tbody>
</table>
</div>




```
# We wish to visualise the best brute force model
w_best_brute = loss_df.loc[loss_df["loss"].idxmin(), ["w0", "w1"]].to_numpy()
print(w_best_brute)
```








    [2.17241379 1.86206897]



```
yhat_brute = model(w_best_brute, xtest)

fig = px.scatter(x=x, y=y)
fig.add_trace(go.Scatter(x=xtest, y=yhat_brute, name="Brute Force Approach"))
html = plotly.offline.plot(fig, filename='3d-scatter-avgxysqloss-plotly.html',include_plotlyjs='cdn')
from IPython.core.display import HTML
HTML(html)
```











<html>
<head><meta charset="utf-8" /></head>
<body>
    <div>

                
            
            <div id="3b7453d6-ec14-4992-a0c4-74fef0062471" class="plotly-graph-div" style="height:100%; width:100%;"></div>
            
        </div>
</body>
</html>



We will try to get a better fit using gradient descent


```
fig = go.Figure()
fig.add_trace(go.Surface(x=w0values, y=w1values,
                         z=loss_df["loss"].to_numpy().reshape((len(w0values), len(w1values)))))
fig.update_layout(margin=dict(l=0, r=0, t=0, b=0), height=600)
html = plotly.offline.plot(fig, filename='3d-scatter-avgxysqloss-plotly.html',include_plotlyjs='cdn')
from IPython.core.display import HTML
HTML(html)
```











<html>
<head><meta charset="utf-8" /></head>
<body>
    <div>

                
            
            <div id="24e20465-c15a-4368-9121-02e5f2c97fdd" class="plotly-graph-div" style="height:600px; width:100%;"></div>
            
        </div>
</body>
</html>




```
fig = go.Figure()
fig.add_trace(go.Contour(x=loss_df["w0"], y=loss_df["w1"], z=loss_df["loss"]))
fig.update_layout(margin=dict(l=0, r=0, t=0, b=0),
                  height=500, width=1000)
html = plotly.offline.plot(fig, filename='3dcontours-plotly.html',include_plotlyjs='cdn')
from IPython.core.display import HTML
HTML(html)
```











<html>
<head><meta charset="utf-8" /></head>
<body>
    <div>

                
            
            <div id="402c0b3f-8f3c-4212-8c7f-1717923d432e" class="plotly-graph-div" style="height:500px; width:1000px;"></div>
            
        </div>
</body>
</html>




```
def gradient(w):
  g0 = -np.mean(2 * (y - np.sin(w[0] * x + w[1]))*np.cos(w[0]*x + w[1]*x))
  g1 = -np.mean(2 * (y - np.sin(w[0] * x + w[1]))*np.cos(w[0]*x + w[1]))
  return np.array([g0, g1])
```









```
gradient([1., 1.])
```











    array([-0.68715648,  0.15427075])




```
loss_grad_df = loss_df.join(loss_df[['w0', 'w1']]
 .apply(lambda w: gradient(w), axis=1, result_type="expand")
 .rename(columns={0:"g0", 1:"g1"}))
loss_grad_df
```











<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>w0</th>
      <th>w1</th>
      <th>loss</th>
      <th>g0</th>
      <th>g1</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>0</th>
      <td>0.0</td>
      <td>0.000000</td>
      <td>0.593748</td>
      <td>-0.346570</td>
      <td>-0.346570</td>
    </tr>
    <tr>
      <th>1</th>
      <td>0.0</td>
      <td>0.103448</td>
      <td>0.568623</td>
      <td>-0.121564</td>
      <td>-0.139293</td>
    </tr>
    <tr>
      <th>2</th>
      <td>0.0</td>
      <td>0.206897</td>
      <td>0.564753</td>
      <td>0.095250</td>
      <td>0.062907</td>
    </tr>
    <tr>
      <th>3</th>
      <td>0.0</td>
      <td>0.310345</td>
      <td>0.581171</td>
      <td>0.246164</td>
      <td>0.251583</td>
    </tr>
    <tr>
      <th>4</th>
      <td>0.0</td>
      <td>0.413793</td>
      <td>0.616070</td>
      <td>0.301754</td>
      <td>0.418980</td>
    </tr>
    <tr>
      <th>...</th>
      <td>...</td>
      <td>...</td>
      <td>...</td>
      <td>...</td>
      <td>...</td>
    </tr>
    <tr>
      <th>895</th>
      <td>3.0</td>
      <td>2.586207</td>
      <td>0.943073</td>
      <td>-0.182591</td>
      <td>0.069638</td>
    </tr>
    <tr>
      <th>896</th>
      <td>3.0</td>
      <td>2.689655</td>
      <td>0.949557</td>
      <td>-0.161851</td>
      <td>0.056666</td>
    </tr>
    <tr>
      <th>897</th>
      <td>3.0</td>
      <td>2.793103</td>
      <td>0.955011</td>
      <td>-0.104241</td>
      <td>0.049892</td>
    </tr>
    <tr>
      <th>898</th>
      <td>3.0</td>
      <td>2.896552</td>
      <td>0.960128</td>
      <td>-0.025551</td>
      <td>0.050302</td>
    </tr>
    <tr>
      <th>899</th>
      <td>3.0</td>
      <td>3.000000</td>
      <td>0.965686</td>
      <td>0.051813</td>
      <td>0.058474</td>
    </tr>
  </tbody>
</table>
<p>900 rows × 5 columns</p>
</div>




```
fig = go.Figure()
fig = ff.create_quiver(x=loss_grad_df['w0'], y=loss_grad_df['w1'],
                       u=loss_grad_df['g0'], v=loss_grad_df['g1'], 
                       line_width=2, line_color="white",
                       scale = 0.1, arrow_scale=.2)
fig.add_trace(go.Contour(x=loss_grad_df['w0'], y=loss_grad_df['w1'], z=loss_grad_df['loss']))
fig.update_layout(margin=dict(l=0, r=0, t=0, b=0), 
                  height=600, width=800)
fig.update_layout(xaxis_range=[w0values.min(), w0values.max()])
fig.update_layout(yaxis_range=[w1values.min(), w1values.max()])
html = plotly.offline.plot(fig, filename='3dplotly.html',include_plotlyjs='cdn')
from IPython.core.display import HTML
HTML(html)
```











<html>
<head><meta charset="utf-8" /></head>
<body>
    <div>

                
            
            <div id="55683ef6-5446-41d8-9f58-7d8475b8c73b" class="plotly-graph-div" style="height:600px; width:800px;"></div>
            
        </div>
</body>
</html>




```
def gradient_descent(w_0, lr = lambda t: 1./(t+1.), nepochs=10):
    w = w_0.copy()
    values = [w]
    for t in range(nepochs):
        w = w - lr(t) * gradient(w)
        values.append(w)
    return np.array(values)
```









```
values = gradient_descent(np.array([3.0, 0.0]), 
                          nepochs=100, 
                          lr =lambda t: 1./np.sqrt(t+1.))
```









```
fig = go.Figure()
fig.add_trace(go.Contour(x=loss_grad_df['w0'], y=loss_grad_df['w1'], z=loss_grad_df['loss']))
fig.add_trace(go.Scatter(x=values[:,0], y=values[:,1], name="Path", mode="markers+lines", 
                     line=go.scatter.Line(color='white')))
fig.update_layout(margin=dict(l=0, r=0, t=0, b=0), 
                  height=600, width=800)
fig.update_layout(xaxis_range=[w0values.min(), w0values.max()])
fig.update_layout(yaxis_range=[w1values.min(), w1values.max()])
html = plotly.offline.plot(fig, filename='3dplotly.html',include_plotlyjs='cdn')
from IPython.core.display import HTML
HTML(html)
```











<html>
<head><meta charset="utf-8" /></head>
<body>
    <div>

                
            
            <div id="9275a496-f64f-48c1-a577-d8cc764c5b3d" class="plotly-graph-div" style="height:600px; width:800px;"></div>
            
        </div>
</body>
</html>




```
fig = go.Figure()
fig.add_trace(
    go.Surface(x=w0values, y=w1values, 
               z=loss_df["loss"].to_numpy().reshape((len(w0values), len(w1values)))))
fig.add_trace(
    go.Scatter3d(x=values[:,1], y=values[:,0], z=[avg_sq_loss(w) for w in values],
                line=dict(color='white')))
fig.update_layout(margin=dict(l=0, r=0, t=0, b=0), 
                  height=600)
html = plotly.offline.plot(fig, filename='3dplotly.html',include_plotlyjs='cdn')
from IPython.core.display import HTML
HTML(html)
```











<html>
<head><meta charset="utf-8" /></head>
<body>
    <div>

                
            
            <div id="f3b18c03-1f9a-4724-b0d8-9b80e007b358" class="plotly-graph-div" style="height:600px; width:100%;"></div>
            
        </div>
</body>
</html>




```
import noise
import numpy as np
import matplotlib
from mpl_toolkits.mplot3d import axes3d
```


```
shape = (50, 50)
scale = 100.0
octaves = 6
persistence = 0.5
lacunarity = 2.0
```


```
world = np.zeros(shape)
for i in range(shape[0]):
  for j in range(shape[1]):
    world[i][j] = noise.pnoise2(i/scale,
                                j/scale,
                                octaves=octaves,
                                persistence=persistence,
                                lacunarity=lacunarity,
                                repeatx=1024,
                                repeaty=1024,
                                base=42)
```


```
import matplotlib.pyplot as plt

plt.imshow(world, cmap='terrain')
```


```
lin_x = np.linspace(0,1,shape[0],endpoint=False)
lin_y = np.linspace(0,1,shape[1],endpoint=False)
x, y = np.meshgrid(lin_x, lin_y)
```


```
fig = plt.figure()
ax = fig.add_subplot(111, projection="3d")
ax.plot_surface(x, y, world, cmap="terrain")
```


```
terrain_cmap = matplotlib.cm.get_cmap('terrain')
def plt_to_plotly(cmap, pl_entries):
  h = 1.0/(pl_entries - 1)
  pl_colorscale = []

  for k in range(pl_entries):
    C = list(map(np.uint8, np.array(cmap(k*h)[:3])*255))
    pl_colorscale.append([k*h, 'rgb'+str((C[0], C[1], C[2]))])
  return pl_colorscale
terrain = plt_to_plotly(terrain_cmap, 255)
```


```
import plotly
import plotly.graph_objects as go
plotly.offline.init_notebook_mode(connected=True)

fig = go.Figure(data=[go.Surface(colorscale=terrain,z=world)])

fig.update_layout(title='Random 3D Terrain')
html = plotly.offline.plot(fig, filename='3d-terrain-plotly.html',include_plotlyjs='cdn')
```







```
from IPython.core.display import HTML
HTML(html)
```




<html>
<head><meta charset="utf-8" /></head>
<body>
    <div>

                
            
            <div id="1d00e941-85e2-4f4c-a39c-34fa64f2725c" class="plotly-graph-div" style="height:100%; width:100%;"></div>
            
        </div>
</body>
</html>



Let us visualise the 3D Terrains, a simple optimization of gradient descent


```
from IPython.core.display import HTML
import plotly
import plotly.graph_objects as go
import noise
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import axes3d
%matplotlib inline
```


```
z = world
plt.imshow(z, origin='lower', cmap='terrain')

# Find maximum value index in numpy array
indices = np.where(z == z.max())
max_z_x_location, max_z_y_location = (indices[1][0], indices[0][0])
plt.plot(max_z_x_location, max_z_y_location, 'ro', markersize=15)

# Find minimum value index in numpy array
indices = np.where(z == z.min())
min_z_x_location, min_z_y_location = (indices[1][0], indices[0][0])
plt.plot(min_z_x_location, min_z_y_location, 'yo', markersize=15)
```


```
import numpy as np
from numpy.lib.stride_tricks import as_strided
```


```
def sliding_window(arr, window_size):
  """
  Slide Window view of array
  """
  arr = np.asarray(arr)
  window_size = int(window_size)
  if arr.ndim!=2:
    raise ValueError("Need 2D input")
  if not(window_size>0):
    raise ValueError("Need positive window size")
  shape = (arr.shape[0] - window_size + 1,
           arr.shape[1] - window_size + 1,
           window_size, window_size)
  if shape[0] <= 0:
    shape = (1, shape[1], arr.shape[0], shape[3])
  if shape[1] <= 0:
    shape = (shape[0], 1, shape[2], arr.shape[1])
  strides = (arr.shape[1]*arr.itemsize, arr.itemsize,
             arr.shape[1]*arr.itemsize, arr.itemsize)
  return as_strided(arr, shape=shape, strides=strides)

def cell_neighbours(arr, i, j, d):
    """Return d-th neighbors of cell (i, j)"""
    w = sliding_window(arr, 2*d+1)

    ix = np.clip(i - d, 0, w.shape[0]-1)
    jx = np.clip(j - d, 0, w.shape[1]-1)

    i0 = max(0, i - d - ix)
    j0 = max(0, j - d - jx)
    i1 = w.shape[2] - max(0, d - i + ix)
    j1 = w.shape[3] - max(0, d - j + jx)

    return w[ix, jx][i0:i1,j0:j1].ravel()
```


```
from dataclasses import dataclass

@dataclass
class descent_step:
  value: float
  x_index: float
  y_index: float

def gradient_descent_3D(array, x_start, y_start, steps=50, step_size=1, plot=False):
  step = descent_step(array[y_start][x_start], x_start, y_start)
  step_history = []
  step_history.append(step)

  # 2D Plotting of array with starting point as red marker
  if plot:
    plt.imshow(array, origin='lower', cmap='terrain')
    plt.plot(x_start, y_start, 'ro')
  current_x = x_start
  current_y = y_start

  for i in range(steps):
    prev_x = current_x
    prev_y = current_y

    neighbours = cell_neighbours(array, current_x, current_y, step_size)

    next_step = neighbours.min()
    indices = np.where(array == next_step)

    current_x, current_y = (indices[1][0], indices[0][0])
    step = descent_step(array[current_y][current_x], current_x, current_y)

    step_history.append(step)

    if plot:
      plt.plot([prev_x, current_x], [prev_y, current_y], 'k-')
      plt.plot(current_x, current_y, 'ro')

    if prev_y == current_y and prev_x == current_x:
      print(f"Converged in {i} steps")
      break
  return next_step, step_history
```


```
np.random.seed(42)
global_minimum = z.min()
indices = np.where(z == global_minimum)
print(f"Target: {global_minimum} @ {indices}")

step_size = 0
found_minimum = 99999

# Random starting point
start_x = np.random.randint(0,50)
start_y = np.random.randint(0,50)

# Increase step size until convergence on global minimum
while found_minimum != global_minimum:
    step_size += 1
    found_minimum,steps = gradient_descent_3D(z,start_x,start_y,step_size=step_size,plot=False)

print(f"Optimal step size {step_size}")
found_minimum,steps = gradient_descent_3D(z,start_x,start_y,step_size=step_size,plot=True)
print(f"Steps: {steps}")
```


```
def multiDimenDist(point1,point2):
   #find the difference between the two points, its really the same as below
   deltaVals = [point2[dimension]-point1[dimension] for dimension in range(len(point1))]
   runningSquared = 0
   #because the pythagarom theorm works for any dimension we can just use that
   for coOrd in deltaVals:
       runningSquared += coOrd**2
   return runningSquared**(1/2)
def findVec(point1,point2,unitSphere = False):
  #setting unitSphere to True will make the vector scaled down to a sphere with a radius one, instead of it's orginal length
  finalVector = [0 for coOrd in point1]
  for dimension, coOrd in enumerate(point1):
      #finding total difference for that co-ordinate(x,y,z...)
      deltaCoOrd = point2[dimension]-coOrd
      #adding total difference
      finalVector[dimension] = deltaCoOrd
  if unitSphere:
      totalDist = multiDimenDist(point1,point2)
      unitVector =[]
      for dimen in finalVector:
          unitVector.append( dimen/totalDist)
      return unitVector
  else:
      return finalVector
```


```
def generate_3d_plot(step_history):
    # Initialise empty lists for markers
    step_markers_x = []
    step_markers_y = []
    step_markers_z = []
    step_markers_u = []
    step_markers_v = []
    step_markers_w = []
    
    for index, step in enumerate(step_history):
        step_markers_x.append(step.x_index)
        step_markers_y.append(step.y_index)
        step_markers_z.append(step.value)
        
        if index < len(steps)-1:
            vec1 = [step.x_index,step.y_index,step.value]
            vec2 = [steps[index+1].x_index,steps[index+1].y_index,steps[index+1].value]

            result_vector = findVec(vec1,vec2)
            step_markers_u.append(result_vector[0])
            step_markers_v.append(result_vector[1])
            step_markers_w.append(result_vector[2])
        else:
            step_markers_u.append(0.1)
            step_markers_v.append(0.1)
            step_markers_w.append(0.1)
    
    fig = go.Figure(data=[
        go.Cone(
        x=step_markers_x,
        y=step_markers_y,
        z=step_markers_z,
        u=step_markers_u,
        v=step_markers_v,
        w=step_markers_w,
        sizemode="absolute",
        sizeref=2,
        anchor='tail'),

        go.Scatter3d(
        x=step_markers_x,
        y=step_markers_y,
        z=step_markers_z,
        mode='lines',
        line=dict(
            color='red',
            width=2
        )),

        go.Surface(colorscale=terrain,z=world,opacity=0.5)])


    fig.update_layout(
        title='Gradient Descent Steps',
        scene = dict(zaxis = dict(range=[world.min(),world.max()],),),)
    return fig
    
# Generate 3D plot from previous random starting location
fig = generate_3d_plot(steps)
HTML(plotly.offline.plot(fig, filename='random_starting_point_3d_gradient_descent.html',include_plotlyjs='cdn'))
```




<html>
<head><meta charset="utf-8" /></head>
<body>
    <div>

                
            
            <div id="9e7a08b1-d84b-40b4-affb-dd6ebca458d6" class="plotly-graph-div" style="height:100%; width:100%;"></div>
            
        </div>
</body>
</html>




```
found_minimum,steps = gradient_descent_3D(z,max_z_x_location,max_z_y_location,step_size=5,plot=True)
fig = generate_3d_plot(steps)
HTML(plotly.offline.plot(fig, filename='maximum_starting_point_step_size_5_3d_gradient_descent.html',include_plotlyjs='cdn'))
```

10204cebdf9ae053a804940521630c5e8d9ebd8f
ipynb
Jupyter Notebook
Day 61/Derivation_GD_Terrain_3D_Plotting.ipynb
vgaurav3011/100-Days-of-ML
ec302b03fd492c459cff2592b3a4f5e38f9c9d72
MIT
2020-03-30T15:10:48.000Z
2021-11-08T06:04:01.000Z
Day 61/Derivation_GD_Terrain_3D_Plotting.ipynb
vgaurav3011/100-Days-of-ML
ec302b03fd492c459cff2592b3a4f5e38f9c9d72
MIT
2021-06-08T22:34:58.000Z
2022-01-13T03:25:23.000Z
Day 61/Derivation_GD_Terrain_3D_Plotting.ipynb
vgaurav3011/100-Days-of-ML
ec302b03fd492c459cff2592b3a4f5e38f9c9d72
MIT
2020-04-13T09:51:28.000Z
2021-04-28T07:37:36.000Z
Qwen/Qwen-72B
1. YES
2. YES