On the Hardness of Entropy Minimization and Related Problems

I Introduction

Joint entropy $H(X,Y)$, conditional entropies $H(X|Y)$, $H(Y|X)$, and mutual information $I(X;Y)$, are some of the founding concepts of information theory. In the present paper we investigate some natural optimization problems associated with these functionals, namely, minimization of joint and conditional entropies and maximization of mutual information over convex polytopes, and show that all these problems are NP-hard. Certain special cases of these problems are found to represent information theoretic analogues of the well-known Subset sum and Partition problems. Our results will thus provide a simple, yet interesting connection between complexity theory and information theory.

Various optimization problems for the above mentioned information measures are studied in the literature. An important example is the well-known Maximum entropy principle formulated by Jaynes , which states that, among all probability distributions satisfying certain constraints (expressing our knowledge about the system), one should pick the one with maximum entropy. It has been recognized by Jaynes, as well as many other researchers, that this choice gives the least biased, the most objective distribution consistent with the information one possesses about a system. Maximizing entropy under constraints is therefore an important problem, and it has been thoroughly studied (see, e.g., ).

It has also been argued that minimum entropy distributions can be of as much interest as maximum entropy distributions. The MinMax information measure, for example, has been introduced in as a measure of the amount of information contained in a given set of constraints, and it is based both on maximum and minimum entropy distributions. More generally, entropy minimization is also very important conceptually. Watanabe has shown that many algorithms for clustering and pattern recognition can be characterized as suitably defined entropy minimization problems.

Since entropy is a concave To avoid possible confusion, concave means $\cap$ and convex means $\cup$. functional, its maximization can be solved by standard concave maximization methods. On the other hand, concave minimization is in general a much harder problem . Indeed, we will show that the minimization of joint entropy over convex polytopes is NP-hard. In fact, we will show that a much more restrictive problem is NP-hard, that of entropy minimization over the so-called transportation polytopes, i.e., entropy minimization under constraints on the marginal distributions. Restricting the problem to transportation polytopes is perhaps the key step in our analysis and has several advantages. First, it enables one to obtain a very simple proof of NP-hardness by using a reduction from the Subset sum problem and some simple information theoretic identities and inequalities. Second, it will immediately follow from this proof that the problems of minimization of conditional entropies and maximization of mutual information are also NP-hard. This claim looks difficult to prove by some other methods because these functionals are neither concave nor convex.

Maximization of mutual information is certainly an important problem, studied in many different scenarios. A familiar example is computing the capacity of the channel which amounts to the maximization of this functional over all input distributions. This is again a convex maximization problem for which efficient algorithms exist . In Section V we will show that the reverse problem – maximizing mutual information over conditional distributions, given the input distribution – is NP-hard. Another important example is the so-called Maximum mutual information (MMI) criterion used in the design of classifiers. See, e.g., for two important applications of this principle.

II Basic definitions

This section reviews the definitions and basic properties of the quantities that will be used later.

Shannon entropy of a random variable $X$ with probability distribution $P=(p_{i})$ is defined as:

with the usual convention $0\log 0=0$ being understood. For a pair of random variables $(X,Y)$ with joint distribution $S=(s_{i,j})$ and marginal distributions $P=(p_{i})$ and $Q=(q_{j})$, the following defines their joint entropy:

again with appropriate conventions. All of these quantities are related by simple identities:

Equalities on the right-hand sides of (6)–(8) are achieved if and only if $X$ and $Y$ are independent. Equalities on the left-hand sides of (6) and (7) are achieved if and only if $X$ deterministically depends on $Y$, or vice versa. Another way to put this is that their joint distribution (written as a matrix) has at most one nonzero entry in every row, or in every column. Equality on the left-hand side of (8) holds if and only if $X$ deterministically depends on $Y$. We will use these properties in our proofs. For their demonstration we point the reader to the standard reference .

From identities (5) one can make the following simple, but crucial, observation: Over a set of two-dimensional probability distributions with fixed marginals (and hence fixed marginal entropies $H(X)$ and $H(Y)$), all the above functionals differ up to an additive constant (and a minus sign in the case of mutual information). This means in particular that the minimization of joint entropy over such domains is equivalent to the minimization of either one of the conditional entropies, or to the maximization of mutual information. Therefore, NP-hardness of any of these problems will imply that all of them are NP-hard. And finally, this will imply that more general problems of minimization/maximization of the corresponding functionals over arbitrary convex polytopes are NP-hard.

II-B Transportation polytopes

Let $\Gamma_{n}^{(1)}$ and $\Gamma_{n\times m}^{(2)}$ denote the sets of one- and two-dimensional probability distributions with alphabets of size $n$ and $n\times m$, respectively:

Now consider the set of all distributions with marginals $P\in\Gamma_{n}^{(1)}$ and $Q\in\Gamma_{m}^{(1)}$, denoted $\mathcal{C}(P,Q)$:

The set of distributions with fixed marginals is basically the set of nonnegative matrices with prescribed row and column sums (only now we require the total sum to be one, but this is inessential). Such sets are known in discrete mathematics as transportation polytopes . Their name comes from the fact that they correspond to the following problem: given $n$ supplies $p_{1},\ldots,p_{n}$ and $m$ demands $q_{1},\ldots,q_{m}$ of some ”goods” (total supply and total demand being equal), describe all ways of transporting the goods so that the demands are fulfilled. For example, one possible solution to the transportation problem with $P=(1,3,5)$ and $Q=(2,4,3)$ would be

which is obtained by the so-called north-west corner rule. The set of all possible solutions constitutes a polytope ${\mathcal{C}}(P,Q)$.

III Entropy over transportation polytopes

As we noted before, we will focus here on sets of probability distributions with fixed marginals, i.e., we will consider the above mentioned optimization problems over transportation polytopes. The problems turn out to be NP-hard even under this restriction, and this is perhaps the easiest way to prove NP-hardness of their more general versions.

Let some marginal distributions $P$ and $Q$ be given, and observe ${\mathcal{C}}(P,Q)$. From identities (5) one sees that over ${\mathcal{C}}(P,Q)$ the minimization of $H(X,Y)$ is equivalent to the minimization of $H(X|Y)$ and $H(Y|X)$, or to the maximization of $I(X;Y)$, so it is enough to consider only the joint entropy for example. Joint entropy $H(X,Y)$ is well-known to be concave in the joint distribution, and so its minimization belongs to a wide class of concave minimization problems which are in general intractable . Conditional entropies $H(X|Y)$ and $H(Y|X)$ are neither concave nor convex in the joint distribution, but over ${\mathcal{C}}(P,Q)$ they are concave because in that case they differ from the joint entropy only by an additive constant. By the same reasoning, mutual information is convex in the joint distribution over ${\mathcal{C}}(P,Q)$. Based on concavity one concludes that the optimizing distribution for these problems must be one of the vertices of ${\mathcal{C}}(P,Q)$. The trouble with concave functions, of course, is that one must visit all of them, or at least a ”large” portion of them, to decide where the minimum is.

The most general form of the problem in the context studied here would be the following: Given a polytope (by a system of inequalities, say) in $\Gamma_{n\times m}^{(2)}$, find the distribution (matrix) $S$ which minimizes the entropy functional $H_{X,Y}(S)$. The decision version of this problem is obtained by giving some threshold $h$ at the input, and asking whether a given polytope contains a distribution $S$ with $H_{X,Y}(S)\leq h$.

Let us now restrict the problem to transportation polytopes. Since:

over the transportation polytope ${\mathcal{C}}(P,Q)$ we have:

with equality if and only if $Y$ deterministically depends on $X$, or vice versa . In other words, we will have equality in (13) iff the joint distribution is such that it has at most one nonzero entry in every row, or in every column. We can now formulate an even more restrictive problem, with the threshold specified in advance: Given a transportation polytope ${\mathcal{C}}(P,Q)\in\Gamma_{n\times m}^{(2)}$, is there a distribution $S$ in this polytope with $H_{X,Y}(S)\leq H(P)$? Note that, because of (13), this inequality must in fact be an equality. We name this problem Entropy minimization even though the name would probably be more appropriate for the more general problems mentioned above.

Positive rational numbers $p_{1},\ldots,p_{n}$ and $q_{1},\ldots,q_{m}$, with $\sum_{i=1}^{n}p_{i}=\sum_{j=1}^{m}q_{j}=1$.

Is there a matrix $S\in\mathcal{C}(P,Q)$ with entropy $H_{X,Y}(S)=H(P)$?

This problem will be shown to be NP-complete.

We also briefly note here that the corresponding problem of the maximization of $H(X,Y)$ (maximization of $H(X|Y)$ or minimization of $I(X;Y)$) over ${\mathcal{C}}(P,Q)$ is trivial because:

with equality if and only if $X$ and $Y$ are independent , i.e., iff their joint distribution is $P\times Q=(p_{i}q_{j})$, and this distribution clearly belongs to ${\mathcal{C}}(P,Q)$.

III-B The proof of NP-hardness

We describe first the Subset sum, a well-known NP-complete problem , which will be the basis of the proof to follow:

Positive integers $d_{1},\ldots,d_{n}$ and $s$.

Is there a $J\subseteq\{1,\ldots,n\}$ such that $\sum_{j\in J}d_{j}=s$ ?

