Sec1_Intro.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Setups of Noisy Labels\n",
    "\n",
    "Throughout this section, you will get familiar with:\n",
    "\n",
    "* What are noisy labels?\n",
    "\n",
    "* How do we characterize noisy labels?\n",
    "\n",
    "* How do we simulate noisy labels for controlled experiments?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. What are noisy labels?\n",
    "\n",
    "* Given an instance $(X,Y)$, where $X$ is the feature, $Y$ is the clean/true label.\n",
    "* A noisy label $\\widetilde Y$ may or may not be the same as the true label."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"tutorial_imgs/label_noise.png\" width=\"1000\"> "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. How noisy is the data?\n",
    "\n",
    "**Statistical measure: Label noise transition matrix**\n",
    "\n",
    "\n",
    "### General: Instance-dependent label noise\n",
    "\n",
    "**Instance-dependent label noise transition matrix $T(X)$** \n",
    "* Different matrices for different feature $X$\n",
    "* Each element $T_{ij}(X)$: Flipping probability the clean label $Y=i$ $\\rightarrow$ the noisy label $\\widetilde{Y} = j$, given feature $X$\n",
    "\n",
    "$$\n",
    "T_{ij}(X)=\\mathbb P(\\widetilde{Y}=j|Y=i,X).\n",
    "$$\n",
    "\n",
    "### Simplified: Class-dependent label noise\n",
    "\n",
    "**Class-dependent label noise transition matrix $T$**\n",
    "* Assume $T(X) = T, \\forall X$\n",
    "* Each element $T_{ij}$: Flipping probability the clean label $Y=i$ $\\rightarrow$ the noisy label $\\widetilde{Y} = j$\n",
    "\n",
    "\n",
    "### Intuitions:\n",
    "* Capture random, averaged flipping errors\n",
    "* Enable more possibilities of theoretical analyses\n",
    "\n",
    "Remembering the previous illustration figure, we could derive a rough estimate that:\n",
    "\n",
    "<img src=\"./tutorial_imgs/label_noise_cut.png\" width=\"700\"> \n",
    "\n",
    "$\n",
    "\\mathbf{P}(\\widetilde{Y} = \\text{dog}| Y = \\text{cat}) = 1/10 = 0.1\n",
    "$\n",
    "\n",
    "$\n",
    "\\mathbf{P}(\\widetilde{Y} = \\text{cat}| Y = \\text{cat}) = 7/10 = 0.7\n",
    "$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Importance of $T$\n",
    "\n",
    "* Understanding the pattern/structure of label noise\n",
    "* Design robust loss functions\n",
    "* Helps label aggregation (weighted majority vote)\n",
    "\n",
    "#### Importance 1: Understand the pattern of label noise\n",
    "**Examples from CIFAR-10N**\n",
    "\n",
    "* CIFAR-10N: \n",
    "  * 10 classes. \n",
    "  * Each image is annotated by 3 independent human workers.\n",
    "* Aggregation labels: \n",
    "  * Take the majority vote from 3 annotations.\n",
    "  * Break ties evenly.\n",
    "\n",
    "<table>\n",
    "  <tr>\n",
    "    <td ><img src=\"./tutorial_imgs/c10_agg.png\" width=\"800\"> \n",
    "\n",
    "    Figure: Label noise transition matrix of CIFAR-10N.\n",
    "</td>\n",
    "    <td>\n",
    "    * Humans can be very accurate on some classes (ship 97%, horse 96%)<br/>\n",
    "    * Humans can be inaccurate on other classes (cat 83%, deer 83%)<br/>\n",
    "    * Human annotations have bias:<br/>\n",
    "      &nbsp;&nbsp;&nbsp;&nbsp;- Horse-deer is a pair with high similarity, <b>but</b>..<br/>\n",
    "      &nbsp;&nbsp;&nbsp;&nbsp;- Humans tend to annotate deer as horse: deer &rarr; horse 0.04<br/>\n",
    "      &nbsp;&nbsp;&nbsp;&nbsp;- Humans tend <b>not</b> to annotate horse as deer: horse &rarr; deer 0.01 <br/>\n",
    "    </td>\n",
    "  </tr>\n",
    "</table> \n",
    "\n",
    "**Examples from CIFAR-100N**\n",
    "\n",
    "* CIFAR-100N: \n",
    "  * 20 coarse classes, 100 fine classes. Each coarse class contains 5 fine classes.\n",
    "  * The human workers are asked to annotate the fine classes for each image (choose one class from the pool of 100 labels).\n",
    "  * Each image is annotated by only one human worker\n",
    "  * The following T shows the transition between coarse labels\n",
    "\n",
    "\n",
    "<table>\n",
    "  <tr>\n",
    "    <td ><img src=\"tutorial_imgs/c100_coarse.png\" width=\"1100\"> \n",
    "\n",
    "    Figure: Label noise transition matrix of CIFAR-100N.\n",
    "</td>\n",
    "    <td>\n",
    "    * Humans can be very accurate on some classes<br/>\n",
    "      &nbsp;&nbsp;&nbsp;&nbsp;- people 94%<br/>\n",
    "    * Humans can be inaccurate on other classes <br/>\n",
    "      &nbsp;&nbsp;&nbsp;&nbsp;- medium-sized mammals 47%<br/>\n",
    "    * Human annotations have bias:<br/>\n",
    "      &nbsp;&nbsp;&nbsp;&nbsp;- man-made &rarr; natural 0.09<br/>\n",
    "      &nbsp;&nbsp;&nbsp;&nbsp;- natural &rarr; man-made 0.03 <br/>\n",
    "    </td>\n",
    "  </tr>\n",
    "</table> \n",
    "\n",
    "#### Importance 2: Design robust loss functions\n",
    "\n",
    "Recall that:\n",
    "* Feature $X$, noisy label $\\widetilde Y$. \n",
    "* Model: $\\bm f(\\cdot)$ (Input: $X$, output: a column vector, probability of predicting each label class)\n",
    "* Loss function: $\\ell$.\n",
    "* Label noise transition matrix $\\bm T$, and its transpose $\\bm T^\\top$.\n",
    "\n",
    "#### Forward loss correction:\n",
    "$$\n",
    "\\ell^{\\rightarrow}(\\bm f(X),\\widetilde Y):= \\ell(\\bm T^\\top \\bm f(X),\\widetilde Y).\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Importance 3 Helps label aggregation (weighted majority vote)\n",
    "\n",
    "Intuition:\n",
    "* Normal majority vote: each labeler has the same weight. \n",
    "  * E.g., $\\text{MV}(1,1,0) = 1$.\n",
    "* Weighted majority vote: human annotation has bias (refer to Importance 1). \n",
    "  * E.g., \n",
    "    * label class 1 is rare, \n",
    "    * clean 1 --> noisy 1 is likely to make mistakes\n",
    "    * ==> we may have $\\text{MV}_\\text{Weighted}(1,1,0) = 0$.\n",
    "  * Condition:  \n",
    "    * $\\mathbb P(Y=1) = 0.2, $ \n",
    "    * $T = \\begin{pmatrix} 0.8 & 0.2 \\\\ 0.7 & 0.3 \\end{pmatrix}  $\n",
    "  * Probability of label 1: $$   \\begin{align*} & \\mathbb P(Y=1| \\widetilde Y_1 = 1, \\widetilde Y_2 = 1, \\widetilde Y_3 = 0)  \\\\ = & \\frac{\\mathbb P(Y=1)}{\\mathbb P( \\widetilde Y_1 = 1, \\widetilde Y_2 = 1, \\widetilde Y_3 = 0)} \\cdot \\mathbb P(\\widetilde Y_1=1|Y=1) \\cdot \\mathbb P(\\widetilde Y_2=1|Y=1) \\cdot \\mathbb P(\\widetilde Y_3=0|Y=1) \\\\ = & \\frac{0.0126}{\\mathbb P( \\widetilde Y_1 = 1, \\widetilde Y_2 = 1, \\widetilde Y_3 = 0)}\\end{align*}  $$\n",
    "  * Probability of label 0: $$   \\begin{align*} & \\mathbb P(Y=0| \\widetilde Y_1 = 1, \\widetilde Y_2 = 1, \\widetilde Y_3 = 0)  \\\\ = & \\frac{\\mathbb P(Y=0)}{\\mathbb P( \\widetilde Y_1 = 1, \\widetilde Y_2 = 1, \\widetilde Y_3 = 0)} \\cdot \\mathbb P(\\widetilde Y_1=1|Y=0) \\cdot \\mathbb P(\\widetilde Y_2=1|Y=0) \\cdot \\mathbb P(\\widetilde Y_3=0|Y=0) \\\\ = & \\frac{0.0256}{\\mathbb P( \\widetilde Y_1 = 1, \\widetilde Y_2 = 1, \\widetilde Y_3 = 0)} \\end{align*} $$\n",
    "  \n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. How can we simulate label noise?\n",
    "\n",
    "* **Symmetric noise** \n",
    "    * Same noise rate, even flipping. \n",
    "    * E.g., $T=\\begin{pmatrix}0.8 & 0.1 & 0.1 \\\\ 0.1 & 0.8 & 0.1 \\\\ 0.1 & 0.1 & 0.8\\end{pmatrix}$\n",
    "  \n",
    "* **Asymmetric noise (Pairflip)** \n",
    "    * Flip only to the next label class, e.g., 1-->2, 2-->3, 3-->1\n",
    "    * E.g., $T=\\begin{pmatrix}0.8 & 0.2 & 0.0 \\\\ 0.0 & 0.8 & 0.2 \\\\ 0.2 & 0.0 & 0.8\\end{pmatrix}$\n",
    "  \n",
    "* **Random noise** \n",
    "    * A random $T$\n",
    "    * E.g., $T=\\begin{pmatrix}0.7 & 0.2 & 0.1 \\\\ 0.2 & 0.6 & 0.2 \\\\ 0.2 & 0.3 & 0.5\\end{pmatrix}$\n",
    "### Simulation of class-dependent label noise"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from numpy.testing import assert_array_almost_equal\n",
    "def multiclass_noisify(y, T, random_state=0):\n",
    "    \"\"\" Flip classes according to transition probability matrix T.\n",
    "    \"\"\"\n",
    "\n",
    "    # T must satisfy the following four properties:\n",
    "    assert T.shape[0] == T.shape[1]  # requires a square matrix\n",
    "    assert np.max(y) < T.shape[0]    # E.g., 3-class classifications, np.max(y)<=2, T.shape[0]=3.\n",
    "    assert_array_almost_equal(T.sum(axis=1), np.ones(T.shape[1])) # row sum should be 1\n",
    "    assert (T >= 0.0).all()  # non-negative\n",
    "\n",
    "    m = y.shape[0]\n",
    "    noisy_y = y.copy()\n",
    "    flipper = np.random.RandomState(random_state)\n",
    "\n",
    "    for idx in np.arange(m):\n",
    "        i = y[idx] # clean label\n",
    "        flipped = flipper.multinomial(1, T[i, :], 1)[0] # take the i-th row from T, draw a vector according to the probability\n",
    "        noisy_y[idx] = np.where(flipped == 1)[0] # noisy label\n",
    "\n",
    "    return noisy_y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example:\n",
    "\n",
    "**A Toy Example**\n",
    "* Synthesize a dataset of 4,000 instances\n",
    "* Binary classification\n",
    "* Each instance has three noisy labels (given by three independent labelers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 1, 1], [1, 0, 1], [1, 1, 1], [1, 1, 1], [0, 0, 1]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "np.random.seed(0)\n",
    "num_samples = 4000\n",
    "\n",
    "# Set the label transition matrix T\n",
    "T = np.array([\n",
    "    [0.6, 0.4],\n",
    "    [0.2, 0.8],\n",
    "])\n",
    "\n",
    "# Set the clean label distribution p\n",
    "p = [0.3, 0.7]\n",
    "\n",
    "# Generate clean labels\n",
    "clean_labels = np.array([0] * int(num_samples * p[0]) + [1] * (num_samples - int(num_samples * p[0])))\n",
    "np.random.shuffle(clean_labels)\n",
    "\n",
    "# Generate three noisy labels\n",
    "noisy_labels_1 = multiclass_noisify(clean_labels, T, random_state=1)\n",
    "noisy_labels_2 = multiclass_noisify(clean_labels, T, random_state=2)\n",
    "noisy_labels_3 = multiclass_noisify(clean_labels, T, random_state=3)\n",
    "noisy_labels = [[noisy_labels_1[i], noisy_labels_2[i], noisy_labels_3[i]] for i in range(len(clean_labels))] # restructure\n",
    "\n",
    "print(noisy_labels[:5])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we have clean labels and noisy labels. We want to double-check the T to ensure we are on the right track."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The true T is:\n",
      "[[0.611 0.389]\n",
      " [0.203 0.797]]\n",
      "The true p is:\n",
      "[0.3 0.7]\n",
      "------------------------------------------\n",
      "The predefined T is:\n",
      "[[0.6 0.4]\n",
      " [0.2 0.8]]\n",
      "The predefined p is:\n",
      "[0.3, 0.7]\n"
     ]
    }
   ],
   "source": [
    "# Get the true T\n",
    "true_T = np.zeros((2,2))\n",
    "true_p = np.zeros(2)\n",
    "for i in range(len(clean_labels)):\n",
    "    for j in range(len(noisy_labels[0])):\n",
    "        true_T[clean_labels[i]][noisy_labels[i][j]] += 1\n",
    "    true_p[clean_labels[i]] += 1\n",
    "true_T /= np.sum(true_T, 1).reshape(-1,1)\n",
    "true_p /= np.sum(true_p)\n",
    "\n",
    "# Set precisions\n",
    "np.set_printoptions(precision=3)\n",
    "\n",
    "# Print the True T and p\n",
    "print(f\"The true T is:\\n{true_T}\")\n",
    "print(f\"The true p is:\\n{true_p}\")\n",
    "print(\"------\"*7)\n",
    "print(f\"The predefined T is:\\n{T}\")\n",
    "print(f\"The predefined p is:\\n{p}\")\n",
    "np.save(\"./data/clean_labels.npy\", clean_labels)\n",
    "np.save(\"./data/noisy_labels.npy\", noisy_labels)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.11.0 64-bit",
   "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.8.10"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "1a1af0ee75eeea9e2e1ee996c87e7a2b11a0bebd85af04bb136d915cefc0abce"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}