2.4.8 Kullback-Leibler Divergence

1 Kullback-Leibler DivergenceTo measure the difference between two probability distributions over the samevariablex, a measure, called theKullback- leibler Divergence , or simply, theKLdivergence, has been popularly used in the data mining literature. The conceptwas originated in probability theory and information KL Divergence , which is closely related torelative entropy,informa-tion Divergence , andinformation for discrimination, is a non-symmetric mea-sure of the difference between two probability distributionsp(x) andq(x).Specifically, the Kullback-Leibler (KL) Divergence ofq(x) fromp(x), denotedDKL(p(x), q(x)), is a measure of the information lost whenq(x) is used to ap-proximatep(x).Letp(x) andq(x) are two probability distributions of a discrete randomvariablex. That is, bothp(x) andq(x) sum up to 1, andp(x)>0 andq(x)>0for (p(x), q(x)) is defined in Equation ( ).DKL(p(x)||q(x)) = x Xp(x) lnp(x)q(x)( )The KL Divergence measures the expected number of extra bits required tocode samples fromp(x) when using a code based onq(x), rather than using acode based onp(x).

2 Typicallyp(x) represents the true distribution of data,observations, or a precisely calculated theoretical distribution . The measureq(x) typically represents a theory, model, description, or approximation ofp(x).The continuous version of the KL Divergence isDKL(p(x)||q(x)) = p(x) lnp(x)q(x)dx( )Although the KL Divergence measures the distance between two distri-butions, it is not a distance measure. This is because that the KL divergenceis not a metric measure. It is not symmetric: the KL fromp(x) toq(x) isgenerally not the same as the KL fromq(x) top(x). Furthermore, it neednot satisfy triangular inequality. Nevertheless,DKL(P||Q) is a (P||Q) 0 andDKL(P||Q) = 0 if and only ifP= that attention should be paid when computing the KL Divergence . Weknowlimp 0plogp= 0. However, whenp = 0 butq= 0,DKL(p||q) is definedas . This means that if one eventeis possible ( ,p(e)>0), and the otherpredicts it is absolutely impossible ( ,q(e) = 0), then the two distributions areabsolutely different.

3 However, in practice, two distributionsPandQare derivedfrom observations and sample counting, that is, from frequency distributions. Itis unreasonable to predict in the derived probability distribution that an event iscompletely impossible since we must take into account the possibility of unseenevents. Asmoothingmethod can be used to derive the probability distributionfrom an observed frequency distribution , as illustrate in the following Computing the KL Divergence by there are two sample distributionsPandQas follows:P: (a: 3/5, b:21/5, c: 1/5) andQ: (a: 5/9, b: 3/9, d: 1/9). To compute the KL divergenceDKL(P||Q), we introduce a small constant , for example = 10 3, and definea smoothed version ofPandQ,P andQ , as sample set observed inP,SP={a, b, c}. Similarly,SQ={a, b, d}. Theunion set isSU={a, b, c, d}. By smoothing, the missing symbols can be addedto each distribution accordingly, with the small probability.

4 Thus, we haveP : (a: 3/5 /3, b: 1/5 /3, c: 1/5 /3, d: ) andQ : (a: 5/9 /3, b:3/9 /3, c: , d: 1/9 /3).DKL(P , Q ) can be computed easily.