tutorial_exp-sizing.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# _TriScale_ - Experiment Sizing\n",
    "\n",
    "> This notebook is intended for **self-study** of _TriScale._  \n",
    "Here is the [version for live sessions](live_exp-sizing.ipynb).\n",
    "\n",
    "This notebook contains tutorial materials for _TriScale_. \n",
    "\n",
    "More specifically, this notebook presents _TriScale_'s `experiment_sizing` function,  \n",
    "which implement a methodology to define the minimal number of runs required to estimate  \n",
    "a certain performance objective with a given level of confidence. \n",
    "\n",
    "> If you don't know about Jupyter Notebooks and how to interact with them,  \n",
    "fear not! We compiled everything that you need to know here: [Notebook Basics](tutorial_notebook-basics.ipynb) :-) \n",
    "\n",
    "\n",
    "For more details about _TriScale,_ you may refer to [the paper](https://doi.org/10.5281/zenodo.3464273).\n",
    "\n",
    "---\n",
    "\n",
    "- [Banana: a black-box example](#Banana:-a-black-box-example)\n",
    "- [Opening the box](#Opening-the-box)\n",
    "    - [Basic computation](#Basic-computation)\n",
    "    - [What about upper bounds instead?](#What-about-upper-bounds-instead?)\n",
    "    - [What about better bounds?](#What-about-better-bounds?)\n",
    "- [Your turn: time to practice](#Your-turn:-time-to-practice)\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To get started, we need to import a few Python modules.  \n",
    "All the _TriScale_-specific functions are part of one module called `triscale`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "from pathlib import Path\n",
    "\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "\n",
    "import triscale"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alright, we are ready to size some experiments!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Banana: a black-box example\n",
    "\n",
    "Throughout the [tutorial presentation](link-to-slides), we used the Banana communication protocol as an example.  \n",
    "Before having a closer look at what _TriScale_ offers, let us simply use the tool to see how many runs we need.\n",
    "\n",
    "**Evaluation objective**  \n",
    "Let us say we want to measure the overall energy consumption achieved by the protocol.  \n",
    "For this purpose, we can use a simple metric: the sum of the energy consumed by all nodes in the network. \n",
    "\n",
    "> Note: We could pick _any metric_; the choice of the metric is independent of TriScale's methodology.\n",
    "\n",
    "**Performance indicator**  \n",
    "TriScale uses percentiles of the metric values as performance indicators.  \n",
    "The goal of the experiments is to obtain an estimate of such a percentile for a given level of confidence. \n",
    ">These estimates are refered to as KPIs, or Key Performance Indicators.\n",
    "\n",
    "For our performance metric (energy consumption), the lower the value, the better.  \n",
    "Thus, we want to derive an upper bound for our chosen percentile and (hopefully) show that this bound is small. \n",
    "\n",
    "So let us go ahead and define the percentive we want to estimate and the confidence level for that estimation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition of Banana's KPI\n",
    "percentile = 50 # the median\n",
    "confidence = 95 # the confidence level, in %"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These two values are sufficient to define the minimal number of runs required to compute this KPI.  \n",
    "The computation is implemented in _TriScale_'s `experiment_sizing()` function: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "triscale.experiment_sizing(\n",
    "    percentile, \n",
    "    confidence,\n",
    "    verbose=True); "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> We need a **minimum of 5 runs.**\n",
    "\n",
    "We can now do the same thing to estimate the long-term variability with the variability score."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition of Banana's variability score\n",
    "percentile = 25 # the median\n",
    "confidence = 95 # the confidence level, in %"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "triscale.experiment_sizing(\n",
    "    percentile, \n",
    "    confidence,\n",
    "    verbose=True); "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> We need a **minimum of 11 series.**\n",
    "\n",
    "Hence, with only these four parameters, we can connect the total number of runs one needs  \n",
    "to perform (a minimum of 11 series of 5 runs) with the corresponding performance claims that one can make:\n",
    "> **KPI**: In a series of runs, the median value of the runs metric values is lower or equal  \n",
    "to the KPI with a confidence of 95%.\n",
    "\n",
    "> **Variability score**: The range of KPI values of the middle 50% of series is less or equal  \n",
    "to the variability score, with a confidence of 95%."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Opening the box\n",
    "\n",
    "In the previous section, we've seen on an example the basic usage of _TriScale_'s `experiment_sizing()` function.  \n",
    "Let us now open the box a bit and explain how things work underneath.\n",
    "\n",
    "<!--During the design phase of an experiment, one important question to answer is:  \n",
    "> __How many times should the experiment be performed?__  \n",
    "\n",
    "This question directly relates to the definition of _TriScale_ KPIs and variability scores. -->\n",
    "\n",
    "### Basic computation\n",
    "\n",
    "_TriScale_ implements a statistical method that allows to estimate, based on a data sample,  \n",
    "any percentile of the underlying distribution with any level of confidence. Importantly,  \n",
    "the estimation does not rely on any assumption on the nature of the underlying distribution  \n",
    "(e.g., normal, or Poisson). The estimate is valid as long as the sample is independent and  \n",
    "identically distributed (or _iid_ ).\n",
    "\n",
    "Intuitively, it is \"easier\" to estimate the median (50th percentile) than the 99th percentile;  \n",
    "the more extreme the percentile, the more samples are required to provide an estimate for a  \n",
    "given level of confidence. \n",
    "\n",
    "Let us consider the samples $x$ are ordered such that $x_1 \\leq x_2 \\ldots \\leq x_N$. One can  derive  \n",
    "the minimal number of samples $N$ such that $x_1$ is a lower bound for  any percentile  $0<p<1$  \n",
    "with a level of confidence $0<C<1$ using the following equation:\n",
    "\n",
    "$$N \\;\\geq\\; \\frac{log(1-C)}{log(1-p)}$$\n",
    "\n",
    "_TriScale_'s `experiment_sizing()` function implements this computation and returns the  \n",
    "minimal number of samples $N$, as illustrated below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Select the percentile we want to estimate \n",
    "percentile = 10\n",
    "\n",
    "# Select the desired level of confidence for the estimation\n",
    "confidence = 99 # in %\n",
    "\n",
    "# Compute the minimal number of samples N required\n",
    "triscale.experiment_sizing(\n",
    "    percentile, \n",
    "    confidence,\n",
    "    verbose=True); "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The previous result indicates that for $N = 44$ samples and above,  $x_1$ is a lower bound  \n",
    "for the 10th percentile with probibility larger than 99%. \n",
    "\n",
    "### What about upper bounds instead?\n",
    "\n",
    "The probability distributions are symetric: it takes the same number of samples to compute  \n",
    "a lower bound for the $p$-th percentile as to compute an upper bound for the $(1-p)$-th percentile.\n",
    "\n",
    "`triscale.experiment_sizing` returns the required number of samples to estimate \n",
    "- a lower bound for percentiles $p <= 0.5$\n",
    "- an upper bound for percentiles $p>0.5$\n",
    "\n",
    "Hence, the following cell returns the same number of samples required as previously:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "percentile = 90\n",
    "confidence = 99 # in %\n",
    "\n",
    "triscale.experiment_sizing(\n",
    "    percentile, \n",
    "    confidence,\n",
    "    verbose=True); "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To get a better feeling of how this minimal number of samples evolves this increasing confidence  \n",
    "and more extreme percentiles, let us compute a range of minimal number of samples and display  \n",
    "the results in a table (where the columns are the percentiles to estimate).\n",
    "\n",
    "> You don't need to understand the code in the following cell. We simply computes the required  \n",
    "number of samples for a list of percentiles and confidence levels, and store everything in a  \n",
    "Pandas DataFrame for a nicer display in tabular format."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Sets of percentiles and confidence levels to try\n",
    "percentiles = [0.1, 1, 5, 10, 25, 50, 75, 90, 95, 99, 99.9]\n",
    "confidences = [75, 90, 95, 99, 99.9, 99.99]\n",
    "\n",
    "# Computing the minimum number of runs for each (perc., conf.) pair\n",
    "min_number_samples = []\n",
    "for c in confidences:\n",
    "    tmp = []\n",
    "    for p in percentiles:\n",
    "        N = triscale.experiment_sizing(p,c)\n",
    "        tmp.append(N[0])\n",
    "    min_number_samples.append(tmp)\n",
    "    \n",
    "# Put the results in a DataFrame for a convenient display of the results\n",
    "df = pd.DataFrame(columns=percentiles, data=min_number_samples)\n",
    "df['Confidence level'] = confidences\n",
    "df.set_index('Confidence level', inplace=True)\n",
    "\n",
    "display(df)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What about better bounds?\n",
    "\n",
    "So far, we have seen how to compute the minimal number of samples such that $x_1$ is a valid lower bound.  \n",
    "This implies that the estimate is then equal to the __smallest value__ obtained in your series of runs. \n",
    "\n",
    "If you work in a domain where outliers are common, you will want to get better bounds, which should be  \n",
    "less affected by outliers. Good news, this is simple: you just need to run more experiments! \n",
    "\n",
    "The `experiment_sizing()` function takes an optional `robustness` argument that defines how many  \n",
    "outliers you want your bound to exclude. In other words, for a `robustness` or $r$, the function returns  \n",
    "the minimal number of samples required such that $x_{r+1}$ is a valid lower bound. \n",
    "This is illustrated below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "percentile = 10\n",
    "confidence = 99\n",
    "triscale.experiment_sizing(\n",
    "    percentile, \n",
    "    confidence,\n",
    "    robustness=3,\n",
    "    verbose=True); "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We obtain that a minimum of $N = 97$ samples are required such that $x_4$ is a lower bound for the  \n",
    "10th percentile with a confidence level of 99%.\n",
    "\n",
    "> Naturally, this is (much) more than the 44 samples we got before, where $x_1$ was the  \n",
    "lower bound. There is no free lunch! Better bounds demand more experiments.  \n",
    "But at least, now you know how many you need :-)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Your turn: time to practice\n",
    "\n",
    "Based on the explanations above, use _TriScale_'s `experiment_sizing` function to answer  \n",
    "the following questions:\n",
    "- What is the minimal number of runs required to estimate the\n",
    "    - **90th** percentile with **90%** confidence?\n",
    "    - **90th** percentile with **95%** confidence?\n",
    "    - **95th** percentile with **90%** confidence?\n",
    "- Based on the answers to the previous questions, is it harder (i.e., does it require more runs)  \n",
    "to increase the confidence level, or to estimate a more extreme percentile? \n",
    "\n",
    "_Optional (and harder) question:_ \n",
    "- For $N = 50$ samples, what is the index $m$ of the best possible (i.e., the largest) lower bound  \n",
    "for the 25th percentile, estimated with a 95% confidence level? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "########## YOUR CODE HERE ###########\n",
    "# ...\n",
    "#####################################"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solutions\n",
    "\n",
    "<details>\n",
    "  <summary><br/>Click here show the solutions</summary>\n",
    "  \n",
    "```python\n",
    ">>> print(triscale.experiment_sizing(90,90)[0])\n",
    "22\n",
    ">>> print(triscale.experiment_sizing(90,95)[0])\n",
    "29\n",
    ">>> print(triscale.experiment_sizing(95,90)[0])\n",
    "45\n",
    "```\n",
    "We observe that it \"costs\" many more runs to estimate a more extreme percentile  \n",
    "    (95th instead of 90th) than to increase the confidence level (90% to 95%).  \n",
    "    This observation holds true in general. The number of runs required increases   \n",
    "    exponentially when the percentiles get more extreme (close to $0$      or to $1$).\n",
    "    \n",
    "For the last question, we must play with the `robusteness` parameter. We can \n",
    "    write a simple loop to increase its value until the number of runs required  \n",
    "    reaches 50.\n",
    "    \n",
    "```python\n",
    ">>> r = 0\n",
    ">>> while (triscale.experiment_sizing(25,95,r)[0] < 50):\n",
    ">>>     r += 1 \n",
    ">>> print(r)\n",
    "7                                           \n",
    "```        \n",
    "Hence, we can exclude the 7 \"worst\" samples from the confidence interval.  \n",
    "    With $N=50$ samples, the best lower bound for the 25th percentile with 95% confidence  \n",
    "    is $x_8$     (assuming the first sample is $x_1$).\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "Next step: [Data Analysis](tutorial_data-analysis.ipynb)  \n",
    "[Back to repo](.)"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "684f90775fb1f43db0d8eed0780ba829f42a97c2f4b9a1bd592c18e47e5c272e"
  },
  "kernelspec": {
   "display_name": "Python 3",
   "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.9.6"
  },
  "metadata": {
   "interpreter": {
    "hash": "684f90775fb1f43db0d8eed0780ba829f42a97c2f4b9a1bd592c18e47e5c272e"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}