把机器学习中的PAC模型和二分图匹配联系起来，揭示了学习理论的新视角。
PAC Learning is just Bipartite Matching (Sort of)
- 用二分图匹配的视角重新理解PAC学习问题
- 通过推广帽子谜题中的图结构建模学习过程
- 适合对学习理论和组合优化感兴趣的读者
本文旨在说服读者：在概率近似正确（PAC）模型下的监督学习，与二分图匹配有着密切关联。在从PAC学习过渡到二分图匹配的过程中，文章概述了一种特定的归纳学习模型及其相关的一包含图（one-inclusion graphs），该图可视为某些流行于趣味数学中的帽子谜题的推广。尽管这种归纳模型并非新概念，但近期因其在解决学习理论深层问题中的潜力而再次受到关注。本文另一目标是作为（有倾向性的）教程，阐述PAC模型与归纳学习模型之间的联系。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。