Excerpts from this page were published as:

Mary Farbood and Bernd Schoner. "Analysis and Synthesis of Palestrina-Style Counterpoint Using Markov Chains." Proceedings of International Computer Music Conference. Havana, Cuba. 2001.

Summary:

Introduction

Sixteenth-century counterpoint, with which the name of Palestrina has almost become synonymous, has long been held by musicians and theoreticians as an exceptionally elegant form of composition which has both musical and pedagogical value. Modeled after this style, species counterpoint was first introduced by J. J. Fux in his 1725 treatise, Gradus ad Parnassum. Fux codified the study of Palestrina-style counterpoint by presenting five categories of instruction, called species.

Gradus was a standard counterpoint text studied by countless musicians during the eighteenth and nineteenth centuries. However, from a stylistic viewpoint, it did not present an adequate approximation of Palestrina's music [SS89]. This goal was eventually realized by Knud Jeppesen, who believed that counterpoint must be studied with as much correspondence between written exercises and composition as possible [Jep31]. In other words, counterpoint had to be learned within the context of a specific musical style.

This project, called Palestrina, presents a framework for generating music in the style of Palestrina using Markov models. A set of species counterpoint rules as outlined by Jeppesen is implemented in the form of probability tables which are then used as state-transition matrices for the Markov models. In the next step, the probability tables are estimated from given counterpoint examples.

Palestrina uses Markov chains, a subclass of graphical models to provide the the necessary structure for representing the compositional process of generating counterpoint. Markov chains provide the flexibility of integrating deterministic and probabilistic rules in the same model and can be trained on experimental data.

Prior Work

Kemal Ebcioglu (1980) created a rule-based system to generate fifth-species counterpoint given a cantus firmus that encapsulates each rule in a simple LISP function [Ebc80]. An enumeration algorithm is used to generate as many solutions as possible given a time limit. The enumeration algorithm uses additional rules to output the more "musical" solutions first (added due to the fact that solutions blindly following the rules were deemed "grossly insufficient"). These include rules for producing better musical contours such as the following:

     If the melody skips, and if the notes within the scope of this skip 
     have not already been sounded, then they must eventually be sounded 
     before the end of the melody.

David Lewin (1983) has written a program that generates first-species counterpoint using his own "Global Rule" which resembles Ebcioglu's musical countour rule [Lew83]:

     For every note X of the counterpoint line lying above (below) the 
     cadence tone, some note lying one step lower (higher) than X must 
     appear in the line at some point subsequent to X.

Gjerdingen (1988) approaches the problem from a musician's point of view, as opposed to a programmer's [Gje88]. His system, PRAENESTE, is based on the idea that, just like a sixteenth-century singer improvising on a cantus, the computer should work forward in time without the benefit of being able to back up and start over. In response to each new contrapuntal situation, PRAENESTE uses a small number of concrete musical schemata to provide for itself a selection of correct melodic patterns. Given the preceding material, it selects a single melodic path that best satisfies a number of the higher-level aesthetic constraints. For PRAENESTE, being correct is a matter of course; its main concern is with style (as described by Jeppesen). PRAENESTE is quite successful, and the results resemble Jeppesen's examples (especially those of the first three species) remarkably. In the case of fifth species, however, the musical differences are still considerable.

William Schottstaedt (1989) implemented all five species with up to six voices [Sch89]. His program follows Fux's guidelines and rules as closely as possible. These rules were extended and modified until the results acceptably resembled Fux's examples. Since most of the rules are not absolute, a penalty system is used to assign them relative degrees of importance. If at any given time the total penalty exceeds a certain amount, that particular path is abandoned. For example, an absolute rule such as the restriction of parallel fifths has a infinite penalty. A "very bad infraction" like direct motion to an octave has a penalty of 200, while a stylistic infraction such as a repeated pattern of three notes only has 4. The penalty values arise from both Fux's commentary as well as experience running the program. The search time is optimized by taking the branch of the search tree which has the least penalty. If the path fails, then the program backs up and tries the next best branch. Unfortunately, the first solution found may not be very good, in which case a new search is made with a different starting interval in order to maximize the chances of finding a truly new solution. Even with this approach, the compute-time for fifth species solutions still remains high. Schottstaedt also admits that the program has no provision for starting a melody with a rest. Neither does it favor invertible counterpoint and imitation. It tends to "let voices get entangled in each other" and make "inadequate judgments about overall melodic shapes."

