Искусственный интеллект оказался неразрешимой задачей
Амир Йегудайоф из университета Тель-Авива и его коллеги занимались прикладной математической задачей — алгоритмами машинного обучения. Неожиданно оказалось, однако, что эта проблема упирается в фундаментальный математический парадокс, обнаруженный великими математиками XIX-ХХ веков, Георгом Кантором и Куртом Гёделем. А именно, вопрос о том, достигает ли успеха алгоритм машинного обучения, оказался фундаментально неразрешимым. Об этом сообщает статья , опубликованная 7 января в Nature Machine Intelligence.
Предыстория вопроса: знаменитые парадоксы ХХ века
Наглядный пример парадокса, обнаруженного математиком Бертраном Расселом еще столетие назад, дает задача о двух каталогах. Согласно ее условиям, в библиотеке все книги должны быть внесены в один из двух каталогов: в первый вносятся те книги, где есть ссылка на самих себя, а во второй — те, в которых ссылка на себя отсутствует. Поскольку эти каталоги сами представляют собой книги, их также нужно внести в один из каталогов. Однако сложность в том, что если в первый каталог можно записать ссылку на сам этот каталог (а можно и не записывать — все равно условие будет выполнено), то второй каталог нельзя записать никуда. Но и не записывать его тоже нельзя: условие задачи будет нарушено в любом случае.
Размышления о расселловском парадоксе привели Курта Геделя к формулировке его знаменитой «теоремы о неполноте». Рассуждал он так: возьмем некую систему математических аксиом и составим полный список всех возможных математических утверждений, которые следуют из этих аксиом (нечто вроде библиотечного каталога). Тогда, доказал Гёдель, можно сконструировать истинное математическое утверждение, которого точно не будет в этом списке («второй каталог» в вышеприведенном примере). Таким образом, любая система аксиом, даже бесконечная, обязательно окажется неполной: некоторое истинное утверждение будет невозможно вывести из нее математически. Оно будет, как выражаются математики, «неразрешимым» (undecidable). Но даже если назвать это утверждение «аксиомой» и добавить к списку, новая система аксиом снова окажется неполной: для нее также можно будет сконструировать недоказуемое и неопровержимое утверждение.
Один из примеров геделевского неразрешимого утверждения — «проблема континуума», сформулированная Георгом Кантором. Немецкий математик сравнивал разные бесконечные множества и обнаружил, что они отличаются друг от друга по «мощности». В частности, множества натуральных, рациональных и действительных чисел бесконечны. Однако если натуральные и рациональные числа можно поставить в соответствие друг другу (мощность этих множеств равна), то с действительными числами это не работает: его элементы расположены гораздо «гуще».
Кантор задал вопрос: а есть ли множества, мощность которых больше, чем у множества натуральных чисел, но меньше, чем у действительных? Ответ на этот вопрос он дать не смог, а в 1940 г. Гедель доказал, что это как раз и есть пример неразрешимого утверждения в рамках теории множеств. Можно сказать, что множеств промежуточной мощности не существует — и это утверждение станет частью непротиворечивой математической системы. Но можно утверждать и обратное, и в результате опять получится непротиворечивая система утверждений, хотя и отличная от первой.
Английский математик Алан Тьюринг развил идею Геделя в применении к вычислительным алгоритмам. Он доказал, что в списке «всех возможных алгоритмов, приводящих к решению задачи» будет заведомо отсутствовать алгоритм, устанавливающий, приведет ли к решению некий произвольный алгоритм. На этом основании современный британский математик Роджер Пенроуз выдвинул аргументированную гипотезу, согласно которой человеческое мышление принципиально неалгоритмизируемо. Из этой гипотезы следует, что «искусственный интеллект» в точном смысле этого слова невозможен: определенный класс задач, решаемых человеческим мозгом, возможно, представляет собой неразрешимые тьюринговские алгоритмы.
Суть проблемы: парадокс машинного обучения
В ХХ веке казалось, что геделевские неразрешимые утверждения носят довольно абстрактный характер и не имеют отношения к прикладным задачам. Несколько лет назад, впрочем, группа физиков-теоретиков во главе с Тони Кьюбиттом доказала, что геделевская неразрешимость возникает в физической задаче «квантового гэпа»: невозможно вычислить теоретически, окажется ли произвольно большая пластина некоего материала сверхпроводником.
Авторы статьи в Nature занимались еще более прикладной проблемой — машинным обучением. Обычно подобные задачи выглядят так: алгоритму предъявляют «обучающие» конечные наборы данных, в которых требуется, к примеру, научиться распознавать изображение котенка. Задача обучения считается решенной, если алгоритм будет способен безошибочно «находить котят» в произвольно большом, то есть бесконечном, наборе данных.
Йегудайоф и его коллеги изучали взаимосвязь между обучаемостью и «сжатием» данных. Они обнаружили, что вопрос о сжимаемости информации тесно связан с проблемой континуума Кантора — которая, как сказано выше, математически неразрешима. Существует бесконечно много способов выбрать из бесконечно большого набора данных меньший набор. Однако «мощность» этой бесконечности оставалась неизвестной. Авторы показали, что эта «мощность» как раз и характеризуется неразрешимостью в рамках проблемы континуума. А именно, если принять гипотезу Кантора, то всегда найдется малый набор обучающих данных, на основании которого алгоритм научится делать предсказания — «искать котенка» — в произвольно большой выборке. Но если принять обратное утверждение, то есть допустить существование множеств промежуточной мощности, никакая выборка данных не даст гарантии успеха.
По мнению авторов работы , обнаруженный парадокс очень важен для понимания принципов сжатия данных, лежащих в основах машинного обучения. В то же время его практическая значимость остается под вопросом: бесконечные наборы данных представляют собой математическую абстракцию. Тем не менее, подобные исследования, указывающие на фундаментальные границы алгоритмического «мышления», очень важны для понимания перспектив разработки систем искусственного интеллекта, а в конечном итоге — для понимания феномена человеческого разума.
