En álgebra multilineal , la descomposición rango tensor o descomposición poliádico canónica (CPD) es una generalización de la matriz de la descomposición de valor singular (SVD) para tensores , que han encontrado aplicación en estadísticas , procesamiento de señales , la visión por ordenador , gráficos de ordenador , psicometría , lingüística y quimiometría . La descomposición del rango tensorial fue introducida por Hitchcock en 1927 [1] y luego redescubierta varias veces, notablemente en psicometría. [2][3] Por esta razón, la descomposición del rango tensorial a menudo se conoce como CANDECOMP, [2] PARAFAC, [3] o CANDECOMP / PARAFAC (CP).
Otra generalización popular de la matriz SVD se conoce como descomposición de valores singulares de orden superior .
Notación
Una variable escalar se denota con letras minúsculas en cursiva, y un escalar constante se denota con una letra cursiva mayúscula, .
Los índices se indican mediante una combinación de letras cursivas en minúsculas y mayúsculas, . Los índices múltiples que uno podría encontrar al referirse a los modos múltiples de un tensor se denotan convenientemente por dónde .
Un vector se denota con una letra mayúscula en negrita Times Roman, y una matriz se indica con letras mayúsculas en negrita .
Un tensor de orden superior se denota con letras caligráficas,. Un elemento de un-tensor de orden se denota por o .
Definición
Un tensor es una transformación multilineal que asigna un conjunto de espacios vectoriales a otro espacio vectorial. Un tensor de datos es una colección de observaciones multivariadas organizadas en una matriz de M vías.
Considere un tensor de datos , dónde es el campo real o el campo complejo . Cada (orden-, se refiere al número de modos) el tensor en este espacio puede entonces representarse con un como una combinación lineal de tensores de rango 1:
dónde y dónde . Cuando el número de términos es mínimo en la expresión anterior, entonces se denomina rango del tensor, y la descomposición a menudo se denomina descomposición de rango (tensor) , descomposición mínima de CP o descomposición poliadica canónica (CPD) . Por el contrario, si el número de términos no es mínimo, a menudo se hace referencia a la descomposición anterior como-term descomposición , CANDECOMP / PARAFAC o descomposición poliádicos .
Rango de tensor
Al contrario que en el caso de las matrices, actualmente no se comprende bien el rango de un tensor. Se sabe que el problema de calcular el rango de un tensor es NP-duro . [4] El único caso notable bien entendido consiste en tensores en, cuyo rango se puede obtener de la forma normal de Kronecker - Weierstrass del lápiz de matriz lineal que representa el tensor. [5] Existe un algoritmo simple de tiempo polinomial para certificar que un tensor es de rango 1, es decir, la descomposición de valores singulares de orden superior .
El rango del tensor de ceros es cero por convención. El rango de un tensor es uno, siempre que .
Dependencia de campo
El rango de un tensor depende del campo sobre el que se descompone el tensor. Se sabe que algunos tensores reales pueden admitir una descomposición compleja cuyo rango es estrictamente menor que el rango de una descomposición real del mismo tensor. Como ejemplo, [6] considere el siguiente tensor real
dónde . Se sabe que el rango de este tensor sobre los reales es 3, mientras que su rango complejo es solo 2 porque es la suma de un tensor complejo de rango 1 con su conjugado complejo , a saber
dónde .
En contraste, el rango de matrices reales nunca disminuirá bajo una extensión de campo a: el rango de la matriz real y el rango de la matriz compleja coinciden para las matrices reales.
Rango genérico
El rango genérico se define como el menor rango tal que el cierre en la topología de Zariski del conjunto de tensores de rango como máximo es todo el espacio . En el caso de tensores complejos, tensores de rango como máximoformar un conjunto denso : cada tensor en el espacio antes mencionado es de rango menor que el rango genérico, o es el límite en la topología euclidiana de una secuencia de tensores de. En el caso de tensores reales, el conjunto de tensores de rango como máximosólo forma un conjunto abierto de medida positiva en la topología euclidiana. Pueden existir conjuntos de tensores abiertos euclidianos de rango estrictamente superior al rango genérico. Todos los rangos que aparecen en conjuntos abiertos en la topología euclidiana se denominan rangos típicos . El rango típico más pequeño se llama rango genérico; esta definición se aplica tanto a tensores complejos como reales. El rango genérico de los espacios tensoriales fue estudiado inicialmente en 1983 por Volker Strassen . [7]
Como ilustración de los conceptos anteriores, se sabe que tanto el 2 como el 3 son rangos típicos de mientras que el rango genérico de es 2. Prácticamente, esto significa que un tensor real muestreado al azar (de una medida de probabilidad continua en el espacio de tensores) de tamaño será un tensor de rango 1 con probabilidad cero, un tensor de rango 2 con probabilidad positiva y un tensor de rango 3 con probabilidad positiva. Por otro lado, un tensor complejo muestreado al azar del mismo tamaño será un tensor de rango 1 con probabilidad cero, un tensor de rango 2 con probabilidad uno y un tensor de rango 3 con probabilidad cero. Incluso se sabe que el tensor real genérico de rango 3 en será de rango complejo igual a 2.
El rango genérico de los espacios tensoriales depende de la distinción entre espacios tensoriales equilibrados y no equilibrados. Un espacio tensorial, dónde , se llama desequilibrado siempre que
y se llama equilibrado de otra manera.
Espacios tensoriales desequilibrados
Cuando el primer factor es muy grande con respecto a los otros factores en el producto tensorial, entonces el espacio tensorial se comporta esencialmente como un espacio matricial. Se sabe que el rango genérico de tensores que viven en espacios tensoriales desequilibrados es igual a
casi en todas partes . Más precisamente, el rango de cada tensor en un espacio tensorial desequilibrado, dónde es un conjunto cerrado indeterminado en la topología de Zariski, es igual al valor anterior. [8]
Espacios tensoriales equilibrados
El rango genérico esperado de tensores que viven en un espacio tensorial equilibrado es igual a
casi en todas partes para tensores complejos y en un conjunto abierto euclidiano para tensores reales, donde
Más precisamente, el rango de cada tensor en , dónde es un conjunto cerrado indeterminado en la topología de Zariski , se espera que sea igual al valor anterior. [9] Para tensores reales,es el rango mínimo que se espera que ocurra en un conjunto de medidas euclidianas positivas. El valorse refiere a menudo como el rango genérico esperado del espacio tensorialporque solo es correcto conjeturas. Se sabe que el verdadero rango genérico siempre satisface
La conjetura de Abo-Ottaviani-Peterson [9] establece que se espera igualdad, es decir,, con los siguientes casos excepcionales:
En cada uno de estos casos excepcionales, se sabe que el rango genérico es . Tenga en cuenta que mientras que el conjunto de tensores de rango 3 en es defectuoso (13 y no el esperado 14), el rango genérico en ese espacio sigue siendo el esperado, 4.
La conjetura de AOP se ha probado completamente en varios casos especiales. Lickteig demostró ya en 1985 que, siempre que . [10] En 2011, Catalisano, Geramita y Gimigliano establecieron un gran avance, quienes demostraron que la dimensión esperada del conjunto de rangos tensores de formato es el esperado excepto para tensores de rango 3 en el caso de 4 factores, sin embargo, el rango esperado en ese caso sigue siendo 4. Como consecuencia, para todos los tensores binarios. [11]
Rango máximo
En general, se desconoce el rango máximo que puede admitir cualquiera de los tensores en un espacio tensorial; incluso falta una conjetura sobre este rango máximo. Actualmente, el mejor límite superior general establece que el rango máximo de , dónde , satisface
dónde es el rango (menos) genérico de. [12] Es bien sabido que la desigualdad anterior puede ser estricta. Por ejemplo, el rango genérico de tensores en es dos, de modo que el límite anterior produce , si bien se sabe que el rango máximo es igual a 3. [6]
Rango fronterizo
Un rango- tensor se llama tensor de borde si existe una secuencia de tensores de rango como máximo cuyo límite es . Sies el valor mínimo para el que existe tal secuencia convergente, entonces se llama rango de borde de. Para tensores de orden 2, es decir, matrices, el rango y el rango de borde siempre coinciden, sin embargo, para tensores de ordenpueden diferir. Los tensores de borde fueron estudiados por primera vez en el contexto de algoritmos de multiplicación de matrices aproximada rápida por Bini, Lotti y Romani en 1980. [13]
Un ejemplo clásico de un tensor de borde es el tensor de rango 3
Puede aproximarse arbitrariamente bien mediante la siguiente secuencia de tensores de rango 2
como . Por lo tanto, su rango de frontera es 2, que es estrictamente menor que su rango. Cuando los dos vectores son ortogonales, este ejemplo también se conoce como un estado W .
Propiedades
Identificabilidad
De la definición de un tensor puro se deduce que si y solo si existen tal que y para todos m . Por esta razón, los parámetros de un tensor de rango 1 se denominan identificables o esencialmente únicos. Un rango- tensor se llama identificable si cada una de sus descomposiciones de rango tensorial es la suma del mismo conjunto de distintos tensores donde el son de rango 1. Un rango identificable- por lo tanto, tiene solo una descomposición esencialmente única
Identificabilidad genérica
Tensores de orden 2 en , es decir, matrices, no son identificables para . Esto se sigue esencialmente de la observación
La situación cambia completamente para tensores de orden superior en con y todo . Para simplificar la notación, suponga sin pérdida de generalidad que los factores están ordenados de manera que. Dejardenotar el conjunto de tensores de rango acotado por . Luego, se demostró que la siguiente declaración era correcta utilizando una prueba asistida por computadora para todos los espacios de dimensión, [15] y se conjetura que es válido en general: [15] [16] [17]
Existe un conjunto cerrado en la topología de Zariski de modo que cada tensor es identificable (se denomina genéricamente identificable en este caso), a menos que se cumpla alguno de los siguientes casos excepcionales:
- El rango es demasiado grande: ;
- El espacio es identificable-desequilibrado, es decir, , y el rango es demasiado grande: ;
- El espacio es el caso defectuoso y el rango es ;
- El espacio es el caso defectuoso , dónde , y el rango es ;
- El espacio es y el rango es ;
- El espacio es y el rango es ; o
- El espacio es y el rango es .
- El espacio es perfecto, es decir, es un número entero y el rango es .
En estos casos excepcionales, el número genérico (y también mínimo) de descomposiciones complejas es
- demostrado ser en los primeros 4 casos;
- resultó ser dos en el caso 5; [18]
- se esperaba que [19] fuera seis en el caso 6;
- resultó ser dos en el caso 7; [20] y
- se espera que [19] sea al menos dos en el caso 8, con excepción de los dos casos identificables y .
En resumen, el tensor genérico de orden y rango que no es identificable-desequilibrado se espera que sea identificable (módulo los casos excepcionales en espacios pequeños).
Mal planteamiento del problema de aproximación estándar
El problema de aproximación de rango pide el rango descomposición más cercana (en la topología euclidiana habitual) a algún rango- tensor , dónde . Es decir, se busca resolver
dónde es la norma de Frobenius .
En un artículo de 2008 de De Silva y Lim [6] se demostró que el problema de aproximación estándar anterior puede estar mal planteado . Es posible que a veces no exista una solución al problema mencionado anteriormente porque el conjunto sobre el que se optimiza no está cerrado. Como tal, es posible que no exista un minimizador, aunque exista un mínimo. En particular, se sabe que ciertos tensores de borde pueden aproximarse arbitrariamente bien mediante una secuencia de tensor de rango como máximo, aunque el límite de la secuencia converge a un tensor de rango estrictamente superior a . El tensor de rango 3
puede aproximarse arbitrariamente bien mediante la siguiente secuencia de tensores de rango 2
como . Este ejemplo ilustra claramente el principio general de que una secuencia de rangosLos tensores que convergen a un tensor de rango estrictamente superior deben admitir al menos dos términos individuales de rango 1 cuyas normas se vuelven ilimitadas. Dicho formalmente, siempre que una secuencia
tiene la propiedad que (en la topología euclidiana) como , entonces debería existir al menos tal que
como . Este fenómeno se encuentra a menudo cuando se intenta aproximar un tensor utilizando algoritmos de optimización numérica. A veces se le llama el problema de los componentes divergentes . Además, se demostró que un tensor de rango bajo aleatorio sobre los reales puede no admitir una aproximación de rango 2 con probabilidad positiva, lo que lleva al entendimiento de que el problema de la mala posición es una consideración importante cuando se emplea la descomposición de rangos del tensor.
Una solución parcial común al problema de la mala situación consiste en imponer una restricción de desigualdad adicional que limita la norma de los términos individuales de rango 1 por alguna constante. Otras restricciones que dan como resultado un conjunto cerrado y, por lo tanto, un problema de optimización bien planteado, incluyen la imposición de positividad o un producto interno acotado estrictamente menor que la unidad entre los términos de rango 1 que aparecen en la descomposición buscada.
Calculando el CPD
Algoritmos alternos:
- mínimos cuadrados alternos (ALS)
- diagonalización alternante por cortes (ASD)
Algoritmos directos:
- algoritmos basados en lápiz [21] [22] [23] [24] [25] [26] [27]
- algoritmos basados en momentos [28]
Algoritmos de optimización general:
- diagonalización simultánea (SD)
- Descomposición simultánea de Schur generalizada (SGSD)
- Levenberg – Marquardt (LM)
- gradiente conjugado no lineal (NCG)
- memoria limitada BFGS (L-BFGS)
Algoritmos generales de resolución de sistemas polinomiales:
- continuación de homotopía [29]
Aplicaciones
En el aprendizaje automático, la descomposición de CP es el ingrediente central en el aprendizaje de modelos probabilísticos de variables latentes mediante la técnica de emparejamiento de momentos. Por ejemplo, considere el modelo de múltiples vistas [30] que es un modelo probabilístico de variable latente. En este modelo, la generación de muestras se plantea de la siguiente manera: existe una variable aleatoria oculta que no se observa directamente, dado que existen varias variables aleatorias condicionalmente independientes conocidas como las diferentes "vistas" de la variable oculta. Para simplificar, suponga que hay tres vistas simétricas de un -establecer variable oculta categórica . Entonces, el tercer momento empírico de este modelo de variable latente se puede escribir como:.
En aplicaciones como el modelado de temas , esto se puede interpretar como la co-ocurrencia de palabras en un documento. Entonces, los valores propios de este tensor de momento empírico se pueden interpretar como la probabilidad de elegir un tema específico y cada columna de la matriz de factores. corresponde a probabilidades de palabras en el vocabulario del tema correspondiente.
Ver también
- Análisis de clases latentes
- Aprendizaje subespacial multilineal
- Valor singular de descomposición
- Descomposición de Tucker
- Descomposición de valores singulares de orden superior
- Descomposición del tensor
Referencias
- ^ FL Hitchcock (1927). "La expresión de un tensor o una poliada como suma de productos". Revista de Matemáticas y Física . 6 : 164-189.
- ^ a b Carroll, JD ; Chang, J. (1970). "Análisis de las diferencias individuales en la escala multidimensional a través de una generalización de n- vías de descomposición 'Eckart-Young'". Psychometrika . 35 (3): 283–319. doi : 10.1007 / BF02310791 .
- ^ a b Harshman, Richard A. (1970). "Fundamentos del procedimiento PARAFAC: Modelos y condiciones para un análisis factorial multimodal" explicativo " (PDF) . Documentos de trabajo de UCLA en fonética . 16 : 84. Nº 10.085. Archivado desde el original (PDF) el 10 de octubre de 2004.
- ^ Hillar, CJ ; Lim, L. (2013). "La mayoría de los problemas de tensores son NP-Hard". Revista de la ACM . 60 (6): 1–39. arXiv : 0911.1393 . doi : 10.1145 / 2512329 .
- ^ Landsberg, JM (2012). Tensores: geometría y aplicaciones . AMS.
- ^ a b c de Silva, V .; Lim, L. (2008). "Rango tensorial y la mala postura del mejor problema de aproximación de rango bajo". Revista SIAM sobre Análisis y Aplicaciones Matriciales . 30 (3): 1084-1127. arXiv : matemáticas / 0607647 . doi : 10.1137 / 06066518x .
- ^ Strassen, V. (1983). "Rango y cálculo óptimo de tensores genéricos" . Álgebra lineal y sus aplicaciones . 52/53: 645–685. doi : 10.1016 / 0024-3795 (83) 80041-x .
- ^ Catalisano, MV ; Geramita, AV ; Gimigliano, A. (2002). "Rangos de tensores, variedades secantes de variedades Segre y puntos grasos" . Álgebra lineal y sus aplicaciones . 355 : 263-285. doi : 10.1016 / s0024-3795 (02) 00352-x .
- ^ a b Abo, H .; Ottaviani, G .; Peterson, C. (2009). "Inducción para variedades secantes de variedades Segre". Transacciones de la American Mathematical Society . 361 (2): 767–792. arXiv : matemáticas / 0607191 . doi : 10.1090 / s0002-9947-08-04725-9 .
- ^ Lickteig, Thomas (1985). "Rango tensorial típico" . Álgebra lineal y sus aplicaciones . 69 : 95-120. doi : 10.1016 / 0024-3795 (85) 90070-9 .
- ^ Catalisano, MV ; Geramita, AV ; Gimigliano, A. (2011). "Variedades secantes de1 × ··· ×1 ( n veces) no son defectuosos para n ≥ 5 ". Journal of Algebraic Geometry . 20 (2): 295–327. Doi : 10.1090 / s1056-3911-10-00537-0 .
- ^ Blehkerman, G .; Teitler, Z. (2014). "Sobre rangos máximos, típicos y genéricos". Mathematische Annalen . En prensa. (3–4): 1–11. arXiv : 1402.2371 . doi : 10.1007 / s00208-014-1150-3 .
- ^ Bini, D .; Lotti, G .; Romani, F. (1980). "Soluciones aproximadas para el problema computacional de forma bilineal". Revista SIAM de Computación Científica . 9 (4): 692–697. doi : 10.1137 / 0209053 .
- ^ Harris, Joe (1992). SpringerLink de geometría algebraica . Textos de Posgrado en Matemáticas. 133 . doi : 10.1007 / 978-1-4757-2189-8 . ISBN 978-1-4419-3099-6.
- ^ a b Chiantini, L .; Ottaviani, G .; Vannieuwenhoven, N. (1 de enero de 2014). "Un algoritmo para la identificabilidad específica genérica y de bajo rango de tensores complejos". Revista SIAM sobre Análisis y Aplicaciones Matriciales . 35 (4): 1265-1287. arXiv : 1403.4157 . doi : 10.1137 / 140961389 . ISSN 0895-4798 .
- ^ Bocci, Cristiano; Chiantini, Luca; Ottaviani, Giorgio (1 de diciembre de 2014). "Métodos refinados para la identificabilidad de tensores". Annali di Matematica Pura ed Applicata . 193 (6): 1691-1702. arXiv : 1303.6915 . doi : 10.1007 / s10231-013-0352-8 . ISSN 0373-3114 .
- ^ Chiantini, L .; Ottaviani, G .; Vannieuwenhoven, N. (1 de enero de 2017). "Criterios efectivos para la identificabilidad específica de tensores y formas". Revista SIAM sobre Análisis y Aplicaciones Matriciales . 38 (2): 656–681. arXiv : 1609.00123 . doi : 10.1137 / 16m1090132 . ISSN 0895-4798 .
- ^ Chiantini, L .; Ottaviani, G. (1 de enero de 2012). "Sobre la identificabilidad genérica de 3 tensores de rango pequeño". Revista SIAM sobre Análisis y Aplicaciones Matriciales . 33 (3): 1018–1037. arXiv : 1103.2696 . doi : 10.1137 / 110829180 . ISSN 0895-4798 .
- ^ a b Hauenstein, JD; Oeding, L .; Ottaviani, G .; Sommese, AJ (2016). "Técnicas de homotopía para descomposición tensorial y perfecta identificabilidad". J. Reine Angew. Matemáticas . arXiv : 1501.00090 . doi : 10.1515 / crelle-2016-0067 .
- ^ Bocci, Cristiano; Chiantini, Luca (2013). "Sobre la identificabilidad de los productos binarios Segre" . Revista de geometría algebraica . 22 (1): 1–11. arXiv : 1105.3643 . doi : 10.1090 / s1056-3911-2011-00592-4 . ISSN 1056-3911 .
- ^ Domanov, Ignat; Lathauwer, Lieven De (enero de 2014). "Descomposición políada canónica de tensores de tercer orden: reducción a la descomposición generalizada de valores propios". Revista SIAM sobre Análisis y Aplicaciones Matriciales . 35 (2): 636–660. arXiv : 1312.2848 . doi : 10.1137 / 130916084 . ISSN 0895-4798 .
- ^ Domanov, Ignat; De Lathauwer, Lieven (enero de 2017). "Descomposición poliada canónica de tensores de tercer orden: condiciones de unicidad relajada y algoritmo algebraico". Álgebra lineal y sus aplicaciones . 513 : 342–375. arXiv : 1501.07251 . doi : 10.1016 / j.laa.2016.10.019 . ISSN 0024-3795 .
- ^ Faber, Nicolaas (Klaas) M .; Ferré, Joan; Boqué, Ricard (enero de 2001). "Método de aniquilación de rango generalizado repetido iterativamente". Quimiometría y sistemas de laboratorio inteligentes . 55 (1–2): 67–90. doi : 10.1016 / s0169-7439 (00) 00117-9 . ISSN 0169-7439 .
- ^ Leurgans, SE ; Ross, RT; Abel, RB (octubre de 1993). "Una descomposición para matrices de tres vías". Revista SIAM sobre Análisis y Aplicaciones Matriciales . 14 (4): 1064–1083. doi : 10.1137 / 0614071 . ISSN 0895-4798 .
- ^ Lorber, Avraham. (Octubre de 1985). "Características de la cuantificación de la composición química de la matriz de datos bidimensionales por el método de análisis del factor de aniquilación de rango". Química analítica . 57 (12): 2395–2397. doi : 10.1021 / ac00289a052 . ISSN 0003-2700 .
- ^ Sánchez, Eugenio; Kowalski, Bruce R. (enero de 1990). "Resolución tensorial: una descomposición trilineal directa". Revista de quimiometría . 4 (1): 29–45. doi : 10.1002 / cem.1180040105 . ISSN 0886-9383 .
- ^ Sands, Richard; Young, Forrest W. (marzo de 1980). "Modelos de componentes para datos de tres vías: un algoritmo de mínimos cuadrados alternos con características de escala óptimas". Psychometrika . 45 (1): 39–67. doi : 10.1007 / bf02293598 . ISSN 0033-3123 .
- ^ Bernardi, A .; Brachat, J .; Comon, P .; Mourrain, B. (mayo de 2013). "Descomposición tensorial general, matrices de momentos y aplicaciones". Revista de Computación Simbólica . 52 : 51–71. arXiv : 1105.1229 . doi : 10.1016 / j.jsc.2012.05.012 . ISSN 0747-7171 .
- ^ Bernardi, Alessandra; Daleo, Noah S .; Hauenstein, Jonathan D .; Mourrain, Bernard (diciembre de 2017). "Descomposición tensorial y continuación de homotopía". Geometría diferencial y sus aplicaciones . 55 : 78-105. arXiv : 1512.04312 . doi : 10.1016 / j.difgeo.2017.07.009 . ISSN 0926-2245 .
- ^ Anandkumar, Animashree; Ge, Rong; Hsu, Daniel; Kakade, Sham M; Telgarsky, Matus (2014). "Descomposiciones tensoriales para el aprendizaje de modelos de variables latentes". The Journal of Machine Learning Research . 15 (1): 2773–2832.
Otras lecturas
- Kolda, Tamara G .; Bader, Brett W. (2009). "Aplicaciones y Descomposiciones Tensoriales". SIAM Rev . 51 (3): 455–500. CiteSeerX 10.1.1.153.2059 . doi : 10.1137 / 07070111X .
- Landsberg, Joseph M. (2012). Tensores: geometría y aplicaciones . AMS.
enlaces externos
- Tutorial PARAFAC
- Análisis de factores paralelos (PARAFAC)
- FactoMineR (software de análisis de datos multivariante exploratorio gratuito vinculado a R )