notebook.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "# Setup"
      ],
      "metadata": {
        "id": "Esn7qGxxQDmL"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "%%capture\n",
        "from google.colab import drive\n",
        "import json\n",
        "\n",
        "drive.mount('/gdrive')\n",
        "%cd /gdrive/My\\ Drive/projects/mentored_decoding/experiments\n",
        "\n",
        "def save(filename, data):\n",
        "    with open(filename, 'w', encoding=\"utf-8\") as f:\n",
        "        json.dump(data, f, ensure_ascii=False)\n",
        "\n",
        "!pip install -q -U git+https://github.com/huggingface/datasets.git\n",
        "!pip install -q -U git+https://github.com/huggingface/transformers.git\n",
        "!pip install -q -U git+https://github.com/huggingface/accelerate.git\n",
        "!pip install -q -U evaluate\n",
        "!pip install sentencepiece"
      ],
      "metadata": {
        "id": "_uibqZwCKF1t"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "feD6YzteId3J"
      },
      "outputs": [],
      "source": [
        "%%capture\n",
        "import torch\n",
        "from transformers import T5Tokenizer, T5ForConditionalGeneration\n",
        "from datasets import load_dataset\n",
        "import evaluate\n",
        "import time\n",
        "import json\n",
        "import os\n",
        "import types\n",
        "import hashlib\n",
        "\n",
        "device = torch.device('cuda:0' if torch.cuda.is_available() else 'cpu')\n",
        "\n",
        "target_model_id = \"t5-large\"\n",
        "draft_model_id = \"t5-small\"\n",
        "\n",
        "tokenizer = T5Tokenizer.from_pretrained(draft_model_id)\n",
        "\n",
        "target_model = T5ForConditionalGeneration.from_pretrained(\n",
        "    target_model_id,\n",
        "    torch_dtype=torch.float16,\n",
        "    device_map=\"auto\"\n",
        ").eval()\n",
        "\n",
        "draft_model = T5ForConditionalGeneration.from_pretrained(\n",
        "    draft_model_id,\n",
        "    device_map=\"auto\"\n",
        ").eval()\n",
        "\n",
        "NUM_SAMPLES = 1000\n",
        "GEN_LEN = draft_model.config.task_specific_params[\"translation_en_to_fr\"][\"max_length\"]\n",
        "PREFIX = draft_model.config.task_specific_params[\"translation_en_to_fr\"][\"prefix\"]\n",
        "\n",
        "ds = load_dataset(\"wmt15\", \"fr-en\", split=\"validation\", streaming=True)\n",
        "bleu = evaluate.load(\"bleu\")"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Sampling methods\n",
        "\n"
      ],
      "metadata": {
        "id": "HU4mRCc9QIoy"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "N3yAwLSNId3K"
      },
      "outputs": [],
      "source": [
        "def greedy_decoding(q):\n",
        "    \"\"\"\n",
        "    Sample a token with greedy decoding\n",
        "    \"\"\"\n",
        "    return torch.argmax(q, -1)\n",
        "\n",
        "def multinomial_sampling(q):\n",
        "    \"\"\"\n",
        "    Sample a token with multinomial sampling\n",
        "    \"\"\"\n",
        "    return torch.multinomial(q, 1)\n",
        "\n",
        "def speculative_sampling(x, p, q):\n",
        "    \"\"\"\n",
        "    Sample a token with speculative sampling\n",
        "    \"\"\"\n",
        "    random_number = torch.rand(1)[0]\n",
        "    if random_number*p[x] < q[x]:\n",
        "        return x\n",
        "    else:\n",
        "        s = torch.clip(q-p, min=0)\n",
        "        s /= s.sum()\n",
        "        return torch.multinomial(s, 1)\n",
        "\n",
        "def mentored_sampling(x, p, q, target_dkl, tol=0.2):\n",
        "    \"\"\"\n",
        "    Sample a token with mentored sampling\n",
        "    \"\"\"\n",
        "    random_number = torch.rand(1)[0]\n",
        "    # Whatever the target KL divergence, we know that P(x accepted) ≥ min(1, q(x)/p(x))\n",
        "    if random_number*p[x] < q[x]:\n",
        "        return x\n",
        "\n",
        "    q_over_p = q/p\n",
        "    sorted_q_over_p, argsort_q_over_p = torch.sort(q_over_p)\n",
        "    sorted_q = q[argsort_q_over_p]\n",
        "    cumsum_q_log_q_over_p = (sorted_q*torch.log(sorted_q_over_p)).cumsum(-1)\n",
        "\n",
        "    # If the KL divergence between q and p is less than the target KL\n",
        "    # divergence, we can direct accept the draft token (we're ready to accept a\n",
        "    # slightly higher KL divergence to reduce the computational overhead)\n",
        "    dkl = cumsum_q_log_q_over_p[-1]\n",
        "    higher_bound = target_dkl*(1+tol)\n",
        "    if dkl <= higher_bound:\n",
        "        return x\n",
        "\n",
        "    sorted_p = p[argsort_q_over_p]\n",
        "    cumsum_p = sorted_p.cumsum(-1)\n",
        "    cumsum_q = sorted_q.cumsum(-1)\n",
        "    cumsum_last_p = torch.flip(torch.flip(sorted_p, [0]).cumsum(-1), [0])\n",
        "    cumsum_last_q = torch.flip(torch.flip(sorted_q, [0]).cumsum(-1), [0])\n",
        "    right = cumsum_last_q / sorted_q_over_p - cumsum_last_p\n",
        "\n",
        "    # We're ready to accept a slightly higher KL divergence to reduce the\n",
        "    # computational overhead\n",
        "    lower_bound = target_dkl*(1-tol)\n",
        "\n",
        "    min_alpha, max_alpha = 0, 1\n",
        "    best_alpha, best_beta, best_one_minus_R, best_dkl = 1, 1, 1 - (torch.clip(q/p, max=1)*p).sum(), 0\n",
        "    for _ in range(10):\n",
        "        alpha = (min_alpha + max_alpha)/2\n",
        "        try:\n",
        "            n1 = torch.nonzero(sorted_q_over_p <= alpha)[-1]\n",
        "        except IndexError:\n",
        "            n1 = 0\n",
        "        one_minus_R = cumsum_p[n1] - cumsum_q[n1] / alpha\n",
        "        try:\n",
        "            n2 = torch.nonzero(right <= one_minus_R)[0]\n",
        "        except IndexError:\n",
        "            n2 = -1\n",
        "        beta = cumsum_last_q[n2-1]/(one_minus_R + cumsum_last_p[n2-1])\n",
        "        if one_minus_R < 0:\n",
        "            dkl = cumsum_q_log_q_over_p[-1]\n",
        "        else:\n",
        "            dkl = (\n",
        "                torch.math.log(alpha)*cumsum_q[n1]\n",
        "                + cumsum_q_log_q_over_p[n2-1]\n",
        "                - cumsum_q_log_q_over_p[n1]\n",
        "                + torch.math.log(beta)*cumsum_last_q[n2]\n",
        "            )\n",
        "\n",
        "        if dkl < lower_bound:\n",
        "            max_alpha = alpha\n",
        "            best_alpha, best_beta, best_one_minus_R, best_dkl = alpha, beta, one_minus_R, dkl\n",
        "        elif dkl > higher_bound:\n",
        "            min_alpha = alpha\n",
        "        else:\n",
        "            break\n",
        "    else:\n",
        "        alpha, beta, one_minus_R, dkl = best_alpha, best_beta, best_one_minus_R, best_dkl\n",
        "\n",
        "    # With α, we can now definitely accept or reject the token sampled from p\n",
        "    if alpha*random_number < q_over_p[x]:\n",
        "        return x\n",
        "\n",
        "    # If the candidate token is rejected, we sample from s\n",
        "    s = torch.clip(sorted_q/beta-sorted_p, min=0)/one_minus_R\n",
        "    return argsort_q_over_p[torch.multinomial(s, 1)]"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Implementation of multinomial sampling, speculative decoding and mentored decoding"
      ],
      "metadata": {
        "id": "6evNRciTQPyk"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "GyVI-XvSId3L"
      },
      "outputs": [],
      "source": [
        "def generate(\n",
        "    llm,\n",
        "    encoder_tokens,\n",
        "    decoder_tokens,\n",
        "    num_new_tokens,\n",
        "    temperature=0.3,\n",
        "    return_proba=False,\n",
        "    past_key_values=None,\n",
        "    encoder_last_hidden_state = None\n",
        "):\n",
        "    \"\"\"\n",
        "    Generate a sequence of tokens with multinomial sampling\n",
        "    \"\"\"\n",
        "    num_tokens = decoder_tokens.shape[-1]\n",
        "    attention_mask = torch.ones((1, num_tokens)).to(device)\n",
        "    if past_key_values is not None:\n",
        "        num_tokens += past_key_values[0][0].shape[2]\n",
        "    initial_num_tokens = num_tokens\n",
        "    input_ids = encoder_tokens if past_key_values is None else None\n",
        "    decoder_input_ids = decoder_tokens[:, -1:]\n",
        "    proba = None\n",
        "    outputs = types.SimpleNamespace()\n",
        "    outputs.past_key_values = past_key_values\n",
        "    outputs.encoder_last_hidden_state = encoder_last_hidden_state\n",
        "\n",
        "    for _ in range(num_new_tokens):\n",
        "        with torch.no_grad():\n",
        "            if outputs.past_key_values is None:\n",
        "                outputs = llm(\n",
        "                    input_ids=input_ids,\n",
        "                    decoder_input_ids=decoder_input_ids,\n",
        "                    use_cache=True\n",
        "                )\n",
        "            else:\n",
        "                outputs = llm(\n",
        "                    decoder_input_ids=decoder_input_ids,\n",
        "                    past_key_values=outputs.past_key_values,\n",
        "                    encoder_outputs=(outputs.encoder_last_hidden_state,),\n",
        "                    use_cache=True\n",
        "                )\n",
        "\n",
        "        q = torch.softmax(outputs.logits[0, -1:, :].float()/temperature, -1)\n",
        "        if return_proba:\n",
        "            if proba is None:\n",
        "                proba = q\n",
        "            else:\n",
        "                proba = torch.concat((proba, q), axis=0)\n",
        "        decoder_input_ids = multinomial_sampling(q[0]).reshape((1, 1))\n",
        "        decoder_tokens = torch.concat((decoder_tokens, decoder_input_ids), axis=-1)\n",
        "        num_tokens += 1\n",
        "        if decoder_input_ids[0, 0] == tokenizer.eos_token_id:\n",
        "            break\n",
        "\n",
        "    return (\n",
        "        decoder_tokens,\n",
        "        num_tokens - initial_num_tokens,\n",
        "        outputs.past_key_values,\n",
        "        outputs.encoder_last_hidden_state,\n",
        "        proba if return_proba else q\n",
        "    )"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "GVTfgr00Id3M"
      },
      "outputs": [],
      "source": [
        "def truncate(past_key_values, n):\n",
        "    \"\"\"\n",
        "    Truncate past key values to keep only the `n` first ones\n",
        "    \"\"\"\n",
        "    return tuple(\n",
        "        (\n",
        "            x[0][:, :, :n, :],\n",
        "            x[1][:, :, :n, :],\n",
        "            x[2],\n",
        "            x[3]\n",
        "        )\n",
        "        for x in past_key_values\n",
        "    )"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "KDDfwBn2Id3M"
      },
      "outputs": [],
      "source": [
        "def verify(target_proba, draft_proba, draft_tokens, target_dkl):\n",
        "    \"\"\"\n",
        "    Verify a sequence tokens given the target and draft probabilities.\n",
        "    \"\"\"\n",
        "    selected_tokens = []\n",
        "    #assert draft_proba.shape[0] == target_proba.shape[0] - 1\n",
        "\n",
        "    for i in range(draft_proba.shape[0]):\n",
        "        p, q = draft_proba[i, :], target_proba[i, :]\n",
        "        candidate_token = draft_tokens[0, -draft_proba.shape[0]+i]\n",
        "        if target_dkl == 0:\n",
        "            selected_token = speculative_sampling(candidate_token, p, q).reshape((1, 1))\n",
        "        else:\n",
        "            selected_token = mentored_sampling(candidate_token, p, q, target_dkl).reshape((1, 1))\n",
        "\n",
        "        if i == 0:\n",
        "            selected_tokens = selected_token\n",
        "        else:\n",
        "            selected_tokens = torch.concat((selected_tokens, selected_token), axis=-1)\n",
        "        if selected_token[0, 0] == tokenizer.eos_token_id:\n",
        "            break\n",
        "        if selected_token != draft_tokens[0, -draft_proba.shape[0]+i]:\n",
        "            break\n",
        "    else:\n",
        "        q = target_proba[-1, :]\n",
        "        selected_token = multinomial_sampling(q).reshape((1, 1))\n",
        "        selected_tokens = torch.concat((selected_tokens, selected_token), axis=-1)\n",
        "    return selected_tokens"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "AtRIm3kIId3N"
      },
      "outputs": [],
      "source": [
        "def draft_and_verify(\n",
        "    target_llm,\n",
        "    draft_llm,\n",
        "    encoder_tokens,\n",
        "    decoder_tokens,\n",
        "    num_new_tokens,\n",
        "    target_dkl=0,\n",
        "    draft_length=5,\n",
        "    temperature=0.3\n",
        "):\n",
        "    \"\"\"\n",
        "    Generate a sequence of tokens with mentored decoding\n",
        "    \"\"\"\n",
        "    num_tokens = decoder_tokens.shape[-1]\n",
        "    initial_num_tokens = num_tokens\n",
        "    max_num_tokens = num_tokens + num_new_tokens\n",
        "    num_selected = []\n",
        "    target_past_key_values = None\n",
        "    draft_past_key_values = None\n",
        "    draft_encoder_last_hidden_state = None\n",
        "\n",
        "    while num_tokens < max_num_tokens:\n",
        "\n",
        "        # After the first iteration, we need to provide the past key values that\n",
        "        # are still valid\n",
        "        if draft_past_key_values is not None:\n",
        "\n",
        "            # For the target model, we keep all past key values corresponding to\n",
        "            # the generated tokens except the last one\n",
        "            target_past_key_values = truncate(target_outputs.past_key_values, num_tokens-1)\n",
        "\n",
        "            # If all draft tokens except maybe the last one were verified, we\n",
        "            # keep all the past key values of the draft model. If not we keep\n",
        "            # those corresponding to all generated tokens except the last one\n",
        "            if selected_tokens.shape[1] < draft_length:\n",
        "                draft_past_key_values = truncate(draft_past_key_values, num_tokens-1)\n",
        "\n",
        "            # δ equals 1 or 2. That's the number of generated tokens for which\n",
        "            # the past key values haven't been computed by the draft model\n",
        "            delta = num_tokens - draft_past_key_values[0][0].shape[2]\n",
        "            decoder_input_ids = decoder_tokens[:, -delta:]\n",
        "            prefix = decoder_tokens[:, :-delta]\n",
        "        else:\n",
        "            decoder_input_ids = decoder_tokens\n",
        "            prefix = None\n",
        "\n",
        "        # We generate draft tokens\n",
        "        draft_tokens, num_new_tokens, draft_past_key_values, draft_encoder_last_hidden_state, draft_proba = generate(\n",
        "            draft_llm,\n",
        "            encoder_tokens,\n",
        "            decoder_input_ids,\n",
        "            draft_length,\n",
        "            return_proba=True,\n",
        "            past_key_values=draft_past_key_values,\n",
        "            encoder_last_hidden_state=draft_encoder_last_hidden_state\n",
        "        )\n",
        "        if prefix is not None:\n",
        "            draft_tokens = torch.concat((prefix, draft_tokens), axis=-1)\n",
        "\n",
        "        # We compute the next token probabilities for draft tokens\n",
        "        with torch.no_grad():\n",
        "            if target_past_key_values is None:\n",
        "                target_outputs = target_llm(\n",
        "                    input_ids=encoder_tokens,\n",
        "                    decoder_input_ids=draft_tokens,\n",
        "                    use_cache=True\n",
        "                )\n",
        "            else:\n",
        "                target_outputs = target_llm(\n",
        "                    decoder_input_ids=draft_tokens[:, (num_tokens-1):],\n",
        "                    encoder_outputs=(target_outputs.encoder_last_hidden_state,),\n",
        "                    past_key_values=target_past_key_values,\n",
        "                    use_cache=True\n",
        "                )\n",
        "\n",
        "        target_proba = torch.softmax(\n",
        "            target_outputs.logits[0, -num_new_tokens-1:, :].float()/temperature,\n",
        "            -1\n",
        "        )\n",
        "\n",
        "        # Probabilities slightly increased for numerical stability purposes\n",
        "        target_proba += 1e-12\n",
        "        target_proba /= target_proba.sum(axis=-1, keepdim=True)\n",
        "        draft_proba += 1e-12\n",
        "        draft_proba /= draft_proba.sum(axis=-1, keepdim=True)\n",
        "\n",
        "        # We use the rejection sampling scheme to verify tokens\n",
        "        selected_tokens = verify(target_proba, draft_proba, draft_tokens, target_dkl)\n",
        "\n",
        "        decoder_tokens = torch.concat((decoder_tokens, selected_tokens), axis=-1)\n",
        "        num_tokens += selected_tokens.shape[1]\n",
        "        num_selected.append(selected_tokens.shape[1])\n",
        "        if decoder_tokens[0, -1] == tokenizer.eos_token_id:\n",
        "            break\n",
        "\n",
        "    return decoder_tokens[:, :max_num_tokens], min(max_num_tokens, num_tokens) - initial_num_tokens, num_selected"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Experiments"
      ],
      "metadata": {
        "id": "FQ7a4sb8P51P"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "7wfN7yybId3N"
      },
      "outputs": [],
      "source": [
        "configs = [(0, 0, model, temperature) for model in [\"draft\", \"target\"] for temperature in [0.3]]\n",
        "configs += [(dkl, draft_length, \"speculative\", temperature) for draft_length in [3, 5, 7, 9, 11, 13, 15] for dkl in [0, 0.1, 0.15, 0.2] for temperature in [0.3]]"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "jmckC1ZAId3O"
      },
      "outputs": [],
      "source": [
        "def log_result(dkl, draft_length, model, temperature, example):\n",
        "    \"\"\"\n",
        "    Perform an experiment and record its results\n",
        "    \"\"\"\n",
        "    idx = hashlib.md5(example[\"translation\"][\"en\"].encode()).hexdigest()\n",
        "    filename = f\"{model}_t{temperature}_dkl{dkl}_dl{draft_length}_{idx}.json\"\n",
        "\n",
        "    encoder_tokens = tokenizer(\n",
        "        f\"{PREFIX}{example['translation']['en']}\",\n",
        "        return_tensors=\"pt\"\n",
        "    ).input_ids.to(device)\n",
        "    decoder_tokens = torch.zeros((1, 1), dtype=int).to(device)\n",
        "\n",
        "    start = time.time()\n",
        "    if draft_length == 0:\n",
        "        tokens, num_new_tokens, _, _, _ = generate(\n",
        "            draft_model if model == \"draft\" else target_model,\n",
        "            encoder_tokens,\n",
        "            decoder_tokens,\n",
        "            GEN_LEN,\n",
        "            return_proba=False,\n",
        "            temperature=temperature\n",
        "        )\n",
        "    else:\n",
        "        tokens, num_new_tokens, _ = draft_and_verify(\n",
        "            target_model,\n",
        "            draft_model,\n",
        "            encoder_tokens,\n",
        "            decoder_tokens,\n",
        "            GEN_LEN,\n",
        "            target_dkl=dkl,\n",
        "            draft_length=draft_length,\n",
        "            temperature=temperature\n",
        "        )\n",
        "    delay = time.time() - start\n",
        "    prediction = tokenizer.decode(tokens[0, -num_new_tokens:], skip_special_tokens=True).strip()\n",
        "\n",
        "    try:\n",
        "        results = bleu.compute(\n",
        "            predictions=[prediction],\n",
        "            references=[example[\"translation\"][\"fr\"]]\n",
        "        )\n",
        "    except ZeroDivisionError:\n",
        "        results = {\n",
        "            'bleu': 0.0,\n",
        "            'precisions': [0.0, 0.0, 0.0, 0.0],\n",
        "            'brevity_penalty': 1.0,\n",
        "            'length_ratio': 1.0,\n",
        "            'translation_length': 1,\n",
        "            'reference_length': 1\n",
        "        }\n",
        "\n",
        "    log = {\n",
        "        \"output\": prediction,\n",
        "        \"num_tokens\": num_new_tokens,\n",
        "        \"delay\": delay,\n",
        "        **results\n",
        "    }\n",
        "\n",
        "    save(filename, log)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "M6tFK4XvId3O"
      },
      "outputs": [],
      "source": [
        "for example in iter(ds.take(NUM_SAMPLES)):\n",
        "    for config in configs:\n",
        "        log_result(*config, example)"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Visualization of results"
      ],
      "metadata": {
        "id": "u7TGeN0iP_KG"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import os\n",
        "import pandas as pd\n",
        "\n",
        "data = {\n",
        "    \"model\": [],\n",
        "    \"temperature\": [],\n",
        "    \"dkl\": [],\n",
        "    \"draft_length\": [],\n",
        "    \"example_id\": [],\n",
        "    \"bleu\": [],\n",
        "    \"num_tokens\": [],\n",
        "    \"delay\": []\n",
        "}\n",
        "\n",
        "for f in os.listdir():\n",
        "    if \".json\" in f:\n",
        "        model, temperature, dkl, draft_length, i = f.split(\".json\")[0].split(\"_\")\n",
        "        data[\"model\"].append(model)\n",
        "        data[\"temperature\"].append(float(temperature[1:]))\n",
        "        data[\"dkl\"].append(float(dkl[3:]))\n",
        "        data[\"draft_length\"].append(int(draft_length[2:]))\n",
        "        data[\"example_id\"].append(i)\n",
        "        with open(f) as file:\n",
        "            results = json.loads(file.read())\n",
        "        for k in [\"bleu\", \"num_tokens\", \"delay\"]:\n",
        "            data[k].append(results[k])\n",
        "\n",
        "df = pd.DataFrame.from_dict(data)\n",
        "grouped = df.groupby([\"model\", \"temperature\", \"dkl\", \"draft_length\"]).sum()\n",
        "grouped[\"token_per_second\"] = grouped[\"num_tokens\"]/grouped[\"delay\"]\n",
        "grouped2 = df.groupby([\"model\", \"temperature\", \"dkl\", \"draft_length\"]).mean()\n",
        "grouped3 = df.groupby([\"model\", \"temperature\", \"dkl\", \"draft_length\"]).count()\n",
        "grouped[\"bleu\"] = grouped2[\"bleu\"]\n",
        "grouped[\"count\"] = grouped3[\"delay\"]\n",
        "grouped"
      ],
      "metadata": {
        "id": "UWZZtxQcOGCO"
      },
      "execution_count": null,
      "outputs": []
    }
  ],
  "metadata": {
    "associatedRecipe": "compute_xeUNIFh8",
    "createdOn": 1694886686931,
    "creator": "vivien.tran-thien",
    "customFields": {},
    "hide_input": false,
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "modifiedBy": "vivien.tran-thien",
    "tags": [
      "recipe-editor"
    ],
    "colab": {
      "provenance": [],
      "gpuType": "T4"
    },
    "accelerator": "GPU",
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}