Scribd
Upload
13 views16 pages

Face and Digit Classification Analysis

This document describes the results of implementing three algorithms - Naive Bayes, Perceptron, and k-Nearest Neighbors (kNN) - for face and digit classification on a project. For each algorithm, the document provides: 1) a description of the algorithm and challenges faced, 2) graphs of accuracy, standard deviation, time taken, and prediction error over varying training sample sizes, and 3) observations about trends in the results. The algorithms were tested on classifying images from datasets of faces and handwritten digits.

Uploaded by

manasvini nittala
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
13 views16 pages

Face and Digit Classification Analysis

This document describes the results of implementing three algorithms - Naive Bayes, Perceptron, and k-Nearest Neighbors (kNN) - for face and digit classification on a project. For each algorithm, the document provides: 1) a description of the algorithm and challenges faced, 2) graphs of accuracy, standard deviation, time taken, and prediction error over varying training sample sizes, and 3) observations about trends in the results. The algorithms were tested on classifying images from datasets of faces and handwritten digits.

Uploaded by

manasvini nittala
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

CS 520: INTRO TO ARTIFICIAL INTELLIGENCE

PROJECT 2

FACE AND DIGIT CLASSIFICATION


December 08, 2022

Manasvini Nittala (Net ID: mn777)


Sahithi Reddy Sakinala (Net ID: ss4362)
Jahnavi Manchala (Net ID: jm2658)

1. NAIVE BAYES

(A) ALGORITHM DESCRIPTION

In Naive Bayes, the feature used was pixel occupancy per region. So first, the al-
gorithm finds the maximum pixel occupancy across all features and all pictures for
that training set. With that maximum, it sets up a matrix for each unique data point
(faces/not faces, 1,2,3, etc.).

Each row corresponds to a feature, and each column is a number between 0 and
count. Where count is nothing but the max value in that column. Next, the algo-
rithm tallies and plots the feature and pixel data received from the training data in
their corresponding matrix. So, for example, if the face picture had 9 pixels in region
1. The face matrix would add a +1 to row 1, column 9. Then at the end, it would
divide each cell by the total number of pictures to create percentages for each feature
and pixel combination.

Lastly, when you test, the algorithm will take the features from the testing image
and look up the associated percent across all matrices. Each matrix will keep a score
by multiplying each feature percent by each other as given by the testing image fea-
ture. Each matrix score is independent of the other. The prediction list will be chosen
as the highest percentage of all the matrices.

1
(B) CHALLENGES FACED

1. Feature Extraction: Finding the right set of features was a bit difficult.
We first took the binary values as pixels but were unable to achieve the desired ac-
curacy, so we split the binary array into grids. We tested by splitting into 5 x 5, 10
x 10, and 20 x 20 grids. We felt that 10 x 10 grids were pretty comfortable to work
with.

2. Unused Values: We first filled all our arrays like faces, not faces, and digits with
0s but later realized that they affected the final prediction array as we multiplied the
probabilities. We solved it by replacing 0 with 0.01, small enough to be ignored but
large enough to uphold the predictions.

(C) TRAINING AND OBSERVATIONS

Observations for the Naive Bayes algorithm are based on its mean accuracy, stan-
dard deviation, prediction error, and time taken over 10% to 100% training samples.

i) Accuracy

Graph 1: Mean Accuracy for Digit using Naive Bayes

2
Graph 2: Mean Accuracy for Face using Naive Bayes

• As observed from the graphs, the Accuracy for both face and digit classification is
increasing with an increase in the sample size. Maximum Accuracy for Digit was 77%
and for Face was 88%

ii) Standard Deviation

Graph 3: Standard Deviation for Digit using Naive Bayes

3
Graph 4: Standard Deviation for Face using Naive Bayes

• As observed from the graphs, the Standard Deviation for both face and digit classi-
fication is increasing up to approximately 40% samples but remains almost constant
afterward.

iii) Time Taken

Graph 5: Time Taken for Digit using Naive Bayes

4
Graph 6: Time Taken for Face using Naive Bayes

• As observed from the graphs, the Time Taken for both face and digit classification
has a linear relationship with the sample size. As the sample size increases, the time
taken increases.

iv) Prediction Error

Graph 7: Prediction Error for Digit using Naive Bayes

5
Graph 8: Prediction Error for Face using Naive Bayes

• As observed from the graphs, the prediction error for Digit is the root mean squared
error (RMSE) between the actual test labels and the predicted test labels. As the
sample size increases, the prediction error decreases. The prediction error for Face is
the ratio of wrong predictions to the total number of predictions. For Face, too the
prediction error decreases as the sample size increases.

