<jupyter_start><jupyter_text>Using Cosine Similarity Model to Classify MNIST Hand-written DigitsBelow I write out the algorithm and show accuracy of it on the entire MNIST dataset.  I later go on to show how this approach needs far less data than other classification methods to work well (I think).<jupyter_code>import numpy as np
from tqdm import tqdm
import cupy as cp
import heapq
from collections import Counter
from sklearn.metrics.pairwise import cosine_similarity
from sklearn import datasets, model_selection
mnist = datasets.fetch_mldata('MNIST original')

data, target = mnist.data, mnist.target
data.shape, target.shape
indices = [0, 5923, 12665, 18623, 24754, 30596, 36017, 41935, 48200, 54051, 10000, 18000, 22000, 25000, 35000, 38000, 43000, 49000, 55000]
for i in indices:
    print(target[i])
# first make a function that takes in array and classifies it
def classification(indx):
    """indx: index of datapoint in dataset to be classified
    n: number of top values to compare
    returns: top n most similar indexes"""
    
    dist = []
    
    for i in range(0, len(target)):
        cpmr = [data[indx]]
        cpmr.append(data[i])
        cpmr = np.array(cpmr)
        
        cosim = cosine_similarity(cpmr)[0][1]
        dist.append(cosim)
    
    dist = np.array(dist)
    top = heapq.nlargest(5, range(len(dist)), dist.take)
    
    # top most similar index (excluding itself)
    decision = target[top[1]]
    
    if(target[indx] == decision):
        return decision, True
    else:
        return decision, False
%%time
p = classification(18623)<jupyter_output>CPU times: user 6.6 s, sys: 3.91 ms, total: 6.61 s
Wall time: 6.63 s<jupyter_text>Great! So the basics are working, now we just need to figure out how to find the accuracy of this throughout the whole dataset...<jupyter_code>%%time
# now make a loop that uses above function to test and predict accuracy
# just pick a random index and work with that.  if do enough over time will fall on all numbers
correct = 0
count = 0

for i in range(0, 100):
    indx = np.random.choice(target.shape[0])
    pred = classification(indx)
    
    if(pred[1] == True):
        correct += 1
        count += 1
    else:
        count += 1
        
    if(i%10 == 0):
        print(i)
print("correct")
print("\n" + "count" + "\n")
print(correct/count)<jupyter_output>correct

count

0.97<jupyter_text>optimizeNow, I will start messing around with everything to see how I can optimize it all.  The above version, **version 1, takes 6 seconds per classification and takes about ten minutes to classify 100 digits.  V1 is very slow**.<jupyter_code>%%time
cosine_similarity(np.array([data[0]]), data)<jupyter_output>CPU times: user 486 ms, sys: 274 ms, total: 760 ms
Wall time: 634 ms<jupyter_text>note how this took an order of magnitude less time with this technique<jupyter_code># try to optimize function
def classif(indx, n):
    """indx: index of datapoint in dataset to be classified
    n: number of top values to compare
    returns: top n most similar indexes"""

    dist = cosine_similarity(np.array([data[indx]]), data)
    
    top = heapq.nlargest((n+1), range(len(dist[0])), dist.take)
    #take off the first value as that is its own
    top = [target[i] for i in top[1:(n+1)]]
    
    mc = Counter(top)
    # voting on value to return
    return mc.most_common(1)[0][0]
%%time
classif(30596, 7) == target[30596]<jupyter_output>CPU times: user 665 ms, sys: 248 ms, total: 913 ms
Wall time: 699 ms<jupyter_text>Find accuracy<jupyter_code>def get_acc(n, steps):
    correct = 0
    count = 0
    #that way we can look and make sure it touched on all values
    indxls = []
    
    for i in range(0, steps):
        indx = np.random.choice(target.shape[0])
        indxls.append(indx)
        
        pred = classif(indx, n)
        
        if(pred == target[indx]):
            correct += 1
            count += 1
        else:
            count += 1
        
        if(i%100 == 0):
            print(str(i) + " correct: " + str(correct/count))
    
    return correct, count, (correct/count)
