Estimativa de tempo de entrega (ETA)

01 · CONTEXTO E REQUISITOS

Por que o ETA importa

Um ETA é a previsão do tempo de chegada. Segundo o blog de engenharia da Uber, ele é usado para calcular tarifas, estimar horários de embarque, casar passageiros com motoristas e planejar entregas, entre outras decisões. Montar essa previsão é um problema clássico de projeto de sistemas de ML.

Para justificar a troca do modelo anterior por aprendizado profundo, a equipe precisou superar três desafios principais. Latência: o modelo deve devolver um ETA em no máximo alguns milissegundos. Acurácia: o erro absoluto médio (MAE) precisa melhorar de forma significativa sobre o modelo XGBoost incumbente. Generalidade: as previsões devem valer globalmente para todas as linhas de negócio, como mobilidade e entrega.

Por vários anos a Uber refinou ETAs com ensembles de árvores de decisão com gradient boosting. Chegou-se a um ponto em que aumentar o dataset e o modelo com XGBoost se tornou inviável, e a equipe decidiu explorar aprendizado profundo pela facilidade relativa de escalar para grandes datasets com SGD paralelo em dados.

02 · ABORDAGEM HÍBRIDA

Rota física mais correção aprendida

Motores de rota tradicionais dividem a malha viária em pequenos segmentos, representados por arestas ponderadas de um grafo. Eles usam algoritmos de caminho mínimo para achar o melhor trajeto e somam os pesos para obter o ETA.

O limite dessa abordagem é que o grafo viário é só um modelo e não captura perfeitamente as condições reais na pista: o mapa não é o terreno.

A solução descrita é híbrida. O modelo físico é o motor de roteamento, que usa dados de mapa e medições de trânsito em tempo real e prevê o ETA como a soma dos tempos de travessia por segmento ao longo do melhor caminho. Sobre ele, o aprendizado de máquina prevê o resíduo entre o ETA do roteador e os resultados observados no mundo real.

A razão prática para essa divisão é que costuma ser mais fácil incorporar novas fontes de dados e acompanhar requisitos de negócio que mudam rápido atualizando o modelo de pós-processamento do que refatorando o próprio motor de roteamento.

03 · FEATURES

Como as features entram no modelo

O modelo de pós-processamento considera features espaciais e temporais, como origem, destino e hora do pedido, além de informação de trânsito em tempo real e da natureza do pedido, por exemplo entrega ou embarque. Esse é o modelo com maior QPS (consultas por segundo) da Uber.

O DeepETA gera embeddings de todas as features categóricas e discretiza as contínuas antes de gerar o embedding. Contra a intuição, discretizar as features contínuas deu mais acurácia do que usá-las diretamente, e buckets por quantil superaram buckets de largura igual.

Origem e destino chegam como latitude e longitude, e a equipe quantiza essas localizações em grades de várias resoluções. Foram exploradas três estratégias para mapear as grades em embeddings.

04 · LATÊNCIA

Como deixar o modelo rápido

O encoder baseado em transformer deu a melhor acurácia, mas foi lento demais para os requisitos de latência do serving online em tempo real. A autoatenção original tem complexidade quadrática, e a equipe escolheu o linear transformer, que usa o truque do kernel para não calcular a matriz de atenção.

Outro ganho vem da esparsidade. O modelo é relativamente raso, com poucas camadas, e a grande maioria dos parâmetros está em tabelas de embeddings. Embora tenha centenas de milhões de parâmetros, cada predição toca só uma fração minúscula deles, cerca de 0,25%.

Discretizar as entradas também acelera o serving: mapear latitude e longitude para um embedding é quantizar as coordenadas e fazer uma consulta hash, em tempo constante. É a clássica troca entre espaço e tempo, pois tabelas de embeddings grandes aprendidas no treino reduzem a computação necessária na hora de servir.

05 · GENERALIDADE E PERDA

Um modelo para todas as linhas de negócio

A distribuição dos erros absolutos varia muito entre entregas e corridas, viagens longas e curtas, embarque e desembarque e megarregiões globais. Por isso o decodificador inclui camadas de ajuste de viés por segmento, que corrigem a predição bruta e melhoram o MAE. A equipe preferiu essa camada a um decodificador multitarefa por restrições de latência.

Casos de uso diferentes pedem estimativas pontuais diferentes: para calcular tarifa quer-se um ETA médio, controlando o efeito de outliers, e outros casos pedem um quantil específico da distribuição do ETA. Para acomodar essa diversidade, o DeepETA usa uma função de perda parametrizada, a perda de Huber assimétrica, robusta a outliers.

06 · SERVING E RETREINO

Do pedido à predição

Uma vez treinado e implantado no Michelangelo, o modelo precisa servir predições para ETAs em tempo real. O primeiro diagrama mostra o caminho de uma consulta online; o segundo, o ciclo de retreino.

1. Os pedidos dos consumidores passam por vários serviços até chegar ao uRoute.

2. O uRoute é o frontend de todas as consultas de roteamento.

3. O uRoute pede ao motor de roteamento as linhas de rota e os ETAs.

4. Com esse ETA e outras features do modelo, o uRoute consulta o serviço de predição online do Michelangelo.

5. O serviço de predição fornece as predições do modelo DeepETA, que estima o resíduo entre o ETA do roteador e os resultados observados.

1. Workflows periódicos de retreino automático treinam e validam o modelo.

2. O modelo é treinado e implantado no Michelangelo.

3. Com o modelo implantado, as predições passam a ser servidas aos usuários para ETA em tempo real.

Como próximo passo, a equipe cita explorar treino contínuo e incremental, que permitiria treinar os ETAs com dados mais frescos.

07 · TRADE-OFFS

Decisões e custos em resumo