Dobrá taxislužba by mala byť bezpečná, spoľahlivá a rýchla. Používateľ nebude zachádzať do detailov: je pre neho dôležité, aby klikol na tlačidlo „Objednať“ a čo najrýchlejšie dostal auto, ktoré ho odvezie z bodu A do bodu B. Ak v blízkosti nie sú žiadne autá, služba by mala bezodkladne o tom informovať, aby klient nemal tam boli falošné očakávania. Ak sa však značka „Žiadne autá“ objavuje príliš často, je logické, že človek túto službu jednoducho prestane využívať a pôjde ku konkurencii.
V tomto článku chcem hovoriť o tom, ako sme pomocou strojového učenia vyriešili problém vyhľadávania áut v oblastiach s nízkou hustotou (inými slovami, kde na prvý pohľad žiadne autá nie sú). A čo z toho vzniklo.
pravek
Ak chcete zavolať taxík, používateľ vykoná niekoľko jednoduchých krokov, čo sa však deje v rámci služby?
| Užívateľ | štádium | Backend Yandex.Taxi |
|---|---|---|
| Vyberie počiatočný bod | kolík | Spúšťame zjednodušené vyhľadávanie kandidátov – pin search. Na základe nájdených ovládačov sa predpovedá čas príchodu - ETA v kolíku. Vypočíta sa rastúci koeficient v danom bode. |
| Vyberie destináciu, cestovné, požiadavky | Ponuka | Zostavíme trasu a vypočítame ceny pre všetky tarify s prihliadnutím na zvyšujúci sa koeficient. |
| Stlačí tlačidlo „Zavolať taxi“. | poriadok | Spúšťame úplné pátranie po aute. Vyberieme najvhodnejšieho vodiča a ponúkneme mu objednávku. |
o , и už sme písali. A toto je príbeh o hľadaní vodičov. Po vytvorení objednávky sa vyhľadávanie uskutoční dvakrát: na pine a na objednávke. Hľadanie zákazky prebieha v dvoch fázach: nábor kandidátov a poradie. Najprv sa nájdu dostupní kandidáti vodiči, ktorí sú najbližšie pozdĺž cestného grafu. Potom sa aplikujú bonusy a filtrovanie. Zostávajúci kandidáti sú zoradení a víťaz dostane ponuku na objednávku. Ak súhlasí, je priradený k objednávke a ide na výdajné miesto. Ak odmietne, ponuka príde ďalšiemu. Ak už nie sú žiadni kandidáti, hľadanie začína odznova. Toto netrvá dlhšie ako tri minúty, po ktorých sa objednávka zruší a spáli.
Vyhľadávanie na Pin je podobné ako vyhľadávanie na zákazku, len zákazka sa nevytvára a samotné vyhľadávanie sa vykonáva iba raz. Používajú sa aj zjednodušené nastavenia počtu kandidátov a okruhu vyhľadávania. Takéto zjednodušenia sú potrebné, pretože pinov je rádovo viac ako objednávok a vyhľadávanie je pomerne náročná operácia. Kľúčový bod nášho príbehu: ak sa počas predbežného vyhľadávania nenašli žiadni vhodní kandidáti na Pin, potom vám neumožňujeme zadať objednávku. Aspoň tak to bývalo.
Toto videl používateľ v aplikácii:
Hľadajte autá bez áut
Jedného dňa sme prišli s hypotézou: možno v niektorých prípadoch možno objednávku ešte dokončiť, aj keď na špendlíku neboli žiadne autá. Medzi špendlíkom a objednávkou totiž uplynie nejaký čas a hľadanie objednávky je kompletnejšie a niekedy sa aj niekoľkokrát opakuje: počas tejto doby sa môžu objaviť dostupné ovládače. Vedeli sme aj opak: ak sa našli vodiči na špendlíku, nebolo faktom, že by sa našli pri objednávke. Niekedy zmiznú alebo každý objednávku odmietne.
Aby sme otestovali túto hypotézu, spustili sme experiment: prestali sme kontrolovať prítomnosť áut počas vyhľadávania na PIN pre testovaciu skupinu používateľov, t. j. mali možnosť urobiť „objednávku bez áut“. Výsledok bol celkom neočakávaný: ak auto nebolo na špendlíku, tak v 29% prípadov sa našlo až neskôr - pri hľadaní na objednávke! Navyše, objednávky bez áut sa výrazne nelíšili od bežných objednávok, pokiaľ ide o storno sadzby, hodnotenia a ďalšie ukazovatele kvality. Rezervácie bez áut tvorili 5 % všetkých rezervácií, ale len niečo vyše 1 % všetkých úspešných ciest.
Aby sme pochopili, odkiaľ pochádzajú vykonávatelia týchto príkazov, pozrime sa na ich stavy počas vyhľadávania na pine:
- K dispozícii: bol k dispozícii, ale z nejakého dôvodu nebol zaradený medzi kandidátov, napríklad bol príliš ďaleko;
- Na objednávku: bol zaneprázdnený, ale podarilo sa mu oslobodiť alebo sa stať dostupným pre ;
- Zaneprázdnený: schopnosť prijímať objednávky bola zakázaná, ale potom sa vodič vrátil na linku;
- Nie je k dispozícií: vodič nebol online, ale objavil sa.
Pridajme spoľahlivosť
Dodatočné objednávky sú skvelé, ale 29 % úspešných vyhľadávaní znamená, že 71 % času používateľ dlho čakal a nakoniec nikam neodišiel. Aj keď to z hľadiska efektivity systému nie je zlá vec, v skutočnosti to dáva používateľovi falošnú nádej a stráca čas, po ktorom sa rozčúli a (možno) prestane službu používať. Aby sme tento problém vyriešili, naučili sme sa predpovedať pravdepodobnosť, že sa nájde auto na objednávku.
Schéma je takáto:
- Používateľ umiestni špendlík.
- Na špendlíku sa vykoná vyhľadávanie.
- Ak tam nebudú žiadne autá, predpovedáme: možno sa objavia.
- A v závislosti od pravdepodobnosti vám umožňujeme alebo neumožňujeme zadať objednávku, ale upozorňujeme vás, že hustota áut v tejto oblasti je v tomto čase nízka.
V aplikácii to vyzeralo takto:
Použitie modelu umožňuje presnejšie vytvárať nové objednávky a zbytočne neupokojovať ľudí. Teda regulovať pomer spoľahlivosti a počtu objednávok bez strojov pomocou modelu precision-recall. Spoľahlivosť služby ovplyvňuje túžbu pokračovať v používaní produktu, t.j. v konečnom dôsledku všetko závisí od počtu jázd.
Trochu o presnom vyvolaníJednou zo základných úloh strojového učenia je klasifikačná úloha: priradenie objektu do jednej z dvoch tried. V tomto prípade sa výsledkom algoritmu strojového učenia často stáva numerické hodnotenie príslušnosti k jednej z tried, napríklad hodnotenie pravdepodobnosti. Akcie, ktoré sa vykonávajú, sú však zvyčajne binárne: ak je auto k dispozícii, necháme vám ho objednať, a ak nie, nie. Aby sme boli konkrétni, nazvime algoritmus, ktorý vytvára numerický odhad, model a klasifikátor pravidlo, ktoré ho priraďuje k jednej z dvoch tried (1 alebo –1). Ak chcete vytvoriť klasifikátor na základe hodnotenia modelu, musíte vybrať prah hodnotenia. Ako presne závisí od úlohy.
Predpokladajme, že robíme test (klasifikátor) na nejaké zriedkavé a nebezpečné ochorenie. Na základe výsledkov testov buď pošleme pacienta na podrobnejšie vyšetrenie, alebo povieme: „Dobre, choď domov“. Poslanie chorého domov je pre nás oveľa horšie ako zbytočné vyšetrenie zdravého človeka. To znamená, že chceme, aby test fungoval pre čo najviac skutočne chorých ľudí. Táto hodnota sa nazýva odvolanie =. Ideálny klasifikátor má 100% vybavovanie. Degenerovaná situácia je poslať všetkých na vyšetrenie, potom bude aj odvolanie 100%.
Stáva sa to aj naopak. Robíme napríklad testovací systém pre študentov a ten má detektor podvádzania. Ak zrazu kontrola v niektorých prípadoch podvádzania nefunguje, je to nepríjemné, ale nie kritické. Na druhej strane je mimoriadne zlé nespravodlivo obviňovať študentov z niečoho, čo neurobili. To znamená, že je pre nás dôležité, aby medzi kladnými odpoveďami klasifikátora bolo čo najviac správnych, možno na úkor ich počtu. To znamená, že musíte maximalizovať presnosť = . Ak sa spustenie vyskytne na všetkých objektoch, presnosť sa bude rovnať frekvencii definovanej triedy vo vzorke.
Ak algoritmus vytvára číselnú hodnotu pravdepodobnosti, potom výberom rôznych prahových hodnôt môžete dosiahnuť rôzne hodnoty presnosti.
V našom probléme je situácia nasledovná. Recall je počet objednávok, ktoré môžeme ponúknuť, presnosť je spoľahlivosť týchto objednávok. Takto vyzerá krivka presnosti vyvolania nášho modelu:
Sú dva extrémne prípady: nedovoliť nikomu objednávať a dovoliť každému objednávať. Ak nikomu nedovolíte, potom bude odvolanie 0: nevytvárame objednávky, ale žiadna z nich nezlyhá. Ak povolíme všetkým, stiahnutie bude 100 % (dostaneme všetky možné objednávky) a presnosť bude 29 %, t. j. 71 % objednávok bude zlých.
Ako znaky sme použili rôzne parametre východiskového bodu:
- Čas/miesto.
- Stav systému (počet obsadených strojov všetkých taríf a pinov v okolí).
- Parametre vyhľadávania (polomer, počet kandidátov, obmedzenia).
Viac o znameniach
Koncepčne chceme rozlišovať medzi dvoma situáciami:
- „Hlboký les“ - v súčasnosti tu nie sú žiadne autá.
- „Nešťastné“ - existujú autá, ale pri hľadaní neboli žiadne vhodné.
Jedným príkladom „nešťastného“ je, ak je v piatok večer v centre veľký dopyt. Objednávok je veľa, ochotných ľudí veľa a vodičov nie je pre každého dosť. Môže to dopadnúť takto: v kolíku nie sú žiadne vhodné ovládače. Objavia sa však doslova v priebehu niekoľkých sekúnd, pretože v tomto čase je na tomto mieste veľa vodičov a ich stav sa neustále mení.
Preto sa rôzne systémové indikátory v blízkosti bodu A ukázali ako dobré vlastnosti:
- Celkový počet áut.
- Počet áut na objednávku.
- Počet áut, ktoré nie je možné objednať v stave „Obsadené“.
- Počet používateľov.
Veď čím viac áut je, tým je pravdepodobnejšie, že sa jedno z nich sprístupní.
V skutočnosti je pre nás dôležité, že nielen autá sa nachádzajú, ale robia sa aj úspešné výlety. Preto bolo možné predpovedať pravdepodobnosť úspešného výletu. Rozhodli sme sa to však neurobiť, pretože táto hodnota veľmi závisí od používateľa a ovládača.
Modelový tréningový algoritmus bol . Údaje získané z experimentu boli použité na tréning. Po implementácii bolo potrebné zhromaždiť údaje o školení, čo niekedy umožnilo malému počtu používateľov objednať si proti rozhodnutiu modelu.
Výsledky
Výsledky experimentu boli podľa očakávania: použitie modelu umožňuje výrazne zvýšiť počet úspešných jázd vďaka objednávkam bez áut, ale bez ohrozenia spoľahlivosti.
V súčasnosti je mechanizmus spustený vo všetkých mestách a krajinách a s jeho pomocou sa uskutoční asi 1% úspešných ciest. Navyše v niektorých mestách s nízkou hustotou áut dosahuje podiel takýchto ciest 15 %.
Ďalšie príspevky o technike taxi
Zdroj: hab.com