Nas ondas do wavelet

A análise numérica de dados é um vasto campo da matemática que tornou-se acessível ao público em geral com o barateamento dos computadores.

Livros como A Lógica do Mercado de Ações de John Allen Paulos, e o clássico Análise de Séries Temporais de Morettin & Toloi, ensinam, por exemplo, peripécias matemáticas que podem tanto ajudar à incautos investidores a como tentar prever e evitar as inconstâncias da bolsa de valores quanto a pequenas indústrias ajustarem sua linha de produção com base na previsão de vendas oriundas de tais técnicas.

A essa imensa literatura disponível, tanto física quanto no mundo virtual, soma-se os inúmeros softwares (muitos deles de custo inacessível a maioria dos mortais) que prometem, em rítmo de produção em massa, mastigar números e cuspir informações, estas últimas de valor inegavelmente estratégico para o incremento da eficiencia num mundo multi-conectado e competitivo de hoje.

Nesse contexto, dentro da minha modesta capacidade, tenho nas últimas semanas reservado tempo para estudar o método de programação genética linear como analisador numérico de dados. Como me deparei no programa que desenvolvi com alguns problemas relacionados a lenta convergência dos modelos encontrados para certas amostras (citado no post anterior), pensei em tentar caminhos alternativos para melhorar esse desempenho.

Com essa idéia na cabeça, comecei a desenvolver um novo programa que permite analisar dados numéricos a partir do método de wavelet (ou, em bom português: ondaletas).

O método de ondaletas surgiu como uma alternativa ao velho método da transformada de Fourier para análise de sinais, permitindo, dentre outras vantagens, uma análise temporal das informações escondidas na amostra estudada, coisa que o método de Fourier não permite pois este último analisa apenas as frequências alí contidas, e não o comportamento destas frequências ao longo do tempo.

Ondaletas são adotadas em diversos campos do saber, como a física (dinâmica molecular, astrofísica, geofísica, mecânica quântica), processamento de imagem (análise de EEG e DNA, clima, reconhecimento da fala e visão artificial), compressão de dados (o famoso JPEG 2000 utiliza essa técnica), em geral substituindo a já citada transformada de Fourier.

O algoritmo que utilizei no programa baseia-se no método discreto de Haars (matemático hungaro precursor desse método), que, a grosso modo funciona assim:

1. Lê-se dois itens da amostra;
2. Aplica-se a eles dois filtros de passagem (isto é, duas funções matemáticas pré-definidas, chamadas de low e high-pass);
3. Obtêm-se dois novos valores, onde cada qual é colocado em amostras diferentes, formando assim duas novas sequências da amostra original;
4. Volta-se ao item 1 até chegar ao final da amostra original.

Ao final do processo as duas novas amostras possuirão metade do tamanho da amostra original, sendo que representarão duas ondaletas dispersas ao longo do tempo, as quais estavam escondidas nos dados analisados.

Os filtros de passagem adotados para implementar o método discreto de Haars impressiona pela simplicidade. Estes foram:

Na imagem abaixo temos um exemplo do programa em funcionamento. Na tela, vemos o sinal de uma função senóide - gerada aleatóriamente – sendo quebrada em duas ondas de frequência menores.

Essa quebra pode ser feita em componentes ainda menores, até um limite imposto pelo tamanho da amostra estudada.

No programa inseri também uma função de forecast, permitindo inferir futuros valores que a amostra irá apresentar caso as ondaletas calculadas se mostrem corretas.

O passo seguinte será implementar uma regressão não linear como método adicional de forecast, bem como integrar esse programa ao de LGP que desenvolvi anteriormente e ver se com isso este último passa a gerar modelos mais precisos dos dados analisados.

Pequenos quadrados….

Ontem atualizei o programa LGPTester para utilizar o conhecidíssimo Método dos Mínimos Quadrados como função de escolha do indivíduo da população que melhor se adequa aos dados analisados.

Essa mudança provocou uma aceleração brutal no tempo de processamento do programa, fazendo-o encontrar mais rapidamente (e com maior qualidade) modelos que se ajustem aos dados analisados.

Na tela abaixo podemos visualizar o LGPTester modelando uma função senóide escolhida aleatóriamente. O programa conseguiu fazer a engenharia reversa dos dados e encontrar um código C que imite o comportamento da função original.

É uma pena que o mesmo ainda não se dá com dados oriundos de geradores pseudo-aleatórios, onde o LGPTester tende a convergir muito lentamente para um modelo coerente.

Um possível motivo para que isso ocorra talvez seja a necessidade ainda de inclusão de novas funções matemáticas (como módulo, por exemplo) ao leque disponível para o programa. Como as funções disponíveis são relativamente simples, talvez o programa só consiga modelar dados oriundos de fontes igualmente simples.