We shall demonstrate a reduction from the Subset sum problem to the Entropy minimization problem. Let there be given an instance of the Subset sum problem, i.e., a set of positive integers $s\,,\,d_{1},\ldots,d_{n}$, $n\geq 2$. Let $D=\sum_{i=1}^{n}d_{i}$, and let $p_{i}=d_{i}/D$, $q=s/D$. The question we are trying to answer is whether there is a $J\subseteq\{1,\ldots,n\}$ such that $\sum_{j\in J}d_{j}=s$. Observe that this is equivalent to asking whether there is a matrix $S$ with row sums $P=(p_{1},\ldots,p_{n})$ and column sums $Q=(q,1-q)$, which has at most one nonzero entry in every row (or, in probabilistic language, such that $Y$ deterministically depends on $X$). We know that in this case, and only in this case, the entropy of $S$ would be equal to $H(P)$ . So if we create an instance of the Entropy minimization problem with $P$ and $Q$ as above, the answer to the question whether there exists $S\in\mathcal{C}(P,Q)$ with $H_{X,Y}(S)=H(P)$ will solve the Subset sum problem. Therefore, this is the reduction we wanted. It is left to prove that Entropy minimization belongs to NP. This is done by using the familiar characterization of the class NP via certificates . We have to show that every Yes-instance of the problem has a succinct certificate, while no No-instance has one, and that the validity of the alleged certificates can be verified in polynomial time. The certificate is of course the optimizing distribution itself. That it is succinct is easy to show (see the comment in the last paragraph of Section II-B), and polynomial time verifiability is even easier, because we only have to check that $S$ belongs to $\mathcal{C}(P,Q)$ and that it has at most one nonzero entry in every row. ∎

As a straightforward consequence of the above claim, the more general problem of finding a minimizing distribution is NP-hard. It is an interesting task to determine the precise complexity of this problem (in the sense of proving that it is complete for some natural complexity class). Note that even determining whether it belongs to FNP The class FNP captures the complexity of function problems associated with decision problems in NP, see . is nontrivial. Whether the decision version of this problem, namely, deciding whether a given polytope contains a distribution with entropy smaller than a given threshold, belongs to NP is also an interesting question (which we shall not be able to resolve here). One has to be careful when reasoning about ”certificates” for these problems. Namely, one has to able to check in polynomial time that the certificate is indeed valid. In the above proof, we only had to check that the given matrix (the alleged certificate) belongs to $\mathcal{C}(P,Q)$ (i.e., that it has nonnegative entries and prescribed row and column sums) and that it has at most one nonzero entry in every row, and this is clearly easy to do. But in the more general problems mentioned above, one is required to compute numbers of the form $a\log a$ to check whether $H(T)\leq h$ for example. These numbers are in general irrational, and therefore verifying this inequality might not be computationally trivial as it might seem. It is interesting to mention in this context the so-called Sqrt sum problem:

Positive integers $d_{1},\ldots,d_{n}$, and $k$.

Decide whether $\sum_{i=1}^{n}\sqrt{d_{i}}\leq k$ ?

This problem, though ”conceptually simple” and bearing certain resemblance with checking of certificates in the general versions of the entropy minimization problem, is not known to be solvable in NP (it is solvable in PSPACE).

IV Two pseudometrics which are hard to compute

A variant of the minimization of the above mentioned quantities produces a distance on the space of discrete probability distributions. For a pair of random variables $(X,Y)$ with joint distribution $S$, define :

The quantity $\Delta(X,Y)$ is sometimes called the variation of information. Its normalized variant, $\Delta^{\prime}(X,Y)$, is basically an information theoretic analogue of the Jaccard distance between finite sets. Both of these quantities satisfy the properties of a pseudometric . However, when this statement is made, one must assume that the joint distribution of $(X,Y)$ is given because joint entropy and mutual information are not defined otherwise. This is usually overlooked in the literature. Furthermore, if these quantities are used as distance measures on the space of all random variables, then joint distributions of every pair of random variables must be given. For example, one could first define some random process $(X_{t})$ and then take $\Delta$ or $\Delta^{\prime}$ as distances between the random variables $X_{t}$. In order to avoid the dependence on the chosen random process (or on some universal joint distribution), and to define a distance between individual random variables (more precisely, between their distributions) one can make the following definitions:

This definition mimics the one for the total variation distance:

where the infimum is taken over all joint distributions of the random vector $(X,Y)$ with marginals $P$ and $Q$.

$\underline{\Delta}$ and $\underline{\Delta}^{\prime}$ are pseudometrics on $\Gamma^{(1)}$.

The proof of this proposition is not difficult but we omit it here since it is not essential for our current aims. We can now prove one more intractability result.

Given rational $P$ and $Q$, determining whether $\underline{\Delta}(P,Q)=H(P)-H(Q)$ is NP-hard.

Now the claim follows directly from Theorem 1. ∎

V One marginal fixed

