Modeling with Categorical Features via Exact Fusion and Sparsity Regularisation

Este artigo propõe um novo método de regressão linear para preditores categóricos de alta dimensão que combina fusão exata e regularização de esparsidade para agrupar níveis e selecionar variáveis, apresentando formulações de programação inteira mista, algoritmos exatos e aproximados, e garantias teóricas que demonstram superioridade sobre os métodos existentes.

O essencial

Imagine que você é um detetive tentando prever o futuro (neste caso, prever quantas bicicletas serão alugadas em uma cidade). Você tem muitas pistas, mas algumas delas são "caixas de categorias" gigantes.

Por exemplo, a pista "Dia da Semana" tem 7 caixas (Segunda, Terça... Domingo). A pista "Hora do Dia" tem 24 caixas. E a pista "Código de CEP" pode ter milhares de caixas!

O problema é que, se você tratar cada uma dessas caixas como algo totalmente único, seu modelo fica gigante, confuso e difícil de entender. É como tentar decorar o nome de cada um dos 8 bilhões de habitantes da Terra para prever o clima.

Os autores deste paper criaram uma nova ferramenta chamada ClusterLearn. Pense nela como um "Organizador Mágico de Caixas" que faz duas coisas incríveis ao mesmo tempo:

1. O Aglutinador (Fusão de Níveis)

Imagine que você está olhando para os dados de "Dia da Semana". Você percebe que Segunda, Terça e Quinta têm um comportamento muito parecido (muitas pessoas alugam bicicletas para ir trabalhar), enquanto Sábado e Domingo são parecidos entre si (poucas pessoas alugam, pois estão de folga).

A ferramenta antiga tratava "Segunda" e "Terça" como coisas totalmente diferentes. O ClusterLearn diz: "Ei, vocês são parecidos! Vamos colar as etiquetas de Segunda, Terça e Quinta em um único grupo chamado 'Dias de Trabalho'."

Isso é o que chamam de Fusão. Em vez de ter 7 coeficientes diferentes para os dias, o modelo cria apenas 2 grupos: "Dia de Trabalho" e "Fim de Semana". Isso simplifica a história e torna o modelo mais inteligente.

2. O Cortador de Gordura (Esparsidade)

Agora, imagine que você tem uma pista chamada "Código de CEP" com 10.000 caixas. O modelo percebe que 9.900 desses CEPs não têm nenhuma influência real no aluguel de bicicletas. Eles são apenas "ruído".

A ferramenta ClusterLearn pega um par de tesouras e diz: "Corta! Vamos zerar esses 9.900 CEPs. Eles não importam."

Isso é a Esparsidade. O modelo foca apenas no que realmente importa, descartando o resto.

Como eles fazem isso? (A Mágica por trás do Truque)

A parte genial do paper é como eles fazem essa organização.

• A Abordagem Antiga (SCOPE): Era como tentar adivinhar o melhor agrupamento chutando e ajustando. Funcionava bem, mas às vezes você ficava preso em uma solução "ok", mas não na melhor possível. Era como tentar organizar uma bagunça de brinquedos olhando apenas para o que está na sua frente.
• A Abordagem Nova (ClusterLearn): Eles transformaram o problema em um Quebra-Cabeça Matemático Perfeito (chamado Programação Inteira Mista).
  • Eles criaram um algoritmo que garante que, se o computador tiver tempo suficiente, ele encontrará a melhor organização possível de todas as caixas, sem deixar nada de fora. É como ter um robô que prova matematicamente que aquela é a única maneira perfeita de organizar os brinquedos.
  • Para problemas muito grandes, eles criaram um "atalho inteligente" (um algoritmo aproximado) que chega muito perto da perfeição em segundos, como um especialista que dá uma olhada rápida e diz: "Quase certeza que essa é a melhor organização".

Por que isso é importante para você?

1. Modelos Menores e Mais Rápidos: Em vez de um modelo gigante que trava seu computador, você tem um modelo enxuto que roda rápido.
2. Interpretação Humana: Em vez de dizer "O CEP 12345 aumenta o aluguel em 0,05 e o CEP 12346 aumenta em 0,06", o modelo diz: "Bairros do centro têm mais aluguel". Isso é muito mais fácil para um humano entender e confiar.
3. Precisão: Ao agrupar coisas parecidas e ignorar o que não importa, o modelo comete menos erros de previsão do que os métodos atuais.

