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

一個徹頭徹尾的悖論。

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

而今，這一朵烏云出人意料地降臨到了機器學習界，或將“顛覆”機器學習理論。

這一研究的最新結果已被發表于1月7日的Nature Machine Intelligence。

那么，什么是“連續統假設(continuum hypothesis)”？這一假設對機器學習而言又意味著什么呢?

近日，幾位研究機器學習問題的數學家表示，“可學習性”問題——即算法能否從有限的數據中提取模式——與被稱為連續統假設(continuum hypothesis)的悖論有關。數學家G?del曾表示，使用標準數學語言不能證明該假設是真是假。

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

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

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

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

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

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

他們的努力是徒勞的。

G?del 1940年的成果（最終由美國數學家 Paul Cohen于20世紀60年代完成）表明，連續統假設不能從標準公理被證明為真或假——這一結論在集合理論上被認為是真的，并通常被認為是所有數學的基礎。

G?del 和Cohen關于連續統假設的研究表明，可以存在兼容標準數學的并行數學宇宙，其中一個連續統假設被添加到標準公理并因此被宣布為真，而另一個則被宣布為假。

可學習性的不穩定性

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

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

Yehudayoff說，這一結果也有助于更好地理解可學習性。“如果你想了解‘學習’，壓縮和泛化之間的聯系非常重要。”

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

但這種不可判定性是“罕見的”，而且更令人驚訝的是，O'Hearn補充說：它指出了 G?del 的發現對任何數學語言都存在內在不完整性。這些發現可能對機器學習理論很重要，盡管“不確定它會在實際應用中產生多大影響”。