#!/usr/bin/env python3
"""
verify_mlp_claims.py
Purpose : compute every number quoted in WHY-THE-MLP-LEARNS.md, so the document
          states nothing about the arithmetic that was not run.
Usage   : python3 verify_mlp_claims.py        (writes verify_results.json beside itself)
Needs   : Python 3 and numpy. No network, no GPU. About two minutes on a laptop.
Author  : written 2026-11-14 for the MLP explainer.
"""
import json
import pathlib
import time

import numpy as np

R = {}


def relu(z):
    return np.maximum(0.0, z)


# The four XOR points used throughout.
X = np.array([[0, 0], [1, 0], [0, 1], [1, 1]], float)
T = np.array([0, 1, 1, 0], float)

# ---------------------------------------------------------------- A
# The fold used on the Q&A page "why nonlinearity matters":
# h1 = ReLU(x1 - x2), h2 = ReLU(x2 - x1), yhat = h1 + h2.
h1 = relu(X[:, 0] - X[:, 1])
h2 = relu(X[:, 1] - X[:, 0])
yh = h1 + h2
R["A_xor_fold"] = {
    "h1": h1.tolist(), "h2": h2.tolist(), "yhat": yh.tolist(), "target": T.tolist(),
    "all_four_right_at_threshold_0.5": bool(((yh > 0.5) == (T > 0.5)).all()),
}

# ---------------------------------------------------------------- B
# B1. One weight: yhat = w*x, x=2, t=1, w=0.25, step 0.1.
x, t, w, lr = 2.0, 1.0, 0.25, 0.1
y0 = w * x
L0 = 0.5 * (y0 - t) ** 2
slope = (y0 - t) * x
w1 = w - lr * slope
y1 = w1 * x
L1 = 0.5 * (y1 - t) ** 2
R["B1_one_weight"] = {"yhat": y0, "loss": L0, "slope": slope, "w_new": w1,
                      "yhat_new": y1, "loss_new": round(L1, 6)}

# B2. The Q&A page's chain: yhat = v*ReLU(w*x), x=2, w=v=0.5, t=1, step 0.1.
x, t, w, v, lr = 2.0, 1.0, 0.5, 0.5, 0.1
h = relu(w * x)
y0 = v * h
L0 = 0.5 * (y0 - t) ** 2
gv = (y0 - t) * h
gw = (y0 - t) * v * (1.0 if w * x > 0 else 0.0) * x
wn, vn = w - lr * gw, v - lr * gv
hn = relu(wn * x)
yn = vn * hn
Ln = 0.5 * (yn - t) ** 2
R["B2_two_weight_chain"] = {"h": h, "yhat": y0, "loss": L0, "slope_v": gv, "slope_w": gw,
                            "w_new": wn, "v_new": vn, "yhat_new": round(yn, 6),
                            "loss_new": round(Ln, 6)}


# ---------------------------------------------------------------- C, L
# A small ReLU network with biases: 3 inputs, rows of 4 and 3 hidden units, 2 outputs.
def forward(xv, W, b):
    a, g = [xv], []
    for l in range(len(W)):
        z = W[l] @ a[-1] + b[l]
        if l < len(W) - 1:
            g.append((z > 0).astype(float))
            a.append(relu(z))
        else:
            a.append(z)
    return a, g


rng = np.random.default_rng(7)
sizes = [3, 4, 3, 2]
W = [rng.normal(size=(sizes[i + 1], sizes[i])) for i in range(3)]
b = [rng.normal(size=sizes[i + 1]) for i in range(3)]
# Pick an input that leaves at least two gates open in each hidden row, so the
# path sum below is not made of offset paths alone.
for _ in range(1000):
    xv = rng.normal(size=3)
    a, g = forward(xv, W, b)
    if g[0].sum() >= 2 and g[1].sum() >= 2:
        break

