Decomposição de posto tensorial

Em álgebra multilinear, a decomposição de posto tensorial ou decomposição poliádica canônica (CPD, na sigla em inglês), pode ser vista como uma generalização da decomposição em valores singulares (SVD) de matrizes para tensores, que tem aplicações em estatística, processamento de sinais, psicometria, linguística e quimiometria. Ela foi introduzida por Hitchcock, em 1927[1] e redescoberto mais tarde várias vezes, nomeadamente em psicometria.[2][3] Por esta razão, a decomposição de posto tensorial, às vezes, é historicamente conhecida como PARAFAC ou CANDECOMP.[3] or CANDECOMP.[2]

A decomposição de posto tensorial expressa um tensor como uma combinação linear de comprimento mínimo de tensores de posto 1. Tais tensores de posto 1 também são chamados simples ou puros. Um tensor puro é o produto tensorial de um conjunto de vetores.

Definição editar

Considere um espaço tensorial   em que   é o corpo dos reais   ou o corpo dos complexos   Todo tensor (de ordem  ) neste espaço pode então ser representado com um   suficientemente grande como uma combinação linear de   tensores de posto 1:

 

em que   e   observe que o índice   não deve ser interpretado como um expoente, é apenas mais um índice. Quando o número   de termos é o menor possível na expressão acima, então   é chamado de posto do tensor, e a decomposição é muitas vezes referida como uma decomposição de posto (tensorial), decomposição CP mínima, ou Decomposição Poliádica Canônica (CPD). Se, pelo contrário, o número de termos não é mínimo, então a decomposição acima é muitas vezes referida como uma decomposição de   termos, CANDECOMP/PARAFAC ou decomposição Poliádica.

Posto de um tensor editar

Diferentemente do que ocorre com matrizes, atualmente, o posto de um tensor não é bem compreendido. Sabe-se que o problema de calcular o posto de um tensor é NP-difícil.[4] Os únicos casos notáveis bem compreendidos , consistem dos tensores em   cuja ordem pode ser obtida a partir da forma normal de KroneckerWeierstrass do feixe de matrizes linear que o tensor representa.[5] Existe um algoritmo simples de tempo polinomial para certificar que um tensor é de posto 1, a saber, a decomposição em valores singulares de ordem superior.

O posto de um tensor de zeros é zero, por convenção. O posto de um tensor   é um, desde que  

Dependência do corpo editar

O posto de um tensor depende do corpo sobre o qual o tensor é decomposto. É conhecido que alguns tensores reais podem admitir uma decomposição complexa cujo posto é estritamente menor que o posto de uma decomposição real do mesmo tensor. Como um exemplo,[6] considere o seguinte tensor real

 

em que   Sabe-se que o posto deste tensor sobre os reais é igual a 3, enquanto que o seu posto sobre os complexos é apenas 2, porque ele é a soma de um tensor complexo de posto 1 com o seu conjugado complexo, a saber

 

em que  

Em contraste, o posto de matrizes reais nunca vai diminuir sob uma extensão de corpos para   o posto real e o posto complexo de matrizes coincidem para matrizes reais.

Posto genérico editar

O posto genérico   é definido como o menor posto   tal que o fecho na Topologia de Zariski de um conjunto de tensores de posto no máximo   é todo o espaço   No caso dos tensores complexos, os tensores de posto no máximo   formam um conjunto denso   todo tensor no espaço mencionado anteriormente tem o posto menor do que o posto genérico,  ou então ele é o limite na topologia euclidiana de uma sequência de tensores de   No caso de tensores reais, o conjunto dos tensores de posto no máximo   forma apenas um conjunto aberto de medida positiva na topologia euclidiana. Podem haver conjuntos abertos na topologia euclidiana, formados por tensores de posto estritamente maior do que o posto genérico. Todos os postos que aparecem nos conjuntos abertos na topologia euclidiana são chamados de postos típicos. O menor posto típico é chamado de posto genérico; esta definição se aplica tanto aos tensores reais quanto aos complexos. O posto genérico de espaços tensoriais foi estudado inicialmente em 1983 por Volker Strassen.[7]

