Доказана неразрешимость одной из моделей машинного обучения

Математики совместно со специалистами в области компьютерных наук доказали неразрешимость одной из моделей машинного обучения. Соответствующая статья опубликована в журнале Nature Machine Intelligence.

Существование задач, которые невозможно ни доказать, ни опровергнуть в рамках стандартных аксиом математики, было обосновано Гёделем в 1931 году. Примером такого утверждения является континуум-гипотеза. Она говорит, что не существует множества, чья мощность была бы больше, чем у множества целых чисел ℤ, но меньше, чем у множества всех чисел из отрезка [0,1] (два множества имеют одинаковую мощность, если между их элементами можно установить взаимно однозначное соответствие). Тот факт, что множество целых чисел и множество точек отрезка имеют разные мощности, был доказан Георгом Кантором в конце XIX века, он же и сформулировал саму гипотезу.

Модель EMX, рассматриваемая авторами статьи, сформулирована в парадигме вероятностно приблизительно корректного обучения (PAC-learning) — наиболее математически обоснованной модели статистического обучения. Примером задачи, описываемой моделью PAC, может быть задача о бинарной классификации спама во входящих письмах на основе конечной выборки. Фундаментальный результат гласит, что обучение теоретически осуществимо тогда и только тогда, когда конечна размерность Вапника-Червоненкиса — количественная характеристика множества возможных гипотез модели (на практике задача о классификации спама обычно решается с помощью метода опорных векторов, нейронных сетей, случайного леса и других алгоритмов).

Модель EMX имеет то же математическое описание, что и PAC, но различается на уровне контекста. Например, ее можно интерпретировать как задачу таргетинга рекламы. Допустим, среди набора рекламных объявлений требуется выбрать то, которое с высокой вероятностью заинтересует как можно большее количество пользователей; решение принимается на основе выборки с неизвестным распределением. Оказывается, эта задача в общей постановке с бесконечным общим числом пользователей эквивалентна континуум-гипотезе, а следовательно неразрешима.

Промежуточным шагом в доказательстве эквивалентности послужила связь между машинным обучением и задачей сжатия данных, обнаруженная в 80-х годах. Грубо говоря, если существует способ уменьшить выборку, не теряя возможности определить категорию пользователей, которые интересует данное рекламное объявление, то существует и способ обучиться выбору почти самой популярной рекламе. В свою очередь, мощность бесконечных множеств, о которых говорится в континуум-гипотезе, несложно привязать к задаче сжатия данных.

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

Как признаются сами авторы, модель EMX может и не иметь практического интереса, однако этот результат дает нам больше понимания о теоретических ограничениях моделей машинного обучения, чьи алгоритмы столь успешно справляются с задачами распознавания лиц, почерка, раковых клеток и многого другого.

Отметим, что журнал Nature Machine Intelligence был создан сравнительно недавно, но после опубликованной статьи ему уже объявили бойкот в ML-сообществе.

Иван Тельпуховский