Jump Like A Squirrel: Optimized Execution Step Order for Anytime Random Forest Inference

Este artigo propõe uma abordagem de algoritmo "anytime" para florestas aleatórias que otimiza a ordem de execução de passos individuais nas árvores de decisão, introduzindo heurísticas como a "Ordem Esquilo Reversa" que alcança desempenho quase ideal em tempo polinomial para sistemas com recursos limitados.

O essencial

Imagine que você tem um time de especialistas (uma "floresta" de árvores de decisão) tentando adivinhar qual é a melhor resposta para um problema complexo. Normalmente, você pede para cada especialista trabalhar até o fim, chegar a uma conclusão definitiva e só então você junta todas as respostas para tomar uma decisão final.

O problema é: e se você tiver apenas pouquíssimo tempo? Se o relógio estiver correndo e você tiver que parar o processo no meio da frase, o que acontece?

Nas abordagens antigas, se você parasse no meio, perderia todo o trabalho daquele especialista que estava respondendo. Era como se ele tivesse que terminar o relatório inteiro para você poder ler algo. Se ele parasse na página 5 de 10, você jogava a página 5 fora e esperava o próximo especialista terminar o trabalho dele.

Este artigo, chamado "Pule Como um Esquilo" (Jump Like A Squirrel), propõe uma maneira muito mais inteligente e ágil de fazer isso.

A Metáfora do Esquilo e da Floresta

Pense nas árvores de decisão como uma floresta de trilhas. Cada trilha tem vários pontos de decisão (curvas, bifurcações).

• O jeito antigo: Você mandava um esquilo correr até o final de uma trilha inteira, pegar uma fruta (a resposta) e só então mandava o próximo esquilo começar na próxima trilha.
• O jeito novo (Jump Like A Squirrel): O esquilo pode pular de uma trilha para outra a qualquer momento! Ele não precisa terminar a trilha atual para ir para a próxima. Ele pode dar um pulo na Trilha A, depois um pulo na Trilha B, depois voltar para a Trilha A.

Por que isso é bom?
Em cada "pulso" (passo) que o esquilo dá, ele aprende algo novo e fica mais confiante na resposta. Mesmo que você pare o esquilo no meio do caminho, ele já tem uma boa ideia do que está acontecendo. Nada do conhecimento ganho até aquele ponto é desperdiçado.

O Grande Desafio: Em qual ordem pular?

Agora que podemos pular livremente entre as árvores, surge uma pergunta: Qual é a melhor ordem de pulos para ter a resposta mais precisa no menor tempo?

Se você pular aleatoriamente, pode demorar muito para chegar a uma boa resposta. Se você seguir uma ordem ruim, pode perder tempo em detalhes que não importam.

Os autores do artigo criaram três "mapas de pulos" (ordens de execução):

1. A Ordem Perfeita (Optimal Order): É como ter um mapa do tesouro feito por um gênio da matemática. Ele calcula exatamente qual sequência de pulos dá a melhor resposta média.

   • O problema: Para florestas grandes, calcular esse mapa perfeito leva tanto tempo que é impossível (leva anos!). É como tentar calcular todas as combinações de um jogo de xadrez antes de fazer o primeiro movimento.

2. A Ordem do Esquilo para Frente (Forward Squirrel Order): É como um esquilo que olha para frente e diz: "Qual é o próximo pulo que me dá a maior chance de acerto agora?". Ele toma a decisão mais inteligente passo a passo, mas de forma rápida.

3. A Ordem do Esquilo para Trás (Backward Squirrel Order): Esta é a estrela do show. Imagine que você já sabe a resposta final perfeita. Agora, o esquilo trabalha de trás para frente, perguntando: "Qual foi o último pulo que me trouxe mais perto da perfeição?". Ele remove os passos menos importantes primeiro e deixa os mais importantes para o final (ou seja, para serem feitos primeiro no tempo real).

   • Resultado: Essa ordem é incrivelmente rápida de calcular e funciona quase tão bem quanto a "Ordem Perfeita" (cerca de 94% da eficiência), mas sem gastar anos calculando.

Por que isso importa no mundo real?

Isso é vital para dispositivos pequenos e rápidos, como:

• Sensores em carros autônomos: Precisam decidir se vão frear ou virar em milissegundos.
• Dispositivos médicos: Precisam analisar sinais vitais e dar um alerta imediato.
• Celulares e IoT: Precisam economizar bateria e processamento.

