The assumption that data samples are independently identically distributed is the backbone of many learning algorithms. Nevertheless, datasets often exhibit rich structures in practice, and we argue that there exist some unknown orders within the data instances. Aiming to find such orders, we introduce a novel Generative Markov Network (GMN) which we use to extract the order of data instances automatically. Specifically, we assume that the instances are sampled from a Markov chain. Our goal is to learn the transitional operator of the chain as well as the generation order by maximizing the generation probability under all possible data permutations. One of our key ideas is to use neural networks as a soft lookup table for approximating the possibly huge, but discrete transition matrix. This strategy allows us to amortize the space complexity with a single model and make the transitional operator generalizable to unseen instances. To ensure the learned Markov chain is ergodic, we propose a greedy batch-wise permutation scheme that allows fast training.   Empirically, we evaluate the learned Markov chain by showing that GMNs are able to discover orders among data instances and also perform comparably well to state-of-the-art methods on the one-shot recognition benchmark task. Recent advances in deep neural networks offer great potentials for machines to learn automatically without humans interventions. For instance, Convolutional Neural Networks (CNNs) BID16 provided an automated way for learning image feature representations. Compared to hand-crafted ones such as SIFT and SURF, these hierarchical deep features demonstrate superior performance in recognition BID35 and transfer learning BID7 problems. Another example would be learning to learn for automatic parameter estimation. BID0 proposed to update model parameters without any pre-defined update rule such as stochastic gradient descent (SGD) or ADAM . Surprisingly, this update-rule-free framework showed better performance and faster convergence on both object recognition and image style transformation tasks. In our paper, we investigate the following novel question: given an unordered dataset where instances may be exhibiting some implicit order, can we order a dataset automatically according to this order?We argue that such order often exists even when we are dealing with the data that are naturally thought of as being i.i.d. sampled from a common though complex distribution. For example, let's consider a dataset consisting of the joint locations on the body of the same person taken on different days. The data i.i.d. assumption is justified since postures of a person took on different days are likely unrelated. However , we can arrange the data instances such that the joints follow an articulated motion or a set of motions in a way that makes each pose highly predictable given the previous ones. Although this arrangement depends on the person as ballerinas' poses might obey different dynamics than the poses of tennis players, the simultaneous inference on the pose dynamics can lead to a robust model that explains the correlations among joints. To put it differently, if we reshuffle the frames of a video clip, the data can now be modeled by an i.i.d. model. Nevertheless , reconstructing the order leads to an alternative model where transitions between the frames are easier to fit the links between the latent structures and observations. The ballerina 's dancing, if sampled very sparsely, can be thought of as a reshuffled video sequence that needs to be reordered such that a temporal model can generate it.One naive and obvious way to find the order in a dataset is to perform sorting based on a predefined distance metric; e.g., the Euclidean distance between image pixel values. However, the distance metrics have to be predefined differently and empirically according to distinct types/characteristics of the datasets at hand. A proper distance metric for one domain may not be a good one for other domains. For instance, p distance is a good measure for DNA/RNA sequences BID23 while it does not characterize the semantic distances between images. We argue that the key component of the ordering problem lies in the discovery of proper distance metric in an automatic and adaptive way.To approach this problem, we propose to learn a distance-metric-free model to discover the ordering in the dataset. More specifically, we model the data by treating them as if they were generated from a Markov chain. We propose to simultaneously train the transitional operator and find the best order by a joint optimization over the parameter space as well as all possible permutations. We term our model Generative Markov Networks (GMNs). One of the key ideas in the design of GMNs is to use neural networks as a soft lookup table to approximate the possibly huge but discrete transition matrix. This strategy allows GMNs to amortize the space complexity using a unified model. Furthermore, due to the differentiable property of neural networks, the transitional operator of GMNs can also generalize on unseen but similar data instances. As an additional contribution, to ensure the Markov chain learned by GMNs is ergodic, we propose a greedy batch-wise permutation scheme that allows fast training.One related task is one-shot recognition which has only one labeled data per category in the target domain. Most of the work in this area considered learning a specific distance metric BID15 BID33 BID28 or category-separation metric BID24 for the data. During the inference phase, they computed either the smallest distance or highest class prediction score between the support and query instances. Alternatively, from a generative modeling perspective, we can first generate the Markov chain for the support instances, then we fit the query instances into the Markov chain and decide the labels with the highest log-likelihood.Empirically, we evaluate the learned Markov chain by showing that GMNs are able to discover implicit orders among data instances and also perform comparably well to state-of-the-art methods on the benchmark one-shot recognition task. In this section we give a detailed description on how to implement the transitional operator where the state can be both discrete or continuous. At the first step, to prevent our GMNs from simply memorizing all the training data and their transitions, we introduce stochastic latent variables z 2 R z via Variational Bayes Inference BID34 . The evidence lower bound (ELBO) of the log likelihood for the transitional operator (i.e., log T (s 0 |s; ✓)) becomes: DISPLAYFORM0 where T (s 0 |s; ✓) has been replaced by a distribution P(s 0 |s, z; ) parametrized by , which allows us to make the dependence of s on z. Moreover, KL is the KL-divergence, Q(z|s; ) is an encoder function parametrized by that encodes latent code z given current state s, and P(z) is a fixed prior which we take its form as Gaussian distribution N (0, I). We use reparametrized trick to draw Q(z|s; ) from Gaussian N µ Q, (s), 2 Q, (s)I where µ Q, (s) and Q, (s) are learnable functions.Next, we consider two types of distribution family for P(s 0 |s, z; ✓): Bernoulli and Gaussian. If s 2 {0, 1} p (i.e., a binary image), we define log P(s 0 |s, z; ) as: DISPLAYFORM1 where is element-wise multiplication and g (s, z) : DISPLAYFORM2 If s 2 R p (i.e., a real-valued feature vector), we choose P(s 0 |s, z; ) to be fixed variance factored DISPLAYFORM3 ⌘ , where µ P, (s, z) : R p+z ! R p and P is a fixed variance. We simply choose P in all the experiments. log P(s 0 |s, z; ✓) can thus be defined as DISPLAYFORM4 where const. is not related to the optimization of .For simplicity, we specify ✓ = { [ }. Therefore , the model parameters update for ✓ in (2) refers to the updates for and . In this paper, we argue that data i.i.d. assumption is not always the case in most of the datasets. Often, data instances are exhibiting some implicit orders which may benefit our understanding and analysis of the dataset. To observe the implicit orders, we propose a novel Generative Markov Network which considers a Markov chain data generation scheme. Specifically, we simultaneously learn the transitional operator as a generative model in the Markov chain as well as find the optimal orders of the data under all possible permutations. In lots of experiments, we show that our model is able to observe implicit orders from unordered datasets and also perform well on the one-shot recognition task.
Propose to observe implicit orders in datasets in a generative model viewpoint. The authors deal with the problem of implicit ordering in a dataset and the challenge of recovering it and propose to learn a distance-metric-free model that assumes a Markov chain as the generative mechanism of the data  The paper proposes “Generative Markov Networks” - a deep-learning-based approach to modeling sequences and discovering order in datasets. Proposes learning the order of an unordered data sample by learning a Markov chain.