Grande parte do sucesso do Google provêm do algoritmo Page Rank, que avalia quantitativamente a importância de cada página na web. Esta ordenação é obtida através do vetor estacionário de uma matriz estocástica específica, utilizando o Método das Potências. A velocidade de convergência deste método será avaliada em detalhe, já que se trata de uma resposta imediata da pesquisa do usuário. Afim de entender as diferentes situações que o modelo pode enfrentar, diversas simulações são apresentadas neste trabalho. Em particular, estamos interessados nos fatores que influenciam a velocidade de convergência. Para tanto, o número de páginas total e de cada conjunto fechado, bem como o número de conjuntos fechados e de nós pendentes foram estudados. / Great part of Google\'s success comes from the Page Rank algorithm, wich quantitatively evaluates the importance of each page on the web. This sort is achieved through a specific stochastic matrix stationary vector, using the Power Method. The convergency speed of this method will be evaluated in details, since this is a imediate response for the user search. In order to understand the diferent situations the model can confront, several simulations are shown in this work. In particular, we are interested in the factors which influences the convergency speed. For that, the total and inside each closed set number of pages and also the closed sets and dangling nodes numbers were studied.

Grande parte do sucesso do Google provêm do algoritmo Page Rank, que avalia quantitativamente a importância de cada página na web. Esta ordenação é obtida através do vetor estacionário de uma matriz estocástica específica, utilizando o Método das Potências. A velocidade de convergência deste método será avaliada em detalhe, já que se trata de uma resposta imediata da pesquisa do usuário. Afim de entender as diferentes situações que o modelo pode enfrentar, diversas simulações são apresentadas neste trabalho. Em particular, estamos interessados nos fatores que influenciam a velocidade de convergência. Para tanto, o número de páginas total e de cada conjunto fechado, bem como o número de conjuntos fechados e de nós pendentes foram estudados. / Great part of Google\'s success comes from the Page Rank algorithm, wich quantitatively evaluates the importance of each page on the web. This sort is achieved through a specific stochastic matrix stationary vector, using the Power Method. The convergency speed of this method will be evaluated in details, since this is a imediate response for the user search. In order to understand the diferent situations the model can confront, several simulations are shown in this work. In particular, we are interested in the factors which influences the convergency speed. For that, the total and inside each closed set number of pages and also the closed sets and dangling nodes numbers were studied.

Made available in DSpace on 2016-08-17T16:54:33Z (GMT). No. of bitstreams: 1 Tese Cristiane Cristina.pdf: 4404224 bytes, checksum: a68e5757bedc2d3d341a5937f100fe1f (MD5) Previous issue date: 2013-07-19 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / In adaptive filtering many adaptive filter are based on the mean square error method (MSE). These filters were developed to improve convergence spedd with a lower misadjustment. The least mean square (LMS) and the recursive least square (RLS) algorithms have been the hallmark of adaptive filtering. In this work we develop adaptive algorithms based on the even powers of the error inspired in the recursive lest square (RLS) algorithm. Namely recursive nom quadratic (RNQ) algorithm. The ideas is based on Widrow s least mean square fourth (LMF) algorithm. Fisrt we derive equations based on a singal even power of the error in order to obtain criterions that guarantee convergence. We also determine equations that measure the misadjustment and the time constant of the adaptive process of the RNQ algorithm. We work also, toward making the algorithm less sensitive to the size of the error in na alternative direction, by proposing a cost function which is a sum of the even powers of the error. This second approach bring the error explicitly to the RLS algorithm formulation by proposing a new cost function that preserves the measnsquare-error (MSE) solution, but allows for the exploitation of higher order moments of the error to speedup the converge of the algorithm. The main goal this work is to create form first principles (new cost functions ) a mechanism to include instantaneous error information in the RLS algorithm, make it track better, and allow for the design of the forgetting factor. As we will see the key aspecto of our approach is to include the error in the Kalman gain that effectively controls the speed of adaptation of the RLS algorithm. / Em filtragem adaptativa, vários filtros são baseados no método do erro quadrático médio (do inglês, MSE- mean squared error ) e muitos desses foram desenvolvidos para obter uma convergência rápida com um menos desajuste. Os algoritmos mínimos quadrático médio (do inglês, LMS- least mean square ) e mínimos quadrados recursivos (do inglês, RLS- recursive least square ) foram um marco em filtragem adaptativa. Nesse trabalho apresentamos o desenvolvimento de uma família de algoritmos adaptativos baseados nas potências pares do erro, inspirado na dedução do algoritmo RLS padrão. Chamaremos esses novos algoritmos de recursivo não-quadrático (RNQ). A ideia básica é baseada na função de custo apresentada por Widrow no algoritmo mínimo quarto médio ( do inglês, LMF least mean square fourth). Inicialmente derivamos equações baseados em uma potência par do erro para obter critérios que garantam a convergência. Determinamos também, equações que definem o desajuste e o tempo de aprendizagem do processo de adaptação do algoritmo RNQ baseado em potência para arbitrária. Trabalhamos também, no sentido de tornar o algoritmo menos sensível ao tamanho do erro numa direção alternativa, propondo uma função de custo baseado na soma das potências pares do erro. Essa segunda abordagem torna explícito o papel do erro na formulação do RLS ao propor uma nova função de custo que preserve a solução MSE, mas permite a utilização dos momentos de alta ordem do erro para aumentar a velocidade de convergência do algoritmo. O principal objetivo do nosso trabalho é criar a partir dos primeiros princípios (novas funções de custo) um mecanismo para incluir informações de erro instantâneo no algoritmo RLS e torná-lo um seguidor melhor. Assim, o aspecto-chave dessa nova abordagem é incluir o erro no ganho de Kalman que controla efetivamente a velocidade de adaptação do algoritmo de RLS.

