Estudo sobre abordagens de extração, classificação e predição de comportamento de processos

7/23/2019 Estudo sobre abordagens de extrao, classificao e predio de comportamento de processos

1/100

Estudo sobre abordagens de extrao, classificao epredio de comportamento de processos

Evgueni Dodonov Rodrigo Fernandes de Mello

12 de maio de 2008


2/100

Those who control the past, control the future

George C. Orwell


3/100

Resumo

A rea de predio do comportamento de processos tm despertado ateno nas ltimasdcadas, resultando em novas abordagens, tcnicas e aplicaes.

Este relatrio tcnico tem como o objetivo introduzir e descrever diversas tcnicas quepodem ser utilizadas para determinar e avaliar o comportamento de processos e predizer suas

operaes futuras.Enquanto este material voltado predio do comportamento de processos em sistemas

distribudos, as tcnicas estudadas podem ser aplicadas em diversas reas computacionais.


4/100

Sumrio

1 Introduo 4

2 Estado da arte e trabalhos relacionados 6

2.1 Consideraes iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.2 Avaliao do comportamento de processos distribudos . . . . . . . . . . . . . 62.3 Avaliaes e comparaes entre as tcnicas . . . . . . . . . . . . . . . . . . . 82.4 Aplicaes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Extrao do comportamento de aplicaes 11

3.1 Consideraes iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.2 Organizao e representao do comportamento de processos . . . . . . . . . . 113.2.1 Tcnicas de extrao de comportamento . . . . . . . . . . . . . . . . . 133.2.2 Representao do comportamento de processos . . . . . . . . . . . . . 133.2.3 Ferramentas para extrao do comportamento . . . . . . . . . . . . . . 143.2.4 Ferramentas para avaliao de aplicaes MPI . . . . . . . . . . . . . 15

3.3 Aplicaes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.4 Consideraes finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4 Classificao de padres 18

4.1 Consideraes iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

4.2 Tcnicas estocsticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184.2.1 Modelo de k-mdias . . . . . . . . . . . . . . . . . . . . . . . . . . . 194.2.2 Clusterizao fuzzy de c-mdias . . . . . . . . . . . . . . . . . . . . . 194.2.3 Algoritmo de clusterizao QT . . . . . . . . . . . . . . . . . . . . . . 214.2.4 Classificao linear: SVM (Support Vector Machines) . . . . . . . . . . 22

4.3 Tcnicas baseadas em redes neurais . . . . . . . . . . . . . . . . . . . . . . . 234.3.1 Mapas auto-organizveis SOM . . . . . . . . . . . . . . . . . . . . . 264.3.2 Redes neurais auto-expansveis . . . . . . . . . . . . . . . . . . . . . 284.3.3 Cascade-Correlation Learning Architecture . . . . . . . . . . . . . . . 294.3.4 Growing Cell Structure . . . . . . . . . . . . . . . . . . . . . . . . . . 294.3.5 Growing Neural Gas . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.3.6 Growing Self-Organizing Maps . . . . . . . . . . . . . . . . . . . . . 314.3.7 Restricted Coulomb Energy . . . . . . . . . . . . . . . . . . . . . . . 314.3.8 Contextual Layered Associative Memory . . . . . . . . . . . . . . . . . 314.3.9 Growing When Required . . . . . . . . . . . . . . . . . . . . . . . . . 314.3.10 Adaptive Resonance Theory . . . . . . . . . . . . . . . . . . . . . . . 34

1


5/100

4.3.11 Rede neural SONDE . . . . . . . . . . . . . . . . . . . . . . . . . . . 394.3.12 Radial Basis Function . . . . . . . . . . . . . . . . . . . . . . . . . . 404.3.13 Redes neurais separadoras . . . . . . . . . . . . . . . . . . . . . . . . 40

4.4 Consideraes finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5 Predio do comportamento de processos 44

5.1 Consideraes iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445.2 Tcnicas baseadas no estado atual . . . . . . . . . . . . . . . . . . . . . . . . 44

5.2.1 Cadeias de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455.2.2 Modelo Markov escondido . . . . . . . . . . . . . . . . . . . . . . . . 465.2.3 Modelo HMMHierrquico . . . . . . . . . . . . . . . . . . . . . . . . 475.2.4 Modelo HMMem nveis . . . . . . . . . . . . . . . . . . . . . . . . . 48

5.3 Tcnicas auto-regressivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485.3.1 Auto-regresso linear . . . . . . . . . . . . . . . . . . . . . . . . . . . 495.3.2 Modelos no-lineares . . . . . . . . . . . . . . . . . . . . . . . . . . . 505.3.3 Auto-correlao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.4 Filtro de Kalman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515.4.1 Modelo de Kalman suavizado: Kalman Smoother . . . . . . . . . . . . 535.4.2 Filtro de Kalman estendido . . . . . . . . . . . . . . . . . . . . . . . . 55

5.5 Redes neurais recorrentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565.5.1 Rede LSTM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575.5.2 Rede neural de Hopfield . . . . . . . . . . . . . . . . . . . . . . . . . 615.5.3 Tcnica de Simulated annealing . . . . . . . . . . . . . . . . . . . . . 645.5.4 Mquinas de Boltzmann . . . . . . . . . . . . . . . . . . . . . . . . . 64

5.6 Redes Associativas Competitivas . . . . . . . . . . . . . . . . . . . . . . . . . 655.6.1 Modelo SOMtemporal . . . . . . . . . . . . . . . . . . . . . . . . . . 665.6.2 Modelo SOMauto-regressivo . . . . . . . . . . . . . . . . . . . . . . 665.6.3 Rede neural VQTAM . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

5.7 Predio por meio de atrasos no tempo: TDNN . . . . . . . . . . . . . . . . . 685.8 Aprendizado supervisionado: Reservoir computing . . . . . . . . . . . . . . . 69

5.9 Aprendizado controlado: SRNN . . . . . . . . . . . . . . . . . . . . . . . . . 715.10 Aprendizado Bayesiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725.11 Teoria de informao e entropia . . . . . . . . . . . . . . . . . . . . . . . . . 755.12 Computao bio-inspirada: algoritmos genticos . . . . . . . . . . . . . . . . 775.13 Consideraes finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

6 Concluses 79

2


6/100

Lista de Figuras

3.1 Organizao do comportamento dos processos . . . . . . . . . . . . . . . . . . 12

4.1 Classificao de acordo com o modelo de k-mdias . . . . . . . . . . . . . . . 204.2 SVM separao entre as classes . . . . . . . . . . . . . . . . . . . . . . . . . 224.3 Componentes de uma rede neural . . . . . . . . . . . . . . . . . . . . . . . . . 244.4 Funes de ativao de neurnios . . . . . . . . . . . . . . . . . . . . . . . . . 254.5 Topologia de rede neural . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264.6 SOM: agrupamento de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . 274.7 ART: classificao de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.8 Arquitetura da rede ART 2A . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4.9 Rede neural RBF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.10 Arquitetura da rede RBF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.11 ICA: decomposio de sinais . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

5.1 Exemplo de cadeia de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . 465.2 Exemplo de HMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475.3 Exemplo de HHMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485.4 Exemplo de LHMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495.5 Exemplo de filtro de Kalman . . . . . . . . . . . . . . . . . . . . . . . . . . . 525.6 Exemplo de uma rede neural recorrente . . . . . . . . . . . . . . . . . . . . . 565.7 Rede neural de Elman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5.8 Clula de memria de LSTM . . . . . . . . . . . . . . . . . . . . . . . . . . . 595.9 Exemplo de LSTM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 615.10 Rede TDNN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695.11 Arquitetura de Reservoir Computing . . . . . . . . . . . . . . . . . . . . . . . 705.12 Spiral Recurrent Neural Network . . . . . . . . . . . . . . . . . . . . . . . . . 725.13 Exemplo de rede Bayesiana . . . . . . . . . . . . . . . . . . . . . . . . . . . . 745.14 Exemplo de rvore de dependncias da 2a ordem . . . . . . . . . . . . . . . . 745.15 Cadeia de Markov para clculo de entropia . . . . . . . . . . . . . . . . . . . . 76

3


7/100

Captulo 1

Introduo

A disponibilidade de microprocessadores de baixo custo e a evoluo das redes de compu-tadores motivou o desenvolvimento de sistemas distribudos, possibilitando a realizao deum mesmo trabalho computacional sobre elementos de processamento (EPs), interconectadospor meio de uma rede computacional [35]. Diversos conceitos de sistemas distribudos tmsido adotadas desde a dcada de 1980 para a resoluo de tais problemas, uma vez que estetipo de sistemas pode oferecer alto desempenho a um custo menor, quando comparado com

super-computadores ou mquinas paralelas. Com isso, novas tcnicas voltadas para a execuoeficiente de aplicaes distribudas foram concebidas, tais como mecanismos de distribuioeficiente de tarefas pela rede (balanceamento de carga e migrao de processos) [18, 50, 15],acesso eficiente a dados distribudos (protocolos de baixa latncia e dispositivos de hardwareespecficos) [68, 101, 124] e mecanismos de otimizao de trfego (pr-busca e mecanismosde caching) [12, 68].

Entretanto, a necessidade da adaptao de aplicaes paralelas arquiteturas, bibliotecasou ambientes especficos tm sido um dos maiores problemas para a utilizao de aplicaeslegadas em tais ambientes de forma eficiente. Para isso, a tecnologia conhecida como imagemnica do sistema (SSI Single System Image) foi introduzida, que visa representar um sistemadistribudo como sendo um local, deixando a distribuio de dados e execuo transparente

para as aplicaes do usurio [15].Com isso, a possibilidade da utilizao de ambientes distribudos para aplicaes conven-

cionais tornou-se mais vivel, uma vez que o sistema, de forma transparente, pode distribuire realizar as tarefas computacionais dos usurios automaticamente. Ambientes de balancea-mento de carga e migrao de processos, tais como PBS [18], Cosmic [50], TUI [208] e Mo-six[15], e sistemas de memria compartilhada distribuda (DSM - Distributed Shared Memory)[22, 134, 8, 88] possibilitam a execuo e comunicao transparente de aplicaes sobre umambiente distribudo, geralmente composto por mquinas homogneas e pr-configuradas paraa execuo das aplicaes especficas dos usurios.

