Главная » Хабрахабр » Чем поможет машинное обучение, когда каждая минута на счету. Прогнозируем ETA в Яндекс.Такси

Чем поможет машинное обучение, когда каждая минута на счету. Прогнозируем ETA в Яндекс.Такси

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

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


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

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

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

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

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

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

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

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

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

$MSE = \frac{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).

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

Итоги

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

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

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

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


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

[Из песочницы] Создание домашнего медиацентра. Пролог

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

Дайджест интересных материалов для мобильного разработчика #279 (10 — 16 декабря)

В новом дайджесте у нас шикарное расследование про геолокацию и то, как приложения делятся данными с рекламодателями, Metal и SceneKit для разработчиков, история приложения на $500,000, лучшие SDK, рост и реклама 2018. SceneKit — высокоуровневый фреймворк трехмерной графики в iOS, ...