KL Divergence and Entropy

I often see Kullback–Leibler (KL) divergence and I need to understand how the entropy and information are defined to explain the KL divergence. KL divergence is described as the following equation. 

```math
\begin{equation}-\sum_{x\in\ \chi}P(x)\log_{}{\cfrac{P(x)}{Q(x)}}\end{equation}
```

First we need to understand the Shanon's entropy. 

```math
\begin{equation}-\sum_{x\in\ \chi}P(x)\log{P(x)}\end{equation}
```

Shannon's self information is often explained via the equation

```math
\begin{equation}-\log{P(x)}\end{equation}
```
However, it is easier to understand with a sigma sign as follows: 

```math
\begin{equation}-\sum_{x\in\ \chi}\log{P(x)}\end{equation}
```
We can rewrite the equation as follows:

```math
\begin{equation}\sum_{x\in\ \chi}\log{\cfrac{1}{P(x)}}\end{equation}
```
Let's imagine you have a box that gives you colored balls. If the color is only black, the sum above will be zero because log1=0. What about you have two colors, black and white with the same probability? The log0.5 is around -0.30, so the amount will be 0.6. If you have one hundred kinds of colors, the amount will be 200. I could not understand the meaning of the information quantity until I came up with this explanation. In short, if you have various types of results (the each P is small in other words), the information is large. Then what is entropy? It is an expectancy of the self-information quantity described as follows:

```math
\begin{equation}-\sum_{x\in\ \chi}P(x)\log{P(x)}\end{equation}
```
Here, the

```math
\begin{equation}-log{P(x)}\end{equation}
```
 is the self-information and the corresponding probability is multiplied to calculate the expected amount of information. Therefore, Shannon's entropy is the expected amount of self-information. Let's calculate to see how the entropy changes with the Box case above.
<img width="379" alt="Screen Shot 2019-06-18 at 12.30.40 PM.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/435846/4bfe39bd-c2ee-eeac-24da-e178aa69e633.png">

As you see, as the number of colors increases, the entropy increases too. All right, now we can look into the KL divergence. 

```math
\begin{equation}-\sum_{x\in\ \chi}P(x)\log_{}{\cfrac{P(x)}{Q(x)}}\end{equation} 
```
This can be written in a different way like

```math
\begin{equation}- \left(\sum_{x\in\ \chi}P(x)\log_{}{P(x)}-\sum_{x\in\ \chi}P(x)\log_{}{Q(x)}\right)\end{equation}
```
 or 

```math
\begin{equation}-\sum_{x\in\ \chi}P(x)\log_{}{P(x)}+ \sum_{x\in\ \chi}P(x)\log_{}{Q(x)} \ \ \ Eq. 2\end{equation}
```
 P is the actual probability distribution and the Q is the estimated distribution. The second term 

```math
\begin{equation}-\sum_{x\in\ \chi}P(x)\log_{}{Q(x)}\end{equation}
```
 is called a cross entropy . 

Obviously, the Eq. 1 will be zero when P = Q. When we look at the Eq. 2, the first term will always be negative because -logP is positive and the P is positive. The second term will be negative from the same reason. The first term doesn't change because it is a true probability distribution, and only the second term will change. 

Ideally, the value of the Eq. 2 will become zero. OK, it is said that the KL divergence is non-negative. Why?? Some article tell that entropy is at its minimum. Why? Check it in the next article. It is called <b>Gibbs's inequality</b>.