Resumo Técnico: Explicações Compostas Ótimas Garantidas para Neurônios

Declaração do Problema

Explicações compostas visam descrever o alinhamento espacial entre as ativações do campo receptivo de um neurônio e conceitos específicos (por exemplo, objetos, texturas) usando regras lógicas. O objetivo central é encontrar uma fórmula lógica $L$, composta por conceitos de um conjunto $L_1$, que maximize a Interseção sobre União (IoU) entre o mapa de ativação do neurônio e as anotações dos conceitos.

No entanto, o espaço de busca para todas as combinações possíveis de conceitos é combinatorialmente explosivo. A literatura anterior (por exemplo, Mu e Andreas, 2020) abordou isso restringindo o espaço de busca através de suposições estruturais e empregando busca em feixe. Embora a busca em feixe seja computacionalmente eficiente, ela não oferece garantia teórica de otimalidade. Consequentemente, permanece incerto se as explicações geradas são verdadeiramente os melhores alinhamentos possíveis ou meros ótimos locais, e o quanto elas se desviam da verdade fundamental. Essa incerteza limita a confiabilidade dos métodos atuais de interpretabilidade e impede o desenvolvimento de algoritmos que possam reduzir erros de aproximação.

Metodologia

Os autores propõem uma estrutura para calcular explicações compostas garantidamente ótimas sobre todo o espaço de estados definido por suposições padrão, sem sacrificar a viabilidade computacional. A metodologia consiste em três componentes principais:

1. Decomposição da Métrica IoU (dIoU)

O artigo introduz uma decomposição da pontuação IoU em quantidades fundamentais que governam a qualidade do alinhamento. Isso depende de três suposições:

• Suposição 1: Os conceitos em uma explicação são distintos.
• Suposição 2: Os conceitos são combinados incrementalmente.
• Suposição 3: Os operadores lógicos são preservadores de 00 (ou seja, não podem produzir um 1 a partir de dois 0s). Isso cobre operadores bit a bit padrão: OU ($\lor$), E ($\land$) e E NÃO ($\land \neg$).

O IoU é reformulado usando quatro conjuntos-chave derivados da matriz de ativação do neurônio $N$ e das matrizes de conceitos $M$:

• Único/Interseção ($I_U, I_C$): Locais onde o neurônio dispara em anotações de conceitos únicos ou comuns.
• Único/Extras ($E_U, E_C$): Locais onde o conceito é anotado, mas o neurônio não dispara.

Essa decomposição ($dIoU$) permite uma análise detalhada de como os operadores lógicos impactam o numerador (interseção) e o denominador (união) da pontuação IoU.

2. Estimativa Heurística

Para guiar a busca, os autores projetam uma heurística que estima o IoU máximo e mínimo possível para qualquer rótulo parcial $L$ e qualquer caminho potencial que estenda $L$ até o comprimento máximo $n$.

• Quantidades de Rótulo: A heurística estima o impacto de adicionar um conceito $k$ a um rótulo $L$ usando uma Matriz Disjunta para verificar sobreposições. Ela deriva limites para interseção e extras com base em se os operandos são disjuntos ou sobrepostos.
• Quantidades de Caminho: Para estimar o potencial de estender um rótulo ainda mais, o método utiliza vetores Top e Bott. Esses vetores armazenam as somas cumulativas dos $t$ valores mais altos e mais baixos para cada quantidade em todo o conjunto de dados, permitindo que o algoritmo estime as melhorias nos melhores e piores casos alcançáveis ao adicionar conceitos restantes.
• Cálculo Agregado vs. Amostragem: Para equilibrar precisão e eficiência, a heurística usa cálculos agregados (somando sobre o conjunto de dados) para poda inicial e gerenciamento da fronteira, enquanto reserva cálculos baseados em amostra (por imagem) para refinar estimativas de nós promissores.

3. Algoritmo de Busca Ótima

Os autores propõem um algoritmo de busca de melhor primeiro (Algoritmo 1) que garante otimalidade:

1. Inicialização: Calcular quantidades exatas para todos os conceitos atômicos e estimar caminhos usando a heurística.
2. Gerenciamento da Fronteira: Manter uma fila de prioridade de nós classificados por sua IoU máxima estimada ($dIoU_{max}$).
3. Poda: Podar dinamicamente a fronteira removendo nós cuja $dIoU_{max}$ caia abaixo do máximo global das estimativas mínimas ($MinIoU$) encontradas até o momento.
4. Expansão e Refinamento:
   • Remover o nó com a estimativa mais alta.
   • Se a estimativa for agregada, refiná-la para uma estimativa baseada em amostra.
   • Aplicar regras de equivalência lógica para reduzir redundância.
   • Se o nó for um rótulo final, calcular seu IoU exato. Se for o melhor novo, atualizar o melhor global e retropropagar quantidades exatas para atualizar estimativas de outros nós que compartilham sub-rótulos.
   • Se o nó não for final, expandi-lo concatenando todos os conceitos e operadores possíveis, reestimando limites e inserindo-os na fronteira.

