An Extended Cencov-Campbell Characterization of Conditional Information Geometry

We formulate and prove an axiomatic characterization of conditional information geometry, for both the normalized and the nonnormalized cases. This characterization extends the axiomatic derivation of the Fisher geometry by Cencov and Campbell to the cone of positive conditional models, and as a special case to the manifold of conditional distributions. Due to the close connection between the conditional I-divergence and the product Fisher information metric the characterization provides a new axiomatic interpretation of the primal problems underlying logistic regression and AdaBoost.


Introduction
The theory of information geometry presents a geometric interpretation of statistical properties and techniques. Among many examples of such properties and techniques are efficiency of estimators, robustness, maximum likelihood estimation for exponential models and hypothesis testing. The monograph of Amari and Nagaoka (2000) contains an overview of relevant research in this topic during the past fifty years.
A fundamental assumption in the information geometric framework, that manifests itself in many statistical and machine learning applications, is the choice of the Fisher information as the metric that underlies the geometry of probability distributions. The choice of the Fisher information metric may be motivated in several ways, the strongest of which isČencov's characterization theorem (Lemma 11.3 in (Čencov, 1982)). In his theorem,Čencov proves that the Fisher information metric is the only metric that is invariant under a family of probabilistically meaningful mappings termed congruent embeddings by a markov morphism. Later on, Campbell (1986) stripped the proof from its category theory language and extendedČencov's result to include non-normalized models.
While the geometric approach to statistical inference has attracted considerable attention, little research was conducted on the geometric approach to conditional inference. The characterization theorems of Cencov and Campbell no longer apply in this setting and the different ways of choosing metrics on the manifold of conditional distributions, in contrast to the non-conditional case, are not supported by theoretical considerations.
In this paper we extend the results ofČencov and Campbell to provide an axiomatic characterization of conditional information geometry. We derive the characterization theorem in the setting of non-normalized conditional models from which the geometry for normalized models is obtained as a special case. In addition, we demonstrate a close connection between the characterized geometry and the conditional I divergence which leads to a new axiomatic interpretation of the geometry underlying the primal problems of logistic regression and AdaBoost. This interpretation builds on the connection between AdaBoost and constrained minimization of I-divergence demonstrated by Lebanon and Lafferty (2001).
Throughout the paper we consider spaces of strictly positive conditional probability distributions where the sample spaces of the explanatory and response variable are finite. Moving to the infinite case presents some serious difficulties. The positivity constraint on the other hand does not play a crucial role in the theorem and may by discarded at some notational cost.
The next section describes some relevant concepts from Riemannian geometry and is followed by a description of the manifolds of normalized and nonnormalized conditional models. Section 4 describes a family of probabilistic mappings that will serve as the basis for the invariance requirement of the characterization theorem in Section 5. Section 6 applies the characterization result to logistic regression and AdaBoost and is followed by concluding remarks.

Relevant Concepts from Riemannian Geometry
In this section we describe briefly relevant concepts from Riemannian geometry. For more details refer to any textbook discussing Riemannian geometry.
Informally, an nth dimensional differentiable manifold M is a continuous and differentiable set of points that is locally equivalent to R n . The set of infinitely differentiable real valued functions on M is denoted by C ∞ (M). A diffeomorphism between two manifolds M, N is a bijection f : M → N such that f and f −1 are infinitely differentiable.
With every point p ∈ M, we associate a vector space T p M ∼ = R n called the tangent space. The elements of T p M can be thought of as directional derivatives at p operating on C ∞ (M). In many cases, the manifold M is a submanifold of a larger manifold, often R m , m ≥ n. For example, the nth dimensional simplex is a submanifold of R n+1 . In these cases, the tangent space of the submanifold T p M is a subspace of T p R m and we may represent tangent vectors v ∈ T p M in the standard basis {∂ i } m i=1 of the embedding tangent space is a differentiable manifold M equipped with a Riemannian metric g. The metric g is defined by a symmetric positive definite inner product on the tangent spaces T p M that is C ∞ in p g p (·, ·) : T p M × T p M → R, p ∈ M.
Since for every u, v ∈ T p M g p is completely described by {g p (∂ i , ∂ j )} -the set of inner products between the basis elements The metric enables us to define lengths of tangent vectors v ∈ T p M by v = v, v p and lengths of curves γ : [a, b] → M by L(γ) = b a γ(t) dt whereγ(t) is the velocity vector of the curve γ at time t. Using the above definition of lengths of curves, we can define the distance d(x, y) between two points x, y ∈ M as where Γ(x, y) is the set of piecewise differentiable curves connecting x and y. The distance d, also called geodesic distance, turns the Riemannian manifold into a metric space. In other words the distance d : M×M → R defined above satisfies the usual properties of positivity, symmetry and triangle inequality.
Given two Riemannian manifolds (M, g), (N , h) and a diffeomorphism between them f : M → N we define the push-forward and pull-back maps below, which are of crucial importance to the characterization theorems of section 5.
Intuitively, the push-forward transforms velocity vectors of curves γ to velocity vectors of transformed curves f (γ).
Definition 2. Given a metric h on N we define a metric f * h on M called the pull-back metric by Definition 3. An isometry is a diffeomorphism f : M → N between two Riemannian manifolds (M, g), (N , h) for which the following condition holds Isometries, as defined above, identify two Riemmanian manifolds as identical in terms of their Riemannian structure. Accordingly, isometries preserve all the geometric properties including the geodesic distance function d g (x, y) = d h (f (x), f (y)). Note that the above definition of an isometry is defined through the local metric in contrast to the global definition of isometry in other branches of mathematical analysis.

