Benoit Gaüzère
email: benoit.gauzere@ensicaen.fr

Luc Brun
email: luc.brun@greyc.ensicaen.fr

Didier Villemin
email: didier.villemin@ensicaen.fr

Two New Graph Kernels and Applications to Chemoinformatics

Keywords: edit-distance, graph kernel, chemoinformatics

Chemoinformatics is a well established research field concerned with the discovery of molecule's properties through informational techniques. Computer science's research fields mainly concerned by the chemoinformatics field are machine learning and graph theory. From this point of view, graph kernels provide a nice framework combining machine learning techniques with graph theory. Such kernels prove their efficiency on several chemoinformatics problems. This paper presents two new graph kernels applied to regression and classification problems within the chemoinformatics field. The first kernel is based on the notion of edit distance while the second is based on sub trees enumeration. Several experiments show the complementary of both approaches.

Introduction

Chemoinformatics aims to predict or analyse molecule's properties through informational techniques. One of the major principle in this research field is the similarity principle, which states that two structurally similar molecules should have similar activities and properties. The structure of a molecule is naturally encoded by a labeled graph G = (V, E, µ, ν), where the unlabeled graph (V, E) encodes the structure of the molecule while µ maps each vertex to an atom's label and ν characterizes a type of bond between two atoms (single, double, triple or aromatic).

