Estimation Theory
Table of Contents
1. Expectation-Maximization Algorithm
- Maximum likelihood estimation with incomplete data.
Iterate over E step and M step:
- E step: determine the \( Q(\theta; \theta_{i}) \)
- M step: find \( \theta_{i+1} \) that maximizes \( Q(\theta ; \theta_{i}) \)
\( Q \) is defined as: \[ Q(\theta ; \theta_i) := \mathrm{E}_{\theta_i}[\log L(\theta \mid \mathcal{Z}) \mid \mathcal{X})] \] where \( \mathcal{Z} \) is the unknown complete data, and \( \mathcal{X} \) is the observed incomplete data.
To illustrate, think of a survey on how long people stay subscribed on Netflix. We were only able to observe one thousand people if they subscribe longer than six months or not. Let us call the data \( (x_i)_{i} \). The exact durations that people are subscribed are unknown. Let us call that \( ( Z_i )_i \), since they are random variables.
The likelihood \( L(\theta \mid \mathcal{Z}) \) in terms of \( \mathcal{Z} := ( Z_i )_i \) is given by: \[ L(\theta \mid \mathcal{Z}) := \prod_{i=1}^{1000} \frac{1}{\theta} e^{-Z_i/\theta} \] assuming the durations follow exponential distribution. \( Q \) would be: \[ Q(\theta; \theta_i) = -1000\log \theta - \sum_{j=1}^{1000}\frac{\mathrm{E}_{\theta_i}[Z_j\mid x_j]}{\theta}. \] Note that we are assuming the independence of each observations, and ignoring the influence of other data \( x_{k, k\neq j} \) on \( Z_j \).
In order to calculate the expectation, the parameter \( \theta_i \) from the previous step is used. If we know that a person stayed longer than six months, the expected value for the true duration for that person would be: \[ E_{\theta_i}[Z| Z > 6] = \int_6^{\infty} z f_{Z|Z>6}(z)\,\mathrm{d}z = \int_6^{\infty} z \frac{f_Z(z)}{\mathrm{P}[z > 6]}\,\mathrm{d}z = \theta_i + 6. \]
\( Q(\theta; \theta_i) \) can now be maximized with respect to \( \theta \). The \( \theta \) found here becomes \( \theta_{i+1} \), which is used in \( Q \) to be maximized again.
2. Penalized Least Squares Criterion
Given datapoints \( \{(x_i, y_i)\}_i \), penalized least squares (PLS) looks for the the function \( \hat{f} \) within a Hilbert space that fits the data the most: \[ \hat{f} := \min_{f\in \mathcal{H}} \left[ \frac{1}{n}\sum_i(y_i - f(x_i))^{2} + P(\| f\|^2) \right]. \]
2.1. Kimeldorf-Wahba Representer Theorem
The solution to the PLS can be given in terms of \( K \)-function \[ \hat{f}(x) = \sum_{i=1}^n \beta_i K(x,x_i) \] where \( K \)-function is the reproducing kernels in the reproducing kernel Hilbert space (RKHS), that satisfies \[ \langle f, K(\cdot, x_i)\rangle = f(x_i). \]