Разработчики «Яндекс. Пробки» рассказали о способах предсказания будущего

В первой половине декабря компания «Яндекс» заявила, что ее сервис «Яндекс. Пробки» сможет предсказывать развитие дорожной ситуации на несколько часов вперед. Ранее, в сентябре 2012 года, стало известно, что сервис сможет предугадывать пробки на час вперед. Как именно это работает? Какие математические модели используются для анализа и прогнозирования пробок? Об этом и многом другом «Лента. ру» поговорила с доцентом кафедры информатики МФТИ и разработчиком сервиса Михаилом Хохловым.

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

«Лента. ру»: Итак, Михаил, как работают «Яндекс. Пробки»?

Михаил Хохлов: Ну тут, наверное, надо начать с того, как мы собираем данные о пробках. Эту информацию мы получаем от пользователей: люди, у которых на телефоне включены «Яндекс. Карты» или «Яндекс. Навигатор», с определенной периодичностью посылают нам информацию о своем местоположении. Эти данные, называемые треки, обезличиваются и анализируются. Из них мы узнаем, в каких местах и с какой скоростью сейчас едут машины.

А как вы узнаете, что источником трека был именно человек на машине, а не пешеход?

Такая проблема есть, действительно, к нам в систему могут попадать некоторые «мусорные» треки от пешеходов, у которых включены «Яндекс. Карты». Поэтому мы фильтруем треки перед анализом. Если в течение своей истории трек ни разу не разгонялся более 5 километров в час, то скорее всего это пешеход. Там есть и другие эвристические принципы. Кроме того, статистика говорит. что пешеходов в процентном соотношении не очень много. Обычно пешеходы включают «Яндекс. Карты», что-то посмотрят и выключают.

Регрессионный (линейный) анализ — статистический метод исследования влияния набора независимых переменных, именуемых регрессорами (или предикторами) на зависимые, именуемые критериальными.

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

То есть вы, используя данные от пользователей, строите такую карту и раскрашиваете ее по скоростям — чем ниже скорость, тем краснее цвет?

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

Я так понимаю, что избавиться от мозаики — это то же самое, что взять ступенчатую функцию и сделать ее гладкой?

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

Таким образом вы получили картину. Это картина на данный конкретный момент. Как часто она обновляется? Сколько времени уходит на подсчет всей картины? Каков шаг по времени?

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

Учитывая, что вы используете данные, полученные только от пользователей, может ли так случиться, что покрытие выйдет неравномерным? То есть в одном месте много пользователей, а в другом мало — и информация уже не такая подробная?

Да, я даже могу сказать, где пользователей очень много — в Москве. В других городах их гораздо меньше.

Я имею в виду, что даже в Москве они могут быть распределены по карте неравномерно. Или такого не происходит на практике?

Их так много, что даже если их мало, то этого все равно достаточно. У нас, в принципе, есть еще так называемые партнеры. Это некоторые транспортные компании, фактически те же самые пользователи, просто мы с ними договорились, что они обязательно будут пользоваться «Яндекс. Картами», они тоже посылают нам информацию.

Михаил Хохлов

Отлично. Итак, у вас получилась картинка, она обновляется раз в минуту. Соответственно, речь заходит о прогнозе. Каким образом вы прогнозируете будущее?

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

То есть вы строите нейросеть?

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

И как далеко у вас получается прогнозировать?

Сейчас горизонт прогноза составляет один час. На самом деле даже немножко больше, чем час — там 75 минут. Чтобы всегда гарантировано покрыть час, приходится закладывать на немножко больший промежуток времени. Что касается качества, то тут вопрос в том, что мы меряем. Мы можем сравнить то, что мы напрогнозировали, с уже известным результатом.

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

То есть у вас есть некий набор маршрутов, вы не считаете для всей карты?

Мы разбиваем всю карту на куски.

То есть вы берете карту и разбиваете ее на набор маршрутов?

Да.

Они пересекаются или нет?

Они могут пересекаться, могут не пересекаться. Главное, что карта полностью покрыта.

И это разбиение постоянно или оно меняется?

Может меняться.

Это вопрос к тому, свободный это параметр в модели или нет? Может быть, у вас какой-то стохастический подход, вы случайно разбиваете карту на набор маршрутов и считаете для них. Так как у вас случайное разбиение, то оно каждый раз разное. Либо же вы руками разбили и считаете время для каждого маршрута изо дня в день.

У нас есть фиксированное разбиение, на котором считается модель. При оценке качества этой модели, однако, мы можем использовать то же разбиение, а можем другое. Естественно, мы проверяем и так, и так. Есть же некоторые разбиения, которые подсчитаны и используются именно на этапе подбора коэффициентов модели.

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

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

Детали подобного рода (например, выбор метрики) — это все какие-то эмпирические вещи, которые вы выяснили методом проб и ошибок, или за этим стоит некая теория? Может, вы использовали чьи-то работы, например?

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

Собственно говоря, вопрос оценки качества — это вопрос того, что мы хотим получить. Здесь нет какого-то одного правильного ответа. Ответим так — получим один прогноз, ответим по-другому — получим другой прогноз. Поэтому это такое исследование, которое шло постоянно и параллельно с разработкой самого прогноза. Мы постоянно уточняли модель и уточняли оценку качества. Тут, например, она плохо работает. Почему наша оценка качества это не ловит? Давайте опять собираться и решать, как менять оценку качества, и так далее. Постоянно возникали вопросы, как взвешивать большие и малые ошибки. Хотим ли мы построить прогноз, который в первую очередь минимизирует большие ошибки, или прогноз, который допускает на некоторых участках очень большую ошибку, но зато на остальных участках очень хорошо работает?

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

Как он устроен?

Он устроен очень просто. Мы собираем статистику и данные о том, какие скорости на каких участках, все эти данные сохраняются. И потом мы можем за какой-то период, за месяц или за два усреднить. Берем один день недели и все скорости в этот день на данном участке за промежуток времени, фильтруем их и усредняем.

Прямо средним арифметическим?

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

С которым кстати можно тоже сравнивать предсказания.

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

Обычно в это время. А если сравнить с этими двумя версиями регрессионную линейную модель, которую вы используете?

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

Сейчас модель не учитывает такие вещи?

Да, пока модель их не учитывает.

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

Совершенно верно. Было бы хорошо это учитывать, если бы мы могли хоть откуда-то эту информацию получить.

Правильно я понимаю, что вы ни с кем не сотрудничаете по поводу этой информации? Ни с правительством Москвы, ни с кем-то еще?

Нет.

А вы сотрудничаете с какими-то научными институтами, университетами, которые занимаются исследованием таких вещей?

Мы сотрудничали с несколькими научными коллективами, которые занимаются научной тематикой. Они по нашему заказу пробовали применять несколько другие подходы — в частности потоковое моделирование.

Расскажите, пожалуйста, подробнее.

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

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

У многих возникает идея: а нельзя ли использовать такие модели для краткосрочного планирования? По нашему заказу научные группы пробовали это делать, но результаты пока отрицательные. Этим занимается один коллектив на физтехе, там Александр Гасников и другие. Еще есть один коллектив под руководством Юрия Чеховича, компания «Форексис», они больше занимаются методом машинного обучения, но и потоковым моделированием тоже. Это из тех, с кем мы сотрудничали. Я могу назвать и других.

А отрицательный результат по какой причине? Не хватает вычислительных мощностей?

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

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

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

Творчество интернет-пользователей, посвященное пробкам