company_banner

Как Яндекс.Такси прогнозирует время подачи автомобиля с помощью машинного обучения

    Представьте, что вам надо вызвать такси. Вы открываете приложение, видите, что машина приедет минут через семь, нажимаете «Заказать» — и… автомобиль в 15 минутах от вас, если вообще найден. Согласитесь, неприятно?

    Под катом поговорим о том, как методы машинного обучения помогают Яндекс.Такси более качественно прогнозировать ETA (Estimated Time of Arrival — ожидаемое время прибытия).



    Для начала напомним, что пользователь видит в приложении перед заказом:



    На карте синим отмечены оптимальные точки для посадки в такси. Красный пин — точка, к которой пользователь вызывает такси. В пине отображается, через какое время прибудет машина. В идеальном мире. Но в реальном мире другие люди неподалеку тоже вызывают себе машину через приложение Яндекс.Такси. И мы не знаем, какой автомобиль к кому поедет, ведь они распределяются только после заказа. Если машина уже назначена, для прогноза мы воспользуемся роутингом Яндекс.Карт и временем при движении по оптимальному пути. Это время (возможно, с небольшим запасом) мы и покажем пользователю сразу после заказа. Остается вопрос: а как же спрогнозировать ETA до заказа?

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

    Почему это важно



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

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

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

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



    Мы хотим, чтобы модель в среднем ошибалась мало. В зависимости от значения «в среднем» возникает два варианта оценки качества прогнозов. Первый вариант — показывать пользователю математическое ожидание времени до приезда такси. В итоге обучится модель, минимизирующая средний квадрат ошибки прогноза (Mean Squared Error, MSE):

    $MSE = \frac{1}{n}\sum_{i=1}^{n} (y_i - \hat{y}_i)^2 \rightarrow min$



    Здесь $y_i$ — правильные ответы, $\hat{y}_i$ — прогнозы модели.

    Другой вариант — не ошибаться с прогнозом ETA преимущественно в одну сторону, в большую или в меньшую. В этом случае мы покажем пользователю медиану распределения времени до приезда такси. В итоге обучится модель, оптимизирующая средний модуль ошибки прогноза (Mean Absolute Error, MAE):

    $MAE = \frac{1}{n}\sum_{i=1}^{n} |y_i - \hat{y}_i| \rightarrow min$



    Но мы поняли, что немного забегаем вперед.

    Переосмысление постановки задачи


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

    Вот в чем оказался подвох в задаче про ЕТА в пине. Пока водитель не назначен, надо прогнозировать именно то время, которое потом покажет роутинг Яндекс.Карт, а не фактическое время до подачи машины.

    Казалось бы, что за чушь: вместо точного значения брать в качестве таргета другой прогноз? Но это имеет смысл, и вот почему. По пути к вам назначенная машина может задержаться. Водитель попал в опасную ситуацию на дороге, в пробку из-за ДТП или вышел купить воды. Такие задержки сложно предугадать. Они создают дополнительный шум в целевой переменной, из-за которого и без того непростая задача спрогнозировать ЕТА в пине становится еще сложнее.

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

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

    Метрики качества, данные, модель и обучение


    Мы выяснили, что для ЕТА в пине нужно прогнозировать не фактическое время, а время, которое будет получено после назначения машины по маршруту. Из двух метрик качества, MAE и MSE, мы выбрали MAE. Возможно, с точки зрения интуитивности прогноза более логично оценивать матожидание (MSE), а не медиану (MAE). Но у MAE есть приятная особенность: модель более устойчива к выбросам (outliers) среди обучающих примеров.

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

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

    Теперь пара слов о том, какие модели сравнивались. Исходное ЕТА (до уточнения машинным обучением) рассчитывалось на основе времени, за которое может приехать ближайшая к пользователю машина. Текущая модель (используется в приложении сейчас) — то, что получилось сделать с помощью машинного обучения и чему посвящена эта статья. Кроме того, в продакшн скоро выкатится новая модель. Она использует на порядок больше значимых для решения задачи признаков. В таблице ниже приводятся замеры качества этих моделей на исторических данных. К слову, у нас планов ещё много — приходите помогать.

    Качество прогноза ETA на валидации*

     
    Mean Absolute Error
    Ошибка более 1 минуты
    Ошибка более 2 минут
    Ошибка более 5 минут

    Исходное ETA


    82,082


    29,95


    18,12


    3,7


    Текущая модель


    79,276 (–3,4)


    29,33 (–2,1)


    16,98 (–6,3)


    3 (–19,2)


    Новая модель


    78,414 (–4,5)


    28,95 (–3,4)


    16,62 (–8,2)


    2,8 (–23,2)




    * В процентах (в скобках указано изменение по сравнению с исходным ETA).

    Машинное обучение позволило выиграть примерно две секунды, или 3,4 % среднего отклонения прогноза. А в новой модели — еще почти секунду, суммарно уже 4,5 %. Но по этим числам сложно понять, что ETA улучшилось существенно. Чтобы почувствовать пользу от машинного обучения, стоит обратить внимание на последний столбец. Промахов с прогнозом более чем на 5 минут стало на 19,2 %, а в новой модели — даже на 23,2 % меньше! Кстати, такие ошибки случаются лишь в 3 и 2,8 % случаев в моделях с использованием машинного обучения.

    Итоги


    Мы уточняли ЕТА в пине в основном для того, чтобы предоставить пользователям достоверный прогноз. Но, разумеется, при любом применении машинного обучения в бизнесе обязательно оценивать экономический эффект. И понимать, сопоставим ли он с затратами на построение и внедрение моделей. После А/В-теста в онлайне выяснилось, что мы, применив машинное обучение, получили статистически значимый рост конверсии из заказа в совершённую поездку (ведь заказ может быть и отменен) и рост конверсии из пользовательской сессии в заказ.

    В обоих случаях речь идет об эффекте порядка 0,1 процентного пункта. Это, кстати, не противоречит статистической значимости: на наших объемах данных даже такое различие достоверно обнаруживается за 2–4 недели. И со значимостью для бизнеса на самом деле все тоже неплохо: оказалось, что затраты на уточнение ЕТА отбиваются приростом конверсии буквально за несколько месяцев.

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

    P.S. Если вам интересны и другие технологии Яндекс.Такси, то рекомендуем пост о динамическом ценообразовании, который совсем недавно опубликовал мой коллега.

    Яндекс

    815,00

    Как мы делаем Яндекс

    Поделиться публикацией
    Комментарии 27
      +3
      Этим летом в Питере в приложении был классный баг)
      Время чемпионата, белые ночи, мосты перекрыты. Нужно было уехать из центра с Невского проспекта в спальный район. Так вот получилось так, что если ходить вокруг места где стоишь +-10 метров, то приложение выдавало цену то 2000р, то 200р. И если успеть нажать вызов в нужный момент, то можно было уехать в 10 дешевле. Таксист был дико зол и было много мата в сторону Яндекса из его уст..:)
        0
        Интересно, а зачем он тогда согласился принять заказ, неужели он цены не видит? Или у них есть какие-то обязательства, кто-нибудь в курсе?
          0
          Он не видит конечную точку маршрута. И да, если он будет постоянно отказываться, то его Яндекс заблокирует.
            0
            Он не видит конечную точку маршрута.
            Не может быть. Меня при посадке в такси в аэропорту, где масса ищущих друг дружку пассажиров и машин, водители сами не раз переспрашивали о конечной точке, чтобы понять, что я именно тот, кто вызывал.
              0
              пока не приедет на место — не увидит конечную точку
                0
                Вот оно что оказывается. Интересно, какой в этом смысл.
                Я так понимаю, что текущее положение клиента он тоже не видит, а то я как-то в Шереметьево заказал такси, но не проконтролировал, что мой адрес был только Шарик, без указания терминала, и хотя мои координаты на карте при заказе были верными, водитель приехал вместо B в E, что в 2 км по прямой от меня. Пришлось созваниваться, уточнять и ещё минут 10 ждать, когда подъедет.
                  0
                  Водители говорят, что теперь, буквально пара недель, видят координаты пассажира, если он это разрешает, но я не нашёл где это разрешать и не видел как это выглядит у водителя, так как когда я подхожу, они все включают поездку раньше, чем я сажусь в машину.
                    0
                    синяя стрелочка в верхнем правом углу
                    +1
                    Какой смысл в том что водитель не видит конечную точку? Огромный. Иначе ваш вызов ночью из центра в Балашиху никто бы не брал. Или наоборот Заказ на 100 р. тоже не брал бы никто. В этом основная суть всех этих такси приложений.
            0
            Ещё расскажу один поучительный случай, на котором в службе поддержки сказали что не видят в этом проблемы. Дело было так: нужно было из Шереметьево съездить в Лобню и обратно. Вызываю Такси — Шемеретьево D — Лобня, ~500 рублей. Доезжаем, водитель ждёт, возвращаюсь, ставлю «Изменить конечную точку», Выскакивает предупреждение, что цена может не совпасть с изначально заявленной. Всё ОК, едем до Шереметьева D. В итоге получается сумма рублей 120. За всё про-всё. Я конечно таксисту перевёл недостающую сумму после попытки разобраться с этим случаем через службу поддержки и получения вышеупомянутого ответа, что проблем нет, все тарифицировано верно…
            +1
            Надо сказать что ETA после заказа тоже далека от реальности (по моим личным наблюдениям). Так как опять же показывает время прибытия идеального «сферического водителя в вакууме». А на самом деле человеческий фактор играет большую роль. И надо сказать что чаще врут именно оптимистичные: машина подъедет через 1 (1,2,3) минуту. Они на практике превращаются в 5 — 10 минут. Начиная где-то минуты с 9-ой ETA уже получается точнее. Человеческий фактор играет роль повторюсь (один водитель тупо стоял на месте 5 минут, а Яндекс радостно говорил мне что машина будет через 1 минуту). Но, например, в другой раз Яндекс точно так же сообщал мне что машина будет через 2 минуты, но она при этом была в начале улицы с глухой пробкой, которую я видел своими глазами, и на Яндекс картах пробка была отмечена. В итоге машина подъехала через 8 минут примерно.
              0

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

                0
                А я на очень далёких маршрутах заметил, что Яндекс угадывает во сколько мы приедем, хотя мы ещё поесть заедем, а то и поспать.
              +6
              “Как Яндекс.Такси прогнозирует время подачи автомобиля с помощью машинного обучения”? — Так себе
                0
                я вообще считал, что это все маркетинг. У Яндекса всегда рядом машины и быстро должны приехать. По факту обычно позже приезжают.
                  +1
                  И раньше приезжают, показывает «4 минуты», а машина ждёт. И буквально позавчера увидел их приложение с надпиьсю «ожидание — 3 рубля/минута». Ехавший человек сразу поинтересоваля «а если я ждать буду?»
                +1
                Как раз в последние пару дней было несмешно из-за этого. Открываю приложение, машина в течение 5 минут, всё хорошо. «Вызвать» — а теперь «Нет свободных машин». То есть ETA было принципиально неверным)
                  +2
                  Лично я вообще перестал смотреть на эту цифру в пине. Всё равно она никак не помогает в планировании. Угадать, через сколько приедет водитель, не реально. Он после приёма заказа регулярно вообще уезжает в противоположную сторону от меня, так как может у вас принимать заказ, не закончив предыдущий. Пару раз я даже отменял заказ, так как было понятно, что заказать заново будет быстрее.
                  Помню раньше было круто — видны были машины вокруг, вот это казалось помогало оценить обстановку.

                  Так что, ИМХО, не тем вы занимаетесь, есть куча более важных вещей в вашем приложении. Сделайте уже возможность легко указать куда именно и как подъехать водителю. Уже сколько лет прошло, а в приложении сделали буквально пару вещей из того что хочется, подъезды добавили и вроде даже водителю стало видно пассажира до посадки, но хочется большей точности, неужели сложно показать водителю ровно ту точку, которую я указал на карте, а лучше дать возможность указать как подъехать. Регулярно попадаю в ситуацию, что мне проще дойти метров 300 до угла, чем объяснить водителю куда подъехать и как встать.
                  Так же довольно напрягает необходимость каждый раз объяснять водителю, что он должен подъехать к шлагбауму и сообщить мне. Сделайте уже для пассажира галочку при заказе и для водителя кнопочку, а лучше скрипт сообщающий мне, что пора открыть шлагбаум.
                  Маршрут тоже заранее выбрать нельзя, только потом водителю объяснять.
                  И так далее, сделайте приложение удобным, а то мне кажется, что вы не пользуетесь им сами.

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

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

                    Так они и сейчас видны.
                    0
                    Вот прогноз подачи машины+- 5 минут не как не напрягает, честно не сижу и не зомбируюсь в телефон — когда подойдет машина. Напрягает само унизительное отношение Яндекса к клиенту, только перечень наименований тарифов (цена не волнует) заставляет обращаться к другим перевозчикам.
                      0
                      Ну там же видно цену когда вы строите маршрут. В чем проблема?
                        +1
                        Расшифрую что написал. Это не сервис должен указывать клиенту когда такси сможет подъехать, а клиент такси указывает когда должна быть поставлена машина. Не успел таксист подъехать за 2 минуты с него штраф по 5 руб/мин., не успел клиент сесть за 2 мин штраф с клиента.
                        +3
                        Надеюсь, не забудете проверять время на адекватность :)
                        Мой скриншот с реального заказа

                          +1
                          Все еще ждете? =)
                            0
                            А лучше водителей. Вчера водитель всю дорогу удивлялся, почему я с Сокола еду на Юбилейный, а не сначала на метро до Речного, а оттуда уже вызвать такси. Калькулировал мой бюджет, советовал по отцовски, призывал экономить. Попросил его отменить заказ — обиделся, но довез
                              0
                              Это реклама Nissan, «и через 136 лет машина будет на ходу».
                              +1
                              То, что вы описали, в жизни работает как обыкновенное гадание, а не прогнозирование. Берешь приложение, вызываешь такси, смотришь, сколько минут выпало. Нет, многовато. Закрываешь. Пробуешь еще раз. О, теперь лучше. Так, водитель поехал не туда. Отменяешь. Пробуешь еще раз. Опять время большое. А нет, уже не надо, пока игрался с приложением, дошел до стоянки такси, где всегда бомбилы тусуются. Зато формулы красивые, да.

                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                              Самое читаемое