Factorización no negativa de matrices
# Factorización no negativa de matrices

Factorización matricial no negativa (NMF o NNMF), también aproximación matricial no negativa, es un grupo de algoritmos en análisis multivariante y álgebra lineal donde una matriz V se factoriza en (habitualmente) dos matrices W y H, con la propiedad de que las tres matrices no tienen elementos negativos. Esta no negatividad hace que las matrices resultantes sean más fáciles de inspeccionar. Además, en aplicaciones tales como el procesamiento de espectrogramas de audio o actividad muscular, la no negatividad es inherente a los datos que se consideran. Dado que el problema en general no se puede resolver exactamente, comúnmente se aproxima numéricamente.

NMF encuentra aplicaciones en campos tales como visión por computadora, agrupación de documentos, quimiometría, procesamiento de señal de audio y sistemas de recomendación.

## Historia

En quimiometría, la factorización matricial no negativa tiene un largo historial bajo el nombre de "resolución de curva de auto modelado". En este marco, los vectores en la matriz derecha son curvas continuas en lugar de vectores discretos. Un grupo de investigadores finlandeses realizaron a mediados de la década de 1990 un trabajo temprano sobre factorizaciones de matrices no negativas bajo el nombre de factorización de matriz positiva. Se hizo más conocido como factorización nonegativa de matrices después de que Lee y Seung investigaron las propiedades del algoritmo y publicaron algunos algoritmos simples y útiles para dos tipos de factorizaciones.

## Bases

Sea la matriz V el producto de las matrices W y H,

    $\mathbf {V} =\mathbf {W} \mathbf {H} \,.$

La multiplicación de matrices se puede implementar computando los vectores columnas de V como combinaciones lineales de los vectores columnas en W usando coeficientes proporcionados por columnas de H. Es decir, cada columna de V se puede calcular de la siguiente manera:

    $\mathbf {v} _{i}=\mathbf {W} \mathbf {h} _{i}\,,$

donde vi es el i-ésimo vector columna de la matriz producto V y hi es el i-ésimo vector columna de la matriz H.

Cuando se multiplican matrices, las dimensiones de las matrices de factores pueden ser significativamente más pequeñas que las de la matriz producto y es esta propiedad la que forma la base de NMF. NMF genera factores con dimensiones significativamente reducidas en comparación con la matriz original. Por ejemplo, si V es una matriz m × n, W es una matriz m × p, y H es una matriz p × n, entonces p puede ser significativamente menor que m y n. .

Este es un ejemplo basado en una aplicación de minería de texto:

* Tenemos que la matriz de entrada (la matriz a factorizar) sea V con 10000 filas y 500 columnas donde las palabras están en las filas y los documentos están en las columnas. Es decir, tenemos 500 documentos indexados por 10000 palabras. Esto significa que un vector columna v en V representa un documento.
* Supongamos que pedimos al algoritmo que encuentre 10 características para generar una matriz de características W con 10000 filas y 10 columnas y una matriz de coeficientes H con 10 filas y 500 columnas.
* El producto de W y H es una matriz con 10000 filas y 500 columnas, la misma forma que la matriz de entrada V y, si la factorización funcionó, es una aproximación razonable a la matriz de entrada V.
* Del tratamiento de la multiplicación matricial anterior, se destaca que cada columna en la matriz de productos WH es una combinación lineal de los 10 vectores columnas en la matriz de características W con coeficientes suministrados por la matriz de coeficientes H.

Este último punto es la base de NMF porque podemos considerar cada documento original en nuestro ejemplo como construido a partir de un pequeño conjunto de características ocultas. NMF genera estas características.

Es útil pensar en cada característica (vector columna) en la matriz de características W como un arquetipo de documento que comprende un conjunto de palabras en el que el valor de la celda de cada palabra define el rango de la palabra en la característica: cuanto mayor sea el valor de la celda de una palabra mayor será el rango de la palabra en la característica. Una columna en la matriz de coeficientes H representa un documento original con un valor de celda que define el rango del documento para una característica. Ahora podemos reconstruir un documento (vector columna) de nuestra matriz de entrada mediante una combinación lineal de nuestras características (vectores columnas en W) donde cada característica se ponderará por el valor de la celda de característica de la columna del documento en H.

## Propiedad de agrupamiento(clúster)

NMF tiene una propiedad inherente de agrupamiento,[11] es decir, agrupa automáticamente las columnas de datos de entrada $\mathbf {V} =(v_{1},\cdots ,v_{n})$.Es esta propiedad la que impulsa la mayoría de las aplicaciones de NMF.

Más específicamente, la aproximación de $\mathbf {V}$ por $\mathbf {V} \simeq \mathbf {W} \mathbf {H}$ se logra minimizando la función de error $\min _{W,H}||V-WH||_{F},$ sujeto a $W\geq 0,H\geq 0.$

