Paragraph Vectors

A position for a text has to be learned from usage, so nothing on this page can be shown on a single sentence, and every number below comes from one collection of thirty short documents. Fifteen of them are about cooking and fifteen about sailing, each eight words long, and each drawn with replacement from a list of ten words about its own subject. The two lists share no word at all, so twenty words in two hundred and forty occurrences is the whole of it.

Two texts run through the page from here on and neither of them is in the collection. One is butter garlic onion simmer broth whisk flour ladle, which is plainly about cooking, and the other is anchor tide rudder harbour keel gust mooring mainsail. They are the held-out texts, and the whole of Part 4 is about what it takes to give one of them a position after the fit has finished.

There is an obvious way to give a text a position once its words have one, which is to stand at the middle of them, and the page on pooling works through what that keeps. The finding worth carrying here is the one it ends on. Every rule of that kind is a sum over the words of a text divided by something that depends on which words they were and not on the order they came in, so any two texts built from the same words in any two arrangements land on one position.

Measured here on the held-out cooking text against its own eight words shuffled, the average of the word positions gives the two arrangements a cosine of exactly 1.0000, which is the same position and not a very near one. That is not a weakness of a particular weighting and no better weighting repairs it, because it follows from the shape of the sum.

v(text)  =  (1 / n) · ∑ v(w)   over the n words, in any order

Here is the other way. Instead of building the text’s position out of its words’ positions, give the text a row in the table, exactly as a word has one, and learn it. The row starts as a small random draw and is moved by the same rule that moves the words’ rows, so at the end of the fit it holds whatever it turned out to need to hold.

Nothing in that description says what the row means. It is not an average of anything, it is not a summary anybody designed, and it cannot be computed from the text by any formula. It is wherever the optimisation left it, which is why the rest of the page has to measure rather than describe, and why Part 4 is the long one.

Word2vec learns a word’s row by asking it to help predict the words that appear beside it. The whole of this method is one observation about that loop, which is that it never asks where the row it is training came from. So put the document into the window as one more token, one that is present at every position inside that document and at no position anywhere else, and the loop trains its row alongside the words’ rows without needing to be changed.

What that row then learns follows from where it appears. It is present at every position of its own document and nowhere else, so the only thing it can help predict is that document’s own words, and the only thing worth carrying is whatever those words have in common. A single context of three words does not determine the subject and a whole document mostly does, which is the argument for expecting the subject to end up there.

a document  =  a token present at every window inside it, and no other

Take one position of one document with three coordinates per vector. There is one context word, so the prediction uses the mean of the document vector and that word’s vector.

h  =  ( d  +  ∑ v(c) )  /  ( 1 + n )     over the n context words

document vector d = (0.2, −0.1, 0.4)
context vector v = (0, 0.3, −0.2)
h = (d + v) / 2
  = (0.2 / 2, 0.2 / 2, 0.2 / 2)
  = (0.1, 0.1, 0.1)

observed-word output vector u₊ = (1, 0, 0)
negative-word output vector u₋ = (0, 1, 0)
s₊ = h · u₊ = 0.1
s₋ = h · u₋ = 0.1
p₊ = p₋ = sigmoid(0.1) ≈ 0.524979

observed-word error = p₊ − 1 ≈ −0.475021
negative-word error = p₋ − 0 ≈ 0.524979
g = (p₊ − 1)u₊ + p₋u₋ ≈ (−0.475021, 0.524979, 0)

learning rate = 0.025
Δd = Δv = −0.025 × g / 2
         ≈ (0.005938, −0.006562, 0)

Δ  =  −rate · g / ( 1 + n )     the same step for every averaged row

The document’s row and the word’s row move by the identical amount at this position, which looks like symmetry and is the source of the asymmetry Part 4 is about. The word will meet many more positions than this document will.

It is worth being precise about what the objective actually rewards, since the phrase about a row learning the subject of a document is a description of an outcome rather than of a mechanism. What is rewarded is raising the score of the words that really are in the document and lowering the score of a handful of words drawn at random, at every one of that document’s eight positions.

A row that leaned towards one cooking word and away from everything else would do well at one position and badly at seven, so the only row that does well across all eight is one that leans towards all eight words at once. Here the eight words are drawn from a list of ten, and any two cooking documents are drawing from the same ten, so the rows that serve two cooking documents well are similar rows.

That is the whole of why the fitted positions come out separated by subject, and it depends on the collection having a structure of that kind rather than on anything in the method.

loss for either target at probability 0.5 = −ln(0.5) = ln 2
initial loss per position = 6 ln 2 ≈ 4.1589

