Feature-Hashing, auch als Hashing-Trick bekannt, ist eine Technik im maschinellen Lernen, um hochdimensionale, spärliche kategoriale Merkmale in eine kompakte Vektorrepräsentation fester Größe umzuwandeln. Es wendet eine Hash-Funktion auf jeden Merkmalsnamen (oder jedes Token) an, um dessen Index im Ausgabevektor zu bestimmen, und optional eine zweite Hash-Funktion, um das Vorzeichen des Beitrags festzulegen. Diese Methode vermeidet die Notwendigkeit, ein separates Merkmalswörterbuch zu führen, reduziert den Speicher- und Rechenaufwand, auf Kosten von Hash-Kollisionen, die die Modellleistung geringfügig beeinträchtigen können.
Die Technik ist besonders nützlich für Lernaufgaben in großem Maßstab, wie Online-Werbung, Textklassifikation und Empfehlungssysteme, bei denen die Anzahl der eindeutigen Merkmale in die Millionen oder Milliarden gehen kann. Durch die Abbildung von Merkmalen in einen Raum von beispielsweise 10.000 bis 1 Million Dimensionen ermöglicht Feature-Hashing ein effizientes Training mit linearen Modellen oder neuronalen Netzen, oft mit vernachlässigbarem Genauigkeitsverlust.
Geschichte und Ursprünge
Das Konzept des Feature-Hashings hat seine Wurzeln in den frühen 2000er Jahren, mit unabhängigen Entwicklungen in der Verarbeitung natürlicher Sprache und Kernel-Methoden. Eine der frühesten veröffentlichten Anwendungen stammt von John Langford und Kollegen aus dem Jahr 2007, die es für großangelegtes Lernen zur Spam-Erkennung einsetzten. Die Technik erlangte nach dem Papier „Feature Hashing for Large Scale Multitask Learning“ von Kilian Weinberger und Kollegen aus dem Jahr 2009 breitere Anerkennung, das den Ansatz formalisierte und seine Wirksamkeit bei mehreren Aufgaben demonstrierte.
Zuvor tauchten ähnliche Ideen im Kontext von Hashing für Kernel-Approximationen auf, wie etwa die Arbeit zu zufälligen Merkmalen von Ali Rahimi und Benjamin Recht aus dem Jahr 2007. Feature-Hashing ist auch eng mit dem „Hashing-Trick“ verwandt, der im Vowpal-Wabbit-Lernsystem verwendet wird, das Langford bei Yahoo! Research entwickelte.
Funktionsweise
Feature-Hashing funktioniert in zwei Hauptschritten. Zuerst wird jeder Merkmalsname (z. B. ein Wort oder ein kategorialer Wert) durch eine Hash-Funktion, typischerweise ein 32-Bit- oder 64-Bit-Hash, geleitet, um eine ganze Zahl zu erzeugen. Diese ganze Zahl wird dann modulo der gewünschten Ausgabedimension reduziert, was den Index ergibt, an dem der Wert des Merkmals (oft 1 für das Vorhandensein) akkumuliert wird. Um die Verzerrung durch Kollisionen zu reduzieren, bestimmt eine zweite Hash-Funktion das Vorzeichen (+1 oder -1) des Beitrags, sodass sich Kollisionen im Durchschnitt tendenziell aufheben.
Zum Beispiel wird bei der Textklassifikation jedes Wort in einem Dokument auf einen Index in einem Vektor der Größe von beispielsweise 100.000 gehasht. Der Vektor wird dann als Eingabe für einen linearen Klassifikator oder ein neuronales Netz verwendet. Da die Hash-Funktion deterministisch ist, wird dasselbe Merkmal immer auf denselben Index abgebildet, was eine Konsistenz zwischen Training und Inferenz gewährleistet.
Der Hauptvorteil besteht darin, dass kein Merkmalswörterbuch gespeichert werden muss, was entscheidend ist, wenn der Merkmalsraum zu groß ist, um in den Speicher zu passen. Es können jedoch Kollisionen auftreten, bei denen verschiedene Merkmale auf denselben Index abgebildet werden, was möglicherweise zu Interferenzen führt. Die Auswirkung ist in der Regel gering, wenn die Ausgabedimension im Verhältnis zur Anzahl der Merkmale ausreichend groß ist.
Anwendungen im maschinellen Lernen
Feature-Hashing wird häufig in großangelegten Systemen des maschinellen Lernens verwendet, insbesondere im Kontext von Online-Lernen und verteiltem Rechnen. Es ist eine Kernkomponente der Vowpal-Wabbit-Bibliothek, die zur Vorhersage der Klickrate in der Werbung verwendet wird. Es wird auch in der Verarbeitung natürlicher Sprache für Bag-of-Words-Repräsentationen eingesetzt, bei denen jedes Dokument in einen gehashten Vektor umgewandelt wird, was ein effizientes Training von Klassifikatoren auf massiven Textkorpora ermöglicht.
In Empfehlungssystemen kann Feature-Hashing Benutzer- und Artikel-IDs sowie kontextuelle Merkmale in eine kompakte Repräsentation kodieren, sodass Modelle Millionen von Benutzern und Artikeln ohne explizite Nachschlagetabellen verarbeiten können. Es wird auch im Feature-Engineering für Gradient-Boosting-Maschinen wie XGBoost und LightGBM verwendet, bei denen kategoriale Merkmale häufig gehasht werden, um den Speicherverbrauch zu reduzieren.
In jüngerer Zeit wurde Feature-Hashing im Deep Learning für Embedding-Schichten angewendet, wo es als Alternative fester Größe zu gelernten Embeddings dienen kann, insbesondere für seltene oder unbekannte Kategorien. Dieser Ansatz wird manchmal als „Hashing-Embeddings“ bezeichnet und kann in Online-Lernszenarien vorteilhaft sein, in denen häufig neue Merkmale auftreten.
Vorteile und Einschränkungen
Der Hauptvorteil von Feature-Hashing ist die Speichereffizienz. Da kein Wörterbuch erforderlich ist, kann das Modell mit Daten trainiert werden, die eine unbegrenzte Anzahl von Merkmalen aufweisen, solange die Hash-Ausgabedimension festgelegt ist. Dies ist besonders nützlich in Streaming- oder verteilten Umgebungen, in denen Merkmale spontan entdeckt werden können.
Ein weiterer Vorteil ist die Einfachheit: Die Implementierung ist unkompliziert und erfordert keine komplexe Vorverarbeitung. Es ermöglicht auch eine einfache Parallelisierung, da jedes Merkmal unabhängig gehasht werden kann.
Feature-Hashing hat jedoch Einschränkungen. Hash-Kollisionen können die Modellgenauigkeit beeinträchtigen, insbesondere wenn die Ausgabedimension zu klein ist. Die Technik verliert auch an Interpretierbarkeit, da es nicht möglich ist, einen gehashten Index ohne Speicherung einer separaten Zuordnung auf den ursprünglichen Merkmalsnamen zurückzuführen, was den Zweck zunichte macht. Darüber hinaus erfordert die Wahl der Hash-Funktion und der Ausgabedimension eine Abstimmung, und es gibt einen Kompromiss zwischen Kollisionsrate und Speicherverbrauch.
Vergleich mit alternativen Methoden
Feature-Hashing wird oft mit anderen Techniken zur Dimensionsreduktion verglichen, wie One-Hot-Kodierung, Label-Kodierung und gelernten Embeddings. One-Hot-Kodierung ist einfach, erfordert jedoch ein Wörterbuch und kann bei Merkmalen mit hoher Kardinalität extrem speicherintensiv sein. Label-Kodierung weist ganzzahlige IDs zu, impliziert jedoch eine willkürliche Reihenfolge, die bei kategorialen Daten irreführend sein kann. Gelernte Embeddings, wie sie in neuronalen Netzen verwendet werden, können semantische Beziehungen erfassen, erfordern jedoch ein Training und einen festen Wortschatz.
Feature-Hashing liegt zwischen diesen Ansätzen: Es ist speichereffizienter als One-Hot-Kodierung, vermeidet das Ordnungsproblem der Label-Kodierung und erfordert weder Training noch einen Wortschatz. Es erfasst jedoch keine Beziehungen zwischen Merkmalen, was Embeddings können.
In der Praxis wird Feature-Hashing oft als Basislinie oder als Fallback verwendet, wenn andere Methoden aufgrund des Maßstabs nicht machbar sind. Es wird auch mit anderen Techniken kombiniert, wie Datenaugmentation oder Modell-Pruning, um die Effizienz in Produktionssystemen zu verbessern.
Neuere Entwicklungen und Forschung
Die Forschung zu Feature-Hashing wird fortgesetzt, insbesondere im Kontext von Deep Learning und großangelegten Systemen. Studien haben die Auswirkung von Hash-Kollisionen auf die Modellleistung analysiert, was zu Richtlinien für die Wahl der Ausgabedimension führte. Einige Arbeiten haben gelernte Hash-Funktionen vorgeschlagen, die sich an die Datenverteilung anpassen und möglicherweise Kollisionen reduzieren.
Im Zeitalter der großen Sprachmodelle ist Feature-Hashing weniger prominent, da diese Modelle typischerweise Tokenisierung und gelernte Embeddings verwenden. Es bleibt jedoch relevant für die Verarbeitung kategorialer Merkmale in tabellarischen Daten und für effizientes Feature-Engineering in Machine-Learning-Pipelines.
Neuere Arbeiten haben auch die Verwendung von Feature-Hashing im föderierten Lernen und in datenschutzerhaltenden Umgebungen untersucht, wo der Hash als eine Form der Merkmalsverschleierung dienen kann. Darüber hinaus können Hardware-Beschleuniger wie AWS Trainium und Google Cloud-TPUs von dem reduzierten Speicherbedarf profitieren, den Feature-Hashing bietet.
Insgesamt ist Feature-Hashing eine ausgereifte Technik, die weiterhin neue Anwendungen in großangelegten und ressourcenbeschränkten Umgebungen findet.