Latent Semantic Analysis

Everything on this page is fitted to one of two collections, and it is worth knowing exactly what is in them before any method touches them. The larger one is twenty-four documents, twelve about cooking and twelve about sailing. The cooking half is written from ten words, flour, sugar, butter, eggs, oven, bake, stir, whisk, dough and pan; the sailing half from ten of its own, sail, wind, boat, harbour, anchor, tide, mast, rope, deck and crew.

No content word appears in both halves. What the two halves do share is three words carrying no subject at all, and, the and we, and each document uses exactly one of them.

Each document is six words long, five consecutive words of its own half taken in a cycle and one of the three shared words, so every word of a half keeps the same company as every other word of that half. That arrangement is deliberate and it is what makes the claims later on testable, since prose written naturally has themes inside a subject, bake and oven against whisk and eggs, and those would compete with the difference between the subjects for the strongest direction.

The smaller collection is four documents of three words each, the cat sat, the cat ran, the boat sailed and the boat sank. It is here because every number that comes out of it can be checked with a pencil, and because its whole table fits on the screen at once.

Write down one row for every distinct word and one column for every document, and in each cell put how many times that word was used in that document. That is the whole of the input. Nothing about order survives it, so the cat sat and sat the cat give the same column, and nothing about which document came first survives it either.

The reason this one table can answer two different questions is that it can be read along either axis. Read a column and a document has become a list of numbers over the vocabulary, which is what it means to say a document is a point. Read a row and a word has become a list of numbers over the collection, which is the same claim about a word.

Neither reading needs anything the other does not have, so a method that works on the table is answering both questions at once whether or not it meant to.

…

Seven distinct words over four documents gives 28 cells, and 12 of them hold anything, so 57.1% of the table is empty even at this size. The row of the is 1, 1, 1, 1, and the row of sat is 1, 0, 0, 0. Those two rows are the two extremes the rest of this page is about.

Take two documents from the cooking half, flour sugar and butter eggs oven and we bake stir whisk dough pan. Both are about cooking, both were written from the same ten words, and by the cycle that built them they happen to share no word at all. Compare their columns and the answer is exactly zero, because two lists of numbers that are never both non-zero in the same place have nothing to multiply together.

Now take that first document against a sailing one, sail wind and boat harbour anchor. They share the word and, and nothing else. The table rates that pair at 0.1483, which is higher than the 0.0000 it gave the two cooking documents. Read literally, the collection is saying that a document about cooking is more like a document about sailing than it is like another document about cooking.

…

This is not one unlucky pair. Of the 132 pairs of documents drawn from one half, 14 come out at exactly nothing, and so do 96 of the 144 pairs that cross the halves. Among words the clash is sharper. Ten of the 90 pairs taken from one half score exactly zero, and the mean over every pair made of a cooking word and a sailing word is exactly zero as well, so flour against bake and flour against anchor are the same number and the table cannot tell the two situations apart.

Look again at the row of the in the four-document table. It reads 1, 1, 1, 1. That row is a perfectly good description of the word, in the sense that it is exactly what the collection observed, and it is useless for telling one document from another, because whatever question is asked of it the answer is the same for all four columns.

The damage is not only that the row says nothing. It is that the row is loud. Under plain counts the takes a third of the weight of every column, so a third of what any comparison of two documents is reading is a quantity that is identical in both and could not possibly separate them. Every document is being pulled towards every other by the same amount, and that pull is a third of the signal.

The repair is to multiply each count by a weight that falls with the number of documents the word turns up in. A word used ten times in a document really is more about that document than a word used once, so the count is kept; a word used in every document really does separate nothing, so the count is discounted by how widely the word is spread.

weight(word) = log( (1 + documents) / (1 + documents holding the word) ) + 1

The additions inside are a smoothing, and they behave as though one extra document contained every word once. Without them the weight would be the logarithm of the number of documents over the number holding the word, which is exactly zero for a word in every document, and a weight of zero deletes the row outright. With them the same word gets a weight of one, so it counts for less than everything else and still counts.

