Maximum likelihood estimation: derivations by hand

Worked solutions

Problem 1

1. $p(x;\theta) = \theta^{x}(1 - \theta)^{1 - x}$, so $\ell(\theta) = \sum_n\big[x_n\log\theta + (1 - x_n)\log(1 - \theta)\big] = k\log\theta + (N - k)\log(1 - \theta)$.One formula covers both outcomes: $x = 1$ leaves $\theta$ and $x = 0$ leaves $1 - \theta$. The log of the product is the sum of the logs, and $\sum_n x_n = k$, $\sum_n(1 - x_n) = N - k$.
2. $\ell'(\theta) = \dfrac k\theta - \dfrac{N - k}{1 - \theta}$.$\log u$ differentiates to $1/u$; the chain rule on $\log(1 - \theta)$ supplies the minus sign.
3. $\ell'(\theta) = 0 \iff k(1 - \theta) = (N - k)\,\theta \iff \theta = k/N$.Multiply by $\theta(1 - \theta) > 0$, which does not change where the expression is zero; the $k\theta$ terms cancel.
4. $\ell''(\theta) = -\dfrac{k}{\theta^2} - \dfrac{N - k}{(1 - \theta)^2} < 0$ for every $\theta \in (0, 1)$.Both terms are negative because $0 < k < N$. So $\ell$ is strictly concave on $(0, 1)$ and its one stationary point is the global maximum.
5. At $\hat\theta = k/N$: $\dfrac{k}{\hat\theta^2} = \dfrac{N}{\hat\theta}$ and $\dfrac{N - k}{(1 - \hat\theta)^2} = \dfrac{N}{1 - \hat\theta}$, whose sum is $\dfrac{N}{\hat\theta(1 - \hat\theta)}$.Substitute $k = N\hat\theta$ and $N - k = N(1 - \hat\theta)$; over the common denominator $\hat\theta(1 - \hat\theta)$ the numerator is $N(1 - \hat\theta) + N\hat\theta = N$.
6. $\hat\theta = k/N$, and $\ell''(\hat\theta) = -\dfrac{N}{\hat\theta(1 - \hat\theta)}$The curvature grows in proportion to $N$: more flips make a sharper peak. Its reciprocal with the sign flipped, $\hat\theta(1 - \hat\theta)/N$, is the usual estimate of the variance of $\hat\theta$, and here it is exactly $\operatorname{Var}(k/N) = \theta(1 - \theta)/N$ with $\theta$ replaced by $\hat\theta$. If $k = 0$ or $k = N$, $\ell$ is monotonic and the maximum sits at the boundary $0$ or $1$, which is still $k/N$ but is not a stationary point.

Problem 2

1. $\ell(\pi) = \sum_{i=1}^K n_i\log\pi_i$.Each draw of value $i$ contributes a factor $\pi_i$ to the likelihood, and there are $n_i$ of them.
2. $\mathcal L(\pi, \nu) = \sum_i n_i\log\pi_i + \nu\big(1 - \sum_i\pi_i\big)$, with multiplier $\nu$.The $\pi_i$ are not free: on its own $\ell$ increases in every $\pi_i$ and has no stationary point (Mistake 3). The multiplier term enforces $\sum_i \pi_i = 1$.
3. $\partial\mathcal L/\partial\pi_i = n_i/\pi_i - \nu = 0$, so $\pi_i = n_i/\nu$.Only the $i$-th terms of the two sums contain $\pi_i$.
4. $\sum_i n_i/\nu = 1$, so $\nu = \sum_i n_i = N$.Substitute step 3 into the constraint.
5. $\ell$ is a sum of concave functions $n_i\log\pi_i$, and the set $\{\pi : \sum_i \pi_i = 1,\ \pi_i > 0\}$ is convex.A stationary point of the Lagrangian of a concave function under a linear equality constraint is the constrained global maximum.
6. $\hat\pi_i = n_i/N$The estimate is the observed frequency. At $\hat\pi$ every partial derivative $n_i/\hat\pi_i$ equals $N$, so $\nabla\ell$ is parallel to $(1, \dots, 1)$: no move that keeps the sum at $1$ can increase $\ell$ to first order. With $K = 2$ this is Problem 1.

Problem 3

