论文标题
动态互动学习的统一分析
A Unified Analysis of Dynamic Interactive Learning
论文作者
论文摘要
在本文中，我们研究了学习在组合结构上不断发展的概念的问题。 Emamjomeh-Zadeh等人的先前工作。 [2020]将动力学引入交互式学习中，作为在聚类问题或推荐系统中对非静态用户偏好进行建模的一种方式。我们为这个问题提供了许多有用的贡献。首先，我们提供了一个框架，该框架捕获了[Emamjomeh-Zadeh等，2020]分析的两个模型，该模型使我们能够研究任何类型的概念演化，并匹配与先前模型相同的查询复杂性界限和运行时间的保证。使用此通用模型，我们解决了在查询复杂性上缩小上限和下限之间差距的开放问题。最后，我们研究了一种有效的算法，其中学习者只是在每个回合中都遵循反馈，并且我们使用Markov链模型为低直径图（例如集团，恒星和一般O（log n）直径图）提供了错误界限。
In this paper we investigate the problem of learning evolving concepts over a combinatorial structure. Previous work by Emamjomeh-Zadeh et al. [2020] introduced dynamics into interactive learning as a way to model non-static user preferences in clustering problems or recommender systems. We provide many useful contributions to this problem. First, we give a framework that captures both of the models analyzed by [Emamjomeh-Zadeh et al., 2020], which allows us to study any type of concept evolution and matches the same query complexity bounds and running time guarantees of the previous models. Using this general model we solve the open problem of closing the gap between the upper and lower bounds on query complexity. Finally, we study an efficient algorithm where the learner simply follows the feedback at each round, and we provide mistake bounds for low diameter graphs such as cliques, stars, and general o(log n) diameter graphs by using a Markov Chain model.