# C1. The output equals a sum over every path, each path being the product of the
# weights along it, counted only if every gate on it is open.
out = np.zeros(2)
n_paths = n_open = 0
for m in range(2):
    for k in range(3):
        for j in range(4):
            for i in range(3):
                n_paths += 1
                n_open += int(g[0][j] * g[1][k] > 0)
                out[m] += xv[i] * W[0][j, i] * g[0][j] * W[1][k, j] * g[1][k] * W[2][m, k]
            out[m] += b[0][j] * g[0][j] * W[1][k, j] * g[1][k] * W[2][m, k]
        out[m] += b[1][k] * g[1][k] * W[2][m, k]
    out[m] += b[2][m]
R["C1_path_sum"] = {
    "input_to_output_paths": n_paths, "open_for_this_input": n_open,
    "gates_row1": g[0].tolist(), "gates_row2": g[1].tolist(),
    "max_abs_difference_from_ordinary_forward_pass": float(np.abs(out - a[-1]).max()),
}

# C2. Sensitivity of an output to one first-row weight equals
# (level on the sending slot) x (gate of the receiving slot) x (sum over open
# downstream paths of the product of their weights). Compared with a direct nudge.
eps = 1e-6
worst = 0.0
for m in range(2):
    for j in range(4):
        for i in range(3):
            formula = xv[i] * g[0][j] * sum(W[1][k, j] * g[1][k] * W[2][m, k] for k in range(3))
            Wp = [w_.copy() for w_ in W]
            Wp[0][j, i] += eps
            Wm = [w_.copy() for w_ in W]
            Wm[0][j, i] -= eps
            nudge = (forward(xv, Wp, b)[0][-1][m] - forward(xv, Wm, b)[0][-1][m]) / (2 * eps)
            worst = max(worst, abs(formula - nudge))
R["C2_weight_sensitivity"] = {"max_abs_difference_formula_vs_nudge": float(worst)}

# L. For one input, the whole network is a single table of numbers (plus offsets).
D0, D1 = np.diag(g[0]), np.diag(g[1])
W_eff = W[2] @ D1 @ W[1] @ D0 @ W[0]
b_eff = W[2] @ D1 @ (W[1] @ D0 @ b[0] + b[1]) + b[2]
near = xv + 1e-4 * rng.normal(size=3)
a2, g2 = forward(near, W, b)
same_gates = bool(all((g[i] == g2[i]).all() for i in range(2)))
# How many different gate patterns does this 7-unit network use over many inputs?
pats = set()
for _ in range(200000):
    _, gg = forward(rng.normal(size=3) * 2.0, W, b)
    pats.add(tuple(gg[0].astype(int)) + tuple(gg[1].astype(int)))
R["L_one_input_one_linear_map"] = {
    "max_abs_difference_this_input": float(np.abs(W_eff @ xv + b_eff - a[-1]).max()),
    "nearby_input_has_same_gates": same_gates,
    "max_abs_difference_nearby_input": float(np.abs(W_eff @ near + b_eff - a2[-1]).max()),
    "distinct_gate_patterns_seen_in_200000_random_inputs": len(pats),
    "possible_patterns_2^7": 2 ** 7,
}


# ---------------------------------------------------------------- K, J
# Backward sweep versus nudging each weight, on a 20-64-64-10 network.
def init(sz, r):
    return ([r.normal(size=(sz[i + 1], sz[i])) / np.sqrt(sz[i]) for i in range(len(sz) - 1)],
            [np.zeros(sz[i + 1]) for i in range(len(sz) - 1)])


def loss_only(xv, tv, W, b):
    a_, _ = forward(xv, W, b)
    return 0.5 * float(((a_[-1] - tv) ** 2).sum())


def backprop(xv, tv, W, b):
    a_, g_ = forward(xv, W, b)
    delta = a_[-1] - tv                      # blame on the bottom row
    gW, gb = [None] * len(W), [None] * len(W)
    for l in reversed(range(len(W))):
        gW[l] = np.outer(delta, a_[l])       # blame at receiver x level at sender
        gb[l] = delta.copy()
        if l > 0:
            delta = (W[l].T @ delta) * g_[l - 1]   # back up the same wires, stop at shut gates
    return gW, gb


