PAC Learning is just Bipartite Matching (Sort of)
This work addresses foundational questions in machine learning theory by linking PAC learning to combinatorial problems, potentially offering new perspectives for researchers in theoretical ML.
The paper argues that supervised learning in the PAC model is closely related to bipartite matching, using a transductive model and one-inclusion graphs as tools to explore this connection, with the aim of providing insights into learning theory.
The main goal of this article is to convince you, the reader, that supervised learning in the Probably Approximately Correct (PAC) model is closely related to -- of all things -- bipartite matching! En-route from PAC learning to bipartite matching, I will overview a particular transductive model of learning, and associated one-inclusion graphs, which can be viewed as a generalization of some of the hat puzzles that are popular in recreational mathematics. Whereas this transductive model is far from new, it has recently seen a resurgence of interest as a tool for tackling deep questions in learning theory. A secondary purpose of this article could be as a (biased) tutorial on the connections between the PAC and transductive models of learning.