Page  00000001 Inductive Logic Programming and Music Rafael Ramirez Music Technology Group - IUA, Pompeu Fabra University Ocata 1, 08003 Barcelona, Spain rramirez @iua.upf.es Abstract First-order logic is one of the most expressive and widely used knowledge representations, and its application to the formalization of musical knowledge raises particularly interesting questions. This paper explores several approaches to learning Horn clauses, an important special case of first-order logic formulas, and provides a representative sample of the issues involved in applying such techniques in a musical context. We then proceed to describe our approach to learning Horn clauses for the harmonization of popular music melodies and their implementation into an automatic harmonization system. 1. Introduction In many cases it is useful to learn and represent a target knowledge as a set of if-then rules. An important special case of if-then rules are a particular kind of rules containing variables, called first-order Horn clauses. Because sets of first-order Horn clauses can be interpreted directly as programs in the logic programming language Prolog, learning them is called inductive logic programming (ILP). The aim of this paper is to introduce different approaches to learning sets of first-order Horn clauses focusing on their application to learning musical concepts. In particular, we present our experimental investigations on learning Horn clauses for the harmonization of popular music melodies and their implementation into an automatic harmonization system. The reader should be cautioned that this article is not a comprehensive review of inductive logic programming or its applications in the field of computer music. Rather, the goal of the paper is to provide a brief introduction to the subject and a representative sample of the issues involved in applying such techniques in a musical context. The rest of the paper is organized as follows: Section 2 briefly introduces inductive logic programming. In section 3, some ILP approaches to learning musical concepts are reported. Section 4 describes our approach to learning harmonization rules in popular music and to implementing them in an automatic harmonization system, and finally section 5 presents some conclusions and further work. 2. Inductive Logic Programming Typical examples of if-then rules used in machine learning are classification rules and association rules. Classification rules are a popular approach to classification learning in which the antecedent of a rule is generally a conjunction of tests (e.g. age < 25Asex = male) and the consequent is the predicted class (e.g. drive = yes) or classes (possibly with a probability associated to each class). Association rules [2] are similar to classification rules except that they can predict any attribute or combinations of attributes, not just the class. It is often assumed implicitly that the conditions in (classification and association) rules involve testing an attribute value against a constant. Such rules are called propositional because they have the same expressive power as propositional logic. In many cases, propositional rules are sufficiently expressive to describe a concept accurately. However, there are cases where more expressive rules would provide a more intuitive concept description. These are cases where the knowl Proceedings ICMC 2004

Page  00000002 edge to be learned is best expressed by allowing variables in attributes (e.g. age(x) < 25) and thus in rules (e.g. if sex(y)=female then...). One important special case involving learning sets of rules containing variables is called inductive logic programming [9, 8]. A type of rules in inductive logic programming, called Horn clauses, are of particular interest because rules in this form can be interpreted and directly executed as a program in the logic programming language Prolog [3]. As an example of sets of rules containing variables, consider the following two rules jointly describing the concept of ancestor (parent(x, y) indicates that y is the mother or the father of x and ancestor(x, y) indicates that y is the ancestor of x): ifparent(x,y) then ancestor(x,y) ifparent(x,z) & ancestor(z,y) then ancestor(x,y) These two rules describe a recursive function that would be very difficult to represent using a decision tree or other propositional representation. One way to see the expressive power of Horn clauses is to consider the Prolog. In Prolog, programs are sets of Horn clauses such as the two shown above. In fact, when stated in a slightly different syntax the above rules form a valid Prolog program for computing the ancestor relation. Thus, an algorithm capable of learning such rule sets may be viewed as an algorithm for automatically inferring Prolog programs from examples. A variety of algorithms that directly learn Horn clauses have been proposed. Probably, the most common approach is represented by sequential covering algorithms which learn one rule at a time, removing the covered examples and repeating the process on the remaining examples. A quite different approach to inductive logic programming is based on the observation that induction is the inverse of deduction. Thus, the approach here is to design inverse entailment operators. Inductive logic programming systems have been successfully applied to a wide range of problems in different areas including chemistry [11], engineering [4] and music. In the next section, we report on some inductive logic programming approaches to learning musical concepts. 3. Inductive Logic Programming in music Previous research in learning sets of clauses in a musical context using inductive logic programming has included a broad spectrum of music domains. Morales has reported research on learning counterpoint rules [7]. The goal of the reported system is to obtain standard counterpoint rules from examples of counterpoint music pieces and basic musical knowledge from traditional music. The system was provided with musical knowledge which includes the classification of intervals into consonances and dissonances, the description of whether two notes of different voices form a perfect or imperfect consonance or a dissonance, and whether two notes from the same voice form a valid or invalid interval. The rules learned by the system, resulting in a Prolog program, were tested for analysis of simple counterpoint pieces. The system was also used for musical creation of simple two voice counterpoint pieces: given the first voice of a piece and a sequence of rules, the system was able to generate the required counterpoint notes of the second voice. Igarashi et al. describe the analysis of respiration during musical performance by inductive logic programming [6]. Using a respiration sensor, respiration during cello performance was measured and rules were extracted from the data together with musical/performance knowledge such as harmonic progression and bowing direction. The data was obtained from four skilled cello players by asking each of them to perform the same representative cello piece. Each subject repeated the performance for this piece six times. As background knowledge fifteen kinds of predicates concerned with musical structure and playing styles were defined. Tobudic et al. [12] describe a relational instancebased approach to the problem of learning to apply expressive tempo and dynamics variations to a piece of classical music, at different levels of the phrase hierarchy. The different phrases of a piece and the relations among them are represented in first-order logic. The description of the musical scores through predicates (e.g. contains (phl, ph2)) provides the background knowledge. The training examples are encoded by another predicate whose arguments encode information about the way the phrase was played Proceedings ICMC 2004

