Newsgroups: bit.listserv.emusic-l
Date:         Fri, 24 Jul 1992 11:06:52 EDT
Reply-To:     xrjdm@calvin.gsfc.nasa.gov
From:         "Joseph D. McMahon" <xrjdm@CALVIN.GSFC.NASA.GOV>
Subject:      Re: A soup computer - comp.theory.cell-automata #395
Comments: To: emusic-l@auvm.american.edu

An article which may be of interest to others here.

In article <EIVERSON.92Jul22162432@ithaka.nmsu.edu>, eiverson@nmsu.edu (Eric
 Iverson) writes:
>
> I have done some work which is roughly analogous to what you're
> talking about, using the autocatalytic replication of proteins as a
> model for a program which composed music.  An ASCII version of a paper
> presented to the 1990 International Computer Music Conference
> follows:
>
> Metabolizing Music
>
> Eric Iverson and Roger Hartley
> Computing Research Lab
> Box 30001/3CRL
> New Mexico State University
> Las Cruces, NM 88003-0001
>
> Abstract
> 	Metamuse is a program that analyzes a piece of music by
> breaking it into its component parts, and then reassembling it into a
> similar piece.  This is done through autocatalytic set theory, which
> effectively allows portions of a string to break apart other portions,
> much like a conventional chemical reaction.  This produces a set of
> substrings that reflect the overall structure in that they are biased
> towards repetitive patterns present within the string as a whole.
> The autocatalytic process can then be run in reverse until a string
> which meets certain meta-selection constraints is produced.
>
> Introduction
> 	In the literature, there are a number of deterministic
> rule-based systems for the synthesis and analysis of music, (see, for
> example [2]).  However, it is clear that these systems are at best an
> approximation, in order that the rules can be used and understood by
> humans, and are at worst inadequate in the face of non-western
> tonality and various world music traditions.  To counter these
> potential shortcomings, we have chosen to take a self-organizing
> adaptive systems approach, where a priori knowledge is kept to a
> minimum.  Here, the user feeds the system pieces of music which it
> assimilates and then uses to generate a piece representative of the
> patterns derived from the originals.
>
> Autocatalytic Set Theory
> 	This assimilation is done through the use of Autocatalytic Set
> Theory.  Briefly stated, an Autocatalytic Set is a set of strings
> where each member is the product of at least one reaction catalyzed by
> at least one other member.  A reaction occurs when a catalyst binds
> onto a corresponding site on a string, and breaks the string in two.
> Similarly, the reaction can occur in reverse; joining two strings
> together to create a larger string.  This allows an autocatalytic set
> of strings to effectively bootstrap itself; making strings of greater
> and greater length until some goal state or level of stability is
> reached.  Thus, autocatalytic sets can in some way simulate
> self-organizing behavior.
>
> fig. 1
> 	    Binding			  Catalytic Reaction
> 	 BCDEF					BCDEF
> 	ABCDEFGBCDEFGH				  /\
> 						 /  \
> 					      ABCD   EFGBCDEFGH
>
> 	       BCDEF				BCDEF
> 	ABCDEFGBCDEFGH				  /\
> 						 /  \
> 				        ABCDEFGBCD   EFGH
>
> 	In the above reaction, BCDEF functions as the catalyst for
> string ABCDEFGBCDEFGH.  It is important to note that there are two
> sites on the string that the catalyst can bind to.  This allows for a
> certain amount of non-determinism, although only one of the sites is
> ultimately chosen.
> 	Autocatalysis, as it is being applied here, is essentially
> similar to using Markov Chains to analyze and then generate a string
> of elements.  However, there are differences.  For example, an
> autocatalytic analysis can be biased toward repetitive structures
> within a string.  This can be done by rewarding a string that
> successfully catalyzes a reaction by allowing it to replicate.  In
> this way, certain catalytic reactions will become more and more likely
> to occur as repetitive sites encourage the replication of their
> catalysts.  At the same time, a certain degree of mutation can be
> allowed during replication, which allows for potentially productive
> additions to the autocatalytic set.  In addition, unlike Markov
> Chains, autocatalysis can occur over a variety of different string
> lengths, thereby allowing large strings to act as templates for the
> creation of even larger strings containing the original catalyst as a
> subset.  This allows for the transferral of information at a variety
> of levels of complexity, thereby allowing for the possibility of
> repetitive patterns within the resultant string.
>
> Algorithmic Composition
> 	We take it that the goals of algorithmic composition are to
> produce "musical" compositions with the minimum amount of human
> interaction.  The spectrum of such techniques runs from full-blown
> composition tools with automatic generation of fixed musical patterns
> (repetitive rhythms especially) to the rule+random systems where a
> musical skeleton is produced by a set of rules, and then variations
> are generated by randomizing the parameters.  Examples are described
> in [6].  However, none of these techniques start from a given
> composition as the provider of musical ideas.  A set of rules for say,
> Bach chorales, or Top-40 tunes may be induced by lengthy analysis of
> many examples, but this is not the same as taking the ideas in one
> composition and working from that basis. Metamuse does just that.  Our
> techniques are independent of any particular compositional theory or
> personal biases.  Autocatalysis simply finds whatever patterns exist
> in the composition, and builds new compositions from these patterns
> taking their mutual compatibility into account.
>
> Applying Autocatalysis to Music
> 	Application of autocatalysis to music can be roughly divided
> into assimilation and regeneration.  Assimilation is used to break a
> string into lengths of 4 to 7 elements, thereby creating a base set
> from which to begin.  During the process of assimilation, it is likely
> that there will be points at which no further progress can be made
> without the introduction of a new catalyst.  These are generated by
> finding a random site on an existing string and allowing a binding to
> occur; creating a new catalyst out of unassociated single elements in
> the process.  This not only allows assimilation to continue, it also
> further defines the autocatalytic set.  After assimilation has been
> completed, regeneration takes place by using the existing inventory of
> strings to create longer and longer strings until some goal is met.
> 	In order to assimilate a piece of music, one must first
> isolate it into different series of elements.  These elements can
> correspond to aspects such as rhythm, pitch, interval, or any other
> salient feature the user wishes to isolate.  This is similar to work
> done by Conklin and Cleary [1] regarding the generation of music using
> multiple viewpoints.  It is important to remember that the individual
> strings should consist of elements drawn from a relatively small set,
> in order that repetitive patterns will be more likely to occur.  In
> the examples below, we have maximized repetition by using strings
> drawn from the set {a,b}.
>
> fig. 2
> 			  (06)BBABA -> (07)BABBA*
> 			(01)AABBA||BABAA(08)*
>
> 	Here BBABA is acting as a catalyst by breaking AABBABABAA into
> AABBA and BABAA.  It does this by binding onto a site on AABBABABAA
> where a one-to-one correspondence with its elements exists.  At the
> same time, BBABA is rewarded for catalyzing a reaction by being
> allowed to copy itself.  This copy is mutated (using a 5% probability
> of error) into BABBA.
> 	When a piece has been completely assimilated, we are left with
> an inventory of strings from which to create a new piece.  The
> probability aspect of Markov Chains is here simulated as populations
> of each string type relative to the others (i.e. the number of members
> of a type of string is equivalent to its probability of occurrence.)
> To create larger strings, we merely reverse the previous process:
>
> fig. 3
> 			   (05)BAAAB -> (09)BAAAB*
> 			(10)BABBAAABBA*
> 			(07)BABBA||AABBA(01)
>
> 	Here BAAAB is creating a new string BABBAAABBA out of the
> existing strings BABBA and AABBA.  It also copies itself as BAAAB.  It
> is important to remember that when a string is copied or created, both
> it and the template string(s) still exist.  This allows us to build a
> growing inventory of strings which can act both as templates to create
> new strings, as well as catalysts for reactions.
>
> Meta-Selection Constraints
> 	While autocatalysis is a powerful tool, it cannot in and of
> itself create strings of the length needed in an average musical
> piece.  One reason for this is that for every string of length N, at
> least two strings of average length N/2 are needed to create it.  In
> addition, since shorter strings take fewer reactions to create than
> longer strings, we end up with a distribution heavily weighted towards
> shorter strings, when in fact it is the longer strings that we are
> interested in.  Therefore, we can infer that strings over a certain
> length will become impractical if not impossible to generate.
> 	However, there are ways to extend the length of strings that
> can be practically generated.  One way to do this is through a variant
> of simulated annealing.  Here we would only allow strings over a
> certain length to be generated, while setting a quota for the number
> of strings to be generated exceeding that length.  By gradually
> restricting the quota, while simultaneously raising the cutoff length,
> we will eventually generate a single string whose length matches our
> goal.
> 	This is analogous to a selection process, in that we start out
> with a large number of candidate strings and proceed to eliminate them
> until only one remains.  While this constrains the number of smaller
> strings that are generated, its main benefit is that it allows us to
> proceed toward a goal length at a faster rate than would normally
> occur.  This allows us to practically generate strings of longer
> length within a reasonable amount of time.
> 	In addition, other meta-selection constraints could be applied
> to candidate strings before allowing them to be added to an existing
> autocatalytic set.  Some of the constraints which could potentially
> disallow the inclusion of candidate strings include:  presence of
> notes not in the original piece, notes falling outside of the range of
> the piece, and incompatibility with the statistical distribution of
> some aspect of the piece.
> 	Statistical distribution could be arrived at by taking a
> feature such as intervalic distance, or note duration and averaging it
> over some arbitrary number of notes or measures.  Thus, we could take
> a candidate string and compare it to an existing statistical profile
> to see if it was "too busy" or lacked adequate contrast.  In addition,
> these average values could function as higher order sites for
> substrings to bind onto.  This binding could occur by stipulating that
> a substring have a similar average parameter value as its parent site.
> In this way a rudimentary hierarchical structure could be generated;
> giving the piece greater length, as well as greater internal
> structure.
> 	In conclusion, we feel that autocatalytic sets are a
> potentially powerful method for generating pieces of music in a
> non-deterministic, yet internally consistent manner.
>
> References
> [1]	Conklin, D., and Cleary, J. G.  "Modelling and Generating
> 	Music using Multiple Viewpoints," Proceedings of the First
> 	Workshop on Artificial Intelligence and Music, AAAI-88, 125-137, 1988.
> [2] 	Ebcioglu, K.  "An Expert System for Harmonizing Four-part
> 	Chorales," Computer Music Journal 12(3): 43-51, 1988.
> [3]	Farmer, J. D., Kauffman, S. A., and Packard, N. H.
> 	"Autocatalytic Replication of Polymers," Physica D, 22: 50-67, 1986.
> [4]	Kauffman, S. A.  "Autocatalytic Sets of Proteins," Journal of
> 	Theoretical Biology, 119: 1-24,  1986.
> [5]	Schuster, P.  "Dynamics of Molecular Evolution," Physica D,
> 	22: 100-119, 1986.
> [6]	Zicarelli, D.  "M and Jam Factory," Computer Music Journal,
> 	11(4): 13-29, 1987.
>
> --
> ------------------------------------------------------------------------
> Eric Iverson				Internet: eiverson@nmsu.edu
> Computing Research Lab
> Box 30001/3CRL				Life is something to do when
> New Mexico State University		you can't get to sleep.
> Las Cruces, NM 88003-0001			-Fran Lebowitz
> VOICE: (505) 646-5711
> FAX:   (505) 646-6218

--
 --- Joe M.

                            THE AUDIENCE IS NOW DEAF
Comments: Gated by NETNEWS@AUVM.AMERICAN.EDU