Pooling a Text

Suppose every word already has a position, so that a text of eight words is eight positions, and suppose we want to ask whether two texts are about the same thing. Nothing about eight positions answers that. We could compare them word against word, but the two texts will not be the same length, and even where they are, the third word of one has no reason to line up with the third word of the other.

Anything downstream that reads a fixed number of inputs, which is most things, cannot take a text at all until the text has been reduced to a fixed number of them.

The obvious answer is to lay the positions end to end. Each position here is four numbers, so an eight-word text becomes thirty-two of them and a three-word text becomes twelve, and the two cannot be handed to the same reader. Padding the short one out to the length of the long one buys a fixed width and loses the meaning, because the fourth word of one text now shares a slot with the fourth word of the other and there is no sense in which they belong together.

Pooling is the other answer. Combine the positions into one position of the same width, so that a text of three words and a text of thirty both come back as four numbers, and let the combining rule decide what survives.

one text  ↦  one position of a fixed width

A word’s position is learned from usage, so nothing here can be shown on a single sentence, and every number on this page comes from one of two collections. The larger is twenty-four documents of six words each, twelve about cooking and twelve about sailing, written from ten cooking words and ten sailing words with no content word appearing in both halves.

Every document also carries exactly one of three words that carry no subject at all, and, the and we. Twenty-three words in all, and each of them has a position of four numbers, found by counting which words keep company with which inside a short window.

The smaller collection is six documents of four words each, built on a table of seven positions written down by hand rather than fitted. Three of its words point along the first axis and three along the second, so it has two subjects the way the larger one does, and the seventh word, the, points along a third axis and is twice as long as any of the others.

It is here because every number that comes out of it can be checked with a pencil, and because it is arranged so that the failure Part 3 is about is visible in a single document.

Three texts run through the page from here on. Two of them are about sailing and one is about cooking, and they were written so that no two of them share a word that carries a subject. What all three do share is and, the and we, in the same numbers, and that is deliberate, because it is the case where a rule that reads only which words a text used has nothing at all to go on.

A reader can try any of this on any text through the panel at the top of the page, which is the same calculation the sections below quote from. The rule to watch is whether the first and third come out nearer to each other than either does to the second, since that is the one fact about them nothing was told.

There is an answer to the whole problem that never asks what a word means. Give every word of the vocabulary a slot, and let a text be how many times it used each of them. Order is gone immediately, since a count says nothing about where the word was, and what is left is a fixed-width position after all, because the vocabulary is fixed even though the texts are not. This is the bag of words, and it is the baseline every method below has to beat.

count(text)₁ , count(text)₂ , … , count(text)ₘ

Two texts are then compared by the angle between their count vectors. The length of a count vector grows with every word counted, so a long text is a long vector whatever it is about, and dividing each vector by its own length puts every text on the same sphere before any comparison happens. After that the angle and the distance agree, and length has stopped carrying anything.

Take the cat sat, the dog sat and a cat as a collection of three. Counting occurrences, cat, sat and the appear twice each and a and dog once, so with ties broken alphabetically the slots run cat, sat, the, a, dog. Under plain counts the second document is one in the slot for sat, one for the and one for dog, and zero elsewhere.

idf(w)  =  log( (1 + N) / (1 + documents holding w) )  +  1

cat, sat, the: ln((3 + 1) / (2 + 1)) + 1 ≈ 1.2877
a, dog:        ln((3 + 1) / (1 + 1)) + 1 ≈ 1.6931

counts:   (0, 1, 1, 0, 1)
weighted: (0, 1.2877, 1.2877, 0, 1.6931)

The last thing this small collection shows is what happens to a word it has never seen. The text the zebra sat comes back as (0, 1.2877, 1.2877, 0, 0), with zebra contributing nothing at all, because a word with no slot has nowhere to put anything. That is not a refusal and it is not an approximation. It is the rule being honest that it has never met the word.

On the larger collection the weighting is the same and its effect is small, because that collection was built so that every content word is used about equally often. The three words carrying no subject are each used eight times across the twenty-four documents and every content word between five and eight times, so the weights run from about 2.02 up to about 2.43, a spread of a fifth rather than of an order.