2. PERCEPTRON

(A) ALGORITHM DESCRIPTION

This algorithm begins with initializing random weights for each feature, which We
defined as pixel occupancy per region. We split the image into a 10x10 grid, so We
have 100 features. Each image has 100 weights. The weight vector is calculated by
multiplying each weight by its corresponding feature pixel density. If this resulting
number is favorable for faces, then the image predicts that it is a face.

If it is negative, then the prediction is not a face. To validate the correctness of


the prediction, the algorithm checks the corresponding training label. If the predic-
tion is correct, the algorithm moves on to the next image and calculates the weight
vector again. If the prediction is too high (predicted face and it is not face), then each
weight for that image is decremented by its corresponding feature. If the prediction
is too low (predicted not face, and it is a face), then each weight is incremented by
its corresponding feature. Our algorithm continues to loop through the training data
and update the weights until it hits a threshold of 74% correct guesses for digits and
81% for faces.

6
The only difference between training faces and digits is that for each image, the algo-
rithm calculates the weight vector for the digits 1-9 and chooses the highest one for
its prediction. If the prediction is wrong, the weights for the wrong predicted digit
are decreased by their respective features, and the weights for the correct digit are
increased by their respective features. This process takes quite a long time due to the
number of calculations that must be made at each iteration.

(B) CHALLENGES FACED

The main challenge in implementing perceptron is how much longer it took to train
digits rather than faces since guessing a face is a binary decision, while digits are not.
Also, calculating each f(x) weight vector for the digits took longer than calculating
just one f(x) weight vector for faces. This takes up more run time as well as memory.

(C) TRAINING AND OBSERVATIONS

Observations for the Naive Bayes algorithm are based on its mean accuracy, stan-
dard deviation, prediction error, and time taken over 10% to 100% training samples.

i) Accuracy

Graph 9: Mean Accuracy for Digit using Perceptron

7
Graph 10: Mean Accuracy for Face using Perceptron

• As observed from the graphs, the Accuracy for both face and digit classification is
increasing with an increase in the sample size. Maximum Accuracy for Digit was 72%
and for Face was 81%

ii) Standard Deviation

Graph 11: Standard Deviation for Digit using Perceptron

8
Graph 12: Standard Deviation for Face using Perceptron

• As observed from the graphs, the Standard Deviation for Digit is seeing a decreasing
trend as the sample size increases whereas Face is seeing an increasing trend but we
should make an observation that these standard deviation values are very very close
and can be approximated to one value.

iii) Time Taken

Graph 13: Time Taken for Digit using Perceptron

9
Graph 14: Time Taken for Face using Perceptron

• As observed from the graphs, the Time Taken for both face and digit classification
has an almost linear relationship with the sample size. As the sample size increases,
the time taken increases.

iv) Prediction Error

Graph 15: Prediction Error for Digit using Perceptron

10
Graph 16: Prediction Error for Face using Perceptron

• As observed from the graphs, the prediction error for Digit is the root mean squared
error (RMSE) between the actual test labels and the predicted test labels. As the
sample size increases, the prediction error decreases. The prediction error for Face
is the ratio of wrong predictions to the total number of predictions. For Face, many
fluctuations are observed, but when trained with 100% training data, the prediction
error is the minimum.

3. k NEAREST NEIGHBORS

(A) ALGORITHM DESCRIPTION

This algorithm works by taking the euclidean distance of the features in the testing
image against all the features of the images in the training data. So, for example,
image 1 of the testing data would be compared against all 5000 images in the training
data by finding the euclidean distance for each pairing. Then all that data is saved
into an array and sorted from lowest to highest. After that, the first three cells are
chosen to vote. The most frequently seen within those three cells is chosen for the
predictions. This process repeats for each image in the training set.

(B) CHALLENGES FACED

1. Run Time: The main challenge we faced while implementing kNN was the time it
took to return predictions. This problem arose with Digit data as there need to be
5000 comparisons made, and we are also iterating it to get the mean values. We have
tried other methods instead but found the comparison to be the best way. We have

11
reduced the run time by decreasing the number of iterations.

(C) TRAINING AND OBSERVATIONS

Observations for the Naive Bayes algorithm are based on its mean accuracy, stan-
dard deviation, prediction error, and time taken over 10% to 100% training samples.

i) Accuracy

Graph 17: Mean Accuracy for Digit using kNN

12
Graph 18: Mean Accuracy for Face using kNN

• As observed from the graphs, the Accuracy for both face and digit classification is
increasing with an increase in the sample size. Maximum Accuracy for Digit was 88%
and for Face was 74%

