main.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Programming Homework 1\n",
    "## Instructions\n",
    "- Do not import other libraries. You are only allowed to use Math,\n",
    "Numpy, Scipy packages which are already imported in the file.\n",
    "- Please follow the type annotations. There are some type annotations of the parameters of function calls and return values. Please use\n",
    "Python 3.5 or 3.6 (for full support for typing annotations). You can\n",
    "use Numpy/Scipy inside the function.  You have to make\n",
    "the functions’ return values converted to the required type.\n",
    "- In this programming assignment you will to implement **Linear Regression**, **K-Nearest Neighbours* and *Perceptron algorithm**. We provide the bootstrap code and you are expected to complete the **classes** and **functions**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 1: Linear Regression"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 1.1 Implementation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Implement** the classes in file *hw1_lr.py*.\n",
    "\n",
    "    - LinearRegression\n",
    "    - LinearRegressionWithL2Loss\n",
    "   \n",
    "and the function in file *utils.py*:\n",
    "    \n",
    "    - mean_squared_error\n",
    "\n",
    "For linear regression with l2 loss (a.k.a. Ridge loss), here are two useful links: \n",
    "\n",
    "- [a tutorial blog](https://goo.gl/iTX39z)\n",
    "- [a lecture slide](http://www.stat.cmu.edu/~ryantibs/datamining/lectures/16-modr1.pdf)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The autoreload extension is already loaded. To reload it, use:\n",
      "  %reload_ext autoreload\n"
     ]
    }
   ],
   "source": [
    "# for auto-reloading external modules\n",
    "# see http://stackoverflow.com/questions/1907993/autoreload-of-modules-in-ipython\n",
    "%load_ext autoreload\n",
    "%autoreload 2\n",
    "from hw1_lr import LinearRegression, LinearRegressionWithL2Loss\n",
    "from utils import mean_squared_error\n",
    "\n",
    "\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 1.2 Sanity test\n",
    "\n",
    "Do the following steps, as a simple test to check your model works correctly.\n",
    "\n",
    "- Load data (features and values) from function `generate_data_part_1`.\n",
    "- Create a LinearRegression model.\n",
    "- Train the model using the loaded data.\n",
    "- Calculate the MSE metric by your implementation of the mean squared error function.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from data import generate_data_part_1\n",
    "features, values = generate_data_part_1()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 1.2]\tmse: 0.00175\n"
     ]
    }
   ],
   "source": [
    "model = LinearRegression(nb_features=1)\n",
    "model.train(features, values)\n",
    "\n",
    "mse = mean_squared_error(values, model.predict(features))\n",
    "print('[part 1.2]\\tmse: {mse:.5f}'.format(mse=mse))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.legend.Legend at 0x112740e80>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "plt.scatter([x[0] for x in features], values, label='origin');\n",
    "plt.plot([x[0] for x in features], model.predict(features), label='predicted');\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 1.3 Feature Engineering\n",
    "In this part, we are following the same procedure as that in part \n",
    "\n",
    "a). First we will try the same process as above.\n",
    "We will try two cases : \n",
    "- No extra features\n",
    "- Adding polynomial features"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1.3.1 No extra features"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "from data import generate_data_part_2\n",
    "features, values = generate_data_part_2()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 1.3.1]\tmse: 0.39997\n"
     ]
    }
   ],
   "source": [
    "model = LinearRegression(nb_features=1)\n",
    "model.train(features, values)\n",
    "\n",
    "mse = mean_squared_error(values, model.predict(features))\n",
    "print('[part 1.3.1]\\tmse: {mse:.5f}'.format(mse=mse))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.legend.Legend at 0x11276a278>"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "plt.scatter([x[0] for x in features], values, label='origin');\n",
    "plt.plot([x[0] for x in features], model.predict(features), label='predicted');\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###  Part 1.3.2 Adding polynomial features\n",
    "\n",
    "Note that in that synthetic dataset, the value is actually not linear with the feature (it is exponential). Inspired by Taylor expansion, we are going to add some polynomial features based on existing features.\n",
    "More specifically, support \n",
    "$${\\vec {x}} = [x_1, ..., x_n]$$\n",
    "is the feature vector of one sample (whose value is $y$). Instead of modeling the relationship between $\\vec{x}$ and $y$, we modeling the relationship of $y$ and $\\vec{x'}$, where (suppose we are adding up to $k$-th degree polynomials)\n",
    "\n",
    "$${\\vec {x'}}_k = [x_1 , x_2 , ..., x_n , x_{21} , ..., x_{2n}, ..., x_{k1}, ..., x_{kn} ]. $$\n",
    "\n",
    "Repeat the 5 steps, then report the MSE value on training set and model weights for the following three cases: $k = 2, k = 4, k = 8$ (for all numbers, keep 6 digits after the decimal point). \n",
    "\n",
    "### !!! Make sure that features’s polynomials follow the order in the above equation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 1.3.2]\tk: 2\tmse: 0.02315\n",
      "[part 1.3.2]\tk: 4\tmse: 0.00002\n",
      "[part 1.3.2]\tk: 8\tmse: 0.00000\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<matplotlib.legend.Legend at 0x1127ae860>"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from utils import polynomial_features\n",
    "features, values = generate_data_part_2()\n",
    "plt.scatter([x[0] for x in features], values, label='origin');\n",
    "\n",
    "for k in [2, 4, 8]:\n",
    "    features_extended = polynomial_features(features, k)\n",
    "    model = LinearRegression(nb_features=k)\n",
    "    model.train(features_extended, values)\n",
    "    mse = mean_squared_error(values, model.predict(features_extended))\n",
    "    print('[part 1.3.2]\\tk: {k:d}\\tmse: {mse:.5f}'.format(k=k, mse=mse))\n",
    "    plt.plot([x[0] for x in features], model.predict(features_extended), label='k={k}'.format(k=k));\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 1.4 Train, validation, test\n",
    "\n",
    "### Data processing \n",
    "\n",
    "Do the following steps:\n",
    "\n",
    "- Load data (features and values) from function generate data part 3. It’s a classification dataset, but we just use it as a regression dataset in this assignment.\n",
    "- Check that there are 150 data samples and each sample have a feature vector of length 4.\n",
    "- Split the whole data set into three parts:\n",
    "    - the train set contains first 100 samples (0th - 99th samples),\n",
    "    - the validation set contains the next 20 samples (100th - 119th samples),\n",
    "    - the test set contains the rest 30 samples (120th - 149th samples)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "from data import generate_data_part_3\n",
    "features, values = generate_data_part_3()\n",
    "\n",
    "train_features, train_values = features[:100], values[:100]\n",
    "valid_features, valid_values = features[100:120], values[100:120]\n",
    "test_features, test_values = features[120:], values[120:]\n",
    "\n",
    "assert len(train_features) == len(train_values) == 100\n",
    "assert len(valid_features) == len(valid_values) == 20\n",
    "assert len(test_features) == len(test_values) == 30"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1.4.1 LinearRegression"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Hyper-parameter and model selection \n",
    "\n",
    "For linear regression model with extra polynomial features, $k$ is a hyper-parameter. \n",
    "To choose the best one, we have to \n",
    "\n",
    "    - train a model with that hyper-parameter based on the train set, \n",
    "    - calculate its performance on the validation set\n",
    "    - select the best hyper-parameter (the trained model has the best performance on validation set). \n",
    "    \n",
    "In this task, we only search $k$ among the set {1, 3, 10}. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 1.4.1]\tk: 1\ttrain mse: 0.00909\tvalid mse: 0.00909\n",
      "[part 1.4.1]\tk: 3\ttrain mse: 0.00261\tvalid mse: 0.00261\n",
      "[part 1.4.1]\tk: 10\ttrain mse: 2.98654\tvalid mse: 2.98654\n"
     ]
    }
   ],
   "source": [
    "best_mse, best_k = 1e10, -1\n",
    "for k in [1, 3, 10]:\n",
    "    train_features_extended = polynomial_features(train_features, k)\n",
    "    model = LinearRegression(nb_features=k)\n",
    "    model.train(train_features_extended, train_values)\n",
    "    train_mse = mean_squared_error(train_values, model.predict(train_features_extended))\n",
    "\n",
    "    valid_features_extended = polynomial_features(valid_features, k)\n",
    "    valid_mse = mean_squared_error(valid_values, model.predict(valid_features_extended))\n",
    "    print('[part 1.4.1]\\tk: {k:d}\\t'.format(k=k) + \n",
    "          'train mse: {train_mse:.5f}\\tvalid mse: {valid_mse:.5f}'.format(\n",
    "              train_mse=train_mse, valid_mse=train_mse))\n",
    "\n",
    "    if valid_mse < best_mse:\n",
    "        best_mse, best_k = valid_mse, k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 1.4.1 Linear Regression]\tbest_k: 1\ttest mse: 0.08778\n"
     ]
    }
   ],
   "source": [
    "combined_features_extended = polynomial_features(train_features + test_features, best_k)\n",
    "model = LinearRegression(nb_features=best_k)\n",
    "model.train(combined_features_extended, train_values + test_values)\n",
    "\n",
    "test_features_extended = polynomial_features(test_features, best_k)\n",
    "test_mse = mean_squared_error(test_values, model.predict(test_features_extended))\n",
    "print('[part 1.4.1 Linear Regression]\\tbest_k: {best_k:d}\\ttest mse: {test_mse:.5f}'.format(\n",
    "    best_k=best_k, test_mse=test_mse))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1.4.2 Linear Regression With L2 Loss (Ridge Regression)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For Ridge (linear regression with l2 loss) Regression, we still need to search $k$ among {1, 3, 10}.\n",
    "$\\alpha$ is also a hyper-parameter, in this task, we search $\\alpha$ among the set {0.01, 0.1, 1, 10}."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 1.4.2]\tk: 1\talpha: 0.01\ttrain mse: 0.00909\tvalid mse: 0.33964\n",
      "[part 1.4.2]\tk: 1\talpha: 0.1\ttrain mse: 0.00911\tvalid mse: 0.34196\n",
      "[part 1.4.2]\tk: 1\talpha: 1\ttrain mse: 0.00955\tvalid mse: 0.35604\n",
      "[part 1.4.2]\tk: 1\talpha: 10\ttrain mse: 0.01058\tvalid mse: 0.40436\n",
      "[part 1.4.2]\tk: 3\talpha: 0.01\ttrain mse: 0.00270\tvalid mse: 3.33796\n",
      "[part 1.4.2]\tk: 3\talpha: 0.1\ttrain mse: 0.00288\tvalid mse: 2.69893\n",
      "[part 1.4.2]\tk: 3\talpha: 1\ttrain mse: 0.00336\tvalid mse: 2.12091\n",
      "[part 1.4.2]\tk: 3\talpha: 10\ttrain mse: 0.00412\tvalid mse: 1.56060\n",
      "[part 1.4.2]\tk: 10\talpha: 0.01\ttrain mse: 0.00021\tvalid mse: 15773.37831\n",
      "[part 1.4.2]\tk: 10\talpha: 0.1\ttrain mse: 0.00027\tvalid mse: 9165.03133\n",
      "[part 1.4.2]\tk: 10\talpha: 1\ttrain mse: 0.00038\tvalid mse: 2407.72803\n",
      "[part 1.4.2]\tk: 10\talpha: 10\ttrain mse: 0.00084\tvalid mse: 1519.90786\n"
     ]
    }
   ],
   "source": [
    "from itertools import product\n",
    "\n",
    "best_mse, best_k, best_alpha = 1e10, -1, -1\n",
    "for k, alpha in product([1, 3, 10], [0.01, 0.1, 1, 10]):\n",
    "    train_features_extended = polynomial_features(train_features, k)\n",
    "    model = LinearRegressionWithL2Loss(nb_features=k, alpha=alpha)\n",
    "    model.train(train_features_extended, train_values)\n",
    "    train_mse = mean_squared_error(train_values, model.predict(train_features_extended))\n",
    "\n",
    "    valid_features_extended = polynomial_features(valid_features, k)\n",
    "    valid_mse = mean_squared_error(valid_values, model.predict(valid_features_extended))\n",
    "    print('[part 1.4.2]\\tk: {k:d}\\talpha: {alpha}\\t'.format(k=k, alpha=alpha) +\n",
    "          'train mse: {train_mse:.5f}\\tvalid mse: {valid_mse:.5f}'.format(\n",
    "              train_mse=train_mse, valid_mse=valid_mse))\n",
    "\n",
    "    if valid_mse < best_mse:\n",
    "        best_mse, best_k, best_alpha = valid_mse, k, alpha"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 1.4.2]\tbest_k: 1\tbest_alpha: 0.010000\ttest mse: 0.08777\n"
     ]
    }
   ],
   "source": [
    "combined_features_extended = polynomial_features(train_features + test_features, best_k)\n",
    "model = LinearRegressionWithL2Loss(nb_features=best_k, alpha=best_alpha)\n",
    "model.train(combined_features_extended, train_values + test_values)\n",
    "\n",
    "test_features_extended = polynomial_features(test_features, best_k)\n",
    "test_mse = mean_squared_error(test_values, model.predict(test_features_extended))\n",
    "print('[part 1.4.2]\\tbest_k: {best_k:d}\\tbest_alpha: {best_alpha:f}\\t'.format(\n",
    "    best_k=best_k, best_alpha=best_alpha) +\n",
    "      'test mse: {test_mse:.5f}'.format(test_mse=test_mse))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 2: K-nearest neighbor (KNN) for binary classification"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Some notes\n",
    "\n",
    "In this task, we will use three distance functions: (we removed the vector symbol for simplicity)\n",
    "\n",
    "- Euclidean distance:  $$d(x, y) = \\sqrt{\\langle x - y, x - y \\rangle}$$\n",
    "- Inner product distance: $$d(x, y ) = \\langle x, y \\rangle$$\n",
    "- Gaussian kernel distance: \n",
    "    $$d(x, y ) = \\exp({−\\frac 12 \\sqrt{\\langle x - y, x - y \\rangle}}) $$\n",
    "\n",
    "\n",
    "F1-score is a important metric for binary classification, as sometimes the accuracy metric has the false positive (a good example is in MLAPP book 2.2.3.1 “Example: medical diagnosis”, Page 29)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2.1 Distance Functions\n",
    "\n",
    "Implement the class in file *hw1_knn.py*\n",
    "    - KNN\n",
    "    \n",
    "and the functions in *utils.py*    \n",
    "    - f1_score\n",
    "    - euclidean_distance\n",
    "    - inner_product_distance\n",
    "    - gaussian_kernel_distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The autoreload extension is already loaded. To reload it, use:\n",
      "  %reload_ext autoreload\n"
     ]
    }
   ],
   "source": [
    "# for auto-reloading external modules\n",
    "# see http://stackoverflow.com/questions/1907993/autoreload-of-modules-in-ipython\n",
    "%load_ext autoreload\n",
    "%autoreload 2\n",
    "\n",
    "from hw1_knn import KNN\n",
    "from utils import euclidean_distance, gaussian_kernel_distance, inner_product_distance\n",
    "from utils import f1_score\n",
    "\n",
    "distance_funcs = {\n",
    "    'euclidean': euclidean_distance,\n",
    "    'gaussian': gaussian_kernel_distance,\n",
    "    'inner_prod': inner_product_distance,\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Data processing \n",
    "\n",
    "Do the following steps:\n",
    "\n",
    "- Load data (features and values) from function generate data cancer\n",
    "- Check that there are 569 data samples and each sample have a feature vector of length 30.\n",
    "- Split the whole data set into three parts:\n",
    "     - the train set contains first 400 samples (0th - 399th samples),\n",
    "     - the validation set contains the next 60 samples (400th - 459th samples),\n",
    "     - the test set contains the rest 109 samples (460th - 568th samples)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "from data import generate_data_cancer\n",
    "features, labels = generate_data_cancer()\n",
    "\n",
    "train_features, train_labels = features[:400], labels[:400]\n",
    "valid_features, valid_labels = features[400:460], labels[400:460]\n",
    "test_features, test_labels = features[460:], labels[460:]\n",
    "\n",
    "assert len(train_features) == len(train_labels) == 400\n",
    "assert len(valid_features) == len(valid_labels) == 60\n",
    "assert len(test_features) == len(test_labels) == 109"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Model selection \n",
    "In kNN model, the parameter k is a hyper-parameter. In this task, we only search k among {1, 3, 10, 20, 50}."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.1] euclidean\tk: 1\ttrain: 1.00000\tvalid: 0.92832\n",
      "[part 2.1] euclidean\tk: 3\ttrain: 0.95137\tvalid: 0.95090\n",
      "[part 2.1] euclidean\tk: 10\ttrain: 0.95129\tvalid: 0.95090\n",
      "[part 2.1] euclidean\tk: 20\ttrain: 0.94094\tvalid: 0.95090\n",
      "[part 2.1] euclidean\tk: 50\ttrain: 0.90681\tvalid: 0.92832\n",
      "\n",
      "[part 2.1] euclidean\tbest_k: 3\ttest f1 score: 0.90603\n",
      "\n",
      "[part 2.1] gaussian\tk: 1\ttrain: 0.25373\tvalid: 0.11765\n",
      "[part 2.1] gaussian\tk: 3\ttrain: 0.25234\tvalid: 0.13043\n",
      "[part 2.1] gaussian\tk: 10\ttrain: 0.24670\tvalid: 0.13043\n",
      "[part 2.1] gaussian\tk: 20\ttrain: 0.22780\tvalid: 0.10448\n",
      "[part 2.1] gaussian\tk: 50\ttrain: 0.17012\tvalid: 0.04762\n",
      "\n",
      "[part 2.1] gaussian\tbest_k: 3\ttest f1 score: 0.13492\n",
      "\n",
      "[part 2.1] inner_prod\tk: 1\ttrain: 0.36204\tvalid: 0.43925\n",
      "[part 2.1] inner_prod\tk: 3\ttrain: 0.36204\tvalid: 0.43925\n",
      "[part 2.1] inner_prod\tk: 10\ttrain: 0.36204\tvalid: 0.43925\n",
      "[part 2.1] inner_prod\tk: 20\ttrain: 0.36204\tvalid: 0.43925\n",
      "[part 2.1] inner_prod\tk: 50\ttrain: 0.36204\tvalid: 0.43925\n",
      "\n",
      "[part 2.1] inner_prod\tbest_k: 1\ttest f1 score: 0.43229\n",
      "\n"
     ]
    }
   ],
   "source": [
    "for name, func in distance_funcs.items():\n",
    "    best_f1_score, best_k = -1, 0\n",
    "    for k in [1, 3, 10, 20, 50]:\n",
    "        model = KNN(k=k, distance_function=func)\n",
    "        model.train(train_features, train_labels)\n",
    "        train_f1_score = f1_score(\n",
    "            train_labels, model.predict(train_features))\n",
    "\n",
    "        valid_f1_score = f1_score(\n",
    "            valid_labels, model.predict(valid_features))\n",
    "        print('[part 2.1] {name}\\tk: {k:d}\\t'.format(name=name, k=k) + \n",
    "              'train: {train_f1_score:.5f}\\t'.format(train_f1_score=train_f1_score) +\n",
    "              'valid: {valid_f1_score:.5f}'.format(valid_f1_score=valid_f1_score))\n",
    "\n",
    "        if valid_f1_score > best_f1_score:\n",
    "            best_f1_score, best_k = valid_f1_score, k\n",
    "\n",
    "    model = KNN(k=best_k, distance_function=func)\n",
    "    model.train(train_features + valid_features,\n",
    "                train_labels + valid_labels)\n",
    "    test_f1_score = f1_score(test_labels, model.predict(test_features))\n",
    "    print()\n",
    "    print('[part 2.1] {name}\\tbest_k: {best_k:d}\\t'.format(name=name, best_k=best_k) +\n",
    "          'test f1 score: {test_f1_score:.5f}'.format(test_f1_score=test_f1_score))\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2.2 Data transformation\n",
    "\n",
    "We are going to add one more step (data transformation) in the data processing part and see how it works. \n",
    "Sometimes, normalization plays an important role to make a machine learning model work (check term “Feature scaling” in wiki).\n",
    "\n",
    "Here, we take two different data transformation approaches.\n",
    "\n",
    "#### Normalizing the feature vector \n",
    "\n",
    "This one is simple but some times may work well. Given a feature vector $x$, the normalized feature vector is given by \n",
    "\n",
    "$$ x' = \\frac x {\\sqrt{\\langle x, x \\rangle}} $$\n",
    "If a vector is a all-zero vector, we let the normalized vector also be a all-zero vector.\n",
    "\n",
    "\n",
    "#### Min-max scaling the feature matrix\n",
    "\n",
    "The above normalization is data independent, that is to say, the output of the normalization function doesn’t depend on the rest training data. However, sometimes it would be helpful to do data dependent normalization. One thing to note is that, when doing data dependent normalization, we can only use training data, as the test data is assumed to be unknown during training (at least for most classification tasks).\n",
    "\n",
    "The min-max scaling works as follows: after min-max scaling, all values of training data’s feature vectors are in the given range.\n",
    "Note that this doesn’t mean the values of the validation/test data’s fea- tures are all in that range, because the validation/test data may have dif- ferent distribution as the training data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Implement** the functions in *utils.py*    \n",
    "    - normalize\n",
    "    - min_max_scale"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from utils import normalize, min_max_scale\n",
    "\n",
    "scaling_functions = {\n",
    "    'min_max_scale': min_max_scale,\n",
    "    'normalize': normalize,\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Model selection\n",
    "\n",
    "Repeat the model selection part in part 2.2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] euclidean\tmin_max_scale\tk: 1\ttrain: 1.00000\tvalid: 0.79538\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] euclidean\tmin_max_scale\tk: 3\ttrain: 0.95172\tvalid: 0.83274\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] euclidean\tmin_max_scale\tk: 10\ttrain: 0.95429\tvalid: 0.84085\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] euclidean\tmin_max_scale\tk: 20\ttrain: 0.93428\tvalid: 0.82955\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] euclidean\tmin_max_scale\tk: 50\ttrain: 0.91166\tvalid: 0.81191\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n[part 2.2] euclidean\tmin_max_scale\tbest_k: 10\ttest: 0.77461\n\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] gaussian\tmin_max_scale\tk: 1\ttrain: 0.27986\tvalid: 0.26829\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] gaussian\tmin_max_scale\tk: 3\ttrain: 0.31699\tvalid: 0.30233\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] gaussian\tmin_max_scale\tk: 10\ttrain: 0.29559\tvalid: 0.29412\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] gaussian\tmin_max_scale\tk: 20\ttrain: 0.29331\tvalid: 0.29412\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] gaussian\tmin_max_scale\tk: 50\ttrain: 0.23690\tvalid: 0.26829\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n[part 2.2] gaussian\tmin_max_scale\tbest_k: 3\ttest: 0.26711\n\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] inner_prod\tmin_max_scale\tk: 1\ttrain: 0.35897\tvalid: 0.41748\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] inner_prod\tmin_max_scale\tk: 3\ttrain: 0.35795\tvalid: 0.41748\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] inner_prod\tmin_max_scale\tk: 10\ttrain: 0.35484\tvalid: 0.40000\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] inner_prod\tmin_max_scale\tk: 20\ttrain: 0.34853\tvalid: 0.40594\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] inner_prod\tmin_max_scale\tk: 50\ttrain: 0.33222\tvalid: 0.39394\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n[part 2.2] inner_prod\tmin_max_scale\tbest_k: 1\ttest: 0.42632\n\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] euclidean\tnormalize\tk: 1\ttrain: 1.00000\tvalid: 0.83274\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] euclidean\tnormalize\tk: 3\ttrain: 0.94921\tvalid: 0.85270\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] euclidean\tnormalize\tk: 10\ttrain: 0.95429\tvalid: 0.86025\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] euclidean\tnormalize\tk: 20\ttrain: 0.93447\tvalid: 0.84777\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] euclidean\tnormalize\tk: 50\ttrain: 0.91679\tvalid: 0.81191\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n[part 2.2] euclidean\tnormalize\tbest_k: 10\ttest: 0.79715\n\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] gaussian\tnormalize\tk: 1\ttrain: 0.32773\tvalid: 0.34783\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] gaussian\tnormalize\tk: 3\ttrain: 0.32660\tvalid: 0.36170\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] gaussian\tnormalize\tk: 10\ttrain: 0.32203\tvalid: 0.35484\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] gaussian\tnormalize\tk: 20\ttrain: 0.30435\tvalid: 0.32584\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[part 2.2] gaussian\tnormalize\tk: 50\ttrain: 0.28121\tvalid: 0.31034\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n[part 2.2] gaussian\tnormalize\tbest_k: 3\ttest: 0.36994\n\n"
     ]
    }
   ],
   "source": [
    "for scaling_name, scaling_func in scaling_functions.items():\n",
    "    train_features = scaling_func(train_features)\n",
    "    valid_features = scaling_func(valid_features)\n",
    "    test_features = scaling_func(test_features)\n",
    "    \n",
    "    for name, func in distance_funcs.items():\n",
    "        best_f1_score, best_k = 0, -1\n",
    "        for k in [1, 3, 10, 20, 50]:\n",
    "            model = KNN(k=k, distance_function=func)\n",
    "            model.train(train_features, train_labels)\n",
    "            train_f1_score = f1_score(\n",
    "                train_labels, model.predict(train_features))\n",
    "            \n",
    "            valid_f1_score = f1_score(\n",
    "                valid_labels, model.predict(valid_features))\n",
    "            print('[part 2.2] {name}\\t{scaling_name}\\tk: {k:d}\\t'.format(name=name, scaling_name=scaling_name, k=k) +\n",
    "                  'train: {train_f1_score:.5f}\\t'.format(train_f1_score=train_f1_score) + \n",
    "                  'valid: {valid_f1_score:.5f}'.format(valid_f1_score=valid_f1_score))\n",
    "\n",
    "            if valid_f1_score > best_f1_score:\n",
    "                best_f1_score, best_k = valid_f1_score, k\n",
    "    \n",
    "        model = KNN(k=best_k, distance_function=func)\n",
    "        model.train(train_features + valid_features,\n",
    "                    train_labels + valid_labels)\n",
    "        test_f1_score = f1_score(test_labels, model.predict(test_features))\n",
    "        print()\n",
    "        print('[part 2.2] {name}\\t{scaling_name}\\t'.format(name=name, scaling_name=scaling_name) +\n",
    "              'best_k: {best_k:d}\\ttest: {test_f1_score:.5f}'.format(best_k=best_k, test_f1_score=test_f1_score))\n",
    "        print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 3: Perceptron Problem \n",
    "In this problem we will implement perceptron algorithm. Recall that perceptron algorithm can converge only when the data is linearly seperable. \n",
    "\n",
    "### Objective \n",
    "Implement the class `Perceptron` in file `hw1_perceptron.py`. \n",
    "\n",
    "#### Some notes\n",
    "- Perceptron update rule is whenever algorithm makes a mistake update\n",
    "weights as $$w ← w + \\frac{y_i x_i}{\\|x\\|}$$\n",
    "- Perceptron algorithm as discussed only works for linearly seperable\n",
    "data. In this problem you will see that it is indeed the case.\n",
    "- For data which is not linearly seperable there is class of model/classifiers\n",
    "called maximum margin classifiers which will be discussed later."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# for auto-reloading external modules\n",
    "# see http://stackoverflow.com/questions/1907993/autoreload-of-modules-in-ipython\n",
    "%load_ext autoreload\n",
    "%autoreload 2\n",
    "\n",
    "import matplotlib.pyplot as plt \n",
    "from data import generate_data_perceptron \n",
    "from hw1_perceptron import Perceptron\n",
    "import numpy as np\n",
    "\n",
    "## To clearly visualize the problem, we just use 2 features for now\n",
    "## y = f(x1,x2)\n",
    "\n",
    "nb_features=2\n",
    "model = Perceptron(nb_features=nb_features)\n",
    "x, y = generate_data_perceptron(nb_features=nb_features, seperation=2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# plot and satisfy your self that data is linearly seperable\n",
    "x1 = []\n",
    "x2 = []\n",
    "for i in x:\n",
    "    x1.append(i[1])\n",
    "    x2.append(i[2])\n",
    "plt.scatter(x1, x2, c=y)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now complete the train & predict function in Perceptron class. You algorithm should find the seperating hyperplane and model.predict should give all the labels correct.   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Accuracy on training data is 100.0\n100\n"
     ]
    }
   ],
   "source": [
    "converged = model.train(x, y)\n",
    "y_hat = model.predict(x) \n",
    "correct = 0 \n",
    "for i, y_real in enumerate(y):\n",
    "    if (y_hat[i]==y_real):\n",
    "        correct = correct + 1\n",
    "    \n",
    "print (\"Accuracy on training data is {}\".format(correct*100/len(y)))\n",
    "print (correct)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Plot the data points and seperating hyperplane to see your perceptron has actually learnt correct seperating plane\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "w = model.get_weights()\n",
    "x1 = []\n",
    "x2 = []\n",
    "for i in x:\n",
    "    x1.append(i[1])\n",
    "    x2.append(i[2])\n",
    "plt.scatter(x1, x2, c=y)\n",
    "plt.plot(np.arange(-3, 3, 1), -(w[1] * np.arange(-3, 3, 1) + w[0]) / w[2])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we will try a 80-20 split of data into train and test and see what happens\n",
    "Try shuffling too. The results will change on shuffling\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0, 0]\nAccuracy on testing data is 100.0\n"
     ]
    }
   ],
   "source": [
    "## TODO : Try shuffling the data\n",
    "\n",
    "model.reset()\n",
    "print (model.get_weights())\n",
    "test_x, train_x = x[80:], x[:80]\n",
    "test_y, train_y = y[80:], y[:80]\n",
    "converged = model.train(train_x, train_y)\n",
    "y_hat = model.predict(test_x) \n",
    "correct = 0 \n",
    "for i, y_real in enumerate(test_y):\n",
    "    if (y_hat[i]==y_real):\n",
    "        correct = correct + 1\n",
    "    \n",
    "print (\"Accuracy on testing data is {}\".format(correct*100/len(test_y)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "w = model.get_weights()\n",
    "x1 = []\n",
    "x2 = []\n",
    "for i in x:\n",
    "    x1.append(i[1])\n",
    "    x2.append(i[2])\n",
    "plt.scatter(x1, x2, c=y)\n",
    "plt.plot(np.arange(-3, 3, 1), -(w[1] * np.arange(-3, 3, 1) + w[0]) / w[2])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What if data is not linearly seperable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "nb_features=2\n",
    "model = Perceptron(nb_features=nb_features)\n",
    "x, y = generate_data_perceptron(nb_features=nb_features, seperation=1)\n",
    "# plot and satisfy your self that data is not linearly seperable\n",
    "x1 = []\n",
    "x2 = []\n",
    "for i in x:\n",
    "    x1.append(i[1])\n",
    "    x2.append(i[2])\n",
    "plt.scatter(x1, x2, c=y)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Algorithm didnot converge\nAccuracy on training data is 81.0\n81\n"
     ]
    }
   ],
   "source": [
    "converged = model.train(x, y)\n",
    "if (converged):\n",
    "    print ('Algorithm has converged')\n",
    "else:\n",
    "    print ('Algorithm didnot converge')\n",
    "    \n",
    "y_hat = model.predict(x) \n",
    "correct = 0 \n",
    "for i, y_real in enumerate(y):\n",
    "    if (y_hat[i]==y_real):\n",
    "        correct = correct + 1\n",
    "    \n",
    "print (\"Accuracy on training data is {}\".format(correct*100/len(y)))\n",
    "print (correct)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "w = model.get_weights()\n",
    "x1 = []\n",
    "x2 = []\n",
    "for i in x:\n",
    "    x1.append(i[1])\n",
    "    x2.append(i[2])\n",
    "plt.scatter(x1, x2, c=y)\n",
    "plt.plot(np.arange(-3, 3, 1), -(w[1] * np.arange(-3, 3, 1) + w[0]) / w[2])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finding a seperating plane when data is d dimensional. Note that we visualize only first two features, so data might not look seperable but might really be seperable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "nb_features=10\n",
    "model = Perceptron(nb_features=nb_features)\n",
    "\n",
    "# use seperation=1 for non-seperable \n",
    "# use seperation=2 for seperable \n",
    "\n",
    "x, y = generate_data_perceptron(nb_features=nb_features, seperation=1)\n",
    "# plot first two dimensions\n",
    "x1 = []\n",
    "x2 = []\n",
    "for i in x:\n",
    "    x1.append(i[1])\n",
    "    x2.append(i[2])\n",
    "plt.scatter(x1, x2, c=y)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Algorithm didnot converge\nAccuracy on training data is 85.0\n85\n"
     ]
    }
   ],
   "source": [
    "converged = model.train(x, y)\n",
    "if (converged):\n",
    "    print ('Algorithm has converged')\n",
    "else:\n",
    "    print ('Algorithm didnot converge')\n",
    "    \n",
    "y_hat = model.predict(x) \n",
    "correct = 0 \n",
    "for i, y_real in enumerate(y):\n",
    "    if (y_hat[i]==y_real):\n",
    "        correct = correct + 1\n",
    "    \n",
    "print (\"Accuracy on training data is {}\".format(correct*100/len(y)))\n",
    "print (correct)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}