A Learning-Based Quantization:
Unsupervised Estimation of the Model Parameters
Masatoshi Hamanaka*, Masataka Goto**, ***, Hideki Asoh***, Nobuyuki Otsu***, ****
*Research Fellow of the Japan Society for the Promotion of Science,** “Information and Human Activity”, PRESTO, JST, ***National Institute ofAdvanced Industrial Science and Technology (AIST), ****University of Tokyo
email: m.hamanaka@aist.go.jp

Abstract
This paper describes a method for organizing onset
times performed along a jam-session accompaniment
into normalized (quantized) positions in a score so theperformance data can be stored in a reusable form.
Unlike most previous beat-tracking-related methods
that focus on predicting or estimating beat positions,
our method deals with the problem of eliminating theonset-time deviations under the condition that thebeat positions are given. Our method solves thisproblem by using hidden Markov models (HMMs)
that model onset-time transition and deviation. The
HMM parameters are obtained by unsupervised
estimation using the Baum-Welch algorithm andheld-out interpolation: they can be derived from only
the session recording that we wanted to quantize.
Experimental results show that our model performs
better than the semi-automatic quantization incommercial sequencing software.

1

Introduction

We have been constructing a jam session system(Hamanaka, Goto, and Otsu 2001) that allows ahuman player to play interactively with virtual players,
each of which is imitating the musical reactions of ahuman player. Each virtual player determines its
intentions by using a reaction model that has beenacquired from a human player and then produces aperformance by connecting short phrases selectedfrom a phrase database (Fig. 1). Because this database
was manually prepared, the system cannot
automatically imitate the player’s characteristic phrases.
A method of simply cutting out phrases at bar lines
and pasting them does not work well (it creates
unnatural performances) because the onset times ofnotes played by human players intentionally orunintentionally deviate from the ‘normal’ position of
onset times in a score. Before cutting and pastingphrases, we need to use a quantization method thateliminates the deviation of onset times and aligns themto the normalized positions in the score. Because there
is no score to follow in improvisation, the normalized
positions in a score mean the positions at which aplayer intended to play. A typical quantization methodof commercial sequencing software requires the user
to specify a fixed grid interval, or resolution, (e.g.,

Virtual Player

Quantization
Cutting phrases

Reaction
model
intention
Connecting phrases
according to player’s
intention[Time]

Output performance[Time]

Figure 1: Performance generation using phrase databases.
eighth triplet or sixteenth note) to which onset times
are aligned, and each onset time is aligned to thenearest grid position. This method can therefore beused only when the rhythm structure within a beat isfixed and known (e.g., the beat contains eighth tripletsor the beat contains sixteenth notes). When therhythm structure changes frequently, as it does in a
jam session, we need to change the grid interval
adaptively.
Several quantization methods have been proposed.
Because tempo tracking methods (Dannenberg andMont-Reynaud 1987), (Allen and Dannenberg 1990),(Vercoe and Puckette 1985) for score following need touse an annotated score as prior knowledge, they cannot
quantize improvisations of a jam session. Beat tracking
methods (Katayose and Inokuchi 1990), (Goto andMuraoka 1998), (Goto 2001), (Dixon 2001) focus onpredicting beat positions and cannot quantize notes which
are not in the beat position. A quantization method using
connectionist model (Desain and Honing 1989) defines apotential energy that is stable if the ratio of the sum of
onset time intervals to the sum of other intervals is an
integer. It is not easily applied to various performances,
however, because the potential energy is fixed.
On the other hand, quantization methods forautomatic transcription (Takeda et al. 2003), (Cemgil
et al. 2000) integrate tempo tracking and quantization.
They indicate that a continuous speech recognition
framework using a probabilistic model provides auseful approach for estimating tempos and beats andallocating bar lines. However, difficult problems stillremain, such as discrimination between eighth triplets
notes and sixteenth notes even if the tempo is known
or constant. Quantization in commercial sequencing
software is not effective at solving this problem
because an onset time that has a large deviation isaligned to an incorrect grid.
The quantization method in our previous work
(Hamanaka et al. 2001) using HMMs indicates thatthe performance of the discrimination between eight
triplets notes and sixteenth notes improves if we
configure the HMM parameters properly. But it could
not quantize a human-performance of a new playerusing appropriate HMM parameters because theHMM parameters were supervised trained withcorrect data. In this study, we propose an
unsupervised estimation method of the model
parameters from a session recording using the BaumWelch algorithm and held-out interpolation. The
HMM-based method can achieve proper quantization.

2

Learning-Based Quantization