Outra possibilidade seria talvez a necessidade de avaliar os dados sob novos enfoques, rearranjando-os para facilitar a análise pelo programa. Nesse sentido, pretendo implementar três métodos que permitem analisar padrões escondidos em dados: wavelets, return maps e recurrence plots.

Comentarei tais métodos nos próximos posts, a medida que for implementando-os.

TV aberta brasileira: Criacionismo 1 x Evolucionismo 0

Semana passada assisti, em uma TV controlada por um grupo religioso, a uma reportagem tendenciosa que tentava refutar a teoria evolucionista em favor do criacionismo.

Nessa tentativa usaram até como argumentos as “maracutaias” que pseudo-cientistas do século 19 (e inicio dos XX) inventaram em prol de enriquecimento próprio (como falsas ossadas, etc). Porém, desmerecer toda uma teoria só porque existem pilantras que fazem mal uso dela e tentam iludir o público é ignorancia por si só; sem contar que esse tipo de argumento falacioso é muito conhecido na literatura: é o famoso “ad hominem” (isto é, ataque o homem, não sua idéia).

Se partir para esse caminho, tivemos, temos e ainda teremos inumeros malandros que tem na religião sua forma de enriquecimento ilicito.

Porém, o que a reportagem não falou é das irrefutáveis evidencias que o estudo do DNA nos trouxe. Está lá, escrito claramente no DNA, que temos 99% de parentesco com algumas espécies de macacos, e que todos os animais na Terra (inclusive insetos e afins) partilham grande parte do DNA, indicando que todos, de certa forma, temos a mesma origem, mesmo que longíngua.

E não falaram também que a evolução se dá em saltos, coisa que modelos computacionais demonstram ser verdadeiro, já que o processo de combinação e recombinação dos genes a cada geração se passa aleatóriamente. É apenas quando a “sorte” se faz presente que uma dada geração se mostra mais eficiente que os demais (tendo, por mera sorte, alguma leve vantagem), ocorrendo aí a seleção natural e a longo prazo a prevalescencia dos genes desse grupo.

Carl Sagan, em seu ótimo livro “O mundo assombrado pelos demônios” escrito em meados da década de 90, já denunciava a pressão que a teoria da evolução sofria para não ser ensinada nas escolas americanas. Parece que no século XXI o “criacionismo” voltou a tomar força, principalmente num mundo ainda fortemente controlado pela religião.

Como relata Sagan em seu livro:

“Conheço muitas pessoas que se sentem ofendidas com a evolução, que preferem apaixonadamente ser uma obra pessoal de Deus a ter surgido do lodo por forças físicas e químicas cegas ao longo das eras. Elas também tendem a evitar o contato com a evidencia. Esta tem pouco a ver com a questão: o que elas querem que seja verdade, elas acreditam que é verdade. [...] Quando o filme Jurassic Park foi exibido em Israel, alguns rabinos ortodoxos o condenaram, porque aceitava a evolução e porque ensinava que os dinossauros viveram há 100 milhões de anos, quando, como se afirma claramente em todo Rosh Hashanah e toda cerimônia de casamento judaica, o Universo tem menos de 6 mil anos. A evidencia mais clara de nossa evolução ainda é contestada, ironicamente por aqueles cujo próprio DNA a proclama, nas escolas, nos tribunais, nas editoras de livros didáticos [...]”

E nas emissoras de TV brasileiras controladas por facções religiosas, como pude constatar.

Em outro trecho do livro de Sagan encontramos:

“Quando Darwin formulou sua teoria da evolução, ele era ateísta e materialista. [...] Darwin estava prestes a se tornar ministro da Igreja da Inglaterra, quando surgiu a oportunidade de zarpar no H.M.S. Beagle. Suas idéias religiosas, como ele próprio as descrevia, eram na época bastante convencionais. [...] Pela sua investigação da Natureza, pela ciência, começou lentamente a compreender que pelo menos parte de sua religião era falsa.”

Por fim, ele conclui acertadamente:

“Se censurássemos Darwin, que outros tipos de conhecimento seriam também censurados? Quem faria a censura? Quem dentre nós é bastante sábio para saber quais as informações e idéias que podemos descartar sem problemas e quais as que serão necessárias daqui a dez, cem ou mil anos?”

É preocupante quando idéias medievais voltam a povoar a mente do povo, pois, como vivemos na “ditadura da maioria“, acaba por afetar e influenciar as decisões desse (e quem decide por esse) povo como um todo.

O que podemos fazer é não deixar essas idéias contaminarem as mentes dos jovens, esclarecendo-os para não cairem nas armadilhas (principalmente a subserviencia) que a ignorância nos traz.

