Moments and maximum likelihood

Factor model. Suppose \(Y_1,\ldots,Y_n\in\R^p\)$Y_1,\ldots,Y_n\in\mathbb{R}^p$ are i.i.d. and \[Y_i=Bf_i+u_i,\qquad B\in\R^{p\times K},\quad \E f_i=0,\quad\operatorname{Cov}(f_i)=I_K,\quad \E u_i=0,\quad\operatorname{Cov}(u_i)=\Sigma.\]$$Y_i=Bf_i+u_i,\qquad B\in\mathbb{R}^{p\times K},\quad \mathbb{E}f_i=0,\quad\operatorname{Cov}(f_i)=I_K,\quad \mathbb{E}u_i=0,\quad\operatorname{Cov}(u_i)=\Sigma.$$

Cross terms and covariance. Assume finite second moments, \(\operatorname{Cov}(f_i,u_i)=0\)$\operatorname{Cov}(f_i,u_i)=0$, and known \(\Sigma\)$\Sigma$. Independence between factors and noise would suffice for the zero cross-covariance condition. Then \[\operatorname{Cov}(Y_i)=BB^\top+\Sigma.\]$$\operatorname{Cov}(Y_i)=BB^\top+\Sigma.$$

Estimate the identified target. The covariance alone does not distinguish \(B\)$B$ from \(BR\)$BR$ for an orthogonal \(K\times K\)$K\times K$ matrix \(R\)$R$. We therefore target \(L=BB^\top\)$L=BB^\top$ and form

Known noise covariance. If \(\Sigma\)$\Sigma$ must also be estimated, that is an additional estimation step; the displayed unbiasedness statement assumes it is known.

Constrain the estimate. The target is positive semidefinite (PSD) and has rank at most \(K\)$K$. Write \(A=\sum_{j=1}^p\lambda_j u_j u_j^\top\)$A=\sum_{j=1}^p\lambda_j u_j u_j^\top$ with \(\lambda_1\ge\cdots\ge\lambda_p\)$\lambda_1\ge\cdots\ge\lambda_p$ and orthonormal \(u_j\)$u_j$. For \(1\le K\le p\)$1\le K\le p$, a closest PSD matrix of rank at most \(K\)$K$ in Frobenius norm is

Clipping and proof. Clipping negative eigenvalues matters: retaining a negative eigenvalue would contradict the structure of \(BB^\top\)$BB^\top$. Ties at the cutoff may give several equally close matrices. Exercise 3 proves the projection formula and the useful bound \(\|\hat L-L\|_F\le2\|A-L\|_F\)$\|\hat L-L\|_F\le2\|A-L\|_F$, where \(\|C\|_F^2=\sum_{i,j}C_{ij}^2\)$\|C\|_F^2=\sum_{i,j}C_{ij}^2$. Projection can introduce bias; the bound is not a universal finite-sample MSE improvement theorem.

Vector offsets. A striking empirical pattern is that some semantic relationships appear as approximately parallel vector offsets. Writing \(e(w)\)$e(w)$ for the learned embedding of word \(w\)$w$, the famous analogy is

Published evidence. Figure 1 shows the original GloVe visualization, including these word pairs. Such linear representations give empirical support to the factor-model viewpoint: reusable concepts can contribute along shared directions.

Factor interpretation. A useful model is \(e(w)\approx Ba(w)\)$e(w)\approx Ba(w)$, where the columns of \(B\)$B$ are common semantic directions and \(a(w)\)$a(w)$ contains the word’s loadings on them. The observed offsets motivate this representation; they do not establish the specific covariance assumptions of our earlier random factor model.

Indicator moments. Earlier language models also used higher-order co-occurrence statistics. An \(n\)$n$-gram is a block of \(n\)$n$ consecutive tokens, and an \(n\)$n$-gram model predicts the next token from the preceding \(n-1\)$n-1$ tokens. Its block frequencies are empirical versions of the joint moments \[\E\!\left[\prod_{j=1}^n\mathbf1\{W_j=a_j\}\right] =\Pr(W_1=a_1,\ldots,W_n=a_n).\]$$\mathbb{E}\!\left[\prod_{j=1}^n\mathbf1\{W_j=a_j\}\right] =\Pr(W_1=a_1,\ldots,W_n=a_n).$$

Meaning of moment order. Thus “\(n\)$n$-th moments” here means products of \(n\)$n$ token indicators, not powers of arbitrary numeric word IDs.

Historical link. Shannon’s successive approximations to English used letter and word transition frequencies [13]; Brown et al. [5] developed count-based and class-based \(n\)$n$-gram models. These methods connect moment statistics to conditional-probability estimation, which we revisit in Section 3.1.

