Page  45 ï~~An Algorithmic Approach to Composition based on Dynamic Hierarchical Assembly Bill Punch Knowledge Based Systems Laboratory, Computer Science Dept A714 Wells Hall, Michigan State University E. Lansing MI 48824 517-353-3541, punch@pleiades.cps.msu.edu Mark Sullivan Computer Music Studio, School of Music Michigan State University E. Lansing MI 48824 517-355-7653, 20677MAI1ibm.cl.msu.edu Robert Koehler Knowledge Based Systems Laboratory, Computer Science Dept A714 Wells Hall, Michigan State University E. Lansing MI 48824 While researchers have pursued a number of algorithmic approaches to composition (cellular automata, fractals, rules), there is a need for more work that analyzes the composition problem first, and have that analysis drive algorithm construction/investigation. This paper describes our work on an approach to composition called Dynamic Hierarchical Assembly. It attempts to model two portions of the composition process, first the concept of assembling "units" into a finished "whole" (notes or sound-elements to phrases) and second the concept of assembly occurring at multiple levels of abstraction (sound flecks to notes, notes to phrases, phrases to sections etc.). We will describe the methodology behind this approach and the tool that encodes it (DHAT, for Dynamic Hierarchical Assembly Tool), what we have accomplished so far in terms of composition and the obstacles we foresee. 1 Introduction By now there are a number of distinct approaches to computer-assisted composition, that is composers utilizing computers as tools in their work. Examining recent work we note: a compositional system that allows "style bases" to be defined and influence the compositional process (Cope [5]), a system that creates musical output comparable in style and structure to the chorales of Bach (Ebcioglu [7]), systems which utilizes connectionist approaches as a composition tool (Lischka [14],Bharucha [1]) and a composition system based on fractals (Degazio [6]). However useful such work may be, if it is to be more than the latest "hot topic" it has to address the concepts behind the composition process to actually prove useful to composers and other practitioners. Attempts to force the domain, of music composition in this case, to fit a particular problem-solving approach instead of having the problem itself dictate what approach is useful all too often leads to demos and toy systems. These results offer nothing to the composer and contribute nothing to our understanding of the composition process. Smoliar's [22] comments on rule-based approaches reflect this attitude: Each technological advance becomes a new temptation to put the data into the computer again. Thus, rule-based systems beget attempts to develop rule bases for exercises in ICMC 45

Page  46 ï~~2 EXPLORING THE PROBLEM OF COMPOSITION harmonization, under the justification that rules are an established technology for modeling expertise, harmonization is a domain of expertise, ergo, one can formulate rules to perform harmonization. These remarks would apply to any approach that concentrated on the implementation itself instead of the needs of the domain and how these needs can be met. There are, however, a number of researchers who have first analyzed the domain of music composition and then chosen a general problem solving approach that meets the requirements of the domain, instead of the other way around. Such work has the advantage of adding to our understanding of the music composition process as well as creating software that can imitate that process. Such work would include (but is not limited to) Smoliar's work on modeling of music information [22], Vicinanza's work on composition using the SOAR model [23] and the compositional systems of Xenakis [16], Brun [2], Scaletti [21], Koenig [13, 12] and others. We feel that each of the above approaches concentrates on a particular aspect of the compositional process and addresses what algorithmic approach meets these particular needs. The thrust of these approaches corresponds with one approach to Knowledge-Based Systems pursued by one of the authors (Punch) in other contexts, Chandrasekaran's view of generic tasks [4]. The intuition behind generic tasks is that different problem-solving tasks (diagnosis, composition, design etc.) might require significantly different problem solving methods and representations. Such a view emphasizes the analysis of the task structure of a domain problem and a mapping of that analysis to a set of highlevel problem solving methods and representations that meet the requirements of the domain. Again there is an emphasis on first understanding the problem, then mapping that problem to appropriate underlying methodologies. This work follows the generic task theme. We have explored a number of aspects of the process of composition and present an algorithmic approach that meets these needs. In so doing we provide a high-level tool that more closely meets the needs of composers using the system by providing a framework that more closely matches their approach to the problem. 2 Exploring the Problem of Composition We of course are not implying that we have addressed all aspects of the problems that emerge in computer-assisted composition. Rather, we have concentrated on some aspects of composition that we perceive to be relevant and have studied these aspects in some detail. We have concentrated on three important issues. First, we choose to view composition as an assembly process, that is the assembling of various "units" into sequences or groups. Following this view, the artist's input is the knowledge used to constrain and control the assembly choices to either initiate the desired process or achieve the desired results. Second, what constitutes a "unit" in the assembly process varies depending on the level of description: composition operates at multiple levels. For example, we can have assembly at the "sound-fleck" level as in granular synthesis [24, 15] to make a note or sound element, or assembly at the note level to make a phrase or sequence, or assembly at the phrase level to make a movement or section, and so on. Third, we note that the "product" of one level's assembly can be used as the units to assemble at the next level of abstraction, and that there is complex interaction between levels. For example, the result of assembly at the sound fleck level is a note that is used as the unit of assembly at the phrase level. Each level can impose constraints from above to insure a useful "product". Continuing with our example, the note passed to the phrase level may not be suitable for inclusion into the partially assembled phrase: it can be sent back to the note level with suggestions for repair based on the state of the phrase being assembled and the constraints it violated. This repair could also take other forms, for example the description or constraints at the phrase level may be modified based on suggestions from the note level, or the conflict might be included, articulated and emphasized. Note that this does not imply a strictly sequential or ICMC 46