That is worth stating plainly rather than glossing, since the rarity weighting is usually introduced on a collection of real prose where the commonest word is a thousand times commoner than a rare one and the weight really does change the answer. Here it moves the score for the three texts from a margin of 0.0000 to a margin of 0.0040, which is not nothing and is not much.

Now the three texts. Each of them uses the twice, and twice, we once, and three content words no other text shares, so the part of any two of them that overlaps is exactly the same five tokens, and the part that does not overlap is exactly three tokens in each. The angle between any two of them therefore has to be the same angle, and it comes out at three quarters for all three pairs.

squared length = 2² + 2² + 1² + 1² + 1² + 1² = 12
dot product from shared words = 2 × 2 + 2 × 2 + 1 × 1 = 9
cosine similarity = 9 / (√12 × √12) = 9/12 = 0.75

The same failure is measurable across the whole collection rather than on three texts. Two documents of one half that happen to share no content word score exactly zero against each other, while two documents of different halves that share a word carrying no subject score 0.1667. So the least alike same-half pair is further apart than the most alike different-half pair, and the gap runs the wrong way by 0.1667. Weighting the counts by rarity does not repair that, since its worst same-half pair is at zero too.

If the words already have positions, the cheapest thing to do with a text is to stand at the middle of them. Add the positions of the words the text used, divide by how many there were, and the result is a position of the same width as any word’s. A text of three words and a text of thirty both come back as four numbers, and a word the table has never seen is skipped rather than guessed at.

v(text)  =  (1 / n) · ∑ v(w)   over the n words of the text

It sounds too crude to work and it is not. What a short text is about is mostly which words it holds, the positions of words about one subject are near each other, and the middle of several nearby positions is near all of them. The mean carries that, which is enough for a great many questions, and the sections after this are about the specific ways it falls short rather than about it failing.

Here is the whole argument for pooling in one number. The first and third texts share no content word, so counting scored them at exactly the same 0.7500 it scored every other pair. Averaging their words’ positions puts them at 0.8737 against each other and at 0.6631 and 0.6142 against the cooking text, so the two that are about the same thing come out ahead by 0.2106.

Nothing told the average which texts were about sailing. It reached that because crew, boat and sail sit near wind, tide and anchor in the table it was handed.

…

Every rule on the page, scored across the whole of a collection rather than on three texts. Watch the top two rows, which are the counting rules, where the far end of the indigo bar lies to the left of the far end of the amber one, so a pair of documents about the same subject can be further apart than a pair about different ones.

Across all twenty-four documents the same thing shows. Counting puts two same-half documents at 0.4343 on average and two different-half documents at 0.0556, a gap of 0.3788, but its worst same-half pair is at 0.0000 and its best different-half pair at 0.1667, so its margin is negative. The plain average puts the two averages at 0.7947 and 0.1346, a gap of 0.6601, and its worst same-half pair at 0.3202 against a best different-half pair of 0.2581, so the margin is positive for the first time, at 0.0622.

A pooled position has a length, and it is worth asking what the length is a fact about before using it for anything. Under the plain average the three texts come out at lengths 0.4886, 0.5083 and 0.5279, close to each other because all three texts are eight words long and the words of each point broadly the same way.

Under the smooth weights they come out between 0.0104 and 0.0112, because no weight there is above 0.028. Under the last rule they come out between 0.0048 and 0.0062, because most of what was there has been taken out.

None of those lengths says anything about the text. They say which rule produced the vector and how big its weights happened to be, so comparing two texts by the distance between them would mostly be comparing the arithmetic that made them. The direction is where the subject was put, and the cosine of the angle between two directions is what every number on this page measures.

cos θ  =  (a · b) / ( ‖a‖ · ‖b‖ )

The usual complaint about the plain average is easy to state. Every text has the in it, the has a position like any other word, and the mean of a text’s words is pulled towards it as hard as towards anything else, so the words that carry the least about the subject get exactly the same say as the words that carry the most. On the hand-built collection that is visible in one document.