Diversos fatores influenciam na utilizao eficiente desses ambientes, tais como as polti-cas de escalonamento e balanceamento de carga [169, 93, 199], protocolos de baixa latncia[64, 73] e mecanismos de entrada e sada [104, 68], mencionados anteriormente. A dependn-cia desses fatores das caractersticas especficas de cada aplicao, como utilizao de recursoscomputacionais, memria, acessos a disco e rede, motivou estudos para distribuir e predizer ocomportamento de aplicaes [199, 198, 110, 32, 179, 203]. Esses estudos demonstraram quea predio do comportamento futuro das aplicaes tem um grande potencial para a otimiza-

4


8/100

o do desempenho do sistema, tendo aplicaes em todas as reas de computao distribudamencionados acima [72, 71].

Diversas tcnicas foram propostas para predizer o comportamento futuro de aplicaes,variando entre abordagens estatsticas, modelos matemticos, redes neurais e computao bio-inspirada.

Este trabalho tem como o objetivo a descrio de principais conceitos e tcnicas que podemser utilizadas para extrair, classificar e predizer o comportamento de aplicaes, e organizadoda seguinte forma: captulo 2 apresenta alguns dos trabalhos relacionados rea de predio docomportamento de processos e suas aplicaes em ambientes distribudos. As principais abor-dagens de extrao do comportamento de processos so apresentadas no captulo 3. Tcnicasde classificao e predio do comportamento so apresentadas nos captulos 4 e 5. Finalmente,captulo 6 conclui este trabalho.

5


9/100

Captulo 2

Estado da arte e trabalhos relacionados

2.1 Consideraes iniciais

A predio do comportamento de aplicaes tem o potencial de aumentar significativamente odesempenho de diversas reas de computao [72, 71, 101], podendo auxiliar no balanceamentode carga, escalonamento de processos e leitura antecipada de dados, resultando em elaboraode diversos trabalhos, abordando as mais variveis tticas de predio.

Este captulo visa apresentar alguns dos trabalhos relacionados classificao e predio docomportamento de processos em ambientes distribudos, ilustrando os diversos caminhos e de-cises tomadas pelos seus autores, demonstrando as suas aplicaes, avaliaes e comparaescom as abordagens atuais.

O captulo organizado em seguintes sees. A seo 2.2 aborda os trabalhos que avaliam ocomportamento de processos distribudos para realizao de tarefas computacionais. Trabalhosreferentes a avaliaes e comparaes entre diversas tcnicas de classificao e predio soapresentados na seo 2.3. E, finalmente, algumas aplicaes prticas de tcnicas de prediodo comportamento so apresentados na seo 2.4.

2.2 Avaliao do comportamento de processos distribudos

Diversos trabalhos tem sido desenvolvidos com o objetivo de determinar e predizer futurasaes de processos com base na avaliao estatstica do seu comportamento.

Estudos sobre as caractersticas de acesso ao sistema de arquivos em sistemas multipro-cessados so apresentados em [150, 181]. Nesses trabalhos, so avaliados as caractersticasde acessos a dados por todos os processos no sistema durante um perodo de duas semanas.Baseando-se nos resultados obtidos, foi demonstrado que a maioria de acessos ocorre de ma-neira repetitiva, possibilitando predizer e antecipar acessos futuros observando a freqncia etaxa de acessos a dados. Com isso, o trabalho demonstra que a utilizao de um mecanismo depredio conjunto com sistema de caching pode otimizar significativamente o desempenho dosistema [150].

Diversos trabalhos relacionados predio de acessos so de autoria de Cortes et al [60,58, 59, 56, 55, 57]. Os trabalhos utilizam um sistema de arquivos paralelo PAFS [60, 57],aplicando diversas tcnicas de predio de acessos em tcnicas de cache e prefetching. Nosistema, os mecanismos de cache so organizados em dois nveis uma srie de caches locais

6


10/100

para cada elemento de processamento do sistema, e um cache global que consiste de um espaode memria nico e compartilhado. A consistncia de caches mantida utilizando tokensrepassados entre caches distintos.

Cortes et al. estendem a discusso do PAFS em [58], avaliando diferentes tipos de acessoao cache local cache hit, remote cache hit e global cache hit. A utilizao de servidoresdedicados para cache (cache servers) apresentada e discutida no trabalho. Visando manter aconsistncia entre diversos caches e diminuir a comunicao entre servidores, introduzido ummecanismo de hashing para determinar de maneira nica a localizao de um bloco de dadosem diversos servidores de cache. No sistema, a predio de acessos feita por meio de tcnicade cadeias de Markov, avaliando a taxa e freqncia de acessos a diversos caches para arquivosindependentes.

Uma outra avaliao do modelo estocstico de Markov apresentada em [204]. Diferente-mente de outros trabalhos, o trabalho visa predizer a ordem de acessos a arquivos independen-tes, e no aos blocos de dados dentro de um mesmo arquivo. Os autores introduzem apresentamquatro abordagens para a determinao do padro de acesso arquivos First Successor, LastSuccessor, Stable Successor e Best-k-out-of-m. O objetivo das tcnicas estudadas o agrupa-mento de arquivos acessados concorrentemente. Como resultado das avaliaes, os autoresafirmam que possvel antecipar at 80% de todos os acessos a arquivos.

Um estudo de predio de acessos em bases de dados distribudas realizado em [232],

apresentando um modelo analtico para a predio de acessos a buffers por meio de avaliaesestocsticas. Como concluses do trabalho, os autores afirmam que a predio de acesso abuffers pode aumentar significativamente a quantidade de transaes por segundo realizados.

Entre os trabalhos relacionados predio de comportamento de processos por meio daavaliao do histrico de operaes passadas possvel destacar os trabalhos de Kots et al.,que tratam da avaliao e predio do comportamento de aplicaes em sistemas distribudos,com o objetivo de extrair diversos padres de acesso [147, 146, 149, 151, 145, 152, 150, 181].

Diversas tcnicas de reconhecimento de padres seqenciais de acesso so apresentadosem [146, 147], apresentando padres de acesso tais como one-block look-ahead, infinite-blocklook-ahead e portion recognition. O algoritmo predictor introduzido pelo trabalho com oobjetivo de detectar automaticamente do tipo de acesso atual da aplicao.

Tratando-se da predio e antecipao de acessos a dados, de grande importncia o traba-lho de Cao et al. [38], que discute as possveis implementaes dos mecanismos de predio,avaliando os algoritmos de prefetching agressivo e passivo, apresentando as vantagens e des-vantagens de cada abordagem. Nesse trabalho, as principais abordagens para a implementaode um mecanismo de prefetching so discutidas, definindo as regras bsicas para um meca-nismo de leitura antecipada eficiente Optimal Prefetching, Optimal Replacement, Do No

Harm e First Opportunity [38, 68].Tpicos de grande relevncia para a rea de antecipao de acessos a dados so apresen-

tados em [227, 138, 139]. Os trabalhos introduzem o termo prefetching, definindo-o comomecanismo para a reduo do tempo ocioso por meio de predio e antecipao de acessos ,

e avaliam diversos algoritmos de predio e leitura antecipada de dados, tais como forestall,fixed horizon, aggressive e reverse aggressive. De acordo com os experimentos realizados, apredio e antecipao de acessos aos dados possibilitam aumentar significativamente o de-sempenho do sistema, diminuindo a latncia dos acessos. Os trabalhos introduzem um sistemade predio e antecipao de acessos para memria global PGMS (Prefetching Global MemorySystem) um sistema que integra os caches locais de cada servidor em um cache global, visvel

7


11/100

para todos os servidores, facilitando a troca de informaes entre os EPs.De acordo com Soloviev et al. [211], possvel utilizar a predio de acessos para me-

lhorar o desempenho de discos rgidos, analisando e re-organizando os acessos paralelos deacordo com a estrutura fsica do disco. Abordagem similar aplicada em sistemas de arquivosparalelos por Aranachalam et el. [10].

Barve et al. [19] avalia dois mecanismos de predio de acessos por meio de prefetching NOM e GREED. O algoritmo NOM avalia constantemente o look-ahead global do sistemadistribudo enquanto o GREED utiliza o look-ahead local para determinar os prximos blocosda seqncia a serem lidos. De acordo com a previso do algoritmo, a seqncia de acessos ablocos re-ordenada, diminuindo o nmero de requisies e melhorando a latncia de acessosaos dados.

Um outro algoritmo de otimizao de acessos aos dados apresentado em [130], que fun-ciona associando prioridades diferentes para todas as requisies de leitura de dados previstas,resultando em melhor desempenho das operaes de entrada e sada por meio de reorganizaodas requisies.

A aplicao de mecanismos de predio em sistemas de memria distribuda discutida em[24, 25]. Os trabalhos apresentam os algoritmos de predio B+ e Adaptive++, que utilizam ohistrico de acessos memria e as invalidaes dos blocos em cache para determinar a listade blocos a serem requisitados no futuro.

Consideraes sobre otimizaes de acesso aos dados por meio de predies de acessosseqenciais e contnuos so apresentados em [212, 158, 68], sendo aplicados a um sistemade arquivos paralelo e distribudo NPFS [104]. Otimizaes para a latncia de operaes deentrada e sada so propostas em [212], visando adaptar de forma dinmica os timeouts demensagens aos parmetros do meio de comunicao utilizado, e so avaliadas por um sistemade vdeo sob demanda distribudo [158]. Estudos sobre predio de acessos em sistemas dearquivos paralelos so realizados em [68], apresentando um sistema de cache e prefetchingadaptativo e auto-configurvel. No trabalho, dois novos algoritmos de prefetching limitedaggressive e prefetch-on-empty so propostos e avaliados junto com algoritmos aggressive e

passive tradicionais. O trabalho tambm introduz o algoritmo de predio de acessos seqen-ciais CPS.

2.3 Avaliaes e comparaes entre as tcnicas

Diversos trabalhos foram desenvolvidos para detectar padres de acessos de forma automtica,tais como os de Sakr et al. [193], que avaliam e comparam trs mtodos de deteco do padrode acesso um baseado em abordagem estocstica de Cadeias de Markov; um baseado em pre-dio linear e um mtodo que utiliza redes neurais (TDNN). O trabalho comparou a eficinciados mecanismos para a predio de acessos a curto prazo (one-step-ahead prediction).

