|
|
(4 intermediate revisions by the same user not shown) |
Line 15: |
Line 15: |
| Just to repeat because it may be confusing, equation 2 just pertains to the uncertainty when only a ''single event'' happened. We can extend this to the total entropy <math> Y </math> when ''any'' of the outcomes in <math> X </math> happens. If we treat <math> H(Y|\cdot) </math> like a random variable that contains a range of <math> \{H(Y|x_1), H(Y|x_2), H(Y|x_3),...,H(Y|x_n) \} </math> and the probability distribution for each associated <math> H(Y|x_i) </math> is <math> \{P(x_1), P(x_2), P(x_3), ... P(x_n) \} </math> so that <math> H(Y|\cdot) </math> is a function of <math> X </math>. Then we define <math> H(Y|X) </math> as the conditional probability of <math> Y </math> given <math> X </math> as: | | Just to repeat because it may be confusing, equation 2 just pertains to the uncertainty when only a ''single event'' happened. We can extend this to the total entropy <math> Y </math> when ''any'' of the outcomes in <math> X </math> happens. If we treat <math> H(Y|\cdot) </math> like a random variable that contains a range of <math> \{H(Y|x_1), H(Y|x_2), H(Y|x_3),...,H(Y|x_n) \} </math> and the probability distribution for each associated <math> H(Y|x_i) </math> is <math> \{P(x_1), P(x_2), P(x_3), ... P(x_n) \} </math> so that <math> H(Y|\cdot) </math> is a function of <math> X </math>. Then we define <math> H(Y|X) </math> as the conditional probability of <math> Y </math> given <math> X </math> as: |
| | | |
− | {{NumBlk|::|<math> H(Y|X) = E(H(Y|\cdot)) = -\sum_{j=1}^m P(x_i) H(Y|x_i) </math>|{{EquationRef|3}}}} | + | {{NumBlk|::|<math> H(Y|X) = E(H(Y|\cdot)) = \sum_{i=1}^n P(x_i) H(Y|x_i) </math>|{{EquationRef|3}}}} |
| | | |
| Substituting equation 2 to equation 3 and knowing that <math> P(y_j|x_i)P(x_i) = P(x_i,y_j) </math>. We can re-write this as: | | Substituting equation 2 to equation 3 and knowing that <math> P(y_j|x_i)P(x_i) = P(x_i,y_j) </math>. We can re-write this as: |
Line 80: |
Line 80: |
| \begin{align} | | \begin{align} |
| H(Y|X) &= -\sum_{i=1}^n \sum_{j=1}^m P(x_i,y_j) \log_2 (P(y_j|x_i)) \\ | | H(Y|X) &= -\sum_{i=1}^n \sum_{j=1}^m P(x_i,y_j) \log_2 (P(y_j|x_i)) \\ |
− | &= -P(a,w) \log_2(P(a|w)) -P(a,x) \log_2(P(a|x)) -P(b,y) \log_2(P(b|y)) -P(b,z) \log_2(P(b|z)) \\ | + | &= -P(w,a) \log_2(P(w|a)) -P(x,a) \log_2(P(x|a)) -P(y,b) \log_2(P(y|b)) -P(z,b) \log_2(P(z|b)) \\ |
| &= -\frac{1}{3} \log_2 \left(\frac{2}{3}\right) -\frac{1}{6} \log_2 \left(\frac{1}{3}\right) -\frac{1}{4} \log_2 \left(\frac{1}{2}\right) -\frac{1}{4} \log_2 \left(\frac{1}{2}\right) \\ | | &= -\frac{1}{3} \log_2 \left(\frac{2}{3}\right) -\frac{1}{6} \log_2 \left(\frac{1}{3}\right) -\frac{1}{4} \log_2 \left(\frac{1}{2}\right) -\frac{1}{4} \log_2 \left(\frac{1}{2}\right) \\ |
| &= 0.959 \ \textrm{bits} | | &= 0.959 \ \textrm{bits} |
Line 189: |
Line 189: |
| == Graphical Summary == | | == Graphical Summary == |
| | | |
− | Figure 2 shows how we can visualize conditional entropy and mutual information. The red and blue pertain to the individual entropies <math> H(X) </math> respectively. Figure 3 shows what joint entropy looks like. | + | Figure 2 shows how we can visualize conditional entropy and mutual information. The red and blue pertain to the individual entropies <math> H(X) </math> and <math> H(Y) </math>, respectively. Figure 3 shows what joint entropy looks like. |
| | | |
| [[File: Venn diagram.svg|400px|thumb|center|Figure 2: Venn diagram visualizing conditional entropy and mutual information.]] | | [[File: Venn diagram.svg|400px|thumb|center|Figure 2: Venn diagram visualizing conditional entropy and mutual information.]] |
Line 210: |
Line 210: |
| * <math> H(X,Y,Z) = H(X) + H(Y) + H(Z) - I(X,Y) - I(Y,Z) - I(X,Z) + I(X,Y,Z) </math> while noting that <math> I(X,Y) = H(X,Y) - H(X|Y) - H(Y|X) </math>, <math> I(X,Z) = H(X,Z) - H(X|Z) - H(Z|X) </math>, and <math> I(Y,Z) = H(Y,Z) - H(Z|Y) - H(Y|Z) </math>. | | * <math> H(X,Y,Z) = H(X) + H(Y) + H(Z) - I(X,Y) - I(Y,Z) - I(X,Z) + I(X,Y,Z) </math> while noting that <math> I(X,Y) = H(X,Y) - H(X|Y) - H(Y|X) </math>, <math> I(X,Z) = H(X,Z) - H(X|Z) - H(Z|X) </math>, and <math> I(Y,Z) = H(Y,Z) - H(Z|Y) - H(Y|Z) </math>. |
| * <math> I(X,Y,Z) = H(X,Y,Z) - H(X) - H(Y) - H(Z) + I(X,Y) + I(Y,Z) + I(X,Z) </math> as a consequence of the previous equation. | | * <math> I(X,Y,Z) = H(X,Y,Z) - H(X) - H(Y) - H(Z) + I(X,Y) + I(Y,Z) + I(X,Z) </math> as a consequence of the previous equation. |
− | * <math> I(X,Y|Z) = H(X,Y,Z) - H(Z) - H(X|Z) - H(Y|Z) = H(X,Y,Z) - H(Z) - H(X|Y,Z) - H(Y|X,Z) </math> essentially, it's like taking away all <math> H(Z) </math> components. All similar combinations (e.g., <math> I(X,Z|Y) </math> and <math> I(Y,Z|X) </math> ) should be the same too. | + | * <math> I(X,Y|Z) = H(X,Y,Z) - H(Z) - H(X|Y,Z) - H(Y|X,Z) </math>. All similar combinations (e.g., <math> I(X,Z|Y) </math> and <math> I(Y,Z|X) </math> ) should be the same too. |
Joint Entropies
In this module, we'll discuss several extensions of entropy. Let's begin with joint entropy. Suppose we have a random variable
with elements
and random variable
with elements
. We define the joint entropy of
and
as:
-
![{\displaystyle H(X,Y)=-\sum _{i=1}^{n}\sum _{j=1}^{m}P(x_{i},y_{j})\log _{2}\left(P(x_{i},y_{j})\right)}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/6a0151ef0daf9a72555fc3f9edcb78b5c105c2e5)
|
|
(1)
|
Take note that
. This is trivial. From our previous discussion about the decision trees of a game, we used joint entropies to calculate the overall entropy.
Conditional Entropies
There are two steps to understand conditional entropies. The first is the uncertainty of a random variable caused by a single outcome only. Suppose we have the same random variables
and
defined earlier in joint entropies. Let's denote
as the conditional probability of
when event
happened. We define the entropy
as the entropy of the random variable
given a
happened. In other words, this is the average information of all the outcomes of
when event
happens. Take note that we're only interested in the entropy of
when only the outcome
occurred. Mathematically this is:
-
![{\displaystyle H(Y|x_{i})=-\sum _{j=1}^{m}P(y_{j}|x_{i})\log _{2}\left(P(y_{j}|x_{i})\right)}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/b6a75a395f416f21ed20f68029ad3f13777a9378)
|
|
(2)
|
Just to repeat because it may be confusing, equation 2 just pertains to the uncertainty when only a single event happened. We can extend this to the total entropy
when any of the outcomes in
happens. If we treat
like a random variable that contains a range of
and the probability distribution for each associated
is
so that
is a function of
. Then we define
as the conditional probability of
given
as:
-
![{\displaystyle H(Y|X)=E(H(Y|\cdot ))=\sum _{i=1}^{n}P(x_{i})H(Y|x_{i})}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/ae1bddb01048c5534c2b8a737b0fbcb6db16e2a9)
|
|
(3)
|
Substituting equation 2 to equation 3 and knowing that
. We can re-write this as:
-
![{\displaystyle H(Y|X)=-\sum _{i=1}^{n}\sum _{j=1}^{m}P(x_{i},y_{j})\log _{2}(P(y_{j}|x_{i}))}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/f7d0cbddaa00a13f1b38844f94fd64b17c8eae5e)
|
|
(3)
|
Note that it is trivial to prove that
if
and
are independent. We'll leave it up to you to prove this. A few hints include:
and
if
and
are independent.
Binary Tree Example
Figure 1: Binary tree example.
Let's apply the first two concepts in a simple binary tree example. Suppose we let
be a random variable with outcomes
and probabilities
. Let
be the random variable with outcomes
. We are also given the probabilities
,
,
, and
. Figure 1 shows the binary tree. Calculate:
(a)
(b)
(c)
(d)
Solution
(a) Use equation 2 to solve
(b) Same as in (a), use equation 2 to solve
(c) Can be solved in two ways. First is to use equation 3.
Or, we can solve it using the alternative version of equation 3. But we also need to know the joint probabilities:
![{\displaystyle P(a,w)={\frac {1}{3}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/0399136e47052574f6f31eddf4af2297ae58a291)
![{\displaystyle P(a,x)={\frac {1}{6}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/efb97b371da670d54a0ab80ee028ddf18be41ada)
![{\displaystyle P(b,y)={\frac {1}{4}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/f898b4cff3b6086b9419cf7043ce06816d4f5881)
![{\displaystyle P(b,z)={\frac {1}{4}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/1f7bea47c3380ad162228e58d593b215c48ddb54)
(d) We already listed the joint probabilities in (c). We simply use equation 1 for this:
Important Note!
This example actually shows us an important observation:
-
![{\displaystyle H(X,Y)=H(X)+H(Y|X)}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/a8725690f0c8920b9a29c37b64fb1f2479c5d0b7)
|
|
(4)
|
We can easily observe that this holds true for the binary tree example. This has an important interpretation: The combined uncertainty in
and
(i.e.,
) is the sum of that uncertainty which is totally due to
(i.e.,
), and that which is still due to
once
has been accounted for (i.e.,
).
Since
it also follows that:
-
![{\displaystyle H(Y,X)=H(Y)+H(X|Y)}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/3eadfa2cdd5dab5331504236c299fdd8df4a399f)
|
|
(5)
|
If
and
are independent then:
-
![{\displaystyle H(X,Y)=H(X)+H(Y)}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/41b9cc4a524a355214eafb8883ccde26a88ca9ce)
|
|
(6)
|
An alternative interpretation to
is the information content of
which is NOT contained in
.
Mutual Information
With the final discussion on the properties of joint and conditional entropies, we also define mutual information as the information content of
contained within
written as:
-
![{\displaystyle I(X,Y)=H(Y)-H(Y|X)}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/0b2bd7d56ad5fb2f736c028a1ae0a24c0619e79f)
|
|
(7)
|
Or:
-
![{\displaystyle I(X,Y)=H(X)-H(X|Y)}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/24eb7982f3513e60afcf8f8e1052bd88ee204682)
|
|
(7)
|
If we plug in the definitions of entropy and conditional entropy, mutual information in expanded form is:
-
![{\displaystyle I(X,Y)=\sum _{i=1}^{n}\sum _{j=1}^{m}P(x_{i},y_{j})\log _{2}\left({\frac {P(x_{i},y_{j})}{P(x_{i})P(y_{j})}}\right)}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/610af2564e3a341726205ce6e54b97d8153f4591)
|
|
(8)
|
It also follows that:
. This is trivial from equation 7.
- If
and
are independent, then
. This is also trivial from equation 8.
As a short example, we can use the binary tree problem again. Let's compute
. We simply need to use equation 7:
. We already know
bits.
is computed by first knowing
. Recall that:
But then, for each outcome in
has the same probability of the joint entropy. For example, event
only occurs if event
occurred first. Event
occurs only if event
occurred first. So it means that:
![{\displaystyle P(w)=P(w|a)P(a)=P(w,a)={\frac {1}{3}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/f19976dc19c8db235dd03205c78678bbc2060624)
![{\displaystyle P(x)=P(x|a)P(a)=P(x,a)={\frac {1}{6}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/a787d8fcb9514a5239ab4d7fb5c6f4ac7180bc8a)
![{\displaystyle P(y)=P(y|b)P(b)=P(y,b)={\frac {1}{4}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/b66b083545a055d3b37eafd49d1207502f1efc7f)
![{\displaystyle P(z)=P(z|b)P(b)=P(z,b)={\frac {1}{4}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/94ce0480409b6ea7480a195ecae8b4f81224f713)
Therefore,
bits. Therefore, the information
bits.
Chain Rule for Conditional Entropy
What happens when we deal with more than two random variables? To facilitate the discussion, let us recall the chain rule for joint distributions.
Let
be a sequence of discrete random variables. Then, their joint distribution can be factored as follows
,
Chain rule for entropy
The chain rule for (joint) entropy is very similar to the above expansion, but we use additions instead of multiplications.
-
![{\displaystyle H(X_{1},X_{2},...,X_{n})=H(X_{1})+H(X_{2}|X_{1})+H(X_{3}|X_{1},X_{2})+...+H(X_{n}|X_{1},X_{2},...,X_{n-1})}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/678dea9ccf23de45409838482617b418a6e66a68)
|
|
(9)
|
Although we do not supply a complete proof here, this fact should not be too surprising since entropy operates on logarithms of probabilities and logarithms of product terms expand to sums of logarithms.
Proof of chain rule for ![{\displaystyle n=3}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/1c5a5a42ced00df920fad4ab2d4acdb960a4105b)
Let us see that the statement is true for
. Let
be three discrete random variables. The idea with the proof is that we operate on two random variables at a time, since prior to the chain rule we only know that
. We can write
, where we bundle
and
into one random variable
.
The proof now proceeds as follows:
One interpretation of the chain rule shown is that to obtain the total information (joint entropy) of
as a whole, we can
- obtain information about
first without any prior knowledge:
, then
- obtain information about
with knowledge of
:
, then
- obtain information about
with knowledge of
and
:
.
For
, we can proceed by induction. Below is the sketch of the proof:
- (Base step) For a fixed
, assume that any collection of
random variables satisfies the chain rule.
- (Induction step) When
, write the joint entropy of
random variables as follows:
, where the first
are bundled together into one random variable.
- Use the two-variable chain rule
and the base step to show that
.
A few things to note:
- The order of "obtaining information" is irrelevant in calculating the joint entropy of multiple rvs. Write the chain rule if we proceed by obtaining information in the following order:
.
- The chain we have now works for any collection of random variables. Can you figure out how to simplify the chain rule for Markov chains? (The answer will be discussed in Module 3.)
Graphical Summary
Figure 2 shows how we can visualize conditional entropy and mutual information. The red and blue pertain to the individual entropies
and
, respectively. Figure 3 shows what joint entropy looks like.
Figure 2: Venn diagram visualizing conditional entropy and mutual information.
Figure 3: Venn diagram visualizing joint entropy.
From the diagrams you should be able to recall the entropy relationships on the fly. We can summarize (and derive new relationships) as:
![{\displaystyle I(X,Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/57248f827beb1691d9292b127b986fe2be9e7ba0)
![{\displaystyle H(X,Y)=H(X|Y)+H(Y|X)+I(X,Y)=H(X)+H(Y)-I(X,Y)}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/764321d0fb0b06ab47d57a42b62545a1b26a9b7d)
From the diagrams, it's easy to re-translate
![{\displaystyle H(Y|X)}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/a4290968969c5477748714a23d5531b65da246b8)
(or
![{\displaystyle H(X|Y)}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/cd2aef35bbe076060f08acfd4a7d314f909ff2c7)
) as
the uncertainty of
without the
happening
Of course we, can extend this concept to three variables. For example, figure 4 shows a Venn diagram for three sets. The entire blue circle is
, the entire red is
, and the entire green is
. The labels are there to guide you.
Figure 4: Entropy Venn diagram from three sets.
We can also derive useful relationships based on figure 4. Some of these include:
which is consistent with equation 9. Look at the diagram carefully.
while noting that
,
, and
.
as a consequence of the previous equation.
. All similar combinations (e.g.,
and
) should be the same too.