Continuous Bag-of-Words (CBOW)

CBOW is a word-embedding algorithm: it learns a mapping from vocabulary words to dense, low-dimensional real vectors (typically 100–300 dimensions) such that words with similar distributional behavior end up with similar vectors. It does this via a fake supervised task derived automatically from raw text — no human labels are needed. Given a window of size $c$ around a position $t$ in a corpus, the context is the set of words $w_{t-c}, \dots, w_{t-1}, w_{t+1}, \dots, w_{t+c}$, and the target is the center word $w_t$. CBOW's task is: given the context words, predict the target word. The crucial architectural choice is how the context words are combined. CBOW looks up each context word's embedding vector and takes their average (or sum, in some formulations) to form a single fixed-size context vector, discarding information about which context position each word occupied and how many distinct words appear. This is why the model is called a "bag of words" — the context is treated as an unordered multiset, pooled into one vector, then passed through a single output layer to score every vocabulary word as a candidate target. This stands in direct contrast to Word2Vec Skip-gram, which uses a target word to predict each context word separately, producing $2c$ independent prediction tasks per window instead of CBOW's one. Averaging in CBOW means the training signal per window is smoothed across all context words simultaneously: a single gradient update nudges the shared context representation to be more predictive of the true center word, rather than nudging the center word to be predictive of each context word individually. This smoothing is the defining mathematical difference between the two architectures, and it drives essentially every practical difference in training speed, statistical behavior on rare versus frequent words, and downstream embedding quality that practitioners observe.

CBOW's parameters are two embedding matrices of the same shape: an input matrix $W_{in} \in \mathbb{R}^{V \times d}$ and an output matrix $W_{out} \in \mathbb{R}^{V \times d}$, where $V$ is vocabulary size and $d$ is the embedding dimension. Word $w$'s input embedding is row $W_{in}[w]$; its output embedding (used only when $w$ is a candidate target) is row $W_{out}[w]$. Only $W_{in}$ is kept as "the" word embeddings after training, though some implementations average or concatenate both.

Forward pass, for one training window: 1. Collect the context word indices $c_1, \dots, c_{2c}$ around target position $t$. 2. Look up their input embeddings and average them:

3. Score every vocabulary word $w$ as a candidate target using a dot product with the output embeddings:

4. Convert scores to a probability distribution over the whole vocabulary with softmax:

Training objective. Over the whole corpus of $T$ tokens, CBOW maximizes the average log-likelihood of each true center word given its context:

Maximizing $J$ is done by stochastic gradient descent (or a minibatch variant), moving through the corpus window by window, computing the softmax loss for the true target, and back-propagating gradients into both $W_{out}$ (the output row for every vocabulary word, because softmax normalizes over all of them) and $W_{in}$ (the input rows for the context words actually present in the window, since $h$ is their average). The backward pass is standard cross-entropy softmax backpropagation, with one subtlety: the gradient with respect to $h$ must be distributed equally to all context word vectors, since $h$ is their arithmetic mean. ``` ALGORITHM: Train-CBOW(corpus, window_size c, dim d, vocab V, learning_rate η, epochs E) Initialize W_in as V×d matrix with small random values Initialize W_out as V×d matrix with small random values for epoch in 1..E: for each position t in corpus (with valid window, i.e. c ≤ t ≤ T-c):

# --- build context and target --- target ← corpus[t] context_ids ← [ corpus[t-c], ..., corpus[t-1], corpus[t+1], ..., corpus[t+c] ] m ← length(context_ids) # = 2c away from corpus boundaries

# --- forward pass --- h ← (1/m) * sum( W_in[i] for i in context_ids ) # d-dim averaged context vector for w in 1..V: z[w] ← dot(W_out[w], h) p ← softmax(z) # V-dim probability vector

# --- loss (for monitoring only) --- loss ← -log( p[target] )

# --- backward pass ---

# dL/dz[w] = p[w] - 1{w == target} (standard softmax-cross-entropy gradient) for w in 1..V: g_z[w] ← p[w] - (1 if w == target else 0)

# gradient wrt h: dL/dh = sum_w g_z[w] W_out[w] g_h ← sum( g_z[w] W_out[w] for w in 1..V ) # d-dim vector

# gradient wrt W_out: dL/dW_out[w] = g_z[w] h for w in 1..V: W_out[w] ← W_out[w] - η g_z[w] * h

# gradient wrt each context input vector (chain rule through the average):

# dh/dW_in[i] = 1/m for each i in context_ids for i in context_ids: W_in[i] ← W_in[i] - η (g_h / m) return W_in # rows of W_in are the learned word embeddings ``` Two implementation notes matter for correctness. First, <strong>boundary windows</strong> near the start or end of a document must either be skipped or padded consistently; the pseudocode above simply restricts $t$ to positions with a full window on both sides. Second, the inner loops over "all $w$ in $1..V$" in the forward/backward pass are the expensive part discussed below — in practice they are replaced by <span class="wiki-link-missing">Negative Sampling</span> or hierarchical softmax, which the raw algorithm above deliberately avoids introducing so the exact* CBOW objective is visible first.

Per-window time complexity (naive softmax). For one training example (one window), the forward pass computes $h$ in $O(cd)$ time (averaging $2c$ vectors of dimension $d$), then computes a dot product with every vocabulary row to get $z$, costing $O(Vd)$. The backward pass is symmetric: computing all softmax gradients is $O(V)$, updating every row of $W_{out}$ is $O(Vd)$, and computing $g_h$ requires summing $V$ vectors, $O(Vd)$. So one training step costs