O trabalho conclui que diferentes abordagens so mais apropriadas para diversos tipos deaplicaes. Por exemplo, enquanto em um caso a predio baseada em cadeias de Markov epredio linear conseguiram eliminar 95% de predies erradas e TDNN conseguiu eliminar71% de falhas, em outro caso o preditor linear conseguiu remover somente 1% de falhas, o ba-seado em cadeias de Markov removeu 6% de falhas e o baseado em TDNN conseguiu remover30% de falhas.

Como concluso final, os autores afirmam que, enquanto todas as tcnicas apresentam uma

8


12/100

eficincia compatvel para padres de acesso simples, com o aumento do grau de complexidadede acessos os modelos simples passam a se tornar ineficientes, e o modelo baseado em redesneurais (TDNN) oferece a melhor eficincia.

A predio de comportamento de processos em ambiente multi-processado avaliada em[193]. No trabalho, rede TDNN utilizada para predizer seqncias de acessos memria emprocessadores independentes. Trs aplicaes diferentes so utilizadas como estudo de caso temperature propagation/2D relaxation, multiplicao de matrizes e transformada de Fourier.De acordo com os autores, a rede neural TDNN possibilitou diminuir em at 3.28 vezes onmero de acessos memria desnecessrios, antecipando-os.

Pesquisas realizadas por Kroeger et al. [154] demonstraram que a maioria de acessos adados em de sistemas distribudos ocorre de forma seqencial, sendo que a predio de acessosfuturos baseando-se no histrico de acessos seqenciais passados pode ser feita com a precisode aproximadamente 70 80%. O trabalho apresenta trs mecanismos de predio de acessosa arquivos independentes, comparando a sua eficincia.

Um estudo sobre predio de acessos em sistemas distribudos apresentado em [36], fo-cando em predio de acessos a dados por aplicaes baseadas em MPI e apresentando ummodelo para a predio de acessos baseado em padres de funcionamento de aplicaes distri-budas. O modelo proposto possibilita predizer 80 90% de todos os acessos, otimizando alatncia de acessos memria.

Finalmente, de grande relevncia as competies entre diversas tcnicas de predio apli-cados sries temporais realizadas em [231, 77, 45, 218], avaliando diversas tcnicas de predi-o com o objetivo de determinar a mais adequada para as predies de curto e longo prazo.

2.4 Aplicaes

A evoluo constante e rpida de arquiteturas de processadores torna ineficientes os mtodosconvencionais de acesso aos dados, limitados pelas configuraes do meio de comunicaoutilizado. Visando solucionar esse problema, diversas estratgias tm sido propostas, abordadasa seguir.

Mecanismos de prefetching, tambm conhecidos como leitura antecipada ou reduo detempo ocioso do sistema [227], procuram antecipar o acesso a dados, pr-carregando-os numespao de armazenamento, tal como a memria principal ou cache. A utilizao conjuntadesses mecanismos possibilita diminuir a latncia de acesso a dados, antecipando requisiesao meio de armazenamento. Entretanto, a eficincia dos mecanismos de prefetching limitadapela necessidade de determinar de forma correta o comportamento, ou padres de acesso, dasaplicaes.

Uma arquitetura de memria compartilhada distribuda voltada para jogos multi-usurio apresentada em [195], utilizando o sistema operacional Plurix OS, baseado na plataforma Javacom sistema de endereamento de memria global. O mecanismo de memria compartilhadautilizado baseado no conceito de transaes atmicas para manter a consistncia de dados.

Nesse sistema, a memria compartilhada utilizada para armazenar as informaes sobre oambiente distribudo de maneira consistente. Cada participante de ambiente requisita informa-es atualizadas sobre o ambiente da memria compartilhada periodicamente, atualizando osseus dados locais, e variando a periodicidade destas requisies de acordo com a capacidade deprocessamento de cada EP. Dessa forma, pode-se diminuir a taxa de atualizaes de dados nos

9


13/100

computadores com menor poder de processamento, ao mesmo tempo mantendo uma viso con-sistente do ambiente distribudo. Por exemplo, no caso de um objeto se movendo no ambientedistribudo, computadores mais potentes podem visualizar o movimento completo do mesmoe os computadores com menor poder de processamento podem visualizar somente alguns dostrechos de movimento. A predio de tais eventos essencial para a utilizao eficiente dosistema.

Um mecanismo de memory ushering, que visa a utilizao da memria de processadoresdistintos atravs de migrao de processos ou swapping, introduzido em [14]. A principal di-ferena com os modelos tradicionais de DSMconsiste na utilizao no-uniforme da memria,sendo que o algoritmo de distribuio de acessos memria visa colocar um nmero mximode processos ativos no mesmo cluster, evitando thrashing ou swapping. Um algoritmo de ba-lanceamento de carga convencional utilizando enquanto a memria livre de um processadorno ultrapassa um pr-determinado valor. Nesse caso, um algoritmo diferente ativado, mi-grando o processo para um elemento de processamento com memria disponvel. O trabalhodemonstrou que a predio de acessos s pginas de memria essencial para o desempenhodo sistema.

Martin et al. [168] adotam o conceito de conjuntos de destino para otimizar a consistnciade dados. Um conjunto de destino definido como um conjunto de elementos de processa-mento que recebem uma mesma requisio para garantir consistncia de memria. O trabalho

prope a adoo de duas tcnicas: a primeira baseada em protocolos snoopy que visa enviaras requisies de consistncia de memria para um conjunto mximo de EPs, permitindo di-minuir a latncia de sharing misses ao custo de uma largura de banda maior. A segunda baseada na utilizao de um servio de diretrio centralizado que envia requisies para umconjunto mnimo de EPs para diminuir a largura de banda necessria. A predio de acessos memria compartilhada possibilita diminuir significativamente a latncia e a largura de bandanecessrios.

Finalmente, estudos sobre aplicaes de tcnicas de predio de acessos a dados distri-budos em mecanismos de leitura antecipada e balanceamento de carga so apresentados em[72, 71], propondo um modelo para predio do comportamento de processos por meio declassificao e predio de seus acessos. O trabalho separa o processo de predio de acessosem trs estgios: o de extrao do comportamento de acessos, o de classificao e agrupamentode acessos similares e o de predio. Diversas tcnicas podem ser utilizadas em cada um dosestgios, variando entre abordagens estatsticas e baseadas em redes neurais. Em [72], redesneurais ART2A e TDNN so avaliadas, avaliando a sua eficincia sobre o NPB (NAS Parallel

Benchmark).

10


14/100

Captulo 3

Extrao do comportamento de aplicaes


Diversas pesquisas demonstraram que a previso de comportamento de um processo tem opotencial de melhorar significativamente a eficincia de execuo de processos em ambien-tes distribudo [72, 170, 71]. A determinao correta do comportamento de um processo ,portanto, essencial para a predio das suas aes futuras, podendo ser utilizada por diversas

tcnicas de otimizao do desempenho e eficincia do sistema.Para isso, necessrio avaliar o comportamento do processo, detectando seus padres de

execuo e acesso a dados. Tratando-se de acessos seqenciais, o padro de acesso pode serdeterminado de maneira simples [148]. Entretanto, a determinao de um padro de acessono-seqencial necessita de tcnicas ou ferramentas especiais [72, 71].

Este captulo apresenta as tcnicas que podem ser aplicadas para a extrao e representaodesse comportamento.

3.2 Organizao e representao do comportamento de pro-

cessosO comportamento de processos pode ser representado de acordo com diversos parmetros querepresentam as suas caractersticas fundamentais. De forma geral, o conhecimento sobre ocomportamento de processos pode ser organizado em nveis global e isolado, conforme de-monstrado na figura 3.1.

O nvel global tem como o objetivo o agrupamento de todas as informaes sobre as aplica-es em execuo no sistema, tendo como as caractersticas comuns o seu tempo de execuoe sua relao com a carga total do sistema. Estes parmetros podem ser utilizados para ma-pear o tempo de execuo de uma aplicao especifica em funo de quantidade de recursosconsumidos por ela, quantificando tais recursos de forma previsvel.

Essas caractersticas podem ser organizadas em classes, por exemplo, agrupando-as pelonome do usurio ou da aplicao. Esta abordagem amplamente utilizada em ambientes degrades, sendo a base de diversos modelos de grid economy [1].

O nvel isolado, por sua vez, representa o comportamento da aplicao em funo dastarefas especficas exercidas por ela, tais como a interao com usurios e utilizao de recursoscomputacionais.

11


15/100

Figura 3.1: Organizao do comportamento dos processos

O comportamento de aplicaes em relao interao com usurio pode ser classificadocomo interativo, para aplicaes que precisam de interao com o usurio; e no-iterativas,tambm conhecido como processamento em lote, para as que no necessitam de interao

explcita.O padro de utilizao de recursos permite classificar as aplicaes em seguintes classes: asorientadas processamento (CPU-Bound), representando as aplicaes voltadas para clculose processamento de dados; as orientadas a Entrada e Sada (IO-Bound), agrupando aplicaescom predominncia de transferncias e acessos a dados; e as voltadas para comunicao (Com-munication Intensive), que abrange processos caracterizados por troca excessiva de mensagenscom outros elementos de processamento.

Alm disso, possvel classificar as aplicaes de acordo com o grau de paralelismo, de-terminando a capacidade da utilizao de mais de um elemento de processamento em paralelo.Neste contexto, o grau de paralelismo representa o nmero de EPs que maximiza a eficin-cia da execuo da aplicao. Da mesma forma, o grau de paralelismo mnimo determina aquantidade mnima de EPs no sistema para a execuo da aplicao; e o paralelismo mximorepresenta o nmero mximo de elementos de processamento que podem ser utilizados pelaaplicao de forma eficiente.

A classificao de aplicaes de acordo com a flexibilidade determina a capacidade deadaptao a ambientes variveis, representando a sua eficincia em relao s decises toma-das pelo escalonador do sistema na atribuio de recursos do sistema [85]. Uma aplicaoinflexvel, neste contexto, sempre necessita de uma configurao de ambiente pr-determinada,sendo que sua execuo em um sistema diferente invivel ou difcil. Aplicaes flexveis, porsua vez, podem ser classificadas em moldveis e maleveis.

As aplicaes maldveis so caracterizadas pela possvel adaptao ao ambiente somente

no incio da execuo. As maleveis, entretanto, permitem uma flexibilidade ainda maior,adaptando-se configurao do ambiente durante a execuo. As aplicaes flexveis geral-mente so construdas utilizando o modelo de paralelismo de dados.

