Прошли те времена, когда вы были в дороге, не имея ни малейшего представления о том, когда вы достигнете пункта назначения. Запущенные 17 лет назад, Карты Google значительно повлияли на нашу повседневную жизнь, полностью изменив динамику навигации. Люди полагаются на Карты Google не только для расчетныхрасчетных временприбытий (ETA), но он также широко используется такими предприятиями, как компании, занимающиеся прокатом автомобилей, для предоставления своим услугам информации о времени посадки и высадки пассажиров, а также ориентировочных цен в зависимости от продолжительности поездки.

В этой статье мы пытаемся демистифицировать алгоритм прогнозирования ETA, используемый в Google Maps, хотя предполагается, что читатели имеют базовое представление о нейронных сетях.

Как выглядит прогноз ETA

Прогнозирование ожидаемого времени прибытия включает моделирование как топологических свойств дорожной сети, так и временных свойств, таких как прогнозирование событий, таких как часы пик, которые могут произойти в будущем. Это достигается путем применения оценки GNeural Neural Nnetwork (GNN) от данных трафика в реальном времени и путем используя методы расписания обучения, такие как MetaGradients, чтобы сделать модель надежной. Модель GNN значительно снизила отрицательные результаты ETA в нескольких регионах по сравнению с предыдущим базовым уровнем производства (40+% в таких городах, как Сидней).

Разделим мир

В этом разделе статьи мы попытаемся объяснить постановку задачи оценки времени в пути в контексте прогнозирования ETA.

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

Суперсегмент S определяется как граф S = (𝑆, 𝐸), где каждый узел 𝑠 ∈ 𝑆 является сегментом дороги, а ребро eᵢⱼ ∈ 𝐸 существует, если два сегмента 𝑠ᵢ и 𝑠ⱼ соединены (обзор см. на рис. 3). ). Тогда задача прогнозирования времени в пути на суперсегменте выглядит так: для суперсегмента Sₜ предсказать время в пути на суперсегменте на разных горизонтах в будущее , ..., hₖ соответствуют разным горизонтам. [1]

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

Функции – для этой задачи использовались как реальные, так и исторические шаблоны трафика с учетом времени суток и дня недели, когда предсказание сделано. Использовались следующие функции:

  • Уровень сегмента (узла) — средняя скорость и время движения сегмента в реальном времени и за прошлые периоды, длина сегмента и приоритет сегмента (например, классификации дорог, такие как автомагистрали);
  • Уровень суперсегмента (графика) — время в пути суперсегмента в реальном времени.

Оценка чудесной архитектуры

Теперь мы закончили закладывать основу, чтобы глубже погрузиться в архитектурные особенности моделей GNN, используемых для прогнозирования ETA. Итак, приступим к делу немедленно. Извините, что разочаровал вас, если вы ожидали увидеть здесь могольскую или византийскую архитектуру.

В GNN выполняется алгоритм передачи сообщений, при котором сообщения и их влияние на состояния ребер и узлов изучаются нейронными сетями. В модели GNN, используемой для прогнозирования ETA, блоки Graph Nnetwork (GN) используются с использованием уравнений, как показано на рисунке 4 ниже.

Блок GN определяется тремя функциями «обновления» 𝜙, соответствующими обновлениям ребра, узла и глобального уровня или уровня суперсегмента, и тремя функциями «агрегации» ρ. Все функции обновления, 𝜙, представляют собой простые многослойные персептроны, а функции агрегации, ρ,, представляют собой суммирование.

Поскольку в GNN соседние узлы передают сообщения друг другу, налагается смещение местоположения, когда узлы могут легко извлечь выгоду из структуры связности дорожной сети (требуется один шаг передачи сообщения, чтобы полагаться на соседние узлы). Проще говоря, это означает, что модель GNN может лучше отражать практичность условий движения, например, когда блокпост на одном участке дороги может напрямую влиять на движение на другом.

Архитектура модели состоит из блоков encode-process-decode GN. Кодировщик сначала применяется к надсегменту с ранее описанными необработанными функциями. Он создает скрытые представления узлов, ребер и самого суперсегмента. Затем эти представления обновляются путем двукратного прохождения через процессор (с общими параметрами). Наконец, эти обновленные представления преобразуются в соответствующие прогнозы с помощью декодера.

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

