Factorització matricial no negativa

Il·lustració de la factorització matricial no negativa aproximada: la matriu V està representada per les dues matrius més petites W i H, que, multiplicades, reconstrueixen aproximadament V.

La factorització matricial no negativa (NMF o NNMF), també l'aproximació matricial no negativa és un grup d'algorismes d' anàlisi multivariant i àlgebra lineal on una matriu V es factoritza en (normalment) dues matrius W i H, amb la propietat que les tres matrius no tenen elements negatius. Aquesta no-negativitat fa que les matrius resultants siguin més fàcils d'inspeccionar. Així mateix, en aplicacions com el processament d'espectrogrames d'àudio o l'activitat muscular, la no-negativitat és inherent a les dades que es consideren. Com que el problema no és exactament resoluble en general, normalment s'aproxima numèricament.

NMF troba aplicacions en camps com l'astronomia, visió per ordinador, agrupació de documents, imputación de dades que falten, quimiometria, processament de senyals d'àudio, sistemes de recomanació i bioinformàtica.

Història

En quimiometria, la factorització matricial no negativa té una llarga història sota el nom de "resolució de corbes d'automodelació". En aquest marc, els vectors de la matriu dreta són corbes contínues en lloc de vectors discrets. També els primers treballs sobre factoritzacions de matrius no negatives van ser realitzats per un grup d'investigadors finlandesos a la dècada de 1990 sota el nom de factorització de matrius positives. Es va fer més conegut com a factorització matricial no negativa després que Lee i Seung investiguessin les propietats de l'algorisme i publiquessin alguns algorismes senzills i útils per a dos tipus de factoritzacions.

Rerefons

Sigui la matriu V el producte de les matrius W i H,

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

La multiplicació de matrius es pot implementar calculant els vectors columna de V com a combinacions lineals dels vectors columna en W utilitzant coeficients subministrats per columnes de H . És a dir, cada columna de V es pot calcular de la següent manera:

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

on v_i és l'i-è vector columna de la matriu producte V i h_i és el i -è vector columna de la matriu H.

Quan es multipliquen matrius, les dimensions de les matrius de factors poden ser significativament inferiors a les de la matriu de producte i és aquesta propietat la que forma la base de NMF. NMF genera factors amb dimensions significativament reduïdes en comparació amb la matriu original. Per exemple, si V és una matriu m × n, W és una matriu m × p i H és una matriu p × n aleshores p pot ser significativament menor tant que m com n.

Aquí teniu un exemple basat en una aplicació de mineria de text:

• Sigui la matriu d'entrada (la matriu a factoritzar) V amb 10.000 files i 500 columnes on les paraules estan en files i els documents en columnes. És a dir, tenim 500 documents indexats per 10.000 paraules. Es dedueix que un vector columna v en V representa un document.
• Suposem que demanem a l'algorisme que trobi 10 característiques per tal de generar una matriu de característiques W amb 10.000 files i 10 columnes i una matriu de coeficients H amb 10 files i 500 columnes.
• El producte de W i H és una matriu amb 10.000 files i 500 columnes, la mateixa forma que la matriu d'entrada V i, si la factorització va funcionar, és una aproximació raonable a la matriu d'entrada V.
• Del tractament de la multiplicació de matrius anterior es desprèn que cada columna de la matriu de productes WH és una combinació lineal dels 10 vectors de columna de la matriu de característiques W amb coeficients proporcionats per la matriu de coeficients H.

Algorismes

Hi ha diverses maneres de trobar la W i H: La regla d'actualització multiplicativa de Lee i Seung ha estat un mètode popular a causa de la senzillesa d'implementació. Aquest algorisme és:

inicialitzar: W i H no negatius.

A continuació, actualitzeu els valors de W i H calculant el següent, amb $n$ com a índex de la iteració.

$\mathbf {H} _{[i,j]}^{n+1}\leftarrow \mathbf {H} _{[i,j]}^{n}{\frac {((\mathbf {W} ^{n})^{T}\mathbf {V} )_{[i,j]}}{((\mathbf {W} ^{n})^{T}\mathbf {W} ^{n}\mathbf {H} ^{n})_{[i,j]}}}$

i

$\mathbf {W} _{[i,j]}^{n+1}\leftarrow \mathbf {W} _{[i,j]}^{n}{\frac {(\mathbf {V} (\mathbf {H} ^{n+1})^{T})_{[i,j]}}{(\mathbf {W} ^{n}\mathbf {H} ^{n+1}(\mathbf {H} ^{n+1})^{T})_{[i,j]}}}$

Fins que W i H són estables.

Tingueu en compte que les actualitzacions es fan element per element, no per multiplicació de matrius.

Observem que els factors multiplicatius per W i H, és a dir, el ${\textstyle {\frac {\mathbf {W} ^{\mathsf {T}}\mathbf {V} }{\mathbf {W} ^{\mathsf {T}}\mathbf {W} \mathbf {H} }}}$ i ${\textstyle {\textstyle {\frac {\mathbf {V} \mathbf {H} ^{\mathsf {T}}}{\mathbf {W} \mathbf {H} \mathbf {H} ^{\mathsf {T}}}}}}$ termes, són matrius d'uns quan $\mathbf {V} =\mathbf {W} \mathbf {H}$.

Aplicacions

• Astronomia
• Imputació de dades
• Mineria de textos
• Anàlisi de dades espectrals
• Predicció escalable de distància a Internet
• Reducció de soroll de la parla no estacionària
• Genètica de poblacions
• Bioinformàtica
• Imatge nuclear