Arshia Cont

Shlomo Dubnov

Gérard Assayag

On the Information Geometry of Audio Streams with Applications to Similarity Computing

This paper proposes methods for information processing of audio streams using methods of information geometry. We lay the theoretical groundwork for a framework allowing the treatment of signal information as information entities, suitable for similarity and symbolic computing on audio signals. The theoretical basis of this paper is based on the information geometry of statistical structures representing audio spectrum features, and specifically through the bijection between the generic families of Bregman divergences and that of exponential distributions. The proposed framework, called Music Information Geometry allows online segmentation of audio streams to metric balls where each ball represents a quasi-stationary continuous chunk of audio, and discusses methods to qualify and quantify information between entities for similarity computing. We define an information geometry that approximates a similarity metric space, redefine general notions in music information retrieval such as similarity between entities, and address methods for dealing with non-stationarity of audio signals. We demonstrate the framework on two sample applications for online audio structure discovery and audio matching.

I. INTRODUCTION

M USIC Information Retrieval (MIR) systems deal one way or another with the information content of music signals, their transformations, or extraction of models or parameters from this information. A common question that many such systems ask at their front-end is what information is presented in the signal and to what relevancy? This question is central in almost all music information retrieval systems dealing either with temporal structures of audio data streams for search applications (query-by-humming, audio matching, music summarization etc.), or with temporal decomposition of audio (source separation, multiple-source identification, etc.).

In this paper, we seek a comprehensive framework that allows us to quantify, process and represent information contained in temporal structure of audio streams. An audio stream is a sequence of audio data presented to an algorithm one item at a time, thus capable of online processing of information. The framework introduced in this paper brings in concepts from various literatures: music signal processing, information geometry and machine learning. By this combination, we aim to investigate the natural geometric structures occupied by families of probability distributions representing audio streams that implicitly represent the ongoing information structure of the signal over time. Within this framework, music information arrives in discrete analysis windows over time and occupy Copyright (c) 2010 IEEE. Personal use of this material is permitted. However, permission to use this material for any other purposes must be obtained from the IEEE by sending a request to pubs-permissions@ieee.org.

Arshia Cont is with Institute of Research for Coordination of Acoustics and Music (IRCAM) in Paris.

statistical points in an information manifold. These statistical points are then analyzed within a generic mathematical framework called Music Information Geometry, that assures the existence of an approximate similarity metric space over data, and redefines common concepts in the MIR literature such as similarity and metric balls.

The present work inscribes itself within the more general framework of information dynamics measures for audio in relation to music cognition. Dubnov has studied information measure based on mutual information between the past and present of audio and showed its significance compared to data collected from listeners [START_REF] Dubnov | Structural and affective aspects of music from statistical audio signal analysis[END_REF]. He later developed his method in [START_REF] Dubnov | Unified view of prediction and repetition structure in audio signals with application to interest point detection[END_REF] for non-stationary audio by separating the data and model aspects of information dynamics. One of the difficulties with this approach is determining what consists of relevant information between data and model. For instance, in the data case it is assumed that individual observations carry little information about the model, while in the model case they are represented by cluster centers, so the information between observations is ignored. The present work solves this problem by explicitly defining models on statistical points and providing mathematical tools for further processing.

Music Information Retrieval (MIR) systems mostly rely on the notion of self-similarity measures for music and audio [START_REF] Foote | Media segmentation using selfsimilarity decomposition[END_REF] as a basis to compare and deduce music structures. Many MIR techniques also rely on geometric concepts in machine learning for building classifiers in supervised problems (genre classification, artist identification, query by example etc.) or clustering data in unsupervised settings (audio search engines, structure discovery etc.). Implicit in all these considerations is the fact that similarity measures, with all their variety of formulations, constitute a metric space where equivalence categories can be deduced and compared. At this stage, there is no clear boundary in the literature between metrics and the notion of similarity. Another drawback of common information processing methods in MIR is the wide use of bag of features models, where audio data is represented to the system with no temporal order. Despite their wide use, such techniques ignore the temporal dimensions of the data which is an essential criteria in many retrieval processes. The proposed Music Information Geometry framework aims at approximating metric spaces over a wide-variaty of signal representations and similarity measures that lie within the generic families of Bregman divergences and exponential family distributions, and by explicitly considering the temporal order of audio streams.

We emphasize that our focus here is on the mathematical properties of common distortion measures once formulated using methods of information geometry, and not the difficult and open problem of characterizing which distortion measures best address the subjective quality of particular psychoacoustic characteristics of music. The major intent of this paper is to lay the theoretical groundwork for forthcoming experimental results. However, we exhibit results on two major MIR applications defined on information manifolds: online audio structure discovery and audio matching. The goal here is not to compare these results with the extensive literature within each application, but to showcase the power of information geometric formulations on complex problem sets. Details of experimental results are thus left for dedicated publications.

This paper is organized as follows: Section II introduces basic mathematical tools and theorems of information geometry over Bregman divergences and their relationship to exponential distributions. Section III, refines common tools and terms such as distortion and similarity to prepare the common ground. Section IV introduces our Music Information Geometry framework, providing tools, theorems and definitions that permit a migration from Bregman divergences to similarity metric spaces. Section V provides sample applications of the proposed framework proceeded by conclusions.

II. PRELIMINARIES

In this section, we introduce the mathematical basis of our proposal. We start by introducing basic concepts of information geometry and move on to Bregman divergences and their geometric properties and introducing exponential families and their behavior in a Bregman geometry. The reader is referred to [START_REF] Amari | Methods of information geometry[END_REF]- [START_REF] Nielsen | On bregman voronoi diagrams[END_REF] for details and proofs.

A. Information Geometry of Statistical Structures

