Algoritmos de aproximação estocástica com valor do passo adaptativo

Abstract

Consideram-se os algoritmos iterativos de aproximação estocástica (AE) do zero de uma função dada quando o valor da função é perturbado aleatoriamente. A teoria da AE está bem desenvolvida para o caso em que o valor do passo do algoritmo é determinístico, dependendo apenas do número da iteração do algoritmo; em particular, foram elaborados algoritmos assimptoticamente optimais. No entanto, em muitos problemas práticos abordados de forma heurística (em particular redes neuronais), verifica-se que são mais efectivos, num periodo transitório, os algoritmos cujo valor do passo é aleatório, sendo determinado através dos parâmetros correntes do algoritmo. A tese concentra-se nos algoritmos onde o valor do passo aumenta caso os incrementos de aproximações consecutivas mantenham o sentido (indicando que o algoritmo está na "zona determinística"), e diminui no caso contrário (estando o algoritmo na "zona estocástica"). No algoritmo de Kesten, o passo mantém-se caso hajam dois incrementos com o mesmo sinal, e em caso oposto, o passo é decrementado. Na tese, o algoritmo é generalizado podendo o passo aumentar caso duas iterações ocorram no mesmo sentido. É demonstrada a convergência para o zero com probabilidade 1 para o caso de funções unidimensionais e multidimensionais com um único zero. É também demonstrada a normalidade assimptótica das estimativas. Podem encontrar-se na literatura, algoritmos heurísticos de variação multiplicativa do passo para redes neuronais. Na tese, e para o caso de funções unidimensionais com vários zeros, é demonstrado com probabilidade 1 que estes algoritmos podem divergir ou convergir para uma vizinhança de um dos zeros. A adaptação do passo depende de dois parâmetros que determinam a precisão da vizinhança. Além desta regulação foi observado em simulações que para uma maior precisão é necessário um aumento do número de iterações. São apresentados inúmeros exemplos numéricos que ilustram a vantagem dos novos algoritmos para o caso unidimensional. Para o caso multidimensional os algoritmos propostos não se mostraram efectivos.

We consider iterative algorithms of Stochastic Approximation (SA) of the zero of a function when the value of the function is randomly perturbated. SA theory is well established when the step-value is deterministic, depending only on the iteration number. In particular, asymptotical optimal algorithms were developed. However, in many practical problems, the use of random step-value becomes more efective in a transitory stage, being determined by current iterations measures. This thesis concentrate on algorithms where step can increase if consecutive increments have the same sign (called `deterministic zone') and decrease otherwise (called `stochastic zone'). Algorithms of this kind were treated heuristically in several publications (particularly in neural networks literature). In Kesten's algorithm, step is kept if two consecutive iterations have the same direction, and decreases otherwise. The thesis makes a generalization allowing the step to increase if successive increments have same sign and decrease otherwise. Almost sure convergence is demonstrated for the case of unidimensional and multidimensional functions with one zero. The asymptotic normality of estimations is also proved. Algorithms with multiplicative step variation were tested for neural networks. In this thesis, and for the case of unidimensional functions of many zeros, is demonstrated that divergence or convergence to a neighborhood of some zero can occur depending on algorithm parameters. In case of convergence more precision of the neighborhood can be reached at the expense of more iterations. Many numerical examples are presented showing the advantage of the new algorithms for the unidimensional case. For the multidimensional case of these algorithms no benefit was observed.