{ "cells": [ { "cell_type": "code", "execution_count": 2, "metadata": { "deletable": false, "editable": false, "tags": [] }, "outputs": [], "source": [ "# Initialization cell\n", "try: # for CS1302 JupyterLite pyodide kernel\n", " import piplite\n", "\n", " with open(\"requirements.txt\") as f:\n", " for package in f:\n", " package = package.strip()\n", " print(\"Installing\", package)\n", " await piplite.install(package)\n", "except ModuleNotFoundError:\n", " pass\n", "\n", "import random\n", "import jupytext\n", "import otter\n", "from ipywidgets import interact\n", "\n", "grader = otter.Notebook(\"main.ipynb\")\n", "%reload_ext divewidgets" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Information Theory" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "-" }, "tags": [ "remove-cell" ] }, "source": [ "**CS1302 Introduction to Computer Programming**\n", "___" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "As mentioned in previous lectures, the following two lists `coin_flips` and `dice_rolls` simulate the random coin flips and rollings of a dice:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "ExecuteTime": { "end_time": "2021-03-20T14:33:36.981555Z", "start_time": "2021-03-20T14:33:36.941676Z" }, "nbgrader": { "grade": false, "grade_id": "random", "locked": true, "schema_version": 3, "solution": false, "task": false }, "slideshow": { "slide_type": "-" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "coin flips: T T H H T H T H H T T T H T T H T T T T H T T T H H H T T T H T H T T H T H T T H H T H H T H T H T T H H H T T H T T T T T T T T H T H T H H H T T H H T T T T T T T H T H T T T T T T H T T T T H T H T T H T H H T H T H H T H T T T T H T T T H H T H H T H H H T T H H H H H T H H T H H T H H T T T H T T H T T H H T H H H H T T H H T H T H T H H H H T H H H T T T T H H T H H H H T H T T H H T H T H\n", "dice rolls: 4 1 3 6 2 4 5 4 5 5 1 1 4 3 3 4 1 4 2 5 6 1 6 2 1 4 6 4 3 1 2 1 6 1 6 5 5 1 2 1 5 6 2 3 3 6 2 1 4 4 6 1 1 3 4 1 3 2 6 5 6 6 3 1 2 3 1 1 1 2 6 3 5 3 3 5 1 6 6 5 6 4 6 6 4 6 4 3 5 2 2 4 5 3 1 2 2 3 3 3 3 6 1 3 5 1 1 3 2 2 5 3 3 4 5 2 3 1 4 6 2 1 3 2 5 6 1 3 4 3 3 4 1 1 5 4 4 3 3 1 4 1 6 4 4 1 3 3 6 6 2 2 6 5 4 6 1 1 1 2 6 2 1 4 1 1 4 5 5 3 4 4 5 6 6 2 4 1 3 2 3 5 2 4 2 3 1 1 6 1 5 4 6 2 1 4 4 3 2 6\n" ] } ], "source": [ "# Do NOT modify any variables defined here because some tests rely on them\n", "import random\n", "import math\n", "\n", "random.seed(0) # for reproducible results.\n", "num_trials = 200\n", "coin_flips = [\"H\" if random.random() <= 1 / 2 else \"T\" for i in range(num_trials)]\n", "dice_rolls = [random.randint(1, 6) for i in range(num_trials)]\n", "print(\"coin flips: \", *coin_flips)\n", "print(\"dice rolls: \", *dice_rolls)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**What is the difference of the two random processes? \n", "Can we say one process has more information content than the other?**" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "-" } }, "source": [ "In this Lab, we will use dictionaries to store their distributions and then compute their information content using information theory, which was introduced by *Claude E. Shannon*. It has [numerous applications](https://www.khanacademy.org/computing/computer-science/informationtheory): \n", "- *compression* (to keep files small)\n", "- *communications* (to send data to mobile phones), and \n", "- *machine learning* (to identify relevant features to learn from)." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Entropy" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Mathematically, we denote a distribution as $\\mathbf{p}=[p_i]_{i\\in \\mathcal{S}}$, where \n", "- $\\mathcal{S}$ is the set of distinct outcomes, and\n", "- $p_i$ denotes the probability (chance) of seeing outcome $i$." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "The following code shown in the lecture uses a dictionary to store the distribution for a sequence efficiently without storing outcomes with zero counts:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "ExecuteTime": { "end_time": "2020-11-30T02:36:09.358277Z", "start_time": "2020-11-30T02:36:09.352201Z" }, "nbgrader": { "grade": false, "grade_id": "dist", "locked": true, "schema_version": 3, "solution": false, "task": false }, "slideshow": { "slide_type": "-" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Distribution of coin flips: {'T': 0.5350000000000004, 'H': 0.4650000000000003}\n", "Distribution of dice rolls: {4: 0.17000000000000007, 1: 0.2150000000000001, 3: 0.18500000000000008, 6: 0.16500000000000006, 2: 0.14500000000000005, 5: 0.12000000000000004}\n" ] } ], "source": [ "# Do NOT modify any variables defined here because some tests rely on them\n", "def distribute(seq):\n", " \"\"\"Returns a dictionary where each value in a key-value pair is\n", " the probability of the associated key occurring in the sequence.\n", " \"\"\"\n", " p = {}\n", " for i in seq:\n", " p[i] = p.get(i, 0) + 1 / len(seq)\n", " return p\n", "\n", "\n", "# tests\n", "coin_flips_dist = distribute(coin_flips)\n", "dice_rolls_dist = distribute(dice_rolls)\n", "print(\"Distribution of coin flips:\", coin_flips_dist)\n", "print(\"Distribution of dice rolls:\", dice_rolls_dist)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "For $\\mathbf{p}$ to be a valid distribution, the probabilities $p_i$'s have to sum to $1$, i.e.,\n", "\n", "$$\\sum_{i\\in \\mathcal{S}} p_i = 1, $$\n", "which can be verified as follows:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "ExecuteTime": { "end_time": "2020-11-30T02:36:10.548606Z", "start_time": "2020-11-30T02:36:10.543473Z" }, "slideshow": { "slide_type": "-" } }, "outputs": [], "source": [ "assert math.isclose(sum(coin_flips_dist.values()), 1) and math.isclose(\n", " sum(dice_rolls_dist.values()), 1\n", ")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**How to measure the information content?**" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "ExecuteTime": { "end_time": "2020-11-30T02:36:11.842356Z", "start_time": "2020-11-30T02:36:11.836253Z" }, "slideshow": { "slide_type": "-" }, "tags": [ "hide-input" ] }, "outputs": [ { "data": { "text/html": [ "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "%%html\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "---\n", "\n", "**Definition** (Entropy)\n", "\n", "In information theory, the information content of a distribution is measured by its [*entropy*](https://en.wikipedia.org/wiki/Entropy_(information_theory)) defined as:\n", "\n", "$$ \n", "\\begin{aligned} \n", "H(\\mathbf{p}) &:= \\sum_{i\\in \\mathcal{S}} p_i \\overbrace{\\log_2 \\tfrac{1}{p_i}}^{\\text{called surprise} } \\\\ \n", "&= - \\sum_{i\\in \\mathcal{S}} p_i \\log_2 p_i \\kern1em \\text{(bits)} \\end{aligned} \n", "$$\n", "\n", "with $p_i \\log_2 \\frac{1}{p_i} = 0$ if $p_i = 0$ because $\\lim_{x\\downarrow 0} x \\log_2 \\frac1x = 0$.\n", "\n", "---" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "For instance, if $\\mathbf{p}=(p_{H},p_{T})=(0.5,0.5)$, then\n", "\n", "$$\n", "\\begin{aligned} H(\\mathbf{p}) &= 0.5 \\log_2 \\frac{1}{0.5} + 0.5 \\log_2 \\frac{1}{0.5} \\\\ &= 0.5 + 0.5 = 1 \\text{ bit,}\\end{aligned} \n", "$$\n", "\n", "i.e., an outcome of a fair coin flip has one bit of information content, as expected." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "On the other hand, if $\\mathbf{p}=(p_{H},p_{T})=(1,0)$, then\n", "\n", "$$\n", "\\begin{aligned} H(\\mathbf{p}) &= 1 \\log_2 \\frac{1}{1} + 0 \\log_2 \\frac{1}{0} \\\\ &= 0 + 0 = 0 \\text{ bits,}\\end{aligned} \n", "$$\n", "\n", "i.e., an outcome of a biased coin flip that always comes up head has no information content, again as expected." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**Exercise** (entropy)\n", "\n", "Define a function `entropy` that\n", "- takes a distribution $\\mathbf{p}$ as its argument, and\n", "- returns the entropy $H(\\mathbf{p})$.\n", "\n", "Handle the case when $p_i=0$, e.g., using the short-circuit evaluation of logical `and`." ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "ExecuteTime": { "end_time": "2020-11-30T02:36:14.574396Z", "start_time": "2020-11-30T02:36:14.568953Z" }, "nbgrader": { "grade": false, "grade_id": "entropy", "locked": false, "schema_version": 3, "solution": true, "task": false }, "slideshow": { "slide_type": "-" }, "tags": [ "remove-output" ] }, "outputs": [], "source": [ "from math import log2\n", "def entropy(dist):\n", " Hp=0\n", " for n in dist:\n", " if dist[n] != 0:\n", " Hp+=dist[n]*log2(1/dist[n])\n", " else:\n", " return 0\n", " return Hp" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "deletable": false, "editable": false }, "outputs": [ { "data": { "text/html": [ "

entropy
passed!

" ], "text/plain": [ "entropy results: All test cases passed!" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "grader.check(\"entropy\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Uniform distribution maximizes entropy" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Intuitively,\n", "- for large enough numbers of fair coin flips, we should have $\\mathcal{S}=\\{H,T\\}$ and $p_H=p_T=0.5$, i.e., equal chance for head and tail.\n", "- for large enough numbers of fair dice rolls, we should have $p_i=\\frac16$ for all $i\\in \\mathcal{S}=\\{1,2,3,4,5,6\\}$." ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "ExecuteTime": { "end_time": "2020-11-30T02:36:16.996779Z", "start_time": "2020-11-30T02:36:16.875089Z" }, "slideshow": { "slide_type": "-" } }, "outputs": [ { "data": { "application/vnd.jupyter.widget-view+json": { "model_id": "5227f5d4a7cc462782f6344fa5d76a8e", "version_major": 2, "version_minor": 0 }, "text/plain": [ "interactive(children=(IntSlider(value=1, continuous_update=False, description='n:', max=200, min=1), Output())…" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "import matplotlib.pyplot as plt\n", "\n", "\n", "def plot_distribution(seq):\n", " dist = distribute(seq)\n", " plt.stem(\n", " dist.keys(), # set-like view of the keys\n", " dist.values(), # view of the values\n", " )\n", " plt.xlabel(\"Outcomes\")\n", " plt.title(\"Distribution\")\n", " plt.ylim(0, 1)\n", "\n", "\n", "import ipywidgets as widgets\n", "\n", "n_widget = widgets.IntSlider(\n", " value=1,\n", " min=1,\n", " max=num_trials,\n", " step=1,\n", " description=\"n:\",\n", " continuous_update=False,\n", ")\n", "\n", "widgets.interactive(lambda n: plot_distribution(coin_flips[:n]), n=n_widget)" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "ExecuteTime": { "end_time": "2020-11-30T02:36:17.688814Z", "start_time": "2020-11-30T02:36:17.537818Z" }, "slideshow": { "slide_type": "-" } }, "outputs": [ { "data": { "application/vnd.jupyter.widget-view+json": { "model_id": "a91e3583b35c4a4fa4cb14574e93534c", "version_major": 2, "version_minor": 0 }, "text/plain": [ "interactive(children=(IntSlider(value=1, continuous_update=False, description='n:', max=200, min=1), Output())…" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "widgets.interactive(lambda n: plot_distribution(dice_rolls[:n]), n=n_widget)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "---\n", "\n", "**Definition** (Uniform)\n", "\n", "A distribution is called a *uniform distribution* if all its distinct outcomes have the same probability of occurring, i.e.,\n", "\n", "$$ p_i = \\frac{1}{|\\mathcal{S}|}\\kern1em \\text{for all }i\\in \\mathcal{S}, $$\n", "\n", "where $|\\mathcal{S}|$ is the mathematical notation to denote the size of the set $\\mathcal{S}$.\n", "\n", "---" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**Exercise** (uniform)\n", "\n", "Define a function `uniform` that\n", "- takes a sequence of possibly duplicate outcomes, and\n", "- returns a uniform distribution of the distinct outcomes." ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "ExecuteTime": { "end_time": "2020-11-30T02:36:19.734972Z", "start_time": "2020-11-30T02:36:19.729594Z" }, "nbgrader": { "grade": false, "grade_id": "uniform", "locked": false, "schema_version": 3, "solution": true, "task": false }, "slideshow": { "slide_type": "-" }, "tags": [ "remove-output" ] }, "outputs": [], "source": [ "def uniform(outcomes):\n", " \"\"\"Returns the uniform distribution (dict) over distinct items in outcomes.\"\"\"\n", " outcomes=set(outcomes)\n", " output={}\n", " for n in outcomes:\n", " output={**output,n: 1/len(outcomes)}\n", " return output" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "deletable": false, "editable": false }, "outputs": [ { "data": { "text/html": [ "

uniform
passed!

" ], "text/plain": [ "uniform results: All test cases passed!" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "grader.check(\"uniform\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**What is the entropy for uniform distributions?**" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "By definition,\n", "\n", "$$ \\begin{aligned} H(\\mathbf{p}) &:= \\sum_{i\\in \\mathcal{S}} p_i \\log_2 \\tfrac{1}{p_i} \\\\ &= \\sum_{i\\in \\mathcal{S}} \\frac{1}{|\\mathcal{S}|} \\log_2 |\\mathcal{S}| = \\log_2 |\\mathcal{S}| \\kern1em \\text{(bits)} \\end{aligned} $$\n", "\n", "Entropy reduces to the formula in Lecture 1 and Lab 1 regarding the number of bits required to encode a set of integers or characters. It is the maximum possible entropy for a given finite set of possible outcomes." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Use this result to test whether you have implemented both `entropy` and `uniform` correctly:" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "ExecuteTime": { "end_time": "2020-11-30T02:36:25.212111Z", "start_time": "2020-11-30T02:36:25.207318Z" }, "slideshow": { "slide_type": "-" }, "tags": [ "remove-output" ] }, "outputs": [], "source": [ "assert all(\n", " math.isclose(entropy(uniform(range(n))), math.log2(n)) for n in range(1, 100)\n", ")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Joint distribution and its entropy" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "If we duplicate a sequence of outcomes, the total information content should remain unchanged, NOT doubled, because the duplicate contains the same information as the original. We will verify this fact by creating a [joint distribution](https://en.wikipedia.org/wiki/Joint_probability_distribution) \n", "\n", "$$\\mathbf{p}=[p_{ij}]_{i\\in \\mathcal{S},j\\in \\mathcal{T}}$$ \n", "- where $\\mathcal{S}$ and $\\mathcal{T}$ are sets of outcomes; and\n", "- $p_{ij}$ is the chance we see outcomes $i$ and $j$ simultaneously. \n", "\n", "The subscript $ij$ in $p_{ij}$ denotes a tuple $(i,j)$, NOT the multiplication $i\\times j$. We also have\n", "\n", "$$\\sum_{i\\in \\mathcal{S}} \\sum_{j\\in \\mathcal{T}} p_{ij} = 1.$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**Exercise** (jointly-distribute)\n", "\n", "Define a function `jointly_distribute` that \n", "- takes two sequences, `seq1` and `seq2`, of outcomes with the same length, and\n", "- returns the joint distribution represented as a dictionary where each key-value pair has the key being a tuple `(i,j)` associated with the probability $p_{ij}$ of seeing `(i,j)` in `zip(seq1,seq2)`." ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "ExecuteTime": { "end_time": "2020-11-30T02:36:35.375122Z", "start_time": "2020-11-30T02:36:35.368117Z" }, "nbgrader": { "grade": false, "grade_id": "jointly_distribute", "locked": false, "schema_version": 3, "solution": true, "task": false }, "slideshow": { "slide_type": "-" }, "tags": [ "remove-output" ] }, "outputs": [], "source": [ "def jointly_distribute(seq1, seq2):\n", " \"\"\"Returns the joint distribution of the tuple (i,j) of outcomes from zip(seq1,seq2).\"\"\"\n", " com=list(zip(seq1, seq2))\n", " output={}\n", " for i in com:\n", " output[i]=output.get(i,0)+1/len(seq1)\n", " return output" ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "deletable": false, "editable": false }, "outputs": [ { "data": { "text/html": [ "

jointly-distribute
passed!

" ], "text/plain": [ "jointly-distribute results: All test cases passed!" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "grader.check(\"jointly-distribute\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "If you have implemented `entropy` and `jointly_distribute` correctly, you can verify that duplicating a sequence will give the same entropy." ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "ExecuteTime": { "end_time": "2020-11-30T02:36:42.862879Z", "start_time": "2020-11-30T02:36:42.859494Z" }, "slideshow": { "slide_type": "-" }, "tags": [ "remove-output" ] }, "outputs": [], "source": [ "assert math.isclose(\n", " entropy(jointly_distribute(coin_flips, coin_flips)), entropy(distribute(coin_flips))\n", ")\n", "assert math.isclose(\n", " entropy(jointly_distribute(dice_rolls, dice_rolls)), entropy(distribute(dice_rolls))\n", ")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "However, for two sequences generated independently, the joint entropy is roughly the sum of the individual entropies." ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "ExecuteTime": { "end_time": "2020-11-30T02:36:45.483459Z", "start_time": "2020-11-30T02:36:45.476684Z" }, "slideshow": { "slide_type": "-" }, "tags": [ "remove-output" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Entropy of coin flip: 0.9964625048848761\n", "Entropy of dice roll: 2.561663937785679\n", "Sum of the above entropies: 3.558126442670555\n", "Joint entropy: 3.528135217157916\n" ] } ], "source": [ "coin_flips_entropy = entropy(distribute(coin_flips))\n", "dice_rolls_entropy = entropy(distribute(dice_rolls))\n", "cf_dr_entropy = entropy(jointly_distribute(coin_flips, dice_rolls))\n", "print(\n", " f\"\"\"Entropy of coin flip: {coin_flips_entropy}\n", "Entropy of dice roll: {dice_rolls_entropy}\n", "Sum of the above entropies: {coin_flips_entropy + dice_rolls_entropy}\n", "Joint entropy: {cf_dr_entropy}\"\"\"\n", ")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "## Conditional distribution and entropy" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Mathematically, we denote a [conditional distribution](https://en.wikipedia.org/wiki/Conditional_probability_distribution) as $\\mathbf{q}:=[q_{j|i}]_{i\\in \\mathcal{S}, j\\in \\mathcal{T}}$, where \n", "- $\\mathcal{S}$ and $\\mathcal{T}$ are two sets of distinct outcomes, and\n", "- $q_{j|i}$ denotes the probability (chance) of seeing outcome $j$ given the condition that outcome $i$ is observed.\n", "\n", "For $\\mathbf{q}$ to be a valid distribution, the probabilities $q_{j|i}$'s have to sum to $1$ for every $i$, i.e.,\n", "\n", "$$\\sum_{j\\in \\mathcal{T}} q_{j|i} = 1 \\kern1em \\text{for all }i\\in \\mathcal{S} $$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "For example, suppose we want to compute the distribution of coin flips given dice rolls, then the following assign `q_H_1` and `q_T_1` to the values $q_{H|1}$ and $q_{T|1}$ respectively:" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "ExecuteTime": { "end_time": "2020-11-30T02:36:52.270634Z", "start_time": "2020-11-30T02:36:52.260818Z" }, "slideshow": { "slide_type": "-" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Coin flips given dice roll is 1: ['T', 'T', 'T', 'T', 'T', 'H', 'T', 'T', 'T', 'H', 'T', 'T', 'H', 'H', 'T', 'T', 'T', 'H', 'T', 'T', 'T', 'H', 'H', 'T', 'H', 'H', 'T', 'H', 'H', 'H', 'H', 'H', 'H', 'T', 'H', 'T', 'H', 'H', 'H', 'H', 'H', 'H', 'H']\n", "Distribution of coin flip given dice roll is 1: { \"H\": 0.5348837209302325, \"T\": 0.46511627906976744}\n" ] } ], "source": [ "coin_flips_1 = [j for i, j in zip(dice_rolls, coin_flips) if i == 1]\n", "q_H_1 = coin_flips_1.count(\"H\") / len(coin_flips_1)\n", "q_T_1 = coin_flips_1.count(\"T\") / len(coin_flips_1)\n", "print(\"Coin flips given dice roll is 1:\", coin_flips_1)\n", "print(\n", " 'Distribution of coin flip given dice roll is 1: {{ \"H\": {}, \"T\": {}}}'.format(\n", " q_H_1, q_T_1\n", " )\n", ")\n", "assert math.isclose(q_H_1 + q_T_1, 1)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Note that `q_H_1 + q_T_1` is 1 as expected. Similarly, we can assign `q_H_2` and `q_T_2` to the values $q_{H|2}$ and $q_{T|2}$ respectively." ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "ExecuteTime": { "end_time": "2020-11-30T02:36:54.400638Z", "start_time": "2020-11-30T02:36:54.391792Z" }, "slideshow": { "slide_type": "-" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Coin flips given dice roll is 2: ['T', 'T', 'T', 'H', 'T', 'T', 'H', 'T', 'T', 'H', 'T', 'T', 'T', 'T', 'T', 'H', 'T', 'T', 'T', 'T', 'T', 'H', 'H', 'T', 'T', 'T', 'H', 'T', 'T']\n", "Distribution of coin flip given dice roll is 2: { \"H\": 0.2413793103448276, \"T\": 0.7586206896551724}\n" ] } ], "source": [ "coin_flips_2 = [j for i, j in zip(dice_rolls, coin_flips) if i == 2]\n", "q_H_2 = coin_flips_2.count(\"H\") / len(coin_flips_2)\n", "q_T_2 = coin_flips_2.count(\"T\") / len(coin_flips_2)\n", "print(\"Coin flips given dice roll is 2:\", coin_flips_2)\n", "print(\n", " 'Distribution of coin flip given dice roll is 2: {{ \"H\": {}, \"T\": {}}}'.format(\n", " q_H_2, q_T_2\n", " )\n", ")\n", "assert math.isclose(q_H_2 + q_T_2, 1)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Finally, we want to store the conditional distribution as a nested dictionary so that `q[i]` points to the distribution \n", "\n", "$$[q_{j|i}]_{j\\in \\mathcal{T}} \\kern1em \\text{for }i\\in \\mathcal{S}.$$" ] }, { "cell_type": "code", "execution_count": 32, "metadata": { "ExecuteTime": { "end_time": "2020-11-30T02:36:55.594506Z", "start_time": "2020-11-30T02:36:55.585985Z" }, "slideshow": { "slide_type": "-" } }, "outputs": [ { "data": { "text/plain": [ "{1: {'H': 0.5348837209302325, 'T': 0.46511627906976744},\n", " 2: {'H': 0.2413793103448276, 'T': 0.7586206896551724}}" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "q = {}\n", "q[1] = dict(zip(\"HT\", (q_H_1, q_T_1)))\n", "q[2] = dict(zip(\"HT\", (q_H_2, q_T_2)))\n", "q" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Of course, the above dictionary is missing the entries for other possible outcomes of the dice rolls." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**Exercise** (conditionally-distribute)\n", "\n", "Define a function `conditionally_distribute` that\n", "- takes two sequences `seq1` and `seq2` of outcomes of the same length, and\n", "- returns the conditional distribution of `seq2` given `seq1` in the form of a nested dictionary efficiently without storing the unobserved outcomes.\n", "\n", "In the above example, `seq1` is `dice_rolls` while `seq2` is `coin_flips`.\n", "\n", "````{hint}\n", "For an efficient implementation without traversing the input sequences too many times, consider using the following solution template and the `setdefault` method.\n", "```Python\n", "def conditionally_distribute(seq1, seq2):\n", " q, count = {}, {} # NOT q = count = {}\n", " for i in seq1:\n", " count[i] = count.get(i, 0) + 1\n", " for i, j in zip(seq1, seq2):\n", " q[i][j] = ____________________________________________________\n", " return q\n", "```\n", "````" ] }, { "cell_type": "code", "execution_count": 44, "metadata": { "ExecuteTime": { "end_time": "2020-11-30T02:37:10.353076Z", "start_time": "2020-11-30T02:37:10.344359Z" }, "nbgrader": { "grade": false, "grade_id": "conditionally_distribute", "locked": false, "schema_version": 3, "solution": true, "task": false }, "slideshow": { "slide_type": "-" }, "tags": [ "remove-output" ] }, "outputs": [], "source": [ "def conditionally_distribute(seq1, seq2):\n", " \"\"\"Returns the conditional distribution q of seq2 given seq1 such that\n", " q[i] is a dictionary for observed outcome i in seq1 and\n", " q[i][j] is the probability of observing j in seq2 given the\n", " corresponding outcome in seq1 is i.\"\"\"\n", " q, count = {}, {} \n", " for i in seq1:\n", " count[i] = count.get(i, 0) + 1\n", " q[i]={}\n", " for i, j in zip(seq1, seq2):\n", " coin_flips = [y for x, y in zip(seq1, seq2) if x == i]\n", " q[i][j] = coin_flips.count(j)/count[i]\n", " return q" ] }, { "cell_type": "code", "execution_count": 45, "metadata": { "deletable": false, "editable": false }, "outputs": [ { "data": { "text/html": [ "

(conditionally-distribute)
passed!

" ], "text/plain": [ "(conditionally-distribute) results: All test cases passed!" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "grader.check(\"(conditionally-distribute)\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "---\n", "\n", "**Definition** (Conditional entropy)\n", "\n", "The [*conditional entropy*](https://en.wikipedia.org/wiki/Conditional_entropy) is defined for a conditional distribution $\\mathbf{q}=[q_{j|i}]_{i\\in \\mathcal{S},j\\in\\mathcal{T}}$ and a distribution $\\mathbf{p}=[p_i]_{i\\in \\mathcal{S}}$ as follows:\n", "\n", "$$ H(\\mathbf{q}|\\mathbf{p}) = \\sum_{i\\in \\mathcal{S}} p_i \\sum_{j\\in \\mathcal{T}} q_{j|i} \\log_2 \\frac{1}{q_{j|i}}, $$\n", "where, by convention, \n", "- the summand of the outer sum is 0 if $p_i=0$ (regardless of the values of $q_{j|i}$), and\n", "- the summand of the inner sum is 0 if $q_{j|i}=0$.\n", "\n", "---" ] }, { "cell_type": "markdown", "metadata": { "ExecuteTime": { "end_time": "2020-11-10T07:01:43.746409Z", "start_time": "2020-11-10T07:01:43.739829Z" }, "slideshow": { "slide_type": "subslide" } }, "source": [ "**Exercise** (conditional-entropy)\n", "\n", "Define a function `conditional_entropy` that\n", "- takes \n", " - a distribution p as its first argument,\n", " - a conditional distribution q as its second argument, and\n", "- returns the conditional entropy $H(\\mathbf{q}|\\mathbf{p})$.\n", "\n", "Handle the cases when $p_i=0$ and $q_{j|i}=0$." ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "ExecuteTime": { "end_time": "2020-11-30T03:05:53.714506Z", "start_time": "2020-11-30T03:05:53.708443Z" }, "nbgrader": { "grade": false, "grade_id": "conditional_entropy", "locked": false, "schema_version": 3, "solution": true, "task": false }, "slideshow": { "slide_type": "-" }, "tags": [ "remove-output" ] }, "outputs": [], "source": [ "def conditional_entropy(p, q):\n", " \"\"\"Returns the conditional entropy of the conditional distribution q given\n", " the distribution p.\"\"\"\n", " result = 0\n", " for i in q:\n", " result += p[i] * entropy(q[i])\n", " return result" ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "ExecuteTime": { "end_time": "2020-11-30T03:05:54.134252Z", "start_time": "2020-11-30T03:05:54.122726Z" }, "nbgrader": { "grade": true, "grade_id": "test-conditional_entropy", "locked": true, "points": 1, "schema_version": 3, "solution": false, "task": false }, "slideshow": { "slide_type": "-" }, "tags": [ "remove-output", "hide-input" ] }, "outputs": [], "source": [ "# tests\n", "cf_given_dr_dist = {\n", " 4: {\"T\": 0.5588235294117647, \"H\": 0.4411764705882353},\n", " 1: {\"T\": 0.46511627906976744, \"H\": 0.5348837209302325},\n", " 3: {\"H\": 0.5135135135135135, \"T\": 0.4864864864864865},\n", " 6: {\"H\": 0.5454545454545454, \"T\": 0.45454545454545453},\n", " 2: {\"T\": 0.7586206896551724, \"H\": 0.2413793103448276},\n", " 5: {\"T\": 0.5416666666666666, \"H\": 0.4583333333333333}}\n", "assert (\n", " conditional_entropy(\n", " {\"H\": 0.5, \"T\": 0.5}, {\"H\": {\"H\": 0.5, \"T\": 0.5}, \"T\": {\"H\": 0.5, \"T\": 0.5}})\n", " == 1)\n", "assert (\n", " conditional_entropy(\n", " {\"H\": 0, \"T\": 1}, {\"H\": {\"H\": 0.5, \"T\": 0.5}, \"T\": {\"H\": 0.5, \"T\": 0.5}})\n", " == 1)\n", "assert (\n", " conditional_entropy(\n", " {\"H\": 0.5, \"T\": 0.5}, {\"H\": {\"H\": 1, \"T\": 0}, \"T\": {\"H\": 0, \"T\": 1}})\n", " == 0)\n", "assert (\n", " conditional_entropy(\n", " {\"H\": 0.5, \"T\": 0.5}, {\"H\": {\"H\": 1, \"T\": 0}, \"T\": {\"H\": 0.5, \"T\": 0.5}})\n", " == 0.5)\n", "assert math.isclose(\n", " conditional_entropy(dice_rolls_dist, cf_given_dr_dist), 0.9664712793722372)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "The joint probability $p_{ij}$ over $i\\in \\mathcal{S}$ and $j\\in \\mathcal{T}$ can be calculated as follows\n", "\n", "$$p_{ij} = p_{i} q_{j|i}$$\n", "where $p_i$ is the probability of $i$ and $q_{j|i}$ is the conditional probability of $j$ given $i$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercise** (joint-distribution)\n", "\n", "Define a function `joint_distribution` that\n", "- takes the distribution $p$ and conditional distribution $q$ as arguments, and\n", "- returns their joint distribution." ] }, { "cell_type": "code", "execution_count": 57, "metadata": { "ExecuteTime": { "end_time": "2020-11-16T11:28:14.895895Z", "start_time": "2020-11-16T11:28:14.892010Z" }, "nbgrader": { "grade": false, "grade_id": "joint_distribution", "locked": false, "schema_version": 3, "solution": true, "task": false }, "tags": [] }, "outputs": [], "source": [ "def joint_distribution(p, q):\n", " output={}\n", " for i in p:\n", " for j in q:\n", " output[i,j]=p[i]*q[i][j]\n", " return output" ] }, { "cell_type": "code", "execution_count": 58, "metadata": { "deletable": false, "editable": false }, "outputs": [ { "data": { "text/html": [ "

joint-distribution
passed!

" ], "text/plain": [ "joint-distribution results: All test cases passed!" ] }, "execution_count": 58, "metadata": {}, "output_type": "execute_result" } ], "source": [ "grader.check(\"joint-distribution\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Finally, a fundamental information identity relating the joint and conditional entropies is the [*chain rule*](https://en.wikipedia.org/wiki/Conditional_entropy#Chain_rule):" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "\n", "**Proposition**\n", "\n", "The joint entropy is equal to\n", "\n", "$$ H(\\mathbf{p}) + H(\\mathbf{q}|\\mathbf{p})$$\n", "\n", "for any distribution $\\mathbf{p}$ over outcome $i\\in \\mathcal{S}$ and conditional distribution $\\mathbf{q}$ over outcome $j\\in \\mathcal{T}$ given outcome $i \\in \\mathcal{S}$. \n", "\n", "---" ] }, { "cell_type": "markdown", "metadata": { "ExecuteTime": { "end_time": "2020-11-10T12:28:29.339662Z", "start_time": "2020-11-10T12:28:29.331637Z" }, "slideshow": { "slide_type": "fragment" } }, "source": [ "If you have implemented `jointly_distribute`, `conditionally_distribute`, `entropy`, and `conditional_entropy` correctly, we can verify the identity as follows." ] }, { "cell_type": "code", "execution_count": 49, "metadata": { "ExecuteTime": { "end_time": "2020-11-16T11:28:43.031007Z", "start_time": "2020-11-16T11:28:43.023358Z" }, "slideshow": { "slide_type": "-" } }, "outputs": [], "source": [ "def validate_chain_rule(seq1, seq2):\n", " p = distribute(seq1)\n", " q = conditionally_distribute(seq1, seq2)\n", " pq = jointly_distribute(seq1, seq2)\n", " H_pq = entropy(pq)\n", " H_p = entropy(p)\n", " H_q_p = conditional_entropy(p, q)\n", " print(\n", " f\"\"\"Entropy of seq1: {H_p}\n", "Conditional entropy of seq2 given seq1: {H_q_p}\n", "Sum of the above entropies: {H_p + H_q_p}\n", "Joint entropy: {H_pq}\"\"\"\n", " )\n", " assert math.isclose(H_pq, H_p + H_q_p)" ] }, { "cell_type": "code", "execution_count": 50, "metadata": { "ExecuteTime": { "end_time": "2020-11-10T14:47:05.282008Z", "start_time": "2020-11-10T14:47:05.275719Z" }, "slideshow": { "slide_type": "-" }, "tags": [ "remove-output" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Entropy of seq1: 0.9964625048848761\n", "Conditional entropy of seq2 given seq1: 0.0\n", "Sum of the above entropies: 0.9964625048848761\n", "Joint entropy: 0.9964625048848761\n" ] } ], "source": [ "validate_chain_rule(coin_flips, coin_flips)" ] }, { "cell_type": "code", "execution_count": 51, "metadata": { "ExecuteTime": { "end_time": "2020-11-10T14:47:08.553680Z", "start_time": "2020-11-10T14:47:08.546789Z" }, "slideshow": { "slide_type": "-" }, "tags": [ "remove-output" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Entropy of seq1: 2.561663937785679\n", "Conditional entropy of seq2 given seq1: 0.9664712793722373\n", "Sum of the above entropies: 3.5281352171579163\n", "Joint entropy: 3.528135217157916\n" ] } ], "source": [ "validate_chain_rule(dice_rolls, coin_flips)" ] }, { "cell_type": "markdown", "metadata": { "editable": false, "tags": [ "remove-cell" ] }, "source": [ "## Submission\n", "\n", "Make sure you have run all cells in your notebook in order before running the cell below, so that all images/graphs appear in the output. The cell below will generate a zip file for you to submit. **Please save before exporting!**" ] }, { "cell_type": "code", "execution_count": 52, "metadata": { "deletable": false, "editable": true, "tags": [] }, "outputs": [], "source": [ "# extra files to submit\n", "extra_files = []" ] }, { "cell_type": "code", "execution_count": 53, "metadata": { "deletable": false, "editable": false, "tags": [] }, "outputs": [], "source": [ "# Generate the source main.py necessary for grading and similarity check.\n", "jupytext.write(jupytext.read(\"main.ipynb\"), \"main.py\", fmt=\"py:percent\")" ] }, { "cell_type": "code", "execution_count": 54, "metadata": { "deletable": false, "editable": false, "tags": [] }, "outputs": [ { "data": { "text/html": [ "\n", "

Your submission has been exported. Click here\n", " to download the zip file.

\n", " " ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Generate the zip file to submit.\n", "grader.export(pdf=False, run_tests=False, files=[\"main.py\", *extra_files])" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "celltoolbar": "Create Assignment", "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.10.6" }, "latex_envs": { "LaTeX_envs_menu_present": true, "autoclose": false, "autocomplete": true, "bibliofile": "biblio.bib", "cite_by": "apalike", "current_citInitial": 1, "eqLabelWithNumbers": true, "eqNumInitial": 1, "hotkeys": { "equation": "Ctrl-E", "itemize": "Ctrl-I" }, "labels_anchors": false, "latex_user_defs": false, "report_style_numbering": false, "user_envs_cfg": false }, "otter": { "OK_FORMAT": true, "tests": { "(conditionally-distribute)": { "name": "(conditionally-distribute)", "points": null, "suites": [ { "cases": [ { "code": ">>> # tests\n>>> cf_given_dr_dist = {\n... 4: {\"T\": 0.5588235294117647, \"H\": 0.4411764705882353},\n... 1: {\"T\": 0.46511627906976744, \"H\": 0.5348837209302325},\n... 3: {\"H\": 0.5135135135135135, \"T\": 0.4864864864864865},\n... 6: {\"H\": 0.5454545454545454, \"T\": 0.45454545454545453},\n... 2: {\"T\": 0.7586206896551724, \"H\": 0.2413793103448276},\n... 5: {\"T\": 0.5416666666666666, \"H\": 0.4583333333333333}}\n>>> cf_given_dr_ans = conditionally_distribute(dice_rolls, coin_flips)\n>>> assert all(\n... math.isclose(cf_given_dr_ans[i][j], v)\n... for i, d in cf_given_dr_dist.items()\n... for j, v in d.items())\n", "hidden": false, "locked": false } ], "scored": true, "setup": "", "teardown": "", "type": "doctest" } ] }, "conditional-entropy": { "name": "conditional-entropy", "points": null, "suites": [ { "cases": [], "scored": true, "setup": "", "teardown": "", "type": "doctest" } ] }, "entropy": { "name": "entropy", "points": null, "suites": [ { "cases": [ { "code": ">>> # tests\n>>> assert math.isclose(entropy({\"H\": 0.5, \"T\": 0.5}), 1)\n>>> assert math.isclose(entropy({\"H\": 1, \"T\": 0}), 0)\n>>> assert math.isclose(entropy(dict.fromkeys(range(1, 7), 1 / 6)), math.log2(6))\n", "hidden": false, "locked": false } ], "scored": true, "setup": "", "teardown": "", "type": "doctest" } ] }, "joint-distribution": { "name": "joint-distribution", "points": null, "suites": [ { "cases": [ { "code": ">>> # tests\n>>> assert joint_distribution(\n... {\"H\": 0.5, \"T\": 0.5}, {\"H\": {\"H\": 0.5, \"T\": 0.5}, \"T\": {\"H\": 0.5, \"T\": 0.5}}) == {(\"H\", \"H\"): 0.25, (\"H\", \"T\"): 0.25, (\"T\", \"H\"): 0.25, (\"T\", \"T\"): 0.25}\n>>> assert joint_distribution(\n... {\"H\": 0, \"T\": 1}, {\"H\": {\"H\": 0.5, \"T\": 0.5}, \"T\": {\"H\": 0.5, \"T\": 0.5}}) == {(\"H\", \"H\"): 0.0, (\"H\", \"T\"): 0.0, (\"T\", \"H\"): 0.5, (\"T\", \"T\"): 0.5}\n>>> assert joint_distribution(\n... {\"H\": 0.5, \"T\": 0.5}, {\"H\": {\"H\": 1, \"T\": 0}, \"T\": {\"H\": 0, \"T\": 1}}) == {(\"H\", \"H\"): 0.5, (\"H\", \"T\"): 0.0, (\"T\", \"H\"): 0.0, (\"T\", \"T\"): 0.5}, {\n... \"H\": 0.5,\n... \"T\": 0.5}\n", "hidden": false, "locked": false } ], "scored": true, "setup": "", "teardown": "", "type": "doctest" } ] }, "jointly-distribute": { "name": "jointly-distribute", "points": null, "suites": [ { "cases": [ { "code": ">>> # tests\n>>> assert jointly_distribute(\"HT\", \"HT\") == {(\"H\", \"H\"): 0.5, (\"T\", \"T\"): 0.5}\n>>> assert jointly_distribute(\"HHTT\", \"HTHT\") == {\n... (\"H\", \"H\"): 0.25,\n... (\"H\", \"T\"): 0.25,\n... (\"T\", \"H\"): 0.25,\n... (\"T\", \"T\"): 0.25}\n>>> coin_flips_duplicate_dist = {\n... (\"T\", \"T\"): 0.5350000000000004,\n... (\"H\", \"H\"): 0.4650000000000003}\n>>> coin_flips_duplicate_ans = jointly_distribute(coin_flips, coin_flips)\n>>> assert all(\n... math.isclose(coin_flips_duplicate_ans[i], pi)\n... for i, pi in coin_flips_duplicate_dist.items())\n", "hidden": false, "locked": false } ], "scored": true, "setup": "", "teardown": "", "type": "doctest" } ] }, "uniform": { "name": "uniform", "points": null, "suites": [ { "cases": [ { "code": ">>> # tests\n>>> assert uniform(\"HT\") == {\"H\": 0.5, \"T\": 0.5}\n>>> assert uniform(\"HTH\") == {\"H\": 0.5, \"T\": 0.5}\n>>> fair_dice_dist = uniform(range(1, 7))\n>>> assert all(\n... math.isclose(fair_dice_dist[k], v)\n... for k, v in {\n... 1: 0.16666666666666666,\n... 2: 0.16666666666666666,\n... 3: 0.16666666666666666,\n... 4: 0.16666666666666666,\n... 5: 0.16666666666666666,\n... 6: 0.16666666666666666,\n... }.items())\n", "hidden": false, "locked": false } ], "scored": true, "setup": "", "teardown": "", "type": "doctest" } ] } } }, "rise": { "enable_chalkboard": true, "scroll": true, "theme": "white" }, "toc": { "base_numbering": 1, "nav_menu": { "height": "195px", "width": "330px" }, "number_sections": true, "sideBar": true, "skip_h1_title": true, "title_cell": "Table of Contents", "title_sidebar": "Contents", "toc_cell": false, "toc_position": { "height": "454.418px", "left": "1533px", "top": "110.284px", "width": "435.327px" }, "toc_section_display": true, "toc_window_display": false }, "widgets": { "application/vnd.jupyter.widget-state+json": { "state": {}, "version_major": 2, "version_minor": 0 } } }, "nbformat": 4, "nbformat_minor": 4 }