Can music cognition benefit from computer music research?
From foot tapper systems to beat induction models
Peter Desain & Henkjan Honing

[Desain, P., & Honing, H. (1994). Can music cognition benefit from computer music research? From foot-tapper systems to beat induction models. In Proceedings of the ICMPC 1994. 397-398. Liege: ESCOM. ]

In music cognition research several theories have been proposed that are concerned with the perception of different types of temporal musical structure (e.g., meter, rhythm, and phrase structure). Often these models, and the models that deal with other aspects of music like melody and harmony, assume a successfully identified beat. For example, a beat can give a first rating of importance to musical events and suggest viable boundaries for chunking, it indicates the level of “focus” in the metrical structure (the level at which events pass at a moderate rate, i.e., tactus), it gives clues on whether the tempo changes and it often functions as a basis to distinguish between the canonical aspects of time and the continuously variable performance aspects (i.e., expressive timing). This makes beat induction  –the process yielding a perceived pulse marking off durational units in the stimulus pattern– a fundamental aspect of many models of music cognition.
Beat induction  or Foot-tapping is a example of a simple cognitive task that is nevertheless hard to model computationally. As result it has been an important issue in interactive computer music, with many different approaches explored. The systems that were developed all use a more or less pragmatic or technological approach (see, e.g., Boulanger, 1990; Chafe, Mont-Reynaud & Rush, 1989). Some of them derive a beat from a stream of musical events in a live, interactive performance situation (Dannenberg & Mont-Reynaud, 1987; Vercoe, 1985). Especially this use in a live performance forced the designers to think of solutions on problems that are rarely touched in cognitive models. In this paper we will give an overview of some aspects involved in this process and the most important models. We restrict ourselves to computational models and focus on the many theories that assume that beat induction is viable considering timed events alone (ignoring information about dynamics, pitch, etc.).

The concerns
From music theory and psychology of music several aspects and concerns are known with regard to beat induction. However, they are never addressed all at the same time by any one computational model.
In music, a retrograde rhythm is often not recognized as such, and rhythms presented in time reversed order work differently (e.g., they induce a different meter). The source of the importance of the time direction lies in the fact that whence induced from the perceived material, a beat is a persistent mental framework that will guide the perception of new incoming material. This duality, where a model needs to be able to infer a beat from scratch but also to later let an induced beat percept guide the organization of more incoming material is hard to model. 
The global tempo at which material is presented can cause a different interpretation. A different tempo influences the focus to another level of the musical structure. In ambiguous patterns, where different beat organizations seem possible, the tempo will favor one or the other, related to the preferred rate for beats (Fraisse, 1982).
In music, with only a few notes (5-10) a strong sense of beat can be induced. This suggests that beat induction is a fast process. The models that concentrate on initial beat induction cannot rely on detecting any statistical regularity.
Many models of beat-induction that operate on performance data directly and that allow for changes in tempo and expressive timing consider timing as jitter or timing noise. However, in performances often meter and beat are communicated, among other means, by timing (Sloboda, 1983). Thus advanced beat induction models may actually perform better if they make use of the information present in the expressive timing, instead of attempting to get rid of it. Furthermore, expressive timing is hard to remove by pre-processing. 
The perception of a beat not carried by an event, a syncopation, is an important aspect in music, often linked to notions of perceived tension or beauty of temporal patterns. Most models either minimize the presence of syncopated events or prevent syncopation from happening at all. However, it is very well possible that after induction of a stable beat, for a relatively long period of time syncopation occurs. Thus, a sophisticated model has to predict how and when a syncopation can be heard as such.
A rhythmic fragment can receive more interpretations at same time. It is difficult to model such ambiguity in a symbolic paradigm. That might be the reason why this issue is often ignored. 
Some theories tend to model the perceiver more like a musicologist studying the score with access to the whole piece at once, instead of a first-time listener. But even if a listener process is modeled, often the computation is implicitly allowed to “listen ahead” of time. This notion of being “on-time” must be made explicit, in order to implement a causal “foot tapper”. The issue can be settled outside of real-time (but in “honest-time”) if computation speed is a practical limit. A further complication arises because any practical device (be it a real foot or some sort of electro-mechanical contraption like a MIDI piano) needs to be sent its commands ahead of time because of inherent transmission and operation delays. The notion of anticipation and planning cannot be evaded here. 

A taxonomy of the formalisms used
A first approach is the rule-based paradigm. Longuet-Higgins & Lee (1982) and Lee (1985) are systems for initial beat-induction. These models take a sequence of score durations and start out with the first note as the beat, and incorporate a small set of rules derived from musical intuition that look for patterns in the input in relation to the current beat and can shift, double and stretch the beat. Their behavior is studied in Desain, Honing & Longuet-Higgins (1994). 
A second approach optimizes the fit of a (steady-state) beat with the input pattern (score durations). All possible beats are rated for their fit, choosing the best one. Povel & Essens (1985) elaborate a theory along these lines using rules for subjective accent in rating the fit, and provide some empirical evidence. It can express ambiguity by assigning equal ratings but is unaware of global tempo and expressive timing. In Parncutt (in press) the dependency of rhythm perception on global tempo is included in the model. Both models are applied to cyclic patterns only.
A third (traditional AI) approach is taken by the musical parser of Longuet-Higgins (1976). It searches beat by beat through meter-space (with some backtracking) and matches a meter with the incoming music material, avoiding syncopations. It is the only model that integrates the use of performance timing with high level symbolic processing. It has to be supplied with an initial beat estimate.
A fourth approach tackles the tracking of tempo with methods from control theory, essentially feeding back an error estimate into the tempo state (e.g., Dannenberg & Mont-Reynaud, 1987). From the measurements of the tempo response of a human accompanists confronted with a sudden tempo change, the plausibility of artificial tempo-trackers can be deduced (Dannenberg, 1993).
A fifth method decomposes the problem as a distributed system based on continuous calculations for every time-interval implicit in the input. In Desain (1992) such a model is presented that projects curves of expectancy into the future. By feeding high peaks in expectancy back into the data –as if a beat had been heard– persistent syncopation can be handled and a systematic smear of the peaks by expressive timing helps the beat induction process. 
A sixth approach decomposes the problem differently and formalizes the calculations as a collection of complex agents in the Minskian sense (e.g., Pennycook, Stammen, & Reynolds, 1993; Rowe, 1993, Rosenthal, 1992). In this method it is more easy to let beat induction benefit from knowledge from other sources (e.g., harmony).
A seventh way is to incorporate neural net interactions between possible beat hypothesis - each with its own activation level and connections of mutual inhibition (e.g., Miller, Scarborough & Jones, 1992). Note that some sort of measure for goodness of fit between beat and input pattern is used - as such these methods can be seen as direct extensions of the more abstract optimizing ones.
An eight more global method is the statistical approach in which a set of scores of know beat and meter is used to collect statistical regularities. In Palmer & Krumhansl (1991) these take the form of profiles of probability of events occurring at the different positions in the bar, implicitly stating a method for detecting meter in new pieces. In Brown (1993) autocorrelation is used to study regularity in rhythmic patterns and link them to durations of the metric levels. 

