{ "metadata": { "name": "" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "heading", "level": 1, "metadata": {}, "source": [ "CSE 546 Review Session" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**October 8: Bias-variance trade-off and L1/L2 regularization comparison**\n", "\n", "In this review section, we'll work through an example to review the bias-variance tradeoff in machine learning. We will later look at some similarities and differences between L1 and L2 regularization." ] }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Bias-Variance Trade-Off" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For this example, assume pairs of data $(x_i, y_i) \\in (\\mathbb{R}, \\mathbb{R})$ are generated from the model $y_i = f^\\ast(x_i) + \\epsilon_i$. Each $\\epsilon_i$ is independently drawn from a Gaussian distribution with mean 0 and standard deviation $\\sigma$. For these examples, we will fix $\\sigma = 0.1$ and $f^*(x) = 3 x^3 - x$, and we assume each $x_i$ is drawn from a uniform distribution between 0 and 1.\n", "\n", "The code below generates a scatter plot of 10 datapoints drawn from this distribution." ] }, { "cell_type": "code", "collapsed": false, "input": [ "import numpy as np\n", "import matplotlib.pyplot as plt\n", "\n", "sigma = 0.1\n", "\n", "def f_star(x):\n", " return 3 * x**3 - x\n", "\n", "def make_data(N):\n", " \"\"\"Generates N pairs of data according to y = f*(x) + epsilon\"\"\"\n", " x = np.random.rand(N)\n", " noise = sigma * np.random.randn(N)\n", " y = f_star(x) + noise\n", " return (x, y)\n", "\n", "# Generate data:\n", "exampleData = make_data(10)\n", "\n", "# Plot f_star:\n", "domainSamples = np.linspace(0, 1)\n", "plt.plot(domainSamples, f_star(domainSamples), 'r')\n", "\n", "# Plot data:\n", "plt.scatter(exampleData[0], exampleData[1])\n", "\n", "# Format/show plot:\n", "plt.xlabel('x')\n", "plt.ylabel('y')\n", "plt.legend(('f*', 'Samples'), loc='upper left')\n", "plt.show()\n" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "display_data", "png": "iVBORw0KGgoAAAANSUhEUgAAAY0AAAEPCAYAAAC+35gCAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XlcVOX+B/DPsKiIiiCJBiiK5gKyqDS4j2mZqJBahuZu\nxTXTqG7X/FVX3FJv3ryu2OqeWlqJkZbbiIq4pLmRXnBlUQwV2UQGeH5/nCuJDDps88wMn/frdV45\ncx7OfM68mvnOc55znqMSQggQEREZwEp2ACIiMh8sGkREZDAWDSIiMhiLBhERGYxFg4iIDMaiQURE\nBpNWNJKSktC7d294eXlBo9Fg1apVpdpotVo4ODjA398f/v7+mD17tvGDEhFRMRtZL2xra4uFCxfC\nz88P6enp8Pb2hlqtRrt27Uq069WrF6KioiSlJCKiB0nraTRp0gR+fn4AAGdnZwQEBCA1NbVUO157\nSERkOkxiTCMxMRFnz55FYGBgiedVKhViY2Ph5eWFoKAgxMfHS0pIRESACRSN7OxshIaGYuHChbC3\nty+xrmPHjkhKSsLvv/+OIUOGIDg4WFJKIiICAJXMuad0Oh0GDhyI/v37Izw8/JFthRBwdnZGQkIC\nnJycSqxr1aoVLly4UJ1RiYgsiqenJxITE8v9d9J6GkIITJgwAV5eXmUWjLS0tOIxjW3btsHOzq5U\nwQCACxcuQAhhlsv06dOlZ2B++TmY3zwXc85f0R/a0s6eOnjwINatWwcfHx/4+/sDAD7++GNcvXoV\nABAWFobNmzcjMjISNjY28PHxwdatW2XFJSIiSCwa3bt3R1FR0SPbTJo0CZMmTTJSIiIiehzpA+E1\nnUajkR2hUphfLuaXy9zzV4TUgfCqolKpYAG7QURkNBX93pR2eMoYnJyccPv2bdkxahRHR0fcunVL\ndgwiqiYW3dNgD8T4+J4TmYeKflY5pkFERAZj0SAiIoOxaBARkcFYNCRJSEjASy+9BEdHRyxdulR2\nHCIig1j02VOmbN68eXBwcMDNmzdhZWWFK1euYNWqVZg+fbrsaEREZWJPQ5KrV69CrVbjyJEj+Pjj\nj1FQUAAA2L9/P+bOnSs5HRGRfuxpSPDMM88gJiYGBw4cgK2tLWbPno2//e1vSE5Ohk6nwwcffCA7\nIhGRXuxpSLBnzx706NEDy5YtQ2ZmJjw8PKBSqQAAVlZWvM6BiExWzS4aKlXVLBUkhMDhw4dx+vRp\nREZGIjQ0FH379sWiRYuqcCeJiKpOzT48JfkXvUqlglqthlqtxpUrVwAAPXv2RM+ePaXmIiIqS83u\naZiQ5s2b88wpIjJ5LBoSceyCiMwNi4ZEqkqMhxARycBZbqlK8T0nMg+c5ZaIiKodiwYRERmMRYOI\niAzGokFERAZj0SAiIoOxaBARkcFYNIiIyGAsGkREZDAWjRosIiICo0aNkh2DiMwIi4YkBw4cQNeu\nXeHg4IBGjRqhe/fuOHbsmFEzcBoTIiovaUUjKSkJvXv3hpeXFzQaDVatWqW33bRp0+Dj44PAwECc\nO3fOKNl0Oh2++uorfPTRP7Ft27Yq335mZiYGDhyIYcOGISkpCSkpKZg+fTpq165d5a/1KJzug4jK\nTUhy7do1ceLECSGEEH/++adwcXER8fHxJdpER0eL/v37CyGEiIuLE2q1Wu+2ytqNsp5PTk4Wixcv\nFkuWLBEpKSkl1hUUFAiNZoCoW7e3AP4p7O3biA8+mFGufXucU6dOiTp16oj8/PxS6xITE0Xv3r1F\no0aNhLOzs3jllVdERkZG8frmzZuL5cuXi8DAQNG4cWPx3nvviezsbPHSSy+JRo0aib59+xa3v3Tp\nklCpVGLjxo2ibdu2omnTpmLBggXF25o+fboYOXJk8eNDhw6JLl26CAcHB+Hr6yu0Wm3xuh9//FFo\nNBrh4OAgWrRoIdavX6933yT+L0VE5VDRz6rJfMIHDhwodu3aVeK5sLAwsXHjxuLHbdq0EdevXy/1\nt+UpGufPnxcNGriIOnXGiTp1xoqGDZuKxMTE4vV79+4V9ep5C0AnlLs0XRe2tnVFdnZ2cZvs7Gzx\n4oujhb29k3BxaSk2bfq23Pvr6ekphg4dKrZt2yZu3bpV/HxiYqLYtWuXyM/PFydPnhQdO3YU4eHh\nxes9PDyEv7+/OHHihDh58qRo0KCBCAgIEFFRUSI1NVWo1WqxZs0aIcRfRWP48OEiNzdXnD59Wjg5\nORW/zw8WjeTkZNGgQQOxcuVKkZmZKVavXi0cHBxEenq6yM/PF82bNxdxcXFCCCGuX78uzp49a/B7\nTkSmp6KfVZMY00hMTMTZs2cRGBhY4vmUlBS4u7sXP3Zzc0NycnKlXmvq1JnIynobeXlfIy9vJTIz\n38AHH8wpXp+ZmQkrK3f8dVPDxrCyqo2cnJziNuPGTcJPP91DTs5ZpKWtxbhxUxAXF1euHD/99BPq\n16+PiRMnonHjxggJCUF6ejo8PT3Rp08f2NrawsfHBxMnTsS+fftK/O2oUaPg5+cHHx8fqNVquLu7\nY9CgQWjatCmCg4Oxe/fuEu1fffVV2NnZwdvbG/369cOGDRtK5Vm3bh3UajXGjh2L+vXrY/To0WjR\nogWio6NhZWWF/Px8JCYmIjc3Fy4uLmjfvn259peILIP0opGdnY3Q0FAsXLgQ9vb2pdaLh467V3bw\n9saNWxCiXfHjoqJ2SEu7WfxYKVzHAawHkAwbm2lo1ao1nnjiieI2O3ZsR17evwE0AdAVeXlj8euv\nO8uVo23btli5ciWSkpJw4MABJCYmYvHixUhLS0NoaCjc3Nzg4OCAt99+Gzdv3izxt76+vsX/dnFx\nKfG4cePGSElJKdHez8+v+N/+/v5ITU0tlefKlSvYv38/HB0di5fExERcv34d1tbW2LJlCzZv3gxX\nV1cMHDgQCQkJ5dpfIotSVASMGAHcvi07idFJvUe4TqfD0KFDMXLkSISEhJRa7+rqiqSkpOLHycnJ\ncHV11butiIiI4n9rNBpoNBq97QYPfg6//z4Hubl+AIpQt+5cDB48rnh948aNsWdPNEaNegMpKX9H\nx46dsWHD1hLFqkEDR2RlJQBQstSqlQBHx16G7/hD1Go1hg8fjh9++AGpqanIyMjAmTNn0LBhQ3z5\n5ZeYMWPGI//+4cL6sBMnTqBPnz4AgOPHj+t9D5s1awaNRoPt27fr3UaXLl3www8/IC8vD++++y7+\n7//+D999952Be0hkYXbvBuLjgYYNZScxmFarhVarrfR2pBUNIQQmTJgALy8vhIeH620THByMpUuX\nIjQ0FHFxcWjYsCFcXFz0tn2waDzKO+9MwfXrN7BihT8AFSZNmojJk98o0aZTp06Ijz9c5jaWLZuP\nESNeRn7+aNjaXsCTTyZi7NiVBr0+AJw/fx7R0dF4+eWX0aRJE5w8eRLr169Hz549UadOHTg6OsLW\n1hZHjhzB0qVLDd5uWb7++mt07doVFy9exM6dO7Fx48ZSbUaOHIl58+ZhzZo1GDRoEOzs7BAXF4fW\nrVvD1tYWhw4dQt++fQEAtra2SE9Pr3QuIrMVGQlMnAiY0WnrD/+YftyP0bJIKxoHDx7EunXr4OPj\nA39/fwDAxx9/jKtXrwIAwsLCEBQUhJiYGHTo0AH29vZYudLwL+ayWFlZYcGCj7FgwccV3kZISAhi\nYtzw66+/wsGhBUaPXoN69eoZ/Pf169fH4cOH8emnn+L27dtwdHTEoEGD8MknnyA9PR3h4eFo3rw5\n2rVrhzfeeAOzZ89+5PYe7AWpVKpSh/CCg4Ph7++PO3fu4P333y/+8n+wrZubsj//+Mc/EB4eDhsb\nG6jVakRGRqKoqAgLFy7EmDFjUL9+ffTu3RsrVqwweH+JLEpyMqDVAmvWyE4iBW/3asEuX76Mli1b\noqCgAFZWxhm+qunvOdUA06cD6enAsmWyk1RKRT+rUsc0iIjMik4HfPkl8MsvspNII/3sKapenCqE\nqApFRQGenoC3t+wk0rCnYcE8PDxQWFgoOwaR5bg/AF6DcUyDqhTfc7JY588DvXoBV64ARp4nrjpU\n9LPKw1NERIZYsQIYP94iCkZlsKdBVYrvOVmk3FygWTPg2DHAw0N2mirBs6f0cHR05ECwkTk6OsqO\nQFT1Nm0CunSxmIJRGRZdNG7duiU7AhGZOyGA5cuBCl5BbWk4pkFE9ChxccrEhM8/LzuJSWDRICJ6\nlMWLgcmTASPNqmDqLHognIioUlJSgA4dgEuXAAcH2WmqFE+5JSKqapGRwMiRFlcwKoM9DSIiffLy\ngObNgf37gaeekp2myrGnQURUlTZuBDp1ssiCURksGkREDxMCWLQImDJFdhKTw6JBRPSwAweAu3eB\n556TncTksGgQET1s0SKeZlsGDoQTET3o6lXA3x+4fBmoX192mmrDgXAioqqwfDkwZoxFF4zKYE+D\niOi+7GygRQvg8GGgZUvZaaoVexpERJX19deARmPxBaMyLHqWWyKiRyksLMS//70Iu3cfQstmTbD0\n1yhYf/ut7FgmjUWDiGqsV199E99+G4/c3IkYbr0Gv1n/iXbt24OjGWXjmAYR1Uh5eXmoV68hCgtv\nAKiPw1Dj0zr3MGz9dAwZMkR2vGrHMQ0ionL46wvTFt1xAA2Rge02rigsLJSay9Sxp0FENdaQISOx\nY0cGNty9iV9UjbDliTM4d+5EjbhtMXsaRETltGHDV4gY7o7uNr/h9qAGOHo0pkYUjMpgT4OIaraw\nMKBpUyAiQnYSo6ro9yaLBhHVXDduAG3aAOfPA40by05jVGZ5eGr8+PFwcXFBhw4d9K7XarVwcHCA\nv78//P39MXv2bCMnJCKLtmwZMGxYjSsYlSH1Oo1x48Zh8uTJGD16dJltevXqhaioKCOmIqIaIStL\nmWcqNlZ2ErMitafRo0ePxw468bATEVWLzz4D+vQBWreWncSsmPTZUyqVCrGxsfDy8kJQUBDi4+Nl\nRyIiS5CXByxcCEybJjuJ2THpaUQ6duyIpKQk2NraYvXq1QgODkZiYqLethEPnPmg0Wig0WiME5KI\nzM/q1co9M3x9ZScxGq1WC61WW+ntSD976vLlyxg0aBBOnz79yHZCCDg7OyMhIQFOTk4l1vHsKSIy\nWEEB8NRTwNq1QLdustNIY5ZnTz1OWlpa8U5t27YNdnZ2pQoGEVG5bNoEuLvX6IJRGVIPTw0fPhz7\n9u1Deno63N3dMWPGDOh0OgBAWFgYNm/ejMjISNjY2MDHxwdbt26VGZeIzF1RETBvHrBggewkZkv6\n4amqwMNTRGSQqChgxgzg2DFApZKdRiqLPDxFRFRlhADmzFHOmKrhBaMyWDSIqGbYuxe4cwcYPFh2\nErPGokFENcPMmUovw9padhKzxqJBRJZPqwVSUoBXXpGdxOyxaBCR5YuIAD76CLAx6euZzQKLBhFZ\ntvu9jBEjZCexCCwaRGTZ2MuoUiwaRGS52MuociwaRGS52MuociwaRGSZ2MuoFiwaRGSZ2MuoFiwa\nRGR59u5lL6OasGgQkWURQrnyOyKCvYxqwKJBRJYlKgrIzQWGD5edxCKxDBOR5SgsBD74AJg7F7Di\nb+LqwHeViCzHN98ADRoAAwfKTmKxeBMmIrIM+flA27bAypVAr16y05g83oSJiGq2L74AnnqKBaOa\nsadBROYvJwdo3Rr46SegY0fZacwCexpEVHMtXgx0786CYQTsaRCRebt9WzksdeAA0KaN7DRmo6Lf\nmywaRGTe/v53IDMT+Pxz2UnMCouG+e8GEZXXxYtAQABw9izQpInsNGaFYxpEVPNMmwaEh7NgGBF7\nGkRkng4dAoYNA86fB+rWlZ3G7LCnQUQ1hxDAu+8Cs2ezYBgZiwYRmZ/Nm4G7d4FRo2QnqXF4eIqI\nzMu9e0D79soV4M88IzuN2TK7w1Pjx4+Hi4sLOnToUGabadOmwcfHB4GBgTh37pwR0xGRyVq2DGjX\njgVDEmlFY9y4cdixY0eZ63/++WecPHkSp06dwqJFizB27FjjhSMi03TzJjBvHvDJJ7KT1FiPLRqL\nFy/G7du3q/yFe/ToAUdHxzLXR0VFYcyYMQAAtVqNjIwMpKWlVXkOIjIjH34IvPyy0tMgKR5bNNLS\n0hAQEIBhw4Zhx44dRhs7SElJgbu7e/FjNzc3JCcnG+W1icgEnTgB/PADMHOm7CQ12mPv3DdnzhzM\nmjULv/76K1atWoU333wTw4YNw4QJE+Dp6Vmt4R4uUCqVqsy2ERERxf/WaDTQaDTVlIqIjE4IYPJk\nYNYs4BFHKKhsWq0WWq220tsx6HavVlZWaNKkCVxcXGBtbY3bt28jJCQEISEhmDNnTqVD6OPq6oqk\npKTix8nJyXB1dS2z/YNFg4gszDffKKfYjh8vO4nZevjH9IwZMyq0nccenlq0aBE6deqEf/zjH+jW\nrRvOnDmDyMhInDp1Clu2bKnQixoiODgYa9asAQDExcWhYcOGcHFxqbbXIyITlZUFTJ0KLF0KWFvL\nTlPjPbancevWLXz//fdo3rx5ieetrKzw/fffV/iFhw8fjn379iE9PR3u7u6YMWMGdDodACAsLAxB\nQUGIiYlBhw4dYG9vj5UrV1b4tYjIjM2eDfTpA3TpIjsJgRf3EZEpO38e6NYNOHOGkxJWMbO7uI+I\n6JGEUGawnTaNBcOEsGgQkWn6/nvgyhXlrCkyGTw8RUSm584dwMsL2LAB6NFDdhqLxDv3mf9uENF9\nkycrp9h++aXsJBarot+bBl2nQURkNEePAt99B8THy05CenBMg4hMR0EB8PrrwIIFgJOT7DSkB4sG\nEZmOxYuBRo2AV16RnYTKwDENIjINV64AnTop9/5u3Vp2GovH6zSIyHzdn5AwPJwFw8RxIJyI5Nuw\nAbh4URkAJ5PGw1NEJNf164CvLxAdDXTuLDtNjcHrNMx/N4hqHiGAoUOBtm2Bjz+WnaZG4XUaRGR+\nvv1WmZRwwwbZSchA7GkQkRw3bgA+PkBUFPD008VPCyFw48YN1KpVC468S1+14dlTRGReJk0Cxowp\nUTAyMzPRvXs/NG/eDi4uzTB69OsoKiqSGJIexqJBRMb33XfKPTIeuuXo5MlT8dtvrrh370/odKnY\nsuUPLFsWKSkk6cOiQUTGde2ack3G118DdeqUWHXo0DHcuxcGwBpAfeTmjsaBA79JiUn6sWgQkfEI\nAYwbp8wvpef2rZ6eHrC23nO/MWrX3ounnmpeqh3Jw4FwIjKeJUuAdeuAAwcAW9tSqy9fvgy1ujfy\n8jwgRCY8PGohNnYn6tWrJyGsZeN1Gua/G0SW7exZQKMBYmMfOVVIZmYmYmNjUatWLXTv3h21atUy\nXsYahEXD/HeDyHLduweo1cCbbwKvvio7DYFFg0WDyJS99x6QkAD88AOgUslOQ+AV4URkqvbuBb75\nBjh5kgXDAvDsKSKqPjduAKNGKafXOjvLTkNVgIeniKh6FBYC/fsrM9dyMkKTw2lEiMi0zJ2rDIDP\nnCk7CVUhjmkQUdXbuxdYtgz47TfAhl8zloQ9DSKqWmlpwMiRwOrVwJNPyk5DVUxq0YiJiUHHjh3h\n4+ODJUuWlFqv1Wrh4OAAf39/+Pv7Y/bs2RJSEpHBCguBV14Bxo8HnntOdhqqBtL6jYWFhRg/fjx2\n7doFV1dXBAQEoG/fvmjXrl2Jdr169UJUVJSklERULjNnKoUjIkJ2Eqom0noaR44cQatWreDh4QFb\nW1uEhoZi69atpdrxrCgiM/Hjj8DKlcDGjYC1tew0VE2kFY2UlBS4u7sXP3Zzc0NKSkqJNiqVCrGx\nsfDy8kJQUBDi4+ONHZOIDBEfr8xcu2UL4OIiOw1VI2mHp1QGXBnasWNHJCUlwdbWFqtXr0ZwcDAS\nExP1to14oDus0Wig0WiqKCkRPdLt20BICLBgARAQIDsNlUGr1UKr1VZ6O9Iu7ouLi0NERAR27NgB\nAJg7dy6srKwwdepUve2FEHB2dkZCQgKcnJxKrOPFfUSSFBYCAwcCbdoA//mP7DRUDmZ3cV/nzp2R\nkJCAy5cvIz8/H5s2bUJwcHCJNmlpacU7tW3bNtjZ2ZUqGEQk0YcfKhfwffKJ7CRkJNIOT9nY2ODr\nr7/G4MGDUVBQgNdeew3t2rXDZ599BgAICwvD5s2bERkZCRsbG/j4+OgdKCciSTZuBDZsAI4e1XtD\nJbJMnHuKiMrv4EFg8GBg1y7Ax0d2GqoAszs8RURmKjERGDoUWLuWBaMGYtEgIsPdvAkEBSkX8fXr\nJzsNScDDU0RkmLw84Nlnga5dgfnzZaehSuLtXs1/N4hMV1GRMgmhTgds2gRY8SCFuePtXomoeggB\nTJ0KXLoE7NnDglHDsWgQ0aPNnw9s3w7ExAB2drLTkGQsGkRUts8+Az7/HDhwAOCFtQQWDSIqy6ZN\nyllSMTG8mRIVY9EgotJ++QWYMgXYuRPw9JSdhkwIiwYRlRQTA4wapdwfgxfv0UN4GgQR/WXfPuDF\nF5V5pbp2lZ2GTBCLBhEp9u0DXnpJKRjPPCM7DZkoFg0iArRapWBs2sSCQY/EokFU02m1wLBhSsHo\n3Vt2GjJxLBpENdmOHUrB+PZbFgwyCIsGUU21YQMwZgywdSug0chOQ2aCp9wS1UTLlgHz5gG7dwPe\n3rLTkBlh0SCqIY4ePYrXX3sHIy/E4xVVAerHHoQ9CwaVE6dGJ6oBrl69ig7tO2FOjh+6IRkhtdrB\n6xkrbN++WXY0koRToxNRmbTbtmFjXi3UQhE0iENmfm2k7myAgoIC2Njwa4AMx54GkaW7ehUZ3bvj\n+2tFCCu4iALUAnAVtWq1R15eFlQqleyEJEFFvzd59hSRJTtyBOjSBXXfeAPzPJxhXXssgAWoW/dZ\n/POf/2TBoHJjT4PIUn37LTBpEvDVV0BwMLKysrBs2XIkJV3Hs8/2wgsvvCA7IUnEe4Sb/24QVQ2d\nDpg2Ddi8WZmp1s9PdiIyQRwIJyLg2jXg5ZcBe3vgt9+ARo1kJyILwzENIksREwN07gz07QtER7Ng\nULVgT4PI3BUVAQsWAJ9+CqxeDfTrJzsRWTAWDSJzlpQEjB4NFBQAhw8DzZvLTkQWTurhqZiYGHTs\n2BE+Pj5YsmSJ3jbTpk2Dj48PAgMDce7cOSMnJDJhGzcCnToBzz2nTG/OgkFGIK2nUVhYiPHjx2PX\nrl1wdXVFQEAA+vbti3bt2hW3+fnnn3Hy5EmcOnUKhw8fxtixYxEXFycrMpFpuHNHOZX22DFg+3al\ncBAZibSexpEjR9CqVSt4eHjA1tYWoaGh2Lp1a4k2UVFRGDNmDABArVYjIyMDaWlpMuISmYYff1Rm\npW3QADh+nAWDjE5aTyMlJQXu7u7Fj93c3HD48OHHtklOToaLi4vRclY7IQBelUuPk5oKTJ4MnDkD\nrFsH9OolOxHVUNJ6GoZOX/DwxScWNe1BejrQrBkwcaJyB7V792QnIlNTVAR89hng6wu0bw+cPMmC\nQVJJ62m4uroiKSmp+HFSUhLc3Nwe2SY5ORmurq56txcREVH8b41GA4053InM2RnYtUu5c9qsWUBo\nKPD880BICNC/P9CwoeyEJFNcHBAervRE9+7lzZKoUrRaLbRabeU3JCTR6XSiZcuW4tKlS+LevXvC\n19dXxMfHl2gTHR0t+vfvL4QQ4tChQ0KtVuvdlsTdqFrXrwvxxRdCDBggRP36QvTtK8SSJUJcuSI7\nGRnT1atCjBghhKurEKtXC1FYKDsRWaCKfm9KnXtq3759CA8PR0FBAV577TVMmTIFn332GQAgLCwM\nAPD+++8jOjoa9vb2WLlyZYmzq+6zyLmnsrOBX39VeiHR0cphrOBgYNAgoGNHjoNYouxs4JNPgKVL\ngTfeAKZOBerVk52KLBQnLDT/3ShbQQEQGwts26YUkdxcpXgMGgT07g3Y2clOWCPcvHkTCxcuxrVr\n6Rg4sC8GDx5cNRvOzQWWL1cKRp8+wNy5vOaCqh2LhvnvhuHOnweiooCffgJOnAA0GmDgQGDAAKCM\nMR+qnDt37sDb+2mkpfWETueNunWXYsaMSfj738MrvtG7d4HPPwfmzwe6dgWmTwc6dKi60ESPwKJh\n/rtRMbduAb/8ohSQHTsAd3cgKEgZSO/SBeCtPKvEl19+ibfeikZu7g//e+Y87O27ITs7HQBQVFSE\nmTPnYu3aLbC3r4t//etDPP/88/o3lpEBfPkl8J//KBMMRkRw+nIyOt65r6ZycgKGDwfWrwfS0oBl\ny5TxjilTgMaNlWmyV64EUlJkJzVrd+/eRVHREw888wTy8+8WP5o+fQ4++WQbLl5cjtOn38XQoWNK\nz15w6ZJyNlTLlsDvvyu9Rd7vgswMexqWLDVV6X388otyam/Tpso8Rf36AT16AHXryk5oNi5cuABf\n30Dk5CwE4AU7u+kICXHGhg1fAwDc3NojJWU9AP///cVsvPXWHfzn0/nK6bIrVgB79gATJigX6T1w\n0SqRDOxpUGlPPgmMHw9s2gTcuKHc9tPRUbkmpHFjZSxk1ixlkF2nk5220tauXY+WLf3g5tYeM2fO\nRVFRUZVt29PTE7t3/4ROnb5Cs2ajMWaMJ1auXF68vk6dOgBuFj9uZnUZA04cBVq1At55B+jZE7h8\nGfjXv1gwyKyxp1FTZWUB+/cDu3cry6VLymBsr17K0qkTUKuW7JQG+/nnn/Hii2G4e3cRgGaoW/dv\n+Oij4Xj//XeN8vrffvsdwsdOQd+7vTEccQhUXYbNK6+g/ltvKe9lOU6RzsnJwYcfzsKxY2fg7d0a\n8+ZFwMHBoRrTU03EgXDz3w250tOVIrJvn7IkJgJqNdCtm1JMAgMBE/7ievrpnjh69BgAewCOAD5E\n+/YrcPZsbPW+cEaGMjbx3Xco2LMHp50b40x7L/RauADN2rYt9+aEEOjevR+OH3dCXt5w1K69Da1b\nn8Hx4/tha2tbDTtANRWLhvnvhmm5fRs4eBA4dEj577FjQIsWyhlZAQHK4uUFmMAX2e+//46AgD4o\nKIgD0BrACgDz8fTTrXD48M6qfbGiIuU0519+UcaLTpwAnnkGGDZMuW6mQYNKbT4xMRG+vhrk5l6G\nMsuPQL1mLiiZAAALiUlEQVR63tizZxUCAgKqYg+IAFT8e5PnY5J+jo7KtR8DByqPdTplsrxDh4AD\nB4CFC4ErVwAfH+Xwi6+vsnh7G32A/fjx47C1DUJBQev/PRMG4E3MmBFZ+Y0XFACnTyvjPgcPKicU\nODkpc4RNm6YcyjPC/vJHEZkK9jSo4jIzlXs6HD+uFJRTp5QLD5s1Uy5Sa9v2r6VNm2qbEmP37t0I\nCXkTOTn3D08dhL19CLKy/izfrMgFBcB//6sUiZMngSNHgCNHUNC0KeIdHJDYuAlaTBgH/6q6ElyP\noqIidO/eDydOPPG/w1NRaNXqFE6cOMDDU1SleHjK/HfDMuh0wLlzyn0fzp8H/vhDeZyQoMza26JF\nycXdXTkVuGlT5Rd8BebUEkJg7NiJ2LJlJ6yt26OgIA7ffbcaQUFB+vNduwZcvPjXcunSXzldXZXe\n0/96UDefegrevfrj1q2e0OncYWf3OTZs+BzBwcFV8Gbpl5OTgw8+mImjR0+jQ4enMH/+DA6EU5Vj\n0TD/3bBshYXKdSOXLpVcUlKUL/HUVGUOpiZNgEaNlMNj95eGDZVDQHXq/LXcP7OrqAgoKoIoKsKV\nCxeQc+MG3Bo2hIONjTIB4J07yunGaWnKkpmpnG7csmXJ5amnlENr9vYlYs+dOw8REQnIz//qf8/s\nRIsWf8fFiyeN+/4RVTGOaZBps7ZWehXu7so1C/rcvQtcv65MjXL7dsnl7l2lAKSlAXl5yg2rVCrA\nygqwsoLKygoe1tZK0alXT/nyr1dPGZhu3BhwcVEWJycli4EyMjKRn9/sgWeaIzs7q3LvBZEZY9Eg\n02Fn99dhKxMRHDwAS5e+iNzcngDcYWf3FoYMqZ5DU0IIrF27FgcOHEXr1s3x5puTYMcZjMnE8PAU\n0WNs2bIF77wzHTk5WRg69AUsXvwv1K5du8pf580338XKlVrk5o5CnTr74OV1C4cO7eIAOFULjmmY\n/25QDZaVlYVGjZpAp0uGcnFiEerV64wff/wEffr0kR2PLBDnniIyY3l5ebCyqgXg/sWBVrCyegK5\nubkyYxGVwqJBZAKcnZ3h4+OHWrXeBHAaKtUS2NicRbdu3WRHIyqBRYPIBKhUKvzyy/cYNCgHrq4v\no0uXaBw8uAtOTk6yoxGVwDENIqIaiGMaRERU7Vg0iIjIYCwaRERkMBYNIiIyGIsGEREZjEWDiIgM\nxqJBREQGY9EgIiKDSZkaPSsrC6NGjcLFixfh6emJtWvXop6eW4F6eHigQYMGsLa2hq2tLY4cOSIh\nLRER3SelpzFr1ix07doVp06dQmBgIGbPnq23nUqlglarxYkTJyy2YGi1WtkRKoX55WJ+ucw9f0VI\nKRpRUVEYM2YMAGDMmDH48ccfy2xr6dODmPv/dMwvF/PLZe75K0JK0UhLS4OLiwsAwMXFBWlpaXrb\nqVQqPPPMM/D398cXX3xhzIhERKRHtY1pPPvss7h+/Xqp5+fMmVPisUqlgkql0ruNgwcPomnTpvjj\njz8QFBSEtm3bokePHtWSl4iIDCAkaNOmjbh27ZoQQojU1FTRpk2bx/7N22+/LRYsWKB3naenpwDA\nhQsXLlwMXDw9PSv0/S3l7Kng4GCsXr0aU6dOxerVq/HCCy+UapObm4vCwkLUr18ff/75J37++Wcs\nXrxY7/YSExOrOzIREUHS/TTKOuU2NTUVr732GqKjo3Hx4kUMGTIEANCoUSMMGzYMYWFhxo5KREQP\nsIibMBERkXGY3RXhWVlZeOGFF+Dj44PBgwcjOzu7VJukpCT07t0bXl5e0Gg0WLVqlfGDPiQmJgYd\nO3aEj48PlixZorfNtGnT4OPjg8DAQJw7d87ICR/tcfnXr18PX19f+Pr6YsSIEThz5oyElGUz5P0H\ngKNHj8LGxgbff/+9EdM9niH5jx49iu7du8PX1xcajca4AR/hcdnv3r2LMWPGwN/fH7169cLWrVsl\npNRv/PjxcHFxQYcOHcpsY8qf28flr9DntkIjIRK99957Yv78+UIIIebNmyemTp1aqs21a9fEiRMn\nhBBC/Pnnn8LFxUXEx8cbNeeDCgoKhKenp7h06ZLIz88Xvr6+pfJER0eL/v37CyGEiIuLE2q1WkZU\nvQzJHxsbKzIyMoQQQqxatcrs8t9v17t3bzFgwACxefNmCUn1MyT/7du3Rfv27UVSUpIQQvn/3hQY\nkj0yMlJMnDhRCCHE5cuXRcuWLUVRUZGMuKXExMSI48ePC29vb73rTflzK8Tj81fkc2t2PQ1DLgxs\n0qQJ/Pz8AADOzs4ICAhAamqqUXM+6MiRI2jVqhU8PDxga2uL0NDQUr+mHtwvtVqNjIyMMq9fMTZD\n8nfp0gUODg4AgAEDBiA5OVlGVL0MyQ8AS5YswYsvvognnnhCQsqyGZL/m2++wdChQ+Hm5gZA+f/e\nFBiS3cHBAVlZWdDpdLh16xbq1q1b5mn4xtajRw84OjqWud6UP7fA4/NX5HNrdkXD0AsD70tMTMTZ\ns2cRGBhojHh6paSkwN3dvfixm5sbUlJSHtvGVL54Dcn/oM8//xwhISHGiGYQQ9//rVu3YuLEiQBg\nMl9agGH5ExIScOvWLfTo0QP+/v5Yv369sWPqZUj24cOHo7CwEM7OzujevbvJZDeEKX9uy8vQz62U\nU24fpyouDASA7OxshIaGYuHChbC3t6/ynIYy9AtIPHROgql8cZUnx969e7Fu3TrExsZWY6LyMSR/\neHg45s2bB5VKBSGESU1fY0h+nU4HrVaLXbt2ITc3F88++yyGDBkCOzs7IyQsmyHZly5dChsbG1y7\ndg2nT5/GgAEDcOXKFVhZmcdvWlP93JZHeT63Jlk0du7cWeY6FxcXXL9+HU2aNMG1a9fQuHFjve10\nOh2GDh2KkSNHSv/V6+rqiqSkpOLHSUlJxYcRymqTnJwMV1dXo2V8FEPyA8CpU6fw+uuvY/v27WjY\nsKExIz6SIfl/++03hIaGAgDS09Oxfft22NraIjg42KhZ9TEkv7u7O/r3748mTZoAADp37oyYmBj0\n69fPqFkfZkj2mJgYTJgwAXXr1oVarcaTTz6J//73v2jbtq2x45abKX9uDVXuz22VjbgYyXvvvSfm\nzZsnhBBi7ty5egfCi4qKxKhRo8Tbb79t7Hh66XQ60bJlS3Hp0iVx7969xw6EHzp0yKQG1AzJf+XK\nFdGqVSsRFxcnKWXZDMn/oLFjx4otW7YYMeGjGZL/jz/+EAEBASInJ0fcvHlTtG7dWmRlZUlK/BdD\nsq9YsUJMmjRJFBYWigsXLohWrVpJSqvfpUuXDBoIN7XP7X2Pyl+Rz63ZFY3MzEwREhIiOnToIF54\n4YXiD0ZKSooICgoSQgixf/9+oVKphK+vr/Dz8xN+fn5i+/btMmMLrVYr/Pz8hLe3t1i0aJEQQvmw\nrFixorjN1KlThbe3t1Cr1VLP9tLncfknTJggnJycit/vgIAAmXFLMeT9v8/UioYQhuVfvny5aNeu\nnWjRooVYtmyZrKilPC57RkaGmDJlivD39xfPPfeciI6Olhm3hNDQUNG0aVNha2sr3NzcxFdffWVW\nn9vH5a/I55YX9xERkcHMY6SJiIhMAosGEREZjEWDiIgMxqJBREQGY9EgIiKDsWgQEZHBWDSIiMhg\nLBpERGQwFg2iKnb06FH4+vri3r17yMnJgbe3N+Lj42XHIqoSvCKcqBp89NFHyMvLw927d+Hu7o6p\nU6fKjkRUJVg0iKqBTqdD586dYWdnh0OHDpnldNlE+vDwFFE1SE9PR05ODrKzs3H37l3ZcYiqDHsa\nRNUgODgYI0aMwMWLF3Ht2jUsWbJEdiSiKmGSN2EiMmdr1qxB7dq1ERoaiqKiInTt2hVarRYajUZ2\nNKJKY0+DiIgMxjENIiIyGIsGEREZjEWDiIgMxqJBREQGY9EgIiKDsWgQEZHBWDSIiMhgLBpERGSw\n/wdMmyJ3RkfB2QAAAABJRU5ErkJggg==\n", "text": [ "" ] } ], "prompt_number": 4 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Using this model, we will now explore the bias-variance tradeoff using polynomial regression. Given some training data and an order k, we will learn a _kth order polynomial_ function $\\hat{f}$ that maps each $x_i$ to a prediction $\\hat{y}_i$. The following code illustrates polynomial regression, learning a 4th degree polynomial to fit our 10 example data points." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def expand(x, order):\n", " \"\"\"Returns a 2d array with (order + 1) columns.\n", " Column i is equal to x raised to the power i\"\"\"\n", " cols = []\n", " for i in range(order + 1):\n", " cols.append(x ** i)\n", " return np.column_stack(cols)\n", "\n", "def polynomial_regression((x, y), order):\n", " \"\"\"Returns a function learned by polynomial regression of order order\"\"\"\n", " lsResult = np.linalg.lstsq(expand(x, order), y)\n", " lsCoefficients = lsResult[0]\n", " return lambda v : np.dot(expand(v, order), lsCoefficients)\n", "\n", "f_hat = polynomial_regression(exampleData, order=4)\n", "\n", "# Plot f_star:\n", "plt.plot(domainSamples, f_hat(domainSamples), 'g')\n", "\n", "# Plot data:\n", "plt.scatter(exampleData[0], exampleData[1])\n", "\n", "# Format/show plot:\n", "plt.xlabel('x')\n", "plt.ylabel('y')\n", "plt.legend(('f_hat', 'Samples'), loc='upper left')\n", "plt.show()" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "display_data", "png": "iVBORw0KGgoAAAANSUhEUgAAAY0AAAEPCAYAAAC+35gCAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XlcVOX+B/DPsC8Cgggo4AamyI4QaC5YWomKe2G5oFZe\ns9K6lnX7ecWbWzdv5pbebuWee2655JIjbqi54AJ6ATdAQBGRfX9+f1hzRUFGhHlmhs/79ZpXzJxn\nznzO5Dnfec5zFoUQQoCIiEgNBrIDEBGR7mDRICIitbFoEBGR2lg0iIhIbSwaRESkNhYNIiJSm7Si\nkZycjB49esDT0xOhoaFYvnz5Y22USiVsbGzg7+8Pf39/zJgxQ/NBiYhIxUjWBxsbG2PevHnw8/ND\nZmYmvLy8EBwcDA8Pj0rtunfvju3bt0tKSURED5PW03BycoKfnx8AwN7eHkFBQbh169Zj7XjuIRGR\n9tCKMY3ExERcunQJISEhlV5XKBQ4duwYPD09ERYWhri4OEkJiYgI0IKikZeXh4iICMybNw+WlpaV\npgUEBCA5ORnnzp3DoEGDEB4eLiklEREBgELmtadKS0vRt29f9O7dG5MmTXpiWyEE7O3tkZCQADs7\nu0rT3N3dkZSUVJ9RiYj0ipubGxITE5/6fdJ6GkIIjB07Fp6entUWjIyMDNWYxo4dO2Bubv5YwQCA\npKQkCCF08jFt2jTpGZhffg7m182HLuev7Q9taUdPHT16FKtXr4aPjw/8/f0BALNmzcLNmzcBAOPG\njcOmTZuwZMkSGBkZwcfHB9u2bZMVl4iIILFodOnSBRUVFU9sM2HCBEyYMEFDiYiIqCbSB8IbutDQ\nUNkRngnzy8X8cul6/tqQOhBeVxQKBfRgMYiINKa2201pu6c0wc7ODvfu3ZMdo0GxtbVFVlaW7BhE\nVE/0uqfBHojm8Tsn0g21XVc5pkFERGpj0SAiIrWxaBARkdpYNIiISG0sGpIkJCRg6NChsLW1xaJF\ni6psExkZialTp2o4GRFR9fT6kFttNmfOHNjY2ODu3bswMKi6disUCigUilrNPyoqCklJSVi1atWz\nxCQiqoQ9DUlu3LiB4ODgagsGEZE24hZLghdffBFKpRIffPABrK2tn3h54vz8fERERMDOzg4hISG4\nevWqatrEiRPRokULWFtbIzAwEEeOHAEA7NmzB7Nnz8b69ethZWWluiAkEdGzatAn9ymm127Xz6PE\ntKf/Cnv06IERI0ZgzJgx1baJjIzEli1bsHz5cnTt2hWjR49Go0aNsHbtWgDAmjVrEBYWBoVCgVmz\nZmHVqlW4ceMGTExMMH36dCQlJWHlypW1Xq7a4Ml9RLqBlxGphdps7Ov089X4H9a9e3cMHDgQAPDm\nm29i+vTpqmlvvvmm6u+pU6di0aJFuHLlCry9vVXXzCciqkvcPSVRTYPcCoUCfn5+qudOTk7Iy8tT\nPZ87dy46dOiAxo0bo0WLFiguLkZmZma95SUiYtHQctX1Fg4fPoxp06Zh9erVyM7Oxs2bN2Fubq5q\nz91ERFQfWDQkqmmj/qTpFhYWMDExgY2NDTIyMvC3v/0NxcXFqulOTk6Ii4ur9BoR0bNi0ZBInd1T\nj7b583nHjh3x7rvv4sUXX0S3bt3g5eUFV1dXVbuhQ4fC0tISDg4OCAwMrPvwRNQgNeijp6ju8Tsn\n0g28NDoREdU7Fg3JPD09YWVl9djjz3MxiIi0CXdPUZ3id04NRfSNaIS4hMDE0ER2lFrh7ikiIg25\nV3gP/db2Q1lFmewoGseiQUT0lHYm7ESPVj1gYWwhO4rGsWgQET2lbVe2oX+7/rJjSMGiQUT0FIrK\nirAvaR/6PtdXdhQpWDQasKioKIwYMUJ2DCKd8tu13+Dj6IOmlk1lR5GCRUOSI0eOoHPnzrCxsUGT\nJk3QpUsX/P777xrNUNu7AhI1ZFsvb8WA9gNkx5BGWtFITk5Gjx494OnpidDQUCxfvrzKdp999hl8\nfHwQEhKCy5cvayRbaWkpfvjhB0yd+nfs2LGjzuefk5ODvn374rXXXkNycjJSU1Mxbdo0mJqa1vln\nPQkPjSV6OhWiAtuvbG+w4xkAACFJWlqaOHv2rBBCiDt37ghHR0cRFxdXqc3OnTtF7969hRBCxMTE\niODg4CrnVd1iVPd6SkqKWLBggVi4cKFITU2tNK2srEyEhvYRFhY9BPB3YWnZTnz++fSnWraanD9/\nXpiZmYmSkpLHpiUmJooePXqIJk2aCHt7e/Hmm2+K7Oxs1fSWLVuKb7/9VoSEhAgHBwfx8ccfi7y8\nPDF06FDRpEkT0bNnT1X7a9euCYVCIdatWyfat28vmjVrJubOnaua17Rp08Tw4cNVz48fPy46deok\nbGxshK+vr1AqlappW7duFaGhocLGxka0bt1arFmzpsplk/hPiqjeHbt5THh96yU7Rp2o7bqqNWt4\n3759xf79+yu9Nm7cOLFu3TrV83bt2on09PTH3vs0RePKlSvC2tpRmJmNFmZmkaJx42YiMTFRNf3g\nwYOiUSMvAZQKQAggXRgbW4i8vDxVm7y8PDFkyEhhaWknHB3biPXrNzz18rq5uYnBgweLHTt2iKys\nLNXriYmJYv/+/aKkpETExsaKgIAAMWnSJNX0Vq1aCX9/f3H27FkRGxsrrK2tRVBQkNi+fbu4deuW\nCA4OFitXrhRC/K9oDBs2TBQUFIgLFy4IOzs71ff8cNFISUkR1tbWYtmyZSInJ0esWLFC2NjYiMzM\nTFFSUiJatmwpYmJihBBCpKeni0uXLqn9nRPpiyn7pojPD3wuO0adqO26qhVjGomJibh06RJCQkIq\nvZ6amlrpyq0uLi5ISUl5ps+aMuUfyM39EEVFP6KoaBlyct7F55/PVE3PycmBgYEr/ndTQwcYGJgi\nPz9f1Wb06An45Zdi5OdfQkbGKowe/QFiYmKeKscvv/wCKysrjB8/Hg4ODujfvz8yMzPh5uaGl156\nCcbGxvDx8cH48eNx6NChSu8dMWIE/Pz84OPjg+DgYLi6uqJfv35o1qwZwsPDceDAgUrt33rrLZib\nm8PLywuvvPJKlZcoWb16NYKDgxEZGQkrKyuMHDkSrVu3xs6dO2FgYICSkhIkJiaioKAAjo6O6NCh\nw1MtL5E+2HZlW4MezwC0YCA8Ly8PERERmDdvHiwtLR+bLh7Z7/6sg7e3b2dBCA/V84oKD2Rk3FU9\nf1C4zgBYAyAFRkafwd29LZo2/d+REnv27EZR0b8AOAHojKKiSOzdu++pcrRv3x7Lli1DcnIyjhw5\ngsTERCxYsAAZGRmIiIiAi4sLbGxs8OGHH+Lu3buV3uvr66v629HRsdJzBwcHpKamVmr/8N3//P39\ncevWrcfy3LhxA4cPH4atra3qkZiYiPT0dBgaGmLz5s3YtGkTnJ2d0bdvXyQkJDzV8hLpuiuZV5Bb\nnIuOzTrKjiKV1HuEl5aWYvDgwRg+fDj69398YMnZ2RnJycmq5ykpKXB2dq5yXlFRUaq/Q0NDERoa\nWmW7gQNfxrlzM1FQ4AegAhYWszFw4GjVdAcHB/z2206MGPEuUlMnIyAgEGvXbqtUrKytbZGbmwDg\nQRYTkwTY2nZXf8EfERwcjGHDhmHLli24desWsrOzcfHiRTRu3Bjff/99pfuCV+XRwvqos2fP4qWX\nXgIAnDlzpsrvsEWLFggNDcXu3burnEenTp2wZcsWFBUV4a9//Sv+9re/YePGjWouIZHu+/OEPl09\n6lCpVEKpVD7zfKQVDSEExo4dC09PT0yaNKnKNuHh4Vi0aBEiIiIQExODxo0bw9HRscq2DxeNJ/no\now+Qnn4bS5f6A1BgwoTxeP/9dyu16dixI+LiTlQ7j8WLv8Qbb7yOkpKRMDZOQvPmiYiMXKbW5wPA\nlStXsHPnTrz++utwcnJCbGws1qxZg27dusHMzAy2trYwNjbGyZMnsWjRIrXnW50ff/wRnTt3xtWr\nV7Fv3z6sW7fusTbDhw/HnDlzsHLlSvTr1w/m5uaIiYlB27ZtYWxsjOPHj6Nnz54AAGNjY96LnBqc\nrZe3Iio0SnaMWnv0x3RNP0arI61oHD16FKtXr4aPjw/8/f0BALNmzcLNmzcBAOPGjUNYWBiio6Ph\n7e0NS0tLLFum/oa5OgYGBpg7dxbmzp1V63n0798f0dEu2Lt3L2xsWmPkyJVo1KiR2u+3srLCiRMn\n8PXXX+PevXuwtbVFv3798NVXXyEzMxOTJk1Cy5Yt4eHhgXfffRczZsx44vwe/uVT1d3+wsPD4e/v\nj/v37+PTTz9Vbfwfbuvi8mB5PvnkE0yaNAlGRkYIDg7GkiVLUFFRgXnz5mHUqFGwsrJCjx49sHTp\nUrWXl0jXpeelIz4zHqGtQmVHkY6XRtdj169fR5s2bVBWVgYDA80MXzX075z0039O/we/Xf8Nawfr\nz31ueGl0IqJ60pAvUPgoFg09p6uDdkTa4n7RfRy+eRhhbcNkR9EKUo+eovrVqlUrlJeXy45BpNN2\n/HcHQluFwtrUWnYUrcCeBhHRE2yM24ghHkNkx9AaLBpERNXIKc6B8roS4e3CZUfRGiwaRETV+OW/\nv6Bri66wMbORHUVr6PWYhq2tLQeCNczW1lZ2BKI6szFuI4Z2GCo7hlbR6/M0iIhqK7c4Fy7zXHB9\n4nXYmuvfjyGep0FEVId2JuzEC64v6GXBeBYsGkREVeCuqaqxaBARPSKvJA/7r+5H//Y8C/xRLBpE\nRI/YlbALnVw6wc7cTnYUrcOiQUT0CO6aqh6LBhHRQ/JL8rE3aS93TVWDRYOI6CG7E3cj2DkY9hb2\nsqNoJRYNIqKHbIzbiCEdeK2p6rBoEBH9Ibc4F3sS92Cwx2DZUbQWiwYR0R+2Xt6Kbi27oYlFE9lR\ntBaLBhHRH366+BPe8HpDdgytxqJBRATgdv5tHE8+zsug14BFg4gIwIZLG9D3ub6wNLGUHUWr6fWl\n0YmInqS8vBz/+td8HDhwHLGBRzBv4NeyI2k9XhqdiBqs0aPHY8OGOBSYDgLe+gwu610Rd/F3WFlZ\nyY5W73hpdCKip1BUVIRVq5ahoGAH4JUHXBqN+/daYN++fbKjaTUWDSJqkP73K9sI8FkDXHgDgAnK\ny8tlxtJ6LBpE1CCZm5sjPHwITFu+AhhnweDWXpibX0LPnj1lR9NqLBpE1GCtXfsDfN4sg9MdMwzo\nfw2nTkXzPvc14NFTRNRgGZsYI80+Bfsm7oaXg5fsODqBPQ0iarAO3zgMWzNbFoynILVojBkzBo6O\njvD29q5yulKphI2NDfz9/eHv748ZM2ZoOCER6bM1F9bgDW9eNuRpSN09NXr0aLz//vsYOXJktW26\nd++O7du3azAVETUEBaUF2BS3CRfGX5AdRadI7Wl07dq1xkEnnrRHRPVhS/wWPO/8PJytnWVH0Sla\nPaahUChw7NgxeHp6IiwsDHFxcbIjEZGeWB67HKP9RsuOoXO0+uipgIAAJCcnw9jYGCtWrEB4eDgS\nExOrbBsVFaX6OzQ0FKGhoZoJSUQ65+b9mziTdgb9hzWc+4ArlUoolcpnno/0a09dv34d/fr1w4UL\nT96vKISAvb09EhISYGdnV2karz1FRE/ji0NfIC0vDd/2+VZ2FGn08tpTGRkZqoXasWMHzM3NHysY\nRERPQwiB5bHLEekXKTuKTpK6e2rYsGE4dOgQMjMz4erqiunTp6O0tBQAMG7cOGzatAlLliyBkZER\nfHx8sG3bNplxiUgPHL55GGZGZghqHiQ7ik6SvnuqLnD3FBGpa8y2MejQtAMmd54sO4pUerl7ioio\nLuWV5GHL5S0Y7jNcdhSdxaJBRA3G5rjN6NKiC5waOcmOorNYNIiowVh2bhkifSNlx9BpLBpE1CBc\nvXcVl+5cQr92/WRH0WksGkTUICw7uwzDvIbBxNBEdhSdptVnhBMR1YXS8lL8cPYH7B2xV3YUncee\nBhHpvV/++wvc7Nx434w6wKJBRHpv6emlGNdxnOwYeoFFg4j0WlJWEs6kncGQDkNkR9ELLBpEpNf+\nc+Y/GOkzEmZGZrKj6AUOhBOR3iopL8Gyc8sQHRktO4reYE+DiPTWlvgt8HLwQjv7drKj6A0WDSLS\nWxwAr3ssGkSkly5nXkb8nXgMaD9AdhS9wqJBRHrpu9PfYbTfaJ4BXsc4EE5EeqewtBArY1fi5Nsn\nZUfRO+xpEJHe2XBpAwKbB6KNbRvZUfQOiwYR6RUhBOafmI8Pgj+QHUUvsWgQkV45cvMI8kvz8ar7\nq7Kj6CUWDSLSK/NPzMcHz38AAwU3b/WB3yoR6Y3r2ddx8PpBjPIbJTuK3mLRICK9sfjkYkT6RqKR\nSSPZUfQWD7klIr2QV5KHZeeW4dTbp2RH0WvsaRCRXlgZuxLdWnZDa9vWsqPoNRYNItJ5FaICC04s\nwMTgibKj6D0WDSLSeXuT9sLc2BzdWnaTHUXvsWgQkc77JuYbTAyeCIVCITuK3mPRICKdFn8nHufS\nzyHCK0J2lAZBWtEYM2YMHB0d4e3tXW2bzz77DD4+PggJCcHly5c1mI6IdMVXx77Ce8+/x9u5aoi0\nojF69Gjs2bOn2um7du1CbGwszp8/j/nz5yMyMlJz4YhIJyTfT8a2K9swIWiC7CgNRo1FY8GCBbh3\n716df3DXrl1ha2tb7fTt27dj1KgHZ3UGBwcjOzsbGRkZdZ6DiHTXvJh5GO03Grbm1W9LqG7VWDQy\nMjIQFBSE1157DXv27IEQQhO5kJqaCldXV9VzFxcXpKSkaOSziUj73S24i+XnluPDkA9lR2lQajwj\nfObMmfjiiy+wd+9eLF++HO+99x5ee+01jB07Fm5ubvUa7tEC9aQjI6KiolR/h4aGIjQ0tJ5SEZE2\nWHxqMQZ5DIKztbPsKDpBqVRCqVQ+83zUuoyIgYEBnJyc4OjoCENDQ9y7dw/9+/dH//79MXPmzGcO\nURVnZ2ckJyernqekpMDZufp/HA8XDSLSb/kl+Vh0chEOjz4sO4rOePTH9PTp02s1nxp3T82fPx8d\nO3bEJ598ghdeeAEXL17EkiVLcP78eWzevLlWH6qO8PBwrFy5EgAQExODxo0bw9HRsd4+j4h0xw9n\nf0C3lt3Qzr6d7CgNTo09jaysLPz8889o2bJlpdcNDAzw888/1/qDhw0bhkOHDiEzMxOurq6YPn06\nSktLAQDjxo1DWFgYoqOj4e3tDUtLSyxbtqzWn0VE+qO0vBT/Ov4vbBq6SXaUBkkhNDWyXY8UCoXG\nBuiJSK6VsSuxMnYl9o/cLzuKTqvtdpOXRicinVEhKvDl0S8x/9X5sqM0WLyMCBHpjJ/jf4aFsQVe\nav2S7CgNFnsaRKQTKkQFopRR+Gevf/LChBKxp0FEOmHjpY1oZNIIvd17y47SoLGnQURar7yiHFGH\nojD/1fnsZUjGngYRab11F9ehiXkT9GrTS3aUBo89DSLSamUVZZh+aDqW9FnCXoYWYE+DiLTaTxd+\nQjOrZnix9YuyoxDY0yAiLVZaXop/HPoHfgj/gb0MLcGeBhFprVXnV6Fl45bo3qq77Cj0B/Y0iEgr\nFZcV44voL7Bq4CrZUegh7GkQkVZa8vsSdGjaAV1adJEdhR7CngYRaZ3somzMOjwLB0cdlB2FHsGe\nBhFpFSEEPt/zOV5t/So8HTxlx6FHsKdBRFojJycHPQb2wZmgozD6zhzYbobly5fCwIC/b7UF/08Q\nkdZ4//0pOGd3Czj5N5TdS8fmzfFYvHiJ7Fj0EBYNItIaBy8fQkXL+8DRKQCsUFAwEkeOnJYdix7C\nokFEWkEIgfwXMqGIfgEosQIgYGp6EM8917LG95LmcEyDiLTCnsQ9sG1hDcObsSi27gEhctCqlQmm\nTPlOdjR6CO8RTkTSlZaXwv/f/pj54kz0aN4Dx44dg4mJCbp06QITExPZ8fRSbbebLBpEJN03Md9g\nV8Iu/Dr8V15jSkNYNHR/MYgapLTcNPgs9cGR0UfQzr6d7DgNRm23mxwIJyKpPtn/Ccb6j2XB0BEc\nCCciaaJvREN5XYn4CfGyo5Ca2NMgIinKKsrw3q738PXLX6ORSSPZcUhNLBpEJMXik4vhYOmAIR2G\nyI5CT4G7p4hI49Lz0jHj8AxER0bzaCkdw54GEWncx/s+xhi/MfBo6iE7Cj0lqUUjOjoaAQEB8PHx\nwcKFCx+brlQqYWNjA39/f/j7+2PGjBkSUhJRXdqdsBtHbh7B1O5TZUehWpC2e6q8vBxjxozB/v37\n4ezsjKCgIPTs2RMeHpV/eXTv3h3bt2+XlJKI6lJOcQ7G/TIOP/b/kYPfOkpaT+PkyZNwd3dHq1at\nYGxsjIiICGzbtu2xdjxpj0h/TNk3Ba+4vYKebXrKjkK1JK1opKamwtXVVfXcxcUFqampldooFAoc\nO3YMnp6eCAsLQ1xcnKZjElEdUV5X4peEXzD35bmyo9AzkLZ7Sp0jJgICApCcnAxjY2OsWLEC4eHh\nSExMrLJtVFSU6u/Q0FCEhobWUVIielb5Jfl4a/tbWNJnCWzMbGTHaZCUSiWUSuUzz0fatadiYmIQ\nFRWFPXv2AABmz54NAwMDTJkypcr2QgjY29sjISEBdnZ2labx2lNE2u2jXz/C7fzbWD1otewo9Aed\nu/ZUYGAgEhIScP36dZSUlGD9+vUIDw+v1CYjI0O1UDt27IC5ufljBYOItFtMSgzWXVyH+a/Olx2F\n6oC03VNGRkb48ccfMXDgQJSVleHtt9+Gh4cH/v3vfwMAxo0bh02bNmHJkiUwMjKCj49PlQPlRKS9\n8kryMHLLSCzovQBNLJrIjkN1gJdGJ6J6M3bbWAgI/Nj/R9lR6BG13W7yMiJEVC82XNqAwzcP48y4\nM7KjUB1i0SCiOncj+wbe2/Uedr25iyfx6Rlee4qI6lRZRRmGbxmOyZ0nI7B5oOw4VMdYNIioTs06\nPAsmhiaY3Hmy7ChUD7h7iojqzNGbR/HtqW9x+p3TMFDwN6k+4v9VIqoT6XnpiNgcge/Dv4eztbPs\nOFRPWDSI6JmVlJdg6MahGOs/Fn2f6ys7DtUjnqdBRM/s/V3v4/r969gWsY27pXQEz9MgIilWnFuB\nX5N+xcm3T7JgNAAsGkRUa6dvncbkfZOhHKVEY7PGsuOQBvBnARHVyp38Oxi8YTCW9FkCTwdP2XFI\nQ1g0iOipFZYWYsD6AXjD+w0M6TBEdhzSIA6EE9FTKa8ox2ubXoOpoSlWD1rNcQwdxYFwIqp3Qgh8\n9OtHyCrMwp4397BgNEAsGkSktnkx83Dg2gEcGXMEpkamsuOQBCwaRKSWjZc2Yl7MPBwdc5RHSjVg\nLBpEVKOD1w5iwq4J2DdiH1rYtJAdhyTiDkmiBuLUqVPw9++G5s3bYfjwd5CXl6fW+w5dP4TXN72O\nDUM3wNfJt55Tkrbj0VNEDcDNmzfh6RmIvLyvAQTA1HQmevQoxu7dm574viM3j2DQ+kFYN2QdXmz9\nombCkkbw6Ckiqta+ffsgxMsAhgMAiot/wL591igrK4ORUdWbgePJxzFo/SCsGbSGBYNUuHuKqAGw\ntLSEQpEB4M9flrdhaGgCQ0PDKtufSDmB/uv6Y+XAlejl1ktjOUn7sWgQNQDh4eFo1iwTpqZvApgL\nC4te+Pvf/w6FQvFY26M3jyJ8XTiWD1iOV91f1XxY0moc0yBqIHJzc7F48bdITk5Hr17dMWDAgMfa\nbL+yHW9tfwurBq7CK+6vSEhJmlLb7SaLBhEBAL4/8z2mHpyK7RHbEeQcJDsO1TMOhBNRrQghMCN6\nBpadW4boyGi0bdJWdiTSYiwaRA1YWUUZJu6eiGMpx3Bs7DE4NXKSHYm0HIsGUQOVWZCJ1ze9DiMD\nIxyKPARrU2vZkUgH8OgpogboTNoZBH4XiOebP49db+xiwSC1SS0a0dHRCAgIgI+PDxYuXFhlm88+\n+ww+Pj4ICQnB5cuXNZyQSP+sjF2JV1a/grkvz8XsnrNhaFD1uRpEVZG2e6q8vBxjxozB/v374ezs\njKCgIPTs2RMeHh6qNrt27UJsbCzOnz+PEydOIDIyEjExMbIiE+m0orIifLz3Y/ya9CuUo5S8RSvV\nirSexsmTJ+Hu7o5WrVrB2NgYERER2LZtW6U227dvx6hRowAAwcHByM7ORkZGhoy4RDrtbNpZBH4X\niPT8dJx8+yQLBtWatKKRmpoKV1dX1XMXFxekpqbW2CYlJUVjGYl0XVlFGWYdnoWXV7+MT7t8ig1D\nNvBeGPRMpO2equryBVV59OQTdd9H1NAlZiVi5JaRMDMyw+l3TvM+GFQnpBUNZ2dnJCcnq54nJyfD\nxcXliW1SUlLg7Oxc5fyioqJUf4eGhiI0NLRO8xLpiqKyInx19Ct8c+IbTO02FR8Ef8B7eROUSiWU\nSuUzz0faZUTKysrQrl07HDhwAM2bN8fzzz+PtWvXPjYQvmjRIuzatQsxMTGYNGlSlQPhvIwI0QM7\n/7sTE/dMhI+jD75+5Wu0atxKdiTSUjp3GREjIyP8+OOPGDhwIMrKyvD222/Dw8MD//73vwEA48aN\nQ1hYGKKjo+Ht7Q1LS0ssW7ZMVlytVlhaiDsFd3An/w5yinNQVFaEwrJCFJYWoqisCAIChgpDGBoY\nwlBhCCMDI1gYW8DK1ApWJlawMrWCtak1mpg3gbGhsezFoVpIykrCpF8n4UrmFSwOW8yLDVK94QUL\ndUBBaQHi78QjMSsRSfeSkJSVhMR7iUjJScHt/NsoLiuGg6UDmlo2hY2pDcyMzGBubA5zI3OYGZlB\nAQXKRfmDR0U5yirKkF+aj7ySPOQW5yK3JBc5xTnIKsyCtak1mlo0hYOlAxwbOcLFygUtbFrA1cYV\nLWxaoIVNCzhaOjbIsaW7d+9i3rwFSEvLRN++PTFw4EDZkXAj+wZmHp6JzfGbMbnTZHzU6SOYGpnK\njkU6gFe51f3FAAAUlxXjdNpp/H7rd5xOO43Tt07j6r2raNukLdzt3OFu6w43Oze42bqhhU0LOFg6\nwNrUuk424hWiAlmFWbiTfwe3828jPS8dyTnJSL6fjOScZNy8fxM37t9AYWmhKoO7nTva2rVFe/v2\naG/fHk191tqXAAAPGUlEQVQtm9bBt6B97t+/Dy+v55GR0Q2lpV6wsFiE6dMnYPLkSVLyJN9PxqzD\ns7AhbgP+0vEv+KjTR2hi0URKFtJNLBo6uhgVogLn0s9h/9X9OHDtAI4lH0O7Ju0Q2DwQHZt1RMfm\nHeHl4AUTQxPZUVXuF93/X48nKxEJWQm4nHkZ8ZnxMFQYor19e3Ro2gFeDl6qh4Olg+zYz+T777/H\nxIk7UVCw5Y9XrsDS8gXk5WUCACoqKvCPf8zGqlWbYWlpgX/+8//w6qt1fwOj8xnnsejkImyO34y3\nA97G5M6TYW9hX+efQ/pP58Y06MEF49ovevDrvGfrnhgfOB7rh6zX+uPobcxsENAsAAHNAiq9LoTA\n7fzbiM+MR9ydOFy8fRGb4jbhwu0LMDYwhrejN3wcfODj6ANfJ190aNoBZkZmkpbi6RQWFqKi4uFe\nVFOUlBSqnk2bNhNff70TBQXfAkjD4MGjcODANoSEhDzzZ5eWl2Lr5a1YdGoRErMS8ZeOf0H8hHid\nL8Skm9jTkCwtNw3NrJrJjlGvhBC4lXsLF29fxPmM84jNiMX5jPNIyEpA68at4evkCx+HB4XE19EX\nza2aa92YSVJSEnx9Q5CfPw+AJ8zNp6F/f3usXfsjAMDFpQNSU9cA8P/jHTMwceJ9fPPNV7X6PCEE\nLty+gPUX12NF7Aq427ljQtAEDGg/gAcrUJ1gT0NH6XvBAB7843S2doaztXOlo3pKyksQfydeVUjm\nxcxDbHosKkTFg96Ioy98HB/0TDo07QBzY/Mnfs6qVWswbdpXKCkpwTvvjMD//d8UGBjUzfkJbm5u\nOHDgF0yY8Cnu3MlEWFhPzJs3WzXdzMwMwF3Vc0PDu7CwaPTUn3Ml8wrWX1qPdRfXIb80HxGeEdj9\n5m54O3rXxWIQPTP2NEirCCGQkZ+B2PQHvZHzt88jNj0WCVkJcLV2hbejN7yaPhgn8WjqgbZ2bWFq\nZIpdu3ZhyJBxKCycD6AFLCz+gqlTh+HTT/+qkdwbNmzE6NGTUFAwGQYGabCyWoXz50+gRYsnn4Wd\nXZQN5XUl9iXtw/5r+5FbnIuBzw1E5qEcpJ7IgrfXc5gzJwo2NjYaWQ5qODgQrvuLQU9QWl6KhKwE\nXMi4gIu3L+LinYuIvxOPG/dvoIVNC9y+dBfZifeBu2ZAlg2Q9TE8XNch7tJxjWU8cOAAfvrpZ1hb\nW2LSpAlo2bJlpekVogIJdxNUR8cdTzmOi7cvopNLJ/Rq0wu93HrB28Eb3br2xpkzdigqGgZT0x1o\n2/Yizpw5DGNj7paiusOiofuLQbVQUl6CHUd34LUJkaiwewuwuwfYHQHsrsHADOjQvANa2rREC5sW\nqv+6WLvAsZEjHC0d6+xw5T8JIZBbkotr966pzqtJzErElbtXcC79HOzM7dCxWUcENg/E887Po7Nr\n50oHAyQmJsLXNxQFBdfxYO+xQKNGXvjtt+UICgqqs5xEHNOgBsnE0AT3E+/DNGkACi/O++NVAcAY\nG3ash1ug24PzS7Jv4Ob9mziddhqpuanIyMvA7fzbKCkvgYOlA+wt7GFtaq16WJlYwczIDEYGRqqH\noYEhyirKUFRWVOlxt/Cu6tyWOwV3oIACbWzbwM3ODe627vBz8sPQDkPh38y/1ofH8kcRaQsWDdJ5\nLVu2hIHB7wDyAVgCOAZLy8YY1GcQFAoF/Jz8qn1vQWkBbuffRlZhFnKKc1SP+0X3UVxejLKKMuTk\n5eDEiRMoLC5Ch/YeaNuqLcyMzFQPO3M7NLVoiqaWTdHUoiksTSxrvSxt2rSBr68Hzp4d+cfuqe1o\n2bIR/P39a34zkQZw9xTpPCEEIiPHY/PmfTA07ICyshhs3LgCYWFhzzzvzMxMeHsHIyurG0pLXWFu\n/h3Wrv0O4eHhdZC8avn5+fj883/g1KkL8PZ+Dl9+OZ0D4VTnOKah+4tBz0AIgZMnTyItLQ0BAQE1\nHrWkrtmz5yAqKgElJT/88co+tG49GVevxtbJ/Ilk4ZgGNWgKhQLBwcF1Pt/s7ByUlDxcgFoiLy+3\nzj+HSFfwzixETxAe3gcWFksBHASQCHPziRg0qH52TQkhsHLlSrzzzvv46qu5KCwsrPlNRBrG3VNE\nNdi8eTM++mga8vNzMXjwACxY8E+Ymtb95cffe++vWLZMiYKCETAzOwRPzywcP76f52dQveCYhu4v\nBjVgubm5aNLECaWlKQBsAVSgUaNAbN36FV566SXZ8UgP1Xa7yd1TRFqgqKgIBgYmAKz/eMUABgZN\nUVBQIDMW0WNYNIi0gL29PXx8/GBi8h6AC1AoFsLI6BJeeOEF2dGIKmHRINICCoUCv/76M/r1y4ez\n8+vo1Gknjh7dDzs7O9nRiCrhmAYRUQPEMQ0iIqp3LBpERKQ2Fg0iIlIbiwYREamNRYOIiNTGokFE\nRGpj0SAiIrWxaBARkdqk3E8jNzcXI0aMwNWrV+Hm5oZVq1ahUaNGj7Vr1aoVrK2tYWhoCGNjY5w8\neVJCWiIi+pOUnsYXX3yBzp074/z58wgJCcGMGTOqbKdQKKBUKnH27Fm9LRhKpVJ2hGfC/HIxv1y6\nnr82pBSN7du3Y9SoUQCAUaNGYevWrdW21ffLg+j6Pzrml4v55dL1/LUhpWhkZGTA0dERAODo6IiM\njIwq2ykUCrz44ovw9/fHf/7zH01GJCKiKtTbmEavXr2Qnp7+2OszZ86s9FyhUEChUFQ5j6NHj6JZ\ns2aIj49HWFgY2rdvj65du9ZLXiIiUoOQoF27diItLU0IIcStW7dEu3btanzPhx9+KObOnVvlNDc3\nNwGADz744IMPNR9ubm612n5LOXoqPDwcK1aswJQpU7BixQoMGDDgsTYFBQUoLy+HlZUV7ty5g127\ndmHBggVVzi8xMbG+IxMRESTdT6O6Q25v3bqFt99+Gzt37sTVq1cxaNAgAECTJk3w2muvYdy4cZqO\nSkRED9GLmzAREZFm6NwZ4bm5uRgwYAB8fHwwcOBA5OXlPdYmOTkZPXr0gKenJ0JDQ7F8+XLNB31E\ndHQ0AgIC4OPjg4ULF1bZ5rPPPoOPjw9CQkJw+fJlDSd8spryr1mzBr6+vvD19cUbb7yBixcvSkhZ\nPXW+fwA4deoUjIyM8PPPP2swXc3UyX/q1Cl06dIFvr6+CA0N1WzAJ6gpe2FhIUaNGgV/f390794d\n27Ztk5CyamPGjIGjoyO8vb2rbaPN621N+Wu13tZqJESijz/+WHz55ZdCCCHmzJkjpkyZ8libtLQ0\ncfbsWSGEEHfu3BGOjo4iLi5OozkfVlZWJtzc3MS1a9dESUmJ8PX1fSzPzp07Re/evYUQQsTExIjg\n4GAZUaukTv5jx46J7OxsIYQQy5cv17n8f7br0aOH6NOnj9i0aZOEpFVTJ/+9e/dEhw4dRHJyshDi\nwb97baBO9iVLlojx48cLIYS4fv26aNOmjaioqJAR9zHR0dHizJkzwsvLq8rp2rzeClFz/tqstzrX\n01DnxEAnJyf4+fkBAOzt7REUFIRbt25pNOfDTp48CXd3d7Rq1QrGxsaIiIh47NfUw8sVHByM7Ozs\nas9f0TR18nfq1Ak2NjYAgD59+iAlJUVG1Cqpkx8AFi5ciCFDhqBp06YSUlZPnfw//fQTBg8eDBcX\nFwAP/t1rA3Wy29jYIDc3F6WlpcjKyoKFhUW1h+FrWteuXWFra1vtdG1eb4Ga89dmvdW5oqHuiYF/\nSkxMxKVLlxASEqKJeFVKTU2Fq6ur6rmLiwtSU1NrbKMtG1518j/su+++Q//+/TURTS3qfv/btm3D\n+PHjAUBrNlqAevkTEhKQlZWFrl27wt/fH2vWrNF0zCqpk33YsGEoLy+Hvb09unTpojXZ1aHN6+3T\nUne9lXLIbU3q4sRAAMjLy0NERATmzZsHS0vLOs+pLnU3QOKRYxK0ZcP1NDkOHjyI1atX49ixY/WY\n6Omok3/SpEmYM2cOFAoFhBBadfkadfKXlpZCqVRi//79KCgoQK9evTBo0CCYm5trIGH11Mm+aNEi\nGBkZIS0tDRcuXECfPn1w48YNGBjoxm9abV1vn8bTrLdaWTT27dtX7TRHR0ekp6fDyckJaWlpcHBw\nqLJdaWkpBg8ejOHDh0v/1evs7Izk5GTV8+TkZNVuhOrapKSkwNnZWWMZn0Sd/ABw/vx5vPPOO9i9\nezcaN26syYhPpE7+06dPIyIiAgCQmZmJ3bt3w9jYGOHh4RrNWhV18ru6uqJ3795wcnICAAQGBiI6\nOhqvvPKKRrM+Sp3s0dHRGDt2LCwsLBAcHIzmzZvjv//9L9q3b6/puE9Nm9dbdT31eltnIy4a8vHH\nH4s5c+YIIYSYPXt2lQPhFRUVYsSIEeLDDz/UdLwqlZaWijZt2ohr166J4uLiGgfCjx8/rlUDaurk\nv3HjhnB3dxcxMTGSUlZPnfwPi4yMFJs3b9ZgwidTJ398fLwICgoS+fn54u7du6Jt27YiNzdXUuL/\nUSf70qVLxYQJE0R5eblISkoS7u7uktJW7dq1a2oNhGvbevunJ+WvzXqrc0UjJydH9O/fX3h7e4sB\nAwaoVozU1FQRFhYmhBDi8OHDQqFQCF9fX+Hn5yf8/PzE7t27ZcYWSqVS+Pn5CS8vLzF//nwhxIOV\nZenSpao2U6ZMEV5eXiI4OFjq0V5VqSn/2LFjhZ2dner7DgoKkhn3Mep8/3/StqIhhHr5v/32W+Hh\n4SFat24tFi9eLCvqY2rKnp2dLT744APh7+8vXn75ZbFz506ZcSuJiIgQzZo1E8bGxsLFxUX88MMP\nOrXe1pS/NustT+4jIiK16cZIExERaQUWDSIiUhuLBhERqY1Fg4iI1MaiQUREamPRICIitbFoEBGR\n2lg0iIhIbSwaRHXs1KlT8PX1RXFxMfLz8+Hl5YW4uDjZsYjqBM8IJ6oHU6dORVFREQoLC+Hq6oop\nU6bIjkRUJ1g0iOpBaWkpAgMDYW5ujuPHj+vk5bKJqsLdU0T1IDMzE/n5+cjLy0NhYaHsOER1hj0N\nonoQHh6ON954A1evXkVaWhoWLlwoOxJRndDKmzAR6bKVK1fC1NQUERERqKioQOfOnaFUKhEaGio7\nGtEzY0+DiIjUxjENIiJSG4sGERGpjUWDiIjUxqJBRERqY9EgIiK1sWgQEZHaWDSIiEhtLBpERKS2\n/wfUBSJqi93lAgAAAABJRU5ErkJggg==\n", "text": [ "" ] } ], "prompt_number": 5 }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Minimizing Expected Error" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now suppose that our goal is to minimize the expected squared error on some test data. That is, we want to find an $\\hat{f}$ that minimizes $R(\\hat{f}) = \\mathbb{E}_X[(\\hat{f}(x) - y)^2] = \\mathbb{E}_X[(\\hat{f}(x) - f^*(x) - \\epsilon)^2]$, where we're taking the expectation over the distribution of $X$.\n", "\n", "Since $\\epsilon$ is indenpendent from $x$, we can expand $R$ to obtain: $R(\\hat{f}) = \\mathbb{E}_X[(\\hat{f}(x) - f^\\ast(x))^2] + \\sigma^2$. As a result of our noisy true model, we see that no matter what we choose for $\\hat{f}$, we can never expect a loss less than $\\sigma^2$.\n", "\n", "In machine learning, we learn $\\hat{f}$ from data, usually by minimizing the _empirical risk_ on some training data. We assume our training dataset has been created for us by generating random i.i.d. samples $(x_i, y_i)$, and as a result, $\\hat{f}$ itself is also random. Thus, the quantity we're actually interested in is $\\mathbb{E}_D [\\mathbb{E}_X [(\\hat{f}(x) - f^*(x))^2]] + \\sigma^2$, taking the expected value over a distribution on training data $D$ as well.\n", "\n", "In class we saw that the first term can be decomposed into a bias and variance term. Letting $h(x) = \\mathbb{E}_D[\\hat{f}(x)]$, the function we expect to learn, we end up with\n", "\n", "$\\mathbb{E}_D [R(\\hat{f})] = \\mathbb{E}_D \\mathbb{E}_X [[(f^*(x) - h(x))^2]] + \\mathbb{E}_D \\mathbb{E}_X [[(\\hat{f}(x) - h(x))^2]] + \\sigma^2$\n", "\n", "This correspondes to a bias term, a variance term, and a noise term we cannot avoid." ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "A Biased Hypothesis Class" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's explore the case when our model of $\\hat{f}$ is not complex enough to match the true function $f^\\ast$. Specifically, we'll restrict $\\hat{f}$ to the form $\\hat{f}(x) = mx + b$ by learning only a first degree polynomial. We'll vary the size of the training set, and for each $\\hat{f}$, estimate $R(\\hat{f})$ empircally with some test data." ] }, { "cell_type": "code", "collapsed": false, "input": [ "# Some test data to empirically evaluate squared error:\n", "testData = make_data(10000)\n", "\n", "def get_mse(predictions, testData):\n", " \"\"\"Evaluates mean squared error between predictions and test labels\"\"\"\n", " yTest = testData[1]\n", " return sum((predictions - yTest) ** 2)/len(yTest)\n", "\n", "# Learn a linear model with increasing amounts of training data:\n", "N_ar = range(2, 1000)\n", "mse_ar = []\n", "for N in N_ar:\n", " # Generate N data points:\n", " trainData = make_data(N) \n", " \n", " # Perform linear regression:\n", " f_hat = polynomial_regression(trainData, order=1)\n", " \n", " # Evaluate:\n", " mse = get_mse(f_hat(testData[0]), testData)\n", " mse_ar.append(mse)\n", " \n", "plt.semilogx(N_ar, mse_ar)\n", "plt.ylim(0, 1.1*max(mse_ar))\n", "plt.xlabel('Size of Training Set')\n", "plt.ylabel('MSE')\n", "plt.title('Order-1 Polynomial Regression')\n", "plt.show()\n", "\n", "print \"Error with\", N_ar[-1], \"training samples:\", mse_ar[-1]" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "display_data", "png": "iVBORw0KGgoAAAANSUhEUgAAAY4AAAEeCAYAAACdYvI/AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XlclNXiBvBnWAQVUnBBBBSVLlKIgmuaF7LUwt3U0BbN\nm0uLt2y3201s8Wfdul1zS00Ms8ylm1qapuaEG6moqCmpCIYoiiDurHN+f5w7G8zAvDDDzMDz/Xz4\nMPNuc2ZeOM+cc95FJYQQICIispCLvQtARETOhcFBRESKMDiIiEgRBgcRESnC4CAiIkUYHEREpAiD\ng6olPj4eTz75pL2LociECRPwz3/+097FMPJ///d/mDRpkkXLOmL5rSU2NhZfffWVvYtBFmJw1EPr\n16/HfffdB19fX3Ts2BGvvvoqioqKFG1DpVJZtUyTJ09Gx44d4erqisTExEqXnTBhAjw8PODt7Q1f\nX18MGDAAf/zxR5WvoVKprF7umpoxYwaWLl1q0bKVlf/LL7+Eq6srvL29cddddyEiIgLff/+9NYtq\nU5s3b3a6LyL1GYOjnlmyZAmmTp2KWbNmITc3F1u3bsXJkyfx0EMPmV2nrKzMaq8vhICpc067dOmC\nhQsXIioqqsrKXaVS4Y033sCNGzdw7NgxuLu7Y8KECRa/vjOrrPx9+vTBjRs3cOHCBTz66KMYN24c\nrl69avUyaDQaq2+TnAuDox65efMm3nzzTcyfPx8DBgyAq6sr2rZtizVr1uCPP/7AqlWrAMhuqLFj\nx+LZZ5+Fv78/EhMTkZGRgejoaDRv3hyPPvoobt68abTt5ORk9O7dG02bNkWXLl3w66+/6ubFxMRg\n9uzZGDBgAJo0aYKMjIwKZXvuuefQr18/eHp6WvRetBVoQEAAnnjiCRw/fhwAcPLkScTExMDHxwfh\n4eH44YcfjNbThlJ4eDh+/PFH3fSSkhI0b94cqampyMzMhIuLC/773/8iLCwMLVq0wOzZs3XLFhUV\n4aWXXkJAQAACAgIwffp0FBcXAwDUajUCAwPx+eefo127drjnnnvwyy+/ICkpCd27d0fz5s3x4Ycf\n6rZVvstv9OjR8Pf3R5MmTRAdHY0TJ05Y9HkYfiZeXl6YMmUKioqKkJWVpSvzq6++irZt28LPzw/P\nPvssCgsLdet+9NFHaN26NcLCwrBmzRq4uLjg7NmzAGQLb/r06RgzZgyaNWsGtVqtC6cWLVqgXbt2\nmDdvnm5bJ06cwMiRI9GyZUu0atUKr7zyiq58L7/8Mjp27AgfHx/06NEDubm5AOTfyLJly3TLvf/+\n+wgODoafnx/Gjx+P69evA0CV+4ZqB4OjHjl69Chu3LiBkSNHGk1v3LgxYmNjjSr77777Dvfccw8y\nMjIwbtw4jBs3DlFRUbh48SJeeuklLFq0SFcJZ2dnY+DAgZg8eTKysrLw8ssvY9iwYcjLy9Ntb8GC\nBXjxxReRn5+PNm3aWO09/fnnn1ixYgWioqJQWlqKIUOGoH///sjNzcW8efPw2GOP4dSpUxXWGz9+\nPFauXKl7vnnzZgQEBKBz5866aWvWrMHPP/+Mr7/+Gv/85z913WEffPAB9uzZg9TUVKSmpmLfvn14\n//33detdvnwZJ06cwMGDBzFu3Dg8/vjjmDt3Lr799lusXbsW7733HkpKSgBU7PIbNGgQzpw5gz/+\n+ANt27bF448/rvgzuXbtGhYsWIAWLVogPDwcAPDmm2/iyJEj2Lx5M/bu3Yu0tDS8++67AIAtW7bg\n448/xo4dO3Do0CGsX7++wjaXLl2KESNG4NKlS7jvvvswZMgQBAYG4vjx41ixYgXmzJmDn3/+GQAw\nc+ZMPPDAA8jOzsbZs2fx2GOP6T7jw4cPY8+ePcjPz8fixYt1XxQMu+GWL1+OhIQEqNVqnD17Fteu\nXcMLL7xgVJ7y+yYtLU3x50Q1IKjeWL16tWjVqpXJeW+88YaIjY0VQggxc+ZM0b59e928c+fOCZVK\nJdLT03XT+vbtK5588kkhhBBz5swR/fv3N9pely5dRGJiohBCiOjoaDFx4kSLynj//ffr1jNn/Pjx\nwtPTUzRt2lS0atVKDBs2TJw9e1YkJSUJd3d3cfPmTd2yffr0EfHx8UIIISZMmCDefvttIYQQ2dnZ\nwsvLS9y4cUMIIcSjjz4q/vWvfwkhhMjIyBAqlUqkpKTothMaGipWr14thBCiffv2YvHixbp5S5cu\nFcHBwUIIIXbu3ClcXV3FlStXhBBCnD9/XqhUKrFx40bd8nfffbdQq9VCCPlZP/HEEybf5+nTp4VK\npRLXr1+vUP7yli9fLtzc3ETTpk2Fm5ub8PLyEqdOnRJCCKHRaETjxo3Fnj17dMt///33ol27dkII\nIZ5++mndvhRCiB07dhjt7/Hjx4t+/frp5icnJ4umTZuK27dv66a9+OKL4umnnxZCCDFy5Ejx6quv\nipycHKMybty4UURFRYkDBw5UKH9MTIxYtmyZEEKIfv36iRkzZujmbdu2Tbi7u4uysrIq9w3VDrY4\n6pHAwEBcuXLFZB/1xYsXjVoCPXv21D2+cOECvLy80L59e920yMhI3eNz585h165d8PHx0f2cOXMG\nOTk5AOS3ScPteXl56QZxz58/r/h9qFQqvPbaa7h69SouXryI9evXo127drhw4QL+8pe/oHHjxrpl\nu3XrhgsXLlTYRuvWrdGnTx+sW7cOBQUF2LJlS4Vv9126dNE99vf313XPXbx4EV27dtXN69q1q9Fr\n+Pv7o1mzZgAAPz8/ADBqyfj5+SE7O7tCmcrKyvDmm28iJCQETZo0Qffu3QEAV65csehz6dWrF65e\nvYo///wT0dHReOuttwAAubm5uH37NgYNGqTbPxMmTNBt9+LFi0b7Myoqymi75fffuXPncPPmTbRu\n3Vq3vYSEBFy+fBkA8Omnn+L27dsIDw9Hjx498NNPPwGQR05NnDgREydOREBAAN544w2zf4vlP9/S\n0lJcunRJN83cvqHaweCoRzp16gRvb2989913RtNv3ryJLVu24K9//atumqurq+6x9h8zPT1dN+3Q\noUO6x23atEFMTAyuXr2q+7lx4wZef/113TJubm5Gr3fjxg1cv34dgYGB1XovwsQgcevWrXHq1Cnc\nunVLN+3AgQMICAgwuQ1td9XatWvRu3dv+Pv7W/TarVu3xsGDB3XPDx48aPY1lPjmm2+wYsUKbNu2\nDdeuXcOBAwcAKB/Q9/f3R0JCArZt24Zdu3ahefPmaNiwIbZu3arbPwUFBbpxA39/fxw+fFi3vuG+\n1TL8ewgKCoK3tzcuXbqk297169d1Y0Zt2rTBggULkJubixdffBF/+9vfoNFo4Orqiueffx5Hjx7F\n3r17sXbtWl2oGDL1+bq5uelCmOyPwVGPeHt7Y/bs2Zg2bRq2bt2KkpISZGZmYsyYMbj77rsxduxY\nk+u1bdsWPXv2xPz581FSUoLdu3fjyJEjuvlPPPEE9u3bhxUrVuDq1asoLCyEWq02+lZdVeVXUlKC\nwsJCaDQaFBcXo7Cw0Ow65qb36tULQUFBmDt3LkpKSqBWq3H48GHExcWZXG/EiBE4dOgQPvvsMzz1\n1FOVls/Q2LFjkZCQgCtXruDKlStISEjAE088YfH65nh5eaFx48Zo1KgRMjMz8c477xjNVxIgLVu2\nxKRJkzB79my4uLhg0qRJeOedd3Do0CFoNBpkZ2frxiTGjBmDLVu24KeffkJmZiY+++yzSl+3Z8+e\naNeuHd566y1kZmairKwMx48f11X2K1euRG5uLkpLS+Hm5oaCggKUlJRg586dOHbsGMrKyuDi4gIX\nFxeTramxY8dizZo1yMzMxM2bN7Fw4ULExcXBxcV8daU0XKlmGBz1zNSpU7Fw4ULEx8ejZcuWGDhw\nIMLCwrB9+3bdMqbOF/jmm2+QkpKCVq1a4d///jeeffZZ3bzAwED8/PPPSEhIQIcOHdCmTRt88skn\nRv/MVR1i279/fzRq1AjJycmYPHkyGjVqhF27dplc1tz5DO7u7vjhhx/w888/o0WLFnjhhRewatUq\n/OUvfzG5nqenJ0aOHInMzMwKBwxUVt63334bvXr1QkREBCIiItCzZ0+8/fbbZtetbFuGZRo2bBj6\n9euHLl26YMiQIXjssceM1q3sPA5T81566SXs3LkTR48exYcffoiuXbti1KhRaNq0Kfr37687aODh\nhx/Gyy+/jIkTJ2LgwIEYNmwYAMDDw8Pktl1cXPDjjz/iwoUL6NWrF1q0aIHJkyfrWjBbt25FeHg4\n/Pz8sHLlSqxbtw4eHh64dOkSRo8ejaZNm2LYsGEYN26cyXM3Jk6ciAkTJuCvf/0r2rdvD29vb6Oj\ntkx9Bo52fk5dpxKMaqrH3n33XZw5cwYrVqywd1EcxqZNmzBs2DAUFxdX+i2f6i/+VVC9lZeXh0WL\nFmHy5Mn2Lordff/99ygqKsKhQ4fwr3/9C0OHDmVokFn8y6B6aenSpQgNDcXjjz+O+++/397Fsbsl\nS5agZcuW6N+/P5o1a4ZFixbZu0jkwNhVRUREirDFQUREirhVvYjj6tKlC1JTU+1dDCIip9K5c2ej\nQ+qVcuoWR2pqqu5qq/b8mTlzpt23pWQ9S5atahlz85VMt+bn5gj7zln2n9J5jrrvnHH/Ocr/Xk2/\ncDt1cDiKmJgYu29LyXqWLFvVMubmK51ub9YulzPsP6XzHHXfAc63/+rK/55TD46rVCo4cfHrvfj4\neMTHx9u7GFQN3HfOraZ1J1scZDeO/E2WKsd9V7+xxUFEVM+wxUFERLWKwUFERIowOIiISBEGBxER\nKcLgICIiRRgcRESkCIODiIgUYXAQEZEiDA4iIlKEwUFERIowOIiISBEGBxERKcLgICIiRRgc9Ux+\nPrB7t71LQUTOjMFRz2zaBLz1lr1LQUTOjMFRz5w5A2Rn27sUROTMGBz1zJkzwPnzAO9/RUTVxeCo\nZ9LTgeJi4MoVe5eEiJwVg6OeOXMG8PNjdxURVR+Dox4pKACKioDISNldRURUHQyOeiQ9HQgJAQID\n2eIgoupjcNQjZ87og4MtDiKqLgZHPZKeDnToAAQEMDiIqPoYHPWIYYuDXVVEVF0MjnrkzBm2OIio\n5mwaHElJSYiKikJERATmzZtXYf7XX3+Nzp07o3Pnzhg3bhyOHz9u8bqkXF0dHC8tBd59196lIKo/\nVELY5hzisrIyhIaGYvv27QgICED37t2xatUqhIWF6ZbZt28f7rnnHjRp0gSJiYlYtGgRkpOTLVoX\nAFQqFWxU/Drn9m2gWTPg1i1ApQK8vICLF4G77rJ3yWouJwfw95eHGjdoYO/SEDm+mtadNmtx7N+/\nHyEhIQgODoa7uzvi4uKwYcMGo2Xuu+8+NGnSBAAwaNAgnP9f/4kl65IyZ88C7doBLi4yOAIC6k6r\n4+pV+fvyZfuWg6i+sFlwZGdnIygoSPc8MDAQ2ZXUVEuWLMGwYcOqtS5VTTswrlWXuqsKCuTvnBz7\nloOovnCz1YZVKpXFy+7cuRMrV67E3r17Fa9LltEOjGvVpQFybYuDwUFUO2wWHAEBAcjKytI9z8rK\nQmBgYIXljh49ismTJ+Onn35C06ZNFa0LAPHx8brHMTExiImJsc4bqGPS04HwcP1ztjiI6g+1Wg21\nWm29DQobKSkpEe3btxcZGRmiqKhIdO7cWZw4ccJomXPnzomQkBCRnJyseN3/Derbqvh1zkMPCbFl\ni/75/PlCTJ1qv/JY04IFQgBCvPeevUtC5BxqWnfarMXh5uaGhIQEjBgxAqWlpZg0aRLCwsKwePFi\nAMCUKVPw7rvvIj8/H1OnTgUAuLu7Y//+/WbXpeoz1VW1ZYv9ymNNV6/Ko8TY4iCqHTY7HLc28HBc\nyxQXy8Nub9wA3N3ltIMHgcmTgUOH7Fs2revXgYcfBjZvBv7XY2mx114D1GqgbVtg3TqbFI+oTnHY\nw3HJcWRmyhaGNjQAxxscz8oC9u0D3nlH+bpXrwIdO7LFQVRbGBz1gPaMcUMtW+rvz+EILl0CIiKA\n1auB1FRl6xYUAGFhDA6i2sLgqAfKj28AgKurPNv6wgX7lKm8y5dlq+Hdd4EXXlB2T3S2OIhqF4Oj\nHih/8p+WI3VXXbokb2n7zDPAnTvAypWWr1tQALRpA2g0wM2btisjEUkMjnrAVFcV4Fjncly+LLvP\nXF2BBQuAN94Arl2zbN2rVwEfH6BVK7Y6iGoDg6MeMNVVBThmiwMAevYEHnkEMDi3s1IFBQwOotrE\n4KjjysqAc+eA9u0rznPEFofWnDlAYmLVQaDRyEN577qLwUFUWxgcddz58/Jy6g0bVpznSPceN2xx\nAECLFvK8jKqC7cYNoFEjwM2NwUFUWxgcdZy5gXHAsbqqyrc4ANn9pL2AoTnabiqAwUFUWxgcdZy5\ngXHAcbqqhKjY4gAsC46rV/VnmjM4iGoHg6OOMzcwDgCtW8uKtqysdstUnvauhI0bG0/39QXy8ytf\nly0OotrH4KjjKuuqatBAVrr2vnOeqdYGwBYHkaNicNRx6enmWxyAYwyQmxrfADjGQeSoGBx1mBBV\nB4cjDJBbq8Xh5ydDSKOxfhmJSI/BUYdduiQPVW3SxPwyjjBAbq0Wh4eHvC9HVeMiRFQzDI46rLKB\ncS1H6Koy1+KwZHDcsMUBsLuKqDYwOOqwygbGtQIC7N/iuHSpZi0OBgdR7WJw1GFVjW8AjtHiuHy5\nZmMc2q4qgMFBVBsYHHWYpS0OewcHWxxEzoXBUYdVdta4lraryp63bjfX4mjSRF6LqrITFA0HxwEG\nB1FtYHDUYZYMjnt7yxMBq/pmb0vmBsddXeVVbwsKzK/LwXGi2sfgqKPy8+U39ebNq17WngPkxcXy\nrn2GrQZDVXVXscVBVPsYHHWUdmBcpap6WXsOkOfmynBzMfOXWFlwFBcDJSXyXBUtBgeR7TE46ihL\nBsa17DlAbu7kPy1fX/PBoR0YNwxHBgeR7TE46iglwWHPs8fNjW9o+fiYPwmw/PgGIG9ade2abI0Q\nkW0wOGro8GHg9m17l6IiS87h0LJnV1VVLY7KuqrKH4oLyAF1Pz/g4kXrlZGIjDE4auiLL4CHHgLy\n8uxdEmNKu6ocucVhLjjKn/yn1batvM86EdkGg6OG5s0D7r8f6NsXyMqyd2n06kqLw5IxjvKCg4HM\nTGuUjohMYXDUkIsL8NFHwKRJQJ8+wO+/27tE8vDWa9fkHf4sYc/B8ZqOcZhqcTA4iGyLwWEl06cD\nc+YA/foBu3fbtyzp6UD79uYPcS2vWTPgzh15C9faZu0xDqDudFX9+9+O1wVKBDA4rGrcOGDlSmDk\nSGD9evuVQ0k3FSAPZ7XXkVU1GeMof/KfVl1pcSxfDpw6Ze9SEFXE4LCy/v2Bn34CnnsOWLLEPmVQ\nMjCuZa8B8pq0OEwdjgvI4KgLLY7CQtkSJHI0bvYuQF3UtSuQlAQMHCgPC33nHcvO4LaW9HSgc2dl\n69hjgFyjkWeOVzU4bm6Mw1yLo00beaBCWZk8PNdZ3bnjmId6E7HFYSMhIcDevcDGjcCzz1Z+hVdr\nq26Lo7aDo6AAaNxYXmTRnOq0ODw9ZeA4+7kcbHGQo2Jw2JCfH6BWy4p89GhZEdSG6gSHPcY4qhrf\nAOTVe+/ckdekKs/c4DhQN7qrGBzkqBgcNubtDWzaBHh4AAMGVH6JcGsoKpLXamrTRtl69uiqqmp8\nA5BHhjVpYvpzM3c4LiCPrHL2AXIGBzkqBkct8PAAvv5ajn307Wvbb/YZGTI03BSOXtmyq2rwYODY\nsYrTLWlxAOZPAqyqxeGMwaHRABMmyBZWWRmDgxwTg6OWuLjI4/KffFKeKHjypG1ex5KbN5liq66q\n/Hxg82bgm28qzrOkxQGYPglQiLrZVVVQACQmAtevy+cMDnJENg2OpKQkREVFISIiAvPmzaswPy0t\nDffddx88PT3xySefGM0LDg5GREQEIiMj0aNHD1sWs9aoVMDrrwPvvgs88ACwb5/1X8OS28Wa4ucH\nXLlieiyhJpKSZCitXVvx9rSWtjhMDZDfvCkHwd3dTa/jrF1V2hP+tEHJ4CBHZLPgKCsrw8SJE/Hf\n//4XKSkpWLZsGU6W+5rdrFkzzJs3D6+++mqF9VUqFdRqNQ4fPoz9+/fbqph28dRT8uSuoUOBH3+0\n7rarMzAOyK4tW1xVVq2WR5VpNEBqqvE8JS2O8sFR2fgG4LwtDm1waH8zOMgR2Sw49u/fj5CQEAQH\nB8Pd3R1xcXHYsGGD0TItWrRAt27d4G7ma6Mo/xW1DnnkERkazzwjQ8RalJ41bsgWA+RqtWxdjRoF\nrFtnPK8mYxyVdVMBcpzn3DkZWM6kfHDwPA5yRDYLjuzsbAQFBemeBwYGIltBJ7pKpUK/fv0QGRmJ\npUuX2qKIdtezJ/Drr7Lravbsil051VHdFgdg/QHy/Hzg7Fl5UMCoURW7q2oyxmHu5D+txo2Bu+6S\n4WSJ3buBGzcsW9aW2FVFzsBmwaGq4anSe/bsQWpqKr755hvMnj0bu3btslLJHEtoKLBnD7B6NfD3\nv9fsRMHSUvktu1276q1v7QHypCSgd285DtG9uzy89Phx/fyajHGYO/nPkKXdVdevyyO/tm2rellb\nu3JF/mZXFTkym11yJCAgAFkGN6jIyspCYGCgxev7+/sDAMLCwjBixAjs378fffv2rbBcfHy87nFM\nTAxiYmKqXWZ7ad1aVrLDh8sLJX71VeVnU5uTlSUrYk/P6pXD2l1VajWg3R0qlb67qlMnOU1Ji6P8\n5eotCQ7tAHmvXpUvt3ixvAx9RkbVZbE1tjjIFtRqNdRqtdW2Z7Pg6NatG06fPo3MzEy0bt0aq1ev\nxqpVq0wuW34s4/bt2ygrK4O3tzdyc3OxefNmfPbZZybXNQwOZ9akibw44mOPyZ/Vq5WHR3UPxdUK\nCABSUqq/fnlqNfD55/rno0YBf/sbMGuW7LsvLZUnSFbF1BhHerpsUVTGkhZHURHwn/8AEyfKbjV7\nY3CQLZT/Uj1r1qwabc9mXVVubm5ISEjAiBEj0LVrV0ycOBFhYWFYvHgxFi9eDADIyclBUFAQPv30\nU7z//vto06YNbt68iZycHPTt2xddunRBXFwcpk+fjgEDBtiqqA7D01M/DjB6NFBcrGz96h6Kq2XN\nFofh+IZWz55yHOHECX1rw5IeTVNjHMeO6Vsu5lhyEuDKlXI7I0aYbnGkpcmgqy15efIIt7w8/eVW\niByNTa+OGx0djcOHDxtNmzJliu5xq1atjLqztLy8vHDkyBFbFs1hNWgArFkDxMXpB5Q9PCxbtyYD\n44B1B8cNxze0XFyARx+V3VUDB1o2vgGYHuM4elTeOKsybdtWfrizRgP861/AwoVAq1amWxz79snW\n38yZlpW1pvLy5H7Iz5ctLQYHOSKeOe6AGjSQlZW7u6xoi4osW88aXVUXL1rnEFbtYbjlacPQ0oFx\noGJw3Lghr8dVVUhW1VV1/Lg8GOGBB/TLln/vmZnyp7aODM/LA4KCZHD4+DA4yDExOByUuzvw7bey\n+2rkSMuurFvTripPT3kIa25u9behZTgwbqh3b1k5JiVZNjAOVAyO338HwsKqvh6XdnDcXKV/9CgQ\nFSW7yxo1koPt5U+AzMiQlbelh/XW1JUr8hyUvDz5vnkeBzkiBocDc3cHVq2S5yRUFR4aTc1O/tOy\nxp0A8/JkhRsVVXGetrtq+XLLWxxeXnK8R9vysmR8A5BjBD4+5lsdqanGN7xq375id1VmpixzZWMl\nxcXA/PlVl6cqQsjPzjA42OIgR8TgcHDu7vICgXfdJQ/XNRceFy/KitKSo5QqY40BclPjG4ZGjZJd\nMZa2OFQq41aHpcEByPA6dMj0vNRUICJC/9xUcGRkAN266QfO79zRH/mkdfIkMG1azS9cefu2fK/N\nm8tzS+pjcFy9annXLNkPg8MJuLnJo398fIBhw0xXJjXtptKyxgC5uW4qrfvvl60NS1scgHFwHD1q\nXOFXprLgOHrUuMXRrp1xcBQXy6O/+vbVB8eSJcATTxhvR7tOYqJlZbp8GdiypeL0vDygWTPZbQZY\nd3D8k0+AuXP1z5VexyspqXbOc/H1ldc2I8fG4HASbm7yxMDmzeXFEcv3fdd0YFzLGmePVxUcrq7y\n/I7oaMu3qQ0OIazT4rh0SQaD4Tmp7dsbV45//ilPzgwJ0U8/eBDYvt241XH2LNC/P7BihTw3pSrb\ntgHvvVdx+oULgL+/7JoEZCuztNQ6tx0+cwb44w/5+M4d4C9/UXa4d3S0vDhnbXCEEzGpcgwOJ+Lm\nJiunVq0qhoe1Whw17aqqbHzD0PDhslK2lPYkwIsX5ZiDpa2VqCh5UmP5AXJtN5XheSTlu6oyM2Ur\npF07/RjH4cMyoL//Xr/c2bPykiVBQZZdtiQry3Q4Z2TI19K2OBo2lAcsWOOWw3l5+gH+ggIZGhcu\nKNtGDa8iRHUIg8PJuLoCX34pK90hQ/ThYa0WR00Hx5OS5I2qzI1vVJf2JEBta8PSSiwwUB44UP5o\nqfLdVEDF4MjIkIfptmsnH9++Lee/8448XFrr7Fm5blwcsHFj1WXKypKVtqlDf4OD9S0OT08ZHtbo\nrjIMDu1NokycQlUpWwRHairwyy/G0+rwRbHrDAaHE3J1lUclBQXJb7q3btX85D+tmrY4quqmqi5t\nV9WxY5aPbwCysjPVXVX+iCpAhnF+vr6i1rYA2rSRleyRI/KilMOHAwcOyLEKQB8cnTtXvKaWKVlZ\n8oZZ5Q971gaHtsVh7eDIyZGPr13Tl0MJlxrWFuvXy/1heBmaYcOABx9ka8bZMDiclKsrsGyZPFdh\n0CDrBYd2cLy63/psHRxHj1o+vqFlLjjKB5CLi/GdA7VdVZ6ecmxp0yYgMlJW7I88IrurysrkQHNw\nMHDvvTI4qvrssrJkt2P5lp329Qy7qho2NH0ux6uvym4zQJbh1KnKX9NUi8PcF4Tly+V7La+mlfuv\nv8rf77+vn2aqG+7XX+VlachxMTicmDY8OnSQlZ6vb823edddsoLQVi5K5OXJys/w+lTWoh3jUDIw\nrhUZaRwCwIM0AAAYyElEQVQcRUXA6dOyoi/PsLtK21UFyAr9v//Vj90MGwb88IPscvL1lZW99tpb\nVZ0smJUly2QqOMp3VTVqVLHFIQSwdKm8CVhZmQzr/v0rf828PLmdW7fMtzheflkus2EDYOouBoYt\njrw8y8ZeCgvlZ12+/NqBesNtGN7nzfAWPJs26VtL1SVE5YFeUmLZgQ3Z2Y5x3xZ7Y3A4ORcX+U+2\nf791mvsqVfW7q7TjG1Wd0V0dPj6ya+ePP0xX+JUp3+JIS5NB0LBhxWUNg0PbAgDk77Q0WeED8lpb\nSUmyhdG+vZymUulbHenpxuMgWrdvy/uld+liHBwajWy5tG1bdVfV+fP6UPn6a9kK+/NP8/vszh0Z\nMIGBMtSuXZMtS8PLyGk0wGefyUo+Lc14TMhUhdu8ORAbC7z0kunX1JZz1ix5BJf28wFk2HbsKB8b\nBsfw4aa3M3iw8YUmf//d8gMGrlyRBwIMGFB5uMbEAP36Vb29wMDaO7rMkTE46gAXF+Duu623veoM\nkO/YAUyfLs8KtwUfHxmOrVvrv5Fbqn17WVlqb5JkqptKKyZGXvTw0iXZwvnfbWEQHCwrPu24iI+P\nrPyXLdMHB6APjgULZHdS+Ur3/HlZ+ZQP55wceWn9Ro2Mg8PHRx4Ka3hHgt9/B8LDZZdPfLwMAFdX\nYNEi/UmIycnAc8/Jx9rzQ4KCZDhpb1x17Jj+qsN5eTJcTp+WoacNjowMGSiA3Mfduunf086d8tyQ\nkhLTn2VQUOUXokxJMX+yX/kvQYatnfBwfZnMCQ2V58q0aAHMmCEPoTYchE9ONj4ybu/eiq2s//xH\n7t/yrHFJHiVUKse4yZghBgdVoKTFcf06MHUqMGGCrLj+9jfblMnHR47jKBkY13JxkS2Fw4dlpffz\nzxUHxrVGj5YV9eDBclBcW2G1ayfD2ctLv+ygQbLyMRUc69fLw14N73gIyO6hoKCK4Xz2rL5bzLCr\nau1aeZ+WGTP0FZY2OKKj5WHJq1fLI+xmz5Zh0qcP8PrrsitNCBkuRUXyPR85IkO0ZUt5IubOnXKb\n2u61X36R62gP1R02zLhVkZJS8UtFairwwQeygtNWtD/9ZLyMSiW7yQx161b+09dbsUK2prQSE4Hf\nfpM/gHw/5gILkGM+O3bIx9pK19VVP/+pp+RlfFQq+X4Ng0n7/qZPl92BKpXsxtMeDHHwoH7Zkyer\nvuz+nj36rjlA/l2Uv/pAVY4dU7a8zQkn5uTFd1hvvSXEqFFCHDggRHGx+eV+/lmItm2FeOYZIQoK\nbFumY8dkL/U771Rv/enThfjgAyGmThUiKkqI3FzzyxYWCtGrlxD9++unpacLsXSp6TKtWKGftnOn\nEC1bCtGunRDPPy/E//2f8TrLlwvx1FNCbNkit79kiRDjxgnRooUsnxBClJXJ7aak6Nd74gkhPD2F\nWLxYiKeflr+12wOEyMgQ4ptvhPDwEMLFRU5zcxNi61a53vTpQnzxhRAREUKEhgrx8cfys4yKEiIu\nTi4HCNG+vXzvvr5y+y1aaEcH5E9MjBBr1xpP05ahqp+QEMuWM/wRQv/4kUfke9c+79pVzi8oEOLP\nP4XYu1eITZuEePhhOb9XL/17AoRo0ED/ed59t347d+4I4e4uH8+aJX8fOVKxLCtWGJdLCPn5la+G\nrl7VT3v/ffk4LEw/v3NnIZo3F6JbNyE0GuN1jx8X4rPP5GONRojMTLl+9+76ZXbtEiI1Vf/8xg1Z\nXiVqWnc6dc3L4LCNM2eEmDRJiPBwIby8hPjrX4V44w0h1q8X4tIl+Y86aZIQbdrICrA2nD8v/4HW\nrq3e+l99JSvVfv2EuHat6uVzc2UwVEajkQGxb59+2uXLspwvvyzE5s1C3H+/EDt2CLF6tZw/a5YQ\n//iH3LaPj6yYv/xSiBMnjLft6SnE778bT0tOFiIgQAaTdvlbt+Q2tYKDZWAtXSormy5d9IGUkqKv\n+JYsEeL77/XPR44UomFD+fiVV4Ro3FiI0aP18/v0keX8+GMZTG3ayOnNm5uv9D09lQdF+Z9r12q+\njfJBlJ1tPO3wYcvW/egj/eP+/YX49lv98zFj5O/PP5eVOiCDTDs/KEiI06fll6zy233uuYrTPv+8\n4rSUFCH69pWPW7cW4vZtIT75RIjJk+W0xYvll4I7d/R/nwcO6P82ioqE2LNHPrZZcHz11Ve6x7t3\n7zaaN2/evBq9qLUwOGyvoEC2LOLjhRg4UIimTYVo1Ej+sVpSAVvLrVvynyMtrXrrX7wow6+w0Lrl\nuny54rdGPz/5rfD2bRm8rVvLCv/992VFvmyZEPn58v2Y+1dq1ky2csobNUpWKuYsWya/tQohxIQJ\nQjRpIkROjnxeUiLEqlXydT/8ULZSDL9ljx+vn/f66/oKa906IU6dkts4f14G8IkT8m9j4ULjyi0o\nSP4ePFguf/q0vqKzVuU/aJB1w6R+/tgoOLp06WLysann9sLgqH1lZbLVUds0GiH+/nchSktr/7WV\nOndOHyabNslwSUuTXSeffSa7/zQaGRrmugL/8Q8ZljWxfbtsJZY3d65sVWo0QuzeLURenhAdOsgW\nRWKiEFlZcl5urv4bqjnFxXL54mLZitJoZAvLsCU6d67sTrlzR/79PPKIvttq+3bZmsnKki2Ujh31\nldtbb8mW7cKFsgXn6yu71IQQYs4cIXr0kOEYFye/Tc+fL9cbNUq2ypo1k8/fe0/+HjtWdtUZVqCv\nvCL3y9Sp9q7InSs4VEIIYWrsIzIyUnfbV8PHpp7bi0qlgpniE5ETE6LunE1u6/ei0RgP7lvyejWt\nO3lUFRE5nLoSGoDt30v5S8HUxmdntsXRsGFDhPzvGhbp6enoYHAFvfT0dNx2gHtassVBRKRcTetO\ns+f4nqzp7cyIiKhOMtviKK+0tBQ7d+6Er68vutriYkTVwBYHEZFyNhvjGDRoEI7/77TXO3fuoEOH\nDvjggw8wePBgfPrpp9V+QSIicm5mgyMzMxPh4eEAgC+++AJRUVFQq9U4duwY5s2bV2sFJCIix2I2\nODw8PHSP16xZg7FjxwIAmjdvjkbaq7AREVG9Y3ZwvFevXpg5cyY6dOiA9PR0DP/fNY9v377NcQUi\nonrMbItj5syZyMnJwY4dO/Ddd9+hQYMGAIDffvsNTz/9dK0VkIiIHIvFR1U5Ih5VRUSknM3O4xgy\nZIjZjatUKmzcuLHaL0pERM7LbHAkJycjMDAQY8eORc+ePQFAFyKqunQ9ACIiUsRsV1VpaSm2bduG\nVatW4dixYxg0aBDGjh2Le5Xe8NmG2FVFRKSczU4AdHNzwyOPPIIVK1YgOTkZISEhiI6Oxvz586v9\nYkRE5PzMdlUBQGFhITZt2oRvv/0WmZmZePHFFzFixIjaKhsRETkgs11VTz75JH7//XfExsbiscce\nQ6dOnWq7bFViVxURkXI1rTvNBoeLiwsaN25s9kWvX79e7Re1FgYHEZFyNjscV6PRVHujRERUd/EO\ngEREpIhNgyMpKQlRUVGIiIgweUXdtLQ03HffffD09MQnn3yiaF0iIrIPm11ypKysDKGhodi+fTsC\nAgLQvXt3rFq1CmFhYbplcnNzce7cOaxfvx4+Pj545ZVXLF4X4BgHEVF12Ow8jprav38/QkJCEBwc\nDHd3d8TFxWHDhg1Gy7Ro0QLdunWDu7u74nWJiMg+bBYc2dnZCAoK0j0PDAxEdna2zdclIiLbqvQE\nwJqoyfWslKwbHx+vexwTE4OYmJhqvy4RUV2kVquhVquttj2bBUdAQACysrJ0z7OyshAYGGj1dQ2D\ng4iIKir/pXrWrFk12p7Nuqq6deuG06dPIzMzE8XFxVi9ejWGDh1qctnygzRK1iUiotplsxaHm5sb\nEhISMGLECJSWlmLSpEkICwvD4sWLAQBTpkxBTk4OunfvjuvXr8PFxQVz587FiRMn4OXlZXJdIiKy\nP94BkIionnHYw3GJiKhuYnAQEZEiDA4iIlKEwUFERIowOIiISBEGBxERKcLgICIiRRgcRESkCIOD\niIgUYXAQEZEiDA4iIlKEwUFERIowOIiISBEGBxERKcLgICIiRRgcRESkCIODiIgUYXAQEZEiDA4i\nIlKEwUFERIowOIiISBEGBxERKcLgICIiRRgcRESkCIODiIgUYXAQEZEiDA4iIlKEwUFERIowOIiI\nSBEGBxERKcLgICIiRRgcRESkCIODiIgUYXAQEZEiDA4iIlKEwUFERIowOIiISBEGBxERKWLT4EhK\nSkJUVBQiIiIwb948k8vMmDEDERER6NWrF9LS0nTTg4ODERERgcjISPTo0cOWxSQiIgXcbLXhsrIy\nTJw4Edu3b0dAQAC6d++Ohx56CGFhYbplNm/ejNTUVBw9ehS//fYbJkyYgOTkZACASqWCWq2Gr6+v\nrYpIRETVYLMWx/79+xESEoLg4GC4u7sjLi4OGzZsMFpm48aNGD9+PACgZ8+eKCgowKVLl3TzhRC2\nKh4REVWTzYIjOzsbQUFBuueBgYHIzs62eBmVSoV+/fohMjISS5cutVUxiYhIIZt1ValUKouWM9eq\n2LNnD/z9/XHy5EnExsaiY8eO6Nu3b4Xl4uPjdY9jYmIQExNTneISEdVZarUaarXaatuzWXAEBAQg\nKytL9zwrKwuBgYGVLnP+/HkEBAQAAPz9/QEAYWFhGDFiBPbv319lcBARUUXlv1TPmjWrRtuzWVdV\nt27dcPr0aWRmZqK4uBirV6/G0KFDjZYZOnQoVqxYAQBITk5G06ZN4efnh9u3b+PGjRsAgNzcXGze\nvBmdOnWyVVGJiEgBm7U43NzckJCQgBEjRqC0tBSTJk1CWFgYFi9eDACYMmUKYmNjkZSUhE6dOqFx\n48ZYvnw5ACAnJwcjR44EADRr1gzTp0/HgAEDbFVUIiJSQCWc+NAllUrFI6+IiBSqad3JM8eJiEgR\nBgcRESnC4CAiIkUYHEREpAiDg4iIFGFwEBGRIgwOIiJShMFBRESKMDiIiEgRBgcRESnC4CAiIkUY\nHEREpAiDg4iIFGFwEBGRIgwOIiJShMFBRESKMDiIiEgRBgcRESnC4CAiIkUYHEREpAiDg4iIFGFw\nEBGRIgwOIiJShMFBRESKMDiIiEgRBgcRESnC4CAiIkUYHEREpAiDg4iIFGFwEBGRIgwOIiJShMFB\nRESKMDiIiEgRBgcRESnC4CAiIkUYHEREpAiDg4iIFLFpcCQlJSEqKgoRERGYN2+eyWVmzJiBiIgI\n9OrVC2lpaYrWJSIiOxA2UlpaKjp06CAyMjJEcXGx6Ny5szhx4oTRMps2bRKPPPKIEEKI5ORk0bNn\nT4vXFUIIGxafasHOnTvtXQSqJu4751bTutNmLY79+/cjJCQEwcHBcHd3R1xcHDZs2GC0zMaNGzF+\n/HgAQM+ePVFQUICcnByL1iXnp1ar7V0Eqibuu/rNZsGRnZ2NoKAg3fPAwEBkZ2dbtMyFCxeqXNeR\nWPOfqLrbUrKeJctWtYy5+Uqn25u1y+UM+0/pPEfdd4Dz7b+68r9ns+BQqVQWLSdbTc6NwVH96fbm\nbBWPpcsyOGp3e/UtOGw2SLBv3z4xcOBA3fPZs2eLOXPmGC0zZcoUsWrVKt3z0NBQkZOTY9G6QgjR\noUMHAYA//OEPf/ij4KdDhw41qt/dYCPdunXD6dOnkZmZidatW2P16tVYtWqV0TJDhw7F/PnzERcX\nh+TkZDRt2hR+fn5o1qxZlesCwJkzZ2xVfCIiMsNmweHm5oaEhASMGDECpaWlmDRpEsLCwrB48WIA\nwJQpUxAbG4ukpCR06tQJjRs3xvLlyytdl4iI7E8lRB0YZCAiolrDM8eJiEgRBgcRESliszEOeygq\nKsKMGTNw584dDBs2DA8//LC9i0QKZGRk4IMPPsC1a9ewdu1aexeHFNiwYQM2bdqE0tJSTJ06FT16\n9LB3kUiBtLQ0zJ07F8XFxRg0aBBGjhxZ6fJ1aozjl19+waVLlzB27FhMnjwZS5YssXeRqBpGjx7N\n4HBSly9fxsyZM7Fo0SJ7F4Wqobi4GOPHjzd5FKshh++qmjhxIvz8/NCpUyej6aYugnjs2DF06NAB\nAHDnzp1aLytVpGT/kWOpzr778MMPMWXKlNosJpmhdP9t3LgRDzzwAMaMGVP1xmt0FkgtSEpKEocO\nHRLh4eG6aeYugvjLL7/oTiicPHmyvYpMBpTsP61Ro0bZo6hUjpJ9p9FoxGuvvSa2b99uxxKToer8\n7wkhxJAhQ6rctsO3OPr27QsfHx+jaeYugti7d28cPHgQ06ZNq7KPjmqHkv2Xn5+PqVOn4siRI/jw\nww/tVGLSUrLv5s+fj19++QXr1q3TnatF9qVk//3666948cUX8fe//x2jR4+ucttOOThu6uKIv/32\nGzw8PPDxxx/bsWRkCXP7z9fXF59//rkdS0ZVMbfv5s2bh2nTptmxZGQJc/svOjoa0dHRFm/H4Vsc\nplh6AUVyTNx/zov7zrlZa/85ZXAEBAQgKytL9zwrKwuBgYF2LBEpwf3nvLjvnJu19p9TBofhBRSL\ni4uxevVqDB061N7FIgtx/zkv7jvnZrX9Z/WhfCuLi4sT/v7+okGDBiIwMFAkJCQIIYRQq9WiS5cu\nIjw8XMydO9fOpSRzuP+cF/edc7Pl/qtTJwASEZHtOWVXFRER2Q+Dg4iIFGFwEBGRIgwOIiJShMFB\nRESKMDiIiEgRBgcRESnC4CCHNn/+fERHRyMiIgKRkZE4cOAAAGDSpEk4efKkTV6zsLAQsbGx6Nq1\nK/bs2aObPnLkSERGRuLuu+9G06ZNERkZicjISCQnJ1u03T59+lS5jDXfV/nPbv/+/ZUun5iYiIsX\nL1rltamOs955ikTWtXfvXtGxY0dx69YtIYQQeXl54sKFCzZ/3Q0bNojx48ebna9Wq8XgwYMrTC8p\nKbFhqZSpzmcXExMjDh48WBvFIyfHFgc5rMLCQgQEBKBRo0YAAF9fX/j7+wMAYmJikJKSgh9++EH3\nzT80NBTt27cHAKSkpKBXr17o2LEjBgwYgCtXrlTY/p9//omYmBi0bdsW/fr1Q1ZWFo4cOYJp06Zh\n8+bNiIyMRGFhYYX1hMHFFr788kuMHj0aDz30EAYOHIhbt27hwQcfRFRUFGJjY7Fjxw7dsl5eXgAA\ntVqNBx98EHFxcbjnnnvwj3/8Q7dMTEwMDh06pFv+vffew7333otx48YhPz8fAHD27Fl0794doaGh\nmD17Nry9vRV9dqY+m3Xr1uHgwYN4/PHHERUVZfJ9E+nYO7mIzNFoNOKBBx4Qbdq0EdOmTROnT5/W\nzYuJiREpKSlGy48ZM0YsXLhQFBcXi06dOomsrCwhhBALFiwQc+bMqbD96dOni48++kgIIcTs2bPF\n8OHDhRBCfPnll2LatGlmy7Vz505di2P58uXCx8dHZGRkCCHkHdauX78uhBDi3LlzIjAwULeel5eX\nbn13d3eRlpYmCgsLRXh4uK6shu9LpVKJL774QgghxDPPPCMSExOFEEI899xz4j//+Y8QQoiZM2cK\nb29viz+7yj4bU58pkSlscZDDUqlUurvKNWzYEH369MHmzZtNLvvRRx+hUaNGePbZZ/HHH3/g3Llz\nGDJkCCIjI/H5558bjVVo/fTTT5g4cSIAeX/mXbt2AZAtCqHgEm79+vVDcHAwAMDV1RVz585F7969\nMWTIEOTn5+Py5csV1unRowdCQ0Ph4eGB3r17myyfm5sbHn/8cd1r7Nu3DwCwbds2PPnkkwCAp59+\n2mRZzX12VX02St431V9OeQdAql+6d++O7t27IywsDF9//TViY2ON5m/fvh3fffcdkpKSAMjKz9fX\nF4cPH65y29qKsiY3uNF2AQGyG2rXrl3YunUrGjdujJYtW5rs9jG8pWeDBg1QVFRUYRkPDw94enoC\nANzd3avsNjOl/Gc3Y8aMSj8b3qiJLMEWBzmsU6dO4fTp0wCA0tJSJCcno1mzZkbLnDt3Ds8//zzW\nrFkDDw8PAEBoaCgA4LvvvoMQAiUlJThx4kSF7cfGxiIxMREajQYJCQmKbp1pTnZ2NgICAuDt7Y1v\nv/1WNy5hTQMGDMDKlSuh0Wjw1VdfmVzG3GdX2Wfj7e1tsnVEVB6DgxzWzZs3MWHCBNx77724++67\nceXKFcTHx+vmCyGQmJiI/Px8DB8+HJGRkRg8eDAaNGiA9evX49///jdCQ0MRGRmp6+Yx9NJLL+HH\nH39Eu3btsG3bNsydOxeA/NZd2Tdvw/nllx0+fDgKCgoQFhaG3bt345577jFaz9Tjyl7H1GtOnz4d\nX331FcLCwnDz5k00adKkwrrmPjt3d3ezn80zzzyDWbNmISoqymQLiEiL9+MgcjJ37txBw4YNIYTA\np59+il27duH777+3d7GoHuEYB5GTSUlJwQsvvIDr168jKCgIy5cvt3eRqJ5hi4OIiBThGAcRESnC\n4CAiIkUYHEREpAiDg4iIFGFwEBGRIgwOIiJS5P8B0a2VvjZg8S8AAAAASUVORK5CYII=\n", "text": [ "" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Error with 999 training samples: 0.126959275764\n" ] } ], "prompt_number": 7 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that even as the size of the training set becomes large, our expected error does not fall below 0.12. This is far from the optimal $\\hat{f} = f^\\ast$, where the error would approach $\\sigma^2 = 0.01$. This result is due to bias. Our model is not complex enough to accurately approximate $f^\\ast$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### *Key idea:* Even as the amount of training data becomes large, we are still far from optimal performance because of *bias*." ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "A More Complex Hypothesis Class" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Next we will learn a 4th degree polynomial, but restrict our training set size to only 10 data points. Now the bias is 0, but we are learning 5 coefficients with only 10 datapoints. For comparision, we will also learn a 1st degree polynomial like before. How do you think the results will compare?" ] }, { "cell_type": "code", "collapsed": false, "input": [ "# Learn a kth degree polynomial with 10 data points\n", "mse_ar_order1 = []\n", "mse_ar_orderk = []\n", "k = 4 # order of more complex polynomial\n", "N = 10\n", "numTrials = 1000\n", "for trial in range(numTrials):\n", " # Generate N data points:\n", " trainData = make_data(N) \n", " \n", " # Perform linear regression:\n", " f_hat_order1 = polynomial_regression(trainData, order=1)\n", " f_hat_orderk = polynomial_regression(trainData, order=k)\n", " \n", " # Evaluate:\n", " mse_order1 = get_mse(f_hat_order1(testData[0]), testData)\n", " mse_ar_order1.append(mse_order1)\n", " \n", " mse_orderk = get_mse(f_hat_orderk(testData[0]), testData)\n", " mse_ar_orderk.append(mse_orderk)\n", " \n", "meanError_order1 = sum(mse_ar_order1)/numTrials\n", "meanError_orderk = sum(mse_ar_orderk)/numTrials\n", " \n", "print \"Average MSE, 1st degree polynomial:\", meanError_order1\n", "print \"Average MSE, kth degree polynomial:\", meanError_orderk" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "Average MSE, 1st degree polynomial: 0.173445439906\n", "Average MSE, kth degree polynomial: 1.20624934823\n" ] } ], "prompt_number": 11 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Whoa, the 1st degree polynomial is still better. Why? This is because even though the more complex model now has 0 bias, it large variance. By training on only 10 data points, we still expect the learned model $\\hat{f}$ to differ greatly from $f^*$ - even more so than a simpler but biased model. Try increasing the number of training examples N to see what happens then." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### *Key idea:* Increasing the complexity of our model may decrease error due to bias. However, without enough training data, we may also be increasing error due to variance! Achieving the right balance is an important goal (and usually taken care of by cross validation)." ] }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "L1 vs. L2 Regularization" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Least squares with **L1 Regularization** (Lasso): $\\min_{\\mathbf{w}, w_0} \\sum_i^N (\\mathbf{w}^T \\mathbf{x_i} + w_0 - y_i)^2 + \\lambda ||\\mathbf{w}||_1$\n", "\n", "Least squares **L2 Regularization** (Ridge Regression): $\\min_{\\mathbf{w}, w_0} \\sum_i^N (\\mathbf{w}^T \\mathbf{x_i} + w_0 - y_i)^2 + \\lambda||\\mathbf{w}||^2_2$\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### L1, L2, or both:\n", "\n", "* Encourages sparsity in solution\n", "\n", "* Magnitude of w decreases as lambda increases\n", "\n", "* Has a closed form solution\n", "\n", "* Larger $\\lambda$ helps avoid over-fitting\n", "\n", "* Too large a $\\lambda$ can lead to under-fitting\n", "\n", "* Shrinkage for each weight is the same, regardless of magnitude\n", "\n", "* Usually solved with coordinate descent\n", "\n", "* Corresponds to MAP estimation with a Gaussian prior\n", "\n", "* The same weight can be positive for one value of lambda, zero for a smaller value of lambda\n", "\n", "* The same weight can be positive for one value of lambda, negative for a smaller value of lambda\n", "\n", "* Tends to lead to better predictive performance\n", "\n", "* Used when many more features than examples\n", "\n", "* Should generally be debiased after solution is found\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Answers:\n", "\n", "* Encourages sparsity in solution - _L1_\n", "\n", "* Magnitude of w decreases as lambda increases - _BOTH_\n", "\n", "* Has a closed form solution - _L2_\n", "\n", "* Larger $\\lambda$ helps avoid over-fitting - _BOTH_\n", "\n", "* Too large a $\\lambda$ can lead to under-fitting - _BOTH_\n", "\n", "* Shrinkage for each weight is the same, regardless of magnitude - _Probably L1, but it depends on the way \"shrinkage\" is defined. In terms of simply looking at the objective value, it looks like both. In terms of (sub-)gradients and how the shrinkage is applied in an algorithm like coordinate descent, the shrinkage penalty is the same for each parameter, regardless of its current weight. This is the reason L1 encourages sparsity but L2 does not. With L2, we penalize weights more when they're large. With L1, we don't care if they're large or not, the soft-thresholding is the same for everyone, meaning less relevant weights get set exactly 0._\n", "\n", "* Usually solved with coordinate descent - _L1 (L2 can be solved with coordinate descent too, but a lot of times it's better to use another algorithm)_\n", "\n", "* Corresponds to MAP estimation with a Gaussian prior - _L2_\n", "\n", "* The same weight can be positive for one value of lambda, zero for a smaller value of lambda - _BOTH, but much, much more likely to happen with L1_\n", "\n", "* The same weight can be positive for one value of lambda, negative for a smaller value of lambda - _BOTH_\n", "\n", "* Tends to lead to better predictive performance - _L2 (That is, L2 is often better than L1. This is mainly an empirical observation.)_\n", "\n", "* Used when many more features than examples - _BOTH, but L1 is talked about more often in this case. Really, it depends on what you're trying to do (e.g. if you want sparsity or not)._\n", "\n", "* Should generally be debiased after solution is found - _L1 (L1 squashes the weights a lot to get the desired sparsity - see Murphy page 439)._\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### *Key idea:* When there are \"too many\" parameters to estimate, we usually assume some \"structure\" to direct our solution. With Lasso, this structure is sparsity. With ridge regression, the structure is small weights. In both cases, we avoid overfitting." ] }, { "cell_type": "code", "collapsed": false, "input": [], "language": "python", "metadata": {}, "outputs": [] } ], "metadata": {} } ] }