Stanisław A Raczyński

Emmanuel Vincent

Genre-based music language modelling with latent hierarchical Pitman-Yor process allocation

Keywords: topic models, hierarchical Pitman-Yor process, Chinese restaurant process, musical genre recognition, music information retrieval, chord model, genre model

In this work we present a new Bayesian topic model: latent hierarchical Pitman-Yor process allocation (LH-PYA), which uses hierarchical Pitman-Yor process priors for both word and topic distributions, and generalizes a few of the existing topic models, including the latent Dirichlet allocation (LDA), the bigram topic model and the hierarchical Pitman-Yor topic model. Using such priors allows for integration of n-grams with a topic model, while smoothing them with the state-of-the-art method.

Our model is evaluated by measuring its perplexity on a dataset of musical genre and harmony annotations 3 Genre Database (3GDB) and by measuring its ability to predict musical genre from chord sequences. In terms of perplexity, for a 262-chord dictionary we achieve a value of 2.74, compared to 18.05 for trigrams and 7.73 for a unigram topic model. In terms of genre prediction accuracy with 9 genres, the proposed approach performs about 33% better in relative terms than genre-dependent n-grams, achieving 60.4% of accuracy.

I. INTRODUCTION

Probabilistic music models are means of incorporating prior knowledge about music into the algorithms used in music information retrieval (MIR). This is done by jointly modelling multiple musical variables (like notes, beats, etc.) with the goal of increasing the accuracy of estimating all of them [1]. These models have already been applied to such MIR problems as: composer identification [START_REF] Mauch | Discovering chord idioms through Beatles and Real Book songs[END_REF], [START_REF] Ogihara | N-gram chord profiles for composer style representation[END_REF], audio chord transcription [START_REF] Papadopoulos | Large-scale study of chord estimation algorithms based on chroma representation and HMM[END_REF]- [START_REF] Lee | A system for automatic chord transcription from audio using genre-specific hidden Markov models[END_REF] and symbolic chord transcription [START_REF] Yoshii | Unsupervised music understanding based on nonparametric Bayesian models[END_REF], [START_REF] Raczyński | Melody harmonisation with interpolated probabilistic models[END_REF], automatic harmonization [START_REF] Raczyński | Melody harmonisation with interpolated probabilistic models[END_REF]- [START_REF] Simon | MySong: automatic accompaniment generation for vocal melodies[END_REF], automatic composition [START_REF] Fukayama | Automatic song composition from the lyrics exploiting prosody of the Japanese language[END_REF], music segmentation [START_REF] Sargent | A regularity-constrained Viterbi algorithm and its application to the structural segmentation of songs[END_REF], [START_REF] Mauch | Using musical structure to enhance automatic chord transcription[END_REF] and polyphonic pitch estimation [START_REF] Yoshii | Unsupervised music understanding based on nonparametric Bayesian models[END_REF], [START_REF] Raczyński | Dynamic Bayesian networks for symbolic polyphonic pitch modeling[END_REF]. Music models are the MIR analogues of the language models that have been successfully used in the fields of natural language processing (NLP) and continuous speech recognition. The world of MIR is slowly adopting the language models for its own purposes: for example, the n-gram model is nowadays commonly used in MIR [START_REF] Ogihara | N-gram chord profiles for composer style representation[END_REF], [START_REF] Raczyński | Melody harmonisation with interpolated probabilistic models[END_REF]- [START_REF] Fukayama | Automatic song composition from the lyrics exploiting prosody of the Japanese language[END_REF], [START_REF] Mauch | Using musical structure to enhance automatic chord transcription[END_REF]. That simple model, however, does not take into account the fact that the characteristics of music differ between genres. A more flexible, genredependent model is therefore sought for. Genre-dependent ngram models have been proposed by Pérez-Sancho et al., who used a collection of n-gram models, one for each genre, for the purpose of musical genre recognition in [START_REF] Pérez-Sancho | Genre classification using chords and stochastic language models[END_REF]. The same genre-dependent n-gram model was also used by Lee in [START_REF] Lee | A system for automatic chord transcription from audio using genre-specific hidden Markov models[END_REF] This work was conducted while E. Vincent was with Inria Rennes and was supported by Inria under the Associate Team Program VERSAMUS (http: //versamus.inria.fr/). S. Raczyński is with Gdańsk Universit of Technology, Faculty of Electronics, Telecommunications and Informatics, ul. Narutowicza 11/12 Gdańsk (e-mail: staraczy@pg.gda.pl). E. Vincent is with Inria, 54600 Villers-lès-Nancy, France (e-mail: emmanuel.vincent@inria.fr).

for automatic chord transcription from audio. However, this approach does not account for any overlap between genres, that is the parameters of the n-grams are not shared between models.

In this work we propose to use topic models, known from the field of NLP, which allow documents to be mixtures of latent topics. The topics, contrary to the genres, which are fixed, adapt to the data, and different genres can share topics, so such a model can fit the data much closer. In a typical topic model each observed word (in our case: chord) is assumed to be generated from a topic-dependent distribution, and each document (in our case: song) defines a distribution over those topics. Later, for the purpose of genre recognition, we will further assume that the genres are mixtures of topics. The most basic probabilistic topic model is the latent Dirichlet allocation (LDA) proposed by Blei et al. in [START_REF] Blei | Latent Dirichlet allocation[END_REF], which was later generalised as the hierarchical Pitman-Yor topic model (HPYTM) [START_REF] Sato | Topic models with power-law using Pitman-Yor process[END_REF] and the bigram topic model (BTM) by Wallach in [START_REF] Wallach | Topic modeling: beyond bag-of-words[END_REF]. Topic models have already been used in MIR: Hu et al. used a simple LDA-based unigram topic model for unsupervised estimation of key profiles from symbolic music data in [START_REF] Hu | A probabilistic topic model for unsupervised learning of musical key-profiles[END_REF]. Spiliopoulou and Storkey derived a more complex n-gram-based topic model for probabilistic modelling of melodic sequences in [START_REF] Spiliopoulou | A Topic Model for Melodic Sequences[END_REF], however that method did not include advanced smoothing. Without smoothing, models with many degrees of freedom (for n-grams their number grows exponentially with the value of n) will overfit to the training data, i.e., they will have poor predictive power and perform poorly on test data [START_REF] Scholz | Robust modeling of musical chord sequences using probabilistic N -grams[END_REF].

In this work we propose a model that generalises all of the above models, that we refer to as latent hierarchical Pitman-Yor process allocation (LHPYA). LHPYA uses hierarchical Pitman-Yor process priors and is therefore capable of using n-grams and advanced smoothing with both the word and the topic posteriors. We evaluate our model by means of crossentropy calculated on chord sequences, which is a common method for language model evaluation [START_REF] Chen | An empirical study of smoothing techniques for language modeling[END_REF], and by applying it to chord-based musical genre recognition (MGR), which is one of the fundamental tasks in MIR. This paper is organised as follows. Section II introduces the LHPYA model, while Section III explains the inference procedure for this model. Symbolic evaluation using crossentropy is presented in Section IV and MGR results are discussed in Section V. Finally, a conclusion is given in Section VI.

II. LATENT HIERARCHICAL PITMAN-YOR PROCESS ALLOCATION

A. State-of-the-art n-gram and topic models

The currently most popular topic model is the LDA [START_REF] Blei | Latent Dirichlet allocation[END_REF], which is a Bayesian generalization of the probabilistic latent semantic analysis (PLSA) from [START_REF] Hofmann | Probabilistic latent semantic indexing[END_REF]. In topic modelling, each document j, where j = 1, . . . , J, is treated as a sequence of observed symbols w j,t from a dictionary W , indexed by i ∈ {1, . . . , |W |}, where t = 1, . . . , T is the position in the sequence. Typically the symbols w j,t correspond to words. In MIR they can be chords, pitches, rhythm words, etc., but in this work we focus on sequences of chords for illustration purposes. In LDA-like models, each document is modelled as a categorical distribution over K hidden topics z j,t . Each topic, in turn, defines a different categorical distribution over the observed symbols w j,t . The topic and symbol distributions are unknown and treated as random variables θ = {θ k,j } and φ = {φ i,k }:

P(z j,t = k|θ) = θ k,j , (1)
P(w j,t = i|z j,t = k, φ) = φ i,k . (2)
In LDA, the topic and symbol posteriors are given Dirichlet priors:

θ j ∼ Dir(αn), (3)
φ k ∼ Dir(βm), (4)
where α and β are the concentration parameters and n, m are normalized base measures (expected values of the distribution) and Dir() is the Dirichlet distribution (defined in the Appendix). Dirichlet priors are used because they are the conjugate priors to the categorical distribution, which greatly simplifies inference. LDA makes the so called bag-of-words assumption, which means that the order of the observed symbols does not matter. We know, however, that the order is very important in many cases. For chords, this order is called the chord progression and is an important genre discriminant [START_REF] Pérez-Sancho | Genre classification using chords and stochastic language models[END_REF]. This limitation of LDA can be removed by using better, contextual symbol distributions, such as the popular n-gram model. n-grams are already commonly used to model chord progressions with a context length of R = 1 [3]- [START_REF] Ueda | HMMbased approach for automatic chord detection using refined acoustic features[END_REF], [START_REF] Raczyński | Melody harmonisation with interpolated probabilistic models[END_REF]- [START_REF] Fukayama | Automatic song composition from the lyrics exploiting prosody of the Japanese language[END_REF], [START_REF] Raczyński | Dynamic Bayesian networks for symbolic polyphonic pitch modeling[END_REF] and R > 1 [6], [START_REF] Yoshii | Unsupervised music understanding based on nonparametric Bayesian models[END_REF], [START_REF] Pérez-Sancho | Genre classification using chords and stochastic language models[END_REF], [START_REF] Scholz | Robust modeling of musical chord sequences using probabilistic N -grams[END_REF].

The number of parameters that we need to train in the ngram models grows extremely quickly-with the power of n-which quickly results in overfitting. A common solution to deal with is to use smoothing [START_REF] Zhai | A study of smoothing methods for language models applied to ad hoc information retrieval[END_REF]. The best known ngram smoothing technique to date is the modified Kneser-Ney smoothing, which interpolates a high-order model with models of lower order and additionally introduces discounting [START_REF] Chen | An empirical study of smoothing techniques for language modeling[END_REF], [START_REF] Kneser | Improved backing-off for m-gram language modeling[END_REF]. This kind of model interpolation can also be achieved in a fully Bayesian framework, by using a hierarchy of Dirichlet processes (DPs) as the prior for the symbol distributions in [START_REF] Teh | Hierarchical Dirichlet processes[END_REF]. A Dirichlet process DP(d, γ, φ 0,k ), where γ the concentration parameter and φ 0,k is the base distribution, is a non-parametric generalisation of the Dirichlet distribution to infinite dimensionality. The additional discounting found in the Kneser-Ney smoothing can be obtained by replacing the DPs with Pitman-Yor processes (PYs) and in fact Teh has proven that the interpolated Kneser-Ney smoothing is only an approximation to his model, which is based on hierarchical PYs [START_REF] Teh | A hierarchical Bayesian language model based on Pitman-Yor processes[END_REF]. His model, called the hierarchical Pitman-Yor process language model (HPYLM), is a hierarchy of PYs, where the symbol distribution φ k,n for a context of length n is drawn from its parent distribution φ k,n-1 for the same context, but of length n -1:

φ k,n ∼ PY(d n , γ n , φ k,n-1 ), (5)
where d n are the discount parameters, γ n the strength parameters (which correspond to the concentration parameters of the DP) and n = 1, . . . , R. The unigram distribution, that is the distribution φ 0,k for an empty context, is drawn from the another PY:

φ 0,k ∼ PY(d 0 , γ 0 , U), (6)
where U(w j,t ) = 1 |W | stands for a uniform symbol distribution and |W | is the size of the symbol vocabulary.

The idea of using n-grams in topic models was already explored by Girolami and Kabán in [START_REF] Kaban | Simplicial mixtures of markov chains: Distributed modelling of dynamic user profiles[END_REF], who introduced a LDA-inspired Markov chain mixture model with Dirichlet priors over the mixing weights, but they did not use any smoothing. Later, in [START_REF] Wallach | Topic modeling: beyond bag-of-words[END_REF], Wallach replaced the Dirichlet symbol prior of the LDA with a hierarchical Dirichlet language model (HDLM) of bigrams, developed earlier by MacKay and Peto in [START_REF] Mackay | A hierarchical Dirichlet language model[END_REF], and experimented with what she called the BTM. The resulting model was limited to context lengths of R = 1. Later, Sato and Nakagawa proposed another extension of LDA with a unigram (R = 0) hierarchical PY symbol prior in [START_REF] Sato | Topic models with power-law using Pitman-Yor process[END_REF], but their formulation did not take into account the symbol order.

B. Proposed model

Since the proposed model is applied to chord sequences, we will refer to the word posterior as the "chord posterior" from now on. Our model extends the work of [START_REF] Sato | Topic models with power-law using Pitman-Yor process[END_REF], [START_REF] Wallach | Topic modeling: beyond bag-of-words[END_REF], [START_REF] Teh | A Bayesian interpretation of interpolated Kneser-Ney[END_REF] by placing hierarchical PYs (HPYs) on both the chord and the topic posteriors:

θ j ∼ PY(d 1 , γ 1 , θ 0 ), (7)
θ 0 ∼ PY(d 0 , γ 0 , V), (8) φ k,u(n) ∼ PY(d k,n , γ k,n , φ k,u(n-1) ), (9) φ k,u(0) ∼ PY(d k,0 , γ k,0 , U), ( 10
)
where V is a uniform topic distribution and u j,t (n) = (w j,t-1 , w j,t-2 , . . . , w j,t-n+1 ) is the context of the chord w j,t of size n -1 (u j,t (1) = ∅), i.e., the n -1 previous chords. Using HPYs for both distributions results in smoothing applied to both chord and topic posteriors. This model is visualised using the plate notation in Fig. 1. Setting the discount parameters to zero turns PYs into DPs and effectively disables discounting in the smoothing of the model parameters. If we further set R = 0 (unigrams) and set γ 0 and γ k,0 to zeros (then θ 0 → V and φ k,u(0) → U then our model will use additive (Laplace) smoothing and will therefore be equivalent to LDA with symmetric priors [START_REF] Zhai | A study of smoothing methods for language models applied to ad hoc information retrieval[END_REF]. Similarly, if we use R = 1 and no discounting, we will have the BTM model from [START_REF] Wallach | Topic modeling: beyond bag-of-words[END_REF].

III. INFERENCE

The key quantity one wants to infer from a topic model is the predictive distribution over a previously unseen test datum w (test) given the training corpus w. To obtain it, we need to integrate out all the latent variables: the latent training topics z, the test topics z (test) , the parameters: θ and φ and the hyper-parameters: d m , γ m , d k,n and γ k,n , where m = {0, 1}. This integration can be performed using an uncollapsed Gibbs sampler [START_REF] Sato | Topic models with power-law using Pitman-Yor process[END_REF], [START_REF] Teh | A hierarchical Bayesian language model based on Pitman-Yor processes[END_REF] akin to the collapsed Gibbs sampling approach used with LDA [START_REF] Wallach | Topic modeling: beyond bag-of-words[END_REF], [START_REF] Griffiths | Finding scientific topics[END_REF], [START_REF] Wallach | Evaluation methods for topic models[END_REF]. A Gibbs sampler samples from the joint distribution of all the variables by sequentially sampling each variable from its distribution conditioned on the values of all the others. The individual topics are drawn from the conditional distribution

P(z j,t |w, z ¬t , θ ¬t , φ ¬t ) ∝ P(z j,t , w j,t |z ¬t , w ¬t , θ ¬t , φ ¬t ), (11)
where ¬t = {1, 2, . . . , t -1, t + 1, . . . , T } is a set of time indices excluding the current time index t, while θ ¬t and φ ¬t are the topic and chord posteriors sampled for all data excluding that at t. The above distribution can be rewritten as a product of these two posteriors:

P(z j,t , w j,t |z ¬t , w ¬t , θ ¬t , φ k,¬t ) = P(w j,t |z j,t , z ¬t , w ¬t , φ k,¬t )P(z j,t |z ¬t , θ ¬t ) (12)
These can be sampled as seating arrangements in a corresponding Chinese restaurant with the t-th customer removed [START_REF] Teh | A hierarchical Bayesian language model based on Pitman-Yor processes[END_REF].

A. Chinese restaurant analogy

Chord unigram models can be drawn from the Pitman-Yor process using a procedure called Chinese restaurant process (CRP) [START_REF] Pitman | Combinatorial stochastic processes[END_REF]. A Chinese restaurant represents a sample of the chord posterior φ k,u(0) . There is one such restaurant for every topic k. Every restaurant consists of the seating arrangement of customers seated at an unbounded number of tables. Each arriving customer w j,t is randomly seated to a table and served the dish i assigned to this table (w j,t = i) that has been drawn independently from U (cf. [START_REF] Simon | MySong: automatic accompaniment generation for vocal melodies[END_REF]). In our case, we know what the customers are eating, but do not know their seating arrangement. By sampling the seating arrangement, we can use it to calculate a sample of the chord posterior. Similarly, topic posteriors can be represented by seating arrangements in restaurants that are serving topics k to customers z j,t .

The CRP technique can also be used for sampling in hierarchical Pitman-Yor processes, and therefore sampling for n-gram models, by introducing a hierarchy of restaurants [START_REF] Teh | A hierarchical Bayesian language model based on Pitman-Yor processes[END_REF], [START_REF] Teh | A Bayesian interpretation of interpolated Kneser-Ney[END_REF], [START_REF] Griffiths | Hierarchical topic models and the nested Chinese restaurant process[END_REF]. In this hierarchy, the child restaurant φ k,u(n) for the context u(n) and topic k is seating a customer, but also sending him/her to an appropriate parent restaurant φ k,u(n-1) .

In a Chinese restaurant sampling process, each arriving customer is seated either to an already occupied table with probability proportional to N p -d 0 , or to a new table, with probability proportional to M d 0 +γ 0 , where N p is the number of customers already eating at table p and M is the current number of occupied tables. We can sample the chord and topic posteriors by sequentially re-sampling the hierarchical seating arrangements, which is achieved by sequentially adding and removing customers to the hierarchy of restaurants. The chord posterior can be calculated recursively from the current seating arrangement in a hierarchy of chord-serving Chinese restaurants as

φ i,k,u(n) = N i,k,u(n) -d k,n L i,k,u(n) γ k,n + N k,u(n) + + γ k,n + d k,n M k,u(n) γ k,n + N k,u(n) φ i,k,u(n-1) , (13)
where L i,k,u(n) is the number of tables at which dish i is served in the restaurant for topic k and context u(n), N i,k,u(n) is the number of people eating this dish in that restaurant; M k,u(n) is the number of occupied tables in this restaurant and N k,u(n) is the total number of people in that restaurant. For the parameters, Teh described an efficient sampling scheme using auxiliary variables [START_REF] Teh | A Bayesian interpretation of interpolated Kneser-Ney[END_REF], which we adopt in our implementation, but the same results can be achieved using other samplers, e.g., slice sampling [START_REF] Wallach | Bayesian modeling of dependency trees using hierarchical Pitman-Yor priors[END_REF].

The hierarchical CRP sampling procedure for the proposed model is a straightforward adaptation of that proposed in [START_REF] Teh | A Bayesian interpretation of interpolated Kneser-Ney[END_REF]. It is outlined in Algorithm 1, while the functions for adding/removing customers and for calculating the posterior are detailed in Algorithm 2.

B. Hyper-parameters

This procedure assumes hyper-prior on the discount and strength parameters. As in [START_REF] Teh | A Bayesian interpretation of interpolated Kneser-Ney[END_REF], we place a beta hyper-prior on the discount parameters and a gamma hyper-prior on the strengths. The hyper-parameters are tied between all contexts u(n) of the same length for each topic k: Algorithm 1: The Gibbs sampler for LHPYA. s is the sample number, t is used to index the training data w, z and j (song numbers associated with each t) and τ to index the test data w (test) , z (test) and j (test) . C++-style notation is used: square brackets denote accessing an element of an array of restaurants and the full stop stands for invoking a method of an object (a restaurant). The italics denote variables, while the normal font functions and methods. The dot notation [ • ] stands for using the entire array. with

d k,n ∼ Beta( a k,n , b k,n ), (14)
γ k,n ∼ Gamma( ℵ k,n , k,n ), (15)
a k,n = a k,n + Q k,n q=1 M k,q -1 p=1 (1 -y q,p ), (16)
b k,n = b k,n + Q k,n q=1 i M k,q,i p=1 N k,q,p,i -1 j=1 (1 -z q,i,p,j ), (17)
ℵ k,n = ℵ k,n + Q k,n q=1 M k,q -1 p=1 y q,p , (18)
k,n = k,n - Q k,n q=1 log x q , (19)
where Q k,n is the number of restaurants with context length n -1 in topic k with at least 2 occupied tables, M k,q is the number of occupied tables in such a restaurant q, M k,q,i is the

(i) if n > 1 then return N i -dnL i γn+N + γn+dnM γn+N restaurants [u j,t (n -1)].DishProbability (i); else return N i -d 0 L i γ 0 +N + γ 0 +d 0 M γ 0 +N U(i); end
Algorithm 2: Methods of the Chinese restaurant class (Restaurant::) for chord-serving restaurants. The DishProbability() method directly implements [START_REF] Mauch | Using musical structure to enhance automatic chord transcription[END_REF]. The methods for topic-serving restaurants are analogous. number of tables in that restaurant serving dish i with at least 2 customers and N k,q,p,i is the number of customers sitting in that restaurant at table p eating dish i. The auxiliary variables are sampled as follows:

x q ∼ Beta(γ k,nq + 1, N q -1), (20)
y q,p ∼ Bernoulli( γ k,nq γ k,nq + d k,nq p ), (21)
z q,i,p,j ∼ Bernoulli( j -1 j -d k,nq ), (22)
where N q is the total number of customers in restaurant q and n q is the order of that restaurant. a k,n , b k,n , ℵ k,n and k,n are hyper-hyper-parameters, which we all set to 1, following our own experience and suggestions from [START_REF] Sato | Topic models with power-law using Pitman-Yor process[END_REF]. The same sampler is used for the hyper-parameters of the topic restaurants.

IV. SYMBOLIC EVALUATION

The proposed model was first evaluated by measuring the cross-entropy (its normalised log-likelihood) on unseen (test) data. We have used data from the 3GDB data set [START_REF] Pérez-Sancho | Genre classification using chords and stochastic language models[END_REF], [START_REF]3 Genre Database (3GDB)[END_REF], a collection of hand-annotated chord labels for 856 songs from 3 genres: popular, jazz and academic music. Each genre had been further divided into 3 sub-genres: blues, celtic and pop (popular), bop, pre-bop and bossa nova (jazz), and baroque, romanticism and classical (academic). Each song has been annotated with both absolute chord labels (C-maj, C -maj, etc.) and chord degrees (Roman numeral notation: I-maj, iimaj, etc.). We have used the chord degree data in all experiments, because that way we work with smaller dictionaries, diminishing somewhat the effects of data sparsity, and the model is independent of the key. The chords in 3GDB had been annotated with three levels of detail: full chord labels, triad-level chords (only the first two intervals of a chord) and dyad-level chords (only the first interval of a chord). The corresponding dictionary sizes (the numbers of distinct chord labels present in the database) were 262, 98 and 15. The entire collection of songs was divided in two equal-sized parts: the training and the test datasets.

A. Cross-entropy

The cross-entropy on the unseen (test) data w (test) is defined as [START_REF] Chen | An empirical study of smoothing techniques for language modeling[END_REF]:

H(w (test) ) = - 1 T log 2 P(w (test) |w). (23)
There are many possible methods for estimating the distribution over test data [START_REF] Wallach | Evaluation methods for topic models[END_REF] and here we chose to use the unbiased estimator from [START_REF] Newton | Approximate Bayesian inference with the weighted likelihood bootstrap[END_REF], which is the harmonic mean of distribution samples collected using the Gibbs sampler from the previous section:

P(w (test) |w) ≈ 1 S S s=1 P(w (test) |w, z s , z (test) s ) -1 -1 , (24)
where z s and z (test) s are training and test topic samples from the Gibbs sampler and S is the total number of collected samples. We have chosen the harmonic mean estimator for its simplicity, although Wallach et al. suggests it has tendencies for overestimation [START_REF] Wallach | Evaluation methods for topic models[END_REF].

Unsurprisingly, we found that the model is sensitive to initialisation, because the topic labels z are correlated with each other and the Gibbs sampler tends to get stuck in modes of the joint distribution. As a result, sampling the initial topic labels z s=0 from a uniform distribution resulted in a slightly different estimate of the cross-entropy each time. To minimise this variation, we initialised the topic assignments with the topics obtained with the Gibbs-EM algorithm used on the BTM from [START_REF] Wallach | Topic modeling: beyond bag-of-words[END_REF] (we have used "prior 2" from that paper).

Nevertheless, the convergence of the algorithm (to a quasistable distribution) is fast. In our experiments, we burned the Gibbs sampler in by sampling for only training data variables for B 1 = 500 samples before starting to sample all the test variables as well. We then waited another B 2 = 500 iterations before starting to collect S = 500 likelihood samples to calculate the cross-entropy. These values have been determined experimentally.

B. Results

Fig. 2 shows a plot of cross-entropies obtained by setting the number of topics to K = 1, i.e., for a smoothed n-gram model. For all chord label detail levels we observe a minimum at R = 2, after which the models slowly start to overfit to the data. In the following experiments we therefore focus on trigrams.

Cross-entropies for 3-grams and different number of latent topics are plotted in Fig. 3. The cross-entropy is decreasing quickly with the number of latent topics, until about K = 30 for dyads, where the model starts to overfit. The curves q q q q q q q q q q q q q q q q q q q q q q full triads dyads Fig. 3: Cross-entropies of the topic-based 3-grams, as a function of K, calculated on the test data for all three data sets.

for triads and full chord labels saturate at larger values of K because of higher data complexity, but do not decrease significantly above K = 60.

For full chord labels the minimal cross-entropy achieved is 1.45 bits per chord, for K = 57. Without the topic model, i.e., for trigrams, the cross-entropy is 4.17 bits and without the n-grams, i.e., with a unigram topic model we only achieve 2.95 bits for the optimal K = 120. The results are summarised in Table I, together with corresponding values of compression rate (calculated as the ratio of the crossentropy to the reference cross-entropy of the uniform model) and perplexity (calculated as 2 H(w (test) ) ). We can therefore conclude that the chordal context and the latent topics are both factors that significantly and independently reduce the uncertainty about predicted chords.

V. MUSICAL GENRE RECOGNITION

As a complementary way of evaluating the proposed model, we apply it to chord-based music genre recognition. Assigning TABLE I: Cross-entropy, as well as equivalent compression rates and perplexities obtained for three models, compared to the reference uniform model for full chords.

genre labels is a very common way of categorizing music [START_REF] Scaringella | Automatic genre classification of music content: a survey[END_REF] and harmony is one of the key discriminants of musical genre (at least in the Western tonal music). For instance, the harmonies of the baroque and classical periods are characterised by strict formalisms, while the more modern jazz music employs much more liberal, complex and dissonant chord progressions; at the same time the harmonies of pop music tend to be simplistic and repetitive, a good illustration of which is the commonly used pop-rock chord progression I-V-vi-IV. The majority of MGR methods use only the features extracted from audio signals [START_REF] Sturm | A survey of evaluation in music genre recognition[END_REF], mostly because this kind of data is readily available in large amounts. Few of them use extracted chord sequences [START_REF] Anglade | Genre classification using harmony rules induced from automatic chord transcriptions[END_REF], [START_REF] Lidy | A Cartesian ensemble of feature subspace classifiers for music categorization[END_REF]. However MGR based on such symbolic features is actually more likely to break the glass ceiling of MGR in the long term, because of the semantic information embodied by these features. Given a sample of the topic posteriors θ, the genre g for a previously unseen song j can be obtained as a maximum a posteriori estimate:

g = arg max g P(g|θ). (25)
We propose two ways to compute the genre posterior: using a generative approach and an approach based on naive Bayes classifiers.

A. Generative approach

In the generative approach, the genre is found as

g = arg max g S s=1 K k=1 P(g|z = k)P(z = k|θ s ), (26)
where z is a topic for this document, s indexes Gibbs samples of the topic posteriors, θ s is a sample of the topic posterior for this document θ s,k = P(z = k|θ s ) and

P (g|z = k) = P(g, z = k|z (training) ) P(z = k|z (training) ) . (27)

B. Naive Bayesian classifiers

Another approach is an approach using naive Bayesian classifiers: The most popular choice of a prior over categorical distributions (such as the topic posteriors) is the Dirichlet distribution. However, because the topic posterior density appears to be multimodal (see Fig. 4), we use Dirichlet mixtures [START_REF] Brown | Using Dirichlet mixture priors to derive hidden Markov models for protein families[END_REF]:

g = arg max g P(g|θ, Λ) = arg max g S s=1 P(θ s |g, Λ)P(g), (28)
P(θ s |g, Λ) = D d=1 λ d Dir(θ s ; ρ d ), (29)
where λ are the mixing coefficients and the Dirichlets are parameterised by K-element vectors ρ d . The mixture coefficients as well as the parameters of the Dirichlets can be found using the EM algorithm (detailed in the Appendix).

C. Results

Experiments were performed for all combinations of the parameters: the number of genres and sub-genres L ∈ {3, 9}, the number of topics K ∈ {3, 9, 12, 15, 18, 21, 24, 27, 30, 39, 48} and the context length R ∈ {0, 1, 2, 3, }. All three chord detail levels were used (dyads, triads, full chords) and 7 estimation methods: generative, and Dirichlet mixtures of 1, 2, 4, 6, 12 and 24 components. For every set of parameter values, topic posterior samples were collected with B 1 = 500, B 2 = 50 and S = 100 and this was performed 20 times, resulting in 2000 topic posterior samples per song. We have used the same division into training and test data as in the symbolic experiments.

The accuracy of musical genre estimation was calculated as the average over accuracies for each genre:

A = 1 L L g=1 N P g N T g , (30)
where N P g is the number of correctly identified songs for genre g and N T g is the total number of songs in that genre. Fig. 5 shows a plot of accuracies relative to the accuracy for dyads, for all values of L, K, R and all methods. We see that higher detail in chord descriptions translated to an accuracy (a) L = 3 q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0.9 Data set Accuracy relative to dyads (b) L = 9 q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 1.0 1.5 2.0 2.5 dyads triads full chord labels Data set Accuracy relative to dyads Fig. 5: Boxplot of accuracies obtained on the three data sets, relative to the dyad data set accuracy, for all combinations of K, R and estimation method. The boxes represent the ranges of the second and third quartiles.

higher by 20-30% on average, even for longer contexts. This suggests that the effect of the extra information about chords is stronger than that of overfitting the model by using larger vocabulary (which, given the smoothing in our model, should indeed be low). In the following discussion and plots we will therefore present data for full chord labels only.

Accuracies for full chord labels are visualised in Fig. 6. For L = 3, there is little difference between analysis methods if an optimal number of topics K is used (depicted by the bar tops), although mixtures of many Dirichlets are slightly better. For both L = 3 and L = 9 the best accuracy was generally obtained for R = 1 and R = 2, which confirms the observation from Fig. 2 that longer contexts do not improve the modelling power, at least for such a small data set. This is also consistent with the results presented in [START_REF] Pérez-Sancho | Genre classification using chords and stochastic language models[END_REF], [START_REF] Pérez-Sancho | Stochastic text models for music categorization[END_REF].

On the other hand, accuracy increases significantly for L = 9 if Dirichlet mixtures are used, by 40% in relative terms (17% absolute) compared to the generative approach. Furthermore, this time the highest accuracy is generally obtained for R = 2, so we can conclude that the context is more important in distinguishing between sub-genres than between genres.

Although there is quite some variance in the obtained accuracies (cf. Fig. 7), we were able to achieve a genre recognition accuracy of 88% for L = 3 and 60% for L = 9 for the mixture of 24 Dirichlets. As shown in Table II [START_REF] Pérez-Sancho | Genre classification using chords and stochastic language models[END_REF] and [START_REF] Pérez-Sancho | Stochastic text models for music categorization[END_REF] for the same data (degrees with extensions, full chord labels). * In the case of [START_REF] Pérez-Sancho | Genre classification using chords and stochastic language models[END_REF] the number of genres L was 8. than the results for n-grams reported both in [START_REF] Pérez-Sancho | Genre classification using chords and stochastic language models[END_REF] and [START_REF] Pérez-Sancho | Stochastic text models for music categorization[END_REF] by 33% in relative terms (15% absolute) and comparable to the naïve Bayesian classifier with multivariate Bernoulli distribution from [START_REF] Pérez-Sancho | Stochastic text models for music categorization[END_REF]. We do not report the results for hierarchical classifiers from [START_REF] Pérez-Sancho | Stochastic text models for music categorization[END_REF], because those used both harmony and melodic information. Fig. 7 shows the accuracies obtained for the best parameter values as a function of K. The same shape can be observed for all methods: the accuracy increases up to about 20-30 topics and then shows a slow decrease towards larger values of K. Additionally, Fig. 8 depicts the confusion matrices for K = 27 and the mixture of 24 Dirichlets. For L = 3 there is more confusion between popular and academic genres than between them and jazz, which is to be expected since jazz generally employs more complex harmonies, which makes it more distinct. It is more difficult to detect confusion patterns for L = 9, but most confusion is between closely related subgenres of the same genre, e.g., between bop and pre-bop or between baroque and romantic music.

VI. CONCLUSION

In this paper we have presented a new smoothed topic model using hierarchical Pitman-Yor process priors and applied it to prediction of chord sequences and to chord-based musical genre recognition. It integrates a topic model with word Fig. 6: Accuracies obtained for all analysis methods (marked on the horizontal axis) and values of R. Bars correspond to minimal, mean and maximal values over all K's for a particular method and value of R.

(chord) n-grams and is therefore capable of handling data for which the bag-of-words assumption does not hold, such as chord sequences, where progressions between chords, in addition to the chords themselves, contribute to discrimination between musical genres. Using topic models is more flexible than the previously proposed genre-dependent n-gram model by allowing both the songs and the genres to be mixtures of latent topics. Of course, the proposed model is not limited to modelling chords and it would be interesting to apply it to other musical sequences, such as pitches (e.g., melodies or voices), rhythm, etc.

In general, this model is potentially useful in all problems where topic models are used and the order of words matters, e.g. in text document modelling [START_REF] Wallach | Topic modeling: beyond bag-of-words[END_REF] or in genomic information analysis [START_REF] Rosen | Probabilistic topic modeling for genomic data interpretation[END_REF]. Fig. 8: Confusion matrices for best sets of parameters. Shades correspond to absolute counts of labelling an "actual genre" as a "predicted count". Marginal barplots show total counts for the actual and predicted genres. Additionally, the text labels show counts relative to the total number of songs for a particular actual genre (i.e., rows sum up to one)

Fig. 1 :

 1 Fig. 1: Plate notation for the proposed model. The hyperparameters are skipped. Variables on plates are repeated the number of times indicated on the plate.

Fig. 2 :

 2 Fig. 2: Cross-entropies for smoothed chord n-grams, calculated on the test data.

Fig. 4 :

 4 Fig. 4: A topic posterior distribution over a K-simplex for the 'romanticism' sub-genre, where K = 3, L = 9, R = 1 and full chord labels are used. Darker shades represent larger density. The distribution shows strong bimodality.

Fig. 7 :

 7 Fig. 7: Genre estimation accuracy as a function of the number of topics K for L = 3 (orange solid line) and L = 9 (black dashed line). A mixture of 24 Dirichlets was used with R = 1 and R = 2, respectively.

  (a) L = 3, R = 1, K = 27, L = 9, R = 2, K = 27, 24 Dirichlets

  (test) ); for s ← 1 to S do for j ← 1 to J do for t ← 1 to T do if s > 1 then chordTrainingRestaurants [z j,t , u j,t (n)].RemoveCustomer (w j,t ); topicTrainingRestaurants [j].RemoveCustomer (z j,t ); for k ←1 to K do φ w j,t ,k,¬t = chordTrainingRestaurants [k, u j,t (n)].DishProbability (w j,t ); θ j,k,¬t = topicTrainingRestaurants [j].DishProbability (k); end z j,t = SampleCategorical (φ w j,t ,¬t θ j,¬t ); end chordTrainingRestaurants [z j,t , u j,t (n)].AddCustomer (w j,t ); topicTrainingRestaurants [j].AddCustomer (z j,t );

	Initialise (z);
	Initialise (z end
	UpdateHyperparameters (topicTrainingRestaurants [•]);
	for k ← 1 to K do
	UpdateHyperparameters (chordTrainingRestaurants [k,•]);
	end
	for τ ← 1 to T end
	topicTestRestaurants [jτ ].AddCustomer (zτ );
	end
	UpdateHyperparameters (topicTestRestaurants [•]);
	end
	end

(test)

do if s > 1 then topicTestRestaurants [jτ ].RemoveCustomer (zτ ); for k ←1 to K do φ wτ ,k,¬τ = chordTrainingRestaurants [k, uτ (n)].DishProbability (wτ ); θ jτ ,k,¬τ = topicTestRestaurants [jτ ].DishProbability (k); end zτ = SampleCategorical (φ wτ ,¬τ θ jτ ,¬τ );

  , this is better

	L	Proposed	[15]		[43]
			n-grams	Bayes	n-grams	Bayes
	3	89.0%	84.8%	85.3%	86 ± 3%	86 ± 4%
	9*	60.4%	45.3%	48.4% 38 ± 12%	62 ± 6%

TABLE II :

 II The best accuracies obtained by the proposed method and the accuracies cited in the reference work by Pérez-Sancho et al. in

A. Learning Dirichlet mixtures

The Dirichlet distribution is defined as [START_REF] Minka | Estimating a dirichlet distribution[END_REF]:

where ρ is a vector of K parameters and the normalising constant is defined as

where Γ() is the gamma function.

The parameters of the Dirichlet mixture model can be found by maximising their likelihood on a set of topic posterior samples collected for songs from a particular genre. In order to find these estimates we need to integrate out the latent mixture component selector variables v j , so we will use the EM algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF]. The parameter likelihood is given by

where I(v j , d) is a binary indicator function that is equal to one iff v j = d and otherwise equal to zero.

B. E-step

The expected value of the log-likelihood function is given by

where l indexes iterations of the EM algorithm. We define

Then

C. M-step

The expectation function Q is a sum of terms that depend on different parameters, so we can maximize each of them separately:

where Ψ is the digamma function. The new ρ can therefore be found as [START_REF] Minka | Estimating a dirichlet distribution[END_REF]: