When Can We Learn from Noisy Logical Data? Parameterized Complexity of Approximate Concept Fitting in Description Logics

摘要

SAT-based bounded fitting—searching for a smallest logical concept that correctly classifies all given examples—yields sample-efficient PAC learning for structured hypothesis classes such as description logic (DL) concepts. Yet this paradigm is fundamentally brittle: it demands realizability, and a single mislabeled example can render the underlying SAT instance unsatisfiable. While agnostic learnability follows from finite VC-dimension of bounded-size concept classes, the real barrier is computational: minimizing misclassifications over all concepts of bounded size is NP-hard. We study this barrier through parameterized complexity. We introduce ApxFit(k,t)—the problem of deciding whether there exists a DL concept of size at most k that misclassifies at most t out of m examples—and establish a complexity landscape for fragments of 𝒜ℒ𝒞 whose operator sets contain {⊓,∃} or {⊔,∀}: the problem is W[2]-hard parameterized by concept size k (even for t=0), yet lies in XP parameterized by outlier count t for any fixed k. Algorithmically, we lift bounded fitting from SAT to partial weighted MAX-SAT and combine it with structural risk minimization, yielding the first noise-tolerant DL concept learner with formal agnostic generalization guarantees.