A Learning-Based Quantization: Estimation of Onset Times in a Musical Score
Masataka Goto**,***
Nobuyuki Otsu***,*

Masatoshi Hamanaka*
Hideki Asoh****University of Tsukuba** “Information and Human Activity”, PRESTO, JST***National Institute of Advanced Industrial Science and Technology (AIST)
Mbox 0604, 1-1-1 Umezono, Tsukuba, Ibaraki 305-8568, Japanm.hamanaka@aist.go.jp

ABSTRACTThis paper describes a method for organizing onset times ofmusical notes performed along a jam-session accompaniment
into the normalized (quantized) positions in a score. The
purpose of this study is to align onset times of a session
recording to quantized positions so the performance data can be
stored in a reusable form. Unlike most previous beat-trackingrelated methods focusing on predicting or estimating beatpositions, our method deals with the problem of eliminating theonset-time deviations under the condition that the beat positions
are given. To quantize polyphonic MIDI recordings of jam
session, we propose a method that uses hidden Markov models
for modeling onset-time transition and deviation. Its main
advantage is that a player’s performance is quantized using amodel learned statistically from session recordings of that
player. Experimental results show that our model performs
better than the semi-automatic quantization in commercial
sequencing software.
Keywords: Quantization, Hidden Markov model, Recognitionof beat and rhythm, Statistical learning

1. INTRODUCTION
We have been constructing a jam session system [1] that allows
a human player to play interactively with virtual players, eachof which is imitating the musical reactions of a human player.
Each virtual player determines its intentions by using a reaction
model that has been acquired from a human player and thenproduces a performance by connecting short phrases selectedfrom a database of phrases. Since this database was preparedby hand, the system could not imitate the player’s characteristicphrases automatically.
Simply cutting out phrases at bar lines and pasting them does
not work well (it creates unnatural performances) because theonset times of notes played by human players intentionally orunintentionally deviate from the ‘normal’ position of onset

times in a score. Before cutting and pasting phrases, we need
to use a quantization method that eliminates the deviation of
onset times and aligns them to the normalized positions1 in ascore.
A quantization method typical of commercial
sequencing software requires the user to specify a fixed gridinterval, or resolution, (e.g., eighth triplet or sixteenth note) towhich onset times are aligned, and each onset time is aligned to
the nearest grid. This method can therefore be used only when
the rhythm structure within a beat is fixed and known (e.g., thebeat contains eighth triplets or the beat contains sixteenth notes).
When the rhythm structure changes frequently, as it does in a
jam session, we need to change the grid interval adaptively.
Several quantization methods have been proposed, and one
using a connectionist model [2] defines a potential energy thatis stable if the ratio of a sum of onset time intervals to a sum ofother intervals is an integer. It is not easily applicable tovarious performances, however, because the potential energy isfixed.
Another quantization method for automatictranscription [3] and beat-tracking methods [4]-[8] focusing on
predicting beat positions cannot be applied to our study directly,
because their problems (estimation of beat position) are
different from our problem (quantization of onset times
performed along a fixed-tempo jam-session accompaniment2).
On the other hand, the results of a study [8] dealing with aproblem similar to ours indicate that the continuous speech
recognition framework using a hidden Markov model (HMM)
provides a useful approach to estimating tempos and beats andto allocating bar lines. The method using that approach
performs better than commercial sequencing software does, but
it deals only with single-note performances and thus cannot be
used to quantize the recording of a jam session that we deals
with.

1
Because in improvisation there is no score to follow, here thenormalized position in a score means the position at which the player
intended to play that note.
2
Quantization of commercial sequencing software is not effective inthis problem, because an onset time that has large deviation is aligned
to an incorrect grid.

In this study, we propose a method that uses the promising
approach proposed in the study [8] and makes it possible toquantize polyphonic MIDI recordings of jam session by using
our own HMM-based model.

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 onset notes because the onset times deviateaccording to performer’s actions and expressions. We canmodel the process generating the deviation by using aprobabilistic model. Then the problem of quantization, which
acquires a sequence of onset times that the player intended froma sequence of deviating onset times that the player actually
performed, can be considered as an inverse problem. This
inverse problem can be solved by using the inverse model
derived from the model generating the deviation of onset times.
A model of onset-time transition and deviation
Let a sequence of intended (normalized) onset times be θ anda sequence of performed onset times (with deviation) be y.
Then a model of generating the deviation of onset times can be
expressed by a conditional probability P( y | θ ) (Figure 1).
Using this conditional probability and the prior probabilityP( θ ), the inverse model can be calculated as Eq. (1) according
to the Bayes’ theorem:

P(θ | y ) =P( y | θ ) P(θ ),P( y )(1)

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

(2)

θ

Formulation of the hidden Markov models
P( θ ) and P(y| θ ) can be formulated as a hidden Markov model(HMM), which is a probabilistic model that generates atransition sequence of hidden states as a Markov chain. Eachhidden state in the state transition sequence then generates anobservation value according to an observation probability.
Modeling of performance:
Target in modeling
We model the onset time of a musical note (i.e. the start
time of the note) and introduce a new model of
distribution of onset times. While the durationtime-based model used in Ref. [8] is limited, ouronset-time-based model is suitable for treating polyphonicperformances, such as those including two-hand pianovoicing and guitar arpeggio.

Figure 1: Forward model and inverse model in the quantization
problem.
Unit in modeling
We use a quarter note (beat) as the unit of each HMM: thetemporal length corresponding to each HMM is a quarter
note. The reason we use the quarter-note unit is todistinguish between eighth triplets and sixteenth notes
within the scope of a quarter note. The three notes ofeighth triplets are located on three equi-divided positions
in a quarter note, while the four notes of the sixteenth
notes are located on four equi-divided positions in aquarter note. An actual performance consisting of asequence of quarter notes can be modeled and quantizedby concatenating the quarter-note-length HMMs.
This quarter-note modeling has the advantages of
reducing calculation time and facilitating the preparationof the large data sets used for training the model.
Unit of quantization
We introduce two different discrete temporal indices, k andi. The unit of k is a quantization unit to describe
performed onset time and is 1/480 of a quarter note, which
is often used in commercial sequencing software. The
unit of i is a quantization unit to describe the intended onset
time and is one-twelfth of a quarter note. It can describe
both eighth triplets and sixteenth notes.
Quarter-note hidden Markov model: Figure 2
shows the HMM used in our study. We model a sequence of
onset times within a quarter note (beat) by using the HMM.
All the hidden states of the HMM correspond to possible
positions of intended onset times, and an observed value thatcomes from a hidden state corresponds to a performed onset
time with deviation. Onset times in a beat are quantized into
12 positions for hidden states, and into 480 positions forobservation values. That is, each component of the HMM isinterpreted as follows.

Transition of intended
Onset time
Observation probabilityof each state

Performed onset time
[time]
beat line
Figure 2.

beat line
Overview of the quarter-note hidden Markov model

Hidden state i: intended onset time. (i =1, …, 12)
Observation k: performed onset time. (k = 1, …, 480)
Transition probability aij: probability that intended onset time
j follows intended onset time i.
Observation probability bi(k): probability that performed
onset time is k and intended onset time is i.
A state-transition sequence begins with a dummy state “Start”
and ends with a state “End.” The following are simple
examples of state sequences.
When the player plays four sixteenth notes within a beat
(Figure 3(a)),
Start -> 1 -> 4 -> 7 -> 10 -> End.
When the player plays three eighth triplets within a beat
(Figure 3(b)),
Start -> 1 -> 5 -> 9 -> End.
When the player plays a two-notes chord at the beginningof a beat (Figure 3(c)),
Start -> 1 -> 1 -> End.
When the player does not play any note within a beat
(Figure 3(d)),
Start -> End.
(a)
(b)
.....
.....

Modeling by a combination of multiple HMMs:
Instead of using a single HMM model, we can use multiple
HMMs. The advantage of using multiple models is that eachmodel becomes simple. Here we propose a model consistingof four HMMs, each of which represents a different type ofrhythm structure within a beat, called inside-beat type. We
define the following four inside-beat types: sixteenth-note type,eight-triplet type, quarter-note type, and no-note type (Figure4(b)). The state transition arcs in the model composed ofmultiple HMMs are simpler than those in a single HMM model(Figure 4(a)).
(a)

