Математики обнаружили нерешаемую компьютером задачу

foo
foo

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

Проблема лежит в области машинного обучения - набора методов, алгоритмов и моделей, применяемых на компьютерах для «обучения», чтобы решать задачи определённого типа.

Когда фейсбук или гугл распознаёт чьё-то фото и предлагает сделать тэг, используется машинное обучение. Машинное обучение в действии, когда беспилотный автомобиль проезжает загруженный перекрёсток. Его методология основывается на математике, поэтому возможно создавать и развивать математический теоретический базис, ведущий к появлению новых ML-методов.

Команда математиков придумала ML-задачу под названием «оценка максимума», или EMX («estimating the maximum»).

Примеры, чтобы понять смысл постановки задачи: требуется организовать рекламу на веб-ресурсе таким способом, чтобы максимизировать отклик на неё посетителей. Имеется тематика для спортивных фанатов, любителей домашних животных, автолюбителей и так далее. Заранее неизвестно распределение визитёров сайта.

Модель решения задачи должна отвечать на поставленный вопрос по маленькому объёму посетителей.

В большей части проблематики machine learning можно установить, решаема ли задача в отдельном случае с определёнными данными. Может ли используемый Google метод распознавания лиц быть применённым, чтобы эффективно прогнозировать тренды рыночных акций?

В работе журнала Nature Machine Intelligence за 7 января доказано, что EMX напрямую зависит от Континуум-гипотезы.

Упомянутая гипотеза рассматривает различные виды бесконечностей. К примеру, есть бесконечная последовательность целых чисел, также есть бесконечная последовательность действительных чисел, включающая в себя первую последовательность. Хотя оба множества бесконечны, до каждой ограниченной величины вещественных чисел всегда больше, чем целых. Отсюда следует вопрос: есть ли бесконечное множество, которое «больше», чем целые числа, и «меньше», чем действительные. Или же, математическим языком, есть ли бесконечное множество с мощностью между мощностями множества целых чисел и континуума. Континуум-гипотеза говорит, что такого множества нет. Гёдель и Коэн обосновали невозможность доказательства гипотезы в аксиоматике Цермело-Френкеля, что означает, что в математике нет ответа на вопрос гипотезы при заданном наборе аксиом.

EMX применима в случае истинности Континуум-гипотезы. В обратном случае EMX бессильна. Это значит, что вся постановка исходной задачи имеет неопределённый ответ, так же, как и гипотеза.

Плюс ситуации в том, что Континуум-гипотеза не имеет большого математического значения. И сама проблематика может и не оказаться барьером машинному обучению.

EMX – это новая модель в machine learning, неизвестен уровень её полезности в реальных задачах, так что связанные с ней результаты могут не возыметь практической пользы. Но появление на повестке дня у математики такой задачи говорит о том, что машинное обучение значительно развилось как математическая дисциплина.


Комментарии