Schwach überwachte Hashing im Kernbereich

Das explosive Wachstum der Vision-Daten motiviert die aktuellen Studien zu effizienten Datenindexierungsverfahren wie dem lokalitäts-sensitiven Hashing (LSH). Die meisten bestehenden Ansätze führen das Hashing auf unüberwachte Weise durch. In diesem Papier machen wir einen Schritt nach vorne und schlagen ein überwachtes Hashing-Verfahren vor, nämlich den LAbel-regulierten Max-Margin Partition (LAMP) Algorithmus. Die vorgeschlagene Methode erzeugt Hash-Funktionen in einem schwach überwachten Umfeld, in dem ein kleiner Teil von Stichprobenpaaren manuell als "ähnlich" oder "unähnlich" gekennzeichnet wird. Wir formulieren die Aufgabe als ein Constrained Convex-Concave Procedure (CCCP), welches in eine Reihe von konvexen Teilproblemen entspannt werden kann, die effizient mit Quadratic-Program (QP) lösbar sind. Die vorgeschlagene Hashing-Methode besitzt weitere Merkmale einschließlich: 1) die meisten bestehenden LSH-Ansätze stützen sich auf lineare Merkmalsdarstellung. Leider sind Kerntricks oft natürlicher, um die Ähnlichkeit zwischen visuellen Objekten in der Vision Forschung zu messen, was wahrscheinlich unendlichen-dimensionalen Hilberträumen entspricht. Der vorgeschlagene LAMP unterstützt natürlich die kernel-basierte Merkmalsdarstellung. 2) traditionelle Hashing-Methoden nehmen ein einheitliches Datenverteilungsmuster an. Typischerweise wird die Kollisionswahrscheinlichkeit von zwei Stichproben in Hash-Eimern nur durch paarweise Ähnlichkeit bestimmt, die nicht mit der kontextuellen Datenverteilung zusammenhängt. Im Gegensatz dazu bieten wir eine solche Kollisionsgrenze, die über den paarweisen Dateninteraktionen auf Basis der Markov-Randfelder-Theorie hinausgeht. Umfassende empirische Bewertungen werden an fünf weit verbreiteten Benchmarks durchgeführt. Es dauert nur einige Sekunden, um eine neue Hashing-Funktion zu generieren, und das verwendete Zufalls-Unterstützungsvektor-Schema ermöglicht es dem LAMP-Algorithmus, auf groß angelegte Probleme skalierbar zu sein. Experimentelle Ergebnisse bestätigen eindeutig die Überlegenheit des LAMP-Algorithmus gegenüber den modernsten kernel-basierten Hashing-Methoden.