Los métodos de aproximación estocástica son una familia de métodos iterativos que se utilizan normalmente para problemas de búsqueda de raíces o para problemas de optimización . Las reglas de actualización recursiva de los métodos de aproximación estocástica se pueden utilizar, entre otras cosas, para resolver sistemas lineales cuando los datos recopilados están corrompidos por el ruido, o para aproximar valores extremos de funciones que no se pueden calcular directamente, sino solo estimar mediante observaciones ruidosas.
En pocas palabras, los algoritmos de aproximación estocástica se ocupan de una función de la forma cuál es el valor esperado de una función dependiendo de una variable aleatoria . El objetivo es recuperar las propiedades de dicha función.sin evaluarlo directamente. En cambio, los algoritmos de aproximación estocástica utilizan muestras aleatorias de para aproximar eficientemente las propiedades de como ceros o extremos.
Recientemente, las aproximaciones estocásticas han encontrado amplias aplicaciones en los campos de la estadística y el aprendizaje automático, especialmente en entornos con big data . Estas aplicaciones van desde métodos y algoritmos de optimización estocástica hasta formas en línea del algoritmo EM , aprendizaje por refuerzo a través de diferencias temporales y aprendizaje profundo , entre otros. [1] Los algoritmos de aproximación estocástica también se han utilizado en las ciencias sociales para describir la dinámica colectiva: el juego ficticio en la teoría del aprendizaje y los algoritmos de consenso pueden estudiarse utilizando su teoría. [2]
Los primeros y prototípicos algoritmos de este tipo son los algoritmos Robbins-Monro y Kiefer-Wolfowitz introducidos respectivamente en 1951 y 1952.
Algoritmo de Robbins-Monro
El algoritmo de Robbins-Monro, introducido en 1951 por Herbert Robbins y Sutton Monro , [3] presentó una metodología para resolver un problema de búsqueda de raíces, donde la función se representa como un valor esperado. Supongamos que tenemos una funcióny una constante , tal que la ecuación tiene una raíz única en . Se supone que si bien no podemos observar directamente la función, podemos obtener medidas de la variable aleatoria dónde . La estructura del algoritmo es generar iteraciones de la forma:
Aquí, es una secuencia de tamaños de paso positivos. Robbins y Monro demostraron [3] , Teorema 2 que converge en (y por tanto también en probabilidad) a , y Blum [4] demostró más tarde que la convergencia es en realidad con probabilidad uno, siempre que:
- está uniformemente acotado,
- no es decreciente,
- existe y es positivo, y
- La secuencia cumple los siguientes requisitos:
Una secuencia particular de pasos que satisfacen estas condiciones, y fue sugerida por Robbins-Monro, tiene la forma: , por . Otras series son posibles pero para promediar el ruido en, se debe cumplir la condición anterior.
Resultados de complejidad
- Si es dos veces continuamente diferenciable y fuertemente convexo, y el minimizador de pertenece al interior de , entonces el algoritmo de Robbins-Monro logrará la tasa de convergencia asintóticamente óptima, con respecto a la función objetivo, siendo , dónde es el valor mínimo de encima . [5] [6]
- Por el contrario, en el caso convexo general, donde carecemos del supuesto de suavidad y convexidad fuerte, Nemirovski y Yudin [7] han demostrado que la tasa de convergencia asintóticamente óptima, con respecto a los valores de la función objetivo, es. También han demostrado que esta tasa no se puede mejorar.
Desarrollos posteriores y promedios de Polyak-Ruppert
Si bien el algoritmo de Robbins-Monro teóricamente es capaz de lograr bajo el supuesto de una diferenciabilidad doble continua y una fuerte convexidad, puede funcionar bastante mal en la implementación. Esto se debe principalmente al hecho de que el algoritmo es muy sensible a la elección de la secuencia de tamaño de paso, y la supuesta política de tamaño de paso asintóticamente óptimo puede ser bastante dañina al principio. [6] [8]
Chung [9] (1954) y Fabian [10] (1968) demostraron que alcanzaríamos una tasa de convergencia óptima con (o ). Lai y Robbins [11] [12] diseñaron procedimientos adaptativos para estimar tal que tiene una variación asintótica mínima. Sin embargo, la aplicación de estos métodos óptimos requiere mucha información a priori que es difícil de obtener en la mayoría de las situaciones. Para superar este déficit, Polyak [13] (1991) y Ruppert [14] (1988) desarrollaron independientemente un nuevo algoritmo óptimo basado en la idea de promediar las trayectorias. Polyak y Juditsky [15] también presentaron un método para acelerar Robbins-Monro para problemas de búsqueda de raíces lineales y no lineales mediante el uso de pasos más largos y promediando los iterados. El algoritmo tendría la siguiente estructura:
A1)
Por tanto, la secuencia con satisface esta restricción, pero no, de ahí los pasos más largos. Bajo los supuestos descritos en el algoritmo de Robbins-Monro, la modificación resultante dará como resultado la misma tasa de convergencia asintóticamente óptimapero con una política de tamaño de paso más sólida. [15] Antes de esto, la idea de usar pasos más largos y promediar las iteraciones ya había sido propuesta por Nemirovski y Yudin [16] para los casos de resolución del problema de optimización estocástica con objetivos convexos continuos y para problemas de punto silla convexo-cóncavo. Se observó que estos algoritmos alcanzan la tasa no asintótica.
En el capítulo 11 de Kushner y Yin [17] se da un resultado más general al definir el tiempo interpolado, proceso interpolado y proceso normalizado interpolado como
Con el supuesto A1) y el siguiente A2)
A2) Hay una matriz de Hurwitz y una matriz simétrica y definida positiva tal que converge débilmente a , dónde es la estatisolución para
satisfecho y definir . Entonces para cada,
El éxito de la idea de promediar se debe a la separación de la escala de tiempo de la secuencia original y la secuencia promediada , siendo la escala de tiempo del anterior más rápida.
Aplicación en optimización estocástica
Supongamos que queremos resolver el siguiente problema de optimización estocástica
Aquí es un estimador insesgado de . Si depende de , en general no existe una forma natural de generar un resultado aleatorio que es un estimador insesgado del gradiente. En algunos casos especiales, cuando son aplicables los métodos de IPA o de razón de verosimilitud, se puede obtener un estimador de gradiente insesgado.. Sies visto como un proceso aleatorio subyacente "fundamental" que se genera independientemente de, y bajo algunas condiciones de regularización para operaciones de intercambio derivado-integral de modo que , luego da la estimación sin sesgo del gradiente fundamental. Sin embargo, para algunas aplicaciones tenemos que utilizar métodos de diferencias finitas en los que tiene una expectativa condicional cercana a pero no exactamente igual.
Luego definimos una recursividad de forma análoga al método de Newton en el algoritmo determinista:
Convergencia del algoritmo
El siguiente resultado proporciona condiciones suficientes en para que el algoritmo converja: [18]
C1)
C2)
C3)
C4)
C5)
Luego converge a casi seguro.
Aquí hay algunas explicaciones intuitivas sobre estas condiciones. Suponeres una variable aleatoria acotada uniformemente. Si C2) no se satisface, es decir , luego
Ejemplo (donde el método de gradiente estocástico es apropiado) [8]
Suponer , dónde es diferenciable y es una variable aleatoria independiente de . Luego depende de la media de , y el método del gradiente estocástico sería apropiado en este problema. Podemos elegir
Algoritmo de Kiefer-Wolfowitz
El algoritmo de Kiefer-Wolfowitz fue introducido en 1952 por Jacob Wolfowitz y Jack Kiefer , [19] y fue motivado por la publicación del algoritmo de Robbins-Monro. Sin embargo, el algoritmo se presentó como un método que estimaría estocásticamente el máximo de una función. Dejar ser una función que tiene un máximo en el punto . Se asume quees desconocido; sin embargo, ciertas observaciones, dónde , se puede hacer en cualquier momento . La estructura del algoritmo sigue un método similar a un gradiente, y las iteraciones se generan de la siguiente manera:
dónde y son independientes, y el gradiente de se aproxima usando diferencias finitas. La secuencia especifica la secuencia de anchos de diferencia finita utilizados para la aproximación de gradiente, mientras que la secuencia especifica una secuencia de tamaños de pasos positivos tomados en esa dirección. Kiefer y Wolfowitz demostraron que, si satisfecho ciertas condiciones de regularidad, entonces convergerá a en probabilidad como , y más tarde Blum [4] en 1954 mostró converge a casi seguro, siempre que:
- para todos .
- La función tiene un punto único de máximo (mínimo) y es cóncavo (convexo) fuerte
- El algoritmo se presentó primero con el requisito de que la función mantiene una fuerte convexidad global (concavidad) en todo el espacio factible. Dado que esta condición es demasiado restrictiva para imponerla sobre todo el dominio, Kiefer y Wolfowitz propusieron que es suficiente imponer la condición sobre un conjunto compacto que se sabe que incluye la solución óptima.
- La función satisface las condiciones de regularidad de la siguiente manera:
- Existe y tal que
- Existe y tal que
- Para cada , existe algo tal que
- Existe y tal que
- Las secuencias seleccionadas y deben ser secuencias infinitas de números positivos tales que
Una elección adecuada de secuencias, como recomiendan Kiefer y Wolfowitz, sería y .
Desarrollos posteriores y cuestiones importantes
- El algoritmo de Kiefer Wolfowitz requiere que para cada cálculo de gradiente, al menos Se deben simular diferentes valores de parámetros para cada iteración del algoritmo, donde es la dimensión del espacio de búsqueda. Esto significa que cuando es grande, el algoritmo de Kiefer-Wolfowitz requerirá un esfuerzo computacional sustancial por iteración, lo que conducirá a una convergencia lenta.
- Para abordar este problema, Spall propuso el uso de perturbaciones simultáneas para estimar el gradiente. Este método requeriría solo dos simulaciones por iteración, independientemente de la dimensión. [20]
- En las condiciones requeridas para la convergencia, la capacidad de especificar un conjunto compacto predeterminado que cumpla con una fuerte convexidad (o concavidad) y contenga la solución única puede ser difícil de encontrar. Con respecto a las aplicaciones del mundo real, si el dominio es bastante grande, estas suposiciones pueden ser bastante restrictivas y poco realistas.
Nuevos desarrollos
Se ha desarrollado una extensa literatura teórica en torno a estos algoritmos, en relación con las condiciones de convergencia, tasas de convergencia, generalizaciones multivariadas y de otro tipo, elección adecuada del tamaño de paso, posibles modelos de ruido, etc. [21] [22] Estos métodos también se aplican en la teoría de control , en cuyo caso la función desconocida que deseamos optimizar o encontrar el cero puede variar en el tiempo. En este caso, el tamaño del pasono debe converger a cero, pero debe elegirse para realizar un seguimiento de la función. [21] , 2ª ed., Capítulo 3
C. Johan Masreliez y R. Douglas Martin fueron los primeros en aplicar la aproximación estocástica a la estimación robusta . [23]
La principal herramienta para analizar los algoritmos de aproximaciones estocásticas (incluidos los algoritmos de Robbins-Monro y Kiefer-Wolfowitz) es un teorema de Aryeh Dvoretzky publicado en las actas del tercer simposio de Berkeley sobre estadística matemática y probabilidad, 1956. [24]
Ver también
- Descenso de gradiente estocástico
Referencias
- ^ Toulis, Panos; Airoldi, Edoardo (2015). "Estrategias de estimación escalables basadas en aproximaciones estocásticas: resultados clásicos y nuevos conocimientos" . Estadística y Computación . 25 (4): 781–795. doi : 10.1007 / s11222-015-9560-y . PMC 4484776 . PMID 26139959 .
- ^ Le Ny, Jerome. "Introducción a los algoritmos de aproximación estocástica" (PDF) . Polytechnique Montreal . Notas de enseñanza . Consultado el 16 de noviembre de 2016 .
- ^ a b Robbins, H .; Monro, S. (1951). "Un método de aproximación estocástico" . Los Anales de Estadística Matemática . 22 (3): 400. doi : 10.1214 / aoms / 1177729586 .
- ^ a b Blum, Julius R. (1 de junio de 1954). "Métodos de aproximación que convergen con la probabilidad uno" . Los Anales de Estadística Matemática . 25 (2): 382–386. doi : 10.1214 / aoms / 1177728794 . ISSN 0003-4851 .
- ^ Sacks, J. (1958). "Distribución asintótica de procedimientos de aproximación estocástica" . Los Anales de Estadística Matemática . 29 (2): 373–405. doi : 10.1214 / aoms / 1177706619 . JSTOR 2237335 .
- ^ a b Nemirovski, A .; Juditsky, A .; Lan, G .; Shapiro, A. (2009). "Enfoque de aproximación estocástica robusta a la programación estocástica". Revista SIAM de Optimización . 19 (4): 1574. doi : 10.1137 / 070704277 .
- ^ Complejidad del problema y eficiencia del método en optimización, A. Nemirovski y D. Yudin, Wiley -Intersci. Ser. Matemáticas discretas 15 John Wiley Nueva York (1983).
- ^ a b Introducción a la búsqueda y optimización estocásticas: estimación, simulación y control , JC Spall, John Wiley Hoboken, Nueva Jersey , (2003).
- ^ Chung, KL (1 de septiembre de 1954). "En un método de aproximación estocástico" . Los Anales de Estadística Matemática . 25 (3): 463–483. doi : 10.1214 / aoms / 1177728716 . ISSN 0003-4851 .
- ^ Fabián, Vaclav (1 de agosto de 1968). "Sobre normalidad asintótica en aproximación estocástica" . Los Anales de Estadística Matemática . 39 (4): 1327-1332. doi : 10.1214 / aoms / 1177698258 . ISSN 0003-4851 .
- ^ Lai, TL; Robbins, Herbert (1 de noviembre de 1979). "Diseño adaptativo y aproximación estocástica" . The Annals of Statistics . 7 (6): 1196-1221. doi : 10.1214 / aos / 1176344840 . ISSN 0090-5364 .
- ^ Lai, Tze Leung; Robbins, Herbert (1 de septiembre de 1981). "Consistencia y eficiencia asintótica de estimaciones de pendiente en esquemas de aproximación estocástica". Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete . 56 (3): 329–360. doi : 10.1007 / BF00536178 . ISSN 0044-3719 . S2CID 122109044 .
- ^ Polyak, BT (1 de enero de 1990). "Nuevos procedimientos de aproximación estocástica. (En ruso)" . 7 (7). Cite journal requiere
|journal=
( ayuda ) - ^ Ruppert, D. "Estimadores eficientes de un proceso robbins-monro de convergencia lenta" . Cite journal requiere
|journal=
( ayuda ) - ^ a b Polyak, BT; Juditsky, AB (1992). "Aceleración de la aproximación estocástica por promediado". Revista SIAM de Control y Optimización . 30 (4): 838. doi : 10.1137 / 0330046 .
- ↑ Sobre la convergencia de Cezari del método de descenso más empinado para aproximar los puntos de silla de las funciones convexo-cóncavas, A. Nemirovski y D. Yudin, Dokl. Akad. Nauk SSR 2939 , (1978 (ruso)), matemáticas soviéticas. Dokl. 19 (1978 (inglés)).
- ^ Kushner, Harold; George Yin, G. (17 de julio de 2003). Aproximación estocástica y algoritmos recursivos y | Harold Kushner | Springer . www.springer.com . ISBN 9780387008943. Consultado el 16 de mayo de 2016 .
- ^ Bouleau, N .; Lepingle, D. (1994). Métodos numéricos para procesos estocásticos . Nueva York: John Wiley. ISBN 9780471546412.
- ^ Kiefer, J .; Wolfowitz, J. (1952). "Estimación estocástica del máximo de una función de regresión" . Los Anales de Estadística Matemática . 23 (3): 462. doi : 10.1214 / aoms / 1177729392 .
- ^ Spall, JC (2000). "Aproximación estocástica adaptativa por el método de perturbación simultánea". Transacciones IEEE sobre control automático . 45 (10): 1839–1853. doi : 10.1109 / TAC.2000.880982 .
- ^ a b Kushner, HJ ; Yin, GG (1997). Algoritmos y aplicaciones de aproximación estocástica . doi : 10.1007 / 978-1-4899-2696-8 . ISBN 978-1-4899-2698-2.
- ^ Aproximación estocástica y estimación recursiva , Mikhail Borisovich Nevel'son y Rafail Zalmanovich Has'minskiĭ, traducido por el Programa de Israel para Traducciones Científicas y B. Silver, Providence, RI: American Mathematical Society, 1973, 1976. ISBN 0-8218-1597-0 .
- ^ Martin, R .; Masreliez, C. (1975). "Estimación robusta mediante aproximación estocástica". Transacciones IEEE sobre teoría de la información . 21 (3): 263. doi : 10.1109 / TIT.1975.1055386 .
- ^ Dvoretzky, Aryeh (1 de enero de 1956). "Sobre aproximación estocástica" . Los regentes de la Universidad de California. Cite journal requiere
|journal=
( ayuda )