on the maximum entropy solution. If those constraints are credible, then this model is also credible. This isn't the first model proposed for which the independence assumptions are reversed. Such models have been proposed formerly in the context of semi-supervised learning [Zhu et al., 2003], probabilistic nonlinear dimensionality reduction
[Lawrence, 2004, 2005] and in models that aim to discover structural form from data [Kemp and Tenenbaum, 2008].

## 2.5 Maximum Likelihood And Blessing Of Dimensionality

Once the form of a maximum entropy density is determined, finding the Lagrange multipliers in the model is equivalent to maximizing the likelihood of the model, where the Lagrange multipliers are now considered to be parameters. The theory underpinning maximum likelihood is broad and well understood, but much of it relies on assuming independence across data points rather than data features. For example, maximum likelihood with independence across data points can be shown to be consistent by viewing the objective as a sample based approximation to the Kullback-Leibler (KL) divergence between the true data generating density, ˜p(y), and our approximation p(y|θ)
which in turn depends on parameters, θ. Taking the expectations under the generating density this KL divergence is written as

$$\operatorname{KL}\left({\bar{p}}(\mathbf{y})\parallel p(\mathbf{y})\right)=\int{\bar{p}}(\mathbf{y})\log{\bar{p}}(\mathbf{y})\mathrm{d}\mathbf{y}-\int{\bar{p}}(\mathbf{y})\log p(\mathbf{y})\mathrm{d}\mathbf{y}.$$

Given n sampled data points from ˜p(y), {yi,:} we can write down a sample based approximation to the KL divergence in the form

$$\operatorname{KL}\left({\tilde{p}}(\mathbf{y})\,\|\,p(\mathbf{y})\right)\approx-{\frac{1}{n}}\sum_{i=1}^{n}\log p(\mathbf{y}_{i,:}|{\boldsymbol{\theta}})+\operatorname{const.},$$

where the constant term derives from the entropy of the generating density, which whilst unknown, does not depend on our model parameters. Since the sample based approximation is known to become exact in the large sample limit, and the KL divergence has a global minimum of zero *only* when the generating density and our approximation are identical, we know that, if the generating density falls within our chosen class of densities, maximum likelihood will reveal it in the large data limit. The global maximum of the likelihood will correspond to a global minimum of the KL divergence. Further, we can show that as we approach this limit, if the total number of parameters is fixed, our parameter values, θ, will become better determined [see e.g. Wasserman, 2003, pg 126]. Since the number of parameters is often related to data dimensionality, p, this implies that for a given data dimensionality, p, we require a large number of data points, n, to have confidence we are approaching the large sample limit and our model's parameters will be well determined. We refer to this model set up as the *sampled-points* formalism.

The scenario described above does not apply for the situation where we have independence across data features.

In this situation we construct an alternative consistency argument, but it is based around a density which describes correlation between data points instead of data features. This model is independent across data features. Models of this type can occur quite naturally. Consider the following illustrative example from cognitive science [Kemp and Tenenbaum, 2008]. We wish to understand the relationship between different animals as more information about those animals' features is uncovered. There are 33 species in the group, and information is gained by unveiling features of the animals. A model which assumes independence over animals would struggle to incorporate additional feature information (such as whether or not the animal has feet, or whether or not it lives in the ocean). A model which assumes independence across features handles this situation naturally. However, to show the consistency of the model we must now think of our model as a generative model for data features, ˜p(y 0), rather than data points.

Our approximation to the KL divergence still applies,

$$\operatorname{KL}\left({\bar{p}}(\mathbf{y}^{\prime})\,\|\,p(\mathbf{y}^{\prime})\right)\approx-{\frac{1}{p}}\sum_{j=1}^{p}\log p(\mathbf{y}_{:,i}|\boldsymbol{\theta})+\operatorname{const.},$$

but now the sample based approximation is based on independent samples of features (in the animal example, whether or not it has a beak, or whether the animal can fly), instead of samples of data points. This model will typically have a parameter vector that increases in size with the data set size, n (in that sense it is non-parametric), rather than the data dimensionality, p. The model is consistent as the number of features becomes large, rather than data points. For our Gaussian random field, the number of parameters increases linearly with the number of data points, but doesn't increase with the number of data (each datum requires O(K) parameters to connect with K neighbors). However, as we increase features there is no corresponding increase in parameters. In other words as the number of features increases there is a clear *blessing of dimensionality*. We refer to this model set up as the sampled-features formalism.