Learnability can be undecidable

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F19%3A00500071" target="_blank" >RIV/67985840:_____/19:00500071 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1038/s42256-018-0002-3" target="_blank" >http://dx.doi.org/10.1038/s42256-018-0002-3</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1038/s42256-018-0002-3" target="_blank" >10.1038/s42256-018-0002-3</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Learnability can be undecidable

Popis výsledku v původním jazyce

The mathematical foundations of machine learning play a key role in the development of the field. They improve our understanding and provide tools for designing new learning paradigms. The advantages of mathematics, however, sometimes come with a cost. Gödel and Cohen showed, in a nutshell, that not everything is provable. Here we show that machine learning shares this fate. We describe simple scenarios where learnability cannot be proved nor refuted using the standard axioms of mathematics. Our proof is based on the fact the continuum hypothesis cannot be proved nor refuted. We show that, in some cases, a solution to the ‘estimating the maximum’ problem is equivalent to the continuum hypothesis. The main idea is to prove an equivalence between learnability and compression.

Název v anglickém jazyce

Learnability can be undecidable

Popis výsledku anglicky

The mathematical foundations of machine learning play a key role in the development of the field. They improve our understanding and provide tools for designing new learning paradigms. The advantages of mathematics, however, sometimes come with a cost. Gödel and Cohen showed, in a nutshell, that not everything is provable. Here we show that machine learning shares this fate. We describe simple scenarios where learnability cannot be proved nor refuted using the standard axioms of mathematics. Our proof is based on the fact the continuum hypothesis cannot be proved nor refuted. We show that, in some cases, a solution to the ‘estimating the maximum’ problem is equivalent to the continuum hypothesis. The main idea is to prove an equivalence between learnability and compression.

Druh

J_ost - Ostatní články v recenzovaných periodicích

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Nature Machine Intelligence

ISSN

2522-5839

e-ISSN

—

Svazek periodika

1

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

5

Strana od-do

44-48

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—