answer = (0.5, 0, 1, 0)          answer · answer = 0.5² + 1² = 1.25
share(word) = (what the word added) · answer / (answer · answer)
the:  (0, 0, 1, 0) · (0.5, 0, 1, 0) / 1.25 = 1 / 1.25 = 0.8000
cat:  (0.25, 0, 0, 0.025) · (0.5, 0, 1, 0) / 1.25 = 0.125 / 1.25 = 0.1000
dog:  (0.25, 0, 0, −0.025) · (0.5, 0, 1, 0) / 1.25 = 0.125 / 1.25 = 0.1000

…

The shares of one document’s answer, by word. Switch the rule to see the same three words divide the same answer differently, which is what a weighting does and all it does.

The consequence across the six documents is that they all end up pointing at nearly the same place. The three about animals score at least 0.9990 against each other, which is what we want, but the animal documents and the finance documents score up to 0.8349 against each other, which we do not, so the margin is only 0.1640. Two texts with no word in common and nothing to do with each other are eighty-three per cent alike because they both said the twice.

I expected the same ranking on the twenty-four documents and did not get it. Taking the first of the three texts and asking which of its words supplied most of its average, the answer is crew at 0.2069, then sail at 0.1839, then and at 0.1736 across its two uses, then the at 0.1532 across its two.

Two tokens of and together supply less than one token of crew. Across all twenty-four documents, the one word in six that carries no subject supplies 0.0649 of its document’s average, where an equal share would be 0.1667.

…

The same division of one answer, on the larger collection. The grey bars are the words carrying no subject, and here they are at the bottom rather than the top.

The reason is in the table of positions rather than in the averaging. The three words carrying no subject own the three shortest positions in it, and at 0.3708, the at 0.3667 and we at 0.5770, against content words running from 0.7327 up to 1.1628, because the table was fitted by measuring how much more often two words occur together than chance would explain, and a word that occurs with everything has no company worth reporting.

The rule that made the positions had already done part of the work the weighting was invented to do.

The repair suggests itself. If a word in every document should count for little and a word in few documents for more, then the weight Part 2 already used on counts can be used again on positions, multiplying each word’s position by its weight before adding. Divide by the total weight rather than by the number of words, and the result is a weighted mean, which sits inside the same region the words do rather than being scaled arbitrarily by how many rare words the text happened to hold.

v(text)  =  ∑ idf(w) · v(w)   /   ∑ idf(w)

In the hand-built collection, the appears in all six documents. Each other word appears in two. Their inverse-document-frequency weights are:

weight(the) = ln((6 + 1) / (6 + 1)) + 1 = 1
weight(other word) = ln((6 + 1) / (2 + 1)) + 1 ≈ 1.8473

Each content word now counts about 1.85 times as much as the. Plain averaging gave them equal weight.

On the hand-built collection it is worth a great deal. The share of the answer supplied by the falls from 0.8000 to 0.5396 and each of cat and dog rises from 0.1000 to 0.2302, and the margin between the two subjects goes from 0.1640 to 0.3871, which is more than double. The most alike pair of documents across the two subjects falls from 0.8349 to 0.6105.

On the twenty-four documents it is worth much less, for the reason Part 2 gave, which is that the weights themselves barely differ there. The margin moves from 0.0622 to 0.0819 and the three texts’ margin from 0.2106 to 0.2331. Both are real improvements and neither is the kind of change that decides whether a method works.

Arora, Liang and Ma weight by a different quantity. Instead of how many documents hold a word, they use how probable the word is across the collection, and instead of a logarithm they use a small constant divided by that constant plus the probability. It is near one for a word that almost never occurs and near zero for a word that is everywhere, and it falls smoothly between.

weight(w)  =  a / ( a + p(w) )     with a = 0.001