dominating the $O(cd)$ context-averaging cost since $V \gg c$ in realistic vocabularies (tens of thousands to millions of words). Over a corpus of $T$ tokens this gives $O(TVd)$ total training time per epoch — the same asymptotic bottleneck that skip-gram faces, and precisely the cost that motivates replacing the full softmax with Negative Sampling (reducing the per-step cost to $O(kd)$ for a small constant number of negative samples $k$) or a hierarchical softmax tree (reducing it to $O(d \log V)$).

Space complexity is $O(Vd)$ for each of $W_{in}$ and $W_{out}$, i.e. $O(Vd)$ total, since these are the only parameters — there are no recurrent or convolutional weights. This is modest even for $V = 10^6$, $d = 300$: about $3 \times 10^8$ floats per matrix, a few gigabytes in float32, comfortably fits on commodity hardware from the era CBOW was introduced.

Why averaging is a mathematically sound smoothing operation. The gradient computation shows precisely what "smoothing" means: since $h = \frac{1}{m}\sum_i W_{in}[c_i]$, the chain rule gives $\frac{\partial h}{\partial W_{in}[c_i]} = \frac{1}{m} I$ for every context word $i$. Consequently every context word receives an identical gradient signal (scaled by $1/m$) regardless of which position in the window it occupied or how informative it individually was. This is the formal justification for the informal claim "CBOW blurs context word order and identity" — it falls directly out of differentiating a mean. Because the gradient magnitude per context word shrinks by a factor of $1/m$ compared to skip-gram (which gives each context word its own undivided gradient from a separate prediction), CBOW updates are individually gentler but there are effectively $2c$ times fewer distinct predictions per window (one softmax instead of $2c$), which is the source of its speed advantage.

Correctness of the training procedure reduces to correctness of maximum-likelihood estimation via SGD on a well-defined, differentiable objective. $J(\theta)$ is a proper log-likelihood: $P(w_t \mid \text{context})$ is a valid probability distribution because softmax normalizes over the vocabulary, so $-\log P$ is a valid cross-entropy loss bounded below by 0. Standard SGD convergence arguments apply: for suitably decaying learning rates and a smooth (here, doubly-differentiable) loss landscape, SGD converges to a stationary point of the empirical objective, though because $J$ is non-convex (it factors through the bilinear form $W_{out}[w] \cdot h$), only local rather than global optimality is guaranteed. In practice this is not a correctness failure specific to CBOW — it is the same non-convexity every neural embedding model accepts, and empirically CBOW reaches representations useful for downstream tasks despite the lack of a global-optimum guarantee.

Honest tradeoff summary.

Take the toy sentence, tokenized and lowercased: ``` the quick brown fox jumps over the lazy dog ``` with window size $c = 2$ and target position $t$ pointing at "fox" (index 3, 0-indexed). The context is the two words on each side:

Suppose $d = 2$ for hand-traceability, and the current (partially trained) input embeddings are:

Step 1 — average the context vectors.

Step 2 — score candidate targets. Suppose the output embeddings for a tiny 3-word slice of the vocabulary (restricting to fox, dog, quick for illustration) are:

Step 3 — softmax over these scores (restricted subset, for illustration; real softmax runs over the full vocabulary):

Step 4 — loss and gradient. True target is "fox", so $g_z(\text{fox}) = 0.355 - 1 = -0.645$, $g_z(\text{dog}) = 0.319$, $g_z(\text{quick}) = 0.326$ (each other vocabulary word similarly gets $g_z(w) = p(w)$). Loss is $-\log(0.355) \approx 1.036$ nats.

Step 5 — update. $W_{out}[\text{fox}]$ moves toward $h$ (negative gradient direction, since $g_z<0$ there), while $W_{out}[\text{dog}]$ and $W_{out}[\text{quick}]$ move away from $h$. Every context word's input vector — "the", "quick", "brown", "jumps" — receives the same $g_h / 4$ nudge, pulling all four slightly in a direction that would have made $h$ score "fox" higher next time. This last point is the concrete instance of the smoothing argument from the complexity section: none of "the", "brown", "jumps" gets individualized credit or blame even though intuitively "brown" is a far more informative context word for "fox" than "the" is.

CBOW was introduced by Tomas Mikolov and colleagues at Google as one half of the Word2Vec family, published alongside skip-gram in 2013. The paper's central claim — that a shallow, log-linear model trained purely on raw text co-occurrence could produce embeddings capturing rich semantic and syntactic regularities (the famous "king − man + woman ≈ queen" analogy) — reoriented the field's default approach to representing words, displacing older count-based methods like latent semantic analysis for many downstream tasks.

CBOW-style pretraining became a standard first step in NLP pipelines throughout the mid-2010s: word vectors trained via CBOW or skip-gram were plugged into downstream classifiers for sentiment analysis, part-of-speech tagging, named entity recognition, and as initialization for the embedding layers of early neural machine translation systems, well before end-to-end contextual models dominated. Libraries such as Gensim's `word2vec` module expose a `sg` flag that switches between skip-gram (`sg=1`) and CBOW (`sg=0`), and CBOW is frequently the default for large corpora precisely because of its speed advantage discussed above. Beyond direct embedding pretraining, the CBOW idea of "predict from pooled context" recurs structurally in other systems: fastText extends CBOW-style training with subword n-gram features to better handle rare and out-of-vocabulary words; paragraph/document embedding methods like Doc2Vec's distributed-memory variant borrow the same averaged-context-predicts-target scaffold at the document level; and average-pooling encoders in sentence embedding baselines echo the same smoothing tradeoff CBOW exhibits at the word level. Understanding CBOW's mechanics is therefore foundational not just historically, but as a recurring architectural pattern — pool, then predict — that reappears whenever engineers trade positional precision for computational efficiency.

Ask the tutor: How does replacing CBOW's full softmax with negative sampling change the training objective and gradient computation?