Locality Sensitive Hashing (LSH)–een schaalbare oplossing voor het dedupliceren van taken uit meerdere bronnen
terug naar het onderwerp — Waarom is deduplicatie belangrijk?
we gebruiken een enorm corpus van vacatures van Kalibrr gecombineerd met gedolven vacatures van verschillende openbare vacatures om ons model te trainen. Het hebben van meerdere banen in ons corpus met vergelijkbare functiebeschrijvingen zal nadelig zijn voor het model. Voorbeeld hiervan wordt weergegeven in de afbeelding hieronder.
Duplicate job descriptions associated to varying positions can affect the model’s performance in distinguishing context between different job titles. Aangezien diep het leren, en in het algemeen machine het leren, modellen worden opgeleid om een functie te leren die een reeks eigenschappen aan categorieën in kaart brengt of een doel optimaliseert, die input hebben die gelijkaardig zijn maar aan verschillende doelstellingen worden geassocieerd zal zeker het vertrouwen en de prestaties van het model beà nvloeden.
naast het probleem van voorspellende prestaties zal het trainen van een model met een groot corpus waarin de meeste gegevens duplicaten zijn, onnodige rekenmiddelen verbruiken.
Dit is een illustratie van hoe inzicht in de gegevens gemakkelijk de prestaties van het model kan beïnvloeden.
Tf-Idf-een eenvoudig deduplicatiealgoritme
het detecteren van duplicaten kan op verschillende manieren worden gedaan. Het weergeven van documenten in eenvoudige vectorvoorstellingen zoals tf-idf kan een redelijke methode zijn voor het ontdekken van bijna-soortgelijke documenten. Dit kan worden gedaan door vergelijking van gelijkenis metrics zoals cosinus of Euclidische gelijkenis tussen document vectoren.
we laten in het volgende fragment zien hoe we het algoritme kunnen toepassen om bijna identieke teksten te identificeren.
hoewel deze methode werkt in kleine corpora, is dit vrij moeilijk te schalen vanwege de resulterende dimensionaliteit van de vectoren na het transformeren van de documenten. Merk ook op dat het 319 ms nodig had voor het script om de hele pijplijn te draaien. Dit is een van de vele manifestaties van de “vloek van dimensionaliteit” — hoge dimensionaliteit van de transformatie beïnvloedt zowel de ruimte als de tijd complexiteit van de analyse.
local Sensitive Hashing (LSH) — de schaalbare techniek
een oplossing voor dit probleem is local Sensitive Hashing (LSH). De LSH methode kan bijna-gelijkenis analyse uitvoeren op enorme datasets. Het maakt gebruik van hashing om documenten in emmers in kaart te brengen met dimensionaliteit die ordes van grootte lager is dan een gelijkwaardige TF-idf transformatie. Deze eigenschap maakt LSH gemakkelijk te gebruiken in grootschalige toepassingen zoals text mining.
LSH gebruikt het minhash algoritme om de kans op botsingen te berekenen. Er is aangetoond dat de kans op botsingen in LSH met minhash gelijk is aan de Jaccard similarity metric. In het kort, Jaccard gelijkenis berekent de snijpunt van twee verzamelingen gedeeld door de Vereniging van de elementen in elke verzameling. De formule waarvan hieronder wordt weergegeven.
de Jaccard gelijkenis kwantificeert het volgende idee — twee groepen met meer gemeenschappelijke items zijn waarschijnlijk vergelijkbaar.
Hier is een fragment over LSH volgens wikipedia:
Locality-sensitive hashing (LSH) vermindert de dimensionaliteit van hoogdimensionale data. LSH hashes input items zodat soortgelijke items kaart naar dezelfde “emmers” met grote waarschijnlijkheid (het aantal emmers is veel kleiner dan het universum van mogelijke input items). LSH verschilt van conventionele en cryptografische hash functies omdat het gericht is op het maximaliseren van de kans op een “botsing” voor soortgelijke items. Locality-sensitive hashing heeft veel gemeen met data clustering en dichtstbijzijnde buur zoeken.
LSH op het werk
We tonen hieronder een implementatie van LSH, met behulp van deze module, toegepast op hetzelfde voorbeeld hierboven geïllustreerd.
de resultaten laten zien dat de volledige pijplijn ongeveer 4x sneller is dan de tf-Idf versie. Dit verschil is drastischer zodra een grotere dataset wordt gebruikt. We hebben de analyse van geheugenprestaties nu uitgesloten, maar we zullen een uitgebreidere benchmark tussen de twee methoden in een aparte post schrijven.
we hebben LSH toegepast op ons corpus en we hebben gezien dat sommige vacatureberichten met bijna vergelijkbare inhoud meer dan 200 keer verschijnen!
Final thoughts
terwijl Tf-Idf populairder is en een meer vertrouwd model voor het werken met tekstvergelijkingen; als het omgaan met datasets die schaalbaar zijn, is LSH een handiger model. Zelfs voor kleinere datasets biedt LSH een aanzienlijke verbetering in computationele tijd.
in staat zijn om een corpus correct te dedupliceren vermindert ruis in de trainingsgegevens, bespaart computationele middelen, en helpt bij het leren van een nauwkeuriger model voor onze use case.
wij geloven dat er veel problemen zijn waarop LSH kan worden toegepast, zoals:
- image cleanup dupliceren: LSH toepassen op afbeeldingseigenschappen en alleen een unieke afbeelding uit elke bin behouden.
- Chatbots: identificeer in de buurt van soortgelijke ingangen en train een model om de beste respons van de kennisbasis te identificeren.
- Recommendations engine: groepeer items met bijna vergelijkbare functies en ondersteun items aan gebruikers.
voel je vrij om te verkennen en probeer LSH om uw eigen problemen! 🙂
referenties op LSH
Deze artikelen illustreren heel goed hoe LSH werkt en laten ook voorbeelden zien.
Hier is een cursus over het ontginnen van enorme datasets die LSH bespreekt.
Volg ons!
We publiceren voortdurend artikelen over Machine Learning, Deep Learning, NLP, probabilistische programmering en Analytics projecten die we doen bij Kalibrr Research. Volg ons om een melding te krijgen op onze volgende berichten! 🙂