Data Mining Basic Probability & Information Theory Terms & Concepts 1.
Consequences of the Cox Axioms Not traditional axioms, but desirable properties of any algorithmic system of rational inference. Degree of belief that proposition x is true can be denoted B(x), and degree of belief that proposition x is false by B( x ) The degree of belief in a conditional proposition, x is true, assuming y to be true can be written B(x|y). (1) Degrees of belief can be ordered mapped onto real numbers. (2) A function F exists that relates any value of B(x) to B( x ). That is, B(x) = F[B( x )]. (3) A function G exists that relates the degree of belief in a conjunction of propositions (x and y are both true) to the degree of belief in a conditional proposition x|y and degree of belief in the proposition y. That is, B(x,y) = G[B(x|y),B(y)]. From the above three axioms can be derived all the probability theory needed for machine learning, Bayesian inference, and data mining. In particular, it can be proven that the only mapping onto the real numbers and functions B and G that meet the above requirements has the following attributes: (i) P(False with certainty) = 0 (ii) P(True with certainty) = 1 (iii) 0 <= P <= 1 (iv) P(x) = 1-P( x ) (v) P(x,y) = p(x|y)P(y). (vi) The sum of mutually exclusive, exhaustive propositions P(x) over a set of n possibilities sums to 1.
n
p(x) = 1.
1
2. Probability Definitions
Joint Probability p(X,Y) The probability that both X and Y are true. Conditional Probability p(X|Y) The probability that X is true, given that Y is true. Marginal Probability p(X) The probability that X is true, independent of the value of Y. Product Distribution p(X)p(Y) The product of two marginal distributions. Definition of Independence: Two distributions are independent if and only if their joint distribution is equal to their product distribution p(X,Y) =p(X)p(Y). Example for Illustration of Definitions Assume the following Joint Distribution:
p(X,Y ) y1
X
y2 p(x1, y2 ) = 0.2 p(x2, y2 ) p(x1, y2 ) = 0.4
x1 x2
p(x1, y1 ) = 0.1 p(x2, y1 ) = 0.3
The marginal distribution of X is p(x1 ) = p(x1, y1 ) + p(x1, y2 ) = 0.3 p(x2 ) = p(x2, y1 ) + p(x2, y2 ) = 0.7 The marginal distribution of Y is
p(y1 ) = p(x1, y1 ) + p(x2, y1 ) = 0.4 p(y2 ) = p(x1, y2 ) + p(x2, y2 ) = 0.6
The product distribution P(X)P(Y) is:
p(X,Y ) y1
y2
x1
X
(.3)(.4)=0.12 (.7)(.4)=0.28
(.3)(.6) = 0.18 (.7)(.6)=0.42
x2
What are the conditional probabilities P(X|Y)?
p(x1 y1 ) ___________________________________________ p(x2 y1 ) ___________________________________________ p(x1 y 2 ) ___________________________________________ p(x2 y 2 ) ___________________________________________
What are the comparable conditional probabilities P(Y|X)?
3. Probability Theorems Sum Rule The marginal probability p(X) is equal to the sum across each value for Y of the joint probabilities p(X|Y)p(Y). Product Rule The joint probability p(X,Y) is equal to the product of the conditional probability p(X|Y) and the marginal probability p(Y). In other words, P(A,B) = P(A|B)P(B). Bayes Theorem Given that P(A,B) = P(B,A), by application of the Product Rule above, P(A|B)P(B)=P(B|A)P(A). Dividing both sides of the above equation by P(B) gives: P(A|B) =
P(B | A)P(A) . P(B)
4. Information Theory Definitions Use of log = log2 is assumed unless stated otherwise. Entropy H(X) = - p(x)log( p(x))
x
Joint Entropy H(X,Y) = - p(x, y)log(p(x, y))
xX yY
Conditional Entropy H(X|Y) =
= p(x)(- (y | x)(log(y | x))
xX yY
xX
p(x)H(Y | X = x)
Relative Entropy The Relative Entropy, or Kullback-Leibler (K-L) Divergence between two distributions P(X) and Q(X), written D(P||Q) =
p(x)log Q(x) .
x
P(x)
Note that unless Q(x) >0 for all x where P(x) is >0, D(P||Q) = . Note further that D(P||Q) generally is not equal to D(Q||P). 5. Relationship Between Relative Entropy and Mutual Information It can be demonstrated that the Mutual Information I(X;Y) between two distributions is equal to the K-L Distance between the joint distribution and product distribution of X and Y. For example, for the Joint Distribution given in Section 2 above, I(X;Y) .1 .2 .3 .4 = (.1)(log ) + (.2)(log )+ (.3)(log ) + (.4)(log ) .12 .18 .28 .42 = 0.00580 bits 4
6. Basic Equalities of Information Theory Mutual Information, written I(X;Y) = H(X) H(X|Y) = H(Y) H(Y|X) = H(X) + H(Y) H(X,Y) = D(p(x,y)||p(x)p(y))
Illustration from MacKay, Figure 9.1, p. 149.
H (X , Y ) H (X ) H (Y ) H (X | Y ) I (X ; Y ) H (Y |X )