Categories and counts. Before considering language, suppose \(N\ge1\)$N\ge1$ i.i.d. categorical observations take values in a finite alphabet \(\mathcal V\)$\mathcal V$ of size \(V\)$V$. Their probability vector is \(p=(p_v)_{v\in\mathcal V}\)$p=(p_v)_{v\in\mathcal V}$ in the closed probability simplex \(\Delta_V=\{p:p_v\ge0,\ \sum_v p_v=1\}\)$\Delta_V=\{p:p_v\ge0,\ \sum_v p_v=1\}$. Let \(C_v\)$C_v$ count category \(v\)$v$, so \((C_v)_{v\in\mathcal V}\sim\operatorname{Multinomial}(N,p)\)$(C_v)_{v\in\mathcal V}\sim\operatorname{Multinomial}(N,p)$.

Multinomial likelihood. For observed counts \(c_v\)$c_v$, put \(\hat p_v=c_v/N\)$\hat p_v=c_v/N$. The likelihood is

where \(A(c)=\log(N!/\prod_v c_v!)\)$A(c)=\log(N!/\prod_v c_v!)$ does not depend on \(p\)$p$. We use \(p_v^0=1\)$p_v^0=1$, including \(0^0=1\)$0^0=1$ in this likelihood. If \(c_v>0\)$c_v>0$ and \(p_v=0\)$p_v=0$, the likelihood is zero and its logarithm is \(-\infty\)$-\infty$.

Cross-entropy identity. For probability vectors \(r,p\)$r,p$, define the cross-entropy

It is \(+\infty\)$+\infty$ if \(p_v=0\)$p_v=0$ for a category with \(r_v>0\)$r_v>0$; zero-weight terms contribute zero. All logarithms in this subsection are natural. Equation (13) gives the exact identity \[-\frac1N\ell(p;c)=H(\hat p,p)-\frac{A(c)}N.\]$$-\frac1N\ell(p;c)=H(\hat p,p)-\frac{A(c)}N.$$

Equivalent optimization. Therefore maximizing the multinomial likelihood is exactly minimizing the cross-entropy from the empirical distribution to the model. The multinomial coefficient changes the objective’s value, not its optimizer. If we observe an ordered categorical sample rather than its count vector, that coefficient is absent, and the same optimizer results.

Entropy and divergence. For a fixed probability vector \(r\)$r$, write \[H(r,p)=H(r)+D_{\mathrm{KL}}(r\Vert p),\qquad H(r)=-\sum_{v:r_v>0}r_v\log r_v,\]$$H(r,p)=H(r)+D_{\mathrm{KL}}(r\Vert p),\qquad H(r)=-\sum_{v:r_v>0}r_v\log r_v,$$ where \(H(r)\)$H(r)$ is its entropy and \(D_{\mathrm{KL}}(r\Vert p)=\sum_{v:r_v>0}r_v\log(r_v/p_v)\)$D_{\mathrm{KL}}(r\Vert p)=\sum_{v:r_v>0}r_v\log(r_v/p_v)$ is the Kullback–Leibler (KL) divergence.

Nonnegativity. To check nonnegativity without overlooking zero counts, let \(S=\{v:r_v>0\}\)$S=\{v:r_v>0\}$. If \(p\)$p$ vanishes anywhere in \(S\)$S$, the divergence is infinite. Otherwise \(-\log u\ge1-u\)$-\log u\ge1-u$ for \(u>0\)$u>0$ gives

Equality and zero counts. The scalar inequality follows by differentiating \(u-1-\log u\)$u-1-\log u$, whose minimum is zero at \(u=1\)$u=1$. Equality in the divergence requires \(p_v/r_v=1\)$p_v/r_v=1$ throughout \(S\)$S$ and no probability outside \(S\)$S$; equivalently \(p=r\)$p=r$. Consequently the unique multinomial MLE over \(\Delta_V\)$\Delta_V$ is \(\hat p_v=c_v/N\)$\hat p_v=c_v/N$, even when some counts are zero. If one insists on strictly positive probabilities, zero counts can instead lead to an unattained supremum at the boundary.

Textbook sources. This elementary calculation is the statistical foundation of the loss used below. For textbook treatments, see Manning, Raghavan, and Schütze, Section 12.1.3, and Goodfellow, Bengio, and Courville, Sections 5.5–5.5.1 [7].

Tokens and conditional distributions. A token is one symbol in a language model’s vocabulary: a word, a word fragment, or punctuation, for example. For an observed sequence \(w_1,\ldots,w_T\)$w_1,\ldots,w_T$, let \(w_{<t}=(w_1,\ldots,w_{t-1})\)$w_{<t}=(w_1,\ldots,w_{t-1})$ denote the prefix before position \(t\)$t$. An autoregressive language model gives a categorical distribution \(q_\theta(v\mid w_{<t})\)$q_\theta(v\mid w_{<t})$ over the next token \(v\in\mathcal V\)$v\in\mathcal V$. For every prefix, these probabilities are nonnegative and sum to one. A fixed BOS token supplies the first context; BOS is the standard shorthand for beginning of sequence (here, a sentence). We include an end-of-sequence token among the predicted tokens so that stopping is part of the model.

