A Connectionist Quantizer
Peter Desain, Henkjan Honing, and Klaus de Rijk

	Center for Art, Media, and Technology	Music Department
	Utrecht School of the Arts	City University
	Lange Viestraat 2B	Northampton Square
	NL-3511 BK Utrecht	UK-London EC1V OHB

[Published as: Desain, P., Honing, H., & Rijk, K. d. (1989). A connectionist quantizer. In Proceedings of the 1989 International Computer Music Conference. 80-85. San Francisco: Computer Music Association.]
Abstract
Time quantization is the process of extracting a metrical score from a musical performance. In (Desain and Honing 1988,1989) we proposed a connectionist quantization network designed to converge from non-metrical performance data to a metrical equilibrium. In this article we discuss several methods for studying this system more closely and describe extensions such as a process model with tempo tracking, and ideas about handling polyphony and multi-tracking. These extensions will result in a full technical implementation of the quantizer. As an appendix a mathematical description is supplied.
Introduction
Time quantization is the process of extracting a metrical score from a musical performance. Expression (e.g. rubato, accelerando), inaccuracies in the timing of a musician, and other performance processes add different kinds of continuous deviations to the notated music, ranging from small to quite large, up to 50% of their metrical values (Povel 1977). 
The traditional approach to quantization is to expand and contract note durations according to a metrical grid that is more or less fixed. Much commercial MIDI software uses this method, with lots of hand adjustment needed to correct absurd notation (sometimes mistaken for being the most accurate notation of the performed rhythm). More sophisticated systems (Dannenberg and Mont-Reynaud 1987, Chowning et al. 1984, Longuet-Higgins 1987) use knowledge of music to decide how to quantize correctly. The knowledge these methods use depends on the specific musical style, and like most AI programs, they break down rapidly when applied to music outside this style (Desain and Honing 1988).
Quantization is still one of the bottlenecks of automatic transcription of performed music. Another important application is real-time interactive music systems, where a computer improvises or interacts with a live performer. And in our research on expressive timing a quantizer is an indispensable part of the environment (called POCO) we are implementing for analyzing, modifying  and generating expressive timing.
Connectionism provides the possibility for new kinds of models which have characteristics traditional AI models lack, in particular robustness and flexibility (Rumelhart et al. 1986, de Rijk 1989). Connectionist models consist of a large number of simple elements, or cells, each of which has its own activation level. These cells are interconnected in a complex network, the connections serving to excite or inhibit others. One broad class of these networks, known as interactive activation and constraint satisfaction networks, generally behave so as to converge towards an equilibrium state given some initial state.
In (Desain and Honing 1988,1989) we proposed to use connectionism for quantization. The quantization model presented was a connectionist network designed to converge from non-metrical performance data to a metrical equilibrium. This convergence is hard wired into the system, and no learning takes place. 
The system (A Review)
The network consists of three kinds of cells: the basic-cell with an initial state equal to an inter-onset interval, the sum-cell to represents the longer time interval generated by a sequence of notes, and the interaction-cell that is connected in a bidirectional manner to two neighboring basic- or sum-cells. Figure 1 shows the topology of a network for quantizing a rhythm of four beats, having its three inter-onset intervals set as initial states of the three basic-cells, labeled A, B, and C, and the two summed time intervals A+B and B+C represented by the corresponding sum-cells. There are four interaction-cells connecting cell A to cell B, B to C, A+B to C and A to B+C respectively. Each interaction-cell steers the two cells, to which it is connected, toward integer multiples of one another, but only if they are already near this state. The two cells receive a small change calculated from the application of an interaction function (see figure 2) to the quotient of their states. These cells accumulate the incoming change signals from the connected interaction-cells. The interaction of a sum-cell with its basic-cells is bidirectional, if the sum cell changes its value, the basic-cells connected to it will all change proportionally and vise versa. In simulating the network this process is repeated until the network reaches an equilibrium. See (Desain and Honing 1989) and the appendix for details.
This system produces good results, but since it seems impossible to give a criterion of 'correct quantization', a rule that is describing the right solutions for every performed rhythm, it is difficult to prove the quantizer is always right . Therefore we define 'correct quantization' as the rhythm that would be noted by human experts, listening to the performed data. Using these criteria we are currently working on a set of experiments to evaluate the quantizer systematically.