In this section we address similar problems as before, only now we fix only one of the marginal distributions, say $P=(p_{1},\ldots,p_{n})$. If the cardinality of the alphabet of the other random variable $Y$ is not specified, then the problems are trivial. Namely, one takes $Q=P$ and for $S=\text{diag}(P)$ (two-dimensional distribution with masses $p_{i}$ on the diagonal and zeros elsewhere) one has $H_{X,Y}(S)=I_{X;Y}(S)=H(P)$, and hence $S$ is optimal. So assume that the cardinality of the other alphabet is bounded to $m$. Denote the set of all distributions with marginal distribution of $X$ fixed to $P$ and the cardinality of the alphabet of $Y$ fixed to $m$, by ${\mathcal{C}}(P,m)$. We have

Minimization of the joint entropy $H(X,Y)$ over such polytopes is trivial. The reason is that $H(X,Y)\geq H(P)$ with equality iff $Y$ deterministically depends on $X$, and so the solution is any joint distribution having at most one nonzero entry in each row. Since $H(X)$ is fixed, this also minimizes the conditional entropy $H(Y|X)$. The other two optimization problems considered so far, minimization of $H(X|Y)$ and maximization of $I(X;Y)$, are still equivalent because $I(X;Y)=H(X)-H(X|Y)$, but they turn out to be much harder. Therefore, in the following we shall consider only the maximization of $I(X;Y)$.

When one marginal is fixed, choosing the optimal joint distribution amounts to choosing the optimal conditional distribution $p(y|x)$. Mutual information $I(X;Y)$ is known to be convex in the conditional distribution (and hence, $H(X|Y)$ is concave in $p(y|x)$, for fixed $p(x)$) and so this is again a convex maximization problem. This conditional distribution can be thought of as a discrete memoryless communication channel with $n$ input symbols and $m$ output symbols, and hence we name the corresponding computational problem Optimal channel.

Positive rational numbers $p_{1},\ldots,p_{n}$ with $\sum_{i=1}^{n}p_{i}=1$, and an integer $m$.

Is there a channel $C\in{\mathcal{C}}(P,m)$ with mutual information $I_{X;Y}(C)\geq\log m$ ?

Note that the above inequality must in fact be an equality because over ${\mathcal{C}}(P,m)$:

which follows from (7) and the fact that $H(Y)\leq\log m$. The above problem is a suitable restriction of a more general problem of finding a maximizing distribution, as we did with Entropy minimization.

We describe next the well-known Partition (or Number partitioning) problem .

Is there a partition of $\{d_{1},\ldots,d_{n}\}$ into two subsets with equal sums?

This is clearly a special case of the Subset sum problem. It can be solved in pseudo-polynomial time by dynamic programming methods . But the following closely related problem is much harder.

Nonnegative integers $d_{1},\ldots,d_{3m}$ and $k$ with $k/4<d_{j}<k/2$ and $\sum_{j}d_{j}=mk$.

Is there a partition of $\{1,\ldots,3m\}$ into $m$ subsets $J_{1},\ldots,J_{m}$ (disjoint and covering $\{1,\ldots,3m\}$) such that $\sum_{j\in J_{r}}d_{j}$ are all equal? (The sums are necessarily $k$ and every $J_{i}$ has $3$ elements.)

This problem is NP-complete in the strong sense , i.e., no pseudo-polynomial time algorithm for it exists unless P=NP.

The following theorem will establish that, given an information source, determining the best channel (in the sense of having the largest mutual information) is NP-hard.

We prove the claim by reducing 3-Partition to Optimal channel. Let there be given an instance of the 3-Partition problem as described above, and let $p_{i}=d_{i}/D$ where $D=\sum d_{i}$. Deciding whether there exists a partition with described properties is clearly equivalent to deciding whether there is a matrix $C\in\mathcal{C}(P,\,m)$ with the other marginal $Q$ being uniform and $C$ having at most one nonzero entry in every row (i.e., $Y$ deterministically depending on $X$). This on the other hand happens if and only if there is a matrix $C\in\mathcal{C}(P,\,m)$ with mutual information equal to $H(Q)=\log m$. Therefore, solving the Optimal channel problem with instance $(p_{i})$ as above will solve the 3-Partition problem. This shows the NP-hardness of Optimal channel. It is left to prove that it belongs to NP. The reasoning here is completely analogous to the one in the proof of Theorem 1, namely, the certificate is the optimal distribution/matrix itself. ∎

The problem remains NP-complete even over ${\mathcal{C}}(P,\,2)$, i.e., when the cardinality of the channel output is fixed in advance to $2$. In that case the problem is equivalent to the Partition problem.

It is easy to see that the transformation in the proof of Theorem 3 is in fact pseudo-polynomial which implies that Optimal channel is strongly NP-complete and, unless P=NP, has no pseudo-polynomial time algorithm.

Acknowledgment

The authors would like to acknowledge the financial support of the Ministry of Science and Technological Development of the Republic of Serbia (grants No. TR32040 and III44003).

References