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

一個徹頭徹尾的悖論。

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

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

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

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

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

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

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

并非所有無限集合都是大小相等的

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

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

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

他們的努力是徒勞的。

G?del 1940年的成果（最終由美國數(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é)宇宙，其中一個連續(xù)統(tǒng)假設(shè)被添加到標(biāo)準(zhǔn)公理并因此被宣布為真，而另一個則被宣布為假。

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

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

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

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

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

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