合成查询让学习效率从多项式跃升至指数级！主动学习难度被彻底改写
On the Sample Complexity of Active Learning with Membership Queries
📖 AI 总结
该研究重新审视了主动学习中的一个基本问题：合成任意查询的能力究竟有多强大。作者发现，与仅能从给定无标注样本池中选择查询的池基主动学习相比，允许学习者合成查询这一看似微小的能力变化，会显著改变统计学习的难度。具体而言，某些在池基设定下学习效率极低、误差随样本量仅呈多项式衰减的假设类，一旦允许合成查询，便可实现指数级的学习效率。这一巨大差距表明，成员查询合成引发了一种本质上不同的学习模式，现有主动学习理论无法充分刻画，需要新的分析工具来描述其复杂度。基于此现象，作者提出了若干充分条件，给出了有趣的示例，并提出了一种猜想性视角，以理解哪些假设类能够通过合成查询实现高效学习。
🔑 关键词速览
| 主动学习 (Active Learning) | 一种机器学习范式，学习器可以主动选择或生成查询来获取标记，旨在用更少样本达到更好效果。 |
| 成员查询合成 (Membership Query Synthesis) | 主动学习中的一种查询方式，学习器可以合成任意未标记实例并向教师询问其标签，而不限于从给定池中选择。 |
| 基于池的主动学习 (Pool-Based Active Learning) | 主动学习的常见设定，学习器只能从预先给定的未标记数据池中选择样本进行查询。 |
| 假设类 (Hypothesis Class) | 学习算法所考虑的候选函数的集合，通常用于刻画学习问题的复杂度。 |
| 样本复杂度 (Sample Complexity) | 学习器达到给定精度和置信度所需的最少训练样本数量，是衡量学习效率的关键指标。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