Aplicação de Algoritmos Evolucionários à Extracção de Padrões Musicais

Abstract

A extracção de padrões é um problema que se coloca em várias áreas como, por exemplo, a biologia molecular ou a área financeira, e que pode ser considerado, do ponto de vista da inteligência artificial, como uma forma de aprendizagem não supervisionada. No domínio musical, o problema pode ser definido, informalmente, da seguinte forma: dada uma peça musical (ou várias), identificar as partes dessa peça que se repitam, aproximadamente ou não, e que possuam um significado relevante no contexto dessa peça. O objectivo deste trabalho consistiu em estudar a viabilidade da aplicação de algoritmos evolucionários ao problema da extracção de padrões musicais. Para levar a cabo o estudo proposto desenvolvemos duas abordagens utilizando dois tipos diferentes de algoritmos evolucionários: a programação genética e os algoritmos genéticos. Em cada uma das abordagens o objectivo é essencialmente o mesmo: encontrar uma segmentação de uma peça que permita identificar os padrões mais importantes nela existentes. Devido às características de cada um dos algoritmos, a representação utilizada para os indivíduos é diferente. Assim, enquanto que na abordagem baseada em programação genética cada indivíduo é um programa que produz como resultado uma determinada peça, constituindo ao mesmo tempo uma descrição da sua estrutura de segmentos, na abordagem baseada em algoritmos genéticos cada indivíduo consiste numa sequência de símbolos que representa uma hipótese de segmentação da peça a analisar. Embora as funções de avaliação utilizadas nas duas abordagens também sejam diferentes, ambas beneficiam os indivíduos que apresentem o conjunto dos padrões mais importantes existentes na peça. Para ambas as abordagens foi também desenvolvido um método que permite realizar uma segunda segmentação de uma peça a partir dos segmentos identificados na primeira segmentação. Os resultados experimentais obtidos com a abordagem baseada em programação genética que desenvolvemos permitem-nos verificar que esta abordagem apresenta bastantes dificuldades na resolução deste tipo de problemas. Pelo contrário, a abordagem baseada em algoritmos genéticos permitiu obter resultados que nos levam a considerar que a aplicação desta abordagem a este tipo de problemas é viável.

Pattern extraction is a problem that occurs in several areas like, for example, molecular biology and finance, and can be viewed, from the point of view of artificial intelligence, as a kind of unsupervised learning. In the musical domain, the problem can be informally defined in the following way: given a musical piece (or more), identify the meaningful recurrent parts of that piece. The goal of this work is to study the viability of applying evolutionary algorithms to the problem of musical pattern extraction. In order to take this study, we develop two approaches based on two different types of evolutionary algorithms: genetic programming and genetic algorithms. The goal in both approaches is essentially the same: find a segmentation of a musical piece that allows the identification of the most meaningful patterns that exist in that piece. Due to the character of each type of algorithm, the representation used to represent individuals in each approach its different. Hence, while in the genetic programming based approach an individual is a program that produces as a result a musical piece, being at the same time a description of the structure of that piece, in the genetic algorithms based approach each individual is a sequence of symbols that represent a possible segmentation of the musical piece that is being analyzed. The two approaches also use different fitness functions, but both have in common the fact that they give a better fitness value to individuals that present the set of most meaningful patterns. For both approaches we also developed a method to make a second segmentation of a musical piece using the segments identified in the first segmentation. The experimental results obtained with the genetic programming based approach allowed us to verify that this approach has great difficulties in the resolution of this type of problems. On the contrary, with the genetic algorithms based approach we obtained results that allow us to believe that this approach can be useful in the resolution of this type of problems.