Large-Scale Bayesian Tensor Reconstruction: An Approximate Message Passing Solution

Resumo Técnico: Reconstrução Tensorial Bayesiana em Larga Escala via CP-GAMP

Definição do Problema
A reconstrução tensorial, particularmente através da decomposição CANDECOMP/PARAFAC (CPD), é essencial para analisar dados de larga escala com estruturas complexas em campos que variam desde o processamento de sinais até a neurociência. Embora as estruturas Bayesianas ofereçam quantificação de incerteza fundamentada e aprendizado automático de hiperparâmetros, os métodos existentes enfrentam desafios significativos de escalabilidade. As abordagens tradicionais de Inferência Variacional (VI), embora mais rápidas que os métodos de amostragem, exigem inversões de matrizes de alta dimensão a cada iteração, tornando-as computacionalmente proibitivas para tensores de grande porte. Além disso, as soluções anteriores de Approximate Message Passing (AMP) para problemas de tensores ou ignoram a esparsidade consistente entre os fatores latentes (degradando o desempenho) ou falham em lidar com observações incompletas e aprendizado de hiperparâmetros (limitando a aplicabilidade no mundo real).

Metodologia
Os autores propõem o CP-GAMP (Tensor CPD Generalized Approximate Message Passing), um algoritmo Bayesiano escalável projetado para superar os gargalos computacionais da inversão de matrizes, lidando simultaneamente com dados incompletos e hiperparâmetros desconhecidos.

1. Fundamentação Algorítmica: O CP-GAMP é derivado do Loopy Belief Propagation (LBP) em um grafo de fator que representa o modelo de CPD do tensor. Para tornar tratáveis as integrais de alta dimensão, os autores empregam o Teorema do Limite Central (CLC) e aproximações de série de Taylor sob o limite de sistemas grandes. Isso transforma o algoritmo sum-product em uma estrutura de AMP generalizada, evitando inversões de matriz explícitas.
2. Lidando com Dados Incompletos: O algoritmo acomoda tensores incompletos (onde elementos estão ausentes) modelando o processo de observação com um tensor de indicador binário e ruído branco gaussiano aditivo (AWGN). A função de verossimilhança é adaptada para considerar entradas observadas e não observadas.
3. Aprendizado Automático de Hiperparâmetros:
   • Estimativa do Rank de CP: Para determinar automaticamente o rank do tensor, os autores introduzem um prior de Bernoulli-Gaussian (BG). Este prior indutor de esparsidade permite que o algoritmo elimine componentes desnecessários. O parâmetro de Bernoulli ($\lambda_r$), que dita a necessidade do $r$-ésimo componente de rank, é atualizado via uma rotina de Expectation-Maximization (EM).
   • Estimativa da Potência do Ruído: Uma atualização de EM também é derivada para aprender a potência do ruído ($v_w$) quando esta é desconhecida, um cenário comum em aplicações do mundo real.
4. Processo Iterativo: O núcleo do algoritmo atualiza iterativamente as mensagens entre os nós de variáveis (elementos das matrizes de fatores) e os nós de fatores (verossimilhanças e priors). Ele utiliza uma função de denoiser derivada do prior BG para computar médias e variâncias posteriores, realizando efetivamente a inferência conjunta dos fatores latentes e hiperparâmetros.

Principais Contribuições
O artigo delineia quatro contribuições primárias:

1. Algoritmo CP-GAMP: Um novo algoritmo baseado em GAMP capaz de lidar com funções de verossimilhança por componente, especificamente para tensores incompletos com AWGN. Ele é derivado utilizando aproximação gaussiana e expansões de série de Taylor.
2. Aprendizado Automático de Rank: A integração de um prior BG com uma rotina EM permite a estimativa automática do rank de CP sem conhecimento prévio, abordando uma limitação crítica nos métodos baseados em AMP existentes.
3. Aprendizado da Potência do Ruído: A derivação de uma regra de atualização EM permite que o algoritmo aprenda a potência do ruído dinamicamente, aumentando a robustez em cenários práticos.
4. Escalabilidade e Eficiência: O método é validado como reduzindo significativamente a complexidade computacional em comparação com os métodos de VI de última geração, mantendo a precisão da reconstrução.

Resultados Experimentais
A eficácia do CP-GAMP foi validada através de experimentos em dados sintéticos e tarefas de inpainting de imagens, comparando-o com o método de Decomposição de Tensores Bayesiano Variacional (FBCP) e o Tensor Completion AMP (TC-AMP).

• Dados Sintéticos: Em experimentos envolvendo tensores de rank-20 de $100 \times 100 \times 100$ com apenas 20% dos elementos observados, o CP-GAMP alcançou uma redução de 82,7% no tempo de execução em comparação ao FBCP. Manteve um desempenho de Erro Quadrático Médio Normalizado (NMSE) comparável ao FBCP e superou significativamente o TC-AMP, que sofreu com maior NMSE devido à sua incapacidade de considerar a esparsidade consistente.
• Inpainting de Imagem: Em tensores de imagem de $256 \times 256 \times 3$ com razões de observação de 30%, o CP-GAMP reduziu o tempo de execução em 56,3% em comparação ao FBCP. Alcançou o menor NMSE entre os métodos comparados, enquanto o TC-AMP foi mais rápido, mas sacrificou a qualidade da reconstrução.
• Escalabilidade: Os resultados demonstraram que, conforme as dimensões do tensor e os ranks de CP aumentavam, o CP-GAMP mantinha um perfil de tempo de execução inferior em comparação ao FBCP, confirmando sua escalabilidade.

Significância
O artigo afirma que o CP-GAMP fornece uma solução escalável para a reconstrução tensorial Bayesiana em larga escala. Ao eliminar a necessidade de inversões de matrizes de alta dimensão e integrar o aprendizado automático de hiperparâmetros (rank e potência do ruído), o algoritmo preenche a lacuna entre os benefícios teóricos da inferência Bayesiana e os requisitos práticos do processamento de conjuntos de dados grandes, incompletos e ruidosos. Os autores enfatizam que esta abordagem torna a quantificação de incerteza fundamentada e a seleção automática de modelos viáveis para aplicações do mundo real, onde os recursos computacionais e a completude dos dados são limitados.