Skip to content
Voltar aos resultados

Completude de Matriz

Proposto por
Emmanuel Candès & Benjamin Recht
Ano
2009
Tipo
Convex low-rank recovery
Família
Missing data

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

Completude de Matriz é uma técnica para recuperar uma matriz de baixo posto a partir de um subconjunto pequeno, possivelmente aleatório, de suas entradas.

Introduzida por Emmanuel Candès e Benjamin Recht em 2009, ela reformula o problema como minimização da norma nuclear — um substituto convexo para a minimização do posto — e fornece garantias teóricas de que a recuperação exata é alcançável quando as entradas são observadas uniformemente ao acaso e a matriz satisfaz uma condição de incoerência.

A intuição por trás do método

Imagine uma planilha parcialmente preenchida de avaliações de usuários-filmes onde a maioria das células está em branco. Se os dados subjacentes tiverem uma estrutura simples — digamos, o gosto é explicado por apenas alguns fatores latentes como preferência de gênero e época — então conhecer mesmo uma pequena fração das avaliações é suficiente para preencher o restante com confiança. A completude de matriz explora essa estrutura oculta de baixa dimensão, muito como completar um quebra-cabeça quando se sabe que a imagem tem apenas algumas formas distintas.

História

A completude de matriz emergiu da literatura de *compressed sensing*. Candès e Recht (2009) estabeleceram o primeiro teorema de recuperação exata via minimização da norma nuclear, seguido de perto pelo trabalho de Candès e Tao sobre o poder da incoerência. O método ganhou ampla atenção pública através da competição Netflix Prize, onde métodos de filtragem colaborativa de baixo posto alcançaram precisão de recomendação de ponta. Trabalhos subsequentes de Recht, Fazel e Parrilo conectaram a minimização da norma nuclear à regularização de norma de traço em aprendizado de máquina.

Quando usar

Use completude de matriz quando os dados podem ser organizados como uma matriz com entradas sistematicamente ausentes e há razão para acreditar que o sinal verdadeiro tem baixo posto — por exemplo, em sistemas de recomendação, genômica, análise de redes sociais e recuperação de imagens. As suposições chave são que as entradas estão ausentes ao acaso e a matriz satisfaz uma condição de incoerência. Não é apropriado para matrizes com ausência estruturada ou não aleatória, estrutura de posto muito alto, ou quando a suposição de baixo posto é injustificada. Alternativas incluem imputação MICE para dados ausentes em geral e NMF quando a não-negatividade é exigida.

Limitações e considerações

  • O custo computacional da programação semidefinida escala mal com as dimensões da matriz
  • A suposição de incoerência pode falhar em conjuntos de dados reais com ausência estruturada ou *outliers*
  • O desempenho degrada quando o posto verdadeiro não é muito menor que as dimensões da matriz
  • A minimização da norma nuclear pode ser sensível a ruído; variantes robustas adicionam complexidade adicional

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Recuperação exata comprovável sob condições brandas com um programa convexo de tempo polinomial
  • Lida com taxas muito altas de ausência quando a matriz é verdadeiramente de baixo posto
  • Nenhum conhecimento prévio do posto é necessário; a minimização da norma nuclear o encontra implicitamente
  • Fortes garantias teóricas fundamentadas na teoria de matrizes aleatórias e análise convexa

Aplicações

  • Filtragem colaborativa e sistemas de recomendação (previsão de avaliações de usuário-item)
  • Genômica e bioinformática (recuperação de matrizes de expressão gênica com medições ausentes)
  • Visão computacional (restauração de imagens e subtração de fundo de vídeo)
  • Localização de redes de sensores (recuperação de matrizes de posição a partir de medições parciais de distância)
  • Neurociência (completude de matrizes de conectividade funcional a partir de observações parciais de fMRI)

Como funciona

Como funciona

1

O algoritmo começa com uma matriz M cujas entradas são observadas apenas em um conjunto de índices Omega. Esses valores observados formam as restrições para o problema de recuperação. Assume-se que o padrão de esparsidade é amostrado uniformemente ao acaso, que é o cenário teórico no qual as garantias de recuperação exata são estabelecidas.

