Suresh Venkatasubramanian University of Utah

Lecture Plan

Information geometry

Algorithms for information distances

Spatially-aware information distances

Review: The Rogues’ Club Bregman divergence For convex φ : Rd → R Dφ (p, q) = φ(p) − φ(q) − h∇φ(q), p − qi f-divergence For convex f : R → R, f (1) = 0, Df (p, q) =

qi

∑ pi f ( pi ) i

α-divergence For |α| < 1, 4 Dα (p, q) = [1 − 1 − α2

Z

p(1−α)/2 q(1+łpha)/2 ]

Review: The Rogues’ Club Bregman divergence For convex φ : Rd → R Dφ (p, q) = φ(p) − φ(q) − h∇φ(q), p − qi

α-divergence For |α| < 1, 4 Dα (p, q) = [1 − 1 − α2

Z

p(1−α)/2 q(1+łpha)/2 ]

Bregman Divergences

Properties: Asymmetry

Dφ (p, q) = φ(p) − φ(q) − h∇φ(q), p − qi In general,

D(p,q)

p

q

Dφ (p, q) 6= Dφ (q, p) However, let

D(q,p)

φ∗ (u) = suphu, pi − φ(p) p

q* D*(q*, p*)

then Dφ (p, q) = Dφ∗ (q∗ , p∗ ) where x∗ = ∇φ(x)

p*

Properties II: Generalized Cosine Rule Generalized Cosine Rule: Dφ (p, q) + Dφ (q, r) = Dφ (p, r) + h∇φ(r) − ∇φ(q), p − qi Compare with standard cosine rule:

kp − qk2 kq − rk2 kp − rk2 + = + hr − q, p − qi 2 2 2 In general, Dφ (p, q) behaves like square of a distance (“energy”, not “distance”) q Dφ (p, q) is not a metric in general. Dφ (p, q) is not a metric.

Bregman bisectors are halfplanes

p

r

D( r,q

)

Dφ (r, p) = Dφ (r, q)

D(

r,p

)=

hr, ∇φ(q) − ∇φ(p)i = f (p, q)

Most combinatorial geometry carries over (Voronoi, Delaunay, arrangements, duality)[BNN10]

q

Euclidean Approximations

Dφ (p, q) = φ(p) − φ(q) − h∇φ(q), p − qi

D(p,q)

q

p

Euclidean Approximations

Dφ (p, q) = φ(p) − φ(q) − h∇φ(q), p − qi

D(p,q)

q

p

Dφ (p, q) = s> ∇2 φ(r)s, s = p − q, r ∈ [p, q]

Euclidean Approximations

Dφ (p, q) = φ(p) − φ(q) − h∇φ(q), p − qi

= s> ∇2 φ(r)s, s = p − q, r ∈ [p, q] As q → p, this becomes the Mahalanobis distance, for positive definite A: q kp − qkA = (p − q) > A(p − q)

Euclidean Approximations

R

∗ λmax = max λmax (∇2 φ(x)) x∈R

∗ λmin = min λmin (∇2 φ(x))

µ=

x∈R ∗ λmax ∗ λmin

µ-similarity A distance measure is µ-similar if d(a, b) + d(b, c) ≥

1 d(a, c) µ

Lemma For a given convex function φ, there exists a bounded region R(µ) in which Dφ is µ-similar. Proof follows by exploiting the connection to the Mahalanobis distance, and looking at the variation in eigenvalues of ∇2 φ. Euclidean clustering algorithm ⇒ µ-similar Bregman clustering algorithm. [ABS10, AB10, ABS11, CM08, MR09]

Dimensionality Reduction

Dimensionality Reduction For Distributions[APV10, KPV10]

Problem Given n points on the simplex ∆d , find a mapping to ∆k , k d such that the “distance structure” of the points is preserved.

The Hellinger Distance

d2H (p, q) =

∑(

√

pi −

√

qi ) 2

i

Hellinger distance: Natural geometric interpretation Local approximation of Fisher information, and closely related to Jensen-Shannon and Bhattacharya distance.

Hellinger Is Chordal Distance on Sphere

√ √ √ (p1 , p2 , . . . pd ) → ( p1 , p2 , . . . , pd ) Hellinger distance on simplex ↔ Euclidean distance on sphere. Dimensionality reduction for simplex ↔ Dimensionality reduction on “sphere”<