linear-regression-using-the-normal-equation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "983d139e",
   "metadata": {
    "papermill": {
     "duration": 0.008184,
     "end_time": "2023-03-24T23:10:42.081555",
     "exception": false,
     "start_time": "2023-03-24T23:10:42.073371",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# Introduction  <a id='introduction'></a>\n",
    "\n",
    "In [Multivariate Linear Regression From Scratch](https://www.kaggle.com/code/erkanhatipoglu/multivariate-linear-regression-from-scratch) notebook, we have seen how to utilize the gradient descent algorithm to solve a multiple linear regression task. We have used the negative gradient of the cost function j(θ) and taken tiny steps to calculate the θ vector that minimizes j(θ) to find the best linear fit for our data. Yet, we may have an alternative analytical solution called the 'normal equation' for a linear regression task.\n",
    "\n",
    "We will first explain the 'normal equation' and compare it with gradient descent to identify the advantages and limitations. Then, we will use the dataset we used in the [Multivariate Linear Regression From Scratch](https://www.kaggle.com/code/erkanhatipoglu/multivariate-linear-regression-from-scratch) notebook to find the θ vector using the 'normal equation.' We will then validate our data with the same validation data we used earlier and compare the results. Interested Kagglers may refer to the [References](#references) section for my works on linear regression for more detailed explanations.  \n",
    "\n",
    "This notebook is greatly inspired by the famous Machine Learning course by [Andrew Ng](https://www.andrewng.org/). All the mistakes, if any, are made by me.\n",
    "\n",
    "Finally, thanks to [@Mohan S Acharya](https://www.kaggle.com/mohansacharya) for this dataset.\n",
    "\n",
    "\n",
    "# Table of Contents\n",
    "* [Introduction](#introduction)\n",
    "* [Helper functions](#functions)\n",
    "* [The Normal Equation](#normal)\n",
    "* [The Hypothesis](#hypothesis)\n",
    "* [The Cost Function](#cost)\n",
    "* [Loading Data](#getdata)\n",
    "* [Model Training](#training)\n",
    "* [Model Validation](#validation)\n",
    "* [Conclusion](#conclusion)\n",
    "* [References](#references)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "90ae495c",
   "metadata": {
    "_cell_guid": "b1076dfc-b9ad-4769-8c92-a6c4dae69d19",
    "_uuid": "8f2839f25d086af736a60e9eeb907d3b93b6e0e5",
    "execution": {
     "iopub.execute_input": "2023-03-24T23:10:42.096901Z",
     "iopub.status.busy": "2023-03-24T23:10:42.096498Z",
     "iopub.status.idle": "2023-03-24T23:10:43.128983Z",
     "shell.execute_reply": "2023-03-24T23:10:43.128030Z"
    },
    "papermill": {
     "duration": 1.04338,
     "end_time": "2023-03-24T23:10:43.131848",
     "exception": false,
     "start_time": "2023-03-24T23:10:42.088468",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "/kaggle/input/graduate-admissions/Admission_Predict.csv\n",
      "/kaggle/input/graduate-admissions/Admission_Predict_Ver1.1.csv\n"
     ]
    }
   ],
   "source": [
    "# This Python 3 environment comes with many helpful analytics libraries installed\n",
    "# It is defined by the kaggle/python Docker image: https://github.com/kaggle/docker-python\n",
    "# For example, here's several helpful packages to load\n",
    "\n",
    "import numpy as np # linear algebra\n",
    "import pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)\n",
    "\n",
    "# Input data files are available in the read-only \"../input/\" directory\n",
    "# For example, running this (by clicking run or pressing Shift+Enter) will list all files under the input directory\n",
    "\n",
    "import os\n",
    "for dirname, _, filenames in os.walk('/kaggle/input'):\n",
    "    for filename in filenames:\n",
    "        print(os.path.join(dirname, filename))\n",
    "\n",
    "# You can write up to 20GB to the current directory (/kaggle/working/) that gets preserved as output when you create a version using \"Save & Run All\" \n",
    "# You can also write temporary files to /kaggle/temp/, but they won't be saved outside of the current session\n",
    "\n",
    "from sklearn.model_selection import train_test_split # Split data into train and validation sets\n",
    "from numpy import linalg # Calculate the inverse of a matrix\n",
    "import matplotlib.pyplot as plt # Data visualization\n",
    "from time import process_time # Calculate elapsed CPU time"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e7f9ba9f",
   "metadata": {
    "papermill": {
     "duration": 0.006335,
     "end_time": "2023-03-24T23:10:43.144770",
     "exception": false,
     "start_time": "2023-03-24T23:10:43.138435",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# Helper Functions   <a id='functions'></a>   "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e68a131a",
   "metadata": {
    "papermill": {
     "duration": 0.006005,
     "end_time": "2023-03-24T23:10:43.157204",
     "exception": false,
     "start_time": "2023-03-24T23:10:43.151199",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "<div class=\"alert alert-block alert-info\">\n",
    "<b>Tip:</b> We will use some helper functions throughout the notebook. Collecting them in one place is a good idea, making the code more organized. First, we will define and explain those functions and then use them in our code.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ffe290df",
   "metadata": {
    "papermill": {
     "duration": 0.006001,
     "end_time": "2023-03-24T23:10:43.169530",
     "exception": false,
     "start_time": "2023-03-24T23:10:43.163529",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# The Normal Equation   <a id='normal'></a> "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad0cbdf9",
   "metadata": {
    "papermill": {
     "duration": 0.006091,
     "end_time": "2023-03-24T23:10:43.182025",
     "exception": false,
     "start_time": "2023-03-24T23:10:43.175934",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "As we all know, gradient descent is an iterative algorithm that must be conducted repeatedly until convergence. Especially for a small number of features, alternatively, we may use a much faster method called the 'normal equation.' The idea is as follows:\n",
    "\n",
    "We know that for a function of f(θ), the θ values that make the derivative of f(θ) zero are the maximum or minimum point for f(θ). For our specific squared error cost function, it turns out that this is the minimum point. We can understand this by the following figure:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "dc4416fa",
   "metadata": {
    "_kg_hide-input": true,
    "execution": {
     "iopub.execute_input": "2023-03-24T23:10:43.197696Z",
     "iopub.status.busy": "2023-03-24T23:10:43.196619Z",
     "iopub.status.idle": "2023-03-24T23:10:43.667995Z",
     "shell.execute_reply": "2023-03-24T23:10:43.666673Z"
    },
    "papermill": {
     "duration": 0.482194,
     "end_time": "2023-03-24T23:10:43.670890",
     "exception": false,
     "start_time": "2023-03-24T23:10:43.188696",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAdIAAAHaCAYAAAC0M8hbAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/NK7nSAAAACXBIWXMAAA9hAAAPYQGoP6dpAABH4ElEQVR4nO3deXhTdd4+/vtkb+i+L7TQQqFAWVtAAUVcUEEccFfcddQZHEBnfBTHcR2oOurPhUccHAfwYXD5Oq6DW0cUREDWspVFytLSUkpLm3RNmuT8/mgTqIXSNmk+5yT367pyXfY0bd+GNvf57JIsyzKIiIioWzSiCyAiIlIzBikREZEXGKREREReYJASERF5gUFKRETkBQYpERGRFxikREREXmCQEhEReYFBSkRE5AUGKRERkRcYpERERF5gkBIFgKVLl0KSJBw+fLjN9WeffRaDBw+Gy+Vq9zVWqxV/+tOfkJqaCpPJhDFjxmD9+vWez7/zzjtISUlBfX19T5dPpGoSN60nUr8TJ06gqKgII0eOhNFoBACUlZVhwIABWLp0Ka677ro2z6+srMSkSZNgMpnw2GOPwWw244knnsDhw4dx4MABREVFweFwYPDgwbj55pvxzDPPiPjfIlIFBilRgHr00Ufxr3/9C8XFxdBo2nY+XXXVVTh8+DA2btwIs9kMANi0aRPGjBmDJUuW4M477wQAvPzyy3juuedQVlbmeR4RtcWuXaIA8OuuXbvdjnfeeQe33HJLuxBdtWoVVq5ciVdeeaVNOGZkZAAADh486Lk2c+ZMWK1WvP/++z3/P0GkUgxSogD0888/o6qqCpMmTWr3ucWLF6Nv376YNGkSHA6H52G1WgEAer3e89zExERkZWVh5cqVfqudSG10ogsgIt9zTxoaNWpUm+sulwvffPMNampqYDAYzvi16enpbT4eNWoU/vvf//ZMoUQBgEFKFIDKysogSRJiY2PbXN+3bx9qamrw3HPP4YorrmjzuYULF2LZsmUYM2ZMm+vx8fGoqKiAw+GATse3DKJf418FUQBqbGyEXq+HVqttc909hjp27Fjk5ua2+dyuXbvQr18/DBgwoM11k8kEWZbR1NSE0NDQHq2bSI04RkoUgGJjY2G329utAW1ubgaAdgFbUFCALVu24L777mv3vU6ePAmj0cgQJToLBilRAMrKygIAFBUVtbnunpm7c+dOzzWHw4HZs2cjPT0dDz74YLvvdfDgQQwePLgHqyVSN3btEgWgiy66CACwYcMGDBs2zHM9OzsbOTk5+Otf/4qEhARERETg5ZdfRmFhIb777rt2a0VdLhc2btyIe+65x5/lE6kKW6REAUSSJABAamoqLrjgAnz22WftnvPvf/8bOTk5uOeee3DrrbciMTERmzdvxvDhw9s994cffoDFYsHMmTN7vHYitWKLlCgAWCwWAEBMTIzn2pw5c3DjjTeitLQUKSkpnut9+vTB119/3anvu2TJEowbN67dMhoiOoVbBBKpmMViwfr16zFv3jw4HI42Y5+yLGPcuHHIycnBwoULu/y9i4qKMGjQIKxatQoTJkzwZdlEAYVdu0Qqtm3bNsyYMQMGgwHLli1r8zlJkvD2228jOTn5jKe/nEtxcTEWLlzIECU6B7ZIiYiIvKCoFumaNWswbdo0JCcnQ5IkfPrpp20+L8synn76aSQnJyMkJAQXXXQRdu/eLaZYIiIiKCxI6+vrMXz48LOO57z44ot45ZVXsHDhQmzatAmJiYm47LLLUFtb6+dKiYiIWii2a1eSJHzyySeYPn06gJbWaHJyMubOnYtHH30UAGCz2ZCQkIAXXngB999/v8BqiYgoWKlm+cuhQ4dQXl6OyZMne64ZjUZMnDgR69atO2OQ2mw22Gw2z8culwsnT55ETEyMZ70dEREFH1mWUVtbi+Tk5HZn9naVaoK0vLwcAJCQkNDmekJCAo4cOXLGr8nLy8MzzzzT47UREZE6lZSUoHfv3l59D9UEqduvW5KyLJ+1dTlv3jw8/PDDno8tFgvS0tJQUlKC8PDwHq1TbY6ebMAVr/0IvVbCxj9fCr1WUcPnRNRFj360HSt3lmP2Jf1x34X9RJejOFarFampqQgLC/P6e6kmSBMTEwG0tEyTkpI81ysqKtq1Ut2MRiOMRmO76+Hh4QzSXxkUFobw8HDU2RyotGkxMNH7Xy4iEueQVYbGaMbIfsl8v+uAL4b5VNPsSE9PR2JiIvLz8z3X7HY7Vq9ejXHjxgmsLDBIkuQJz73lVsHVEJE3mp0uFJ2oAwDeFPuBolqkdXV1OHDggOfjQ4cOoaCgANHR0UhLS8PcuXOxYMECZGZmIjMzEwsWLIDZbMYtt9wisOrAMTAxDFuOVGNveS1+I7oYIuq2gyfq0eyUEWbUISUyRHQ5AU9RQbp582ZMmjTJ87F7fPOOO+7A0qVL8T//8z9obGzE73//e1RXV2Ps2LH49ttvfdLHTcCg1jvXfeVcl0ukZu5epYGJYVyh4AeKCtKLLroIHS1rlSQJTz/9NJ5++mn/FRVEBia2jKPsPcauXSI129t6M8xuXf9QzRgp9byBCS1/dGWWJlgamwVXQ0Td5e5VymKQ+gWDlDwizHokR5gAAPuPs3uXSK08QZrE2br+wCClNjwzd9m9S6RKlsZmlNY0AgAGJLBF6g8MUmrDM07KCUdEquTuTUqOMCEiRC+4muDAIKU2BiVx5i6Rmrl7k9it6z8MUmpj4GlLYBR6MBARdYAzdv2PQUptZMSGQqeRUGtzeMZZiEg9OGPX/xik1IZBp0H/+FAA7N4lUhtZlk8LUnbt+guDlNo5tecug5RITUprGlFrc0CvlZAR10t0OUGDQUrtMEiJ1MndGu0XF8qjEP2IrzS1M6i1S2gfT4EhUpW9HB8VgkFK7bhbpEUn6mFzOAVXQ0SddWrGLsdH/YlBSu0kRZgQZtLB6ZJRVFEvuhwi6iTPGlK2SP2KQUrtSJJ0qnv3OLt3idTA5nDiYGXLjW9WEoPUnxikdEan9tzlhCMiNSiqqIfTJSPcpENiuEl0OUGFQUpnxJm7ROriPsw7KzGch3n7GYOUzoh77hKpy6mj09it628MUjoj9/FL5dYm1DTYBVdDROfCPXbFYZDSGYWZ9EiJDAHA7l0iNTjVtcsg9TcGKZ0Vu3eJ1KG63o7jVhsAHuYtAoOUzurUhCMugSFSMnevUe+oEISZeJi3vzFI6azcu6Owa5dI2faxW1coBimd1aDWP8r95bVwuXjIN5FS7TvOo9NEYpDSWfWN7QWDVoN6uxNHq3nIN5FS7TnGGbsiMUjprPRaDfq1HvLNcVIiZXK5ZOw/zlNfRGKQUofc3bucuUukTEerG9Fgd8Kg1SA9lod5i8AgpQ5xq0AiZdvT2lvUPz4UOh7mLQRfdeoQl8AQKds+HuYtHIOUOjQoqWUW4KHKejTaecg3kdLscZ9Byj12hWGQUofiw4yIDTXAJbNVSqREu8ta/i6HJEcIriR4MUipQ5IkYXDrH+iuMgYpkZJYGptRfLIBADAkmWtIRWGQ0jm5/0ALyyyCKyGi0xW23tymRIYg0mwQXE3wYpDSOWW3tkh3s0VKpCi7W29u2RoVi0FK5+T+I91bXotmp0twNUTkVsjxUUVgkNI5pUWbEWrUwe5w4UBFnehyiKjVLrZIFYFBSuek0UgY3PqHyu5dImVoanai6EQ9ACA7hS1SkRik1ClDPEHKCUdESrC3vBZOl4yYXgYkhBtFlxPUGKTUKe4xmN2lbJESKcGu0pab2sHJ4ZAkSXA1wY1BSp2SndK6BOaYlWeTEimAe5iF3briMUipU/rFhcKg06DO5vAsACcicQo50UgxGKTUKXqtxrMpNiccEYnV7HRhT+tm9Vz6Ih6DlDrNfee7ixOOiIQqOlEHu8OFUKMOfaLNossJegxS6rQh3OGISBHck/4GJ4VDo+FEI9EYpNRpniUwpRbIMiccEYnivpkdzPFRRWCQUqdlJYZDIwFV9XYct9pEl0MUtLijkbIwSKnTQgxa9I8PBcCNGYhEcblk7OHSF0VhkFKXcJyUSKyS6gbU2hww6DSeG1sSi0FKXcKtAonEct/EDkwIg17Lt3Al4L8CdYm7RbqLWwUSCeHeGtC92xiJxyClLnHPEiytaURNg11wNUTB59SMXY6PKgWDlLokIkSP1OgQAKcOFSYi/5Bl2TOswhm7ysEgpS4bktTavctxUiK/qqi1obLODo0EDEpkkCoFg5S6zD02w5m7RP7lbo32iwtFiEEruBpyY5BSl3EJDJEY7q0B2a2rLAxS6jL3H/HBE3VosDsEV0MUPNw3rzzxRVkYpNRl8eEmxIUZ4ZKBPcdqRZdDFDQ8WwNy6YuiMEipW9yt0kJOOCLyC0tDM45WNwI4NeGPlIFBSt1yaocjjpMS+cPuYy03rb2jQhBh1guuhk7HIKVu8exwxBYpkV9wopFyqSpIHQ4HnnjiCaSnpyMkJAQZGRl49tln4XK5RJcWdLJbg3R/eR2anXz9iXqae+lLNicaKY5OdAFd8cILL+Ctt97CsmXLMGTIEGzevBl33XUXIiIiMGfOHNHlBZXU6BCEmXSobXLgl+N1PGCYqId5ZuxyopHiqCpI169fj9/85jeYOnUqAKBv37547733sHnzZsGVBR9JkjA4KRw/HzqJ3WUWBilRD2q0O1F0og4Al74okaq6didMmIDvvvsO+/fvBwBs374da9euxZQpU874fJvNBqvV2uZBvuM+VJgTjoh61p5yK1wyEBtqRHyYUXQ59CuqapE++uijsFgsyMrKglarhdPpxPz583HzzTef8fl5eXl45pln/Fxl8ODZpET+cWojhnBIkiS4Gvo1VbVIP/jgAyxfvhwrVqzA1q1bsWzZMrz00ktYtmzZGZ8/b948WCwWz6OkpMTPFQc2dxdTYZkVLpcsuBqiwFXIE18UTVUt0kceeQSPPfYYbrrpJgDA0KFDceTIEeTl5eGOO+5o93yj0Qijkd0gPaVfXC8YdRrU2504XFWPjLhQ0SURBaRdrUtf3MMppCyqapE2NDRAo2lbslar5fIXQXRaDbKSuDEDUU9qdrqwr7xlK062SJVJVUE6bdo0zJ8/HytXrsThw4fxySef4JVXXsGMGTNElxa0uMMRUc86UFEHu9OFMKMOqVFm0eXQGaiqa/eNN97AX/7yF/z+979HRUUFkpOTcf/99+PJJ58UXVrQ4oQjop7lvkkdlBwOjYYTjZRIVUEaFhaGV199Fa+++qroUqhV9mlnk8qyzBmFRD62q5Q7Gimdqrp2SXkGJoZBq5Fwst6OcmuT6HKIAk5hGffYVToGKXnFpNeif+tsXfem2kTkGy6XjMJj3BpQ6Rik5DX3HzhPgiHyrSMnG1Bnc8Co03huWEl5GKTktSHJ3CqQqCe4J/FlJYZBp+XbtVLxX4a85h67KWSQEvmU++Z0MCcaKRqDlLzmPvmltKYR1fV2wdUQBQ53kGZzfFTRGKTktXCTHn1iWhaKs3uXyDdkWcbuUvceu2yRKhmDlHyCGzMQ+dZxqw1V9XZoNRKyEsNEl0MdYJCST7jvmHexRUrkE+6NGPrF9YJJrxVcDXWEQUo+Max3S5DuOFojthCiAOH+WxrWO1JoHXRuDFLyiWEpkQCAI1UNnHBE5AMFR1tapMNTI8UWQufEICWfiDDrkRHbCwCwna1SIq/IsoztJTUAgBFskSoeg5R8xn3nvL2EE46IvHGkqgGWxmYYdBoM5EQjxWOQks8Mbx0nZYuUyDvuv6EhyeEw6Pg2rXT8FyKfOdUirYEsy2KLIVKxgtZu3eHs1lUFBin5zKCkcOi1Eqrq7Tha3Si6HCLV8oyPcqKRKjBIyWdMei0GJbVszMDuXaLuaXa6POuxOWNXHRik5FPurij3HTURdc2+8lrYHS6Em3To27r1Jikbg5R8ijN3ibzjGR9NjYQkSWKLoU5hkJJPjUhtmbm7s9QCh9MluBoi9eH4qPowSMmnMmJDEWrUobHZiV8q6kSXQ6Q67vkFnLGrHgxS8imNRvLsu8txUqKuqbM5PDegw1J5dJpaMEjJ5zzjpJy5S9QlO49aIMtASmQI4sNMosuhTmKQks+5u6QKOOGIqEs83bpsjaoKg5R8zj1JYv/xWjTYHWKLIVKR7dzRSJUYpORziREmJIQb4XTJ2M2Dvok6bftpS19IPRik1CO4MQNR11RYm1BmaYJGAoamsGtXTRik1CPcd9QFDFKiTtneepB3ZnwYehl1gquhrmCQUo8YwZm7RF1yqluXrVG1YZBSjxjaupa05GQjqupsgqshUr5TM3YjhdZBXccgpR4RbtKjX1wvAMCOo1wGQ9QRl0vmjF0VY5BSj+E4KVHnHK6qh7XJAaNOg4GJYaLLoS5ikFKP4TgpUee4/0ayUyKg1/JtWW34L0Y95vQlMLIsiy2GSMHcxw6yW1edGKTUY7KSwmDQalDd0IySk42iyyFSrALO2FU1Bin1GKNOi0HJ4QCAAnbvEp2R3eFCYesOYDyDVJ0YpNSjRvBINaIO7S23wu50IdKsR1q0WXQ51A0MUupRniPVGKREZ3T6shdJksQWQ93CIKUe5Q7SXWUWNDtdYoshUiD3cYPciEG9GKTUo9JjeiHMpENTswv7j9eKLodIcdxLX0ZwopFqMUipR2k00mnLYLjDEdHprE3NKDpRBwAYxqUvqsUgpR7nntLPcVKitnYdtUCWgd5RIYgNNYouh7qJQUo9ztMi5RIYojYKuFF9QGCQUo9zr43bf7wW9TaH2GKIFMTdSzOC3bqqxiClHhcfbkJShAkuGdhVynFSIrftnLEbEBik5Bfs3iVqq9zShHJrEzQSkJ0SLroc8gKDlPzi1MYMbJESAaduKgckhMFs0IkthrzCICW/cM/c5dmkRC0846Ps1lU9Bin5xdCUCEgSUFrTiBO1NtHlEAm3nTN2AwaDlPwizKRH/7hQAMAOjpNSkHO5ZOzgGaQBg0FKfsMN7IlaHKysR63NAZNegwEJoaLLIS8xSMlv3EFacJQTjii4uW8mh6ZEQKfl27Da8V+Q/Gb4aWeTyrIsuBoicdzjo9xfNzAwSMlvshLDYdBqYGlsxpGqBtHlEAnjOYOUE40CAoOU/Mag02BwcsvC820l1YKrIRKjqdmJwmNWANwaMFAwSMmvcvpEAQC2HGGQUnDaWWpBs1NGbKgRqdEhosshH2CQkl+N7tsSpJsPM0gpOG06fBJAy9+CJEmCqyFfYJCSX+X0iQYA7DteC0tjs+BqiPzPfROZ2zdacCXkKwxS8qu4MCP6xpghy8DWYrZKKbi4XLJnWCO3dZiD1E91QVpaWopbb70VMTExMJvNGDFiBLZs2SK6LOoC95345tYuLqJgceBEHSyNzQjRaz0T70j9VBWk1dXVGD9+PPR6Pb766isUFhbi5ZdfRmRkpOjSqAvc46SbOE5KQcY9PjoyLRJ6bsQQMFR1ds8LL7yA1NRULFmyxHOtb9++4gqibnGPk24vqYHd4YJBxzcUCg5bDrNbNxCp6h3s888/R25uLq6//nrEx8dj5MiRePvtt8/6fJvNBqvV2uZB4vWL64Uosx42hwu7yrhdIAWPTUdaWqScaBRYVBWkBw8exKJFi5CZmYlvvvkGDzzwAGbPno133333jM/Py8tDRESE55GamurniulMJEniOCkFnePWJpScbIRGaunapcChqiB1uVwYNWoUFixYgJEjR+L+++/Hb3/7WyxatOiMz583bx4sFovnUVJS4ueK6WzcXVtcT0rBwv27npUYjjCTXnA15EuqCtKkpCQMHjy4zbVBgwahuLj4jM83Go0IDw9v8yBl8LRIj1RzA3sKCqdvxECBRVVBOn78eOzbt6/Ntf3796NPnz6CKqLuyk4Jh1Gnwcl6Ow5W1osuh6jHbeb4aMBSVZA+9NBD2LBhAxYsWIADBw5gxYoVWLx4MWbNmiW6NOoio07rOfliC7t3KcDV2RwoLGuZ7JjLFmnAUVWQjh49Gp988gnee+89ZGdn47nnnsOrr76KmTNnii6NusE9TrqJE44owBUU18AlAymRIUiK4Eb1gUZV60gB4KqrrsJVV10lugzygdF9owEUYTNPgqEAx/HRwKaqFikFllFpUZAk4FBlPSrrbKLLIeoxnv11OT4akBikJEyEWY8B8WEAuAyGApfD6fIc0MDx0cDEICWhcj3nk3KclALTnmO1aLA7EWbSeW4cKbAwSEmo0aetJyUKRJ5lL32ioNHwIO9AxCAloXJaZ+7uKrWg0e4UXA2R7/Eg78DHICWhekeFIDHcBIdLRkFJjehyiHxKlmXPjF2e+BK4GKQkVMsG9i1vMFuOcJyUAsvR6kZU1Nqg10qeDUgo8DBISbhTGzNwnJQCi7s1mp0SAZNeK7ga6ikMUhLOPXa0tbgaThc3sKfA4Z5EN5rjowGNQUrCZSWGIdSoQ22TA/uP14ouh8hnNnN8NCgwSEk4nVbjOeiY60kpUNQ02LH/eB2AU7PTKTAxSEkRcvtwPSkFFvduRhlxvRATahRcDfUkBikpwmjPDkcMUgoM7slzo/twfDTQMUhJEUakRUKrkVBa04iymkbR5RB5zT1MkcP9dQMeg5QUwWzQYUhyOAB275L62RxObD9qAcAZu8GAQUqK4Rkn5YQjUrldpRbYHS7EhhrQN8YsuhzqYQxSUgz3DkfcmIHUzv07nNMnCpLEjeoDHYOUFMO91m5fuRXWpmbB1RB1n3vSHLt1gwODlBQjPtyEPjFmuGRgW3GN6HKIusXlkj37RvPEl+DAICVF4Tgpqd3ByjpUNzTDpNd4JtBRYGOQkqLkcj0pqZz7d3dEaiT0Wr7FBgP+K5OiuDdm2FZSjWanS3A1RF23ieOjQYdBSorSLy4UUWY9mppd2F1mFV0OUZdt5vho0GGQkqJIkuTZ4JvjpKQ2FbVNOFLVAEmC5yAGCnwMUlIc9508x0lJbba0/s5mJYYj3KQXXA35C4OUFMezgf2Rk5BlHvRN6nFqfJT76wYTBikpTnZKBIw6DSrr7Cg6USe6HKJO23CwCgDHR4MNg5QUx6jTemY8riuqElwNUedU19tReKxlgtz5GTGCqyF/YpCSIp3fr+WN6KcDlYIrIeqc9a2t0YEJYYgL40HewYRBSoo0vn8sAGB9URWcLo6TkvK5b/rG9WdrNNgwSEmRspPDEWbSwdrkwO4yi+hyiM7JPQwxvl+s4ErI3xikpEg6rQZj01vu7DlOSkpXVtOIQ5X10EjAmAxONAo2DFJSrPH9OU5K6uC+2RvWO5LrR4MQg5QUyz1OuunwSdgcTsHVEJ3dutabvfEcHw1KDFJSrMz4UMSGGtHU7EIBzyclhZJl2dMiHcfx0aDEICXFkiQJ49zLYDhOSgp1sLIe5dYmGHQazz7RFFwYpKRo7q6ydRwnJYVy/27m9omCSa8VXA2JwCAlRXN3lRWU1KDe5hBcDVF7nmUv/dmtG6wYpKRoqdFmpEaHwOGSsZHHqpHCuFyyZ0cj925cFHwYpKR47gXu7N4lpSk8ZkVNQzPCjDoMS4kQXQ4J4nWQNjY2orS0tN313bt3e/utiQAA41q7zLgxAynNuqKWm7uxGdHQadkuCVZe/ct/9NFHGDBgAKZMmYJhw4bh559/9nzutttu87o4IuDUSRqFx6yorrcLrobolJ8OuLt1OT4azLwK0r/+9a/YunUrtm/fjn/+85+4++67sWLFCgDggczkM3FhRgxMCIMsnzphg0g0u8OFjYdaxu25EUNw03nzxc3NzYiLiwMA5ObmYs2aNbjmmmtw4MABSJLkkwKJgJYTNfYdr8W6okpMGZokuhwibD9ag8ZmJ2J6GTAwIUx0OSSQVy3S+Ph47Nixw/NxTEwM8vPzsWfPnjbXibw1zjPhiC1SUgb3HtDn94thwyHIeRWk//d//4eEhIQ21wwGA9577z2sXr3aq8KITjc2IxoaqWUXmWOWRtHlEHlu6rh+lDodpLW1tfjTn/6ErKwsxMbGol+/frjvvvvwj3/8A3v37m33/PHjx/u0UApu4SY9hvWOBHBqggeRKA12B7aVVAPg+aPUhSC9/fbb8dFHH+GOO+7A888/jzlz5mDVqlVYsWIFhgwZgt/85jcoKyvryVopyLn33XUvOSASZdPhajQ7ZaREhiA1OkR0OSRYp4P022+/xaeffop58+bh3nvvxezZs6HX6/HFF1/g0KFDSExMxOjRo3Ho0KGerJeCmLsLbd2BKs4KJ6FOPzaN46PU6SBNSEhAfX39GT+XlpaGv//975g1axbmzJnjs+KITpfTJwoGnQbl1iYcrDzz7yKRP/xU5A5SdutSF4J0zpw5uPvuu7F9+/azPmfmzJlYtWqVTwoj+jWTXouctJZjqrjLEYlS02DH7jIrgFObhVBw61KQXnvttcjJycEVV1yBt956Cy6Xq023xnvvvYfYWN6hUc/hsWok2oaDVZDlloPn48NNosshBejS8pcFCxZg/fr1iIiIwB//+Ec0NjYiOzsb6enpiImJwXPPPYe//e1vPVUrkWff3fUHq+BycZyU/O8nLnuhX+nyzkajR4/GBx98ALvdjq1bt2L//v2wWq2IjY3FxRdfjPj4+J6okwgAMCwlAqFGHWoamlF4zIpsnrhBfuaeNT6Ox6ZRq25vEWgwGHDeeefhvPPO82U9RB3SaTUYmx6N7/ZWYF1RJYOU/Krc0oSiE/XQSMBYjo9SK577Q6rj7t7lxgzkb+7W6NCUCESE6AVXQ0rBICXVcU842nT4JOwOl+BqKJi4Z4uP4/gonYZBSqozID4MMb0MaLA7sf1ojehyKEjIsuyZLc7xUTodg5RUR6ORcH7rG9lPXAZDfnK4qgFlliYYtBrk9okWXQ4piKqDNC8vD5IkYe7cuaJLIT87fbtAIn9w37SN6hOJEINWcDWkJKoN0k2bNmHx4sUYNmyY6FJIAHfX2raSajTYHYKroWCw3j0+ytNe6FdUGaR1dXWYOXMm3n77bURFRYkuhwRIizYjJTIEzU4Zmw5Xiy6HApzLJXtm7LonuxG5qTJIZ82ahalTp+LSSy/t8Hk2mw1Wq7XNgwKDJEncLpD8Zk+5FdUNzehl0HrOxSVyU12Qvv/++9i6dSvy8vLO+dy8vDxERER4HqmpqX6okPzFPU66ev8JwZVQoPvxl5abtbEZMdBrVfe2ST1MVb8RJSUlmDNnDpYvXw6T6dybRc+bNw8Wi8XzKCkp8UOV5C8XZsZBIwF7y2tRVtMouhwKYKv2VAAAJg2ME1wJKZGqgnTLli2oqKhATk4OdDoddDodVq9ejddffx06nQ5Op7PN841GI8LDw9s8KHBE9TJgVOuxat/vqxBcDQWqmgY7thS3jMNPyuJe4tSeqoL0kksuwc6dO1FQUOB55ObmYubMmSgoKIBWyynpwcb9xuZuMRD52ur9J+B0yRiYEIbeUWbR5ZACdXvTehHCwsKQnZ3d5lqvXr0QExPT7joFh0sGxeNv3+zDT0WVaGp2wqTnzRT51qq9LTdpFw9ia5TOTFUtUqJfG5gQhuQIE5qaXZ51fkS+4nC6PJPZLma3Lp2FqlqkZ/LDDz+ILoEEkiQJFw+Kx/INxfhu73GOYZFPbSupQU1DMyLNeoxMjRRdDikUW6SkepdkJQAAvt97ArIsC66GAom7W/eiAXHQcdkLnQV/M0j1zu8XA5Neg9KaRuw7Xiu6HAognmUv7OmgDjBISfVMei3Gt+5/+h1n75KPHK1uwL7jtdBqJEwcwPWjdHYMUgoI7hbD93sZpOQb7t+lnLQoRJoNgqshJWOQUkBwz6jcWlyN6nq74GooEHzHZS/USQxSCgjJkSHISgyDS+beu+S9BrsD61qXU3HZC50Lg5QCxiWtLYfv2L1LXlp3oAp2hwu9o0KQGR8quhxSOAYpBQx3y2H1vgo4nC7B1ZCaebp1s+IhSZLgakjpGKQUMEakRiHKrIe1yYEtR3jYN3WPLMueiUbs1qXOYJBSwNBqJEwa2LqJPbt3qZsKj1lRbm1CiF6L8zJiRJdDKsAgpYDiOQ2GQUrd5G6Nju8fy0MQqFMYpBRQLhwQB61Gwi8VdSiuahBdDqmQe3z0Ei57oU5ikFJAiQjRI7dPy2Hfq/YeF1wNqU1VnQ0FJTUA4BkmIDoXBikFHHdLYtU+rielrvlh3wnIMjAkORyJESbR5ZBKMEgp4LhnWm4oqkK9zSG4GlKTVZytS93AIKWA0y8uFGnRZtidLvx0oFJ0OaQSzU4X1vAQb+oGBikFHEmSPG+EnL1LnbXp8EnU2hyI6WXA8N6RosshFWGQUkA6PUh52Dd1hvvs0YsGxkOj4W5G1HkMUgpIYzOiYTZoUVFrw+4yq+hySAVW7eOyF+oeBikFJKNOiwn9edg3dc7hynocPFEPnUbChMxY0eWQyjBIKWCdWgbDIKWOucfSx6RHI9ykF1wNqQ2DlAKWe0H99pIanKi1Ca6GlIzLXsgbDFIKWPHhJgxNiQAAfM9WKZ1Fnc2Bnw/xEG/qPgYpBTT3JvbfcxkMncXaX06g2Smjb4wZGXE8xJu6jkFKAe2S1iD98ZdK2B087Jvac09GuzgrQXAlpFYMUgpoQ1MiEBtqRJ3NgY2HToouhxTG5ZLxfeuezFz2Qt3FIKWAptFInlbpV7uOCa6GlGbzkWpU1tkQZtRhdN9o0eWQSjFIKeBNHZYEAPhqVzkcTnbv0in/2VEGAJg8JBEGHd8OqXv4m0MBb1y/GET3MuBkvR3riqpEl0MK4XC68OXOll6Kq4YnCa6G1IxBSgFPp9XgiuxEAKdaIEQ/HzqJyjo7Is16zy5YRN3BIKWgcFVr9+7Xu8o5e5cAnLqpumJIIvRavhVS9/G3h4LC2PQYxIUZYW1yYO2BE6LLIcGanS58tascADBteLLgakjtGKQUFLQaCVOHtrRK/7Ods3eD3U8HKlHT0IzYUAPGpnO2LnmHQUpBw929+23hcTQ1OwVXQyJ90XozdWV2EnTs1iUv8TeIgsaotCgkRZhQZ3Pgh33s3g1WNocT3xa2dOu6b66IvMEgpaChOb17l7N3g9aa/ZWobXIgIdzITRjIJxikFFTcE0u+21OBBrtDcDUkgvsmaurQZGg0kuBqKBAwSCmoDOsdgbRoMxqbnZ7Nyil4NNqdyC88DoCbMJDvMEgpqEiS5NkykN27wef7fRVosDuREhmCkamRosuhAMEgpaDjnmDy/b4TqG1qFlwN+ZP75umqYUmQJHbrkm8wSCnoDE4KR0ZsL9gdLvx3z3HR5ZCf1NscWNV6wPtVw7gJA/kOg5SCjiRJuKp10hE3Zwge/91zHE3NLvSNMSM7JVx0ORRAGKQUlKa1du+u+eUELA3s3g0G7k0YrhqWzG5d8ikGKQWlzIQwDEwIQ7NTxje7y0WXQz3M0tiMNftbNuHgbF3yNQYpBS33pKMvOHs34OUXHofd6UL/+FAMTAgTXQ4FGAYpBS33OOm6oipU1dkEV0M9ibN1qScxSClopcf2QnZKOJwuGV+zezdgVdfbsfaXSgCcrUs9g0FKQc39xvrFdnbvBqqvd5fD4ZIxKCkc/eNDRZdDAYhBSkHNvYn9z4dOosLaJLga6gmnd+sS9QQGKQW11GgzRqRGQpaBL3dyTWmgOVFrw/qiKgDANHbrUg9hkFLQu8qz9y6DNNB8vesYXHLrYQUxZtHlUIBikFLQa1mgD2w+Uo2ymkbR5ZAPfdF6c8TWKPUkBikFvcQIE0b3aTngeSVbpQGj3NKETYdPAoDnxB+insAgJcKp3W54tFrgWLnzGGQZyOkTheTIENHlUABjkBIBuDI7CRoJ2H7UgqITdaLLIR/4dFspAM7WpZ7HICUCEBdmxEUD4wEA7/1cLLga8tbOoxbsLLXAoNXg6uEcH6WexSAlajVzbBoA4KOtR9HU7BRcDXljxcYjAIArshMRE2oUXA0FOgYpUauLBsYjOcKEmoZmfL2LWwaqVW1TMz4raBnrvqX15oioJzFIiVppNRJuHN3yxruC3buq9VlBGRrsTvSL64Wx6dGiy6EgoKogzcvLw+jRoxEWFob4+HhMnz4d+/btE10WBZAbR6dCq5Gw8fBJ/HK8VnQ51EWyLHtugm4ek8aTXsgvVBWkq1evxqxZs7Bhwwbk5+fD4XBg8uTJqK+vF10aBYjECBMuzmqZdLRiI1ularP9qAWFx6ww6DS4Lqe36HIoSOhEF9AVX3/9dZuPlyxZgvj4eGzZsgUXXnihoKoo0NwyNg35hcfx7y1H8egVWTDptaJLok5a8XPLJKOpQ5MQaTYIroaChapapL9msVgAANHRZx4HsdlssFqtbR5E53JhZhxSIkNgbXJwpyMVsTY144vtLf9enGRE/qTaIJVlGQ8//DAmTJiA7OzsMz4nLy8PERERnkdqaqqfqyQ10mok3Dym5XeF3bvq8em2UjQ2O5EZH4rcPlGiy6EgotogffDBB7Fjxw689957Z33OvHnzYLFYPI+SkhI/VkhqdkNuKnQaCVuOVGNfOScdKd3pk4xuGctJRuRfqgzSP/zhD/j888/x/fffo3fvs08oMBqNCA8Pb/Mg6oz4cBMuHZQA4NS4GynX1uIa7C2vhVGnwTUjOcmI/EtVQSrLMh588EF8/PHHWLVqFdLT00WXRAHMPc728bZSNNq505GSuVujVw1LRoRZL7gaCjaqCtJZs2Zh+fLlWLFiBcLCwlBeXo7y8nI0NvIMSfK9Cf1jkRZtRm2TA1/wVBjFsjQ0e07t4SQjEkFVQbpo0SJYLBZcdNFFSEpK8jw++OAD0aVRANJoJNw8hjsdKd3H247C5nAhKzEMo9IiRZdDQUhV60hlWRZdAgWZ63N745X8fSgoqUFhmRWDkznOriSnTzKayUlGJIiqWqRE/hYbasTkIYkATp0oQsqx+Ug1fqmoQ4hei9+MTBFdDgUpBinROcxs7d79dFsZ6m0OwdXQ6dyt0auHJyPcxElGJAaDlOgczu8Xg/TYXqizOfD5dk46UorqejtW7uRORiQeg5ToHCTptJ2OOOlIMf699SjsDheGJIdjWO8I0eVQEGOQEnXCdTmpMGg12Flqwc6jFtHlBD1Zlj3bN3InIxKNQUrUCdG9DLgim5OOlGLDwZM4eKIevQxa/GYEJxmRWAxSok5yj8N9VlCG2qZmwdUEN3dr9OoRKQg1qmoVHwUgBilRJ41Nj0a/uF5osDvxWQEnHYlSVWfD17taJhnN5CQjUgAGKVEntUw6annjXrbuMFwubhAiwoqfi9HslDGsdwSyUzjJiMRjkBJ1wQ2jUxFm0uGXijp8s7tcdDlBp87mwDs/HQIA3DOBh1aQMjBIibog3KTHXeNb3sBf++4Xtkr97P/WH0FNQzMyYnvhqmHJosshAsAgJeqyu8f3RahRh73ltfjvnuOiywkaDXYH3v7xIADgwYv7Q6vhkhdSBgYpURdFmg24Y1wfAMDrq37hYQp+8q8NxThZb0efGDOuHs7WKCkHg5SoG+6ZkAGzQYtdpVZ8v69CdDkBr9HuxN/XtLRGZ03qD52Wb12kHPxtJOqG6F4G3HZ+S6v0te8OsFXaw97bWIzKOht6R4VgBk95IYVhkBJ1028vyIBJr8H2khqs+aVSdDkBq6nZibdWFwFoaY3q2RolheFvJFE3xYYacevY1lbpf/ezVdpDPtxcgopaG5IjTLh2VG/R5RC1wyAl8sJ9F2bAqNNga3EN1hVViS4n4NgcTiz6oaU1+rtJ/WHQ8S2LlIe/lUReiA83eXY7eu27XwRXE3g+2nIUxyxNSAw34YZctkZJmRikRF56YGI/GLQabDx0EhsOslXqK81OF978vqU1+sDEDBh1WsEVEZ0Zg5TIS4kRJtwwuqW19MYqtkp95ZOtpSitaURsqBE3jeHm9KRcDFIiH/jdRf2h10r46UAVNh8+Kboc1XM4XVj4/QEALa1Rk56tUVIuBimRD6REhuC6nJZW6eurDgiuRv0+KyhD8ckGxPQyeM6BJVIqBimRj/z+opb9X9fsP4FtxdWiy1Etp0v2tEZ/e2EGzAYe3E3KxiAl8pHUaDOuad115w22SrvtPzvKcKiyHlFmPW47r4/ocojOiUFK5EOzJvWHRgJW7a3AzqMW0eWojtMle25C7r0gA72MbI2S8jFIiXyob2wvTB/R0ip9nTN4u+yrXcdwoKIO4SYdbj+frVFSBwYpkY/Nurg/JAnILzyOXaVslXaW0yXjje9aWqP3TMhAmEkvuCKizmGQEvlYv7hQTBvWcl7m05/vhsvFPXg7418/H8G+47UIM+lw5/i+ossh6jQGKVEPeOzKLPQyaLH5SDXe21QsuhzFO2ZpxItf7wMA/M/lAxERwtYoqQeDlKgHJEeG4E+XDwQAPP/lXhy3NgmuSNme+mw36mwOjEqLxMyxHBsldWGQEvWQ28/vi+G9I1Brc+CZL3aLLkexvt5Vjm8Lj0OnkZB3zTBoNJLokoi6hHPLz8DpdKK5uVl0GYqj1+uh1XKrts7StgbDtIVr8eXOcuQXHsdlgxNEl6Uo1qZmPPX5LgAtm/8PTAwTXBFR1zFITyPLMsrLy1FTUyO6FMWKjIxEYmIiJImths4YnByO316QgbdWF+HJz3bh/H4xCOXaSI+/fb0Px602pMf2woMX9xddDlG38C/6NO4QjY+Ph9lsZlicRpZlNDQ0oKKiAgCQlJQkuCL1mHNJJr7ceQzFJxvw0jf78PTVQ0SXpAhbjpzE8p+PAADmz8jmxvSkWgzSVk6n0xOiMTExostRpJCQEABARUUF4uPj2c3bSSEGLebPyMZt72zEsvWHMX1kCkakRoouSyi7w4V5H++ELAPX5/TGuH6xoksi6jZONmrlHhM1m82CK1E29+vDMeSuuSAzDteMTIEsA4/9eweanS7RJQm1eE0R9h+vQ0wvAx6fMkh0OUReYZD+CrtzO8bXp/v+PHUQosx67C2vxTtrD4kuR5hDlfWeo+aenDYYUb0Mgisi8g6DNEDceeedmD59uufjqqoqxMfH4/Dhw55rpaWlmDJlCsxmM/r164fly5e3+R7XXXcdXnnlFT9VHHxiQo14YupgAMCr/92PI1X1givyP1mW8fjHO2F3uHDhgDhcPTxZdElEXmOQBojXXnsNS5cu9Xycl5eHadOmoW/fvgAAl8uFq6++GmazGdu3b8ezzz6Le++9F99//73na5588knMnz8fVqvVz9UHj2tGpWB8/xg0NbvwxKe7IMvBtX3gR1uOYv3BKpj0Gsyfns0eDgoIDNIAERERgcjISABAY2Mj3nnnHdx7772ez3/55ZfYvXs33nnnHWRmZmLmzJm46667sGDBAs9zhg0bhr59++Jf//qXv8sPGpIkYf70oTDqNPjxl0p8WlAquiS/qayzYf6XewAAD182AKnRnI9AgYFBGiBO79r96quvoNPpcP7553s+n5+fj3HjxiEiIsJzbfLkyVi9enWbiUNXX3013nvvPb/VHYz6xvbCnEszAQDP/WcPTtbbBVfkH3/9TyFqGpoxOCkcd49PF10Okc8wSAPQmjVrkJub2+bawYMHkZmZ2eZaZmYmmpubUVJS4rk2ZswYbNy4ETabzS+1BqvfXpCBrMQwnKy3Y/7KPaLL6XGr95/ApwVl0EjA89cOhU7Ltx4KHFxH2gFZltHY7BTys0P02m6PHx0+fBjJyW0ncTQ0NGDJkiVtum3d43MNDQ2eaykpKbDZbCgvL0efPtw8vKfotRrkXTMU1yxah39vPYrRfaNw05g00WX1iJKTDfjjh9sBAHeOS8ew3pFiCyLyMQZpBxqbnRj85DdCfnbhs5fDbOjeP09jYyNMJlOba2azGTfddBOefPJJz7WioiJcccUVbdbOujddOD1cqWeMTIvC7Isz8dp3v+DPn+5CQrgJk7LiRZflU9X1dtzxz42orLNhUFI4/jh5gOiSiHyO/SsBKDY2FtXV1W2uZWRkwOFwoH///p6H2WyGXq9Hamqq53knT54EAMTFxfm15mA199JMXDuqN5wuGb//11bsOFojuiSfaWp24p5lm3Cwsh4pkSFYetdo9OI+wxSA+FvdgRC9FoXPXi7sZ3fXyJEj260Rveyyy/Dggw/C6XR6tvbLz8/HxIkTodefOkR5165d6N27N2JjuWWbP0iShOevHYqK2ib8+Esl7l66CR//bjzSYtQ9o9XpkjH7vW3YWlyDcJMOS+8ajYRw07m/kEiF2CLtgCRJMBt0Qh7erK+7/PLLsXv37jat0ilTpiA6Ohq/+93vUFRUhM8++wyvv/46Hn/88TZf++OPP2Ly5Mnd/tnUdXqtBotuzcGQ5HBU1tlxx5KNqKpT72QvWZbxzBe78W3hcRh0GvzjjtHITODxaBS4GKQBaOjQocjNzcWHH37ouabRaPD555/j6NGjyM7OxkMPPYSFCxdi0qRJnuc0NTXhk08+wW9/+1sRZQe1UKMOS+4cjZTIEByqrMe9725Go13MRDdv/X3NQby7/ggkCXj1xhEYkx4tuiSiHsUgDRA2mw2hoaGej//yl7/gtddeg8t1anP03r1748svv0RjYyMOHjyIW2+9tc33eOeddzB27Ficd955fqubTokPN2HZ3WMQEaLHtuIazH5/G5wude189FlBKZ7/ai8A4C9TB2PKUB63R4GPQapyDocDhYWFWL9+PYYMOXXO5ZQpU3D//fejtLTzO+fo9Xq88cYbPVEmdVL/+FC8c0cuDDoN8guP46nP1bON4E8HKvGn/9eyzOXeCem4ewI3XaDgwCBVuV27diE3NxdDhgzBAw880OZzc+bMaTMj91zuu+8+DBw40NclUhfl9o3G6zeNgCQByzcU480fikSXdE57jlnxwP9tQbNTxlXDkng0GgUVBqnKjRgxAg0NDVi5ciWioqJEl0M+ckV2Ep66quWkmL99sw8fbz0quKKzK6tpxJ1LNqLW5sDY9Gi8fMNwaDTcjJ6CB4OUSKHuHJ+O+y/MAAD8z0c78MO+CsEVtXey3o47l2zEcasNAxJCsfj2XBh13V+6RaRGDFIiBXv0iixMG54Mh0vG3Us3Ie/LPWgStG3lr/238Dguf3UN9h+vQ0K4EUvvapkoRRRsGKRECqbRSHjp+mG4Lqc3XHLL0pJpb6zFzqMWYTVZm5rxp/+3Hfe+uxknam3oHx+K5feMRXJkiLCaiERikBIpnFGnxUvXD8fbt+ciNtSIXyrqMP3Nn/BK/n7YHa5zfwMfWrP/BC7//9bgoy1HIUnA/Rdm4D9/mMANFyiocYtAIpW4bHACcvpE4cnPduE/O47h9e9+wX8Lj+OVG4cjKzG8R392vc2BBV/uwb9+LgYA9I0x46XrhyO3LzdbIGKLlEhFonsZsPCWUVh4y0hEmfUoPGbFtDfW4n+/PwCHs2dapxsOVuGK19Z4QvSO8/vgyzkXMESJWqkySN98802kp6fDZDIhJycHP/74o+iSiPzqqmHJ+OahC3HpoAQ0O2X87Zt9uPat9ThQUeezn9HU7MSzXxTi5rc3oORkI1IiQ7Di3rF45jfZ3T7ijygQqe6v4YMPPsDcuXPx5ptvYvz48fj73/+OK6+8EoWFhUhLC8yDkYnOJD7MhLdvz8HHW0vx9Be7sb2kBlNe/xHj+8VgVFoUcvpEYXhqZKePLnO6ZPxSUYstR6qx5Ug11h2oQrm1CQBw0+hU/HnqIISZOCuX6NckWS37j7UaO3YsRo0ahUWLFnmuDRo0CNOnT0deXl6HX2u1WhEREQGLxYLw8LZjSk1NTTh06JCnpRsI1q5dix9//BGzZ8/GjBkz8O233wIA7HY7Zs2ahZ9++gkRERH46quvIMsybrnlFnz11Vcdfs9AfJ0UT5aB5o4PWi+3NuKJT3fjpwOVba5rJGBgYjhGpkZiZFokRqRGISXSBEmSYG1qxo6jFmwrrsH2kmrsOGpBrc3R5uvjQo14bkY2JmZ24nxavRnw4tQiIn/qKA+6SlUtUrvdji1btuCxxx5rc33y5MlYt25du+fbbDbYbKeOo7JarT1eoyjLly/HP//5T0ycOBFPPvkkJEnChAkTMGHCBLz++uu47rrrPM996qmnMHHiRLz99tt47LHH8OGHH+K+++5Damoq1q9fj/PPP1/g/wm109wALEju8CmJAP4BAGe6t6lufexoezkcwITWBwBAOsPXOwD8v07W+XgZYOjVyScTBQ5VjZFWVlbC6XQiISGhzfWEhASUl5e3e35eXh4iIiI8j67sO6s2kydPxocffoiNGzdixYoVAIAZM2agoKAAK1aswNVXXw0AsFgsWLt2refkl/79+6OoqGUv16uvvhrvv/++mP8BIiKVUlWL1O3Xh17LsnzGg7DnzZuHhx9+2POx1WoN2DCNj48HAPzud7/DypUrMXPmTOzZsweDBg3CsWPHkJiYCADIz8/HgQMHMGLECABAeXk5HnroIQDAqFGj8PTTT4sonzqiN7e09nygqdmJXaVWWJuakd07HPGhPuye15t9972IVERVQRobGwutVtuu9VlRUdGulQoARqMRRqPRX+UJU1dXhxtuuAF1dXUYMmQIzGYz6uvrodPpUFVVhcjISM9zt2/fjhdffBG33XYbAOCyyy7zhGpcXByOHTsm4P+AOiRJPusyNRmA3AE9u+aUKNioqmvXYDAgJycH+fn5ba7n5+dj3LhxgqoS791338UFF1yANWvW4OTJkxg1ahR27dqF7OxsmEymNuPENTU1CAkJ8fz3zp07MXHiRAAtY8qcQERE1DWqClIAePjhh/GPf/wD//znP7Fnzx489NBDKC4ubncWZzA5duwYBgwYAIvFgiNHjmDq1KnYuXMnhg4diujoaDQ2NsLhaJmNmZGRgU2bNgEAnn76acydO9cTngcOHMDgwYOF/X8QEamR6oL0xhtvxKuvvopnn30WI0aMwJo1a/Dll1+iT58+oksT5rbbbsNLL72Eyy+/HM888wwiIyM9QQoAEydOxMaNGwEAM2fORH5+PjIzM+FyufDII494vs/q1atx5ZVXCvl/ICJSK9WtI/VGMK0jHTVqFFauXImkpCRs2LAB7777Lt58880Ov+aSSy7BRx991OEB4YH2OhFRcAradaR0bna7Heeddx6uuOIKJCUlAQDOO+887Nmzp8Ovq66uxqxZszoMUSIiao9B2pFO7CjTY7q5S4zBYMDWrVvbXb/rrrs6/LqoqChcc801Xf55RETBjkHakU7sKNNjuEsMEZEqMEgDwJk2o/CVIBpCJyLqFgZpR3y4o0y3fnYnMeyIiMRhkHbEhzvKKMWZTn45fecjIiLqGtWtI6XOW758OS6++GI888wznlar++SXwsJCTJw4ER9++KHgKomI1I1BGsB+fSJMRye/EBFR97BrN4D9+kQYo9F41pNfiIioexikAepMJ8J0dPILERF1D7t2A9SZToTp6OQXIiLqHgZpgDrTiTAdnfxCRETdwyANUGc6Eaajk1+IiKh7OEYaoAYMGID169e3uRYfH3/GfXiJiKj72CIlIiLyAoOUiIjICwxSIiIiLzBIiYiIvMAgJSIi8gKD9FdcLpfoEhSNrw8RUVtc/tLKYDBAo9GgrKwMcXFxMBgMPXpgttrIsgy73Y4TJ05Ao9HAYDCILomISBEYpK00Gg3S09Nx7NgxlJUJOsxbBcxmM9LS0qDRsDODiAhgkLZhMBiQlpYGh8MBp9MpuhzF0Wq10Ol0bKkTEZ2GQforkiRBr9dDr9eLLoWIiFSA/XNEREReYJASERF5gUFKRETkhaAaI5VlGQBgtVoFV0JERCK5c8CdC94IqiCtqqoCAKSmpgquhIiIlKCqqgoRERFefY+gCtLo6GgAQHFxsdcvXDCxWq1ITU1FSUkJwsPDRZejCnzNuoevW9fxNesei8WCtLQ0Ty54I6iC1L2JQEREBH/huiE8PJyvWxfxNesevm5dx9ese3yxuQwnGxEREXmBQUpEROSFoApSo9GIp556CkajUXQpqsLXrev4mnUPX7eu42vWPb583STZF3N/iYiIglRQtUiJiIh8jUFKRETkBQYpERGRFxikREREXgiqIH3zzTeRnp4Ok8mEnJwc/Pjjj6JLUqy8vDyMHj0aYWFhiI+Px/Tp07Fv3z7RZalOXl4eJEnC3LlzRZeiaKWlpbj11lsRExMDs9mMESNGYMuWLaLLUjSHw4EnnngC6enpCAkJQUZGBp599lm4XC7RpSnKmjVrMG3aNCQnJ0OSJHz66adtPi/LMp5++mkkJycjJCQEF110EXbv3t2lnxE0QfrBBx9g7ty5+POf/4xt27bhggsuwJVXXoni4mLRpSnS6tWrMWvWLGzYsAH5+flwOByYPHky6uvrRZemGps2bcLixYsxbNgw0aUoWnV1NcaPHw+9Xo+vvvoKhYWFePnllxEZGSm6NEV74YUX8NZbb2HhwoXYs2cPXnzxRfztb3/DG2+8Ibo0Ramvr8fw4cOxcOHCM37+xRdfxCuvvIKFCxdi06ZNSExMxGWXXYba2trO/xA5SIwZM0Z+4IEH2lzLysqSH3vsMUEVqUtFRYUMQF69erXoUlShtrZWzszMlPPz8+WJEyfKc+bMEV2SYj366KPyhAkTRJehOlOnTpXvvvvuNteuueYa+dZbbxVUkfIBkD/55BPPxy6XS05MTJSff/55z7WmpiY5IiJCfuuttzr9fYOiRWq327FlyxZMnjy5zfXJkydj3bp1gqpSF4vFAgA+2eA5GMyaNQtTp07FpZdeKroUxfv888+Rm5uL66+/HvHx8Rg5ciTefvtt0WUp3oQJE/Ddd99h//79AIDt27dj7dq1mDJliuDK1OPQoUMoLy9vkw1GoxETJ07sUjYExab1lZWVcDqdSEhIaHM9ISEB5eXlgqpSD1mW8fDDD2PChAnIzs4WXY7ivf/++9i6dSs2bdokuhRVOHjwIBYtWoSHH34Yjz/+ODZu3IjZs2fDaDTi9ttvF12eYj366KOwWCzIysqCVquF0+nE/PnzcfPNN4suTTXc7/9nyoYjR450+vsERZC6SZLU5mNZlttdo/YefPBB7NixA2vXrhVdiuKVlJRgzpw5+Pbbb2EymUSXowoulwu5ublYsGABAGDkyJHYvXs3Fi1axCDtwAcffIDly5djxYoVGDJkCAoKCjB37lwkJyfjjjvuEF2eqnibDUERpLGxsdBqte1anxUVFe3uRKitP/zhD/j888+xZs0a9O7dW3Q5irdlyxZUVFQgJyfHc83pdGLNmjVYuHAhbDYbtFqtwAqVJykpCYMHD25zbdCgQfj3v/8tqCJ1eOSRR/DYY4/hpptuAgAMHToUR44cQV5eHoO0kxITEwG0tEyTkpI817uaDUExRmowGJCTk4P8/Pw21/Pz8zFu3DhBVSmbLMt48MEH8fHHH2PVqlVIT08XXZIqXHLJJdi5cycKCgo8j9zcXMycORMFBQUM0TMYP358u6VV+/fvR58+fQRVpA4NDQ3tztLUarVc/tIF6enpSExMbJMNdrsdq1ev7lI2BEWLFAAefvhh3HbbbcjNzcX555+PxYsXo7i4GA888IDo0hRp1qxZWLFiBT777DOEhYV5WvMREREICQkRXJ1yhYWFtRtH7tWrF2JiYji+fBYPPfQQxo0bhwULFuCGG27Axo0bsXjxYixevFh0aYo2bdo0zJ8/H2lpaRgyZAi2bduGV155BXfffbfo0hSlrq4OBw4c8Hx86NAhFBQUIDo6GmlpaZg7dy4WLFiAzMxMZGZmYsGCBTCbzbjllls6/0N8Na1YDf73f/9X7tOnj2wwGORRo0ZxKUcHAJzxsWTJEtGlqQ6Xv5zbF198IWdnZ8tGo1HOysqSFy9eLLokxbNarfKcOXPktLQ02WQyyRkZGfKf//xn2WaziS5NUb7//vszvpfdcccdsiy3LIF56qmn5MTERNloNMoXXnihvHPnzi79DB6jRkRE5IWgGCMlIiLqKQxSIiIiLzBIiYiIvMAgJSIi8gKDlIiIyAsMUiIiIi8wSImIiLzAICUiIvICg5SIiMgLDFKiIPDaa68hPT0dZrMZ06dP9xzUTkTeY5ASBbjHH38cCxcuxLJly7B27Vps27YNzzzzjOiyiAIG99olCmCbNm3Ceeedh02bNmHUqFEAgAULFmDp0qXYv3+/4OqIAgNbpEQB7KWXXsLFF1/sCVEAiIuLQ2VlpcCqiAILg5QoQNlsNnzxxReYMWNGm+uNjY2IiIgQVBVR4GGQEgWorVu3orGxEX/84x8RGhrqeTzyyCMYOHAgAGDGjBmIiorCddddJ7haIvXSiS6AiHrG/v37YTKZsHPnzjbXr776aowfPx4AMHv2bNx9991YtmyZiBKJAgJbpEQBymq1Ij4+Hv379/c8DAYD9u7di2uvvRYAMGnSJISFhQmulEjdGKREASo2NhZWqxWnT8yfP38+pkyZgsGDBwusjCiwsGuXKEBdfPHFaGpqwvPPP4+bb74ZK1aswOeff46NGzeKLo0ooLBFShSgEhISsHTpUixatAiDBw/GunXrsHbtWqSmpooujSigsEVKFMBuvPFG3HjjjaLLIApo3NmIKIhdfvnl2Lp1K+rr6xEdHY1PPvkEo0ePFl0WkaowSImIiLzAMVIiIiIvMEiJiIi8wCAlIiLyAoOUiIjICwxSIiIiLzBIiYiIvMAgJSIi8gKDlIiIyAsMUiIiIi8wSImIiLzAICUiIvICg5SIiMgL/z/svv/PQDbODAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 500x500 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "x = np.arange(-20, 20, 0.25)\n",
    "y = (x-5)**2\n",
    "\n",
    "plt.figure(figsize=(5, 5))\n",
    "\n",
    "plt.xlabel(r'$\\theta_1$')\n",
    "plt.ylabel(r'$\\theta_2$')\n",
    "plt.title(r'j($\\theta$)')\n",
    "\n",
    "plt.xlim(0, 10)\n",
    "plt.ylim(-1, 10)\n",
    "\n",
    "plt.plot(x, y, label='j(θ)')\n",
    "\n",
    "p1 = [4.5, 5.5]\n",
    "p2 = [0, 0]\n",
    "\n",
    "plt.plot(p1, p2, label=r'$\\frac{\\partial j(θ)}{\\partial θ}$')\n",
    "\n",
    "plt.legend()\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a0662597",
   "metadata": {
    "papermill": {
     "duration": 0.006781,
     "end_time": "2023-03-24T23:10:43.684714",
     "exception": false,
     "start_time": "2023-03-24T23:10:43.677933",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "Suppose we have a squared error cost function j(θ), as the plot above shows. As can be seen, the derivate of j(θ) at the global minimum is zero. So if we find the θ values that make the derivative of the cost function j(θ) zero, we can use them for the optimal solution. We know that j(θ) in vectorized form can be written as follows:\n",
    "\n",
    "$ J(\\theta) = \\frac{1}{2m}( X\\theta - \\vec y)^T(X\\theta - \\vec y) $\n",
    "\n",
    "Therefore,\n",
    "\n",
    "$\\frac{\\partial J(\\theta)}{\\partial \\theta} = \\frac{\\partial}{\\partial \\theta} \\frac{1}{2m}( X\\theta - \\vec y)^T(X\\theta - \\vec y) := 0 $\n",
    "\n",
    "If we solve the equation above for θ, we get the following:\n",
    "\n",
    "$ \\boldsymbol{\\theta} := (\\boldsymbol{X}^T \\boldsymbol{X})^{-1} \\boldsymbol{X}^T \\boldsymbol{\\vec y}  $\n",
    "\n",
    "We must calculate the inverse of matrix $\\boldsymbol{X}^T \\boldsymbol{X}$, which has dimensions (n+1 X n+1), to find the θ values. Unfortunately, not every matrix has an inverse. So we must be careful while taking the inverse. Too many (m>=n, where m is the number of examples and n is the number of features) or redundant features may cause $\\boldsymbol{X}^T \\boldsymbol{X}$ to be non-invertible. If we run across a non-invertible matrix case, we may attempt to decrease the features or get more data to solve the issue. \n",
    "\n",
    "Also, the [NumPy library](https://numpy.org/doc/stable/index.html) has a function called [pinv()](https://numpy.org/doc/stable/reference/generated/numpy.linalg.pinv.html) that will compute the pseudo-inverse of $\\boldsymbol{X}^T \\boldsymbol{X}$ so that even if $\\boldsymbol{X}^T \\boldsymbol{X}$ is non-invertible, we may have a solution. \n",
    "\n",
    "We get the following table if we compare the 'normal equation' approach with the gradient descent approach [[1](https://www.deeplearning.ai/program/machine-learning-specialization/)].\n",
    "\n",
    "|Gradient Descent                           |Normal Equation                                                                 |\n",
    "|:------------------------------------------|:-------------------------------------------------------------------------------|\n",
    "|Need to choose alpha                       |No need to choose alpha                                                         |\n",
    "|Needs many iterations                      |No need to iterate                                                              |\n",
    "|$O(n^2)$                                   |$O(n^3)$, need to calculate $(\\boldsymbol{X}^T \\boldsymbol{X})^{-1}$            |\n",
    "|Works well when n is large                 |Slow if n is very large                                                         |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "b597b3f1",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-03-24T23:10:43.700652Z",
     "iopub.status.busy": "2023-03-24T23:10:43.699853Z",
     "iopub.status.idle": "2023-03-24T23:10:43.707689Z",
     "shell.execute_reply": "2023-03-24T23:10:43.706357Z"
    },
    "papermill": {
     "duration": 0.018543,
     "end_time": "2023-03-24T23:10:43.710163",
     "exception": false,
     "start_time": "2023-03-24T23:10:43.691620",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# The normal equation\n",
    "\n",
    "def calculate_theta(X,y):\n",
    "    \"\"\"\n",
    "     Calculates the theta vector using the normal equation.\n",
    "    \n",
    "    :param X: inputs (feature values) - data frame of floats\n",
    "    :param y: outputs (actual target values) - Numpy array of floats\n",
    "    \n",
    "    :return: new theta - Numpy array of floats\n",
    "    \n",
    "    \"\"\"\n",
    "    # Calculate transpose of X\n",
    "    X_transpose = X.transpose()\n",
    "    \n",
    "    # Calculate the dot product between X_transpose and X\n",
    "    temp_0 = np.dot(X_transpose, X)\n",
    "        \n",
    "    # Calculate the inverse of temp_0\n",
    "    try:\n",
    "        temp_1 = linalg.inv(temp_0)\n",
    "     \n",
    "    except:\n",
    "        print(\"\\033[93mWarning: Non-invertible Matrix! pinv() will be used\\033[0m\")\n",
    "        temp_1 = linalg.pinv(temp_0)\n",
    "\n",
    "    # Calculate the dot product between temp_1 and X_transpose\n",
    "    temp_2 = np.dot(temp_1, X_transpose)\n",
    "\n",
    "    # Calculate the dot product between temp_2 and y\n",
    "    theta = np.dot(temp_2, y) \n",
    "\n",
    "    return  theta.reshape(-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "86376350",
   "metadata": {
    "papermill": {
     "duration": 0.006486,
     "end_time": "2023-03-24T23:10:43.723538",
     "exception": false,
     "start_time": "2023-03-24T23:10:43.717052",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# The  Hypothesis   <a id='hypothesis'></a>   "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "786717f9",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-03-19T20:08:10.723871Z",
     "iopub.status.busy": "2023-03-19T20:08:10.723267Z",
     "iopub.status.idle": "2023-03-19T20:08:10.730032Z",
     "shell.execute_reply": "2023-03-19T20:08:10.728533Z",
     "shell.execute_reply.started": "2023-03-19T20:08:10.723828Z"
    },
    "papermill": {
     "duration": 0.006413,
     "end_time": "2023-03-24T23:10:43.737758",
     "exception": false,
     "start_time": "2023-03-24T23:10:43.731345",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "The vectorized form of the hypothesis for linear regression is:\n",
    "\n",
    "$ h_\\theta(x) = \\boldsymbol{X}\\boldsymbol{\\theta} $\n",
    "\n",
    "The vectorized hypothesis is needed in the cost function. You can refer to [Multivariate Linear Regression From Scratch](https://www.kaggle.com/code/erkanhatipoglu/multivariate-linear-regression-from-scratch) notebook for more detailed information."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "a5dede53",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-03-24T23:10:43.753181Z",
     "iopub.status.busy": "2023-03-24T23:10:43.752704Z",
     "iopub.status.idle": "2023-03-24T23:10:43.759051Z",
     "shell.execute_reply": "2023-03-24T23:10:43.757641Z"
    },
    "papermill": {
     "duration": 0.016973,
     "end_time": "2023-03-24T23:10:43.761454",
     "exception": false,
     "start_time": "2023-03-24T23:10:43.744481",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# The hypothesis\n",
    "def h(x, theta):\n",
    "    \"\"\"\n",
    "     Calculates the predicted values (or predicted targets) for a given set of input and theta vectors.\n",
    "    \n",
    "    :param x: inputs (feature values) - data frame of floats \n",
    "    :param theta: theta vector (weights) - Numpy array of floats\n",
    "    \n",
    "    :return: predicted targets - Numpy array of floats\n",
    "    \n",
    "    \"\"\"\n",
    "    # The hypothesis is a column vector of m x 1\n",
    "    return np.dot(x, theta)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9118722",
   "metadata": {
    "papermill": {
     "duration": 0.006504,
     "end_time": "2023-03-24T23:10:43.774907",
     "exception": false,
     "start_time": "2023-03-24T23:10:43.768403",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# The  Cost Function   <a id='cost'></a> "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a0fee272",
   "metadata": {
    "papermill": {
     "duration": 0.006411,
     "end_time": "2023-03-24T23:10:43.788052",
     "exception": false,
     "start_time": "2023-03-24T23:10:43.781641",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "The vectorized form of the cost function for linear regression is:\n",
    "\n",
    "$ J(\\theta) = \\frac{1}{2m}( X\\theta - \\vec y)^T(X\\theta - \\vec y) $\n",
    "\n",
    "The cost function will be used for validating the model. You can refer to [Multivariate Linear Regression From Scratch](https://www.kaggle.com/code/erkanhatipoglu/multivariate-linear-regression-from-scratch) notebook for more detailed information."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "55dc414e",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-03-24T23:10:43.803815Z",
     "iopub.status.busy": "2023-03-24T23:10:43.803338Z",
     "iopub.status.idle": "2023-03-24T23:10:43.810752Z",
     "shell.execute_reply": "2023-03-24T23:10:43.809323Z"
    },
    "papermill": {
     "duration": 0.018263,
     "end_time": "2023-03-24T23:10:43.813142",
     "exception": false,
     "start_time": "2023-03-24T23:10:43.794879",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# The cost function\n",
    "\n",
    "def J(X,y,theta):\n",
    "    \"\"\"\n",
    "     Calculates the total error using squared error function.\n",
    "    \n",
    "    :param X: inputs (feature values) - data frame of floats\n",
    "    :param y: outputs (actual target values) - Numpy array of floats\n",
    "    :param theta: theta vector (weights) - Numpy array of floats\n",
    "    \n",
    "    :return: total error - float\n",
    "    \n",
    "    \"\"\"\n",
    "    # Calculate number of examples\n",
    "    m = len(X)\n",
    "    \n",
    "    # Calculate the constant\n",
    "    c = 1/(2 * m)\n",
    "       \n",
    "    # Calculate the array of errors\n",
    "    temp_0 = h(X, theta) - y.reshape(-1)\n",
    "\n",
    "    # Calculate the transpose of array of errors\n",
    "    temp_1 = temp_0.transpose()\n",
    "\n",
    "    # Calculate the dot product \n",
    "    temp_2 = np.dot(temp_1, temp_0) \n",
    "\n",
    "    return  c * temp_2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8fd715bf",
   "metadata": {
    "papermill": {
     "duration": 0.006597,
     "end_time": "2023-03-24T23:10:43.826611",
     "exception": false,
     "start_time": "2023-03-24T23:10:43.820014",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# Loading Data   <a id='getdata'></a> "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0f711d67",
   "metadata": {
    "papermill": {
     "duration": 0.006412,
     "end_time": "2023-03-24T23:10:43.839949",
     "exception": false,
     "start_time": "2023-03-24T23:10:43.833537",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "First of all, we will load the CSV file in this part. Since there are two different versions of the dataset, we will load the one with more data. We will then create our training DataFrame and target vector. Finally, we will split our data into training and validation DataFrames so that we can validate the results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "4a2662ec",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-03-24T23:10:43.855470Z",
     "iopub.status.busy": "2023-03-24T23:10:43.855017Z",
     "iopub.status.idle": "2023-03-24T23:10:43.903665Z",
     "shell.execute_reply": "2023-03-24T23:10:43.902794Z"
    },
    "papermill": {
     "duration": 0.059254,
     "end_time": "2023-03-24T23:10:43.905942",
     "exception": false,
     "start_time": "2023-03-24T23:10:43.846688",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>GRE Score</th>\n",
       "      <th>TOEFL Score</th>\n",
       "      <th>University Rating</th>\n",
       "      <th>SOP</th>\n",
       "      <th>LOR</th>\n",
       "      <th>CGPA</th>\n",
       "      <th>Research</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>107</th>\n",
       "      <td>338</td>\n",
       "      <td>117</td>\n",
       "      <td>4</td>\n",
       "      <td>3.5</td>\n",
       "      <td>4.5</td>\n",
       "      <td>9.46</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>336</th>\n",
       "      <td>319</td>\n",
       "      <td>110</td>\n",
       "      <td>3</td>\n",
       "      <td>3.0</td>\n",
       "      <td>2.5</td>\n",
       "      <td>8.79</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>71</th>\n",
       "      <td>336</td>\n",
       "      <td>112</td>\n",
       "      <td>5</td>\n",
       "      <td>5.0</td>\n",
       "      <td>5.0</td>\n",
       "      <td>9.76</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>474</th>\n",
       "      <td>308</td>\n",
       "      <td>105</td>\n",
       "      <td>4</td>\n",
       "      <td>3.0</td>\n",
       "      <td>2.5</td>\n",
       "      <td>7.95</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>321</td>\n",
       "      <td>109</td>\n",
       "      <td>3</td>\n",
       "      <td>3.0</td>\n",
       "      <td>4.0</td>\n",
       "      <td>8.20</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "     GRE Score  TOEFL Score  University Rating  SOP  LOR   CGPA  Research\n",
       "107        338          117                  4  3.5   4.5  9.46         1\n",
       "336        319          110                  3  3.0   2.5  8.79         0\n",
       "71         336          112                  5  5.0   5.0  9.76         1\n",
       "474        308          105                  4  3.0   2.5  7.95         1\n",
       "6          321          109                  3  3.0   4.0  8.20         1"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Get the data. Note that there are two versions. We will use the one\n",
    "# with the most rows.\n",
    "\n",
    "train_data = pd.read_csv(\"/kaggle/input/graduate-admissions/Admission_Predict_Ver1.1.csv\")\n",
    "\n",
    "# Set X and y\n",
    "X = train_data.drop(['Chance of Admit ', 'Serial No.'], axis=1) # Chance of Admit is the target variable and Serial No. is the order. So we drop them.\n",
    "y = pd.DataFrame(data = train_data['Chance of Admit ']).to_numpy()\n",
    "\n",
    "# Instead of finding probabilities, we want to calculate the percentages.\n",
    "y = y * 100\n",
    "\n",
    "# Break off validation set from training data\n",
    "X_train, X_valid, y_train, y_valid = train_test_split(X, y, train_size=0.8, test_size=0.2, random_state = 0)\n",
    "\n",
    "X_train.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bb719767",
   "metadata": {
    "papermill": {
     "duration": 0.00665,
     "end_time": "2023-03-24T23:10:43.919824",
     "exception": false,
     "start_time": "2023-03-24T23:10:43.913174",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# Model Training   <a id='training'></a> "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1f45368d",
   "metadata": {
    "papermill": {
     "duration": 0.006698,
     "end_time": "2023-03-24T23:10:43.933436",
     "exception": false,
     "start_time": "2023-03-24T23:10:43.926738",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "We need to define an $X_0$ feature equal to one for all training examples for a vectorized solution. So our first task is to insert the $X_0$ column into the training and validation data. Then we will call the calculate_theta function for training data. There will be no iterations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "5158f447",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-03-24T23:10:43.949738Z",
     "iopub.status.busy": "2023-03-24T23:10:43.949311Z",
     "iopub.status.idle": "2023-03-24T23:10:43.972177Z",
     "shell.execute_reply": "2023-03-24T23:10:43.970557Z"
    },
    "papermill": {
     "duration": 0.036409,
     "end_time": "2023-03-24T23:10:43.977116",
     "exception": false,
     "start_time": "2023-03-24T23:10:43.940707",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Execution time: 11.789296999999976 milliseconds\n",
      "\n",
      "Calculated\u001b[1m θ\u001b[0m: [-1.34416734e+02  2.14141419e-01  2.77038677e-01  5.55692827e-01\n",
      "  5.10313673e-02  2.04133847e+00  1.15053979e+01  2.41256700e+00]\n",
      "\n",
      "The training cost is: 17.100414719720018\n"
     ]
    }
   ],
   "source": [
    "# Initialize\n",
    "\n",
    "# Calculate elapsed CPU time\n",
    "start = process_time()\n",
    "\n",
    "# Calculate the number of examles\n",
    "m_train = len(X_train)\n",
    "m_valid = len(X_valid)\n",
    "\n",
    "# Calculate the number of features\n",
    "# including X_0\n",
    "n = len(X_train.axes[1]) + 1\n",
    "\n",
    "# Create a list of ones\n",
    "ones_train = [1] * m_train\n",
    "ones_valid = [1] * m_valid\n",
    "\n",
    "# Insert ones to the fist column since\n",
    "# X_0 for all training examples should\n",
    "# be one.\n",
    "X_train.insert(0, \"X_0\", ones_train, True)\n",
    "X_valid.insert(0, \"X_0\", ones_valid, True)\n",
    "\n",
    "# Find the theta vector using the normal equation\n",
    "theta_train = calculate_theta(X_train,y_train)\n",
    "\n",
    "# Calculate elapsed CPU time\n",
    "end = process_time()\n",
    "execution_time = (end - start)*1000\n",
    "\n",
    "# display theta and cpu execution time of training\n",
    "print(\"\\nExecution time: {} milliseconds\".format(execution_time))\n",
    "print(\"\\nCalculated\\033[1m θ\\033[0m: {}\\n\".format(theta_train))\n",
    "\n",
    "# Calculate and display the cost value on the training dataset\n",
    "cost_train = J(X_train, y_train, theta_train)\n",
    "print(\"The training cost is: {}\".format(cost_train))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d78a33d8",
   "metadata": {
    "papermill": {
     "duration": 0.017886,
     "end_time": "2023-03-24T23:10:44.013290",
     "exception": false,
     "start_time": "2023-03-24T23:10:43.995404",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# Model Validation   <a id='validation'></a> "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "10c5c0de",
   "metadata": {
    "papermill": {
     "duration": 0.017416,
     "end_time": "2023-03-24T23:10:44.048999",
     "exception": false,
     "start_time": "2023-03-24T23:10:44.031583",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "We have split our data into two portions in the 'Loading Data' section. The training and validation datasets. These datasets are the same as the ones in the [Multivariate Linear Regression From Scratch](https://www.kaggle.com/code/erkanhatipoglu/multivariate-linear-regression-from-scratch) notebook. We will now use the validation dataset to validate our model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "fe89bba1",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-03-24T23:10:44.086993Z",
     "iopub.status.busy": "2023-03-24T23:10:44.086580Z",
     "iopub.status.idle": "2023-03-24T23:10:44.094452Z",
     "shell.execute_reply": "2023-03-24T23:10:44.093356Z"
    },
    "papermill": {
     "duration": 0.029595,
     "end_time": "2023-03-24T23:10:44.097008",
     "exception": false,
     "start_time": "2023-03-24T23:10:44.067413",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Calculated\u001b[1m θ\u001b[0m: [-1.34416734e+02  2.14141419e-01  2.77038677e-01  5.55692827e-01\n",
      "  5.10313673e-02  2.04133847e+00  1.15053979e+01  2.41256700e+00]\n",
      "\n",
      "The validation cost is: 20.39840017300976\n"
     ]
    }
   ],
   "source": [
    "print(\"\\nCalculated\\033[1m θ\\033[0m: {}\\n\".format(theta_train))\n",
    "\n",
    "cost_valid = J(X_valid, y_valid, theta_train)\n",
    "print(\"The validation cost is: {}\".format(cost_valid))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1a1bebfd",
   "metadata": {
    "papermill": {
     "duration": 0.006894,
     "end_time": "2023-03-24T23:10:44.111317",
     "exception": false,
     "start_time": "2023-03-24T23:10:44.104423",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "The cost of the validation dataset seems slightly bigger (worse) than the training dataset, which is expected. We can also see the validation results below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "5d2d90df",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-03-24T23:10:44.127573Z",
     "iopub.status.busy": "2023-03-24T23:10:44.126998Z",
     "iopub.status.idle": "2023-03-24T23:10:44.141030Z",
     "shell.execute_reply": "2023-03-24T23:10:44.140135Z"
    },
    "papermill": {
     "duration": 0.024885,
     "end_time": "2023-03-24T23:10:44.143303",
     "exception": false,
     "start_time": "2023-03-24T23:10:44.118418",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Actual CoA</th>\n",
       "      <th>Predicted CoA</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>90</th>\n",
       "      <td>64.0</td>\n",
       "      <td>66.062520</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>254</th>\n",
       "      <td>85.0</td>\n",
       "      <td>83.467888</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>283</th>\n",
       "      <td>80.0</td>\n",
       "      <td>77.803235</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>445</th>\n",
       "      <td>91.0</td>\n",
       "      <td>88.054515</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>461</th>\n",
       "      <td>68.0</td>\n",
       "      <td>60.126564</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "     Actual CoA  Predicted CoA\n",
       "90         64.0      66.062520\n",
       "254        85.0      83.467888\n",
       "283        80.0      77.803235\n",
       "445        91.0      88.054515\n",
       "461        68.0      60.126564"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Compare actual results with predicted results\n",
    "result = pd.DataFrame(index=X_valid.index)\n",
    "result['Actual CoA'] = y_valid\n",
    "result['Predicted CoA'] = h(X_valid, theta_train)\n",
    "result.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0fe46bb3",
   "metadata": {
    "papermill": {
     "duration": 0.007458,
     "end_time": "2023-03-24T23:10:44.158515",
     "exception": false,
     "start_time": "2023-03-24T23:10:44.151057",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# Conclusion   <a id='conclusion'></a> "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2d5306b8",
   "metadata": {
    "papermill": {
     "duration": 0.007205,
     "end_time": "2023-03-24T23:10:44.173227",
     "exception": false,
     "start_time": "2023-03-24T23:10:44.166022",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "By using the 'normal equation' method, we have created a more accurate model with a much faster time. This can be seen by comparing this notebook with the [Multivariate Linear Regression From Scratch](https://www.kaggle.com/code/erkanhatipoglu/multivariate-linear-regression-from-scratch) notebook in which we have created a model using gradient descent. But please note that the model with gradient descent could have been more precise; however, we preferred a faster model for demonstration purposes. We could create a better model by playing with the learning rate and the threshold value for convergence.  \n",
    "\n",
    "Anyway, you can find the comparison of the two models below:\n",
    "\n",
    "|Gradient Descent                           |Normal Equation                                                                     |\n",
    "|:------------------------------------------|:------------------------------------------------------------------------------------|\n",
    "|Training Cost: ~ 66.55                     |Training Cost: ~ 17.10                                                               |\n",
    "|Validation Cost: ~ 76.48                   |Validation Cost: ~ 20.40                                                             |\n",
    "|Execution Time \\[*]: ~ 25-30 millisecond   |Execution Time: ~ 5-15 millisecond                                                   |\n",
    "\n",
    "[*] Note that the execution time for the gradient descent is measured for a very high learning rate and a threshold value. For a standard training procedure, this value will be much more significant. On the other hand, the training and validation cost values will be much smaller.  \n",
    "\n",
    "And the comparison of the first 5 predictions of the validation dataset is below (CoA: Chance of Admit):\n",
    "\n",
    "|#  |Actual CoA              |Predicted CoA (Gradient Descent)             |Predicted CoA (Normal Equation)             |\n",
    "|:-:|:----------------------:|:-------------------------------------------:|:------------------------------------------:|\n",
    "|90 |64.0                    |70.687762                                    |66.062520                                   |\n",
    "|254|85.0                    |89.177016                                    |83.467888                                   |\n",
    "|283|80.0                    |60.641830                                    |77.803235                                   |\n",
    "|445|91.0                    |99.983114                                    |88.054515                                   |\n",
    "|461|68.0                    |52.698085                                    |60.126564                                   |\n",
    "\n",
    "As can be seen, the 'normal equation' gives us a more accurate and much faster solution for the small number of inputs. But if the number of inputs is high, gradient descent will be much better. And we must be aware that we can come across a non-invertible matrix.\n",
    "\n",
    "Thank you for reading!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bdb2f9d2",
   "metadata": {
    "papermill": {
     "duration": 0.007112,
     "end_time": "2023-03-24T23:10:44.187730",
     "exception": false,
     "start_time": "2023-03-24T23:10:44.180618",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# References   <a id='references'></a>\n",
    "[1] - [Machine Learning Specialization - Deeplearning.AI](https://www.deeplearning.ai/program/machine-learning-specialization/)\n",
    "\n",
    "[2] - [Andrew Ng](https://en.wikipedia.org/wiki/Andrew_Ng)\n",
    "\n",
    "[3] - [@Mohan S Acharya](https://www.kaggle.com/mohansacharya)\n",
    "\n",
    "[4] - [Multivariate Linear Regression From Scratch - Kaggle](https://www.kaggle.com/code/erkanhatipoglu/multivariate-linear-regression-from-scratch)\n",
    "\n",
    "[5] - [Univariate Linear Regression From Scratch - Kaggle](https://www.kaggle.com/code/erkanhatipoglu/univariate-linear-regression-from-scratch)\n",
    "\n",
    "[6] - [Univariate Linear Regression From Scratch - Towards AI](https://pub.towardsai.net/univariate-linear-regression-from-scratch-68065fe8eb09)\n",
    "\n",
    "[7] - [Multivariate Linear Regression From Scratch - Towards AI](https://medium.com/towards-artificial-intelligence/multivariate-linear-regression-from-scratch-c6702e26cce0https://medium.com/towards-artificial-intelligence/multivariate-linear-regression-from-scratch-c6702e26cce0)\n",
    "\n",
    "[8] - [Towards AI](https://pub.towardsai.net/)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.12"
  },
  "papermill": {
   "default_parameters": {},
   "duration": 12.685575,
   "end_time": "2023-03-24T23:10:44.917680",
   "environment_variables": {},
   "exception": null,
   "input_path": "__notebook__.ipynb",
   "output_path": "__notebook__.ipynb",
   "parameters": {},
   "start_time": "2023-03-24T23:10:32.232105",
   "version": "2.4.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}