Hispanopedia Wiki
Articulo de referencia

Computación estocástica

La computación estocástica es un conjunto de técnicas que representan valores continuos mediante secuencias de bits aleatorios. De esta forma, se pueden realizar cálculos comple...

Hispanopedia WikiContenido en espanolLectura gratuita

La computación estocástica es un conjunto de técnicas que representan valores continuos mediante secuencias de bits aleatorios. De esta forma, se pueden realizar cálculos complejos mediante operaciones bit a bit sencillas aplicadas a dichas secuencias. La computación estocástica se distingue del estudio de los algoritmos aleatorios .

Motivación y un ejemplo sencillo

Supongamos quepag,q∈[0,1]{\displaystyle p,q\in [0,1]}Se da, y deseamos calcularpag×q{\displaystyle p\times q}La computación estocástica realiza esta operación utilizando probabilidad en lugar de aritmética.

Específicamente, supongamos que hay dos secuencias de bits aleatorias e independientes llamadas números estocásticos s (es decir, procesos de Bernoulli ), donde la probabilidad de un 1 en la primera secuencia espag{\displaystyle p}y la probabilidad en el segundo flujo esq{\displaystyle q}Podemos realizar la operación lógica AND entre las dos secuencias.

La probabilidad de un 1 en el flujo de salida espagq{\displaystyle pq}Al observar suficientes bits de salida y medir la frecuencia de los 1, es posible estimarpagq{\displaystyle pq}con una precisión arbitraria.

La operación anterior convierte un cálculo bastante complicado (multiplicación depag{\displaystyle p}yq{\displaystyle q}) en una serie de operaciones muy simples (evaluación deai∧bi{\displaystyle a_{i}\land b_{i}}) en bits aleatorios. Para ponerlo en otra perspectiva, supongamos la tabla de verdad de una puerta AND. La interpretación convencional es que la salida es verdadera si y solo si las entradas A y B son verdaderas. Sin embargo, si la tabla se interpreta verticalmente, (0011) AND (0101) es (0001), es decir, 1/2 x 1/2 = 1/4, que es exactamente una multiplicación aritmética. Como la información se presenta en una distribución de probabilidad , la multiplicación de probabilidad es literalmente una operación AND.

En términos más generales, la computación estocástica representa los números como secuencias de bits aleatorios y reconstruye los números calculando frecuencias. Los cálculos se realizan sobre las secuencias y traducen operaciones complicadas enpag{\displaystyle p}yq{\displaystyle q}en operaciones simples sobre sus representaciones de flujo. (Debido al método de reconstrucción, los dispositivos que realizan estas operaciones a veces se denominan procesadores de promedio estocástico). En términos modernos, la computación estocástica puede considerarse una interpretación de cálculos en términos probabilísticos, que luego se evalúan con un muestreador de Gibbs . También puede interpretarse como una computadora híbrida analógica / digital .

Historia

Fotografía del ordenador estocástico RASCEL.
La computadora estocástica RASCEL, alrededor de 1969.

La computación estocástica fue introducida por primera vez en un artículo pionero de John von Neumann en 1953. [ 1 ] Sin embargo, la teoría no pudo desarrollarse completamente hasta los avances en computación de la década de 1960, [ 2 ] [ 3 ] principalmente a través de una serie de esfuerzos simultáneos y paralelos en los EE. UU. [ 4 ] y el Reino Unido. [ 5 ] A finales de la década de 1960, la atención se centró en el diseño de hardware de propósito especial para realizar computación estocástica. Una gran cantidad [ 6 ] de estas máquinas se construyeron entre 1969 y 1974; RASCEL [ 7 ] se muestra en este artículo.

A pesar del gran interés que despertó en las décadas de 1960 y 1970, la computación estocástica finalmente no logró competir con la lógica digital más tradicional, por las razones que se detallan a continuación. El primer (y último) Simposio Internacional sobre Computación Estocástica [ 8 ] tuvo lugar en 1978; la investigación activa en este campo disminuyó en los años siguientes.