Let us consider a family of probability distributions specified by a vector parameter p(x, ξ) where ξ is a vector constituting the model parameters of the probability distribution. This set can be regarded as a manifold under certain regularity conditions where ξ = (ξ 1 , . . . , ξ n ) would be its coordinate system. A manifold is an abstract mathematical space in which every point has a neighborhood which resembles a regular Euclidean space but the global structure may be more complicated. By defining probability distributions on a manifold, each point would then refer to a realization of a family of probability distribution. The manifold has a natural geometrical structure if the geometrical structure is (1) invariant under the coordinate system (or parameters) used to specify the distributions, and (2) invariant under rescaling of the random variable x.

Amari [START_REF] Amari | Methods of information geometry[END_REF] shows that representing statistical structures within a Riemannian geometry equipped with the Fisher Information measure as inner product g, and a canonic affine connection ∆, would constitute an information geometry. This construction allows definitions for many geometrical structures such as distances, lines, volumes etc. Among such constructs, the existence of dual canonic divergences or distance like measure D between two points in the geometry is of extreme importance to us. Alternatively, there have been attempts to define information geometries on Riemannian manifolds with g, directly by inducing divergences instead of affine connections. Recently, Zhang [START_REF] Zhang | Divergence function, duality, and convex analysis[END_REF] introduced a canonical form of affine connection that deduces many types of divergence functions which are in common use in engineering including the well-known Bregman Divergence family [START_REF] Bregman | The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming[END_REF]. Given these findings, and within the framework introduced in [START_REF] Zhang | Divergence function, duality, and convex analysis[END_REF], we can assume a geometrical structure over probability manifolds S using Fisher Information and Bregman Divergences.

Throughout this paper, we assume that a system under measurement generates families of probability distributions on a dual information manifold defined as (S, g, ∆ D , ∆ D * ) where its geometric properties are induced by employing Bregman Divergence D. Also, the term point represents a family of probability distributions that belongs to a probability simplex X ∈ R d . Vector mathematical constructs are notated using boldface characters in contrast to scalar constructs.

B. Elements of Bregman Geometry

Definition 1 ( [6], [START_REF] Bregman | The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming[END_REF]). For any two points p and q of X ∈ R d , the Bregman Divergence D Φ (., .) : X × X → R of p to q associated to a strictly convex and differentiable function Φ (called generator function) is defined as:

D Φ (p, q) = Φ(p) -Φ(q) -∇Φ(q), p -q (1)
where ∇Φ = ∂Φ ∂x1 , . . . , ∂Φ ∂x d denotes the gradient operator and p, q the inner or dot product.

The most interesting point about Bregman family of divergence is that they can generate many of the common distances in the literature. Table I shows several of these canonical generations (see also [START_REF] Nielsen | Sided and symmetrized bregman centroids[END_REF]). Among common properties of Bregman divergences, we can easily show that they are nonnegative, convex on the first argument, and linearly invariant on Φ. The reader is referred to [5, Appendix A] for details.

I BREGMAN DIVERGENCE GENERATION EXAMPLES X Φ D Φ (p, q) Generic Name R + x log x -x p log p q -p + q Kullback-Leibler Div. R + * -log x p q -log p q -1 Itakura-Saito Div. R d ||x|| 2 ||p -q|| 2 Squared Euclidean
1) Dual Structure: An important property of information manifolds is the existence of a dual structure based on Legendre transformation for any geometrical structure on S. Using statistical manifolds on Bregman divergences, this dual structure can be entirely exploited by defining the dual divergence that is generated by the Legendre transformation of Φ or Φ * = ∇ -1 Φ. In the sequel, we denote the dual point of x as x ′ = ∇Φ(x). The following property shows the relationship between a Bregman divergence and its dual: Property 1 ( [START_REF] Nielsen | On bregman voronoi diagrams[END_REF]). D Φ * is also a Bregman divergence called the Legendre dual divergence of D Φ and we have:

D Φ (p, q) = Φ(p) + Φ * (q)-< p, q ′ >= D Φ * (q ′ , p ′ )
2) Bregman Balls: In analogy to Euclidean geometry, we can define a Bregman ball. Due to the asymmetric nature of Bregman divergences, a Bregman ball can be defined as two counterparts which are right-type or left-type. A Bregman ball of right-type centered at µ k with radius R k is defined as:

B r (µ k , R k ) = {x ∈ X : D Φ (x, µ k ) ≤ R k } (2)
Similarly, the Bregman ball of left-type B ℓ (µ k , R k ) is defined by inverting the divergence in eq. 2 to D Φ (µ k , x).

3) Bregman Information: Let X be a random variable following a probability ν that takes values in

X = {x i } n i=1 ⊂ R d . Let µ = E ν [X].
Then the Bregman Information of X is:

I Φ (X) = E ν [D Φ (X, µ)] = n i=1 ν i D Φ (x i , µ) (3)
Well-known examples of Bregman Information are variance and mutual information (see [START_REF] Banerjee | Clustering with bregman divergences[END_REF]).

C. Exponential Family of Distributions

Among different distribution families, the exponential family of probability distributions are of special importance and have found their way in many pattern recognition applications. Their canonical definition is as follows:

p(x|θ) = exp [< θ, f (x) > -F (θ) + C(x)] (4)
where f (x) is the sufficient statistics and θ ∈ X represents the natural parameters. F is called the cumulant function, and fully characterizes the exponential family while the term C(x) ensures density normalization. Many of commonly used distribution families can be generated by proper choice of natural parameters and sufficient statistics as demonstrated in table II. The expectation of X with respect to p(x; θ) is called the expectation parameter or µ = µ(θ) = x p(x; θ) dx.