Como uma ilustração dos conceitos acima, sabe-se que tanto 2 quanto 3 são postos típicos de   enquanto que o posto genérico de   é 2. Na prática, isso significa que um tensor real sorteado aleatoriamente (a partir de uma medida de probabilidade contínua no espaço dos tensores) de tamanho   será um tensor de posto 1 com probabilidade zero, um tensor de posto 2 com probabilidade positiva, e um tensor de posto 3 com probabilidade positiva. Por outro lado, um tensor complexo de mesmo tamanho, sorteado aleatoriamente, será um tensor de posto 1 com probabilidade zero, um tensor de posto 2 com probabilidade um, e um tensor de posto 3 tensor com probabilidade zero. Sabe-se também que um tensor real genérico de posto 3 em   igual a 2.

O posto genérico de espaços tensoriais depende da distinção entre espaços tensoriais balanceados e não balanceados. Um espaço tensorial   em que   é chamado não balanceado sempre que

 

e ele é chamado de balanceado caso contrário.

Espaços tensoriais não balanceados editar

Quando o primeiro fator é muito grande em relação aos outros fatores do produto tensorial, então o espaço tensorial se comporta essencialmente como um espaço matricial. Sabe-se que o posto genérico de tensores de espaços tensoriais não balanceados é

 

em quase toda parte. Mais precisamente, o posto de todo tensor em um espaço tensorial não balanceado   em que   é algum conjunto indeterminado fechado na topologia de Zariski, é igual ao valor referido acima.[8]

Espaços tensoriais balanceados editar

O posto genérico dos tensores de um espaço tensorial equilibrado é esperado ser igual a

 

em quase toda a parte para tensores complexos e em um conjunto aberto euclidiano para os tensores reais, em que

 

Mais precisamente, espera-se que o posto de cada tensor em   em que   é algum conjunto indeterminado fechado na topologia de Zariski, seja igual ao valor referido acima.[9] Para tensores reais,   é o posto mínimo que se espera ocorrer em um conjunto de medida Euclidiana positivo. O valor   é muitas vezes chamado de posto genérico esperado do espaço tensorial   porque apenas se conjectura que seja correto. Sabe-se que o posto genérico efetivo sempre satisfaz

 

A conjectura de Abo–Ottaviani–Peterson[9] afirma que a igualdade é esperada, isto é,   com os seguintes casos excepcionais:

  •  
  •  
  •  

Em cada um desses casos excepcionais, sabe-se que o posto genérico é   A conjectura foi provada completamente em um número de casos especiais. Em 1985, Lickteig mostrou que   desde que   [10] Em 2011, um grande avanço foi feito por Catalisano, Geramita, e Gimigliano que provaram que   exceto para o espaço   [11]

Posto máximo editar

O posto máximo que pode ser alcançado por qualquer dos tensores de um espaço tensorial é geralmente desconhecido; não há sequer uma uma conjectura sobre este posto máximo. Atualmente, a melhor cota superior indica que o posto máximo   de   em que   satisfaz

 

em que   é o (menor) posto genérico de   [12] É bem conhecido que a desigualdade anterior pode ser estrita. Por exemplo, o posto genérico de tensores em   é dois, de modo que a cota anterior fornece   enquanto se sabe que o posto máximo é igual a 3.[6]

Posto de fronteira editar

Um tensor   de posto   é chamado de tensor de fronteira se existe uma sequência de tensores de posto no máximo   cujo limite é   Se   é o menor valor para o qual existe uma sequência convergente nessas condições, então ele é chamado o posto de fronteira de   Para tensores de ordem 2, isto é, matrizes, o posto e o posto de fronteira sempre coincidem, no entanto, para tensores de ordem   eles podem ser diferentes. Tensores de fronteira foram primeiramente estudados no contexto de algoritmos de multiplicação de matrizes aproximada e rápida, por Bini, Lotti, e Romani em 1980.[13]

Um exemplo clássico de um tensor de fronteira é o tensor de posto 3

 

Ele pode ser aproximado arbitrariamente bem pela seguinte sequência de tensores de posto 2

 

