论文标题
主动学习多项式阈值功能
Active Learning Polynomial Threshold Functions
论文作者
论文摘要
我们启动主动学习多项式阈值函数（PTF）的研究。尽管传统的下限意味着即使单变量二次学也不能是非微不足道的，但我们表明，允许学习者的基本访问基础分类器的基本访问范围绕过这个问题，并导致计算高效的算法，以实现积极学习度 - $ \ tilde {o}（d^3 \ log（1/\varepsilunΔ））$ queries。我们还提供了几乎最佳的算法和分析在几个平均情况下的主动学习PTF。最后，我们证明对衍生产品的访问不足以用于主动学习多元PTF，甚至仅是两个变量的PTF。
We initiate the study of active learning polynomial threshold functions (PTFs). While traditional lower bounds imply that even univariate quadratics cannot be non-trivially actively learned, we show that allowing the learner basic access to the derivatives of the underlying classifier circumvents this issue and leads to a computationally efficient algorithm for active learning degree-$d$ univariate PTFs in $\tilde{O}(d^3\log(1/\varepsilonδ))$ queries. We also provide near-optimal algorithms and analyses for active learning PTFs in several average case settings. Finally, we prove that access to derivatives is insufficient for active learning multivariate PTFs, even those of just two variables.
