Um bom serviço de táxi deve ser seguro, confiável e rápido. O usuário não entrará em detalhes: é importante para ele que clique no botão “Encomendar” e receba o mais rápido possível um carro que o levará do ponto A ao ponto B. Se não houver carros por perto, o serviço deverá informar imediatamente sobre isso para que o cliente não tenha falsas expectativas. Mas se o sinal “Proibido carros” aparecer com muita frequência, é lógico que uma pessoa simplesmente pare de usar este serviço e procure um concorrente.
Neste artigo quero falar sobre como, por meio do aprendizado de máquina, resolvemos o problema de busca de carros em áreas de baixa densidade (ou seja, onde, à primeira vista, não há carros). E o que resultou disso.
Pré-história
Para chamar um táxi, o usuário realiza alguns passos simples, mas o que acontece dentro do serviço?
| Usuário | Etapa | Back-end Yandex.Taxi |
|---|---|---|
| Seleciona o ponto de partida | Pin | Estamos lançando uma busca simplificada de candidatos - busca por pin. Com base nos drivers encontrados, o horário de chegada é previsto - ETA no alfinete. O coeficiente crescente em um determinado ponto é calculado. |
| Seleciona destino, tarifa, requisitos | Oferecer | Construímos uma rota e calculamos os preços de todas as tarifas, tendo em conta o coeficiente crescente. |
| Aperta o botão “Chamar um táxi” | Заказ | Lançamos uma busca completa pelo carro. Selecionamos o driver mais adequado e oferecemos-lhe um pedido. |
Про , и nós já escrevemos. E esta é uma história sobre como encontrar motoristas. Quando um pedido é criado, a busca ocorre duas vezes: no Pin e no pedido. A busca por um pedido ocorre em duas etapas: recrutamento de candidatos e classificação. Primeiro, são encontrados os candidatos a motoristas disponíveis que estão mais próximos ao longo do gráfico da estrada. Em seguida, os bônus e a filtragem são aplicados. Os demais candidatos são classificados e o vencedor recebe uma oferta de pedido. Se ele concordar, ele é designado para o pedido e segue para o ponto de entrega. Se ele recusar, a oferta vai para o próximo. Se não houver mais candidatos, a busca será reiniciada. Isso não dura mais do que três minutos, após os quais o pedido é cancelado e queimado.
Pesquisar em um Pin é semelhante a pesquisar em um pedido, só que o pedido não é criado e a pesquisa em si é realizada apenas uma vez. Também são utilizadas configurações simplificadas para número de candidatos e raio de pesquisa. Tais simplificações são necessárias porque há uma ordem de grandeza de mais pinos do que ordens, e a busca é uma operação bastante difícil. O ponto-chave da nossa história: se durante a pesquisa preliminar não foram encontrados candidatos adequados no Pin, então não permitimos que você faça um pedido. Pelo menos era assim que costumava ser.
Isto é o que o usuário viu no aplicativo:
Procure carros sem carros
Um dia levantamos uma hipótese: talvez em alguns casos o pedido ainda possa ser concluído, mesmo que não houvesse carros no alfinete. Afinal, passa algum tempo entre o pin e o pedido, e a busca pelo pedido é mais completa e às vezes repetida várias vezes: durante esse tempo podem aparecer drivers disponíveis. Também sabíamos o contrário: se fossem encontrados drivers no alfinete, não era fato que seriam encontrados no momento do pedido. Às vezes eles desaparecem ou todos recusam o pedido.
Para testar essa hipótese, lançamos um experimento: paramos de verificar a presença de carros durante uma busca em um Pin para um grupo de usuários de teste, ou seja, eles tiveram a oportunidade de fazer um “pedido sem carro”. O resultado foi bastante inesperado: se o carro não estava no pino, em 29% dos casos ele foi encontrado mais tarde - ao pesquisar no pedido! Além disso, os pedidos sem carros não diferiram significativamente dos pedidos normais em termos de taxas de cancelamento, classificações e outros indicadores de qualidade. As reservas sem carro representaram 5% de todas as reservas, mas pouco mais de 1% de todas as viagens bem-sucedidas.
Para entender de onde vêm os executores dessas ordens, vamos dar uma olhada em seus status durante uma pesquisa em um Pin:
- Disponível: estava disponível, mas por algum motivo não foi incluído nos candidatos, por exemplo, estava muito longe;
- Em ordem: estava ocupado, mas conseguiu se libertar ou ficar disponível para ;
- Ocupado: a capacidade de aceitar pedidos foi desativada, mas o motorista voltou à fila;
- Não disponível: o motorista não estava online, mas apareceu.
Vamos adicionar confiabilidade
Pedidos adicionais são ótimos, mas 29% das pesquisas bem-sucedidas significam que 71% das vezes o usuário esperou muito tempo e acabou não indo a lugar nenhum. Embora isso não seja ruim do ponto de vista da eficiência do sistema, na verdade dá ao usuário falsas esperanças e desperdiça tempo, após o qual ele fica chateado e (possivelmente) para de usar o serviço. Para resolver esse problema, aprendemos a prever a probabilidade de encontrar um carro encomendado.
O esquema é o seguinte:
- O usuário coloca um alfinete.
- Uma pesquisa é realizada no alfinete.
- Se não houver carros, prevemos: talvez apareçam.
- E dependendo da probabilidade, permitimos ou não que você faça um pedido, mas avisamos que a densidade de carros nesta área neste momento é baixa.
No aplicativo ficou assim:
Usar o modelo permite criar novos pedidos com mais precisão e não tranquilizar as pessoas em vão. Ou seja, regular a relação de confiabilidade e o número de pedidos sem máquinas utilizando o modelo de recall de precisão. A confiabilidade do serviço influencia na vontade de continuar utilizando o produto, ou seja, no final tudo se resume ao número de viagens.
Um pouco sobre recall de precisãoUma das tarefas básicas do aprendizado de máquina é a tarefa de classificação: atribuir um objeto a uma de duas classes. Nesse caso, o resultado do algoritmo de aprendizado de máquina geralmente se torna uma avaliação numérica da participação em uma das classes, por exemplo, uma avaliação de probabilidade. No entanto, as ações executadas são geralmente binárias: se o carro estiver disponível, permitiremos que você o encomende e, se não, não o faremos. Para ser mais específico, vamos chamar um algoritmo que produz uma estimativa numérica de modelo, e um classificador de regra que o atribui a uma de duas classes (1 ou –1). Para criar um classificador baseado na avaliação do modelo, você precisa selecionar um limite de avaliação. Como exatamente depende muito da tarefa.
Suponha que estejamos fazendo um teste (classificador) para alguma doença rara e perigosa. Com base no resultado do exame, ou encaminhamos o paciente para um exame mais detalhado ou dizemos: “Bom, vá para casa”. Para nós, mandar uma pessoa doente para casa é muito pior do que examinar desnecessariamente uma pessoa saudável. Ou seja, queremos que o teste funcione para o maior número possível de pessoas realmente doentes. Este valor é chamado de recall =. Um classificador ideal tem um recall de 100%. Uma situação degenerada é mandar todo mundo para exame, aí o recall também será de 100%.
Também acontece o contrário. Por exemplo, estamos fazendo um sistema de testes para estudantes e ele possui um detector de trapaça. Se de repente a verificação não funcionar em alguns casos de trapaça, isso será desagradável, mas não crítico. Por outro lado, é extremamente ruim acusar injustamente os alunos de algo que eles não fizeram. Ou seja, é importante para nós que entre as respostas positivas do classificador existam tantas respostas corretas quanto possível, talvez em detrimento do seu número. Isso significa que você precisa maximizar a precisão = . Se o disparo ocorrer em todos os objetos, a precisão será igual à frequência da classe definida na amostra.
Se o algoritmo produzir um valor de probabilidade numérica, ao selecionar diferentes limites, você poderá obter diferentes valores de recuperação de precisão.
No nosso problema a situação é a seguinte. Recall é o número de pedidos que podemos oferecer, precisão é a confiabilidade desses pedidos. Esta é a aparência da curva de recuperação de precisão do nosso modelo:
Existem dois casos extremos: não permitir que ninguém faça pedidos e permitir que todos façam pedidos. Se você não permitir ninguém, o recall será 0: não criamos pedidos, mas nenhum deles falhará. Se permitirmos a todos, o recall será de 100% (receberemos todos os pedidos possíveis) e a precisão será de 29%, ou seja, 71% dos pedidos serão ruins.
Usamos vários parâmetros do ponto de partida como sinais:
- Hora/lugar.
- Estado do sistema (número de máquinas ocupadas de todas as tarifas e pinos nas proximidades).
- Parâmetros de pesquisa (raio, número de candidatos, restrições).
Mais sobre os sinais
Conceitualmente, queremos distinguir entre duas situações:
- “Floresta profunda” - não há carros aqui neste momento.
- “Azar” - existem carros, mas na busca não havia nenhum adequado.
Um exemplo de “azar” é se houver muita procura no centro na noite de sexta-feira. Há muitos pedidos, muita gente disposta e poucos motoristas para todos. Pode acontecer assim: não há drivers adequados no pino. Mas eles aparecem literalmente em segundos, porque neste momento há muitos motoristas neste local e seu status está mudando constantemente.
Portanto, vários indicadores do sistema nas proximidades do ponto A revelaram-se boas características:
- Número total de carros.
- Número de carros encomendados.
- O número de carros indisponíveis para encomenda no status “Ocupado”.
- Número de usuários.
Afinal, quanto mais carros houver, maior será a probabilidade de um deles ficar disponível.
Na verdade, é importante para nós que não apenas os carros sejam localizados, mas também que sejam feitas viagens bem-sucedidas. Portanto, foi possível prever a probabilidade de uma viagem bem-sucedida. Mas decidimos não fazer isso, pois esse valor depende muito do usuário e do motorista.
O algoritmo de treinamento do modelo foi . Os dados obtidos no experimento foram utilizados para treinamento. Após a implementação, os dados de treinamento tiveram que ser coletados, às vezes permitindo que um pequeno número de usuários fizessem pedidos contra a decisão do modelo.
Resultados de
Os resultados do experimento foram os esperados: a utilização do modelo permite aumentar significativamente o número de viagens bem-sucedidas devido a pedidos sem carros, mas sem comprometer a confiabilidade.
Neste momento, o mecanismo foi lançado em todas as cidades e países e com a sua ajuda ocorrem cerca de 1% das viagens bem-sucedidas. Além disso, em algumas cidades com baixa densidade de automóveis, a participação dessas viagens chega a 15%.
Outros posts sobre tecnologia de táxi
Fonte: habr.com