May, 2024
传导学习是否等同于 PAC 学习？
Is Transductive Learning Equivalent to PAC Learning?
Shaddin Dughmi, Yusuf Kalayci, Grayson York
TL;DR通过向数据集添加少量样本，我们将依靠 PAC 保证的无偏泛化学习转化为依靠转导保证的无偏泛化学习，从而展示了这些问题的等效性。我们还将所得到的结果扩展到了 agnostic 情况，证明了一种 agnostic 转导学习器可以高效转化为 agnostic 无偏泛化学习器。最后，我们对二进制分类的 agnostic one inclusion 图算法进行了性能表征，并且展示了将其和我们的转导转化方法相结合可以得到一个本质上最优的 agnostic 无偏泛化学习器。我们的结果意味着在可实现的环境下，使用伪度量损失函数进行监督学习时，转导学习和 PAC 学习在本质上是等价的；在 agnostic 情况下，对于二进制分类问题，也是如此。我们猜想这个结论在 agnostic 情况下更普遍适用。