In this assignment, students create a GUI which allows the user to draw handwritten digits using a mouse and then attempts to recognize the character using a CS1-accessible machine learning algorithm.
The GUI consists of
- a canvas which responds to click-move mouse events by changing the color of the canvas pixel and capturing the corresponding entry in a 2D-List of 0s and 1s
- a button which runs the prediction algorithm
- a label to display the algorithm’s guess
- (optional) another canvas to show the closest match in the database of handwritten digit samples
- (optional) a clear button to clear the drawing canvas
The user’s handwritten digit is compared against a set of handwritten digit samples. The data for this comes from the well-known MNIST database. However, we have made some changes to the data which make it more appropriate for this assignment. Here are the changes we made:
- file format: The MNIST data is stored in a binary format. We converted this to a comma separated values (csv) file where every 29 lines consists of a line with the digit represented and then 28 lines representing the rows in the 28×28 pixel image.
- grayscale format: The MNIST data contains grayscale values which we converted to black and white (represented as 1s and 0s) for easy comparison with the canvas drawing.
- size: The MNIST data is large (60000 examples). We reduced this to the first 2000 examples which allows for a nice balance between prediction accuracy and algorithm run time.
The resulting data set has an easy-to-understand format that is just begging to be read in as 2D-lists which can then be compared to the 2D-list from the canvas drawing.
The Prediction Algorithm
The MNIST page gives the error rates of several machine learning algorithms, and one of the families of algorithms which performs well is K-nearest-neighbor. The K-nearest-neighbor algorithm works by comparing the unknown drawing against every sample in the database and predicting the most common label among the K most similar examples. This algorithm is accessible for CS1 students, especially when K=1, where you have to do the following:
- Create a function which can return a similarity score between two examples. We found that counting the number of pixels that agree between the two lists worked well, and it does a little better when black pixel agreement is weighted more heavily (5 points for agreeing on a black pixel, 1 point for agreeing on a white pixel). However, this is something that students can be given freedom to investigate on their own.
- Keep track of the example with the best similarity score and then use that to make the prediction.
- Assignment Handout
- Reformatted Data File
- Sample Starter Code: sample code can be provided depending on how much scaffolding needs to be provided. Here are some examples of code we used in two different terms for in-class labs leading up to the assignment. Some or all of these could be provided.
- nongui_1nn.py: Implement the 1-nearest-neighbor algorithm (or even just compare, the similarity score function), to predict the character in a mystery test file like mystery.csv
- display_characters_from_dataset.py: A GUI where handwriting samples from the data set can be displayed on a canvas.
- draw_on_canvas_save_as_2D_list.py: draw_on_canvas_save_as_2D_list.py: A GUI with a drawing canvas where the drawing can be saved to a 2D list.
- draw_on_big_canvas.py: Like draw_on_canvas_save_as_2D_list.py but with a canvas that is larger than the corresponding 2D list.
File input, GUI, 2D lists/arrays
CS1 second half
The assignment uses real data with a simple algorithm to achieve compelling results. No special external libraries or software is needed. It can be adapted to most programming languages that have some sort of GUI. The difficulty is scalable, with several opportunities for scaffolding or lead-in assignments as well as more difficult extensions.
While good-enough for students to have the satisfaction of building something that works, the prediction accuracy for the easy-level, 1-nearest-neighbor algorithm isn’t great for certain digits.
It also may need scaffolding for parts like saving drawing to 2D list or larger canvas than 28×28.
Variants and Extensions
We have built up to this assignment with previous smaller labs/assignments like
- Drawing Canvas: Create a GUI with a canvas you can draw on
- Non-GUI version: Split the data file into two parts; use one set as the unknown samples and the other as the known set of samples. Use the set of known samples to see how many of the unknown samples the algorithm can correctly identify. This has the benefit of allowing you to quantify the accuracy of your algorithm.
There are also extensions which can make the project more difficult or lead into more advanced topics in computer science:
- Improve the Predictor: As an extra challenge, students can try to improve the algorithm. Implementing the general K-nearest-neighbor algorithm is a little harder than the K=1 version but may result in better performance.
- GUI Handwriting Capture: Students can be challenged to capture their own handwritten numerals using the GUI, save them to a file (optional), and then make a prediction using the algorithm.