HackerPapers

arXiv:2208.10255cs.DB

On the non-efficient PAC learnability of conjunctive queries

Balder ten Cate, Maurice Funk, Jean Christoph Jung, Carsten Lutz

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

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.

arXiv comments
To appear in Information Processing Letters
Journal reference
DOI
Subjects
cs.DBDatabases cs.AIArtificial Intelligence cs.LGMachine Learning cs.LOLogic in Computer Science

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Oct 2023 to Oct 2023.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Language Models Represent Space and Time 1 comment

    • The halting problem simply doesn't apply to biological neurons, they don't side step them, unless your context is humans writing down an Algorithm. The rules of a human writing down an algorithm is the same thing as a Turing machine running an algorithm. The halting problem…

      nyrikkiView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.