Graded question with feedback [20 points]

Implement in Python the batch perceptron with margin algorithm. To do so, you should first revisit the lecture slides to come up with the right variant of this algorithm.

1. As in the single-example perceptron with margin, the criterion to be (ideally) satisfied is that each training example must be correctly classified with a prescribed margin \(b\) (assumed \(> 0\)).
2. As in the simple batch perceptron, the weight vector is updated only once per batch and, for simplicity, one considers here the batch size to be the number of training examples (alternative implementations could consider a so-called mini batch size).
3. The stopping criterion is either that all margin constraints are satisfied and the algorithm has converged or a maximal number of epochs has been reached. One epoch corresponds to one weight update.

Note that, according to the standard Python indexing, the training examples are indexed here as x[0], x[1], ... The indexing convention may slightly differ in the lecture slides but the logic is exactly the same.

Your function will be tested on (subsets of) the data available in the task A2-2, which is a binary classification problem with class labels being either 0 or 1. You may notice that, in the perceptron algorithm, each y value is normally represented as 1 or -1. Therefore, the first step of the implementation of the perceptron should be to transform y to match this specification. This can be implemented by the line y = 2 * y - 1, already included in the code below.

The specification of the function is as follows (pay attention to the type of each parameter):

def perceptron(x, y, b, w_init, eta, epoch, decay=False):
    """
    Learn a binary classifier: batch perceptron with margin
    Inputs:    x : a feature matrix containing an example on each row [pandas DataFrame of shape n x d]
               y : a vector with the class (either 1 or 0) of each example  [numpy array of size n]
               b : a margin [float]
               w_init : a vector with the initial weight values (intercept in w_init[0]) [numpy array of size d+1]
               eta : an (initial) learning rate [float]
               epoch : the maximal number of epochs (1 epoch = 1 weight update) [int]
               decay : a boolean [default=False], when True the learning rate at the k-th weight update should be equal to eta/k.
                       When False, the learning rate should be equal to eta and should remain constant.
    Output:    A weight vector [list or numpy array of size d+1] (intercept in w[0])
    """

Graded question with feedback [20 points]

Implement in Python the function predict which predicts the labels of the examples contained in the data matrix x, according to the weight vector w.

Note that, even though you have to use 1 or -1 in your implementation of the perceptron, the predict function must output the class labels according to their original representation: either 1 or 0.

The specification of the function is as follows:

def predict(w, x):
    """
    Predicts the class labels of the data matrix x
    Inputs:    w a vector with the weight values defining a linear discriminant (intercept in w[0]) [list or numpy array of size d+1]
               x a feature matrix containing an example on each row [pandas DataFrame of shape n x d]
    Output:    A vector of labels (1 or 0) [numpy array of size n]
    """

Test question [30 points]

Implement in Python the Windrow-Hoff (or LMS) algorithm as described in the lecture slides.

Specifically, we ask the learning examples to be considered in order. Note that, according to the Python indexing, this order is x[0], x[1], ..., then back to x[0], .... Note also that the indexing convention may slightly differ in the lecture slides but the logic is exactly the same. For simplicity, no shuffling of the training examples is considered here.

Your function will be tested on (subsets of) the data available in the task A2-2, which is a binary classification problem with class labels being either 0 or 1.

def lms(x, y, b, w_init, eta, epoch, decay=True):
    """
    Learn a binary classifier with the Windrow-Hoff algorithm
    Inputs:    x : a feature matrix containing an example on each row [pandas DataFrame of shape n x d]
               y : a vector with the class (either 1 or 0) of each example  [numpy array of size n]
               b : equality constraint value (same value for each training point) [float]
               w_init : a vector with the initial weight values (intercept in w_init[0]) [numpy array of size d+1]
               eta : an (initial) learning rate [float]
               epoch : the maximal number of iterations (1 epoch = 1 iteration
                       of the "repeat" loop in the lecture slides) [int]
               decay : a boolean [default=True], when True the learning rate at iteration k should be equal to eta/k. When False,
                       the learning rate should be equal to eta and should remain constant.
    Output:    A weight vector [list or numpy array of size d+1] (intercept in w[0])
    """

Test question [30 points]: This question will be graded after the deadline. You will only receive credit for this question if you answered questions 1 and 2 correctly.

Run this algorithm on the training set till observing convergence or when a maximal number of iterations is reached. How is the margin and/or the learning rate chosen influencing the number of iterations performed? And the accuracy measured on the test set ?

Which conclusions can you draw from your experiments? To obtain sound results, you should probably repeat your experiments for various initializations of the model.

Select all valid affirmations.