A first family of methods introduced within the Quantitative Structure-Activity Relationship (QSAR) field is based on the correlation between molecule's descriptors such as the number of atoms and molecule's properties (e.g. molecule's boiling point). Vectors of descriptors may be defined from structural information [START_REF] Cherqaoui | Use of a neural network to determine the boiling point of alkanes[END_REF], physical properties or biological activities and may be used within any statistical machine learning algorithm to predict molecule's properties. Such a scheme allows to benefit from the large set of tools available within the statistical machine learning framework. However, the definition of a vector from a molecule, ie. a graph, induces a loss of information. Moreover, for each application, the definition of a vectorial description of each molecule remains heuristic.

A second family of methods, based on graph theory may be decomposed in two sub families. The first sub family [START_REF] Poezevara | Discovering emerging graph patterns from chemicals[END_REF], related to the data mining field, aims to discover sub graphs with a large difference of frequencies in a set of positive and negative examples. The second sub family [START_REF] Brun | Symbolic learning vs. graph kernels: An experimental comparison in a chemical application[END_REF], more related to the machine learning field, builds a structural description of each class of molecule so that the classification is conducted by mean of a structural matching between each prototype and a graph representation of an input molecule. Both sub families are however mainly restricted to the classification field.

Graph kernels can be understood as symmetric graph similarity measures. Using a semidefinite positive kernel, the value k(G, G ′ ) where G, G ′ encode two input graphs corresponds to a scalar product between two vectors ψ(G) and ψ(G ′ ) in an Hilbert space (this space is only a Krein space if the kernel is non definite). Graph kernels provide thus a natural connection between structural pattern recognition and graph theory on one hand and statistical pattern recognition on the other hand. A large family of kernels is based on the definition of a bag of patterns for each graph and deduces graph similarity from the similarity between bags. Kashima [START_REF] Kashima | Kernels for graphs[END_REF] defines graph kernels based on the comparison of sets of walks extracted from each graph. Ramon and Gärtner [START_REF] Ramon | Expressivity versus efficiency of graph kernels[END_REF] and Mahé [START_REF] Mahé | Graph kernels based on tree patterns for molecules[END_REF] define kernels using an infinite set of tree patterns instead of walks. These methods improve the limited expressiveness of linear features such as walks hence providing a priori a more meaningful similarity measure. Instead of decomposing graphs into an infinite set of substructures (ie walks or trees), Shervashidze and Borgwardt [START_REF] Shervashidze | Efficient graphlet kernels for large graph comparison[END_REF] compute the kernel from the distribution of a predefined set of subgraphs, called graphlets. An other approach to the definition of graph kernels is proposed by Neuhaus and Bunke [START_REF] Neuhaus | Bridging the gap between graph edit distance and kernel machines[END_REF]. This approach aims to define definite positive kernels from the notion of edit distance. The main challenge of this approach is that the edit distance does not fulfill all requirements of a metric and hence does not readily lead to a definite positive kernel.

This paper presents two new kernels: A first kernel, presented in Section 2, combines graph edit distance and graph Laplacian kernel notions in order to obtain a definite positive graph kernel. A method to update efficiently this kernel is also proposed. Our second kernel, presented in Section 3, uses a different approach based on an explicit enumeration of subtrees within an acyclic unlabeled graph. The efficiency and complementarity of these two kernels is finally demonstrated in Section 4 through experiments.

Kernel from Edit Distance

An edit path between two graphs G and G ′ is defined as a sequence of operations transforming G into G ′ . Such a sequence may include vertex or edge addition, removal and relabeling. Given a cost function c(.), associated to each operation, the cost of an edit path is defined as the sum of its elementary operation's costs. The minimal cost among all edit paths transforming G into G ′ is defined as the edit distance between both graphs. A high edit distance indicates a low similarity between two graphs while a small one indicates a strong similarity.

According to Bunke and Neuhaus [START_REF] Neuhaus | Bridging the gap between graph edit distance and kernel machines[END_REF], the computational cost of the exact edit distance grows exponentially with the size of the graphs. Such a property limits the computation of exact edit distance to small graphs. To overcome this problem, Bunke and Riesen [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF] defined a method to compute a sub optimal edit distance. This method computes an approximate edit distance in O(nv 2 ) where n and v are respectively equal to the number of nodes and to the maximal degree of both graph.

Unfortunately, edit distance doesn't define a metric and trivial kernels based on edit distance are not definite positive. Neuhaus and Bunke [START_REF] Neuhaus | Bridging the gap between graph edit distance and kernel machines[END_REF] proposed several method to overcome this important drawback, however the proposed kernels are not explicitly based on the minimization problem addressed by kernel methods. Such a minimization problem may be stated as follows: Given a kernel k and a dataset of graphs D = {G 1 , . . . , G n }, the Gram matrix K associated to D is an n × n matrix defined by K i,j = k(G i , G j ). Within the kernel framework, a classification or regression problem based on K may be stated as the minimization of the following formula on the set of real vectors of dimension n:

f * = arg min f ∈R n CLoss(f, y, K) + f t K -1 f (1)
where CLoss(., ., .) denotes a given loss function encoding the distance between vector f and the vector of known values y.

As denoted by Steinke [START_REF] Steinke | Kernels, regularization and differential equations[END_REF], the term f t K -1 f in equation 1 may be considered as a regularization term which counter balance the fit to data term encoded by the function CLoss(., .). Therefore, the inverse of K (or its pseudo inverse if K is not invertible) may be considered as a regularization operator on the set of vectors of dimension n. Such vectors may be considered as functions mapping each graph of the database to a real value. Conversely, the inverse (or pseudo inverse) of any semi definite positive regularization operator may be considered as a kernel. We thus follow a kernel construction scheme recently introduced [START_REF] Brun | Symbolic learning vs. graph kernels: An experimental comparison in a chemical application[END_REF] which first builds a semi definite positive regularization operator on the set of functions mapping each graph {G 1 , . . . , G n } to a real value. The inverse, or pseudo inverse of this operator defines a kernel on the set {G 1 , . . . , G n }.

In order to construct this regularization operator, let us define a n × n adjacency matrix W defined by

W ij = e -d(G i ,G j ) σ
, where d(., .) denotes the edit distance and σ is a tuning variable. The Laplacian of W is defined as l = ∆ -W where ∆ is a diagonal matrix defined by: ∆ i,i = n j=1 W i,j . Classical results from spectral graph theory [START_REF] Chung | Spectral graph theory[END_REF] establish that l is a symmetric semi definite positive matrix whose minimal eigenvalue is equal to 0. Such a matrix is thus not invertible. To overcome this problem, Smola [START_REF] Smola | Kernels and regularization on graphs[END_REF] defines the regularized Laplacian l of W as l = I + λl where λ is a regularization coefficient. The minimal eigen value of l is equal to 1 and the matrix l is thus definite positive. Moreover, given any vector f , we have :

f t lf = f 2 + λ n i,j=1 W ij (f i -f j ) 2 (2)
Intuitively, minimising equation 2, leads to build a vector f with a small norm which maps graphs with a small edit distance (and thus a strong weight) to close values. Such a constraint corresponds to the regularization term required by equation 1 in order to smoothly interpolate the test values y over the set of graphs {G 1 , . . . , G n }. Our un normalized kernel, is thus defined as:

K un = l-1 .
Note that a regularized normalized Laplacian kernel may alternatively be considered by introducing the matrix L = ∆ -1 2 l∆ -1 2 . We have in this case, for any vector f :

f t Lf = n i=1 f 2 i ∆ ii + λ n j=1 W ij ∆ ii ∆ jj (f i -f j ) 2
The matrix L is definite positive and its associated kernel is defined as K norm = L-1 . Note that, our regularized normalized Laplacian kernel is not defined as the inverse of the regularized normalized Laplacian I +λ∆ -1 2 l∆ -1 2 . This new formulation is consistent with the regularization constraint which should be added to equation 1 and provides significant advantages in the context of incoming data (Section 2.1).

Incoming Data

Let us first consider a kernel defined from the un normalized Laplacian. Given our learning set D = {G 1 , . . . , G n }, the test of a new graph G within a regression or classification scheme requires to update the un normalized Laplacian l with this new graph and to compute the updated kernel defined as the inverse of the regularized and un normalized Laplacian K = (I + λl) -1 . This direct method has a complexity equal to O((n + 1) 3 ), where n is the size of our data set. Such a method is thus computationally costly, especially for large datasets. In this section, we propose a method to reduce the complexity of this operation.

Given the regularized and un normalized Laplacian ln = (I n + λ(∆ n -W n )) defined on the dataset D, its updated version ln+1 defined on D ∪ {G} may be expressed as follows:

ln+1 = ln -δ n B B t 1 -i B i where B = (-λexp( -d(G,Gi) σ
)) i={1,...,n} is deduced from the weights between the new input graph G and each graph (G i ) i={1,...,n} of our dataset and δ n is a diagonal matrix with (δ n ) i,i = B i .

The minimal eigen value of ln+1 is equal to 1 (Section 2). This matrix is thus invertible, and its inverse may be expressed using a block inversion scheme:

K un = ( ln+1 ) -1 = Γ Θ Λ Φ with        Γ = E -1 + ΦE -1 BB t E -1 Θ = -E -1 BΦ Λ = -ΦB t E -1 Φ = (1 -i B i -B t E -1 B) -1 (3)
where E = lnδ n . Note that Φ corresponds to a scalar. The computation of our new kernel, using equation 3, relies on the computation of the inverse of the matrix E = ln + δ n which may be efficiently approximated using a development to the order K of (I -l-1

n δ n ) -1 : ( ln -δ n ) -1 = l-1 n (I -l-1 n δ n ) -1 ≈ K k=0 l -k-1 n δ k n ( 4
)
Such a sum converges since l-1 n δ n 2 < 1, for λ < 1. Indeed:

l-1 n δ n 2 ≤ l-1 n 2 δ n 2 ≤ δ n 2 ≤ λ max i=1,n exp( -d(G, G i ) σ )
The last term of this equation is strictly lower than one for any λ lower than one. Moreover, basic matrix calculus show that the approximation error is lower than ǫ for any K greater than:

log(2ǫ) log(max i=1,n exp( -d(G,Gi) σ )) . (5)
Equation 4 allows to approximate the inverse of ( lnδ n ) by a sum of pre computed matrices l -k-1 n multiplied by diagonal matrices. Using such pre calculus, the inverse of ( lnδ n ) and hence the computation of our new kernel may be achieved in KN 2 .

If we now consider the regularized normalized Laplacian (Section 2) L = ∆ -1 2 l∆ -1 2 , its inverse is defined as:

L-1 = ∆ 1 2 l-1 ∆ 1 2
and we have:

K norm = ∆ 1 2 K un ∆ 1 2 (6)
The update of the regularized and normalized Laplacian kernel may thus be deduced from the one of the regularized un normalized Laplacian kernel.

Treelet Kernel

Kernels based on edit distance rely on a direct comparison of each pair of graph. An alternative strategy consists to represent each graph by a bag of patterns and to deduce the similarity between two graphs from the similarity of their bags. This strategy may provide semi definite kernels hereby avoiding the necessity to regularize the whole gram matrix for each incoming data (Section 2.1). As mentioned in Section 1, most of kernels of this family are based on linear patterns (bags of paths, trails or walks). Shervashidze et al. [START_REF] Shervashidze | Efficient graphlet kernels for large graph comparison[END_REF] describe a method to enumerate for any input unlabelled graph, all its connected subgraphs composed of up to 5 nodes. This efficient method provides up to 2048 patterns composed of connected subgraphs (called graphlets) of size lower or equal to 5. We propose here to adapt this method to the enumeration of sub-trees of acyclic unlabeled graphs up to size 6. The resulting patterns are called treelets (Fig. 1).

G 0 G 1 G 3 G 4 G 5 G 6 G 8 G 9 G 10 G 11 G 12 G 2 G 7 G 13
Fig. 1. Acyclic and unlabeled graphlets of maximum size equals to 6. Centers of 3-star and 4-star are surrounded

Computing Embedded Distribution

Following [START_REF] Shervashidze | Efficient graphlet kernels for large graph comparison[END_REF], our enumeration of all treelets starts by an enumeration of all paths with a length lower or equal to 6. A recursive depth first search with a max depth equals to 6 from each node of the graph is thus performed. Note that using such an enumeration each path is retrieved from its two extremities and is thus counted twice. In order to prevent this problem, each path composed of at least two nodes is counted 1 2 times. With this first step, the distribution of treelets G 0 , G 1 , G 2 , G 3 , G 5 and G 8 is computed (Fig. 1).

To compute the distribution of the remaining treelets, our method is based on the detection of nodes of degree 3 and 4. These nodes are respectively called R 3-star and R 4-star and are the center of the 3-star and 4-star treelets. Note that a 4-star treelet (G 7 ) contains four 3-star treelets (Fig. 2). This first degree analysis allows to compute the distribution of treelets G 4 and G 7 . Treelets G 6 , G 9 , G 10 and G 12 are enumerated from the neighbourhood of 3-star treelets. For example, treelet G 6 requires a 3-star with at least one neighbour of R 3-star with a degree greater or equal to 2. Treelet G 11 is the only sub tree derived from a 4-star. Properties characterizing treelets with a 3 or 4 star are summarized Table 1. Conditions characterizing treelets derived from 3-star and 4-star. N (v) and d(v) denote respectively the set of neighbours and the degree of vertex v.

Treelet Source treelet Condition

G6 3-star |{v; v ∈ N (R3-star); d(v) ≥ 2}| ≥ 1 G9 3-star |{v; v ∈ N (R3-star); d(v) ≥ 2}| ≥ 2 G10 ∃v0 ∈ N (R3-star); d(v0) ≥ 2 and 3-star |{v; v ∈ N (v0) -{R3-star}; d(v) ≥ 2}| ≥ 1 G11 4-star |{v; v ∈ N (R4-star); d(v) ≥ 2}| ≥ 1 G12 3-star |{v; v ∈ N (R3-star); d(v) ≥ 3}| ≥ 1
Fig. 3. Three permutations of G9 sharing the same core.

in Table 1. Note that treelet G 12 is symmetric since it contains two centers of 3-star. Such a treelet will thus be counted twice (once from each of its 3-star) and must be counted for 1 2 . Note that conditions summarized in Table 1 define necessary conditions for the existence of a given treelet centered around a 3 or 4 star. However, such conditions does not guarantee the uniqueness of such a treelet. Fig. 3 shows such an example: the rightest node of G 9 has a degree equals to 4 within the input graph whereas a degree greater or equal to 2 is required to define treelet G 9 . Three different treelet G 9 may thus be built from the same five nodes. This configuration thus induces to count G 9 three times from the graph represented in Fig. 3(a) One may easily check that no isomorphism exists between treelets depicted in Fig. 1. Moreover, has shown by Read [START_REF] Read | Some recent results in chemical enumeration[END_REF], the number of different alkanes composed of up to 6 carbons is equal to 13. Within our context, an alkane may be considered as an unlabeled acyclic graph whose vertex degree is bounded by 4. Therefore, treelet G 13 which is the only treelet with a vertex of degree greater than 4 does not corresponds to a feasible alkane. The remaining 13 treelets in Fig. 1 represents, up to isomorphisms, all the unlabeled acyclic graphs whose size is lower than 6 and whose vertex degree is bounded by 4. Adding G 13 to this set provides all unlabeled acyclic graphs with a size lower than 6.When all treelets from a graph G have been enumerated, a vector representing treelet distribution is computed. Each component of this vector, denoted the spectrum of G, is equal to the frequency of a given treelet in G:

f i (G) = |(G i ⊂ G)| (7)
Table 2. Comparison of addition methods.

Method

Classification Accuracy KMean [START_REF] Suard | Kernel on bag of paths for measuring similarity of shapes[END_REF] 80% (55/68) KWMean [START_REF] Dupé | Tree covering within a graph kernel framework for shape classification[END_REF] 88% (60/68) Trivial Similarity Kernel from Edit Distance [START_REF] Neuhaus | Bridging the gap between graph edit distance and kernel machines[END_REF] 90% (61/68) Normalized Standard Graph Laplacian Kernel (Eq. 6) 90% (61/68) Normalized Fast Graph Laplacian Kernel (Eq. 6) 90% (61/68) Random Walk Kernel [START_REF] Vishwanathan | Graph Kernels. Neural Networks[END_REF] 82% (56/68)

Definition of Treelet Kernel

A first idea to define a kernel from treelets consists to perform the inner product of vectors encoding the spectrum of graphs. Unfortunately, the inner product doesn't highlight spectrum similarities. For example, two graphs with nearly equal spectrum but with a low number of occurrences for each treelet are considered as less similar than two graphs having a same high number of treelet G 0 (ie same size) but a distribution of others treelets highly dissimilar. We thus use RBF kernels in order to better highlight differences between two spectra:

k T reelet (G, G ′ ) = N k=0 e -(f k (G)-f k (G ′ )) 2 σ ( 8
)
where σ is a tuning variable used to weight the differences between treelet distribution and N is the number of enumerated treelets. Our kernel may thus be considered as a basic RBF kernel between two vectors and is hence definite positive.

Experiments

Our first experiment evaluates the graph Laplacian kernel on a classification problem. This problem is defined on the monoamine oxidase dataset(MAO) 1 which is composed of 68 molecules divided into two classes: 38 molecules inhibits the monoamine oxidase (antidepressant drugs) and 30 does not. These molecules are composed of different types of atoms with simple bonds and are thus encoded as labeled graphs. Classification accuracy is measured for each method using a leave one out procedure with a two-class SVM. This classification scheme is made for each of the 68 molecules of the dataset. Table 2 shows results obtained by graph Laplacian kernel using approximate graph edit distance [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF] with node substitution and edge deletion costs set to 1 and edge substitution cost set to the sum of incident node substitution costs. Graph Laplacian kernel methods obtain a classification accuracy of 90% which 1 All databases in this section are available on the TC15 Web page: http://www.greyc.ensicaen.fr/iapr-tc15/links.html#chemistry corresponds to the highest score. Note that the other method obtaining 90% of classification accuracy is also based on the edit distance. This last kernel may however be non definite positive. We may additionally notice that the use of our fast inversion method (Section 2.1) does not modify graph Laplacian kernel's classification accuracy (Table 2, lines 4 and 5). The number of iterations required by this fast inversion method is determined by equation 5. Our experiments performed on the MAO database show that a value of ǫ equal to 10 -4 induces a maximum of 9 iterations hence allowing to update the gram matrix in O(9N 2 ) instead of O(N 3 ) using a standard matrix inversion method. The low value of N on this dataset (N = 68) does not induce an important gain on execution time since the average time to update a Gram matrix using method described in Section 2.1 is 0.273ms on the MAO database while this time is equal to 0.498ms using a direct inverse matrix computation. The ratio between both execution times is nevertheless about 1.8 hence showing a significant gain. Our treelet kernel is not tested against this database since this kernel is devoted to unlabeled graphs.

Our second experiment is based on a database of alkanes [START_REF] Cherqaoui | Use of a neural network to determine the boiling point of alkanes[END_REF]. An alkane is an acyclic molecule solely composed of carbons and hydrogens. A common encoding consists to implicitly encode hydrogen atoms using the valency of carbon atoms. Such an encoding scheme allows to represent alkanes as acyclic unlabeled graphs. The alkane dataset described in [START_REF] Cherqaoui | Use of a neural network to determine the boiling point of alkanes[END_REF] is composed of 150 molecules, associated to their respective boiling points. Using the same protocol than [START_REF] Cherqaoui | Use of a neural network to determine the boiling point of alkanes[END_REF], we evaluate the boiling point of each alkane using several test sets composed of 10% of the database, the remaining 90% being used as training set.

Table 3 shows results obtained by different methods. Poor results obtained by graph Laplacian kernel can be explained by the lack of information when dealing with unlabeled graphs. Indeed, using such graphs, the heuristic used to approximate graph edit distance [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF] maps the set of vertices of both graphs using uniquely the degree of vertices. Such a method thus consider several mappings as equivalent if several vertices with a same degree exist in both graphs. In this case, the sub optimal graph edit distance induces a poor graph discrimination. This lack of local information within unlabeled graphs also explains the poor results obtained by Kmean and random walk kernels. Indeed, these kernels are based on linear structures which are only discriminated by their lengths within unlabeled graphs. On the other hand, treelet kernel (with σ = 0, 25) outperforms previous results of [START_REF] Cherqaoui | Use of a neural network to determine the boiling point of alkanes[END_REF] based on neural networks combined with chemical descriptors.

Conclusion

In this paper we proposed a graph Laplacian kernel based on a sub optimal graph edit distance combined with an efficient update of the kernel in order to predict relevant properties of incoming data. Our experiments show the efficiency of this kernel on databases composed of complex molecules with several hetero atoms. However, this kernel performs poorly on unlabeled graphs. We thus propose a new kernel based on treelet enumeration for unlabeled acyclic graphs. This kernel outperforms results obtained by state of the art methods on this dataset but remains restricted to unlabeled graphs. Our future work will be devoted to overcome this last limitation by extending treelet kernel to labeled graphs.

Fig. 2 .

 2 Fig. 2. G7 contains 4 G4.

Table 3 .

 3 Boiling point prediction on alkane dataset.

	Method	Average error (C) Standard deviation (C) Correlation
	Neural Network [2]	3.11453	3.69993	0.9827
	KMean [15]	4.65536	6.20788	0.9918
	Random Walk Kernel [16]	10.6084	16.2799	0.9057
	Graph Laplacian Kernel	10.7948	16.4484	0.9412
	Treelet Kernel	1.40663	1.91695	0.9992


Frédéric Bimbot
email: frederic.bimbot@irisa.fr

Emmanuel Deruty
email: emmanuel.deruty@gmail.com

Gabriel Sargent
email: gabriel.sargent@irisa.fr

Emmanuel Vincent
email: emmanuel.vincent@inria.fr

METHODOLOGY AND RESOURCES FOR THE STRUCTURAL SEGMENTATION OF MUSIC PIECES INTO AUTONOMOUS AND COMPARABLE BLOCKS

Keywords: music structure, annotation, MIR structure musicale, annotation, recherche d'information dans les contenus musicaux

The approach called decomposition into autonomous and comparable blocks specifies a methodology for producing music structure annotation by human listeners based on a set of criteria relying on the listening experience of the human annotator. The present article develops further a number of fundamental notions and practical issues, so as to facilitate the usability and the reproducibility of the approach.

We formalize the general methodology as an iterative process which aims at estimating both a structural metric pattern and its realization, by searching empirically for an optimal compromise describing the organization of the content of the music piece in the most economical way, around a typical timescale.

Based on experimental observations, we detail some practical considerations and we illustrate the method by an extensive case study. We introduce a set of 350 songs for which we are releasing freely the structural annotations to the research community, for examination, discussion and utilization.

INTRODUCTION

Given its numerous applications, the automatic inference of musical structure is a key subject in MIR [START_REF] Paulus | Audio-based music structure analysis[END_REF], which has been focusing significant research effort in the past years [START_REF] Peeters | Deriving Musical Structures from Signal Analysis for Music Audio Summary Generation: Sequence and State Approach[END_REF][START_REF] Abdallah | Theory and evaluation of a Bayesian music structure extractor[END_REF][START_REF] Goto | A Chorus Section Detection Method for Musical Audio Signals and Its Application to a Music Listening Station[END_REF][START_REF] Paulus | Music structure analysis by finding repeated parts[END_REF][START_REF] Peeters | Sequence Representation of Music Structure Using Higher-Order Similarity Matrix and Maximum-Likelihood Approach[END_REF][START_REF] Levy | Structural Segmentation of musical audio by constrained clustering[END_REF][START_REF] Kelly | Locating tune changes and providing a semantic labelling of sets of Irish traditional tunes[END_REF][START_REF] Weiss | Identifying Repeated Patterns in Music Using Sparse Convolutive Non-Negative Matrix Factorization[END_REF][START_REF] Kaiser | Music structure discovery in popular music using non-negative matrix factorization[END_REF]. It has also triggered several studies [START_REF] Peeters | Is Music Structure Annotation Multi-Dimensional ? A Proposal For Robust Local Music Annotation[END_REF][START_REF] Bimbot | Decomposition into autonomous and comparable blocks : a structural description of music pieces[END_REF] and projects [13,[START_REF]SALAMI Project[END_REF] supporting this research with the investigation of methodological issues and the collection of annotated data.

In this context, the structural description approach called decomposition into autonomous and comparable blocks was recently introduced [START_REF] Bimbot | Decomposition into autonomous and comparable blocks : a structural description of music pieces[END_REF] in terms of general concepts, inspired from structuralism and generativism. It has been designed to be applicable to a wide range of "conventional" music, including pop music.

The present paper develops further this approach, with the purpose of providing a more practical annotation methodology, so as to facilitate the usability and the reproducibility of the process. We also present the current state of our annotation effort, namely 350 pop songs, for which we are releasing freely the structural annotations to the research community.

PROBLEM STATEMENT 2.1 Levels of musical organisation

It is commonly agreed that the composition and the perception of music pieces rely on simultaneous processes which vary at different timescales. Similarly to [START_REF] Snyder | Music and Memory[END_REF], we consider the three following levels corresponding to three different ranges of timescales :

• the low-level elements which correspond to fine-grain events such as notes, beats, silences, etc... We call this level the acoustic level and its time scale is typically below or around 1 second.

• the mid-level organization of the musical content, based on compositional units such as bars or hyper-bars or on perceptual units such as musical cells and phrases, ranging typically between 1 and 16 seconds. We will refer to this level as the morpho-syntagmatic level.

• the high-level structure of the musical piece, which describes the long term regularities and relationships between its successive parts, and which we will call the level of the semiotic structure, typically at a time scale around or above 16 seconds.

The figure of section 6 provides an illustration of these three levels. Note that we use the term semiotic in a quite restricted scope, (compared for instance to that of Nattiez [START_REF] Nattiez | Musicologie générale et sémiologie[END_REF]) as denoting the high-level symbolic and metaphoric representation of musical content1 .

Semiotic structure

What we consider as the semiotic structure of a music piece is something that may look like :

A B C D E F B C D E G D E D E H
thus reflecting :

1. some sort of high-level decomposition/segmentation of the whole piece into a limited number of blocks (here 16 blocks) of comparable size, and 2. some form of similarity or equivalence relationship between blocks bearing identical labels (here, 8 distinct symbols)

Providing a semiotic description for a music piece requires primarily the identification of the most adequate granularity (block size and number of blocks) which then conditions the inventory of labels.

From the example below, choosing a finer granularity could lead to a sequence of labels such as :

AA'BB'CC'DD'EE'FF'BB'CC'DD'EE'GG'DD'EE'DD'EE'HH'
where any symbol X is systematically followed by symbol X, therefore yielding a rather redundant semiotic description. Conversely, a coarser granularity would require either the uneven grouping of the units into irregular segments (i.e. of more diverse sizes) :

A BC DE F BC DE G DE DE H
or a very misleading representation such as :

AB CD EF BC DE GD ED EH

which completely hides the similarities existing between portions of the piece which had identical labels at a lower scale. This example thus illustrates a simple case where there exist clearly a preferable granularity at which the semiotic level of the music piece can be described with some form of optimal compromise between :

• The minimality of the set of labels

• The informativeness of the sequence of labels

• The regularity of the block size

The goal of this work is to present a set of methodological principles for :

1. identifying the most appropriate granularity for describing the semiotic structure, and 2. locating as univocally as possible the corresponding block boundaries.

In this article, the granularity referred to in item 1 is defined as the structural metric of the music piece and the actual borders of the segmental units (item 2) as the realization of the structural meter.

The proposed process relies on the listening of music pieces, but can be extended to music in written form (scores). However, note that scores may not be available and sometimes are even meaningless w.r.t. the type of musical content under consideration.

BASIC CONCEPTS

Definitions

As exposed in the previous section, the hypothesis of this work is that the semiotic structure of "conventional" music pieces is built on structural blocks, characterized by the content of their musical layers. One of the aim of semiotic structure annotation is therefore to locate the block boundaries (with the convention that they are synchronized with the first beat of a bar). We call size the dimension of the blocks relative to a snap scale proportional to that of the beat (see 3.3).

We call structural metric pattern, the underlying high-level organization of the musical content which is the most adequate for representing economically the semiotic level, and we assume that block boundaries rest on the (potentially irregular) realization of that structural metric pattern. The annotation task thus consists in jointly inferring the structural metric pattern and its realization.

Musical information layers

Even though this is a simplified view of reality, we consider that a piece of music is characterized by 4 main reference properties, potentially evolving over time2 :

• intensity (amplitude / sound level)

• tonality/modality (reference key and scale)

• tempo (speed / pace of the piece)

• timbre (instrumentation / audio texture)

We also consider that a piece of music shows 4 main levels of temporal organization :

• rhythm (relative duration and accentuation of notes)

• melody (pitch intervals between successive notes)

• harmony (chord progression)

• lyrics (linguistic content and, in particular, rhymes) These levels of description form 8 musical layers 3 .

Because of their cyclic properties in conventional music, the levels of temporal organization are central to the determination of block boundaries, in our approach. Indeed, as explained in section 4.1, we assume that block boundaries coincide with the convergence of cyclic behaviors taking place simultaneously in the 4 levels of temporal organization.

On the opposite, blocks may globally differ in terms of intensity, tonality, tempo or timbre but these properties may happen to change within a block without corresponding to a structural boundary.

Block size

A primary property of blocks is their size, which we describe in a custom unit that we call snap, and which is defined as the number of times a listener would snap his fingers to accompany the music, at a rate which is as close as possible to 1 bps (beat per second). As opposed to the beat (which is a compositional notion), the snap is a perceptual unit.

Although we may come to consider the blocks from a variety of perspectives during their identification, their ultimate description will be their size in snaps. The definition of the snap requires further consolidation, since a tempo-invariant unit would be desirable. However, an evolution of the definition of the snap would not affect the structural segmentation per se, as the snap is only a measure of the block size.

Structural metric pattern

A fundamental assumption of the proposed method is based on the hypothesis that the semiotic structure can be described in reference to a structural metric pattern, i.e. a prototypical partition of the beat or the snap scale. As an example, a very common structural metric pattern is the repetition of blocks of 16 snaps (structural pulsation period Ψ = 16).

The high-level structure of the music piece is governed by the structural meter but actual semiotic blocks result from the realization of the structural meter and this realization may lead to blocks of irregular size. For example, even if the structural period of a piece is equal to 16, the size of some blocks may deviate from the prototypical value (for instance, 18). We develop further the fact that, in a large number of cases, irregular blocks can be reduced to regular stems that conform to the structural metric pattern.

The structural metric pattern is analogous to the bar, but operates at a higher level : whereas the bar is the organizational entity of low-level elements such as beats and notes, the structural metric pattern governs the organization of mid-level elements (bars, cells, phases, etc...).

ANNOTATION CRITERIA AND NOTATION

Detection of cycles (syntagmatic analysis)

In conventional music, the various temporal organization layers tend to show (quasi-)cyclic behaviors, which we define as the recurrent return of the considered layer to some specific state or set of states4 . For instance, rhythmic patterns generally show a short-term recurrence which participates to the mid-level organization of the music piece, melodies tend to return to tonic or to exhibit particular intervals (depending on the piece), specific chords sequences conclude harmonic progressions (cadences), etc... We consider that, in conventional music pieces, there exist time instants for which the 4 levels of temporal organization exhibit some phase convergence towards their respective ends of cycles, which creates identifiable cues of the piece structure. In other words, block boundaries should correspond to some form of recurrent convergence of all levels of temporal organization.

These instants of convergence take very versatile forms, as they can be signaled in the music content by very diverse combination of structuring cues, such as a particular rhythmic pattern combined with the return to a specific note or chord, the completion of a system of rhymes in the lyrics the conclusion of a carrure and a recurrent sound effect... Even though these cues and their combinations are partly conventional (at least within a particular music genre), they generally vary from one piece to another and their identification is part of the empirical analysis conducted by the annotator.

In our approach, cyclicity plays a central role for identifying structural blocks through the 2 ensuing properties :

1. iterability : structural blocks can be looped to yield a consistent (larger) musical stream 2. suppressibility : structural blocks can be skipped in the music piece without creating the perception of a discontinuity in the remaining musical stream Indeed, if one thinks of a periodic signal, each period can be repeated indefinitely and can be removed from the signal without disrupting seriously the organization of the remaining signal. This generalizes conceptually to quasi-cyclic processes, as defined above.

The property of cyclicity gives a founded ground for the syntagmatic definition of structural blocks. It establishes more clearly the criterion formerly based on the preservation of "musical consistency" [START_REF] Bimbot | Decomposition into autonomous and comparable blocks : a structural description of music pieces[END_REF] and also brings additional substance to the concept of Constitutive Solid Loop [START_REF] Peeters | Is Music Structure Annotation Multi-Dimensional ? A Proposal For Robust Local Music Annotation[END_REF].

The listener's ability to identify iterable and suppressible segments in the music piece is a key point in the proposed analysis and it does not require the annotator to be able to express in musicological terms the actual properties of the structuring cues.

When necessary, the analysis can be complemented by an explicit designation of the structuring cues, but attention must be paid that these cues should not be expected to be univocally associated to blocks boundaries : all structuring cues are not systematically observed at all segment borders and some cues can also be observed within block boundaries.

Detection of similarities (paradigmatic analysis)

The identification of actual block boundaries is further (or, in practice, simultaneously) carried out by performing paradigmatic analysis on the musical content, for reinforcing and disambiguating the set of candidate borders hinted by the detection of cyclic segments.

It consists in searching for "repeating" patterns across the musical content, which are identical, similar or, more generally speaking, easy to explain economically relative to one another (for instance, transposition, level of instrumental support, addition of a melodic motif, insertion of a musical segment, ...).

As for the syntagmatic analysis of section 4.1, the locations of such paradigms do not coincide univocally with block boundaries : they only constitute additional cues of such boundaries.

Note that the paradigmatic analysis performed at this stage calls for similar processes to those that are needed for labeling the segments. However, whereas the labeling stage requires the determination of a global system of contrasts between segments, the extraction of paradigmatic structural cues simply requires pairwise comparisons of musical segments for the only purpose of identifying and locating candidate blocks.

Regularity and reduction

For many conventional music pieces, it can be assumed that a majority of blocks within the piece have a comparable size in snaps, hence corresponding to some structural pulsation period (Ψ). Blocks whose size is equal to the structural pulsation period are called regular blocks.

Some blocks have a smaller size than Ψ, which can generally be interpreted as corresponding to a shortened realization of a regular block. This is especially true for half-size target segments, which can often be matched with the first or second half of a regular block observed somewhere else in the piece. Alternatively such blocks may be considered as a half realization of the structural metric (this is often the case for pre-chorus and bridges).

In a significant number of cases, blocks are longer than the structural period. However, in these cases, they can often be reduced into a stem of size Ψ and an affix. An affix is a subset of snaps which can be viewed as having been inserted into a (regular) stem and affixes are therefore suppressible from the original block (but not necessarily iterable), i.e. the stem forms, on its own, an admissible block. If the insertion of the affix takes place at the beginning (resp. at the end) of the block, it is called a prefix (resp. suffix).

Affixes are particularly easy to identify and locate within a block when there exist, somewhere else in the song, another block which corresponds to the realization of the stem alone. But sometimes, the stem has to be hypothesized based on more subtle considerations, because it is not attested alone in the piece (but, for instance, with a different affix).

Frequent examples of suffixes are observed when for instance a block is extended by lengthening the last snap over 2 more snaps (resulting in some form of break), by doubling the duration values of the notes on the last 2 snaps of the block or by repeating the last 4 snaps twice (thus rendering an insistence effect). Affixes within blocks can be more tricky to detect, and may take versatile forms, for instance the repetition of a p-snap segment, a tonal excursion of a few snap or a segment with totally different properties from the rest of the block.

By convention, prefixes and suffixes should be of maximum size equal to half of that of the block (preferably strictly less) and they should not alter the harmonic valence of the block, i.e. the harmonic properties at the block boundaries.

Structural metric pattern notation

To describe the structural metric pattern, we use the following notation : n a constant stem size of n snaps throughout the piece {n 1 , n 2 } 2 stem sizes in the piece, n 1 and n 2 , occurring in any order but in decreasing frequency (can be generalized to more than 2 values) (n 1 , n 2 ) a systematic alternation of stem sizes n 1 and n 2 , starting with n 1 (can be generalized to more than 2 values)

These notations are superscripted with a star (n * , {n1, n2} * , etc...), if the piece contains only within-blocks irregularities, or very few short blocks considered by the annotator as non-representative of the dominant structure of the piece (in particular, in intros, outros, re-intros, etc...). If relevant, the annotator can combine further the notations, for instance {16, (12, 8)}, but these needs are quite exceptional...

In conventional pop music, the most common segmental structure is m x 16 * (m being the number of blocks, which is itself usually close to 16), but pieces from the genre blues have usually block sizes based on 24 snaps. More complex patterns such as {16, 12}, [START_REF] Nattiez | Musicologie générale et sémiologie[END_REF][START_REF] Kelly | Locating tune changes and providing a semantic labelling of sets of Irish traditional tunes[END_REF] or [START_REF] Nattiez | Musicologie générale et sémiologie[END_REF][START_REF] Nattiez | Musicologie générale et sémiologie[END_REF][START_REF] Kelly | Locating tune changes and providing a semantic labelling of sets of Irish traditional tunes[END_REF] happen to be observed.

Block size notation

Following are the corresponding notation conventions which we use to designate the size of (realized) blocks, in reference to a structural pulsation period of n snaps: Undeterminable size (usually owing to a lack of snap)

[p + n]
Sometimes, two structural blocks may overlap over p snaps, which we call block tiling. This is the case when the realization of a new block starts while the previous blocks is still p snaps before its final boundary and continues in the meantime (for instance, in canons). It is also the case when some snaps function simultaneously as the end of a given block and the beginning of the next one. The notation convention for tiling situations is :

[n -p [p] p + n].
Note that the internal structure of blocks could be further specified by decomposing the block size into sub-blocks according to paradigmatic properties within the block (for instance 4x4 as the internal structure of a size 16 block), but this goes beyond the scope of the current paper.

GENERAL METHODOLOGY

Annotation process

Based on the notions introduced in the previous section, the annotation of a music piece X can be understood as an (empirical) joint estimation task, namely the determination of :

• The most likely structural metric pattern (M ) for the piece.

• The most likely decomposition of the piece into a set of blocks (S), i.e. the realization of M .

In practice, the annotator proceeds iteratively as follows :

1. hypothesize a structural period Ψ, or (more generally) a structural metric pattern M from the listening of X.

2. (attempt to) decompose X into blocks following M , by introducing, if and only if necessary, irregularities (affixes, irregular blocks) so as to satisfy cyclicity of blocks and to maximize similarities across blocks (resp. sections 4.1 and 4.2).

3. consider possible alternatives to Ψ or M .

4. if such alternative(s) seem to be worth considering, return to step 2 and test the new hypothesis.

Collection des Publications Internes de l'Irisa c IRISA

The understanding of step 2 is crucial to the proposed methodology : at that stage, the annotator is actually trying to estimate the realization of M via the minimization of the necessary distortion that M should undergo to make it match the properties of the actual musical content of X. Ultimately, among various hypotheses for M and the corresponding decompositions, the annotator retains that which seems globally more economical for describing the semiotic level, i.e. the solution which results in a satisfactory compromise between :

• the simplicity and typicality of the structural metric,

• the regularity of the decomposition,

• the non-redundancy of successive blocks,

• the closeness of the structural period(s) to a reference value (currently set to 15 seconds).

Hypothesizing the structural metric pattern

A priori properties and typical values

Previous work has put forward arguments based on the "Predictive Information Context" (PIC) which suggest that the a priori most economical decomposition of a music piece into structural units is based on segments whose typical length would be equal to the square root of the length of the piece.

In an annex to this paper, we propose complementary considerations based on information theory concepts, which strengthen this point.

As a consequence of this property, we assume that structural blocks of a size approximately equal to the square root of the length of the piece happen to be a reasonable initial assumption when looking for possible hypothesis of the structural pulsation period. However, the actual analysis of the musical content may lead to a final (a posteriori) result which deviates significantly from this starting point.

Numerically, on the basis of an average song length of 240 seconds and a snap value around 1 s, n = √ N falls in the range of 15.5 s, which is roughly the typical duration of blocks used so far as target value in our annotations.

With a snap around 1 second, the size of a block will therefore typically be of 16 snaps. Here again, this property should only be considered as a priori hypothesis (the one to start with).

From these consideration, a canonical model which summarizes all the a priori can be laid down : it consists in 16 blocks of 16 snaps of 1 s each. For a given piece, the structural metric pattern and its realization are thus searched as the minimal deviation from this canonical model, which enables a structural description compatible with the musical content.

Estimating plausible snap ans structural period(s)

By definition, the snap is the multiple of the beat corresponding to a duration as close as possible (in logarithmic scale) to 1 s (in fact, it usually corresponds to the downbeat, but not always). Therefore, identifying the snap is, in general, rather straightforward from the listening of parts of the piece, preferably away from the beginning or the end, which may exhibit particular beat and tempo properties. Depending on the type of bar, admissible intervals for the snap are : [0.71, 1.41] for binary bars and [0.58, 1.73] for ternary ones (for more complex, odd bars, the snap can be unevenly alternating between different numbers of beats).

Once the snap is determined, plausible values of the structural pulsation period(s) are hypothesized by listening to the piece and considering in priority the most salient and steady parts of the piece : typically the chorus (if any), the developments of recurring motifs or phrases, the parts of the piece perceived as relatively homogeneous, etc... From these segments, the annotator can generally infer rapidly one or two plausible values of pulsation period(s), from which he/she will start a more comprehensive analysis of the entire musical material of the piece, looking for particular patterns and locating irregularities.

As a consequence of the central role played by the canonical model, the value of 16 is usually investigated in priority, unless obvious evidences in the musical content directs the annotator towards another hypothesis (for instance, 24 in many pieces of blues). Segments IV, VII, XII and XIII present a clear paradigmatic relationship (they are easy to qualify as the chorus of this piece). Three of them last 18 snaps but XII lasts only 16 snaps and can be considered as the stem on which the three other blocks are built by lengthening the harmonic content over the last 2 snaps.

A CASE STUDY

Segments II, V, X form a second paradigm, with the return to tonic as a clear (conventional) structuring cue. Being of size 16, they are in line with the Ψ = 16 hypothesis. An alternative hypothesis would be to consider them as the repetition of 2 almost identical (half-)blocks of 8 snaps, but i) this would need the introduction of a second structural period and ii) no occurrence of such a half-block alone is observed in the song and iii) it would split the rhyming pattern of block V.

Segments III, VI and XI constitute a third paradigm. Their raw form amounts for 14 snaps, but they can be described as a 4x4 snap carrure of the abab type, whose last quarter has been truncated of the last 2 snaps, hence the notation 16 -2. This comforts (or at least does not contradict) the hypothesis Ψ = 16.

Segments I and IX are very similar, I being an instrumental intro of 16 snaps and IX the second half of I, used as an instrumental bridge (hence the notation -8 + 16). Finally, VIII is a solo, which conveniently lasts exactly 16 snaps.

The segmental structure of the piece is therefore considered to be 13 x 16 * , i.e. a basic 16-snap pattern realized 13 times with a few within-block irregularities. Alternative options could have been 25 x 8 * , but this would introduce much redundancy in the underlying semiotic description, since almost all segments would be observed in systematical pairs, without bringing significantly down the number of irregular segments (only IX would thus become regular). A pattern such as (16, 14, 18) * could be envisaged given the recurrence of this particular size sequence in II-III-IV and V-VI-VII but the existence of XII as a 16-snap realization of the chorus just in between XI and XIII makes this complicated alternative a non-sustainable option.

CORPUS DESCRIPTION 7.1 RWC Pop set

Part of the available annotations is composed of the 100 Pop songs from the RWC database [17], written and produced for research purposes. Their structural annotations have been released and used last year for the MIREX 2010 evaluation [START_REF][END_REF] in structural segmentation and they are currently under minor revision. The average length of songs in this corpus is approximately 4 minutes. A subset of 55 titles contains several pieces from the same artists (The Beatles : 9, Eric Clapton : 7, Pink Floyd : 7, Queen : 7, The Cure : 6, Jedi Mind Tricks : 5, D Angelo : 4, ACDC : 2, Eminem : 2, Madonna : 2, Plastikman : 2, Shack : 2) and the remaining 59 titles correspond to 59 other distinct artists. In this corpus, a large range of music genres is covered but the vast majority of artists are American or English. Eurovision songs have the particularity of being limited to a 3'00" maximum duration by the rules of the contest, and they tend to show other properties (including their structure) influenced by the contests format and its target public. These titles however cover a variety of languages and a diversity of sub-genres within European pop music.