N (x; ν, σ 2 ) { ν σ 2 -1 2σ 2 } - θ 2 1 4θ 2 + 1 2 log(-π θ 2 ) (Univ. Gaussian) N (x; ν, Σ) {Σ -1 ν -1 2 Σ -1 } 1 2 ν T Σ -1 ν (Multiv. Gaussian) + 1 2 log det(2πΣ) N ! d j=1 x j ! d j=1 q x j j log q i 1- d j=1 q i log(1 + d i=1 exp θ i ) (Multinomial)
1) Duality of natural and expectation parameters: It can be shown [START_REF] Amari | Methods of information geometry[END_REF] that the expectation and natural parameters of exponential families of distributions have a one-to-one correspondence and span spaces that exhibit a dual relationship as outlined in section II-B1. Due to the convexity of F , its dual F * exists on Θ and the following important one-to-one mappings hold between the two spaces:

µ(θ) = ∇F (θ) and θ(µ) = ∇F * (µ) (5)
meaning that the expectation parameter is the image of the natural parameter under the gradient mapping and vice-versa.

2) Bijection with Bregman divergences: A natural question to ask at this point is: What family of Bregman divergence should be chosen for a given family of exponential distributions? The answer lies in the important property of bijection between exponential families and Bregman divergences as proved in [START_REF] Banerjee | Clustering with bregman divergences[END_REF]. This theorem implies that every regular exponential family corresponds to a unique Bregman divergence and vice versa, leading to a one-to-one mapping: Theorem 1 ( [START_REF] Banerjee | Clustering with bregman divergences[END_REF]). Let p(x; θ) be the probability density function of a regular exponential family of distribution with F as its associated cumulant function. Let F * be the conjugate function of F . Let θ ∈ Θ be the natural parameter and µ be the corresponding expectation parameter. Then p(x; θ) can be uniquely expressed as

p(x; θ) = exp(-D F * (x, µ))b F * (x) (6)
where b F * (x) is a uniquely determined function.

Table III shows three examples of bijection between exponential distributions and Bregman divergences with derived expectation parameters corresponding to examples in table II. This information suggests that the bijected Bregman divergence for Multinomial distributions is the well-known KL divergence, whereas for a spherical Gaussian it amounts to a simple Mahalanobis distance (see [START_REF] Banerjee | Clustering with bregman divergences[END_REF] for more examples).

TABLE III EXPONENTIAL DISTRIBUTIONS WITH BIJECTED BREGMAN DIVERGENCES

Distribution

Expectation Parameter Bijected Bregman Div.

p(x, Θ) µ D F * (x, µ) N (x; ν, σ 2 ) ν Squared Euclidean 1 2σ 2 (x -ν) 2 N (x; ν, Σ) ν Mahalanobis (x -µ) T Σ(x -µ) Multinomial {N q j } d-1 j=1
Kullback-Leibler

3) Mixture Models: In machine learning and pattern recognition literature, many stochastic sources are expressed as a mixture of k densities of the same exponential family. This yields a soft clustering where clusters correspond to the components of the mixture model, and the soft membership of a data point in each cluster is proportional to the probability of the data point being generated by the corresponding density function. Using the right side of eq. 6, the log-likelihood of an exponential mixture model with mixture weights π i becomes:

L(x|Γ) = k i=1 log[π i b F * (x)]D F * (x, µ i ) = k i=1 ν i D F (θ i , x ′ ) (7)
where property 1 and relationships in eq. 5 have been employed. Note that eq. 7 is simply a reiteration of the Bregman Information in the dual setting and up to an additive constant. This simply states that there is a duality relationship between exponential distributions and their mixtures. This is also true for more general affine connections as discussed in [START_REF] Amari | Methods of information geometry[END_REF].

III. DISTORTIONS, SIMILARITY, AND METRICS

An information manifold defined on Bregman divergences or (S, g, ∆ D , ∆ D * ) provides us with interesting information theoretic tools for qualification and quantification of parametric stream information. Once such a framework exists, it is desirable to apply it to common pattern recognition problems such as nearest neighbor search or segmentation schemes to name a few. Such measures of information have been widely referred to as distortion measures in the speech and audio processing literatures. The distortion between two entities represents the cost resulting when the first is reproduced by the other and is related to new information carried from one entity to other. Distortion measures have wide variety of applications in the design and comparison of systems [START_REF] Gray | Distortion measures for speech processing[END_REF]. Despite their usefulness, these measures do not guarantee equivalence between entities if distortion is low. This is in contrast to most information processing systems where a notion of metric is required to assure equivalence between classes for clustering or classifying data points or clusters. In this section, we study necessary properties for metric equivalence and discuss the behavior of Bregman distortions as metrics.

Let Ω be a nonempty set and R + be the set of non-negative real numbers. A metric function on Ω is a function d : Ω×Ω → R + if it satisfies the following properties [START_REF] Cilibrasi | Clustering by compression[END_REF]:

Property 2. d(x, y) = 0 iff x = y Property 3 (Symmetry). d(x, y) = d(y, x) Property 4 (Triangle Inequality). d(x, y) ≤ d(x, z)+d(z, y)
We are interested in a particular type of distance, the "similarity distance". In the field of Music Information Retrieval, Jonathan Foote has been credited for promoting and using self-similarity measures for music and audio [START_REF] Foote | Media segmentation using selfsimilarity decomposition[END_REF]. The MIR literature on database search, structure discovery, querybased retrieval and many more, rely on Foote's general notion of similarity as a basis to compare, retrieve, and discover music structures. Nevertheless, the metrics employed in such approaches lack one or more of the properties above, and moreover do not necessarily address any information theoretic aspect of the content. In this section, we study the notions of distortions, similarity and metric spaces with a special eye on the bijected Bregman divergences on information manifolds to pave the way for the proposal in section IV.

A. Equivalence and Similarity

