Os métodos de aproximação estocástica são uma família de métodos iterativos tipicamente usados para problemas de busca de raízes ou para problemas de otimização. As regras de atualização recursiva dos métodos de aproximação estocástica podem ser usadas, entre outras coisas, para resolver sistemas lineares quando os dados coletados são corrompidos por ruído, ou para aproximar valores extremos de funções que não podem ser computadas diretamente, mas apenas estimadas via observações ruidosas.
Em resumo, os algoritmos de aproximação estocástica lidam com uma função da forma que é o valor esperado de uma função que depende de uma variável aleatória . O objetivo é recuperar propriedades de tal função sem avaliá-la diretamente. Em vez disso, algoritmos de aproximação estocástica usam amostras aleatórias de para aproximar eficientemente propriedades de , como zeros ou extremos.
Recentemente, as aproximações estocásticas encontraram extensas aplicações nas áreas de estatística e aprendizado de máquina, especialmente em configurações com big data. Estas aplicações variam desde métodos e algoritmos de otimização estocástica, a formas online do algoritmo EM, aprendizado por reforço via diferenças temporais, e aprendizado profundo (deep learning), entre outros. Algoritmos de aproximação estocástica também têm sido usados nas ciências sociais para descrever dinâmicas coletivas: a jogada fictícia (fictitious play) na teoria do aprendizado e os algoritmos de consenso podem ser estudados usando a sua teoria.
Os algoritmos mais antigos, e prototípicos, deste tipo são os algoritmos de Robbins-Monro e Kiefer-Wolfowitz, introduzidos respetivamente em 1951 e 1952.
Algoritmo de Robbins-Monro O algoritmo de Robbins-Monro, introduzido em 1951 por Herbert Robbins e Sutton Monro, apresentou uma metodologia para resolver um problema de busca de raízes, onde a função é representada como um valor esperado. Assuma que temos uma função , e uma constante , de modo que a equação tenha uma raiz única em Presume-se que, embora não possamos observar diretamente a função podemos, em vez disso, obter medições da variável aleatória onde . A estrutura do algoritmo consiste então em gerar iterações da forma:
Aqui, é uma sequência de tamanhos de passo positivos. Robbins e Monro provaram, Teorema 2 que converge em (e, portanto, também em probabilidade) para , e Blum provou mais tarde que a convergência é, na verdade, com probabilidade um, desde que:
seja uniformemente limitada, seja não decrescente, exista e seja positiva, e A sequência satisfaça os seguintes requisitos:
Uma sequência particular de passos que satisfaz essas condições, e que foi sugerida por Robbins-Monro, tem a forma: , para . Outras séries, como são possíveis, mas para calcular a média do ruído em , a condição acima deve ser atendida.
Exemplo Considere o problema de estimar a média de uma distribuição de probabilidade a partir de um fluxo de amostras independentes .
Seja , então a solução única para é a média desejada . O algoritmo RM dá-nosIsto é equivalente à descida de gradiente estocástico com a função de perda . Também é equivalente a uma média ponderada:No geral, se existe alguma função tal que , então o algoritmo de Robbins-Monro é equivalente à descida de gradiente estocástico com a função de perda . No entanto, o algoritmo RM não exige que exista para convergir.
Resultados de complexidade
Se for duas vezes continuamente diferenciável, e fortemente convexa, e o minimizador de pertencer ao interior de , então o algoritmo de Robbins-Monro alcançará a taxa de convergência assintoticamente ótima, com respeito à função objetivo, sendo , onde é o valor mínimo de sobre . Por outro lado, no caso convexo geral, onde carecemos tanto da suposição de suavidade quanto de forte convexidade, Nemirovski e YudinProblem Complexity and Method Efficiency in Optimization, A. Nemirovski and D. Yudin, Wiley -Intersci. Ser. Discrete Math 15 John Wiley New York (1983). mostraram que a taxa de convergência assintoticamente ótima, com relação aos valores da função objetivo, é . Eles também provaram que essa taxa não pode ser melhorada.
Desenvolvimentos subsequentes e cálculo de média de Polyak-Ruppert Embora o algoritmo de Robbins-Monro seja teoricamente capaz de alcançar sob a suposição de diferenciabilidade contínua dupla e forte convexidade, ele pode ter um desempenho bastante fraco na implementação. Isto deve-se principalmente ao facto de que o algoritmo é muito sensível à escolha da sequência de tamanhos de passo, e a suposta política de tamanho de passo assintoticamente ideal pode ser bastante prejudicial no início.Introduction to Stochastic Search and Optimization: Estimation, Simulation and Control, J.C. Spall, John Wiley Hoboken, NJ, (2003).
Chung (1954) e Fabian (1968) mostraram que alcançaríamos a taxa de convergência ótima com (ou ). Lai e Robbins desenvolveram procedimentos adaptativos para estimar de tal modo que tenha variância assintótica mínima. Contudo, a aplicação de tais métodos ótimos requer muita informação a priori que é difícil de obter na maioria das situações. Para superar essa deficiência, Polyak (1991) e Ruppert (1988) desenvolveram independentemente um novo algoritmo ótimo baseado na ideia de calcular a média das trajetórias. Polyak e Juditsky também apresentaram um método para acelerar o Robbins-Monro para problemas de busca de raízes lineares e não lineares através do uso de passos mais longos, e do cálculo da média das iterações. O algoritmo teria a seguinte estrutura:A convergência de para a raiz única baseia-se na condição de que a sequência de passos diminua suficientemente devagar. Isso é
A1)
Portanto, a sequência com satisfaz esta restrição, mas não, daí os passos mais longos. Sob as suposições delineadas no algoritmo de Robbins-Monro, a modificação resultante resultará na mesma taxa de convergência assintoticamente ótima , mas com uma política de tamanho de passo mais robusta. Antes disto, a ideia de usar passos mais longos e calcular a média das iterações já havia sido proposta por Nemirovski e YudinOn Cezari's convergence of the steepest descent method for approximating saddle points of convex-concave functions, A. Nemirovski and D. Yudin, Dokl. Akad. Nauk SSR 2939, (1978 (Russian)), Soviet Math. Dokl. 19 (1978 (English)). para os casos de resolução do problema de otimização estocástica com objetivos convexos contínuos e para problemas de ponto de sela convexo-côncavo. Observou-se que esses algoritmos atingem a taxa não assintótica .
Um resultado mais geral é dado no Capítulo 11 de Kushner e Yin definindo o tempo interpolado , o processo interpolado e o processo normalizado interpolado como
Seja a média da iteração e o erro normalizado associado seja .
Com a suposição A1) e a seguinte A2)
A2) Existe uma matriz de Hurwitz e uma matriz simétrica e positiva definida de tal modo que converge fracamente para , onde é a solução estacionária para onde é um processo de Wiener padrão.
Satisfeita, e defina . Então para cada ,
O sucesso da ideia de calcular a média deve-se à separação da escala de tempo da sequência original e da sequência com a média , sendo a escala de tempo da primeira mais rápida.
Aplicação em otimização estocástica Suponha que queremos resolver o seguinte problema de otimização estocásticaonde é diferenciável e convexa, então este problema é equivalente a encontrar a raiz de . Aqui pode ser interpretado como algum custo "observado" em função do escolhido e dos efeitos aleatórios . Na prática, pode ser difícil obter uma forma analítica de . O método de Robbins-Monro consegue gerar uma sequência para aproximar se for possível gerar , no qual a expectativa condicional de dado é exatamente , ou seja, é simulado a partir de uma distribuição condicional definida por
Aqui é um estimador imparcial (não enviesado) de . Se depende de , geralmente não há uma maneira natural de gerar um resultado aleatório que seja um estimador imparcial do gradiente. Em alguns casos especiais, quando os métodos de IPA ou razão de verossimilhança são aplicáveis, é possível obter um estimador de gradiente imparcial . Se é visto como algum processo aleatório "fundamental" subjacente que é gerado independentemente de , e sob algumas condições de regularização para operações de troca derivativa-integral de modo que , então fornece a estimativa fundamental e imparcial do gradiente. Contudo, para algumas aplicações temos de usar métodos de diferenças finitas nos quais tem uma expectativa condicional próxima de , mas não exatamente igual a ela.
Ao identificar a minimização com o problema de busca de raízes , a aproximação estocástica pode ser aplicada para definir uma solução recursiva para o mínimo, análoga ao algoritmo de Robbins-Monro:
Convergência do algoritmo O resultado seguinte fornece condições suficientes em para o algoritmo convergir:
C1)
C2)
C3)
C4) , para um limite fixo .
C5) é estritamente convexa, isto é:
Então converge para quase certamente.
Aqui estão algumas explicações intuitivas sobre essas condições. Suponha que seja uma variável aleatória uniformemente limitada. Se a C2) não for satisfeita, ou seja, , então
é uma sequência limitada, portanto a iteração não pode convergir para se a suposição inicial estiver muito distante de . Quanto à C3), observe que se convergir para então
então devemos ter , e a condição C3) assegura isso. Uma escolha natural seria . A condição C5) é uma condição bastante rigorosa sobre a forma de ; ela fornece a direção de busca do algoritmo.
Exemplo (onde o método do gradiente estocástico é apropriado) Suponha que , onde é diferenciável e é uma variável aleatória independente de . Então depende da média de , e o método do gradiente estocástico seria apropriado neste problema. Podemos escolher
Algoritmo de Kiefer-Wolfowitz O algoritmo de Kiefer-Wolfowitz foi introduzido em 1952 por Jacob Wolfowitz e Jack Kiefer, e foi motivado pela publicação do algoritmo de Robbins-Monro. No entanto, o algoritmo foi apresentado como um método que estimaria estocasticamente o máximo de uma função.
Seja uma função que tem um máximo no ponto . Presume-se que seja desconhecida; no entanto, certas observações , onde , podem ser feitas em qualquer ponto . A estrutura do algoritmo segue um método do tipo gradiente, com as iterações sendo geradas como
onde e são independentes. A cada passo, o gradiente de é aproximado de forma semelhante a um método de diferenças centrais com . Portanto a sequência especifica a sequência de larguras de diferenças finitas usadas para a aproximação do gradiente, enquanto a sequência especifica uma sequência de tamanhos de passo positivos dados ao longo dessa direção.
Kiefer e Wolfowitz provaram que, se satisfizesse certas condições de regularidade, então convergiria para em probabilidade à medida que , e mais tarde Blum em 1954 mostrou que converge para quase certamente, desde que:
para todo . A função tenha um único ponto de máximo (mínimo) e seja fortemente côncava (convexa) O algoritmo foi primeiro apresentado com o requisito de que a função mantivesse forte convexidade (concavidade) global sobre todo o espaço viável. Como essa condição é demasiado restritiva para ser imposta sobre todo o domínio, Kiefer e Wolfowitz propuseram que é suficiente impor a condição sobre um conjunto compacto que se sabe incluir a solução ótima. A função satisfaça as condições de regularidade a seguir: Existam e tais que Existam e tais que Para cada , exista algum tal que As sequências selecionadas e devem ser sequências infinitas de números positivos tais que
Uma escolha adequada de sequências, conforme recomendado por Kiefer e Wolfowitz, seria e .
Desenvolvimentos subsequentes e questões importantes