0
$\begingroup$

In information theory the information entropy of a vector of probabilities $\bf p$ can be defined as

$$I_b({\bf p}) = -\sum_{\forall i} p_i \log_b(p_i) = -{\bf p}^T \log_b({\bf p})$$

Where $1^T{\bf p} = 1$ is the probability sums to 100% condition which all probabilities must obey together with positivity $p_i \geq 0, \forall i$ .

Now to the question how would it be possible to make this quantity linear in the sense that we can express it with linear algebra and solve for it using ordinary least squares as we would if it were a linear equation system or minimization?

$\endgroup$
1
$\begingroup$

$p \log p$ isn't nice around $p=0$ due to the behavior of $\log p$ -- to see some issues that could occur, for example, in estimating entropy from data, see arXiv:1407.0381 [cs.IT]. The paper outlines some polynomial approximation techniques for $-p \log p$ in section 4. If you knew all your elements of $p$ had to be far away from $0$, you could do something like a Taylor series about a probability vector with full support (i.e. no zero elements).

That being said, entropy is concave, so maximizing entropy over a convex subset of probability distributions isn't hard. This functionality is built into packages like CVX.

Minimizing a concave function isn't straightforward, but you do have some structural properties of entropy (e.g. looking more like a point mass helps reduce entropy). But you're maximizing entropy in a lot more cases than minimizing it.

$\endgroup$
  • $\begingroup$ Okay thanks for the input. The only use for minimizing entropy that I've found would be to try and get sparse dictionaries. Each 0 probability we can get ( which gives minimal addition of entropy ) reduces the need to store or represent that state or symbol completely when sampling. But since I haven't linearized it in any nice way I haven't seen if it works for me yet. $\endgroup$ – mathreadler May 20 '17 at 7:44
  • $\begingroup$ Linearizing it is not a good idea in that case, because you will precisely want $p_i \log p_i$ to go to zero for those coordinates, where $p \log p$ pretty non-linear. $\endgroup$ – Batman May 20 '17 at 11:59
  • $\begingroup$ I already know a couple of fruitful approaches, mostly polling for new ideas. $\endgroup$ – mathreadler May 20 '17 at 18:27
  • $\begingroup$ $(p\log p)\big|_0 =0$ $\endgroup$ – rych May 23 '17 at 12:44
  • 1
    $\begingroup$ @rych - sure. But having an accurate non-zero estimate of $p \log p$ around $0$ when $p$ is small is trickier. $\endgroup$ – Batman May 23 '17 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.