A formal proof of PAC learnability for decision stumps
A formal proof of PAC learnability for decision stumps
复制标题
决策树桩的 PAC 可学习性的正式证明
DOI：
10.1145/3437992.3439917
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Jean
中科院分区：
文献类型：
--
作者：
Joseph Tassarotti;Koundinya Vajjha;Anindya Banerjee;Jean
我们以倾斜的方式提供了一个正式的证据，可能是对决策树桩的概念类别的可学习性。机器学习理论的这一经典结果得出了一个简单类型的分类器类型的错误概率。尽管这种证明在纸上看起来很简单，但在正式进行时，出现了分析和测量理论的微妙之处。我们的证明是结构化的，以便将学习功能的确定性特性分开，从可测量性和概率分析的证据中。
We present a formal proof in Lean of probably approximately correct (PAC) learnability of the concept class of decision stumps. This classic result in machine learning theory derives a bound on error probabilities for a simple type of classifier. Though such a proof appears simple on paper, analytic and measure-theoretic subtleties arise when carrying it out fully formally. Our proof is structured so as to separate reasoning about deterministic properties of a learning function from proofs of measurability and analysis of probabilities.
DOI：
10.1007/s10817-017-9404-x
发表时间：
2017
期刊：
Journal of Automated Reasoning
影响因子：
--
作者：
Jeremy Avigad;Johannes Hölzl;Luke Serafin
通讯作者：
Luke Serafin
DOI：
10.1609/aaai.v33i01.33012662
发表时间：
2019-07
期刊：
ArXiv
影响因子：
--
作者：
Alexander Bagnall;Gordon Stewart
通讯作者：
Alexander Bagnall;Gordon Stewart
《Isabelle/HOL》中的测度论三章
DOI：
10.1007/978-3-642-22863-6_12
发表时间：
2011
期刊：
影响因子：
--
作者：
Johannes Hölzl;Armin Heller
通讯作者：
Armin Heller