20世紀(jì)30年代，奧地利數(shù)學(xué)家Kurt G?del向世人證明，集合論中的“連續(xù)統(tǒng)假設(shè)(continuum hypothesis)”既無(wú)法被證明，也無(wú)法被證偽。

一個(gè)徹頭徹尾的悖論。

自此，這一悖論如烏云般籠罩于數(shù)學(xué)界，并給數(shù)學(xué)的根基帶了革命性的改變。

而今，這一朵烏云出人意料地降臨到了機(jī)器學(xué)習(xí)界，或?qū)ⅰ邦嵏病睓C(jī)器學(xué)習(xí)理論。

這一研究的最新結(jié)果已被發(fā)表于1月7日的Nature Machine Intelligence。

那么，什么是“連續(xù)統(tǒng)假設(shè)(continuum hypothesis)”？這一假設(shè)對(duì)機(jī)器學(xué)習(xí)而言又意味著什么呢?

近日，幾位研究機(jī)器學(xué)習(xí)問(wèn)題的數(shù)學(xué)家表示，“可學(xué)習(xí)性”問(wèn)題——即算法能否從有限的數(shù)據(jù)中提取模式——與被稱為連續(xù)統(tǒng)假設(shè)(continuum hypothesis)的悖論有關(guān)。數(shù)學(xué)家G?del曾表示，使用標(biāo)準(zhǔn)數(shù)學(xué)語(yǔ)言不能證明該假設(shè)是真是假。

“對(duì)我們來(lái)說(shuō)，這是一個(gè)驚喜，”該論文的作者之一、以色列理工學(xué)院(Technio)的Amir Yehudayoff說(shuō)，雖然有許多技術(shù)數(shù)學(xué)問(wèn)題被同樣認(rèn)為“不可判定”，但他之前并沒有想到這種現(xiàn)象會(huì)出現(xiàn)在機(jī)器學(xué)習(xí)中一個(gè)相對(duì)簡(jiǎn)單的問(wèn)題上。

英國(guó)斯旺西大學(xué)( Swansea University, UK)的計(jì)算機(jī)科學(xué)家John Tucker說(shuō)，這篇論文是“關(guān)于我們知識(shí)局限性的重量級(jí)結(jié)果”，對(duì)數(shù)學(xué)和機(jī)器學(xué)習(xí)都具有基礎(chǔ)性意義。

并非所有無(wú)限集合都是大小相等的

研究人員通常根據(jù)算法是否可以被推廣應(yīng)用來(lái)定義可學(xué)習(xí)性。比如，算法會(huì)回答“是或否”類型的問(wèn)題，例如“這張圖是否是只貓？”。通過(guò)有限數(shù)量的數(shù)據(jù)進(jìn)行訓(xùn)練，然后應(yīng)用于猜測(cè)新數(shù)據(jù)的答案。

Yehudayoff和他的合作者在研究可學(xué)習(xí)性和“壓縮”之間的聯(lián)系時(shí)得出了結(jié)論，這意味著找到一種方法，來(lái)總結(jié)較小數(shù)據(jù)集中大量數(shù)據(jù)的顯著特征。 作者發(fā)現(xiàn)，信息被有效壓縮的能力可以被歸結(jié)為集合理論中的一個(gè)問(wèn)題——對(duì)象的數(shù)學(xué)集合，例如溫氏圖中的集合。特別是對(duì)于涉及包含無(wú)限多個(gè)對(duì)象的不同大小的集合。

集合論的創(chuàng)始人Georg Cantor在19世紀(jì)70年代證明，并非所有的無(wú)限集都是大小相等的：特別值得一提是，整數(shù)的集合比所有實(shí)數(shù)的集合“小”，也稱為連續(xù)統(tǒng)(continuum)。（實(shí)數(shù)包括無(wú)理數(shù)，有理數(shù)和整數(shù)。）Cantor還推測(cè)不可能存在“中間”大小的集合，即大于整數(shù)但小于連續(xù)統(tǒng)的集合。但他無(wú)法證明這種連續(xù)統(tǒng)假設(shè)，許多追隨他的數(shù)學(xué)家和邏輯學(xué)家也未能證明。

他們的努力是徒勞的。

G?del 1940年的成果（最終由美國(guó)數(shù)學(xué)家 Paul Cohen于20世紀(jì)60年代完成）表明，連續(xù)統(tǒng)假設(shè)不能從標(biāo)準(zhǔn)公理被證明為真或假——這一結(jié)論在集合理論上被認(rèn)為是真的，并通常被認(rèn)為是所有數(shù)學(xué)的基礎(chǔ)。

G?del 和Cohen關(guān)于連續(xù)統(tǒng)假設(shè)的研究表明，可以存在兼容標(biāo)準(zhǔn)數(shù)學(xué)的并行數(shù)學(xué)宇宙，其中一個(gè)連續(xù)統(tǒng)假設(shè)被添加到標(biāo)準(zhǔn)公理并因此被宣布為真，而另一個(gè)則被宣布為假。

可學(xué)習(xí)性的不穩(wěn)定性

在最新的論文中，Yehudayoff和他的合作者將可學(xué)習(xí)性定義為通過(guò)采樣少量數(shù)據(jù)點(diǎn)來(lái)預(yù)測(cè)較大數(shù)據(jù)集的能力。與Cantor問(wèn)題的聯(lián)系是，選擇較小的采樣集合的方式有無(wú)限種，但這個(gè)無(wú)限集合有多大卻是未知的。

論文作者繼續(xù)表明，如果連續(xù)統(tǒng)假設(shè)為真，那么一個(gè)小樣本就足以進(jìn)行外推。但如果它為假，那么將需要無(wú)限的樣本。通過(guò)這種方式，他們表明可學(xué)習(xí)性問(wèn)題等同于連續(xù)統(tǒng)假設(shè)。因此，可學(xué)習(xí)性問(wèn)題也處于不穩(wěn)定狀態(tài)，只有通過(guò)選擇公理宇宙才能解決。

Yehudayoff說(shuō)，這一結(jié)果也有助于更好地理解可學(xué)習(xí)性?！叭绻阆肓私狻畬W(xué)習(xí)’，壓縮和泛化之間的聯(lián)系非常重要?！?/p>

倫敦大學(xué)學(xué)院的計(jì)算機(jī)科學(xué)家Peter O’Hearn說(shuō)，研究人員發(fā)現(xiàn)了許多類似的“不可判定”問(wèn)題。特別是，繼G?del的工作之后，共同創(chuàng)立算法理論的Alan Turing發(fā)現(xiàn)了一類任何計(jì)算機(jī)程序都無(wú)法保證能在任何有限的步驟中解答的問(wèn)題。

但這種不可判定性是“罕見的”，而且更令人驚訝的是，O'Hearn補(bǔ)充說(shuō)：它指出了 G?del 的發(fā)現(xiàn)對(duì)任何數(shù)學(xué)語(yǔ)言都存在內(nèi)在不完整性。這些發(fā)現(xiàn)可能對(duì)機(jī)器學(xué)習(xí)理論很重要，盡管“不確定它會(huì)在實(shí)際應(yīng)用中產(chǎn)生多大影響”。