Figure 1. Network for three inter-onset intervals.	Figure 2. Interaction function.
Understanding the system
In connectionist models the global behavior emerges from a large number of local interactions. This makes it very difficult to study the behavior of the network in detail. While it may initially seem attractive to use descriptions like 'winning cells', 'pulling harder ', etc., a better understanding of the patterns of change within the network, and the influence of context requires the development of specialized methods. 
An approach that has proved useful is what we call the 'clamping' method (Desain and Honing 1989). In this the behavior of the network is simplified by clamping all of the durations in a network to fixed values - except for one that is allowed to change freely. The method uses the change, that is forced upon this one free cell by the fixed context, to construct a 'potential energy' function. This function has local minima at stable points where the value in the free cell could come to rest. The minima tends to be more pronounced when there is a clear context. Using the 'clamping' method, visualizing the influence of context on the actual quantization process gives us a much better understanding of its emerging global behavior.
A second method visualizes the state space of the system. It only takes rhythms of three inter-onset intervals into account. They are normalized to a fixed total duration. In this representation every rhythm of three inter-onset times can be represented as a point in a two dimensional state space. Drawing the rhythm after each iteration yields a trajectory towards a stable point in this space: the quantized version. Plotting the trajectories of different rhythms exhibits the behavior of the network and the stable attractor points in this two dimensional space. They are positioned on straight lines that represent rhythms with an integer ratio of two durations or their sums (A=B, A+B=C, 2A=B, etc.). Figure 3 shows the state space diagram. One can see relatively large area's around the simple rhythms and relatively small area's around more complex rhythms. 
A third method amounts to a systematic exploration of the parameter/performance space. While choosing a fixed rhythm, the quantizer is run each time with a different set of parameters. The performance (success/failure and the number of iterations needed) is monitored and studied as a function of the parameters. This method shows the dependence of the behavior on the parameters and the sensitivity of the model for parameter changes. 
However, the best understanding of such a complex system arises from a mathematical description where one can search for analytical solutions, prove convergence and stability, etc. The present state of the work done on a mathematical description is given in the appendix, but much remains to be done. 
Graceful degradation
When an error is made in the simple quantizers that are part of commercial MIDI sequencer software, large parts of the score succeeding the error are deformed. Navigating through the resulting mess becomes virtually impossible. On the other hand, when the connectionist quantizer breaks down in a complex situation it is often able to maintain musical integrity and consistency at higher levels. The resulting error will only generate a local deformation of the score. This deformation will be a simplification of the rhythm - not a more complex notated fragment. Furthermore it is possible to edit a wrong note by hand and run the quantizer on the new data giving it a chance to correct the local score (This, and other ideas where generously generated by David Bristow).
A second way in which our system exhibits graceful degradation is when exposed to more difficult rhythms. It will be able to quantize correctly when they are performed with high accuracy or consistency.  A more complex rhythm implies a smaller range of deviations that can be captured by the quantizer.

Figure 3. Trajectories in state space of a rhythm of three notes adding up to 3/4. The peak   parameter is set to 2 and 6 respectively.
Process model and tempo tracking
A system that takes all of the data into consideration is, of course, not feasible when the aim is to develop a robust technical tool for near real-time quantization of longer pieces, and neither is such an algorithm plausible as a cognitive model. Luckily, it proved quite simple to design a process version of the quantizer in which it is operating upon a window of events where new inter-onset intervals shift in and score durations shift out, being quantized on the way through. In such a model tempo tracking becomes an absolute necessity since slow global tempo changes spanning a time lapse larger then the window can not be operated upon. 
The architecture we invented for this system consists of two separate modules, the quantizer and a tempo curve fitter. They work in mutual cooperation, communicating via a window of inter-onset intervals. First the quantizer tries to quantize the data. The resulting change is passed, together with the original data to the curve fitter. This process then tries to explain the changes proposed by the quantizer as a change in the global tempo profile by fitting a third order polynomial to the quantized (score) and original (performance) data. Therefore any consistent global change in tempo is taken care of by this module. The resulting rhythm will be simpler to operate upon (because global tempo changes are already extracted) and the quantizer is given a chance to remove the remaining deviations from a metrical score (e.g. small scale rubato, timing errors, inaccuracies of the performers motor system). When a new duration comes in it is first passed through the global tempo model. On the basis of the expected global tempo its value is reinterpreted. Then the whole cycle starts again. As a result a rhythm can be quantized differently depending on the context established by the preceding data. Which of course is the same as we would expect from human listeners. 
Polyphony
The system described so far is unable to deal with inter-onset times that may move towards zero (as in chords or music with multiple voices). Although it may be possible to use other means to 'clean' the data before quantizing it, such as symbolic rules for recognizing chords chunks, the general connectionist approach used in the quantizer seems a much better alternative. Since the context can be taken into account when deciding if e.g. something is to be considered a chord with some spread or a regular run of notes or an arpeggio that has its own metrical structure. Of course, note durations then have to be supplied as well. We are currently experimenting with multiple interlocking networks that can handle polyphony. Although the preliminary results seem to be promising, describing the algorithm here would be premature.
other Applications
Quantization has many applications in different domains.  
In the domain of signal processing, extracting a fundamental pitch from a complex spectrum is a notoriously difficult problem. A good quantizer could pre-process the data by moving the harmonics to their 'perfect' positions. 
In the domain of graphical user interfaces and desktop publishing the quantizer could be used for cleaning up pictures, schematics and lay-outs, using harmonic ratio's as a composition rule (Desain 1988).
An application of the system in music composition is the use of the state space diagrams to generate interpolations between rhythms (Saariaho 1984) that are perceptually smooth, or to guide the search for rhythms that are ambiguous or maximally un-metrical.
Conclusion
It seems very important to have specialized tools available to study and understand the behavior of the connectionist model for quantization. Although the methods presented in this article gained much insight and understanding, a mathematical analysis is still needed. Considerable work was done in extending the system to a process model in combination with a tempo tracker. This process model with tempo tracking and the ideas of handling polyphony and multi-tracking will contribute to a complete technical tool for quantization.
Acknowledgements
We would like to thank here all the colleagues that helped us with comments and suggestions: Dave Bristow, Jim Grant, Christopher Longuet-Higgins, Steve McAdams, Dirk-Jan Povel, and especially Eric Clarke for his enthusiastic support. We are grateful to Johan den Biggelaar, Nicoline Bruin, and Ton Hokken in Utrecht and Eric Clarke in London who made this research possible. 
Appendix
In this appendix the mathematical details of the quantization method will be presented. The change of a ratio is given by the interaction function F, defined as

	F(r) = R(r)SUP7(d) (R(r) - r) |2(r - E(r) - 0.5)|Sup7(p)	(1)

