Submitted by Caroline Xavier (caroline.xavier@pucrs.br) on 2017-03-20T14:37:41Z No. of bitstreams: 1 TES_JOAQUIM_VINICIUS_CARVALHO_ASSUNCAO_COMPLETO.pdf: 5447781 bytes, checksum: f414b8262d7361d1082fc73dfea5f008 (MD5) / Made available in DSpace on 2017-03-20T14:37:41Z (GMT). No. of bitstreams: 1 TES_JOAQUIM_VINICIUS_CARVALHO_ASSUNCAO_COMPLETO.pdf: 5447781 bytes, checksum: f414b8262d7361d1082fc73dfea5f008 (MD5) Previous issue date: 2016-08-09 / Modelos estoc?sticos podem ser ?teis para representar de maneira compacta cen?rios n?o determin?sticos. Al?m disso, simula??es aplicadas em um modelo compacto s?o mais r?pidas e demandam menos recursos computacionais do que t?cnicas de minera??o em grandes volumes de dados. O desafio est? na constru??o desses modelos. A acur?cia, juntamente com tempo e a quantidade de recursos usados para ajustar um modelo s?o fatores chave para sua utilidade. Tratamos aqui de t?cnicas de aprendizado de m?quina para ajustes de estruturas com a propriedade de Markov; especialmente formalismos complexos como Modelos Ocultos de Markov (HMM) e Redes de Automatos Estoc?sticos (SAN). Quanto a acur?cia, levamos em considera??o as atuais t?cnicas de ajuste, e medidas baseadas em verossimilhan?a. Quanto ao tempo de cria??o, automatizamos o processo de mapeamento de dados via s?ries temporais e t?cnicas de representa??o. Quanto aos recursos computacionais, usamos s?ries temporais e t?cnicas de redu??o de dimensionalidade, evitando assim, problemas com a explos?o do espa?o de estados. Tais t?cnicas s?o demonstradas em um processo que incorpora uma s?rie de passos comuns para o ajuste de modelos com s?ries temporais. Algo semelhante ao que o processo de descoberta de conhecimento em banco de dados (KDD) faz; por?m, tendo como componente principal, modelos estoc?sticos. / Stochastic models might be useful for creating compact representations of non-deterministic scenarios. Furthermore, simulations applied to a compact model, are faster and require fewer computational resources than the use of data mining techniques over large volumes of data. The challenge is to build such models. The accuracy as well as the time and the amount of resources used to fit such models, are the key factors related to their utility. We use machine learning techniques for the fitting of structures characterized by a Markov property; especially, complex formalisms such as Hidden Markov Models (HMM) and Stochastic Automata Networks (SAN). Regarding the accuracy, we considered the state of the art on fitting techniques and model measurements based on likelihood. Regarding the computational resources, we used time series and dimensionality reduction techniques to avoid the space state explosion. Such techniques are demonstrated in a process that embodies a set of common steps for the model fitting through time series. Similar to the knowledge discovery in databases (KDD), yet using stochastic models as a main component.

Made available in DSpace on 2015-04-14T14:49:22Z (GMT). No. of bitstreams: 1 423499.pdf: 2268638 bytes, checksum: a9a287a49644290eaf88a8b8d38f9f10 (MD5) Previous issue date: 2010-03-29 / Os formalismos estruturados foram definidos ao longo dos anos com o objetivo de aumentar o n?vel de abstra??o e oferecer uma alternativa de modelagem mais sofisticada do que a proporcionada pelas tradicionais Cadeias de Markov. Exemplos de formalismos estruturados que utilizam ?lgebra tensorial para o armazenamento de seus descritores s?o as Redes de Aut?matos Estoc?sticos, as Redes de Petri Estoc?sticas Generalizadas Superpostas e as ?lgebras de Processo. Tais descri??es utilizam primitivas de modelagem entre seus componentes capturando sua sem?ntica operacional e permitindo a sua an?lise ao retornarem ?ndices quantitativos de desempenho quando s?o resolvidos numericamente. Os mecanismos atuais de solu??o usam propriedades da ?lgebra Tensorial (cl?ssica ou generalizada) para multiplicar termos tensoriais de eventos entre os estados dos modelos (i.e., um descritor Markoviano) por um vetor de probabilidade, que cont?m a solu??o estacion?ria ou transiente. Esta opera??o ? chamada de Multiplica??o Vetor-Descritor (MVD) e ? realizada de tr?s maneiras b?sicas: de forma esparsa (ineficiente em mem?ria, eficiente em tempo), utilizando o Algoritmo Shuffle (eficiente em mem?ria, ineficiente em tempo para algumas classes de modelos) ou atrav?s do Algoritmo Split, que ? uma combina??o das duas primeiras abordagens. A principal contribui??o deste ?ltimo foi a proposi??o de um m?todo h?brido onde incrementa-se a mem?ria (de forma razo?vel) para acelerar o c?lculo efetuado por itera??o. Entretanto, o principal desafio do Algoritmo Split ? relativo ? determina??o de cortes de cada termo tensorial e em como re-estrutur?-lo para reduzir o custo computacional por itera??o, acelerando a converg?ncia de modelos estruturados. Este trabalho aborda estes problemas, baseando-se em tr?s eixos: i) na discuss?o das primitivas de modelagem para composi??o de sistemas atrav?s de formas mais abstratas de descri??o, ii) nas diferentes formas de tratamento de termos tensoriais de descritores Markovianos para execu??o mais otimizada da MVD a partir de re-estrutura??es das ordens originais, e iii) na execu??o do Algoritmo Split com taxas constantes ou funcionais demonstrando os resultados obtidos para diversas classes de modelos. Para os casos observados, foi demonstrado atrav?s de experimentos que o melhor ganho, balanceando-se tempo e mem?ria, ? verificado quando as matrizes dos termos tensoriais s?o reordenadas, tratando as do tipo identidade na parte estruturada e avaliando-se os elementos funcionais uma ?nica vez na parte esparsa. Ao avaliar as fun??es somente uma vez em todo o processo de MVD, converte-se os descritores generalizados para cl?ssicos em tempo de execu??o e promove-se ganhos consider?veis em tempo para determinadas classes de modelos. Observou-se tamb?m que as atividades de sincroniza??o ou comunica??o entre os m?dulos ou parti??es envolvidas bem como o total de par?metros das depend?ncias funcionais realizam um papel crucial no desempenho obtido. A presente tese ? finalizada identificando as classes de modelos mais adequadas para a utiliza??o do Algoritmo Split, propondo formas de re-estrutura??o de descritores Markovianos que privilegiem a esparsidade e a exist?ncia de matrizes do tipo identidade para balancear os custos em mem?ria e tempo de execu??o.