Com essa técnica, o dispositivo não precisa esperar o "relatório completo". Ele pode dar uma resposta boa a qualquer momento. Se o tempo acabar, ele entrega a melhor resposta possível baseada no pouco tempo que teve.

Resumo da Ópera

O artigo ensina que, em vez de fazer os especialistas trabalharem até o fim antes de ouvir deles, podemos ouvir um pouco de cada um, a cada segundo, pulando entre eles de forma inteligente.

A técnica do "Esquilo para Trás" (Backward Squirrel) é a melhor solução prática: ela organiza o trabalho de forma que, não importa quando você pare o processo, você tenha a maior chance possível de acertar a resposta, tudo isso sem gastar tempo demais calculando como organizar o trabalho. É como ter um time de especialistas que sabe exatamente o que dizer a cada segundo para que você nunca fique sem uma boa resposta.

Resumo técnico

Título: Jump Like A Squirrel: Ordem de Execução Otimizada de Passos para Inferência de Florestas Aleatórias "Anytime"

1. Problema e Motivação

Florestas aleatórias (Random Forests) e árvores de decisão são modelos populares para sistemas com recursos limitados devido à sua eficiência e tamanho reduzido. No entanto, em ambientes onde o tempo de execução é imprevisível ou restrito (como sistemas embarcados ou em tempo real), pode não haver tempo suficiente para executar a floresta completa.

• Limitação das Abordagens Atuais: Métodos existentes de algoritmos "anytime" (que podem ser interrompidos a qualquer momento com um resultado útil) operam na granularidade de árvores inteiras. Ou seja, uma árvore deve ser totalmente percorrida até uma folha antes que sua previsão seja considerada. Se a execução for interrompida no meio de uma árvore, toda a informação ganha até aquele ponto é perdida.
• Oportunidade: Árvores de decisão aumentam a confiança da previsão a cada passo (nó interno). Interromper a execução no meio de uma árvore não deve resultar na perda de dados se os vetores de probabilidade dos nós internos forem preservados.
• Desafio: Ao permitir a execução na granularidade de passos individuais (nós) e a capacidade de "pular" entre árvores antes de atingir uma folha, abre-se um espaço de design vasto. O objetivo é encontrar a ordem de passos que maximize a precisão média ao longo de todo o processo de execução, assumindo que a probabilidade de interrupção é uniforme ao longo do tempo.

2. Metodologia

Os autores propõem uma abordagem que estende a inferência de florestas aleatórias para operar em qualquer momento, preservando previsões em nós internos.

A. Adaptação para "Anytime"

• Previsão em Nós Internos: Durante o treinamento (algoritmo CART), cada nó interno é associado a um subconjunto dos dados de treinamento. O vetor de probabilidade de classes para esse subconjunto é calculado e armazenado no nó.
• Inferência Interrompida: Em caso de interrupção, a previsão final é a soma dos vetores de probabilidade de todos os nós visitados em todas as árvores, selecionando a classe com maior probabilidade acumulada.

B. Estratégias de Ordenação de Passos (Step Orders)

O artigo propõe três métodos principais para determinar a ordem em que os passos (nós) devem ser visitados para maximizar a precisão média:

1. Ordem Ótima (Optimal Order):

   • Conceito: Encontra a ordem de passos que maximiza a precisão média em um conjunto de dados de ordenação ($S_o$).
   • Abordagem: Modela o espaço de busca como um grafo acíclico direcionado ponderado, onde vértices representam estados (número de passos em cada árvore) e arestas representam a transição para o próximo passo.
   • Algoritmo: Utiliza o algoritmo de Dijkstra para encontrar o caminho que minimiza a soma das imprecisões (equivalente a maximizar a precisão).
   • Complexidade: Exponencial em relação ao tamanho da floresta ($O((d+1)^t \cdot \log((d+1)^t))$), tornando-se inviável para florestas grandes.