A human player, even when repeating a given
phrase on a MIDI-equipped instrument, rarely produces
exactly the same sequence of note onset times because
the onset times deviate according to the performer’s
actions and expression. We can model a process togenerate the deviations by using a probabilistic model.
The problem of quantization, which acquires thesequence of onset times that the player intended fromthe sequence of deviating onset times that the player
actually performed, can be considered as an inverse
problem. This inverse problem can then be solved
using the inverse model derived from the model thatgenerates the deviation of onset times.

2.1 A model of onset-time transition and deviation
Let a sequence of intended (normalized) onset
times be θ and a sequence of performed onset times(with deviation) be y. Then a model for generating
the deviation of onset times can be expressed by aconditional probability P(y | θ ) (Fig. 2). Using thisconditional probability and the prior probability P( θ ),the inverse model can be calculated as Eq. (1)according to Bayes’ theorem.
P (θ | y ) =P ( y | θ ) P (θ )P( y ).

(1)

Here, P( θ ) represents how likely it is that a player
plays the sequence of onset times θ . Thus thesolution to the inverse problem for determining
optimal θˆ can be obtained by maximizing Eq. (1):θˆ = argmax P (θ | y ) = argmax P ( y | θ ) P (θ ) .
(2)θθ
Because P( y) is independent of θ , it can be ignored.

2.2 Formulation of the hidden Markov
modelsP( θ ) and P(y| θ ) can be formulated as a hidden
Markov model (HMM), which is a probabilistic
model that generates the transition sequence of hidden
states as a Markov chain. Each hidden state in thestate transition sequence then generates an observation
value according to the observation probability.
Modeling of performance.
• Target in modeling
We model the onset time of a musical note (i.e. thestart time of the note) and introduce a new model of
distribution of onset times. While the duration-timebased model used in Takeda (Takeda, et al. 2003) islimited, our onset-time-based model is suitable forpolyphonic performances, such as those that include
two-hand piano voicing and guitar arpeggio.
• Unit in modeling
We use a quarter note (beat) as the unit of each HMM,
i.e., the temporal length corresponding to each HMM
is a quarter note. The reason we use a quarter-note
unit is to distinguish between eighth triplets andsixteenth notes within the scope of a quarter note.
The three notes of eighth triplets are located on threeequi-distant positions within a quarter note duration,
while the four notes of the sixteenth notes are locatedon four equi-distant positions in a quarter note. An
actual performance consisting of a sequence ofquarter notes can be modeled and quantized byconcatenating the quarter-note-length HMMs.
This quarter-note modeling reduces the calculation
time and facilitates the preparation of large data sets
for training the model.
• Unit of quantization
We introduce two different discrete temporal indices,k and i. The unit of k is a quantization unit for
describing performed onset time; it is 1/480 of aquarter note, a value often used in commercial
sequencing software. The unit of i is a quantization
unit for describing the intended onset time; it is onetwelfth of a quarter note. It can describe both eighth
triplets and sixteenth notes.

Figure 2: Forward model and inverse modelin the quantization problem.

Quarter-note hidden Markov model. Figure 3
shows the HMM used in our study to model asequence of onset times within a quarter note (beat).
All the hidden states of the HMM correspond to thepossible positions of the intended onset times, and theobserved value that comes from a hidden statecorresponds to a performed onset time with deviation.

E

Transition of intended onset time

S

aS 1

1

12

2

a14

b1(k)

a10 E

a4 10
4

3

5

6

7

8

9

10

11

E

S

12

1

2

3

Observation probability of each state
b4(k)
b7(k)
b10(k)

0beat line

120

240

Performed onset time

0 [k]

360

beat line[Time]

Figure 3: Overview of the quarter-note hidden Markov model.

Onset times in a beat are quantized into 12 positions
for hidden states, and into 480 positions forobservation values. That is, each HMM component isinterpreted as follows.
Hidden state i: intended onset time. (i =1, …, 12)
Observation k: performed onset time. (k = 1,…, 480)
Transition probability aij:probability that theintended onset time j follows the intended onset time i.
Observation probability bi(k): probability that theperformed onset time is k and the intended onset time is i.
A state-transition sequence begins with a dummy
state “Start” and ends with a state “End”. Figure 4
shows simple examples of state sequences.
Start -> 1 -> 4 -> 7 -> 10 -> End.
Start -> 1 -> 5 -> 9 -> End.

