Главная ложь XXI века: «Данных много не бывает». MIT доказали обратное

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

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

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

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

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

Статья, препринт которой размещен на сервере arXiv, подготовлена совместно с аспирантом кафедры электротехники и информатики Омаром Беннуна, его братом Амином Беннуна, ранее работавшим в MIT, а сейчас преподающим в Северо-Западном университете, и Саурабом Амином, профессором кафедры гражданского строительства и экологической инженерии MIT. Результаты будут представлены на конференции Neural Information Processing Systems (NeurIPS 2025), которая пройдет с 30 ноября по 5 декабря в Сан-Диего.

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

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

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

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

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

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

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

Численные эксперименты показали, что с помощью этого подхода можно обеспечивать оптимальный выбор, опираясь на набор данных, который намного меньше того, что обычно собирают на практике. «Мы оспариваем распространенное представление, что малый объем данных означает лишь приблизительные ответы. В нашей работе речь идет о строгих результатах достаточности, подкрепленных математическими доказательствами. Мы показали, что можно гарантировать получение оптимального решения при очень небольшом объеме данных, и это именно гарантия, а не вероятность», подчеркивает Амин Беннуна.

В дальнейшем исследователи планируют расширить свой подход на другие классы задач и более сложные структуры, а также изучить, как на достаточность наборов данных влияют шум и погрешности измерений. Профессор Яо Се из Технологического института Джорджии, не участвовавшая в работе, отмечает, что ее впечатлили оригинальность идеи, ясность изложения и элегантный геометрический подход. По ее словам, предложенный каркас предлагает новый взгляд на эффективность использования данных при принятии решений и оптимизации.