Resumo da Ópera

Pense no ClusterLearn como um chef de cozinha que recebe 100 ingredientes diferentes.

• O chef antigo tentava usar cada ingrediente de uma forma única, criando pratos complexos e confusos.
• O ClusterLearn olha para os ingredientes, percebe que "tomate", "pimentão" e "cebola" são todos vegetais que funcionam bem juntos, e cria um "Mix de Vegetais". Ele também joga fora o "sal de rocha" que não tem gosto nenhum.
• O resultado? Um prato (modelo) mais saboroso (preciso), mais fácil de explicar e feito com menos esforço.

Os autores provaram matematicamente que essa abordagem funciona e mostraram, com dados reais (como aluguel de bicicletas e seguros de vida), que eles conseguem prever o futuro com mais clareza do que os melhores métodos que existiam antes.

Resumo técnico

Resumo Técnico: Modelagem com Características Categóricas via Fusão Exata e Regularização de Esparsidade

1. Problema Abordado

O artigo foca no problema de regressão linear de alta dimensão onde os preditores incluem variáveis categóricas nominais com um grande número de níveis (categorias).

• Contexto: Em aplicações do mundo real (ex: códigos de CEP, marcas de veículos, códigos de diagnóstico), variáveis categóricas podem ter centenas ou milhares de níveis.
• Desafio: Modelos tradicionais (como Lasso) tratam cada nível como uma variável binária independente, o que pode levar a modelos com excesso de parâmetros, baixa interpretabilidade e sobreajuste.
• Objetivo: Desenvolver um estimador que realize duas tarefas simultaneamente:
  1. Fusão (Clustering): Agrupar níveis de uma mesma variável categórica que possuem efeitos semelhantes na resposta, reduzindo o número de coeficientes distintos.
  2. Esparsidade: Selecionar apenas as variáveis e níveis relevantes, zerando coeficientes desnecessários.

2. Metodologia Proposta: ClusterLearn-L0

Os autores propõem um novo estimador baseado em otimização discreta, denominado ClusterLearn-L0.

Formulação do Modelo:
O estimador minimiza uma função de perda de mínimos quadrados penalizada:
$$(\hat{\alpha}, \hat{\beta}) \in \arg\min_{\alpha, \beta} \frac{1}{n}\|y - \alpha\mathbf{1} - X\beta\|_2^2 + \lambda_0 \|\beta\|_0 + \lambda \sum_{j=1}^{q} |\{\beta_k : k \in I_j\}|$$
Onde:

• $\|\beta\|_0$: Penalidade de esparsidade (contagem de coeficientes não nulos).
• $\sum |\{\beta_k : k \in I_j\}|$: Penalidade de fusão (contagem de valores distintos de coeficientes para cada variável categórica $j$).
• $\lambda_0$ e $\lambda$: Parâmetros de ajuste que controlam a esparsidade e a fusão, respectivamente.

Abordagem de Otimização:
Diferente de métodos aproximados anteriores, os autores formulam o problema como um Programa Inteiro Misto (MIP):

• Variáveis Binárias: Utilizam variáveis binárias para codificar tanto o padrão de esparsidade quanto o padrão de agrupamento (fusão) dos coeficientes.
• Solução Exata: O problema é resolvido globalmente usando solvers MIP comerciais (como Gurobi), garantindo otimalidade global para instâncias de tamanho moderado.
• Geração de Linhas (Row Generation): Para lidar com a complexidade computacional (devido ao número quadrático de restrições de fusão), desenvolvem um algoritmo personalizado de geração de linhas. Ele começa com um subconjunto de restrições e adiciona-as iterativamente conforme necessário, acelerando significativamente a convergência em comparação com solvers "off-the-shelf".

Algoritmos Aproximados:
Para problemas de grande escala onde a solução exata é inviável, propõem um algoritmo de Descida Coordenada de Blocos (BCD):

• Decomposição Univariate: O problema de otimização para cada bloco de variáveis (uma variável categórica de cada vez) é reduzido a um problema univariado.
• Programação Dinâmica (DP): Desenvolvem um algoritmo exato baseado em DP para resolver o subproblema univariado (fusão e esparsidade simultâneas), que é o bloco construtor principal do BCD. Este algoritmo é uma extensão do trabalho de Johnson (2013) sobre segmentação de sinais, adaptado para lidar com a penalidade $\ell_0$ não convexa.
• Extensão: O método é estendido para classificação binária usando perda logística.