Conclusion and further research
Both the cognitive and technological approach have not been able to arrive at a general, robust beat extraction method. It is difficult to proceed from the current situation. Many models have evolved and several complicated computer music systems exist that behave reasonably, but none of the systems has attained the generality and robustness strived for. Detailed study of the performance and behavior of these models aimed at finding ways of generalization and unification, is the best way to further research. To initiate this effort we organized a platform (via electronic mail) concentrating on computational “foot tapping” models. A special session during the 1994 International Computer Music Conference is planned. The newsletter (Shoes News) of this work group can be obtained via desain@nici.kun.nl.

References 
Boulanger, R. (1990) Conducting the MIDI Orchestra, Part1: Interviews with Max Mathews, Barry Vercoe and Roger Dannenberg. Computer Music Journal ,14(2).
Brown, J.C. (1993) Determination of meter of musical scores by autocorrelation. J. Acoust. Soc. Am., 94(4), 1953-1957.
Chafe, C. , B. Mont-Reynaud and L. Rush (1989) Toward an Intelligent Editor of Digital Audio: Recognition of Musical Constructs. In C. Roads (ed.), The Music Machine. MIT Press, Cambridge, MA.
Dannenberg, R.B. & B Mont-Reynaud (1987) Following an improvisation in real-time. In Proceedings of the 1987 International Computer Music Conference. 241 - 248. San Francisco: International Computer Music Association.
Dannenberg, R.B. (1993) Music Understanding by Computer. In Proceedings of the IAKTA Workshop on Knowledge Technology in the Arts. 41-55. Osaka: IAKTA/LIST.
Desain, P. (1992) A (de)composable theory of rhythm perception. Music Perception, 9(4), 439-454.
Desain, P., Honing, H. & H.C. Longuet-Higgins (1994). Rule-based models of initial-beat induction and an analysis of their behaviour. To appear in Proceedings of the 1994 International Computer Music Conference. San Francisco: International Computer Music Association.
Fraisse, P. (1982) Rhythm and Tempo. In D. Deutsch (ed.) The Psychology of Music. New York: Academic Press.
Lee, C. S. (1985) The rhythmic interpretation of simple musical sequences: towards a perceptual model. In R. West, P. Howell, & I. Cross (eds.) Musical Structure and Cognition. 53-69. London: Academic Press.
Longuet-Higgins, H.C. & C.S. Lee (1982) Perception of musical rhythms. Perception. 11, 115-128.
Longuet-Higgins, H.C. (1976) The Perception of Melodies Nature 263: 646-653. Also in Longuet-Higgins, 1987.
Longuet-Higgins, H.C.(1987). Mental Processes. Cambridge, Mass.:MIT Press.
Miller, B. O., D. L. Scarborough, & J. A. Jones (1992) On the perception of meter. In M. Balaban, K. Ebcioglu, & O. Laske (eds.), Understanding Music with AI: Perspectives on Music Cognition. 428- 447. Cambridge: MIT Press.
Palmer, C. and C.L. Krumhansl (1990) Mental representations of musical meter. Journal of Experimental Psychology: Human Perception and performance 16(4), 728-741.
Parncutt, R. (1987). The perception of pulse in musical rhythm. In A.Gabrielsson (ed.), Action and Perception in Rhythm and Music 127-138. Royal Swedish Academy of Music, Stockholm.
Parncutt, R. (in press). A perceptual model of pulse salience and metrical accent in musical rhythms. Music Perception.
Pennycook, B., D.R. Stammen, & D. Reynolds (1993) Toward a computer model of a jazz improviser. In Proceedings of the 1993 International Computer Music Conference. 228-231. San Francisco: International Computer Music Association. 
Povel, D.J. & P. Essens (1985). Perception of temporal Patterns. Music Perception. 2(4):411-440
Rosenthal, D. (1992) Intelligent rhtyhm tracking. In Proceedings of the 1992 International Computer Music Conference. 227-230. San Francisco: International Computer Music Association.
Rowe, R. (1993). Interactive Music Systems: Machine Listening and Composing. MIT press: Cambridge.
Sloboda, J. (1983) The communication of musical metre in piano performance. Quarterly Journal of Experimental Psychology 35.
Vercoe, B. (1985) The synthetic performer in the context of live music. In Proceedings of the 1985 International Computer Music Conference.199-200. San Francisco: Computer Music Association.