Aunque la computación estocástica disminuyó como método general de computación, ha demostrado ser prometedora en varias aplicaciones. La investigación se ha centrado tradicionalmente en ciertas tareas en aprendizaje automático y control. [ 9 ] [ 10 ] Recientemente, el interés se ha dirigido hacia la decodificación estocástica, que aplica la computación estocástica a la decodificación de códigos de corrección de errores. [ 11 ] Más recientemente, los circuitos estocásticos se han utilizado con éxito en tareas de procesamiento de imágenes como la detección de bordes [ 12 ] y el umbralizado de imágenes . [ 13 ] Los avances recientes en circuitos estocásticos también muestran ventajas prometedoras en velocidad y eficiencia energética en la aceleración de hardware de inteligencia artificial (IA) en computación de borde .

Fortalezas y debilidades

Si bien la computación estocástica fue un fracaso histórico, aún puede ser relevante para resolver ciertos problemas. Para comprender cuándo sigue siendo relevante, resulta útil compararla con métodos más tradicionales de computación digital.

Fortalezas

Supongamos que deseamos multiplicar dos números cada uno pornorte{\displaystyle n}bits de precisión. Usando el método típico de multiplicación larga , necesitamos realizar norte2{\displaystyle n^{2}}operaciones. Con la computación estocástica, podemos combinar mediante AND cualquier número de bits y el valor esperado siempre será correcto. (Sin embargo, con un número pequeño de muestras, la varianza hará que el resultado real sea muy impreciso).

Además, las operaciones subyacentes en un multiplicador digital son sumadores completos , mientras que una computadora estocástica solo requiere una puerta AND . Adicionalmente, un multiplicador digital requeriría ingenuamente2norte{\displaystyle 2n}un multiplicador estocástico requeriría solo dos cables de entrada, mientras que un multiplicador estocástico solo requeriría dos cables de entrada . (Sin embargo, si el multiplicador digital serializara su salida, también requeriría solo dos cables de entrada).

Además, la computación estocástica es robusta frente al ruido; si se invierten algunos bits en una secuencia, esos errores no tendrán un impacto significativo en la solución.

Además, los elementos de computación estocástica pueden tolerar desfases en el tiempo de llegada de las entradas. Los circuitos funcionan correctamente incluso cuando las entradas están desalineadas temporalmente. Como resultado, los sistemas estocásticos pueden diseñarse para funcionar con relojes locales de bajo costo en lugar de utilizar un reloj global y una costosa red de distribución de reloj. [ 14 ]

Finalmente, la computación estocástica proporciona una estimación de la solución que se vuelve más precisa a medida que extendemos el flujo de bits. En particular, proporciona una estimación aproximada muy rápidamente. Esta propiedad se conoce como precisión progresiva , lo que sugiere que la precisión de los números estocásticos (flujos de bits) aumenta a medida que avanza la computación. [ 15 ] Es como si los bits más significativos del número llegaran antes que los menos significativos ; a diferencia de los circuitos aritméticos convencionales donde los bits más significativos suelen llegar al final. En algunos sistemas iterativos, las soluciones parciales obtenidas mediante precisión progresiva pueden proporcionar una retroalimentación más rápida que mediante métodos de computación tradicionales, lo que conduce a una convergencia más rápida.

Debilidades

La computación estocástica es, por su propia naturaleza, aleatoria. Cuando examinamos una secuencia de bits aleatoria e intentamos reconstruir el valor subyacente, la precisión efectiva se puede medir mediante la varianza de nuestra muestra. En el ejemplo anterior, el multiplicador digital calcula un número para2norte{\displaystyle 2n}bits de exactitud, por lo que la precisión es2−2norte{\displaystyle 2^{-2n}}Si estamos utilizando una secuencia de bits aleatoria para estimar un número y queremos que la desviación estándar de nuestra estimación de la solución sea al menos2−2norte{\displaystyle 2^{-2n}}necesitaríamosO(24norte){\displaystyle O(2^{4n})}muestras. Esto representa un aumento exponencial en el trabajo. Sin embargo, en ciertas aplicaciones, la propiedad de precisión progresiva de la computación estocástica puede aprovecharse para compensar esta pérdida exponencial.

