Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $E$ be a closed and convex set of distributions on a finite set $A$. Let $P',Q'\notin E$ and let $P^{\star},Q^{\star}$ be their respective estimates in $E$ with respect to the KL-divergence, i.e., $D(P'\|P^{\star})=\min_{P\in E}D(P'\|P)$ and similarly for $Q^{\star}$. I am wondering whether $D(P'\|Q')\ge D(P^{\star}\|Q^{\star})$.

share|improve this question
    
Sorry, I'm not familiar with your notation (but I am not a probabilist). Could you explain in more detail? –  Zen Harper Aug 1 '10 at 1:02
    
I've explained everything except $D(P\|Q)=\sum_{a\in A}P(a)\log \frac{P(a)}{Q(a)}$. I hope you know what a distribution is! A (probability)distribution on a (finite)set $A$ is a fuction $P:A\to [0,1]$ such that $\sum_{a\in A}P(a)=1$. –  Ashok Aug 1 '10 at 5:27
3  
Ashok, I am fairly sure that what Zen was asking for was the definition of Kullback-Leibler divergence (en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence) In future you should probably add such definitions to your question (you also assume everyone will know that by "distribution" you mean "probability distribution", rather than in the sense of Laurent Schwarz). –  Yemon Choi Aug 1 '10 at 7:38
1  
Interesting question...perhaps you can find the answer in Csiszar's "Information Projections Revisited" "Notes on Information Geometry and Statistics" and let us know :) I have copies of those two documents I can email –  Yaroslav Bulatov Aug 15 '10 at 3:27
    
I'll second Yemon: with both "pr" and "fa" tags, it was not obvious straight away what "distribution" meant in the context. –  Thierry Zell Aug 15 '10 at 4:30

1 Answer 1

up vote 2 down vote accepted

The inequality $D(P'|Q') \ge D(P^\star| Q^\star)$ does not need to hold.

Here is an example.

Let $A$ be the set $\{1,2,3,...,n\}$. Let $E$ be the set of measures $P$ on $A$ such that $P(\{1\}) = 0$. Projecting a measure $P$ on $E$ using $D$ is equivalent to conditioning $P$ on $ A- \{1\}$. Choose $P'$ and $Q'$ such that they both put equal and nonzero mass on $\{1\}$. By direct computation one sees: $D(P^\star| Q^\star) = \frac{1}{1-P'(\{1\})} D(P'|Q') > D(P' | Q')$.

The details of the above computation are as follows.

For ease of notation set $n=3$. Let $E$ be the set of measures $P$ with $P(\{1\}) =\epsilon$; to obtain the example above, one sets $\epsilon = 0$. Let us parametrize the measures on $\{1,2,3\}$ as follows: $P(\{1\}) = p_1$, $P(\{2\}) =p_2$ and $P(\{3\}) = 1-p_1 -p_2$. Our problem is: $$ \inf_{ Q \in E}\left[ p_1 \log \frac{p_1}{q_1} + p_2 \log \frac{p_2}{q_2} + (1-p_1 -p_2) \log\frac{ 1- p_1 - p_2}{ 1- q_1 - q_2 } \right]. $$ Let $F$ denote the expression after the $\inf$. $F$ is strictly convex in $Q$ and therefore will have a unique optimizer. In the above coordinates, the normal to $E$ is the vector $(1,0)$. Then $$ \frac{\partial F} {\partial q_1} = -\frac{p_1}{q_1} + \frac{1-p_1-p_2}{1-q_1-q_2} = \lambda $$ and $$ \frac{\partial F} {\partial q_2} = -\frac{p_2}{q_2} + \frac{1-p_1-p_2}{1-q_1-q_2} = 0. $$ We have the constraint that $Q\in E$, i.e., $q_1 =\epsilon$. From the last two equalities one infers: $$ q_2 = \frac{(1-\epsilon) p_2}{ 1-p_1}. $$

Going back to the coordinates $(p_1,p_2,p_3)$ to denote a measure on $\{1,2,3\}$, projecting a measure on $E$ using $D$ corresponds to the following map: $$ (p_1,p_2,p_3) \rightarrow \left(\epsilon, (1-\epsilon)\frac{p_2}{p_2+p_3}, (1-\epsilon)\frac{p_3}{p_2 + p_3}\right). $$ For $\epsilon =0$, this is the same as conditioning $P$ on $\{2,3\}$.

One obtains the expression for the relative entropy given above by directly computing it using this formula for the projections.

share|improve this answer
    
although the OP probably also wants to know if it's possible that D(P*| Q*) is less than D(P'| Q'). I wonder if all projections onto convex sets can be expressed as some kind of conditioning, after which one could invoke results like the data processing inequality to conclude that it can't happen. –  Suresh Venkat Aug 16 '10 at 8:22
    
Hi, one can slightly modify the above case to generate an example in which projection decreases relative entropy. The main idea appears to be this: conditioning can increase or decrease entropy; depends on what one conditions on. –  has2 Aug 17 '10 at 20:49
    
has2, in your example the projection is not unique; in fact, every member in $E$ is a projection. I hope you may be aware of the fact that projection is unique if Support of $P'$= Support of $E$; otherwise need not be. So, in such a case how did you get $D(P^\star| Q^\star) = \frac{1}{1-P'(\{1\})} D(P'|Q') > D(P' | Q')$? –  Ashok Aug 18 '10 at 5:52
    
Relative entropy (KL-divergence) is strictly convex in both of its variables. Therefore, it will always have a unique minimizer over any convex set. I tried to provide the details of the calculations above; they seem to be correct. –  has2 Aug 18 '10 at 8:42
1  
There is a limiting process involved in the case that reduces to conditioning. To get an example without infinite entropy, choose $1>\epsilon>0$ in the answer above. Then $D(P^\star|Q^\star)=\frac{1−\epsilon}{1−p'_1}D(P'|Q')$ and if one chooses $1>p'_1=q'_1>\epsilon$ and $(p'_2,p'_3)\neq(q'_2,q'_3)$, one gets $D(P^\star|Q^\star)> D(P'|Q')$ –  has2 Aug 19 '10 at 10:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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