Optimization Algorithms¶

Need not be just gradient-based

• The algorithms from AI course can also be used
• Even brute force is fine for small datasets; since this evaluates all possibilities and does not take any approximations/gradients, this would be robust to noisy data

Gradient-based algorithms are preferred for large datasets

Rule of thumb: recommended learning rate \(\eta = 3e^{-4}\)

Newton’s Method¶

Integrates more “global” structure into optimization methods, which scales gradients according to the inverse of the Hessian Equivalent to approximating the function as quadratic using second-order Taylor expansion, then solving for optimal solution

• \(\eta=1:\) Full step
• o.w: Damped Newton method

Brute-Force Regression¶

m_hat = (0, 5, 0.1) # min, max, precision
c_hat = (0, 5, 0.1) # min, max, precision

Imports¶

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

Generate Synthetic Data¶

\(y = mx + c\)

def equation(x, m, c):
  return m*x + c

x = np.arange(1, 10+1, 1)

m_true = 2
c_true = 3
y = equation(x, m_true, c_true)

m_hat_range = np.arange(m_hat[0], m_hat[1]+m_hat[2], m_hat[2])
c_hat_range = np.arange(c_hat[0], c_hat[1]+c_hat[2], c_hat[2])

data = (
  np.column_stack(
    (
        x,
        y
    ),
  )
)

m, c = (
  np.meshgrid(
    m_hat_range,
    c_hat_range
  )
)
params = (
  np.column_stack(
    (
        m.flatten(),
        c.flatten()
    ),
  )
)

df = pd.DataFrame(
    data = np.column_stack(
        (
            np.tile(data, (params.shape[0], 1)),
            np.tile(params, (data.shape[0], 1))
        )
    ),
    columns = ["x", "y", "m", "c"]
)

Forward Pass¶

df["pred"] = equation(df["x"], df["m"], df["c"])

Backward Pass¶

df["error"] = df["pred"] - df["y"]
df["loss"] = df["error"]**2

Results¶

results = (
    df
    .groupby(["m", "c"])
    ["loss"]
    .mean()
    .reset_index()
    .rename(columns = {
        "loss": "cost"
    })
)

Loss Landscape¶

fig, ax = plt.subplots()

ax = plt.tricontourf(
    results["m"],
    results["c"],
    results["cost"].pow(0.1),
    levels = 1_000,
    cmap="Reds_r"
)
fig.colorbar(ax)
plt.show()

Most Optimal Parameters¶

(
    results
    .sort_values("cost", ascending=True)
    .reset_index(drop=True)
    .head(5)
)

Gradient Descent¶

Similar to trial and error

1. Start with some \(\theta\) vector
2. Keep changing \(\theta_0, \theta_1, \dots, \theta_n\) using derivative of cost function, until minimum for \(J(\theta)\) is obtained - Simultaneously

Gradients of the Loss Function¶

Learning Rate \(\eta\)¶

\(0 < \eta < 1\)

• Large value may lead to underfitting/overfitting
• Small value will lead to more time taken

Rule of thumb: recommended learning rate \(\eta = 3 e {-4}\)

Can be

• constant
• decay
  • Step: \(\alpha_t = \alpha_{t-a}/2\)
    • Decay by half every few epochs
  • Exponential: \(\alpha_t = \alpha_0 e^{-kt}\)
  • 1/t: \(\alpha_t = \alpha_0/(1+kt)\)

Iterative vs Normal Equation¶

Gradient-based methods find min of a function by moving in the direction in which the function decreases most steeply

Comments