An Iterative Geometric Approach to Optimizing Separating Hyperplanes

Resumo Técnico: Uma Abordagem Geométrica Iterativa para a Otimização de Hiperplanos de Separação

Definição do Problema
O artigo aborda o problema de computar o hiperplano de separação de margem máxima para um conjunto de dados com rótulos binários e linearmente separáveis. Isso é equivalente a resolver o problema de otimização de margem rígida (hard-margin) do SVM (Máquina de Vetores de Suporte), que é um programa quadrático convexo. Enquanto os solvers padrão (ex: SMO, métodos de ponto interior) resolvem este problema diretamente sobre todo o conjunto de dados, o artigo investiga um cenário específico: dado um hiperplano inicial, viável (mas não ótimo), de separação, é possível alcançar a solução ótima de forma mais eficiente através de uma sequência de refinamentos geométricos iterativos? O objetivo é melhorar a margem continuamente, mantendo estritamente a separabilidade linear em cada etapa.

Metodologia
O método proposto é um algoritmo iterativo que transforma um hiperplano de separação atual $H_i$ em um novo hiperplano $H_{i+1}$ com uma margem maior. O processo baseia-se em informações locais (o "conjunto ativo") em vez do conjunto de dados global. O algoritmo procede da seguinte forma:

1. Identificação do Conjunto Ativo: Para o hiperplano atual $H_i$, o algoritmo identifica o conjunto ativo $A_i$, composto pelas amostras de ambas as classes mais próximas do hiperplano.
2. Otimização Local: Um solver de SVM existente é aplicado exclusivamente ao conjunto ativo $A_i$ para computar seu hiperplano de separação de margem máxima local, denotado por $H^*_i$, com vetor normal $w^*_i$.
3. Verificação de Convergência: Se o hiperplano atual $H_i$ coincide com $H^*_i$, o algoritmo termina, pois prova-se que um hiperplano ótimo para seu conjunto ativo é globalmente ótimo (Lema 1).
4. Realinhamento Geométrico: Se $H_i \neq H^*_i$, o algoritmo realinha $H_i$ em direção a $H^*_i$. Isso é alcançado interpolando o vetor normal: $w_i(\alpha) = (1-\alpha)w_i + \alpha w^*_i$. A rotação ocorre em torno de um ponto de pivô $m$, definido como o ponto médio de um par selecionado de vetores de suporte de classes opostas de $A_i$.
5. Expansão da Margem e Bloqueio: O parâmetro $\alpha$ é aumentado de 0 para 1. Durante esta rotação, a margem em relação ao conjunto ativo aumenta de forma estritamente monotônica. No entanto, a rotação é restringida por "amostras de bloqueio" fora do conjunto ativo que possam cruzar os hiperplanos de margem. O algoritmo calcula o $\alpha$ máximo admissível ($\alpha_{actual}$) tal que nenhuma nova amostra viole a restrição de separação.
6. Iteração: O hiperplano é atualizado usando $\alpha_{actual}$. Se $\alpha_{actual} < 1$, uma nova amostra (ou conjunto de amostras) tornou-se ativa (uma "amostra de bloqueio"), e o processo se repete com o conjunto ativo atualizado. Se $\alpha_{actual} = 1$, o ótimo global é alcançado.

Principais Contribuições

• Técnica Geométrica Iterativa: O artigo introduz um novo algoritmo que decompõe o problema de otimização global em uma sequência de subproblemas menores definidos por conjuntos ativos. Diferente dos métodos tradicionais que minimizam uma função objetivo global, esta abordagem realiza transformações geométricas (rotações) do hiperplano para maximizar a margem.
• Achados Teóricos:
  • Otimalidade Local-Global: O artigo formaliza a condição de que, se um hiperplano de separação é ótimo em relação ao seu conjunto ativo, ele é globalmente ótimo.
  • Relação de Margem Geométrica: Deriva uma relação mostrando que a margem do hiperplano interpolado é proporcional ao cosseno do ângulo entre o vetor normal atual e o vetor normal ótimo do conjunto ativo ($\gamma(\alpha) = \gamma^* \cos \theta(\alpha)$).
  • Interpretação KKT: O trabalho fornece uma interpretação geométrica das condições de Karush–Kuhn–Tucker (KKT) no contexto de SVMs, ligando a separação de invólucros convexos projetados à otimalidade.
• Avaliação Experimental: O método foi implementado em Python usando NumPy e CVXPY e testado em pares de dígitos MNIST linearmente separáveis.

Resultados Experimentais
Os experimentos compararam o método de refinamento iterativo proposto contra um solver global de linha de base (CVXPY com OSQP) em pares de dígitos MNIST (variando de ~2.000 a ~12.000 amostras).

• Conjuntos de Dados Pequenos (~2.000 amostras): O método proposto foi mais lento que o solver global direto, exigindo aproximadamente 10 vezes mais tempo de computação em alguns casos. O overhead de resolver múltiplos subproblemas superou os benefícios.
• Conjuntos de Dados Grandes (~12.000 amostras): O método tornou-se competitivo. Quando o tempo para computar o hiperplano viável inicial foi incluído, o método foi mais rápido em 6 de 10 experimentos de conjunto de treinamento. Quando o hiperplano inicial foi assumido como pré-existente, a fase de refinamento sozinha superou a linha de base em 8 de 10 experimentos.
• Tamanho do Conjunto Ativo: Os conjuntos ativos permaneceram significativamente menores que o tamanho total do conjunto de dados (o tamanho médio do conjunto ativo foi aproximadamente metade do número de vetores de suporte), validando a estratégia de resolver subproblemas reduzidos.
• Convergência: O algoritmo atingiu consistentemente a solução ótima em todos os experimentos, com contagens de iteração variando de 84 a 778.

Significância e Alegações
O artigo alega que a abordagem proposta é particularmente benéfica em cenários onde encontrar um hiperplano de separação viável é computacionalmente mais fácil do que computar o ótimo diretamente, ou quando um hiperplano viável já está disponível. O método não substitui os solvers de SVM existentes, mas oferece um framework alternativo que explora a viabilidade e a geometria do conjunto ativo.

Os autores são modestos quanto à universalidade do método. Eles reconhecem que o método não supera a otimização direta em conjuntos de dados menores e que a complexidade computacional depende fortemente do solver escolhido para os subproblemas do conjunto ativo. Além disso, o artigo observa que questões teóricas permanecem abertas, especificamente sobre se a direção de realinhamento escolhida garante o aumento de margem mais rápido possível e se o método garante a terminação em um número finito de iterações para todos os casos. O trabalho é apresentado como uma perspectiva geométrica sobre a otimização de margem máxima que fornece novos insights sobre a relação entre ótimos locais e globais.