sz = [20, 64, 64, 10]
r2 = np.random.default_rng(11)
Wn, bn = init(sz, r2)
bn = [r2.normal(size=v_.shape) * 0.1 for v_ in bn]
xin, tin = r2.normal(size=20), r2.normal(size=10)
n_params = sum(w_.size for w_ in Wn) + sum(v_.size for v_ in bn)

t0 = time.perf_counter()
for _ in range(200):
    gW, gb = backprop(xin, tin, Wn, bn)
t_bp = (time.perf_counter() - t0) / 200

t0 = time.perf_counter()
eps = 1e-5
worst = 0.0
passes = 0
for l in range(3):
    for idx in np.ndindex(Wn[l].shape):
        old = Wn[l][idx]
        Wn[l][idx] = old + eps
        lp = loss_only(xin, tin, Wn, bn)
        Wn[l][idx] = old - eps
        lm = loss_only(xin, tin, Wn, bn)
        Wn[l][idx] = old
        passes += 2
        worst = max(worst, abs((lp - lm) / (2 * eps) - gW[l][idx]))
    for idx in np.ndindex(bn[l].shape):
        old = bn[l][idx]
        bn[l][idx] = old + eps
        lp = loss_only(xin, tin, Wn, bn)
        bn[l][idx] = old - eps
        lm = loss_only(xin, tin, Wn, bn)
        bn[l][idx] = old
        passes += 2
        worst = max(worst, abs((lp - lm) / (2 * eps) - gb[l][idx]))
t_fd = time.perf_counter() - t0
R["KJ_backward_sweep_vs_nudging"] = {
    "adjustable_numbers": int(n_params),
    "forward_passes_needed_by_nudging_two_sided": passes,
    "forward_passes_needed_by_nudging_one_sided": int(n_params) + 1,
    "max_abs_difference_between_the_two_answers": float(worst),
    "seconds_backward_sweep": t_bp, "seconds_nudging": t_fd,
    "time_ratio": t_fd / t_bp,
}

# ---------------------------------------------------------------- D
# The change in a row of weights is a signed sum of the inputs that row saw.
r3 = np.random.default_rng(3)
Bmix = r3.normal(size=(3, 10))               # inputs live in a 3-dimensional slice of 10-D
Zlat = r3.normal(size=(400, 3))
Xd = Zlat @ Bmix
Yd = np.sin(Zlat[:, 0]) + Zlat[:, 1] * Zlat[:, 2]
Wd, bd = init([10, 16, 1], r3)
W1_start = Wd[0].copy()
acc = np.zeros_like(Wd[0])
eta = 0.01
for step in range(4000):
    n = r3.integers(0, 400)
    gW, gb = backprop(Xd[n], np.array([Yd[n]]), Wd, bd)
    acc += gW[0]
    for l in range(2):
        Wd[l] -= eta * gW[l]
        bd[l] -= eta * gb[l]
dW1 = Wd[0] - W1_start
# Component of the change that lies outside the span of the inputs:
Q, _ = np.linalg.qr(Bmix.T)                  # 10x3 basis of the input slice
outside = dW1 - (dW1 @ Q) @ Q.T
loss_before = float(np.mean([loss_only(Xd[n], np.array([Yd[n]]), [W1_start, Wd[1] * 0 + 0], bd) for n in range(0)] or [0]))
R["D_weights_are_built_from_inputs"] = {
    "max_abs_difference_final_minus_start_vs_minus_eta_times_sum_of_blame_times_input":
        float(np.abs(dW1 - (-eta * acc)).max()),
    "size_of_weight_change": float(np.linalg.norm(dW1)),
    "size_of_the_part_outside_the_span_of_the_inputs": float(np.linalg.norm(outside)),
}

# ---------------------------------------------------------------- E
# Does a nudge of 0.001 to one weight change the error at all?
# 2-2-1 networks on the four XOR points, three kinds of unit.
def err_for(act, W1, b1, W2, b2):
    Z = X @ W1.T + b1
    if act == "step":
        Hh = (Z > 0).astype(float)
    elif act == "relu":
        Hh = relu(Z)
    else:
        Hh = 1.0 / (1.0 + np.exp(-Z))
    Y = Hh @ W2 + b2
    return 0.5 * float(((Y - T) ** 2).mean())