En segundo lugar, la computación estocástica requiere un método para generar secuencias de bits aleatorias con sesgo. En la práctica, estas secuencias se generan con generadores de números pseudoaleatorios . Desafortunadamente, generar bits (pseudo)aleatorios es bastante costoso (en comparación con el costo de, por ejemplo, un sumador completo). Por lo tanto, la ventaja a nivel de compuertas de la computación estocástica generalmente se pierde.

En tercer lugar, el análisis de la computación estocástica supone que los flujos de bits son independientes (no correlacionados). Si esta suposición no se cumple, la computación estocástica puede fallar estrepitosamente. Por ejemplo, si intentamos calcularpag2{\displaystyle p^{2}}multiplicando una secuencia de bits por pag{\displaystyle p}Por sí mismo, el proceso falla: dado queai∧ai=ai{\displaystyle a_{i}\land a_{i}=a_{i}}, el cálculo estocástico produciríapag×pag=pag{\displaystyle p\times p=p}, lo cual no es generalmente cierto (a menos quepag={\displaystyle p=}0 o 1). En sistemas con retroalimentación, el problema de la decorrelación puede manifestarse de formas más complejas. Los sistemas de procesadores estocásticos son propensos al enclavamiento , donde la retroalimentación entre diferentes componentes puede generar un estado de interbloqueo. [ 16 ] Se debe invertir un gran esfuerzo en descorrelacionar el sistema para intentar remediar el enclavamiento.

En cuarto lugar, aunque algunas funciones digitales tienen contrapartes estocásticas muy simples (como la traducción entre la multiplicación y la puerta AND), muchas no las tienen. Intentar expresar estas funciones estocásticamente puede causar diversas patologías. Por ejemplo, la decodificación estocástica requiere el cálculo de la funciónF(pag,q)→pagq/(pagq+(1−pag)(1−q)){\displaystyle f(p,q)\rightarrow pq/(pq+(1-p)(1-q))}No existe una única operación bit a bit que pueda calcular esta función; la solución habitual implica producir bits de salida correlacionados, lo que, como hemos visto anteriormente, puede causar una serie de problemas.

Otras funciones (como el operador de promedio)F(pag,q)→(pag+q)/2{\displaystyle f(p,q)\rightarrow (p+q)/2}Requiere diezmo o inflación de flujo. El equilibrio entre precisión y memoria puede ser complejo.

Decodificación estocástica

Si bien la computación estocástica presenta varios defectos como método de cálculo general, existen ciertas aplicaciones que resaltan sus ventajas. Un caso notable se da en la decodificación de ciertos códigos de corrección de errores.

En desarrollos ajenos a la computación estocástica, se desarrollaron métodos altamente eficaces para decodificar códigos LDPC mediante el algoritmo de propagación de creencias . En este contexto, la propagación de creencias implica la reestimación iterativa de ciertos parámetros utilizando dos operaciones básicas (esencialmente, una operación XOR probabilística y una operación de promediado).

En 2003, los investigadores se percataron de que estas dos operaciones podían modelarse de forma muy sencilla mediante computación estocástica. [ 17 ] Además, dado que el algoritmo de propagación de creencias es iterativo, la computación estocástica proporciona soluciones parciales que pueden conducir a una convergencia más rápida. Se han desarrollado implementaciones de hardware de decodificadores estocásticos en FPGA . [ 18 ] Los defensores de estos métodos argumentan que el rendimiento de la decodificación estocástica es comparable al de las alternativas digitales.

Métodos deterministas para la computación estocástica

