Uber DeepETA

01 · CONTEXTO E DESAFIOS

Por que o Uber trocou árvores por deep learning

No Uber, a estimativa de tempo de chegada (ETA) alimenta decisões centrais. O blog cita o cálculo de tarifas, a estimativa de tempo de coleta, o casamento entre passageiros e motoristas e o planejamento de entregas.

Um motor de rotas tradicional divide a malha viária em segmentos representados por arestas ponderadas, aplica algoritmos de caminho mínimo e soma os pesos para chegar ao ETA. Os autores lembram que o mapa não é o território: o grafo viário é só um modelo.

Durante vários anos, o Uber usou ensembles de árvores de decisão com gradient boosting para refinar essas previsões. O modelo e o conjunto de treino cresceram a cada versão, até que, nas palavras dos autores, aumentar dados e modelo com XGBoost tornou-se insustentável. A alternativa explorada foi o deep learning, pela facilidade relativa de escalar em conjuntos grandes com SGD paralelo em dados.

Para justificar a troca, o time precisava vencer três desafios. Latência: o modelo deve devolver o ETA em poucos milissegundos, no máximo. Acurácia: o erro absoluto médio (MAE) precisa melhorar bastante sobre o XGBoost incumbente. Generalidade: previsões globais para todas as linhas de negócio, como mobilidade e entregas.

02 · FÍSICA MAIS APRENDIZADO

O modelo corrige o motor de rotas

A ideia central é híbrida. O modelo físico é o motor de rotas, que usa dados de mapa e medições de trânsito em tempo real para prever 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 motor e o resultado real observado. O blog chama essa abordagem de pós-processamento de ETA, e o DeepETA é um exemplo.

Na prática, é 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 motor de rotas. O modelo recebe características espaciais e temporais, como origem, destino e hora do pedido, além de informação de tráfego em tempo real e da natureza do pedido.

Esse modelo é o de maior QPS do Uber e precisa ser rápido para não somar latência ao pedido de ETA.

1. Os pedidos dos consumidores chegam ao uRoute por vários serviços intermediários.

2. O uRoute consulta o motor de rotas, que produz rotas e o ETA base.

3. Com esse ETA e outras features, o uRoute chama a predição online do Michelangelo, onde roda o DeepETA.

Repare que o motor de rotas continua no caminho: o modelo de aprendizado prevê o resíduo sobre o ETA dele, e o uRoute usa esse ETA como entrada da chamada de predição.

03 · COMO FICOU PRECISO

Self-attention sobre features e embeddings

O time testou e ajustou sete arquiteturas de rede neural: MLP, NODE, TabNet, mixture-of-experts com portas esparsas, HyperNetworks, Transformer e Linear Transformer. A que deu a melhor acurácia foi um encoder-decoder com self-attention. Os autores também relatam que discretizar e embutir todas as entradas deu um ganho significativo sobre as alternativas.

Em um modelo de linguagem, cada vetor é uma palavra. No DeepETA, cada vetor é uma feature, como a origem da viagem ou a hora do dia. A self-attention calcula as interações par a par entre as K features por meio de uma matriz de atenção K*K de produtos escalares. Não há codificação posicional, porque a ordem das features não importa.

Todas as features categóricas viram embeddings, e as contínuas são discretizadas em buckets antes de virar embeddings. De forma contraintuitiva, discretizar deu mais acurácia do que usar o valor contínuo diretamente, e buckets por quantis superaram buckets de mesma largura.

Origem e destino chegam como latitude e longitude e recebem tratamento especial: os locais são quantizados em grades de várias resoluções. Os autores exploraram três estratégias para mapear as células da grade em embeddings.

Segundo os autores, a perda de acurácia do hashing simples provavelmente vem de colisões de hash que perdem informação. O resultado do hashing múltiplo sugere que a rede consegue combinar a informação de vários buckets independentes para desfazer o efeito das colisões de um único bucket.

04 · COMO FICOU RÁPIDO

Linear transformer e muitos embeddings

