Learning equivalence hash functions

Abstract

Imaginez héberger une plateforme où les utilisateurs partagent du contenu original, tel que des images, de la musique ou des vidéos. Pour garantir l’intégrité, vous avez besoin d’un algorithme capable de détecter la réinsertion de contenu existant. Cependant, étant donné l’échelle massive des ajouts quotidiens, comparer directement chaque nouvelle publication avec des milliards d’éléments existants est impossible en pratique. Pour les réinsertions exactes, les tables de hachage sont la solution la plus efficace, permettant une détection des doublons en temps constant. Cependant, si la plateforme doit également repérer des réinsertions avec des modifications légères, cette solution ne fonctionne pas. Même une modification minime, comme l’altération d’un seul pixel, entraînera une valeur de hachage différente, associant ainsi le contenu original et modifié à des adresses distinctes dans la table, ce qui empêchera la plateforme de détecter le contenu altéré. De plus, un utilisateur malveillant pourrait effectuer des transformations plus complexes, telles que l’ajustement de la teinte, de la luminosité et de la saturation, ou introduire de légères distorsions ou rotations à l’image. Les approches actuelles pour traiter ce type de problème proviennent de la littérature sur les algorithmes de plus proches voisins approximatifs, où les techniques les plus prometteuses sont basées sur des arbres et des graphes. Cependant, bien qu’efficaces, ces techniques ne peuvent égaler l’efficience d’une simple consultation de table de hachage. Au cœur de ce travail, cette thèse introduit et explore les fonctions d'équihachage, une variante des fonctions de hachage conçue pour associer des instances «équivalentes» à la même empreinte (une chaîne binaire de longueur fixe). Dans notre exemple, une fonction d'équihachage appropriée attribuerait la même empreinte à la fois au contenu original et au contenu modifié, permettant une détection efficace des variations tout en conservant la simplicité et la rapidité de la table de hachage. Les fonctions d'équihachage étendent l'applicabilité de nombreux algorithmes basés sur le hachage. Dans notre exemple, elles élargissent le champ d’application de la recherche dans la table de hachage. Au-delà de cela, elles peuvent également étendre l'applicabilité des algorithmes basés sur les ensembles. Par exemple, étant donné une fonction d'équihachage qui associe tous les portraits d'une même personne à la même empreinte et une collection de portraits, on pourrait déterminer en temps constant si une personne figure dans la collection ou bien compter le nombre d'individus distincts dans celle-ci en temps linéaire. La plupart des exemples les plus intéressants nécessitent l'apprentissage profond pour entraîner la fonction d'équihachage appropriée. Idéalement, ces fonctions produiraient des empreintes identiques pour des instances équivalentes et des empreintes distinctes pour des instances non équivalentes. Cependant, les fonctions d'équihachage apprises ne sont pas idéales, et une partie importante de cette thèse traite des défis liés à leur entaînement, leur évaluation et l'amélioration de leurs performances. Deux métriques clés sont le taux de collision pertinente (Relevant-Collision Rate (RCR)), qui mesure la probabilité que des instances équivalentes partagent la même empreinte, et le taux de collision non pertinente (Irrelevant-Collision Rate (ICR)), qui mesure la probabilité que des instances non équivalentes partagent la même empreinte. Lorsqu'il s'agit de bases de données massives, l’ICR doit être exceptionnellement bas. Sinon, de nombreuses instances non équivalentes partageront la même empreinte, créant toutes sortes de problèmes. Atteindre un ICR faible présente deux défis: estimer avec précision un taux de collision aussi bas et entraîner efficacement des modèles capables de respecter ce critère strict. Pour répondre au premier défi, nous proposons l’intervalle de confiance de Chebyshev, qui tire parti du paradoxe des anniversaires pour estimer efficacement l’ICR. Pour le second défi, nous introduisons l'hypothèse de «challenge-starvation». Cette hypothèse identifie une limitation potentielle dans toutes les approches d'apprentissage contrastif existantes qui pourrait nuire à leur capacité d'obtenir un ICR bas. Pour contourner ce problème, nous présentons la fonction de perte de Shannon-Hamming, une stratégie d'entraînement novatrice qui se concentre exclusivement sur les signaux positifs. Notre fonction de perte améliore l'ICR d'un ordre de grandeur par rapport à ses prédécesseurs contrastifs. De plus, une fonction d'équihachage apprise devrait idéalement présenter un RCR élevé. Cependant, étant donné que la descente de gradient est incompatible avec la nature discrète de l'empreinte et que nous devons équilibrer le RCR avec un ICR exceptionnellement bas, les modèles attribueront parfois des empreintes distinctes à des instances équivalentes. Pour pallier cela, nous proposons l'algorithme de sondage multiple priorisé (prioritized multi-probing) qui exploite l'incertitude du modèle pour générer plusieurs empreintes pour chaque instance. Cette technique peut être utilisée pour améliorer le taux de détection des réinsertions de contenues modifiés dans notre exemple précédent. Nos expériences avec une base de données d'un milliard d'images démontrent la viabilité et le potentiel de notre projet de recherche. Imagine hosting a platform where users share original content, such as images, music, or videos. To maintain integrity, you need an algorithm that detects re-uploads of existing content. However, given the vast scale of daily uploads, directly comparing each new post against billions of existing items is impractical. For exact re-uploads, hash tables are the most efficient solution, enabling constant-time detection of duplicates. However, if the platform also needs to catch re-uploads with slight modifications, the hash table solution fails. Even an unnoticeable change, such as altering a single pixel, will result in a different hash value, mapping the original and modified content to distinct addresses in the table and thus preventing the platform from detecting the altered content. Moreover, a malicious user could perform more complex transformations, such as adjusting the hue, lightness, and saturation or introducing slight distortions or rotations to the image. Current approaches for addressing this type of problem come from the approximate nearest neighbors literature, where the most promising techniques are based on trees and graphs. However, while effective, these techniques cannot match the efficiency of a single hash table lookup. At its core, this thesis introduces and explores equihash functions, a variant of hash functions that map “equivalent” instances to the same fingerprint (a fixed-length binary string). In our example, an appropriate equihash function would map both the original and modified content to the same fingerprint, enabling efficient detection of slight variations while preserving the simplicity and speed of the hash table. Equihash functions extend the applicability of many hash-based algorithms. In our example, they expanded the scope of the hash table lookup. Beyond that, they can also extend the applicability of set-based algorithms. For instance, given an equihash function that maps all portraits of the same person to the same fingerprint and a collection of portraits, one could determine in constant time if a person is pictured in the collection or count the number of distinct individuals within it in linear time. Most compelling examples require deep learning to train the appropriate equihash function. Ideally, such functions would produce identical fingerprints for equivalent instances and distinct fingerprints for non-equivalent ones. However, learned equihash functions are not ideal, and a significant portion of this thesis addresses the challenges of training, monitoring, and enhancing their performance. Two key metrics are the Relevant-Collision Rate (RCR), which measures the probability that equivalent instances share the same fingerprint, and the Irrelevant-Collision Rate (ICR), which measures the probability that non-equivalent instances share the same fingerprint. When dealing with massive databases, the ICR must be exceptionally low; otherwise, many non-equivalent instances will share the same fingerprint, creating all sorts of problems. Achieving a low ICR presents two challenges: accurately estimating such a low collision rate and effectively training models to meet this stringent criterion. To address the first challenge, we propose the Chebyshev confidence interval, which capitalizes on the birthday paradox to estimate the ICR efficiently. For the second challenge, we introduce the challenge-starvation hypothesis, which identifies a potential limitation in all existing contrastive learning approaches that could impede their capacity to achieve a low ICR. To overcome this, we present the Shannon-Hamming loss, a novel training strategy that focuses exclusively on positive signals. The Shannon-Hamming loss improves the ICR by an order of magnitude compared to its contrastive predecessors. Additionally, a learned equihash function should ideally exhibit a high RCR. However, considering that gradient descent is incompatible with the discrete nature of the fingerprint and that we need to balance the RCR with an exceptionally low ICR, the learned models may sometimes assign distinct fingerprints to equivalent instances. To address this, we propose the prioritized multi-probing algorithm that exploits the model’s uncertainty to generate multiple fingerprints per instance. This technique can be used to enhance the detection rate of distorted re-uploads in our earlier example. Our experiments with a database of one billion images demonstrated the viability and potential of our research.