12


16/100

3.2.1 Tcnicas de extrao de comportamento

A extrao de comportamento de aplicaes pode ser realizada de duas maneiras. A primeiraabordagem consiste na avaliao esttica, onde a aplicao analisada de maneira emprica,sem a necessidade de execuo. A segunda, tambm conhecida como avaliao dinmica,consiste na extrao de comportamento durante execuo, sem utilizao do conhecimentoprvio.

A abordagem de avaliao esttica uma das tcnicas mais antigas, sendo concebida nadcada de 1930 por Church e Turing [87]. Originalmente, a tcnica foi aplicada s mquinas

de estados finitos e mquinas de Turing [87], com o objetivo de determinar possveis falhas quepodem levar a um estado de empasse, finalizando a execuo de maneira imprevista.

Com a evoluo de sistemas computacionais, novas tcnicas de avaliao esttica forampropostas. Atualmente, entre tais tcnicas pode-se citar o mtodo de verificao de modelo[177, 76, 100, 111], que consiste na reduo da aplicao para uma representao formal atra-vs de um autmato; e o mtodo de interpretao abstrata [51, 115, 164, 228], que consiste naavaliao do sistema modelando-o na forma de uma mquina de estados abstrata, representandocada declarao por um estado.

A tcnica de avaliao dinmica, por sua vez, permite investigar o comportamento da apli-cao durante a sua execuo, geralmente com o auxlio de ferramentas de monitoramento oudepurao. possvel dividir as tcnicas de avaliao dinmica nas de monitoramento contnuoe baseadas em eventos [128].

Tcnicas de monitoramento contnuo consistem na avaliao peridica do estado de aplica-es em execuo, permitindo extrair as variaes do comportamento. Essa tcnica geralmente mais simples de ser utilizada, uma vez que no necessita de alteraes em aplicaes. Con-tudo, sua desvantagem est relacionada ao fato de que o monitoramento ocorre continuamente,introduzindo um overheadna execuo. Outra desvantagem dessa abordagem est relacionadaao fato de no possibilitar a extrao do comportamento de aplicaes em estados de execuoespecficos.

A tcnica baseada em eventos avalia o estado de execuo de aplicaes em estados pr-definidos, permitindo uma melhor extrao de comportamento, uma vez que apenas aes em

etapas relevantes so capturadas para posterior anlise. Geralmente, esta tcnica apresentamaior complexidade para adoo, necessitando de conhecimento prvio sobre o funcionamentodas aplicaes avaliadas. Alm disso, a necessidade de adaptar aplicaes para o processo deinterceptao de eventos (atravs de instrumentao ou interceptao de chamadas) torna essatcnica mais complicada para uso.

Como vantagem dessa abordagem pode-se citar a determinao do comportamento de apli-caes em perodos de execuo especficos (por exemplo, nos pontos de sincronizao entreprocessos distribudos). Alm disso, o overhead introduzido na execuo menor, uma vezque a avaliao do comportamento no contnua.

3.2.2 Representao do comportamento de processosA avaliao do comportamento histrico de uma aplicao permite predizer suas prximasoperaes. Para isso deve-se analisar as mudanas de comportamento e freqncia dessas alte-raes.

Geralmente, o comportamento de processos ao longo do tempo representado por meio

13


17/100

de sries temporais, um conjunto de observaes feitas seqencialmente ao longo do tempo.Enquanto em modelos de regresso linear a ordem das observaes irrelevante para a anlise[136], tal ordem fundamental para anlise de sries temporais, uma vez que as observaesvizinhas geralmente so inter-dependentes. Desse modo, uma srie temporal pode ser utili-zada para analisar e modelar o comportamento de um processo, avaliando a dependncia entreobservaes subseqentes e possibilitando a previso de acontecimentos futuros.

Duas abordagens podem ser empregadas para estudar uma srie temporal. A primeira abor-dagem define a anlise da srie como sendo um mtodo para entender o comportamento doprocesso que a gerou. A outra abordagem visa realizar predies a partir da srie, construindomodelos matemticos a partir de quais possvel estimar e predizer acontecimentos futuros.

Por exemplo, o comportamento de um processo pode ser representado por meio de umasrie de transies entre estados em execuo e ocioso ao longo de tempo. Representadoo estado em execuo como 1, e estado ocioso como 0, a srie temporal que representaria ocomportamento de tal processo durante n = 10 intervalos de amostragem pode ser representadacomo X = [X1, X2, . . ,Xn] = [0, 1, 0, 1,.., 1].

Dessa forma, uma srie temporal representa o conjunto seqencial de eventos, podendo serreduzida para uma equao obtida por meio de uma regresso linear ou no-linear.

3.2.3 Ferramentas para extrao do comportamento

Umas das tarefas mais comuns na avaliao do comportamento de aplicaes a anlise do seucdigo fonte. As abordagens mais comum consistem na avaliao manual de cdigo, utilizandoferramentas como grep, finde sed[69].

A utilizao de aplicaes para indexao de cdigo fonte, como LXR, Doxygen e JavaDoc,possibilita visualizao mais eficiente do comportamento, possibilitando observar as interaesentre classes, funes e trocas de mensagens. Enquanto algumas dessas ferramentas necessitamde uma instrumentao especfica de cdigo fonte por meio de comentrios, como JavaDoc e

Doxygen, ferramentas como LXR realizam indexao automaticamente.A avaliao dos problemas presentes nas aplicaes pode ser feita de maneira automtica,

utilizando ferramentas como Lint, Blast e Valgrind, que permitem identificar falhas mais co-muns em aplicaes, tais como uso incorreto de memria, casting incorreto de parmetros,etc. Uma outra abordagem consiste em adaptao automtica do cdigo fonte de aplicaes,determinando, analisando e modificando seus pontos crticos. Um modelo semi-automtico detransposio e avaliao de cdigo fonte foi proposto por Quadrado [187], com o objetivo deauxiliar na avaliao e transformao de aplicaes seqenciais em paralelas.

Para avaliar o comportamento de aplicaes de maneira dinmica, vrias tcnicas podem serempregadas. Dentre elas est a de tracing, baseada em visualizao da seqncia das chamadasdo sistema feitas pela aplicao. Essa tcnica utilizada nas ferramentas strace e GridBox [74].

Nessa abordagem utilizada uma chamada do sistema especfica ptrace [69] que indicaao ncleo do sistema operacional que um processo est em depurao. Dessa maneira, o sis-

tema passa a controlar a execuo do processo, rastreando chamadas de sistema, e permitindoexecutar operaes arbitrrias a cada chamada interceptada. possvel, alm de monitorar,interferir no funcionamento dos processo, por exemplo, interceptando as funes de aberturade arquivo e, caso o acesso no seja autorizado, abortar a operao.

Uma vez que o funcionamento do ptrace ocorre no nvel do ncleo do sistema, no poss-vel interceptar funes de alto nvel. Quando a interceptao de funes de diversas bibliotecas

14


18/100

necessria, os recursos do carregador dinmico de bibliotecas do sistema ld.so podem serempregadas. Utilizando variveis de ambiente LD_PRELOAD e LD_LIBRARY_PATH, pode-seinterceptar as chamadas de funes de bibliotecas compartilhadas de maneira transparente, mo-nitorando ou alterando o seu funcionamento [69]. Como exemplo dessa abordagem, possvelcitar o GridBox [74] para ambientes Linux.

Outra abordagem de monitoramento e controle da execuo de aplicaes consiste na utili-zao de um depurador, como, por exemplo, gdb, presente nos ambientes UNIX. Com a ajudada ferramenta, possvel monitorar diversos breakpoints na execuo de aplicaes, observaro comportamento de funes, analisar o contedo da pilha e registradores.

Como exemplo de ferramentas de monitoramento contnua pode-se citar [70] e [199]. Aprimeira ferramenta, conhecida como StatMonitor, monitora o funcionamento de aplicaesno nvel do usurio, coletando informaes sobre seu funcionamento periodicamente [135]. Asegunda abordagem utiliza um kernel Linux modificado para monitorar aplicaes de maneiratransparente.

3.2.4 Ferramentas para avaliao de aplicaes MPI

Um dos mecanismos mais comuns para programao paralela a tecnologia de passagem demensagens Message Passing Intreface (MPI) [33, 214]. Esse mecanismo oferece recursos

de troca de mensagens entre diversos computadores do sistema, possibilitando transmissosncrona e assncrona de dados entre os EPs.

Entre diversas implementaes de MPI, pode-se citar MPICH [102, 103] e LAM-MPI[33, 214], ambas amplamente utilizadas e disponveis livremente. Como exemplo de imple-mentao proprietria de MPI pode-se citar Intel MPI Library (anteriormente denominadoVampir) [178].

Inicialmente, MPI foi concebido para ser utilizado em ambientes de cluster, com configu-raes homogneas e sem suporte s possveis falhas nos EPs. Entretanto, com o crescimentodo uso de ambientes distribudos, isso tornou-se uma desvantagem clara. Dessa maneira, novasverses de MPI foram projetadas, oferecendo suporte para ambientes heterogneos distribu-dos, tais como grids computacionais [235].

Uma vez que a tecnologia MPI implementada na forma de uma biblioteca de funes, asopes de depurao e monitoramento das aplicaes so limitadas, sendo necessria a utiliza-o de ferramentas ou bibliotecas especficas.

Uma das ferramentas para monitoramento, depurao e anlise de aplicaes paralelas am-plamente utilizada Intel Trace Tools (originalmente Vampir) [178], a qual permite tanto umaavaliao contnua de aplicaes MPI quanto baseada em eventos. A ferramenta oferece su-porte para execuo controlada, tracing da aplicaes, controle de fluxo e visualizao dosparmetros de comunicao entre os EPs durante a execuo, sendo que dividida em duasaplicaes: Intel Trace Collector, utilizado para a coleta on-line das informaes referentes execuo da aplicao e Intel Trace Analyserque analisa as informaes adquiridas.

O monitoramento e extrao do comportamento de aplicaes so realizados por meio deuma biblioteca compartilhada, dinamicamente ligada a uma aplicao MPI. Os dados adquiri-dos so armazenados em formato STF (Structured Trace Format). A anlise de dados pode serfeita com a utilizao do Intel Trace Analyser, utilizando uma interface grfica para identificarpontos crticos, visualizar a seqncia e o fluxo de dados, e observar o comportamento de apli-caes em diversos EPs. Alm disso, possvel instrumentar o cdigo fonte de uma aplicao

15


19/100

MPI utilizando funes especficas da ferramenta, as quais definem, de maneira precisa, osdados a serem capturados.

Uma abordagem similar utilizada no sistema MPE (Multi Processing Environment), com-posto por um conjunto de bibliotecas, aplicaes e ferramentas grficas para anlise de desem-penho de aplicaes MPI. O sistema utiliza abordagem baseada em eventos, oferecendo umconjunto de bibliotecas para tracing de eventos MPI, similares ao Intel Trace Tools, junto comum visualizador grfico de eventos. O ambiente disponvel livremente.

Uma outra biblioteca que oferece funcionalidades para instrumentao de cdigo MPI MPICL. Essa biblioteca oferece funes de instrumentao de aplicaes MPI e encontra-sedisponvel para diversas arquiteturas paralelas. Entretanto, necessria instrumentao manualde cdigo fonte.

Outra ferramenta que permite avaliar aplicaes MPI a mpiP. Ela composta por umabiblioteca de anlise estatstica de eventos de aplicaes distribudas (profiling).

Alm disso, pode-se citar a aplicao Xmpi que permite visualizar eventos e fluxo de dadosentre os EPs para aplicaes MPI. Aplicaes devem utilizar arquivos .trace, gerados automa-ticamente em sua execuo.

Entretanto, a grande maioria das ferramentas de avaliao de MPI existentes limitada,pois no oferecem suporte completo para avaliao automtica de aplicaes sem a necessi-dade de alterao e instrumentao de cdigo fonte. Para isso, uma nova tcnica de avaliao

on-line transparente de aplicaes distribudas foi proposta em [72], utilizando o conceito deinterceptao dinmica de chamadas do sistema e baseado no pelo projeto GridBox [74].

3.3 Aplicaes

O comportamento extrado de processos pode ser classificado e analisado segundo tcnicasestatsticas [65, 85], histrico de execues [99, 209], algoritmos de avaliao on-line de com-portamento [9, 205], extrao e classificao do comportamento para predizer futuras aes dasaplicaes [198, 199].

Em [65], uma abordagem estatstica proposta para predizer os requisitos de CPU, entrada

e sada e memria de aplicaes, atravs da utilizao de agrupamento (clustering) estatstico(utilizando o algoritmo de k-mdias) e modelo de cadeias de Markov para identificar regiesde aplicaes com maior uso de recursos.

Uma abordagem similar utilizada em [85], onde os autores executam repetidamente umamesma aplicao e analisam variaes de seu comportamento. Uma baixa variao entre exe-cues sucessivas observada no trabalho, o que permitiu utilizar as caractersticas funcionaisde aplicaes para determinar seus comportamentos sem a necessidade de cooperao explcitado usurio.

Outros trabalhos [99, 209] classificam de maneira esttica o comportamento de processossegundo seus histricos de execues, determinando valores mdios de uso de CPU, mem-ria e mecanismos de entrada e sada para cada grupo. Os valores derivados so utilizados,posteriormente, para predizer o comportamento de aplicaes.

Estratgias de predio on-line do comportamento de processos utilizando o modelo deBayes [20] e lgica fuzzy so apresentadas em [205]. Uma abordagem similar utilizada em[9] e [54], onde informaes coletadas durante a execuo so utilizadas para controlar o me-canismo de balanceamento de carga.

16


20/100

Uma abordagem que utiliza tcnicas de inteligncia artificial para classificao e prediodo comportamento apresentada em [198, 199, 172]. Nesses trabalhos o comportamento deaplicaes automaticamente extrado e classificado, por meio de redes neurais, de acordo coma utilizao de recursos computacionais. A avaliao do comportamento histrico de aplicaes utilizada pelos autores para otimizar as polticas de balanceamento de carga [200, 201, 202,171].

Uma ferramenta para anlise dos padres de acesso nos mecanismos de memria compar-tilhada distribuda proposta em [82]. A ferramenta permite a gerao de traces e visualizaodo funcionamento da memria compartilhada distribuda, identificando acessos, possveis pro-blemas de desempenho e fluxo de comunicao entre elementos de processamento. O sistemautiliza a plataforma Java com espao global de endereamento distribudo, baseado em umsistema prprio de memria compartilhada, utilizando recursos da plataforma Java e ofere-cendo objetos com suporte a escrita mltipla. A ferramenta permite identificar sincronizaesde acesso memria compartilhada, leituras e escritas em objetos distribudos e migraes deobjetos. Experimentos comprovam uma queda de desempenho em torno de 2% causada pelacoleta de informaes (tracing).

Uma abordagem que utiliza as tcnicas de classificao e predio do comportamento deprocessos em sistemas distribudos apresentada em [72]. No trabalho, NAS Benchmark avaliado utilizando redes neurais e modelos estatsticos, demonstrando que as abordagem que

misturam estas tcnicas apresentam uma eficincia maior de que as abordagens individuais.

3.4 Consideraes finais

Neste captulo foram apresentadas as principais tcnicas de extrao de comportamento de apli-caes. O comportamento pode ser extrado atravs da avaliao do cdigo fonte dos mesmosou utilizando uma das tcnicas de extrao on-line do comportamento. Ferramentas para ambasas abordagens foram apresentadas.

17


21/100

Captulo 4

Classificao de padres


Classificao de padres um processo estatstico que visa agrupar padres similares em di-versas classes, ou clusters, de acordo com as suas caractersticas.

Enquanto possvel utilizar dados extrados do comportamento de processos sem o pro-cesso de classificao, tal abordagem resulta em uma grande quantidade de variveis repeti-

tivas ou similares, o que dificulta a sua anlise. Neste caso, possvel empregar tcnicas declassificao ou agrupamento com o objetivo de reduzir a dimensionalidade de dados. Dessamaneira, possvel agrupar comportamentos similares e realizar predies sobre os pontosmais relevantes.

Diversas tcnicas de classificao podem ser empregadas para a classificao de padres,como as abordagens estatsticas e baseadas em redes neurais.

Entre as abordagens estatsticas, pode-se citar o modelo de k-mdias, c-mdias, clusteriza-o QT e Support Vector Machines. As baseadas em redes neurais so mais variadas, incluindomapas de Kohnen (tambm conhecido como modelo SOM), redes neurais auto-expansveis,tais como GCS, GNG, GSOM, RCE, GWR e SONDE, e outros modelos como redes RBF, ARTe ICA.

O objetivo deste captulo a apresentao e discusso das principais tcnicas de classifi-cao de padres descritas na literatura. Enquanto o foco do trabalho a sua aplicao emclassificao do comportamento de processos distribudos, tais tcnicas podem ser aplicadasem outras reas de computao.

As tcnicas apresentadas so classificadas de acordo com a abordagem utilizada, sendo queas baseadas em modelos estatsticos e estocsticos so apresentados na seo 4.2, e as baseadasem redes neurais na seo 4.3. A seo 4.4 sumariza as tcnicas apresentadas e conclui estecaptulo.

4.2 Tcnicas estocsticasEntre diversas tcnicas utilizadas para classificar o comportamento de processos possveldestacar alguns modelos estatsticos, tais como os modelos de k-mdias e SVM.

Esta seo tem como o objetivo descrever tais tcnicas e suas aplicaes para a classificaodo comportamento de processos.

18


22/100

4.2.1 Modelo de k-mdias

O modelo de k-mdias um modelo de clusterizao iterativa, que visa agrupar os objetos em kparties [31, 84, 196, 4, 53]. O modelo tem como o objetivo a minimizao do erro quadrticomdio, ou a varincia total intra-cluster, conforme a equao 4.1, onde existem k clusters Si,sendo i = 1, 2,..,k, e i representando o centride, ou a mdia central de todos os padres deentrada xj Si .

V =

ki=1

xjSi |x

j i|

2

(4.1)

Diversos algoritmos foram propostos para a classificao de acordo com o modelo, sendomais conhecido o de Lloyd [132], descrito a seguir:

1. Particionar o espao de entrada em k clusters iniciais. Esse particionamento pode serfeito tanto da forma aleatria quanto por meio de utilizao de uma heurstica;

2. Para cada amostra:

(a) Encontrar o centride, ou o ponto mdio, mais prximo;

(b) Atribuir a amostra a clustercorrespondente;(c) Recalcular o centride do cluster;

3. Repetir o algoritmo at os valores dos centrides dos clusters permanecerem constantes.

Um exemplo de classificao realizada pelo modelo de k-mdias demonstrado na figura4.1, apresentando o resultado de classificao das entradas em um conjunto de clusters defini-dos.

O modelo de k-mdias encontra o mnimo local, no necessariamente convergindo a umasoluo tima, sendo que o resultado final influenciado pela configurao inicial dos clusters

e amostras. A grande vantagem desta tcnica, entretanto, o seu baixo custo computacional, oque possibilita executar o procedimento repetitivamente at conseguir resultado adequado.

4.2.2 Clusterizao fuzzy de c-mdias

A tcnica de clusterizao fuzzy de c-mdias similar ao modelo de k-mdias, com a diferenade que, ao invs de pertencer a um nico cluster, para cada amostra calculado um grau desemelhana a todos os clusters presentes no sistema [163, 127, 185, 161]. Dessa forma, cadaponto x tem um coeficiente uk(x), que determina o seu grau de semelhana com o cluster k.Geralmente, a soma desses coeficientes igual a 1, conforme a equao 4.2, sendo N o nmerode clusters.

k=1

Nuk(x) = 1 (4.2)

Neste modelo, o centride calculado como sendo a mdia de todos os pontos presentes nosistema, de acordo com a sua semelhana ao cluster atual, conforme demonstrado na equao4.3, onde ck centride do clusterk e m constante de normalizao.

19


23/100

Figura 4.1: Classificao de acordo com o modelo de k-mdias

ck =

x uk(x)

mxx uk(x)

m(4.3)

O grau de similaridade de uma amostra cada cluster determinado atravs da equao4.4, onde uk(x) representa a semelhana do ponto x em relao ao clusterk.

uk(x) =1

dc(k, x)(4.4)

Os coeficientes so normalizados, utilizando um coeficiente real m > 1, para satisfazeras equaes 4.5 e 4.6, sendo m uma constante fuzzy de normalizao e d a distncia entre os

padres.

kj

uk(x) = 1 (4.5)

20


24/100

uk(x) =1

j (d(ck,x)d(cj ,x)

)2

m1

(4.6)

Para m igual a 2, a equao 4.6 resulta numa normalizao linear dos coeficientes, ondea soma resulta em 1. Quando o valor de m aproxima-se a 1, os pontos mais prximos docentro do clusterrecebem pesos maiores, e o comportamento do modelo torna-se similar ao dek-mdias.

O funcionamento do algoritmo de c-mdias descrito a seguir:

1. Particionar o espao de entrada em k clusters iniciais. Este particionamento pode serfeito tanto da forma aleatria quanto por meio de utilizao de uma heurstica.

2. Para cada amostra:

(a) Calcular o valor do centride de cada cluster;

(b) Para cada amostra, calcular os coeficientes correspondentes aos clusters presentesno sistema;

3. Repetir o algoritmo at que a variao dos coeficientes entre duas iteraes consecutivas

do algoritmos seja inferior a .

O modelo de c-mdias visa minimizar a varincia intra-clusters. Entretanto, sendo simi-lar ao modelo de k-mdias, ele encontra mnimos locais, nem sempre convergindo para umasoluo tima.

4.2.3 Algoritmo de clusterizao QT

Algoritmo de clusterizao QT (Quality Threshold) [116, 129] um mtodo de agrupamento dedados alternativo, proposto inicialmente para a clusterizao de genes do cromossomo humano.Enquanto ele requer maior poder computacional para atingir o resultado, o seu funcionamentono depende da pr-determinao do nmero de clusters, sempre retornando o mnimo globalda soluo.

O algoritmo de clusterizao QT apresentado a seguir:

1. Inicialmente, necessrio escolher o dimetro mximo para cada cluster;

2. Para cada amostra, encontrar o cluster-candidato mais apropriado, considerando a dis-tncia do ponto atual at o ponto mais prximo do cluster, repetindo esse procedimentopara todos os clusters que esto dentro do limite pr-estabelecido pelo dimetro do passo1;

3. Salvar o cluster-candidato que tem o maior nmero de amostras como sendo o primeiroclusterverdadeiro, removendo todos os pontos que pertencem a ele das iteraes futuras;

4. Repetir o algoritmo com o nmero de pontos reduzidos, at que todas as amostras sejamalocados nos clusters.

21


25/100

Figura 4.2: SVM separao entre as classes

O valor de proximidade entre uma amostra e um cluster calculado considerando a distn-cia mxima entre ela e todos os pontos pertencentes ao cluster.

O modelo resulta em uma clusterizao mais precisa, uma vez que um numero adequadode clusters alocado para cada caso. O custo computacional do modelo, entretanto, signifi-cativamente maior de que o do modelo de k-mdias e c-mdias.

As tcnicas de classificao iterativa tambm podem ser utilizadas para a predio de pa-dres, conforme demonstrado em [65], onde o modelo de k-mdias utilizado para identificare predizer diversos estados de execuo de processos.

4.2.4 Classificao linear: SVM (Support Vector Machines)

SVM (Support Vector Machines) uma tcnica de aprendizagem linear supervisionada, voltadapara classificao e regresso de padres. Uma caracterstica especial desta famlia de tcnicasconsiste no fato delas minimizarem o erro emprico de classificao, maximizando ao mesmotempo a margem geomtrica de erro. Com isso, essas tcnicas so tambm conhecidas comoclassificadores de margem mxima (maximum margin classifiers) [197, 221, 240, 210].

A tcnica consiste em mapeamento de vetores de entrada em um espao amostral comdimenso superior, por meio de construo do hiper-plano mximo de separao. Para isso,dois hiper-planos auxiliares so construdos, de uma forma que o hiper-plano de separaoresultante maximize a distncia entre eles. assumido que, quanto maior for a margem dedistncia entre os planos, menor o erro de generalizao do classificador.

A tcnica de SVM classifica os padres de entrada representados por um vetor de pesos-dimensional em diversas classes, com o objetivo de separar tais classes com um hiper-plano

de dimenso 1. Alm disso, a tcnica visa encontrar um hiper-plano que possibilita a maiorseparao entre as classes ou seja, encontrar um cuja distncia at o padro atual de entradaseja mxima, conhecido como hiper-plano de margem mxima (ou maximum-margin hyper-

plane). Como possvel ver na figura 4.2, enquanto trs hiper-planos podem ser construdospara os valores de entrada considerados, somente um resulta em separao mxima entre asclasses.

22


26/100

O algoritmo de SVM pode ser descrito da seguinte forma:Considerando X R0 n os vetores de entrada, y {1, +1} os eixos, e : R0 F

a funo de mapeamento do espao de entrada para o espao de apresentao, o algoritmo visaencontrar um hiper-plano (w, b) tal que o valor da equao 4.7 seja mximo, sendo a margem,vetor w com a mesma dimenso de F, e b um nmero real.

= mini

yi{w, (Xi) b} (4.7)

A funo de deciso correspondente demonstrada na equao 4.8.

f(X) = sign(w, (X) b) (4.8)

O mnimo da funo f(X) ocorre quando a equao 4.9 satisfeita, sendo que i sonmeros reais positivos que maximizam a equao 4.10 e satisfazem a equao 4.11.

w =

i

iyi(Xi) (4.9)

i

i

ij

ij yiyj(Xi), (Xj) (4.10)

iyi = 0, i > 0 (4.11)

Desta forma, possvel representar a funo de deciso atravs da equao 4.12.

f(X) = sign(

i

iyi(Xi), (X) b) (4.12)

A partir da equao 4.12 observa-se que i, associado ao ponto de treinamento Xi, expressaa importncia daquele ponto no resultado final da funo de deciso.

importante observar que somente um sub-conjunto de pontos associado a i no-nulos.Tais pontos so denominados de vetores de suporte (support vectors, dando nome tcnica deSVM), e so os pontos mais prximos ao hiper-plano de separao.

Dessa forma, a tcnica possibilita a classificao de padres de acesso, separando-os deacordo com os vetores de suporte do hiper-plano determinados. A tcnica pode ser utilizadapara predio de padres numa seqncia longa, conforme demonstrado em [117].

4.3 Tcnicas baseadas em redes neurais

Redes neurais artificiais so sistemas computacionais baseados em ligaes, que visam simulara estrutura do crebro humano. Uma rede composta por um conjunto de elementos de pro-cessamento ("neurnios", "ns"ou "unidades"), interligados por meio de conexes com pesosassociados, que se comunicam atravs de troca de sinais [155]. O funcionamento da rede neural

relativamente simples, sendo que cada neurnio responsvel apenas por receber sinais deseus vizinhos ou fontes externas, determinar o sinal de sada em funo dos dados recebidos eo propagar para outras unidades de processamento, conforme ilustrado na figura 4.3 [155].

Geralmente, assume-se que cada unidade de processamento oferece uma contribuio adi-tiva para o neurnio qual ela conectada, calculada em funo do peso associado conexoentre eles. Dessa forma, o valor total de entrada sk de um neurnio k pode ser representado

23


27/100

Figura 4.3: Componentes de uma rede neural

como uma soma ponderada dos valores de sada yj dos neurnios j ajustada em funo dopeso wjk , associado conexo entre neurnio j e k, mais um valor inicial k(t) do neurnio k,conforme a equao 4.13.

sk(t) =

j

wjk (t)yj(t) + k(t) (4.13)

A contribuio de um neurnio, determinada pelo peso da conexo wj , pode ser negativa,utilizada para inibio de um neurnio, ou positiva, utilizada para a sua excitao.

Os pesos das conexes podem ser ajustados dinamicamente para indicar conexes maisrelevantes durante um processo de treinamento ou aprendizado. O treinamento de uma rede

neural pode ser feito de maneira supervisionada, ou associativa [39], quando a rede alimen-tada com valores pr-determinados de entrada e sada para possibilitar reconhecimento de umasrie de padres de entrada. Outro tipo de treinamento conhecido como treinamento no-supervisionado, ou auto-organizvel [155], na qual a rede se adapta dinamicamente ao seucontedo sem nenhum conhecimento prvio sobre os padres de entrada.

O aprendizado de rede feito de acordo com uma regra de aprendizado. Geralmente, omodelo de aprendizado Hebbiano [113] aplicado, no qual afirma-se que, caso duas unidadesde processamento j e k estiverem ativas simultaneamente, sua conexo deve ser reforada,ajustando o peso dessa conexo. O ajuste do peso pode ser feito de maneira direta, ajustando opeso da conexo de acordo com a equao 4.14, onde uma constante que representa a taxa

de aprendizado da rede (eq. 4.14):

wjk = yjyk (4.14)

Uma outra maneira de ajustar o peso de uma conexo consiste na tcnica de aproximao,que visa adaptar gradativamente a diferena entre o peso atual da conexo yk e o peso desejadodk, informado explicitamente, conforme a equao 4.15.

24


28/100

Figura 4.4: Funes de ativao de neurnios

wjk = yj(dk yk) (4.15)

Outras tcnicas de aprendizagem podem ser aplicadas, tais como as de aprendizado com-petitivo, utilizada pela rede neural SOM(seo 4.3.1), as de aprendizado baseado em memria,utilizada pela rede RSOM (seo 5.6.1), as de aprendizado de Boltzmann, utilizada pela redede Hopfield (seo 5.5.2) entre outras.

Em redes com mltiplas conexes entre os neurnios, cada elemento tem um valor de ati-vao yk(t), usado para determinar os neurnios mais adequados para a propagao do sinal

calculado pelo neurnio atual. A escolha do prximo neurnio yk(t + 1) feita por uma funode ativao Fk(t) com base no valor total de entrada sk(t) do neurnio k (eq. 4.16).

yk(t + 1) = Fk(tk(t), sk(t)) (4.16)

O valor de ativao yk do neurnio k controlado pelo valor de nvel (threshold) s e podeser calculado por diversas funes, tais como funo de corte (sgn) , semi-linear ou sigmide(equao 4.17), conforme a figura 4.4 [155].

yk = F(sk) =1

1 + esk(4.17)

Uma rede neural geralmente composta por uma srie de camadas de neurnios, conformea figura 4.5, com uma camada de entrada cujo objetivo receber dados de entrada, uma camadade sada e uma srie de camadas escondidas utilizadas para o processamento e propagao desinais.