Softmax probabilities. Often a neural network gives a score \(s_\theta(v,h)\)$s_\theta(v,h)$ to each candidate \(v\)$v$ in context \(h\)$h$, and softmax turns the scores into probabilities: \[q_\theta(v\mid h)=\frac{\exp s_\theta(v,h)} {\sum_{u\in\mathcal V}\exp s_\theta(u,h)}.\]$$q_\theta(v\mid h)=\frac{\exp s_\theta(v,h)} {\sum_{u\in\mathcal V}\exp s_\theta(u,h)}.$$

Shared parameters. The parameter vector \(\theta\)$\theta$ is shared across all positions and contexts. Neural probabilistic language models already used learned word representations and conditional likelihood in [3]; the basic estimation principle does not depend on a particular neural network architecture.

Product becomes sum. The probability chain rule gives

Definition of conditional probability. We don’t need any assumption about independence, since the decomposition follows from the definition of conditional probability. A model may restrict the context it uses, as an \(n\)$n$-gram model does, but the full-prefix chain rule itself is exact.

One loss at every position. For the toy sequence “the cat sleeps” followed by an end marker, the four prediction tasks are

Training and generation. BOS is implicit in the last three prefixes. Training uses the observed preceding tokens, often called teacher forcing; during generation, later predictions instead condition on the tokens generated so far. We score every target position, not merely the final token of the sequence.

Corpus likelihood. Suppose a training corpus consists of \(m\)$m$ sequences, modeled as independent, with lengths \(T_1,\ldots,T_m\)$T_1,\ldots,T_m$ including the end markers. Let \(M=\sum_iT_i\)$M=\sum_iT_i$ be the number of predicted tokens. The token-averaged negative log-likelihood is

Token averaging. Maximizing the corpus likelihood is equivalent to minimizing this loss, since taking a negative logarithm reverses the optimization and \(M\)$M$ is fixed by the corpus. This is an average over tokens; giving every sequence equal weight regardless of length would generally be a different objective.

One-hot cross-entropy. To identify each summand as cross-entropy, let \(y_{it}\)$y_{it}$ be the probability vector with mass one on the observed target: \(y_{it}(v)=\mathbf1\{v=w_{it}\}\)$y_{it}(v)=\mathbf1\{v=w_{it}\}$. Then \[H(y_{it},q_\theta(\cdot\mid w_{i,<t})) =-\sum_v y_{it}(v)\log q_\theta(v\mid w_{i,<t}) =-\log q_\theta(w_{it}\mid w_{i,<t}).\]$$H(y_{it},q_\theta(\cdot\mid w_{i,<t})) =-\sum_v y_{it}(v)\log q_\theta(v\mid w_{i,<t}) =-\log q_\theta(w_{it}\mid w_{i,<t}).$$

The MLE objective. Thus the common next-token cross-entropy loss is exactly the MLE objective, written as one categorical prediction problem at every position.

Population loss decomposition. At the population level, fix a position \(t\)$t$ and regard \(w_{<t}\)$w_{<t}$ and \(w_t\)$w_t$ as random tokens drawn from the text distribution. Write \(p_*(v\mid w_{<t})\)$p_*(v\mid w_{<t})$ for the true conditional probability that the next token \(w_t\)$w_t$ equals \(v\)$v$, given the prefix \(w_{<t}\)$w_{<t}$. Applying the previous entropy identity at each prefix yields \[\begin{aligned} \E[-\log q_\theta(w_t\mid w_{<t})] &=\E_{w_{<t}} H\big(p_*(\cdot\mid w_{<t}),q_\theta(\cdot\mid w_{<t})\big)\\ &=\E_{w_{<t}} H\big(p_*(\cdot\mid w_{<t})\big)\\ &\quad+\E_{w_{<t}} D_{\mathrm{KL}}\big(p_*(\cdot\mid w_{<t})\Vert q_\theta(\cdot\mid w_{<t})\big).\end{aligned}\]$$\begin{aligned} \mathbb{E}[-\log q_\theta(w_t\mid w_{<t})] &=\mathbb{E}_{w_{<t}} H\big(p_*(\cdot\mid w_{<t}),q_\theta(\cdot\mid w_{<t})\big)\\ &=\mathbb{E}_{w_{<t}} H\big(p_*(\cdot\mid w_{<t})\big)\\ &\quad+\mathbb{E}_{w_{<t}} D_{\mathrm{KL}}\big(p_*(\cdot\mid w_{<t})\Vert q_\theta(\cdot\mid w_{<t})\big).\end{aligned}$$