The approach used in Palestrina is considerably different from the cited work, because it (a) uses a probabilistic description of the problem and (b) infers its model from data which ensures that the result is musical assuming that the training examples themselves are musical.

Synthesizing the counterpoint

Dynamic Programming

Figure 1: Trellis state diagram. The vertical states n correspond to note intervals relative to the cantus note at time t. The time t corresponds to time steps going forward. Pj,i(t,r) denotes the probability of transition from state i at time t to state j at time t+1 with respect to rule r.

The first step is the construction of a state trellis diagram where the states describe the possible chromatic notes in the counterpoint (Fig. 1). The counterpoint is constrained to be above or below the cantus and the permissible note range spans a major tenth above (or below) the highest (or lowest) cantus note. Hence the number of states in the trellis equals the chromatic range of the cantus plus 16 (a major tenth is equivalent to 16 minor seconds). Musical constraints on the counterpoint are then formalized by a mix of transition probabilities and state probabilities conditioned on the cantus. For example, the unconditional likelihood of a harmonic interval and the probability of a melodic interval given the previous melodic interval are specified.

While most rules can be realized based on a first-order Markov chain, some require a second-order system. A basic first-order structure has been implemented, but the model also allows for second-order considerations by looking one step ahead and choosing optimal solutions with respect to the next time step.

In the synthesis application, the most likely path through the trellis structure given the underlying cantus and transition rules is calculated. Evaluating every possible path would be computationally prohibitive. However, the problem is made tractable by using a dynamic programming approach commonly known as the Viterbi algorithm. The Viterbi algorithm is based on the insight that the most likely past state sequence leading into any one state is independent from future states. There are a number of variants that are used for different problems, one of the most common applications is finding the most likely state sequence in a Hidden Markov model - that is, a Markov Chain with undefined states at the time of building the model. Another common application is for demodulating convolved communication channels [Vit67].

Going forward in the chain, previous path probabilities are multiplied with the transition probability of the new update, and the path that generated the highest joint probability is stored. At any time step τ, the only considerations are the path leading into state τ-1, the probability associated with that sequence, and the transition probabilities at time τ. After the last transition occurs, the sequence with the highest probability is selected as the solution [Ber95].

Probabilistic counterpoint rules

• The harmonic table determines whether the interval between the counterpoint note and its respective cantus note at any time τ is permissible. The likely intervals - third, sixth, tenth - are assigned higher probability values, whereas the forbidden intervals are assigned zero (Table 2). For the first cantus note, only perfect intervals are permitted, and for the last, only unisons and octaves.
  
  
• The melodic table describes the likelihood of a melodic interval created by two consecutive counterpoint notes being followed by any other melodic interval (Table 1). This table not only implements the rules determining legal melodic intervals and melodic patterns, but also has a profound effect on the shape of the line as a whole, since stepwise motion (among other such desirable behavior) is heavily weighted.
  
  
• The cadence table, in conjunction with the chromatic table, ensures that there is an appropriate cadence at the end of each example. Only stepwise motion is permitted to the final note, and stepwise motion to the penultimate note is given very high probability.
  
  
• The chromatic table gives very low weight to chromatically-altered notes (except the penultimate) - low enough that they will not be used unless there are no other solutions. For the penultimate note, only chromatically-altered notes, with the exception of Eb, are permitted, in order to provide a leading tone (the E-based Phyrgian mode does not have a raised leading tone).
  
  
• The good parallel motion table prevents too many consecutive parallel thirds, sixths, and tenths. The probability that three in a row can occur is small.
  
  
• The approaching motion table prohibits approaching a perfect interval in direct motion (also known as "hidden" fifths or octaves).
  
  
• The departing motion table prohibits leaving a unison in direct motion. This also has the added advantage of preventing the overlap of voices.
  
  
• The general motion table assigns contrary motion high probability, oblique and direct motion low probability.
  
  
• The leap and climax tables return probabilities of zero or one. The leap table returns zero if both the cantus and the counterpoint are leaping simultaneously in the same direction and have done so previously (only one such occurrence is permitted). The climax table determines whether a pitch is acceptable given restrictions set by the chosen climax position of the counterpoint.