Page  47 ï~~3 HIERARCHICAL ASSEMBLY top-down model of composition, but a dynamically changing model where any part of the present work can be modified to meet the artist's constraints. Our goal has been to design a software tool that would support the artist in describing and inputting knowledge concerning the assembly process itself, knowledge concerning the re-assembly process based on errors, and the constraints the assembly process must adhere to. We are also providing data (visual and textual) on the progress of the assembly algorithm to give the artist detailed feedback on the results of this input. The tool is called DHAT, Dynamic Hierarchical Assembly Tool, and the next section will describe the details of the algorithm it encodes. 3 Hierarchical Assembly 3.1 What is Assembly The process of assembly is a generic task/method that has occurred in many domains including design [20, 17], biomolecular structure determination [8], abduction/diagnosis [11, 9], control/sequencing of Al problem-solvers [19, 18] and now musical composition. The first step in describing the assembly task is to describe it's information processing structure, namely the inputs, outputs and requirements that assembly requires/expects: Task Function: The assembly task takes as input: a set of constraints that should be adhered to if possible, a goal set that the assembly result should achieve (again as much as possible), and a set of units which can be used in assembly. The output of the assembly process is that subset of units termed the composite that "best" meets the goals and constraints. In automobile diagnosis, the goals would to explain the symptoms of a car problem such as leaking gas or frequent stalling, constraints would be information about auto parts such as connectedness, and the units would be hypotheses that represent conclusions of failure, i. e., broken gas-line or misadjusted carburetor. In music, goals would be compositional, constraints would be constraints between notes1 and the output would be a sequence of notes meeting the compositional goals under constraint. Types of Knowledge: Various types of knowledge are required. Knowledge that represents the goals as well as ways to meet constraints. Also required is knowledge of how units achieve goals or portions of them. Control Strategy: The approach is to focus on each unachieved goal until all are achieved or an unachievable goal is found. For each unachieved goal, a composite is developed based on those units that offer to achieve the chosen goal under the constraints of the problem. From this candidate subset, one candidate is chosen and added to the composite which ultimately contains the candidates used to best achieve the goals of the problem. Note that the system is required to give the "best" answer it can under the goals, constraints, and units it has available. By that we mean that the system needs to perform an efficient search of the possibilities. Even if it cannot meet all the goals and constraints it should then yield the best answer it can with ancillary information about what goals were not achieved and what constraints prevented this achievement. It should also be able to report on alternative composite answers, perhaps rated on some relative scale, so that the user can make some high-level evaluations of system performance. 3.2 The Assembly Algorithm The assembly algorithm is based on the algorithm first used in the RED [11, 9] antibody identification system. This assembly algorithm consists of three main parts: 1 We will continue to use notes as the unit of assembly and note that the other levels of unit (sound flecks, phrases) can be used interchangeably ICMC 47