RWC

Eurovision set

Ongoing effort

At the time of writing this paper, we are finalizing the annotation of the RWC Genre database (100 titles). We have also planned to annotate a new set of 50 titles for the Quaero project and will complete the current effort by an additional set of 12 titles, so as to reach, together with the already achieved annotations, a total of 500 annotated titles by the end of the summer 2011.

Release

All the aforementioned annotations will gradually be made available online before September 2011 at : http://musicdata.gforge.inria.fr and a number of them will be accompanied with comments as case studies (such as in section 6), so as to document the annotation method.

Figure 1

 1 Figure1illustrates the analysis of song Genre 08 from the RWC database[17]. Structural blocks are depicted both as their span on the x-axis (time in snap) and their height on the y-axis (in log scale). Each block is identified by a distinct roman number.The duration of the song file is 3'26" (including initial and final silences) and the size of the actual song in snap is 200 (snap duration almost exactly equal to 1 s). The following observations are based on the listening of the music piece.

Figure 1 :

 1 Figure 1: RWC Genre 08 annotation levels

The

  Eurovision set is currently composed of 124 titles, corresponding to the songs which participated to the semi-finals and/or the final in years 2008, 2009 and 2010, in their studio version (as recorded on the "official" albums) :

  The Quaero set is composed of 114 titles which have been selected by IRCAM and used in the Quaero project[13] for the evaluation of music structure detection algorithms :

	Pop		100 titles
	7.2 Quaero set
	Quaero 2009	Development set	20 titles
	Quaero 2009	Evaluation set	49 titles
	Quaero 2010	Evaluation set	45 titles
	Total		114 titles

