Abstract:
Recognizing a digit in a black-white image is a relatively simple task: the input consists of black and white pixels, the digits are well separated from the background, and there are only ten possible output categories. Yet, this task deals with mapping from the 2-dimensional image space onto the category space and thus this task has considerable complexity. MNIST is the most widely used benchmark for isolated digit recognition. This is the dataset we used. In this project, we will attempt to build a structured model and machine learning algorithm that will give better performance compared to KNN algorithm. We started the 1st part with the assumption that there is no relationship between the nodes, so we take Naïve Bayes- NB algorithm. The accuracy was 75% compared to 93.41% that KNN gave. In the 2nd part we thought which structured algorithm can improve our results and we found LBP and used NB as the initiating values for the factors. This fusion of the 2 algorithms gave us accuracy of 83.74% when we used only 1 iteration and the accuracy decreased when we did more iterations. In the 3rd part we thought about the problems of all the algorithms we used and concluded that all of them should have big training data. From this need we developed a new algorithm that takes the edges with the highest and lowest probabilities for each label. In this part, all of the algorithms got only 1 image from each label and the new algorithm gave the highest performance with 48.77%.
Models and Algorithms:
knn vs Naive bayes, Naive bayes VS Loopy belief-propagation and dataset of 10 images 1 from each kind
Discussion and Conclusions:
We can infer from the basic part of the project that the connection between different edges didn’t influence the probability of the edges, meaning that relating to edges as mutually independent didn’t help increase the performance. This can also mean that the Naïve independence assumption doesn’t fit our classification problem. Because of that we have moved to a different, structured approach – the Loopy BP where every edge sends information to other edges in the graph and receives information in order to increase the performance of the predicting algorithm. We can see that after a single iteration the performance increased by 8.74% compared to the Naïve-Bayes. Furthermore, we can see that after 2 or 3 iterations the performance decreases and even worse than the Naïve-Bayes in the start. It is noted in some papers that Loopy BP converges to a local minimum and not global. The fact that after 2 iterations or more the Accuracy of the algorithm decreases can be explained by the fact that our algorithm found a local minimum and created an overfitted classifier for the test set. In the creative part we found an algorithm that gives a better performance compared to Naïve-Bayes and Loopy BP when the dataset is very small (=10 images) when we are taking at least 200 edges for this algorithm. In the start we assumed that there is no dependency between edges, and we saw that this assumption was wrong for this task with this data set. In the creative part we want to compare and find better algorithm for when the data is very small, a situation that happens regularly in the machine learning world and we found an algorithm that gave a better performance in this situation. The main conclusions from this project is that we don’t have the best algorithm that will give the best performance to every problem, however, we need to understand our problem, how much data we have and what are the right assumptions on it and then choose the right algorithm for the task.