¿Garantías teóricas para los tiempos de ejecución de los métodos de propagación de creencias?

Se ha demostrado que la propagación de creencias es un método muy poderoso a través de la investigación en modelos gráficos probabilísticos.

Sin embargo, no sé nada sobre BP que sea comparable a los métodos MCMC donde podemos tener esquemas de aproximación aleatoria totalmente polinomiales (FPRAS) para problemas # P-completos.

¿Alguien podría señalarme algunas referencias?

cc.complexity-theory reference-request graph-algorithms machine-learning st.statistics Tianyang Li
fuente

Las versiones de propagación de creencias aparecen en los códigos de expansión y en la técnica espectral A de Alon & Kahale para colorear gráficos aleatorios de 3 colores (así como numerosos documentos posteriores que explotan sus ideas). Si bien eso responde su título hasta cierto punto, no responde el cuerpo de su pregunta.

Yuval Filmus

Por cierto, no recibí tu última oración. ¿Qué quiere decir con esto? "Métodos MCMC donde podemos tener esquemas de aproximación aleatoria completamente polinomiales (FPRAS) para problemas # P-completos". Cualquier puntero?

Daniel

@Daniel Estaba buscando resolver problemas usando BP donde tienen buenas garantías teóricas para el tiempo de ejecución.

Tianyang Li el

Entonces supongo que debe cambiar la declaración de su problema. Entendí algo diferente.

Daniel

Respuestas:

Se ha demostrado que BP y la mayoría de sus variantes convergen en gráficos sin ciclos. Cuando tienes ciclos, a veces muestran un comportamiento muy extraño. Para estos casos, las personas han probado diferentes esquemas de aproximaciones, por ejemplo, las Jerarquías Sherali-Adams, Lov? Asz-Schrijver y Lasserre.

Ver [1] para una revisión exhaustiva de estas aproximaciones. Además (Wainwright y Jordan, 2008) incluye otra clase de aproximaciones.

[1] http://cs.nyu.edu/~dsontag/papers/sontag_phd_thesis.pdf

Daniel
fuente

Esta es también la razón por la cual la propagación de encuestas (un primo de propagación de creencias) funciona tan bien para resolver grandes problemas aleatorios de 3-SAT. Para gráficos de factores aleatorios, localmente, el gráfico parece un árbol y, por lo tanto, la propagación de encuestas puede progresar.

user834

Aquí hay un artículo en el que los autores utilizaron BP para obtener un esquema de aproximación aleatoria de tiempo completamente polinomial para el problema de flujo de red de costo mínimo capacitado.

Tianyang Li
fuente