3. Principais Contribuições

1. Formulação MIP Exata: Primeira formulação MIP para regressão linear com fusão de níveis categóricos e esparsidade simultâneas, permitindo encontrar soluções globalmente ótimas.
2. Algoritmos Eficientes:
   • Desenvolvimento de um procedimento de geração de linhas para acelerar solvers exatos.
   • Criação de um algoritmo exato de Programação Dinâmica para o caso univariado, que serve como motor para o algoritmo aproximado BCD.
   • O algoritmo aproximado BCD é até 500 vezes mais rápido que o estado da arte (SCOPE) em certos cenários de grande escala.
3. Garantias Teóricas:
   • Limites de Erro de Previsão: Estabelecem limites superiores para o erro de previsão que dependem do número de clusters e da esparsidade. Mostram que o erro pode ser tão baixo quanto $O(\frac{\sigma^2 s^* \log(q)}{n})$ em certos cenários, onde $q$ é o número de preditores categóricos (melhor que a dependência em $p$, o número total de níveis).
   • Recuperação de Clusters: Provam que, sob condições de separação mínima entre os coeficientes verdadeiros, o estimador recupera o padrão de agrupamento correto com alta probabilidade.
4. Comparação com o Estado da Arte: O método supera o SCOPE (Stokell et al., 2021), que é o método atual de ponta, tanto em precisão de previsão quanto em recuperação de clusters, além de oferecer certificação de otimalidade.

4. Resultados Numéricos

Os autores realizaram experimentos extensivos em dados sintéticos e reais:

• Dados Sintéticos:

  • O ClusterLearn-L0 demonstrou superioridade em métricas de $R^2$ (desempenho de previsão) e pureza de clusters (capacidade de agrupar corretamente) em comparação com Elastic Net, IHT e SCOPE.
  • Em cenários de alta dimensão, o método aproximado escalou para problemas com milhares de variáveis ($p \approx 4500$) em segundos, enquanto o SCOPE foi significativamente mais lento.
  • O algoritmo exato com geração de linhas conseguiu obter certificados de otimalidade (gap < 0.5%) em problemas com $p \approx 4500$ em cerca de 15 minutos em um laptop.

• Dados Reais:

  • Bike Sharing (UCI): O ClusterLearn-L0 obteve a melhor $R^2$ no conjunto de teste (0.532) e um número reduzido de níveis de coeficientes, superando o SCOPE e o Elastic Net.
  • Seguro de Vida (Prudential): Em um problema de classificação binária, o método alcançou a maior acurácia (0.6908) com um número de níveis de coeficientes menor que o Elastic Net e competitivo com o SCOPE, mas com tempo de execução muito inferior.
  • Acesso de Funcionários (Amazon): O método manteve alta acurácia com um modelo mais compacto e rápido que o SCOPE.

5. Significado e Impacto

Este trabalho é significativo por várias razões:

• Interpretabilidade: Ao forçar a fusão de níveis categóricos, o modelo torna-se mais interpretável para especialistas de domínio (ex: agrupar códigos de diagnóstico semelhantes em vez de tratar cada um isoladamente).
• Eficiência Computacional: A combinação de formulação MIP exata com heurísticas de geração de linhas e algoritmos aproximados rápidos preenche a lacuna entre a necessidade de soluções globais ótimas e a escalabilidade para grandes conjuntos de dados.
• Fundamentação Teórica: Fornece as primeiras garantias teóricas rigorosas para a recuperação de clusters em regressão linear com preditores categóricos de alta dimensão, estabelecendo limites de separação minimax ótimos.
• Flexibilidade: O framework permite o controle direto sobre o número de clusters e a esparsidade, oferecendo uma ferramenta versátil para modelagem estatística moderna.

Em resumo, o artigo apresenta uma abordagem robusta e teoricamente fundamentada para lidar com a complexidade de variáveis categóricas de alta cardinalidade, superando os métodos existentes em precisão, eficiência e capacidade de fornecer soluções ótimas verificáveis.