Within information entities, an ideal similarity metric d and distortion measure D are inversely related. In other words, two entities have high similarity when the information rate between them is low, and vice versa. Given this intuition, we can consider two information states similar if the information carried from one to the other is minimal. Because signals can have arbitrary forms, usual choices for assessing signal difference like mean-squared error make little sense. Instead we rely on distance measures that quantify difference between the signals' probabilistic descriptions. We thus append the following definition to property 2: Definition 2 (Similarity). Two entities θ 0 , θ 1 ∈ X are assumed to be similar if the information gain by passing from one representation to other is zero or minimal; quantified by D(θ 0 , θ 1 ) < ǫ which depends not on the signal itself, but on the probability functions p X (x; θ 0 ) and p X (x; θ 1 ).

Following the intimate relationship between exponential families and Bregman divergences, they would naturally fit to the above definition to detect similar entities when audio streams are modeled parametrically as exponential family of distributions. While property 2 is inherent for all D F , Bregman divergences are not necessarily metrics since they are usually not symmetrical and the triangular inequality does not generally hold. We now study these two missing properties and provide the grounds to approach them in section IV.

B. Symmetrized Bregman Divergences

Bregman divergences are not necessarily symmetric and various methods exist to make them so. A common approach is to employ the J-divergence or

D J F = 1 2 [D F (x, y) + D F (y, x)] (8)
as in [START_REF] Stylianou | Perceptual and objective detection of discontinuities in concatenative speech synthesis[END_REF], [START_REF] Carlson | A computationally compact divergence measure for speech processing[END_REF], but this symmetrization scheme does not fit the dually flat manifold [START_REF] Nielsen | Sided and symmetrized bregman centroids[END_REF], and requires further considerations for use within applications that necessitate similarity computing.

C. Triangle Inequality

Among the three properties for metrics, the triangle inequality is probably the most non-trivial. The triangle inequality can be generalized for any triple x, y, and z in X as follows:

D F (x, z) + D F (z, y) = D F (x, y) + x -z, y ′ -z ′ (9)
If the underlying geometry is dually flat, which is the case with manifolds deduced from Bregman divergences, the generalized Pythagoras theorem states that

D F (x, y) ≥ D F (x, z) + D F (z, y) (10)
where the equality hold only if for X being a convex simplex of x [START_REF] Amari | Methods of information geometry[END_REF], z = argmin q∈X D F (q, y) which is not true for arbitrary entities r ∈ X , and we are left with eq. 10 which is the inverse of property 4. Therefore special attention must be paid in computing similarity using regular Bregman divergences.

IV. MUSIC INFORMATION GEOMETRY

Using mathematical tools introduced so far, we aim at providing a framework for processing and qualifying the effectiveness of audio streams. We define an affine information geometry (S, g, ∆ D , ∆ D * ) using Bregman divergences induced by the choice of statistical distribution over incoming data and represented hereafter as D F , where F is deduced from theorem 1. We start by presenting the general framework, proceed to data and model information entities, and discuss information theoretic tools useful for many pattern recognition and information retrieval applications.

A. General Framework

In our framework, audio data arrives incrementally to the system as time series X ti containing sampled overlapping windows of audio where t i is time (in seconds) of the window center. For simplicity, we drop the i index hereafter and use X t instead where t ∈ N. We assume that data underlying X t is generated by a family of exponential distributions (or mixture there of). By this assumption, theorem 1 would provide us automatically with distortion measure D F and underlying geometrical tools discussed so far to introduce an information processing framework. In this section, we discuss these assumptions and their consequence in the design and formulation of common problems in audio processing.

The choice of the exponential family distribution over time series X t depends on the nature of the problem to solve and constitutes the a priori over modeling. Despite this limitation, generic exponential distributions (or their mixtures) are widely employed in general pattern recognition as well as audio and speech processing systems either implicitly or explicitly. For example many researchers choose a time-frequency representation over X t as S t (ω) such as short-time Fourier or wavelet transforms, where each S t (ω) can be treated as frequency distributions or histograms of the corresponding X t . Such histogram features can be assumed, without loss of generality, to be generated by Multinomial distributions with the wellknown KL divergence as bijected distortion measure. This choice has been empirically proved in [START_REF] Stylianou | Perceptual and objective detection of discontinuities in concatenative speech synthesis[END_REF] for concatenative speech synthesis. Other systems tend to use more compact representations for audio signals such as Cepstral Coefficients and/or by directly modeling through probability distributions with sparser natural parameter space. The review of such systems is out of the scope of this paper but existing literature should convince the reader of the wide use of exponential distributions and their mixtures. In summary, any design process for a given problem that involves exponential distributions (or their mixtures) as front-end has a unique information geometry defined by its bijected Bregman divergence.

Using exponential distributions over data streams, the time series X t can be represented by their equivalent distributions p(x, θ t ) or by natural parameters θ t ∈ Θ. θ t s constitute the points of the information manifold, referred hereafter as data points. Converting back and forth between the data in X t (or relevant feature representations) and θ t is problem dependent but is a one-to-one mapping (see [START_REF] Banerjee | Clustering with bregman divergences[END_REF] for examples). In the following subsections, we employ information geometric tools for information processing of underlying audio streams.

B. From Data Information Rate to Model Information Rate

The first step in any information processing system is to introduce measures quantifying the amount of information carried through the signal. Following [START_REF] Dubnov | Unified view of prediction and repetition structure in audio signals with application to interest point detection[END_REF], we denote such measure as Information Rate (IR) within a transmission process over a noisy time-channel and defined as the relative reduction of uncertainty of the present considering the past. [START_REF] Dubnov | Unified view of prediction and repetition structure in audio signals with application to interest point detection[END_REF] shows that the Information Rate at time t = T is equal to the mutual information carried between the past

