Learning Low Density Separators

Shai Ben-David, Tyler Lu, David Pal, Miroslava Sotakova
; Proceedings of the Twelth 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 = {Shai Ben-David and Tyler Lu and David Pal and Miroslava Sotakova}, booktitle = {Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics}, pages = {25--32}, year = {2009}, editor = {David van Dyk and Max Welling}, 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 = {http://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 Twelth 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 %J Proceedings of Machine Learning Research %P 25--32 %U http://proceedings.mlr.press %V 5 %W PMLR %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 Twelth International Conference on Artificial Intelligence and Statistics PY - 2009/04/15 DA - 2009/04/15 ED - David van Dyk ED - Max Welling ID - pmlr-v5-ben-david09a PB - PMLR SP - 25 DP - PMLR EP - 32 L1 - http://proceedings.mlr.press/v5/ben-david09a/ben-david09a.pdf UR - http://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 Twelth International Conference on Artificial Intelligence and Statistics, in PMLR 5:25-32

Related Material