2 - Perceptron
In this homework, we will implement the perceptron algorithm from scratch and experiment with it in different conditions. Submit a written report in .pdf format (no code) to the corresponding deliverable entry in the aula virtual. The report should contain a description of the whole procedure with some representative figures.
1 - Generate the data
The first thing we need to do is to define a function to generate synthetic datasets suitable for the task. In this homework, we will experiment with datasets of different sizes and different dimensions.
To build an intuition, we start with 2-dimensional data points. Start by sampling random points \(\mathbf{x}_n\in \mathbb{R}^2\) in a plane within a finite range. Then, choose a random line in the plane as your target function \(f\), where each side of the line belongs to a class, e.g., \(f(\mathbf{x})=\pm 1\). Finally, generate the dataset \(\left\{\left(\mathbf{x}_n,y_n\right)\right\}\), with labels \(y_n = f(\mathbf{x}_n)\).
To generalize this approach to arbitrary dimension \(d\), we simply need to change our line \(f\) to a hyperplane.
2 - Perceptron in \(\mathbb{R}^2\)
We will start by building some intuition in two dimensions, which is very easy to visualize.
2.1 - Sparse data points
Generate a dataset with 20 data points and run the perceptron algorithm. Plot the examples \(\left\{\left(\mathbf{x}_n,y_n\right)\right\}\), and the target function \(f\) and the final hypothesis \(g\) on a plane. Report the number of updates that the algorithm took to converge.
Repeat the procedure with more randomly generated datasets of the same size. Can you observe any differences? Report the results as described for the first dataset for two significant additional datasets.
2.2 - Some more data
Generate two more random datasets with 100 and 1000 examples and run the perceptron algorithm. Plot the examples \(\left\{\left(\mathbf{x}_n,y_n\right)\right\}\), and the target function \(f\) and the final hypothesis \(g\) on a plane. Report the number of updates that the algorithm took to converge.
3 - Perceptron in \(\mathbb{R}^{10}\)
Now that we have built some intuition visualizing the algorithm in two dimensions, let’s apply it in a high dimensional case.
Generate a dataset of 1000 samples with \(\mathbf{x}_n\in\mathbb{R}^{10}\) and run the perceptron algorithm. How many updates does it take to converge?
4 - Conclusions
Summarize your conclusions regarding the accuracy (how close is \(g\) to \(f\)) and running time of the perceptron algorithm as a function of the number of data points and the number of dimensions.