Nem toda inteligência artificial é uma rede neural. As florestas aleatórias são uma das demonstrações mais claras de que o aprendizado de máquina é uma construção matemática: a reamostragem altera os dados vistos por cada modelo, a aleatorização altera as decisões disponíveis para cada árvore e a agregação transforma muitos preditores instáveis em um único preditor robusto. Quando os dados se tornam grandes demais para uma única máquina — ou chegam como um fluxo — cada parte dessa construção precisa sobreviver à mudança de engenharia.
01A parte fácil: as florestas já contêm trabalho paralelo
O artigo de 2015 de Robin Genuer, Jean-Michel Poggi, Christine Tuleau-Malot e Nathalie Villa-Vialaneix parte de um atrativo óbvio. Uma floresta aleatória é um conjunto de muitas árvores de decisão. As árvores são deliberadamente diferenciadas umas das outras e, em seguida, suas previsões são agregadas — um voto majoritário para classificação ou uma média para regressão. Como uma árvore não precisa esperar que a árvore anterior termine, a floresta parece “embaraçosamente paralela”.
Essa observação está correta, mas incompleta. Ela descreve como distribuir as árvores. O big data muitas vezes nos obriga a distribuir os próprios dados, e essas não são a mesma operação.
Extraia uma amostra bootstrap dos dados de aprendizado, com reposição.
Em cada nó, considere apenas um subconjunto aleatório de variáveis preditoras.
Construa a árvore de decisão aleatória sem a etapa usual de poda.
Combine muitas árvores em um voto de classificação ou média de regressão.
Esta distinção entre paralelismo em nível de árvore e particionamento em nível de dados é a primeira lição duradoura do artigo. Um sistema distribuído pode tornar o código mais rápido e, ao mesmo tempo, alterar silenciosamente o experimento estatístico subjacente.
02Bootstrap não é apenas uma forma de manter os processadores ocupados
Para um conjunto de aprendizado de n observações, uma amostra bootstrap clássica contém n extrações feitas com reposição. Algumas observações aparecem várias vezes; outras não são selecionadas nenhuma vez. Esse padrão não é um detalhe de implementação. É um dos mecanismos matemáticos que criam diversidade entre as árvores.
À medida que o conjunto de dados cresce, o número de cópias de uma observação específica em uma amostra bootstrap é bem aproximado por uma distribuição de Poisson com média 1.
Aproximadamente 36,8% das observações estão ausentes na amostra bootstrap de uma determinada árvore. Essas são suas observações out-of-bag.
Laboratório Bootstrap
Extraia 12 vezes de 12 observações, com reposição. Rótulos repetidos são usados para treinar a árvore; observações que nunca aparecem tornam-se o conjunto de teste out-of-bag daquela árvore.
As variantes online revisadas no artigo usam essa convergência ao contrário: quando chega uma nova observação, cada árvore é atualizada k vezes, com k extraído de uma distribuição de Poisson(1). Essa é uma maneira compacta de imitar as multiplicidades que um bootstrap em lote teria produzido — sem armazenar e reamostrar todo o conjunto de dados históricos.
03Dados out-of-bag são o diagnóstico integrado da floresta
Uma observação excluída da amostra bootstrap de uma árvore pode testar essa árvore porque a árvore não foi treinada nela. Em toda a floresta, cada observação é out-of-bag para um subconjunto de árvores. Suas previsões podem ser combinadas em um erro out-of-bag, fornecendo à floresta uma estimativa interna do desempenho preditivo sem reservar uma amostra de validação separada.
O mesmo mecanismo sustenta a importância de variáveis por permutação. Pegue a amostra out-of-bag de uma árvore, embaralhe um preditor e meça quanto o erro aumenta. Se destruir a relação capturada por esse preditor prejudica a previsão, a variável foi importante para a árvore.
Média, sobre as árvores, do erro out-of-bag adicional causado pela permutação do preditor Xj.
É aqui que o artigo se torna mais do que um levantamento de implementações mais rápidas. Seus autores tratam a estimativa de erros e a importância das variáveis como parte do método, e não como relatórios opcionais. Um sistema escalonado que ainda retorna previsões, mas perde seus diagnósticos confiáveis, não é obviamente a mesma floresta aleatória.
04Quando o diagnóstico se torna um método: VSURF
O erro out-of-bag e a importância por permutação também se tornaram o motor de uma linha de trabalho conectada. Robin Genuer, Jean-Michel Poggi e Christine Tuleau-Malot — o trio central compartilhado por ambos os projetos de pesquisa — desenvolveram um procedimento de seleção de variáveis e o disponibilizaram como VSURF, um pacote R distribuído pelo CRAN.
A conexão é direta. O trabalho de big data pergunta o que acontece quando uma implementação escalável não consegue mais reproduzir o erro OOB clássico ou a importância das variáveis. O VSURF mostra o quanto essas quantidades podem fazer quando são preservadas: elas ordenam os preditores, identificam um piso de ruído orientado por dados, comparam florestas aninhadas e decidem se uma variável adicional melhora a previsão o suficiente para ser mantida.
A seleção de variáveis depende da finalidade da análise
Mantenha as variáveis fortemente relacionadas à resposta, incluindo a redundância útil. Em imagens ou dados funcionais, os preditores correlacionados podem descrever uma região inteira ou uma estrutura científica que vale a pena compreender.
Crie um subconjunto menor e com menor redundância que seja suficiente para uma previsão precisa. O objetivo é um modelo operacional compacto e não um mapa completo de todas as variáveis associadas.
Calcule a média da importância por permutação em florestas repetidas, estime a variabilidade associada a preditores não informativos e remova as variáveis abaixo do limiar orientado por dados.
Compare florestas aninhadas construídas a partir das variáveis ordenadas e mantenha um modelo compacto cujo erro OOB permaneça dentro da incerteza do melhor resultado observado.
Introduza as variáveis ordenadas sequencialmente e mantenha uma nova variável apenas quando sua redução no erro OOB exceder um limiar estimado a partir da cauda ruidosa.
library(VSURF)
selection <- VSURF(x = predictors, y = response)
summary(selection)O pacote operacionaliza a pesquisa para regressão e classificação supervisionada, incluindo cenários de alta dimensão. Seus cálculos também podem ser paralelizados, preservando a geração reproduzível de números aleatórios.
05A armadilha paralela: os pedaços raramente são populações aleatórias
Uma adaptação comum do MapReduce divide um conjunto de dados muito grande em partes menores, constrói uma floresta independentemente em cada parte e mescla todas as árvores. Computacionalmente, isso é atraente. Estatisticamente, pode ser perigoso.
Os dados reais em disco são frequentemente ordenados por tempo, geografia, sistema de aquisição, cliente, classe ou alguma outra forma de localidade. Envie blocos contíguos para nós de trabalho separados e cada floresta pode aprender uma população diferente.
Partição contígua
Cada nó de trabalho recebe uma fatia localmente homogênea.
Partição aleatória ou estratificada
Cada nó de trabalho recebe uma mistura mais representativa.
Registros vizinhos no disco podem compartilhar atributos, portanto, blocos ingênuos não são amostras aleatórias.
As florestas locais podem ser tão diferentes que a média de todas as suas árvores não tem um significado estatístico claro.
O comportamento de um bootstrap m-out-of-n depende fortemente de m, que é difícil de ajustar dentro de um esquema distribuído simples.
Os nós de trabalho perdem os índices globais de treinamento necessários para reconstruir o erro out-of-bag clássico e a importância das variáveis.
06Quando os dados nunca param, o experimento muda novamente
Em um ambiente online, o aprendiz vê a observação atual, mas pode não reter todas as observações anteriores. A floresta precisa se atualizar à medida que os dados chegam. As florestas aleatórias on-line revisadas pelos autores combinam bagging on-line de Poisson, Árvores Extremamente Randomizadas e estatísticas incrementais de nós.
(xt, yt)
para cada árvore
ou testá-la quando k = 0
Se k = 0, a observação atual é out-of-bag para essa árvore e pode atualizar sua estimativa de erro. Mas o artigo aponta a aproximação: depois que a árvore muda com dados posteriores, essa previsão antiga não pode ser recalculada a menos que a observação tenha sido armazenada. A estimativa out-of-bag on-line, portanto, não é idêntica à quantidade clássica em lote.
A importância das variáveis é ainda mais difícil. A importância por permutação nos pede para embaralhar uma variável em uma amostra out-of-bag. Um fluxo que é descartado após o processamento não deixa nada para permutar. A restrição computacional remove o objeto exigido pela definição estatística.
Esse é o cerne de “IA é matemática”
O algoritmo não é apenas o código que produz uma previsão. É também o experimento amostral, a estimativa do erro e a definição da importância. Altere o ciclo de vida dos dados e esses objetos matemáticos poderão ter que ser redefinidos.
07Várias rotas preservam diferentes partes do método
Os autores mapeiam diversas direções para preservar mais o significado do método sob restrições de big data. Diferentes formas de escala exigem diferentes compromissos, e a escolha deve seguir a propriedade estatística que mais importa.
Randomize ou estratifique os dados antes de distribuí-los, especialmente na resposta, em vez de confiar na ordem de armazenamento físico.
Construa amostras bootstrap de tamanho nominal n a partir de apenas m ≪ n observações distintas, mantendo a lógica de reamostragem e reduzindo a carga computacional.
Use famílias de árvores mais fortemente aleatorizadas, como Árvores Extremamente Randomizadas, Perfect Random Tree Ensembles ou Purely Random Forests.
Trate o resultado como um conjunto de florestas locais e adapte a votação para levar em conta o viés de amostragem, em vez de mesclar todas as árvores indiscriminadamente.
Use florestas on-line para lidar com volume e velocidade, processando apenas o fluxo de dados suficiente para atingir a precisão adequada.
Julgue uma variante escalável pelo que ela preserva a respeito do erro OOB e da importância das variáveis, não apenas pela taxa de transferência.
08Por que essas obras conectadas ainda constituem um artigo didático contundente
MapReduce não é mais a manchete da moda que era em 2015. O problema subjacente não envelheceu: o aprendizado distribuído ainda particiona observações, os sistemas de streaming ainda esquecem o histórico e as restrições de produção ainda tentam os engenheiros a tratar um estimador definido matematicamente como intercambiável com qualquer implementação que produza previsões de aparência semelhante.
O valor do artigo é a sua recusa em confundir escalabilidade com correção. Ele faz quatro perguntas que permanecem úteis sempre que um método de aprendizado de máquina passa de um notebook para uma infraestrutura:
- Que distribuição cada nó de trabalho realmente vê?
- Qual aleatoriedade é essencial para o estimador e qual é meramente computacional?
- Ainda podemos estimar o erro sem contaminar as observações de teste?
- Ainda podemos explicar quais variáveis são importantes no novo ciclo de vida dos dados?
Essas são questões matemáticas expressas através da arquitetura de sistemas. As máquinas, o layout de armazenamento e a estratégia de atualização fazem parte do modelo estatístico, quer os reconheçamos ou não.
O VSURF acrescenta a lição complementar. Quando o erro OOB e a importância das variáveis são preservados com cuidado, eles podem conduzir um fluxo de trabalho de seleção de ponta a ponta, distinguir interpretação de previsão e se tornar um software que outros pesquisadores e engenheiros podem aplicar aos seus próprios dados.
09A pesquisa por trás deste artigo
Random forests and big data
Robin Genuer, Jean-Michel Poggi, Christine Tuleau-Malot e Nathalie Villa-Vialaneix. Apresentado nas 47ª Journées de Statistique de la Société Française de Statistique, Lille, .
VSURF: An R Package for Variable Selection Using Random Forests
Robin Genuer, Jean-Michel Poggi e Christine Tuleau-Malot. Publicado em The R Journal, volume 7, edição 2, páginas 19–33, . DOI: 10.32614/RJ-2015-018.
O artigo revisado por pares explica a estratégia de seleção e sua implementação; o pacote torna o método diretamente utilizável em R.
Dra. Christine Malot
Publica na literatura de pesquisa sob seu nome completo, Christine Tuleau-Malot. Na DSTI, é copresidente, com o Pr Fabien Gandon, do Conselho Científico e Consultivo da DSTI.
Seu doutorado de , sobre seleção de variáveis para discriminação de alta dimensão e classificação de dados funcionais, foi orientado por Pr Jean-Michel Poggi. Seu trabalho posterior com Robin Genuer dá continuidade a essa relação de pesquisa por meio de um método estatístico, um artigo de software revisado por pares e o pacote VSURF.
Ela leciona Foundations of Statistical Analysis - Part 2 e Advanced Statistical Analysis no MSc in Data Science & AI, e Mathematics Harmonisation no BSc Computer Science & Engineering.
Random Forests for Big Data
Os quatro autores desenvolveram a contribuição da conferência em um artigo mais longo publicado em Big Data Research em . Ele expande a revisão e a discussão de variantes escalonáveis de florestas aleatórias.
No artigo da conferência, na extensão em periódico e no VSURF, o tema compartilhado é consistente: definições matemáticas, diagnósticos e escolhas de implementação pertencem a um único objeto de engenharia.
Nota editorial. Este artigo do DSTI TechBlog é uma interpretação educacional da pesquisa citada, escrita para a série “IA é matemática”. Não é apresentado como um artigo novo e não atribui a redação editorial aos pesquisadores. A notação matemática foi simplificada onde isso melhora a legibilidade; o artigo original continua sendo a fonte autoritativa.