Normalized and Non-Normalized Conditional Manifolds
Given a parametric family of distributions {p(y ; θ) : θ ∈ Θ ⊂ R n } and assuming some regularity conditions we can identify statistical models in it as points on the manifold Θ. The Fisher information matrix E θ {ss } where s = ∇ θ log p(y ; θ) may be used to endow Θ with a Riemannian structure In the finite non-parametric setting, which is the topic of this paper, the sample space Y is a finite set with |Y| = n and Θ is the n − 1 simplex which represents the manifold of all positive probability models over Y. Representing tangent vec- For more details on the Fisher information metric in the parametric and the non-parametric cases refer to Amari and Nagaoka (2000).
Given two finite event sets X , Y of sizes k and m respectively, a conditional probability model p(y|x) reduces to an element of P m−1 for each x ∈ X . We may thus identify the space of conditional probability models associated with X and Y as the product space For our purposes, it will be more convenient to work with the more general case of positive non-normalized conditional models. In this case the manifold of conditional models is the cone of k × m matrices with positive entries, denoted by R k×m + . Since P k m−1 ⊂ R k×m + , results obtained for non-normalized models apply to normalized models as a special case. In addition, some of the notation and formulation is simplified by working with non-normalized models. By taking this approach, we follow the philosophy of Campbell (1986) and Lebanon and Lafferty (2001).
We replace the cumbersome probabilistic notation with matrix notation M ij = p(y j |x i ). Note that matrices that correspond to normalized models are (row) stochastic matrices. We denote tangent vectors to R k×m + using the standard basis Tangent vectors to P k m−1 , when expressed using the basis of the embedding tangent space T M R k×m + are linear combinations of {∂ ij } such that the sum of the combination coefficients over each row are 0, e.g.
Note that the identification of the space of conditional models as a product of simplexes demonstrates the topological and differentiable structure. In particular, we do not assume that the metric has a product form.
In the characterization theorem we will make use of the fact that P k m−1 ∩ Q k×m and R k×m are dense in P k m−1 and R k×m + respectively. Since continuous functions are uniquely characterized by their values on dense sets, it is enough to compute the metric for positive rational models Q k×m + . The value of the metric on non-rational models follows from its continuous extension to R k×m + .

Congruent Embeddings by Markov Morphisms of Conditional Models
We now discuss some probabilistically meaningful transformations of conditional models that correspond to sufficient statistics on conditional models. These transformations play a crucial role in the characterization theorem and are termed congruent embeddings by a markov morphism for consistency withČencov (1982) and Campbell (1986).
In other words, the ith row of M ⊗ Q is the ith row of the matrix product M Q (i) .
Definition 5. Let A = {A 1 , . . . , A m } be a partition of {1, . . . , n} with 0 < m ≤ n. An A-stochastic matrix is a stochastic matrix Q ∈ R m×n whose rows are concentrated on A. In other words, ∀i n j=1 Q ij = 1 and Note that the columns of any A-stochastic matrix have precisely one non-zero element.
Definition 6. An A-stochastic matrix is called uniform if every row has the same number of non-zero elements and if all its positive entries are identical.

