Un bo servizo de taxi debe ser seguro, fiable e rápido. O usuario non entrará en detalles: é importante para el que prema no botón "Pedir" e reciba o máis rápido posible un coche que o levará do punto A ao punto B. Se non hai coches preto, o servizo debería informar inmediatamente sobre isto para que o cliente non teña expectativas falsas. Pero se o sinal "Non hai coches" aparece con demasiada frecuencia, é lóxico que unha persoa simplemente deixe de usar este servizo e vaia a un competidor.
Neste artigo quero falar de como, mediante a aprendizaxe automática, resolvemos o problema da busca de coches en zonas de baixa densidade (é dicir, onde, a primeira vista, non hai coches). E que saíu diso.
prehistoria
Para chamar a un taxi, o usuario realiza uns sinxelos pasos, pero que pasa dentro do servizo?
| Usuario | Etapa | Backend Yandex.Taxi |
|---|---|---|
| Selecciona o punto de partida | Pin | Estamos lanzando unha busca simplificada de candidatos: busca de pin. Segundo os condutores atopados, prevese a hora de chegada: ETA no pin. Calcúlase o coeficiente crecente nun punto dado. |
| Selecciona destino, tarifa e requisitos | Oferta | Construímos unha ruta e calculamos prezos para todas as tarifas, tendo en conta o coeficiente crecente. |
| Preme o botón "Chamar a un taxi". | Orde | Lanzamos unha busca completa do coche. Seleccionamos o condutor máis axeitado e ofrecémoslle un pedido. |
en , и xa escribimos. E esta é unha historia sobre atopar condutores. Cando se crea unha orde, a busca ocorre dúas veces: no Pin e na orde. A busca dunha orde realízase en dúas fases: captación de candidatos e clasificación. En primeiro lugar, atópanse os condutores candidatos dispoñibles que están máis preto do gráfico da estrada. Despois aplícanse bonos e filtrado. Os candidatos restantes son clasificados e o gañador recibe unha oferta de pedido. Se está de acordo, asígnaselle o pedido e diríxese ao punto de entrega. Se se rexeita, a oferta pasa á seguinte. Se non hai máis candidatos, a busca comeza de novo. Isto non dura máis de tres minutos, despois dos cales a orde é cancelada e queimada.
Buscar nun Pin é semellante a buscar nun pedido, só que non se crea a orde e a propia busca realízase só unha vez. Tamén se utilizan axustes simplificados para o número de candidatos e o radio de busca. Tales simplificacións son necesarias porque hai unha orde de magnitude máis alfinetes que ordes, e buscar é unha operación bastante difícil. O punto clave da nosa historia: se durante a busca preliminar non se atoparon candidatos axeitados no Pin, non che permitimos facer un pedido. Polo menos así era antes.
Isto é o que o usuario viu na aplicación:
Busca coches sen coches
Un día demos unha hipótese: quizais nalgúns casos aínda se poida cumprir a orde, aínda que non houbese coches no alfinete. Despois de todo, pasa un tempo entre o PIN e a orde, e a busca da orde é máis completa e ás veces repítese varias veces: durante este tempo, poden aparecer controladores dispoñibles. Tamén sabiamos o contrario: se se atopaban condutores no alfinete, non era un feito que se atopasen ao pedir. Ás veces desaparecen ou todos rexeitan a orde.
Para probar esta hipótese, puxemos en marcha un experimento: deixamos de comprobar a presenza de coches durante unha busca nun Pin dun grupo de usuarios de proba, é dicir, que tiveron a oportunidade de facer un "pedido sen coches". O resultado foi bastante inesperado: se o coche non estaba no alfinete, entón no 29% dos casos atopouse máis tarde - ao buscar na orde! Ademais, os pedidos sen coches non foron significativamente diferentes dos pedidos habituais en termos de taxas de cancelación, valoracións e outros indicadores de calidade. As reservas sen coches representaron o 5% de todas as reservas, pero algo máis do 1% de todas as viaxes exitosas.
Para comprender de onde veñen os executores destas ordes, vexamos o seu estado durante unha busca nun Pin:
- Dispoñible: estaba dispoñible, pero por algún motivo non estaba incluído nos candidatos, por exemplo, estaba demasiado lonxe;
- En orde: estaba ocupado, pero conseguiu liberarse ou estar dispoñible para ;
- Ocupado: a capacidade de aceptar pedidos foi desactivada, pero entón o condutor volveu á liña;
- Non dispoñible: o condutor non estaba en liña, pero apareceu.
Engadimos fiabilidade
Os pedidos adicionais son xeniais, pero o 29% das buscas exitosas significa que o 71% das veces o usuario esperou moito tempo e acabou sen ir a ningunha parte. Aínda que isto non é algo malo desde o punto de vista da eficiencia do sistema, en realidade dálle ao usuario falsas esperanzas e perde o tempo, despois de que se moleste e (posiblemente) deixe de usar o servizo. Para resolver este problema, aprendemos a predicir a probabilidade de que se atope un coche en pedido.
O esquema é o seguinte:
- O usuario pon un alfinete.
- Realízase unha busca no pin.
- Se non hai coches, predecimos: quizais aparezan.
- E dependendo da probabilidade, permitimos ou non facer un pedido, pero advertimos que a densidade de coches nesta zona neste momento é baixa.
Na aplicación parecíase así:
Usar o modelo permíteche crear novos pedidos con máis precisión e non tranquilizar á xente en balde. É dicir, para regular a relación de fiabilidade e o número de pedidos sen máquinas mediante o modelo de precisión-recall. A fiabilidade do servizo inflúe no desexo de seguir usando o produto, é dicir, ao final todo se reduce ao número de viaxes.
Un pouco sobre recordo de precisiónUnha das tarefas básicas na aprendizaxe automática é a tarefa de clasificación: asignar un obxecto a unha das dúas clases. Neste caso, o resultado do algoritmo de aprendizaxe automática convértese a miúdo nunha avaliación numérica da pertenza a unha das clases, por exemplo, nunha avaliación de probabilidades. Non obstante, as accións que se realizan adoitan ser binarias: se o coche está dispoñible, permitirémosche encargalo e, se non, non o faremos. Para ser específicos, chamemos un modelo a un algoritmo que produce unha estimación numérica e a un clasificador unha regra que o atribúe a unha das dúas clases (1 ou –1). Para facer un clasificador baseado na avaliación do modelo, cómpre seleccionar un limiar de avaliación. Como exactamente depende moito da tarefa.
Supoñamos que estamos a facer unha proba (clasificador) para algunha enfermidade rara e perigosa. En función dos resultados das probas, enviamos ao paciente a un exame máis detallado ou dicimos: "Ben, volve a casa". Para nós, enviar a unha persoa enferma a casa é moito peor que examinar innecesariamente a unha persoa sa. É dicir, queremos que a proba funcione para o maior número posible de persoas realmente enfermas. Este valor chámase recall =. Un clasificador ideal ten unha lembranza do 100%. Unha situación dexenerada é enviar a todos para o exame, entón o recordo tamén será do 100%.
Tamén ocorre ao revés. Por exemplo, estamos a facer un sistema de probas para estudantes e ten un detector de trampas. Se de súpeto a comprobación non funciona para algúns casos de trampas, entón isto é desagradable, pero non crítico. Por outra banda, é moi malo acusar inxustamente aos estudantes de algo que non fixeron. É dicir, é importante para nós que entre as respostas positivas do clasificador haxa o maior número posible de correctas, quizais en detrimento do seu número. Isto significa que cómpre maximizar a precisión = . Se o disparo ocorre en todos os obxectos, entón a precisión será igual á frecuencia da clase definida na mostra.
Se o algoritmo produce un valor de probabilidade numérico, entón seleccionando diferentes limiares, pode acadar diferentes valores de precisión de lembranza.
No noso problema a situación é a seguinte. Recordar é o número de pedidos que podemos ofrecer, a precisión é a fiabilidade destes pedidos. Este é o aspecto da curva de precisión-recordo do noso modelo:
Hai dous casos extremos: non permitir que ninguén ordene e permitir que todos pidan. Se non permites a ninguén, a lembranza será 0: non creamos pedidos, pero ningún deles fallará. Se permitimos a todos, a retirada será do 100 % (recibiremos todos os pedidos posibles) e a precisión será do 29 %, é dicir, o 71 % dos pedidos será malo.
Usamos varios parámetros do punto de partida como sinais:
- Tempo/lugar.
- Estado do sistema (número de máquinas ocupadas de todas as tarifas e pinos nas proximidades).
- Parámetros de busca (raio, número de candidatos, restricións).
Máis información sobre os sinais
Conceptualmente, queremos distinguir entre dúas situacións:
- "Bosque profundo": non hai coches aquí neste momento.
- "Desafortunado": hai coches, pero ao buscar non había ningún axeitado.
Un exemplo de "Desafortunado" é se o venres á noite hai moita demanda no centro. Hai moitos pedidos, moita xente disposta e non hai suficientes condutores para todos. Pode resultar así: non hai controladores axeitados no pin. Pero literalmente en segundos aparecen, porque neste momento hai moitos condutores neste lugar e o seu estado cambia constantemente.
Polo tanto, varios indicadores do sistema nas proximidades do punto A resultaron ser boas características:
- Número total de coches.
- Número de coches encomendados.
- O número de coches que non se poden pedir no estado "Ocupado".
- Número de usuarios.
Despois de todo, cantos máis coches haxa, máis probable é que un deles estea dispoñible.
De feito, é importante para nós que non só se localicen os coches, senón que tamén se fagan viaxes exitosas. Polo tanto, foi posible prever a probabilidade dunha viaxe exitosa. Pero decidimos non facelo, porque este valor depende moito do usuario e do condutor.
O algoritmo de adestramento do modelo foi . Os datos obtidos do experimento utilizáronse para o adestramento. Despois da implementación, houbo que recoller datos de formación, permitindo ás veces que un pequeno número de usuarios ordenase contra a decisión do modelo.
Resultados de
Os resultados do experimento foron os esperados: o uso do modelo permítelle aumentar significativamente o número de viaxes exitosas debido a pedidos sen coches, pero sen comprometer a fiabilidade.
Polo momento, o mecanismo púxose en marcha en todas as cidades e países e coa súa axuda prodúcense preto do 1% das viaxes exitosas. Ademais, nalgunhas cidades con pouca densidade de coches, a participación deste tipo de viaxes alcanza o 15%.
Outras publicacións sobre tecnoloxía do taxi
Fonte: www.habr.com