{X 1 , • • • , X T -1 } (denoted in the sequel as X T -1 1
) and history of the signal up to present or X T 1 . It is further shown in [START_REF] Dubnov | Generalization of spectral flatness measure for non-gaussian linear processes[END_REF] that for a stationary Gaussian process, IR can be approximated asymptotically in T using the spectral flatness measure of the time signal, or the ratio between geometrical and arithmetical means of {S t (ω)}. We refer to this measure as Data-IR, reflecting information rates on data points. It can be proven that this data-IR measure is a special case of Bregman Information for Itakura-Saito (IS) divergence, widely used in speech and audio as a distortion measure on power spectra [START_REF] Gray | Distortion measures for speech processing[END_REF]. See [START_REF] Cont | Modeling musical anticipation: From the time of music to the music of time[END_REF]Ch. 4] for proof.

Using Bregman Information on information manifolds, the Data-IR measure can thus be extended to other representational aspects of the underlying stream. Despite this theoretical comfort, Data-IR is not useful in practice for two main reasons: (1) the underlying assumption of stationarity on X t which is not true for real audio, and (2) extensive consideration of data-points in computation specially for long streams.

To tackle both issues, we adopt the plausible hypothesis that the signal is stationary in a finite and continuous time-interval under some model θ k and described through P (x 1 , . . . , x n |θ k ). Within our information manifold, this draws down to the geometric intuition that a set of continuous data points on our manifold are concentrated around a single point representative of θ k . Definition 3 (Models). Given (S, g, ∆ D , ∆ D * ) on a regular exponential family formed on X k , a model θ i consists of a set

X i = {X k |k ∈ N , N ⊂ N} that forms a minimum enclosing Bregman Ball B r (µ i , R i ).
A model defined and constructed on an audio stream refers to continuous data points on the information manifold that are self-contained in an information theoretic sense, and corresponds to a quasi-stationary chunk of audio in the stream. Therefore, the distinction between data points and models on an audio stream manifold is structural: data points refer to micro-structures of the audio whereas models correspond to macro-structures that give sense to the global structure of the stream. In this manner, it makes little sense to directly compute between data points where their model parameters provide enough information for intra-structural comparisons. For similarity computing, it is more useful to structurally refer to model parameters first and if needed, refer to the data points within the model. Therefore, providing a metric space as in section III is crucial for between-model comparisons.

The above definition requires us to formalize the following aspects: (1) How to form a minimum enclosing ball once model data-points X i are given, (2) How to quantify the information rate carried from one model to another, and (3) how to incrementally achieve a segmentation of audio streams to information entities or models as defined above. The following subsections would address each question separately.

C. Centroid Computation

An important tool in both quantizer design and cluster analysis techniques is the generalized centroid of a cluster of data points. Given a cluster of points, this is the best single representative of the cluster and defined as the optimizer of the minimum average distance for the entire set of points in the cluster. Banerjee et al [START_REF] Banerjee | Clustering with bregman divergences[END_REF] have proven the following important theorem for Bregman centroids: Theorem 2 ( [5]). Let X be a random variable that takes values in X = {x i } n i=1 ⊂ R d following a probability ν. Given a Bregman divergence D F , the right type centroid of X or

c F R (X ) = argmin c n i=1 ν i D F (x i , c) (11)
is unique, independent of F and coincides with µ

= E ν [X]
or for ν i = 1/n to center of mass µ = 1 n n i=1

x i .

It is important to notice the equivalence between eq. 11 and that of Bregman Information on uniform distributions with additional optimization. In other words, a computed centroid on an information geometric framework represents a minimum enclosing ball in terms of information content, or minimum distortion point of the given set. Given this, we can safely adopt the Bregman centroid computation for forming balls representing models of our information geometric framework.

In addition to the above definition and due to general asymmetry of Bregman divergences, we can define a lefttype centroid by reversing the order of computation in eq. 11.

Obviously, theorem 2 does not hold for the left-type centroid and the optimization becomes non-trivial. We can however employ the dualistic structure of our information manifold to obtain c F L . Combining theorem 2 and property 1 we obtain:

c F L (X ) = (∇F ) -1 ( n i=1 ∇F (x i )) = (∇F ) -1 (c F * R (X ′ )) (12)
stating that the left-type centroid is obtained by calculating the right-type centroid in the dual manifold using theorem 2 and converting it back to the original space. For asymmetric Bregman divergences, a symmetrized Bregman centroid on the set P = {p i } n i=1 ⊂ X can be defined by the following optimization problem:

c F (P) = argmin c∈X n i=1 D F (c, p i ) + D F (p i , c) 2 (13)
conforming to the symmetrization scheme in eq. 8. This optimization problem has been previously addressed in [START_REF] Veldhuis | On the computation of the kullbackleibler measure for spectral distances[END_REF] for Kullback-Leibler divergences and by employing convex optimization techniques. It is shown in [START_REF] Nielsen | Sided and symmetrized bregman centroids[END_REF] that it can be extended to general Bregman divergences and simplified to a constant-size system relying on the right-type and lefttype centroids by employing duality and a geodesic-walk dichotomic approximation algorithm; hence, well adapted to information manifolds of exponential distributions. Solving eq. 13 requires an optimization framework in contrary to most literature that define (for example) symmetrized KL divergence centroids as arithmetic or normalized geometric mean of the left-type and right-type. Both approaches in [START_REF] Veldhuis | On the computation of the kullbackleibler measure for spectral distances[END_REF] and [START_REF] Nielsen | Sided and symmetrized bregman centroids[END_REF] empirically prove this remark on image and audio processing applications. For our framework, we adopt the geodesic-walk algorithm in [START_REF] Nielsen | Sided and symmetrized bregman centroids[END_REF] to solve for an optimal symmetric Bregman ball. The radius of a given Bregman ball B r with centroid c F R on the set P = {p i } n i=1 ⊂ X is simply the Bregman Information of eq. 3 on the set P. For the symmetric construction above, it is shown that this radius is equal for the right-sided and left-sided centroids [9, Corollary 3.3].

D. Model Comparison and Data Membership Check