Además, el $H$ computado proporciona el indicador de grupo, es decir ,si $\mathbf {H} _{kj}>0$, el hecho de que $v_{j}$ pertenezca al grupo $k^{th}$. Y el computado $W$ proporciona el centroide del grupo, es decir, las columnas $k^{th}$ proporcionan el centroide del grupo de $k^{th}$ cluster. Esta representación del centroide se puede mejorar significativamente con NMF convexa.

Cuando la ortogonalidad $HH^{T}=I$ no se impone explícitamente, la ortogonalidad se mantiene en gran medida, y la propiedad de agrupación también se mantiene. La agrupación en grupos (clúster) es el objetivo principal de la mayoría de las aplicaciones de minería de datos de NMF.

Cuando la función de error que se utilizará es la divergencia Kullback-Leibler, NMF es idéntica al análisis semántico latente probabilístico, un método popular de agrupación de documentos.

## Tipos

### Aproximada factorización no negativa de matrices

Habitualmente, en NMF se selecciona el número de columnas de W y el número de filas de H, de modo que el producto WH se convertirá en una aproximación a V. La descomposición completa de V entonces equivale a las dos matrices no negativas W y H, así como a una matriz U residual, tal que: V = WH + U. Los elementos de la matriz residual pueden ser negativos o positivos.

Cuando W y H son más pequeños que V, se vuelven más fáciles de almacenar y manipular. Otra razón para factorizar V en matrices más pequeñas W y H es que si se pueden representar aproximadamente los elementos de V con datos significativamente menores, entonces se debe inferir alguna estructura latente en los datos.

### Factorización convexa no negativa de matrices

En la NMF estándar, la matriz factor W ∈ $ℝ+^{m×k},$ es decir, W puede ser cualquier cosa en ese espacio. La NMF convexa restringe las columnas de W a combinaciones convexas de los vectores de datos de entrada $(v_{1},\cdots ,v_{n})$. Esto mejora en muy alto grado la calidad de la representación de W. Es más, la matriz factor H resultante es más dispersa y ortogonal.

### Factorización de rango no negativa

En caso de que el rango no negativo de V sea igual a su rango real, V = WH se denomina factorización de rango no negativo. El problema de encontrar la NRF de V, si existe, se sabe que es NP-duro.

### Diferentes funciones de costo y regularizaciones

Existen diferentes tipos de factorizaciones no negativas de matrices. Los diferentes tipos surgen del uso de diferentes funciones de costo para medir la divergencia entre V y WH y posiblemente mediante la regularización de las matrices W y/o H.

Dos simples funciones de divergencia estudiadas por Lee y Seung son el error cuadrado (o norma Frobenius) y una extensión de la divergencia Kullback-Leibler a matrices positivas (la divergencia Kullback-Leibler original se define en las distribuciones de probabilidad). Cada divergencia conduce a un algoritmo de NMF diferente, por lo general minimizando la divergencia usando reglas de actualización iterativa.

El problema de factorización en la versión de error cuadrado de NMF puede establecerse como: Dado una matriz V, encuentre matrices no negativas W y H que minimicen la función

Otro tipo de NMF para las imágenes se basa en la norma de variación total.

Cuando se agrega L1 regularización (similar a Lasso) a NMF con la función de costo de error cuadrático medio, el problema resultante se puede llamar codificación dispersa no negativa debido a la similitud con el problema de codificación dispersa, aunque también se conoce como NMF.

### NMF en línea

Muchos algoritmos de NMF estándar analizan todos los datos juntos; es decir, toda la matriz está disponible desde el principio. Esto puede ser insatisfactorio en aplicaciones en las que hay demasiados datos para caber en la memoria o donde los datos se proporcionan de forma continua. Uno de estos usos es el filtrado colaborativo en los sistemas de recomendación, donde puede haber muchos usuarios y muchos artículos para recomendar, y sería ineficiente volver a calcular todo cuando se agrega al sistema un usuario o un elemento. La función de costo para la optimización en estos casos puede o no ser la misma que para el NMF estándar, pero los algoritmos necesitan ser bastante diferentes.

## Algoritmos

Hay varias formas en que se puede encontrar W y H: la regla de actualización multiplicativa de Lee y Seung ha sido un método popular debido a la simplicidad de implementación. Este algoritmo es:

    Inicializa: <W and H no negativo.
    Luego actualizar los valores en W y H computando alternativamente:
    $H_{[i,j]}\leftarrow H_{[i,j]}{\frac {(W^{T}V)_{[i,j]}}{(W^{T}WH)_{[i,j]}}}$
    and
    $W_{[i,j]}\leftarrow W_{[i,j]}{\frac {(VH^{T})_{[i,j]}}{(WHH^{T})_{[i,j]}}}$

