В первой половине декабря компания "Яндекс" заявила, что ее сервис "Яндекс.Пробки" сможет предсказывать развитие дорожной ситуации на несколько часов вперед. Ранее, в сентябре 2012 года, стало известно, что сервис сможет предугадывать пробки на час вперед. Как именно это работает? Какие математические модели используются для анализа и прогнозирования пробок? Об этом и многом другом "Лента.ру" поговорила с доцентом кафедры информатики МФТИ и разработчиком сервиса Михаилом Хохловым.
Примечательно, что в назначенный Михаилом Хохловым день Москва встала в 10-балльных пробках, в одну из которых угодил и корреспондент "Ленты.ру", спешивший на интервью.
"Лента.ру": Итак, Михаил, как работают "Яндекс.Пробки"?
Михаил Хохлов: Ну тут, наверное, надо начать с того, как мы собираем данные о пробках. Эту информацию мы получаем от пользователей: люди, у которых на телефоне включены "Яндекс.Карты" или "Яндекс.Навигатор", с определенной периодичностью посылают нам информацию о своем местоположении. Эти данные, называемые треки, обезличиваются и анализируются. Из них мы узнаем, в каких местах и с какой скоростью сейчас едут машины.
А как вы узнаете, что источником трека был именно человек на машине, а не пешеход?
Такая проблема есть, действительно, к нам в систему могут попадать некоторые "мусорные" треки от пешеходов, у которых включены "Яндекс.Карты". Поэтому мы фильтруем треки перед анализом. Если в течение своей истории трек ни разу не разгонялся более 5 километров в час, то скорее всего это пешеход. Там есть и другие эвристические принципы. Кроме того, статистика говорит , что пешеходов в процентном соотношении не очень много. Обычно пешеходы включают "Яндекс.Карты", что-то посмотрят и выключают.
После того как треки обработаны и прошли фильтрацию, из многих треков, проехавших по одному участку дороги, мы должны получить одно число - среднюю скорость. Для этого используется разнообразное усреднение.
То есть вы, используя данные от пользователей, строите такую карту и раскрашиваете ее по скоростям - чем ниже скорость, тем краснее цвет?
Не сразу, на самом деле. Мелкие пробки объединяются в крупные, мы вычисляем, какой продолжительности эта пробка.Если просто раскрасить каждый участок разным цветом в зависимости от скорости, то получится рябая мозаика, из которой очень сложно понять, где и как едут. Поэтому перед тем, как показать картинку пользователю, мы ее обрабатываем. В частности, при помощи фильтрации убираем мелкие помехи.
Я так понимаю, что избавиться от мозаики - это то же самое, что взять ступенчатую функцию и сделать ее гладкой?
Она все равно остается ступенчатой, потому что у нас всего три цвета. Конечно, если мы не хотим перейти к непрерывной палитре цветов, что было бы довольно неожиданным ходом. Цвета всего три, и функция все равно остается ступенчатой. Но мы стараемся некоторым образом фильтровать и укрупнять участки одного цвета. Если, допустим, все кругом красное и у нас тут маленький кусочек зеленого, то мы, скорее всего, не будем показывать этот зеленый кусочек, а закрасим его красным. Потому что ясно, что внутри пробки всегда есть небольшие участки по 50 метров, которые можно быстро проскочить. Это уже получается пространственное усреднение.
Таким образом вы получили картину. Это картина на данный конкретный момент. Как часто она обновляется? Сколько времени уходит на подсчет всей картины? Каков шаг по времени?
Вообще шаг по времени - одна минута. Конкретная картина, которую видит пользователь, когда заходит на "Карты", может отставать больше, чем на одну минуту. Это зависит от многих факторов. Естественно, мы всегда стараемся выдать пользователю самый свежий срез из тех, которые есть. Но иногда он может отставать на минут пять, это зависит от загруженности серверов и многих других факторов.
Учитывая, что вы используете данные, полученные только от пользователей, может ли так случиться, что покрытие выйдет неравномерным? То есть в одном месте много пользователей, а в другом мало - и информация уже не такая подробная?
Да, я даже могу сказать, где пользователей очень много - в Москве. В других городах их гораздо меньше.
Я имею в виду, что даже в Москве они могут быть распределены по карте неравномерно. Или такого не происходит на практике?
Их так много, что даже если их мало, то этого все равно достаточно. У нас, в принципе, есть еще так называемые партнеры. Это некоторые транспортные компании, фактически те же самые пользователи, просто мы с ними договорились, что они обязательно будут пользоваться "Яндекс.Картами", они тоже посылают нам информацию.
Отлично. Итак, у вас получилась картинка, она обновляется раз в минуту. Соответственно, речь заходит о прогнозе. Каким образом вы прогнозируете будущее?
Для этого мы используем методы машинного обучения, мы пытаемся построить некоторую модель, которая бы вычисляла, как зависит будущая скорость на дороге от текущей.
То есть вы строите нейросеть?
Нет, нейросеть мы не используем. Мы используем более простую линейную модель. Это линейная авторегрессионная модель: следующее значение временного ряда есть линейная комбинация от фиксированного количества предыдущих. То есть она векторная, в зависимость включаются и соседние сегменты тоже.
И как далеко у вас получается прогнозировать?
Сейчас горизонт прогноза составляет один час. На самом деле даже немножко больше, чем час - там 75 минут. Чтобы всегда гарантировано покрыть час, приходится закладывать на немножко больший промежуток времени. Что касается качества, то тут вопрос в том, что мы меряем. Мы можем сравнить то, что мы напрогнозировали, с уже известным результатом.
Во-первых, мы смотрим на времена проезда, а не на скорости, поскольку наша цель - как можно более точно предсказывать время движения по маршруту - скорости нам известны. Мы сравниваем время проезда по маршруту, сперва исходя из нашего прогноза на час вперед, а потом, грубо говоря, ждем этот час - на самом же деле мы берем уже известные данные прошлого дня, смотрим, сколько на самом деле занял бы такой маршрут.
То есть у вас есть некий набор маршрутов, вы не считаете для всей карты?
Мы разбиваем всю карту на куски.
То есть вы берете карту и разбиваете ее на набор маршрутов?
Да.
Они пересекаются или нет?
Они могут пересекаться, могут не пересекаться. Главное, что карта полностью покрыта.
И это разбиение постоянно или оно меняется?
Может меняться.
Это вопрос к тому, свободный это параметр в модели или нет? Может быть, у вас какой-то стохастический подход, вы случайно разбиваете карту на набор маршрутов и считаете для них. Так как у вас случайное разбиение, то оно каждый раз разное. Либо же вы руками разбили и считаете время для каждого маршрута изо дня в день.
У нас есть фиксированное разбиение, на котором считается модель. При оценке качества этой модели, однако, мы можем использовать то же разбиение, а можем другое. Естественно, мы проверяем и так, и так. Есть же некоторые разбиения, которые подсчитаны и используются именно на этапе подбора коэффициентов модели.
А дальше?
Допустим, мы нашли, насколько наш прогноз отличается относительно реальности. Эти величины еще рано с чем-то сравнивать, потому что это величины на разных дорогах совершенно разных порядков. Есть дороги, на которых пробки постоянно, и там сложно что-то предсказать. Есть дороги, где всегда относительно свободно, и там предсказать гораздо проще. И абсолютная величина ошибки на них гораздо меньше, но не потому, что наш прогноз там хорошо работает, а просто потому, что там и так все понятно.
Поэтому мы смотрим не просто на абсолютную величину ошибки, а на то, насколько эта ошибка меньше, чем ошибка некоего базового уровня. За базовый уровень мы берем прогноз константой - то есть мы считаем, что через час будет то же самое, что и сейчас. И мы считаем, насколько наш прогноз точнее, чем тривиальный прогноз, что через час будет то же самое. По этим результатам наш прогноз где-то на 15 процентов точнее базового.
Детали подобного рода (например, выбор метрики) - это все какие-то эмпирические вещи, которые вы выяснили методом проб и ошибок, или за этим стоит некая теория? Может, вы использовали чьи-то работы, например?
У нас было большое исследование (правда для внутреннего пользования, результаты не публиковались), посвященное оценке качества. Все, что я вам рассказываю, все эти проблемы когда-то перед нами реально возникли и мы обсуждали разные варианты того, как можно их обойти.
Собственно говоря, вопрос оценки качества - это вопрос того, что мы хотим получить. Здесь нет какого-то одного правильного ответа. Ответим так - получим один прогноз, ответим по-другому - получим другой прогноз. Поэтому это такое исследование, которое шло постоянно и параллельно с разработкой самого прогноза. Мы постоянно уточняли модель и уточняли оценку качества. Тут, например, она плохо работает. Почему наша оценка качества это не ловит? Давайте опять собираться и решать, как менять оценку качества, и так далее. Постоянно возникали вопросы, как взвешивать большие и малые ошибки. Хотим ли мы построить прогноз, который в первую очередь минимизирует большие ошибки, или прогноз, который допускает на некоторых участках очень большую ошибку, но зато на остальных участках очень хорошо работает?
Насчет прогнозирования на больший период, тут такая вещь: у нас уже достаточно давно есть обычный сервис пробок, который строит так называемый "недельный профиль", то есть как в течение недели обычно меняются пробки.
Как он устроен?
Он устроен очень просто. Мы собираем статистику и данные о том, какие скорости на каких участках, все эти данные сохраняются. И потом мы можем за какой-то период, за месяц или за два усреднить. Берем один день недели и все скорости в этот день на данном участке за промежуток времени, фильтруем их и усредняем.
Прямо средним арифметическим?
Нет, не средним арифметическим, но как-то усредняем. И говорим, что обычно в этот день недели в такое время бывает такая ситуация. Это тоже один из методов прогноза.
С которым кстати можно тоже сравнивать предсказания.
Я к этому и веду. Если сравнить его с тем, что уже есть, то есть с постоянным прогнозом и с нашим, оказывается, что на горизонтах до часа константный способ лучше, чем среднее. А после часа среднее лучше. То есть ситуация на дороге все время меняется, и где-то в течение часа она остается больше похожей на то, что было. А уже через два часа она не будет иметь ничего общего с тем, что сейчас, и будет гораздо больше похожа на то, что обычно бывает в это время.
Обычно в это время. А если сравнить с этими двумя версиями регрессионную линейную модель, которую вы используете?
Наша модель прогнозирует лучше, чем константная. Через два часа ошибка, однако, ухудшается до уровня средних пробок. Дольше чем на два часа не имеет смысла прогнозировать ни нашей моделью, ни как-то по-другому, только пробки обычные могут вам подсказать, что будет через два часа и позже. Поэтому прогнозирование на более далекий срок - это просто улучшение обычного сервиса пробок. Можно как-то учитывать погоду в них, еще какие-то другие факторы. Например, известно, что наступят долгие праздники.
Сейчас модель не учитывает такие вещи?
Да, пока модель их не учитывает.
Меня очень интересовал вопрос, учитывает ли она режим работы светофоров. Потому что этот режим меняется и оказывает очень большое влияние на динамику движения (pdf). Например, часто же бывает, что меняют время переключения светофоров. Например, на кольце включают зеленый свет, и становится легче ездить. С точки зрения модели, это такие же непредвиденные вещи (или не непредвиденные), правильно?
Совершенно верно. Было бы хорошо это учитывать, если бы мы могли хоть откуда-то эту информацию получить.
Правильно я понимаю, что вы ни с кем не сотрудничаете по поводу этой информации? Ни с правительством Москвы, ни с кем-то еще?
Нет.
А вы сотрудничаете с какими-то научными институтами, университетами, которые занимаются исследованием таких вещей?
Мы сотрудничали с несколькими научными коллективами, которые занимаются научной тематикой. Они по нашему заказу пробовали применять несколько другие подходы - в частности потоковое моделирование.
Расскажите, пожалуйста, подробнее.
Да, есть такое направление в науке - моделирование транспортных потоков. Оно пытается описывать движение автомобилей в городе как движение некоторой особенной жидкости. Там используется уравнение, похожее на уравнение гидродинамики, но там есть и существенное отличие, которое приводит к тому, что решение этих уравнений совершенно не похоже на гидродинамические.
Эти модели сейчас очень активно развиваются. В частности, они используются в целях планирования градостроительства. С их помощью можно предсказать, как изменится нагрузка на разные дороги, если где-то построить новую дорогу или мост, и увидеть проблемные участки, где движение перегружено. Это такое долговременное масштабное планирование.
У многих возникает идея: а нельзя ли использовать такие модели для краткосрочного планирования? По нашему заказу научные группы пробовали это делать, но результаты пока отрицательные. Этим занимается один коллектив на физтехе, там Александр Гасников и другие. Еще есть один коллектив под руководством Юрия Чеховича, компания "Форексис", они больше занимаются методом машинного обучения, но и потоковым моделированием тоже. Это из тех, с кем мы сотрудничали. Я могу назвать и других.
А отрицательный результат по какой причине? Не хватает вычислительных мощностей?
Нет, там более серьезные причины. Во-первых, в наших данных нет информации о потоке, только о скорости. Мы не можем восстановить, сколько машин едет по дороге, можем только сказать, с какой скоростью они движутся, а для потоковых моделей (как следует и из названия) это принципиальная вещь. К сожалению, по скорости однозначно установить поток нельзя.
Во-вторых, во многих местах качество данных хромает. Ту же самую линейную регрессию мы во многом выбрали из-за ее устойчивости, она очень устойчива к шуму. Потоковые же модели относятся к шуму гораздо хуже.
И кроме того, есть некая проблема задания начальных условий. Если вы восстанавливаете картину в среднем за месяц, то это одно дело: скорее всего для этого вы используете какой-то итерационный алгоритм, который сходится к равновесию. А другое дело, если вам надо точно задать начальные условия и сказать, что будет через час. Это задача гораздо более сложная, и не до конца понятно, как ее решать.
В общем пока результат отрицательный, но сотрудничество мы не бросаем.
Еще какие-нибудь модели?
Есть подход так называемой имитационной модели, когда каждый водитель имитируется в отдельности. Создается простой алгоритм, который обычно заключается в том, что у каждого водителя есть какая-то комфортная скорость, и если у него есть такая возможность, то он едет с этой скоростью. Если ему кто-то мешает, то он тормозит, чтобы соблюдать безопасную дистанцию. Плюс время от времени перестраивается, если ему надо куда-то поворачивать. Берется тысяча таких простых алгоритмов и запускается симуляция на известной конфигурации дороги. Это тоже достаточно распространенная вещь, которая часто используется при проектировании развязок.
Мы ее тоже пробовали. Соответственно, тут еще больше проблем. Откуда брать всех этих водителей, кто куда едет - тоже абсолютно неизвестно. Это очень любопытно, но пока совершенно неприменимо. Мы общались с организациями, которые занимаются этими моделями, они посмотрели на наши данные, тоже сказали, что данные им не подходят.
Какие-нибудь еще интересные модели?
Это все были модели, которые я условно называю "физические модели". В них пытаются моделировать, что же там на самом деле происходит. Есть еще другой подход - это собственно подход машинного обучения. То есть нам не интересно, что там происходит, мы просто смотрим на числа и пытаемся понять, какие числа появятся дальше после вот этих вот чисел.
Тут набор методов тоже достаточно широкий. В том числе и упоминавшиеся нейронные сети, то есть по сути нелинейные параметрические модели. Есть линейные параметрические модели. Есть просто непараметрические модели, которые не предполагают никакой конкретной зависимости. Например, есть метод "k ближайших соседей", мы его сами пробовали.
Расскажите, пожалуйста, подробнее об этом методе.
Метод KNN (k-Nearest Neighbors) заключается в том, что у нас есть большая история. Мы знаем, что раньше было на этом участке дороги. Мы можем взять нынешнюю ситуацию, тоже с небольшой историей, и найти какое-то количество похожих ситуаций в прошлом. Посмотреть, что было после них. Усреднить, как всегда. И сказать, что раз раньше после этого было то-то, то и сейчас будет то же самое.
С точки зрения здравого смысла, это вообще очень адекватно.
Это очень логично, и это действительно работает. Мы такую модель реализовали, и она работает. Более того, она дает качество, вполне сравнимое с качеством, которое дает линейная модель, лучшие варианты того и другого методов работают одинаково, практически с точностью до процента. Линейную модель мы выбрали по соображениям вычислительной простоты. Понимаете, для нее главная сложность - найти некие численные коэффициенты. Когда коэффициенты есть, то вычислить прогноз - задача тривиальная, для этого надо умножить одну матрицу на другую. Для kNN каждый, раз, когда мы хотим построить прогноз, нам надо полностью просмотреть всю историю, найти ближайшие значения, усреднить их. Вычислительно это очень сложная задача. А у нас история наблюдений, которую мы храним, это десятки терабайт.
А сколько по времени вы храните историю?
С момента начала проекта в 2006 году.
То есть в принципе ваши данные можно использовать, чтобы увидеть, как ухудшилась ситуация с московскими дорогами за эти годы?
Если вы найдете метрику, которая показывает "степень хорошести" ситуации, то да. Такую метрику сложно придумать. Те же самые баллы - их коэффициенты постоянно подбираются, чтобы отражать дорожную ситуацию.
Расскажите хотя бы в общих чертах, как считаются баллы?
Для каждого города мы выбираем набор маршрутов, который, по нашему мнению, наилучшим образом отражает дорожную ситуацию в городе. И считаем, сколько времени занимает объехать все эти маршруты. Вся шкала времени разбита на 11 частей, пронумерована от 0 до 10, и этот балл мы показываем.
А что-нибудь аналогичное есть у ваших друзей-конкурентов, что известно про них?
Про конкурентов известно очень мало. Многое известно про комплексные системы управления городом, типа "Умный город", который разрабатывает IBM. Они в том числе строят прогнозы, потому что, естественно, чтобы правильно управлять системой, надо смотреть на шаг вперед, иначе ничего не получится. Они принципиально отличаются от нас. Во-первых, это системы управления, а не чисто информационные, как у нас. Это и сложнее, и проще. Проще - потому что часто пробку проще предотвратить, чем предсказать, как она будет потом изменяться.
Сложнее же потому, что они все требуют подстройки под конкретный город, они не универсальны. И они все требуют установки дополнительного оборудования: датчиков движения на дорогах, которые подсчитывают количество проехавших автомобилей и их скорость. Наша система отличается от них тем, что она основана только на пользовательских данных и она универсальна - везде, где у нас есть данные, там есть прогноз. Про прямых конкурентов я ничего определенного сказать не могу. То, что видят пользователи, то видим и мы.
IBM много рассказывала про свое исследование, и в частности их статьи кое в чем нам помогли. Про векторную линейную авторегрессию они рассказывают именно то, что у нас тоже работает. А вот в Австралии разрабатывают аналогичную систему, основанную на нейросетях. Хотя, конечно, это отчасти слухи.
Ну и обязательный вопрос про планы на будущее. Как вы планируете усовершенствовать модель?
Можно значительно улучшить качество прогноза, если учитывать какие-то внешние факторы. Первое, что приходит в голову - это погода. Мы исследуем возможность включить в качестве фактора погоду - просто коэффициенты в модели будут другими в случае, если идет снег. Ну или интенсивность осадков как еще одна переменная. Это все темы для дальнейшего исследования. Этот вопрос пока исследуется. Пока мы реализовали то, что есть. Очередной этап будет больше исследовательским.
Зависимость от времени суток у нас, между прочим, в модели уже есть. Время суток в качестве внешней переменной - это достаточно очевидная вещь.
А какие еще временные переменные есть?
Пока только время суток. Возможно, если бы у нас была достоверная информация об авариях или если бы мы могли как-то извлекать ее из тех данных, которые у нас есть, то это тоже могло бы улучшить прогноз. Потому что если мы знаем, что где-то авария, это поможет нам прогнозировать, сколько времени будет продолжаться пробка и что произойдет после того, как она рассосется.
Сейчас данные об авариях у нас есть только от пользователей - это то, что показывается в "Яндекс.Пробки". Мы рассматриваем варианты их включения в расчеты, но качество сейчас у них крайне низкое. Это пока работает так: вот едет пользователь. Если он увидел ДТП, то может поставить точку.
Дальше работает система голосования. Например, я ставлю точку, а вы едете и тоже видите, что там ДТП, - вы можете подтвердить точку, можете ее опровергнуть.
В этих точках тоже есть проблема. У нас есть информация, когда точка появилась, но когда она исчезла, у нас информации нет. Точнее, если никто не подтвердит точку, то она будет держаться 20 минут, если я не ошибаюсь, а потом исчезнет, пока кто-то снова не поставит эту точку.
Единственное, что пока можно сказать, это то, что если на этом участке часто происходят ДТП и они есть в обучающей выборке, на которой мы обучали модель, то, скорее всего, в модели будет это учтено. То есть коэффициенты модели будут отражать то, как обычно развивается пробка.
Большое вам спасибо, было очень интересно.