Epsilon-Neighborhood Decision-Boundary Governed Estimation (EDGE) of 2D Black Box Classifier Functions

Título: Estimativa Governada por Vizinhança Épsilon da Fronteira de Decisão (EDGE) de Funções de Classificadores de Caixa Preta 2D

1. Problema

Em aplicações do mundo real críticas para a segurança e qualidade (como estabilidade de redes elétricas ou otimização de projetos), é fundamental caracterizar com precisão como os parâmetros do sistema variam antes de resultarem em estados indesejáveis. Isso envolve identificar a fronteira de decisão ($\partial S$) que separa estados "desejáveis" (interior, $S_1$) de "indesejáveis" (exterior, $S_0$).

O desafio principal surge em sistemas de caixa preta, onde não há uma expressão analítica explícita da função $f(x)$. Métodos existentes de estimativa de fronteira geralmente:

• Refinam estimativas amostrando iterativamente regiões de alta incerteza.
• Não oferecem garantias matemáticas de que a fronteira estimada esteja dentro de uma distância específica ($\epsilon$) da fronteira real.
• Realizam exploração desnecessária em regiões distantes da fronteira, reduzindo a eficiência amostral (crucial quando as avaliações da função são computacionalmente caras).
• Requerem ajuste de hiperparâmetros e sofrem com variabilidade estocástica.

O objetivo é desenvolver um algoritmo que localize a fronteira de decisão dentro de uma vizinhança $\epsilon$ definida pelo usuário, garantindo que o erro de localização seja controlado, maximizando a eficiência amostral e eliminando a necessidade de ajuste de hiperparâmetros.

2. Metodologia: Algoritmo EDGE

O artigo propõe o EDGE ($\epsilon$-Neighborhood Decision-Boundary Governed Estimation), um algoritmo agnóstico à função que utiliza o Teorema do Valor Intermediário (TVI) para garantir a localização da fronteira. O método opera em duas fases principais:

A. Inicialização e Localização Inicial (Bissecção)

1. Pré-requisito: O algoritmo requer a identificação de pelo menos um ponto interior ($x_{in} \in S_1$) e um ponto exterior ($x_{out} \in S_0$).
2. Procedimento de Bissecção: Utiliza-se um algoritmo de bissecção ao longo do segmento que conecta $x_{in}$ e $x_{out}$. O ponto médio é consultado repetidamente.
   • Se $f(\text{médio}) = 1$, o ponto é adicionado ao conjunto interior.
   • Se $f(\text{médio}) = 0$, o ponto é adicionado ao conjunto exterior.
   • O processo continua até que a distância entre os últimos pontos adicionados dos conjuntos interior e exterior seja menor que $\epsilon$. Isso garante que a fronteira real cruza o segmento entre esses dois pontos, situando-os dentro da vizinhança $\epsilon$.

B. Caminhada da Fronteira (Stepping)

Uma vez estabelecidos os pontos iniciais de referência ($\partial \tilde{S}^1_0$ e $\partial \tilde{S}^0_0$), o algoritmo "caminha" ao longo da fronteira:

1. Interseção de Círculos: Para cada par de pontos adjacentes (um interior e um exterior), traça-se círculos de raio $\epsilon$ centrados nesses pontos.
2. Seleção de Teste: Os pontos de interseção desses círculos são calculados. Um ponto de teste ($x_{test}$) é selecionado com base em um produto vetorial positivo (para manter a direção de varredura).
3. Consulta e Atualização: O ponto $x_{test}$ é consultado na função caixa preta.
   • Se $f(x_{test}) = 1$, ele é adicionado ao conjunto de aproximação interior ($\partial \tilde{S}^1$).
   • Se $f(x_{test}) = 0$, ele é adicionado ao conjunto de aproximação exterior ($\partial \tilde{S}^0$).
4. Contorno do Domínio: Se o ponto de teste cair fora do domínio definido ($X$), o algoritmo realiza uma caminhada ao longo da fronteira do domínio ($\partial X$) até encontrar um ponto que cruze a fronteira de decisão novamente, reiniciando a varredura.
5. Terminação: O processo para quando um ponto de teste retorna a uma distância $\epsilon$ de um dos pontos de inicialização, indicando que toda a extensão da fronteira foi coberta.

