chapter-04/4.3-linear-discriminant-analysis.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4.3 Linear Discriminant Analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose $f_k(x)$ is the class-conditional density of X, and let $\\pi_k$ be the prior-probability, with $\\sum \\pi_k = 1$. \n",
    "The Bayes theorem gives us (4.7): \n",
    "\n",
    "$$\n",
    "Pr(G = k, X = x) = \\cfrac{f_k(x)\\pi_k}{\\sum_{l=1}^K f_l(x)\\pi_l}\n",
    "$$\n",
    "\n",
    "Suppose that we model each class density as multivariate Gaussian (4.8):\n",
    "\n",
    "$$\n",
    "f_k(x) = \\cfrac{1}{(2\\pi)^{p/2} |\\Sigma_k|^{1/2}} e^{-\\frac{1}{2}(x-\\mu_k)^T\\Sigma_k^{-1}(x-\\mu_k)}\n",
    "$$\n",
    "\n",
    "Linear discriminant analysis (LDA) arises when $\\Sigma_k = \\Sigma \\text{ }\\forall k$. The log-ration between two classes $k \\text{ and } l$ is (4.9):\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "log \\cfrac{PR(G=k|X=x)}{PR(G=l|X=x)} &= log \\cfrac{f_k(x)}{f_l(x)} + log \\cfrac{\\pi_k}{\\pi_l}\\\\\n",
    "&= log \\cfrac{\\pi_k}{\\pi_l} - \\frac{1}{2}(\\mu_k+\\mu_l)^T\\Sigma^{-1}(\\mu_k - \\mu_l)\n",
    "+ x^T\\Sigma^{-1}(\\mu_k-\\mu_l),\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "an equation is linear in x. \n",
    "\n",
    "From (4.9) we see that the linear discriminant functions (4.10):\n",
    "\n",
    "$$\n",
    "\\delta_k(x) = x^T\\Sigma^{-1}\\mu_k - \\frac{1}{2}\\mu_k^T\\Sigma^{-1}\\mu_k + log \\pi_k\n",
    "$$\n",
    "\n",
    "are an equivalent description of the decision rule, with $G(x) = argmax_k \\delta_k(x)$.\n",
    "\n",
    "In practice we do not know the parameters of the Gaussian distributions, and will need to estimate them using the training data:\n",
    "\n",
    "- $\\hat{\\pi_k} = N_k / N, N_k$ is the number of class-k observations;\n",
    "\n",
    "- $\\hat{\\mu}_k = \\sum_{g_i = k} x_i / N_k$\n",
    "\n",
    "- $\\hat{\\Sigma} = \\sum_{k=1}^K\\sum_{g_i=k} (x_i - \\hat{\\mu}_k)(x_i-\\hat{\\mu}_k)^T / (N - K)$\n",
    "\n",
    "With two classes, the LDA rule classifies to class 2 if (4.11):\n",
    "\n",
    "$$\n",
    "x^T\\hat{\\Sigma}^{-1}(\\hat{\\mu}_2 - \\hat{\\mu}_1) > \n",
    "\\frac{1}{2}\\hat{\\mu}_2^T\\hat{\\Sigma}^{-1}\\hat{\\mu}_2 \n",
    "- \\frac{1}{2}\\hat{\\mu}_1^T\\hat{\\Sigma}^{-1}\\hat{\\mu}_1\n",
    "+ log(N_1/N)\n",
    "- log(N_2/N)\n",
    "$$\n",
    "\n",
    "Suppose we code the targets in the 2-classes as +1 and -1. It is easy to show that the coefficient vector from least squares is proportional to the LDA direction given in (4.11). However unless $N_1 = N_2$ the intercepts are different.\n",
    "(**TODO**: solve exercise 4.11)\n",
    "\n",
    "Since LDA direction via least squares does not use a Gaussian assumption, except the derivation of the intercept or cut-point via (4.11). Thus it makes sense to choose the cut-point that minimizes the training error.\n",
    "\n",
    "With more than two classes, LDA is not the same as linear regression and it avoids the masking problems."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Quadratic discriminant functions**\n",
    "\n",
    "If $\\Sigma_k$ are assumed to be equal, then we get *quadratic discriminant functions (QDA)* (4.12):\n",
    "$$\n",
    "\\delta_k(x)=\\cfrac{1}{2}log|\\Sigma_k| - \\cfrac{1}{2}(x-\\mu_k)^T\\Sigma_k^{-1}(x-\\mu_k)+log \\pi_k\n",
    "$$"
   ]
  }
 ],
 "metadata": {
  "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}