Page  48 ï~~3 HIERARCHICAL ASSEMBLY 1. Generation/Evaluation method 2. Assembly method 3. Critique method (optional) The first step in the assembly process is the generation and evaluation of the units to be used in the composite answer. In fact, the main goal of this step is to reduce the search space of the assembly process to a small set of likely candidates for inclusion in the composite. Thus the system must either generate a small set of plausible candidates to be used in the composite or prune the pre-existing pool of units to a smaller number. In the original RED system, this was accomplished using the technique of hierarchical classification [3]. This was possible because the units (in this case, antibodies to explain a clotting reaction) were pre-enumerated and well-know. Hierarchical Classification was used to reduce greatly the number of antibodies that could potentially be used to achieve the goal of explaining the clotting reactions of a case. It furthermore rated the plausibility of the antibodies to give the assembler more discrimination data. In composition, it is not at all clear that a pre-existing classification of units would be of much use. Rather, its seems that in the process of assembling a set of notes, certain constraints are generated and as a result only certain notes will achieve the goals of the composition. Rather than attempting to classify notes into structures, it seems plausible to generate notes from the constraints of the existing problem. Consider the following example. The composer supplies some constraints initially, but the construction of the piece imposes new constraints during the composition process. If, at some point, the composer has stipulated several sequences of rhythmic proportions consisting of attack intervals, there is no need to create a hierarchy for all possible set of individual attack intervals. The present constraints of the piece limit what intervals could used and these can be generated. Likewise, if the rhythmic proportions are to be synchronized with pitch sequences this further constrains the generation process. The assembly module is driven by the two requirements already mentioned. The first is to create a composite that achieves all the goals by assembling a subset of the candidates received from the generation module. The second is to not violate any constraints of the problem during achievement of the first requirement. The result is that the system will implicitly search multiple possible composites and find the "best" composite that achieves as many goals as possible while violating as few constraints as possible. This leads to the following algorithm: 1. Select a single goal that needs to be achieved. 2. From the candidate list (from the generation module), select those candidates seem most appropriate for use in the composite 3. If only one candidate is available, select that candidate, otherwise select one candidate from the list. 4. Integrate the selected candidate into the composite. If the introduced hypotheses is incompatible with the existing composite i.e., violates some constraint, then there are two choices. Either select another candidate i.e., go back to step 3. or remove incompatible candidates in the composite and unmark the goals they were selected to achieve. Maintain a history mechanism to avoid loops. 5. Update any other goals that might be achieved by the integration, and if some goals still remain unachieved, go to 1. In the context of a granular synthesis of a series of sound masses in sequence, it could the that the relevant constraints entail a sequence of densities for each sound mass (i.e., the total number of frequencies in the individual sound mass), a sequence of upper note or frequency boundaries, a ICMC 48