A model consisting of a single HMM.

(b)

A model consisting of four HMMs.

sixteenth-note typeeight-triplet type

quarter-note type

(c)

(d)
.....

Figure 3.

.....

Simple examples of state sequences.

no-note typeFigure 4. A model consisting of a single HMM and a model
consisting of four different HMMs.

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

where δ t(i) is the best score (highest probability) of the statetransition sequence θ =( θ 1, θ 2,…, θ t) conditioned that the t-thstate θ t is equal to i, and λ denotes a set of all the parametersof the model. The value of the best score satisfies thefollowing recurrent equation:[]

δ t + 1 ( j ) = max δ t (i ) a ij b j (y t + 1 ) .
i(4)The Viterbi algorithm searches for the optimal sequence of statetransitions by scanning paths on a trellis from left to right(Figure. 5).

Sequence ofperformed onset-times

Figure 5.

[time]

A trellis for finding the optimal state transition.

The horizontal axis in Figure 5 represents the performed onset
times and the vertical axis represents the twelve hidden states ofthe HMM. The optimal state transition sequence can beobtained by choosing one optimal state from 12 possible states
while using Eq. (4) to calculate δ t(i) from left to right on thistrellis. When the state transition passes across a beat line, twodummy states, "End" and "Start," should be inserted.

3. LEARNING MODEL PARAMETERS
By preparing the intended onset times θ (correct data) and theperformed onset times y as training data, it learns a model of
onset-time transition P( θ ) represented as aij and a model ofgenerating the deviation of onset times P(y| θ ) represented as
bj(k).

Training data
In order to estimate the model parameters aij and bj(k), we
prepared two sets of training data, artificially generated dataand human-performance data. Artificial data is mainly used toconfirm that the program works properly.
Artificial data: For each beat we randomly decide
whether the inside-beat type is sixteenth-note type oreighth-triplets type. The number of notes in the beat wasdetermined by random numbers between one and six. Thenthe position of each note was determined randomly: there are
four possible positions in the case of sixteenth notes and threepossible positions in the case of eighth triplets. Finally, using anormal (Gaussian) distribution with the average 0 and thestandard deviation σ , we make the onset times in random dataθ a deviate, and obtain the artificial data ya. Here the three setsof data were generated by using σ = 10, 20, 30 (1 beat = 480).
Human-performance
data:
The
humanperformance data yh are actual MIDI recordings performed bythree human players (guitarists), A, B, and C. Each player
played on a MIDI guitar along a fixed-tempo jam session
accompaniment. The length of each performance was twelve
choruses (1 chorus = 12 bars). Every player performed in two
different tempos: one is 120 M.M. and the other is an arbitrary
tempo decided by that player. Consequently there were 6 sets ofdata.
Correct data: For supervised learning, it isnecessary to prepare correct data, which is the intended onset
times. In the case of artificial data, the onset-time positions
θ a before adding random deviation can be used as the correct
data. For human-performance data, however, we should
prepare the correct data by hands. By using the commercial
sequencing software (Twelve Tone System, Cakewalk Pro
Audio 9) providing a visual piano-roll display, we manuallyquantized each performed note so its position and duration areproper.
Estimation of model parameters
The HMM parameters aij and bj(k) were learned from correct
data θ and the sequence y of performed onset times. Figure6(a) shows a distribution of b5(k) learned from artificial datawith the standard deviation σ = 20 (1 beat = 480) and Figure6(b) shows a distribution of b5(k) learned from the second
performance of the player C (we call it performance C2). The
b5(k) learned from artificial data (Figure 6 (a)) becomes anormal distribution because it was generated by normally
distributed random numbers. The b5(k) learned from theperformance C2 (Figure 6 (b)) is also nearly normally
distributed but is skewed to the right. This shows that a noteon the state 5 tended to be delayed from its original position.
In fact, in the performance C2 the first note of eighth triplets
tended to be played longer and the onset time of the second
note consequently tended to be delayed.

(a) b5(k) obtained from artificial data.
(b) b5(k) obtained from human-performance data.

