Episodio
Sintesi di MCMC e propagazione delle convinzioni
con Sung-Soo Ahn
Markov Chain Monte Carlo (MCMC) e Belief Propagation (BP) sono gli algoritmi più diffusi per l'inferenza computazionale nei modelli grafici (GM). In linea di principio, MCMC è un metodo probabilistico esatto che, tuttavia, spesso soffre di mixaggio esponenzialmente lento. Al contrario, BP è un metodo deterministico, che in genere è veloce, empiricamente molto riuscito, ma in generale manca il controllo dell'accuratezza sui grafici a cicli. In questo documento vengono introdotti algoritmi MCMC che correggeranno l'errore di approssimazione di BP, ovvero forniamo un modo per compensare gli errori BP tramite un MCMC compatibile con BP consecutivo. Il framework si basa sull'approccio Di calcolo del ciclo (LC) che consente di esprimere l'errore BP come somma dei cicli generalizzati ponderati. Sebbene la serie completa sia intrattabile in modo computazionale, è noto che una serie troncata, sommando tutti i cicli regolari 2, è calcolabile in tempo polinomiale per le macchine virtuali binarie planari e fornisce anche un'approssimazione empiricamente accurata. Motivata da questo, prima di tutto, proporre uno schema MCMC di approssimazione polinomiale per la serie troncata di modelli binari generali (non planari). La nostra idea principale è usare l'algoritmo Worm, noto per fornire una combinazione rapida in altri problemi (correlati) e quindi progettare uno schema di rifiuto appropriato per campionare cicli regolari 2. Inoltre, abbiamo anche progettato uno schema MCMC efficiente senza rifiuto per approssimare la serie completa. La novità principale alla base del nostro design consiste nell'utilizzare il concetto di base del ciclo, che fornisce una scomposizione efficiente dei cicli generalizzati. In sostanza, gli schemi MCMC proposti vengono eseguiti su GM trasformato basato sulla soluzione BP non semplice, e i nostri esperimenti mostrano che questa sintesi di BP e MCMC supera le prestazioni sia dei sistemi MCMC diretti che bare BP.
Markov Chain Monte Carlo (MCMC) e Belief Propagation (BP) sono gli algoritmi più diffusi per l'inferenza computazionale nei modelli grafici (GM). In linea di principio, MCMC è un metodo probabilistico esatto che, tuttavia, spesso soffre di mixaggio esponenzialmente lento. Al contrario, BP è un metodo deterministico, che in genere è veloce, empiricamente molto riuscito, ma in generale manca il controllo dell'accuratezza sui grafici a cicli. In questo documento vengono introdotti algoritmi MCMC che correggeranno l'errore di approssimazione di BP, ovvero forniamo un modo per compensare gli errori BP tramite un MCMC compatibile con BP consecutivo. Il framework si basa sull'approccio Di calcolo del ciclo (LC) che consente di esprimere l'errore BP come somma dei cicli generalizzati ponderati. Sebbene la serie completa sia intrattabile in modo computazionale, è noto che una serie troncata, sommando tutti i cicli regolari 2, è calcolabile in tempo polinomiale per le macchine virtuali binarie planari e fornisce anche un'approssimazione empiricamente accurata. Motivata da questo, prima di tutto, proporre uno schema MCMC di approssimazione polinomiale per la serie troncata di modelli binari generali (non planari). La nostra idea principale è usare l'algoritmo Worm, noto per fornire una combinazione rapida in altri problemi (correlati) e quindi progettare uno schema di rifiuto appropriato per campionare cicli regolari 2. Inoltre, abbiamo anche progettato uno schema MCMC efficiente senza rifiuto per approssimare la serie completa. La novità principale alla base del nostro design consiste nell'utilizzare il concetto di base del ciclo, che fornisce una scomposizione efficiente dei cicli generalizzati. In sostanza, gli schemi MCMC proposti vengono eseguiti su GM trasformato basato sulla soluzione BP non semplice, e i nostri esperimenti mostrano che questa sintesi di BP e MCMC supera le prestazioni sia dei sistemi MCMC diretti che bare BP.
Per inviare suggerimenti, Invia un problema qui.