Nesta tese apresentamos alguns resultados teóricos e práticos da modelagem de seqüências simbólicas com cadeias estocásticas parcimoniosas. As cadeias estocásticas parcimoniosas, que incluem as cadeias estocásticas de memória variável, constituem uma generalização das cadeias de Markov de alcance fixo. As seqüências simbólicas às quais foram aplicadas as ferramentas desenvolvidas são as cadeias de aminoácidos. Primeiramente, introduzimos um novo algoritmo, chamado de SPST, para selecionar o modelo de cadeia estocástica parcimoniosa mais ajustado a uma amostra de seqüências. Em seguida, utilizamos esse algoritmo para estudar dois importantes problemas da genômica; a saber, a classificação de proteínas em famílias e o estudo da evolução das seqüências biológicas. Finalmente, estudamos a velocidade de convergência de algoritmos relacionados com a estimação de uma subclasse das cadeias estocásticas parcimoniosas, as cadeias estocásticas de memória variável. Assim, generalizamos um resultado prévio de velocidade exponencial de convergência para o algoritmo PST, no caso de cadeias de memória ilimitada. Além disso, obtemos um resultado de velocidade de convergência para uma versão generalizada do Critério da Informação Bayesiana (BIC), também conhecido como Critério de Schwarz. / In this thesis we present some theoretical and practical results, concerning symbolic sequence modeling with parsimonious stochastic chains. Parsimonious stochastic chains, which include variable memory stochastic chains, constitute a generalization of fixed order Markov chains. The symbolic sequences modeled with parsimonious stochastic chains were the sequences of amino acids. First, we introduce a new algorithm, called SPST, to select the model of parsimonious stochastic chain that fits better to a sample of sequences. Then, we use the SPST algorithm to study two important problems of genomics. These problems are the classification of proteins into families and the study of the evolution of biological sequences. Finally, we find upper bounds for the rate of convergence of some algorithms related with the estimation of a subclass of parsimonious stochastic chains; namely, the variable memory stochastic chains. In consequence, we generalize a previous result about the exponential rate of convergence of the PST algorithm, in the case of unbounded variable memory stochastic chains. On the other hand, we prove a result about the rate of convergence of a generalized version of the Bayesian Information Criterion (BIC), also known as Schwarz\' Criterion.

