
Olá! Meu nome é Mikhail Dyachkov, e na Citymobil eu faço aprendizado de máquina. Hoje vou falar sobre nosso novo algoritmo para gerar sugestões de busca para destinos finais. Você aprenderá como uma tarefa aparentemente simples se transformou em um cenário interessante, com a ajuda do qual, esperamos, conseguimos facilitar um pouco a vida dos usuários. Continuamos monitorando de perto o trabalho do novo algoritmo e, subsequentemente, iremos ajustá-lo para manter a qualidade da classificação em um alto nível. Para todos os usuários, lançaremos o algoritmo nas próximas semanas, mas já estamos prontos para falar sobre a longa jornada que percorremos da heurística ao algoritmo de aprendizado de máquina e colocá-lo em operação.
Acho que vale a pena começar descrevendo a visão de mundo ideal de um cenário de pedido de táxi de uma perspectiva de interface do usuário. Gostaria que nosso aplicativo entendesse onde / onde / quando / em que carro o usuário deseja sair. Neste artigo, veremos nossa solução para responder à pergunta "onde".
Um dos elementos centrais da primeira tela (aquele que o usuário vê após o login) são as sugestões de pesquisa. Na equipe de pesquisa geográfica, nós os chamamos de "sajests" (da sugestão em inglês) Eles oferecem ao usuário os endereços finais da rota (pontos “B”) de seu histórico de viagens com base na localização atual do pino (ou seja, o ponto de entrega) e a hora do dia, sem inserir uma consulta de pesquisa. Tentamos ajudar o usuário a fazer um pedido "em um clique" com a ajuda de sagests. Na versão atual do aplicativo cliente iOS, os sajests se parecem com isto:

Geo-search devido a algoritmos para gerar resultados de pesquisa pode afetar uma das métricas de produto mais importantes para o aplicativo cliente, como o tempo gasto para pedir um táxi ( tempo para pedir ou T2O ), bem como o número de ações que o cliente realizou para formar um pedido ( Ações para solicitar ou A2O) Portanto, decidimos desenvolver um algoritmo que irá prever os pontos finais mais prováveis da rota (pontos "B") para um determinado local e hora do dia.
Heurística
Um dos desenvolvedores de back-end da equipe de geo-search (Vasilesk, olá!) surgiu com uma heurística bastante simples para gerar sajests que funcionou para o ponto inicial "A" e o ponto final "B". É importante destacar que a heurística não funcionou no histórico de viagens do usuário, mas sim no histórico de cliques nos resultados da pesquisa, o que acarretou alguns problemas. A esses objetos chamamos de "picos" (do inglês. A picareta ). A heurística era assim:
- Para o usuário atual, consideramos todos os seus picos históricos.
- Nós os filtramos, deixando aqueles com o mesmo destino (de / onde).
- , , 300 ( «» — 300 «», «» — 300 «»). , GPS- .
- , , , , , .
- , , 3:00 14:00, , .
- - (), , - .
- .
Esse algoritmo funcionou por um tempo e geralmente era bom para MVPs (falaremos sobre métricas um pouco mais tarde), mas tinha uma série de desvantagens. Além da lógica de trabalho bastante primitiva, não se baseava em viagens, mas em escolhas do usuário. Por causa disso, às vezes os usuários obtêm resultados de pesquisa não óbvios. E também, devido à maneira "específica" de armazenar o histórico dos picos, era bastante difícil realizar análises rápidas. Com base nisso, decidimos tentar aplicar o aprendizado de máquina. A seguir, consideraremos a formulação de problemas de classificação e reduziremos nosso problema a uma classificação binária.
Classificação do problema
Antes de falar sobre recursos, métricas e um modelo, precisamos descobrir que tipo de problema estamos tentando resolver. Vamos iterativamente e primeiro tentar formular uma formulação geral do problema de classificação. Se parece com isso:
é um conjunto de objetos.
- amostra de treinamento.
é a ordem correta dos pares
Tarefa: construir uma função de classificação, com qual
Agora vamos formular a tarefa de classificar os resultados da pesquisa por consulta. É diferente do problema de classificação geral porque, em vez do conjunto geral de objetos que precisamos classificar, dois conjuntos aparecem e - muitos documentos e consultas.
- coleção de documentos (respostas).
- muitos pedidos.
- o conjunto de documentos encontrados pela consulta q.
- os objetos são pares "pedido, documento":
- um conjunto ordenado de classificações (classificações).
- pontuações de relevância.
Quanto maior a pontuação, mais relevante o documento solicitação ...
A ordem correta é definida apenas entre os documentos encontrados pela mesma consulta:
Em nossa tarefa de recomendar pontos finais de rota, o conjunto de classificações é binário. Para o usuário, o endereço sugerido pode ser relevante ou irrelevante (excluindo casos com uma rota complexa com vários terminais). Se considerarmos a tarefa no contexto do usuário, então- um pedido ao serviço, que contém o id do cliente, geo-posição, data e hora;- muitos endpoints históricos "B" para as viagens do usuário (apenas fazemos sugestões com base nos endereços de viagens anteriores). E toda resposta válida a pedido pode ser relevante para o usuário (do ponto atual e no momento atual, o usuário precisa ir exatamente aqui) ou irrelevante.
Para fins de integridade, resta apenas descrever o processo de criação de uma amostra de pares de solicitação-resposta com um destino. Considere, para simplificar, um cliente que fez 5 viagens. Vamos classificar essas viagens do primeiro ao último. Para a primeira viagem, não sabemos nada sobre as viagens do usuário, por isso não podemos oferecer a ele um sagest usando o algoritmo de aprendizado de máquina descrito (a heurística para novos usuários funciona aqui). Para a segunda viagem, sabemos o destino final da primeira viagem e podemos oferecer este endereço ao usuário se ele passar com sucesso no procedimento de pós-processamento (localizado a mais de 1 km do local atual, na mesma região, etc.). Para a terceira viagem, podemos já ter de um a dois tristes possíveis,se o endereço final da segunda viagem for o mesmo que o endereço final da primeira e se os endereços finais forem diferentes, respectivamente. Se o sajest coincidiu com o ponto final "B" (isto é, ele caiu no mesmo hex de tamanho fixo), então definimos 1 como o alvo, caso contrário - 0. De acordo com este algoritmo, formamos todos os tipos de pares da forma "solicitação - (possível) resposta "Para cada cliente.
Portanto, reduzimos o problema de classificação a um problema de classificação binária. Agora podemos falar sobre métricas de avaliação de qualidade.
Métricas
Em problemas de classificação, uma métrica que mostra a proporção de respostas corretas de documentos para o topo lista de classificação quando solicitado são chamados de Precision @ n . Estamos interessados na Precision @ 1/2/3 , uma vez que a taxa de cliques total para as três primeiras posições é de cerca de 95%. Nesse caso, há apenas um endereço final correto (naturalmente, se o usuário quiser deixar o endereço de seu histórico), portanto, essa métrica mostrará apenas a proporção de casos em que o ponto final "B" correto chega aos 1/2/3 endereços superiores que sugeriu nosso algoritmo.
Lembre-se disso em nosso problema - relevância, É a função de classificação necessária. Então, Precision @ n pode ser escrito como:
Sinais e modelo
Os recursos do modelo em nosso problema podem ser divididos em vários blocos:
- Apenas para documento (endereço final, ponto “B”).
- Somente para solicitação (endereço inicial, ponto "A").
- Comum para solicitar e documentar (rota de "A" para "B").
- Geral para o usuário.
Aqui estão alguns exemplos para cada um deles.
Exemplos de sinais apenas para o documento (ponto "B"):
- Número de viagens para o ponto "B" nos últimos K dias.
- Número de viagens para o ponto "B" por dia da semana e hora do dia.
- Quando foi a viagem anterior ao ponto “B”.
- Sinalizar que a viagem anterior foi feita para o ponto "B".
- O ponto “B” é um endereço / casa / trabalho escolhido.
Exemplos de características apenas para solicitação ( «» + /):
- , .
- «».
- «» K .
- «» .
- «» //.
- / .
- «».
, ( «» “”):
- , .
- .
- .
:
- K .
- .
- Estatísticas históricas de viagem (média, quantis, distância média de viagem, etc.).
Como resultado, obtivemos mais de 100 recursos que descrevem um par de objetos "pedido-documento". Visto que queremos maximizar a Precisão @ 1/2/3 , é lógico que precisemos prever a probabilidade de uma viagem do usuário a um destino específico e classificar os possíveis candidatos de acordo com a probabilidade obtida. Tentamos diferentes algoritmos e diferentes funções de perda e decidimos pelo aumento de gradiente em árvores e perda de log . Os resultados que foram obtidos no momento de usar a heurística:
Heurística | Algoritmo ML | |
---|---|---|
Precisão @ 1 | 0,657 | 0,789 |
Precisão @ 2 | 0,719 | 0,872 |
Precisão @ 3 | 0,761 | 0,923 |
Produção
Naturalmente, antes de criar alguns algoritmos, recursos e modelos de treinamento complexos, você precisa pensar em como tudo isso funcionará em combate sob carga, sem se esquecer da escala. Reunidos com a equipe de desenvolvimento de back-end, esboçamos um esboço de como nosso serviço deveria ser. Decidimos envolver o modelo de aprendizado de máquina treinado no framework web async- await Sanic, para o qual o serviço de pesquisa enviará solicitações. Além do dimensionamento vertical, implementamos a capacidade de implantação em várias máquinas. As solicitações para o serviço serão enviadas para a URL do balanceador de carga e, em seguida, ocorrerá o proxy para esta ou aquela máquina usando o algoritmo Round-robin. Após implementar o primeiro protótipo do serviço, percebemos que poderíamos reduzir significativamente o volume de consultas no MySQL. Como qualquer deslocamento do pino com a escolha do ponto de feed é uma nova solicitação de busca e, portanto, para nosso serviço, pensamos que poderíamos armazenar um cache com o histórico de viagens do usuário por N minutos a partir do momento da solicitação ao Redis. Graças a isso, reduzimos a carga na base em três vezes. Como resultado, o esquema de serviço pode ser representado da seguinte forma:

Armazenamos as solicitações do serviço e suas respostas no ElasticSearch, e transferimos e monitoramos as métricas responsáveis pela estabilidade do trabalho no NewRelic.
O fluxo de trabalho geral do nosso serviço:
- O serviço de pesquisa envia uma solicitação ao serviço de dicas de pesquisa.
- O balanceador seleciona uma das máquinas e envia esta solicitação para ela.
- Dentro da máquina, a solicitação é enviada a um dos workers abertos ou entra na fila.
- Dentro do trabalhador:
- Nós validamos a solicitação recebida.
- Fazemos uma solicitação no Redis, se não houver histórico de pedidos para o usuário, vamos ao MySQL e gravamos os dados recebidos no Redis.
- Fazemos pré-processamento de dados básicos e coletamos recursos para o modelo.
- Fazemos isso de
predict_proba()
acordo com todos os sajests gerados e os classificamos por "probabilidade". - Fazemos pós-processamento adicional dos dados e formamos a resposta.
- Devolvemos a resposta ao serviço de pesquisa.
Qual é o próximo?
Agora estamos testando ativamente nosso modelo usando o teste de switchback para posteriormente tirar conclusões e implementar add-ons adicionais ao algoritmo para melhorar a qualidade da classificação. No futuro, tentaremos agregar recursos adicionais ao modelo, bem como, junto com os designers de produtos, preparar uma nova solução para a “exibição” de flechas. Claro, seria ótimo se nosso próprio aplicativo entendesse onde / quando / onde / por qual carro o usuário quer sair. Trabalhamos em todas as direções para que um pedido de táxi seja realmente feito com um clique.