{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# _KERNAL DENSITY METHODS_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is an [jupyter](http://jupyter.org) notebook.\n",
    "Lectures about Python, useful both for beginners and experts, can be found at http://scipy-lectures.github.io."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Open the notebook by (1) copying this file into a directory, (2) in that directory typing \n",
    "jupyter-notebook\n",
    "and (3) selecting the notebook.\n",
    "\n",
    "***\n",
    "Written By: **Riddhish Bhalodia**\n",
    "***\n",
    "\n",
    "In this exercise, we will learn about different kernal methods for pattern recognition. Reader should be familiar with basic machine learning, estimation theory, linear algebra and a good command over regression.\n",
    "\n",
    "__Dependencies__: numpy, matplotlib"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Dual Representation\n",
    "\n",
    "_Dual Representation_ is an alternate way of formulating many **linear models** used for regression and classification problems. Here the predictions/ estimates are based on the linear combination of a ___kernal function___ evaluated at the training points. To get to what exactly kernal functions are and how they are formulated we consider the linear regression least squares error\n",
    "\n",
    "$$J(\\textbf{w}) = \\frac{1}{2} \\sum \\limits_{n=1}^N \\{\\textbf{w}^T \\phi(\\textbf{x}_n) - \\textbf{t}_n\\}^2 + \\frac{\\lambda}{2}\\textbf{w}^T\\textbf{w} \\quad \\quad \\quad (1)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By setting the gradient of the error term (1) wrt the vector $\\textbf{w}$ to be zero, we get the solution as linear conbination of the vectors $\\phi (\\textbf{x}_n)$ where the weights are a function of $\\textbf{w}$, as follows.\n",
    "\n",
    "$$\\textbf{w} = -\\frac{1}{\\lambda} \\sum \\limits_{n=1}^N \\{\\textbf{w}^T \\phi(\\textbf{x}_n) - \\textbf{t}_n\\}\\phi (\\textbf{x}_n) = \\pmb{\\phi}^T\\textbf{a} \\quad \\quad \\quad (2)$$\n",
    "\n",
    "The $\\pmb{\\phi}^T$ is called a _Design Matrix_ and it's N'th row is given by $\\phi(\\textbf{x}_n)$. The vector $\\textbf{a} = (a_1, a_2, \\cdots, a_N)^T$ is given by\n",
    "\n",
    "$$a_n = -\\frac{1}{\\lambda} \\{\\textbf{w}^T \\phi(\\textbf{x}_n) - \\textbf{t}_n\\} \\quad \\quad \\quad (3)$$\n",
    "\n",
    "Now, we would like to represent the $J(\\textbf{w})$ in terms of $\\textbf{a}$ and hence we substitue the equation (3) in equation (1). So we get\n",
    "\n",
    "$$J(\\textbf{a}) = \\frac{1}{2}\\pmb{a^T \\phi \\phi^T \\phi \\phi^T a} - \\pmb{a^T \\phi \\phi^T t} + \\frac{1}{2}\\pmb{t^T t} + \\frac{\\lambda}{2}\\pmb{a^T \\phi \\phi^T a} \\quad \\quad \\quad (4)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we define something called a _Gram Matrix_ as \n",
    "\n",
    "$$\\textbf{K} = \\pmb{\\phi \\phi^T} \\quad \\quad \\quad (5)$$\n",
    "\n",
    "Gram martix is a symmetric NxN matrix whose each element is given by\n",
    "\n",
    "$$K_{nm} = \\phi(\\textbf{x}_n)^T\\phi(\\textbf{x}_m) = k(\\textbf{x}_n, \\textbf{x}_m) \\quad \\quad \\quad (6)$$\n",
    "\n",
    "Here, $k(\\textbf{x}_n, \\textbf{x}_m)$ is called the ___kernal function___ which is defined by the inner profuct of feature space, as follows.\n",
    "\n",
    "$$k(\\textbf{x}, \\textbf{x}') = \\phi(\\textbf{x})^T\\phi(\\textbf{x}') \\quad \\quad \\quad (7)$$\n",
    "\n",
    "Hence, we can see that the equation (4) can completely be written in ter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}