Nesta tese apresentamos alguns resultados teóricos e práticos da modelagem de seqüências simbólicas com cadeias estocásticas parcimoniosas. As cadeias estocásticas parcimoniosas, que incluem as cadeias estocásticas de memória variável, constituem uma generalização das cadeias de Markov de alcance fixo. As seqüências simbólicas às quais foram aplicadas as ferramentas desenvolvidas são as cadeias de aminoácidos. Primeiramente, introduzimos um novo algoritmo, chamado de SPST, para selecionar o modelo de cadeia estocástica parcimoniosa mais ajustado a uma amostra de seqüências. Em seguida, utilizamos esse algoritmo para estudar dois importantes problemas da genômica; a saber, a classificação de proteínas em famílias e o estudo da evolução das seqüências biológicas. Finalmente, estudamos a velocidade de convergência de algoritmos relacionados com a estimação de uma subclasse das cadeias estocásticas parcimoniosas, as cadeias estocásticas de memória variável. Assim, generalizamos um resultado prévio de velocidade exponencial de convergência para o algoritmo PST, no caso de cadeias de memória ilimitada. Além disso, obtemos um resultado de velocidade de convergência para uma versão generalizada do Critério da Informação Bayesiana (BIC), também conhecido como Critério de Schwarz. / In this thesis we present some theoretical and practical results, concerning symbolic sequence modeling with parsimonious stochastic chains. Parsimonious stochastic chains, which include variable memory stochastic chains, constitute a generalization of fixed order Markov chains. The symbolic sequences modeled with parsimonious stochastic chains were the sequences of amino acids. First, we introduce a new algorithm, called SPST, to select the model of parsimonious stochastic chain that fits better to a sample of sequences. Then, we use the SPST algorithm to study two important problems of genomics. These problems are the classification of proteins into families and the study of the evolution of biological sequences. Finally, we find upper bounds for the rate of convergence of some algorithms related with the estimation of a subclass of parsimonious stochastic chains; namely, the variable memory stochastic chains. In consequence, we generalize a previous result about the exponential rate of convergence of the PST algorithm, in the case of unbounded variable memory stochastic chains. On the other hand, we prove a result about the rate of convergence of a generalized version of the Bayesian Information Criterion (BIC), also known as Schwarz\' Criterion.

Submitted by Rosivalda Pereira (mrs.pereira@ufma.br) on 2017-06-23T21:14:46Z No. of bitstreams: 1 JonathanQueiroz.pdf: 631286 bytes, checksum: 2cab2a7d6e496bf574ddef1f49a77440 (MD5) / Made available in DSpace on 2017-06-23T21:14:46Z (GMT). No. of bitstreams: 1 JonathanQueiroz.pdf: 631286 bytes, checksum: 2cab2a7d6e496bf574ddef1f49a77440 (MD5) Previous issue date: 2016-03-08 / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPQ) / The discrete Riccati algebraic equation has played an increasingly important role in optimal control theory and adaptive ltering. For this reason, various techniques have been developed to solve the DARE, for example the approach based on self vectors or approaches related to invariant subspaces [1], which require mathematical rigor and precision. However, these approaches present a number of problems, among them the fact that they can not be implemented in real-time due to its high computational cost to estimate the solution of DARE in many systems, especially systems with higher order three. In order to overcomes this problem, we propose to solve the DARE using as an estimator based on the sum of potential error pairs. The estimator is similar to the Recursive Least Squares (RLS), but with a better performance in terms of convergence speed and estimation accuracy without a signi- cant increase in computational complexity. The estimator is called Recursive Least Non-Squares (RLNS). One other aspect in unraveling the general DARE is to ensure that DARE is numerically well conditioned. To perform the numerical conditioning of DARE, a matrix decomposition technique known as Moore-Penrose inverse or generalized inverse is used. The proposed method is evaluated in a multivariate system 6th order corresponding to the wind generator. The method is evaluated under the numerical stability point of view and speed of convergence. / A equação algébrica Riccati discreta (discrete algebraic Riccati equation (DARE)) tem desempenhado uma papel cada vez mais importante na teoria de controle ótimo. Por esse motivo, varias técnicas tem sido desenvolvidas para solucionar a DARE, por exemplo a abordagem baseada em auto vetores ou ainda abordagens relacionadas a subespaços invariantes, as quais requerem rigor e precisão matemáticas. No entanto, estas abordagens apresentam uma serie de problemas, dentre eles, o fato de não poderem ser implementadas em tempo real devido ao seu alto custo computacional para estimar a solução da DARE em diversos sistemas, sobretudo sistemas com ordem superior a três. Com o intuito de contorna este problema, propomos solucionar a DARE utilizando um estimador baseado na soma das potencias pares do erro. O estimador e similar ao Recursive least squares (RLS), mas com um desempenho melhor em termos de velocidade de convergência e precisão de estimativa, sem aumento significativo da complexidade computacional. O estimador é denominado Recursive Least Non-Squares (RLNS). Um outra aspecto para que possamos solucionar a DARE de forma geral, e garantir que a DARE seja numericamente bem condicionada. Para efetuar o condicionamento numérico da DARE, será utilizada uma técnica de decomposição matricial conhecida como inversa de Moore-Penrose ou inversa generalizada. A metodologia proposta e avaliada em um sistema multivariavel de 6th ordem correspondente ao gerador eólico.