论文标题
关于连接性查询的非效率PAC可学习性
On the non-efficient PAC learnability of conjunctive queries
论文作者
论文摘要
该注释有三个目的：（i）我们提供了一个独立的阐述，表明连接性查询在可能的模型中无法有效地学习（PAC）模型，从而清楚地关注了复杂的事实，即该概念类缺乏拟合多项式的属性，这是在计算学院学习理论理论文献中均具有宽容性的属性； （ii）我们建立了一个强大的负PAC可学习性结果，该结果适用于许多限制类别的连接性查询（CQ），包括针对“ acyclicity”概念的露无环CQ； （iii）我们表明，CQS（和UCQS）在会员查询中有效地学习了PAC。
This note serves three purposes: (i) we provide a self-contained exposition of the fact that conjunctive queries are not efficiently learnable in the Probably-Approximately-Correct (PAC) model, paying clear attention to the complicating fact that this concept class lacks the polynomial-size fitting property, a property that is tacitly assumed in much of the computational learning theory literature; (ii) we establish a strong negative PAC learnability result that applies to many restricted classes of conjunctive queries (CQs), including acyclic CQs for a wide range of notions of "acyclicity"; (iii) we show that CQs (and UCQs) are efficiently PAC learnable with membership queries.
