Poster on distances/divergences

Informations

• Publié par: mtoledan
• Publié le: 03 décembre 2012
• Nombre de lectures: 39
• Poids de l'ouvrage: 1 Mo

Extrait

Taxonomy of principal distances
Hamming distance
Statistical geometryEuclidean geometry (jfi : p = qgj)i i
1Physics entropy JK Additive entropyREuclidean distance Manhattan distancepP P k p logp cross-entropy2d (p; q) = (p q ) (Pythagoras’ d (p; q) = jp qj2 i i 1 i i conditional entropyi i (Boltzmann-Gibbs 1878)
mutual informationtheorem circa 500 BC) (city block-taxi cab)
(chain rules)
Information entropyMinkowski distance (L -norm)k RpP
k k H(p) = p logpd (p; q) = jp qj Mahalanobis metric (1936)k i ii p
T 1 (C. Shannon 1948)(H. Minkowski 1864-1909) d = (p q) (p q)
Space-time geometry
I-projection Life
H(p) = KL(pjju) negative entropy
Kullback-Leibler divergenceR
p PKL(pjjq) = p log = E [log ]pq Q
(relative entropy, 1951)Quadratic distancep
Td = (p q) Q(p q)Q
Je rey divergenceNon-Euclidean geometries
(Jensen-Shannon)
Fisher information (local entropy)
2@ Bhattacharya distance (1967)I() = E[ lnp(Xj) ] q
@ R p p
2(R. A. Fisher 1890-1962) d(p;q) = ln ( p q)
KolmogorovR
K(pjjq) = jq pj
= 1 (Kolmogorov-Smirnoff maxjp qj)
Riemannian metric tensorq
R dxdxi j exponential familiesg dsij Matsushita distance (1956)ds ds qR 1 1(B. Riemann 1826-1866,)
M (p;q) = jq p j
Cherno divergence (1952)Itakura-Saito divergence HellingerRP q 1 p p Ri i C (pjjq) = ln p q p pIS(pjq) = ( log 1) 2i q qi i H(pjjq) = ( p q)
(Burg entropy) p p
= 2(1 fg(1 )
2 testRenyi divergence (1961) R 2R 2 (q p)1 = 0 (pjjq) =H = log f p(1 ) R
1 1 (K. Pearson, 1857-1936 )R (pjq) = ln p q ( 1)
(additive entropy)
T
Csiszar’ f-divergenceR
q Neyman
Kullback-Leibler D (pjjq) = pf( )f p
(Ali& Silvey 1966, Csisz ar 1967)
Bregman divergences (1967) Dual div.-conjugate (f (y) =yf(1=y))
B (pjjq) =F (p) F (q) < p q;rF (q)>F Information geometriesD (pjjq) =D (qjjp)f f
Amari -divergence (1985)Bregman-Csiszar divergence (1991) xlogx = 1x logx 1 = 0 rlogx = 1xlogx x+1 = 1F (x) = f (x) = 1+1 ( x + x +1) 0<< 1 4 (1 x 2 ) 1<< 1 (1 ) 2 r1 GeneralizedDual div. (Legendre) D (rF (p)jjrF (q)) =D (qjjp)F F
f-means
Generalized Pythagoras’ theorem
duality... Quantum geometry(Generalized projection)
Quantum entropy
S() = kTr( log)
(Von Neumann 1927)Permissible Bregman divergences Burbea-Rao
(Nock & Nielsen, 2007) (incl. Jensen-Shannon)
f(p)+f(q) p+q
J (p;q) = fF 2 2
Non-additive entropy
Log Det divergence
Tsallis entropy (1998) 1 1D(PjjQ) =< P; Q > log det PQ dimP
(Non-additive entropy)P
1 T (p) = ( p 1) i1 i Von Neumann divergenceR
1 pT (pjjq) = (1 ) D(PjjQ) = Tr(P(log P log Q) P + Q) 11 q
Earth mover distance
(EMD 1998)
Kolmogorov complexityAlgorithmic geometry?
c Frank Nielsen, 2007. Version 0.2Distance between two algorithms ?
Last updated, May 2008
6