O encoder com transformer deu a melhor acurácia, mas era lento demais para servir online em tempo real. A self-attention original tem complexidade quadrática. Há pesquisas que linearizam esse cálculo, e depois de experimentar o time escolheu o linear transformer, que usa o truque do kernel para evitar calcular a matriz de atenção.

No exemplo do blog, com K igual a 40 features de dimensão d igual a 8, o resultado é o da tabela, e o linear transformer é mais rápido sempre que K é maior que d.

Outro fator de velocidade é a esparsidade. O modelo tem centenas de milhões de parâmetros, mas cada previsão toca só uma fração minúscula deles, cerca de 0,25%. O modelo é relativamente raso, com poucas camadas, e a maior parte dos parâmetros está em tabelas de embeddings. Ao discretizar as entradas, o sistema evita avaliar os parâmetros de embedding que não são usados.

Para mapear latitude e longitude a um embedding, o DeepETA quantiza as coordenadas e faz uma busca por hash em tempo O(1). Os autores comparam com árvores, que exigiriam O(log N), e com camadas totalmente conectadas, que exigiriam O(N²). É a velha troca entre espaço e tempo: ao pré-computar respostas parciais em grandes tabelas de embeddings aprendidas no treino, reduz-se a computação no momento do servimento.

05 · COMO FICOU GERAL

Ajuste de viés por segmento e perda Huber assimétrica

Depois de aprender as representações, o decoder é uma rede totalmente conectada com uma camada de ajuste de viés por segmento. A distribuição do erro absoluto varia muito entre entregas e corridas, viagens longas e curtas, coleta e entrega no destino e entre mega-regiões globais. Ajustar a previsão bruta por segmento absorve essa variação e melhora o MAE, e funciona melhor do que apenas adicionar features de segmento.

Os autores escolheram a camada de viés em vez de um decoder multitarefa por restrições de latência. Também usam ReLU na saída para forçar o ETA previsto a ser positivo e clamping para reduzir o efeito de valores extremos.

Casos de uso diferentes pedem estimativas pontuais diferentes. Para calcular tarifa, o time quer um ETA médio, mas precisa controlar o efeito de outliers. Outros casos pedem um quantil específico da distribuição. Por isso o DeepETA usa uma função de perda parametrizada, a Huber assimétrica, robusta a outliers e capaz de produzir várias estimativas pontuais comuns.

Dois parâmetros controlam o comportamento. O delta interpola suavemente entre erro quadrático e erro absoluto, este menos sensível a outliers. O omega controla o custo relativo de subestimar contra superestimar, útil quando chegar um minuto atrasado é pior do que chegar um minuto adiantado.

06 · TREINO, SERVING E EVOLUÇÃO

Do Michelangelo ao uRoute

O time usou o framework Canvas da plataforma de ML do Uber, o Michelangelo, para treinar e implantar o modelo. Depois de implantado, é preciso servir as previsões em tempo real. Para a atualização do modelo, o blog descreve fluxos periódicos de retreino e validação automáticos.

1. O modelo é treinado com o framework Canvas do Michelangelo sobre o conjunto de treino.

2. Depois de treinado e implantado, o modelo passa a atender as previsões em tempo real.

3. Fluxos periódicos de retreino e validação automáticos estão configurados sobre o modelo.

No lado do serving, o uRoute faz o papel de frontend das consultas de rota, pede rotas e ETAs ao motor de rotas e, com esse ETA e outras features, chama o serviço de predição online do Michelangelo para obter a previsão do DeepETA.

O DeepETA foi lançado em produção para previsão global de ETA de veículos de quatro rodas (4-wheel, no blog). Segundo os autores, o lançamento torna possível e eficiente treinar e servir modelos de deep learning de grande escala que preveem ETAs melhor que as abordagens com XGBoost, e estabelece uma base de modelo reutilizável para vários casos de consumo.

Entre os próximos passos, o time cita explorar treino contínuo e incremental, que permitiria treinar os ETAs com dados mais recentes.