At the paper’s constant, a word filling half of every text weighs 0.001996, and a word appearing about once in a million weighs 0.999001. The common word is held down five hundred times against the rare one, and the sharpness of that is the point of the choice. The paper also divides by the number of words rather than by the total weight, so a text made entirely of common words comes out short rather than rescaled back up, which is a deliberate difference from the previous section and one reason the lengths in section 10 were so small.

On the twenty-four documents that sharpness has nothing to bite on. No word is commoner than an eighteenth of the collection, so the weights run from 0.017682 up to 0.027994, a ratio of 1.5832 against the 500 the paper’s own illustration reaches. Measured, the weights alone take the margin from 0.0622 to 0.1096, which is a little more than the rarity weight managed and is still not the thing that makes the method work.

Look at what is left after the best weighting so far. On the twenty-four documents the average similarity between two documents of different halves is still 0.1070 and the most alike such pair is at 0.2045, so two documents with nothing in common still point substantially the same way. Turning the weights down further would not fix it, because the problem is no longer how much each word counts.

The remaining problem is that every text of the collection is leaning in one shared direction, whatever it is about, and a weighting can only shrink a word’s contribution towards zero. It cannot subtract. Measured, the plain average of a document of this collection lies at a cosine of 0.6797 from one particular direction, never below 0.5820 and never above 0.7774, so roughly two thirds of every document’s answer is the same answer, and it is the same answer for all twenty-four.

Put every training document’s weighted average into a table, one row per document, and ask which single direction the rows lean along most. That is the leading direction of the table, and once it is known it can be taken out of every vector, leaving each document with only what distinguishes it from the rest.

v  ←  v − u · (u · v)     where u is the leading direction

Two details of how the direction is found are decisions rather than consequences. It is found from the table exactly as it stands, without first subtracting each coordinate’s mean across the documents, which is what makes this different from the decomposition on the principal components page. Centring would take the mean direction away before the search began, and the mean direction is precisely what is meant to be removed.

And a direction found this way is determined only up to its sign, since a direction and its opposite span the same line, so a convention is needed if the answer is to be a function of the collection alone. The projection is the same either way.

Nothing so far has said what that direction contains, and the honest way to find out is to ask every word in the collection how far it leans along it. On the twenty-four documents the answer is not subtle. And leans along it at 0.9897, we at 0.9848 and the at 0.9032, and the furthest any word carrying a subject reaches is 0.7087. The three words that mean nothing about cooking or sailing are the first three in the list, separated from everything else by nearly two tenths.

…

Every word of the collection, ranked by how far it leans along the direction that is about to be removed. The three grey bars at the top are the words carrying no subject, and the dashed line is where the furthest content word reaches. Switching to the smaller collection reorders the list entirely, which the note below is about.

Section 12 found those same three words to be the three shortest positions in the table, supplying less of a plain average than their share of the tokens, so this is not the textbook story about common words being loud. They are quiet and they are aligned. Every text of the collection contains them, they all point the same way, and a small quantity added to every text alike is exactly as useless for telling texts apart as a large one, which is what makes removing the direction worth more here than any weighting was.

With the direction removed, the three texts stop being variations on one theme. The two about sailing come out at 0.3633 against each other, and the sailing texts against the cooking one come out at −0.9016 and −0.5762, which is to say they now point in substantially opposite directions rather than in slightly different ones. The margin goes from 0.2637 under the weights alone to 0.9395.

Across the whole collection the same thing happens at scale. Two documents of different halves average −0.6370 against each other, where every rule before this had them positive, and the margin between the worst same-half pair and the best different-half pair reaches 0.2752, four times what the plain average managed.

There is a case on this collection where the sharpest method is beaten by the plainest one. The least alike pair of documents from the same half scores 0.3202 under the plain average and −0.0767 after the direction is removed, so two documents genuinely about the same subject have been pushed past perpendicular and now read as unrelated. The plain average kept them together and the repair separated them.

It is the same mechanism as the improvement, seen from the other side. What every document of the collection had in common was also part of what any two documents of one half had in common, so removing it removes some genuine agreement along with the spurious kind. Two documents of one half that share no content word were relying on the shared part more than most, and they are the pair that suffers.

