12th International Society for Music Information Retrieval Conference (ISMIR 2011)

A VOCABULARY-FREE INFINITY-GRAM MODEL
FOR NONPARAMETRIC BAYESIAN CHORD PROGRESSION ANALYSIS
Kazuyoshi Yoshii
Masataka Goto
National Institute of Advanced Industrial Science and Technology (AIST), Japan{k.yoshii, m.goto}@aist.go.jp
ABSTRACTThis paper presents probabilistic n-gram models for symbolic chord sequences. To overcome the fundamental limitations in conventional models—that the model optimality
is not guaranteed, that the value of n is fixed uniquely, andthat a vocabulary of chord types (e.g., major, minor, · · · ) isdefined in an arbitrary way—we propose a vocabulary-free
infinity-gram model based on Bayesian nonparametrics. It
accepts any combinations of notes as chord types and allows
each chord appearing in a sequence to have an unbounded
and variable-length context. All possibilities of n are taken
into account when calculating the predictive probability ofa next chord given a particular context, and when an unseen
chord type emerges we can avoid out-of-vocabulary error byadaptively evaluating the 0-gram probability, i.e., the combinatorial probability of note components. Our experiments
using Beatles songs showed that the predictive performanceof the proposed model is better than that of the state-of-theart models and that we could find stochastically-coherent
chord patterns by sorting variable-length n-grams in a line
according to their generative probabilities.

C:maj
G:7
F:maj
Context

G:7

0-gram probability (base measure)P(C:maj)
Bayesiansmoothing
1-gram probabilityP(C:maj|φ)

C:maj

2-gram probabilityP(C:maj|G:7)

C:maj

3-gram probabilityP(C:maj|F:maj G:7)

Bayesiansmoothing
Bayesiansmoothing

Next chord

Figure 1. A hierarchical nonparametric Bayesian model for
accurately smoothing n-gram probabilities.
models are based on (n−1)-order Markovian assumption because chords exhibit strong short-term dependency. In otherwords, each chord in a given sequence is assumed to depend on its n − 1 previous chords called a context. Usinga limited amount of observed data, the goal is to make astatistical model that can calculate the predictive probabilityof a next chord (n-gram probability), given any context oflength n−1. However, the observed n-grams are generally alimited subset of all kinds of n-grams, and the number of all
kinds of n-grams increases exponentially with increasing n.
Therefore, the naive estimates of the probabilities of unobserved n-grams are zero. To avoid such overfitting, various
heuristic smoothing methods have been developed [7].
In this paper we focus on three fundamental limitationsof conventional n-gram models: 1) n-gram models based onheuristic smoothing methods have no solid theoretical foundation, 2) the value of n should be specified uniquely in advance even though each chord depends on a variable-length
context, 3) A limited set of chord labels (e.g., major, minor,
augmented, diminished, seventh, · · · , and their derivations)should be defined as a vocabulary in advance. Especially,
the last limitation has not been discussed so far.
To overcome these limitations, we propose a vocabularyfree infinity-gram model by extending modern nonparametric Bayesian n-gram models [8–10]. Our model is formulated in a hierarchical Bayesian manner (Figure 1) and has
the following merits: 1) The predictive distribution of a next
chord can be naturally formalized by providing the probabilistic generative model of chord sequences. 2) Each chordin a sequence is allowed to have an unbounded and variablelength context. A posterior distribution of the context length

1. INTRODUCTION
Chord progression analysis is an important task for contentbased music information retrieval (MIR) [1, 2]. Because thechord patterns used in musical pieces are closely related tothe composer styles [3] and musical genres [4], it is useful
to build statistical models of chord patterns from symbolic
chord sequences. In addition, accurate models of chord sequences (called language models in analogy with automatic
speech recognition) could improve the accuracy of automatic chord recognition for music audio signals [5, 6].
So far, n-gram models have often been used as language
models of chord sequences [2–6]. An n-gram is a subsequence of n chords in a given chord sequence, and n-gram
Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page.
c 2011 International Society for Music Information Retrieval.
645

