📄
Wiki/
🌌
Hierarchical Navigable Small Worlds and image recognition
Hierarchical Navigable Small Worlds and image recognition
🌌

Hierarchical Navigable Small Worlds and image recognition

Understanding Hierarchical Navigable Small Worlds

Small worlds are groups of things or objects that are linked together. A hierarchical navigable small world (HNSW) is a type of small world where the things or objects are organized a way that enables easy navigation between them: there is a specific order that determines how they are linked together.
One analogy is that of a city and its supporting road networks. Cities are organized in a way that makes them easy to navigate with small streets facilitating navigation from one neighborhood to another, and major highways that connect cities and then entire states. But the design of these road networks determines a certain ordering in how you navigate from place to place.
HNSW is a useful concept in machine learning because it helps organize items such that they are traversable at a local and global level, enabling fast retrieval of items organized as a network.

Using Hierarchical Navigable Small Worlds for Image Recognition

One ML application for HNSW is image recognition, a common machine learning task.
Traditional reverse image techniques search tend to be significantly slower because they typically perform a brute force search through the dataset of images to find the closest matches. This involves comparing the feature vector of the new image to the feature vectors of all the images in the dataset, which can be computationally expensive, especially when working with large datasets and high dimensional vectors.
HNSW, by contrast, enables nearest neighbor operations which is much faster for both search and retrieval. This can be useful to enable real-time ML applications of image recognition such as spotting people in need of rescue in disaster zones.
For example, you could create an HNSW structure on a dataset of images and their associated labels, where each image is represented by a high-dimensional feature vector. Then, when a new image is presented, you can use the HNSW to find the nearest neighbors of that image in the dataset, and use those neighbors to make a prediction about the label of the new image.
Having made the case for HNSW as a useful tool in the ML toolbox, let’s turn to how to implement it.

Implementing Hierarchical Navigable Small Worlds

Here are the steps you could take to implement hierarchical navigable small worlds (HNSWs) in an image recognition task using machine learning. For the steps that are highly-specific to HNSW, we have included code snippers to explain how to carry them out. The other steps should be largely familiar to those with experience performing ML tasks.
  1. Prepare the dataset: Collect a dataset of images and their associated labels. Then, extract feature vectors from each image using a feature extraction algorithm such as SIFT, SURF, or VGG.
  1. Create the HNSW structure: Using the feature vectors, create an HNSW structure by building a series of nested layers of nodes, where each node represents an image in the dataset. This can be done using a library such as NMSLIB.
import nmslib
nms = nmslib.init(method='hnsw', space='l2')
nms.addDataPointBatch(feature_vectors)
nms.createIndex({'efConstruction': 100, 'M': 16})
In this example, we're using the python library NMSLIB to create an HNSW, the method 'hnsw'is used to indicate that we're creating an HNSW, the space 'l2' is used to indicate that we're using the Euclidean distance as the similarity metric, efConstruction is the number of neighbors that a node will have and M is the number of links that a new node will have to existing nodes.
  1. Train the classifier: Train a classifier such as KNN, SVM or Random Forest using the feature vectors and labels of the images.
from sklearn.neighbors import KNeighborsClassifier
knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(feature_vectors, labels)
In this example, we're using the KNeighborsClassifier from the sklearn library to train a KNN classifier, the parameter n_neighbors indicates the number of neighbors that will be considered to make a prediction.
  1. Test the classifier: Use the classifier to classify new images by finding the nearest neighbors of the new image in the HNSW structure, and using the labels of those neighbors to make a prediction.
new_image_feature_vector = extract_feature_vector(new_image)
indices, distances = nms.knnQuery(new_image_feature_vector, k=5)
neighbors_labels = [labels[i] for i in indices]
prediction = max(set(neighbors_labels), key = neighbors_labels.count)
In this example, we're using the knnQuery method from the NMSLIB library to find the k nearest neighbors of the new image feature vector, the indices variable contains the indices of the images in the dataset that are the nearest neighbors and the distances variable contains the distance between the new image feature vector and the nearest neighbors. Then we're using these indices to retrieve the labels of the nearest neighbors and we're using the max function to find the most common label among the nearest neighbors as the prediction.
  1. Fine-tune and evaluate: Fine-tune the parameters of the HNSW and the classifier, and evaluate the performance of the image recognition system using metrics such as accuracy, precision, recall and F1-score.
  1. Improve the representation: If the performance is not satisfactory, try different feature extraction algorithms to improve the representation of the images, this will allow the classifier to work with more informative data.
  1. Deployment: Once the performance is satisfactory, the system can be deployed in a production environment.
It's worth noting that the specific steps and library used may vary depending on the programming language and the platform you are using.

Conclusion

In this post, we have explained how HNSWs can be used to improve the performance of image recognition. We have discussed how HNSWs work and how they can be used to perform nearest neighbor search on high-dimensional feature vectors. We also provided examples of real-world applications of HNSWs in image recognition and a step-by-step guide on how to implement HNSWs in an image recognition task.
In conclusion, HNSWs are a powerful tool for image recognition and other similar tasks, they allow for faster and more precise nearest neighbor search, which can improve the performance of image recognition systems. With the increasing amount of data that we have today, it's more important than ever to have efficient methods to process and analyze it and HNSWs are one such method that can help us achieve this goal.

References and additional information”