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\delta))$ 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.

翻译：我们开始研究积极的学习多元阈值函数(PTFs ) 。 虽然传统的下限意味着即使是单亚里亚特二次曲线也不能不积极学习,但我们显示,允许学习者基本接触基础分类器衍生物可以绕过这个问题,导致在$\tilde{O}(d}3\log(1/\varepsilon\delta)$查询中,对积极的学习学位-美元单亚里亚特多功能计算法的计算法。 我们还为几个普通情况下的积极学习多变量提供接近最佳的算法和分析。 最后,我们证明,对于积极学习多变量多变量的多变量,即使只有两种变量,获取衍生物的算法也是不够的。