The first arrangement is called distributed memory, and it is the one worked through in section 5. The words on either side of a position are collected up, the document’s row is added to that collection, the whole lot is averaged, and the average is asked to predict the word in the middle. The document is there at every position, which is what the word memory in the name is pointing at, since it is the thing that remembers what the rest of the document was about while a local window is being read.

Two details of the version measured here are choices rather than consequences. The paper describes joining the vectors end to end as well as averaging them, and averaging is what is used throughout below, because joining them fixes the window size into the model and makes a shorter window a different model rather than a different setting. And a document of one word has no context at all, in which case the mean is over the document’s row alone and the position is scored rather than skipped.

The second arrangement is called the distributed bag of words, and it throws the context away. The document’s row is the whole of what predicts, and what it is asked to predict is a word of the document, one word at a time, with no reference to what stood beside that word. The paper draws a window and then a word from inside it at each step; sweeping every word of the document once per pass, which is what happens here, is the same objective with the sampling replaced by an exhaustive walk.

h  =  d     the document’s row and nothing else

The immediate consequence is that the whole of the gradient belongs to the document’s row. Under the first arrangement that row got one share of a mean over several rows; here there is nothing to share it with, and it takes the step whole. That one difference is behind almost every number in Part 4.

h = d = (0.2, −0.1, 0.4)
s₊ = h · u₊ = 0.2         p₊ = sigmoid(0.2) ≈ 0.549834
s₋ = h · u₋ = −0.1        p₋ = sigmoid(−0.1) ≈ 0.475021
g = (p₊ − 1)u₊ + p₋u₋ ≈ (−0.450166, 0.475021, 0)
Δd = −0.025 × g ≈ (0.011254, −0.011876, 0)

Both work. Under distributed memory two cooking documents come out at a mean cosine of 0.8974 and two sailing documents at 0.8696, against 0.2811 for one of each; under the bag of words the three figures are 0.7763, 0.8078 and 0.1445. Under both, the fourteen documents nearest the first cooking document are the other fourteen cooking documents, with no sailing document breaking in.

…

Every pair of fitted documents, as a grid of cosines. The two bright blocks on the diagonal are the two subjects, and no fit was told which document belonged to which. Switch the arrangement to see the same structure found twice by different arithmetic.

The across-subject figure is positive under both, and that is worth stopping on, because a reader used to seeing two unrelated things come out near zero or below it will read 0.2811 as a failure. Every document in the collection is trained against one shared table of output rows, so every document’s position picks up a component pointing the same way as every other document’s. The quantity to read is therefore the gap between the within figure and the across figure, and not the sign of either.

Under the bag of words the word rows are never read and never written. The prediction is made from the document’s row, the correction goes to the document’s row and to the output rows, and the input row belonging to butter is never touched from the beginning of the fit to the end of it. So the word table this arrangement hands back at the end is the random draw it was given at the start, which is a fact about the method and not a shortcoming of any particular run.

Measured, that is exactly what it looks like. Under distributed memory butter and garlic reach a cosine of 0.994 against 0.120 for butter and anchor, which is the separation of the two lists showing up in the words as well as the documents. Under the plain bag of words the same two pairs read 0.4206 and −0.2104, which are the values two random draws happen to have and mean nothing whatever.

Adding an ordinary word pair alongside each document pair, which is the usual repair, brings them back to 0.9666 and 0.0965 in a third of the passes.

Every number above comes from thirty passes at a step size of 0.1, and it is worth saying plainly why, since those are not the settings the published work uses. At the reference settings of ten passes from a step size of 0.025, this collection offers 2,400 positions in total, which is not enough movement to get anywhere. The cost falls from 4.1586 to 4.1155, barely off the 4.1589 an untrained pair costs.

The document positions are then still essentially where they were drawn. Two documents of one subject come out at a mean cosine of 0.0330 and two documents of different subjects at 0.0437, so the pairs that ought to be alike are on average slightly less alike than the pairs that ought not to be, which is what thirty directions drawn at random in eight dimensions look like.

Here is where the method becomes awkward. A word seen during the fit has a row, and a document seen during the fit has a row, and either can be looked up in constant time. A text that arrives afterwards has no row, and there is nothing whatever to look up, because its position was never a function of its words in the first place.

What there is instead is the same loop, run again with everything else nailed down. Give the new text a fresh random row, freeze the word table and the output table so nothing already learned can move, and run the same updates over the new text’s own positions, moving that one row and nothing else. After enough passes the row sits wherever it needed to sit to predict that text’s words.

