{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "## Introduction to Machine Learning: Homework 1\n", " \n", " \n", "__Given date:__ Tuesday October 6\n", "\n", "__Due date:__ Tuesday October 20\n", "\n", "__Total:__ 25pts + 4pts\n", " \n", "In this first homework we review gradient descent, linear regression and classification. The total is on 20pts with a 5pts bonus so that you can score 25/20 if you get the maximum in every exercise. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Question 1. Gradient descent on the Ridge loss (5pts)\n", "\n", "Consider the data shown below. In this first exercise we want to learn the quadratic function that best fits this data. " ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD8CAYAAABn919SAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi40LCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcv7US4rQAAIABJREFUeJzt3Xd0VGXixvHvmwaEAKEkEEijQ6QT\nkaIIoohiwV5iXdfoLuyqy7oWbOuKq7sq6lpjL7GtorBiBbGgCASE0ENLICEkoYWE9OT9/THRHyKQ\nEDK5U57POTkzc3OH+wyc88zLLe811lpERMT7BTgdQEREGocKXUTER6jQRUR8hApdRMRHqNBFRHyE\nCl1ExEeo0EVEfIQKXUTER6jQRUR8RFBTbqxDhw42Pj6+KTcpIuL1li5dutNaG1HXek1a6PHx8aSl\npTXlJkVEvJ4xJqs+62mXi4iIj1Chi4j4CBW6iIiPUKGLiPgIFbqIiI9QoYuIuEtqKsTHQ0CA6zE1\n1a2ba9LTFkVE/EZqKiQnQ0mJ63VWlus1QFKSWzapEbqIiDtMm/b/Zf6zkhLXcjdRoYuIuMPWrUe3\nvBHUWejGmObGmMXGmBXGmNXGmL/XLu9qjFlkjNlojHnXGBPitpQiIt4mNvboljeC+ozQy4FTrLUD\ngUHABGPMcOBhYIa1tgewB7jObSlFRLzN9OkQGvrrZaGhruVuUmehW5fi2pfBtT8WOAV4v3b5a8Ak\ntyQUEfFGSUmQksKOPgNY2akHxMVBSorbDohCPc9yMcYEAkuBHsDTwCZgr7W2qnaVbKCLWxKKiHir\npCReaDOY137I5Mc7x9EhrJlbN1evg6LW2mpr7SAgGhgG9KnvBowxycaYNGNMWkFBQQNjioh4n+Ly\nKt5bso0z+0e5vczhKM9ysdbuBeYDI4BwY8zPI/xoIOcw70mx1iZaaxMjIuqczldExGe8n7aNovIq\nfndi1ybZXn3OcokwxoTXPm8BnAasxVXsF9audjUwy10hRUS8TU2N5dUfMhkcG86gmPAm2WZ9RuhR\nwHxjTDqwBPjSWvsxcBvwF2PMRqA98JL7YoqIeJf56/PJ3FXC70Y1zegc6nFQ1FqbDgw+xPLNuPan\ni4jIQV7+fgudWjdnQr9OTbZNXSkqItLI1u3Yx/cbd3HVyDiCA5uuZlXoIiKN7JUFmTQLCuCy4913\nVeihqNBFRBrRzuJyPlyewwVDo2nbsmlnRFGhi4g0ojd/zKKiqqZJD4b+TIUuItJIyiqreWNhFqf0\niaRHZFiTb1+FLiLSSGYv386u/RX8vokuJDqYCl1EpBFYa3lxwWb6RrVmRPf2jmRQoYuINILvNuwk\nI6+Y607sijHGkQwqdBGRRvDigi1EtGrG2QOjHMugQhcROUZrc/fxbUYB14yMp1lQoGM5VOgiIsfo\nxe+2EBoSSNIJTXsh0cFU6CIix2BHYRmzV+RwcWIM4aHO3lpZhS4icgxe/SGT6hrryIVEB1Ohi4g0\nUHF5FW8tyuKMflHEtg+t+w1upkIXEWmg95ZsY19ZFb8/yfnROajQRUQapLK6hpcWbGFYfDsGx7Z1\nOg6gQhcRaZA56bnk7C3lhpO7OR3lFyp0EZGjZK3luW820TMyjLG9I52O8wsVuojIUfp2w07W7Sgi\neXQ3AgKcucz/UFToIiJH6flvNtGpdXPOHdTF6Si/okIXETkK6dl7+WHTLq47sSshQZ5VoZ6VRkTE\nwz3/zWZaNQ/i0mExTkf5DRW6iEg9bdm5n09W5XLF8DhaNQ92Os5v1FnoxpgYY8x8Y8waY8xqY8xN\ntcvvM8bkGGOW1/6c6f64IiLOef6bTYQEBnjEZf6HElSPdaqAqdbaZcaYVsBSY8yXtb+bYa19xH3x\nREQ8w47CMj5Yls2lx8cS0aqZ03EOqc5Ct9bmArm1z4uMMWsBzzq0KyLiZi8t2EyNheTRnnMh0cGO\nah+6MSYeGAwsql00xRiTbox52RjjGde+iog0sr0lFaQu2srZA6KIaef8JFyHU+9CN8aEAR8AN1tr\n9wHPAt2BQbhG8I8e5n3Jxpg0Y0xaQUFBI0QWEWlary/MoqSimhvHdHc6yhHVq9CNMcG4yjzVWjsT\nwFqbZ62tttbWAC8Aww71XmttirU20VqbGBER0Vi5RUSaRElFFa98v4VT+kTSp1Nrp+McUX3OcjHA\nS8Baa+1jByw/8E6o5wGrGj+eiIiz3lq0lT0llUwe28PpKHWqz1kuo4ArgZXGmOW1y+4ELjPGDAIs\nkAnc4JaEIiIOKausJuXbzYzo1p6hcZ5/mLA+Z7ksAA41+8wnjR9HRMRzvL80m/yicmZcMsjpKPWi\nK0VFRA6hsrqG577ZxKCYcEZ2b+90nHpRoYuIHMLs5dvJ3lPKlLE9cB1K9HwqdBGRg1TXWJ75eiN9\no1ozrq/n3MCiLip0EZGDfLoql00F+5k8trvXjM5BhS4i8is1NZb/zNtIj8gwzuwXVfcbPIgKXUTk\nAF+syWN9XhF/OqWHR91erj5U6CIitay1PDlvA107tOSsAZ2djnPUVOgiIrXmrc1nTe4+Jo/tQaCX\njc5BhS4iArhG5//5agMx7Vpw7iDvG52DCl1EBICv1xewIruQyWN6EBzondXonalFRBqRtZbH52YQ\n3bYFFwyNdjpOg6nQRcTv/Tw6/9Mp3js6BxW6iPg5ay0zakfn5w/x3tE5qNBFxM/NX59Pug+MzkGF\nLiJ+zLXvfINPjM5BhS4ifmzeWt8ZnYMKXUT8VE2N5dEvM4hrH+oTo3NQoYuIn/ps9Q7W5u7jpnE9\nfWJ0Dip0EfFD1TWWGV9m0D2iJecO6uJ0nEajQhcRv/Nx+nY25Bdzy2m9vHLOlsNRoYuIX6mqruGJ\nuRvo06mV1813XhcVuoj4lZnLcti8cz+3nNbL6+Y7r4sKXUT8RnlVNU/M28DA6DaMT+jodJxGV2eh\nG2NijDHzjTFrjDGrjTE31S5vZ4z50hizofaxrfvjiog03NuLtpKzt5RbT+/jVfcKra/6jNCrgKnW\n2gRgODDZGJMA3A7Ms9b2BObVvhYR8UglFVU8NX8jI7q1Z1SP9k7HcYs6C91am2utXVb7vAhYC3QB\nzgVeq13tNWCSu0KWV1Uza3kO1lp3bUJEfNwr32eys7iCv57e2ydH53CU+9CNMfHAYGAR0NFam1v7\nqx2A23ZIzUnP5aZ3lvPFmjx3bUJEfFhhSSXPf7OJU/tGMjTOd/cO17vQjTFhwAfAzdbafQf+zrqG\nzoccPhtjko0xacaYtIKCgqNPmJrKOReMpvuubfz7qY+pejP16P8MEfFrz36ziaLyKqaO7+10FLeq\nV6EbY4JxlXmqtXZm7eI8Y0xU7e+jgPxDvddam2KtTbTWJkZERBxdutRUSE4mKHMLt377OhvbRDHz\n8bddy0VE6mFHYRmvfL+FSYO60DeqtdNx3Ko+Z7kY4CVgrbX2sQN+NRu4uvb51cCsRk83bRqUlABw\nesZCBm5fz4xhF1J2972NvikR8U1PzMugxlr+clovp6O4XX1G6KOAK4FTjDHLa3/OBB4CTjPGbABO\nrX3duLZu/eWpAW775lVyW0fwRsSARt+UiPieTQXFvJeWTdIJccS0C3U6jtsF1bWCtXYBrj49lHGN\nG+cgsbGQlfXLy5FbVzJ681KeHnkJl5RV0rp5sFs3LyJeLDWVRz7ZQvOOvZly6yVQdAckJTmdyq08\n+0rR6dMh9Nffqn9b9C57m4Xx3NebHAolIh4vNZXldz/MpzGDuX7xh3TIWA3JyT5//M2zCz0pCVJS\nIC4OjIG4OPo9eCeTBnXmpQVbyC0sdTqhiHggO20aDw6/nA779/D7JR+5FpaUuI7L+TDPLnRwlXpm\nJtTUuB6Tkpg6vjfWwmNfZDidTkQ80LzgjiyO7c/NC94irOKAgd8Bx+V8kecX+iHEtAvl6pFxvL8s\nm3U79tX9BhHxG1XVNTx06vV027WNS9K/+PUvY2OdCdVEvLLQASaP7UGrZkE89Ok6p6OIiAd5Ly2b\njW2iuO3Hdwiuqf7/X4SGuo7L+TCvLfTw0BCmnNKDr9cX8P3GnU7HEREPsL+8ihlzM0iMa8v4267/\n1fE3UlJ0losnu2pEPF3CWzB9zlqqazRxl4i/S/l2MwVF5dxxZl/MFb89/ubrvLrQmwcHctsZfViT\nu48PlmU7HUdEHLSjsIyUbzczcUCUT0/AdSReXegAZw+IYlBMOI98vp6Siiqn44iIQx75Yj3VNZbb\nJ/RxOopjvL7QjTHcfVZf8ovKSfl2s9NxRMQBq3IK+WBZNteOiveLS/wPx+sLHWBoXDsm9o/i+W82\nk7evzOk4ItKErLVMn7OW8BbB/HFsD6fjOMonCh3gtgl9qK6x/Pvz9U5HEZEmNHdtPgs37+KW03rR\npoV/z+/kM4Ue2z6Ua0+M5/2l2aRn73U6jog0gfKqaqbPWUOPyDAuG+bbFw3Vh88UOsCUsT3oEBbC\n/f9bo/uPiviB137IJHNXCXdN7EtwoE/VWYP41N9Aq+bB/HV8b9Ky9vBxem7dbxARr7WzuJz/zNvI\n2N4RjOkd6XQcj+BThQ5wUWIMCVGteejTdZRVVtf9BhHxSo9+sZ7SymruOivB6Sgew+cKPTDAcM/Z\nCeTsLeX5b3Qao4gvWr29kHeWbOOqEfF0jwhzOo7H8LlCBxjerT0T+0fx7DcbydmrOdNFfIm1lr/P\nXkPb0BBuGtfT6TgexScLHeDOiX0BeHDOWoeTiEhjmr1iO4szd3Pr6b1pE+rfpykezGcLvUt4C/44\npgdzVubywybNxijiC/aXV/HgJ2vp36UNFyfGOB3H4/hsoQMkj+5GdNsW/H32Gqqqa5yOIyLH6Kn5\nG8nbV8595xxHYMDh7l3vv3y60JsHB3LXxATW5xXxxo9ZTscRkWOwZed+XvxuM+cP6eK3synWxacL\nHeD04zpyUs8OPPZFBgVF5U7HEZEGsNby9/+tpllQoF/PpliXOgvdGPOyMSbfGLPqgGX3GWNyjDHL\na3/OdG/MhjPG8PdzjqOsqpp/fqoDpCLe6Is1eXy9voCbT+1JZOvmTsfxWPUZob8KTDjE8hnW2kG1\nP580bqzG1S0ijOTR3Zi5LIfFW3Y7HUdEjkJJRRX3/28NfTq14pqR8U7H8Wh1Frq19lvA61tw8tge\ndAlvwT2zVukAqYgXeeor1/Uk95/bjyDN13JEx/K3M8UYk167S8bjj1CEhgRxz9kJrNtRxGsLdYBU\nxBtsKijmhdoDocO6tnM6jsdraKE/C3QHBgG5wKOHW9EYk2yMSTPGpBUUFDRwc41jfEJHxvSO4LEv\n1rOjUDfCEPFk1lrumbWK5sGB3HFGX6fjeIUGFbq1Ns9aW22trQFeAIYdYd0Ua22itTYxIiKioTkb\nhTGG+8/pR1WN64i5iHiuWcu38/3GXfxtQh8iWjVzOo5XaFChG2OiDnh5HrDqcOt6mtj2ofx5XE8+\nXbWDr9blOR1HRA6hsKSSB+asYVBMOEm6cUW91ee0xbeBhUBvY0y2MeY64F/GmJXGmHRgLHCLm3M2\nqutP6kaPyDDumbWa0gpNsSviaR76bB17Sip58Lz+BOiK0Hqrz1kul1lro6y1wdbaaGvtS9baK621\n/a21A6y151hrvepuEiFBAUyf1I/sPaU8MW+D03FE5ABLs3bz9uKtXDsynoTOrZ2O41X89hygE7q1\n56Kh0bzw3WbW5u5zOo6IABVVNdw5cxVRbZpzy2m9nI7jdfy20AHuPLMv4S2Cuf2DdKprdA9SEael\nfLuJ9XlF/OPcfrRsFuR0HK/j14XetmUI95ydwIrsQl5fmOl0HBG/trmgmCe/2sjE/lGcmtDR6The\nya8LHeCcgZ05uVcE//58ve5uJOKQmhrLHTNX0jwogHvP0T1CG8rvC90YwwOT+mEt3P3RKqzVrheR\npvZe2jYWbdnNnWf2JbKVJt9qKL8vdICYdqFMHd+Lr9blM2v5dqfjiPiVvH1lTP9kLSd0bcclx+su\nRMdChV7r2lFdGRwbzt//t5qdxZo3XaQpWGuZ9uFKKqtrePiCARijc86PhQq9VmCA4V8XDGB/eTX3\nzta0ACJNYfaK7cxdm89fx/cmvkNLp+N4PRX6AXp2bMWfTunBnPRcPlu1w+k4Ij5tZ3E5981ezaCY\ncK4d1dXpOD5BhX6QG8d0p29Ua+76aBV79lc4HUfEZ907ezX7y6v514UDdMPnRqJCP0hwYACPXDSA\nvSUV3KcZGUXcYk56LnPSc/nzuB706tjK6Tg+Q4V+CMd1bsOUU3owa/l27XoRaWQ7i8u5e9YqBkS3\n4caTuzsdx6eo0A9j8tgeJES15q6PVrJbu15EGoW1lrs+XEVxWRWPXjRQt5RrZPrbPIzgwAAevXgg\nhaWV3D3La6Z7F/Fos1ds57PVO/jL+F701K6WRqdCP4K+Ua25aVxP5qTnMmt5jtNxRLxa3r4y7pm1\nmsGx4Vx/Ujen4/gkFXodbjy5O4Njw7n7o1W6D6lIA1lrufX9dMqrqnn0ooE6q8VNVOh1CAoMYMbF\ng6isttz6/grN9SLSAG/+mMW3GQVMm5hAt4gwp+P4LBV6PcR3aMm0iX35bsNO3vgxy+k4Il5lU0Ex\n0z9Zy8m9IrjiBN0f1J1U6PWUdEIsY3pH8OAna9mYX+R0HBHPlZoK8fEQEEBl12785Zl5NA8O5F8X\naq4Wd1Oh15MxrrleQkOC+PPbyymv0s2lRX4jNRWSkyErC6zliZhRrCgNYnqHvXRsrWlx3U2FfhQi\nWzfn4QsGsCZ3H49+keF0HBHPM20alJQAsCj6OJ4ecTEXpX/JxH/9zeFg/kGFfpROS+jIFcNjSfl2\nMws27HQ6john2boVgMJmLfnLWVOJ27OD++Y+/8tycS8VegNMOzOB7hEtmfrf5bqKVORAsbFYYNrp\nk8kLa8fjHz9Cy8oyiNXB0KZQZ6EbY142xuQbY1YdsKydMeZLY8yG2se27o3pAQ440NOiV3eebLOD\nPfsrufW/OpVR5BfTp/PfoRP5uO9oblmQyqDcDAgNhenTnU7mF+ozQn8VmHDQstuBedbansC82te+\n66ADPWRlcdxN13FnZDHz1uXzyveZTicU8QgbTj2He067kVE71nHj4pkQFwcpKZCU5HQ0v1BnoVtr\nvwV2H7T4XOC12uevAZMaOZdnOeBAzy9KSrh6xq2c2rcj//x0LSuzC53JJuIhyiqrmfLWT7QMbcaM\nJycTWF0FmZkq8ybU0H3oHa21ubXPdwAdGymPZzrMAR2zdSv/vnAAHcKa8ae3l1FUVtnEwUQ8x/0f\nr2F9XhGPXjyQSJ2i6IhjPihqXTuQD7sT2RiTbIxJM8akFRQUHOvmnHG4AzqxsbRtGcITlw5m255S\nbp+5UvvTxS/NXrGdtxZt5YbR3RjTO9LpOH6roYWeZ4yJAqh9zD/citbaFGttorU2MSIiooGbc9j0\n6a4DOwc64EDPsK7tmDq+F3PSczU1gPidjfnF3P5BOkPj2vLX03s7HcevNbTQZwNX1z6/GpjVOHE8\nVFKS68BOXBwYc8gDPTeO7s7Y3hH84+M1rNi218GwIk2ntKKayanLaB4cyFOXDyZYN6xwlKlrF4Ex\n5m1gDNAByAPuBT4C3gNigSzgYmvtwQdOfyMxMdGmpaUdY2TPtWd/BROf/I6AAMOcP51Em9BgpyOJ\nuI21lr/+N52ZP2Xz2rXDGN3LS/8H7gWMMUuttYl1rVefs1wus9ZGWWuDrbXR1tqXrLW7rLXjrLU9\nrbWn1qfM/UHbliE8lTSEvH1l3PzuT9TUaH+6+K53lmzjg2XZ/OmUnipzD6H/HzWyIbFtueesBOav\nL+A/X210Oo6IWyzftpd7Z61mdK8IbhrX0+k4UkuF7gZXDI/j/CFdeHxeBvPXH/Z4sYhX2lVczh/f\nXEpk62Y8cckg3X3Ig6jQ3cAYw/RJ/enTqTU3v7OcrbtK6n6TiBeoqq7hT2//xK79FTx3xVDatgxx\nOpIcQIXuJi1CAnn+iqEAXP96GvvLqxxOJHLsHvp0HT9s2sUDk/rRr0sbp+PIQVTobhTbPpSnLx/C\nhvwipr63QgdJxat9sDSbFxds4ZqR8VyUGON0HDkEFbqbndizA3ee2ZfPVu/gqfk6SCreafm2vdzx\n4UpGdGvPtIl9nY4jhxHkdAB/cN2JXVmzfR+PfZlBr46tmNCvk9ORROotb18ZN7yRRmSrZjydNEQX\nD3kw/cs0AWMMD57fn0Ex4dzy7nJW5WhmRvEOpRXVXP96GkVlVbxwVSLtdBDUo6nQm0jz4EBSrhpK\n29Bgrn89jfx9ZU5HEjmimhrL1P8uZ2VOIU9eOpi+Ua2djiR1UKE3ochWzXnx6uMpLK3k+tfTKKus\ndjqSyGHNmJvBJyt3cOcZfTk1wbdnyPYVKvQmltC5NU9cOpj0nEJueXe5znwRjzRzWTb/+WojlyTG\n8PuTujodR+pJhe6A0xI6Mu3Mvny6agf//HSt03FEfuWHjTu57YN0RnRrzz8m9cMYXQnqLXSWi0Ou\nO7Er2XtKeeG7LcS0C+WqEfFORxIhI6+IG95cStcOLXnuyqGEBGnM501U6A4xxnD3WQlk7ynhvtmr\niWrTgtO0n1IclLevjGtfWUKL4EBeuXYYbVpo+mdvo69fBwUGGJ68bDD9u7RhylvLSMvULMTijMLS\nSq5+eTF7Sip4+Zrj6RLewulI0gAqdIeFhgTx8jXH0zm8Bde9lkZGXtGR35CaCvHxEBDgekxNbYqY\n4sPKKl3nmm8qKOb5K4dqjhYvpkL3AO3DmvH674YREhTA1S8vZvve0kOvmJoKycmQlQXWuh6Tk1Xq\n4tKAL/vqGstN7/zE4i27efTiQZzUUzeq8GYqdA8R0y6U164dRnFZFVe8tIhdxeW/XWnaNCg5aCre\nkhLXcvFvDfiyt9Zy10cr+Xx1HveencA5Azs3YWBxBxW6B0no3JqXrz2e7XtLuerlxRSWVv56ha1b\nD/3Gwy0X/3GUX/bWWqbPWcvbi7cxZWwPrh2lc819gQrdwxwf347nrhhKRl4R1726hNKKA64mjY09\n9JsOt1z8x1F+2T85b+MvU+FOHd/LjcGkKanQPdCY3pE8celglm3d8+spAqZPh9DQX68cGupaLv7t\nKL7sX/xuMzPmZnDBkGjuOStBFw75EBW6hzqzfxT/unAg32/ayY1vLqW8qhqSkiAlBeLiwBjXY0qK\na7n4t3p+2b/6/RYemLOWM/p14uEL+hOg+4H6FBW6B7twaDQPntefr9cXMDl1GRVVNa7yzsyEmhrX\no8pcoF5f9m/8mMV9/1vD+ISOPHnZYII0r7nPMdY2fHIoY0wmUARUA1XW2sQjrZ+YmGjT0tIavD1/\n9cbCTO6etZrxCR156vIhuhxbjtpbi7Zy54crObVvJM8k6ZJ+b2OMWVpXv0LjjNDHWmsH1Wdj0jBX\njojnvrMT+GJNHn/4efeLSD29sTCTOz9cydjeETydpAGBL9O/rJe4ZlRXHpjUj3nr8kl+fanmUpd6\neWnBFu6etZpT+3bkuSuH0iwo0OlI4kbHWugW+MIYs9QYk9wYgeTwrhgex8MX9OfbDQX87tUl7C+v\ncjqSeLBnv97EPz5ewxn9OvFM0hCVuR841kI/0Vo7BDgDmGyMGX3wCsaYZGNMmjEmraCg4Bg3J5cc\nH8ujFw1k0ZbdJL24iL0lFU5HEg9jreXhz9bx8GfrOHtgZ568bLB2s/iJY/pXttbm1D7mAx8Cww6x\nToq1NtFamxgRoXkiGsP5Q6J5JmkIa7bv49KUH8kv0v1JxaW6xjLto1U8+/UmLj8hlscvGUSwzmbx\nGw3+lzbGtDTGtPr5OTAeWNVYweTITj+uEy9fczxbd5dw4bMLydy53+lI4rDyqmr+/M5PvLVoK38Y\n053pk/oRqPPM/cqxfHV3BBYYY1YAi4E51trPGieW1MeJPTuQ+vsTKCqr5IJnfyA9e6/TkcQhP89n\nPic9lzvO6MNtE/roClA/1OBCt9ZuttYOrP05zlqr688dMDi2LR/8YSQtQgK5NOVHvl6f73QkaWI7\nCsu45PmFpGXuYcYlA7nh5O5ORxKHaOeaD+gWEcbMP46ka4eWXPdaGm/+mOV0JGkiq7cXct4z35O9\np5RXrj2e8wZHOx1JHKRC9xGRrZrz7g0jOLlXBHd9tIp/fLyG6pqGXwUsnm/umjwuem4hAO/eMFw3\npxAVui8JaxbEC1clcs3IeF5asIUb3kijqKyy7jeKV7HW8uJ3m7n+jTS6R4Qxa/Iojuus28aJCt3n\nBAYY7jvnOO4/9zjmry/gvGd+YIvOgPEZZZXVTP3vCh6Ys5bTEzrx7g3DiWzd3OlY4iFU6D7qqhHx\nvPG7YewqLufcpxboYKkP2L63lIufX8jMZTnccmovnkkaQmhIkNOxxIOo0H3YyB4dmD3lRDqHt+Da\nV5fwxNwN1Gi/ulf6fuNOznlqAZsL9vPCVYncdGpPzWUuv6FC93Ex7UKZ+ceRTBrUhRlzM7jm1SXs\n3q/pArxFTY3lP/M2cOVLiwgPDeGjySM5LaGj07HEQ6nQ/UBoSBCPXTyQ6ef148dNuzjrye9YvGW3\n07GkDjuLy7n21SU8+mUG5wzszKzJo+gR2crpWOLBVOh+whhD0glxfPCHkQQHBXBpykIen5tBVXWN\n09G8X2oqxMdDQIDrMTX1mP/IbzIKmPD4dyzcvIsHJvVjxiWDaNlM+8vlyFTofqZ/dBvm/PkkJg3q\nwuNzN3D5C4vYtrvE6VjeKzUVkpMhKwusdT0mJze41Msqq3ng4zVc/fJi2rUM5n9TTuSK4XG6jF/q\n5ZhuQXe0dAs6z/LhT9nc/dFqrLXcdVYClx4fo+I4WvHxrhI/WFyc656vRyE9ey9T31vBhvxirhwe\nx7SJfWkerDnMpWlvQSde6rzB0Xx280kMiA7njpkr+d2rS8gtLK3fm92wm8Erbd16dMsPoaKqhse+\nzOC8Z36gqKyKV689nn9M6qcyl6OmEbpQU2N548cs/vnpWoICAvjbhN5ccULc4U+L+3k3Q8kBu2pC\nQ39zl3m/cIwj9KVZu7n9g5VsyC/m/MFduPfs42gTGtzoMcW71XeErkKXX2zdVcK0j1by3YadDI1r\nywOT+tE3qvVvV2zE3Qxer4GPmZeiAAAII0lEQVRfboWllTzy+XreXJRFVOvmPHBeP07po9MR5dBU\n6NIg1lpmLsvhgTlr2FdWxZXD47jltF60aXHAqDEgwHUA8GDGQI0fnjWTmgrTprl2s8TGwvTphy3z\nmhrL+8uyefjTdewuqeDqEfH89fTehOkMFjkCFbock70lFTzyxXpSF22lfcsQpo7vzUVDowkKDNAI\nvYGWZu3hHx+vYfm2vQyJDef+c/vRr4sm1ZK6qdClUazKKeS+2atJy9pDr45h3HFmX8Ys+RJzg/ah\n11fmzv386/N1fLJyBx3CmnHHGX04b3AXXbov9aZCl0ZjreXz1Tt46NN1ZO4q4YSu7Zhqshj24O31\n2s3gr3ILS3l6/kbeXbKNoIAAkkd3I3l0N10gJEdNhS6NrqKqhrcXb+Wp+RspKCrnpJ4duGlcTxLj\n2zkdzaPsKCzjuW828dairVgsFyfGcNO4nprmVhpMhS5uU1pRTeqiLJ79ehO79ldwfHxb/jCmO2N7\nR/r1hUkb84t4/pvNfLQ8B2vhosRoJo/tQXTbUKejiZdToYvblVZU817aNlK+3UzO3lK6R7TkmpHx\nnD8k2m92K9TUWL7dUMDrC7OYvz6fZkEBXJIYw+9P6kZMOxW5NA4VujSZyuoaPk7fzivfZ5KeXUir\nZkGcN6QLFyfG+OxZHAVF5Xz4UzZvLdpK5q4SOoQ14/ITYrl6RBztw5o5HU98jApdmpy1lp+27eW1\nHzL5dNUOKqpqOK5zay4YEs3EAVF09PJ9yGWV1cxfl88Hy3KYvz6f6hrLkNhwrh4Zzxn9oggJ0kwa\n4h5NUujGmAnAE0Ag8KK19qEjra9C9x97SyqYvWI776VtY1XOPoyB4+PbMbF/FOP6RnrNfuXi8ioW\nbCjgk5U7mLs2j5KKaiJaNeP8IV24aGi05ieXJuH2QjfGBAIZwGlANrAEuMxau+Zw71Gh+6dNBcV8\nvCKX/6VvZ2N+MQC9O7ZiTJ8IRnXvQGJ824bdG/MortCsr+oay9rcfSzctItvMgpYtGUXldWWtqHB\nTOgXxVkDojihazvXBVYiTaQpCn0EcJ+19vTa13cAWGv/ebj3qNBlc0ExX63LZ+7aPJZm7aGy2hIc\naBgQHc6gGNfPwOhwotu2OPKFN400Qdie/RWszClkxba9LN+2lyWZu9lXVgVAj8gwxvWJ5JQ+kQyN\na6sSF8c0RaFfCEyw1v6+9vWVwAnW2imHe48KXQ5UUlFFWuYevt+0k6WZe1iZU0h5lWsumNCQQHp2\nbEXPyDBi2oYS064FXcJbENGqGe3DmtG6b09MPaYfKK2oZtf+cnbvryBnTynZe0rZtqeEjfnFZOQV\ns7O4/Jd1e0SGMTS2LSO6t2d4t/Z0auPd+/zFd9S30N1+bpkxJhlIBoiNjXX35sSLhIYEMbpXBKN7\nRQCus2XW7yhiZU4hGXlFZOQV8d2GAvL2lf/mvUEXPUFoZRktK0ppUVmO4f8HJmUPfUVpZTUlFVWU\nVf52srBWzYLoFhnG2N4R9OrYiuM6t6ZfdBtaN9e0teLdjqXQc4CYA15H1y77FWttCpACrhH6MWxP\nfFxwYAD9urT5zamOZZXV5OwtZfveUnYVV7CzuJzd/36ckpJy9oe0oDS4mavOjYHQljTrNpwWwYGE\nhgQSHhpC+5YhtGsZQufwFsS0C/31zJEiPuRYCn0J0NMY0xVXkV8KXN4oqUQO0Dw4kO4RYXSPCPv/\nhVtPOPw+9IsHNX1IEQ/Q4KM81toqYArwObAWeM9au7qxgokcUVKSq7zj4lwj87g4zfYofk8XFomI\neDjdJFpExM+o0EVEfIQKXUTER6jQRUR8hApdRMRHqNBFRHxEk562aIwpAA4xAYfH6wDsdDpEE/O3\nz+xvnxf0mb1JnLU2oq6VmrTQvZUxJq0+54D6En/7zP72eUGf2Rdpl4uIiI9QoYuI+AgVev2kOB3A\nAf72mf3t84I+s8/RPnQRER+hEbqIiI9QoR8lY8xUY4w1xnRwOos7GWP+bYxZZ4xJN8Z8aIwJdzqT\nuxhjJhhj1htjNhpjbnc6j7sZY2KMMfONMWuMMauNMTc5nakpGGMCjTE/GWM+djqLu6jQj4IxJgYY\nD2x1OksT+BLoZ60dAGQAdzicxy2MMYHA08AZQAJwmTEmwdlUblcFTLXWJgDDgcl+8JkBbsJ17waf\npUI/OjOAvwE+f+DBWvtF7U1MAH7EdYtBXzQM2Git3WytrQDeAc51OJNbWWtzrbXLap8X4Sq5Ls6m\nci9jTDQwEXjR6SzupEKvJ2PMuUCOtXaF01kc8DvgU6dDuEkXYNsBr7Px8XI7kDEmHhgMLHI2ids9\njmsw9tu7hvuQY7mnqM8xxswFOh3iV9OAO3HtbvEZR/q81tpZtetMw/Vf9NSmzCbuZ4wJAz4AbrbW\n7nM6j7sYY84C8q21S40xY5zO404q9ANYa0891HJjTH+gK7DCGAOu3Q/LjDHDrLU7mjBiozrc5/2Z\nMeYa4CxgnPXd81tzgJgDXkfXLvNpxphgXGWeaq2d6XQeNxsFnGOMORNoDrQ2xrxprb3C4VyNTueh\nN4AxJhNItNZ64yQ/9WKMmQA8BpxsrS1wOo+7GGOCcB30HYeryJcAl/vyDc+Na1TyGrDbWnuz03ma\nUu0I/a/W2rOczuIO2ocuh/MU0Ar40hiz3BjznNOB3KH2wO8U4HNcBwff8+UyrzUKuBI4pfbfdnnt\n6FW8nEboIiI+QiN0EREfoUIXEfERKnQRER+hQhcR8REqdBERH6FCFxHxESp0EREfoUIXEfER/wcG\njjQmoMJxygAAAABJRU5ErkJggg==\n", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "import numpy as np\n", "import matplotlib.pyplot as plt\n", "\n", "\n", "\n", "xtraining = np.linspace(-5,5,10)\n", "xtest = np.linspace(-5,5,100)\n", "\n", "t = 0.1 + xtraining + xtraining**2\n", "ttest = 0.1 + xtest + xtest**2\n", "\n", "ttraining = t+ np.random.normal(0,1,np.shape(xtraining))\n", "\n", "plt.scatter(xtraining, ttraining, c='r')\n", "plt.plot(xtest, ttest)\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Question 1.1. \n", "\n", "Start by completing the function 'ridgeLoss' that computes the Ridge loss for a given weight vector $\\boldsymbol{\\beta}$ and regularization parameter $\\lambda$. " ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "\n", "# Step 1: Define the ridge loss\n", "\n", "def ridgeLoss(beta, lam, x, t):\n", " \n", " '''The function should return the ridge regularized RSS loss,\n", " sum_{i=1}^N |t^i - (beta_0 + sum_j beta_j^T x^i_j)|^2 + lambda sum_j |beta_j|^2\n", " for a set of pairs {x_i, t_i} weight vector beta and regularization parameter lambda '''\n", " \n", " loss = # complete with your code \n", " \n", " \n", " return loss\n", "\n", "# Step 2: implement the gradient descent iterations\n", "\n", "def gradient_descent(beta0, eta, fun, maxIter):\n", " \n", " '''general gradient descent iterations. The function gradient_descent should \n", " return the minimum of the function fun starting from beta0 and with learning rate eta. \n", " The gradient iterations should stop after maxIter iterations'''\n", " \n", " \n", " \n", " return beta_final\n", "\n", "\n", "# Step 3. Apply your functions to solve the regression problem above \n", "\n", "\n", " \n", " \n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Question 2. Gradient descent with momentum (5pts)\n", "\n", "#### Question 2.1. Gradient oscillations (2pts)\n", "\n", "When using gradient descent, one of the issue that might arise is to have oscillating iterates, the first step being taken in one direction, the second one, in the opposite direction. Consequently, step sizes that are too big are at risk of preventing efficient convergence of the iterates to the minimum. To see this, apply you gradient descent iterations to the function below, starting at $x_1=-4$,\n", "$x_2=-6$ and taking a learning rate $\\eta = 0.4$. Play a little with the learning rate. What do you observe? Comment your results. \n", "\n", "Recall that the gradient iterations are given as \n", "\n", "$$\\mathbf{x}^{k+1} \\leftarrow \\mathbf{x}^{k} - \\eta \\nabla f(\\mathbf{x}^k)$$" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXYAAAD8CAYAAABjAo9vAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi40LCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcv7US4rQAAIABJREFUeJztvXmsLNl93/f9ndp6u32Xt82b9+bN\nDMnhMiQjknqiKNFaySiSzFBI4MSSIVkL4EGEWJYUBYokIjHyRwDFEmwzsOFgINGAIcKLKFoyBC2k\nEktWQHOZGVIckkNxhrO9Wd92t15r++WPc07Vqbp9l3e77+t7+/4+ePXOWtV1u6u+53eqq75NzAxB\nEARhcVDz3gFBEARhtoiwC4IgLBgi7IIgCAuGCLsgCMKCIcIuCIKwYIiwC4IgLBgzEXYi+kUi+ioR\nfYWI/jURNWaxXUEQBOHOmVrYiegSgH8A4CozvwOAB+BHp92uIAiCcDhmdSnGB9AkIh9AC8ArM9qu\nIAiCcIf4026AmV8mot8E8CKAIYBPMfOn6v2I6BEAjwBAu93+1re+9a3TvrQgCMKp4vHHH7/JzOf2\n60fTWgoQ0SqA3wPwtwFsAPhdAJ9g5t/ZbZ2rV6/yY489NtXrCoIgnDaI6HFmvrpfv1lcivkggOeY\n+QYzJwA+CeA7Z7BdQRAE4RDMQthfBPA+ImoREQH4AICnZrBdQRAE4RBMLezM/DkAnwDwBIAnzTYf\nnXa7giAIwuGY+stTAGDmfwjgH85iW4IgCMJ0yJOngiAIC8ZMInbh+KPvfmIAuVlMnp28m/KEOrDT\n313c9gl1eg+qC+9SX1kHtW0CO7eJat8d9bv1mQbapUwH7ENlmQg715u0uH1r9VBlmVRtO6ran5RT\nb9c1deSu4/QjNbG//kpNOI6IsB8QLYwptBhmOq2Us1pbtkdbXmtjnXLurMsT+ufV8sQ6nljHnB/t\nG3SXoIoQ7pZW1tglv1ddnUmDwV6Dh1u3M12YXy2j2gBQGQTcgcFz+nhmAPHKPuQ563hOnV3PM9v1\nnNfwnO3Zsue83oQ28irrLfLAdOyFvRTUDGA3rdXtaLd1VjxTJ2/75BPq60Ksl6MSRqoc1PWDtn6i\n2APVR3kC1Puost6NroptUe316lFdPYJz15kU+dUXu809Is9iG3u01cqLdBIS4Ih7fZayyyyHd+vn\nzo6wy4zKzs5sXzjr7DVDs4GD7T8peLD9M2cbewQZbLeZlOvmkwKYsu7IgpLi3PN3GQBsva/7kb9L\nHzd1201/8qv93DqoIzm25yPsvAUe/Ukp0JU0q+SZ06lfjuwHUnnjzYdVvOGRLiv3wys/VKqP+JVt\nHTBiqAi1Li+SYAkHp/zcD/j5n+bDhM2MtjLT3W9WvDM4KweMegCXOus4bWwDwLEu5zsDROZsqj+N\niMA7BgCrQX61Tq0deLtzEvYYyK4DFKD8g1o6JQ9AUIxuNHFE9GujYG3krIm4iKcgnFz0+etI1XE6\nnXdcUahdBeDE1CUTrh44wSwnKAeWpNwej3S/YlZzMOYj7OosqP135/LSgiAIs0IPOoFejtGAI7c7\nCoIgLBgi7IIgCAuGCLsgCMKCIcIuCIKwYIiwC4IgLBgi7IIgCAuGCLsgCMKCIcIuCIKwYBx7rxhh\nsbGuk2y8Tth4m1SNsrisL1d0SlzpuXvdjqY7h+rFqjUA7XhKxaknt5VMX9NufHOosh23TRAOjgj7\nMYKZwciRcwY25keMHLkxIdN1XC2DwZyBwciN4VLurKtTLtZlZGad3EnLPGzfQlzddfOK8O4s6zr9\nt9htwdS52wMKsV4Up8OjhMpBoEgJ2titqFE7+pWDhXLKyraCiMptkK1XRT0Zs7eyvzehT5lXlXZV\nSdWkuqLsVdvFQ2lqTr2wM2vhzDkzgpohY23uY+t1Pi/a3b45W+HNjKBW28q0KtjVdUoRPmqKk9M9\nMYsTW1XFoBAKVZzY9jQH2XUcgSmEwhUalHVUClFVpGrR6wRHR7e9KNPOKLkeQddD7B1ysZ+ATBh4\neGLJnXG4rdZ1kWttziylNmtxB73KIFipr81iigHcnfHsNUjbQCCpDNJuIAC33g0S7tpx6oq/goLn\npOVgoIq+Xq2P07fWR5Hdhs7rdm9i+0kcZGYi7ES0AuC3ALwD+gj/GWb+z4fZVhm1psg4RY7UCGlq\nlgwZUjBnup0z0yctBFcLcurkdVmLdloT7ekPUn0QuAfczgNQUYBANQoxLQ+celSz84DWB9zOCAhE\nxWvVo6h6fyvegjAtdpCoBCXOzLGsy4ugpt7PXXfHDNUERDoAcgMhN1AyQRUnSPJRWV8JwvKp3RcB\n1AYBvyL+evEntPm7lj04bbYeHjzyZ3aOzipi/yiAP2Hmv0VEIYDWXp1H2Ta+tvmpQqwzK9pGxA8j\ntnbkVvBrb7YHjzwEKire4FJs/YkjdLm+coRai2vRt0hl2iicLuyszoM6VsZXkygvXVZn1NXZeFk3\nqT2r1FcDyIxTJPnY6FfmtKWHusxoZxceBYVeeUb82/5dtO0lomUA3w3gpwCAmWMA8V7r2JHUowCB\naprRKigE1StGNx8KPrzayFYf6ezIKQiC4EJE8Aqb77uHe+XBCn3mXnlAVgtsq1ceMk6c9VJknCDN\n95TVCrP4ax8EcAPAvySibwHwOICfZ+b+bis0vWW8feWHZvDSgiAIxw99WXR+AecsLuj4AN4D4F8w\n87sB9AH8Sr0TET1CRI8R0WM3btyYwcsKgiAIk5iFsL8E4CVm/pwpfwJa6Csw86PMfJWZr547d24G\nLysIgiBMYmphZ+bXAFwjoreYqg8A+Nq02xUEQRAOx6y+Ufg5AB83d8Q8C+CnZ7RdQRAE4Q6ZibAz\n85cAXJ3FtgRBEITpkCdWBEEQFgwRdkEQhAVDhF0QBGHBOPUmYKcRZkZmDJ0yZmNkxqbePjHHeinq\nc2McxeYxbZOfkLKzHgPG24PBjMJSyraVrpAo6lBsCxUzLLdf8beY7dq8W6//1klth2OnIa+11a2W\n621uvaKqBZr2+7FGaOWaZOrtOtr0zPFmNP2VdV+0bWY9RWW+TFXZ5vTxTB/PbEsRGfsMmy/LYp9x\nMhBhP0KswGWcI8tzZJwj5RwZZ7rOLrmuz6HzORhpXpZtv2JbrI2SdMq1tOyXG9G24p1Z2985WuVa\nQbKOjlZIABQCVdrEVjwgAbe8w/kRlfq6L3q1f22fdjE82eHjjuqgwLX30XVr5Al1gB7Y7IbsQJU7\ndsZ2oKoMfkV+vp8dAC3+ZhBQpO3oPCv8ZgDxlAcPZZ1HyvTXfW1eEcEnZSxDyn77LkqZ9crtClVO\nnbDb6DPlDGlu0wwp1/JOXWb7mXq7fsY50kKws0Kg3fb6yX8Y6ifCxBMGhFD5Rb2NsjwTadk6HaGV\n7fZkLPJOlOdB7Yjk6lFgPfpzI0pFpSjbfhLxTU91RuTOlFDUlzOqvDLLqs+2MmbjnsjFLI1NYFDO\n4KpBQz1g0EGDzZdBRZynZaCR68DCtttlFueHPi88eKoUe588nSqvGAT8omzbdD9feWW7Kfuk4CkP\ngVO2/U4Cx1bYmRkJZ0hyvaR5Wi0X+bQQXN2eIs1zJIVIZ0WbFfLDHEyePQjsQaPKgyfyfLQoLMqe\ncxDYA8aNNjwTpVSjDirq6tGLiKHgYi+fHHdnxYOQFyLPlZmoDZCKdidoqi464NoRVDkB1zBPnYCs\nDM6yQ7jIKiIEyq8OAmYACIoBwC/yQZHX7YEzWATKL9ab9Xk+F2HvpyP85fWnEOdpIdSJzTuCfVCI\nyHljyzc7VD7aKqqM1L7zhpf1TnulbyneIq6CMHuUmXEGc3jt3BH6+mxcB4epM6u3s/ZyVu8GkXGe\nYpCNnQBT9zso5YChdSxUvtEwO2j4WA3bB97eXIR9mCV4oX+zGL1C5aPlR+UfVIxufmWUC8wf64r4\nUYx2giAsPooUQlII1dHIIDM7Vxay4iqCzqdOXg8MthznabHeVhIjzTPEeYbzje6BX3suwn42WsKP\nP/hd83hpQRCEu4K+kuAjOKKBYy9OxjcBgiAIwoERYRcEQVgwRNgFQRAWDBF2QRCEBUOEXRAEYcEQ\nYRcEQVgwRNgFQRAWjGNrKSAsFtZ8zPUjybmsZ7h506adsipeKNY4qzDRqqfO66GWrxp43fnfULo4\nunVUydtSxcSMXBOzss71zyGzfbfOeu1YDx+aUBaESYiwn2CsSVOWO2ZkeY4st46SPKHOmjcZB0mz\nvq3LOEdu+zIX+bxoZ+R5jhzQTpQ1wd4p3tbqd97v1uJhB4L6QiB4SkGZAUX7E1lr3tKG11O2rPuW\nPkYEpUrjOE8Z8zmzHe2TRFDGZVEV7catUWmDLY8IvlIyCM2BmQk7EXkAHgPwMjN/aFbbPWmwEcw0\nz/Xjwlk+oZwhybXIJnnZrpesVi4XK+JJniHL9evMCk9ZN0iq5BXtFIbQ83VeGYdHVbpCVvJURp5l\nlIlKO2qRqRuVupEt4Fj+7hMN6757+6XXDbQmWffusO3lnW12prAjb/7bbVbB7PrVT66rz2QqLo5u\nnR1wrYtjrawHZmu4xUjyHLkxyrJ9y7wd7GdnEUwE7bukrEGeFv9AlRa8vqfbAqXzvnVf9JS2DzHr\nB8p4OXk2r9sD008GEc0sI/afB/AUgIMbGsyZnBlJliE2S5KbNMsQ5zkSW5dqsY2NMGuBNosRZ5tP\n8+yOo1N94HvFgV4c8GaJfL+IhGybV4+OTBRly8pES1aUi5R21snJIEzCnRG64p9OSEsLa9Pfui2a\nAMQGMWV9GbCMsxT9pB7E5EiyQ7oveqXY2/Mq9PTgEHhe0RYqD6Hn6Tqv7BeaPqFTf9LOj5kIOxFd\nBvA3AfwfAP6nWWxzL3JmxFmKOMswTrUYj7MU40Kk00KsdXuKJM9rbVqMD0p5sOgP2h4MrTA0RmWq\naLNRhs57lcjCjUbsgeeJsArHECKCbwKEeVCd/Zaz2STPkZqZb2wHgyLIKmfFsTM7HqWpCd7KgC3L\nDxaBEaEi9pHnIfT8YhAoFr+sj4p638l7d+08n1XE/k8B/DKApd06ENEjAB4BgCtXrmCcphhnKUZp\ninGa6TQzS5rVUi3aNj2IICuiHW980w+wHDUQGVEuRufaaG0/RLdehFcQ7i5EVARQzSPYvr2saYO8\n+ozdBoJJlpf1TvC4HY8rs/39ZupWkyK/FP/I18IfeX6Rb/g2X627kwF2amEnog8BuM7MjxPR9+7W\nj5kfBfAoAFx521v5Xzz2+T22icofFfk+VoPAvBn+jjfGinHkjKL+CZw+CYJw9/DMpcrGDMJbZnZE\nXwekOrVXDtLyyoITsG6ORiao3T9gvdS9u7a97wfwYSL6YQANAF0i+h1m/vHdVmgFIb77/gcKYW4U\no1MpziLKgiCcFIhIB6L+4SU1Zy6uZLhXMWza8g/+cyQ0i98cLDamI/b/eb+7Yq5evcqPPfbYzF5X\nEAThNEBEjzPz1f36yZOngiAIC8ZMH1Bi5j8H8Oez3KYgCIJwZ0jELgiCsGCIsAuCICwYIuyCIAgL\nhgi7IAjCgiHujsKu2Ee685yRZcYZMjeeIbnTlhvHR2akmXF8NCZStm9RlxtDKscZsjC1MnWcl1a9\nulza+HJemmSBrbFWaaAF2wYUbfaRwLql753c6VsYiVlDMqfSWu5aUzIUNrylHS85hmhwXBndvGuY\nRtZMTZVtntqZWpfGomx8hDyl3RaLPp7xCfKMC6Pt54n74iIiwn7CKPwzUuOPkTpeGaYuzfLa4tQZ\nn43Mpjafc6VsRXzWWLGyYlQ4P6qquJFyXB4dx0gKFAilU2Th7Oh4mcMRYSuwgBXjcl/qYuaW6n95\n8byHk7g+72xGkbqbo62zA5gdgHIG0jwvPehNXTmQGWfGvHRsLAbIGXsgE8xTmB7B97xiYPC80mHR\ns6ln3BdNXeBpPyTfrOsXZYXAN15Jpi7w9TrC0SPCfsRYIU4S7RKZpDq1+aSWT7K8rLOC7NQnabZD\ndPbDnqjuCWlP0iDw0FRBpU47RFKRLyI8E935JtXtZdSobKRITt7WkyoiV2E6XKF3Z0vaO1/PrtzZ\nUjnLKmdcmZmFpbkdzB1XRju4Z1yUR0laDPxuwHCnx6IiQuBrwzzfN3a7vvFu8j34vi6Hpi7wvbJs\n0tD3EAQ6lYFiMiLs+8DMGCcZ4sSYkcUp4jTDOEkRG7HWbTqNK6luP0iERUBx4LoHfKcR6pPAU5V6\n36aqLPueKvsWiwelREwXCeuL7yng4A+Zzx47o9gxKzTlxOSTVLclWVYEKbY+yfQ50h+NsZHmRTk9\noGWvrxTCoBT+KPBNWaeRTQNfDwqBj8iUo8CH7y2mp9SpEfY8Z4yTFKNEi/MoToryKE4xNvXjpLrE\nyd5RCQHlgWQOnHYjwqo52EJ7QLkRR+BVohQrzIt4gAmLCxGZSzAKs5aSPNe/lVCf1dZnvTp4SpGk\nGcaJbuuP4qJtP2MtRaRFPjReVaEW/IatC3w0wsCkZX3oH28/qxMr7EmaYRQnGMYphuPE5BOM4tQs\nSSUdJ+muAq2IEAae/tACH80owEqnWYzqts2O9qFv0uD4f8CCcBJRihApff5NQ5bn5QBgg7U0wyhO\nEZsZ+DjNiqBuME6wvj3Ubcnug4Ii0kIfBiY1eTMQNCNd33Tyd/Oy0bERdnvJYxgnGI5jDEYJBmMj\n1uMyPzTpblM1TxGaxZsd4Oxyuxh1bd1JG30FQTgcnlJohgrN8M4vWu06y7cBY5FPsb49xCjexihO\ndg0go8AzQh+iGZWi34oCNMIArShEKwrQbAQIPG+qv3suwj4YxfhPTz6L4ShBfxxjMNbiPek3PBUR\nmlGAZuijEQVYbjdMOShSOzI2Qh+BiLQgCDNAKaM90cEHBWYuBN9eSRjFCYbjtBKYrm8P8cp4C6Mk\nnbid0Pe0yBuxbzVCnOm2DrwfcxH2/jjBs6/e0iNUQ1/2aEV29DKjVqhHrkbgi1ALgnAiINJXDJph\ngNXO/r/7lOV5IfZDc2ViMIrL/DjBra0+Xry+gQurnQPvx1yE/dxyGz/1A982j5cWBEE4NnhKodOM\n0GlG+/bNJlzR2A25CVQQBOEEcCdfvoqwC4IgLBgi7IIgCAuGCLsgCMKCMfWXp0R0H4B/BeACtB/S\no8z80Wm3Kyw+zIw8czxNshx5ZtwgrQdKzrrOmmOZhbmawjHQKoy4jJGWNuPiws2Rmct7jfeze3Du\nyCocG63JmCLHhIx2uDiS8ckhx8hMp4AyfjvK046MRATP5JUieL4q8nYbgnBQZnFXTArgl5j5CSJa\nAvA4EX2amb82g20LcyAzxmNpkiFJMu0kacppmus00/ks1X2yjJGlps6sb4U6yxhpmpX2v2bJD+gH\nctoha6rmKXi+MWOzhm3WcdHUe75XlH1fl3XeM4uCHxg/oUCbafm+V+RlAFkMphZ2Zn4VwKsmv01E\nTwG4BECE/S6T54wkSRGPU8SxXTIkJp8kNp8hSdJCuBNTTkz5TgXXCooVEFeAwiioCJCtt9GpFikn\nUlW67BnvHB3ZViNcK3Ru6kbFkyLowuIXKNqBSkBe1HEtincjfWvDa9/vilUvl37xhfXuhBkGGydF\n25bltl9ezGCyrJyt2Lw7KGZZjiwt86NhYgbUHFmWIUu10dYdf5a+hzA0RnShhyDwERjRD0O/rAt1\nOQx1exjpfBgF8H3xPZo3M72PnYgeAPBuAJ+b0PYIgEcA4MqVK7N82YUjzxlxnGI8SvQyNvm4LFvx\nHo8TnTfl/bAnbnHChh46Sw34gTYnK6I4E8mVEZ22+PU8XecVUeDincQ7fNqL4sn7O/Ocy9lWVs6w\nUmcmpmdlui6OjQOjSeM4Rb8/rgz++w0WpAhh6COKAoShhzAKEEW+k/poNAJEDV2OIp2XGcPsmJmw\nE1EHwO8B+AVm3qq3M/OjAB4FgKtXr87+FxyOMcyMJM4wHMYYDmOMhglGI5smGA1jnRohj8fpjqjR\nQor0CRP5iCIfrVaE5ZW2PmFCGzX5RXRVRFUmsvI8+b78NKGMyIbh7GI4K/xJYmaFYz0LLGeJaRFs\njMf6mN7eGmI8TpHEux/bylOIogCNRoBGM9D5pi2HaDQCNFtl6vvT+aksMjP5tIkogBb1jzPzJ2ex\nzZMAM2M0SjDojzEcxBgMtHAPB2Yx+dEwRjYhyiEiHb2Yg3Z1tY2oERTRTKNhBdxENhLVCMcAe72+\nifCO17Wz0XhsAxkj/mYAsMHOeJygtz3CaJQg2WUmGoQ+ms0QjaYW+lYrQrMZoNmK0GqFuq4dncpz\nZhZ3xRCA3wbwFDP/4+l36XjAzBgNE/T7I/T7Mfq9EQb9MfpWxPtjDAbxxGlp1AjQbOoDq3txWeft\nAWjSRiNE1AjkRzCEU4VSpCPwRoDu8sHWydIco1GM4dDMbodJMfu1wdP6rT5evnYb6QSrXT/w0GpH\naLcjtFoRWm0t+O1OA+12hHYnmumM5jgwi7/m/QB+AsCTRPQlU/drzPxHM9j2kcHMGA5i9Hoj9LbN\n0huj3xuhb9J6lO15Cq12hFY7wrkLy2i3Qx0dtHWE0GqFaDRDudwhCDPE85UW4U5j375JkmE40EHX\ncBBXArF+f4xXX1nHcBiDa7/nG4a+eY0InaUGOp0G2ksNdDoRlpaaCKOTJfyzuCvm/8Mx/VYpzxm9\n3gjbW0OzmPz2CL2t4Q7hbrZCtNsRVs+0cfnKWmVEb3caiCJxmhSE40wQeAiWW+gu725xm+eM4UAL\nfb/npCaoe/21zR2Xf8IowNJSA51uA0vdJrpLTSyZfLMVHjtdOFnD0C6MRgk21/vY3Bxia3OArc0h\ntjaH2N4eVkZmP/CwtNREt9vEvZdW0e02i1G5s9SQL2ME4RSgFJUzgAs725n19wB2Jr9t060hbt/s\n4cXnb+7Qle5yE91uC8srTXSXW1heaaG73JybppwoYR+NEqzf7mFzY4CN9QE21vvY3BhgPEqKPp6n\n0F1uYXWtjSsPnkV3qYnuchNL3SYazeDYjayCIBwviMjcsBDgzNmlHe31KwE2kLx5YxsvPHejctdP\nZ6mB5ZUWVlbbRbqy2jpywT+Wwp7njM2NAdZv97B+u4/bt3rYWO9jOIiLPmHoY3m1hSsPnMXycgvd\nlRaWl5voLDVEvAVBODKUInS7euZfJ0tzbG0NsLkxxObmAJvrA2xuDPDqKxvFjRZEhKVuE6trbayu\ntbF2poPVMx20ZnhJZ+7CbkX81o1t3Lq5jVu3tJhnqf52W3kKK6st3HtpDStrLayutrGy2j6W17UE\nQTjdeL7C6loHq2vVXzvKc8b21hAb631srPeLgPWF524UfaKGniGsne3gzNklnD23dGixn4uwx3GK\nJ77wLG5c12Jub1EKQh9rZzp481svYu1MB2tn2ugut+QuE0EQTjRKEZZX9LX3+x88V9THcYqN233c\nvt3D7Zs93LrVw1e/fK24ht9shTh7rotz55dw/sIB7w/FnIR9e2uIr33lZayttfHGh+7B2XN6dOou\nNyUKF2ZO4fJo/FhKt8fS42USrp8M6f+0N43rTyPHqzAFYejj/D3LOH9PKdpZmuP27R5u3tjWy/Ut\nXHvhJs5d6B54u3MR9uWVFn7sJ94Pz5dI/LTCzEjGCRLjdZOME6SxTpM4RWoXY1yWJRnSJNXGVzZN\nM7MYF8k0K21/CwvgfMc9y7OEFBVOi6RK10XluC0q33jrBH6ZWj+ewIcf6iVw0iDyEUQBgihA2Ajg\n+afv6cnTiucrnDvfxbnzpZBb65GDMhdh982BLpx8tA9OilF/hFF/jPFgjPEgxmgwRjws0/EwRjxK\nkIwSxKMYyR5+OHW8wEMQ+tqS1oihZyxpgyjQ3uVWRI2lrTKCS8Y1UnujKx19mxSO86OFiIr9qro6\nmujeeMSz49yYZ7mud+yI3cEmSzMk4xSj3ki7LhpnzSzJiu+S9oMUIWyECBta6MNmiMgsYTNE1IrQ\naEWIWjrfbEdotBvw5BbehcA+rXtQ5v7lqXA8sRF1f3OA/tYQw+0hBttDDLdHGPZGGG4PMeqPMeyN\ndhUn5alSeJoh2ssthBeCQqBsNKojUxupBpUIdtEj1Tw3/vZmhpLE1dlLPHJmNSM9OI6HMeJhjP7G\nAKPBGMko2XWQDKIAzU4DjU4DzU4DraUGmktNtJaaaHXNstSEH4gULBLyaZ5i4lGMrds99Nb76K33\n0NsYoLfR12K+OUA6wXwpakVoLWmh6J5dQqPdQKMdmaWBRitEo91A2AwRhPKk7n4opRBG2rf+sDAz\n4lFczJhGg7iYQdnBd9gbYf21Dbz89HDi59poR2gvt/Sy0kZnpY2l1TY6q20srXYk8j9hiLAvOHme\no7fex8aNLWzd3MLmzW1s3drG1q0exoNxpW/YDNFZaWP57BLufeMFtLottLpNtLtNtLotNDsytT+O\nEBGiZoSoGR2ofzxO9Axsa4j+1kCnZjDfuLGFl595DZljpkVEaHWb6J5ZQvfsEpbPLmH5bBfL57po\nduS5keOICPsCEY8T3H51HbdfXcf665tYf30Tmze2KpdKmktNdM90cOVtl7C01tHLahud1c5UUaNw\ncgijAGEUYPns5LssmBmj/gjb63301vvYvt3D1u0etm9t49m/egHJuHzSO2yGWDm/jLV7VvRycQXL\n57rwPAkA5okI+wmFmbFxYwvXX7yJmy/dwo2XbmHr5nbR3uw0sHJhGW9575uwcr6LlXNddM92RbyF\nfSEiNDtNNDtNnL/vbKWNmTHsjbB5YwsbN7awcV0HEM988bniEo/ne1i9ZwXnLq/h3H1ncf7KWbSW\ndj6lKRwdIuwniN5GHy8/8xpe/eZreP2Fm8WllEY7wtnLZ/DgO6/gzL1rOHNxBc2OnEjC7CEi/cXr\nUhMX31A6aDEztm/3cOuV27j16gZuvnQL33j8WTz12acBAEtrHdzz4Hnc+8YLuPiGCwgbd/4jHcLB\nEWE/5qy/voHnv3oN177+CjaubwIA2sstXH7zRVx44BzOXzmLpdWOXOcU5goR6WvwZ5bw4DvvBwBk\nWYb11zbw+gs38frz1/H8V67h6cefBSnChfvP4crbLuH+hy9LEHIE0EHvJZ4lV69e5ccee+yuv+5J\nIR4n+OaXnsczTzyL9dc3ixMVijw7AAAgAElEQVTh8psv4tJDF9E9syRCLpw4sizDzZdu4+WnX8WL\nX38ZWze3QYpw6U334KFvfQMuv/leOa73gYgeZ+ar+/YTYT8+xOMEX/vMX+Opzz6NZJzgzL2reOO7\nHsD9b78Pzfb+vx4jCCeJ9eubeO7LL+Cbf/UChttDdM8u4Vu+52E88I4rIvC7IMJ+wnjpG6/gP/+H\nxzDsjXD/w5fx9ve/BWcvnZn3bgnCkZNlGV586mV85S+fwvrrmzh/5Sze/9+8F0urnf1XPmXcVWEn\noh8E8FEAHoDfYuZf36u/CHuVr3/+aXz+j76I1QvL+I4PXxVBF04lzIxvful5PPanXwKI8AM/+T1Y\nu2d13rt1rDiosE9t2EJEHoB/DuCHADwM4MeI6OFpt3tauPnKbXzhj7+Ey2+5Fz/89z4ooi6cWogI\nb3r3g/jhRz6IIPTx5//2Mwf20hGqzMKJ670AnmHmZ5k5BvBvAPzIDLZ7KvjmF5+DF3j4G//tt8tT\nnYIAoLu2hPf+8LvRW+/jteevz3t3TiSzEPZLAK455ZdMXQUieoSIHiOix27cuFFvPrVkWW6cCcXt\nUhAs9j73LM3nvCcnk7umJsz8KDNfZear586d23+FU8L9D19GPIzx+Ke+fGAbW0FYZOJRjC/8yZcQ\nNkPc8+D5ee/OiWQWDyi9DOA+p3zZ1AkH4NKbLuJt73sIT332afQ3B3jfh94jD2wIp5br127iM7//\nBfQ2+vjeH32/WGAcklkI+xcAPERED0IL+o8C+Dsz2O6p4ep/9S60l1t44s+exL//v/4Yb3vfQ3jr\ntz8k964Lp4bbr63jyb/8Ol746jW0l1v4L//u9+DC/TKzPyxTCzszp0T09wH8KfTtjh9j5q9OvWen\nCCLCw9/xFlx+87344v/zJJ78T0/ha5/5Bq48fBlvevcDuHD/OSgl1+CFxSIeJ7j29Zfx9BPP4foL\nN+CHPt753W/DO/7GWxGEEqlPgzygdAzZuLGJv/78M3j2yy8iGSdoLjVx5a334vJb7sWF+8/Jr90I\nJ5Zhf4RXnnkN177+Ml5++jVkaYaltQ4e+tY34KH3PHhgT/nTijx5ugCkSYqXvvEqnv/Ki8WPH3iB\nh/NXzuLiGy7gwv3nsHZxRbyvhWNLPIpx/dotvP78dbz67HXcfnUdgP5dgCtvu4QH33Efzt13ViwE\nDshBhV1Cv2OMH/h44O334YG334c0SfHa8zfwyjOv4dVnX8cTn/4yAP1Dz2fuXcO5y2s4e2kNZ+5d\nQ3u5JSeKcNfJsgybN7Zw65V13Hz5Nm6+dAsb17fAzFCewtnLZ/Cu738H7n3TPThzcVWO0SNEhP2E\n4Ac+Lj90EZcfuggAGPaGeP2Fm7hx7SZuXLuFpz77NPJM3/MbNkOs3bOC1QvLWDmvl+Vz8iMbwmxw\nf2xj/fomNl7fxO3XNrBxfbM8BhsBzl4+gysPX8b5K2dx7vIZuYR4F5F3+oTS7DSLaB4AsjTD+usb\nuPXqhv5pvNc28I3Hn638dmVzqal/SemM/km87pkl+bFiYVfsj51vm8X+Vu7WzS3Eo/Ln8RrtCKsX\nVvDWb38IZy6u4My9a1hak98ImCci7AuC53s4e+lMxWuGmbG93sPGdf1D1voHrbfx3JMvVk5MQIv+\n0mq7+JX64hfru020uk2EjVBO1AUiz3OM+mMMtvSPWPe3huhv9NHfHKC3MUBvvbfjGLE/aP3gO69g\n+Zz+MeuV88tyW+4xRIR9gSEidNeW0F1bguvywMwYD2Ns3drWP1a83kNvvY/eRh83rt3C81+9Bs6r\nX6p7vofmUgOtbgvNTqNYGu2oSKNWhEY7gh/4MgjMAWZGPIox6o/1Mhhj1Bth2BtpEd8eYtQbYbA9\nxLA32vkZBx46K210Vto4d3kNndUOOqttdNd0KrcgnhxE2E8hRIRGK0KjFe34sWJAR3PD3gj9zQEG\nW0MMtgYYbI8w2Bpg2Bth/bUNvNIbVX6t3sXzPUStEFEzRNSKEDVDBI0AUTNE2AgRNgKEjQBBI0QY\n+QiiwCw+/NA/tXf5MDOyNEMSp0jGCZKxTuNRUqTxKNbpMMZ4GCMexhgNxkW5LtaA/ryjVqgH4E4D\nF8910erq3y1tdZtodfXsLGrKrGxREGEXdqCUQrvbQrvb2rNfmqQY9ccY9kYYD5wosT+uCM7GjS3E\nQy1IB7FhVZ6CH/oIQi30fuDBC0zqe0Xq+QrKL/Oep6DcRemUFEEpAkinRARSWsCIqBQzV9OMPjKz\nWQAwI89NOWdwnutyzsiyHHltydLMLGU+TTJkSVYIeJbYNEUSpxOFuY4f+nqQbOrBc/X8MqJWhLAZ\notHWA3ajbRc9m5IH3E4XcxF2MbtaDPzAR2fFR2elfeB10iStRKA6MtXRaTxOkMYp0liLnM2nSabX\nG8ZaGF2RTDPkWX4gQbzbaNdOM+jYASgoB6b2cgt+4MEPzAAW+gjNrMWdxQRRYGY5IYLo9M5oTjPM\njCQ+uDf9XIT99q0+fv93v4Cz55dw7lwXZ84tYXWtDc+TqGLR8QNf3/a2NFujszx3ImWTcs66Ltd5\nNhG3jbwBADYahy1y5XIEkf5PR/Yoo36lTErFzMAuduYglzWEwxKPU9y6uY2bN7Zx4/oWbt7Yxura\nwQOouQh7qx2iu9zEKy+t49mnXwego5vV1TbOnFvC2pkO1s60sbraEZ9y4UAopS+9QL7fE04Yo1GC\n9Vs93L7dw60bPdy+1cPW5qBo7660cOnyGu65d+XA25yLsDebIb7/B94BZka/N8bNG9u4dVMvz3/z\nOr7x1CsAAFKE5eUWVtfaWF1rY2Wtg9XVFlrtSKIhQRBOFFmWY2tziI31PtbX+9i43cf67T76vVHR\np91p4MzZDt740AWcOdvBmXNLiA7xYOFcvzwlInSWGugsNfDAG7RFJzOjtz3C7Vt65Fq/3cf117fw\n3DfLn8gKQh8rqy0sr7SxstJCd6WFlZUW2h0RfEEQ5kuW5tjaGmJzY4DNzQE21vvYXB9ga2tYPJlr\ng9bzF7pYffherK21sXZ2CY3GbKacx+6uGCLCUreJpW4T9z9Y+jHH4xTrt3vYWNdv1MbGAC+9eAvP\n/PWrRR/P99Bdbuql20R3uYXust5WFMm91YIgzAZ7tWF7a4itzSG2tobY2hxga3OI3vaouEGEiNDu\nNLCy2sLlK2tYWW1jZbWN5eXWkV5mPnbCvhth5OPCxRVcuFi9zjQaJdhc72NzU4+QW5sD3L7Zw4vP\n36zcKRGGfjFgdLoNLJmZQqfTQLvT0LfDCYIgGNI0w/bWCP3eCNvbI2xvadHe3h6htzVElpW/x2qD\nyrWzHTz4xvNYXtFB5fJKC/4c7DpOjLDvRqMRoDFB8LMsR297hK3NIba39LK1NcStm9t44fkbFdEn\nRWi3I7Q7Wug7SxHa7QbanQjtToRWO5rLhyMIwtHAzIjjFP3eWC/9Efq9MXq9EfrbI/R6Y4yGcWUd\nP/CwtNTE8nITl+9bM4FiA93lFlqt4/Vw14kX9t3wPIXllRaWV3Y+ZJPnjH5vhF5vhN62s/RGePWV\ndQwH8Y577aNGoEW+FaHd1mLfbIVom7TVihCE3rH6cAXhNMLMGA0TDAZjDAcx+v0xBv0yb8tpUr0v\nXHkK7XaEzlIDl6900OlEeoZvZveNRnBizu+FFfa9UKq8jj+JLMsxMAeAHtFHGAxi9Ht6VL/++hbi\nCY/Te76HVitE0y7Ncmm0QjSbARrNEI1GIPfsC8IdkiQZRsMYw2GM0TAxaYzBIMZw4OQnWCsQERrN\nEO12iNXVNi5dXisCtHYnKgK0kyLc+zGVsBPRbwD4rwHEAL4J4KeZeWMWOzZPPE/tKfyAvv42GMRF\nJDAYjDHo6wNsOIyxfquPV4brSOJ04vphFKDRDPSlpIYW/CjyC+GPIh+RaQujAL4vD7wIi4O9FDIe\npxiPEoxHCUajBONxgtGwLI+GMUajBMPhZDsKIkLUCHQA1QqxvNJGsx2aACtCqxXq2XUzPFXfo00b\nsX8awK+aH7T+PwH8KoD/ZfrdOv74vqfvvNlD/AE9AFixL6KMkT54RyNdt7k5xOuvbSIep7vaLXie\n0oNBI0AY+YgiH2EUIAw9RFGA0DyOHka+zjuLPOQlHAXMjMR43cSxTsfjFHFslnGCOM4wHieIxynG\n46QQ8ngPXxzlKR3cmMBmabmFRiMoZ7xNPfttmvxpEuyDMpWwM/OnnOJnAfyt6XZn8fB9b9/o35Ln\nJoqxkYrxTxmPyhNibE6Qrc0hxuNtxOOk8u38JJSnEIY+gsBDEHoIAi34Qegh8Ms6P/B0H+NnEhjD\nLT/w4HtKp74nJ9IJJstyZGmOxHjtJEmGtJZP4gyJdZlMdFts8kmcIUlSxGNd3s/3KQhtEOIjigK0\n2hGiyMxIIy3e7uw0agQIAvmualpmeY39ZwD8290aiegRAI8AwJUrV2b4souDUlRcmpn0pe9uZGmu\noyIbKZnoKXaipzKy0vne9kifoOZEvRMTLc+YW/m+FXvtj+L7nmlT8L3ScbFIrY+KojLvKXimrBQZ\nV0btv+J52qNFeQqKCMqWVTU97rDjCplnjNy4Q+Z5jix38plOc+Nx45azVHvgZMb7JstypE6dFew0\nzco2U06Nu2SSZnf2OfvlQG8H/3YnQhi1TXDgIajMDr1yxmhmkRIEzId9hZ2I/gzAPROaPsLMf2D6\nfARACuDju22HmR8F8CgAXL169fhZ8Z1gPF+h5esvgg5LluaIE+OkmGZFpJakuXFXzJBmJk21cNi6\nUkAyjEZJITJaYLTQHJX7orXgLYQeKMpa83VaL9t1yw1N2HjNHKwMTnW+rLPC7dj85gwGCvOxo0B5\nCr47cPoePI/gG0FuNkM96NpB2NeDr29mYkGgB2Ir3HY93SaifJLZV9iZ+YN7tRPRTwH4EIAPsPjx\nnlg8X6Hph8BsTRcLcuNZnjnuizr6NNFqaiLTwpHRiV6t53meF6KZO26NZYqqqDo+6swAoyyjTArY\nUXJCzeHRyRDp9tL5EVBU+r0DMLMJ7JhhKGX84Z0ZiOfMUpSn+3nKOkXa2Ysz4/H0OidhtiLMh2nv\nivlBAL8M4HuYebBff+H0ooVLR4SCIBwt094u8c8ALAH4NBF9iYj+7xnskyAIgjAF094V86ZZ7Ygg\nCIIwG+QGZ0EQhAVDhF0QBGHBmM9vnm4P8Puf+QraUYhWFKAZBWg1nHwUohkGcruVIAingiTLMBon\nGJhlOI4xGCfoj2IMTd1K5+C3rM1F2H3zwMmtrT6ujRPEkzwgAEShb0TeRzMK0DT5RqgHgGaR+gh8\neVpNEITjQZ4zxkmKUZxgGCcYjhMM49SkSZmOdLqbBjbCAC0T+HZbB39OZS7C3m018OHveHtRTrIM\nw5EdreLijx6Myz/8xkYfw3hj4hsAAJ4iLfhG+Bv1NPARhb4uB7rOl3uBBUHYB2bGOMkKodZpimGc\nYBTrOp2WQj6OU0x6qMcGrE0j2OdW2kWAWr9q0Qh9eOpwV8uPhW1v4HkI2h667ca+fZMs02+gM/LV\n3+ThOMH2YIxRkmCcTB4IAD0YREbko0ALfhh4iEIfUVBfPISmT+Br7xRBEE4GzIw0yzFOUsRJhnGa\nYhynGCdpIdpxkmKUmDrTNjL53Z68VGQ1ROvI6lITF8MuGoFfXFVohG7+7lxiPhbCficEnoeg6WGp\nebBpSXVKVI64dtQdx+WHuTUYFR9muo+xlu8pRIGP0Pf0YsQ/8D1ERvxte2D7OPkg8OArmTEIwn4w\nM5I0Q2z8buJafpykZX1Sll0Rj5MM+R4PxhOggzobyIU+llpRUbazf1fEbcB3HM/hEyfsd4pSZK7P\nB1i9g/XSTHun2BE9TvVAEDsHTJykxUEzihNsD0YYJ/qAS/O9BwZAj/aBrxD4PgJPFcIfeMZ4yVNF\n2fcVAk+ba+k6mzep8Q3xPXFfFOYDs7aESLNc+wplORKbpk5dmiHJtA+RTrX/UJKVgq375IgT3fcg\nBJ5XCa6aUYCVdhNB4CHy9Uw8tAFXMUP3iwBskc6bhRf2w6JFMkSrER5qfXsA6+jCRhDlQWujjtSN\nQDJ9gA/GSXHwp2l+oEHCxVNUiLyvrOAbwyib2npVrdP1VOQ9675YlAkeOQ6NVDox2nphfjBr90jr\nu5Pl2g0ydbx3UuMOaduLNMuLttRpT7OyLjXlNMuMiGemrJe9ouJJBCY4KVJfC/Jyu+EEONXZbhjU\nZ8GLJ8zTIsJ+RFghbUbB1NvKcy4im8ScVG4EZAeR8gSrnmxpliPJdV08TsxJm9fS2fi3EaANrJQx\nvbLCb1wYPSrrCzMsm5Ixy6Jqu3VstHkUfY1rI0r3RgLB/CumyEW93UGU5f1m0a5OFSZhXJZteyFo\njtlYrl3JwKbdGpDlZoHpkxtHSG3nu7POCnU1zSt1Wc7Iecafozvwq2pgYG8+8J2Zos0Hbt58HxXU\nZpe2/jhexlgERNhPAEoRIqWnjEcFs43kyugty/OiLuccaVZGgGU0qNezLoxZrqO2zEaIVoxyRsZ5\nIVw6z8hZ/5ZlKWQo/cqtBS5QuDhWRROVPscN5Qw2xcBjHR/J1hEUoTKoUW2g84gQBF51EDSzKKJy\nILWzJ91GUKRnX8rOtsy6njNjs2Xfzsq8sq+I7slFhF0AoMUm8DycZPNFa9Nrxd+NsK2jNBd9a+vW\nhgaaYNBO1aBfC58pKDs7cPzfBWFeiLALC4P7YxqCcJqRm7EFQRAWDBF2QRCEBUOEXRAEYcEQYRcE\nQVgwRNgFQRAWjJncFUNEvwTgNwGcY+ab+/UfpSme21hH5Hlo+D4iz0fk+/AP6WQmCIKwKDAzkjzH\nOE0xyrSNyShNEHgHvxd5amEnovsA/ACAFw+6zuZ4hD/4+lM76gNPIfJ8hJ6HqBB8r5aads8zadk/\nEFMtQRDmTM6MOEsRZxnGxv9mnKUmr9OxEexxlmJctOv8KE0nWjNc6nYPvA+ziNj/CYBfBvAHB13h\nTLOFv/32d2KUaROtsf1jU/3HjUx5kMRYHxl3tmxvdzZAP0ASeh5Czy+EP/TKgSAo6vRSlJUtK4Se\nHiDEeVEQTg/MjDjLkOQ54izVBmRZhiTX4pxkGWJnSYw4635GtLOy7374SpXBqrly0Y0alUC24QeV\nqxqt4OD2JFMJOxH9CICXmfmv9hNBInoEwCMAcOXKFVxcWrqj13KnJ3HmjIBZKfzlUrYN0wSb46Hz\ngRzMUIsICFR1ENCC7yH0FAJl6mxeGR8MpfRiDLgCZdJifVU8Ki4IwsGxthdpniPJc6S5dlFNrBdS\nbtwic8cbKTf+SiZN8qwQ8MQI9zS6EJngsRNGiPwykHTbdH31isNRX3beV9iJ6M8A3DOh6SMAfg36\nMsy+MPOjAB4FgKtXr96xtQcRFW/YNOTMZrQtR9648gFnxcFgy7pNHxSDJMbWuBzNk0M42ikiI/Z6\noPDM4/y+UvCpdF0s8mS8PcziKQWfqKjzlO2jt+uZvEdlu+d4jwjCNDAzMjaeQtZjyOSzPEfKjs9Q\nzkXZtqWZ7cNI8qzoO2lxBTzN8x1WEPvhnmeBUkWQ1vB9PWNX5cw9cAK2yPMKAbcz+dAEZyfhHNpX\n2Jn5g5PqieidAB4EYKP1ywCeIKL3MvNrM93LGaKI9PV7f3ZuClmeF+K/VxRRHqxZaYHK1n1RrzvO\nUvST6sGd8eEO6knYGYNNXdGfVOeRPpA9azJFpo9jUFWYVSmCQunoqIAdjo3WU8UtW38Vm1dkHRq1\nY4s109LrlusXro7mb6u4OO5oc+qd9+MgJyk7bzzX6uplXWe9alAYlJVGZVU/m9y2gwuvm5wZOWru\nj+CqURp2OkBawc13WTIuTdl0P2PYxqVJm13fmrml1tSNjfXvjBwk7XEWmMDDpr7J2+/MfFWKsnWY\ntLNg29dXriiX/QPPK46308ah1Y2ZnwRw3paJ6HkAVw9yV8yiYb3KG0fovONGSa7YZ9ZfuyjnSJ1o\nKjNthbc2G0dGk9oTvDyBdb+kIhK5sYV1xKEQgOPoqyhY7ICoqBysrahqV0ldb50hA6V0nZnxuQN6\nPSjwTQDgOamdMfqq9PF3Z5yeXU/ugDtSxATshEBE8M1JcfDfKr875E6UpyNLOHm7lD8CUUafqJTt\nJS3bVvQDCh9zdl7T1rtRs41+TVMlvxc8ocNe0Xzp9LjT870yk6DaDKPWVtZr+97Cyrc2iykFumyv\ne9h7E8on4bKBMHtmJuzM/MCstiWcLKzAyHMIgnA8kDNREARhwRBhFwRBWDBE2AVBEBYMEXZBEIQF\nQ4RdEARhwRBhFwRBWDBE2AVBEBaMuTygtBH38YcvPY5A+cZAS6eh8uCTk1c+AvJMn7KfT/rpOEEQ\nhJNCxtZmJEOcp0hY5xOTT3K7pDrlMh/nKVbDzoFfay7CroiQg9FLR8UfFecpsvxgDmuAfow/IL8Q\nfZ887RFB1lXR1yZapq3so0wfU3b6aOMtr/BHEQTh9MDMSNkYjnFWySd5tZyasq7PnXYj1o5Q2/qM\nD+ogSfDJBrceQhPghuou/tDGYegGLXz48tUd9bl5g/RolVZHMPsm5jlSt60Y9fQb2MuS2pu+v497\nHTLmV3Wx981swXMGA93PcVikso9nfTPcfqZewV1HLzILEQRjPQFjSmZ9kDhHxpkxKsuLttQpp7Y9\nr5ZTI75uPmXjKsnV8p1itSCoBZBNL8RSUNbZYNLmA3NFIiza3KsW3tSB5bHyilGkEHkKkXdwQ/n9\nYOtMx3llRK2U6yPuPgfBOEvK+uIAu/MBpI4dULyK2JeDjDVz8k29IgUP1nGxVm+dGOE6Mpp2Zx3X\nc8SWrWsjQRV+I7Yf1VIZjI437HrzOGlmnSFRujzafFmvzx1mRobccY/MC+G151du+hSmcUWal8Zx\nMKILRpZneht5jgylUGemz7RYwXUDKlsOlY+WCotZvu3jFzP5Mogr6mrl435J+FgJ+1FgpzU+PACz\nGzAmkdvIwoky6lFENepgJ68HjdJB0TgxuhGKOVlGzkwkd7aTc16cXJNMrY6K0phKVU2rzCChhwgq\nzK9snbbk1SdGYXylC4UxVtVcq1Z2bXldw14q++sURX+XO4mJ3Hdzoo2vzbmmZKgalBV1rjmZa+OL\nUogr+Zq1b2HpC2ucxlUbX5TrTRts3AllUFEGEh5Upd6KaOT7lZmqV7hMlnXubNbOfu2MWJnz2m23\nwiuXUk+BsN9NFCmEpI7FvUa5M0jYCM0OAoxykLBRGDsRWBHFOa6LvCPvuDc6IuI6MpYujjkYKPpV\nxcz1J7eClleEDZjk3FgtoyKWtmqSs+NOodtL+ibLg+v5bmscZ0cUlTscH21fd4ADykFKD4CqaFfO\nOq6XPcF1gXRmULUBtDrTUs5My3WIdOtrszhnxqfM4O25ZdNfxPR4IcK+oOiTEWamIgjCaeIYxJaC\nIAjCLBFhFwRBWDBE2AVBEBYMEXZBEIQFY2phJ6KfI6KvE9FXiegfzWKnBEEQhMMz1V0xRPR9AH4E\nwLcw85iIzs9mtwRBEITDMm3E/rMAfp2ZxwDAzNen3yVBEARhGqYV9jcD+C4i+hwR/QURfdssdkoQ\nBEE4PPteiiGiPwNwz4Smj5j11wC8D8C3Afh3RPQGnvA8OxE9AuARALjyxot4dvszUORDkQ/PpAoe\nFAXwyCvadJ3t4xV1dEw9GgRBECaRc2aWFDlS5Jwh49SUTT2npi5Dzgkyp77hLR34tfYVdmb+4G5t\nRPSzAD5phPzzRJQDOAvgxoTtPArgUQB4+F1v4o34ZWTQO8wHtLN0UeSByIMHMwCQpxc4eWdg0H31\nOtU2r0jJySvyQE5eBhNBWAzY2GrknIFhxBaZsdjIHJHVeTYCbNepCrG7vl0nLfs55cPqnA1yc84O\nvN60lgK/D+D7APxHInozgBDAzf1WavkreM+Z/64o2zcn46T2pphRDanzJppRzbyR9k1339iER8jz\nzLyZen02rzEN2sNDOULvGZ8NOxCoySl5UFBOqoqBouxrt2XbyzzV1q30sWWIV4dwfODCSyjTFmWc\nW6sy4zPk1HEO40xkhNXWZUUfey6X/fJi26VA54VQlyLs5FFuA9OYoxEVAaOqBIM6WAyoCaXqgaZf\nKRdXKXZclSjrPPIPHUxOK+wfA/AxIvoKgBjAT066DLMfNir2EU65O3ujDa7cEThDdcTNnBHbORB2\ntOeVfuWBlyPjpDgoy4M6Kw7SqQ+qvTAmTYCqDBKFv+KueZ2iMKCq1hMIsMZUu5btNuCsq3voXSu8\nG62vo+Pk6FpnUbG9sq/r0uj4ODoDmdsPztaqb49bd6eDYPUzm3SYu76O1TKKz7xmZVbtV5ieVbwf\nzWsV/o6ma+70ymt1ritk7pTzor9tK+vdcrWNrYWbOX/g9rHCW+TNax7RMV4NbLxq6syyPQQg5VX6\nVGflZUC22+zcI9+pL2f4JyGImkrYmTkG8OMz2pcjh4jgwQfIh49obvvhRjF2kCgjD64NCPokqfSr\nRTv6BDTrIge41qc4QSfnc84BJBNPaHuSOmawRmiMA+NRDlTC1OiIr3SDBMrBuj6I79amRTDQgYMR\nVhsEKCigmGFSRXjtTFKZfShFcdKMdNIslgrRdWeowv6Iu+McUOQB8O48aDym2IiyFP4yMixiVBMV\nouiZO1a7bgRbesm70afzYpXIuO6MXulr+mNCb6fDPn/dhMi/XrfD5710id/5f302YnOlfW/V/Le0\n5a30g3J861XRrxBxI7LC6USEXZiaUlBsxRx3RhAE8YoRBEFYNETYBUEQFgwRdkEQhAVDhF0QBGHB\nEGEXBEFYMETYBUEQFgwRdkEQhAVDhF0QBGHBmM8DSvkGePiHAPlmFzyAApOaOvJMm5uf1G7rPOAE\neDgIgrDY6CenM71wavIpwDZ169IJ/VKnf1K2q7UD78OcnjxlgLeA3P0DdP4QHmIFRAQuxN4Kv3KE\n3w4IXpnW8265qFdmXfx57J0AAAdwSURBVFXro2p5+3oe9OOXMtgIwlFifYu0KOZGS3JoXXHqkZk2\nK7imT7FONqHPXnlXkHO44sycTvU3aSsIv6ZbAcCdA29jPsKuVkGtv7OjmplBlZGuNpqxGb0qdenO\nusro6H7QGcAjXc7d9coP7TCeyfsycRAwS6XsGR8Rr9bu1pGzjqknm3e3q5w+bh3V6qnW1+1PO+sA\np82ug9r6JIPZHHBdIIHcyZuF63W5WWDa8mob5xP6WtM3t/+k+tzZ5n51mdlO5vRx6na0l2J9FOcr\n7Rb0Va4SNHSqbHt5FYHcvpV13KsQbl31asUsPH6OlVeMFgP7h8/JfdEd5SujcTa5vhj93UHCOTCL\nvnmtr3tQOwe9cVosDuTcPah550HvmGYdK3YMChZnACj6wOnr5us2u65db9Voa7JBzV42vYcZeOrv\nM+/R5tZxmWeu1aPWh6v9AfOZ2z45dm63ap52nCByg4J60GGClh3BjoIWO1NWbnBjAxkzG64ER27b\nzr67z9LtrF73XYSg5FgJ+3GAyIlM5zW43CmVKIidwaIWWVX6AdUIiqtpIUC1/sV2nHLRD077JJFy\nXoMni1O1DtV0xzqVN2FC/qDCux/7DRpuebfBxBmUaNJg5pbrA5s7oKld2qlwfNy5DTszq5V3zNp2\nm51Nmv3VBbs+85PLkPNEhH0BqAxGwOGCUUEQFga53VEQBGHBEGEXBEFYMETYBUEQFoyphJ2I3kVE\nnyWiLxHRY0T03lntmCAIgnA4po3Y/xGA/52Z3wXgfzNlQRAEYY5MK+wMoGvyywBemXJ7giAIwpTQ\nlI/wvw3An6K8wfU7mfmFXfo+AuARU3wHgK8c+oXvHmcB3Jz3ThwA2c/ZcRL2EZD9nDUnZT/fwsxL\n+3XaV9iJ6M8A3DOh6SMAPgDgL5j594jovwfwCDN/cN8XJXqMma/u12/eyH7OlpOwnydhHwHZz1mz\naPu57wNKewk1Ef0rAD9vir8L4LcOvIeCIAjCkTDtNfZXAHyPyX8/gKen3J4gCIIwJdNaCvw9AB8l\nIh/ACOU19P14dMrXvVvIfs6Wk7CfJ2EfAdnPWbNQ+znVl6eCIAjC8UOePBUEQVgwRNgFQRAWjLkJ\n+0myIyCinyOirxPRV4no2D5dS0S/RERMRGfnvS+TIKLfMO/jl4no3xPRyrz3yYWIfpCI/pqIniGi\nX5n3/kyCiO4jov9IRF8zx+PP77/WfCAij4i+SER/OO992Q0iWiGiT5jj8iki+o5579MkiOgXzef9\nFSL610TU2Kv/PCP2E2FHQETfB+BHAHwLM78dwG/OeZcmQkT3AfgBAC/Oe1/24NMA3sHM/wWAbwD4\n1TnvTwHp30P75wB+CMDDAH6MiB6e715NJAXwS8z8MID3Afgfj+l+AvpW6KfmvRP78FEAf8LMbwXw\nLTiG+0tElwD8AwBXmfkd0L9i8qN7rTNPYT8pdgQ/C+DXmXkMAMx8fc77sxv/BMAv4+A/C3TXYeZP\ncflLv58FcHme+1PjvQCeYeZnmTkG8G+gB/RjBTO/ysxPmPw2tBBdmu9e7YSILgP4mzjGz7YQ0TKA\n7wbw2wDAzDEzb8x3r3bFB9A0dyC2sI9ezlPYfwHAbxDRNego+NhEbzXeDOC7iOhzRPQXRPRt896h\nOkT0IwBeZua/mve+3AE/A+CP570TDpcAXHPKL+EYCqYLET0A4N0APjffPZnIP4UONI7g1+FnxoMA\nbgD4l+aS0W8RUXveO1WHmV+G1sgXAbwKYJOZP7XXOkf603gHsCP4RceO4LcB7GtHcBTss58+gDXo\nae+3Afh3RPQGvsv3ie6zj78GfRlm7uy1n8z8B6bPR6AvKXz8bu7bIkFEHQC/B+AXmHlr3vvjQkQf\nAnCdmR8nou+d9/7sgQ/gPQB+jpk/R0QfBfArAP7X+e5WFSJahZ49PghgA8DvEtGPM/Pv7LbOkQr7\nSbEj2Gc/fxbAJ42Qf56IcmjDoBt3a/+A3feRiN4J/YH/lfnh4MsAniCi9zLza3dxFwHs/V4CABH9\nFIAPAfjA3R4c9+FlAPc55cum7thBRAG0qH+cmT857/2ZwPsBfJiIfhhAA0CXiH6HmX98zvtV5yUA\nLzGznfF8AlrYjxsfBPAcM98AACL6JIDvBLCrsM/zUsxJsSP4fQDfBwBE9GYAIY6RCxwzP8nM55n5\nAWZ+APpgfc88RH0/iOgHoafnH2bmwbz3p8YXADxERA8SUQj95dR/mPM+7YD06P3bAJ5i5n887/2Z\nBDP/KjNfNsfjjwL4f4+hqMOcI9eI6C2m6gMAvjbHXdqNFwG8j4ha5vP/APb5kvdII/Z9OKwdwd3m\nYwA+RkRfARAD+MljFmmeJP4ZgAjAp83s4rPM/D/Md5c0zJwS0d+HtqH2AHyMmb86592axPsB/ASA\nJ4noS6bu15j5j+a4TyeZnwPwcTOYPwvgp+e8Pzswl4k+AeAJ6EuYX8Q+1gJiKSAIgrBgyJOngiAI\nC4YIuyAIwoIhwi4IgrBgiLALgiAsGCLsgiAIC4YIuyAIwoIhwi4IgrBg/P8Mrq1GB2DBtQAAAABJ\nRU5ErkJggg==\n", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "import matplotlib.pyplot as plt\n", "import numpy as np\n", "\n", "x = np.linspace(-8, 8, 800)\n", "y = np.linspace(-8, 8, 800)\n", "xx, yy = np.meshgrid(x, y)\n", "ff = np.sqrt(0.1*xx**2 + 2*yy**2)\n", "plt.contour(xx,yy,ff,alpha = 0.5)\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Question 2.2. Momentum (3pts)\n", "\n", "\n", "To mitigate those oscillations (among other advantages) and accelerate convergence, one can combine the gradient iterations with an additional momentum term, getting the system\n", "\n", "$$\\left\\{\\begin{array}{l}\n", "\\mathbf{v}^{k+1} \\leftarrow \\gamma\\mathbf{v}^k + \\nabla f(\\mathbf{x}^{k})\\\\\n", "\\mathbf{x}^{k+1} \\leftarrow \\mathbf{x}^k - \\eta\\cdot \\mathbf{v}\\end{array}\\right.$$\n", "\n", "Take $\\gamma=0.5$, $\\eta = 0.4$ and plot the iterations you get with the momentum approach on top of the level lines. " ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def MoMgradientDescent(x0,maxIter, gamma, eta):\n", " \n", " '''Implement the gradient descent with momentum for the parameters gamma and eta. \n", " You can take the initial speed v=0.'''\n", " \n", " \n", " \n", " \n", " return solution " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Question 2.3. \n", "\n", "Try various values of the $\\gamma$ (momentum parameter) including $\\gamma=0$. what do you notice? comment your results below.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Question 3. Logistic regression and Fischer scoring. (10pts)\n", "\n", "#### Question 3.1 Logistic regression\n", "\n", "As we saw during the lectures, one approach at learning a (binary) linear discriminant is to combine the sigmoid activation function with the linear discriminant $\\beta_0 + \\mathbf{\\beta}^T \\mathbf{x}$. We then assume that the probability of having a particular target ($0$ vs $1$) follows a Bernoulli with parameter $\\sigma(\\tilde{\\mathbf{\\beta}}^T\\tilde{\\mathbf{x}})$. i.e. we have \n", "\n", "$$\\left\\{\\begin{array}{l}\n", "P(t = 1|x) = \\sigma(\\mathbf{\\beta}^T\\mathbf{x})\\\\\n", "P(t = 0|x) = 1-\\sigma(\\mathbf{\\beta}^T\\mathbf{x})\\end{array}\\right.$$\n", "\n", "The total density can read from the product of each of the independent densities as \n", "\n", "$$P(\\left\\{t_i\\right\\}_{i=1}^N) = \\prod_{i=1}^N \\sigma(\\mathbf{\\beta}^T\\mathbf{x})^{t^{(i)}}(1-\\sigma(\\mathbf{\\beta}^T\\mathbf{x}))^{1-t^{(i)}}$$\n", "\n", "we can then take the log and compute the derivatives of the resulting expression with respect to each weight $\\beta_j$. Implement this approach below. Recall that the derivative of sigma has a _simple expression_. The first function below might not be needed in the implementation of the function 'solve_logisticRegression'" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# Step 1 define the sigmoid activation and its derivative\n", "\n", "\n", "def sigmoid(x):\n", "\n", " '''the function should return the sigmoid and its derivative at all the \n", " points encoded in the vector x (be careful of the fact that )'''\n", " \n", " \n", " return sig, deriv_sig\n", "\n", "\n", "def solve_logisticRegression(xi, ti, beta0, maxIter, eta):\n", " \n", " '''The function should return the vector of weights in logistic regression\n", " following from gradient descent iterations applied to the log likelihood function'''\n", " \n", " \n", " \n", " return beta\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Question 3.2 Logistic regression and Fisher scoring. \n", "\n", "An interesting aspect of the MLE estimator in logistic regression (as opposed to other objective functions) is that the Hessian is positive definite. We can thus improve the iterations by using a second order method (such as Newton's method) where the simpler gradient iterations $\\mathbf{\\beta}^{k+1}\\leftarrow \\mathbf{\\beta}^k - \\eta\\nabla \\ell(\\mathbf{\\beta}^k)$ are replaced by \n", "\n", "$$\\mathbf{\\beta}^{k+1}\\leftarrow \\mathbf{\\beta}^k - \\eta H^{-1}(\\mathbf{\\beta^k})\\nabla \\ell(\\mathbf{\\beta}^k)$$\n", "\n", "Start by completing the function below which should return the Hessian of the negative log likelihood. Note that we move in the direction $-\\nabla_{\\beta}\\ell$, hence we minimize. You should there consider the negative log likelihood. " ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def HessianMLE(beta):\n", " \n", " '''Function should return the Hessian (see https://en.wikipedia.org/wiki/Hessian_matrix) \n", " of the log likelihood at a particular value of the weights beta'''\n", " \n", " \n", " return HessianMatrix\n", " " ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def Fisher_scoring(beta0, maxIter, eta):\n", " \n", " '''Function should compute the logistic regression classifier by relying on Fisher scoring\n", " iterates should start at beta0 and be applied with a learning eta'''\n", "\n", " while numIter" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "import numpy as np\n", "import matplotlib.pyplot as plt\n", "\n", "import scipy.io\n", "class1 = scipy.io.loadmat('class1HW1_LR.mat')['class1']\n", "class0 = scipy.io.loadmat('class2HW1_LR.mat')['class2']\n", "\n", "targets_class1 = np.ones(np.shape(class1)[0])\n", "targets_class0 = np.zeros(np.shape(class0)[0])\n", "\n", "plt.scatter(class1[:,0], class1[:,1], c = 'r')\n", "plt.scatter(class2[:,0], class2[:,1], c = 'b')\n", "plt.show()\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "\n", "'''Your plots. replace the vectors NlogLikelihood_gradient and NlogLikelihood_Fisher \n", "with the values of the negative log likelihood at each iteration obtained from your functions above'''\n", "\n", "\n", "plt.figure()\n", "plt.subplot(211)\n", "plt.plot()\n", "plt.title()\n", "\n", "fig, axs = plt.subplots(2, 1, constrained_layout=True)\n", "\n", "# gradient descent plot\n", "\n", "axs[0].plot(iterations, NlogLikelihood_gradient)\n", "axs[0].set_title('gradient descent')\n", "\n", "# Fisher scoring plot\n", "\n", "axs[1].plot(iterations, NlogLikelihood_Fisher)\n", "axs[1].set_ylabel('Fisher scoring')\n", "\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Question 4. kernel and real data (5pts)\n", "\n", "We want to learn a classifier to discriminate between the images of the 1 and the 8 digits (see below). Images are size $28\\times 28$ and we thus don't want to use a classifier on the images themselves. Extend your gradient descent algorithm from Question 1 so that the iterations rely on the Kernel instead of the features. Then use the Gaussian kernel to encode similarity between the images $\\text{im}_i$ and $\\text{im}_j$ as $\\exp(-\\frac{\\|\\text{im}_i - \\text{im}_j\\|}{2\\sigma^2})$ for an appropriate sigma. \n", "\n" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": true }, "outputs": [], "source": [ "from sklearn.datasets import fetch_openml\n", "from sklearn.linear_model import LogisticRegression\n", "from sklearn.model_selection import train_test_split\n", "\n", "X, y = fetch_openml('mnist_784', version=1, return_X_y=True)\n" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(array([ 3, 6, 8, ..., 69978, 69984, 69994]),)\n", "(array([ 17, 31, 41, ..., 69959, 69967, 69991]),)\n", "(70000, 784)\n" ] }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAC7CAYAAAB1qmWGAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi40LCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcv7US4rQAAEHJJREFUeJzt3X+QldV9x/HPl3VhFaOIP5BBEPyB\nFh0LzcYfkagpsbWOFZm0xl8ZkphiqrSa2KmUdoZMG1OmKiajSRyMCKZGxwn4a8Y2IYwGrZaI1sgv\nUbQgbBbQSBV1wIX99o+9OBvOWfey97n37v3yfs0we+/3nvs859n97pdn7znPeczdBQBofAPq3QEA\nQDEo6AAQBAUdAIKgoANAEBR0AAiCgg4AQVDQASAICjoABFFRQTezC8xsrZmtM7MZRXUKqDdyG43I\n+nqlqJk1SXpV0vmSNkl6XtLl7r66uO4BtUduo1EdUMF7T5e0zt3fkCQze1DSZEk9Jv1AG+QtGlzB\nLoGe7dAH+sh3WgGbIrfRr5Sb25UU9BGSNnZ7vknSGZ/0hhYN1hk2qYJdAj1b5kuK2hS5jX6l3Nyu\npKCXxcymSZomSS06qNq7A2qG3EZ/U8mgaJukkd2eH1OK/R53n+vure7e2qxBFewOqBlyGw2pkoL+\nvKQTzWyMmQ2UdJmkx4rpFlBX5DYaUp8/cnH3XWY2XdLPJTVJmufuqwrrGVAn5DYaVUWfobv7E5Ke\nKKgvQL9BbqMRcaUoAARBQQeAICjoABAEBR0AgqCgA0AQFHQACIKCDgBBUNABIAgKOgAEQUEHgCAo\n6AAQBAUdAIKgoANAEBR0AAiCgg4AQVDQASAICjoABEFBB4AgKOgAEERF9xQ1s/WStkvaLWmXu7cW\n0SlU1+u3nJWNr7niziTWbE3ZtudcOy2JHfjIryvrWD9CbsfSNOTQJDb+yW3ZtpMOSe8HftvFf5Ft\nu3vV2so6VrCKCnrJ59397QK2A/Q35DYaCh+5AEAQlRZ0l/QLM3vBzNK/wYHGRW6j4VT6kctEd28z\ns6MkLTazV9x9afcGpV+GaZLUooMq3B1QM+Q2Gk5FZ+ju3lb6ulXSw5JOz7SZ6+6t7t7arEGV7A6o\nGXIbjajPZ+hmNljSAHffXnr8J5L+ubCeoRCbv/nZJPbUl/4t27bDB5a/Ye9rj/o/crt+mk4Yk8Q6\nhg8p+/3Nb7+fjbf96ZFJ7PGj0lldknT3uyPT4Oa3yu5DPVXykcswSQ+b2Z7t/NTd/7OQXgH1RW6j\nIfW5oLv7G5L+sMC+AP0CuY1GxbRFAAiCgg4AQRRxpSj6sfdHdiaxoQP2YfATyPCzx2fj66eno+Wn\njvht2du98uglSeziwflL9HNOevjabHzU2LQPTZY/n31q20lJzFpayu5DPXGGDgBBUNABIAgKOgAE\nQUEHgCAo6AAQBLNcgnj/L8/IxhdO+X4matm2d/3fyUnsl5fm7+sweEN6E4B0Pg2i2jgpvxjZqnPu\nqGi72zp3JLEJy/KLXc457aEktnbKD8ve127P/x688mD6ezCs7dmyt1tPnKEDQBAUdAAIgoIOAEFQ\n0AEgCAZFG9COi5J7LWjWv87Lth3bnB/4yVlw9wVJ7OjVjTEYhOpZd/uZSeyZL+bX1JcOTCKnPfuV\nJLbjd2k7SRp3c3qJ/oiN6QC8JN1y7lVJ7JB7f5xt++nM/Uee35lf1H/4vN8ksUYZ8OcMHQCCoKAD\nQBAUdAAIgoIOAEH0WtDNbJ6ZbTWzld1iQ81ssZm9Vvp6WHW7CRSP3EY05cxymS/pTkn3dYvNkLTE\n3Web2YzS85uK7x5y2q9KL4/+/IFprEtTEpm6/gvZlkd/f7+b0TJf5HavOg/ancSOaspf+v/IB0OS\n2HE3bU9iu95YkX3/rkxswPhx2bbvZrb7mUH5WV3tuz9MYlf/+O+zbY/5oHF/D3o9Q3f3pZLe2Ss8\nWdKC0uMFki4puF9A1ZHbiKavn6EPc/f20uPNkoYV1B+g3shtNKyKB0Xd3SXlZ+hLMrNpZrbczJZ3\naGeluwNqhtxGo+lrQd9iZsMlqfR1a08N3X2uu7e6e2uzMpdrAf0LuY2G1ddL/x+TNFXS7NLXRwvr\nET52wDEjsvFVn7s3iXV4OnAlSWs60tibc8Zm2w7WsvI7Fxe5vZfRi9I/Uu6YeFy27XVDXk9is24d\nnMRGfe3Q/M6OGJqEOm5LBz8l6emTH0liKz7KDatKl92XDoAe+93GHfzsSTnTFh+Q9Jykk8xsk5ld\nra5kP9/MXpP0hdJzoKGQ24im1zN0d7+8h5cmFdwXoKbIbUTDlaIAEAQFHQCCoKADQBDc4KKfaDrl\npCTW+tOVmZb75kuL/jaJHb/wvyveLvYfLU+vTmI/XHFOtu11n0tnucw57aEk9o9Tvp59/4x/uD+J\nXTx4W29d/NgV876ZjR/7L/FmtORwhg4AQVDQASAICjoABEFBB4AgGBTtJzZcfHgS+9nh/9ND63SN\n8yte//Nsy7Gz00Gq/CIBQF7nh+la4h3by1+7JrdW/7PfuTPbdoDS9cw7e9juKUu/lsROeCi/9M7+\nkvOcoQNAEBR0AAiCgg4AQVDQASAIBkXr4J2vnpXEHv7GLZmWzdn3f2PjuUmsY2p+kGr3W2/uU9+A\ncrRszOdmNVz0yuRs/Lhb07XPd69dV+3u9GucoQNAEBR0AAiCgg4AQVDQASCIcu4pOs/MtprZym6x\nb5tZm5m9VPp3YXW7CRSP3EY05cxymS/pTkn37RW/3d1vLbxHgeTWOJd6uuy5peztPrdpdBIbub7y\ntdP3Q/NFbvfKDkjLxJCztmTb5i7d3xcXvnJxGpy0KdvWlY/vz3o9Q3f3pZLeqUFfgJoitxFNJZ+h\nTzezl0t/th5WWI+A+iO30ZD6WtB/JOl4SeMltUu6raeGZjbNzJab2fIO7ezj7oCaIbfRsPpU0N19\ni7vvdvdOSXdLOv0T2s5191Z3b21W+UtuAvVAbqOR9enSfzMb7u7tpadTJDEil/HqzIOy8Q6vbHXm\nUbPTmFe0RexBbqfeffzYJLY0c+Nnqee1y8vVmRlUZW51+Xot6Gb2gKTzJB1hZpskzZJ0npmNV1cd\nWS/pmir2EagKchvR9FrQ3f3yTPieKvQFqClyG9Hw1wwABEFBB4AgKOgAEAQ3uChI57kTkth3Wh+p\naJvnr7wsGz94+X4/8QIVajphTBJ7bdrR2bavnPaDJNbTbJZZW9Pfg4Wvjk9iKyfem33/aUPa0rY9\n7AspztABIAgKOgAEQUEHgCAo6AAQBIOiBbl5/twkdmpz+Rfk/137OUns0Mu3ZdtWtnAAIP32wuFJ\nbPWVd/TQOr0cf9xPpmdbnnjL2iR24JUHpw0n5vf0xBunJLFRWtFDv7A3ztABIAgKOgAEQUEHgCAo\n6AAQBAUdAIJglktBJgxM/2/clxtZPHfvHyWxo7Y9W1GfgA+nnJGNP/CtWzPR/F2XPjvjuiR2wqKX\n8zscfUwS+ta1+Zth5HS8Objstkhxhg4AQVDQASAICjoABNFrQTezkWb2pJmtNrNVZnZ9KT7UzBab\n2Wulr4dVv7tAcchtRFPOoOguSTe6+4tm9ilJL5jZYklfkbTE3Web2QxJMyTdVL2u9g8bf3ZqNt5s\nL1W03eFPvZ3EuMS/6sLndtukfHxsc0sS++qb52XbDvnJc0nMB+UHUDdMOTyJnTyoPYkNUFP2/YN+\nx4cGlej1u+fu7e7+YunxdklrJI2QNFnSglKzBZIuqVYngWogtxHNPv13aGajJU2QtEzSMHff81/v\nZknDCu0ZUEPkNiIou6Cb2cGSFkq6wd3f6/6au7uk7NKCZjbNzJab2fIO7ayos0A1kNuIoqyCbmbN\n6kr4+919USm8xcyGl14fLmlr7r3uPtfdW929tbmHCxeAeiG3EUk5s1xM0j2S1rj7nG4vPSZpaunx\nVEmPFt89oHrIbURTziyXsyV9WdIKs4+ncsyUNFvSQ2Z2taQNki6tThfrp/Pc9A7m3xv/79m2ucv8\n3+3ckW37mf+4IYmdvGH1PvYOBYif2z3cY6Uz80Kn58/vLDOj5a2p6VIVkvSbv05vkrHqo84k9gdL\nv559/5jvstxFJXot6O7+jHK3LOnSw6QooP8jtxENkz4BIAgKOgAEQUEHgCBYD/0T7Bg6MIlNbPmg\nh9bppcw//3BUtuXYac8nsXTYCKhc0+Hlz49/dduR2fgpv9qcxB4feWfZ271mVjoJYMx96XICqBxn\n6AAQBAUdAIKgoANAEBR0AAiCgg4AQTDLBQjsgFcPyr9wbhr6r/EPZpsOyFxMu+KjXdm2X3z0+iQ2\n9uGVSYxZXdXBGToABEFBB4AgKOgAEAQFHQCCYFD0ExzyUnrJ899s+uNs27tG/qra3QH22XF3vZ6N\nnzJwehL75VW3ZNv+U9uFSezXvzg12/aEWel65gyA1g5n6AAQBAUdAIKgoANAEOXcJHqkmT1pZqvN\nbJWZXV+Kf9vM2szspdK/9IM2oB8jtxFNOYOiuyTd6O4vmtmnJL1gZotLr93u7rdWr3tAVZHbCKWc\nm0S3S2ovPd5uZmskjah2x/qDXf+7IYltOjPf9iJ9usq9QdH2h9zetXlLNj5mZhr/q5kTe9jKe0nk\nWKWzWVB/+/QZupmNljRB0rJSaLqZvWxm88zssIL7BtQMuY0Iyi7oZnawpIWSbnD39yT9SNLxksar\n6yznth7eN83MlpvZ8g6VfzssoFbIbURRVkE3s2Z1Jfz97r5Iktx9i7vvdvdOSXdLOj33Xnef6+6t\n7t7arEFF9RsoBLmNSMqZ5WKS7pG0xt3ndIsP79ZsiqR0jUygHyO3EU05s1zOlvRlSSvM7KVSbKak\ny81svCSXtF7SNVXpIVA95DZCKWeWyzNSZoV76YniuwPUDrmNaLhSFACCoKADQBAUdAAIgoIOAEFQ\n0AEgCAo6AARBQQeAICjoABAEBR0AgjB3r93OzN6StGeR8SMkvV2zndcOx1U/x7r7kfXYcbfcboTv\nU19FPbZGOK6ycrumBf33dmy23N1b67LzKuK49m+Rv09Rjy3ScfGRCwAEQUEHgCDqWdDn1nHf1cRx\n7d8if5+iHluY46rbZ+gAgGLxkQsABFHzgm5mF5jZWjNbZ2Yzar3/IpXuCL/VzFZ2iw01s8Vm9lrp\na8PdMd7MRprZk2a22sxWmdn1pXjDH1s1Rclt8rrxjm2PmhZ0M2uS9ANJfyZpnLpu9TWuln0o2HxJ\nF+wVmyFpibufKGlJ6Xmj2SXpRncfJ+lMSdeVfk4Rjq0qguX2fJHXDanWZ+inS1rn7m+4+0eSHpQ0\nucZ9KIy7L5X0zl7hyZIWlB4vkHRJTTtVAHdvd/cXS4+3S1ojaYQCHFsVhclt8rrxjm2PWhf0EZI2\ndnu+qRSLZJi7t5ceb5Y0rJ6dqZSZjZY0QdIyBTu2gkXP7VA/+6h5zaBoFXnXFKKGnUZkZgdLWijp\nBnd/r/trjX5s6LtG/9lHzutaF/Q2SSO7PT+mFItki5kNl6TS16117k+fmFmzupL+fndfVAqHOLYq\niZ7bIX720fO61gX9eUknmtkYMxso6TJJj9W4D9X2mKSppcdTJT1ax770iZmZpHskrXH3Od1eavhj\nq6Loud3wP/v9Ia9rfmGRmV0o6XuSmiTNc/eba9qBApnZA5LOU9dqbVskzZL0iKSHJI1S1+p7l7r7\n3gNM/ZqZTZT0tKQVkjpL4Znq+ryxoY+tmqLkNnndeMe2B1eKAkAQDIoCQBAUdAAIgoIOAEFQ0AEg\nCAo6AARBQQeAICjoABAEBR0Agvh/bl3kM3ShcFwAAAAASUVORK5CYII=\n", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "print(np.where(y=='1'))\n", "print(np.where(y=='8'))\n", "\n", "# extracting the images corresponding to 1 and 8\n", "\n", "print(np.shape(X))\n", "images1 = np.squeeze(X[np.where(y=='1'),:])\n", "images8 = np.squeeze(X[np.where(y=='8'),:])\n", "\n", "import matplotlib.pyplot as plt\n", "import numpy as np\n", "\n", "plt.subplot(121)\n", "plt.imshow(np.reshape(images1[0],(28,28)))\n", "\n", "plt.subplot(122)\n", "plt.imshow(np.reshape(images8[0],(28,28)))\n", "plt.show()\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "### Bonus 1. (4pts)\n", "\n", "In Question 1 above, you got to implement gradient descent on the ridge regression loss. As we saw, an alternative to this loss is the LASSO where one minimizes the usual RSS criterion augnmented with a penalty on the absolute of the weights, i.e.\n", "\n", "$$\\min_{\\boldsymbol{\\beta}, \\beta_0} \\sum_{i=1}^N |t^{(i)} - (\\boldsymbol{\\beta}^T\\boldsymbol{x}^{(i)} + \\beta_0)|^2 + \\lambda \\sum_{j=0}^D |\\beta_j|$$\n", "\n", "\n", "\n", "(the difficulty is that the absolute value is not differentiable at $0$. There exists several approaches at handling this difficulty). Extend your answer to question 1 and make your function capable of handling both the Ridge and LASSO formulation by adding an extra parameter. " ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def linearRegression_regularized(x_i, t_i, beta_0,eta, type):\n", " \n", " '''The function should return the solution of the linear regression \n", " problem obtained through gradient descent on either the unregularized (type ='None') formulation, \n", " the Ridge (type = 'ridge') or the Lasso (type ='lasso') regularization'''\n", " \n", " \n", " return \n", " \n" ] } ], "metadata": { "kernelspec": { "display_name": "Python 2", "language": "python", "name": "python2" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.13" } }, "nbformat": 4, "nbformat_minor": 2 }