Un bonu serviziu di taxi deve esse sicuru, affidabile è veloce. L'utilizatore ùn entrerà micca in i dettagli: hè impurtante per ellu chì cliccà u buttone "Ordine" è riceve una vittura u più prestu pussibule chì u purterà da u puntu A à u puntu B. Se ùn ci hè micca vitture vicinu, u serviziu duveria. Infurmà immediatamente nantu à questu per chì u cliente ùn hà micca esse falsi aspettative. Ma s'è u segnu "No cars" appare troppu spessu, hè logicu chì una persona smetta di utilizà stu serviziu è andate à un cuncurrente.
In questu articulu vogliu parlà di cumu, utilizendu l'apprendimentu di macchina, avemu risoltu u prublema di ricerca di vitture in spazii di bassa densità (in altre parolle, induve, à prima vista, ùn ci hè micca vitture). È ciò chì hè vinutu.
Pristoria
Per chjamà un taxi, l'utilizatore face uni pochi di passi simplici, ma chì succede in u serviziu?
| Utilizatori | Stage | Backend Yandex.Taxi |
|---|---|---|
| Sceglie u puntu di partenza | Pin | Lancemu una ricerca simplificata per i candidati - pin search. Basatu nantu à i cunduttori truvati, l'ora d'arrivu hè prevista - ETA in u pin. U coefficient crescente in un puntu datu hè calculatu. |
| Sceglie destinazione, tariffa, esigenze | Offerta | Custruemu una strada è calculemu i prezzi per tutti i tariffi, tenendu in contu u coefficientu crescente. |
| Press u buttone "Call a Taxi". | Ordine | Lanciamu una ricerca cumpleta per a vittura. Selezziemu u cunduttore più adattatu è li offre un ordine. |
nantu , и avemu digià scrittu. È questa hè una storia di truvà i cunduttori. Quandu un ordine hè creatu, a ricerca si faci duie volte: nantu à u Pin è in l'ordine. A ricerca di un ordine si faci in duie tappe: reclutazione di candidati è ranking. Prima, i cunduttori candidati dispunibuli sò truvati chì sò più vicinu à u graficu di a strada. Allora i bonus è i filtri sò applicati. I candidati rimanenti sò classificati è u vincitore riceve una offerta di ordine. S'ellu accunsente, hè assignatu à l'ordine è va à u puntu di consegna. S'ellu ricusa, allura l'offerta vene à u prossimu. Se ùn ci sò più candidati, a ricerca principia di novu. Questu ùn dura micca più di trè minuti, dopu chì l'ordine hè annullatu è brusgiatu.
A ricerca nantu à un Pin hè simile à a ricerca nantu à un ordine, solu l'ordine ùn hè micca creatu è a ricerca stessu hè fatta solu una volta. I paràmetri simplificati per u numeru di candidati è u raghju di ricerca sò ancu usati. Tali simplificazioni sò necessarii perchè ci sò un ordine di grandezza più pins chì ordini, è a ricerca hè una operazione piuttostu difficiule. U puntu chjave per a nostra storia: s'ellu durante a ricerca preliminari ùn sò micca stati trovati candidati adattati nantu à u Pin, allora ùn permettenu micca di mette un ordine. Almenu cusì era prima.
Questu hè ciò chì l'utilizatore hà vistu in l'applicazione:
Ricerca di vitture senza vitture
Un ghjornu avemu avutu una ipotesi: forse in certi casi l'ordine pò ancu esse cumpletu, ancu s'ellu ùn ci era micca vitture nantu à u pin. Dopu tuttu, un pocu di tempu passa trà u pin è l'ordine, è a ricerca di l'ordine hè più cumpleta è qualchì volta ripetuta parechje volte: in questu tempu, i cunduttori dispunibuli ponu appare. Sapemu ancu u cuntrariu: se i cunduttori sò stati truvati nantu à u pin, ùn era micca un fattu chì si trovanu quandu l'ordine. Calchì volta spariscanu o tutti ricusanu l'ordine.
Per pruvà sta ipotesi, avemu lanciatu un esperimentu: avemu cessatu di verificà a prisenza di vitture durante una ricerca nantu à un Pin per un gruppu di teste d'utilizatori, vale à dì, anu avutu l'uppurtunità di fà un "ordine senza vitture". U risultatu era abbastanza inesperu: se a vittura ùn era micca nantu à u pin, allora in 29% di i casi hè stata trovata dopu - quandu cercate nantu à l'ordine! Inoltre, l'ordine senza vitture ùn era micca significativamente sfarente di l'ordine regulare in termini di tassi di annullamentu, valutazioni è altri indicatori di qualità. E riservazioni senza vitture rapprisentanu u 5% di tutte e riservazioni, ma pocu più di l'1% di tutti i viaghji successi.
Per capiscenu d'induve venenu l'esecutori di questi ordini, fighjemu i so stati durante una ricerca nantu à un Pin:
- Disponibile: era dispunibule, ma per qualchi ragiuni ùn era micca inclusu in i candidati, per esempiu, era troppu luntanu;
- In ordine: era occupatu, ma hà sappiutu di liberà ellu stessu o di diventà dispunibule ;
- occupatu: a capacità di accettà ordini hè stata disattivata, ma dopu u cunduttore hà tornatu à a linea;
- Ùn dispunibile: u cunduttore ùn era micca in linea, ma apparsu.
Aghjunghjemu a fiducia
Ordini supplementari sò grandi, ma u 29% di e ricerche successe significa chì u 71% di u tempu chì l'utilizatore hà aspittatu assai tempu è hà finitu per andà in nulla. Ancu s'ellu ùn hè micca una mala cosa da un puntu di vista di l'efficienza di u sistema, in realtà dà à l'utilizatore una falsa speranza è perde u tempu, dopu chì si arrabbianu è (possibilmente) cessanu di utilizà u serviziu. Per risolve stu prublema, avemu amparatu à predichendu a probabilità chì una vittura in ordine serà trovu.
U schema hè cusì:
- L'utilizatore mette un pin.
- Una ricerca hè fatta nantu à u pin.
- S'ellu ùn ci hè micca vitture, predichemu: forse apparisceranu.
- E sicondu a probabilità, permettenu o ùn permettenu micca di fà un ordine, ma avemu avvistu chì a densità di vitture in questa zona in questu tempu hè bassu.
In l'applicazione pareva cusì:
Utilizà u mudellu permette di creà novi ordini più precisamente è micca rassicurà a ghjente in vain. Questu hè, per regulà u rapportu di affidabilità è u numeru di ordini senza machini chì utilizanu u mudellu di precisione-recall. L'affidabilità di u serviziu influenza u desideriu di cuntinuà à aduprà u pruduttu, vale à dì, à a fine, tuttu vene à u numeru di viaghji.
Un pocu di precisione-recallUnu di i travaglii basi in l'apprendimentu machine hè u compitu di classificazione: assignà un oggettu à una di duie classi. In questu casu, u risultatu di l'algoritmu di l'apprendimentu di a macchina spessu diventa una valutazione numerica di l'appartenenza à una di e classi, per esempiu, una valutazione di probabilità. In ogni casu, l'azzioni chì sò realizati sò di solitu binari: se a vittura hè dispunibule, allora vi permetteremu di urdinà, è s'ellu ùn hè micca, allora ùn avemu micca. Per esse specifichi, chjamemu un algoritmu chì pruduce una stima numerica un mudellu, è un classificatore una regula chì l'assigna à una di duie classi (1 o -1). Per fà un classificatore basatu nantu à a valutazione di u mudellu, avete bisognu di selezziunà un limitu di valutazione. Cumu esattamente dipende assai di u compitu.
Supponemu chì facemu una prova (classificatore) per una malatia rara è periculosa. Basatu nantu à i risultati di a prova, o mandemu u paziente per un esame più detallatu, o dicemu: "Bè, vai in casa". Per noi, mandà una persona malata in casa hè assai peghju chè esaminà inutilmente una persona sana. Vale à dì, vulemu chì a prova funziona per quant'è più persone veramente malate pussibule. Stu valore hè chjamatu recall =. Un classificatore ideale hà un ricordu di 100%. Una situazione degenerata hè di mandà à tutti per l'esaminazione, allora u ricurdamentu serà ancu 100%.
Succede ancu à l'inversu. Per esempiu, facemu un sistema di teste per i studienti, è hà un detector di tradimentu. Se di colpu u cuntrollu ùn viaghja micca per certi casi di ingannà, allora questu hè dispiacevule, ma micca criticu. Per d 'altra banda, hè estremamente male per accusà ingiustamente i studienti di qualcosa chì ùn anu micca fattu. Vale à dì, hè impurtante per noi chì trà e risposti pusitivi di u classificatore ci sò tanti curretti pussibuli, forse à u detrimentu di u so numeru. Questu significa chì avete bisognu di maximizà a precisione = . Se l'attivazione si trova nantu à tutti l'uggetti, a precisione serà uguale à a frequenza di a classa definita in u sample.
Se l'algoritmu pruduce un valore di probabilità numerica, allora selezziunendu diverse soglie, pudete ottene diverse valori di precisione-recall.
In u nostru prublema, a situazione hè a siguenti. Recall hè u numeru di ordini chì pudemu offre, a precisione hè a fiducia di questi ordini. Eccu ciò chì a curva di precisione-ricordu di u nostru mudellu s'assumiglia:
Ci sò dui casi estremi: ùn permettenu micca à nimu di urdinà è permettenu à tutti di urdinà. Se ùn permettenu micca à nimu, allora u ricordu serà 0: ùn creamu micca ordini, ma nimu ùn falla. Se permettemu à tutti, allora u ricordu serà 100% (avemu da riceve tutti l'ordini pussibuli), è a precisione serà 29%, vale à dì 71% di l'ordini seranu male.
Avemu usatu diversi paràmetri di u puntu di partenza cum'è segni:
- U tempu / locu.
- Statu di u sistema (numaru di machini occupati di tutti i tariffi è pins in a vicinanza).
- Paràmetri di ricerca (radiu, numeru di candidati, restrizioni).
Più nantu à i segni
In u cuncettu, vulemu distingue trà duie situazioni:
- "Deep forest" - ùn ci sò micca vitture quì à questu tempu.
- "Unlucky" - ci sò vitture, ma quandu cercanu ùn ci era micca adattati.
Un esempiu di "Unlucky" hè s'ellu ci hè assai dumanda in u centru u venneri sera. Ci hè assai ordini, assai persone disposti, è micca abbastanza cunduttori per tutti. Puderia esse cusì: ùn ci sò micca cunduttori adattati in u pin. Ma littiralmenti in sicondi si prisentanu, perchè à questu tempu ci sò assai cunduttori in questu locu è u so status hè cambiatu constantemente.
Per quessa, diversi indicatori di u sistema vicinu à u puntu A sò stati boni caratteristiche:
- U numeru tutale di vitture.
- Numero di vitture in ordine.
- U numeru di vitture indisponibili per l'ordine in u statu "Busy".
- Numero di utilizatori.
Dopu tuttu, più vitture ci sò, u più prubabile hè chì unu di elli diventerà dispunibule.
In fatti, hè impurtante per noi chì micca solu i vitture sò situati, ma ancu i viaghji successi sò fatti. Per quessa, era pussibule predichendu a probabilità di un viaghju successu. Ma avemu decisu di ùn fà micca questu, perchè stu valore dipende assai di l'utilizatori è di u driver.
L'algoritmu di furmazione mudellu era . I dati ottenuti da l'esperimentu sò stati utilizati per a furmazione. Dopu à l'implementazione, i dati di furmazione anu da esse recullati, à volte permettenu à un picculu numeru d'utilizatori per urdinà contru à a decisione di u mudellu.
Risultati
I risultati di l'esperimentu eranu cum'è s'aspittava: l'usu di u mudellu permette di aumentà significativamente u nùmeru di viaghji successi per via di ordini senza vitture, ma senza compromette a fiducia.
À u mumentu, u mecanismu hè statu lanciatu in tutte e cità è i paesi è cù u so aiutu, circa 1% di i viaghji riesciuti. Inoltre, in certi cità cù una bassa densità di vitture, a parte di tali viaghji righjunghji u 15%.
Altri posti nantu à a tecnulugia di Taxi
Source: www.habr.com