{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2><center>Introduction to Machine Learning: Assignment 2</center></h2>\n",
    "\n",
    "__Given date:__ Monday September 27\n",
    "\n",
    "__Due date:__ Friday October 15"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Question 1 Least Absolute Shrinkage and Selection Operator \n",
    "\n",
    "__(13pts)__\n",
    "\n",
    "Learning a model through the OLS loss can be done very efficiently through either gradient descent or even through the Normal equations. The same is true for ridge regression. For the Lasso formulation however, the non differentiability of the absolute value at $0$ makes the learning more tricky.\n",
    "\n",
    "\n",
    "\n",
    "One approach, known as _ISTA_ (see Amir Beck and Marc Teboulle, _A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems_) consists in combining traditional gradient descent steps with a projection onto the $\\ell_1$ norm ball. Concretely, for the LASSO objective \n",
    "\n",
    "\\begin{align}\n",
    "\\ell(\\boldsymbol \\beta) = \\|\\boldsymbol X\\boldsymbol \\beta - \\boldsymbol t\\|^2_2 + \\lambda \\|\\boldsymbol \\beta\\|_1\n",
    "\\end{align}\n",
    "\n",
    "where $\\boldsymbol \\beta = (\\beta_1, \\beta_2,\\ldots, \\beta_D)$ (note that we don't include the bias) and the feature vectors $\\left\\{\\boldsymbol  x_i\\right\\}_{i=1}^N$ (corresponding to the rows of the matrix $\\boldsymbol X$) as well as the targets $t_i$ are assumed to be centered, i.e.\n",
    "\\begin{align}\n",
    "\\boldsymbol x_{ij} \\leftarrow \\boldsymbol x_{ij}-  \\frac{1}{N}\\sum_{i=1}^{N} x_{ij}\\\\\n",
    "t_i \\leftarrow t_i - \\frac{1}{N}\\sum_{i=1}^N t_i\n",
    "\\end{align}\n",
    "\n",
    "(Note that this is equivalent to taking $\\beta_0 = \\frac{1}{N}\\sum_{i=1}^N t_i$)\n",
    "The ISTA update takes the form \n",
    "\n",
    "\\begin{align}\n",
    "\\boldsymbol \\beta^{k+1} \\leftarrow \\mathcal{T}_{\\lambda \\eta} (\\boldsymbol \\beta^{k} - 2\\eta \\mathbf{X}^T(\\mathbf{X}\\mathbf{\\beta} - \\mathbf{t}))\n",
    "\\end{align}\n",
    "\n",
    "where $\\mathcal{T}_{\\lambda \\eta}(\\mathbf{x})_i$ is the thresholding operator defined component-wise as\n",
    "\n",
    "\\begin{align}\n",
    "\\mathcal{T}_{\\lambda t}(\\mathbf{\\beta})_i = (|\\beta_i| - \\lambda t)_+ \\text{sign}(\\beta_i)\n",
    "\\end{align}\n",
    "\n",
    "In the equations above, $\\eta$ is an appropriate step size and $(x)_+ = \\max(x, 0)$ \n",
    "\n",
    "##### Question 1.1. (5pts)\n",
    "\n",
    "Complete the function 'ISTA' which must return a final estimate for the regression vector $\\mathbf{\\beta}$ given a feature matrix $\\mathbf{X}$, a target vector $\\mathbf{t}$ (the function should include the centering steps for $\\mathbf{x}_i$ and $t_i$) regularization weight $\\lambda$, and the choice for the learning rate $\\eta$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ISTA(beta_init, X, t, lbda, eta):\n",
    "    \n",
    "    '''The function takes as input an initial guess for beta, a set \n",
    "    of feature vectors stored in X and their corresponding \n",
    "    targets stored in t, a regularization weight lbda, \n",
    "    step size parameter eta and must return the \n",
    "    regression weights following from the minimization of \n",
    "    the LASSO objective'''\n",
    "    \n",
    "    beta_LASSO = np.zeros((np.shape(X)[0], 1))\n",
    "    \n",
    "        # add your code here\n",
    "    \n",
    "    \n",
    "    return beta_LASSO\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Question 1.2.  (3pts)\n",
    "\n",
    "Apply your algorithm to the data (in red) given below for polynomial features up to degree 8-10 and for various values of $\\lambda$. Display the result on top of the true model (in blue)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD4CAYAAAD8Zh1EAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8vihELAAAACXBIWXMAAAsTAAALEwEAmpwYAAAiQUlEQVR4nO3deXxU5b3H8c8vYZEAArJpCSEoO4IVAqioqBVlUamAdaFat3K1pe3VtgKCFatUsK27FKPXuqXSe2URVypu0AqytBrCDmExgLLJYiBAkuf+MYMOMSQHcjIzZ+b7fr18hZlzknmO4Jfjc873OeacQ0REgi8l1gMQERF/KNBFRBKEAl1EJEEo0EVEEoQCXUQkQdSI1Qc3adLEZWZmxurjRUQCafHixdudc03L2xazQM/MzGTRokWx+ngRkUAysw1H26YpFxGRBKFAFxFJEAp0EZEEoUAXEUkQCnQRkQShQBeR5JGTA5mZkJIS+pqTE+sR+arSQDez58xsq5nlVbJfDzMrMbOh/g1PRMQnOTkwfDhs2ADOhb4OH55Qoe7lDP15oF9FO5hZKjARmOXDmERE/DdmDOzbd+R7+/aF3o+iklJHaWn1LFteaaA75+YAOyvZ7RfAVGCrH4MSEfHdxo3H9n41WP3lXq6a/DF/X/R5tfz8Ks+hm1kL4Epgsod9h5vZIjNbtG3btqp+tIiIdxkZx/a+jw4Wl/L4e6sZ+OhH5K8uoN6NP66WOXw/qv+PAiOdcyVmVuGOzrlsIBsgKytLj0oSkegZPz40Zx457ZKWFnq/Gn32+S5GTs1lxRd7uXzVx9w7axJN9u0ObRw+PPR12DBfPsuPQM8CpoTDvAkwwMyKnXMzfPjZIiL+OByaY8aEplkyMkJh7lOYlrX/YAkPv7uS//nnOprVP4Fn5kym77w3jtzp8By+T2MwL88UNbNM4A3n3OmV7Pd8eL9XK/uZWVlZTotziUgi+njtdkZPW8KGHfu4rlcGo/p34MS02qG7a8oyg9JSzz/bzBY757LK21bpGbqZvQJcADQxswLgXqAmgHOu0nlzEZFksXv/ISa8vZxXFnxOZuM0XvnpWZx9WuPQxoyM0K2SZfk4h19poDvnrvX6w5xzN1ZpNCIi8Swn56hTNv9Y+gX3vJbHtr0H+K8+p3LHxe04oWbqt98bhTn8mK2HLiISKIeLSYcDOVxM2nbIGFezA28u2UKHk+vzzA1ZdE1v+N3vj8IcvgJdRMSLMsUkB0w99Szu/6wG+9O+5LeXtmf4+adSM7WCu8GHDau2i7CgQBcR8SaigFRwYlPuvnQEc07tTveCZUx8+HbaNKsXw8GFKNBFRLzIyKB0w0Ze7DaQh/r8BHOO+96dzPU78khp9ttYjw5QoIuIeLLmngcZ+dFmFn+vA+fnL+YPs54kvbgQsrNjPbRvKNBFRCpwsLiUpz9ayxP5DUlrWY+H//UCV855FcvIgPGPVOuc+LFSoIuIHEVuwS7uejVU27+s6ymMu6IzTepdHuthHZUCXUSkjP0HS3hk9iqenZtP0/q1eeaGLPp2ah7rYVVKgS4iEiGytn9tz5aMHtCRE0+oGetheaJAFxGhktp+QCjQRSTpVVrbDwgFuogkrW17DzDu9aW8mVtJbT8gFOgiknScc0z79yZ+/8Yy9h8s4dd923HbBadVXNsPAAW6iCSVgq/2cff0POas2kb3Vo2YOKQLbZrVj/WwfKFAF5GkUFrqeHHeeh6atRKAcZd34oazM0lJqfjRmUGiQBeRhLdm615GTl3C4g1f0addU8ZfeTrpjdJiPSzfKdBFJGEdKill8odreeL9NaTVTuXPV53B4G4tqOyB9kGlQBeRhBRZ2x/Y9RTGXd6ZpvVrx3pY1UqBLiIJpWxt/+nru3Np55NjPayoCPY9OiKSXHJyIDMTUlJCX3Nyjtg8b+0O+j82h+w5+VzdoyX/uKNP0oQ56AxdRILiKM/0BNgz5Ec8+NYKXlmwkVaN0/jbrb04p02TGA42NioNdDN7DrgM2OqcO72c7cOAkeGXXwO3O+c+83WUIiJlnukJwL59vPvUFMZuaM62vQcYfn6otl+nVvBq+37wcob+PPAk8OJRtq8D+jjnvjKz/kA20Muf4YmIhEU80xNge1oDxl38X7zR8Xw6pNUKfG3fD5UGunNujpllVrD944iX84F0H8YlInKkjAzYsAEHTO98Ib//wU/ZV7MOv8mdyX+N/0vga/t+8PvfwC3A20fbaGbDzWyRmS3atm2bzx8tIglt/HgKmmdw41XjuPOyX3Pqzk28NeUuRgw7X2Ee5ttFUTO7kFCgn3u0fZxz2YSmZMjKynJ+fbaIJLbSUsdLrXvz0M1P4Q4cZNzsp7l+xxJSJz4QV8/0jDVfAt3MugLPAv2dczv8+JkiIgBrtn7NqKm5LNrwFee1bcofruxCyz8PjvWw4lKVA93MMoBpwPXOuVVVH5KISKi2//RHa3n8vVBt/+EfncGVZyZubd8PlU48mdkrwDygvZkVmNktZnabmd0W3uV3QGNgkpl9amaLqnG8IhJklRSDDltSsJvLn/gnf/rHKvp2as67d/RhcLd0hXklvNzlcm0l228FbvVtRCJydDk5ofuxN24M3fUxfnxw5pArKAYdPob9B0t4dPYqnpmbT5N6yVXb94M5F5trk1lZWW7RIp3Mi3hWNhAB0tIgOzsYoZ6ZGQrxslq1gvXrmbd2B6On5bJ+xz6u6dGS0QM60qBOzagPM96Z2WLnXFa52xToIgFRSSDGvZQUKCdv9tSuy4N/m8crCzaScVIaEwZ3ScravlcVBbrWchEJijJNyUrfjzfhYlCkd9v0ZGz/X7Jt4UZ+el5r7uzbPmlr+35QoIsERTmB+M37QTB+/DdTRkfU9k8oIfuW3pzRsmGsRxh4CnSRoIgIxG+kpYXeD4Jhw3AOZjwzg/u+P5jCWmnc0Ww/t/9yMLVqqOnpBwW6SFAcvvAZ0LtcNu3az5hDbfnw7BvpltGQiUO60rZ5/VgPK6Eo0EWCZNiwwAT4YaWljpc/2cDEt1fggHsv78QNZ2eSmqJ7yv2mQBeRanNkbb9JqLZ/Ulqsh5WwFOgi4rtDJaVkz8nnsdmrqVMrlT9fdQaDu6m2X90U6CLiqyUFu7lrai7Lt+xhYJdTGHdFZ5rWrx3rYSUFBbqI+KLoUAmPzF7Fs3PX0bhuLSb/uDv9TldtP5oU6CJSZfPzdzB62hLWbS9UbT+GdPOnSDLxuNqhV3uKDnH39CVckz2fklLH327txYQhXRXmMaIzdJFk4WG1w2Mxe9mXjJ2Rx9a9RQw//1TuuLidavsxpsW5RJKFT4t7bf/6AONmLuWN3C10OLk+E4d0VW0/irQ4l4hUeXEv5xwzPt3E719fxtcHirmzbztu63OaavtxRIEukiyqsLjXpl37GTN9CR+u3KbafhxToIski+NY3Ku01JHzyQYmqLYfCAp0kWRxjIt7rd0Wqu0vXK/aflAo0EWSiYfFvb6p7b+3mjo1U/nTVWcwRLX9QFCgi8g3ytb2772iE83qnxDrYYlHlQa6mT0HXAZsdc6dXs52Ax4DBgD7gBudc//2e6AiUn3K1vafvr47l3ZWbT9ovJyhPw88Cbx4lO39gbbhf3oBfwl/FZEAiKztX53VkrsHdKRBmpqeQVRpoDvn5phZZgW7DAJedKGG0nwza2hmpzjntvg1SBHx396iQ0x4ewU5n2wk46Q0cm7tRe82TWI9LKkCP+bQWwCfR7wuCL+nQBeJU5G1/VvPbc2vL2mv2n4C8CPQy7v0Xe56AmY2HBgOkBGUJ5WLJJDtXx/gvteX8fpnm2nfvD6Tr+/O91XbTxh+dHYLgJYRr9OBzeXt6JzLds5lOeeymjZt6sNHi0SZz6sVRotzjhn/2UTfhz/inbwt3HFxO17/xbkK8wTjxxn6TGCEmU0hdDF0t+bPJSH5vFphtGwO1/Y/WLmNM8O1/Xaq7SekSldbNLNXgAuAJsCXwL1ATQDn3OTwbYtPAv0I3bZ4k3Ou0mUUtdqiBI5PqxVGS2mpI2fBRia+vYKSUsdvL23PT85RbT/oqrTaonPu2kq2O+Dnxzk2keCo4mqF0bR229eMnrqEBet3cm6bJjw4WLX9ZKCmqIhXVVitMFoia/sn1Ejhj0O7MrR7umr7SUKBLuLVcaxWGE15m3Zz16u5LNuyh/6nn8x9gzqrtp9kFOgiXh3jaoXRUnSohEdnr+aZufmcVLcWk3/cjX6nnxLTMUlsKNBFjoWH1Qqj6ZP8HYxSbV/CFOgiAaTavpRHgS4SMO8t/5Ix07+t7d95STvSauk/ZVGgiwTGjnBtf6Zq+3IUCnSROOecY+Znmxk3cylfHyjmvy9uy88uaEOtGn6s3CGJRH8iROLY5l37ufn5hfxqyqdkNqnLm788j/++uF3swjyga9kkC52hi8ShsrX9313WKfa1/YCuZZNMKl3LpbpoLReR8sVtbT9ga9kkqorWctGUi0g0VTBlcaiklEkfrqH/Y3NZ8cUeHhralZdu6RkfYQ6BWssmWWnKRSRaKpiyyLvgsviv7QdgLZtkp0AXiZYxY45cBwYoOljMY3//hOyljeK/th/na9mIAl0kespMTSxI78yofr8gv3E6V3dLj//afpyuZSPf0kVRkWgJX1TcW6sOE/vcyMvdBtJy1xdM+M//0vuTWbEenQRElR5wISI+GT+e9//wF8b0uZUv653ErQumc+fiaaRNeiLWI5MEoUAXiYIdXx/g96mdeO3y0bTftYlJOXdxZs0imPSEpizENwp0kWpUtrZ/x8XtuP2C/tSaPDzWQ5MEpEAXqSabd+1n7Iw83l+xle+3bMhDQ7vSrnn9WA9LEpgCXcRnZWv7Ywd25KberWNb25ekoEAX8VH+tq8ZFY+1fUkKngLdzPoBjwGpwLPOuQlltjcAXgYywj/zT865v/o8VpG4daiklGfm5vPo7NWcUCOFh4Z25aru6ZjprFyip9JAN7NU4CmgL1AALDSzmc65ZRG7/RxY5py73MyaAivNLMc5d7BaRi0SR/I27Wbk1FyWbg7X9q/oTLMT46y2L0nByxl6T2CNcy4fwMymAIOAyEB3QH0LnY7UA3YCxT6PVSSuFB0q4bH3VpM9Jz/+a/uSFLwEegvg84jXBUCvMvs8CcwENgP1gaudc6Vlf5CZDQeGA2RoQR8JsAXrdjJqai752wu5Oqtl/Nf2JSl4CfTyJgHLrhdwKfApcBFwGvCumc11zu054pucywayIVT9P+bRisTY3qJDPPTOSl6av4GWJ9Xh5Vt6cW7bJrEelgjgLdALgJYRr9MJnYlHugmY4EILw6wxs3VAB2CBL6MUiQPvr/iSMdPz+GJPETf3bs1vLm1HWi3dKCbxw8ufxoVAWzNrDWwCrgGuK7PPRuAHwFwzaw60B/L9HKhIrOwsPMjvX1/KjE830655PZ4adg7dMhrFelgi31FpoDvnis1sBDCL0G2LzznnlprZbeHtk4H7gefNbAmhKZqRzrnt1ThukWp3uLZ/3+vL2Ft0iP++uC0/u6BN7B7QLFIJT/+/6Jx7C3irzHuTI369GbjE36GJxM6W3fsZOz2P91Zs5YyWDXloSFfan6zavsQ3nWpIcqngmZ4Qqu2/PH8DfR+ew8drdzB2YEem3X6OwlwCQVd0JHlU8ExPhg0L1fanLWHBup30btOYB6/sSkZj1fYlOBTokjzKeaYn+/ZRPPYenmlxFo/MXqXavgSaAl2SR5lnegIsbdaakX1+Rd47K+jX+WR+P0i1fQkuBbokj4yM0DQLUJRak8d7X8vTvYbQ6EAhfxnWjf5dVNuXYNNFUUke48dDWhoL0jsz4KYnmHT2jxi8Yg6zuzmFuSQEnaFL0tg75Ec8tKkOL+2sTfquL3npgyc475fXw7CyPTmRYFKgS1L4YMVWxkxfwpY9tbm5d2t+fcml1K19c6yHJeIrBboktMjafttm9Zh6u2r7krgU6JKQnHO8nruFcTOXsrfoEL/6QVt+duFp1K6RGuuhiVQbBbokHNX2JVkp0CVhlJY6Xlm4kQffWkFJqWPswI7c1Ls1qSkqCElyUKBLQlBtX0SBLgFXXFLKM3PX8ejsVdRWbV+SnIpFEl2VrHZ4LJZu3s0PJ/2Lie+s4IL2TZl9Zx9+lNVSYS5JS2foEj2VrHboVdGhEh5/bzVPz8mnUVot1fZFwiz0GNDoy8rKcosWLYrJZ0uMZGZ+s5bKEVq1gvXrPf2IBet2MmpqLvnbC7mqezpjBnakYVotX4cpEs/MbLFzLqu8bZpykWNTlSmTclY7rPD9CHuLDnHPjDx+9PQ8Dq7fwEt/v4c//nYQDaf/n/fPF0lwmnIR76o6ZRKx2uF33q/AN7X93fu56dO3+M37f6XuoaLQxuOYshFJVDpDF++O8oAIxozx9v3h1Q6PkJYWer8cOwsPcsffP+Wm5xdSt3YNXn33z9w76y/fhvmxfr5IgtMZunhXhSkT4Nuz6DFjQt+TkREK8zJn10et7f/mo6p9vkiC8xToZtYPeAxIBZ51zk0oZ58LgEeBmsB251wf30Yp8eE4p0yOMGxYhdMjR9T20xswcWgvOpx8on+fL5LAKp1yMbNU4CmgP9AJuNbMOpXZpyEwCbjCOdcZuMr/oUrMHeOUybEoLXW8PH8DfR+ew7/WbmfswI5M+1nvb8O8mj9fJBF4OUPvCaxxzuUDmNkUYBCwLGKf64BpzrmNAM65rX4PVOKAxymTY7VueyEjp+ayYN1OzjmtMRMGH6W2X02fL5IoKr0P3cyGAv2cc7eGX18P9HLOjYjY51FCUy2dgfrAY865F8v5WcOB4QAZGRndN5T3v8+SNIpLSnn2n+t45N1V1KqRwtiBHdX0FKlERfehezlDL++/rrJ/C9QAugM/AOoA88xsvnNu1RHf5Fw2kA2hYpGHz5YEtWzzHu6a+hl5m/ZwSafm3P/D02l+4gmxHpZIoHkJ9AKgZcTrdGBzOftsd84VAoVmNgc4A1iFSISiQyU88f5qJn+UT6O0mkwa1o3+p5+ss3IRH3gJ9IVAWzNrDWwCriE0Zx7pNeBJM6sB1AJ6AY/4OVAJvoXrdzJyai752woZ2j2dsarti/iq0kB3zhWb2QhgFqHbFp9zzi01s9vC2yc755ab2TtALlBK6NbGvOocuATH3qJD/HHWSl6ct4H0RnV48eaenN+uaayHJZJwtDiXVKtvavt7irjxnEx+c0l76tZWn03keFX1oqjIMdtZeJD731jG9P9som2zerx62zl0b9Uo1sMSSWgKdPGVc443wrX93fsP8csftOXnF55G7RqpsR6aSMJToItvtuzezz0z8pi9PFTbz/lpryObniJSrRToUmWlpY4pCz/nwbeWc6i0lDEDOnLzua1JTdGtiCLRpECXKlm3vZBRU3P5JFzbf3BwF1o1rhvrYYkkJQW6HJfiklL+55/reDhc258wuAtX91BtXySWFOhyzJZt3sPIqbks2bSbvp2a84Bq+yJxQYEunhUdKuHJ99cw+aO1NFRtXyTu6BF0yeY4H/K8aP1OBjw+lyc/WMOg77dg9p19GNDlFIW5SBzRGXoyOY6HPH99oJg/vrOCF+dv4HsNVNsXiWeq/ieTzMzyH+HWqhWsX/+dtz9YuZUx00K1/Z+cnclvL1VtXyTWVP2XEI8Pef4qXNuf9p9NnNa0Lq/edjbdW50UhQGKSFUo0JNJJQ9Z/k5t/6I2/PyiNqrtiwSEAj2ZjB9/5Bw6fPOQ5S92FzF2Rh6zl39J1/QGvHxrLzqeotq+SJAo0JNJOQ9ZLn1gPFPanMeDD3/0TW3/pt6Z1EjVDVAiQaOLokls3fZCRk/LZX7+Ts4+tTEThqi2LxLvdFFUjqDavkhiUqAnmcja/iWdmnO/avsiCUOBniRU2xdJfAr0JLB4w07uejWXtdsKGdItnbEDO9Kobq1YD0tEfKZAT2CFB4r546yVvDBvPd9rUIcXbu5JH9X2RRKWp3vTzKyfma00szVmNqqC/XqYWYmZDfVviHI8Plq1jUsemcML89bzk7Mz+ccd5yvMRRJcpWfoZpYKPAX0BQqAhWY20zm3rJz9JgKzqmOg4s1XhQe5/81lTPu3avsiycbLlEtPYI1zLh/AzKYAg4BlZfb7BTAV6OHrCMUT5xxvLgnV9nftU21fJBl5CfQWwOcRrwuAXpE7mFkL4ErgIioIdDMbDgwHyAivHyJVV7a2/9Itqu2LJCMvgV7efW1l66WPAiOdcyUV3QbnnMsGsiHUFPU4RjkK5xxTFn7OH95crtq+iHgK9AKgZcTrdGBzmX2ygCnhMG8CDDCzYufcDD8GKd+1fnsho6ctYV7+Ds469SQmDO5KZhPV9kWSmZdAXwi0NbPWwCbgGuC6yB2cc60P/9rMngfeUJhXj+KSUp77V6i2XzMlhQcHd+Ea1fZFBA+B7pwrNrMRhO5eSQWec84tNbPbwtsnV/MYJWz5llBtP7dgN307Nef+QadzcgPV9kUkxFOxyDn3FvBWmffKDXLn3I1VH5ZEOlAcqu3/5cNQbf+p67oxoItq+yJyJDVF41xkbX9wtxbcM7CTavsiUi7dDhGnCg8UM27mUoZOnkfRoVJeuLknDx9aSqPO7SAlJfTA55ycWA9TROKIztDj0IcrtzJmeh6bd+/nhrNa8dt+Haj36t+PfHzchg2h1/Dtk4hEJKnpiUVxpGxt/6GhXb+t7Wdmlv+A51atYP36aA5TRGJITyyKc2Vr+yMubMOIi9pwQs2I2v7GjeV/89HeF5Gko0CPsS92F3HPa3m8u6yS2n5GRvln6FpCQUTCgnVRNCcnNPWQABcFS0sdf/tkI30f/oi5q7dx94AOTLv9nKOvwTJ+PKSlHfleWlrofRERgnSGnpOTMBcF128vZNS0XObn7/Re2z98jGPGhKZZMjJCYR6wYxeR6hOci6IJcFHwcG3/z/9YRa3UFEYP6Mi1PVXbFxHvEuOiaMAvCkbW9i/u2JwHfqjavoj4KziBHtCLgpG1/QZ1avLkdWcysMspOisXEd8FJ9DHjz9yDh3i/qLg4g07GTl1CWu2fs3gM1twz2Wq7YtI9QnOXS7DhkF2dmjO3Cz0NTs7uhcFPd5lE1nb33egmOdv6sHDV39fYS4i1So4Z+gQCu9Y3dXh8S6bOau2MXrakiNr+7WD9a9ZRIIpOHe5xFold9ns2neQ+99YztR/F3Bq07o8NKQrWZknRX2YIpLYEuMul1g7yt00buNG3srdwr0z845e2xcRiQIFulfl3GXzZb2TGDvo17z7t3/TpUUDXry5F52+d5Smp4hINVOgexVxl40D/t71EsZfdAsHT0jj7v4duLl3a2qkBucas4gkHgW6V+ELnxsefIRRXQYzr9UZ9KpbzMTbL6y8ti8iEgXJdUpZhcW9iktKeabl2Vx65f3ktevOH67switjrlCYi0jcSJ4z9Cos7nVkbb8ZD/ywi2r7IhJ3kue2xeNY3OtAcQlPvb+GSeHa/n2DOqu2LyIxVeXbFs2sH/AYkAo865ybUGb7MGBk+OXXwO3Ouc+Of8jV4BgX94qs7V95Zgt+p9q+iMS5SgPdzFKBp4C+QAGw0MxmOueWRey2DujjnPvKzPoD2UCv6hjwcfO4uFfhgWL+OGslL8xbz/ca1OH5m3pwQftmURqkiMjx83KG3hNY45zLBzCzKcAg4JtAd859HLH/fCDdz0H6wsPiXodr+5t27eeGs1txl2r7IhIgXtKqBfB5xOsCKj77vgV4u7wNZjYcGA6QEe1lbyt44k/Z2v7/3XY2PVTbF5GA8RLo5V0BLPdKqpldSCjQzy1vu3Mum9B0DFlZWdG/GltmcS/n3BG1/Z9feBq/uKitavsiEkheAr0AaBnxOh3YXHYnM+sKPAv0d87t8Gd41efLPUXcMyOPfyz7ktNbnMgLN/ek8/caxHpYIiLHzUugLwTamllrYBNwDXBd5A5mlgFMA653zq3yfZQ+cs7xv4s+54E3l3OwuJSR/Trw0/NU2xeR4Ks00J1zxWY2AphF6LbF55xzS83stvD2ycDvgMbApPA92sVHu08yljbu2Mfo6bn8a80OerU+iQlDutJaTU8RSRBJUSwqKXU89891/PndldRMSWHUgA5c2yODlBQVhEQkWJJ6PfQVX+xh5Ku5fBau7d//w9M5pUGdWA9LRMR3CRvoB4pLeOqDtUz6YA0N6tTk8WvP5PKuqu2LSOJKyEBfvOErRk3NZXW4tn/PZZ04SbV9EUlwCXVrR+GBYu57fSlDJ39M4YFi/npjDx65+vvxE+ZVWL5XRKQyCXOGPnd1qLZf8FWc1varsHyviIgXgb/LZde+gzzw5nJeXRyq7U8c0jU+a/vHsXyviEhZCXmXi3OOt/O+4HevLeWrfQcZcWEbRlzUJn5r+8e4fK+IyLEKZKBv3VPEPa/lMWvp4dp+j/iv7XtcvldE5HgFLtA/WLmVX77yHw4WlzK6fwduOTcgtX0Py/eKiFRF4AK9deO6dMtoxLgrOgertl/B8r0iIn4I/EVREZFkUtFF0QDMVYiIiBcKdBGRBKFAFxFJEAp0EZEEoUAXEUkQCnQRkQShQBcRSRAKdBGRBBGzYpGZbQPKWdzEkybAdh+HEwQ65uSgY04OVTnmVs65puVtiFmgV4WZLTpaUypR6ZiTg445OVTXMWvKRUQkQSjQRUQSRFADPTvWA4gBHXNy0DEnh2o55kDOoYuIyHcF9QxdRETKUKCLiCSIuA50M+tnZivNbI2ZjSpnu5nZ4+HtuWbWLRbj9JOHYx4WPtZcM/vYzM6IxTj9VNkxR+zXw8xKzGxoNMdXHbwcs5ldYGafmtlSM/so2mP0m4c/2w3M7HUz+yx8zDfFYpx+MbPnzGyrmeUdZbv/+eWci8t/gFRgLXAqUAv4DOhUZp8BwNuAAWcBn8R63FE45nOARuFf90+GY47Y733gLWBorMcdhd/nhsAyICP8ulmsxx2FY74bmBj+dVNgJ1Ar1mOvwjGfD3QD8o6y3ff8iucz9J7AGudcvnPuIDAFGFRmn0HAiy5kPtDQzE6J9kB9VOkxO+c+ds59FX45H0iP8hj95uX3GeAXwFRgazQHV028HPN1wDTn3EYA51zQj9vLMTugvpkZUI9QoBdHd5j+cc7NIXQMR+N7fsVzoLcAPo94XRB+71j3CZJjPZ5bCP0NH2SVHrOZtQCuBCZHcVzVycvvczugkZl9aGaLzeyGqI2ueng55ieBjsBmYAnwK+dcaXSGFxO+51eNKg2nelk575W9x9LLPkHi+XjM7EJCgX5utY6o+nk55keBkc65ktDJW+B5OeYaQHfgB0AdYJ6ZzXfOraruwVUTL8d8KfApcBFwGvCumc11zu2p5rHFiu/5Fc+BXgC0jHidTuhv7mPdJ0g8HY+ZdQWeBfo753ZEaWzVxcsxZwFTwmHeBBhgZsXOuRlRGaH/vP7Z3u6cKwQKzWwOcAYQ1ED3csw3ARNcaIJ5jZmtAzoAC6IzxKjzPb/iecplIdDWzFqbWS3gGmBmmX1mAjeErxafBex2zm2J9kB9VOkxm1kGMA24PsBna5EqPWbnXGvnXKZzLhN4FfhZgMMcvP3Zfg04z8xqmFka0AtYHuVx+snLMW8k9H8kmFlzoD2QH9VRRpfv+RW3Z+jOuWIzGwHMInSF/Dnn3FIzuy28fTKhOx4GAGuAfYT+hg8sj8f8O6AxMCl8xlrsArxSncdjTihejtk5t9zM3gFygVLgWedcube/BYHH3+f7gefNbAmh6YiRzrnALqtrZq8AFwBNzKwAuBeoCdWXX6r+i4gkiHiechERkWOgQBcRSRAKdBGRBKFAFxFJEAp0EZEEoUAXEUkQCnQRkQTx/2M32Zz70Ne9AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "\n",
    "\n",
    "x = np.linspace(0,1,20)\n",
    "xtrue = np.linspace(0,1,100)\n",
    "t_true = 0.1 + 1.3*xtrue\n",
    "\n",
    "t = 0.1 + 1.3*x\n",
    "\n",
    "tnoisy  = t+np.random.normal(0,.1,len(x))\n",
    "\n",
    "plt.scatter(x, tnoisy, c='r')\n",
    "plt.plot(xtrue, t_true)\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Question 1.3 FISTA (3pts)\n",
    "\n",
    "It is possible to improve the ISTA updates by combining them with Nesterov accelerated gradient descent. The resulting update, known as FISTA can read, for a constant step size, by \n",
    "letting $\\mathbf{y}^{(1)} = {\\boldsymbol \\beta}^{(0)}$, $\\eta^1 = 1$ and then using (for $k \\geq 1$) \n",
    "\n",
    "\\begin{align}\n",
    "\\left\\{\n",
    "\\begin{array}{l}\n",
    "&\\boldsymbol{\\beta}^{k} = \\text{ISTA}(\\mathbf{y}^{k})\\\\\n",
    "&\\eta^{(k+1)} = \\frac{1+\\sqrt{1+4(\\eta^{(k)})^2}}{2}\\\\\n",
    "&\\mathbf{y}^{(k+1)} = \\mathbf{\\beta}^{(k)} + \\left(\\frac{\\eta^{(k)} - 1}{\\eta^{(k+1)}}\\right)\\left({\\boldsymbol\\beta}^{(k)} - {\\boldsymbol\\beta}^{(k-1)}\\right)\\end{array}\\right.\n",
    "\\end{align}\n",
    "\n",
    "Here $\\text{ISTA}$ denotes a __single__ ISTA update.\n",
    "\n",
    "Complete the function below so that it performs the FISTA iterations. Then apply it to the data given in question 1.2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def FISTA(X, t, eta1, beta0, lbda):\n",
    "    \n",
    "    '''function should return the solution to the minimization of the\n",
    "    the LASSO objective ||X*beta - t||_2^2 + lambda*||beta||_1\n",
    "    by means of FISTA updates'''\n",
    "    \n",
    "    \n",
    "    \n",
    "    return beta_LASSO "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Question 1.4. (2pts)\n",
    "\n",
    "Compare the ISTA and FISTA updates by plotting the evolution of the loss $\\ell(\\mathbf{\\beta})$ as a function of the iterations for both approaches. Take a sufficient number of iterations (1000 - 10,000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "\n",
    "FISTA_loss = np.zeros((max_iter, 1))\n",
    "ISTA_loss = np.zeros((max_iter, 1))\n",
    "\n",
    "plt.plot(FISTA_loss)\n",
    "plt.plot(ISTA_loss)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Question 2. Classification Trees\n",
    "\n",
    "__(10pts)__\n",
    "\n",
    "When the data is not easily separable, it remains possible to learn a tree based classifier. For a dataset that consists of pairs $\\left\\{(\\mathbf{x}_i, t_i)\\right\\}_{i=1, \\ldots, N}$ where $\\mathbf{x}_i = (x_{i1}, x_{i2})\\in \\mathbb{R}^2$. We start with all the data in a single class. We then consider a split point $(j,s)$ such that it defines the two regions $R_1(j,s) = \\left\\{x|x_j\\leq s\\right\\}$ and $R_2(j, s) = \\left\\{x|x_j>s\\right\\}$\n",
    "\n",
    "In general we seek the splitting variables $j$ and split point $s$ that solve \n",
    "\\begin{align}\n",
    "\\min_{j, s} \\left[\\min_{c_1} \\sum_{\\mathbf{x}_i\\in R_1(j, s)} (t_i - c_1)^2 + \\min_{c_2} \\sum_{\\mathbf{x}_i\\in R_2(j, s)} (t_i - c_2)^2\\right]\n",
    "\\end{align}\n",
    "\n",
    "For which the inner minimization is solved by \n",
    "\\begin{align}\n",
    "\\hat{c}_1 = \\text{average}(t_i|\\mathbf{x}_i \\in R_1(j, s))\n",
    "\\end{align}\n",
    "and \n",
    "\\begin{align}\n",
    "\\hat{c}_2 = \\text{average}(t_i|\\mathbf{x}_i \\in R_2(j, s))\n",
    "\\end{align}\n",
    "\n",
    "Having found the best split, we partition the data into the corresponding two regions and repeat the splitting process on each of the two regions. Note that $s$ should always be taken amond the training points.\n",
    "\n",
    "\n",
    "##### Question 2.1. (10pts)\n",
    "\n",
    "Build a classification tree for the dataset given below with a stopping criterion corresponding to a target that is constant (or almost) across regions. Then plot the result with meshgrid and contourf. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD4CAYAAAD8Zh1EAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8vihELAAAACXBIWXMAAAsTAAALEwEAmpwYAAAbsklEQVR4nO3dYYydVZkH8P+zMzSt1bRGQO60ZVtMxXaxRBwxCxq1E6ewzSxqugQ17i4xIcRlt/CBUDexmcAHa8ym1AhpGkJ0PxHSJbWzg7amjatZZO0gWmybQndcYdohFJWaNG1kyrMf7ly4vX3vve+973nPec55/7+kgbn32nvuK/Pc8z7nOc8RVQUREcXvL0IPgIiI3GBAJyJKBAM6EVEiGNCJiBLBgE5ElIjBUG98+eWX68qVK0O9PRFRlJ577rnXVfWKrOeCBfSVK1diamoq1NsTEUVJRH7X7jmmXIiIEsGATkSUCAZ0IqJEMKATESWCAZ2IKBHBqlzIlj3Pn8S39x3HqTfOYWjpIty/4Vp87iPLQg+LiHrAgE7Y8/xJfP2pF3DuzQsAgJNvnMPXn3oBABjUK2xyehI7frkDr559FVctvgqbb9iMjddsDD0s6oApF8K39x1/O5g3nHvzAr6973igEVFok9OTGH9mHLNnZ6FQzJ6dxfgz45icngw9NOqAAZ1w6o1zPT1O6dvxyx04f+H8RY+dv3AeO365I9CIKA8GdMLQ0kU9PU7pe/Xsqz09TjYwoBPu33AtFl02cNFjiy4bwP0brg00IgrtqsVX9fQ42cCATvjcR5bhm1/4MJYtXQQBsGzpInzzCx/mgmiFbb5hMxYOLLzosYUDC7H5hs2BRkR5sMqFANSDOgO4DRaqSxrvF3oc1BsGdCJDGtUljQXJRnUJgCBBnQE8Lky5BLDn+ZO4edtBrNoyiZu3HcSe50+GHhIZweqS3k1OT2J09yjWfX8dRnePVrq0kjN0z7iJxx5Lu2RZXdIbS3c0FiQ9Q7c4E05pE4/F69urxhfsyTfOQfHOF2yoz8Lqkt5YvqMJceeQbEC39ovakMomHqvXt1fWvmBZXdIbq3c0oXbaJhvQrf2iNqSyicfq9e2VtS/YjddsxPhN46gtrkEgqC2uYfym8UqmD/KwekcT6s4h2Ry6tV/Uhvs3XHtRDh2IcxOP1evbq6Gli3AyY8whv2BZXZLf5hs2X5RDB2zc0YS6c0h2hm51JpzKJh6r17dX3CUbN6t3NKHuHJKdoVueCaewicfy9e1F4/8HK1Uu1DuLdzSh7hySDej8RS1X2dfXZylhCl+wZEuonbaiqqW+QTvDw8M6NTUV5L3JttZafaA++48xNUXkmog8p6rDWc8lm0OneKVSQUPkGwM6mZNKBQ2RbwzoZE4qFTREvjGgkzksJSTqT7JVLhQvVigR9YcBnUxiKWG6ihzgYeHwD8sY0InImyLtbtkqtzvm0InImyJNqyy3yrWCAZ2IvCnStMpqq1xLGNCJyJsiTaustsq1hAHdoBROAiLKUuQADx7+0R0XRY3hmaNUBivVIUWaVpXR8MrKdXGFzbmMuXnbwcwDF5YtXYT/3rI+wIgodq3VIUB9Zmuhb3hIsV6Xws25ROQWETkuIidEZEvG80tEZEJEfi0iR0TkzqKDLpvVtAb7mJBrrA7JluJ16RrQRWQAwCMAbgWwFsAXRWRty8v+CcBRVb0ewKcB/JuILHA8VmcsH3DMPibkGqtDsqV4XfLM0G8EcEJVp1X1zwCeAHBby2sUwHtERAC8G8AfAMw5HalDltuzso8JucbqkGwpXpc8AX0ZgFeafp6Zf6zZdwGsAXAKwAsANqvqW61/kYjcJSJTIjJ1+vTpPodcnOW0RsgzR62moagYVodkS/G65KlykYzHWldSNwD4FYD1AD4A4Mci8jNV/dNF/yPVXQB2AfVF0Z5H64jFk96bhehjwuqadIU6Ds26FK9LnoA+A2BF08/LUZ+JN7sTwDatl8ycEJHfAvgQgF84GaVjqRxw7FKnNBQDeu+slcNZPEjZgtSuS56UyyEAq0Vk1fxC5x0A9ra85mUAIwAgIu8HcC2AaZcDdSlkWsMqy2mo2DTK4WbPzkKhbzeRmpyeDD20vkxOT2J09yjWfX8dRnePRvs5qqDrDF1V50TkHgD7AAwAeFxVj4jI3fPP7wTwEIDvicgLqKdoHlDV10scd2Fsz3ox62momHQqh4ttNsgOh3HJtVNUVZ8G8HTLYzub/v0UgFG3Q0vTnudPmjy4gWkod1Iqh0vpy6kKuPXfI8sLj9ZPCbL6RZjlqsVXYfbsbObjsUnpy8m3EOsoDOgelb3wWDToWU1DWf4izLL5hs2ZW8pjLIdL6cvJp1CpKnZb9KjMhUfLu1+LsrwRLMvGazZi/KZx1BbXIBDUFtfM9wdpJ8VabR9CtRXgDN2jMhceUy47jLECJ5VyuBRrtX0IlapiQPeozIXHGINeXqzACSuVLyefQqWqmHLxqMz695SberG/Dfngst4+VKqKM/Q+FFl8LGvhMeWyQ+sVOFS+sitGXC9ihkpV8YCLHrVWXAD1wGlhp2lMpX1Eefk4iGJ092hmiqS2uIb9m/Y7eQ9XOh1wwRl6jywvPlotOyQqwsfmplTq7ZlD71HKi49EFvkItqn0RmdA71HKi49EFvkItqnU2zOg94gVF0R++Qi2qWwGYw69R74qLrjASVTnq2IkhXp7VrkYZLmShqgba4d7pIZVLpHpt5KGs3oKjf3Tw2IO3aB+KmlSbs5Fbvg4eShUUyqqY0A3qJ9Kmtg6EpJfvo7Fc1liyKPveseAblA/lTSsjw/LevDxNXN2VWKY2rmsvjCgG9RPEy/Wx4cTQ/DxtRPSVYkhUzf94aKoUb1u47fanKsKC7UxnLvpq52rqxLDsr+AXFXiWKvoYUBPhMWOhLEdHdevGPqA+DwWz0U9d5lfQK4qcSxW9CQf0H3MEK3MQq0157LcyMylGM7djO3koTK/gFzdUVm8M0s6oPuYIRZ9DytfBmWoykJtLIdCx7QTsswvIFd3VBbvzJIO6D5miEXeI/WURFWOjott9huLsr6AXN1RWbwzS7rKxccMsch7pF47XqVGZhuv2Yj9m/bj8D8cxv5N+xnMDXNViWOxQ2PSM3QfM8Qi75F6SsLiQi2Rqzsqi3dmSQd0H6V8Rd6jCikJawu1RIC7dI61dYmkUy79bNDx+R5VSkkQUfnYPjewlKtciMg9ts81jCkJqjJrOy1jx4BOREFY3GkZu6Rz6PSOPc+fxM3bDmLVlkncvO0g+6RTcGzA5R5n6Aa5zqunvoGJ4mRxp2XsOEN3wOXst4yTh1LfwERxctU7nd7BgF6Q6wBcRvD1uYGJqR3Ky+JOy9gxoBfkOgCXEXx9HX7Bc02pFxuv2Yjxm8ZRW1yDQFBbXMP4TeNcEC0gVw5dRG4BsAPAAIDHVHVbxms+DeBhAJcBeF1VP+VslIa5DsBl7B71dfiFxXa5rPO3rcydllUsiew6QxeRAQCPALgVwFoAXxSRtS2vWQrgUQB/q6p/BeDv3A/VJtez3zJ2j/rYMQvY603DO4bqiuFYwDLkmaHfCOCEqk4DgIg8AeA2AEebXvMlAE+p6ssAoKqvuR6oVa5nv2U1tPKxgclabxqLdwwWVGHmavHwCR/yBPRlAF5p+nkGwMdbXvNBAJeJyE8AvAfADlX999a/SETuAnAXAFx99dX9jNe7brfsZQTgWHePWjvX1NodgwVV2cxT1ZLIPAFdMh5rbQAzCOCjAEYALALwcxF5VlVfvOh/pLoLwC6g3sul9+H6lbd+O9YA7Jq1drnW7hgsqMrM1eLhEz7kCegzAFY0/bwcwKmM17yuqmcBnBWRnwK4HsCLiBhv2Xtn6cvN2h2DBVWZucZyLKBrecoWDwFYLSKrRGQBgDsA7G15zQ8AfFJEBkXkXainZI65Hap/vGWPm6/F4JhUZTNPVUsiu87QVXVORO4BsA/1ssXHVfWIiNw9//xOVT0mIj8CcBjAW6iXNv6mzIH7wFv2+Fm6Y7CgSjNXn4dPWFloZj/0Dlpz6ED9lr3qszxfWENeDivBJxWtC81A/UuyrDuCTv3QGdC7YFAJg1+mFIvR3aOZC7C1xTXs37Tf+fslc8BFiODKW/YwuCBNsbC00BxNLxfu+qsWLkinZXJ6EqO7R7Hu++swuns0qR2blhaaownobAFbLb4ailH5Ut+Gb6lrZDQBnTO2aimjpw2FkfrJRJZKJKPJobOEsFqs7Tql/lnKMZfFZ4lkJ9EEdO76qx4uSKehqtvwQ4gm5cJdf2QJT2bKz1KOOXXRzNABztjIBh663ZtGKoKbmcoXVUAnsoA18r2zkmNOXTQpFyIrWHFFVjGgE/WINfJkFQM6UY9YI09WMYdO1CPWyJNVDOhEfSi74urMxARe2/4w5mZnMVir4cr77sWSsbHS3o/SwIBOZMyZiQnMfmMr9Hx9u/zcqVOY/cZWAGBQp46YQ3ft8JPA9uuA8aX1fx5+MvSIKDKvbX/47WDeoOfP47XtD4cZEEWDM3SXDj8JTPwL8OZ8+dqZV+o/A8C628ONi6IyN3vpNvlOjxM1cIbu0oEH3wnmDW+eqz9OlNNgrdbT40QNDOgunZnp7fGyMO0TtSvvuxey8OLeJ7JwIa68794wA6JoMOXi0pLl9TRL1uO+MO0TvcbCJ6tcqFcM6C6NbL04mALAZYvqj/vSKe3DgB6NJWNjDODUM6ZcXFp3OzD2HWDJCgBS/+fYd/wGUitpH6IMZyYm8NL6ERxbsxYvrR/BmYmJ0ENKCmforq27PexM2ELahygD6+vLxxl6aka21tM8zXynfYgysL6+fAzoqbGQ9iHKULX6+hDpJaZcUhQ67UOUYbBWw9ypU5mPpyZUeokzdPKDtfHOhFpYLPq+VaqvD5VeSmOGfvjJelnemZn64t/IVs5QLWFtvDOhZn4u3rdK9fWh0kuiqqW+QTvDw8M6NTVV/C9qDRZAfRGQeWM7tl/XpvJmBXDfb/yPJ2IvrR/JTlsMDWH1wQPJvW+syrxeIvKcqg5nPRd/yoX9U+xjbbwzoWZ+VVnQdJXOCpVeij+g+woWzAH3r10NPGvjexaqcVfohmE+1g0aaaW5U6cA1bfTSv2815KxMdQeehCDQ0OACAaHhlB76MHS00vxB3QfwaKR1jnzCgB9JwfMoJ4Pa+OdCTXzC7mg6TLQduJ6IXPJ2BhWHzyANceOYvXBA17WCuIP6D6CBdM6xbA23plQM79Q7wv4qxhJIa0Uf5VLIyiUWeXCHHBxrI13JlTjrlDv6yvQplAnH39AB8oPFuyPQhSMr0B75X33XlSaCcRXJ58r5SIit4jIcRE5ISJbOrzuYyJyQUQ2uRuiAVXOAXMxmALzlb8PmVZypesMXUQGADwC4LMAZgAcEpG9qno043XfArCvjIEG5SOtYxE3BJEBPjckxd6HvuvGIhH5awDjqrph/uevA4CqfrPldfcCeBPAxwD8p6ru7vT3OttYROXhhiAic4puLFoGoPm3emb+seY3WAbg8wB2dhnIXSIyJSJTp0+fzvHWlFsZqREuBhNFJU9Al4zHWqf1DwN4QFUvdPqLVHWXqg6r6vAVV1yRc4jUVVl18kVq/Jl7p4qxcBpTnoA+A2BF08/LAbQuOQ8DeEJE/g/AJgCPisjnXAwwWS4DXll18v0uBnMjFlWMr81P3eQJ6IcArBaRVSKyAMAdAPY2v0BVV6nqSlVdCWA3gK+p6h7Xg02G64BXVmqk3w1B3IhFFWPlNKauVS6qOici96BevTIA4HFVPSIid88/3zFvThk6Bbx+qkfKrJPvp8afuXeqGCu7THNtLFLVpwE83fJYZiBX1X8sPqzEuQ54I1uzWwiHqpPnRiyqGCu7TOPv5RIj1w3FrPVKqfJGLKokK6cxpbH1PzZlzKgt9Uqp6kYsqiwrpzHFf2JRrHhsXh2vA1FPOm0s4gw9FEsz6lBBla0FyKEzExPBZ8ihMYdedSFrxlneSI5YqQMPjQG96kIGVZY3kiNW6sBDY0CvupBB1UW1D1sMEOzUgYfGgA5UOyiEPMC5aHkjWwzQvNCHWFvBgF71oBCyZrxo/Txz8OWIcIJjpQ48NFa5uN6GH1qvFSuha8aLVPswB+9epJVHVurAQ2NATyko9PvLaKmEshfWWwzEWGMf8QQn9tOGXGDKJaWe375SEFY+t+UWA7Gm8lKa4FQQA3pKPb99/DJa+tzWetg0izW/H3KRnApjQE+p57ePX0Zrn3vd7fXzTcffqP/TQjAH4p3pWr7roa6YQwfS6fnto42uxc9tkfX8fjuhF8mpEAb0fln8hfXxy2jxc1tkrUd9L2JdJCcG9L5Z/YUt+5fR6ue2hjNdCoABvV9Ff2FjLGkDGKh6wZluJVjq8sh+6CG01osD9VmulQoNooiEDKiNLo/NjcFk4ULUHnqwtDF06ofOKpcQrFWKEEUqdNtca10eGdBDYKUIkROuAuqZiQm8tH4Ex9asxUvrR3J/IVjr8siAHgI3bxA54SKgFpnlW+vyyIAeAjdvXMpnOwErrQuKSOEzOOAioBaZ5Vvr8siAHoLlLesh+GwnYKl1Qb9S+AyOuAioRWb5S8bGUHvoQQwODQEiGBwaKnVBtBtWuVB4269rs1lpRX07f6zvVZYUPkOGfqtVila5vLR+pJ5uaTE4NITVBw/09Bm6cVGR06nKhXXoKYqtxt3nInEKC9IpfIYWreV/jTw2gK4Br2jb3Cvvuzez9NB12qTIZ8yLKZfUuL4d95Gr9blInMKCdAqfoUXI8j9faRMfn5EBPTUua9x95Wp9LhKnsCCdwmdoEbr8b8nYGFYfPIA1x45i9cEDpeTAfXxGBvTUuLwd97UByucicQoL0il8hhbWyv/K4OMzxp9Djy1fXDaX3RB95mp99j1JocdKCp+hia88dkg+PmPcM/TYy7fKyE+7vB1PMFdLNlkr/yuDj88Yd9lizOVbZTbocnXXwiZiROakW7YYc/lWmaeru7odZ6tcqihLLXF7EXdAj/n0nFi+jBLL1RJ146NevCxx59B9lm+5znczP00J6bdboUXWWuL2Iu6A7qt8q4zF1wRriamaQvckdy10TXwRuQK6iNwiIsdF5ISIbMl4/ssicnj+zzMicr37obax7vb6Auj4G/V/lpEeKKMeO8FaYqqmUDPasu4KYq6J75pDF5EBAI8A+CyAGQCHRGSvqh5tetlvAXxKVf8oIrcC2AXg42UMOIiy8t3MT1MCQsxoy8xzu6wX9724mmeGfiOAE6o6rap/BvAEgNuaX6Cqz6jqH+d/fBZAWolg5ruJ2goxoy3zrsBVvXiIVFSegL4MQHMpycz8Y+18FcAPs54QkbtEZEpEpk6fPp1/lKHFmO/mAQjkSYhDHsq+K3DR2yVEKipP2aJkPJa5G0lEPoN6QP9E1vOqugv1dAyGh4fD7GjqR2z12K0bghqLuIDdMVO0GsHOZ2phsFbL7mFuKM8dIhWVJ6DPAFjR9PNyAJdcSRFZB+AxALeq6u/dDM+QmPLdZW5aIspQtCd5r2Lo/RLiSydPyuUQgNUiskpEFgC4A8De5heIyNUAngLwFVV90f0wqSexbFoi6pOLPHfZtfMhUlFdZ+iqOici9wDYB2AAwOOqekRE7p5/fieArQDeB+BREQGAuXa9BsiDmHfQEuVU5K7Ax27QEKmouJtzUTY21aIIhOyX4vMcUdfSbc5F2WJbxKXKCd0vJebdoJ0woIdS9sEcMS3iUs9i7QbY0Kmkz8fniKFKph9x93KJVewHc1BQKfROCT1DDrFg6QMDegi+zuqkJMXcDbAhdL+UVE9IYsqlk7LSIiwrpAJCz25dsFBH7rt23gfO0NspMy3C3jBUQOjZrQupzpC7Kbv2nQG9nTLTIjH2hiEzrOR/iwYnF/1SYuJj7YMBvZ0y0yLshU4FWJjdprAw248iX2I+1j64said7de12W25on6QRlWUXV5JUYp5Y06/WmvngfqdUd4v02Nr1gJZ8VYEa44dvfTxNjptLOIMvR2mRVheSW1ZWZj1eZZp0Rm2j7UPBvR2mBZheSW1ZWFh1nfap+iXmI+1D5YtdlL13ZYsr6Q2LJQd+t5tWnR3qY9mXQzo1B67NlIbIToJtvKd9nHxJVZ27TsDOrU3sjW7a2OV1hGordAbc3z3Y7HwJdYNAzq1x66NZFiItE/oL7FuGNCps6qvI1Dfyu4IGcOM2TcGdCJyzle/c+szZt9YtkhEzqXQETJGDOhE5JyVjUeW+NgExYBORM4V3XjkcweoD742QTGgE5FzRXZFptj4y1cKigGdiJwr0hEyxfy7rxQUq1yIKFPRssN+K1BC5d/LLLP0tQmKM3QiukTItEeIxl9lf15fh5IwoBPRJUKmPUKcyFT25/V1KAlTLkR0iZBlhyF2gPr4vD42QTGgE9ElfDe+auV7B2joz+sKUy5EdAkrB1H7ksrn5QydiC5RtcZXqXxeHhJNRBQRHhJNRFQBDOhERIlgQCciSgQDOhFRIhjQiYgSEazKRUROA/hdkDcv3+UAXg89CKN4bdrjtWmP1+Ydf6mqV2Q9ESygp0xEptqVFVUdr017vDbt8drkw5QLEVEiGNCJiBLBgF6OXaEHYBivTXu8Nu3x2uTAHDoRUSI4QyciSgQDOhFRIhjQCxCRW0TkuIicEJEtGc9/WUQOz/95RkSuDzHOELpdm6bXfUxELojIJp/jCynPtRGRT4vIr0TkiIj8l+8xhpLjd2qJiEyIyK/nr82dIcZplqryTx9/AAwA+F8A1wBYAODXANa2vOYmAO+d//dbAfxP6HFbuTZNrzsI4GkAm0KP28q1AbAUwFEAV8//fGXocRu6Nv8K4Fvz/34FgD8AWBB67Fb+cIbevxsBnFDVaVX9M4AnANzW/AJVfUZV/zj/47MAlnseYyhdr828fwbwHwBe8zm4wPJcmy8BeEpVXwYAVa3K9clzbRTAe0REALwb9YA+53eYdjGg928ZgFeafp6Zf6ydrwL4YakjsqPrtRGRZQA+D2Cnx3FZkOe/mw8CeK+I/EREnhORv/c2urDyXJvvAlgD4BSAFwBsVtW3/AzPPh5B1z/JeCyzBlREPoN6QP9EqSOyI8+1eRjAA6p6oT7Zqow812YQwEcBjABYBODnIvKsqr5Y9uACy3NtNgD4FYD1AD4A4Mci8jNV/VPJY4sCA3r/ZgCsaPp5OeqzhouIyDoAjwG4VVV/72lsoeW5NsMAnpgP5pcD+BsRmVPVPV5GGE6eazMD4HVVPQvgrIj8FMD1AFIP6HmuzZ0Atmk9iX5CRH4L4EMAfuFniLYx5dK/QwBWi8gqEVkA4A4Ae5tfICJXA3gKwFcqMLtq1vXaqOoqVV2pqisB7AbwtQoEcyDHtQHwAwCfFJFBEXkXgI8DOOZ5nCHkuTYvo37nAhF5P4BrAUx7HaVhnKH3SVXnROQeAPtQX51/XFWPiMjd88/vBLAVwPsAPDo/E53TCnSMy3ltKinPtVHVYyLyIwCHAbwF4DFV/U24UfuR87+bhwB8T0ReQD1F84Cqsq3uPG79JyJKBFMuRESJYEAnIkoEAzoRUSIY0ImIEsGATkSUCAZ0IqJEMKATESXi/wH9gaEyfG43YQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import scipy.io\n",
    "\n",
    "class1 = scipy.io.loadmat('points_Assignment2_Ex2_class1.mat')['points_Assignment2_Ex2_class1']\n",
    "class2 = scipy.io.loadmat('points_Assignment2_Ex2_class2.mat')['points_Assignment2_Ex2_class2']\n",
    "class3 = scipy.io.loadmat('points_Assignment2_Ex2_class3.mat')['points_Assignment2_Ex2_class3']\n",
    "class4 = scipy.io.loadmat('points_Assignment2_Ex2_class4.mat')['points_Assignment2_Ex2_class4']\n",
    "\n",
    "\n",
    "plt.scatter(class1[:,0], class1[:,1])\n",
    "plt.scatter(class2[:,0], class2[:,1])\n",
    "plt.scatter(class3[:,0], class3[:,1])\n",
    "plt.scatter(class4[:,0], class4[:,1])\n",
    "plt.show()\n"
   ]
  }
 ],
 "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
}