Vanishing Component Analysis

Roi Livni, David Lehavi, Sagi Schein, Hila Nachliely, Shai Shalev-Shwartz, Amir Globerson
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(1):597-605, 2013.

Abstract

The vanishing ideal of a set of n points S, is the set of all polynomials that attain the value of zero on all the points in S. Such ideals can be compactly represented using a small set of polynomials known as generators of the ideal. Here we describe and analyze an efficient procedure that constructs a set of generators of a vanishing ideal. Our procedure is numerically stable, and can be used to find approximately vanishing polynomials. The resulting polynomials capture nonlinear structure in data, and can for example be used within supervised learning. Empirical comparison with kernel methods show that our method constructs more compact classifiers with comparable accuracy.

Cite this Paper


BibTeX
@InProceedings{pmlr-v28-livni13, title = {Vanishing Component Analysis}, author = {Livni, Roi and Lehavi, David and Schein, Sagi and Nachliely, Hila and Shalev-Shwartz, Shai and Globerson, Amir}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {597--605}, 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/livni13.pdf}, url = {https://proceedings.mlr.press/v28/livni13.html}, abstract = {The vanishing ideal of a set of n points S, is the set of all polynomials that attain the value of zero on all the points in S. Such ideals can be compactly represented using a small set of polynomials known as generators of the ideal. Here we describe and analyze an efficient procedure that constructs a set of generators of a vanishing ideal. Our procedure is numerically stable, and can be used to find approximately vanishing polynomials. The resulting polynomials capture nonlinear structure in data, and can for example be used within supervised learning. Empirical comparison with kernel methods show that our method constructs more compact classifiers with comparable accuracy. } }
Endnote
%0 Conference Paper %T Vanishing Component Analysis %A Roi Livni %A David Lehavi %A Sagi Schein %A Hila Nachliely %A Shai Shalev-Shwartz %A Amir Globerson %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-livni13 %I PMLR %P 597--605 %U https://proceedings.mlr.press/v28/livni13.html %V 28 %N 1 %X The vanishing ideal of a set of n points S, is the set of all polynomials that attain the value of zero on all the points in S. Such ideals can be compactly represented using a small set of polynomials known as generators of the ideal. Here we describe and analyze an efficient procedure that constructs a set of generators of a vanishing ideal. Our procedure is numerically stable, and can be used to find approximately vanishing polynomials. The resulting polynomials capture nonlinear structure in data, and can for example be used within supervised learning. Empirical comparison with kernel methods show that our method constructs more compact classifiers with comparable accuracy.
RIS
TY - CPAPER TI - Vanishing Component Analysis AU - Roi Livni AU - David Lehavi AU - Sagi Schein AU - Hila Nachliely AU - Shai Shalev-Shwartz AU - Amir Globerson BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/02/13 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-livni13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 1 SP - 597 EP - 605 L1 - http://proceedings.mlr.press/v28/livni13.pdf UR - https://proceedings.mlr.press/v28/livni13.html AB - The vanishing ideal of a set of n points S, is the set of all polynomials that attain the value of zero on all the points in S. Such ideals can be compactly represented using a small set of polynomials known as generators of the ideal. Here we describe and analyze an efficient procedure that constructs a set of generators of a vanishing ideal. Our procedure is numerically stable, and can be used to find approximately vanishing polynomials. The resulting polynomials capture nonlinear structure in data, and can for example be used within supervised learning. Empirical comparison with kernel methods show that our method constructs more compact classifiers with comparable accuracy. ER -
APA
Livni, R., Lehavi, D., Schein, S., Nachliely, H., Shalev-Shwartz, S. & Globerson, A.. (2013). Vanishing Component Analysis. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(1):597-605 Available from https://proceedings.mlr.press/v28/livni13.html.

Related Material