The Pairwise Piecewise-Linear Embedding for Efficient Non-Linear Classification

Ofir Pele, Ben Taskar, Amir Globerson, Michael Werman
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(1):205-213, 2013.

Abstract

Linear classiffers are much faster to learn and test than non-linear ones. On the other hand, non-linear kernels offer improved performance, albeit at the increased cost of training kernel classiffers. To use non-linear mappings with efficient linear learning algorithms, explicit embeddings that approximate popular kernels have recently been proposed. However, the embedding process itself is often costly and the results are usually less accurate than kernel methods. In this work we propose a non-linear feature map that is both very efficient, but at the same time highly expressive. The method is based on discretization and interpolation of individual features values and feature pairs. The discretization allows us to model different regions of the feature space separately, while the interpolation preserves the original continuous values. Using this embedding is strictly more general than a linear model and as efficient as the second-order polynomial explicit feature map. An extensive empirical evaluation shows that our method consistently signiffcantly outperforms other methods, including a wide range of kernels. This is in contrast to other proposed embeddings that were faster than kernel methods, but with lower accuracy.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-pele13, title = {The Pairwise Piecewise-Linear Embedding for Efficient Non-Linear Classification}, author = {Pele, Ofir and Taskar, Ben and Globerson, Amir and Werman, Michael}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {205--213}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {1}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/pele13.pdf}, url = {https://proceedings.mlr.press/v28/pele13.html}, abstract = {Linear classiffers are much faster to learn and test than non-linear ones. On the other hand, non-linear kernels offer improved performance, albeit at the increased cost of training kernel classiffers. To use non-linear mappings with efficient linear learning algorithms, explicit embeddings that approximate popular kernels have recently been proposed. However, the embedding process itself is often costly and the results are usually less accurate than kernel methods. In this work we propose a non-linear feature map that is both very efficient, but at the same time highly expressive. The method is based on discretization and interpolation of individual features values and feature pairs. The discretization allows us to model different regions of the feature space separately, while the interpolation preserves the original continuous values. Using this embedding is strictly more general than a linear model and as efficient as the second-order polynomial explicit feature map. An extensive empirical evaluation shows that our method consistently signiffcantly outperforms other methods, including a wide range of kernels. This is in contrast to other proposed embeddings that were faster than kernel methods, but with lower accuracy.} }
Endnote
%0 Conference Paper %T The Pairwise Piecewise-Linear Embedding for Efficient Non-Linear Classification %A Ofir Pele %A Ben Taskar %A Amir Globerson %A Michael Werman %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-pele13 %I PMLR %P 205--213 %U https://proceedings.mlr.press/v28/pele13.html %V 28 %N 1 %X Linear classiffers are much faster to learn and test than non-linear ones. On the other hand, non-linear kernels offer improved performance, albeit at the increased cost of training kernel classiffers. To use non-linear mappings with efficient linear learning algorithms, explicit embeddings that approximate popular kernels have recently been proposed. However, the embedding process itself is often costly and the results are usually less accurate than kernel methods. In this work we propose a non-linear feature map that is both very efficient, but at the same time highly expressive. The method is based on discretization and interpolation of individual features values and feature pairs. The discretization allows us to model different regions of the feature space separately, while the interpolation preserves the original continuous values. Using this embedding is strictly more general than a linear model and as efficient as the second-order polynomial explicit feature map. An extensive empirical evaluation shows that our method consistently signiffcantly outperforms other methods, including a wide range of kernels. This is in contrast to other proposed embeddings that were faster than kernel methods, but with lower accuracy.
RIS
TY - CPAPER TI - The Pairwise Piecewise-Linear Embedding for Efficient Non-Linear Classification AU - Ofir Pele AU - Ben Taskar AU - Amir Globerson AU - Michael Werman BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/02/13 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-pele13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 1 SP - 205 EP - 213 L1 - http://proceedings.mlr.press/v28/pele13.pdf UR - https://proceedings.mlr.press/v28/pele13.html AB - Linear classiffers are much faster to learn and test than non-linear ones. On the other hand, non-linear kernels offer improved performance, albeit at the increased cost of training kernel classiffers. To use non-linear mappings with efficient linear learning algorithms, explicit embeddings that approximate popular kernels have recently been proposed. However, the embedding process itself is often costly and the results are usually less accurate than kernel methods. In this work we propose a non-linear feature map that is both very efficient, but at the same time highly expressive. The method is based on discretization and interpolation of individual features values and feature pairs. The discretization allows us to model different regions of the feature space separately, while the interpolation preserves the original continuous values. Using this embedding is strictly more general than a linear model and as efficient as the second-order polynomial explicit feature map. An extensive empirical evaluation shows that our method consistently signiffcantly outperforms other methods, including a wide range of kernels. This is in contrast to other proposed embeddings that were faster than kernel methods, but with lower accuracy. ER -
APA
Pele, O., Taskar, B., Globerson, A. & Werman, M.. (2013). The Pairwise Piecewise-Linear Embedding for Efficient Non-Linear Classification. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(1):205-213 Available from https://proceedings.mlr.press/v28/pele13.html.

Related Material