quando   Portanto, o seu posto de fronteira vale 2, que é estritamente menor do que o seu posto. Quando os dois vetores são ortogonais, este exemplo também é conhecido como um estado W.

Propriedades editar

Identificabilidade editar

Segue da definição de um tensor puro que   se, e somente se, existe   tal que  e   para todo k. Por este motivo, os parâmetros   de um tensor   de posto 1 são chamados de identificáveis ou essencialmente únicos. Um tensor   de posto r é chamado de identificável se todas as suas decomposições de posto tensorial é a soma do mesmo conjunto de   tensores distintos   em que os  's são de posto 1. Um tensor identificável de posto   tem então apenas uma decomposição essencialmente única

 
e todas as outras   decomposições de posto tensoriais de   podem ser obtidas permutando a ordem das parcelas. Observe que em uma decomposição de posto tensorial todos os  's são distintos, caso contrário, o posto de   seria, no máximo,  

Tensores de ordem 2 em   isto é, matrizes, não são identificáveis para   Isto resulta, essencialmente, da constatação de que

 
em que   é uma matriz   inversível,       e   Pode ser demonstrado[14] que para todo   em que   é um conjunto fechado na topologia de Zariski, a decomposição do lado direito é uma soma de um conjunto de tensores de posto 1 diferente da decomposição do lado esquerdo, implicando que tensores de ordem 2 de posto   geralmente não são identificáveis.

A situação muda completamente para tensores de ordem superior em   com   e todos os   Por simplicidade de notação, suponha sem perda de generalidade, que os fatores são ordenados de tal forma que   Denote por   o conjunto de tensores de posto limitado por   Então, a seguinte afirmação mostrou-se correta, usando uma demonstração assistida por computador para todos os espaços de dimensão   [15] e conjectura-se que seja válida em geral:[15][16][17]

Existe um conjunto   fechado na topologia de Zariski, tal que cada tensor   é identificável (neste caso,   é dito genericamente identificável), a menos que ocorra uma das seguintes situações excepcionais:

  1. O posto é grande demais:  
  2. O espaço é identificavelmente não balanceado, isto é,   e o posto é grande demais:  
  3. O espaço é o caso defectivo   e o posto é  
  4. O espaço é o caso defectivo   em que   e o posto é  
  5. O espaço é   e o posto é  
  6. O espaço é   e o posto é   ou
  7. O espaço é   e o posto é  
  8. O espaço é perfeito, ou seja,   é um inteiro, e o posto é  

Nesses casos excepcionais, o número genérico (e mínimo) de decomposições complexas é

  • demonstrado ser   nos 4 primeiros casos;
  • demonstrado ser dois no caso 5;[18]
  • esperado[19] ser seis no caso 6;
  • demonstrado ser dois no caso 7;[20] e
  • esperado[19] ser pelo menos dois no caso 8, com exceção dos dois casos identificáveis   e  

Em resumo, espera-se que o tensor genérico de ordem   e posto   que não é desbalanceado por identificabilidade, seja identificável (módulo os casos excepcionais em espaços pequenos).

Mal condicionamento do problema de aproximação padrão editar

O problema da aproximação do posto busca a decomposição de posto   mais próxima (na topologia euclidiana usual) a algum tensor   de posto   em que   Isto é, procura-se resolver

 

em que   é a norma de Frobenius.

Foi demonstrado em um artigo de 2008, de Silva e Lim,[6] que o problema de aproximação padrão acima pode ser mal-posto. Uma solução para o referido problema pode, às vezes, não existir, pois o conjunto sobre o qual se faz a otimização não é fechado. Como tal, um minimizer pode não existir, mesmo que exista um ínfimo. Em particular, sabe-se que certos chamado tensores de fronteira podem ser aproximados arbitrariamente bem por uma seqüência de posto tensorial no máximo   mesmo que o limite da sequência seja um tensor de ordem estritamente superior a   O tensor de posto 3

 

pode ser aproximado arbitrariamente bem pela seguinte sequência de tensores de posto 2

 

