====== Assignment: Kernel Perceptron ======

**📅 Deadline:** 18.12.2025 21:59

**🏦 Points:** 4

===== Task Description =====
In this assignment, you are tasked with implementing a **kernel Perceptron** algorithm. The goal is to understand how the "kernel trick," introduced in the Support Vector Machines lecture, can be used to create a non-linear classifier based on the simple Perceptron update rule. You can find the complete theoretical description of the assignment in the {{ :courses:be4m33ssu:homeworks:hw_assignment_kernel_perceptron_ws2025.pdf | Assignment PDF}} (last update 2025-11-13 22:00; bug fix).

You are provided with a {{ {{ :courses:be4m33ssu:homeworks:hw_kernel_perceptron_template_2025.zip |template}} containing the following files that you **do not** need to modify:

  * **utils.py**: Contains helper functions for loading data, saving your results, and visualizing the decision boundary. You do not need to modify this file.
  * **test-cases**: A folder containing public test cases to help you verify your implementation before submitting to [[https://cw.felk.cvut.cz/brute/student/course/BE4M33SSU/ker_percep|BRUTE]].

The template also includes the following file which you **do** need to modify:
  * **main.py**: This file contains the main logic. You will implement the kernel Perceptron algorithm here.


Your objective is to complete the **kernel_perceptron** function in the **main.py** file. You can find the parts to complete by searching for ''#TODO'' in the python file.

<note tip>
The prediction of the SVM needs to robustly handle the cases when the discriminant score is 0 or close to 0. To this end, you should disallow the scores to be small, e.g., ''if (np.abs(score) < 1e-7): "update weights"''
</note>

<note tip>
Since the kernel values are used repeatedly, it is efficient to pre-compute them once, store them in a matrix, and only index into the matrix in the Perceptron algorithm.
</note>

<note important>
All Python files from the template (`main.py` and `utils.py`) must be stored in the root of the .zip file you submit.
</note>


===== How to Test =====
After completing your implementation, you can test your solution locally using the provided public test cases before submitting it to BRUTE.

----


== Public Test Cases ==
You can validate your code by running the main script on the public instances:
  python main.py test-cases/public/instances/instance_1.json --visualize


  python main.py test-cases/public/instances/instance_2.json --visualize


  python main.py test-cases/public/instances/instance_3.json


For all of these instances, a correct implementation should successfully separate the data and produce the following output:

  
  --- Local Test ---
  Evaluating if the learned classifier correctly separates all training data...
  Training Accuracy: 100.00%
  ✅ Test PASSED: The model correctly classified all training points.


===== Submission Guidelines =====
  * Submit the completed code as a **.zip archive** via BRUTE.
  * All required python files (`main.py`, `utils.py`) must be stored in the **root** of the .zip archive.
  * Your implementation must find a perfectly separating hyperplane for all test cases within the given update budget. Good luck! 😊