Agreeable Instantia

The class of all discrete and continuous probability distributions forms a remarkably rich space of functions, and one that may prove to deserve a great deal of our attention. Within this space, exponential families provide an algebraically succinct description of a broad and important class of probability distributions. This description is capable of exactly representing many of the probability distributions most familiar to statistics and probability theory. This post will not pursue the question of exactly how expansive the class described by exponential families is. Instead, we will consider a number of specific examples demonstrating how the general algebraic form of an exponential family can be identified with familiar probability distributions.

The exponential-family representation becomes particularly useful because the realization of its general form as a particular probability distribution can be described through a natural parameter and a sufficient statistic.

$T(x)$ is the sufficient statistic, $\eta$ is the natural parameter, and $A(\eta)$ is the log-partition function that normalizes the distribution. Together, these objects provide a compact parameterization through which observations can be related to a particular member of the exponential family. For an observed sequence ($x_1,\ldots,x_t$), the data relevant to maximum-likelihood estimation can be compressed into the empirical sufficient statistic

An algorithm that uses the algebraic structure of exponential families to compute the sufficient statistic and natural parameter of the Maximum Likelihood Estimator from an observed sequence, and then uses these quantities to update its probability distribution and predictions at each step, turns out to provide an excellent description of an Online Learner capable of achieving the asymptotic convergence associated with Universal Prediction.

The algebraic description of probability distributions given by Exponential families is as follows

Aptly named exponential families, as any given probability distribution is specified by a factor $h(x)$ multiplied by the exponential of the inner product of the natural parameter $\eta$, with the sufficient statistic $T(x)$, subtracted by log-partition function of the natural parameter $A(\eta)$.

Maximum Likelihood Estimation involves observing a sequence of data and computing the probability distribution which maximizes the probability of observing that data. Maximum Likelihood Estimation often involves the consideration of the log-likelihood.

Given data

the log-likelihood of the form given by the exponential family is

$\ell_n(\eta) = \sum_{i=1}^n \log p_\eta(x_i) = \eta^\top \sum_{i=1}^n T(x_i) – nA(\eta) + \sum_{i=1}^n \log h(x_i).$

Importantly, when derivative of the log-likelihood reaches zero, so too should the derivative of the likelihood, and when the derivative of the likelihood reaches zero, the likelihood reaches a maximum.

Thus when considering the log-likelihood in Maximum Likelihood Estimation, often it is convenient to solve for the derivative of the log-likelihood equal to zero.

The Exponential Family functional is highly determined by the sufficient statistic $T(x)$ and the natural parameter $\eta \hspace{0.3mm}$, especially when conditioning on observed sample data.

In the Online Learning setting, with data

we want to calculate

Consider a concrete example

This example demonstrates the exponential family predictor’s convergence to the optimal distribution in the setting when observations are generated by the Bernoulli distribution. Given a ledger of events occurring with a fixed probability, learning in the online setting to predict the event with a probability given by the empirically observed frequency of events.

The maximum likelihood estimator of the exponential family over an observed sequence of data is well suited to the problem of online learning because of its convergence to the optimal distribution, but in particular, its rate of convergence is compelling enough to identify it as a member of the class of universal predictors whose cumulative convergence is logarithmic in the number of observations and whose average regret is asymptotically zero as a result.

By the Law of Large Numbers, the empirical mean of the sufficient statistic converges to its expectation under the true distribution. The Central Limit Theorem further characterizes the rate of this convergence: under the usual finite-variance and independence conditions, the variance of the empirical mean decreases proportionally to $1/t$, the fluctuations of the observed sufficient statistic around its expectation occur at the $1/\sqrt{t}$ scale. The natural parameter of the Maximum Likelihood Estimator is obtained by applying the inverse of the gradient of the log-partition function to this empirical mean. Provided that this inverse is smooth in a neighborhood of the true parameter, it preserves the $1/\sqrt{t}$ order of the estimation error. Consequently, the variance of the learned natural parameter also decreases at the $1/t$ rate.

IF the joint distribution of the data source $p(x_t | x_{t-1})$ has a finite alphabet, is there a way to develop performance and/or regret bounds based on the size of the alphabet and number of observations shown to an exponential family approximator?