the:              ln(5/5) + 1 = 1
cat, boat:        ln(5/3) + 1 ≈ 1.5108
sat, ran, sailed, sank: ln(5/2) + 1 ≈ 1.9163

Switch the table in step 2 to weighted counts and watch what stays put. Every cell that was empty is still empty, since a weight multiplies a count and cannot create one, and every cell that was filled is still filled. The weighting changes how loud each row is and changes nothing about which cells the collection ever wrote in, which is the limitation Part 6 comes back to.

On the twenty-four documents the weighting moves very little, and it is worth reporting that rather than the usual claim made for it. No word appears in every document there. The three shared words are each in eight documents and the subject words in five to seven, so the weights run only from 2.0217 to 2.4271 and the most common word is barely held back at all.

The effect is nearly absent because this collection was built without a word common enough for the weighting to work on. It is therefore a poor demonstration of the weighting, and it also means that no claim later on this page is being propped up by it. Every one of them holds under both weightings, and the playground has a switch so that can be checked rather than taken on trust.

The squeeze rests on a fact about matrices that predates all of this. Any table can be written as a sum of simple pieces, each piece a direction over the words paired with a direction over the documents and a single number saying how much of the table that pairing accounts for. Sort the pieces by that number and keep the largest few, and what is left is the closest table of that rank there is.

X  =  U S Vᵀ,   and keeping the k largest gives   X(k) = U(k) S(k) V(k)ᵀ

Closest is meant strictly. Add up the squared difference between every cell of the original and the corresponding cell of the rebuild, and no other table of that rank scores lower. The size of that error is known in advance too, since it is exactly the sum of the squares of the numbers that were thrown away.

sum over every cell of ( X − X(k) )²  =  the sum of the discarded squared numbers

A rebuilt table has entries in cells the collection never wrote in, and that is the entire point rather than a side effect. Take the row of flour. In the collection it holds a weight in six of the twelve cooking documents and nothing anywhere else. Keep two directions, rebuild, and the row holds about 1.1 in all twelve cooking documents and no more than a hundredth in any sailing one.

…

The fit has decided that flour belongs to the cooking documents it was never used in, from nothing but the company it kept in the six where it was. Across the whole table the cells the collection left empty come back at 0.4043 on average, and the largest of them at 1.2970, which is more than half of the 2.2730 that a single observed use of flour carries.

It also fills some of them in with numbers no count can be. At two directions kept, 104 cells of the rebuild are below zero, the least of them at −0.0149; at eight directions kept the figures are 208 cells and −0.3643. Nothing in the arithmetic forbids that, because the fit is minimising a squared difference over a whole table and has never been told that its entries are counts.

Each kept direction carries a share of the table, its own number squared over the total of every number squared. Those shares are worth reading because they say how much a cut is discarding, and because the shape of the sequence says whether the collection has a few strong patterns in it or many weak ones.

…

The last row is the one to notice. The running total reaches the whole table at the fourteenth direction and never moves again, because twenty-three words over twenty-four documents arranged in this cycle leave only fourteen directions with any spread in them at all. Asking for a fifteenth is asking for a direction that accounts for nothing, and the coordinates every word and document get on it are zero.

Part 1 left two cooking documents rated at exactly nothing and a cooking document rated above them by a sailing one. Rebuild the table from two directions and compare the same pairs. The two cooking documents come out at 0.9998 and the cross-half pair falls to 0.0819, so the ordering has reversed and the reversal is the method doing the job it was invented for.

Among words the same thing happens and the numbers are cleaner. Flour against bake, which the collection rated at exactly zero because the two never shared a document, comes out at 1.0000. Flour against anchor, which the collection also rated at exactly zero, comes out at −0.0028. The two pairs that the table could not tell apart are now at opposite ends of the range.

A natural expectation about the strongest direction is that it is the one the collection divides along, so that cooking documents land at one end of it and sailing documents at the other. That expectation is wrong, and it is wrong for a reason that has nothing to do with this collection.

A table of counts has no negative entry in it. A theorem of Perron says that a matrix with no negative entry has a leading direction with no negative entry either, so every document gets a coordinate of the same sign on it. A direction on which nothing is negative cannot put two groups on opposite sides, since there are no opposite sides to be on.

