Dobrá taxislužba by měla být bezpečná, spolehlivá a rychlá. Uživatel nebude zacházet do podrobností: je pro něj důležité, aby kliknul na tlačítko „Objednat“ a co nejrychleji obdržel vůz, který ho doveze z bodu A do bodu B. Pokud v blízkosti nejsou žádná auta, služba by měla neprodleně o tom informovat, aby klient neměl falešná očekávání. Pokud se ale značka „Žádná auta“ objevuje příliš často, pak je logické, že člověk tuto službu prostě přestane využívat a přejde ke konkurenci.
V tomto článku chci mluvit o tom, jak jsme pomocí strojového učení vyřešili problém hledání aut v oblastech s nízkou hustotou (jinými slovy tam, kde na první pohled žádná auta nejsou). A co z toho vzešlo.
pravěk
Chcete-li zavolat taxi, uživatel provede několik jednoduchých kroků, ale co se děje uvnitř služby?
| ПоР»ÑŒÐ · овРn, Ðμл Noe | Stage | Backend Yandex.Taxi |
|---|---|---|
| Vybere počáteční bod | Kolík | Spouštíme zjednodušené vyhledávání kandidátů - pin search. Na základě nalezených ovladačů je predikován čas příjezdu - ETA v pinu. Vypočítá se rostoucí koeficient v daném bodě. |
| Vybere destinaci, jízdné, požadavky | Nabídka | Stavíme trasu a kalkulujeme ceny pro všechny tarify s přihlédnutím k narůstajícímu koeficientu. |
| Stiskne tlačítko „Zavolat taxi“. | Objednávka | Spouštíme úplné pátrání po autě. Vybereme nejvhodnějšího řidiče a nabídneme mu objednávku. |
O , и už jsme psali. A toto je příběh o hledání řidičů. Když je objednávka vytvořena, vyhledávání probíhá dvakrát: na špendlíku a na objednávce. Hledání zakázky probíhá ve dvou fázích: nábor kandidátů a pořadí. Nejprve jsou nalezeni dostupní kandidáti na řidiče, kteří jsou na silničním grafu nejblíže. Poté se aplikují bonusy a filtrování. Zbývající kandidáti jsou seřazeni a vítěz obdrží nabídku objednávky. Pokud souhlasí, je přidělen k objednávce a jde na výdejní místo. Pokud odmítne, přijde nabídka na další. Pokud již nejsou žádní další kandidáti, hledání začíná znovu. To netrvá déle než tři minuty, poté je objednávka zrušena a spálena.
Vyhledávání na Pin je podobné jako vyhledávání na zakázku, pouze objednávka se nevytváří a samotné vyhledávání se provádí pouze jednou. Používá se také zjednodušené nastavení počtu kandidátů a okruhu vyhledávání. Taková zjednodušení jsou nutná, protože pinů je řádově více než objednávek a vyhledávání je poměrně náročná operace. Klíčový bod našeho příběhu: pokud během předběžného vyhledávání nebyli na Pinu nalezeni žádní vhodní kandidáti, pak vám neumožňujeme zadat objednávku. Alespoň to tak bývalo.
Toto viděl uživatel v aplikaci:
Hledání aut bez aut
Jednoho dne jsme přišli s hypotézou: možná v některých případech lze zakázku ještě dokončit, i když na čepu nebyla žádná auta. Mezi špendlíkem a objednávkou totiž uplyne nějaký čas a hledání objednávky je úplnější a někdy se i několikrát opakuje: během této doby se mohou objevit dostupné ovladače. Věděli jsme i opak: pokud se na čepu našli ovladače, nebylo pravda, že by se našli při objednávce. Někdy zmizí nebo všichni objednávku odmítnou.
Abychom tuto hypotézu ověřili, spustili jsme experiment: přestali jsme kontrolovat přítomnost aut při vyhledávání na pinu pro testovací skupinu uživatelů, tedy měli možnost udělat „objednávku bez aut“. Výsledek byl zcela nečekaný: pokud auto nebylo na čepu, tak ve 29% případů bylo nalezeno později - při hledání na zakázce! Objednávky bez aut se navíc výrazně nelišily od běžných objednávek z hlediska storno sazeb, hodnocení a dalších ukazatelů kvality. Rezervace bez aut tvořily 5 % všech rezervací, ale jen něco málo přes 1 % všech úspěšných cest.
Abychom pochopili, odkud pocházejí vykonavatelé těchto příkazů, podívejme se na jejich stavy během vyhledávání na pinu:
- Dostupný: byl k dispozici, ale z nějakého důvodu nebyl zařazen mezi kandidáty, například byl příliš daleko;
- Na pořadí: byl zaneprázdněn, ale dokázal se osvobodit nebo se stal dostupným pro ;
- Zaneprázdněný: schopnost přijímat objednávky byla zakázána, ale poté se řidič vrátil na linku;
- Není dostupný: řidič nebyl online, ale objevil se.
Dodejme spolehlivost
Dodatečné objednávky jsou skvělé, ale 29 % úspěšných vyhledávání znamená, že 71 % času uživatel dlouho čekal a nakonec nikam neodešel. I když to z hlediska efektivity systému není špatné, ve skutečnosti to dává uživateli falešnou naději a plýtvá časem, po kterém se rozčílí a (možná) přestanou službu používat. Abychom tento problém vyřešili, naučili jsme se předpovídat pravděpodobnost, že bude nalezeno auto na objednávku.
Schéma je následující:
- Uživatel vloží špendlík.
- Na špendlíku se provádí vyhledávání.
- Pokud nebudou žádná auta, předpovídáme: možná se objeví.
- A podle pravděpodobnosti vám objednávku povolujeme nebo nepovolujeme, ale upozorňujeme vás, že hustota aut v této oblasti je v tuto chvíli nízká.
V aplikaci to vypadalo takto:
Použití modelu umožňuje přesněji vytvářet nové objednávky a neuklidňovat lidi zbytečně. Tedy regulovat poměr spolehlivosti a počtu zakázek bez strojů pomocí modelu precision-recall. Spolehlivost služby ovlivňuje touhu produkt nadále používat, to znamená, že nakonec vše závisí na počtu jízd.
Něco málo o přesném vyvoláníJednou ze základních úloh ve strojovém učení je klasifikační úloha: přiřazení objektu do jedné ze dvou tříd. V tomto případě se výsledkem algoritmu strojového učení často stává numerické hodnocení příslušnosti k jedné ze tříd, například hodnocení pravděpodobnosti. Akce, které se provádějí, jsou však obvykle binární: pokud je vůz k dispozici, necháme vás jej objednat, a pokud ne, ne. Abychom byli konkrétní, nazvěme algoritmus, který vytváří numerický odhad, model a klasifikátor pravidlo, které jej přiřadí do jedné ze dvou tříd (1 nebo –1). Chcete-li vytvořit klasifikátor na základě modelového hodnocení, musíte vybrat práh hodnocení. Jak přesně, velmi záleží na úkolu.
Předpokládejme, že provádíme test (klasifikátor) na nějakou vzácnou a nebezpečnou nemoc. Na základě výsledků testů buď pošleme pacienta na podrobnější vyšetření, nebo řekneme: „Dobrá, jdi domů“. Pro nás je poslat nemocného domů mnohem horší, než zbytečně vyšetřovat zdravého člověka. To znamená, že chceme, aby test fungoval pro co nejvíce skutečně nemocných lidí. Tato hodnota se nazývá vyvolání =. Ideální klasifikátor má vybavitelnost 100 %. Zvrhlou situací je poslat všechny na vyšetření, pak bude odvolání také 100%.
Stává se to i obráceně. Děláme například testovací systém pro studenty a ten má detektor podvádění. Pokud najednou kontrola v některých případech podvádění nefunguje, je to nepříjemné, ale ne kritické. Na druhou stranu je extrémně špatné nespravedlivě obviňovat studenty z něčeho, co neudělali. To znamená, že je pro nás důležité, aby mezi kladnými odpověďmi klasifikátoru bylo co nejvíce správných, možná na úkor jejich počtu. To znamená, že musíte maximalizovat přesnost = . Pokud ke spouštění dojde u všech objektů, pak se přesnost bude rovnat frekvenci definované třídy ve vzorku.
Pokud algoritmus vytváří číselnou hodnotu pravděpodobnosti, pak výběrem různých prahových hodnot můžete dosáhnout různých hodnot přesnosti vyvolání.
V našem problému je situace následující. Recall je počet objednávek, které můžeme nabídnout, přesnost je spolehlivost těchto objednávek. Takto vypadá křivka přesného vyvolání našeho modelu:
Existují dva extrémní případy: nedovolit nikomu objednávat a dovolit všem objednávat. Pokud nikomu nedovolíte, pak odvolání bude 0: nevytváříme objednávky, ale žádná z nich se nezdaří. Pokud umožníme všem, pak odvolání bude 100 % (obdržíme všechny možné objednávky) a přesnost bude 29 %, tj. 71 % objednávek bude špatných.
Jako znaky jsme použili různé parametry výchozího bodu:
- Čas/místo.
- Stav systému (počet obsazených strojů všech tarifů a pinů v okolí).
- Parametry vyhledávání (poloměr, počet kandidátů, omezení).
Více o znameních
Koncepčně chceme rozlišovat mezi dvěma situacemi:
- "Hluboký les" - v tuto chvíli zde nejsou žádná auta.
- „Smůla“ - existují auta, ale při hledání nebyla žádná vhodná.
Jedním z příkladů „nešťastných“ je situace, kdy je v pátek večer v centru velká poptávka. Objednávek je hodně, ochotných lidí hodně a řidičů pro všechny málo. Může to dopadnout takto: v kolíku nejsou žádné vhodné ovladače. Objeví se však doslova během několika sekund, protože v tuto dobu je na tomto místě mnoho řidičů a jejich stav se neustále mění.
Proto se různé systémové indikátory v blízkosti bodu A ukázaly jako dobré vlastnosti:
- Celkový počet vozů.
- Počet vozů na objednávku.
- Počet vozů, které nelze objednat ve stavu „Obsazeno“.
- Počet uživatelů.
Ostatně, čím více aut bude, tím je pravděpodobnější, že se jedno z nich uvolní.
Ve skutečnosti je pro nás důležité, aby se nejen auta lokalizovala, ale dělaly se i úspěšné výlety. Proto bylo možné předpovědět pravděpodobnost úspěšného výletu. Ale rozhodli jsme se to neudělat, protože tato hodnota velmi závisí na uživateli a ovladači.
Modelový cvičný algoritmus byl . Data získaná z experimentu byla použita pro trénink. Po implementaci bylo nutné shromáždit tréninková data, což někdy umožnilo malému počtu uživatelů objednávat proti rozhodnutí modelu.
Výsledky
Výsledky experimentu byly podle očekávání: použití modelu umožňuje výrazně zvýšit počet úspěšných jízd díky objednávkám bez aut, ale bez ohrožení spolehlivosti.
V tuto chvíli je mechanismus spuštěn ve všech městech a zemích a s jeho pomocí dochází k cca 1 % úspěšných cest. Navíc v některých městech s nízkou hustotou aut dosahuje podíl takových cest 15 %.
Další příspěvky o technologii Taxi
Zdroj: www.habr.com