RPZ/hw/07_perceptron/perceptron.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "03be629e",
   "metadata": {},
   "source": [
    "# RPZ assignment: Perceptron Algorithm\n",
    " \n",
    "**Detailed BRUTE upload instructions for this assignment are at the end of this notebook.**\n",
    "\n",
    "## Introduction\n",
    "In all the previous labs, we were trying to design a classifier $q(\\mathbf{x}):X \\rightarrow D$ by using the a priori probabilities $p_K(k)$ and the\n",
    "probability density functions $p_{X \\vert k}(\\mathbf{x}\\vert k)$. We were minimising\n",
    "the Bayesian risk or some more complex criterion. This kind of approach is\n",
    "commonly referred to as [generative](https://en.wikipedia.org/wiki/Generative_model), because we try to estimate the full\n",
    "probabilistic model of all variables (we try to find the probabilistic model\n",
    "which “generated” the training samples).\n",
    "\n",
    "Sometimes, this is however not practical or even possible, e.g. it is not\n",
    "possible to get enough samples to get a good estimate of $p_{X\\vert k}(\\mathbf{x}\\vert k)$, so \n",
    "instead we try to approximate the decision function $q(\\mathbf{x})$ directly\n",
    "without any knowledge of the underlying probability distribution. This\n",
    "approach is referred to as [discriminative](https://en.wikipedia.org/wiki/Discriminative_model), \n",
    "because we are only interested in training the classifier to make correct decisions and we do not care about\n",
    "the actual probabilistic model.\n",
    "\n",
    "In the discriminative approach, we define a criterion (emperical risk) $R_{\\text{emp}}(q)$ \n",
    "which estimates the risk of the classifier using the training set.\n",
    "Typically, we calculate $R_{\\text{emp}}(q)$ as the classification error of the\n",
    "classifier $q$ on a training set $\\mathcal{T}$ and we try to find a classifier $q^∗$ which\n",
    "minimizes the emperical risk:\n",
    "\\begin{align*} \n",
    "   \\mathcal{T}  &=\\{(\\mathbf{x}_i, y_i); \\mathbf{x}_i\\in R^n, y_i\\in\\{0,1\\}\\}_{i=1,\\ldots,N} \\\\\n",
    "   R_{\\text{emp}}(q)  &= \\frac{1}{N}\\sum_{i=1}^N W(q(\\mathbf{x}_i), y_i)\\\\\n",
    "   q^* &= \\arg\\min_q R_{\\text{emp}}(q)\n",
    "\\end{align*}\n",
    "\n",
    "where $W(d, k)$ denotes the loss function (typically the zero-one loss function is\n",
    "used). Note that in the discriminative task formulation no probability\n",
    "densities are used. In this lab we will also strictly use bold letters for\n",
    "vectors and regular font for scalars.\n",
    "\n",
    "Prepare the notebook environment and import current task file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "a8e7009e",
   "metadata": {},
   "outputs": [],
   "source": [
    "%load_ext autoreload\n",
    "%autoreload 2\n",
    "\n",
    "# %matplotlib inline\n",
    "\n",
    "from perceptron import *\n",
    "import scipy.io\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b78d293f",
   "metadata": {},
   "source": [
    "## Part 1: The Perceptron Algorithm\n",
    "\n",
    "Today's task is to implement the Perceptron algorithm for learning a linear\n",
    "classifier. In the case of a linear classifier for two classes ($\\vert K \\vert = 2$),\n",
    "the discriminative function $q(\\mathbf{x}) : X \\rightarrow \\{0,1\\}$ can be expressed as:\n",
    "\n",
    "<!-- \\begin{equation*} -->\n",
    "$$\n",
    "q(\\mathbf{x}) = \\left\\{ \\begin{array}{l l} 0 & \\quad \\mathbf{x} \\cdot \\mathbf{w} + b > 0 \\\\ 1 & \\quad \\mathbf{x} \\cdot \\mathbf{w} + b < 0 \\end{array} \\right.\n",
    "$$\n",
    "<!-- \\end{equation*} -->\n",
    "\n",
    "where $\\mathbf{x}=(x_1 , \\dots , x_n)^T$, $\\mathbf{w} = (w_1, \\dots , w_n)^T$, and\n",
    "$\\mathbf{x} \\cdot \\mathbf{w} = \\sum^{n}_{i = 1}{x_i w_i}$ denotes the dot product and the dimensionality of\n",
    "$X$ is $n$. In geometrical interpretation, the expression $\\mathbf{x} \\cdot \\mathbf{w} + b = 0$ is an\n",
    "equation of a line (or a hyperplane in higher dimensions) which divides the\n",
    "space into two subspaces and the value of the discriminative function $q(\\mathbf{x})$\n",
    "represents in which of the two subspaces the vector $\\mathbf{x}$ is located.\n",
    "\n",
    "Thus, the task of finding a linear classifier for two classes can be\n",
    "formulated as finding parameters $\\mathbf{w}$ and $b$ so that the following system of\n",
    "linear inequalities holds for each item $(\\mathbf{x}_i , y_i)$ in the training set:\n",
    "\\begin{align*}\n",
    "  \\mathbf{w} \\cdot \\mathbf{x}_i + b &> 0 \\quad \\text{if}\\;y_i = 0 \\\\\n",
    "  \\mathbf{w} \\cdot \\mathbf{x}_i + b &< 0 \\quad \\text{if}\\;y_i = 1\n",
    "\\end{align*}\n",
    "\n",
    "The solution of the system exists only if the training data are [linearly\n",
    "separable](https://en.wikipedia.org/wiki/Linearly_separable), in which case\n",
    "the solution can be found using the [Perceptron\n",
    "algorithm](https://en.wikipedia.org/wiki/Perceptron).\n",
    "\n",
    "The system of inequalities can be equally rewritten as \n",
    "\\begin{equation*}\n",
    "\\mathbf{v} \\cdot \\mathbf{z}_i > 0 \n",
    "\\end{equation*}\n",
    "if we substitute\n",
    "\\begin{align*}\n",
    "  \\mathbf{v} &= [\\mathbf{w}; b] \\\\\n",
    "  \\mathbf{z}_i &= [\\mathbf{x}_i; 1] \\quad \\text{if}\\;y_i = 0 \\\\\n",
    "  \\mathbf{z}_i &= -[\\mathbf{x}_i; 1] \\quad \\text{if}\\;y_i = 1\n",
    "\\end{align*}\n",
    "(try it yourself on a piece of paper - all that happened here is that we made\n",
    "a 'clever' substitution so that we still have a system of N inequalities, but\n",
    "now all inequalities have the same format).\n",
    "\n",
    "Now we can easily describe the algorithm:\n",
    "\n",
    ">  **The Perceptron Algorithm**\n",
    ">\n",
    "> 1. Initialize $\\mathbf{v} = 0$\n",
    "> 2. Find a vector $\\mathbf{z}_t$ in the (transformed) training set\n",
    ">  $\\{\\mathbf{z}_1, \\dots, \\mathbf{z}_N\\}$ for which the inequality $\\mathbf{v} \\cdot \\mathbf{z}_i > 0$ does not hold.\n",
    "> 3. Terminate the algorithm if there is no such vector for which the inequality from 2. does not hold, i.e. **all** inequalities are satisfied\n",
    "> 4. Update the parameters $\\mathbf{w}$ and $b$ using the vector $\\mathbf{z}_t$ (for which the inequality from 2. does not hold).\n",
    ">     - The solution is updated as $\\mathbf{v} = \\mathbf{v} + \\mathbf{z}_t$ \n",
    ">     - The model parameters $\\mathbf{w}$ and $b$ can be simply extracted from $\\mathbf{v}$ because $\\mathbf{v} = [ \\mathbf{w} ; b ]$. \n",
    "> 5. Go to step 2."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f9eeb1d6",
   "metadata": {},
   "source": [
    "\n",
    "### Implementation of the Perceptron algorithm\n",
    "Complete the function `w, b = perceptron(X, y, max_iterations)` which implements\n",
    "the perceptron algorithm. The function accepts a matrix `X` of `N` training\n",
    "samples and a vector `y` of training labels. The parameter `max_iterations`\n",
    "specifies the maximal number of iterations of the algorithm. If a solution is\n",
    "not found in the given number of iterations the function is expected to\n",
    "return `w, b = nan, nan` to signal this situation. \n",
    "\n",
    "**Hint**: There is more than one valid solution. All valid solutions are able to pass Brute-AE evaluation.\n",
    "\n",
    "**Hint**: Try to minimalise the number of loops in your code and use NumPy's array operations instead (for the sake of speed)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "ecdcdfa7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-2.  1.  1.]\n",
      "[-2. -2.  2.]\n",
      "[-2.  0.  3.]\n",
      "[0. 2. 4.]\n",
      "[ 0. -1.  5.]\n",
      "your solution may differ\n",
      "w:  [ 0. -1.] \n",
      "b:  5.0\n",
      "[3. 2. 1.]\n",
      "w:  [3. 2.] \n",
      "b:  1.0\n"
     ]
    }
   ],
   "source": [
    "# X = np.array([[1, 1, 2, 2], [1, 3, 5, 6]])\n",
    "# y = np.array([0, 0, 1, 1])\n",
    "\n",
    "X = np.array([[-2, 0, 0, 0, 2], [1, 0, 2, -3, 2]])\n",
    "y = np.array([1, 1, 0, 1, 0])\n",
    "# Run the perceptron algorithm with at most 100 iterations\n",
    "w, b = perceptron(X, y, 100)\n",
    "print('your solution may differ\\nw: ', w, '\\nb: ', b)\n",
    "# -> your solution may differ\n",
    "# -> w:  [ 2. -3.] \n",
    "# -> b:  9.0\n",
    " \n",
    "X = np.array([[3, 1, 2, 2], [2, 3, 5, 6]])\n",
    "y = np.array([0, 0, 1, 0])\n",
    "w, b = perceptron(X, y, 100)\n",
    "print('w: ', w, '\\nb: ', b)\n",
    "# -> w:  nan \n",
    "# -> b:  nan"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31de1aef",
   "metadata": {
    "lines_to_next_cell": 2
   },
   "source": [
    "### Test its functionality\n",
    "Test its functionality on synthetic two-dimensional linearly separable data that **you create**.\n",
    "\n",
    "- Manually generate the data (for example using [plt.ginput()](https://matplotlib.org/api/_as_gen/matplotlib.pyplot.ginput.html))\n",
    "- Find the linear classifier using the perceptron algorithm (the `perceptron` function you created)\n",
    "- Visualize the classifier and save the figure as `perceptron_linear.png`. **You are encouraged to create an interesting or funny picture of your own :)**\n",
    "- Test the algorithm for data, which cannot be linearly separated (e.g. the [XOR problem](https://en.wikipedia.org/wiki/Perceptron#History)). What's happening in this non-separable case?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "id": "31f0f2de",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load or input the custom X, y data, e.g. \n",
    "data = np.load(\"my_data_perceptron_separable.npz\", allow_pickle=True)\n",
    "X = data[\"X_nice\"]\n",
    "y = data[\"y_nice\"]\n",
    "\n",
    "# Drawing own pictures\n",
    "# import matplotlib\n",
    "# matplotlib.use('Qt5Agg')\n",
    "\n",
    "# plt.scatter([], []) # Create a scatter plot\n",
    "# points_0 = np.array(plt.ginput(n=-1,timeout=0))  # Collect clicks until the user presses Enter\n",
    "# plt.close()\n",
    "# plt.plot(points_0[:,0], points_0[:,1] ,'bo')\n",
    "# points_1 = np.array(plt.ginput(n=-1,timeout=0))  # Collect clicks until the user presses Enter\n",
    "# plt.close()\n",
    "\n",
    "# points_0 = points_0.T\n",
    "# points_1 = points_1.T\n",
    "\n",
    "# X = np.hstack((points_0,points_1))\n",
    "# y = np.ones(X.shape[1])\n",
    "# y[:points_0.shape[1]] = 0\n",
    "\n",
    "# np.savez('my_data_perceptron_separable.npz', X_nice=X, y_nice=y)\n",
    "\n",
    "\n",
    "# Run the perceptron algorithm\n",
    "w, b = perceptron(X, y, 1000)\n",
    "\n",
    "# Show the data and the resulting linear classifier\n",
    "plt.figure()\n",
    "plt.plot(X[0,y==0],X[1,y==0],'bx',ms=10)\n",
    "plt.plot(X[0,y==1],X[1,y==1],'r+',ms=10)\n",
    "x_bound =[np.min(X[0]), np.max(X[0])]\n",
    "xs = np.linspace(x_bound[0], x_bound[1])\n",
    "ys = -(xs*w[0] +b)/w[1]\n",
    "plt.plot(xs,ys,'k-')\n",
    "plt.title('Perceptron algorithm')\n",
    "plt.savefig('perceptron_linear.png')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "68f63ec7",
   "metadata": {
    "lines_to_next_cell": 2
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The algorithm did not converge in given iteration limit.\n",
      "w:nan\n",
      "b:nan\n"
     ]
    }
   ],
   "source": [
    "# Testing on unseparable data \n",
    "data = np.load(\"my_data_perceptron_unseparable.npz\", allow_pickle=True)\n",
    "X_un = data[\"X_nice\"]\n",
    "y_un = data[\"y_nice\"]\n",
    "\n",
    "# Drawing own pictures\n",
    "# import matplotlib\n",
    "# matplotlib.use('Qt5Agg')\n",
    "\n",
    "# plt.scatter([], []) # Create a scatter plot\n",
    "# points_0 = np.array(plt.ginput(n=-1,timeout=0))  # Collect clicks until the user presses Enter\n",
    "# plt.close()\n",
    "# plt.plot(points_0[:,0], points_0[:,1] ,'bo')\n",
    "# points_1 = np.array(plt.ginput(n=-1,timeout=0))  # Collect clicks until the user presses Enter\n",
    "# plt.close()\n",
    "\n",
    "# points_0 = points_0.T\n",
    "# points_1 = points_1.T\n",
    "\n",
    "# X_un = np.hstack((points_0,points_1))\n",
    "# y_un = np.ones(X_un.shape[1])\n",
    "# y_un[:points_0.shape[1]] = 0\n",
    "\n",
    "# np.savez('my_data_perceptron_unseparable.npz', X_nice=X_un, y_nice=y_un)\n",
    "\n",
    "# Run the perceptron algorithm\n",
    "w, b = perceptron(X_un, y_un, 1000)\n",
    "if np.all(np.isnan(w)):\n",
    "    print('The algorithm did not converge in given iteration limit.')\n",
    "print(f\"w:{w}\\nb:{b}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "18944ec0",
   "metadata": {
    "lines_to_next_cell": 0
   },
   "source": [
    "## Part 2: Lifting dimensionality of the feature space\n",
    "As we have seen in the last point of the first task, for some data a linear\n",
    "discriminative function that would separate the data does not exist.\n",
    "\n",
    "In order to deal with this problem, we will extend the Perceptron algorithm\n",
    "so that it learns quadratic discriminant function (see [non-linear perceptron](https://cw.fel.cvut.cz/wiki/_media/courses/be5b33rpz/labs/07_perceptron/nelin_perceptron_en.pdf)). We define a mapping function $\\phi: X \\rightarrow Z$ which projects the training samples\n",
    "$\\mathbf{x} \\in X$ (in the last example $X=\\mathbb{R}^2$) into a higher-dimensional space $Z$.\n",
    "\n",
    "In our task, we will consider the discriminative function in the form:\n",
    "$$\n",
    "q'(\\mathbf{x}) = w_1x_1 + w_2x_2 + w_3x_1^2 + w_4x_1x_2 + w_5x_2^2 + b\n",
    "$$\n",
    "By comparing this discriminative function $q'(\\mathbf{x})$ to the linear case $q(\\mathbf{x})$, we can derive the formula for \n",
    "the feature vector $\\mathbf{z} \\in Z$ in the lifted space:\n",
    "$$\n",
    "\\mathbf{z} = \\phi(\\mathbf{x})= (x_1, x_2, x_1^2, x_1x_2, x_2^2)^T\n",
    "$$\n",
    "\n",
    "The entire extension of the Perceptron algorithm then goes as follows:\n",
    "\n",
    "- Transform the training data into the lifted space $Z$ using the mapping function $\\phi(\\cdot)$\n",
    "- Run the standard linear Perceptron algorithm in the lifted space $Z$\n",
    "- Substitute found parameters $w_1, \\dotsc, w_5$ and $b$ into the quadratic discriminative function\n",
    "\n",
    "**Hint**: If the Perceptron algorithm does not converge for the lifted features, try increasing the number ``max_iterations``"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a51e70f6",
   "metadata": {},
   "source": [
    "### Implementation the lifting function\n",
    "\n",
    "Complete the function `Z = lift_dimension(X)` which implements the mapping $\\phi(\\cdot)$ of the feature space into the 5-dimensional space"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "id": "967128ec",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "w_un:[-35.48387097  70.88744589 -15.5632154   -8.12124703 -22.5234722 ]\n",
      "b_un:25.0\n"
     ]
    }
   ],
   "source": [
    "X = np.array([[1, 0, 2], [3, 5, 1]])\n",
    "Z = lift_dimension(X)\n",
    "\n",
    "np.testing.assert_equal(Z, \n",
    "                        np.array([[1 ,    0,     2],\n",
    "                                  [3 ,    5,     1],\n",
    "                                  [1 ,    0,     4],\n",
    "                                  [3 ,    0,     2],\n",
    "                                  [9 ,   25,     1]]),\n",
    "                        \"The lifting is incorrect!\")\n",
    "\n",
    "# Try lifting the unseparable data\n",
    "Z_un = lift_dimension(X_un)\n",
    "\n",
    "# Run the Perceptron algorithm with at most 1000 iterations on lifted data\n",
    "w_un, b_un = perceptron(Z_un, y_un, 100000)\n",
    "if np.all(np.isnan(w_un)):\n",
    "    print('The algorithm did not converge in given iteration limit.')\n",
    "print(f\"w_un:{w_un}\\nb_un:{b_un}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f12ab1dd",
   "metadata": {},
   "source": [
    "### Implementation the quadratic discriminative function\n",
    "Complete the template function `Y = classif_quadrat_perc(tst, model)` which classifies the testing data using the quadratic discriminative function $q'(\\mathbf{x})$\n",
    "\n",
    "The function is called automatically by the visualisation function `pboundary` and\n",
    "its role is to classify the supplied testing data tst (in our case 2D data)\n",
    "to two classes (i.e. the elements of the output Y are either 0 or 1).\n",
    "Parameters of the classifier are stored in the `model` parameter, which is the\n",
    "same one as the one passed to the `pboundary` function. In our case, the model\n",
    "will contain parameters of the current state of the quadratic classifier - `w` and `b`\n",
    "\n",
    "### Test its functionality\n",
    "Test functionality of the two functions on synthetic two-dimensional non-separable data that **you create**.\n",
    "\n",
    "- Manually generate some linearly non-separable data (for example using [plt.ginput()](https://matplotlib.org/api/_as_gen/matplotlib.pyplot.ginput.html))\n",
    "- Find the quadratic classifier using the perceptron algorithm\n",
    "- Visualize the classifier using the `pboundary` function and save the figure\n",
    "  into `perceptron_quadratic.png` (again use your imagination to create some interesting picture ;-))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "id": "565cece5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "w:[-35.48387097  70.88744589 -15.5632154   -8.12124703 -22.5234722 ]\n",
      "b:25.0\n"
     ]
    }
   ],
   "source": [
    "# Load or input the custom X, y data, e.g. \n",
    "X = X_un\n",
    "y = y_un\n",
    "\n",
    "# lift the input data to Z\n",
    "Z = lift_dimension(X)\n",
    "\n",
    "# Run the perceptron algorithm\n",
    "w, b = perceptron(Z, y, 2000)\n",
    "if np.all(np.isnan(w)):\n",
    "    print('The algorithm did not converge in given iteration limit.')\n",
    "print(f\"w:{w}\\nb:{b}\")\n",
    "\n",
    "# Show the data and the resulting classifier\n",
    "model = {'w': w, 'b': b}\n",
    "pboundary(X, y, model)\n",
    "plt.title('Perceptron algorithm with quadratic discriminative function')\n",
    "plt.savefig('perceptron_quadratic.png')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ed1ad44",
   "metadata": {},
   "source": [
    "## Submission to the BRUTE Upload System\n",
    "\n",
    "To fulfill this assignment, you need to submit these files (all packed in one ''.zip'' file) into the __[upload system](https://cw.felk.cvut.cz/brute/)__:\n",
    "\n",
    "  - **`perceptron.ipynb`** - a script for data initialisation, calling of the implemented functions and plotting of their results (for your convenience, will not be checked).\n",
    "  - **`perceptron.py`** - containing the following implemented methods:\n",
    "    - **`perceptron `** - a function which implements the perceptron algorithm, section 1.2\n",
    "    - **`lift_dimension `** - a mapping function which lifts the dimensionality of the feature space, section 1.YY\n",
    "    - **`classif_quadrat_perc `** - a quadratic discriminative function, section 1.ZZ\n",
    "  - **`perceptron_linear.png`** and **`perceptron_quadratic.png`** - images specified in the tasks\n",
    "\n",
    "When preparing a zip file for the upload system, **do not include any directories**, the files have to be in the zip file root."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fd2171c3-2e73-468b-9366-d073e0f1aae4",
   "metadata": {},
   "source": [
    "## Bonus Tasks\n",
    "Choose one or both of the following bonus tasks."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ff3fa8e0",
   "metadata": {},
   "source": [
    "\n",
    "### Kozinec's Algorithm\n",
    "Implement the Kozinec's algorithm for learning of a linear discriminant function. For a set of points $\\{x^j, j \\in J\\}$, the Kozinec's algorithm finds vector \n",
    "$\\alpha$, which satisfies a set of linear inequations\n",
    "\\begin{equation*}\n",
    "\\langle\\alpha, x^j\\rangle > 0,  \\quad j \\in J\n",
    "\\end{equation*}\n",
    "I.e. the problem is the same as in the Perceptron. The Kozinec's algorithm creates a sequence of vectors $\\alpha_1, \\alpha_2, \\ldots, \\alpha_t, \\alpha_{t+1}, \\ldots$ in the following way.\n",
    "\n",
    "**The algorithm**: Vector $\\alpha_1$ is any vector from the convex hull of the set $\\{x^j, j \\in J\\}$, e.g. one of the vectors $\\{x^j, j \\in J\\}$. If the vector \n",
    "$\\alpha_t$ has already been computed, $\\alpha_{t+1}$ is obtained using the following rules:\n",
    "1. A misclassified vector $\\{x^j, j \\in J\\}$ is sought, which satisfies $\\langle\\alpha_t, x^j\\rangle \\leq 0$\n",
    "2. If such $x_j$ does not exist, the solution to the task has been found, and $\\alpha_{t+1}$ equals to $\\alpha_t$.\n",
    "3. If such $x_j$ does exist, it will be denoted as $x_t$. Vector $\\alpha_{t+1}$ then lies on a line passing through $\\alpha_t$ and $x_t$. From all the points on the\n",
    "   line, $\\alpha_{t+1}$ is the closest one to the origin of the coordinate system. In other words\n",
    "   \\begin{equation*}\n",
    "      \\alpha_{t+1} = (1 - k) \\alpha_t + k x_t\n",
    "   \\end{equation*}\n",
    "   where\n",
    "   \\begin{equation*}\n",
    "      k = \\arg\\min_k |(1 - k) \\alpha_t + k x_t|.\n",
    "   \\end{equation*}\n",
    "\n",
    "**Find $k$ analytically, do not use numerical methods.**\n",
    "\n",
    "**Output**: Identical to the output to the task in section _Part 1: The Perceptron Algorithm_.\n",
    "\n",
    "**Hint**: The Kozinec algorithm is described in Chapter 5 of _Michail I. Schlesinger, Vaclav Hlavac. Ten Lectures on Statistical and Structural Pattern Recognition. Kluwer 2002_"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aa574b3e",
   "metadata": {},
   "source": [
    "\n",
    "### Multi-class Perceptron\n",
    "Implement multi-class perceptron learning algorithm. The mutli-class classifier is formulated as\n",
    "\\begin{equation*}\n",
    "    f(\\mathbf{x}) = \\arg\\max_{y\\in\\cal Y}\\,\\bigl(\\mathbf{w}_y^\\top\\mathbf{x}+b_y\\bigr),\n",
    "\\end{equation*}\n",
    "where $\\cal W=\\bigl\\{(\\mathbf{w}_y, b_y)\\mid y\\in\\cal Y\\bigr\\}$ is a set of classifier parameters and $\\cal Y$ is a set of classes.\n",
    "\n",
    "The training algorithm was not presented at the lectures, but it is simple and elegant as follows:\n",
    "1. Compute class means\n",
    "\\begin{equation*}\n",
    "    \\boldsymbol{\\mu}_y = \\frac{1}{|\\cal X^y|}\\sum_{i\\in\\cal X^y} \\mathbf{x}^y_i,\n",
    "\\end{equation*}\n",
    "where $\\cal X^y$ are indices of training set samples belonging to class $y$.\n",
    "2. Set $\\mathbf{w}_y = \\boldsymbol{\\mu}_y$ and $b_y = 0$ for all $y\\in \\cal Y$.\n",
    "3. From the training set $\\cal T=\\{(\\mathbf{x}^1,y^1),\\ldots,(\\mathbf{x}^m,y^m)\\}$ choose $(\\mathbf{x}^t,y^t)$ subject to $y^t \\neq \\hat{y}\\:$, where \n",
    "\\begin{equation*}\n",
    "    \\hat{y}= \\arg\\max_{y\\in\\cal Y}  \\,\\bigl(\\mathbf{w}_y^\\top\\mathbf{x}^t + b_y \\bigr)\n",
    "\\end{equation*}\n",
    "(i.e. arbitrary misclassified sample).\n",
    "4. Terminate if such a sample is not found. Parameters $\\cal W=\\{(\\mathbf{w}_y,b_y) \\mid y\\in\\cal Y\\}$ define a classificatior with zero training error.\n",
    "5. Otherwise let $\\hat{y}$ be the classification $\\mathbf{x}_t$ using current classifier. Modify classifier parameters $\\cal W$ as follows\n",
    "   \\begin{align*}\n",
    "   \\mathbf{w}_{y^t}     & := \\mathbf{w}_{y^t} + \\mathbf{x}^t\\,, \\hspace{2em} &  \\mathbf{w}_{\\hat{y}} & :=  \\mathbf{w}_{\\hat{y}} - \\mathbf{x}^t\\,,\\\\\n",
    "   b_{y^t}      & := b_{y^t} + 1\\,, \\hspace{2em} &  b_{\\hat{y}} & := b_{\\hat{y}} - 1\\,.\\\\\n",
    "   \\end{align*}\n",
    "6. Continue with step 3.\n",
    "\n",
    "**Plot the multi-class decision boundaries.**"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}