Se han desarrollado métodos deterministas de SC para realizar cálculos completamente precisos con circuitos SC. [ 19 ] El principio esencial de estos métodos es que cada bit de una secuencia de bits interactúa con cada bit de las otras secuencias de bits exactamente una vez. Para producir un resultado completamente preciso con estos métodos, la operación debe ejecutarse para el producto de la longitud de las secuencias de bits de entrada. Los métodos deterministas se desarrollan en base a secuencias de bits unarias, [ 20 ] [ 21 ] secuencias de bits pseudoaleatorias, [ 22 ] y secuencias de bits de baja discrepancia. [ 23 ]

Variantes de la computación estocástica

Existen diversas variantes del paradigma básico de computación estocástica. Para obtener más información, consulte el libro de Mars y Poppelbaum citado.

El procesamiento de paquetes implica enviar un número fijo de bits en lugar de un flujo continuo. Una de las ventajas de este enfoque es que se mejora la precisión. Para ver por qué, supongamos que transmitimos s{\displaystyle s}bits. En la computación estocástica regular, podemos representar una precisión de aproximadamenteO(1/s){\displaystyle O(1/{\sqrt {s}})}diferentes valores, debido a la varianza de la estimación. En el procesamiento de paquetes, podemos representar una precisión de1/s{\displaystyle 1/s}Sin embargo, el procesamiento de paquetes conserva la misma robustez frente a errores que el procesamiento estocástico regular.

El procesamiento ergódico implica el envío de un flujo de paquetes, lo que aprovecha las ventajas del procesamiento estocástico y de paquetes convencional.

El procesamiento en ráfaga codifica un número mediante una secuencia de base creciente. Por ejemplo, codificaríamos 4.3 con diez dígitos decimales como

4444444555

Dado que el valor promedio del flujo anterior es 4,3, esta representación ofrece diversas ventajas: no hay aleatorización, ya que los números aparecen en orden ascendente, evitando así los problemas de los generadores de números pseudoaleatorios (PRNG), pero se conservan muchas de las ventajas de la computación estocástica (como las estimaciones parciales de la solución). Además, mantiene la precisión lineal del procesamiento ergódico y de haces.

Véase también

