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
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
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}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\OmegaPara 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}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
Candès, E. J., & Recht, B. (2009). Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6), 717–772.
Abrir referência DOICopiado.