%%time
get_acc(5, 100)<jupyter_output>0 correct: 0.0
CPU times: user 1min 42s, sys: 30.3 s, total: 2min 12s
Wall time: 1min 8s<jupyter_text>**Version 2 (above) took about 1 minute, an order of magnitude faster than Version 1**<jupyter_code>%%time
get_acc(6, 1000)
%%time
get_acc(7, 10000)<jupyter_output>0 correct: 1.0
100 correct: 0.9900990099009901
200 correct: 0.9900497512437811
300 correct: 0.9833887043189369
400 correct: 0.9850374064837906
500 correct: 0.9860279441117764
600 correct: 0.9883527454242929
700 correct: 0.985734664764622
800 correct: 0.9862671660424469
900 correct: 0.9866814650388457
1000 correct: 0.988011988011988
1100 correct: 0.9872842870118075
1200 correct: 0.9866777685262281
1300 correct: 0.9846272098385856
1400 correct: 0.9857244825124911
1500 correct: 0.9846768820786143
1600 correct: 0.985633978763273
1700 correct: 0.9841269841269841
1800 correct: 0.9816768461965575
1900 correct: 0.9810625986322988
2000 correct: 0.9810094952523738
2100 correct: 0.9804854831032842
2200 correct: 0.9809177646524307
2300 correct: 0.9817470664928292
2400 correct: 0.9816743023740109
2500 correct: 0.9804078368652539
2600 correct: 0.98000768935025
2700 correct: 0.9796371714179933
2800 correct: 0.9796501249553731
2900 correct: 0.9800068941744227
3000 correct: 0.9803398867044318
3100 corr[...]<jupyter_text>So if this is anywhere faster than 10 minutes we know we have a good speedup.  And **Version 2 is much faster than Version 1**.**Next step is to see how little data this can work on**  Also speed up even more via vectorization and doing things like pre-picking the random index valuesAlso do weighted voting and distance of matrices instead of vectors.  When it gets one wrong, return index of incorrect one.First below will start by trying to furthur optimize the cosine similarity by messing with entereing matrices and pre-picking random numbers. Work towards vectorizing and optimizing even more<jupyter_code>data.shape, target.shape
#choose n random indices
random_indx = [np.random.choice(len(target)) for i in range(0, 1000)]
random_indx[:10]<jupyter_output><empty_output><jupyter_text>Now need to make some matrix P with n random images chosen from data.  Can do the same thing for either matrix passed into cosine_similarity so as to choose the amount of data testing on.<jupyter_code>P = [data[i] for i in random_indx]
P = np.array(P)
P.shape
# test how the output datastructure looks for cosine similarity between two matrices
X = np.array([[3, 5, 2],
             [4, 4, 1]])
Y = np.array([[3, 5, 2],
             [200, 10, 10]])
cosine_similarity(X, Y)
Z = [[3, 5, 3], [200, 10, 10]]
mc = Counter(Z)
classification = mc.most_common(1)
classification
top = [(heapq.nlargest(2, range(len(i)), i.take)) for i in Y]

top
def classif(indx, n):
    """indx: index of datapoint in dataset to be classified
    n: number of top values to compare
    returns: top n most similar indexes"""

    dist = cosine_similarity(np.array([data[indx]]), data)
    
    top = heapq.nlargest((n+1), range(len(dist[0])), dist.take)
    #take off the first value as that is its own
    top = [target[i] for i in top[1:(n+1)]]
    
    mc = Counter(top)
    # voting on value to return
    return mc.most_common(1)[0][0]
def most_common(lst):
    return max(set(lst), key=lst.count)
x = np.random.randint(1, 10, (5000))
x = list(x)
most_common(x)
def superclassif(comparisons, n):
    correct = 0
    count = 0
    # classify all comparisons
    random_indx = [np.random.choice(len(target)) for i in range(0, comparisons)]
    X = [data[i] for i in random_indx]
    X = np.array(X)
    
    # comparisons x size data structure
    cosim = cosine_similarity(X, data)
    
    # get top n indices for each
    top = [(heapq.nlargest((n), range(len(i)), i.take)) for i in cosim]
    top = [[target[j] for j in i] for i in top[:(n)]]
    
    pred = [most_common(i) for i in top]
    
    correct_classification = [target[i] for i in random_indx]
    
    for i, j in pred, correct_classification:
        if(i==j):
            correct += 1
            count += 1
        else:
            count += 1