where R and E are resp. the round-off and the entier function.
F consists of a polynomial section around each integer ratio. The first term of F realizes the decreasing magnitude with increasing ratios by scaling each section with a multiplication factor that is a negative power of the integer ratio. This power is called the decay parameter d, and is typically between -1 and -3. The second term of F signifies the change needed for the ratio to become integer. The third term expresses the rate of change being higher when the ratio is already near a integer. The order of this last term, called the peak parameter p, is typically between 2 and 12. F is shown in Figure 1.
There are some constraints for interaction functions. First, the function and its derivative should be 0 in the middle between two integer ratios. In this region it is not clear if the integer ratio is above or below the proper goal, so no attempt is made to change the ratio. Second, the derivative around integer ratios should be negative to steer the ratio towards the integer, but a value greater than -1 to prevent overshoot, resulting in oscillations.  
The actual change of time intervals is calculated as follows. Suppose rold is the ratio of two durations aold and bold, with aold≥bold . Thus the new ratio rnew is the ratio of two new durations anew and bnew and given by

	F(anew,bnew)  =  F(aold,bold)  + F(F(aold ,bold ))	(2)

The aim is that the total duration does not change, or 

	aold + bold  =  anew +bnew 	(3)

by letting D= bold - bnew = anew - aold , we can write

	anew = aold + D       and        bnew  = bold -  D	(4)

Substitution of (4) in (1) and solving for D gives

	D = bold  F(F(F(aold ,bold )),1 + F(aold ,bold ) +F(F(aold ,bold )))	(5)

This yields a suitable increment to apply to the durations, which keeps their sum constant but steers their ratio to a nearby integer multiple. Note that the denominator is never zero, because -1 < F(r) for all r > 1.
Now suppose a rhythm is given by a vector of durations x = (x1,...,xN). Let us first consider a simplified network, i.e. a network without sum-cells. For each ratio F(xi,xi+1) , a Dis computed, and is defined by

	Di =  h(xi,xi+1) F(F(g(xi,xi+1)),1 + g(xi,xi+1) +F(g(xi,xi+1)))	i = 1,...,N-1			(6)