d*  =  argmin over d of  ∑ loss( word, d )     every table held fixed

Two things follow immediately and both matter. The answer is gradient descent, so it depends on where it started and on how long it was allowed to run, and the cost of placing one text is no longer a table lookup but an optimisation whose length the caller chooses. Section 14 is about how badly that second choice can go.

Before the passes are counted, the reason the count matters has to be visible, and it is a fact about how often each kind of row is stepped. Under distributed memory a document’s row is stepped eight times a pass, once at each of its own positions, and never again. A word’s row is stepped once for every position it stands beside, in every document that used it, and each of the ten cooking words turns up in between seven and twelve of the fifteen cooking documents.

Measured after the fit, the word rows have lengths between 1.7429 and 2.6753, mean 2.2348, and the document rows lengths between 0.2909 and 0.5249, mean 0.3897. The word rows are nearly six times as long. A new document begins at a random draw of length about 0.115, so it enters a mean in which the word rows already dominate, and it is answerable for only its share of a gradient that has to move it a long way.

…

The range of row lengths in each family, with the dot at the mean. The top two bars are distributed memory, where the words are long; the bottom two are the bag of words, where the word rows were never stepped and the document rows took every step whole.

Under the bag of words the picture is the reverse, and for the reason section 8 gave. The document rows there run from 1.9010 to 2.5183 while the word rows sit between 0.0713 and 0.1485, which are the lengths a random draw at this width has. A new document under that arrangement starts short and is stepped by the whole gradient rather than a share of it.

The published number of passes to give a new text is twenty. On this collection, under distributed memory, twenty passes put the held-out cooking text at a mean cosine of 0.4786 to the cooking documents and 0.7608 to the sailing ones. It is in the wrong half, and not narrowly. All five of the documents it comes out nearest are sailing documents, and a reader who took that answer and did anything with it would be working with a cooking text filed under sailing.

…

The held-out cooking text’s position against the number of passes, on a logarithmic axis, with the published twenty marked. Under distributed memory the two lines have not yet crossed there. Switch the arrangement to see the other one, where they never cross because they never had to.

Given more passes it arrives, and the crossing happens between twenty and fifty. Fifty passes give 0.8347 against 0.3303, a hundred give 0.9031 against 0.2116, and two hundred give 0.9081 against 0.1405, after which very little more is bought. The length of the inferred row rises with the passes too, from 0.1112 at one pass to 0.8071 at two hundred, which is the row walking out of its random start towards the scale the fitted rows work at.

The same measurement under the other arrangement looks nothing like it. A single pass already puts the held-out text at 0.8330 to the cooking documents against 0.4047 to the sailing ones, so it is in the right half before it has seen its own eight words more than once. Twenty passes give 0.8565 against 0.1420, which is a good answer, and the published default serves this arrangement well.

What happens after twenty is more interesting than what happens before it. Two hundred passes give 0.7665 against 0.0924, so the distance to the wrong subject keeps improving while the distance to the right one gets worse, and four hundred passes leave the text at 0.6954 to its own subject. The row is not going wrong. It is becoming a better and better description of its own eight particular words, which is what it was asked to do, and a description that particular has moved away from what the fifteen cooking documents share.

The honest unit of cost here is a position, since every position costs one vector of eight numbers and six output rows whatever machine is running it. The collection is thirty documents of eight words, so a pass is two hundred and forty positions and thirty passes are 7,200. Averaging the words of those same documents costs two hundred and forty additions and no passes at all, because there is nothing to fit.

a fit  =  documents × words per document × passes     positions

The tables that come out of it are worth counting too. Twenty words at a width of eight is 160 numbers of word table, thirty documents is 240 of document table, and the output rows the fit needed and does not answer with are another 160. Already, on a collection this small, the document half of what was learned is larger than the word half, and section 22 comes back to what that means as a collection grows.

A held-out text of eight words at two hundred passes costs 1,600 positions, which is more than six times what one training document contributed to the whole fit and is 22 per cent of the entire fit, for one document out of thirty. Under the bag of words at twenty passes it is 160 positions. Averaging that text’s word positions costs eight additions and a division.

In seconds on one machine the ratios come out at roughly three thousand to one between the first row and the last, and roughly a hundred and fifty to one between the third row and the last. The panel in the next section carries the current figures, and they move a little from run to run, which is the reason to trust the position counts above rather than the clocks.

The comparison that matters is not which method has the higher average similarity inside a subject, since that can be raised by making everything more alike. It is the margin between the least alike pair from one subject and the most alike pair across the two, because a positive margin means the two groups do not overlap at all and a negative one means they do.