“É mais freqüente que a confiança seja gerada pela ignorância do que pelo conhecimento: são os que conhecem pouco, e não os que conhecem muito, os que afirmam tão positivamente que este ou aquele problema nunca será solucionado pela ciência.” Charles Darwin, The descent of man (1871).

Modelando o caos

Encontrei um ótimo artigo sobre um experimento feito com um pacote de software baseado na seleção natural (veja em Comparison of Discipulus™ Linear Genetic Programming Software with Support Vector machines, Classification Trees, Neural Networks and Human Experts, seção “Deriving Physical Laws”, de Larry M. Deschaine e Frank D. Francone).

No experimento foi entrado dados de uma equação da física bem conhecida e o computador, mimetizando a teoria evolucionista, chegou como resultado a exata equação original.

Abaixo segue uma livre tradução de um trecho desse artigo:

[...] Nós testamos o programa “Discipulus Lite” e “Standard” em inúmeros domínios de problemas durante a primeira fase de nossa investigação. A primeira fase cobriu cerca de dois anos e tem seus resultados descritos nas próximas três seções [...]

DERIVANDO LEIS DA FÍSICA

O interesse em LGP (linear genetic programming) da SAIC (Science Applications International Corporation’s) era inicialmente baseada na sua potencial habilidade de modelar relações físicas. Assim, seu primeiro teste foi se LGP pode modelar a bem conhecida (ao menos para engenheiros ambientais) lei de Darcy. Essa lei descreve o fluxo da água através de um meio poroso.

A equação é a seguinte:

Q=K*I*A

onde:

Q = fluxo [L3/T],
K = condutividade hidráulica [L/T],
I = gradiente [L/L], e
A = area [L2].

Foi então obtida uma massa de dados real, aplicando-se a lei de Darcy para produzir os resultados que serão usados como amostra.

A essa amostra foi também adicionado 10% de variação aleatória (para camuflar imprecisão) e o software LGP foi rodado em cima dessa nova massa de dados. Após o fim do processo, o melhor modelo gerado pelo sofware foi examinado.

A melhor solução que o software derivou da amostra foram as seguintes quatro instruções:

Q = 0.0
Q += I
Q *= K
Q *= A

Estas instruções são precisamente a lei de Darcy, representada na linguagem ANSI C.

No programa evoluído, Q é um acumulador e, além disso, o resultado final desse programa. [...]

A partir desse estudo empírico, a conclusão chegada por Deschaine e Francone foi que o pacote de software LGP consistentemente produziu excelentes resultados em problemas industriais difíceis, com pouca interferencia humana no algoritmo de aprendizado utilizado por ele.

Além disso, embora o pacote não tenha em geral produzido um melhor resultado que os outros algoritmos estudados (redes neurais, máquinas vetoriais etc), em todo problema analisado ele produziu um modelo que era pelo menos tão bom quanto qualquer outro método de análise numérica pesquisado por eles.

Outro ponto foi que o pacote produziu modelos robustos comparados a outros métodos de inteligencia artificial. LGP identificou quais eram os dados importantes em uma amostra e quais não eram, reduzindo o número de variaveis a serem monitoradas e permitindo uma melhor acertividade além de menor tempo de processamento.

Com base nessa idéia, pensei em testar o programa LGPTester em cima de uma amostra obtida a partir de um gerador de números pseudo-aleatórios, já que este tipo de dado decididamente possui uma função matemática por trás - sendo assim bem mais um exemplo de caoticidade (onde resultados mudam completamente de acordo com o ambiente inicial dado: no caso, a semente do gerador) do que de aleatoriedade  propriamente dita.

No teste que realizei, o programa encontrou modelos que acertavam o dado Y da amostra entre 20 a 25% das vezes.

Embora eu não tenha feito uma análise mais adequada para verificar se 20% de acerto dentre uma amotra de 100 números “aleatórios” não se enquadra dentro do esperado pela “pura sorte” (isto é, por exemplo, tal qual duas pessoas dizendo 100 numeros em sequencia e descobrir que a chance de que certa quantidade desses números sejam idênticos esteja perto dos 20%), não há como negar que esse é um percentual interessante que nos leva a pensar se o modelo não está encontrando alguma relação escondida.

Relações escondidas dentro de geradores de números pseudo-aleatórios é um fato bastante conhecido na literatura, vide o caso da famosa congruencia linear, usada em muitas linguagens de programação, onde surgem padrões quando os dados são plotados em múltiplas dimensões, situação esta chamada de efeito Marsaglia em homenagem a quem a descobriu.

Testei também o programa com alguns dados da lotofácil – no caso, a primeira bola dos últimos 100 sorteios – e verifiquei que rapidamente o programa encontrou um modelo que apostava mais na bola “1″ do que em qualquer outra. O interessante é que estatísticamente essa bola sai em 60% dos sorteios da lotofácil.