…

Measured on the twenty-four documents, every coordinate on the leading direction lies between 2.6501 and 2.8994, and the two halves’ means come out at 2.7948 and 2.7948, differing by 4.4 times ten to the minus sixteen, which is the last bit of a double-precision number rather than a difference. That direction carries 26.3% of the table, more than any other, and it says nothing whatever about which half a document is in.

Switch the strip above to the second direction. Every cooking document is now negative and every sailing document positive, with the two means at −2.5388 and 2.5388, and no document is anywhere near the line. The split the first direction could not make is complete on the second, which carries 21.7% of the table.

The words agree with the documents, since they came out of the same decomposition. The three words both halves use, and, the and we, have second coordinates of zero to fifteen decimal places, which is the fit saying that a word used equally on both sides has no position on the direction that tells the sides apart. Every cooking word is on one side of them and every sailing word on the other.

                  the cat sat   the cat ran   the boat sailed   the boat sank
the cat sat            3             2               1                1
the cat ran            2             3               1                1
the boat sailed        1             1               3                2
the boat sank          1             1               2                3

every document alike              3 + 2 + 1 + 1  =  7
cat pair against boat pair        3 + 2 − 1 − 1  =  3
one cat document against the other        3 − 2  =  1
one boat document against the other       3 − 2  =  1

The other decomposition on this site starts by moving the data so that its mean is at the origin, and that step is exactly what is missing here. It is worth doing to the same table, once, to see what the omission costs and what it buys.

Subtract from every row its own mean across the documents and decompose what is left. The leading direction is now the separating one, with the cooking half at 2.5388 and the sailing half at −2.5388, and it carries 29.4% of the table against the 26.3% the unshifted leading direction carried. Every negative entry the shift introduced is what makes the sign change possible, and Perron no longer applies because the matrix is no longer non-negative.

So why not shift? Because the table has an interpretation the shifted one loses. An entry of the table as counted is a weight a document actually gave a word, and a rebuilt entry is a guess at the same quantity, which is what makes the rebuild readable and what makes a new document foldable into the space later.

Shifting also fills every empty cell with the negative of a row mean, which on a table that is 73.9% empty means almost the whole of it stops being sparse, and on a real collection that is the difference between a computation that fits in memory and one that does not.

The decomposition hands back two sets of directions, one over the words and one over the documents, and both are scaled by the numbers that say how much each direction accounts for. That gives a coordinate list for every word and a coordinate list for every document, in one space, from one fit.

position of a word = U(k) S(k)        position of a document = V(k) S(k)

The scaling by those numbers is not decoration. Without it every direction would count alike, and with it the inner products between two words reproduce exactly the inner products of the rebuilt table, which is the quantity the fit was chosen to get right. The same holds for two documents.

…

At six directions kept, the words nearest flour are sugar at 0.8777, pan at 0.8561, butter at 0.6810, then the shared word and at 0.6756, then dough at 0.6193, and the documents nearest the first one are flour sugar butter the eggs oven at 0.9963, pan flour and sugar butter eggs at 0.9161 and sugar butter eggs the oven bake at 0.8686. The first of those shares five content words with the first document and the other two share four each, which is the ordering anybody would have written by hand.

The two directions that separated the halves so cleanly also flattened everything inside a half. Every pair of cooking words comes out between 0.9999 and 1.0000, so the fit cannot tell flour from sugar, and cannot tell either of them from any of the other eight cooking words. Every pair of cooking documents comes out at 1.0000 as well, so asking which document is nearest the first one returns a list in which every entry is at the top.

The table as counted does better at that question, and it is worth saying so plainly. Its angles between two cooking words run all the way from 0.0000 to 0.8571, which is a real ordering, and the fit at two directions replaces that ordering with a single value. Switch the widget in Part 1 to the second view and the amber band collapses to a point at the second row.

Six directions is where both things are true at once, with the halves still apart at 0.0000 across and the words of one half spread from 0.0727 to 0.9553. Nothing computed during the fit turns over as the width passes that value, and the shares in step 9 do not point at it either, since they fall smoothly. The width is a judgement made from outside.

