PAC Learning: From Finite Families to CNF Formulas - Lecture on March 20, 2023

Learn about Probably Approximately Correct (PAC) learning through this comprehensive seminar lecture that explores finite families, conjunctions, k-CNFs, and CNFs with k terms. Delve into the theoretical foundations of machine learning as presented at the prestigious Kolmogorov seminar on computational and descriptional complexity. Examine the NP-completeness of proper learning for 2-term Conjunctive Normal Form (CNF) and gain insights into fundamental concepts of computational learning theory. The lecture, delivered as part of a seminar series founded by Kolmogorov around 1979, provides a rigorous mathematical treatment of PAC learning frameworks and their computational complexity implications.