Unsupervised SVMs: On the Complexity of the Furthest Hyperplane Problem

Zohar Karnin, Edo Liberty, Shachar Lovett, Roy Schwartz, Omri Weinstein
Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:2.1-2.17, 2012.

Abstract

This paper introduces the Furthest Hyperplane Problem (FHP), which is an unsupervised counterpart of Support Vector Machines. Given a set of n points in R^d, the objective is to produce the hyperplane (passing through the origin) which maximizes the separation margin, that is, the minimal distance between the hyperplane and any input point. To the best of our knowledge, this is the first paper achieving provable results regarding FHP. We provide both lower and upper bounds to this NP-hard problem. First, we give a simple randomized algorithm whose running time is n^O(1/θ^2) where θis the optimal separation margin. We show that its exponential dependency on 1/θ^2 is tight, up to sub-polynomial factors, assuming SAT cannot be solved in sub-exponential time. Next, we give an efficient approximation algorithm. For any α∈[0, 1], the algorithm produces a hyperplane whose distance from at least 1 - 3αfraction of the points is at least αtimes the optimal separation margin. Finally, we show that FHP does not admit a PTAS by presenting a gap preserving reduction from a particular version of the PCP theorem.

Cite this Paper

BibTeX
@InProceedings{pmlr-v23-karnin12, title = {Unsupervised SVMs: On the Complexity of the Furthest Hyperplane Problem}, author = {Karnin, Zohar and Liberty, Edo and Lovett, Shachar and Schwartz, Roy and Weinstein, Omri}, booktitle = {Proceedings of the 25th Annual Conference on Learning Theory}, pages = {2.1--2.17}, year = {2012}, editor = {Mannor, Shie and Srebro, Nathan and Williamson, Robert C.}, volume = {23}, series = {Proceedings of Machine Learning Research}, address = {Edinburgh, Scotland}, month = {25--27 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v23/karnin12/karnin12.pdf}, url = {https://proceedings.mlr.press/v23/karnin12.html}, abstract = {This paper introduces the Furthest Hyperplane Problem (FHP), which is an unsupervised counterpart of Support Vector Machines. Given a set of n points in R^d, the objective is to produce the hyperplane (passing through the origin) which maximizes the separation margin, that is, the minimal distance between the hyperplane and any input point. To the best of our knowledge, this is the first paper achieving provable results regarding FHP. We provide both lower and upper bounds to this NP-hard problem. First, we give a simple randomized algorithm whose running time is n^O(1/θ^2) where θis the optimal separation margin. We show that its exponential dependency on 1/θ^2 is tight, up to sub-polynomial factors, assuming SAT cannot be solved in sub-exponential time. Next, we give an efficient approximation algorithm. For any α∈[0, 1], the algorithm produces a hyperplane whose distance from at least 1 - 3αfraction of the points is at least αtimes the optimal separation margin. Finally, we show that FHP does not admit a PTAS by presenting a gap preserving reduction from a particular version of the PCP theorem.} }
Endnote
%0 Conference Paper %T Unsupervised SVMs: On the Complexity of the Furthest Hyperplane Problem %A Zohar Karnin %A Edo Liberty %A Shachar Lovett %A Roy Schwartz %A Omri Weinstein %B Proceedings of the 25th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2012 %E Shie Mannor %E Nathan Srebro %E Robert C. Williamson %F pmlr-v23-karnin12 %I PMLR %P 2.1--2.17 %U https://proceedings.mlr.press/v23/karnin12.html %V 23 %X This paper introduces the Furthest Hyperplane Problem (FHP), which is an unsupervised counterpart of Support Vector Machines. Given a set of n points in R^d, the objective is to produce the hyperplane (passing through the origin) which maximizes the separation margin, that is, the minimal distance between the hyperplane and any input point. To the best of our knowledge, this is the first paper achieving provable results regarding FHP. We provide both lower and upper bounds to this NP-hard problem. First, we give a simple randomized algorithm whose running time is n^O(1/θ^2) where θis the optimal separation margin. We show that its exponential dependency on 1/θ^2 is tight, up to sub-polynomial factors, assuming SAT cannot be solved in sub-exponential time. Next, we give an efficient approximation algorithm. For any α∈[0, 1], the algorithm produces a hyperplane whose distance from at least 1 - 3αfraction of the points is at least αtimes the optimal separation margin. Finally, we show that FHP does not admit a PTAS by presenting a gap preserving reduction from a particular version of the PCP theorem.
RIS
TY - CPAPER TI - Unsupervised SVMs: On the Complexity of the Furthest Hyperplane Problem AU - Zohar Karnin AU - Edo Liberty AU - Shachar Lovett AU - Roy Schwartz AU - Omri Weinstein BT - Proceedings of the 25th Annual Conference on Learning Theory DA - 2012/06/16 ED - Shie Mannor ED - Nathan Srebro ED - Robert C. Williamson ID - pmlr-v23-karnin12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 23 SP - 2.1 EP - 2.17 L1 - http://proceedings.mlr.press/v23/karnin12/karnin12.pdf UR - https://proceedings.mlr.press/v23/karnin12.html AB - This paper introduces the Furthest Hyperplane Problem (FHP), which is an unsupervised counterpart of Support Vector Machines. Given a set of n points in R^d, the objective is to produce the hyperplane (passing through the origin) which maximizes the separation margin, that is, the minimal distance between the hyperplane and any input point. To the best of our knowledge, this is the first paper achieving provable results regarding FHP. We provide both lower and upper bounds to this NP-hard problem. First, we give a simple randomized algorithm whose running time is n^O(1/θ^2) where θis the optimal separation margin. We show that its exponential dependency on 1/θ^2 is tight, up to sub-polynomial factors, assuming SAT cannot be solved in sub-exponential time. Next, we give an efficient approximation algorithm. For any α∈[0, 1], the algorithm produces a hyperplane whose distance from at least 1 - 3αfraction of the points is at least αtimes the optimal separation margin. Finally, we show that FHP does not admit a PTAS by presenting a gap preserving reduction from a particular version of the PCP theorem. ER -
APA
Karnin, Z., Liberty, E., Lovett, S., Schwartz, R. & Weinstein, O.. (2012). Unsupervised SVMs: On the Complexity of the Furthest Hyperplane Problem. Proceedings of the 25th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 23:2.1-2.17 Available from https://proceedings.mlr.press/v23/karnin12.html.

Related Material