On that measure the learned positions lose. Under distributed memory the least alike pair inside one subject scores 0.6364 and the most alike pair across the two scores 0.7204, a margin of −0.0840; under the bag of words the figures are 0.4552 and 0.4994, a margin of −0.0442. The average of a document’s word positions gives 0.9935 and 0.1552, a margin of +0.8383, so its two groups are cleanly apart where neither learned rule’s are.

…

Each bar runs from the least alike pair inside one subject to the most alike pair across the two, so a bar is green where the two have not crossed. Two of the three are red, and they are the two that were fitted.

The held-out text tells the same story. Averaging places it at 0.9996 to the cooking documents and 0.1336 to the sailing ones, which is better than the 0.9081 and 0.1405 that two hundred passes of descent reach, and it does it in eight additions against 1,600 positions. Some of that advantage is borrowed, since the word table being averaged is the one this method’s own fit produced, so averaging is getting the fit for free and paying only for the composition.

So what is the learned position for? The claim to test is the one Part 1 set up, which is that a sum over words cannot tell two arrangements of the same words apart and this method might. Under distributed memory the window really does read which words stood beside which, so a different arrangement is a different set of contexts and could produce a different answer.

Testing it needs a control, because this method’s answers differ from run to run anyway. So the same eight words are inferred in two arrangements from one starting draw, and the same arrangement is inferred from two different starting draws, and the question is whether the order moved the answer more than the draw did.

…

The grey band is the control, which is how far apart two starting draws of one arrangement come out, and the dot is how far apart two arrangements come out. Only where the dot is well to the left of the band did the order do anything.

One row of five passes the test. Under distributed memory at two hundred passes the two arrangements agree to 0.8548 while two starting draws of one arrangement agree to 0.9823 and 0.9905, so the two arrangements are about three times further apart in angle than two draws of one arrangement are. At twenty passes the same comparison reads 0.9874 against 0.6076, which is the opposite verdict, because the descent has not gone far enough for anything but the starting point to matter.

The bag of words gives 0.9996 and 0.9998 at the two lengths, reading no order at all, and the average gives exactly one.

A fitted document’s row was determined jointly with everything else the fit learned, and it is what it is. A held-out text’s row is defined as the point that minimises a quantity, and that definition only names a unique answer if the quantity has a unique minimum and the search is run until it gets there. Neither holds. The objective is not convex in the row it is being minimised over, and the search is stopped after a number of passes the caller picks.

So the position of a held-out text is a function of three things rather than one, the text and the starting draw and the number of passes, and the same text really does come back differently. At twenty passes under distributed memory, two starting draws agree to 0.6076, which is a disagreement about the answer and not about its last few digits. At two hundred passes they agree to 0.9823, so more passes narrow the spread without closing it.

Both arrangements answer with a word table and a document table of the same shapes, and the two word tables do not mean the same thing. Under distributed memory a word’s row was trained against the same objective the documents were, so a document and a word live in one space and the angle between them is a quantity the fit actually pushed on.

Under the plain bag of words a word’s row was never touched, so the angle between a document and a word is the angle between something learned and something drawn at random.

Nothing in the shape of the answer records which of those it is. Two tables of twenty rows by eight numbers arrive, and only a reader who knows how they were made can tell that one of them is the initialisation. Measured here, the untouched rows give butter and garlic a cosine of 0.4206 and butter and anchor −0.2104, both of which are perfectly plausible-looking numbers.

A word table has one row per word, and a vocabulary saturates, so a table fitted to ten times as much text of the same language is not ten times larger. A document table has one row per document and grows without limit, so the size of what has been learned is a function of how much text was shown rather than of the language it was in. Here the document table is already 240 numbers against the word table’s 160, on thirty documents of eight words.

Worse for the definition, nothing in the objective says where one document ends and the next begins. The method gives a row to each text it is handed, so the same corpus divided into paragraphs instead of articles is a different model with a different number of rows and different positions, and the division is a modelling choice made before the fit that the fit itself never sees. A word boundary is at least a fact about the text.

Four inputs make the placement undefined rather than merely awkward, and in each one it is worth knowing which quantity fails and why, since each is a decision anybody implementing the method has to make.

The first of those is the one that arises in ordinary use rather than in a constructed example, and it is worth contrasting with the pooled answer to the same input. Pooling a text of unknown words gives the origin, which is honestly nothing; this gives a random direction of ordinary length, which is confidently something. Of the two, the second is the harder mistake to notice.