Eficiência Amostrais: Diferente de métodos adaptativos que exploram regiões inteiras, o EDGE garante 100% de eficiência amostral na fase de caminhada, pois cada ponto amostrado é estritamente adicionado aos conjuntos de aproximação da fronteira.

3. Contribuições Chave

• Garantia de Vizinhança $\epsilon$: O algoritmo fornece uma garantia matemática de que a fronteira estimada está contida dentro de uma distância $\epsilon$ da fronteira real, algo que métodos de aprendizado ativo (como SVM) não garantem.
• Eficiência Amostrais Superior: O método evita a exploração de regiões irrelevantes, focando apenas na vizinhança da fronteira. A complexidade de amostragem escala com $L/\epsilon$ (onde $L$ é o perímetro da fronteira), em contraste com métodos de grade que escalam com $1/\epsilon^2$.
• Agnóstico a Hiperparâmetros: Não requer ajuste de hiperparâmetros (como largura de kernel em SVM ou taxas de aprendizado), tornando-o robusto e fácil de aplicar em diversos sistemas.
• Agnóstico à Função: Funciona para qualquer função de caixa preta contínua, independentemente de sua não-linearidade interna.

4. Resultados e Avaliação

O desempenho do EDGE foi comparado com dois métodos de referência em três funções de teste não lineares (Rosenbrock, Goldenstein-Price e Beale) e em um estudo de caso de estabilidade de rede elétrica.

• Estudo de Caso (Rede Elétrica): Aplicado a um sistema de 5 barras da IEEE com fontes renováveis. O EDGE conseguiu delinear a fronteira de viabilidade (estabilidade da rede) com alta precisão, identificando faixas seguras de injeção de potência.
• Comparação com Grade (Grid Search): O método de grade simples garante a vizinhança $\epsilon$, mas é computacionalmente proibitivo. O EDGE alcançou precisão de aproximação (medida pela Distância Superficial Média - ASD) similar, mas com ordens de magnitude menos consultas de função.
  • Exemplo: Para a função Rosenbrock com $\epsilon=0.05$, o EDGE usou ~1.948 amostras, enquanto a grade exigiu ~58.081.
• Comparação com Aprendizado Ativo (ALB/SVM): O método baseado em SVM (Active Learning at the Boundaries) mostrou-se instável e dependente da inicialização aleatória.
  • O EDGE apresentou zero estocasticidade (resultados consistentes em repetições), enquanto o ALB variou significativamente.
  • O EDGE foi mais preciso (menor ASD) e muito mais rápido computacionalmente, evitando a complexidade $O(m^3)$ da inversão de matrizes de kernel do SVM.

Tabela de Desempenho (Resumo):

Métrica	EDGE	ALB (SVM)	Grade (Grid)
Garantia $\epsilon$	Sim	Não	Sim
Eficiência Amostrais	Alta (Ótima)	Média/Baixa	Muito Baixa
Estocasticidade	Nula	Alta	Nula
Tempo Computacional	Baixo	Alto (devido ao SVM)	Médio/Alto

5. Significado e Conclusão

O algoritmo EDGE representa um avanço significativo na estimativa de fronteiras de decisão para sistemas de caixa preta. Sua principal vantagem reside na capacidade de fornecer garantias rigorosas de erro ($\epsilon$) com mínimo custo computacional, superando tanto as abordagens de grade (ineficientes) quanto as de aprendizado de máquina ativo (instáveis e sem garantias de vizinhança).

A aplicação em problemas de engenharia crítica, como a estabilidade de redes elétricas com fontes renováveis, demonstra sua utilidade prática para tomada de decisões seguras. O trabalho sugere futuras extensões para problemas de classificação multiclasse e espaços de alta dimensão, além de sua potencial aplicação para enriquecer conjuntos de treinamento de SVMs com pontos de fronteira otimizados, reduzindo ainda mais a variabilidade estocástica nesses modelos.