Хороший сервіс для замовлення таксі має бути безпечним, надійним та швидким. Користувач не вдаватиметься в деталі: йому важливо, щоб він натиснув кнопку «Замовити» і якнайшвидше отримав машину, яка доставить його з точки А в точку Б. Якщо поряд немає машин — сервіс повинен відразу про це повідомити, щоб у клієнта не складалося хибних очікувань. Але якщо плашка «Немає машин» висвічуватиметься дуже часто, то логічно, що людина просто перестане користуватися цим сервісом і піде до конкурента.
У цій статті я хочу розповісти про те, як за допомогою машинного навчання ми вирішували завдання пошуку машин на території з малою щільністю (простіше, там, де, на перший погляд, немає машин). І що з цього вийшло.
Передісторія
Щоб викликати таксі, користувач робить кілька простих дій, а що при цьому відбувається у нутрощі сервісу?
| Користувач | етап | Бекенд Яндекс.Таксі |
|---|---|---|
| Вибирає точку відправлення | пін | Запускаємо спрощений пошук кандидатів – пошук на піні. На основі знайдених водіїв передбачається час приїзду – ETA у піні. Розраховується підвищуючий коефіцієнт у цій точці. |
| Вибирає точку призначення, тариф, вимоги | оффер | Будуємо маршрут та розраховуємо ціни на всі тарифи з урахуванням підвищуючого коефіцієнта. |
| Натискає кнопку «Викликати таксі» | Замовлення | Запускаємо повноцінний пошук машини. Вибираємо найбільш відповідного водія та пропонуємо йому замовлення. |
Про , и ми вже писали. А це історія про пошук водіїв. Коли створюється замовлення, пошук відбувається двічі: на піні та на замовлення. Пошук на замовлення відбувається у два етапи: набір кандидатів та ранжування. Спочатку знаходяться вільні водії-кандидати, які є найближчими за дорожнім графом. Потім застосовуються бонуси та фільтрації. Кандидати, що залишилися, ранжуються, і переможцю приходить пропозиція замовлення. Якщо він погоджується, то призначається на замовлення та їде до точки подачі. Якщо відмовляється, то пропозиція приходить наступному. Якщо кандидатів більше немає, пошук запускається заново. Це триває не більше трьох хвилин, після чого замовлення скасовується - згоряє.
Пошук на піні схожий на пошук на замовлення, тільки замовлення не створюється і сам пошук виконується лише один раз. Також використовуються спрощені налаштування числа кандидатів та радіусу пошуку. Такі спрощення потрібні, тому що пінів на порядок більше, ніж замовлень, а пошук досить важка операція. Ключовий момент для нашої історії: якщо під час попереднього пошуку на піні відповідних кандидатів не знайшлося, ми не дозволяємо зробити замовлення. Принаймні раніше було так.
Ось що бачив користувач у додатку:
Пошук машин без машин
Якось у нас з'явилася гіпотеза: можливо, в деяких випадках замовлення все ж таки можна виконати, навіть якщо на піні не знайшлося машин. Адже між піном та замовленням минає якийсь час, а пошук на замовлення повніший і іноді повторюється кілька разів: за цей час вільні водії можуть з'явитися. Ще ми знали протилежне: якщо водії знайшлися на піні, ще не факт, що вони знайдуться при замовленні. Іноді вони зникають або всі відмовляються від замовлення.
Щоб перевірити цю гіпотезу, ми запустили експеримент: перестали перевіряти наявність машин під час пошуку на піні для тестової групи користувачів, тобто у них з'явилася можливість зробити замовлення без машин. Результат вийшов досить несподіваним: якщо машина не перебувала на піні, то в 29% випадків вона перебувала пізніше - при пошуку на замовленні! Більше того, замовлення без машин не сильно відрізнялися від звичайних за частотою відмін, оцінок та інших показників якості. Число замовлень без машин становило 5% всіх замовлень, але трохи більше 1% усіх успішних поїздок.
Щоб зрозуміти, звідки беруться виконавці цих замовлень, подивимося на їхні статуси під час пошуку на піні:
- Вільний: був доступний, але з якихось причин не потрапив у кандидати, наприклад, був надто далеко;
- На замовлення: був зайнятий, але встиг звільнитися або стати доступним для ;
- Зайнятий: можливість приймати замовлення було вимкнено, але потім водій повернувся на лінію;
- Недоступний: водія не було у мережі, але він з'явився.
Додамо надійності
Додаткові замовлення - це чудово, проте 29% успішних пошуків означають, що в 71% випадків користувач довго чекав і в результаті нікуди не поїхав. Хоча з точки зору ефективності системи в цьому немає нічого жахливого, але насправді користувач отримує помилкову надію і витрачає час, після чого засмучується і (можливо) перестає користуватися сервісом. Щоб вирішити цю проблему, ми навчилися передбачати ймовірність того, що машину на замовлення буде знайдено.
Схема така:
- Користувач ставить пін.
- Проводиться пошук на піні.
- Якщо машин немає — передбачаємо: можливо, вони з'являться.
- І в залежності від ймовірності даємо або не даємо зробити замовлення, але попереджаємо, що щільність машин у цьому районі та в цей час маленька.
У додатку це виглядало так:
Використання моделі дозволяє акуратніше створювати нові замовлення, не обнадійувати людину марно. Тобто регулювати співвідношення надійності та кількості замовлень без машин за допомогою precision-recall моделі. Надійність сервісу впливає бажання і далі скористатися товаром, т. е. у результаті все зводиться до поїздок.
Трохи про precision-recallОдне з базових завдань у машинному навчанні — завдання класифікації: зарахувати об'єкт до одного з двох класів. При цьому результатом роботи алгоритму машинного навчання часто стає числова оцінка приналежності до одного з класів, наприклад, оцінка ймовірності. Однак дії, які відбуваються, зазвичай бінарні: якщо машина буде — то даємо замовити, а якщо ні — ні. Для певності назвемо моделлю алгоритм, який видає числову оцінку, а класифікатором - правило, яке відносить до одного із двох класів (1 або -1). Щоб з урахуванням оцінки моделі зробити класифікатор, потрібно підібрати поріг оцінки. Як саме сильно залежить від завдання.
Припустимо, ми робимо тест (класифікатор) на якусь рідкісну та небезпечну хворобу. За результатами тесту ми або відправляємо пацієнта на докладніше обстеження, або говоримо: «Здоров, йди додому». Для нас відправити додому хвору людину набагато гірше, ніж даремно обстежити здорову. Тобто ми хочемо, щоб тест спрацьовував для якомога більшої кількості реально хворих людей. Ця величина називається recall =. У ідеального класифікатора recall дорівнює 100%. Вироджена ситуація – відправляти на обстеження всіх, тоді recall теж буде 100%.
Буває і навпаки. Наприклад, ми робимо систему тестування для студентів, і в ній є детектор списування. Якщо раптом на якісь випадки списування не спрацює перевірка, це неприємно, але не критично. З іншого боку, вкрай погано незаслужено звинувачувати студентів у тому, чого вони не робили. Тобто нам важливо, щоб серед позитивних відповідей класифікатора було якнайбільше правильних, можливо, на шкоду їх кількості. Отже, необхідно максимізувати precision = . Якщо спрацьовування будуть відбуватися на всіх об'єктах, то precision дорівнюватиме частоті визначається класу у вибірці.
Якщо алгоритм видає числове значення ймовірності, то, підбираючи різні пороги, можна досягти різних значень precision-recall.
У нашому завданні ситуація така. Recall – кількість замовлень, яку ми можемо запропонувати, precision – надійність цих замовлень. Ось так виглядає precision-recall крива нашої моделі:
Є два крайні випадки: не дозволяти замовляти нікому і дозволяти замовляти всім. Якщо не дозволяти нікому, то recall буде 0: ми не створюємо замовлень, але жодної з них не стане провальним. Якщо дозволяти всім, то recall буде 100% (ми отримаємо всі можливі замовлення), а precision - 29%, тобто 71% замовлень виявляться поганими.
Як ознаки ми використовували різні параметри точки відправлення:
- Час/місце.
- Стан системи (кількість зайнятих машин усіх тарифів і пінів в околиці).
- Параметри пошуку (радіус, кількість кандидатів, обмеження).
Детальніше про ознаки
Концептуально ми хочемо розрізнити дві ситуації:
- "Глухий ліс" - машин тут у цей час не буває.
- "Не пощастило" - машини є, але при пошуку підходящих не виявилося.
Один із прикладів «Не пощастило» — якщо у п'ятницю ввечері у центрі великий попит. Замов багато, бажаючих багато, водіїв на всіх не вистачає. Може вийти так: у піні потрібних водіїв немає. Але буквально через секунди вони з'являються, тому що в цей час тут багато водіїв і їх статус постійно змінюється.
Тому хорошими фічами виявилися різні показники системи на околицях точки А:
- Загальна кількість машин.
- Число машин на замовлення.
- Число недоступних для замовлення машин у статусі "Зайнятий".
- Число користувачів.
Адже чим більше навколо машин, тим більш імовірно, що якась із них стане доступною.
Насправді для нас важливо, щоб не просто знаходилися машини, а й відбувалися успішні поїздки. Тому можна було передбачати можливість успішної поїздки. Але вирішили так не робити, тому що ця величина сильно залежить від користувача та водія.
Як алгоритм навчання моделі застосовували . Для навчання використовували дані, одержані з експерименту. Після впровадження довелося збирати навчальні дані, іноді дозволяючи невеликій кількості користувачів робити замовлення всупереч рішенню моделі.
Підсумки
Результати експерименту вийшли очікуваними: використання моделі дозволяє значно збільшити кількість успішних поїздок за рахунок замовлень без машин, але не просадити надійність.
На даний момент механізм запущений у всіх містах та країнах та за його допомогою відбувається близько 1% успішних поїздок. Причому в деяких містах із невеликою щільністю машин частка таких поїздок сягає 15%.
Інші пости про технології Таксі
Джерело: habr.com