De acordo com o padro de conexes entre as camadas, possvel classificar as redesneurais em redes feed-forward, onde os dados somente so propagados da camada de entradaat a camada de sada, e redes recorrentes, que possibilitam conexes de feedbackpara ajustardinamicamente a configurao da rede. Como exemplos de redes feed-forward possvel citarredes Adaline e Perceptron [155], e como exemplos de redes recorrentes pode-se citar redesSOM[143] e redes de Hopfield [120].

Atualmente existe uma grande variedade de redes neurais com vasta aplicao em diversas

reas computacionais. No caso de sistemas distribudos, possvel representar um ambientedistribudo como sendo composto por diversos neurnios, cada um representando um elementode processamento. Nesse caso, os parmetros dos neurnios representariam o poder de pro-cessamento, memria disponvel, latncia de acessos, etc. Dessa forma, a rede neural podeser utilizada para solucionar diversos problemas, tais como a distribuio de dados pelo ambi-

25


29/100

Figura 4.5: Topologia de rede neural

ente em funo de parmetros de recursos computacionais [170] ou antecipao de acessos aosdados [72].

A seguir, as principais redes neurais usadas para classificao de padres so apresentadas.

4.3.1 Mapas auto-organizveis SOM

Os mapas auto-organizveis (SOM Self-Organizing Maps) foram introduzidos por Kohonen[143] com o objetivo de resolver o problema de classificao de dados de entrada de acordocom o nvel de similaridades [133, 143]. SOMutiliza treinamento no-supervisionado, onde oneurnio que mais se adequa a um determinado padro de entrada utilizado para classificar

padres de entrada similares. Um exemplo de classificao feita por SOM apresentado nafigura 4.6 [166].Supondo que a figura 4.6 representa os processos executados em um ambiente distribudo,

pode-se ver que processos com caractersticas similares (por exemplo, uso do processador,memria e taxa de transmisso) so agrupados em clusters com caractersticas similares.

SOM representa os dados de entrada como pontos, ou ns, em um mapa. Aps o mapea-mento inicial de dados, o algoritmo SOM aplicado sobre um vetor de entrada de dimensesarbitrrias contendo todos os ns do mapa com o objetivo de agrupar vetores semelhantes, atra-vs do processo winner-take-all. Nesse processo, o neurnio com vetor de peso mais similar aovetor de entrada declarado vencedor e tem seu peso ajustado, visando torn-lo mais prximoao vetor de entrada. Alm disso, para cada neurnio no mapa determinada a sua vizinhana(conjunto de neurnios, cujo peso prximo ao do neurnio vencedor), ajustando os pesos dosneurnios encontrados proporcionalmente sua distncia do vencedor. O processo repetidodurante um nmero arbitrrio de ciclos.

O algoritmo pode ser descrito da seguinte maneira:

1. Inicializar a rede, representada como um mapa, conforme demonstrado na figura 4.6,

26


30/100

Figura 4.6: SOM: agrupamento de dados

com neurnios aleatrios;

2. Para cada vetor de entrada:

(a) Para cada neurnio presente no mapa:

i. Determinar a distncia Euclidiana DE entre o neurnio encontrado q e o vetorde entradap para calcular a sua semelhana por meio da equao 4.18, ondepxrepresenta o x-simo elemento do vetor de entrada e qy representa o y-simoelemento do neurnio atual;

DE =

(p1 q1)2 + (p2 q2)2 + ... + (pn qn)2 =

ni=1

(pi qi)2

(4.18)

ii. Salvar o neurnioj com peso wj que apresentou a menor distncia D do padrode entrada x, satisfazendo a equao 4.19, o qual denominado de BMU (BestMatching Unit).

D = argminx wj (4.19)

(b) Determinar os neurnios em vizinhana do BMU;

27


31/100

(c) Para cada neurnio k vizinho do BMU:

i. Atualizar os pesos do neurnio k, aproximando-os aos do BMU, conformeequao 4.20, onde t representa a iterao atual, W v representa o vetor depesos do neurnio k, (t) representa a distncia entre o neurnio k e o BMU,(t) representa a taxa de aprendizagem e D(t) a distncia entre o neurnio ke o BMU.

W v(t + 1) = W v(t) + (t)(t)(D(t) W v(t)) (4.20)

3. Repetir para todos os vetores restantes.

Considerando que para cada vetor de entrada determinado um neurnio-vencedor (BMU)diferente, o algoritmo possibilita agrupar padres em um nmero de clusters com caractersticassimilares.

A variao do parmetro (t) possibilita controlar a taxa de aprendizado do algoritmo SOM.Com valores altos, pode-se obter uma taxa de aprendizagem rpida, enquanto valores baixosresultam em treinamento mais refinado.

O SOM apresenta dois modos de operao:

1. Durante o processo de treinamento, construdo um mapa, organizando os vetores deentrada atravs do processo competitivo winner-take-all.

2. Durante o processo de classificao, ou clustering, os vetores de entrada so classificadosde acordo com o mapa criado no passo anterior.

Nesse caso, apenas o passo 2.a do algoritmo realizado, determinando o BMUpara cadaelemento de entrada. Aps isso, o vetor de entrada classificado no cluster correspon-dente ao neurnio BMUencontrado.

Redes SOM so aplicadas em diversas reas, onde evidente a necessidade de classifica-o e organizao de grande nmero de informaes. Como exemplos de aplicaes de redesSOM possvel citar organizaes de bases de dados [143], predio do uso de energia [159],classificao de dados de satlites [175] e processamento de imagens [7].

4.3.2 Redes neurais auto-expansveis

Enquanto redes neurais classificadoras, tais como SOM, permitem classificao automtica eno-supervisionada de dados, elas apresentam limitaes relacionadas necessidade de defini-o prvia de configurao, topologia, e parmetros de treinamento da rede.

Com o objetivo de permitir uma classificao mais adaptiva, diversas redes neurais auto-expansveis, ou seja, redes que possibilitam a criao de novos neurnios sob demanda, fo-

ram propostas, tais como Cascade-Correlation Learning Architecture (CCLA) [81, 213, 13],Growing Cell Structure (GCS) [156, 215], Probabilistic GCS [226, 34, 47], Growing NeuralGas (GNG) [156, 107, 91], Growing Self-Organizing Maps [5, 61], RCE [75, 236], CLAM[219]. Growing When Required (GWR) [167] e SONDE[6].

A maioria das redes neurais auto-expansveis so similares ao modelo de redes SOM. Aseguir, as principais caractersticas delas sero discutidas.

28


32/100

4.3.3 Cascade-Correlation Learning Architecture

A rede neural CCLA uma rede neural supervisionada, criada com o objetivo de otimizar odesempenho do processo de aprendizagem [81, 213, 13]. De maneira similar outras redesneurais classificadoras, a CCLA inicializada com uma estrutura mnima, sendo que novosneurnios so inseridos medida que for necessrio.

A principal diferena de CCLA em relao a outras redes classificadores consiste no fatodela empregar treinamento supervisionado, adicionando novos neurnios nas camadas escondi-das da rede somente quando necessrio. Novas unidades so inseridas na rede quando o erro de

classificao no reduzido durante iteraes consecutivas do processo de treinamento. Nestecaso, o seguinte algoritmo executado:

1. Um novo neurnio-candidato criado;

2. Os pesos do neurnio so treinados, visando maximizar a correlao entre a sada doneurnio e o erro residual de sada. Ao final do treinamento, este neurnio adicionado rede;

3. Ao ser includo na rede, os pesos do neurnio so congelados, no permitindo modifica-es futuras nos seus valores.

Dessa maneira, a rede CCLA visa uma criao rpida de rede classificatria, criando neur-nios adicionais dinamicamente.

4.3.4 Growing Cell Structure

A rede GCS (Growing Cell Structure), apresentada por Fritzke [91, 156, 215], foi uma dasprimeiras redes neurais auto-expansveis no supervisionadas. A rede baseada na SOM, sendocomposta por superfcies k-dimensionais, sendo que o valor de k geralmente definido comosendo k = 2. Com isso, as superfcies criadas so sempre triangulares.

Na rede GCS, um novo neurnio inserido a cada iteraes, sendo uma constante pr-

definida, de forma a suportar o neurnio que acumulou o maior nmero de erros durante asiteraes passadas. Esse processo continua at que um critrio de parada seja satisfeito, sejaele um tamanho pr-determinado da rede, ou um valor mnimo para o erro acumulado.

Diversas variaes da rede GCS foram propostas, visando otimizar seu funcionamento.Em [34], Burzevski e Mohan propuseram um novo mecanismo para tratar as mudanas daestrutura de rede que podem ocorrer devido remoo de neurnios uma vez que a rede composta por uma srie de superfcies k-dimensionais, a remoo de um neurnio podemodificar drasticamente a sua estrutura.

Uma das propriedades fundamentais da rede GCS o fato dela manter a mesma topologiadurante todo o processo de treinamento, aplicando uma diviso de neurnios existentes, criandonovas ligaes entre eles. Dessa forma, quando um elemento removido da rede, o neurnio

mais prximo a ele dividido em dois, visando manter a mesma topologia.De acordo com os autores, esse algoritmo oferece diversas vantagens em alguns casos,

resultando em uma classificao mais precisa e eficiente, a custo de aumento significativo denmero de neurnios na rede, resultando em uma topologia mais complexa da rede neural [34].

Uma extenso rede, conhecida como DCS (Dynamic Cell Structures), foi proposta porBruske e Sommer [3, 83]. Nessa extenso, os autores propem a insero de novos neurnios

29


33/100

na rede de uma forma a manter a topologia da rede, diferentemente da rede GCS original, quevisa somente equalizar os valores de erro esperados em cada neurnio.

Uma abordagem diferente proposta por Vlassis, conhecida como Probabilistic GCS [226,34, 47]. O modelo proposto visa tornar a rede GCS probabilstica, com o objetivo de melhoraro mecanismo de tratamento de entradas. Para isso, as entradas da rede so avaliadas por meiode tcnicas estocsticas, visando determinar co-relaes entre elas.

