Een goede taxiservice moet veilig, betrouwbaar en snel zijn. De gebruiker zal niet in details treden: het is voor hem belangrijk dat hij op de knop ‘Bestellen’ klikt en zo snel mogelijk een auto ontvangt die hem van punt A naar punt B brengt. Als er geen auto’s in de buurt zijn, moet de dienst informeer hier dan direct over, zodat de opdrachtgever geen valse verwachtingen heeft. Maar als het bord 'Geen auto's' te vaak verschijnt, is het logisch dat iemand gewoon stopt met het gebruik van deze service en naar een concurrent gaat.
In dit artikel wil ik het hebben over hoe we met behulp van machine learning het probleem van het zoeken naar auto's in gebieden met een lage dichtheid hebben opgelost (met andere woorden, waar op het eerste gezicht geen auto's zijn). En wat er van terecht kwam.
prehistorie
Om een taxi te bellen voert de gebruiker een paar eenvoudige stappen uit, maar wat gebeurt er binnen de dienst?
| Gebruiker | Stadium | Backend Yandex.Taxi |
|---|---|---|
| Selecteert het startpunt | pin | We lanceren een vereenvoudigde zoektocht naar kandidaten: pin-search. Op basis van de gevonden chauffeurs wordt de aankomsttijd voorspeld - ETA in de pin. De toenemende coëfficiënt op een bepaald punt wordt berekend. |
| Selecteert bestemming, tarief, vereisten | Aanbod | We bouwen een route en berekenen prijzen voor alle tarieven, rekening houdend met de stijgende coëfficiënt. |
| Druk op de knop 'Bel een taxi' | Orde | We starten een volledige zoektocht naar de auto. Wij selecteren de meest geschikte chauffeur en bieden hem een bestelling aan. |
Про , и wij schreven al. En dit is een verhaal over het vinden van chauffeurs. Wanneer een bestelling wordt aangemaakt, wordt er twee keer gezocht: op de pin en op de bestelling. Het zoeken naar een opdracht vindt plaats in twee fasen: de werving van kandidaten en de rangschikking. Eerst worden beschikbare kandidaat-chauffeurs gevonden die het dichtst bij de weggrafiek staan. Vervolgens worden bonussen en filtering toegepast. De overige kandidaten worden gerangschikt en de winnaar ontvangt een bestelaanbod. Als hij akkoord gaat, wordt hij aan de bestelling toegewezen en gaat hij naar het afleverpunt. Als hij weigert, komt het aanbod naar de volgende. Als er geen kandidaten meer zijn, begint de zoektocht opnieuw. Dit duurt maximaal drie minuten, waarna de bestelling wordt geannuleerd en verbrand.
Zoeken op een pin is vergelijkbaar met zoeken op een bestelling, alleen wordt de bestelling niet aangemaakt en wordt de zoekopdracht zelf slechts één keer uitgevoerd. Ook worden vereenvoudigde instellingen voor het aantal kandidaten en de zoekradius gebruikt. Dergelijke vereenvoudigingen zijn nodig omdat er een orde van grootte meer pinnen dan orders zijn, en zoeken een nogal moeilijke operatie is. Kernpunt van ons verhaal: als er tijdens het vooronderzoek geen geschikte kandidaten op de Pin zijn gevonden, dan laten wij u geen bestelling plaatsen. Tenminste, zo was het vroeger.
Dit is wat de gebruiker in de applicatie zag:
Zoek naar auto's zonder auto's
Op een dag kwamen we met een hypothese: misschien kan de bestelling in sommige gevallen toch worden voltooid, zelfs als er geen auto's op de pin stonden. Er verstrijkt immers enige tijd tussen de pincode en de bestelling, en het zoeken naar de bestelling is completer en wordt soms meerdere keren herhaald: gedurende deze tijd kunnen beschikbare stuurprogramma's verschijnen. Wij wisten ook het tegenovergestelde: als er chauffeurs op de pin werden aangetroffen, was het geen feit dat deze bij het bestellen zouden worden gevonden. Soms verdwijnen ze of weigert iedereen de bestelling.
Om deze hypothese te testen, hebben we een experiment gelanceerd: we zijn gestopt met het controleren van de aanwezigheid van auto's tijdens het zoeken op een pin voor een testgroep gebruikers, dat wil zeggen dat ze de mogelijkheid hadden om een 'bestelling zonder auto's' te plaatsen. Het resultaat was nogal onverwacht: stond de auto niet op de pin, dan werd deze in 29% van de gevallen later gevonden - bij het zoeken op de bestelling! Bovendien verschilden bestellingen zonder auto's niet significant van reguliere bestellingen in termen van annuleringspercentages, beoordelingen en andere kwaliteitsindicatoren. Boekingen zonder auto waren goed voor 5% van alle boekingen, maar iets meer dan 1% van alle succesvolle reizen.
Om te begrijpen waar de uitvoerders van deze orders vandaan komen, kijken we naar hun status tijdens een zoekopdracht op een pin:
- Beschikbaar: was beschikbaar, maar werd om de een of andere reden niet opgenomen in de kandidaten, hij was bijvoorbeeld te ver weg;
- Op bestelling: had het druk, maar wist zich te bevrijden of zich beschikbaar te stellen ;
- Druk bezig: de mogelijkheid om bestellingen te accepteren was uitgeschakeld, maar toen keerde de chauffeur terug naar de rij;
- Niet beschikbaar: de chauffeur was niet online, maar hij verscheen.
Laten we betrouwbaarheid toevoegen
Extra bestellingen zijn geweldig, maar 29% van de succesvolle zoekopdrachten betekent dat de gebruiker 71% van de tijd lang heeft gewacht en uiteindelijk nergens heen ging. Hoewel dit vanuit het oogpunt van systeemefficiëntie geen slechte zaak is, geeft het de gebruiker feitelijk valse hoop en verspilt het tijd, waarna hij boos wordt en (mogelijk) stopt met het gebruik van de dienst. Om dit probleem op te lossen, hebben we geleerd de waarschijnlijkheid te voorspellen dat een auto in bestelling wordt gevonden.
Het schema is als volgt:
- De gebruiker plaatst een pincode.
- Er wordt op de pin gezocht.
- Als er geen auto's zijn, voorspellen we: misschien verschijnen ze wel.
- En afhankelijk van de waarschijnlijkheid staan we u wel of niet toe een bestelling te plaatsen, maar we waarschuwen u dat de dichtheid van auto's in dit gebied op dit moment laag is.
In de applicatie zag het er zo uit:
Door het model te gebruiken, kunt u nauwkeuriger nieuwe orders creëren en mensen niet tevergeefs geruststellen. Dat wil zeggen: de verhouding tussen betrouwbaarheid en het aantal bestellingen zonder machines regelen met behulp van het precisie-terugroepmodel. De betrouwbaarheid van de dienst heeft invloed op de wens om het product te blijven gebruiken, het komt uiteindelijk allemaal neer op het aantal ritten.
Een beetje over precisie-herinneringEen van de basistaken bij machinaal leren is de classificatietaak: het toewijzen van een object aan een van de twee klassen. In dit geval wordt het resultaat van het machine learning-algoritme vaak een numerieke beoordeling van het lidmaatschap van een van de klassen, bijvoorbeeld een waarschijnlijkheidsbeoordeling. De acties die worden uitgevoerd zijn echter meestal binair: als de auto beschikbaar is, laten we je hem bestellen, en zo niet, dan niet. Om specifiek te zijn: laten we een algoritme dat een numerieke schatting produceert een model noemen, en een classificator een regel die deze aan een van de twee klassen (1 of –1) toewijst. Om een classificatie te maken op basis van de modelbeoordeling, moet u een beoordelingsdrempel selecteren. Hoe precies hangt sterk af van de taak.
Stel dat we een test (classificator) doen voor een zeldzame en gevaarlijke ziekte. Op basis van de testresultaten sturen we de patiënt voor een uitgebreider onderzoek, of zeggen we: “Goed, ga naar huis.” Voor ons is het naar huis sturen van een zieke veel erger dan het onnodig onderzoeken van een gezond persoon. Dat wil zeggen: we willen dat de test voor zoveel mogelijk echt zieke mensen werkt. Deze waarde wordt recall = genoemd. Een ideale classificator heeft een terugroepactie van 100%. Een gedegenereerde situatie is om iedereen ter onderzoek op te sturen, dan is de terugroepactie ook 100%.
Andersom gebeurt het ook. We maken bijvoorbeeld een toetssysteem voor studenten, en daar zit een spiekdetector in. Als de cheque bij sommige gevallen van bedrog plotseling niet werkt, is dit onaangenaam, maar niet kritisch. Aan de andere kant is het buitengewoon slecht om studenten onterecht te beschuldigen van iets dat ze niet hebben gedaan. Dat wil zeggen, het is belangrijk voor ons dat er onder de positieve antwoorden van de classificator zoveel mogelijk correcte antwoorden zijn, misschien ten koste van hun aantal. Dit betekent dat u de precisie = moet maximaliseren . Als triggering op alle objecten plaatsvindt, is de precisie gelijk aan de frequentie van de gedefinieerde klasse in het monster.
Als het algoritme een numerieke waarschijnlijkheidswaarde produceert, kunt u door verschillende drempels te selecteren verschillende precisie-herinneringswaarden bereiken.
In ons probleem is de situatie als volgt. Recall is het aantal orders dat we kunnen aanbieden, precisie is de betrouwbaarheid van deze orders. Dit is hoe de precisie-herinneringscurve van ons model eruit ziet:
Er zijn twee extreme gevallen: laat niemand bestellen en laat iedereen bestellen. Als u niemand toestaat, is de terugroepactie 0: we maken geen bestellingen, maar geen enkele zal mislukken. Als we iedereen toestaan, zal de terugroepactie 100% zijn (we zullen alle mogelijke bestellingen ontvangen) en de nauwkeurigheid 29%, dat wil zeggen dat 71% van de bestellingen slecht zal zijn.
We gebruikten verschillende parameters van het startpunt als tekens:
- Tijd/plaats.
- Systeemstatus (aantal bezette machines van alle tarieven en pinnen in de buurt).
- Zoekparameters (straal, aantal kandidaten, beperkingen).
Meer over de borden
Conceptueel willen we onderscheid maken tussen twee situaties:
- "Deep forest" - er zijn hier op dit moment geen auto's.
- "Pech" - er zijn auto's, maar bij het zoeken waren er geen geschikte.
Een voorbeeld van ‘Pech’ is als er op vrijdagavond veel vraag is in het centrum. Er zijn veel bestellingen, veel mensen bereid, en niet genoeg chauffeurs voor iedereen. Het kan zo uitpakken: er zitten geen geschikte stuurprogramma's in de pin. Maar letterlijk binnen enkele seconden verschijnen ze, omdat er op dit moment veel chauffeurs op deze plek zijn en hun status voortdurend verandert.
Daarom bleken verschillende systeemindicatoren in de buurt van punt A goede eigenschappen te zijn:
- Totaal aantal auto's.
- Aantal auto's in bestelling.
- Het aantal auto's dat niet kan worden besteld in de status 'Bezet'.
- Aantal gebruikers.
Hoe meer auto’s er zijn, hoe groter de kans dat er één beschikbaar komt.
Sterker nog, voor ons is het belangrijk dat er niet alleen auto’s worden gelokaliseerd, maar dat er ook succesvolle reizen worden gemaakt. Daarom was het mogelijk om de waarschijnlijkheid van een succesvolle reis te voorspellen. Maar we hebben besloten dit niet te doen, omdat deze waarde sterk afhankelijk is van de gebruiker en de bestuurder.
Het modeltrainingsalgoritme was . Gegevens verkregen uit het experiment werden gebruikt voor training. Na de implementatie moesten trainingsgegevens worden verzameld, waardoor soms een klein aantal gebruikers tegen de beslissing van het model in kon bestellen.
Resultaten van
De resultaten van het experiment waren zoals verwacht: door het model te gebruiken, kun je het aantal succesvolle reizen aanzienlijk vergroten door bestellingen zonder auto's, maar zonder de betrouwbaarheid in gevaar te brengen.
Op dit moment is het mechanisme in alle steden en landen gelanceerd en met zijn hulp vindt ongeveer 1% van de succesvolle reizen plaats. Bovendien bereikt het aandeel van dergelijke ritten in sommige steden met een lage autodichtheid 15%.
Andere berichten over taxitechnologie
Bron: www.habr.com