Cargando…
Hashing Based Prediction for Large-Scale Kernel Machine
Kernel Machines, such as Kernel Ridge Regression, provide an effective way to construct non-linear, nonparametric models by projecting data into high-dimensional space and play an important role in machine learning. However, when dealing with large-scale problems, high computational cost in the pred...
Autores principales: | , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
2020
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7302813/ http://dx.doi.org/10.1007/978-3-030-50417-5_37 |
Sumario: | Kernel Machines, such as Kernel Ridge Regression, provide an effective way to construct non-linear, nonparametric models by projecting data into high-dimensional space and play an important role in machine learning. However, when dealing with large-scale problems, high computational cost in the prediction stage limits their use in real-world applications. In this paper, we propose hashing based prediction, a fast kernel prediction algorithm leveraging hash technique. The algorithm samples a small subset from the input dataset through the locality-sensitive hashing method and computes prediction value approximately using the subset. Hashing based prediction has the minimum time complexity compared to the state-of-art kernel machine prediction approaches. We further present a theoretical analysis of the proposed algorithm showing that it can keep comparable accuracy. Experiment results on most commonly used large-scale datasets, even with million-level data points, show that the proposed algorithm outperforms the state-of-art kernel prediction methods in time cost while maintaining satisfactory accuracy. |
---|