Page  49 ï~~3 HIERARCHICAL ASSEMBLY sequence of lower note or frequency boundaries and a sequence of rhythmic proportions for each individual sound mass. Several candidates could be generated that have the required density and these could be examined to determine if they have the correct upper and lower bounds. If any mass meets all the requirements, it is selected for inclusion in the composition. If some conflict occurs i.e., the densities are correct but some boundaries are violated, two actions are possible. One, further generation of masses could occur to see if a fully acceptable mass can be found. Two, corrective actions could be taken. These actions include changing the conflicting boundaries either as an exception for this one case or as a global change that affects the entire piece. The third phase of the algorithm is an optional critique phase of the composite the assembly algorithm creates. The critique phase is performed to evaluate the "desirability" of the composite and, if possible, improve it. In the original RED algorithm, two specific kinds of critique were used. The first is parsimony critique which determines if the composite is minimal in terms of set size. That is, can the composite set size be reduced and still meet the two requirements. The other critique used in RED is essential critique. This determined if any element of the composite was required since only that element could meet one of the problem goals. Those elements determined to be essential were then required to be in the final composite and could form a nucleus around which the rest of the composite could be built. For the composition problem, it would appear that parsimony would not always be a common critique method due to the ambiguity of the term "minimal", but essentialness would have a clear role. For example, only one note would fill the goal of the composition and still meet the constraints of the problem. Other critiques seem should be made available to meet the particulars of the domain i.e., richness, harmony etc. 3.3 Hierarchical Assembly While assembly may capture some aspect of musical composition, it ignores what appears to be the multi-level complexity of such a task. For example, we could view musical composition as simply the sequencing of notes to make sound, but that ignores the complexity of the rich set of levels of abstraction at which composition typically occurs. It is not the case the composers only "sequence notes", rather they seem to work at different levels of abstraction (sound fleck, note, phrase, movement) each requiring its own knowledge and special consideration. Furthermore there is a dynamic interaction between these levels such that the work at each level interacts with those above and below. Our goal was to investigate this aspect of multiple, interacting levels of abstraction within the context of the assembly view of composition. To accomplish this we needed to extend the vision of assembly. The original view of hierarchical assembly comes from the work of Josephson et. al. [10] who worked on hierarchical assembly as applied to speech understanding. The additions to the basic assembly algorithm are this: First, we define multiple levels at which assembly can occur (sound fleck, note, phrase, section) and we define the relations between these levels hierarchically. Second, we impose the following operations between assembly levels: 1. A lower-level assembler can output a composite answer to a higher assembler. The higher assembler then uses this composite as a unit for goal achievement in its level. This output may also contain extra information concerning the assembly process that occurred in the lower assembler that yielded that composite. 2. A lower-level assembler can also output suggestion on how to re-organize the constraints and goals of the higher-level assembler. These could include message on the goal-constraint combinations the lower-level cannot meet and ways to avoid the conflict. ICMC 49

Page  50 ï~~4 THE QUESTION OF KNOWLEDGE 3. The higher-level assembler can either utilize the composite from the lower assembler, now a unit in this assembler, or reject that composite. In rejecting the unit it can suggest to the lower assembler ways in which to improve the composite. 4. The higher-level assembler can also re-organize its goal-constraint combinations based on suggestions from above or below, or based on attempts to incorporate apparent conflicts into the compositional process. 5. This interaction need not be synchronous, that is a composite passed up to a higher assembler can be rejected at any time as a candidate, including after multiple attempts by the higher assembler to utilize it. 6. This communication up and down the assembler hierarchy is not constrained to be one direction. Control can pass up and down based on the state of problem-solving as it proceeds, not in a pre-determined fashion. 4 The Question of Knowledge The main question mentioned at this beginning of the paper is "So what, how does this work contribute to our knowledge of composition?". Our main contribution so far is the architecture in which we view composition, namely hierarchical assembly. By examining only a few aspects of the broad domain of composition, assembly at multiple levels of abstraction, we restrict our focus ourselves enough concentrate our resources on a meaningful evaluation of the problem. What remains to be done is to prove that knowledge can be obtained to run the hierarchical assembler that does "reasonable" composition. In other words, if this model has anything pertinent to say about the composition process, then we should be able to find knowledge from composers that will allow us to operate this architecture to create at least a limited kind of compositions. This is in fact an empirical question, a question to be answered by experiment within the paradigm of hierarchical assembly. This we believe is the critical step. First one must propose an architecture that captures some important aspect of the domain to be investigated, then one attempts to justify the approach by gathering knowledge and creating systems that prove (or disprove) the usefulness of the system. One criteria of usefulness, perhaps the most important, is that it somehow contributes to the communities understanding of the domain. Thus the gathering of knowledge about how hierarchical assembly applies to composition should not only allow us to create systems that produce music in some limited sense, but also contribute to the understanding of the composition process itself. 4.1 Work to Date We have implemented a version of the Dynamic Hierarchical Assembly Tool (DHAT) for experimentation with granular synthesis. The original system generated random composites of sound flecks based on: fleck timbre, fleck frequency, fleck number and the distribution of the number in time. This system generated csound file format for compatibility purposes. Sullivan is now in the process of placing knowledge into the system to allow it to create non-random granular synthesis with particular characteristics. The system runs on a Sun-4 in Common Lisp with an X windows graphical user interface. Punch and Koehler are presently in the process of extending the tool to support the hierarchical nature of the assembly process and experiments with this are underway. References [1] J. Bharucha. Neural net modeling of music. In Proceedings of the First Workshop on Artificial Intelligence and Music, pages 173-182. AAAI, 1988. ICMC 50