Oral Session 8: Chord Analysis

Chord type
Major
Minor
Diminished
Augmented
Major Seventh
Minor Seventh
SeventhDim. Seventh
Half Dim. Seventh
Min. (Maj. Seventh)
Major Sixth
Minor Sixth
Ninth
Major NinthMinor Ninth
Suspended Second
Suspended Fourth

can be estimated. 3) Any combinations of notes can be accepted as chord types. A chord vocabulary is incrementally
expanded as needed. These metits enable our model to not
only attain the best performance but also find “stochasticallycoherent” variable-length chord patterns that are not always
simply the ones used most frequently (cf. [11]).
The innovative models of symbolic chord sequences (aninfinity-gram model and its vocabulary-free extension) areuseful for probabilistic modeling of music audio signals. A
typical application is automatic chord recognition, where a
vocabulary of chord labels is given. For example, an infinitygram model could be fused with a joint probabilistic modelof keys, chords, and bass notes [12]. Another novel application is automatic music transcription, where a vocabulary is
not given. We plan to use a vocabulary-free model as a priordistribution on a probabilistic acoustic model for multipitch
estimation [13], and jointly optimize the both models. Thismeans that chords and their progressions (now “chords” arecombinations of notes, not text labels) are self-organized in
an unsupervised manner and are used as a constraint on simultaneous and temporal pitch distributions.
The rest of this paper is organized as follows: Section 2
describes the chord notations used in this study. Section 3
introduces related work on nonparametric Bayesian n-grammodels and Section 4 explains our model. Section 5 reports
our experiments and Section 6 concludes this paper.

Label
maj
min
dim
aug
maj7
min7
7
dim7
hdim7
minmaj7
maj6
min6
9
maj9
min9
sus2
sus4

Components
100010010000
100100010000
100100100000
100010001000
100010010001
100100010010
100010010010
100100100100
100100100010
100100010001
100010010100
100100010100
101010010010
101010010001
101100010010
101000010000
100001010000

Table 1. Shorthand labels and pitch-class components
they are not defined in Table 1. For example, C major chords
with an added fourth are written as C:100011010000. Suchinformation is available in Harte’s chord annotations [14].
With the additional symbol “N”, the resulting vocabulary
size is 49153 (212 × 12 + 1). This is finite because we focus on note existences in individual pitch classes. Note thata truly vocabulary-free (infinite-vocabulary) notation can be
defined by focusing on note counts based on musical scores,
i.e., by representing note components of each chord as a 12dimensional nonnegative-integer vector.

2. CHORD NOTATIONS

3. PROBABILISTIC LANGUAGE MODELS

We introduce label-based and component-based notations torepresent chord sequences (Table 1).

This section introduces related work on n-gram models. We
first identify the purpose of n-gram modeling and then explain several state-of-the-art models based on the probability
theory of Bayesian nonparametrics.

2.1 Label-based Notation
The conventional label-based notation is based on intuitive
shorthand labels defined by Harte et al. [14]. There are 17
chord labels with an attached root note, which is one of 12
pitch classes.1 In this paper we do not distinguish C# from
Db because they are in the same pitch class. This is a standard treatment used in [2, 3]. For example, C major and
Gb diminished seventh chords are respectively represented
as C:maj and F#:dim7. The symbol “N” is used to indicate“no chord” (e.g., silence or untuned sounds). The resulting
vocabulary size is 205 (17 × 12 + 1).

