Back-End

16 fev, 2018

Omphalos: ferramenta de backtesting de séries temporais, extensiva em linguagem e paralela da Uber

Publicidade

Operando em mais de 600 cidades em todo o mundo, a Uber aproveita os dados agregados sobre as preferências dos usuários para melhorar as experiências de motoristas e passageiros. Ao longo do tempo, esses pontos de dados anonimamente agregados geram milhões de séries temporais, que podem ser vistas amplamente ou em um nível profundo de granularidade.

Essas previsões de séries temporais são essenciais para grande parte da nossa tomada de decisões, da otimização de mercado e da modelagem de custos até o planejamento de capacidade de hardware.

Para permitir previsões rápidas, flexíveis e precisas e proporcionar maior confiabilidade e consistência em nossos modelos, a equipe da Forecasting Platform da Uber criou o Omphalos, um framework de backtesting de séries temporais que gera comparações eficientes e precisas de modelos de previsão em todas as linguagens e simplifica nosso processo de desenvolvimento de modelos, melhorando assim a experiência do cliente. Neste artigo, discutimos o design, a implementação e as aplicações desse novo framework.

Previsão na Uber

Ao aproveitar os dados da série temporal, os algoritmos de previsão geralmente exigem testes cronológicos, referido de outra maneira como backtesting. Simplificando, os modelos que aplicam esses algoritmos não devem ser treinados com valores de data após o horizonte de previsão.

Uma prática comum divide arbitrariamente uma série temporal em conjuntos de treinamento e validação, preservando a cronologia, semelhante a escolher aleatoriamente uma passagem de treinamento (conforme mostrado na Figura 1). Dada a variância métrica de negócios da Uber e a vida útil relativamente curta, achamos esse método pouco confiável.

Por exemplo, os modelos de séries temporais treinados com e sem dados da véspera de Ano Novo mostram significativas diferenças de desempenho de previsão, dado o rápido crescimento (ano a ano) do nosso negócio.

Duas formas de backtesting

Para obter uma medida mais consistente do desempenho do modelo, nós criamos um procedimento de backtesting que aplica uma lógica de validação cruzada, que explica a natureza sequenciada do conjunto de dados.
Esse procedimento aplica dois tipos de backtesting: janela deslizante e janela de expansão.

Embora ambos tenham seus casos de uso aplicáveis, a forma da janela deslizante consegue um equilíbrio favorável entre a precisão do modelo e o tempo de treinamento, especialmente quando se trata de testar dados de alta frequência, como séries temporais diárias e horárias. A forma de janela de expansão, por outro lado, é usada com mais frequência em séries temporais semanais, mensais ou trimestrais, nas quais o número de pontos históricos é limitado.

Em seguida, descrevemos como esses dois tipos de backtesting podem ser aplicados à previsão:

Janela deslizante

O método da janela deslizante requer três hiperparâmetros – tamanho da janela de treinamento, tamanho da janela de previsão (horizonte) e passos deslizantes, detalhados abaixo:

  • Tamanho da janela de treinamento: o número de pontos de dados incluídos em uma passagem de treinamento.
  • Tamanho da janela de previsão: o número de pontos de dados a serem incluídos na previsão.
  • Passos deslizantes: o número de pontos de dados saltados de um passe para outro.
No modelo de backtesting de janela deslizante, uma janela de treinamento de tamanho fixo (em preto), desliza sobre todo o histórico de uma série temporal e é repetidamente testada contra uma janela de previsão (em laranja) com pontos de dados mais antigos descartados.

Janela de expansão

A forma de janela de expansão requer quatro hiperparâmetros: tamanho da janela inicial, tamanho da janela final, tamanho da janela de previsão e etapas de expansão, descritas abaixo:

  • Tamanho da janela inicial: o número de pontos de dados incluídos na primeira passagem de treinamento.
  • Tamanho da janela final: o número de pontos de dados incluídos na última passagem de treinamento.
  • Tamanho da janela de previsão: número de pontos de dados incluídos para previsão.
  • Etapas de expansão: o número de pontos de dados adicionados às séries temporais de treinamento de uma passagem para outra.
No modelo de backtesting de janela de expansão, uma janela de treinamento (em preto) se expande ao longo do histórico completo de uma série temporal e é repetidamente testada contra a janela de previsão (em laranja) sem descartar pontos de dados mais antigos.

Medindo a precisão da previsão

Quando um algoritmo de previsão de séries temporais é testado usando qualquer um desses dois métodos de backtesting, a Omphalos gera automaticamente arrays de valores previstos e valores reais correspondentes a partir dos quais podemos calcular várias medidas de precisão de previsão.

Enquanto essas medidas tipicamente assumem uma única passagem de treinamento, precisamos adequar essas medidas para refletir melhor o desempenho do modelo em uma configuração de backtesting. Além disso, como a Uber opera em centenas de cidades em todo o mundo, a precisão do modelo pode variar de acordo com as métricas da cidade. Por exemplo, em uma previsão típica com duas semanas de antecedência, observamos um grande intervalo de Weighted Mean Absolute Percentage Error (wMAPE, medida de desempenho que usamos) quando o mesmo modelo é aplicado a diferentes cidades. Portanto, precisamos de uma maneira confiável de resumir o desempenho geral do modelo para determinar qual devemos usar.