In our information geoemtry, an audio stream is thus represented by Bregman Balls B k r (µ k , R k ) which by themselves contain continuous data points θ t . Here, we study the task of qualifying information rates within models and also membership of data points to models. These operations are important in many pattern recognition and information retrieval tasks that require information theoretic comparisons between entities such as similarity and nearest neighbor seach and clustering.

Following our definition of similarity, we can safely assign the information rate for passing from one model B i r (µ i , R i ) to another B j r (µ j , R j ) as the distortion between the two representative centroids of the two clusters or D F (µ i , µ j ) (and similarly D J F (µ i , µ j ) for symmetrized centroids). However, checking for membership of an arbitrary data point X to a given ball B k r (µ k , R k ) containing its own set of points becomes non-trivial mostly due to the lack of triangle inequality. Note that if the triangle inequality holds, this membership check simply amounts to checking whether D F (X, µ k ) ≤ R k . In the absence of this property, we perform tests by projecting X onto the Bregman ball B r (µ k , R k ). This projection is the unique minimizer X B such that

X B = argmin x∈B k r D F (x, µ k ).
Once X B is established, membership can be obtained by checking whether D F (X, X B ) ≤ ǫ.

It can be easily shown that X B lies on the geodesic line connecting X and µ k [START_REF] Nielsen | On bregman voronoi diagrams[END_REF], [START_REF] Cayton | Fast nearest neighbor retrieval for bregman divergences[END_REF]. Such geodesic is characterized as the set of points

Γ Xµ k = {∇ -1 F ((1 -λ)X ′ + λµ ′ k ) |λ ∈ [0, 1]}.
To find X B , we can first check whether X is inside the ball or not: D F (X, µ) > R k . If not, then D F (X, µ) ≤ R k and hence the projection is the point itself. Otherwise, X B ∈ Γ Xµ k for some arbitrary λ B ∈ [0, 1]. Geometrically, such a point must lie on the boundary of B r and thus combining Γ Xµ k with a bisection can approximate the placement of X B and can be found by a linear search as proposed in [START_REF] Nielsen | Tailored Bregman Ball Trees for Effective Nearest Neighbors[END_REF]. Note that this projection procedure assures an approximation of the Pythagoras equality in eq. 10.

E. Incremental Segmentation/Change Detection

In this section we propose a simple method for online segmentation of an audio stream to information geometric models and through a change detection process. Given a set of data points in S, the problem of finding models according to definition 3 is a classical clustering problem in S where each cluster defines a minimum enclosing Bregman ball over data points. Offline Clustering over Bregman spaces has been previously addressed in [START_REF] Banerjee | Clustering with bregman divergences[END_REF] and as an extension to EM algorithms. These methods are in common use for speech and audio clustering by considering bag of features or bag of frames models and thus neglecting the importance of temporal dimensions in retrieval processes. Based on our information manifolds, we propose a simple online clustering algorithm for incremental model formation that strongly employs the temporal morphology of data over the information manifold.

Following definitions 3, we base our segmentation technique on detecting information jumps in an ongoing audio stream X t for forming models or minimum-information Bregman balls over time. The information radius R k defines the maximum information gain around a centroid µ k that model k contains through D J F . Employing change detection for incremental Bregman ball formation on continuous streams has the implicit assumption that the models' information gain on audio streams is a right-continuous with left limit function of time. This assumption is a direct consequence of our initial consideration that the signal is stationary in a finite time-frame under a model θ k . This conforms to the intuitive nature of music information characterized by distinct events with an information onset implying a discontinuity with regards to the past.

The goal of model formation in our framework is thus to search for a proper segmentation on audio streams such that each resulting segment is quasi-stationary and homogeneous in terms of information content. The detection of a change is equivalent to accepting a hypothesis H 1 of change for time r ≤ n when testing against the hypothesis H 0 of no change. Algorithm 1 shows a basic online implementation of the change detection which accepts an observation sequence of length n, and initialized on X n 0 with f = 0.

Algorithm 1 Online model Segmentation/Change Detection Require: Audio stream X t , ongoing model B k (µ k , R k ), ob- servation window n, first index f Ensure: t -f ≥ n (minimum observation length) 1: Initialize observation vectors {O i } t-f -1 i=0 to X t t-f 2: Detect change point r * in {O i } with regards to B k 3: if No change is detected then 4: set f = t 5: else 6: Initiate a new Bregman ball B k+1 on {O i } n-1 i=r * 7: set f = r * , k = k + 1 8: end if 9: return next starting index f , ongoing ball B k (µ k , R k )
The change detection algorithm proposed here is an adopted version of the CuSum algorithm [START_REF] Basseville | Detection of abrupt changes: theory and application[END_REF] which has been employed in various segmentation schemes such as audio [START_REF] Omar | Blind change detection for audio segmentation[END_REF]. In a generic CuSum algorithm, the likelihood ratio of the conditional probabilities of the observations under the hypothesis H 1 and H 0 is estimated, then the maximum of the sum of the log-likelihood ratio of the sequence of observations is compared to a threshold λ to determine whether a boundary exists between two segments of the sequence. Concretely, given n observations, c n = max r n k=r ℓ k where ℓ k is the log-likelihood ratio of conditional probabilities with respect to H 0 and H 1 , and compared to λ to assess the change point.

The CuSum algorithm assumes that the conditional probabilities of observations under both hypothesis H 1 and H 0 are known. While this is a difficulty for most applications, it does not pose any in our framework. Concretely, given an ongoing model B k (µ k , R k ) and n observations, H 0 hypothesis at r assumes that O r 0 are all members of B k (µ k , R k ) as explained in section IV-D, and H 1 at r assumes that O n r constructs a new ball. Therefore, the likelihood ratio ℓ k becomes

ℓ k = D J F (c F µ k ∪ {O k-1 0 } , c F [{O n k }]) (14)
where c F is the symmetric Bregman centroid. The first argument of D J F refers to the inclusion of data points {O n k } within B k and the second is the hypothesis of forming a new ball.

