¿Qué quiere decir uno con integración numérica que es demasiado costoso?

Estoy leyendo sobre la inferencia bayesiana y me encontré con la frase "la integración numérica de la probabilidad marginal es demasiado costosa"

No tengo experiencia en matemáticas y me preguntaba qué significa exactamente caro aquí. ¿Es solo en términos de potencia de cálculo o hay algo más?

bayesian numerical-integration variational-bayes approximate-inference discretetimeisnice
fuente

Significa que requiere demasiada potencia computacional, probablemente en términos de tiempo de CPU (ya que todos los recursos informáticos son esencialmente memoria o CPU).

Sycorax dice Reinstate Monica

En realidad, el ancho de banda de la comunicación puede convertirse en un problema a veces (por ejemplo, entre caché / RAM / disco en serie, o entre nodos de cómputo en paralelo).

GeoMatt22

Significa que lleva demasiado tiempo, para una sola computadora, nuestra para una red de computadoras, realizar el cálculo.

Jack Maddington

Y si la probabilidad marginal se necesita dentro de algún ciclo, lo que cuenta como demasiado caro es mucho menor. P.ej. una rutina de integración de 1 segundo suena rápido, pero puede ser "demasiado costoso" si necesita hacerlo 1 millón de veces ...

Matthew Gunn

Caro en términos de esfuerzo computacional, ya que requiere más esfuerzo calcularlo de lo que puede permitirse, ya que lleva demasiado tiempo o necesita demasiados procesadores para hacerlo en un tiempo razonable.

user253751

Respuestas:

En el contexto de los problemas computacionales, incluidos los métodos numéricos para la inferencia bayesiana, la frase "demasiado caro" generalmente podría referirse a dos cuestiones

un problema particular es demasiado "grande" para computarlo para un " presupuesto " particular
un enfoque general escala mal, es decir, tiene una alta complejidad computacional

Para cualquier caso, los recursos computacionales que comprenden el "presupuesto" pueden consistir en cosas como ciclos de CPU ( complejidad de tiempo ), memoria ( complejidad de espacio ) o ancho de banda de comunicación ( dentro o entre nodos de cómputo). En la segunda instancia, "demasiado caro" significaría intratable .

En el contexto del cálculo bayesiano, la cita probablemente se refiere a problemas de marginación en una gran cantidad de variables .

Por ejemplo, comienza el resumen de este artículo reciente

La integración se ve afectada por la maldición de la dimensionalidad y rápidamente se vuelve intratable a medida que crece la dimensionalidad del problema.

y continúa diciendo

Proponemos un algoritmo aleatorio que ... a su vez puede usarse, por ejemplo, para computación marginal o selección de modelo.

(A modo de comparación, este reciente capítulo de libro discute métodos considerados "no demasiado caros").

GeoMatt22
fuente

Esta es una respuesta genial. Sin embargo, solo agregaré que "caro" también puede tomarse cada vez más literalmente. - Uno puede aumentar drásticamente la potencia de cómputo y el almacenamiento (a niveles de supercomputadora, durante el tiempo que sea necesario), muy fácilmente en estos días (y bastante barato) ... pero para grandes problemas aún resultará demasiado costoso - - en eso literalmente costará más dinero real del que tienes disponible.

Glen_b -Reinstate Monica

@Glen_b que es un buen punto! Me imagino que este significado es menos común en la literatura publicada ... pero más común en las propuestas (¡y sus comentarios!)

GeoMatt22

@ GeoMatt22 En realidad, es otra forma de expresar el mismo significado, si lo piensas.

user253751

@ GeoMatt22 ¡Gracias! Ahora entiendo perfectamente lo que significa caro en un contexto bayesiano.

discretetimeisnice

Le daré un ejemplo de caso discreto para mostrar por qué la integración / suma es tan costosa.

$100$ $P(X_1, X_2, \cdots, X_{100})$ $2^{100}$

$P(X_1)$

PAG (X_{1}) = \sum_{X_{2}} \sum_{X_{3}} \dots \sum_{X_{100}} PAG (X_{1}, X_{2}, \dots, X_{100})

$P(X_1)=\sum_{X_2}\sum_{X_3}\cdots \sum_{X_{100}}P(X_1, X_2, \cdots, X_{100})$

$99$ $2^{99}$

En la literatura de modelos gráficos probabilísticos , tal forma de calcular la distribución marginal se llama enfoque de "fuerza bruta" para realizar "inferencia". Por nombre, podemos saber que es costoso. Y las personas usan muchas otras formas de realizar la inferencia, por ejemplo, obtener la distribución marginal de manera efectiva. "Otras formas" incluyendo inferencia aproximada , etc.

Haitao Du
fuente

Tal vez también podría comentar por qué el enfoque bayesiano es útil aquí, como surgió la pregunta en este contexto.

Tim

Por lo general, cuando se realiza la inferencia bayesiana, es fácil encontrar una gran integración sobre variables molestas, por ejemplo. Otro ejemplo puede ser un muestreo numérico como en este caso a partir de una función de probabilidad, lo que significa realizar un muestreo aleatorio de una distribución dada. A medida que aumenta el número de parámetros del modelo, este muestreo se vuelve extremadamente pesado y se han desarrollado varios métodos computacionales para acelerar el procedimiento y permitir implementaciones muy rápidas, manteniendo, por supuesto, un alto nivel de precisión. Estas técnicas son, por ejemplo, MC, MCMC, Metropolis ecc. Eche un vistazo al análisis de datos bayesianos de Gelman et. ¡Debería darle una amplia introducción! buena suerte

Lcol
fuente

Esta respuesta no parece abordar la pregunta principal del OP en torno al significado de "caro" en este contexto. O al menos no muy claramente.

Shufflepants

La explicación breve es presentar al lector el significado de la demanda computacional al realizar análisis específicos en estadística bayesiana, ya que se afirma que no es un matemático. De todos modos espero que haya sido claro para alguien

Lcol