Best conditional distribution. Over all conditional probability distributions, the minimum is attained by \(q_\theta(\cdot\mid w_{<t})=p_*(\cdot\mid w_{<t})\)$q_\theta(\cdot\mid w_{<t})=p_*(\cdot\mid w_{<t})$ on prefixes with positive probability. A restricted model family tries to approximate this target from finite data.

Several plausible continuations. The target is the distribution of text, so there can be several plausible continuations rather than one universally correct next token.

Complete calculation and reading. Exercise 13 gives a finite count example, the one-token gradient, and a numerical check of the summed loss. Further background is in Deep Learning, Chapter 10 and [3].

Independent edges. Suppose \(n\)$n$ is even and a graph has two equally sized communities. For example, the nodes may represent students and an edge may record an interaction. Write \(z_i^*\in\{+1,-1\}\)$z_i^*\in\{+1,-1\}$ for the unknown memberships, with \(\sum_i z_i^*=0\)$\sum_i z_i^*=0$. Conditional on these fixed memberships, edges \((Y_{ij})_{i<j}\)$(Y_{ij})_{i<j}$ are independent, with \[Y_{ij}\sim\begin{cases} \operatorname{Bern}(p^*)&z_i^*=z_j^*,\\ \operatorname{Bern}(q^*)&z_i^*\ne z_j^*, \end{cases} \qquad 0<q^*\le p^*\le\tfrac12.\]$$Y_{ij}\sim\begin{cases} \operatorname{Bern}(p^*)&z_i^*=z_j^*,\\ \operatorname{Bern}(q^*)&z_i^*\ne z_j^*, \end{cases} \qquad 0<q^*\le p^*\le\tfrac12.$$

Parameter space and balance. They need not be identically distributed across all pairs. This is a balanced two-community stochastic block model. Its parameter space is \[\Theta=\{(p,q,z):0<q\le p\le\tfrac12,\quad z\in\{\pm1\}^n,\quad z^\top\mathbf1_n=0\}.\]$$\Theta=\{(p,q,z):0<q\le p\le\tfrac12,\quad z\in\{\pm1\}^n,\quad z^\top\mathbf1_n=0\}.$$

Labels up to a sign. Swapping the community names changes \(z\)$z$ to \(-z\)$-z$ without changing the model, so recovery is always understood up to this global sign.

Count pairs and edges. Recall the earlier likelihood definition: we hold the observed graph fixed while varying its candidate parameters. For a balanced candidate \(z\)$z$, let \(s_w(z)\)$s_w(z)$ and \(s_b(z)\)$s_b(z)$ count observed edges within and between its communities. The numbers of possible pairs are \(N_w=n(n-2)/4\)$N_w=n(n-2)/4$ and \(N_b=n^2/4\)$N_b=n^2/4$. Then

where \(s=s_w+s_b=\sum_{i<j}Y_{ij}\)$s=s_w+s_b=\sum_{i<j}Y_{ij}$ is fixed by the data and \(C_n(p,q)=N_w\log(1-p)+N_b\log(1-q)\)$C_n(p,q)=N_w\log(1-p)+N_b\log(1-q)$. The pair counts and all algebra are derived in Exercise 5.

Balanced minimum bisection. For fixed \(p>q\)$p>q$, the coefficient of \(s_w\)$s_w$ is positive. Maximizing the likelihood over balanced labels therefore amounts to

Equivalently, minimize the number of edges crossing an equal-sized split: this is minimum bisection. It is not max-cut. Removing the balance condition from this within-edge objective would give the trivial all-in-one-group solution. If \(p=q\)$p=q$, every balanced labeling has the same likelihood and the graph contains no information about the memberships.

Unknown probabilities. If \(p,q\)$p,q$ are also unknown, we can first maximize over the finite set of balanced labelings and then optimize over \(p,q\)$p,q$. Because \(q>0\)$q>0$ defines an open boundary, the latter optimization may have a supremum without an attained maximum. Exercise 5 writes this profile expression explicitly; one should not assume the joint MLE always exists.

Information and computation. MoM is flexible: we can specify moment relationships without a full parametric distribution, and the resulting equations may be simple to solve. A few moments, however, may discard useful shape or support information. MLE uses a full probability model and, in regular correctly specified families, has strong large-sample efficiency properties.⁴ Neither the existence of a maximizer nor an efficient numerical method comes for free.

High moments and noise. High moments can be particularly unstable under heavy tails. Although \(\E|X|^j<\infty\)$\mathbb{E}|X|^j<\infty$ makes the \(j\)$j$-th empirical moment meaningful, its variance needs a finite \(2j\)$2j$-th moment. Thus adding more equations can add more noise. Robustness to misspecification, estimation accuracy, and computational cost all belong in the comparison.