We thus avoid the term semantic, referring to the musical meaning of objects (for instance, chorus, verse, etc) : such a notion falls completely outside the scope of this paper.Collection des Publications Internes de l'Irisa c IRISA

In previous work, we identified

reference properties only, but we consider now that intensity should also be part of the list.Collection des Publications Internes de l'Irisa c IRISA

These layers may not all be active simultaneously and some additional layers may be observed in some music pieces.

Note that cyclic does not necessarily mean periodic, the latter being a stronger property. For example, the zero-crossing of a sequence of values form a set of cycles which may not be periodic.Collection des Publications Internes de l'Irisa c IRISA

Collection des Publications Internes de l'Irisa c IRISA

CONCLUSIONS

The work presented in this paper constitutes a contribution towards the general strategic goal of disseminating consistent and re-usable resources for research and development in MIR. It also contributes to the objective of converging towards operational concepts for the description of music structure, through the definition of the structural metric pattern, and a consistent annotation procedure. Together with the production of additional resources, our current work direction is to consolidate the connections between music structure description and information theory, so as to encompass a wider range of concepts and, in particular, to integrate several timescales in the structural description.

ANNEX

Let's consider a song represented as a sequence of discrete elements at a given time-scale X = {x k } 1≤k≤N and let's now consider a bi-dimensional organization of X into blocks of size q, i.e. a m (lines) × n (columns) matrix representation of X :

with m = N/n and k = (i -1)n + j. Given this structure, the quantity of information needed to index all elements in the matrix requires :

Thus, the index of each line in the matrix X can be coded with log(m) bits, and the total number of bits required to index all lines in the matrix is m log(m) (the same applies for the columns, hence n log(n)). Seeking for the minimum of I n (by zeroing the derivative of I n w.r.t. n) yields n = √ N . Hence, in the absence of any particular knowledge concerning the redundancies in X, the most economical way to index it bi-dimensionally is to shape it as a square matrix structure.