LIPIcs.SoCG.2021.12.pdf
- Filesize: 0.94 MB
- 15 pages
Document
On Undecided LP, Clustering and Active Learning
Authors
Stav Ashur 
,
Sariel Har-Peled
-
Part of:
Volume:
37th International Symposium on Computational Geometry (SoCG 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-06-02
File
Document Identifiers
Author Details
Acknowledgements
The authors thank Pankaj Agarwal for useful discussions. We thank Lev Reyzin for pointing out the work by Maass and Turán [Maass and Tur{á}n, 1994; Maass and Turán, 1994].
Cite AsGet BibTex
Stav Ashur and Sariel Har-Peled. On Undecided LP, Clustering and Active Learning. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.12
https://doi.org/10.4230/LIPIcs.SoCG.2021.12
Abstract
We study colored coverage and clustering problems. Here, we are given a colored point set, where the points are covered by k (unknown) clusters, which are monochromatic (i.e., all the points covered by the same cluster have the same color). The access to the colors of the points (or even the points themselves) is provided indirectly via various oracle queries (such as nearest neighbor, or separation queries). We show that one can correctly deduce the color of all the points (i.e., compute a monochromatic clustering of the points) using a polylogarithmic number of queries, if the number of clusters is a constant.
We investigate several variants of this problem, including Undecided Linear Programming and covering of points by k monochromatic balls.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- Linear Programming
- Active learning
- Classification
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Dana Angluin. Queries and concept learning. Mach. Learn., 2(4):319-342, 1987. URL: https://doi.org/10.1007/BF00116828.
- Stav Ashur and Sariel Har-Peled. On undecided LP, clustering and active learning. CoRR, abs/2103.09308, 2021. URL: http://arxiv.org/abs/2103.09308.
- Timothy M. Chan. An optimal randomized algorithm for maximum Tukey depth. In J. Ian Munro, editor, Proc. 15th ACM-SIAM Sympos. Discrete Algs. (SODA), pages 430-436, Philadelphia, PA, USA, 2004. SIAM. URL: http://dl.acm.org/citation.cfm?id=982792.982853.
- Timothy M. Chan. Dynamic geometric data structures via shallow cuttings. In Proc. 35th Int. Annu. Sympos. Comput. Geom. (SoCG), pages 24:1-24:13, 2019. URL: https://doi.org/10.4230/LIPIcs.SoCG.2019.24.
- Martin E. Dyer, Nimrod Megiddo, and Emo Welzl. Linear programming. In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, Second Edition, pages 999-1014. Chapman and Hall/CRC, 2004. URL: https://doi.org/10.1201/9781420035315.pt6.
-
S. Har-Peled. Taking a walk in a planar arrangement. SIAM J. Comput., 30(4):1341-1367, 2000.
- S. Har-Peled. Geometric Approximation Algorithms, volume 173 of Math. Surveys & Monographs. Amer. Math. Soc., Boston, MA, USA, 2011. URL: https://doi.org/10.1090/surv/173.
- Sariel Har-Peled and Mitchell Jones. Journey to the center of the point set. In Gill Barequet and Yusu Wang, editors, Proc. 35th Int. Annu. Sympos. Comput. Geom. (SoCG), volume 129 of LIPIcs, pages 41:1-41:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.SoCG.2019.41.
- Sariel Har-Peled and Mitchell Jones. On separating points by lines. Discret. Comput. Geom., 63(3):705-730, 2020. URL: https://doi.org/10.1007/s00454-019-00103-z.
- Sariel Har-Peled, Mitchell Jones, and Saladi Rahul. Active learning a convex body in low dimensions. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, Proc. 47th Int. Colloq. Automata Lang. Prog. (ICALP), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 64:1-64:17, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.64.
- Sariel Har-Peled, Nirman Kumar, David M. Mount, and Benjamin Raichel. Space exploration via proximity search. Discrete Comput. Geom., 56(2):357-376, 2016. URL: https://doi.org/10.1007/s00454-016-9801-7.
-
S. Jadhav and A. Mukhopadhyay. Computing a centerpoint of a finite planar set of points in linear time. Discrete Comput. Geom., 12:291-312, 1994.
- Daniel M. Kane, Shachar Lovett, Shay Moran, and Jiapeng Zhang. Active classification with comparison queries. In Proc. 58th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pages 355-366, 2017. URL: https://doi.org/10.1109/FOCS.2017.40.
- Wolfgang Maass and György Turán. On the complexity of learning from counterexamples and membership queries. In Proc. 31st Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pages 203-210. IEEE Computer Society, 1990. URL: https://doi.org/10.1109/FSCS.1990.89539.
- Wolfgang Maass and György Turán. Algorithms and lower bounds for on-line learning of geometrical concepts. Machine Learning, 14(3):251-269, 1994. URL: https://doi.org/10.1007/BF00993976.
-
Wolfgang Maass and György Turán. How fast can a threshold gate learn? In Proc. Work. Comput. Learning Theory and Nat. Learn. Systems, pages 381-–414, Cambridge, MA, USA, 1994. MIT Press.
- Burr Settles. Active learning literature survey. Technical Report #1648, Computer Science, Univ. Wisconsin, Madison, 2009. URL: https://minds.wisconsin.edu/bitstream/handle/1793/60660/TR1648.pdf?sequence=1&isAllowed=y.