UAI 2004 LEBANON
The definition below of a congruent embedding by a markov morphism is a straightforward generalization ofČencov and Campbell's definition to the case of conditional models.
Definition 7. Let B be a k sized partition of {1, . . . , l} and {A (i) } k i=1 be a set of m sized partitions of {1, . . . , n}. For a B-stochastic matrix R ∈ R k×l (3) Maps of the form (3) are termed congruent embeddings by a markov morphism of R k×m + into R l×n + and are denoted by the function class F l,n k,m .
The componentwise version of equation (3) is with the above sum containing precisely one nonzero term since every column of Q (s) and R contains only one non-zero entry. The push-forward map f * : for ∂ ab ∈ T M R k×m + and ∂ ij ∈ T f (M) R l×n + . Congruent embeddings by a markov morphism are injective and if restricted to the space of normalized models P k m−1 we have f (P k m−1 ) ⊂ P l n−1 . Using equation (5), the pull-back of a metric g on R l×n The term congruent embedding by a markov morphism is motivated by the following observation. A map f ∈ F l,n k,m transforms p, a conditional model over explanatory space {x 1 , . . . , x k } and response space {y 1 , . . . , y m }, to a conditional model q = f (p) over explanatory space {x 1 , . . . , x l } and response space {y 1 , . . . , y n } in the following way. If R = I the model p(·|x i ) corresponds to extracting a sufficient statistic represented by the rows of Q (i) from the model q(·|x i ). If R = I, then in addition a sufficient statistic on the explanatory space {x 1 , . . . , x l } is extracted to obtain {x 1 , . . . , x k }.
Several observations are in order. First, note that the above definitions of the manifold of conditional models and of F l,n k,m are applicable in a non-parametric setting. In this setting, statistics correspond to taking the row product of a model with a stochastic matrix. Sufficient statistics correspond to taking the row product of the model with an A-stochastic matrix, that contains only one non-zero element in each column. In this case the mapping is injective and hence invertible.

AČencov Characterization of Metrics on Conditional Manifolds
We now turn to the generalization ofČencov's theorem to conditional manifolds. We proceed with the case of non-normalized conditional models and come back at the end of the section to normalized models. The method of proof is somewhat similar to the generalization ofČencov's theorem to the positive cone by Campbell (1986). We use only standard techniques from differential geometry and avoid the use of category theory. Before we state the main theorems we present some results and definitions that will be useful in the proofs.
We denote by M i the ith row of the matrix M and by | · | the L 1 norm applied to vectors or matrices. For non-negative matrices M we have |M | = i |M i | = ij M ij . Proposition 1. Maps in F l,n k,m are norm preserving: Proof. Multiplying a positive row vector v by an Astochastic matrix T is norm preserving As a result, |[M Q (i) ] i | = |M i | for any positive matrix M and hence |M ⊗Q| = |M |. A map f ∈ F l,n k,m is norm preserving since We discuss next three mappings in F l,n k,m that will have a key role in the proof of the characterization theorem.

