<jupyter_start><jupyter_text>Gradient descent from scratch with Python From the [Data Science from Scratch book](https://www.oreilly.com/library/view/data-science-from/9781492041122/).  Libraries and helper functions<jupyter_code>import random
from typing import List, Callable

import pandas as pd
import altair as alt
Vector = List[float]
Vector
def add(vector1: Vector, vector2: Vector) -> Vector:
    assert len(vector1) == len(vector2)
    return [v1 + v2 for v1, v2 in zip(vector1, vector2)]
def scalar_multiply(c: float, vector: Vector) -> Vector:
    return [c * v for v in vector]
def dot(vector1: Vector, vector2: Vector) -> float:
    assert len(vector1) == len(vector2)

    return sum(v1 * v2 for v1, v2 in zip(vector1, vector2))
def sum_of_squares(v: Vector) -> Vector:
    return dot(v, v)
def magnitude(v: Vector) -> Vector:
    return m.sqrt(sum_of_squares(v))
def distance(vector1: Vector, vector2: Vector) -> Vector:
    return magnitude(subtract(vector1, vector2))
def vector_sum(vectors: List[Vector]) -> Vector:
    assert vectors
    
    vector_length = len(vectors[0])
    assert all(len(v) == vector_length for v in vectors)

    sums = [0] * vector_length
    for vector in vectors:
        sums = add(sums, vector)

    return sums
def vector_mean(vectors: List[Vector]) -> Vector:
    n = len(vectors)
    return scalar_multiply(1/n, vector_sum(vectors))<jupyter_output><empty_output><jupyter_text>Estimate gradient<jupyter_code>def estimate_gradient(
    f: Callable[[Vector], float],
    v: Vector,
    h: float = 0.0001
):
    return [
        partial_difference_quotient(f, v, i, h)
        for i in range(len(v))
    ]
v = [random.uniform(-10, 10) for i in range(3)]
v<jupyter_output><empty_output><jupyter_text>Adjusting with gradients<jupyter_code>def gradient_step(v: Vector, gradient: Vector, step_size: float) -> Vector:
    """Return vector adjusted with step. Step is gradient times step size.
    """
    step = scalar_multiply(step_size, gradient)
    return add(v, step)

v, gradient_step(v, [1, 1, 1], step_size=0.1)
def sum_of_squares_gradient(v: Vector) -> Vector:
    return [2 * v_i for v_i in v]

sum_of_squares_gradient(v)
steps = pd.DataFrame()

for epoch in range(1000):
    grad = sum_of_squares_gradient(v)
    v = gradient_step(v, grad, -0.01)
    steps = steps.append(
        {'x': v[0], 'y': v[1], 'z': v[2]}, ignore_index=True
    )

steps
alt.Chart(steps.reset_index().melt(id_vars='index')).mark_point().encode(
    alt.X('index:Q'), alt.Y('value:Q'), alt.Color('variable:N')
).properties(title='Gradient steps')<jupyter_output><empty_output><jupyter_text>Changing the step size<jupyter_code>inputs = [(x, 20 * x + 5) for x in range(-50, 50)]
inputs[:20]<jupyter_output><empty_output><jupyter_text>We use a simple linear gradient<jupyter_code>def linear_gradient(x: float, y: float, theta: Vector) -> Vector:
    slope, intercept = theta
    predicted = slope * x + intercept
    error = (predicted - y) #** 2
    return [2 * error * x, 2 * error]
    

x, y = inputs[0][0], inputs[0][1]
theta = [random.uniform(-1, 1), random.uniform(-1, 1)]

x, y, theta, linear_gradient(x, y, theta)    
theta = [random.uniform(-1, 1), random.uniform(-1, 1)]

learning_rate = 0.001

for epoch in range(20):
    grad = vector_mean([linear_gradient(x, y, theta) for x, y in inputs])
    theta = gradient_step(theta, grad, -learning_rate)
    print(epoch, theta)<jupyter_output>0 [32.89133392765593, 0.47755932457342315]
1 [11.396957829578067, 0.4994955398519324]
2 [25.733728623211277, 0.49989350660180654]
3 [16.171102901824685, 0.5146274482118142]
4 [22.549388991931146, 0.5197692962172151]
5 [18.295077311678142, 0.5312791466167119]
6 [21.132714712257297, 0.5385116656351566]
7 [19.24001779859002, 0.5485673570161436]
8 [20.50245669569747, 0.5567102401007012]
9 [19.660418094209888, 0.5660992763161973]
10 [20.22206723043832, 0.5746274958577747]
11 [19.8474557847935, 0.5837003080964975]
12 [20.097330691850832, 0.592380363265098]
13 [19.93067280889876, 0.6012929332304187]
14 [20.04184252939776, 0.6100210201728566]
15 [19.967701053911867, 0.6188428206619087]
16 [20.017162239861445, 0.6275728360744967]
17 [19.98418035884849, 0.6363348526422091]
18 [20.0061880355007, 0.6450463632957731]
19 [19.99151762668433, 0.6537624586046823]
{'fraction_non_alphanumeric': 0.1340808222377949, 'fraction_numerical': 0.18570427470217238, 'mean_word_length': 4.755376344086022, 'pattern_counts': {'":': 0, '<': 20, '<?xml version=': 0, '>': 31, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '337804', 'license': 'Apache-2.0', 'n_tokens_mistral': 2114, 'n_tokens_neox': 1645, 'n_words': 382, 'path': '_notebooks/2020-10-20-gradient-descent.ipynb', 'repo_name': 'nocibambi/ds_blog', 'size': '4281'}