r4 = np.random.default_rng(5)
trials = 20000
nud = 1e-3
res = {}
for act in ("step", "relu", "sigmoid"):
    hid_changed = hid_total = last_changed = last_total = 0
    for _ in range(trials):
        W1 = r4.uniform(-1, 1, size=(2, 2)); b1 = r4.uniform(-1, 1, size=2)
        W2 = r4.uniform(-1, 1, size=2); b2 = r4.uniform(-1, 1)
        base = err_for(act, W1, b1, W2, b2)
        for idx in np.ndindex(2, 2):
            Wp = W1.copy(); Wp[idx] += nud
            hid_changed += abs(err_for(act, Wp, b1, W2, b2) - base) > 1e-13
            hid_total += 1
        for j in range(2):
            bp_ = b1.copy(); bp_[j] += nud
            hid_changed += abs(err_for(act, W1, bp_, W2, b2) - base) > 1e-13
            hid_total += 1
            Wq = W2.copy(); Wq[j] += nud
            last_changed += abs(err_for(act, W1, b1, Wq, b2) - base) > 1e-13
            last_total += 1
        last_changed += abs(err_for(act, W1, b1, W2, b2 + nud) - base) > 1e-13
        last_total += 1
    res[act] = {"hidden_row_nudges_that_changed_the_error_percent": round(100 * hid_changed / hid_total, 2),
                "last_row_nudges_that_changed_the_error_percent": round(100 * last_changed / last_total, 2)}
R["E_does_a_small_nudge_register"] = {"networks": trials, "nudge": nud, **res}

# E2. Sweep one hidden weight across its range in one fixed network and count how
# many different error values appear. Shelves with jumps, or a continuous curve?
r5 = np.random.default_rng(21)
W1 = r5.uniform(-1, 1, size=(2, 2)); b1 = r5.uniform(-1, 1, size=2)
W2 = r5.uniform(-1, 1, size=2); b2 = r5.uniform(-1, 1)
sweep = np.linspace(-2, 2, 4001)
e2 = {}
for act in ("step", "relu", "sigmoid"):
    vals = []
    for wv in sweep:
        Wp = W1.copy(); Wp[0, 0] = wv
        vals.append(round(err_for(act, Wp, b1, W2, b2), 12))
    e2[act] = {"settings_tried": len(sweep), "different_error_values": len(set(vals))}
R["E2_sweep_one_hidden_weight"] = e2

# M. With a softmax and cross-entropy at the bottom, the blame on each score is
# (probability given) minus (1 for the right bin, 0 for the others).
r6 = np.random.default_rng(9)
zs = r6.normal(size=5); right = 2
def xent(zv):
    p = np.exp(zv - zv.max()); p /= p.sum()
    return -float(np.log(p[right]))
p = np.exp(zs - zs.max()); p /= p.sum()
onehot = np.zeros(5); onehot[right] = 1.0
fd = np.array([(xent(zs + 1e-6 * np.eye(5)[i]) - xent(zs - 1e-6 * np.eye(5)[i])) / 2e-6 for i in range(5)])
R["M_softmax_blame_is_probability_minus_target"] = {
    "max_abs_difference": float(np.abs(fd - (p - onehot)).max())}


