Learning equivalence hash functions
Identification
- Clé publique
- radar:r-4862bdaa90209488b8a849264e1386f5
- Auteurs
- Duchesneau, Mathieu
- Année déclarée
- 2025
- Langue déclarée
- en
- Type source
- Dissertation
- Première détection
- 2026-11-13T08:39:50.562691+00:00
- Dernière observation des métadonnées
- 2026-11-13T08:39:50.562691+00:00
- Dernière vérification HTTP
- Non effectuée
Résumé documentaire — langue originale
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.
Identifiants
- DOI
- 10.71781/11085
- URI
- https://hdl.handle.net/1866/40944
Repères documentaires
- Famille documentaire
- Thèse
- Types déclarés par les sources
- Dissertation
- Éditeurs
- Université de Montréal
Les mentions d’entités ne constituent pas une preuve de reconnaissance juridique. La juridiction étudiée est distincte du pays d’affiliation des auteurs.
Sources
DataCite · Document 1
Citer cette référence
Duchesneau, Mathieu. Learning equivalence hash functions. 2025. https://doi.org/10.71781/11085
JSON · CSL-JSON · BibTeX · RIS · CSV · JSON-LD ·
APA, Chicago, ISO 690 : formats bibliographiques fondés sur les champs disponibles. OSCOLA / Bluebook : données structurées uniquement ; aucune conformité juridique complète n’est revendiquée sans vérification des éléments nécessaires.
- APA
- Duchesneau, Mathieu. (2025). Learning equivalence hash functions. https://doi.org/10.71781/11085
- Chicago
- Duchesneau, Mathieu. Learning equivalence hash functions. 2025. https://doi.org/10.71781/11085
- ISO 690
- Duchesneau, Mathieu. Learning equivalence hash functions. 2025. https://doi.org/10.71781/11085
Warning: Undefined array key "last_link_verified" in /home/clients/e27d81e12f04d2bfd747aa264540ac56/sites/_UDTR_APP/legal_library_reference.php on line 31
UDTR — Bibliothèque juridique mondiale des droits de la Nature. Learning equivalence hash functions. Notice documentaire: https://www.declarationuniverselledesdroitsdelarbre.org/global-rights-of-nature-radar/reference/r-4862bdaa90209488b8a849264e1386f5/ · Dernière vérification HTTP : non effectuée
Données de cette version figée
Dossiers et relations documentaires
Rôles des sources
Source bibliographique / publication d’origine · https://umontreal.scholaris.ca/handle/1866/40944
Un lien vers une autorité ne prouve pas à lui seul une affirmation juridique. Les résumés et les textes intégraux restent soumis aux conditions de leur source.
Statut documentaire
Pertinence à examiner
Bibliothèque
Cette identité n’est pas encore intégrée à la Bibliothèque juridique.