Stochastic Multiplicative Updates for Symmetric Nonnegative Matrix Factorization

Abstract

Innen maskinlæring brukes symmetrisk ikkenegativ matrisefaktorisering (NMF) i forbindelse med clusteranalyse. NMF utføres ofte ved hjelp av algoritmer som tar i bruk multiplikative oppdateringer (MU). Disse har den fordelen at de automatisk opprettholder ikkenegativitet i faktormatrisen. Inspirert av suksessen til stokastisk gradient descent, utvikler vi en ny stokastisk MU-algoritme. Vi kaller algoritmen Stochastic Bound-and-Scale Multiplicative Updates (SBSMU). Så langt vi vet, er dette den første gangen en stokastisk MU-algoritme har blitt utviklet for symmetrisk NMF. Vi presenterer en teoretisk analyse av SBSMU, inkludert et bevis som gir innsikt i betingelsene som avgjør om SBSMU konvergerer. Videre presenterer vi resultatene fra tre empiriske eksperimenter. Dataene tilsier at en standardkonfigurasjon for SBSMU gir relativt god ytelse på tvers av datasett. I tillegg viser vi at SBSMU kan faktorisere store datasett vi tester den på, selv om algoritmen ikke når opp til de beste referansealgoritmene.

In the field of machine learning, symmetric nonnegative matrix factorization(NMF) is commonly used for clustering. NMF is often performed by multiplicative update (MU) algorithms, because they naturally maintain nonnegativity. Inspired by the success of stochasticity in gradient descent, we develop a novel stochastic MU algorithm for symmetric NMF. We call the algorithm Stochastic Bound-and-Scale Multiplicative Updates (SBSMU). To the best of our knowledge, this is the first time stochasticity has been introduced to MU for symmetric NMF. We provide a theoretical analysis of SBSMU, including a proof which provides insights into the conditions under which the algorithm converges. Furthermore, we present the results of three empirical experiments. The data suggests that a standard configuration of SBSMU achieves a relatively good performance across datasets. Moreover, we find that that SBSMU is able to factorize the large datasets we apply it to, although it is not on par with the best benchmarks.