Exportar este item: EndNote BibTex

Use este identificador para citar ou linkar para este item: http://tede.mackenzie.br/jspui/handle/tede/4270
Tipo do documento: Tese
Título: Classificação automática do comportamento dinâmico automato celulares binários unidimensionais
Autor: Nogueira, Marcelo Arbori 
Primeiro orientador: Oliveira, Pedro Paulo Balbi de
Primeiro membro da banca: Ruivo, Eurico Luiz Prospero
Segundo membro da banca: Costa , Pedro Contino da Silva
Terceiro membro da banca: Schimit, Pedro Henrique Triguis
Quarto membro da banca: Bahamon, Dario
Resumo: A variabilidade de evoluções temporais geradas por autômatos celulares advém do grande número de regras possíveis, a sua configuração inicial, quantidade de estados, quantidade de células na vizinhança e dimensão do reticulado. Mesmo para os mais simples, o número de regras do autômato celular pode facilmente ser da ordem de bilhões, e ainda que o reticulado seja unidimensional, a quantidade de evoluções temporais possíveis cresce exponencialmente com relação ao tamanho do reticulado. Portanto, classificar a dinâmica típica das evoluções temporais e trabalho de difícil realização, sendo útil qualquer processo automatizado para a tarefa. Relata-se aqui o desenvolvimento de dois classificadores da dinâmica apresentada pelas evoluções temporais, segundo o esquema de classificação nas 4 classes de Wolfram, tendo como base o espaço elementar, mas tendo também por objetivo aplicá-lo em um espaço maior, cuja classificação e desconhecida, qual seja, aquele com 4 células na vizinhança e 2 estados possíveis. Inicialmente foi feita uma revisão da classificação das regras do espaço elementar desenvolvida por Wuensche (1998), no qual, a cada itera c~ao do autômato celular, a varia c~ao da entropia de evoluções temporais foi associada as classes das regras geradoras. Os resultados obtidos serviram como referência para os dois classificadores desenvolvidos posteriormente. Dos dois classificadores, um usou rede neural convolucional, treinada para predizer a classe da regra associada a uma evolução temporal. Como as 4 classes não possuem a mesma quantidade de regras, o que afeta o treinamento da rede, as regras foram escolhidas aleatoriamente, mas mantendo a mesma proporção para cada classe. O segundo classificador usou análise de textura para extrair, das evoluções temporais, informação quanto as configurações de vizinhanças das células, de forma a se poder construir um espectro de frequência destas configurações. Um único espectro, com a frequência média de cada configuração possível, associado a regra geradora, foi incluído em um conjunto de dados para ser utilizado no algoritmo k-NN, a m de se obter a predição da classe em questão. Os classificadores foram avaliados de duas formas: a princípio, para inferir as classes das regras do espaço elementar, tomando por base os comportamentos t picos delas, aqueles mais comumente apresentados em um conjunto de evoluções temporais. As classes preditas puderam ser comparadas com a classificação conhecida do espaço elementar e se observou acurácia total para ambos. J a para o espaço com 4 células na vizinhança, foi realizada uma classificação visual de todo o espaço. Neste caso, nenhum dos classificadores conseguiu acurácia elevada. Ainda assim, ambos foram capazes de extrair informações do espaço muito maior que o elementar. Por fim, foram usadas matrizes de confusão para avaliar a qualidade dos classificadores com dados dos dois espaços, com ambos os classificadores apresentando dificuldades na classificação do espaço com 4 células na vizinhança
Abstract: The variability of temporal evolution generated by cellular automata comes from the large number of possible rules, their initial con guration, the number of states, the number of cells in the neighborhood and the dimension of the lattice. Even for the simplest cases, the number of rules in the space can easily reach billions, and even if the lattice is one-dimensional, the number of possible temporal evolutions grows exponentially as the lattice size grows. Therefore, to classify the typical dynamics of the temporal evolutions is a dauting endeavour, so that any automated process for the task is clearly useful. We report here the development of two classi ers of the dynamics presented by the temporal evolutions, according to Wolfram's 4-class classi cation scheme, based on the elementary space, but also aiming to apply it to a larger space, whose classi cation is unknown, namely, the one with 4 cells in the neighbourhood and 2 possible states. At rst, a review was made of the classi cation method developed byWuensche (1998), in which, at each time step of the cellular automaton, the entropy variation observed in the temporal evolution was associated with the generating rule classes. The results obtained served as a reference for the classi ers developed further on. One of the two classi ers relied on a convolutional neural network, trained to predict the rule class that generated a temporal evolution. Since the 4 classes do not have the same amount of rules, which a ects the network training, the rules were chosen randomly, while keeping the same proportion for each class. The second classi er used texture analysis to extract, from the temporal evolutions, information of the neighborhood con gurations of the cells, which allowed for the construction of a frequency spectrum of these con gurations. A single spectrum, with the average frequency of each possible con guration associated with the generating rule was then included in a dataset, and used in the k-NN algorithm to obtain the prediction of the class at issue. The classi ers were evaluated in two ways: at rst, to de ne the classes of the elementary space, according to their typical behaviors, which are the most common ones displayed in a set of temporal evolutions. The predicted classes could be compared with the known classi cation of elementary space and total accuracy was observed for both. For the space with 4 cells in the neighbourhood, a visual classi cation of the entire space was performed. In this case, none of the classi ers achieved high accuracy. Still, they were able to extract information from that space, which is larger than the elementary space. Finally, confusion matrices were used to evaluate the quality of the classi ers with data from both spaces, with both classi ers having di culties in classifying the space with 4 cells in the vicinity.
Palavras-chave: autômato celular
rede neural convolucional
classificação de comportamento dinâmico
classes de Wolfram
espectro de con guração de vizinhança
aprendizado profundo
Área(s) do CNPq: CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA
Idioma: por
País: Brasil
Instituição: Universidade Presbiteriana Mackenzie
Sigla da instituição: UPM
Departamento: Escola de Engenharia Mackenzie (EE)
Programa: Engenharia Elétrica
Agencia(s) de fomento: Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
Instituto Presbiteriano Mackenzie
Citação: NOGUEIRA, Marcelo Arbori. Classificação automática do comportamento dinâmico automato celulares binários unidimensionais. 2019. 89 f. Tese (doutorado em Engenharia Elétrica e Computação) - Universidade Presbiteriana Mackenzie, São Paulo, 2019.
Tipo de acesso: Acesso Aberto
URI: http://tede.mackenzie.br/jspui/handle/tede/4270
Data de defesa: 2-Out-2019
Aparece nas coleções:Doutorado - Engenharia Elétrica e Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
MARCELO ARBORI NOGUEIRA.pdfMarcelo Arbori Nogueira1.26 MBAdobe PDFBaixar/Abrir Pré-Visualizar


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.