Algoritmos de aproximação estocástica com valor do passo adaptativo - Cruz, João Pedro Antunes Ferreira da (2011)
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.