Factorizzazione rapida della matrice non negativa su matrice sparsa grande

Question

Utilizzo di Scikit-learn (v 0.15.2) per la fattorizzazione della matrice non negativa su una matrice sparsa di grandi dimensioni (meno dell'1% dei valori> 0). Voglio trovare i fattori riducendo al minimo gli errori solo su valori diversi da zero della matrice (ad esempio, non calcolare gli errori per le voci che sono zero) e per favorire la scarsità. Non sono sicuro se qualcosa non va in quello che sto provando. Il pacchetto di scikit-learn NMF e ProjectedGradientNMF hanno funzionato bene per me prima. Ma sembra che quando la dimensione della matrice aumenta, la fattorizzazione è terribilmente lenta.

Sto parlando di matrici con> 10^10 celle. Per la matrice con ~ 10^7 celle, trovo che il tempo di esecuzione sia buono.

I parametri utilizzati sono i seguenti: nmf_model = NMF(n_components = 100, init='nndsvd', random_state=0, tol = 0.01, sparseness='data').

Quando ho provato leggermente diversi parametri (passare a init=random), ottengo il seguente avviso. Dopo l'avviso, l'esecuzione dello script si interrompe.

/lib/python2.7/site-packages/sklearn/decomposition/nmf.py:252: UserWarning: Iteration limit reached in nls subproblem. 
    warnings.warn("Iteration limit reached in nls subproblem.") 

C'è un modo per rendere più veloce e risolvere il problema precedente? Ho provato a usare la matrice sparsa numpy (column-and row-sparse), ma sorprendentemente - è più lento nel test che ho fatto con una matrice più piccola (~ 10^7 celle).

Considerando che si dovrebbero eseguire più iterazioni di tale fattorizzazione (per scegliere un numero ideale di fattori e la convalida incrociata k-fold), un modo più rapido per risolvere questo problema è altamente auspicabile.

Sono aperto anche a suggerimenti di pacchetti/strumenti che non sono basati su sklearn o Pyhon. Capisco che le domande sulle scelte di pacchetti/strumenti non siano incoraggiate, ma per un caso d'uso specifico, sapendo quali tecniche potrebbero essere utili da altri utenti del settore.

Answer 1

Forse poche parole su quale sia il problema iniziale potrebbero consentirci di dare risposte migliori.

Il fattore di matrix su una matrice molto grande è sempre lento a causa della natura del problema.

Suggerimenti: Ridurre n_components a < 20 lo accelera un po '. Tuttavia, l'unico vero miglioramento della velocità sarà raggiunto limitando la dimensione della matrice. Con una matrice come la descrivi, si potrebbe pensare che si stia tentando di scomporre una matrice di frequenza del termine. Se è così, puoi provare a utilizzare le funzioni di vettorizzazione in scikit-learn per limitare la dimensione della matrice. Molti di questi hanno un parametro max_features. Esempio:

vectorizer = TfidfVectorizer(
    max_features=10000, 
    ngram_range=(1,2)) 
tfidf = vectorizer.fit_transform(data) 

Ciò consentirà di velocizzare notevolmente la risoluzione dei problemi.

Se dovessi essere completamente sbagliato e questo non è un problema di frequenza di termini, vorrei ancora esaminare i modi per limitare la matrice iniziale che stai cercando di scomporre.

Answer 2

Si potrebbe voler dare un'occhiata a questo articolo che discute le tecniche più recenti su NMF: http://www.cc.gatech.edu/~hpark/papers/nmf_blockpivot.pdf

L'idea è quella di lavorare solo sulle voci diverso da zero per la fattorizzazione che riduce il tempo di calcolo soprattutto quando la matrice/matrici coinvolte è/sono molto sparsi.

Inoltre, uno degli autori dello stesso articolo ha creato implementazioni NMF su github comprese quelle menzionate nel loro articolo.Ecco il link: https://github.com/kimjingu/nonnegfac-python

Spero che questo aiuti.