Fitting Unknown Number of Hyperplanes with Manifold Optimization

Resumo Técnico: Ajuste de Número Desconhecido de Hipersplanos com Otimização em Variedades

Definição do Problema
O artigo aborda o desafio fundamental de ajustar um número desconhecido de hipersplanos a um conjunto de pontos de dados em um espaço de dimensão $d$. Este problema é caracterizado como não convexo, não diferenciável e com ordem de modelo desconhecida (o número de hipersplanos $m$). Abordagens existentes, incluindo algoritmos de agrupamento tradicionais (por exemplo, K-Means, DBSCAN) e variantes baseadas em RANSAC, frequentemente lutam com ótimos locais, falta de consistência geométrica em pontos de interseção ou falham em lidar com a natureza dinâmica das dimensões de entrada/saída inerente a configurações não supervisionadas. Além disso, métodos de aprendizado profundo enfrentam dificuldades devido a objetivos não diferenciáveis e à necessidade de dimensões de entrada/saída fixas.

Metodologia
Os autores propõem um novo framework baseado em Otimização em Variedades para superar essas limitações. A metodologia central envolve três componentes principais:

1. Reformulação do Problema e Representação em Variedade:

   • O problema é reformulado como uma tarefa de agrupamento não supervisionado onde os centros dos clusters são hipersplanos.
   • Para lidar com a restrição não convexa $\|n\|^2 = 1$ (onde $n$ é o vetor normal unitário de um hipersplano), os autores definem o espaço de busca como a variedade da esfera unitária $S^{dim-1}$.
   • Ao representar hipersplanos por meio de seus vetores normais unitários $n$ e parâmetros de distância $d$, a métrica de distância entre pontos e hipersplanos é linearizada, tornando a otimização baseada em gradiente tratável.

2. Algoritmo de Otimização em Variedade em Duas Etapas:
   A solução emprega um processo iterativo de duas fases (Algoritmo 1):

   • Fase I: Otimização Suave (EM Riemanniana): Esta etapa utiliza um framework de Expectation-Maximization (EM) Riemanniano. Em vez de suposições Gaussianas padrão, um kernel de cauda pesada (especificamente, distância inversa ao quadrado $1/D^2$) é usado para modelar probabilidades posteriores. Isso permite uma estimativa robusta das atribuições de ponto a hipersplano, resolvendo efetivamente ambiguidades onde pontos de dados estão próximos de hipersplanos que se intersectam. A otimização é realizada na variedade usando operações de retração para garantir que as atualizações permaneçam na esfera unitária.
   • Fase II: Refinamento Rígido: Uma vez que os pesos probabilísticos suaves convergem, eles degeneram em atribuições rígidas (cada ponto pertence a exatamente um cluster). Uma otimização em variedade sem ponderação é então realizada dentro de cada cluster para refinar os parâmetros geométricos ($n, d$) até um ótimo local preciso que satisfaça estritamente a definição geométrica.

3. Estratégia de Inicialização:
   Para abordar a ordem de modelo desconhecida e evitar ótimos locais pobres, os autores introduzem uma estratégia de estimativa de densidade projetada (Algoritmo 3). Este método seleciona incrementalmente hipersplanos iniciais amostrando vetores normais na variedade (usando parametrização trigonométrica para reduzir o espaço de estados) e identificando regiões densas de pontos. Esta estratégia visa facilitar a convergência global reduzindo significativamente o espaço de descrição de características e a complexidade de busca.

Contribuições Principais
O artigo reivindica as seguintes contribuições:

• Reformulação: Transformar o problema de ajuste de hipersplanos não diferenciável em um framework de agrupamento para eliminar a não diferenciabilidade.
• Representação em Variedade: Usar vetores normais unitários na variedade da esfera $S^{dim-1}$ para reduzir o espaço de estados e linearizar cálculos de distância.
• Design de Algoritmo: Propor um algoritmo de Otimização em Variedade em Duas Etapas que combina EM Riemanniana (para robustez e resolução de ambiguidades) com Refinamento Rígido (para precisão geométrica).
• Inicialização: Desenvolver um método para determinar hipersplanos potenciais e gerar valores iniciais, auxiliando na busca por ótimos globais.

Resultados Experimentais
Experimentos extensivos foram conduzidos em conjuntos de dados sintéticos 2D e 3D com números variados de hipersplanos e níveis de ruído.

• Desempenho: O "Pipeline Completo" proposto (Inicialização + Fase I + Fase II) superou consistentemente as linhas de base mais avançadas, incluindo Agrupamento Aglomerativo, K-Means, DBSCAN, GMM, RANSAC, PARSAC e SupeRANSAC.
• Métricas: O método alcançou resultados superiores em Custo Total (distância euclidiana agregada) e Erro do Hipersplano (precisão da estimativa de parâmetros). Notavelmente, enquanto algumas variantes do RANSAC performaram bem quando o número de hipersplanos era conhecido, elas degradaram-se significativamente no cenário não supervisionado (superestimando o número de hipersplanos). O método proposto recuperou com sucesso a ordem do modelo com alta precisão.
• Estudos de Ablação: Experimentos confirmaram que a combinação de Otimização Suave e Refinamento Rígido é crítica; usar qualquer uma das etapas isoladamente resultou em desempenho inferior. A estratégia de inicialização proposta também provou ser eficaz em comparação com amostragem aleatória.
• Escalabilidade: Testes de escalabilidade indicaram que o método mantém a optimalidade global à medida que o número de pontos aumenta, com o Erro do Hipersplano diminuindo à medida que a densidade dos dados melhora.

Significado e Reivindicações
O artigo posiciona este trabalho como uma solução para um desafio de longa data em aprendizado de máquina e geometria: ajustar um número desconhecido de hipersplanos sem depender de relaxações convexas ou heurísticas de busca global caras. Os autores afirmam que, ao aproveitar a estrutura geométrica dos dados através da otimização em variedades, seu método lida efetivamente com restrições não convexas e objetivos não diferenciáveis. O significado reside em fornecer um framework geometricamente consistente, robusto e preciso que supera as abordagens de agrupamento e baseadas em RANSAC existentes, particularmente em cenários envolvendo hipersplanos que se intersectam e ordens de modelo desconhecidas. Os autores reconhecem limitações quanto à dificuldade de distinguir hipersplanos quando seus vetores de características estão extremamente próximos, mas afirmam que seu método representa um avanço significativo em relação às linhas de base atuais.