Para enfrentar esses desafios, desenvolvemos uma estratégia de avaliação de modelo automático que compara a média de wMAPE por cidade e a passagem de treinamento, enquanto estabelece um limiar para o wMAPE menos precisa e a tendência mediana. Um histograma de wMAPE também pode ser usado durante uma verificação manual, se necessário.

Com essa nova técnica pronta, precisamos apenas de uma ferramenta de backtesting para aplicá-la.

Construindo a Omphalos

Embora – geralmente – não seja difícil implementar um procedimento de backtesting em uma linguagem, é preciso muito mais esforço para alinhar as medidas de desempenho do modelo em todas as linguagens, mesmo entre dois cientistas de dados na mesma equipe. Como resultado, decidimos criar um framework extensível à linguagem que poderia aplicar nossa estratégia de avaliação automática do modelo; o desempenho do modelo deve ser comparável entre as linguagens, desde que a mesma configuração de backtesting seja usada.

Também precisávamos do framework para orquestrar eficazmente dezenas de algoritmos que funcionavam contra centenas (ou mesmo milhares) de séries temporais, enquanto permaneciam leves. Para conseguir isso, escolhemos escrever a estrutura em Go por causa de sua robustez e escalabilidade.

Incorporando a extensibilidade de linguagem

Dada a variedade de linguagens usadas pelas equipes de engenharia e ciência de dados da Uber, precisávamos garantir que o Omphalos pudesse ser usado com linguagens além de Go. Na indústria em geral, R tem sido a linguagem padrão na previsão de séries temporais como resultado de seu conhecido pacote de previsão, e Python surgiu como um importante jogador nesse domínio, também devido aos pacotes de machine learning bem suportados como Scikit-Learn e TensorFlow. Por essas razões, decidimos construir interfaces para suportar essas três linguagens com a capacidade de incorporar outras no futuro.

Ao configurar um algoritmo para testar com a Omphalos, precisamos de três funcionalidades:

  • O caminho do arquivo para o código de entrada do algoritmo.
  • Uma função de geração do modelo que aceita o quadro de dados de entrada.
  • Uma função de previsão que aceita o horizonte de modelo e previsão e retorna a respectiva previsão.

A camada de console orquestra o treinamento do modelo em diferentes linguagens usando o pacote exec do Go. Esse sistema nos dá a flexibilidade para testar qualquer algoritmo que suporte esses requisitos, reutilizar modelos que não requeram reciclagem em cada etapa de backtest (redes neurais) e usar bibliotecas comuns (por exemplo, aplicando o pacote de previsão em R como a função de previsão).

Até agora, testamos 10 algoritmos de previsão de séries em R, três em Python e quatro em Go, conforme listado na Tabela 1 abaixo:

Os algoritmos de previsão de séries temporais testados usando a Omphalos incluem os tradicionalmente aplicados em R, Go e Python.

Robustez e escalabilidade

Além da extensibilidade de linguagem, queríamos que a Omphalos fosse robusta e escalável o suficiente para atender às demandas de previsão da Uber. Mais especificamente:

  1. A ferramenta deve aproveitar a capacidade computacional crítica para fornecer uma iteração mais rápida e um melhor feedback para nossos usuários.
  2. Ela deve ser capaz de rodar localmente em uma estação de trabalho ou remotamente em um servidor de CPU/GPU aprimorado.
  3. Deve ser simples para os usuários se adaptarem a ela facilmente e interagir seus algoritmos no framework.

Para facilitar essas condições, o núcleo do design da Omphalos é uma camada de console de interface de linha de comando que carrega um arquivo de configuração definido pelo usuário e dados de séries temporais, alimenta esses dados em algoritmos de previsão implementados em diferentes linguagens, coleta os valores de previsão e gera relatórios abrangentes de backtesting.

A arquitetura da Omphalos usa dados de séries temporais e um arquivo de configuração definido pelo usuário, incorporando parâmetros especificados como entrada, e produz um relatório de resumo abrangente de backtesting como saída.

Dado o design concorrente do Go, o console que construímos pode coordenar e supervisionar muitos algoritmos em R e Python de uma única thread para utilizar completamente todas as CPUs disponíveis. O Omphalos também facilita o backtesting concorrente de séries temporais, com a camada de console desencadeando X vezes as goroutines de Y – cada uma delas responsável por rodar backtesting de um algoritmo versus uma série temporal.

Os resultados de previsão de cada passagem de treinamento são armazenados separadamente e usados para calcular métricas de resumo, como o wMAPE médio.

Usando a Omphalos

A Omphalos tem duas funcionalidades principais que nos permitem fazer backtest de uma série temporal de forma mais rápida e eficaz: comparando modelos dentro dela e entre linguagens para determinar o melhor ajuste para um determinado conjunto de dados e alavancar nossa API AutoForecaster para testar a precisão de previsão.

Comparação de modelo

