Compact Random Feature Maps

Raffay Hamid, Ying Xiao, Alex Gittens, Dennis Decoste
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):19-27, 2014.

Abstract

Kernel approximation using randomized feature maps has recently gained a lot of interest. In this work, we identify that previous approaches for polynomial kernel approximation create maps that are rank deficient, and therefore do not utilize the capacity of the projected feature space effectively. To address this challenge, we propose compact random feature maps (CRAFTMaps) to approximate polynomial kernels more concisely and accurately. We prove the error bounds of CRAFTMaps demonstrating their superior kernel reconstruction performance compared to the previous approximation schemes. We show how structured random matrices can be used to efficiently generate CRAFTMaps, and present a single-pass algorithm using CRAFTMaps to learn non-linear multi-class classifiers. We present experiments on multiple standard data-sets with performance competitive with state-of-the-art results.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-hamid14, title = {Compact Random Feature Maps}, author = {Hamid, Raffay and Xiao, Ying and Gittens, Alex and Decoste, Dennis}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {19--27}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/hamid14.pdf}, url = {https://proceedings.mlr.press/v32/hamid14.html}, abstract = {Kernel approximation using randomized feature maps has recently gained a lot of interest. In this work, we identify that previous approaches for polynomial kernel approximation create maps that are rank deficient, and therefore do not utilize the capacity of the projected feature space effectively. To address this challenge, we propose compact random feature maps (CRAFTMaps) to approximate polynomial kernels more concisely and accurately. We prove the error bounds of CRAFTMaps demonstrating their superior kernel reconstruction performance compared to the previous approximation schemes. We show how structured random matrices can be used to efficiently generate CRAFTMaps, and present a single-pass algorithm using CRAFTMaps to learn non-linear multi-class classifiers. We present experiments on multiple standard data-sets with performance competitive with state-of-the-art results.} }
Endnote
%0 Conference Paper %T Compact Random Feature Maps %A Raffay Hamid %A Ying Xiao %A Alex Gittens %A Dennis Decoste %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-hamid14 %I PMLR %P 19--27 %U https://proceedings.mlr.press/v32/hamid14.html %V 32 %N 2 %X Kernel approximation using randomized feature maps has recently gained a lot of interest. In this work, we identify that previous approaches for polynomial kernel approximation create maps that are rank deficient, and therefore do not utilize the capacity of the projected feature space effectively. To address this challenge, we propose compact random feature maps (CRAFTMaps) to approximate polynomial kernels more concisely and accurately. We prove the error bounds of CRAFTMaps demonstrating their superior kernel reconstruction performance compared to the previous approximation schemes. We show how structured random matrices can be used to efficiently generate CRAFTMaps, and present a single-pass algorithm using CRAFTMaps to learn non-linear multi-class classifiers. We present experiments on multiple standard data-sets with performance competitive with state-of-the-art results.
RIS
TY - CPAPER TI - Compact Random Feature Maps AU - Raffay Hamid AU - Ying Xiao AU - Alex Gittens AU - Dennis Decoste BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/06/18 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-hamid14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 2 SP - 19 EP - 27 L1 - http://proceedings.mlr.press/v32/hamid14.pdf UR - https://proceedings.mlr.press/v32/hamid14.html AB - Kernel approximation using randomized feature maps has recently gained a lot of interest. In this work, we identify that previous approaches for polynomial kernel approximation create maps that are rank deficient, and therefore do not utilize the capacity of the projected feature space effectively. To address this challenge, we propose compact random feature maps (CRAFTMaps) to approximate polynomial kernels more concisely and accurately. We prove the error bounds of CRAFTMaps demonstrating their superior kernel reconstruction performance compared to the previous approximation schemes. We show how structured random matrices can be used to efficiently generate CRAFTMaps, and present a single-pass algorithm using CRAFTMaps to learn non-linear multi-class classifiers. We present experiments on multiple standard data-sets with performance competitive with state-of-the-art results. ER -
APA
Hamid, R., Xiao, Y., Gittens, A. & Decoste, D.. (2014). Compact Random Feature Maps. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(2):19-27 Available from https://proceedings.mlr.press/v32/hamid14.html.

Related Material