Latent semantic analysis and Gibbs sampling topic allocation (based on latent Dirichlet allocation) are methods used to compare topics and identify topics, respectively. By applying these methods to short stories, I explore the inner workings of these methods and interpret their results’ connection to the relationships between the stories.
Introduction
Introduction
I implemented latent semantic analysis (LSA), a topic comparing method, and Gibbs sampling to allocate topics, which makes it possible to identify topics. My English class was centered around the works of Karen Russell, especially her short stories. Since her stories are written about a wide variety of subjects in the style of magical realism, I wanted to see if common topics between these stories could be computationally revealed. When researching methods of comparing writing I came upon LSA and latent Dirichlet allocation (LDA). I implemented a Gibbs sampling version of LDA, which uses discrete statistics rather than the continuous Dirichlet distribution.
Examples of LSA and Gibbs Topic Allocation
Examples of LSA and Gibbs Topic Allocation
Both LSA and Gibbs topic allocation treat a document as a “bag of words,” where order does not matter. Each document needs to be formatted so that there are no stopwords, like “and” or “the,” that have no individual meaning. Since documents can be thought of as a mix of topics, I can construct example documents by specifying a document should be made of specific percentages of each topic.
Topic words [1, 2]:
In[]:=
animals={"bird","cat","dog","ferret","fish","gerbil","guinea pig","hamster","lizard","mouse","rabbit","rat","snake","turtle"};colors={"black","white","red","green","yellow","blue","brown","orange","pink","purple","gray"};
I constructed 3 documents: and one that is 4 words long that is 100% about colors. I used the colors from exDoc1 to choose the colors for exDoc2 because LSA compares based on the existence of common topic words.
◼
one that is 4 words long that is 100% about colors,
◼
one that is 4 words long that is 50% about animals and 50% about colors (I used the colors from exDoc1 to choose the colors for exDoc2 because LSA compares based on the existence of common topic words),
◼
and another that is 4 words long and 100% about colors.
In[]:=
exDoc1=RandomChoice[colors,4]exDoc2=Join[RandomChoice[animals,2],RandomChoice[exDoc1,2]]exDoc3=RandomChoice[colors,4]
Out[]=
{purple,pink,orange,green}
Out[]=
{dog,turtle,green,orange}
Out[]=
{pink,red,orange,purple}
LSA compares the topics in documents by inferring the probability of topic-related words appearing in each document. Since exDoc1 only contains colors, the inferred probability of animals appearing in this document would be less than or equal to zero. While there are 2 color words in exDoc2, the inferred probability for these words will likely decrease from one because colors are only half of the document.
Initial LSA matrix
In[]:=
TableForm[Table[Count[doc,word],{word,exDoc2[[-3;;-2]]},{doc,{exDoc1,exDoc2,exDoc3}}],TableHeadings->{exDoc2[[-3;;-2]],{doc1,doc2,doc3}}]
Out[]//TableForm=
doc1 | doc2 | doc3 | |
turtle | 0 | 1 | 0 |
green | 1 | 1 | 0 |
Final LSA matrix with inferences
In[]:=
TableForm[{{0,.5,0},{1,.5,1}},TableHeadings->{exDoc2[[-3;;-2]],{doc1,doc2,doc3}}]
Out[]//TableForm=
doc1 | doc2 | doc3 | |
turtle | 0 | 0.5 | 0 |
green | 1 | 0.5 | 1 |
The above final LSA matrix shows how LSA groups documents by topic. Since doc1 and doc3 have the same probabilities, it is likely that they cover the same or closely related topics.
Showing documents again for LDA explanation:
In[]:=
exDoc1exDoc2exDoc3
Out[]=
{purple,pink,orange,green}
Out[]=
{dog,turtle,green,orange}
Out[]=
{pink,red,orange,purple}
Given there are 2 topics, say topic A for colors and topic B for animals, Gibbs topic allocation would classify exDoc1 and exDoc3 as all topic A and exDoc2 as half topic A and half topic B. Since Gibbs topic allocation assigns the words in each document to a topic, the result of Gibbs topic allocation can be used to generate documents the way I generated the example documents.
By comparing the results of LSA, how related documents are, and Gibbs topic allocation, the topics a document covers, I can organize documents by topic and within topic by closeness. For instance, when deciding which document to read next I would have the recommendation be the most closely related document from the same topic.
Latent Semantic Analysis (LSA)
Latent Semantic Analysis (LSA)
LSA is a method to determine how likely a word is to appear in a document, which helps us understand what type of topics the document is covering. With LSA topics are treated as specific groupings of words, so we can test for the presence of topics in a document by finding the probability that words linked to a topic will appear in that document.
We begin by assuming that each word represents a different topic and use a matrix to record how often each word appears in each document. Then we remove information from this matrix in order to infer the probability that a word will appear in a document. Using these probabilities we can use the Spearman Rank Coefficient to determine if words have a positive relationship, meaning they often appear together and are likely from the same topic, or a negative relationship, meaning they rarely appear together and are from different topics. I used the Spearman Rank Coefficient because it is commonly used with LSA since it is less sensitive to outliers and skewedness than other statistical tests [3]. Once we know which words are from the same topic, we can interpret the topic for documents that are likely to contain those words.
I performed LSA step by step to understand how it works and show how LSA is implemented in Wolfram. After verifying that my steps worked, I applied LSA to some of Russell’s short stories. The word comparisons based on the LSA of the stories were a good test of my implementation because they show that while these stories seem quite different on the surface, they do have topics in common.
We begin by assuming that each word represents a different topic and use a matrix to record how often each word appears in each document. Then we remove information from this matrix in order to infer the probability that a word will appear in a document. Using these probabilities we can use the Spearman Rank Coefficient to determine if words have a positive relationship, meaning they often appear together and are likely from the same topic, or a negative relationship, meaning they rarely appear together and are from different topics. I used the Spearman Rank Coefficient because it is commonly used with LSA since it is less sensitive to outliers and skewedness than other statistical tests [3]. Once we know which words are from the same topic, we can interpret the topic for documents that are likely to contain those words.
I performed LSA step by step to understand how it works and show how LSA is implemented in Wolfram. After verifying that my steps worked, I applied LSA to some of Russell’s short stories. The word comparisons based on the LSA of the stories were a good test of my implementation because they show that while these stories seem quite different on the surface, they do have topics in common.
Implementing LSA using an example
Implementing LSA using an example
I used an example from “An Introduction to Latent Semantic Analysis” [4] to verify that my step by step implementation worked correctly. This example compared the titles of papers covering two distinct topics (human computer interaction and graph theory).
titles stores the documents and titleWords stores the words whose relationship with each other and with the documents we want to know
titles=ToLowerCase/@{"Human machine interface for ABC computer applications","A survey of user opinion of computer system response time","The EPS user interface management system","System and human system engineering testing of EPS","Relation of user perceived response time to error measurement","The generation of random, binary, ordered trees","The intersection graph of paths in trees","Graph minors IV: Widths of trees and well-quasi-ordering","Graph minors: A survey"};titleWords={"human","interface","computer","user","system","response","time","eps","survey","trees","graph","minors"};
Matrix of how often titles occur in each title with words from titleWords as rows and titles as columns.
In[]:=
matrix=Table[StringCount[doc,word],{word,titleWords},{doc,titles}];TableForm[matrix,TableHeadings->{titleWords,Table[StringJoin["doc",ToString[i]],{i,Length[titles]}]}]
Out[]//TableForm=
doc1 | doc2 | doc3 | doc4 | doc5 | doc6 | doc7 | doc8 | doc9 | |
human | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
interface | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
computer | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
user | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
system | 0 | 1 | 1 | 2 | 0 | 0 | 0 | 0 | 0 |
response | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
time | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
eps | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
survey | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
trees | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 |
graph | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
minors | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
In order to see if two words were related or not I used SpearmanRho to find the correlation coefficient between words from titleWords. Words with negative correlation coefficients are inversely related, so the existence of one word decreases the likelihood of the other existing in the same document, while words with positive correlation coefficients are closely related and are likely to appear in the same document. Below we can see that based on the relationships between the documents, the words “human” and “minors” are more closely related than “human” and “user.”
For human (row 1) and user (row 4):
In[]:=
N[SpearmanRho[matrix[[1]],matrix[[4]]]]
Out[]=
-0.377964
For human (row 1) and minors (last row):
In[]:=
N[SpearmanRho[matrix[[1]],Last[matrix]]]
Out[]=
-0.285714
Then I applied singular value decomposition (SVD), which returns three matrices whose product produces the original matrix. These three matrices represent the relationship between the meaning of the individual words, the relationship between the meaning of the individual words and their meaning in the context of the documents, and the meaning of the documents, respectively [5]. By manipulating the second matrix from SVD (the matrix representing the relationship between the meaning of the individual words and their contextual meaning in the documents) and then multiplying this new matrix by the remaining two unmodified matrices I can produce a matrix displaying inferred relationships between words and documents [6].
The three matrices from SVD:
In[]:=
{W,S,P}=SingularValueDecomposition[N[matrix],UpTo[Infinity]];Column[{TableForm[W],TableForm[S],TableForm[P]},Dividers->All]
Out[]=
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Checking that product of three matrices from SVD Matches original matrix:
In[]:=
Chop[W.S.Transpose[P]]==matrix
Out[]=
True
I modified the second matrix from SVD, matrix S, by setting all but the highest 2 values equal to 0 because I want to identify two topics. This modification results in the inference by removing unnecessary information about the relationship between the meaning of the words and their meaning in the context of the document. In reducing the amount of known data, there is room for estimation of the relationship between the words and the documents in the matrix made by replacing matrix S with its modified version. Following this modification the word frequency for a document can be greater than zero even if the original document didn’t contain that word, since the original document could have contained that word because of its topic.
In[]:=
S2Highest=PadRight[S[[All,#]]&/@{1,2},Dimensions[S]];MatrixForm[S2Highest]
Out[]//MatrixForm=
3.34088 | 0. | 0. | 0. | 0. | 0. | 0. | 0. | 0. |
0. | 2.5417 | 0. | 0. | 0. | 0. | 0. | 0. | 0. |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
In[]:=
reducedMatrix=W.S2Highest.Transpose[P];TableForm[reducedMatrix,TableHeadings->{titleWords,Table[StringJoin["doc",ToString[i]],{i,Length[titles]}]}]
Out[]//TableForm=
doc1 | doc2 | doc3 | doc4 | doc5 | doc6 | doc7 | doc8 | doc9 | |
human | 0.162058 | 0.400498 | 0.378955 | 0.467566 | 0.175954 | -0.0526549 | -0.115143 | -0.159102 | -0.0918383 |
interface | 0.140585 | 0.369801 | 0.328996 | 0.400427 | 0.164972 | -0.0328155 | -0.0705686 | -0.0967683 | -0.0429807 |
computer | 0.152449 | 0.505004 | 0.357937 | 0.410107 | 0.236232 | 0.0242165 | 0.0597805 | 0.0868573 | 0.123966 |
user | 0.258049 | 0.841123 | 0.60572 | 0.697357 | 0.392318 | 0.033118 | 0.0832449 | 0.121772 | 0.18738 |
system | 0.44879 | 1.23436 | 1.05086 | 1.2658 | 0.556331 | -0.07379 | -0.154694 | -0.209598 | -0.0488795 |
response | 0.159554 | 0.581682 | 0.375219 | 0.416898 | 0.276541 | 0.0559037 | 0.132218 | 0.188911 | 0.216908 |
time | 0.159554 | 0.581682 | 0.375219 | 0.416898 | 0.276541 | 0.0559037 | 0.132218 | 0.188911 | 0.216908 |
eps | 0.218463 | 0.549581 | 0.51096 | 0.628058 | 0.242536 | -0.065411 | -0.142521 | -0.196612 | -0.107913 |
survey | 0.0969064 | 0.532064 | 0.229914 | 0.211754 | 0.266525 | 0.136756 | 0.314621 | 0.444441 | 0.424969 |
trees | -0.0612539 | 0.232108 | -0.138898 | -0.265646 | 0.144925 | 0.240421 | 0.546147 | 0.767374 | 0.663709 |
graph | -0.064677 | 0.335281 | -0.145641 | -0.301406 | 0.202756 | 0.305726 | 0.694893 | 0.976611 | 0.84875 |
minors | -0.043082 | 0.253906 | -0.096667 | -0.207858 | 0.151913 | 0.221227 | 0.502945 | 0.706912 | 0.615504 |
I again used SpearmanRho to find correlation between title words after LSA. Notice that the correlations are different after the inference was made, with “human” and “user,” which were fairly close being even more closely related and “human” and “minors,” which were originally closer than “human” and “user” not being as related.
For human and user
For human and minors
Applying LSA to stories
Applying LSA to stories
I applied LSA to the following short stories to determine the proximity of the stories’ topics. In order to implement LSA I needed to reformat each document into a “bag of words,” since order does not matter with LSA, and deleted stopwords, which are words such as “and” and “the” that do not add meaning individually. Then I selected the most common nouns from each story as my words.
Original documents [7, 8, 9, 10, 11, 12]:
Delete stopwords:
Found 10 most common words in each story and selected nouns:
Matrix with number of times chosen nouns appeared in each story. Rows correspond to the nouns and columns correspond to the stories.
Once I had the storyMatrix storing the original relationship between documents and words, I applied SVD and removed information from matrix storyS to obtain the inferred relationships between the documents and words.
Applying SVD to storyMatrix to obtain 3 matrices whose product reproduces the original:
The matrices from SVD do represent storyMatrix because Union of the differences between the entries of the two matrices is a list of zeros, therefore, the matrices are equal. I used Chop to show that the difference between elements of original matrix and reconstruction from SVD matrices is very close to zero:
Reconstructing approximation of original matrix by setting all but highest 2 values in storyS to 0, so that this new matrix can be used in our product to infer the frequency of words in documents:
Constructing matrix with inferences about word occurrence in stories based on existing words. Notice that some of the frequencies are now negative, which means that some words have less than 0 chance of appearing in certain documents.
Then I used SpearmanRho to find correlations between words in nouns.
For “mountain” and “desert,” applying LSA lowered the likelihood of these words appearing in the same story, which makes sense because they describe two different settings.
Correlation for “mountain” and “desert” before LSA:
Correlation for “mountain” and “desert” after LSA:
For “bog” and “girl” the initial correlation was low because “bog” only appears in one document, whereas as “girl” appears in multiple documents. The high correlation after LSA makes sense because these words appear in the title of one of the documents, “Bog Girl,” so these words are closely related. The correlation of 1. implies that they always appear together.
Correlation for “bog” and “girl” before LSA:
Correlation for “bog” and “girl” after LSA:
In addition to showing that my implementation of LSA is applicable beyond the title words example, these correlations demonstrate future classifications of comparison, such as comparing setting words to determine story similarity.
Gibbs Topic Allocation
Gibbs Topic Allocation
Gibbs sampling is a method that works iteratively, starting with randomly assigned values, so probabilities are improved after each step. I used Gibbs sampling in place of the Dirichlet distribution to allocate topics using a process similar to latent Dirichlet Allocation (LDA). My method, like LDA, defines a given number of topics based on the words in a set of documents. I explored Gibbs topic allocation because I was interested in seeing which topics would be generated for Russell’s stories.
To implement my Gibbs method based on LDA, I used one of Edwin Chen’s examples in his response to “What is a good explanation of Latent Dirichlet Allocation?” [13].
Cleaning the documents by removing stopwords:
I implemented Gibbs topic allocation to identify 2 topics because the documents I used to test my method were each one sentence long. Originally I used “A” and “B” as my topics, but I switched to using numbers to make it easier to implement Gibbs topic allocation with more than 2 topics.
Randomly assigning each word a topic:
AssignProbs assigns an initial weight to each word. Weights are the product of the probability of topic t given document d and the probability of word w given topic t. This function finds those probabilities based on the inputted topic assignment. For example, inputting the randomly assigned topics from randTopics would result in weights based on randomness.
The function assign2Topics reassigns topics based on the inputted topic assignment and its weights. When a word was incorrectly assigned during random assignment, its assigned weight for that topic will be lower, so the word will eventually be assigned to a different topic. Reassignment is an iterative process that improves each time. Given that the documents being used are only sentences, the duration of reassignment will vary depending on the accuracy of the initial random topic assignment.
Assigned topics after running assign2topics 25 times. Note that this is a fairly small number of iterations, so the final assignments will vary in accuracy.
Gibbs topic allocation for more than 2 topics
Gibbs topic allocation for more than 2 topics
I then implemented Gibbs topic allocation for more than 2 topics because the larger the collection of documents, the higher the number of possible topics. Since topic generation with this method is iterative, I plan to see if a pattern emerges for 3 topics within each of the topics generated for Russell’s stories. However, as seen with assign2topics, a large number of iterations is necessary, which will affect the accuracy of my application of Gibbs topic allocation to Russell’s stories.
Rather than calculating the probabilities needed for Gibbs sampling within the same function assigning random probabilities, I created functions to find the probability of a topic, t, being in a document and the probability of a word, w, being assigned to a topic into shorter, helper functions.
Rather than calculating the probabilities needed for Gibbs sampling within the same function assigning random probabilities, I created functions to find the probability of a topic, t, being in a document and the probability of a word, w, being assigned to a topic into shorter, helper functions.
randomTopicAssign randomly assigns each word a topic:
Randomly assigning 3 topics to the words in cleanDocs:
Calculates the probability of topic t in each document:
Calculates the probability of a word w for each topic:
The probability of each word for all 3 topics (each sublist has the word’s probability for topic 1, topic 2, and topic 3):
calcDocProbs uses wordWeight and topicWeight to calculate the weights for each word. The weights for a word are the product of wordWeight and topicWeight for each topic. When I first wrote calcDocProbs I encountered a name collision bug because I used t to represent topic in calcDocProbs, wordWeight, and topicWeight.
The weight for the word “ate” for topics 1, 2, and 3 (topic number is second element of each sublist and the third element is the weight):
Assigns a topic to each word based on the weights from calcDocProbs:
Applying reAssignTopics with three topics to my test sentences had varying results because these sentences really only have two topics:
Applying Gibbs topic allocation to short stories
Applying Gibbs topic allocation to short stories
When I first applied reAssignTopics to Russell’s stories, even though the stopwords were deleted, punctuation was still present. After deleting the punctuation, I stored the stories in a list to make them easier to access.
Deleting punctuation and assigning stories to list of six Russell stories:
Having reformatted the stories, I began the process of Gibbs topic allocation with three topics. I randomly assigned a topic to each word and then used reAssignTopics.
Randomly assigning topics to each word in the six Russell stories:
When I first tried applying reAssignTopics to the six Russell stories at once, the run time was quite long. I compared the AbsoluteTiming results of reAssignTopics with two stories at once and the results of applying reAssignTopics separately to the same two stories using Table. Using Table cut the run time roughly in half, so I proceeded applying reAssignTopics to each story separately.
Run time for two stories at once was about 274 seconds:
Run time for two stories separated with Table was about 135 seconds:
While reassigning the topics for the two stories separately, it is important to remember the curly braces around the first and second entries of reAssignTopics because the function expects a list of lists.
Applying reAssignTopics ten times, with the topic assignment improving each time:
I analyzed the first thirty words for each of the three topics to try to determine the three topics. Considering that ten iterations is not large, these topic assignments are likely lacking in accuracy. My approximations of the topics are wildlife for topic 1, mountain activities for topic 2, and travel for topic 3.
Thirty words from topic 1:
Thirty words from topic 2:
Thirty words from topic 3:
While topic approximation is not an exact science, certain words do repeat within the topics, which suggests that Russell’s stories do have topics in common.
Conclusion
Conclusion
Future work
Future work
I would like to further analyze the output from LSA and Gibbs topic allocation. I also hope to reduce the run time for reAssignTopics. For both LSA and Gibbs topic allocation I would like to replace words with their stems when formatting documents to make these methods more realistic. In addition, I would be interested in applying LSA to topics identified using Gibbs topic allocation. Concerning Gibbs topic allocation, I would like to implement LDA.
Acknowledgements
Acknowledgements
I would like to give a big thank you to Eric Rimbey for all of his help and guidance, especially explaining Gibbs sampling. Thank you again to Rory for making WELP possible.
References
References
[7] Russell, K. (2015). The Prospectors. The New Yorker. Retrieved from https://www.newyorker.com/magazine/2015/06/08/the-prospectors
[8] Russell, K. (2014). The Bad Graft. The New Yorker. Retrieved from https://www.newyorker.com/magazine/2014/06/09/the-bad-graft
[9] Russell, K. (2010). The Dredgeman’s Revelation. The New Yorker. Retrieved from https://www.newyorker.com/magazine/2010/07/26/the-dredgemans-revelation
[10] Russell, K. (2018). The Orange World. The New Yorker. Retrieved from https://www.newyorker.com/magazine/2018/06/04/orange-world
[11] Russell, K. (2016). The Bog Girl. The New Yorker. Retrieved from https://www.newyorker.com/magazine/2016/06/20/bog-girl-by-karen-russell
[12] Russell, K. (2021). The Ghost Birds. The New Yorker. Retrieved from https://www.newyorker.com/magazine/2021/10/11/the-ghost-birds
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Implementation of latent semantic analysis and Gibbs sampling topic allocation
by Sophie Chen
Wolfram Community, STAFF PICKS, February 8, 2025
https://community.wolfram.com/groups/-/m/t/3389307
by Sophie Chen
Wolfram Community, STAFF PICKS, February 8, 2025
https://community.wolfram.com/groups/-/m/t/3389307