Последний шаг в прогнозировании ETA

Чтобы объяснить, как предсказывать ETA, мы уже разделили весь мир, а затем перешли к созданию некоторых архитектурных чудес. Кто бы мог подумать, что предсказание ожидаемого времени прибытия — это такое большое дело? Здесь мы представляем последний шаг в прогнозировании ETA. Подождите, еще осталось? Да, последний шаг — настроить режим обучения модели таким образом, чтобы он был более надежным и обобщаемым, чтобы избежать описанного ниже сценария.

GNN чувствительны к большой изменчивости структур графов, используемых во время обучения. Чтобы сделать модели более устойчивыми к этим изменениям, был разработан метод динамической адаптации скорости обучения во время обучения. Скорость обучения системы определяет, насколько «пластичной» — или изменяемой для новой информации — является модель. Существует компромисс между изучением новых вещей и забыванием уже изученных важных особенностей — мало чем отличающийся от перехода от детства к взрослой жизни, и для достижения этого компромисса важно сделать скорость обучения динамичной.

MetaGradients[3]был наиболее успешным подходом к динамической адаптации скорости обучения во время обучения, что позволило системе эффективно изучить собственный график оптимальной скорости обучения. Этот метод совместно оптимизирует гиперпараметр скорости обучения с параметрами модели на каждой итерации обучения. Это позволяет модели автоматически адаптировать скорость обучения во время обучения, благодаря чему модель достигает более высокого качества, чем раньше.

Линейная комбинация нескольких функций потерь (соответственно взвешенных) значительно увеличила способность модели обобщать. Окончательный убыток для конкретного горизонта составляет:

В частности, была сформулирована цель с несколькими потерями с использованием фактора регулирования для весов модели, L₂ и L₁ потери на глобальном времени прохождения, а также отдельные Хьюберовские и отрицательные логарифмические вероятности потери для каждого узла на графике. Объединив эти потери, модель смогла избежать переобучения в наборе обучающих данных и лучше обобщить в тестовом наборе. .

Во время оценки и обслуживания Eэкспоненциальная Mскользящая Aсредняя (EMA) параметров модели ( θ). EMA уменьшили дисперсию в сохраненных моделях во время тренировочных прогонов, назначив веса параметрам модели.
𝜃(EMA) = 𝛼 · 𝜃(EMA) + (1 − 𝛼) · 𝜃 , где 𝛼 = 0,99 — коэффициент затухания

Конец близок

Теперь, когда мы так много сделали, чтобы понять, как на самом деле работает предсказание ETA, давайте посмотрим на некоторые результаты практического применения модели. Хотя модели были запущены в разных регионах мира, оценка проводится конкретно для: Нью-Йорка (NYC), Лос-Анджелеса (LAX), Токио (TYO) и Сингапур (SGP), как результаты, распространяются на другие регионы. Была проведена автономная, а также онлайновая оценка, чтобы показать эффективность моделей во время обслуживания. Оценка выполняется по непараметрическому времени в пути, рассчитанному с использованием скоростей в реальном времени и исторических скоростей, а также моделей, выполняющих агрегирование сумм по сегменту. представления уровня и не используют структуру графа (DeepSets). Результаты сравнения как для автономной, так и для онлайновой оценки показаны ниже в Таблице 2 и Таблице 7 соответственно.

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

  • Расширенные суперсегменты.Расширенные суперсегменты — это более крупные графы, включающие узлы из соседних сегментов в дополнение к исходным сегментам. К ним относятся сегменты близлежащего, возможно подключенного трафика. Задача прогнозирования и метки остаются прежними. В частности, цель по-прежнему состоит в том, чтобы предсказать время в пути по исходным сегментам и суперсегментам в пределах расширенных суперсегментов. Это позволяет модели использовать дополнительные пространственные контексты, такие как заторы на стыковочном маршруте, за счет хранения данных, более медленного обучения и логических выводов. Кроме того, одна и та же архитектура GNN используется как для суперсегментов, так и для экспериментов с расширенными суперсегментами, благодаря чему стоимость хранения модели остается постоянной.
  • Комбинации агрегаторов.По сравнению с функцией суммирования по умолчанию, комбинации различных агрегаторов (например, среднего, минимального, максимального и квадратного корня) могут дать улучшение в зависимости от региона и горизонта. Поскольку оптимальная функция агрегирования различается в зависимости от региона и горизонта, вероятно, сложно и дорого настроить ее для всех регионов и горизонтов мира. Следовательно, использование всех пяти агрегаций одновременно является разумным предпочтением.
  • Неконтролируемые вспомогательные потери. Наконец, были проведены эксперименты по включению неконтролируемых потерь, которые предназначены для создания представлений, фиксирующих структурную информацию входных графов. Это, в свою очередь, может упростить обнаружение интересных мотивов в топологии дорожной сети, которые могут неявным образом влиять на динамику трафика. Во всех экспериментах эти потери сочетаются с контролируемой целью, чтобы помочь обучению. Deep Graph Infomax (DGI) [4] поощряет встраивание узлов кодировать глобальные структурные свойства, путем тщательного сопоставления дорожной сети с искусственно искаженной версией. GAauto-Eкодер Encoder (GAE) [5] использует потери в стиле прогнозирования ссылок и следовательно, учитывает локальную топологию. Использовалась комбинация DGI и GAE.

