Digit recognition algorithm -- 2
Budget: $10 – $30 USD
In this exercise, you are to implement only one of two possible classifiers (your choice). Note, you are not to use modules which provide these functions - that would be too easy (no sklearn.naive_bayes, for example) but rather create them yourselves. Due to time constraints, we are concerned more with functionality rather than efficiency.
The data set to use is the digit recognition data set available from the sklearn module; the demonstration linked here (Links to an external site.) should provide some guidance. You are expected to use Jupyter notebooks and Python on this assignment, but can ask for exceptions.
Your goal is to take the first half of the data set to train your model, and the last half is used for prediction.
a) k-Nearest Neighbors
Each digit is an 8x8 pixel patch, which when reshaped is a 64 length vector.
Distance metric: the simplest distance metric for k-Nearest Neighbors is the sum of squares error between pixel values.
For each example in the test set, calculate the distance to every other example in the training set. Identify the closest k neighbors (a good use of numpy.argsort). Pick the class which most of the neighbors belong to. Break ties in any way you wish.
Compare the true class of each member of the test set to the predicted class using k-Nearest neighbors. Report the accuracy.
Now, change the value of k. Create a table with the accuracy for k=1, k=3, k=5, and k=100, and k=500
Show a classification matrix for each run of k. You can use sklearn.metrics.confusion_matrix for this
Note which errors are more common. In what way does that match your intuitions?
b) Gaussian Naive Bayes
x represent the image vector (x1, x2, x3, … x64)
ck represents class k = that is, one of the 10 digits for recognition
Recall, we’re looking for the highest p(ck|x) by using this fact:
p(ck|x) = p(x|ck) p(ck) / p(x)
Let’s step through the parts:
p(ck) is simply the proportion of that class in the training data. E.g. if there are 20 fives out of 200 digits in the training sample p(five) = 20/200 = 0.1
p(x|ck) is more complicated
The main assumption of naive Bayes is that the features should be treated independently (which is why it’s “naive”). This means
p(x|ck) = p(x1|ck) * p(x2|ck) * … * p(x64|ck)
For each class, k, in the training data:
Calculate the mean and variance of each pixel location for that class
Use that and the formula for a gaussian probability to calculate p(xi|ck)
p(x) is the normalization term. You don’t need to calculate this, since you just want to pick the largest p(ck|x), and p(x) is the same denominator in calculating p(ck|x) for every class.
However, if you want p(ck|x) to provide a true estimate of the probability, you can use the following formula to calculate p(x):
p(x) = Σk p(x,ck) = Σk p(x|ck) p(ck)
The predicted class is the largest p(ck|x) for each image
Report the overall accuracy of your prediction.
Show the classification matrix.
Note which errors are more common. In what way does that match your intuitions?
Turning it in:
Post the assignment on this discussion. Write which classifier you implemented, your names, and the date in the title of the card. Attach a PDF and the jupyter notebook file to the card.
Helpful tips:
The standard deviation is undefined when there is only one value for the feature. In this case, we can use a small value to avoid execution error, e.g. 0.00001
If the data is read as an integer array, you may want to recast it as a double array to avoid integer arithmetic. This is a common issue when working with certain image formats
Here is a colaboratory notebook (Links to an external site.) (a version of a jupyter notebook on google drive) which recreates the example naive bayes classifier discussed in class
The data set to use is the digit recognition data set available from the sklearn module; the demonstration linked here (Links to an external site.) should provide some guidance. You are expected to use Jupyter notebooks and Python on this assignment, but can ask for exceptions.
Your goal is to take the first half of the data set to train your model, and the last half is used for prediction.
a) k-Nearest Neighbors
Each digit is an 8x8 pixel patch, which when reshaped is a 64 length vector.
Distance metric: the simplest distance metric for k-Nearest Neighbors is the sum of squares error between pixel values.
For each example in the test set, calculate the distance to every other example in the training set. Identify the closest k neighbors (a good use of numpy.argsort). Pick the class which most of the neighbors belong to. Break ties in any way you wish.
Compare the true class of each member of the test set to the predicted class using k-Nearest neighbors. Report the accuracy.
Now, change the value of k. Create a table with the accuracy for k=1, k=3, k=5, and k=100, and k=500
Show a classification matrix for each run of k. You can use sklearn.metrics.confusion_matrix for this
Note which errors are more common. In what way does that match your intuitions?
b) Gaussian Naive Bayes
x represent the image vector (x1, x2, x3, … x64)
ck represents class k = that is, one of the 10 digits for recognition
Recall, we’re looking for the highest p(ck|x) by using this fact:
p(ck|x) = p(x|ck) p(ck) / p(x)
Let’s step through the parts:
p(ck) is simply the proportion of that class in the training data. E.g. if there are 20 fives out of 200 digits in the training sample p(five) = 20/200 = 0.1
p(x|ck) is more complicated
The main assumption of naive Bayes is that the features should be treated independently (which is why it’s “naive”). This means
p(x|ck) = p(x1|ck) * p(x2|ck) * … * p(x64|ck)
For each class, k, in the training data:
Calculate the mean and variance of each pixel location for that class
Use that and the formula for a gaussian probability to calculate p(xi|ck)
p(x) is the normalization term. You don’t need to calculate this, since you just want to pick the largest p(ck|x), and p(x) is the same denominator in calculating p(ck|x) for every class.
However, if you want p(ck|x) to provide a true estimate of the probability, you can use the following formula to calculate p(x):
p(x) = Σk p(x,ck) = Σk p(x|ck) p(ck)
The predicted class is the largest p(ck|x) for each image
Report the overall accuracy of your prediction.
Show the classification matrix.
Note which errors are more common. In what way does that match your intuitions?
Turning it in:
Post the assignment on this discussion. Write which classifier you implemented, your names, and the date in the title of the card. Attach a PDF and the jupyter notebook file to the card.
Helpful tips:
The standard deviation is undefined when there is only one value for the feature. In this case, we can use a small value to avoid execution error, e.g. 0.00001
If the data is read as an integer array, you may want to recast it as a double array to avoid integer arithmetic. This is a common issue when working with certain image formats
Here is a colaboratory notebook (Links to an external site.) (a version of a jupyter notebook on google drive) which recreates the example naive bayes classifier discussed in class