Dada a variedade de casos de uso de previsão da Uber, precisávamos de uma ferramenta que pudesse comparar perfeitamente modelos em métricas de previsão, algoritmos de tempos de execução e taxas de erro. Com o Omphalos, podemos justapor o desempenho das redes neurais no TensorFlow (Python) nos algoritmos estatísticos tradicionais em R, à uma implementação leve de 500ms em Go.

Para testar a eficiência do Omphalos, comparamos oito algoritmos de previsão populares em R para nossa API AutoForecaster (uma ferramenta in-house que fornece previsões precisas para qualquer série temporal), usando contagens de viagens diárias completas de 20 cidades ao redor do globo.

Ao comparar algoritmos de previsão populares em R com AutoForecaster, usamos contagens de viagens diárias completas de 20 cidades como nossos dados de entrada e configuramos um procedimento de backtesting de janela deslizante com tamanho de janela de treino, tamanho de janela de previsão e passos deslizantes definidos em 189, 14 e 14, respectivamente.

Dada essa capacidade, a Omphalos tornou-se parte integrante do nosso processo de desenvolvimento de modelos. Agora, os cientistas de dados podem comparar seu próprio modelo com muitos existentes, sem nenhum esforço extra; uma vez que um determinado modelo seja comprovadamente mais efetivo, ele pode ser adotado rapidamente por outros.

Auto-Forecaster

Nossa equipe da Forecasting Platform criou o Auto-Forecaster para fornecer previsões precisas para qualquer série temporal com entrada mínima, permitindo que cientistas de dados em toda a empresa prevejam em casos de uso ilimitados. Para avaliar o desempenho desse algoritmo, no entanto, precisamos testá-lo em uma ampla gama de séries temporais em diferentes períodos de tempo, e a Omphalos foi um excelente candidato para o trabalho.

Para testar seu desempenho, queríamos determinar se o Auto-Forecaster poderia fornecer previsões para centenas de milhares de séries temporais em centenas de painéis definidos pelo usuário – simultaneamente. Nossos testes incluíram: construir um histograma de desempenho de erro (conforme descrito na Figura 4), identificar tipos de séries temporais que estavam funcionando muito bem ou muito mal e garantir a execução de séries temporais rejeitadas (aquelas que fornecem previsões não confiáveis). Um cálculo simples mostrou que a execução dessas previsões em série com um tempo médio de previsão de dois segundos levaria 155 horas, ou aproximadamente 6,5 dias.

Um histograma de erros de backtest ao alavancar o Auto-Forecaster para uma determinada série temporal pode nos ajudar a entender como nossos algoritmos estão funcionando.

Ao aproveitar a capacidade da Omphalos de orquestrar processos concorrentes, no entanto, dividimos as tarefas de previsão em 24 núcleos em um único servidor (com cada núcleo correspondendo a uma série temporal). Com outros métodos, uma única previsão pode demorar apenas alguns segundos, mas testar séries temporais muitas vezes normalmente demora dias. Com a Omphalos, determinamos que demora apenas um quarto do dia – uma diferença horária de aproximadamente 150 horas – para executar essas previsões em R e Python.

Em seguida, testamos esse conjunto de dados do Omphalos com a nossa implementação do Auto-Forecaster. Isso resultou em um desempenho mais rápido (0,5 segundos em média) e melhor gerenciamento de concorrência, reduzindo o tempo de feedback para uma hora – agora uma diferença de tempo de 154 horas do processo em série.

Esse tipo de melhoria de desempenho nos permite incorporar backtesting de conjunto de dados completo em um pipeline de integração contínua, levando a uma previsão mais precisa.

Trabalho futuro

Embora o Omphalos tenha sido originalmente projetado como um framework de backtesting extensível e paralelizada em linguagem para algoritmos de previsão de séries temporais, identificamos duas áreas nas quais poderíamos aproveitar ainda mais essa ferramenta:

Construindo intervalos de previsão empírica

Os intervalos de previsão gerados por algoritmos de previsão são tipicamente muito estreitos, levando a uma subestimação do risco; por outro lado, como geralmente usamos conjuntos de modelos de previsão, pode ser complicado gerar intervalos de previsão de conjunto. Assim, estamos explorando a possibilidade de usar a Omphalos para construir intervalos de previsão empírica para melhor informar as decisões empresariais relacionadas com a previsão.

Algoritmos de detecção de anomalia

A previsão e a detecção de anomalia estão inerentemente conectadas. No futuro, planejamos adicionar novos recursos ao Omphalos para que, tanto a janela deslizante quanto os métodos de backtesting da janela em expansão possam ser aplicados diretamente aos algoritmos de detecção de anomalia. Isso expandirá amplamente nossas capacidades de previsão, facilitando, por sua vez, experiências aprimoradas nos nossos serviços.

Se você está interessado em pressionar os limites da previsão de séries temporais ou detecção de anomalia, considere se candidatar para um cargo em nossa equipe!

***

Este artigo é do Uber Engineering. Ele foi escrito por Roy Yang e Calvin Worsnup. A tradução foi feita pela Redação iMasters com autorização. Você pode conferir o original em: https://eng.uber.com/omphalos/