论文标题
通过歧视性功能反馈改进了可靠学习的鲁棒算法
Improved Robust Algorithms for Learning with Discriminative Feature Feedback
论文作者
论文摘要
判别特征反馈是Dastupta等人提出的设置。 （2018年），它根据人类教师提供的功能解释提供了一种用于互动学习的协议。这些功能区分了可能的类似实例对的标签。这项工作表明，在基于标准标签的交互式学习模型中，在此模型中学习可以具有相当大的统计和计算优势。 在这项工作中，我们为判别特征反馈模型提供了新的鲁棒交互式学习算法，错误界限明显低于此设置的先前可靠算法的界限。在对抗性环境中，我们减少了对协议异常数量的依赖性，从二次到线性。此外，我们为稍微受到限制的模型提供了一种算法，该算法在大型模型中获得了一个甚至较小的错误，但许多例外。 在随机环境中，我们提供了第一种以多项式样本复杂性收敛到异常速率的算法。我们对随机设置的算法和分析涉及我们称之为特征影响的新结构，这可能是更广泛的适用性。
Discriminative Feature Feedback is a setting proposed by Dastupta et al. (2018), which provides a protocol for interactive learning based on feature explanations that are provided by a human teacher. The features distinguish between the labels of pairs of possibly similar instances. That work has shown that learning in this model can have considerable statistical and computational advantages over learning in standard label-based interactive learning models. In this work, we provide new robust interactive learning algorithms for the Discriminative Feature Feedback model, with mistake bounds that are significantly lower than those of previous robust algorithms for this setting. In the adversarial setting, we reduce the dependence on the number of protocol exceptions from quadratic to linear. In addition, we provide an algorithm for a slightly more restricted model, which obtains an even smaller mistake bound for large models with many exceptions. In the stochastic setting, we provide the first algorithm that converges to the exception rate with a polynomial sample complexity. Our algorithm and analysis for the stochastic setting involve a new construction that we call Feature Influence, which may be of wider applicability.