0.030
0.025

than those for the sequencing software. With the artificial data,
all the correct rates for both the single-HMM model and thefour-HMM model were at least 20 percent higher than those forthe sequencing software.
These results show that our
HMM-based method is effective for both artificial andhuman-performance data.

0.020
0.015
0.010
0.005
0.000

0

1

40

41

80
81

120
121

160
161

200
201

Figure 6: b5(k) obtained
human-performance data.

240 280 320 360 400 440 480
241
281
321
361
401
441
[k: Onset time which the player performed]

fromartificial

data

and

4. EXPERIMENTAL RESULTS
We tested the proposed method on both artificial data andhuman-performance data. We evaluated the performance ofquantization by using the correct rate we defined as follows:(correct rate) =(the number of onsets quantized correctly)(the number of onsets)(5)

Quantization performance of commercial sequencing
softwareTo evaluate the baseline quantization performance ofcommercial sequencing software, we specified three different
grid intervals (eighth triplet, sixteenth note, and sixteenth
triplet) on the software and calculated the correct rate ofquantization for each of them (Table 2). The correct rates
obtained with other grid intervals were worse than the rates
listed in Table 2.
Table 1 also shows the percentages of the four different
inside-beat types contained in each performance, whichpercentages were calculated on the basis of the correct data.
The results listed in Tables 1 and 2 show that the correct ratesof the sequencing software tended to be lower for the
performances containing many sixteenth-note-type beats, suchas all the artificial data and the two human-performance data
sets A1 and C1. The correct rate for the human-performancedata set C2 indicates that the simple quantization witheighth-triplets grids is effective enough for the performance
without sixteenth-note-type beats.
Quantization performance of our method with theparameters learned from the same performance data
Table 2 also shows the correct rates for our method using either
the single-HMM model or the four-HMM model. For most of
the performances, the correct rates for our method were higher

We also compared the performances of the single-HMM modeland the four-HMM model. With human-performance data, thecorrect rates for the four-HMM model were higher than thosefor the single-HMM model; this is because the four-HMM
model can represent the observation probability in further detailby learning three different b1(k) corresponding to the threestates (sixteenth-note type, eighth-triplets type, and quarter-notetype) at the beginning of a beat. With artificial data, thecorrect rates for the single-HMM model and the four-HMM
model were the same because both the b1(k) parameter obtainedby the single-HMM model and the three different b1(k)parameters obtained by the four-HMM model were the same
normal (Gaussian) distribution, which was used for adding
random deviation when generating the artificial data.
Quantization performance of our method with theparameters learned from other performance data.
To evaluate the generalization capability of the method, we
calculated the correct rates obtained when the method was usedwith the following three different sets of the four-HMM model
parameters:(1) parameters learned from the other performance of the sameplayer,(2) parameters learned from the performances of the other two
players, and(3) parameters learned from the artificial data ( σ = 20).
The results, listed in Table 3, show that with the parameter set(1) the correct rates for players A and B were at most 6.4
percent lower than those obtained when using the parameters
learned from the same performance data (at the bottom line of
Table 2) and that the correct rates for player C were about 20
percent lower. This is because the performances C1 and C2
had very different styles (C2 did not contain sixteenth-note-type
beats), whereas the performances A1 and A2 as well as B1 andB2 were of a similar style.
The results obtained with the parameter sets (2) and (3) showthat the correct rates for players A and B were lower than thoseobtained with the parameter set (1) and that the correct rates forthe player C were lower than those obtained with theparameters learned from the same performance data.
These results showed that our method was able to acquire theplayer's characteristic manner of generating onset-timetransition and deviation and that the model parameters learned
from a performance of a player can be applied to performancesof the same player if the performance styles are similar.

[2]5. CONCLUSION
This paper has described a quantization method using a HMM
model of onset-time transition and deviation. This method
makes it possible to estimate the intended onset times (without
deviation) from the onset times (with deviation) performed
along a fixed-tempo jam session accompaniment.
Experimental results showed that the proposed model trainedusing the correct data performed better than commercial
sequencing software.
We plan to use this method to create the phrase database for ourjam session system automatically and also to extend the methodby enabling it to estimate the model parameters from session
recordings without correct data.

