Decomposição de posto tensorial

Fonte: testwiki
Saltar para a navegação Saltar para a pesquisa

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

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

𝒜=i=1rλi𝐚i1𝐚i2𝐚id,

em que λiF e 𝐚ikFnk; observe que o índice k não deve ser interpretado como um expoente, é apenas mais um índice. Quando o número r de termos é o menor possível na expressão acima, então r é 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 r termos, CANDECOMP/PARAFAC ou decomposição Poliádica.

Posto de um tensor

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 FmFnF2 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 𝐚1𝐚d é um, desde que 𝐚kFnk{0}.

Dependência do corpo

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

𝒜=𝐱1𝐱2𝐱3+𝐱1𝐲2𝐲3𝐲1𝐱2𝐲3+𝐲1𝐲2𝐱3,

em que 𝐱i,𝐲j2. 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

𝒜=12(𝐳¯1𝐳2𝐳¯3+𝐳1𝐳¯2𝐳3),

em que 𝐳k=𝐱k+i𝐲k.

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

O posto genérico r(n1,,nd) é definido como o menor posto r tal que o fecho na Topologia de Zariski de um conjunto de tensores de posto no máximo r é todo o espaço Fn1Fnd. No caso dos tensores complexos, os tensores de posto no máximo r(n1,,nd) formam um conjunto denso S: 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 S. No caso de tensores reais, o conjunto dos tensores de posto no máximo r(n1,,nd) 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 222 enquanto que o posto genérico de 222 é 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 2×2×2 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 222 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 Fn1Fnd, em que n1n2nd, é chamado não balanceado sempre que

n1>1+k=2dnkk=2d(nk1),

e ele é chamado de balanceado caso contrário.

Espaços tensoriais não balanceados

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 é

r(n1,,nd)=min{n1,k=2dnk}

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

Espaços tensoriais balanceados

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

rE(n1,,nd)=ΠΣ+1

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

Π=k=1dnkeΣ=k=1d(nk1).

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

r(n1,,nd)rE(n1,,nd).

A conjectura de Abo–Ottaviani–Peterson[9] afirma que a igualdade é esperada, isto é, r(n1,,nd)=rE(n1,,nd), com os seguintes casos excepcionais:

  • F4×4×3
  • F(2n+1)×(2n+1)×3 com n=1,2,
  • F(n+1)×(n+1)×2×2 com n=1,2,

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

Posto máximo

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 rM(n1,,nd) de Fn1Fnd, em que n1n2nd satisfaz

rM(n1,,nd)min{k=2dnk,2r(n1,,nd)},

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

Posto de fronteira

Um tensor 𝒜 de posto s é chamado de tensor de fronteira se existe uma sequência de tensores de posto no máximo r<s cujo limite é 𝒜. Se s é 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 3 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

𝒜=𝐮𝐮𝐯+𝐮𝐯𝐮+𝐯𝐮𝐮,com 𝐮=𝐯=1 e 𝐮,𝐯1.

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

𝒜n=n(𝐮+1n𝐯)(𝐮+1n𝐯)(𝐮+1n𝐯)n𝐮𝐮𝐮=𝐮𝐮𝐯+𝐮𝐯𝐮+𝐯𝐮𝐮+1n(𝐮𝐯𝐯+𝐯𝐮𝐯+𝐯𝐯𝐮)+1n2𝐯𝐯𝐯

quando n. 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

Identificabilidade

Segue da definição de um tensor puro que 𝒜=𝐚1𝐚2𝐚d=𝐛1𝐛2𝐛d se, e somente se, existe λk tal queλ1λ2λk=1 e 𝐚k=λk𝐛k para todo k. Por este motivo, os parâmetros {𝐚k}k=1d de um tensor 𝒜 de posto 1 são chamados de identificáveis ou essencialmente únicos. Um tensor 𝒜Fn1Fn2Fnd de posto r é chamado de identificável se todas as suas decomposições de posto tensorial é a soma do mesmo conjunto de r tensores distintos {𝒜1,𝒜2,,𝒜r} em que os 𝒜i's são de posto 1. Um tensor identificável de posto r tem então apenas uma decomposição essencialmente única 𝒜=i=1r𝒜i, e todas as outras r! 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 𝒜i's são distintos, caso contrário, o posto de 𝒜 seria, no máximo, r1.

Tensores de ordem 2 em Fn1Fn2Fn1×n2, isto é, matrizes, não são identificáveis para r>1. Isto resulta, essencialmente, da constatação de que 𝒜=i=1r𝐚i𝐛i=i=1r𝐚i𝐛iT=ABT=(AX1)(BXT)T=i=1r𝐜i𝐝iT=i=1r𝐜i𝐝i, em que XGLr(F) é uma matriz r×r inversível, A=[𝐚i]i=1r, B=[𝐛i]i=1r, AX1=[𝐜i]i=1r e BXT=[𝐝i]i=1r. Pode ser demonstrado[14] que para todo XGLn(F)Z, em que Z é 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 r>1 geralmente não são identificáveis.

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

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

  1. O posto é grande demais: r>rE(n1,n2,,nd);
  2. O espaço é identificavelmente não balanceado, isto é, n1>k=2dnkk=2d(nk1), e o posto é grande demais: rk=2dnkk=2d(nk1);
  3. O espaço é o caso defectivo F4F4F3 e o posto é r=5;
  4. O espaço é o caso defectivo FnFnF2F2, em que n2, e o posto é r=2n1;
  5. O espaço é F4F4F4 e o posto é r=6;
  6. O espaço é F6F6F3 e o posto é r=8; ou
  7. O espaço é F2F2F2F2F2 e o posto é r=5.
  8. O espaço é perfeito, ou seja, rE(n1,n2,,nd)=ΠΣ+1 é um inteiro, e o posto é r=rE(n1,n2,,nd).

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 F5F4F3 e F3F2F2F2.

Em resumo, espera-se que o tensor genérico de ordem d>2 e posto r<ΠΣ+1 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

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

min𝐚ikFnk𝒜i=1r𝐚i1𝐚i2𝐚idF,

em que F é 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 r, mesmo que o limite da sequência seja um tensor de ordem estritamente superior a r. O tensor de posto 3

𝒜=𝐮𝐮𝐯+𝐮𝐯𝐮+𝐯𝐮𝐮,com 𝐮=𝐯=1 e 𝐮,𝐯1

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

𝒜n=n(𝐮+1n𝐯)(𝐮+1n𝐯)(𝐮+1n𝐯)n𝐮𝐮𝐮

quando n. Este exemplo ilustra perfeitamente o princípio geral de que uma sequência de tensores de posto r 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

𝒜n=i=1r𝐚i,n1𝐚i,n2𝐚i,nd

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

𝐚i,n1𝐚i,n2𝐚i,ndF e 𝐚j,n1𝐚j,n2𝐚j,ndF

quando n. 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

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

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 x de uma variável oculta categórica de k-estado h. Então, o terceiro momento empírico desse modelo de variável latente pode ser escrito como: T=i=1kPr(h=i)E[x|h=i]3.

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 E[x|h=k] corresponde às probabilidades das palavras no vocabulário, no tópico correspondente.

Ver também

  • 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

Predefinição:Reflist

Leitura complementar

Ligações externas