The Principle of Uncertain Maximum Entropy

The Principle of Maximum Entropy may be thought of as a special case of the Principle of Minimum Cross Entropy (see Shore and Johnson, 1980; Wu, 2012; Kárnỳ, 2020). Suppose that we have a prior distribution $Q(X)$ whose information we wish to incorporate into $P(X)$ in addition to $\tilde{P}(X)$. The Principle of Minimum Cross Entropy specifies that we should choose the distribution that requires the least additional information from $Q(X)$ while satisfying the constraints. In other words, in the set of all $P(X)$ that satisfy the constraints, we should choose the one that is most similar to $Q(X)$ as measured by the Kullback–Leibler divergence. Replace the objective in equation 1 with:

Solving, we find the definition of $\Pr(x)\leavevmode\nobreak\ =\leavevmode\nobreak\ q(x)e^{\sum\nolimits_{k=1}^{K}\lambda_{k}\phi_{k}(x)}/Z(\lambda)$, where
$Z(\lambda)\leavevmode\nobreak\ =\leavevmode\nobreak\ {(e^{-1}e^{\eta})}^{-1}\leavevmode\nobreak\ =\leavevmode\nobreak\ \sum\limits_{x^{\prime}\in\mathcal{X}}q(x^{\prime})e^{\sum\nolimits_{k=1}^{K}\lambda_{k}\phi_{k}(x^{\prime})}$

In the event that $Q(X)$ is the uniform distribution the Principle of Minimum Cross Entropy is equivalent to the Principle of Maximum Entropy.

One requirement of the principle of maximum entropy is that the variable $X$ is completely observable in order to calculate $\tilde{P}(X)$ (or $\tilde{\Phi}$). In many real-world cases this is not possible as some portion of $X$ is hidden from observation due to occlusion (Bogert et al., 2016), underlying hidden structure, or missing data. Wang et al. (2012) model this as $X$ containing a latent variable and describe the principle of latent maximum entropy which generalizes the standard principle to these scenarios.

Divide each $X$ into $Y$ and $Z$ such that $X=Y\cup Z$ and $P(X)\leavevmode\nobreak\ =\leavevmode\nobreak\ P(Y,Z)$. $Y$ is the portion of $X$ that is perfectly observed while $Z$ is perfectly hidden, and let $\mathcal{Z}_{y}$ be the set of all $z$ which when combined with a given $y$ forms a $x\in\mathcal{X}$. The Principle of Latent Maximum Entropy is now defined as:

Intuitively, this program corrects for the missing portion of $X$ in the empirical data by constraining the distribution over $X$ to match the feature expectations of the observed components $Y$ while taking into account any known structure in the hidden portion $Z$. Notice that $Pr(z|y)={\frac{Pr(x)}{\sum\nolimits_{x^{\prime}\in\mathcal{X}}Pr(x^{\prime})}}$, therefore the right side of the constraint which computes the empirical feature expectations has a dependency on the program solution. This leads to a non-convex program which is solved by approximating $P(X)$ to be log-linear and making use of Expectation-Maximization.

In the event that $X$ may only be partially observed, for instance, if observations of $X$ are corrupted by noise, it is possible for standard maximum entropy approaches to fail as the empirical feature expectations could be unmatched with any distribution over $X$. In spite of this, we may still desire to make use of the principle of maximum entropy to encode any information available and exclude error.

For clarity, we make a distinction between the data points produced by the noisy observation method and the elements of the system being observed. Let $O$ be a random variable whose elements $o\in\mathcal{O}$ correspond to all possible received observations from a system represented by $X$. The non-deterministic observation function $P(O|X)$ captures all information available about the observation methods employed to gather information about $X$. While $\mathcal{O}$ may in principle be infinite it is common to limit this set to only those observation methods that have minimal impact on $P(X)$, are low error (low entropy $P(O|X)$), are economically or practically feasible to perform, etc.

Now, given the observation function and the true distribution over $X$, $P_{0}(X)$, we may find the true distribution over $O$ as $P_{0}(O)=P(O|X)P_{0}(X)$. For simplicity, in this work, we assume this distribution exists and any observation methods sample from this distribution directly to produce $\tilde{P}(O)$. We also assume unless otherwise noted that $P(O|X)$ is either perfectly known or estimated to be within a negligible margin of error. This may be done as part of calibration or training of the observation methods. An example of this process could be tuning the frequency of an antenna and computing the standard deviation of the background noise distribution.

