Hash-SVM: Skalierbare Kernelmaschinen für die großangelegte visuelle Klassifizierung

In diesem Papier wird ein neuartiger Algorithmus vorgestellt, der kompakte Hash-Bits verwendet, um die Effizienz von nichtlinearen Kernel-SVM bei sehr großangelegten visuellen Klassifizierungsproblemen erheblich zu verbessern. Unsere zentrale Idee besteht darin, jede Probe mit kompakten Hash-Bits darzustellen, über die ein inneres Produkt definiert ist, das als Ersatz für die ursprünglichen nichtlinearen Kerne dient. Dann kann das Problem der Lösung der nichtlinearen SVM in das Lösen einer linearen SVM über die Hash-Bits umgewandelt werden. Die vorgeschlagene Hash-SVM profitiert von dramatischen Einsparungen bei den Speicherkosten aufgrund der kompakten binären Darstellung sowie von einer (unter-)linearen Trainingskomplexität über die lineare SVM. Als kritische Komponente der Hash-SVM schlagen wir ein neuartiges Hashing-Schema für beliebige nichtlineare Kerne durch zufällige Unterraumprojektion im reproduzierenden Kern-Hilbertraum vor. Unsere umfassende Analyse zeigt eine gut definierte theoretische Schranke der Abweichung zwischen der vorgeschlagenen hashing-basierten Kernel-Approximation und der ursprünglichen Kernfunktion. Wir leiten auch Anforderungen an die Hash-Bits ab, um ein zufriedenstellendes Genauigkeitsniveau zu erreichen. Es werden mehrere Experimente an großangelegten visuellen Klassifizierungsbenchmarks durchgeführt, darunter eines mit über 1 Million Bildern. Die Ergebnisse zeigen, dass Hash-SVM die rechnerische Komplexität erheblich reduziert (in vielen Fällen mehr als zehnmal schneller), während vergleichbare Genauigkeiten beibehalten werden.