Nature撰文表明哥德尔不完备性定理也适用于机器学习领域
数学经纬2019-01-08 19:51
二十世纪，数学逻辑的发现彻底改变了我们对数学基础的理解。1931年，逻辑学家哥德尔（ Kurt Gdel）证明，在可比拟算术的公理系统中，一些陈述是不可证伪的。这就是著名的哥德尔不完备性定理。
随后的几十年中，连续统假说——即不存在大于整数而小于实数的集合——被证实在标准公理体系中是不完备的，它既不能被证明，也不能被证伪。
机器学习领域，似乎远离数理逻辑，但最近本-大卫（Ben-David）等人发现了一个机器学习中的问题，它与连续统假说等价，表明机器学习中也存在不可证伪的算法。
Natureyilan对机器学习的畅想，源自这样的事实：2001年，Viola和Jones在AdaBoost算法的基础上，使用Haar-like小波特征和积分图方法进行人脸检测，发现在经过照片样本训练之后，机器系统可以实时地检测人的面孔。这可以说是机器学习史上的里程碑。
本-大卫等人描述一个估计最大值(EMX)问题：在事先不知道哪些访客会访问该网站的情况下，投放以网站最频繁的访客为目标的广告。作者将EMX正规化为一个关于学习者从给定的函数族中寻找特定函数的问题，该函数族对目标分布的期望值尽可能大。EMX模型实际上与PAC模型（Probably Approximately Correct）)非常相似，但稍微不同的学习标准将它与连续统假设联系在一起。
作者证明机器学习和数据压缩之间有一个漂亮的关联：如果由某个函数族标记的样本总是能被压缩，那么这个函数族在某种意义上必须是低复杂度的，因此是可学习的。单调压缩是压缩的一种变体，它适用于描述EMX中特定函数族的可学习性。对于0到1之间的实数构成的集合，其有限子集具有单调压缩格式，因此在EMX中是可学习的，但前提是当且仅当连续统假设是正确的，而众所周知，这是一个不可证明的命题。
EMX是机器学习中的一个新模型，我们还不知道它在开发真实世界算法中的作用。因此，这些结果可能没有实际意义。机器学习作为一门数学学科已经成熟，也许这样的结果会给机器学习领域带来新的机遇。
举报/反馈
0
0
收藏
分享