Many existing ad hoc approaches involve relaxing the constraints to avoid undesirable noise being incorporated into $P(X)$. For instance, as mentioned in section 1, suppose the error is zero mean Gaussian. Then we may relax the feature expectation constraint to account for the error as $\chi^{2}={{|\Phi-\tilde{\Phi}|^{2}}/\sigma^{2}}$, where $\sigma$ is the error’s standard deviation and $\chi^{2}$ is the chi-squared statistic. Unfortunately, while finding feasible solutions, due to the constraint relaxation we may no longer interpret $P(X)$ as encoding only the information in the feature expectations. Instead, we may say that the solution is the distribution with the maximum entropy found within the $\chi^{2}$ ellipsoid (Skilling and Bryan, 1984), making the interpretation ad hoc.

As a step towards a solution to scenarios with arbitrary observation models, it is possible to simply select the most likely $x$ given an observation sample $o$, ie. $ML_{x}(o)=\mathop{\mathrm{argmax}}\limits_{x}Pr(x|o)$ and use these to compute $\tilde{P}(X)$. This method does not introduce error provided that the observation function is unambiguous, where for each o the observation function $\textbf{{Pr(o}}\mathbf{|}\textbf{{x)}}$ is non-zero for exactly one x, and for each x $\textbf{{Pr(o}}\mathbf{|}\textbf{{x)}}$ is non-zero for at least one o.

It is common in practice for experimenters to selectively limit or engineer the observation methods to produce a low error when this method is used. Specifically, for observation methods in which $P(O|X)$ is close to unambiguous, the error tends to be tolerable, particularly in discrete $\mathcal{X}$ domains with categorical error. However, there are serious concerns with this approach. As $P(X|O)\propto P(O|X)P(X)$, what should we choose the unknown $P(X)$ to be? Common choices include the uniform distribution or a known prior, and this choice may unexpectedly impact the results, particularly if a prior is used for $P(X)$. For example, $P(X|O)$ must be checked to ensure every $x$ has at least one $o$ for which it is most likely, or else the resulting $\tilde{Pr}(x)$ will be 0.

The effect of the Most-Likely-x method is to produce a $\tilde{P}(X)$ that may vary significantly from $P_{0}(X)$. The magnitude of this distortion is dependent on the distance $P(O|X)$ is from being unambiguous . We discuss this further in Appendix A. In the event $P(O|X)$ is not completely known the Most-Likely-x method may be utilized provided for every observation the most likely $x$ is identifiable. However, in this case, the amount of error introduced into the posterior is also unknown.

Finally, we note that in many real-world scenarios, it is difficult or impossible to engineer the observation methods such that the resulting observations approach unambiguous, which limits the applicability of this method.

As a straightforward attempt to improve upon Most-Likely-x we could first utilize the principle of maximum entropy to find a distribution for $X$ that encodes only the information present in the observations, then use this distribution as $\tilde{Pr}(x)$ in a second feature-constrained principle of maximum entropy program. We define the first program as:

Solving, we find $Pr^{\prime}(x)\propto e^{\sum\nolimits_{o\in\mathcal{O}}\lambda_{o}Pr(o|x)}$. Once solved, $P^{\prime}(X)$ is used in equation 1 as $\tilde{P}(X)$ to produce a final $P(X)$. We call this algorithm MaxEnt-MaxEnt.

As can be seen in our experimental results section, MaxEnt-MaxEnt offers a substantial improvement in accuracy over Most-Likely-x, however, there are a number of theoretical objections we may raise to its use. Because the true $P_{0}(X)$ is not parameterized using the observation function, there is no guarantee that equation 6 will be able to produce an accurate distribution over $X$. As the first program outputs a high-entropy distribution over $X$, no significant improvement over $P^{\prime}(X)$ is likely in the second program. Further, as $\mathcal{O}$ grows in size relative to $\mathcal{X}$ it becomes increasingly difficult to find a vector of weights that produces a $P^{\prime}(X)$ that satisfies the constraints. For these reasons, the accuracy of this technique is dependent upon the structure of the observations, an undesirable situation.

By contrast, if the observation function provides error-free information, ie, each observation could only have one $x$ as its source, the principle of uncertain maximum entropy reduces to the standard principle of maximum entropy.

See proof in Appendix C. A theorem and proof of the generalization of the principle of latent maximum entropy is given in Appendix H.

See proof in Appendix D. Intuitively, as applying a function to a random variable can only decrease its entropy (or leave entropy unchanged), using any function to produce $\tilde{P}(X)$ from $\tilde{P}(O)$ may add information not present in the observations. This includes both methods discussed in section 2.

The Principle of Uncertain Maximum Entropy avoids these potential sources of bias, producing solutions with potentially higher entropy than can be achieved by the corresponding classic principle. All else being equal we expect less error more often from the new principle’s solutions, which we will examine in our experiments.