The human-performance data, y, comprises actual
MIDI recordings performed by three human players(guitarists), A, B, and C. Each player played on a
MIDI guitar along with a fixed-tempo jam session
accompaniment.
Each performance was twelve
choruses long (1 chorus = 12 bars). Each player
performed at two different tempos: 120 M.M. and an
arbitrary tempo decided by the player. Consequently,
there were 6 sets of data (A1, A2, B1, B2, C1, and C2).
Baum-Welch algorithm. The HMM parameters aij andbi(k) were learned from the first half of the humanperformance data using the Baum-Welch algorithm.
• Set the initial value a0ij and b0i(k) properly.
Let a0ij be the average aij derived from the 6 sets ofdata. Let b 0 i (k) have a normal distribution withmean = (i-1)*40 and standard deviation = 20 (1 beat =480). The similarity of the distributions of bi(k) and anormal distribution with mean = (i-1)*40 andstandard deviation = 20 has been reported previously(Hamanaka et al. 2001).
• Forward-Backward Algorithm.
Calculate the forward probability t(i) and backward
probability t(i). t(i) is the probability of the partial
observation sequence from the start of a humanperformance to note t given state i at t and the model. t(i) is the probability of the partial observation
sequence from t+1 to the end of a humanperformance, given state i at t and the model .
• Reestimation of model parameter
Reestimate aij and bi(k) using a recurrence formula as follows.
T is the number of notes in the human-performance data.
a k +1ij =Start -> 1 -> 1 -> End.
Start -> End.

(expected number of state - transition from i to j )(expected number of state - transition from i)

T −1∑αt (i )a k ijbk j ( yt +1 mod 480)βt +1( j )= t =1

Estimation of the optimal sequence of onset times.
By concatenating the quarter-note HMMs and using
the Viterbi algorithm that maximizes the posterior
probability P( θ |y) to search for the sequence ofhidden-state transitions, we can estimate the mostprobable sequence of onset times throughout aperformance. When a performance includes T notes,
the observed onset-time sequence can be denoted asy=(y1, y2,…, yT). To acquire the optimal statetransition sequence, we define t(i) as:
δt (i ) = max P(θ1 ,θ 2 ,...,θ t-1 ;θ t = i; y1 , y 2 ,..., y t | ) , (3)θ1 ,θ 2 ,...,θ t-1

where t(i) is the best score (highest probability) of
the state transition sequence θ =( θ 1, θ 2,…, θ t), withthe condition that the t-th state θ t is equal to i, anddenotes a set of all the parameters of the model. The
value of the best score satisfies the following
recursive equation:(4)
δ t + 1 ( j ) = max [δ t (i ) a ij ] b j ( y t + 1 )i.

2.3 Unsupervised Estimation of Model Parameters
The HMM parameters aij and bi(k) were derived
from a set of human-performance data using the
Baum-Welch algorithm and held-out interpolation.

(5)

T −1

∑αt (i )βt (i )Figure 4: Simple example of state sequences.

t =1

 expected number instants in state i and having observation kk +1b j (k ) = (expected number instants in state i)
12

T

=

∑

α t ( j )βt ( j ) ∑α t ( j )βt ( j )t =1s.t . ( yt +1 mod 480 )= k
T

j =1

∑

α t ( j )βt ( j ) ∑α t ( j )βt ( j )

12

t =1

j =1

(6)

• Iteration
After the reestimation of the model parameters, wehave another model, , which is more likely thanmodel to produce the observed onset-time sequencey. This means that
P(y| ) > P(y| ).
(7)
The reestimation process can be continued until nofurther improvement in P(y| ) is achieved; that is,until a local maximum is reached.
Held-Out interpolation. When using the BaumWelch algorithm, the HMM parameters generally
converge, but the model parameters bi(k) cannot bereestimated properly when the number of notes in thehuman-performance data is insufficient. To reestimate

bi(k) properly, we use the held-out interpolation technique.
In the following explanation, we use normalized timel to align the time that corresponds to state j (Eq. (8)).
k − 40 ⋅ ( j − 1)l=k − 40 ⋅ ( j − 1) + 480(k − 40 ⋅ ( j − 1) ≥ 0 )(8)(k − 40 ⋅ ( j − 1) < 0 )We perform linear interpolation of bj(l) ( j = 1, 2, …,
12) by an interpolation factor (0 ≤ ≤ 1).
bˆ j (l ) = ζ b (l ) + (1 − ζ ) b j (l ) (k=0, 1, …, 479)(9)b (l ) is an average of bi(l).
b (l ) =1 12∑b j (l )12 j =1(10)bˆ j (l ) is a more accurate estimate than bi(l) if weproperly configure the interpolation factor, (Efron
and Morris 1977).
We estimate
by using the EM algorithm from thesecond half of the human-performance data. Equation(11) is for reestimation of .

ζˆ =

ζ × b j (l )
1 T
∑
(
)
T t =1 1 - ζ × b j (l ) + ζ × b j (l )(11)

The HMM parameters aij and bi(k) were derived by
iterating the Baum-Welch algorithm and held-out
interpolation.

