Математики доказали, что алгоритмы машинного обучения упираются в проблему теории множеств, не имеющую решения по фундаментальным причинам.

Амир Йегудайоф из университета Тель-Авива и его коллеги занимались прикладной математической задачей — алгоритмами машинного обучения. Неожиданно оказалось, однако, что эта проблема упирается в фундаментальный математический парадокс, обнаруженный великими математиками XIX-ХХ веков Георгом Кантором и Куртом Гёделем. А именно, вопрос о том, достигает ли успеха алгоритм машинного обучения, оказался фундаментально неразрешимым. Об этом сообщает статья, опубликованная 7 января в Nature Machine Intelligence.

Предыстория вопроса: знаменитые парадоксы ХХ века Наглядный пример парадокса, обнаруженного математиком Бертраном Расселом еще столетие назад, дает задача о двух каталогах. Согласно ее условиям, в библиотеке все книги должны быть внесены в один из двух каталогов: в первый вносятся те книги, где есть ссылка на самих себя, а во второй — те, в которых ссылка на себя отсутствует. Поскольку эти каталоги сами представляют собой книги, их также нужно внести в один из каталогов. Однако сложность в том, что если в первый каталог можно записать ссылку на сам этот каталог (а можно и не записывать — все равно условие будет выполнено), то второй каталог нельзя записать никуда. Но и не записывать его тоже нельзя: условие задачи будет нарушено в любом случае.

Размышления о расселовском парадоксе привели Курта Геделя к формулировке его знаменитой «теоремы о неполноте». Рассуждал он так: возьмем некую систему математических аксиом и составим полный список всех возможных математических утверждений, которые следуют из этих аксиом (нечто вроде библиотечного каталога). Тогда, доказал Гёдель, можно сконструировать истинное математическое утверждение, которого точно не будет в этом списке («второй каталог» в вышеприведенном примере). Таким образом, любая система аксиом, даже бесконечная, обязательно окажется неполной: некоторое истинное утверждение будет невозможно вывести из нее математически. Оно будет, как выражаются математики, «неразрешимым» (undecidable). Но даже если назвать это утверждение «аксиомой» и добавить к списку, новая система аксиом снова окажется неполной: для нее также можно будет сконструировать недоказуемое и неопровержимое утверждение.

Один из примеров геделевского неразрешимого утверждения — «проблема континуума», сформулированная Георгом Кантором. Немецкий математик сравнивал разные бесконечные множества и обнаружил, что они отличаются друг от друга по «мощности». В частности, множества натуральных, рациональных и действительных чисел бесконечны. Однако если натуральные и рациональные числа можно поставить в соответствие друг другу (мощность этих множеств равна), то с действительными числами это не работает: его элементы расположены гораздо «гуще».

Кантор задал вопрос: а есть ли множества, мощность которых больше, чем у множества натуральных чисел, но меньше, чем у действительных? Ответ на этот вопрос он дать не смог, а в 1940 году Гедель доказал, что это как раз и есть пример неразрешимого утверждения в рамках теории множеств. Можно сказать, что множеств промежуточной мощности не существует — и это утверждение станет частью непротиворечивой математической системы. Но можно утверждать и обратное, и в результате опять получится непротиворечивая система утверждений, хотя и отличная от первой.

Английский математик Алан Тьюринг развил идею Геделя в применении к вычислительным алгоритмам. Он доказал, что в списке «всех возможных алгоритмов, приводящих к решению задачи» будет заведомо отсутствовать алгоритм, устанавливающий, приведет ли к решению некий произвольный алгоритм. На этом основании современный британский математик Роджер Пенроуз выдвинул аргументированную гипотезу, согласно которой человеческое мышление принципиально неалгоритмизируемо. Из этой гипотезы следует, что «искусственный интеллект» в точном смысле этого слова невозможен: определенный класс задач, решаемых человеческим мозгом, возможно, представляет собой неразрешимые тьюринговские алгоритмы.

Суть проблемы: парадокс машинного обучения

В ХХ веке казалось, что геделевские неразрешимые утверждения носят довольно абстрактный характер и не имеют отношения к прикладным задачам. Несколько лет назад, впрочем, группа физиков-теоретиков во главе с Тони Кьюбиттом доказала, что геделевская неразрешимость возникает в физической задаче «квантового гэпа»: невозможно вычислить теоретически, окажется ли произвольно большая пластина некоего материала сверхпроводником.

Авторы статьи в Nature занимались еще более прикладной проблемой — машинным обучением. Обычно подобные задачи выглядят так: алгоритму предъявляют «обучающие» конечные наборы данных, в которых требуется, к примеру, научиться распознавать изображение котенка. Задача обучения считается решенной, если алгоритм будет способен безошибочно «находить котят» в произвольно большом, то есть бесконечном, наборе данных.

Йегудайоф и его коллеги изучали взаимосвязь между обучаемостью и «сжатием» данных. Они обнаружили, что вопрос о сжимаемости информации тесно связан с проблемой континуума Кантора — которая, как сказано выше, математически неразрешима. Существует бесконечно много способов выбрать из бесконечно большого набора данных меньший набор. Однако «мощность» этой бесконечности оставалась неизвестной. Авторы показали, что эта «мощность» как раз и характеризуется неразрешимостью в рамках проблемы континуума. А именно, если принять гипотезу Кантора, то всегда найдется малый набор обучающих данных, на основании которого алгоритм научится делать предсказания — «искать котенка» — в произвольно большой выборке. Но если принять обратное утверждение, то есть допустить существование множеств промежуточной мощности, никакая выборка данных не даст гарантии успеха.

По мнению авторов работы, обнаруженный парадокс очень важен для понимания принципов сжатия данных, лежащих в основах машинного обучения. В то же время его практическая значимость остается под вопросом: бесконечные наборы данных представляют собой математическую абстракцию. Тем не менее подобные исследования, указывающие на фундаментальные границы алгоритмического «мышления», очень важны для понимания перспектив разработки систем искусственного интеллекта, а в конечном итоге — для понимания феномена человеческого разума.