"""A tiny tensor autograd engine written from scratch on top of numpy. Every op records how to push gradients back to its inputs (reverse-mode autodiff). No ML libraries are used anywhere in this project. """ import numpy as np DT = np.float32 def _unbroadcast(g, shape): # Sum gradient back down to the input's shape after numpy broadcasting. while g.ndim > len(shape): g = g.sum(0) for i, s in enumerate(shape): if s == 1 and g.shape[i] != 1: g = g.sum(i, keepdims=True) return g class T: def __init__(self, data, parents=(), back=None, req=False): self.data = np.asarray(data, dtype=DT) self.grad = None self.parents = parents self._back = back self.req = req or any(p.req for p in parents) shape = property(lambda s: s.data.shape) # ---- graph traversal ---- def backward(self, g=None): order, seen = [], set() def visit(t): if id(t) in seen or not t.req: return seen.add(id(t)) for p in t.parents: visit(p) order.append(t) visit(self) self.grad = np.ones_like(self.data) if g is None else g for t in reversed(order): if t._back is not None and t.grad is not None: t._back(t.grad) def _acc(self, g): if not self.req: return self.grad = g if self.grad is None else self.grad + g # ---- elementwise ---- def __add__(a, b): b = b if isinstance(b, T) else T(b) out = T(a.data + b.data, (a, b)) out._back = lambda g: (a._acc(_unbroadcast(g, a.shape)), b._acc(_unbroadcast(g, b.shape))) return out def __sub__(a, b): return a + (b * -1.0 if isinstance(b, T) else T(-np.asarray(b))) def __mul__(a, b): b = b if isinstance(b, T) else T(b) out = T(a.data * b.data, (a, b)) out._back = lambda g: (a._acc(_unbroadcast(g * b.data, a.shape)), b._acc(_unbroadcast(g * a.data, b.shape))) return out __radd__ = __add__ __rmul__ = __mul__ def relu(a): m = a.data > 0 out = T(a.data * m, (a,)) out._back = lambda g: a._acc(g * m) return out def gelu(a): x = a.data c = np.sqrt(2 / np.pi) t = np.tanh(c * (x + 0.044715 * x ** 3)) out = T(0.5 * x * (1 + t), (a,)) def back(g): dt = (1 - t ** 2) * c * (1 + 3 * 0.044715 * x ** 2) a._acc(g * (0.5 * (1 + t) + 0.5 * x * dt)) out._back = back return out # ---- shapes ---- def __matmul__(a, b): out = T(a.data @ b.data, (a, b)) def back(g): a._acc(_unbroadcast(g @ np.swapaxes(b.data, -1, -2), a.shape)) b._acc(_unbroadcast(np.swapaxes(a.data, -1, -2) @ g, b.shape)) out._back = back return out def reshape(a, *s): out = T(a.data.reshape(*s), (a,)) out._back = lambda g: a._acc(g.reshape(a.shape)) return out def transpose(a, *ax): out = T(a.data.transpose(*ax), (a,)) inv = np.argsort(ax) out._back = lambda g: a._acc(g.transpose(*inv)) return out def sum(a, axis=None, keepdims=False): out = T(a.data.sum(axis, keepdims=keepdims), (a,)) def back(g): if axis is not None and not keepdims: g = np.expand_dims(g, axis) a._acc(np.broadcast_to(g, a.shape).copy()) out._back = back return out def mean(a, axis=None, keepdims=False): n = a.data.size if axis is None else a.shape[axis] return a.sum(axis, keepdims) * (1.0 / n) def max(a, axis): idx = a.data.argmax(axis) out = T(a.data.max(axis), (a,)) def back(g): gg = np.zeros_like(a.data) np.put_along_axis(gg, np.expand_dims(idx, axis), np.expand_dims(g, axis), axis) a._acc(gg) out._back = back return out def softmax(a, axis=-1): e = np.exp(a.data - a.data.max(axis, keepdims=True)) s = e / e.sum(axis, keepdims=True) out = T(s, (a,)) out._back = lambda g: a._acc(s * (g - (g * s).sum(axis, keepdims=True))) return out def layernorm(a, w, b, eps=1e-5): x = a.data mu = x.mean(-1, keepdims=True) var = x.var(-1, keepdims=True) inv = 1 / np.sqrt(var + eps) xh = (x - mu) * inv out = T(xh * w.data + b.data, (a, w, b)) def back(g): w._acc(_unbroadcast(g * xh, w.shape)) b._acc(_unbroadcast(g, b.shape)) gx = g * w.data n = x.shape[-1] a._acc(inv / n * (n * gx - gx.sum(-1, keepdims=True) - xh * (gx * xh).sum(-1, keepdims=True))) out._back = back return out def concat(ts, axis): out = T(np.concatenate([t.data for t in ts], axis), tuple(ts)) sizes = np.cumsum([t.shape[axis] for t in ts])[:-1] def back(g): for t, gg in zip(ts, np.split(g, sizes, axis)): t._acc(gg) out._back = back return out def embed(table, idx): out = T(table.data[idx], (table,)) def back(g): gg = np.zeros_like(table.data) np.add.at(gg, idx, g) table._acc(gg) out._back = back return out def cross_entropy(logits, target, soft=False): """Mean cross-entropy over the last axis. target: int labels or soft distributions.""" x = logits.data e = np.exp(x - x.max(-1, keepdims=True)) p = e / e.sum(-1, keepdims=True) if soft: q = target else: q = np.zeros_like(p) np.put_along_axis(q, target[..., None], 1.0, -1) n = int(np.prod(x.shape[:-1])) loss = -(q * np.log(p + 1e-9)).sum() / n out = T(loss, (logits,)) out._back = lambda g: logits._acc(g * (p - q) / n) return out class Param(T): def __init__(self, *shape, scale=None, init=None): if init is not None: d = np.full(shape, init) else: scale = scale if scale is not None else 1 / np.sqrt(shape[0]) d = np.random.randn(*shape) * scale super().__init__(d, req=True) class Adam: def __init__(self, params, lr=1e-3, b1=0.9, b2=0.99, wd=0.0): self.p, self.lr, self.b1, self.b2, self.wd = params, lr, b1, b2, wd self.m = [np.zeros_like(p.data) for p in params] self.v = [np.zeros_like(p.data) for p in params] self.t = 0 def step(self, lr=None): lr = lr or self.lr self.t += 1 for p, m, v in zip(self.p, self.m, self.v): if p.grad is None: continue g = np.clip(p.grad, -5, 5) m *= self.b1; m += (1 - self.b1) * g v *= self.b2; v += (1 - self.b2) * g * g mh = m / (1 - self.b1 ** self.t) vh = v / (1 - self.b2 ** self.t) p.data -= lr * (mh / (np.sqrt(vh) + 1e-8) + self.wd * p.data) p.grad = None class Linear: def __init__(self, i, o): self.w = Param(i, o, scale=np.sqrt(2 / i)) self.b = Param(o, init=0.0) self.params = [self.w, self.b] def __call__(self, x): return x @ self.w + self.b def gradcheck(): np.random.seed(0) a = Param(3, 4); b = Param(4, 5) w = Param(5, init=1.0); bb = Param(5, init=0.0) f = lambda: ((a @ b).gelu().layernorm(w, bb).softmax() * T(np.arange(5.0))).max(1).sum() f().backward() num = np.zeros_like(a.data); eps = 1e-3 for i in np.ndindex(a.shape): a.data = a.data.astype(np.float64) old = a.data[i]; a.data[i] = old + eps; fp = f().data a.data[i] = old - eps; fm = f().data; a.data[i] = old num[i] = (fp - fm) / (2 * eps) print("gradcheck max err", np.abs(num - a.grad).max()) if __name__ == "__main__": gradcheck() def index(t, key): """Fancy-index a tensor (numpy semantics); gradient scatters back.""" out = T(t.data[key], (t,)) def back(g): gg = np.zeros_like(t.data) np.add.at(gg, key, g) t._acc(gg) out._back = back return out