Исследователи MIT CSAIL создали метод выборки с низким уровнем погрешности на основе ИИ, который равномерно распределяет точки данных для повышения точности моделирования.
Представьте, что вам нужно отправить команду футболистов на поле, чтобы оценить состояние травы (конечно, это вполне реальная задача для них). Если вы распределите их случайным образом, они могут собраться в одних местах, полностью игнорируя другие. Но если вы дадите им стратегию, например, равномерно рассредоточиться по полю, вы сможете получить гораздо более точное представление о состоянии травы.
А теперь представьте, что вам нужно распространиться не только в двух измерениях, но и в десятках или даже сотнях. Именно такую задачу решают исследователи Лаборатории компьютерных наук и искусственного интеллекта Массачусетского технологического института (CSAIL). Они разработали основанный на искусственном интеллекте подход к «выборочному моделированию с низкой погрешностью» — метод, который повышает точность моделирования за счёт более равномерного распределения точек данных в пространстве.
Ключевая новизна заключается в использовании графовых нейронных сетей (GNN), которые позволяют точкам «общаться» и самооптимизироваться для достижения большей однородности. Этот подход является важным усовершенствованием для моделирования в таких областях, как робототехника, финансы и вычислительная наука, особенно при решении сложных многомерных задач, критически важных для точного моделирования и численных вычислений.
«Во многих задачах, чем равномернее вы распределяете точки, тем точнее вы можете моделировать сложные системы», — говорит Т. Константин Руш, ведущий автор новой статьи и научный сотрудник MIT CSAIL. «Мы разработали метод под названием «Монте-Карло с передачей сообщений» (MPMC) для создания равномерно распределённых точек с помощью методов геометрического глубокого обучения. Это позволяет нам создавать точки, которые подчёркивают измерения, особенно важные для конкретной задачи, что очень важно во многих приложениях». Графовые нейронные сети, лежащие в основе модели, позволяют точкам «общаться» друг с другом, обеспечивая гораздо более равномерное распределение, чем предыдущие методы».
Их работа была опубликована в сентябрьском выпуске журнала«Труды Национальной академии наук».
Отвези меня в Монте-Карло
Идея методов Монте-Карло заключается в том, чтобы изучать систему, моделируя её с помощью случайной выборки. Выборка — это отбор подмножества совокупности для оценки характеристик всей совокупности. Исторически этот метод использовался ещё в XVIII веке, когда математик Пьер-Симон Лаплас применил его для оценки численности населения Франции без необходимости подсчитывать каждого человека.
Последовательности с низким расхождением, которые представляют собой последовательности с низким расхождением, то есть с высокой однородностью, такие как Соболь, Халтон и Нидеррайтер, долгое время были золотым стандартом квазислучайной выборки, которая заменяет случайную выборку выборкой с низким расхождением. Они широко используются в таких областях, как компьютерная графика и вычислительные финансы, для всего, от вариантов ценообразования до оценки рисков, где равномерное заполнение пробелов точками может привести к более точным результатам.
Предлагаемая командой структура MPMC преобразует случайные выборки в точки с высокой однородностью. Это достигается путём обработки случайных выборок с помощью GNN, которая минимизирует определённую меру несоответствия.
Одна из серьёзных проблем, связанных с использованием ИИ для создания очень однородных точек, заключается в том, что обычный способ измерения однородности точек очень медленный и с ним трудно работать. Чтобы решить эту проблему, команда перешла на более быстрый и гибкий способ измерения однородности, называемый L2-расхождением. Для задач с большим количеством измерений, где этого метода недостаточно, они используют новую технику, которая фокусируется на важных низкоразмерных проекциях точек. Таким образом, они могут создавать наборы точек, которые лучше подходят для конкретных задач.
По словам команды, последствия выходят далеко за рамки академических кругов. Например, в вычислительном финансировании моделирование в значительной степени зависит от качества точек выборки. «При использовании таких методов случайные точки часто оказываются неэффективными, но точки с низким уровнем отклонений, сгенерированные с помощью GNN, обеспечивают более высокую точность, — говорит Руш. — Например, мы рассмотрели классическую задачу из области вычислительного финансирования в 32 измерениях, где наши точки MPMC превзошли предыдущие современные методы квазислучайной выборки в 4–24 раза».
Роботы в Монте-Карло
В робототехнике планирование пути и движения часто основывается на алгоритмах, основанных на выборке, которые помогают роботам принимать решения в режиме реального времени. Улучшенная однородность MPMC может привести к более эффективной навигации роботов и адаптации в режиме реального времени для таких задач, как автономное вождение или беспилотные технологии. «На самом деле, в недавней статье, опубликованной в препринте, мы продемонстрировали, что наши точки MPMC в четыре раза лучше предыдущих методов с низкой погрешностью при применении к реальным задачам планирования движения в робототехнике», — говорит Руш.
«Традиционные последовательности с низкой дисперсией были большим достижением в своё время, но мир стал сложнее, и проблемы, которые мы решаем сейчас, часто существуют в 10-, 20- или даже 100-мерных пространствах, — говорит Даниэла Рус, директор CSAIL и профессор Массачусетского технологического института в области электротехники и информатики. — Нам нужно было что-то более умное, что-то, что адаптируется по мере роста размерности. GNN — это смена парадигмы в том, как мы генерируем наборы точек с низкой дисперсией. В отличие от традиционных методов, где точки генерируются независимо друг от друга, GNN позволяют точкам «общаться» друг с другом, чтобы сеть научилась размещать точки таким образом, чтобы уменьшить кластеризацию и пробелы — распространённые проблемы при использовании типичных подходов».
В дальнейшем команда планирует сделать точки MPMC ещё более доступными для всех, устранив существующее ограничение, связанное с обучением новой GNN для каждого фиксированного количества точек и измерений.
«Большая часть прикладной математики использует непрерывно изменяющиеся величины, но вычисления, как правило, позволяют использовать только конечное число точек, — говорит Арт Б. Оуэн, профессор статистики Стэнфордского университета, который не участвовал в исследовании. — Область несоответствия, существующая уже более века, использует абстрактную алгебру и теорию чисел для определения эффективных точек выборки. В этой статье используются графовые нейронные сети для поиска входных точек с низким несоответствием по сравнению с непрерывным распределением. Этот подход уже очень близок к наиболее известным наборам точек с низкой погрешностью для небольших задач и показывает большие перспективы для 32-мерного интеграла в области вычислительных финансов. Мы можем ожидать, что это будет первая из многих попыток использовать нейронные методы для поиска хороших входных точек для численных вычислений».
Раш и Рус написали статью в соавторстве с исследователем из Университета Ватерлоо Натаном Кирком, профессором искусственного интеллекта DeepMind в Оксфордском университете и бывшим сотрудником CSAIL Майклом Бронштейном, а также с профессором статистики и актуарных наук в Университете Ватерлоо Кристиан Лемье. Их исследование частично финансировалось программой AI2050 в Schmidt Sciences, компанией Boeing, Исследовательской лабораторией ВВС США и Ускорителем искусственного интеллекта ВВС США, Швейцарским национальным научным фондом, Советом по естественным наукам и инженерным исследованиям Канады, а также программой EPSRC Turing AI World-Leading Research Fellowship.