Referencias

  1. ↑ von Neumann, J. (1963). «Lógicas probabilísticas y la síntesis de organismos fiables a partir de componentes poco fiables». Obras completas de John von Neumann . Macmillan. ISBN 978-0-393-05169-8.{{cite conference}}: Incompatibilidad de ISBN/Fecha ( ayuda )
  2. ↑ Petrovic, R.; Siljak, D. (1962). "Multiplicación por medio de coincidencia" . Actas de la 3ª Reunión Internacional de Computación Analógica de ACTES .
  3. ↑ Afuso, C. (1964), Informe trimestral de programas técnicos , Departamento de Ciencias de la Computación, Universidad de Illinois, Urbana, Illinois{{citation}}: CS1 mantenimiento: falta el editor de ubicación ( enlace )
  4. ↑ Poppelbaum, W.; Afuso, C.; Esch, J. (1967). «Elementos y sistemas de computación estocástica». Actas de la conferencia conjunta de computación de otoño del 14 al 16 de noviembre de 1967 - AFIPS '67 (Otoño) . Vol. 31. págs. 635–644 . doi : 10.1145/1465611.1465696 . ISBN   9781450378963. S2CID 8504153 . 
  5. ↑ Gaines, B. (1967). «Computación estocástica». Actas de la conferencia conjunta de computación de primavera del 18 al 20 de abril de 1967 - AFIPS '67 (Primavera) . Vol. 30. págs. 149–156 . doi : 10.1145/1465482.1465505 . ISBN   9781450378956. S2CID 832296 . 
  6. ↑ Mars, P.; Poppelbaum, W. (1981). Procesadores de promediado estocástico y determinista . P. Peregrinus. ISBN 978-0-906048-44-3.
  7. ↑ Esch, John W. (1969). RASCEL, una computadora analógica programable basada en una matriz regular de lógica de elementos de computación estocástica (Tesis doctoral). Universidad de Illinois, Urbana, Illinois. AAI700084.
  8. ↑ Actas del primer Simposio Internacional sobre Computación Estocástica y sus Aplicaciones . Toulouse, Francia. 1978. OCLC 499229066 . 
  9. ↑ Gaines, BR (2013) [1969]. "Sistemas de computación estocástica". En Tou, Julius (ed.). Avances en la ciencia de los sistemas de información . Vol. 2. Springer. ISBN  9781489958433.
  10. ↑ van Daalen, M.; Jeavons, P.; Shawe-Taylor, J. (1993). "Una arquitectura neuronal estocástica que aprovecha las FPGA reconfigurables dinámicamente". [ 1993 ] Actas del Taller IEEE sobre FPGA para Máquinas de Computación Personalizadas . págs. 202–211 . doi : 10.1109/FPGA.1993.279462 . ISBN  0-8186-3890-7. S2CID 14929278 . 
  11. ↑ Gaudet, Vincent; Rapley, Anthony (febrero de 2003). "Decodificación iterativa mediante computación estocástica". Electronics Letters . 39 (3): 299– 301. Bibcode : 2003ElL....39..299G . doi : 10.1049/el:20030217 .
  12. ↑ Alaghi, A.; Li, C.; Hayes, JP (2013). "Circuitos estocásticos para aplicaciones de procesamiento de imágenes en tiempo real". Actas de la 50.ª Conferencia Anual de Automatización del Diseño (DAC '13 ). pág. 1. doi : 10.1145/2463209.2488901 . ISBN  9781450320719. S2CID 18174415 . 
  13. ↑ Najafi, MH; Salehi, ME (2016). "Una arquitectura rápida tolerante a fallos para el algoritmo de umbralización de imágenes locales de Sauvola mediante computación estocástica". IEEE Transactions on Very Large Scale Integration (VLSI) Systems . 24 (2): 808– 812. doi : 10.1109/TVLSI.2015.2415932 . S2CID 6591306 . 
  14. ↑ Najafi, MH; Lilja, DJ; Riedel, MD; Bazargan, K. (2016). "Circuitos estocásticos polisíncronos". 2016 21.ª Conferencia de Automatización del Diseño de Asia y el Pacífico Sur (ASP-DAC) . págs. 492–498 . doi : 10.1109/ASPDAC.2016.7428060 . ISBN  978-1-4673-9569-4. S2CID 8973285 . 
  15. ↑ Alaghi, A.; Hayes, JP (2013). "Revisión de la computación estocástica". ACM Transactions on Embedded Computing Systems . 12 (2s): 1. CiteSeerX 10.1.1.296.4448 . doi : 10.1145/2465787.2465794 . S2CID 4689958 .  
  16. ↑ Winstead, C.; Rapley, A.; Gaudet, V.; Schlegel, C. (septiembre de 2005). «Decodificadores iterativos estocásticos». Actas del Simposio Internacional sobre Teoría de la Información, 2005. ISIT 2005. Adelaida, Australia. págs. 1116–1120 . arXiv : cs/0501090 . doi : 10.1109/ISIT.2005.1523513 . ISBN  0-7803-9151-9. S2CID 16390484 . {{cite book}}: CS1 mantenimiento: falta el editor de ubicación ( enlace )
  17. ↑ Gaudet, Vincent; Rapley, Anthony (febrero de 2003). "Decodificación iterativa mediante computación estocástica". Electronics Letters . 39 (3): 299– 301. Bibcode : 2003ElL....39..299G . doi : 10.1049/el:20030217 .
  18. ↑ Gross, W.; Gaudet, V.; Milner, A. (2006). "Implementación estocástica de decodificadores LDPC". Actas de la Trigésimo Novena Conferencia de Asilomar sobre Señales, Sistemas y Computadoras .
  19. ↑ Najafi, M. Hassan; Jenson, Devon; Lilja, David J.; Riedel, Marc D. (diciembre de 2019). "Realización de cálculos estocásticos de forma determinista" . IEEE Transactions on Very Large Scale Integration (VLSI) Systems . 27 (12): 2925– 2938. doi : 10.1109/tvlsi.2019.2929354 . ISSN 1063-8210 . S2CID 201888463 .  
  20. ↑ Jenson, Devon; Riedel, Marc (7 de noviembre de 2016). «Un enfoque determinista para la computación estocástica». Actas de la 35.ª Conferencia Internacional sobre Diseño Asistido por Computadora . Nueva York, NY, EE. UU.: ACM. págs. 1-8 . doi : 10.1145/2966986.2966988 . ISBN  978-1-4503-4466-1. S2CID 11281124 . 
  21. ↑ Najafi, M. Hassan; Jamali-Zavareh, Shiva; Lilja, David J.; Riedel, Marc D.; Bazargan, Kia; Harjani, Ramesh (mayo de 2017). "Valores codificados en el tiempo para circuitos estocásticos altamente eficientes" . IEEE Transactions on Very Large Scale Integration (VLSI) Systems . 25 (5): 1644– 1657. doi : 10.1109/tvlsi.2016.2645902 . ISSN 1063-8210 . S2CID 5672761 .  
  22. ↑ Najafi, M. Hassan; Lilja, David (2018). "Muestreo descendente de alta calidad para enfoques deterministas de computación estocástica" . IEEE Transactions on Emerging Topics in Computing . 9 : 7–14 . doi : 10.1109/tetc.2017.2789243 . ISSN 2168-6750 . 
  23. ↑ Najafi, M. Hassan; Lilja, David J.; Riedel, Marc (5 de noviembre de 2018). «Métodos deterministas para computación estocástica utilizando secuencias de baja discrepancia». Actas de la Conferencia Internacional sobre Diseño Asistido por Computadora . Nueva York, NY, EE. UU.: ACM. págs. 1–8 . doi : 10.1145/3240765.3240797 . ISBN  978-1-4503-5950-4. S2CID 53236540 . 

Lecturas adicionales

  • Gaines, Brian R. (1967). "Técnicas de identificación con la computadora estocástica" (PDF) . Actas del Simposio IFAC sobre "Los problemas de la identificación en los sistemas de control automático", Sección 6 Instrumentos especiales de identificación, Praga, 12-19 de junio de 1967. Recuperado el 11 de noviembre de 2013 .
  • Alaghi, Armin; Hayes, John P. (2013). "Encuesta sobre computación estocástica" (PDF) . ACM Transactions on Embedded Computing Systems . 12 (2s): 1–19 . CiteSeerX 10.1.1.296.4448 . doi : 10.1145/2465787.2465794 . S2CID 4689958. Recuperado el 11 de noviembre de 2013 .  
Lecturas relacionadas
6 articulos
{\displaystyle \lim _{n\to \infty }\sum _{i=1}^{n}{\frac {i}{2^{i}}}=2}Algoritmo aleatorioUn algoritmo aleatorio es un algoritmo que emplea un grado de aleatoriedad como parte de su lógica o procedimiento. El algoritmo normalmente utiliz...proceso de Bernoulliproceso de BernoulliEn probabilidad y estadística , un proceso de Bernoulli (llamado así por Jacob Bernoulli ) es una secuencia finita o infinita de variables aleatori...Diagrama de Venn de conjunción lógicaConjunción lógicaEn lógica , matemáticas y lingüística , y (∧{\displaystyle \wedge }) es el operador veritativo-funcional de conjunción o conjunción lógica . El con...{\displaystyle \flecha izquierda-derecha}Si y sólo si↔⇔≡⟺ Símbolos lógicos que representan si y solo siDistribución de probabilidadEn teoría de probabilidad y estadística , una distribución de probabilidad es la función matemática que da las probabilidades de ocurrencia de posi...Muestreo de GibbsMuestreo de GibbsEn estadística , el muestreo de Gibbs o un muestreador de Gibbs es un algoritmo de Monte Carlo de cadena de Markov (MCMC) para muestrear a partir d...