[3]

[4]

[5]

[6]

[7]
6. ACKNOWLEDGMENTS
We thank Daisuke Hashimoto, Shinichi Chida, and Yasuhiro
Saita, who cooperated with the experiment as players.

[8]

7. REFERENCES[1]

P. Desain and H. Honing, “The Quantization of Music
Time: A Connectionist Approach”, Computer Music
Journal, vol.13, 1989, pp. 56–66.
H. Katayose and S. Inokuchi, “Intelligent Music
Transcription System,” Journal of Japanese Society for
Artificial Intelligence, vol.5, no. 1, 1990, pp. 59–66. (inJapanese)
M. Goto and Y. Muraoka, "An Audio-based Real-time
Beat Tracking System and Its Applications," Proc. of Intl.
Computer Music Conf., 1998, pp. 17–20.
M. Goto, "An Audio-based Real-time Beat Tracking
System for Music With or Without Drum-sounds,"
Journal of New Music Research, 2001 (in press).
R. Dannenberg and B. Mont-Reynaud, “Following an
Improvisation in Real Time” Proc. of Intl. Computer
Music Conf., 1987, pp. 241–248.
P. Allen and R. Dannenberg, “Tracking Musical Beats inReal Time,” Proc. of Intl. Computer Music Conf., 1990,
pp. 140–143.
N. Saitou, M. Nakai, H. Shimodaira and S. Sagayama,“Hidden Markov Model for Restoration of Musical Note
Sequence from the Performance,” Information Processing
Society of Japan SIG Notes, vol. 99, no. 106, 1999, pp.
27–32. (in Japanese)

M. Hamanaka, M. Goto and N. Otsu, “A Learning
Session System: Statistical Modeling of Player’s
Reaction,” Information Processing Society of Japan SIG
Notes, vol. 2000, no. 19, 2000, pp. 27–34. (in Japanese)
Table 1: Percentages of four kinds of beat included in correct data.
Artificial data
σ =20
σ =30
38.8% 38.8% 38.8%
37.8% 37.8% 37.8%
6.9%
6.9%
6.9%
16.4% 16.4% 16.4%

σ =10

Sixteenth-note type
Eighth-triplet type
Quarter-note typeNo-note type

Player A
A1
A2
21.4%
5.5%
54.2% 68.7%
6.8% 10.1%
17.6% 15.7%

Player B
B1
B2
6.5%
2.7%
58.2% 85.8%
11.9%
6.4%
23.3%
5.1%

Player C
C1
C2
37.2%
0.0%
42.1% 39.7%
5.9% 26.7%
14.8% 33.8%

Table 2: Performance of commercial sequence software and of our method.
Artificial data
σ =20
σ =30
65.6% 58.2% 62.0%
63.9% 67.9% 65.9%
77.1% 70.7% 60.8%
99.6% 95.9% 86.5%
99.5% 95.9% 86.5%

σ =10Commercial sequencing software (eighth triplet)
Commercial sequencing software (sixteenth note)
Commercial sequencing software (sixteenth triplet)

The single HMM model of our method
The four HMMs model of our method

Player A
A1
A2
67.6% 85.6%
54.5% 37.3%
57.7% 48.4%
75.9% 84.8%
82.3% 89.8%

Player B
B1
B2
79.4% 88.6%
36.8% 34.7%
57.8% 51.3%
80.0% 90.5%
81.4% 92.8%

Player C
C1
C2
57.0% 97.7%
70.7% 45.5%
56.1% 82.8%
85.1% 95.0%
85.5% 95.7%

Notes: Underlined rates are those for which the proposed method outperforms the commercial sequencing software.
Table 3: Quantization results obtained using the model parameters for other performances.
Artificial data
σ =20
σ =30
-

σ =10
1) Other performance of the same player2) Performance of two other players
3) Artificial data-

Player A
A1
A2
75.9% 85.3%
70.2% 79.0%
73.3% 53.4%

Player B
B1
B2
79.4% 91.6%
59.2% 73.5%
60.8% 55.2%

Player C
C1
C2
55.5% 77.9%
76.9% 93.1%
82.5% 86.1%