Page  00000003 by the musician. Their learning algorithm recognizes similar phrases from the training set and applies their expressive patterns to a new piece. Other inductive logic programming approaches to rule learning and musical analysis of music include [5] and [1]. In [5], Dovey analyzes piano performances of Rachmaniloff pieces using inductive logic programming and extracts rules underlying them. In [1], Van Baelen extended Doveys work and attempted to discover regularities that could be used to generate MIDI information derived from the musical analysis of the piece. 4. Inducing clauses for harmonizing popular music melodies We describe an inductive logic programming approach for learning Horn clauses from popular music harmonizations. As opposed to most of the existing work on harmonization in computer music which views harmonization as deriving/analyzing a four voice score for a particular voice, our view is on the sequence of chords that harmonize a melody. In this context, the process of harmonization is difficult to formalize and the way a given melody is harmonized normally varies from person to person according to his/her taste and background. Thus, the approach presented here makes no attempts at providing a definite set of rules but to learn generic rules from a set of popular music examples. The data used in our experimental investigations was collected from popular music scores with chord annotations. We used 42 scores mainly western popsongs. The data included information about position of a particular bar in the score (initial, middle or last), notes in and harmonization of the bar, harmonizations of preceding bars (via the successor relationship), some music theory background knowledge (e.g. notes included in particular chords), and some simple background knowledge (e.g. the member predicate). We used the inductive logic programming system Aleph [10] to induce Horn clauses. We applied Aleph's default greedy set cover algorithm that constructs hypothesis one clause at a time. In the search for any single clause, Aleph selects the first uncovered positive example as the seed example, saturates it, and performs an admissible search over the space of clauses that subsume this saturation, subject to a user-specified clause length bound. We chose to provide the learning algorithms with harmonic knowledge at both the note and bar level, as opposed to only at the note level, in order to capture common chord patterns in popular music. This information would have been lost if we only analyzed the harmonization of melodies at a note level. WYe also structured our data by musical phrases. We manually segmented the pieces into phrases and provided harmonization knowledge for each segment. This, we believe, is closer to the process of harmonizing a melody by a musician. All the data provided to the learning algorithms was coded by hand which explains the relatively small number of musical scores considered. However, despite the reduced number of training data some of the rules generated by the learning algorithm turn out to be of musical interest and correspond to intuitive musical knowledge. In order to illustrate the types of rules found let us consider some examples of learned rules: RULEl: harmonize (X, Y) + notes (Y, Z), member (X, Z) "A chord harmonizes a note if the note belong to the set of notes in the chord" RULE2: harmonize (X, 1) + prevehord (1, X, 5), prevchord(2,X, 4) "if the penultimate bar and last bar are harmonized with the subdominant and dominant chords respectively, then the current note (i.e. bar) is harmonized with the tonic." The induced clauses turned out to be very simple and general, e.g. rule 1 and rule 2 above predict 62% and 42% of all the cases, respectively. We used a slightly modified version of the induced clauses as the basis for a Prolog-based system for automatically harmonizing popular music melodies. The program outputs all possible harmonizations for a given melody which are consistent with the ind~uced rules. Wre have explored different ways in which the rules interact with each other. One alternative is, as exemplified by the program bellow, to consider the set of rules as a disjunctive set. The main body of our Prolog program is as follows: Proceedings ICMC 2004