A collection that has been fitted once should not have to be fitted again to say where a new text belongs. Weight the new text’s counts over the vocabulary already fitted, then multiply by the directions over the words, and the answer is a position in the same space as everything else.

position of a new document = U(k)ᵀ x,   with x weighted by the fitted weights

The weights have to be the fitted ones rather than weights recomputed from the new text, since a word’s weight is a statement about the collection and a single new document would say that every word in it is equally rare. Applied to a document that was in the fit, the same arithmetic returns exactly the position that document already had, which is how the two routes are held together.

Type a text into the box under the playground to try this. A text built from cooking words appears among the cooking documents and one built from sailing words among the sailing ones, and a text built from words the collection never saw appears at the origin with a note saying why.

The table on the twenty-four documents holds 552 numbers. A fit keeping two directions holds 46 for the words, 48 for the documents and 2 for the directions themselves, which is 96, and a fit keeping six holds 288. That is the trade the method offers, and at this size it is a factor of about six.

factorized storage = 23k + 24k + k = 48k values
original table = 23 × 24 = 552 values

The saving looks thin because the collection is tiny, and the shape of the arithmetic says why it is not thin in practice. The table grows as the vocabulary times the number of documents and the fit grows as their sum times the width, so at a hundred thousand words and a million documents the table has a hundred billion cells and a fit at three hundred directions has about three hundred and thirty million numbers.

A cell holding zero means the collection did not observe that word in that document. It does not mean the word does not belong there, and the table has no way of saying which of the two it meant. On the twenty-four documents that is 408 of the 552 cells, and on a real collection it is essentially all of them.

The squeeze does not treat those cells as unknown. It minimises the squared difference over every cell of the table, so a cell holding zero is an observation of the value zero and the fit is penalised for placing anything else there. A word that truly belongs to a document it was never used in and a word that truly does not belong there are pushing the fit in exactly the same direction with exactly the same force.

That is a real modelling choice with a cost that can be stated. Treating an empty cell as unknown rather than as a zero is a different problem, the one a recommender solves when most of the ratings are missing, and it has no closed-form answer of this kind; the decomposition here is exact and quick precisely because it is allowed to assume every cell was observed.

The directions are chosen to account for as much of the table’s squared size as possible, and that is a statement about where the numbers vary, not about what anyone wants to know. Nothing in the procedure looks at a subject, a label or a question. The strongest direction on this collection carries 26.3% of the table and measures how much common vocabulary a document uses.

So a direction describes whatever the collection happened to vary along. Assemble a collection where every document is about one subject and differs only in length, and the leading directions describe length; assemble one where half the documents were transcribed by a different typist, and they may describe the typist. The method has no way to prefer one of those to another, and a fit gives no sign that it has found something uninteresting.

A related consequence is that the individual coordinates carry no meaning even when the fit is good. Two directions of equal strength are only determined up to a rotation within the plane they span, so the pair can be turned arbitrarily and the rebuild is unchanged. The four-document collection has exactly that, since its third and fourth numbers are both exactly 1, so its third and fourth directions are settled by the arithmetic and not by the data.

Each direction is also determined only up to a sign, since flipping a word direction and its matching document direction together leaves everything the fit says unchanged.

The table has one row for each distinct spelling, so a word used for two unrelated things contributes both sets of company to one row and gets one position. There is no second position for the second sense to occupy, because there is no second row.

This is where the method states the limitation most plainly of anything on these pages, since the row is right there to look at. Take the running collection and respell one cooking word and one sailing word as roll, a bread roll in one half and the roll of a boat in the other. Nothing else changes.

…

Roll lands at zero on the direction that separates the halves, in the same place the three words carrying no subject sit, and its nearest neighbours are those three words at 1.0000, 0.9997 and 0.9997. It is 0.7219 from flour and 0.7050 from sail, almost the same distance from both. One row holds the company of both senses at once, and the position that fits both sets of company is the one halfway between them, which is where the words carrying no subject already sit.

Several inputs leave the method with nothing to work out rather than something approximate to work out, and a few more leave it with a genuine choice whose cost is worth knowing. The table gathers both, with what the mathematics says in each case.