The change point threshold λ applied to ℓ k of eq. 14 has a direct geometrical interpretation. It corresponds to the minimal discrimination information distance between two consecutive models on the audio stream. In other words, using the change detection algorithm above and for two consecutive models k and k + 1, we would always have D J F (µ k , µ k+1 ) ≥ λ. Figure 1 shows the result of this segmentation on an audio excerpt corresponding to the first theme of Beethoven's 1 st Piano sonata performed by Friedrich Gulda. The information geometry employed for this excerpt corresponds to amplitude spectrum, assumed without lack of generality to be generated by Multinomial distributions with the bijected Bregman as Kullback-Leibler. The normalized audio waveform is superposed by ℓ t or change point likelihoods as well as detected model onsets. This example consists of 583 data points (analysis frames) and leads to 44 disjoint and variable length models.

V. SAMPLE APPLICATIONS

To motivate the theoretical framework discussed above, we present two sample applications in pattern recognition and music information retrieval on audio streams. More results of these sample applications (on different types of sounds and music) can be found on our project website 1 .

A. Online Audio Structure Discovery

For our first sample application, we are interested in representing the repetitions and long-term regularities within an ongoing audio stream. Music structure analysis from acoustic signals has been addressed previously by various methods. A good review of existing approches can be found in [START_REF] Dannenberg | Handbook of Signal Processing in Acoustics[END_REF]. We aim at obtaining an online procedure that can quickly group equivalent patterns and find the longest sequence of models in the past of the audio stream. The first problem is referred to as clustering and the second as structure discovery. We are interested in a fast method that can address both in one shot.

The idea behind this application is the following: The Music Information Geometry framework provides us with information entities as minimum information Bregman balls over the time series X t , which can be compared to each other using the discussed methods as in symbolic equivalence classes but on a continuous metric and using the similarity definition on page 4. This brings out the idea of adapting common symbolic algorithms for the signal world.

Our algorithm for automatic discovery of audio structures is motivated by a technique for fast indexing of symbolic data such as text and DNA called Factor Oracle (FO) [START_REF] Allauzen | Factor oracle: A new structure for pattern matching[END_REF]. A time series of symbols S = σ n 1 in a FO is learned as a state-space diagram, whose states are indexed by from 0 to n. There is always a transition called the factor link labelled by symbol σ i going from state i-1 to state i. Navigating a FO from state 0 to n incrementally would generate the original sequence S. Depending on the structure of S, other labelled factors links as forward transitions might be created, as well as some backward transitions called suffix links with no label.

The factor and suffix links in FO have direct structural interpretations. A factor link going from state i to j indicates that a (variable length) history of symbols immediately before i is a common prefix of the sequence of symbols leading to j. A Suffix link from state m to an earlier state k indicates that the two states share the longest suffix. A suffix link goes from i to j if and only if the longest repeated suffix of s i 1 is recognized in j, connecting repeated patterns in S. The length of each repeating factor for each suffix link can be computed in linear time and denoted as lrs(i) for each state i. This property of suffix links alone make FOs attractive on large sequences. Figure 2a shows schematically how maximum length repeated factors are interconnected by suffix links. The thickness of the chunks represents the length of the repeated factor. Following each suffix link from the head of a Factor Oracle structure to the very beginning provides a forest of disjoint tree structures whose roots are the smallest and leftmost patterns appearing in the trees, thus capturing all redundancies inside the sequence. Figure 2b shows these linked trees associated to fig. 2a. To extend Factor Oracles to music information geometry, symbols σ i are replaced by models and symbolic equivalence to similarity as in definition 2 on bijected and symmetric D J F . Following figure 2, by learning audio structures we are interested in suffix links and their corresponding lengths. Figure 3 visualizes the learned structures of the Oracle on a recording of Beethoven's first piano sonata, 3 rd movement performed by Friedrich Gulda (recorded in 1950s). In this example, data points are constant-Q power spectrum on logarithmic musical scales as reported in [START_REF] Purwins | Constant q profiles for tracking modulations in audio data[END_REF] with an analysis window of approximately 64ms and an overlap factor of 2. Using these histogram features, the corresponding Bregman geometry is that of KL divergences. The information threshold for the CuSum algorithm is set to 0.15 and the similarity threshold ǫ for Oracle to 0.1. The three subplots show the audio waveform, the suffix structure, and the length of repeating sequence lrs associated to each state respectively. The suffix subplot is read as follows: A time t on the x-axis would send a pointer back to a time t ′ (t ′ < t) indicating the longest common suffix between a factor at time t and t ′ . The corresponding value for t on the lrs subplot reveals the length of the detected longest sequence (as number of states) for that state. In this example, we have superposed the reference structure in terms of labelled blocks taken from explicit repetitions in the music score. In the classical music example of figure 3, the music goes through various structural repetitions and recombinations which are mostly captured by the Oracle structure. Such repetitions in the context of a human performance of a piece of music are never exact, but nevertheless detected. This sample comprises an audio stream of 9500 analysis frames that leads to 440 learned models and states. Given this structure, we can construct a traditional similarity matrix by substituting each found suffix link by its corresponding distance or sim(i, j) = D J F (µ i , µ j ) given that a suffix link exist between i and j or zero otherwise. Figure 4a shows this similarity matrix constructed out of the Oracle in figure 3 revealing the recall and similarity structure discussed above.

To compare, figure 4b provides a classical frame-based selfsimilarity matrix over the same audio (and same features), in common use in the MIR literature and as proposed in [START_REF] Foote | Media segmentation using selfsimilarity decomposition[END_REF]. Roughly, this measure is obtained by calculating the distance between all analysis frames of the entire audio against each other, using the same distortion. By segmenting the audio stream into quasi-stationary states and using symbolic equivalence rather than a distortion, figure 4a can be obtained more efficiently and online where 4b requires the entire audio. The similarity described in figure 4a