quando   Este exemplo ilustra perfeitamente o princípio geral de que uma sequência de tensores de posto   que converge para um tensor de posto estritamente maior precisa admitir, pelo menos, dois termos individuais de posto 1 cujas normas se tornem ilimitadas. Mais precisamente, sempre que uma seqüência

 

tem a propriedade de que   (na topologia Euclidiana) quando   e, então, devem existir pelo menos   tais que

 

quando   Este fenômeno é encontrado frequentemente ao tentar aproximar um tensor utilizando algoritmos de otimização numérica. Às vezes é chamado de o problema das componentes divergentes. Além disso, foi demonstrado que um tensor aleatório de posto pequeno sobre os reais pode não admitir uma aproximação de posto 2 com probabilidade positiva, levando ao entendimento de que o mau condicionamento do problema é uma consideração importante quando se emprega a decomposição de posto tensorial.

Uma solução parcial comum para o problema do mal condicionamento consiste em impor uma restrição de desigualdade adicional que limita a norma dos termos de posto 1 individuais por alguma constante. Outras restrições que resultam em um conjunto fechado, e, consequentemente, em problemas de otimização bem posto, incluem a imposição de positividade ou de um produto interno limitado estritamente menor que a unidade entre os termos de posto 1 que aparecem na decomposição procurada.

O cálculo do CPD editar

Algoritmos alternantes:

  • mínimos quadrados alternantes (ALS)
  • diagonalização alternante por fatias (ASD)

Algoritmos algébricos:

  • diagonalização simultânea (SD)
  • decomposição de Schur simultânea generalizada (SGSD)

Algoritmos de otimização:

Métodos diretos:

  • Decomposição multilinear direta (DMLD)

Aplicações editar

Em aprendizado de máquina, a decomposição CP é o ingrediente central na aprendizagem de modelos de variáveis latentes probabilísticos através da técnica da correspondência de momento. Por exemplo, considere o modelo multi-modo de exibição,[21] que é um modelo de variáveis latentes probabilístico. Neste modelo, a geração de amostras é colocada da seguinte forma: existe uma variável aleatória oculta que não é observado diretamente, dado que, há várias variáveis aleatórias condicionalmente independentes conhecidas como os diferentes "pontos de vista" da variável oculta. Por simplicidade, suponha que há três vistas simétricas   de uma variável oculta categórica de  -estado   Então, o terceiro momento empírico desse modelo de variável latente pode ser escrito como:  

Em aplicações tais como a modelagem de tópicos, isto pode ser interpretado como a coocorrência de palavras em um documento. Então os autovalores do tensor de momento empírico podem ser interpretados como a probabilidade de escolha de um tema específico e cada coluna do fator matricial   corresponde às probabilidades das palavras no vocabulário, no tópico correspondente.

Ver também editar

  • Análise de classes latentes
  • Aprendizagem de subespaço multilinear
  • Decomposição em valores singulares
  • Decomposição de Tucker
  • Decomposição em valores singulares de ordem superior
  • Decomposição tensorial

