<jupyter_start><jupyter_text>Run in Google Colab        View source on GitHub  This code is part of [Chapter 4 - Building a Reverse Image Search Engine: Understanding Embeddings ](https://learning.oreilly.com/library/view/practical-deep-learning/9781492034858/ch04.html).Note: In order to run this notebook on Google Colab you need to [follow these instructions](https://colab.research.google.com/github/googlecolab/colabtools/blob/master/notebooks/colab-github-demo.ipynbscrollTo=WzIRIt9d2huC) so that the local data such as the images are available in your Google Drive.  Similarity Search Level 2We benchmark the algorithms based on the time it takes to index images and locate the most similar image based on its features using the Caltech-101 dataset. We also experiment with t-SNE and PCA. Understanding the time it takes to index images and locate the most similar image based on its featuresFor these experiments we will use the features of the Caltech101 dataset that we read above.First, let's choose a random image to experiment with. We will be using the same image for all the following experiments. Note: the results may change if the image is changed.<jupyter_code>import numpy as np
import pickle
from tqdm import tqdm, tqdm_notebook
import random
import time
from sklearn.manifold import TSNE
from sklearn.decomposition import PCA
import PIL
from PIL import Image
from sklearn.neighbors import NearestNeighbors

import glob
import matplotlib
import matplotlib.pyplot as plt
import matplotlib.image as mpimg
%matplotlib inline
filenames = pickle.load(open('data/filenames-caltech101.pickle', 'rb'))
feature_list = pickle.load(open('data/features-caltech101-resnet.pickle',
                                'rb'))
class_ids = pickle.load(open('data/class_ids-caltech101.pickle', 'rb'))
num_images = len(filenames)
num_features_per_image = len(feature_list[0])
print("Number of images = ", num_images)
print("Number of features per image = ", num_features_per_image)
random_image_index = random.randint(0, num_images)<jupyter_output><empty_output><jupyter_text>Standard featuresThe following experiments are based on the ResNet-50 features derived from the images of the Caltech101 dataset.  Standard features + Brute Force Algorithm on one imageWe will be timing the indexing for various Nearest Neighbors algorithms, so let's start with timing the indexing for the Brute force algorithm. While running terminal commands in iPython like the `timeit` command, the variables are not stored in memory, so we need to rerun the same command to compute and store the results in the variable.<jupyter_code>%timeit NearestNeighbors(n_neighbors=5, algorithm='brute', metric='euclidean').fit(feature_list)
neighbors = NearestNeighbors(n_neighbors=5,
                             algorithm='brute',
                             metric='euclidean').fit(feature_list)<jupyter_output><empty_output><jupyter_text>Now, let's look at the time it takes to search for the nearest neighbors for the selected random image using the trained model with the Brute force algorithm.<jupyter_code>%timeit neighbors.kneighbors([feature_list[random_image_index]])<jupyter_output><empty_output><jupyter_text>Standard features + k-d Tree Algorithm  on one imageNow let's turn our attention to the next nearest neighbors algorithm, the k-d tree. Let's time the indexing for the k-d tree algorithm.<jupyter_code>%timeit NearestNeighbors(n_neighbors=5, algorithm='kd_tree').fit(feature_list)
neighbors = NearestNeighbors(n_neighbors=5,
                             algorithm='kd_tree').fit(feature_list)<jupyter_output><empty_output><jupyter_text>Now, time the search for the same random image using the k-d tree trained model.<jupyter_code>%timeit neighbors.kneighbors([feature_list[random_image_index]])<jupyter_output><empty_output><jupyter_text>Standard features + Ball Tree Algorithm  on one imageFinally, its time for our last nearest neighbors algorithm - the Ball Tree algorithm. As before, let's calculate the time it takes to train the model.<jupyter_code>%timeit NearestNeighbors(n_neighbors=5, algorithm='ball_tree').fit(feature_list)
neighbors = NearestNeighbors(n_neighbors=5,
                             algorithm='ball_tree').fit(feature_list)<jupyter_output><empty_output><jupyter_text>As before, let's time the search for the Ball Tree model.<jupyter_code>%timeit neighbors.kneighbors([feature_list[random_image_index]])<jupyter_output><empty_output><jupyter_text>We will increase the number of our test images so that we can experiment with how the scalability of different nearest neighbors algorithms change. Let's choose a random set of 100 or 1000 images to experiment. Note: the results may change if any of the images are changed Generate a list of images to do the next set of experiments on.<jupyter_code>random_image_indices = random.sample(range(0, num_images), 1000)
random_feature_list = [
    feature_list[each_index] for each_index in random_image_indices
]<jupyter_output><empty_output><jupyter_text>Standard features + Brute Force Algorithm on a set of imagesTime the search for the Brute force algorithm.<jupyter_code>neighbors = NearestNeighbors(n_neighbors=5,
                             algorithm='brute',
                             metric='euclidean').fit(feature_list)
%timeit neighbors.kneighbors(random_feature_list)<jupyter_output><empty_output><jupyter_text>Standard features +  k-d Tree Algorithm on a set of imagesTime the search for the k-d tree algorithm.<jupyter_code>neighbors = NearestNeighbors(n_neighbors=5,
                             algorithm='kd_tree').fit(feature_list)
%timeit neighbors.kneighbors(random_feature_list)<jupyter_output><empty_output><jupyter_text>Standard features +  Ball Tree Algorithm on a set of imagesTime the search for the Ball Tree algorithm.<jupyter_code>neighbors = NearestNeighbors(n_neighbors=5,
                             algorithm='ball_tree').fit(feature_list)
%timeit neighbors.kneighbors(random_feature_list)<jupyter_output><empty_output><jupyter_text>PCANow we have seen the time it takes to index and search using nearest neighbor algorithms on the full feature length. We can use PCA to compress the features and reduce the time. As before we set the number of features intended.<jupyter_code>num_feature_dimensions = 100
num_feature_dimensions = min(num_images, num_feature_dimensions,
                             len(feature_list[0]))<jupyter_output><empty_output><jupyter_text>Train the PCA model with the number of desired feature dimensions.<jupyter_code>pca = PCA(n_components=num_feature_dimensions)
pca.fit(feature_list)
feature_list_compressed = pca.transform(feature_list)
feature_list_compressed = feature_list_compressed.tolist()<jupyter_output><empty_output><jupyter_text>Let's try to understand the importance of each of the resultant features. The numbers displayed below show the relative importance of the first 20 features.<jupyter_code>print(pca.explained_variance_ratio_[0:20])<jupyter_output><empty_output><jupyter_text>Repeat the timing experiments. We use the same random image to experiment.Note: the results may change if the image is changed.  PCA + Brute Force Algorithm on one imageLet's time the indexing for the brute force algorithm.<jupyter_code>%timeit NearestNeighbors(n_neighbors=5, algorithm='brute', metric='euclidean').fit(feature_list_compressed)
neighbors = NearestNeighbors(n_neighbors=5,
                             algorithm='brute',
                             metric='euclidean').fit(feature_list_compressed)<jupyter_output><empty_output><jupyter_text>We will now time the search for the brute force algorithm.<jupyter_code>%timeit neighbors.kneighbors([feature_list_compressed[random_image_index]])<jupyter_output><empty_output><jupyter_text>PCA + k-d Tree Algorithm  on one imageTime the indexing for the k-d tree algorithm.<jupyter_code>%timeit NearestNeighbors(n_neighbors=5, algorithm='kd_tree').fit(feature_list_compressed)
neighbors = NearestNeighbors(n_neighbors=5,
                             algorithm='kd_tree').fit(feature_list_compressed)<jupyter_output><empty_output><jupyter_text>Time the search for the k-d tree algorithm.<jupyter_code>%timeit neighbors.kneighbors([feature_list_compressed[random_image_index]])<jupyter_output><empty_output><jupyter_text>PCA + Ball Tree Algorithm  on one imageTime the indexing for the ball tree algorithm.<jupyter_code>%timeit NearestNeighbors(n_neighbors=5, algorithm='ball_tree').fit(feature_list_compressed)
neighbors = NearestNeighbors(
    n_neighbors=5, algorithm='ball_tree').fit(feature_list_compressed)<jupyter_output><empty_output><jupyter_text>Time the search for the ball tree algorithm.<jupyter_code>%timeit neighbors.kneighbors([feature_list_compressed[random_image_index]])<jupyter_output><empty_output><jupyter_text>We use the same random indices to experiment. Note: the results may change if any of the images are changed.Generate a list of images to do the next set of experiments on.<jupyter_code>random_feature_list_compressed = [
    feature_list_compressed[each_index] for each_index in random_image_indices
]<jupyter_output><empty_output><jupyter_text>PCA + Brute Force Algorithm on a set of imagesTime the search for the brute force algorithm.<jupyter_code>neighbors = NearestNeighbors(n_neighbors=5,
                             algorithm='brute',
                             metric='euclidean').fit(feature_list_compressed)
%timeit neighbors.kneighbors(random_feature_list_compressed)<jupyter_output><empty_output><jupyter_text>PCA + k-d Tree Algorithm on a set of imagesTime the search for the k-d tree algorithm.<jupyter_code>neighbors = NearestNeighbors(n_neighbors=5,
                             algorithm='kd_tree').fit(feature_list_compressed)
%timeit neighbors.kneighbors(random_feature_list_compressed)<jupyter_output><empty_output><jupyter_text>PCA + Ball Tree Algorithm on a set of imagesTime the search for the Ball Tree algorithm.<jupyter_code>neighbors = NearestNeighbors(
    n_neighbors=5, algorithm='ball_tree').fit(feature_list_compressed)
%timeit neighbors.kneighbors(random_feature_list_compressed)<jupyter_output><empty_output><jupyter_text>Annoy Make sure you have `annoy` installed. You can install it using pip, `pip3 install annoy`.<jupyter_code>from annoy import AnnoyIndex
# Time the indexing for Annoy
t = AnnoyIndex(2048)  # Length of item vector that will be indexed
starttime = time.time()
for i in range(num_images):
    feature = feature_list[i]
    t.add_item(i, feature)
endtime = time.time()
print(endtime - starttime)
t.build(40)  # 50 trees
t.save('data/caltech101index.ann')<jupyter_output><empty_output><jupyter_text>Annoy on one image Time the search for one image for Annoy.<jupyter_code>u = AnnoyIndex(2048)
%timeit u.get_nns_by_vector(feature_list[random_image_index], 5, include_distances=True)
indexes = u.get_nns_by_vector(feature_list[random_image_index],
                              5,
                              include_distances=True)<jupyter_output><empty_output><jupyter_text>Helper function to time the search for multiple images for Annoy. Perform the search for the same image multiple times to get an average value.<jupyter_code>def calculate_annoy_time():
    for i in range(0, 100):
        indexes = u.get_nns_by_vector(feature_list[random_image_index],
                                      5,
                                      include_distances=True)<jupyter_output><empty_output><jupyter_text>Annoy on a set of imagesTime the search for multiple images for Annoy.<jupyter_code>%time calculate_annoy_time()<jupyter_output><empty_output><jupyter_text>PCA + AnnoyNow, let's time the indexing for Annoy for the PCA generated features.<jupyter_code>starttime = time.time()
# Length of item vector that will be indexed
t = AnnoyIndex(num_feature_dimensions)

for i in range(num_images):
    feature = feature_list_compressed[i]
    t.add_item(i, feature)
endtime = time.time()
print(endtime - starttime)
t.build(40)  # 50 trees
t.save('data/caltech101index.ann')<jupyter_output><empty_output><jupyter_text>PCA + Annoy for one imageTime the search for one image for Annoy.<jupyter_code>u = AnnoyIndex(num_feature_dimensions)
%timeit u.get_nns_by_vector(feature_list_compressed[random_image_index], 5, include_distances=True)
indexes = u.get_nns_by_vector(feature_list_compressed[random_image_index],
                              5,
                              include_distances=True)<jupyter_output><empty_output><jupyter_text>Helper function to time the search for multiple images for Annoy. Perform the search for the same image multiple times to get an average value.<jupyter_code>def calculate_annoy_time():
    for i in range(0, 100):
        indexes = u.get_nns_by_vector(
            feature_list_compressed[random_image_index],
            5,
            include_distances=True)<jupyter_output><empty_output><jupyter_text>PCA + Annoy on a set of imagesTime the search for multiple images for Annoy.<jupyter_code>%time calculate_annoy_time()<jupyter_output><empty_output><jupyter_text>NMS Lib<jupyter_code>import nmslib
index = nmslib.init(method='hnsw', space='cosinesimil')
index.addDataPointBatch(feature_list_compressed)
index.createIndex({'post': 2}, print_progress=True)<jupyter_output><empty_output><jupyter_text>NMS Lib on one image<jupyter_code># Query for the nearest neighbors of the first datapoint
%timeit index.knnQuery(feature_list_compressed[random_image_index], k=5)
ids, distances = index.knnQuery(feature_list_compressed[random_image_index],
                                k=5)<jupyter_output><empty_output><jupyter_text>NMS Lib on a set of images<jupyter_code># Get all nearest neighbors for all the datapoint
# using a pool of 4 threads to compute
%timeit index.knnQueryBatch(feature_list_compressed, k=5, num_threads=16)
neighbors = index.knnQueryBatch(feature_list_compressed, k=5, num_threads=16)<jupyter_output><empty_output><jupyter_text>Falconn<jupyter_code>import falconn
# Setup different parameters for Falonn
parameters = falconn.LSHConstructionParameters()
num_tables = 1
parameters.l = num_tables
parameters.dimension = num_feature_dimensions
parameters.distance_function = falconn.DistanceFunction.EuclideanSquared
parameters.lsh_family = falconn.LSHFamily.CrossPolytope
parameters.num_rotations = 1
parameters.num_setup_threads = 1
parameters.storage_hash_table = falconn.StorageHashTable.BitPackedFlatHashTable

# Train the Falconn model
falconn.compute_number_of_hash_functions(16, parameters)<jupyter_output><empty_output><jupyter_text>Falconn on a set of images<jupyter_code>dataset = np.array(feature_list_compressed)
a = np.random.randn(8677, 100)
a /= np.linalg.norm(a, axis=1).reshape(-1, 1)
dataset = a

index = falconn.LSHIndex(parameters)
%time index.setup(dataset)

query_object = index.construct_query_object()
num_probes = 1
query_object.set_num_probes(num_probes)

searchQuery = np.array(feature_list_compressed[random_image_index])
searchQuery = a[0]
%timeit query_object.find_k_nearest_neighbors(searchQuery, 5)<jupyter_output><empty_output><jupyter_text>PCA + Annoy<jupyter_code># Time the indexing for Annoy for the PCA generated features
starttime = time.time()
# Length of item vector that will be indexed
t = AnnoyIndex(num_feature_dimensions)

for i in range(num_images):
    feature = dataset[i]
    t.add_item(i, feature)
endtime = time.time()
print(endtime - starttime)
t.build(40)  # 50 trees
t.save('data/caltech101index.ann')
u = AnnoyIndex(num_feature_dimensions)
# Time the search for one image for Annoy
%timeit u.get_nns_by_vector(dataset[random_image_index], 5, include_distances=True)
indexes = u.get_nns_by_vector(dataset[random_image_index],
                              5,
                              include_distances=True)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.07852807283763277, 'fraction_numerical': 0.00973697521497218, 'mean_word_length': 5.406237343053868, 'pattern_counts': {'":': 0, '<': 153, '<?xml version=': 0, '>': 153, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '38', 'dir': 'jupyter-structured-clean-dedup', 'id': '586051', 'license': 'MIT', 'n_tokens_mistral': 5048, 'n_tokens_neox': 4809, 'n_words': 1260, 'path': 'code/chapter-4/2-similarity-search-level-2.ipynb', 'repo_name': 'owillner/Practical-Deep-Learning-Book', 'size': '15816'}