Analysis of counterpoint

Experimental results

Figure 3: Screenshot of the Palestrina application.

Much of the experimentation centered around deciding appropriate transition probabilities for the rule tables. While it was easy to make transitions legal or illegal, based on the outlined rules, it was more interesting and time-consuming to weight the probabilities properly in order to get musical results. Subtle changes in the table values resulted in very different solutions. Also probabilities had to be weighted not just with respect to other values in the same table but with respect to competing rules. For example, one possible situation where there are two acceptable solutions might be the following: (1) the penultimate note is approached in stepwise motion (ideal) but four consecutive parallel sixths result (acceptable, but not ideal) vs. (2) the penultimate note is not approached in stepwise motion (acceptable, but not ideal) but there are fewer consecutive parallel sixths. This is just one example of an aesthetic decision which can be reflected in the probability values.

During the course of implementation, it became apparent that some of the earlier tables were unnecessary. For example, there was initially a table which restricted parallel fifths and octaves. This was later rendered superfluous by the approaching motion table listed above (parallel motion is a special case of direct motion).

Another influential aesthetic factor was climax placement. As recommended by Jeppesen, the climax note should be unique as well as higher in pitch than all other notes. The program either tries each possible climax time until a satisfactory (if any) solution is reached, or the user specifies where the climax point should be. This rule helps produce surprisingly musical results.

Sound examples

• Example 1 - Dorian mode
• Example 2 - Dorian mode
• Example 3 - Phrygian mode
• Example 4 - Phrygian mode
• Example 5 - Mixolydian mode

Conclusions and Future Work

References

[SS89] Felix Salzer and Carl Schachter. Counterpoint in Composition. Columbia University Press, New York, 1989.

[Jep31] Knud Jeppesen. Counterpoint, the Polyphonic Vocal Style of the Sixteenth Century, 1931.

[Jor98] Michael Jordan. Learning in Graphical Models. MIT Press, Cambridge, Massachusetts, 1998.

[HI58] Lejaren Hiller and Leonard Isaacson. Musical Composition with a High-Speed Digital Computer. Journal of the Audi o Engineering Society. 1958.

[Ebc80] Kemal Ebcioglu. Computer Counterpoint. ICMC, 1980.

[Lew83] David Lewin. An Interesting Global Rule for Species Counterpoint. Theory Only, 6.8. March 1983. pp. 19-44.

[Gjer88] Robert Gjerdingen. Concrete Musical Knowledge and a Computer Program for Species Counterpoint. Explorations in M usic, the Arts, and Ideas: Essays in Honor of Leonard B. Meyer. Pendragon Press, Stuyvesant, 1988.

[Sch89] William Schottstaedt. Automatic Counterpoint. In: Current Directions in Computer Music Research. Matthews & Pierce eds. MIT Press, 1989.

[Ber95] Dimitri P. Bertsekas. Dynamic Programming and Optimal Control. Athena Scientific, Belmont Massachusetts, 1995.

[RJ86] L.R. Rabiner and B.H. Juang. An Introduction to Hidden Markov Models. IEEE ASSP Magazine. 1986. pp 4-16.

[Vit67] Viterbi, A. J. Error bounds for convolutional codes and an asymptotically optimal decoding algorithm. IEEE Transactions on Information Processing, 1967. 13:260-269.