# 机器学习 深度学习 python代写

DLNN 2020: Assignment 1

Wojtek Kowalczyk

wojtek@liacs.nl

18 February 2020

Introduction

The objective of this assignment is to develop and evaluate several algorithms for classifying

images of handwritten digits. You will work with a simplified version of the famous MNIST

data set: a collection of 2707 digits represented by vectors of 256 numbers that represent 16×16

images. The data is split into a training set (1707 images) and a test set (1000 images). These

data sets are stored in 4 files: train in.csv, train out.csv, test in.csv, test out.csv,

where in and out refer to the input records (images) and the corresponding digits (class

labels), respectively. These files are stored in data.zip.

You may find more information about the original problem of handwritten digit recognition,

more data sets, and an overview of accuracies of best classifiers (it is about 99.6%!) at

Task 1: Analyze distances between images

The purpose of this task is to develop some intuitions about clouds of points in highly

dimensional spaces. In particular, you are supposed to develop a very simple algorithm for

classifying hand-written digits.

Let us start with developing a simple distance-based classifier. For each digit d, d =

0, 1, . . . , 9, let us consider a cloud of points in 256 dimensional space, Cd, which consists of

all training images (vectors) that represent d. Then for each cloud Cd we can calculate its

center, cd, which is just a 256-dimensional vector of means over all coordinates of vectors that

belong to Cd. Once we have these centers, we can easily classify new images: to classify an

image, calculate the distance from the vector that represents this image to each of the 10

centers; the closest center defines the label of the image. But first let us take a closer look at

our data.

For each cloud Cd, d = 0, 1, . . . , 9, calculate its center, cd, and the radius, rd. The

radius of Cd is defined as the biggest distance between the center of Cd and points from Cd.

Additionally, find the number of points that belong to Cd, nd. Clearly, at this stage you are

supposed to work with the training set only.

Next, calculate the distances between the centers of the 10 clouds, distij = dist(ci, cj), for

i, j = 0, 1, . . . 9. Given all these distances, try to say something about the expected accuracy

of your classifier. What pairs of digits seem to be most difficult to separate?

1

u

2707g digits 9 b 9

j

ooo test

as

o l 0 13 pie

25,6 numbers

70.0 du TtImgT

ri

Lx yH

Task 2: Implement and evaluate the simplest classifier

Implement the simplest distance-based classifier that is described above. Apply your

classifier to all points from the training set and calculate the percentage of correctly classified

digits. Do the same with the test set, using the centers that were calculated from the training

set. In both cases, generate a confusion matrix which should provide a deeper insight into

classes that are difficult to separate. A confusion matrix is here a 10-by-10 matrix (cij ), where

cij contains the percentage (or count) of digits i that are classified as j. Which digits are most

difficult to classify correctly? For calculating and visualising confusion matrices you may use

the sklearn package. Describe your findings. Compare performance of your classifier on the

train and test sets. How do the results compare to the observations you’ve made in Step 1?

How would you explain it?

So far we assumed that the distance between two vectors is measured with help of the Euclidean

distance. However, this is not the only choice. Rerun your code using alternative distance

measures that are implemented in sklearn.metrics.pairwise.pairwise distances.

Which distance measure provides best results (on the test set)?

Task 3: Implement a multi-class perceptron algorithm

Implement (from scratch) a multi-class perceptron training algorithm (from slide 36, second

lecture) and use it for training a single layer perceptron with 10 nodes (one per digit),

each node having 256+1 inputs and 1 output. Train your network on the train set and evaluate

on both the train and the test set, in the same way as you did in the previous steps.

As your algorithm is non-deterministic (results depend on how you initialize weights), repeat

your experiments a few times to get a feelinig of the reliability of your accuracy estimates.

Try to make your code efficient. In particular, try to limit the number of loops, using

matrix multiplication whenever possible. For example, append to your train and test data a

column of ones that will represent the bias. The weights of your network can be stored in a

matrix W of size 257×10. Then the output of the network on all inputs is just a dot product

of two matricies: Train and W, where Train denotes the matrix of all input vectors (one per

row), augumented with 1’s. To find the output node with the strongest activation use the

numpy argmax function. An efficient implementation of your algorithm shouldn’t take more

than a few seconds to converge on the training set (yes, the training sets consists of patterns

that are linearly separable so the perceptron algorithm will converge).

Finally, notice that the perceptron algorithm that is presented in the G´eron’s textbook on

page 287 (Equation 10-3) is slightly di↵erent than the algorithm discussed during the lecture

(slide 36). Accordingly, slightly modify your code and rerun your experiments (assume ⌘ to

be 1). Compare the results (accuracy, convergence speed, runtime).

Task 4: Linear Separability

What do you think: is the set of all images of the digit 1 (from the training set) linearly

separable from the set of all images of the digit 7? More generally, are images of the digit

i linearly separable from the images of the digit j, for i, j in {0, 1, . . . , 9}, such that i 6= j?

To answer these questions study the Cover’s Theorem, think about the answers, and then

implement the simple perceptron algorithm and apply it to all pairs of sets of images from

classes i and j. (Hint: don’t run your algorithm for more than a few hundred iterations).

And can you linearly separate the set of all images of i (for i in {0, 1, . . . , 9} from all

remaining images? (This time you might need to use a few thousands iterations.)

Task 5: Implement the XOR network and the Gradient Descent Algorithm

This is probably the last time in your life that you are asked to implement a neural network

from scratch – therefore, have fun! Proceed as follows:

1. Implement the function xor net(x1, x2, weights) that simulates a network with two

inputs, two hidden nodes and one output node. The vector weights denotes 9 weights

(tunable parameters): each non-input node has three incoming weights: one connected

to the bias node that has value 1, and two other connections that are leading from the

input nodes to a hidden node or from the two hidden nodes to the output node. Assume

that all non-input nodes use the sigmoid activation function.

2. Implement the error function, mse(weights), which returns the mean squared error

made by your network on 4 possible input vectors (0, 0), (0, 1), (1, 0), (1, 1) and the corresponding

targets: 0, 1, 1, 0.

3. Implement the gradient of the mse(weights) function, grdmse(weights). Note that the

vector of values that are returned by grdmse(weights) should have the same length

as the input vector weights: it should be the vector of partial derivatives of the mse

function over each element of the weights vector.

4. Finally, implement the gradient descent algorithm:

(a) Initialize weights to some random values,

(b) Iterate: weights = weights − ⌘ · grdmse(weights),

where ⌘ is a small positive constant (called “step size” or “learning rate”).

Use your program to train the network on the XOR data. During training, monitor two

values: the MSE made by your network on the training set (it should be dropping), and the

number of misclassified inputs. (The network returns a value between 0 and 1; we may agree

that values bigger than 0.5 are interpreted as “1”, otherwise as “0”.)

Run your program several times using various initialization strategies and values of the

learning rate. You may experiment with alternative activation functions, e.g., hyperbolic

tangent, tanh, or a linear rectifier, relu(x) = max(0, x).

Additionally, try the “lazy approach”: just keep generating random weights of the

network, testing if it computes the XOR function, and stop as soon as you’ve found such

weights. To get an idea how many sets of weights should be tried before finding a good one

repeat your experiment several times. Describe your work and findings in a report.

Organization

Your submission should consist of a report in the pdf format (at most 10 pages) and neatly

organized code that you’ve used in your experiments (but no data) so we (or others) could

reproduce your results. Submit your work via the Blackboard – details of the submission

procedure will be announced soon.

The deadline for this assignment is Sunday, 15th March, 23:59.