Салют, хабровчане! В преддверии запуска новых потоков по продвинутому и базовому курсам «Математика для Data Science» хотим поделиться с вами достаточно интересным переводом. В этой статье не будет практики, но материал интересен для общего развития и обсуждения.
Группа исследователей столкнулась с открытой математической проблемой, связанной с рядом логических парадоксов, которые были открыты знаменитым австрийским математиком Куртом Гёделем еще в 1930-х годах.
Математики, работавшие над проблемами машинного обучения, доказали, что возможность «обучаемости», то есть то, может ли алгоритм извлечь паттерн из ограниченных данных, тесно связана с парадоксом, известным как гипотеза континуума. Гедель говорил о том, что с помощью стандартных возможностей математического языка гипотезу нельзя ни подтвердить, ни опровергнуть. Последние результаты исследований на эту тему были опубликованы в Nature Machine Intelligence от 7 января.
«Для нас это было неожиданностью», — сказал Амир Иегудаев из Technion – Израильского Института Технологий в Хаифе, который был соавтором исследования. Он говорил о том, что несмотря на ряд технических вопросов, которые также известны как «неразрешимые», он не ожидал, что это явление встретится в, казалось бы, простой задаче машинного обучения.
Джон Такер, специалист по computer science Университета Суонси, Великобритания, говорит, что эта работа представляет из себя «весомый результат на границе наших знаний», с основополагающими последствиями как для математики, так и для машинного обучения.
Исследователи часто определяют обучаемость с точки зрения того, может ли алгоритм обобщать свои знания. Алгоритм дает ответ «да» или «нет», например, на вопрос «Есть ли на изображении кошка?» для ограниченного числа объектов, а затем он должен сделать прогноз для новых, ранее неизвестных ему, объектов.
Иегудаев и его коллеги получили результаты, исследуя связь между обучаемостью и «сжатием», которое включает в себя поиск способа отображения характерных признаков большого набора данных на меньший набор. Авторы обнаружили, что способность информации эффективно сжиматься сводится к вопросу теории множеств – математических совокупностей объектов, таких как множества в диаграммах Венна. В частности, это относится к множествам различного размера, содержащим бесконечно большое количество объектов.
Георг Кантор, основатель теории множеств, в 1870-х годах доказал, что не все бесконечные множества равны между собой: так, например, множество целых чисел «меньше», чем множество всех действительных чисел, также известное как континуум. (Поскольку действительные числа включают в себя иррациональные, а также рациональные и целые числа.) Кантор также предположил, что не существует множеств промежуточного размера, то есть большего, чем множество целых чисел, но меньшего, чем континуум. Но он не смог доказать эту гипотезу континуума, как и многие математики и логики – его последователи.
Их усилия оказались напрасны. В 1940 году Гедель провел исследование (которое было завершено только в 1960-х годах американском математиком Полом Коэном), в котором с помощью аксиом доказал, что гипотеза континуума не может быть ни истинной, ни ложной.
Работа Геделя и Коэна над гипотезой континуума допускает, что могут существовать параллельные математические вселенные, отвечающие законам стандартной математики: одна — в которой гипотеза континуума становится общепринятой аксиомой, то есть объявляется истинной, а вторая – в которой она же объявлена ложной.
В своей последней работе Иегудаев и его коллеги определяют обучаемость как способность делать прогнозы относительного большого набора данных путем выборки небольшого числа точек данных. Связь с проблемой Кантора заключается в том, что существует бесконечно много способов выбора меньшего множества, но размер этой бесконечности неизвестен.
Далее авторы показывают, что если гипотеза континуума верна, то для экстраполяции достаточно небольшой выборки. Но если же она ложна, то не может существовать конечной выборки, которая была бы достаточной. Таким образом, они полагают, что проблема обучаемости фактически эквивалентна гипотезе континуума. Как итог, проблема обучаемости также находится в состоянии неопределенности, которое может быть решено только путем выбора аксиоматической вселенной.
«Результат исследования также помогает сформировать более широкое понимание обучаемости», говорит Иегудаев. «Эта связь между сжатием и обобщением действительно фундаментальна в вопросе понимания процесса обучения.»
«Исследователи обнаружили ряд подобных «неразрешимых» проблем», говорит Питер О'Хирн, специалист по computer science из Университетского Колледжа в Лондоне. В частности, по результатам работ Геделя, Алан Тьюринг – один из основателей теории алгоритмов – обнаружил класс вопросов, на которые ни одна компьютерная программа не может гарантированно ответить за любое конечное число шагов.
«Однако неразрешимость, полученная в ходе последних исследований очень редка и гораздо более удивительна», добавляет О'Хирн: она указывает на то, что Гедель обнаружил внутреннюю неполноту любого рода математического языка. Полученные результаты, вероятно, окажутся важны для теории машинного обучения, однако вряд ли это окажет большое практическое влияние.
Пишите в комментарии, что думаете по поводу данного материала, а мы приглашаем вас на бесплатный вебинар, в рамках которого поговорим о методах регрессионного анализа в Data Science.
Группа исследователей столкнулась с открытой математической проблемой, связанной с рядом логических парадоксов, которые были открыты знаменитым австрийским математиком Куртом Гёделем еще в 1930-х годах.
Математики, работавшие над проблемами машинного обучения, доказали, что возможность «обучаемости», то есть то, может ли алгоритм извлечь паттерн из ограниченных данных, тесно связана с парадоксом, известным как гипотеза континуума. Гедель говорил о том, что с помощью стандартных возможностей математического языка гипотезу нельзя ни подтвердить, ни опровергнуть. Последние результаты исследований на эту тему были опубликованы в Nature Machine Intelligence от 7 января.
«Для нас это было неожиданностью», — сказал Амир Иегудаев из Technion – Израильского Института Технологий в Хаифе, который был соавтором исследования. Он говорил о том, что несмотря на ряд технических вопросов, которые также известны как «неразрешимые», он не ожидал, что это явление встретится в, казалось бы, простой задаче машинного обучения.
Джон Такер, специалист по computer science Университета Суонси, Великобритания, говорит, что эта работа представляет из себя «весомый результат на границе наших знаний», с основополагающими последствиями как для математики, так и для машинного обучения.
Не все наборы одинаковы
Исследователи часто определяют обучаемость с точки зрения того, может ли алгоритм обобщать свои знания. Алгоритм дает ответ «да» или «нет», например, на вопрос «Есть ли на изображении кошка?» для ограниченного числа объектов, а затем он должен сделать прогноз для новых, ранее неизвестных ему, объектов.
Иегудаев и его коллеги получили результаты, исследуя связь между обучаемостью и «сжатием», которое включает в себя поиск способа отображения характерных признаков большого набора данных на меньший набор. Авторы обнаружили, что способность информации эффективно сжиматься сводится к вопросу теории множеств – математических совокупностей объектов, таких как множества в диаграммах Венна. В частности, это относится к множествам различного размера, содержащим бесконечно большое количество объектов.
Георг Кантор, основатель теории множеств, в 1870-х годах доказал, что не все бесконечные множества равны между собой: так, например, множество целых чисел «меньше», чем множество всех действительных чисел, также известное как континуум. (Поскольку действительные числа включают в себя иррациональные, а также рациональные и целые числа.) Кантор также предположил, что не существует множеств промежуточного размера, то есть большего, чем множество целых чисел, но меньшего, чем континуум. Но он не смог доказать эту гипотезу континуума, как и многие математики и логики – его последователи.
Их усилия оказались напрасны. В 1940 году Гедель провел исследование (которое было завершено только в 1960-х годах американском математиком Полом Коэном), в котором с помощью аксиом доказал, что гипотеза континуума не может быть ни истинной, ни ложной.
Работа Геделя и Коэна над гипотезой континуума допускает, что могут существовать параллельные математические вселенные, отвечающие законам стандартной математики: одна — в которой гипотеза континуума становится общепринятой аксиомой, то есть объявляется истинной, а вторая – в которой она же объявлена ложной.
Лимб обучаемости
В своей последней работе Иегудаев и его коллеги определяют обучаемость как способность делать прогнозы относительного большого набора данных путем выборки небольшого числа точек данных. Связь с проблемой Кантора заключается в том, что существует бесконечно много способов выбора меньшего множества, но размер этой бесконечности неизвестен.
Далее авторы показывают, что если гипотеза континуума верна, то для экстраполяции достаточно небольшой выборки. Но если же она ложна, то не может существовать конечной выборки, которая была бы достаточной. Таким образом, они полагают, что проблема обучаемости фактически эквивалентна гипотезе континуума. Как итог, проблема обучаемости также находится в состоянии неопределенности, которое может быть решено только путем выбора аксиоматической вселенной.
«Результат исследования также помогает сформировать более широкое понимание обучаемости», говорит Иегудаев. «Эта связь между сжатием и обобщением действительно фундаментальна в вопросе понимания процесса обучения.»
«Исследователи обнаружили ряд подобных «неразрешимых» проблем», говорит Питер О'Хирн, специалист по computer science из Университетского Колледжа в Лондоне. В частности, по результатам работ Геделя, Алан Тьюринг – один из основателей теории алгоритмов – обнаружил класс вопросов, на которые ни одна компьютерная программа не может гарантированно ответить за любое конечное число шагов.
«Однако неразрешимость, полученная в ходе последних исследований очень редка и гораздо более удивительна», добавляет О'Хирн: она указывает на то, что Гедель обнаружил внутреннюю неполноту любого рода математического языка. Полученные результаты, вероятно, окажутся важны для теории машинного обучения, однако вряд ли это окажет большое практическое влияние.
Пишите в комментарии, что думаете по поводу данного материала, а мы приглашаем вас на бесплатный вебинар, в рамках которого поговорим о методах регрессионного анализа в Data Science.
