CS229_DiscussionSections.ipynb

{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import sys, os\n",
      "import numpy as np\n",
      "import matplotlib\n",
      "import matplotlib.pyplot as plt \n",
      "import pandas as pd\n",
      "import re\n",
      "import cmath\n",
      "import math\n",
      "import glob\n",
      "import subprocess\n",
      "%matplotlib inline\n",
      "import scipy.stats as stats\n",
      "import pylab as pl\n",
      "from scipy.spatial.distance import pdist, squareform\n",
      "from scipy.cluster.hierarchy import linkage, dendrogram\n",
      "from sklearn import svm, datasets"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Useful links"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "http://en.wikibooks.org/wiki/LaTeX/Mathematics\n",
      "http://en.wikipedia.org/wiki/List_of_mathematical_symbols\n",
      "http://www.dfcd.net/projects/latex/latex.php"
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Linear algebra"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "A system of linear equations in which each term is either a constant or a constant multiplied by a single variable."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "\\begin{equation} 4x_{1} - 5x{2} = -13 \\end{equation}\n",
      "\\begin{equation} 2x_{1} + 3x{2} = 9 \\end{equation}\n",
      "\\begin{equation} x_{1} + x{2} = 0 \\end{equation}"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This set of equations can be re-cast in matrix form, a more compact form:"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "\\begin{equation} \\begin{bmatrix} 4 & -5 \\\\ 2 & 3 \\\\ 1 & 1 \\end{bmatrix}  \\begin{bmatrix} x_{1} \\\\ x_{2}  \\end{bmatrix} = \\begin{bmatrix} -13 \\\\ 9 \\\\ 0 \\end{bmatrix} \\end{equation}\n",
      "\n",
      "$\\textbf{A} \\textbf{x} = \\textbf{B} $"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Matrix multiplication follows that the product coordinate (i,j) is i row of $\\textbf{A}$ and i columns of $\\textbf{x}$."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "\\begin{equation} \\begin{bmatrix} 1 & 2 \\\\ 3 & 4 \\\\ 5 & 6 \\end{bmatrix} \\begin{bmatrix} 1 & 2 \\\\ 3 & 4 \\end{bmatrix} = \\begin{bmatrix} 7 & 10 \\\\ 15 & 22 \\\\ 23 & 34 \\end{bmatrix} \\end{equation}"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Note that the multiplcation of each row by a column is the $\\textbf{inner product}$ (dot product) and gives a real number (for i,j=0: $1 \\times 1 + 2 \\times 3 = 7$).\n",
      "\n",
      "Note that the multiplcation of each column by a row is the $\\textbf{outer product}$ and gives a matrix."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Diagonal matrix has specified values on the diagonal (and all else zeros) and identity matrix has ones on the diagonal and the $\\textbf{trace}$ is the sum of diagonal elements."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "A $\\textbf{norm}$ is the \"length\" of a vector.\n",
      "\n",
      "Euclidian norm is the sum of the square of elements in the vector: $\\sqrt{\\sum x_i^2}$.\n",
      "\n",
      "A similar idea can be applied to matricies: $\\sqrt{\\sum x_{ij}^2}$."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The $\\textbf{Invertible matrix}$, $\\textbf{B}$, produces the identity matrix: $\\textbf{A} \\textbf{B} = \\textbf{I}$ where $B = A^{-1}$. \n",
      "\n",
      "The identitfy matrix  $\\textbf{A} \\textbf{I} = \\textbf{A}$.\n",
      "Though not all matricies have inverses, they can be useful:\n",
      "\n",
      "$Ax=b \\Leftrightarrow A^{-1}Ax =  A^{-1}b \\Leftrightarrow x = A^{-1}b$\n",
      "\n",
      "Thus, $\\textbf{A}$ is $\\textbf{invertible}$ or $\\textbf{non-signular}$ if $ A^{-1} $ exists."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "$\\textbf{Linear independence}$ means that no vector in a set can be written as a linear combination of the remaining.\n",
      "\n",
      "Recall that a linear combination is achieved by multiplying each term by a constant and adding the results.\n",
      "\n",
      "For example, the below set is linearly dependent becase there is a valid linear combination: $x_3$ = -2 $x_1$ + $x_2$:\n",
      "\\begin{equation} x_1 = \\begin{bmatrix} 1 \\\\ 2 \\\\ 3 \\end{bmatrix}  x_2 = \\begin{bmatrix} 4 \\\\ 1 \\\\ 5 \\end{bmatrix}  x_3 = \\begin{bmatrix} 2 \\\\ -3 \\\\ -1 \\end{bmatrix} \\end{equation}\n",
      "\n",
      "$\\textbf{Rank}$ is a related idea, and simply indicates the number of linearly independent columns (column rank) or rows (row rank) of a matrix.\n",
      "\n",
      "$\\textbf{Full rank}$ matricies are invertible."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "$\\textbf{Orthogonality}$ means that the dot product of two orthogonal vectors is zero. \n",
      "\n",
      "\\begin{equation} x = \\begin{bmatrix} 1 & 1\\end{bmatrix} \\end{equation}\n",
      "\n",
      "\\begin{equation} x^{T} = \\begin{bmatrix} 1 \\\\ 1 \\end{bmatrix} \\end{equation}\n",
      "\n",
      "\\begin{equation} y = \\begin{bmatrix} -1 & -1 \\end{bmatrix} \\end{equation}\n",
      "\n",
      "x and y are orthogonal because $\\begin{equation} x^{T} y = 0 \\end{equation}$."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The $\\textbf{span}$ is the set of vectors that can be expressed as a linear combination of a given set."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The $\\textbf{determinant}$ is used to see whether a matrix is invertiable.\n",
      "\n",
      "For a given matrix, there is a set of points $\\textbf{S}$ formed by taking all possible linear combinations of the row vectors with combination coefficients between 0 and 1. \n",
      "\n",
      "Given a matrix:\n",
      "\n",
      "\\begin{equation} A= \\begin{bmatrix} 1 & 3 \\\\ 3 & 2 \\end{bmatrix} \\end{equation}\n",
      "\n",
      "The rows are:\n",
      "\n",
      "\\begin{equation} a_1= \\begin{bmatrix} 1 & 3 \\end{bmatrix}  \\end{equation}\n",
      "\n",
      "\\begin{equation} a_2= \\begin{bmatrix} 3 & 2 \\end{bmatrix}  \\end{equation}\n",
      "\n",
      "The linear combination is: \n",
      "\n",
      "\\begin{equation} c = \\alpha \\times a_1 + \\beta \\times a_2 \\end{equation}\n",
      "\n",
      "The edge case for $ \\alpha = \\beta = 1 $ is:\n",
      "\n",
      "\\begin{bmatrix} 4 & 5 \\end{bmatrix}\n",
      "\n",
      "By setting the coefficients to zero and exploring other edge cases, $S$ forms a parallelogram. \n",
      "\n",
      "The $\\textbf{determinant}$ is the area of the parallelogram: 7."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "$\\lambda$ is an $\\textbf{eigenvalue}$ of square matrix $A$ and x is the $\\textbf{eigenvector}$ if:\n",
      "\n",
      "$ Ax = \\lambda x $\n",
      "\n",
      "This simply means that multiplying a matrix $A$ by its eigenvector, $x$, results a new vector that points in the direction of $x$ but is scaled by $\\lambda$."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The $\\textbf{gradient}$ of $f(A)$ is defined below, and is always the same size as A and requires that $f(A)$ returns a scalar:\n",
      "\n",
      "\\begin{equation} (\\nabla_A f(A))_{ij} = \\frac{\\partial(A)}{\\partial(A_{ij})} \\end{equation}"
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Probability "
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Sample space $= \\Omega =$ Set of all possible outcomes.\n",
      "\n",
      "Event space - Sub-set of $\\Omega$ that we care about. \n",
      "\n",
      "Probability measure - Maps an outcome into a real number with contraints:\n",
      "\n",
      "$P(A) > 0$\n",
      "\n",
      "$P(\\Omega) = 1$\n",
      "\n",
      "A $\\textbf{random variable}$ can be discrete or continuous."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The $\\textbf{probability mass funtion}$: is the probability that the random variable is a specific value, $P(x=k)$. \n",
      "\n",
      "This works for discrete random variables, but does for a continuous random variable. \n",
      "\n",
      "The $\\textbf{cumulative distribution funtion}$ is the probability from negative $\\infty$ to a given value, and can be computed for discrete or continuous random variables, $P(x<k)$.\n",
      "\n",
      "$$ CDF = F_{X}(x) = P(x < X) $$\n",
      "\n",
      "The $\\textbf{probability density funtion}$ is the derivative of the CDF.\n",
      "\n",
      "$$ f_{X}(x) = \\frac{dF_{X}(x)}{dx} $$ \n",
      "\n",
      "$$ \\int_{-\\infty}^{\\infty} f_{X}(x) dx = 1 $$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "$\\textbf{Expectation}$ of a function $g(x)$ is the weighted sum of all values that $x$ can take on.\n",
      "\n",
      "$$ E[g(x)] = \\sum_{x \\in Va(x)} g(x) p(x) $$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "$\\textbf{Variance}$ of a distribution is the expected devation of a random variable from its mean.\n",
      "\n",
      "$$ Var[X] = E((X-E(x))^2) = E[x^2] - E[x]^2 $$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "$\\textbf{Probability mass funtion}$ for various distribution types. The distribution of a discrete random variable can be characterized through its probability mass function (pmf). The probability that a given number will be the realization of a discrete random variable is equal to the value taken by its pmf in correspondence of that number. \n",
      "\n",
      "$\\textbf{Bernoulli}$ random variable means that event succeeds with probability $p$ and fails with $1-p$.\n",
      "\n",
      "$\\textbf{Binomial}$ Considering a random variable, n, compute the probability of observing n successes for N trials given a probability P for each without regard for order. If N=5, p=0.5, n=2, then the first success can occour in any of the 5 trials. The second success can occour in any of the remaining 4 trials, giving 5 $\\times$ 4 permutations. But, we don't care about the order so 5 $\\times$ 4 / n! = 10 combinations of 2 successes. The number of combinations that satisfy the condition, n, is generally given by the binomial coefficient in the below probability mass function. This states: (1) there are N choose n combinations with (2) the probability of each combination $p^n (1-p)^{N-n}$ (n successes, N-n failures)\n",
      "\n",
      "$$ P(n) = {N \\choose n} p^n (1-p)^{N-n} $$\n",
      "\n",
      "$\\textbf{Geometric}$ models the number of failures prior to a success.\n",
      "\n",
      "$$ P(n) = (1-p)^{n-1}p $$\n",
      "\n",
      "$\\textbf{Poisson}$ Assuming an expected value of a Binomial random variable, $\\lambda$, let's assume $\\lambda$ is a measured value such as the number of cars observed per hour. If we let N=60 (one trial per minute over the course of the hour), then we can compute the probability of success per trail, p=$\\frac{\\lambda}{60}$. If we want to compute the number of cars, n, obsered per minute then we again use the binomial where the probability of observing a car per minute is $\\frac{\\lambda}{60}$: \n",
      "\n",
      "$$ P(n=k) = {60 \\choose k} \\frac{\\lambda}{60}^k (1-\\frac{\\lambda}{60})^{60-k} $$\n",
      "\n",
      "However, we can have > 1 car per minute. We can get more granular. So, let's assume the number of trials is large (e.g., sample at >> second frequency) and the probability of success at each is correspondingly smaller. As N approaches infinity, Binomal becomes the Poisson distribution:\n",
      "\n",
      "$$ \\lambda = Np $$ \n",
      "$$ P(X=k) = \\lim _{N \\to \\infty} {N \\choose k} \\frac{\\lambda}{N}^k (1-\\frac{\\lambda}{N})^{N-k} = \\frac{\\lambda^k}{k!} e^{-\\lambda} $$\n",
      "\n",
      "$\\textbf{Exponential}$ A specific condition for Poisson is that (1) the time (distance) between successes (reads) is exponentially distributed with rate parameter $\\lambda$ and (2) each trial (read) is independent. The probability of observing an event over an interval (of time, or in the case of sequencing, distance) is proportional to the length of that interval with $\\lambda$ the constant of proportionality. The probability density funtion is, and it decays in proportion to the value of $\\lambda$ and x, the length of the interval.\n",
      "\n",
      "$$ P(x) = \\lambda e^{-\\lambda x} $$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "$\\textbf{Bayes Rule}$ Frequentist probability relies on the long-run frequency of events (e.g., the probability of plane accidents under a frequentist philosophy is interpreted as the long-term frequency of plane accidents). Bayesian probability assigns a belief, or prior probability, to an unlabeled point $P(H)$. Thus, we have to state our prior probability that a point has a specific label.\n",
      "We also must state the probabilty of observing the data point $P(D)$ and the probability of observing the point if the hypothesis is true is $P(D|H)$. From this we can estimate the probability that the point is labeled given the data $P(H|D)$, the posterial probability. We use the chain rule to de-compose D into its features.\n",
      "\n",
      "$$ P(H|D) = \\frac{P(D|H)P(H)}{P(D)} $$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "$\\textbf{Covariance}$ is the linear association between two samples and indicates the direction, not the strength, of the relationship.\n",
      "\n",
      "$$ \\sigma_{xy} = \\frac{\\sum (x_i - \\mu_x)(y_i - \\mu_{u})}{N} $$"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}