random_indx = [np.random.choice(len(target)) for i in range(0, 5)]
random_indx
target[21490]
X = [data[i] for i in random_indx]
X = np.array(X)
X
cosim = cosine_similarity(X, data)
cosim.shape
top = [(heapq.nlargest((6), range(len(i)), i.take)) for i in cosim]
top
top = [[target[j] for j in i[1:6]] for i in top]
top
pred = [most_common(i) for i in top]
pred
correct_classification = [target[i] for i in random_indx]
correct_classification
count = 0
correct = 0
for i, j in zip(pred, correct_classification):
    if(i==j):
        correct += 1
        count += 1
    else:
        count += 1
        
print(correct/count)<jupyter_output>1.0<jupyter_text>FinalThis should be the final (optimized) version (version 3) coming from the work above, of course are always more way to optimize.I will now run again on 1,000 comparisons and see how it performs.  On last optimized version (version 2), it took about 10 minutes to run through 1,000.<jupyter_code>def most_common(lst):
    return max(set(lst), key=lst.count)

def superclassif(comparisons, n):
    """comparisons: the number of numbers to test
    n: number of top highest indices to vote on
    returns: amount of correct predictions, total predictions, and percentage accuracy"""
    correct = 0
    count = 0
    # classify all comparisons
    random_indx = [np.random.choice(len(target)) for i in range(0, comparisons)]
    X = [data[i] for i in random_indx]
    X = np.array(X)
    
    # comparisons x size data structure
    cosim = cosine_similarity(X, data)
    
    # get top n indices for each
    top = [(heapq.nlargest((n+1), range(len(i)), i.take)) for i in cosim]
    top = [[target[j] for j in i[1:(n+1)]] for i in top]
    
    pred = [most_common(i) for i in top]
    
    correct_classification = [target[i] for i in random_indx]
    
    for i, j in zip(pred, correct_classification):
        if(i==j):
            correct += 1
            count += 1
        else:
            count += 1
            
    acc = (correct / count) * 100
    
    return correct, count, acc
%%time
superclassif(1, 6)
%%time
superclassif(100, 5)<jupyter_output>CPU times: user 4.8 s, sys: 297 ms, total: 5.1 s
Wall time: 4.19 s<jupyter_text>**Version 3 (above) is even faster than version 1, classifying 100 samples in four seconds, far faster than Version 2 and Verison 1.  Note however, that Version 3 classifies one image in about the same time as Version 2.  This is because Version 3 is built to have a lot of images pushed through it at once, thus it is the same speed on the lower threshold of comparisons, but much faster on the upper threshhold.  If only singular comparisons were being made however, much could be done to Version 3 to make it faster on the lower threshold of comparisons.**<jupyter_code>%%time
superclassif(1000, 6)<jupyter_output>CPU times: user 40.4 s, sys: 458 ms, total: 40.9 s
Wall time: 37.7 s<jupyter_text>What took Version 2 11 minutes to complete, and what would have taken Version 1 over 100 minutes to complete, was done in 37 seconds on Version 3!Below I will mess with the n parameter a bit and see how I can nudge more accuracy with adjusting that.<jupyter_code>%%time
superclassif(1000, 3)
%%time
superclassif(1000, 4)
%%time
superclassif(1000, 5)
%%time
superclassif(1000, 13)
%%time
superclassif(1000, 21)<jupyter_output>CPU times: user 40.1 s, sys: 475 ms, total: 40.6 s
Wall time: 37.3 s<jupyter_text>Looking at the results above, it would seem that smaller values of n do better than larget numbers, however the drop for larget numbers is not very steep.Now I will test on a large base of 10,000 with an n=3<jupyter_code>%%time
superclassif(10000, 3)<jupyter_output>CPU times: user 6min 30s, sys: 1.61 s, total: 6min 32s
Wall time: 6min 4s
{'fraction_non_alphanumeric': 0.09823297881249476, 'fraction_numerical': 0.0886860396951679, 'mean_word_length': 3.601926782273603, 'pattern_counts': {'":': 0, '<': 38, '<?xml version=': 0, '>': 38, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '12', 'dir': 'jupyter-structured-clean-dedup', 'id': '352941', 'license': 'MIT', 'n_tokens_mistral': 4713, 'n_tokens_neox': 3943, 'n_words': 1474, 'path': 'Model Development/Cosine-sim dev Pt. 2.ipynb', 'repo_name': 'KadjelRamkisoen/Cosine-Similarity-Classifier', 'size': '11941'}