Denna Lawrence and Dr. Sean Warnick, Department of Computer Science
Project Purpose
I developed an algorithm that generated musical accompaniment to real-time improvisation from a soloist and analyzed my results using well-defined conditions of harmonization.
Project Background
Many electronic keyboards have a feature called “auto accompaniment”. When in that mode, the keyboard plays a chord when the performer presses a single key on the keyboard. For example, if the performer plays the note “C”, the keyboard will play a C major chord. This approach to accompaniment is limited because for each note the performer might play, the keyboard has only one chord option (C major for C, D major for D, etc). Also, “auto accompaniment” only chooses from major chords, but both major and minor cords are needed to create interesting music.
There are several music-generation algorithms that confront these limitations. One such algorithm uses fuzzy logic to decide how to arrange notes within a given chord progression [4]. Other algorithms employ Markov decision processes to generate accompaniment [1,3]. But these algorithms require complete knowledge of the underlying chord progression before they can generate music to match a melody. A recent innovative approach uses just a melody to generate a chord progression that matches it [2]. However, even this algorithm requires prior knowledge of the complete melody.
My goal was to create an algorithm that can create musical accompaniment in real time, referencing only past music played in the performance. A way to think of this algorithm’s applications is to imagine a soloist improvising a melody. Without any prior knowledge of what the soloist will play next, the algorithm can compose and play matching music in real time to create a joint performance between soloist and computer.
Process
Gathering Data
First, I chose pop as the genre to focus on for my project. Then, I got a corpus of songs representative of the pop genre from the top pop songs on the Billboard. Next, I obtained the chord structure for each song in my corpus. Because I wanted to study patterns in chord transitions independent of the key of the song, I transposed all of the song’s chord structures to the same key, arbitrarily choosing C without loss of generality. This doesn’t fundamentally change the relationships between adjacent chords in a sequence or lose any information about the original chord sequence. After gathering data on the chord structures, I analyzed each song and recorded its melody aligned with the chord sequence. I developed a file format to store the data relevant to my project. Here’s an excerpt from one of these data files:
A C | Dm
D F | F
E | C
D D D C | G
Each chord (often a measure or half a measure) is on its own line following the melody that was played during that chord. For example, in the first measure, the notes A and C were played during the chord Dm (D minor), then in the next measure, the notes D and F were played during the chord F (F Major), and so on.
Processing Data
I wrote a simple script that read a file in my defined format and created programming structures to hold this data so it could be analyzed for patterns.
Learning
To learn from the data, I trained a Hidden Markov Model. First, I trained a state transition matrix by going through the chord structure for each song in the corpus and adding “1” to a cell (i, j) in the matrix each time I encountered a chord transition from chord “i” to chord “j.” Next, I trained the melody (emissions) matrix by walking through the chord structure and melody of each song, measure by measure. For each note in the melody, I added a “1” to cell (i, j) in the melody matrix if I encountered chord “i” and note “j” playing at the same time. After doing this for all the song data, I normalized the matrices to be column-stochastic.
Prediction
With the chord-transition matrix and the melody matrix trained, I could then accompany a melody in real time. This is the process: the algorithm listens to a measure of the melody and uses the melody matrix to obtain a vector of probabilities for what the current chord is. Then using these estimations and the chord-transition matrix, I obtained a vector of probabilities for what the next chord may be. I then sampled from this prediction vector to decide on a prediction for the next chord, and this is the chord the algorithm plays on the downbeat of the next measure.
Results
To test my algorithm, I ran it on several common melodies and analyzed and listened to the resulting performance. Using the measurement of harmonization, the chord predictions matched the melody fairly well harmonically. However, I learned that I should have included other measurements of the performances. Specifically, I should have had some way to measure the “interesting-ness” of a performance. In the song data I used, some chords (such as C, the “root” chord) occurred much more often than other chords (such as D Major). Having the probabilities so heavily weighted toward these chords made it so the algorithm predicted and played one or two chords disproportionately more often than other chords, making the resulting performances not very interesting.
Discussion
I think a Hidden Markov Model is a promising research direction for this problem. In the future, to improve the results of my algorithm, I would make the data-collecting process more automated so I could collect a lot more song data. Specifically, it’s tedious to analyze the song’s melodies by hand and match the melody up with the chord progression. I think a promising possibility is to collect songs in the form of MIDI files and then build an algorithm to analyze the chordal structure and locate the melodies in the MIDI files. Building such an algorithm would be a difficult research problem by itself, but it would greatly facilitate the real-time accompaniment problem. Also, I would use some sort of smoothing method so if a chord is never encountered in the song data, it wouldn’t be assumed that its probability of ever occurring is 0.
References
- Liangrong Yi, Goldsmith, J., “Decision-‐theoretic harmony: A first step,” International Journal of Approximate Reasoning, Volume 51, Issue 2, January 2010, Pages 263-‐274.
- Monteith, Kristine, Martinez, T., Ventura, D., “Automatic Generation of Music for Inducing Emotive Response,” Proceedings of the International Conference on Computational Creativity, pp. 140-‐149, 2010.
- Schulze, W., van der Merwe, B., “Music Generation with Markov Models,” Multimedia, IEEE , vol.18, no.3, pp.78-‐85, March 2011.
- Yilmaz, A. Egemen, and Ziya Telatar. “Fuzzy logic based four-‐voice choral harmonization in traditional style,” Journal of Intelligent & Fuzzy Systems 21.5 (2010): 289-‐301. Computers & Applied Sciences Complete. EBSCO. Web. 1 Oct. 2011.