Тем не менее, некоторые препятствия еще предстоит устранить

Несмотря на то, насколько удивительным является алгоритм, он столкнулся с некоторыми инженерными проблемами. Давайте кратко рассмотрим, какие они были и как они были решены.

Кэширование.Соответствовать требованиям Google Maps по задержке сложно, сохраняя при этом низкую стоимость оценки моделей Graph Net. Путь в запросе ETA обычно включает в себя несколько суперсегментов, и делать прогнозы для этих суперсегментов на лету нецелесообразно и не масштабируемо. Чтобы решить эту проблему, была создана общая таблица поиска, в которой кэшируются свежие прогнозы для предопределенных суперсегментов для фиксированного набора горизонтов, который периодически обновляется. Сервер извлекает необходимые прогнозы по запросу и интерполирует прогнозы соседних горизонтов, чтобы вычислить предполагаемое время прибытия для каждого суперсегмента.

Скорости поворота.Обычно имеет место мультимодальное распределение скорости для оживленного участка дороги, направляющегося к разделению трафика, например перекрестку или съезду с шоссе. В таких случаях для конкретного поворота, за которым следует суперсегмент, использовалась реальная скорость и историческая скорость.

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

Завершение в стиле

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

Поздравляем! Вы успешно добрались до конца статьи и, надеюсь, поняли, как на самом деле работает предсказание ETA.

Если вы все еще считаете, что прогноз ETA не был достаточно демистифицирован для вас, мы сделали видео, подробно объясняющее этот блог здесь.

Взносы

Спасибо Shrinivas Khiste и YASHICA PATODIA за ценные правки и предложения.

Ссылка

[1] Ше, Дж., Вонг, Д., Ланге, О., Хестер, Т., Перес, Л., Нункессер, М., Ли, С., Го, X., Уилтшир, Б., Батталья, П. В., Гупта В., Ли А., Сюй З., Ли Ю. и Величкович П. (2021). Прогноз ETA с помощью графических нейронных сетей в Google Maps. архив https://doi.org/10.1145/3459637.3481916

[2] https://www.deepmind.com/blog/traffic-prediction-with-advanced-graph-neural-networks

[3] Чжунвэнь Сюй, Хадо П. ван Хасселт и Дэвид Сильвер. 2018. Метаградиентное обучение с подкреплением. Достижения в области нейронных систем обработки информации 31 (2018), 2396–2407.

[4] Величкович, П., Федус, В., Гамильтон, В.Л., Лио, П., Бенжио, Ю., и Хьельм, Р.Д. (2018). Глубокий график Инфомакс. архив https://doi.org/10.48550/arXiv.1809.10341

[5] Кипф, Т. Н., и Веллинг, М. (2016). Автокодировщики вариационного графа. архив https://doi.org/10.48550/arXiv.1611.07308