Linear-Discriminant-Analysis-From-Scratch.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linear Discriminant Analysis\n",
    "\n",
    "\n",
    "\n",
    "* Assume that we have a set of vectors $\\mathbf x^{(i)}$ and for each vector we have a label $y_i$ which is either 0 or 1.\n",
    "\n",
    "Means and variances for each class\n",
    "\n",
    "for $y = 0$\n",
    "\n",
    "$$\n",
    "\\mathbf \\mu_0 = \\frac{1}{n_0} \\sum_{i \\in C_0} \\mathbf x^{(i)}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\Sigma_0 =  \\frac{1}{n_0-1} \\sum_{i \\in C_0} (\\mathbf x^{(i)} - \\mathbf \\mu_0)^T (\\mathbf x^{(i)} - \\mathbf \\mu_0)\n",
    "$$\n",
    "\n",
    "and for  $y = 1$\n",
    "\n",
    "$$\n",
    "\\mathbf \\mu_1 = \\frac{1}{n_1} \\sum_{i \\in C_1} \\mathbf x^{(i)}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\Sigma_1 =  \\frac{1}{n_1-1} \\sum_{i \\in C_1} (\\mathbf x^{(i)} - \\mathbf \\mu_1)^T (\\mathbf x^{(i)} - \\mathbf \\mu_1)\n",
    "$$\n",
    "\n",
    "\n",
    "\n",
    "$$\n",
    "\\mathbf w = \\mathrm{argmax}_w \\frac{ (\\mathbf \\mu_0^T \\mathbf w - \\mathbf \\mu_1^T \\mathbf w)^2 } \n",
    "{n_0 \\mathbf w^T \\mathbf \\Sigma_0  \\mathbf w + n_1 \\mathbf w^T \\mathbf \\Sigma_1  \\mathbf w}\n",
    "$$\n",
    "\n",
    "$$\n",
    "= \\frac{ ((\\mathbf \\mu_O  - \\mathbf \\mu_1)^T \\mathbf w)^2 } \n",
    "{\\mathbf w^T (n_0  \\mathbf \\Sigma_0  + n_1  \\mathbf \\Sigma_1)  \\mathbf w}\n",
    "$$\n",
    "\n",
    "$$\n",
    "= \\frac{ (\\mathbf m^T \\mathbf w)^2 } \n",
    "{\\mathbf w^T \\mathbf S  \\mathbf w}\n",
    "$$\n",
    "\n",
    "$\\mathbf S = (n_0  \\mathbf \\Sigma_0  + n_1  \\mathbf \\Sigma_1) $ and $\\mathbf m = \\mathbf \\mu_O  - \\mathbf \\mu_1$.\n",
    "Just as $\\Sigma_0$  and $\\mathbf \\Sigma_1$, $\\mathbf S$ is a symetric positive defined matrix.\n",
    "\n",
    "$$\n",
    "= \\frac{ (\\mathbf m^T \\mathbf w)^2 } \n",
    "{\\mathbf w^T \\mathbf R^T \\mathbf R  \\mathbf w}\n",
    "$$\n",
    "\n",
    "where $\\mathbf S = \\mathbf R^T \\mathbf R$ (square root decomposition)\n",
    "\n",
    "\n",
    "$$\n",
    "= \\frac{ (\\mathbf m^T \\mathbf R^{-1} \\mathbf v)^2 } \n",
    "{\\mathbf v^T {\\mathbf R^T}^{-1} \\mathbf R^T \\mathbf R  \\mathbf R^{-1} \\mathbf v}\n",
    "$$\n",
    "\n",
    "where $\\mathbf v = \\mathbf R \\mathbf w$ (transformed vector)\n",
    "\n",
    "$$\n",
    "= \\frac{ (\\mathbf m^T \\mathbf R^{-1} \\mathbf v)^2 } \n",
    "{\\mathbf v^T  \\mathbf v}\n",
    "$$\n",
    "\n",
    "$\\mathbf v^T  \\mathbf v = \\| \\mathbf v \\|^2$\n",
    "\n",
    "$$\n",
    "= \\left( \\frac{ \\mathbf m^T \\mathbf R^{-1} \\mathbf v} \n",
    "{\\| \\mathbf v \\|} \\right)^2\n",
    "= \n",
    "\\left( \\frac{ ({\\mathbf R^{-1}}^T \\mathbf m)^T  \\mathbf v} \n",
    "{\\| \\mathbf v \\|} \\right)^2\n",
    "$$\n",
    "\n",
    "The function to maximize could be rewritten as the project between two vectors. The projection is maximum if they are a multiple of each other."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\mathbf v = a \\; {\\mathbf R^{-1}}^T \\mathbf m = a; {\\mathbf R^{-1}}^T (\\mathbf \\mu_0 - \\mathbf \\mu_1)\n",
    "$$\n",
    "\n",
    "where $a$ is a arbitrary scalar.\n",
    "\n",
    "$$\n",
    "\\mathbf w = \\mathbf R^{-1} \\mathbf v =  a \\; \\mathbf R^{-1}  {\\mathbf R^{-1}}^T (\\mathbf \\mu_0 - \\mathbf \\mu_1) = a \\; \\mathbf S^{-1} (\\mathbf \\mu_0 - \\mathbf \\mu_1)\n",
    "$$\n",
    "\n",
    "$$ \n",
    "\\mathbf w = (n_0  \\mathbf \\Sigma_0  + n_1  \\mathbf \\Sigma_1)^{-1} (\\mathbf \\mu_0 - \\mathbf \\mu_1)\n",
    "$$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.6.0",
   "language": "julia",
   "name": "julia-1.6"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.0.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}