1. $\log P(x;\lambda) = x\log\lambda - \lambda - \log x!$, so $\ell(\lambda) = \big(\sum_n x_n\big)\log\lambda - N\lambda - \sum_n\log x_n!$.The log turns the power into a product and the quotient into a difference; the last sum does not contain $\lambda$.
2. $\ell'(\lambda) = \dfrac{\sum_n x_n}{\lambda} - N = 0 \iff \lambda = \tfrac1N\sum_n x_n$.The constant $\sum_n\log x_n!$ differentiates to $0$.
3. $\ell''(\lambda) = -\dfrac{\sum_n x_n}{\lambda^2} < 0$.$\sum_n x_n > 0$ by assumption, so $\ell$ is strictly concave and the stationary point is the maximum.
4. $\hat\lambda = \bar x$The mean of a Poisson variable is $\lambda$, so the MLE is the sample mean. The exponential distribution, which models the waiting times between Poisson events, also has a parameter called a rate, but its mean is $1/\lambda$ and its MLE is $1/\bar x$ (Mistake 2).

Problem 4

1. $\ell(\mu, \sigma^2) = -\tfrac N2\log(2\pi\sigma^2) - \dfrac{1}{2\sigma^2}\sum_n(x_n - \mu)^2$.The log of the Gaussian density, summed over the data.
2. $\dfrac{\partial\ell}{\partial\mu} = \dfrac1{\sigma^2}\sum_n(x_n - \mu) = 0 \iff \mu = \bar x$, whatever $\sigma^2$ is.$(x_n - \mu)^2$ differentiates to $-2(x_n - \mu)$, and the $-2$ cancels the $-\tfrac12$. Since $\sum_n(x_n - \mu) = N\bar x - N\mu$, the zero does not depend on $\sigma^2$.
3. With $v = \sigma^2$ as the variable: $\dfrac{\partial\ell}{\partial v} = -\dfrac{N}{2v} + \dfrac{1}{2v^2}\sum_n(x_n - \mu)^2 = 0 \iff v = \tfrac1N\sum_n(x_n - \mu)^2$.$\log(2\pi v)$ differentiates to $1/v$ and $1/v$ to $-1/v^2$. Multiply by $2v^2 > 0$ to solve.
4. Put $\mu = \bar x$ from step 2 into step 3.The joint stationary point has to satisfy both equations, and step 2 fixes $\mu$ independently of $v$.
5. For each $v$, $\ell$ is a concave quadratic in $\mu$ with its peak at $\bar x$. With $S = \sum_n(x_n - \bar x)^2 > 0$, the profile $\ell(\bar x, v) = -\tfrac N2\log(2\pi v) - S/(2v)$ has derivative $(S - Nv)/(2v^2)$, positive for $v < S/N$ and negative beyond.So $\ell(\mu, v) \le \ell(\bar x, v) \le \ell(\bar x, S/N)$ for every $(\mu, v)$: the stationary point is the global maximum. $S > 0$ because the $x_n$ are not all equal.
6. $\hat\mu = \bar x$, $\hat\sigma^2 = \tfrac1N\sum_n(x_n - \bar x)^2$The variance estimate divides by $N$, not $N - 1$; Problem 5 shows what that costs. Differentiating with respect to $\sigma$ instead of $\sigma^2$ gives the same answer, because the maximiser does not depend on how the parameter is written.

Problem 5

1. $\sum_n(x_n - \bar x)^2 = \sum_n(x_n - \mu)^2 - N(\bar x - \mu)^2$.Write $x_n - \bar x = (x_n - \mu) - (\bar x - \mu)$ and expand. The cross term is $-2(\bar x - \mu)\sum_n(x_n - \mu) = -2N(\bar x - \mu)^2$, because $\sum_n(x_n - \mu) = N(\bar x - \mu)$; adding the $N(\bar x - \mu)^2$ from the squares leaves $-N(\bar x - \mu)^2$.
2. $\mathbb E\big[\sum_n(x_n - \mu)^2\big] = N\sigma^2$.Each term has expectation $\operatorname{Var}(x_n) = \sigma^2$, and expectation is linear.
3. $\mathbb E\big[(\bar x - \mu)^2\big] = \operatorname{Var}(\bar x) = \sigma^2/N$.$\mathbb E[\bar x] = \mu$, so this is the variance of $\bar x$. By independence $\operatorname{Var}\big(\sum_n x_n\big) = N\sigma^2$, and the factor $1/N$ divides that by $N^2$.
4. $\mathbb E\big[\sum_n(x_n - \bar x)^2\big] = N\sigma^2 - N\cdot\sigma^2/N = (N - 1)\sigma^2$.Steps 1 to 3, by linearity of expectation.
5. $\mathbb E[\hat\sigma^2] = \tfrac{N - 1}{N}\sigma^2$Divide step 4 by $N$. The MLE is biased low: $\bar x$ is fitted to the same data, and it minimises $\sum_n(x_n - c)^2$ over $c$, so the residuals about $\bar x$ are smaller than those about the true $\mu$. Dividing by $N - 1$ instead gives the unbiased sample variance; the two agree as $N \to \infty$.

