Composing music by constraint satisfaction:
using human composed music to improve the quality of computer composed sequences
Nicholas Hindle
March 2008
1. Abstract
using human composed music to improve the quality of computer composed sequences
Nicholas Hindle
March 2008
Music composition was attempted with the first generations of digital computer as early as 1949 (Wikipedia, 2008). Although computer technology has increased considerably in capability, advances in computer composition of music are still constrained by challenges such as how to measure the quality of computer composed music.
This research seeks to analyse the effects of using human composed music as reference data for improving the structure and quality of computer generated music.
The research involved the development of an experimental software tool which produced music fragments, which were compared to a database of human composed music. The results were then programmatically fed back into the tool, allowing the feedback to influence the musical quality of subsequent sequences.
The research concluded that, by modifying the tool's parameters as a result of comparing computer and human music, the structure of composed sequences became more similar to the structure of human composed music, and arguably increased in quality.
2. Objectives of the Research
While there is no effort involved in you or I deciding whether a piece of music sounds good, it is very difficult for a computer to assess. The computer based composition process must emulate or model the human thought based processes involved, or combine existing techniques in order to produce original music that sounds acceptable.
While a number of contemporary studies have used Artificial Intelligence to model the human composition process (Balaban, 1992), there is so far little evidence of any great success.
Continuing research into alternative methods is still producing interesting results. Work by Hoeve (2006) and Patchet and Roy (2004) has made extensive use of constraint programming for computer assisted composition. Constraint programming is a relatively new model that operates in a declarative manner; the programmer states the problem and supplies the necessary variables, and the constraint satisfaction program (CSP) generates solutions based on internal mechanisms.
Computer created music fragments may be assessed by listening, but this task could become somewhat tedious, and maintaining an objective assessment may prove difficult. A mechanism called contour matching has proved effective in providing quantitative comparison of music sequences in work by Uitenbogerd and Zobel (1998) and Downie (2000).
The objective of this research is to analyse the effects of combining constraint based composition techniques with contour matching, and measure whether any improvement in quality of the composed music can be gained as a result of the amalgamation.
3 Research Method
The research entailed investigations into existing work in the areas of music composition and sequence contour matching, followed by the development of a fully functional experimental tool. The tool, a “contoured constraint music system” (CCMS), provides the combined functionality required to generate music sequences and compare them with a database of human composed music. The results of matching the music sequences is automatically integrated into subsequent compositions by adjusting the constraint program variables. The conclusions of the research are drawn from analysis of the results produced by the CCMS.
The discrete components of the CCMS are the constraint system, the contour matching system, a music database, and the control mechanism for integrating the three components.
3.1 Constraint System
An investigation into available constraint systems and algorithms resulted in the selection of a constraint programming environment called Gecode (Schulte, 2007). This CSP was chosen for its support for the selected sequencing constraints, and because it exists as a standard C++ library, thus allowing relatively straightforward integration with other parts of the CCMS.
3.2 Contour Matching
Following research into the methods for contour matching techniques, a version of the contour matching methods used by Uitenbogerd and Zobel (1998) was used. The original method provides a contour showing the change in direction of notes on the score.
Figure 1. A sample music fragment
Figure 1 shows a bar of standard notation music, known as an n-gram. This is simply a small fragment of musical notes, delimited by bar markers. There are a number of ways to define where an n-gram starts and ends, but for the purposes of this research, a single bar proved to be effective.
| D | U | U | U |
Figure 2. Corresponding sequence contour
Figure 2 shows a string of characters known as a sequence contour, based on the method suggested by Uitdenbogerd and Zobel (1998). This illustrates how the characters U, D, S (up, down or the same) represent the change in direction of the notes, but do not show the size of the intervals between them. Note that a contour is relative, so an identical fragment played in different octaves will exhibit the same contour and can be recognised as the same tune by the listener.
| -03 | +05 | +01 | +01 | +01 |
Figure 3. Vectored sequence contour
The contour matching method used was based on a system proposed by Kim (2000), and is illustrated in Figure 3. This illustrates a vectored sequence contour of the music fragment shown in Figure 1, showing both the direction and size of the interval in semitones.
3.3 Database
A database of over one thousand human composed tunes was created using a freely available database system (Microsoft(R) SQL Server ExpressTM), populated from internet based music websites. The downloaded tunes belonged largely to the traditional folk genre. These are simply structured tunes, free from royalty restrictions, and hence ideally suited to music research.
Figure 4. Music database model
Figure 4 shows a standard entity relationship model that supports the required basic structures of music notation. The contour matching routines were stored in the database system as precompiled procedures. This arrangement meant intensive searching processes could take place close to where the data is stored, ensuring acceptable performance.
3.4 Contoured Constraint System
The experimental tool was written in C++. The tool consisted of three parts; the Gecode constraint system libraries, the mechanism for interacting with the database, and a simple user interface.
The user interface was based on a simple command line, where the user specified the key signature, the number of bars of music required, and the maximum interval (in semitones) allowed between each note.
Figure 5. User interface of CCMS
Figure 5 shows the user interface of the CCMS. The results of the composition are stored in the database for subsequent analysis, and can be extracted for playing on the computer sound system.
4. Results
A reference sample from the database of human composed music is shown. This is a short folk piece in the key of C Major.
Figure 6. Human composed folk music with audio sample
The speaker icon in Figure 6 provides an audio sample of the above folk tune, which can be listened to by clicking the icon.
Figure 7. Constraint generated sequence with audio sample
Figure 7 shows a sequence that was generated by the CCMS with a user selected key of A Major, a fragment length of four bars with a maximum interval of six semitones. The feedback from the contour matching process was disabled in this instance, so this represents a collection of four unmodified solutions (each bar represents one solution) that were created by the CSP.
On listening to the audio sample, it is clear that there are some musical interval patterns that are likely to sound atonal to those used to the music of Western Europe.
Figure 8. Contour adjusted sequence with audio sample
The sequence illustrated by Figure 8 was generated by the CCMS using a user selected key of C Major, a length of four bars, and a maximum interval of six semitones. This time, each bar (representing one CSP solution) was converted into a vectored contour and matched against the database of human composed music. If the contour matched few or no fragments in the database, it was discarded and recomposed. The resulting tune has less atonal qualities and, after listening to the phrase repeatedly, some of the phrases can be learnt, suggesting some familiarity in structure.
Figure 9. Human assembled collection of contour adjusted sequences
The sample in Figure 9 was created by listening to the CCMS composed fragments and assembling them into a folk style structure, based on how good they sounded together. Attempts to assemble such a structure without human intervention produced somewhat disappointing structures. An example of a computer assembled tune is shown below.
Figure 10. Computer assembled collection of solutions
The contours representing each of the discrete solutions in the tune in Figure 10 were found to occur relatively frequently in the music database. However the computer appears unable to arrange them into a whole tune effectively, based on the contour matching score alone.
Figure 11. Statistical analysis of music structure
The chart in Figure 11 shows how the pitch of notes taken from a sample of twenty bars of music deviates around the pitch of the mean note in each bar.
Human composed folk music exhibits a relatively small deviation. This demonstrates the typical structure of Western European music. The raw constraint output deviates to a much greater extent and shows an inconsistent pattern. The deviation in contoured constraint music is considerably closer in deviation and pattern to that of human composed music.
5. Conclusions
By autonomously adjusting the constraint program parameters relative to the number of occurrences of computer composed sequences in the database, it was shown that the structure of the computer composed music subtly changed to become more similar to that of the human music in the database. The use of a single genre of music (traditional folk) may have had some impact on the resulting sequence structures. This type of music commonly uses repeating themes based on bars of short notes with reasonably large intervals, and the generated sequences that produced higher contour matching scores (i.e. occurred more frequently in the database) did in fact exhibit some of these fundamental structural properties. Investigations into using similar techniques using different genres of reference music present an interesting prospect for further work.
6. References
Anders, T (2007) 'Composing Music by Composing Rules: Design and Usage of a Generic Music Constraint System', URL: http://strasheela.sourceforge.net/documents/TorstenAnders-PhDThesis.pdf (Accessed: 24 March 2007)
Balaban, M., Ebcioglu, K., and Laske, O. (1992) Understanding Music with AI: Perspectives on Music Cognition, pp. 3 - 25, Cambridge (USA), MIT Press.
Kim, Y. E., Chai, W., Garcia, R., and Vercoe, B. (2000) 'Analysis of a contour-based representation for melody', URL: http://www.ragomusic.com/publications/musicIR2000.pdf (Accessed: 11 February 2008)
Patchet, F. and Roy, P. (2004) Principles and Practice of Constraint Programming, pp. 331 - 345, Vol. 1713/2004, Berlin, Springer.
Schulte, C. (2007) 'Generic constraint development environment', URL: http://www.gecode.org/ (Accessed 6 Feb 2008)
Uitdenbogerd, A. and Zobel, J. (1998) 'Manipulation of music for melody matching', Proceedings of the sixth ACM international conference on Multimedia, pp. 235 - 240, URL: http://doi.acm.org/10.1145/290747.290776 (Accessed 14 May 2007)
van Hoeve, W., Pesant, G., Rousseau, L. and Sabharwal A. (2006) 'Revisiting the Sequence Constraint', Principles and Practice of Constraint Programming, Volume 4204/2006, Berlin, Springer-Verlag. URL: http://www.springerlink.com.libezproxy.open.ac.uk/content/1683kw005032x3r2/fulltext.pdf (Accessed: 4 August 2007)
Wikipedia (2007) 'Computer Music', URL: http://en.wikipedia.org/wiki/Computer_music (Accessed 2 Feb 2008)