Finalmente, uma outra extenso para da rede GCS foi proposta por Cheng e Zell [47], alte-rando a estrutura bsica do algoritmo de GCS. No trabalho, a rede foi modificada, permitindocom que mais de um neurnio pudesse ser adicionado simultaneamente. Dessa forma, depen-dendo da topologia atual, dois ou mais neurnios podem ser adicionados rede simultanea-mente, dependendo da posio do neurnio-vencedor atual, resultando em uma convergnciamais rpida da rede, ao custo de criao de um nmero maior de neurnios.

Tanto a rede original GCS, quanto as suas extenses, so empregados em diversas reascomputacionais, porm a sua eficincia varia de acordo com os padres de entrada avaliados.

4.3.5 Growing Neural Gas

A rede neural Growing Neural Gas (GNG), tambm proposta por Fritzke [156, 107, 91], similar GCS. Na rede, os neurnios so adicionados a cada iteraes, de forma similar

rede GCS, visando suportar o neurnio com maior erro acumulado. Entretanto, diferentementede GCS, a estrutura topolgica da rede no mantida, sendo que as conexes so criadas entredois elementos que apresentaram a maior atividade:para cada padro de entrada.

Dessa forma, para cada entrada do sistema so selecionados dois neurnios-vencedores,cuja distncia Euclidiana do padro de entrada menor. Tais neurnios so conhecidos comovencedores, uma conexo entre eles criada e suas posies alteradas de forma com que osseus pesos sejam mais adequados ao valor de entrada. Alm disso, as posies dos neurnios-vizinhos dos vencedores tambm so ajustadas.

Visando manter somente as conexes entre os neurnios mais significativos, as conexesque no foram atualizadas por um determinado nmero de iteraes so removidas. Aps iteraes, o neurnio que acumulou a maior taxa de erros durante as execues passadas doalgoritmo determinado, e um novo elemento inserido na rede para diminuir a taxa de erros.O novo neurnio posicionado entre o que apresentou a maior taxa de erro e o seu vizinhocom a taxa de erros mais prxima. O algoritmo continua at atingir um critrio de paradapr-estabelecido.

Diversos trabalhos comparam o desempenho das redes GCS e GNG [156, 107, 91], con-cluindo que a eficincia dessas redes varia de acordo com o padro de entrada avaliado.

Visando melhorar o desempenho da rede GNG para padres de entrada no-estacionrios,uma modificao da rede foi proposta por Fritzke [92], denominada de GNGU (Growing NeuralGas with Utility). Essa abordagem introduz o conceito da utilidade dos neurnios, calculadapor maio da avaliao da possvel variao do erro global do sistema, caso tal neurnio for re-

movido. Portanto, para manter somente os dados mais relevantes, os neurnios que apresentambaixa utilidade so deletados, mantendo somente os mais adequados.

30


34/100

4.3.6 Growing Self-Organizing Maps

Uma outra abordagem apresentada por Bauer e Villmann [5, 61], introduzindo uma extensoda rede neural SOM conhecida como Growing Self-Organizing Map. O algoritmo de treina-mento baseado no algoritmo original de SOM, com a diferena de que a cada iteraesnovos neurnios so acrescentados na rede. No lugar de inserir somente um elemento porvez, supondo que as conexes entre os neurnios sero estabelecidas automaticamente duranteo treinamento, o algoritmo proposto adiciona uma srie de neurnios simultaneamente, man-tendo a topologia da rede.

O algoritmo visa manter a estrutura da rede inserindo um conjunto de neurnios de uma vez,de acordo com a topologia atual da rede. Ao adicionar novas entradas na rede, a vizinhanaentre os neurnios atuais mantida, considerando a correspondncia topolgica entre dados deentrada e a sua representao na rede.

4.3.7 Restricted Coulomb Energy

A rede neural Restricted Coulomb Energy (RCE) uma rede no-supervisionada, que classificapadres de entrada sem criar conexes entre os neurnios-vizinhos [75, 236]. A rede utilizasries de vetores-prottipos para classes particulares de entrada.

Caso nenhum dos vetores existentes, cada um dos quais representa um cluster, suficien-temente prximo ao valor de entrada avaliado, uma nova classe criada e inicializada com e ovalor de entrada atual. Com isso, no existem conexes entre os clusters, e os prottipos noso modificados aps serem criados. Uma abordagem similar empregada na famlia de redesneurais ART (Adaptive Resonance Theory), apresentada na seo 4.3.10.

4.3.8 Contextual Layered Associative Memory

Uma abordagem diferente proposta por Thacker e Mayhew [37, 220, 219], introduzindo arede neural CLAM (Contextual Layered Associative memory). A rede composta por umasrie de camadas interconectadas com um mecanismo de ressonncia dentro de cada, utilizado

para detectar similaridades entre os padres de entrada.Diferentemente de outras redes, que utilizam a abordagem winner-takes-all para escolherum nico vencedor, CLAM classifica os padres entre diversos grupos de neurnios, efetiva-mente cobrindo o espao amostral dos padres de entrada. Neurnios adicionais so acres-centados na rede quando a mesma detecta que uma regio de entrada apresenta uma baixadensidade de neurnios.

4.3.9 Growing When Required

A rede neural Growing When Required (GWR), proposta por Marsland et al. [167], umarede auto-organizvel e auto-expansvel, criada com o objetivo de suprir as deficincias das

redes auto-expansveis existentes, sendo amplamente utilizada para classificao de padres edeteco de novidades.

A rede composta por neurnios interconectados com vetores de pesos conectados comos seus vizinhos, sendo que os padres de entrada similares so representados por meio deagrupamentos de neurnios. Tanto os ns da rede quanto as conexes so criados e destrudosdurante o processo de aprendizagem dinamicamente.

31


35/100

Diferentemente de GNG e GCS, onde novos neurnios so inseridos na rede a cada iteraes, GWR permite a criao de novos neurnios a qualquer momento. A rede utilizaaprendizado Hebbiano competitivo, e para cada padro de entrada uma conexo entre os doisneurnios-vencedores criado. cada conexo associado um parmetro representando a suaidade, inicializado com zero, sendo que as idades das conexes estabelecidas so incrementa-das a cada iterao, e as cuja idade excede a constante max so removidas. Da mesma forma,os neurnios sem nenhuma conexo tambm so removidos, por serem considerados mortos.

Diferentemente de GNG, onde novos neurnios so inseridos de forma a suportar neurnioscom maior taxa de erro acumulada, na rede GWR eles so criados de acordo com a topologia darede. Para adicionar um neurnio, a atividade dos neurnio presentes no sistema calculada,sendo representada pela distncia Euclidiana entre o vetor de pesos de neurnio e atual padrode entrada. Neurnios com menor distncia so escolhidos como vencedores.

Levando em considerao o fato de que neurnios recm-criados podem no ser treinadoso suficientemente para realizar uma classificao adequada, a rede introduz um mecanismopara avaliar quantas vezes cada neurnio foi disparado. Geralmente, um contador simples utilizado para calcular tal valor, sendo incrementado cada vez que o neurnio for consideradoum vencedor.

Uma outra abordagem consiste na utilizao de uma varivel que decresce exponencial-mente de 1 a 0, sendo que os neurnios recm-criados so inicializados com 1 e os neurnios

disparados frequentemente tendem a ter seus valores prximos a 0. Essa abordagem equi-valente anterior, porm possibilita a modificao das variveis dos neurnios-vizinhos dovencedor, levando em considerao a distncia entre eles. Alm disso, o nmero de vezes queum neurnio foi disparado tambm pode ser levado em considerao durante o processo deaprendizagem, de uma forma que os disparados com maior freqncia so treinados menos doque os que raramente ativados. Com isso, possvel otimizar a convergncia da rede, evitandosuper-utilizao de alguns neurnios a custo de outros, o que pode levar a uma classificaoimprecisa.

Dessa forma, quando um novo padro de entrada processado pela rede, a atividade detodos os neurnios calculada, escolhendo um vencedor. Se o valor que representa a suaatividade prximo a 1, a rede considera que ele representa o padro de entrada de formaadequada. Caso contrrio, se a atividade da rede inferior ao valor mnimo estabelecido,determinado por T, isso pode significar que o neurnio foi inserido na rede recentemente ouque nenhum elemento da rede representa o padro de entrada adequadamente.

Se o neurnio foi criado recentemente, ele treinado. Caso contrrio, um novo neurnio criado entre o vencedor e o padro de entrada considerado, tendo seus pesos inicializados comvalores mdios dos pesos do neurnio-vencedor e o atual padro de entrada.

Com isso, o comportamento da rede pode ser configurado por meio do parmetro T, sendoque quando T prximo a 1, a fase de treinamento cria um nmero maior de neurnios,resultando em classificao mais detalhada. Por outro lado, quando o valor de T baixo, arede resulta em uma classificao mais generalizada.

O algoritmo da rede GWR descrito a seguir:

1. Considerando A o conjunto de neurnios presentes na rede, C AxA o conjunto dasconexes entre eles, n o vetor de pesos do neurnio n e os valores de entrada, cujoespao amostral representado por (), a rede inicializada com dois neurnios n1 en2, escolhidos aleatoriamente de ();

32


36/100

2. Para cada iterao do algoritmo:

(a) Escolher um padro de entrada ;

(b) Para cada neurnio i da rede, calcular a distncia Euclidiana dele para o padro deentrada atual || i||;

(c) Selecionar os dois neurnios-vencedores, representados por s, t A, de acordocom as equaes 4.21 e 4.22, onde n o vetor de pesos do neurnio n;

s = arg minnA|| n|| (4.21)

t = arg minnA/{s}|| n|| (4.22)

(d) Caso no exista conexo entre s e t, a conexo criada entre eles, tendo a sua idadeinicializada com 0. Caso contrrio, a idade da conexo zerada;

(e) A atividade do neurnio-vencedor calculada atravs da equao 4.23;

= exp(|| s||) (4.23)

(f) Caso o valor da atividade seja inferior ao valor de corte T, e o contador dedisparos do neurnio seja inferior ao valor de corte hT, um novo neurnio r in-serido entre os dois neurnios-vencedores (s e t), tendo o seu vetor de pesos rinicializado de acordo com a equao 4.24.

r = (s + )/2 (4.24)

Aps isso, conexes entre r e s so criadas, e conexo entre s e t removida darede;

(g) Caso a criao de um novo neurnio no for necessria, as posies do neurnio-

vencedor e dos seus vizinhos

Documents

Estudo sobre abordagens de extração, classificação e predição de comportamento de processos