Novel GPU Boruta algorithms for feature selection from high-dimensional data

Resumo Técnico: Novos Algoritmos Boruta em GPU para Seleção de Características a partir de Dados de Alta Dimensionalidade

Declaração do Problema
A seleção de características é uma etapa crítica no desenvolvimento de modelos robustos de Inteligência Artificial para a Ciência (AI4S), particularmente em áreas como bioinformática e descoberta de materiais, onde os dados exibem alta dimensionalidade e correlações complexas entre características. Embora métodos de envoltório, como o algoritmo Boruta, sejam eficazes na identificação de características relevantes ao considerar interações entre características, eles sofrem de alta complexidade computacional. O algoritmo Boruta original, que depende de Florestas Aleatórias, possui uma complexidade de tempo proporcional ao produto de atributos e objetos, tornando-o ineficiente para conjuntos de dados em grande escala quando executado em plataformas baseadas em CPU. Essa ineficiência limita a aplicabilidade da seleção rigorosa de características na análise moderna de dados científicos de alta dimensionalidade.

Metodologia
Para abordar o gargalo computacional, os autores propõem duas variantes aceleradas por GPU do algoritmo Boruta, aproveitando a biblioteca cuML para implementação de Florestas Aleatórias em GPUs NVIDIA. Ambas as variantes mantêm a lógica central do algoritmo Boruta original — comparando a importância das características originais contra "características sombra" randomizadas —, mas diferem na forma como a importância das características é quantificada:

1. Boruta-TreeImp: Esta variante quantifica a importância das características com base na redução da impureza (impureza de Gini ou métricas similares) acumulada em todas as árvores da Floresta Aleatória. O algoritmo acelera a construção da Floresta Aleatória na GPU e calcula a importância percorrendo as estruturas das árvores para somar os valores de ganho.
2. Boruta-Permut: Esta variante quantifica a importância das características com base em permutação. Ela mede a mudança no erro de previsão do modelo (Erro Quadrático Médio para regressão; divergência KL para probabilidades de classificação) quando os valores das características são embaralhados aleatoriamente. Este método é implementado inteiramente na GPU para maximizar o paralelismo durante as fases de previsão e cálculo de perda.

Os autores fornecem uma análise de complexidade computacional, observando que, embora ambos os métodos sejam dominados pelo tempo de treinamento da Floresta Aleatória $O(M \cdot m \cdot n \cdot \log n)$, a paralelização em GPU reduz significativamente o tempo de relógio. Eles observam que o Boruta-TreeImp é geralmente mais eficiente para grandes conjuntos de características ($m$), enquanto o Boruta-Permut pode ser preferível para conjuntos de características menores, embora incorra em custos mais elevados devido à necessidade de $m$ previsões separadas por iteração.

Principais Contribuições

• Implementação em GPU: A adaptação bem-sucedida do método de envoltório Boruta para arquiteturas de GPU usando cuML, criando duas implementações distintas (TreeImp e Permut).
• Análise de Custo-Efetividade: Uma comparação rigorosa dos custos computacionais usando preços de aluguel de servidores em nuvem, demonstrando que a execução em GPU é significativamente mais barata do que a execução em CPU multinúcleo para essas tarefas.
• Comparação Algorítmica: Uma avaliação detalhada das compensações entre métricas de importância baseadas em impureza e baseadas em permutação dentro do framework Boruta acelerado.

Resultados Experimentais
Os autores avaliaram os algoritmos propostos em um conjunto de dados sintético autoconstruído e quatro conjuntos de dados públicos (CT, NEWS, ENERGY, MADELON), comparando-os com o Boruta original baseado em CPU (scikit-learn) e o algoritmo BorutaShap.

• Dados Sintéticos: Em um conjunto de dados com 10 características relevantes conhecidas e 40 características de ruído, tanto o Boruta quanto o Boruta-Permut identificaram corretamente todas as 10 características. O Boruta-TreeImp identificou corretamente 9, falhando em selecionar uma característica (feature-18) que entrou na função objetivo como uma raiz cúbica. Os autores atribuem isso à limitação conhecida da importância baseada em impureza, que pode superestimar a importância de características aleatórias, levando a uma seleção conservadora neste contexto específico.
• Viés e Multicolinearidade: Experimentos mostraram que o viés de amostra (amostras escassas para uma característica relevante) fez com que todos os algoritmos falhassem em selecionar essa característica. Na presença de multicolinearidade, o Boruta-Permut selecionou menos características redundantes linearmente correlacionadas em comparação com o Boruta original.
• Conjuntos de Dados Públicos: Através dos conjuntos de dados CT, NEWS, ENERGY e MADELON, as versões aceleradas por GPU mantiveram a eficácia na seleção de características comparável ao Boruta original (medida por métricas de desempenho do modelo como MSE, MAE, $R^2$ e Acurácia).
• Ganhos de Eficiência: A descoberta mais significativa foi a redução no tempo e no custo. Por exemplo, no conjunto de dados NEWS, o Boruta original levou ~22 minutos (custando ~$1,77), enquanto o Boruta-TreeImp levou ~7,5 minutos (custando ~$0,015). No conjunto de dados MADELON, o Boruta-TreeImp foi concluído em menos de 5 minutos a um custo de ~$0,01, comparado a ~10 minutos e ~$0,80 para o original.

Significado e Alegações
O artigo afirma que realizar a seleção de características Boruta em GPUs oferece uma solução eficaz e economicamente viável para análise de dados em grande escala. Os autores enfatizam que seus métodos "melhoram significativamente a eficiência computacional enquanto preservam a precisão da seleção de características comparável ao algoritmo Boruta original".

O estudo conclui modestamente que, embora a aceleração em GPU resolva o problema de escalabilidade, a escolha entre as duas variantes depende das características dos dados. Especificamente, eles observam que a versão baseada em impureza (Boruta-TreeImp) pode às vezes superestimar a importância de características sombra ou perder características com contribuições complexas e não lineares (como o exemplo da raiz cúbica), sugerindo que a versão baseada em permutação (Boruta-Permut) pode ser mais robusta em certos cenários, apesar da maior sobrecarga computacional. O trabalho posiciona esses algoritmos como um passo prático rumo à habilitação da engenharia de características rigorosa para modelos AI4S que lidam com conjuntos de dados massivos.