Collaborative Use of Features in a Distributed System for the Organization of Music Collections - Intelligent Music Information Systems: Tools and Methodologies - page 161

within the universe of method trees is a cycle
of selecting a population, applying the method
trees to the raw data, evaluating the fitness of
the population, and enhancing the fittest method
trees further to build a new population (Section
4.2). This cycle corresponds to the standard pro-
cess of genetic algorithms. What differs from the
standard is that method trees instead of binary
vectors form the search space, that the search
space is structured, and that the fitness evaluation
is not merely a function but the result of running
another learning algorithm. Figure 10 details the
left box of the overall picture.

one of the same class, that is by a function or
transformation. For all operations it is ensured
that the resulting tree still obeys the constraints
discussed above. Another possible mutation is to
allow parameter changes like the size of the used
windows. This further increases the size of the
search space which must not necessarily mean
that the problem gets harder. In fact, in our ex-
periments allowing also parameter optimizations
further increases the achieved accuracies while
the additional effort is approximately 20% of
run time. Crossover replaces a subtree from one
method tree by a subtree from another method
tree, respecting the well-formedness conditions.
This means that the roots of the subtrees must be
of the same type of methods.
For selection purposes, the fitness of all method
trees might be expressed by a roulette wheel , that
is, fitness proportional parts of a wheel's 360 de-
grees. The larger the portion, the more likely it
becomes that the particular individual is selected
for the next generation or crossover. Other possible
selection schemes include tournament selection ,
where t method trees are randomly chosen from
the population and the winner of this set, i.e. the
method tree with the largest fitness, is added to
the next generation. The parameter t allows the
definition of selection pressure.

representation

Genetic programming constructs finite automata.
Here, method trees are to be constructed. They
are represented by XML expressions. Figure 11
shows the representation of the method tree from
Figure 8. The Y ale system executes such trees and
takes care of the syntactic well-formedness.
The restriction that chains are concluded by
a function implies a level-wise structure of all
possible method trees. The lowest level 1 entails
only functions. These are chains of length 1. The
next level, 2, covers chains with a concluding
function. Levels 3 and above entail windowing.
Method trees are constructed according to their
levels. The level-wise growing means small
changes to a current method tree. On the one
hand, this reduces the probability of missing the
optimal method tree. On the other hand, it may
slow down the search, if the fitness of the lower
levels does not distinguish between good and bad
method trees.

fitness evaluation

Since method trees serve classification in the
end, the quality of classification is the ultimate
criterion of fitness. Each audio file is represented
by a set of random variables X that describe fea-
tures of this audio file. This feature set X is the
one obtained by the method tree constructed by
the genetic search operations described above.
For each method tree (individual) another fea-
ture set X will be constructed and evaluated. Y
is another random variable that denotes to which
class the audio file belongs. These obey a fixed
but unknown probability distribution Pr ( X,Y ).
The objective of classification is to find a function

mutation, crossover, and selection

The operations of genetic programming are
mutation and crossover. By random, mutations
insert a new method into the current tree, delete
a method from the tree, or replace a method by