B. Similarity Queries over Information Streams

We showed in the previous section how long-term information flows can be easily captured using our information geometric framework. In this section we showcase the idea of finding the most similar stream paths on a stream database given a query. This problem is usually addressed under the topic of audio matching. Once again, the goal here is not to compare to all existing methods but to showcase the ease of algorithmic programming once the problem set is projected onto an information geometric framework.

Given a stream query X t represented as a succession of models B k X (µ, R k ), and a target stream in T as well represented by its successive Bregman balls B j T , the problem of finding the best match of X t within T can be reduced to finding the best sequence of balls in T that best constructs the ball sequence in X t . The problem then can be formulated as a regular Approximate Nearest Neighbor search algorithm with special considerations for temporal continuity between balls. Given the compact state-space representation presented in the previous section, and given its inherent temporal and disjoint tree structures as shown in figure 2b, it would be natural to choose this data structure instead of a regular ball-tree (such as in [START_REF] Cayton | Fast nearest neighbor retrieval for bregman divergences[END_REF]) for the search domain representation. Following an Oracle representation on the target for a sequential search has the advantage of providing results with best perceptual continuity once synthesized since they correspond to natural continuations and regularities in the original audio.

Bregman Ball sequence matching between a source (query) and target can be achieved using dynamic programming and following discussions in section IV-D. At the initialization, the program chooses the most similar balls to B 1 X over all balls in T , resulting into the next search domain by choosing all factor and suffix links from the found states following the Oracle of T . This process is then repeated until either we reach the end of query B T X or an empty set is found during recursion. This simple dynamic programming scheme is able to trace multiple paths in a single run and provides partial matches where possible. The result is a concatenative tree structure on the target balls that are able to reconstruct X t balls.

Figure 5 shows the resulting Concatenative tree for an audio query corresponding to Beethoven's Piano Sonata Nr.1's first musical theme (corresponding to the model sequence in Figure 1) and the entire Piano sonatas Oracle ball sequence obtained as in section V-A. This experiment was done using a similarity threshold of ǫ = 0.1. Each numbered state represents a Bregman ball in the target domain T . The tree reconstructs the query from left to right by following existing arrows. Among possible reconstruction paths, the path highlighted with gray corresponds to the original theme of the exact construction of the query (balls 1 to 37), which is naturally expected. Parallel to this main path, two rather continuous and alternative paths exist consisting of states 169 to 202 and 460 to 511. These paths correspond to the repetition of the main musical theme in the middle and the end of the Piano Sonata which is a main characteristic of Sonata form in classical music. Other sub-paths also correspond to reappearance of the main theme in one form or another during the development section of the sonata form. The explosion of states around time 11 and towards the end correspond to a specific model that is representing a cadential chord which re-appears in various places throughout the piece as an important stylistic element.

A given path of the concatenative tree result can be easily re-synthesized to audio by concatenating corresponding audio frames of data points within each model (ball) using classical concatenative synthesis techniques [START_REF] Schwarz | Corpus-based concatenative synthesis[END_REF]. For more audio results we encourage the reader to check our project website.

VI. CONCLUSION

We proposed a preliminary framework for representation of temporal dynamics of audio streams on an information manifold. The construction of our information manifold approaches a similarity metric space where similarity is defined as control over the rate of change of information content between continuous data streams, and requires modeling the data streams as points on an information manifold generated by a family of exponential distributions. The music information geometry framework presented of section IV, provides an alternative representation of data points by incrementally gathering quasistationary data points within Bregman balls that represent self-contained models in terms of statistical information. The music information geometry in theory provides the following facilities: (1) representation of audio entities as well-behaved geometric objects with intuitive geometric properties, (2) sim- plifies optimization problems thanks to duality, (3) provides an approximate similarity metric space, bridging the gap between continuous and symbolic aspects of audio streams, (4) fast, sparse and incremental treatments suitable for data stream analysis, and (5) provides a generic mathematical framework extensible to more intricate models and applications.

The major intent of this paper was to lay the theoretical groundwork for forthcoming experimental results and hopefully, for other researchers interested in exploring the new possibilities offered by methods of information geometry on audio streams. We however showcased two common and complex MIR applications using the proposed framework. The promising sample results demonstrate the intuitive manner by which complex problems can be addressed within the proposed information geometry framework, and the facility to access information entities in our framework similar to symbolic processing. Further aspects and applications of music information geometry will be reported in future publications.

The study of audio streams as information geometries provide a new and challenging way to address complex problems with rather simple solutions. Besides its theoretical merit, we believe that its solutions brings out new horizons to the applications of multimedia information retrieval.

Fig. 1 .

 1 Fig. 1. Segmentation result on the first theme of Beethoven's first sonata, performed by Friedrich Gulda with λ = 0.1.

Fig. 2 .

 2 Fig. 2. The Suffix structure and Suffix Link forest of disjoint trees.

Fig. 3 .

 3 Fig. 3. Incrementally learned Oracle structure along with the segmented structure in terms of blocks from the orignal symbolic music score; Beethoven's Piano Sonata 1-movement 3, interpreted by Friedrich Gulda.

  also gives explicit access to equivalent entities and continuations over time through the structure of figure 3, whereas the similarity matrix of fig 4b requires further processing to deduce such relations. Furthermore, the classical similarity matrix contains exhaustive basis (9500 × 9500 versus 440 × 440 in fig 4a) for processing.

Fig. 4 .

 4 Fig. 4. Structural Similarity matrix using structural segmentation on the music example of figure 3 using two different kernel values.

Fig. 5 .

 5 Fig. 5. Audio Matching concatenative tree result on Beethoven's Piano Sonata Nr.1-Mvt.1 (target) and the first musical theme as query -Showing possible audio reconstruction paths and best path highlighted in light-gray.

TABLE

http://imtr.ircam.fr/imtr/Music Information Geometry