{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Cross-validation and polynomial regression" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Polynomial regression\n", "\n", "Polynomial regression consists of fitting some data $(x, y)$ to a $n$-order polynomial of the form:\n", "\n", "$$\n", " y = f(x) = b + w_1 \\cdot x + w_2 \\cdot x^2 + ... + w_n \\cdot x^n\n", "$$\n", " \n", "By rewriting the unidimensional input $x$ into the following vector:\n", "\n", "$$\n", " \\mathbf{x} = \\begin{bmatrix} x & x^2 & ... & x^n \\end{bmatrix}^T\n", "$$\n", "\n", "and the weight vector as:\n", "\n", "$$\n", " \\mathbf{w} = \\begin{bmatrix} w_1 & w_2 & ... & w_n \\end{bmatrix}^T\n", "$$\n", " \n", "the problem can be reduced to linear regression:\n", "\n", "$$\n", " y = \\langle \\mathbf{w} \\cdot \\mathbf{x} \\rangle + b\n", "$$\n", " \n", " and we can apply the delta learning rule to find $\\mathbf{w}$ and $b$:\n", "\n", "$$\n", " \\Delta \\mathbf{w} = \\eta \\, (t_i - y_i ) \\, \\mathbf{x_i}\n", "$$\n", "$$\n", " \\Delta b = \\eta \\cdot (t_i - y_i ) \n", "$$\n", "\n", "A first method to perform polynomial regression would be to adapt the code you wrote in the last exercise session for linear regression. However, you saw that properly setting the correct learning rate can be quite tricky. \n", "\n", "The solution retained for this exercise is to use the built-in functions of Numpy which can already perform polynomial regression in an optimized and proved-sure manner (Note: NumPy does not use gradient descent, but rather directly minimizes the error-function by inversing the Gram matrix).\n", "\n", "```python\n", "w = np.polyfit(X, t, deg)\n", "```\n", "\n", "This function takes the inputs $X$, the desired outputs $t$ and the desired degree of the polynomial `deg`, performs the polynomial regression and returns the adequate set of weights (beware: the higher-order coefficient comes first, the bias is last).\n", "\n", "Once the weights are obtained, one can use them to predict the value of an example with the function:\n", "\n", "```python\n", "y = np.polyval(w, X)\n", "```\n", "\n", "*Note:* if you prefer to use scikit-learn, check but see for why it may be a bad idea.\n", "\n", "Let's start by importing the usual stuff and create a dataset of 16 samples generated using the function $x \\, \\sin x$ plus some noise:" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "import matplotlib.pyplot as plt\n", "\n", "# Just to avoid the annoying warnings, please ignore\n", "def warn(*args, **kwargs):\n", " pass\n", "import warnings\n", "warnings.warn = warn\n", " \n", "def create_dataset(N, noise):\n", " \"Creates a dataset of N points generated from x*sin(x) plus some noise.\"\n", " \n", " x = np.linspace(0, 10, 300)\n", " rng = np.random.default_rng()\n", " rng.shuffle(x)\n", " x = np.sort(x[:N])\n", " t = x * np.sin(x) + noise*rng.uniform(-1.0, 1.0, N)\n", " \n", " return x, t\n", "\n", "N = 16\n", "X, t = create_dataset(N, noise=0.2)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAlIAAAFlCAYAAAAgSAb7AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8vihELAAAACXBIWXMAAAsTAAALEwEAmpwYAABIRElEQVR4nO3dd1jUV74G8PdMAYbOUKVIUcSCBQWsMdHEmK7pZdOzm3LTNjfrbkx2N3t3Nxs3brLJtmTTNsV0CxpNYowlxlhBRGxYKMKg9F6HmXP/AF0LqMAwZ8r7eR6f6AAzr0Hl5fzO73uElBJERERE1Hsa1QGIiIiInBWLFBEREVEfsUgRERER9RGLFBEREVEfsUgRERER9RGLFBEREVEf6VS8aEhIiIyLi1Px0kRERES9kpWVVSmlDO3ubUqKVFxcHDIzM1W8NBEREVGvCCGKenobL+0RERER9RGLFBEREVEfsUgRERER9ZGSPVJEREQEmM1mlJSUoLW1VXUUAuDl5YXo6Gjo9foL/hgWKSIiIkVKSkrg5+eHuLg4CCFUx3FrUkpUVVWhpKQE8fHxF/xxvLRHRESkSGtrK4KDg1miHIAQAsHBwb1eHWSRIiIiUoglynH05XNhkyIlhHhKCLFXCLFHCPGJEMLLFs9LREREA6usrAx33HEHEhISMGHCBEyePBnLli2za4bCwkIkJyd3+/jHH3/cp+d89dVX0dzcfPLXvr6+fc53Lv0uUkKIKABPAEiVUiYD0AK4rb/PS0RERANLSom5c+di+vTpyM/PR1ZWFj799FOUlJSc9b4dHR12z3euInW+PGcWqYFiq83mOgAGIYQZgDeAUhs9LxEREQ2QdevWwcPDAw8//PDJx2JjY/H4448DAN577z2sWrUKra2taGpqwuLFi3H//fcjPz8f3t7eePPNNzFmzBj87ne/g6+vL37xi18AAJKTk7Fy5UoAwJVXXolp06Zh8+bNiIqKwvLly2EwGJCVlYX7778f3t7emDZtWrf5nnnmGezfvx/jxo3DPffcg6CgoNPy/Pa3v8Vf/vKXk6/12GOPITU1FfX19SgtLcWMGTMQEhKC9evXAwCee+45rFy5EgaDAcuXL0d4eHi//x/2u0hJKU1CiL8AOAqgBcC3Uspv+52MiIjIjfzfl3uxr7Teps85MtIfz187qse37927F+PHjz/nc2zZsgW7d++G0WjE448/jpSUFGRkZGDdunW4++67sWvXrnN+/KFDh/DJJ5/grbfewi233IIlS5bgzjvvxH333Ye///3vuPjiizFv3rxuP3bBggWnFaX33nvvtDwbNmzo9uOeeOIJvPLKK1i/fj1CQkIAAE1NTZg0aRJeeOEF/PKXv8Rbb72FX//61+fMfiFscWkvCMAcAPEAIgH4CCHu7Ob9HhRCZAohMisqKvr7skRERAOu1WzBHlMdsopq0Nhm/0tb9vboo49i7NixSEtLO/nYrFmzYDQaAQCbNm3CXXfdBQCYOXMmqqqqUFdXd87njI+Px7hx4wAAEyZMQGFhIerq6lBbW4uLL74YAE4+54U4NU9veHh44Jprrjkthy3Y4tLeZQAKpJQVACCEWApgCoBFp76TlPJNAG8CQGpqqrTB6xIREdlUVlENfjhUgYNlDThwvAGFlU2wnvIVKy7YGyMG+WPkIH+kxRsxMd6I5btKsXB1HkprWxAZaMC82UmYmxLV69c+18rRQBk1ahSWLFly8tf//Oc/UVlZidTU1JOP+fj4nPy5lGd/+RZCQKfTwWq1nnzs1BECnp6eJ3+u1WrR0tICKWWf71Y8Nc+5XvdMer3+5GtqtVqb7fmyRZE6CmCSEMIbnZf2LgWQaYPnJSIisos9pjr85ds8bMirgBBArNEbSRF+uGZMJJLC/eCh0+DAsXrs6/rx9Z7jAIDEMF8crW5GW0fnF3NTbQvmL80FgD6VKXubOXMmnn32Wbz++ut45JFHAOCcG7SnT5+Ojz76CL/5zW+wYcMGhISEwN/fH3FxcScvv+3cuRMFBQXnfN3AwEAEBARg06ZNmDZtGj766KNu38/Pzw8NDQ09Pk9sbCz27duHtrY2tLa2Yu3atSf3W5342BOX9gaKLfZIbRNCLAawE0AHgGx0rTwRERE5siMVjXhlzUGs2n0MAQY9nrlyOO6cFAtfz7O/PM4a+d+NyQ2tZizdacL/fbn3tBUrAGgxW7BwdZ5TFCkhBDIyMvDUU0/hpZdeQmhoKHx8fPDnP/+52/f/3e9+h/vuuw9jxoyBt7c33n//fQDAjTfeiA8++ADjxo1DWloahg0bdt7X/s9//nNys/ns2bO7fZ8xY8ZAp9Nh7NixuPfeexEUFHTa22NiYnDLLbdgzJgxSExMREpKysm3Pfjgg7jyyisxaNCgk5vNB4LobpluoKWmpsrMTC5aERGRGu0dVvxx1T58tO0oPHUaPDAtHj+bngB/rws/Yw0A4p5Z1e3jAkDBgqvP+/H79+/HiBEjevWaNLC6+5wIIbKklKndvT/P2iMiIrdS12zGQ4sysTW/GndPjsUTlyYixNfz/B/YjahAA0y1LWc9PiiAc6ndBY+IISIit3G0qhnXv/4jdhbV4tVbx+H3c5L7XKIAYN7sJBj02rMeN3hoUd9q7k9UchIsUkRE5Bayimow918/orqpHR8+kG6TPUxzU6Lw4g2jERVogEDnCtXdk2NRVNWM29/cisrGtv4HJ4fGS3tEROTyVu0+hqc+34XIAC+8e28aEkJtd+7a3JSos0rZzOFheGTRTtz8xhZ8cH86YozePX58f0YBkG31Zd84V6SIiMilrd1fhsc+2YkxUQFY+j9TbVqienJJUhgW/TQdVY1tuPmNLSip6X6kgJeXF6qqqvr0BZxsS0qJqqoqeHn1bn8b79ojIiKXta+0Hje9sRkJoT74/KHJ8Paw74WYA8frcfMbWxAf4oMvHp4MT93p+6nMZjNKSkrOOUiS7MfLywvR0dHQ60+/e5N37RERkdspr2/FA+/vgL+XHu/ck2b3EgUAwyP88fLNY/Hgh1n4/Zf78ML1o097u16vR3x8vN1zke2wSBERkctpabfgpx9koq7FjM8fmoxwfzXjCDKyTVi4Og8A8NG2o5AS+NMNo8/zUeRMuEeKiIhcitUq8dRnu5BrqsPfbktBclSAkhwZ2SbMX5p72pypj7cfxb/WH1aShwYGixQREbmUhd/m4Zu9x/HcVSNw2SnHutg9x+o8tJgtZz3+8pqDqGvhjClXwSJFREQu47t9ZXh9wxHcnj4YD0xTu/eotJuJ5wBgsUr84osc3qnnIlikiIjIJdQ0teOZpbkYHuGH3103UvlspshAQ7ePBxj0WLOvDIu2HbVzIhoILFJEROQSfrtiL2qb2/HyLWPPGjOgQnfHxxj0Wvzu2pGYMiQYC785gCpOPnd6LFJEROT0Vu0+hi9zSvHEpYkYFalmc/mZujs+5sUbRuP68dH4/ZxRaG63YMHXB1THpH7i+AMiInJqFQ1t+HVGLsZEB+CRS4aojnOa7o6PAYChYX544KJ4/Pv7fNyWHoMJsUYF6cgWuCJFREROS0qJ55bloqndgpdvHgu91nm+rD0xMxGDArzw64y96LBYVcehPnKeP3FERERnyNhlwrf7yvD0rGFIDPdTHadXfDx1+M01I7H/WD0WbS1SHYf6iEWKiIicUnl9K55fvhcTYoPw04sSVMfpkyuTI3BRYghe/vYgyht43p4zYpEiIiKn9Odv8tBqtuIvN4+FVqN21EFfCSHwf9eNQluHFQu+4sZzZ8QiRURETienuBZLdpbg/mnxiA/xUR2nXxJCffHg9AQszTZhe0G16jjUSyxSRETkVKSU+Pmnu6ARwBvfH8HUBeuQkW1SHatfHp0xFBH+Xli4+gAnnjsZFikiInIqz6/Yi4KqJli7+oaptgXzl+Y6dZkyeGjxyCVDsKOwBluOVKmOQ73AIkVERE6j1WzBR1vPPlqlxWzBwtV5ChLZzq1pMQj398Sraw+pjkK9wCJFRERO462N+bD0cOmrp0OCnYWXXouHLx6C7QXVXJVyIixSRETkFMrqW/GvDUfgpe/+S1dPhwQ7k9vTByPMzxOvrT2oOgpdIBYpIiJyCi99kweLVeIXl3d/GPC82UmKktnOiVWprfnV2JrPVSlnwCJFREQOL7ek7uS4g59elNDtYcDdnWnnjO6YOBihfp547TvulXIGPLSYiIgc3str8hDkrcejMzoPJe7pMGBX4KXX4qHpCfjjqv3YXlCN9HgeaOzIuCJFREQOLftoDTbkVeDB6UPg56VXHccufjIxFiG+3CvlDFikiIjIob229hCCvPW4e3Ks6ih2Y/DoXJX68XAVMgs57dyRsUgREZHDOnU1ysfTvXaj/GTSYAT7eOD1DUdUR6FzYJEiIiKH5Y6rUSd4e+hwx8TBWJdXjqNVzarjUA9YpIiIyCG582rUCT+ZGAutEPhwa6HqKNQDFikiInJI7rwadUJEgBdmJ0fgsx3FaG7vUB2HusEiRUREDoerUf9175Q41Ld2ICO7VHUU6gaLFBERORyuRv1XamwQRg7yx/ubCyF7OGeQ1LFJkRJCBAohFgshDggh9gshJtvieYmIyP1wNep0QgjcOyUOeWUN2JrPUQiOxlYrUq8B+EZKORzAWAD7bfS8RETkZv614QgCuRp1muvGRSLQW4/3NxeqjkJn6HeREkL4A5gO4B0AkFK2Sylr+/u8RETkfvIrGvHd/jLcNSmWq1Gn8NJrcWtaDL7ddxym2hbVcegUtliRSgBQAeA/QohsIcTbQgifM99JCPGgECJTCJFZUVFhg5clIiJX886mAug1Gtw9OU51FIdz16TOFbqPthYpTkKnskWR0gEYD+B1KWUKgCYAz5z5TlLKN6WUqVLK1NDQUBu8LBERuZKqxjYszirB9SlRCPXzVB3H4UQHeeOyEeH4dEcxWs0W1XGoiy2KVAmAEinltq5fL0ZnsSIiIrpgi7YeRVuHFT+9KF51FId175Q4VDe148scjkJwFP0uUlLK4wCKhRBJXQ9dCmBff5+XiIjcR6vZgg+2FGJGUigSw/1Ux3FYk4cEIzHMF4u2HVUdhbrY6q69xwF8JITYDWAcgD/Z6HmJiMgNLMs2oaqpHT+7KEF1FIcmhMCtaTHIKa7F4fIG1XEINipSUspdXfufxkgp50opa2zxvERE5PqsVom3f8jHqEh/TB4SrDqOw5szLgpajcDiLJPqKITOjeJERER2lZFtwsLVeSitbYHRxwNVTe149dZxEEKojubwQv08ccmwUCzLLsG82UnQavj/TCUeEUNERHaVkW3C/KW5MNW2QAKoamqHAGCx8viTC3XThGiU1bdh0+FK1VHcHosUERHZ1cLVeWg54/Z9CeCVNQfVBHJCM0eEIcCgx+KsEtVR3B6LFBER2VVpD5O5e3qczuap02LOuEh8u/c46lrMquO4NRYpIiKyq8hAQ68ep+7dOD4abR1WrNp9THUUt8YiRUREdjVvdhIMeu1pjxn0WsybndTDR1B3xkQHIDHMF0t28vKeSixSRERkV3NTovDC3GRou+7Qiwo04MUbRmNuSpTiZM5FCIGbJkQjq6gG+RWNquO4LRYpIiKyO3+DHhYp8fpPxuPHZ2ayRPXR9SlR0AhwVUohFikiIrK7D7cWIdzfE5eNDFcdxamF+Xth+rBQLN1p4vgIRVikiIjIrgorm/D9wQrcnj4Yei2/DPXXTROicayuFVuOVKmO4pb4J5iIiOzqo21F0GkEbk8frDqKS7hsRDj8vXRYnFWsOopbYpEiIiK7aTVb8HlmCWaPikC4v5fqOC7BS6/F1WMisXpvGVraLef/ALIpFikiIrKbL3NKUddixp2TYlVHcSnXjhmEFrMF6/PKVUdxOyxSRERkNx9uLUJimC8mJRhVR3Ep6fFGhPh6cDinAixSRERkFznFtdhdUoe7JsdCdM2QItvQaTW4IjkCaw+Uobm9Q3Uct8IiRUREdvHh1iL4eGhxPWdGDYirR0ei1WzF+gMVqqO4FRYpIiIacPWtZqzcXYrrxkXBz0uvOo5L6ry854lVuaWqo7gVFikiIhpwK3aVotVsxe3pMaqjuCytRuCq0RFYd6AcTW28vGcvLFJERDTgPs8sxvAIP4yOClAdxaVdPXoQWs1WrDvAu/fshUWKiIgG1N7SOuwuqcNtaTHcZD7AUuOMCPPz5N17dsQiRUREA+rzHcXw0Gl4MLEddF7eG4T1eeVo5OU9u2CRIiKiAdNqtmBZtglXjIpAoLeH6jhu4eoxg9DWYcXa/WWqo7gFFikiIhowq/ceR31rB25L4yZze5kwOAjh/ry8Zy8sUkRENGA+3V6MwUZvTEoIVh3FbWi6Lu9tOFiBhlaz6jguj0WKiIgGRFFVE7bkV+GW1GhoNNxkbk/XjBmE9g4r1u7n3XsDjUWKiIgGxOeZxdAI4KYJvKxnbykxQRgU4IWVvLw34FikiIjI5josVnyRWYIZSWGICPBSHcftaDQCVyYPwsaDFbx7b4CxSBERkc1tyKtAeUMbbuEmc2UuHxWOdosVGw/y7L2BxCJFREQ291lmMUJ8PTFzeJjqKG4rNTYIgd56rNnHMQgDiUWKiIhsqrKxDesPlOPG8VHQa/llRhWdVoOZw8Ow7kA5zBar6jgui3/CiYjIppbvKkWHVeKmCdGqo7i9WSPCUddiRmZhjeooLotFioiIbGpJVgnGRAcgMdxPdRS3N31YKDx0Gl7eG0AsUkREZDP7Suux71g9bhzP1ShH4OOpw9QhwViz/ziklKrjuCQWKSIispklO0ug1wpcNzZSdRTqMmtkBIqrW3CwrFF1FJfEIkVERDZhtlixfJcJM4eHIciHBxQ7iktHdN45uWbfccVJXJPNipQQQiuEyBZCrLTVcxIRkfPYeLAClY3tvKznYML9vTA2JhBreFzMgLDlitSTAPbb8PmIiMiJLNlZAqOPBy5J4uwoR3P5yHDkFNeirL5VdRSXY5MiJYSIBnA1gLdt8XxERORcapvb8d2+clw3NhIeOu4acTSXjQgHAHy3n3fv2Zqt/rS/CuCXAHqc+CWEeFAIkSmEyKyo4Lh6IiJX8uXuY2i3WDk7ykENC/fFYKM3vuMYBJvrd5ESQlwDoFxKmXWu95NSvimlTJVSpoaGhvb3ZYmIyIEsySpBUrgfRkX6q45C3RBCYNbIcPx4pApNPMTYpmyxIjUVwHVCiEIAnwKYKYRYZIPnJSIiJ3CkohG7imtx44QoCCFUx6EeXDYiHO0dPMTY1vpdpKSU86WU0VLKOAC3AVgnpbyz38mIiMgpLMkqgUYAc8dFqY5C55AW13WIMfdJ2RR3BBIRUZ9ZrRLLsk2YPiwUYf5equPQOei0GsxM6jzEuIOHGNuMTYuUlHKDlPIaWz4nERE5rq0FVThW14obODvKKVw6Ihy1zWbsKq5VHcVlcEWKiIj6LCPbBB8PLWZ13V5Pjm1aYgi0GoH1eRzOaSssUkRE1CetZgu+zj2OK5IHweChVR2HLkCAQY8Jg4OwIY8bzm2FRYqIiPpk3YFyNLR14PoUbjJ3JhcnhWJvaT3KGzjl3BZYpIiIqE+WZZsQ5ueJyUOCVUehXrgkqXOW4/dclbIJFikiIuq1mqZ2bMgrx5xxkdBqODvKmYwc5I8wP09s4Dwpm2CRIiKiXluVewxmi8Qczo5yOkIIXDwsFD8crOAYBBtgkSIiol7LyDYhMcyXR8I4qUuSwlDf2sExCDbAIkVERL1SXN2MzKIazE3hkTDO6sQYBN69138sUkRE1CvLd5kAAHPGRSpOQn0VYNBj/OBAzpOyARYpIiK6YFJ2HgmTHm9EdJC36jjUD5ckhXEMgg2wSBER0QXbY6rHkYomHlDsAi4exjEItsAiRUREFyxjlwkeWg2uHj1IdRTqp1GR/gjlGIR+Y5EiIqIL0mGxYkVOKWYMD0WAt151HOonjkGwDRYpIiK6IFvyq1DR0MbLei7kkqRQjkHoJxYpIiK6IMt3lcLPU4cZw8NURyEbuWhoKDQCHIPQDyxSRER0Xq1mC1bvOY4rkiPgpdeqjkM2EuCtx/jBQdhwkGMQ+opFioiIzmtDXjka2jpwHWdHuZxLkkKxx8QxCH3FIkVEROe1fFcpQnw9MTkhWHUUsrGLh3Veqt10qFJxEufEIkVEROdU32rG2gPluGbMIOi0/LLhakZF+iPIW88i1Uf8G0FEROe0es9xtHdYeSSMi9JoBKYMDcGmw5WQUqqO43RYpIiI6JxW5JRisNEb42ICVUehAXLR0BCUN7ThYFmj6ihOh0WKiIh6VN7Qih8PV2LOuEgIIVTHoQEyLTEEALDpMC/v9RaLFBER9eir3cdgleBlPRcXHeSN+BAfbDrEeVK9xSJFREQ9Wp5TipGD/DE0zE91FBpg04aGYFtBNdo7eFxMb7BIERFRt45WNSP7aC1nR7mJaYkhaG63YOfRGtVRnAqLFBERdWtFjgkAcO1YFil3MHlIMLQawTEIvcQiRUREZ5FSImNXKdLjjIgKNKiOQ3bg76XH2OgA/MAN573CIkVERGfZf6wBh8sbeVnPzUxLDEVuSS3qms2qozgNFikiIjrLipxS6DQCV40epDoK2dFFiSGwSmBLPlelLhSLFBERnUZKiS9zSjEtMQRGHw/VcciOxsUEwsdDix+4T+qCsUgREdFpdh6tgam2Bddxk7nb0Ws1mJQQzMGcvcAiRUREp1mxqxSeOg0uHxWhOgopMC0xBEVVzSiublYdxSmwSBER0UkdFitW5R7DpSPC4OupUx2HFLio67gYXt67MCxSRER00pb8KlQ2tvOynhsbEuqLCH8vbDrM42IuBIsUERGdtGJXKfw8dbgkKUx1FFJECIFpiSHYfKQKFqtUHcfh9btICSFihBDrhRD7hRB7hRBP2iIYERHZV1uHBd/sPY7LR0XAS69VHYcUuigxBLXNZuwtrVMdxeHZYkWqA8DTUsoRACYBeFQIMdIGz0tERHa0Ia8CDa0dHMJJmDKkc5/Uj4erFCdxfP0uUlLKY1LKnV0/bwCwH0BUf5+XiIjsa0VOKYJ9PDB1SLDqKKRYqJ8nhoX7YvMRbjg/H5vukRJCxAFIAbDNls9LREQDq6mtA2v3l+Gq0YOg03L7LHWuSmUW1qC9w6o6ikOz2d8WIYQvgCUAfi6lrO/m7Q8KITKFEJkVFbwTgIjIkazZV4ZWs5WX9eikyUOC0WK2IKekVnUUh2aTIiWE0KOzRH0kpVza3ftIKd+UUqZKKVNDQ0Nt8bLkIjKyTZi6YB3in1mFqQvWISPbpDoSkdtZkVOKyAAvTBgcpDoKOYhJ8cEQAtjMfVLnZIu79gSAdwDsl1K+0v9I5E4ysk2YvzQXptoWSACm2hbMX5rLMkVkRzVN7dh4sALXjo2ERiNUxyEHEeCtx6hIf+6TOg9bjK2dCuAuALlCiF1djz0rpfzKBs9NTqaprQMHyxpw4HgDDpY1oKqxHbUtZtS1mFHf9V+tRsDXUwdvDy0OlTWi3XL69fcWswULV+dhbgrvWSCyh6/3HEeHVeJaDuGkM0wZEoL3fixEq9nCkRg96HeRklJuAsBvYdxIRrYJC1fnobS2BWF+npiWGIKmNgv2H69HUdV/z2Yy6LUI8/dEoEEPf4Meg43e8PfSwSolGtssaGrrwN7Ss7bTAehcmXr0o524bGQYZiSFIdCbJ9ATDZQVOSYkhPpgVKS/6ijkYCYPCcabG/ORVVSDqUNDVMdxSDxIiXrli8xiPLdsz8lVpLKGNizZaYLRxwOTEoy4cXw0kiL8MCLCH9FBhvNeJpi6YB1MtS1nPW7Qa7G9sBqrco9BqxFIjzPispHhuCI5AlGBhgH5vRG5o+N1rdhWUI0nL01E504Nov9KizNCqxHYfKSSRaoHLFJ0XlarRGZRDZbuLMFnO4rR3YEBXjoN/vWTCb1+7nmzkzB/aS5azJaTjxn0Wrx4w2hcNzYSOSW1WLOvDGv2leEPK/fhhVX7MHtUBB6YFo8JsUH8h5+on1buLoWU4Nl61C1fTx3GRgdgyxFuOO8JixT1qKSmGZ/vKMbSbBNKalrg7aHttkQBwLG61j69xol9UCcuFUYGGjBvdtLJx1MGByFlcBB+ecVwFFY24bPMYny87Si+3nMcY2MC8cC0eFyZHAE9594Q9cmXOaVIjvJHQqiv6ijkoKYMCcHr3x9BY1sHfD1ZG87E/yN0Gikldh6twbubCvHN3uOQUmLq0BA8ffkwzB4VgVmvbOz2UlxkPy63zU2JuqCN5XEhPvjVFcPx+MyhWJJVgnd/LMQTn2QjKtCA+VcNx9WjB3GFiqgXCiubkFNSh2evGq46CjmwyUOC8Y/1h7GjoBozhvMw6zOxSBEAwGyx4us9x/HOpgLkFNfC30uHn14Uj7snx522J6mnS3HzZifZLau3hw53TY7DTybGYt2Bcry85iAe+zgbH8QX4flrR2JUZIDdshA5sy9zSgEA14zhZT3q2YTYIHhoNdiSX8Ui1Q0WKTdntlixLNuEf6w7jKPVzYgP8cHv54zCjeOj4dPNEu75LsXZk0YjcNnIcMwYHoZPdxzFX1bn4dq/b8Jt6YPx9KxhCPb1tHsmImchpcSKnFKkxxn7taJMrs9Lr8X42EDOk+oBi5Sb6jhRoNYfRlFVM5Kj/PHmXRNw2Yjw895pd6GX4uxFqxH4ycRYXDM6Eq+uPYgPthRhZU4p/nj9aG6gJerBgeMNOFTeiD/MTVYdhZzA5IQQvLr2IGqb2zmO5gzcoetmrFaJjGwTLnvle8xbvBu+njq8dXcqvnxsGi4fFeHUU40DvPV4/tpR+ObJizAkzBdPfJKNpz/PQWNbh+poRA5nRU4ptBqBq5IjVEchJzBlaDCkBLYVVKuO4nC4IuVGNh+uxJ++3o89pnqMGNS5AjVrZLjLbdBODPfDFw9Nxt/WHsI/1h9GZlE1XrstBeNiAlVHI3IIUkqs2FWKaUNDeAmcLsjY6EAY9FpsOVKF2aNYvk/FFSk3kHe8Aff+ZzvueHsbaprMePXWcVj1eOcKlKuVqBN0Wg3+9/IkfPrgZHRYJG56fTP+uf4wrNaeBjgQuY+dR2tgqm3hpW+6YB46DVLjgrhPqhssUi6ssrEN85fuxpWvbURWUQ3mXzkca5++GHNTopz6El5vpMcb8dWTF+GK5AgsXJ2Hhxdlobmdl/rIva3YVQpPnQaXjwpXHYWcyJQhIThY1oiKhjbVURwKL+25ILPFig+2FOHV7w6ipd2Ce6bE4YmZiQjycc8NggEGPf5+ewomxAbhDyv34ZZ/b8E796Qh3N9LdTQiu+uwWLEq9xhmDg+Dn5dedRxyIlOGBAMAtuRXcTXzFFyRcjE/HKrAla/9gD+s3IeUwUH45ucX4flrR7ltiTpBCIH7psbjrbtTkV/RhDn/+BF7S+tUxyKyuy35VahsbOcXQuq15KgA+HnqsDWfx8WcikXKRRRXN+PBDzJx1zvbYbZY8fbdqXj/vjQMDfNTHc2hXDoiHIsfngIhgJvf2ILv9pWpjkRkVyt2lcLXU8fBitRrWo1AalwQtrFInYZFysm1dVjwj3WHMOuv3+OHQ5WYNzsJ3z41HZe54N14tjIy0h/LH52KIaG++NmHmfh421HVkYjsotVswTd7jmP2qAh46bWq45ATmpQQjCMVTdwndQrukXJiGw9W4PkVe1FQ2YQrkyPwm2tGckLxBQrz98JnD03Cox/txLPLctFhteLuyXGqYxENqA155Who68DcFF7Wo76ZmNC5T2pbQRWPFurCFSknVFrbgkcWZeHud7cDAN6/Px2v3zmBJaqXvD10eKNrltZvl+/Fu5sKVEciGlAZ2aUI8fXE5K4vhkS9lRzpDx8PLbblczDnCVyRciJmixXvbirAa2sPwWKVeHrWMDx4cQI8dVyi7ytPnRb/vGM8nvgkG79fuQ8dVisenD5EdSwim6trMWNdXjnuSB8MnZbfQ1Pf6LQapMYZueH8FCxSTmJrfhV+u3wPDpY14rIRYXj+2lGIMXqrjuUSPHQa/P2OFPz8s13401cHYLZIPDpjqOpYRDa1eu9xtHdYMWccL8dQ/0xMMOKlb/JQ1djGyfhgkXI4GdkmLFydh9LaFkQGGvDwxQnIPlqLpdkmRAUa8NbdqZg1kkP0bE2v1eC1W8dBpxFYuDoPQgD/cwnLFLmOFbtKERvszaOSqN8mxndeGt5eUI0rRw9SnEY9FikHkpFtwvyluWgxWwAAptoW/Gb5Xmg1Ao/OGILHZiTC4MHLeANFp9XglVvGQUrgpW/yEOzjgVvTBquORdRv5fWt2HykEo/NGMq7eanfxkQHwKDXYmt+FYsUWKQcysLVeSdL1KmCfTwwb/ZwBYncj1Yj8Jebx6KmuR3zl+bC6OPJFUByeit3H4NVAtfxsh7ZgF7bee7etgJuOAd4155DMdW2dPs453XYl4dOgzfunIDRUQF47OOdyCzkPxbk3JbvMmFUpD8H9JLNTEoIxoHjDahualcdRTkWKQfQarbgXxsOo6cFd441sD8fTx3evTcNUYEG3P/eDuQdb1AdiahPCiqbkFNSh7njolRHIRfS1nX1ZPwf1mDqgnXIyDYpTqQOi5RCUkp8s+c4Lv/rRrz0TR5GRfnDU3f6p8Sg12Le7CRFCd1bsK8n3r8/HV56Le5+dxtKappVRyLqtRW7SiEEcM1Y7mUh28jINuHNjfknf22qbcH8pbluW6ZYpBTZW1qHn7y9DQ8vyoKXXoNFD0zEyscvwp9vHIOoQAMEgKhAA168YTTmpvA7SVVijN54//50NLdbcP97O9DY1qE6EtEFk1JieY4JE+ONGBTAlW2yjYWr89DaYT3tsRazBQtX5ylKpBY3m9tZcXUzXv42Dxm7ShHorccf5ozC7acMyJubEsXi5GBGDPLHnRNj8fr3R5D8/GpEBnjhl1cM5+eJHN7e0nrkVzThZxclqI5CLqS0h/28PT3u6lik7KS6qR3/WHcYi7YWQQjgkUuG4OGLhyDAoFcdjc4jI9uE9zYXnvx1aV0r5i/NBQCWKXJoGdkm6LUCVyXzsh7ZTmSgodubo9x1Py+LlA2dOUxz3uwkzBgehvd+LMTbP+Sjqb0DN0+IwVOzhiEiwEt1XLpA3Y2lOLGMzSJFjspilViRU4pLksIQ4M1v2Mh25s1OOm3mIeDe+3lZpGyku2Gav/giBzqtQKvZistHhmPe7CQkhvP2Y2fT03J1T+MqiBzB5iOVKG9oww0s+2RjJ76BXLg6D6baFui1wq3387JI2Uh3qxYdVgmdVmDVE9MwKjJAUTLqr56WsTWic2J0mD9XF8nxLMs2wc9LhxnDw1RHIRd0Yj/vX9ccxN/WHXLrP2e8a89GelqdaDNbWaKc3LzZSTDoTz+ax1OngU6rwcOLstB+xt0rRKo1t3dg9Z7juGbMIHjpeawUDZxJCcGQEm49uJhFqh+sVon1B8px1zvbenwfd91850rmpkThxRtGnzaW4s83jsErt4zFzqO1eOmbA6ojEp1mzb4yNLVbOISTBlzK4EB4aDXYml+lOooyvLTXB8XVzVi604Sl2SUoqmpGmJ8nrh49CGv3l502W8OdN9+5mp7GUuwoqMbbmwqQGmfEFckRCpIRnW1ZtglRgQakxRlVRyEX56XXYlxMILYX1qiOogyL1AVqbOvAV7nHsCSr5ORBjZMTgvHUZcNw1ehB8NBpur1rz10337mLZ68egeziWsxbnIORg/wxONhbdSRycxUNbfjhUCUemp4Ajaang6eIbCc93ojXvz+CprYO+Hi6X61wv99xLxRXN2N9XjnW7i/HlvwqtHdYERfsjadnDcP146MQHXT6F00O03Q/njot/nnHeFz9tx/wPx9nYfHDU7gnhZRaubsUFqvE9fy3iOwkPd6If6w/jJ1Ha3BRYqjqOHZnkyIlhLgCwGsAtADellIusMXz2lt5fSuyi2uxs6gGG/IqkFfWeVBtfIgP7poUi6tGR2D84CAIwe/y6L9ijN54+ZZx+NkHmXhh1X78YW6y6kjkxpZlm5Ac5c9RK2Q342ODoNUIbC+oZpHqCyGEFsA/AcwCUAJghxBihZRyX3+fe6A0tnWguLoZxdXNKKhswu6SOuwqrj15551eK5AWZ8SvU0dg5vAwJIT6Kk5Mjm7WyHA8OD0Bb27MR1q8EdeNjVQdidzQ4fJG7C6pw6+vHqE6CrkRX08dkiP9T257cTe2WJFKB3BYSpkPAEKITwHMAaCsSG3Lr8K3+8rQ3G5BS3sHmtotaGm3oL7VjJKaFlQ3tZ/2/tFBBqQMDsT90+IxLiYQoyL9eXmGem3e7CTsLKrB/CW7MTY6ALHBPqojkZtZvssEjQCLPNldWpwRH2wtQluHBZ469/r6aYsiFQWg+JRflwCYeOY7CSEeBPAgAAwePNgGL9uzvLIGfLr9KAweOvh4amHQa+HtoUWAQY9RkQEYbPRGjNGAwUZvDDZ6I9DbY0DzkHvQazV47fYUXPHqRvz8s1344qHJJw+jJhpoVqvEsmwTpiWGckgs2V16vBFvbyrA7pI6t7tb1BZFqrsNQ/KsB6R8E8CbAJCamnrW223p7slxuHty3EC+BFG3ogIN+NP1o/H4J9n4+7rDeGrWMNWRyE1kHa1BSU0Lnr6cf+bI/k6Up+0F1W5XpGzx7XIJgJhTfh0NoNQGz0vklK4dG4kbUqLw93WHkFXknnsGyP6WZZtg0Gtx+UjOMyP7C/LxQFK4n1vuk7JFkdoBIFEIES+E8ABwG4AVNnheIqf1f3NGISrIgCc/3YWGVrPqOOTiWs0WrMwpxRXJEW45x4ccQ3q8EVmF1eiwuNexWf0uUlLKDgCPAVgNYD+Az6WUe/v7vETOzM9Lj1dvHYfS2hY8v5x/HWhgfbe/DPWtHbhpQrTqKOTG0uONaGq3YN+xetVR7MomO2GllF9JKYdJKYdIKV+wxXMSObsJsUY8PjMRS7NNWJHDq900cBZnlSAywAuTE4JVRyE3lh7/331S7oS3FBENoMdnDkXK4EA8tywXx+paVMchF1Re34qNBytww/hoHglDSoX7eyEu2JtFiohsR6fV4NVbx6HDIvGrJbmQckBvWCU3tCzbBKsEbhjPI2FIvbQ4I3YUVsNqdZ9/61ikiAZYbLAPnrlyODYerMCnO4rP/wFEF0hKicVZJZgQG8QTGMghpMcbUdNsxuGKRtVR7IZFisgO7poUi8kJwfjjyn0oqWlWHYdcRK6pDofKG3HjeG4yJ8cwMb5zn547jUFgkSKyA41G4KWbxgAAfrl4t1ste9PAWZxVAk+dBlePGaQ6ChEAIMZoQIS/l1vtk2KRIrKTGKM3nrt6JDYfqcKibUWq45CTa+uwYEVOKS4fFYEAg151HCIAgBAC6fFGbC+ocps9oSxSRHZ0e3oMLkoMwYtfHUBRVZPqOOTE1u0vR22zmbOjyOGkxxtRVt+Go9XusY2BRYrIjoQQ+PONY6DTCMz7gpf4qO+W7CxBuL8npg0NUR2F6DQT3WyeFIsUkZ1FBhrw22tHYnthNT7cykt81HsVDW1Yn1eB61OioeXsKHIwQ8N8YfTxcJsN5yxSRArcNCEa04eF4s/fHOBdfNRry3eZYLFK3DSBs6PI8QghkBobhB2FLFJENECEEPjT9ckAgGeX7XGbTZnUfydmR42NCcTQMD/VcYi6lR5vRFFVM8rrW1VHGXAsUkSKRAd541dXdA7qXLrTpDoOOYndJXU4cLyBm8zJoaXFde2TcoNVKRYpIoXumhSL1Ngg/H7lPlQ0tKmOQ07g0x3F8NJrMGdcpOooRD0aFekPbw8tdrjBPikWKSKFNBqBBTeOQUu7Bb9bsVd1HHJwTW0dWLHLhKtHR8Lfi7OjyHHptBqMHxyE7YU1qqMMOBYpIsWGhvniycsSsSr3GL7Zc1x1HHJgq3KPoandgtvSY1RHITqvtDgjDhyvR12LWXWUAcUiReQAHpyegJGD/PGb5XtQ1+za/+hQ3322oxgJoT5IjQ1SHYXovNLigiAlsLPItVelWKSIHIBeq8FLN41BdVM7FnxzABnZJkxdsA7xz6zC1AXrkJHNzeju7lBZA7KKanBbWgyE4Owocnwpg4Og0wiX33CuUx2AiDolRwXggWnxeHNjPpZklaDdYgUAmGpbMH9pLgBgbgrnBrmrz3YUQ68VuGE879Yj52Dw0CI5KsDlN5xzRYrIgfz8skRohThZok5oMVuwcHWeolSkUka2CVNeXIu3NxVAqxHYdKhSdSSiC5Yeb8Tukjq0mi2qowwYFikiB+LtoYOlh+GcpbUtdk5DqmVkmzB/aS5K6zqHGraarZi/NJeXeslppMUZ0W6xIqe4VnWUAcMiReRgogIN3T4e2cPj5LoWrs5DyxnfyXN1kpzJiRsjXPm4GBYpIgczb3YSvHSn/9U06LWYNztJUSJSpadVSK5OkrMI8vHAsHBfl54nxSJF5GDmpkRhwY1jEGjoHLgYaNDjxRtGc6O5G+ppFZKrk+RM0uKM2FlUA4vVNc8UZZEickBzU6KQ/dtZSI83wiolpgwNVh2JFPjfWcNw5qADrk6Ss0mPN6KxrQP7j9WrjjIgWKSIHJQQAn+6fjRazVb8YeV+1XFIAT8vHSQAo7cHBDr3z3F1kpzNyQOMXXQMAudIETmwoWG+eOSSIXht7SHcNCEaFw8LVR2J7OjDrUWI8PfCpl/NgE7L73vJOUUGGhAVaMCOwmrcPy1edRyb499MIgf3yCVDkBDig99k7HHpWSx0uoLKJvxwqBJ3TBzMEkVOLz3eiB2F1ZA9jHdxZvzbSeTgvPRa/PH6ZBytbsbf1x1SHYfsZNHWIug0Arel8YBicn5pcUZUNrajoLJJdRSbY5EicgJThoTghvFR+Pf3+ThY1qA6Dg2wlnYLvsgsxuzkCIT5e6mOQ9Rv6fGuO0+KRYrISTx31Qj4eunw3LJcWF30NmLq9GVOKepbO3DXpFjVUYhsYkioL4w+Hthe4HrzpFikiJxEsK8nnr1qBHYU1uDzzGLVcWiASCnxwdZCJIb5YmK8UXUcIpsQQiA1NogrUkSk1s0TopEeb8SLXx9AZWOb6jg0AHJK6rDHVI+7JsdCiDOnSBE5r/R4I45WN6OsvlV1FJtikSJyIp2zpZLR3N6BF1ZxtpQr+nBLEXw8tLies6LIxaR2zZNytVUpFikiJzM0zA8PXzwEy7JN+PFwpeo4ZEM1Te34cncprh8fBT8vveo4RDY1KtIfBr0WO1xsMCeLFJETenTGUMQFe+PXnC3lUr7IKkZ7hxV3cpM5uSC9VoPxsYEud4Bxv4qUEGKhEOKAEGK3EGKZECLQRrmI6By89Fr8ce5oFFQ24V8bjqiOQzZgtUos2noU6XFGDI/wVx2HaECkxRlx4Hg96lrMqqPYTH9XpNYASJZSjgFwEMD8/kciogsxLTEEc8dF4vUNh3G4vFF1HOqn9XnlOFrdjDsnczWKXFd6nBFSAjuPus6qVL+KlJTyWyllR9cvtwKI7n8kIrpQz109Ega9Fs8ty3XJoxfcyds/FGBQgBeuTI5QHYVowIwbHAidRrjUPilb7pG6H8DXNnw+IjqPUD9PzL9qBLYVVGPJTpPqONRHe0x12JJfhXunxEHPc/XIhXl76DAqKsCl7tw7799YIcR3Qog93fyYc8r7PAegA8BH53ieB4UQmUKIzIqKCtukJyLcmhqD1NggvLBqH6qb2lXHoT54d1MBvD20uC19sOooRAMuPS4IOcV1LnOjzHmLlJTyMillcjc/lgOAEOIeANcA+Ik8x7UFKeWbUspUKWVqaGio7X4HRG5OoxF44frRaGjtwJ++4mwpZ3O8rhUrckpxS2oMAgwceUCuLy3OiHaLFbtL6lRHsYn+3rV3BYBfAbhOStlsm0hE1FtJEX742fQELM4qweYjnC3lTD7YUgiLlLh/arzqKER24WqDOft7Mf4fAPwArBFC7BJCvGGDTETUB09emojYYG88t4yzpZxFc3sHPtp2FLNHRmBwsLfqOER2YfTxwNAwXxYpAJBSDpVSxkgpx3X9eNhWwYiod7z0WrzQNVvqn+sPq45DF2DJThPqWsz46UVcjSL3khZnRFZhDSxW57/bmLeHELmQaYkhuCElCm98fwSHyhpUx6FzsFol3t1UgLExgZgQG6Q6DpFdpccHoaGtAweO16uO0m8sUkQu5rmrR8DXU4f5S3NhdYHv9lzVugPlKKhswk+nxUMIoToOkV2lndgn5QLzpFikiFxMsK8nnr1qBDKLavDJjqOq41AP3t6Uj6hAAwdwkluKCjRgUIAXdhQ5/4RzFikiF3TThGhMTgjGgq8PoLy+VXUcOkNuSR225lfj3ilx0HEAJ7khIQTS4ozYUVDt9Kcy8G8wkQsSQuBPN4xGW4cVv/tyr+o4dIZ/rD8Efy8dbk2PUR2FSJm0eCPKG9pwtNq5pyexSBG5qPgQHzx5aSK+yj2O1XuPq45DXfKON2D13jLcOzUe/l4cwEnuK71rn9R2J98nxSJF5MIenJ6AEYP88ZuMPahrMauOQwD+sf4wfDy0uH9qnOooREolhvkiwKBHZqFz75NikSJyYXqtBi/dOAaVjW14kcfHKHekohErd5firslxCPT2UB2HSCmNRiA1NsjpB3OySBG5uNHRAfjZ9AR8uqMYmw/z+BiVXt9wBJ46DQdwEnVJizciv7IJFQ1tqqP0GYsUkRt46rJhiAv2xjNLc9HSzuNjVCiubsaybBNuTx+MEF9P1XGIHMKJeVKZTrwqxSJF5Aa89FosuHEMjlY345U1earjuKXXvz8CrRB4aPoQ1VGIHMboqAB46TXY5sQbzlmkiNzEpIRg3DFxMN7ZVICc4lrVcdzKsboWLM4swc2p0YgI8FIdh8hheOg0SIlx7n1SLFJEbuSZK4fDz0uPG1/fjLhnVmHqgnXIyDapjuXy/v19PqxS4uGLuRpFdKa0eCP2H6tHQ6tz3lnMIkXkRtbtL0dLuwUdXWfwmWpbMH9pLsvUAKpoaMMn24/i+pQoxBi9VcchcjjpcUZYJZDlpMfFsEgRuZGFq/PQbrGe9liL2YKFq7lvaqD8a8NhmC1WPHIJV6OIupMyOBBajXDay3ssUkRupLS2pVePU/8UVzdj0dYi3JoWg4RQX9VxiBySj6cOyVEBTjvhnEWKyI1EBhp69Tj1z8vf5kGrEXjy0mGqoxA5tPS4IOQU16HV7HzjWVikiNzIvNlJMOi1Zz1+4/goBWlc2x5THTJ2leL+qfG8U4/oPNLijGi3WLG7pE51lF5jkSJyI3NTovDiDaMRFWiAADAowAtGHw+syCnloE4be2l1HgK99XiId+oRndeJwZzOuE9KpzoAEdnX3JQozE357wrUliNVuP2trfjzNwfwu+tGKUzmOn48XImNByvw66tHIMCgVx2HyOEF+XhgWLgvthdU49EZqtP0DlekiNzc5CHBuHdKHN7bXIiNBytUx3F6VqvEgq8PICrQgDsnxaqOQ+Q00uKMyCqqgaVrPIuzYJEiIjxz5XAkhvni6S9yUNXovIeHOoKv9hxDrqkO/ztrGLy62Y9GRN1Ljzeisa0D+4/Vq47SKyxSRAQvvRZ/uz0Fdc1m/GrJbkjpXN8ROgqzxYqFq/MwPMLvtMunRHR+J/ZJOdsYBBYpIgIAjBjkj19dORzf7S/Hom1HVcdxSh9tLUJRVTN+dcVwaDVCdRwipxIZaEBUoMHpNpyzSBHRSfdNicPFw0Lxx5X7cKisQXUcp1Le0IqX1xzEtKEhuCQpVHUcIqc0Md6IHYXVTrUqziJFRCdpNAJ/uXksfD11eOLTXU45HE+VF786gDazFb+fMwpCcDWKqC/S4o2obGxHQWWT6igXjEWKiE4T6ueJhTePwf5j9XjpG57BdyE2H6nEsmwTHr44gUfBEPWDM+6TYpEiorPMHB6OeybH4t0fC/DdvjLVcRxae4cVv8nYgxijAf8zY6jqOERObUioD4J9PLDdifZJsUgRUbeSowKg1wr89INMTHzhO2Rkm1RHckhvb8rHkYom/P66ZI47IOonIQRS44KcasM5ixQRnSUj24TfLt8Ls6Vzw2dZQxueWbKbZeoMxdXN+NvaQ7hiVARmDA9THYfIJaTHB6O4ugXH6lpUR7kgLFJEdJaFq/PQcsZG89YOK1765oCiRI7p/77cB40Q+O21I1VHIXIZE+Oda58UixQRnaW0tvvvBEvrWu2cxHGt2VeG7/aX4clLExEZaFAdh8hljBjkDz9PHbaxSBGRszpXMdhdUmu/IA6qqrENzy7LxfAIP9w/LV51HCKXotV07pPiihQROa15s5NgOGPjtJdOgyBvPR5ZtBPVTe2KkqknpcSvluSirtmMv946Dnot/xklsrX0+GAcLm9EpROc/cl/AYjoLHNTovDiDaMRFWiAABAVaMCCG8fgvfvSUdHYhoc+zERbh3sO6/x4+1F8t78Mv7wiCSMG+auOQ+SS0rv2Se1wglUpneoAROSY5qZEdXvw7ss3j8Xjn2Tjl4t349Vbx7nVFO/D5Y34w8p9uCgxBPdP5SU9ooEyOioABr0W2wqqceXoQarjnJNNVqSEEL8QQkghRIgtno+IHNe1YyMxb3YSlu8qxV+/O6Q6jt20d1jx88+yYdBr8Zebx0LDQ4mJBoyHToPxsYFOseG830VKCBEDYBYAHhdP5Cb+55IhuHlCNP629hCWZJWojmMXr6w5iD2meiy4cQzC/b1UxyFyeelxwThwvB51zWbVUc7JFitSfwXwSwDOc1QzEfWLEAIvXD8aU4YE45mlu7HlSJXqSANq85FK/HvjEdyeHoPZoyJUxyFyCxMTjJASyCxy7FWpfhUpIcR1AExSypwLeN8HhRCZQojMioqK/rwsETkAD50Gr985AbHBPnh4URYOlzeojjQgSmqa8cQnuxAX7IPfXMPBm0T2Mi4mEB5ajcNf3jtvkRJCfCeE2NPNjzkAngPw2wt5ISnlm1LKVCllamhoaH9zE5EDCDDo8Z9706DXanD7W9twpKJRdSSbqm814/73dqCtw4K37p4Abw/en0NkL156LcbGBDh/kZJSXialTD7zB4B8APEAcoQQhQCiAewUQnDdm8iNxBi98cnPJsJqlbjjra0orGxSHckmOixWPPZxNvIrmvDGnRMwNMxPdSQitzMxPhh7THVoautQHaVHfb60J6XMlVKGSSnjpJRxAEoAjJdSHrdZOiJyConhfvj4Z5Ngtkjc/tZWHK1qVh2pX6SUeH7FXmw8WIE/zk3G1KG8IZlIhfR4IyxWiayiGtVResSBnERkE0kRflj0wES0mC24/a2tKK523jL1zqYCfLTtKB66OAG3pQ9WHYfIbU2IDYJWIxz6uBibFamulalKWz0fETmfkZH+WPTARDS0mnH7W1tRUuN8Zerbvcfxwlf7ccWoCPxq9nDVcYjcmo+nDslRAdhW4Lh3BnNFiohsKjkqAIt+OhF1LWZc/6/NTnXI8bd7j+OxT7IxJioAf711HIduEjmAifFG5BTXodXsmMdSsUgRkc2NiQ7EkkemwEOrwS3/3oJv9hxTHem8FmeV4JGPdmLEIH+8d186DB7a838QEQ24ifFGtFus2FVcqzpKt1ikiGhADAv3Q8ajUzFikD8eXrQTb3x/BFI65tzedzYV4Bdf5GBSghEf/3Qignw8VEcioi6psUYIAWzLd8x9UixSRDRgQv088cnPJuGaMYOw4OsDeGZJLto7rKpjnSSlxCvf5uEPK/fhilERePfeNPh4clYUkSMJ8NZjeIQ/thc65j4pFikiGlBeei3+dlsKHp85FJ9lFuOWf2/B4XL1gzvbOiz4zfI9+Nu6w7g1NQb/uCMFnjpeziNyRBPjjcgqqnGob8RO4LdeRDTgNBqBpy9PQlKEH36dsQdX/e0H/OLyYXhgWgK0dtjQnZFtwsLVeSitbUFkoAF3pA/Gl7tLceB4Ax6anoBnrhwOIbixnMhRTYw34r3Nhcg11WJCrFF1nNNwRYqI7OaaMZH49qnpuGRYKP701QHc/MbmAT9WJiPbhPlLc2GqbYEEYKptwcJv82CqbcE796Ri/lUjWKKIHFx6fGd52uqA+6RYpIjIrsL8vPDvuybgtdvG4UhFE6567Qf8be0h1LWYB+T1Fq7OQ0s3t037eOhw6YjwAXlNIrKtYF9PJIX7YWu+4+2TYpEiIrsTQmDOuCis+d/pmJEUhlfWHMS0Beuw4OsDKK9vtelrmWpbun28zMavQ0QDa1KCEZmFjrdPinukiEiZMD8vvHHXBOwtrcMb3+fjzY1H8O6mAtw4IRr3TY1DYphvry67ndgLZaptQbCPB0L8PHt838hAgy1+C0RkJ5OHBOP9LUUOt0+KRYqIlBsVGYC/356CX1w+DG9uzMcXWSX4ZPtRhPt7YnJCMKYMCcHkIcGIMXp3+/FmixX//v4IXlt7CGZL56yqqqZ2VDW1Y1xMAA4ca0DrKd/FGvRazJudZJffGxHZRnp8MIDOfVKOVKSEigF5qampMjMz0+6vS0TOobyhFd/tK8eW/CpsOVKJysZ2AIDRxwM+nlp46rTw1GngqdPAbJHIK2vocbk/KtCAebOTTrtrb97sJMxNibLnb4mIbOCKVzci1M8THz4w0a6vK4TIklKmdvc2rkgRkcMJ8/PCHRMH446JgyGlxOHyRmw+UoUDx+vRZraircOKtg4LWs1WCAHcMzkWb/1Q0O1zlda2YG5KFIsTkQuYlBCMz3YUo73DCg+dY2zzZpEiIocmhEBiuB8Sw/3O+X5f5R7vdmM590IRuY5JCcF4b3MhdpfUIjXOMS7vOUadIyLqp3mzk2DQnz6ZnHuhiFzLxJPzpBxnDAKLFBG5hLkpUXjxhtGICjRAoHNv1Is3jOYlPSIXEuTjgeERfg41mJOX9ojIZXAvFJHrm5QQjE93HHWYfVLqExARERFdoMlDgtFqtmJ3Sa3qKABYpIiIiMiJTIw3QghgyxHH2CfFIkVEREROI9DbA8Mj/LG1gEWKiIiIqNcmJRiRVVSDto6zDyS3NxYpIiIiciqTE07sk6pTHYVFioiIiJxLugPtk2KRIiIiIqcS6O2BERH+DjGYk0WKiIiInM6khGCH2CfFIkVEREROZ/KQYLR1WJFTrHafFIsUEREROZ30OCNSY4PQYbUqzcEjYoiIiMjpBHjrsfiRKapjcEWKiIiIqK9YpIiIiIj6iEWKiIiIqI9YpIiIiIj6iEWKiIiIqI9YpIiIiIj6iEWKiIiIqI/6XaSEEI8LIfKEEHuFEC/ZIhQRERGRM+jXQE4hxAwAcwCMkVK2CSHCbBOLiIiIyPH1d0XqEQALpJRtACClLO9/JCIiIiLn0N8iNQzARUKIbUKI74UQaT29oxDiQSFEphAis6Kiop8vS0RERKTeeS/tCSG+AxDRzZue6/r4IACTAKQB+FwIkSCllGe+s5TyTQBvAkBqaupZbyciIiJyNuctUlLKy3p6mxDiEQBLu4rTdiGEFUAIAC45ERERkcvr12ZzABkAZgLYIIQYBsADQOX5PigrK6tSCFHUz9c+n5ALyUJ2x8+L4+HnxDHx8+J4+DlxTPb4vMT29AbRzVW4CyaE8ADwLoBxANoB/EJKua7PT2hDQohMKWWq6hx0On5eHA8/J46JnxfHw8+JY1L9eenXipSUsh3AnTbKQkRERORUONmciIiIqI9cuUi9qToAdYufF8fDz4lj4ufF8fBz4piUfl76tUeKiIiIyJ258ooUERER0YByySIlhLii6yDlw0KIZ1TncXdCiBghxHohxP6uw62fVJ2JOgkhtEKIbCHEStVZqJMQIlAIsVgIcaDr78xk1ZkIEEI81fXv1x4hxCdCCC/VmdyNEOJdIUS5EGLPKY8ZhRBrhBCHuv4bZO9cLlekhBBaAP8EcCWAkQBuF0KMVJvK7XUAeFpKOQKdU/Af5efEYTwJYL/qEHSa1wB8I6UcDmAs+PlRTggRBeAJAKlSymQAWgC3qU3llt4DcMUZjz0DYK2UMhHA2q5f25XLFSkA6QAOSynzu8YzfApgjuJMbk1KeUxKubPr5w3o/MIQpTYVCSGiAVwN4G3VWaiTEMIfwHQA7wCdI2aklLVKQ9EJOgAGIYQOgDeAUsV53I6UciOA6jMengPg/a6fvw9grj0zAa5ZpKIAFJ/y6xLwi7bDEELEAUgBsE1xFAJeBfBLAFbFOei/EtB5xNZ/ui65vi2E8FEdyt1JKU0A/gLgKIBjAOqklN+qTUVdwqWUx4DOb9oBhNk7gCsWKdHNY7w10QEIIXwBLAHwcyllveo87kwIcQ2AcillluosdBodgPEAXpdSpgBogoJLFXS6rn03cwDEA4gE4COE4DBqAuCaRaoEQMwpv44Gl2CVE0Lo0VmiPpJSLlWdhzAVwHVCiEJ0Xv6eKYRYpDYSofPfrxIp5YkV28XoLFak1mUACqSUFVJKM4ClAKYozkSdyoQQgwCg67/l9g7gikVqB4BEIUR811mAtwFYoTiTWxNCCHTu+dgvpXxFdR4CpJTzpZTRUso4dP4dWSel5HfYikkpjwMoFkIkdT10KYB9CiNRp6MAJgkhvLv+PbsUvAnAUawAcE/Xz+8BsNzeAfp11p4jklJ2CCEeA7AanXdWvCul3Ks4lrubCuAuALlCiF1djz0rpfxKXSQih/U4gI+6vhHMB3Cf4jxuT0q5TQixGMBOdN6FnA1OObc7IcQnAC4BECKEKAHwPIAFAD4XQjyAzsJ7s91zcbI5ERERUd+44qU9IiIiIrtgkSIiIiLqIxYpIiIioj5ikSIiIiLqIxYpIiIioj5ikSIiIiLqIxYpIiIioj5ikSIiIiLqo/8Hg9t/4mXzS3oAAAAASUVORK5CYII=\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "x = np.linspace(0, 10, 100)\n", "\n", "plt.figure(figsize=(10, 6))\n", "plt.plot(x, x*np.sin(x), label=\"Ground truth\")\n", "plt.scatter(X, t)\n", "plt.legend()\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Q:** Apply the `np.polyfit()` function on the data and visualize the result for different degrees of the polynomial (from 1 to 20 or even more). What do you observe? Find a polynomial degree which clearly overfits." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Q:** Plot the mean square error on the training set for all polynomial regressions from 1 to 20. How does the training error evolve when the degree of the polynomial is increased? What is the risk by taking the hypothesis with the smallest training error? " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Simple hold-out cross-validation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You will now apply **simple hold-out cross-validation** to find the optimal degree for the polynomial regression. You will need to separate the data set into a training set $S_{\\text{train}}$ (70% of the data) and a test set $S_{\\text{test}}$ (the remaining 30%). \n", "\n", "The data (X, t) could be easily split into two sets of arrays using slices of indices, as the data is already randomized:\n", "\n", "```python\n", "N_train = int(0.7*N)\n", "X_train, t_train = X[:N_train], t[:N_train]\n", "X_test, t_test = X[N_train:], t[N_train:]\n", "```\n", "\n", "A much more generic approach is to use the library `scikit-learn` (), which provides a method able to split any dataset randomly. \n", "\n", "You can import the method `train_test_split()` from its module:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "from sklearn.model_selection import train_test_split" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The doc of the function is available at: .\n", "\n", "**Q:** Use scikit-learn to split the data into the corresponding training and test sets. Train each polynomial from degree 1 to 20 on $S_{\\text{train}}$ and plot the generalization error on $S_{\\text{test}}$. Which degree of the polynomial gives the minimal empirical error? Why? Run the cross-validation split multiple times. Do you always obtain the same optimal degree? " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## k-fold cross-validation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "As we only have 16 samples to learn from, it is quite annoying to \"lose\" 5 of them for the test set. Here we can afford to use **k-fold cross-validation**, where the cross-validation split is performed $k$ times:\n", "\n", "* The dataset is split into $k$ subsets of equal size (if possible).\n", "* Each subset is iteratively used as the test set, while the $k-1$ other ones are used as a training set.\n", "* The final empirical error is the average of the mse on all subsets.\n", "\n", "It would be possible to make the splits using indices too, but it is much easier to use `scikit-learn` once again. You can import the `KFold` class like this:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "from sklearn.model_selection import KFold\n", "\n", "k = 4\n", "kf = KFold(n_splits=k, shuffle=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "`n_splits` corresponds to $k$: how many times the dataset is split. We can take $k=4$ for example (4 subsets of 4 samples).\n", "\n", "**Q:** Check the doc of `KFold` (). Print the indices of the examples of the training and test sets for each iteration of the algorithm. Change the value of $k$ to understand how it works." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Q:** Apply k-fold cross-validation on the polynomial regression problem. Which polynomial degree is the best? Run the split multiple times: does the best polynomial degree change?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Q:** Change $k$ to $N$. How stable are the results between two runs?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Q:** Regenerate the data with a noise equal to 0.0 and re-run all experiments. What does it change?" ] } ], "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.8.5" } }, "nbformat": 4, "nbformat_minor": 4 }