论文标题
点位置和主动学习：学习半空间几乎是最佳的
Point Location and Active Learning: Learning Halfspaces Almost Optimally
论文作者
论文摘要
给定有限集$ x \ subset \ mathbb {r}^d $和二进制线性分类器$ c：\ mathbb {r}^d \ to \ to \ {0,1 \} $，需要$ c（x）$的$ c（x）$的查询。这个问题被称为\ textit {point stopation}，在追求最佳算法的过程中启发了35年的研究。在凯恩（Kane），洛维特（Lovett）和莫兰（Moran）的先前工作（ICALP 2018）的基础上，我们提供了第一个几乎最佳解决方案，这是一个随机的线性线性决策树，深度$ \ tilde {o}（d \ log（| x |））$，以$ \ tilde {o}（d^2 \ log（d^2 \ log（x | x |）的$ \ tilde {| x | x |）和earkrie $ \ tilde（| 2019）。作为推论，我们还提供了第一种几乎最佳的算法，用于在会员查询模型中积极学习半个空间。在这些结果途中，我们证明了Barthe定理（Mathematicae，1998）独立利益的新颖表征。特别是，我们表明$ x $只有在没有$ k $二维子空间，大于$ k/d $ raction $ x $的情况下，并且只有存在$ k $二维的子空间，并且提供类似的各向同性位置的特征。
Given a finite set $X \subset \mathbb{R}^d$ and a binary linear classifier $c: \mathbb{R}^d \to \{0,1\}$, how many queries of the form $c(x)$ are required to learn the label of every point in $X$? Known as \textit{point location}, this problem has inspired over 35 years of research in the pursuit of an optimal algorithm. Building on the prior work of Kane, Lovett, and Moran (ICALP 2018), we provide the first nearly optimal solution, a randomized linear decision tree of depth $\tilde{O}(d\log(|X|))$, improving on the previous best of $\tilde{O}(d^2\log(|X|))$ from Ezra and Sharir (Discrete and Computational Geometry, 2019). As a corollary, we also provide the first nearly optimal algorithm for actively learning halfspaces in the membership query model. En route to these results, we prove a novel characterization of Barthe's Theorem (Inventiones Mathematicae, 1998) of independent interest. In particular, we show that $X$ may be transformed into approximate isotropic position if and only if there exists no $k$-dimensional subspace with more than a $k/d$-fraction of $X$, and provide a similar characterization for exact isotropic position.