2. Ordem Esquilo (Squirrel Order) - Heurísticas Polinomiais:
   Para contornar a complexidade exponencial, são propostas duas heurísticas de busca gulosa (greedy) que operam no mesmo grafo lógico, mas sem construí-lo explicitamente:

   • Forward Squirrel Order (Esquilo Forward): Começa no estado inicial (0 passos) e escolhe iterativamente o próximo passo (em qualquer árvore) que oferece a maior precisão imediata.
   • Backward Squirrel Order (Esquilo Backward): Começa no estado final (todas as árvores completas) e trabalha de trás para frente, escolhendo o passo que, se removido, mantém a maior precisão no estado anterior.
   • Complexidade: Polinomial ($O(d \cdot t^2)$), permitindo a geração de ordens para florestas muito maiores.

3. Ordens Intuitivas (Baselines):

   • Depth Order: Executa uma árvore inteira antes de passar para a próxima.
   • Breadth Order: Executa um nível de todas as árvores antes de descer ao próximo nível.
   • Prune/QWYC Orders: Usam métricas de poda existentes para ordenar as árvores, aplicadas nas estratégias de profundidade ou largura.

C. Implementação Técnica

• A implementação utiliza árvores nativas (armazenadas em arrays) em vez de estruturas de ponteiros ou árvores if-else no código.
• O estado da inferência é mantido por um array de índices que aponta para o nó atual em cada árvore.
• O loop de inferência itera sobre a ordem de passos gerada, avançando um nó por vez e atualizando o índice correspondente, permitindo interrupção e retomada instantânea.

3. Contribuições Principais

1. Generalização Anytime: Habilita a execução de florestas aleatórias como algoritmos anytime na granularidade de passos individuais, preservando informações parciais.
2. Novos Geradores de Ordem: Propõe três geradores de ordem de passos focados em otimizar a precisão média: Optimal Order, Forward Squirrel Order e Backward Squirrel Order.
3. Validação Experimental: Realiza uma avaliação extensiva em 9 conjuntos de dados do repositório UCI, comparando as novas abordagens com soluções intuitivas e de poda.

4. Resultados da Avaliação

Os experimentos foram conduzidos em conjuntos de dados variados (binários e multiclasse) e em diferentes plataformas (servidor AMD EPYC e microcontrolador ESP32).

• Correlação Tempo-Passos: Foi estabelecido que existe uma relação linear entre o número de passos e o tempo de execução, validando o uso de "passos" como métrica de progresso para algoritmos anytime.
• Desempenho de Precisão:
  • A precisão aumenta consistentemente com o número de passos, confirmando a viabilidade da abordagem.
  • A Ordem Ótima obteve a melhor precisão média normalizada (NMA), atingindo ~97% da precisão máxima possível em média.
  • A Backward Squirrel Order performou excepcionalmente bem, alcançando ~94% da precisão da Ordem Ótima e ~99% da melhor precisão entre todas as outras ordens testadas (incluindo as heurísticas e intuitivas).
  • A Forward Squirrel Order foi inferior à versão Backward na maioria dos casos.
• Eficiência Computacional:
  • A geração da Ordem Ótima tornou-se inviável após 8 árvores devido ao tempo e memória exponenciais.
  • A Backward Squirrel Order manteve tempos de geração polinomiais, permitindo a aplicação em florestas muito maiores e mais profundas.
• Impacto da Estrutura de Dados:
  • Em problemas de classificação multiclasse, variantes de profundidade (Depth Order) tendem a performar melhor.
  • Em problemas binários, variantes de largura (Breadth Order) mostraram-se competitivas.
  • Contudo, a Backward Squirrel Order demonstrou robustez, performando bem independentemente do tipo de conjunto de dados.

5. Significado e Conclusão

O trabalho demonstra que é possível transformar florestas aleatórias tradicionais em algoritmos "anytime" altamente eficientes, não apenas interrompendo árvores inteiras, mas navegando dinamicamente entre elas passo a passo.

A principal descoberta é que a Backward Squirrel Order oferece o melhor compromisso entre qualidade e custo computacional. Ela consegue aproximar-se muito da solução ótima teórica (que é computacionalmente proibitiva) com um custo de geração polinomial. Isso torna a técnica viável para sistemas embarcados e de tempo real, onde o tempo de inferência é crítico e imprevisível, permitindo que o sistema retorne a melhor previsão possível dentro de qualquer janela de tempo disponível.

Em resumo, o artigo redefine como florestas aleatórias podem ser executadas em ambientes restritos, oferecendo uma metodologia prática e otimizada para maximizar a precisão sob restrições de tempo.