Learning From Data_A Short Course Notes.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/javascript": [
       "MathJax.Hub.Config({\n",
       "    TeX: { equationNumbers: { autoNumber: \"AMS\" } }\n",
       "});\n"
      ],
      "text/plain": [
       "<IPython.core.display.Javascript object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%javascript\n",
    "MathJax.Hub.Config({\n",
    "    TeX: { equationNumbers: { autoNumber: \"AMS\" } }\n",
    "});"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Questions\n",
    "1. What is learning from data? Give an example.\n",
    "1. What is Hoeffding Inequality?\n",
    "1. What is perceptron learning algorithm? \n",
    "1. How can we connect the bin example with the learning problem?\n",
    "  * For the case where there's only one hypothesis function\n",
    "  * For the case there are finite many hypothesis functions: can you prove the uniform Hoeffding inequality?\n",
    "  * What does the comparison tell us?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 1 The Learning Problem\n",
    "\n",
    "Learning from data is used in situations where we don't have an analytic solution, but we do have data that we can use to construct an empirical solution.\n",
    "\n",
    "## 1.1 Problem Setup\n",
    "Consider the problem of predicting how a movie viewer would rate the various movies out there. The power of learning from data is that we don't need to analyze movie content or viewer taste. The learning algorithm 'reverse-engineers' the factors (which can impact rating) based solely on previous ratings.\n",
    "\n",
    "### 1.1.2 A Simple Learning Model\n",
    "\n",
    "#### Learning Model\n",
    "The hypothesis set $\\mathcal{H}$ and learning algorithm are referred to informally as the **learning model**.\n",
    "\n",
    "#### The Perceptron Classifier\n",
    "* The output space: $\\mathcal{Y}=\\{+1,-1\\}$\n",
    "* The Hypothesis space $\\mathcal{H}$ is called the perceptron if the functions are of the form $h(x) = sign\\left(\\left(\\sum^{d}_{i=1}w_ix_i\\right)+b\\right)$ or $sign(w^Tx)$ if we merge $b$ into $w$\n",
    "* **The perceptron learning algorithm (PLA)**\n",
    "  * Update rule: at each iteration $t$, for each misclassified point $\\left(x(t),y(t)\\right)$, update $w(t+1) = w(t) + y(t)x(t)$\n",
    "  * The update rule moves in the direction of classifying $x(t)$ correctly.\n",
    "* If the data set if **linearly separable**, it is guaranteed that **PLA** will find some parameters $w$ that classifies all the training examples correctly.\n",
    "\n",
    "### 1.1.3 Learning versus Design\n",
    "\n",
    "* Learning process constructs a model based on data\n",
    "* Deisgn process constructs analytically a physical model based on specifications and does not use data\n",
    "\n",
    "## 1.2 Types of Learning\n",
    "### 1.2.1 Supervised Learning\n",
    "\n",
    "The form of training examples: (input, correct output)\n",
    "\n",
    "#### Variations\n",
    "* Active Learning: The data set is acquired through queries that we make. Thus, we get to choose a point $x$ in the input space, and the supervisor reports to us the target value for $x$. \n",
    "\n",
    "* Online Learning: The data set is given to the algorithm one example at a time.\n",
    "\n",
    "### 1.2.2 Reinforcement Learning\n",
    "\n",
    "* The training sample does not contain the target output, but instead contains some possible output together with a measure of how good that output is. Importantly, the example does not say how good other outputs would have been for this particular input. \n",
    "\n",
    "* The form of training examples: (input, some output, grade for this output)\n",
    "\n",
    "### 1.2.3 Unsupervised Learning\n",
    "* The form of traing examples: (input)\n",
    "* Unsupervised learning can be viewed as the task of spontaneously finding patterns and structure in input data.\n",
    "* Unsupervised learning can also be viewed as a way to create a higher level representation of the data. \n",
    "\n",
    "### 1.2.4 Other Views of Learning\n",
    "* Machine Learning\n",
    "* Statistical Learning: It uses a set of observations to uncover an underlying process. The process is a probability distribution and the observations are samples from that distribution. It focuses on somewhat idealized models and analyzes them in great detail. \n",
    "* Data Mining: It's a practical field that focuses on finding patterns, correlations or anomalies in large relational databases. It emphasizes on data analysis than on prediction. \n",
    "\n",
    "## 1.3 Is Learning Feasible?\n",
    "\n",
    "How could a limited data set reveal enough information to pin down the entire target function? \n",
    "\n",
    "### 1.3.1 Outside the Data Set\n",
    "\n",
    "* Does the data set $\\mathcal{D}$ tell us anything outside of $\\mathcal{D}$ that we didn't know before?\n",
    "  * If the answer is yes, then we have learned something. \n",
    "  * If the answer is no, we can conclude that learning is not feasible.\n",
    "* Since the target function $f$ is an unknown function, we can prove that $f$ remains unknown outside of $\\mathcal{D}$.  \n",
    "* Dilemma:\n",
    "  * As long as the target function $f$ is an unknown function, knowing the data set $\\mathcal{D}$ cannot exclude any pattern of values for $f$ outside of $\\mathcal{D}$. Therefore, the predictions (of the final hypothesis $g$) outside of $\\mathcal{D}$ are meaningless.\n",
    "\n",
    "### 1.3.2 Probability to the Rescue\n",
    "\n",
    "#### Hoeffding Inequality\n",
    "\n",
    "For our learning problem, consider the target function $f$ and a fixed hypothesis function $h$. For each point $x_i$ in input space, let $Z$ be a random variable and $Z=0$ if $h(x) = f(x)$ and $Z=1$ if $h(x) \\ne f(x)$. \n",
    "\n",
    "$Z$ is thus bounded between $[0,1]$. The expectation of $Z$ is $E[Z] = P\\left(h(x)\\ne f(x)\\right)$. \n",
    "\n",
    "Let $e_{out}(h)=P\\left(h(x)\\ne f(x)\\right)$ be the error rate in whole input space, and $e_{in}(h) =$(fraction of $\\mathcal{D}$ where $f$ and $h$ disagree)=$\\frac{1}{N}\\sum^{N}_{n=1}h(x_n)\\ne f(x_n)$.\n",
    "\n",
    "If we sample $N$ points from the input space, i.e. $x_1, x_2, \\dots, x_N$, according to Hoeffding inequality, and because $b-a = 1$, we have for $\\epsilon \\gt 0$, \n",
    "\n",
    "\\begin{align}\n",
    "P\\left(\\frac{1}{N}\\sum^{N}_{i=1}(Z_i - E[Z_i])\\ge \\epsilon\\right) &\\le exp\\left(-\\frac{2N\\epsilon^2}{(b-a)^2}\\right)\\\\\n",
    "P\\left(e_{in}(h) - e_{out}(h)\\ge \\epsilon\\right) &\\le e^{-2N\\epsilon^2}\\\\\n",
    "\\text{and}\\\\\n",
    "P\\left(\\frac{1}{n}\\sum^{n}_{i=1}Z_i - E[Z_i])\\le -\\epsilon\\right) &\\le exp\\left(-\\frac{2N\\epsilon^2}{(b-a)^2}\\right)\\\\\n",
    "P\\left(e_{in}(h) - e_{out}(h)\\le -\\epsilon\\right) &\\le e^{-2N\\epsilon^2}\\\\\n",
    "\\end{align}\n",
    "\n",
    "Combine the two sides inequalities, we have\n",
    "\n",
    "\\begin{align}\n",
    "P\\left[|e_{in}(h) - e_{out}(h)| \\gt \\epsilon \\right] \\le 2 e^{-2N\\epsilon^2}\\;\\;\\;\\text{for any}\\;\\epsilon \\gt 0\n",
    "\\end{align}\n",
    "\n",
    "\n",
    "* The only quantity that is random is $e_{in}(h)$ which depends on the random sample.\n",
    "* The inequality says that as the sample size $N$ grows, it becomes exponentially unlikely that $e_{in}(h)$ will deviate from $e_{out}(h)$ by more than our 'tolerance' $\\epsilon$.\n",
    "* Note the bound does not depend on $e_{out}(h)$, it only depends on the sample size $N$.\n",
    "* This assumes that the samples $x_1,x_2,\\dots,x_N$ are randomly selected.\n",
    "\n",
    "#### Uniform version of Hoeffding Inequality\n",
    "\n",
    "When there's only one hypothesis function in the hypothesis space $\\mathcal{H}$, the hypothesis $h$ is fixed before you generate the data set, and the probability is with respect to random data sets $\\mathcal{D}$ in the above inequality.\n",
    "\n",
    "However, if there are $M$ hypothesis functions in the hypothesis space $\\mathcal{H}$, the learning algorithm has to pick the final hypothesis function $g$ based on the data $\\mathcal{D}$, i.e. after generating the data set. So we can't fix the $g$ ahead of time before generating the data, so we can't just plug in $g$ for $h$ in the above Hoeffding inequality. \n",
    "\n",
    "We need bound the probability $P\\left[|e_{in}(g) - e_{out}(g)| \\gt \\epsilon \\right]$ in a way that doesn't depend on which $g$ the learning algorithm picks. This can be achieved by the union bound, we have:\n",
    "\n",
    "\\begin{align}\n",
    "P\\left[|e_{in}(g) - e_{out}(g)| \\gt \\epsilon \\right] \\le 2 M e^{-2\\epsilon^2N}\\;\\;\\;\\text{for any}\\;\\epsilon \\gt 0\n",
    "\\end{align}\n",
    "\n",
    "\n",
    "This is called the 'uniform' version of the previous Hoeffding inequality. We are trying to simultaneously approximate all $e_{out}(h_m)$'s by the corresponding $e_{in}(h_m)$'s. \n",
    "\n",
    "### 1.3.3 Feasibility of Learning\n",
    "1. A probabilistic view gives us a positive answer that $\\mathcal{D}$ tells us something likely about the target function $f$ outside of $\\mathcal{D}$. The only assumption we make is that the examples in $\\mathcal{D}$ are generated independently. \n",
    "1. The feasibility of learning is thus split into two questions:\n",
    "  * Can we make sure that $e_{out}(g)$ is close enough to $e_{in}(g)$?\n",
    "    * The Hoeffding inequality addresses this question only.\n",
    "  * Can we make $e_{in}(g)$ small enough?\n",
    "    * Note there are cases where we won't insist that $e_{in}(g)\\approx 0$. For example, financial forecasting is impossible to have error near zero. All we hope for is a forecast that gets it right more often than not.\n",
    "    \n",
    "#### The complexity of $\\mathcal{H}$\n",
    "* The number of hypothesis functions $M$ can be thought of as a 'complexity' measure of the hypothesis set $\\mathcal{H}$.\n",
    "* If $M$ goes up, then $e_{in}(g)$ will be a poor estimator of $e_{out}(g)$ according to the inequality (hence helps question 1), however there'll be a better chance to get small $e_{in}(g)$ (hence hurts question 2).\n",
    "\n",
    "#### The complexity of the target function $f$\n",
    "* The complexity of $f$ doesn't affect how well  $e_{in}(g)$ approximates  $e_{out}(g)$\n",
    "* However, we'll get a worse  $e_{in}(g)$ when $f$ is complex.\n",
    "\n",
    "* As long as we make sure that the complexity of $\\mathcal{H}$ gives us a good Hoeffding bound, our success or failure in learning $f$ can be determined by our success or failure in fitting the training data.\n",
    "\n",
    "    \n",
    "\n",
    "## 1.4 Error and Noise\n",
    "\n",
    "### 1.4.1 Error Measures\n",
    "\n",
    "* We use **error measure** (also called an **error function**, and sometimes the error is referred to as **cost**, **objective**, or **risk**) to quantify how well the final hypothesis $g$ approximates the target function $f$.\n",
    "\n",
    "* An error measure quantifies how well each hypothesis function $h$ in the model approximates the target function $f$.\n",
    "$Error = E(h,f)$.\n",
    "* One may view $E(h,f)$ as the cost of using $h$ when you should use $f$.\n",
    "* The choice of the error measure affects the outcome of learning process.\n",
    "* The choice of the error measure depends on how the system is going to be used, rather than on any inherent criterion that we can independently determine during learning process.\n",
    "\n",
    "### 1.4.2 Noisy Targets\n",
    "\n",
    "* Instead of $y=f(X)$, we take the output $y$ to be a random variable that is affected by, rather than determined by, the input $X$.\n",
    "Formally, we have a target distribution, $P(y|X)$ instead. A data point $(x,y)$ is now generated by the joint distribution $P(X,y) = P(X)P(y|X)$.\n",
    "* One can think of a noise target $y$ as a deterministic target plus added noise. For example, take $f(X)=E[y|X]$, then $y = f(X) + noise$.\n",
    "* $P(y|X)$ is what we are trying to learn, $P(X)$ only quantifies the relative importance of the point $X$ in gauging how well we have learned. \n",
    "\n",
    "* Note, the Hoeffding inequality applies to noise target as well because it applies to an arbitrary, unknown target function. Assume we randomly pick all the $y$'s according to the distribution $P(y|X)$ over the entire input space $\\mathcal{X}$. This realization of $P(y|X)$ is effectively a target function. Therefore the inequality will be valid no matter which particular random realization the 'target function' happens to be.\n",
    "\n",
    "# Chapter 2 Traing versus Testing\n",
    "## 2.1 Theory of Generalization\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\\begin{align}\n",
    "A &= B*C \\\\\n",
    "\\label{eq:vector_ray} \\tag{1}\n",
    "\\end{align}\n",
    "\n",
    "\n",
    "\\begin{align}\n",
    "F &= ma \\\\\n",
    "\\label{eq:newton} \\tag{2}\n",
    "\\end{align}\n",
    "\n",
    "Vector **r** is defined by equation $\\eqref{eq:vector_ray}$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}