We note here two cases where the new principle’s solution is known to be equivalent to that produced by the classic principle.

See proof in Appendix E

To begin our attempt at solving equation 7 we take the Lagrangian:

And the Lagrangian’s gradient.

Unfortunately, the existence of $Pr(x|o)$ on the right side of the constraints causes the derivative to be non-linear in $P(X)$. To make further progress, we require a reasonable closed-form approximation for $P(X)$. To arrive at one, we must make an assumption about the relationship between the model and observations, as we desire a definition of $P(X)$ that is independent of the methods used to observe it. In other words, assume every $x$ exists independently of the methods used to observe them and $\mathcal{O}$ is chosen such that $P_{0}(X)$ is not significantly altered by any of the observation methods in use. Given this, we drop the last term of equation 10 in order to approximate $P(X)$ to be log-linear in its features alone:

Now if we plug our approximation back into equation 9 we arrive at a function that appears similar to a Lagrangian Dual:

However, this function’s minima is not located at a $\lambda$ that produces the correct $P(X)$ (this may be seen by noting its gradient is not zero when the constraints of equation 7 are satisfied). Therefore, unable to simply minimize this function directly, we take a different approach.

Inspired by Wang et al. (2012), the constraints of equation 7 can be satisfied by locally maximizing the likelihood of the observed data. One method is to derive an Expectation- Maximization based algorithm utilizing our log-linear model. We begin with the log likelihood of all the observations:

Equation 13 follows because we assume the observation function $P(O|X)$ is known and does not depend on $\lambda$. This leaves $Q(\lambda,\lambda^{\prime})$ as the only function which depends on $\lambda$. For the sake of completeness, we note that $H^{X}(\lambda^{\prime})$ the empirical conditional entropy of the model and $H^{O}(\lambda^{\prime})$ is the conditional entropy of the observation function if $\tilde{P}(O)=P_{\lambda^{\prime}}(O)$. While these impact the data likelihood they do not alter the solution as they do not depend upon $\lambda$.

We now substitute the log-linear model of $Pr(x)$ (equation 11) into $Q(\lambda,\lambda^{\prime})$:

The expectation-maximization algorithm proceeds by iteratively maximizing $Q$, and upon convergence $\lambda=\lambda^{\prime}$, at which point the likelihood of the data is at a stationary point (first derivative is zero). EM is guaranteed to converge to such points as the likelihood monotonically increases each iteration (McLachlan and Krishnan, 2007).

Notice that at convergence, when $\lambda=\lambda^{\prime}$, equation 15 is the exact negative of equation 12. It remains to be shown, however, that all stationary points that equation 15 may converge to satisfy the constraints of equation 7.

See proof in Appendix F.

Working backward, the process of maximizing $Q(\lambda,\lambda^{\prime})$ is equivalent to solving the following convex program by minimizing its Lagrangian dual, where we abuse notation slightly to mark the respective parameterization of $P(X)$:

which exactly equals Eq. 7 at EM convergence. Therefore, we have found a convex approximation to the principle of uncertain maximum entropy.

However, as EM is well known to become trapped in local maxima, solver restarts with different initial $\lambda^{\prime}$ are recommended. Then, whichever solution among those found has the maximum entropy is chosen as the final output. Thus, we arrive at algorithm 1.

To empirically validate the performance of our uMaxEnt algorithm, we compare it to the Most-Likely-x and MaxEnt-Maxent approaches in small problems (randomly chosen $P_{0}(X)$ and $P(O|X)$), as well as a number of controls. $\Phi$ is set to a random sparse matrix, where 25% of the entries are 1 and all others 0, and $K$, the number of features, varies between one-half and twenty times $|\mathcal{X}|$. The results can be seen in figure 1 for $|\mathcal{X}|=10$ and $|\mathcal{O}|=20$ as the average Jensen-Shannon Divergence (JSD) between $P_{0}(X)$ and $P(X)$ achieved by each method as the number of observation samples increases (further experiment details in Appendix I). Notice that True X, in which the true $x$ for each sample is provided to MaxEnt achieves a low error that quickly approaches zero, while ML x, which uses the Most-Likely-x algorithm for each $o$ sample (assuming uniform prior) converges at a high error. Notice also the contrast between the two controls True $\mathbf{P(X)}$ and Uniform $\mathbf{P(X)}$, which simply compute one iteration of uMaxEnt using $P_{0}(X)$ and $U(X)$ respectively as $P(X)$ in the E step. Finally, uMaxEnt and MaxEnt-MaxEnt perform well, reaching lower error than all other methods except those with perfect knowledge.

