Active-Learning a Convex Body in Low Dimensions
Active-Learning a Convex Body in Low Dimensions
复制标题
主动学习低维凸体
DOI：
10.1007/s00453-021-00807-w
复制
发表时间：
2021
期刊：
影响因子：
1.1
通讯作者：
Rahul, Saladi
中科院分区：
文献类型：
--
作者：
Har-Peled, Sariel;Jones, Mitchell;Rahul, Saladi
考虑一个由n个点组成的集合P <$R^ d P <$R d，一个凸体C C通过一个分离预言机给出。手头的任务是决定P P的每个点是否在C C中使用最少数量的Oracle查询。我们表明，可以解决这个问题，在两个和三个维度使用查询，其中是P P的凸位置的点的最大子集的大小。在2D中，我们提供了一个算法，有效地生成这些自适应查询。此外，我们表明，在两个维度上，可以解决这个问题，使用Oracle查询，其中是一个下界的最小数量的查询，任何算法，这个特定的实例需要。最后，我们考虑问题的其他变化，如使用最少的查询次数来决定C C是否包含P P的所有点。作为上述的应用，我们证明了点集P在R^2 R2中的离散几何中值可以在预期的时间内计算。
Consider a set P ⊆ R^ d P⊆ R d of n points, and a convex body C C provided via a separation oracle. The task at hand is to decide for each point of P P if it is in C C using the fewest number of oracle queries. We show that one can solve this problem in two and three dimensions using queries, where is the size of the largest subset of points of P P in convex position. In 2D, we provide an algorithm that efficiently generates these adaptive queries. Furthermore, we show that in two dimensions one can solve this problem using oracle queries, where is a lower bound on the minimum number of queries that any algorithm for this specific instance requires. Finally, we consider other variations on the problem, such as using the fewest number of queries to decide if C C contains all points of P P. As an application of the above, we show that the discrete geometric median of a point set P in R^ 2 R 2 can be computed in expected time.
登录
查看更多内容
一种高效的计量邻近探测算法
DOI：
10.1109/coase.2013.6653995
发表时间：
2013
期刊：
2013 IEEE International Conference on Automation Science and Engineering (CASE)
影响因子：
--
作者：
S. Panahi;Aviv Adler;A.F. van der Stappen;Ken Goldberg
通讯作者：
Ken Goldberg
在平均稀疏的图上快速混合吉布斯采样
影响因子：
1
作者：
Elchanan Mossel;Allan Sly
通讯作者：
Allan Sly
弱epsilon网的新构造
影响因子：
1
作者：
J. Matoušek
通讯作者：
J. Matoušek
K 顶点 D 多面体的 VC 维数
影响因子：
1.1
作者：
A. Kupavskii
通讯作者：
A. Kupavskii
平面上弱 Epsilon 网的改进界限
DOI：
10.1145/3555985
发表时间：
2018
期刊：
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
Natan Rubin
通讯作者：
Natan Rubin