1
$\begingroup$

Say we have a simple case of $p(x,y)$ is a 3x3 matrix: $$\begin{bmatrix} 1/6 & 0 & 0 \\ 1/6 & 3/6 & 0 \\ 0 & 0 & 1/6 \end{bmatrix}$$

And $q(x,y)=q(x)q(y)$. If I'm trying to solve for the form of $q_x$ and $q_y$ that minimizes $D_{KL}(q||p)$, what's the best approach to solving this problem? I know that if the two distributions were continuous, I could use gradient descent or something similar, but without trying to brute force the solution here, I can't see the proper way to solve.

Lastly, I've been concerned about taking the $D_{KL}(q||p)$ when the two distributions do not have the same support (because of the 0's in the matrix above), but I read somewhere on SE that we can treat those $\log(0)$ terms as 0 although I remain unconvinced.

$\endgroup$
1
$\begingroup$

Your problem is about handling impossible events in KL-divergence. Your $x$ and $y$ notation is not useful here (though it might be relevant for your specific problem). We can flatten everything and call X = (x,y).

Let's start from the definition of KL divergence : $$D_{KL}(q\|p) = \sum _{X} q(X) \log\left(\frac{q(X)}{p(X)}\right)$$

It looks rather undefined as soon $p(X)=0$ or $q(X)=0$... Let's look at the calculus :

Case 1: $q(X) = 0$ and $p(X)\neq 0$ : In that case , $\lim_{x\rightarrow 0}xlog(x) =0$. Hence, we will count 0 in the sum.

Case 2: $q(X) \neq 0$ and $p(X) = 0$ : In that case , $\lim_{x\rightarrow 0}log(1/x) =+ \infty$. Hence, we will count $+ \infty$ in the sum.

Case 3: $q(X) =0$ and $p(X) = 0$ : Then, it is really undefined...

Now, let's look at some higher level interpretation. $D_{KL}(q\|p)$ quantifies how credible distribution $p$ is when we sample according to $q$.

Case 1: $q(X) = 0$ and $p(X)\neq 0$ : Since we sample according to $q$, we will never sample event $X$. Hence, it does not weight in $D_{KL}(q\|p)$.

Case 2: $q(X) \neq 0$ and $p(X) = 0$ : Since we sample according to $q$, a single sample of event $X$ tells us with absolute certainty that we are not sampling $p$. Hence, $D_{KL}(q\|p)$ is infinite.

Case 3: $q(X) =0$ and $p(X) = 0$ : $X$ is an event which does not happen in $p$ and $q$. So why would you put it in the sum in the first place?

For your specific case, you have a lot of $0$ in $p$. Hence, your KL-divergence will be infinite except if $q$ have the same zeros. Since you further assume that $q(x,y) = q_x(x)q_y(y)$, we have the following constraint :

$$q_x(1)q_y(2)=0$$ $$q_x(1)q_y(3)=0$$ $$q_x(2)q_y(3)=0$$ $$q_x(3)q_y(1)=0$$ $$q_x(3)q_y(2)=0$$

For instance : $q_x = \left[1/2, 1/2, 0 \right]$ and $q_y = \left[1, 0, 0 \right]$.

$\endgroup$

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.