where h(x,y) and g(x,y) resp. are defined by
	h(x,y) = BLC{(A(x      if x > y,  -y     otherwise))                 g(x,y) =  BLC{(A(F(x,y)       if x >y,     F(y,x)       otherwise))	(7,8)

The functions g and h are introduced because of the assumption in (2), is that r > 1.
Now the new duration vector x* can be computed by 

	x*1 = x1 + D1
	x*i = xi + Di - Di-1 	i = 2,...,N-1	 (9)
	x*N = xN - DN-1 

For the complete network the computations are much more complex. The formulas are

	x*i = xi +  o(sdo20(A(k=1,k£i)),sup12(N-1),sdo3(S)) o(sdo26(A(l=1,l≥i,l≥k)),sup12(N-1),sdo3(S)) o(sdo20(A(m=2,m>l)),sup12(N),sdo3(S))  D(xk,...,xl,xl+1,...,xm) F(xi,xk+...+xl)
	                 -  o(sdo14(A(k=1)),sup12(N-1),sdo3(S)) o(sdo26(A(l=1,l<i,l>k)),sup12(N-1),sdo3(S)) o(sdo26(A(m=2,m≥i,m>l)),sup12(N),sdo3(S))  D(xk,...,xl,xl+1,...,xm) F(xi,xl+1+...+xm)	(10)
with the following definitions

	D(xk,...,xl,xl+1,...,xm) = F(h(xl(k,l),xl(l+1,m)) F(g(xl(k,l),xl(l+1,m))),1 + g(xl(k,l),xl(l+1,m)) +F(g(xl(k,l),xl(l+1,m))))	(11)

with xl(k,l)= ISU(i=k,l,xi)  and xl(l+1,m) = ISU(i=l+1,m,xi) , and h,g defined as in (7).

Now we can compute, given a duration vector x, a new duration vector x*, by applying (10) to all the components of x. Lets define a vector function D which performs this computation, i.e.

	x* = D(x) = x + D(x),	(12)

where D in this case is a kind of 'change function'. With a certain starting vector x(0), we can construct a row of vectors, x(0), x(1), x(2), x(3), x(4), ... using D:

	x(t+1) = D(x(t)) = x(t) + D(x(t)) 	(13)

which hopefully converges to a equilibrium state x defined as

	D(x) = x        or equivalently           D(x) = 0      ( the zero vector)	(14,15)

In the simplified network (9) it can easily be seen that condition (14) only holds when all Di  are zero. This implies that the interaction function F has to be zero for all ratios, which in turn means that all ratios have to have integer or integer plus 0.5 values. When the sum cells are introduced the system is much harder to analyze. All equilibrium points of the simplified system are also equilibrium points of the complete system, but there are many more of them. In fact it is not clear yet what exactly are the (stable) equilibrium points of the complete system.
Another point worth noting is the implication of formulas (2) and (5), i.e. the basic assumption of the system. From (2) it follows that the new ratio rnew only depends upon the old ratio rold, and not on the absolute values of aold and bold. However, the change in the durations, given by D in (4) depends upon the absolute value of bold. This is not a problem when all durations in a rhythm are of the same size, but normally this is not the case. And large corrections to large durations may introduce errors in smaller durations. Indeed, when we tried to implement the system with (5) (or better, with (6) and (10)), the results tended to be inaccurate or become unstable. Therefore instead of having a different multiplication factor bold or h( , ) for every ratio we looked for a uniform factor for all ratios. The most natural choice was the minimum duration of the duration vector. In other words we redefined h as 

	h(xl,xk)   =   BLC{(AAL(    o(sdo12(A(1£i£N)),min) xi      if xl ≥ xk , -  o(sdo12(A(1£i£N)),min) xi     otherwise))	(16)

References
Chowning, J., L.Rush, B. Mont-Reynaud, C. Chafe, W. Andrew Schloss, and J. Smith, 1984. "Intelligent systems for the Analysis of Digitized Acoustical Signals."  CCRMA Report No. STAN-M-15.

Dannenberg, R. B. and B. Mont-Reynaud, 1987. "An on-line Algorithm for Real Time Accompaniment."  In: Proc. ICMC 1987. San Francisco: CMA.

Desain, P. and H. Honing , 1988. "The Quantization Problem: Traditional and Connectionist Approaches. " Proceedings of  the first AI and Music Workshop. St. Augustin, Germany.

Desain, P. and H. Honing , 1989. "Quantization of Musical Time: A Connectionist Approach. " Computer Music Journal 13(3). Mass.:MIT Press.

Desain, P. 1988. "Direct Manipulation and the design of User Interfaces" Journal for the Integrated Study of AI, Cognitive Science and Applied Epistemology 5(3-4). Ghent: Comm. and Cogn. 

Longuet-Higgins, H.C., 1987. Mental Processes. Cambridge, Mass.:MIT Press.

Rijk, Klaus de 1989. "Neural Networks: A Mathematical Point of View"  Report RR/07, CAMT, Utrecht.

Rumelhart, D.E. and J.E. McClelland (Eds.), 1986. Parallel Distributed Processing. Cambridge,: MIT Press. 

Saariaho, K. 1984. "Shaping a Compositional Network with Computer" Proc. ICMC  1984 . Berkeley: CMA.