Page  00000004 harmonizeall (_, [], []). harmonizeall(N, [X|R], [Y|R1]) harmonize (N, X, Y), assert (prevchord (N, Y)), N1 is N+1, harmonizeall(Ni,R,R1). harmonize(_,X,Y) notes (Y, Z), member (X,Z). harmonize(NX,1) prevchord (N-1, 5), prevchord (N-2f, 4) The ha rmo ni z eall predicate is the simple loop calling the harmonize predicate which encodes the induced rules and computes the harmonizations (e.g. the last two program clauses encode rule 1 and rule 2 as above). At any point, the history of the chords used to harmonize the previous bars is recorded by asserting this information into the program. As opposed to other machine learning techniques, ILP does not require explicit information about the chord history for finding rules involving previous chords (e.g. rule 2). 5. Conclusion This paper describes different approaches to learning sets of first-order Horn clauses and provides a representative sample of the issues involved in applying such techniques in a musical context. In particular we present our experimental investigations on learning Horn clauses for the harmonization of popular music melodies and to implementing the resulting clauses in an automatic harmonization system. We applied the inductive logic programming system Aleph to data with information about position of a particular bar in the score, notes in and harmonization of the bar, and harmonizations of preceding bars to induce a set of clauses which are the basis of a Prolog-based system for automatically harmonizing popular music melodies. Future work: This paper presents work in progress so there is future work in different directions. The manual segmentation and coding of training data is obviously not scalable so a (semi) automatic method to do this is necessary. We also plan to experiment with different information encoded in the training data. Currently, we only provide information and induce clauses about harmonizations with one chord per bar. We plan to extend this to harmonizations with more than one chord. Another extension to be explored is the use of richer chords with four notes or more. Acknowledgments: This work is supported by the Spanish project ProMusic TIC 2003-07776-CO2-01. References [1] Van Baelen, E. and De Raedt, L. (1996). Analysis and Prediction of Piano Performances Using Inductive Logic Programming. International Conference in Inductive Logic Programming, 55-71. [2] Chen, M., Jan, J. and Yu, P.S. (1996). Data Mining: An Overview from a Database Perpective. IEEE Trans. Knowledge and Data Engineering 8(6), 866 -883. [3] Colmenauer A. (1990). An Introduction to PROLOGIII. Communications of the ACM, 33(7). [4] Dolsak, B., Muggleton, S. (1992). The application of inductive logic programming to finite element mesh design. In Inductive Logic Programming. London, Academic Press. [5] Dovey, M.J. (1995). Analysis of Rachmaninoff's Piano Performances Using Inductive Logic Programming. European Conference on Machine Learning, Springer-Verlag. [6] Igarashi, S., Ozaki, T. and Furukawa, K. (2002). Respiration Reflecting Musical Expression: Analysis of Respiration during Musical Performance by Inductive Logic Programming. Proceedings of Second International Conference on Music and Artificial Intelligence, Springer-Verlag. [7] Morales, E. (1997). PAL: A Pattern-Based First-Order Inductive System. Machine Learning, 26, 227-252. [8] Quinlan, J.R. (1990) Learning logical definitions from relations. Machine Learning, 5, 239-266. [9] Shapiro, E. (1983) Algorithmic Program Debugging. Cambridge MA, MIT Press. [10] Srinivasan, A. (2001). The Aleph Manual. [11] Srinivasan, A., Muggleton, S., King, R.D., Steinberg, M. (1994). Mutagenesis: ILP experiments in a nondeterminate biological domain. Proceding of Inductive Logic Programming Workshop. [12] Tobudic A., Widmer G. (2003). Relational IBL in Music with a New Structural Similarity Measure, Proceedings of the International Conference on Inductive Logic Programming, Springer Verlag. Proceedings ICMC 2004