Nem toda inteligência artificial é uma rede neural. As florestas aleatórias são uma das demonstrações mais claras de que a aprendizado de máquina é uma construção matemática: a reamostragem altera os dados vistos por cada modelo, a aleatoriedade altera as decisões disponíveis para cada árvore e a agregação transforma muitos preditores instáveis num preditor robusto. Quando os dados se tornam demasiado grandes para uma máquina — ou chegam como um fluxo — cada parte dessa construção tem de 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 uma atração óbvia. 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. Ele descreve como distribuir o árvores. O big data muitas vezes nos obriga a distribuir o os próprios dados, e essas não são a mesma operação.
Desenhe uma amostra de bootstrap a partir dos dados de aprendizagem, 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 aprendizagem de n observações, uma amostra de bootstrap clássica contém n sorteios feitos com substituição. Algumas observações aparecem diversas vezes; outros não são selecionados. Esse padrão não é um detalhe de implementação. É um dos mecanismos matemáticos que cria diversidade entre as árvores.
À medida que o conjunto de dados cresce, o número de cópias de uma observação específica numa 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
Desenhe 12 vezes a partir 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. Do outro lado da floresta, todas as observações sã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 deixar de lado uma amostra de validação separada.
O mesmo mecanismo suporta a importância da variável de permutação. Pegue a amostra out-of-bag de uma árvore, embaralhe um preditor e meça quanto o erro aumenta. Se a destruição do relacionamento carregado por esse preditor prejudicar a previsão, a variável será 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 OOB e a importância da 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 partilhado por ambos os projetos de investigação — desenvolveram um procedimento de seleção de variáveis e disponibilizaram-no como VSURF, um pacote R distribuído através do 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 variável. VSURF mostra o quanto essas quantidades podem fazer quando são preservadas: elas classificam os preditores, identificam um nível de ruído baseado em dados, comparam florestas aninhadas e decidem se uma variável adicional melhora a previsão o suficiente para ser retida.
A seleção de variáveis depende da finalidade da análise
Retenha as variáveis fortemente relacionadas com a resposta, incluindo 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.
Importância média da permutação em florestas repetidas, estimar a variabilidade associada a preditores não informativos e remover variáveis abaixo do limite baseado em dados.
Compare florestas aninhadas construídas a partir das variáveis classificadas e retenha um modelo compacto cujo erro OOB permanece dentro da incerteza do melhor resultado observado.
Introduza variáveis classificadas sequencialmente e mantenha uma nova variável somente quando sua redução no erro OOB exceder um limite estimado a partir da cauda ruidosa.
library(VSURF)
selection <- VSURF(x = predictors, y = response)
summary(selection)O pacote operacionaliza a pesquisa de regressão e classificação supervisionada, incluindo configurações 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 pedaços contíguos para trabalhadores separados e cada floresta poderá aprender uma população diferente.
Partição contígua
Cada trabalhador recebe uma fatia localmente homogênea.
Partição aleatória ou estratificada
Cada trabalhador recebe uma mistura mais representativa.
Registros vizinhos no disco podem compartilhar atributos, portanto, pedaços 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 eu-fora de-n bootstrap depende fortemente de eu, que é difícil de ajustar dentro de um esquema distribuído simples.
Os trabalhadores perdem os índices globais de formação necessários para reconstruir o clássico erro OOB e a importância variável.
06Quando os dados nunca param, o experimento muda novamente
Num ambiente online, o aluno vê a observação atual, mas pode não reter todas as observações anteriores. A floresta deve ser atualizada conforme os dados chegam. As florestas aleatórias on-line revisadas pelos autores combinam bagging on-line de Poisson, árvores extremamente randomizadas e estatísticas de nós incrementais.
(xt, simt)
para cada árvore
ou teste 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 em dados posteriores, essa previsão antiga não pode ser recalculada a menos que a observação seja armazenada. A estimativa OOB on-line, portanto, não é idêntica à quantidade clássica do lote.
A importância variável é ainda mais difícil. A importância da permutação nos pede para embaralhar uma variável em uma amostra out-of-bag. Um fluxo descartado após o processamento não deixa nada para ser permutado. 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.
Construir tamanho nominal-n amostras de bootstrap apenas de m ≪ n observações distintas, mantendo a lógica de reamostragem e reduzindo a carga computacional.
Use famílias de árvores mais fortemente aleatórias, 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 sobre o erro OOB e a importância da variável, 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 as observações, os sistemas de streaming ainda esquecem a história 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 trabalhador realmente vê?
- Qual aleatoriedade é essencial para o estimador e qual é meramente computacional?
- Ainda podemos estimar o erro sem contaminar as observações do 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.
VSURF adiciona a lição complementar. Quando o erro OOB e a importância das variáveis são preservados cuidadosamente, 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
Publicado na literatura de pesquisa com seu nome completo, Christine Tuleau-Malot. Na DSTI, é copresidente, com o Pr Fabien Gandon, do Conselho Científico e Consultivo da DSTI.
Dela doutorado em seleção de variáveis para discriminação de alta dimensão e classificação de dados funcionais foi supervisionado por Pr Jean-Michel Poggi. Seu trabalho posterior com Robin Genuer dá continuidade a esse relacionamento de pesquisa por meio de um método estatístico, um artigo de software revisado por pares e o pacote VSURF.
Ela ensina Fundamentos da Análise Estatística - Parte 2 e Análise Estatística Avançada no MSc in Data Science & AI, e Harmonização Matemática no Licenciatura em Ciência da Computação e Engenharia.
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 documento da conferência, na extensão do periódico e no VSURF, o tema compartilhado é consistente: definições matemáticas, diagnósticos e opções de implementação pertencem a um objeto de engenharia.
Nota editorial. Este artigo 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 oficial.