3.1 Problem Specification
Suppose we have a chord vocabulary W whose size is V
(in this paper, 205 or 49153). Let w ∈ W be a chord andu ∈ W n−1 , where n can be any positive integer, be a context consisting of a sequence of n − 1 chords. We have alimited amount of observed data X, which is a sequence of
M chords, x1 x2 · · · xM , where xm ∈ W (1 ≤ m ≤ M ).
We assume for simplicity that we have only one chord sequence. In n-gram modeling, each chord xm is assumed todepend on the past n−1 chords (context).
Given observed data X, the goal is to estimate Pu (w|X),i.e., the predictive probability of chord w following context
u. Let cuw be the number of occurrences of chord w following context u in training data X. The naive maximum
likelihood (ML) estimate is given by
cuw
PuML (w|X) =(1)
cu·
where the dot (·) means the sum over that index, i.e., cu· =w cuw . However, if n-gram uw is not observed in X

2.2 Component-based Notation
The component-based notation is based on degrees of note
components (relative displacements against a root note). Each
chord is represented as a combination of a root note and a
12-dimensional binary vector whose elements indicate theexistences of the corresponding degrees. For example, Cmajor chords are written as C:100010010000 and D major
chords as D:100010010000, not as D:001000100100. Notethat any combinations of notes can be represented even if
1 The pitch classes are defined as 12 different scales within an octave,i.e., {C, C#, D, D#, E, F, F#, G, G#, A, A#, B}.

646

12th International Society for Music Information Retrieval Conference (ISMIR 2011)(cuw = 0), its probability is estimated to be zero. This iscalled the zero-probability problem.
To solve this problem various smoothing methods havebeen proposed. The family of Kneser-Ney (KN) smoothingis empirically known as one of the most accurate smoothing
techniques [7]. A method called interpolated KN (IKN) estimates Pu (w|X) by discounting the actual count cuw by
a fixed amount d|u| depending on the context length |u|
if cuw > 0 (otherwise the count remains 0). Furthermore,
the discounted n-gram probability of chord w is interpolated with the (n−1)-gram probability of chord w. Anotherimportant variant is called modified KN (MKN), where theamount of discount is allowed to vary according to the valueof cuw . MKN is known to slightly outperform IKN.

φ

F:maj
…

Send
a proxy

C:maj
Depth 1

Original customer
Original customer
who sends a proxy
Proxy customer…

Depth 2Proxy customer
who sends a proxy

Figure 2. Hierarchical Pitman-Yor language model.
global base measure (0-gram distribution), which is usuallyassumed to be uniform, i.e., G0 (w) = 1/V .
Consequently, the hierarchical structure of the HPYLM
can be represented as a suffix tree of depth n−1, as shown in
Figure 2 where the case of n = 3 is illustrated. Each node is
identified as a context, i.e., descending the tree from the root
node to the target node means back-tracking the context.
3.2.2 Stochastic Process for Data Generation
Once the HPYLM is defined, observed data X is generated
according to a stochastic process called the Chinese restaurant franchise (CRF), which can be explained by using a
metaphor in which contexts are likened to restaurants, M
observed variables in X are likened to customers, and V
chord types in W are likened to dishes. Each restaurant isallowed to have an unbounded number of tables and each table is served a dish. Each customer enters a restaurant, sits
at a table, and eats a dish served at that table.
We suppose that x1 , · · · , xM are generated sequentially,
and consider how the m-th customer xm behaves, given aseating arrangement of the past customers {x1 , · · · , xm−1 }.
The customer xm enters restaurant u = xm−(n−1) · · · xm−1
of depth n−1. Let tuw be the number of tables serving dishw in restaurant u. There are tu· tables in total. Let cuwk be
the number of customers sitting at table k and eating dish w(cuwk = 0 if table k does not serve dish w). The customer
xm then sits (i) at an existing table k (1 ≤ k ≤ tu· ) and eatsa dish w served at the table with probability proportional to
cuwk −d|u| or (ii) at a new table k = tu· +1 with probability
proportional to d|u| tu· +θ|u| . In the case (i), the value of xm
is set to w and cuwk is incremented. In the case (ii), to ordera dish served at the new table k, a proxy customer is sent to
the parent restaurant π(u), where he behaves in a recursive
manner. If he eventually eats a dish w in restaurant π(u),the dish w is also served at the new table k in restaurant u
and the customer xm eats the dish w. Consequently, tuw isincremented, the value of xm is set to w, and cuwk is incremented. Note that when the proxy customer sits at a newtable in restaurant π(u), a new proxy customer is further
sent to the restaurant π(π(u)). Finally, a proxy customer
may be sent to the root restaurant φ. When he sits at a newtable in the root restaurant φ, a dish served at the new tableis chosen according to the global base measure G0 .

3.2.1 Pitman-Yor Process and Hierarchical Formulation
We briefly explain the Pitman-Yor process (PY) [15], which
is a building block of nonparametric Bayesian models. The
PY is a distribution over distributions (e.g., n-gram distributions) over a sample space (e.g., vocabulary W ). Let d andθ be positive real numbers and G0 be a distribution over asample space. The PY is written as(2)

where d is called a discount parameter, θ a strength parameter, and G0 a base measure. G is a random distribution overthe sample space. When the value of θ becomes larger, G ismore likely to be similar to G0 .
The HPYLM is formulated by layering PYs in a hierarchical Bayesian manner. Suppose we have a unigram distribution Gφ over W , where φ is the empty context and Gφ (w)is the unigram probability of chord w. A bigram distribution
Gu given the last chord u differs from but is somewhat similar to Gφ . Here Gu is assumed to be drawn from a PY withbase measure Gφ as Gu ∼ PY(d1 , θ1 , Gφ ), where d1 and θ1
are discount and strength parameters that are shared amongcontexts of length 1. Generally speaking, an n-gram distribution Gu given a context u of length n−1 is drawn from a
PY with base measure Gπ(u) as follows:Gu ∼ PY(d|u| , θ|u| , Gπ(u) )Senda proxy

Depth 0

D:min

C:maj

3.2 Hierarchical Pitman-Yor Language Model
Teh [8] proposed a nonparametric Bayesian n-gram model
called a hierarchical Pitman-Yor language model (HPYLM).
Interestingly, IKN was proven to be a deterministic approximation of the HPYLM, which can be optimized in a principled way and performs better than IKN.

G ∼ PY(d, θ, G0 )…

Back-track
the context(3)

where π(u) is a shortened context obtained by removing
the earliest chord from u, and d|u| and θ|u| are discount andstrength parameters depending on the length |u|. Since the(n−1)-gram distribution Gπ(u) is unknown, a PY prior withparameters d|π(u)| and θ|π(u)| and base measure Gπ(π(u))
is recursively put on Gπ(u) . Finally, the unigram distribution Gφ is given by Gφ ∼ PY(d0 , θ0 , G0 ) where G0 is a647

Oral Session 8: Chord Analysis

More specifically, given a particular seating arrangement(denoted by S), a next chord w following context u is generated according to the following predictive distribution:
PuHPY (w|S) =Create an empty tree
for m = 1 : M in random order
Add customer xm to the tree at depth n-1
for i = 1 : ∞for m = 1 : M in random order
Remove customer xm from the tree
Add customer xm to the tree at depth n-1

cuw· − d|u| tuw
d|u| tu· + θ|u| HPY+
Pπ(u) (w|S) (4)cu·· + θ|u|cu·· + θ|u|where Eqn. (4) is a recursive definition with respect to conHPY
text u of any length, e.g., Pπ(u)(w|S) is given by substituting π(u) into u in Eqn. (4). Starting with an empty tree
(cuwk = 0 and tuw = 0), a seating arrangement for X is
obtained by adding M customers one by one. The IKN was
found to be an approximation of the HPYLM (the HPYLM
reduces to the IKN when θ|u| = 0 and tuw = 1).

Figure 3. Gibbs sampling algorithm for HPYLM.
3.3.1 Stochastic Process for Data Generation
We consider how the value of n-gram length zm is stochastically determined. The customer xm descends the tree byfollowing a path φ → xm−1 → xm−2 → · · · , i.e., by backtracking the context u. When he arrives at restaurant ui of
depth i (0 ≤ i ≤ ∞), he stops there with probability ηui or
passes through with probability 1 − ηui . The probability ofzm = n (1 ≤ n ≤ ∞) is therefore given by

3.2.3 Predictive Distribution and Bayesian Inference
The goal is to estimate the predictive distribution Pu (w|X)
in a Bayesian manner. Since a true seating arrangement for
X is unknown, the expected value of PuHPY (w|S) is calculated under the CRF P (S|X) as follows:
PuHPY (w|X) =PuHPY (w|S)P (S|X)(5)

Pu (n|η) = ηun−1(7)

Since η (a set of parameters) is unknown, beta prior distributions with hyperparameters α and β are put on η as follows:p(η) =
Beta(ηu |α, β)(8)Because this sum is analytically intractable, Gibbs samplingis used for approximation. More specifically, we getL

1  HPY
Pu (w|S l )L(1 − ηui )i=0

S

PuHPY (w|X) ≈n−2u∈tree(6)

Given the value of zm , the value of xm is stochasticallydetermined according to the CRF described in Section 3.2.2.
Note that there are not only proxy customers but also original customers in restaurants other than leaf nodes.
More specifically, given a particular seating arrangement
denoted by S, a next chord w following context u is generated according to the following predictive distribution:

PuVPY (w|S) =PuVPY (w|n, S)Pu (n|S)
(9)

l=1

where L is the number of many i.i.d. seating arrangements
sampled from p(S|X) and l is a sample index.
The Gibbs sampling algorithm is shown in Figure 3. First,
a seating arrangement is initialized by adding all customers
one by one according to the posterior CRF, where each customer xm = w sits at an existing or new table serving dish w
with probability given by the first or second term of Eqn. (4).
Then a customer xm is selected randomly and removed fromthe tree, from which the related proxy customers and tables
that become empty are also removed. Given a seating arrangement of the other customers, the customer xm is added
to the tree again according to the posterior CRF. By iterating this operation, L seating arrangements are sampled witha certain interval. Since the parameters d0 , · · · , dn−1 andθ0 , · · · , θn−1 are unknown, beta and gamma prior distributions are put on them and the values of the parameters are
sampled from posterior distributions (see details in [8]).

nwhere PuVPY (w|n, S) is obtained in the same way as Eqn. (4)and Pu (n|S) = Pu (n|η)p(η|S)dη is easily calculated byusing the conjugacy between Eqns. (7) and (8) (see [9]).
3.3.2 Predictive Distribution and Bayesian Inference
The predictive distribution of a next chord w is obtained in
the same way as the HPYLM (Section 3.2.3). The only difference with respect to Gibbs sampling is that the VPYLM
needs to sample the value of zm from its posterior distribution before adding customer xm to the tree. When xm = w,
the posterior probability of zm = n is given by

3.3 Variable-Order Pitman-Yor Language Model
A problem of the HPYLM is that all M customers are forced
to enter restaurants of fixed depth n−1. To solve the problem, Mochihashi and Sumita [9] proposed a variable-order
PY language model (VPYLM) that allows each customer toenter a restaurant of variable depth. Each chord xm is associated with a latent variable zm that indicates the value of n(depth+1). Since a true value of zm is unknown, all possible values of zm are considered (n is marginalized out) formaking predictions, resulting in the infinity-gram model.

Pu (n|S, w) ∝ Pu (w, n|S) = PuVPY (w|n, S)Pu (n|S) (10)
3.4 Nested Pitman-Yor Language ModelAn essential problem of standard n-gram models is that weneed to define a finite vocabulary even though in the realworld the vocabulary is growing steadily. To solve this problem in the context of word sequence modeling, Mochihashi
et al. [10] proposed a nested PY language model (NPYLM)
by formulating a global base measure G0 over a countably

648

12th International Society for Music Information Retrieval Conference (ISMIR 2011)

The predictive distribution of a next chord w can be calculated in the same way as the VPYLM (Section 3.3.2). The
Gibbs sampling algorithm of the VPYLM is modified as follows: When a (proxy) customer sits at a new table (a newtable is added) in the root restaurant φ, the values of nv andni or n̄i are incremented according to the components of thetarget chord (a dish served at that table). When a table is removed from the root restaurant φ, the values of nv and ni
or n̄i are decremented. The values of π and τ are sampledfrom the posterior distribution given by Eqn. (13).

infinite number of variable-length words. Note that the conventional base measure G0 (w) = 1/V cannot be used because G0 (w) → 0 when V → ∞. Instead, a spelling model
based on a letter-level VPYLM is given as a global basemeasure G0 of a word-level VPYLM. More specifically, eachword is regarded as a sequence of letters, which are assumed
to follow a letter-level CRF. The word length (the numberof letters) is assumed to follow a Poisson distribution. Thus,
the 0-gram probability of any word w, G0 (w), is given by
the product of the probabilities of the letters and their number, resulting in the infinite-vocabulary model.

5. EXPERIMENTS
4. VOCABULARY-FREE INFINITY-GRAM MODEL

This section reports our comparative experiments.

For chord sequence modeling we propose a novel vocabularyfree infinity-gram model similar in spirit to the NPYLM.

5.1 Experimental Conditions
We used a standard dataset of chord sequences for 180 Beatles songs collected from 12 albums (13 CDs) [14]. Because the choice of chords depends on the musical key, we
selected 137 major-scale non-transposition songs and transposed them to C major. The total number of chords was
10,761, where 103 chord types were observed in the labelbased notation (the vocabulary size was 205) and 149 chordtypes were observed in the component-based notation (thevocabulary size was 49153). The entropies of both data were
3.79 [bits] and 3.92 [bits], respectively.
In the first experiment using the label-based notation, theeffectiveness of infinity-gram modeling was evaluated bycomparing six existing methods: Good-Turing (GT), WittenBell (WB), IKN, MKN, HPYLM, and VPYLM, where GT
and WB are classical smoothing methods [7]. In the second
experiment using the component-based notation, the effectiveness of vocabulary-free modeling was evaluated. In addition to the existing methods, we tested our models that incorporate the vocabulary-free base measure G0 into HPYLM
and VPYLM (denoted by prefix “VF-”). To evaluate the predictive performance, we conducted 10-fold cross validationand measured perplexity, which indicates the average number of next-chord candidates (a degree of uncertainty), given
a context. A lower perplexity means better performance.

4.1 Mathematical Formulation
A critical problem is that we cannot apply the NPYLM tochord sequence modeling. Because words are temporal sequences of letters and chords are simultaneous combinationsof notes, we need a different base measure G0 .
To solve this problem, we formulate a probabilistic model
based on the component-based notation (Section 2.2) as a
global base measure G0 of a chord-level VPYLM. The basemeasure G0 is based on a conjugate model. In general, achord w can be written as w0 :w1 · · · w12 , where w0 is aroot note and the other variables take binary values. Whenw = N, w0 = N and other variables are not used. We assume
w0 to follow a 13-dimensional discrete distribution and theothers to follow Bernoulli distributions as follows:12G0 (w) = p(w|π, τ ) = πw0
τiwi (1 − τi )1−wi
(11)
i=1

where π = {πC , πC# , · · · , πB , πN } indicates the probabilitiesof the respective pitch classes and “N” and τ = {τ1 , · · · ,τ12 }indicates the existence probabilities of the respective degrees. If w = N , G0 (w) = πN . Since the values of π and τ
are unknown, we put prior distributions as follows:12
Beta(τi |b0 , c0 )(12)p(π, τ ) = Dir(π|a0 )5.2 Experimental Results
We found in the first experiment that VPYLM yielded thelowest perplexity (Table 2) and that, as shown in Figure 4,
a posterior distribution over n can be estimated for eachchord. To obtain better predictive performance, it is important to marginalize out n (take all possibilities into account)rather than use a maximum-a-posteriori (MAP) estimate ofn. The training time and memory usage of the VPYLM were
two times shorter and five times smaller than those of the 10gram HPYLM because unnecessarily-longer contexts (deepnodes) do not need to be considered (expanded). We could
discover stochastically-coherent
 chord patterns (Table 3) bycalculating Pu (w, n|X) = S Pu (w, n|S)P (S|X), whichindicates how likely chord w is to follow context u of lengthi=1

where a0 , b0 , and c0 are hyperparameters (set to 0.5).
4.2 Bayesian Inference
Given a seating arrangement S, the posterior distribution of
π and τ can be easily calculated as follows:12
Beta(τi |b0 +ni , c0 + n̄i ) (13)p(π, τ |S) = Dir(π|a0 +n)i=1

where nv (v is one of the pitch classes or “N”) is the numberof tables serving dishes with root note v (w0 = v) in the root
restaurant φ, ni is the number of tables serving dishes with
the i-th note (wi = 1) in φ, and n̄i is the number of tables
serving dishes without the i-th note (wi = 0) in φ.

649

Oral Session 8: Chord Analysis

n
1
2
3
4
5
6
7
8
9
10

GT

WB

IKN

MKN

HPYLM

16.8
20.3
23.5
25.5
26.3
27.0
27.3
27.3
27.3
27.3

15.6
14.2
15.4
16.8
17.5
17.8
18.0
18.0
18.0
18.0

16.0
15.2
16.0
17.7
16.2
15.1
14.5
14.2
14.1
14.0

15.7
15.8
16.3
15.5
14.1
13.5
13.3
13.2
13.1
13.1

15.8 (±0.03)
14.5 (±0.10)
16.0 (±0.18)
13.9 (±0.25)
13.7 (±0.23)
13.6 (±0.23)
13.6 (±0.23)
13.6 (±0.22)
13.5 (±0.23)
13.5 (±0.23)

Pu (w, n|X)

VPYLM

n: posterior sample
13.4 (±0.33)
n: MAP estimate
12.9 (±0.35)
n: marginalized out
11.9 (±0.22)

Table 2. Perplexities in label-based notation.
n = 1 2 3 4 5 6 7 8 9 10

C:maj
G:maj
A:min
A:min
F:maj7
F:maj6
C:maj
G:maj
F:maj
C:maj
Verse A C:maj
G:maj
A:min
A:min
F:maj7
F:maj6
C:maj
G:maj
F:maj
C:maj
Intro

Figure 4. Hinton-diagram representation of posterior distributions over n at the beginning of the Beatles’ “Let It Be.”n − 1. For example, C:7 F:7 C:7 is a typical blues-rock pattern that was popularized by the Beatles. We can see that the
Beatles liked to use chord patterns including (major/minor)
seventh chords, which were not so common at that time.
In the second experiment, VF-VPYLM, the vocabularyfree infinity-gram model, yielded a perplexity significantly
lower than the other models did (Table 4). The performanceadvantage was larger than that in the first experiment. This
proves that our model is robust to the data sparseness (largeor infinite-vocabulary situation).
6. CONCLUSION
We presented a nonparametric Bayesian n-gram model for
chord sequences that requires neither a vocabulary of chordtypes nor a predefinition of n. We showed that it performed
significantly better than the state-of-the-art models.
This study opens up a new research direction. We plan tolet computers acquire the concept of “chords” in an unsupervised manner from a large amount of music scores and, ultimately, from a large amount of musical audio signals. We
know that certain combinations of notes can form chords. Is
this learned from experience? How reasonable is a definition of chords? To explore ways to answer this question weneed to consider an infinite number of note combinations as
chord candidates. Bayesian nonparametrics is a promising
generative approach to such kinds of meta-level problems.

Stochastically-coherent chord pattern (n ≥ 3)
n = 3: C:7 F:7 C:7
n = 3: B:maj F:maj G:majn = 3: A:min C:7 F:majn = 3: F:min G:maj C:majn = 4: F:maj F:maj G:maj C:majn = 3: E:min C:7 F:majn = 3: C:maj7 D:min7 E:min7
n = 4: B:maj F:maj G:maj C:majn = 3: D:min7 G:sus4 G:majn = 5: D:min G:maj C:maj F:maj C:maj

Table 3. Stochastically-coherent chord patterns.

n = 1 2 3 4 5 6 7 8 9 10
Verse B C:maj

G:maj
A:min
F:maj7
F:maj6
C:maj
G:maj
F:maj
C:maj
Chorus C:maj
A:min
E:min
F:maj
C:maj
C:maj
G:maj
F:maj
C:maj

0.701
0.682
0.656
0.647
0.645
0.632
0.630
0.627
0.622
0.620

n
10

GT

WB

IKN

MKN

38.3

24.4

18.5

17.5

n HPYLM
VF-HPYLM
10 18.0 (±0.29) 16.5 (±0.60)

n VPYLMVF-VPYLM∞ 15.8 (±0.29) 14.6 (±0.55)

Table 4. Perplexities in component-based notation.
Acknowledgment: This study was partially supported by KAKENHI 23700184. We thank Dr. Daichi Mochihashi (ISM).

7. REFERENCES[1] J.-F. Paiement, D. Eck, and S. Bengio. A probabilistic model
for chord progressions. ISMIR, pp.312–319, 2005.
[2] R. Scholz, E. Vincent, and F. Bimbot. Robust modeling of musical chord sequences using probabilistic N-grams. ICASSP,
pp.53–56, 2009.
[3] M. Ogihara and T. Li. N-gram chord profiles for composerstyle representation. ISMIR, pp.671–676, 2008.
[4] C. Pérez-Sancho, D. Rizo, and J. M. Iñesta. Genre classification using chords and stochastic language models. Connection
Science, vol.21, no.2-3, pp.145–159, 2009.
[5] H.-T. Cheng, Y.-H. Yang, Y.-C. Lin, I-B. Liao, and H. H. Chen.
Automatic chord recognition for music classification and retrieval. ICME, pp.1505–1508, 2008.
[6] M. Khadkevich and M. Omologo. Use of hidden Markov models and factored language models for automatic chord recognition. ISMIR, pp.561–566, 2009.
[7] S. Chen and J. Goodman. An empirical study of smoothing techniques for language modeling. Tech. Repo. TR-10-98,
Computer Science Group, Harvard University, 1998.
[8] Y. W. Teh. A Bayesian interpretation of interpolated KneserNey. Tech. Repo. TRA2/06, NUS School of Computing, 2006.
[9] D. Mochihashi and E. Sumita. The infinite Markov model.
NIPS, pp.1017–1024, 2007.
[10] D. Mochihashi, T. Yamada, and N. Ueda. Bayesian unsupervised word segmentation with nested Pitman-Yor language
modeling. ACL-IJCNLP, pp.100–1008, 2009.
[11] M. Mauch, S. Dixon, C. Harte, B. Fields, and M. Casey. Discovering chord idioms through Beatles and real book songs,
ISMIR, pp.255–258, 2007.
[12] M. Mauch and S. Dixon. Simultaneous estimation of chords
and musical context from audio. IEEE Trans. ASLP, vol.18,
no.6, pp.1280–1289, 2010.
[13] K. Yoshii and M. Goto. Infinite latent harmonic allocation: A
nonparametric Bayesian approach to multipitch analysis. ISMIR, pp.309–314, 2010.
[14] C. Harte, M. Sandler, S. Abdallah, and E. Gómez. Symbolic
representation of musical chords: A proposed syntax for text
annotations. ISMIR, pp.66–71, 2005.
[15] J. Pitman and M. Yor. The two-parameter Poisson-Dirichlet
distribution derived from a stable subordinator. Annals ofProbability, vol.25, no.2, pp.855–900, 1997.

650