论文标题
通过半空间查询，教学凸多属的平均案例复杂性
Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries
论文作者
论文摘要
我们检查了在$ \ mathbb {r}^d $中，在$ n $ halfspaces引起的交集中找到目标区域的任务。这项通用的任务与基本的机器学习问题有关，例如训练感知者和学习$ ϕ $ - 分离的二分法。我们研究任务的平均教学复杂性，即，教师要求的样本数量最少（半空间查询），以帮助版本空间学习者找到一个随机选择的目标。作为我们的主要结果，我们表明平均教学复杂性为$θ（d）$，与$θ（n）$的最差教学复杂性形成鲜明对比。相反，如果我们考虑平均学习复杂性，则界限对$ n $的依赖性为$θ（n）$，用于\ tt {i.i.d。}查询和$θ（d \ log（n））$，用于由学习者积极选择的查询。我们的证明技术基于计算几何形状的新见解，这些见解使我们能够根据半个空间的排列来计算欧几里得空间中凸多型和面的数量。我们的见解使我们能够建立对$ ϕ $ - 分离的二分法的平均案例复杂性的紧密束缚，该二分法概括了已知的$ \ Mathcal {o}（d）$绑定的经典计算几何形状中的“极端模式”数量的“极端模式”数量（封面，封面，1965年）。
We examine the task of locating a target region among those induced by intersections of $n$ halfspaces in $\mathbb{R}^d$. This generic task connects to fundamental machine learning problems, such as training a perceptron and learning a $ϕ$-separable dichotomy. We investigate the average teaching complexity of the task, i.e., the minimal number of samples (halfspace queries) required by a teacher to help a version-space learner in locating a randomly selected target. As our main result, we show that the average-case teaching complexity is $Θ(d)$, which is in sharp contrast to the worst-case teaching complexity of $Θ(n)$. If instead, we consider the average-case learning complexity, the bounds have a dependency on $n$ as $Θ(n)$ for \tt{i.i.d.} queries and $Θ(d \log(n))$ for actively chosen queries by the learner. Our proof techniques are based on novel insights from computational geometry, which allow us to count the number of convex polytopes and faces in a Euclidean space depending on the arrangement of halfspaces. Our insights allow us to establish a tight bound on the average-case complexity for $ϕ$-separable dichotomies, which generalizes the known $\mathcal{O}(d)$ bound on the average number of "extreme patterns" in the classical computational geometry literature (Cover, 1965).