# ---------------------------------------------------------------- F
# How often does plain gradient descent solve XOR, as the hidden row gets wider?
def xor_trials(H, S, steps, lr, seed):
    r = np.random.default_rng(seed)
    k1, k2 = 1 / np.sqrt(2), 1 / np.sqrt(H)
    W1 = r.uniform(-k1, k1, size=(S, H, 2)); B1 = r.uniform(-k1, k1, size=(S, H))
    W2 = r.uniform(-k2, k2, size=(S, H)); B2 = r.uniform(-k2, k2, size=(S,))
    for _ in range(steps):
        Z = np.einsum("shi,ni->snh", W1, X) + B1[:, None, :]
        Hh = np.maximum(Z, 0.0)
        Y = np.einsum("snh,sh->sn", Hh, W2) + B2[:, None]
        E = (Y - T[None, :]) / 4.0
        dH = E[:, :, None] * W2[:, None, :] * (Z > 0)
        W2 -= lr * np.einsum("sn,snh->sh", E, Hh)
        B2 -= lr * E.sum(1)
        W1 -= lr * np.einsum("snh,ni->shi", dH, X)
        B1 -= lr * dH.sum(1)
    Z = np.einsum("shi,ni->snh", W1, X) + B1[:, None, :]
    Y = np.einsum("snh,sh->sn", np.maximum(Z, 0.0), W2) + B2[:, None]
    ok_fit = (np.abs(Y - T[None, :]) < 0.05).all(1)
    ok_cls = ((Y > 0.5) == (T[None, :] > 0.5)).all(1)
    bad = ~np.isfinite(Y).all(1)
    return float(ok_fit.mean()), float(ok_cls.mean()), float(bad.mean())


widths = [1, 2, 3, 4, 8, 16, 32]
S, steps, lr = 2000, 20000, 0.1
tab = {}
for H in widths:
    fit, cls, bad = xor_trials(H, S, steps, lr, seed=100 + H)
    tab[str(H)] = {"solved_within_0.05_percent": round(100 * fit, 1),
                   "all_four_on_right_side_of_0.5_percent": round(100 * cls, 1),
                   "diverged_percent": round(100 * bad, 1)}
R["F_xor_success_by_width"] = {"starts_per_width": S, "steps": steps, "step_size": lr,
                              "start": "uniform(-1/sqrt(fan_in), 1/sqrt(fan_in)) weights and offsets",
                              "by_hidden_width": tab}

# F2. Are the failures stuck, or only slow? Same starts, five times as many steps,
# and separately a smaller step size.
f2 = {}
for H in (2, 4, 8):
    fit_long, _, _ = xor_trials(H, 2000, 100000, 0.1, seed=100 + H)
    fit_small, _, _ = xor_trials(H, 2000, 100000, 0.03, seed=100 + H)
    f2[str(H)] = {"solved_percent_100000_steps_step_0.1": round(100 * fit_long, 1),
                  "solved_percent_100000_steps_step_0.03": round(100 * fit_small, 1)}
R["F2_xor_longer_runs"] = f2

# ---------------------------------------------------------------- G
# A sum of hinges that follows sin(x) on [0, 2*pi].
grid = np.linspace(0, 2 * np.pi, 200001)
gtab = {}
for n in (4, 8, 16, 32, 64):
    c = np.linspace(0, 2 * np.pi, n + 1)
    f = np.sin(c)
    slopes = np.diff(f) / np.diff(c)
    coef = np.concatenate([[slopes[0]], np.diff(slopes)])   # each hinge changes the slope by this much
    approx = f[0] + sum(coef[i] * relu(grid - c[i]) for i in range(n))
    gtab[str(n)] = {"hinges": n, "largest_miss": round(float(np.abs(approx - np.sin(grid)).max()), 5)}
R["G_hinges_following_a_sine"] = gtab

# ---------------------------------------------------------------- I
# Folding: the tent map 2*ReLU(x) - 4*ReLU(x - 0.5), applied k times, on [0, 1].
xs = np.linspace(0, 1, 2 ** 16 + 1)
itab = {}
y = xs.copy()
for k in range(1, 9):
    y = 2 * relu(y) - 4 * relu(y - 0.5)
    s = np.sign(np.diff(y))
    pieces = 1 + int((s[1:] != s[:-1]).sum())
    itab[str(k)] = {"rows": k, "hidden_units_used": 2 * k, "straight_pieces": pieces,
                    "units_one_row_would_need": pieces - 1}
R["I_folding_by_depth"] = itab

out_path = pathlib.Path(__file__).with_name("verify_results.json")
out_path.write_text(json.dumps(R, indent=2))
print(json.dumps(R, indent=2))