Fórmula
\text{Given } M \in \mathbb{R}^{n_1 \times n_2},\; \text{observe entries } \{M_{ij}\}_{(i,j)\in\Omega}
2

Como minimizar diretamente o posto de uma matriz é NP-difícil, Candès e Recht propõem minimizar a norma nuclear — a soma dos valores singulares — como um relaxamento convexo. A norma nuclear desempenha o mesmo papel para matrizes que a norma L1 desempenha para vetores em *compressed sensing*: ela promove soluções de baixo posto, mantendo o problema tratável via programação semidefinida.

Fórmula
\min_{X} \|X\|_* \quad \text{subject to} \quad X_{ij} = M_{ij},\; \forall (i,j)\in\Omega
3

Para que a recuperação seja possível, os vetores singulares da matriz verdadeira não devem estar muito alinhados com a base padrão, quantificado pelo parâmetro de incoerência mu. Matrizes que concentram sua energia em apenas algumas linhas ou colunas são incoerentes; matrizes altamente localizadas violam essa condição e não podem ser recuperadas de uma amostra aleatória, pois muita informação está codificada nas entradas não observadas.

Fórmula
\max_{i} \|U^\top e_i\|^2 \leq \frac{\mu r}{n_1},\quad \max_{j} \|V^\top e_j\|^2 \leq \frac{\mu r}{n_2}
4

Quando o número de entradas observadas excede um limiar proporcional a mu vezes o posto r vezes n log n, o minimizador do problema da norma nuclear recupera a matriz verdadeira exatamente com alta probabilidade. Este resultado mostra que o tamanho da amostra necessário é apenas um múltiplo polilogarítmico maior que os graus de liberdade intrínsecos de uma matriz de posto-r, tornando a abordagem teoricamente informacionalmente quase ótima.

Fórmula
\text{If } |\Omega| \geq C \cdot \mu r n \log n,\; \text{then } \hat{X} = M \text{ with high probability}

Erros comuns

  • Suposição de ausência aleatória uniforme quando observações reais são selecionadas pelo usuário ou enviesadas (por exemplo, apenas itens altamente avaliados são avaliados), o que viola o modelo teórico de amostragem
  • Negligência em verificar a condição de incoerência, levando a uma recuperação ruim mesmo com observações suficientes
  • Uso de minimização da norma nuclear sem escalonamento ou regularização no cenário ruidoso, onde a formulação de recuperação exata é inadequada
  • Confundir completude de matriz com heurísticas de fatoração de matriz: *alternating least squares* pode convergir para mínimos locais e carece das garantias de recuperação da minimização da norma nuclear

Perguntas frequentes

A minimização da norma nuclear é a única maneira de resolver a completude de matriz?

Não. *Alternating least squares* (ALS) e descida de gradiente em formas fatoradas (por exemplo, SGD em U e V tal que M ≈ UV^T) são amplamente utilizados na prática para escalabilidade. No entanto, essas abordagens não convexas carecem das garantias de recuperação exata da minimização da norma nuclear e podem convergir para mínimos locais sem inicialização cuidadosa.

Quanta informação é necessária para recuperação exata?

Candès e Recht mostraram que aproximadamente C·mu·r·n·log(n) entradas observadas são suficientes para uma matriz n×n de posto-r com parâmetro de incoerência mu. Na prática, isso significa que uma matriz de baixo posto pode frequentemente ser recuperada de uma amostra que é apenas um pequeno múltiplo de seus graus de liberdade intrínsecos, que é igual a r(2n−r) para uma matriz n×n.

O que é a condição de incoerência e por que ela importa?

A incoerência mede o quão espalhados os vetores singulares estão pela base coordenada. Uma matriz com vetores singulares concentrados — como uma matriz de posto 1 que é diferente de zero apenas em uma linha — armazena a maior parte de sua informação em um pequeno conjunto de entradas. Se essas entradas por acaso não forem observadas, a recuperação é impossível, independentemente de quantas outras entradas sejam conhecidas.

Métodos relacionados

Fontes

  1. Candès, E. J., & Recht, B. (2009). Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6), 717–772.

    Abrir referência DOI
    Copiado.