Non-negative Matrix Factorisation (NMF)

Aim

NMF aims to find latent topics within a document by factorising a term-document matrix. Unlike LSA, every value in the output is constrained to be non-negative.

Introduction

The term-document matrix is factorised into 2 parts:

1. a word-topic matrix
2. a topic-document matrix

These matrices can then be used to infer the semantic relations of words with each sentence.

Algorithm

Main Idea

Factorise the term-document matrix into 2 non-negative matrices, so that every weight is positive.

1. Generate the term-document matrix

• the matrix $A$ has size $n\times m$, where $n$ is the number of words and $m$ is the number of documents
• it is normalised using TF-IDF, the same as in LSA

2. Factorise into 2 matrices

$$A\approx W_{+}\times H_{+}$$

Matrix	Shape	Meaning
$A$	$n\times m$	words by documents
$W_{+}$	$n\times k$	every topic and the terms found within the topic
$H_{+}$	$k\times m$	every document and the topics found within the document

• the sign is $\approx$ and not $=$ because the factorisation is an approximation
• it is assumed that all elements of $W$ and $H$ are positive, given that the elements of $A$ are positive
• there are only 2 factor matrices, so there is no equivalent of the $S$ matrix from LSA

3. Minimise a cost function

When factorising the matrix, the 2 main cost functions that can be used are:

Generalised Kullback-Liebler Divergence (KL Divergence)

$$k{l}_{div(x,y)}=\{\begin{array}{ll}x\log \left(\frac{x}{y}\right)-x+y& x>0,y>0\\ y& x=0,y\ge 0\\ \infty & \text{otherwise}\end{array}$$

• as the value of the KL divergence reaches zero, the closeness of corresponding words increases

Frobenius Norm

$$\Vert A{\Vert }_F\equiv \sqrt{\sum _{i=1}^m\sum _{j=1}^n|a_{ij}{|}^2}$$

• defined as the square root of the sum of the absolute squares of its elements, the Frobenius Norm is a method of measuring how good an approximation is

NMF in Scikit-Learn

1. Apply TF-IDF

# use tf-idf by removing tokens that don't appear in at least 10 documents
vect = TfidfVectorizer(min_df=10, stop_words=stop_words)
 
# Fit and transform
X = vect.fit_transform(tweets.OriginalTweet)

• min_df=10 filters out words that do not appear in at least 10 tweets

2. Fit the NMF model

from sklearn.decomposition import NMF
 
# Create an NMF instance: model
# the 10 components will be the topics
model = NMF(n_components=10, random_state=5)
 
# Fit the model to TF-IDF
model.fit(X)
 
# Transform the TF-IDF: nmf_features
nmf_features = model.transform(X)

• n_components is the number of topics $k$
• random_state=5 fixes the seed, which matters because NMF is not deterministic
• nmf_features is the document-topic matrix, so it is one row per tweet and one column per topic

3. Inspect the topic-word matrix

components_df = pd.DataFrame(model.components_, columns=vect.get_feature_names_out())
components_df

Output, showing a subset of the columns:

	19	co	coronavirus	covid	covid19	food	grocery	people	prices	store	supermarket
0	0.000000	43.263244	0.000026	0.073465	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.002273
1	2.631301	0.000000	0.000000	2.717343	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000
2	0.000000	0.000000	0.000000	0.005084	0.000000	0.000269	0.155498	0.000000	0.000000	3.331384	0.000000
3	0.070977	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000133	2.964687
4	0.082723	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	3.580360	0.000000	0.000000
5	0.041040	0.000000	0.000000	0.000000	0.000000	1.939326	0.000000	0.000000	0.000000	0.000225	0.000000
6	0.000000	0.000000	0.000000	0.002607	0.000000	0.000029	0.000000	1.688712	0.000000	0.000172	0.000378
7	0.000000	0.000067	1.950688	0.000000	0.000000	0.000139	0.001383	0.000000	0.000358	0.000000	0.000172
8	0.000000	0.000000	0.000005	0.000413	1.594873	0.000027	0.001882	0.000000	0.000184	0.000000	0.000112
9	0.031762	0.000000	0.000000	0.000000	0.000000	0.000000	1.200351	0.000000	0.000000	0.000000	0.000000

• model.components_ has shape $k\times n$, so rows are topics and columns are words
• every value is 0 or positive, which is the non-negativity constraint in action

4. Print the top 10 words in each topic

for topic in range(components_df.shape[0]):
    tmp = components_df.iloc[topic]
    print(f'For topic {topic+1} the words with the highest value are:')
    print(tmp.nlargest(10))
    print('\n')

Output for the first 2 topics:

For topic 1 the words with the highest value are:
co             43.263244
covid           0.073465
supermarket     0.002273
coronavirus     0.000026
19              0.000000
covid19         0.000000
food            0.000000
grocery         0.000000
people          0.000000
prices          0.000000
Name: 0, dtype: float64

For topic 2 the words with the highest value are:
covid           2.717343
19              2.631301
co              0.000000
coronavirus     0.000000
covid19         0.000000
food            0.000000
grocery         0.000000
people          0.000000

Reading the output

• every weight is 0 or positive, so there is no negative weight to interpret, which is the main readability gain over LSA
• most weights are exactly 0, so each topic is defined by a small handful of words, which is what "parts-based representation" means
• topic 1 is dominated by "co" at 43.26, which comes from the t.co link fragments in the raw tweets, so it is a preprocessing artefact and not a real topic
• topic 3 is "store", topic 4 is "supermarket", topic 5 is "prices", and topic 6 is "food", so most topics reduce to a single strong word
• the topics are numbered 0 to 9 in components_, and the printing loop adds 1, so the printed "topic 1" is row 0

Advantages and Limitations

Advantages	Limitations
Parts-based representation: NMF naturally produces parts-based representations, which is valuable in applications like image processing and text mining, since it can discover fundamental components or topics within data	Non-convex optimisation: NMF is based on non-convex optimisation, so it may converge to local minima rather than the global minimum, and the quality of results can be sensitive to initialisation
Noise reduction: NMF can reduce the impact of noise in data, because it focuses on capturing underlying patterns and structures rather than specific noisy details	Preprocessing sensitivity: NMF is highly sensitive to the preprocessing used on the data, as well as the choice of cost function for the model