Referências editar

  1. F. L. Hitchcock (1927). «The expression of a tensor or a polyadic as a sum of products». Journal of Mathematics and Physics. 6: 164–189 
  2. a b Carroll, J. D.; Chang, J. (1970). «Analysis of individual differences in multidimensional scaling via an n-way generalization of 'Eckart–Young' decomposition». Psychometrika. 35: 283–319. doi:10.1007/BF02310791 
  3. a b Harshman, Richard A. (1970). «Foundations of the PARAFAC procedure: Models and conditions for an "explanatory" multi-modal factor analysis» (PDF). Ann Arbor: University Microfilms. UCLA Working Papers in Phonetics. 16. 84 páginas. No. 10,085. Arquivado do original (PDF) em 10 de outubro de 2004 
  4. Hillar, C. J.; Lim, L. (2013). «Most tensor problems are NP-Hard». Journal of the ACM. 60. 45 páginas. arXiv:0911.1393 . doi:10.1145/2512329 
  5. Landsberg, J. M. (2012). Tensors: Geometry and Applications. [S.l.]: AMS 
  6. a b c de Silva, V.; Lim, L. (2008). «Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem». SIAM Journal on Matrix Analysis and Applications. 30: 1084–1127. doi:10.1137/06066518x 
  7. Strassen, V. (1983). «Rank and optimal computation of generic tensors». Linear Algebra and its Applications. 52/53: 645–685. doi:10.1016/0024-3795(83)80041-x 
  8. Catalisano, M. V.; Geramita, A. V.; Gimigliano, A. (2002). «Ranks of tensors, secant varieties of Segre varieties and fat points». Linear Algebra and its Applications. 355: 263–285. doi:10.1016/s0024-3795(02)00352-x 
  9. a b Abo, H.; Ottaviani, G.; Peterson, C. (2009). «Induction for secant varieties of Segre varieties». Transactions of the American Mathematical Society. 361: 767–792. arXiv:math/0607191 . doi:10.1090/s0002-9947-08-04725-9 
  10. Lickteig, Thomas (1985). «Typical tensorial rank». Linear Algebra and its Applications. 69: 95–120. doi:10.1016/0024-3795(85)90070-9 
  11. Catalisano, M. V.; Geramita, A. V.; Gimigliano, A. (2011). «Secant varieties of ℙ1 × ··· × ℙ1 (n-times) are not defective for n ≥ 5». Journal of Algebraic Geometry. 20: 295–327. doi:10.1090/s1056-3911-10-00537-0 
  12. Blehkerman, G.; Teitler, Z. (2014). «On maximum, typical and generic ranks». Mathematische Annalen. In press.: 1–11. arXiv:1402.2371 . doi:10.1007/s00208-014-1150-3 
  13. Bini, D.; Lotti, G.; Romani, F. (1980). «Approximate solutions for the bilinear form computational problem». SIAM Journal on Scientific Computing. 9: 692–697. doi:10.1137/0209053 
  14. Harris, Joe. Algebraic Geometry | SpringerLink (em inglês). [S.l.: s.n.] doi:10.1007/978-1-4757-2189-8 
  15. a b Chiantini, L.; Ottaviani, G.; Vannieuwenhoven, N. (1 de janeiro de 2014). «An Algorithm For Generic and Low-Rank Specific Identifiability of Complex Tensors». SIAM Journal on Matrix Analysis and Applications. 35 (4): 1265–1287. ISSN 0895-4798. doi:10.1137/140961389 
  16. Bocci, Cristiano; Chiantini, Luca; Ottaviani, Giorgio (1 de dezembro de 2014). «Refined methods for the identifiability of tensors». Annali di Matematica Pura ed Applicata (1923 -) (em inglês). 193 (6): 1691–1702. ISSN 0373-3114. doi:10.1007/s10231-013-0352-8 
  17. Chiantini, L.; Ottaviani, G.; Vannieuwenhoven, N. (1 de janeiro de 2017). «Effective Criteria for Specific Identifiability of Tensors and Forms». SIAM Journal on Matrix Analysis and Applications. 38 (2): 656–681. ISSN 0895-4798. doi:10.1137/16m1090132 
  18. Chiantini, L.; Ottaviani, G. (1 de janeiro de 2012). «On Generic Identifiability of 3-Tensors of Small Rank». SIAM Journal on Matrix Analysis and Applications. 33 (3): 1018–1037. ISSN 0895-4798. doi:10.1137/110829180 
  19. a b Hauenstein, J. D.; Oeding, L.; Ottaviani, G.; Sommese, A. J. «Homotopy techniques for tensor decomposition and perfect identifiability». J. Reine Angew. Math. 
  20. Bocci, Cristiano; Chiantini, Luca (2013). «On the identifiability of binary Segre products». Journal of Algebraic Geometry. 22 (1): 1–11. ISSN 1056-3911. doi:10.1090/s1056-3911-2011-00592-4 
  21. Anandkumar, Animashree; Ge, Rong; Hsu, Daniel; Kakade, Sham M; Telgarsky, Matus (2014). «Tensor decompositions for learning latent variable models». The Journal of Machine Learning Research. 15 (1): 2773–2832 

Leitura complementar editar

Ligações externas editar