网易首页 > 网易号 > 正文 申请入驻

一个无解的数学难题是如何触及机器学习的极限的?数学统治一切

0
分享至


机器能学习什么?这可能是机器学习理论中最令人兴奋的问题之一。它涉及学科的极限——可学习性。另一方面,连续统假设触及了我们数学知识的极限——不可证明性。

可学习性问题

让我们从机器学习开始。为了研究可学习性问题,我们需要一个精确的数学框架来分析机器学习。为了这个目的,莱斯利·瓦利安特(Leslie Valiant)在1984年引入了可能近似正确学习模型(probably approximately correct learning ,PAC-learning)。

可能近似正确学习的想法很简单:学习者接收关于某个问题的少量信息,然后根据这些数据输出一个一般性的假设。例如,学习者可以接收照片和关于这些照片中是否有猫的信息。然后,学习者必须选择一个函数来决定给定的照片中是否包含一只猫。

可能近似正确学习模型的名字来自于这样一个事实,即我们要求学习者选择一个具有高概率的近似正确的函数。总之,如果学习者可能选择一个近似正确的函数,那么这个问题就是可能近似正确学习的。

连续统假设

康托尔的连续统问题是什么1878年,数学家康托尔(Georg Cantor))提出一个问题:实数的所有子集是与自然数一一对应,还是与实数一一对应。这就是所谓的连续统假设。

哥德尔和科恩证明了这个问题是可从ZFC公理体系(the Zermelo-Fraenkel axioms of set theory)中判定。他们指出,既没有证据证明连续统假设,也没有证据反驳它。连续统假说是不可证明的,它的否定也是不可证明的。

可学习性与连续统假设的关系

这里似乎有两个非常不同的问题:一个是可能近似正确学习模型问题,来自于理论计算机科学,讨论机器是否可以学习某些功能。还有一个连续统问题问的是是否存在一定规模的无穷集合。这两件事有什么关系?

2019年,一组研究人员在《自然-机器智能》上发表了一篇题为《学习性可以是不可判定的》的文章:

我们描述了不能用数学标准公理证明或反驳可学习性的简单场景。我们的证明是基于一个事实,即连续统假说既不能被证明,也不能被反驳。

他们是怎么表现出来的?研究人员本·大卫对学习问题进行了极大的简化。他们称之为估计最大值问题(EMX),并给出了一个例子:

想象一个被各种各样的用户访问的网站。用X表示该网站所有潜在访问者的集合。该网站的所有者希望在上面发布广告。发布的广告将从给定的广告池中选择。广告池中的每个广告A针对特定的用户群体F(A) ⊆ X。例如,如果A是一个体育广告,则F(A)是体育爱好者的集合。目标是放置一个目标人群访问网站最频繁的广告。挑战在于事先不知道哪些访客会来访问这个网站。

这个为你的网站找到最佳广告的简单问题可以被概括为一个涉及集合族和概率分布的数学问题。给定定义域D上的子集集合F,以及在D上的一个概率分布,在F中找到具有最高概率的集合。真正困难的是我们事先不知道概率分布。

本·大卫和他的同事如何证明特定问题的“估计最大值(EMX)”可学习性独立于ZFC数学公理?

一种方法是构建集合理论的模型,即可能的数学世界,其中一个问题是估计最大值可学习的,另一个则不是。然而,这将是非常复杂的。

相反,本·大卫和他的合著者做了许多聪明的数学家以前做过的事,并使用已经确定的结果。他们利用学习和压缩之间的联系证明了估计最大值学习问题的一个非常复杂的实例等同于康托的连续体假设。

如果你能证明一个命题等同于连续统假设,那么事实上,你就证明了你的命题独立于ZFC。很容易看到,如果你的表述是正确的,那么根据等价性,连续统假设一定是正确的。如果你的表述是错误的,那么根据等价性,连续统假设一定是错误的。但是连续体假说在ZFC中既不正确也不错误,所以你的表述也必须是一样的。

数学家可计算机科学家们发现了一种巧妙的方法,将数学的基础与机器学习的基础联系起来。所有的东西都是相互联系的——可学习性的极限可能取决于我们的数学基础。

集论

一个关键的声音

我们应该如何严肃对待这些结果?荷兰数学家和集合理论家K.P.哈特批判性地分析了本·大卫等人的论文。简单地说,哈特的观点是:

学习问题本质上要求学习者想出一个广义函数。如果这个广义函数足够好,那么我们就说学习者已经学会了这个问题。换句话说,这个问题是可以学习的。

然而,要求一个问题可以被机器学习是一个进一步的限制。艾伦·图灵用他著名的停机问题证明了并不是所有的函数都是可计算的。所以,要说机器可以学习问题,我们必须确保我们正在讨论的函数实际上可以由机器来处理:

所使用的函数是任意的,与任何可识别的算法无关。(K.P.哈特,《机器学习与连续体假说》)。

哈特指出,本·大卫和他的合著者已经认识到了这一点。然后他建议让问题更加精确:

一种分离“算法”函数的可能方法是要求它们具有良好的描述性属性。如果用“nice”表示“波莱尔可测性”,则期望的函数不存在。(K.P.哈特,《机器学习与连续体假说》)。

波莱尔可测性是函数所具有的一个性质。定义的精确细节在这里并不重要。然而,使用标准的算法形式(例如图灵机),并将算法函数视为根据算法将某些输入映射到某些输出的函数,可以得出这样的结论:算法是波莱尔可测函数。

哈特证明了没有波莱尔可测函数可以解决估计最大值学习问题。这意味着没有算法,没有计算机,没有机器可以解决这个问题。因此:

结果表明波莱尔可测学习函数不存在。这意味着标题《可学习性可以是不可判定的》应该修订为《估计最大值学习是不可能的》。(K.P.哈特,《机器学习与连续体假说》)

我们应该如何理解呢?不管估计最大值学习问题是不是学习问题不可定性的恰当例子,我的结论是,数学和逻辑的基础有时看起来是多么抽象和模糊,它们是如此基础,以至于它们影响了像机器学习这样最实用的学科。

想了解更多精彩内容,快来关注老胡说科学

特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.

相关推荐
热点推荐
沈阳人注意!取消、调整、延期

沈阳人注意!取消、调整、延期

今日说要闻
2021-08-03 04:00:39
吴亦凡在拘留所现状:据称几十人挤通铺还没空调,但伙食有肉还行

吴亦凡在拘留所现状:据称几十人挤通铺还没空调,但伙食有肉还行

每暮风来晚相依
2021-08-02 23:40:20
实在是太损了,网友:32万的雷克萨斯ES,真跑不过32岁的苏炳添?

实在是太损了,网友:32万的雷克萨斯ES,真跑不过32岁的苏炳添?

小李车评李建红
2021-08-03 08:43:04
不排除生物武器?央媒披露疫情暴发前美军预言大流行,还提到武汉

不排除生物武器?央媒披露疫情暴发前美军预言大流行,还提到武汉

云窗房市天天报
2021-08-02 18:09:40
谣言可以停止了!郎平透露最新消息,朱婷的伤病是手腕韧带撕裂

谣言可以停止了!郎平透露最新消息,朱婷的伤病是手腕韧带撕裂

赛场风云
2021-08-03 08:09:37
土榨油闻着是真香,吃着也是真的毒

土榨油闻着是真香,吃着也是真的毒

舌尖下de美食
2021-08-02 17:35:00
66岁大妈坦言:我和丈夫退休金共3万,可穷得连猪肉都买不起

66岁大妈坦言:我和丈夫退休金共3万,可穷得连猪肉都买不起

莎莎情感屋
2021-08-03 09:11:03
售卖“过期”红酒,上海酒商被重罚!专家:简直荒谬!

售卖“过期”红酒,上海酒商被重罚!专家:简直荒谬!

葡萄酒智库
2021-08-02 18:34:04
广东任命一批厅级干部

广东任命一批厅级干部

时事解读评论员
2021-08-03 07:06:24
4.56亿!上海市轨道交通23号线一期工程设计1标中标

4.56亿!上海市轨道交通23号线一期工程设计1标中标

e车网
2021-08-02 18:51:54
塔克正式加盟热火!1500万告别字母哥,篮网对不起,东部第1不是你

塔克正式加盟热火!1500万告别字母哥,篮网对不起,东部第1不是你

篮球迷聚集地
2021-08-03 11:25:10
紧急寻人!不主动报告!已有2人被查处!

紧急寻人!不主动报告!已有2人被查处!

老囧奇谈
2021-08-02 18:15:33
简约的牛仔裤,给美丽增添了清新的气息

简约的牛仔裤,给美丽增添了清新的气息

奶昔音乐
2021-08-03 10:18:08
英国发布报告:世界文明面临崩溃,只有5国能存活,不包括中美

英国发布报告:世界文明面临崩溃,只有5国能存活,不包括中美

君清奇趣
2021-08-02 19:42:56
我国驻美大使履新即遭下马威,拜登接近明牌!亲台政客猛打擦边球

我国驻美大使履新即遭下马威,拜登接近明牌!亲台政客猛打擦边球

全球鹰视野
2021-08-03 10:34:59
中国最贵的三棵树,一棵配有警卫,一棵投保1个亿,还有一棵…

中国最贵的三棵树,一棵配有警卫,一棵投保1个亿,还有一棵…

读史
2021-08-02 10:27:29
关键时刻,英内阁高级官员称,如苏格兰公投独立意志坚定,不阻挠

关键时刻,英内阁高级官员称,如苏格兰公投独立意志坚定,不阻挠

志宏教授
2021-08-03 07:00:22
腾讯跌幅收窄,经济参考报删除游戏“精神鸦片”一文,新华网也删除

腾讯跌幅收窄,经济参考报删除游戏“精神鸦片”一文,新华网也删除

和讯网
2021-08-03 13:11:04
菲媒:请美国开放德特里克堡接受新冠溯源调查

菲媒:请美国开放德特里克堡接受新冠溯源调查

国际在线
2021-07-25 21:02:39
吴亦凡再出新料,涉及上亿,这事儿越闹越大了……

吴亦凡再出新料,涉及上亿,这事儿越闹越大了……

品牌营销官
2021-07-31 21:48:26
2021-08-03 17:00:49
老胡说科学
老胡说科学
科学如此美妙,我想让你知道
707文章数 18912关注度
往期回顾 全部

科技要闻

传特斯拉拟减少一线城市商超体验店数量

头条要闻

中国女子水球队队长因颜值出圈 她却想当"万兽之王"

头条要闻

中国女子水球队队长因颜值出圈 她却想当"万兽之王"

体育要闻

杜兰特率领美国男篮突围!卢比奥尽力了

娱乐要闻

吴的瓜让4年前裸身坠亡的她再被提起

财经要闻

汽车要闻

奥迪A6纯电版将于2023年上市 续航或达700km

态度原创

本地
教育
时尚
游戏
家居

本地新闻

柚子叶洗澡,如何成为广东人的转运密码?

教育要闻

混血学霸美女为中国香港队夺两银!还有另一身份引关注

昨天LV舍弃吴亦凡 今天LVMH"吞食"了他的好兄弟

Steam喜加一:《战地1》载具捆绑包

家居要闻

中国小伙在德国花350万买两室一厅 赠超爽地下室