Problem 6

1. $y_n \sim \mathcal N\big(x^{(n)\top}w, \sigma^2\big)$.$y_n$ is the constant $x^{(n)\top}w$ plus Gaussian noise, and adding a constant shifts the mean without changing the variance.
2. $-\ell(w, \sigma^2) = \tfrac N2\log(2\pi\sigma^2) + \dfrac{1}{2\sigma^2}\|Xw - y\|^2$.Problem 4, step 1, with $\mu$ replaced by $x^{(n)\top}w$ for example $n$; $\sum_n(y_n - x^{(n)\top}w)^2 = \|Xw - y\|^2$ because entry $n$ of $Xw$ is $x^{(n)\top}w$.
3. For every fixed $\sigma^2$, $w$ enters only through $\|Xw - y\|^2$ with the positive coefficient $1/(2\sigma^2)$, so $\hat w$ minimises $\|Xw - y\|^2$: $\hat w = (X^\top X)^{-1}X^\top y$.Minimising a positive multiple of a function has the same minimiser; the least-squares solution is the regression page, Problem 2. The noise level does not affect $\hat w$.
4. With $w = \hat w$, setting $\partial(-\ell)/\partial\sigma^2 = 0$ gives $\sigma^2 = \tfrac1N\|X\hat w - y\|^2$.This is Problem 4, step 3, with the residuals $y_n - x^{(n)\top}\hat w$ in place of $x_n - \mu$.
5. $\hat w = (X^\top X)^{-1}X^\top y$ and $\hat\sigma^2 = \tfrac1N\|X\hat w - y\|^2$Least squares is maximum likelihood under Gaussian noise, and the mean squared error at the optimum is the noise-variance MLE. Like Problem 5, it is biased low, now because $d$ parameters were fitted: dividing by $N - d$ removes the bias.

Problem 7

1. $P(y_n \mid x^{(n)}; w) = p_n^{y_n}(1 - p_n)^{1 - y_n}$ with $p_n = \sigma(x^{(n)\top}w)$.The Bernoulli of Problem 1, with its probability now different for each example.
2. $\ell(w) = \sum_n\big[y_n\log p_n + (1 - y_n)\log(1 - p_n)\big]$.The log of the product of the step 1 factors, as in Problem 1, step 1.
3. $-\ell(w)/N = -\tfrac1N\sum_n\big[y_n\log p_n + (1 - y_n)\log(1 - p_n)\big] = L(w)$So minimising the mean binary cross-entropy is maximum likelihood, and its gradient $\tfrac1N X^\top(\sigma(Xw) - y)$ (regression page, Problem 6) is the negative score divided by $N$. The $1/N$ scales the loss without moving the minimiser. In the same way, softmax cross-entropy is the negative log-likelihood of Problem 2's categorical distribution with per-example probabilities.

Problem 8

