Markov Chains on Orbits of Permutation Groups

2014-08-09 · Mathias Niepert

We present a novel approach to detecting and utilizing symmetries in probabilistic graphical models with two main contributions. First, we present a scalable approach to computing generating sets of permutation groups representing the symmetries of graphical models. Second, we introduce orbital Markov chains, a novel family of Markov chains leveraging model symmetries to reduce mixing times. We establish an insightful connection between model symmetries and rapid mixing of orbital Markov chains. Thus, we present the first lifted MCMC algorithm for probabilistic graphical models. Both analytical and empirical results demonstrate the effectiveness and efficiency of the approach.

📄 PDF Abstract BibTeX arXiv:1408.2052

Code (0)

등록된 구현이 없습니다.

Analysis and FPGA based Implementation of Permutation Binary Neural Networks

2023-06-02 · Mikito Onuki, Kento Saka, Toshimichi Saito

This paper studies a permutation binary neural network characterized by local binary connections, global permutation connections, and the signum activation function. Depending on the permutation connections, the network …

Time Series

An Information-Theoretic Approach for Automatically Determining the Number of States when Aggregating Markov Chains

2021-07-05 · Isaac J. Sledge, Jose C. Principe

A fundamental problem when aggregating Markov chains is the specification of the number of state groups. Too few state groups may fail to sufficiently capture the pertinent dynamics of the original, high-order Markov cha…

Block-Value Symmetries in Probabilistic Graphical Models

2018-07-02 · Gagan Madan, Ankit Anand, Mausam, Parag Singla

One popular way for lifted inference in probabilistic graphical models is to first merge symmetric states into a single cluster (orbit) and then use these for downstream inference, via variations of orbital MCMC [Niepert…

Extending Conformal Prediction to Hidden Markov Models with Exact Validity via de Finetti's Theorem for Markov Chains

2022-10-05 · Buddhika Nettasinghe, Samrat Chatterjee, Ramakrishna Tipireddy, Mahantesh Halappanavar

Conformal prediction is a widely used method to quantify the uncertainty of a classifier under the assumption of exchangeability (e.g., IID data). We generalize conformal prediction to the Hidden Markov Model (HMM) frame…

Conformal Prediction Prediction valid

Learning Mixtures of Markov Chains with Quality Guarantees

2023-02-09 · Fabian Spaeh, Charalampos E. Tsourakakis

A large number of modern applications ranging from listening songs online and browsing the Web to using a navigation app on a smartphone generate a plethora of user trails. Clustering such trails into groups with a commo…