← Study Guide Mind Map Home

Math Foundations — Lecture 1

Notation, sets, vectors, TF–IDF, BM25, cosine, SVD, softmax, cross-entropy.

Sets & notation

\(V\)Vocabulary — finite set of word types, \(|V|\) = vocab size.
\(w_1,\dots,w_N\)A corpus or document of \(N\) tokens, each \(w_i\in V\).
\(\text{count}(t,d)\)How many times term \(t\) appears in document \(d\).
\(\text{df}(t)\)Document frequency — number of documents containing \(t\).
\(N_\text{docs}\)Total number of documents in the collection.

One-hot & bag-of-words vectors

One-hot: word \(w\) at index \(j\) in \(V\) → vector \(\mathbf{e}_w\in\{0,1\}^{|V|}\) with a single 1 at position \(j\).

\[\mathbf{e}_w[i] = \begin{cases}1 & i=j \\ 0 & \text{otherwise}\end{cases}\]

BoW document vector (count variant): \(\mathbf{d}[j]=\text{count}(w_j,d)\). Binary variant uses OR instead of sum.

Orthogonality: \(\mathbf{e}_a\cdot\mathbf{e}_b=0\) for \(a\neq b\) — synonyms have zero overlap.

Quick Check: If \(|V|=50{,}000\) and a document has 120 unique words, how many entries are non-zero in the BoW vector?
50,000
120

TF–IDF

Raw counts over-weight frequent but uninformative terms (e.g. the). TF–IDF re-weights:

Term frequency (log-scaled)

\[\mathrm{tf}_{t,d} = \begin{cases}1 + \log_{10}\mathrm{count}(t,d) & \mathrm{count}(t,d)>0\\0 & \text{otherwise}\end{cases}\]

Inverse document frequency

\[\mathrm{idf}_t = \log_{10}\frac{N_\text{docs}}{\mathrm{df}(t)}\]

If \(t\) appears in every document, \(\mathrm{idf}_t=\log_{10}1=0\) — term has no discriminative power.

Combined

\[\mathrm{tf\text{-}idf}_{t,d} = \mathrm{tf}_{t,d}\times\mathrm{idf}_t\]
Quick Check: A term appears 1000 times in doc \(d\). What is its log-scaled tf?
\(1+\log_{10}1000=4\)
\(\log_{10}1000=3\)
\(1000\)

BM25 (Okapi)

Information retrieval scoring; same spirit as TF–IDF with saturation and length normalisation.

\[\mathrm{BM25}(q,d)=\sum_{t\in q}\underbrace{\log\frac{N_\text{docs}-\mathrm{df}(t)+0.5}{\mathrm{df}(t)+0.5}}_{\text{IDF-like}}\;\cdot\;\frac{\mathrm{count}(t,d)\,(a+1)}{\mathrm{count}(t,d)+a\!\left(1-b+b\,\frac{|d|}{L_\text{avg}}\right)}\]
\(a\in[0.1,4]\)Controls TF saturation (higher → slower saturation).
\(b\in[0.1,1]\)Controls length normalisation (\(b=0\) → ignore doc length).
\(L_\text{avg}\)Average document length in the collection.

Cosine similarity

Dot product favours longer vectors; cosine normalises by magnitude:

\[\cos(\mathbf{u},\mathbf{v})=\frac{\mathbf{u}\cdot\mathbf{v}}{\|\mathbf{u}\|\;\|\mathbf{v}\|}=\frac{\sum_i u_i v_i}{\sqrt{\sum_i u_i^2}\;\sqrt{\sum_i v_i^2}}\]

Range \([-1,1]\); 1 = same direction; 0 = orthogonal; −1 = opposite.

Analogy arithmetic

Check: \(\mathbf{v}_{w_1}-\mathbf{v}_{w_2}+\mathbf{v}_{w_3}\approx\mathbf{v}_{w_4}\) via nearest-neighbour in cosine. Example: Paris − France + Italy ≈ Rome.

Quick Check: Two unit vectors have dot product 0.95. Is their cosine similarity 0.95?
Yes — unit vectors already normalised
No — need to divide by norms first

SVD for distributional vectors

Co-occurrence matrix \(M\in\mathbb{R}^{|V|\times|V|}\) (or \(|V|\times C\) for context features). Truncated SVD:

\[M \approx U_k \Sigma_k V_k^\top\]

Keep top-\(k\) singular values → each word gets a dense \(k\)-dimensional vector (row of \(U_k\Sigma_k\)). Captures latent semantic structure (Schütze 1993, LSA).

Softmax & cross-entropy (preview)

Maps raw scores (logits) \(z_1,\dots,z_C\) to a probability distribution over \(C\) classes:

\[\mathrm{softmax}(z_i) = \frac{e^{z_i}}{\sum_{j=1}^{C}e^{z_j}}\]

Always positive; sums to 1. Sensitive to scale of \(z\).

Cross-entropy loss

Measures distance between predicted distribution \(\hat{\mathbf{p}}\) and one-hot target \(\mathbf{y}\):

\[\mathcal{L}_\text{CE}=-\sum_c y_c\log\hat p_c = -\log\hat p_{y^*}\]

where \(y^*\) is the true class. Minimising CE = maximising log-probability of the correct label.

Quick Check: If the model assigns probability 1.0 to the correct class, what is the cross-entropy loss?
\(-\log 1 = 0\)
\(1\)
\(\infty\)

Dense embeddings

Map each word to a learned vector \(\mathbf{e}_w\in\mathbb{R}^d\) with \(d\ll|V|\). Equivalent to a lookup in an embedding matrix \(E\in\mathbb{R}^{|V|\times d}\):

\[\mathbf{e}_w = E[w,:] = E^\top \mathbf{1}_w\]

Properties (animacy, part-of-speech, etc.) encoded as directions, axes, or regions in embedding space — not always a single dimension.