1. $\log p(w \mid y) = \log p(y \mid w) + \log p(w) - \log p(y)$.Bayes' rule; $\log p(y)$ does not depend on $w$.
2. $\log p(w) = \sum_j\big[-\tfrac12\log(2\pi\tau^2) - w_j^2/(2\tau^2)\big] = \text{const} - \|w\|^2/(2\tau^2)$.The prior is a product over $j$, so its log is a sum of Gaussian log-densities with mean $0$.
3. $-\log p(w \mid y) = \dfrac{1}{2\sigma^2}\|Xw - y\|^2 + \dfrac{1}{2\tau^2}\|w\|^2 + c$, with $c$ free of $w$.Problem 6, step 2, for $-\log p(y \mid w)$; the $\log(2\pi\sigma^2)$ and $\log(2\pi\tau^2)$ terms and $\log p(y)$ go into $c$.
4. Multiplying by $2\sigma^2/N > 0$: $\tfrac1N\|Xw - y\|^2 + \dfrac{\sigma^2}{N\tau^2}\|w\|^2 + c'$.A positive multiple has the same minimiser, and this one makes the data term a mean.
5. The mean ridge loss with $\lambda$ has minimiser $(X^\top X + N\lambda I)^{-1}X^\top y$, and $N\lambda = \sigma^2/\tau^2$.Regression page, Problem 3, which exists for every $X$.
6. $\lambda = \dfrac{\sigma^2}{N\tau^2}$ and $w_{\text{MAP}} = \big(X^\top X + (\sigma^2/\tau^2)\,I\big)^{-1}X^\top y$Weight decay is a Gaussian prior. A wide prior ($\tau \to \infty$) gives $\lambda \to 0$ and the MLE of Problem 6. For the mean loss, $\lambda$ shrinks as $N$ grows: the prior's pull is fixed while the evidence accumulates.

Problem 9

1. $\log p(w) = -d\log(2b) - \|w\|_1/b$.The log of a product of $d$ Laplace densities: each contributes $-\log(2b) - |w_j|/b$.
2. $-\log p(w \mid y) = \dfrac{1}{2\sigma^2}\|Xw - y\|^2 + \dfrac1b\|w\|_1 + c$.Problem 8, steps 1 and 3, with this prior in place of the Gaussian one; constants go into $c$.
3. Multiplying by $2\sigma^2/N$: $\tfrac1N\|Xw - y\|^2 + \dfrac{2\sigma^2}{Nb}\|w\|_1 + c'$.The same positive rescaling as Problem 8, step 4.
4. $\lambda = \dfrac{2\sigma^2}{Nb}$: the MAP estimate under a Laplace prior is the lassoThe factor is $2\sigma^2$ here and $\sigma^2$ in Problem 8 because the Gaussian prior's exponent carries a $\tfrac12$ and the Laplace prior's does not. $|w_j|$ has a corner at $0$, so there is no closed form in general; the corner in the prior is also what lets the lasso set weights exactly to zero.

Problem 10

1. $L(\theta) = \prod_n p(x_n;\theta) = \theta^{-N}$ if $\theta \ge m$, and $0$ if $\theta < m$, where $m = \max_n x_n$.One factor is $0$ as soon as any $x_n$ lies above $\theta$, and every $x_n$ lies in $[0, \theta]$ exactly when the largest one does.
2. $L'(\theta) = -N\theta^{-N-1} < 0$ for every $\theta > m$, and $L = 0$ below $m$.Above $m$ the likelihood strictly decreases, so no $\theta$ has a zero derivative; below $m$ it is zero, the smallest possible value.
3. $\hat\theta = m$.$L$ jumps from $0$ to $m^{-N}$ at $m$ and decreases afterwards, so its maximum is the left end of the region where it is positive. The maximum is at a discontinuity, where no derivative exists: the calculus recipe assumes a maximum in the interior of a smooth region.
4. $P(\hat\theta \le t) = P(\text{every } x_n \le t) = (t/\theta)^N$ for $0 \le t \le \theta$.The maximum is at most $t$ exactly when every point is, and by independence the $N$ probabilities $t/\theta$ multiply.
5. $\mathbb E[\hat\theta] = \int_0^\theta t\cdot\dfrac{Nt^{N-1}}{\theta^N}\,dt = \dfrac{N}{\theta^N}\cdot\dfrac{\theta^{N+1}}{N + 1} = \dfrac{N\theta}{N + 1}$.Differentiating step 4 in $t$ gives the density $Nt^{N-1}/\theta^N$; then integrate $t^N$.
6. $\hat\theta = \max_n x_n$, with $\mathbb E[\hat\theta] = \dfrac{N\theta}{N + 1}$The MLE can never exceed $\theta$, so it is biased low, by $\theta/(N + 1)$; $\tfrac{N + 1}{N}\max_n x_n$ is unbiased. Problem 1 noted a boundary maximum at $k = 0$; here the maximum is always at a boundary.