Por ejemplo, en una red generativa adversaria, a menudo escuchamos que la inferencia es fácil porque la distribución condicional de x dado la variable latente z es 'manejable'. Además, he leído en algún lugar que la máquina de Boltzmann y el autoencoder variacional se utilizan cuando la distribución posterior no es manejable, por lo que se necesita aplicar algún tipo de aproximación. ¿Podría alguien decirme qué significa exactamente 'manejable', en una definición rigurosa? ¿O alguien podría explicar en alguno de los ejemplos que di arriba, qué significa exactamente "manejable" en ese contexto?
Respuestas
¿Demasiados anuncios?
Steve
Puntos
477
A mi mejor memoria, nunca me he encontrado con una definición formal de esto en un texto estadístico, pero creo que puedes armar una a partir de unas lecturas contextuales. Comienza con Análisis de Datos Bayesiano, p. 261:
La computación Bayesiana gira en torno a dos pasos: la computación de la distribución posterior, $p(\theta|y)$, y la computación de la distribución predictiva posterior, $p(\hat y|y)$. Hasta ahora hemos considerado ejemplos donde estos podrían ser calculados analíticamente en forma cerrada [.]
El obstáculo suele ser la verosimilitud marginal, el denominador en el lado derecho de la regla de Bayes, que podría involucrar una integral que no puede ser expresada analíticamente. Para más información, creo que encontrarás útil el artículo de wiki sobre expresión en forma cerrada (énfasis mío):
En matemáticas, una expresión en forma cerrada es una expresión matemática que puede ser evaluada en un número finito de operaciones. Puede contener constantes, variables, ciertas operaciones "bien conocidas" (por ejemplo, + − × ÷) y funciones (por ejemplo, raíz enésima, exponencial, logaritmo, funciones trigonométricas y funciones hiperbólicas inversas), pero usualmente sin límites. El conjunto de operaciones y funciones admitidas en una expresión en forma cerrada puede variar con el autor y el contexto.
Los problemas se dicen ser tratables si pueden resolverse en términos de una expresión en forma cerrada.
Si sigues leyendo, verás una tabla de clases de expresiones, y "Expresiones Analíticas" incluye varias involucradas en las constantes de normalización de las distribuciones de la familia exponencial. Por ejemplo, la función gamma en la distribución gamma, y la función de Bessel en la de von-Mises Fisher.
Es decir, estamos dispuestos a admitir al menos estas en nuestra definición de "tratabilidad". (Puede haber otras distribuciones que involucren las clases de operaciones clasificadas como "expresiones analíticas"; confieso que no estoy familiarizado.)
Harshiv
Puntos
4
Además de la respuesta de Sean Easter, intentaré arrojar algo de luz desde la perspectiva del costo computacional.
En primer lugar, definamos qué son los problemas tratables e intratables (Referencia: http://www.cs.ucc.ie/~dgb/courses/toc/handout29.pdf).
Problema Tratable: un problema que es solucionable por un algoritmo de tiempo polinómico. El límite superior es polinómico.
Problema Intratable: un problema que no puede ser resuelto por un algoritmo de tiempo polinómico. El límite inferior es exponencial.
Desde esta perspectiva, una definición para una distribución tratable es aquella que toma tiempo polinómico para calcular la probabilidad de esta distribución en cualquier punto dado.
Si una distribución está en una expresión en forma cerrada, la probabilidad de esta distribución definitivamente puede ser calculada en tiempo polinómico, lo cual, en el mundo académico, significa que la distribución es tratable. Las distribuciones intratables toman tiempo exponencial o más, lo cual generalmente significa que con los recursos computacionales existentes, nunca podremos calcular la probabilidad en un punto dado en un tiempo relativamente "corto" (cualquier tiempo mayor que tiempo polinómico se considera largo...).
Sam
Puntos
122