As mentioned in section 2.5, the performance of MaxEnt-MaxEnt is very sensitive to the size of $\mathcal{O}$, which we show in figure 2 (left) in comparison to uMaxEnt. Notice that both methods perform similarly for $|\mathcal{O}|\leq 20$ but while uMaxEnt converges on a low error above 20 MaxEnt-MaxEnt’s performance degrades significantly with larger $\mathcal{O}$ such that a size of 100 performs approximately as well as 5.

Finally, we look for cases where $uMaxEnt$ finds degenerate solutions in an attempt to disprove Conjecture 1. Let $\omega=[\frac{\tilde{Pr}(o)}{Pr(o)}\leavevmode\nobreak\ \forall\leavevmode\nobreak\ o]$, $\Omega=[\sum\limits_{o}\omega\times Pr(o|x)\leavevmode\nobreak\ \forall\leavevmode\nobreak\ x]$ and the Euclidean distance between each of these vectors and a vector of all 1s be their respective error. In a degenerate solution $\omega\neq[1,1...]$ while $\Omega=[1,1...]$, however, due to a number of factors $uMaxEnt$ is not expected to find zero error solutions (see Appendix I). Therefore our strategy is to look for cases where the error of $\omega$ is inexplicably high relative to the error in $\Omega$ and manually examine these to identify any approximate degenerate solutions. As can be seen in an example scatter plot in figure 2 (right) we arguably do not see these extreme outliers, nevertheless we examine the few existing outlier cases and find no evidence of a degenerate solution.

A key requirement for applications of uMaxEnt is that the observation function $P(O|X)$ is known or accurately estimated. In this section we describe scenarios where this requirement cannot be met through direct estimation, but we may instead use widely available machine learning techniques to approximate $P(X|O)$ and use this in a modified uMaxEnt program as a reasonable approximation. We demonstrate this technique in a simple machine vision application and compare it to the performance of uMaxEnt when the observation function is exactly known.

Suppose that $P(O|X)$ is unknown and cannot be accurately estimated through standard sampling techniques because $|\mathcal{O}|$ is extremely large and $P(O|X)$ is sparse, meaning the probability of observing most $o$ for any specific $x$ is zero. This makes the amount of samples needed to estimate $P(O|X)$ prohibitively high and non-zero probability samples potentially costly to generate.

To make progress, we may perform supervised learning using a machine learning model. Suppose we label a number of $o$ samples with the corresponding $x$ that produced them. We may then train our learning model to output the distribution $P_{BB}(X|O)$ with the lowest amount of training error. Notice that even though $P(O|X)$ is sparse, $P(X|O)$ is not necessarily sparse and is often an attractive target for estimation in these cases. We do not place any other requirements on the learning model, allowing it to be a ”black box” for our purposes.

Once trained we deploy the model by receiving new, perhaps previously unseen, $o$ samples from an unknown $P_{0}(O)$ and use the model to predict $P_{0}(X)$. To incorporate known features $\Phi$ into our answer a straightforward approach would be to gather the predictions into $\tilde{P}(X)$ and utilize the principle of maximum entropy. However, these predictions are expected to contain some amount of error leading to the issues described in section 2.3.

We will therefore employ the principle of uncertain maximum entropy, but despite the similarity we cannot use $P_{BB}(X|O)$ directly in place of $P(X|O)$ in uMaxEnt as the assumed black box nature does not permit us to make use of $P(X)$ in the E step. Instead, we will interpret the black box model as transforming the large sparse observation space $\mathcal{O}$ into another observation space which happens to be the same as the model $\mathcal{X}$. To avoid confusion, we will mark all predictions made by the black box using a separate variable from the uMaxEnt elements: $o^{X}\in\mathcal{O}^{X}$ where $\mathcal{O}^{X}=\mathcal{X}$.

Let the empirical observations $\tilde{P}(O^{X})={1\over N}\sum\limits_{n=1}^{N}P_{BB}(O^{X}|o_{n})$, where $o_{n}$ is the $n^{th}$ observation. We may now estimate the new observation function, $P(O^{X}|X)$, as the probability that the black box outputs $o^{x}$ given the observations generated from $x$. For instance, if given a set of labeled observations $(o,x)$, we can compute $P(O^{X}|X)$ as:

$Pr(o^{x}|x)\approx\eta\sum\limits_{(o,x^{\prime}):x^{\prime}=x}Pr_{BB}(o^{x}|o)$

where $\eta$ is a normalizer.

Again, we place no other requirements on the black box, only that we are able to estimate its prediction accuracy. This allows us to use any source of predictions for our black box model, including large deep learning systems, a human’s most likely guess, or high-noise indirect observations specific to a given environment (Bogert and Doshi, 2022; Torralba and Freeman, 2014; Baradad et al., 2018).