Latent Semantic Analysis in Perl
I’m currently a little into quantitative text analysis. Not big time, but a little. A nice end goal, that I have no intention of reaching, would be a script that can suggest if a cluster of articles on this site seem similar but don’t share a tag, or if there’s a tag that might as well not exist because it’s applied to a very broad range of articles. This would help me maintain the tags that are currently assigned completely manually and, as the observant reader has noticed, rather arbitrarily.
TF-IDF
I have never really done quantitative text analysis before, so I gave myself a soft first task: compute tf-idf scores for the terms used in all articles.
The code to do this is littered with special cases1 Naïve efforts to strip
out most html tags, skipping source code, Swedish articles, drafts, picking
out terms of minimum length only, treating some \w characters as term
boundaries, and so on. and probably not of interest to anyone else. The
tf-idf computation is simple enough with a nested key–value dictionary to keep
track of which articles contain each term.
The script produces a text file that lists every term along with the articles in which it is present, and the total tf-idf score for the term as well as in each article, like so:
ada 521.5157 ( 171 x 3.0498)
expressive-ada-2012-challenge 179.93817
unicode-strings-in-ada-2012 118.94218
guessing-game-ada-style 106.74298
timeout-blocking-requests-in-ada 48.79679
selective-delay-in-spark-and-ravenscar 30.49799
...
how-much-does-an-experienced-programmer-use-goo 3.04980
how-laziness-works 3.04980
dotnet-on-non-windows-platforms-brief-historic- 3.04980
probability 488.2770 ( 236 x 2.0690)
what-is-probability 175.86247
unreasonable-effectiveness-of-conditional-proba 62.06911
birthday-line-puzzle 57.93117
frequentism-and-false-dichotomies 41.37940
markov-chains-for-queueing-systems 20.68970
...
secure-dns-on-a-laptop-with-debian 2.06897
precel-like-excel-for-uncertain-values 2.06897
survival-analysis-for-customer-retention 2.06897
code 447.9971 ( 436 x 1.0275)
how-laziness-works 60.62347
expressive-ada-2012-challenge 32.88052
on-competing-with-c-using-haskell 19.52281
the-case-for-controlled-side-effects 18.49529
guessing-game-ada-style 18.49529
...
documentation-reference-manual-vs-cookbook 1.02752
current-email-solution-gpg-agent-offlineimap-not 1.02752
why-perl 1.02752
emacs 393.4511 ( 163 x 2.4138)
why-you-should-buy-into-the-emacs-platform 120.69054
migrating-away-from-use-package 55.51765
on-escape-meta-alt-control-shift-emacs 55.51765
...
starting-spaced-repetition 2.41381
dotnet-on-non-windows-platforms-brief-historic- 2.41381
swedish-colemak-hack 2.41381
system 377.2019 ( 332 x 1.1362)
markov-chains-for-queueing-systems 59.07981
predicting-resource-usage-from-increased-traffic 42.03756
statistical-process-control-a-practitioners-guid 28.40376
...
sidescrolling-flight-simulator 1.13615
fallback-font-and-good-fonts-including-recommend 1.13615
rethinking-text-input-on-touchscreens 1.13615
The list goes on for 10,000 terms. This is actually way cooler than I would have expected. It associates a word like “code” most strongly with not just articles that contain code, but articles that are, in some sense, about code.
The list of terms is ordered by highest total tf-idf, which means – if my intuition for this is correct – the top terms are ones that discriminate well between articles; they’re terms used often, but only in specific articles.
Significant Terms
Just over half of the 10,000 terms are used more than once. Here’s a rough histogram of number of terms used once, twice, and so on up to 10 times:
1: 3850 ###################################### 2: 1530 ############### 3: 864 ######### 4: 586 ###### 5: 383 #### 6: 294 ### 7: 255 ### 8: 185 ## 9: 173 ## 10: 142 # >10: 1671 #################
I don’t know if this is how the professionals do it, but to make things simpler for myself and reduce the dimensionality of the problem slightly, I picked out a subset of significant terms, by keeping only terms that were used more than 10 times, and had an idf value higher than 1.2 The point here is to focus on terms that hopefully appear in multiple places, but still aren’t meaningless terms like “time” or “that” which occur in every other article. This produced a list of 1800 terms.
In the rest of this article except as noted, all analysis is done on those 1800 terms only.
Matrix Representation
Mainly for convenience, there’s another script that converts the lookup table of terms-to-documents above to a term–document matrix, where each row is a term, each column is a document, and the corresponding cell contains the tf-idf value of that term in that document.
To keep the associations with terms and articles, the first two lines of the file that contains the term–document matrix are a list of words in the order they occur in the matrix, then a list of articles in the order they occur in the matrix. It looks something like this (truncated):
prelude alice utctime req gpg lambda agile meal toys ... what-is-probability statistical-process-control-a-pr ... 0 4.54329 0 0 0 0 0 0 0 0 0 0 0 141.38393 0 0 0 20.6 ... 0 222.62144 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 9.08659 0 0 0 0 ... 40.87633 0 199.90497 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... ...
This file accidentally stores the term–document matrix transposed, meaning there’s a row for each document and a column for each term. Conventionally, it’s done the other way around.
K-means Clustering on Raw Data
After that, I tried k-means clustering on the raw term–document matrix. This approach produced garbage. It’s possible to vary how bad the garbage is by tweaking pre-processing rules and parameters, but it is garbage all the same.
The main problem is that it finds a bunch of clusters of just one or two articles3 Which sometimes, to its credit, are related – but just as often they are not. and then it piles almost all articels into a “misc” cluster. Here’s an example of two clusters that are of non-trivial size. Note how unrelated the articles in them seem to be.
Cluster 7: book-review-parallel-agile parser-combinators-parsing-for-haskell-beginners on-competing-with-c-using-haskell starting-to-commute-by-bicycle verifiable-software-development-estimations predicting-resource-usage-from-increased-traffic underrated-technique-sampling reading-notes-guide-for-ravenscar-in-high-integrity-systems purely-functional-avl-trees-in-common-lisp scales-of-plan-driven-development timeout-blocking-requests-in-ada Cluster 8: dotnet-on-non-windows-platforms-brief-historic-summary haskell-time-library-tutorial matrix-is-everything-i-want-irc-to-be the-mystery-of-the-deterministic-super-shotgun emptying-the-dishwasher-with-systems-theory
For another taste of how devoid of insight the raw term–document matrix is, here are some words and how similar they are judged to be4 Cosine similiarity.:
(probability, probabilities) ~ 0.962887911214321 (probability, odds) ~ 0.145700881235703 (probability, sampling) ~ 0.0680276850235823 (probability, throughput) ~ 0.100707873143784
and
(functional, haskell) ~ 0.392247216407078 (procedural, haskell) ~ 0.0174985128544403 (procedural, java) ~ 0.277575389792799
It’s not that it’s completely wrong all the time, but it seems to be right in the way a broken clock is – mainly by accident, and without external reference, it’s hard to know when it’s right and when it’s wrong.
I had hoped for at least one non-garbage result, so I was a little bummed out, but I figured there ought to be a simple way to reduce the dimensionality and perhaps get more robust results.
Latent Semantic Analysis
I remembered from my university days that I tried taking apart a data set by principal component analysis, and making some quite cool discoveries along the way5 Unfortunately, the assignment was for a data visualisation class, and I had very little time to polish the visualisation after I succeeded with the analysis, so my solution was close to failed.. Maybe one can do something like that to the term–document matrix instead?
A quick web search reveals that this is an established technique called latent semantic analysis. And at first, it seems to sort of work. It comes up with some coherent themes I have written about, such as
Concept number 1, top terms: probability average probabilities event individual likely outcome usually rate events frac compute against answer week distribution mathrm theory late alice questions roughly statistical dice process variation per chance team train Concept number 5, top terms: haskell parser parse parsing data day month parsers combinators html date combinator hackage blog monad attoparsec year maybe turtle libraries char parsed text report int convert readp mean pattern function Concept number 6, top terms: development projects project authors task model agile design implementation complete parts programmers product software code deadline tasks parallel domain data cases driven book systems result system separate finished market critical Concept number 7, top terms: run server response configuration request emacs servers running process events network manager extension requests remote dns users system command extend user define defined milliseconds send alice connect event land web Concept number 9, top terms: functional code systems haskell image result performance distance components length class runs system simple programming sort classes loop calls function looks implementations ghc png recursion functions essentially level left knowledge
Not all concepts are coherent, but it looks like there’s something intelligent going on there.
What really blew me away was when I started asking it about the similarity between terms:
(probability, probabilities) ~ 0.952301678239469 (probability, odds) ~ 0.845109841511912 (probability, sampling) ~ 0.567053242317574 (probability, throughput) ~ 0.406783545108254
It has also learned something about programming:
(functional, haskell) ~ 0.66153907357199 (procedural, haskell) ~ 0.166412102018881 (procedural, java) ~ 0.729791346849553
This is baby stuff, of course, but it’s the first time I’ve made it, and it’s fascinating.
Unfortunately, if I try to go closer to the original objective of discovering similiarities between articles, also this approach seems to fail. I tweaked the parameters for what counts as significant terms to include in the analysis6 Specifically, I made it select more based on semantic relevance (high idf) than number of usages., which does seem to improve article similarity, but make term similarity a lot worse.
Anyway, these are the best results I’ve had so far:
Closest five articles to the-reinforcing-nature-of-toil:
quick-variance-computation 0.778638685528717
timeboxing-is-not-about-deadlines 0.762039700762091
learning-some-logarithms 0.75815903308222
securing-a-debian-laptop-with-a-firewall 0.748513263154762
dichotomisation-discards-data 0.737257487469376
Closest five articles to emptying-the-dishwasher-with-systems-theory:
verifiable-software-development-estimations 0.724795485238744
starting-spaced-repetition 0.719353302217007
securing-a-debian-laptop-with-a-firewall 0.698859553750974
ceasing-short-lived-maintenance-of-emacs-versor 0.666658448749324
what-optimisations-are-not 0.663293458890785
Closest five articles to on-competing-with-c-using-haskell:
text-selection-behaves-as-swipe-in-weechat 0.871357916356826
share-buybacks-are-indirect-investments 0.736398228385749
emacs-magic-simple-pastebin 0.664821850265228
matrix-is-everything-i-want-irc-to-be 0.59431696836662
confusing-uncertainty-for-information 0.592934531238207
Closest five articles to hidden-cost-of-heroics:
resize-video-while-keeping-quality-high-with-ffmpeg 0.821504405028828
why-code-review-matters-suble-often-non-breaking-bugs 0.760687478808574
historic-mistakes-carriers-and-presses 0.757533916663089
mind-the-gap-when-pdsa 0.743727177824199
recordmydesktop-videos-going-out-of-sync 0.676645616522803
This is fairly good, but does seem a bit … just-so. I can’t explain why this particular set of significant terms happen to yield okay-ish recommendations for these specific articles, nor am I very confident it performs well out of sample, given how much I’ve tweaked it to look good here.
Code
It seems unfair to leave you without at least a little code, so here’s some of the latent semantic analysis stuff in Perl:
use v5.16; use strict; use warnings; use autodie qw( :all ); use PDL; use PDL::NiceSlice; use PDL::LinearAlgebra; use utils qw( read_termdocmat cos_sim ); # Read in the term–document matrix. my ($terms, $slugs, $x) = read_termdocmat(); # Log transform seems to yield better results # than raw tf-idf values. $x = log ($x + 1); # Perform SVD using BLAS/LAPACK and extract out # term–concept matrix, document–concept matrix, # and singular values. my ($v, $s_diag, $fat_u) = $x->msvd; my $t = $fat_u(0:(nelem($s_diag)-1)); my $s = stretcher $s_diag; my $d = $v->transpose; # Truncate to 10 main concepts. my $k = 10; my $tk = $t(0:($k-1)); my $sk = $s(0:($k-1), 0:($k-1)); my $dk = $d(:, 0:($k-1)); # These are the concepts represented by each term. my $concepts = $tk x $sk; sub term_sim { # Ugly code I'm embarrassed to publish please don't hate me. my ($ta, $tb) = @_; my @terms = @$terms; my $ia = (grep { $terms[$_] eq $ta } 0..$#terms)[0]; my $ib = (grep { $terms[$_] eq $tb } 0..$#terms)[0]; my $ca = $concepts(:, ($ia)); my $cb = $concepts(:, ($ib)); my $c = cos_sim $ca, $cb; say "Similarity between $ta and $tb is $c"; } term_sim "functional", "haskell"; term_sim "procedural", "haskell"; term_sim "procedural", "java"; # These are the concepts each article is about. my $docconc = $sk x $dk; sub doc_closest { # Ugly code I'm embarrassed to publish please don't hate me. my ($sp) = @_; my @slugs = @$slugs; my $ia = (grep { $slugs[$_] =~ $sp } 0..$#slugs)[0]; my $ca = $docconc(($ia)); my @dists; for my $ib (0..$#slugs) { my $cb = $docconc(($ib)); my $c = cos_sim $ca, $cb; push @dists, $c; } say ""; say ""; say "Closest five articles to $slugs[$ia]:"; my @clost = sort { $dists[$b] <=> $dists[$a] } 0..$#dists; ## Skipping 0th because it's going to be the article itself. for (@clost[1..5]) { say " $slugs[$_] $dists[$_]"; } } doc_closest qr/toil/i; doc_closest qr/dishwasher/i; doc_closest qr/competing/i;
Next Steps
I think the main problem that needs to be solved before moving on is that of diagnostics. I can’t really say why certain parameters work better and others worse. I don’t have a good way of looking at articles the way the model sees them. I also don’t know how I would do that, because I still have some trouble interpreting the matrices involved in the latent semantic analysis.
Another approach is to just move on from linear algebra and crack open neural networks, and try to write a model based on word embeddings. I have no faith that would work better, but it is something I’ve always wanted to experiment with.