{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "JnGHatCI51JP"
   },
   "source": [
    "# micrograd exercises\n",
    "\n",
    "1. watch the [micrograd video](https://www.youtube.com/watch?v=VMj-3S1tku0) on YouTube\n",
    "2. come back and complete these exercises to level up :)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "OFt6NKOz6iBZ"
   },
   "source": [
    "## section 1: derivatives"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "id": "3Jx9fCXl5xHd"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6.336362190988558\n"
     ]
    }
   ],
   "source": [
    "# here is a mathematical expression that takes 3 inputs and produces one output\n",
    "from math import sin, cos\n",
    "\n",
    "def f(a, b, c):\n",
    "  return -a**3 + sin(3*b) - 1.0/c + b**2.5 - a**0.5\n",
    "\n",
    "print(f(2, 3, 4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "id": "qXaH59eL9zxf"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "OK for dim 0: expected -12.353553390593273, yours returns -12.353553390593273\n",
      "OK for dim 1: expected 10.25699027111255, yours returns 10.25699027111255\n",
      "OK for dim 2: expected 0.0625, yours returns 0.0625\n"
     ]
    }
   ],
   "source": [
    "# write the function df that returns the analytical gradient of f\n",
    "# i.e. use your skills from calculus to take the derivative, then implement the formula\n",
    "# if you do not calculus then feel free to ask wolframalpha, e.g.:\n",
    "# https://www.wolframalpha.com/input?i=d%2Fda%28sin%283*a%29%29%29\n",
    "\n",
    "def gradf(a, b, c):\n",
    "    dfda = -3*(a**2) - 0.5*(a**-0.5)\n",
    "    dfdb = 3*cos(3*b) + 2.5*(b**1.5)\n",
    "    dfdc = c**-2\n",
    "    return [dfda, dfdb, dfdc] # todo, return [df/da, df/db, df/dc]\n",
    "\n",
    "# expected answer is the list of\n",
    "ans = [-12.353553390593273, 10.25699027111255, 0.0625]\n",
    "yours = gradf(2, 3, 4)\n",
    "for dim in range(3):\n",
    "  ok = 'OK' if abs(yours[dim] - ans[dim]) < 1e-5 else 'WRONG!'\n",
    "  print(f\"{ok} for dim {dim}: expected {ans[dim]}, yours returns {yours[dim]}\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "id": "_27n-KTA9Qla"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "OK for dim 0: expected -12.353553390593273, yours returns -12.353559348809995\n",
      "OK for dim 1: expected 10.25699027111255, yours returns 10.256991666679482\n",
      "OK for dim 2: expected 0.0625, yours returns 0.062499984743169534\n"
     ]
    }
   ],
   "source": [
    "# now estimate the gradient numerically without any calculus, using\n",
    "# the approximation we used in the video.\n",
    "# you should not call the function df from the last cell\n",
    "\n",
    "# -----------\n",
    "h = 0.000001\n",
    "a = 2\n",
    "b = 3\n",
    "c = 4\n",
    "\n",
    "ndfda = ((f(a + h, b, c) - f(a, b, c)) / h)\n",
    "ndfdb = ((f(a, b + h, c) - f(a, b, c)) / h)\n",
    "ndfdc = ((f(a, b, c + h) - f(a, b, c)) / h)\n",
    "\n",
    "numerical_grad = [ndfda, ndfdb, ndfdc] # TODO\n",
    "# -----------\n",
    "\n",
    "for dim in range(3):\n",
    "  ok = 'OK' if abs(numerical_grad[dim] - ans[dim]) < 1e-5 else 'WRONG!'\n",
    "  print(f\"{ok} for dim {dim}: expected {ans[dim]}, yours returns {numerical_grad[dim]}\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "id": "BUqsGb5o_h2P"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "OK for dim 0: expected -12.353553390593273, yours returns -12.353553391353245\n",
      "OK for dim 1: expected 10.25699027111255, yours returns 10.25699027401572\n",
      "OK for dim 2: expected 0.0625, yours returns 0.06250000028629188\n"
     ]
    }
   ],
   "source": [
    "# there is an alternative formula that provides a much better numerical\n",
    "# approximation to the derivative of a function.\n",
    "# learn about it here: https://en.wikipedia.org/wiki/Symmetric_derivative\n",
    "# implement it. confirm that for the same step size h this version gives a\n",
    "# better approximation.\n",
    "\n",
    "# -----------\n",
    "h = 0.000001\n",
    "a = 2\n",
    "b = 3\n",
    "c = 4\n",
    "\n",
    "n2dfda = ((f(a + h, b, c) - f(a - h, b, c)) / (2*h))\n",
    "n2dfdb = ((f(a, b + h, c) - f(a, b - h, c)) / (2*h))\n",
    "n2dfdc = ((f(a, b, c + h) - f(a, b, c - h)) / (2*h))\n",
    "\n",
    "numerical_grad2 = [n2dfda, n2dfdb, n2dfdc]\n",
    "# -----------\n",
    "\n",
    "for dim in range(3):\n",
    "  ok = 'OK' if abs(numerical_grad2[dim] - ans[dim]) < 1e-5 else 'WRONG!'\n",
    "  print(f\"{ok} for dim {dim}: expected {ans[dim]}, yours returns {numerical_grad2[dim]}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "tklF9s_4AtlI"
   },
   "source": [
    "## section 2: support for softmax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "id": "nAPe_RVrCTeO"
   },
   "outputs": [],
   "source": [
    "from math import exp, log\n",
    "\n",
    "\n",
    "class Value:\n",
    "\n",
    "    def __init__(self, data, _children=(), _op=\"\", label=\"\"):\n",
    "        self.data = data\n",
    "        self.grad = 0.0\n",
    "        self._backward = lambda: None\n",
    "        self._prev = set(_children)\n",
    "        self._op = _op\n",
    "        self.label = label\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"Value(data={self.data})\"\n",
    "\n",
    "    def __add__(self, other):  # exactly as in the video\n",
    "        other = other if isinstance(other, Value) else Value(other)\n",
    "        out = Value(self.data + other.data, (self, other), \"+\")\n",
    "\n",
    "        def _backward():\n",
    "            self.grad += 1.0 * out.grad\n",
    "            other.grad += 1.0 * out.grad\n",
    "\n",
    "        out._backward = _backward\n",
    "\n",
    "        return out\n",
    "\n",
    "    def __mul__(self, other):  # self * other\n",
    "        other = other if isinstance(other, Value) else Value(other)\n",
    "        out = Value(self.data * other.data, (self, other), \"*\")\n",
    "\n",
    "        def _backward():\n",
    "            self.grad += other.data * out.grad\n",
    "            other.grad += self.data * out.grad\n",
    "\n",
    "        out._backward = _backward\n",
    "\n",
    "        return out\n",
    "\n",
    "    def __pow__(self, other):  # self ** other\n",
    "        assert isinstance(other, (float, int))\n",
    "        out = Value(self.data**other, (self,), f\"**{other}\")\n",
    "\n",
    "        def _backward():\n",
    "            self.grad += other * (self.data ** (other - 1.0)) * out.grad\n",
    "\n",
    "        out._backward = _backward\n",
    "\n",
    "        return out\n",
    "\n",
    "    def __radd__(self, other):  # other + self\n",
    "        return self + other\n",
    "\n",
    "    def __sub__(self, other):  # self - other\n",
    "        return self + (-other)\n",
    "\n",
    "    def __neg__(self):  # -self\n",
    "        return -1 * self\n",
    "\n",
    "    def __rmul__(self, other):  # other * self\n",
    "        return self * other\n",
    "\n",
    "    def __truediv__(self, other):  # self / other\n",
    "        return self * (other**-1)\n",
    "\n",
    "    def exp(self):\n",
    "        x = self.data\n",
    "        out = Value(exp(x), (self,), \"exp\")\n",
    "\n",
    "        def _backward():\n",
    "            self.grad += out.data * out.grad\n",
    "        \n",
    "        out._backward = _backward\n",
    "\n",
    "        return out\n",
    "\n",
    "    def log(self):\n",
    "        # assert isinstance(other, (float, int))\n",
    "        x = self.data\n",
    "        out = Value(log(x), (self,), \"log\")\n",
    "\n",
    "        def _backward():\n",
    "            self.grad += (1 / x) * out.grad\n",
    "        \n",
    "        out._backward = _backward\n",
    "\n",
    "        return out\n",
    "\n",
    "    # ------\n",
    "    # re-implement all the other functions needed for the exercises below\n",
    "    # your code here\n",
    "    # TODO\n",
    "    # ------\n",
    "\n",
    "    def backward(self):  # exactly as in video\n",
    "        topo = []\n",
    "        visited = set()\n",
    "\n",
    "        def build_topo(v):\n",
    "            if v not in visited:\n",
    "                visited.add(v)\n",
    "                for child in v._prev:\n",
    "                    build_topo(child)\n",
    "                topo.append(v)\n",
    "\n",
    "        build_topo(self)\n",
    "\n",
    "        self.grad = 1.0\n",
    "        for node in reversed(topo):\n",
    "            node._backward()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "id": "VgWvwVQNAvnI"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.1755153626167147\n",
      "OK for dim 0: expected 0.041772570515350445, yours returns 0.041772570515350445\n",
      "OK for dim 1: expected 0.8390245074625319, yours returns 0.8390245074625319\n",
      "OK for dim 2: expected 0.005653302662216329, yours returns 0.005653302662216329\n",
      "OK for dim 3: expected -0.8864503806400986, yours returns -0.8864503806400986\n"
     ]
    }
   ],
   "source": [
    "# without referencing our code/video __too__ much, make this cell work\n",
    "# you'll have to implement (in some cases re-implemented) a number of functions\n",
    "# of the Value object, similar to what we've seen in the video.\n",
    "# instead of the squared error loss this implements the negative log likelihood\n",
    "# loss, which is very often used in classification.\n",
    "\n",
    "# this is the softmax function\n",
    "# https://en.wikipedia.org/wiki/Softmax_function\n",
    "def softmax(logits):\n",
    "  counts = [logit.exp() for logit in logits]\n",
    "  denominator = sum(counts)\n",
    "  out = [c / denominator for c in counts]\n",
    "  return out\n",
    "\n",
    "# this is the negative log likelihood loss function, pervasive in classification\n",
    "logits = [Value(0.0), Value(3.0), Value(-2.0), Value(1.0)]\n",
    "probs = softmax(logits)\n",
    "loss = -probs[3].log() # dim 3 acts as the label for this input example\n",
    "loss.backward()\n",
    "print(loss.data)\n",
    "\n",
    "ans = [0.041772570515350445, 0.8390245074625319, 0.005653302662216329, -0.8864503806400986]\n",
    "for dim in range(4):\n",
    "  ok = 'OK' if abs(logits[dim].grad - ans[dim]) < 1e-5 else 'WRONG!'\n",
    "  print(f\"{ok} for dim {dim}: expected {ans[dim]}, yours returns {logits[dim].grad}\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "id": "q7ca1SVAGG1S"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tensor([2.1755], dtype=torch.float64)\n",
      "tensor([0.0418], dtype=torch.float64)\n",
      "tensor([0.8390], dtype=torch.float64)\n",
      "tensor([0.0057], dtype=torch.float64)\n",
      "tensor([-0.8865], dtype=torch.float64)\n"
     ]
    }
   ],
   "source": [
    "# verify the gradient using the torch library\n",
    "# torch should give you the exact same gradient\n",
    "import torch\n",
    "\n",
    "t1 = torch.Tensor([0.0]).double()            ; t1.requires_grad = True\n",
    "t2 = torch.Tensor([3.0]).double()            ; t2.requires_grad = True\n",
    "t3 = torch.Tensor([-2.0]).double()           ; t3.requires_grad = True\n",
    "t4 = torch.Tensor([1.0]).double()            ; t4.requires_grad = True\n",
    "t_logits = [t1, t2, t3, t4]\n",
    "t_o = softmax(t_logits)\n",
    "t_loss = -t_o[3].log()\n",
    "t_loss.backward()\n",
    "print(t_loss.data)\n",
    "for dim in range(4):\n",
    "    print(t_logits[dim].grad)"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}