Three Useful Transformations
The first transformation h Π σ ∈ F k,m k,m is parameterized by a permutation σ over k letters and a sequence of permutations Π = (π (1) , . . . , π (k) ) over m letters. It is defined by Q (i) being the permutation matrix that corresponds to π (i) and R being the permutation matrix that corresponds to σ. The push forward is h Π σ * (∂ ab ) = ∂ σ(a)π (a) (b) and requiring h Π σ to be an isometry from (R k×m + , g) to itself results in ). (7) The usefulness of h Π σ stems in part from the following proposition.
Proposition 2. Given ∂ a1b1 , ∂ a2b2 , ∂ c1d1 , ∂ c2d2 with a 1 = c 1 and a 2 = c 2 there exists σ, Π such that Proof. The desired map may be obtained by selecting Π, σ such that σ(a 1 ) = a 2 , σ(c 1 ) = c 2 and π (a1 The second transformation r zw ∈ F kz,mw k,m for z, w ∈ N, is defined by Q (1) = · · · = Q (k) ∈ R m×mw and R ∈ R k×kz being uniform matrices. The exact forms of {Q (i) } and R are immaterial for our purposes. By equation (5) the push-forward is for some permutations π, σ that depend on s, t. The pull-back of g is The third transformation y M is parameterized by a rational model M ∈ Q k×m + . Since M is rational it may be written as where N is the natural numbers. The mapping y M ∈ By equation (5) the push-forward of y M is for some permutations π, σ that depend on M, s, t.

The Characterization Theorem
Theorems 1 and 2 below are the main result of the paper.
Theorem 1. Let {(R k×m + , g (k,m) ) : k ≥ 1, m ≥ 2} be a sequence of Riemannian manifolds with the property that every congruent embedding by a markov morphism is an isometry. Then for some A, B, C ∈ C ∞ (R + ).
Proof. The proof below uses the isometry requirement to obtain restrictions on g (k,m) M (∂ ab , ∂ cd ) first for a = c, followed by the case of a = c, b = d and finally for the case a = c, b = d. In each of these cases, we first characterize the metric at constant matrices U and then compute it for rational models M by pulling back the metric at U through y M . The value of the metric at non-rational models follows from the rational case by the denseness of Q k×m + in R k×m + and the continuity of the metric.
Proof. For u, v ∈ T M P k m−1 expressed in the coordinates of the embedding tangent space T M R k×m since |M | = k and ∀v ∈ T M P k m−1 we have j v ij = 0 for all i. We see that the choice of A and B is immaterial and the resulting metric is precisely the product Fisher information metric up to a multiplicative constant kC(k), that corresponds to the choice of C.

A Geometric Interpretation of Logistic Regression and AdaBoost
The conditional I-divergence between two positive conditional models p(y|x), q(y|x) with respect to a probability measure r over X is x r(x) y p(y|x) log p(y|x) q(y|x) − p(y|x) + q(y|x) .

Assuming
= q − p → 0 we may approximate D r (p, q) = D r (p, p + ) by a second order Taylor approximation around = 0 The first order terms ∂D r (p, p + ) ∂ (y 1 , x 1 ) = r(x 1 ) 1 − p(y 1 |x 1 ) p(y 1 |x 1 ) + (y 1 , x 1 ) zero out for = 0. The second order terms ∂ 2 D r (p, p + ) ∂ (y 1 , x 1 )∂ (y 2 , x 2 ) = δ y1y2 δ x1x2 r(x 1 )p(y 1 |x 1 ) (p(y 1 |x 1 ) + (y 1 , x 1 )) 2 at = 0 are δ y1y2 δ x1x2 r(x1) p(y1|x1) . Substituting these expressions in the Taylor approximation gives which is the squared length of r(x) (y, x) ∈ T r(x)p(y|x) R k×m + under the metric (12) for the choices A(|M |) = B(|M |) = 0 and C(|M |) = 1/(2 |M |). Lebanon and Lafferty (2001) have shown that maximum likelihood for logistic regression and minimum exponential loss for AdaBoost may be cast as minimization of conditional I-divergence D r subject to linear constraints. In both cases r is the empirical distribution r(x) = 1 N N i=1 δ x,xi over the training set {(x i , y i )} N i=1 . The I divergence D r (p, q) which both logistic regression and AdaBoost minimize is then approximately the geodesic distance between the conditional models r(x)p(y|x) and r(x)q(y|x) under a metric (12) with the above choices of A, B, C. The fact that the models r(x)p(y|x) and r(x)q(y|x) are not strictly positive is not problematic, since by the continuity of the metric, theorems 1 and 2 pertaining to R k×m + apply also to its closure R k×m + -the set of all non-negative conditional models.

Discussion
We formulated and proved an axiomatic characterization of a family of metrics, the simplest of which is the Fisher information metric in the conditional setting for both normalized and non-normalized models. This result is a strict generalization of Campbell anď Cencov's theorems. For the case k = 1, Theorems 1 and 2 reduce to the theorem of Campbell (1986) and corollary 1 reduces to Lemma 11.3 ofČencov (1982).
Using the characterization theorem and the result of Lebanon and Lafferty (2001) we give for the first time, a differential geometric interpretation of logistic regression and AdaBoost whose metric is characterized by natural invariance properties. It is interesting to explore directions suggested by alternative choices of A, B and C. Another interesting prospect is exploring conditional modeling, where the unbounded I divergence is replaced with the more robust geodesic distance.