Chapter 04 - Linear Neural Networks for Classification.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "dc730f53",
   "metadata": {},
   "source": [
    "# Chapter 4: Linear Neural Networks for Classification\n",
    "\n",
    "### Dhuvi Karthikeyan\n",
    "\n",
    "##### 1/16/2023"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b64e6281",
   "metadata": {},
   "source": [
    "## 4.1 Softmax Regression\n",
    "\n",
    "Interesting Multi-Class Labeling Papers Referenced in the Textbook:\n",
    "\n",
    "https://arxiv.org/abs/1508.01991 - Bi-LSTM-CRF for sequence tagging\n",
    "\n",
    "https://www.igi-global.com/gateway/article/1786 - Multi-Label classification: An overview"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a38132ea",
   "metadata": {},
   "source": [
    "#### Digression into Conditional-Random Fields (CRFs) - [Bi-LSTMs come up later]\n",
    "\n",
    "CRFs are a standard model class for entity recognition problems. They combine desirable qualities from maximum entropy markov models (MEMMs) and Hidden Markov Models (HMMs). The model is as follows:\n",
    "\n",
    "$$ p(\\textbf{y}|\\textbf{x}) = \\frac{1}{Z(x)}\\prod_{t=1}^T \\exp{\\sum_{k=1}^K\\theta_kf_k(y_t, y_{t-1}, x_t)}$$\n",
    "\n",
    "where $\\frac{1}{Z(t)}$ is the normalization, $\\theta_k$ is the weight of feature k and $f_k(y_t, y_{t-1}, x_t)$ is the feature function of feature k\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "399aecbb",
   "metadata": {},
   "source": [
    "### 4.1.1 Classification\n",
    "\n",
    "* In regression, we mapped input features to a continuous output. \n",
    "* Classification on the other hand seeks to do one of two things:\n",
    "    * Hard classification: assign an example to a class [clustering based?]\n",
    "    * Soft classification: identify the probability that the example belongs to each class\n",
    "* Assigning labels {1,2,3,4} for a problem with 4 classes assumes an ordinal structure to the data and hence breaks during training -> One hot encoding"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c0e05d7",
   "metadata": {},
   "source": [
    "#### Linear Model\n",
    "\n",
    "* Taking the four class problem a linear model for classification would have a linear model for each set of classes where the output for class 1, $O_i= x_iw_{11} + x_2w_{i2} + .. x_nW_{in} + b_1$ for each class.\n",
    "\n",
    "#### Softmax Function\n",
    "\n",
    "* $ y_i = \\frac{exp(o_i)}{\\sum_j exp(o_j)}$\n",
    "* Softmax is nonnegative, monotonic, conditional probabilities increase with $o_i$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d50fb064",
   "metadata": {},
   "source": [
    "### 4.1.2 Loss Function"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d327cf13",
   "metadata": {},
   "source": [
    "* After finding the mapping (system of linear equations, one per class), we need to choose a loss function to optimize the weights and biases.\n",
    "\n",
    "#### Log-Likelihood\n",
    "\n",
    "We can take the output of the softmax to represent the conditional likelihoods of each class given the features. So we have the distribution for each example.\n",
    "\n",
    "\n",
    "* Take matrix of feature vectors X and matrix of one-hot label encoding vectors Y: $P(Y|X) = \\prod_{i=1}^n P(y^{(i)}|x^{(i)})$ where $P(y^{(i)}|x^{(i)})$ is the probability that the label is assigned to those features taken as the softmax of the highest output.\n",
    "\n",
    "* Taking the log:\n",
    "\n",
    "$$ -log P (Y|X) = \\sum_i^n -log P(y^{(i)}|x^{(i)}) = \\sum_i^n -log \\text{ argmax}_j \\hat{y_j} = \\sum_i^n -log \\text{ argmax}_j \\frac{exp(o_i)}{\\sum_j exp(o_j)} $$\n",
    "$$= \\sum_i^nl(y^{(i)}|x^{(i)}) $$ \n",
    "\n",
    "$$l(y, \\hat{y}) = -\\sum_{j=1}^q y_jlog\\hat{y_j} \\textit{ <---- cross entropy loss.}$$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21dbe484",
   "metadata": {},
   "source": [
    "#### Gradient of the Loss Function\n",
    "\n",
    "$$ \\partial_{o_j}l(y, \\hat{y}) = -\\sum_{j=1}^q \\partial_{o_j} y_jlog\\hat{y_j}= -\\sum_{j=1}^q \\partial_{o_j} y_jlog \\frac{exp(o_i)}{\\sum_j exp(o_j)} $$ \n",
    "\n",
    "\n",
    "$$ -\\sum_{j=1}^q \\partial_{o_j} y_j\\log exp(o_i) - \\partial_{o_j}\\log{\\sum_j exp(o_j)} $$ \n",
    "\n",
    "\n",
    "$$ -\\sum_{j=1}^q \\partial_{o_j} y_j o_j - \\frac{\\partial_{o_j}\\sum_j exp(o_j)}{\\log{\\sum_j exp(o_j)}} $$ \n",
    "\n",
    "\n",
    "$$ -\\sum_{j=1}^q y_j - \\frac{exp(o_j)}{\\log{\\sum_j exp(o_j)}} = \\textbf{softmax}(o_j) - y_j$$ \n",
    "\n",
    "This demonstrates that much like the regression MSE loss the gradient here calculates the deviation between the predicted probability that an example belongs to a certain class and 1 which is the value at that one-hot position. Thus the cross entropy loss (whose name we go into below) simultaneously seeks to push the correct class to 1 but also push the incorrect classes to zero."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cefa8d23",
   "metadata": {},
   "source": [
    "### 4.1.3 Information Theory 101"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e7070a8",
   "metadata": {},
   "source": [
    "#### Entropy\n",
    "\n",
    "Any distribution P has an associated entropy defined as: $ H[P] = \\sum_j -P(j)logP(j)$.\n",
    "\n",
    "#### Surprisal\n",
    "\n",
    "Claude Shannon defined surprisal mathematically as: $ \\log \\frac{1}{P(j)} = -\\log P(j)$ where surprisal is the surprise at observing even j having assigned it a prob P(j). So the above entropy is the expectation over all the surprisals for an event space J. \n",
    "\n",
    "#### Cross Entropy\n",
    "\n",
    "Cross entropy is the expected surprisal between data generating process P and subjective probabilities (assigned probabilities) Q.\n",
    "\n",
    "$$ H(P,Q) = \\sum_j -P(j)logQ(j) $$\n",
    "\n",
    "The lowest possible cross-entropy occurs at the highest entropy which is where the two values are equal so in this case where P=Q. \n",
    "\n",
    "Our log-likelihood loss function thus maximizes the likelihood of the observed data, but also minimizes the surprisal of our labels given the observations."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "57084667",
   "metadata": {},
   "source": [
    "## 4.5 Concise Implementation of Softmax Regression"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "634c2283",
   "metadata": {},
   "source": [
    "### Overflow and Underflow in Exponentiation\n",
    "\n",
    "With the softmax any number for the output $o_j$ is over than 10^38 is overflow so a simple trick to avoid this is subtracting the maximum of all the oututs across dimensions to push all the values within the overflow and underflow limits."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2d00c711",
   "metadata": {},
   "source": [
    "## 4.6 Generalization in Classification\n",
    "\n",
    "Generalization to an arbitrary error of $\\epsilon$, also called the generalization gap, can be guaranteed a-priori using statistical methods given a required number of samples n. Usually this number is order of magnitudes higher than the actual size of the dataset and yet deep learning models are able to generalize effectively anyways."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2f99e3f6",
   "metadata": {},
   "source": [
    "### 4.6.1 Test Set\n",
    "\n",
    "Empirical Error is the error on the test set which is defined for classification problems as:\n",
    "\n",
    "$$ \\epsilon_D(f) = \\frac{1}{n}\\sum_{i \\in Data}\\mathbb{1}(f(\\mathbf{x}^{(i)}) \\neq y^{(i)})$$\n",
    "\n",
    "This is again constranted to the population error which is the expected error rate of some data generating function P(X,Y):\n",
    "\n",
    "$$ \\epsilon (f) = E_{(x,y)~P}\\mathbb{1}(f\\mathbf(x)\\neq y) = \\int\\int\\mathbb{1}(f(\\mathbf{x})\\neq y)p(\\mathbf{x}, y)d\\mathbf{x}y$$\n",
    "\n",
    "\n",
    "Our estimator based on the test data is thus an unbiased estimator of the mean that converges towards the true value at $\\mathbb{O}(\\frac{1}{\\sqrt{n}})$\n",
    "\n",
    "We can also use the Hoeffding inequality to derive the bounds for a finite data sample:\n",
    "\n",
    "$$ \\textbf{Hoeffding: } P(\\epsilon_D(f) - \\epsilon(f) \\geq t) < \\exp(-2nt^2)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7960ecba",
   "metadata": {},
   "source": [
    "### 4.6.2 Test Set Reuse\n",
    "\n",
    "The act of evaluating multiple predictors on the same evaluation set is an egregious act of multiple hypothesis testing and can lead to false discovery. This is because the test dataset was constructed by careful consideration of the precision of empirical error for a single classifier.\n",
    "\n",
    "Adaptive overfitting is a similar issue where information about the test set and performance on a particular model architecture influences design choices\n",
    "\n",
    "In benchmarks it is important to have multiple test sets that after use are aggregated into validation set."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f89e9f3d",
   "metadata": {},
   "source": [
    "### 4.6.3 Statistical Learning Theory\n",
    "\n",
    "Pessimistic View of Empirical Error:\n",
    "\n",
    "$$P(R[p,f] - R_{emp}[X, Y. f] < \\alpha) \\geq 1- \\delta \\text{ for } \\alpha \\geq c\\sqrt{(VC-\\log \\delta)/n}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9abe392e",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "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.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}