VC 学习的最优信息复杂度

一项针对条件互信息（CMI）框架的研究证实，通过依赖算法的信息论分析可恢复 VC 类的最优 PAC 保证。研究在可实现情形下构造出一种评估条件互信息（eCMI）阶数为 O(d) 的学习算法，其中 d 为概念类的 VC 维。该算法采用随机化 Majority-of-5 基学习器架构，具备最优的期望泛化保证。