Nested Barycentric Coordinate System as an Explicit Feature Map
Lee-Ad Gottlieb, Eran Kaufman, Aryeh Kontorovich, Gabriel Nivasch, Ofir Pele
Abstract
We introduce a new embedding technique based on barycentric coordinate system. We show that our embedding can be used to transforms the problem of polytope approximation into that of finding a linear classifier in a higher (but nevertheless quite sparse) dimensional representation. This embedding in effect maps a piecewise linear function into a single linear function, and allows us to invoke well-known algorithms for the latter problem to solve the former. We demonstrate that our embedding has applications to the problems of approximating separating polytopes – in fact, it can approximate any convex body and multiple convex bodies – as well as to classification by separating polytopes and piecewise linear regression.
BibTeX
@InProceedings{pmlr-v130-gottlieb21a,
title = { Nested Barycentric Coordinate System as an Explicit Feature Map },
author = {Gottlieb, Lee-Ad and Kaufman, Eran and Kontorovich, Aryeh and Nivasch, Gabriel and Pele, Ofir},
booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics},
pages = {766--774},
year = {2021},
editor = {Banerjee, Arindam and Fukumizu, Kenji},
volume = {130},
series = {Proceedings of Machine Learning Research},
month = {13--15 Apr},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v130/gottlieb21a/gottlieb21a.pdf},
url = {https://proceedings.mlr.press/v130/gottlieb21a.html},
abstract = { We introduce a new embedding technique based on barycentric coordinate system. We show that our embedding can be used to transforms the problem of polytope approximation into that of finding a linear classifier in a higher (but nevertheless quite sparse) dimensional representation. This embedding in effect maps a piecewise linear function into a single linear function, and allows us to invoke well-known algorithms for the latter problem to solve the former. We demonstrate that our embedding has applications to the problems of approximating separating polytopes – in fact, it can approximate any convex body and multiple convex bodies – as well as to classification by separating polytopes and piecewise linear regression. }
}