Embora apostar na bola “1″ seja um fato fácil de um humano deduzir estatísticamente (veja mais detalhes aqui), o computador chegar a essa conclusão por si só, principalmente através da evolução de programas puramente aleatórios, é um fato intrigante.

Isso também demonstra que outras relações podem ser encontradas pelo programa, caso entremos com os dados certos e deixemos ele processar por tempo necessário.

Estou pensando agora em fazer uma versão em C, a fim de que rode mais rápido, e que use Threads para aproveitar máquinas bi-processadas.

Programação Genética Linear

Ando pesquisando sobre Programação Genética Linear, que trata de gerar automaticamente modelos matemáticos (leia-se: código fonte) a partir de amostra de dados numéricas.

As principais idéias estou tirando da excelente dissertação de Brameier (On Linear Genetic Programming), bem como de uma ferramenta comercial que cumpre bem esse fim (Discipulus).
 
Nessa técnica, os modelos evoluem muito parecido como é descrito na teoria darwinista, isto é: dada uma população aleatória de indivíduos (programas) os quais estão imersos em um ambiente hostil (massa de dados numérica previamente definida), aqueles que melhor se adequarem ao ambiente (mimetizarem a amostra) passam para uma próxima geração (rodada de testes), onde partes deles são propagados para o resto da população. Nesse processo, ainda, a parte da população que menos se adaptou é descartada e novos individuos são gerados aleatóriamente para substituí-los.
 
Assim, em resumo:
 
1) Individuos que apresentam bom desempenho permanecem e distribuem parte de seu código para os indivíduos “medianos” (aqui chamado de “crossover”).
2) Os indivíduos “mediocres” são eliminados e novos individuos – de igual proporção aos eliminados e com código aleatório – são introduzidos na população (aqui chamado de “mutation”).
 
Quem quiser pode pegar o protótipo do programa no seguinte link: LGPTester.
 
Esse programa teste permite analisar amostras no formato X -> Y, isto é, quando executado, o programa busca por uma função de X que resulte em Y para toda a amostra.

Para testar, tente 1 variável e 3 instruções (que dá um desempenho bem interessante). Veja como rapidamente ele consegue modelar funções senóides aleatórias (geradas pelo botão “sample generate”).
 
O código gerado para o modelo, embora simule C, pode ser transcrito para qualquer linguagem (ou até Excel). Isso pode ser feito para, por exemplo, testar a efetividade do modelo em uma massa de dados semelhante mas ainda não analisada.
 
É interessante como mesmo um programa com regras simples como esse consegue chegar a modelos rebuscados, mesmo que seja de matemática elementar.

E é ainda mais interessante como modelos que, de outro modo exigiriam um mínimo de inteligencia para criá-los, podem simplesmente emergir do puramente aleatório, sem magias ou misticismos, nos fazendo ter um pequeníssimo vislumbre do poder da seleção natural.

Como tudo tem um inicio…

Resolvi abrir esse weblog como forma de compartilhar algumas idéias sobre programação, que costumo pesquisar sem muita pretensão ou preciosismo nas minhas horas vagas. Como minha área de interesse é inteligencia artificial, esse tema será bastante recorrente por aqui.

O nome do blog deriva da biologia, mais especificamente da genética. Tive essa idéia quando li uma reportagem que falava que nosso DNA possui muito código “lixo”, ou ainda “inativo”, e que o tamanho do DNA não significa propriamente “complexidade” do organismo, já que há muitas plantas simples que tem sequencias de DNA maiores que o do ser humano.

Podemos fazer um paralelismo disso com o mundo dos bits e bytes, onde nem sempre códigos gigantes apresentam necessariamente comportamento complexos e vice-versa (vide os estudos sobre automatos celulares de Stephen Wolfram).

Isso inclusive nos leva a pensar se simplesmente “inflar” um software com código o fará realmente mais eficiente, ou melhor, ou mais completo, já que isso definitivamente não é o que contribui para esses atributos.

Ou então o inverso: subestimar o problema, isto é, achar que este, por ser simples, terá uma solução igualmente simples. A natureza nos mostra que não é bem por aí. Ela nos ensina que o que vale realmente é o poder de adaptação às mudanças que tal código (ou codificador) tem, já que o mundo real está em constante e ininterrupta evolução.

Fica então a dica para nós meros mortais codificadores de bits e bytes: evolução sempre, de idéias, crenças e atitudes.

E para saber mais sobre o “enigma do valor C”, vale a pena uma consulta nessa reportagem da Folha ou, ainda, sua definição na Wikipedia.

Vale também uma visita aos termos Noncoding DNA e Junk DNA, que falam sobre a parte do DNA que não faz nada de útil e da parte que é meramente lixo.