Solutions to Chapter 5 Three Learning Principles.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise 5.1\n",
    "\n",
    "* (a) For $\\mathcal{X}=\\{-1, +1\\}^{10}$, there are $2^{10}$ possible input points in total. Given the number of input points $N$, there are $N \\choose 1$ ways to select one of the input points to evaluate to $+1$, and the rest of the input points to evaluate to $-1$. So there are total $2^{10}$ hypothesis functions in $\\mathcal{H}_1$. Similarly there are ${2^{10} \\choose 100}$ hypothesis functions in $\\mathcal{H}_{10}$.\n",
    "\n",
    "\n",
    "* (b) For $\\mathcal{H}_{1}$, we can use 10 bits to represent the single input point where the function evaluates to 1.\n",
    "\n",
    "* (c) For $\\mathcal{H}_{10}$ we can use $10*100$ bits to represent the 100 input points where the function evaluates to 1.\n",
    "\n",
    "\n",
    "\n",
    "#### Exercise 5.2\n",
    "* (a) There are $2^5$ possible predictions of win-lose for 5 games.\n",
    "* (b) If the sender wants to make sure that at least one person receives correct predictions on all 5 games from him, he should begin with $2^5$ people.\n",
    "* (c) After the first letter 'predicting' the outcome of the first game, he only need target $2^4$ of the original recipients.\n",
    "* (d) There are total $2^5+2^4+\\dots+2^1 = 63$ letters been sent.\n",
    "* (e) He will make $50 - 63*0.50 = 18.5$ dollars.\n",
    "* (f) This is similar to the growth function that if our hypothesis set is large enough, it can possiblely contain all the possible dichotomies for the training data set, and if we are lucky, the training algorithm may find a hypothesis function that can predict correctly for each of the training data (this hypothesis is the guy who receives correct predictions for each of 5 games). This doesn't mean that our model can predict new data very well. So the credibility of fitting the data is not convinciable. \n",
    "\n",
    "#### Exercise 5.3\n",
    "\n",
    "The sampling bias might be caused by the size of the holes on the net. The fish that are smaller than the holes are not in the samples.\n",
    "\n",
    "#### Exercise 5.4\n",
    "\n",
    "* (a) It's not correct to use the perceptron's VC dimension for the generalization error. Because one has looked the data before selecting the perceptron model, so the actual hypothesis set is much larger than perceptron model.\n",
    "\n",
    "* (b) We don't know the $d_{VC}$ for the learning model that we actually used. As stated in problem (a), we started from a pretty big hypothesis which might include all models we are aware of. The $d_{VC}$ is not known for such a hypothesis set.\n",
    "\n",
    "#### Exercise 5.5\n",
    "\n",
    "* (a) The $M=3*500$ in equation (1.6) since each hypothesis is obtained from a size of $500$ hypothesis space, and according to text, they should also be considered.\n",
    "\n",
    "* (b) The level of contamination is much larger if the 100 examples are used in training rather than in the final selection. Because if the 100 examples are used in training, they are reused by every hypothesis in the model (for training) while if they are used to select from final 3 hypotheses, they are only reused 3 times."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 5.1\n",
    "\n",
    "* (a) If $\\mathcal{H}$ shatters $x_1, \\dots,x_N$, then for any given $f$, there exists a $h$ that can generate the same values as $f$ on all the points of $x$. So the proposition is not falsifiable.\n",
    "\n",
    "* (b) For a given hypothesis set $\\mathcal{H}$ and given $N$ data points, there are $m_{\\mathcal{H}}(N)$ dichotomies that can be generated by the hypothesis functions in $\\mathcal{H}$. Each dichotomy corresponds to a $h$ in the hypothesis set that maps the $x$ into different values. \n",
    "Since $f$ is random, on a given $x_i$, the probability for a $h$ to mismatch $f$ is $P[h(x_i)\\ne f(x_i)] = \\frac{1}{2}$. \n",
    "\n",
    "The probability that $h$ matches with $f$ on all points is thus: $P[h(x)=f(x)] = \\left(\\frac{1}{2}\\right)^N$, and the probability that $h$ doesn't match with $f$ for at least one $x_i$ in $x_1, \\dots, x_N$ is: \n",
    "\n",
    "$P[h(x)\\ne f(x)] = 1-\\frac{1}{2^N}$\n",
    "\n",
    "The probability of falsibility is thus the probability that none of the $m_{\\mathcal{H}(N)}$ hypotheses functions can match $f$ perfectly on all $N$ data points. So we have\n",
    "\n",
    "\\begin{align*}\n",
    "P[\\text{falsifibility}] &= \\left(1-\\frac{1}{2^N}\\right)^{m_{\\mathcal{H}}(N)}\\\\\n",
    "&= 1 - m_{\\mathcal{H}}(N)\\frac{1}{2^N} + \\frac{m_{\\mathcal{H}}(N)\\left(m_{\\mathcal{H}}(N)-1\\right)}{2}(-\\frac{1}{2^N})^2\\left(1-\\theta\\frac{1}{2^N}\\right)^{m_{\\mathcal{H}}(N)-2}\\\\\n",
    "&\\ge 1 - \\frac{m_{\\mathcal{H}}(N)}{2^N}\\\\\n",
    "\\end{align*}\n",
    "\n",
    "Where the second step comes from the Taylor expansion of function $(1+x)^m$, with $x = -\\frac{1}{2^N}$ and $m = m_{\\mathcal{H}}(N)$, and the last term in the Taylor expansion is the Lagrange Remainder and $0 \\le \\theta \\le 1$. It's easy to see that the Lagrange Remainder is greater or equal to zero, so we arrived at the final inequality.\n",
    "\n",
    "\n",
    "* (c) If $d_{VC}=10$ and $N=100$, then $m_{\\mathcal{H}}(N) \\le 100^{10}+1$, $P[\\text{falsification}] \\ge 1- \\frac{100^{10}+1}{2^{100}} \\ge 0.9999$. So it's almost certain that the proposition is falsifiable. If we obtain a hypothesis  $f$ with zero $E_{in}$ on the data, it doesn't generalize well to $f$. \n",
    "\n",
    "#### Problem 5.2 \n",
    "\n",
    "* (a) $E_{in}(g_i)$ has to be non-increasing in $i$ because for $p \\lt q$, $g_p \\in \\mathcal{H}_p$ and $g_p \\in \\mathcal{H}_q$ because $\\mathcal{H}_p \\subset \\mathcal{H}_q$. So $E_{in}(g_q) \\le E_{in}(g_p)$, otherwise we can always let $g_q = g_p$ and achieve the same performance as $E_{in}(g_p)$. \n",
    "\n",
    "* (b) For a given $p_i$, the more complex the target function, the lower the probability that hypothesis set $\\mathcal{H}_i$ will approximate $f$ well, so the lower the $p_i$.\n",
    "\n",
    "* (c) We expect that $p_0 \\le p_1 \\le \\dots \\le 1$, since as $i$ increases, the hypothesis set contains all the hypothesis functions in previous hypothesis sets in addition to any new functions. \n",
    "It should have higher probability to achieve the minimum values than its previous sets. \n",
    "\n",
    "* (d) According to VC generalization bound theorem 2.5, we have  $E_{out}(g) \\le E_{in}(g) + \\sqrt{\\frac{8}{N}\\ln \\frac{4m_{\\mathcal{H}}(2N)}{\\delta}}$ with probability of at least $1-\\delta$, thus with at most a probability of $\\delta$, we have $P\\left[|E_{out}(g)-E_{in}(g)| \\gt \\epsilon \\right] \\le \\delta$, where $\\epsilon = \\sqrt{\\frac{8}{N}\\ln \\frac{4m_{\\mathcal{H}}(2N)}{\\delta}}$, solve for $\\delta$ we have $P\\left[|E_{out}(g)-E_{in}(g)| \\gt \\epsilon \\right] \\le 4m_{\\mathcal{H}}(2N)e^{-\\frac{\\epsilon^2N}{8}}$\n",
    "\n",
    "\\begin{align*}\n",
    "P\\left[|E_{in}(g_i) - E_{out}(g_i)| \\gt \\epsilon | g^* = g_i\\right] &= \\frac{P\\left[|E_{in}(g_i) - E_{out}(g_i)| \\gt \\epsilon \\cap  g^* = g_i\\right]}{P(g^* = g_i)}\\\\\n",
    "&= \\frac{P[g^* = g_i| \\;|E_{in}(g_i) - E_{out}(g_i)| \\gt \\epsilon]P\\left[|E_{in}(g_i) - E_{out}(g_i)| \\gt \\epsilon\\right]}{p_i}\\\\\n",
    "&\\le \\frac{P\\left[|E_{in}(g_i) - E_{out}(g_i)| \\gt \\epsilon\\right]}{p_i}\\\\\n",
    "&= \\frac{4m_{\\mathcal{H}_i}(2N)e^{-\\frac{\\epsilon^2N}{8}}}{p_i}\\\\\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 5.3\n",
    "\n",
    "* (a) $M=1$, we only have one hypothesis function.\n",
    "* (b) Hoeffding bound $P[|E_{out}-E_{in}| \\gt 0.02] \\le 2e^{-2\\times0.02^2\\times N} =0.0006709252558050237$ . It says that for a high confidence,the out-of-sample error should be very close to our in-sample error, which is zero.\n",
    "* (c) It's possible that the first $N$ customers all come from same local area, i.e. we may have sample bias. So the model works on such sample but not on all samples.\n",
    "* (d) The bank may apply your function to certain type of customers once it knows the implicit assumption in the function. \n",
    "\n",
    "#### Problem 5.4\n",
    "\n",
    "* (a) \n",
    "  * (i) It's wrong because there's data snooping, the S&P 500 stocks survived the 50 years of market trading, so we underestimate the $M$.\n",
    "  * (ii) A better estimate should use $M=50000$, which gives a probability of $0.045 * 100 = 4.5$, This means nothing for our purpose. \n",
    "* (b) \n",
    "  * (i) We have data snooping here, because we look at the stocks that survived the 50 year trading and get into S&P 500 in current year. Then we use them to test our strategy.\n",
    "  * (ii) The performance of buy and hold trading is over estimate of actual performance.\n",
    "  \n",
    "#### Problem 5.5\n",
    "\n",
    "* (a) I don't expect it to perform at $12\\%$. This is because there is data snooping, the S&P 500 stocks are survivals in the market. \n",
    "* (b) We should test the strategy using all stocks in the market from the beginning of your training period. \n",
    "\n",
    "#### Problem 5.6\n",
    "\n",
    "Interpolation is like training with a given set of data, and extrapolation is like testing the curve with new data. It's highly possible that the known set of data has a very different distribution as the data used in extrapolation. This is similar to the training distribution and testing distribution. This is why the Extrapolation is harder than interpolation."
   ]
  },
  {
   "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
}