Dobra taksi služba treba da bude sigurna, pouzdana i brza. Korisnik neće ulaziti u detalje: važno mu je da klikne na dugme „Naruči“ i u najkraćem mogućem roku dobije automobil koji će ga odvesti od tačke A do tačke B. Ukoliko nema automobila u blizini, servis treba da odmah obavijestite o tome kako klijent ne bi imao lažna očekivanja. Ali ako se znak "Nema automobila" pojavljuje prečesto, onda je logično da će osoba jednostavno prestati koristiti ovu uslugu i otići kod konkurenta.
U ovom članku želim govoriti o tome kako smo pomoću strojnog učenja riješili problem traženja automobila u područjima niske gustoće (drugim riječima, gdje na prvi pogled nema automobila). I šta je iz toga proizašlo.
prapovijest
Da bi pozvao taksi, korisnik izvodi nekoliko jednostavnih koraka, ali šta se dešava unutar usluge?
| Korisnik | Scena | Backend Yandex.Taxi |
|---|---|---|
| Odabire početnu tačku | Pin | Pokrećemo pojednostavljenu pretragu kandidata - pin search. Na osnovu pronađenih vozača predviđeno je vrijeme dolaska - ETA u pin-u. Izračunava se koeficijent povećanja u datoj tački. |
| Bira destinaciju, tarifu, zahtjeve | Ponuda | Izrađujemo rutu i izračunavamo cijene za sve tarife, uzimajući u obzir rastući koeficijent. |
| Pritiska dugme "Pozovi taksi". | Zakaz | Pokrećemo potpunu potragu za automobilom. Odaberemo najprikladnijeg vozača i ponudimo mu narudžbu. |
na , и već smo pisali. A ovo je priča o pronalaženju vozača. Kada se kreira nalog, pretraga se dešava dva puta: na Pin i na nalog. Potraga za narudžbom odvija se u dvije faze: regrutacija kandidata i rangiranje. Prvo se pronađu dostupni kandidati za vozače koji su najbliži duž grafa puta. Zatim se primjenjuju bonusi i filtriranje. Preostali kandidati se rangiraju i pobjednik dobija ponudu za narudžbu. Ako pristane, dodjeljuje se narudžbini i odlazi na mjesto isporuke. Ako odbije, onda ponuda dolazi na sljedeću. Ako nema više kandidata, potraga počinje ponovo. To ne traje duže od tri minute, nakon čega se narudžba poništava i spaljuje.
Pretraživanje na Pin-u je slično pretraživanju po narudžbi, samo što se narudžba ne kreira i sama pretraga se izvodi samo jednom. Koriste se i pojednostavljene postavke za broj kandidata i radijus pretraživanja. Takva pojednostavljenja su neophodna jer postoji red veličine više pinova nego naloga, a pretraživanje je prilično teška operacija. Ključna stvar za našu priču: ako tokom preliminarne pretrage na Pin-u nisu pronađeni odgovarajući kandidati, onda vam ne dozvoljavamo da naručite. Barem je tako bilo nekad.
Ovo je ono što je korisnik vidio u aplikaciji:
Tražite automobile bez automobila
Jednog dana došli smo do hipoteze: možda se u nekim slučajevima narudžba i dalje može izvršiti, čak i ako na ivici nije bilo automobila. Na kraju krajeva, između pin-a i narudžbe prođe neko vrijeme, a potraga za narudžbom je potpunija i ponekad se ponavlja nekoliko puta: za to vrijeme mogu se pojaviti dostupni upravljački programi. Znali smo i suprotno: ako su se vozači našli na pin-u, nije bila činjenica da će se naći prilikom naručivanja. Ponekad nestanu ili svi odbiju naredbu.
Da bismo testirali ovu hipotezu, pokrenuli smo eksperiment: prestali smo provjeravati prisutnost automobila tokom pretrage na Pin-u za testnu grupu korisnika, odnosno imali su priliku da naprave „narudžbu bez automobila“. Rezultat je bio prilično neočekivan: ako auto nije bio na ivici, onda je u 29% slučajeva pronađen kasnije - prilikom pretraživanja po narudžbi! Štaviše, narudžbe bez automobila nisu se značajno razlikovale od redovnih u pogledu stope otkazivanja, ocjena i drugih pokazatelja kvaliteta. Rezervacije bez automobila činile su 5% svih rezervacija, ali nešto više od 1% svih uspješnih putovanja.
Da bismo razumjeli odakle dolaze izvršioci ovih naloga, pogledajmo njihove statuse tokom pretrage na Pin:
- Dostupan: bio dostupan, ali iz nekog razloga nije bio uključen među kandidate, na primjer, bio je predaleko;
- po narudžbi: bio zauzet, ali se uspio osloboditi ili postati dostupan za ;
- Zauzeto: mogućnost prihvatanja narudžbi bila je onemogućena, ali se tada vozač vratio na liniju;
- Nije dostupno: vozač nije bio online, ali se pojavio.
Dodajmo pouzdanost
Dodatne narudžbe su odlične, ali 29% uspješnih pretraga znači da je 71% vremena korisnik dugo čekao i na kraju nije otišao nigdje. Iako to nije loša stvar sa stanovišta efikasnosti sistema, to zapravo daje korisniku lažnu nadu i gubi vrijeme, nakon čega se uznemiri i (eventualno) prestane koristiti uslugu. Kako bismo riješili ovaj problem, naučili smo predvidjeti vjerovatnoću da će se automobil po narudžbi naći.
Shema je sljedeća:
- Korisnik stavlja pin.
- Na pin-u se vrši pretraga.
- Ako ne bude automobila, predviđamo: možda će se pojaviti.
- I ovisno o vjerovatnoći, dozvoljavamo ili ne dozvoljavamo da naručite, ali vas upozoravamo da je gustina automobila u ovom području u ovom trenutku mala.
U aplikaciji je to izgledalo ovako:
Korištenje modela omogućava vam da preciznije kreirate nove narudžbe i ne uvjeravate ljude uzalud. Odnosno, da se reguliše odnos pouzdanosti i broja narudžbi bez mašina koristeći model preciznog opoziva. Pouzdanost usluge utiče na želju da se proizvod i dalje koristi, odnosno na kraju se sve svodi na broj putovanja.
Malo o preciznosti - opozivuJedan od osnovnih zadataka u mašinskom učenju je zadatak klasifikacije: dodeljivanje objekta jednoj od dve klase. U ovom slučaju, rezultat algoritma mašinskog učenja često postaje numerička procena članstva u jednoj od klasa, na primer, procena verovatnoće. Međutim, radnje koje se izvode obično su binarne: ako je automobil dostupan, dozvolit ćemo vam da ga naručite, a ako ne, onda nećemo. Da budemo konkretni, nazovimo algoritam koji proizvodi numeričku procjenu modelom, a klasifikator pravilom koje ga dodjeljuje jednoj od dvije klase (1 ili –1). Da biste napravili klasifikator na osnovu procjene modela, morate odabrati prag procjene. Kako tačno zavisi u velikoj meri od zadatka.
Pretpostavimo da radimo test (klasifikator) za neku rijetku i opasnu bolest. Na osnovu rezultata testa ili šaljemo pacijenta na detaljniji pregled, ili kažemo: „Dobro, idi kući“. Za nas je mnogo gore poslati bolesnu osobu kući nego bespotrebno pregledati zdravu osobu. Odnosno, želimo da test radi za što više zaista bolesnih ljudi. Ova vrijednost se zove opoziv =. Idealan klasifikator ima 100% opoziv. Degenerirana situacija je slati sve na pregled, onda će i opoziv biti 100%.
Dešava se i obrnuto. Na primjer, pravimo sistem za testiranje učenika i on ima detektor varanja. Ako odjednom provjera ne radi za neke slučajeve varanja, onda je to neugodno, ali nije kritično. S druge strane, izuzetno je loše nepravedno optuživati studente za nešto što nisu uradili. Odnosno, važno nam je da među pozitivnim odgovorima klasifikatora bude što više tačnih, možda nauštrb njihovog broja. To znači da trebate maksimizirati preciznost = . Ako se okidanje dogodi na svim objektima, tada će preciznost biti jednaka frekvenciji definirane klase u uzorku.
Ako algoritam proizvodi numeričku vrijednost vjerovatnoće, onda odabirom različitih pragova možete postići različite vrijednosti preciznosti prisjećanja.
U našem problemu situacija je sljedeća. Opoziv je broj narudžbi koje možemo ponuditi, preciznost je pouzdanost ovih narudžbi. Ovako izgleda krivulja preciznog opoziva našeg modela:
Postoje dva ekstremna slučaja: ne dozvolite nikome da naručuje i dozvolite svima da naručuju. Ako nikome ne dozvolite, tada će opoziv biti 0: mi ne kreiramo narudžbe, ali nijedan od njih neće uspjeti. Ako dozvolimo svima, onda će opoziv biti 100% (primićemo sve moguće narudžbe), a preciznost će biti 29%, odnosno 71% naloga će biti loša.
Kao znakove koristili smo različite parametre polazne tačke:
- Vrijeme/mjesto.
- Stanje sistema (broj zauzetih mašina svih tarifa i pinova u blizini).
- Parametri pretraživanja (radijus, broj kandidata, ograničenja).
Više o znakovima
Konceptualno, želimo razlikovati dvije situacije:
- “Duboka šuma” - ovdje trenutno nema automobila.
- "Nesrećni" - automobila ima, ali prilikom pretraživanja nije bilo odgovarajućih.
Jedan od primjera “Nesrećnika” je ako je u centru u petak uveče velika potražnja. Ima puno narudžbi, puno voljnih, a nema dovoljno vozača za sve. Može ispasti ovako: u pinu nema odgovarajućih drajvera. Ali bukvalno za nekoliko sekundi se pojavljuju, jer u ovom trenutku na ovom mjestu ima puno vozača i njihov status se stalno mijenja.
Stoga su se različiti sistemski indikatori u blizini tačke A pokazali kao dobre karakteristike:
- Ukupan broj automobila.
- Broj automobila po narudžbi.
- Broj automobila nedostupnih za naručivanje u statusu „Zauzeto“.
- Broj korisnika.
Uostalom, što više automobila ima, veća je vjerovatnoća da će jedan od njih postati dostupan.
Zapravo, važno nam je da se ne samo lociraju automobili, već i da se naprave uspješna putovanja. Stoga je bilo moguće predvidjeti vjerovatnoću uspješnog putovanja. Ali odlučili smo da to ne radimo, jer ova vrijednost uvelike ovisi o korisniku i vozaču.
Algoritam obuke modela je bio . Za obuku su korišteni podaci dobiveni eksperimentom. Nakon implementacije, trebalo je prikupiti podatke o obuci, ponekad dozvoljavajući malom broju korisnika da naruče protiv odluke modela.
Ishodi
Rezultati eksperimenta bili su očekivani: korištenje modela omogućava vam da značajno povećate broj uspješnih putovanja zbog narudžbi bez automobila, ali bez ugrožavanja pouzdanosti.
Trenutno je mehanizam pokrenut u svim gradovima i državama i uz njegovu pomoć se dešava oko 1% uspješnih putovanja. Štaviše, u nekim gradovima sa malom gustinom automobila udio takvih putovanja dostiže 15%.
Ostali postovi o taksi tehnologiji
izvor: www.habr.com