O algoritmo é provado ser admissível (nunca subestima a IoU máxima possível) e completo, garantindo que encontre a solução globalmente ótima.

Contribuições Principais

1. Garantias Formais: Esta é a primeira estrutura a fornecer garantias teóricas de otimalidade para explicações compostas sobre todo o espaço de estados abrangido por suposições padrão.
2. Decomposição (dIoU): Uma decomposição inovadora da métrica IoU que identifica quantidades fundamentais que governam o alinhamento, permitindo uma caracterização precisa dos impactos dos operadores lógicos.
3. Algoritmo Ótimo: Um algoritmo de busca que calcula explicações ótimas em um tempo comparável à busca em feixe exaustiva, tornando viável a exploração de todo o espaço de estados.
4. Busca em Feixe Guiada por Heurística: Uma variante da busca em feixe guiada pela decomposição e heurística propostas, que iguala ou melhora o desempenho de tempo de execução anterior, oferecendo maior flexibilidade em hiperparâmetros.

Resultados

Os autores avaliaram seu método em modelos ResNet18, AlexNet e DenseNet161 treinados em Places365, usando três conjuntos de dados de complexidade variável (Cityscapes, Ade20K, Broden).

• Viabilidade: O algoritmo ótimo encontra com sucesso a solução ótima dentro de tempos de execução viáveis em todos os níveis de complexidade. Embora explore um espaço de estados maior do que a busca em feixe, seu tempo de execução permanece comparável à busca em feixe padrão (por exemplo, ~5768 segundos/unidade para alta complexidade versus ~5929 para busca em feixe padrão), enquanto uma busca em largura ingênua exigiria centenas de milhões de horas.
• Subotimalidade da Busca em Feixe: A análise revela que 10–40% das explicações anteriormente obtidas via busca em feixe são subótimas quando conceitos sobrepostos estão envolvidos.
  • Categoria 1 (Mais Comum): Explicações diferem tanto em conceitos quanto em IoU. A busca em feixe frequentemente falha em encontrar explicações envolvendo combinações complexas de E/E NÃO que descrevem unidades especializadas.
  • Categoria 2: Explicações compartilham conceitos, mas diferem na estrutura lógica, levando a diferentes pontuações IoU (por exemplo, ((A OU B) E C) vs ((A E C) OU B)).
  • Categoria 3: Explicações compartilham o mesmo IoU, mas diferem na estrutura. A busca em feixe pode produzir explicações "não verificadas" que dependem de conceitos disjuntos que nunca co-ocorrem, enquanto o algoritmo ótimo identifica o alinhamento correto.
• Desempenho da Heurística: A variante de busca em feixe guiada pela heurística proposta supera as linhas de base (MMESH, Feixe Padrão) em termos de estados visitados e escala mais efetivamente com o comprimento da explicação e o tamanho do feixe, exigindo menos memória, pois não precisa armazenar tensores espaciais para o cálculo da heurística.

Significado e Alegações

O artigo alega que identificar a solução ótima da verdade fundamental é crítico para:

1. Confiabilidade: Prevenir visões enganosas do comportamento do neurônio causadas por aproximações subótimas.
2. Caracterização de Conjuntos de Dados: Revelar propriedades não estudadas de conjuntos de dados se a busca em feixe convergir para o ótimo.
3. Desenvolvimento de Algoritmos: Fornecer um benchmark para orientar o desenvolvimento de novos algoritmos que reduzam erros de aproximação.

Os autores enfatizam que seu método não depende de informações espaciais (ao contrário do MMESH), tornando a heurística potencialmente aplicável em domínios além da visão computacional. Eles posicionam este trabalho como uma fundação teórica que preenche a lacuna entre a Dissecção de Rede (que encontra conceitos únicos ótimos) e Explicações Compostas (que anteriormente sacrificavam otimalidade pela complexidade). O artigo conclui observando que, embora o algoritmo ótimo seja um passo significativo, trabalho futuro é necessário para estender essas garantias a operadores não preservadores de 00 e outras arquiteturas como Transformers.