3. Experimental Results
We evaluated the performance of quantization
using the rate of correct quantization, which we
defined as follows:(correct rate) =(the number of onsets quantized correctly)(the number of onsets)(12)

4. Conclusion
This paper has described a quantization method thatuses HMMs for modeling onset-time transition anddeviation. This method makes it possible to estimate
the intended onset times (without deviation) from theonset times (with deviation) performed together
with a fixed-tempo jam session accompaniment.
Experimental results showed that the proposed
method that trains the HMMs with the humanperformance data using the Baum-Welch algorithm
and held-out interpolation is effective when therhythm structure changes frequently.
We plan to use this method to automatically generate
the phrase database for our jam session system.

References
Hamanaka, M., Goto, M., and Otsu, N. 2001. “Learning-BasedJam Session System for a Guitar Trio.” Proceedings of theInternational Computer Music Conference. pp. 467-470.
Dannenberg, R. B. and Mont-Reynaud, B. 1987. “Following an
Improvisation in Real Time.” Proceedings of theInternational Computer Music Conference. pp. 241-248.
Allen, P. and Dannenberg, R. B. 1990. “Tracking MusicalBeats in Real Time.” Proceedings of the International
Computer Music Conference. pp. 140-143.
Vercoe, B.L. and Puckette, M. 1985. “The synthetic rehearsal:
Training the synthetic performer.” Proceedings of theInternational Computer Music Conference. pp. 275-278.
Katayose, H. and Inokuchi, S. 1990. “Intelligent Music
Transcription System.” Journal of Japanese Society for
Artificial Intelligence 5(1): 59-66. (in Japanese)
Goto, M. and Muraoka, Y. 1998. “An Audio-based Real-time
Beat Tracking System and Its Applications.” Proceedings ofthe International Computer Music Conference. pp. 17-20.
Goto, M. 2001. “An Audio-based Real-time Beat Tracking
System for Music With or Without Drum-sounds.” Journalof New Music Research 30(2):159-171.
Dixon, S. 2001. “An Interactive beat tracking and visualization
system.” Proceedings of the International Computer Music
Conference. pp. 215-218.
Desain, P. and Honing, H. 1989. “The Quantization of Music
Time: A Connectionist Approach.” Computer Music
Journal 13(3):56-66.
Takeda, H., Nishimoto, T., Shinoda, K., and Sagayama, S.
2003. “Score Estimation from Polyphonic MIDI
Performance with Probabilistic Models.” Information
Processing Society of Japan SIG Notes 2003(48): 21-26.
(in Japanese)
Cemgil, A. T., Desain, P., and Kappen, H. J. 2000. “Rhythm
quantization for transcription.” Computer Music Journal
24(2):60-76.
Hamanaka, M., Goto, M., Asoh, H., and Otsu, N. 2001. “A
Learning-Based Quantization: Estimation of Onset Times
in a Musical Score.” Proceedings of the World
Multiconference on Systemics, Cybernetics and Informatics
2001 10(1):pp. 374-379.
Efron, E. and Morris, C. 1977. “Stein’s Paradox in Statistics.”
Scientific American 20(1): pp. 451-468.

To evaluate the baseline quantization performanceof commercial sequencing software, we specified
three different grid intervals (eighth triplet, sixteenth
note, and sixteenth triplet) on the software andcalculated the rate of correct quantization for each
(Table 1). The correct rates obtained with other gridintervals were worse than the rates listed in Table 1.
Table 1 also shows the correct rates for our method.
For all of the performances the correct rates for our
method were higher than 70 percent. Our method
performed better than the commercial sequencing
software on the human-performance data (A2 and C1)
which contain eight triplet bars in half of it andsixteenth bars in the other half. The simple quantization
with eight triplet grids was effective on most of thehuman-performance data (A1, B2, and C2) whichcontain eight triplet bars in most of it. The results
showed that our method is effective in typical cases
where the rhythm structure changes frequently during
human-performance data (i.e., the ratio of eight triplet
bars and sixteenth bars is not known in advance).
Table 1: Performance of commercial sequencing software compared with our method.
Player A
Player B
Player C
A1
A2
B1
B2
C1
C2
Commercial sequencing software (eighth triplet)
85.6%
67.6%
79.4%
88.6%
57.0% 97.7%
Commercial sequencing software (sixteenth note)
37.3%
54.5%
36.8%
34.7%
70.7% 45.5%
Commercial sequencing software (sixteenth triplet) 48.4%
57.7%
57.8%
51.3%
56.1% 82.5%
Our HMM-based quantization method
74.7%
78.4%
72.1%
78.2%
84.7% 89.4%