Three costs, in the order they bite. The first is a constraint rather than a quantity, which is that the last two rules cannot score a single text at all until they have seen a collection. Counting needs a collection to fix the vocabulary, the rarity weight needs one to count documents, the smooth weight needs one to estimate probabilities, and the removal needs one to find a direction, so a text arriving on its own can be given a position only by the plain average.

The second is width, and it runs the other way. A counted text is as wide as the vocabulary, which is twenty-three numbers here and tens of thousands on real prose, and almost all of them are zero. A pooled text is as wide as one word’s position, which is four numbers here whatever the vocabulary does. That is the trade a fixed width was bought with.

The third is what cannot be got back. A counted vector is the words, so the text’s vocabulary can be read straight off it. A pooled vector is not, and asking which six words of the table lie nearest a document’s pooled position recovers 4.3333 of that document’s six words on average under the plain average, and 4.1667 under the sharpest rule, so a little under three quarters of a document is still readable off its position and the rest of it has gone.

A sum does not remember the order its terms arrived in. Every rule on this page is a sum over the words of a text, divided by something that depends on the multiset of those words and not on their arrangement, so any two texts built from the same words in any two orders are one position. This is not a limitation of a particular weighting and it cannot be repaired by choosing better weights, because it follows from the shape of the calculation.

Crew sail the boat and boat sail the crew are two English sentences that say opposite things about who is doing the sailing. Under both counting rules they come back as the identical list of numbers, agreeing in every bit. Under the four averaging rules the largest disagreement between the two lists first appears in the seventeenth decimal place, which is the order the additions ran in rather than any difference in what was computed, and the angle between them is one.

…

The same four words in two orders under every rule. The column to read is the last one, which is the angle between the two answers, and it does not move.

Four words admit twenty-four orderings and all twenty-four land on the same position, and the count of orderings grows faster than any other quantity here as the text lengthens. Whether that matters depends entirely on the question being asked, since it costs nothing when the question is what a text is about and costs everything when the question is who did what to whom.

A weight learned from a collection is a statement about that collection, and so is a direction. Change the company a text is scored in and both change, which means the same text with the same words and the same word positions has no single answer under the last rule. It has one answer per collection.

Scoring the crew and the boat and we sail against all twenty-four documents and then against the twelve sailing ones gives two positions whose cosine is −0.6124. Not two slightly different readings of one text. Two readings that point substantially away from each other, from a change in nothing but which documents were in the room.

…

Each word of the text against the direction removed under each of the two collections. Watch sail, which is nearly perpendicular to the whole collection’s direction and almost parallel to the sailing half’s.

The mechanism is visible word by word. In the whole collection the three words carrying no subject lead the direction, because they are what all twenty-four documents agree on. In the sailing half every document is about sailing, so sail is now something they all agree on too, and it leads at 0.9031 where in the whole collection it reached only 0.6551. The two directions themselves agree only to 0.7812.

Take a text with two sailing words and two cooking words in it, and ask where one position could possibly put it. It has to answer with a single direction, so it can lean towards one subject, or lean towards the other, or lean towards something in between that is neither. What it cannot say is both, since being about two things is not a direction.

…

A text about both subjects against a text about each, under every rule. The first rules put it near both, and the last one picks a side.

Both failures are on display. Under the plain average the mixed text scores 0.8862 against the sailing text and 0.9202 against the cooking one, both of which are higher than the 0.6631 those two score against each other, so the text reads as more like each of them than they are like each other, which is the answer of something that is vaguely like everything.

Under the last rule it scores −0.1187 against sailing and 0.5057 against cooking, and all four of the documents it comes out nearest are cooking documents, so a text holding crew and boat has been placed in the kitchen.

Four inputs make one of these calculations undefined rather than merely awkward, and it is worth knowing which quantity fails and why, since each one is a decision anybody implementing this has to make.

The first of those is the one that arises in ordinary use rather than in a constructed example. A text of words a collection has never met is not rare, and every rule on this page answers it the same way, which is with a position at the origin and no similarity to anything at all.