ii) Standard Deviation

Graph 19: Standard Deviation for Digit using kNN

Graph 20: Standard Deviation for Face using kNN

• As observed from the graphs, the Standard Deviation for digit classification in-
creases up to approximately 20% samples but remains almost constant afterward,

13
but for Face data, there is a decreasing trend observed, whereas the sample size in-
creases the standard deviation is decreasing.

iii) Time Taken

Graph 21: Time Taken for Digit using kNN

Graph 22: Time Taken for Face using kNN

• As observed from the graphs, the Time Taken for both face and digit classification
has a linear relationship with the sample size. As the sample size increases, the time
taken increases.

14
iv) Prediction Error

Graph 23: Prediction Error for Digit using kNN

Graph 24: Prediction Error for Face using kNN

• As observed from the graphs, the prediction error for Digit is the root mean squared
error (RMSE) between the actual test labels and the predicted test labels. As the
sample size increases, the prediction error decreases. The prediction error for Face is
the ratio of wrong predictions to the total number of predictions. For Face, too, the
prediction error decreases as the sample size increases.

15
Figure 1: Output Values for FACE

Figure 2: Output Values for DIGIT

16

Common questions

Powered by AI

For Naive Bayes, the maximum accuracy achieved was 88% for face classification and 77% for digit classification. Perceptron reached a maximum accuracy of 81% for face classification and 72% for digit classification. In contrast, the k-Nearest Neighbors (kNN) algorithm achieved a slightly higher accuracy for digit classification at 88% but lower for face classification at 74%. All algorithms showed an increase in accuracy with larger sample sizes .

For all three algorithms—Naive Bayes, Perceptron, and k-Nearest Neighbors—training time increases linearly with sample size. However, the Perceptron algorithm requires more time due to its iterative nature and weight updates, especially for digit classification because it involves multiple weight vector calculations. kNN is computationally intensive due to the requirement to compute distances for each pairing, which can also be time-consuming .

For Naive Bayes, the standard deviation increased up to approximately 40% of the samples, then remained constant. For the Perceptron, the standard deviation decreased for digits as the sample size increased but slightly increased for faces, though remaining close to a single value. In k-Nearest Neighbors, the standard deviation for digit classification stabilized after 20% of samples, while for face data, it decreased with increased sample sizes .

Grid size is crucial for feature extraction in digit and face classification, as it determines the granularity of the feature set used by the Naive Bayes and Perceptron algorithms. For example, moving from a pixel-wise binary value to a 10x10 grid for pixel occupancy per region allowed for a more detailed and effective representation of features. This was found to balance the trade-off between computational efficiency and classification accuracy effectively .

In Naive Bayes, the prediction error for digit classification, measured as RMSE, decreases as the training sample size increases, indicative of more robust model performance with larger datasets. Similarly, for the Perceptron, the prediction error also decreases with an increase in sample size but is initially higher due to the algorithm's iterative learning process, which is more sensitive to sample size variations .

To address long runtimes in k-Nearest Neighbors, the number of iterations was reduced to lessen computational load. For the Perceptron, adjustments largely focused on optimizing code efficiency given its inherently longer training process, particularly for digit categorization, which required multiple vector calculations. Both methods aimed to preserve prediction accuracy while streamlining processing time .

The Naive Bayes algorithm determines the matrix score by first looking up the associated percentage values across all matrices using the features extracted from the testing image. It then multiplies each feature's percentage together to compute a score for each matrix, independent of the others. The final prediction is chosen based on the matrix with the highest score .

When a prediction by the Perceptron algorithm is incorrect, it updates the weights differently based on whether the predicted face/digit is higher or lower than expected. If the prediction is too high, indicating a false positive, the algorithm decrements each weight by its corresponding feature. Conversely, if the prediction is too low, indicating a false negative, it increments each weight by its corresponding feature .

A significant challenge in feature extraction for the Naive Bayes algorithm was selecting the right set of features. Initially, binary pixel values were used, but due to inadequate accuracy, the approach was modified to split the binary array into grids of varying sizes. A 10x10 grid was eventually found to be optimal. To handle unused values affecting predictions, zeros were replaced with 0.01 to maintain the integrity of predictions while minimizing the impact .

The k-Nearest Neighbors algorithm faces a trade-off between speed and accuracy in digit classification due to computational demands. Achieving a high accuracy (up to 88%) requires comparing feature distances across many examples, which is time-consuming, especially with large datasets, leading to longer runtimes. Adjusting the number of nearest neighbors (k) and reducing iterations can improve speed but potentially at the cost of accuracy .

You might also like