Page  51 ï~~REFERENCES [2] Thomas Blum. Herbert Brin: Project sawdust. Computer Music Journal, 3(1):6-7, 1979. [3] T. C. Bylander and S. Mittal. CSRL: A language for classificatory problem solving and uncertainty handling. AI Magazine, 7, Summer 1986. [4] B. Chandrasekaran. Task structures, knowledge acquisition and learning. Machine Learning, 4:339-345, 1989. [5] D. Cope. Music & lisp. AI Expert, pages 26-34, 1988. [6] A. Degazio. Musical aspects of fractal geometry. In Proceedings of the International Computer Music Conference, pages 435-442. ICMC, 1986. [7] K. Ebcioglu. An expert system for chorale harmonization. In Proceedings of the National Conference on Artificial Intelligence, pages 419-421. AAAI, 1986. [8] Barbera Hayes-Roth, Bruce Buchanan, Olivier Lichtarge, Mike Hewett, Russ Altman, James Brinkley, Craig Cornelius, Bruce Duncan, and Oleg Jardtzky. PROTEAN: Deriving protein structure from constraints. In AAAI86, volume 2, pages 904-909. Morgan Kaufmann, 1986. [9] W. F. Punch III, M. C. Tanner, J. R. Josephson, and J. W. Smith. Using the tool PEIRCE to represent the goal structure of abductive reasoning. IEEE Expert, 5(5):34-44, 1990. [10] J. R. Josephson. A layered abduction model of perception: Integrating bottom-up and topdown processing in a multi-sense agent. In NASA Conference on Space Telerobotics, volume IV, pages 197-206, Pasadena, California, 1989. NASA. [11] J. R. Josephson, B. Chandrasekaran, J. R. Smith, and M. C. Tanner. A mechanisim for forming composite explanatory hypotheses. IEEE Transactions on Systems, Man and Cybernetics, SMC-17(3):445-454, 1987. [12] G. M. Koenig. Aesthetic integration of computer-composed scores. Computer Music Journal, 7(4):27-32, 1983. [13] O. Laske. Composition theory in Koenig's project one and project two. Computer Music Journal, 5(4):54-65, 1981. [14] C. Lischka. Connectionist models of musical thinking. In Proceedings of the International Computer Music Conference, pages 190-196. ICMC, 1987. [15] John MacKay. On the perception of density and stratification in granular sonic textures: An exploratory study. Interface, 13:171-186, 1984. [16] G. Marion, J. Raczinski, and M. Serra. The new upic system. In International Computer Music Conference Proceedings, pages 249-252, Glasgow, 1990. ICMC. [17] S. Mittal and F. Frayman. Towards a generic model of configuration tasks. In Eleventh International Joint Conference on Artificial Intelligence, pages 1395-1401, Detroit, MI, 1989. AAAI. [18] W. F. Punch. Interactions of compiled and causal reasoning in diagnosis. Accepted for publication in Fall 91, IEEE Expert. [19] W. F. Punch and B. Chandrasekaran. An investigation of the roles of problem-solving methods in diagnosis. In Proceedings of Second Generation Expert System 's Conference, pages 25-36, May 1990. ICMC 51

Page  52 ï~~REFERENCES [20] W. F. Punch and C. S. Criddle. Knowledge-based system for design of water & wastewater treatment facilities. Technical Report, Michigan State University AI/KBS Lab (work in progress). [21] C. Scaletti. The Kyma/Platypus computer music workstation. Computer Music Journal, 13(2):23-28, 1989. [22] S. Smoliar. Music notation: Cognitive red herring? In Proceedings of the Second Workshop on Artificial Intelligence and Music, pages 53-62. IJCAI, 1989. [23] S. Visnanza and M. Prietula. A computation model of musical creativity. In Proceedings of the Second Workshop on Artificial Intelligence and Music, pages 21-25. IJCAI, 1989. [24] I. Xenakis. Formalized Music. Indiana University Press, Bloomington, Indiana, 1971. ICMC 52