Aug, 2022
关于非高效 PAC 学习无环连通查询的研究
On the non-efficient PAC learnability of acyclic conjunctive queries
Balder ten Cate, Maurice Funk, Jean Christoph Jung, Carsten Lutz
TL;DR本文研究在 PAC 模型下共识查询的学习问题，证明了共识查询类不具有多项式大小匹配的性质，给出了许多限制类共识查询的负 PAC 可学性结果，最后提出了利用成员查询实现共识查询的高效 PAC 学习方法。