Hasta que W y H sean estables. Tenga en cuenta que las actualizaciones se realizan de elemento en elemento, no de una multiplicación matricial.

Observamos que el factor multiplicativo W y H es la matriz identidad cuando V = W H.

Desde entonces, se han desarrollado algunos otros enfoques algorítmicos. Algunos algoritmos exitosos se basan en alternar mínimos cuadrados no negativos : en cada paso de dicho algoritmo, primero H se fija y W se encuentra mediante un solucionador de mínimos cuadrados no negativo, entonces W se fija y H se encuentra de manera análoga. Los procedimientos utilizados para resolver W y H pueden ser los mismos o diferentes, ya que algunas variantes de NMF regularizan una de las dos matrices W y H. Los enfoques específicos incluyen los métodos de descenso de gradiente proyectados, el método de conjunto activo, el método de gradiente óptimo, y el método de pivote principal del bloque entre varios otros.

Los algoritmos actualmente disponibles son subóptimos ya que solo pueden garantizar la búsqueda de un mínimo local, en lugar de un mínimo global de la función de costo. Un algoritmo probablemente óptimo es improbable en el futuro cercano ya que se ha demostrado que el problema generaliza el problema de la agrupación k-means que se conoce como NP-completo. Sin embargo, como en muchas otras aplicaciones de minería de datos, un mínimo local aún puede resultar útil.

### Exacto NMF

Se pueden esperar soluciones exactas para las variantes de NMF (en tiempo polinomial) cuando existen restricciones adicionales para la matriz V. Un algoritmo de tiempo polinomial para resolver factorización de rango no negativo si V contiene una sub-matriz monomérica de rango igual a su rango fue dada por Campbell y Poole en 1981. Kalofolias y Gallopoulos (2012) resolvieron la contraparte simétrica de este problema, donde V es simétrico y contiene una sub-matriz de diagonal principal de rango r. Su algoritmo se ejecuta en tiempo O (rm ^ 2) en el caso denso. Arora, Ge, Halpern, Mimno, Moitra, Sontag, Wu y Zhu (2013) dan un algoritmo de tiempo polinomial para NMF exacta que funciona para el caso donde uno de los factores W satisface la condición de separabilidad.

## Relación con otras técnicas

En Learning the parts of objects para factorización no negativa de matrices, Lee y Seung propusieron NMF principalmente para la descomposición de imágenes basada en partes. Esto compara la NMF con la cuantificación vectorial y el análisis de componentes principales, y muestra que aunque las tres técnicas pueden escribirse como factorizaciones, implementan diferentes restricciones y, por lo tanto, producen resultados diferentes.

Más tarde se demostró que algunos tipos de NMF son una instancia de un modelo probabilístico más general llamado "PCA multinomial". Cuando se obtiene NMF minimizando la divergencia Kullback-Leibler, es de hecho equivalente a otra instancia de PCA multinomial, análisis semántico latente probabilístico, entrenado por estimación de máxima verosimilitud. Ese método se usa comúnmente para analizar y agrupar datos textuales y también está relacionado con el modelo de clase latente.

NMF con el objetivo de mínimos cuadrados es equivalente a una forma relajada de K-means clustering: la matriz factor W contiene los centroides del grupo y H contiene los indicadores de pertenencia al grupo. Esto proporciona una base teórica para usar NMF para la agrupación de datos. Sin embargo, k-means no impone la no negatividad en sus centroides, por lo que la analogía más cercana es en realidad con "semi-NMF".

La NMF puede verse como un modelo gráfico dirigido de dos capas con una capa de variables aleatorias observadas y una capa de variables aleatorias ocultas.

NMF se extiende más allá de las matrices a tensores de orden arbitrario. Esta extensión puede verse como una contraparte no negativa para, por ejemplo, el modelo PARAFAC

Otras extensiones de NMF incluyen factorización conjunta de varias matrices de datos y tensores donde se comparten algunos factores. Dichos modelos son útiles para la fusión del sensor y el aprendizaje relacional.

NMF es una instancia de programación cuadrática no negativa (NQP), al igual que la máquina de vectores de soporte (SVM). Sin embargo, SVM y NMF están relacionados a un nivel más íntimo que el de NQP, lo que permite la aplicación directa de los algoritmos de solución desarrollados para cualquiera de los dos métodos a problemas en ambos dominios.

## Unicidad

La factorización no es única: una matriz y su inversa pueden usarse para transformar las dos matrices de factorización por, por ejemplo,

Si las dos matrices nuevas

La no negatividad de

Se obtiene un mayor control sobre la no singularidad de NMF con restricciones de esparcidad.

## Aplicaciones

### Extracción de textos

