Простая проблема искусственного интеллекта ставит исследователей перед логическим парадоксом, открытым известным математиком Куртом Геделем.
Австрийский математик Курт Гедель известен своими теоремами "неполноты". Фото: Alfred Eisenstaedt/ LIFE Picture Coll./Getty
Однажды команда исследователей наткнулась на задачу, которую невозможно решить математически, т.к. она оказалась связана с логическими парадоксами. Эти парадоксы, которые не могут быть решены с помощью стандартной математики, были обнаружены в 1930-х годах австрийским математиком Куртом Геделем.
Математики, которые работали над проблемой машинного обучения, доказывают, что вопрос "обучаемости", а именно сможет ли алгоритм извлечь шаблон из ограниченных данных, связан с парадоксом, известным как гипотеза континуума. Гедель показал, что утверждение не может быть доказано ни истинным, ни ложным с помощью стандартного математического языка. Последний результат появился 7 января в Nature Machine Intelligence.
" Для нас это было неожиданностью", - говорит соавтор статьи Амир Ехудайофф (Amir Yehudayoff) из Техниона - Израильского технологического института в Хайфе. Он говорит, что хотя и есть ряд "неразрешимых", технических математических вопросов, он не ожидал, что это явление проявится в относительно простой проблеме в машинном обучении.
Джон Такер (John Tucker), компьютерный ученый из Университета Суонси, Великобритания, говорит, что доклад является "тяжеловесным результатом на границах наших знаний", с основополагающими последствиями как для математики, так и для машинного обучения.
Не все наборы данных одинаковы
Исследователи часто определяют обучаемость с точки зрения того, может ли алгоритм обобщать свои знания. Алгоритм получает ответ на вопрос "да или нет". Например: "Показывает ли это изображение кошку?" – ответ должен быть дан на основании ограниченного количества объектов, а затем, на основании этого, должен быть дан ответ для новых объектов.
Ехудайофф и его коллеги пришли к своему результату, исследуя связь между обучаемостью и "сжатием", что включает в себя поиск способа суммировать характерные черты большого набора данных в меньшем наборе данных. Авторы обнаружили, что способность информации к эффективному сжатию сводится к вопросу в теории множеств - математических коллекций объектов, таких, как множества в диаграммах Венна. В частности, это относится к различным размерам множеств, содержащих бесконечно много объектов.
Георг Кантор (Georg Cantor), основатель теории множеств, продемонстрировал в 1870-х годах, что не все бесконечные множества созданы равными: в частности, множество целых чисел "меньше" множества всех вещественных чисел, также известного как континуум. (Действительные числа включают иррациональные числа, а также рациональные и целые числа.) Кантор также предположил, что не может быть множеств промежуточного размера — то есть больше целых чисел, но меньше континуума. Но он не смог доказать эту гипотезу континуума, и не было большого числа математиков и логиков, которые бы последовали за ним.
Их усилия были напрасны. В 1940 году результат Геделя (он был завершен в 1960-х годах американским математиком полом Коэном) показал, что гипотеза континуума не может быть доказана ни истинной, ни ложной, начиная со стандартных аксиом — утверждений, которые считаются истинными, т.е. теории множеств, которые обычно принимаются за основу для всей математики.
Работа Геделя и Коэна над гипотезой континуума подразумевает, что могут существовать параллельные математические Вселенные, которые совместимы со стандартной математикой — одна, в которой гипотеза континуума добавляется к стандартным аксиомам и поэтому объявляется истинной, а другая, в которой она объявляется ложной.
Обучаемость в состоянии неопределенности
В последней публикации Ехудайофф и его коллеги определяют обучаемость как способность делать прогнозы о большом наборе данных путем выборки небольшого числа элементов данных. Связь с проблемой Кантора состоит в том, что существует бесконечно много способов выбора меньшего множества, но размер этой бесконечности неизвестен.
Далее авторы показывают, что если гипотеза континуума верна, то для экстраполяции достаточно небольшой выборки. Но если оно ложно, то никакая конечная выборка не может быть достаточной. Таким образом они показывают, что проблема обучаемости эквивалентна гипотезе континуума. Следовательно, проблема обучаемости также находится в состоянии неопределенности, которую можно решить, только путем выбора аксиоматической вселенной.
Результат также помогает дать более широкое понимание обучаемости, говорит Йехудайофф. "Эта связь между сжатием и обобщением действительно фундаментальна, если вы хотите понять обучение."
"Исследователи обнаружили ряд подобных "неразрешимых" проблем", - говорит Питер О'Хирн (Peter O'Hearn), специалист по информатике в Университетском колледже Лондона. В частности, после работы Геделя Алан Тьюринг (Alan Turing), соучредитель теории алгоритмов, обнаружил класс вопросов, на которые ни одна компьютерная программа не может гарантировать ответ за любое конечное число шагов.
"Неразрешимость в последних результатах "довольно редка", и, что еще более удивительно, - говорит О'Хирн, – это указывает на то, что Гедель обнаружил внутреннюю незавершенность в любом математическом языке. Выводы, вероятно, будут важны для теории машинного обучения, хотя, я не уверен, что это окажет большое влияние на практику ", - добавляет он.
Оригинал статьи на сайте
Автор статьи: Davide Castelvecchi
