Learning Low Density Separators

Shai Ben-David, Tyler Lu, David Pal, Miroslava Sotakova
Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, PMLR 5:25-32, 2009.

Abstract

We define a novel, basic, unsupervised learning problem - learning the lowest density homogeneous hyperplane separator of an unknown probability distribution. This task is relevant to several problems in machine learning, such as semi-supervised learning and clustering stability. We investigate the question of existence of a universally consistent algorithm for this problem. We propose two natural learning paradigms and prove that, on input unlabeled random samples generated by any member of a rich family of distributions, they are guaranteed to converge to the optimal separator for that distribution. We complement this result by showing that no learning algorithm for our task can achieve uniform learning rates (that are independent of the data generating distribution).

Cite this Paper

BibTeX
@InProceedings{pmlr-v5-ben-david09a, title = {Learning Low Density Separators}, author = {Ben-David, Shai and Lu, Tyler and Pal, David and Sotakova, Miroslava}, booktitle = {Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics}, pages = {25--32}, year = {2009}, editor = {van Dyk, David and Welling, Max}, volume = {5}, series = {Proceedings of Machine Learning Research}, address = {Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v5/ben-david09a/ben-david09a.pdf}, url = {https://proceedings.mlr.press/v5/ben-david09a.html}, abstract = {We define a novel, basic, unsupervised learning problem - learning the lowest density homogeneous hyperplane separator of an unknown probability distribution. This task is relevant to several problems in machine learning, such as semi-supervised learning and clustering stability. We investigate the question of existence of a universally consistent algorithm for this problem. We propose two natural learning paradigms and prove that, on input unlabeled random samples generated by any member of a rich family of distributions, they are guaranteed to converge to the optimal separator for that distribution. We complement this result by showing that no learning algorithm for our task can achieve uniform learning rates (that are independent of the data generating distribution).} }
Endnote
%0 Conference Paper %T Learning Low Density Separators %A Shai Ben-David %A Tyler Lu %A David Pal %A Miroslava Sotakova %B Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2009 %E David van Dyk %E Max Welling %F pmlr-v5-ben-david09a %I PMLR %P 25--32 %U https://proceedings.mlr.press/v5/ben-david09a.html %V 5 %X We define a novel, basic, unsupervised learning problem - learning the lowest density homogeneous hyperplane separator of an unknown probability distribution. This task is relevant to several problems in machine learning, such as semi-supervised learning and clustering stability. We investigate the question of existence of a universally consistent algorithm for this problem. We propose two natural learning paradigms and prove that, on input unlabeled random samples generated by any member of a rich family of distributions, they are guaranteed to converge to the optimal separator for that distribution. We complement this result by showing that no learning algorithm for our task can achieve uniform learning rates (that are independent of the data generating distribution).
RIS
TY - CPAPER TI - Learning Low Density Separators AU - Shai Ben-David AU - Tyler Lu AU - David Pal AU - Miroslava Sotakova BT - Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics DA - 2009/04/15 ED - David van Dyk ED - Max Welling ID - pmlr-v5-ben-david09a PB - PMLR DP - Proceedings of Machine Learning Research VL - 5 SP - 25 EP - 32 L1 - http://proceedings.mlr.press/v5/ben-david09a/ben-david09a.pdf UR - https://proceedings.mlr.press/v5/ben-david09a.html AB - We define a novel, basic, unsupervised learning problem - learning the lowest density homogeneous hyperplane separator of an unknown probability distribution. This task is relevant to several problems in machine learning, such as semi-supervised learning and clustering stability. We investigate the question of existence of a universally consistent algorithm for this problem. We propose two natural learning paradigms and prove that, on input unlabeled random samples generated by any member of a rich family of distributions, they are guaranteed to converge to the optimal separator for that distribution. We complement this result by showing that no learning algorithm for our task can achieve uniform learning rates (that are independent of the data generating distribution). ER -
APA
Ben-David, S., Lu, T., Pal, D. & Sotakova, M.. (2009). Learning Low Density Separators. Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 5:25-32 Available from https://proceedings.mlr.press/v5/ben-david09a.html.

Related Material