NMF se puede usar para aplicaciones de minería de texto. En este proceso, se construye una matriz de términos de documentos con los pesos de varios términos (típicamente información de frecuencia de palabras ponderadas) de un conjunto de documentos. Esta matriz se factoriza en una función de término y una matriz de documento de características. Las características se derivan del contenido de los documentos, y la matriz del documento de características describe grupos de datos de documentos relacionados.

Una aplicación específica utilizó NMF jerárquica en un pequeño subconjunto de resúmenes científicos de PubMed. Otro grupo de investigación agrupó partes del conjunto de datos de correo electrónico de Enron con 65,033 mensajes y 91,133 términos en 50 grupos. NMF también se ha aplicado a los datos de citas, con un ejemplo agrupando los artículos de Wikipedia en inglés y las revistas científicas basadas en las citas científicas salientes en Wikipedia en inglés.

Arora, Ge, Halpern, Mimno, Moitra, Sontag, Wu y Zhu (2013) han dado algoritmos de tiempo polinomial para aprender modelos de temas utilizando NMF. El algoritmo asume que la matriz del tema satisface una condición de separabilidad que a menudo se encuentra en esta configuración.

### Análisis de datos espectrales

NMF también se usa para analizar datos espectrales; uno de esos usos está en la clasificación de los objetos dispersos y los desechos.

### Predicción de distancia escalable de Internet

NMF se aplica en la predicción de distancia escalable de Internet (tiempo de ida y vuelta). Para una red con hosts . Este tipo de método se introdujo en primer lugar en el Servicio de Estimación de Distancia de Internet (IDES). Posteriormente, como un enfoque totalmente descentralizado, se propone el sistema de coordenadas de la red Phoenix. Este alcanza una mejor precisión de predicción global introduciendo el concepto de peso.

### Eliminación de ruido del habla no estacionaria

El ruido de voz ha sido un problema de larga duración en el procesamiento de la señal de audio. Hay muchos algoritmos para eliminar ruido si el ruido es estacionario. Por ejemplo, el filtro Wiener es adecuado para el ruido Gaussiano aditivo. Sin embargo, si el ruido no es estacionario, los algoritmos de eliminación de ruido clásicos generalmente tienen un rendimiento bajo porque la información estadística del ruido no estacionario es difícil de estimar. Schmidt y col. usan NMF para hacer ruido de voz bajo ruido no estacionario, que es completamente diferente de los enfoques estadísticos clásicos. La idea clave es que la señal de voz limpia puede estar escasamente representada por un diccionario de voz, pero el ruido no estacionario no puede. De manera similar, el ruido no estacionario también puede estar escasamente representado por un diccionario de ruido, pero el habla no puede.

El algoritmo para la eliminación de NMF es el siguiente. Dos diccionarios, uno para discurso y uno para ruido, deben ser entrenados sin conexión. Una vez que se da un discurso ruidoso, primero calculamos la magnitud de la Transformada de Fourier de Corto Tiempo. En segundo lugar, sepárelo en dos partes a través de NMF, uno puede ser escasamente representado por el diccionario de voz, y la otra parte puede ser escasamente representado por el diccionario de ruido. Tercero, la parte que está representada por el diccionario de habla será el discurso limpio estimado.

### Bioinformática

La NMF se aplicó con éxito en bioinformática para agrupar la expresión génica y los datos de metilación del ADN y encontrar los genes más representativos de los grupos. En el análisis de las mutaciones del cáncer se ha utilizado para identificar patrones comunes de mutaciones que ocurren en muchos tipos de cáncer y que probablemente tengan causas distintas.

### Imágenes nucleares

La NMF, también referida en este campo como análisis factorial, se ha utilizado desde los años 80 para analizar secuencias de imágenes en imágenes médicas dinámicas SPECT y PET. La no-singularidad de NMF fue abordada usando limitaciones de dispersidad.

## Búsqueda actual

La investigación actual (desde 2010) en factorización no negativa de matrices incluye, pero no se limita a,

* Algorítmico: búsqueda de mínimos globales de los factores y la inicialización de factores.
* Escalabilidad: cómo factorizar las matrices de millones de mil millones, que son comunes en la minería de datos a escala Web, por ejemplo, ver Factorización de matriz no negativa distribuida (DNMF) y Factorización no negativa de matrices escalables (ScalableNMF)
* En línea: cómo actualizar la factorización cuando entran nuevos datos sin recompilar desde cero, por ejemplo, consulte CNSC en línea
* Facturación colectiva (conjunta): factorización de múltiples matrices interrelacionadas para el aprendizaje de múltiples vistas, ejemplo mutli-view clustering, ver CoNMF y MultiNMF
* Problema de Cohen y Rothblum 1993: si una matriz racional siempre tiene una NMF de dimensión interna mínima cuyos factores también son racionales. Recientemente, este problema ha sido respondido negativamente.

## Ve también

* Multilinear Álgebra
* Multilinear subspace learning
* Tensor
* Tensor decomposition
* Tensor Software
