NetNews Usenet Archive 1992 #16/NN_1992_16.iso/spool/comp/theory/cellaut/315

Internet Message Format | 1992-07-22 | 12.5 KB

Path: sparky!uunet!dtix!darwin.sura.net!wupost!usc!sol.ctr.columbia.edu!The-Star.honeywell.com!umn.edu!lynx!nmsu.edu!opus!eiverson
From: [e-mail] (Eric Iverson)
Newsgroups: comp.theory.cell-automata
Subject: Re: A soup computer
Message-ID: <[e-mail]>
Date: 22 Jul 92 23:24:32 GMT
References: <[e-mail]>
Sender: [e-mail]
Organization: Computing Research Lab
Lines: 238
In-Reply-To: [e-mail]'s message of 21 Jul 92 10:42:17 GMT


In article <[e-mail]> [e-mail] (Jean-Paul V Jeral) writes:

> Once upon a time I attended a lecture where something remotely
> relevant to "soup computation" was said. I took note of it.
> Now I am unable to find that piece of paper and even to
> remember who gave that lecture (It might have been Sherrington).
> In the hope that someone can bring in more precision and
> reliability, here is what I think I remember (no garantee given!):

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: [e-mail]
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: [phone]
FAX:   [phone]